ａｄ?。瑁铮憔W絡ＡＯＤＶ協議在Ｗｉｎｄｏｗｓ?。茫派系膶崿F

武亞靜　黃鉞峰　亢　旭　史　鋒

摘 要：為給無線網絡的應用提供研究平臺，用Windows CE模擬器平臺和IEEE 802.11b無線網絡接口搭建真實的移動網絡環境，通過調用API和增加功能模塊的方式實現ad hoc路由協議，使用模擬器編寫相關應用程序，實現AODV(Ad hoc on-demand Distance Vector)路由算法模塊. 對該模塊進行初步的驗證和測試，結果表明：所設計的路由協議不僅在1跳范圍內具有良好的通信性能，而且具備多跳通信能力；可以按需建立路由并實時啟動路由維護過程. 該路由協議的實現為編寫其他ad hoc網絡路由協議提供1種實用框架.

關鍵詞：ad hoc網絡；AODV協議；Windows CE

中圖分類號：TP393.09；TP311.52

文獻標志碼：A

Implementation on AODV routing protocol of ad hoc network in Windows CE

WU Yajing1，HUANG Yuefeng2，KANG Xu2，SHI Feng2

(1.Xian Branch，Shaanxi BC&TV Info-Network Co.，Ltd.，Xian 710068，China；

2.School of Electronic & Info. Eng.，Xian Jiaotong Univ.，Xian 710049，China)

Abstract：To provide a research platform for applications of wireless network，a real mobile network environment is set up based on Windows CE simulator and interfaces of IEEE 802.11b wireless network. Ad hoc routing protocol is implemented by calling API and adding corresponding modules. The routing algorithm of Ad hoc on-demand Distance Vector (AODV) is implemented as a module by programming in the simulator. The preliminary test and verification are done and the results show：the routing protocol performs well not only in one-hop distance but also in multi-hop communication；it can establish the route on demand and start route-maintenance process in time. The implementation of the routing protocol provides a practical framework for implementation on other ad hoc network routing protocols.

Key words：ad hoc network；AODV protocol；Windows CE

0 引 言

隨著人們對擺脫有線網絡束縛、隨時隨地進行自由通信的渴望度的提升，無線網絡通信得到迅速發展.為了能夠在沒有固定基站的地方進行通信，1種新的網絡技術——ad hoc網絡[1]應運而生.1991年5月的IEEE 802.11標準委員會采用“ad hoc網絡”一詞描述這種特殊的自組織對等式多跳移動通信網絡.IETF也將ad hoc網絡稱為MANET(Mobile Ad hoc NETwrok).[2]

目前，對ad hoc網絡的研究尚處于理論階段，對協議性能的驗證大多通過仿真實驗方式進行[3](如OPNET等).仿真在一定程度上存在理想化因素，不能完全精確模擬實際軟硬件條件和現實環境.由于操作系統自身開放程度的限制，在網絡協議編程方面，使用Linux系統平臺可以更直觀地在其網絡層編寫或修改，使其具備路由功能.而Windows并未提供如此寬松的開發空間，只為開發者留出相對固定的接口而并非將整個協議層公布于眾，導致現有路由協議多數基于Linux操作系統.嵌入式平臺也是如此.為改善此現狀，本實驗在嵌入式移動平臺Windows CE[4](以下簡稱WinCE)上建立ad hoc按需路由協議算法所需的一系列機制，提供相應調用接口，并在此基礎上實現AODV(Ad hoc on-demand Distance Vector)[5]路由算法模塊.因考慮按需路由的一般需求，實現內容具備良好的可重用性，有望為其他Windows平臺按需路由協議的實現提供參考.

另外，用WinCE模擬器平臺和筆記本電腦上的802.11b無線網絡接口搭建真實的移動網絡環境，對所實現的 AODV路由協議進行初步驗證和測試.

1 AODV路由協議

