ａｄ ｈｏｃ网络ＡＯＤＶ协议在Ｗｉｎｄｏｗｓ ＣＥ上的实现

武亚静　黄钺峰　亢　旭　史　锋

摘 要：为给无线网络的应用提供研究平台，用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.

(编辑 廖粤新)