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

doi:10.11772/j.issn.1001-9081.2019020365

Journal of Computer Applications ›› 2019, Vol. 39 ›› Issue (9): 2778-2783.DOI: 10.11772/j.issn.1001-9081.2019020365

• Frontier & interdisciplinary applications • Previous Articles Next Articles

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).

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

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

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

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

Abstract

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)

摘要：

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

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

CLC Number:

TP393.01

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.

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

References

[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

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	Peiyao ZHANG, Xiaodong FU. Incentive mechanism of crowdsourcing multi-task assignment against malicious bidding [J]. Journal of Computer Applications, 2024, 44(1): 261-268.
[2]	Yanan SUN, Jiehong WU, Junling SHI, Lijun GAO. Multi-UAV collaborative task assignment method based on improved self-organizing map [J]. Journal of Computer Applications, 2023, 43(5): 1551-1556.
[3]	LI Zhuo, SONG Zihui, SHEN Xin, CHEN Xin. Local differential privacy protection mechanism for mobile crowd sensing with edge computing [J]. Journal of Computer Applications, 2021, 41(9): 2678-2686.
[4]	MA Hua, CHEN Yuepeng, TANG Wensheng, LOU Xiaoping, HUANG Zhuoxuan. Survey of research progress on crowdsourcing task assignment for evaluation of workers’ ability [J]. Journal of Computer Applications, 2021, 41(8): 2232-2241.
[5]	Junying HAN, Zhenyu ZHANG, Deshi KONG. Distributed multi-task allocation method for user area in mobile crowd sensing [J]. Journal of Computer Applications, 2020, 40(2): 358-362.
[6]	JIN Xin, WAN Taochun, LYU Chengmei, WANG Chengtian, CHEN Fulong, ZHAO Chuanxin. Privacy preservation algorithm of original data in mobile crowd sensing [J]. Journal of Computer Applications, 2020, 40(11): 3249-3254.
[7]	QIN Haiyan, ZHANG Yonglong, LI Bin. Truthful mechanism for crowdsourcing task assignment in social network [J]. Journal of Computer Applications, 2020, 40(10): 3019-3024.
[8]	ZHANG Xingsheng, YU Dunhui, ZHANG Wanshan, WANG Chenxu. Time utility balanced online task assignment algorithm under spatial crowdsourcing environment [J]. Journal of Computer Applications, 2019, 39(5): 1357-1363.
[9]	CHEN Youling, ZUO Lidan, NIU Yufei, WANG Long. Task assignment method of product development based on knowledge similarity [J]. Journal of Computer Applications, 2019, 39(2): 323-329.
[10]	DU Xueling, MENG Xuelei, YANG Bei, TANG Lin. Emergency resource assignment for requirements of multiple disaster sites in view of fairness [J]. Journal of Computer Applications, 2018, 38(7): 2089-2094.
[11]	LIU Hui, LI Sheng'en. Adaptive threshold algorithm based on statistical prediction under spatial crowdsourcing environment [J]. Journal of Computer Applications, 2018, 38(2): 415-420.
[12]	YU Dunhui, WANG Yi, ZHANG Wanshan. Ability dynamic measurement algorithm for software crowdsourcing workers [J]. Journal of Computer Applications, 2018, 38(12): 3612-3617.
[13]	MAO Yingchi, MU Chao, BAO Wei, LI Xiaofang. Multi-type task assignment and scheduling oriented to spatial crowdsourcing [J]. Journal of Computer Applications, 2018, 38(1): 6-12.
[14]	WANG Guan, WANG Yuxin, CHEN Xin, WANG Fei, GUO He. Heterogeneous scheduling algorithm with immediate successor finish time [J]. Journal of Computer Applications, 2017, 37(1): 12-17.
[15]	XU Zhe, LI Zhuo, CHEN Xin. Multi-task assignment algorithm for mobile crowdsensing [J]. Journal of Computer Applications, 2017, 37(1): 18-23.