基于Voronoi图的优化方法

文献（Heo and Varshney，2005；Wang et al.，2004a；Cortes et al.，2004）考虑了采用基于Voronoi图来实现传感器自部署。Voronoi图（Aurenhammer and Klein，XXXX）是一种广泛应用于不同领域的计算几何结构。它使用给定节点p₁，…，p_n将平面分为n个Voronoi区。每个区仅包含一个作为生成节点的节点。节点p_i的Voronoi区V_i是比其他节点更靠近p_i的点区。也就是说，V_i={q∈Q|‖q-p_i‖≤‖q-p_j‖，∀j≠j}，其中Q代表整个平面。图10-6给出了3个Voronoi图。

基于Voronoi图的自部署方案思路非常简单：通过尽可能使其传感器的感知范围对准其Voronoi区，传感器运动的目标是实现其局部未覆盖面积最小化（等价于说，最大化其感知有效面积）。通常情况下，这种方法包括多轮对准，且当无法实现更大增益（如参考文献（Heo and Varshney，2005）中的效用增益和参考文献（Wang et al.，2004a）中的覆盖增益）时终止。现有基于Voronoi图的算法仅在节点对准方法上有所区别。在参考文献（Heo and Varshney，2005）中，节点移动到能够实现效用指标最大化的点处，该点被定义为节点有效面积与节点生存时间估计值的乘积。在参考文献（Wang et al.，2004a）中，节点向最远的Voronoi顶点运动通信范围的一半，或到达所谓的极大极小点。在参考文献（Cortes et al.，2004）中，节点移动到其Voronoi多边形的加权质心。下面，我们详细说明参考文献（Cortes et al.，2004）中的工作。

图10-6 基于Voronoi图的方法

a）初始分布 b）瞬时分布 c）最终分布(www.xing528.com)

参考文献（Cortes et al.，2004）研究了机器人网络中的覆盖控制问题。机器人的覆盖能力可由一个位置和预期效用的函数来定义。简单起见，我们考虑仅包含一个源，实现源的组总覆盖最大化。区域覆盖仍然非常重要，因为效用函数代表了机器人网络覆盖源附近事件的能力。假定每个机器人知道其自身和其Voronoi邻居的位置。它还负责Voronoi区内的测量工作。目标是控制机器人的运动，实现检测概率最大化。例如，某个事件的检测概率可能会随着到事件的平方距离增大而降低。

机器人从最初位置运动到能够优化其集体监测能力的最终位置。提出的算法（Cortes et al.，2004）是以迭代方式运行的。当机器人移动时，它更新其Voronoi多边形。Voronoi多边形的质心可通过高斯密度函数进行计算，该函数代表远离源的位置监测能力降低。因此，每个Voronoi多边形中的这些加权质心，比Voronoi多边形的几何中心（它位于当前机器人位置）更接近源。这些位置也与相邻机器人的位置有关。机器人向对应Voronoi多边形的质心运动。它们预计在最终位置融合。在图10-6的实例中，源用黑星标记。机器人的初始位置和最终位置分别如图10-6a和图10-6c所示，图10-6b给出了瞬时节点分布。

基于Voronoi图的方法，需要反复构建Voronoi图，来反映节点的运动。由于Voronoi图构建需要进行全局计算，因而这种方法消息开销大。为了避免振荡（即在几个点之间来回移动），在这些算法中，节点根据特定策略，需要及早停止运动。但是，及早停止运动可能会带来覆盖冗余和形成空穴。