关志艳

(山西大学商务学院 信息学院，山西 太原 030031)

多级能量异构自适应传感器网络成簇算法*

关志艳

(山西大学商务学院 信息学院，山西 太原 030031)

在经典LEACH算法的基础上，综合考虑簇首选择概率、节点剩余能量及与基站距离等因素，本文提出了多级能量异构自适应传感网络成簇算法，对簇首选择阈值进行改进，将高能量近距离的节点优先选为簇首。在簇首将数据传输到基站的过程中，考虑中继簇首的选择，从而减少路由中继次数，最大限度节约能耗。仿真实验表明，本文算法在异构能量网络环境下有更长的网络稳定期。

能量异构；簇首；剩余能量

无线传感器网络是物联网的重要分支，在地形复杂区域往往不能人为部署节点，需要利用直升机等设备随机部署在监测区域内，此时能耗与通信就显得尤为突出。在网络运行过程中各节点能量出现异构，将不同能量级别的节点组织簇，将剩余能量高的节点选为簇首，负责收集、融合、压缩及发送来自簇成员节点采集的信息。

经典LEACH[1]是每个节点等概率随机产生于[0,1]，选择小于阈值的节点为簇首，广播簇首信息，每个节点据收到信号强弱来判断距离远近是否适合加入簇，该协议主要应用于同构。Younis[2]提出HEED协议，设定主次参数，主参数依赖于迭代过程是否比周围节点收敛快，次参数依赖于簇内通信代价，以平衡簇首间负载。

邓亚平[3]提出了多级能量异构传感器网络能量有效的路由算法，其针对TDEEC、SEP算法的平均网络能量进行改进，保证相对剩余能量较高的节点更有可能成为簇首，簇间采用多跳路由协议。刘唐[4]提出了基于相对距离的多级能量传感网络成簇算法，考虑到节点与基站的距离，节点等概率轮流成为簇首。张颖[5]提出了一种基于能量与距离的多级能量异构传感网络路由算法，其针对CDEE簇首选择机制进行改进，在簇首间形成一个多跳路由路径通向基站，但实现较难，无形中增加了网络计算能耗。

本研究综合考虑簇首选择概率、节点剩余能量及与基站距离三个因素，对簇首选择阈值进行改进，提出了多级能量异构自适应传感网络成簇算法，在簇首将数据传输到基站的过程中，设定通信阈值以选择中继簇首。仿真实验表明，本算法可以延长节点死亡时间，有效节约能量。

1 系统模型

1.1 同构能量网络成簇模型

在M×M的矩形监测区域内随机分布N个节点，所有节点初始能量相同，并在其中选出Kopt个簇首节点，Popt为优化簇首比例，簇首对本簇成员节点感知的数据信息进行收集并融合，再传输给基站。所有节点不具备移动性，节点依据接受信号强弱来判断与簇首距离，以确定是否加入该簇。

1.2 多级能量异构网络成簇模型

在上述同构能量网络模型的基础上，所有节点初始能量不再是相同的，而是随机分布于[E0,E0(1+ai)]内，ai是比E0多出的能量倍数。节点能量消耗主要考虑无线收发通信消耗，据收发节点间距离的不同，可采用自由空间模型和多路衰减模型。当发送端将1 bit数据传输到距离为d的接收端时，发送能耗为式(1)，接受能耗为式(2)，数据融合能耗为式(3)。

图1 100个节点随机分布

图2 LEACH 形成的分簇

(1)

ER(L,d)=L·Eelec.

(2)

EF(L)=L·EDA.

(3)

σ∈[1,6]为距离能量梯度系数，由物理环境而定，λ∈[1,2]为常数。

2 算法设计

2.1 簇首选择

在网络运行过程中，将时间分成许多间隙，称为轮。每轮节点是否成为簇首主要受节点与基站的距离、节点的剩余能量和节点选择成簇概率三方面决定。节点的选择成簇概率决定了优化簇首比例，文献[5]详细阐述了簇首个数的计算。

(6)

同时考虑到簇首要将收集到的信息融合发送给基站，式(1)(2)可知，离基站越近成为簇首的可能性越大，节点i按距离基站远近成为簇首的加权概率为：

(7)

经过每轮的选择、广播通信等能耗，下一轮簇首应选择剩余能量更多的节点，假设Ei(r)为节点i第r轮的剩余能量，Ei(r)=Ei(r-1)-ET(L,d)-ER(L,d)-EF(L)，Eave(r)为第r轮所有节点剩余能量平均值，在式(6)(7)的基础上，节点i再按初始能量不同、距离基站远近、剩余能量多少三方面影响成为簇首的加权概率为：

(8)

依据LEACH协议，每个节点在簇首选择过程中，产生[0,1]随机数，小于阈值选择为簇首，为了使具有更多剩余能量且离基站更近的节点成为簇首，阈值设计为：

(9)

其中:r为选择簇首轮数，G为本轮还未当簇首的节点集合，η1为对应的能量调节因子，η2为距离调节因子，η1+η2=1 且η1≥0,η2≥0。

2.2 数据传输

