多跳

ISSN1000-9825,CODENRUXUEWE-mail:jos@

JournalofSoftware,Vol.21,No.10,October2010,pp.2542−2553

doi:10.3724/SP.J.1001.2010.03740Tel/Fax:+86-10-62562563

©byInstituteofSoftware,htsrerved.

无线多跳网络中的机会路由

∗

田克1,2,张宝贤2,3,马建4,姚郑2+

1(北京邮电大学网络与交换国家重点实验室,北京100876)

2(中国科学院研究生院泛在与传感网研究中心,北京100049)

3(中国科学院微电子研究所物联网研究中心,北京100029)

4(诺基亚中国研究中心,北京100176)

OpportunisticRoutingProtocolsforWirelessMultihopNetworks

TIANKe1,2,ZHANGBao-Xian2,3,MAJian4,YAOZheng2+

1(StateKeyLaboratoryofNetworking&SwitchingTechnology,BeijingUniversityofPostsandTelecommunications,Beijing100876,

China)

2(RearchCenterofUbiquitousSensorNetworks,GraduateUniversity,TheChineAcademyofSciences,Beijing100049,China)

3(RearchCenterofInternetofThings,InstituteofMicroelectronice,TheChineAcademyofSciences,Beijing100029,China)

4(NokiaRearchCenter,Beijing100176,China)

+Correspondingauthor:E-mail:yaozheng@,

TianK,ZhangBX,MaJ,lof

Software,2010,21(10):2542−:///1000-9825/

Abstract:Opportunisticroutingcanlargelyimprovetheperformanceofwirelessmultihopnetworksbytaking

paper,thebasicideabehindopportunisticrouting

isintroduced,andthenthepaperlookstoclassifyexistingworkinthisareabadondifferentcriteria.A

cperintroduces,indetails,how

eachoftheprotocolswork,y,thispaper

concludeswithsomeissuesthatstillneedtoberesolvedinthisareainhopesofstimulatingfuturerearchonthis

topic.

Keywords:opportunisticrouting;reliabilitytransmission;networkcoding;wirelessmultihopnetworks

摘要:机会路由通过充分利用无线信道的广播特性,可以大大提高无线多跳网络的性能.从阐述机会路由的基

本思想开始,介绍了机会路由协议的主要特点、适用环境和影响机会路由性能的重要因素.在此基础上,对重要机会

路由协议进行了综述,讨论不同协议的工作机制及其优缺点.最后,探讨了机会路由的一些未来发展方向,以期为这

一领域的发展提供一些有意义的借鉴.

关键词:机会路由;可靠传输;网络编码;无线多跳网络

∗SupportedbytheNationalNaturalScienceFoundationofChinaunderGrantNo.60970137(国家自然科学基金);theNationalKey

SpecialProgramofChinaunderGrantNos.2009ZX03006-001-02,2009ZX03006-006(国家重大专项);theKnowledgeInnovation

2-YW-120(中国科学院知识创新工程项目)

Received2009-05-12;Accepted2009-09-03

田克等:无线多跳网络中的机会路由

2543

中图法分类号:TP391文献标识码:A

1引言

在无线自组织网络、无线mesh网络和无线传感器网络(统称“无线多跳网络”)中,各节点既可以作为数据的

终端节点,也可以是网络的路由节点.无线链路动态、时变和丢失特性,导致无线链路质量较差且稳定性较低,这

对提高无线多跳网络的吞吐量和传输可靠性提出了挑战.另外,节点移动性带来的链路不稳定、节点能量的有

限性也给路由协议的设计及优化带来困难.然而,无线信道的广播特性是其先天的优势,机会路由(opportunistic

routing)正是利用了无线信道的这一特性来提高无线网络的传输可靠性和端到端的吞吐率.

需要说明的是,间歇性连接(intermittentlyconnected)移动AdHoc网络和容迟网络(delaytolerantnetwork,简

称DTN)中的路由选择(有些工作中,也将这类网络中的路由协议称作机会路由协议)[1]也是当前的热点问题之

一.这类网络中,节点之间的连通性是间歇性的,因而传统路由机制不再适用.这类网络常常利用节点的移动来

携带信息、创造新的通信机会,最终期望以较高的成功概率实现端到端通信.通常,这类网络中分组投递延迟很

大(如几分钟乃至几小时).本文研究面向任意时刻总是连通的无线多跳网络,所针对的应用延迟要求较小(如几

百毫秒到1~2秒),所研究的机会路由协议主要考虑如何利用无线链路的广播特性和终端的空间多样性来提高

无线网络吞吐量和传输可靠性.除非特殊声明,下面的讨论中将不再涉及这类间歇性连通的无线网络.

1.1机会路由基本思想及其优势

传统无线自组织网络和传感器网络的路由协议都采用确定性路由方式(如AODV(adhocon-demand

distancevectorrouting)[2],directeddiffusion[3]),即:在端到端的数据传输过程中,首先建立一条端到端的节点序列,

然后在每次分组转发时,首先确定一个下一跳节点,再执行链路层转发.如果传输过程中发生分组丢失或差错,

则启动链路层重传.在链路质量和稳定性较差的环境下,频繁的链路层数据重传将消耗大量的带宽资源.因此,

尽管确定性路由方式逻辑简单,但未能充分考虑无线信道的广播特性、时变特性和干扰不规则性.无线信道的

广播特性使得一次分组转发可能被多个节点收到,且接收概率各不相同;无线链路的时变特性导致网络中链路

的状态随时间而改变.路由协议设计过程中如果缺乏对信道广播和丢失特性的充分考虑,必将导致大量网络资

源无谓浪费,这将严重影响无线多跳网络的吞吐量和提供服务质量的能力.

针对无线信道的广播、时变、丢失特性和确定性路由策略的不足,麻省理工学院(MIT)的Biswas等人于

2004年率先提出了机会路由(也称作机会转发)的概念[4,5].机会路由通过多个潜在中继节点竞争、自主智能判断

