基于IWOA群智感知中数量敏感的任务分配方法

doi:10.12263/DZXB.20210198

电子学报 ›› 2022, Vol. 50 ›› Issue (10): 2489-2502.DOI: 10.12263/DZXB.20210198

基于IWOA群智感知中数量敏感的任务分配方法

蒋伟进¹^,²^,³, 张婉清¹^,², 陈萍萍²^,³, 陈君鹏²^,³, 孙永霞²^,³, 刘权¹

^1.湖南工商大学前沿交叉学院，湖南长沙 410205
^2.新零售虚拟现实技术湖南省重点实验室，湖南长沙 410205
^3.湖南工商大学计算机学院，湖南长沙 410205

收稿日期:2021-02-02 修回日期:2021-08-04 出版日期:2022-10-25
- 作者简介:
- 蒋伟进男，1964年出生，湖南桃江人.博士，二级教授.研究方向为云计算安全、边缘计算、群智感知、社会计算等.E-mail: jwjnudt@163.com
  张婉清女，1997年出生，河南洛阳人. 硕士研究生. 研究方向为群智感知、移动边缘计算.E-mail: 727149424@qq.com
- 基金资助:
- 国家自然科学基金面上项目 (61772196); 湖南省自然科学基金面上项目 (2020JJ4249); 湖南省社会科学基金重点项目 (2016ZDB006); 湖南省社会科学成果评审委员会课题重点项目 (湘社评19ZD1005); 湖南省研究生科研创新项目 (CX20211108)

Quantity Sensitive Task Allocation Method Based on IWOA in Group Intelligence Perception

JIANG Wei-jin¹^,²^,³, ZHANG Wan-qing¹^,², CHEN Ping-ping²^,³, CHEN Jun-peng²^,³, SUN Yong-xia²^,³, LIU Quan¹

^1.College of Frontier Intersection，Hunan University of Technology and Business，Changsha，Hunan 410205，China
^2.Key Laboratory of Hunan Province for New Retail Virtual Reality Technology，Changsha，Hunan 410205，China
^3.School of Computer Science，Hunan University of Technology and Business，Changsha，Hunan 410205，China

Received:2021-02-02 Revised:2021-08-04 Online:2022-10-25 Published:2022-10-11

摘要/Abstract

摘要：

随着移动终端的大规模普及，群智感知技术以其高效且成本低廉的优势逐渐取代现有的静态传感器，成为一种新兴的数据收集方式.如何在保证质量、降低成本的前提下，把感知任务分配给最佳执行用户以实现用户任务完成数量的最大化，是数量敏感任务分配问题研究的重点.基于此，提出一种结合非线性递减收敛因子、最优局部抖动以及动态位置更新三种操作的改进鲸鱼优化算法（Improved Whale Optimization Algorithm，IWOA），并将其用于求解所提出的任务分配问题.对数量敏感的任务分配问题进行建模，根据用户与任务间的适应程度，定义空间匹配度与技能匹配度.在用户执行任务的过程中考虑到用户的学习能力，引入技能更新机制对用户已有技能进行及时更新，以此提高任务分配的效率.综合考虑预算、用户在线时长以及感知任务完成质量，对最大化任务完成数量的任务分配问题进行合理定义，并从为任务选择最佳执行用户的角度出发，设计一种基于优先级的用户选择策略，以实现在保证感知任务基本完成质量的前提下，降低任务分配的成本.在最优任务分配方案的求解过程中，利用改进算法对每次迭代初始的任务序列进行不断优化，经过有限次迭代即可得到最终结果.将改进算法与其他优化算法在相同环境下进行对比实验，结果表明改进算法在求解任务分配问题时具有更高的性能.

关键词: 数量敏感, 任务分配, 改进的鲸鱼优化算法, 技能更新机制, 优先级

Abstract:

