基于簇头功能分化的无线传感器网络成簇算法

2015-05-06陈东海李长庚

传感技术学报 2015年2期

关键词：能量消耗权值无线

陈东海,李长庚

(中南大学物理与电子学院,长沙 410083)

基于簇头功能分化的无线传感器网络成簇算法

陈东海,李长庚*

(中南大学物理与电子学院,长沙 410083)

以LEACH为基础演化而来的各类算法在簇头选举时始终包含有“随机选择”的成分,导致无线传感器网络在拓扑结构的优化和能量消耗的均衡上受到限制。从分化簇头功能和优化功能节点选举机制的角度出发,提出一种分化簇头功能的分布式算法,引入功能节点推荐机制,弱化簇头选举中的随机成分,分化簇头功能,将以往簇头管理节点、融合数据、转发信息的三大功能分别由管理节点、融合节点、转发节点3个功能节点来承担。仿真数据表明,提出的分簇算法能有效优化簇内拓扑结构、提高节点能量消耗均衡性,能够延长网络生存周期15%～20%。

无线传感器网络;功能分化;管理节点;融合节点;转发节点

无线传感器网络改变了人类与自然界的交互方式,其节点一般部署在无人值守地域,且能量和计算能力有限,因而在设计算法和执行任务时必须突出考虑其能量因素,以此获得较长的网络生存周期。分簇算法的基本思想是把随机分布的传感器节点按簇进行划分,每个簇内按照一定选举规则选出簇头,簇头负责召集和管理成员节点、融合成员节点发来的数据并进行转发[1],循环组簇,轮流选择簇头,将整个网络的能量负载尽可能的平均分配到每个传感器节点。分簇算法能减小节点数据传输距离和传输数据量,进而大幅度降低节点能量消耗。此外,分簇算法作为节点组网的一种方式,在较大规模的无线传感器网络中,能很好的提高网络生存周期,增强网络的稳定性和鲁棒性。

LEACH[2]算法是经典的分层路由算法,其节点等概率地随机担任簇头,这使得低能量的节点也有相同的概率成为簇头节点,HEED[3]算法和TEEN[4]算法在选举簇头时考虑了能量因素,使能量较少的节点被选为簇头的概率减小,EEUC[5]算法、EOUCP[6]算法、CHTD算法、LDBPL[7]算法引入了竞选半径非均匀、竞选时间延迟、分层次成链等概念,文献[8]还提出了代理簇头的思想,这些算法均在簇头选举过程中作了改进,其结果更趋合理,但仍旧存在一定的随机性,且多个约束条件作用于簇头的选举过程,增加了算法复杂度,增加了节点成簇组网的能量消耗。本文提出一种分化簇头功能的算法,引入功能节点推荐机制,降低选举的随机性和复杂度,提高选举功能节点的合理度,将原来一个簇头的功能分担到3个功能节点上,即管理节点、融合节点和转发节点,分化簇头功能,均衡网络能耗。

1 系统模型与问题描述

1.1 网络模型

无线传感器网络是一个面向应用的系统,不同的应用环境需要不同的网络模型。文中假定N个传感器节点随机均匀分布在一个面积为M×M的方形区域A内,并且有如下性质:①所有节点部署后不移动,能量不补充;②基站部署在区域A内或边界外一个固定位置,并且是唯一的;③无线信道满足对称性,即正向传输和反向传输等量的数据消耗的能量相同;④节点同构,具有相同的处理和通信能力,在网络中地位平等;⑤节点无线发射功率可控,可根据距离调整发射功率;⑥节点可以获取无线接收信号的强度(RSSI);⑦每轮中节点的能量消耗不一致。

1.2 无线通信能量模型

网络中节点通信采用Heinzelman等人在文献[9-10]中提出的无线通信模型。当发送节点与接收节点的距离小于阈值d0时,采用自由空间模型,否则采用多路衰减模型。发送方发送长度为lbit的数据到距离为d0的位置所消耗的能量为

(1)

而接收方接收lbit的数据所需能量为

