一种基于无交集节点分组的无线传感器网络覆盖算法

杨凤伟，陈小惠，刘银锋

（南京邮电大学自动化学院，江苏 南京，210003）

0 引言

无线传感器网络(wireless sensor network，WSN)是随着无线通信技术、传感器技术、移动计算技术和嵌入式信息处理技术的发展而新兴的研究课题，可以应用到人类无法到达的地方，比如战场、受污染区域等[1]。

覆盖问题和连通问题是无线传感器网络中的基本问题，是直接影响网络性能和服务质量的关键因素之一。无线传感器网络中的覆盖问题指被监测区域内的每一点至少在一个传感器节点的传感范围内；连通问题指网络内没有孤立节点存在，任意两个节点都可以通信。无线传感器网络中的覆盖问题、连通问题及节点布置问题对提高WSN的鲁棒性，容错性等性能以及降低成本和节省能量等方面有着直接的影响，因此对这些问题的研究已经成为目前的一个研究热点[2-3]。

近年来，许多学者都对WSN的覆盖问题进行了研究，并取得了一定的成果[4]。许多研究[5-9]都在完全覆盖或k覆盖方面做了很多工作，因此研究“通过使用尽可能少的工作节点来达到所期望的任意覆盖率”的方案是很有意义的[10]。

1 随机调度覆盖算法

1.1 传感器节点部署模型

本文考虑如下性质的传感器网络[11]：

（1）需要检测的目标区域相对传感器感知范围足够大，可以忽略边界因素对目标覆盖带来的影响。

（2）传感器节点采用随机部署，部署后不再移动。

（3）传感器感知采用0-1感知模型，即每个节点具有相同的感知半径，在感知半径内的事件可被传感器节点侦测。

（4）传感器节点间需要用某种机制或者算法完成有一定精度的时钟同步，保证节点之间时钟误差在一定范围内。

1.2 问题描述及分析

为了满足实际应用需求，在部署无线传感器网络时，往往会存在许多冗余节点。如果所有节点始终处于活动状态，会产生许多冗余数据，从而造成能量浪费。利用传感器节点的高冗余特性，通过调度传感器节点的工作状态，关闭众多的冗余节点，可有效减少节点的能耗，由此可见，研究节点调度方式延长网络的生存时间完全有必要并且是可行的。

覆盖调度算法的基本思想是将全部随机部署的传感器节点组织成为若干个节点的集合，并且每个节点集合都能够完全覆盖被监测的目标，这些节点集以时间槽的方式轮流交替工作。并且在每个时间槽内只有一个节点集合处于工作模式，不属于此集合的其它传感器节点都处于低功耗的休眠模式。通过采用这样的方式调度每个传感器节点，可以延长整个网络的生存时间。

随机调度覆盖算法是一种基于分组的节点调度覆盖算法，它的基本思想是：每个传感器节点随机赋予1到K的某个值i(K，i∈N*),并将自身分配到第i组。在执行完算法之后，依次调度每一组的传感器节点对目标区域进行监测[12]。由于位置非常临近的传感器节点可能分配到同一组或者是少数几组，导致目标区域内节点分布不均匀，目标区域中某些小区域节点分布过于密集，增加了该区域的通信冲突和数据冗余。而有些小区域节点分布过于稀疏，导致传感器节点不能对目标区域进行有效监控，并且降低了网络的连通性。

基于随机选取节点实现无交集节点分组的调度覆盖算法虽然执行简单，运行时间较快，但它获得的分组数较少且节点的通信半径必须是传感半径的2倍。研究一种改进的基于无交集节点分组的节点调度覆盖算法，确保传感器网络获得的分组较多，且保证网络的连通性。

2 一种基于无交集的节点分组算法

2.1 问题分析

给定一个特定目标区域，在目标区域上采用冗余布置节点办法，大量的传感器节点随机散布目标区域。当传感器节点布置完毕后，形成区域A，它由众多不同覆盖度的小区域组成。区域划分结束之后，假定Acri区域：在所有组成区域A的小区域中覆盖度最低的区域，称之为关键区域。

假设：Acri为{S1,S2,S3,S4},其覆盖度为4。每一次选出一个子集Ci,覆盖区域Acri的节点至少有一个被选入，因此所能获得的最大子集数为4。在考虑Acri时，选择了S1加入Ci，当遍历到下面某个区域Ai={S2,S3,S6,S7},如果选择S2或S3，作为覆盖区域Ai的节点加入Ci，则进入Ci+1子集时，以前的Acri覆盖度至少减少2，减少了能分得的子集数。

任意给定无线传感器网络的两个节点Si和Sj，Si的位置为（xi,yi），Sj的位置为（xj,yj）。若两个传感器节点之间的距离小于或等于通信半径Rc，即:

则称Si和Sj互为传感邻居，即节点Si和节点Sj之间是连通的。

2.2 算法流程图

流程图如图1所示。

图1 算法流程图

其中A为目标区域，C为所有的传感器节点集合；U为没有被传感器节点覆盖到的区域；V为可用节点集合。

该算法试图选择这样的传感器节点，能尽可能多地覆盖还没有被已选择的节点覆盖的区域，尽可能地没有覆盖已经被其他节点覆盖的区域。算法期望得到的每个节点分组都能对目标区域实现全覆盖，并且通过考虑节点之间的距离来使整个网络连通。

3 仿真结果与分析

3.1 工作节点分布

我们用MATLAB随机生成一个节点分布区域,在500m×500m的范围内随机安放节点，如图2所示。

图2 节点分布图

为了对比随机选取节点实现无交集节点分组方式和本文改进的节点调度覆盖算法的性能表现，本文考虑了在节点传感半径和目标区域划分为小区域的数目一定的情况下，所获得连通覆盖集数与节点数目之间的关系。

3.2 实验结果

首先设定传感半径为Rs=50m，下面来对比随机选取节点实现无交集节点分组方式和本文改进的无交集节点分组算法分别在节点通信半径Rc=100m、Rc=80m所获得的连通覆盖集数，仿真结果如图3与图4所示。

图3 Rc=100m时获得的连通覆盖集数

图4 Rc=80m时获得的连通覆盖集数

从图3, 4中可以看出，改进的无交集节点分组算法比随机选取节点的无交集节点分组能获得更多的连通覆盖集，即能延长网络的寿命。且改进的无交集节点分组算法因为考虑了网络的连通性，所以随着通信半径的变化，获得的连通覆盖集个数变化很小。而随机选取节点的无交集节点分组算法因为要求通信半径是传感半径的2倍，所以获得的连通覆盖集个数会明显减少。

由于该算法的退出条件是不能找到一个节点集合能覆盖整个给定目标区域且保证整个网络连通，算法中止。在传感器网络中，会存在空闲节点。空闲节点的数量可以反映出对传感器节点的利用程度。

为了更形象的表示，我们对节点数和节点利用率进行了仿真，结果如图5所示。

图5 节点利用率比较

4 结论

综上所述，本文研究的算法比随机选取节点实现无交集节点分组算法能获得更多的分组且保证网络连通。

[1] Wall J, Platt G, James G. Wireless sensor networks as agents for intelligent control of distributed energy resourcees[C]. In: Wireless Pervasive Computing, Sydney, Australia, 2007.

[2] 李德识,李薇.无线传感器网络中覆盖问题的研究[J].微电子学与计算机,2005,22(8):150-152.

[3] 王燕莉，安世全.无线传感器网络的覆盖问题研究[J].传感技术学报，2005，18(2):307-312.

[4] ZHANG H,HOU J C.Maintaining sensing coverage and connectivity in large sensor networks[J].Ad Hoc & Sensor Networks,2005,1(1-2):89-124.

[5] CARLE J,SMPLOT-PYL D.Energy-efficient area monitoring for sensornetworks[J]. Computer,2004,37(2):40-46.

[6] GUPTA H,ZHOU Z,DAS S R,et al Connected sensor cover.self-organization of sensor networks for efficient query execution[J].IEEE/ACM Transactions on Networking,2006,14(1):55-67.

[7] M E G U E R D I C H I A N S,K O U S H A N F A R F,POTKONJAK M,et al Coverage Problems in Wireless Ad-hoc Sensor Networks[C]//Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies Anchorage:[sn],2001:1380-1387.

[8] SHAKKOTTAI S,SRIKANT R,SHROFF N.Unreliable Sensor Grids:Coverage,Connectivity and Diameter[C]. Proc IEEE NFOCOM 2003.SanFrancisco:[sn],2003.

[9] ZHOU Z,DAS S,GUPTA H.Connected K-coverage Problem in Sensor Networks[C]//13th Intemational Conference on Computer Communications and Networks Chicagv:[sn],2004:373-378.

[10] LIU Y,LIANGW.Approximate Coverage in Wireless Sensor Networks[C].Proceedings of IEEE Conference on Local Computer Networks 30th Anniversary(LCN’05). Sydney:[sn],2005.

[11] 蒋 杰, 方 力, 张鹤颖. 无线传感器网络最小连通覆盖集问题求解算法[J].软件学报,2006,17(2): 175-184.

[12] Liu C, Wu K, King V. Randomized coverage-preserving scheduling schemes for wireless sensor networks[C]. In: Proc. of Fourth IFIP International Conference on Networking. HCMC, Viet Nam, 2005, 956-967.