郑志明， 郑燕娥，李智仁

(1.湄洲湾职业技术学院，福建 莆田 351254；2.仰恩大学工程技术学院，福建 泉州 362014)



一种基于DEEC的异构节能分簇改进算法

郑志明1， 郑燕娥2，李智仁1

(1.湄洲湾职业技术学院，福建 莆田 351254；2.仰恩大学工程技术学院，福建 泉州 362014)

摘要：针对无线传感器网络中因有限能量利用不佳从而导致网络生存周期缩短的问题，提出一种基于DEEC的优化能量利用的改进算法(IDEEC)。该算法一方面对DEEC的阈值进行调整，在DEEC的阈值中加入剩余能量与网络平均剩余能量的比值以及最优簇头数，以增加剩余能量多的节点成为簇头的概率，另一方面采用精确化方案求解网络平均剩余能量，同时采用簇内成员节点的调度机制让冗余节点进入休眠模式以节约网络能耗、延长网络生存周期。仿真结果表明，IDEEC的能耗比LEACH降低60.6%，比DEEC降低47.9%，网络生存时间比LEACH提高61.9%，比DEEC提高49.1%。

关键词：多级能量异构；DEEC；簇头选举算法优化；成员节点调度机制

无线传感器网络(WSN)是通过分布密集的传感器节点间的协作以实现感知、采集、融合、转发和处理信息的一种自组织网络。WSN依据传感器节点是否具备异构特征分为同构和异构2种，异构WSN更能满足实际应用需求。传感器节点本身能量、处理及存储能力受限，因此，通过研究高效节能的路由算法来延长整个网络寿命具有重要的现实意义。能量利用率成为WSN性能评价的一项重要指标，因而提高能量利用率的路由算法也成为WSN研究的热点。目前,无线传感器网络中的节能路由算法有SPIN[1]、 LEACH[2]、PEGASIS[3]、FA[4]、ENCAST[5]、DEEC[6]等。在现有的节能算法上致力于优化研究的学者数不胜数，例如文献[7-11]等。本文在分析多级能量异构DEEC算法的基础上，提出一种提高能量利用率的IDEEC算法。

1相关研究

1.1　DEEC算法

DEEC是一种基于LEACH并适用于多级能量异构网络的分布式高能效分簇路由算法。LEACH是首个基于簇分层的低功率路由算法，它采用周期性轮转选举簇头，各节点成为簇头的概率相同，能耗均衡；但没有考虑网络中簇头分布不均、节点的剩余能量、簇头产生数目不稳定等问题。在DEEC中，算法根据节点的当前剩余能量与网络平均能量的比值来定义节点成为簇头的概率，综合考虑节点的剩余能量，能更有效均衡能耗，尽可能延长网络生存时间；但DEEC使用估算方案求解网络平均剩余能量，求解的前提是网络能耗均匀，这与实际并不相符，从而削弱了DEEC的实用性。

1.2　DEEC算法的簇构建过程

1.2.1簇头的选取

(1)

(2)

由于R的值难于精确获取，网络能耗均匀的假设不符合实际情况，大大削弱了该算法的实用性。每一轮由每个节点先算出本身成为簇头的概率，接着随机生成一个大于0而小于1的数，如果该数小于其算出的阈值，则被选为簇头节点，否则为簇内成员节点。阈值的计算公式[1]为

(3)

其中G为最后1/p轮中没有当选为簇头的节点集。将由式(1)求出的pi值代入式(3)中，可知如果节点的剩余能量越多，其阈值也越大，那么节点成为簇头的概率也相应提高。

1.2.2簇的形成

簇头节点一旦确定了，便向周边节点广播“加入簇”的消息(簇头ID号及剩余能量)，非簇头节点收到此消息时，就发送请求加入的消息给与自己有最强信号的簇头，随后簇头向簇内成员节点广播TDMA时隙以便它们利用该时隙与其进行数据传输，其他时刻则进入休眠模式以减少能耗。

2异构网络能耗模型

本文采用文献[10]所述的能耗模型，节点的能耗主要有3种：发送数据能耗ETx(l,d)、接收数据能耗ERx(l)、数据融合能耗Ec。其计算公式为：

(4)

ERx(l)=lEelec；

(5)

Ec=(M+1)lEDA。

(6)

3IDEEC节能算法

IDEEC(improvedDEEC)节能算法主要包含3方面：1)调整DEEC的阈值，在阈值的计算公式中加入节点剩余能量与当前网络平均剩余能量的比值以及最优簇头数，以增加剩余能量多的节点成为簇头的概率，从而均衡网络能耗；2)对网络的平均剩余能量进行精化求解，克服DEEC估算方案的不足；3)设置簇内成员节点的调度机制，让冗余节点进入休眠模式，进一步节约节点能耗。

