传感器中基于连通支配集的区域覆盖控制算法

黄恒杰，龚小龙，王高才

(1.玉林师范学院教育技术中心，广西玉林537000；2.广西大学计算机与电子信息学院，广西南宁530004)

传感器中基于连通支配集的区域覆盖控制算法

黄恒杰1，龚小龙2，王高才2

(1.玉林师范学院教育技术中心，广西玉林537000；2.广西大学计算机与电子信息学院，广西南宁530004)

针对现有无线传感器网络区域覆盖控制算法很难在确保网络连通率的同时对网络覆盖率和能耗进行优化的问题，本文提出一种基于连通支配集的区域覆盖控制(area coverage control based on connected dominating set，ACCBCDS)算法。当节点随机分布于监测区域后，未连通的节点移向Sink节点直至网络实现全连通，之后利用三着色算法构建网络连通支配集，Sink节点对非连通支配节点进行集中式优化调整，让非连通支配节点移至更优位置。在优化调整的过程中同时考虑了网络连通率、覆盖率和节点移动距离。仿真结果表明，与典型的基于虚拟力的区域覆盖控制(area coverage control based on virtual forces，ACCBVF)算法相比较，本文提出的ACCBCDS算法能使网络在确保全连通的前提下获得更高覆盖率，并能减少网络覆盖控制中的移动能耗。

传感器网络；连通支配集；覆盖率；能耗

0 引言

无线传感器网络覆盖控制是指在考虑网络存储、计算、通信和能量等资源受限的情况下，通过调整节点位置、网络路由和节点状态等手段，使各受限资源得到优化配置，进而使网络感知、通信和生存周期等服务质量得到改善[1-3]。根据覆盖对象的不同，现有无线传感器网络覆盖控制方法可分为区域覆盖、点覆盖、栅栏覆盖3类。

点覆盖是指对监测区域中某些重要的目标点进行覆盖，该问题已被广泛研究[4-7]。点覆盖通过单个活动节点监控覆盖区域，其他节点睡眠，从而有效延长整个网络生存时间。如何构造最大数量的无交节点集是一个NP完全问题。栅栏覆盖是研究运动物体通过监测区域时被监测到的概率问题。目前，针对栅栏覆盖已取得一定成果[8-10]。栅栏覆盖的意义在于：一方面可以确定最佳网络部署，使得目标检测概率最大；另一方面，当穿越有危险的监控区域时，可以选择一条最安全的路径。

区域覆盖要求监测区域中的每个点至少被一个节点覆盖，这是覆盖控制中研究最多的一类。Huang等研究了正方形监测区域的网络覆盖率与节点感知半径、监测区域边长等参数之间的数学关系，提出可用于网络初始部署阶段控制覆盖率[11]，该算法对于全局部署效果不好。Zhang等研究了对于按照泊松分布方式进行随机初始部署的无线传感器网络，如何实现目标区域的K覆盖问题[12]，该算法需要根据网络状况手工设定大量参数，同时只能保证节点通信距离大于或等于两倍感知距离时的网络连通性。Dhillon等针对二维平面的区域覆盖问题，提出利用正方形网格对目标区域进行划分，借助最大化平均覆盖部署算法(max average coverage deployment，MACD)[13]，但是该算法会消耗过多的节点能耗。文献[14]提出一种在构建连通支配集的基础上调整连通支配集的中间节点状态进行节点优化控制的算法。该算法能够在确保网络全连通的前提下提高网络覆盖率，然而其集中式优化过程中未考虑节点移动距离，使得节点移动能耗仍存在优化空间，该方法没有考虑能耗优化问题。Zou等针对二维空间中移动无线传感器网络覆盖控制问题，提出一种基于虚拟力的覆盖控制(area coverage control based on virtual forces, ACCBVF)算法[15]。作为典型的移动无线传感器网络区域覆盖控制算法，该算法利用节点引力避免节点相互之间出现过大距离，从而能确保网络连通率；利用节点斥力避免节点相互之间出现过小距离(这会带来较大覆盖重叠)，从而能确保网络覆盖率。然而，经过科学分析及必要仿真可知，该算法存在以下不足之处：如无法实现网络的全连通，网络覆盖率可进一步优化以及过多的网络移动能耗。

