基于位置信息的无线自组网路由算法对比研究∗

胥建鹏 敖 欣

（1.西安工业大学电子信息工程学院 西安 710021）（2.东莞理工学院网络空间安全学院 东莞 523808）

1 引言

不依赖于固定基础设施，无线自组网中各节点通过自组织、自我管理的方式动态组网［1］，具有很高的灵活性。因此，针对这种拓扑变化频繁的网络设计适应性强的路由协议成为国内外学者研究的重点［2］。功率所限，无线节点只能直接与周围一跳邻居节点进行通信。在此限制下，传统无线路由协议所能依靠的决策信息非常有限，对邻居节点的运动也缺乏预测性。虽然有些路由算法基于无线信号传播经验模型、节点运动与信号变化的关联模型等分析手段，可以获得一些粗粒度的相对位置信息，但仍然存在较大的决策误差。

近年来，随着GPS接收装置走向微型化、低功耗、低成本，越来越多的无线节点开始装备GPS模块。因此，利用节点位置这一新的决策信息，来更好地建立无线自组网路由，逐渐成为一种实用的路由选择。此类算法也因此被称为地理位置路由算法。其中，作为典型代表的GPSR协议应用最广，并催生了包括GPSR-R、WF-IGPSR等在内的后续改进协议。利用内置的节点位置信息，地理位置路由算法可免于路由维护，具有路由开销小、时延性能好等显著特点。然而，受传输功率所限，节点间的位置信息交互仍然只能局限在一跳传输范围，导致节点只有局部的位置视野，容易遭遇路由空洞而降低路由转发效率。此外，考虑到节点运动方向、速度均可能发生变化，基于节点间交互的位置信息进行的位置预测很可能失效。特别是当节点移动速度较大、节点密度稀疏时，节点位置信息可能频繁失效，并引起严重的丢包。

理想的Ad-Hoc网络的路由协议必须具备以下功能：1）维护网络拓扑的链接；2）快速地了解网络拓扑结构的变化；3）良好的自适应能力［3］。由此而知，地理位置路由算法仍然存在一定的优化空间，需要彻底解决路由空洞、位置信息交互频率的自适应调整等挑战。为此，本文对GPSR及其改进算法GPSR-R、WF-IGPSR进行对比研究，并基于NS2仿真平台，从端到端时延和分组交付率等角度对上述三种算法优缺点进行客观分析与评价。

2 GPSR及其改进算法基本原理

GPSR（Greedy Perimeter Stateless Routing ，GPSR）［4］贪婪周边无状态路由协议是一种典型的基于地理位置信息的自组网路由算法。网络中的每个节点通过GPS获得自身位置，源节点根据数据分组中目的节点位置完成分组的转发［5～6］任务。GPSR有两种转发模式，贪婪转发和周边转发［7］。GPSR路由协议的贪婪转发是将其传输范围内离目的节点最近的节点作为下一跳节点［8］。在网络中节点分布均匀且移动速度相对缓慢的情况下，GPSR能够将分组较快的转发到目的节点。但在网络节点分布不均和节点移动速度较快的情况下，由于GPSR路由判据单一，选择的下一跳节点大都分布在通信的边界区域，容易引起路由空洞和丢包。在分组转发过程中遇到路由空洞时，GPSR将自动切换到周边转发模式，借助平面图和右手法则绕过空洞区域［9］，当再次满足贪婪转发条件时，网络又将切换到贪婪转发模式。GPSR路由协议存在当贪婪转发失效而采用周边转发而造成路由冗余度增加的现象，此外，邻居表信息更新过慢，在转发数据包时，保存在表头中的目的节点位置没有更新等［10］。因此，GPSR路由协议依然有需要改进的地方。

GPSR-R（Reliability Based GPSR Protocol）［11］是GPSR的一种改进算法，针对GPSR算法中下一跳节点选择机制的缺陷和链路质量低下等问题，GPSR-R算法侧重强调链路质量，关注分组交付率。为了获得可靠的传输路径，选择相对稳定的节点作为下一跳转发节点，GPSR-R在链路稳定性高于一定阈值的链路上完成分组的转发任务，可以有效避免GPSR算法选择下一跳节点分布在节点通信边缘的风险所引起的链路不稳定和极易断裂情况，因此，GPSR-R算法获得了较高的分组交付率，但同时，由于过分注重传输链路的稳定性，增加了分组的转发跳数，GPSR-R算法的时延特性比GPSR差。

