南京大学学报(自然科学版) ›› 2023, Vol. 59 ›› Issue (4): 561–569.doi: 10.13232/j.cnki.jnju.2023.04.003

• • 上一篇    下一篇

移动群智感知中基于改进文化基因算法的长时多任务分配

张寿军1,2, 江海峰1,2(), 肖硕1,2, 王树豪1,2, 商景杰1,2   

  1. 1.中国矿业大学计算机科学与技术学院, 徐州, 221000
    2.矿山数字化教育部工程研究中心, 中国矿业大学, 徐州, 221000
  • 收稿日期:2023-06-13 出版日期:2023-07-31 发布日期:2023-08-18
  • 通讯作者: 江海峰 E-mail:jhfeng@cumt.edu.cn
  • 基金资助:
    国家自然科学基金(62071470);徐州市科技计划(KC20167)

Long⁃duration and multi⁃tasks assignment based on improved memetic algorithm in mobile crowd sensing

Shoujun Zhang1,2, Haifeng Jiang1,2(), Shuo Xiao1,2, Shuhao Wang1,2, Jingjie Shang1,2   

  1. 1.School of Computer Science and Technology, China University of Mining and Technology, Xuzhou, 221000, China
    2.Engineering Research Center of the Ministry of Mining Digital Education, China University of Mining and Technology, Xuzhou, 221000, China
  • Received:2023-06-13 Online:2023-07-31 Published:2023-08-18
  • Contact: Haifeng Jiang E-mail:jhfeng@cumt.edu.cn

RichHTML

2

PDF (PC)

219

摘要：

任务分配一直是移动群智感知的研究热点，对于任务的完成质量有重要影响，但目前针对多地点、长持续时间的任务分配研究较少.面向长时多任务分配问题，设计多轮次多时间段的任务分解策略，考虑任务权重、时间覆盖率、时间冗余度和冗余均衡度等因素，构建长时多任务质量评价模型.以预算为约束，以最大化任务覆盖质量为优化目标，提出基于改进文化基因算法的任务分配方法.该算法使用自适应遗传算法进行全局搜索，结合模拟退火算法进行局部搜索，并设计贪心修复算法对不合适的个体进行修复.仿真实验的结果表明，提出的算法同各基准算法相比，具有良好的性能.

关键词: 移动群智感知, 长时任务, 多任务分配, 质量评价, 文化基因算法

Abstract:

Task assignment has always been a research hotspot in mobile crowd sensing which has an important impact on the quality of task completion. Currently，there is relatively little research on task assignment for multi?location and long?duration tasks. This article aims to address the problem of long?duration and multimedia tasks assignment by designing a task decomposition strategy that includes multiple rounds and time periods，while considering factors such as task weight，time coverage rate，time redundancy，and redundancy balance. A long?duration and multimedia tasks quality evaluation model is also constructed. With budget constraints and the goal of maximizing task coverage quality，the article proposes a task assignment method based on an improved cultural genetic algorithm. The algorithm uses an adaptive genetic algorithm for global search，combines it with simulated annealing algorithm for local search，and includes a greedy repair algorithm to repair improper individuals. Simulation experiment results show that the proposed algorithm has good performance compared with various baseline algorithms.

Key words: mobile crowd sensing, long?duration tasks, multi?tasks assignment, quality evaluation, memetic algorithm

中图分类号: 

  • TP391

图1

任务?用户?时间段关系"

图2

(a)任务?用户关系；(b)用户?时间段关系；(c)任务?时间段关系"

图3

任务分配示意图"

图4

上海的热点区域图"

表1

主要参数范围"

主要参数范围
总预算 （元）200,1000
任务地点数2,6
任务时长 (h)3,7
时长阈值 (h)12
单位时间段时长 (h)0.5
热点区域任务权重2
非热点区域任务权重1
报名用户数50,250
用户单位时间段报价 (元)2,10
种群规模50
迭代阈值250

图5

500×3×4×100条件下的迭代次数?覆盖质量关系"

图6

Taxis (a)和T?Drive (b)数据集中各算法在不同任务规模时的覆盖质量"

图7

Taxis (a)和T?Drive (b)数据集中各算法在不同报名人数时的覆盖质量"

图8

Taxis (a)和T?Drive (b)数据集中各算法在不同预算时的覆盖质量"

图9

Taxis (a)和T?Drive (b)数据集中各算法在不同报名人数时的运行耗时"

