基于位置辅助的自适应广播AODV路由协议

李友良，陈桂芬，罗宝翔

（长春理工大学 电子信息工程学院，长春 130022）

移动自组织组网络MANET属于无线移动通信网络的一种［1］，它不具备相应的预设基础设施，且是由众多配备无线收发信装置的移动终端所构成。由于在该网络内的节点能够自由移动，开放性较强，所以这种网络能够用于基础设施不可用和无法部署网络的环境，如灾难恢复、会议中的临时信息共享、军事应用、数据共享和紧急情况［2］。

AODV（Ad Hoc On-Demand Distance Vector）按需距离矢量路由协议是自组网中的一种被广泛应用的路由协议，只有存在通信需要时，它才会开始探寻到目的节点的路由［3］。即，网络内一节点A需要将数据传输到另一节点B，但没有已知到节点B的路径。节点A需要向它通信范围内的所有节点广播路由请求分组（RREQ），接收到RREQ的节点在网络内继续转发工作，直至节点B或已知到节点B路径的节点接收到RREQ，生成路由应答分组（RREP）并单播回源节点［4］。RREP消息到达源节点表明路由发现过程已经结束，此时使用单播传输将数据包转发到目的地。由于协议采用洪泛广播的方式来探寻路由，并且选择路由的依据只是依照路由跳数和延时长短，这在很大程度上提高了网络中节点间彼此通信的能量开销，降低了最佳路由的建立概率［5］。近年来，随着GLONASS、GPS、北斗等定位系统的发展，许多研究人员通过定位技术使网络中各节点能够方便地获得自己的地理位置信息。借助地理位置信息，研究数据转发方案，能够使节点在探寻路由时减少过度的洪泛，增大探寻路由的效率［6］。

地理 AODV［7］（GeoAODV）是 AODV 协议的另一种改进，与LAR协议类似，它将寻找域限制在可能包含到目的地路由的网络部分［8］。不过，区别于LAR的地方是，GeoAODV并不假设目标坐标对发起路由发现过程的节点有效。GeoAODV依靠一个分布式进程在网络节点之间共享位置坐标。此外，GeoAODV定义的搜索区域不同于LAR，它可以动态调整当RREQ消息遍历网络时的搜索区域。它只通过仿真经验在不同节点密度情况下预设广播角度，在节点密度不均匀且拓扑快速变化的情况下适应度不高［9］。

LAODV协议［10］提出了最大前程策略的思想，它根据节点间的投影长度提出前程值的变量，在节点转发RREQ时根据前程值选取优先转发的中继节点以建立数据传输的最短路径。由于节点的前程值为衡量中继节点优先值的唯一变量，根据最大前程策略所建立的路由可能并不是最佳路由。且在节点密度低的环境下，按照前程策略选取中继节点容易出现路由空洞，节点需要多次重启路由发现过程，就会导致路由可建立概率减小［11］。

针对以上路由协议在不同节点密度的适应度不强的缺点，本文提出了一种根据节点密度自适应调整广播范围的位置辅助路由协议（AbAODV），协议通过网络内节点间定期交互的Hello报文获得网络中各节点的所处位置信息［12］，并考虑到相应时间内节点的位置变化提出最大误差值。基于前程值的思想提出最大优选区域，根据节点密度自适应调整广播角度来筛选中继节点，最后通过节点广播概率公式建立最优路由。能够在避免路由空洞情况下减少消息的冗余，减轻网络负载，提高协议效能。

1 AbAODV协议设计

AbAODV是借助定位技术所设计的按需距离矢量路由协议，需要在路由请求分组RREQ和网络中定期交互的Hello报文中添加当前节点的地理位置信息，以帮助建立最佳路由。

1.1 节点的偏移误差

在某一网络拓扑中，若源节点I向目的节点D转发消息，已知节点D的位置信息，但在转发过程中D点位置会随转发时间和路由寻找时间产生变化。这里考虑网络中最恶劣的情况［13］，为了避免错过最佳转发的中继节点，提出了目的节点位置最大误差值：

式中，Tr为一跳节点转发路由消息所需的时间；H为当前网络路由允许建立的最大跳数；Ti为节点周期性交互Hello消息的间隔时间；Vmax为节点最大移动速度。节点偏移模型如图1所示。

图1 节点偏移模型

图中，线段ID为源节点到目的节点的最近距离，D'为误差时间内节点竖向最大偏移位置。α为误差偏移角且满足：

1.2 前向优选区域