ERx(l,d)=Eelec(l)=lEelec

(2)

其中,Eelec为发射电路的能量消耗,εfs和εmp为两种模型发射放大器系数。

1.3 平均剩余能量估计

为提高能量消耗均衡性,便于节点了解自身剩余能量在全网络中所处的水平,通常需要对节点的平均能量进行计算,但平均能量的计算需要统计全网的剩余能量信息,这对分布式路由算法是非常困难的[11],这里引入估计方法,对平均能量进行相应估计。首先粗略估计全网每一轮消耗的能量Eround

(3)

式中,Etotal为全网初始总能量,r0为估计轮数,即网络理论生存周期,在实验过程中可采用递归的方法取得,这里不作论述。估计全网剩余能量的平均值为

(4)

其中,N为节点数目,r为实验轮数。

2 簇头功能分化算法

本文所提算法沿用按轮组网的思想,每轮包含成簇设置和稳定运行两个阶段。在成簇设置阶段,首先按所需成簇比例选出管理节点,然后由管理节点推荐融合节点,再由融合节点推荐转发节点,进而完成组簇。

2.1 初始化

算法开始时,基站首先以某一特定的功率向全网发送广播消息,各节点根据接收基站发来消息的信号强度确定自身与基站的近似距离di-BS,并通过定限功率与周围节交换信息,确定半径R内的节点度Ddegree。

2.2 选举管理节点

2.3 选举融合节点

融合节点负责接收簇成员节点发送的信息并进行融合,是真正意义上的“簇头”,对节点能量和位置有一定要求。本文提出一种“推荐”机制,由管理节点在其邻节点中选取,选取标准为节点能量和节点度。首先由管理节点以特定功率向邻节点发送广播消息,要求邻节点计算出自身成为融合节点的权值,同时也计算出自身成为融合节点的权值,各节点计算出权值后发送给管理节点,管理节点对各权值进行比较,并向权值最大者发送消息,通知其被选为融合节点。权值计算公式为

(5)

2.4 选举转发节点

转发节点由融合节点推荐,需要满足3个要素:是融合节点的邻节点、离基站较近、剩余能量较多。融合节点首先以特定功率向邻节点发送广播消息,要求邻节点计算出自身成为转发节点的权值,各节点计算出权值后发送给融合节点,融合节点对各权值进行比较,并向权值最小者发送消息,通知其被选为转发节点。其权值公式为:

(6)

至此,簇拓扑结构已生成,它缓解了以往算法中簇头节点功能过多、能量消耗过快、簇头位置不科学的现象,减小了网络重组的频率、降低了簇头选举的要求和复杂度、优化了簇头位置,节省了簇内成员节点的通信能量,所形成簇结构如图1所示。

需要强调的是,在符合条件的情况下,同一个簇内的管理节点、融合节点和转发节点可以只由一个节点或两个节点担任。

图1 本文算法簇结构

3 仿真实验及数据分析

由于本文主要是对簇的结构和成簇过程进行研究和创新,在实验仿真过程中涉及的其他相关方面如簇半径的大小、簇的数目的优化和簇间转发策略等方面分别采用文献[5,12-13]中的办法。

3.1 仿真实验及结果分析

仿真中,设置仿真场景参数为:在边长M=100 m区域内随机分布N=100个无线传感器节点,节点初始能量E=0.5 J,基站位于(150,50)m,能量不受限制,初始成簇概率p=0.05,节点每次发送或接收数据长度为l=4 000 bit。对LEACH、EEUC和本文算法进行仿真,得到死亡节点个数随仿真轮数的变化图,如图2所示。

图2 M=100 m时生存周期比较

