无线Ad Hoc网络(以下简称为ad hoc网络)是由具有无线通信功能的节点在没有固定基础设施支持的情况下,自组织形成的一种无线网络,广泛地应用于抢险抗灾、野外探险、医疗急救、军事行动和环境监测等场合以及一些临时的重大活动中.常见的Ad Hoc网络包括移动Ad Hoc网络(mobile ad hoc network,简称MANET)与无线传感器网络(wireless sensor network,简称WSN)等.

与传统网络相比,Ad Hoc网络的节点能量往往有限,同时,在许多应用场合及时补充能量是不现实的.Ad Hoc网络的能量受限问题己成为制约其发展与应用的一个瓶颈,如何降低节点的能量消耗与延长网络的生存时间,已成为当前研究的一个热点.为了合理利用Ad Hoc网络节点现有的能量和减小通信过程中的能量消耗,近年来,很多国内外研究者提出了能量感知地理路由协议.以伊利诺伊大学香槟分校(University of Illinois at Urbana-Champaign)、渥太华大学(University of Ottawa)、亚利桑那州立大学(Arizona State University)、南加州大学(University of Southern California)、阿德雷德大学(University of Adelaide)、加州大学洛杉矶分校(University of California, Los Angeles)、康卡迪亚大学(Concordia University)为代表的国外大学和科研院所已经在该领域展开了一系列研究,并取得了初步成果.相比之下,我国在能量感知地理路由研究领域由于起步较晚,目前仅取得了阶段性成果.

本文系统阐述了近年来Ad Hoc网络能量感知地理路由研究现状及进展,目的在于更好地理解这些路由协议,为相应的地理路由协议进一步研究提供参考.本文第1节概述Ad Hoc网络能量感知地理路由协议.第2节解析典型能量感知地理路由协议.第3节对典型能量感知地理路由协议进行系统而详细的归类和多角度比较分析.第4节阐述能量感知地理路由协议研究目前存在的问题和未来需要研究的内容.第5节总结全文.

1Ad Hoc网络能量感知地理路由协议概述 1.1 地理路由介绍

自从美国哈佛大学(Harvard University)的Karp等人在2000年ACM MobiCom会议提出了地理路由GPSR (greedy perimeter stateless routing)^[1]以来,地理路由研究受到了国内外学术界和工业界的高度重视,IEEE和ACM的各种杂志和会议发表了大量的文章,诸多地理路由协议被提出来.地理路由是一种仅利用节点位置信息来实现数据转发的路由.与基于拓扑的路由相比,地理路由不需要建立和维护路由表,选择转发节点仅依据节点位置信息,而不是跳数、时延等指标.

在地理路由中,每个节点常用GPS(global position system)、北斗定位系统和节点定位技术来获得自己当前的地理位置信息;同时,周期性或自适应地向邻居节点发送Beacon分组或Hello分组,并且接收邻居节点发送过来的Beacon分组或Hello分组.这里,Beacon分组和Hello分组仅包含节点位置信息.通过这种方式,每个节点可以知道邻居节点位置信息.在网络中,每个节点都保存有一张用来记录邻节点位置信息的邻接表.源节点在发送数据分组之前,需要通过某种方式来获得目的节点的位置信息,并将这个信息添加到该数据分组的头部.然后,默认地根据贪婪转发策略选择一个邻节点来转发该数据分组.在整个数据转发过程中,每个转发节点只需要知道自己的位置信息和中继区域邻居节点的位置信息就可以完成转发,而不需要整个网络的拓扑信息,从而避免了盲目地洪泛,极大地改善了路由性能.从源节点到目的节点的整个数据传输可以分为两个主要阶段:首先确定目的节点地理位置,然后选择下一跳来转发数据分组.其中,前一个阶段由“位置服务”来完成,后一个阶段通过中间节点接力转发来实现.

根据对地理位置信息的表示方式和使用程度的不同,地理路由可以划分为贪婪路由、定向洪泛路由和分层路由这3类.在贪婪路由中,当前节点仅将数据转发到距离目的节点更近的一个邻居节点.该策略简单、可行,但容易受路由空洞影响而失效.在定向洪泛路由中,一个节点将收到的数据分组,通过定向广播发送给多个邻居节点.这多个邻居节点在地理位置上比当前节点更靠近目的节点.在网络负载加重的情况下,该策略具有很好的鲁棒性.为了适应大规模的无线网络的可扩展性,研究者提出了分层路由.分层路由将基于拓扑的路由与地理路由有机结合,为了提高路由效率,分层路由在局部范围和大的范围内分别采用基于拓扑的路由和地理路由.这里的地理路由既可以是贪婪路由,也可以是定向洪泛路由.

地理路由由于可扩展性好、鲁棒性高、实现容易,已成为降低资源受限Ad Hoc网络能量开销的一种有效方式.近年来已提出了很多能量感知地理路由协议.

1.2 能量感知地理路由概述

能量感知地理路由在路由选择及下一跳的选择过程中考虑了节点的能量消耗因素,路由的选择标准从与跳数等有关的指标转移到与能量消耗有关的参数上,以使节点在通信过程中所消耗的能量最小.

1.2.1 主要度量指标

现阶段,能量感知地理路由的主要度量指标有如下几种:

(1) 最小化每个数据分组的能量消耗^{[2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18]}

以c(u,v)表示从节点u传输数据分组到其一跳覆盖范围内邻节点v所消耗的能量,以表示从源节点n₁到目的节点n_k传输数据分组所经过的路径,则经过该路径传输数据分组所消耗的能量e可以表示为

(1)

其中,n_i(2≤i≤k-1)表示中继节点.对于任意一个数据分组,度量指标(1)的优化目标函数为

min e (2)

当数据分组经过每一跳的能量消耗均相等时,度量指标(1)的目标事实上就是要最小化路由跳数.在网络负载较低时,依据这种度量指标所选择的路由与根据最小跳数所选择的路由相同;而当网络负载加重时,由于出现通信冲突的概率大大增加,使得依据上述度量指标与基于跳数所选择的路由不同.

(2) 最大化网络寿命^{[19,20,21,22,23,24,25,26]}

在给定的网络中,总能找到一些核心节点,一旦这些节点消耗完其能量就势必引起网络分割,从而使得网络通信中断.因此,能量感知地理路由必须均衡网络流量负载,尽可能地让这些节点平均分摊网络能量开销,从而达到延长网络寿命的目的.

(3) 最小化节点的能量差异^[27,2829]

该度量指标认为:网络中所有的节点都同等重要,网络通信应该尽可能地保证每个节点的剩余能量相同或者是趋于相同.

(4) 最小化分组代价^{[30,31,32,33,34]}

最小化分组代价旨在最大化网络中所有节点的网络寿命,与度量指标(1)不同在于:该度量使得那些即将消耗完能量代价的节点尽可能地分布在不同的路径上.

(5) 最小化最大的节点代价^[24,25,26]

以c_i(t)表示某路径中节点i在t时刻传递一个数据分组所消耗的代价,以c(t)表示整个路径中c_i(t)的最大值,则度量指标(5)的优化目标函数为

min c(t) (3)

