武亞靜　黃鉞峰　亢　旭　史　鋒

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

關(guān)鍵詞：ad hoc網(wǎng)絡(luò)；AODV協(xié)議；Windows CE

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

文獻(xiàn)標(biāo)志碼：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 引 言

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

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

另外，用WinCE模擬器平臺和筆記本電腦上的802.11b無線網(wǎng)絡(luò)接口搭建真實(shí)的移動網(wǎng)絡(luò)環(huán)境，對所實(shí)現(xiàn)的 AODV路由協(xié)議進(jìn)行初步驗(yàn)證和測試.

1 AODV路由協(xié)議

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

1.1 AODV路由發(fā)現(xiàn)過程

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

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

(b) 反向路由建立過程

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

(d) 正向路由建立過程

圖 1 AODV路由發(fā)現(xiàn)過程

1.2 AODV路由維護(hù)過程

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

2 AODV協(xié)議在WinCE上實(shí)現(xiàn)的解決方案

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

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

2.1 整體協(xié)議設(shè)計框架

在PASSTHRU實(shí)例程序的基礎(chǔ)上，修改用于發(fā)送封包的函數(shù)MiniPortSendPackets和用于接收封包的接口函數(shù)ProtocolReceivePacket，在這2個函數(shù)中分別加入發(fā)包過濾器和收包過濾器的功能.將截獲的網(wǎng)絡(luò)封包送入AODV算法模塊進(jìn)行處理，從而對處理的封包進(jìn)行路由發(fā)現(xiàn)，見圖2.

圖 2 整體協(xié)議設(shè)計框架

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

在維護(hù)AODV路由表的同時，AODV協(xié)議模塊實(shí)時更新位于TCP/IP協(xié)議棧的系統(tǒng)路由表，使AODV的路由表與TCP/IP系統(tǒng)路由表保持一致，其目的在于利用系統(tǒng)路由表轉(zhuǎn)發(fā)目的節(jié)點(diǎn)不是自己的封包，從而實(shí)現(xiàn)多跳路由的功能.

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

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

2.2 發(fā)送過濾器

AODV 路由算法設(shè)計主要是為了實(shí)現(xiàn)路由發(fā)現(xiàn)和路由維護(hù)的功能.由于AODV協(xié)議路由表與TCP/IP系統(tǒng)路由表一致，在發(fā)送過濾器過程中，通過函數(shù)GetRouteTableEntry判斷上層封包是否經(jīng)過AODV協(xié)議的處理.如此既能處理本節(jié)點(diǎn)的業(yè)務(wù)包，也能處理轉(zhuǎn)發(fā)的業(yè)務(wù)包，實(shí)現(xiàn)路由修復(fù)的功能.

在MiniPortSendPakcets函數(shù)中的發(fā)送過程控制包過濾規(guī)則見圖3.

圖 3 發(fā)送過濾器流程

2.3 接收過濾器

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

圖 4 接受過濾器流程

分離出來的控制包被“封裝”成為WorkItem，并放入AODV協(xié)議線程隊列等待相應(yīng)回調(diào)函數(shù)觸發(fā).回調(diào)函數(shù)根據(jù)不同的控制包調(diào)用不同的函數(shù)(如使用ReceiveRrep函數(shù)處理RREP包的接收處理).分離出來的業(yè)務(wù)包由系統(tǒng)路由表進(jìn)行處理.

2.4 線程管理

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

2.5 業(yè)務(wù)包隊列管理技術(shù)

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

3 AODV協(xié)議的測試

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

3.1 鄰居探測包

每個節(jié)點(diǎn)周期性廣播HELLO分組.實(shí)驗(yàn)結(jié)果如下：節(jié)點(diǎn)能正確收到鄰居的HELLO消息；正確將此節(jié)點(diǎn)信息添入路由表；當(dāng)兩節(jié)點(diǎn)斷路時，在路由表中刪除相應(yīng)條目.

3.2 RREP與RREQ消息

建立A—B—C的拓?fù)浣Y(jié)構(gòu)(A作為源節(jié)點(diǎn)，B作為中間節(jié)點(diǎn)，C作為目的節(jié)點(diǎn)，“—”表示被其連接的兩節(jié)點(diǎn)均在對方通信范圍之內(nèi))，見圖5.

圖 5 1—2—3式的拓?fù)浣Y(jié)構(gòu)及各節(jié)點(diǎn)IP地址

路由發(fā)現(xiàn)發(fā)起前，C節(jié)點(diǎn)的系統(tǒng)路由表內(nèi)容見圖6.

圖 6 路由發(fā)現(xiàn)之前C節(jié)點(diǎn)系統(tǒng)路由表

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

圖 7 路由發(fā)現(xiàn)之后C節(jié)點(diǎn)系統(tǒng)路由表

3.3 RERR消息

使用第3.2節(jié)所描述的拓?fù)浣Y(jié)構(gòu)，當(dāng)節(jié)點(diǎn)A到節(jié)點(diǎn)C的路由建立后，斷開B—C節(jié)點(diǎn)的鏈路，節(jié)點(diǎn)A能正確收到RERR包，說明節(jié)點(diǎn)B操作正確.實(shí)驗(yàn)結(jié)果驗(yàn)證如下：節(jié)點(diǎn)B因鏈路中斷發(fā)出RERR消息，并將有關(guān)節(jié)點(diǎn)C的路由條目從路由表中刪除；節(jié)點(diǎn)A收到RERR消息，將有關(guān)節(jié)點(diǎn)B的路由條目從路由表中刪除.

3.4 本地修復(fù)

建立A—B—D和A—C—D的拓?fù)浣Y(jié)構(gòu).首先建立A—B—D路徑，當(dāng)B—D斷路時，源節(jié)點(diǎn)采用A—C—D路徑.實(shí)驗(yàn)結(jié)果驗(yàn)證如下：當(dāng)B—D斷路時，節(jié)點(diǎn)B發(fā)送RERR消息給節(jié)點(diǎn)A；節(jié)點(diǎn)A收到RERR消息，發(fā)出新的RREQ；節(jié)點(diǎn)C用RREP消息回復(fù)此RREQ；節(jié)點(diǎn)A收到RREQ，將節(jié)點(diǎn)C添加到路由表相關(guān)條目，到節(jié)點(diǎn)D的路徑建立.

4 結(jié)束語

當(dāng)前，無線網(wǎng)絡(luò)應(yīng)用需求非常廣泛，但相關(guān)實(shí)際應(yīng)用卻還在起步階段.因此，為了提供研究平臺并為今后的研究奠定基礎(chǔ)，對按需路由協(xié)議AODV進(jìn)行簡單分析，并在WinCE平臺上對其進(jìn)行驗(yàn)證.

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

后續(xù)工作將集中于提高節(jié)點(diǎn)數(shù)量、密度和移動速率，擴(kuò)展網(wǎng)絡(luò)范圍，并引入多種統(tǒng)計量分析協(xié)議效率，提出實(shí)際的建設(shè)性改進(jìn)策略.

參考文獻(xiàn)：

[1] 于宏毅. 無線移動自組織網(wǎng)[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.

(編輯 廖粵新)