由图可以看出,LEACH算法在750轮左右开始出现死亡节点,到1 350轮左右全部节点死亡,第1个节点死亡的时间和全部节点死亡的时间均较早,这是因为LEACH采用的随机选举簇头的方式,对簇头的能量和位置未做限制,簇头功能多、能耗大,簇头位置随机,簇规模不均匀,且采用单跳通信,导致簇内成员节点通信距离难以控制,加大节点能耗;EEUC算法在1 200轮左右时开始出现死亡节点,在1 600轮左右全部节点死亡,相比LEACH算法有较大提高,能量均衡性较好,因为EEUC在簇头选举时考虑了能量因素,减少了低能量节点当选簇头的可能性,且其通过对节点竞选半径的设置控制了簇规模的大小,提高了能耗均衡性;而本文算法在1 400轮左右出现第1个死亡节点,到1 800轮左右全部死亡,相比于EEUC,新算法在成簇时采用的推荐机制,不仅考虑了簇头的能量因素,剔除了低能量节点当选簇头的可能性,而且分化了簇头的功能,进一步增强了能耗均衡性。

第1个节点死亡的时间FD(First Dead)和全部节点死亡时间AD(All Dead)是衡量路由算法的重要指标。为进一步验证算法的性能,在上述仿真条件下重复实验50次,记录其第1个节点死亡的时间(轮数)和全部节点死亡时间(轮数),并进行比较。从表1数据可知,EEUC在FD和AD上比LEACH分别提高了54%、18%,这得益于EEUC在簇头竞选中引入了非均匀方案和对能量因素的考虑,而本文算法在FD和AD上比EEUC分别提高了19%、15%。

表1 网络生存周期

为确定算法应用在不同规模条件下的变化,修改仿真场景条件为:边长M=200 m,节点数N=400个,基站位于(300,100)m,其他条件不变,即单纯改变监控区域大小而不改变节点密度,得到数据如图3所示。

图3 M=200 m时生存周期比较

从图3可以看出,在保持节点密度不变而扩大监控区域时,3种算法的生存周期均有所下降,其中LEACH生存周期下降最快,EEUC次之,本文算法下降较慢,且较EEUC延长了20%～25%,这是由于在保持相同节点密度而扩大监控区域的条件下,增加的能量消耗主要是来源于簇头与簇头或簇头与基站之间的通信,簇头能量消耗加快导致簇重组频率增加,从而缩短网络生存周期,LEACH中簇头与基站之间的通信距离大大增加,能量消耗随距离二次方增长,EEUC和本文算法中簇间簇间转发次数增加但距离未增加,能量消耗呈线性增长,又由于本文算法的簇头功能分化机制比其他算法在功能节点能量的消耗上相对缓和,从而也降低了簇重组的频率,减缓了能量的消耗。实验证明,簇头功能分化算法对大规模部署的无线传感器网络具有更强的适应性。

3.2 仿真参数分析

算法中的权值因子w0、w1、w2十分重要,对算法性能影响比较大,理论上,在特定的场景中,每个权值因子均存在一个最优值。如在上述M=100 m仿真场景条件下,限定w1=0.6、w2=0.55时,w0从0按步长0.05增加到1时,其第1个节点死亡时间(轮数)变化如图4所示。当w0从0增大到0.2的过程中,第1个节点死亡时间逐渐推迟,即生存周期延长,这是由于管理节点需要一定的能量要求,过低能量的节点担任管理节点后会加速死亡;当w0大于0.2以后,越来越多的节点达不到担任管理节点的能量要求,使得管理节点数目逐渐减少,直接导致成簇数目减少,从而影响网络的生存周期,所以0.2为w0的在该条件下的最优值。

图4 第1个节点死亡时间随参数w0变化图

当限定w0=0.2、w2=0.55时,w1从0按步长0.05增加到1时,其第1个节点死亡的时间(轮数)变化如图5所示。当w1从0增大到0.6的过程中,网络生存周期逐渐延长,原因在于高能量节点被推荐为融合节点的权重在逐渐增加,更容易选取得最优的融合节点;而当w1大于0.8后,网络生存周期加速减短,这是因为式(5)中,对融合节点的能量阈值提高,推荐权重却没有相应地提高,所在w1的值在0.6到0.8之间比较合适,图为w1=0.6左右时,第1个死亡节点出现的时间最晚,即网络生存时间最长。

图5 第1个节点死亡时间随参数w1变化图

