面向异构WSNs的基于能量感知的簇路由算法*

焦克莹,郭 强

(1.驻马店职业技术学院,河南 驻马店 463000;2.黄淮学院国际教育学院,河南 驻马店 463000)

面向异构WSNs的基于能量感知的簇路由算法*

焦克莹1*,郭 强2

(1.驻马店职业技术学院,河南 驻马店 463000;2.黄淮学院国际教育学院,河南 驻马店 463000)

有效地使用传感节点的能量,进而延长网络寿命成为设计无线传感网路由协议的一项挑战性的工作。为了延长网络,现存的多数簇路由是面向同构网络。为此,提出分布式能量感知的异构WSNs非均匀分簇路由DEAC(Distributed Energy Aware unequal Clustering)算法。DEAC算法是以EADUC(Energy Aware Distributed Unequal Clustering)为基础,并进行优化。与EADUC不同,DEAC算法从簇头竞选机制、簇间多跳通信中的下一跳转发节点的选择策略以及自适应的节点通信半径的设置三方面进行优化。在簇头竞选机制中,采用退避算法,利用节点的剩余能量以及邻居节点的平均能量设置延时时间;在选择下一跳转发节点时,建立节点的关于能量的度量函数,选择具有最大剩余能量的节点作为下一跳;而在设置节点通信半径时,考虑了距离、剩余能量以及邻居节点数信息。仿真结果表明,与EADUC协议相比,提出的DEAC算法能够有效地延缓第1个节点失效的时间,减少了能耗,扩延网络寿命。

异构无线传感网;路由;能量感知;非均匀簇;网络寿命

通着现代电子技术的发展,无线传感网络 WSNs(Wireless Sensor Networks)在多类应用中得到广泛使用[1-2]。然而,WSNs受到多类资源的限制,包括能量、功耗、存储容量以及传输距离。其中,能量的有限性是目前WSNs最主要的资源限制。而部署WSNs的根本目的就是收集监测区域数据。若节点的能量耗尽,则该节点就成为失效节点,一旦失效,节点便无法收集数据。这不仅缩短了网络寿命,还产生覆盖空洞,这直接影响了数据收集,也失去对区域监测的目的。

目前,研究人员针对WSNs的能量受限问题提出了不同处理算法[3-5]。其中,簇路由技术得到广泛关注,它能够有效地完成数据传输,并提高了网络能量利用率。基于簇的网络的模型如图1所示。多个节点形成不同的簇,每个簇产生一个簇头,簇头收集簇内成员数据,经处理后传输基站。

图1 网络模型

基于分簇路由可提高网络寿命[3]。文献[6]提出了LEACH协议。文献[7]提出了分布式能量有效簇DEEC(Distributed Energy-Efficient Clustering)协议。DEEC协议采用了两级能量结构,每个节点依据自己的剩余能量选择自己的簇头。DEEC协议仅从自己的剩余能量选择簇头,存在不足。为此,文献[8]提出了改进算法,提出DDEEC(Developed DEEC)协议。DDEEC协议自适应地选择簇头,进而实现节点能量消耗的平衡。文献[9]也提出了DEEC的改进协议,记为HUCL协议。HUCL协议采用了三级能量结构,将节点分为三类。每类节点初始能量不同。但是,HUCL协议并没有依据节点的能量水平改变簇头的选择概率。

此外,文献[10]提出了能量感知的分布式非均匀簇EADUC(Energy Aware Distributed Unequal Clustering)路由。EADUC协议采用非均匀的簇算法,进而降低了能量消耗速率。但是该协议在选择簇头以及簇形成阶段,只考虑了节点本身的剩余能量和离基站的距离信息,并没有充分考虑节点所处区域的能量信息以及区域的节点数。