对于给定的通信环境,度量指标(5)显著地延长了从通信开始到第1次发生节点失效的网络时间.

1.2.2 节点选择准则

在没有整个网络节点位置信息的前提下,为了实现上述度量目标,国内外的研究者提出了一序列基于能量优化的选择转发节点的准则^{[30,31,32,33,34,35]}.对于当前节点c,以a表示其邻居节点,v表示其目的节点.设r=d(c,a),d=d(c,v), s=d(a,v).对于任意相距为k的相邻节点,直接传输1比特数据所消耗的能量表示为c₁xk^a+c₂.令f(a)=1/g(a),这里,g(a)表示节点a剩余的网络寿命.以表示节点a所有邻居x的f(x)的平均值;类似地,表示节点a所有邻居x的g(x)的平均值.目前,选择能量优化节点的准则主要有以下几种:

(1) Power

这类节点选择准则旨在减小通信过程中整个网络能量消耗.对于任意邻居节点a,当前节点c通过最小化p(c,a)+p(a,v)来选择下一跳.这里,

· p(c,a)=c₁r^a+c₂,表示到达节点a所需要消耗的能量;

· 是节点a达到目的节点v所需要的理想能量消耗.

(2) Cost

这类节点选择准则利用Cost选择剩余能量最多的节点充当下一跳来最大化网络寿命.对于当前节点c,其到邻居节点a的代价Cost(a)可以表示为这里,或R为节点c的传输范围.

(3) PowerxCost

在这类节点选择准则中,当前节点c选择一个邻居节点a,使得PowerxCost(a)=PowerxCost(c,a)+Powerx Cost(a,v)在所有邻居中最小.这里,

· PowerxCost(c,a)=f(a)x(c₁r^a+c₂);

·

(4) Power+Cost

在这类节点选择准则中,当前节点c选择一个邻居节点a,使得Power+Cost(a)=[Power+Cost(c,a)]+[Power+ Cost(a,v)]在所有邻居中最小.这里,

·

·

(5) PowerxProgress

在这类节点选择准则中,当前节点c选择一个邻居a,使得最小.

(6) Cost/Progress

在这类节点选择准则中,当前节点c选择一个邻居a,使得最小.

1.3 能量感知地理路由的研究意义

能量感知地理路由的最终目标是要寻找能量优化的路径来传输数据分组,其涉及到网络的连通性、容错性、可靠性、简单性、吞吐量、可扩展性等性能.针对当前Ad Hoc网络所应用的环境,研究能量感知地理路由的意义主要体现在:

(1) 有利于降低节点能量消耗与延长网络寿命

在给定Ad Hoc网络中,典型基于拓扑的路由往往利用最小跳数作为选择路径的依据,这种路由方式很难保证我们选择的路径是能量有效的.对于常规地理路由来说,也存在类似的问题.其根本原因在于:地理路由往往选择距离目的节点最近的邻接点作为下一跳,在转发数据过程中,根本没有考虑能量效益问题.对于资源受限,尤其是能量受限的Ad Hoc网络来说,选择能量优化的路径或下一跳来发送数据显得尤为重要.能量感知地理路由在转发数据过程中,通过引入能量消耗因子到路由决策中,极大地提高了数据分组通过能量优化路径和能量优化下一跳转发的概率,从而有利于降低网络节点能量消耗,同时有利于延长网络寿命.

(2) 有利于整体改善网络各项性能指标

在Ad Hoc网络中,通过能量感知地理路由降低节点能量消耗与延长网络寿命,我们能够最大限度地延长网络服务时间,及时传递消息,并改善网络的各项性能指标.例如,借助能量感知多路径地理路由来传输数据,我们能够将网络流量负载尽可能均衡地在多路径上传输,在降低节点能量消耗与延长网络寿命的同时,缩短了数据分组传输时延,提高了网络吞吐量,改善了数据分组的投递率等性能.

1.4 能量感知地理路由的分类

由于Ad Hoc网络与实际应用高度相关,单一的能量感知地理路由协议不能满足各种应用需求,因而,人们提出了众多能量感知地理路由协议.为了揭示这些协议特点,我们根据文献^{[2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,2829,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,4849,50,]}中能量感知地理路由协议采用的通信模式、路由建立时机、路由结构和投递方式等策略,运用多种分类方法对其进行了分类.由于国内外研究人员利用多种策略来实现路由机制,故同一能量感知地理路由协议可分属不同类别:

(1) 根据源节点和目的节点之间传输数据所经过的路径,可以分为单路径能量感知地理路由和多路径能量感知地理路由;

(2) 根据源节点和目的节点间对应关系,可以分为单播能量感知地理路由、多播能量感知地理路由和广播能量感知地理路由;

(3) 根据下一跳选择过程中是否考虑QoS(quality of service)约束,可分为保证QoS约束能量感知地理路由和不保证QoS约束能量感知地理路由;

(4) 根据是否周期性发送Beacon分组,可分为基于周期性Beacon分组能量感知地理路由和非基于周期性Beacon分组能量感知地理路由;

(5) 根据是否考虑路由空洞问题,可分为贪婪能量感知地理路由和全局能量感知地理路由;

(6) 从协议所考虑的网络是否同构来看,可分为同构能量感知地理路由与异构能量感知地理路由;

(7) 从协议所考虑的网络所处维数来看,可分为二维能量感知地理路由与三维能量感知地理路由.

2 典型Ad Hoc网络能量感知地理路由协议解析

近年来,国内外研究者提出了诸多能量感知地理路由协议,部分协议已经在仿真实验和实际系统中得到验证和应用.为了便于分析和理解,我们采用第1.4节中第1种方法对其进行分类,表 1列举了目前部分适用于Ad Hoc网络的能量感知地理路由协议,我们从中选取了一些典型的能量感知地理路由协议(字体加粗标明),对其基本思想、实现方式、路由特性和优缺点进行多方面的解析.

2.1 单路径能量感知地理路由 2.1.1 LAPAR^[9]

2001年,美国伊利诺伊大学香槟分校的Xue等人提出了位置辅助的功率感知路由LAPAR(location-aided power-aware routing).LAPAR基本思想是:利用转发节点及邻居节点通过GPS获得的位置信息及节点移动情况等信息,为每次路由发现设定一个能量优化的中继区域,仅允许位于该区域内的节点参与到路由的发现与数据分组转发过程中,一旦遇到路由空洞,将采用类似于GPSR的策略绕行.这里,中继区域的确定综合考虑了源节点和目的节点物理位置及节点能量消耗效益,通过位于中继区域内的节点接力转发数据分组,能够极大地优化网络能量消耗.虽然LAPAR通过引入中继区域减小了路由报文广播的影响范围,降低了接收与转发路由广播所消耗的能量,但由于所发现的路由是局部最优的,难以保证整个数据传输路径上的能量消耗是最优的.

2.1.2 Stojmenovic, et al.^[10]

加拿大渥太华大学的Stojmenovic等人提出了一种功率感知的地理路由协议,其基本思想是:对于当前转发节点a(包括源节点在内)选择一个邻居节点b,使得节点a,b间转发数据所消耗的功率p(a,b)与节点b转发数据到目的节点v所消耗的功率p(b,v)之和最小,即