进行下一跳节点选择,充分利用信道广播特性,提高吞吐量和传输可靠性.研究机会路由算法来提升无线多跳网

络的性能,已成为当前无线自组织网络与传感器网络组网协议研究中的一个重要方向.

1.2两个例子

利用无线媒介的广播特性,机会路由主要从两个方面来提高无线多跳网络的吞吐量:一是增加单跳传输的

可靠性;二是减少端到端传输跳数.下面分别从这两个方面解释说明机会路由的原理.

机会转发可以选择多个中间节点作为转发中继节点.每次数据发送后,都有更多的被接收和再次转发的机

会.如图1所示(链路上的值代表该链路分组成功投递率),假设从源节点Src到每个中间节点的转发成功率为

30%,从每个中间节点到目的节点Dst的转发成功率是100%.使用传统确定性路由方法,源节点将从4个中间节

点中选择一个节点作为下一跳节点.此时,从源节点到目的节点的转发成功率只有30%,即源节点平均发送3.3

次,目的节点才能成功收到1次.如果使用机会路由的方式,建立一个转发节点集(forwardercandidatet),把4个

中继节点同时作为备选转发节点,只要其中一个收到源节点发来的数据包就可以继续向目的节点转发,转发率

可以提高到(1−(1−0.3)4)×100%≈76%,转发率从30%上升到了76%,从而显著提高了端到端的吞吐量.

机会路由协议也可以减少端到端转发跳数、降低延迟、提高吞吐量.如图2所示,5个中间节点在源节点和

目的节点之间沿直线分布,图中长度相同的链路具有相同的分组投递率.传统路由协议事先确定源到目的节点

2544

JournalofSoftware软件学报Vol.21,No.10,October2010

所要经过的中间节点,例如Src-B-D-Dst.当源节点向下一跳节点B发送数据时,B收到了数据包,但同时C也收到

了同样的数据包.机会路由策略允许C向下游转发,而不是由B来承担此任务,这样就可能形成Src-C-Dst路径,

相比Src-B-D-Dst路径减少了跳数.另一种情况是,源在给B发送数据时,B没有收到,但A收到了,传统路由协议

中,源节点必须重发这个数据包,而机会路由允许A来发送这个数据包.这种策略会使得数据更快地向目的端方

向传输,从而增加了端到端的数据吞吐量,同时也提供了可靠传输.

Fig.1EachintermediatenodehasindependentprobabilitytorelaypacketsfromsourceSrctodestinationDst

图1每个中间转发节点有独立的机会为源节点转发数据

Fig.2OpportunisticroutingenablessourceSrctotransmitdatatodestinationDstviapathswithdifferenthops

图2机会路由使分组可能经过不同跳数的路径到达目的节点

2影响机会路由性能的主要因素

机会路由的主要问题包括如何选择备选转发节点、如何为各备选节点分配转发优先级以及如何避免或抑

制数据重复发送.下面将对这些问题分别加以阐述.

2.1备选转发节点选择

如何选择备选转发节点集是影响路由协议性能的关键因素,选择合适的转发节点集很大程度上决定着是

否可以获得较高的协议性能提升.在现有机会路由协议中,存在多种路由测度(metrics)可以用来选择备选转发

节点集,其中主要包括跳数(例如SOAR[6],OPRAH[7])、ETX(expectedtransmissioncount)[8](例如ExOR[4,5],

MORE[9]等)、地理距离(例如GeRaF[10,11],HARBINGER[12])等.基于不同测度的代价计算方法包括端到端最短路

方式、迭代方式.端到端最短路方式是在数据包发送之前计算出每个备选转发节点到目的端最短路径的ETX

值、跳数或地理距离,以此来确定不同备选转发节点的优先级,这种方式实现比较简单.同时,结合节点出行链路

质量、各备选转发节点自身状态(如缓存队列占用情况)等其他因素,对端到端方法作进一步优化,也是一种常见

方法.但由于数据的转发是机会的而不是按照固定最短路转发的,所以端到端最短路方式难以保证所选的备选

转发节点集是最优的.端到端迭代法首先通过对每个转发节点到目的节点使用同样的机会转发策略执行端到

端的逐跳迭代运算,然后得出每个邻居节点到目的节点的平均代价,这一代价与实际的转发过程较为接近.但

是,这一方法常常涉及较多的网络知识和运算量.

无论采用何种测度,都需要一种机制来得到邻居节点的状态.这些状态可以是邻接链路状态,也可以是邻居

节点到目的节点的距离.比如,ExOR协议是基于ETX工作的,它需要以ETX的全网链路状态信息为基础,这将

给网络带来一些额外开销.GeRaF协议以地理距离为测度,数据包发送节点只需知道邻居节点和目的节点的位

置,就可以用每个邻居到目的节点的距离作为测度来选择转发节点集,并确定每个备选转发节点的优先级.

A

B

D

C

DstSrc

100%

100%

100%

100%

30%

30%

30%

30%

A

B

D

C

Dst

Src

50%

90%

70%

E

田克等:无线多跳网络中的机会路由

2545

此外,备选转发集中节点的数量也是影响转发效率的一个重要因素.较多的备选转发节点可以提高机会转

发的成功率,减少重传的概率.但另一方面,较多的备选转发节点也会给转发节点之间的协调带来困难,增加了

控制开销.另外,剔除质量较差的备选节点也能够有效地提高机会转发的性能.

2.2备选转发节点协调机制

在选择了备选转发节点并为各节点确定优先级之后,需要一种机制使得各转发节点之间能够相互协调,以

有效避免或抑制不必要的重复发送.现有的机会路由协议所使用的协调机制可以分为控制包应答模式、数据包

应答模式和无协调模式.

控制包应答方式存在两种具体实现方式,包括基于RTS-CTS(requesttond-cleartond)控制分组或ACK

分组,备选转发节点按照当前发送节点事先设定好的优先级按次序应答.在使用RTS-CTS的机会协议中,在数据

