基于位置信息改进的AODV路由协议

王泰麟，张法全，叶金才，王国富

(桂林电子科技大学 信息与通信学院，广西 桂林　541004)



基于位置信息改进的AODV路由协议

王泰麟，张法全，叶金才，王国富

(桂林电子科技大学 信息与通信学院，广西 桂林541004)

为减少AODV路由协议的路由开销，设计了一种基于位置信息改进的AODV路由协议——Im-AODV。改进的AODV路由协议通过在RREQ消息中添加节点位置信息来限制RREQ消息的洪泛区域，减少控制报文的转发。位置信息则通过RREQ消息和RREP消息在网络中扩散，并未增加额外的控制报文。通过NS2对改进的AODV路由协议进行仿真，仿真结果表明，改进的AODV路由协议减少了归一化路由开销，提高了分组投递率。

路由开销；AODV；位置信息；Im-AODV；NS2

无线自组织网络(mobile Ad Hoc network，简称MANET)是一种多跳、无中心、自组织无线网络，整个网络无需固定基础设施，网络中各个节点均可移动，并且能够与其他节点保持联系[1-2]。网络中各节点地位平等，拓扑可变，节点的移动、加入和退出并不影响整个网络的正常工作。当节点需要与其通信覆盖范围之外的节点进行通信时，将由中间节点进行多跳转发，各节点兼任路由器的角色。由于无线自组织网络的以上特点，MANET已经得到广泛应用。但由于无线网络的带宽资源、节点能源的限制，使得路由协议在设计时，除了满足应用需求外，还应减少路由协议对网络带宽资源的占用和能源的消耗，提高协议的效率和网络的吞吐率。

根据应用场景不同，人们提出了很多无线路由协议。根据触发原理的不同，这些路由协议可分为3类：1)表驱动路由协议；2)按需驱动路由协议；3)混合式路由协议[3]。表驱动路由协议又称先验式路由协议，网络中每个节点都保存一张包含到达其他节点的路由表，通过周期性广播更新路由信息，但其无法适用于网络拓扑变化较快的场景，且其周期性广播带来的带宽资源占用往往是不可接受的。按需路由协议也称后验式路由协议，其主要特点是：当源节点需要时才进行路由查找，从而减小了路由开销，保证路由信息的时效性，但传送数据的时延相对较大。混合式路由协议是在表驱动路由协议和按需驱动路由协议都不能满足应用需求时，研究人员结合两类路由的优点和不同特点提出的路由协议。

AODV路由协议(Ad Hoc on-demand distance vector routing protocol)是MANET的一种经典按需路由协议，具有算法简单、扩展性好的特点[4]。其工作流程为：当源节点需要与目标节点进行通信而路由表中无相应表项时，源节点发送路由请求RREQ消息，当RREQ消息逐跳广播至目标节点或有目标节点路由表项的节点，则沿最先到达的路径反向应答路由回复RREP消息至源节点，从而获取达到目标节点的路由。此外，AODV路由协议采用HELLO消息及RERR消息维护链路[5-6]。AODV路由协议采用简单洪泛机制[7]，虽然提高了路由的发现机率，但由此引起的路由请求广播的无效转发，往往带来带宽资源的大量消耗，造成信道拥塞，从而降低整个网络的工作效率。

针对AODV路由协议的路由发现过程中简单洪泛带来的问题，提出一种基于位置信息改进的AODV路由协议(Im-AODV)，限制RREQ消息的广播范围，从而减少洪泛带来的网络开销。

1　基于位置信息改进的AODV路由协议

为限制RREQ消息的广播范围，在AODV路由协议的基础上，增加了一个称为节点信息表的数据结构，用于存储网络中节点的位置信息。每个节点信息表的内容包括：节点IP地址、节点序列号、节点坐标有效标识、节点坐标。

为了将节点的坐标信息扩散到整个网络，改进的AODV路由协议采用将节点的坐标信息附加到AODV路由协议的RREQ消息和RREP消息中的方式。改进的RREQ消息结构如表1所示，相对标准AODV路由协议的RREQ消息，在原保留区内增加了1位目标节点坐标标识位S，在RREQ消息后部增加了目标节点坐标和源节点坐标2个字段。改进的RREP消息结构如表2所示，在原保留字段内增加了1位回复节点坐标标识位S，并在RREP消息后部增加了目标节点坐标、回复节点IP地址、回复节点序列号和回复节点坐标4个字段。

表1　改进的RREQ消息结构

表2　改进的RREP消息结构

若源节点需要到达目标节点的路由，则向目标节点发起路由发现。源节点根据表1所示消息结构，生成一个RREQ消息，并对此RREQ消息进行广播。中间节点接收到RREQ消息后，提取源节点和目标节点的坐标信息，更新本地的节点信息表，然后判断本节点是否在允许洪泛区域内。若在区域内，则根据AODV路由协议的规定对RREQ消息进行响应或继续转发；若不在区域内，则在更新本地的节点信息表后，直接丢弃RREQ消息。