由于现有的无线传感器网络区域覆盖控制算法很难在确保网络全连通的同时对网络覆盖率和能耗进行优化，本文提出一种基于连通支配集的区域覆盖控制(area coverage control based on connected dominating set, ACCBCDS)算法。当移动传感器网络以随机方式在监测区域完成初始部署后，未连通节点自主移向Sink节点直至网络实现全连通，并通过三着色算法构建网络连通支配集。之后Sink节点进行集中式优化计算，对非连通支配节点位置进行优化调整。仿真结果表明，所提出的ACCBCDS算法能使网络在确保全连通的前提下实现较高网络覆盖率，并减少网络覆盖过程中的移动能耗。

1 问题定义及算法描述

1.1 问题定义

当利用移动无线传感器网络对某些场合(如灾害救助、军事监控等)进行区域覆盖时，要求系统除了对监测区域具有较高网络覆盖率之外，还必须具有很强的实时监测性能，所有移动节点最好能和Sink节点始终保持通信(即网络应一直保持全连通)。由于移动无线传感器网络亦具有显著的能量有效性，为了延长网络生存周期，系统在覆盖过程中应尽量减少网络能耗。因此，针对该类场合的移动无线传感器网络区域覆盖控制问题，是指在充分考虑网络要求和特点的前提下，对初始随机部署于监测区域的节点进行位置调整，以实现较高网络覆盖率，并尽量减少网络在调整过程中的能耗。

本文对传感器网络节点做如下合理的假设：(1)所有传感器节点同构，具有相同的感知半径Rs和通信半径Rc，并各自具有唯一的ID号；(2)传感器节点初始时随机部署于二维监测区域，之后可自由移动。为了研究简便，Sink节点可认为一直固定于二维监测区域中心；(3)传感器节点均能借助相关定位装置或算法确定自身实时位置；(4)Sink节点位置信息(即二维监测区域中心的位置信息)在部署前已写入其他各传感器节点内存中。Sink节点内存中则写入二维监测区域的坐标信息和传感器节点的数目信息。

下面首先对ACCBCDS算法中如何利用三着色方法构建网络连通支配集和Sink节点对非连通支配节点进行的集中式优化调整进行详细描述，然后概述算法整体实现过程。

1.2 算法描述

1.2.1三着色算法构建网络连通支配集

三着色算法构建网络连通支配集的流程图如图1所示。将网络中所有节点分为3个不同状态，并用白色、灰色和黑色3个不同颜色表示。未被使用的节点表示为白色，非骨干节点表示为灰色，骨干节点表示为黑色。在构建连通支配节点之前，所有节点初始状态都认为是未被使用，并用白色表示。选取Sink节点作为起始点标记为黑色，当所有节点均被标记为灰色或黑色时，算法结束。

三着色算法的具体实现过程如下：

①将所有节点均初始化为未被使用状态，并用白色表示。选取Sink节点作为起始点，将该点状态标记为骨干节点，并用黑色表示，之后该黑色起始点广播查询信息Mf。

②若白色节点s1收到来自黑色节点s2的查询信息Mf，则将自身标记为灰色节点，并根据自身与黑色节点s2的距离d(s1,s2)计算等待时间Tw1，Tw1与距离d(s1,s2)成反比。当等待时间结束后，节点s1广播查询信息。

图1 三着色算法构建网络连通支配集的流程图Fig.1 The flow chart of three coloring methods to construct a network connected dominating set

③若白色节点s1收到来自灰色节点s2的查询信息Mf，则根据自身与灰色节点s2的距离d(s1,s2)计算等待时间Tw2，Tw2与距离d(s1,s2)成反比。若在等待时间内，节点s1收到来自黑色节点的查询信息，则将自身标为灰色节点；否则将自身标记为黑色节点。

④若黑色节点或灰色节点收到查询信息，则忽略所有查询信息。

