一种基于邻近区域平均能量的分簇算法

蔡 扬，张怀相

(杭州电子科技大学计算机学院，浙江 杭州 310018)

一种基于邻近区域平均能量的分簇算法

蔡 扬，张怀相

(杭州电子科技大学计算机学院，浙江 杭州 310018)

针对无线传感器网络中传感器节点能量受限的问题，为减少节点能量消耗，提出了一种基于邻近区域平均能量的节能分簇算法.算法采用分阶段的簇头选举策略.在候选簇头选举阶段，根据节点剩余能量与邻近区域平均能量的比率来选取候选簇头.在簇头竞选阶段，使用功率控制方法使得每轮选出的簇头个数稳定，且均匀地分布在网络中，从而均衡网络能耗.仿真结果表明，算法具有更长的网络生存时间，网络稳定周期较AEAR算法和TCAC算法分别提高了16.9%和10.0%.

邻近区域平均能量；分簇；功率控制；节能；无线传感器网络

0 引 言

由于传感器的存储容量和计算能力有限，有效的拓扑控制对节能至关重要.拓扑控制一般可分为节点功率控制和层次型拓扑结构两类.功率控制通过设置或动态调整节点发射功率的大小，确保网络的连通性，使得节点能耗最低或者网络的干扰性最小.分簇机制是一种减少无线传感器网络通信开销和提供更好数据聚合的拓扑管理方法[1].低功耗自适应集簇分层型协议(Low Energy Adaptive Clustering Hierarchy，LEACH)[2]是一种经典的自适应分簇算法，通过周期性执行簇头轮值，均匀分配节点间的能量负载.但LEACH算法采用随机的方式选举簇头，簇头在网络中分布可能不均匀，且每个节点成为簇头的概率相同，不适用于能量异构的网络.文献[3]在簇头选举时，考虑了网络平均剩余能量，但每个节点须获取整个网络的平均剩余能量.文献[4]在簇头选举时，考虑了所有前一轮所形成的簇在当前轮的平均能量，但每轮每个节点都要重新计算簇内平均剩余能量.多种方式结合也是拓扑控制研究的一个方向.例如拓扑控制的自适应分簇(Topology-Controlled Adaptive Clustering，TCAC)[5]算法在簇头选举阶段，使用功率控制，以稳定簇头个数和均匀簇头分布.为了均衡节点的能耗，延长网络的生存时间，本文提出了一种基于邻近区域平均能量的功率控制分簇算法(Power Controlled Clustering algorithm with Average Energy of Adjacent Region，PCCAEAR).

1 异构网络模型

数据传输的能耗模型一般采用文献[3]中的模型.每发送和接收一个Lbits数据的能耗分别描述如下：

(1)

ERx(L)=LEelec

(2)

其中，Eelec表示电路处理每个bit数据的能耗，d0表示距离阈值.如果传输距离小于d0，则采用自由空间传输模型，功放因子为εfs.反之采用多径衰耗模型，其功放因子为εmp.

假设在一个M×M范围内有N个传感器节点均匀分布，基站位于这个区域的中心，并且任意一个节点到基站或簇头的距离都不大于距离阈值d0.则每轮消耗的网络能量如下：

(3)

2 基于邻近区域平均能量的分簇算法

网络中，以某一个节点为中心，该节点一定通信半径内的区域称为邻近区域，在该邻近区域中的其余节点称为该节点的邻近区域节点，这个区域中所有节点的平均能量被称为邻近区域平均能量.本文提出了一种基于邻近区域平均能量的功率控制分簇算法PCCAEAR.算法分为4个阶段，分别为网络初始化、簇头选举、成簇及稳定传输.

2.1 初始化网络

初始时，网络中所有的节点以Ri为半径广播Hello消息，Hello消息中包含节点剩余能量、地理位置等信息.

Ri=λRNavg, (Ri>RNavg)

(4)

节点i利用接收到的Hello消息统计出自己的邻居数Nbi后，根据自身剩余能量Ei(r)和所有邻居剩余能量计算其邻近区域平均能量Ei Navg(r)(r表示当前轮数，初始化时r=0)：

(5)

2.2 簇头选举

簇头选举包含候选簇头选举阶段和候选簇头竞选簇头阶段.

