无线传感器网络中目标覆盖图的分解

张红武，张 聪，丰洪才，杨博斐，刘昌华，袁 操，夏祥胜，管 华

(1.武汉工业学院 a.数学与计算机学院；b.现代教育技术中心，武汉 430023；2.浙江大学信息与电子工程系，杭州 310058)

1 概述

无线传感器网络是由部署在监测区域内大量传感器节点组成[1-2]，通过无线通信连接成一个多跳的自组织网络系统[3-4]。它能协作地感知[5-6]、采集和处理网络覆盖区域内被感知对象的信息[7-8]，并发送给观察者[9-10]。

目标覆盖是无线传感器网络的一个重要问题[11]，研究在完成监测任务的前提下，如何尽量节省能耗以最大化目标覆盖生命期[12]。最大化目标覆盖生命期的主要途径，是合理配置网络中各节点状态，平衡网络能耗和有效覆盖率，提高网络能效[13]。文献[14-15]给出了最大目标覆盖生命期问题的定义。

定义 1 给定传感器网络，目标覆盖问题(Target Coverage Problem, TCP)是，在保证全部目标被连续监测的条件下，调度节点的活动，使网络覆盖的生命期最大。

TCP是一个NP完全问题[14-15]。随着目标和传感器节点的增加，无线传感器网络的规模迅速增大，TCP问题的难度也呈指数增长。

在无线传感器中，减小网络规模是减低算法复杂度的重要方法。但国内外还没有删除冗余节点、删除冗余目标、将无线传感器网络的目标覆盖图分解成多个独立子图的算法相关的研究。

本文采用减小网络规模的方法来降低算法的复杂度。首先，提出删除冗余的传感器节点的方法。其次，给出删除冗余的目标的方法。最后，将目标覆盖图分解成多个独立子图，并描述构建独立子图算法(Construct Independent Sub Graph Algorithm,CISGA)。

2 问题描述

在二维平面内，m个随机分布的目标要求被连续监测。为完成检测任务，n个传感器节点(简称节点)随机投放在目标区域内。假设每个节点的有效监测半径均为Rs，通信半径为 Rc，且Rc≥2Rs。

假设基站能获得全部传感器节点和目标的坐标，并能计算出传感器节点对目标的覆盖关系。

传感器网络用图G(S,T,E,W)表示[10]。其中，S是随机分布的传感器节点集，S={s1,s2,…,sm}；T是m个随机分布的目标集合，T={t1,t2,…,tm}；E是eij中eij=1位置关系集，E={eij|i∈{1,2,…,n}, j∈{1,2,…, m}}，eij表示节点si与目标tj的位置关系，eij=1，当且仅当目标 tj与节点 si的欧氏距离小于或等于覆盖半径 R，d(si,tj)≤R 时；否则，eij=0；W= {w1,w2,…,wn}是传感器节点初始能量集，wi表示传感器节点 si的初始能量，wi用节点能工作的最大单位能量数表示。

3 问题分析

3.1 冗余节点的删除

随着传感器节点和目标的增加，目标覆盖问题的计算复杂度急剧增长。减少问题的规模是减少计算复杂度的最好方法。为此，本文设计了3种措施来减少目标覆盖问题的规模。

传感器网络及其目标覆盖网络分解如图1所示。图1(a)所示是一个有5个传感器节点{s1, s2, s3, s4, s5}和4个目标{t1, t2, t3, t4}的传感器网络。每个节点的覆盖区域是以节点为圆心的圆，圆的半径是节点的感知半径。图1(b)描述了节点和目标的覆盖关系。若用T(si)

表示节点si覆盖的目标集，则在图1(b)中，T(s1)={t1,t2}, T(s2)={t3,t4}, T(s3)={t1,t2}, T(s4)= {t3,t4}, T(s5)=Φ。

在图1(b)中，s5不覆盖任何目标，为研究其能否被删除，下面证明冗余节点的删除定理。

图1 传感器网络及其目标覆盖网络分解

定义 2 在不考虑节点连通的条件下，冗余节点是不覆盖任何目标的传感器节点。

定理 1 如果某节点不覆盖任何目标，则该节点可以被删除。

证明：由定义可知，在不考虑传感器节点连通的情况下，目标覆盖问题是调度能覆盖目标的节点，而与不覆盖目标的节点没有任何影响。因此，删除冗余节点，目标覆盖问题没有任何变化。

下面导出冗余节点删除规则。

规则1 冗余节点可以删除。

如图1所示，删除节点s5能减少无线传感器网络中的节点数目。特别是，在大量节点密集部署的无线传感器网络中，存在大量冗余节点。删除这些冗余节点能大幅减少节点数目，从而减少目标覆盖问题的计算复杂度。

3.2 冗余目标的删除

如图1所示，当t2被覆盖时，则t1也一定被覆盖，反之亦然。当t4被覆盖时，则t3也一定被覆盖，反之亦然。也就是说，若有 2个目标 ti和 tj，当 ti的覆盖集等于tj的覆盖集时，删除其中的一个目标，能减少无线传感器网络中目标的数目，但对于目标覆盖问题的最大生命期没有影响。

