一种可控簇规模的能耗均衡路由协议的设计*

应可珍,杨志凯,周贤年,毛科技,陈庆章*

(1.浙江工业大学计算机科学与技术学院,杭州 310014;2.浙江财经大学东方学院,浙江 海宁 314408)

无线传感器网络是由部署在监测区域内大量廉价的微型传感器节点通过无线通讯的方式形成的多跳自组织网络,主要功能是数据采集及监测[1],其被广泛的应用于各个领域,如在林业方面监测森林的温湿度、光照强度;在农业方面监测大棚环境;在医疗方面可进行远程医疗和实时监护等[2-3]。一般传感器网络部署区域环境复杂,很难为传感器节点更换电池,在节点电源有限的情况下很容易死亡,尤其是大规模传感器网络需要采集转发大量的数据。在转发数据过程中某些传感器节点负载过大,能量消耗过快,最终导致无线传感器网络过早死亡,因此研究能耗均衡的路由协议有重要意义。

目前针对WSN路由协议的研究主要有两个方面,一种是链路式路由协议,另外一种是层次路由协议。链路式路由协议适合小规模的传感器网络,在大规模的传感器网络中使用链路式路由协议容易导致链路拥塞,而层次路由协议适用于大规模的传感器网络。分簇路由协议是层次路由协议的一种,如早期文献[4]提出的LEACH路由协议,采用随机分簇策略并且周期性簇头轮换,该协议对节点进行均匀分簇,簇内成员节点数量相同,因此理论上每个簇的平均消耗能量相同。该协议规定每个簇成员节点采集的数据通过一跳通讯发送给簇首节点,簇首节点直接与Sink节点通讯,由于网络中每个节点都可能出任簇首,所以达到了均衡网络能耗的目的,但是簇首需要直接与Sink节点进行通讯,这就导致距离Sink节点较远的簇首需要消耗大量的能量,而且需要传感器网络中每个节点都具有远程通讯能力,不适用与普通传感器网络。文献[5]针对传统的LEACH簇首选举方法进行改进,在选取簇首的过程中综合考虑了其剩余能量等因素,在能耗均衡性能上有优于传统的LEACH。文献[6]在传统LEACH协议的基础上选举出副簇首,使得簇首之间能耗均衡性更好,实验结果也验证了该方法能够延长网络的生存时间。文献[7]提出一种改进的LEACH协议(EE-LEACH),该路由协议在簇首选择时充分考虑了节点剩余能量并且采用簇首间多跳路由将采集的数据传输至基站,实验结果表明该协议在能量消耗和能量均衡性方面都优于传统的LEACH路由协议。

文献[8]针对LEACH协议的均匀分簇和簇首与Sink节点单跳通讯存在的问题,首次提出了非均匀分簇均衡网络能耗的思想UCS,簇间采用多跳通讯。UCS根据簇首期望转发负荷来调整簇规模,最终实现网络能耗均衡。文献[9]提出一种分区和分簇双层划分的路由协议,多个簇形成一个区,簇首将信息传输至区首,区首通过多跳将信息传输至Sink节点,在区划分和簇规模控制上,距离Sink节点越近,簇规模越小,该协议较好的均衡了网络能耗,但是该协议要求传感器节点的位置已知,因此不适用于普通传感器网络。节点位置已知的路由协议还有文献[10]提出的DEBUC协议,该协议利用节点位置计算距离Sink节点的距离,然后控制簇首的竞争半径从而控制簇规模大小。在簇首优化方面文献[11]利用PSO算法优化选择的簇首,提出了PSO-C分簇路由协议。文献[12-15]都研究了簇首竞争半径非均匀的分簇协议,但这些研究重点在如何分簇,对簇首之间多跳传输缺少研究,且上述的分簇路由研究中有些是基于节点位置已知的,并不适用于普通传感器网络,而有些则并没有充分考虑簇规模的问题,因此并不能较好的发挥能耗均衡作用。