AODV其實是DSR(Dynamic Source Routing)[6]和DSDV(Destination Sequenced Distance Vector)[7]的綜合，以DSDV為基礎，并改進DSR中的按需路由思想.它采用DSR中路由發現和路由維護的基礎原理，結合DSDV的逐跳(hop-by-hop)路由、順序編號和路由維護階段的周期更新機制.AODV協議僅在需要時才為目的節點建立路由，比DSDV減少大量維護路由所需的開銷.與DSR相比，AODV的優勢在于源路由無須包括在每個數據分組中，能有效降低控制負載.[8]

1.1 AODV路由發現過程

在AODV協議中，為了找到通往目的節點的路由，源節點將廣播1個路由請求分組RREQ(Router REQuest)，見圖1(a).中間節點A第1次收到來自S的RREQ包，隨即建立到源節點S的路由，稱為反向路由.此路由的目的節點是廣播RREQ的源節點，下一跳節點是將RREQ發送給本節點的鄰節點.圖1(b)表示反向路由的建立結果.一旦RREQ分組到達目的節點或存在到達目的節點的有效路由的中間節點時，節點就回復1個路由應答分組RREP(Router REPeat)，圖1(c)表示這一回復過程.RREP分組沿逆向路徑回傳時，此路徑上的每個節點都建立正向路由，記錄最新的目的節點序列號和到源節點的路由生存時間，圖1(d)表示正向路由的建立結果.

(a) 路由請求分組的傳播路徑

(b) 反向路由建立過程

(c) 路由應答分組傳播路徑(白) 與路由形成路徑(黑)

(d) 正向路由建立過程

圖 1 AODV路由發現過程

1.2 AODV路由維護過程

節點移動可能導致原來的路由不可用，針對以上情況，AODV協議有2種處理方式[9]：本地修復和源節點重建路由.中間節點檢測到與某鄰節點之間的鏈路中斷時，所有使用這段鏈路的路由將失效，因此采用由檢測到中斷節點在1跳范圍內廣播出錯消息RERR(Router ERRor)的方式.節點收到此消息后，判斷自己是否會受到影響，把相應條目置為無效，如果該節點還存在上游節點，則繼續廣播該消息，否則丟棄該分組.

2 AODV協議在WinCE上實現的解決方案

由于WinCE操作系統的限制，程序員不可能修改其核心協議棧，因此只能通過調用現有函數接口和增加功能模塊的方式實現ad hoc路由協議.在網絡編程方面，WinCE支持NDIS(Network Driver Interface Specification)中間層[10]驅動，用于網絡數據包的過濾和修改；提供Windows Sockets網絡通信接口，用于部分收發包操作和對協議可用性的測試；提供IPHelper函數接口，用于對IP路由表的操作.這些因素使驅動編寫的重點集中于NDIS層.

通過修改微軟提供的實例程序PASSTHRU[10]，在發送接收封包的函數中加入過濾器，使此過濾器觸發AODV協議模塊處理來自上層的業務包，使其可以按需進行路由發現，更新路由表，分離來自下層的業務包和AODV控制包，并作分類處理.

2.1 整體協議設計框架

在PASSTHRU實例程序的基礎上，修改用于發送封包的函數MiniPortSendPackets和用于接收封包的接口函數ProtocolReceivePacket，在這2個函數中分別加入發包過濾器和收包過濾器的功能.將截獲的網絡封包送入AODV算法模塊進行處理，從而對處理的封包進行路由發現，見圖2.

圖 2 整體協議設計框架

發送過濾器主要用來判斷上層發來的封包是否經過AODV協議模塊的處理，將未經處理的封包送入AODV協議模塊進行處理(見第2.2節).該模塊首先使用隊列緩存沒有到達目的節點的路由封包(見第2.5節)，并為該封包發起1次路由發現過程，待AODV協議模塊路由發現過程結束，從隊列中取出該封包并發往目的節點.

