基于Linux嵌入式系統按需路由協議架構設計與實現＊

謝毅勇 ，謝維波

(1.華僑大學 計算機科學與技術學院，福建 廈門 361021；2.華僑大學 廈門軟件園嵌入式技術開放實驗室，福建 廈門 361008)

Ad hoc網絡[1]是一種特殊的對等式網絡，它不需要固定的通信設施支持即可快速建立無線網絡，其最初的動機是滿足戰場生存的軍事需求。由于其自組能力、低成本、工作壽命長等特點，Ad hoc網絡逐漸進入了民用和商用領域，遺憾的是發展較為緩慢。其主要原因之一就是Ad hoc路由協議通常采用新的路由模式，并不支持目前操作系統路由體系結構。若沒有通用的操作系統路由體系結構解決方案，路由算法研究員就得被迫進行低級系統程序設計，而且往往會無計劃地更改系統內部，以獲得更多功能的Ad hoc路由要求，這容易導致系統不穩定。許多研究人員為了回避這種低級系統程序設計，大多從事基于仿真路由算法工作[2-3]而很少真正在產品或嵌入式上實現，所以實際應用價值不大。為了加速Ad hoc網絡民用商用產品發展，設計一個Ad hoc通用嵌入式系統路由體系結構迫在眉睫，Ad hoc網絡和嵌入式系統相結合是必然的。在嵌入式系統下實現無線自組網才有實際應用意義。

針對上述問題，本文首先分析了Linux操作系統的原有工作方式以及在此體系結構上實現按需路由協議的問題，并給出了合理的解決方案。提出一種基于Linux操作系統實現通用的按需路由協議[4]體系結構，使Ad hoc研究員易于在此路由體系結構上進行路由算法編程，而不用進行底層內核系統編程。最后，本文根據此方案實現Aodv路由協議并應用在實際的網絡中，從而驗證方案的性能及可行性。

1 Linux系統現有路由體系結構

目前的主流網絡體系結構一般將路由功能分為兩部分：分組轉發功能模塊和分組尋路功能模塊[5]。分組轉發是指根據內核路由表(轉發表)的信息，將需要發送的數據分組，通過指定的網絡接口發送到下一跳的節點。分組尋路是指建立轉發表的過程，實現路由協議的邏輯計算，根據與其他主機交換的路由信息，計算出到其他節點的正確路由。轉發表含有充分的信息來完成轉發使命，而路由表中包含路由算法用于發現和維護路由的信息。

在通用的嵌入式開源操作系統之一的Linux操作系統的體系結構中，分組轉發功能模塊的轉發表是在內核空間實現的，在查找內核轉發表的時候，根據轉發表項的最佳匹配原則進行轉發。如果找不到匹配的轉發表項，則按缺省路由發送，一般是將網關作為缺省路由的下一跳節點。如果缺省路由又不存在，操作系統則將把這個數據分組丟棄。分組尋路功能模塊可以在內核空間實現，也可以在用戶空間實現。本文采用在用戶空間實現[6]，如圖 1所示。

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

2 按需路由協議實現的關鍵問題

目前大多數通用嵌入式操作系統中的路由體系結構都是按照有線網絡路由協議的方式來構造的，這些路由協議為主動路由協議。在這種路由體系結構上，只能實現 Ad hoc主動路由協議(如 Dsdv路由協議)，而不能實現 Ad hoc按需路由協議(如 Aodv、Dsr路由協議)。本文將探討不能在通用路由體系結構實現Ad hoc按需路由協議三個關鍵的難點。

(1)當發送數據分組的時候，如果不存在從節點到目的地址的路由，則需要發起路由查找過程，但在通常情況下，沒有路由匹配，內核將立即刪除該數據包。然而，這不是一個按需臨時路由想要的情況。在按需路由中，并不是所有的路線被固定安排好，有些路線是必須在需要的時候“發現”。所以在這種情況下，正確的行為應該是請求發現路由，并在路由表更新路由或尋找結束以前，數據分組將不會被發送出去或者丟棄處理。

(2)需要建立一個緩沖區，在按需路由協議等待路由發現的過程中，數據分組需要進入一個緩沖區，該緩沖區設置在內核外，因為可減少內存和CPU的負荷。

