移动Ad Hoc 网络中机会路由转发策略的研究

聂 志，刘 静，甘小莺，徐友云，刘汉春

(1.上海交通大学电子工程系无线通信技术研究所，上海 200240;2.综合业务网理论及关键技术国家重点实验室，陕西 西安 710071;3.上海数字多媒体处理与传输重点实验室，上海 200240)

0 引言

近年来，研究者提出了许多应用于移动无线自组织(Ad Hoc)网络的路由协议［1-5］。这些路由协议大致可分为2种类型:传统移动Ad Hoc路由协议和移动Ad Hoc机会路由协议［6］。传统Ad Hoc路由协议大多数是从有线网络发展而来，这些协议常常选择一条从源节点到目的节点的固定路径，在整个业务传输的过程中，均使用这条路径进行传输直至传输完毕或者此路径失效，如经典的 DSR［1］和 AODV［2］路由协议。然而，这样的静态路由策略需要建立端到端的基于全局链路状态的路由，需要存储路由信息表，需要在数据传输过程中维持一条固定的路由。显然这样的路由协议并不适用于具有移动节点的Ad Hoc网络。因此在传统路由中，节点的移动性成了影响网络各项性能的一个很重要的原因。

基于上述原因，研究者们提出了一种新的应用于移动Ad Hoc网络的路由技术—机会路由。机会路由是和传统路由截然不同的一种应用于无线多跳网络的路由技术，其特征在于，它不是在传输开始之前预先指定一条固定的传输路径，而是在每一跳结束以后，动态地选择一个合适的节点作为转发节点继续传输［7-9］。机会路由可以解决传统路由中因节点移动性而导致的某条路径频繁失效的问题，同时能很好地利用无线传输广播的特性和空间分集，降低链路质量波动所带来的影响［5，10］。机会路由所带来的众多好处使其成为了当前移动Ad Hoc网络路由技术中的一项热点研究对象，本文所做的工作也是应用于机会路由的。

目前，大多数机会路由协议中所使用的转发策略为贪婪转发策略［7-8，11-12］。贪婪转发策略指转发节点在邻居节点中找一个离目的节点最近且比转发节点离目的节点距离更近的节点作为下一跳节点。机会路由协议GeRaF就是采用了贪婪转发策略的一个很经典的路由协议，它根据“距离目的节点的距离的远近”定义了不同的优先级区域，从而设计出了基于优先级的竞争转发机制:各个节点根据距离值在不同的时刻回复允许发送(clear to send，CTS)，距离值越小的节点优先级越高，越快回复CTS，从而竞争得到转发机会。而且，它规定了相对复杂的握手动作用于避免候选节点之间的冲突。文献［7-8，11-12］已经证明了机会路由协议GeRaF(geographic random forwarding)拥有比传统路由协议更好的时延和吞吐量性能。然而在这样的贪婪转发策略中，候选中继节点仅仅根据当前本地节点的情况判断自己是否应承接此次转发，那么即使在一个连通的网络中也会出现这样的问题:经过某节点转发之后的若干跳内，没有可用的后续节点能转发当前的数据报文。因此网络的成功传输率会减小，尤其是在某些有障碍物的场景中或网络节点密度较低的场景中。

本文中我们提出了一种新的转发策略:机会路由中考虑后续路径的转发策略(selection considering future path，CFP)。在CFP中，节点会考虑某一跳之后若干跳的传输情况，从而做出是否应该参与转发此数据报文的决定。

1 问题描述

前面提到了在贪婪转发策略中，后续路径中可能会出现没有转发节点可用的情况，其原因是:当前转发节点的邻居节点中距离目的节点最近的点，它成功收到了当前转发节点转发的数据报文，然而它没有比其距离目的节点更近的邻居节点。即使这个节点仍然拥有比其距离目的节点更近的邻居节点，那么经过此点转发后，在若干跳中，仍然有可能会出现类似的情况。

如图1所示，假设节点传输半径为R，源节点是S，目的节点是D。根据贪婪转发策略，N0是S点距离目的节点最近的一个点，它将有最大可能获得转发的机会。此跳之后，N1和N2都是当前转发节点N0的邻居节点，而且他们距离目的节点相对N0更近，他们将竞争获得此跳的转发权。N1是N0所有邻居中距离目的节点最近的节点，它将有最高的优先级赢得此次转发。然而，如果N1得到了转发的机会，那么就会出现上述问题:N1的邻居节点中，没有比其距离目的节点更近的邻居节点可用来进行转发。实际上在基于贪婪转发策略的GeRaF中，当N1尝试着发了若干次请求发送(request to send，RTS)之后，如果没有收到候选节点返回的CTS，它将丢弃此次传输的数据报文。然而，如果N2得到了转发机会的话，那么通过N2-N3-N4，目的节点是能够接收到这个数据报文的。N1就是一个“似乎可以胜任转发任务”的节点。如果这样的节点获得了转发的机会，那么实际上数据报文是有很大可能不能成功到达目的节点。

