基于睡眠机制的WSN簇维护算法改进

［王瑞］



基于睡眠机制的WSN簇维护算法改进

［王瑞］

摘要

局域按需簇维护方法（LDMC）能够明显延长网络的生命周期，但是网络中仍存在大量的冗余节点，在成簇阶段也没有考虑剩余能量和节点密度对簇头的影响，提出了一种改进的无线传感网簇维护算法。该算法在簇头的选举阶段引入了节点剩余能量和密度因子，避免能量过低的节点担任簇头；同时针对网络中存在的大量的冗余节点提出部分冗余节点睡眠机制，使网络的整体生命周期得以进一步延长。NS2仿真结果表明，与原局域按需簇维护算法相比，该改进优化算法可减少业务中断时长、增加发送的数据包总量；仿真条件下网络的生命周期相较于LDMC方法最多可延长16.3%；网络规模越大，运用该算法的优势越明显。

关键词：簇维护 睡眠机制 剩余能量 密度因子 生命周期

王瑞

重庆邮电大学信息与通信工程学院，硕士研究生，主要研究方向为物联网理论与技术。

0 引言

无线传感网由计算、通信、能量等资源均受限的大量传感器节点以多跳、自组织的方式组成，是物联网感知层的核心支撑[1]。无线传感网自二十世纪九十年代提出以来，引发了世界范围内的广泛关注，特别是美国、日本、欧洲等发达

国家或地区陆续开展了无线传感网方面的探索性研究[2]。传感器节点一般通过电池供电，并且工作于无人值守的环境中，能量补给困难，甚至是一次性的，因此如何节省能量，延长网络的生命周期显得十分重要[3,4]。

基于簇的层次式拓扑结构是无线传感网最流行的组网模式，具有管理方便、能量利用高效、数据融合简单等优点[5-7]。目前，普遍采用全网周期性重新成簇的簇维护模式，导致超范围过度维护，存在维护成本高、能量浪费严重、周期性服务中断、响应不及时等缺点。因此，如何优化管理与维护网络拓扑、最大限度地均衡网络内节点的能量消耗以延长整个网络的生命周期一直是无线传感网的研究热点。

1 相关工作

一些研究者针对传统全网周期性成簇存在的维护成本高、能量消耗大、针对性差、周期难确定等问题进行了改进：文献[8]通过在簇头形成过程中引入节点剩余能量，是对LEACH改进的一种双轮成簇协议，形成混合型网络拓扑结构；文献[9]提出由汇聚（Sink）节点采用集中式算法产生簇头，不需要每轮都选举簇头，簇头是否轮换取决于簇的能量消耗；文献[10]提出了两种集中式簇头产生算法：LEACH-C由基站负责完成簇头选取工作,只有能量高于网络平均剩余能量的节点才有可能成为簇头；LEACH-F要求一旦簇被形成，簇的结构就不再改变，簇内节点无需每轮循环都构造簇，减少了构造簇的开销；文献[11]创造性地提出并构建了基于事件驱动的“局域”、“按需”簇维护算法(LDMC)，一旦网络中出现需要维护的事件，能够快速及时地在簇受损的局部范围内进行维护，明显提高能量利用率、延长网络生命周期；文献[12]进一步从系统实现的角度进行了完善和仿真测试；在此基础上，文献[13]针对不同的簇受损情形建立了一种可以满足不同簇维护需要的多模簇维护机制(M2CM)，以自适应局域按需簇维护的需要。

局域按需簇维护方法的提出和多模簇维护机制的构建，克服了传统簇维护方法存在的弊端，能够明显减少簇维护的能量消耗、延长网络生存时间，并增加传输数据包的总量。但这种方法在成簇阶段时采用了LEACH算法，没有考虑到节点剩余能量和节点的邻居节点数对簇头选取的影响；传感器网络中节点稠密撒布、节点间的有效探测范围相互重叠，使得同一时刻不同节点采集来的数据存在大量的冗余，造成不必要的能量浪费。为进一步完善LDMC算法，本文提出IACM算法。该算法在簇头选取阶段，引入剩余能量因子和节点密度因子，对LDMC算法的簇头选取阈值进行改进，使得簇头的分布更加合理，避免了剩余能量小的节点或者孤立节点成为簇头；同时引入节点睡眠机制，使得剩余能量小的部分冗余节点进入睡眠状态，不进行数据监测，节省了节点能量，进一步延长了网络生命周期、提高了数据包发送量。通过对T (n)的改进以及冗余节点睡眠机制来最大限度地减少簇维护的能量消耗和服务中断次数，延长网络生命周期。

