基于上下文认知的高能效路由算法

Foundation items: Supported by the National Natural Science Foundation of China(61272454),the Specialized Research Fund for the Doctoral Program of Higher Education of China(20130141110022) and the Science Research Fund of Hubei Provincial Education Office(Q20152703)

† 通信作者： 张沪寅(1962-),男,博士,教授,博导生导师,主要从事网络QoS、计算机网络研究.E-mail: zhy2536@whu.edu.cn

基于上下文认知的高能效路由算法*

徐方1,2张沪寅1†徐宁1汪志勇1

(1．武汉大学 计算机学院,湖北 武汉 430072; 2．湖北工程学院 计算机与信息科学学院, 湖北 孝感 432000)

摘要：针对由智能移动通信设备组成的、支持网络富媒体应用的无线Ad hoc网络环境,提出了一种基于上下文认知的高能效路由算法.该算法使用上下文认知自学习方法监测设备运行过程中的上下文信息,计算节点上各类应用对应的能量效用值,然后综合利用节点上与应用相关的能量效用、剩余能量和信号强度等上下文信息自适应地调整路由,为资源受限的移动节点节约能量.仿真结果表明,与一些经典路由算法相比,文中路由算法能有效地提高网络的能量使用效率和网络生存时间,减少网络的时延开销.

关键词：自组网；上下文认知；能量效率；路由算法；应用程序

基金项目：* 国家自然科学基金资助项目(61272454);高等学校博士学科点专项科研基金资助项目(20130141110022);湖北省教育厅科学研究项目(Q20152703)

作者简介：徐方(1981-),男,博士生,主要从事无线移动通信网络研究.E-mail: xf2012@whu.edu.cn

文章编号：1000-565X(2015)05-0139-06

中图分类号：TN915

doi:10.3969/j.issn.1000-565X.2015.05.022

随着智能移动通信设备数量的快速增长,这些设备有可能形成移动Ad hoc网络,从而为本地的网络服务提供一种廉价的替代方案.这种Ad hoc无线网络可以部置在公共场所,作为一个复杂异构无线网络环境的一部分[1].在集成有传感器的智能移动通信设备组成的网络中,路由协议可以利用各种上下文信息反映出的变化来提高Ad hoc网络的性能[2].

上下文认知路由协议中的上下文信息主要有能量上下文、位置上下文、功率上下文、频谱上下文等[3].文中侧重于讨论与能量相关的上下文认知路由算法.传统的路由算法大多忽略节点的能量消耗,这样可能会导致网络中某些节点电能的过快消耗,因而容易造成路由断裂、网络分割的情况,严重影响网络的性能[4].由于终端节点的能量受限,节省能耗和均衡能耗是目前深入研究的重点[5].文中提到的高能效是指网络中的能量使用效率较高,而能量使用效率是指网络中传输一定数量的数据时节点所消耗的能量平均值.

最小总传输能量路由(MTPR)算法[6]选取节点总传输功率消耗最小的路径作为数据转发路由.由于没有考虑到节点的剩余电量,MTPR并不能平衡网络中每个节点的能量消耗,故存在某些节点能量消耗过快的问题.Singh等[7]提出了最小最多电池耗费路由(MMBCR)算法,该算法以网络中节点的剩余能量为度量标准,可以延长节点的生存时间.在所有能发现的路径上,该算法计算出每条路径上各节点的剩余能量,然后利用路径中剩余能量最少的节点(瓶颈节点)来检测该路由的保持稳定的时间.有条件的最大最小电池容量路由(CMMBCR)算法[8]同时考虑了总的路径传输的能量消耗和节点剩余能量,通过设置节点剩余能量的阈值来保护瓶颈节点.最小能量流失率路由(MDR)算法[9]引入了节点能量消耗速率,结合节点能量消耗速率和节点剩余能量来预测节点的生存时间,但在网络流量有细小变化时,MDR不容易准确评估和计算节点能量消耗速率.

