狭长域无线传感器网络动态能量均衡控制

柳 艳，耿 鹏，杨 洁

(南京工程学院，江苏 南京 211167)

狭长域无线传感器网络动态能量均衡控制

柳 艳，耿 鹏，杨 洁

(南京工程学院，江苏南京211167)

针对基于连通支配集的无线传感器网络拓扑构造算法在狭长域环境应用中会存在能量失衡的问题，提出了狭长域无线传感器网络动态能量均衡控制方法。该方法基于A3、A3 Cov、EECDS和CDS Rule K等经典拓扑构造算法，将节点动态能量均衡的方法融入到上述算法之中，并对介数中心性重要节点进行了缓冲管理。在狭长区域内布置随机网络，对基于介数缓冲的动态能量均衡拓扑控制算法进行了仿真分析。结果表明，该算法能够更加充分利用节点能量，延长了网络寿命，提高了狭长域无线传感器网络的整体性能。

无线传感器网络；狭长域；能量均衡；介数

0 引言

无线传感器网络[1](Wireless Sensor Networks, WSN)是指在被探测区域中布置大量的传感器节点，这些节点能够形成一个自组织无线网络，每个节点通过无线信道和邻居节点进行通信，以多跳方式将感应数据传递到指定的集合位置(通常称之为Sink节点)。由于应用环境的恶劣性和节点数量的庞大性，导致网络中节点往往难以补充能量[2]，所以采取相应的措施减少网络能量消耗是无线传感器网络的重要研究课题。本文所关注的是从拓扑层面上对网络结构进行优化控制，以达到节约能量的目的。

从数据的完整性和有效性来看，无线传感器网络存在的基本问题是：在保证网络连通性和覆盖率的前提条件下，尽量延长网络的生命周期。连通性和覆盖率可以通过增加传输半径、感应半径和节点密度来进行保证，但这样会带来更多的能量消耗和更高的网络成本[3]。一种有效的方法是网络部署时保证一定的节点密度冗余；网络运行时利用相关机制在不影响连通性和覆盖率的同时关闭一部分节点，使没有数据收发任务的节点进入睡眠状态；网络运行到一定阶段时再将这些睡眠节点逐次唤醒[4-6]。在无线传感器网络的研究中，使用较为广泛的拓扑控制(Topology Control, TC)方法是在冗余网络中寻找连通支配集(Connected Dominating Set, CDS)，再在此集合中求解最小值，以构建虚拟骨干网(Virtual Backbone Network, VBN)。求解最小连通支配集本质上是NP-hard问题[7]，无法得到精确答案，因此研究此问题的目的是在尽量平衡连通性、覆盖率和生命周期的情况下，寻求一种近似最佳结果。文献[8—11]所提出的基于连通支配集的无线传感器网络拓扑构造算法在狭长域环境应用中会存在能量失衡的问题，基于此问题，本文提出了狭长域无线传感器网络动态能量均衡控制方法。

1 连通支配集网络构造算法

无线传感器网络可抽象为由若干个节点及节点与节点之间的连接边组成，这样便形成了由节点集合V和连接边集合E组成的图G=(V,E)，集合E中每个元素都有集合V中的两个元素与之对应。网络中的节点数可描述为N=|V|，节点与节点之间的连接边数可描述为M=|E|。假设网络中连接边的存在总是意味着一定有两个能够互相传输数据的节点在边的两端，不考虑连接强度，并且两个节点之间至多只有一条连接边，节点本身不可以自连接，这样就形成了无方向、无加权的简单图，本文即是基于简单图进行讨论。简单图中与支配集相关的定义如下描述：

定义1 支配集与连通支配集：若图G=(V,E)中存在D⊆V,∀u∈VD，在D中至少存在一个节点与u之间存在连接边，则集合D为图G的一个支配集。可以看出，支配集的个数往往不唯一。若D中的节点是连通的，则集合D为图G的一个连通支配集。

定义2 极小支配集：若对于图G的一个支配集D，其子集均不能成为图G的支配集，则D为图G的极小支配集。

定义3 最小支配集：对于图G中的所有支配集，可以找到包含节点数最少的那个支配集，称之为最小支配集。容易得到，最小支配集一定是一个极小支配集，反之不然。

定义4 独立集：对于图G=(V,E)中的一个集合I⊆V，I中任意两个节点都不存在连接边，则称集合I为图G的一个独立集。

定义5 极大独立集：对于独立集I，若存在∀v∈VI，使得I与{v}的并集不是独立集，则称该独立集I为极大独立集。

定义6 最大独立集：对于图G中的所有独立集，可以找到包含节点数最多的那个独立集，称之为最大独立集。