2 系统假设与能耗模型

在物联网感知层中，节点一般分为Sink节点和普通节点。本文假设：

（1）网络中有一个Sink节点和多个普通节点，且位置都是固定不变的；

（2）Sink节点的能量是可补充的，但普通节点的能量是受限的；Sink节点留存整个网络的拓扑结构信息；

（3）普通节点具有相同的初始属性（如无线电发射功率、通信半径、能量等）；

（4）普通节点将收集的数据发送给簇头，簇头负责将收集的数据进行融合，然后以单跳或者多跳的方式传送给Sink节点。

本文采用的无线通信能量消耗模型如图1所示。

图1 传感器网络能量消耗模型

传感器节点发送l bit的信息，传输距离为d，则发送端消耗的能量可表示为：

式中，Eelec为无线收发电路的能量消耗，和分别为自由空间模型和多径衰减模型中功率放大器的能量消耗；d0为传输距离门限，可用式(2)表示：

传感器节点接收l bit消息的能耗为：

3 改进的算法

原簇维护算法根据不同的场景，设置了相应的维护动作，分别为有(无)簇头重选、并入邻簇、簇分裂、时隙再分配、簇合并以及多簇重新成簇等簇维护策略，有效地延长了网络的生存时间。但是该算法在网络初始化时，采用了LEACH算法进行分簇，没有考虑节点密度对簇头的影响；由于无线传感网节点密度大，大量的冗余节点造成了不必要的能量消耗。

针对LDMC算法的不足，考虑到簇头节点担负着融合簇内信息，并且发送至Sink节点的任务，簇头节点的寿命在很大程度上影响了整个网络的生存时间。这里提出了两点改进方法：、

（1）在簇头选择时，求出网络的最优簇头数，同时考虑节点剩余能量和密度，避免能量低或者邻居节点少的节点被选为簇头；

（2）根据节点监测到的数据的相似度，使一部分节点进入睡眠状态，减少能量消耗。

3.1 簇头选举阶段

原LDMC算法在成簇阶段，采用LEACH算法进行簇的生成，没有考虑能量和节点密度对簇头选举的影响。本文提出的改进算法，充分考虑了节点剩余能量和节点密度对簇头选举的影响，在簇头选举时，对阈值T(n)进行重新设定，使簇头的分布更加合理。

1 最优簇头数

在网络其他条件一定时，当簇头数在某一值时，网络所消耗的能量最少，我们称该值为最优簇头数。我们以单跳LEACH网络求解最优簇头数。假定在的区域内分布了N 个节点，簇头数为k 个，EDA表示数据融合消耗的能量，计算最优簇头数Kopt。簇头的能量主要消耗在接收簇内节点的数据、数据融合以及把数据传输给Sink节点。每个簇头节点的能耗为：

簇内采用自由空间传输模型，假设簇内成员节点每次发送l 比特的数据包，dCH表示到簇头的距离，则一个簇内成员节点的能量消耗为：

整个网络是分布在M´ M 的区域内，有k个簇，则每个簇所占的区域平均是M2/ k ，假设这是一个圆形区域，则半径，设区域内节点的分布概率为，则簇内成员节点到簇头的距离的平方的数学期望是：

把式(7)带入式(5)可以得到簇内一个成员节点的能量消耗为：

因此一个簇在这一轮消耗的能量为：

则k 个簇消耗的能量E 可表示为：

等式两边对k 进行求导，得出最优簇头数kopt为：

2 剩余能量因子

在簇头选取时考虑节点当前的剩余能量，增加剩余能量大的节点的当选概率，引入剩余能量因子：

3 密度因子

节点周围邻居节点的多少，对簇头的选取也有重要影响，在剩余能量相等的情况下，节点的密度越大，当选簇头的概率越大。节点的密度因子可表示为：

其中Ntotal( i )为节点i的有效通信区域内的节点总数；Nalive为网络中存活的节点总数。

4 阈值的改进

通过引入节点剩余能量因子和密度因子，可以使簇头的选择更加合理，有助于节省能量，延长网络的生命周期。改进的阈值为：

式中，k+ k = 1，p'= k/ n 。当簇头选举完

12opt成后，各个节点根据接收到的广播信息的信号强度，选择信号最强的簇头加入。当所有节点都加入簇后，进入稳定的数据传输阶段。