图1 中继节点选取示意图Fig.1 Relay node selection example

2 考虑后续路径的转发策略

2.1 考虑后续路径的转发策略的基本思想

CFP的基本思想如下:首先确定候选节点，接着对候选节点进行后续路径检测，以确定合格的候选节点，最后合格的候选节点竞争发送CTS。当一个节点接收到RTS的时候，首先确定自己是否是一个候选节点，如果某节点是候选节点，那么该节点才对自己进行后续路径检测，否则此节点不发送CTS。候选节点的确定包括3个条件，全部满足则是候选节点，设当前转发节点为CN，那么这3个条件可表示为:1)是CN的邻居节点;2)和目的节点的距离较CN而言更近;3)不是CN上一跳节点的邻居节点。前2个条件是贪婪转发策略中判断是否是候选中继节点的条件，而第3个条件则是为了防止在机会路由中出现传输死循环式。如果候选节点不存在，那么将没有CTS回复到CN，CN将暂时缓存此数据报文，等待一段时间之后再次发送RTS。若CN对同一数据报文发送了指定次数的RTS都没有得到回复，那么CN放弃此数据报文。

如果这样的候选节点存在，那么此候选节点在本地范围内被标记为当前转发节点的下一跳候选节点(设为FN1)。FN1接着开始进行后续路径的检测，估计通过此FN1是否能够使得此数据报文到达最终目的节点。FN1用其邻居节点的地理位置信息作检测，检测的方法和上述类似，搜索FN1的邻居节点中是否存在一个适合进行接下来第二跳转发的节点FN2，FN2需要满足的条件表述为:1)是FN1的邻居节点;2)和目的节点的距离较FN1而言更近且是FN1邻居节点中距目的节点最近的一个点;3)不是CN的邻居节点。选中FN2之后，在FN1本地节点范围内继续搜索是否存在FN3，接着搜索 FN4，FN5，…，这样的检测模式类似于一个嵌套搜索的过程。设FNK为第K－1次后续搜索所得的候选节点，当目的节点在 FNK传输范围内时，或者当FN(K+1)不存在时，检测结束。前一种检测结果表明通过本候选节点FN1的转发，该数据报文能够到达目的节点;后一种检测结果表明无法到达目的节点。若检测得出可以到达目的节点，那么此候选节点参与发送CTS的竞争，否则退出此次转发。如图1所示，当N1接收到RTS时，根据CFP，它能得出自己是候选节点，然而在第一轮搜索时就不能找到FN1，因此检测结果为N1不能参与转发的竞争。然而N2可以检测到如果自己拿到转发机会，能够使得数据报文成功到达目的节点D，于是N2参与转发，通过接下来的N3-N4，数据报文就到达了D。

候选节点竞争转发数据报文的过程和贪婪转发策略类似:根据和目的节点距离的大小划分发送CTS的时间优先级，距离目的节点更近的节点更早地给CN回复CTS，如果多个CTS冲突，那么发送CTS的候选节点采用随机时间等待的退避算法随机等待一段时间之后再重发CTS，保证只有一个CTS到达当前转发节点。

2.2 CFP 转发策略

考虑节点的移动性，将会有另外一个问题，如图2所示，目的节点在N1收到N0所发的RTS时处于D1的位置，此时N1能够参与竞争并且可以获得转发权。然而当N1接收完数据报文准备发送RTS时，目的节点从D1移动到了D2的位置，于是当N1发送了几次RTS之后，没有CTS回复，N1就丢弃了这个数据报文。同样，在图1中，如果N1需要传输一个自己产生的数据报文给D，那么也是无法实现的。为了使这些数据报文能够成功传输出去，CFP

图2 考虑移动性的中继节点选取示意图Fig.2 Example of relay node selection with node mobility

