移动群智感知系统中基于离散布谷鸟搜索算法的任务分配

doi:10.11772/j.issn.1001-9081.2019020365

计算机应用 ›› 2019, Vol. 39 ›› Issue (9): 2778-2783.DOI: 10.11772/j.issn.1001-9081.2019020365

• 应用前沿、交叉与综合 • 上一篇下一篇

移动群智感知系统中基于离散布谷鸟搜索算法的任务分配

杨正清¹, 周朝荣^1,2, 袁姝¹

1. 四川师范大学物理与电子工程学院, 成都 610101;
2. 气象信息与信号处理四川省高校重点实验室(成都信息工程大学), 成都 610225

收稿日期:2019-03-06 修回日期:2019-05-20 发布日期:2019-05-28 出版日期:2019-09-10
通讯作者: 周朝荣
作者简介:杨正清(1994-),女,四川自贡人,硕士研究生,CCF会员,主要研究方向:移动群智感知;周朝荣(1975-),男,四川安岳人,副教授,博士,CCF会员,主要研究方向:无线网络;袁姝(1995-),女,四川南充人,硕士研究生,CCF会员,主要研究方向:空间众包。
基金资助:
气象信息与信号处理四川省高校重点实验室开放课题资助项目（QXXCSYS201704）；四川省教育厅重点项目（15CZ0004）。

Task assignment based on discrete cuckoo search algorithm in mobile crowd sensing system

YANG Zhengqing1, ZHOU Zhaorong1,2, YUAN Shu1

1. School of Physics and Electronic Engineering, Sichuan Normal University, Chengdu Sichuan 610101, China;
2. Meteorological Information and Signal Processing Key Laboratory of Sichuan Higher Education Institutes(Chengdu University of Information Technology), Chengdu Sichuan 610225, China

Received:2019-03-06 Revised:2019-05-20 Online:2019-05-28 Published:2019-09-10
Supported by:
This work is partially supported by the Open Program of Meteorological Information and Signal Processing Key Laboratory of Sichuan Higher Education Institutes (QXXCSYS201704), the Key Project of Sichuan Provincial Education Department (15CZ0004).

摘要/Abstract

摘要：

针对移动群智感知系统中工人积极性低以及任务过期的问题，提出了基于初始成本和软时间窗的任务分配算法。对应的任务分配问题为NP-hard问题，不存在计算有效的最优算法，因此，基于离散布谷鸟搜索算法（DCSA）进行求解。首先，根据问题特征，分别设计了对应的全局搜索过程以及局部搜索过程。其次，根据任务与工人起始位置的距离以及时间窗大小，分析其优先级以便得到更好的解。最后，执行可行化操作，使各次任务分配均满足相关约束。仿真结果表明，与遗传算法和贪婪算法相比，基于DCSA的任务分配算法能够提升工人的参与积极性，解决任务过期的问题，并最终降低系统的总成本。

关键词: 移动群智感知, 任务分配, 初始成本, 软时间窗, 任务优先级, 离散布谷鸟搜索算法

Abstract:

Considering the problems of low-enthusiasm workers and task expiration in the mobile crowd sensing system, a task assignment algorithm based on initial cost and soft time window was proposed. As the corresponding task assignment problem belongs to the category of NP-hard problems and the computationally efficient optimal algorithm cannot be found, thus, an algorithm was developed based on Discrete Cuckoo Search Algorithm (DCSA). Firstly, the corresponding global search process and local search process were designed respectively according to the problem characteristics. Secondly, to derive the better solution, the priorities of tasks with respect to the distance between tasks and workers' starting positions as well as the size of time windows were analyzed. Finally, feasible operations were executed to guarantee that the related constraints were satisfied by each task assignment. Compared with genetic algorithm and greedy algorithm, the simulation results show that DCSA-based task assignment algorithm can improve the enthusiasm of workers to participate, solve the problem of task expiration, and ultimately reduce the total system cost.

Key words: mobile crowd sensing, task assignment, initial cost, soft time window, task priority, Discrete Cuckoo Search Algorithm (DCSA)

中图分类号:

TP393.01

