移动群智感知中收益最大化的用户招募算法  

Profit-maximizing User Recruitment Under Budget Constraint in Mobile Crowdsensing

作　　者：郭会东 黄刘生[1,2] 高国举 徐宏力 

机构地区：[1]中国科学技术大学计算机科学与技术学院,合肥230027 [2]中国科学技术大学苏州研究院,江苏苏州215123

出　　处：《小型微型计算机系统》2018年第3期439-444,共6页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(61170058;U1301256)资助

摘　　要：在移动群智感知中,平台需要招募大量用户来协同完成一项包含众多感知任务的复杂工作.本文研究预算受限的移动群智感知中,收益最大化的用户招募问题.在这一问题中,平台希望用户覆盖的感知任务带来的总收益最大化,同时,招募总开销不超过给定的预算.不同于以往研究,本文中单个感知任务可以被多个用户执行,但是单个任务的收益是固定的,此外,每个移动用户能处理的感知任务也是确定的.为此,首先证明了这是一个NP难问题,并提出了一个改进的贪心算法来解决这一问题.进一步通过数学推导分析了该算法的性能保证,证明了该算法与最优解的近似比至少为1/2(1-1/e).通过实验验证了该算法具有很好的性能表现,符合理论分析的预期.In mobile crowdsensing （ MCS }, lots of mobile users are recruited by an MCS platform, to cooperatively perform a complex job including many sensing tasks. In this paper,we focus on the Profit-maximizing User Recruitment problem （PUR） under budget constraint in MCS. In this problem, the MCS platform wants to maximize the total profits of sensing tasks covered by the recruited us- ers, while total costs are not more than a given budget. Unlike previous works,each sensing task can be performed by more than one users, but its single profit is invariable. Additionally, the sensing tasks that each mobile user can deal with are determined, which makes the fees charged by each user be determined. To this end, we first prove the NP-hardness of this problem. Then, we adopt a modified greedy algorithm, called gPUR, to solve it. Moreover, we analyze the performance guarantee of gPUR, and give the approximation ratio of 1（ 1 - I/e）. In addition, we demonstrate the significant performances of the proposed algorithm through extensive simulations.

关 键 词：移动群智感知 预算受限 用户招募 贪心算法 

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