Full-View Area Coverage in Camera Sensor Networks: Dimension Reduction and Near-Optimal Solutions
Full-View Area Coverage in Camera Sensor Networks: Dimension Reduction and Near-Optimal Solutions
复制标题
相机传感器网络中的全视野区域覆盖：降维和近乎最优的解决方案
DOI：
10.1109/tvt.2015.2498281
复制
发表时间：
2016-09-01
影响因子：
6.8
通讯作者：
Sun, Youxian
中科院分区：
文献类型：
--
作者：
He, Shibo;Shin, Dong-Hoon;Sun, Youxian
研究了摄像机传感器网络中全景覆盖的最小数目问题，即如何选择最小数目的摄像机传感器来保证给定区域的全景覆盖。全景区域覆盖是具有挑战性的，因为必须考虑2-D连续区域的全景覆盖。为了应对这一挑战，我们首先研究了全景区域覆盖和全视点覆盖之间的内在几何关系，证明了只要选择一组确保全景覆盖的点，全视域覆盖是可以保证的。这导致了全视点区域覆盖问题的显著降维。其次，我们证明了最小数目全视点覆盖是NP难的，并分别从两个不同的角度提出了两种近似算法：1)通过引入全景覆盖率函数，量化每个摄像机传感器对全景覆盖的贡献，将全视点覆盖问题转化为一个子模集合覆盖问题，并提出了贪婪算法(GA)；2)通过研究全景覆盖与传统覆盖之间的几何关系，提出了一种基于集合覆盖的算法(SCA)。我们分析了这两种近似算法的性能，并刻画了它们的逼近比。此外，我们设计了两个分布式算法，分别获得了与GA和SCA相同的逼近比。最后，我们给出了大量的仿真结果来验证我们的分析。
We study the problem of minimum-number full-view area coverage in camera sensor networks, i.e., how to select the minimum number of camera sensors to guarantee the full-view coverage of a given region. Full-view area coverage is challenging because the full-view coverage of a 2-D continuous domain has to be considered. To tackle this challenge, we first study the intrinsic geometric relationship between the full-view area coverage and the full-view point coverage and prove that the full-view area coverage can be guaranteed, as long as a selected full-view ensuring set of points is full-view covered. This leads to a significant dimension reduction for the full-view area coverage problem. Next, we prove that the minimum-number full-view point coverage is NP-hard and propose two approximation algorithms to solve it from two different perspectives, respectively: 1) By introducing a full-view coverage ratio function, we quantify the “contribution” of each camera sensor to the full-view coverage through which we transform the full-view point coverage into a submodular set cover problem and propose a greedy algorithm (GA); and 2) by studying the geometric relationship between the full-view coverage and the traditional coverage, we propose a set-cover-based algorithm (SCA). We analyze the performance of these two approximation algorithms and characterize their approximation ratios. Furthermore, we devise two distributed algorithms that obtain the same approximation ratios as GA and SCA, respectively. Finally, we provide extensive simulation results to validate our analysis.