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

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

作　　者：李卓[1,2] 徐哲[2] 陈昕[2] 李淑琴[2,3] LI Zhuo;XU Zhe;CHEN Xin;LI Shu-qin(Beijing Key Laboratory of Internet Culture and Digital Dissemination Research,Beijing Information Science & Technology University,Beijing 100101,China;School of Computer Science,Beijing Information Science & Technology University,Beijing 100101,China;Joint Lab of Sensing and Computational Intelligence,Beijing Information Science & Technology University,Beijing 100101,China)

机构地区：[1]北京信息科技大学网络文化与数字传播北京市重点实验室,北京100101 [2]北京信息科技大学计算机学院,北京100101 [3]北京信息科技大学感知与计算智能联合实验室,北京100101

出　　处：《计算机科学》2019年第6期102-106,共5页Computer Science

基　　金：国家自然科学基金资助项目(61502040);北京市属高校高水平教师队伍建设支持计划青年拔尖人才培育计划资助项目(CIT&TCD201804055);网络文化与数字传播北京市重点实验室资助项目(ICDDXN001);北京信息科技大学“勤信英才”培养计划资助项目资助

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

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

分 类 号：TP393[自动化与计算机技术—计算机应用技术]