1-WSN关键区域覆盖启发式优化算法

计算机工程第 35 卷第14期

Vol.35 No.14 Computer Engineering ·博士论文·

文章编号：1000—3428(2009)14—0016—04

文献标识码：A

2009年7月

July 2009

中图分类号：TP302

WSN 关键区域覆盖启发式优化算法

张晋1，刘大昕1，徐悦竹1，廉盟2

(1. 哈尔滨工程大学计算机科学与技术学院，哈尔滨 150001；2. 中国移动通信集团黑龙江分公司，哈尔滨 150001)

摘要：针对无线传感器网络关键区域覆盖NP 完全问题，提出一种关键区域覆盖启发式优化(CACHO)算法。该算法基于单位圆通信模型对关键区域覆盖问题进行描述，为关键区域格点与一般区域格点分配不同权值，以创建感知区域图和终端集合，形成具有最少数量的关键区域覆盖格点集合。与现有覆盖算法NPCC 的比较结果表明，CACHO 算法放置的传感器数量较少，能完全覆盖关键区域。关键词：无线传感器网络；关键区域；覆盖；启发式算法

Critical Area Coverage Heuristic Optimization Algorithm in WSN

ZHANG Jin1, LIU Da-xin1, XU Yue-zhu1, LIAN Meng2

(1. College of Computer Science and Technology, Harbin Engineering University, Harbin 150001;

2. Heilongjiang Filiale of China Mobile Communication Co. Ltd, Harbin 150001)

【Abstract 】Aiming at the critical areas coverage NP-complete problem in Wireless Sensor Networks(WSN), this paper proposes a Critical AreasCoverage Heuristic Optimization(CACHO) algorithm. Based on unit disk graph communication model, this algorithm describes the problem ofcritical areas coverage, and assigns different weight for critical grid points and common grid points to create graph of sensing filed and terminal setand form critical areas coverage grids set with minimal number. Comparison results with an existed coverage algorithm named NPCCprove thatCACHO algorithm deploys fewer sensors and can fully cover critical areas.

【Key words】Wireless Sensor Networks(WSN); critical area; coverage; heuristic algorithm

1 概述

近年来，随着微机电系统、无线通信、信息网络与集成

电路等技术的迅速发展，出现了无线传感器网络(Wireless Sensor Networks, WSN)[1]。WSN 利用大量具有数据采集、处理和无线通信功能的微型智能节点，在网络覆盖区域内协作完成复杂的监测任务。WSN 网络覆盖优化能有效提高测量可靠度与精度，已成为研究热点之一[1]。以环境感知、目标监测、信息获取和有效传输为主要目标的WSN 需要关心对传感区域或监测目标的覆盖能力，WSN 覆盖控制问题随之产生。网络对目标区域或目标点的覆盖程度是衡量一个WSN 覆盖控制算法优劣的首要标准。已有一些学者开展了WSN 优化覆盖控制方面的研究，并取得了一定进展。文献[2]对WSN 中的目标覆盖定位问题进行研究，提出一种在有限代价条件下最小化最大错误距离的组合优化配置方法。文献[3]研究WSN 中传感器节点移动条件下的覆盖问题，充分考虑了战场等实际应用场景中可能需要节点或网络具有移动性支持的特征。文献[4]从更实际的应用场景出发，研究有遮挡环境下的分布式WSN 中的覆盖问题，分析遮挡造成的感知覆盖范围的性能。很多研究者对覆盖增强问题进行了研究[5]，且研究热点正逐步向实用化、实际的应用场景方向发展，但在很多实际应用中，尤其是对监控范围较广的场景，应区分关键区域与一般区域，以实现有效覆盖。上述区分是一种更实际且有效的方法。而WSN 中的关键区域覆盖问题为NP 完全问题[6]，现有覆盖算法没有针对该问题提出有效的解决方法。

