基于网格的动态能量阈值的簇头选择算法*

梁 潘,贺 伟

(1.成都航空职业技术学院机电工程学院,成都 610100;2.阿坝师范学院物理与电子科学系,四川 汶川 623002)

项目来源:国家自然科学基金项目(61373163)；四川省教育厅重点项目(17ZA0020)

2017-02-28修改日期2017-07-03

基于网格的动态能量阈值的簇头选择算法*

梁 潘1,贺 伟2*

(1.成都航空职业技术学院机电工程学院,成都 610100;2.阿坝师范学院物理与电子科学系,四川 汶川 623002)

有效地使用传感节点的能量进而延长网络寿命成为设计无线传感网路由协议的一项挑战性的工作。而动态簇被认为提高能量利用率的有效技术之一。然而,簇头分布不均匀加速了网络能量的消耗,降低了网络寿命。为此,提出基于网格的动态能量阈值的簇头选择算法GDET-CH(Grid Dynamic Energy Threshold-based Cluster Header),平衡簇头分布。GDET-CH算法先将网络区域划分多个网格,并每个网格产生一个簇头。然后,利用节点离网格中心距离和节点剩余能量选择簇头。最后,引用动态能量阈值机制,只有当节点剩余能量大于能量阈值才可能成为簇头,进而平衡网络能耗。实验数据表明,与DDEEC和EDDDEC算法相比,GDET-CH算法的网络寿命分别提高了近24.5%和36%。

无线传感网;簇头;能量;网格;阈值

无线传感网络WSNs(Wireless Sensor Networks)已广泛应用于各类领域[1-4],如环境监测、健康医疗、战场勘察。WSNs通过传感节点实时感测环境数据,实现对应用环境的监测。然而,由于传感节点的资源受限,如存储容量、数据处理能力以及能量受限,尤其是能量受限。此外,WSNs常部署于野外恶劣环境,给传感节点补给能量或更换电池都有巨大挑战[5-6]。因此,降低节点能耗,提高节点的能量使用率,进而延长网络寿命成为WSNs的研究重点。

为了提高WSNs的可扩展性和能量效率,常采用簇拓扑结构,即将整个网络虚拟地划分不同的群(簇),如图1所示。通过簇结构,平衡能耗,提高网络连通率[7]。通常,WSNs中的簇头需完成多项特殊任务,如传感节点间的协调、数据融合(基站)、与邻近簇头的通信,这加大了簇头的能耗。因此,如何选择簇头成为WSNs研究的热点。

图1 基于簇结构的WSNs

常利用节点剩余能量和距离信息选择簇头。典型的有低功耗自适应簇LEACH[8]协议。LEACH协议利用阈值概率选择簇头,但它并没有从平衡能耗角度选择簇头,导致某些低能量的节点误选为簇头,这加剧了这类簇头因能量耗尽而失效的速度,并且它也只适用同构网络。

针对异构网络,文献[9-10]分别提出基于分布式能效簇DEEC(Distributed Energy-Efficient Clustering)算法、DEEC的改进DDEEC(Developed DEEC)算法。DEEC和DDEEC算法均采用二级能量结构,即依据节点能量将传感节点划分为普通节点和超级节点。而文献[11]提出EDEEC算法,其是采用三级能量结构,将传感节点划分为普通节点、超级节点和特超节点。然而,EDEEC算法并没有实时依据网络能量调整簇头的选择概率,最终导致某些节点因能量过早消耗殆尽而失效,节点一旦失效,就形成覆盖空洞,这影响了传感网络的应用性能

为此,本文提出基于网格的动态能量阈值的簇头选择算法GDET-CH平衡网络能耗。GDET-CH算法先将网络划分为同等大小的网格,在每个网格内产生一个簇头。然后,计算非簇头节点就选择自己最近的离簇头加入,进而形成簇。实验数据表明,提出的GDET-CH算法能够有效地适用于同构网络和异构网络,并提高了网络寿命。

1 系统模型

考虑n个节点随机分布于A×B的感测区域的多跳传感网络。在部署初期,每个传感节点具有一定的数据处理和通信能力。假定S为网络内所有传感节点集,如式(1)所示:

S={S1,S2,…,Si}

(1)

式中:Si表示第i个传感节点。

同时,将整个网络划分为无不重叠唯一的网格ac×bc。假定Q表示网络内所有网格集,如式(2):

Q={Qj|j=1,2,…,q}

(2)

式中:q表示网络的网格数。并且每个网格内有pj个节点数。而在每个网格内的传感节点数集可表示为{Si|i=1,2,…,pj}。因此,网络内的节点数可表示为:

(3)

此外,假定第j个网格内的传感节点集为Qj,其定义如式(4)所示:

(4)

在每个网格内选择一个节点作为簇头,网格内的其他节点称为成员节点,并由簇头与成员节点进行协调。簇头先接收来自成员节点的数据,然后,再进行数据融合,并转发至数据中心。GDET-CH算法从能量角度,有效地选择簇头,进而能有效地适应网络拓扑的动态变化。

此外,假定nt个数据传输节点所传输的数据矢量为x:

x=[x1,x2,…,xnt]T

(5)

数据融合中心的接收信号矢量可表述为y:

y=Hx+n

(6)

式中:y为nr×1维的接收信号矢量。H为瑞利衰落信道矩阵,且尺寸为nr×nt。而n为nr×1维的噪声矢量,其中n为零均值的加性高斯白噪声,且方差为σ2。

瑞利衰落信道矩阵H定义如式(7):

(7)

式中:hj,i表示从第i个发射节点到数据中心的第j个接收天线的信道协方差系数。

图2 GDET-CH算法的时间模型

1.1 时间模型

提出的GDET-CH算法将运行时间划分等间隔轮r(round),并规定从簇头产生至数据传输至融合中心称为一轮,如图2所示。即在每轮内产生簇头,并传输数据。此外,本文引用轮数衡量网络寿命。网络经历的轮数越多,说明网络运行的时间越长,即网络寿命越大。

2 GDET-CH 算法

GDET-CH算法主要从距离和能量两个角度选择簇头。先计算节点离所有网格的距离,并进行排序。然后设置能量阈值。当节点的剩余能量大于阈值,才有可能作为簇头候选节点,再从这些簇头候选集内选择离网格最近的节点作为该网格的簇头。

2.1 距离因子

(8)

当所有节点部署后,它们就计算离他们各自的网格中心的距离,其定义如式(9)所示:

d1=Γ(cx,cy,sx,sy)

(9)

据此,可定义矩阵Q,其定义如式(10)所示:

(10)

矩阵Q内的第1行表示每个网格内所有的节点数。尽管每个网格内所拥有的节点数不同,但仍用矩阵Q表示。利用S(j,i)的值,表示此位置是否存在一个节点。此值为1,表示存在传感节点,-1表示不存在传感节点。

接下来,定义q×p维的矩阵D1,其表示所有节点到每个网格中心的距离,如式(11)所示:

(11)

从式(11)可知,矩阵D1的第1行表示传感节点所有节点至第1个网格中心的距离。为此,利用d1(k)表示所有节点至第kth个网格中心的距离,即d1(k)={d1(k,1),d1(k,2),…,d1(k,p)},且k=1,2,…,q。

ξk=min[abs(d1(k))]

(12)

2.2 动态能量阈值

GDET-CH算法在选择簇头时,充分考虑了节点剩余能量。当节点剩余能量Ere大于预定Eth值,才可能成为簇头。将Eth称为能量阈值。

而如何设定阈值Eth对簇头选择起到关键作用。传统的簇头选择算法常引用固定阈值,这不利用网络能耗的平衡。具体而言,最初节点能量较高,可以设置较大的阈值,但随着网络的运行,节点能量下降,这时需要降低阈值。为此,采用自适应的阈值机制。

首先,引用ψ={ψ1,ψ2,…,ψm}表示节点能量的范围,且ψ∈[0,1]。随着,网络的运行,节点能量肯定逐步下降。换而言之,最初,阈值Eth可以较高,因为多数节点的能量较为充足。但是,经过一段时间后,节点能量肯定下降,如果节点阈值Eth过高,或者不随进行改变,那多数节点的能量肯定低于阈值Eth。

