ISSN 1000-1239 CN 11-1777/TP

• 网络技术 •

### 地理位置相关移动感知系统任务分配问题研究

1. 1(苏州大学计算机科学与技术学院 江苏苏州 215006);2(苏州大学城市轨道交通学院 江苏苏州 215137);3(中国科学技术大学计算机科学与技术学院 合肥 230027);4(中国科学技术大学苏州研究院 江苏苏州 215123) (huangh12@suda.edu.cn)
• 出版日期: 2014-11-01
• 基金资助:
基金项目：国家“九七三”重点基础研究发展计划基金项目(2011CB302905)；国家自然科学基金项目(61202028,61303206)；教育部高等学校博士学科点专项科研基金项目(20123201120010)；广东省普及型高性能计算机重点实验室开放课题(SZU-GDPHPCL-2012-01)

### A Location-Based Task Assignment Mechanism for Mobile Phone Sensing

Du Yang1, Huang He1, Sun Yue2, Li Fanzhang1, Zhu Yanqin1, Huang Liusheng3,4

1. 1(School of Computer Science and Technology, Soochow University, Suzhou, Jiangsu 215006) ; 2(School of Urban Rail Transportation, Soochow University, Suzhou, Jiangsu 215137); 3(School of Computer Science and Technology, University of Science and Technology of China, Hefei 230027); 4(Suzhou Institute for Advanced Study, University of Science and Technology of China, Suzhou, Jiangsu 215123)
• Online: 2014-11-01

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.