基于目前已经取得的研究成果有待提高的部分,提出一种可控簇规模的能耗均衡路由协议。首先综合考虑节点的剩余能量、节点与邻居节点的链路质量、节点的度选择簇首节点,然后根据节点距离Sink节点的最短跳数控制簇首竞争半径,从而控制簇规模,接着利用虚拟力模型进行普通节点成簇,最后簇首通过多跳路由将采集的数据发送至Sink节点。该协议在簇首选举、簇规模控制和簇首间路由都充分考虑了负载均衡,实验结果验证了该协议具有较好的能耗均衡性。

1 网络定义与能耗模型

1.1 相关网络定义

①总共有N个传感器节点均匀部署在长为L,宽为H的监测区域中,以监测区域左下角为坐标原点建立坐标系,Sink节点的坐标为(0,H/2)。②传感器网络中节点同构,初始能量相同且都为E0。③传感器节点的位置是未知的。④传感器节点初始时刻通讯半径为r,当节点出任簇头后通讯半径自动调整为ar,a为常数。⑤Sink节点由服务器供电,无需考虑能量且有足够的处理能力。

1.2 节点能耗模型

传感器节点发送和接收数据包都需要消耗能量,节点通讯过程如图1所示。其中发射节点消耗能量的器件主要有信号发射电路和信号放大电路,因此发射节点的能量消耗与数据包大小、信号放大倍数有关。接收节点消耗能量的器件主要有信号接收电路,因此接收节点的能量消耗主要与数据包大小有关。

图1 节点通讯模型

本文的研究基于文献[16]中的节点通讯能耗模型,其中发送能耗模型如式(1)所示,接收能耗模型如式(2)所示。

(1)

Erx=k×Ee

(2)

式(1)、式(2)中:Ee表示信号发射和信号接收电路处理1 bit数据所消耗的能量。k表示发送或接收数据包的大小(单位为bit),εamp表示信号放大电路将信号放大的倍数,d表示信号发射的距离,cd为一个距离阈值,主要与节点距离地面的高度相关,如式(3)所示。

(3)

式中:hr、ht分别表示接收节点和发送节点的天线距离地面高度。λ为电磁波波长,L为常数。

2 节点分簇方法

2.1小节介绍利用距离Sink节点最短跳数设置簇首竞争半径,2.2小节介绍在簇首竞争半径内选取簇首,最后2.3小节介绍普通节点加入簇的方法。

2.1 簇首竞争半径

簇首的选择是以簇首候选节点为圆心,以竞争半径为半径的范围内判断候选节点是否出任簇首。簇首候选节点的竞争半径与最终簇首被选择的数量相关,由于传感器网络采集的数据包通过簇首之间多条转发至Sink节点,因此越靠近Sink节点的簇首不仅需要接收和转发其簇成员的数据包,而且还需要转发大量距离Sink节点较远的簇首节点发送来的数据包,而距离Sink节点较远的簇首节点在为其他簇首节点转发数据包方面消耗的能量相对来说较少。综上所述,越靠近Sink节点的簇首在同一轮数据采集转发过程中消耗的能量远远多于距离Sink节点较远的簇首,为了均衡传感器网络的整体能耗,距离Sink节点较近的区域应该选择更多的传感器节点成为簇首,分担传感器网络负载,而距离Sink节点较远的区域应该选择较少的簇首。

由于本文的研究针对位置未知的传感器节点,因此利用节点距离Sink节点的最短跳数表示节点与Sink节点的距离,传感器节点的最短跳数可通过传感器网络洪泛方法获得,如文献[17]介绍的方法。本文的竞争半径并不采用欧氏距离,而是采用信号强度(RSSI<0),因为文中传感器节点的位置未知,当节点与簇首候选节点之间的信号强度大于cr(竞争半径对应的RSSI值),则认为该节点位于簇首候选节点的竞争半径内,竞争半径如式(4)所示。

(4)

