相关专题：
近年来，无线传感器网络引起了业界极大关注，其应用环境通常是由价格便宜的传感器节点组成的，每个节点都能够采集、存储和处理环境信息，并且能和邻居节点通过无线链路保持通信。覆盖问题是无线传感器网络配置首先面临的基本问题，因为传感器节点可能任意分布在配置区域，它反映了一个无线传感器网络某区域被监测和跟踪的状况。随着无线传感器网络应用的普及，更多的研究工作深入到其网络配置的基本理论方面，其中覆盖问题就是无线传感器网络设计和规划需要面临的一个基本问题之一。随着深入研究的角度不同，覆盖问题也表述成不同的理论模型，甚至在计算几何里面就能找到与覆盖相关的解决方案。尽管这些办法并不能直接应用到无线传感器网络中，但是研究这些问题有助于建立读者对无线传感器网络覆盖问题相关的理论背景。
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等提出了基于电势场技术的未知环境移动传感器网络的部署配置方法。这种移动传感器网络可通过简易的初始配置就可实现网络的自我配置。网络内的节点可以随意扩展，使得网络覆盖最大化。该配置算法的基本思想就是将传感器节点当做假想的物粒子，且受到势力场的势力。势力压迫节点彼此之间和障碍物之间发生作用力。通过节点的初始简易配置快速地在整个网络扩散，从而最大化网络的覆盖。节点之间除了相互的排斥力外，还受到一个黏性摩擦力。该力用来确保网络最终达到一个静态平衡状态，也就是说所有节点最后都能够完全停止下来。然而，黏性摩擦力不能阻止网络对环境变化的反应。如果节点发生移动，网络就会为变化后的环境自动重新配置，直到再次达到一个静态平衡状态。这样，节点仅仅当需要的时候才改变位置，从而可以节省大量的宝贵能量资源。该算法的核心就是利用了电势场技术，但依赖于一个重要的假设：每个节点的安装传感器都能够确定它的邻居节点及障碍物的距离和方位(可利用扫描激光距离探测仪或全息相机配置适当的传感器)。利用该信息，节点就可知道作用的电势力的大小，并将其转换为控制矢量信息发给传感器的发动机。该算法不需要其他信息，最大的优点就是不需要考虑环境的建模、节点的局部定位和节点彼此之间的通信。因此，该算法具有较高的鲁棒性和扩展性。