(4)

这里,p(b,v)为节点b转发数据到目的节点v理想状态下所消耗的功率,其大小由采用的能量模型和节点间距离决定;N_a为节点a的邻居节点集.该协议认为:整个网络节点均匀分布,对于所有转发节点,其下一跳转发数据到目的节点的功率消耗是一种理想统计.由于没有考虑网络路由空洞等情况的出现,该协议仅适用于节点密度大且均匀分布的网络.

2.1.3 GEAR^[29]

GEAR(geographical and energy aware routing)基本思想是:通过选择最小路径代价的节点来转发数据分组,从而达到优化传感网能量消耗的目的.与定向洪泛路由协议相比,GEAR仅通过某个区域的节点转发消息,而不是通过整个网络来转发,从而节省更多的网络能量开销.GEAR转发消息包括以下两个阶段:

(1) 转发消息到目标区域

在此过程中,GEAR利用估计代价(estimated cost)和获得代价(learned cost)来表示路径代价.估计代价统筹考虑了节点剩余能量和到位于目标区域的目的节点的归一化距离.对于节点n,其估计代价c(n,r)定义为

c(n,r)=ad(n,r)+(1-a)e(n) (5)

其中,d(n,r)表示节点n到目标区域r的归一化距离,e(n)为节点n的归一化剩余能量,a为取值范围为0~1的比例因子.

获得代价是对估计代价的一种修正,默认情况下等于估计代价.在贪婪模式下,节点选择到目标区域获得代价最小的邻居节点作为下一跳,此时,节点获得代价等于估计代价.一旦遇到路由空洞,就从路由空洞节点开始,中间节点将自己的路径代价设为到达下一跳的获得代价与其下一跳路径代价之和.

(2) 在目标区域广播消息

在这个过程中,当网络节点密度大时,GEAR通过迭代将收到的消息广播给所有节点;否则,通过洪泛方式来广播收到的消息.

2.1.4 GPER^[54]和GPEB^{[11, 55]}

GPER(geographical power efficient routing)的基本思想是:当前节点u首先在传输范围内选择距离目的节点最近的邻节点v作为次目的节点,接着再选择若干个中继节点w₁,w₂,…,使其到次目的节点v的路径u-w₁, w₂,…,-v是能量优化的;然后,节点u将数据分组发送给节点w₁;之后,节点w₁按照节点u的处理方式转发数据分组.这个过程一直重复到目的节点成功接收到数据分组为止,一旦遇到路由空洞,则采用类似于GPSR的方式绕行.在整个数据的传递过程中,数据分组均沿着同一路径传递,使得流量负载不能均匀分布于整个网络中.

GPEB(geographic power efficient broadcast)是基于GPER的广播功率有效地理路由协议.文献^{[11, 55]}中深入讨论了广播路由的传输特性,指出:GPEB通过减少在节点覆盖重叠区域内的广播次数,可以显著优化网络能量消耗.在GPEB中,针对节点s,其邻居节点集合记为n(s),以f(s)表示节点s所寻找的一系列用来转发广播分组的邻居节点集.显然,f(s)Ín(s).用f_min(s)表示节点f(s)有最少节点的集合,则节点s的邻居节点覆盖范围都能被集合f_min(s)Ès内的节点覆盖.对于在n(s)-f_min(s)的邻居节点,它们均能被动收到广播分组.为了减少在节点覆盖重叠区域内的广播次数,节点s寻找具有最大纯有益区域(net beneficial area)的节点来构建f_min(s).在转发多播分组过程中,节点s首先寻找最小f_min(s),然后将f_min(s)中所有节点位置信息添加到广播分组里,并以最大的传输功率发送该广播分组.位于n(s)内的节点一旦收到该广播,则首先确定自己是否存在于广播分组中(即是否在于f_min(s)):如果在,则立即从广播分组中删除自己,并按照节点s发送广播分组方式转发该多播分组;否则,立即丢弃该广播分组.该过程一直执行到整个网络所有节点受到该广播分组.

2.1.5 LEMA^{[12, 13]}

针对有数据转发到多个目的节点的Ad Hoc网络,西班牙穆尔西亚大学(University of Murcia)的Sanchez等人^[13]提出了一种多播地理路由LEMA(localized energy-efficient multicast algorithm).LEMA工作原理为:对于具有n个目的节点d₁,d₂,…,d_n-1,d_n的当前节点s,首先建立一个能量感知的路由树,然后,沿着路由树从最大覆盖范围内按照Dijkstra算法确定一条到达下一个多播节点的局部能量优化路径.为了指导路径上的节点转发数据,LEMA在每一条路径上引入了SRH(source routing header)表记录当前节点所选路径上除自己本身外的一系列转发节点.当SRH表上的节点接收到数据时,首先将自己从当前表上删除,然后将数据转发给下一跳,下一跳重复类似过程.一旦当前节点上的SRH为空(意味着路由树的节点收到该多播),该节点则继续沿着路由树,从最大覆盖范围内,按照Dijkstra确定一条局部能量优化路径.针对无线传输因固有的误差而影响能量消耗,文献^[13]中提出了基于数据接收概率的能量模型来评估LEMA的能量有效性.

图 1给出LEMA的一个工作示意图,图中节点s有3个目的节点d₁,d₂与d₃,按照LEMA工作原理,s确定的路由树由图 1(a)中节点s,d₁,d₂与d₃连线所构成,图中随着节点位置的变化所构成的路由树不尽相同.确定路由树以后,节点s利用Dijkstra算法寻找最大覆盖范围内到目的节点的局部能量优化路径.在图 1(b)中,到d₁,d₂与d₃的路径分别为s-i-j,s-a-b-c,s-a-g-h,相应的SRH表为[i,j],[a,b,c],[a,g,h].3条路径上的节点i,a,b,a,g一旦接收到数据,则首先从SRH表中删除自己,然后分别将数据转发到节点j,c与h.节点j,c与h接收到数据以后,分别利用Dijkstra算法寻找最大覆盖范围内到目的节点d₁,d₂与d₃的局部能量优化路径.针对可能遇到的路由空洞,该协议采用类似于GPSR的方式绕行.

2.1.6 GMREE^[14]

针对无线传感中继网络(sensor and actuator network,简称SANET)的一对多通信需求,Sanchez等人在文献^[14]中提出了能量有效的多播地理路由协议GMREE(energy-efficient geographic multicast routing).GMREE包括贪婪转发和绕行转发两种工作模式,其数据包头包括目标节点位置信息、转发节点位置信息及转发模式(贪婪或绕行模式).对于当前节点c,其转发数据分组所消耗的能量为e(c,d)=d^a+c_e+|n(c,d)xc_r|.其中,c_e表示节点c与节点a处理信号所消耗的能量;c_r为处于节点c覆盖范围内侦听节点消耗的能量;n(c,d)为节点c传输半径d(c,a)=d覆盖范围内的邻居节点集;d^a表示节点c到节点a的路径损耗,a为信道衰减指数,取值范围通常为2~5.在贪婪模式下,针对k个目的节点,源节点c首先将目标节点分成s_k个集合(每个集合均包含这k个目标节点,只是子集划分不同),然后针对每个集合中的子集,尝试寻找一个到其所有目的节点距离小于其本身到该子集所有目的节点距离的节点:如果没有,就删除该子集;否则,保留该子集,并将该节点作为该子集可选转发节点.紧接着,节点c计算自己和该集合所有可选转发节点到其所有目标节点的能耗和前进距离,并计算出单位前进能耗代价.最后,当前节点c从所有集合中选择具有最小单位前进能耗代价的集合划分,并按照该集合的多播构成形式发送多播信息.针对数据转发到某一个目的节点,不存在可选中继节点的情况,当前节点c立即将数据包头转发模式调整为绕行模式,并记下当前节点位置信息,继续沿着空洞边缘以单播形式转发数据.位于空洞边缘的节点收到数据以后,通过与自己比较到目标节点的距离来决定采取何种模式转发数据.一旦其到目标节点距离比空洞节点近,则转换到贪婪模式下转发数据.