定义7 生成树：对于图G的一个子图T，若T是一棵不含闭合路径的连通树，且节点v(T)=v(G)，则称T是G的生成树。

无线传感器网络中经典的基于连通支配集的拓扑构造算法有A3[8]、A3 Cov[9]、EECDS[10]和CDS Rule K[11]等。其中，A3和A3 Cov属于基于增长树的拓扑构造算法；EECDS是基于连通独立集的拓扑构造算法；CDS Rule K是基于剪枝的拓扑构造算法。

2 动态能量均衡下的拓扑维护

一个完整的无线传感器网络拓扑控制应该包含拓扑构造和拓扑维护两方面[12]。上述拓扑构造算法即是在保证网络连通和覆盖的前提下，尽量简化网络结构，减少能量消耗。尽管网络已经简化，节点的能耗速度仍然不同。例如，由于所有节点采集的数据都向Sink节点汇集，那么距离Sink节点较近的普通节点自然承担着更重的数据流量，能耗速度自然更快。拓扑维护的作用就是在原有的拓扑结构即将遭到破坏时(由于某些节点能量的即将耗尽)转变成一种新的拓扑结构，以缓解任务较重的节点，达到网络负载均衡的目的。正是由于最小连通支配集的不唯一性，为拓扑构造和拓扑维护的交替运作提供了理论支持。

2.1 拓扑维护方式及其触发条件

拓扑维护可分为静态、动态和混合三种方式。为网络设定一定条件的阈值，静态拓扑维护是指在拓扑构造时预先维护不唯一的拓扑结构，当网络运行超过阈值时，根据预先维护的、可达到阈值条件的其他拓扑来替代当前拓扑；动态拓扑维护是指网络运行的任何时刻，一旦超过阈值，立即终止当前拓扑，重新构建拓扑结构；混合拓扑维护是指网络运行超过阈值时，先利用静态拓扑维护机制，如果预先维护的拓扑结构都不能替代当前拓扑，则调用动态拓扑维护机制来重建拓扑结构。

常见的触发拓扑维护的条件如下描述：

随机拓扑维护：设定一个随机数，拓扑维护随机进行。这种方法可能会给网络运行带来较大不确定性。

基于失效节点的拓扑维护：当网络中失效节点达到一定数量时进行拓扑重构。此方法并没有尽量避免节点的能量耗尽，在稀疏性网络中可能导致覆盖率的急剧下降。

基于节点密度的拓扑维护：当网络平均节点度达到一定阈值时进行拓扑重构。节点度描述的是节点邻居的个数，平均节点度是指所有节点度之和与节点数之比。由于节点度本身需要一定的计算量，此方法可能产生较大的额外开销。

基于时间阈值的拓扑维护：可以在全网节点定义一个时间阈值，当网络运行到阈值时间时，即刻进行拓扑重构。此方法的关键在于阈值大小的确定，若阈值过小，拓扑重构的次数就会过多，给网络带来额外的开销；若阈值过大，可能导致在拓扑重构时死亡节点过多，影响覆盖率。

基于能量阈值的拓扑维护：对网络节点能量设定一个阈值，网络能量低于此阈值时进行拓扑重构。此方法的特点与基于时间阈值的拓扑维护类似。

2.2 基于介数缓冲的动态能量均衡拓扑维护

由于静态拓扑维护会给网络带来额外开销，本文将采用动态拓扑维护机制。节点能量的均衡利用是无线传感器网络最重要的目标，所以本文采用能量阈值作为拓扑重构的触发条件。将能量阈值设定为单个节点的10%，即当某个活动节点的剩余能量低于其初始能量的10%时，重新调用拓扑构造算法。另外，本文还特别关注无线传感器网络中的那些注定要消耗更多能量的重要节点。如前所述的距离Sink节点较近的普通节点，由于其位置的重要性，无论怎么重新构造拓扑结构，这类节点始终需要包含在活动节点之中，始终要最先耗尽能量。本文将这种重要节点抽象成介数中心性重要节点，并对之进行数据缓冲处理，以延长此类节点的寿命，从而进一步增加网络生命周期。

用经过某节点的最短路径数目来刻画此节点重要性的指标叫做介数中心性(Betweenness Centrality, BC)[13]。无线传感器网络节点i的介数定义为：

(1)

在不考虑节点计算能耗的条件下，网络节点能耗主要包含三大部分：发送信息产生的能耗、接收信息产生的能耗和感知信息产生的能耗。由于网络中所有节点均需要感知信息并发送出去，且能耗一致，所以介数中心性重要节点和普通节点的能耗区别在于接收来自其他节点的信息并发送出去(转发)的次数。减少介数中心性重要节点对信息转发的次数，是网络能量均衡的有效办法。一种方案是移动另一节点到重要节点处作为支援节点；另一种方案是重要节点的邻居节点将信息暂存在缓冲区中进行聚集，缓冲区满后再转发给重要节点。对于部署在特殊环境下的无线传感器网络而言，节点的移动往往较为困难，第二种方案是可行的。