1)对DEEC的阈值进行调整。为让剩余能量多的节点优先成为簇头，在阈值计算公式中引入节点的当前剩余能量和网络平均剩余能量的比值以及最优化的簇头数。调整后的阈值计算公式为：

(7)

(8)

其中kopt为最优状态时的簇头数。簇头数过少或过多都将导致网络能耗的增加，因此只有合理优化簇头数，才能有效节约网络能耗，从而提高节能效果。

2)网络平均剩余能量的精化求解。假如网络的初始总能量为Etotal，第1轮簇头选举中，网络的平均剩余能量为

(9)

从第2轮选举开始，簇内活动节点将要发送的数据携同其剩余能量一并发给所属的簇头，簇头计算出本簇当前总剩余能量，并将其告之于其他簇头，通过统计区域内失效以及休眠节点数计算出下一轮活动节点数，从而计算出当前网络平均剩余能量。一般情况下，每比特数据传送所消耗的能量为50 nJ。由于在信息交换过程中只需加入剩余能量值，其数据量极小且只需在网络重新分簇时进行，因此其通信能耗在整个网络的使用中可以忽略不计。

3)簇内成员节点的调度机制。现实中所应用的网络可能出现在地形险要而不利于后期维护的区域，这样一般会通过密集部署传感器节点来提升网络的容错能力。通常多个邻近的节点存在信息检测的冗余，这些冗余节点也必然增加数据融合能耗及通信时延。本文采用文献[12]的“簇内覆盖思想”,由式(10)近似计算出各簇头满足实际应用要求所需最少的覆盖节点数k，再依据剩余能量由高至低的次序从簇内选出k-1个节点作为本轮的工作节点，将冗余节点设置为休眠模式，以待进行下一轮的接替工作，从而节约节点能量消耗。满足覆盖率的簇内节点数的计算公式[11]为

(10)

式中：η为满足实际应用要求所期望达到的覆盖率；k为最少的活动节点数；r为节点能够感知到的半径；A为网络区域的面积。

4仿真结果分析

本文利用MATLAB仿真实现了LEACH、DEEC和IDEEC算法，采用2组不同仿真参数，从网络能耗和网络生存时间这2方面进行性能分析。假定异构网络模型的基本特征保持不变，如节点数(100个)、仿真轮数(4 000)、监测区域(100×100)、基站位置(50，110)、Eelec(50 nJ/bit)、εfs(10 pJ/bit/m2)和εmp(0.013 pJ/bit/ m4)。2组仿真实验不同的参数体现为：第1组，初始能量取值区间[0.5，1.5]、数据包长度(450 byte)、d0(80 m)，其仿真结果如图1(a)、图2(a)所示；第2组，初始能量取值区间[1，2]、数据包长度(400 byte)、d0(85 m)，其仿真结果如图1(b)、图2(b)所示。

图1为2组仿真实验的网络能耗曲线，它们具有共同的特征：随着轮数的增加，能耗逐渐耗尽，且IDEEC的能耗曲线的斜率相对于LEACH和DEEC都较小，说明IDEEC能量消耗比LEACH和DEEC要少。图1(a)中LEACH在1 780轮左右能量全部耗尽，DEEC在1 900轮左右， 而IDEEC在2 980轮左右，其能耗比LEACH降低67.4%，比DEEC降低56.8%；图1(b)中LEACH在1 980轮左右能量全部耗尽，DEEC在2 150轮左右， 而IDEEC在3 180轮左右，其能耗比LEACH降低60.6%，比DEEC降低47.9%。可见，IDEEC的能量利用率较好。

图2为2组仿真实验的网络生存时间曲线，它们具有共同的特征：IDEEC在较大轮数时才逐渐出现死亡节点，说明IDEEC的网络生存时间明显比LEACH和DEEC长。图2(a)中LEACH在1 800轮左右所有节点死亡，DEEC在1 910轮左右，而IDEEC在3 005轮左右才全部死亡，其网络寿命比LEACH提高66.9%，比DEEC提高57.3%；图2(b)LEACH在2 100轮左右所有节点死亡，DEEC在2 280轮左右，而IDEEC在3 400轮左右，其网络寿命比LEACH提高61.9%，比DEEC提高49.1%。可见，IDEEC网络生存时间较长。

5结束语

