论文标题
通过点和设置分类降低传感器目标覆盖问题的复杂性
Reducing the Complexity of the Sensor-Target Coverage Problem Through Point and Set Classification
论文作者
论文摘要
在具有给定形状的一组平面中覆盖随机点的问题在通信和操作研究中具有多种实际应用。一种特别突出的应用是通过无线传感器网络中随机划分的传感器对随机关注点的覆盖范围。在本文中，我们考虑了包含随机放置点（表示关注点）的大面积的状况，以及在同一区域（代表单个传感器的覆盖面积）中许多随机位置相等的磁盘。发现覆盖给定点的最小磁盘的最小磁盘的问题已知是NP完整的。我们表明，可以通过将磁盘分类为几个确定的类，这些分类可以降低计算复杂性，这些类别可以表征为必要，不可排除或不确定。然后，问题可以减少为仅考虑不确定的集合及其涵盖的点。此外，不确定的集合及其覆盖的点可能会分为``岛屿''，可以分开解决。因此，实际复杂性取决于最大岛屿的点和集合的数量。我们运行许多模拟，以显示各种类型的集合和点的比例如何取决于与点和集密度相关的两个基本规模不变参数。我们表明，即使在点和设定密度相对较高的情况下，复杂性也可以实现。
The problem of covering random points in a plane with sets of a given shape has several practical applications in communications and operations research. One especially prominent application is the coverage of randomly-located points of interest by randomly-located sensors in a wireless sensor network. In this article we consider the situation of a large area containing randomly placed points (representing points of interest), as well a number of randomly-placed disks of equal radius in the same region (representing individual sensors' coverage areas). The problem of finding the smallest possible set of disks that cover the given points is known to be NP-complete. We show that the computational complexity may be reduced by classifying the disks into several definite classes that can be characterized as necessary, excludable, or indeterminate. The problem may then be reduced to considering only the indeterminate sets and the points that they cover. In addition, indeterminate sets and the points that they cover may be divided into disjoint ``islands'' that can be solved separately. Hence the actual complexity is determined by the number of points and sets in the largest island. We run a number of simulations to show how the proportion of sets and points of various types depend on two basic scale-invariant parameters related to point and set density. We show that enormous reductions in complexity can be achieved even in situations where point and set density is relatively high.