若某节点的介数值大于网络平均介数值，即可判定自身为重要节点，并可将此信息发送给邻居节点。当邻居节点需要发送信息给重要节点时，会采用缓冲并聚集的方法来减少重要节点的转发次数，本文将节点缓冲区大小设置为数据包长的5倍。此方案在牺牲较少数据传输延时的情况下，延长了网络生命周期。

3 狭长域无线传感器网络模型

目前我国对诸如矿井和轨道内基础设施的检查仍然主要采用检查车和人工巡查的方式，这种传统方式在数据的准确性、广泛性、实时性和节能等方面都存在较大缺陷[14]。虽然当前对桥梁、岔口等特定区域做了重点监测，但尚无面向整个网络的监测。利用无线传感器网络对基础设施进行监测，是解决当前问题的最佳解决方案。

在狭长区域部署的无线传感器网络除了要监测静止的基础设施之外，还要监测区域内的穿过物。物体沿任何路径穿过该区域时，都能够被至少一个节点探测到的网络覆盖方式被称为栅栏覆盖[15-16]。显然对于同质网络而言，为了保证栅栏覆盖，网络中节点数N必须满足式(2)所示的条件。其中L为目标区域长度，rs为节点感知半径。

(2)

对于连通性而言，文献[17]已经证明，当传输半径rc≥rs，且目标区域被节点全覆盖，就能保证网络全连通。

本文采用的网络模型为：

1)狭长域无线传感器网络由N个同质节点和1个Sink节点构成，且Sink节点位于域的中心位置。普通节点具有一定的初始能量，在数据采集、计算、传输和转发过程中均有能量消耗，Sink节点无能量限制；

2)被监测区域为长度远大于宽度的狭长带状区域；

3)节点在被监测区域为随机布局，且保证栏栅覆盖和全连通。节点一旦撒下，其位置固定，不可移动。节点发送1bit数据所消耗的能量为：ETxbit=Eelect+Eamp·(π·r2)；接收1 bit数据所消耗的能量为：ERxbit=Eelect。其中r为节点通信半径，Eamp为发送放大器的消耗能量；

4)节点在网络中的编号各不相同，节点之间的传输链路无向，且可根据接收信号的强弱来判断信息发送者的远近。

4 仿真分析

将基于介数缓冲的动态能量均衡拓扑维护机制分别融入到A3、A3 Cov、EECDS和CDS Rule K等拓扑构造算法之中(分别命名为：BC-Based A3、BC-Based A3 Cov、BC-Based EECDS和BC-Based CDS Rule K)，在1 000 m×100 m狭长带状区域内随机部署200个节点(节点分布情况如图1所示)，对算法进行了仿真和对比分析。仿真基于Java平台，仿

真得到的数据在Matlab中进行处理分析。具体仿真参数设置如表1所示。

表1 仿真参数设置

图1 节点分布图
Fig.1 Node distribution

本文将生命周期定义为从无线传感器网络运行开始至与Sink节点存在连接的节点完全死亡为止。以时间为横坐标，与Sink存在连接的活动节点数目为纵坐标，对比各个协议的生命周期情况如图2-图5所示。可以看出，在没有添加基于介数缓冲的动态能量均衡拓扑维护机制时，A3、A3 Cov、EECDS和CDS Rule K都存在活动节点数量阶跃式下降的情况。向经典协议添加新机制之后，活动节点数的下降趋势得到了明显的缓冲，证明新机制下的拓扑控制协议使网络能量得到了很好的均衡控制，整个网络的生命周期得到了明显的改善。

5 结论

本文提出了狭长域无线传感器网络动态能量均衡控制方法，该方法将节点动态能量均衡的方法融入到经典算法之中，采用能量阈值作为拓扑重构的触发条件，当某个活动节点的剩余能量低于其初始能量的10%时，重新调用拓扑构造算法。另外，本文还分析了介数中心性节点对网络性能的影响，对介数中心性重要节点进行了缓冲管理。在狭长形状区域内布置随机网络，对基于介数缓冲的动态能量均衡拓扑控制算法进行了仿真分析。结果表明，向经典协议添加新机制之后，活动节点数的下降趋势得到了明显的缓冲，证明新机制下的拓扑控制协议使网络性能得到了明显的改善。