⑤重复上述步骤，当网络中所有节点的颜色均被标记为黑色或者灰色时停止对节点进行颜色标记。此时，网络中黑色节点组成的集合即为连通支配集。

1.2.2非连通支配节点的优化调整

当未连通节点移向Sink节点使网络实现全连通且通过三着色算法确立网络连通支配集后，Sink节点可对非连通支配节点位置进行集中式优化调整，令非连通支配节点移至更优位置。该位置位于连通支配节点的通信半径范围内，且优化过程中同时考虑如何提高网络覆盖率和减少节点移动距离。具体步骤如下：

①Sink节点根据非连通支配节点剩余能量，按照由大到小顺序对其逐个研究，为其计算更优位置。

②设二维平面区域中与网络连通支配节点不超过节点通信半径Rc的探测点集合为C1，对于某非连通支配节点si，可将其调度至C1中的某个点pd(si)，以此实现在确保全连通的前提下提高网络覆盖率。

③同时，应尽量减少节点移动距离，以减少网络移动能耗。因此，可按式(1)为节点s1在C1中寻找目标位置pd(si)：

(1)

其中，oi表示节点si在被Sink节点调度前的旧位置，Cv(oi)表示节点si在被Sink节点调度前的网络覆盖率，Cv(pi)则表示假定节点si到达探测点pi时的网络覆盖率。

1.2.3 ACCBCDS算法整体步骤

前面已经详述了ACCBCDS算法的2个主要部分，即网络连通支配集的构建和非连通支配节点的优化调整，接下来描述该算法的整体实现步骤：

①有传感器节点初始随机分布于监测区域，之后Sink节点固定于二维监测区域中心，以接收来自各个传感器节点所采集的数据信息。

②Sink节点广播就绪信息Mr，收到该就绪信息的节点对就绪信息做进一步转发，并将自身位置信息告知Sink节点；未收到就绪信息的节点则沿直线移至Sink节点，并在移动过程中保持对就绪信息的侦听，直至收到就绪信息，之后将自身位置信息告知Sink节点。

③若所有节点均收到就绪信息，则Sink节点所接收的位置信息数目应等于节点数目。Sink节点可根据位置信息数目与节点数目是否相等确定网络是否实现全连通，若二者不相等，表明网络未全连通，Sink节点应一直等待；若二者相等，则表示网络已实现全连通，转第④步。

④Sink节点确定网络连通支配集。

⑤Sink节点对网络中的非连通支配节点位置进行优化调整。

⑥算法结束。

2 仿真算例与分析

ACCBVF算法是典型移动无线传感器网络区域覆盖控制算法之一。为了合理评价ACCBCDS算法的性能，选择ACCBVF算法作为对比算法，以网络连通率、覆盖率和覆盖控制中的移动能耗作为算法性能评价指标，对ACCBCDS算法和ACCBVF算法进行对比仿真及分析。

2.1 仿真场景和参数

利用Matlab进行仿真，为消除实验随机性影响，最终结果取50次实验的平均值。模拟的二维监测区域为200 m×200 m的正方形平面，网格分辨率w=1 m。为尽量提高ACCBVF算法的网络覆盖率和连通率，其运行轮数设为30。ACCBVF算法和ACCBCDS算法的其余主要参数设置如表1所示。

表1 仿真参数表

2.2 仿真结果与分析

ACCBVF算法和ACCBCDS算法的网络连通率对比图如图2所示，其中图2(a)对应的仿真场景为节点数目变化，通信半径固定为30 m，图2(b)对应的仿真场景为节点通信半径变化，节点数目固定为40个。可以看出，与ACCBVF算法相比，ACCBCDS算法始终能确保部署结束后网络达到全连通(即连通率为1)。由于ACCBVF算法中能够对网络连通率起提高作用的是节点引力，而节点的移动由其所受的虚拟力合力决定，因此节点引力并不能完全控制节点的移动，造成网络无法达到全连通。而对于ACCBCDS算法，未连通的节点自主移向Sink节点直至网络达到全连通，且Sink节点确定连通支配集后，在确保非连通支配节点处于连通支配节点通信半径范围内的前提下，对非连通支配节点位置进行优化调整，因此调整结束后网络仍保持全连通。