包发送之前首先发送RTS,该RTS中包含各备选转发节点地址;备选转发节点按优先级依次回送CTS;一旦数据

包发送节点收到第1个CTS后,它就会选择这个发送CTS的节点作为转发节点,同时为数据包的转发预约了无

线信道;其他备选转发节点听到数据发送后停止发送CTS.此种方案很大程度上避免了各备选转发节点由于相

互听不到而可能发生的重传现象,但需要在MAC(mediaaccesscontrol)层作一定改动,对协议实现复杂度有所增

加.另外,在信道预约以后,并不能确保数据包成功传输,这可能为数据包转发率带来了一些负面的影响.

另一种

控制包应答方式是ACK应答,数据包发送节点发出数据后,每个备选转发节点按照预先设定的优先级顺序回送

ACK,当较低优先级的备选转发节点听到较高优先级的节点发出的ACK时,就获知该高优先级节点已经收到此

数据包,随即将已收到的数据包丢弃.发送节点在一段时间内收不到ACK,则重发数据包.此应答模式用少量的

ACK开销换来的转发的可靠性,很大程度上提高了端到端的转发率.为了抑制重复发送,基于ACK的应答模式

需要各备选转发节点之间具有相互的直接相邻性.

数据包应答方案省去了数据发出后的各种MAC层控制分组应答过程,备选转发节点收到数据包后按优先

级顺序转发数据,优先级较高的备选转发节点先于优先级较低的转发节点发送数据包,低优先级备选转发节点

听到后丢弃存于本地的相应数据包.此方案由于没有控制包的应答过程,降低了控制开销,但同时也增加了数据

包重传和碰撞的机率,因此,对于链路状态较好的网络环境中更适用.

在无应答模式中,转发节点之间没有任何直接的协调动作.各备选转发节点收到数据后,可以根据自身转发

所带来的增益、编码机会、从本节点到目的节点的剩余路径长度等因素,以一定概率或一定条件下的分组转发,

目的节点收到数据包后,可以选择向信源发送ACK,也可以不作任何确认.这种模式中,分组通常以广播方式发

送,无控制开销.但是,如果备选转发节点集选择不当或中间节点转发概率确定不当,那么这种方案常常会导致

目的节点收到较多的重复分组.

3主要机会路由协议

下面将分别介绍采用不同策略进行机会路由的主要协议.其中着重介绍各协议的主要工作机制,并讨论它

们的优缺点.

3.1基于端到端最短路径

这类机会路由协议需要无线网络在后台运行一个全网范围的路由协议,提供节点间基于不同度量的最短

路径,在此基础上实现高效机会路由.下面将对典型协议一一加以介绍.

ExOR(extremelyopportunisticrouting):ExOR是最早的机会路由方案,这是一个以端到端的最短路的ETX

值为基准的机会路由算法.网络中每个节点周期性地发送探测包,从而得到相邻链路的ETX值,通过全网广播,

网络中的每个节点都能够获得全网链路状态.在节点欲发送数据时,采用逆向Dijkstra最短路径算法计算各邻

居节点到目的节点的最小期望转发总次数.ExOR的基本思想是,源节点欲向目的节点发送数据,它首先选择到

目的节点的最短ETX路径小于自身的节点作为备选转发节点,这些节点组成备选转发节点集,并依据其到目的

节点的距离设置优先级,距离目的节点越近,优先级越高.在数据包中携带了各备选转发节点ID,并以优先级顺

2546

JournalofSoftware软件学报Vol.21,No.10,October2010

序排列.源节点成批地广播数据包,收到包的邻居节点按优先级的次序转发数据,优先级高的节点转发过的数

据,若被优先级低的备选转发节点听到后,该低优先级节点将不再转发这些数据包,而是发送本地存储且较高优

先级节点尚未成功发送的数据包.每个备选转发节点按此方式转发,直到目的节点接到大部分(如90%)数据包

为止,其余数据包按照传统的最短路由方式转发.

ExOR所采用的简单方法能够在很大程度上提高数据包转发率,但也存在着一些不足:首先,由于ExOR以

全网链路状态为基础,因此网络中每个节点需要定期地全网广播自己邻接链路的ETX值.这给网络带来了较大

的负担,因此可扩展性不强;其次,由于缺乏各备选转发节点之间的有效相互确认和协调机制,因此,目的节点收

到重复分组的概率较高.

SOAR(simpleopportunisticadaptiverouting):在Rozner等人提出的SOAR协议中,首先建立一条端到端的最

短路径,数据发送节点在选择备选转发节点时,以偏离这条路经的跳数来选择邻居作为转发节点,并确定其优先

级;为了抑制重复分组,各备选转发节点相互之间的链路ETX值必须高于一个给定门限,以使得任何一个节点发

出的数据包或ACK包都能以高概率被其他备选转发节点收到.这样做的好处是:可以把备选转发节点集中在端

到端最短路径的附近,有效避免了数据的分叉传输,

减少了数据重传,且有利于执行机会转发节点之间的协调过

程.由于SOAR限制了备选转发节点的选择,要求各备选转发节点位于相互间的通信范围内,因此高概率保证高

优先级转发节点发送的数据包不会被低优先级转发节点再次转发.SOAR在追求重传最小化的同时,也在一定

程度上限制了转发的效率.

CBF(cluster-badforwarding)[13]:CBF是一种基于分簇的机会转发方法.CBF引入了两种帮助节点:

intermediatehelper和distancehelper.一个数据发送节点(记当前节点)以最短路径路由的方式选择其下一跳转

发节点的邻居节点作为本次转发的帮助节点.其中,距离目的节点比下一跳节点远且又比当前节点距离目的节

点近的邻居为intermediatehelper,而距离目的节点比下一跳节点近的邻居节点为distancehelper.数据包从当前

节点发出后,如果distancehelper收到,则无论其他节点收到与否,它都将转发此数据包;如果intermediatehelper