本文针对WSN 中的关键区域覆盖问题，提出一种关键区域覆盖启发式优化算法(Critical Areas Coverage Heuristic Optimization, CACHO)。该算法以迭代合并方式创建加权节 —16—

点Steiner 树，形成具有最少数量的格点集合，并以该集合中

优化的格点位置构建覆盖关键区域网络的传感器放置方法。

2 关键区域覆盖启发式优化算法

2.1 问题描述

以单位圆模型为通信模型，当一个传感器位于另一个传感器的发送范围R t 内时，可以向该传感器发送消息。一个传感器检测到事件的概率服从二进制传感模型，即如果该事件位于传感器的感知范围内，则检测到该事件的概率为1，否则检测到该事件的概率为0。对于感知区域F ，将其划分为长度为l 的方格，被置于方格中心的传感器称为格点。感知区域F 中必须全覆盖的所有方格称为关键区域C ，C 表示所有必须全覆盖的方格的集合。假设当R s 且R t =l 时，

每个放置在格点的传感器可以覆盖该方格区域，并能与邻居格点进行通信。关键区域覆盖问题表示如下：

已知R s , R t , F ,

C 和一个正整数m ，求解是否存在一种以不大于m 的传感器数的放置方法实现感知区域F 中关键区域的全覆盖。

如图1(a)所示，F ={(i , j ) |i ∈[1,3],j ∈[1,3]}, C ={(1,1),

(2,3),(3,2)}, R s =

, R t 。容易证明，此时可以由基金项目：国家自然科学基金资助项目(40746029)

作者简介：张晋(1981－) ，女，博士研究生，主研方向：无线传感器网络；刘大昕，教授、博士生导师；徐悦竹，讲师、博士研究生；廉盟，工程师、硕士

收稿日期：2009-02-21 E-mail ：[email protected]

2个分别放置在(1, 1)和(2, 2)位置的传感器形成关键区域全覆盖的网络，如图1(b)所示。

(6)形成格点集合GS 和格点放置方法。如果v x , y 在树T 中，则格点集合GS 包含格点(x , y ) 。

定理1 由COCOA 算法创建的格点集合GS ，在格点集合GS 中的位置放置传感器能完全覆盖关键区域并形成一个有效的WSN 。

为了证明定理1，引入如下引理：

引理如果2个分别放置在格点位置(x , y ) , (z , w ) 的传感

(a)传感器网络格点示例 (b)关键区域覆盖示例

器都能全覆盖格点位置(i , j ) ，则节点v x , y 和v z , w 之间的距离满

⎡⎤

⎢R ⎥

足d (v x , y , v z , w ) ≤4⎢s ⎥。

⎢⎡t ⎤⎥

l ⎥⎥⎢⎢

⎢⎢t ⎥⎥

图1 关键区域覆盖示例

2.2 CACHO算法

CACHO 算法的具体实现步骤如下：输入 R s , R t , F , C

输出格点集合GS 和格点放置方法

(1)建立集合C 。用U 表示关键区域格点的集合，C i , j 表示放置在格点位置(i , j ) 覆盖的关键区域格点的集合，则C 表示C i , j 的集合。

(2)建立最小覆盖集合C ' 。根据文献[7]中的算法创建最小覆盖集。

(3)布置完全覆盖关键区域的传感器。根据步骤(2)获得的最小覆盖集合C ' ，对于C ' 中包含的所有C i , j ，在格点位置布置传感器。

(4)创建图G (V , E ) 和终端集合S 。用V 表示感知区域F 中所有格点(i , j ) 的节点v x , y 集合，终端集合S 包含最小覆盖集合C ' 中所有的格点v i , j 。如果2个分别放置在(i , j ) 和(x , y ) 位置的传感器能互相通信，则有边(v i , j , v x , y ) 。对于集合S 中的节点v i , j ，如果布置在格点(i , j ) ，则分配权值0，否则分配权值1。对于所有边，分配权值0。