图 2给出GMREE一个工作示意图,图中d₁,d₂,d₃,d₄,d₅为5个目标节点所组成的一个集合,我们将其分为2个子集{d₁,d₂,d₃}与{d₄,d₅},当前节点c到5个目标节点的距离t₁=|cd₁|+|cd₂|+|cd₃|+|cd₄|+|cd₅|,其可选转发节点集合f_i={a₁,a₂}到5个目标节点的距离t₂=|a₁d₁|+|a₁d₂|+|a₁d₃|+|a₂d₄|+|a₂d₅|,前进距离为t₁-t₂,消耗的能量为e(c,d)+|f_i|xc_e,单位前进距离能耗代价为[e(c,d)+|f_i|xc_e]/(t₂-t₁).图 2中,源节点c首先将所有的5个目标节点划分为1个集合(每个集合包含所有目标节点),然后寻找出该集合子集的可选转发节点a₁与a₂(此时,因为只有1个集合划分,所以没有计算单位前进能耗代价),并按照该集合覆盖形式转发多播数据.

2.1.7 EEGR^[15],EBGR^[16]和LEARN^[17]

Zhang等人提出了一个能量有效的地理路由协议EEGR(energy efficient geographic routing).EEGR利用节点位置信息和能量消耗特性去选择下一跳.对于当前转发节点u,如果其到目的节点v的距离d满足d≤d_char且d≤r(d_char是转发临界值,r为节点的最大传输半径),则其直接将数据分组转发到目的节点v;否则,需要借助一个靠近理想转发节点的邻居节点作为中继节点来转发.这里,理想转发节点定义为距离当前节点距离为d_o(d_o为能量优化的传输距离),且位于源节点和目的节点连线上的节点.上述转发过程一直持续到数据分组被目的节点v成功接收到为止.在整个数据传输过程中,一旦遭遇路由空洞问题,EEGR的能量有效性则有所降低.对此, EBGR(energy-efficient beaconelss geographic routing)对其进行了优化.当转发节点遇到空洞时,EBGR利用无信标的角度中继(beaconless angular relaying)方法绕过.

LEARN(localized energy-aware restricted neighborhood)的基本思想是:在中继区域里选择能量运费(energy mileage)最高的节点作为中继节点.对于任何能量模型c(x),设x为当前节点到下一跳的欧拉距离,能量运费定义为x/c(x).在节点分布比较均衡的情况下,LEARN具有良好的能量利用效率;当节点稀疏分布时,其能量有效性急剧下降.

2.1.8 LED^{[56, 57]}

针对现有能量感知地理路由协议忽视节点位置误差而导致能量有效性降低的问题,Peng等人在文献^{[56, 57]}中提出了一种面向位置误差能量有效的地理路由协议LED(least expected distance).为了有效地评估节点位置误差效应,LED提出了一个位置误差模型.LED假设节点i与j分别分布在二维平面P(X_i,Y_i)与P(X_j,Y_j)位置,其节点位置误差服从高斯分布,以P¢(x_i,y_i)与P¢(x_j,y_j)分别表示其测量位置,于是有:X_i=x_i+W_i,Y_i=y_i+W_i,X_j=x_j+W_j,Y_j=y_j+W_j.这里,如果节点i与j互为邻居节点,则其真实距离Z_ij服从的分布f(Z_ij)满足:

(6)

其中,

在此基础上,文献^{[56, 57]}采用类似于文献[15-17]的能量模型,分析了节点能量传输特性,推导出能量优化距离d_o.为了便于分析,文献假设节点i位于坐标原点,目标节点位于(d,0),则其优化传输节点m应该位于(d₀,0)上,

如图 3所示.由于节点i位置服从高斯分布,则节点m服从高斯分布.为了减小能量消耗,节点i计算节点的任何一个邻居j与节点m的距离Z_jm的期望值E(Z_jm).这里,E(Z_jm)满足:

(7)

其中,

经过比较,最终节点i选择具有最小期望值的邻居节点来转发数据分组.迄今为止,LED是首个将节点位置误差引入到路由决策中的能量感知地理路由协议,在贪婪模式下,该协议能够较好地优化网络能量消耗;一旦遇到路由空洞则失效.

2.1.9 PAG,PAG:CFace(3),PAG:CFace(1):PAG^[33],PAGH,PAGO,PAGR,PAGRC和PAGR:CFace(1):PAGR^[34]

考虑到Ad Hoc网络节点的实际分布情况,Bdallah等人在文献^{[33, 34]}中提出了多个三维能量感知地理路由协议.

PAG(power adjusted greedy)的工作原理是:所有节点以二分之一的最大传输功率去发现邻居节点,在默认情况下,节点按照贪婪模式选择能量优化的节点以统一功率(节点最大传输的功率二分之一)转发数据,一旦遇到路由空洞,则增加相应传输功率b倍去发现邻居节点和转发数据.在这种情况下,节点如果发现新的邻居节点,则继续以贪婪方式转发数据;否则,放弃转发该数据.

针对在增加传输功率b倍情况下,PAG仍然寻找不到邻居节点的情况,PAG:CFace(3)(PAG:Coordinate Face(3))对其进行了优化.其工作原理是:贪婪模式节点以PAG方式转发数据,当遇到路由空洞时随机将路由空洞投影(最多尝试3次)到3个二维平面(xy平面、xz平面、yz平面)中的某一个平面,在二维平面上通过采用表面路由的方法进行数据转发.如果在此种情形下转发失败,就停止转发数据.

PAG:CFace(1):PAG是对PAG的另外一种优化,其工作原理是:在贪婪模式下,节点按照PAG方式转发数据,一旦遇到路由空洞,就将路由空洞投影到任意的一个二维平面(只能尝试一次);在二维平面上,通过采用表面路由的方法进行数据转发.如果这种情况下数据没有转发到最终目的节点并且不存在路由循环,则当前转发节点继续在三维空间按照PAG在贪婪模式下转发数据;否则,停止转发.

PAGH(power adjusted greedy algorithm with half transmission range)的工作原理与PAG类似,只是b=1. PAGO(power adjusted greedy algorithm with optimal transmission range)的工作原理与PAGH类似,只是所有节点不再以二分之一的传输功率去发现邻居节点和传输数据,取而代之的是最优传输功率.这里,最优传输功率是基于所采用的传输模型得到的.