杨正清, 周朝荣, 袁姝. 移动群智感知系统中基于离散布谷鸟搜索算法的任务分配[J]. 计算机应用, 2019, 39(9): 2778-2783.

YANG Zhengqing, ZHOU Zhaorong, YUAN Shu. Task assignment based on discrete cuckoo search algorithm in mobile crowd sensing system[J]. Journal of Computer Applications, 2019, 39(9): 2778-2783.

参考文献

[1] GONG W, ZHANG B, LI C. Task assignment in mobile crowdsensing:present and future directions[J]. IEEE Network, 2018, 32(4):100-107.
[2] MANOLOPOULOS V, TAO S, RODRIGUEZ S, et al. MobiTraS:a mobile application for a smart traffic system[C]//Proceedings of the 2010 8th IEEE International NEWCAS Conference. Piscataway, NJ:IEEE, 2010:365-368.
[3] MAISONNEUVE N, STEVENS M, NIESSEN M E, et al. NoiseTube:measuring and mapping noise pollution with mobile phones[M]//ATHANASIADIS I N, RIZZOLI A E, MITKAS P A, et al. Information Technologies in Environmental Engineering. Berlin:Springer, 2009:215-228.
[4] DUTTA P, AOKI P M, KUMAR N, et al. Common sense:participatory urban sensing using a network of handheld air quality monitors[C]//Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems. New York:ACM, 2009:349-350.
[5] CHENG P, LIAN X, CHEN L, et al. Prediction-based task assignment in spatial cowdsourcing[C]//ICDE 2017:Proceedings of the 2017 IEEE 33rd International Conference on Data Engineering. Washington, DC:IEEE Computer Society, 2017:997-1008.
[6] WANG L, YANG D, HAN X, et al. Location privacy-preserving task allocation for mobile crowdsensing with differential geo-obfuscation[C]//Proceedings of the 26th International Conference on World Wide Web. Perth:International World Wide Web Conferences Steering Committee, 2017:627-636.
[7] HU T, XIAO M, HU C, et al. A QoS-sensitive task assignment algorithm for mobile crowdsensing[J]. Pervasive and Mobile Computing, 2017, 41:333-342.
[8] LUAN T, TO H, FAN L, et al. A real-time framework for task assignment in hyperlocal spatial crowdsourcing[J]. ACM Transactions on Intelligent Systems and Technology, 2017, 9(3):1-25.
[9] CHENG P, LIAN X, CHEN L, et al. Task assignment on multi-skill oriented spatial crowdsourcing[J]. IEEE Transactions on Knowledge and Data Engineering, 2016, 28(8):2201-2215.
[10] MRS D S B, MRV S K, THANEERU L, et al. A survey on mobile crowd sensing using MCS task allocation[J]. International Journal of Research, 2017, 4(5):600-607.
[11] XIONG H, ZHANG D, CHEN G, et al. CrowdTasker:maximizing coverage quality in piggyback crowdsensing under budget constraint[C]//Proceedings of the 2015 IEEE International Conference on Pervasive Computing and Communications. Piscataway, NJ:IEEE, 2015:55-62.
[12] CHEUNG M H, SOUTHWELL R, HOU F, et al. Distributed time-sensitive task selection in mobile crowdsensing[EB/OL].[2019-01-07]. https://arxiv.org/pdf/1503.06007v1.pdf.
[13] 李洋,贾梦迪,杨文彦,等.基于树分解的空间众包最优任务分配算法[J].软件学报,2018,29(3):824-838.(LI Y, JIA M D, YANG W Y, et al. Optimal task assignment algorithm based on tree-decouple in spatial crowdsourcing[J]. Journal of Software, 2018, 29(3):824-838.)
[14] WU S, GAO X, WU F, et al. A constant-factor approximation for bounded task allocation problem in crowdsourcing[C]//GLOBECOM 2017:Proceedings of the 2017 IEEE Global Communications Conference. Piscataway, NJ:IEEE, 2017:1-6.
[15] YANG X-S, DEB S. Cuckoo search via Lévy flights[C]//NaBIC 2019:Proceedings of the 2009 World Congress on Nature and Biologically Inspired Computing. Piscataway, NJ:IEEE, 2009:210-214.
[16] JATI G K, MANURUNG H M, SUYANTO. Discrete cuckoo search for traveling salesman problem[C]//ICCCT 2012:Proceedings of the 2012 7th International Conference on Computing and Convergence Technology. Piscataway, NJ:IEEE, 2012:993-997.
[17] ZHENG H, ZHOU Y, LUO Q. A hybrid cuckoo search algorithm-GRASP for vehicle routing problem[J]. Journal of Convergence Information Technology, 2013, 8(3):821-828.
[18] 张丽萍,柴跃廷,曹瑞.有时间窗车辆路径问题的改进遗传算法[J].计算机集成制造系统,2002,8(6):451-454.(ZHANG L P, CHAI Y T, CAO R. Improved genetic algorithm for vehicle routing problem with time windows[J]. Computer Integrated Manufacturing Systems, 2002, 8(6):451-454.)