选取候选节点:当一个节点收到RTS以后，它首先检测CN其本身是否是一个合格的候选节点，检测过程和前述方法类似，估计经CN转发之后通过一系列FN的传输，是否能使得数据报文成功到达目的节点。如果检测到通过CN转发数据报文可以到达目的节点，那么本节点执行前述CFP的3个过程;如果检测得到通过CN转发数据报文无法到达目的节点，那么无论本节点是否执行CFP的3个过程的第一个过程，即无论自己是否是候选节点，它都立刻对自己进行后续路径检测，如果本节点依照CFP的后2步的检测，得出自己可以连通到目的节点，那么本节点参与竞争发送CTS。综上所述，整个CFP的执行过程如下:首先检测CN是否是合格的候选节点，如果是，那么按照确认候选节点—后续路径检测—竞争发送CTS这3个步骤顺序执行;如果CN不是合格的候选节点，那么按照后续路径检测—竞争发送CTS这2个步骤实现下一跳中继节点的选取。

2.3 采用CFP的机会路由数据成功传输率的分析

首先考虑单次报文传输成功接收概率密度是发射机距离的函数，此函数可通过(1)式计算得到［7-8，13］

(1)式中:ψ为SNR;ptx与pnoise为发射机功率和噪声功率;α为路径损耗指数;σ为接收信号强度概率分布的标准方差。假设网络中的节点服从均匀分布且最大传输半径为R，那么如图3所示，对于单跳传输而言，由文献［8］可得传输区域中能够成功接收点S发送的数据报文的概率为

(2)式中:A(x)为阴影面积;A(0)为近似的有效传输区域;IN(x)是一个基本表达式的符号，详细意义参考文献［7-8］。

图3描述了移动自组织网络的传递过程和子分区示意图。图3b中，A(0)分成N个子区域，其中ri－1和ri分别是第i个子区域的内外圆半径。

图3 移动自组织网络的传递过程和子分区示意图Fig.3 Transmission progress in MANET and subdividing into sub-sectors

由文献［8］可得，当N趋向于无穷大时，I∞(x)计算如下

假设S为网络面积大小，网络中节点数目为Nd，那么对于发送节点而言，有效传输区域中至少有一个节点能够执行下一跳的概率为

(4)式中，pr为传输区域中能够成功接收点S发送的数据报文的概率。

根据文献［14］，我们可设每次传输距离目的节点的平均前进距离为rpg，平均每个业务数据报文需要途经的距离为d，那么平均跳数为

(5)式中，int(x)是x的取整运算。那么轻业务负载下GeRaF的成功传输概率为

其因为没有后续中继节点而导致的失败概率为

若网络是连通的，那么因为没有后续中继节点而导致的失败传输可以被挽救回来，因此其成功传输的概率大约为

由此可见，使用CFP的机会路由能有效减小数据报文传输失败的概率，由此可提高系统的成功传输率和吞吐率，这点将在后面的仿真结果中被证明。

3 仿真结果

我们选择GeRaF作为机会路由协议，因为它是现在机会路由协议中最完善的一个协议。仿真使用OPNET仿真平台，且网络中所有节点均可产生业务，转发业务和接收业务，仿真参数如表1所示。

表1 仿真参数Tab.1 Simulation parameters

仿真时主要考虑3个性能:数据报文成功传输概率(ratio)，实际吞吐率(goodput)和时延(delay)。数据报文成功传输概率是指网络中所有节点成功接收到的数据报文数目和产生数据报文总数目的比值;实际吞吐率是指整个网络平均每秒接收到的比特数;时延是数据报文的端到端平均时延。

图4所示为数据报文成功传输率的仿真结果。从图4中可以看出，CFP在成功传输率性能上明显优于贪婪转发策略。尤其是在节点密度较低的网络中，此优势更加明显，在网络尺寸一定而网络节点数目只有30时，CFP可以提升大概20%的成功传输率性能。原因是，当网络节点密度较小时，出现没有后续中继节点的可能性更大，因为上述pr值更低。当全网节点均可移动时，网络的数据成功传输率仅比静态的网络略低，其原因是，CFP针对节点的移动性专门做了一次后续检测，即前述CFP的第一步。通过这样的一步检测，能够针对上一跳节点在发送数据前后位置的变化，在选择下一跳中继节点时做出不同的选择，避免了数据报文因节点移动性造成的丢失。因此该转发策略非常适用于节点可移动的网络。

图4 数据报文成功传输概率仿真结果对比示意图Fig.4 Performance of successful delivery ratio

图5所示为实际吞吐率的仿真结果，由于数据报文成功传输率增大，相应地，实际接收到的比特数也增大。

