Min-Max Planning of Time-Sensitive and Heterogeneous Tasks in Mobile Crowd Sensing
Hao Wang, Dong Yang Zhao, Huadóng Ma, Lige Ding · 2018
With the explosive growth of mobile devices such as smartphones, it is convenient for participants to perform mobile crowd sensing (MCS) tasks. It is a useful way to recruit participants to perform location-dependent tasks. We first propose Min-Max Task (MMT) planning problem in MCS systems, considering time-sensitivity and heterogeneity of sensing tasks. In other words, how to design a cooperation scheme, in which the participants spend as little time as possible. Then, to address MMT problem, we propose a Memetic based Bidirectional General Variable Neighborhood (MBGVN) algorithm, in which all tasks are separated into groups and traveling path is designed for each participant. Finally, extensive experiments are conducted to demonstrate the benefits of our scheme, outperforming other similar state-of-the-art algorithms.