PAGR(power adjusted greedy algorithm with optimal transmission range and threshold)的工作原理与PAGH类似,其不同点在于:所有节点以优化传输功率去发现邻居,当节点的覆盖度降低到一个阈值时,当前节点就以最大功率去发现邻居,其数据转发与PAGH完全相同.

PAGRC(power-aware greedy-cost)的工作原理与PAGR类似,其不同点在于:在贪婪方式下转发数据不同,具体来说,在贪婪模式下,在PAGRC中所有转发节点选择具有最大前进距离^[34]的节点为下一跳,而在PAGR中,所有节点选择距离目的节点最近的节点为下一跳.

PAGR:CFace(1):PAGR类似于PAG:CFace(1):PAG,只是b=1.

文献^{[33, 34]}在一定程度上解决了三维Ad Hoc网路的路由空洞问题,其前提条件是,要求投影在二维平面的节点服从随机均匀分布或规则分布.而在现实应用中,Ad Hoc网络部署环境复杂,容易受到物理环境的严格制约,经过平面化后的绕行空洞集中在少数节点上完成,容易导致数据碰撞和节点能量的过度消耗,从而扩大路由空洞.

2.1.10 LOSR^[18]

目前,地理路由普遍选取距离目的节点较近的或者最近的节点作为中继节点,而不能保证网络通信能量消耗最小或者趋于最小.这些路由方案忽视了适当引入一些位于非正向中继区域的节点能够降低网络能量消耗的事实.对于当前节点,非正向中继区域定义为不比其自身更靠近目的节点的邻节点所组成的集合.在文献^[18]中,穆尔西亚大学的Juan等人提出了一种局部优化的能量感知地理路由协议LOSR(locally optimal source routing).LOSR引入了不能提供正向前进距离的邻居节点,结合具有正向前进距离的邻居节点,通过Dijkstra算法寻找一条到次目的节点局部能量优化的路径来降低网络能量消耗.

图 4给出了LOSR工作原理示意图.

在图 4中,节点u与节点v分别为当前转发节点(或源节点)和目的节点,节点w₁,w₂,w₃与w₄分别为节点u可能的转发节点.对于节点u来说,首先选择距离目的节点v最近的节点为次目的节点.因为d(u,w)<min{d(w₁,v), d(w₂,v),d(w₃,v),d(w₄,v)},则其选择节点w作为次目的节点.然后按照Dijkstra算法寻找到一条到次目的节点w能耗最小的路径.图 4给出了3条可能的路径,分别为u®w,u®w₁®w₂®w,u®w₃®w.采用不同网络模型和能量模型,LOSR选择的路径不同.在这3条路径中,只有节点w₁到节点v的距离d(w₁,v)>d(u,v),其正向前进距离为负.当选择的路径为u®w₁®w₂®w时,说明与其他可选路径相比,节点u按照路径u®w₁®w₂®w传输数据到节点w消耗的能量最小.引入前进距离为负的节点充当转发节点,这是LOSR首次提出的,对减小网络能量消耗具有重大意义.

2.1.11 EIGR^[22]

文献^[22]结合图 5分析了地理路由能量有效性与降低网络干扰之间的关系,指出:能量有效的地理路由与降低网络干扰没有必然的关系.其主要原因在于,路由策略未将降低能量消耗与减小网络干扰同时作为优化目标来选择下一跳.如图 5所示,对于节点u来说,处于中继区域r(u,v)里的节点w₁,w₂,w₃,w₄和w₅都是其能量效益较高的可选转发节点,但它们能量优化的程度不完全相同,这与它们所处的物理位置有很大关系.对于能量受限的传感网来说,选择一个能量最优的中继节点是至关重要的.现有的能量感知地理路由往往将这个因素作为首要任务考虑,但是它们忽视了节点间的相互干扰.事实上,在网络中,每个节点都有可能充当其他通信的转发节点,转发数据具有随机性,节点间的相互干扰在所难免.干扰会造成节点浪费过多通信能量.考虑到这些因素,该文献提出了干扰优化的能量感知地理路由EIGR(energy-aware interference-sensitive geographic routing).EIGR以减小网络通信干扰和能量消耗为首要任务,其工作原理如下:首先,自适应建立锚节点表来引导数据分组的转发;然后,根据锚节点间位置信息,在能量优化中继区域决定直接转发数据还是选择所受干扰较小的节点来转发数据;最后,调整传输功率到优化值发送数据.在图 5中,EIGR将从能量优化的中继区域r(u,v)中,在节点w₁,w₂,w₃,w₄和w₅之间选择所受干扰最小的节点充当转发节点.

2.1.12 EAGR^[23]

EAGR(energy-aware geographic routing)的工作原理是:在发送数据之前,先建立锚节点表来引导数据的传输,每个数据分组以锚节点为次目的节点,在源节点、次目的节点和目的节点间选择能量优化的中继节点来转发.在转发数据过程中,EAGR结合网络能量消耗特征值、节点位置信息及能量消耗代价来选择转发节点,统筹考虑了节点在贪婪模式和边缘转发模式下的能量消耗.针对可能遇到的路由空洞,EAGR通过建立锚节点表来绕行.图 6给出了EAGR工作示意图,其主要由4个部分构成:

(1) 邻居节点信息收集与交换;

(2) 锚节点表的建立;

(3) 下一跳的选择;

(4) 传输功率的改变与分组的传输.

由于只使用贪婪模式沿着能量优化路径转发数据,EAGR有效地降低了网络能量消耗,同时减小了网络传输时延.在具有有限路由空洞节点的传感网中,如果锚节点间传感节点均匀分布,则EAGR能够有效降低网络通信能量消耗;否则,其有效性将显著降低.

2.1.13 OFEB^{[58, 59]}

针对现有能量感知地理路由忽视节点剩余能量而缩短网络寿命的情况,文献^{[58, 59]}提出了一种能量消耗均衡的地理路由协议OFEB(optimal forward with energy balance).OFEB基于所采用的能量模型分析了网络能量消耗特征,提出了能量优化的传输距离R_opt.在整个数据传输过程中,当前节点在最大传输范围内按照公式(8)选择具有最大f(E_res,Dd)的节点作为下一跳:

(8)

其中,Dd为邻居节点到理想转发节点距离.这里,理想转发节点与EEGR,EBGR定义类似,E_res与E_cap分别为当前邻居节点剩余能量和初始能量,a为取值范围为0~1的比例因子.OFEB由于考虑了节点能量状态,使得那些剩余能量较多的节点尽可能参与到转发数据的过程中,从而较大限度地延长了网络寿命,一旦网络中存在路由空洞,其有效性则大为降低.

2.1.14 EBaGR^[60]

针对贪婪转发和空洞解决方案中存在的节点能量消耗不平衡的问题,文献^[60]提出了一种具有能量意识的无信标地理路由协议EBaGR(energy-aware and beaconless geographic routing).EBaGR包括贪婪竞争策略和空洞解决策略两个模式.在贪婪竞争策略中,源节点或中继节点(即上游节点)以广播形式发送数据分组,位于转发域内具有最小动态转发延迟DFD(dynamic forwarding delay)的节点(即下游节点)一旦收到数据分组就以广播形式转发,其余候选节点侦听到该广播后就自动放弃转发.这里,DFD由当前节点、上游节点和目的节点的位置信息以及当前节点的能量状况计算得到,可以表示为

