8-WSNs中基于Voronoi图的分布式覆盖协议

Vol.34 No.9 Computer Engineering · 网络与通信 ·

文章编号：1000—3428(2008)09—0145—03

文献标识码：A

2008年5月

May2008

中图分类号：TP393

WSNs中基于Voronoi图的分布式覆盖协议

文 戈，王

(中南大学信息科学与工程学院，长沙 410083)

摘 要：研究网络随机部署情况下的覆盖问题，提出基于Voronoi图的分布式覆盖协议。采用分布式节点冗余判断算法来判断传感器节点自身的冗余性，据此对节点进行相应的职能调度。当网络中节点的通信半径大于或等于其感应半径的2倍时，该协议能达到网络完全覆盖及连通的要求。通过该协议的推广，满足了覆盖度动态变化的要求，保证网络的k-度覆盖。 关键词：无线传感器网络；Voronoi图；覆盖；连通

Distributed Coverage Protocol Based on Voronoi Diagram

in Wireless Sensor Networks

WEN Ge, WANG Guo-jun

(School of Information Science and Engineering, Central South University, Changsha 410083)

【Abstract】This paper focuses on the coverage issue in randomly deployed Wireless Sensor Networks(WSNs) and proposes a Voronoidiagram-based distributed coverage protocol. The protocol adopts a distributed eligibility algorithm for detecting redundancy of sensor nodes andscheduling their duties accordingly. Itcan achieve both coverage and connectivity when the communication range of sensor nodes is at least twicethe sensing range of sensor nodes. It is extended to maintain k-coverage to handle the case of dynamic change of coverage degree. 【Key words】Wireless Sensor Networks (WSNs); Voronoi diagram; coverage; connectivity

无线传感器网络(Wireless Sensor Networks, WSNs)是目前计算机科学与技术领域内的一个热门研究课题。国内外学术界、工业界以及军事部门对该领域投入了大量的科研资金和力量，试图解决其应用基础难题，覆盖问题就是其中一个基本问题。本文基于目前无线传感器网络研究中的基本假设，将网络覆盖问题的解决划分为网络的初始化阶段和网络平稳运行阶段。 第1阶段提出的协议采用基于概率的初始化算法，使网络快速达到覆盖要求。 第2阶段采用一个已存在的、高效的、基于局部Voronoi图的判断冗余的算法，将其与节点自调度方案相结合，以分布式的方式来维护网络的覆盖度。 杂度是O(N 3)。 文献[2]提出了基于局部Voronoi图的冗余节点消除算法(RSE)，节点运用该算法来判断在1-度覆盖要求时自身是否冗余，算法复杂度是O(NlogN)。但该文献没有从整个生命期的角度考虑节点职能调度问题，在保持网络覆盖阶段采取的是活跃节点维护更新已构建的局部Voronoi图的方式。当节点从休眠状态变为活跃状态、有节点死亡或加入时，为了修改局部Voronoi图，活跃节点需要消耗较多的能量。 本文结合以上2个协议和算法的优点，以节能、快速作为重要指标来优化整个网络覆盖协议。 2 基本假设和基本概念 本文的工作基于如下基本假设： (1)无线传感器节点的通信模型和感应模型都是圆盘模型，即通信范围和感应范围呈圆盘状。 (2)网络中的节点是同构的，所有节点的感应范围和通信范围是一样的。 (3)每个节点都知道自己的地理位置信息。 (4)Rc≥2Rs。 根据文献[1]给出的定理(Rc≥2Rs时，如果网络1-度覆盖给定凸区域，则在该区域中网络是连通的)，在给出第4个假设后，只要覆盖协议能够保证网络对给定区域的1-度覆盖，基金项目：国家自然科学基金资助项目(60740440032)；教育部2006年度新世纪优秀人才支持计划基金资助项目(NCET-06-0686) 作者简介：文 戈(1981－)，男，硕士研究生，主研方向：无线传感器网络；王，教授、博士、博士生导师

收稿日期：2007-05-29 E-mail：csgjwang@mail.csu.edu.cn