2　Im-AODV的实现

当源节点需要一条到目标节点的路由，而路由表中无路由时，源节点即发起路由发现。改进的AODV路由产生的RREQ消息，需要在标准AODV路由协议的RREQ消息中附加如下信息：1)若目标节点坐标对于源节点是已知的，则置目标节点坐标标识位S为1，否则置0；2)目标节点坐标(若未知，则置该字段为0)；3)源节点坐标。

源节点在生成RREQ消息后进行洪泛广播，等待接收RREP消息。改进的AODV路由协议的不同之处在于中间节点收到RREQ消息后，首先根据RREQ消息中源节点和目标节点的坐标，更新本地的节点信息表中相应内容，然后根据标准AODV查看本节点是否有到目标节点的有效路由，从而决定是否产生RREP消息。若不产生RREP消息，则根据源节点和目标节点坐标信息判断本节点是否在允许洪泛区域。若在，则继续转发该RREQ消息；若不在，则丢弃。

中间节点判断本节点是否在允许洪泛区域内的方法为：

允许洪泛区域如图1所示，由源节点坐标S(Xs,Ys)和目标节点坐标D(Xd,Yd)构成的矩形即为允许洪泛区域，中间节点N(Xn,Yn)根据RREQ消息的源节点和目标节点的坐标判断其是否在允许洪泛区域内，即是否满足：

(1)

(2)

因为节点N(Xn,Yn)满足式(1)、(2)，所以判断其在允许洪泛区域内；而节点I(Xi,Yi)不能同时满足式(1)、(2)，则判定其不在允许洪泛区域。

为了进一步优化路由发现的成功率，将目标节点坐标扩展为一个半径为R的圆形区域，优化后的允许洪泛区域如图2所示。R的设定可根据网络节点的密度调整，若节点分布较为密集，可设定一个较小的R，若节点分布较为稀疏，则设定一个较大的R。

图1　允许洪泛区域Fig.1　Allowed flooding zone

图2　优化后的允许洪泛区域Fig.2　Optimization of allowed flooding zone

以图2为例，允许洪泛区域调整为X∈(Xs,Xd+R)，Y∈(Ys,Yd+R)的区域。

当RREQ消息成功转发至目标节点或具有到达目标节点路由的节点时，则产生RREP消息，这与标准AODV路由协议是一致的。为了满足网络拓扑变化的需要，改进的AODV路由协议对RREP消息进行了修改，根据产生RREP消息节点的不同，RREP消息的内容也稍有区别。若产生RREP消息的是目标节点，则将回复节点标识位置1，并将目标节点IP地址和坐标写到回复节点IP地址和坐标字段；若产生RREP消息的是具有到达目标节点路由的中间节点，则将回复节点标识位置0，将目标节点IP地址、坐标和回复节点IP地址、坐标分别写入相应字段。

收到RREP消息的节点，判断回复节点标识位。若为1，则更新本地的节点信息表中目标节点的相应信息；若为0，则更新本地节点信息表中产生RREP消息的节点相应信息和目标节点的相应信息。

3　仿真测试与结果分析

3.1仿真测试

利用NS2(network simulator version 2)仿真平台对AODV路由协议和改进后的AODV路由协议(Im-AODV)进行仿真[8]。根据改进方法，对AODV路由协议进行修改。改进AODV所需的位置信息可用NS2提供的getLoc( )函数获取的坐标，替代实际应用中GPS获取的位置信息。分别利用AODV和改进的AODV在不同场景下进行3种性能测试：

1)路由发现时间。源节点发起路由发现进程到成功建立到达目标节点的路由所耗费的时间。

2)归一化路由开销。在整个网络运行期间，路由控制报文数量和实际完成的数据报文数量的比值，这个比值可以较好地反映网络的拥塞情况。

3)分组投递率。目标节点接收的数据分组和源节点发送的数据分组的比值，主要反映网络的可靠性。

路由发现时间测试方法：30个节点分布在250 m×300 m区域，节点间距50 m，节点有效通信距离55 m，MAC层协议为802.11，分别用不同节点以固定码率(CBR)向目标节点发送数据分组，每秒4个分组，每个分组512 Byte，传输层协议采用UDP。在此场景下进行仿真，分别利用gawk对2种协议的多次仿真记录文件trace进行分析统计。

归一化路由开销和数据分组投递率测试方法：将20、40、60、80、100个节点分布在150 m×200 m、350 m×400 m、550 m×600 m、750 m×800 m、950 m×1000 m的区域，节点以不超过10 m/s的速度在区域内移动，停留80 s，以固定码率(CBR)向目标节点发送数据分组，每秒4个分组，每个分组512 Byte，传输层协议为UDP。在对应场景下进行仿真，对2种协议的多次仿真记录文件trace进行分析统计。