(9)

其中,a(0<a≤1)是可调常系数;r是节点的通信半径;p是指当前节点相对于上游节点向目的节点前进的距离;e表示当前节点的剩余能量;E是节点的初始能量;Max_delay是节点等待的最长时间,一般设为50ms.

如果经过Max_delay的等待时间,上游节点仍未侦听到下游节点转发数据分组,即认为转发域内无候选节点,随即将转入到空洞模式下转发数据.此时,上游节点将角度和能量信息同时加入到DFD计算中,寻找具有最小动态转发延迟的节点,从而在数据分组转发过程中有效地避绕空洞和平衡节点间的能量消耗.

2.1.15 PDA^[24]

在地理路由采用贪婪模式转发数据过程中,节点往往会遇到在当前邻居节点里找不到一个到目的节点距离与比自身到目的节点距离更近的节点的情形,此时,地理路由便由贪婪模式转换到边缘模式.一旦进入边缘模式,地理路由就会增加整个路径长度,并消耗额外的能量.为了解决该问题,文献^[24]提出了一种基于锚节点的能量感知地理路由协议PDA(projection distance-based anchor).PDA工作原理是:在开始发送数据之前,利用现有的地理路由(如GPSR)建立锚节点表来引导数据的传输,每个数据分组以锚节点为次目的节点,在锚节点间以贪婪方式经过多跳转发至目的节点.与绕行路由空洞转发数据的地理路由协议相比,PDA由于通过锚节点引导而不再绕行路由空洞转发数据,在一定程度上缩短了数据传输路径,从而较好地减小了网络能量消耗.与EAGR类似,PDA能量有效仅适用于锚节点间节点均匀分布的传感网.

2.2 多路径能量感知地理路由 2.2.1 OPDA^{[24, 25]}

针对PDA由于利用单路径传输数据到目的节点而导致网络寿命显著减小,OPDA(optimal PDA)提出了一种优化方案.OPDA通过对所获得的锚节点引入符合高斯分布的变量,获得一个动态变化的锚节点表.这样,不同的数据分组将获得一系列不同的锚节点,从而沿着不同的路径传输到目的节点.因为不同的数据沿着不同路径传输,OPDA尽可能地均衡了网络能量消耗,从而较好地延长了网络寿命.

图 7给出了OPDA工作原理的一个示意图.在图 7中,每个数据分组在发送前,通过向坐标为(x,y)的锚节点引入变量(x_i,y_i)来获得坐标为(x+x_i,y+y_i)的虚拟锚节点,从而达到动态获取新锚节点表的目的.每个数据分组以一系列虚拟锚节点为次目的节点,在相邻锚节点间,按照贪婪地理路由策略选择下一跳.当其传送到(x+x_i,y+y_i)而不存在真实节点时,调整次目的节点为下一个虚拟锚节点或目的节点.OPDA通过动态引入变量来获得多锚节点表,使得不同数据分组沿着多路径传输到目的节点,较好地均衡了网络能量消耗,在一定程度上延长了网络寿命.但是,因为没有考虑各条路径的能量消耗问题,从而导致整个网络的能量消耗较大,甚至是加大了网络能量消耗.

2.2.2 K-MGPSR,MGPER_hop与MGPER_sub^[61]

GPSR是国外研究者提出来的第一个地理路由协议,在传输数据时,只是选择距离目的节点最近的邻居节点作为中继节点,而使得网络传输能量消耗较大.对此,文献^[61]提出了能量感知的多路径地理路由协议K-MGPSR.在K-MGPSR中,转发节点首先在最大覆盖范围内确定k个可选转发节点.这里,k个可选转发节点均比当前节点距离目标节点要近,且比其他节点更接近目标节点.为了减小能量消耗,当前节点利用离散概率分布函数选择k个可选转发节点中的任何一个节点来转发数据,从而使得不同数据沿着不同路径传输到目的节点,较好地均衡了网络能量消耗.与采用其他可选分布函数选择转发节点相比,如果采用统一的概率分布函数,每个可选节点充当转发节点的概率为1/k;如果采用常规分布函数,则每个可选节点充当转发节点的概率会更高,如当k=3时,3个节点分别充当转发节点的概率为0.55,0.31,0.14.如果k变大,将会使更多节点参与到转发数据,而一旦有更多节点参与到转发数据,则会使多个转发路径偏离源节点和目的节点之间的直线路径,从而浪费过多的能量.

针对GPER由于采用单路径传递数据分组,易造成网络流量负载过于集中通过部分网络节点传输的问题,文献^[61]提出了能量感知多路径地理路由协议MGPER_sub(multipath GPER_sub)与MGPER_hop(multipath GPER_hopb),对其进行优化扩展.

在MGPER_sub中,当前节点u首先选择k个距离目的节点最近的节点作为备选次目的节点,然后从中选择一个节点v作为正式次目的节点.接着,从其他邻居节点中选择一个节点w,使得从节点u经w到正式次目的节点v的路径是能量优化的.图 8给出了GPER与MGPER_sub工作原理对比图.在图 8(a)中,GPER沿着路径u-b-f-g-j-v转发从节点u到目的节点v的数据分组.在图 8(b)中,k=3,当前节点u具有3个备选的次目的节点f,c与e,分别到达这3个次目的节点的中间转发节点有b,c与d.图 8(c)给出了节点u选择备选次目的节点f为正式次目的节点的示意图.节点u首先通过引入节点b构建了一条到达节点f能量优化的路径,接着转发数据分组到节点b.一旦节点b接收到该数据分组,则会采用与节点u类似的步骤,首先确定次目的节点,图 8(c)中为节点g与节点h(此时对于节点b来说,不存在第3个备选的次目的节点).在图 8(c)中,节点b选择了节点g为正式次目的节点,其下一跳为节点f.图 8(d)给出了节点u选择节点c作为次目的节点的示意图,其到达节点c的下一跳为节点本身.此时,在当前节点u与次目的节点c之间不存在第三方中继节点.

与MGPER_sub不同,在MGPER_hop中,当前节点u首先选择一个距离目的节点最近的节点v为次目的节点,然后找出k个可以到达节点v的中间转发节点,最后以等概率从这k个节点中选择一个节点作为到达节点v的转发节点.图 9给出了MGPER_hop示意图,其中,k=2.在图 9(a)中,节点u首先确定其次目的节点f,然后寻找能够到达节点f的两个中间节点b与c,紧接着,以等概率从节点b与c中选择一个作为下一跳.在图 9(b)中,节点u选择节点b为下一跳,一旦节点b接收到数据分组,则首先选择其次目的节点,然后确定两个可以到达该次目的节点的转发节点.

针对可能遇到的路由空洞问题,MGPER_sub与MGPER_hop采用类似于GPSR的边缘转发方式来加以克服.虽然MGPER_sub与MGPER_hop能够较好地均衡网络负载,但是由于二者不能保证所选择的次目的节点是能量优化的,同时也没有考虑处理路由空洞能量消耗问题,从而使得整个网络的能量有效性显著降低.