收到数据包且没有听到下一跳节点的确认消息,则intermediatehelper转发此数据包给此下一跳节点,当前节点

则不再转发此数据包.在数据包转发过程中,distancehelper的转发可以增加向下游转发的成功率,intermediate

helper代替当前节点执行重传可以提高重传成功率.因此,在链路质量较差的情况下,CBF充分利用了数据包成

功传输的机会来减少数据包重传次数,提高了传输成功率,从而提高了单跳链路的转发率.从端到端数据转发的

角度来看,减少了端到端的转发次数,也减少了链路不稳定带来的重传消耗.

ROMER(resilientopportunisticmeshrouting)[14]:为了提高严重丢失情况下的无线网络的分组转发健壮性和

可靠性,ROMER以每分组为单位在线构建连接源端到目的端的转发网状结构.ROMER要求每个分组都必须携

带一个表征该分组已经偏离最短路的距离.如果偏离距离小于一个给定门限,收到分组的中间节点将继续转发

该分组.上述转发方式将自动生成一个围绕连接源端到目的端最短路径的椭圆型转发结构,这一结构可以提供

足够数量的交织路径以支持机会路由,克服无线链路瞬时波动.同时,为了降低重复分组的数量,对于一个节点

来说,如果它不是连接源端到目的端最短路径上的节点,那么它可以根据出行链路的瞬时吞吐量来调整其分组

转发概率.

DTRP(directedtransmissionroutingprotocol)[15]:DTRP的工作机理与ROMER类似.所不同的是,DTRP以不

同的方式来调节中间节点的分组转发概率.具体地,连接源端到目的端最短路径上的节点以概率1转发数据分

组;不在最短路径上的节点的转发概率与偏离最短路的路径长度有关:偏离越大,概率越低.ROMER和DTRP的

优势在于其简单性和高可靠性,能够有效对抗无线信道质量波动.缺点是代价大、重复分组数量大.

3.2基于端到端迭代策略

以最短距离来确定各备选节点优先级,这一方法实现起来较为简单,在很多机会路由协议中得到了运用.但

是,这种最短距离法并没有考虑到每个转发节点自身将继续执行机会转发这一事实——而不是沿最短路下行

发送.因此,如果备选转发节点选择欠佳,有可能导致分组被转发到质量较差的路径上去.基于上述考虑,迭代法

把端到端的转发分成两个阶段:第1阶段是从当前节点(包括源节点)发出数据包到至少一个备选下一跳节点收

田克等:无线多跳网络中的机会路由

2547

到此数据包;第2阶段是从该备选节点发出数据包到目的节点收到数据包(如图3所示).在迭代计算过程中,需要

结合每一个备选转发节点的分组接收率、每个备选转发节点的下一跳备选转发节点集及其出行链路质量等因

素,通过迭代方式计算端到端多路径加权平均代价.与纯粹的基于最短路径的方法相比,迭代法更能客观地反映

出一个机会路由协议的分组转发状况,从而更合理地优化转发节点集及各被备选转发节点的优先级.

Fig.3Illustrationofiterativelectionofcandidateforwardert

图3迭代方式选择备选转发节点集示意图

LCOR(least-costopportunisticrouting)[16]:这是最早的基于迭代法的机会路由协议.迭代法的引入主要是因

为在机会转发执行过程中,任何一个备选转发节点,当它作为实际的转发节点时,都会同样以机会转发的方式继

续向目的端方向转发数据.因此,仅使用最短路径的相关测度作为衡量备选转发节点优先级不能正确地反映备

选转发节点的优劣.在LCOR中,对于一个转发节点i来说,它将穷举所有的邻居组合形式,从中选择最好的一个.

对于每一种组合,可以用迭代的方式计算出从节点i通过该子集中的节点到目的节点的端到端代价,以此来确

定各备选转发节点的优先级.以迭代法来确定转发节点集的方式,相对于早期机会路由单纯地以最短路径ETX

为测度的方式具有明显的优势.但当节点平均度数较高时,LCOR会出现过量迭代、计算量过大的问题,协议可

扩展性较差.

OAPF(opportunisticany-pathforwarding)[17,18]:OAPF也是通过计算端到端代价来选择备选转发节点集的,

OAPF的提出者给出了一种新的测度——EAX(expectedany-pathtransmissions).EAX是从数据发送端到目的端

所有可能经过路径的ETX期望值的加权平均.与早期迭代方案不同,OAPF没有事先确定备选转发节点的个数,

而是在迭代计算的过程中逐渐增加备选节点的个数,直到加入新的备选节点后计算所得EAX值的提升小于一

个门限值为止.这种机制有效地限制了备选转发节点集的规模,也控制了转发协调过程中带来的额外开销.但这

种迭代方法同样不可避免地引入了较高的计算量和大量网络状态信息的采集和传播.

BitSOR(bit-ratelectionforopportunisticrouting)[19]:早期机会路由只考虑丢失率而没有考虑链路带宽,这

将产生带宽利用不充分的问题.针对这一问题,BitSOR采用了新的测度ExACT(expectedanypathcommunication

time).ExACT表示数据包从当前节点传输到目的节点所需的时间.ExACT使用反向迭代方式,先从目的节点开

始计算,直到计算出数据发送节点到目的节点的端到端ExACT值,并根据ExACT值来安排备选转发节点的转

发优先级.BitSOR以端到端时延作为优化目标,明显提高了数据在网络中的移动速率,充分利用了网络带宽,有

效地避开了网络瓶颈.

3.3基于地理位置策略

基于拓扑的机会路由协议在动态网络中会导致较高的协议开销,从而带来可扩展性问题.地理位置、地理

距离可以为备选转发节点集的选择和优先级设定带来便利,这方面的研究已经引起了关注.

GeRaF(geographicrandomforwarding):按照GeRaF,各节点可以自主休眠与苏醒,并且节点有能力获知自身

和sink节点(无线传感器网络中的数据汇集节点)的地理位置信息.GeRaF根据地理位置确定转发节点及其优先