旨在寻找网络内两节点间通信的最短路径，LAODV协议引入了最大前程策略［10］在路由发现阶段：将转发数据的临节点在上一跳节点到目的节点的线段上的投影长度定义为前程值。如图2所示，Y1、Y2为源节点I的两个邻居节点，则Y1、Y2的前程值分别为K1、K2。

图2 最大前程策略

由于以前程值作为路由建立的依据具有局限性，所以AbAODV协议基于最大前程策略，提出了节点前向优选区域以进行节点密度的判断，节点的前向优选区域如图3所示。

图3 节点前向优选区域

阴影部分扇形为源节点I关于目的节点D的前向优选区域，它由两个以I为圆心，节点I的通信半径r为半径的半圆重叠而成。两个半圆分别被线段ID'，ID″平均分割，圆心角为π +2α。阴影区域的面积S为：

在该区域内，源节点I、邻居节点Y和目的节点D的位置信息能够借助定位系统获得，假设它们 的 经 纬 度 坐 标 分 别 为(xIE,yIN )，(xYE,yYN )，(xDE,yDN )，则 节 点 间 的 距 离 ：

通过计算节点间的距离，可以得到节点Y在线段ID上的投影值KY：

通过计算投影值，可以得到邻居节点Y的关于源节点I和目的节点D的投影角度β：

若β≤0.5π+α，则可判定节点Y处于节点I的前向优选区域内。

1.3 概率广播公式

通过计算所有位于自身通信范围内的邻居节点的投影角度，当前节点就可以得到位于自己前向优选区域内的邻居节点数量，从而计算当前节点的前向优选区域内节点密度的大小。由于移动自组织网络拓扑动态变化，前向优选区域内的节点密度也在不断变化。为了以较少代价选取有效的邻居节点，需要以前向优选区域圆心角度和前向优选区域节点密度大小为衡量值，设计自适应广播角度θ和广播概率期望值Pe：

式中，Nh为处于当前节点前向优选区域内的节点数量；Ne为参与广播的邻居节点数的期望值。Ne在仿真中的取值由仿真环境决定（如节点通信范围、节点个数、仿真区域大小）。结合最短路径问题，根据自适应广播角度值和广播概率期望值，设计中继节点的广播概率公式：

由中继节点的广播概率P与广播概率期望值Pe相比较，可作为该节点是否能够参与本次路由建立的依据。

1.4 AbAODV协议描述

基于前向优选区域和广播概率公式，以选取最优路径为目的，AbAODV的路由建立过程如图4所示。

图4 AbAODV路由建立过程

（1）网络中源节点向目的节点发送消息，源节点首先进行路由请求RREQ的准备工作：通过两节点的位置信息找到前向优选区域并计算广播角度θ和广播概率期望值Pe，结果记入RREQ并对其进行转发。

（2）接收到RREQ的邻居节点首先判断自己是否为目的节点，如果是，则回复路由应答RREP，否则进行以下判断：是否已接收过该消息，若是则直接丢弃RREQ，否则进行下一步。

（3）计算本节点关于上一跳节点的投影角度β，若β小于θ，则进行下一步计算，否则丢弃RREQ。

（4）计算广播概率P，若P不大于Pe，丢弃RREQ，否则继续进行RREQ的准备工作，直至目的节点接收到RREQ，并回复路由应答RREP以建立路由。

AbAODV的节点的自适应广播如图5所示。

图5 AbAODV节点的自适应广播

节点I向节点D发送RREQ消息，根据网络中各区域节点密度的差异和目的节点D的位置信息，中继节点能够自适应的调整广播范围并筛选最佳转发节点。

2 仿真与结果分析

为了对比分析AbAODV、AODV、LAODV、Geo⁃AODV协议的性能，借助NS-2仿真软件对它们在不同节点密度下的数据分组投递率、路由发起频率、端到端传输时延、归一化路由开销、平均吞吐量等方面进行比较，从而确定AbAODV协议的可行性。

2.1 仿真环境设置

仿真取1 000×1 000 m2的区域，节点的运动模型为Random Waypoint，移动速度在0～ 20 m/s之间，分组发送速度为5个/s，数据包大小为512 Byte，业务类型为CBR，传输层协议为UDP，仿真时间为 400 s，在节点数为 50，75，100，125，150个的情况下分别运行40次取平均值。

表1 仿真参数

2.2 仿真分析

