论文笔记——Sensor Placement for Effec
摘要 - 我们提出了两种算法，用于传感器领域中传感器的高效放置。所提出的方法旨在优化传感器的数量并确定它们的位置以支持分布式传感器网络。由于与传感器检测相关的不确定性，优化框架是固有的概率性的。所提出的算法在不精确检测和地形属性的约束下，对覆盖优化进行了定位。这些算法的目标是平均覆盖面以及最大限度地提高最脆弱网格点的覆盖面。网格点的优先覆盖问题（基于安全性和战术重要性的相对措施）也被建模。具有障碍物的示例传感器场的实验结果表明我们的方法的应用。
传感器布置直接影响资源管理以及必须用分布式传感器网络中感测数据执行的后端处理和开发的类型。传感器资源管理中的一个关键挑战是确定优化成本的传感器现场架构，并提供高传感器覆盖率，对传感器故障的恢复能力以及适当的计算/通信权衡。智能传感器放置有助于传感器/开发系统的统一设计和操作，并减少对过度的网络通信进行监视，目标定位和跟踪的需要。传感器放置因此在前端感测和后端开发之间形成必不可少的“胶”。
在这项工作中，我们提出了一个在需要覆盖足够传感器范围的网格的限制下，对资源有限的传感器资源管理优化框架。所提出的方法提供了分布式传感器网络的独特的“简约”想法（这里指的就是在满足可工作的条件下，使用最少的资源），其中部署了最少数量的传感器，并且它们传送/报告最小量的感测数据。智能传感器的放置确保该数据的集合包含足够的信息，用于数据处理中心随后查询少量传感器以获取详细信息，例如，图像和时间序列数据。所提出的方法旨在优化传感器的数量及其在网络配置中的布局，并支持这样的简约传感器网络。
传感器部署必须考虑到地形的性质，例如红外传感器视线中的建筑物和树木等障碍物，丘陵地带的不平坦表面和高程，传感器故障的可能性造成的冗余以及所需的电力在部署的传感器之间以及部署的传感器和集群头之间传输信息。
我们将传感器场表示为一个网格（二维或三维）点。因此，传感器领域中的目标是一个逻辑对象，它由一组可以看到它的传感器表示。不规则传感器场被建模为网格集合。然而，由于与传感器检测相关的不确定性，优化框架本质上是概率性的。我们提出了两种用于传感器布置的算法，在不精确检测和地形属性的约束下解决覆盖优化问题。网格点的优先覆盖问题（基于安全性和战术重要性的相对措施）也被建模。我们将本文的讨论限于固定传感器。具有障碍物的示例传感器场的实验结果表明我们的方法的应用。
随着传感器在现场操作中的使用越来越多，高效的部署策略越来越重要。运动规划的地形模型获取的相关工作集中在机器人在未开发的“传感器领域”的运动[1]。虽然地形的知识对于监视至关重要，但它并不直接解决传感器放置问题。 [8]提出了基于潜在领域概念的移动传感器的自我部署。然而，自我部署不能为需要部署在特定配置中的静态传感器提供解决方案，以用于环境监控等应用。无线传感器网络中的一个相关问题是空间定位[9]。当确定性地部署传感器时，本地化尤其重要，例如，当传感器从战场上的飞机投掷时，以及由于漂移可能移动的水下传感器。最近提出了一些用于精细和粗粒度定位的技术[6,10]。
在文献[7]中还讨论了确定传感器给定放置提供的覆盖范围的问题。传感器放置在二维和三维网格上已被公式化为组合优化问题，并使用整数线性规划求解[2,3]。这种方法有两个主要缺点。首先，计算复杂度使得该方法对于大问题实例不可行。第二，电网覆盖方法依赖于“完美”传感器检测，即传感器预期在每种情况下产生二进制的是/否检测结果。传感器读数存在固有的不确定性，因此必须对传感器检测进行概率建模。
传感器放置问题与艺术画廊问题（AGP）在艺术画廊定理[4]中存在着非常相似的关系。 AGP问题可以非正式地说明为确定覆盖艺术画廊内部所需的最少卫兵数量。我们的传感器放置问题与AGP的不同之处有两个基本的方面：（a）传感器可以具有不同的范围，不同于在AGP中，卫星被假设具有相似的能力，（b）与卫兵的入侵者检测不同，传感器检测结果是概率性的。其他相关工作包括放置一定数量的传感器以降低通信成本[5]，以及给定目标分布的最佳传感器放置。
本文的其余部分组织如下。在第2节中，我们描述了我们的传感器检测模型以及我们对地形建模的方法。第3节描述了放置传感器以提供传感器场的足够覆盖的两个程序。我们还展示了如何增加放置算法以提供网格点的差异覆盖（基于安全性和战术重要性的相对度量）。第4节介绍了各种问题实例的实验结果。提出了随机传感器放置和传感器均匀放置的比较，以突出所提出的算法的有效性。最后，第5节总结了本文，并描述了未来工作的方向。
II. SENSOR AND TERRAIN MODEL
传感器放置需要准确但计算可行的传感器检测模型。在这项工作中，我们首先假设传感器场由网格点组成。网格的粒度（连续网格点之间的距离）由传感器放置所需的准确度决定。
我们假设传感器检测目标的概率随着目标和传感器之间的距离而呈指数级变化。该模型在图1中示出。来自传感器的距离d处的目标由具有概率e^-αd的传感器检测。参数α可用于对传感器的可靠性和其检测概率随距离减小的速率进行建模。显然，如果目标位置和传感器位置重合，检测概率为1。对于传感器场中的每两个网格点i和j，我们将两个概率值相关联：（i）pij，其表示网格点i处的传感器在网格点j处检测到的目标的概率; （ii）pji，其表示在网格点j处由传感器检测到网格点i处的目标的概率。在没有障碍物的情况下，这些值是对称的，即pij = pji。然而，我们将在本节稍后展示这些值在存在障碍物时不必相等。
注意，传感器检测模型的选择不会以任何方式限制放置算法的适用性。检测模型仅仅是放置算法的输入参数。因此可以考虑替代检测模型，而不需要重新设计放置算法。
接下来，我们将介绍如何在这个框架中模拟地形中的障碍。多个传感器，例如红外摄像机，需要一个目标躺在他们的视线。障碍物引起闭塞并使这种传感器对检测无效。我们假设在传感器放置之前获取一些关于地形的知识，例如。通过卫星图像。然后通过改变适当的网格点对的检测概率来建模障碍物。例如，如果诸如建筑物或树叶的对象存在于从网格点i到网格点j的视线中，则我们设置pij = 0。部分遮挡也可以通过设置非零但小的检测概率的值。
例如，考虑图2传感器领域的两个障碍物。该图中的网格点从1到16进行编号。如果我们假设这些障碍是对称的，那么它们会导致p36，p63，p27，p72和许多其他检测概率要呈现为零。直接确定对于任何两个网格点i和j，pij是否受到障碍物的影响。每个网格点与平面中的一对（x，y）坐标相关联。类似地，障碍物还具有关联（x，y）坐标。我们确定连接i和j的直线的方程。如果障碍物的坐标满足该等式，则将概率pij设置为零。
在许多实际情况下，传感器场中的障碍物是不对称的，即pij = 0并不意味着pji = 0。这可能发生在例如丘陵地带的情况下。较低仰角的传感器不太可能在较高仰角处检测到目标，但是在较高仰角处的传感器可以在较低高度检测目标。通过使用适当的检测概率值，可以在我们的框架中轻松建模这种情况。
III. SENSOR PLACEMENT ALGORITHMS
在本节中，我们描述了传感器领域（无论是否有障碍物）中给定的一组检测概率的传感器放置算法。传感器放置算法的目标是确定传感器的最小数量及其位置，以便每个网格点都以最小置信度水平覆盖。我们使用术语覆盖阈值来引用这个置信水平。提供覆盖阈值T作为放置算法的输入。我们的目标是确保每个网格点的概率至少为T。
第一个程序MAX_AVG_COV尝试最大化网格点的平均覆盖。第二个程序MAX_MIN_COV尝试最大限度地提高覆盖率最小的网格点。
我们首先为传感器场中的所有网格点对生成传感器检测矩阵D =[pij]。对于n×n网格，我们共有n2个网格点，因此矩阵D由n2行和n2列组成，总共包含n4个元素。
从传感器检测矩阵D，我们确定未知概率矩阵M = mij，其中mij = 1-pij。我们不会在传感器放置算法中直接使用D。相反，我们使用未命中概率矩阵M。传感器放置算法都使用贪心启发式来一次确定一个传感器的最佳位置。算法是迭代的，并且它们在每次迭代期间将一个传感器放置在传感器场中。当达到传感器数量的预设上限，或者达到网格点的足够覆盖时，它们终止。
我们将矢量M * =（M1，M2，...，MN）定义为传感器场中N = n^2个网格点的遗漏概率集合。该矢量中的Mi表示网格点i未被集成在传感器场中的传感器集合覆盖的概率。在放置算法开始时，矢量M被初始化为全1矢量，即M * =（1,1，...，1）。放置在传感器区域中的每个传感器减少该矢量中的一个或多个Mi。当遗漏概率矩阵中的相应行和列变得多余时，传感器的放置也将遗漏概率矩阵的顺序降低1。第一传感器放置算法MAX_AVG_COV的伪代码步骤在图3中概述。令Mmin = 1-T是任何网格点允许的未命中概率的最大值。
请注意，通过Σi参数在MAX_AVG_COV过程中测量由附加传感器引起的电网覆盖的有效性。这种方法尝试通过对各个网格点的遗漏概率的变化求和来评估附加传感器的全局影响。接下来我们将介绍传感器布置方法如何有助于网格点的优先覆盖。在典型的军事力量保护或民防方案中，必须给予某些装置额外的保护。这样的设施可能包括核电厂，指挥总部或民政管理中心。
为了模拟优先覆盖，我们为每个网格点i分配不同的保护概率pri。网格点i的未知概率阈值则表示为Mimin = 1-pri。程序MAX_AVG_COV被修改为使得重复/直到循环的终止标准基于检查已经达到每个网格点的各个未知概率阈值。
传感器放置的另一种方法是将传感器放置在栅格点的每次迭代处，覆盖面最小。 （第一个传感器随机放置在网格中）然后计算每个网格点的覆盖范围，并将下一个传感器放置在网格中的最小覆盖点。这个过程一直持续到所有的传感器都被放置，或者超出了覆盖范围上的预定阈值。传感器放置算法MAX_MIN_COV的伪代码步骤如图4所示。
个人观点：两者的区别是上面一种算法将传感器放在使得全局降低最多的地方，而这种算法则放在覆盖率最低的地方。
MAX_AVG_COV和MAX_MIN_COV算法的计算复杂度为O（kN），其中k是给定覆盖阈值所需的传感器数量。由于k不是先验知道的，我们使用N作为k的上限，并获得O（N^2）的计算复杂度。
MAX_AVG_COV和MAX_MIN_COV算法的伪代码描述使得传感器检测是独立的隐式假设，即如果传感器以概率p1在网格点处检测到目标，并且另一个传感器以概率p2在该网格点处检测到相同的目标，则目标的未命中概率为（1- p1）（1- p2）。
迄今为止，我们已经考虑了传感器领域中只有网格点的覆盖范围。为了提供传感器场的稳健覆盖，我们还需要确保位于网格点之间的区域被充分覆盖，即每个非网格点的故障概率小于阈值Mmin。考虑图5中位于正方形四角的四个网格点。让这些网格点之间的距离为d *。平方对角线的交点与四个网格点的距离为d * /√2。以下定理提供了足够的条件，在该条件下，非栅极点被MAX_AVG_COV和MAX_MIN_COV算法充分覆盖。
定理1：使网格点P1和潜在传感器位置P2之间的距离为d。让相邻网格点之间的距离为d *。如果使用d + d * /√2的值来计算由于传感器在P2处的网格点P1的覆盖范围，并且可用传感器的数量是足够的，则所有非网格点的未命中概率小于算法MAX_AVG_COV和MAX_MIN_COV终止时的阈值Mmin。
证明：考虑图5中的四个网格点。平方的中心，即对角线的交点与四个网格点中的每一个距离为d * /√2。每个其他非网格点距离四个网格点中的至少一个更短的距离（小于d * /√2）。因此，如果使用d + d * /√2的值来确定MAX_AVG_COV和MAX_MIN_COV算法中的覆盖范围，则可以保证每个非网格点以超过1 Mmin的概率被覆盖。
为了说明定理1，我们考虑一个8乘8格，α= 0.6，Mmin = 0.4。我们使用定理1和MAX_AVG_COV算法来确定传感器位置，并计算所有正方形中心的遗漏概率。图6所示的结果表明，遗漏概率总是小于阈值Mmin，从而确保对非网格点的充分覆盖。
在本节中，我们提出了两种传感器放置算法的实验结果。我们首先确定传感器位置，以最小化给定覆盖阈值的传感器数量。我们将MAX_AVG_COV和MAX_MIN_COV与传感器的随机放置以及均匀放置进行比较。我们使用定理1来保证所有非网格点都被充分覆盖。我们的第一个观察是，如果传感器领域没有障碍物，并且所有的传感器被认为是相同的，则随机放置与MAX_AVG_COV一样有效。这不是意想不到的，因为这些问题实例的规律性使得它们特别适合随机放置。我们接下来显示，当传感器场包含障碍物并且需要优先覆盖时，随机放置执行得更差。
