Computer Science ›› 2018, Vol. 45 ›› Issue (2): 157-164.

### Participant Selection Algorithm for t-Sweep k-Coverage Crowd Sensing Tasks

ZHOU Jie, YU Zhi-yong, GUO Wen-zhong, GUO Long-kun and ZHU Wei-ping

• Online:2018-02-15 Published:2018-11-13

Abstract: 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.