Quality-Aware Sensing Coverage in Budget-Constrained Mobile Crowdsensing Networks
Quality-Aware Sensing Coverage in Budget-Constrained Mobile Crowdsensing Networks
复制标题
DOI：
10.1109/tvt.2015.2490679
复制
发表时间：
2016-09
影响因子：
6.8
通讯作者：
Maotian Zhang;Panlong Yang;Chang Tian;Shaojie Tang;Xiaofeng Gao;Baowei Wang;Fu Xiao
中科院分区：
文献类型：
--
作者：
Maotian Zhang;Panlong Yang;Chang Tian;Shaojie Tang;Xiaofeng Gao;Baowei Wang;Fu Xiao
移动的群体感知在数据收集方面显示出出色的能力，并产生了许多应用。在覆盖质量的意义上，边际工程已经考虑了高效（更少的成本）和有效（相当大的覆盖范围）的设计移动的人群感知网络。研究了移动的人群感知网络中质量感知的最优覆盖问题。我们与传统的覆盖问题之间的区别在于，我们只选择一个子集的移动的用户，使覆盖质量最大化与有限的预算。为了解决这个新的问题，这被证明是NP-难的，我们首先证明了覆盖质量的集合函数是非减子模。利用子模优化的有利性质，我们提出了一个（1 -（1/e））近似算法，时间复杂度为O（nk+2），其中k是一个整数，大于或等于3。最后，我们进行了广泛的模拟所提出的计划，结果表明，我们优于随机选择方案和最先进的一个方面的总覆盖质量，最多，2.4倍和1.5倍，平均，1.4倍和1.3倍，分别。此外，我们实现了一个接近最优的解决方案，与蛮力搜索结果相比。
Mobile crowdsensing has shown elegant capacity in data collection and has given rise to numerous applications. In the sense of coverage quality, marginal works have considered the efficient (less cost) and effective (considerable coverage) design for mobile crowdsensing networks. We investigate the optimal quality-aware coverage in mobile crowdsensing networks. The difference between ours and the conventional coverage problem is that we only select a subset of mobile users so that the coverage quality is maximized with constrained budget. To address this new problem, which is proved to be NP-hard, we first prove that the set function of coverage quality is nondecreasing submodular. By leveraging the favorable property in submodular optimization, we then propose an (1 - (1/e)) approximation algorithm with O(nk+2) time complexity, where k is an integer that is greater than or equal to 3. Finally, we conduct extensive simulations for the proposed scheme, and the results demonstrate that ours outperforms the random selection scheme and one of the state of the art in terms of total coverage quality by, at most, 2.4× and 1.5× and by, on average, 1.4× and 1.3×, respectively. Additionally, ours achieves a near-optimal solution, compared with the brute-force search results.