基于地理位置的HEED非均匀分簇算法

渠帅军，　吕红芳，　赵　静

(上海电机学院 电气学院, 上海 201306)



基于地理位置的HEED非均匀分簇算法

渠帅军，吕红芳，赵静

(上海电机学院 电气学院, 上海 201306)

摘要HEED-M分簇算法中，簇首节点与汇聚节点采用多跳路由的方式进行通信，距汇聚节点越近的节点越容易过早地耗尽能量而失效。针对上述问题，提出基于地理位置的HEED非均匀分簇路由算法(LHEED)，根据簇首节点距离汇聚节点的距离动态地调整簇半径的大小。使距汇聚节点近的簇首簇半径较小，距汇聚节点远的簇首簇半径较大，从而有效地均衡网络的能量消耗。仿真结果表明，该算法可有效延长网络的寿命。

关键词地理位置; HEED; 非均匀分簇; 簇半径

无线传感网络(Wireless Sensor Network, WSN)是由分布在被监测区域内的大量廉价的传感器节点以自组织的形式构成的网络。设计能量高效的路由协议是WSN路由协议设计中需要重点考虑的一个问题[1]。目前，在WSN路由协议研究领域中主要采用分簇的方法来解决这一问题[2]，其基本思想是将WSN划分为多个簇的结构，由簇首节点负责搜集簇内成员节点采集的数据，并进行数据聚合处理，然后，簇首节点间通过协作的方式将融合后的数据传送回sink节点。

针对分簇路由算法，国内外学者进行了许多研究。LEACH(Low Energy Adaptive Clustering Hierarchy)协议[3]是第一个提出数据聚合的分簇路由协议。在LEACH协议中，由于簇首是随机选择的，故簇首节点的分布是不均匀的。HEED(Hybrid, Energy-Efficient Distributed Clustering)[4]算法针对此问题进行了改进，产生了分布均匀的簇首，以均衡全网能耗。但是，HEED算法也存在一些问题，目前许多文献对HEED算法进行了改进。文献[5]中针对HEED协议中簇首与基站直接通信能量消耗过大的问题，根据能耗模型与网络模型提出了一种基于HEED的簇首多跳融合路由算法(HEED-M)，在簇首与基站之间采用多跳路由的方式通信。文献[6]中提出了一种A-HEED算法，降低了各节点间广播通信的能耗。文献[7]中提出了一种基于HEED的多层分簇路由算法，在网络拓扑的底层构建了多个簇首节点的簇集合，在拓扑的顶层构建了多跳转发机制。文献[8]中提出了HEED-CHEE分簇算法，对于“孤儿”节点和“孤立”簇首节点，采用最优邻居中继入簇策略加入邻近簇，从而减少了簇首数目和簇首节点间的通信开销。文献[9]中使用非均匀分簇机制，计算得出最优簇半径并设定了上、下限，使得网络中的节点分簇更合理。

上述对HEED分簇算法的改进，都是改变簇首与sink节点的通信方式，并没有考虑内层节点能量消耗过多这一问题。本文将非均匀分簇的思想[10]运用到HEED分簇算法中，研究了一种基于地理位置的HEED非均匀分簇算法(The HEED Non-uniform Clustering Algorithm Based on Geographic Loction, LHEED)分簇算法。该算法根据簇首节点与汇聚节点的距离动态地调整簇半径的大小，即距汇聚节点近的簇首，簇半径较小，距汇聚节点远的簇首，簇半径较大，从而均衡网络的能量消耗，同时在簇间通信中引入了簇首通信代价函数，从而有效地延长了网络的寿命。

1能耗模型

1.1能耗模型

WSN中的节点在通信过程中的能耗模型采用自由空间模型和多路径衰减模型[11]，如图1所示。图中，Eelec为电路处理单位比特数据消耗的能量，Eamp为放大器的系数；d为发送器与接收器之间的距离；ETx、ERx分别为发送和接收单位比特数据所消耗的能量；n=2或n=4。

图1　WSN的能耗模型Fig.1　Energy consumption model of wireless sensor network

在WSN模型中，有

(1)

由式(1)可见，WSN节点发送的能耗随着发送距离的增加而迅速增多。在HEED算法中，簇首的选择主要依据主、次两个参数[12]，其中主参数依赖于剩余能量，具有较多剩余能量的节点成为临时簇首的概率更大，次参数为簇内平均可达能量[4](Average Miximum Reachability Power, AMRP)。

