A Task Assignment Method for Sweep Coverage Optimization Based on Crowdsensing

Abstract

One of the keys for the success of sweep coverage is to organize the participants to patrol effectively in large-scale target areas in order to satisfy the quality requirements of the sweep tasks. In this article, we first analyze the possibility of applying crowdsensing technology for sweep coverage and propose a framework to solve the problem of arranging participants to sweep large-scale target areas when the quality requirements change dynamically over time. First, this problem is formulated as a task assignment problem with the goal of maximizing social welfare. Then, we establish a sweep coverage quality model for the area, which is a different approach from conventional methods that focus on the point of interest (PoI), and we propose a participant incentive model that considers the sustainability of the crowdsensing platform. Since determining the optimal assignment solution is an NP-hard problem, we design two approximate algorithms to arrange participants with the goal of maximizing social welfare; these are the participant-task oriented search (PTOS) algorithm based on a two-stage greed search and the bipartite graph-based participant search (BGPS) algorithm. We evaluate our methods using a population density map dataset from real-world cities as the large-scale target area and create dynamic task requirements for the sweep coverage. The experimental results show that the performance of our two algorithms is significantly better than the performance of the baseline algorithm.