(5)创建加权节点Steiner 树T [8]。基于步骤(4)得到的图G (V , E ) 和终端集合S ，创建Steiner 树T ，步骤如下：在初始情况下，3棵树T 1, T 2和T 3分别只包含终端节点t 1,2, t 2,3和

t 3,1。在第1次迭代中，每个节点计算其商耗散值，以节点v 2,2

证明：用N 1和N 2分别表示放置在格点(x , y ) , (z , w ) 的传感器。容易得到需要满足连接N 1和N 2的放置节点的数量不

⎡⎤⎡⎤

⎢|x −z |⎥⎢|y −w |⎥

⎥+⎢⎥。由于2个分别放置在格点(x , y ) , 大于⎢

⎢⎢R t ⎥⎥⎢⎢R t ⎥⎥

⎥l ⎥⎢⎢⎥l ⎥⎢⎢

⎢⎣l ⎦⎥⎢⎣l ⎦⎥(z , w ) 的传感器N 1和N 2都能全覆盖格点(i , j ) ，N 1和N 2的欧

式距离不大于2R s ，因此需要满足连接N 1和N 2的放置节点的

⎡⎤

⎢2R ⎥

s ⎥数量不大于2⎢。即在图G 的子图V 1所包含的图中，在⎢⎢R t ⎥⎥

⎥l ⎥⎢⎢

⎢⎣l ⎦⎥v x , y

⎡⎤⎢2R ⎥

s ⎥和v z , w 之间存在一条包含数量不大于2⎢个节点的⎢⎢R t ⎥⎥

⎥l ⎥⎢⎢

⎢⎣l ⎦⎥⎡⎤⎢R ⎥

d (v x , y , v z , w ) ≤4⎢s ⎥

⎢⎢R t ⎥⎥

⎥l ⎥⎢⎢

⎢⎣l ⎦⎥

路径。因此，节点v x , y 和v z , w 之间的距离满足

为例，该节点到3棵树的距离分别为10, 9和9。因此，对于

选择树T 2和T 1产生的商耗散值为(1+9+9) /2=9.5。节点v 2,2，

类似地，可以计算出节点t 3,1到树T 1, T 2和T 3的距离分别为0, 20, 20，因此，其商耗散值为(0+0+20) /2=10。容易证明节点v 2,2具有最小的商耗散值。因此，用节点v 2,2和树T 2之间的最短路径以及节点v 2,2和树T 3之间的最短路径，可以将树T 2和T 1可以合并为一棵树T 2+3。

在第2次迭代中，从节点t 1,2到树T 1和

T 2+3之间的距离分别为9和0，容易证明t 1,2具有最小商耗散值。因此，用节点t 1,2和T 1的最短路径以及t 1,2和T 2+3的最短路径，可以将树T 1和

T 2+3合并为一棵树。图2给出了创建加权节点Steiner 树T 的

证毕。

定理1证明如下：由于每个终端节点在CACHO 算法创建得到的Steiner 树T 中都是叶子节点，即格点集合GS 中的位置放置传感器节点必定是相连的，因此，能形成一个传感器网络。

考虑放置在格点(i , j ) 的关键区域，在图G 中存在一个终端节点t i , j ，由于t i , j 为加权节点Steiner 树T 创建过程中的节点，因此对于某一个非终端节点v x , y ，边(v x , y , t i , j ) ∈T ，即格点(x , y ) ∈GS ，且(v x , y , t i , j ) ∈G 。因此，放置在格点(x , y ) 的传感器完全覆盖了位于(i , j ) 关键区域格点，证毕。

对于图1(a)的示例，关键区域覆盖优化算法执行步骤如下： (1)因为将传感器放置在格点(1,1)可以完全覆盖关键区域格点(1,1)，所以C 1,1={(1,1)}。

