摘  要： 針對在Linux操作系統(tǒng)原有的路由體系結(jié)構(gòu)上實現(xiàn)按需路由的制約問題，分析了Linux操作系統(tǒng)路由體系結(jié)構(gòu)特點以及實現(xiàn)按需路由的難點，提出了一種適合按需路由的通用路由體系結(jié)構(gòu)，并基于Linux系統(tǒng)實現(xiàn)了按需路由之一的Aodv路由協(xié)議的嵌入式實現(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ò)，其最初的動機(jī)是滿足戰(zhà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)行低級系統(tǒng)程序設(shè)計，而且往往會無計劃地更改系統(tǒng)內(nèi)部，以獲得更多功能的Ad hoc路由要求，這容易導(dǎo)致系統(tǒng)不穩(wěn)定。許多研究人員為了回避這種低級系統(tǒng)程序設(shè)計，大多從事基于仿真路由算法工作[2-3]而很少真正在產(chǎn)品或嵌入式上實現(xiàn)，所以實際應(yīng)用價值不大。為了加速Ad hoc網(wǎng)絡(luò)民用商用產(chǎn)品發(fā)展，設(shè)計一個Ad hoc通用嵌入式系統(tǒng)路由體系結(jié)構(gòu)迫在眉睫，Ad hoc 網(wǎng)絡(luò)和嵌入式系統(tǒng)相結(jié)合是必然的。在嵌入式系統(tǒng)下實現(xiàn)無線自組網(wǎng)才有實際應(yīng)用意義。
　針對上述問題，本文首先分析了Linux操作系統(tǒng)的原有工作方式以及在此體系結(jié)構(gòu)上實現(xiàn)按需路由協(xié)議的問題，并給出了合理的解決方案。提出一種基于Linux操作系統(tǒng)實現(xiàn)通用的按需路由協(xié)議[4]體系結(jié)構(gòu)，使Ad hoc研究員易于在此路由體系結(jié)構(gòu)上進(jìn)行路由算法編程，而不用進(jìn)行底層內(nèi)核系統(tǒng)編程。最后，本文根據(jù)此方案實現(xiàn)Aodv路由協(xié)議并應(yīng)用在實際的網(wǎng)絡(luò)中，從而驗證方案的性能及可行性。
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é)點。分組尋路是指建立轉(zhuǎn)發(fā)表的過程，實現(xiàn)路由協(xié)議的邏輯計算，根據(jù)與其他主機(jī)交換的路由信息，計算出到其他節(jié)點的正確路由。轉(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)核空間實現(xiàn)的，在查找內(nèi)核轉(zhuǎn)發(fā)表的時候，根據(jù)轉(zhuǎn)發(fā)表項的最佳匹配原則進(jìn)行轉(zhuǎn)發(fā)。如果找不到匹配的轉(zhuǎn)發(fā)表項，則按缺省路由發(fā)送，一般是將網(wǎng)關(guān)作為缺省路由的下一跳節(jié)點。如果缺省路由又不存在，操作系統(tǒng)則將把這個數(shù)據(jù)分組丟棄。分組尋路功能模塊可以在內(nèi)核空間實現(xiàn)，也可以在用戶空間實現(xiàn)。本文采用在用戶空間實現(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é)議實現(xiàn)的關(guān)鍵問題

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

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

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

5 方案實施驗證分析
　實驗現(xiàn)場為華僑大學(xué)廈門軟件園嵌入式技術(shù)開放實驗室(廈門軟件園二期54號402，華僑大學(xué)產(chǎn)學(xué)研基地)。網(wǎng)絡(luò)節(jié)點由兩個PC機(jī)節(jié)點和一個嵌入式系統(tǒng)節(jié)點組成。PC機(jī)節(jié)點配置是DELL工作站PY597 + ZD1211b無線網(wǎng)卡，安裝CentOS 5操作系統(tǒng)(內(nèi)核版本號為26.18-128.e15)，加載Aodv路由協(xié)議模塊，支持直接或多跳的通信。嵌入式系統(tǒng)節(jié)點配置則為致遠(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é)點PC1不需要經(jīng)過中繼節(jié)點K1就可直接到達(dá)節(jié)點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é)點定期廣播傳送HELLO消息，發(fā)現(xiàn)了附近的兩個節(jié)點PC1和PC2，如圖5所示。

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

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

　從Ping命令的輸出結(jié)果中可以看到，數(shù)據(jù)包所經(jīng)過的路徑是PC1→K1→PC2→K1→PC1。經(jīng)過K1節(jié)點上　Aodv模塊的路由功能將Ping數(shù)據(jù)包轉(zhuǎn)發(fā)，使得不能直接通信的節(jié)點PC1和PC2實現(xiàn)了數(shù)據(jù)傳輸，具有了路由發(fā)現(xiàn)和網(wǎng)絡(luò)自組的功能。
　本文提出按需路由協(xié)議的實現(xiàn)方案，充分考慮了按需路由的特點，針對按需路由在linux嵌入式環(huán)境下實現(xiàn)的難點，提出了解決方案和設(shè)計實現(xiàn)方案，其功能函數(shù)具有良好的通用性。該方案為以后研究員驗證和比較各種協(xié)議在實際網(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ī)學(xué)報，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.