计算机科学 ›› 2019, Vol. 46 ›› Issue (6): 102-106.doi: 10.11896/j.issn.1002-137X.2019.06.014
李卓1,2, 徐哲2, 陈昕2, 李淑琴2,3
LI Zhuo1,2, XU Zhe2, CHEN Xin2, LI Shu-qin2,3
摘要: 越高的数据质量要求对应越高的感知成本,如何权衡质量与成本是当前移动群智感知任务分配问题的研究热点之一。研究了保证最低数据质量要求的位置相关在线多任务分配问题,以最小化总体感知成本为优化目标,将数据质量要求量化为不同执行节点的个数;提出了一种基于划分的贪心算法,其主要思想是以执行节点的初始位置为圆心、以节点最远移动意愿为半径生成圆盘,然后从圆盘覆盖到的任务集合中选出合适的任务子集作为相应执行节点的待执行任务集。根据实验仿真,与GGA-I算法相比,所提算法在相同运行时间下,总体感知成本降低12.7%;在相近计算性能下,所需的计算时间平均缩短51.6%。
中图分类号:
[1]ZHANG D Q,XIONG H Y,WANG L Y,et al.CrowdRecruiter Selecting participants for piggyback crowdsensing under probabilistic coverage constraint[C]∥Proceedings of the 2014 ACM International joint Conference on Pervasive and Ubiquitous Computing(UbiComp’14).ACM,2014:703-714. [2]WANG J,TAN N,LUO J,et al.WOLoc:WiFi-only outdoor localization using crowdsensed hotspot labels[C]∥INFOCOM 2017-IEEE Conference on Computer Communications.IEEE,2017:1-9. [3]JING Y,GUO B,LIU Y,et al.CrowdTracker:object tracking using mobile crowd sensing[C]∥Proceedings of the 2017 ACM International Joint Conference on Pervasive and Ubiquitous Computing and Proceedings of the 2017 ACM International Symposium on Wearable Computers.ACM,2017:85-88. [4]ZHENG Y,LIU F,HSIEH H P.U-air:When urban air quality inference meets big data[C]∥Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining.ACM,2013:1436-1444. [5]YANG D,XUE G,FANG X,et al.Crowdsourcing to smartphones:Incentive mechanism design for mobile phone sensing[C]∥Proceedings of the 18th Annual International Conference on Mobile Computing and Networking.ACM,2012:173-184. [6]HAN K,HUANG H,LUO J.Posted pricing for robust crowdsensing[C]∥Proceedings of the 17th ACM International Symposium on Mobile Ad Hoc Networking and Computing.ACM,2016:261-270. [7]HE S,SHIN D H,ZHANG J,et al.Toward optimal allocation of location dependent tasks in crowdsensing[C]∥2014 IEEE Conference on Computer Communications(INFOCOM).2014:745-753. [8]WANG J,WANG Y,ZHANG D,et al.PSAllocator:multi-task allocation for participatory sensing with sensing capability constraints[C]∥Proceedings of the 2017 ACM Conference on Computer Supported Cooperative Work and Social Computing.2017:1139-1151. [9]ESTRADA R,MIZOUNI R,OTROK H,et al.A crowd-sensing framework for allocation of time-constrained and location-based tasks[J/OL].IEEE Transactions on Services Computing,https://www.computer.org/csdl/trans/sc/preprint/07974784-abs.html. [10]HU T,XIAO M,HU C,et al.A QoS-sensitive task assignment algorithm for mobile crowdsensing[J].Pervasive and Mobile Computing,2017,41:333-342. [11]GAMBOSI G,PROTASI M,TALAMO M.Preserving approximation in the Min-Weighted Set Cover Problem[J].Discrete Applied Mathematics,1997,73(1):13-22. [12]堵丁柱,葛可一,胡晓东,等.近似算法的设计与分析[M].北京:高等教育出版社,2011. [13]BOWDEN J A.Foursquare-user-dataset[EB/OL].https:// github.com/jalbertbowden/foursquare-user-dataset. [14]CHRISTOFIDES N.Worst-case analysis of a new heuristic for the travelling salesman problem[R].Carnegie-Mellon Univ Pittsburgh Pa Management Sciences Research Group,1976. |
[1] | 张翀宇, 陈彦明, 李炜. 边缘计算中面向数据流的实时任务调度算法 Task Offloading Online Algorithm for Data Stream Edge Computing 计算机科学, 2022, 49(7): 263-270. https://doi.org/10.11896/jsjkx.210300195 |
[2] | 刘漳辉, 郑鸿强, 张建山, 陈哲毅. 多无人机使能移动边缘计算系统中的计算卸载与部署优化 Computation Offloading and Deployment Optimization in Multi-UAV-Enabled Mobile Edge Computing Systems 计算机科学, 2022, 49(6A): 619-627. https://doi.org/10.11896/jsjkx.210600165 |
[3] | 郑小萌, 高猛, 滕俊元. 航天器软件缺陷预测数据集构建方法研究 Research on Construction Method of Defect Prediction Dataset for Spacecraft Software 计算机科学, 2021, 48(6A): 575-580. https://doi.org/10.11896/jsjkx.200900133 |
[4] | 李建军, 汪校铃, 杨玉, 付佳. 基于CQPSO移动群智感知紧急任务分配方法研究 Emergency Task Assignment Method Based on CQPSO Mobile Crowd Sensing 计算机科学, 2020, 47(6A): 273-277. https://doi.org/10.11896/JsJkx.190700040 |
[5] | 张新明, 李双倩, 刘艳, 毛文涛, 刘尚旺, 刘国奇. 信息共享模型和组外贪心策略的郊狼优化算法 Coyote Optimization Algorithm Based on Information Sharing and Static Greed Selection 计算机科学, 2020, 47(5): 217-224. https://doi.org/10.11896/jsjkx.190400039 |
[6] | 蔡威, 白光伟, 沈航, 成昭炜, 张慧丽. 移动群智感知中基于强化学习的双赢博弈 Reinforcement Learning Based Win-Win Game for Mobile Crowdsensing 计算机科学, 2020, 47(10): 41-47. https://doi.org/10.11896/jsjkx.200700070 |
[7] | 胡俊钦, 张佳俊, 黄引豪, 陈星, 林兵. 边缘环境下DNN应用的计算迁移调度技术 Computation Offloading Scheduling Technology for DNN Applications in Edge Environment 计算机科学, 2020, 47(10): 247-255. https://doi.org/10.11896/jsjkx.190900106 |
[8] | 翟书颖, 李茹, 李波, 郝少阳. 视觉群智感知应用综述 Survey on Applications of Visual Crowdsensing 计算机科学, 2019, 46(6A): 11-15. |
[9] | 王旸, 蔡淑琴, 邹新文, 陈梓桐. 质量嵌入的大数据产品生产系统超图模型及其生产线决策研究 Quality-embedded Hypergraph Model for Big Data Product Manufacturing System and Decision for Production Lines 计算机科学, 2019, 46(2): 11-17. https://doi.org/10.11896/j.issn.1002-137X.2019.02.002 |
[10] | 陈晋音,胡可科,李玉玮. 基于MB-RRT*的无人机多点航迹规划算法研究 Research on UAV Multi-point Navigation Algorithm Based on MB-RRT* 计算机科学, 2018, 45(6A): 85-90. |
[11] | 朱瑞超,钱文华,普园媛,徐丹. 自相似性匹配的纹理合成 Texture Synthesis Based on Self-similarity Matching 计算机科学, 2018, 45(6A): 215-219. |
[12] | 胡庆成, 张勇, 邢春晓. 基于有重叠社区划分的社会网络影响最大化方法研究 K-clique Heuristic Algorithm for Influence Maximization in Social Network 计算机科学, 2018, 45(6): 32-35. https://doi.org/10.11896/j.issn.1002-137X.2018.06.005 |
[13] | 蔡莉,梁宇,朱扬勇,何婧. 数据质量的历史沿革和发展趋势 History and Development Tendency of Data Quality 计算机科学, 2018, 45(4): 1-10. https://doi.org/10.11896/j.issn.1002-137X.2018.04.001 |
[14] | 尚玉玲, 曹建军, 李红梅, 郑奇斌. 基于合作作者与隶属机构信息的同名排歧方法 Co-author and Affiliate Based Name Disambiguation Approach 计算机科学, 2018, 45(11): 220-225. https://doi.org/10.11896/j.issn.1002-137X.2018.11.034 |
[15] | 孙焘,朱晓明. 基于格代数的最长公共子序列近似求解 Computing Longest Common Subsequences Approximately Based on Lattice 计算机科学, 2017, 44(2): 270-274. https://doi.org/10.11896/j.issn.1002-137X.2017.02.045 |
|