摘  要： 針對在Linux操作系統(tǒng)原有的路由體系結(jié)構(gòu)上實(shí)現(xiàn)按需路由的制約問題，分析了Linux操作系統(tǒng)路由體系結(jié)構(gòu)特點(diǎn)以及實(shí)現(xiàn)按需路由的難點(diǎn),，提出了一種適合按需路由的通用路由體系結(jié)構(gòu),，并基于Linux系統(tǒng)實(shí)現(xiàn)了按需路由之一的Aodv路由協(xié)議的嵌入式實(shí)現(xiàn)。結(jié)果表明了此路由體系結(jié)構(gòu)很好地解決了Linux傳統(tǒng)的路由體系結(jié)構(gòu)瓶頸,。
關(guān)鍵詞： 按需路由,；嵌入式系統(tǒng)；路由體系結(jié)構(gòu),；Ad hoc

　Ad hoc網(wǎng)絡(luò)[1]是一種特殊的對等式網(wǎng)絡(luò),，它不需要固定的通信設(shè)施支持即可快速建立無線網(wǎng)絡(luò)，其最初的動(dòng)機(jī)是滿足戰(zhàn)場生存的軍事需求,。由于其自組能力,、低成本、工作壽命長等特點(diǎn),，Ad hoc網(wǎng)絡(luò)逐漸進(jìn)入了民用和商用領(lǐng)域,，遺憾的是發(fā)展較為緩慢。其主要原因之一就是Ad hoc路由協(xié)議通常采用新的路由模式,，并不支持目前操作系統(tǒng)路由體系結(jié)構(gòu),。若沒有通用的操作系統(tǒng)路由體系結(jié)構(gòu)解決方案，路由算法研究員就得被迫進(jìn)行低級(jí)系統(tǒng)程序設(shè)計(jì),，而且往往會(huì)無計(jì)劃地更改系統(tǒng)內(nèi)部,，以獲得更多功能的Ad hoc路由要求，這容易導(dǎo)致系統(tǒng)不穩(wěn)定,。許多研究人員為了回避這種低級(jí)系統(tǒng)程序設(shè)計(jì),，大多從事基于仿真路由算法工作[2-3]而很少真正在產(chǎn)品或嵌入式上實(shí)現(xiàn)，所以實(shí)際應(yīng)用價(jià)值不大,。為了加速Ad hoc網(wǎng)絡(luò)民用商用產(chǎn)品發(fā)展,，設(shè)計(jì)一個(gè)Ad hoc通用嵌入式系統(tǒng)路由體系結(jié)構(gòu)迫在眉睫，Ad hoc 網(wǎng)絡(luò)和嵌入式系統(tǒng)相結(jié)合是必然的,。在嵌入式系統(tǒng)下實(shí)現(xiàn)無線自組網(wǎng)才有實(shí)際應(yīng)用意義,。
　針對上述問題，本文首先分析了Linux操作系統(tǒng)的原有工作方式以及在此體系結(jié)構(gòu)上實(shí)現(xiàn)按需路由協(xié)議的問題,，并給出了合理的解決方案,。提出一種基于Linux操作系統(tǒng)實(shí)現(xiàn)通用的按需路由協(xié)議[4]體系結(jié)構(gòu),，使Ad hoc研究員易于在此路由體系結(jié)構(gòu)上進(jìn)行路由算法編程，而不用進(jìn)行底層內(nèi)核系統(tǒng)編程,。最后,，本文根據(jù)此方案實(shí)現(xiàn)Aodv路由協(xié)議并應(yīng)用在實(shí)際的網(wǎng)絡(luò)中，從而驗(yàn)證方案的性能及可行性,。
1 Linux系統(tǒng)現(xiàn)有路由體系結(jié)構(gòu)
　目前的主流網(wǎng)絡(luò)體系結(jié)構(gòu)一般將路由功能分為兩部分：分組轉(zhuǎn)發(fā)功能模塊和分組尋路功能模塊[5],。分組轉(zhuǎn)發(fā)是指根據(jù)內(nèi)核路由表(轉(zhuǎn)發(fā)表)的信息，將需要發(fā)送的數(shù)據(jù)分組,，通過指定的網(wǎng)絡(luò)接口發(fā)送到下一跳的節(jié)點(diǎn),。分組尋路是指建立轉(zhuǎn)發(fā)表的過程，實(shí)現(xiàn)路由協(xié)議的邏輯計(jì)算,，根據(jù)與其他主機(jī)交換的路由信息,，計(jì)算出到其他節(jié)點(diǎn)的正確路由。轉(zhuǎn)發(fā)表含有充分的信息來完成轉(zhuǎn)發(fā)使命,，而路由表中包含路由算法用于發(fā)現(xiàn)和維護(hù)路由的信息,。
　在通用的嵌入式開源操作系統(tǒng)之一的Linux操作系統(tǒng)的體系結(jié)構(gòu)中，分組轉(zhuǎn)發(fā)功能模塊的轉(zhuǎn)發(fā)表是在內(nèi)核空間實(shí)現(xiàn)的,，在查找內(nèi)核轉(zhuǎn)發(fā)表的時(shí)候,，根據(jù)轉(zhuǎn)發(fā)表項(xiàng)的最佳匹配原則進(jìn)行轉(zhuǎn)發(fā)。如果找不到匹配的轉(zhuǎn)發(fā)表項(xiàng),，則按缺省路由發(fā)送,，一般是將網(wǎng)關(guān)作為缺省路由的下一跳節(jié)點(diǎn)。如果缺省路由又不存在,，操作系統(tǒng)則將把這個(gè)數(shù)據(jù)分組丟棄,。分組尋路功能模塊可以在內(nèi)核空間實(shí)現(xiàn)，也可以在用戶空間實(shí)現(xiàn),。本文采用在用戶空間實(shí)現(xiàn)[6],，如圖1所示。