在网络初始化成簇以及执行重新成簇的维护动作进行簇头选取时，改进的阈值可以使簇头位置更加合理，延长簇头的寿命，减少重新选择簇头造成的网络中断，进而延长网络生存时间。

3.2 簇维护阶段

传感器网络中节点稠密撒布、节点间的有效探测范围相互重叠。这使得在网络数据收集应用中，同一时刻不同节点采集的数据间存在空间相关性，造成观测信息间存在较高空间冗余度，使得网络产生不必要的能量消耗。本文根据两个节点监测到的数据的时空相关性[14]，使一部分节点进入睡眠状态，不进行信息监测，直到将其唤醒，并在本簇内进行广播睡眠节点的ID。

分簇完成后，当簇头接收一轮数据之后,若是有两个节点监测的数据的相似度达到一定值时，簇头使得两个节点中能量较小的进入睡眠状态，不再进行数据监测，直到将其唤醒。

随着网络的运行，当网络中出现了需要维护的事件时，立即对网络进行维护，具体的维护机制如下：

（1）有簇头重选

当进行有簇头重选时，首先簇头唤醒本簇内的睡眠节点，然后簇头在簇内广播cluster_rebuild消息，收到消息的簇内节点把自己的剩余能量和ID发送给簇头，簇头选择其中剩余能量最大的节点作为簇头，并向簇内其他节点和邻近的簇头广播簇头更换消息。当新簇头接收一轮簇内成员节点发送的数据后，根据两个节点发送的数据的相似度使能量小的节点进入睡眠状态，不再进行数据监测，同时在本簇内广播睡眠节点的ID。

（2）无簇头重选

由最先发现簇头失效的节点唤醒本簇内的睡眠节点，然后进行无簇头重选。当新簇头接收一轮数据之后，根据数据的相似程度使剩余能量小的部分节点进入睡眠状态，不再进行数据监测，同时在簇内广播睡眠节点的ID。

（3）并入邻簇

当需要执行并入相邻簇的维护动作时，由需要加入邻簇的簇头唤醒本簇内的睡眠节点。动作完成后，新簇头根据接收到的数据的相似程度剩余能量小的部分节点进入睡眠状态，并在簇内广播睡眠节点的ID。

（4）簇分裂

当执行簇分裂的维护动作时，首先由需要分裂的簇的簇头唤醒本簇内睡眠节点，然后执行簇分裂。当维护动作完成后，新簇头在接收一轮数据后，根据数据的相似程度使剩余能量小的部分节点进入睡眠状态，并在簇内广播睡眠节点ID。

（5）簇合并

需要进行合并的簇的簇头将各自簇内睡眠节点唤醒，然后执行簇合并动作。合并完成后，当新簇头接收一轮数据之后，如果两个节点的监测数据相似度达到一定程度，簇头使得能量小的那个节点进入睡眠状态，并在簇内广播睡眠节点的ID。

（6）多簇重新成簇

需要执行重新成簇的各个簇头唤醒本簇内的睡眠节点，然后执行多簇重新成簇的维护动作。当新簇头产生后，簇头根据接收到的数据的相似度使一部分节点进入睡眠状态，并在本簇内广播睡眠节点的ID。

当维护完成后，继续进入稳定的数据传输阶段。随着网络的运行，当网络中发生需要维护的事件时，网络会在受损的局域范围内进行维护，执行相应的改进后的维护动作，如此循环。

4 仿真与结果分析

4.1 仿真场景设置

本文采用网络仿真软件NS-2.34，仿真区域为100m×100 m，在其中随机分布100个和200个传感器节点，基站位于场景上方。具体的节点仿真参数配置如表1所示。

表1 仿真参数配置

4.2 仿真结果分析

图2为在网络运行过程中当出现了受损簇时分别采用LDMC和改进算法的簇维护方法所对应的网络中断时长对比图。由图2可见，当网络中出现了受损簇时，采用改进算法比LDMC簇维护方法更能减少网络中断时长，约减少了11.48%，同时也减少了业务中断次数，更加有利于簇结构稳定。这是因为在簇头选举时，考虑了剩余能量因子和密度因子的影响，重新设置阈值，使得节点剩余能量大、邻居节点多的节点当选簇头的概率增大，避免了节点剩余能量小的节点当选簇头造成的频繁的网络中断；同时，在网络中引入节点睡眠机制，使网络中剩余能量小的部分冗余节点进入睡眠状态，不进行数据监测，节省了能量，同时也减轻了簇头的负担，节省了能量，使网络运行更加稳定，也即减少了网络的中断时长和中断次数。