级.数据包发送之前,发送节点首先发送RTS,其中携带发送节点和sink节点的位置信息.发送完RTS之后,发送

节点等待潜在的CTS.收到RTS的节点,如果自身距离目的节点比发送节点到目的节点要近,那么它是一个CTS

Src

Thefirststage

Thecondstage

Candidatet

Dst

2548

JournalofSoftware软件学报Vol.21,No.10,October2010

的潜在发送者,并且根据自己到目的节点的距离确定自己发送CTS的优先级.距离目的节点越近,优先级越高.

如果发送节点没有收到CTS或发生CTS碰撞,将重新执行MAC层握手.

以地理距离来确定备选转发节点及其优先级的方法省去了维护全网拓扑和路由表所带来的协议开销,但

是,节点之间的地理距离并不能完全体现其间的路径质量,更不能正确反映转发率的高低.节点密度等其他因素

也会对链路质量产生影响.另外,提供节点定位机制也给系统带来了额外的开销或成本.

HARBINGER(hybridARQ-badinterclustergeographicrelaying):HARBINGER是HARQ(hybrid-ARQ)和

GeRaF的结合.在GeRaF中,如果数据发送节点前方没有处于活动状态的节点,发送节点将会周期性地发出RTS,

以试图找到发送的机会,由此带来的开销和延迟都比较大.HAEBINGER没有采用GeRaF中的RTS-CTS机制,

相反地引入了HARQ技术,使得在链路状态不好的情况下减少了单跳重传带来的开销,加大了单跳传输距离,适

合在低密度网络中运行,可以提高网络的能量有效性,延长网络生存期.

MGOR(multi-rategeographicopportunisticrouting)[20,21]:MGOR是一种面向多速率无线网络、基于地理位

置的机会路由方案.MGOR的方案设计和分析基于这样一种考虑:每个节点可以工作在不同速率上,不同工作速

率将导致不同的传输范围,从而导致备选转发节点集、优先级及相互间协调关系的变化.针对这一问题,MGOR

设计了一种新的测度EOT(expectedone-hopthroughput),通过对EOT的选择来达到备选转发集和传输速率的平

衡优化.MGOR将多速率的思想应用到基于地理位置的机会路由方案中,可控地选择节点传输速率以达到提高

端到端吞吐量的目的.

3.4基于网络编码策略

网络编码可以在一次传输内携带多个报文来有效地提升网络吞吐量,将这些技术与机会路由技术结合可

以有效地提高性能.但如何设计基于编码的机会路由协议需要考虑网络的拓扑、网络动态性和重传开销等多种

因素,使两项技术相互协调,都能体现出各自的优势.MORE,CORE,PACE等协议中都巧妙地将上述两种技术进

行了有机结合,下面将一一加以介绍.

MORE(MAC-independentopportunisticroutingandencodingprotocol):MORE是ExOR的增强版.具体来说,

MORE把流内随机网络编码(intra-flowrandomnetworkcoding)引入了机会路由,并利用网络编码来降低重复分

组发生的概率.如图4所示,源节点发出a,b两个数据包,备选转发节点A收到了全部的两个数据包,另一个备选

转发节点B只接收了其中的一个数据包b.由于B距离目的节点更近,具有比A更高的优先级,所以节点B先转

发分组b到目的节点.但此次发送并没有被节点A听到

,因此,节点A将发送两个数据包.在这个过程中,数据包b

被两个备选节点重复发送.为避免重复发送,MORE引入网络编码的方法.在上面的例子中,节点A在收到两个数

据包a,b后,对其做线形编码为a⊕b,并发送编码后的分组.目的节点收到数据包a⊕b后,做线性运算a⊕b⊕b=a,

目的节点可以得到全部两个数据包.

Fig.4IllustrationofpotentialduplicatetransmissionsinExOR

图4ExOR中存在的潜在重复分组发送现象示意图

MORE具体的工作流程如下:当源节点欲发送数据时,将所要发送的原始数据分成批(batch),例如,把每K个

包作为一批.源节点将每一批数据包做随机线性编码后,不停地广播出去,每个分组携带其编码向量.中间转发

节点只接受Innovative包,即:收到一个包后,首先判断它与本地已经收到的属于该批的数据包是否线性独立,如

果线性独立,则将新数据包存入缓存,否则,丢弃该包

.每个中间节点采用基于Credit的方式转发数据,即:每收到

一个Innovative包,本节点credit加一个x值,0

Src

Dst

b

b

B

Ab

ba

a

田克等:无线多跳网络中的机会路由

2549

发,转发完一个数据包后Credit减1.当收到属于同一批次的K个innovative数据包后,目的节点就可以恢复出原

始K个数据包,并向源节点回送ACK包.源节点收到ACK后,进行下一批数据包的发送.实验结果显示,与ExOR

相比,MORE可以极大地提高分组成功投递率.

CORE(coding-awareopportunisticroutingmechanism)[22]:针对已有的基于局部信息网络编码(localized

networkcoding)方案只是被动地利用各节点现有的编码机会的不足,我们提出了CORE协议,以在无线网络中

创造更多的编码机会,提高网络吞吐量.针对这一目标,CORE将局部流间网络编码(localizedinter-flownetwork

coding)和机会路由相结合.具体来说,在确定备选转发节点优先级时,编码机会越大的节点优先级越高,从而使

得分组总是尽量转发到编码机会多的节点上去.通过创造更多的编码机会,CORE大大提高了多流无线网络的

吞吐率.在CORE协议执行过程中,需要节点保持两跳邻居缓存队列内的分组信息.

PACE(probabilisticarea-centricnetworkcodingmechanism)[23]:在CORE中,每个节点仅考虑单个分组转发

带来的增益.然而在一定地域区域内,各节点采用不同的转发次序,可能导致不同的联合编码增益.这是因为,编

码增益依赖于各节点当前存有哪些分组.针对这一问题,我们提出的基于区域的网络编码机制PACE,也是一种