在維護AODV路由表的同時，AODV協議模塊實時更新位于TCP/IP協議棧的系統路由表，使AODV的路由表與TCP/IP系統路由表保持一致，其目的在于利用系統路由表轉發目的節點不是自己的封包，從而實現多跳路由的功能.

接收過濾器主要負責分離下層發來的封包是否是AODV協議的控制包.如果是則送入AODV協議模塊進行處理，否則發送到上層，交給TCP/IP協議的系統路由表處理(見第2.3節).

在AODV協議模塊中，定義AODV協議的控制包為端口號是AODVPort的UDP包，并在AODV協議模塊中使用WinSocket進行發送.使用Socket發送AODV控制包的目的是通過TCP/IP協議棧給控制包加入必要的Ethernet包頭、IP包頭和UDP包頭.

2.2 發送過濾器

AODV 路由算法設計主要是為了實現路由發現和路由維護的功能.由于AODV協議路由表與TCP/IP系統路由表一致，在發送過濾器過程中，通過函數GetRouteTableEntry判斷上層封包是否經過AODV協議的處理.如此既能處理本節點的業務包，也能處理轉發的業務包，實現路由修復的功能.

在MiniPortSendPakcets函數中的發送過程控制包過濾規則見圖3.

圖 3 發送過濾器流程

2.3 接收過濾器

在ProtocolReceivePackets函數中，需要將控制包從眾多的收包中提取出來，接收過程的過濾規則見圖4.

圖 4 接受過濾器流程

分離出來的控制包被“封裝”成為WorkItem，并放入AODV協議線程隊列等待相應回調函數觸發.回調函數根據不同的控制包調用不同的函數(如使用ReceiveRrep函數處理RREP包的接收處理).分離出來的業務包由系統路由表進行處理.

2.4 線程管理

NDIS中間層使用WorkItem創建線程.在AODV工程中，WorkItem機制被安置在收包過濾器中，用于處理不同類型的控制包.通過定義InsertWorkItem函數，對已經解析完畢的控制包進行操作.此函數首先對結構體WORK-ITEM-CONTEXT包過濾器中進行一系列初始化；接著在函數中調用NDIS的WorkItem控制函數. 首先調用函數NdisInitializeWorkItem，它有3個參數：pNewWorkItem，ProcessWorkItem和pNewWorkItemContext，第2個參數ProcessWorkItem實際為自定義函數.在函數中通過包類型進行判斷，對不同的包調用不同的函數，作不同的處理；其次調用NdisScheduleWorkItem函數以將初始化完畢的pNewWorkItem加入線程隊列并等待執行.

2.5 業務包隊列管理技術

當沒有到達目的節點路由時，需要緩存暫時無法發出的業務包.包以NDIS中間層定義的包描述符(Packet Descriptor)形式進行緩存，即包的實際存儲物理地址未變，只簡單存儲指向此地址的指針.使用包描述符緩存業務封包不僅使協議更加結構化，而且可避免使用Socket還原業務封包的復雜操作.驅動加載后，需要分配1塊存儲區，并根據數據項格式初始化這段緩存；當有業務包到來時，將其插入FIFO.當1次路由發現完成，根據路由表的更新情況，從隊列中刪除可達的業務包并發給下一跳節點.

3 AODV協議的測試

為了測試第1節AODV路由協議所描述的各項性能，采用4臺安裝有此協議的筆記本電腦(Core Duo 1.6 GHz，1 GB RAM 802.11b WLAN，以下簡稱節點)進行實驗.

3.1 鄰居探測包

每個節點周期性廣播HELLO分組.實驗結果如下：節點能正確收到鄰居的HELLO消息；正確將此節點信息添入路由表；當兩節點斷路時，在路由表中刪除相應條目.

3.2 RREP與RREQ消息

建立A—B—C的拓撲結構(A作為源節點，B作為中間節點，C作為目的節點，“—”表示被其連接的兩節點均在對方通信范圍之內)，見圖5.

