Efficient Algorithms for Flexible Sweep Coverage in Crowdsensing

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 are 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 (maxSAF), where each participant proposes several routes and the new task is to strategically assign each participant a route among her choices in which way maximizes the total weight of the monitored POIs. In this paper, we first prove 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.