第28卷第9期 电 子 与 信 息 学 报 V ol.28No.9 2006年9月 Journal of Electronics & Information Technology Sept.2006
无线传感器网络部署及其覆盖问题研究
刘丽萍 王 智 孙优贤
(浙江大学 工业控制技术国家重点实验室 杭州 310027)
摘 要 无线传感器网络是近几年发展起来的一种新兴技术，在条件恶劣和无人坚守的环境监测和事件跟踪中显示了很大的应用价值。节点部署是无线传感器网络工作的基础，对网络的运行情况和寿命有很大的影响。部署问题涉及覆盖、连接和节约能量消耗3个方面。该文重点讨论了网络部署中的覆盖问题，综述了现有的研究成果，总结了今后的热点研究方向，为以后的研究奠定了基础。 关键词 无线传感器网络，部署，覆盖
中图分类号: TP393 文献标识码: A 文章编号:1009-5896(2006)09-1752-06
Survey on Coverage in Wireless Sensor Networks Deployment
Liu Li-ping Wang Zhi Sun You-xian
(National Laboratory of Industrial Control Technology Zhejiang University, Hangzhou 310027, China)
Abstract Wireless Sensor Network (WSN), which is a novel class of computing and a new spot of information technology, is envisaged in application such as hostile environment surveillance and void event tracking. One fundamental issue in WSN is the deployment issue, which affects the performance and lifetime of the network. The deployment issue in WSN includes coverage, connectivity and energy-efficiency. The coverage problem in WSN is discussed in this paper. Therefore, the future work is presented.
Key words Wireless sensor networks, Deployment, Coverage
1 引言
无线传感器网络是随着无线通信和嵌入式计算技术、传感器技术、微机电技术的发展而发展起来的一种新兴的信息获取技术。网络中的每个节点都含有一个体积小、价格便宜、低能耗、支持短距离通信的多功能传感器。每个传感器节点具备信号采集、数据处理、相互通信的功能，直接嵌入到相应的设备或环境当中，具有很大的灵活性和移动性。基于这些优点，无线传感器网络在军事、环境监测、医疗卫生、智能家庭等方面有很大的潜在应用价值(表1所示) ，尤其在无人监测或环境恶劣情况下的事件监测和事件跟踪中显示了很大的优势。同时，在商业方面也呈现出很好的应用前景(办公建筑的环境控制、汽车防盗、库存管理、控制产品质量等)
[1-3]
根据无线传感器网络的应用，它的任务类型可以分为：环境数据收集、安全性监控、事件跟踪以及三者的混合任 务[4]。在应用现场，需要通过适当的调度算法来完成节点的部署。不管无线传感器网络要完成哪种任务，首先要解决节点的部署问题，它直接影响着监测结果的准确性和全面性。合理有效的节点部署方案可以大大减少网络搭建时间，快速覆盖目标区域，而且通过协调控制还可以延长网络寿命，适应变化的拓扑结构。本文从这一角度出发，探讨了无线传感器网络节点部署的热点问题，指出了节点部署问题的研究方向和面临的挑战；就节点部署中的覆盖问题进行了深入的讨论，并在全面和系统地归纳总结已有的研究成果的基础上，提出了无线传感器网络覆盖问题的研究方向，为进一步深入研究奠定了坚实的基础。
。
表1 无线传感器网络的应用及应用前景
Tab.1Wireless sensor networks applications
领 域 任务使命
友军兵力、装备、弹药调配监视；战区监控；
军事及反恐
敌方军力的侦察；目标追踪；战争损伤评估；
防爆应用
核、生物和化学攻击的探测与侦察。 森林火灾的监测；环境的生物复杂性映射；
环境应用
洪水监测；精密农业。
人体生理指标的远程监测；医院内医生和患者
保健应用
的跟踪；药物管理。
家庭应用 家居自动化；居住环境智能化。 其它商务 汽车防盗；交互式博物馆；库存管理控制； 应用 车辆跟踪与控制。
2 体系结构
无线传感器网络是由大量无处不在的、具有无线通信与计算能力的微小传感器节点构成的自组织分布式网络系统，是能根据环境自主完成指定任务的“智能”系统。无线传感器网络不同于普通的Ad hoc网络，前者是以收集和处理信息为目的，而后者通常以通信为目的。与传统的传感器网络相比，无线传感器网络具有节点分布密集、自组网络、资源受限、拓扑变化频繁、多跳方式通信等特点。
应用中，无线传感器网络一般有两种结构：同构型[1]和异构型结构[5]。典型的同构型结构如图1所示：监控领域的节点，对感兴趣的数据进行采集、处理、融合，并通过主节
2005-01-17收到，2005-07-22改回 国家自然科学基金重点项目（NSFC-60434030），中法先进研究计划资助项目（PRA SI01-04，SI03-02）和浙江省院士基金" 无线传感器网络关键技术及开发平台" （2004.01-2004.12）资助课题
第9期 刘丽萍等：无线传感器网络部署及其覆盖问题研究 1753 点路由到基站，用户可以通过卫星或因特网进行查看、控制。典型的异构型结构如图2所示：传感器节点自组织成子网，每个子网通过网关同数据库中心连接，终端用户通过数据中心对各个子网进行监控[3]。
的是上层面向应用的任务分配和协调控制问题。应用层的协调控制大致可以分为节点部署、信息处理、动态管理3大模块。通过有效的节点部署方案和信息处理技术可以大大减少系统的能量消耗。节点部署是无线传感器网络应用的基础，节点初始部署的优劣直接影响着网络以后的性能和寿命。信息处理技术通过相关数据的融合处理减少网络的通信量，进而节约了系统的能量。动态管理是在系统运行过程中根据实际需求和剩余能量，综合考虑服务质量和能量均衡延长网络寿命而进行的一些动态的调整。
图1 无线传感器网络同构型结构
Fig.1 Structure of a homogeneous sensor network
3 节点部署
节点部署，即通过一定的算法布置节点，优化现有的网络资源，以期网络在未来的应用中获得的最大利用率或单个任务的最少消耗量。节点部署是传感器网络进行工作的第一步，是网络正常工作的基础，只有把传感器节点在目标区域布置好，才能进一步进行其它的工作和优化。 3.1 节点部署的评价指标
节点部署的好坏直接影响着网络的寿命和性能。有效的部署方案，依赖于一套完整的节点部署评价体系。结合无线传感器网络的应用特点和系统特性[4]，我们认为评价无线传感器网络的节点部署时，主要考虑以下3个指标。
图2 无线传感器网络异构型结构
Fig.2 Structure of an inhomogeneous sensor network
(1) 采集信息的完整性和精确性 要求节点能够覆盖目标区域，并且综合考虑节点的冗余和信息的容错，对传感器节点要进行动态的管理，以保证采集信息的完整性和精确性。
(2) 信息可传输性 要求保证采集到的信息能够准确及时的传递到信息的使用终端。
(3) 系统耗能(即网络寿命) 由于无线传感器网络与其它网络的最大区别在于能量限制的问题，要求在完成任务的前提下最大限度的延长整个网络的寿命。
从上面的3个指标出发，在节点部署时主要考虑下面3方面的问题。
(1) 覆盖(Coverage problem) 覆盖考虑的两个问题是：(a)初始传感器节点的布置是否覆盖了整个目标区域；(b)这些节点能否完整准确地采集目标区域的信息。结合无线传感器网络的特点，主要从下面3种情况考虑这两个问题，(a)初始覆盖：假设无线传感器网络随着监测工作的进展不发生变化，根据最初的任务需求对目标区域进行覆盖，这是一个静态的覆盖过程；(b)动态调整：考虑拓扑变化和能量消耗的因素，网络应用过程中需要对原有的节点部署进行动态调整，这是动态适应实际需求的覆盖过程；(c)移动站点辅助覆盖：将移动站点或移动机器人引入无线传感器网络部署中，应用于节点密度稀疏或大部分节点能量不足的应用中。
(2) 连接(Connectivity problem) 连接考虑的问题是：节点间的连接情况能否保证采集的信息能够准确地传递给基站。围绕这个问题，也可以从两方面展开，(a)纯连接(Pure connectivity) ：不论网络是否运行，都要保证网络任意两节
从网络各部分功能的角度出发，网络可以分为基础通信结构、支撑技术和应用层3部分。基础通信结构由底层向上包括物理层、数据链路层、路由层、传输层。支撑技术包括时间同步、节点定位、系统管理等一些中间件技术。上层即应用层包括节点部署、动态管理、信息处理等几个部分。其各部分功能的体系结构图如图3所示。
图3 无线传感器网络的功能体系结构图 Fig.3 Architecture of wireless sensor networks function
节约系统能量，延长网络寿命，适应变化的拓扑结构是目前无线传感器网络设计追求的目标，其内容涉及无线传感器网络结构设计的各个部分，也贯穿无线传感器网络应用过程中的每一个阶段。在节点间协同工作中，最具有普遍意义
1754 电 子 与 信 息 学 报 第28卷 点是连接，这是网络运行的基础；(b)路由连接(Routing algorithm based connectivity)：指在网络运行时，按照某种特定的算法实现任意两点间的连接，是对纯连接的优化[6]。不同的路由算法，对连接效果也有很大的影响。
(3) 节能(Energy efficiency problem) 节能主要考虑两个问题：(a)网络部署时传感器节点消耗的能量少；(b)网络在使用过程中能量的平均消耗量最低。前者主要是减少部署时能量的消耗，后者是从能量平衡的角度考虑延长网络寿命。
在下面的章节里，我们重点讨论无线传感器网络部署中的覆盖问题，在综述研究现状的基础上，提出适应无线传感器网络特点的覆盖问题的热点研究方向。对于部署问题的另外两个关键部分：连接和节能问题，我们会在后面的文章中作重点讨论。
就越好。
U =
1N
∑U i (2) N i =1
2
⎛1K i ⎞
U i =⎜∑(D i , j −M i ) 2⎟ (3)
⎜K j =1⎟⎝i ⎠
式中U 代表均匀性，N 是节点总数目，K i 表示第i 个节点的邻居节点个数，D i , j 表示第i 个节点与第j 个节点之间的距离，M i 表示第i 个节点与其传感范围相交的所有节点的距离的平均值。
(4) 覆盖时间 是指目标区域被完全覆盖或者跟踪时，所有工作节点从启动到就绪所需要的时间(在有移动节点的覆盖中是指移动节点移动到最终位置所需要的时间) 。覆盖时间在营救或者突发事件监测中是一个很重要的节点覆盖衡量指标，可以通过算法优化和改进硬件设施来减少覆盖时间。
4 覆盖问题
在传感器网络中，每个传感器的传感范围(即传感器所能感知的最大物理空间，为研究方便，传感器的传感范围通常被假设为圆形区域) 有限，为保证整个区域都在监测范围之内，需要按照一定的算法在目标区域布置传感器，即覆盖问题，它是整个任务得以继续进行的基础。覆盖问题从最初的画廊问题(线性规划问题) 发展到Ad hoc网络的覆盖问题，以及现在考虑能量消耗的无线传感器网络的覆盖问题，甚至出现了移动站点辅助的覆盖方案。当然随着实际应用的发展，还会出现更多的适合实际需求的有效覆盖方案。 4.1 基本概念
目前在传感器网络覆盖问题的研究中，经常涉及到邻居节点，覆盖程度，均匀性，时间和距离、覆盖重数等几个基本概念[7]。实际应用中，一些学者会根据不同的应用具体化这些概念，致使数学公式不尽相同，这里给出如下的通用定义。
(1) 邻居节点 在节点的传感范围内的节点，一对邻居节点的传感范围一般会相交或者相切，即邻居节点的传感范围能够连接起来，这样才能完全覆盖被监测区域。
(2) 覆盖程度 作为衡量传感器网络节点部署的一个指标，覆盖程度是Gage 最先提出来的，它一般定义为所有节点覆盖的总面积与目标区域总面积的比值。其中节点覆盖的总面积取集合概念中的并集，所以覆盖程度一般是小于或等于1的。
C =
i =1N
(5) 平均移动距离 移动节点的覆盖方案中，每个节点到达最终位置所移动距离的平均值。这个距离越小，系统消耗的总能量就越少。在实际应用中，不仅要减少节点移动的平均距离，而且要尽量减少节点间能量消耗的差异。因此距离可以用节点移动的平均距离和标准方差来表示更为准确，即每个节点移动的距离与整个网络中节点移动平均距离的偏差来表示(可以根据式(2)给出定义公式) 。这个标准差越小，则系统中节点消耗的能量就越均衡，不易导致网络因为某个节点能量的过多消耗而中断。
(6) 覆盖重数 最近有学者基于需要较强监测能力或较高容错率的应用环境，提出了多重覆盖[8]的概念，即某一事件是否被k 个节点覆盖。这与上面的覆盖程度并不矛盾，只是关注的侧重点不同。前者关注的是对目标区域的整体覆盖情况，后者则侧重于局部的重点观测。覆盖重数表示某个区域的覆盖的冗余程度，如果这个区域在K 个节点的传感覆盖范围之内，那么它的覆盖重数就是K 。具体的数学表达式为
N
K A =∑K i ， K i =
i =1
{
1 ， A ⊆A i
(4)
0 ， A ∩A i ≠A
这里K A 表示A 区域的覆盖重数，A i 为i 节点的传感范围，K i 表示第i 个节点传感范围是否覆盖A 区域，覆盖时K i 为
1，否则为0。 4.2 研究现状
在多机器人系统中，Gage 首先提出了覆盖问题的基本概念，并根据监测区域的侦察方式，将覆盖问题分为地毯覆盖(Blanket coverage)，障碍覆盖(Barrier coverage)，扫描覆盖(Sweep coverage)，3类[9]。但是无线传感器网络的覆盖问题
U A i A
(1)
其中C 代表覆盖程度，A i 表示第i 个节点的覆盖面积，N 代表节点的数目，A 表示整个目标区域的面积。
(3) 覆盖均匀性 节点均匀分布的传感器网络在工作时，能量的消耗相对来讲会均衡一些，这样可以避免过早出现失效节点，即起到了平衡能量负载的作用。均匀性一般用节点间距离的标准差来表示，标准差的值越小则覆盖均匀性
与以往的覆盖问题相比较，最大的区别在于网络的动态性上，网络的动态性涉及网络的初始部署和运行过程中的调整。
首先，无线传感器网络运行过程中，要尽量节约系统的整体能量；传感器节点的能量也有很大区别，需要通过适当的手段对节点的能量消耗和剩余能量分布的均衡性进行动
第9期 刘丽萍等：无线传感器网络部署及其覆盖问题研究 1755 态的调整。
其次，由于能量和通信的原因，会出现一些失效节点，这些节点所在的区域需要重新覆盖。
最后，在监测过程中，某些区域的覆盖程度和传感器采集频率也要进行调整，监测的重点区域也会发生改变，也需要对原有的覆盖结果进行相应的调整。
因此本文按无线传感器网络的使用周期，将覆盖问题划分为初始覆盖、动态调整和移动站点辅助覆盖几部分，并分别进行了探讨。
4.2.1初始覆盖 初始覆盖是假设无线传感器网络随着监测
4.2.2 动态调整 初始覆盖问题假设环境模型是可用的，进
而能够找到确定性解，但是在实际的无线传感器网络中不可能获得完整的环境信息；同时在大范围内获得全局信息而消耗的通讯能量也很巨大(这一点在无线传感器网络中是最不可取的) ，节点也会有很长的等待时间，因而不可能获得精确解[16]；加之应用环境恶劣，通信也存在一定的问题；最后，应用环境也有很大的动态性，需要网络进行动态的调整以适应应用的需求。
动态覆盖方案包括两方面的内容：(1)为了节约能量，通过算法控制一些节点的开启和关闭，完成对节点工作状态的调节；(2)适应不同应用的需要，对某些区域进行可变的多重覆盖调整，调整传感器采集的频率。
(A)节点工作状态切换 Liu 等[17]通过对偶空间法确定传
工作的进展不发生变化，根据最初的任务需求对目标区域进行覆盖的方案。与初始覆盖问题息息相关的一个问题就是计算数学中的画廊问题[10]。画廊问题是试图找到能保证画廊中的每一点都能被至少一个警卫观察到的最少警卫的数量，而初始覆盖问题的目的是确定传感器节点能够覆盖整个监测区域所需要的节点分布。将画廊问题的解法引入初始覆盖问题，初始覆盖问题可以在二维空间内进行优化，并且能够得到精确解；但在三维的空间内，覆盖问题抽象成的画廊问题被证明为NP-hard 问题。问题的难点在于单个传感器节点的传感覆盖范围的确定和对整个覆盖问题的影响。后来Meguerdichian 等[11]从覆盖的角度考虑了无线传感器网络中
感器节点的监测范围，根据跟踪的目标在哪些节点的监测范围内，以及目标的移动情况，决定哪些传感器节点负责监测事件。针对栖息环境的监测问题，Cerpa 等[18]提出了利用中心节点负责制的方案。中心节点处于警备状态，负责侦察被监测目标，一旦发现目标便以一定的半径唤醒周围的节点。节点间通过信息传递确定跟踪目标的移动方向、速度及具体位置，当目标已超出节点的监测范围时，节点会自动转入休眠状态。Tian 等[19]提出了自发的检测休眠算法，当节点的邻居节点能够覆盖监测区域时，这个节点就进入休眠状态。在没有监测盲区的情况下，这种算法可以保证100％的覆盖率。但是这种算法中，邻居节点会自发地醒来检测，导致能量的浪费。而文献[20]利用周期性的探测机制(Probing mechanism)实现对覆盖程度的监测。活动节点(通过周期性的唤醒) 在一定范围内广播探测信息并等候一定时间，如果在等待时间内收到其它节点的信息，该节点进入休眠状态；否则，节点就进行监测，直到能量耗尽。这样可以减少文献[19]中节点因为自发唤醒而消耗过多的能量。在这个算法当中，探测范围和唤醒频率一般会间接影响覆盖的程度，而且这种算法存在盲区，不能保证完全覆盖。
(B)覆盖程度调节 在一些实际的监测中不仅需要对监
的传感器定位和覆盖问题，指出覆盖范围是考虑覆盖服务质量的一个基本的性能指标，并且给出了节点固定时解决覆盖问题的计算几何和图论相结合的覆盖算法，这种覆盖算法可以得到较高的覆盖程度。
通过数学方法得到精确解的部署方案，仅适用于小范围规则区域的部署。当目标区域不规则或很大时，许多学者提出通过局部的信息找到次优化方法。Chakrabarty [12]和Meguerdichian [13]通过线性规划的方法，得到保持覆盖的最小
活动(Active)节点集。在保证覆盖程度的基础上，考虑了网络运行时的覆盖均匀性问题。从最小化未覆盖区域(Exposure area) 的角度入手，Meguerdichian
[11，14]
提出了更复杂的覆盖模
型。文献[11]用V oronoi 图和Delaunay 三角测量技术计算了传感器网络中的最差路径和最有效路径，文献[14]提出了寻找最小路径的问题。Couqueur 等[15]提出了传感器网络覆盖的目标是对分布式的监测提供充分的覆盖，可扩展的容错的局部算法更是适合动态环境下的大尺度无线传感器网络，并且具有良好的鲁棒性。Slijepcevic [16]假设节点间是等距离的，提出了一个部署的启发式算法，使传感器节点互相排斥使所有的节点能够覆盖整个研究的区域。
在实际应用中，有些区域或某些部分很重要，如火山监测中的火山口附近，战场上的指挥中心等，为获得较高的可信度，防止节点失效和信息传输失败以及由于周围噪音的干扰导致信息的不准确，Huang 等提出了采用多传感器的多重覆盖方案。然而，目前该方案仅停留在理论研究上，并没有运用到实际应用当中。
[8]
测区域完全覆盖，还要根据实际需要随时改变对某些监测区域的覆盖程度，这时需要覆盖算法根据应用的覆盖要求作相应的调整。例如，文献[21]中需要对每个监测位置进行多节点的覆盖。文献[22]中的跟踪和分类需要更高程度的覆盖。监测时需要较低的覆盖；当有入侵者时，能够自动地调节成与跟踪问题相匹配的较高程度的覆盖。这些覆盖要求依赖于对失效节点的容忍程度，高的覆盖程度对高比例的节点失效有更好的覆盖。Huang 等[8]在应用需要较强监测能力和较高容错率的情况下，提出了k 重覆盖的多项式时间算法。对动态环境下的大尺度无线传感器网络来讲，可扩展的容错的局部算法会更适合，并且具有较好的鲁棒性。Meguerdichian [14]研究了在一定时间周期内沿任意路径以任意速度移动的目标监测问题，使用复分辨技术(Multiresolution technique)与
1756 电 子 与 信 息 学 报 第28卷 Dijkstra 或者Floyd 算法结合的方式给出了覆盖的最短路径。
题的解决有很大的影响。但是，在目前拓扑发现和覆盖问题的研究中，初始分布都是自由部署的。因此改进初始的分布在很大程度上会改善整个网络的使用性能，这是在网络覆盖理论研究上的一个热点方向。
再次，部署中覆盖与连接的关系问题也是目前部署理论研究的热点问题。在无线传感器网络中，节点间一般通过无线射频的方式通信，每个节点具有一定的通信范围(Transmitting range，一般假设为球形，二维空间为圆形) ，
文献[23]在考虑能量优化、硬件精度和测量精度、以及数据查询和处理的基础上，提出了局部面向曝光的覆盖和位置发现算法(Localized exposure-based coverage and location discovery algorithms)，给出了3个移动传感器从密集区域移动
到稀疏区域的分布式协议，并通过试验证明了协议的有效性。
4.2.3 移动站点辅助的覆盖方案 随着移动基站在Ad hoc网
络中研究的进一步深入，很多学者把移动站点、移动机器人引入无线传感器网络的部署当中，出现了移动站点辅助的覆盖方案。
移动站点辅助的方案在环境数据收集或者事件监测过程中，使用移动节点或基站辅助，在固定节点间交换信息，并依据一定的算法进行目标区域覆盖的优化。Winfield [24]提出了网络缺乏连接时，借助移动站点辅助覆盖整个区域的自治分散算法。在固定监测区域收集数据时，使用自由分布的方法；节点增加时，使用递增覆盖算法，使网络的覆盖区域最广。Heo 和Varshney [25]在假设节点可靠、具有移动能力，使用理想的采集和通信覆盖模型的基础上，使用机器人的移动改进拓扑，增加整个系统的寿命；通过渐进方法，节点能够在完成目标区域覆盖的同时，进行自适应的自组。Tan 等[26]研究了多移动小车的无线网络区域覆盖系统，提出了移动传感器网络的分布式模型，并进一步基于该模型提出了连续和衍生的部署算法，使移动机器人能够覆盖更广的区域。在传感器节点自由分布的基础上，Zou [27]等通过内在的部署算法使整个覆盖均匀化，并提出用虚拟力算法可以改进初始自由的覆盖，提高了灵活性。Andrew
[28]
只有在彼此通信范围内的节点能够实现点对点的直接通信，在通信范围外的节点要通过多跳的方式进行通信。通信时也需要通信范围的连通，这样才能保证节点间能够彼此通信，这是连接问题要研究的重要内容。目前对于覆盖与连接关系的研究，文献[29,30]从理论上证明了节点的通信范围大于二倍传感范围的情况下，覆盖问题就包含了纯连接问题，此时在部署中只考虑覆盖问题就可以保证通信。但是当节点的通信范围小于二倍传感范围时，二者的包含关系如何还有待进一步的研究，而且在这种情况下节点间的通信存在严重的干涉，这也是问题研究的难点。
最后，覆盖时的能量优化以及延长网络寿命的覆盖方案也是未来无线传感器网络覆盖问题的新兴研究方向。传感器节点一般靠电池提供电源，工作在无人值守、恶劣的工作环境当中，这就使得能量问题显得尤为重要。在覆盖时除了考虑使用最少的节点总数外，还需要研究节点的传感范围与能量消耗之间的关系，找出合适的传感范围；同时需要研究节点的密度与覆盖性能之间的平衡关系，以及节约单个节点的能量与平衡整个网络能量消耗之间的关系。这些问题都直接影响着网络的寿命，寻求性能与寿命之间的平衡一直是网络研究的热点。
将势场引入移动节点的
无线传感器网络的覆盖问题，通过假设虚拟势场和虚拟受力，利用相关的物理定律作指导达到良好的覆盖效果。
6 结束语
无线传感器网络是近几年发展起来的一种新兴技术，在恶劣条件和无人值守的环境监测和事件跟踪中显示了很大的应用价值。节点部署是无线传感器网络工作的基础，对网络以后的运行情况和网络寿命有很大的影响。覆盖、连接和节能是无线传感器网络的部署问题研究的重点。本文针对部署中的覆盖问题，综述了现有的研究成果，并对今后的热点研究方向进行了讨论，希望对以后的研究有一定的指导作用。
当然，研究部署问题应该综合考虑覆盖、连接和能量消耗几个方面，这是我们以后研究的重点。与此同时，部署问题还依赖于一些支撑技术如时间同步和节点定位技术的发展。
5 热点方向
拓扑结构的变化是无线传感器网络的显著特点，也是从发展角度研究无线传感器网络覆盖问题必须解决的问题。前期的无线传感器网络的覆盖一般是建立两个假设之上的：(1)假设传感器节点固定不动，并且是随机布置的(在网络中，传感器节点多是通过飞行器散播、人工埋置、或火箭弹射等方式随机布置在监测区域[1]。) ；(2)假设传感器节点的数量非常大，以至于认为监测区域的覆盖不是问题。因此，以前的研究没有太多考虑节点数量的优化和拓扑结构的优化。适应多变环境的覆盖研究涉及到覆盖程度的调节、节点采集频率的转换、节点的开启与关闭的调度、邻居节点覆盖范围的判定等等，同时还涉及到工作节点的调度问题，即保证网络完成覆盖的最小节点数目和节点分布问题。这些都是针对无线传感器网络特点，在网络研究方面迫切需要解决的新的研究问题。
另一方面，目前许多学者做的与覆盖有关的工作，通常借用圆覆盖问题、几何问题和受限密码理论中的某种拓扑问题的解决方法。这些问题的研究中，节点的初始分布对于问
[2]
参 考 文 献
[1] Akyildiz I F, Su W, Sankarasubramaniam Y, et al.. Wireless
sensor networks: A survey [J]. Computer Networks, 2002, 38(4): 393-422.
任丰原, 黄海宁, 林闯. 无线传感器网络[J]. 软件学报, 2003, 14(7): 1282-1291.
第9期 刘丽萍等：无线传感器网络部署及其覆盖问题研究 1757
[3]
叶驰, 孙利民, 廖勇. 传感器网络的能量管理[J]. 计算机工程与应用, 2004, 8: 196-198.
[4] Jason Lester Hill. System architecture for wireless sensor
networks[D]. [Ph.D], Computer Science University of California , Berkeley, 11-17: 2003.
[5] Pister K, Hohlt B, Jeong J, et al.. Ivy－A sensor network
infrastructure. 2003. http://www-bsac.eecs.berkeley.edu/ projects/ivy.
[6] Jian N, Chandler S A G. Connectivity properties of radio
telephone network. [A]Mobile and Personal Communi -cations.1993. Seventh IEE European Conference [C], 13-25 Dec 1993: 136-141. [7]
Heo N, Varshney P K. A distributed self spreading algorithm for mobile wireless sensor networks[A]. IEEE Conference on Wireless Communications and Networking, March 16-20, 2003, vol3. 1597–1602.
[8] Huang C-F, Tseng Y-C. The coverage problem in a wireless
sensor network.[A] WSNA03 [C], September 19, 2003, San Diego, CA. 2003: 115-121.
[9] Gage D W. Command control for many-robot systems [A].
AUVS-92, the 19th Annual AUVS Technical Symposium, Huntsville AL[C], June 1992: 22-24.
[10] O'Rourke J. Art gallery theorem and algorithms[M]. New York:
Oxford University Press, 1987.
[11] Meguerdichian S, Koushanfar F, Potkonjak M, et al.. Coverage
problems in wireless Ad-hoc sensor networks [J]. INFOCOM'01, 2001, (3): 1380-1387.
[12] Chakrabarty K, Iyengar S. S, Qi H, et al.. Grid coverage for
surveillance and target location in distributed sensor networks [J]. IEEE Trans. on Computers, 2002, 51(12): 1448-1453.
[13] Bulusu N, Heidemann J, Estrin D. Adaptive beacon placement[A].
in Proceedings of the 21th International Conference on Distributed Computing Systems[C]. Phoenix, AZ, Apr. 2001: 489-498.
[14] Meguerdichian S, Koushanfar F, Qu G, et al.. Exposure in
wireless Ad hoc sensor networks [A]. Proc. of 7th Annual International Conference on Mobile Computing and Networking (MobiCom'01)[C]. July 2001: 139-150.
[15] Couqueur T, Phipatanasuphorn V, Ramanathan P, et al.. Sensor
deployment strategy for target detection [A]. Proceeding of The First ACM International Workshop on Wireless Sensor Networks and Applications, WSNA’02[C], Atlanta, Georgia, USA, September 28, 2002.42-48.
[16] Slijepcevic S, Potkonjak. Power efficient organization of wireless
sensor networks[A]. Communications IEEE International Conference on, 11-14 June 2001, 2: 472 -476 .
[17] Liu J, Cheung P, et al.. A dual-space approach to tracking and
sensor management in wireless sensor networks[A]. WSNA’02[C], Atlanta, Georgia, USA, September 28, 2002: 131-139.
[18] Cerpa A, Elson J. Hamilton M, et al.. Habitat monitoring:
application driver for wireless communications technology [R]. UCLA Computer Science Technical Report 2002, 3, December
2000.
[19] Di Tian, Georganas N D. A node scheduling scheme for energy
conservation in large wireless sensor networks[J]. Wireless Communications and Mobile Computing, 2003, 3(2): 271-290. [20] Ye F, Zhong G., Lu S, et al.. Energy efficient robust sensing
coverage in large sensor networks[R]. UCLA Technical report 2002.
[21] Varshney P. Distributed Detection and Data Fusion[M].
Spinger-Verlag, New York, 1996.
[22] Li D, Wong K, Hu Y H, et al.. Detection, classification and
tracking of targets in distributed sensor networks [J]. IEEE Signal Processing Magazine, 2002, 19(2): 17-29.
[23] Meguerdichian S, Slijepcevic S, Karayan V, et al.. Localized
algorithms in wireless Ad-hoc networks: location discovery and sensor exposure[A]. In ACM Int’l Symp. on Mobile Ad Hoc Networking and Computing (MobiHOC)[C], 2001: 106–116. [24] Winfield A F T. Distributed sensing and data collection via broken
Ad hoc wireless connected networks of mobile robots, in Distributed Autonomous Robotic Systems 4, eds. LE Parker, G Bekey & J Barhen, Springer-Verlag, 2000: 273-282.
[25] Nojeong H, Varshney P K，An intelligent deployment and
clustering algorithm for a distributed mobile sensor network[A]. IEEE International Conference on Systems, Man and Cybernetics, 5-8 Oct., 2003, 5: 4576 -4581.
[26] Jindong Tan, et al.. Multiple vechile for sensor network area
coverage[A]. Proceedings of the 5 th world congress on intelligent control and automation [C]. Hangzhou, China, June 15-19, 2004: 4666-4670.
[27] Zou Y, Chakrabarty K. Sensor deployment and target localization
based on virtual forces [A]. in Proc. IEEE INFOCOM Conference[C], 2003: 1293-1303.
[28] Howard A, Matari´c M J, Sukhatme G S. Mobile sensor network
deployment using potential fields: A distributed, scalable solution to the area coverage problem[A]. The 6th International Conference on Distributed Autonomous Robotic Systems (DARS02)[C], Fukuoka, Japan, June 25-27, 2002: 299-308. [29] Di T, Georganas N D. Connectivity maintenance and coverage
preservation in wireless sensor networks[A]. Electrical and Computer Engineering, 2004. Canadian Conference on[C], 2-5 May 2004, 2 : 1097 -1100 .
[30] Ye F, Zhong G, Lu S, et al.. PEAS: A robust energy conserving
protocol for long-lived sensor networks[A]. The 23rd International Conference on Distributed Computing Systems (ICDCS'03)[C], May 2003: 1-10.
刘丽萍： 女， 1979年生，博士生，研究方向为无线传感器网
络部署、任务分配、数据处理和协调控制.
王 智： 男， 1969年生，工学博士，副教授，主要研究方向为实
时与工业通信、网络控制和传感器网络.
孙优贤： 男， 1940年生，教授，博士生导师，中国工程院院土，
研究方向为复杂系统理论、分布控制系统以及企业综合自动化等.
第28卷第9期 电 子 与 信 息 学 报 V ol.28No.9 2006年9月 Journal of Electronics & Information Technology Sept.2006
无线传感器网络部署及其覆盖问题研究
刘丽萍 王 智 孙优贤
(浙江大学 工业控制技术国家重点实验室 杭州 310027)
摘 要 无线传感器网络是近几年发展起来的一种新兴技术，在条件恶劣和无人坚守的环境监测和事件跟踪中显示了很大的应用价值。节点部署是无线传感器网络工作的基础，对网络的运行情况和寿命有很大的影响。部署问题涉及覆盖、连接和节约能量消耗3个方面。该文重点讨论了网络部署中的覆盖问题，综述了现有的研究成果，总结了今后的热点研究方向，为以后的研究奠定了基础。 关键词 无线传感器网络，部署，覆盖
中图分类号: TP393 文献标识码: A 文章编号:1009-5896(2006)09-1752-06
Survey on Coverage in Wireless Sensor Networks Deployment
Liu Li-ping Wang Zhi Sun You-xian
(National Laboratory of Industrial Control Technology Zhejiang University, Hangzhou 310027, China)
Abstract Wireless Sensor Network (WSN), which is a novel class of computing and a new spot of information technology, is envisaged in application such as hostile environment surveillance and void event tracking. One fundamental issue in WSN is the deployment issue, which affects the performance and lifetime of the network. The deployment issue in WSN includes coverage, connectivity and energy-efficiency. The coverage problem in WSN is discussed in this paper. Therefore, the future work is presented.
Key words Wireless sensor networks, Deployment, Coverage
1 引言
无线传感器网络是随着无线通信和嵌入式计算技术、传感器技术、微机电技术的发展而发展起来的一种新兴的信息获取技术。网络中的每个节点都含有一个体积小、价格便宜、低能耗、支持短距离通信的多功能传感器。每个传感器节点具备信号采集、数据处理、相互通信的功能，直接嵌入到相应的设备或环境当中，具有很大的灵活性和移动性。基于这些优点，无线传感器网络在军事、环境监测、医疗卫生、智能家庭等方面有很大的潜在应用价值(表1所示) ，尤其在无人监测或环境恶劣情况下的事件监测和事件跟踪中显示了很大的优势。同时，在商业方面也呈现出很好的应用前景(办公建筑的环境控制、汽车防盗、库存管理、控制产品质量等)
[1-3]
根据无线传感器网络的应用，它的任务类型可以分为：环境数据收集、安全性监控、事件跟踪以及三者的混合任 务[4]。在应用现场，需要通过适当的调度算法来完成节点的部署。不管无线传感器网络要完成哪种任务，首先要解决节点的部署问题，它直接影响着监测结果的准确性和全面性。合理有效的节点部署方案可以大大减少网络搭建时间，快速覆盖目标区域，而且通过协调控制还可以延长网络寿命，适应变化的拓扑结构。本文从这一角度出发，探讨了无线传感器网络节点部署的热点问题，指出了节点部署问题的研究方向和面临的挑战；就节点部署中的覆盖问题进行了深入的讨论，并在全面和系统地归纳总结已有的研究成果的基础上，提出了无线传感器网络覆盖问题的研究方向，为进一步深入研究奠定了坚实的基础。
。
表1 无线传感器网络的应用及应用前景
Tab.1Wireless sensor networks applications
领 域 任务使命
友军兵力、装备、弹药调配监视；战区监控；
军事及反恐
敌方军力的侦察；目标追踪；战争损伤评估；
防爆应用
核、生物和化学攻击的探测与侦察。 森林火灾的监测；环境的生物复杂性映射；
环境应用
洪水监测；精密农业。
人体生理指标的远程监测；医院内医生和患者
保健应用
的跟踪；药物管理。
家庭应用 家居自动化；居住环境智能化。 其它商务 汽车防盗；交互式博物馆；库存管理控制； 应用 车辆跟踪与控制。
2 体系结构
无线传感器网络是由大量无处不在的、具有无线通信与计算能力的微小传感器节点构成的自组织分布式网络系统，是能根据环境自主完成指定任务的“智能”系统。无线传感器网络不同于普通的Ad hoc网络，前者是以收集和处理信息为目的，而后者通常以通信为目的。与传统的传感器网络相比，无线传感器网络具有节点分布密集、自组网络、资源受限、拓扑变化频繁、多跳方式通信等特点。
应用中，无线传感器网络一般有两种结构：同构型[1]和异构型结构[5]。典型的同构型结构如图1所示：监控领域的节点，对感兴趣的数据进行采集、处理、融合，并通过主节
2005-01-17收到，2005-07-22改回 国家自然科学基金重点项目（NSFC-60434030），中法先进研究计划资助项目（PRA SI01-04，SI03-02）和浙江省院士基金" 无线传感器网络关键技术及开发平台" （2004.01-2004.12）资助课题
第9期 刘丽萍等：无线传感器网络部署及其覆盖问题研究 1753 点路由到基站，用户可以通过卫星或因特网进行查看、控制。典型的异构型结构如图2所示：传感器节点自组织成子网，每个子网通过网关同数据库中心连接，终端用户通过数据中心对各个子网进行监控[3]。
的是上层面向应用的任务分配和协调控制问题。应用层的协调控制大致可以分为节点部署、信息处理、动态管理3大模块。通过有效的节点部署方案和信息处理技术可以大大减少系统的能量消耗。节点部署是无线传感器网络应用的基础，节点初始部署的优劣直接影响着网络以后的性能和寿命。信息处理技术通过相关数据的融合处理减少网络的通信量，进而节约了系统的能量。动态管理是在系统运行过程中根据实际需求和剩余能量，综合考虑服务质量和能量均衡延长网络寿命而进行的一些动态的调整。
图1 无线传感器网络同构型结构
Fig.1 Structure of a homogeneous sensor network
3 节点部署
节点部署，即通过一定的算法布置节点，优化现有的网络资源，以期网络在未来的应用中获得的最大利用率或单个任务的最少消耗量。节点部署是传感器网络进行工作的第一步，是网络正常工作的基础，只有把传感器节点在目标区域布置好，才能进一步进行其它的工作和优化。 3.1 节点部署的评价指标
节点部署的好坏直接影响着网络的寿命和性能。有效的部署方案，依赖于一套完整的节点部署评价体系。结合无线传感器网络的应用特点和系统特性[4]，我们认为评价无线传感器网络的节点部署时，主要考虑以下3个指标。
图2 无线传感器网络异构型结构
Fig.2 Structure of an inhomogeneous sensor network
(1) 采集信息的完整性和精确性 要求节点能够覆盖目标区域，并且综合考虑节点的冗余和信息的容错，对传感器节点要进行动态的管理，以保证采集信息的完整性和精确性。
(2) 信息可传输性 要求保证采集到的信息能够准确及时的传递到信息的使用终端。
(3) 系统耗能(即网络寿命) 由于无线传感器网络与其它网络的最大区别在于能量限制的问题，要求在完成任务的前提下最大限度的延长整个网络的寿命。
从上面的3个指标出发，在节点部署时主要考虑下面3方面的问题。
(1) 覆盖(Coverage problem) 覆盖考虑的两个问题是：(a)初始传感器节点的布置是否覆盖了整个目标区域；(b)这些节点能否完整准确地采集目标区域的信息。结合无线传感器网络的特点，主要从下面3种情况考虑这两个问题，(a)初始覆盖：假设无线传感器网络随着监测工作的进展不发生变化，根据最初的任务需求对目标区域进行覆盖，这是一个静态的覆盖过程；(b)动态调整：考虑拓扑变化和能量消耗的因素，网络应用过程中需要对原有的节点部署进行动态调整，这是动态适应实际需求的覆盖过程；(c)移动站点辅助覆盖：将移动站点或移动机器人引入无线传感器网络部署中，应用于节点密度稀疏或大部分节点能量不足的应用中。
(2) 连接(Connectivity problem) 连接考虑的问题是：节点间的连接情况能否保证采集的信息能够准确地传递给基站。围绕这个问题，也可以从两方面展开，(a)纯连接(Pure connectivity) ：不论网络是否运行，都要保证网络任意两节
从网络各部分功能的角度出发，网络可以分为基础通信结构、支撑技术和应用层3部分。基础通信结构由底层向上包括物理层、数据链路层、路由层、传输层。支撑技术包括时间同步、节点定位、系统管理等一些中间件技术。上层即应用层包括节点部署、动态管理、信息处理等几个部分。其各部分功能的体系结构图如图3所示。
图3 无线传感器网络的功能体系结构图 Fig.3 Architecture of wireless sensor networks function
节约系统能量，延长网络寿命，适应变化的拓扑结构是目前无线传感器网络设计追求的目标，其内容涉及无线传感器网络结构设计的各个部分，也贯穿无线传感器网络应用过程中的每一个阶段。在节点间协同工作中，最具有普遍意义
1754 电 子 与 信 息 学 报 第28卷 点是连接，这是网络运行的基础；(b)路由连接(Routing algorithm based connectivity)：指在网络运行时，按照某种特定的算法实现任意两点间的连接，是对纯连接的优化[6]。不同的路由算法，对连接效果也有很大的影响。
(3) 节能(Energy efficiency problem) 节能主要考虑两个问题：(a)网络部署时传感器节点消耗的能量少；(b)网络在使用过程中能量的平均消耗量最低。前者主要是减少部署时能量的消耗，后者是从能量平衡的角度考虑延长网络寿命。
在下面的章节里，我们重点讨论无线传感器网络部署中的覆盖问题，在综述研究现状的基础上，提出适应无线传感器网络特点的覆盖问题的热点研究方向。对于部署问题的另外两个关键部分：连接和节能问题，我们会在后面的文章中作重点讨论。
就越好。
U =
1N
∑U i (2) N i =1
2
⎛1K i ⎞
U i =⎜∑(D i , j −M i ) 2⎟ (3)
⎜K j =1⎟⎝i ⎠
式中U 代表均匀性，N 是节点总数目，K i 表示第i 个节点的邻居节点个数，D i , j 表示第i 个节点与第j 个节点之间的距离，M i 表示第i 个节点与其传感范围相交的所有节点的距离的平均值。
(4) 覆盖时间 是指目标区域被完全覆盖或者跟踪时，所有工作节点从启动到就绪所需要的时间(在有移动节点的覆盖中是指移动节点移动到最终位置所需要的时间) 。覆盖时间在营救或者突发事件监测中是一个很重要的节点覆盖衡量指标，可以通过算法优化和改进硬件设施来减少覆盖时间。
4 覆盖问题
在传感器网络中，每个传感器的传感范围(即传感器所能感知的最大物理空间，为研究方便，传感器的传感范围通常被假设为圆形区域) 有限，为保证整个区域都在监测范围之内，需要按照一定的算法在目标区域布置传感器，即覆盖问题，它是整个任务得以继续进行的基础。覆盖问题从最初的画廊问题(线性规划问题) 发展到Ad hoc网络的覆盖问题，以及现在考虑能量消耗的无线传感器网络的覆盖问题，甚至出现了移动站点辅助的覆盖方案。当然随着实际应用的发展，还会出现更多的适合实际需求的有效覆盖方案。 4.1 基本概念
目前在传感器网络覆盖问题的研究中，经常涉及到邻居节点，覆盖程度，均匀性，时间和距离、覆盖重数等几个基本概念[7]。实际应用中，一些学者会根据不同的应用具体化这些概念，致使数学公式不尽相同，这里给出如下的通用定义。
(1) 邻居节点 在节点的传感范围内的节点，一对邻居节点的传感范围一般会相交或者相切，即邻居节点的传感范围能够连接起来，这样才能完全覆盖被监测区域。
(2) 覆盖程度 作为衡量传感器网络节点部署的一个指标，覆盖程度是Gage 最先提出来的，它一般定义为所有节点覆盖的总面积与目标区域总面积的比值。其中节点覆盖的总面积取集合概念中的并集，所以覆盖程度一般是小于或等于1的。
C =
i =1N
(5) 平均移动距离 移动节点的覆盖方案中，每个节点到达最终位置所移动距离的平均值。这个距离越小，系统消耗的总能量就越少。在实际应用中，不仅要减少节点移动的平均距离，而且要尽量减少节点间能量消耗的差异。因此距离可以用节点移动的平均距离和标准方差来表示更为准确，即每个节点移动的距离与整个网络中节点移动平均距离的偏差来表示(可以根据式(2)给出定义公式) 。这个标准差越小，则系统中节点消耗的能量就越均衡，不易导致网络因为某个节点能量的过多消耗而中断。
(6) 覆盖重数 最近有学者基于需要较强监测能力或较高容错率的应用环境，提出了多重覆盖[8]的概念，即某一事件是否被k 个节点覆盖。这与上面的覆盖程度并不矛盾，只是关注的侧重点不同。前者关注的是对目标区域的整体覆盖情况，后者则侧重于局部的重点观测。覆盖重数表示某个区域的覆盖的冗余程度，如果这个区域在K 个节点的传感覆盖范围之内，那么它的覆盖重数就是K 。具体的数学表达式为
N
K A =∑K i ， K i =
i =1
{
1 ， A ⊆A i
(4)
0 ， A ∩A i ≠A
这里K A 表示A 区域的覆盖重数，A i 为i 节点的传感范围，K i 表示第i 个节点传感范围是否覆盖A 区域，覆盖时K i 为
1，否则为0。 4.2 研究现状
在多机器人系统中，Gage 首先提出了覆盖问题的基本概念，并根据监测区域的侦察方式，将覆盖问题分为地毯覆盖(Blanket coverage)，障碍覆盖(Barrier coverage)，扫描覆盖(Sweep coverage)，3类[9]。但是无线传感器网络的覆盖问题
U A i A
(1)
其中C 代表覆盖程度，A i 表示第i 个节点的覆盖面积，N 代表节点的数目，A 表示整个目标区域的面积。
(3) 覆盖均匀性 节点均匀分布的传感器网络在工作时，能量的消耗相对来讲会均衡一些，这样可以避免过早出现失效节点，即起到了平衡能量负载的作用。均匀性一般用节点间距离的标准差来表示，标准差的值越小则覆盖均匀性
与以往的覆盖问题相比较，最大的区别在于网络的动态性上，网络的动态性涉及网络的初始部署和运行过程中的调整。
首先，无线传感器网络运行过程中，要尽量节约系统的整体能量；传感器节点的能量也有很大区别，需要通过适当的手段对节点的能量消耗和剩余能量分布的均衡性进行动
第9期 刘丽萍等：无线传感器网络部署及其覆盖问题研究 1755 态的调整。
其次，由于能量和通信的原因，会出现一些失效节点，这些节点所在的区域需要重新覆盖。
最后，在监测过程中，某些区域的覆盖程度和传感器采集频率也要进行调整，监测的重点区域也会发生改变，也需要对原有的覆盖结果进行相应的调整。
因此本文按无线传感器网络的使用周期，将覆盖问题划分为初始覆盖、动态调整和移动站点辅助覆盖几部分，并分别进行了探讨。
4.2.1初始覆盖 初始覆盖是假设无线传感器网络随着监测
4.2.2 动态调整 初始覆盖问题假设环境模型是可用的，进
而能够找到确定性解，但是在实际的无线传感器网络中不可能获得完整的环境信息；同时在大范围内获得全局信息而消耗的通讯能量也很巨大(这一点在无线传感器网络中是最不可取的) ，节点也会有很长的等待时间，因而不可能获得精确解[16]；加之应用环境恶劣，通信也存在一定的问题；最后，应用环境也有很大的动态性，需要网络进行动态的调整以适应应用的需求。
动态覆盖方案包括两方面的内容：(1)为了节约能量，通过算法控制一些节点的开启和关闭，完成对节点工作状态的调节；(2)适应不同应用的需要，对某些区域进行可变的多重覆盖调整，调整传感器采集的频率。
(A)节点工作状态切换 Liu 等[17]通过对偶空间法确定传
工作的进展不发生变化，根据最初的任务需求对目标区域进行覆盖的方案。与初始覆盖问题息息相关的一个问题就是计算数学中的画廊问题[10]。画廊问题是试图找到能保证画廊中的每一点都能被至少一个警卫观察到的最少警卫的数量，而初始覆盖问题的目的是确定传感器节点能够覆盖整个监测区域所需要的节点分布。将画廊问题的解法引入初始覆盖问题，初始覆盖问题可以在二维空间内进行优化，并且能够得到精确解；但在三维的空间内，覆盖问题抽象成的画廊问题被证明为NP-hard 问题。问题的难点在于单个传感器节点的传感覆盖范围的确定和对整个覆盖问题的影响。后来Meguerdichian 等[11]从覆盖的角度考虑了无线传感器网络中
感器节点的监测范围，根据跟踪的目标在哪些节点的监测范围内，以及目标的移动情况，决定哪些传感器节点负责监测事件。针对栖息环境的监测问题，Cerpa 等[18]提出了利用中心节点负责制的方案。中心节点处于警备状态，负责侦察被监测目标，一旦发现目标便以一定的半径唤醒周围的节点。节点间通过信息传递确定跟踪目标的移动方向、速度及具体位置，当目标已超出节点的监测范围时，节点会自动转入休眠状态。Tian 等[19]提出了自发的检测休眠算法，当节点的邻居节点能够覆盖监测区域时，这个节点就进入休眠状态。在没有监测盲区的情况下，这种算法可以保证100％的覆盖率。但是这种算法中，邻居节点会自发地醒来检测，导致能量的浪费。而文献[20]利用周期性的探测机制(Probing mechanism)实现对覆盖程度的监测。活动节点(通过周期性的唤醒) 在一定范围内广播探测信息并等候一定时间，如果在等待时间内收到其它节点的信息，该节点进入休眠状态；否则，节点就进行监测，直到能量耗尽。这样可以减少文献[19]中节点因为自发唤醒而消耗过多的能量。在这个算法当中，探测范围和唤醒频率一般会间接影响覆盖的程度，而且这种算法存在盲区，不能保证完全覆盖。
(B)覆盖程度调节 在一些实际的监测中不仅需要对监
的传感器定位和覆盖问题，指出覆盖范围是考虑覆盖服务质量的一个基本的性能指标，并且给出了节点固定时解决覆盖问题的计算几何和图论相结合的覆盖算法，这种覆盖算法可以得到较高的覆盖程度。
通过数学方法得到精确解的部署方案，仅适用于小范围规则区域的部署。当目标区域不规则或很大时，许多学者提出通过局部的信息找到次优化方法。Chakrabarty [12]和Meguerdichian [13]通过线性规划的方法，得到保持覆盖的最小
活动(Active)节点集。在保证覆盖程度的基础上，考虑了网络运行时的覆盖均匀性问题。从最小化未覆盖区域(Exposure area) 的角度入手，Meguerdichian
[11，14]
提出了更复杂的覆盖模
型。文献[11]用V oronoi 图和Delaunay 三角测量技术计算了传感器网络中的最差路径和最有效路径，文献[14]提出了寻找最小路径的问题。Couqueur 等[15]提出了传感器网络覆盖的目标是对分布式的监测提供充分的覆盖，可扩展的容错的局部算法更是适合动态环境下的大尺度无线传感器网络，并且具有良好的鲁棒性。Slijepcevic [16]假设节点间是等距离的，提出了一个部署的启发式算法，使传感器节点互相排斥使所有的节点能够覆盖整个研究的区域。
在实际应用中，有些区域或某些部分很重要，如火山监测中的火山口附近，战场上的指挥中心等，为获得较高的可信度，防止节点失效和信息传输失败以及由于周围噪音的干扰导致信息的不准确，Huang 等提出了采用多传感器的多重覆盖方案。然而，目前该方案仅停留在理论研究上，并没有运用到实际应用当中。
[8]
测区域完全覆盖，还要根据实际需要随时改变对某些监测区域的覆盖程度，这时需要覆盖算法根据应用的覆盖要求作相应的调整。例如，文献[21]中需要对每个监测位置进行多节点的覆盖。文献[22]中的跟踪和分类需要更高程度的覆盖。监测时需要较低的覆盖；当有入侵者时，能够自动地调节成与跟踪问题相匹配的较高程度的覆盖。这些覆盖要求依赖于对失效节点的容忍程度，高的覆盖程度对高比例的节点失效有更好的覆盖。Huang 等[8]在应用需要较强监测能力和较高容错率的情况下，提出了k 重覆盖的多项式时间算法。对动态环境下的大尺度无线传感器网络来讲，可扩展的容错的局部算法会更适合，并且具有较好的鲁棒性。Meguerdichian [14]研究了在一定时间周期内沿任意路径以任意速度移动的目标监测问题，使用复分辨技术(Multiresolution technique)与
1756 电 子 与 信 息 学 报 第28卷 Dijkstra 或者Floyd 算法结合的方式给出了覆盖的最短路径。
题的解决有很大的影响。但是，在目前拓扑发现和覆盖问题的研究中，初始分布都是自由部署的。因此改进初始的分布在很大程度上会改善整个网络的使用性能，这是在网络覆盖理论研究上的一个热点方向。
再次，部署中覆盖与连接的关系问题也是目前部署理论研究的热点问题。在无线传感器网络中，节点间一般通过无线射频的方式通信，每个节点具有一定的通信范围(Transmitting range，一般假设为球形，二维空间为圆形) ，
文献[23]在考虑能量优化、硬件精度和测量精度、以及数据查询和处理的基础上，提出了局部面向曝光的覆盖和位置发现算法(Localized exposure-based coverage and location discovery algorithms)，给出了3个移动传感器从密集区域移动
到稀疏区域的分布式协议，并通过试验证明了协议的有效性。
4.2.3 移动站点辅助的覆盖方案 随着移动基站在Ad hoc网
络中研究的进一步深入，很多学者把移动站点、移动机器人引入无线传感器网络的部署当中，出现了移动站点辅助的覆盖方案。
移动站点辅助的方案在环境数据收集或者事件监测过程中，使用移动节点或基站辅助，在固定节点间交换信息，并依据一定的算法进行目标区域覆盖的优化。Winfield [24]提出了网络缺乏连接时，借助移动站点辅助覆盖整个区域的自治分散算法。在固定监测区域收集数据时，使用自由分布的方法；节点增加时，使用递增覆盖算法，使网络的覆盖区域最广。Heo 和Varshney [25]在假设节点可靠、具有移动能力，使用理想的采集和通信覆盖模型的基础上，使用机器人的移动改进拓扑，增加整个系统的寿命；通过渐进方法，节点能够在完成目标区域覆盖的同时，进行自适应的自组。Tan 等[26]研究了多移动小车的无线网络区域覆盖系统，提出了移动传感器网络的分布式模型，并进一步基于该模型提出了连续和衍生的部署算法，使移动机器人能够覆盖更广的区域。在传感器节点自由分布的基础上，Zou [27]等通过内在的部署算法使整个覆盖均匀化，并提出用虚拟力算法可以改进初始自由的覆盖，提高了灵活性。Andrew
[28]
只有在彼此通信范围内的节点能够实现点对点的直接通信，在通信范围外的节点要通过多跳的方式进行通信。通信时也需要通信范围的连通，这样才能保证节点间能够彼此通信，这是连接问题要研究的重要内容。目前对于覆盖与连接关系的研究，文献[29,30]从理论上证明了节点的通信范围大于二倍传感范围的情况下，覆盖问题就包含了纯连接问题，此时在部署中只考虑覆盖问题就可以保证通信。但是当节点的通信范围小于二倍传感范围时，二者的包含关系如何还有待进一步的研究，而且在这种情况下节点间的通信存在严重的干涉，这也是问题研究的难点。
最后，覆盖时的能量优化以及延长网络寿命的覆盖方案也是未来无线传感器网络覆盖问题的新兴研究方向。传感器节点一般靠电池提供电源，工作在无人值守、恶劣的工作环境当中，这就使得能量问题显得尤为重要。在覆盖时除了考虑使用最少的节点总数外，还需要研究节点的传感范围与能量消耗之间的关系，找出合适的传感范围；同时需要研究节点的密度与覆盖性能之间的平衡关系，以及节约单个节点的能量与平衡整个网络能量消耗之间的关系。这些问题都直接影响着网络的寿命，寻求性能与寿命之间的平衡一直是网络研究的热点。
将势场引入移动节点的
无线传感器网络的覆盖问题，通过假设虚拟势场和虚拟受力，利用相关的物理定律作指导达到良好的覆盖效果。
6 结束语
无线传感器网络是近几年发展起来的一种新兴技术，在恶劣条件和无人值守的环境监测和事件跟踪中显示了很大的应用价值。节点部署是无线传感器网络工作的基础，对网络以后的运行情况和网络寿命有很大的影响。覆盖、连接和节能是无线传感器网络的部署问题研究的重点。本文针对部署中的覆盖问题，综述了现有的研究成果，并对今后的热点研究方向进行了讨论，希望对以后的研究有一定的指导作用。
当然，研究部署问题应该综合考虑覆盖、连接和能量消耗几个方面，这是我们以后研究的重点。与此同时，部署问题还依赖于一些支撑技术如时间同步和节点定位技术的发展。
5 热点方向
拓扑结构的变化是无线传感器网络的显著特点，也是从发展角度研究无线传感器网络覆盖问题必须解决的问题。前期的无线传感器网络的覆盖一般是建立两个假设之上的：(1)假设传感器节点固定不动，并且是随机布置的(在网络中，传感器节点多是通过飞行器散播、人工埋置、或火箭弹射等方式随机布置在监测区域[1]。) ；(2)假设传感器节点的数量非常大，以至于认为监测区域的覆盖不是问题。因此，以前的研究没有太多考虑节点数量的优化和拓扑结构的优化。适应多变环境的覆盖研究涉及到覆盖程度的调节、节点采集频率的转换、节点的开启与关闭的调度、邻居节点覆盖范围的判定等等，同时还涉及到工作节点的调度问题，即保证网络完成覆盖的最小节点数目和节点分布问题。这些都是针对无线传感器网络特点，在网络研究方面迫切需要解决的新的研究问题。
另一方面，目前许多学者做的与覆盖有关的工作，通常借用圆覆盖问题、几何问题和受限密码理论中的某种拓扑问题的解决方法。这些问题的研究中，节点的初始分布对于问
[2]
参 考 文 献
[1] Akyildiz I F, Su W, Sankarasubramaniam Y, et al.. Wireless
sensor networks: A survey [J]. Computer Networks, 2002, 38(4): 393-422.
任丰原, 黄海宁, 林闯. 无线传感器网络[J]. 软件学报, 2003, 14(7): 1282-1291.
第9期 刘丽萍等：无线传感器网络部署及其覆盖问题研究 1757
[3]
叶驰, 孙利民, 廖勇. 传感器网络的能量管理[J]. 计算机工程与应用, 2004, 8: 196-198.
[4] Jason Lester Hill. System architecture for wireless sensor
networks[D]. [Ph.D], Computer Science University of California , Berkeley, 11-17: 2003.
[5] Pister K, Hohlt B, Jeong J, et al.. Ivy－A sensor network
infrastructure. 2003. http://www-bsac.eecs.berkeley.edu/ projects/ivy.
[6] Jian N, Chandler S A G. Connectivity properties of radio
telephone network. [A]Mobile and Personal Communi -cations.1993. Seventh IEE European Conference [C], 13-25 Dec 1993: 136-141. [7]
Heo N, Varshney P K. A distributed self spreading algorithm for mobile wireless sensor networks[A]. IEEE Conference on Wireless Communications and Networking, March 16-20, 2003, vol3. 1597–1602.
[8] Huang C-F, Tseng Y-C. The coverage problem in a wireless
sensor network.[A] WSNA03 [C], September 19, 2003, San Diego, CA. 2003: 115-121.
[9] Gage D W. Command control for many-robot systems [A].
AUVS-92, the 19th Annual AUVS Technical Symposium, Huntsville AL[C], June 1992: 22-24.
[10] O'Rourke J. Art gallery theorem and algorithms[M]. New York:
Oxford University Press, 1987.
[11] Meguerdichian S, Koushanfar F, Potkonjak M, et al.. Coverage
problems in wireless Ad-hoc sensor networks [J]. INFOCOM'01, 2001, (3): 1380-1387.
[12] Chakrabarty K, Iyengar S. S, Qi H, et al.. Grid coverage for
surveillance and target location in distributed sensor networks [J]. IEEE Trans. on Computers, 2002, 51(12): 1448-1453.
[13] Bulusu N, Heidemann J, Estrin D. Adaptive beacon placement[A].
in Proceedings of the 21th International Conference on Distributed Computing Systems[C]. Phoenix, AZ, Apr. 2001: 489-498.
[14] Meguerdichian S, Koushanfar F, Qu G, et al.. Exposure in
wireless Ad hoc sensor networks [A]. Proc. of 7th Annual International Conference on Mobile Computing and Networking (MobiCom'01)[C]. July 2001: 139-150.
[15] Couqueur T, Phipatanasuphorn V, Ramanathan P, et al.. Sensor
deployment strategy for target detection [A]. Proceeding of The First ACM International Workshop on Wireless Sensor Networks and Applications, WSNA’02[C], Atlanta, Georgia, USA, September 28, 2002.42-48.
[16] Slijepcevic S, Potkonjak. Power efficient organization of wireless
sensor networks[A]. Communications IEEE International Conference on, 11-14 June 2001, 2: 472 -476 .
[17] Liu J, Cheung P, et al.. A dual-space approach to tracking and
sensor management in wireless sensor networks[A]. WSNA’02[C], Atlanta, Georgia, USA, September 28, 2002: 131-139.
[18] Cerpa A, Elson J. Hamilton M, et al.. Habitat monitoring:
application driver for wireless communications technology [R]. UCLA Computer Science Technical Report 2002, 3, December
2000.
[19] Di Tian, Georganas N D. A node scheduling scheme for energy
conservation in large wireless sensor networks[J]. Wireless Communications and Mobile Computing, 2003, 3(2): 271-290. [20] Ye F, Zhong G., Lu S, et al.. Energy efficient robust sensing
coverage in large sensor networks[R]. UCLA Technical report 2002.
[21] Varshney P. Distributed Detection and Data Fusion[M].
Spinger-Verlag, New York, 1996.
[22] Li D, Wong K, Hu Y H, et al.. Detection, classification and
tracking of targets in distributed sensor networks [J]. IEEE Signal Processing Magazine, 2002, 19(2): 17-29.
[23] Meguerdichian S, Slijepcevic S, Karayan V, et al.. Localized
algorithms in wireless Ad-hoc networks: location discovery and sensor exposure[A]. In ACM Int’l Symp. on Mobile Ad Hoc Networking and Computing (MobiHOC)[C], 2001: 106–116. [24] Winfield A F T. Distributed sensing and data collection via broken
Ad hoc wireless connected networks of mobile robots, in Distributed Autonomous Robotic Systems 4, eds. LE Parker, G Bekey & J Barhen, Springer-Verlag, 2000: 273-282.
[25] Nojeong H, Varshney P K，An intelligent deployment and
clustering algorithm for a distributed mobile sensor network[A]. IEEE International Conference on Systems, Man and Cybernetics, 5-8 Oct., 2003, 5: 4576 -4581.
[26] Jindong Tan, et al.. Multiple vechile for sensor network area
coverage[A]. Proceedings of the 5 th world congress on intelligent control and automation [C]. Hangzhou, China, June 15-19, 2004: 4666-4670.
[27] Zou Y, Chakrabarty K. Sensor deployment and target localization
based on virtual forces [A]. in Proc. IEEE INFOCOM Conference[C], 2003: 1293-1303.
[28] Howard A, Matari´c M J, Sukhatme G S. Mobile sensor network
deployment using potential fields: A distributed, scalable solution to the area coverage problem[A]. The 6th International Conference on Distributed Autonomous Robotic Systems (DARS02)[C], Fukuoka, Japan, June 25-27, 2002: 299-308. [29] Di T, Georganas N D. Connectivity maintenance and coverage
preservation in wireless sensor networks[A]. Electrical and Computer Engineering, 2004. Canadian Conference on[C], 2-5 May 2004, 2 : 1097 -1100 .
[30] Ye F, Zhong G, Lu S, et al.. PEAS: A robust energy conserving
protocol for long-lived sensor networks[A]. The 23rd International Conference on Distributed Computing Systems (ICDCS'03)[C], May 2003: 1-10.
刘丽萍： 女， 1979年生，博士生，研究方向为无线传感器网
络部署、任务分配、数据处理和协调控制.
王 智： 男， 1969年生，工学博士，副教授，主要研究方向为实
时与工业通信、网络控制和传感器网络.
孙优贤： 男， 1940年生，教授，博士生导师，中国工程院院土，
研究方向为复杂系统理论、分布控制系统以及企业综合自动化等.