移动Ad hoc网基于链路质量和局部拓扑的机会路由协议

汪红霞

(安徽新华学院 信息工程学院, 合肥 230088)

移动自组织网络(MANETs)是通过无线链路连接组成的一组可移动节点。在不借助静态基础设施的情况下，无线自组网中的每个节点都充当路由器，将数据包转发给其它节点。在传统的无线自组网路由协议(主动式或被动式)中，每个源节点或中继节点维护一张路由表来保存到达其它节点的路径。在反应式路由协议中，当一个节点想要与另一个节点通信时，如果连接两个节点的路径在路由表中没有找到，路由发现过程就会启动并在网络中广播一个路由请求包。当链路断开时，将启动一个新的路由发现。因此，反应式路由协议在路由发现中可能引起很大的负载。另一方面，在主动式路由协议中，节点通过周期性的交换路由信息包维护网络拓扑信息。传统的确定性路由协议适合静态或低动态环境。然而，在高速移动场景下，由于节点的移动拓扑频繁的改变，造成了每一个移动的节点很难维护确定性的路由。频繁交换拓扑更新信息也会导致资源的浪费。

机会路由利用广播的特性，使用某种路由度量来确定转发优先级。数据包以单跳广播的方式被转发，所以在转发数据包之前不需要维护确定的路由。与传统的路由相比，机会路由可以很好地适应节点频繁移动和拓扑信息难以维护的场景，克服了不可靠的无线传输的弊端。

然而，利用拓扑信息和移动性特征为移动场景设计路由协议仍存在挑战[1]。基于拓扑的机会路由协议,例如ExOR[2]在维护全局拓扑信息时存在很大的困难，它需要和相邻节点频繁的交换信息[3]。基于地理信息的机会路由在解决路由空洞问题上需要花费额外的负载[4]，这意味着这个节点除了本身外不能找到离目的节点更近的节点。况且，由于节点的移动性，地理转发机制不可能总是较适合的。一方面，机会路由将广播作为转发方法。这样，当一个节点向邻居节点转发数据包时，它可能会遭受来自其它发送节点的干扰，这将影响无线传输。另一方面，在移动自组网中，所有节点不可以预测地移动导致两个通信节点距离的变化。随着彼此之间移进或移出通信半径，节点之间的链路质量发生变化，这也影响了无线传输。

本文为移动自组织网提出一种基于链路质量和局部拓扑机会路由协议，该协议综合考虑移动场景下的拓扑位置信息和利用干扰与移动性去优化机会路由的两个关键过程：候选集的选择和节点的优先级的评定，从而本文的主要贡献如下：

(1)为发送节点确定候选节点集合。本文提出的协议综合考虑了MAC层引入的干扰以及节点移动性导致的链路剩余生存期的变化，通过更准确的评定节点间的链路质量确定更合适的候选节点集合。

(2)为候选节点评定优先级。本文提出的协议综合考虑了两跳范围内的位置信息、局部拓扑信息以及节点移动的自适应性，选出合适的转发节点，降低路由空洞的出现次数。

1 相关工作

机会路由可以归结为三大类：基于拓扑的、地理位置的和混合的机会路由。Biswas[2]等提出一种基于拓扑的机会路由称ExOR。ExOR首先在候选集中通过节点序列转发每个数据包，然后确定根据期望传输次数(ETX)选择哪个节点作为转发节点，ETX即所有节点成功接收数据包数。然而，在移动自组织网中，每个节点可能随机频繁地移动。估计一条不稳定路径上的ETX是很困难的，而且链路相关也影响ETX的准确性[5]。Wang等人[6]提出一种局部协作中继方法以扩展ExOR，这样可以进一步探索广播特性和桥梁失效链接。它利用多个不在候选集中的节点进行机会数据转发来维持一个健壮的拓扑。Yang等人[7]提出一种基于节点地理位置的机会路由。前一跳根据本地位置信息确定预定义的顺序。预定义的顺序插入节点IP报头中以通知候选集中的节点。Seada等人[8]研究了基于链路损耗模型的多中转发策略性能，分析了距离和跳数之间的权衡关系。他们发现数据包接受率(PRR)和距离目的地距离相乘(PRR*D),是一个非常适合无线传感器网络的地理转发度量。然而，PRR*D度量可以被推荐用于静态或低动态环境中，如环境监测。在高动态环境下，整个时间链路质量可能变化很大，PRR的稳定估计可能无法获得。Zhao等人[9]提出混合式协议CAOR，其中候选集每个节点利用采用多跨层信息，如地理进程、能量、链路质量和移动来决定自己的优先级。具有最高优先级的节点具有转发数据包的权限，CAOR也能调整在运行时上下文信息的权重。

2 基于链路质量和局部拓扑的机会路由

