Computer Science ›› 2018, Vol. 45 ›› Issue (2): 157-164.doi: 10.11896/j.issn.1002-137X.2018.02.028

Previous Articles     Next Articles

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.

Key words: Crowd sensing,Sweep coverage,Participant selection,Linear programming,Set covering

[1] THIAGARAJAN A,RAVINDRANATH L,LACURTS K,et at.VTrack:Accurate,energy-aware road traffic delay estimation using mobile phones[C]∥Proceedings of the 7th ACM Con-ference on Embedded Network Sensor Systems.Berkeley,USA,2009:85-98.
[2] MOHAN P,PADMANABHAN V N,RANJEE R.Nericell:Rich Monitoring of Road and Traffic Conditions using Mobile Smart-phones[C]∥Proceedings of the 6th ACM Conference on Embedded Network Sensor Systems.Raleigh,USA,2008:323-336.
[3] STEVENS M,D’HONDT E.Crowdsourcing of Pollution Data using Smartphones[C]∥Proceedings of the Workshop on Ubi-quitous Crowdsourcing.Copenhagen Denmark,2010:1-4.
[4] WU W L,GUO B,YU Z W.Crowd sensing based urban noise map and temporal-spatial feature analysis[J].Journal of Computer-Aided Design & Computer Graphics,2014,6(4):638-643.(in Chinese) 吴文乐,郭斌,於志文.基于群智感知的城市噪音检测与时空规律分析[J].计算机辅助设计与图形学学报,2014,6(4):638-643.
[5] MUN M,REDDY S,SHILTON K,et al.PEIR,the personal environmental impact report,as a platform for participatory sensing systems research[C]∥Proceedings of the 7th International Conference on Mobile Systems,Applications and Services.Krakow,Poland,2009:55-68.
[6] HUANG C F,TSENG Y C.The Coverage Problem in a Wireless Sensor Network[J].Mobile Networks and Applications,2005,0(4):519-528.
[7] KUMAR S,LAI T H,BALOGH J.On K-Coverage in a Mostly Sleeping Sensor Network[C]∥Proceedings of the 10th annual international conference on Mobile computing and networking(MobiCom’04).Philadelphia,PA,USA,2004:144-158.
[8] LIN L,LEE H Y.Distributed Algorithms for Dynamic Coverage in Sensor Networks[C]∥Proceedings of the Twenty-sixth Annual ACM Symposium on Principles of Distributed Computing(PODC’07).Portland,Oregon,USA,2007:392-393.
[9] MEGUERDICHIAN S,KOUSHANFAR F,POTKONJAK M,et al.Coverage Problems in Wireless Ad-Hoc Sensor Networks[C]∥Proceedings IEEE INFOCOM 2001,The Conference on Computer Communications,Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies.Alaska,USA,2001:1380-1387.
[10] BALISTER P,BOLLOBAS B,SARKAR A,et al.Reliable Density Estimates for Achieving Coverage and Connectivity in Thin Strips of Finite Length[C]∥Proceedings of the 13th Annual ACM International Conference on Mobile Computing and Networking(MobiCom’07).Montréal,Québec,Canada,2007:75-86.
[11] CHEN A,KUMAR S,LAI T H.Local Barrier Coverage inWireless Sensor Networks[J].IEEE Transactions on Mobile Computing,2010,9(4):491-504.
[12] KUMAR S,LAI T H,ARORA A.Barrier coverage with wireless sensors[J].Wireless Networks,2007,3(6):817-834.
[13] CHEN A,KUMAR S.Designing localized algorithms for barrier coverage[C]∥Proceedings of the 13th Annual ACM International Conference on Mobile Computing and Networking(MobiCom’07).Montréal,Québec,Canada,2007:63-74.
[14] LI M,CHENG W F,LIU K B,et al.Sweep coverage with mobile sensors[J].IEEE Transactions on Mobile Computing,2011,0(11):1534-1545.
[15] XI M,WU K,QI Y,et al.Run to Potential:Sweep Coverage in Wireless Sensor Networks[C]∥International Conference on Parallel Processing.Vienna,Austria,2009:50-57.
[16] REDDY S,ESTRIN D,SRIVASTAVA M.Recruitment framework for participatory sensing data collections[C]∥Proceedings of the 8th international conference on Pervasive Computing(Pervasive’10).Helsinki,Finland,2010:138-155.
[17] GIUSEPPE C,LUCA F,PAOLO B,et al.Fostering participaction in smart cities:a geo-social crowdsensing platform[J].IEEE Communications Magazine,2013,51(6):112-119.
[18] AHMED A,YASUMOTO K,YAMAUCHI Y,et al.Distance and time based node selection for probabilistic coverage in people-centric sensing[C]∥The 8th Annual IEEE Communications Society Conference on Sensor,Mesh and Ad-Hoc Communications and Networks.Utah,USA,2011:134-142.
[19] HACHEM S,PATHAK A,ISSARNY V.Probabilistic registration for large-scale mobile participatory sensing[C]∥IEEE International Conference on Pervasive Computing and Communications (PerCom).San Diego,California,USA,2013:132-140.
[20] ZHANG D Q,XIONG H Y,WANG L Y,et al.Crowd Recruiter:Selecting Participants for Piggy Back Crowd Sensing under Probabilistic Coverage Constraint[C]∥Proceedings of the 2014 ACM International Joint Conference on Pervasive and Ubiquitous Computing(UbiComp’14).Seattle,USA,2014:703-714.
[21] REDDY S,SAMANTA V,SHILTON K,et al.Mobisense,mobile network services for coordinated participatory sensing[C]∥Proceedings of International Symposium Autonomous Decentralized Systems (ISADS’09).Athens,Greece,2009:1-6.
[22] REDDY S,SHILTON K,BURKE J,et al.Using context annotated mobility profles to recruit data collectors in participatory sensing[C]∥Proceedings of the 4th International Symposium on Location and Context Awareness.Tokyo,Japan,2009:52-69.
[23] MENDEZ D,LABRADOR M A.Density Maps:DeterminingWhere to Sample in Participatory Sensing Systems[C]∥Proceedings of the 2012 Third FTRA International Conference on Mobile,Ubiquitous,and Intelligent Computing(MUSIC’12).Fukuoka,Japan,2012:35-40.

No related articles found!
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[2] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[3] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[4] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[5] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[6] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[7] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[8] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[9] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .
[10] WANG Zhen-chao, HOU Huan-huan and LIAN Rui. Path Optimization Scheme for Restraining Degree of Disorder in CMT[J]. Computer Science, 2018, 45(4): 122 -125 .