(2)根据最小覆盖集创建算法可得C ' ={C 1,1, C 2,2}。 (3)根据最小覆盖C ' 集，在位置(1,1)(2,2)放置传感器。 (4)因为格点v 1,2∈V ，v 1,1∈C ' 且v 2,2∈C ' ，又v 1,1与v 2,2可以相互通信，所以边(v 1,1, v 1,2) ∈E 。因此，v 1,1与v 2,2的权值为

过程及其结果。

v 1,1(0)

v 1,2(1)

v 1,3(1)

v 2,1(1)

v 2,2(0)

v 2,3(1)

v 3,1(1)

v 3,2(1)

v 3,3(1)

0，v 1,2的权值为1。可以创建如图2所示的加权节点Steiner 树T 。

(5)由于T 中包含(v 1,1, v 2,2) ，因此GS ={(1,1),(2,2)}。即只

—17—

图2 加权节点Steiner 树的创建及其结果

要分别在(1,1)和(2,2)位置放置1个传感器，就可以形成关键区域全覆盖网络，如图1(b)所示。

2.3 算法时间复杂性

定理2 CACHO算法的时间复杂性为O (n 4) ，其中，n 为

有效减少了不必要的节点放置。而NPCC 算法并没有考虑这些因素，仅以增加传感器节点的数量实现网络的连通性。

140120平均传感器数

感知区域中格点的数量。

证明：

(1)在创建集合C 时，包含感知区域F 中位于位置(x , y ) 格点C x , y 。每个C x , y 需要至多O (n ) 的时间获得放置在格点

(i , j ) 位置并覆盖关键区域格点的集合。而创建集合C 的时间

[1**********]0

CACHO NPCC

7080关键区域格点数

100

消耗为O (n ) 。

(2)在建立最小覆盖集合C ' 的过程中，对于所有C x , y 格点，找到最大C x , y 消耗的时间为O (n ) ，而建立最小覆盖集合

C ' 的时间耗散为O (n ) 。

图3 关键区域格点数增加时的平均传感器数

图4

为感知范围从

时，CACHO 算法与

(3)在布置完全覆盖关键区域的传感器时，k 个关键区域格点的耗散时间为O (k ) 。

(4)在创建图G (V , E ) 和终端集合的步骤中，G (V , E ) 包含

n 个节点和至多n (n −1) /2条边。创建图G (V , E ) 所需的时间

NPCC 算法的平均传感器数。此时，发送范围R t 为5l ，选择分布概率p 为0，关键区域格点数固定为100。如图4所示，随着感知范围的增加，2种算法放置的平均传感器数量逐渐减少。无论感知范围为多少，CACHO 算法与NPCC 算法相比，其平均传感器数都少一些。且随着感知范围的增加，两者的差值始终保持在11左右。

140120平均传感器数

消耗至多为O (n 2) 。

(5)在建立加权节点树T 的过程中，每次迭代时，每个节点需要计算该节点到所有树的距离，其时间消耗至多为

O (n 3) 。由于在每次迭代中，至少有2棵树合成一棵新树，

因此最多需要k −1次迭代。所以，创建树T 需要的时间消耗为O (n 4) 。

(6)在形成GS 的过程中，至多需要时间O (n ) 消耗形成

GS 。

[1**********]0

2CACHO NPCC

因此，CACHO 实现复杂性为O (n 4) ，证毕。

3 仿真结果

仿真系统中将感知区域划分为长度为l 的50×50的方格。在该区域中以随机方式选择k 个关键区域格点。初始情况下，关键区域格点从所有格点中随机选择。在每次迭代中，如果产生的随机数大于等于关键区域格点选择分布概率p ，则从非关键区域格点中随机选择一个作为关键区域格点。否则，从与当前关键区域格点中至少有一个公共边的非关键区域格点中随机选取一个作为关键区域格点。实验中对关键区域格点数、感知范围、发送范围和关键区域格点选择分布概率变化时对放置传感器的数量进行研究，并取10次仿真结果的平均值。为了证明CACHO 算法的有效性，将CACHO 算法与NPCC [5]算法进行对比。