(13)

2.3 簇头产生过程

簇头产生过程的伪代码如图3所示。先将矩阵D1、P1和Qs初始化,并将矢量d1、p1也初始化。其中Qs为节点状态矩阵,维数为q×p。如果节点为簇头,则其元素值就为1,否则就为零,即节点为普通节点。

然后,从第1个网格开始,再依据式(9),每个节点计算离此网格中心的距离,即形成d1(1),再进行排序。然后再从第2个网格开始,重复上述过程,直至所有传感网络均计算了离各自网格中心的距离。

图3 产生簇头算法的伪代码

2.4 簇形成过程

产生簇头后,就形成簇头集Qch,其定义如式(14)所示:

(14)

非簇头节点(普通节点)需要加入至一个簇,加入的原则就是,选择离自己最近的簇。为此,定义n×q维的矩阵D2,其表示所有普通节点离q个簇头的距离,如式(15)所示:

(15)

而d2表示普通节点离簇头的距离,可由式(8)计算,如式(16)所示:

(16)

引用d2(i)表示矩阵D2的第i行,其元素值等于普通节点(第i个普通节点)至离q个簇头的距离。该普通节点就选择离自己最近的簇头加入,即min{d2(i)}。簇形成算法的伪代码如图4所示。

图4 簇形成过程的伪代码

3 性能仿真

3.1 仿真参数及性能指标

为了更好地评估GDET-CH算法性能,通过MATLAB软件建立仿真平台。选择100 m×100 m的感测区域,且传感节点数为100。每个节点的初始能量E0=1 J。假定融合中心位于100 m×100 m区域的中心。

此外,为了更好地考查传感节点的同构或异构性对GDET-CH算法的性能影响,建立两个实验:同构网络实验;异构网络实验。本文所指的同构网络是指网络内所有节点的初始相同,而异构网络是指节点能量初始不相同。

3.2 同构网络实验

为了更好地分析GDET-CH算法性能,选择同类动态簇算法LEACH作为参照。假定所有传感节点是同构的,并且由簇头负责将数据转发至融合中心。

图5 同构网络寿命

图5显示了GDET-CH和LEACH算法的活动节点数NA随轮数的变化情况。从图5可知,GDET-CH算法的第1个失效节点FND(First Node Died)发生在1 370轮,而LEACH算法的FND发生于903轮。此外,当LEACH算法运行至1 198轮时,就有一半的节点失效HND(Half Nodes Died),而GDET-CH算法直到2 334轮才出现这种情况。观察图5可发现,GDET-CH算法的最后一个失效节点LND(Last Node Died)发生于3 415轮,而LEACH算法在1 862轮就出现这种情况。从这些数据可知,GDET-CH算法分别通过100%、50%、1%的活动节点提高的51%、94%、83%的网络寿命。这里的网络寿命是通过轮数表征。运行的轮数越多,网络寿命也就越长。

3.3 异构网络实验

本次实验是基于异构网络,并且考虑二级、三级的异构网络。在二级异构网络中,通过节点的初始能量的不同,将网络内传感节点划分为普通节点、超级节点。且普通节点数为n×(1-m)、超级节点数为n×m。

而在三级异构网络中,将传感节点划分为普通节点、超级节点和特超节点,它们的节点数分别为n×(1-m)、n×m×(1-m0)和n×m×m0。其中n=100、m、m0分别设置为0.3。而超级节点和特超节点的初始能量分别为(1+α)E0、(1+b)E0,其中a、b分别为2、3.5。

图6显示了GDET-CH算法和DDEEC和DEEC在二级异构网络内的活动节点数。从图6可知,GDET-CH算法的FND、HND和LND分别发生于2 151、2 777和4 351轮。而DEEC和DDEEC算法的FND分别发生于936和2 013轮,而HND分别发生于2 145和2 232轮,LND发生于3 531和3 770轮。因此,相比于DEEC和DDEEC,GDET-CH算法的网络寿命提高了近23.2%和15.4%。