簇首收集簇成员信息，并采用单跳或多跳相结合的传输形式。在多跳传输时，假设中继簇首只是转发其他簇首数据，不进行簇首间数据融合，则将数据发送到基站的关键因素在于中继路由次数。为了选取合适的中继簇首，设定距离阈值dth，若di-BS(r)>dth，则需寻求中继簇首。

构建路由表时，需要寻求中继簇首的簇首，向所有簇首广播信息(包括剩余能量和基站距离)，其余簇首据接收信号强度估算与该簇首的相对距离，据文献[6]，符合式(10)的簇首可作为中继簇首。

(10)

2.3 算法流程

多级能量异构自适应传感网络成簇算法按轮进行，流程如图3所示，在簇首选择阶段，会根据节点与基站的距离、节点的剩余能量和节点选择成簇概率来确定节点成为簇首的阈值，再进行簇首间数据传输。

3 仿真结果及性能分析

3.1 仿真环境

将本文所提算法与经典LEACH算法和异构SEP算法进行对比，主要从网络稳定期和网络能量消耗量方面来测试该算法的节能有效性。在100×100的监测区域，随机分布100个节点，基站在监测区域外位置为(50,150)，所有节点与基站位置固定不具备移动性，初始能量分布于1～3J,算法所需实验参数在介绍各个公式时已说明，簇首传输数据量为4 000 bit,可计算出优化簇首个数，Kopt=9、η1、η2取值参考文献[6],当(η1,η2)为(0.5,0.5)时，节点的第一个死亡时间最晚，可最大限度延缓所有节点的整体死亡时间，从而有效均衡负载。LEACH算法、SEP算法与本算法相同参数上取值相同，在数据传输阶段，假设数据在传输过程中无丢失，并忽略信道干扰等随机因素。

图3 算法流程图

3.2 结果与分析

初始能量倍数ai对网络的稳定期影响如图4所示，从LEACH、SEP算法来看，随着ai的增长，并没有出现增长网络稳定期的效果，整体趋向呈现随着ai增长，缩短网络稳定期的现象。但本文算法随着ai增长，节点死亡时间延迟，有效延长网络稳定期，下面的实验结果是以ai=2作为能量倍数。

图4 随ai变化的网络稳定期

网络能耗主要是在节点的数据传输、广播、融合等方面。从图5中可以看出，LEACH算法能耗高于SEP算法和本文算法，本算法在前期能耗较低，但是到了后期能耗较大，这是因为SEP算法和LEACH算法在前期的死亡节点多，到了后期存活节点数量少，而本算法后期存活节点较多，消耗相对来说就高些。

图5 网络能耗

4 结束语

本文在LEACH算法和SEP算法的基础上，对簇首选择的阈值进行了改进，充分考虑了节点的剩余能量和基站距离的因素。在数据传输方面，当簇首与基站距离大于通信阈值时，需寻求中继簇首，从而整体上延长网络稳定期。仿真结果表明，本文算法可以有效均衡网络负载。

[1] Heinzelman W R,Chandralcasan A, Balalcrishnan

H.Energy-efficient Communication Protocol for Wireless Sensor Networks[C].Proceedings of the 33rd Annual Hawaii International Conference on System Sciences.Washigton,DC:IEEEComputer Society,2000,2:1-10.

[2] Younis O,Fahmy S,HEED: A Hybrid,Enengy-Efficient,Distributed Clustering Approach fo Ad Hoc Sensor Networks[J].IEEE Fras on Mobile computing,2004,3(4):660-669.

[3] 邓亚平,蔺换换.多级能量异构传感器网络能量有效的路由算法[J].计算机应用,2011,31(1):4-7.

[4] 刘唐,汪小芬.杨进.基于相对距离的多级能量传感网络成簇算法[J].计算机科学,2012,39(8):119-203.

[5] 张颖,季常刚.李俊甫.一种基于能量与距离的多级能量异构传感网络路由算法[J].上海交通大学,2014,48(7):953-958.

[6] 吴保强,张霓,邹涛,等.多级异构传感器网络距离和能量有效分簇算法[J].机电工程,2010,27(7):57-60.

A Clustering Algorithm for Multilevel Energy Heterogeneous Self-adaption Sensor Networks

Guan Zhiyan

(InformationInstitute,BusinessCollegeofShanxiUniversity,TaiyuanShanxi030001,China)

Based on the classical LEACH algorithm，considering the cluster head selection probability, the node residual energy and distance of base station ,this paper proposes a clustering algorithm for multilevel energy heterogeneous self-adaption sensor networks which improves the cluster head selection threshold, and the high energy and close distance nodes is selected as cluster head preferentially. In the process of data transmitting to the base station, the relay cluster head is selected so as to reduce the number of routing relays and save the energy. Simulation results show that the algorithm is more stable in the heterogeneous network environment.

energy heterogeneous; cluster head; residual energy

2017-03-31

山西大学商务学院教学改革基金项目(2015012)； 2016教育部人文社会科学研究规划基金项目(16YJAZH040)；山西省“十三五”高等院校规划课题(GH—16182)

关志艳(1983- )，女，山西太原人，讲师，硕士研究生，研究方向为无线传感器网络节点覆盖研究。

1674- 4578(2017)03- 0051- 04

TP301.6

A