图3为关键区域格点数从50增加到100时，CACHO 算法与NPCC 算法的平均传感器数。此时，感知范围R

s 固定为

，发送范围R t 为5l ，选择分布概率p 为0。如图3所34感知范围

图4 感知范围增加时的平均传感器数

对于CACHO 算法，平均传感器数量减少明显，当感知

范围增加时从

增加到

时，平均传感器数量从109

减少到57。

对于NPCC 算法，平均传感器数量从最开始的120减少到69。其原因在于当感知范围增加时，CACHO 算法充分考虑了关键区域覆盖的连通性，通过增加的感知范围尽可能合理地分析关键区域格点间的位置与感知范围关系，减少节点放置数量，有效减少了节点放置数量。

图5为发送范围从l 增加到6l 时，CACHO 算法与NPCC 算法的平均传感器数。此时，感知范围R

s 固定为

，选择分布概率p 为0，关键区域格点数固定为100。如图5所示，随着发送范围的增加，2种算法放置的平均传感器数量逐渐减少。无论发送范围为多少，CACHO 算法与NPCC 算法相比，其平均传感器数都较少。2种算法的差值平均值为79.5，而最大值达到了118。对于CACHO 算法，平均传感器数量随着发送范围的增加明显减少，当感知范围增加时从l 增加

平均传感器数量从282减少到55。对于NPCC 算法，到6l 时，

平均传感器数量从最开始的400减少到了103。其原因在于当发送范围从l 增加到6l 时，CACHO 算法充分考虑了关键区域格点间的位置关系，通过增加的发送范围尽可能合理地减少节点放置数量，在保证连通性的同时有效减少了节点放置数量。

示，随着关键区域格点数的增加，2种算法放置的平均传感器数量随之增加。无论关键区域格点数为多少，CACHO 算法与NPCC 算法相比，其平均传感器数都少一些。且随着关键区域格点数的增加，两者的差值逐渐加大，从最初的21增加到55。对于CACHO 算法，其值增加得并不多，当关键区域格点数从50增加到100时，平均传感器数量仅从51增加到62。而对于NPCC 算法，平均传感器数量增加明显，基本呈线性增长，从最开始的72增加到了117。其原因在于CACHO 算法充分考虑了关键区域覆盖的连通性，并通过合理的分析关键区域格点之间的位置关系构建节点放置算法， —18—

500400平均传感器数

良好的连通性和覆盖优化能力。

CACHO NPCC

4 结束语

CACHO 算法易于在相关产品中实现，且具有良好的连通性与覆盖能力，为WSN 实际应用中的节点放置提供了一种切实可行且有效的途径。未来的研究工作将考虑网络中节点不同质(节点配置代价和覆盖能力有差异的情况) 并提供移动性情况下的覆盖问题，进而开发和设计实用的WSN 覆盖控制算法。

参考文献

[1] Akyildiz I F, Su Weiliang, Sankarasubramaniam Y, et al. Wireless

Sensor Networks: A Survey[J]. Computer Networks, 2002, 38(4): 393-422.

[2] Wang Wei, Vikram S, Wang Bang, et al. Coverage for Target

Localization in Wireless Sensor Networks[J]. IEEE Transactions on Wireless Communications, 2008, 7(2): 667-676.

[3] Cortes J, Martinez S, Karatas T, et al. Coverage Control for Mobile

Sensing Networks[J]. IEEE Trans. on Robotics and Automation, 2004, 20(2): 243-255.

[4] Tsai Yuh-Ren. Sensing Coverage for Randomly Distributed Wireless

Sensor Networks in Shadowed Environments[J]. IEEE Transactions

3002001000

34发送范围

1256

图5 发送范围增加时的平均传感器数