文献[10]中提出了一个具有跨层能量负载感知的框架(DELAR),它适用于具有设备多样化特征的Ad hoc网络,其路由开销度量考虑了节点剩余能量和节点密度状态.文献[11]中提出了链路稳定性和能量感知的Ad hoc路由算法(LAER),该算法综合考虑链接稳定性和能量消耗速率两种路由度量,并使用多目标整数线性规划优化模型,力求最小化移动节点的能量消耗和最大化链路传输的稳定性.文献[12]中提出了一种灵活的高能效路由机制(E2),它平衡地利用了节点剩余能量和节点失效度.E2路由机制是在多条路径中选择能量优化的路径,使被选中的路径有最高的剩余能量和较少的跳数.

从以上分析可知,由智能移动通信设备组成的Ad hoc网络在路由设计方面还有较大的改进空间,在计算智能移动通信设备的能量效用时不仅要考虑其剩余能量、传输功率和链路稳定性等因素,还应考虑设备上应用程序的能量消耗对节点开销的影响.为此,文中提出了一种适合于Ad hoc网络环境且具有上下文认知能力的高能效路由(CAER)算法.该算法利用网络中与能量相关的上下文信息动态优化路由选择策略,以实现网络性能和能量使用效率之间的平衡.

1上下文认知自学习过程

在智能移动终端中,很多上下文信息与能量相关,如设备特征(电池容量、屏幕大小等)、设备上的应用类型、网络状况和用户偏好等,在操作系统的应用层可以获得这些上下文信息.图1描述了上下文认知自学习过程,包括初始化、检测和节点开销计算3个阶段.首先构造设备的组件负载能效表,用于描述节点上主要硬件组件的工作负载与对应能量消耗速率之间的关系;然后结合当前节点上应用的具体情况计算出节点应用的效用开销.

图1上下文认知自学习过程

Fig.1Context-aware self-learning process

1.1初始化阶段

目前智能移动通信设备的生产厂商繁多,生产的设备规格有所差别,从而导致同样的应用在不同规格的硬件上产生不同的工作负载.更重要的是,在不同设备上相同的工作负载率会导致不同的电池消耗速率.因此,初始化阶段主要是为了解决此问题.

现有智能移动通信设备中主要的耗能组件有图形处理器(GPU)、处理器芯片(CPU)、屏幕(SCR)、蜂窝网络模块(CELL)和WLAN模块[13].不同应用在这些组件上的能量消耗差异很大,故在初始化阶段重点考虑这5个硬件组件.首先在每个节点内部的5个硬件组件上运行一组预定义的任务,以便取得相应的负载(分别是5%、25%、50%、75%和100%),然后使用线性内插法来检测它们对应的能耗(线性内插法虽然精度有限,但资源耗费少).因此,在初始化阶段为节点中每个组件建立了一个工作负载百分比与能量消耗速率之间的对应关系,即组件负载能耗表.

1.2检测阶段

当一个新的应用启动时,该过程开始记录硬件上的工作负载;而应用结束时,计算工作负载的平均值,并将新记录添加到应用负载描述表中,其中对于应用j来说,LCPU(j)为CPU上的工作负载,LGPU(j)、LCELL(j)和LWLAN(j)分别为GPU、CELL、WLAN模块上的工作负载.上下文认知自学习过程获取和维护上下文信息,采样和检测当前节点每个硬件组件的工作负载,将“应用,组件,能量约束”关系存入节点应用能效表.屏幕的能量消耗速率可以通过操作系统获取屏幕亮度参数来记录,它高度依赖于环境照度和用户偏好.

1.3节点开销计算阶段

结合当前节点的剩余能量和节点应用能效表可以计算出当前节点的开销.一旦智能移动通信设备启动,就可以从操作系统获取当前屏幕的亮度和当前应用的类型,然后结合节点应用能效表计算出节点的开销.如果在应用能效表中没有找到当前正在运行的应用程序的记录,则上下文认知自学习模块启动监测过程,并在应用能效表中建立一条记录.其中,应用的能量约束效用函数Uapp为