图5 实际吞吐率仿真结果对比示意图Fig.5 Performance of goodput

图6所示为时延仿真结果对比示意图。使用贪婪转发策略的机会路由总是搜索距离目的节点最近的点进行中继，而CFP不是这样的贪婪策略，因此一个数据报文实际传送的距离可能会大于贪婪转发策略，平均跳数也可能大于贪婪转发策略。因此，时延稍微高一点是可以理解的。从上述结果可以看出，对比贪婪转发策略，虽然CFP在时延性能上稍有牺牲，然而在数据报文成功传输率和实际吞吐率性能上，CFP优于贪婪转发策略。

图6 时延仿真结果对比示意图Fig.6 Performance of delay

4 结束语

本文中我们针对在移动Ad Hoc网络中使用机会路由协议时，采用贪婪转发策略会引起“没有后续转发节点”这一现象，提出了一种新的应用于移动Ad Hoc网络的机会路由转发策略—考虑后续路径的转发策略(CFP)。其主要思想是在每跳之后进行中继节点选取时，不仅考虑各个候选节点本身距离目的节点的距离，还要考虑经过此节点的转发，当前数据报文能否成功到达目的节点。仿真结果表明，对比于采用贪婪转发策略选取中继节点的机会路由协议GeRaF，CFP在少量增加数据传输平均时延的情况下，能够有效地消除无后续转发节点的现象，提高了数据传送成功率和网络吞吐率，提高了可靠性。

［1］JOHNSON David B，MALTZ David A，BROCH Josh.DSR:The dynamic source routing protocol for multihop wireless ad hoc networks［C］//ACM/IEEE.Ad Hoc Networking.USA:Addison Wesley Longman Publishing Co，2001:139-172.

［2］PERKINS C E，ROYER E M.Ad hoc on-demand distance vector routing［C］//IEEE WORKSHOP.Proc of the 2nd IEEE Workshop on Mobile Computing Systems and Applications.USA:IEEE Computer Society，1999:90.

［3］SONG Li-bo，KOTZ David F.Evaluating Opportunistic Routing Protocols with Large Realistic Contact Traces ［C］//ACM，SIGCOM.Proceedings of the second ACM workshop on Challenged networks.USA:ACM，2007:35-42.

［4］COUTO D S J De，AGUAYO D，BICKET J，et al.A high throughput path metric for multi-hop wireless routing［J］.Wireless Networks，2003，11(4):419-434.

［5］BISWAS S，MORRIS R.Opportunistic Routing in Multihop Wireless Networks［J］.ACM SIGCOMM Computer Communication Review，2004，34(1):69-74.

［6］邵凯，张红卫，梁燕，等.无线传感网络中的数据融合问题［J］.重庆邮电大学学报(自然科学版)，2006，18(1):53-59.

［7］ZORZI M，RAO R R.Geographic Random Forwarding(GeRaF)for Ad Hoc and Sensor Networks:Multihop Performance ［J］.IEEE Trans:Mobile Computing，2003，2(4):337-348.

［8］ZORZI M，RAO R R.Geographic random forwarding(GeR-aF)for ad hoc and sensor networks:energy and latency performance ［J］.Mobile Computing，2003，2(4):349-365.

［9］JUANG P，OKI H，WANG Y，et al.Rubenstein.Energy-EfficientComputing for Wildlife Tracking:Design Tradeoffs and Early Experiences with ZebraNet［J］.ACM SIGPLAN Notices，2002，37(10):96-107.

［10］BISWAS S，MORRIS R.ExOR:Opportunistic routing in multi-hop wireless networks［J］.ACM SIGCOMM Computer Communication Review，2005，35(4):133-144.

［11］KARP B.Geographic routing for wireless networks［D］.USA:Harvard University，2000.

［12］ROZNER Eric，SESHADRI Jayesh，MEHTA Yogita，et al.Simple Opportunistic Routing Protocol for Wireless Mesh Networks［C］//WiMesh 2006.USA:2nd IEEE Workshop，2006:48-54.

［13］LUK Chun Pong，LAU Wing Cheong，YUE On Ching.An Analysis of Opportunistic Routing in Wireles Mesh Network［C］//IEEE explore.ICC 2008 proceedings.China:IEEE International Conference ，2008:2877-2883.

［14］ZHONG Zi-fei，NELAKUDITI Srihari.On the Efficacy of Opportunistic Routing［C］//IEEE WORKSHOP.Secom’07.San Diego:4th Annual IEEE Com-munications Society Conference，2007:441-450.