无线传感器网络不依赖位置信息的能耗均衡拓扑控制

摘 要：针对无线传感器网络（WSN）稠密部署的特点，首先提出一种不依赖位置信息的拓扑构建（LTC）算法用于构造连通支配树型结构的虚拟骨干网。在此基础上，深入分析骨干节点的能量消耗以及数据传输时延，引入密度控制与数据传输率控制因子以均衡虚拟骨干网能耗，提出了不依赖位置信息的能耗均衡拓扑控制（LETC）算法。LETC算法依据各个区域不同的数据传输量，调整该区域虚拟骨干节点的布置密度，同时增加低能耗节点的传输速率以减少网络时延。理论分析与仿真表明，经过优化的LETC算法相比LTC能够更有效地均衡能耗，延长网络寿命24.1%，减少时延28.1%。

关键词：无线传感器网络；拓扑控制；不依赖位置信息；密度控制因子；速率控制因子

0 引言

无线传感器网络（Wireless Sensor Network， WSN）由部署在监测区域内大量廉价的微型传感器节点组成，通过无线通信方式形成一个多跳、自组织的网络系统，其目的是协作地感知、采集和处理网络覆盖区域中被感知对象的信息，并发送给汇聚节点。由于传感器节点能量有限且监测区域通常为非常恶劣或者人类无法到达的远程环境，对节点进行能量补给十分困难。如何在保证准确与迅速搜集信息的基础上，尽量控制节点能耗以延长网络寿命使其能更加长久地运行[1]，成了传感器网络研究领域的一个重大难题，而拓扑控制就是这个难题的一个重要解决方案。

拓扑控制指在保证网络连通域覆盖所有节点的前提下，通过功率控制和骨干网节点选择，剔除节点间不必要的通信链路，形成一个数据转发的优化网络结构。拓扑控制问题作为当前的研究热点，已经开展了大量的研究工作：文献[2]不再将虚拟骨干网的规模最小化作为衡量算法优越性的唯一标准，而是综合考虑骨干网的构建成本与路由成本，提出了一种保证路由开销的连通支配集结构虚拟骨干网的构建算法；文献[3]首先定义一种基于最小路由代价的连通支配集（α Minimum rOuting Cost Connected Dominating Set， αMOCCDS），针对连通支配集构建NPhard问题，给出了αMOCCDS构建的启发式算法；文献[4]提出了通过调整节点发射功率均衡节点能耗的算法，对剩余能量较少的节点降低其发射半径，剩余能量较多的节点增大发射速率，使所有节点的能耗趋于一致，以延缓能量空洞的出现，很大程度上延长了网络寿命；文献[5]提出了一种基于节点剩余能量的簇头节点选择机制，每个节点根据自身跟邻节点的剩余能量计算簇头声明报文发送的理论时间范围，在这个时间范围内没收到任何簇头声明的节点成为簇头，收到簇头声明报文的节点成为普通节点。

但是现有的拓扑控制研究大部分都假设已知节点精确位置信息，而在大规模传感器网络中，获取准确的位置信息是十分繁杂和困难的，所以这种对位置信息的严格依赖很大程度上限制了这些方法的实际可操作性。不依赖位置信息的拓扑技术可极大地提高网络系统在位置信息无法获取或部分可用情况下的有效性，因而成为近年来拓扑问题的研究热点。

本文提出一种不依赖位置信息的能耗均衡拓扑控制（Locationfree and Energybalanced Topology Control， LETC）算法。主要工作如下：首先，本文提出一种不依赖位置信息的拓扑构建（Locationfree Topology Construction， LTC）算法，构造出基于连通支配树结构的虚拟骨干网，并对其骨干节点的能耗和时延进行分析；在此基础上，引入密度控制因子和变速率控制，均衡虚拟骨干网的节点能耗分布，提出不依赖位置信息的能耗均衡拓扑控制算法LETC；最后，仿真表明，LETC算法能够充分利用网络中节点的剩余能量，均衡网络中的节点能耗，延长网络寿命。

2.2 算法描述

研究表明，连通支配树结构的虚拟骨干网在能效性、扩展性以及可靠性上都具有更加优越的表现[10]。本节讨论基于连通支配树结构的拓扑构建算法，并构建虚拟骨干网，算法不依赖各个节点的具置信息，具有更广泛的适应性。这种不依赖位置信息的拓扑构建（LTC）算法的具体流程见算法1。

算法1 LTC算法。

1）初始化算法，对任意一个节点，根据节点自身各项性能参数的不同设定一个权值，并标记为白色节点；选取汇聚节点作为连通支配树的根节点，并标记为黑色节点。

2）黑色节点作为父节点，对其所有邻节点按照权值的大小降序排列，取前f位的邻节点作为虚拟骨干网中父节点的子节点，标记为黑色，剩余的邻节点标记为灰色节点。 f=k・m，其中：m为黑色节点的邻节点数，k为选取骨干节点的比例。

3）对新入选的黑色节点重复2），直至网络中的所有节点均被标记为黑色或者灰色。

4）当黑色节点没有任何白色相邻节点时，它将被标记为灰色节点。

5）连通支配树构造完毕，所有的黑色节点构成虚拟骨干网。

虚拟骨干网进入工作状态一段时间之后，会有节点因能量耗尽而死亡，其修复流程见算法2。

算法2 连通支配树的修复。

1）当有骨干节点死亡时，它的所有灰色的相邻节点进入候选状态。

2）若候选节点能够连接不连通的两个骨干节点，则被标记为骨干节点。

3）若候选节点能够连接不连通的一个骨干节点与其他候选节点，则被标记为骨干节点。

