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

发布时间：2018-05-12 14:18

  本文选题：移动感知 + 任务分配　； 参考：《计算机研究与发展》2014年11期

【摘要】：随着智能手机应用的普及,移动感知技术已被认为是一种高效且成本低廉的环境数据收集方式.移动感知系统中地理位置相关的最优任务分配问题是一个NP难问题.为了解决该问题,提出了一种多项式时间的近似最优的任务分配算法.该算法首先引入了单位圆盘模型中移动划分的思想,将整个监测地理空间划分为若干个子区间,并使得子区间内的最优分配方案的集合是划分前最优解的1/1+ε,这表明所设计的近似算法是一个多项式时间近似机制.随后,证明了最优任务分配问题在每个子区间内是多项式时间可解的,并设计了枚举算法求出该问题的最优解.最后,仿真实验结果表明所设计的近似最优任务分配算法的实际性能与理论分析相吻合.
[Abstract]:With the popularity of smart phone applications, mobile sensing technology has been considered as an efficient and low-cost way to collect environmental data. The problem of geographic location-dependent optimal task assignment in mobile sensing systems is a NP-hard problem. In order to solve this problem, an approximate optimal task allocation algorithm with polynomial time is proposed. The algorithm firstly introduces the idea of moving partition in the unit disk model, and divides the whole monitoring geographic space into several sub-regions. The set of optimal allocation scheme in subinterval is 1 / 1 蔚 of the optimal solution before partition, which shows that the proposed approximation algorithm is a polynomial time approximation mechanism. Then, it is proved that the optimal task assignment problem is polynomial time solvable in each subinterval, and an enumeration algorithm is designed to find the optimal solution of the problem. Finally, the simulation results show that the performance of the proposed approximate optimal task assignment algorithm is in agreement with the theoretical analysis.
【作者单位】： 苏州大学计算机科学与技术学院;苏州大学城市轨道交通学院;中国科学技术大学计算机科学与技术学院;中国科学技术大学苏州研究院;
【基金】：国家“九七三”重点基础研究发展计划基金项目(2011CB302905) 国家自然科学基金项目(61202028,61303206) 教育部高等学校博士学科点专项科研基金项目(20123201120010) 广东省普及型高性能计算机重点实验室开放课题(SZU-GDPHPCL-2012-01)
【分类号】：TN929.53

【参考文献】

中国期刊全文数据库 前2条

1 安健;桂小林;张文东;蒋精华;张进;;物联网移动感知中的社会关系认知模型[J];计算机学报;2012年06期

2 武建佳;赵伟;;WInternet:从物网到物联网[J];计算机研究与发展;2013年06期

【共引文献】

中国期刊全文数据库 前10条

1 王明晓;;基于Android的物联网移动感知服务平台[J];电脑知识与技术;2013年04期

2 田伟;于岚;殷淑娥;;物联网技术在移动购物领域的应用[J];电子商务;2013年05期

3 夏开建;任晓刚;吴s，

本文编号：1878940