式中:RSSIr表示在节点通讯半径r处的信号强度值,为负数,hopmin表示距离Sink节点的最短跳数,h为常数。当节点与簇首候选节点之间的信号强度大于cr时,认为该节点位于簇首候选节点的竞争半径内。当hopmin越小则越靠近Sink节点,此时cr越大,则该簇首候选节点竞争半径越小,最终能够构建的簇规模越小,而hopmin越大,则cr越小,则该节点能够构建的簇规模越大。

2.2 簇首选举

簇首的选择对分簇路由协议的影响重大,选择合适的节点出任簇首能够较好的均衡网络能耗延长网络生存时间。簇首的任务是接收簇成员节点的消息并转发给下一跳簇首,因此簇首需要考虑剩余能量,其次簇成员节点会发送大量的数据包到簇首节点,因此簇成员节点与簇首节点之间的链路质量(LQI)要好。最后簇首与簇首之间通讯需要将通讯半径扩大,且成为簇首需要消耗较大的能量,因此簇首的度(簇首候选节点竞争半径内传感器节点的数量)不宜太小,否则会造成能量的浪费。

基于上述分析,综合考虑簇首候选节点的剩余能量、簇首候选节点与其簇成员节点之间的链路质量LQI和簇首候选节点的度进行簇首选举。利用文献[17]提出的方法为每个传感器节点建立并储存邻居节点表,如表1所示。

表1 邻居节点表

表1中ID为邻居节点的唯一表示,Ej为邻居节点的剩余能量,RSSIij为节点与其邻居节点之间的信号强度,LQIij为节点与邻居节点之间的链路质量。根据表1中的相关信息计算每个簇首候选节点的W值,如式(5)所示,W值综合考虑了簇首候选节点的剩余能量、簇首候选节点与簇成员节点的链路质量以及簇首候选节点度,根据W值的大小选择簇首节点,W值越大,则簇首候选节点最终被选择为簇首节点的概率越高。

(5)

式中:α、β、χ为常数,可根据经验设置,且α+β+χ=1,Ei为簇首候选节点的剩余能量,E0为传感器节点的初始能量,LQIij为簇首候选节点i与其竞争半径内的邻居节点j之间的链路质量。LQImax为一个常数,即链路质量范围内的最大值,Da为传感器网络的平均度,Di为簇首候选节点的度。

在长为500,宽为300的矩形区域内部署800个传感器节点,传感器节点的通讯半径r=30,根据上述簇首选择方法选择的簇首节点如图2所示。从图中可知越靠近Sink节点的区域,簇首密度越高,越远离Sink节点的区域簇首密度较低。

图2 簇首分布图

2.3 普通节点加入簇

2.2小节选取了合适的节点出任簇首,在2.3小节中研究利用虚拟引力方法将普通传感器节点加入到簇首中形成簇。当簇首节点的剩余能量和通讯质量都比较高时,该簇首节点有能力构建规模较大的簇,而剩余能量较低的簇首则构建规模较小的簇,这有利于簇首之间的能耗均衡。

在路由协议中,节点i出任簇首后,向周围传感器节点广播信标帧,告知其邻居节点。广播的信标帧中包括簇首的剩余能量Ei和簇首到邻居节点j的信号强度RSSIij。同一个邻居节点j可能收到多个簇首发送的信标帧,根据信标帧中的信息计算节点j与其各个邻居簇首的引力F(i,j),最后节点j加入对其引力最大的簇首,引力计算如式(6)所示。

(6)

节点之间的距离可用信号强度表示,当信号强度RSSIij的平方越小,则说明节点与簇首之间的距离越小,通讯需要消耗的能量越少,普通节点与簇首节点间的引力F(i,j)越大,因此普通节点选择加入簇首时会选择距离该节点相对较近的簇首。当簇首节点的剩余能量Ei越大,则对其周围的普通节点引力F(i,j)越大,则更容易构建规模较大的簇,而大规模的簇使得该簇首能量消耗较快,最终与其他簇首的剩余能量均衡。剩余能量相对较少的簇首则构建规模较小的簇,降低能量的消耗。

3 簇头间路由

