异构网络中基于DEEC的非均匀分簇路由算法

尚 静，董增寿，康 琳

(太原科技大学 电子信息工程学院,太原 030024)

近年，随着微机电系统(MEMS)、片上系统(SoC)、无线通信以及低功耗嵌入式技术的快速发展，无线传感器网络(WSNs)得到了更加广泛的应用[1]。传感器网络面临的主要问题是能量受限，而分簇路由是解决此问题的关键技术之一，它可以增加网络的可扩展性和延长网络的生存周期，故得到了广泛的关注和研究。

即使节点在开始时具有相同的能量，随着通信的时间和新节点加入等因素的影响，节点的能耗不可能均匀。所以无论节点的初始能量是否相同，传感器网络更有可能是一个能量多级异构的网络[2]。LEACH[3]是第一个含有成簇思想的无线传感器网络路由协议。其主要思想是通过“轮”，随机循环的进行簇头的选举和簇的重构，从而将网络的能耗均衡的分配到每个节点上，有效的提高了网络的生存周期。但 LEACH也存在一些缺陷，如：簇头分布不均，未考虑节点的剩余能量、易造成能量空洞现象[4]等。SEP[5]算法基于二级异构网络，即网络中存在高级节点和普通节点，算法为不同初始能量的节点分配不同的轮转周期来实现延长网络稳定周期的目的，但SEP算法的簇首选举只是基于节点的初始能量，未考虑节点的剩余能量。DEEC[2]算法将二级异构网络扩展到多级异构网络，在SEP算法的基础上根据节点的剩余能量水平和网络的异构性来决定簇首的选举，既能充分利用网络的异构性又能适应节点能量的变化。IDEEC[6]算法是在DEEC基础上对阈值公式进行了改进并对网络平均剩余能量进行了精化求解。上述算法虽然在很大程度上提高了网络的生存周期，但是均无法避免能量空洞现象的发生。UCS[7]是第一个提出以非均匀分簇的方法来均衡簇头间的负载，算法以每簇头能耗相同为目标，根据期望的中继负载来改变簇的大小，实现非均匀分簇。但UCS假设簇头位置是事先设计好的，并且在网络死亡之前分簇不变，不适合随机部署的WSN网络，有一定的局限性。EEUC[8]算法为不同节点设置不同的竞争半径，竞争半径的大小与节点到基站的距离成正比。EEUC的缺陷是一些参数需要人工选取，随机性大，操作困难。

本文一方面将网络的异构性与非均匀分簇思想结合起来，既充分利用了网络多级异构的优势又能克服能量空洞现象；另一方面对DEEC算法簇形成阶段进行了改进，节约了节点的能耗。有效的提高了网络生存时间和数据传输量。

1 网络模型

1.1 节点模型

假定N个传感器节点均匀的分布在M*M区域中，sink节点位于区域的中心。其他基本假设如下：

1)所有分布的节点都是静止的；

2)传感器节点的能量是有限的，而sink节点的能量是无限的或是可以补充的；

3)每一个节点有独立的ID号；

4)传感器节点和sink节点可以任意改变它们的传输半径。

1.2 能耗模型

节点无线传输的能耗模型采用和文献[2]中相同的一阶无线电模型。

图1 能量消耗模型
Fig.1 Energy consumption model

如图1所示，发送数据能耗、接收数据能耗，其计算公式如下：

(1)

ERx(k)=kEelec

(2)

其中Eelec表示每发送或者接收1比特数据电路的能耗；k表示传输数据包的长度；εfs、εmp分别表示在自由空间模型和多径衰减模型下功率放大器的能耗系数。当d

(3)

2 EIDEEC算法

2.1 簇头选举阶段

2.1.1 阈值公式

(4)

(5)

其中，d为节点Si与sink节点之间的距离，M为区域大小。

由于簇间传输为单跳形式，故远离sink的簇头簇间能耗更大，更容易过早死亡，所以我们为其分配较少的簇成员节点来弥补簇间传输能耗。在改进的簇头概率中，节点能量越大且距离sink越远的节点成为簇头的概率越大，即实现非均匀分簇。

