Coverage-Aware Stable Task Assignment in Opportunistic Mobile Crowdsensing

In opportunistic mobile crowdsensing, the objective of service requesters is to have as many of their sensing tasks completed as possible within their budget constraints, whereas that of participants (workers) is to collect the highest monetary reward possible on their trajectories. However, these objectives can conflict and may result in unhappy service requesters or workers if the matching between them is not handled carefully. In this paper, we study the problem of finding task assignments that fulfill both coverage-aware preferences of service requesters and profit-based preferences of workers in a budget-constrained, opportunistic mobile crowdsensing system. Since this is a matching problem with bilateral preferences, we aim to find a matching in which everyone is satisfied with their assignment based on their preference profile. We first propose a polynomial-time approximation algorithm for general settings, and then show that a slightly modified version of this algorithm has a constant approximation ratio when the rewards offered to workers by service requesters are proportional to the coverage capability of workers for corresponding tasks. Through extensive simulations, we evaluate the performance of our algorithms in different settings, and show that they mostly provide substantially better task assignments in terms of user happiness and coverage quality while having a few orders of magnitude lower running times compared to the benchmark algorithms.