为此,本文基于EADUC协议,并面向异构网络,提出分布式能量感知的异构WSNs非均匀分簇路由DEAC(Distributed Energy Aware unequal Clustering)算法。DEAC算法对EADUC进行了三点优化。首先,在簇头选择阶段,基于区域剩余能量设置延时退避机制;其次,采用自适应通信半径策略,形成非均匀化的簇;最后一点的改进体现于簇间多跳通信中的下一跳节点选择算法。通过从这三方面的改进,提高了网络寿命,降低了节点消耗速度。仿真结果表明,改进后的DEAC有效地减少能量消耗,即延缓了第1个失效节点所发生的时间,也提高了活动节点数。

1 系统模型

考虑如图1所示的系统模型,N个传感节点随机分布于M×M感测区域。一旦部署节点后,传感节点和基站就不再移动,即静态网络。基站远离感测区域,并且所有传感节点知道基站的位置。

此外,考虑异构网络,即网络内所有传感节点具有不同的特性。本文假定所有节点的初始能量不同,即节点的初始能量不完全相同,同时,所有节点的传输距离不相同,而同构网络的传输距离相同。

每个传感节点能够依据传输距离调整自己的传输功率,这有利于提高节点的能量利用率,可延长网络寿命,但是它们的位置未知,它们可以依据从基站接收的信号功率估计离基站的距离。同时,假定网络内的链路是对称的[11-12]。N个传感节点形成不同的簇,簇头能够直接与基站通信。在簇内,簇内成员节点将感测数据传输至簇头,并由簇头收集、融合。

1.1 能量消耗模型

能量消耗模型如图2所示。在相距为d两节点间传输l比特的数据信息,消耗的能量如式(1)所示。当传输距离d小于门限值dco时,就采用自由空间传输模型,若传输距离d大于门限值dco时,就采用多径传输模型。

(1)

式中:Eelec表示运行发射器或接收器固定的能量消耗,εfs、εmp分别表示发射器在自空间、双径传播模型(two ray ground model)的单位功率放大器的能量消耗[13]。在NS2的仿真场景中,使用式(2)计算dco:

(2)

式中:λ为波长、κ为系统损耗。ht、hr分别表示发射天线和接收天线的增益系数。相应地,对于接收l比特的数据包,所消耗的能量ERx(l):

ERx(l)=lEelec

(3)

图2 无线电能量消耗模型

2 DEAC

将时间划分等间隔的轮。在每一轮内执行一次DEAC算法。DEAC协议主要两个阶段:簇建立阶段和稳定阶段。而簇建立阶段又分为3个子阶段,第1个子阶段用于收集邻居信息;第2个子阶段选择簇头;最后一个子阶段形成簇,如图3所示。

图3 DEAC协议的时间模型

2.1 簇建立阶段

簇建立阶段由邻居信息收集、簇头选择和簇形成3个子阶段组成。这3个子阶段的时限分别为T1、T2、T3。

2.1.1 邻居信息收集

每个节点广播通告消息Know_Msg,其包含节点的ID、剩余能量。邻居内所有节点将接收到该通告消息。然后,每个节点通过邻居内节点的能量信息,计算邻居区域的平均能量Eavg_res:

(4)

式中:Ni表示节点Si的邻居数、Er(Sj)表示Si的邻居节点Sj的剩余能量。

2.1.2 簇头选择

完成了邻居信息收集后,即T1结束后便进入簇头选择阶段。采用延时退避机制广播簇头竞争消息Com_Head_Msg。为了避免竞争,每个节点依据自己的剩余能量和邻居区域的平均能量,设置不同的延时时间t:

(5)

式中:Er表示节点的剩余能量。而Vr表示在[0.9,1]区内的随机值,用于降低不同节点具有相同的延时时间的概率,即减少节点同时发送Com_Head_Msg消息的概率[14]。在自己的延时退避期间内,若没有收到其他节点所发送的Com_Head_Msg消息,即自己的延时时间最短,那么自己就成为簇头。否则,就不转发Com_Head_Msg消息。

2.1.3 簇形成

一旦产生了簇头,便进入簇形成阶段。簇头广播自己成为簇头的宣告消息Acc_Msg。邻居节点(非簇头节点)收到后,选择离自己最近的簇头作为自己的簇头,即加入该簇,成为该簇成员,同时向该簇头发送加入消息Join_Msg,进而形成簇。