3.2结果分析

根据对仿真记录文件的统计分析，得到图3所示的2种路由发现时间。从图3可看出，2种协议的路由发现时间基本一致，且随着源节点到目标节点的跳数增加，2种协议路由发现时间也相应递增。

归一化路由开销仿真测试结果如图4所示。从图4可看出，2种协议的归一化路由开销都随网络中节点数的增加而增加，但改进的AODV路由协议的路由开销比标准AODV路由协议要小，且随着节点数的增加，优势更加明显。这是因为改进的AODV路由协议对允许洪泛的区域进行了限制，只允许洪泛区域内的节点转发RREQ，从而减少了控制报文的开销。

图3　AODV和Im-AODV的路由发现时间Fig.3　Roue discovery time of AODV and Im-AODV

图4　AODV和Im-AODV归一化路由开销Fig.4　Normalized routing overhead of AODV and Im-AODV

分组投递率仿真测试结果如图5所示。从图5可看出，随着节点数的增加，路由跳数也随之增加，2种协议的数据分组投递率随之降低，且改进的AODV协议的分组投递率高于标准AODV协议。这是因为随着链路的增长，链路的不稳定性增加，从而投递率下降；同时，随着控制报文的增加，数据报文与控制报文竞争有限的无线资源，也会导致分组传送失败增加；而由于减少了控制报文的数量，使得改进的AODV路由协议的分组投递率略高于标准AODV路由协议的分组投递率。

图5　AODV和Im-AODV分组投递率Fig.5　Packets delivery ratio of AODV and Im-AODV

4　结束语

仿真测试结果表明，基于位置信息改进的AODV路由协议大大减小了协议的路由开销，并提高了数据分组投递率。由于并未改变RREP消息的产生机制，在路由发现时间等性能方面相对于标准AODV路由协议并没有变化。此外，基于位置信息改进的AODV路由协议只针对节点布置在一个平面或可近似为平面的无线自组织网络，将平面的允许洪泛区域向立体空间拓展，即可使改进的AODV路由协议适用于节点立体分布的无线自组织网络。

[1]张希婕.Ad Hoc网络混合路由协议的研究[D].北京：北京邮电大学，2014:1-2.

[2]徐年，沙宏武.Ad Hoc技术在地震监测系统中的应用[J].电脑学习，2010(1):5-6.

[3]彭永祥.无线Adhoc网络路由技术若干关键问题研究[D].成都：电子科技大学，2013:15-20.

[4]雷建栋.地理位置信息辅助的AODV路由协议[J].火力与指挥控制，2013(增刊1):59-62.

[5]谢世欢.Linux 系统上AODV路由协议的实现[D].成都：电子科技大学，2004：17-21.

[6]卢山，宋志群，周凌宇，等.无线自组织网络按需路由协议研究[J].无线电工程，2015,45(11):5-8.

[7]何绵禄，褚伟，刘辉舟.AODV路由协议的研究和改进[J].计算机工程，2015,41(1):110-114.

[8]谢佳，徐山峰.AODV、AOMDV和AODV-UU路由协议性能仿真与分析[J].中国电子科学研究学院学报，2011,6(6):592-596.

编辑：翁史振

An improved AODV routing protocol based on position information

WANG Tailin, ZHANG Faquan, YE Jincai, WANG Guofu

(School of Information and Communication Engineering, Guilin University of Electronic Technology, Guilin 541004, China)

The flooding request method of AODV routing protocol makes RREQ message forwarding across Ad Hoc network, which increases the routing overhead of protocol. To reduce the routing overhead of AODV routing protocol, an improved AODV routing protocol based on position information is proposed and called Im-AODV. In RREQ message of Im-AODV, the position information is added to limit the flooding zone of RREQ, which can reduce the forwarding of control packets. The position information diffuses in the network through RREQ and RREP, which does not add additional control packets. The improved AODV routing protocol is simulated by NS2, the simulation results show that the normalized routing overhead of the improved AODV routing protocol is effectively reduced, and the packets delivery ratio is improved.

routing overhead; AODV; position information; Im-AODV; NS2

2016-02-24

国家自然科学基金(61362020)；广西自然科学基金(2013GXNSFAA019327，2013GXNSFFA019004)

张法全(1969-)，男，河南林州人，研究员，博士，研究方向为信号与信息处理。E-mail:zhangfq@guet.edu.cn

TN92

A

1673-808X(2016)04-0270-05

引文格式：王泰麟，张法全，叶金才，等.基于位置信息改进的AODV路由协议[J].桂林电子科技大学学报，2016,36(4):270-274.