当源节点需要发送数据包到目的节点时，OR-LqT首先会选择候选集中具有优先权的节点作为下一跳，然后再到候选集中所有节点。每一个收到数据包的节点发送一个ACK应答源节点。然后根据ACK源节点为候选集所有节点分配优先级。具有最高优先级的节点将数据包转发给邻居并继续该过程，直到数据包到达目的节点为止。

地理信息可以引导机会路由协议向正确的方向转发，并加速协议的收敛性。然而，它也可能会导致路由空洞。这种边界转发方案产生了数据包转发死角区。虽然一些机制被提出用来解决这个问题，但需要花费额外的时延和跳数。拓扑信息可以在一定程度上反映网络的全局连接，可以引导转发数据包朝正确的方向转发，然而，由于无线自组网的维护成本高，拓扑信息很难获得。一个好的机会路由在无线自组网应具有快速收敛和低成本转发数据包。更重要的是，它应该适应节点移动带来的频繁变化的拓扑。

本文将分别讨论机会路由中候选集和优先级这两个处理过程，以及它们的决定因素。

2.1 候选集的影响因素

候选集的选择是控制机会路由负载的一个重要程序。只有侯选集里的节点才有权转发数据包。如果集合太大，有限的能量就会被浪费很多。因为有些节点可能收到冗余包，这会给其他的发送节点造成大量的干扰。如果集合太小，它可能转发失败。本案确定候选集的决定性因素是传输时的链路质量，这是由机会路由的特征决定的。机会路由利用广播特性，每次转发都是一个新的程序，与上一次转发毫无联系。如果链路质量好就足以完成转发。节点可能被选做发送节点集。当发送节点需要转下一次数据包时，需要开启一个新的广播。

与无线网络不同，在移动Ad hoc网络中，节点随意地独立移动，这个节点的移动可能引起链路质量的变化。因此，解决变化的链路质量问题需精确的链路质量测量。精确的链路质量测量可以降低发现成本、减少未知链路质量引起的数据重发；同时，还需要具备高效、灵活、低成本等特性。

2.2 哪些候选节点应获得更高的优先级

为所有候选做优化是机会路由中的一个重要过程，它决定了不同候选的转发概率。一个好的优化方案，可以提高转发效率和避免重复转发。在无线自组织网络中，优先级由两个因素决定，一个是地理位置，另一个是移动适应性。位置意味着下一个节点应该有一个更接近目标的的节点。移动适应性有两层含义：一是下一个节点应该有一个正确移动趋势。当节点朝目标节点相反方向移动时，它不是很好的下一跳选择，即使它有一个更近目标的位置，它也可能将数据包传送到一个不必要的区域，所以，这个数据包可能被转发远离目的地。移动趋势的另一层含义是，下一个节点还应该有它的下一跳选择。当发送节点转发数据包到下一个节点时，需要考虑下一个节点的下一跳选择。这是一个重要的概念,因为，虽然对于下一个节点来说是一跳的信息，但对于发送节点来说是一个两跳的信息，更多了解候选集的拓扑结构能够有效降低路由空洞产生的概率。

2.3 详细设计

一个精确的链路质量测量可以帮助节点在一个更稳定的环境中通信，可以减少冲突概率和重传次数。自组织网中，两个节点之间通信受节点移动性和冲突的影响。节点的移动性引起两个节点之间距离的变化，从而导致变化的链路质量。当一个节点发送一个数据包给另一个节点时，数据包可能会遇到从其它同步数据包传输的冲突。本文同时考虑节点的移动性和冲突。

关于冲突的影响。当一个节点s想要发送数据包，节点s成功传输数据包给节点r的概率为：

Psucc=1-(PaPc)N,

(1)

其中，Pa为结点s，是在一个虚拟时间槽内试图传输的概率，Pc为假定传输条件下的冲突概率，N为有限的重传次数。

Pc=1-(1-pa)|CS∩INr|,

(2)

其中|CS∩INr|是在载波侦听范围(CS)和干扰区(INr)干扰结点次数。从文献[10]获知：

(3)

至于移动性影响，使用一个简单而有效的方案估计两个节点移出彼此通信范围的概率，文献[11]假设D0、D1和D2是节点s和节点r在T0、T1和T2时刻之间的距离。在t时刻的距离可以表示为D(t)2=At2+Bt+C，能够得出：

(4)

其中，t1=T1-T0，t2=T2-T0。

RLL(t)=Tb-t=tb+T0-t

(5)

则节点s和节点r之间的链路稳定性可以表示为：

(6)

由公式(1)和(6)，可以得出节点之间的链路质量为：

Pq=Psucc*Ps,

(7)