(6)

式中:α、β、γ均为权重系数,且在[0,1]区间内。Rmax表示最大的通信半径。dmax、dmin分别表示节点离基站的最大、最短距离。Einit为节点的初始能量。Ni表示节点Si的邻居节点数,相应地Nmax表示最大的邻居节点数。

2.2 稳定阶段

当构建了簇后,便进入稳定阶段,开始进行数据传输。在簇内,成员节点将自己所感测的数据直接传输至簇头,由于在同一个簇,只需一跳就能完成数据传输,因此也称为簇内通信。簇头收集簇内成员数据后,便进行数据融合,最后传输到基站。

依据离基站的距离的不同,簇头要么以直接或间接转发方式向基站传输数据。如果离基站的距离大于门限值dth,就得借助其他簇头节点进行转发,形成簇间的多跳通信。否则,就采用直接传输。对于簇间多跳通信,需要通过多跳节点转发才能完成数据的传输。因此,下一跳节点的选择成为簇间通信的关键。

最初的EADUC协议是通过距离信息决策下一跳转发节点。假定簇头CHi需要向基站发送数据,并需要从其邻居节点中选择一个节点作为下一跳转发节点。那么它就计算邻居节点的成本值Cj(假定邻居节点为Sj),如式(7)所示:

Cj=d2(CHi,Sj)+d2(Sj,BS)

(7)

式中:d(CHi,Sj)、d(Sj,BS)分别表示CHi离Sj、Sj离基站的距离。成本越低,节点成来下一跳节点的概率就越大。最终,簇头CHi选择成本最低的节点作为下一跳。

与EADUCE协议不同,提出的DEAC协议采用不同的策略选择下一跳节点。提出的DEAC协议在选择下一跳节点时不仅考虑了距离信息,而且还考虑了剩余能量以及邻居节点数,并将这些信息量化为能量,最后选择剩余能量最多的节点作为下一跳转发节点。因此,DEAC协议引入了变量En_resj(假定邻居节点为Sj):

(8)

式中:Mj表示簇头CHj内的成员节点数。Eagg表示簇头融合数据所消耗的单位能量。依据式(8)可知,En_resj越大,意味着节点的剩余能量越多。簇头CHi就选择剩余能量最多的节点作为下一跳节点。

2.3 与EADUC协议的不同之处

作为基于EADUC的改进协议,DEAC算法与EADUC有以下3点不同。①在簇头选择过程中,充分考虑了剩余能量,并采用延时退避机制,如式(5)所示,进而扩延网络寿命;②采用自适应的通信半径机制[15],如式(6)所示,这有利于更好地平衡网络能量;③选择下一跳的标准不同。DEAC协议更充分地考虑了节点的剩余能量,并选择剩余能量最多的节点作为下一跳节点,进一步平衡了网络内能量消耗。

3 性能仿真

3.1 仿真参数及性能指标

本节评估DEAC算法的性能,利用MATLAB建立仿真平台,并与原始的EADUC、HUCL协议进行比较。100个节点随机分布于200 m×200 m区域,基站位于区域外,其位置坐标表示为(250,100),数据包大小为512 byte,其他的仿真参数如表1所示。

表1 仿真参数

同时,考虑3个不同的仿真场景[16]:(1)场景1:100个节点均匀分布于200 m×200 m,如图4(a)所示;(2)场景2:节点并不是均匀分布,而是多数节点分布区域的右边,靠近于基站,如图4(b)所示;(3)场景3:多数节点分布于区域的左边,远离基站,如图4(c)所示。

图4 仿真场景

3.2 网络寿命

为了更好地评估网络寿命,本次实验分别从第1个节点失效所发生的轮数和10%节点失效所发生的轮数表征网络寿命。实验数据表2、表3所示。