(2)

式中，M为簇内节点个数；Pri为节点与簇首节点间通信能耗。

由于簇首节点与sink节点直接通信，故距离sink节点远的簇首发送的能耗远大于距离sink节点近的簇首发送的能耗，从而造成距离远的簇首能量过早耗尽而死亡。在文献[5]中提出的HEED-M分簇算法针对这一问题进行了改进。该算法与HEED算法的唯一区别就是后者采用单跳的方式与sink节点通信，而前者采用多跳路由的方式与sink节点通信[13]，如图2所示，其中，j、k、q为簇首节点。

图2　HEED-M算法中的簇间通信Fig.2　Communication between clusters and clusters of HEED-M

文献[14]中研究表明，虽然多跳路由的通信方式可以从整体上降低网络能量消耗，但是，由于距离sink节点近的簇首也会因转发大量数据而消耗能量，这种内层节点消耗的能量是不可忽略的。而非均匀分簇可以使内层节点在分簇时通过控制成簇半径来控制簇内节点个数，若簇半径相对较小，则簇内成员节点数目就比较少，从而可减少簇首接收成员节点传递数据所消耗的能量，为内层簇首转发远端簇首的数据预留了能量。本文在HEED-M分簇算法的基础上引入非均匀分簇机制，来均衡网络能量的消耗。

2网络模型与LHEED分簇算法

2.1网络模型

WSN中的节点随机分布，本文对网络模型做如下假设：

(1) 由N个传感器节点组成的网络，节点随机部署在监测区域，所有节点地位平等；

(2) 各节点一旦部署就无法更换；

(3) 监测区域中的无线传感器节点位置固定；

(4) 整个网络中只有一个sink节点，且sink节点是静止的；

(5) 无线传感器节点可以感知自身位置。

2.2算法的描述

本文研究的LHEED分簇算法根据节点与sink节点的距离动态地调整簇半径的大小，簇首距汇聚节点近，则簇半径较小；簇首距汇聚节点远，则簇半径较大，以此来均衡网络的能量消耗。同时，在簇间通信时，簇首选择下一跳节点应考虑到该节点的地理位置和剩余能量，故引入了一种新的簇首间的通信代价函数，通过计算选择中继簇首。

2.3算法的实现

2.3.1初始化阶段在随机分布的WSN区域内，首先汇聚节点向监测区域内的无线传感器节点播报自己的地理位置，无线传感器节点根据自身的地理位置计算出与汇聚节点的距离dto-sink，若该节点当选为簇首节点，则计算得到该簇首的最优簇半径为[15]

(3)

式中，α为距离调节因子(其值为0～1)的值，系统最优值由仿真实验得出；dmax和dmin分别为所有节点距离sink节点的最大值和最小值；Rmax为节点的最大通信半径。

各节点根据其最优簇半径确定其邻居节点的个数，以及各自的AMRP，并根据系统规定的簇首比例Cprob计算得到该节点成为族首的概率为[10]

(4)

式中，Pmin为最小剩余能量比例；Eres为节点剩余能量；Emax为节点初始能量。

簇首选择的主参数依赖于剩余能量，剩余能量多的节点将有较大的概率成为簇首。

2.3.2迭代阶段每个节点在每轮的迭代过程中判断邻居节点中是否有临时簇首节点，若有且该节点也是临时簇首，则比较该节点与邻居节点中临时簇首的AMRP，若该节点的AMRP最小，则该节点就被推举为最终簇首；否则，该节点的CHprob×2，并与1相比较，将两者中的较小值赋予CHprob进行下一轮迭代，直到CHprob为1，此时迭代结束。若该节点的邻居节点中没有临时簇首，则该节点按照一定的概率成为临时簇首。

2.3.3分簇完成若临时簇首的邻居节点中没有临时簇首或其他临时簇首的AMRP都较该节点大，则该临时簇首就宣布自己成为最终的簇首。若普通节点处于多个簇的覆盖范围，则加入簇首AMRP最小的簇。

本文研究的LHEED分簇算法具有以下特点： 节点先根据自身的地理位置计算出自己的最优簇半径，然后，根据最优簇半径进行动态分簇，在有限迭代次数内完成簇首的选择。

2.4簇间通信

