移动群智感知网络中信息量最大化的用户选择方法研究

On Designing Most Informative User Selection Methods for Mobile Crowdsensing

移动群智感知网络已经成为一种新型的感知模式,被广泛应用在环境数据收集等多种不同场景.限制群智感知系统效能的一个关键问题在于:如何在一定预算范围内选取最合适的用户来进行感知任务,从而最大化收集到数据的信息量.这其中的关键挑战包括:(1)如何定义量化评价指标衡量数据的信息量,(2)如何在无先验知识的情况下有效地学习选择每个用户的成本,(3)如何设计有效的用户选择算法,最大程度地降低算法的累计遗憾.在本文中,我们采用高斯过程建模空间环境,并且提出一个基于互信息的信息量衡量指标.为了解决第二、第三个挑战,我们提出有预算限制的多臂老虎机用户选择问题模型,并为静态和动态场景分别设计了理论可证的低累计遗憾的多轮用户选择算法.我们的理论分析和仿真实验均证实我们提出的算法能够在预算限制情况下有效地选择最有信息量的用户,与基准方法相比提升约20%.

With the rapid development of mobile devices and wireless technology,mobile crowdsensing has become a novel and promising to sense paradigm.In mobile crowdsensing,there are three major components:service requesters,mobile device users,and crowdsensing platform.Crowdsensing platform releases sensing tasks to the mobile device users based on the received information requests.Then,the mobile device users will collect specific local information and send it back to the platform.It has been applied in various scenarios,including but not limited to environmental data collecting,human activity recognition,traffic monitoring,navigation,indoor localization,and indoor floorplan construction.A critical problem in improving the quality and effectiveness of crowdsensing is to decide which users to select to perform sensing tasks,in order to obtain the most informative data,while maintaining the total sensing costs below a given threshold.To solve this problem,the key challenges lie in(1)finding an effective measure of the informativeness of the users’ data,(2)learning users’ sensing costs which are unknown a priori,and(3)designing an efficient user selection algorithm that achieves low-regret guarantees.In this paper,to solve the first challenge,we adopt Gaussian Processes(GPs)to model spatial environmental locations,and provide a mutual information-based criterion to characterize the users’ informativeness.To tackle the second and third challenge,we model the problem as a budgeted Multi-Armed Bandit(MAB)problem based on stochastic assumptions.In the problem model,we assume that each user’s sensing cost follows an unknown distribution with unknown mean.The platform receives the knowledge of a user’s sensing cost after the user finishes its sensing task.In this case,the platform needs to learn the users’ sensing costs and make decisions in an online manner.This problem is NP-hard even if the full knowledge of the users’ sensing costs is available.To address the NP-hardness of the problem,we first consider an ideal full-knowledge scenario,and propose efficient greedy algorithms with constant approximation ratios for both single-rounded and multi-rounded user selection scenarios.Then,based on the full-knowledge user selection algorithms,we design two multi-armed bandit algorithms for static and dynamic scenarios respectively with theoretically proven low-regret guarantees.Our evaluation results show that our algorithm can efficiently select most informative users under stringent constraints,improving the performance up to about 20%compared with the benchmarks.