图6 第1个节点死亡时间随参数w2变化图

同样的,当限定w0=0.2、w1=0.6时,则得到随参数w2变化的生存周期图,得到该条件下w2的最优值为0.55,见图6。值得注意是,当仿真条件改变时,生存周期随参数的变化也会有相应的改变。

4 结论

本文提出的簇头功能分化算法,其核心思想包含两个方面:一是提出分化簇头功能的方案,使原来由一个节点承担的功能任务分担到2～3个节点,降低了功能节点的能量要求,缓解了功能节点过早死亡的现象,增强了网络的能耗均衡性能;二是提出了功能节点的推荐机制,降低了选举的复杂度,消除了融合节点选举的随机性,优化了功能节点在簇内的位置,降低了簇成员节的通信成本。仿真结果表明,采用本文算法提出的分化簇头功能方案和功能节点的推荐机制,能将无线传感器网络生存周期提高15%～20%。

[1]AkyildizIF,SuW,SankarasubramaniamY,etal.ASurveyonSensorNetworks[J].IEEECommunicationsMagazine,2002,40(8):102-114.

[2]Heinzelman W,Chandrakasan A,Balakrishnan H.Energy-Efficient Communication Protocol for Wireless Micro Sensor Networks[C]//Proceedings of the Hawaii Internationnal Conference on System Sciences,LosAlamitos,C A,USA:IEEE Computer Society,2000:3005-3014.

[3]Ossama Y,Sonia F.HEED:A Hybird,Energy-Efficient,Distributed Clustering Approach for Ad Hoc Sensor Networks[J].IEEE Transactions on Mobile Computing,2004,3(4):366-379.

[4]Manjeshwar A,Agrawal D P.TEEN:A Routing Protocol for Enhanced Efficiency in Wireless Sensor Networks[C]//Proceedings of the 15th International Parallel and Distributed Processing Symposium(IPDPS),San Francisco,2001:2009-2015.

[5]李成法,陈贵海,叶懋,等.一种基于非均匀分簇的无线传感器网络路由协议[J].计算机学报,2007,30(1):27-36.

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

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

[8]刘东江,贾卓生.基于分簇的无线传感器网络路由协议的研究[J].计算机学报,2012,39(10):23-38.

[9]Soro S,Heinzelman W B.Prolonging the Lifetime of Wireless Sensors Networks Via Unequal Clustering[J].In:Proc of the 19th IEEE Intertional on Parallel and Distributed Processing Symposium.San Francisco:IEEE Computer Society Press,2005:236-240.

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

[11]尚凤军.无线传感器网络通信协议[M].北京:电子工业出版社,2011:53-54.

[12]Tripathi R K,Singh Y N,Verma N K.Clustering Algorithm for Non-Uniformly Distributed Nodes in Wireless Sensor Network[J].E Electronics Letters,2013,49(4):299-300.

[13]Zhang D G,Li G,Zheng K,et al.An Energy-Balanced Routing Method Based on Forward-Aware Factor for Wireless Sensor Network[J].IEEE Transactions on Mobile Computing,2014,10(1):766-773.

An Function Decomposition Algorithms for Cluster Head for WSNs

CHENDonghai,LIChanggeng*

(School of Physics and Electronics,Central South University,Changsha 410083,China)

Current algorithms based on LEACH or its derivatives always contain the factor of “random”in the aspect of selecting cluster heads,this is not conducive to balance the energy consumption of the wireless sensor networks.In order to improve the election mechanism of the cluster head and optimize its position and function,a new clustering method(Function Decomposition Algorithms for Cluster Head)for wireless sensor networks is proposed.Our approach provides a mechanism to recommend functional nodes,weaken the random component of cluster head selection,and split the cluster head into 3 functional nodes:management node,data fusion node,sending node.Simulation data show that the new algorithm can effectively optimize the topology of wireless sensor networks,improve the balance performance of energy consumption,and prolong sensor networks lifetime by 15%～20%.

wireless sensor networks,function decomposition,management node,data fusion node,sending node