　把分組轉(zhuǎn)發(fā)功能模塊和分組尋路功能模塊分開的主要原因是數(shù)據(jù)分組轉(zhuǎn)發(fā)必須盡可能快且有效地遍歷轉(zhuǎn)發(fā)表,，故分組轉(zhuǎn)發(fā)功能模塊需駐留在內(nèi)核中,。然而分組尋路功能模塊涉及復(fù)雜的數(shù)據(jù)分組或內(nèi)存密集型讀寫任務(wù)，所以應(yīng)該置于內(nèi)核外,。這種分離的原則使Linux操作系統(tǒng)中的路由既有效率又靈活,。
2 按需路由協(xié)議實(shí)現(xiàn)的關(guān)鍵問題

　目前大多數(shù)通用嵌入式操作系統(tǒng)中的路由體系結(jié)構(gòu)都是按照有線網(wǎng)絡(luò)路由協(xié)議的方式來構(gòu)造的，這些路由協(xié)議為主動(dòng)路由協(xié)議,。在這種路由體系結(jié)構(gòu)上,，只能實(shí)現(xiàn)Ad hoc主動(dòng)路由協(xié)議(如Dsdv路由協(xié)議)，而不能實(shí)現(xiàn)Ad hoc按需路由協(xié)議(如Aodv、Dsr路由協(xié)議),。本文將探討不能在通用路由體系結(jié)構(gòu)實(shí)現(xiàn)Ad hoc按需路由協(xié)議三個(gè)關(guān)鍵的難點(diǎn),。
　(1)當(dāng)發(fā)送數(shù)據(jù)分組的時(shí)候，如果不存在從節(jié)點(diǎn)到目的地址的路由,，則需要發(fā)起路由查找過程,，但在通常情況下,，沒有路由匹配,，內(nèi)核將立即刪除該數(shù)據(jù)包。然而,，這不是一個(gè)按需臨時(shí)路由想要的情況,。在按需路由中，并不是所有的路線被固定安排好,，有些路線是必須在需要的時(shí)候“發(fā)現(xiàn)”,。所以在這種情況下，正確的行為應(yīng)該是請求發(fā)現(xiàn)路由,，并在路由表更新路由或?qū)ふ医Y(jié)束以前,，數(shù)據(jù)分組將不會(huì)被發(fā)送出去或者丟棄處理。
　(2)需要建立一個(gè)緩沖區(qū),，在按需路由協(xié)議等待路由發(fā)現(xiàn)的過程中,，數(shù)據(jù)分組需要進(jìn)入一個(gè)緩沖區(qū)，該緩沖區(qū)設(shè)置在內(nèi)核外,，因?yàn)榭蓽p少內(nèi)存和CPU的負(fù)荷,。
　(3)為了減少查找內(nèi)核路由表的代價(jià)，就需要定期維護(hù)更新這路由表,，即時(shí)把失效的路由清除,。為了實(shí)現(xiàn)這功能，需要建立一個(gè)路由檢查表,。所有表都有一個(gè)相關(guān)定時(shí)器,，當(dāng)該表的路由被使用時(shí)，它的定時(shí)器就必須重置,。當(dāng)定時(shí)器的時(shí)間用完時(shí),，則該表項(xiàng)就要從內(nèi)核路由表中刪除。關(guān)鍵問題是內(nèi)核中沒有記錄路由使用的機(jī)制,，所以路由守護(hù)進(jìn)程根本無法知道內(nèi)核中使用過哪些路由或什么時(shí)候使用過路由,。
　以上分析可知目前通用嵌入式操作系統(tǒng)沒有這種機(jī)制來支持上述行為，所以通用的嵌入式系統(tǒng)應(yīng)該為Ad hoc網(wǎng)增加以下系統(tǒng)功能：
　(1)判斷是否是按需路由,，如果是,，則查看是否有路由請求；
　(2)把請求告知Ad hoc守護(hù)進(jìn)程；
　(3)建立一個(gè)高速緩沖區(qū),，將需要路由請求的數(shù)據(jù)分組送到緩沖區(qū),；
　(4)當(dāng)路由發(fā)現(xiàn)完成或發(fā)現(xiàn)失敗，將數(shù)據(jù)分組注入內(nèi)核中或?qū)ζ鋻仐墶?br /> 　(5)建立路由檢查表,，且能定期對其維護(hù),，以便能更新內(nèi)核路由表。
3 通用的按需路由體系設(shè)計(jì)實(shí)現(xiàn)方案
3.1 Ad hoc按需路由協(xié)議體系結(jié)構(gòu)
　針對本文提出的問題,，所設(shè)計(jì)的按需路由體系如圖2所示,。