从表2可知,提出的DEAC协议拖延了第1个失效节点所发生的轮数。通过5次实验数据可知,不论是在场景1、场景2、场景3,DEAC协议的第1个失效节点所发生的轮数大于EADUC和HUCL协议,例如,在场景1时,DEAC协议的第1个失效节点所发生的平均值轮数为650,而EADUC和HUCL协议分别在280、320。这些数据说明DEAC协议能够有效地扩延网络寿命。此外,通过表2数据不难发现,3个场景的数据略有差别,在同等条件下,场景3的数据低于场景1、场景2。这说明,场景3的环境加速了节点失效,使得节点失效提前。这主要是因为在场景3中,多数节点远离基站,增加了节点的能量消耗。

表3统计了3个协议在3个场景下,当10%节点失效时,所发生的轮数。换而言之,90%的节点还处于活动状态时所维持的轮数。从表3可知,提出的DEAC协议的这项性能优于EADUC和HUCL协议。例如,在场景2,DEAC协议直到执行900轮时,才有10%的节点失效。即在900轮时,仍有90%的节点还处于活动状态。而EADUCE和HUCL协议分别只能执行到350、750轮。

表2 第1个节点失效所发生的轮数

表3 10%节点失效所发生的轮数

图5 活动节点数随轮数的变化情况

3.3 活动节点数

本次实验分析DEAC算法在3个不同场景的活动节点数,并与EADUC和HUCL协议进行比较,数值结果如图5所示。

从图5可知,提出的DEAC算法的活动节点数优于EADUC协议。特别是当执行轮数超过500次后,DEAC协议的优势特别明显。例如,在场景1中,当轮数达到500次时,EADUC协议的活动节点数低于60,而DEAC的活动节点数达到100,提高了近一倍。此外,与HUCL协议相比,DEAC算法在活动节点数方面也存在优势,特别在场景1。即在传感节点均匀分布的环境下,DEAC算法能够有力地增加活动节点数。

4 总结

基于无线传感网络的节点能量受限的事实,分析了现有簇路由协议,并提出了基于EADUC的改进簇路由DEAC。DEAC算法采用非均匀的簇机制,进而平衡网内能量消耗。DEAC从簇头选择、节点通信半径以及簇间多跳通信的下一跳转发节点的选择机制三方面对EADUC协议进行了改进。在簇头选择过程了,利用节点所处的区域能量信息设置不同的延时,进而产生簇头;其次,依据节点能量自适应地设置节点的通信半径,降低能量消耗。最后,在选择下一跳转发节点时,更充分地考虑节点的能量水平,选择最佳的节点参与簇间多跳通信。

在本文中的3个不同场景的实验数据可知,提出的DEAC算法有效地延缓第1个失效节点发生的时间,提高了活动节点数目。此外,通过3个不同场景的实验数据可知,提出的DEAC算法可适用大中型的WSNs应用场景,如森林防火监测。

[1] Muruganathan S D,Ma D C,Bhasin R I. A Centralized Energy-Efficient Routing Protocol for Wireless Sensor Networks[J]. IEEE Radio Communications,2011,43(3):8-13.

[2] 邵奇可,冯淑娜,毛科技. 面向WSN的自适应模糊功率控制算法研究[J]. 传感技术学报,2015,4(28):563-572.

[3] 归奕红. 无线传感器网络HEDSA数据聚合研究[J]. 计算机工程,2011,37(7):160-164.

[4] Kaundal V,Mondal A K,Sharma P,et al. Tracing of Shading Effect on Underachieving SPV Cell of an SPV Grid Using Wireless Sensor Network[J]. Eng Sci Technol Int J,2015(18):475-484.

[5] Gu X,Yu J,Yu D,et al. ECDC:An Energy and Coverage-Aware Distributed Clustering Protocol for Wireless Sensor Networks[J]. Comp Electr Eng,2014(40):384-398.

[6] Yan J F,Liu Y L. Improved LEACH Routing Protocol for Large Scale Wireless Sensor Networks Routing[C]//International Conference on Electronics,Communications and Control. Ningbo,China,September 2011:35-42.

[7] Qing L,Zhu Q,Wang M. Design of a Distributed Energy-Efficient Clustering Algorithm for Heterogeneous Wireless Sensor Network[J]. ELSEVIER,Comput Commun,2016,29:2230-2237.