本文使用Pq来选择候选集。当节点i和发送节点s之间的链路质量Pq满足Pq>ε时，节点i可以被选作为候选节点集中的候选，ε是一个域值。

在候选集中要选择一个最佳的转发节点，需要把两跳相关的位置信息、局部拓扑和移动适应都考虑在内。离目的地较近的位置，可以减少传输期间的跳数，从而降低路由协议的成本。然而，一味的求近也会让路由空洞产生更多无用的边界转发。移动适应性矫正优化传输方向。在网络中这点很重要，因为一个朝目的节点相反方向移动的节点转发有负面的影响，应该消除这种节点。此外，这样的节点可能会导致路由空洞，也应该被淘汰。

综上所述，当节点s转发数据包时，下一个节点应该位于节点s和目标节点组成的矩形区域内。当一个节点发送数据包给邻居时，会插入自己当前位置的信息。邻居接收到数据后，会重新计算发送节点的位置，更新自己的邻居集。节点i的优先级定义为：

(8)

图1 节点i的优先级的示例

本文修改了ACKs、hello和数据包的格式。在ACK包中插入移动自适应信息、“更好的邻居”集和位置，使发送节点能够作优先级的评估。在hello包和数据包中插入发送节点的位置和邻居信息，使接收者能够更新其“更好的邻居”集。

图1阐述了节点i的优化，算法1描述了OR-LqT协议。

算法1基于链路质量与局部拓扑信息的机会路由协议定义：Ns()：节点s的邻居集.Nbs()：离节点s到目的地更近的一组邻居集.Lqs，a()：节点s与节点a之间的链路质量.Cs()：节点s的候选集.ds，D：节点S与节点D之间的距离.ifnodesreceivesadatapacketfromnodeathen{replyanACKwithNbs()Ns()andmovingdirectionmd}endififnodeshasadatapackettoforward：then{determinethecandidatesetCs()basedonlinkqualityLqs，a()}{broadcastthepackettoallthenodesinCs()；}endififnodesreceivesanACKfromnodekthen{computethepriority；}foreverynodeiinCs()doifmd>0&&Nbi()！=0thenPr=1-di，Dds，Dæèçöø÷×Nbi()Ni()endifendforendif

3 协议实现和性能评价

本文利用NS-2，将PRR*d[8]、贪婪地理路由协议GPSR[4]、反应式路由协议AODV协议[12]和OR-LqT进行对比仿真。设置网络45,80,125,180个节点的传输范围250米和每12500平方一个节点的密度。移动模型采用随机移动模型(RWP)[13]暂停时间为0秒。仿真参数如表1所示。

表1 仿真参数

对比不同的移动速度与链路质量参数，使用空洞数、丢包率、时延和路由负载度量反映这些协议性能实验结果如下：

空洞数：空洞节点意味着除了自己不能找到一个更接近目的地的节点。图2显示了传统的GPSP、PRR*d和OR_LqT空洞的数量。在GPSR和PRR*d中贪婪转发可能产生一个局部最大值，这意味着一个节点不能找到比它自己更好的下一跳。在本文的OR_LqT协议里，拓扑和地理信息都被考虑，其中包含移动自适应性和位置。移动自适应性，指示移动方向和一个更好下一次选择，矫正转发到最佳区域并减少空洞数。与GPSR协议相比，减少了41.5%的空洞数目，而与PRR*d相比，OR_LqT减少了大约33.5%。

图2 空洞数与节点数的关系图

图3 丢包率与节点数的关系图

丢包率：比较OR_LqT与其他协议的丢包率。图3显示，在GPSR中采用贪婪转发，而在PRR*d候选集选择地理距离和链路成功接收率乘积的最大值。在AODV中，节点的移动性导致拓扑频繁变化和链路故障的发生。因此，它增加了丢包率。在OR_LqT协议中可以获得更精确的链路质量测量，这种测量考虑了干扰和移动性，使用了MAC层成功传输概率的信息和路由层的移动模型。因此,避免了不稳定的传输。平均而言，OR_LqT与AODV相比丢包率减少大约62%，与PRR*d相比，丢包率减少大约21%。

图4 平均端到端时延与节点数的关系图

图5 标准化路由负载与节点数的关系图

平均端到端时延：图4显示所提出的OR_LqT，PRR*d，GPSR和AODV的平均时延。在AODV协议中，每个节点保持一个确定的路由。频繁的链路故障引起了很多的改变，从而增加路由发现的次数。也增加了平均时延。因为GPSR仅考虑地理转发，所以可能会导致路由空洞。边界转发为了摆脱空洞需要采取额外的跳数和时延，而提出的OR_LqT考虑了位置和移动适应性。如图2所示。空洞的数目随着周边转发次数的减少而减少。此外，精确的链路质量测量带来一个更稳定的传输环境，减少数据包的冲突概率和重传次数。由于上述原因，平均时延降低。相比AODV协议，提出的OR_LqT降低了约61%的平均时延，而与PRR*d相比，平均时延降低约22%。