WF-IGPSR（The Weighted Function Based GPSR Protocol）［12］是GPSR的另为一种改进算法，针对GPSR路由算法选择的下一跳节点缺乏稳定性、容易遭遇路由空洞等问题，WF-IGPSR算法提出了利用权重函数在邻居节点中选择可靠的下一跳分组转发节点。权重函数受三方面的因素影响，第一，链路的稳定性，用来描述所选择路径的可靠程度；第二，距离，即下一跳转发节点到目的节点的距离，用来描述下一跳节点与源节点的接近程度；第三，运动方向，用来描述下一跳节点运动方向与目的节点所在位置的偏向程度。源节点在邻居节点中选择权重函数最大的邻居节点作为下一跳分组的转发节点，既可以保证数据分组转发链路的稳定性，又可以有效地降低路由空洞出现的概率，因此，WF-IGPSR算法能够保证一定的分组交付率的情况下兼顾了时延特性，在两者之间进行比较合理的折中和均衡。

3 仿真分析

无线自组网中路由算法的性能主要通过分组交付率和平均端到端时延等指标进行评价。分组丢包率越高表明路由协议的性能越稳定［13］；平均端到端时延越小，表明网络中路由投递的分组越快［14］。为了验证GPSR、GPSR-R和WF-IGPSR的网络性能，利用NS-2仿真平台，通过多次实验取平均值的方法获得不同算法对应的性能参数，并对三种算法做出客观的、合理的评价。由于在Ad-Hoc自组网中，路由的性能受网络中节点密度和移动速度影响显著，因此，本次实验分成两部分来完成。其中，第一部分是不同节点密度下三种路由协议的性能对比；第二部分是不同节点移动速度下三种路由协议的性能对比。实验主要参数设置如表1所示。

表1 实验参数

3.1 不同节点密度下的路由性能分析与评价

图1和图2描述的是不同节点数变化时，GPSR、GPSR-R和WF-IGPSR三种算法在平均端到端时延和分组交付率方面的比较。

图1 平均端到端时延与节点密度的关系

图2 分组交付率与节点密度的关系

由图1可知，三者的变化曲线可描述为，三种路由算法的平均端到端时延曲线随节点密度增大呈现下降趋势，其中，GPSR的时延最小，WF-IGPSR次之，GPSR-R时延最大。具体表现为当网络中节点数目在20～35个范围变化时，GPSR、WF-IGPSR和GPSR-R之间的时延差距较大，随着节点数目的增多，三者的时延差距呈现缩小态势，时延性能相当。其原因在于GPSR算法采用贪婪转发策略，能够维持较小的时延；WF-IGPSR算法在选择下一节点时，因为考虑了距离和方向角因素，能够使数据分组沿着目的节点方向快速的转发，但由于兼顾了传输链路的质量，所以，WF-IGPSR算法的传输时延性能不如GPSR；GPSR-R算法侧重传输链路的稳定性，为了选择可靠的下一跳节点，牺牲了时延特性，所以，时延特性最差。但随着节点密度的增加，可供选择的中间转发节点数目也随之增加，三者之间的差距不断缩小；当网络中节点数目为50个左右时，三者的时延特性表现相当，均降至50ms左右。

由图2可知，三者的变化曲线可描述为：三种路由算法的分组交付率随节点密度增大呈上升趋势，其中，GPSR的分组交付率最低，WF-IGPSR次之，GPSR-R最高。具体表现为当网络中节点数目在20个左右时，GPSR和WF-IGPSR算法的分组交付率只有35%左右，而GPSR-R为50%左右，相差较大；其原因是网络中节点数目较少时，GPSR和WF-IGPSR算法可供选择的下一跳节点数目相对较少，选择的分组转发路径质量较差，容易断裂，分组交付率较低；GPSR-R算法侧重传输链路的稳定性，选择可靠的、质量高的链路进行分组转发，分组交付率最高。随着网络中节点数目的增加，三种算法都能选择相对稳定的链路进行分组转发，各自对应的分组交付率也随之不断升高，相互间的差距也呈现缩小态势，当网络中节点数目为50个左右时，GPSR、WF-IGPSR和GPSR-R算法的分组交付率分别达到86%、95%和98%左右。

3.2 不同节点移动速度下的路由性能分析与评价

图3 平均端到端时延与节点移动性的关系

图3 和图4描述的是不同节点平均速度时，GP-SR、GPSR-R和WF-IGPSR三种算法在平均端到端时延和分组交付率方面的比较。

图4 分组交付率与节点移动性的关系

