计算机科学 ›› 2019, Vol. 46 ›› Issue (6): 102-106.doi: 10.11896/j.issn.1002-137X.2019.06.014

• 网络与通信 • 上一篇    下一篇

面向移动群智感知的位置相关在线多任务分配算法

李卓1,2, 徐哲2, 陈昕2, 李淑琴2,3   

  1. (北京信息科技大学网络文化与数字传播北京市重点实验室 北京100101)1
    (北京信息科技大学计算机学院 北京100101)2
    (北京信息科技大学感知与计算智能联合实验室 北京100101)3
  • 收稿日期:2018-04-30 发布日期:2019-06-24
  • 通讯作者: 李 卓(1983-),男,博士,副教授,CCF会员,主要研究方向为移动无线网络、分布式计算,E-mail:lizhuo@bistu.edu.cn
  • 作者简介:徐 哲(1993-),男,硕士生,主要研究方向为移动群智感知;陈 昕(1965-),男,博士,教授,CCF会员,主要研究方向为网络性能评价、网络安全;李淑琴(1963-),女,博士,教授,CCF会员,主要研究方向为人工智能。
  • 基金资助:
    国家自然科学基金资助项目(61502040),北京市属高校高水平教师队伍建设支持计划青年拔尖人才培育计划资助项目(CIT&TCD201804055),网络文化与数字传播北京市重点实验室资助项目(ICDDXN001),北京信息科技大学“勤信英才”培养计划资助项目资助。

Location-related Online Multi-task Assignment Algorithm for Mobile Crowd Sensing

LI Zhuo1,2, XU Zhe2, CHEN Xin2, LI Shu-qin2,3   

  1. (Beijing Key Laboratory of Internet Culture and Digital Dissemination Research,Beijing Information Science & Technology University,Beijing 100101,China)1
    (School of Computer Science,Beijing Information Science & Technology University,Beijing 100101,China)2
    (Joint Lab of Sensing and Computational Intelligence,Beijing Information Science & Technology University,Beijing 100101,China)3
  • Received:2018-04-30 Published:2019-06-24

摘要: 越高的数据质量要求对应越高的感知成本,如何权衡质量与成本是当前移动群智感知任务分配问题的研究热点之一。研究了保证最低数据质量要求的位置相关在线多任务分配问题,以最小化总体感知成本为优化目标,将数据质量要求量化为不同执行节点的个数;提出了一种基于划分的贪心算法,其主要思想是以执行节点的初始位置为圆心、以节点最远移动意愿为半径生成圆盘,然后从圆盘覆盖到的任务集合中选出合适的任务子集作为相应执行节点的待执行任务集。根据实验仿真,与GGA-I算法相比,所提算法在相同运行时间下,总体感知成本降低12.7%;在相近计算性能下,所需的计算时间平均缩短51.6%。

关键词: 数据质量, 贪心算法, 位置相关, 移动群智感知, 在线多任务分配

Abstract: The higher data quality is required,the more sensing cost is needed.How to achieve the trade-off between the quality and cost is one of the hot topics in the current research on the problem of task assignment in mobile crowd sen-sing.In this paper,the location-related online multi-task assignment problem where the lower bound of the data quality is required to ensure was investigated.The optimization goal is to minimize the total sensing cost,and the data quality requirement is quantified as the number of different execution nodes.This paper proposed a greedy algorithmbased on partition.Its main idea is as follows.Firstly,a disk is generated,whose center is the initial position of the execution node and whose radius is the farthest expected move of the node.After that,a subset of proper tasks whose locations are in the disk are selected,and they are regarded as the tasks to be taken by the corresponding execution node.According to the experimental simulation,compared with the GGA-I algorithm,the proposed algorithm reduces the total sensing cost on the average of 12.7% in the same running time,and reduces the running time on an average of 51% in the similar sensing performance.

Key words: Data quality, Greedy algorithm, Location-related, Mobile crowd sensing, Online multi-task assignment

中图分类号: 

  • TP393
[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
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!