3.2 Ad hoc按需路由協(xié)議體系結(jié)構(gòu)組成
　通用的Ad hoc按需路由協(xié)議架構(gòu)主要組成有：操作系統(tǒng)原有的內(nèi)核轉(zhuǎn)發(fā)表(本文不對其修改)、一個(gè)可加載的內(nèi)核模塊route_check(即路由檢查表),、netfiilter鉤子程序[7],、用戶空間的Ad hoc支持庫ASL(Ad hoc Support Library)和Ad hoc路由守護(hù)進(jìn)程。netfiilter鉤子程序是系統(tǒng)自帶的,，用來捕捉每一個(gè)發(fā)送數(shù)據(jù)分組,，記錄每條路由的最后使用時(shí)間，然后對路由檢查表做相應(yīng)的處理,，路由檢查表約800行代碼,。其中，ASL是一個(gè)共享庫,，約2 500行代碼,，用來實(shí)現(xiàn)按需路由功能。當(dāng)ASL接到一個(gè)延時(shí)發(fā)送的數(shù)據(jù)分組,，就會(huì)告知Ad hoc守護(hù)進(jìn)程,，以便對數(shù)據(jù)分組的目的地址進(jìn)行路由發(fā)現(xiàn)。之后它將該數(shù)據(jù)分組儲(chǔ)存在一個(gè)臨時(shí)緩沖區(qū)中,，等待守護(hù)進(jìn)程返回路由發(fā)現(xiàn)的結(jié)果,。一旦這些處理完成，相應(yīng)的內(nèi)核路由表就加入新的元組,，數(shù)據(jù)分組移出緩沖區(qū),，重新注入到包轉(zhuǎn)發(fā)功能塊的隊(duì)列中。ASL基本函數(shù)如表1所示,。