With the large-scale popularity of mobile terminals, group intelligence sensing technology gradually replaces the existing static sensors with its advantages of high efficiency and low cost, becoming an emerging data collection method. How to assign perception tasks to the best performing users under the premise of ensuring quality and reducing costs to maximize the number of user tasks completed is the focus of the research on quantity sensitive task allocation. Based on this, a solution based on the improved whale optimization algorithm(IWOA) that combines the three operations of nonlinear decreasing convergence factor, optimal local jitter, and dynamic position update is put forward, which is used to solve the proposed task allocation problem. First, modeling the quantity sensitive task allocation problem, and then defining the spatial matching degree and skill matching degree according to the degree of adaptation between the user and the task. Taking into account the user's learning ability during the user's task execution, the skill update mechanism is introduced to update the user's existing skills in a timely manner, so as to improve task allocation effectiveness. Secondly, comprehensively considering the budget, the user's online time and the perceived task completion quality, and reasonably defining the task allocation problem that maximizes the number of tasks completed. In addition, from the perspective of selecting the best performing user for the task, designing a user selection strategy based on user’s priority to reduce the cost of task allocation while ensuring the quality of the perceived task is basically completed. Then, in the process of solving the optimal task allocation plan, the improved algorithm is used to continuously optimize the initial task sequences of each iteration, and the final result can be obtained after a limited number of iterations. Finally, the improved algorithm is compared with other optimization algorithms in the same environment, and the results show that the improved algorithm has higher performance in solving task allocation problem.

Key words: quantity sensitive, task allocation, improved Whale Optimization Algorithm, skill update mechanism, priority

中图分类号:

TP393

蒋伟进, 张婉清, 陈萍萍, 等. 基于IWOA群智感知中数量敏感的任务分配方法[J]. 电子学报, 2022, 50(10): 2489-2502.

Wei-jin JIANG, Wan-qing ZHANG, Ping-ping CHEN, et al. Quantity Sensitive Task Allocation Method Based on IWOA in Group Intelligence Perception[J]. Acta Electronica Sinica, 2022, 50(10): 2489-2502.

图/表 24

图1 用户-任务分布情况

图2 用户移动速度的变化趋势

图3 技能信息与感知内容匹配示意图

图4 用户感知数据质量与质量生成函数值的关系

图5 两种非线性递减收敛因子的变化趋势

图6 基于改进鲸鱼优化算法的流程

图7 初始任务序列

图8 第一个用户优先级序列

图9 第一次用户选择结果

图10 第二个用户优先级序列

图11 第二次用户选择结果

图12 第四次用户选择结果

图13 最终用户选择结果

图14 数量敏感的任务分配流程

表1 相关参数设置

参数	取值
P_a	[0, 1]
用户数	6
用户所在位置	[0-30, 0-30]
用户可工作时长/min	[200, 500]
用户技能熟练度	[0, 1]
用户基本移动速度/(m/s)	[1.1, 1.5]
用户基本执行速度	[1, 2]
用户基本感知数据质量	[0, 1)
任务数	20
任务所需数据量	[40, 70]
任务所在位置	[0-30, 0-30]
单位移动成本	0.7
单位执行成本	0.2
所有系数	1

图15 最大任务完成数量

图16 总成本

图17 数据质量

图18 最大任务完成数量

图19 总成本

图20 数据质量

图21 最大任务完成数量

图22 总成本

图23 数据质量

参考文献 39

1	李卓, 徐哲, 陈昕, 等. 面向移动群智感知的位置相关在线多任务分配算法[J]. 计算机科学, 2019, 46(6): 102-106.
	LI Z, XU Z, CHEN X, et al. Location-related online multi-task assignment algorithm for mobile crowd sensing[J]. Computer Science, 2019, 46(6): 102-106. (in Chinese)
2	杜扬, 黄河, 孙玉娥, 等. 地理位置相关移动感知系统任务分配问题研究[J]. 计算机研究与发展, 2014, 51(11): 2374-2381.
	DU Y, HUANG H, SUN Y, et al. A location-based task assignment mechanism for mobile phone sensing[J]. Journal of Computer Research and Development, 2014, 51(11): 2374-2381. (in Chinese)