图2 网络连通率对比图Fig.2 The comparisons of network connectivity

ACCBVF算法和ACCBCDS算法的网络覆盖率对比图如图3所示，仿真场景为节点数目变化，通信半径固定为30 m。可以看出，与ACCBVF算法相比，在相同的网络节点数目下，ACCBCDS算法能使网络获得更高覆盖率。对于ACCBVF算法，节点移动由局部范围内所受的虚拟力合力决定，此移动只能从局部角度对覆盖率起一定提高作用。而对于ACCBCDS算法，Sink节点在确定网络连通支配集后，从全局角度对非连通支配节点位置进行优化调整，因此该移动能带来更大的覆盖率提高。

图3 网络覆盖率对比图Fig.3 The comparisons of networkcoverage ratio

图4 节点总移动能耗对比图Fig.4 The comparisons of the totalenergy consumption of node

ACCBVF算法和ACCBCDS算法的节点总移动能耗对比图如图4所示，由图可知，相比于ACCBVF算法，ACCBCDS算法的节点总移动能耗更小。对于ACCBVF算法，在其运行的每一轮中所有节点都要根据所受的虚拟力合力进行移动，故其总移动距离和总移动能耗较大。而对于ACCBCDS算法，所有节点在监测区域完成初始随机分布后，只有少量未连通节点移向Sink节点，且当网络达到全连通后，Sink节点只对部分非连通支配节点的位置进行优化调整，因此总移动距离和总移动能耗较小。

总的来说，相比于ACCBVF算法，本文提出的ACCBCDS算法的优点在于：

(1)该算法要求未连通的节点移向Sink节点直至网络实现全连通，之后仅对非连通支配节点位置进行优化调整，且调整后的位置仍位于连通支配节点的通信半径范围内，因此网络的全连通性能够一直保持。

(2)该算法对非连通支配节点的位置优化通过Sink节点进行集中式计算完成，由于Sink节点能够获取网络全局信息，因而这样的集中式优化调整能使网络获得更大覆盖率提升。

(3)Sink节点在对非连通支配节点位置进行集中式优化调整时，不仅考虑了如何增加网络覆盖率，而且考虑了如何减少节点移动距离，因此能够减少网络移动能耗。

3 结束语

无线传感器网络区域覆盖控制就是在确保网络尽可能连通时对网络覆盖率和能耗进行优化。本文提出一种基于连通支配集的区域覆盖控制ACCBCDS算法。该算法通过对非连通支配节点位置进行优化调整，持续保持网络的全连通性和极大提高网络的覆盖率。同时通过减少节点移动距离来减少网络移动能耗，从而有效地延长了网络生存周期。仿真结果表明了ACCBCDS算法在各性能指标上的优势。为了促使研究成果尽量应用至实际场景，应对节点感知、节点移动能耗建立更加符合实际情况的模型是下一步需要开展的研究工作。

[1] 岳才杰, 陈元琰, 朱新华. 一种有效的传感器网络区域查询算法[J].广西师范大学学报(自然科学版)，2015,33(1):52-58.

[2] ABOUELKHAIR O, ELSAADNY A. Multipath adaptive periodic threshold-sensitive energy efficient protocol for wireless sensor networks[C]//Proceedings of the 6th IEEE International Conference on Computational Intelligence, Communication Systems and Networks. New York:IEEE Press, 2015: 33-37.

[3] JIANG P, LIU J, WU F, et al. Node deployment algorithm for underwater sensor networks based on connected dominating set[J]. Sensors, 2016, 16(3):388. DOI:10.3390/s16030388.

[4] CARDEI M, DU D Z. Improving wireless sensor network lifetime through power aware organization[J]. Wireless Networks, 2005, 11(3): 333-340.

[5] SEN A, DAS N, MURTHY S. Coverage and connected coverage problems for sensors embedded in a temperature-sensitive environment[J]. International Journal of Sensor Networks, 2010, 7(2): 106-123.