3.3 Ad hoc按需路由協(xié)議體系結(jié)構(gòu)數(shù)據(jù)分組傳遞流程
　在實(shí)現(xiàn)方案中,，為了確認(rèn)是否有路由請求，利用一個(gè)系統(tǒng)不用的隧道設(shè)備,，Universal TUN/TAP(tun)[8],，此設(shè)備虛擬了一個(gè)網(wǎng)絡(luò)接口，當(dāng)數(shù)據(jù)分組發(fā)送的時(shí)候,，如果目的地址不存在其路由,，則這些數(shù)據(jù)分組將tun作為缺省路由的下一跳“接口”,。這樣就可以通過/dev/net/tun設(shè)備將所有需要路由發(fā)現(xiàn)的數(shù)據(jù)分組傳遞到用戶空間做進(jìn)一步的處理。
　處理工作第一步為調(diào)用open_route_request()函數(shù)來打開,。當(dāng)一個(gè)新的數(shù)據(jù)包從/dev/net/tun中讀出時(shí),，Ad hoc守護(hù)進(jìn)程就會(huì)利用read_route_request()函數(shù)讀取路由請求，之后就可以初始化路由發(fā)現(xiàn),。同時(shí),，數(shù)據(jù)分組會(huì)在一個(gè)臨時(shí)緩沖區(qū)排隊(duì)。因?yàn)榫彌_區(qū)在用戶空間,，所以可以有一個(gè)較大的緩沖區(qū)來存儲(chǔ)數(shù)據(jù)分組,，這樣即使分組在路由發(fā)現(xiàn)延時(shí)很大的情況下也不會(huì)出現(xiàn)丟失的情況。在路由發(fā)現(xiàn)成功完成以后,，就將數(shù)據(jù)分組通過raw socket重新注入內(nèi)核,。
　為了保持路由表的有效性，內(nèi)核可加載模塊route_check在Netfilter的NF_IP_POST_ROUTING鉤子中注冊,，這樣每個(gè)外出的數(shù)據(jù)包都要經(jīng)過這個(gè)模塊。該模塊只是查看數(shù)據(jù)包的首部,，更新相應(yīng)的時(shí)間戳值,，并輸出到/proc/asl/route_check中。ASL通過API中的query_route_idle_time()告知Ad hoc路由守護(hù)進(jìn)程內(nèi)核路由表的使用情況,，這樣守護(hù)進(jìn)程就可以檢查路由的更新和刪除內(nèi)核路由表失去時(shí)效的路由,。
route_add()和route_del()函數(shù)使用ioct()接口加入或者刪除內(nèi)核中的路由。
4 Aodv按需路由協(xié)議架構(gòu)
　通過上述設(shè)計(jì)架構(gòu),，在不用改變系統(tǒng)的內(nèi)核情況下,，就可以實(shí)現(xiàn)移動(dòng)自組網(wǎng)按需路由協(xié)議在通用的操作系統(tǒng)上的應(yīng)用。
　圖3是根據(jù)Aodv基本的路由功能(如RREQ,、RREP,、RERR等路由功能)，置入通用分組尋路功能模塊使其成為Aodv專用的分組尋路功能模塊,，如圖3所示,。

5 方案實(shí)施驗(yàn)證分析
　實(shí)驗(yàn)現(xiàn)場為華僑大學(xué)廈門軟件園嵌入式技術(shù)開放實(shí)驗(yàn)室(廈門軟件園二期54號(hào)402，華僑大學(xué)產(chǎn)學(xué)研基地),。網(wǎng)絡(luò)節(jié)點(diǎn)由兩個(gè)PC機(jī)節(jié)點(diǎn)和一個(gè)嵌入式系統(tǒng)節(jié)點(diǎn)組成,。PC機(jī)節(jié)點(diǎn)配置是DELL工作站PY597 + ZD1211b無線網(wǎng)卡，安裝CentOS 5操作系統(tǒng)(內(nèi)核版本號(hào)為26.18-128.e15),，加載Aodv路由協(xié)議模塊,，支持直接或多跳的通信。嵌入式系統(tǒng)節(jié)點(diǎn)配置則為致遠(yuǎn)MagicARM2410 + Asus WL-167無線網(wǎng)卡,，加載Aodv路由協(xié)議模塊,，支持直接或多跳的通信,。PC1的IP為192.168.0.5；PC2的IP為192.168.0.55,；K1的IP為192.168.0.45,。網(wǎng)絡(luò)拓?fù)淙鐖D4所示。