簇成员节点定时采集数据并通过一跳路由发送至簇首节点,然后簇首经过多跳路由将数据传输至Sink节点。由于簇首之间距离比较大,为保证传感器网络通讯质量,簇首节点主动放大发射功率,将通讯半径r调整为R=γr,γ为常数且大于1。本文提出的路由协议不仅在网络分簇方面充分考虑了能耗均衡,在簇首间路由转发方面同样需要考虑能耗均衡。

簇首间路由采用链路式路由协议,为了均衡网络中簇首节点的能耗,设计了簇首下一跳代价选择函数,如式(7)所示。

(7)

式中:a、b、c为常数,可根据经验获得,且a+b+c=1,ci为需要发送数据包的簇首节点编号,cj为与簇首ci相邻的簇首节点编号,Ecj为簇首cj的剩余能量,Hcj为簇首cj距离Sink节点的最短跳数,Hmax为簇首ci的通讯半径R内的簇首节点距离Sink节点的最短跳数的最大值,Di为簇首ci的度,Da为网络平均度。

根据式(7),当簇首节点ci收集了其簇成员节点的数据,然后根据代价选择函数计算与之相邻的簇首节点cj转发其数据包的代价,选择转发代价最小的簇首作为下一跳转发节点。当簇首节点的剩余能量Ecj较低,则被选择为下一跳转发节点的概率越低,反之则反。距离Sink节点最短跳数Hcj越大时,该簇首节点被选择为下一跳转发节点的概率越低,同时当簇首的度太大时,其消耗了大量的能量用于簇内通讯,因此被选择为下一跳节点的概率也就越低。因此该代价选择函数能够较好的均衡簇首之间的通讯能耗。

4 实验

实验中在长度为500、宽度为300的矩形区域中部署了800个传感器节点,传感器节点的相关参数如表2所示。

表2 传感器节点参数表

簇成员传感器节点的通讯半径r=30 m,簇首通讯半径R=45 m,传感器网络采集500次数据为一轮,然后按照簇首选择方法重新选择簇首。传感器节点采集转发一次数据的大小为600 bit。

4.1 成簇实验

本文提出的分簇路由协议能够根据簇首距离Sink节点的最短跳数控制簇规模的大小。越靠近Sink节点的簇首节点需要转发更多的数据包,因此构建较小规模的簇,使得簇内能量消耗少,而更多的能量用于数据包转发。而距离Sink节点越远的簇首为其他节点转发数据的数量较少,因此构建规模较大的簇,使得簇内能量消耗较多。最终实现部署区域内簇首能量消耗均衡。分簇实验结果如图3所示。

实验结果表明本文提出分簇方法能使越靠近Sink节点的簇规模越小,远离Sink节点的簇规模越大。

4.2 网络能耗情况分析

传感器网络每次采集和转发数据包都会消耗能量,实验对比了本文提出的路由协议(CCERP)、LEACH路由协议、最短路径路由协议以及文献[7]提出的EE-LEACH路由协议的能耗均衡性,实验中利用传感器网络剩余能量的方差作为衡量网络能耗均衡性的标准。实验结果如图4所示,传感器网络一次簇首调整作为一轮数据采集,每轮采集500次数据,横坐标为网络采集数据的轮数,纵坐标为剩余能量的方差。

图4 网络剩余能量方差图

实验结果表明随着传感器网络采集次数的增加,方差逐渐变大,因为网络中某些节点为其他节点转发了大量的数据包,消耗了较多的能量,而有些节点为其他节点转发数据包的次数比较少,消耗的能量也就比较少,因此会导致网络中剩余能量的方差增大。首先本文提出的路由协议比其他3种路由协议的剩余能量方差小,因为CCERP协议不仅考虑了簇首间的能耗均衡,还充分考虑了簇内能耗均衡。其次EE-LEACH的剩余能量方差也比传统的LEACH协议小,节点剩余能量方差最大的是最短路径。且CCERP协议随着网络的轮数增加,方差增加比其他3种协议都慢,因此CCERP路由协议具有较好的能耗均衡性。