1)候选簇头选举阶段

PCCAEAR算法中，如果节点i在第r轮属于能够参与簇头选举的节点集合，则根据概率函数pi计算其成为候选簇头的概率：

(6)

其中，P表示节点中簇头的百分比.α表示影响候选簇头个数的参数，由于在簇头选举阶段要进行功率控制，为选出一定量的簇头，需增加候选簇头个数.

第r轮的邻近区域平均能量Ei Navg(r)是根据上一轮的邻近区域平均能量Ei Navg(r-1)与上一轮节点i估计消耗的能量Eic=Eround/N来计算的.若节点i当选为簇头节点时，需判断是否需要更新自己的邻近区域平均能量Ei Navg(r)，如果小于前一次更新的t倍时(称t为簇头邻近区域平均能量更新因子)，则需用式(5)重新计算.所以得到新的计算邻近区域平均能量公式如下：

(7)

然后节点i将概率pi值代入阈值函数计算出阈值T(i):

(8)

其中，G表示节点在第r轮能够参与簇头选举的节点集合.如果节点i当选为簇头，节点i将会在接下来的1/pi轮内都不参与簇头的竞选.

计算出阈值后，节点i随机产生一个[0,1]之间随机数，若比阈值小则该节点成为候选簇头.当α的值取0，且在簇头竞选过程中不采用功率控制，此时选出的候选簇头节点作为最终的簇头节点，将此算法称之为AEAR算法.否则，需要对这些候选簇头进行筛选以得到簇头节点.

2)候选簇头竞选簇头阶段

竞选簇头的方法类似于TCAC算法.经过上一阶段选出的候选簇头以一定的发射半径Rc广播候选簇头竞选簇头消息CCHMSG，消息包含节点位置、剩余能量等信息.

(9)

其中，β为影响簇头竞争阶段发射半径的因子，rc根据每个簇头的通信面积计算得到.

候选簇头等待其他候选簇头广播CCHMSG消息.若候选簇头未收到其他候选簇头发来的CCHMSG消息，则该节点成为簇头节点；若收到其他候选簇头广播的CCHMSG消息，则比较这些候选簇头节点能量的大小.如果该候选簇头节点能量最大，则被选为簇头节点；否则，变为非簇头节点.候选簇头竞选簇头的过程如图1所示.

图1 候选簇头竞选簇头过程

PCCAEAR算法的网络成簇及稳定传输阶段同LEACH，非簇头节点接收到簇头广播的CHMSG后，根据所收到的信号强度的大小，选择加入某个簇并向该簇头发送申请加入簇的消息REQMSG.

2.3 算法分析

PCCAEAR算法在网络初始化阶段节点是以小于最大功率的固定功率广播消息，从而与其邻居节点建立连接.相比于节点以最大功率广播消息的其他算法，缩小了通信范围，因此，在初始化阶段减少了节点收集邻居节点信息的能耗.算法通过两步的方式选举簇头，首先，在选取候选簇头时不是以固定概率来选取，而是考虑了节点的剩余能量和邻近区域平均能量，能量高且其邻近区域节点能量相对较低的节点被选中的概率大.PCCAEAR算法只有簇头才有权利更新其邻近区域平均能量，而且只有在小于上次更新的一定倍数时，才进行更新操作.此更新操作只是收集小范围内邻居节点的剩余能量，即簇头的邻近区域范围内的节点的能量.因此，相比于一般考虑平均能量这一参数的算法节约了通信开销.然后在簇头选举时进行功率控制，采用功率控制的方法可以有效避免簇头分布过于密集，在一定范围内只有一个簇头，使得簇头的分布更加均匀，簇头个数更加稳定.

3 仿真实验

仿真实验中，节点一旦部署后就固定不动，每个节点可感知自身剩余能量和自身地理位置，节点能量分布在[E0,4E0]区间.基站位于网络的中心位置.由于kopt≈10，设置最优簇头个数为10.仿真实验参数如表1所示.

表1 仿真实验参数设置

3.1 邻近区域半径和簇头邻近区域平均能量更新

