关键词: 移动感知, 任务分配, 近似算法, 多项式时间近似方案, 划分

Abstract: In recent years, mobile phone sensing application has been regarded as a new paradigm which makes use of the smartphones to get the ubiquitous environment data. Most of the mobile phone sensing task assignment problems are based on the locations of the smartphone users. Unfortunately, the location-based optimal task assignment problem in mobile phone sensing system is an NP-hard problem. To solve this challenge, we study the optimal location-based task assignment problem for mobile phone sensing system, and propose a polynomial time approximation algorithm in this paper. The proposed approximation algorithm first introduces the shifting method for unit disk model into the task assignment problem of mobile phone sensing, and divides the sensing area into many sub-areas. We can prove that the union of the optimal task assignment solution in each sub-area is 〖SX(〗1〖〗1+ε〖SX)〗 of the optimal solution in the whole area, which illustrates the presented algorithm is a polynomial-time approximation scheme (PTAS). Then, we also prove that the optimal assignment problem in each sub-area is polynomial-time solvable, and design an enumeration method to get the optimal solution in the sub-area. Finally, the simulation results show that the practical performance of the proposed near optimal task assignment algorithm corroborates the theoretical analysis.

Key words: mobile phone sensing, task assignment, approximation algorithm, PTAS, shifting