计算机科学 ›› 2018, Vol. 45 ›› Issue (2): 157-164.doi: 10.11896/j.issn.1002-137X.2018.02.028
周杰,於志勇,郭文忠,郭龙坤,朱伟平
ZHOU Jie, YU Zhi-yong, GUO Wen-zhong, GUO Long-kun and ZHU Wei-ping
摘要: 随着无线网络技术和移动智能终端的快速发展和普及,对群智感知的研究受到越来越多相关科研工作者的关注。群智感知利用众包的思想,将任务分配给拥有移动设备的用户(即感知任务的参与者),用户分别上传自己使用移动设备感知到的数据。参与者的选择直接决定了收集信息的质量和相关耗费。选择尽可能少的参与者来接受感知任务,达到对指定地点集合的时空覆盖这一质量要求,就显得至关重要。首先定义了“t-时隙k-覆盖”群智感知任务,以最小代价完成该类任务是NP-hard问题。通过特殊的构造技巧,在问题规模较小时可以用线性规划进行求解,但随着问题规模的增大,线性规划越来越力不从心,因此提出了基于贪心策略的参与者选择算法。在给定移动用户CDR信息的基础上,实验模拟了以上两种参与者选择方法。实验结果表明,在问题规模较小时,以上两种方法均可找出参与者集合,满足覆盖要求,贪心策略的结果大约是线性规划的两倍;在问题规模变大后,线性规划会出现不可求解的情况,而贪心策略依然可以得到近似最优结果。
[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! |
|