面向单任务质量保障的移动群智感知任务分配

doi:10.19678/j.issn.1000-3428.0064071

摘要/Abstract

摘要： 在移动群智感知中，现有的任务分配方法大多关注平台的整体感知质量，未充分考虑任务对工人、预算等资源的竞争，无法有效保障大规模任务分配场景下每个任务的感知质量，从而导致平台资源利用率降低。针对该问题，提出一种面向单任务质量保障的任务分配方法。为高效利用平台预算，考虑任务的难度和位置以及工人的设备能耗和理性因素，设计平台的激励成本。为保障每个任务的感知质量，考虑任务间的资源竞争情况并设计2种衡量指标，分别是从任务的角度根据差异化感知质量需求设计任务覆盖效率，以及从工人的角度基于最大熵原理设计工人利用效率，将这2种衡量指标相结合作为平台的系统效用，在平台资源有限的情况下以平台系统效用最大化为优化目标，提出一种融合交叉和变异操作的天牛群（BSO）算法。实验结果表明，与PSO、GA等基线方法相比，BSO算法的系统效用最大值平均提升13.51%，寻优速度平均提高40.61%，利用该算法获取的具有最大系统效用的任务分配方案可以有效保障每个任务的感知质量。

关键词: 移动群智感知, 任务分配, 单任务质量保障, 系统效用, 天牛群算法

Abstract: In Mobile Crowd Sensing(MCS), most existing task allocation methods focus on the overall sensing quality of the platform and do not fully consider task competition for workers, budgets and other resources.This cannot effectively guarantee the sensing quality of each task in a large-scale task allocation scenario, resulting in a reduction of resource utilization of the platform.To solve this problem, a task allocation method for individual task quality assurance is proposed.To efficiently use the platform budget, the incentive cost of the platform is designed by considering the difficulty and location of tasks and the energy consumption and rationality of worker equipment.To ensure the sensing quality of each task, the resource competition between tasks is considered and two measurement indicators are implemented:the task coverage efficiency according to the differentiated perceived quality requirements from the perspective of tasks and the worker utilization efficiency based on the maximum entropy principle from the perspective of workers.These two measurement indicators are combined as the system utility of the platform.In the case of limited platform resources, a Beetle Swarm Optimization(BSO) algorithm that integrates crossover and mutation operations is proposed for maximizing the system utility of the platform.The experiments show that the maximum system utility and optimization speed of the BSO algorithm increases by 13.51% and 40.61% on average, respectively, compared with Particle Swarm Optimization(PSO), Genetic Algorithm(GA), and other baseline methods.The task allocation scheme with the maximum system utility obtained by this algorithm can effectively ensure the sensing quality of each task.

Key words: Mobile Crowd Sensing(MCS), task allocation, individual task quality assurance, system utility, Beetle Swarm Optimization(BSO) algorithm

中图分类号:

TP393

杨桂松, 吴笑天, 高丽, 何杏宇. 面向单任务质量保障的移动群智感知任务分配[J]. 计算机工程, 2022, 48(9): 45-54.

YANG Guisong, WU Xiaotian, GAO Li, HE Xingyu. Task Allocation Towards Individual Task Quality Assurance in Mobile Crowd Sensing[J]. Computer Engineering, 2022, 48(9): 45-54.

https://www.ecice06.com/CN/Y2022/V48/I9/45

图/表 13

20220917173550

20220917173554

20220917173558

20220917173602

20220917173606

20220917173610

20220917173614

20220917173618

20220917173622

20220917173626

20220917173633

20220917173637

20220917173641

参考文献

