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

杜扬; 黄河; 孙玉娥; 李凡长; 朱艳琴; 黄刘生

doi:10.7544/issn1000-1239.2014.20131070

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

¹(苏州大学计算机科学与技术学院江苏苏州 215006)
²(苏州大学城市轨道交通学院江苏苏州 215137)
³(中国科学技术大学计算机科学与技术学院合肥 230027)
⁴(中国科学技术大学苏州研究院江苏苏州 215123) (huangh12@suda.edu.cn)

基金项目: 国家“九七三”重点基础研究发展计划基金项目(2011CB302905)；国家自然科学基金项目(61202028,61303206)；教育部高等学校博士学科点专项科研基金项目(20123201120010)；广东省普及型高性能计算机重点实验室开放课题(SZU-GDPHPCL-2012-01)

详细信息

中图分类号: TP393; TN92
计量
- 文章访问数: 1452
- HTML全文浏览量: 0
- PDF下载量: 1103
出版历程
- 发布日期: 2014-10-31

A Location-Based Task Assignment Mechanism for Mobile Phone Sensing

¹(School of Computer Science and Technology, Soochow University, Suzhou, Jiangsu 215006)
²(School of Urban Rail Transportation, Soochow University, Suzhou, Jiangsu 215137)
³(School of Computer Science and Technology, University of Science and Technology of China, Hefei 230027)
⁴(Suzhou Institute for Advanced Study, University of Science and Technology of China, Suzhou, Jiangsu 215123)

摘要

摘要: 随着智能手机应用的普及，移动感知技术已被认为是一种高效且成本低廉的环境数据收集方式.移动感知系统中地理位置相关的最优任务分配问题是一个NP难问题.为了解决该问题，提出了一种多项式时间的近似最优的任务分配算法.该算法首先引入了单位圆盘模型中移动划分的思想，将整个监测地理空间划分为若干个子区间，并使得子区间内的最优分配方案的集合是划分前最优解的〖SX(〗1〖〗1+ε〖SX)〗，这表明所设计的近似算法是一个多项式时间近似机制.随后，证明了最优任务分配问题在每个子区间内是多项式时间可解的，并设计了枚举算法求出该问题的最优解.最后，仿真实验结果表明所设计的近似最优任务分配算法的实际性能与理论分析相吻合.
- 移动感知 /
- 任务分配 /
- 近似算法 /
- 多项式时间近似方案 /
- 划分
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.
- mobile phone sensing /
- task assignment /
- approximation algorithm /
- PTAS /
- shifting

HTML全文

参考文献(0)

施引文献(14)

期刊类型引用(7)

1.	姜磊，章小卫. 基于模糊隶属度邻域覆盖的三支分类决策. 计算机应用与软件. 2024(02): 271-278 . 百度学术
2.	骆公志，张尚蕾. 基于正区域和投票式属性重要度的特征提取算法. 南京邮电大学学报(自然科学版). 2024(01): 79-89 . 百度学术
3.	王笑笑，巴婧，陈建军，宋晶晶，杨习贝. 超约简求解：效率与性能的提升. 计算机科学. 2023(02): 166-172 . 百度学术
4.	刘长顺，刘炎，宋晶晶，徐泰华. 基于论域离散度的属性约简算法. 山东大学学报(理学版). 2023(05): 26-35+52 . 百度学术
5.	张清华，艾志华，张金镇. 融合密度与邻域覆盖约简的分类方法. 陕西师范大学学报(自然科学版). 2022(03): 33-42 . 百度学术
6.	沈毅波. RBF神经网络在关联数据一致性挖掘中的应用. 福建电脑. 2022(08): 5-9 . 百度学术
7.	周长顺，徐久成，瞿康林，申凯丽，章磊. 一种基于改进邻域粗糙集中属性重要度的快速属性约简方法. 西北大学学报(自然科学版). 2022(05): 745-752 . 百度学术