传感器网络适用于监控环境。传感器类似于站在特定位置的守卫人员进行侦察。通常，传感器用它的无线通信组件将其收集的数据传送回网络中的数据收集器（汇聚节点）。传感器可以被用在环境栖息的监测领域[1]，自然灾害监测[2]，森林检测[3]或核辐射检测[4]。传感器也用于医疗中心加快应急响应[5,6]。部署的传感器也可用于本地化用户[7]或检测设备的温度[8]。

传感器节点的放置可以是确定性的或随机的。随机部署不能保证部署传感器完全覆盖的感兴趣区域。我们需要部署更多的传感器来覆盖未被发现的空间[9,10]。使用移动节点是常用的方法。[11,12]。 确定性部署方法考虑覆盖ROI的整个区域在第一时间部署传感器[13-17]。 目标是确定传感器的位置以最小化部署的传感器的数量。找到覆盖整个空间的最小传感器数量是类似于图中着色问题的NP完整问题。我们，建立一个多项式时间可解的问题来近似最优解是这个研究问题的目标。现有的方法总是将传感器放置在可以覆盖最大未覆盖空间的位置。因此，可以减少部署传感器的数量。然而，传感器的感测区域是圆形的。使用贪婪的方法来覆盖整个感兴趣的区域，引入了多个小的隔离区域。传感器必须部署在这些分散的区域以实现全面覆盖。因此，部署了更多的传感器。

本文提出了一种增强的确定性部署方法，称为基于拼图的传感器布置（JSP）算法。传感器从感兴趣区域的周边部署，例如解决拼图。提出的JSP算法可以防止引入隔离区。评估开放空间场景和中心障碍场景。 JSP可以使用较少数量的传感器来覆盖感兴趣的区域。传感器之间的重复覆盖也可以减少。

本文的其余部分组织如下。 相关研究在第2节中进行了评述。第3节给出了JSP的主要思想和减少JSP时间复杂度的方法。 评估结果如第4节所示。最后，第5节给出了结论。

确定性部署方法着重于使用最小数量的传感器来覆盖整个区域利益。 Dhillon等提出了两种方法，称为MAX_AVG_COV和MIN_AVG_COV的算法。ROI区域被分割成nn的网格，并用一个n^2n^2的矩阵来表示任意两个网格之间的探测概率。通过累积以sensor为中心的传感器覆盖的所有相邻网格的概率，对每个网格𝑔进行评分。MAX AVG COV方法选择最高分数网格作为候选位置放置下一个传感器。放置传感器，更新矩阵。 程序继续，直到所有网格都被覆盖。

MAX_AVG_COV方法扫描所有网格并计算其分数。确定部署位置的时间复杂度为𝑂（𝑛^4）。在大型部署区域，对网格进行计算的开销是巨大的。另外，减小网格大小也会产生较高的计算开销。将下一个传感器放置在可以覆盖最多未被覆盖的空间的位置上的这种做法将引入许多小的隔离区域，如图1所示，每个隔离区域都需要一个传感器来覆盖它。为了防止在微小隔离区域上放置附加传感器，提出了MIN AVG COV方法。候选未覆盖网格放置下一个传感器是可以包括最小未覆盖空间的。提出了MIN AVG COV方法来防止产生孤立区域，但成本是部署更多的传感器。 Xu和Sahnialso提出了一种贪心的方法作为MIN AVG COV，但使用整数线性规划公式来发现用异质传感器部署传感器[15]的最低成本位置。

吴等提出了一种DT分数算法[16]利用Delaunay三角测量来确定位置用于放置传感器。DT分数算法由两部分组成阶段。在第一阶段，传感器沿着在其附近产生边界轮廓和消除覆盖孔的障碍物。扫描感兴趣区域中的所有网格以识别障碍物的轮廓。该阶段的时间复杂度为𝑂（𝑛）。第二阶段是重新部署。传感器的新候选位置是通过Delaunay三角测量算法生成的所有三角形的外接圆的中心。所有候选点都得分，下一个传感器放置在获得最多覆盖增益的位置。

Delaunay三角测量算法被应用于连续添加顶点以包括未覆盖空间使得图形三角测量的时间复杂度为𝑂（𝑚） e𝑚是沿障碍物轮廓部署的传感器的数量。呃，DT分数算法需要𝑂（𝑛2log𝑛）时间复杂度来获取放置传感器的候选位置。 e过程重复，直到达到预定的可部署传感器数量。DT分数算法需要𝑂（𝑛2log𝑛）时间复杂度来获取放置传感器的候选位置。 过程重复，直到达到预定的可部署传感器数量。

第一，DT-Score算法计算由Delaunay三角测量算法生成的三角形外接圆的中心作为候选位置。最大半径圆圈的中心是放置下一个传感器的位置。它还产生多个散射隔离区域作为MAX AVG COV方法。靠近障碍物的传感器仅略微缓和了这个问题。因此，Dhillon等人还提出了用于减少隔离区域的MIN AVG COV方法。 eMIN AVG COV方法总是将下一个传感器放置在包含最少未被空间的位置。部署传感器的数量也比MAX AVG COV差。然而，它提供了改进确定性部署方法的动机。如果可以从未覆盖的空间的周边逐个添加传感器，则会减少产生隔离区域的概率。它类似于玩拼图游戏的策略。通过考虑不同的覆盖率，在[17]中提出了类似的方法。

JSP算法：假设所有的传感器有相同的监测半径R。V是包含所有在ROI上未覆盖网格的集合。集合B（属于V）包含了所有边界网格。与MAX_AVG_COV方法相似的是，ROI被分为n*n个网格。每个网格Pij最初分配一个令牌T，T被用于计算每一个网格的分数。T的值被设置为：

算法流程：

（2）是每一个点的打分方法

算法讲解：

1. 最初使用上面的初始化方法初始化
2. 接下来进行打分环节，打分的方式是看在不超过半径的距离中，该网格点包含了多少边 界点。（每个边界点计为1，不是边界点计为0）
3. 选取打分最高的点作为放置传感器的点
4. 更新V集合（因为现在由于已经选择了传感器点，那么在这个传感器半径内的点都是完全可监测的点。）
5. 更新B集合（也就是边界点集合）
6. 一直重复该过程直到点分完

以下是示例：

JSP算法

JSP的时间复杂度也与网格数量成正比。 让网格大小为𝑔^2。𝑉中的所有网格都需要打分。 每个网格需要扫描包括传感器的感测区域的矩形以累积令牌。矩形为（𝑅/𝑔）∈𝑂（𝑅）面积。 设置𝑉的初始网格数为𝑛×𝑛，在传感器的部署后会逐渐减少。 𝑉中的平均网格下降率为δ，范围为1〜𝑅^2/𝑔2。 时间复杂度可以表示为递归关系T（n^2）。 时间的复杂度是O（n^4*R2)，计算公式如下：

改进的JSP算法：

其核心思想是在一个传感器节点被防止后，并不是对所有在V中的点都进行更新，而是更新那些与传感器节点位置相差2R的点

引用的文献：