为了让剩余能量更多的节点优先成为簇头，将节点剩余能量与网络平均能量之比和最优簇头数因子加入到阈值公式中。将阈值公式调整为：

(6)

其中最佳簇头数为：

(7)

dtoBS表示网络中簇头到基站的平均距离，假定节点是均匀分布的，有[8]

(8)

从公式(6)可看出，剩余能量多的节点成为簇头的概率大，这样可以提高能量利用率，延长网络的生存周期。

2.1.2 网络的平均能量

(9)

2.1.3 簇头选举的调整

在EIDEEC选择簇头时，首先将能量大于网络平均能量的节点作为候选簇头，这样可以使剩余能量多的节点优先成为簇头，延长网络的生存周期。

2.2 簇形成阶段

在传统算法中，非簇头节点选择距离自身最近的簇头加入来形成簇。在EIDEEC高效路由算法中，既考虑了节点与簇首的距离，也考虑了节点与sink的距离。当节点到sink的距离小于节点到其最近簇头的距离时，节点直接将感知到的数据发送给sink节点。以这样的方式，既节省了簇头的能耗，也节省了成员节点的能耗。即表1为节点传输方案。

表1 节点传输方案
Tab.1 Node forwarding method

状态条件直接传输dtosink

dtosink为节点到sink的距离。d1是判定节点Si采用直接传输或簇头传输的阈值。表2说明了EIDEEC算法的工作过程。

表2 EIDEEC算法
Tab.2 The Algorithm of EIDEEC

EIDEEC算法的簇头选举与簇形成阶段1．簇头选举阶段01fori=0：1：n02ifS(i)．E>Ea//节点为候选簇头03ifi∈G04ifRa≤T(Si)//节点产生的随机数小于概率阈值05i∈cluster//节点当选为簇头06endif07endif08endif

09endfor2．簇形成阶段01fori=0：1：n02if(type(i)=’Normal’&S(i)．E>0)03d1=节点i与sink的距离04d2=节点i与最近簇头C的距离05ifd1

3 仿真结果分析

这节利用MATLAB仿真平台对本文提出的EIDEEC高效路由算法与经典的LEACH、DEEC、IDEEC进行了比较，来验证EIDEEC的优越性。主要在网络生命周期、数据传输量和节点剩余能量三方面进行对比。

3.1 仿真参数设置

假设100个传感器节点随机分布在100*100 m的区域内，其他主要仿真参数参考表3.

表3 仿真参数
Tab.3Thesimulationparameters

参数数值sink(50，50)E00．5JEelec50nJ/bitεfs10pJ/bit/m2εmp0．013pJ/bit/m4k4000bitsa1pkoptN

3.2 仿真结果及分析

如图2、图3、图4所示，分别比较了LEACH，DEEC，IDEEC，EIDEEC四种算法在执行了5000轮之后，网络生存周期、数据传输量以及节点平均剩余能量的变化。在网络生存周期方面，我们把节点数死亡50%的时间定义为网络生存周期的结束。

如图2及表4所示，LEACH在执行1350轮之后，50%节点死亡；DEEC算法由于根据不同剩余能量的节点采用不同的轮数，比LEACH延长了264轮；IDEEC算法在阈值公式中考虑了剩余能量并对网络生存周期精化求解，生存周期延长了730轮；本文提出的EIDEEC算法，不但在簇头选举阶段增加了平均能量限制和调整了簇头概率，而且在簇形成阶段改善了节点数据传输方式，节约了节点耗能，所以生存周期也延长到了2949轮。

如图2及图4所示，分别为四种算法在数据接收量和节点平均剩余能量的对比，可看出本文提出的EIDEEC算法较其他三种算法在数据接收量和节点平均剩余能量方面均有所提高。

综上比较，在网络生存周期方面，EIDEEC算法比LEACH算法提高了118%，比DEEC算法提高了83%，比DEEC算法提高了26%.在数据接收量方面，EIDEEC算法比IEEEC算法提高了25%.在节点平均剩余能量方面，EIDEEC算法比IEEEC算法提高了33%.

图2 生命周期比较
Fig.2 Comparison of number of death nodes表4 死亡节点轮数比较Tab.4 Round number of the death node