[6] 林祝亮, 冯远静, 俞立. 无线传感网络覆盖的粒子进化优化策略研究[J]. 传感技术学报, 2009, 22(6): 873-877.

[7] JIANG P, LIU J, WU F. Node non-uniform deployment based on clustering algorithm for underwater sensor networks[J]. 2015, 15(12): 29997-30010.

[8] MEGUERDICHIAN S, KOUSHANFAR F, POTKONJAK M, et al. Coverage problems in wireless ad-hoc sensor networks[C]// Proceedings of the IEEE Conference on INFOCOM. New York: IEEE Press, 2001:1380-1387.

[9] SANTOSH K, TEN H, ANISH A. Barrier coverage with wireless sensors[J]. Wireless Networks, 2007, 13(6): 817-834.

[10] LIU B Y, DOUSSE O, WANG J, et al. Strong barrier coverage of wireless sensor networks[C]// Proceedings of the ACM International Symposium on Mobile Ad Hoc Networking and Computing. New York: ACM Press, 2010: 411-419.

[11] HUANG C F, TSENG Y C, LO L C. The coverage problem in three-dimensional wireless sensor networks[J]. Journal of Interconnection Networks, 2011, 8(3): 3182-3186.

[12] ZHANG H, HOU J. On deriving the upper bound of α-lifetime for large sensor networks[J]. ACM Transactions on Sensor Networks, 2005, 1(2): 272-300.

[13] DHILLON S S, CHAKRABARTY K. Sensor placement for effective coverage and surveillance in distributed sensor networks[C]// Proceedings of the Wireless Communications and Networking. New York: IEEE Press, 2003: 1609-1614.

[14] 李海坡,马向南. 无线传感器网络中基于连通支配集的覆盖控制算法[C]// 中国通信学会第六届学术年会论文集(下).北京：北京邮电大学出版社,2009：658-661.

[15] ZOU Y, CHAKRABARTY K. Sensor deployment and target localization based on virtual forces[C]// Proceedings of the 22th Annual Joint Conference of Computer and Communications. New York： IEEE Press， 2003: 1293-1303.

(实习编辑 李 朝)

(责任编辑 马殷华)

An Area Coverage Control Algorithm Based on ConnectedDominating Set for Sensor Networks

HUANG Hengjie1, GONG Xiaolong2, WANG Gaocai2

(1. Educational Technology Center,Yulin Normal University,Yulin Guangxi 537000,China;2. School of Computer, Electronics and Information, Guangxi University, Nanning Guangxi 530004, China)

To solve the problem that existing area coverage control algorithms for the mobile WSNs are difficult to ensure the network connectivity rate of the network coverage and energy consumption optimization, an area coverage control algorithm based on connected dominating set (ACCBCDS) algorithm is proposed for the mobile WSNs. When the nodes are randomly distributed in the monitoring area, nodes disconnected to the Sink node are required to move toward the Sink node until full network connectivity is achieved. Then the three-staining method is adopted to construct the network connected dominating set, after which the Sink node performs centralized optimization adjustment on dominated nodes, requiring dominated nodes to move toward better locations. During the adjustment, network coverage rate, connectivity rate and node movement distance are synthetically considered. Simulation results show that compared with typical area coverage control algorithm based on virtual forces (ACCBVF) algorithm, the proposed ACCBCDS can achieve higher network coverage rate under the premise of ensuring full network connectivity, and decrease node movement energy consumption during network coverage control.

sensors networks; connected dominating set; coverage rate; energy consumption

10.16088/j.issn.1001-6600.2016.04.003

2016-06-18

广西高等学校优秀中青年骨干教师培养工程资助项目；国家自然科学基金资助项目(61562006，61262003)；广西自然科学杰出青年基金资助项目(2013GXNSFGA019006)

王高才(1976—)，男，广西灌阳人，广西大学教授，博士，博士生导师。 E-mail：wanggcgx@163.com

TP393

A

1001-6600(2016)04-0019-07