[1]Yick J, Mukherjee B, Ghosal D. Wireless sensor network survey [J]. Computer Networks the International Journal of Computer & Telecommunications Networking, 2008, 52(12):2292-2330.

[2]Chen CP, Mukhopadhyay SC, Chuang CL, et al. Efficient coverage and connectivity preservation with load balance for wireless sensor networks[J]. Sensors Journal IEEE, 2015, 15(1):48-62.

[3]Wang H, Huang Y, Roman HE. Some fundamental results on complex network problem for large-scale wireless sensor networks[J]. Wireless Personal Communications, 2014, 77(77):1-17.

[4]Jelicic V, Magno M, Brunelli D, et al. Benefits of wake-up radio in energy-efficient multimodal surveillance wireless sensor network[J]. IEEE Sensors Journal, 2014, 14(9):3210-3220.

[5]Liu X, Cao J, Tang S, et al. Enabling reliable and network-wide wakeup in wireless sensor networks[J]. IEEE Transactions on Wireless Communications, 2015, 4490(1):1-1.

[6]Chen H, Li X, Zhao F. A reinforcement learning-rased sleep scheduling algorithm for desired area coverage in solar-powered wireless sensor networks[J]. IEEE Sensors Journal, 2016, 16(8):2763-2774.

[7]Gorain B, Mandal PS. Line sweep coverage in wireless sensor networks[C]//Sixth International Conference on Communication Systems & Networks, 2014:1-6.

[8]Wightman PM, Labrador MA. A3: A topology construction algorithm for wireless sensor networks[J]. IEEE Globecom IEEE Global Telecommunications Conference, 2008, 48(4):1-6.

[9]Wightman PM, Labrador MA. A3Cov: A new topology construction protocol for connected area coverage in WSN[J]. IEEE Wireless Communications and Networking Conference, 2011, 34(17):522-527.

[10]Zeng Y Y, Xiao H J, He Y X. Energy efficient distributed connected dominating sets construction in wireless sensor networks [C]//International Conference on Wireless Communications & Mobile Computing, 2006:797-802.

[11]Wu J, Cardei M, Dai F, et al. Extended dominating set and its applications in ad hoc networks using cooperative communication[J]. IEEE Transactions on Parallel & Distributed Systems, 2006, 17(8):851-864.

[12]Wightman PM, Labrador MA. Topology maintenance: Extending the lifetime of wireless sensor networks[J]. Latin America Transactions IEEE, 2010, 8(4):469-475.

[13]汪小帆, 李翔, 陈关荣. 网络科学导论[M]. 北京：高等教育出版社, 2012: 159-161.

[14]霍宏伟, 郜帅, 牛延超, 等. 一种实时轨道监测无线传感器网络与服务模型研究[J]. 铁道学报, 2008, 30(6):51-57.

[15]He SB, Chen JM, Li X, et al. Mobility and intruder prior information improving the barrier coverage of sparse sensor networks[J]. IEEE Transactions on Mobile Computing, 2014, 13(6): 1268-1282.

[16]Tao D, Wu TY. A survey on barrier coverage problem in directional sensor networks[J]. IEEE Sensors Journal, 2015, 15(2): 876-885.

[17]付俊松, 张振江, 刘云. 一种轨道交通新型无线传感器网络能量有效覆盖算法RTST的研究与仿真[J]. 铁道学报, 2014(01):49-55.

TopologyControlforWirelessSensorNetworksBasedonDynamicEnergyBalanceinNarrowRegion

LIU Yan, GENG Peng, YANG Jie

(Nanjing Institute of Technology, Nanjing 211167, China)

The wireless sensor networks topology construction algorithm based on connected dominating set has the problem of energy imbalance in the application of narrow region environment. We proposed a dynamic energy balance control method for narrow region wireless sensor networks. The topology construction algorithms such as A3, A3 CoV, EECDS and CDs rule K were analyzed. We integrated the dynamic energy balance of nodes into these algorithms and the buffer management was used in the betweenness centrality important nodes. The dynamic energy balance topology control algorithm based on the betweenness buffer management was simulated and analyzed in the orbit shape region. The simulation results showed that the new algorithm could make full use of node energy, prolong the network lifetime, and improve the overall performance of the wireless sensor networks.

wireless sensor networks; narrow region; energy balance; betweenness centrality

2017-04-10

南京工程学院校级科研基金项目资助(QKJA201509)；江苏省自然科学基金项目资助(BK20160781)；江苏省高校自然科学研究基金项目资助(16KJB510013)

柳艳(1980—)，女，江苏高邮人，讲师，研究方向：应用数学，无线传感器网络，复杂网络。E-mail：huayiliu2000@126.com。

TP393

A

1008-1194(2017)05-0076-05