由图3可知，三者的变化曲线可描述为：三种路由算法的平均端到端时延曲线随节点速度增大呈现上升趋势，其中，GPSR的时延最小，WF-IGPSR次之，GPSR-R时延较大。具体表现为当网络中节点的平均速度为40km/h～60km/h时，网络拓扑结构变化相对缓慢，链路质量相对较好，数据分组在网络中能够得到及时的转发，三种算法的平均端到端时延较小；随着节点移动速度的增加，三种算法的平均端到端时延增大，当节点平均速度为120km/h时，引起网络拓扑结构频繁变化，下一跳节点可靠性和链路质量随之下降，网络中节点为了及时更新各自有效的邻居节点表而需要使用大量的控制信息，这将占用大量的网络资源，网络拥堵程度随之加重，数据分组不能得到及时转发，GPSR、WF-IGPSR和GPSR-R三种算法的传输时延随之分别增至175ms、210ms和250ms左右。具体原因在于GPSR算法选择邻居节点中距离目的节点最近的节点进行分组的转发，时延最小；WF-IGPSR算法在链路质量和传输时延之间进行均衡，选择邻居节点中权重函数值最大的节点进行分组的转发，时延方面比GPSR大；GPSR-R算法只注重传输链路的质量，时延特性表现最差。

由图4可知，三者的变化曲线可描述为：三种路由算法的分组交付率随节点运动速度的增大呈下降趋势，其中，GPSR的分组交付率最低，WF-IGPSR次之，GPSR-R最高，并且GPSR算法的分组交付率性能较WF-IGPSR和GPSR-R算法下降速度较快。具体表现为当网络中节点的平均速度为40km/h～60km/h时，三种算法所选择的下一跳节点相对稳定，转发路径也相对可靠，分组交付率维持在85%以上；随着节点运动速度的增大，三种算法的分组交付率呈现下降趋势，其中GPSR算法的分组交付率的下降趋势最为突出，当节点平均速度为120km/h时，由于快速移动导致网络中所有节点位置的不确定性增大，选择的下一跳分组转发节点运动出源节点的通信范围的风险随之增大，数据转发路径越不可靠，GPSR、WF-IGPSR和GPSR-R算法的分组交付率分别降至60%、75%和80%。其具体原因是，GPSR算法仅以最短欧式距离为依据选择的下一跳节点大都分布在节点通信的边界区域，随着节点运动速度的增大，下一跳节点移出源节点通信范围的风险越大，对应着链路质量越差，分组交付率最低；WF-IGPSR算法较GPSR算法，以权重函数选择的下一跳节点相对可靠，传输链路相对稳定，能够维持一定的交付率；GPSR-R算法侧重强调链路质量，选择分组的转发路径可靠性最高，因此，交付率性能最好。

4 结语

为进一步探索地理位置路由的优化空间，本文对GPSR及其改进算法GPSR-R、WF-IGPSR进行对比研究。仿真实验结果表明，在三种算法中，GPSR的时延特性表现最好，而分组交付率特性表现最差；WF-IGPSR的时延特性和交付率特性表现居中；GPSR-R的交付率特性表现最好，而时延特性表现最差。三种算法的设计有不同侧重点和应用需求，整体而言，WF-IGPSR算法能够保证一定的分组交付率的情况下兼顾了时延特性，在两者之间进行了比较合理的折中和均衡。三种算法共同的缺点是，都采用固定的信标交互周期。这在一定程度上严重影响和制约了路由算法的性能和适用空间。在Ad-Hoc网络中，节点的随机移动是最显著的特征，也是引起网络拓扑结构随时都可能发生变化的根本原因，因此，网络拓扑结构变化快慢和邻居节点表更新间隔的同步性显得尤为重要，而邻居节点表的更新需要借助节点间的信标交互信息来完成，所以，网络中节点之间的信标交互间隔的选择成为了研究的重点。当信标交互间隔选择较小时，当网络规模较大时，频繁的信标交互信息占用大量的网络资源，容易引起拥堵；当信标交互间隔选择较大时，邻居节点表的更新将滞后于网络拓扑变化，容易出现邻居节点表失效问题。鉴于固定式信标间隔的上述缺点，如能够根据网络环境的变化自动调整信标交互间隔，即采用自适应式信标交互间隔，将有望解决频繁交互的网络拥堵或交互迟滞引发的邻居节点表失效等问题。换言之，自适应信标交互周期体制更适用于拓扑变化快的无线自组网，并可考虑作为进一步优化无线自组网地理位置路由算法的一个实际着手点。