1 相关工作 无线传感器网络的部署方式分为确定部署和随机部署 2种。在有大量传感器节点或网络部署地域不适合人工部署时，通常采用随机的方式来部署网络，因此，随机部署的无线传感器网络的覆盖问题非常重要。对于随机部署的无线传感器网络，通常会布撒大量的无线传感器节点，因此，有必要进行节点的职能调度，即在保证网络覆盖要求的前提下让一部分节点活跃，而大部分节点休眠。同时，由于节点数目较多，因此采用分布式算法或协议成为了首选。 文献[1]的覆盖配置协议(CCP)利用节点的位置信息进行分布式的节点职能合格性判断，合格者为活跃节点，不合格者为休眠节点。它证明了当无线传感器网络中节点的通信半径大于或者等于感应半径的2倍时，如果网络1-度覆盖给定凸区域，则在该区域中网络是连通的。文献[1]将协议推广到可以满足多度覆盖的要求，但节点职能合格性判断算法的复

—145—

就能保证网络的连通性。而且实际应用中大部分节点确实满足这个假设条件。 为了便于后文描述，这里对感应邻居、Voronoi邻居以及2-Voronoi图的基本概念说明如下。 定义1 当2个传感器节点的覆盖圆盘(覆盖范围)相交，则称这2个节点互为感应邻居。 定义2 当2个传感器节点所形成的2个Voronoi多边形共边，则称这2个节点互为Voronoi邻居。 定义3 传感器节点s的2-Voronoi图是由节点s的Voronoi邻居构成的，构造该Voronoi图时是将节点s自身排除在外的。节点s的2-Voronoi顶点(2-VV)是节点s的2-Voronoi图的顶点。节点s的2-Voronoi交点(2-VIP)是节点s的2-Voronoi图中的边与节点s的覆盖圆周的交点。 定理1[2] 当且仅当传感器节点s的全部2-Voronoi顶点和2-Voronoi交点被节点s的Voronoi邻居覆盖，则节点s是冗余节点。 阈值Pt，则设置该节点将要转入活跃状态；否则设置该节点将要转入侦听状态并立即进入侦听状态。但在进入活跃状态前，要先随机生成一个回退时钟，在时钟过期前，该节点一直侦听。倘若在回退时钟过期前侦听到一个ACTIVE消息(该消息是由新进入活跃状态的节点发送的1跳范围的广播消则这个节点需要判断发送者与自己的距离是否小于节点息)，感应半径Rs。如果小于Rs，则该节点将要转入睡眠状态，并将消息发送方添加到感应邻居集合SN(s)中；如果大于Rs，则进一步判断消息发送方与自己的距离是否小于2Rs。如果小于2Rs，则将消息发送方添加到SN(s)中；否则，继续侦听。在时钟超时后，该节点正式转入之前设置的转入状态。 在第2阶段中，本文提出VDCP的覆盖维护算法。CCP[1]假设网络初始时所有的节点都是活跃的，但VDCP假设所有的节点都是侦听状态。这两者的区别是：所有的活跃节点都将主动发送消息，而且网络初始化时，每个活跃节点必然发送广播消息告知所有1跳范围内的邻居其基本信息(如地理位置信息等)；但是侦听状态的节点只接收消息而不主动发送消息。因此，本文对文献[1]的节点职能调度方案做了一定的改动成为覆盖维护算法，以适应VDCP的要求。 覆盖维护算法中节点有5种状态：休眠，侦听，加入，活跃以及退出状态。覆盖维护算法是如下调度节点状态的： (1)处于休眠状态中的节点会在休眠时钟Ts超时后，启动侦听时钟Tl，然后进入侦听状态。 (2)处于侦听状态的节点如果在侦听时钟Tl超时之前收到来自其Voronoi邻居集合VN(s)中所有节点的Beacon消息，则该节点启动休眠时钟Ts并转入休眠状态。否则，在Tl超时之后，它要用节点冗余判断算法判断自身是否冗余，如果不是冗余节点，则启动加入时钟Tj并进入加入状态；否则启动休眠时钟Ts并转入休眠状态。 (3)处于加入状态的节点如果在加入时钟Tj超时之前收到ACTIVE消息，则先判断消息发送者是不是自己新的感应邻居，如果是，该节点要重新判断自身冗余性；如果发现自己是冗余节点，则启动休眠时钟Ts并转入休眠状态；如果消息发送者不是该节点新的感应邻居或者该节点在调用节点冗余判断算法后发现自己仍然不是冗余节点，则该节点在加入时钟Tj超时之后会广播一个ACTIVE消息并转入活跃状态。 (4)处于活跃状态的节点需要周期性地广播Beacon消息。当活跃节点收到一个ACTIVE消息并发现发送者是其新的感应邻居，它就重新计算自身冗余性；如果它发现自己变成了冗余节点，则启动退出时钟Tw并进入退出状态。 (5)处于退出状态的节点如果在Tw超时之前收到了SLEEP消息，它先要查看消息发送方是否为自己的Voronoi邻居，如果是，那么它须重新评估自身冗余性；如果它发现自己已不是冗余节点，则取消Tw并返回活跃状态；否则，它会在Tw超时之后，广播一个SLEEP消息，启动Ts并转入休眠状态。 无论是Beacon消息、ACTIVE消息还是SLEEP消息，它们都必须包含发送者的地理位置信息，而且可以包含具体应用或其他基于本协议的上层协议中需要携带的一些信息(例如剩余能量信息等)。 所有的非休眠节点都要对自己接收到的这3类消息进行处理，根据这些消息来维护自己的感应邻居集合SN(s)和Voronoi邻居集合VN(s)。 3 基于Voronoi图的分布式覆盖协议(VDCP) 在很多应用中要求无线传感器网络能够完全监控其所布撒的区域。给定一个平面区域，如果其中任意一个物理位置都至少落在一个传感器节点的感应范围之内，则这个区域被1-度覆盖。网络一旦部署后，必须控制网络的拓扑结构使网络完全覆盖给定区域，有时只要求1-度覆盖即可，但有的应用要求达到多度覆盖。本节针对1-度覆盖要求提出一个新的分布式覆盖协议，下文将其推广到多度覆盖的情形。 无线传感器网络一旦被部署，就需要让其尽快达到覆盖要求，同时还要以能量高效的方式(如让尽可能多的节点休眠，用尽可能少的通信量交换局部信息等)来调度管理节点的职能，从而延长整个网络的生命期。 如果把覆盖当作一个过程来看，那么这个过程可以分成网络的初始化和网络的稳定运行2个阶段。前一阶段要尽可能快地完成，这样整个网络就可以尽早执行其任务；而后一阶段，则应该使网络运行得稳定，即不要频繁地改变网络的拓扑结构。在这2个阶段中，如果能尽量减少不必要的信息交换，就能节省很多能量，这是因为通信是整个节点运行过程中单位时间消耗能量最多的行为。覆盖协议需要达到2个要求： (1)从应用需求出发满足网络覆盖要求； (2)从网络节能角度出发选出尽可能少的节点担任活跃节点完成给定任务。 本文提出的VDCP就是根据以上要求来设计的。该协议分成上面提到的2个阶段，由3个算法组成，其中，一个算法叫做节点冗余判断算法，它贯穿2个阶段，本文直接使用文献[2]提出的RSE算法，其基本思想如下：节点s在收集到其感应邻居信息后，构造一个基于这些信息的局部Voronoi图，该图是由包括节点s及其感应邻居在内的Voronoi图；通过该图找到节点s的Voronoi邻居，再由其Voronoi邻居构造一个2-Voronoi图，该图是不包括节点s的；最后根据节点s的这个2-Voronoi图找到全部2-Voronoi顶点和2-Voronoi交点，再根据定理1判断该节点是否冗余。 针对第1阶段的要求，本文提出快速初始化算法，其基本思想是，在部署网络的时候，每个传感器节点的初始状态为侦听状态，而其将要转入的状态未知，并且每个节点随机生成一个随机数。如果这个随机数的值小于一个预先设定的 ——146

