计算机科学 ›› 2022, Vol. 49 ›› Issue (5): 371-379.doi: 10.11896/jsjkx.210200005
• 交叉与前沿 • 上一篇
李晓东1, 於志勇1,2, 黄昉菀1,2, 朱伟平1, 涂淳钰1, 郑伟楠1
LI Xiao-dong1, YU Zhi-yong1,2, HUANG Fang-wan1,2, ZHU Wei-ping1, TU Chun-yu1, ZHENG Wei-nan1
摘要: 城市内河周边环境常常受到破坏和污染,如何有效地对河道进行监测逐渐引起公众、政府和学术界的关注。目前传统的监测方式存在成本高昂、覆盖面不足等缺陷。鉴于智能移动设备的不断普及,文中提出利用群智感知来高效监测河道环境的新思路。该问题可描述为假定每一河段附近有c个位置点可监测该河段,然后根据大量用户的移动轨迹选择出其中r个用户来共同完成s个时段对所有河段的监测。文中规定用户数r越小,监测成本越少。设计了逐步贪心策略、全局贪心策略和整数规划策略用于解决该问题,即选择最少参与者达到“s时长-c范围-r用户”的监测目标。将上述策略应用于福州市台江区部分河道的环境监测,实验结果表明,上述策略均能获得比随机策略更好的解,其中整数规划策略的表现最好。但是,随着问题规模的变大,解决小规模整数规划的隐枚举算法会出现无法求解的情况,因此提出了基于贪心初始化的离散粒子群算法(Greedy Initialization-Discrete Particle Swarm Optimization,GI-DPSO)。虽然该算法可以求解大规模整数规划,但计算费时。综合考虑监测成本和计算代价,建议对小规模问题采用整数规划策略,对大规模问题采用全局贪心策略。
中图分类号:
[1]GAO R W.Reshaping the relationship between inland rivers and people’s livelihood from the perspective of humanism:A study on the comprehensive accessibility of inland rivers in Fuzhou[J].Fujian Architecture,2020(8):1-9. [2]Fuzhou Urban and Rural Construction Bureau.Measures for the Management of Urban Inland Rivers in Fuzhou[R].Fuzhou,2019. [3]DUTTA J,CHOWDHURY C,ROY S,et al.Towards smartcity:sensing air quality in city based on opportunistic crowd-sensing[C]//Proceedings of the 18th International Conference on Distributed Computing and Networking.2017:1-6. [4]GANTI R K,YE F,LEI H.Mobile crowdsensing:current state and future challenges[J].IEEE Communications Magazine,2011,49(11):32-39. [5]RADU V,KRIARA L,MARINA M K.Pazl:A mobile crowd-sensing based indoor WiFi monitoring system[C]//Proceedings of the 9th International Conference on Network and Service Management (CNSM 2013).IEEE,2013:75-83. [6]CARDONE G,FOSCHINI L,BELLAVISTA P,et al.Fostering participaction in smart cities:a geo-social crowdsensing platform[J].IEEE Communications Magazine,2013,51(6):112-119. [7]GUO W,ZHU W,YU Z,et al.A survey of task allocation:Contrastive perspectives from wireless sensor networks and mobile crowdsensing[J].IEEE Access,2019,7:78406-78420. [8]LIU Y,GUO B,WU W L,et al.Research on the method of selecting multitask participants for mobile group intelligence perception[J].Chinese Journal of Computers,2017,40(8):1872-1887. [9]LI H.Participant Selection and Task Assignment in MobileCrowd Sensing[D].Charlott:University of North Carolina at Charlotte,2018. [10]LUDWIG T,REUTER C,PIPEK V.What you see is what I need:Mobile reporting practices in emergencies[C]//ECSCW 2013:Proceedings of the 13th European Conference on Compu-ter Supported Cooperative Work.London:Springer,2013:181-206. [11]DUTTA J,GAZI F,ROY S,et al.AirSense:Opportunistic crowd-sensing based air quality monitoring system for smart city[C]//Sensors.IEEE,2017. [12]QIN Z,ZHU Y.NoiseSense:A crowd sensing system for urban noise mapping service[C]//2016 IEEE 22nd International Conference on Parallel and Distributed Systems (ICPADS).IEEE,2016:80-87. [13]RAMBURN T,BADOREEA D,CHEERKOOT-JALIM S.Drive-MU:A Real-time Road-Traffic Monitoring Android Application for Mauritius[C]//2019 Conference on Next Generation Computing Applications (NextComp).IEEE,2019:1-8. [14]EL KHAILI M,BAKKOURY J,KHIAT A,et al.Crowdsour-cing by IoT using LabVIEW for Measuring the Air Quality[C]//Proceedings of the 3rd International Conference on Smart City Applications.2018:1-8. [15]LEE H P,GARG S,LIM K M.Crowdsourcing of environmental noise map using calibrated smartphones[J].Applied Acoustics,2020,160:107130. [16]JING Y,GUO B,LIU Y,et al.CrowdTracker:object trackingusing mobile crowd sensing[C]//Proceedings of the 2017 ACM International Joint Conference on Pervasive and Ubiquitous Computing and Proceedings of the 2017 ACM International Symposium on Wearable Computers.2017:85-88. [17]KIM K,ZABIHI H,KIM H,et al.TrailSense:A crowdsensing system for detecting risky mountain trail segments with walking pattern analysis[J].Proceedings of the ACM on Interactive,Mobile,Wearable and Ubiquitous Technologies,2017,1(3):1-31. [18]WU F,YANG S,ZHENG Z,et al.Fine Grained User Profiling for Personalized Task Matching in Mobile Crowdsensing[J].IEEE Transactions on Mobile Computing,2020,1(1):99-112. [19]SONG Z,ZHANG B,LIU C H,et al.QoI-aware energy-efficient participant selection[C]//2014 Eleventh Annual IEEE International Conference on Sensing,Communication,and Networking (SECON).IEEE,2014:248-256. [20]LI H,LI T,WANG Y.Dynamic participant recruitment of mobile crowd sensing for heterogeneous sensing tasks[C]//2015 IEEE 12th International Conference on Mobile Ad Hoc and Sensor Systems.IEEE,2015:136-144. [21]ZHANG D,XIONG H,WANG L,et al.CrowdRecruiter:selecting participants for piggyback crowdsensing under probabilistic coverage constraint[C]//Proceedings of the 2014 ACM International Joint Conference on Pervasive and Ubiquitous Computing.2014:703-714. [22]REDDY S,ESTRIN D,SRIVASTAVA M.Recruitment framework for participatory sensing data collections[C]//Interna-tional Conference on Pervasive Computing.Berlin:Springer,2010:138-155. [23]YU Z,ZHOU J,GUO W,et al.Participant selection for t-sweep k-coverage crowd sensing tasks[J].World Wide Web,2018,21(3):741-758. [24]LV Q,GU J Q,XU S,et al.Structure and characteristics of the automatic monitoring system for rivers in Suzhou city[J].Urban and Rural Construction,2015(4):82-84. [25]CHEN Z Q.Research on Intelligent Video Monitoring System under “River Chief System”[D].North China University of Water Conservancy and Hydropower,2019. [26]TANG X Y.Design and development of an intelligent waterquality monitoring platform for unmanned ships[D].Haikou:Hainan University,2018. [27]KARP R M.Reducibility among combinatorial problems[M]//Complexity of Computer Computations.Boston:Springer,1972:85-103. [28]JUN W,DUAN L I.A New Implicit Enumeration Method for Polynomial 0-1 Programming and Applications[J].Systems Engineering-Theory & Practice,2007 (3):2. [29]LU S H,HU M H.Multi-airport GDP release strategy based on heuristic implicit enumeration algorithm[J].Journal of Wuhan Institute of Technology,2010,32(1):97-99. [30]KENNEDY J,EBERHART R.Particle swarm optimization[C]//Proceedings of ICNN’95-International Conference on Neural Networks.IEEE,1995:1942-1948. [31]EBERHART R,KENNEDY J.A new optimizer using particleswarm theory[C]//Proceedings of the Sixth International Symposium on Micro Machine and Human Science(MHS’95).IEEE,1995:39-43. [32]SHEN L C,HUO X H,NIU Y F.Overview of the Research Status of Discrete Particle Swarm Optimization Algorithms[J].Systems Engineering and Electronics,2008(10):1986-1990. |
[1] | 李利, 何欣, 韩志杰. 群智感知的隐私保护研究综述 Review of Privacy-preserving Mechanisms in Crowdsensing 计算机科学, 2022, 49(5): 303-310. https://doi.org/10.11896/jsjkx.210400077 |
[2] | 王乐业. 群智感知中的地理位置本地化差分隐私机制:现状与机遇 Geographic Local Differential Privacy in Crowdsensing:Current States and Future Opportunities 计算机科学, 2021, 48(6): 301-305. https://doi.org/10.11896/jsjkx.201200223 |
[3] | 张红颖, 申荣苗, 罗谦. 基于混合整数规划的停机位优化调度研究 Study on Optimal Scheduling of Gate Based on Mixed Integer Programming 计算机科学, 2020, 47(8): 278-283. https://doi.org/10.11896/jsjkx.190400154 |
[4] | 李建军, 汪校铃, 杨玉, 付佳. 基于CQPSO移动群智感知紧急任务分配方法研究 Emergency Task Assignment Method Based on CQPSO Mobile Crowd Sensing 计算机科学, 2020, 47(6A): 273-277. https://doi.org/10.11896/JsJkx.190700040 |
[5] | 周欣悦, 钱丽萍, 黄玉蘋, 吴远. 一种基于蚁群的电动汽车充电调度优化方法 Optimization Method of Electric Vehicles Charging Scheduling Based on Ant Colony 计算机科学, 2020, 47(11): 280-285. https://doi.org/10.11896/jsjkx.190700129 |
[6] | 蔡威, 白光伟, 沈航, 成昭炜, 张慧丽. 移动群智感知中基于强化学习的双赢博弈 Reinforcement Learning Based Win-Win Game for Mobile Crowdsensing 计算机科学, 2020, 47(10): 41-47. https://doi.org/10.11896/jsjkx.200700070 |
[7] | 刘丹. 基于雾计算和自评估的VANET聚类与协作感知 Fog Computing and Self-assessment Based Clustering and Cooperative Perception for VANET 计算机科学, 2020, 47(10): 55-62. https://doi.org/10.11896/jsjkx.200500154 |
[8] | 翟书颖, 李茹, 李波, 郝少阳. 视觉群智感知应用综述 Survey on Applications of Visual Crowdsensing 计算机科学, 2019, 46(6A): 11-15. |
[9] | 郑斐峰, 蒋娟, 梅启煌. 最小化集装箱运输成本的配载优化 Study on Stowage Optimization in Minimum Container Transportation Cost 计算机科学, 2019, 46(6): 239-245. https://doi.org/10.11896/j.issn.1002-137X.2019.06.036 |
[10] | 李卓, 徐哲, 陈昕, 李淑琴. 面向移动群智感知的位置相关在线多任务分配算法 Location-related Online Multi-task Assignment Algorithm for Mobile Crowd Sensing 计算机科学, 2019, 46(6): 102-106. https://doi.org/10.11896/j.issn.1002-137X.2019.06.014 |
[11] | 程显毅, 施佺, 朱建新, 陈凤妹, 代冉冉. 大数据环境下的车路人协同控制模型VID VID Model of Vehicles-infrastructure-driver Collaborative Control in Big Data Environment 计算机科学, 2019, 46(11A): 185-188. |
[12] | 郑香平, 於志勇, 温广槟. 地点网络中的社区发现 Community Discovery in Location Network 计算机科学, 2018, 45(6): 46-50. https://doi.org/10.11896/j.issn.1002-137X.2018.06.008 |
[13] | 周杰,於志勇,郭文忠,郭龙坤,朱伟平. “t-时隙k-覆盖”群智感知任务的参与者选择方法 Participant Selection Algorithm for t-Sweep k-Coverage Crowd Sensing Tasks 计算机科学, 2018, 45(2): 157-164. https://doi.org/10.11896/j.issn.1002-137X.2018.02.028 |
[14] | 曾子懿, 邱菡, 朱俊虎, 周天阳. 基于能力度量的网络安全实验环境多仿真规划 Network Security Experiment Environment Multi-emulation Planning Based on Capability Measurement 计算机科学, 2018, 45(11): 160-163. https://doi.org/10.11896/j.issn.1002-137X.2018.11.024 |
[15] | 王璐,张小宁,孙智慧,吴辉. 精确求解进港飞机调度双目标优化问题的epsilon约束算法 Exact Epsilon-constraint Algorithm for Bi-objective Optimization of Flight Arrival Scheduling Problem 计算机科学, 2017, 44(Z11): 580-582. https://doi.org/10.11896/j.issn.1002-137X.2017.11A.124 |
|