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

蒋伟进; 张婉清; 陈萍萍; 陈君鹏; 孙永霞; 刘权

doi:10.12263/DZXB.20210198

您当前的位置：

首页 >

文章列表页 >

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

学术论文 | 更新时间：2025-12-08

- 基于IWOA群智感知中数量敏感的任务分配方法
- Quantity Sensitive Task Allocation Method Based on IWOA in Group Intelligence Perception
- 电子学报 2022年50卷第10期页码：2489-2502
- 作者机构：
  
  1.湖南工商大学前沿交叉学院，湖南长沙 410205
  2.新零售虚拟现实技术湖南省重点实验室，湖南长沙 410205
  3.湖南工商大学计算机学院，湖南长沙 410205
- 作者简介：
  
  [ "蒋伟进男，1964年出生，湖南桃江人.博士，二级教授.研究方向为云计算安全、边缘计算、群智感知、社会计算等.E-mail: jwjnudt@163.com" ]
  [ "张婉清女，1997年出生，河南洛阳人. 硕士研究生. 研究方向为群智感知、移动边缘计算.E-mail: 727149424@qq.com" ]
- 基金信息：
  
  国家自然科学基金面上项目(61772196);湖南省自然科学基金面上项目(2020JJ4249);湖南省社会科学基金重点项目(2016ZDB006);湖南省社会科学成果评审委员会课题重点项目(湘社评19ZD1005);湖南省研究生科研创新项目(CX20211108;CX20211102)
- DOI：10.12263/DZXB.20210198
  中图分类号： TP393;
- 收稿：2021-02-02，
  
  修回：2021-08-04，
  
  纸质出版：2022-10-25
- 稿件说明：
移动端阅览
蒋伟进,张婉清,陈萍萍等.基于IWOA群智感知中数量敏感的任务分配方法[J].电子学报,2022,50(10):2489-2502.

JIANG Wei-jin,ZHANG Wan-qing,CHEN Ping-ping,et al.Quantity Sensitive Task Allocation Method Based on IWOA in Group Intelligence Perception[J].ACTA ELECTRONICA SINICA,2022,50(10):2489-2502.
蒋伟进,张婉清,陈萍萍等.基于IWOA群智感知中数量敏感的任务分配方法[J].电子学报,2022,50(10):2489-2502. DOI： 10.12263/DZXB.20210198.

JIANG Wei-jin,ZHANG Wan-qing,CHEN Ping-ping,et al.Quantity Sensitive Task Allocation Method Based on IWOA in Group Intelligence Perception[J].ACTA ELECTRONICA SINICA,2022,50(10):2489-2502. DOI： 10.12263/DZXB.20210198.

摘要

随着移动终端的大规模普及，群智感知技术以其高效且成本低廉的优势逐渐取代现有的静态传感器，成为一种新兴的数据收集方式.如何在保证质量、降低成本的前提下，把感知任务分配给最佳执行用户以实现用户任务完成数量的最大化，是数量敏感任务分配问题研究的重点.基于此，提出一种结合非线性递减收敛因子、最优局部抖动以及动态位置更新三种操作的改进鲸鱼优化算法（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.

关键词

Keywords

references

李卓 , 徐哲 , 陈昕 , 等 . 面向移动群智感知的位置相关在线多任务分配算法 [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)

杜扬 , 黄河 , 孙玉娥 , 等 . 地理位置相关移动感知系统任务分配问题研究 [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)

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

EL-ASHMAWI W H , ALI A F . A modified salp swarm algorithm for task assignment problem [J]. Applied Soft Computing , 2020 , 94 : 106445 .

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 .

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 .

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 .

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 .

MIRJALILI S , LEWIS A . The whale optimization algorithm [J]. Advances in Engineering Software , 2016 , 95 : 51 - 67 .

杨正清 , 周朝荣 , 袁姝 . 移动群智感知系统中基于离散布谷鸟搜索算法的任务分配 [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)

姚远远 , 叶春明 . 求解作业车间调度问题的改进混合灰狼优化算法 [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)

范泽军 , 沈立炜 , 彭鑫 , 等 . 基于约束的空间众包多阶段任务分配 [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)

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 .

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 .

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 http://dx.doi.org/10.13140/RG.2.1.1290.2003 .

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 .

郭兴海 , 计明军 , 温都苏 , 等 . “最后一公里”配送的分布式多无人机的任务分配和路径规划 [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)

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 .

蔡雨岑 , 杜鹏桢 . 基于平衡鲸鱼优化算法的无人车路径规划 [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)

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 .

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 .

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 .

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 .

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 .

GHAREHCHOPOGH F S , GHOLIZADEH H . A comprehensive survey: Whale optimization algorithm and its applications [J]. Swarm and Evolutionary Computation , 2019 , 48 : 1 - 24 .

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 .

陈思光 , 陈佳民 , 赵传信 . 基于深度强化学习的云边协同计算迁移研究 [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)

李博扬 , 成雨蓉 , 王国仁 , 等 . 新型时空众包平台中的在线三维稳定匹配问题 [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)

王乐乐 , 眭泽智 , 蒲志强 , 等 . 一种改进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)

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

基于移动性预测的群智感知混合式任务分配

满足地理不可区分性的偏好感知多对多任务分配算法

OBS网络中基于优先级与参数可调的偏射路由算法