(1)

(2)

Ucomp,i=Ecomp,i/Ecomp,i,max

(3)

式中,Ecomp,i为第i个硬件组件的能耗速率,Ucomp,i为第i个硬件组件上应用能量约束的效用等级,权值Wcomp,i为第i个组件的最大能耗Ecomp,i,max与系统最大能耗的比值,第i个组件的效用函数Ucomp,i是该组件在某个应用阶段的能耗与该组件最大能耗的比值.

然而,在计算节点的效用值时,不仅要考虑与应用相关的开销,还应考虑节点电池剩余能量的影响.设Econs为检测过程中取得的实时能耗值,Etotal为总的电池容量,则节点上能量水平的效用函数Ubat为

Ubat=Escale/e1-Escale

(4)

Escale=Econs/Etotal

(5)

它的取值范围是0～1.式(4)使用指数式表达Ubat,表明Ubat越小,节点上的剩余能量越多,节点的运行状态越可靠.

节点开销(Cnode)由节点上的应用开销和剩余能量开销组成,即

(6)

式(6)中通过使用归一化的权重Wapp和Wbat来协调上述两个因素对节点开销的贡献.

2链路上的能量效用计算

路径开销不仅包括节点能量开销,还要包括链路信号强度的影响(即链路开销).假设链路是双向对称的,每个节点使用固定的发射功率.节点的发送功率Pt与接收功率Pr服从∂次方路径损耗,即

Pr=cPtd-∂

(7)

式中:c为常数;d为发送节点与接收节点之间的欧拉距离;∂取决于节点所使用的无线传播模型[14],自由模型中∂取值为2,双线模型中∂取值为4.

(8)

(9)

它的范围是0～1.这里假设所有智能移动通信设备传输数据时使用固定的发射功率.由式(9)可知,Pr越大,Clink越小,链路上的数据传输越稳定可靠.

3CAER路由协议

文中提出的高能效路由算法CAER使用广播式方法进行路由发现,通过中间节点建立和维护路由表并进行数据转发.该算法通过上下文认知自学习过程获得网络中的能量效用和链路开销,然后在路由请求报文中加入能量效用信息Enode和链路开销Elink,为路由决策提供依据.路由算法主要包括路由发现和路由维护两个阶段.

3.1路由发现

(1)源节点首先发起路由请求(RREQ)过程,RREQ报文包含源节点序列号、目的节点序列号、广播ID、节点开销和链路开销,其帧格式如图2所示.

源节点序列号目的节点序列号广播IDEnodeElink

图2RREQ帧格式

Fig.2RREQ frame format

Enode和Elink分别由式(10)和(11)计算得出.k为路径上当前节点的序号,源节点的序号为1,下一跳节点的序号依次递增,目的节点序号为n,直到k=n时Enode和Elink才分别表示整个路径上的能量效用值和链路效用开销值.

(10)

(11)

(2)节点在收到路由请求报文时,比较本节点和目的节点的地址,如果自己是目的节点,则回复路由响应报文,否则根据〈源地址序列号,广播ID〉判断是否收到过该路由请求消息,如果之前收到过该请求,则丢弃该请求消息以防产生路由环路,否则记录相应的信息形成反向路由,同时更新RREQ中的Enode和Elink.获取的能量信息来自每个节点部署的上下文认知自学习模块,其更新公式为

(12)

(13)

(3)如果中间节点存在到目的节点的路由,则直接向源节点发送路由应答报文(RREP),完成路由发现过程;否则目的节点收到第1个路由请求后,开始启动定时器,等待一个延时T的时间,接收所有有效的请求.目的节点收到每一个有效路由请求后,计算路径的效用Croute,

(14)

在定时器的值达到T后,选择Croute值最小的路径向源节点发送RREP,完成路由的发现过程.

3.2路由维护