　由于測試區(qū)域較小,，節(jié)點(diǎn)PC1不需要經(jīng)過中繼節(jié)點(diǎn)K1就可直接到達(dá)節(jié)點(diǎn)PC2,。為了測試Aodv路由協(xié)議的“跳轉(zhuǎn)”功能，采取屏蔽策略,，使PC1與PC2相互屏蔽,。
　(1)PC1對PC2的屏蔽
　在PC1執(zhí)行：iptables -A INPUT -p ALL -m mac --mac-source 00：02：72：61：ED：4B -j DROP。其中,，00：02：72：61：ED：4B為PC2的Mac地址,，使得PC1拒絕PC2發(fā)送的數(shù)據(jù)包。
　(2)PC2對PC1的屏蔽
　在PC2執(zhí)行：iptables -A INPUT -p ALL -m mac --mac-source 00：02：72：61：ED：53 -j DROP,。其中,，00：02：72：61：ED：53為PC1的Mac地址，使得PC2拒絕PC1發(fā)送的數(shù)據(jù)包,。
?、貹1節(jié)點(diǎn)定期廣播傳送HELLO消息，發(fā)現(xiàn)了附近的兩個(gè)節(jié)點(diǎn)PC1和PC2,，如圖5所示,。

　②PC1節(jié)點(diǎn)定期廣播傳送HELLO消息,，先發(fā)現(xiàn)了附近的K1節(jié)點(diǎn),，然后透過K1發(fā)現(xiàn)了PC2，并對其建立路由,。如圖6所示,。

　③PC1節(jié)點(diǎn)Ping PC2節(jié)點(diǎn),，信息返回成功,，如圖7所示。

　從Ping命令的輸出結(jié)果中可以看到,，數(shù)據(jù)包所經(jīng)過的路徑是PC1→K1→PC2→K1→PC1,。經(jīng)過K1節(jié)點(diǎn)上　Aodv模塊的路由功能將Ping數(shù)據(jù)包轉(zhuǎn)發(fā)，使得不能直接通信的節(jié)點(diǎn)PC1和PC2實(shí)現(xiàn)了數(shù)據(jù)傳輸,，具有了路由發(fā)現(xiàn)和網(wǎng)絡(luò)自組的功能,。
　本文提出按需路由協(xié)議的實(shí)現(xiàn)方案，充分考慮了按需路由的特點(diǎn),，針對按需路由在linux嵌入式環(huán)境下實(shí)現(xiàn)的難點(diǎn),，提出了解決方案和設(shè)計(jì)實(shí)現(xiàn)方案,，其功能函數(shù)具有良好的通用性。該方案為以后研究員驗(yàn)證和比較各種協(xié)議在實(shí)際網(wǎng)絡(luò)中的性能提供了良好的基礎(chǔ),。
參考文獻(xiàn)
[1] HARTENSTEIN H. Topics in ad hoc and sensor networks - A tutorial survey on vehicular ad hoc networks[J]. IEEE Communications Magazine,，2008，46(6).
[2] GIOVANARDI A,， MAZZINI G. Ad hoc routing protocols： emulation vs simulation[C]. 2nd International Symposium on Wireless Communication Systems,， 2005：140-144.
[3] BOUKHALKHAL A， YAGOUBI M B,， DJOUDI M,， et al.Simulation of mobile ad hoc routing strategies[C]. 4th International Conference on Innovations in Information Technologies， Dubai,， United Arab Emirates,， 2007：128-132.
[4] 余旭濤，畢光國.Ad Hoc網(wǎng)絡(luò)按需路由協(xié)議的改進(jìn)[J].計(jì)算機(jī)學(xué)報(bào),，2004,，27(6).
[5] PETERSON  L L，DAVIE B S. Computer networks：a system approach[M]. Morgan Kaufmann Publishers,， 2nd edition,， 2000.
[6] RANDHAWA T， RICHAROS J. Implementation of a kernel mode IPv6 AODV routing daemon to improve data throughput[C]. 2005 IEEE International Conference on Communications (ICC 2005),， 2005(5)：16-20.
[7] Netfilter/Iptable homepage[EB/OL]. http： //www.netfilter.org，2005-09.
[8] Tun/Tap universal driver[EB/OL].http：//vtun.sourceforge.net/tun/,， 2005-10.