基于簇首连任和多汇聚节点的WSN路由算法

*通信作者： 李永珍(1971—)，男，博士，副教授，研究方向为网络安全、无线网络协议.

基于簇首连任和多汇聚节点的WSN路由算法

王梦娇1，张爱丽2，李永珍1*

( 1.延边大学工学院 计算机科学与技术学科 网络与信息安全研究室， 吉林 延吉 133002；

2.电信规划研究院 工业和信息化部， 北京 100037 )

摘要：为延缓传感器网络寿命，减少网络能量消耗，通过分析LEACH路由算法的不足，提出一种基于簇首连任机制和多汇聚(sink)节点的无线传感器路由算法.即在成簇阶段采用一个簇首在多轮中连续担任簇首的机制，以减少每轮因选簇首而耗费的能量；在数据传输阶段使用多个sink节点接收簇首发来的信息，以降低通信中的能量消耗.仿真实验结果表明，该算法能有效延长网络生命周期且减少网络能量消耗.

关键词：无线传感器网络； 簇首； 连任； 多汇聚节点

收稿日期：2014-12-21

文章编号：1004-4353(2015)02-0156-04

中图分类号：TP393.1

The research of WSN routing algorithm based on cluster head reappointment and multiple sink nodes

WANG Mengjiao1,ZHANG Aili2，LI Yongzhen1*

( 1.NetworkandInformationSecurityLab.,Dept.ofComputerScience&Technology,

CollegeofEngineering,YanbianUniversity,Yanji133002,China; 2.TelecomPlanningInstitute,

MinistryofIndustryandInformation,Beijing100037,China)

Abstract：According to the analysis of the disadvantages of LEACH algorithm, the wireless sensor network clustering algorithm based on cluster head reappointment and multiple sink nodes was presented to prolong the network lifetime and reduce energy consumption. This paper uses cluster head reappointment technology in the network clustering stage can avoid to select cluster head nodes frequently that consumes energy. The proposed algorithm uses multiple sink nodes in wireless sensor network to receive the messages from the cluster heads and then reduce the energy consumption in communication. The simulation result indicates that the proposed algorithm is very energy-efficient, and it can prolong the lifetime of the sensor network and reduce the energy consumption of the network.

Key words： wireless sensor network; cluster head; reappointment; multiple sink nodes

无线传感器网络(wireless sensor network,WSN)是近年来基于数字电路、无线通信、微电机系统等学科发展起来的一个新的研究领域，在军事、医疗、环境等许多领域具有广泛的应用[1].但由于WSN中节点数量众多，且受成本、体积和功耗的限制，其处理能力、存储能量、通信能力及范围比普通计算机功能要弱小得多，因此减少其能量消耗具有重要意义.

在无线传感器网络路由协议中，LEACH(low energy adaptive clustering hierarchy)协议[2-4]是最具有代表性的一种协议.本文基于LEACH协议的不足，提出了基于簇首连任和多汇聚(sink)节点的WSN路由算法，并通过仿真试验验证了该算法的有效性.

1LEACH协议

在无线传感器分簇路由协议中，LEACH路由协议采用分布式和跨层设计的方法[5]，能有效减小网络的整体能耗，是优化能量和提高使用效率的路由协议代表之一.LEACH算法的整个执行过程以轮数为单位，周期性循环，每轮由簇建立阶段和数据传输阶段组成[6].

在簇建立阶段，用产生随机数与阈值比较的方法选择簇首节点[7].簇首节点向周围节点广播其成为簇首的信息，其他节点根据接收到的广播信息的强度来选择它所要加入的簇，并告知相应的簇首节点，从而动态地形成簇.

选择簇首节点的具体方法是：各节点产生一个[0,1]之间的随机数，若该数小于某一个阈值T(n)，则该节点成为簇首[8-9].T(n)的计算公式为

