Cost-Fair Task Allocation in Mobile Crowd Sensing With Probabilistic Users

摘要

Mobile crowd sensing (MCS) is a new paradigm for urban-scale monitoring. This article concentrates on the Cost-Fair Task Allocation (CFA) problem for the MCS scenario where the collaboration of multiple probabilistic mobilephone users is needed to yield more reliable observation. CFA aims to allocate sensing tasks to users so that the sensing costs undertaken by all users are as balancing as possible, while the requirement of the requester for data reliability can be satisfied. CFA is greatly important to MCS campaigns in terms of reliability and sustainability. We design two algorithms to solve the CFA problem in the offline and online cases, respectively. Specifically, we propose a novel penalty-based model to reformulate the offline CFA problem, and based on this model, we design an offline algorithm, which can yield a computation-efficient e-solution with any small epsilon > 0. For the online case, we design a polynomial-time approximation algorithm, which struggles to allocate each of the sequentially arriving tasks to users as fairly as possible, and can achieve an upper-bounded competitiveness relative to the optimal CFA solution. Finally, we conduct extensive numeric analyses to validate the performance of our algorithms under diverse experimental setups.