无线传感器网络的覆盖优化机制研究

基金项目：国家自然科学基金(60303027)

    无线传感器网络(WSN)的应用研究被认为是21世纪的一项挑战性科研课题，在监控和军事领域具有重要的应用价值，如目标跟踪、入侵检测、气候监测、灾难管理和战场侦查等。

    无线传感器网络是由部署在观测环境附近的大量微型廉价低功耗的传感器节点组成，通过无线通信方式形成一个多跳的网络系统。作为一种全新的信息获取和处理技术，它可在很多应用领域实现复杂的大规模监测和跟踪服务[1，2]。
新技术在带来应用机会的同时，也带来了新的研究问题。由于传感器网络的节点容量十分有限，需要节点之间相互协作完成感知和通信任务，因此希望节点计算和通信的工作量最小化。

    传感器网络具有分布式处理带来的监测精度高、容错性能好、覆盖区域大、可远程监控等众多优点，已成为近期国内外网络界研究的热点。Akyildiz等人对传感器网络研究的系列问题进行过权威性的综述[3]，包括物理层至应用层的各种急需解决的技术。
无线传感器网络最重要的特点是节点携带的电池能量不能补充，这是无线传感器网络应用的“瓶颈”问题和研究的焦点。

    最优覆盖是无线传感器网络应用的一个基本问题，是提供监测和目标跟踪服务质量的一种度量。人们通常需要网络在完成监测任务的前提下，尽量节省能耗以延长网络寿命。最优覆盖问题是传感器网络的基本问题，主要研究传感器监测物理空间的效果程度。如何实现最优覆盖是网络拓扑管理的关键内容，与能量高效和可靠监测两方面都直接相关。在网络体系结构的层次上，它可视为网络层的研究范畴。
覆盖反映了网络监测和实现目标跟踪的质量效果。覆盖问题已引起了业界越来越多的关注。

1 传感器节能覆盖问题
    传感器网络的研究目前在国际上特别是在美国十分热门。在履行有保障的监测任务的前提下，降低能耗是无线传感器网络的重要研究课题。动态控制拓扑结构、调度节点状态是一种可行的解决方案。目前已有多种拓扑结构控制和节点调度的方法。覆盖问题的起源可追溯到艺术馆定理问题，通常分为区域覆盖、点覆盖和障碍物覆盖3种，最常见的是区域覆盖[4]。

    网络实现覆盖优化的主要机理是调度节点的休眠间隔时间，而其他节点保持工作活动状态，但网络仍能提供连续的监测服务。区域覆盖和点覆盖问题在第2和3部分阐述。障碍物覆盖优化是通过障碍物而未被发现的最小化概率。

    覆盖算法分为集中式和分布式两类。分布式和局部化算法是在各节点上独立计算的分布式决策过程，只利用其邻居节点的信息，通信跳数固定。由于WSN的拓扑结构是动态的，传感器种类众多，人们比较倾向于采用分布式或局部化的协议和算法[5]。目前解决覆盖问题的主流方案是通过调度节点的值守时间来节省能耗。由于节点呈随机分布，暂时关闭部分冗余节点从网络全局来看是可行的，可以使得所有节点轮流依次得到休眠，从而提高整个网络系统的寿命。通常认为网络寿命是网络可执行感知功能，且能将数据可靠传至监控基站的时间。

    最常见的覆盖优化方法是将所有节点分成若干个不相交的集合，每个集合可完全覆盖整个地区。这些节点集合依次被唤醒，只要一个集合的节点处于工作状态，则可由其完成监测任务。覆盖优化的目标是确定感知不相交重叠的节点集合的最大数目，极大化每个传感器两次被激活之间的时间，使其寿命得以延长。由于节点硬件资源受到严格限制，在这种网络平台上实现通用的协议具有一定难度，本文认为对潜在应用进行合理区分，对某些重要应用有针对性地开发相应协议，在可靠性、可扩展性和能量高效等方面更容易获得最优化的网络性能。

    网络寿命最大化是传感器网络设计的主要目标。通常传感器节点的收发器所处状态可分为以下4种：传输、接收、空闲和休眠。空闲状态指收发器处于既不传输也不接收状态，休眠状态指收发器处于关闭状态。一份关于地震传感器的分析报告指出[6]，一般节点功耗比例如下：传输状态为0.38～0.7 W，接收状态为0.36 W，空闲状态为0.34 W，休眠状态时则为0.03 W，其中用于完成感知任务的能耗为0.02 W。

    研究表明接收状态和空闲状态的功耗与传输状态几乎相等，而传统Ad hoc无线网络传输功耗通常是接收的两倍。因此为了节省能源延长节点寿命，从而延长整个网络的寿命，尽量增加节点的总体休眠时间是突破口，关键技术在于优化调度节点的工作行为模式。

    研究传感器的节能覆盖问题具有重要的应用价值。节能覆盖的主要手段包括：

    (1)优化节点调度，延长网络寿命
    譬如网络初始寿命为6个月，通过采用新型调度方案后若延长寿命1倍，网络部署后则正常使用期将扩展为12个月，可大大降低供应商和客户的网络造价成本，对用户具有很大的吸引力。

    (2)优化网络的动态拓扑结构提供充分覆盖监测
    对覆盖问题的研究可用于保证对某些区域监测的高度严密性，这对重要地带和敏感事件形成无漏隙的监控网，具有特殊价值。