若路由表中的某条路由正在被使用,则更新该路由表项的超时时间为当前时间与超时阈值之和.如果节点收到源地址和目的地址相同的新的路由,则比较路由表中存储路由和新路由的序列号,选择序列号大的为有效路由.当节点移动时,路由表中的已有路由可能会失效.根据不同的节点类型,文中算法采取不同的路由维护策略:①如果路由失效是因源节点移动所导致,那么此时只能由源节点在网络中再次发起路由请求；②如果路由失效是因为目的节点或者中间节点移动所导致,则检测到路由断裂的节点会发送报文给其上游节点,告知其目的节点不可达.这样,检测到路由断裂的节点和源节点之间的所有节点都会收到报文并及时更新本地的路由信息.

4实验仿真与结果分析

4.1实验环境与参数设置

文中采用NS2网络仿真平台对CAER算法的能源效率和性能进行评估,并在同样的网络参数环境中与AODV[15]、E2和LAER路由算法进行了对比分析.仿真场景的主要参数设置如下:节点数为150,节点全随机移动,网络范围为400m×250m,节点移动速率为2m/s,传播模型为两径传播模型,最大传输范围为50m,全向天线模型,802.11 MAC层协议,传输带宽为2Mb/s.

为简化实验,文中根据节点上所运行的应用将150个节点分为50个空闲节点(A类节点)、50个游戏节点(B类节点)和50个3G视频流媒体节点(C类节点).4对随机选择的源到目的节点传输视频流,采用5种不同的传输速率(150、200、250、300和350kb/s),每种速率运行20次,每次模拟的持续时间为100s.设定空闲节点、游戏节点和3G视频流媒体节点的功率分别为150、350、550mW,接入WiFi/WLAN的功率为400mW.每个节点的初始能量为100J.

设定A、B、C类节点的Uapp分别为0.25、0.45、0.65,Wapp和Wbat分别为0.4和0.6,以突出节点剩余能量效用对总效用的贡献,Wlink和Wnode分别为0.1和0.9,以体现节点开销的重要性.由式(7)可知,节点接收到的信息强度与其到发射节点的距离d有关,而距离d可以通过两个节点的坐标值进行计算.

4.2仿真结果分析

A、B和C类节点在5种不同数据传输速率下的平均能量消耗如图3所示.在图3(a)中,由于AODV算法没有考虑到节点能耗问题,故其平均能耗最大;其他3种算法考虑了节点能耗因素,在不同程度上降低了网络的平均能耗.CAER算法对A类节点的节能效果最为明显,在5种传输速率下,相比于AODV算法,CAER、LAER和E2算法能为A类节点平均节能约21%、15%、12%.这是因为A类空闲节点的能量使用率低、剩余能量多,为引入上下文认知机制的CAER算法提供了更多的节能空间.对于B类游戏节点,由于E2和CAER算法都考虑了节点剩余能量问题,特别是在网络运行后期能对剩余能量低的节点进行保护,故其节能效果远远优于AODV算法.CAER算法不仅考虑了节点剩余能量问题,还考虑了节点上相关应用能耗以及链路开销的影响,故其节能效果最优.与AODV算法相比,CAER、LAER和E2算法分别为B类节点节约了14%、10%和9%的能量.在3类节点中,CAER算法为C类节点节能的效果最不明显,这是因为C类节点上本地应用消耗的能量太多,留给路由策略节省的能量空间有限.与AODV算法相比,CAER、LAER和E2算法分别为C类节点节约了7%、6%和4%的能量.这些结果表明,CAER算法在路由过程中利用了多种能耗相关的上下文信息,通过自学习过程为路由选择提供依据,故相比于其他高性能协议降低了网络的平均能耗.

图33类节点的平均能耗

Fig.3Average energy consumption of three kinds of nodes