(3)為了減少查找內核路由表的代價，就需要定期維護更新這路由表，即時把失效的路由清除。為了實現這功能，需要建立一個路由檢查表。所有表都有一個相關定時器，當該表的路由被使用時，它的定時器就必須重置。當定時器的時間用完時，則該表項就要從內核路由表中刪除。關鍵問題是內核中沒有記錄路由使用的機制，所以路由守護進程根本無法知道內核中使用過哪些路由或什么時候使用過路由。

以上分析可知目前通用嵌入式操作系統沒有這種機制來支持上述行為，所以通用的嵌入式系統應該為Ad hoc網增加以下系統功能：

(1)判斷是否是按需路由，如果是，則查看是否有路由請求；

(2)把請求告知Ad hoc守護進程；

(3)建立一個高速緩沖區，將需要路由請求的數據分組送到緩沖區；

(4)當路由發現完成或發現失敗，將數據分組注入內核中或對其拋棄。

(5)建立路由檢查表，且能定期對其維護，以便能更新內核路由表。

3 通用的按需路由體系設計實現方案

3.1 Ad hoc按需路由協議體系結構

針對本文提出的問題，所設計的按需路由體系如圖2所示。

圖2 通用的ad hoc按需路由協議體系結構圖

3.2 Ad hoc按需路由協議體系結構組成

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

表1 ASL基本函數

3.3 Ad hoc按需路由協議體系結構數據分組傳遞流程

在實現方案中，為了確認是否有路由請求，利用一個系統不用的隧道設備，Universal TUN/TAP(tun)[8]，此設備虛擬了一個網絡接口，當數據分組發送的時候，如果目的地址不存在其路由，則這些數據分組將tun作為缺省路由的下一跳“接口”。這樣就可以通過/dev/net/tun設備將所有需要路由發現的數據分組傳遞到用戶空間做進一步的處理。

處理工作第一步為調用open_route_request()函數來打開。當一個新的數據包從/dev/net/tun中讀出時，Ad hoc守護進程就會利用read_route_request()函數讀取路由請求，之后就可以初始化路由發現。同時，數據分組會在一個臨時緩沖區排隊。因為緩沖區在用戶空間，所以可以有一個較大的緩沖區來存儲數據分組，這樣即使分組在路由發現延時很大的情況下也不會出現丟失的情況。在路由發現成功完成以后，就將數據分組通過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按需路由協議架構

通過上述設計架構，在不用改變系統的內核情況下，就可以實現移動自組網按需路由協議在通用的操作系統上的應用。

圖3是根據Aodv基本的路由功能(如 RREQ、RREP、RERR等路由功能)，置入通用分組尋路功能模塊使其成為Aodv專用的分組尋路功能模塊，如圖3所示。

圖3 Aodv按需路由協議架構

5 方案實施驗證分析

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

由于測試區域較小，節點PC1不需要經過中繼節點K1就可直接到達節點PC2。為了測試Aodv路由協議的“跳轉”功能，采取屏蔽策略，使PC1與PC2相互屏蔽。

(1)PC1對PC2的屏蔽

圖4 實驗環境

在 PC1執行：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發送的數據包。

(2)PC2對PC1的屏蔽

在 PC2執行：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發送的數據包。

①K1節點定期廣播傳送HELLO消息，發現了附近的兩個節點PC1和PC2，如圖5所示。

圖5 K1節點發現PC1、PC2過程

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

圖6 PC1與PC2路由建立過程

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

從Ping命令的輸出結果中可以看到，數據包所經過的路徑是 PC1→K1→PC2→K1→PC1。經過 K1節點上Aodv模塊的路由功能將Ping數據包轉發，使得不能直接通信的節點PC1和PC2實現了數據傳輸，具有了路由發現和網絡自組的功能。

圖7 路由建立成功

本文提出按需路由協議的實現方案，充分考慮了按需路由的特點，針對按需路由在linux嵌入式環境下實現的難點，提出了解決方案和設計實現方案，其功能函數具有良好的通用性。該方案為以后研究員驗證和比較各種協議在實際網絡中的性能提供了良好的基礎。

[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 ofmobile ad hoc routing strategies[C].4th International Conference on Innovations in Information Technologies， Dubai， United Arab Emirates， 2007：128-132.

[4]余旭濤，畢光國.Ad Hoc網絡按需路由協議的改進[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 universaldriver[EB/OL].http：//vtun.sourceforge.net/tun/，2005-10.