无线传感器网络中一种基于节点序列的覆盖算法
宁菲菲，王国军，邢萧飞
(中南大学 信息科学与工程学院，湖南 长沙，410083)
摘要：针对覆盖问题是无线传感器网络中的一个基本问题。不同的应用场景对网络的覆盖度有不同的要求，提出一种基于节点序列的覆盖算法(CNS)来判断网络的覆盖情况、消除覆盖漏洞。算法首先讨论如何判断网络1度覆盖情况，然后通过调整距离覆盖漏洞最近的传感器节点的感应半径来动态提高网络的1度覆盖率。同时，还对CNS算法进行扩展，用来解决多度覆盖问题。模拟结果表明：CNS算法在性能上要比现有覆盖算法优越。
关键词：无线传感器网络；覆盖；覆盖漏洞；覆盖率；节点序列
中图分类号：TP393 文献标志码：A 文章编号：1672-7207(2011)07-2028-06
Coverage algorithm with node sequences in wireless sensor networks
NING Fei-fei, WANG Guo-jun, XING Xiao-fei
(School of Information Science and Engineering, Central South University, Changsha 410083, China)
Abstract: Coverage is a fundamental issue in wireless sensor networks (WSNs) where different applications require different coverage degrees. For the coverage problem, a coverage algorithm with node sequences (CNS) judging whether a region was covered and solving the coverage hole problem was proposed. Firstly, the method of judging whether a network was 1-covered by using the CNS algorithm is discussed. Secondly, by adjusting the sensing radius of the sensor nodes which are nearest to the uncovered regions, the uncovered regions are 1-covered. At last, the CNS algorithm to solve the k-coverage problem is extended. The simulation results show that the proposed CNS algorithm has better performance than the existing coverage algorithms.
Key words: wireless sensor networks; coverage; coverage hole; coverage rate; node sequences
无线传感器网络是当前十分热门的研究课题，得到了越来越广泛的关注[1]。无线传感器网络是一个由大量廉价的传感器节点组成的无线自组织网络。每个传感器节点由计算单元、存储单元、传感器单元和无线通信单元等构成[2]。无线传感器网络被广泛应用在国家基础设施、工业生产环境的安全监控、医疗护理监控、自然生态环境监测和动植物栖息地的科学观测等领域。覆盖作为无线传感器网络中的一个基本问题，它要解决的问题是在传感器节点被布置到目标区域后保证该区域能够被传感器节点有效监控。文献[3]中将传感器网络的覆盖问题分为3大类：区域覆盖[4-6]、目标覆盖[7-8]和障碍覆盖[9]。由于传感器节点能量有限并且难以给数目众多的节点更换电池，所以，很多应用为了保证网络的服务质量要求网络覆盖度k＞1[10]。因此，覆盖度被认为是衡量传感器网络服务质量的一个重要标准。人们对无线传感器网络的覆盖问题进行了深入研究。Huang等[11]提出了一个多项式时间复杂度的算法来判断网络是否被k度覆盖。该算法通过判断网络内每个传感器节点感应圆盘的圆周覆盖情况进而得出整个网络的覆盖情况，并证明了只要网络中节点感应圆盘的圆周被充分覆盖，整个网络区域就被充分覆盖。Wang等[12]提出当网络内任意2个节点感应圆盘的交点以及节点感应圆盘与区域边界的交点都至少被k度覆盖时，网络区域一定被k度覆盖；CCP协议可以动态配置网络以提供不同的覆盖度来满足不同的应用需求。该协议利用节点的局部位置信息进行分布式的节点职能合格性的判断，合格节点处于活跃状态，而不合格者将暂时处于休眠或监听状态，从而达到节省能量的目的。该研究证明了当节点的通信半径大于或者等于感应半径的2倍时，如果网络k度覆盖给定凸区域，那么在该区域中网络是k度连通的。CCP协议的时间复杂度高于文献[11]中的方法。Shen等[13]提出了Grid Scan算法，其主要思想是通过将网络区域划分成许多正方形网格并分别对每个网格进行覆盖判断，最终得出整个网络区域的覆盖率。只要网格的中心点被k度覆盖，就可以认为该网格被k度覆盖。如果覆盖率达不到应用要求，则通过增加节点的方法增大网络的覆盖率。本文作者提出一个基于节点序列的覆盖算法。CNS算法通过使用节点序列不仅可以有效地判断网络区域的1度覆盖情况，而且对目标区域的多度覆盖情况也能够进行准确判断。同时，还提出了动态增大网络1/多度覆盖率的有效方法。
1 算法描述
1.1 基本假设和基本概念
基本假设：
(1) 传感器节点比较均匀地布撒在网络中并且节点密度较大。
(2) 传感器节点的感应模型都是圆盘模型。
(3) 传感器节点的感应半径是可以调节的，变化范围为Rs~Rsmax，初始值为Rs。
(4) 每个传感器节点都知道自身的地理位置信息 (如通过配备GPS或某种定位算法获得)。
为便于描述，这里对将要用到的基本概念说明如下。
定义1 如果区域A中点P至少位于k个不同的传感器节点的感应圆盘内，那么，就称点P被k度 覆盖。
定义2 如果区域A中点P被节点数量小于k的传感器覆盖，则称该点P为k度覆盖漏洞。
1.2 节点序列
Zhong等[14]提出了节点序列的概念。下面对该概念进行简要介绍。
定义3 按照区域中的点与网络中各传感器节点之间的距离递增的顺序对网络中的传感器节点排序，所得的序列称为传感器节点序列，简称为节点序列。
定义4 将由具有相同节点序列的点所组成的区域定义为“面”(face)，记为fi (fi表示区域中第i个“面”)。
定义5 把“面”所对应的节点序列称为“面”的标志节点序列，简称标志序列。fi的标志序列记为Sfi。
定义6 当节点Sj (Sj表示区域中第j个节点)与“面”fi的重心之间的距离小于节点的感应半径Rs时，就称fi被节点Sj覆盖。
步骤1 给定节点S1和S2，整个区域被2个节点连线的中垂线Div(S2, S1)划分为左、右2个部分，如图1(a)所示。从几何的角度来讲，位于右半部分区域中的点距离S2比S1更近，因此，如果按照节点距离区域内的点由近至远的顺序对S1和S2进行排序，那么，右半部分区域内的点都有着共同的节点序列：(S2, S1)。图1(a)中共有2个“面”，分别记为f1和f2，它们的标志序列分别为Sf1=(S1, S2)和Sf2 =(S2, S1)。当节点数目为3时，网络区域被划分为6个“面”，每个“面”都有着唯一的标志序列，如图1(b)所示。
图1 网络区域划分
Fig.1 Network division examples
对文献[14]中所提出的网络区域划分方法进行改进。该方法在对网络区域进行划分的过程中，需要对网络中任意2个节点的连线做中垂线。对一个节点数量为n的网络区域进行划分共需要做n(n-1)/2条中垂线。这种全局的区域划分方法不仅繁琐而且计算过程中节点能量消耗较大，尤其是对于节点数目较多的大规模传感器网络。改进后的区域划分方法具体如下：将网络区域划分为一定面积的正方形网格(边长依区域面积和网络中节点数目而定)，如图1(b)所示。一个网格为一个簇，每个簇都有1个簇头节点。
步骤2 依次对网络区域内的网格进行区域划分，即对同一网格内的任意2个节点的连线做中垂线。簇头节点负责计算和存储簇内所有“面”的标志序列。
为了对比这2种区域划分算法的性能，在400 m×400 m的区域内随机部署1 000个初始能量为1 J的传感器节点，对改进前、后的算法进行能耗和时间的比较，见表1。
表1 改进前、后的区域划分方法的性能比较
Table 1 Performance comparison between two network division algorithms
由表1可以看出：改进后的划分方法无论是在能耗上还是在运行时间上都比改进前降低很多。
图2(a)和2(b)所示分别为按照文献[14]中的方法和改进后的方法对包含有20个传感器节点的网络区域进行划分所得的对比结果。
通过比较发现：按照改进后的方法来对网络区域进行划分，不仅使得区域中“面”的总数大大减少，而且面积较小的“面”的数目也较改进前减少很多；提高了算法的执行效率。
1.3 覆盖度k=1时CNS算法的实现
首先讨论如何判断网络区域是否被1度覆盖，然后对其产生的覆盖漏洞的解决方案进行描述。
1.3.1 对网络1度覆盖情况的判断
对网络区域进行划分后，网络区域可以看作由一定数目的“面”组成，如图2(b)所示。在这些“面”中，有些包含有传感器节点，有些是不含有传感器节点的。根据这一特点，在判断网络的1度覆盖情况时，本文分以下2种情况分别进行讨论。
图2 网络区域划分对比(节点数目为20)
Fig.2 Comparison of network divisions after deployed 20 sensors
(1) 包含传感器节点的“面”。由于网络中节点密度较大，区域划分所得“面”的面积较小，所以，在大多数情况下，节点与“面”的重心间的距离比节点的感应半径要小得多。因而，对于网络区域中那些包含有传感器节点的“面”来说，可以认为它们被其所包含的传感器节点大致覆盖。
(2) 不包含传感器节点的“面”。“面”的标志序列中各传感器节点的顺序是按照节点与“面”内各点间的距离由近至远的规律排列的。当判断不包含传感器节点的“面”的1度覆盖情况时，需要根据“面”的标志序列找出距离它最近的传感器节点，进而判断此节点对该“面”的覆盖情况即可。如果该节点能够覆盖该“面”，那么该“面”一定被1度覆盖；如果该“面”不能被距离它最近的节点所覆盖，那么，它也一定不能被网络中的其他节点所覆盖，则该“面”为覆盖漏洞。
“面”f1，f3和f4各包含1个传感器节点，根据上述(1)中的描述可以认为它们分别被其所包含的节点覆盖，如图1(b)所示。“面”f6不含有传感器节点，需根据上述(2)中的方法判断其1度覆盖情况。f6的标志序列(S2, S3, S1)表明在S1，S2和S3这3个节点中，S2距离f6最近。所以，要判断f6的1度覆盖情况，只需要判断距离f6最近的节点S2是否覆盖f6即可。根据定义6，计算S2与f6的重心间的距离d。若d＜Rs，则认为f6被节点S2 1度覆盖；反之，则表明f6没有被1度覆盖。判断网络1度覆盖情况的算法如下所示。
For each grid Gk∈G
{
For each Si in Gk
If (i≠j) Div(Sj, Si);
Get the division of Gk;
Calculate the signature sequence Sfi of each fi in Gk, Sfi= (Sa, Sb, …, Sx);
}
For each fi in G
{
If (there is Si ∈S in fi)
fi is 1-covered by Si;
Else{
Calculate the center of gravity point Ci of fi;
d=D(Sa , Ci);
If (d＞Rs) fi is not 1-covered;
Else fi is 1-covered;
}
}
1.3.2 动态提高网络的1度覆盖率
按照1.3.1节中所述方法对网络区域中的“面”进行1度覆盖判断后，可以计算得到网络的1度覆盖率。如果得到的1度覆盖率不满足应用需要，那么，可通过如下方法提高网络覆盖率。
步骤1 由簇头节点对其簇内没有被1度覆盖的“面”进行统计。
步骤2 簇头根据它所存储的“面”的标志序列信息找出距离步骤1中每个“面”最近的节点，即出现在标志序列第1位的节点。簇头对这些节点按出现次数由多至少的顺序进行排序。
步骤3 根据步骤2所得节点次序先后增大相应节点的感应至Rs max，直至网络当前的1度覆盖率达到应用要求为止。
假设有一节点数量为5的网络，经区域划分并判断之后，网络中共有6个“面”没有被1度覆盖，它们的标志序列分别为(Si, …)，(Sj, …)，(Si, …)，(Sk, …)，(Si, …)和(Sk, …)。统计各节点在标志序列的第1位所出现的次数，Si共出现3次，Sk出现2次，Sj出现1次。因此，增大Si，Sk和Sj的感应半径分别能使3个、2个和1个未被覆盖的面可能被覆盖，故选择增大Si的感应半径，以最小的能耗使网络覆盖率得到最大的提高。因此，首先选择增大Si的感应半径至 Rs max，若覆盖率还不能满足应用要求，再增大Sk的感应半径至Rs max，最后增大Sj的感应半径至Rs max。
1.4 覆盖度k＞1时CNS算法的实现
1.4.1 对网络多度覆盖情况的判断
要判断网络的多度覆盖情况，需要先对网络中的“面”的覆盖情况进行判断，然后得出网络的覆盖情况。要判断一个“面”是否被k(k＞1)度覆盖，只需要判断该“面”是否被其标志序列中第k个节点覆盖即可。如果第k个传感器节点覆盖该“面”，那么标志序列中的前k-1个节点必定覆盖该面，则该“面”被k度覆盖。如图1(b)所示，由f1的标志序列(S2, S1, S3)可知：要判断f1是否被3度覆盖，只需要判断f1是否被其标志序列中的第3个传感器节点S3覆盖即可；当S3覆盖f1时，f1一定被3度覆盖；若S3没有覆盖f1，则f1一定不满足3度覆盖。
判断网络区域是否被k度覆盖的具体算法如算法2所示。
1.4.2 动态提高网络的多度覆盖率
为了以最小的代价使网络的k(k＞1)度覆盖率得到最大提高，采用以下方案来动态提高网络的多度覆盖率：
步骤1 由簇头节点对簇内被k-1度覆盖的“面”进行统计。
步骤2 簇头对出现在步骤1中每个“面”标志序列第k位的节点进行统计并按出现次数的多少对它们进行排序。
步骤3 增大出现次数最多的传感器节点的感应半径至Rs max。
步骤4 计算网络当前的k度覆盖率，若达到应用要求则结束，否则转步骤1。
对于区域中被k-1度覆盖的“面”，只需要增大其标志序列中第k个传感器节点的感应半径便有可能使其达到k度覆盖。上述方法是大幅度提高网络k度覆盖率的有效方法。
判断网络多度覆盖情况的算法如下：
For each grid Gk∈G
{
For each Si in Gk
If (i≠j) Div (Sj, Si);
Get the division of Gk;
Calculate the signature sequence Sfi of each fi in Gk, Sfi =
(Sa, Sb, …, Sk, …, Sx);
}
For each fi in G
{
Calculate the center of gravity point Ci of fi;
d=D (Sk, Ci);
If (d＜Rs) fi is k-covered;
Else fi is not k-covered;
}
1.5 理论分析
定理1 CNS算法的平均时间复杂性为O(n2)，其中n为网络中的节点数目。
证明 CNS算法由判断网络1/多度覆盖情况和动态提高网络1/多度覆盖率2个算法组成。其中判断网络1/多度覆盖情况的算法中，对网络区域进行划分的时间复杂性为O(n2)，对区域中的“面”进行覆盖判断的时间复杂性为O(n2)；而动态提高网络1/多度覆盖率算法的时间复杂性取决于步骤2中对节点进行排序的时间复杂性。最慢的排序算法的时间复杂性为O(n2)，最快的排序算法的时间复杂性为O(nlogn)。故CNS算法的平均时间复杂性为O(n2)。
2 性能评价
为了评估本文提出的CNS算法的性能，将CNS与文献[13]中Grid Scan算法性能进行比较。具体的实验参数如表2所示。在实验中，使用网络覆盖率和网络生命期作为评价算法性能的指标。所有实验均在Windows XP操作系统下采用Java语言编程，运行环境为Eclipse 3.2。
表2 模拟参数
Table 2 Simulation parameters
为方便计算网络覆盖率，本文采用的方法是将网络区域划分为1 m×1 m的小方格。如果方格的中心点被覆盖，就认为整个方格被覆盖。因此，k度覆盖率η可以按如下公式计算：
η=|t|/|T|。 (1)
其中：|T|为整个网络区域的方格总数；|t|表示至少被k个不同节点所覆盖的方格数目。
2.1 网络覆盖率
网络覆盖率是衡量网络服务质量的一个重要指标。本实验根据1.3.2节和1.4.2节所描述的算法选择网络中的某些传感器节点，增大它们的感应半径至 Rs max=15 m，以提高网络的覆盖率，网络覆盖率与Rs=Rs max的节点数的关系如图3所示。
图3中，横坐标表示从网络中选择的需增大感应半径的节点数量。从图3可见：当网络中所有节点的感应半径均等于Rs=10 m时，网络的1度覆盖率为85.02%。依据1.3.2节中的算法从网络中选取20个传感器节点并增大它们的感应半径至Rs max，网络的1度覆盖率可增大至94.16%。当按照1.4.2节中的算法从网络中选取80个节点并增大它们的感应半径至Rs max时，网络的2度覆盖率和3度覆盖率分别提高了22.5%和31.42%。
图3 网络覆盖率与Rs=Rs max的节点数的关系
Fig.3 Relationship between coverage rate and number of sensors whose Rs= Rs max
2.2 网络生命期
节点的能耗是无线传感器网络中的一个重要问题，它在很大程度上决定了网络的生命期，因此，希望所提出的算法具有能量高效的特点。图4所示为网络覆盖率随时间的变化关系。当网络的1度覆盖率小于0.7时，就认为网络无法实现完全覆盖。从图4可以看出：与Grid Scan算法相比，CNS算法在保持较高的1度覆盖率的前提下使网络的生命周期延长了 20 h；虽然在网络工作的开始阶段中，文献[15]中的DSLE算法所能实现的2度覆盖率比CNS算法所实现2度覆盖率略高，但是，在网络工作26 h之后，DSLE算法所维持的网络2度覆盖率随着网络生命期的延长迅速降低，而CNS算法可使网络的2度覆盖率保持在50%以上长达52 h。较高的网络覆盖率、较长的网络生命期对保证传感器网络的服务质量是非常重要的。
图4 网络覆盖率与时间的关系
Fig.4 Relationship between k-coverage rate and time
3 结论
(1) 提出一种基于节点序列的覆盖算法；讨论如何判断网络的1度覆盖情况，而且可以调整传感器节点的感应半径以解决覆盖漏洞的问题。
(2) 对覆盖度k＞1，即网络多度覆盖情况的判断问题进行研究并提出解决k度覆盖漏洞的方案，从而动态提高网络的k度覆盖率。
参考文献：
[1] Megerian S, Koushanfar F, Potkonjak M, et al. Coverage problems in wireless ad-hoc sensor networks[C]//Proceedings of IEEE International Conference on Computer Communications (INFOCOM). Anchorage: IEEE Press, 2001: 1380-1387.
[2] 文戈, 王国军, 过敏意. 无线传感器网络中基于Voronoi图的覆盖和连通综合配置协议[J]. 传感器技术学报, 2007, 20(10): 2294-2302.
WEN Ge, WANG Guo-jun, GUO Min-yi. A Voronoi diagram-based integrated protocol for coverage and connectivity configuration in wireless sensor networks[J]. Chinese Journal of Sensors and Actuators, 2007, 20(10): 2294-2302.
[3] Cardei M, WU J. Energy-efficient coverage problems in wireless ad-hoc sensor networks[J]. Journal of Computer Communications on Sensor Networks, 2006, 29(4): 413-420.
[4] He X, Yin K, Gui X. The area coverage algorithm to maintain connectivity for WSN[C]//Proceedings of IEEE International Conference on Computer and Information Technology. Atlanta: IEEE Computer Society Press, 2009: 81-86.
[5] Liu D. On connected area coverage sets in wireless sensor networks[C]//Proceedings of International Conference on Mobile Technology, Applications, and Systems. Singapore: ACM Press, 2007: 226-229.
[6] Xing X, Wang G, Wu J, et al. Square region-based coverage and connectivity probability model in wireless sensor networks[C]// Proceedings of International Conference on Collaborative Computing: Networking, Applications and Worksharing (CollaborateCom). Washington DC: IEEE Press, 2009: 1-8.
[7] Cardei M, Du D. Improving wireless sensor network lifetime through power aware organization[J]. Wireless Networks, 2005, 11(3): 330-340.
[8] Zorbas D, Glynos D, Kotzanikolaou P, et al. Solving coverage problems in wireless sensor networks using cover sets[J]. Ad Hoc Networks, 2010, 8(4): 400-415.
[9] Chen A, Lai T H, Xuan D. Measuring and guaranteeing quality of barrier-coverage in wireless sensor networks[C]//Proceedings of International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc). Hong Kong: ACM Press, 2008: 421-430.
[10] Hefeeda M, Bagheri M. Randomized k-coverage algorithms for dense sensor networks[C]//Proceedings of IEEE International Conference on Computer Communications (INFOCOM), Anchorage: IEEE Press, 2007: 2376-2380.
[11] Huang C, Tseng Y. The coverage problem in a wireless sensor network[C]//Proceedings of International Conference on Wireless Sensor Networks and Applications. New York: ACM Press, 2003: 519-528.
[12] Wang X, Xing G, Zhang Y, et al. Integrated coverage and connectivity configuration in wireless sensor networks[C]// Proceedings of International Conference on Embedded Networked Sensor Systems. Los Angeles: ACM Press, 2003: 28-39.
[13] Shen X, Chen J, Sun Y. Grid scan: A simple and effective approach for coverage issue in wireless sensor networks[C]// Proceedings of IEEE International Conference on Communications (ICC). Istanbul: IEEE Press, 2006: 3480-3484.
[14] Zhong Z, Zhu T, Wang D, et al. Tracking with unreliable node sequences[C]//Proceedings of IEEE International Conference on Computer Communications (INFOCOM). Rio de Janeiro: IEEE Press, 2009: 1215-1223.
[15] Li J, Kao H. Distributed k-coverage self-location estimation scheme based on Voronoi diagram[J]. IET Communications, 2010, 4(2): 167-177.
(编辑 陈爱华)
收稿日期：2010-07-07；修回日期：2010-10-04
基金项目：湖南省杰出青年科学基金资助项目(07JJ1010)；教育部新世纪优秀人才支持计划项目(NCET-06-0686)
通信作者：王国军(1970-)，男，湖南长沙人，教授，博士生导师，从事可信计算、移动计算、普适计算和软件工程研究；电话：0731-88877711；E-mail: csgjwang@mail.csu.edu.cn