[8] Elbhiri B,Saadane R,El-Fkihi S,et al. Developed Distributed Energy-Efficient Clustering(DDEEC)for Heterogeneous Wireless Sensor Networks[C]//5th International Symposium on I/V Communications and Mobile Network. 2010:32-42.

[9] Saini A P,Sharma K. Distributed and Grid Computing(PDGC-2010). E-DEEC-Enhanced Distributed Energy Efficient Clustering Scheme for Heterogeneous WSN[C]//2010 1st International Conference on Parallel,2011,3-9.

[10] Wu J,Qi Y,Wang G,et al. An Energy Aware Distributed Unequal Clustering Protocol for Wireless Sensor Networks[J]. Int J Distrib Sens Netw,2011:23-32.

[11] Li C,Ye M,Chen G,et al. An Energy Ecient Unequal Clustering Mechanism for Wireless Sensor Networks[C]//Proceedings of IEEE International Conference on Mobile Ad-Hoc and Sensor Systems(MASS),2015:596-604.

[12] Min X,Wei-Ren S,Changjiang J,et al. Energy Ecient Clustering Algorithm for Maximizing Lifetime of Wireless Sensor Networks[J]. Int J Electron Commun,2010:(64):289-298.

[13] Liao Y,Qi H,Li W. Load-Balanced Clustering Algorithm with Distributed Self-Organization for Wireless Sensor Networks[J]. IEEE Sens,2013,13(5):1498-1506.

[14] Li J,Mohapatra P. An Analytical Model on the Energy Hole Problem in Many-to-One Sensor Networks[J]. Proc of IEEE Vehicular Technology Conf,Fall. 2015,3(5):2721-2725.

[15] Vrinda G,Rajoo P. An Improved Energy Aware Distributed Unequal Clustering Protocol for Heterogeneous Wireless Sensor Networks[J]. Engineering Science and Technology,2016,4(6):23-31.

[16] Coutinho R W L,Boukerche A,Vieira L F M,et al. GEDAR:Geographic and Opportunistic Routing Protocol with Depth Adjustment for Mobile Underwater Sensor Networks[C]//Proc IEEE Int Conf Commun,2014:251-256.

焦克莹(1973-),女,汉族,河南南阳人,博士,副教授,研究方向为计算机网络应用不确定信息处理、数据分析,jiaokeying89@yeah.net。

DistributedEnergyAwareUnequalClusteringAlgorithmforHeterogeneousWSNs*

JIAOKeying1*,GUOQiang2

(1.Zhumadian Vocational and Technical College,Zhumadian He’nan 463000,China; 2.Huanghuai University International Education College,Zhumadian He’nan 463000,China)

Using the energy of sensor nodes efficiently to prolong the network lifetime is a chief challenge for designing routing protocols. To prolong WSNs(Wireless Sensor Networks)lifetime,most of the existing clustering schemes are geared towards homogeneous WSNs. Therefore,Distributed Energy Aware Unequal Clustering(DEAC)algorithm for heterogeneous WSNs is proposed in this paper. Based on Energy Aware Distributed Unequal Clustering(EADUC),DEAC is different from EADUC. DEAC algorithm has improved in terms of cluster head campaign mechanism,next-hop forwarding node selection strategy in multi-hop inter-cluster communication,and the adaptive setting communication radius. In cluster head campaign mechanism,the delay is computed based on residual energy and energy level of neighbor nodes by back off algorithm. In selecting the next-hop forwarding node,the metric with energy is estimated,and the node with high-residual energy is selected. To set the communication radius,the distance,residual energy and number of neighbor nodes are taken into account. Simulation results show that DEAC can postpone the time of the first failed node,and reduce the energy consumption,prolong the network lifetime.

heterogeneous wireless sensor network;clustering routing;energy aware;unequal clustering;network lifetime

项目来源:国家自然科学基金项目(71073033);河南省科技攻关计划项目(122102210430)

2017-03-28修改日期:2017-05-23

TP393

:A

:1004-1699(2017)09-1427-06

10.3969/j.issn.1004-1699.2017.09.022