无线传感器网络覆盖问题

近年来，无线传感器网络引起了业界极大关注，其应用环境通常是由价格便宜的传感器节点组成的，每个节点都能够采集、存储和处理环境信息，并且能和邻居节点通过无线链路保持通信。覆盖问题是无线传感器网络配置首先面临的基本问题，因为传感器节点可能任意分布在配置区域，它反映了一个无线传感器网络某区域被监测和跟踪的状况。随着无线传感器网络应用的普及，更多的研究工作深入到其网络配置的基本理论方面，其中覆盖问题就是无线传感器网络设计和规划需要面临的一个基本问题之一。随着深入研究的角度不同，覆盖问题也表述成不同的理论模型，甚至在计算几何里面就能找到与覆盖相关的解决方案。尽管这些办法并不能直接应用到无线传感器网络中，但是研究这些问题有助于建立读者对无线传感器网络覆盖问题相关的理论背景。

1  无线传感器网络覆盖理论基础

在现有的研究成果当中，很多都是致力于解决传感器网络的部署和监测及覆盖与连接的关系等方面问题。另外，也有一些研究致力于特定的应用需求，但其核心思想都是与覆盖问题有关的。例如，减少传感器节点的有效工作时间，那些共享感应区域和任务的传感器节点可以关掉电源以节省能量，从而可以延长网络的寿命。为此，必须确定关闭哪些传感器节点及如何调度分配节点的工作时间，以至于当关掉节点时网络不存在覆盖的盲点。

本小节将着重讨论一下与无线传感器网络覆盖相关的两个计算几何问题。第一个就是艺术馆问题(Art Gallery Problem)。设想艺术馆的业主想在馆内放置照相机，以便能够预防小偷盗窃。关于实现这个想法存在两个问题需要回答：首先就是到底需要多少台相机；其次，这些相机应当放置在哪些地方才能保证馆内每个点至少被一台相机监视到。假定相机可以有360°的视角而且可以极大速度旋转。此外，相机可以监视任何位置，视线不受影响。问题优化要实现的目标就是所需相机的数目应该最小化。在这个问题当中，艺术馆通常建模成一个二维平面的简单多边形。一个简单的解决办法就是将多边形分成不重叠的三角形，每个三角形里面放置一个相机。通过三角测量法将多边形分成若干个三角形，这样可以实现任何一个多边形都可被

个相机所监视到，这里n表示多边形所包含的三角形的数目。这也是最糟糕情况下的最佳结果。如图2-8所示是将一个简单多边形用三角测量法拆分的例子，放置两个监视相机足以覆盖整个艺术馆。尽管这个问题在二维平面可以得到最优解，然而扩展到三维空间，这个问题就变成了NP-hard问题了。   

另外一个与无线传感器网络覆盖相关的几何问题是圆覆盖问题，即在一个平面上最多需要排列多少个相同大小的圆，才使其能够完全覆盖整个平面。换个角度说，也就是给定了圆的数目，如何使得圆的半径最小。参考文献就矩形平面区域的圆覆盖问题做了详细的探讨。A.Heppes和J.B.M.Melissen实现了矩形平面的圆最优覆盖问题，分为最多用5个圆和7个圆来完成覆盖两种情况。如图2-9所示给出了一个7个圆最优覆盖的一个例子。参考文献[10]给出了6个和8个圆的最优覆盖办法，并且基于一种模拟退火方法提出了一种全新的用11个圆的覆盖解决方案。多达30个圆的覆盖问题在文献[11]中也做了详细的探讨。




