计算机科学 ›› 2022, Vol. 49 ›› Issue (5): 371-379.doi: 10.11896/jsjkx.210200005

• 交叉与前沿 • 上一篇    

面向河道环境监测的群智感知参与者选择策略

李晓东1, 於志勇1,2, 黄昉菀1,2, 朱伟平1, 涂淳钰1, 郑伟楠1   

  1. 1 福州大学数学与计算机科学学院 福州350108
    2 福建省网络计算与智能信息处理重点实验室(福州大学) 福州350108
  • 收稿日期:2021-02-01 修回日期:2021-05-27 出版日期:2022-05-15 发布日期:2022-05-06
  • 通讯作者: 黄昉菀(hfw@fzu.edu.cn)
  • 作者简介:(lxdydyx@163.com)
  • 基金资助:
    国家自然科学基金(61772136)

Participant Selection Strategies Based on Crowd Sensing for River Environmental Monitoring

LI Xiao-dong1, YU Zhi-yong1,2, HUANG Fang-wan1,2, ZHU Wei-ping1, TU Chun-yu1, ZHENG Wei-nan1   

  1. 1 College of Mathematics and Computer Science,Fuzhou University,Fuzhou 350108,China
    2 Fujian Key Laboratory of Network Computing and Intelligent Information Processing (Fuzhou University),Fuzhou 350108,China
  • Received:2021-02-01 Revised:2021-05-27 Online:2022-05-15 Published:2022-05-06
  • About author:LI Xiao-dong,born in 1994,postgra-duate.His main research interests include crowd sensing and so on.
    HUANG Fang-wan,born in 1980,master,senior lecturer,is a member of China Computer Federation.Her main research interests include computational intelligence,machine learning and big data analysis.
  • Supported by:
    National Natural Science Foundation of China(61772136).

摘要: 城市内河周边环境常常受到破坏和污染,如何有效地对河道进行监测逐渐引起公众、政府和学术界的关注。目前传统的监测方式存在成本高昂、覆盖面不足等缺陷。鉴于智能移动设备的不断普及,文中提出利用群智感知来高效监测河道环境的新思路。该问题可描述为假定每一河段附近有c个位置点可监测该河段,然后根据大量用户的移动轨迹选择出其中r个用户来共同完成s个时段对所有河段的监测。文中规定用户数r越小,监测成本越少。设计了逐步贪心策略、全局贪心策略和整数规划策略用于解决该问题,即选择最少参与者达到“s时长-c范围-r用户”的监测目标。将上述策略应用于福州市台江区部分河道的环境监测,实验结果表明,上述策略均能获得比随机策略更好的解,其中整数规划策略的表现最好。但是,随着问题规模的变大,解决小规模整数规划的隐枚举算法会出现无法求解的情况,因此提出了基于贪心初始化的离散粒子群算法(Greedy Initialization-Discrete Particle Swarm Optimization,GI-DPSO)。虽然该算法可以求解大规模整数规划,但计算费时。综合考虑监测成本和计算代价,建议对小规模问题采用整数规划策略,对大规模问题采用全局贪心策略。

关键词: 河道环境监测, 离散粒子群算法, 群智感知, 贪心策略, 整数规划

Abstract: The surrounding environment of rivers in city is often damaged and polluted.How to effectively monitor rivers has gradually attracted the attention of public,government and academia.At present,traditional monitoring methods are facing with high cost,insufficient coverage and other defects.With the increasing popularity of intelligent mobile devices,a new idea of using crowd sensing to efficiently monitor the river environment is proposed in this paper.The problem can be described as the assumption that each river reach contains c monitoring points,and then r users are selected according to the movement tracks of a large number of users to jointly complete the monitoring of all river reaches in s periods.It is stipulated that the smaller the number of users r,the less the monitoring cost.The stepwise-greedy strategy,the global-greedy strategy and the integer-programming stra-tegy are designed to solve this problem,that is,to select the least number of participants to achieve the monitoring goal of “s durations-c ranges-r users”.In this paper,the above strategies are applied to environmental monitoring of some rivers in Taijiang,Fuzhou.Experimental results show that the above strategies can obtain better solutions than the random strategy,and the integer-programming strategy has the best performance.However,with the increase of the scale of the problem,the implicit enumeration algorithm used to solve the small-scale integer programming will be unable to solve the situation.Motivated by this,this paper designs a discrete particle swarm optimization algorithm based on greedy initialization(GI-DPSO).Although this algorithm can solve large-scale integer programming,it is time-consuming.Considering the monitoring cost and computational cost comprehensively,it is suggested that the integer-programming strategy can be adopted for small-scale problems and the global-greedy strategy can be adopted for large-scale problems.

Key words: Crowd sensing, Discrete particle swarm optimization algorithm, Greedy strategy, Integer programming, River environmental monitoring

中图分类号: 

  • TP391
[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
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!