首先确定邻近区域半径因子λ和簇头邻近区域平均能量更新因子t的值.将t从0.5增加到0.9，设置不同的λ为2到6之间的整数，第一个节点死亡的轮数如图2所示.观察发现，第一个节点死亡的轮数随着t值的增大总体呈现先上升后下降的趋势.t从0.7增加到0.8的过程中，第1个节点死亡的轮数呈现上升的状态，可能的原因是：簇头的选举是基于节点的邻近区域平均能量及剩余能量的，簇头节点更新邻近区域平均能量相对较为频繁，选出来的簇头较优，均衡了网络能量的消耗.当λ=4，t=0.6时，第一个节点死亡轮数最大.所以取λ=4，t=0.6作为之后的实验参数.

对比AEAR，LEACH，LEACH-E[3]和REAC[4]算法的网络生存时间，如图3所示.从图中观察到，AEAR算法较LEACH-E和REAC网络生存时间有所提高.因为AEAR算法并不是每轮都更新邻近区域平均能量，只有当簇头的邻近区域平均能量小于上次更新后能量值的0.6倍时才重新收集计算，相比于每轮都重新计算平均剩余能量LEACH-E和REAC算法减少了能量的消耗.AEAR算法相较于LEACH的稳定周期大幅提高(稳定周期指网络中出现死亡节点前网络执行的轮数)，由于LEACH算法每个节点当选簇头的概率相同，对于异构网络来说，能量较低的节点会过早地死亡.

图2 不同λ，t对应第一个节点死亡轮数

图3 每轮存活节点个数

3.2 发射半径和候选簇头

继续研究本文算法发射半径和候选簇头个数这2个参数对簇头个数和网络生存时间的影响.对α和β取不同值，计算平均簇头个数和评估网络生存时间.实验时，将α从0.00增加到0.20，β从0.8递增到1.2，找出最优参数组，使得平均簇头个数接近最优簇头个数的情况下网络生存时间最长.

当网络生存一定时间后，部分节点逐渐开始死亡.因此，对前2 000轮的平均簇头个数进行评估，相应的仿真结果如图4所示.从仿真结果可知，当β为特定值时，随着α的增大，网络中的每轮平均簇头个数逐渐增大，增大到一定程度后到达稳定的数目.原因是α较小时，所选出的候选簇头较少，竞争选出的簇头也较少.而随着α增大时，所选出的候选簇头增多，由于竞选簇头过程中，候选簇头的竞争半径是固定的，某一候选簇头在其竞争范围内的候选簇头数目可能增多，而在这区域内最多只能竞选出一个簇头节点.因此，当α增大到一定程度后，选出来的簇头的数量趋于稳定.在相同的α下，每轮平均簇头个数随β值的增大而减小.因为β对应的是簇头竞争阶段的候选簇头的发射半径，在一定范围内只有一个能量最高的候选簇头成为簇头节点，β越大，选出的簇头就越少.当β取1.0，α从0.08到0.20时，网络中每轮平均簇头个数最接近于kopt.其他每轮平均簇头个数接近kopt的参数组(α,β)有(0.03,0.8)和(0.04,0.9).

然后评估功率参数因子β和概率参数因子α对网络生存时间的影响.网络生存时间是依据第一个节点死亡的轮数来评估，结果如图5所示.结果显示节点死亡轮数随着α增大而增大，到达一定值后减小.原因是α较小时，候选簇头较少，竞争选出的簇头也较少，簇间通信时簇头的能耗较大.而α较大时，由于候选簇头的数量增多，在簇头竞争阶段消耗更多的能量.这些都会造成节点相对较早死亡.结合之前选出的参数组，当(α,β)=(0.12,1.0)，第一个节点死亡的轮数最大.从图中也可以看出当β=1.0时，α在0.10到0.16之间第一个节点死亡轮数相差不大.因此，最终取(α,β)=(0.12,1.0)作为最佳的参数组.

图4 不同α，β对应的平均簇头个数

图5 不同α，β对应的第一个节点死亡的轮数

3.3 簇头个数和网络生存时间

根据相对较优的参数组，设置PCCAEAR算法的参数α和β分别为0.12和1.0，并将本文算法与AEAR和TCAC算法比较.对于TCAC算法，传输半径设置为rc，簇头参数kinitial=2kopt.图6显示了3种算法的每轮簇头个数，关于网络生存时间仿真结果如图7所示.

