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

Participant Selection Strategies Based on Crowd Sensing for River Environmental Monitoring

作　　者：李晓东 於志勇[1,2] 黄昉菀[1,2] 朱伟平[1] 涂淳钰 郑伟楠 LI Xiao-dong;YU Zhi-yong;HUANG Fang-wan;ZHU Wei-ping;TU Chun-yu;ZHENG Wei-nan(College of Mathematics and Computer Science,Fuzhou University,Fuzhou 350108,China;Fujian Key Laboratory of Network Computing and Intelligent Information Processing(Fuzhou University),Fuzhou 350108,China)

机构地区：[1]福州大学数学与计算机科学学院,福州350108 [2]福建省网络计算与智能信息处理重点实验室(福州大学),福州350108

出　　处：《计算机科学》2022年第5期371-379,共9页Computer Science

基　　金：国家自然科学基金(61772136)。

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

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

分 类 号：TP391[自动化与计算机技术—计算机应用技术]