謝毅勇 ，謝維波

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

Ad hoc網(wǎng)絡(luò)[1]是一種特殊的對等式網(wǎng)絡(luò)，它不需要固定的通信設(shè)施支持即可快速建立無線網(wǎng)絡(luò)，其最初的動機是滿足戰(zhàn)場生存的軍事需求。由于其自組能力、低成本、工作壽命長等特點，Ad hoc網(wǎng)絡(luò)逐漸進入了民用和商用領(lǐng)域，遺憾的是發(fā)展較為緩慢。其主要原因之一就是Ad hoc路由協(xié)議通常采用新的路由模式，并不支持目前操作系統(tǒng)路由體系結(jié)構(gòu)。若沒有通用的操作系統(tǒng)路由體系結(jié)構(gòu)解決方案，路由算法研究員就得被迫進行低級系統(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)上進行路由算法編程，而不用進行底層內(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ù)與其他主機交換的路由信息，計算出到其他節(jié)點的正確路由。轉(zhuǎn)發(fā)表含有充分的信息來完成轉(zhuǎn)發(fā)使命，而路由表中包含路由算法用于發(fā)現(xiàn)和維護路由的信息。

在通用的嵌入式開源操作系統(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ā)表項的最佳匹配原則進行轉(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ù)分組需要進入一個緩沖區(qū)，該緩沖區(qū)設(shè)置在內(nèi)核外，因為可減少內(nèi)存和CPU的負荷。

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

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

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

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

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

(4)當(dāng)路由發(fā)現(xiàn)完成或發(fā)現(xiàn)失敗，將數(shù)據(jù)分組注入內(nèi)核中或?qū)ζ鋻仐墶?/p>

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

3 通用的按需路由體系設(shè)計實現(xiàn)方案

3.1 Ad hoc按需路由協(xié)議體系結(jié)構(gòu)

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

圖2 通用的ad hoc按需路由協(xié)議體系結(jié)構(gòu)圖

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路由守護進程。netfiilter鉤子程序是系統(tǒng)自帶的，用來捕捉每一個發(fā)送數(shù)據(jù)分組，記錄每條路由的最后使用時間，然后對路由檢查表做相應(yīng)的處理，路由檢查表約800行代碼。其中，ASL是一個共享庫，約2 500行代碼，用來實現(xiàn)按需路由功能。當(dāng)ASL接到一個延時發(fā)送的數(shù)據(jù)分組，就會告知Ad hoc守護進程，以便對數(shù)據(jù)分組的目的地址進行路由發(fā)現(xiàn)。之后它將該數(shù)據(jù)分組儲存在一個臨時緩沖區(qū)中，等待守護進程返回路由發(fā)現(xiàn)的結(jié)果。一旦這些處理完成，相應(yīng)的內(nèi)核路由表就加入新的元組，數(shù)據(jù)分組移出緩沖區(qū)，重新注入到包轉(zhuǎn)發(fā)功能塊的隊列中。ASL基本函數(shù)如表1所示。

表1 ASL基本函數(shù)

3.3 Ad hoc按需路由協(xié)議體系結(jié)構(gòu)數(shù)據(jù)分組傳遞流程

在實現(xià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ù)分組傳遞到用戶空間做進一步的處理。

處理工作第一步為調(diào)用open_route_request()函數(shù)來打開。當(dāng)一個新的數(shù)據(jù)包從/dev/net/tun中讀出時，Ad hoc守護進程就會利用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路由守護進程內(nèi)核路由表的使用情況，這樣守護進程就可以檢查路由的更新和刪除內(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所示。

圖3 Aodv按需路由協(xié)議架構(gòu)

5 方案實施驗證分析

實驗現(xiàn)場為華僑大學(xué)廈門軟件園嵌入式技術(shù)開放實驗室(廈門軟件園二期54號402，華僑大學(xué)產(chǎn)學(xué)研基地)。網(wǎng)絡(luò)節(jié)點由兩個PC機節(jié)點和一個嵌入式系統(tǒng)節(jié)點組成。PC機節(jié)點配置是DELL工作站PY597+ZD1211b無線網(wǎng)卡，安裝CentOS 5操作系統(tǒng) (內(nèi)核版本號為26.18-128.e15)，加載Aodv路由協(xié)議模塊，支持直接或多跳的通信。嵌入式系統(tǒng)節(jié)點配置則為致遠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ò)拓撲如圖4所示。

由于測試區(qū)域較小，節(jié)點PC1不需要經(jīng)過中繼節(jié)點K1就可直接到達節(jié)點PC2。為了測試Aodv路由協(xié)議的“跳轉(zhuǎn)”功能，采取屏蔽策略，使PC1與PC2相互屏蔽。

(1)PC1對PC2的屏蔽

圖4 實驗環(huán)境

在 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ù)包。

①K1節(jié)點定期廣播傳送HELLO消息，發(fā)現(xiàn)了附近的兩個節(jié)點PC1和PC2，如圖5所示。

圖5 K1節(jié)點發(fā)現(xiàn)PC1、PC2過程

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

圖6 PC1與PC2路由建立過程

③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ò)自組的功能。

圖7 路由建立成功

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

[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網(wǎng)絡(luò)按需路由協(xié)議的改進[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 universaldriver[EB/OL].http：//vtun.sourceforge.net/tun/，2005-10.