本文对DEEC算法进行改进，提出一种IDEEC算法。该算法克服了DEEC估算方案求解网络平均剩余能量的不足，在DEEC的阈值中加入剩余能量与网络平均剩余能量的比值以及最优簇头数,同时采用簇内成员节点的调度机制，多方位节约节点能耗，以延长网络生存周期。仿真结果表明，IDEEC的能量利用率和网络生存时间均有明显提升。

参考文献

[1]Heinzelman W, Kulik J, Balakrishnan H. Adaptive Protocols for Information Dissemination in Wireless Sensor Networks[C]//MobiCom '99 Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking. New York, NY, USA: ACM,1999:174.

[2]Heinzelman W, Chandrakasan A, Balakrishnan H. Energy-efficient Communication Protocol for Wireless Sensor Networks[C]//Proceedings of the Hawaii International Conference on System Sciences. Piscataway, USA：IEEE, 2000:175.

[3]Lindsey S, Raghavendra CS.PEGASIS: Power-efficient Gathering in Sensor Information Systems[J]. Aerospace Conference Proceedings, 2002,3:1125.

[4]Chang J H, Tassiulas L. Maximum Lifetime Routing in Wireless Sensor Networks[J].IEEE/ACM Trans on Networking, 2004,12(4):609.

[5]Zou S, Nikolaidis I, Janelle J Harms. ENCAST: Energy-critical Node Aware Spanning Tree for Sensor Networks[C]//Communication Networks and Services Research Conference, Proceedings of the 3rdAnnual.[S.l.]:IEEE，2005:249.

[6]Li Qing, Zhu Qingxin, Wang Mingwen. Design of a Distributed Energy-efficient Clustering Algorithm for Heterogeneous Wireless Sensor Networks[J].Computer Communications, 2006,29:2230.

[7]陈静,沈鸿.MELEACH一个高效节能的WSN路由协议[J].传感技术学报,2007,20(9):2089.

[8]王晓喃,高德民,徐江.高效节能的无线传感器网络路由协议设计与实现[J]. 计算机应用研究,2010,27(8):3107.

[9]申志远,刘方爱,侯冰俏,等.节能高效的无线传感器网络非均匀分簇路由协[J].传感器与微系统.2013,32(12):67.

[10]魏春娟,杨俊杰，张志美.一种分布式能量有效的无线传感器网络分簇路由协议[J].传感技术学报,2013,26(7):1014.

[11]杨东勇,陈晓倩,顾东袁.一种节能的无线传感器网络路由协议的设计与实现[J].计算机工程与科学,2010,32(4):110.

[12]Choi W,Das S K.Trade-Off Between Coverage and Data Reporting Latalcy for Energy-Conserving Data Gathering in Wireless Sensor Networks[C]∥Mobile Ad-hoc and Sensor Systems, 2004 IEEE International Conference on.[S.l.]:IEEE，2004：503.

(编校：饶莉)

An Improved Clustering Algorithm Based on DEEC for Heterogeneous Energy Saving

ZHENG Zhiming1，ZHENG Yane2，LI Zhiren1

(1.MeiZhouWanVocationalTechnologyCollege,Putian351254China;

2.CollegeofEngineeringandTechnology,Yang′enUniversity,Quanzhou362014China)

Abstract:Aimed at the problem that the improper use of the limited energy in wireless sensor networks can lead to the shortening of the lifetime of the network, an improved algorithm based on DEEC is proposed for the optimization of energy utilization. On the one hand, the algorithm adjusts the threshold of DEEC, and adds the ratio of residual energy and the average residual energy of network as well as the optimal number of cluster heads in the DEEC threshold in order to increase the probability of more residual energy node to be cluster head. On the other hand, the average residual energy of the network is solved by using the exact solution, and the scheduling mechanism of the cluster member nodes is used to make the redundant nodes enter the sleep mode to save the network energy consumption and prolong the network lifetime. The simulation results show that the energy consumption of the improved algorithm reduces no less 60.6% than that of LEACH, and no less 47.9% than that of DEEC, and the survival time of the network is higher 61.9% than that of LEACH, and higher 49.1% than that of DEEC.

Keywords:multilevel energy heterogeneous; DEEC; cluster head election algorithm optimization; member node scheduling mechanism

doi:10.3969/j.issn.1673-159X.2016.01.018

中图分类号：TP212.9

文献标志码：A

文章编号：1673-159X(2016)01-0085-4

基金项目：湄洲湾职业技术学院2016年科研项目。

收稿日期：2015-08-29

第一作者：郑志明(1980—)，男，讲师，硕士，主要研究方向为无线传感网、信息安全。E-mail：48266269@qq.com

·计算机软件理论、技术与应用·