1.1  区域覆盖
    覆盖问题研究得最多的是区域覆盖，此时传感器网络的主要用途是监测某个区域。图1(a)所示为随机配置传感器来覆盖一个矩形区域，其中圆形表示节点感知范围，区域内各地点至少被一个传感器所监测到。图1中连接在一起的黑色节点形成一组当前工作的传感器集合，监测区域覆盖了整个矩形。

    对于大量传感器随机配置的情况，目前比较成熟的区域覆盖优化方法是将节点划分成多个不交叉的集合，各集合能独立承担整个区域的监测任务。这些节点集合依次被唤醒，当一个节点集工作时，其余节点集中的所有传感器则处于低能耗的休眠模式。
优化目标是使得子集合的数目最大化，以便使节点得到更长的休眠时间。
除此之外，也可将不交叉的节点模型化为无向图内不交叉的优势集合，传感器构成图的所有顶点，连接任意两个在感知范围内的传感器则形成图的边。

    最大不交叉优势集合的求解为非多项式-完全(NP-complete)问题，且任何多项式时间逼近算法的下限为1.5。基于图染色的策略可求解这种最大不交叉优势集合的问题，该策略的过程如下：首先不交叉的节点集合对所有节点按顺序染色法进行染色；然后非优势节点用渐增颜色标绘，最深颜色节点被重新着色并转移至优势集合中，直到过程结束。

    另外还有一个基于探测和节点调度的节能覆盖方法，每个传感器具有相同的感知范围，且定义覆盖度为可监控区域占整个网络区域的比重。休息准则基于探测机制，探测范围是依据工作节点的平均密度(即单位区域上的传感器数目)或平均覆盖冗余率。该协议为分布式、局部化协议，计算复杂度较低。

1.2 点覆盖
    点覆盖问题要求覆盖一组给定的地点。图1(b)用随机分布的传感器网络覆盖一组地点(即小方形块)。相连的黑色节点构成一组当前工作的传感器集合。由于大量传感器随机散布在目标点附近，将监测到的数据传输至信息中心。假设每个传感器可监测其感知区域内的所有目标，研究目标就是保证每个目标在任意时刻至少被一个传感器所监控。点覆盖优化方法是将传感器分成若干个不相交的集合，每个集合能完全覆盖所有目标点。这些集合依次被唤醒，只有一个集合处于工作状态即可。

    由于所有目标点均能被传感器集合监测，优化目标是确定不相交集合的最大数，因此可通过延长每个传感器两次激活之间的时间间隔，相应地延长寿命。

    当大规模密集型传感器随机配置时，区域覆盖问题也可用点覆盖近似表示。前提是网络规模大、节点分布密集，可通过覆盖每个传感器位置来近似给定区域内所有点的覆盖。点覆盖和区域覆盖的不同点在于，实现点覆盖只要有邻居集合的信息，区域覆盖则还需要几何/方向等方面的数据。

