多层无线异质传感网络的高效节能预测聚类算法*

成亚玲，谭爱平,谢丁峰

(湖南工业职业技术学院 湖南 长沙 410208)

多层无线异质传感网络的高效节能预测聚类算法*

成亚玲，谭爱平,谢丁峰

(湖南工业职业技术学院 湖南 长沙 410208)

无线传感网络设计主要是减少能源消耗，延长网络生存时间。介绍了一种异质传感网络应用于现存聚类算法的研究，并提出了一种高效节能的预测聚类算法，此算法能适应能源和目标异质的传感网络。根据能源和通信成本等各种因素，该算法能使节点选择簇头。相对于具有较低剩余能源的节点来说，具有较高剩余能源的节点成为簇头的概率较大，因此可以均匀消耗网络能源。为了减少聚类阶段进行广播时的能源消耗和延长网络生存时间, 建立了一种用于常规数据采集节点的能源消耗预测模式。相对于目前聚类的算法来说，仿真结果表明该算法可实现更长传感网络生存时间、更高能源效率和卓越网络监测质量。

无线传感器网络;节能；异质传感网络

0 引言

近年来，无线传感器网络(WSN)[1]已成为研究热点，并有广泛的潜在应用范围，主要运用在环境监测、军事探测、工业控制和家庭网络[2-5]。但在实际应用中，为了满足传感网络技术的各种应用程序要求，异质无线传感网络(Heterogeneous Wireless Sensor Networks，HWSN)[6]的研究已引起了更多关注。

HWSN是由不同类型的传感节点组成的,此传感节点的应用范围广泛[7-9]。对于HWSN来说，应优先考虑减少网络运行中能源消耗、改善网络负载能力和稳定性、延长网络生存时间。

组织聚类传感节点能有效减少网络中的能源消耗。由于能源配置和网络演变的动态性和复杂性，难以在异质网络中设计一个既节省能源，又能提供可靠数据传输的聚类协议。

本文提出了一种新型异质传感网络模式，此模式拥有异质监控目标、能源和所有异质节点。对于具有这些特性的异质网络来说，为了能更合理利用网络能源和延长网络生存时间，提出一种高效节能的预测聚类算法(Energy-Efficient Prediction Clustering Algorithm，EEPCA)。

通过比较通信范围内的一个节点能源和其他节点平均能源，EEPCA确定节点能源因素。根据所有节点内一次通信所消耗的平均能源比率，EEPCA确定通信成本因素。在节点成为簇头后，EEPCA确定理想平均能源消耗。节点成为簇头的可能性直接与能源因素和通信成本相关。在每回合节点聚类中广播能源信息时为了节省能源消耗，本文提出了用于节点的能源预测模式，此节点的数据采集(如温度、湿度)在时间间隔和信息长度方面有规律。考虑到网络环境变化和计算出的节点能源消耗与实际节点的能量消耗间的误差，如果在初始阶段的当前回合中节点的剩余能源和最后回合的预测数值之间的差异在一定范围之内，那么节点可设置为不需广播其能源信息。仿真结果表明,相比其他聚类协议(如LEACH、SEP和EDFCM)，EEPCA可以实现更长网络生存时间、更高能源效率和卓越网络监控质量。

1 相关工作

在无线传感网络中，LEACH[10]是最流行分布式聚类路由协议的一种。在初始化阶段，LEACH进行簇头选择。为了平衡所有网络节点的负载，LEACH在每一回合选择簇头节点。每一回合中可看出最佳簇头选择的比例。只有当节点i的可能性低于以下阈值的可能性，那么成为簇头公式如下：

(1)

其中，r为回合的当前数量，G为最后回合中未成功成为簇头的一系列簇头节点(rmod(1/popt))。

然而，LEACH存在一定局限性：(1)LEACH未考虑优化簇头的数量；(2)为了实现每一节点中均衡的能源消耗，LEACH必须基于以下2种假设：①每个节点的初始能源均等；②在充当簇头时每一节点所消耗的能源均等。

许多学者已对HWSN做了深入研究。文献[10]中改善了LEACH算法，并提出一种根据剩余能量选举簇头的LEACH-C算法。然而，每个节点需知晓当前网络的总能源之后才能确定其是否可成为簇头，但LEACH-C算法需得到路由协议的支持，因此此分布式实施难以实现。SEP[11]是为两层异质网络而设计的，但SEP不适合于多层异质网络。