若Ci表示目标ti的覆盖集，Ci是由能够覆盖目标ti的节点组成的集合。如图 1所示，C1={s1,s3},C2={s1,s3}, C3={s2,s4}, C4={s2,s4}。

定理 2 若 Ci=Ck，则当 ti被覆盖，则 tk也一定覆盖。

证明：当ti节点覆盖，则 ∃ su∈ Ci，su覆盖 ti。又因 Ci=Ck，所以 su∈Ck。也就是说，su也覆盖tk。

从定理2可知，若2个目标的覆盖集相等，当其中的一个目标被覆盖时，则另一个目标也一定被覆盖。因此，给出冗余目标的定义。

定义3 当2个或2个以上的目标覆盖集相等时，则下标最小的目标是必要目标，其他目标都是冗余目标。冗余目标可以被删除。

假设在某一时间段 b1内，为保证目标集 T的完全覆盖，最优的活动节点集为S1。下面要证明删除冗余目标后，为保证目标集T’的完全覆盖，最优的活动节点集S1不改变。

定理 3 为保证目标的完全覆盖，删除冗余目标不会减少活动节点集中的活动节点。

证明：设 T1={ti,ti+1,…,tj}是一个具有相同覆盖集的目标集，活动节点sk(sk∈S1)唯一覆盖目标集T1。

当删除T1中的冗余目标时，一定要保留T1中的必要目标，为保证该必要目标的覆盖，sk必须保持活动状态。也就是说，删除冗余目标后，不会减少活动节点集中的活动节点。

由此，引出定理4。

定理 4 若删除冗余目标，目标覆盖问题的最大生命期不变。

证明：设目标覆盖问题的最大生命期的最优时间序列为,,…,。其中，T是初始目标集；bk表示活动时刻；Sk是 bk的活动节点集。

由定理3，可知删除目标集中的冗余节点后，不改变该时刻的活动节点集。则删除 T中的冗余节点后，各活动节点集不会减少，当然也不会增加。这样，目标覆盖问题的最大生命期的最优时间序列不会发生变化。定理得证。

下面导出冗余目标删除规则。

规则 2 当 Ci=Ck时，保留必要目标，删除冗余目标。

特别地，在目标分布密集的无线传感器网络中，删除冗余节点能大幅减小目标数目，从而减小目标覆盖问题的算法复杂度。

3.3 目标覆盖图的分解

每一个目标覆盖网络都可以用一个目标覆盖图表示。例如图1(a)可以表示成图1(b)。为便于理解，将目标覆盖网络的分解描述成目标覆盖图的分解。

在目标覆盖图中，如果一个子图与其他部分没有公共节点和公共边，则该子图能被分割出来，成为一个独立子图。

如图1(b)所示，目标覆盖图分割成2个独立自网络，一个子图是 G(S1,T1,E1,W1)，其中，S1={s1,s2}；T1={t1,t2}；E1={e11,e12,e31,e32}。另一个子图是G(S2,T2,E2,W2)，其中，S2={s2,s4}；T2={t3,t4}；E1={e23,e24,e43,e44}。

给定目标覆盖图 G(S,T,E,W)。G(S,T,E,W)能被分解成 2个独立子网 G(S1,T1,E1,W1)和 G(S2,T2,E2,W2)，当且仅当 S1∪S2=S, T1∪T2=T, E1∪E2=E, W1∪W2=W,S1∩S2=Φ, T1∩T2=Φ, E1∩E2=Φ, W1∩W2=Φ。如此类推，可将子图分解成更小的独立子图，直到不能再分为止。

下面提出一种构造独立子图算法CISGA。

定理 5 CISGA算法不改变目标覆盖问题的最大生命期。

证明：CISGA算法只是将结构上独立的子网从整体上分离出来。它既没有增加边，也没有减少边；它没有增加或减少任何节点。也就是说，它没有改变目标覆盖图的结构，不会改变目标覆盖问题，所以也不会改变目标覆盖问题的最大生命期。

4 算法仿真

在Windows XP上采用Matlab作为仿真软件，在设定的500 m×500 m的矩形区域内，随机产生目标的二维坐标、节点的二维坐标和初始能量。假设传感器节点为全向覆盖，覆盖半径为Rs=40 m。

实验1 在监测区域内随机放置25个目标后，再分别随机放置40个、60个、80个、100个、120个、140个、160个、180个、200个节点。比较冗余节点的数目，取多次实验的均值为实验结果，实验结果如图2所示。

图2 不同节点的无线传感器网络中的冗余节点个数

从图2可见，无线传感器网络中存在冗余节点。删除冗余节点能大幅减少目标覆盖问题的规模。当节点分布越密集，则在非目标区域内存在更多的冗余节点，则删除冗余节点来减小算法规模的效果越明显。