2 网络连通与节能覆盖的关系
    无线传感器网络的另一个重要研究问题是连通性。如果网络中任意活动节点能和网内其他活动节点进行通信，通信过程可通过中间节点作为中介，则称该网络是连通的。一旦传感器配置完毕，则须组成连通的网络才能将采集到的信息传回控制中心。研究目标是确定保持足够覆盖和全网连通的最少传感器数目，通过选择最小工作节点数且在位置距离上满足全网通信传输，可降低能耗和延长网络寿命。保证覆盖和连通性的方法是将活动传感器集合设计成连通优势集合。当传输节点集合较小时，节点覆盖问题可与广播结合起来。传输集合的广播式选择类似节点覆盖问题，两者都试图找到一个小的覆盖集合。

    文献[4]证明了一个重要结论，认为如果通信距离Rc不小于感知距离Rs的两倍，则一个凸形区域的完全覆盖意味着工作节点可通信互连。如果通信距离太大，无线通信会受外界干扰。如果通信距离可调节，则确保连通的最优方法是将通信距离设置为感知距离的两倍。两个节点如果存在重叠的感知区域，则称为邻居节点。直观上当Rc≥2Rs时，两邻居节点处于彼此的感知范围内(如图2所示)。基于以上结论，文献[4]深入研究了连通与覆盖之间的关系，认为如果节点密度足够高，通过部署处于正六边形顶点的活动节点子集能保证完全覆盖，并根据这些研究结论提出了一种分布式协议，即最佳地理密度控制(OGDC)协议。该协议在NS2[7]仿真平台上进行实验，模拟结果表明在覆盖率、工作节点数目以及系统寿命方面性能良好。

    有些应用要求在保持工作节点通信连通的同时，还需提供不同的覆盖等级。如果网络中所有地点至少在k个传感器的感知范围内，则称该网络具有k 级覆盖。覆盖等级越高，网络越能获得高的传感精度和强的容错能力。研究表明当通信距离Rc至少是感知距离Rs的两倍时，k 级覆盖的网络可简化为k 级连通的网络图。k级连通的网络图具有如下性质：移去网络中任意k -1个节点，网络依然保持连通。借助连通图的这些性质，可以设计出覆盖性能细粒度化的节点调度协议和算法。

    目前的覆盖配置协议可提供不同的覆盖等级。文献[8]提出的协议主要过程如下：为了计算相交点，节点维护一张关于邻居节点的信息表(包括位置和工作状态)，且定期广播问候(Hello)信号通报当前位置与状态。这里节点状态分为3种：休眠状态、监听状态和活动状态。所有节点以随机时间间隔进行休眠状态启动。当节点苏醒时进入监听状态，根据时间片决定转入休眠还是活动状态。一旦节点处于活动状态，在每次收到Hello消息时重新评估周围覆盖的情况，决定进入休眠还是保持活动状态。

3 移动式修复覆盖机制
    现有的覆盖问题解决思路是调度高密度网络中静态冗余节点的状态。通常总是假设网络中存在大量传感冗余的节点，可进行工作/休眠模式转换，减少其工作时间以提高生命周期，很少有人考虑遗漏或薄弱区域的覆盖不充分问题。

    由于传感器随机布撒，网络部署后部分节点可能会失效，从而导致形成监测遗漏。
解决方法是先找出冗余节点的位置，再选择最短路径移动该节点至目的地。由于研究对象是网络部署后移动节点的问题，不考虑起始部署网络时调整部分节点位置的那种情况。确定高密度网络中是否存在冗余节点，已有不少成熟的研究结果。但在全网范围内统一找出冗余节点，则实现起来较困难，因为集中式计算在传感器网络中通常认为是不可行的，主要是通信代价太高和数据量过大。

    本文采用分簇方式将覆盖地区划分成许多子区域或簇，进行细粒度的网络监测与覆盖控制。簇首负责收集信息，判断本簇是否存在冗余节点，或本区域是否属于覆盖度不足k值的薄弱地带，并负责向全网广播该消息。另外覆盖不充分地带由其附近存在冗余节点的簇负责指派移动传感器。

    如果移动节点直接行走至目的地，则会花费很长时间和消耗很多电能，导致该节点中途死亡。比较可行的方法是采用接力搬移方式，基本思想是根据路由理论中的Dijkstra算法确定一条从该节点至终点位置的最短距离传输路径。沿该路径上的各节点依次朝终点方向移动一步，则终点位置被该路径上的最后一个节点占据，原本为冗余节点的链首位置变空。此方式将使移动时间大大缩短，移动过程所需耗电被多个节点分摊，因而具有较好的性能，并且节点移动不影响网络正在进行的监测服务，这在监控重要安全敏感区域时显得特别有用。