图6显示了四种路由协议在节点密度变化的运动环境中分组投递率的具体效果。仿真结果显示，节点密度相对较低的情况下，四种路由协议的分组投递率均处于较高水平，但随着节点密度的提升，AbAODV的分组投递率下降趋势较为缓慢，这是由于AbAODV路由协议在LAODV的前向区域的基础上引入误差值理念改进为前向优选区域，降低了节点移动误差，在GeoAODV的广播角度调整的基础上基于节点密度的变化提出自适应的广播角度，减少了分组重发，所以其分组投递率在不同节点密度下都能有较好的表现。相比于AODV协议，AbAODV协议的分组投递率平均提高了11.5%，相比于LAODV协议平均提高了2.3%，相比于GeoAODV协议平均提高了4.7%。

图6 分组投递率仿真图

图7显示了四种路由协议在节点密度变化的运动环境中路由发起频率的具体效果。仿真结果代表着四种路由协议在单位时间内启动路由发现的频率，能够反映出协议在路由发现阶段的工作效率。图中可知，AODV协议的路由发起频率最高，且AbAODV协议的路由发起频率最低，这是因为AbAODV协议考虑到网络拓扑快速变化的特点，提出目的节点位置最大误差值以应对网络中出现的恶劣情况，减少了链路断裂的概率，提高了路由建立的有效性。相比于AODV协议，AbAODV协议的路由发起频率平均减少了19.1%，相比于LAODV协议平均减少了10.6%，相比于GeoAODV协议平均提升了12.6%。

图7 路由发起频率仿真图

图8显示了四种路由协议在节点密度变化的运动环境中路由开销的具体效果。随着节点密度的提高，路由协议需要管理的节点不断增多，所以在相互通信时需要转发更多的控制消息。仿真结果显示，节点密度相对较低的情况下，由于LAODV、GeoAODV协议较容易出现路由空洞，节点需要转发更多的RREQ消息来发现路由，所以其路由开销相对于传统的AODV路由协议表现较差，不过随着节点密度的提升，由于LAODV、GeoAODV均以限制广播范围，减少路由冗余为目的，所以其在节点密度适中条件下路由开销较低，且由于AbAODV路由协议相对于两者的改进，其在节点密度过高的条件下路由开销也处于较优水平。其中，相比于AODV协议，AbAODV协议的路由开销平均减少了54.1%，相比于LAODV协议平均减少了34.3%，相比于Geo⁃AODV协议平均减少了39.1%。

图8 归一化路由开销仿真图

图9显示了四种路由协议在节点密度变化的运动环境中端到端时延的具体效果，由于GeoAODV路由协议在开始最小广播角度传输失败后会多次的扩大其路由广播角度，所以其时延表现较差，由于LAODV和AbAODV在传统的AODV路由协议基础上都考虑了最短路径的问题，且AbAODV在数据转发过程中能够根据转发时间预估节点的偏移误差，减少了链路断裂的可能性，所以其端到端时延表现更加出色。相比于AODV协议，AbAODV协议的端到端传输时延平均减少了47.7%，相比于LAODV协议平均减少了35.3%，相比于GeoAODV协议平均减少了50.1%。

图9 端到端传输时延仿真图

图10显示了四种路由协议在节点密度变化的运动环境中平均吞吐量的具体效果。由于节点密度的提高会使节点间对于信道资源的竞争更加剧烈，这导致了四种协议的平均吞吐量都呈下降趋势。图中可知，AODV协议的平均吞吐量最低，AbAODV协议的平均吞吐量最高，这是因为AbAODV在计算广播RREQ概率时考虑了节点移动误差和节点密度，能够增加RREQ到达目的节点的成功率。相比于AODV协议，AbAODV协议的平均吞吐量平均提升了85.1%，相比于LAODV协议平均提升了31.2%，相比于GeoAODV协议平均提升了43.4%。

图10 平均吞吐量仿真图

3 结论

本文通过对传统的AODV路由协议其洪泛广播方式所存在的不足进行分析，寻找借助地理位置信息来达到限制网络广播的洪泛，从而减少过多冗余的路由消息和中继节点的数量、提高路由性能的方法。并借助相关文献搜集同类型的改进AODV路由协议的先进思想和存在的不足加以总结。根据节点的运动情况考虑到节点移动误差值，并基于LAODV路由协议前程值的思想提出前向优选区域，基于GeoAODV路由协议限制广播角度的思想提出概率广播公式，最终达到根据节点密度自适应调整广播角度来筛选中继节点，AbAODV通过节点广播概率公式建立最优路由。能够在避免路由空洞情况下减少消息的冗余，减轻网络负载，提高协议效能。通过仿真分析，在不同节点密度的情况下，AbAODV协议都有很好的性能表现。