无线传感器网络部署及其覆盖问题研究

第28卷第9期 电 子 与 信 息 学 报 Vol.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]。 表 1 无线传感器网络的应用及应用前景 Tab.1Wireless sensor networks applications 领 域 任务使命 军事及反恐 防爆应用 友军兵力、装备、弹药调配监视；战区监控； 敌方军力的侦察；目标追踪；战争损伤评估； 核、生物和化学攻击的探测与侦察。 环境应用 森林火灾的监测；环境的生物复杂性映射； 洪水监测；精密农业。 保健应用 人体生理指标的远程监测；医院内医生和患者 的跟踪；药物管理。 家庭应用 家居自动化；居住环境智能化。 其它商务 应用 汽车防盗；交互式博物馆；库存管理控制； 车辆跟踪与控制。 2005-01-17 收到，2005-07-22 改回 国家自然科学基金重点项目（NSFC-60434030），中法先进研究 资助项目（PRA SI01-04，SI03-02）和浙江省院士基金"无线传感器 网络关键技术及开发平台"（2004.01-2004.12）资助课题 根据无线传感器网络的应用，它的任务类型可以分为： 环境数据收集、安全性监控、事件跟踪以及三者的混合任 务[4]。在应用现场，需要通过适当的调度算法来完成节点的 部署。不管无线传感器网络要完成哪种任务，首先要解决节 点的部署问题，它直接影响着监测结果的准确性和全面性。 合理有效的节点部署可以大大减少网络搭建时间，快速 覆盖目标区域，而且通过协调控制还可以延长网络寿命，适 应变化的拓扑结构。本文从这一角度出发，探讨了无线传感 器网络节点部署的热点问题，指出了节点部署问题的研究方 向和面临的挑战；就节点部署中的覆盖问题进行了深入的讨 论，并在全面和系统地归纳总结已有的研究成果的基础上， 提出了无线传感器网络覆盖问题的研究方向，为进一步深入 研究奠定了坚实的基础。 2 体系结构 无线传感器网络是由大量无处不在的、具有无线通信与 计算能力的微小传感器节点构成的自组织分布式网络系统， 是能根据环境自主完成指定任务的“智能”系统。无线传感器 网络不同于普通的 Ad hoc 网络，前者是以收集和处理信息 为目的，而后者通常以通信为目的。与传统的传感器网络相 比，无线传感器网络具有节点分布密集、自组网络、资源受 限、拓扑变化频繁、多跳方式通信等特点。 应用中，无线传感器网络一般有两种结构：同构型[1]和 异构型结构[5]。典型的同构型结构如图 1 所示：监控领域的 节点，对感兴趣的数据进行采集、处理、融合，并通过主节 第 9 期 刘丽萍等：无线传感器网络部署及其覆盖问题研究 1753 点路由到基站，用户可以通过卫星或因特网进行查看、控制。 典型的异构型结构如图 2 所示：传感器节点自组织成子网， 每个子网通过网关同数据库中心连接，终端用户通过数据中 心对各个子网进行监控[3]。 图 1 无线传感器网络同构型结构 Fig.1 Structure of a homogeneous sensor network 图 2 无线传感器网络异构型结构 Fig.2 Structure of an inhomogeneous sensor network 从网络各部分功能的角度出发，网络可以分为基础通信 结构、支撑技术和应用层 3 部分。基础通信结构由底层向上 包括物理层、数据链路层、路由层、传输层。支撑技术包括 时间同步、节点定位、系统管理等一些中间件技术。上层即 应用层包括节点部署、动态管理、信息处理等几个部分。其 各部分功能的体系结构图如图 3 所示。 图 3 无线传感器网络的功能体系结构图 Fig.3 Architecture of wireless sensor networks function 节约系统能量，延长网络寿命，适应变化的拓扑结构是 目前无线传感器网络设计追求的目标，其内容涉及无线传感 器网络结构设计的各个部分，也贯穿无线传感器网络应用过 程中的每一个阶段。在节点间协同工作中，最具有普遍意义 的是上层面向应用的任务分配和协调控制问题。应用层的协 调控制大致可以分为节点部署、信息处理、动态管理 3 大模 块。通过有效的节点部署方案和信息处理技术可以大大减少 系统的能量消耗。节点部署是无线传感器网络应用的基础， 节点初始部署的优劣直接影响着网络以后的性能和寿命。信 息处理技术通过相关数据的融合处理减少网络的通信量，进 而节约了系统的能量。动态管理是在系统运行过程中根据实 际需求和剩余能量，综合考虑服务质量和能量均衡延长网络 寿命而进行的一些动态的调整。 3 节点部署 节点部署，即通过一定的算法布置节点，优化现有的网 络资源，以期网络在未来的应用中获得的最大利用率或单个 任务的最少消耗量。节点部署是传感器网络进行工作的第一 步，是网络正常工作的基础，只有把传感器节点在目标区域 布置好，才能进一步进行其它的工作和优化。 3.1 节点部署的评价指标 节点部署的好坏直接影响着网络的寿命和性能。有效的 部署方案，依赖于一套完整的节点部署评价体系。结合无线 传感器网络的应用特点和系统特性[4]，我们认为评价无线传 感器网络的节点部署时，主要考虑以下 3 个指标。 (1) 采集信息的完整性和精确性 要求节点能够覆盖目 标区域，并且综合考虑节点的冗余和信息的容错，对传感器 节点要进行动态的管理，以保证采集信息的完整性和精确 性。 (2) 信息可传输性 要求保证采集到的信息能够准确及 时的传递到信息的使用终端。 (3) 系统耗能(即网络寿命) 由于无线传感器网络与其 它网络的最大区别在于能量限制的问题，要求在完成任务的 前提下最大限度的延长整个网络的寿命。 从上面的 3 个指标出发，在节点部署时主要考虑下面 3 方面的问题。 (1) 覆盖(Coverage problem) 覆盖考虑的两个问题是：(a) 初始传感器节点的布置是否覆盖了整个目标区域；(b)这些节 点能否完整准确地采集目标区域的信息。结合无线传感器网 络的特点，主要从下面 3 种情况考虑这两个问题，(a)初始覆 盖：假设无线传感器网络随着监测工作的进展不发生变化， 根据最初的任务需求对目标区域进行覆盖，这是一个静态的 覆盖过程；(b)动态调整：考虑拓扑变化和能量消耗的因素， 网络应用过程中需要对原有的节点部署进行动态调整，这是 动态适应实际需求的覆盖过程；(c)移动站点辅助覆盖：将移 动站点或移动机器人引入无线传感器网络部署中，应用于节 点密度稀疏或大部分节点能量不足的应用中。 (2) 连接(Connectivity problem) 连接考虑的问题是：节 点间的连接情况能否保证采集的信息能够准确地传递给基 站。围绕这个问题，也可以从两方面展开，(a)纯连接(Pure connectivity)：不论网络是否运行，都要保证网络任意两节 1754 电 子 与 信 息 学 报 第 28 卷 点是连接，这是网络运行的基础； (b)路由连接 (Routing algorithm based connectivity)：指在网络运行时，按照某种特 定的算法实现任意两点间的连接，是对纯连接的优化[6]。不 同的路由算法，对连接效果也有很大的影响。 (3) 节能(Energy efficiency problem) 节能主要考虑两 个问题：(a)网络部署时传感器节点消耗的能量少；(b)网络 在使用过程中能量的平均消耗量最低。前者主要是减少部署 时能量的消耗，后者是从能量平衡的角度考虑延长网络寿 命。 在下面的章节里，我们重点讨论无线传感器网络部署中 的覆盖问题，在综述研究现状的基础上，提出适应无线传感 器网络特点的覆盖问题的热点研究方向。对于部署问题的另 外两个关键部分：连接和节能问题，我们会在后面的文章中 作重点讨论。 4 覆盖问题 在传感器网络中，每个传感器的传感范围(即传感器所 能感知的最大物理空间，为研究方便，传感器的传感范围通 常被假设为圆形区域)有限，为保证整个区域都在监测范围 之内，需要按照一定的算法在目标区域布置传感器，即覆盖 问题，它是整个任务得以继续进行的基础。覆盖问题从最初 的画廊问题(线性规划问题)发展到 Ad hoc 网络的覆盖问题， 以及现在考虑能量消耗的无线传感器网络的覆盖问题，甚至 出现了移动站点辅助的覆盖方案。当然随着实际应用的发 展，还会出现更多的适合实际需求的有效覆盖方案。 4.1 基本概念 目前在传感器网络覆盖问题的研究中，经常涉及到邻居 节点，覆盖程度，均匀性，时间和距离、覆盖重数等几个基 本概念[7]。实际应用中，一些学者会根据不同的应用具体化 这些概念，致使数学公式不尽相同，这里给出如下的通用定 义。 (1) 邻居节点 在节点的传感范围内的节点，一对邻居 节点的传感范围一般会相交或者相切，即邻居节点的传感范 围能够连接起来，这样才能完全覆盖被监测区域。 (2) 覆盖程度 作为衡量传感器网络节点部署的一个指 标，覆盖程度是 Gage 最先提出来的，它一般定义为所有节 点覆盖的总面积与目标区域总面积的比值。其中节点覆盖的 总面积取集合概念中的并集，所以覆盖程度一般是小于或等 于 1 的。 1 i i N A C A == L U i (1) 其中 C 代表覆盖程度，A 表示第 i 个节点的覆盖面积，N 代 表节点的数目，A 表示整个目标区域的面积。 (3) 覆盖均匀性 节点均匀分布的传感器网络在工作 时，能量的消耗相对来讲会均衡一些，这样可以避免过早出 现失效节点，即起到了平衡能量负载的作用。均匀性一般用 节点间距离的标准差来表示，标准差的值越小则覆盖均匀性 就越好。 1 1 N i i U U N = = ∑ (2) 1 2 2 , 1 1 ( ) iK i i j i ji U D M K = ⎛ ⎞= −⎜ ⎟⎜ ⎟⎝ ⎠∑ i (3) 式中 U 代表均匀性，N 是节点总数目，K 表示第 i 个节点的 邻居节点个数， ,i jD 表示第 i 个节点与第 j 个节点之间的距 离， iM 表示第 i 个节点与其传感范围相交的所有节点的距离 的平均值。 (4) 覆盖时间 是指目标区域被完全覆盖或者跟踪时， 所有工作节点从启动到就绪所需要的时间(在有移动节点的 覆盖中是指移动节点移动到最终位置所需要的时间)。覆盖 时间在营救或者突发事件监测中是一个很重要的节点覆盖 衡量指标，可以通过算法优化和改进硬件设施来减少覆盖时 间。 (5) 平均移动距离 移动节点的覆盖方案中，每个节点 到达最终位置所移动距离的平均值。这个距离越小，系统消 耗的总能量就越少。在实际应用中，不仅要减少节点移动的 平均距离，而且要尽量减少节点间能量消耗的差异。因此距 离可以用节点移动的平均距离和标准方差来表示更为准确， 即每个节点移动的距离与整个网络中节点移动平均距离的 偏差来表示(可以根据式(2)给出定义公式)。这个标准差越 小，则系统中节点消耗的能量就越均衡，不易导致网络因为 某个节点能量的过多消耗而中断。 (6) 覆盖重数 最近有学者基于需要较强监测能力或较 高容错率的应用环境，提出了多重覆盖[8]的概念，即某一事 件是否被k个节点覆盖。这与上面的覆盖程度并不矛盾，只 是关注的侧重点不同。前者关注的是对目标区域的整体覆盖 情况，后者则侧重于局部的重点观测。覆盖重数表示某个区 域的覆盖的冗余程度，如果这个区域在K个节点的传感覆盖 范围之内，那么它的覆盖重数就是K。具体的数学表达式为 { 1 1 0 N i A i i ii A AK K K A A A= ⊆= = ∩ ≠∑ ，， ， A (4) K 表示 A 区域的覆盖重数，这里 iA 为 i 节点的传感范围， iK 表示第 i 个节点传感范围是否覆盖 A 区域，覆盖时 iK 为 1，否则为 0。 4.2 研究现状 在多机器人系统中，Gage首先提出了覆盖问题的基本概 念，并根据监测区域的侦察方式，将覆盖问题分为地毯覆盖 (Blanket coverage)，障碍覆盖(Barrier coverage)，扫描覆盖 (Sweep coverage)，3类[9]。但是无线传感器网络的覆盖问题 与以往的覆盖问题相比较，最大的区别在于网络的动态性 上，网络的动态性涉及网络的初始部署和运行过程中的调 整。 首先，无线传感器网络运行过程中，要尽量节约系统的 整体能量；传感器节点的能量也有很大区别，需要通过适当 的手段对节点的能量消耗和剩余能量分布的均衡性进行动 第 9 期 刘丽萍等：无线传感器网络部署及其覆盖问题研究 1755 态的调整。 其次，由于能量和通信的原因，会出现一些失效节点， 这些节点所在的区域需要重新覆盖。 最后，在监测过程中，某些区域的覆盖程度和传感器采 集频率也要进行调整，监测的重点区域也会发生改变，也需 要对原有的覆盖结果进行相应的调整。 因此本文按无线传感器网络的使用周期，将覆盖问题划 分为初始覆盖、动态调整和移动站点辅助覆盖几部分，并分 别进行了探讨。 4.2.1初始覆盖 初始覆盖是假设无线传感器网络随着监测 工作的进展不发生变化，根据最初的任务需求对目标区域进 行覆盖的方案。与初始覆盖问题息息相关的一个问题就是计 算数学中的画廊问题[10]。画廊问题是试图找到能保证画廊中 的每一点都能被至少一个警卫观察到的最少警卫的数量，而 初始覆盖问题的目的是确定传感器节点能够覆盖整个监测 区域所需要的节点分布。将画廊问题的解法引入初始覆盖问 题，初始覆盖问题可以在二维空间内进行优化，并且能够得 到精确解；但在三维的空间内，覆盖问题抽象成的画廊问题 被证明为NP-hard问题。问题的难点在于单个传感器节点的传 感覆盖范围的确定和对整个覆盖问题的影响。后来 Meguerdichian 等[11]从覆盖的角度考虑了无线传感器网络中 的传感器定位和覆盖问题，指出覆盖范围是考虑覆盖服务质 量的一个基本的性能指标，并且给出了节点固定时解决覆盖 问题的计算几何和图论相结合的覆盖算法，这种覆盖算法可 以得到较高的覆盖程度。 通过数学方法得到精确解的部署方案，仅适用于小范围 规则区域的部署。当目标区域不规则或很大时，许多学者提 出通过局部的信息找到次优化方法。Chakrabarty[12]和 Meguerdichian[13]通过线性规划的方法，得到保持覆盖的最小 活动(Active)节点集。在保证覆盖程度的基础上，考虑了网络 运行时的覆盖均匀性问题。从最小化未覆盖区域(Exposure area)的角度入手，Meguerdichian[11，14]提出了更复杂的覆盖模 型。文献[11]用Voronoi 图和Delaunay 三角测量技术计算了 传感器网络中的最差路径和最有效路径，文献[14]提出了寻 找最小路径的问题。Couqueur 等[15]提出了传感器网络覆盖 的目标是对分布式的监测提供充分的覆盖，可扩展的容错的 局部算法更是适合动态环境下的大尺度无线传感器网络，并 且具有良好的鲁棒性。Slijepcevic[16]假设节点间是等距离的， 提出了一个部署的启发式算法，使传感器节点互相排斥使所 有的节点能够覆盖整个研究的区域。 在实际应用中，有些区域或某些部分很重要，如火山监 测中的火山口附近，战场上的指挥中心等，为获得较高的可 信度，防止节点失效和信息传输失败以及由于周围噪音的干 扰导致信息的不准确，Huang等[8]提出了采用多传感器的多 重覆盖方案。然而，目前该方案仅停留在理论研究上，并没 有运用到实际应用当中。 4.2.2 动态调整 初始覆盖问题假设环境模型是可用的，进 而能够找到确定性解，但是在实际的无线传感器网络中不可 能获得完整的环境信息；同时在大范围内获得全局信息而消 耗的通讯能量也很巨大(这一点在无线传感器网络中是最不 可取的)，节点也会有很长的等待时间，因而不可能获得精 确解[16]；加之应用环境恶劣，通信也存在一定的问题；最后， 应用环境也有很大的动态性，需要网络进行动态的调整以适 应应用的需求。 动态覆盖方案包括两方面的内容：(1)为了节约能量，通 过算法控制一些节点的开启和关闭，完成对节点工作状态的 调节；(2)适应不同应用的需要，对某些区域进行可变的多重 覆盖调整，调整传感器采集的频率。 (A)节点工作状态切换 Liu等[17]通过对偶空间法确定传 感器节点的监测范围，根据跟踪的目标在哪些节点的监测范 围内，以及目标的移动情况，决定哪些传感器节点负责监测 事件。针对栖息环境的监测问题，Cerpa等[18]提出了利用中 心节点负责制的方案。中心节点处于警备状态，负责侦察被 监测目标，一旦发现目标便以一定的半径唤醒周围的节点。 节点间通过信息传递确定跟踪目标的移动方向、速度及具体 位置，当目标已超出节点的监测范围时，节点会自动转入休 眠状态。Tian等[19]提出了自发的检测休眠算法，当节点的邻 居节点能够覆盖监测区域时，这个节点就进入休眠状态。在 没有监测盲区的情况下，这种算法可以保证100％的覆盖率。 但是这种算法中，邻居节点会自发地醒来检测，导致能量的 浪费。而文献[20]利用周期性的探测机制(Probing mechanism) 实现对覆盖程度的监测。活动节点(通过周期性的唤醒)在一 定范围内广播探测信息并等候一定时间，如果在等待时间内 收到其它节点的信息，该节点进入休眠状态；否则，节点就 进行监测，直到能量耗尽。这样可以减少文献[19]中节点因 为自发唤醒而消耗过多的能量。在这个算法当中，探测范围 和唤醒频率一般会间接影响覆盖的程度，而且这种算法存在 盲区，不能保证完全覆盖。 (B)覆盖程度调节 在一些实际的监测中不仅需要对监 测区域完全覆盖，还要根据实际需要随时改变对某些监测区 域的覆盖程度，这时需要覆盖算法根据应用的覆盖要求作相 应的调整。例如，文献[21]中需要对每个监测位置进行多节 点的覆盖。文献[22]中的跟踪和分类需要更高程度的覆盖。 监测时需要较低的覆盖；当有入侵者时，能够自动地调节成 与跟踪问题相匹配的较高程度的覆盖。这些覆盖要求依赖于 对失效节点的容忍程度，高的覆盖程度对高比例的节点失效 有更好的覆盖。Huang等[8]在应用需要较强监测能力和较高 容错率的情况下，提出了k重覆盖的多项式时间算法。对动 态环境下的大尺度无线传感器网络来讲，可扩展的容错的局 部算法会更适合，并且具有较好的鲁棒性。Meguerdichian[14] 研究了在一定时间周期内沿任意路径以任意速度移动的目 标监测问题，使用复分辨技术(Multiresolution technique)与 1756 电 子 与 信 息 学 报 第 28 卷 Dijkstra或者Floyd算法结合的方式给出了覆盖的最短路径。 文献[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]将势场引入移动节点的 无线传感器网络的覆盖问题，通过假设虚拟势场和虚拟受 力，利用相关的物理定律作指导达到良好的覆盖效果。 5 热点方向 拓扑结构的变化是无线传感器网络的显著特点，也是从 发展角度研究无线传感器网络覆盖问题必须解决的问题。前 期的无线传感器网络的覆盖一般是建立两个假设之上的：(1) 假设传感器节点固定不动，并且是随机布置的(在网络中， 传感器节点多是通过飞行器散播、人工埋置、或火箭弹射等 方式随机布置在监测区域[1]。)；(2)假设传感器节点的数量 非常大，以至于认为监测区域的覆盖不是问题。因此，以前 的研究没有太多考虑节点数量的优化和拓扑结构的优化。适 应多变环境的覆盖研究涉及到覆盖程度的调节、节点采集频 率的转换、节点的开启与关闭的调度、邻居节点覆盖范围的 判定等等，同时还涉及到工作节点的调度问题，即保证网络 完成覆盖的最小节点数目和节点分布问题。这些都是针对无 线传感器网络特点，在网络研究方面迫切需要解决的新的研 究问题。 另一方面，目前许多学者做的与覆盖有关的工作，通常 借用圆覆盖问题、几何问题和受限密码理论中的某种拓扑问 题的解决方法。这些问题的研究中，节点的初始分布对于问 题的解决有很大的影响。但是，在目前拓扑发现和覆盖问题 的研究中，初始分布都是自由部署的。因此改进初始的分布 在很大程度上会改善整个网络的使用性能，这是在网络覆盖 理论研究上的一个热点方向。 再次，部署中覆盖与连接的关系问题也是目前部署理论 研究的热点问题。在无线传感器网络中，节点间一般通过无 线射频的方式通信，每个节点具有一定的通信范围 (Transmitting range，一般假设为球形，二维空间为圆形)， 只有在彼此通信范围内的节点能够实现点对点的直接通信， 在通信范围外的节点要通过多跳的方式进行通信。通信时也 需要通信范围的连通，这样才能保证节点间能够彼此通信， 这是连接问题要研究的重要内容。目前对于覆盖与连接关系 的研究，文献[29,30]从理论上证明了节点的通信范围大于二 倍传感范围的情况下，覆盖问题就包含了纯连接问题，此时 在部署中只考虑覆盖问题就可以保证通信。但是当节点的通 信范围小于二倍传感范围时，二者的包含关系如何还有待进 一步的研究，而且在这种情况下节点间的通信存在严重的干 涉，这也是问题研究的难点。 最后，覆盖时的能量优化以及延长网络寿命的覆盖方案 也是未来无线传感器网络覆盖问题的新兴研究方向。传感器 节点一般靠电池提供电源，工作在无人值守、恶劣的工作环 境当中，这就使得能量问题显得尤为重要。在覆盖时除了考 虑使用最少的节点总数外，还需要研究节点的传感范围与能 量消耗之间的关系，找出合适的传感范围；同时需要研究节 点的密度与覆盖性能之间的平衡关系，以及节约单个节点的 能量与平衡整个网络能量消耗之间的关系。这些问题都直接 影响着网络的寿命，寻求性能与寿命之间的平衡一直是网络 研究的热点。 6 结束语 无线传感器网络是近几年发展起来的一种新兴技术，在 恶劣条件和无人值守的环境监测和事件跟踪中显示了很大 的应用价值。节点部署是无线传感器网络工作的基础，对网 络以后的运行情况和网络寿命有很大的影响。覆盖、连接和 节能是无线传感器网络的部署问题研究的重点。本文针对部 署中的覆盖问题，综述了现有的研究成果，并对今后的热点 研究方向进行了讨论，希望对以后的研究有一定的指导作 用。 当然，研究部署问题应该综合考虑覆盖、连接和能量消 耗几个方面，这是我们以后研究的重点。与此同时，部署问 题还依赖于一些支撑技术如时间同步和节点定位技术的发 展。 参 考 文 献 [1] Akyildiz I F, Su W, Sankarasubramaniam Y, et al.. Wireless sensor networks: A survey [J]. Computer Networks, 2002, 38(4): 393-422. [2] 任丰原, 黄海宁, 林闯. 无线传感器网络[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年生，教授，博士生导师，中国工程院院土， 研究方向为复杂系统理论、分布控制系统以及企业综合 自动化等. 无线传感器网络部署及其覆盖问题研究 1 引言( 2 体系结构 3 节点部署 3.1 节点部署的评价指标 4 覆盖问题 4.1 基本概念 4.2 研究现状 4.2.2 动态调整 初始覆盖问题假设环境模型是可用的，进而能够找到确定性解，但是在实际的无线传感器网络中不可能获得完整的环境信息；同时在大范围内获得全局信息而消耗的通讯能量也很巨大(这一点在无线传感器网络中是最不可取的)，节点也会有很长的等待时间，因而不可能获得精确解[16]；加之应用环境恶劣，通信也存在一定的问题；最后，应用环境也有很大的动态性，需要网络进行动态的调整以适应应用的需求。 4.2.3 移动站点辅助的覆盖方案 随着移动基站在Ad hoc网络中研究的进一步深入，很多学者把移动站点、移动机器人引入无线传感器网络的部署当中，出现了移动站点辅助的覆盖方案。 5 热点方向 6 结束语 参 考 文 献