4 结束语
    传感器覆盖是无线传感器网络应用的服务质量的一种表现。覆盖通常与无线传感器网络的节能和网络连通性相关。本文阐述了在确保覆盖要求条件下，目前实施调度机制的主要方法和原理，可通过优化节能和降低功耗来延长网络寿命。调度传感器节点在休眠和活动模式之间进行切换，是覆盖问题研究得出的一种重要节能方法。

    对于资源受限且拓扑动态变化的无线传感器网络，宜采用分布式和局部化的覆盖控制协议和算法。

5 参考文献
[1] 孙利民, 李建中等. 无线传感器网络 [J]. 北京: 清华大学出版社, 2005.5.
[2] 任丰原, 黄海宁, 林闯. 无线传感器网络 [J]. 软件学报, 2003,14(1):1282—1291.
[3] Akyildiz I F, Su W,  Sankarasubramaniam Y, Cayirci E. Wireless Sensor Networks: a Survey [J]. Computer Networks, 2002,38(3):393—422.
[4] Zhang H, Hou J C. Maintaining Sensing Coverage and Connectivity in Large Sensor Networks [R]. University of Illinois at Urbana Champaign UIUC Computer Science Technical Report UIUCDCS-R-2003-2351, 2004.
[5] 于海斌, 曾鹏, 王忠锋等. 分布式无线传感器网络通信协议研究 [J]. 通信学报, 2004,25(4):102—110.
[6] Raghunathan V, Schurgers C, Park S. Energy-Aware Wireless Microsensor Networks [J]. IEEE Signal Processing Magazine, 2002,19(2):40—50.
[7] The Network Simulator -NS2 [DB/OL].
http://www.isi.edu/nsnam/ns/.
[8] Wang X, Xing G, Zhang Y. Integrated Coverage and Connectivity Configuration in Wireless Sensor Networks [C]. In:Proceedings of the First International Conference on Embedded Networked Sensor Systems, Los Angeles, California, USA, 2003.

收稿日期：2005-05-16

[摘要] 如何实现最优覆盖是无线传感器组网的一个基本问题。文章分析了传感器覆盖问题的背景，给出了节点调度方案的主要方法和技术原理，探讨了基于网络能量高效的覆盖优化与网络连通性之间的关系，重点阐述了实现区域覆盖和点覆盖的机制。对于覆盖薄弱地区，文章提出了采用分簇方式将覆盖地区划分成许多子区域或簇，用动态移动修复机制提供细粒度的网络监测与覆盖控制。文章认为调度传感器节点在休眠和活动模式之间进行切换，是一种重要节能方法；对于资源受限且拓扑动态变化的无线传感器网络，宜采用分布式和局部化的覆盖控制协议和算法。

[关键词] 无线传感器网络；覆盖；能量高效；最优化

[Abstract] Coverage optimization is a fundamental issue for the operation and management of Wireless Sensor Network (WSN). In the paper, the background of sensor coverage is given, and the main methods and technology principles of node scheduling are described. After the mechanism of area coverage and point coverage are emphatically considered, the relationship of coverage optimization based on energy efficiency and network connectivity is discussed. Areas with bad coverage are proposed to be divided into multiple clusters, and a new repairing mechanism with mobile node is used to offer fine-granularity network monitoring and coverage control. It is an important method for energy saving to handover the sensor node between the dormant and active modes. The WSN with limited resources and dynamic topology had better adopt distributed and localized coverage control protocols and algorithms.

[Keywords] wireless sensor network; coverage; energy efficiency; optimization