图3所示为LHEED分簇算法的簇间通信过程。图中，d(q，j)、d(q，k)为簇首节点q与j、k间的距离，dto-sink(q)、dto-sink(j)、dto-sink(k)分别为簇首节点q、j、k到sink节点的距离。利用LHEED分簇算法完成节点的分簇后，普通节点将采集到的数据传输给簇首节点，由簇首节点通过中继簇首以多跳的方式将数据传输到sink节点。当簇首节点q向sink节点传输数据时，假设候选中继簇首节点为j、k。由于簇首节点发送的能耗与该节点距sink节点的距离有很大关系，簇首之间的通信距离应小于d0，本文所研究的网络中sink节点在监测区域附近，故WSN的能耗模型采用自由空间模型。图3中，簇首节点q通过簇首j向sink节点传输单位bit数据消耗的能量为

(5)

图3　LHEED算法中的簇间通信Fig.3　Communication between clusters and clusters of LHEED

q的路由代价也就越小。由于簇首节点通过多跳路由的方式向sink节点传输数据，故在选择中继簇首时应考虑该节点的剩余能量，以及其与sink节点的距离。基于此，本文引入了簇首间的路由通信代价函数

(6)

式中，β、λ分别为距离均衡因子、能量均衡因子，最优值由仿真实验得出；Emax(j)为中继簇首j的最大能量。每个簇首依次计算其到其他簇首的路由通信代价，cost(q，j)大的簇首节点将更容易成为簇首节点的中继簇首。

分簇完成后，在开始传送数据之前所有簇首节点向全网中节点广播一条包含其节点ID、剩余能量和至sink节点距离的信息。

3仿真验证与分析

为分析LHEED算法的性能，分析该算法与HEED算法的网络拓扑结构，比较其与HEED-M及HEED算法的节点存活个数，本文使用MATLAB软件作为仿真平台，在100m×100m的区域内，取100个节点进行仿真实验。实验参数如表1所示。

表1　试验参数Tab.1　Experimental parameters

图4给出了HEED和LHEED分簇算法的网络拓扑结构。由图可见，LHEED分簇算法中采用基于地理位置的非均匀分簇，所形成的网络拓扑结构与HEED分簇算法不同。HEED算法中，簇首节点的分布是随机的，簇的大小也都相同。而LHEED算法中，簇的大小根据簇首节点与sink间的距离动态地调整，簇首节点距汇聚节点较近，则其簇半径较小；簇首节点距汇聚节点较远，则其簇半径较大。由于α的取值直接影响最优簇半径，进而对网络的拓补结构产生影响，通过大量仿真实验得到当α=0.6时，网络分簇比较均衡(见图4(b))。

图4　HEED和LHEED分簇算法的网络拓扑结构Fig.4　Network topology of HEED and LHEED clustering algorithm

图5给出了LHEED、HEED-M和HEED分簇算法的存活节点数比较。由图可知，HEED算法中能量消耗最快，这是由于簇首节点与sink节点直接通信造成的。而在HEED-M算法中，簇首节点与sink节点采用多跳路由的方式通信，故能量消耗次之。在LHEED算法中，簇首节点距sink节点较近，则其簇半径较小；簇首节点距sink节点较远，则其簇半径较大。由于簇首节点在接收成员节点传输数据和传输其他簇首节点发送来的数据时，都要消耗能量，且当簇半径较小时，其覆盖的成员节点就少，所消耗的能量就较少；而簇半径较大时，其覆盖的成员节点就多，所消耗的能量就较多；故距离sink节点近的簇首节点在接收成员节点传输数据上的能量消耗就较少，为距离sink节点远的簇首转发数据预留了能量；同时，由于使用了路由代价函数来选择中继簇首，故该算法的能量消耗最慢。由大量仿真实验表明，当β=0.6、λ=0.4时能量消耗最慢。

图5　3种算法的存活节点数比较Fig.5　Comparison of three kinds of algorithm in the number of surviving nodes

表2给出了3种算法节点运行周期的比较。由表可见，LHEED分簇算法运行周期最长，HEED-M分簇算法次之，HEED分簇算法运行周期最短。这是由于LHEED分簇算法采用非均匀分簇机制有效地均衡了网络的能量消耗；HEED-M分簇算法虽采用多跳路由的方式传输数据，但是也加重了内层节点负担；HEED分簇算法由于簇首节点与sink节点直接通信，使远离sink节点的簇首因能量消耗过快而较早死亡。

表2　3种算法节点运行周期的比较Tab.2　Comparison of three kinds of algorithms of node operation cycle

4结语