4）若候选节点能够连接不能连通的两个其他候选节点，则被标记为骨干节点。

5）若候选节点没有任何子节点，它将重新进入睡眠状态。

6）若虚拟骨干网在死亡节点处重新恢复连通，则修复完成。

3 算法优化

2.3节分析了基于LTC算法的虚拟骨干网中节点传输数据的能耗和时延性能。本章综合考虑这两方面因素，对拓扑控制算法进行均衡能耗的优化，提出不依赖位置信息的能耗均衡拓扑控制优化（LETC）算法，以期进一步延长网络寿命。

3.1 密度控制因子

由图3可知，靠近Sink节点的骨干节点能耗远远高于其他骨干节点，当这些节点能量耗尽时，在汇聚节点周围会形成能量空洞，WSN就会失效。如果不能被及时修补，会造成网络的数据传输不畅，甚至引发整个网络的死亡。有模拟实验表明[13]，在监测区域内节点均匀分布的情况下，当汇聚节点周围的节点能量最先耗尽而造成网络失效时，在远离汇聚节点处还剩余大量的能量未被利用，有时甚至高达初始总体能量的90%。

为了解决无线传感网能耗分布不均匀的问题，LETC算法引入一个密度控制因子c，用来控制选取骨干节点的比例。在传感器网络中靠近汇聚节点的位置，往往也是通信量较大的区域，算法增大骨干节点的选取比例，使得更多的骨干节点来分担数据传输任务，节点承担数据传输任务减轻之后，就会延后能量空洞的出现时间。

而远离汇聚节点的骨干节点承担着较少的通信量，算法减小骨干节点的布置密度，这样使得树的节点密度根据该节点所要传输的数据量的多少而有所不同，均衡了虚拟骨干网络中节点的能量损耗，从而延长了网络的寿命。

考虑到某一区域监测节点的更换次数会直接影响该区域网络的工作寿命，密度控制因子c的取值应该予以一定的控制：c值过小会影响密度控制的力度，优化不明显；而过大的c值会使得该区域内骨干节点过多，睡眠节点过少，修复网络时比较容易出现因剩余节点太少而无法修复的情况，直接影响到网络的使用寿命。本文对密度控制因子c的取值范围作出如下规定：

为了提高仿真的精确性，实验进行10次随机均匀撒点，各形成一种网络拓扑结构。随后，对每种拓扑结构执行3次算法，将平均值作为最终的仿真结果。

图5给出了采用不同算法的情况下，虚拟骨干网节点能耗与其到汇聚节点距离的关系。从图5可以看出，基于LTC算法的虚拟骨干网能量分布非常不均衡，高能耗节点处会过早出现能量空洞，严重影响了网络的寿命；经过密度控制因子优化过后，最高能耗有了明显下降；变速率优化使得网络节点的剩余能量得到有效的利用。因此，LETC算法在均衡能耗方面效果显著，能够有效提高网络的使用寿命。

5 结语

无线传感器网络的稠密布置特点与能量空洞现象，造成了网络失效后能量的大量残留。本文提出了一种不依赖位置信息的能耗均衡拓扑控制算法LETC，通过构建基于连通支配树结构的虚拟骨干网，并在此基础上引入密度控制因子与变速率控制对骨干节点能耗进行均衡。仿真分析表明，该算法能推迟能量空洞的出现，延长网络寿命。另外，LETC试着利用对节点到汇聚节点的距离进行跳数近似，减少了大型无线传感网络对节点具置信息的依赖性。本文采用的是同构传感器节点模型，没有考虑异构网络的性能分析、网络构造以及优化问题，下一步工作准备针对异构传感器网络进行进一步的研究，考虑较为实际情况下的网络寿命与时延优化情况。

参考文献：

[1]OK C S， LEE S， MITRA P， et al. Distributed routing in wireless sensor networks using energy welfare metric [J]. Information Sciences， 2010， 180（3）： 1656-1670.

[2]DU H， WU W， YE Q， et al. CDSbased virtual backbone construction with guaranteed routing cost in wireless sensor networks [J]. IEEE Transactions on Parallel and Distributed Systems， 2013， 24（4）： 652-661.

[3]DING L， WU W， WILLSON J， et al. Efficient algorithms for topology control problem with routing cost constraints in wireless networks [J]. IEEE Transactions on Parallel and Distributed Systems， 2011， 22（10）： 1601-1609.

[4]ZENG Z， CHEN Z， LIU A. Energyhole avoidance for WSN based on adjust transmission power [J]. Chinese Journal of Computer， 2010， 133（1）： 12-22. （曾志文，陈志刚，刘安丰.无线传感器网络中基于可调发射功率的能量空洞避免[J].计算机学报，2010，133（1）：12-22.）

[5]CHEN Z， LUO P， YUE W， et al. An energyaware topology control algorithm for wireless sensor networks [J]. Chinese Journal of Sensors and Actuators， 2013，26（3）： 382-387. （陈志， 骆平，岳文静，等.一种能量感知的无线传感网拓扑控制算法[J].传感技术学报，2013，26（3） ：382-387.）

[6]YANG Y， KRISHNAMACHARI B， PRASANNA V. Energylatency tradeoffs for data gathering in wireless sensor networks [C]// Proceedings of the 23rd Conference on Computer Communications. Piscataway： IEEE， 2004： 224-235.

[7]SONG C， LIU M， GONG H， et al. ACObased algorithm for solving energy hole problems in wireless sensor networks [J]. Journal of Software， 2009， 20（10）： 2729-2743. （宋超，刘明，龚海刚，等.基于蚁群优化解决传感器网络中的能量洞问题[J].软件学报，2009，20（10）：2729-2743.）