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

作者：刘文彬; 杨永健; 王恩^*

来源：计算机学报, 2022, 45(12): 2576-2591.

• 移动群智感知
• 用户招募
• 在线优化
• 非子模函数
• 秘书问题

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

• 单位
  吉林大学