图6为关键区域格点选择分布概率从0.2增加到1时，CACHO 算法与NPCC 算法的平均传感器数。此时，感知范围R

s 固定为为100。

120100

，发送范围R t 为5l ，关键区域格点数固定平均传感器数

806040200

0.2

0.3

CACHO NPCC

0.40.50.80.60.7

关键区域格点选择分布概率

0.9

1.0

on Vehicular Technology, 2008, 57(1): 556-564.

[5] Kar K, Banerjee S. Node Placement for Connected Coverage in

Sensor Networks[C]//Proc. of Conference on the Modeling and

Optimization in Mobile, Ad Hoc and Wireless Networks. New Jersey, USA: IEEE Press, 2003: 50-52.

[6] Ke Wei-Chieh, Liu Binghong, Tsai Ming-Jer. Constructing a

图6 关键区域格点选择分布概率增加时的平均传感器数

如图6所示，随着分布概率的增加，2种算法放置的平

Wireless Sensor Network to Fully Cover Critical Grids by

均传感器数量逐渐减少。无论分布概率为多少，CACHO 算

Deploying Minimum Sensors on Grid Points is NP-complete[J].

法的平均传感器数都明显少于NPCC 算法。2种算法的差值

IEEE Transactions on Computers, 2007, 56(5): 710-715.

始终保持在40左右。对于CACHO 算法，平均传感器数量随

[7] Chvatal V. A Greedy Heuristic for Set Cover Problem[J]. Math.

着分布概率的增加逐步减少，当分布概率从0.2增加到1时，

Operations Research, 1979, 4(3): 233-235.

平均传感器数量从67减少到42。对于NPCC 算法，平均传

[8] Klein P N, Ravi R. A Nearly Best-possible Approximation

感器数量从最开始的112个减少到87。这表明关键区域格点

Algorithm for Node-weighted Steiner Tress[J]. Journal of 选择分布概率对2种算法的影响相当，即2种算法对不同关

Algorithms, 1995, 10(1): 104-115. 键区域格点的选取都具有较好的适应性。而CACHO 算法在

编辑陈晖

平均传感器数量放置的数量上具有明显优势，证明了它具有

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(上接第15页) 此其分析和设计过程较复杂。因为系统控制与信息传输情Constraints: Application to a Car Suspension System[J]. IEEE 况相关，所以系统稳定性与系统本身特性相关，并依赖信Transactions on Control Systems Technology, 2006, 14(4): 776-787.

[4] Lu Lilei, Xie Lihua, Fu Minyue. Optimal Control of Networked 息调度策略。本文提出的信息调度模型和分析方法适用于

Systems with Limited Communication: a Combined Heuristic and 多输入多输出的网络控制系统。基于此模型可以进一步研

Convex Optimization Approach[C]//Proceedings of the 42nd IEEE 究系统的信息调度与控制协同优化。

Conference on Decision and Control. Maui, Hawaii, USA: [s. n.], 参考文献

[1] Walsh G C, Beldiman O, Bushnell L. Scheduling of Networked

Control Systems[J]. IEEE Control Systems Magazine, 2002, 21(1): 57-65.

[2] Brockett R. Stabilization of Motor Networks[C]//Proceedings of the

34th IEEE Conference on Decision and Control. New Orleans, France: [s. n.], 1995: 1484-1488.

[3] Gaid M. B, Çela A, Hamam Y. Optimal Integrated Control and

Scheduling of Networked Control Systems with Communication

2003: 1194-1199.

[5] 宋洪波, 俞立, 张文安. 存在通信约束和时延的多输入多输出

网络控制系统镇定研究[J]. 信息与控制, 2007, 36(3): 334-339. [6] 樊卫华. 网络控制系统的建模与控制[D]. 南京: 南京理工大学,

2004.

[7] 俞立. 鲁棒控制——线性矩阵不等式处理方法[M]. 北京: 清

华大学出版社, 2002.

编辑陈晖

—19—