“t-时隙 k-覆盖”群智感知任务的参与者选择方法

摘要

With the rapid development and popularization of the wireless network technology and mobile intelligent terminal,the research of crowd sensing has been concerned by more and more related research workers.The crowd sensing uses the idea of crowdsourcing to assign tasks to users who have mobile devices and then the users respectively upload the data sensed by their own mobile devices.Therefore,the choice of the participants directly determines the quality of information collection and related costs.Selecting as few users as possible to accept the perceptual tasks to achieve the quality requirements of the time and space coverage of the specified location set is very improtant.First,the "t-sweep k-coverage" crowd sensing tasks was defined.It is an NP-hard problem to complete the task with the mini-mum cost.Through the construction of special skills,linear programming can be used to solve the problem while the scale of the problem is small.With the increase of the scale of the problem,the linear programming fails to solve it.Therefore,the participant selection algorithm based on the theory of greedy strategy was proposed.Based on the information of the mobile users' CDR,two kinds of participant selection method were simulated in the experiment.The results of experiment show that when the problem scale is small,both the above two methods can find the user set to meet the coverage requirements.The size of user set of the greedy strategy is about twice bigger than that of the linear programming.When the scale of the problem becomes larger,the linear programming fails to solve the problem sometimes,while the greedy strategy can still get a reasonable result.%随着无线网络技术和移动智能终端的快速发展和普及,对群智感知的研究受到越来越多相关科研工作者的关注.群智感知利用众包的思想,将任务分配给拥有移动设备的用户(即感知任务的参与者),用户分别上传自己使用移动设备感知到的数据.参与者的选择直接决定了收集信息的质量和相关耗费.选择尽可能少的参与者来接受感知任务,达到对指定地点集合的时空覆盖这一质量要求,就显得至关重要.首先定义了“t-时隙k-覆盖”群智感知任务,以最小代价完成该类任务是NP-hard问题.通过特殊的构造技巧,在问题规模较小时可以用线性规划进行求解,但随着问题规模的增大,线性规划越来越力不从心,因此提出了基于贪心策略的参与者选择算法.在给定移动用户CDR信息的基础上,实验模拟了以上两种参与者选择方法.实验结果表明,在问题规模较小时,以上两种方法均可找出参与者集合,满足覆盖要求,贪心策略的结果大约是线性规划的两倍;在问题规模变大后,线性规划会出现不可求解的情况,而贪心策略依然可以得到近似最优结果.