Efficient algorithms for flexible sweep coverage in crowdsensing
Journal article
Huang, Peihuang, Zhu, Wenxing, Liao, Kewen, Sellis, Timos, Yu, Zhiyong and Guo, Longkun. (2018). Efficient algorithms for flexible sweep coverage in crowdsensing. IEEE Access. 6, pp. 50055-50065. https://doi.org/10.1109/ACCESS.2018.2868931
Authors | Huang, Peihuang, Zhu, Wenxing, Liao, Kewen, Sellis, Timos, Yu, Zhiyong and Guo, Longkun |
---|---|
Abstract | Sweep coverage is an important covering technique in mobile crowdsensing, in which users or participants are employed to periodically monitor a set of points of interest (POIs) each with a weight indicating the value of its information to be collected. Traditionally, each user proposes a route along which there is a set of POIs to be monitored. The task is to select a set of participants such that the total weight of the monitored POIs is maximized. However, in real applications, users should have the flexibility to offer several preferred routes. This arises our studied maximum sweep assignment problem with flexibility, where each participant proposes several routes, and the new task is to strategically assign each participant a route among their choices in which the way maximizes the total weight of the monitored POIs. In this paper, we first prove that the problem is NP -complete and then devise two novel approximation algorithms with ratios 0.5 and 0.632. Experiments are also conducted to evaluate algorithms’ practical performance. The results demonstrate that the proposed approximate methods are significantly faster (with up to two orders of magnitude runtime reduction) than the exact integer linear programming solution. In addition, we theoretically study another flexible sweep coverage model in which it costs to hire each user, and the goal is to cover all POIs multiple times (for more complete and accurate information) while minimizing the total hiring cost. |
Keywords | sweep assignment; N P-complete; flexibility; crowdsensing; sensor networks |
Year | 2018 |
Journal | IEEE Access |
Journal citation | 6, pp. 50055-50065 |
Publisher | Institute of Electrical and Electronics Engineers Inc. |
ISSN | 2169-3536 |
Digital Object Identifier (DOI) | https://doi.org/10.1109/ACCESS.2018.2868931 |
Scopus EID | 2-s2.0-85052871134 |
Research or scholarly | Research |
Page range | 50055-50065 |
Publisher's version | License All rights reserved File Access Level Controlled |
Output status | Published |
Publication dates | |
Online | 06 Sep 2018 |
Publication process dates | |
Accepted | 03 Sep 2018 |
Deposited | 13 Jan 2022 |
https://acuresearchbank.acu.edu.au/item/8x473/efficient-algorithms-for-flexible-sweep-coverage-in-crowdsensing
Restricted files
Publisher's version
91
total views0
total downloads1
views this month0
downloads this month