1 刘云浩. 群智感知计算. 中国计算机学会通讯，2012，8(10)：38-41.
Liu Y H. Crowd sensing and computing. Communications of the CCF，2012，8(10)：38-41.
2 Capponi A， Fiandrino C， Kantarci B，et al. A survey on mobile crowdsensing systems：Challenges，solutions，and opportunities. IEEE Communications Surveys & Tutorials，2019，21(3)：2419-2465.
3 Kang X， Liu L， Ma H D. Enhance the quality of crowdsensing for fine?grained urban environment monitoring via data correlation. Sensors，2017，17(1)：88.
4 Ali A， Ayub N， Shiraz M，et al. Traffic efficiency models for urban traffic management using mobile crowd sensing：Aa survey. Sustainability，2021，13(23)：13068.
5 Tian B Q， Yuan Y B， Zhou H Y，et al. Pavement management utilizing mobile crowd sensing. Advances in Civil Engineering，2020(2020)：4192602.
6 Arcas?Tunez F， Terroso?Saenz F. Forest path condition monitoring based on crowd?based trajectory data analysis. Journal of Ambient Intelligence and Smart Environments，2021，13(1)：37-54.
7 Liu X， Cen J， Hu H Z，et al. A radio map self?updating algorithm based on mobile crowd sensing. Journal of Network and Computer Applications，2021(194)：103225.
8 An J， Wang Z X， He X，et al. Know where you are：A practical privacy?preserving semi?supervised indoor positioning via edge?crowdsensing. IEEE Transactions on Network and Service Management，2021，18(4)：4875-4887.
9 Wang J T， Wang L Y， Wang Y S，et al. Task allocation in mobile crowd sensing：State?of?the?art and future opportunities. IEEE Internet of Things Journal，2018，5(5)：3747-3757.
10 Ji J J， Guo Y N， Gong D W，et al. MOEA/D?based participant selection method for crowdsensing with social awareness. Applied Soft Computing，2020(87)：105981.
11 李卓，徐哲，陈昕，等. 面向移动群智感知的位置相关在线多任务分配算法. 计算机科学，2019，46(6)：102-106.
Li Z， Xu Z， Chen X，et al. Location?related online multi?task assignment algorithm for mobile crowd sensing. Computer Science，2019，46(6)：102-106.
12 Guo B， Liu Y， Wu W L，et al. Activecrowd：A framework for optimized multitask allocation in mobile crowdsensing systems. IEEE Transactions on Human?Machine Systems，2017，47(3)：392-403.
13 Lai C， Zhang X L. Duration?sensitive task allocation for mobile crowd sensing. IEEE Systems Journal，2020. 14(3)：4430-4441.
14 Wang Y N， Sun G D， Ding X J. Coverage?balancing user selection in mobile crowd sensing with budget constraint. Sensors，2019，19(10)：2371.
15 Mondal S， Mitra S， Mukherjee A，et al. Participant selection algorithms for large?scale mobile crowd sensing environment. Microsystem Technologies，2022，28(12)：2641-2657.
16 Yang G S， Wang B Y， He X Y，et al. Competition?congestion?aware stable worker?task matching in mobile crowd sensing. IEEE Transactions on Network and Service Management，2021，18(3)：3719-3732.
17 周杰，於志勇，郭文忠，等.“ t?时隙k?覆盖”群智感知任务的参与者选择方法. 计算机科学，2018，45(2)：157-164，196.
Zhou J， Yu Z Y， Guo W Z，et al. Participant selection algorithm for t?sweep k?coverage crowd sensing tasks. Computer Science，2018，45(2)：157-164，196.
18 Jiang W J， Chen J P， Liu X L，et al. Participant recruitment method aiming at service quality in mobile crowd sensing. Wireless Communications and Mobile Computing，2021(2021)：6621659.
19 Ji J J， Guo Y N， Gong D W，et al. Evolutionary multi?task allocation for mobile crowdsensing with limited resource. Swarm and Evolutionary Computation，2021(63)：100872.
20 李晓东，於志勇，黄昉菀,等. 面向河道环境监测的群智感知参与者选择策略. 计算机科学，2022，49(5)：371-379.
Li X D， Yu Z Y， Huang F W，et al. Participant selection strategies based on crowd sensing for river environmental monitoring. Computer Science，2022，49(5)：371-379.
21 Estrada R， Valeriano L， Torres D. Multi?task versus consecutive task allocation with tasks clustering for Mobile Crowd Sensing Systems. Procedia Computer Science，2022，19(8)：67-76.
22 Huang Y， Chen H L， Ma G Q，et al. OPAT：Optimized allocation of time?dependent tasks for mobile crowdsensing. IEEE Transactions on Industrial Informatics，2022，18(4)：2476-2485.
23 Li X， Zhang X L. Multi?task allocation under time constraints in mobile crowdsensing. IEEE Transactions on Mobile Computing，2021，20(4)：1494-1510.
24 Yuan J， Zheng Y， Xie X，et al. Driving with knowledge from the physical world∥Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Diego，CA，USA：ACM，2011：316-324.
[1] 王旻,林志斌,卢晶. 适用于虚拟低音音质的客观评价方法研究[J]. 南京大学学报(自然科学版), 2019, 55(5): 796-803.
[2] 周 啸1，史瑞芝1*，李少梅1，巩现勇1, 2，管凌霄1. 高阶网点集聚型重心定位频率调制半色调算法[J]. 南京大学学报(自然科学版), 2015, 51(4): 866-879.
[3]  陈惠娟*，钱亚枫，李 勃，陈启美.  基于HVS和四元数的彩色图像质量评价方法 

[J]. 南京大学学报(自然科学版), 2015, 51(2): 271-278.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!

版权所有 © 2021 《南京大学学报(自然科学)》

地址：江苏省南京市鼓楼区汉口路22号，南京大学学报编辑部，210093

电话：025-83592704 , 传真：025-83592704        技术支持：北京玛格泰克科技发展有限公司