3	ESTRADA R, MIZOUNI R, OTROK H, et al. A crowd-sensing framework for allocation of time-constrained and location-based tasks[J]. IEEE Transactions on Services Computing, 2020, 13(5): 769-785.
4	GONG W, ZHANG B X, LI C. Location-based online task assignment and path planning for mobile crowdsensing[J]. IEEE Transactions on Vehicular Technology, 2019, 68(2): 1772-1783.
5	ZHAO B X, WANG Y J, LI Y S, et al. Task allocation model based on worker friend relationship for mobile crowdsourcing[J]. Sensors(Basel, Switzerland), 2019, 19(4): 921.
6	TU J Z, YU G X, WANG J, et al. CrowdWT: Crowdsourcing via joint modeling of workers and tasks[J]. ACM Transactions on Knowledge Discovery from Data, 2021, 15(1): 1-24.
7	ZHU W P, GUO W Z, YU Z Y, et al. Multitask allocation to heterogeneous participants in mobile crowd sensing[J]. Wireless Communications and Mobile Computing, 2018, 2018: 7218061.
8	ALSAYASNEH M, AMER-YAHIA S, GAUSSIER E, et al. Personalized and diverse task composition in crowdsourcing[J]. IEEE Transactions on Knowledge and Data Engineering, 2018, 30(1): 128-141.
9	GAO X F, HUANG H W, LIU C L, et al. Quality inference based task assignment in mobile crowdsensing[J]. IEEE Transactions on Knowledge and Data Engineering, 2021, 33(10): 3410-3423.
10	PAN Q X, PAN T W, DONG H B, et al. An online task assignment based on quality constraint for spatio-temporal crowdsourcing[J]. IEEE Access, 2019, 7: 170292-170303.
11	TU J Y, CHENG P, CHEN L. Quality-assured synchronized task assignment in crowdsourcing[J]. IEEE Transactions on Knowledge and Data Engineering, 2021, 33(3): 1156-1168.
12	SONG S W, LIU Z D, LI Z J, et al. Coverage-oriented task assignment for mobile crowdsensing[J]. IEEE Internet of Things Journal, 2020, 7(8): 7407-7418.
13	CHEN J Y, YANG J S. Maximizing coverage quality with budget constrained in mobile crowd-sensing network for environmental monitoring applications[J]. Sensors(Basel, Switzerland), 2019, 19(10): 2399.
14	EL-ASHMAWI W H, ALI A F. A modified salp swarm algorithm for task assignment problem[J]. Applied Soft Computing, 2020, 94: 106445.
15	HASSAN U UL, CURRY E. Efficient task assignment for spatial crowdsourcing: A combinatorial fractional optimization approach with semi-bandit learning[J]. Expert Systems With Applications, 2016, 58: 36-56.
16	WU P K, NGAI E W T, WU Y Y. Toward a real-time and budget-aware task package allocation in spatial crowdsourcing[J]. Decision Support Systems, 2018, 110: 107-117.
17	MIAO C Y, YU H, SHEN Z Q, et al. Balancing quality and budget considerations in mobile crowdsourcing[J]. Decision Support Systems, 2016, 90: 56-64.
18	LIU W B, YANG Y J, WANG E, et al. Prediction based user selection in time-sensitive mobile crowdsensing[C]//2017 14th Annual IEEE International Conference on Sensing, Communication, and Networking. San Diego: IEEE, 2017: 1-9.
19	MIRJALILI S, LEWIS A. The whale optimization algorithm[J]. Advances in Engineering Software, 2016, 95: 51-67.
20	杨正清, 周朝荣, 袁姝. 移动群智感知系统中基于离散布谷鸟搜索算法的任务分配[J]. 计算机应用, 2019, 39(9): 2778-2783.
	YANG Z Q, ZHOU Z R, YUAN S. Task assignment based on discrete cuckoo search algorithm in mobile crowd sensing system[J]. Journal of Computer Applications, 2019, 39(9): 2778-2783. (in Chinese)
21	姚远远, 叶春明. 求解作业车间调度问题的改进混合灰狼优化算法[J]. 计算机应用研究, 2018, 35(5): 1310-1314.
	YAO Y Y, YE C M. Solving Job-Shop scheduling problem using improved hybrid grey wolf optimizer[J]. Application Research of Computers, 2018, 35(5): 1310-1314. (in Chinese)