VDCP协议有如下几个特点： (1)通过设定所有的节点在初始时是侦听状态，利用生成随机数的方法来选出第一批活跃节点。这些节点在经过一个随机的回退时间后，如果最终进入活跃状态，就发送ACTIVE消息，以表明自己的地理位置信息和状态。与传统的假设所有节点初始时都是活跃节点的方法相比，本文提出的方法减少了大量节点都需要发送广播消息而造成的通信冲突以及由此带来的时延，较快地完成了初始化。VDCP可以在很短的时间内使网络基本达到覆盖要求并开始工作。另外让准备进入活跃状态的节点在收到ACTIVE消息后判断消息发送者和自己的距离是否小于Rs，如果是，则该节点将要转入睡眠状态，目的是使随机产生的第一批活跃节点之间的感应范围重叠较小。这样在一定程度上提高了能量的有效性。 (2)在整个运行阶段，除了前述的一个特殊情况外，活跃节点一旦确定后基本会持续工作到能量耗尽或者出现故障。这样一来整个网络的拓扑结构会比较稳定，减少了网络在维护拓扑结构上的通信开销。 (3)本协议将很多本来需要靠大量节点通信完成的工作转变为只进行少量的通信但须进行一定的计算来完成的工作。由于本协议采用了RSE算法作为节点冗余判断算法，因此计算速度相对其他协议得到提高而且相应的能量消耗会大大减小。 5 模拟分析 为了评价VDCP的性能，本文在Rc≥2Rs的条件下对VDCP与CCP进行了模拟，将给定的区域划分成1 m×1 m的小方格，如果小方格的中心被覆盖住，则认为整个小方格被覆盖住了。因此，覆盖率被定义成被至少一个无线传感器节点覆盖住的小方格数目与整个区域的小方格总数之比。本文的模拟不考虑信道出错的情况。 给定一个50 m×50 m的区域，假设在该区域里均匀随机在模布撒了感应半径为10 m的节点组成的无线传感器网络。拟过程中，在给定的覆盖度要求和给定的网络节点数目下，都随机生成100个不同的网络初始拓扑。 覆盖度的要求从1-度变化到3-度，而网络节点的数目从100增加到1 000，变化步长为100。从图1可以看出，在1-度、2-度、3-度覆盖要求下，在节点总数增长时，CCP和VDCP的活跃节点数目基本保持稳定。但是VDCP所需的活跃节点要少于CCP协议，这意味着VDCP可以让更多的节点进入休眠状态，从而为整个网络节省了能量消耗。 6060CCP/3-度覆盖活跃节点数目The number of active nodesVDCP/3-度覆盖4040CCP/2-度覆盖VDCP/2-度覆盖4 协议的推广 在实际应用中很可能保证网络的1-度覆盖无法满足应用的需求，而且由于应用中事件的发生或者环境的变化会要求覆盖度动态变化。本文实现多度覆盖的方法根据应用需求的不同将略有差别。 如果在开始时网络只需要1-度覆盖，那么在达到1-度覆盖要求时产生的活跃节点都给自己标上一个标记，如“1”表明自己是第1组的。如果随着事件的发生或者环境的改变网络的覆盖要求发生了变化(如要求3-度覆盖)，那么处于侦听状态的节点会采用前述的快速初始化方法，随机生成活跃节或“3”点并给自己随机分组，这些节点会分别给自己标上“2”的标记，表明自己是第2组或第3组的成员。 其他产生的随机数大于预定阈值而没能使自己成为活跃节点的非休眠节点，根据自己收到的ACTIVE消息或者Beacon消息以及包含在这些消息中的发送者的地理位置信息、组号等来判断自己是否冗余。 当它发现自己在某个组来说是不冗余的，那么它就竞争成为这个组的一员。每个组都将使得网络达到1-度覆盖要求，从而3个组都工作时使网络达到3-度覆盖要求。 如果一开始网络就要求达到k-度覆盖，那么在初始化阶段就随机生成k个活跃节点分组，每个组的成员都给自己标上组号。其他节点将根据这些活跃节点来判断自己可以加入哪个组来保证这个组达到1-度覆盖要求，从而最终保证网络达到k-度覆盖的要求。

2020CCP/1-度覆盖VDCP/1-度覆盖00001002002003003004004005005006006007007008008009009001 0001000100The total number of nodes节点总数 图1 VDCP和CCP在同样条件下需要的活跃节点数目比较 6 结束语 基于Voronoi图的分布式覆盖协议结合了现有协议的优点，能够达到节能和1-度乃至多度覆盖的要求。在Rc≥2Rs的条件下，该协议不仅使得网络能达到覆盖要求，还能保证网络的连通性。下一步的研究方向是在Rc<2Rs的条件下，应用该协议也能使网络达到要求的覆盖度，并且保证网络的连通性。 参考文献

[1] Xing Guoliang, Wang Xiaorui, Zhang Yuanfang, et al. Integrated

Coverage and Connectivity Configuration for Energy Conservation in Sensor Networks[J]. ACM Transactions on Sensor Networks, 2005, 1(1): 36-72.

[2] Carbunar B, Grama A, Vitek J, et al. Redundancy and Coverage

Detection in Sensor Networks[J]. ACM Transactions on Sensor Networks, 2006, 2(1): 94-128.

—147—