移动群智感知系统中基于离散布谷鸟搜索算法的任务分配

Task assignment based on discrete cuckoo search algorithm in mobile crowd sensing system

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	李卓, 宋子晖, 沈鑫, 陈昕. 边缘计算支持下的移动群智感知本地差分隐私保护机制[J]. 计算机应用, 2021, 41(9): 2678-2686.
[2]	马华, 陈跃鹏, 唐文胜, 娄小平, 黄卓轩. 面向工作者能力评估的众包任务分配方法的研究进展综述[J]. 计算机应用, 2021, 41(8): 2232-2241.
[3]	冉家敏, 倪志伟, 彭鹏, 朱旭辉. 考虑空间众包工作者服务质量的任务分配策略及其萤火虫群优化算法求解[J]. 计算机应用, 2021, 41(3): 794-802.
[4]	杨玮, 李然, 张堃. 基于变邻域模拟退火算法的多自动导引车任务分配优化[J]. 计算机应用, 2021, 41(10): 3056-3062.
[5]	余敦辉, 袁旭, 张万山, 王晨旭. 基于动态阈值的时空众包在线分配算法[J]. 计算机应用, 2020, 40(3): 658-664.
[6]	韩俊樱, 张振宇, 孔德仕. 移动群智感知中面向用户区域的分布式多任务分配方法[J]. 计算机应用, 2020, 40(2): 358-362.
[7]	金鑫, 王涛春, 吕成梅, 王成田, 陈付龙, 赵传信. 移动群智感知中原始数据隐私保护算法[J]. 计算机应用, 2020, 40(11): 3249-3254.
[8]	秦海燕, 章永龙, 李斌. 社会网络下分配众包任务的真实机制[J]. 计算机应用, 2020, 40(10): 3019-3024.
[9]	陈秀华, 刘慧, 熊金波, 马蓉. 移动群智感知中面向任务需求的用户选择激励机制[J]. 计算机应用, 2019, 39(8): 2310-2317.
[10]	张兴盛, 余敦辉, 张万山, 王晨旭. 时空众包环境下时效均衡的在线任务分配算法[J]. 计算机应用, 2019, 39(5): 1357-1363.
[11]	陈友玲, 左丽丹, 牛禹霏, 王龙. 基于知识相似度的产品开发任务分配方法[J]. 计算机应用, 2019, 39(2): 323-329.
[12]	李鑫滨, 章寿涛, 闫磊, 韩松. 基于鲁棒Restless Bandits模型的多水下自主航行器任务分配策略[J]. 计算机应用, 2019, 39(10): 2795-2801.
[13]	刘鹏飞, 毛莺池, 王龙宝. 基于云雾协作模型的任务分配方法[J]. 计算机应用, 2019, 39(1): 8-14.
[14]	宋子晖, 李卓, 陈昕. 基于压缩感知的移动群智感知任务分发机制[J]. 计算机应用, 2019, 39(1): 15-21.
[15]	赵焜松, 余敦辉, 张万山. 软件众包任务发布优先级计算方法[J]. 计算机应用, 2018, 38(7): 2032-2036.