其中：p为期望的簇首节点数在所有无线传感器节点数中所占的百分比，r为当前轮数，G为在最后的1/p轮中未成为簇首节点的节点集合.1/p轮后为一个新的大循环，在1/p轮中所有传感节点都有机会轮流当选一次簇首.

在数据传输阶段，成员节点把数据发送给簇首节点，由簇首节点对数据进行必要的融合处理后发送到目的节点(sink节点).相比普通节点，簇首的工作量较大，能量消耗也多，原因是其不仅需要承担数据融合任务，还要保持与sink节点之间的数据传输.

通过以上分析可知，LEACH协议只有在源节点与目的节点之间距离较短，或者数据处理耗能较小的情况下才能体现出更好的能量有效性，其具体的不足主要表现为[10-12]：

1) 簇首负载不均衡.由于簇首的选举策略是随机的，可能造成簇首分布不均，簇成员个数也有较大差异，因而使得各簇首负载不均衡.

2) 网络能量分配不均衡.簇首离sink节点较远，会使这些节点耗能过多，造成网络能量分配不均衡.

3) 网络生存周期短.由于簇内频繁选择簇首，节点负载不均衡，算法可能会选本身已经能量消耗较多的节点作为簇首节点，这样就会使该节点的能量过早地消耗完，使网络生存周期变短.

2基于簇首连任和多sink节点的路由算法

本文提出的基于簇首连任和多sink节点的RSN路由算法的主要思想是让能量相对较高的簇首多次连续担任簇首，以此避免频繁选择簇首导致耗费不必要的能量；对簇首与距离较远的sink节点传输数据需要耗费较多能量的问题，通过在WSN中部署多个sink节点来减少其通信中的能量消耗.该算法包括网络成簇和数据传输两个阶段.

1) 网络成簇阶段

改进算法在成簇阶段利用簇首连任机制来减少能量消耗并延长网络生命周期.所有节点都有一个相同的概率被选为簇首，第1轮每个节点选择一个[0,1]之间的随机数,如果这个随机数小于或等于阈值T(n)，则这个节点就被选为簇首.第1轮成为簇首的节点连续担任多轮簇首后，重新按第1轮方式根据随机数选簇首，直至第1个节点能量耗尽为止.阈值T(n)的计算公式为

其中：p为期望的簇首节点数在所有无线传感器节点数中所占的百分比，通常被设为5%；rf为簇首连续担任簇首的轮数；r1是在rf(1/p)轮中的轮数值，每次新的rf(1/p)轮开始，r1的值就被设为0；G为在最后的1/p轮中未成为簇首节点的节点集合；n是网络中所有传感器节点的总数.

当簇首节点选择完毕，簇首节点广播其成为簇首的消息，普通节点依据收到信号的强弱计算其与各簇首之间的距离，并选择最近的簇首向其发送加入控制消息以加入该簇.簇首接收到该消息包以后，依据自己簇内的成员节点个数为每个成员节点分配数据传输时隙，创建TDMA调度时隙表，防止发送数据产生冲突，随后将该表传送给本簇内所有的成员节点.

2) 数据传输阶段

在大规模的或不规则的网络监测区域，若只有一个sink节点，难免会在数据传输阶段消耗过多的能量.为节省能量消耗、延长网络生命周期，本文拟采用2个sink节点来接收簇首节点发送来的融合后的监测消息，即采用多sink节点接收簇首发送数据机制.

数据从成员节点发送到簇首节点是按照LEACH协议方式进行的,簇首节点接收到来自成员节点发送的消息后对所有消息进行数据融合，然后把融合后的消息发送给sink节点.由于改进算法使用2个sink节点，所以簇首节点首先计算其与这2个sink节点的距离，并记下离自己近的sink节点的坐标位置，每轮融合后把数据发送到离自己近的sink节点.

当每个簇首都把融合后的数据发送到离自己近的sink节点后，数据传输阶段结束，同时这一轮算法也执行结束.无线传感器网络循环进行网络成簇阶段和数据传输阶段，直到所有节点都死亡为止.

3仿真实验

3.1仿真环境