无线传感器网络的覆盖问题在本质上和上面的几何计算问题是一致的：需要知道是否某个特定的区域被充分覆盖和完全处于监视之下。就成本而言，配置的传感器节点的数量是非常重要的。尽管计算几何研究的结果对理解传感器网络覆盖问题提供了一个理论背景，但仅仅是计算几何问题的求解办法是不能直接应用于无线传感器网络的。主要有以下几个方面的原因：首先，所做的前提假设不同。例如，艺术馆问题的照相机可以看到无穷远处，除非中间有障碍物遮挡。事实上刚好相反，传感器节点存在最大的感应范围。其次，无线传感器网络通常没有固定的基础设施，并且其拓扑可能随时变化。因此，很多决策必须通过分布式方式来完成。然而，大多数几何问题都是通过集中式来解决的。

在典型的无线传感器网络应用当中，放置或配置一些传感器节点来监视一个区域或点集。一些应用中可以选择传感器配置场地，如定点部署和配置，这种方式称为确定性配置：而另外一些应用(如敌方区域或非常恶劣等人员不能到达的环境)，只能通过随机部署(如空投撒播方式)足够多的传感器节点到监视区域，希望空投后未遭破坏的传感器足以监视目标区域，这种方式称为非确定性的配置或随机配置。如果可以选取部署场地，可采用确定性的传感器配置方法；否则，该配置就是随机配置。在上面两种配置情况下，都希望部署的传感器集合能够彼此通信，或者直接或者间接通过多跳方式通信。因此，除了要覆盖感应的区域或点集外，通常需要配置的传感器集合能够形成一个互联的网络。对于已经放置好的传感器，很容易地就能检测是否配置的传感器集合覆盖了目标区域或点集，而且也能判断是否该集合相互连通。就覆盖特性而言，需要知道各个传感器节点的感应范围(假设传感器能够感应距离r之内发生的事件，其中，r为传感器的感应半径)。就连接特性而言，需要知道传感器的通信半径，记为c。Zhang和Lou在文献[12]中给出了包含连接的覆盖的充分必要条件，满足定理1：

定理1：当传感器的密度(即单位区域的传感器数目)为有限时，c≥2r是覆盖包含连接性的充分必要条件。

X.Wang等人也证明了在k阶覆盖(每个点至少被k个传感器覆盖)和k阶连接性(配置传感器的通信图是尼阶连接的)情况下的一个类似的结论，满足定理2。

定理2：当c≥2r，一个凸区域的k阶覆盖必定包含了k阶连接性。

注意到k>1的k阶覆盖提供了一定的容错度，能够监视所有的点，只要不多于k-1个传感器故障或失效。

当然，除了上面介绍的典型的无线传感器网络配置问题外，也可能出现其他形式的无线传感器配置问题。例如，不必要求传感器节点间彼此通信。相反，每个传感器可直接和一个位于所有传感器通信半径范围内的基站通信。还有一种情况就是传感器是移动和自我配置的无线传感器。移动传感器集合可以部署到一个未知的和有潜在危险的环境中。根据初始的配置，这种传感器可以重新确定位置以便实现未知环境的最大覆盖。它们再将采集到的信息发给感应环境外面的一个基站。

2.2.2  无线传感器网络覆盖的计算

关于无线传感器网络覆盖的计算主要是介绍现有的配置和覆盖相关的算法及一般的无线传感器网络覆盖设计准则。

