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

摘要

空间众包的分配问题是众包分配中的一个重要分支,空间众包任务不仅要求参与者在规定时间去完成某个特定的任务,而且要求参与者在指定的地点完成任务.移动众包感知技术MCS利用智能手机的感知功能来完成关于采集感知数据（如WIFI强弱信息,噪音信息等）的空间众包任务,在现今的空间众包的分配算法中对于带有范围特性的任务在分配时,没有具体对于任务区域相互覆盖问题的解决方法,由于任务范围的冗余会对分配结果产生负面影响,通常会造成人力和任务成本的提高,本文基于MCS技术研究在人少任务多的情况下如何解决任务范围冗余问题,通过利用二叉树将任务范围信息进行分类,快速找到与任务有关系的一系列任务减小问题规模并且加快分配速度.本文将OSSA算法与TGOA算法和贪心算法在任务分配数量和任务成本方面进行对比,证明OSSA算法的可行性和正确性.同时,由于本文的算法是在OSSA基础上对执行效率进行的改良,所以本文同时会将优化后的改良算法和没有优化的OSSA算法进行对比,证明算法在运行效率上的优化.