本文研究了基于地理位置的HEED非均匀分簇算法，根据簇首节点距汇聚节点的距离动态调整簇半径的大小，距汇聚节点近的簇首簇半径较小，距汇聚节点远的簇首，簇半径较大，通过调整成簇半径来均衡网络的能量消耗，簇间通信也考虑到节点剩余能量和地理位置，从而有效的延长了网络的寿命。本文未能考虑整个网络的连通性[16]，以及节点密度大的地区节点间的干扰，这些将在以后的工作中展开研究。

参考文献

[1]YANG Shuang Hua.Wireless Sensor Networks： Principles，Design and Applications[M].[S.L.]Springer，2014： 7-15.

[2]宋宁博.基于能量优化的无线传感器网络分簇路由协议研究[D].重庆： 重庆大学，2014： 24-31.

[3]HEINZELMAN W R，CHANDRAKASAN A，BALAKRISHNAN H.Energy-Efficient communication protocol for wireless microsensor networks[C]∥Proceedings of the 33rd Annual Hawaii International Conference on System Science(HICSS 2000).[S.L.]: IEEE，2000: 1-10.

[4]YOUNIS O，FAHMY S.Heed： A hybrid，Energy-efficient，Distributed clustering approach for ad-hoc sensor networks[J].IEEE Transactions on Mobile Computing，2004，3(4)： 366-379.

[5]姚新兵, 王向东.一种基于HEED的簇首多跳融合路由算法[J].通信技术，2011，44(4)： 106-108，111.

[6]李晶，史杏荣.无线传感器网络中改进的 HeeD路由协议[J].计算机工程与应用，2007，43(25)： 165-167.

[7]王秀花，张国荣.无线传感器网络中基于HEED的多层分簇路由算法[J].甘肃联合大学学报(自然科学版)，2011，25(1)： 78-81，90.

[8]尹安，汪秉文，戴志诚，等.无线传感器网络HEED分簇协议的研究与改进[J].小型微型计算机系统，2010，31(10)： 2002-2006.

[9]陈良文.无线传感器网络分簇式路由算法研究与改进[D].合肥： 安徽理工大学，2014.

[10]刘佳，范书瑞，刘艳萍，等.基于非均匀分簇和信息熵的无线传感网络路由算法[J].传感技术学报，2015，28(12)： 1867-1872.

[11]苏兵，张钰婧.基于非均匀分簇的无线传感器网络路由协议[J].计算机测量与控制，2016，24(2)： 325-327.

[12]康琼.无线传感器网络中分簇算法的研究[D].长春： 吉林大学，2013： 10-12.

[13]赵海荣.无线传感器网络能量高效的分簇路由协议研究[D].上海： 东华大学，2013： 39-41.

[14]卢先领，王莹莹，王洪斌，等.无线传感器网络能量均衡的非均匀分簇算法[J].计算机科学，2013，40(5)： 78-81.

[15]张瑞华，贾智平，程合友，等.基于非均匀分簇和最小能耗的无线传感网络路由算法[J].上海交通大学学报(自然科学版)，2012，46(11)： 1774-1778.

[16]孙毅，孙跃，曾璐琨，等.基于最优连通功率控制的WSNs跨层路由优化算法[J].传感器与微系统，2014，33(11)： 135-138.

收稿日期：2016-04-17

基金项目：上海市经济和信息化委员会专项资金项目资助(12AZ22)

作者简介：渠帅军(1991-)，男，硕士生，主要研究方向为无线传感器网络路由算法，E-mail： 523078212@qq.com

文章编号2095-0020(2016)03-0170-06

中图分类号TP 212.9

文献标识码A

HEED Non-uniform Clustering Algorithm Based on Geographic Location

QUShuaijun，LÜHongfang，ZHAOJing

(School of Electrical Engineering, Shanghai Dianji University, Shanghai 201306, China)

AbstractFor HEED-M clustering algorithm, cluster head nodes and sink node communicate in a multi-hop routing way so that energy easily depletes prematurely near the sink node more, causing system failure. To solve the problem, this paper proposes a HEED non-uniform clustering algorithm based on geographic location. The algorithm dynamically adjusts size of radius of the cluster according to the distance between cluster head nodes and sink node. Cluster of the head nodes near the sink node is small, and that of the head nodes far from the sink node is large. This way, energy consumption of the network is balanced effectively. Simulation results show that the algorithm is effective in prolonging the network life.

Keywordsgeographic location; HEED; non-uniform clustering; radius of cluster