算法(轮)LEACHDEECIDEECEIDEEC首个节点死亡84310071277155150%节点死亡1350161423442949所有节点死亡2035223736054628

图3 数据接收量比较
Fig.3 Comparison of the receiving data packets

图4 节点平均能量比较
Fig.4 Comparison of average remaining energy for nodes

4 结论

对DEEC算法进行改进，提出更节能高效的EIDEEC算法。该算法通过改变远离sink节点的簇头轮数来克服IDEEC中易出现的能量空洞现象；且通过节点与网络平均能量比较，使得剩余能量较大的节点成为簇头概率较大；同时在构簇阶段的调整，减少了节点和簇头的能耗。通过仿真结果证明，与LEACH、DEEC、IDEEC算法相比，EIDEEC的网络生存周期、数据传输量、能量利用率均有明显的提升。但改进算法仍采用簇间单跳的传输方式，由于节点的传输半径和能量的限制，可能会造成距离sink较远的簇头无法将数据传输给sink节点，在接下来的工作中，应设计一种新型的簇间路由方式来克服此缺陷。

参考文献：

[1] 王占魁.基于不均匀分簇的LEACH协议的改进研究[D].武汉：武汉理工大学，2011.

[2] QING L, ZHU Q, WANG M.Design of a distributed energy-efficient clustering algorithm for heterogeneous wireless sensor networks[J].Computer Communications, 2006, 29(12)：2230-2237.

[3] HEINZELMAN WB, CHANDRAKASAN A P, BALAKRISHNAN H.An Application Specific Protocol Architecture for Wireless Microsensor Networks[J].IEEE Transactions on Wireless Communication.2002，1(4)：660-670.

[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：3005-3014.

[5] SMARAGDAKIS G, MATTA I, BESTAVROS A.SEP： A stable election protocol for clustered heterogeneous wireless sensor networks[J].Proceeding of 2nd International Workshop on Sensor and Actor Network Protocol and Applications，2004.

[6] 郑志明, 郑燕娥, 李智仁.一种基于DEEC的异构节能分簇改进算法[J].西华大学学报：自然科学版, 2016, 35(1)：85-88.

[7] CHEN G, LI C, YE M, et al.An unequal cluster-based routing protocol in wireless sensor networks[C]// Wireless Networks, 2007, 15(2)：193-207.

[8] LI N C, YE N M, CHEN N G, et al.An energy-efficient unequal clustering mechanism for wireless sensor networks[J].// IEEE International Conference on Mobile Ad hoc and Sensor Systems Conference.IEEE Xplore, 2005：598-604.

[9] 谢琳, 彭舰, 刘唐.基于多级能量异构的无线传感器网络能量空洞避免策略[J].计算机应用, 2016, 36(6)：1475-1479.

[10] JIA D, ZHU H, ZOU S, et al.Dynamic Cluster Head Selection Method for Wireless Sensor Network[J].IEEE Sensors Journal, 2015, 16(8)：2746-2754.

[11] ABO-ZAHHAD M, AHMED S M, SABOR N, et al.Mobile Sink-Based Adaptive Immune Energy-Efficient Clustering Protocol for Improving the Lifetime and Stability Period of Wireless Sensor Networks[J].IEEE Sensors Journal, 2015, 15(8)：4576-4586.

[12] CHOI W, DAS S K.Trade-off between coverage and data reporting latency for energy-conserving data gathering in wireless sensor networks[C]// IEEE International Conference on Mobile Ad-Hoc and Sensor Systems.IEEE, 2004：503-512.

[13] SAINI P, SHARMA A K.E-DEEC- Enhanced Distributed Energy Efficient Clustering scheme for heterogeneous WSN[C]// International Conference on Parallel Distributed and Grid Computing.IEEE, 2010：205-210.

[14] KAUR S, MIR R N.Clustering in Wireless Sensor Networks-A survey[C]// International Journal of Computer Network and Information Security.2016：1-9.

[15] 高瑜, 徐玉斌.基于节点权值的簇头选举优化算法[J].太原科技大学学报, 2011, 32(6)：427-431.