为了进一步验证提出的路由协议具有较好的能耗性能,实验又在剩余能量均值方面与最短路径路由协议、EE_LEACH、LEACH分簇路由协议进行了对比。实验结果如图5所示,横坐标为网络进行的轮数,纵坐标为网络剩余能量的均值。

图5 网络剩余能量均值

实验结果表明随着网络轮数的增加,网络中的剩余能量逐渐减低且剩余能量差距逐渐拉开,因为传感器网络每次采集和转发数据都需要消耗能量,所以网络的剩余能量均值会降低。同时本文提出的路由协议(CCERP)的网络平均剩余能量高于其他3种路由协议,其中最短路径路由协议的剩余能量最低,EE-LEACH协议使得网络的剩余能量高于传统的LEACH协议,因为CCERP路由协议在分簇方面较符合能耗均衡性的要求,使得簇首节点不会过早死亡,因此簇首间的路由比较稳定,降低了簇首间重新进行路由选择而消耗的能,但是EE-LEACH并没有充分考虑簇规模大小对能耗均衡性的影响,因此随着传感器网络的运行,距离Sink节点较近的簇首节点需要为其他节点转发大量的数据,当某些簇首节点死亡后簇首需要重选进行路由选择而消耗能量,而LEACH路由协议需要簇首直接与Sink节点进行通讯,在大型传感器网络中簇首节点与Sink节点距离非常远,因此消耗了大量的能量。

4.3 网络生存时间分析

网络的生存时间与网络中路由协议的能耗均衡性息息相关,如果路由协议只考虑最短路径将数据包传输至Sink节点,则势必会使网络陷入局部过热问题,在“热区”中的传感器节点容易提早死亡,从而大大降低了网络的生存时间,因此设计路由协议时需要考虑节点的能耗均衡原则。本文提出的CCERP能耗均衡路由协议综合考虑了节点的剩余能量、节点距离Sink节点的跳数、节点度等因素,最终实验结果如图6所示,横坐标为网络进行的轮数,纵坐标为网络中节点死亡的数量。

图6 死亡节点数量

实验结果表明随着网络轮数的进行,网络中会逐渐出现死亡节点。最先出现死亡节点的是最短路径路由协议,因为该协议只考虑数据传输的最短跳数,并没有考虑能耗均衡性,其次是LEACH路由协议出现了死亡节点,因为该协议的簇首选择是随机性的,同样不能避免“热区”问题,EE-LEACH路由协议在传统的LEACH协议基础上考虑了簇首能耗均衡问题,因此出现死亡节点的时间比LEACH晚。本文提出CCERP路由协议在进行了16轮数据采集后还未出现死亡节点,因为本文提出的路由协议不管在簇首选择、成簇过程和簇间路由方面都充分考虑了能耗的均衡性。如果以第1个节点死亡表示网络的死亡,则本文提出的路由协议能够大大延长网络的生存时间。

4.4 平均跳数与网络生存时间

网络的生存时间与数据包转发的跳数息息相关,跳数越多,消耗的能量越大,网络生存时间越短。传感器节点传输数据包的跳数和簇规模的大小相关,簇规模越大,则跳数越少,簇规模的大小可通过式(4)中的常数h控制。实验研究传感器网络中节点的平均跳数和网络生存时间的关系,实验中共进行了30轮簇首调整,每轮调整采集500次数据,结果如图7所示,横坐标为网络的平均跳数,纵坐标为传感器网络中死亡节点的平均数量。

实验结果表明平均跳数在5、6跳之间时网络的生存时间最大,出现的死亡节点数量最少,而少于5跳时虽然簇首节点转发的次数少了,但是每一跳需要转发的距离较长,因此网络的能耗均衡性较差,而岛屿6跳时,每个簇的规模较小,需要转发的跳数增加,因此消耗了较多的能量且能耗均衡性较差,因此网络的平均跳数在5、6跳左右时,能够较好的均衡转发距离和转发次数消耗的能量,达到较好的网络能耗均衡性。

图7 平均跳数与网络生存时间图

5 总结