2.2.3 AGEM^[62]

针对无线多媒体传感网WMSNs(wireless multimedia sensors networks),文献^[62]提出了自适应的能量感知多路径地理路由协议AGEM(adaptive greedy-compass energy-aware multipath).AGEM工作模式分为贪婪模式和绕行模式两种.在默认情况下,每个转发节点以贪婪模式转发数据,一旦找不到转发节点(意味着遇到路由空洞)就切换到绕行模式转发数据.为了构建多路径,当前节点u首先以ud(d为目的节点)为直线,分别以逆时针和顺时针旋转a角度,在每个旋转区域基于剩余能量、节点间距离、转发次数来选择中继节点来转发数据.如图 10所示,图中Ðv₁ud与(a=30°)为节点u逆时针和顺时针旋转所形成区域,节点u首先在两个区域寻找不同节点发送不同数据到目的节点d,如果两个区域中任意一个区域不存在节点,则节点u分别逆时针和顺时针旋转更大角度(如图Da=30°,此时,)寻找节点来转发数据.一旦旋转角度超过90°,就意味着节点u找不到转发节点,此时,节点u将数据回送给上一个转发节点.此种情形将会极大地增加数据传输时延,甚至导致数据传输失败.

2.2.4 EMGR^[26]

EMGR(energy-aware multipath geographic routing)的工作原理是:动态地利用多锚节点表来引导数据转发,基于能量消耗特征选择能量优化的节点来转发数据,从而使不同数据尽可能地沿着能量优化的多路径转发到目的节点.EMGR主要由两个部分构成:

· 首先建立多锚节点表.为此,EMGR采用常规路由建立基本锚节点表,然后建立锚节点区域,通过随机选择每个锚节点区域的锚节点获得动态锚节点表,达到获取多路径的目的.

· 然后,选择能量优化的下一跳转发数据分组.在整个数据转发过程中,每个数据分组分别依次以锚节点表中的锚节点为次目的节点(除目的节点外),基于能量消耗特征和节点物理位置来选择能量优化的中继节点.

为了精确地统计网络能量开销,EMGR提出了一种新的能量模型,其能量消耗c(u,v)可以表示为

c(u,v)=c₁×d(u,v)^a+c₂+c₃×d(u,v)² (10)

其中,c₁×d(u,v)^a表示节点u与v之间的路径损耗,c₁表示传输节点u与接收节点v的能量消耗,c₃d(u,v)²为处于节点u覆盖范围内节点侦听的能量消耗.这里,a为信道衰减指数,取值范围通常为2~5;为平均网络密度,l是节点侦听信号所消耗的能量(对于所有侦听节点,这部分能量消耗相同).与现有相关研究相比,EMGR统计了网络中处于侦听状态的节点能量开销,更有利于选择能耗小的路径来转发数据.由于EMGR假设锚节点及锚节点区域间网络节点分布较为均匀,其能量优化将仅仅针对路由空洞分布于锚节点区域附近的传感网有效.

3 典型AdHoc网络能量感知地理路由协议比较

Ad Hoc网络能量感知地理路由协议对网络多个方面的性能均会产生显著影响,基于不同应用环境和设计目标,所采用的策略以及在系统中的表现也不尽相同,这使得能量感知地理路由协议具有多样性的特点,难以通过简单的比较来说明哪个协议更加优越.为了能够进行比较全面的说明,我们采用列表的方式对本文第2节解析的各种典型能量感知地理路由协议进行综合比较分析.表 2将所涉及的各种协议按照本文在第1.4节所介绍的7种分类方法进行了系统的归类.表 3按照单路径和多路径分类(本文第1.4节所介绍的第1种分类方法)对所涉及的各种协议性能与特点进行了总结与比较.比较的范围包括协议控制开销、能量有效性、可扩展性以及是否适用于异构网络、是否存在影响路由的关键节点、是否支持普通节点移动、适用于何种节点密度网络、路由负载等.表 4按照单路径和多路径分类对所涉及协议的应用范围进行了总结与归纳,但并不是绝对的.所比较的应用范围包括节点的移动性、网络规模、节点密度、通信干扰、位置误差、网络维数(二维还是三维)、网络类型、流量负载、数据丢包容忍、sink节点数目及QoS等.在实际使用中,我们应当根据Ad Hoc网络应用特点选择合适的能量感知地理路由协议,通常需要在网络规模、应用环境、实现难度、部署成本和协议性能之间做出折衷和选择.

4 存在的问题与亟待研究的内容

虽然Ad Hoc网络能量感知地理路由研究已经引起较大的关注,现有的研究工作也取得了一定的成果,但是普遍存在着一些问题.这些问题将是未来能量感知地理路由需要深入研究的内容,概括如下:

(1) 能量感知地理路由度量模糊,缺乏明确定义

能量感知地理路由涉及到网络的连通性、容错性、可靠性、简单性、吞吐量、可扩展性等性能,很多能量感知地理路由对提高Ad Hoc网络性能度量模糊,对能量优化研究的问题描述不明确.众多能量感知地理路由研究对减小Ad Hoc网络的能量开销关注较多,但对网络冲突、负载、吞吐量等考虑较少,在追求最小能耗的时候,往往会削弱网络整体性能,甚至不能保证能量消耗是最优或者是次优的.例如,我们在考虑节点选择传输路径或下一跳的时候,为了节省能量,很可能造成某些中间节点成为很多路由的中继节点,这样会加重这些节点的负载,加快其能量消耗速度,从而影响到网络的传输性能.能量感知地理路由最终的目标是要寻找一个能量优化的路径.对于究竟什么样的路径才能达到优化网络能耗的目的,目前还没有明确的定义与共识.不同的Ad Hoc网络在不同的应用中对能量感知地理路由的要求不尽相同,给出一个通用的定义比较困难.虽然在很多实际应用中不大可能寻找到能量消耗最优的路由,但是对能量感知地理路由的研究对于提升Ad Hoc网络整体性能具有重大的指导意义.

能量感知地理路由的好坏不仅应从能量角度上衡量,同时也应该兼顾网络性能等方面的需要.未来我们需要将网络能耗与网络干扰、连通性、容错性、吞吐量、简单性、可靠性、可扩展性等性能相结合来定义和研究能量感知地理路由,包括结合其他路由机制,如机会路由,来研究能量感知地理路由^[63].为了达到上述目的,我们可以从单路径、多路径、多播与广播及QoS等路由方面着手研究.

(2) 网络模型简单,研究结果没有足够的说服力

目前,大多数的能量感知地理路由研究将通过节省网络能量消耗来提高网络性能作为主要目标,但即使在十分理想的情况下,仍然不能判定和寻找到最小能耗的路由.节点在网络中的能量开销包括传输、接收、睡眠及侦听这4个状态所消耗的能量,然而很多相关文献通常仅考虑节点在传输状态与接收状态所消耗的能量,由于Ad Hoc网络通信受天气、地形、设备等因素的综合影响,就连这部分能量也很难精确统计.它是一个NP-hard问题.

