无源感知网络中能耗和延迟平衡的机会路由协议∗
2019-10-28高宏超陈晓江汤战勇房鼎益
高宏超 , 陈晓江,2 , 徐 丹,2 , 彭 瑶,2 , 汤战勇,2 , 房鼎益,2
1(西北大学 信息科学与技术学院,陕西 西安 710127)
2(陕西省无源物联网国际联合研究中心(西北大学),陕西 西安 710127)
目前,感知网络中绝大部分感知节点是有源节点,即采用电池供电[1].于是,电池能量耗尽就会导致感知网络工作异常或者所获信息失真.因此,节能降耗以延长感知节点乃至感知网络的工作时间,成为一个重要的研究课题.现有的在低功耗感知元器件、低功耗处理模块芯片、低功耗通信等方面技术的不断发展,在很大程度上缓解了节点能量有限性问题,然而,它们无法从根本上解决感知节点能量耗竭导致节点失效以及感知网络异常这一难题.而且在一些特殊的应用中,如在火山监测预警系统这样的自然条件恶劣的野外环境中[2],或者军事作战中要监视敌方行动这样的需求,有些待监测本体如农作物需要在24 小时全天候监控[3]等场景下,由于环境具有监测范围大、部署区域偏远、难以进行长时间的人力监测等特点,我们无法定期更换布置在恶劣环境或敌对环境中的感知节点的电池.因此,解决感知节点不因电池电量耗竭而停止工作,一直是需要解决的问题.
近年来,无源感知网络研究的兴起给感知网络带来了新的发展机遇,为解决节点电量有限问题带来了曙光.这种网络的主要特点是:(1) 网络中感知节点自身不携带电池,节点通过能量捕获技术将环境中的能源充分利用,来补充自己的能耗,本文中将这类节点称为能量收集型节点,即无源节点;(2) 无源感知网络中的感知节点具有低功耗的感知模块、处理模块以及低能耗通信协议,能够完成特定的感知和数据传输任务.利用能量收集型节点的特性,无源感知网络能够获得更长的生存周期,从而更好地完成长期监测型任务.
根据无源网络的特点,节点可以通过能量收集技术[4],利用存在于人们周围的可利用的能源,如光能、热能、风能、电磁波等,周期性地为自己供电,以保证其正常工作.然而,无源节点在每一个周期内所捕获的能量远远小于有源节点中电池所提供的能量,因此,如何在节点所获能量如此小的无源网络中降低节点能耗,以保证节点足以支撑自身顺利完成数据传输的过程,成为亟需解决的问题.再者,网络延迟的问题一直是有源网络中致力于要解决的挑战,在无源网络中也不例外.如在火山监测预警系统中,因为数据传输的长时间延迟而导致没有及时发现险情,就会造成人员伤害及重大财产损失等严重后果.但是,无源节点每一次捕获的能量和电池所提供的能量有很大差别,已有的用于传统有源网络中降低延迟的方法不能直接用在无源网络中.因此,在节点能够持续收集能量,但每一次所捕获的能量都非常小的约束下去提高网络的延迟性能,以满足在无源感知网络中的应用需求很有必要.
然而,现有的路由协议在应用于无源感知网络环境时,大多缺乏兼顾能耗和延迟性能的考虑.如何设计一种在无源网络中能够兼顾能耗和延迟的合理的路由协议,尽可能低地降低节点能耗的同时降低网络延迟,是本文所面临的挑战.因此,本文提出能耗和延迟平衡的机会路由协议(balance of energy and delay opportunistic routing protocol,简称EDOR).该协议通过提出节点能耗模型,并考虑转发节点的邻居节点占空比的综合影响来进行路由决策,获得能耗和延迟平衡的良好效果,并提出合理的退避策略实现数据包被单一转发节点转发,来减少通信过程中碰撞带来的能量和时间的消耗,减少网络中无效的数据副本数量,延长网络生存周期和提高数据传输效率,以完成在自然条件恶劣的野外环境中的监测任务.
本文的贡献在于分析了在无源感知网络中所面临的挑战是兼顾能耗和延迟,即在尽可能降低网络中能耗的同时,如何合理地权衡考虑延迟问题,以提高数据的传输效率,使得网络中的节点达到能耗和延迟平衡的工作状态.而且,针对这一挑战提出了能耗和延迟平衡的机会路由协议EDOR.
1 相关研究
近年来,科研人员在能量收集技术方面展开了研究.相比于太阳能、风能等能源,泛在的电磁波是未来无源感知网络的最主要能量来源之一.科研人员对如何从泛在的电磁波中获取能量这一问题有了一些研究成果.例如,研究人员在射频识别(RFID)系统[5]中RFID 阅读器发送射频波给周围RFID 标签时,RFID 标签通过捕获来自阅读器的射频能量来驱动内置微芯片工作,并通过调制反射电磁波,将其自身ID 调制在反射电磁波中发送给阅读器.2007 年,Sample 等人开发了无线识别和感知平台(wireless identification sensing platform,简称WISP)[6,7],它是第一个以射频读取器的射频信号为能量源、且能够通过反射电磁波将所感知到的数据回复给射频读取器.2011 年,Vyas 等人设计了能够捕获470MHz～570MHz 频段射频能量的电路;用超级电容给微控制器和无线收发器供电,以实现能够无源自主感知和自主发送数据的无线传感器[8].2013 年,Parks 等人研究了从无线蜂窝射频信号和电视广播射频信号中捕获能量的技术,设计出射频能量捕获电路,其测试结果表明:所设计的基于能量捕获的低功耗传感节点在距离发送功率为1mW 的电视塔约10km 范围内能够正常工作[9].Liu 等人进一步研究了无源节点之间的通信技术,使无源节点能够以泛在射频作为唯一的能量源来获取能量,且通过控制射频信号的反射给邻近无源节点传输数据,实现了1Kbps 传输速率[10].
由此可见,从周围泛在的电磁波中捕获能量以支持无源感知节点工作,已取得了一些成果.然而,它们无法直接应用于无源感知网络,其主要原因有两点.其一,无源感知节点在捕获能量时存在着瓶颈:储能单元(如电容)只能储存非常有限的电量,一旦电容储存满电量,就无法继续捕获能量;同时,泛在的电磁波信号强度低导致充电过程非常缓慢;其二,感知节点的主要任务是感知环境变化,尤其是捕捉突发事件所产生的物理量,如火灾、泥石流等自然灾害等,对网络延迟性能有很高的要求.因此,需要设计合理的路由协议,以实现无源网络的感知.
传统的确定性路由协议在应对无线链路时存在诸多限制,其固定的路由选择可能会因为无线链路的不稳定性而造成严重的性能下降.因此,为了克服确定性路由协议的诸多局限性,机会路由策略被越来越广泛地使用[11].这类协议充分利用广播特性,使得在解决不可靠链路方面相比传统路由有着得天独厚的优势.该协议使得节点的转发选择不再固定,而是很多下一跳节点都可能进行转发,从而使得网络性能在能耗、延迟等方面都有所提升.
现有的机会路由协议大多应用在有源节点网络中,并在发展过程中逐渐形成了五大类别,分别是基于地理信息类、链路状态感知类、随机类、基于图论和概率思想类以及跨层设定类.基于地理信息类的机会路由协议,如DTRP[12],LinGo[13]以及COR[14]等协议,利用地理定位信息克服传感网络中的基础设备不足的问题.链路状态感知类的机会路由协议利用无线传输的天然广播特性,通过某种计算标准来交换评估链路质量信息并作为转发决策来提升包传输的可靠性,MORE[15]和CCACK[16]等协议都是基于这种思路设计的.而随机类机会路由协议则是为了应对移动节点的情况,这种网络环境下节点选择转发候选节点时,很难判断究竟选择哪个候选节点可以得到低能耗或者延迟,因此采用随机的策略如OPF[17]以及OOF[18]等策略.随着前3 种策略的机会路由协议的发展,机会路由算法慢慢成熟.基于图论和概率思想的机会路由算法是近年来受到关注的新思路,通过结合一些计算机领域的新的研究点来提升协议的性能,例如基于图论研究的MAP[19]以及基于学习的ORL[20]协议等.最后一类使用跨层策略的机会路由算法则利用底层的信息来辅助路由决策,例如利用物理层信息的EEOR[21]和HS-OR[22]协议、利用MAC 层信息的ORCD[23]和ORW[24]以及利用物理层和MAC 层两层信息的CL-EE[25]和SCAD[26]协议,这些机会路由协议通过利用下层的关键信息来辅助决策,往往能够取得很好的能耗或者延迟方面的性能.
然而,应用于传统使用电池的传感器网络的路由协议虽然能够很好地解决有源网络中的能耗和延迟问题,但却不能把它们直接应用到无源网络中来,因为这些方法未能充分考虑无源感知网络的下述因素:(1) 无源节点每一次所捕获的能量非常小,这使得节点可以用于探路以及发送数据包的能量极为受限,因此需要尽可能地降低能耗,以确保节点所获得的能量足以支撑其完成数据传输的任务;(2) 在一些无法按期更换电池的应用中,对数据的实时性要求较高,还要提高网络的延迟性能,否则可能造成严重后果.鉴于此,需要设计适用于无源感知网络的路由协议.而现有的应用于无源感知网络的机会路由协议并不多,并且由于能量收集型节点能级的不稳定以及相对较长的生存周期,其应用时的侧重点和设计思路也有所区别[27].例如,文献[28]提出的EoR 协议就是在ORW 协议的基础上进行改进,使其适用于无源感知网络的特点,并取得了较好的延迟效果;文献[29]提出的TPGFPlus 协议同样利用跨层思想降低了延迟;文献[30]提出的OR-AHaD 协议在无源感知网络中取得了较低的能耗效果;文献[31]中提出的协议实现了处理不同延迟要求包的机会路由协议.所以,本文要设计一种适用于无源感知网络的兼顾低延迟和低能耗特性的路由协议.
2 能耗和延迟平衡的机会路由协议EDOR
在无源感知网络中,能量不再是唯一关注的因素,对延迟性能的提升,将会使节点向基站发送数据时获得更高的效率.但现有的路由协议在应用于无源节点的网络环境时,大多缺乏兼顾能耗和延迟性能的考虑,因此,本节提出能耗和延迟平衡的机会路由协议(EDOR).该协议通过分析节点通信的过程来估算节点的预期能耗值,让节点选择令自己能耗较低的邻居节点作为转发候选节点.在最终确定转发节点时,本协议通过结合候选节点下一跳邻居节点的占空比信息来进行决策,使得发送节点选择能更快将数据转发出去的候选节点来降低延迟,获得了能耗和延迟平衡的良好效果;然后提出合理的退避策略,实现了数据包被单一转发节点转发,减少了网络中无效的数据副本数量.
2.1 EDOR协议设计
2.1.1 机会路由策略
为了减少节点的能耗和延迟,不能使用确定性的路由方法来固定选择某一个节点作为数据转发的唯一选择.因为随着网络环境的变化以及无线链路状态的不稳定性,如果选定的唯一下一跳节点与当前发送节点的工作周期恰好交错开,等待过程会增加节点的能耗和延迟;若节点在等待过程中持续发送探测包消耗了过多能量,可能造成将无源节点上一个周期收集的能量消耗殆尽,使节点得重新进入能量收集阶段而无法进行通信.因此,我们考虑使用机会路由策略.
机会路由的主要思路可以总结如下:用Cu表示节点u使用某种机会路由策略向目标节点发包时预计所需消耗的能量,初始阶段,目标节点的期望能耗值设定为0,其他所有节点的期望能耗值设定为正无穷.同基于距离向量的路由机制类似,机会路由协议机制中,每个节点的期望能耗值以及转发列表将会周期性地计算并且更新.当一个节点准备向目的节点发送或者转发包时,该节点只需简单地将数据包朝着基站方向广播出去,并利用一定的选择策略选择转发节点,从而完成整个发送过程[32].如图1 所示.
Fig.1 Model of opportunistic routing图1 机会路由传输实例
假定发送节点经过两跳到达目标节点,并且发送节点的下一跳范围内有v1,v2,…,vn共n个节点.从发送节点到下一跳每个节点的传输错误率都是en,而下一跳的所有节点到目标节点都是完美链路,即传输错误概率都是0.对于传统路由方法而言,每次传输时,源节点都会选择固定的节点,比如vi作为下一跳进行传输,则根据假设整个传输成功所需要的预期次数为.而如果使用机会路由策略,由于发送节点会监听所有下一跳节点的状态,只要至少有1 个节点醒来就立刻传输数据,因此传输成功需要预期次数降到了(证明过程见下).尤其当e值越接近于1,n值也较大时,两种策略下的预期传输次数差距也会越大,消耗能量的差距也就越大.也就是说,机会路由对于链路质量较差并且节点个数较多的网络环境性能有着较明显的提升.同样,如果下一跳中哪个节点最先醒来进入工作状态,机会路由就最先将其选择为转发节点的话,整个转发过程的延迟相较于固定节点也会显著降低.
证明:假设从发送节点到下一跳每个节点的传输错误率是e,则传输成功率为1−e,在传统路由方法中,传输成功的预期次数即为.当使用机会路由策略时,只要有至少1 个节点醒来时就会立刻传输数据,则传输失败的概率为en,因此传输成功所需要的预期次数降低为.证明完毕. □
2.1.2 EDOR 协议设计思路
现有的机会路由协议,有些仅从能耗角度出发,虽然取得了不错的效果,但是完全舍弃了延迟;有些协议则从延迟入手,却忽略了能耗的计算,这些都不符合使用能量收集型节点的网络特点.本文提出一种适用于异构占空比网络下的兼顾延迟和能耗问题的路由协议,该协议整体的设计思路如图2 所示.
Fig.2 Overview of the EDOR protocol图2 EDOR 协议设计思路
发送节点通过广播探测包获取周围邻居节点反馈的关于能耗的信息,确定转发候选集合.候选集中的节点则根据考虑了延迟因素的通信代价计算标准来决定自己的退避时间,退避时间短的节点即为选中的转发节点,从而实现发送节点选择使自己能耗和延迟性能平衡的转发节点.
2.2 能耗和延迟的影响因素
2.2.1 网络模型
为了保证整个网络有着稳定和合适的任务循环周期,同时为了不同类型的节点完成不同的数据采集和传输任务,本文设定所有节点拥有相同的总周期长度L和各自不同的占空比Dv.
设定传感网中所有的节点都有一个独一无二的id 号i∈[1,n].在野外部署的多跳无线网络环境下,本文抽象出一个图的模型,并将其表示为G=(V,E),其中,V代表网络中n个节点组成的集合,E表示两个可以直接通信的节点之间的链路.比如,对网络中任意两个可以直接通信的节点u∈V,v∈V而言,(u,v)代表两个节点间的一条链路,每条链路都有一个非负的权值,表示为w(u,v),这个权值代表了节点u给节点v发包成功所耗费的能量,称其为传输功率.这个值根据所处监测环境的不同,以及能量收集型节点能量源的不同而有所区别.由于当节点u以不同的传输功率进行通信时,其通信范围会不同,进而单跳范围内的邻居节点个数也会有所差别,因此这种情况下,路由更新的代价将会增大,并且网络的通信会不稳定.因此对节点i,为了整个监测网络的稳定传输,假定在其通信过程中拥有的传输功率w保持不变.本文以NW(u)用来表示当节点u以w能量进行通信时它的邻居节点的集合,为了简化起见,当节点以设定好的传输功率进行通信时,省略下标W,记为N(u).另外,现实环境部署情况下节点间的通信链路不可能是完美链路,将每条链路(u,v)的传输不成功的概率表示为euv.通过以上假设可以得出:对每一个节点u,其传输一次至少会消耗w(u,v)的能量,并且传输成功的概率为1−euv.为了提升网络性能,接下来,本文将从影响能耗和延迟的因素对协议的设计进行分析.
2.2.2 节点的预期能耗
虽然无源节点的生存周期得到显著延长,但并不意味着其能量可以无限使用.在路由过程中,选择能量消耗少的节点更有利于网络的长期生存.我们首先研究了将节点发包时的预期能耗计算标准(expected consumed cost,简称ECC)来作为发送节点选择转发候选节点的依据.
机会路由通信过程中,考虑从当前节点的下一跳节点中有节点收到包时到转发出去为止这一整段过程,主要分为以下两个部分:一部分为当前节点向其转发候选集广播探测包发现候选节点时,其下一跳节点中至少有1 个节点接收到这一过程,由于受链路质量以及能量收集型节点剩余电量的影响,可能出现下一跳节点均未成功接收发送节点信息的情况,该部分能耗称为失败代价;另一部分则是转发候选集中至少有1 个节点成功将该包转发出去这一过程,该过程的能耗称为转发代价.针对这两个过程,本文将分别讨论其能耗的计算标准.
(1) 失败代价
如果U表示一个节点集合,那么Usort表示一个节点集合,其中所包含的节点与U相同,但其中的元素排布顺序按照每个节点向某一个固定的目标节点发包时的期望能耗升序排列.假定Fwd(u)表示节点u的转发候选集(该转发候选集的选择策略将在下一节进行讨论),那么Fwdsort(u)表示候选集中的点已经按照其期望能耗升序排列.例如,如果i 其中,vi表示属于集合Fwdsort(u)中的任意一个节点,SumFwd表示Fwdsort(u)包含的节点个数. 当前节点u是以w的能量功率进行每次通信过程,即发包消耗的能量为w.令表示节点u发包给候选集中至少1 个节点预计消耗的能量,由于w消耗能量的过程是在该节点发送的包成功被其转发候选集中节点接收到的情况下假定的,因此该过程中实际消耗的能量为 (2) 转发代价 当前节点的候选集中有至少1 个节点成功收到发送的包后,这时进入了转发阶段.这个阶段经历的过程如下:首先选择候选集中优先级最高的节点作为下一跳完成转发过程(候选集的节点选取和建立过程以及候选集中节点优先级的确定方法将在下一节详细讨论),如果转发未能成功完成,在不考虑重传的情况下,则继续选择优先级第二高节点进行转发,以此类推,直到至少有1 个候选节点完成了转发过程.同时,在节点转发过程中,转发代价中已经包含了节点由于占空比导致的等待和空闲监听带来的消耗.因为当前节点向下一跳转发数据时,当前节点的工作周期需要与下一跳节点的工作周期对应上,若两个节点的工作周期没有对接上时,当前节点就会等待下一跳节点醒来时,再完成转发过程. 假定节点u的转发候选集已经按照其中节点的预期能耗值按升序排列得到了含有优先级的转发候选集,则首先选择其中的第1 个节点进行转发,如果没有成功,则选择第2 个节点,依次类推.由此可以得到第1 个节点v1将以的概率成功转发,并消耗的能量,节点v2则将以的概率成功转发并消耗的能量.由于该过程同样建立在候选集中至少有1 个节点成功接收的基础上,则该过程中预期消耗的能量可通过公式(3)计算. 令Cu表示节点u通过转发候选集发包过程中产生的预期能量,那么通过前文分析可知,即 2.2.3 转发候选集的选择策略 机会路由过程中,合适的转发候选集的选择策略将会对网络性能的提升产生重要影响.本节提出一个基于ECC值的转发候选集选择策略. 首先,当前节点u的转发候选集合是其邻居节点集的子集,即Fwd(u)⊂N(u).转发候选集合中节点的数目的增加对发送节点的预期能耗将会产生以下影响. (1) 增加候选集中的节点数目,将会使得当前发送节点的转发候选变多,从而提高至少1 个节点接收到探测信息的可能性,对发送节点的失败代价产生正面的收益. (2) 转发候选集中节点数目过多,也可能会将与当前发送节点通信链路失败率较高的节点或其本身预期能耗较高的节点加入转发的候选集,导致通信质量不好的节点加入候选,如果发送节点选择其作为转发节点,将会对转发代价带来负面的收益. 因此,如何在当前节点的邻居节点集中选择合适的节点加入转发候选集,是降低节点能耗的关键过程. 在确定转发候选集的过程中,已知当前节点u的邻居节点集N(u),该集合中每个点的预期能耗值以及节点u与每一个邻居节点间传输成功的概率,于是,当前的问题转化为如何找到合适的转发候选集Fwd(u)⊂N(u),使得发送节点的预期能耗Cu值最小.假设当前节点u的邻居集中的节点已经按照其预期能耗值进行了升序排列,并将这个排好后的邻居集记为Nsort(u),于是可以得到如下定理. 定理1.对当前节点u而言,如果现在起邻居集中有一个节点vk不属于当前已经确定的转发候选集,即vk∉Fwdsort(u),那么如果,则 定理2.对当前节点u而言,如果现在起邻居集中有一个节点vk不属于当前已经确定的转发候选集,即vk∉Fwdsort(u),那么,如果,则Cu(Fwdsort(u)∪{vk})>Cu. 证明:根据公式(4)可知,节点u当前的ECC值为 尝试加入邻居节点vk后,节点u的ECC值更新为 于是,两项相减可得: 则通分后可得: 两个定理共同指出,为了使当前发送节点的ECC最小而判断一个邻居节点是否可以加入当前节点的转发候选集时,根据自身不断更新的ECC值即可:如果该邻居节点的ECC值小于当前候选节点集情况下确定的发送节点的ECC值,则加入该邻居节点到候选集中会使发送节点的ECC值变小,所以策略上应该将该邻居节点加入转发候选集;反之,当该邻居节点的ECC值大于当前候选节点集情况下确定的发送节点的ECC值,则不加入该节点.由于Nsort(u)中的节点已经按照ECC值升序排列,因此当发送节点遇到第1 个大于当前ECC值的邻居节点时,转发候选集的构建便宣告完毕.下面是创建当前发送节点u的候选集的算法描述,通过该算法确定的转发候选集会将通信过程中预期能耗较大的节点剔除,使得当前节点在能耗较低的邻居节点中选择转发节点. 算法1.构建转发候选集. 输入:N(u)中所有节点的EEC值. 输出:当前节点的EEC值Cu以及转发候选集Fwdsort(u). 显然,该算法中存在一个以邻居节点个数为长度的循环,并且节点最多需要保存所有邻居节点,因此,该算法的时间复杂度和空间复杂度均为O(SumFwd). 2.2.4 占空比对延迟的影响 为了降低节点能耗的同时降低延迟,在利用ECC值完成了转发候选集的构建之后,本协议还需要考虑节点运行的整个过程中,影响延迟的因素. 大多数文献和现有机会路由方法中考虑节点能耗和延迟时只从通信过程入手,分析从下一跳节点中至少有1 个节点收到包时到转发出去为止这一段过程中,就是上一节中讨论过的组成ECC度量标准的两个部分.然而当考虑如下情况时:一个节点跟另一个节点进行通信,如果其工作周期与另一个节点的工作周期没有对接上,那么发送节点就得不停地发探测包等待该节点醒,这样会增加网络延迟.这一部分可以称为等待代价,如图3 所示,发送节点前3 次探测,接收节点都处于休眠状态,直到探测到第4 次才成功遇上接收节点的工作周期,因此整个传输分为前后两部分过程.本次传输的延迟也如图3 所示分为等待过程和通信过程两部分.文献[22]中提出了一种考虑等待代价的路由协议,其思路是利用MAC 信息进行跨层处理,本文参考其方法并做出了改进. Fig.3 Waiting cost during transmission图3 节点发送过程中等待代价示意图 当前节点发送数据时,由于使用了基于CSMA 的MAC 层协议,因此必须通过探测的方式来进行通信.然而当真正选择某个节点进行转发时,考虑该节点获得数据后再向后进行转发的过程,显然是该转发节点的邻居节点的工作周期覆盖越全面,该转发节点发送数据时的等待时间就越短,延迟就越低,如图4 所示. Fig.4 Waiting costs in the network layer图4 网络层中的等待代价示例 当前节点有两个邻居节点A和B,而A,B分别拥有两个和3 个下一跳的邻居节点,其中,A的两个邻居节点的占空比分别为50%和60%,B的3 个候选节点的占空比为10%,20%和10%,并且工作周期在总周期中的位置如图中所示.因此可以看出,如果选择A节点进行转发,那么A节点在下一跳时可以很快将数据继续转发下去(因为A节点的邻居节点的占空比之和达到了100%);如果选择B节点进行转发,则意味着B拿到数据后有70%的时间是不能直接转发的,必须等待候选节点的苏醒(因为B节点邻居节点之间除去重叠部分,其占空比之和只有30%).因此,如果按照ECC的值排序,B的预期能耗小于A,从而优先选择B进行转发的话仅仅是在当前情况下的最优选择,而在进行到下一跳的转发过程时,B的选择代价是大于A的.因此当转发候选集确定后,具体选择哪个节点进行转发,本文协议考虑了通过转发候选节点的邻居节点占空比之和的判断因素. 在节点的每个周期中,易知其周期性醒来工作的时间为Twake=L×Du.假设使用表示转发候选集中节点i和j醒来时间的重叠部分,那么对于该过程的等待代价而言,所有邻居节点除过重叠部分的占空比之和越大,该节点进行转发时的等待代价就越低.可以通过公式(10)计算对当前节点u的所有邻居节点的有效工作时间占总周期的比例RoFu: 在上式的分子表示的时间段内,由于邻居节点中总有节点是处于唤醒状态,因此在该时间段内,当前节点总是能够立刻将数据发送出去.而等待阶段则由于没有任何一个候选节点处于唤醒状态,故当前节点的等待时间所占总周期的比例RoWu为 可以看出,转发候选节点的RoWu越小,其等待代价越小,节点发送数据的延迟也就越小. 2.3.1 协议概述 上一小节中讨论了在异构占空比网络中影响节点能耗和延迟的因素,为了达到平衡能耗和延迟性能的目的,本节提出综合能耗和延迟代价的机会路由协议. 本协议主要分为探测邻居节点、构建转发候选集以及选择转发节点这几个过程.其中,探测邻居节点即为广播探测包获取邻居节点ECC值以及RoW值的过程,而转发候选集将根据第2.3.3 节中提出的转发候选集选择策略来构建.接下来,本节将重点讨论选择转发节点的过程. 2.3.2 转发代价Cost 本协议使用Cost值作为节点的通信代价来作为转发节点的选择标准.考虑转发代价时,为了实现平衡能耗和延迟的目标,该值将通过各个转发候选节点的ECC值以及RoWu来联合确定. RoWu的值显然处于[0,1]之间,因此当候选集确定后选择转发节点时,也必须将传输代价的值归一化到[0,1]区间内.假设由算法1 确定的转发候选集中存在n个候选节点,其ECC值分别为,则对转发候选节点vi而言,通过公式(12)将其进行归一化处理. 于是,真正衡量转发候选节点通信代价标准的Cost值将由公式(13)计算. 其中,系数a的数值将决定能耗因素和延迟因素的占比,将在评估与实验章节通过仿真实验来具体验证确定.转发候选集中Cost值最低的节点,即为应该选择的转发节点. 2.3.3 转发节点退避策略 这一节中,本协议讨论当前发送节点如何将数据单播给通过上一节方法选定的转发候选节点,从而减少网络中无效数据副本的数量.利用无线传感网络的广播特性,当前节点可以很容易将数据包发送给转发候选集中的节点,但这样也会造成潜在的问题:如果一个数据包被很多候选节点收到而没有合适的退避处理策略的话,这些候选节点将都给发送节点回复ACK,会大大提升碰撞的可能性,造成不必要的能量消耗;即便合理地使用了退避策略,如果一个候选节点不知道已经有其他候选节点完成了转发而选择继续转发,就会使同一个数据包在网络中存在很多不必要的副本,造成能量浪费和无效吞吐.针对这些问题,本协议提出基于选择策略度量值Cost的退避策略以及ACK 压制策略. 为了减少碰撞带来的能量和时间消耗,本协议利用Cost值设计一种退避策略.当发送节点确定了自己的转发候选集并计算出ECC值后,该节点发送数据时将转发候选集中最大的ECC值Cmax以及转发候选集中所有节点的ECC值之和包含在内.收到数据节点通过与自身的ECC值进行对比:如果,则该邻居节点将自己选为转发候选节点,并在回复ACK 之前执行退避过程.该节点的退避时间应该同Cost值成正比,假设Bmax是MAC 层预设的最大的随机退避时间,那么对候选集中的节点vi,其退避时间由公式(14)计算: 通过这种退避机制,候选集中代价最小的节点将会退避最短的时间,即其拥有了最高的转发优先级.当其退避时间结束后,将优先广播ACK 信息.这样,当发送节点接收到第1 个ACK 信息时,得知其数据包已经被成功接收.而其他收到该数据包的转发候选节点由于退避时间较长,在其退避时间内如果收到了来自其他节点的数据包ACK 信息,则该节点将收到的数据包丢弃,不再进行转发和回复.通过这样的退避以及ACK 压制策略,本协议就实现了发送节点把数据单播给某一选定的转发节点,从而减少了该过程中额外的能量消耗. 2.3.4 网络初始化 在网络第1 次启动时,整个网络的初始建立过程将从基站(sink)开始到边缘节点,直到每一个节点都完成自身的初始化过程后进入休眠状态为止.每个节点在其初始化阶段保持工作状态不休眠,直到完成该节点的初始化过程后将休眠一整个时间周期L,之后,将根据其设定好的占空比开始正常的工作周期. 当网络初始化开始时,基站首先向全网发送广播信息.广播信息中包括其占空比D、ECC值C和其等待代价度量标准RoW(对基站而言,由于其是组网的第1 个节点并且不休眠,因此Dsink=100%,Csink=0,RoWsink=0).因为sink 是该网络中所有数据包的归宿,因此收到其广播包的节点都将其视为自己的下一跳以及转发唯一的转发候选节点,并据此计算自己相应的ECC值.计算完毕后,为了防止碰撞消耗不必要的能量,每个节点随机退避一个时间后,继续将含有自己占空比和ECC值信息的包广播出去.节点广播之后,将会监听一段时间(T1)来确认自己的包是否被至少1 个节点接收到,如果没有问题,节点将休眠一整个周期. 对于网络中距离汇聚节点两跳及以上的节点u,当其接受到其他节点广播包中的信息时,将其id 号加入到自己的邻居节点集N(u).当经过一段监听时间(T2)不再收到广播信息时,利用前文中提出的转发候选集构建方案,将N(u)中的节点按C值排序后依次尝试加入并最终形成候选集Fwdsort(u),同时计算出该转发候选集情况下当前节点的预期能耗值Cu,并根据当前时间和广播包中的占空比信息计算出节点的RoWu,以便为之后的转发决策服务.通过每个广播包,可以计算该发包节点(即转发候选节点)下次醒来的时间为 则其工作时间的范围即为 通过此计算方法,还可以估算出不同发送节点占空比的重叠部分,从而计算出当前转发候选集情况下节点u的RoWu值.之后,当前节点同样随机退避一个时间之后将自己的占空比D、ECC值C及其等待代价度量标准RoW值加入包中广播出去,广播完成后,使用同样的机制监听一段时间(T1)进入休眠.同理,网络中每个节点在网络初始化过程中都执行这样一整套流程后,整个网络初始化过程结束.这时,网络中每个节点的转发候选集以及等待代价度量标准RoWu都得以确定. 2.3.5 网络通信过程 当网络的初始化过程完成后,网络中的节点将陆续醒来进行发送或转发数据包的工作.当一个节点有数据包要发送时,首先广播探测包,然后利用收到回复的节点中根据其ECC值参考前文提出的算法选择是否加入转发候选集.由于初始化过程结束后网络中节点的ECC值是按照远离汇聚节点逐渐增大而排布的,因此根据算法中加入候选集的节点都是ECC值小于当前值这一规则,可以避免将上一跳的节点加入候选集而形成路由环路.当前节点也随着候选集中节点的不断加入而重新计算自己的C值,直到不再有可以降低本身ECC值的节点出现时,当前发送节点的转发候选集就确定了.转发候选集的确定会使一部分能耗代价较高的邻居节点被排除,这样可以降低节点之间通信的能耗.之后,转发候选节点通过公式(13)计算出的Cost值执行退避,从而完成转发过程.在此过程中,把转发数据的延迟降到最小.如图5 所示为一个节点通信过程示例. Fig.5 Example of communication process图5 通信过程示例 如图5 所示,Sender 为发送节点,其含有3 个邻居节点A,B,C;同时,节点A有3 个邻居节点B,D和E,节点B有邻居节点A,C,E和F,节点C的邻居节点为B,F,G,H.Sender 首先广播探测包,假设得到节点A,B,C回复的各自的ECC值分别为1,1.5 和3.假设发送节点同A,B,C之间链路的错误率都为0.5,而发送功率为1. (1) Sender 根据ECC值将A,B,C节点从小到大排序,首先将节点A加入转发候选集,并计算出自己当前的ECC值为3;之后比较节点B的ECC值小于3,于是将B也加入转发候选集,重新计算自己的ECC值为2.25;此时发现节点C的ECC值大于当前计算出的ECC值,于是不将C值加入,转发候选集构建结束,将能耗代价较高的邻居节点C被排除,降低节点之间通信的能耗. (2) Sender 将转发候选集中节点最大的ECC值1.5 作为阈值和所有ECC值之和2.5 加入数据包进行广播,收到数据包的节点A,B,C将自己的ECC值与阈值1.5 进行对比,其中,节点A,B发现自己的ECC值小于等于该阈值,于是将自己视为转发节点,准备执行退避后转发,节点C则丢弃该数据包. (3) 节点A,B根据退避计算公式计算自己需要退避的时间,如果节点A退避时间短,则首先广播ACK,Sender 节点收到ACK 后得知转发成功;而节点B收到A的ACK 则得知自己的转发优先级较低,于是丢弃收到的数据包,使得转发数据的延迟最短,实现能耗和延迟的平衡. 在该过程中,单个节点的占空比虽然不会发生变化,但是由于网络中链路质量有可能改变,从而造成节点的邻居节点集可能发生变化;并且由于时钟累计后出现误差现象的存在,节点的邻居节点工作周期的重叠部分也可能发生变化,这些都可能改变一个节点的RoW值,从而影响路由决策.为了解决这个问题,本协议设计了更新节点RoW值的策略:初始化阶段时,邻居节点回复发送节点时会捎带自己的占空比等信息;而在网络结束初始化过程开始正常运行时,邻居节点将在回复的信息中添加一项Tpass,代表其睡醒后经过的时间;而发送节点接收到后,可以根据自身的时钟来修正时钟漂移带来的误差. 为了验证所提出的路由协议的有效性,本文利用Omnet++仿真平台在MAC 层使用CSMA 的基础上对EDOR 协议进行了多组实验.由于能量收集型节点的能量收集过程对上层来说是隐藏的,并且该过程也不是本协议研究的范畴,因此本文使用占空比较高的节点模拟代替能量收集型节点,并研究所提出的EDOR 协议的能耗和延迟性能. 本文对不同数量、不同占空比类型的节点组成的网络环境都进行了测试.由于本协议适用于拥有相对较高占空比的能量收集型节点,因此将使用4 种不同占空比类型的节点,分别是占空比为40%,30%,20%以及低于10%的节点.实验中使用N-X%-Y%-Z%分别表示节点的总个数为N、占空比为40%的节点占比为X%、30%的占比为Y%、20%的占比为Z%、其余为占空比低于10%的节点.所有节点的总周期长度L一致,其他一些网络设置的关键参数见表1. Table 1 Settings of network parameter表1 网络参数设置 为了确定转发候选节点选择标准Cost值计算公式中的系数a,本实验将系数a在[0,1]的区间内每次变化0.1,从而产生11 组对比数据;同时,利用OMNeT++平台的拓扑产生器随机产生6 组不同规模和节点类型的拓扑,见表2. Table 2 Example of test networking表2 测试网络示例 本文首先对端到端延迟进行了仿真实验,得到了如图6 所示的结果.从图中可以看出,随着Cost值计算公式中系数a取值的不断增大,不同的网络拓扑均表现出延迟上升的总体趋势.这时,因为随着系数a取值的增大,RoW值在Cost中的占比就越来越小,因此在对转发候选集中的节点进行选择时,候选节点的邻居节点占空比之和对决策的影响就越小,发送节点更倾向于选择能耗较小而不是延迟较低的节点进行转发,因而端到端延迟随之变大.同时可以看出,随着节点个数的增多,每个节点邻居节点数目的增多,网络中平均延迟的数值是在减小的.对于具有相同节点数目的网络T4,T5,T6,则随着网络中高占空比节点数目的增加使得通信节点之间工作周期相遇的概率提升,从而延迟减少. 对于节点的能量消耗问题,本实验使用发包的数量来模拟衡量.本文使6 组网络分别仿真相同的时间,在同样的时间跨度内,发包次数越多,代表节点处于工作状态的时间越长,进行的通信过程越多,从而能耗越大.结果如图7 所示. 从图7 中可以看出,随着系数a值的不断增大,Cost值计算中关于ECC值的占比不断上升,即发送节点在从转发候选集中选择转发节点时,会更倾向于能耗较少而不是延迟较低的节点进行转发.因此,节点平均发包数量整体在减少.同时还发现,在T1和T2的网络情况下,发包数量的下降并不明显.这是因为在网络中节点数量较少时,每个发送节点的邻居节点以及选定的转发候选中的节点数量都不会很多,在转发候选集选择过程中已经将能耗较大的节点排除在外的情况下,节点发包数量的变化并不明显.而随着网络规模的扩大,能耗下降的趋势就逐渐显现出来.从图中可以看出,随着网络中节点个数的增加,节点的平均能耗也会增加.这是由于随着邻居节点个数的增多,节点的通信频率增加造成的.T5,T6相比于T4则是随着网络中高占空比节点数量的增加,能耗相应增加. Fig.6 Average delay of end-to-end图6 端到端延迟平均值 Fig.7 Average number of packets图7 发包数量平均值 从两个图中可知,随着系数a的增大,节点的延迟和能耗的整体变化趋势是相反的,这符合前文的分析和设定.由于转发候选集的确定已经使得一部分能耗代价较高的邻居节点被排除,因此在从转发候选集中选择转发节点时,本协议更倾向于考虑降低延迟.从图中可以看出,a值处于[0,0.4]范围时,延迟相对处在较低水平,能耗则在a值取得0.2 开始,T4,T5,T6均出现较明显的能耗下降,因此本协议选择a值为0.2. 为了减少网络中无效的数据副本数量,本文协议设定了从转发候选集中选择单一节点进行转发的退避过程.对6 种随机网络拓扑,分别测试了每个数据包被转发的次数,以此来验证该退避过程对于确定单一转发节点的有效性.仿真结果如图8 所示. Fig.8 Average number of forwarding nodes per hop图8 每跳平均转发节点个数 从上图中可以看出,随着网络拓扑规模的增大,真正转发数据包的节点有所增加,但总体基本接近于一个.这时,由于虽然本文协议使用基于Cost值的退避来选择唯一转发节点,并且利用Cost值较小的节点,使用ACK压制了其他转发候选节点,但是因隐藏终端问题的存在,有可能被选中的转发节点发送的ACK 无法被所有转发候选节点收到,而误以为自己是被选中的转发节点.这种情况出现的次数随着网络规模的扩大、邻居节点数目的增多而增加,因此使得有些数据包可能会被两个节点转发.然而,因为在转发候选集的构建过程中已经排除了一部分邻居节点,剩余的加入转发候选集的节点彼此之间不在通信范围内的概率很低,所以出现两个转发节点的概率很低,两个以上的情况几乎没有.因此,本文协议基本实现了数据包单一转发的功能,从而有效减少了网络中的无用副本. 3.3.1 延迟比较 为了验证本协议(EDOR-Cost)的有效性,实验中对比了同样是机会路由的比较经典的ORW 协议(ORWETC)以及对其进行改进的EoR 协议(EoR-ETC),从平均延迟和平均能耗两方面,同样使用了6 种随机网络拓扑进行了对比实验. 本文对6 种网络拓扑下3 种方法的端到端延迟和单跳延迟进行了实验,结果如图9 和图10 所示. Fig.9 Comparison of the average end-to-end delay图9 平均端到端延迟比较 Fig.10 Comparison of average one-hop delay图10 平均单跳延迟比较 从两图中可以看出,无论是端到端延迟还是单跳延迟,本文提出协议的延迟都在ORW 和EoR 方法之间,并且更靠近延迟较低的EoR 方法.因为ORW 只是根据候选节点的下一跳邻居节点的个数来进行选择,相当于忽略了等待过程产生的代价,其选择的转发节点并不是下一跳转发时延迟较小的节点.而EoR 方法则充分考虑了节点自身和其转发候选节点占空比的情况,在进行选择时相比ORW 方法提升了延迟性能.本文的方法EDOR综合考虑了节点的能耗和延迟两方面因素,在平衡两者的同时,在延迟方面取得了接近EoR 方法的良好效果. 3.3.2 能耗比较 本文随机选取了网络拓扑T3来比较3 个协议的节点能耗.为了使得能耗的数值更贴近于数据收集网络的实际情况,选取基站收集到同样数量的数据包时,节点产生的平均能耗,即当基站收集到相同数量的数据包时,节点平均能耗更低的协议可以使得网络能够更好地完成收集任务.能量收集型节点的能量级别很低,节点一次发送或接收过程产生的能耗在10−1mA 甚至微安级别,本实验根据文献[33]中提供的参考,将节点进行一次发送和传输的能量消耗分别设定为0.56mW 和0.67mW 进行仿真实验,得到的结果如图11 所示. Fig.11 Comparison of average energy consumption图11 平均能耗比较 由上图可以看出,随着基站收集到的包的数量的增加,节点的能耗基本呈线性增加的趋势(前提是该节点拥有足够的能量).其中,EoR 方法由于减少了节点的平均等待时间,使得不用频繁地发送探测包或者监听信道,从而能耗情况也优于ORW 协议.而本协议由于能量模型的存在,转发候选集中选择的节点都向后转发时预计能量消耗较少的节点,因此取得了最优的能耗特性. 针对于无源感知网络,本文提出了基于综合能耗和延迟代价的机会路由协议,利用节点的预期能耗模型以及单一转发节点选择策略,平衡了节点的能耗和延迟.通过仿真实验,证明了本文提出的协议取得了良好的能耗和延迟效果,并且成功降低了网络中的无效数据副本数目.在实验方面,将研制自己的无源感知节点,考虑在HitchHike 的基础上做进一步的改进,参考WISP5 上的energy harvesting 部分的电路,使用能量收集技术,结合无线能量获取与太阳能,为系统构建专门的软件,通过指令集优化系统,节约能耗,对实验加以扩展.
2.3 EDOR协议原理
3 实验设计与分析
3.1 系数确定实验
3.2 单一转发节点验证实验
3.3 对比实验
4 总结与展望