图6 每轮簇头个数

图7 每轮存活节点个数

观察图6的仿真结果发现，TCAC和PCCAEAR算法每轮簇头个数较为稳定，在10左右小幅波动，而AEAR簇头个数的波动范围较大，在0到30之间.由此可见，在簇头选举阶段进行功率控制可以稳定簇头的个数.

观察图7发现，PCCAEAR的稳定周期最长，相较于AEAR和TCAC分别增加了16.9%和10.0%.因为PCCAEAR簇头不是每轮都更新邻近区域平均能量，而是当小于上一次更新后的t倍时才进行更新，减少了能量的消耗.AEAR的稳定周期最短，由于每轮的簇头个数不稳定，导致一些能量较低的节点较早死亡.TCAC和PCCAEAR算法当节点开始出现死亡后，剩余节点以较快的速度死亡，原因是进行功率控制后网络中节点分布较为均匀，导致网络能耗也更为均匀.PCCAEAR算法较TCAC算法的网络生命周期提高了约11.0%.因为TCAC虽然进行了功率控制，但是每一轮都需要计算网络的平均剩余能量，反而增加了网络开销.

4 结束语

本文以能量受限的无线传感器网络为背景，提出了一种基于邻近区域平均能量的簇头选举算法AEAR，并在此基础上，结合功率控制方法提出了PCCAEAR算法.实验结果表明，PCCAEAR算法可以有效地稳定簇头个数和均匀簇头分布，使得网络的能耗更加均衡，相较于AEAR算法延长了网络生存时间.PCCAEAR算法减少了簇头收集邻居信息的能耗，相较于每轮簇头都要收集簇成员节点剩余能量的TCAC算法减少了额外开销.然而,算法中的参数如邻近区域半径因子,功率参数因子,概率参数因子等是根据仿真实验的结果来确定的.因此,在实际应用中,必须对参数作进一步的调整.

[1]BOYINBODE O, LE H, TAKIZAWA M. A survey on clustering algorithms for wireless sensor networks[J]. International Journal of Space-Based and Situated Computing, 2011,1(2/3):130-136.

[2]HEINZELMAN, RABINER W, CHANDRAKASAN, et al. Energy-efficient communication protocol for wireless microsensor networks[J]. Adhoc & Sensor Wireless Networks, 2000,18:8020.

[3]HEINZELMAN W B, CHANDRAKASAN A P, BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks[J]. Wireless Communications, IEEE Transactions on, 2002,1(4):660-670.

[4]LEU J S, CHIANG T H, YU M C, et al. Energy Efficient Clustering Scheme for Prolonging the Lifetime of Wireless Sensor Network With Isolated Nodes[J]. IEEE Communications Letters, 2015,19(2):259-262.

[5]DAHNIL D P, SINGH Y P, HO C K. Topology-controlled adaptive clustering for uniformity and increased lifetime in wireless sensor networks[J]. Wireless Sensor Systems Iet, 2012,2(4):318-327.

A Clustering Algorithm Based on Average Energy of Adjacent Region

CAI Yang, ZHANG Huaixiang

(SchoolofComputer,HangzhouDianziUniversity,HangzhouZhejiang310018,China)

Sensor nodes are energy constrained in wireless sensor networks, in order to reduce nodes energy consumption, an energy efficient clustering algorithm based on average energy of adjacent region is proposed. The algorithm adopts staged cluster heads election strategy. In candidate cluster heads election stage, candidate cluster heads are elected based on the ratio between residual energy and average energy of adjacent region. Power control is used in cluster heads election stage, cluster heads are elected in a stable number per round and evenly distributed in network that makes the network energy consumption more balanced. Simulation results show that proposed algorithm has a longer network lifetime, with the stability period increasing by 16.9% and 10.0% respectively compared to AEAR and TCAC.

average energy of adjacent region; clustering; power control; energy saving; wireless sensor network

10.13954/j.cnki.hdu.2017.04.009

2016-11-03

国家科技支撑计划资助项目(2014BAF07B01)

蔡扬(1991-)，女，浙江丽水人，硕士研究生，无线传感器网络.通信作者：张怀相副教授，E-mail：hxzhang@hdu.edu.cn.

TP393

A

1001-9146(2017)04-0041-06