Andrew Howard等专门针对移动无线传感器网络提出了一种增量自我配置的贪婪算法(Greedy and Incremental Self-deployment Algorithm)。移动无线传感器网络是一个分布式的节点集合，每个节点都有感应、计算、通信和局部移动等功能。而配置区域通常都是恶劣或未知的环境区域。该增量自我配置的贪婪算法的基本思想就是每次配置一个节点到未知区域，每个加入的节点都充分利用先前配置的节点收集到的信息来确定其最佳目标位置。算法设计的目的就是使网络的覆盖最大化，而同时又确保节点彼此保持视距通信，即本地化。实现本地化可以通过Mesh结构的方式实现，节点可以在完全未知的环境下通过使用其他节点作为路标来实现本地化，从而确定节点之间的相互位置和保证可靠通信。该算法的核心就是贪婪和增量。贪婪一词来自于该算法尝试为每个节点都寻找能使网络覆盖最大化的位置。事实上，寻找节点的最优位置是一个相当困难的问题，因此不得不采用大量的初始化操作来指导选择的过程，如边界初始化和覆盖初始化等。增量一词主要是因为每次配置只增加一个节点到配置区域。该算法的复杂度为O(n2)，其中n为配置的传感器节点数目。

    A.Howard等提出了基于电势场技术的未知环境移动传感器网络的部署配置方法。这种移动传感器网络可通过简易的初始配置就可实现网络的自我配置。网络内的节点可以随意扩展，使得网络覆盖最大化。该配置算法的基本思想就是将传感器节点当做假想的物粒子，且受到势力场的势力。势力压迫节点彼此之间和障碍物之间发生作用力。通过节点的初始简易配置快速地在整个网络扩散，从而最大化网络的覆盖。节点之间除了相互的排斥力外，还受到一个黏性摩擦力。该力用来确保网络最终达到一个静态平衡状态，也就是说所有节点最后都能够完全停止下来。然而，黏性摩擦力不能阻止网络对环境变化的反应。如果节点发生移动，网络就会为变化后的环境自动重新配置，直到再次达到一个静态平衡状态。这样，节点仅仅当需要的时候才改变位置，从而可以节省大量的宝贵能量资源。该算法的核心就是利用了电势场技术，但依赖于一个重要的假设：每个节点的安装传感器都能够确定它的邻居节点及障碍物的距离和方位(可利用扫描激光距离探测仪或全息相机配置适当的传感器)。利用该信息，节点就可知道作用的电势力的大小，并将其转换为控制矢量信息发给传感器的发动机。该算法不需要其他信息，最大的优点就是不需要考虑环境的建模、节点的局部定位和节点彼此之间的通信。因此，该算法具有较高的鲁棒性和扩展性。

Huang和Tseng提出了一种基于传感器数目的多项式时间算法，将覆盖问题抽象表述为一个决策问题，并验证了一个传感器配置是否提供了k阶覆盖。该算法的目标就是确定无线传感器网络服务区域中的每个点是否至少被k个传感器节点监视覆盖。传感器的感应范围可以是单位圆，也可是非单位圆。这种算法可方便地用到传感器网络的分布式协议当中，每个节点只需收集本地信息做出自己的决策。另外，该算法不需确定每个位置的覆盖，而是尽量看每个传感器感应范围的周界是如何被覆盖的，这样最大的优点就是得到了多项式时间的算法，降低了算法的计算复杂度，即O(nd log d)，其中n为传感器节点数目，d为和一个传感器感应范围交叉的最大传感器数目。只要传感器的周界被充分覆盖，则整个区域就能够被充分覆盖。因此这种算法适合于下面几种无线传感器网络应用，包括定位应用、要求较强的环境监测功能的应用场合及要求严格的容错功能的传感器网络应用。文献[16]通过与节点数相关的多项式有效算法解决了二维平面的无线传感器网络的覆盖问题。文献和文献最大的不同就是将无线传感器网络的节点感应区域建模成一个球体(不一定是相同的半径)，并将覆盖问题推广到三维空间来解决，最终得到了可行的多项式求解算法。

Gupta在参考文献[18]中提出的算法是通过选择连接的传感器节点路径来得到最大化的网络覆盖效果。该算法同时属于连接性覆盖中的连接路径覆盖及确定性区域／点覆盖类型。当基站或汇聚中心向无线传感器网络发送一个感应区域查询消息时，连接传感器覆盖的目标是选择最小的连接传感器节点集合并充分覆盖无线传感器网络区域。Gupta分别给出了集中与分布式两种贪婪算法。假设已选择的传感器节点集为M，剩余与M有相交传感区域的传感器节点称为候选节点。集中式算法初始节点随机选择构成M集合之后，在所有从初始节点集合出发到候选节点的路径中选择一条可以覆盖更多未覆盖子区域的路径，并将该路径经过的节点加入M。该算法一直执行到网络查询区域可以完全被更新后的M覆盖为止。如图2-10所示为该贪婪算法执行的方式，在如图2-10(a)所示中，贪婪算法会选择路径P2，得到如图2-10(b)所示，这是由于在所有备选路径中选择B3和B4组成的路径P2可以覆盖更多未覆盖子区域。