圖 5 1—2—3式的拓撲結構及各節點IP地址

路由發現發起前，C節點的系統路由表內容見圖6.

圖 6 路由發現之前C節點系統路由表

在A節點使用ping命令測試與C節點的連通性時，會發出1個RREQ消息，節點B收到RREQ消息，回復1個RREP；節點A收到此RREP消息，添加相應路由表項，此后ping命令得以正確接收.此時查看C節點路由表(見圖7)，已含有“到達A節點，需要B節點轉發(被標明為GatewayAddress)”的路由表項.

圖 7 路由發現之后C節點系統路由表

3.3 RERR消息

使用第3.2節所描述的拓撲結構，當節點A到節點C的路由建立后，斷開B—C節點的鏈路，節點A能正確收到RERR包，說明節點B操作正確.實驗結果驗證如下：節點B因鏈路中斷發出RERR消息，并將有關節點C的路由條目從路由表中刪除；節點A收到RERR消息，將有關節點B的路由條目從路由表中刪除.

3.4 本地修復

建立A—B—D和A—C—D的拓撲結構.首先建立A—B—D路徑，當B—D斷路時，源節點采用A—C—D路徑.實驗結果驗證如下：當B—D斷路時，節點B發送RERR消息給節點A；節點A收到RERR消息，發出新的RREQ；節點C用RREP消息回復此RREQ；節點A收到RREQ，將節點C添加到路由表相關條目，到節點D的路徑建立.

4 結束語

當前，無線網絡應用需求非常廣泛，但相關實際應用卻還在起步階段.因此，為了提供研究平臺并為今后的研究奠定基礎，對按需路由協議AODV進行簡單分析，并在WinCE平臺上對其進行驗證.

無線網絡接口卡自身存在局限性，協議的穩定性、可移動性和其他性能均可能受此影響.中間層協議應具備簡潔高效的算法，盡可能降低使傳輸穩定性再惡化的幾率.協議在編寫過程中充分考慮可重用性因素，各功能高度模塊化.這為其他ad hoc網絡路由協議的編寫提供1種實用框架，為編程者提供參考.

后續工作將集中于提高節點數量、密度和移動速率，擴展網絡范圍，并引入多種統計量分析協議效率，提出實際的建設性改進策略.

參考文獻：

[1] 于宏毅. 無線移動自組織網[M]. 北京：人民郵電出版社，2005：18-235.

[2] The official IETF working group MANET Webpage[EB/OL]. (2008-06-02)[2006-06-23]. http：//www.ietf.org/tml.charters.

[3] LEE S J，GERLA M T. A simulation study of table-driven and on-demand routing protocols for mobile ad hoc networks[J]. IEEE Trans，1999，13(4)：48-54.

[4] Microsoft Corporation. Microsoft Windows CE homepage[EB/OL]. (2008-06-21)[2005-11-24]. http：//msdn.microsoft.com/en-us/embedded/default.aspx.

[5] IETF. RFC3561，Ad hoc on-demand Distance Vector(AODV) routing[S]. 2003.

[6] BROCH J，JOHNSON D B，MALTZ D A. DSR：the dynamic source routing protocol for mobile ad hoc networks[J]. USA：Addison-Wesley，2001：139-172.

[7] PERKINS C E，BHAGWAT P. Highly dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for mobile computers[J]. ACM SIGCOMM Comput Commun Rev，1994，24(4)：234-244.

[8] GUO Song，YANG O，SHU Yantai.Improving source routing reliability in mobile ad hoc networks[J]. IEEE Trans on Parallel & Distributed Syst，2005，16(4)：362-373.

[9] AODV homepage[EB/OL]. (2008-06-28)[2007-04-05]. http：//moment.cs.ucsb.edu.

[10] Microsoft Corp. Windows driver development kit[Z]. 2002.

(編輯 廖粵新)