“t-时隙k-覆盖”任务模型和分配算法
背景简介
人们利用移动设备参与执行感知任务（即采集身边的某种状态数据），所有参与者贡献的数据被汇集起来，以较高准确度揭示大范围的环境或社会状态。这种被称为“群智感知”（Mobile Crowdsensing）的方式具有计算感知资源丰富、无需专门安装部署、配置灵活方便等优点，是传感基础设施的有益补充。
很多典型的任务，如对某地区环境质量的监测等，并不要求参与者时时刻刻对目标区域进行采样，而只要求在规定的每个时间间隔（即时隙，记作t）内完成一次采样，这样就可以利用参与者的移动来扩大覆盖范围。另一方面，为了提高数据质量，需要多个参与者提交同一时间地点的数据，即要求每个时隙目标地点至少被k个人覆盖。感知任务的这种细粒度需求在带来好处的同时也带来了理论和技术上的挑战。
图1 福州市内河及“保护河道，人人有责”告示牌
图2 一个参与者经过河边的骑行轨迹
理论和技术简介
我们构建了“t-时隙k-覆盖”群智感知任务质量模型，证明了最少代价或最大覆盖完成该类任务是NP-hard问题。通过特殊的构造技巧，在问题规模较小时可以用线性规划求解；但是随着问题规模的增大，线性规划越来越力不从心，在证明其子模性的基础上，提出了有性能下限保证的几种基于贪心策略的参与者选择算法（如GI-DPSO），并分析了其计算复杂度。
图3 基于贪心初始化的离散粒子群算法（GI-DPSO）
演示简介
城市内河环境监测主要针对排放污水、张网捕鱼、丢弃垃圾、违法占用河道及岸线等环境破坏行为。近一百位经过河边的单车骑行者是候选的监测任务参与者。对于指定的一条内河，目标是选择尽可能少的参与者对该内河进行时空覆盖（t、k已取默认值）。
演示界面分为左上、左下、右上、右下四个部分。左上可以切换显示哪种参与者选择策略，目前演示了随机策略和GI-DPSO策略（基于贪心初始化的离散离散粒子群算法）。左下展示了福州主要内河所在位置，可以指定任务是监测哪一条。当点击某条内河时，会显示当前策略下该内河的候选监测任务参与者；点击某个参与者，可获得其骑行轨迹即可视化的覆盖范围。同时在选中某条内河时，可通过切换左上的两种选择策略，观察同一内河在不同策略下选择的参与者。右上通过下拉框的方式选择要监测的内河，与左下地图同步。右下对比了两种策略监测不同内河所需参与者的人数。
图4 面向内河环境监测的参与者选择演示界面
成果列表
- 【论文】Z Yu, J Zhou, W Guo, L Guo, Z Yu. “Participant selection for t-sweep k-coverage crowd sensing tasks”, World Wide Web 2018, 21(3): 741-758.
- 【论文】Z Yu, W Zhu, L Guo, W Guo, Z Yu. “Task allocation for crowdsensing based on submodular optimisation”, International Journal of Ad Hoc and Ubiquitous Computing, 2020, 33(1): 48-61.
- 【论文】李晓东, 於志勇, 黄昉菀, 朱伟平, 涂淳钰, 郑伟楠. “面向河道环境监测的群智感知参与者选择策略”, 计算机科学, 2022, 49(5): 371-379.
- 【专利】於志勇, 郭文忠, 郭龙坤, 周杰. “一种基于贪心策略的群智感知参与者选择方法”, 中国专利，2019年授权, ZL20161118 9560.1