该连接传感器网络覆盖的贪婪算法的主要思想是：首先从M中最新加入的候选节点开始执行，在一定范围内广播候选路径查找消息，收到候选路径查找消息的节点判断自身是否为候选节点，如果是，则以单播方式返回发起者一个候选路径响应消息。发起者选择可以最大化增加覆盖区域的候选路径，更新各参数，算法继续执行，直到网络查询区域可完全被更新后的M所覆盖。该算法的优点主要有以下几点。

    ① 节点传感区域模型可以是任意凸形区域，更加符合实际环境。

② 可以灵活地选择使用集中式或分布式方式来实现。

③在保证网络覆盖的同时，考虑了网络的连接性，算法周期执行降低了网络通信代价，并可以延长网络的寿命。


该算法主要缺点是：

    ① 虽然同时考虑了连通性与网络的覆盖性，但不能保证查询返回结果的精度。

  ② 没有考虑实际无线信道中出现的干扰和消息丢失情况。

通常，将无线传感器网络的覆盖和部署配置分为确定性覆盖和不确定性覆盖(或叫随机覆盖)两种，而每种覆盖又分为点覆盖和区域覆盖两种方式。这里仅给出确定性覆盖和部署配置的一种基于贪婪算法的点覆盖算法，其他类型的覆盖和配置算法(如Voronoi图表搜索算法)请读者参考文献[20～22]。

一种基于点覆盖的贪婪无线传感器部署和配置算法伪代码如下；



除了上面介绍的无线传感器网络配置和覆盖控制算法以外，对于覆盖问题的计算，还来自于这样一些实际的应用，如野外动植物或环境监测。假定节点感知距离半径为R′，并且各个节点工作相互独立，共同完成监控面积为A的区域，问究竟要布置多少个节点才能以要求的覆盖概率(覆盖率)实现对该区域的监控?

    先不考虑节点位于边界区而造成节点覆盖面积减小，因每个节点感知和监控整个区域的概率为

，令每个节点覆盖率为P(A)=p，由于各个节点独立覆盖，则M个节点的覆盖率为

，如果给定了传感器感知距离半径R′，则要满足给定覆盖率P要求所需的最少节点数为

。如考虑边界节点影响，存在部分区域A′落在区域A外面，则所需节点数为：

这里仅给出了无线传感器网络覆盖设计的一个参考界，而实际情况存在一定的差异，为保持相应的连接性，可取实际传感器节点数略大于理论值。

综上所述，可以得出无线传感器网络覆盖的一般准则：如已知传感器节点的通信距离，可以通过文献[24]提出的方法得知所需配置的节点数，然后选择适当的感知覆盖半径；同样如已确定传感器感知覆盖半径，可先计算出布置的节点数，然后选择合适的通信距离或调整控制传感器节点功率大小；如通信距离和感知覆盖半径都确定的情况下，只有增加或减少节点数来满足给定的最低连接可靠性和成本设计要求。

最近，国内也有学者对无线传感器网络的覆盖控制问题进行了全面的研究，详细分类总结了近年来提出的各种覆盖控制问题的思想和有代表性的研究成果，着重分析了一些典型的无线传感器网络覆盖控制算法与协议，最后进行了各种算法的比较，探讨了目前无线传感器网络覆盖控制亟待解决的问题，并给出了一些最新的仿真研究成果。如图2-11所示给出了一个无线传感器网络覆盖算法和协议分类。