22	范泽军, 沈立炜, 彭鑫, 等. 基于约束的空间众包多阶段任务分配[J]. 计算机学报, 2019, 42(12): 2722-2741.
	FAN Z J, SHEN L W, PENG X, et al. Multi stage task allocation on constrained spatial crowdsourcing[J]. Chinese Journal of Computers, 2019, 42(12): 2722-2741. (in Chinese)
23	JIANG N, XU D, ZHOU J, et al. Toward optimal participant decisions with voting-based incentive model for crowd sensing[J]. Information Sciences, 2020, 512: 1-17.
24	WANG T X, WEI X L, TANG C G, et al. Efficient multi-tasks scheduling algorithm in mobile cloud computing with time constraints[J]. Peer-to-Peer Networking and Applications, 2018, 11(4): 793-807.
25	LADUMOR D P, TRIVEDI I N, JANGIR P, et al. A whale optimization algorithm approach for unit commitment problem solution[C]//Proceedings of National Conference Advancement in Electrical & Power Electronics Engineering(AEPEE 2016). Morbi: AEPEE, 2016: DOI:10.13140/RG.2.1.1290.2003 .
26	WANG W D, GAO H, LIU C H, et al. Credible and energy-aware participant selection with limited task budget for mobile crowd sensing[J]. Ad Hoc Networks, 2016, 43: 56-70.
27	郭兴海, 计明军, 温都苏, 等. “最后一公里”配送的分布式多无人机的任务分配和路径规划[J]. 系统工程理论与实践, 2021, 41(4): 946-961.
	GUO X H, JI M J, WEN D S, et al. Task assignment and path planning for distributed multiple unmanned aerial vehicles in the “last Mile”[J]. Systems Engineering-Theory & Practice, 2021, 41(4): 946-961. (in Chinese)