网络编码和机会路由的有效结合.在PACE中,节点每次传输都着眼于提升节点附近区域中多个节点的联合编

码增益,同时使用编码感知的MAC层传输调度来保证编码机会的实现.PACE要求网络中每个节点保持两跳邻

居信息.PACE的不足之处在于,单个分组编码增益的计算量较大.

3.5其他协议

MCExOR(multi-channelextremelyopportunisticrouting)[24]:考虑多信道问题,MCExOR给每个节点都分配

一个主信道,一个备选节点集中的所有节点都将使用相同的主信道.转发节点在数据包传送过程中尽量减少同

一个信道的重复使用,每次转发数据时尽量切换到与上一跳不同的信道上去.在选择备选转发节点集时,

MCExOR考虑了多跳路径状况,使用迭代的方式计算路径代价来决定备选节点的优先级.MCExOR有效地利用

了无线多信道的优势,在数据传输过程中减少了碰撞.

OPRAH(opportunisticroutingindynamicadhocnetworks):OPRAH是一种按需多路径构造协议.OPRAH采

用了类似经典路由协议AODV的RouteRequest和RouteReply机制,但在寻径过程中,允许中间节点通过收到

的多个路由请求报文和从目的节点可能收到的多个路由应答报文建立缠绕式多路径.数据包将按照建立的多

路径进行发送:每个转发节点收到一个数据包后,通过广播方式继续下行转发.OPRAH可能导致目的节点收到

较多的重复分组.表1总结和比较了典型无线网络机会路由协议的主要特性.

Table1Classificationandcomparisonoftypicalopportunisticroutingprotocols

表1典型机会路由协议分类与对比表

Characteristics

Protocols

Metrics

Coordination

mechanisms

Codingornot

Location

information

Global

information

ExORETXACK

××

9

SOARHopcountsACK

××

9

ROMERHopcountsNo

××

9

DTRPHopcountsNo

××

9

CBFMulti-MetricsACK

×××

LCOREAXACK

××

9

OAPFEAXACK

××

9

BitSORExACTShortpul

××

9

GeRaFDistanceRTS-CTS

×

9

×

HARBINGERDistanceACK

9

××

MGOREOTACK

×

9

×

MOREETXNo

9

×

9

CORECodingopportunitiesDATA

9

××

PACECodingopportunitiesDATA

9

××

MCExORETXACK

××

9

OPRAHHopcountsNo

×××

2550

JournalofSoftware软件学报Vol.21,No.10,October2010

4总结与展望

本文综述了已有机会路由的基本思想、主要问题和主要协议.已有工作显示,机会路由能够显著提高无线

多跳网络的性能.但作为一个无线网络领域的新技术,无线网络机会路由领域还有很多问题需要进一步研究,下

面列举几个这方面的问题.

•新型路由测度

路由测度对机会转发节点集的选择、优先级设定及路由协议的性能会有重大的影响.已有机会路由协议主

要以跳数、ETX、地理距离、编码机会等作为主要测度来设计路由协议.引入新的路由度量有可能孕育着突

破.Wu等人[25]提出了基于效益(utility)的机会路由协议.该协议以每个分组的效益作为路由度量,即:一个分组的

成功端到端发送所带来的效益等于该分组的价值减去端到端传输代价.

•跨层设计

很多已有机会路由协议主要着重MAC层和路由层的联合设计.除此之外,MAC层的前向纠错机制、分组

大小、发送功率、信道选择及调度也是影响机会路由性能的重要因素.综合考虑上述因素及其应用的特点进行

机会路由研究,对跨层机会路由将起到较好的促进作用.

在机会路由协议中,MAC协议的设计对于数据包发送节点与备选转发节点、备选转发节点与备选转发节

点之间的协调起着重要的作用.一个好的MAC协议可以有效地提高机会路由的转发效率,降低碰撞,减少重传.

除了前面介绍的结合RTS-CTS或ACK机制的机会转发,还有一些研究人员设计了面向机会路由的MAC层改

进机制.

在Zubow等人提出的MCExOR[24]协议中,对802.11的MAC层作了修改,相应地提出了一种紧凑式ACK

机制,减少了机会转发的分时槽ACK机制所引起的数据碰撞问题.基本思想是,优先级高的节点如果没有发送

ACK,低优先级的节点就无需空等发送一个完整ACK所用的时间,而是在一个很短的时间间隔后立即向数据发

送节点发送ACK.

Baccelli等人[26]也针对这一问题提出了适用于移动AdHoc网络的解决方案.此方案中,数据转发节点对数

据发送节点的确认信息以短信号脉冲(shortsignalingburst)的形式来实现.它由长度相同的二进制序列组成,高

电平1表示节点发送脉冲信号,低电平0表示节点处于监听状态.短脉冲序列根据优先级设定,优先级高的节点

相应的脉冲序列号较大,反之则小.如果备选节点在监听阶段听到其他节点发送的脉冲信号就放弃转发数据包.

此方案能够有效地缩短机会路由的应答过程所耗时间,但对网络中节点的时间同步性要求较高.

另外,Cui等人[27]采用了规划的方法研究了综合机会路由选择和媒质接入传输调度的节能传输问题,文中

同时利用网络编码技术来提高能量效率,但该文所采用的集中式优化方法导致所设计的算法可扩展性较差.

•节能机会路由

节能是无线网络的重要指标之一,如何在机会路由协议设计过程中考虑转发效率、节能性能和投递延迟建

立的折衷关系具有重要意义.一方面,机会路由通过降低分组重传次数,可以降低分组发送所带来的能耗;另一

方面,备选转发节点集的规模在很大程度上影响了机会路由的性能,这需要更多的节点处于苏醒状态.但与之相

矛盾的是,在能量有限的无线网络中,应鼓励尽量多的节点处于休眠状态,以降低信道侦听能耗.因此,如何在节

能与转发效率以及分组端到端投递延迟之间建立折衷关系具有重要价值.HARBINGER是适合节点比较稀疏

