一种范围性空间众包任务的在线分配优化研究  

Research on Online Allocation and Optimization of Scope Spatial Crowdsourcing Tasks

作　　者：高丽萍[1,2] 戴焜 高丽[3] GAO Li-ping;DAI Kun;GAO Li(School of Optical-Electrical Computer Engineering,University of Shanghai for Science&Technology,Shanghai 200093,China;Shanghai Key Laboratory of Data Science,FudanUniversity,Shanghai 200093,China;Library Department of Shanghai University of Technology,Shanghai 200093,China)

机构地区：[1]上海理工大学光电信息与计算机工程学院,上海200093 [2]复旦大学上海数据科学重点实验室,上海200093 [3]上海理工大学图书馆,上海200093

出　　处：《小型微型计算机系统》2020年第8期1580-1589,共10页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(61202376,61572325)资助;上海市自然科学基金项目(17ZR1429100)资助;上海市数据科学重点实验室重点开放课题项目(201609060003)资助。

摘　　要：空间众包的分配问题是众包分配中的一个重要分支,空间众包任务不仅要求参与者在规定时间去完成某个特定的任务,而且要求参与者在指定的地点完成任务.移动众包感知技术MCS利用智能手机的感知功能来完成关于采集感知数据(如WIFI强弱信息,噪音信息等)的空间众包任务,在现今的空间众包的分配算法中对于带有范围特性的任务在分配时,没有具体对于任务区域相互覆盖问题的解决方法,由于任务范围的冗余会对分配结果产生负面影响,通常会造成人力和任务成本的提高,本文基于MCS技术研究在人少任务多的情况下如何解决任务范围冗余问题,通过利用二叉树将任务范围信息进行分类,快速找到与任务有关系的一系列任务减小问题规模并且加快分配速度.本文将OSSA算法与TGOA算法和贪心算法在任务分配数量和任务成本方面进行对比,证明OSSA算法的可行性和正确性.同时,由于本文的算法是在OSSA基础上对执行效率进行的改良,所以本文同时会将优化后的改良算法和没有优化的OSSA算法进行对比,证明算法在运行效率上的优化.The problem of allocation of space crow dsourcing is an important branch of crow dsourcing allocation.Sptial crow dsourcing tasks not only require participants to complete a specific task at a specified time,but also require participants to complete tasks at designated locations.Mobile crow dsourcing awareness technology MCS uses the perception function of smartphones to complete the sptial crow dsourcing task of collecting sensory data(such as WIFI strength information,noise information,etc.),with range characteristics in today’s sptial crow dsourcing allocation algorithm.When the task is assigned,there is no specific solution to the problem of mutual coverage of the task area.Since the redundancy of the task scope will have a negative impact on the distribution result,the manpower and task costs are usually increased.This paper is based on the MCS technology research.How to solve the task scope redundancy problem in the case of many tasks,by using the binary tree to classify the task scope information,quickly find a series of tasks related to the task to reduce the problem size and speed up the allocation.This paper compares OSSA algorithm with TGOA algorithm and greedy algorithm in terms of task allocation quantity and task cost,and proves the feasibility and correctness of OSSA algorithm.At the same time,because the algorithm of this paper is to improve the execution efficiency based on OSSA,this paper will compare the optimized algorithm with the optimized OSSA algorithm to prove the optimization of the algorithm.

关 键 词：众包 空间众包 分类 二叉树 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]