28	XIE X F, LIU J M. Multiagent optimization system for solving the traveling salesman problem(TSP)[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 2009, 39(2): 489-502.
29	蔡雨岑, 杜鹏桢. 基于平衡鲸鱼优化算法的无人车路径规划[J]. 控制与决策, 2021, 36(11): 2647-2655.
	CAI Y C, DU P Z. Path planning of unmanned ground vehicle based on balanced whale optimization algorithm[J]. Control and Decision, 2021, 36(11): 2647-2655. (in Chinese)
30	GAO H, SHI Y J, PUN C M, et al. An improved artificial bee colony algorithm with its application[J]. IEEE Transactions on Industrial Informatics, 2019, 15(4): 1853-1865.
31	CHI M W. An improved wolf pack algorithm[C]//AIIPCC'19: Proceedings of the International Conference on Artificial Intelligence, Information Processing and Cloud Computing. Sanya: ACM, 2019: 1-5.
32	IBRAHIM R A, EWEES A A, OLIVA D, et al. Improved salp swarm algorithm based on particle swarm optimization for feature selection[J].Journal of Ambient Intelligence and Humanized Computing, 2019, 10(8): 3155-3169.
33	LI Z Y. An improved genetic algorithm for solving packing problem[C]//Proceedings of the 2016 4th International Conference on Machinery, Materials and Computing Technology & Advances in Engineering Research. Paris: Atlantis Press, 2016: 1815-1820.
34	WANG F, ZHANG H, LI K S, et al. A hybrid particle swarm optimization algorithm using adaptive learning strategy[J]. Information Sciences, 2018, 436/437: 162-177.
35	GHAREHCHOPOGH F S, GHOLIZADEH H. A comprehensive survey: Whale optimization algorithm and its applications[J]. Swarm and Evolutionary Computation, 2019, 48: 1-24.
36	TONG Y X, WANG L B, ZHOU Z M, et al. Flexible online task assignment in real-time spatial data[J]. Proceedings of the VLDB Endowment, 2017, 10(11): 1334-1345.
37	陈思光, 陈佳民, 赵传信. 基于深度强化学习的云边协同计算迁移研究[J]. 电子学报, 2021, 49(1): 157-166.
	CHEN S G, CHEN J M, ZHAO C X. Deep reinforcement learning based cloud-edge collaborative computation offloading mechanism[J]. Acta Electronica Sinica, 2021, 49(1): 157-166. (in Chinese)
38	李博扬, 成雨蓉, 王国仁, 等. 新型时空众包平台中的在线三维稳定匹配问题[J]. 软件学报, 2020, 31(12): 3836-3851.
	LI B Y, CHENG Y R, WANG G R, et al. 3D-online stable matching problem for new spatial crowdsourcing platforms[J]. Journal of Software, 2020, 31(12): 3836-3851. (in Chinese)
39	王乐乐, 眭泽智, 蒲志强, 等. 一种改进RRT的多机器人编队路径规划算法[J]. 电子学报, 2020, 48(11): 2138-2145.
	WANG L L, SUI Z Z, PU Z Q, et al. An improved RRT algorithm for multi-robot formation path planning[J]. Acta Electronica Sinica, 2020, 48(11): 2138-2145. (in Chinese)

[1]	段毅, 谭贤四, 曲智国, 王红. 基于分支定界法的相控阵雷达事件调度算法[J]. 电子学报, 2019, 47(6): 1309-1315.
[2]	刘俊秀, 黄星月, 罗玉玲, 曹弋. 脉冲神经网络硬件互连系统的动态优先级仲裁策略[J]. 电子学报, 2018, 46(8): 1898-1905.
[3]	木文浩, 保利勇, 丁洪伟, 赵一帆. 离散时间闸门式多级门限服务的两级优先级轮询排队系统分析[J]. 电子学报, 2018, 46(2): 276-280.
[4]	张浩为, 谢军伟, 师俊朋, 宗彬锋, 盛川. 动态优先级下防空相控阵雷达在线交错调度算法[J]. 电子学报, 2018, 46(1): 55-60.
[5]	韩博文, 姚佩阳, 孙昱. 基于多目标MSQPSO算法的UAVS协同任务分配[J]. 电子学报, 2017, 45(8): 1856-1863.
[6]	田相轩, 杨君刚, 车雅良, 牛俊勇, 刘故箐, 王新桐. 多域光网络中基于优先级的波长路由分配算法[J]. 电子学报, 2014, 42(4): 625-632.
[7]	谭国真;杨际祥;王凡;潘东. 多核集群任务分配问题复杂性分析[J]. 电子学报, 2012, 40(2): 241-246.
[8]	潘伟丰, 李兵, 马于涛, 刘婧. 基于复杂软件网络的回归测试用例优先级排序[J]. 电子学报, 2012, 40(12): 2456-2465.
[9]	管爱红;王波云;张元;傅洪亮. OBS网络中基于优先级与参数可调的偏射路由算法[J]. 电子学报, 2011, 39(7): 1668-1672.
[10]	赵鹏;王大伟;李思昆. 面向SoC任务分配的应用程序存储需求量分析方法[J]. 电子学报, 2010, 38(3): 541-545.
[11]	朱颖;武穆清. 基于802.11e的无线多跳自适应合作式QoS算法[J]. 电子学报, 2010, 38(10): 2350-2357.
[12]	杨志军;赵东风;丁洪伟;赵一帆. 两级优先级控制轮询系统研究[J]. 电子学报, 2009, 37(7): 1452-1456.
[13]	苑迎春;李小平;王茜;张晓东;. 基于优先级规则的网格工作流调度[J]. 电子学报, 2009, 37(7): 1457-1464.
[14]	张瑜;李凡长. 基于DFS的多Agent动态任务分配算法研究[J]. 电子学报, 2009, 37(11): 2551-2556.
[15]	伊鹏, 汪斌强, 郭云飞, 李挥. 一种可提供QoS保障的新型交换结构[J]. 电子学报, 2007, 35(7): 1257-1263.

基于IWOA群智感知中数量敏感的任务分配方法

Quantity Sensitive Task Allocation Method Based on IWOA in Group Intelligence Perception

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 24

参考文献 39

相关文章 15

编辑推荐

Metrics