无线传感器网络能量均衡分簇路由协议

赵成林,毛 松,谭 虎

(北京邮电大学无线网络实验室,北京100876)

0 引言

无线传感器网络是近年来综合了传感器技术、嵌入式计算技术、分布式信息处理技术和无线通信技术等多学科的研究成果迅速发展的一门技术,在工业、农业、军事、环境、医疗、家用、保健和交通等领域具有广阔的应用前景。

无线传感器网络节点能量的有限性使高能效路由协议的研究成为无线传感器网络研究热点之一。无线传感器网络的路由协议按照拓扑结构可分为平面型和层次型2类。平面型路由需要维护动态变化的路由表,维护相对困难且扩展性差。而层次型路由控制信息较少,可扩展性好,适合大规模的无线传感器网络。LEACH协议[1]是一种典型的基于簇结构的层次路由协议,得到了非常广泛的应用,其成簇思想也在很多后期发展的协议中得到应用,如TEEN协议[2]、PEGASIS协议[3]和HEED协议[4]等。

1 LEACH协议及性能分析

LEACH协议将WSN中的节点分为簇首节点和普通节点,普通节点采集数据后发送到簇首节点,簇首节点进行数据的融合后再发送到汇聚节点(基站)。一般来讲,簇首节点的能量消耗要大于普通节点的能量消耗。在LEACH算法中定义了“轮”的概念,每一轮包括簇的建立和稳定的数据传输2个阶段,每个节点通过周期性轮转都有可能成为簇首,因此均衡了网络节点的能量负载。

在簇的建立阶段,每个节点自动生成一个0～1间的随机数RandomNumber,若RandomNumber小于某门限值T(n),则此节点在本轮中被选为簇首。

式中,p为网络中簇首节点占总节点数的百分比;r为已完成的轮数;G为在最后rmod(1/p)轮中还没有当选簇首的节点集合。

节点当选为簇首后向周围节点广播自己是簇首的消息ADV,非簇首节点收到该消息后,根据接收到的信号强度选择信号最强,即距离最近的簇首发送加入簇请求消息,此后簇首节点设定一个TDMA时间表为其簇成员节点分配发送时隙,同时产生一个本簇内使用的CDMA编码,连同TDMA时间表一起发送给本簇的成员节点,至此,簇建立阶段结束。

在稳定运行阶段,簇成员节点采集数据并在TDMA时间表确定的时隙内向簇首节点发送数据,然后进入睡眠状态以节省能量,直到下一个传输时刻的到来。簇首节点接收到本簇所有成员节点的数据形成一帧数据,然后经过数据融合后发送到基站。每隔一定时间后,整个网络重新进入簇形成阶段开始新一轮的簇首选举过程。

LEACH协议采用层次结构,与平面路由相比简化了路径的选择及路由信息的存储,同时自适应随机选取簇首节点,利于实现全网负载的均衡。但是LEACH协议存在的下列3个方面的问题制约着网络能量的均衡消耗:

①节点担任簇首是严格的等概率选择,能量较低的节点一旦成为簇首很容易耗尽能量而死亡;

②簇的形成过程中只考虑了节点与被选簇首之间的距离,而没有考虑能量因素,因此可能导致能量较低的簇首节点过快的消耗能量而死亡;

③簇首节点以单跳形式向基站传送数据,不仅会导致距离基站较远节点的能量消耗过大,也不利于网络的大规模扩展。

2 改进的能量均衡分簇路由协议

针对LEACH协议中存在的上述问题,提出了一种改进的高能效分簇路由协议,协议在簇首选择、簇的形成和簇间路由3个方面均引入传感器节点的能量因子,均衡了网络的能量消耗,全面提高了网络的生命周期。

2.1 能量模型

传感器节点的能量损耗采用文献[2]中的自由空间模型和多径衰减模型进行计算。由文献[2]得知,当通信距离小于阈值d0时,发送数据的能量消耗与距离的平方成正比,否则与距离的4次方成正比。

当发送方发送l比特信息到距离为d的接收方时,发送方消耗的能量由发射电路损耗和功率放大损耗2个部分构成,可表示为:

同时,接收方消耗的能量为:

式中,Eelec为无线收发单位信息电路所消耗的能量;εfriss-amp、εtwo-ray-amp分别为2种信道模型下功率放大所需要的能量。其中d0的表达式为:

2.2 簇首的选择

为了均衡传感器节点的能量,改进的算法在簇首选择时考虑了节点的当前能量与历史能量消耗2种信息,以增大当前具有较高能量的节点成为簇首的概率。具体的方法是对LEACH协议中选择簇首的门限值T(n)进行如下修正:

式中,Eresidual为备选簇首节点的当前能量;Etotal为网络中所有传感器节点当前的总能量;Er-1_average为 上一轮簇首形成过程中传感器节点的平均能量;Er-1_dissipate为上一轮簇首形成过程中节点消耗的能量。

为了方便,采用下面的方法对Er-1_average的值进行估计[5]。

式中,N为网络中节点的数目;Ei(r-1)为第r-1轮中节点i的剩余能量;E0为传感器网络建立时各节点的总能量。

假设理想情况下网络中所有节点的生命周期相同,设R为网络运行的总轮数,则有

式中,Eround为网络运行每一轮中消耗的能量,

式中,l为一个数据包含的比特数;k为网络中簇首的个数;EDA为簇首节点融合单位数据消耗的能量;dtoBS为簇首到基站的平均距离;dtoCH为成员节点到簇首的平均距离。假设节点在M×M区域均匀部撒,则有[6]

将式(9)和式(10)代入式(8)求得Eround值,进而代入式(7)中求得R值,最后将R值代入式(6)中即可求得Er-1_ average值。

2.3 簇的形成

式中,Einitial为每个节点已知的初始能量;w为权重因子。普通节点选择有最大权值的簇首节点加入,然后当选为簇首的节点创建TDMA时间表,向簇成员节点分配时隙和簇内CDMA编码。式(11)的意义在于成簇阶段普通节点选择簇首加入其中时综合权衡了备选簇首节点的当前能量信息以及普通节点距离备选簇首节点的距离因素,这样做主要基于以下2点:

①考虑备选簇首节点的当前能量信息可以有效避免当前能量较低的簇首节点加入过多的簇成员节点,使簇首节点的负载过重造成能量消耗过速;

②根据上述能量模型,簇内通信的消耗和距离的平方成正比(假设簇首节点和簇成员节点的距离小于阈值d0),考虑普通节点距离备选簇首节点的距离因素可以有效降低簇内通信代价,节省簇内通信能量消耗。

权重因子w用于平衡能量和距离2个因素在weight中所占比例,以使实验效果得到最优。实验中从0到1变化w的取值,观察网络中第1个节点死亡的时间(定义为网络的生命周期)随之变化的趋势,结果如图1所示,图中当w等于0.8时,网络的生命周期达到最大值,因此将w的值确定为0.8。

为了均衡簇内节点的能量消耗,在簇首节点广播的ADV消息中增加自身的能量信息Eresidual,非簇首节点在收到ADV消息后首先根据信号强度计算本节点与该备选簇首节点的距离Dch。通过上述计算可以得出非簇首节点与所有备选簇首节点的距离,选择上述最小值Dmin和所有备选簇首节点能量的最小值Emin,计算所有备选簇首节点的权重为:

图1 第1节点死亡时间随w值变化关系

2.4 簇间路由的建立

假设簇首节点A向基站BS传输数据,做如下定义:

①定义当前轮中簇首节点的集合为I;

②定义D(X)=+,X∈I其中dA-X表示节点A到节点X的距离,dX-BS表示节点X到基站的距离。

分别计算集合I中除节点A以外节点的函数值D(X),找出其中的最小值D(X)min,当满足以下2个条件时,将节点X作为节点A的下一跳节点,否则,节点A直接向基站传送数据。

①D(X)min＜,dA-BS为节点A到基站的距离;

②EX＞EA,EX、EA分别为节点X和A的当前能量。