不同数据传输速率下各算法的网络生存时间如图4(a)所示,其中网络生存时间的计算方法为:网络中前10个因数据通信而耗尽能量的节点存在时间的算术平均值.从图可以看出,Ad hoc网络的生存时间随着传输业务负载的增大而减小.由于AODV路由算法没有考虑节点的能耗因素,故其生存时间最短.其他路由算法考虑了能量信息进行路由选择,在不同程度上提高了网络的生存时间.相对于AOVD算法,CAER、LAER和E2算法的网络生存时间平均分别提高了约20%、12%和15%.E2算法考虑了对节点失效度的评估,故其生存时间略高于LAER算法.CAER算法考虑了节点的应用程序能效、剩余能量和传输路径的稳定性,故其生存时间性能最好,特别是在业务负载加大时,提高网络生存时间的效果最为明显.

图44种算法的网络生存时间和平均端到端时延

Fig.4Network lifetime and average end-to-end delay of four algorithms

不同数据传输速率下各算法的平均端到端时延如图4(b)所示.所有路由算法的网络时延随着业务负载的增加而增大．在传输速率较低时AODV算法的时延性能要优于其他算法,这是因为AODV算法是以源节点到目的节点的最短路径为原则,选择跳数最小的路径转发数据,而其他路由算法还要考虑能耗等其他因素,并不是每次选取的路径都是跳数最小的路径.在传输速率为150kb/s时,相比于AODV算法,CAER、LAER和E2算法的平均时延分别增加了11%、18%和9%．随着数据传输速率的增加(传输速率大于230kb/s),网络负载越来越大,某些链路上会出现拥塞情况,由于AODV算法没有考虑这些上下文信息,故其时延逐渐增大.在传输速率为350kb/s时,相比于AODV算法,CAER、LAER和E2算法的平均时延分别减少了12%、7%和14%.增大传输速率后,E2算法的时延性能表现最好,其次是CAER算法.

不同数据传输速率下网络中接收节点的平均吞吐量如图5所示.随着数据传输速率的增加,使用这4种算法的网络中接收节点的平均吞吐量均呈上升趋势.考虑了节能因素的E2、LAER和CAER算法的吞吐量性能不及AODV算法.相比于AODV算法,CAER、LAER和E2算法的平均吞吐量分别降低了6%、6%和11%.

图5接收节点的平均吞吐量

Fig.5Average throughout of receiving nodes

大量的仿真实验结果表明,CAER算法在不同程度上为这3类节点节约了能量.负载均衡和路由稳定性是一个综合性的指标,可以用网络的平均生存时间和平均端到端时延综合反映.仿真实验结果表明,虽然CAER算法的平均吞吐量稍差于其他算法,但其负载均衡和路由稳定性优于其他算法.

5结语

目前人们携带的智能移动通信设备不同于传统的Ad hoc终端,它支持丰富的网络多媒体应用.不同应用对终端能量使用效率的影响各不相同,如果不对这一因素加以考虑,会导致某些节点能量的过度使用,使其有限的能量过快耗尽,出现路由断裂和网络分割现象.此外,链路开销也是路由选择的一个重要因素,接收到的信号强度不够,会出现数据包的多次重传,增加网络拥塞,导致数据传输速率下降.为此,文中所提出了基于上下文认知的路由算法,该算法通过对节点的应用、设备特征和用户喜好等上下文知识的学习和利用来进行路由决策.在不影响路由性能的情况下,文中算法能有效地提高网络中能量的使用效率,同时对网络的负载均衡有着积极的影响.今后将使用真实智能移动通信设备组成试验床,对用户服务质量(QoE)进行研究和分析.

参考文献：

[1]Collins K,Mangold S,Muntean G.Supporting mobile devices with wireless LAN/MAN in large controlled environments [J].IEEE Communications Magazine,2010,48(12):36-43.

[2]Makris P,Skoutas D N,Skianis C.A survey on context-aware mobile and wireless networking:on networking and computing environments’ integration [J].IEEE Communications Surveys & Tutorials,2013,15(1):362-386.

[3]Chen Z,Wang H,Liu Y,et al.A context-aware routing protocol on Internet of things based on sea computing model [J].Journal of Computers,2012,7(1):96-105.