情况下的位置机会路由算法,它允许节点休眠,并通过HARQ延伸节点传输距离.

Zhang等人[28]分析了分簇机会路由协议的能量-延迟折衷关系的下限.但文献[28]仅面向满足如下特性的

分簇网络结构:对于相邻簇间通信,簇内不同节点可以相互替换的分簇网络.因此,其分析结果难以推广到其他

机会路由协议.Cui等人[27]研究了综合网络编码、机会路由和传输调度的节能传输问题,以有效延长网络寿命.

FSA(fastslottedacknowledgment)协议[29]研究了在硬件可靠性有一定限制的条件下,如何在能量最小化和端到

端延时最小化之间建立平衡.FSA首先把能量模型集成到不可靠的链路模型中,从而为能量有效性建立一个优

化测度,并对各类信道模型作相应的优化.分析了在逐跳选择和多跳迭代选择备选转发节点集的策略下,如何使

得能量与延时联合最小化.分析结果显示,机会转发策略可以利用空间分配的优势,有效地提高了延时约束下的

田克等:无线多跳网络中的机会路由

2551

瑞利衰落信道条件下的转发性能.如何综合考虑能量因素(如剩余能量、发射功率)、转发效率和拓扑信息来设

计高效机会路由协议值得进一步加以研究.

•基于编码的机会路由

在无线网络领域广泛应用了多种编码技术,FEC(forwardingerrorcorrection)可以改善链路丢失率;HARQ可

以增加节点的传输范围和成功率;网络编码可以在一次传输内携带多个报文以有效地提升网络吞吐量.将这些

技术与机会路由技术结合可以有效地提高性能,但如何设计基于编码的机会路由协议要考虑网络的拓扑、网络

动态性和重传开销等多种因素,使两项技术相互协调,都能体现出各自的优势.前文提到的MORE,CORE,PACE

和HARBINGER等协议中,都巧妙地结合了不同编码技术.另外,在文献[30]中,我们提出了如何通过“机会转发+

网络编码”,以协作的方式有效重传MAC层丢失掉的分组的方案.仿真结果显示,该方案在高丢失无线网络中可

以有效地提高传输可靠性.Zhang和Li[31]采用规划的方法,优化了MORE协议中单个batch传输过程中各个转

发节点的转发次数,进一步降低了重复分组投递的概率,提高了网络吞吐量.如何有机地将编码方法和机会路由

进行综合设计,仍是当前的一个热点问题.

•机会组播/广播路由

利用机会路由的特性来支持高效的组播/广播通信,称作机会组播/广播.学术界对这一领域的研究尚少.例

如,在基于网格的组播路由协议中加入机会广播机制,充分利用转发组节点的“非转发组”邻居的监听和帮助能

力以降低转发冗余度,提高转发效率.根据丢失率等知识,建立转发组内节点的转发效率表及转发先后关系,抑

制不必要的转发,降低组播开销.Guo等人提出的机会洪泛[32]以基于树的广播为基础,同时考虑到树中节点的双

亲节点有可能和它的其他邻居节点同时收到需要洪泛的数据包,从而可以利用洪泛生成树以外的链路来辅助

转发数据.另外,Li等人提出的OppCast(opportunisticbroadcast)协议[33]是针对在链路不可靠的移动无线自组织

网络中报警数据包的传输而提出来的一种高可靠性快速广播协议,该协议使用了机会路由的基本思想来最小

化报警数据包转发的每一跳的延时.

借鉴机会转发的思想,我们将目的端驱动的方法应用于基于网状转发组结构的无线多跳组播路由协议

ODMRP(on-demandmulticastroutingprotocol)[34]之上,相应地设计了D-ODMRPP(destination-drivenon-demand

multicastroutingprotocol)协议[35].D-ODMRP在选择转发节点来建立组播转发组结构的过程中,尽量机会地选

择组播组成员,而少使用非组播组成员节点来转发数据,从而减少了转发次数.在不影响分组转发率的前提下,

提高了全网转发效率.

•机会拓扑控制

Ma等人[36]提出了结合机会转发特性的拓扑控制方案,目的是减少网络的连通支撑集(S)节点,并满足给定

的上行通信端到端转发成功率.该方法主要考虑无线链路的广播特性和概率特性,一个节点可以通过多条低转

发率链路,以机会的方式接入连通支撑集S形成的骨干网络,并达到较高的接入成功率,从而实现与网关节点的

可靠信息传输.在无线传感器网络中,通过减少连通支撑集节点的数量,可以让更多的节点处于休眠状态,因此

可以有效提高网络能量有效性.但是,这一方案仅适用于上行通信为主的无线传感网应用.

综上所述,机会路由可以有效地提高无线AdHoc网络、无线Mesh网络和无线传感器网络的性能.但作为

一项无线网络新技术,机会路由在很多方面仍需深入研究.

References:

[1]ginintermittentlyconnectedmobileadhocnetworksanddelaytolerantnetworks:

CommunicationsSurveys&Tutorials,2006,8(1):24−37.[doi:10.1109/COMST.2006.323440]

[2]PerkinsC,:EEEWMCSA’gton:IEEEComputer

SocietyPress,1999.90−100.[doi:10.1109/MCSA.1999.749281]

[3]IntanagonwiwatC,GovindanR,eddiffusion:Ascalableandrobustcommunicationparadigmfornsornetworks.

In:k:ACMPress,2000.56−67.[doi:10.1145/345910.345920]

2552

JournalofSoftware软件学报Vol.21,No.10,October2010

[4]BiswasS,COMMComputerCommunicationReview,

2004,34(1):69−74.[doi:10.1145/972374.972387]

[5]BiswasS,::

York:ACMPress,2005.133−:///sigcomm2005/

[6]RoznerE,SeshadriJ,MehtaY,:EEE

gton:IEEEComputerSocietyPress,2006.48−54.[doi:10.1109/WIMESH.2006.288602]

