Trajectory segment selection with limited budget in mobile crowd sensing

Mobile Crowd Sensing is an emerging paradigm, in which a large number of participants are involved to complete a sensing task under a certain incentive mechanism. Hence, when the budget used to pay participants is limited, how to choose the most appropriate participants becomes a critical problem. Most of existing works aim to select a subset of participants to maximize the coverage, without considering redundancy. There are two kinds of redundancy in the existing literature, one is brought by the incomplete coverage assessment, while the other one is brought by the traditional participant selection process. Since paying for redundant data leads to budget waste, existing works cannot solve the participant selection problem commendably under limited budget. To address such issues, we first propose a coverage assessment considering both uniform coverage and maximum coverage, then design a trajectory segment selection scheme. Rather than choosing the whole trajectory of a participant, our scheme selects certain segments. Both offline and online algorithms are proposed in this paper. Two benchmarks are implemented and we carry out extensive experiments based on a real dataset. The evaluation results prove the effectiveness and the advantage of our algorithms in terms of the coverage quality.