当前,Ad Hoc网络能量感知地理路由研究及仿真实验所采用的能量模型过于简单化和理想化,往往与实际Ad Hoc网络差异较大,很多研究仅仅考虑同构网络,对异构网络考虑较少.例如,很多能量感知地理路由研究总是假定所有的节点具有相同的最大传输距离和最大发射功率^{[10, 15, 16, 23, 34]},即同构网络,而事实上,Ad Hoc网络的节点不可能总是相同,不同节点的发射功率和传输距离往往不相同.即使网络中所有的节点使用相同的发射功率,由于受地形及天气等因素的影响,每个节点所形成的覆盖范围最终也不尽相同.与同构网络相比,异构网络更接近实际的网络模型.由于网络的异构性给理论研究增加了复杂度,因此人们目前对异构网络的研究还比较少.现阶段,很多研究仅对能量感知地理路由做理论上的分析和小规模的仿真模拟,这些理论分析所基于的能量模型基本上是理想化的,而小规模的仿真模拟又不能仿真大规模Ad Hoc网络及其复杂的通信环境.实验和应用是能量感知地理路由有效性的最有说服力的证明,由于受经费等方面的限制,做大量节点的实验不太可能.此外,受硬件条件和技术等方面的限制,Ad Hoc网络还没有进入大量实用阶段.这些使得现有的研究结果普遍缺乏足够的说服力.

为了增加研究结果的说服力,我们需要构建更加实际的模型,特别是能量模型和通信模型.现阶段,能量感知地理路由研究往往仅将节点的发射状态与接收状态能耗作为其主要的能量开销来考虑,沈耀博士在文献^[64]中提出的能量模型将节点处于发射状态、接收状态、侦听状态的能量开销考虑进来.这是值得我们借鉴和关注的一个接近实际的能量模型.为了构建实用的通信模型,我们可以从随机型链路、链路信噪比、地形地貌等方面着手研究.此外,我们需要构建尽可能真实的仿真环境,同时加大实际验证,并以实际验证为主,仿真为辅.

(3) 节点位置误差影响着能量感知地理路由的效果

目前,我们常用GPS、北斗导航和节点定位技术来获取网络节点位置信息.通常情况下,网络节点可通过GPS接收机获得自己当前的地理位置信息,但是存在15m左右的位置误差.在Ad Hoc网络中,节点一跳的有效通信范围一般在几十米~一二百米之间,这样大的位置误差将会严重降低路由的精度和可靠性.随着我国北斗导航系统的逐步建立和完善,节点定位将变得低廉和便捷,定位的精度将有所提高,但同样存在着定位误差问题.目前误差约为25m,后期误差有望减小到10m.这些误差的存在,同样影响着我们能量感知地理路由路径选择的可靠性,甚至不排除选择的路径根本就不是能量最优的.在现阶段,有很多研究者提出利用信号强度等来估计节点相对坐标的方案,但由于信号易受衰减、噪声干扰等影响,使其在实际应用中受到很大的限制.

在后续工作中,我们需要建立误差模型来分析节点位置误差对能量感知地理路由性能的影响,并运用相关结论将节点位置误差引入到路由决策中统筹考虑,以此来提高能量感知地理路由有效性.同时,我们需要研究与开发具有精度高的定位技术来获得节点位置信息.

(4) 缺乏有效的局部优化方案

通常,地理路由包含贪婪模式与边缘模式两种工作模式.在默认情况下,地理路由利用贪婪算法选择下一跳.在贪婪模式下,选择的路由趋于源节点和目的节点之间的连线,沿着该路径转发数据所消耗的能量趋于次优.然而,一旦遇到路由空洞,地理路由进入到边缘模式下绕行路由空洞,使得整个传输路径变长,将消耗额外的能量.在没有全局网络的位置信息情况下,寻找一条从源节点到目的节点能量优化的路径是一个充满挑战性的问题.为了节省能量消耗,目前我们通常是采用锚节点作为次目的节点来引导数据的传递.在大多数情况下,该方案是可行的.但是我们不能保证在源节点、次目的节点、目的节点之间是否还存在路由空洞,这使得我们选择一条能量优化的路径变得异常艰难,几乎是一个NP-hard问题.虽然现有的研究提出了一些能量感知选路策略,但是这些策略仅仅在贪婪模式下表现出良好的能量优化性能,一旦在路由中遇到路由空洞,其节省能量的有效性则将大为降低.

解决这些问题的关键在于,需要我们研究新的局部优化方案.如何考虑各因素、权衡各因素的影响、针对具体问题制定切实可行的路由策略,是值得我们进一步研究的内容.在前期的研究工作中,我们提出了利用电子地图感知节点分布来引导地理路由数据传输的方法,取得了较好的数据传输性能.在未来能量感知地理路由协议研究工作中,我们可以借助于电子地图来提前感知路由空洞,在此基础上设计和研究新的局部优化方案.

(5) 三维地理路由研究显不足,缺乏有效的三维能量感知地理路由

当前,能量感知地理路由的研究与方案设计通常基于二维平面网络,而事实上,Ad Hoc网络的节点所处高度并不总是相同,同时,所处环境也不尽相同,三维立体空间建模更能反映节点实际所处环境的差异性.在二维环境下,现有的研究忽视了节点高度的差别,利用欧拉距离能够选择到更接近目的节点的中继节点,然而在三维环境下,这个结论未必成立.同时,由于节点的随机分布和节点能量的耗尽而导致的失效,使得三维环境下依然存在路由空洞.由于现有的二维环绕路由空洞方案不能直接应用到三维环境下,现有的三维能量感知地理路由研究还没有一个行之有效的方案.国内外研究者虽然进行了一系列的尝试,但是很少有这方面的成果介绍和报道.文献^{[17, 33, 34]}虽然能够绕开路由空洞,但是并不能保证转发数据的路径是能量优化的.随着小型化和廉价的定位设备的推广以及定位技术发展,地理路由在Ad Hoc网络将具有更加广阔的空间.分析与研究三维空间Ad Hoc网络的特性,运用相关结论设计能量优化的地理路由协议,必将成为未来能量感知地理路由研究领域的趋势之一.今后,我们将在这方面展开一系列的研究,研究内容包括三维空洞绕行、三维多播能量感知地理路由、三维广播能量感知地理路由、三维多路径能量感知地理路由等.

5 总 结

本文系统综述了Ad Hoc网络能量感知地理路由协议研究现状及进展,并分析了当前研究中所存在的问题.从目前研究现状来看,现有的能量感知地理路由协议研究已经取得初步的成果,但普遍存在着能量度量模糊、缺乏明确定义,模型过于理想化、研究结果没有足够说服力、位置误差影响路由效果、缺乏有效的局部优化方案、对三维地理路由研究不足、忽视对三维能量感知地理路由研究等问题,这些问题有待于我们未来进行深入的研究.目前,实用化的Ad Hoc网络能量感知地理路由协议研究尚处于初步探索阶段.随着研究的深入进行,能量感知地理路由必将日趋成熟与完善,Ad Hoc网络必将迎来更广阔的发展空间,展现出更巨大的应用价值.