为今后进一步研究,文献[6]、[12]-[14]中依据不同的初始能源讨论了异质网络模式。文献[15]中提出了一种用模糊逻辑来克服LEACH算法缺陷的簇头选择方法。通过调查发现使用模糊变量可延长网络生存时间。

文献[14]中提出EEHC协议。该协议基于同初始能源有关的加权概率来选择簇头。初始能源越高，成为簇头的概率则越高。然而该协议不能预测能源消耗，因此该协议的性能在异质网络方面受到限制，其中异质网络中的部分节点是常规数据采集节点。

文献[13]中提出EDFCM协议，该协议适用于三种不同异质节点的网络。在本协议下网络模型节点分为两种普通类型：一种是履行管理信息的功能；另一种是收集不同数据(分为类型0和类型1)。类型1具有更复杂的硬件和软件结构，因此其具有较多初始能源和更大数据传输能力，但该协议的应用范围仅限于只有两种普通节点的网络中。

文献[14]提出ERP聚类路由协议。在具备本质聚类特性的情况下，本文提出具有合适功能的进化算法。

2 系统模式和问题描述

2.1 无线传感网络中的异质模式

为了满足高效监控需求，本文描述HWSN模式的不同初始能源和监控目标。网络模式的基本假设如下：网络位于M×M正方形区域(如图1所示)；N传感节点随机分布于网络中；节点是固定的，且其基地台位于区域的中间位置。传感节点监测各种目标，并定义一些节点为常规数据采集(Regular Data Acquisition, RDA)节点：这些节点在固定间隔内送回固定长度的信息；而在采集数据中一些节点并不常规，导致送回的信息也不常规。

图1 随机异质网络

因此两种方式下节点为异质：(1)异质数据采集常规：采集数据时一些节点常规，而一些不常规。所有常规节点在循环期间传输n1～n2信息,且信息容量在[l1,l2] bit间；(2)所有节点的初始能源是异质的。

节点不具有任何位置信息，但却能根据接收的信号强度来计算出节点间距离。网络中的节点组织于聚类形式中。簇头执行数据融合功能并负责将合成数据传输至基地台。网络中只存在一个基地台。节点初始能源随机分布于坐标(Emin,Emax)中。对于任何节点i来说，其初始能源为Ei。

2.2 能源消耗模式

本文运用一种简单的能源消耗模式[10]来计算出通信过程中的能源消耗，同时忽略计算、储存等过程中的节点能源消耗。

通过距离d传输l bit信息时，传输器的能源消耗如下:

ETx(l,d) =ETx_elec(k)+ERTx_amp(l,d)

(2)

接收器的能源消耗如下：

ERx(l)=ERx_elec(l)=lEelec

(3)

其中，Eelec是每bit沿着传输器或接收器周围运行时的能源消耗；εfsd2和εmpd4是依赖于传输器放大模式的放大能源。

2.3 问题描述

EEPCA必须完全考虑以下因素：

(1)算法应完全分布并自行组织。每个节点必须决定是否能成为一个簇头或在聚类阶段中[10]属于簇头的一名成员；

(2)具有更多剩余能源的节点必须具有较高的可能性成为簇头，必须确保聚类的通信成本低，但能源并不是簇头选择的唯一因素；

(3)确保聚类负载平衡；

(4)在每一回合初始聚类阶段中广播节点时为了节省能源消耗，建立RDA的一种能源预测模式。

3 EEPCA 聚类算法

3.1 节点间的距离计算

(4)

(5)

节点建立了基于接收数据的邻居节点的一种路由表格，并在其通信范围内为所有节点节省了所有相关的信息。网络中的所有节点由每个节点的一个整数值来标记。存储于路由表格中的信息包含节点和邻居节点间的距离、簇头节点的ID、至簇头的距离、当前能源和预测能源消耗。

3.2 簇头选择

簇头节点可执行额外功能，如数据融合和信息传递。这些额外功能导致簇头节点能量过度消耗而迅速死亡。通常做法是利用簇头重分布使其他节点拥有更多机会成为簇头节点。

设置popt为成为最优簇头的比例，Pi成为节点i被选为簇头的概率。在能源异质的无线传感网络中，Pi计算复杂化。目前，通过使用节点当前剩余能源的比率和整个无线传感网络的平均能源值来确定异质无线传感网络中许多聚类算法来确定Pi参数，但是后者难以获取[13]，尤其对于那些不同节点监测不同目标物的网络。最终，主要误差很可能发生在预测平均能源中。