[1] 赵东, 马华东.群智感知网络的发展及挑战[J].信息通信技术, 2014, 8(5):66-70. ZHAO D, MA H D.Development and challenges of crowd sensing networks[J].Information and Communications Technologies, 2014, 8(5):66-70.(in Chinese)
[2] SEID S, ZENNARO M, LIBSE M, et al.Mobile crowd sensing based road surface monitoring using smartphone vibration sensor and lorawan[C]//Proceedings of the 1st Workshop on Experiences with the Design and Implemen-tation of Frugal Smart Objects.Washington D.C., USA:IEEE Press, 2020:36-41.
[3] 张建宗, 陶丹.移动群智感知下的交通流速缺失数据恢复算法[J].小型微型计算机系统, 2021, 42(2):225-230. ZHANG J Z, TAO D.Crowdsensing based traffic velocity missing data recovery algorithm[J].Journal of Chinese Computer Systems, 2021, 42(2):225-230.(in Chinese)
[4] BOCK F, DI MARTINO S, ORIGLIA A.Smart parking:using a crowd of taxis to sense on-street parking space availability[J].IEEE Transactions on Intelligent Transportation Systems, 2020, 21(2):496-508.
[5] ZHANG D Q, XIONG H Y, WANG L Y, et al.CrowdRecruiter:selecting participants for piggyback crowdsensing under probabilistic coverage constraint[C]//Proceedings of 2014 ACM International Joint Conference on Pervasive and Ubiquitous Computing.New York, USA:ACM Press, 2014:703-714.
[6] ZHANG M T, YANG P L, TIAN C, et al.Quality-aware sensing coverage in budget-constrained mobile crowdsensing networks[J].IEEE Transactions on Vehicular Technology, 2016, 65(9):7698-7707.
[7] LI X, ZHANG X L.Multi-task allocation under time constraints in mobile crowdsensing[J].IEEE Transactions on Mobile Computing, 2021, 20(4):1494-1510.
[8] SUN G D, WANG Y N, DING X J, et al.Cost-fair task allocation in mobile crowd sensing with probabilistic users[J].IEEE Transactions on Mobile Computing, 2021, 20(2):403-415.
[9] 杨桂松, 王不野, 何杏宇.面向延迟接受的移动群智感知多任务分配[J].计算机应用研究, 2021, 38(8):2440-2444. YANG G S, WANG B Y, HE X Y.Multi-task allocation based on deferred acceptance in mobile crowd sensing[J].Application Research of Computers, 2021, 38(8):2440-2444.(in Chinese)
[10] ZHOU S W, HE Y, XIANG S Z, et al.Region-based compressive networked storage with lazy encoding[J].IEEE Transactions on Parallel and Distributed Systems, 2019, 30(6):1390-1402.
[11] LIU W B, WANG L Y, WANG E, et al.Reinforcement learning-based cell selection in sparse mobile crowdsensing[J].Computer Networks, 2019, 161:102-114.
[12] YANG J, FU L, YANG B R, et al.Participant service quality aware data collecting mechanism with high coverage for mobile crowdsensing[J].IEEE Access, 2020, 8:10628-10639.
[13] AKTER S, DAO T N, YOON S.Time-constrained task allocation and worker routing in mobile crowd-sensing using a decomposition technique and deep Q-learning[J].IEEE Access, 2021, 9:95808-95822.
[14] ZHAO Y O, MENG X Y, KANG B R.A task allocation scheme for protecting location privacy in vehicle ad hoc networks[C]//Proceedings of IEEE International Conference on Automation, Electronics and Electrical Engineering.Washington D.C., USA:IEEE Press, 2020:395-402.
[15] GAO H, FENG J H, XIAO Y, et al.A UAV-assisted multi-task allocation method for mobile crowd sensing[EB/OL].[2022-02-05].https://acris.aalto.fi/ws/portalfiles/portal/79542109/TMC_2021_05_0361.pdf.
[16] WANG J T, WANG F, WANG Y S, et al.Allocating heterogeneous tasks in participatory sensing with diverse participant-side factors[J].IEEE Transactions on Mobile Computing, 2019, 18(9):1979-1991.
[17] XIONG H Y, ZHANG D Q, CHEN G L, et al.CrowdTasker:maximizing coverage quality in piggyback crowdsensing under budget constraint[C]//Proceedings of IEEE International Conference on Pervasive Computing and Communications.Washington D.C., USA:IEEE Press, 2015:55-62.
[18] WANG J T, WANG Y S, ZHANG D Q, et al.Fine-grained multitask allocation for participatory sensing with a shared budget[J].IEEE Internet of Things Journal, 2016, 3(6):1395-1405.
[19] WANG J T, WANG Y S, ZHANG D Q, et al.PSAllocator:multi-task allocation for participatory sensing with sensing capability constraints[C]//Proceedings of 2017 ACM Conference on Computer Supported Cooperative Work and Social Computing.New York, USA:ACM Press, 2017:1139-1151.
[20] KARALIOPOULOS M, BAKALI E.Optimizing mobile crowdsensing platforms for boundedly rational users[J].IEEE Transactions on Mobile Computing, 2022, 21(4):1305-1318.
[21] LAI C, ZHANG X L.Duration-sensitive task allocation for mobile crowd sensing[J].IEEE Systems Journal, 2020, 14(3):4430-4441.
[22] 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.
[23] WANG T T, YANG L.Beetle swarm optimization algorithm:theory and application[EB/OL].[2022-02-05].https://arxiv.org/abs/1808.00206.
[24] KENNEDY J, EBERHART R.Particle swarm optimization[C]//Proceedings of IEEE International Conference on Neural Networks.Washington D.C., USA:IEEE Press, 1995:1942-1948.
[25] HOLLAND J H.Genetic algorithms[J].Scientific American, 1992, 267(1):66-73.
[26] SAREMI S, MIRJALILI S, LEWIS A.Grasshopper optimisation algorithm:theory and application[J].Advances in Engineering Software, 2017, 105:30-47.
[27] WANG J T, WANG Y S, ZHANG D Q, et al.Multi-task allocation in mobile crowd sensing with individual task quality assurance[J].IEEE Transactions on Mobile Computing, 2018, 17(9):2101-2113.

选择文件类型/文献管理软件名称

选择包含的内容