图6 异构网络寿命(二级)

图7 异构网络寿命(三级能量)

图7显示了三级异构网络的实验数据,也选择同类的EDEEC和EDDEEC[12]与GDET-CH算法进行参照。从图7可知,GDET-CH算法的FND、HND和LND分别发生于2 158、3 391和4 635轮,而EDEEC和EDDEEC的FND分别发生于2 401轮和2 492轮。相应地,LND发生于4 157和4 520轮。这些数据表明,在三级异构网络中,GDET-CH算法的网络寿命比EDEEC和EDDEEC分别提高了11.25%和2.6%。

4 总结

本文针对无线传感网络的簇头选择问题,提出了基于网格的动态能量阈值的簇头选择算法GDET-CH。GDET-CH算法充分考虑了簇头分布的均匀性对网络寿命的影响。在选择簇头时,融合了距离和节点剩余能量信息,并且考虑了动态的能量阈值,而不是单一的能量阈值。实验数据表明,提出的GDET-CH算法能够有效地提高网络寿命。

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

[3] 沈艳霞,薛小松. 无线传感网络移动信标节点路径优化策略[J]. 传感器与微系统,2012,31(12):42-46.

[4] Tyagi S,Kumar N. A Systematic Review on Clustering and Routing Techniques Based Upon LEACH Protocol for Wireless Sensor Networks[J]. Journal of Network and Computer Applications,2013,36(2):623-645.

[5] 陈东海,李长庚. 基于簇头功能分化的无线传感器网络成簇算法[J]. 传感技术学报,2015,28(2):244-248.

[6] 门顺治,孙顺远,徐保国. 基于PSO的非均匀分簇双簇头路由算法[J]. 传感技术学报,2014,27(9):1281-1286.

[7] Chidean M I,Morgado E,del Arco E,et al. Scalable Data-Coupled Clustering for Large Scale WSN[J]. IEEE Transactions on Wireless Communications,2015,14(9):4681-4694.

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

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

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

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

[12] Javaid N,Qureshi T,Khan A,et al. EDDEEC:Enhanced Developed Distributed Energy-Efficient Clustering for Heterogeneous Wireless Sensor Networks[J]. Procedia Computer Science,2013,19(2):914-919.

GridDynamicEnergyThreshold-BasedClusterHeaderAlgorithminWirelessSensorNetwork*

LIANGPan1,HEWei2*

(1.Department of Electro-Mechanic Engineering,Cheng Du Aeronautic Polytechnic,Chengdu 610100,China; 2.Department of Electronic Information,ABA Teahers University,Wenchuan Sichuan 423002,China)

Using the energy of sensor nodes efficiently to prolong the network lifetime is a chief challenge for designing routing protocols. Dynamic clustering is generally considered as one of the energy conservation techniques,but unbalanced distribution of cluster heads in clusters tend to drain out the network energy quickly resulting premature decrease in network lifetime. Grid dynamic energy threshold-based Cluster header(GDET-CH)algorithm is proposed in this paper,which balanced the distribution of cluster heads. In GDET-CH,Firstly,the whole network is divided into non-overlapping uniform grids,and each grid has a cluster head. Then,Distance from the center of grid and residual energy of node are both considered into selecting cluster head. Finally,GDET-CH introduces the dynamic energy threshold to balance the energy consumption,Only residual energy is more than threshold,the node may to be a cluster head. From simulation results,it is observed that the proposed clustering scheme enhances network lifetime by 24.5% and 36% as compared to existing schemes e.g. DDEEC and EDDEEC respectively.

wireless sensor network;cluster header;energy;grid;threshold

TPT393

A

1004-1699(2017)10-1583-06

10.3969/j.issn.1004-1699.2017.10.022

ξk表示离第kth个网格中心的距离最小的节点信息,其定义如式(12)所示:

梁潘(1978-),男,四川广汉人,副教授,硕士,研究方向为人工智能与网络安全;

贺伟(1980-),男,四川郫县人,副教授,硕士,研究方向为人工智能与网络安全。