上述2个条件既可以保证通过中继节点转发的能量消耗小于节点直接向基站发送数据的能量消耗,又可以避免低能量节点频繁转发数据造成的过早死亡。

此外,为了有效接收上一跳簇首节点发送的数据,在簇形成阶段备选簇首节点创建TDMA时间表时增加一个时隙,用于接收簇间数据,同时,当前簇首节点在向下一跳簇首节点传送数据时采用目的节点的簇内CDMA编码,这样可以有效地改善簇间数据传输带来的冲突和干扰。

3 仿真与分析

在Linux下用NS2仿真软件对改进后的路由协议进行仿真,仿真场景为100个传感器节点均匀部撒在100 m×100 m范围内,基站位于(50 m,175 m)位置,每个节点的初始能量为2 J,每个数据包的分组长度为500 byte,p=5%,其他能量模型相关的参数取自文献[2],即EDA=5 nJ,Eelec=50 nJ/bit/m,εfriss-amp=10 pJ/bit/m2,εtwo-ray-amp=0.0013 pJ/bit/m4。仿真中用CEBRP(Cluster based Energy Balance Routing Protocol)表示改进的协议。

图2为应用LEACH协议和改进协议的存活节点数随时间的变化规律。可以看出,LEACH协议中第1个节点死亡时间为400 s,节点全部死亡的时间为500 s左右,而改进的协议第1个节点死亡时间为680 s左右,节点全部死亡的时间为1 000 s左右,很明显后者较好地延长了网络的生存寿命。

图2 2种协议节点存活数比较

图3为分别应用LEACH协议和改进协议的网络能量消耗随时间的变化过程,可以看出应用改进协议的网络能量消耗速度明显小于应用LEACH协议的网络能量消耗。

图3 2种协议中网络总耗能比较

图4为分别应用LEACH协议和改进协议的网络基站接收到的数据量和能量消耗关系图,由图可知相同能量消耗情况下应用改进后协议的网络基站所接收到的数据明显比应用LEACH协议的网络基站接收到的数据量大。

图4 2种协议中消耗能量与接收数据比较

4 结束语

上述深入研究了无线传感器网络经典的层次路由协议LEACH,并在此基础上针对LEACH协议存在的缺陷进行了改进。改进后的协议在簇首的选择和簇的形成环节引入了传感器节点的能量因子,有效避免了低能量节点过早死亡的现象。同时采用基于能量比较的簇间多跳路由,改善了LEACH协议中簇首节点向基站直接传输数据造成的能量消耗过大的缺陷,从而从整体上均衡了传感器节点的能量消耗,大幅度地延长了网络的使用寿命。

[1]HEINZELMAN W,CHANDRAKASAN A,BALAKRISHMAN H.Energy-efficientCommunication ProtocolforWireless MicrosensorNetworks[C]//ProceedingsoftheHawaii International Conference on System Sciences.Piscataway,USA,2000:175-187.

[2]MANJESHWAR A,GRAWAL D P.TEEN:A Protocol for Enhanced Efficiency in Wireless Sensor Networks[C]//Proceedings of the 15th Parallel and Distributed Processing Symp.San Francisco,2001:2009-2015.

[3]LINDSEYS,RAGHA VENDR A C.PEGSIS:Power-Efficient Gathering in Sensor Information Systems[C]//Proceedings of the IEEEAerospace Conference'02.Montana,2002:1125-1130.

[4]YOUNIS O,FAHMY S.HEED:A Hybrid,Energy-efficent,Distributed Clustering Approach for Ad Hoc Sensor Networks[J].IEEE Transactions on Mobile Computing 2004,3(4):366-379.

[5]SUN Yanjing,CHEN Wei,ZHANG Bei,et al.Energy-efficient Clustering Routing ProtocolBased on Weight[C]//International Conference on Wireless Communications and Siganl Processing.Nanjing,China,2009:1-5.

[6]HEINZELMAN W,CHANDRAKASAN A,BALAKRISHNAN H.An Application-specific Protocol Architecture for Wireless Microsensor Networks[J].IEEE Trans on Wireless Comm.,2002,1(4):660-670.