本文采用MATLAB作为实验平台对改进算法进行仿真实验，通过与LEACH算法对比来检验本文算法的有效性.评价采用通用的标准，如能量消耗、网络生命周期(第1个节点死亡的轮数).

仿真实验中被监测区域的大小为200m×200m，网络中无线传感器的节点个数为200，所有传感器节点有相同的初始能量(1J)，簇首节点占所有节点的比例p大小为0.05，2个sink节点的位置坐标分别为(100,100)和(100,200).

3.2仿真实验结果与分析

图1和表1是改进算法与LEACH算法的第1个节点死亡的轮数(即网络生命周期)比较结果.从表1可知，改进算法第1个节点死亡的轮数是1436轮，而LEACH算法第1个节点死亡的轮数是1108轮，改进算法在网络生命周期上比LEACH算法提高了29.6%，这表明改进算法在网络生存周期方面比LEACH算法更有优势.

图1　改进算法与LEACH算法的生存周期比较

表1改进算法与LEACH算法的第1个节点死亡时间的比较

算法第1个节点死亡时间/轮LEACH算法1108改进算法1436

图2是改进算法与LEACH算法在能量消耗上的比较.从图中可知，改进算法的能量消耗曲线斜率没有LEACH算法的大，由此可知改进算法相比LEACH算法，能够减少能量消耗.这是因为改进算法在簇首选择阶段使一些簇首连续担任簇首，有效地节省了能量消耗；在数据传输阶段利用2个sink节点接收簇首节点发送来的消息，又减少了由于传输距离过长而消耗的能量.

图2　改进算法与LEACH算法的能量消耗比较

4结论

本文在分析LEACH协议的基础上，提出了基于簇首连任和多sink节点的WSN路由算法.改进的算法主要包括：① 在网络成簇阶段，利用簇首连续担任多轮的机制，避免频繁选择簇首，节省簇首能量消耗.② 在数据传输阶段，基站使用2个sink节点接收簇首发送来的数据，减小簇首传输距离.仿真实验结果表明，改进算法比LEACH算法更高效和节能，能有效延长网络生存周期.本文在研究中没有对sink节点的部署问题进行研究，今后将对此作进一步研究.

参考文献：

[1]任丰原,黄海宁,林闯.无线传感器网络[J].软件学报,2003,14(7):1282-1291.

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

[3]刘强,毛玉明,李龙江.随机分布WSN中sink节点部署研究[J].计算机工程与科学,2013,35(2):49-55.

[4]刘强,毛玉明,李龙江.无线传感器网络中多sink节点优化部署方法[J].计算机应用,2011,31(9):2313-2316.

[5]陈炳才,么华卓,杨明川.一种基于LEACH协议改进的簇间多跳路由协议[J].传感器学报,2014,27(3):373-377.

[6]陈志雄,潘耘,李嫣.用改进蚁群算法求解无线传感器网络多sink节点关联问题[J].计算机应用与软件,2012,29(2):246-249.

[7]陶志勇,蒋守凤.负载均衡的无线传感器网络的分簇路由算法[J].计算机工程与应用,2015,3(1):1-5.

[8]Sakkottai S, Rappaport T S, Karlsson P C. Cross layer design for wireless network[J]. IEEE Communications Magazine, 2003,41(10):74-80.

[9]胡艳华,张建军.LEACH协议的簇头(LEACH-M)改进算法[J].计算机工程与应用,2009,45(34):107-109.

[10]Meenakshi Sharma, Kalpana Sharma. An energy efficient extended LEACH (EEE LEACH)[C]//2012 International Conference Communication System and Network Technologies. Rajkot, India, 2012:377-382.

[11]陈建明,王青海,路建军.自适应分簇拓扑算法EC-LEACH的研究[J].测试技术学报,2008,22(6):538-543.

[12]李岩,张曦煌,李彦中.LEACH-EE-基于LEACH协议的高效聚类路由算法[J].计算机应用,2007,27(5):1103-1105.