理想情况下，节点分布均匀，并能在相同频率和长度下送回数据。设置dtoBS为簇头节点和BS间的平均距离，设dtoCH为簇类的成员节点与簇头节点间的平均距离，其结果如下[10 ]：

(6)

最优簇头的数量如下[13]：

(7)

因此，最优簇头的比例如下：

(8)

(9)

(10)

(11)

因此，此两种节点的数量如下：

(12)

(13)

随机节点分布可看为泊松点过程[19]。理想的情况下，在圆圈A中有n个点，且均匀分布在A中的位置都是相互独立的随机变量。di是一个随机变量，并呈现出从一个泊松点(xi,yi)到此圆圈中心点的距离。圆圈内所有泊松点到中心点的预期值如下：

(14)

任何半径在中心点周围旋转后能得到一个圆圈，因此需要考虑一个随机半径上的泊松点分布。在圆圈内的所有泊松点分布均匀，且泊松点的密度与半径平方成比例。因此，在随机半径上的泊松点密度概率如下：

(15)

其中R是半径长度。

因此E(di)的计算如下：

(16)

通过式(15)和式(16)，到达簇头的距离小于d0的节点的预期平均距离如下：

(17)

到达簇头的距离大于d0的节点的预期平均距离如下：

(18)

因此，在理想情况下聚类的一次数据传输中平均能源消耗如下：

(19)

(20)

整合节点能源因素和通信成本因子，节点i成为簇头的概率如下:

(21)

其中α和β是计算因子，此因子主要是在演算Pi中调节能源因子和通信因子的比例，α+β=1。

LEACH阈值方式T(i)的限制应根据以下两个步骤得到完善：(1)推进T(i)进入多层异质网络中；(2)在EEPCA中，考虑能源因子和通信成本因子，并改善T(i)的演算方式，如下：

T(i)

(22)

当一个节点未成功被选为簇头时，rs是回合数量。一旦此节点被选为簇头，那么rs则被重设为0。

3.3 能源消耗预测机制

在网络完成一个回合之后，一个新的节点需被选为簇头。为了确定节点成为簇头的可能性，有必要重新评估能源因子和通信成本因子，这样就能获得当前节点的剩余能源。最早的方法如下，网络中的所有节点都在聚类第一个回合时执行广播。然而，当聚类每个回合进行广播时大量能源将被消耗。因此，本文为RDA节点提出一种能源消耗预测机制。

在r-1回合中，对于任何节点j来说将花费nj次来传输信息，且其长度为lj，另外节点i和节点j的距离为di,j。由于每个节点都会在通信范围和相互距离内保持所有节点的相关信息，节点j′的通信范围内的任何节点都能计算r-1回合中节点j的能源消耗如下：

(23)

当开始执行r-1回合时，在r回合的初始阶段能预测出节点j剩余能源如下：

Ejr-prediction=Ejr-1-Ejr-1-comsume

(24)

由于受诸多因素影响(如网络环境改变)，当开始执行r回合时，所有节点需重新聚类，且其新的簇头需被重新选择，确定节点j。

当前节点的剩余能源的当前剩余能源是否在最后一轮回合被预测，其结果如下：

(25)

如果γ小于常数ε，那么能接受能源预测误差。在初始阶段r回合中，节点j不能广播其能源信息，且根据计算结果其剩余节点能在路由表中更新节点j′。

4 仿真实验

4.1 仿真环境构建

本文提出一种评估性能的算法，且在MATLAB中进行了仿真实验。实验随机仿真了在100 m×100 m范围内的传感节点。在形成之后，节点成为静止状态，且100个节点随机分布于此区域内。假设BS位于区域内的中心位置，用于此实验中的参数如表1所示。比较EEPCA、LEACH、SEP和EDFCM的性能，所有结果都是100次独立实验的平均值。

表1 用于仿真实验中的参数

4.2 实验结果和分析

在EEPCA中，α和β分别是计算pi中调节能源因子和通信成本因子的计算因子，并满足α+β=1。改变α和β数值后观察EEPCA的性能。此实验设置所有节点的能源为异质，且其初始能源是1～3 J。除了RDA节点外，网络中的所有监测的目标物都为异质。在TDMA时间段中所有节点会发送4 000 bit的信息给簇头。

当α和β数值随着上述情况改变时，图2表明了第一个节点的死亡时间、10%和50%节点的死亡时间。当α数值在0.74附近时，第一个节点的死亡时间和10%节点的死亡时间出现在最后；然而当α数值在0.66～0.68范围内时，50%节点的死亡时间出现在最后。在后续的实验中α和β数值统一为0.7和0.3。