图6 标准化路由负载与速度的关系图

标准化路由负载：图5显示了OR_LqT、PRR*d、GPSR和AODV的负载。机会路由负载计数了hello包和ACK的数量，而路由控制分组的数量，像RREQ、RREP和hello包都算在AODV路由协议中。当路由失败时，一个新的路由发现开启。因此，在AODV中增加了路由控制包的数量和路由负载。然而，机会路由数据包被广播转发，在AODV协议中较少的路由控制包产生，包的大小如ACK也比RREQ、RREP、RRER包小。如上图所示。OR_lqT降低了丢包率和空洞数，以至于重传和去除空洞的额外转发次数也减少，因此，降低了负载。平均而言，与PRR * D相比，负载减少了约21%，与GPSR相比，负载减少约32%。

OR_lqT针对高速动态环境，本文也验证了其在不同场景下的性能。仿真了四个不同的协议在网络大小为1250*1250平方米和125个节点，速度从0m/s到20m/s。图6显示变化速度的标准化路由负载。当网络是静态或者接近静态时，通过路由发现获得的路由信息可以维持很长一段时间。因此，AODV比机会路由性能更好，但在AODV中，随着节点速度的增加，拓扑结构的变化更频繁，路由发现次数增多，导致更多的负载。

5 结语

本文为移动Ad Hoc网络提出了一种基于链路质量和局部拓扑的机会路由协议。该协议通过链路质量选择候选集，并通过优先级选择下一个转发节点，增加直接转发概率，减少路由空洞数。其中链路质量同时考虑了干扰和节点的移动性，而候选集的优先级则根据它们的位置、局部拓扑和移动适应性来决定。仿真结果表明，同样的移动环境下，本文提出的OR_LqT在空洞数量、平均时延、丢包率和负载方面比其它路由协议具有更好的性能。

参考文献：

[1] Q Wang, X Wang, X Lin. Mobility Increases the Connectivity of K-hop Clustered Wireless Networks[J]. Proc.ACM MobiCom，2009(9)：121-132.

[2] S Biswas， R Morris. ExOR:Opportunistic Multi-Hop Routing for Wireless NetWorks[J]. Proc.ACM SIGCOM，2005，35(4)：133-144.

[3] Z Zhang， R KrishnanAn. An Overview of Opportunistic Routing in Mobile Ad Hoc Networks[C]// Proc.IEEE MILCOM, San Diego:2013：119-121.

[4] B Karp Harvard, H T Kung. GPSR:greedy perimeter stateless routing for wireless networks[C]// Proc.ACM MobiCom，Boston:Harvard University,2000：243-254.

[5] M K Song, S Guo, T He， et al. Link Correlation Aware Opportunistic Routing[J]. Proc.IEEE INFOCOM.2012,14(1)：3036-3040.

[6] Z Wang, C Li, Y Z Chen. Local cooperative relay for opportunistic data forwarding in mobile ad-hoc networks[J]. Proc.IEEE ICC，2012,1(8)：5381-5386.

[7] S Yang, F Zhong, C K Yeo, et al. Position based Opportunistic Routing for Robust Data Delivery in MANETs[J]. Proc.IEEE GLOBECOM，2009(1)：1-6.

[8] K Seada, M Zuniqa, A Helmy， et al. Energy-efficient forwarding strategies for geographic routing in lossy wireless sensor networks[J]. Proc.ACM SenSys， 2008(4):108-121.

[9] Z Zhao, T Braun, D Rosario， et al. CAOR:Context-aware Adaptive Opportunistic Routing in Mobile Ad-hoc Networks[J]. Proc.IFIP WMNC，2014(10)：1-8.

[10] Y Yang, H J C, L Kung. Modeling the Effect of Transmit Power and Physical Carrier Sense in Multi-hop Wireless Networks[C]. Proc.IEEE INFOCOM，2007：2331-2335.

[11] X M Zhang, K Chen, Y Zhang， et al. A Probabilistic Broadcast Algorithm Based on the Connectivity Information of Predictable Rendezvous Nodes in Mobile Ad hoc Networks[C]. Proc.IEEE ICCN workshop of BDeHS,2014.

[12] C Perkins, E Belding-Royer, S Das. Ad Hoc On-Demand Distance Vector (AODV) Routing[C]. IETF RFC Santa Barbara:University of California,2003:3561.

[13] D B Johnson, D A Maltz. Dynamic Source Routing in Ad Hoc Wireless Networks[J]. Mobile Computing,Kluwer Academic Publishers,1996(353)：153-181.