[7]unisticroutingindynamicadhocnetworks::EEEMASS2006.

Washington:IEEEComputerSocietyPress,2006.570−573.[doi:10.1109/MOBHOC.2006.278612]

[8]CoutoDD,AguayoD,BicketJ,:CM/

gton:IEEEComputerSocietyPress,2003.134−146.[doi:10.1145/938985.939000]

[9]ChachulskiS,JenningsM,KattiS,:

k:ACMPress,2007.169−180.[doi:10.1145/1282427.1282400]

[10]ZorziM,phicrandomforwarding(GeRaF)foradhocandnsornetworks:

MobileComputing,2003,2(4):337−348.[doi:10.1109/TMC.2003.1255648]

[11]ZorziM,phicrandomforwarding(GeRaF)foradhocandnsornetworks:

leComputing,2003,2(4):349−365.[doi:10.1109/TMC.2003.1255650]

[12]ZhaoB,SeshadriRI,phicrandomforwardingwithhybrid—ARQforadhocnetworkswithrapidsleepcycles.

In:gton:IEEEComputerSocietyPress,2004.3047−3052.[doi:10.1109/

GLOCOM.2004.1378912]

[13]CaoQ,AbdelzaherT,HeT,r-Bad:

gton:IEEEComputerSocietyPress,2007.1928−1936.[doi:10.1109/

INFCOM.2007.224]

[14]YuanY,YangH,WongS,LuS,::

gton:IEEEComputerSocietyPress,:///viewdoc/summary?doi=

10.1.1.80.7105

[15]NassrMS,JangeunJ,EidenbenzSJ,HanssonAA,leandreliablensornetworkrouting:performancestudy

:gton:IEEEComputerSocietyPress,2007.670−678.[doi:

10.1109/INFCOM.2007.84]

[16]DuboisFH,GrossglaurM,calReport,LCAV-REPORT-2007-001,Schoolof

ComputerandCommunicationSciences,EPFL,2007.

[17]ZhongZ,WangJ,calReport,

TR-2006-015,USC-CSE,2006.

[18]ZhongZ,:gton:IEEEComputer

SocietyPress,2007.441−450.[doi:10.1109/SAHCN.2007.4292856]

[19]GrayC,SanthapuriN,:EEESECON2008.

Washington:IEEEComputerSocietyPress,2008.1−6.[doi:10.1109/SAHCNW.2008.17]

[20]ZengK,LouW,-to-endthrough:Proc.

gton:IEEEComputerSocietyPress,2008.816−824.[doi:10.1109/INFOCOM.2008.133]

[21]ZengK,LouW,:EEEMilcom

gton:IEEEComputerSocietyPress,2007.1−7.[doi:10.1109/MILCOM.2007.4454897]

[22]YanY,ZhangBX,ZhengJ,:Ac

WirelessCommunications,2010,17(3):96−103.[doi:10.1109/MWC.2010.5490984]

[23]YanY,ZhangBX,HusinM,ism:Proc.

gton:IEEEComputerSocietyPress,2009.[doi:10.1109/ICC.2009.5199177]

[24]ZubowA,KurthM,:EEEEW

gton:IEEEComputerSocietyPress,:///papers/

田克等:无线多跳网络中的机会路由

2553

[25]WuJ,LuM,:EEEICDCS2008.

Washington:IEEEComputerSocietyPress,2008.470−477.[doi:10.1109/ICDCS.2008.90]

[26]BaccelliF,BlaszczyszynB,ErmelE,mizedrelaylflectiontechniqueforopportunisticroutingin

:W2008.2008.1−7.[doi:10.1109/EW.2008.4623843]

[27]CuiT,ChenL,:EEEINFOCOM2008.

Washington:IEEEComputerSocietyPress,2008.361−365.[doi:10.1109/INFOCOM.2008.81]

[28]ZhangR,GorceJM,Jaffrèndofe:

gton:IEEEComputerSocietyPress,2009.[doi:10.1109/ICC.2009.5199148]

[29]YangZ,ZengK,::gton:

IEEEComputerSocietyPress,2009.2871−2876.[doi:10.1109/ICC.2009.5199042]

[30]YanY,ZhangBX,HusinM,:

gton:IEEEComputerSocietyPress,2009.4548−4553.[doi:10.1109/GLOCOM.2009.

5425249]

[31]ZhangX,:gton:

IEEEComputerSocietyPress,2008.243−250.[doi:10.1109/ICDCS.2008.45]

[32]GuoS,GuY,JiangB,unisticfl:

k:ACMPress,2009.133−144.[doi:10.1145/1614320.1614336]

[33]LiM,LouW,t:Opp:

gton:IEEEComputerSocietyPress,2009.534−543.[doi:10.1109/MOBHOC.2009.5336959]

[34]LeeS,SuW,-Networksand

Applications,2002,7(6):441−453.[doi:10.1023/A:1]

[35]TianK,ZhangBX,ZhangZ,HusinM,ation-Drivenon-demandmulticastroutingprotocolforwirelessadhoc

:gton:IEEEComputerSocietyPress,2009.[doi:10.1109/ICC.2009.5198907]

[36]MaJ,ZhangQ,QianC,-:CM

k:ACMPress,2007.33−38.[doi:10.1145/1247694.1247701]

田克(1976－),男,河南新乡人,博士,主要

研究领域为无线传感器网络,无线自组织

网络,无线Mesh网络协议算法,原型系统.

马建(1959－),男,博士,教授,博士生导

师,CCF高级会员,主要研究领域为未来互

联网人性化移动系统(包括移动无线传感

网,多媒体传感网,自组织网络,P2P网,泛

在网及社会网)协议与关键技术.

张宝贤(1972－),男,博士,教授,博士生导

师,CCF会员,主要研究领域为无线传感器

网络,无线自组织网络,无线Mesh网络算

法,关键技术,原型系统.

姚郑(1969－),男,博士,教授,主要研究领

域为软件工程,开放源码软件,无线传感器

网络.