图2 α和β′数值对性能的影响

当所有节点为异质时，以往的实验环境通常会比较EEPCA、LEACH、SEP和EDFCM，并通过测试来分析EEPCA簇头的选择机制对算法性能的影响。

图3的仿真实验表明了以往实验环境下不同算法中死亡节点数量的变量，此变量随着时间的推移而得到。图3显示LEACH不能充分利用异质节点的额外能源，其稳定期较短，且其节点死于固定速率中。与LEACH比较，SEP是稳定期较长。EEPCA和EDFCM在X轴上的曲线坡度较小，原因在于EEPCA能在异质网络中给每个节点均匀分配能源消耗，且其第一个节点和最后一个节点的死亡时间相对较近。

图3 节点的死亡时间

在以往实验环境中，改变整个节点数量中异质节点的比例，并观察每个算法的性能。当异质节点的比例在0～100%改变时，图4展现了从开端至第一个节点死亡时的回合数量。此实验中所有非能源异质节点的初始能源为2 J。

图4 当异质节点改变时第一个节点的死亡时间

先于10%节点面临死亡的时间，此时网络能送回高质量、高可靠性的BS数据[13]。因此图5表示从开端至10%节点死亡期间的回合数量，也就是其稳定期。

图5 当异质能源节点的数量改变时网络的稳定期

对于异质网络来说，如果LEACH不是一个聚类算法，那么随着异质节点的增加，其得到的网络稳定期将迅速减少。相对于LEACH，SEP能获得25%以上的稳定期，基本上与参考文献[11]中呈现的环境结果一致。由于EDFCM考虑不同节点的异质能源，因此其比SEP能获得更长的稳定期。EEPCA考虑了通信过程中除剩余能源以外的节点能源消耗，因此在异质节点比例增加的过程中EEPCA的稳定期减少率明显低于其他算法。随着异质节点的比例更大，就能获得更长的稳定期。

此实验中介绍了RDA节点。设置网络中的所有节点能源都为异质，那么50%的节点为RDA节点，10%节点为故障节点。所有RDA节点将在一回合中发送信息3～7次，其信息容量基本在2 000～6 000 bit之间。检查网络稳定期中常量ξ的影响，结果如图6所示。

图6 网络稳定期中常量ξ的影响

图6表明，当ξ的数值在0.92～0.93之间时，网络得到最大稳定期。

介绍了RDA节点后，应检查所有算法的稳定期。此实验设置所有节点为异质能源，50%的RDA节点的常数ξ为0.93,网络中10%的节点为故障节点。图7表明EEPCA算法能有效改善异质网络稳定期结果。

图7 网络稳定期

在介绍了能源消耗预测机制后，每回合中聚类阶段的广播频率有效减少。因此，与其他3种算法相比，EEPCA能有效改善网络稳定期，通过异质网络中的两种方式：初始能源和被检测的目标物。

图8 BS中接收的信息数量

图8显示了所有的节点能量异构，50%节点为RDA节点，10%节点为故障节点。在EEPCA中，BS所接收的信息数量长时间呈线性上升趋势，然而在其他算法中，早期BS所接收信息数量的增长比率开始下降。为了在此四种算法中得出网络出现故障时所有节点送回BS的信息总数，由EEPCA收集的数据总量比其他三个算法收集到的数据总量要多。因此，EEPCA有更高的网络监测质量。

5 结论

本文通过使用不同初始能源和监测目标物来描述HWSB模式，并提出用于多层异质传感网络中的一种高效能源预测聚类算法：EEPCA。基于能源因子和通信成本因子，EEPCA中的每个节点都独立选择自身作为簇头节点，簇头选择的概率与节点当前剩余能源和平均通信成本有关。同时，考虑到WSNs通常被用于监测的目标物(如温度、湿度)，且此目标物需定期报道数据及其报道数据的长度通常是固定的，因此给RDA节点介绍了一种高效能源消耗预测机制。通过比较LEACH、SEP、EDFCM和EEPCA，仿真实验表明EEPCA能获得更长生存期、更高效能源、更优质网络监测，且其性能高于其他协议的性能。

[1] AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y, et al. Wireless sensor network: a survey[J]. Computer Networks, 2002, 38(4): 393-422.

[2] HAENGGI M. Handbook of sensor networks: compact wireless and wired sensing systems[M].Boca Raton: CRC Press, 2005.