[4]朱斌,曾孝平,仲元红,等.一种能量高效的 Ad hoc 网络路由协议 [J].华南理工大学学报:自然科学版,2010,38(10):42-46.

Zhu Bin,Zeng Xiao-ping,Zhong Yuan-hong,et al.An energy-eficient routing protocol for ad hoc networks [J].Journal of South China University of Technology:Natural Science Edition,2010,38(10):42-46.

[5]Conti M,Giordano S.Mobile ad hoc networking:milestones,challenges,and new research directions [J].IEEE Communications Magazine,2014,52(16):85-96.

[6]Scott K,Bambos N.Routing and channel assignment for low power transmission in PCS [C]∥Proceedings of the 5th IEEE International Universal Personal Communications Conference.Cambridge:IEEE,1996:498-502.

[7]Singh S,Woo M,Raghavendra C.Power-aware routing in mobile ad hoc networks [C]∥Proceedings of ACM MobiCom’98.Dallas:ACM,1998:181-190.

[8]Cao L J,Dahlberg T,Wang Y.Performance evaluation of

energy efficient ad hoc routing protocols [C]∥Procee-dings of IEEE International Performance Computing and Communications Conference.New Orleans:IEEE,2007:306-313.

[9]Kim D,Garcia-Luna-Aceves J J,Obraczka K,et al.Power-aware routing based on the energy drain rate for mobile ad hoc networks [C]∥Proceedings of IEEE the Eleventh International Conference on Computer Communications and Networks.Tallahassee:IEEE,2002:565-569.

[10]Liu W,Zhang C,Yao G,et al.DELAR:a device energy load aware relaying framework for heterogeneous mobile ad hoc networks [J].IEEE Journal of Selected Areas Communication,2011,29(8):1572-1584.

[11]de Rango F,Guerriero F,Fazio P.Link stability and energy aware routing protocol in distributed wireless networks [J].IEEE Transactions on Parallel Distributed Systems,2012,23(4):713-726.

[12]Ramrekha T A,Talooki V N,Rodriguez J,et al.Energy efficient and scalable routing protocol for extreme emergency ad hoc communications [J].Mobile Network and Application,2012,17(2):312-324.

[13]Perrucci G,Fitzek F,Widmer J.Survey on energy consumption entities on the smartphone platform [C]∥Proceedings of IEEE the 73rd Vehicular Technology Confe-rence.Yokohama:IEEE,2011:1-6.

[14]黄浩军.无线Ad Hoc网络中能量优化的路由协议研究 [D].成都:电子科技大学通信与信息工程学院,2012:46-48.

[15]Perkins C,Belding-Royer E,Das S.Ad hoc on-demand distance vector (AODV) routing [S/OL].(2003-07-13).http:∥tools.ietf.org/html/rfc3561.html.

An Energy-Efficient Routing Algorithm Based on Context Awareness

XuFang1,2ZhangHu-yin1XuNing1WangZhi-yong1

(1.School of Computer,Wuhan University,Wuhan 430072,Hubei,China;

2.School of Computer and Information Science,Hubei Engineering University,Xiaogan 432000,Hubei,China)

Abstract:In order to cope with Ad hoc networks consisting of smart mobile communication devices that support rich media applications with Internet connectivity, a novel context-aware energy-efficient routing(CAER) algorithm is proposed. The algorithm introduces a context-aware self-learning solution to monitor context information in the operation process of devices, calculates energy utility imposed by various applications in nodes, and then synthetically utilizes the context information containing application-related energy utility, remaining energy and signal strength to make routing decisions in an adaptive way. By using this algorithm, energy is saved for mobile nodes with limited resources. Simulated results show that, in comparison with some routing protocols, CAER performs more effectively on the energy efficiency and lifetime of network, and reduces the delay overhead of network at the same time.

Key words: Ad hoc networks; context awareness;energy efficiency;routing algorithms;application software