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

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

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

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

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

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

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

　由于測試區(qū)域較小，節(jié)點PC1不需要經過中繼節(jié)點K1就可直接到達節(jié)點PC2。為了測試Aodv路由協(xié)議的“跳轉”功能，采取屏蔽策略，使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ā)送的數據包。
　(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ā)送的數據包。
?、貹1節(jié)點定期廣播傳送HELLO消息，發(fā)現了附近的兩個節(jié)點PC1和PC2，如圖5所示。

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

?、跴C1節(jié)點Ping PC2節(jié)點，信息返回成功，如圖7所示。

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