[3] CHONG C Y, KUMAR S P. Sensor networks: evolution, opportunities, and challenges[J]. Proceedings of the IEEE, 2003,91(8): 1247-1256.

[4] ESTRIN D, GIROD L, POTTIE G, et al. Instrumenting the world with wireless sensor networks[C].Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP ’01),2001:2033-2036.

[5] CHANG C Y, CHANG H R. Energy-aware node placement, topology control and MAC scheduling for wireless sensor networks[J]. Computer Networks, 2008, 52(11):2189-2204.

[6] DUARTE-MELO E J, LIU M. Analysis of energy consumption and lifetime of heterogeneous wireless sensor networks[C]. Proceedings of the IEEE Global Telecommunications Conference(GLOBECOM ’02), IEEE Press, Taipei, 2002:21-25.

[7] de FREITAS E P, HEIMFARTH T, PEREIRA C E, et al. Evaluation of coordination strategies for heterogeneous sensor networks aiming at surveillance applications[C]. Proceedings of the IEEE Sensors Conference (SENSORS’09), Christchurch, New Zealand, 2009: 591-596.

[8] CORCHADO J M, BAJO J, TAPIA D I, et al. Using heterogeneous wireless sensor networks in a telemonitoring system for healthcare[J]. IEEE Transactions on Information Technology in Biomedicine, 2010,14(2): 234-240.

[9] DIETRICH I, DRESSLER F. On the lifetime of wireless sensor networks[J]. ACM Transactions on Sensor Networks, 2009,5(1):531-539.

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

[11] SMARAGDAKIS G, MATTA I, BESTAVROS A. SEP: a stable election protocol for clustered heterogeneous wireless sensor networks[C]. Proceedings of the International Workshop on SANPA, 2004:251-261.

[12] MHATRE V P, ROSENBERG C, KOFMAN D, et al. A minimum cost heterogeneous sensor network with a lifetime constraint [J]. IEEE Transactions on Mobile Computing, 2005,4(1):4-14.

[13] ATTEA B A, KHALIL E A. A new evolutionary based routing protocol for clustered heterogeneous wireless sensor networks[J]. Applied Soft Computing Journal, 2012,12(7): 1950-1957.

[14] DILIP K, TRILOK C A, PATEL R B. EEHC: energy efficient heterogeneous clustered scheme for wireless sensor networks[J]. Computer Communications, 2009,32(4):662-667.

[15] KIM J M, PARK S H, HAN Y J, et al. CHEF: cluster head election mechanism using fuzzy logic in wireless sensor networks[C]. in Proceedings of the 10th International Conference on Advanced Communication Technology (ICACT ’08), 2008: 654-659.

Energy efficient clustering algorithm of multilayer wireless heterogeneous sensor networks prediction

Cheng Yaling, Tan Aiping, Xie Dingfeng

(Hunan Industry Polytechnic, Changsha 410208, China)

In designing wireless sensor networks, it is important to reduce energy dissipation and prolong network lifetime. This paper presents research on the existing clustering algorithm applied in heterogeneous sensor networks and then puts forward an energy-efficient prediction clustering algorithm, which is adaptive to sensor networks with energy and objects heterogeneous. This algorithm enables the nodes to select the cluster head according to factors such as energy and communication cost, thus the nodes with higher residual energy have higher probability to become a cluster head than those with lower residual energy, so that the network energy can be dissipated uniformly. In order to reduce energy consumption when broadcasting in clustering phase and prolong network lifetime, an energy consumption prediction model is established for regular data acquisition nodes. Simulation results show that compared with current clustering algorithms, this algorithm can achieve longer sensor network lifetime, higher energy efficiency, and superior network monitoring quality.

WSN; energy-efficient； heterogeneous sensor networks

TP14

A

10.19358/j.issn.1674- 7720.2017.02.019

成亚玲，谭爱平,谢丁峰.多层无线异质传感网络的高效节能预测聚类算法[J].微型机与应用，2017,36(2)：60-65，69.

湖南省教育厅优秀青年科研项目(15B072)；湖南省教育厅科研项目(15C0452)

2016-08-17)

成亚玲(1981-)，女，硕士，讲师，主要研究方向：软件工程、模式识别和人工智能。

谢丁峰(1978-)，男，硕士，讲师，主要研究方向：软件工程，视频压缩。

谭爱平(1979-)，男，硕士，副教授师，主要研究方向：数据挖掘、生物识别。