Minimum cost collaborative sensing network with mobile phones

Abstract

Mobile phones with a rich set of embedded sensors have been applied in various collaborative sensing applications. In some applications, to encourage mobile phone users performing collaborative sensing tasks, the data demanders may pay mobile phone users. However, none of the existing works takes into account it. In this paper, we study the Minimum Cost of Attaining the Required Data with mobile phones (MCARD) problem in collaborative sensing network. Given sensing regions R = {R <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> , R <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> , ..., R <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</sub> }, the set of requisite data D <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> for each sensing region R <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> and a set of mobile phones M, the MCARD problem is how to select mobile phones to get all the required data such that the total cost on paying mobile phone users is minimized. We first formally define the MCARD problem. Then, we propose an approximation algorithm for the MCARD problem with the determinate trajectories of mobile phones and a heuristic algorithm for that trajectories are unknown respectively. Simulation results demonstrate our algorithms are efficient.