图2 LDMC与改进算法中断时长对比

由图3可知，当网络中有100个节点时，LDMC算法的网络存活时间是744s，LEACH协议的网络存活时间为521s，改进算法的网络存活时间为835s，较LDMC算法延长了约12.2%，相比于LEACH协议延长了约60.3%。这是因为该改进算法使得簇头分布更加合理，引入睡眠机制，减少了节点冗余和中断次数，节省了能量消耗，从而延长网络存活时间。

图3 两种算法的网络存活时间对比

由图4可知，LDMC算法接收了78235比特的数据量，改进算法接收了89189比特的数据量，提高约14.0%；LEACH协议中基站接收了52374比特的数据，改进算法较之提高了约70.3%。由此可见：改进算法在延长网络存活时间的同时，增加了基站接收到的数据包数量。

图4 数据传输量对比

5 结束语

本文在相对于传统全网周期性重新成簇具有较大优势的局域按需簇维护算法基础上，提出一种改进优化算法。首先引入剩余能量因子和节点密度因子对选举阈值进行改进，使得剩余能量大、邻居节点多的节点称为簇头的几率增大；然后根据节点监测数据的相似度使一部分能量低的节点进入睡眠状态，减少了数据冗余度，节省了节点的能量消耗，延长了簇头的存活时间，进而使得网络的生命周期得以延长。仿真测试结果表明：相比于原局域按需簇维护算法，改进算法有助于减少业务中断次数和中断时长，降低用于簇维护的能量消耗，增加传输数据包总量，网络生命周期最多延长了12.2%；网络规模越大，运用该优化算法的优势越明。

参考文献

1Li Shancang, Xu Lida, Zhao Shanshan. The internet of things: a survey[J], Information Systems Frontiers, 2015, 17(2):243-259

2Iyengar R, Kar K, Banerjee S. Low- coordination topologies for redundancy in sensor networks [C]// Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing, Chicago, USA: ACM，2005: 332-342

3钱志鸿，王义军. 面向物联网的无线传感器网络综述[J]. 电子与信息学报，2013, 35(1):215-225

4孙波，高随祥. 无线传感器网络中最大化簇寿命的优化模型[J].计算机仿真，2008, 25(2):116-120

5HEINZELMAN W R, CHANDRAKA- SAN A, BALAKRISHNAN H. Energy-efficient communication protocol for wireless micro sensor networks[C] // Proceedings of the 33rd Annual Hawaii International Conference on System Sciences. Hawaii: IEEE Computer Society, 2000: 10-15

6Handy MJ, Haase M, Timmermann D. Low energy adaptive clustering hierarchy with deterministic cluster-head selection[C]// Proceedings of the 4th IEEE Conf. on Mobile and Wireless Communications Networks, 2002: 368-372

7YOUNIS O, FAHMY S. HEED: A hybrid energy- efficient distributed clustering approach for Ad hoc sensor networks [J]. IEEE Transaction on Mobile Computing, 2004, 3(4): 366-379

8Chan H, Perrig A. ACE: An emergent algorithm for highly uniform cluster formation[C]// Proceedings of the 1st European Workshop on Wireless Sensor Networks. LNCS 2920, Berlin: Springer Verlag, 2004: 154-171

9Tillapart P, Thumthawatworn T, Pakdeepinit P. Method for cluster heads selection in wireless sensor networks[C]// Proceedings of the 2004 IEEE Aerospace Conf. Chiang Mai: IEEE Press, 2004: 3615-3620

10Gao J J, Liu Y H, Zhu L Q, et al. The LEACH-DCHS protocol cluster maintenance algorithm based on WSN[J]. Computer engineering and applications, 2009, 45(30): 95-97

11廖明华, 张华, 王东. 基于LEACH 协议的簇头选举改进算法[J]. 计算机工程, 2011, 37(7): 112-114

12胡向东，徐慧芬，张力. 物联网感知层局域按需簇维护模型与算法[J]. 软件学报, 2015,26(8):2020-2040

13胡向东，徐慧芬，王恺. 无线传感网多模簇维护机制与算法[J].系统工程与电子技术，2015,37(10): 2376-2382

14王军，王正路，程勇. 基于时间序列预测模型的簇型数据收集机制[J]. 计算机应用，2014,34(10):2766-2770

DOI:10.3969/j.issn.1006-6403.2016.02.012

收稿日期：（2016-01-12）