合作性移动群智感知中具有一般效用和成本的用户招募方法

User Recruitment with General Utility and Cost for Cooperative Mobile CrowdSensing

移动群智感知(Mobile CrowdSensing,MCS)是一种强力而有效的感知数据收集模式,其允许我们在预算有限的情况下招募一群移动用户并利用其随身携带的智能设备来合作地执行感知任务.现有的工作通常根据具有子模性质的效用函数(如用户集合的任务覆盖概率,存在边际收益递减)和线性的成本函数(如用户集合的累积支付成本)来招募用户.然而,在实际应用中,我们往往需要进一步考虑用户间合作意愿,导致实际问题比现有工作所假设的场景更加复杂,相应的效用和成本函数可能不再满足子模和线性关系.举例来说,如果某个用户基于隐私考虑而不愿意与陌生人合作,他可能会拒绝执行一部分敏感的工作,或者要求支付较高的费用,导致效用和成本发生变化.本文研究了具有一般效用和成本的合作性移动群智感知用户招募问题.为了解决非子模的效用和成本,我们提出了一种广义离线贪婪算法,离线地从已知用户池中选择用户,并通过引入子模比率和曲率来证明该算法的理论近似比.进一步考虑在线场景,我们提出了一种分段的在线招募策略,首先将用户序列划分为数个片段,然后在每个片段中分别进行在线招募,并同样给出该策略的理论近似比.我们在四个真实数据集上进行了广泛的评估,其结果验证了所提出方法的有效性.

Mobile CrowdSensing(MCS) is a powerful sensing paradigm,which recruits a crowd of users within a limited budget to cooperatively perform sensing tasks.The existing works usually recruit users based on their submodular utility and linear cost functions,e.g.,the users’ probabilistic coverage of tasks and total consumed costs.However,we argue that these works do not consider the cooperative willingness of users,which may lead to non-submodular utility and cost.For example,if a user is unwilling to cooperate with strangers,he may refuse to perform some sensitive tasks and/or ask for a higher payment due to the privacy concern.In this paper,we study the user recruitment problem with general utility and cost for cooperative MCS.To deal with the non-submodular utility and cost,we present a generalized online greedy algorithm to select users from a determined user pool,which achieves an approximation ratio by introducing submodularity ratio and curvature.Taking online recruiting into further consideration,we propose a segmented online strategy,which first divides the user sequence into segments and then recruits them with a theoretical performance approximation.Extensive evaluations have been conducted over four real-world datasets,which verify the effectiveness of the proposals.