本文提出的分簇路由协议创新之处在于在位置未知的传感器网络中通过距离Sink节点的跳数控制簇首竞争半径,从而达到控制簇规模的目的,在成簇过程中使用虚拟力模型综合考虑了普通节点与簇首节点的剩余能量以及信号强度最终普通节点根据虚拟力大小选择加入合适的簇首,并且簇首间多跳通讯也综合考虑了簇首距离Sink节点的最短跳数、簇首的剩余能量和簇首的度,因此在簇首选举、成簇过程、簇间通讯都充分考虑了网络能耗的均衡性,实验结果验证了该协议具有较好的能耗均衡性能。后续将针对能耗均衡分簇路由问题继续深入研究。

[1] 廖先林,陆畅,姜婷,等. 一种能耗均匀的WSN分簇路由协议研究与设计[J]. 小型微型计算机系统,2014,35(10):2199-2202.

[2] 刘龙军,丁洪伟,柳虔林,等. 基于FPGA WSN轮询接入控制协议的研究[J]. 通信学报,2016,37(10):181-187.

[3] 徐祥振,汪成亮. 基于节点密度与TDMA的无线传感器网络集簇协议[J]. 传感技术学报,2015,28(11):1689-1694.

[4] Heinzelman W R,Chandrakasan A,Balakrishnan H. Energy-Efficient Communication Protocol for Wireless Microsensor Networks[C]//Hawaii International Conference on System Sciences. IEEE Computer Society,2000:8020.

[5] 白永祥. 一种LEACH路由协议算法的改进与分析[J]. 通信技术,2015,48(9):1062-1067.

[6] Mehmood A,Lloret J,Noman M,et al. Improvement of the Wireless Sensor Network Lifetime Using LEACH with Vice-Cluster Head[J]. Ad Hoc and Sensor Wireless Networks,2015,28(1):1-17.

[7] Arumugam G S,Ponnuchamy T. EE-LEACH:Development of Energy-Efficient LEACH Protocol for Data Gathering in WSN[J]. EURASIP Journal on Wireless Communications and Networking,2015,2015(1):1-9.

[8] Soro S,Heinzelman W B. Prolonging the Lifetime of Wireless Sensor Networks via Unequal Clustering[C]//Parallel and Distributed Processing Symposium,2005. Proceedings. 19th IEEE International. IEEE,2005:8 pp.

[9] 孙彦清,彭舰,刘唐,等. 基于动态分区的无线传感器网络非均匀成簇路由协议[J]. 通信学报,2014(1):198-206.

[10] 蒋畅江,石为人,唐贤伦,等. 能量均衡的无线传感器网络非均匀分簇路由协议[J]. 软件学报,2012,34(5):1222-1232.

[11] Latiff N M A,Tsimenidis C C,Sharif B S. Energy-Aware Clustering for Wireless Sensor Networks Using Particle Swarm Optimization[C]//IEEE,International Symposium on Personal,Indoor and Mobile Radio Communications. IEEE,2007:1-5.

[12] 李长庚,于澄澄,陈东海. 基于半径递增有向成簇的WSN路由算法[J]. 传感技术学报,2015,28(11):1682-1688.

[13] 刘铁流,巫咏群. 基于能量优化的无线传感器网络分簇路由算法研究[J]. 传感技术学报,2011,24(5):764-770.

[14] 严英,郭丽,许建真. 一种基于LEACH与PEGASIS协议的分层成链优化路由算法[J]. 传感技术学报,2011,24(9):1311-1316.

[15] 刘铁流,巫咏群. 基于能量优化的无线传感器网络分簇路由算法研究[J]. 传感技术学报,2011,24(5):764-770.

[16] Heinzelman W B,Chandrakasan A P,Balakrishnan H. An Application-Specific Protocol Architecture for Wireless Microsensor Networks[J]. IEEE Transactions on Wireless Communications,2002,1(4):660-670.

[17] 周雪,朱小明,陈立建,等. 基于停车诱导系统的能量均衡可靠路由协议的设计[J]. 传感技术学报,2015,28(9):1408-1417.