实验结果表明：删除冗余节点能大大减少目标覆盖问题的规模。

实验 2 在监测区域内随机放置 100个节点，再分别随机放置25个、55个、85个、115个、135个、175个、205个、235个、265个、295个、325个目标。比较冗余目标的数目，取多次实验的均值为实验结果，实验结果如图3所示。

从图3可见，无线传感器网络中存在冗余目标。删除冗余目标能大大减少目标覆盖问题的规模。当目标分布越密集，则在节点覆盖区域内存在更多的目标，则冗余目标就越多。

图3 不同目标的无线传感器网络中冗余目标的个数

实验结果表明：删除冗余目标能大幅减少目标覆盖问题的规模。

实验3 在监测区域内随机放置25个目标后，再分别随机放置25个、55个、85个、115个、135个、175个、205个、235个、265个、295个、325个目标。比较独立子网的最大规模，取多次试验的均值为实验结果，实验结果如图4所示。

图4 不同节点网络中最大独立子网的规模

从图4可见，CISGA算法能大幅减小目标覆盖图的规模。随着节点数目的增大，CISGA算法减小网络规模的效果越明显。

5 结束语

为了减小目标覆盖问题的规模，本文设计了删除冗余节点和冗余目标、分解独立子图的策略，并提出了一种构造独立子网算法。仿真实验证明，CISGA算法能降低30%的网络规模，大幅减少了目标覆盖问题的复杂度。该算法的复杂度低、效率高、可扩展性好。

目前，在无线传感器网络中，目标覆盖与连通[16]、基于定向天线节点的目标覆盖、基于移动节点的目标覆盖[17]、三维空间的目标覆盖、多目标的关联覆盖[18]等问题，都是NP-完全问题。研究这些问题的网络分解算法是下一步的工作内容。

[1]Huang G T.Casting the Wireless Sensor Network[J].Technology Review, 2003, 106(6): 50-56.

[2]Kahn J, Katz R H, Pister K.Next Century Challenges:Mobile Networking for Smart Dust[C]//Proc.of the 5th Annual International Conference on Mobile Computing and Networking.New York, USA: ACM Press, 1999: 271-278.

[3]Raghunathan V, Schurgers C, Park S, et al.Energy-aware Wireless Microsensor Networks[J]. IEEE Signal Processing Magazine, 2002, 19(2): 40-50.

[4]Cardei M, Du Dingzhu.Improving Wireless Sensor Network Lifetime Through Power Aware Organization[J].ACM Wireless Networks, 2005, 11(3): 333-340.

[5]郑增威, 吴朝晖, 金水祥.无线传感器网络及其应用[J].计算机科学, 2003, 30(10): 138-140.

[6]沈 波, 张世永, 钟亦平.无线传感器网络分簇路由协议[J].软件学报, 2006, 17(7): 1589-1600.

[7]张媛媛, 谷大武.无线传感器网络密钥建立协议的能耗分析[J].信息安全与通信保密, 2007, 8(8): 85-89.

[8]文 戈, 王国军, 过敏意.无线传感器网络中基于Voronoi图的覆盖和连通综合配置协议[J].传感技术学报, 2007, 20(10): 2294-2302.

[9]Zhang Hongwu, Wang Hongyuan, Feng Hongcai.A Heuristic Greedy Optimum Algorithm for Target Coverage in Wireless Sensor Networks[C]//Proc.of IEEE International Conference on Circuits, Communications and Systems.[S.l.]: IEEE Press, 2009: 39-42.

[10]张西红, 妙文亮, 高彦彦.无线传感器网络的覆盖问题研究[J].计算机工程, 2009, 35(16): 109-111.

[11]张红武, 王宏远, 丰洪才.一种无线传感器网络目标的最优覆盖算法[J].小型微型计算机系统, 2009, 30(11):2146-2149.

[12]孙泽宇, 邢萧飞, 巍 巍.无线传感器网络中的目标关联覆盖算法[J].计算机工程, 2011, 37(9): 138-143.

[13]王小平, 罗 军, 沈昌祥.无线传感器网络定位理论和算法[J].计算机研究与发展, 2011, 48(3): 353-363.

[14]Cardei M, Thai M T, Li Yingshu, et al.Energy-efficient Target Coverage in Wireless Sensor Networks[C]//Proc.of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies.[S.l.]: IEEE Press, 2005:1976-1984.

[15]Garey M R, Johnson D S.Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman[M].New York, USA: [s.n.], 1977.

[16]曲家庆, 张 曙.连通和覆盖性优化无线传感器网络寿命的方法[J].通信学报, 2011, 32(3): 361-365.

[17]王良民, 李 菲, 秦 颖.基于移动节点的无线传感器网络覆盖洞修复方法[J].通信学报, 2011, 32(4): 456-461.

[18]孟凡治, 王换招, 何 晖.基于联合感知模型的无线传感器网络连通性覆盖协议[J].电子学报, 2011, 39(4):772-779.