Task reduction using regression-based missing data imputation in sparse mobile crowdsensing.

Mobile Crowd Sensing (MCS) involves allocation of sensing tasks associated with an area of interest to a crowd of participants over time. Consequently, the collective amount of time and energy spent on sensing can be quite large. Sparse Mobile Crowd Sensing (Sparse-MCS) aims at reducing this overhead by reducing the number of sensing tasks, which results in obtaining sensed values from only some portions of the area or time. For those portions which are not thus covered, their corresponding values can be inferred from the collected sensed values. Hence, missing data inference is an integral part of Sparse-MCS. This study is divided into two phases: First, we explore the viability of using machine learning, viz., regression for missing data inference in Sparse-MCS. Hence, we explore several representative regression algorithms such as Linear Regression, LASSO, Elastic Net, Ridge, Decision Tree (DT), Random Forest (RF) and KNN. Using two real data-sets, we conclude that some algorithms such as DT and RF exhibit good performance (giving normalized mean absolute error much less than 0.1 most of the time) whereas the rest do not. Moreover, we compare these techniques with a state-of-the-art missing data inference method known as Compressing Sensing with the help of simulation results. Next, we propose a divide-and-conquer polynomial-time algorithm for task reduction which is based on the proposed inference approach. We also present the results of the analysis of the algorithm in terms of: (i) its time complexity, and (ii) lower and upper bounds on task reduction. [ABSTRACT FROM AUTHOR]