时空众包中多目标优化任务分配
Multi-Objective Task Assignment in Spatio-Temporal Crowdsourcing

DOI: 10.12677/CSA.2021.113056, PP. 549-560

Keywords: 时空众包，任务分配，多目标优化，帕累托最优解
Spatio-Temporal Crowdsourcing, Task Assignment, Multi-Objective Optimization, Pareto Optimal Solutions

Full-Text   Cite this paper   Add to My Lib

Abstract:

随着移动网络的快速发展以及配备各种内部传感器的移动设备的普及，时空众包已成为解决基于位置的传感任务的新兴范例。在现有研究中，时空众包系统主要最大化平台效用。为了最大化社会福利，本文提出了一种多目标优化任务分配(MOO-TA)模型，以最大化平台和众包工人的效用，激励众包工人执行偏远地区任务，扩大数据覆盖率。本文提出一种组合算法LWS_NSGA_II，结合传统的线性加权求和(LWS)算法和带精英策略的快速非支配排序遗传算法(NSGA_II)算法，以搜索针对多目标优化任务分配问题的所有可选择的帕累托最优解供平台选择。通过在真实数据集上进行比较实验，评估了该方法的有效性和可行性。
With the rapid development of mobile networks and the popularity of mobile devices equipped with various internal sensors, spatio-temporal crowdsourcing has become an emerging paradigm for solving location-based sensing tasks. In the existing research, the spatio-temporal crowdsourcing system mainly maximizes the utility of the platform. In order to maximize social welfare, this paper proposes the Multi-Objective Optimization Task Assignment (MOO-TA) model to maximize the utility of the platform and crowds workers. It encourages crowds workers to perform crowds tasks in remote areas, and expands data coverage. In this paper, the combination algorithm LWS_NSGA_II is proposed, which combines the traditional linear weighted Summation (LWS) algorithm and the Fast Non-dominated Sorting Genetic Algorithm (NSGA_II) algorithm to search for all selectable Pareto optimal solutions for multi-objective optimization task assignment problems for system selection. Through comparison experiments on real data sets, the effectiveness and feasibility of the proposed method are evaluated.

References

[1]	Wen, Y., Shi, J., Zhang, Q., Tian, X., Huang, Z., Yu, H., Cheng, Y. and Shen, X. (2015) Quality-Driven Auction-Based Incentive Mechanism for Mobile Crowd Sensing. IEEE Transactions on Vehicular Technology, 64, 4203-4214. https://doi.org/10.1109/TVT.2014.2363842
[2]	Tong, Y., Yuan, Y., Cheng, Y., Chen, L. and Wang, G. (2017) Survey on Spatiotemporal Crowdsourced Data Management Techniques. Journal of Software, 28, 35-58.
[3]	Zhang, X., Yang, Z., Gong, Y.J., Liu, Y. and Tang, S. (2017) Spatial Recruiter: Maximizing Sensing Coverage in Selecting Workers for Spatial Crowdsourcing. IEEE Transactions on Vehicular Technology, 66, 5229-5240. https://doi.org/10.1109/TVT.2016.2614312
[4]	Wang, L., Yu, Z., Han, Q., Guo, B. and Xiong, H. (2017) Mul-ti-Objective Optimization based Allocation of Heterogeneous Spatial Crowdsourcing Tasks. IEEE Transactions on Mobile Computing, 17, 1637-1650. https://doi.org/10.1109/TMC.2017.2771259
[5]	Zhang, X., Yang, Z. and Liu, Y. (2018) Vehicle-Based Bi-Objective Crowdsourcing. IEEE Transactions on Intelligent Transportation Systems, 19, 3420-3428. https://doi.org/10.1109/TITS.2017.2766769
[6]	Zhang, X., Yang, Z., Liu, Y. and Tang, S. (2016) On Reliable Task Assignment for Spatial Crowdsourcing. IEEE Transactions on Emerging Topics in Computing, 7, 174-186. https://doi.org/10.1109/TETC.2016.2614383
[7]	Liang, W., Yu, Z., Qi, H., Guo, B. and Xiong, H. (2018) Mul-ti-Objective Optimization Based Allocation of Heterogeneous Spatial Crowdsourcing Tasks. IEEE Transactions on Mobile Computing, 17, 1637-1650.
[8]	Wang, Y., Jia, X., Jin, Q. and Ma, J. (2016) QuaCentive: A Quality-Aware Incentive Mechanism in Mobile Crowdsourced Sensing (MCS). The Journal of Supercomputing, 72, 2924-2941. https://doi.org/10.1007/s11227-015-1395-y
[9]	Duan, X., Zhao, C., He, S., Cheng, P. and Zhang, J. (2017) Dis-tributed Algorithms to Compute Walrasian Equilibrium in Mobile Crowdsensing. IEEE Transactions on Industrial Elec-tronics, 64, 4048-4057. https://doi.org/10.1109/TIE.2016.2645138
[10]	Deb, K. (2005) Multi-Objective Optimization. In: Burke, E.K. and Kendall, G., Ed., Search Methodologies, Springer, Berlin, Heidelberg, 273-316. https://doi.org/10.1007/0-387-28356-0_10
[11]	Ul Hassan, U. and Curry, E. (2016) Efficient Task Assignment for Spatial Crowdsourcing: A Combinatorial Fractional Optimization Approach with Semi-Bandit Learning. Expert Systems with Applications, 58, 36-56. https://doi.org/10.1016/j.eswa.2016.03.022
[12]	Wang, J., Wang, Y., Zhang, D., Wang, L., Xiong, H., Helal, A., et al. (2016) Fine-Grained Multi-Task Allocation for Participatory Sensing with a Shared Budget. IEEE Internet of Things Journal, 3, 1395-1405. https://doi.org/10.1109/JIOT.2016.2608141
[13]	Ben Messaoud, R. and Ghamri-Doudane, Y. (2016) Fair QoI and Energy-Aware Task Allocation in Participatory Sensing. 2016 IEEE Wireless Communications and Networking Conference, Doha, 3-6 April 2016, 1-6. https://doi.org/10.1109/WCNC.2016.7565025
[14]	Liu, Y., Guo, B., Wang, Y., Wu, W., Yu, Z. and Zhang, D. (2016) Taskme: Multi-Task Allocation in Mobile Crowd Sensing. Proceedings of the 2016 ACM International Joint Conference on Pervasive and Ubiquitous Computing, Heidelberg, September 2016, 403-414. https://doi.org/10.1145/2971648.2971709
[15]	Liu, Y. and Li, X. (2015) Heterogeneous Participant Recruitment for Comprehensive Vehicle Sensing. PLoS ONE, 10, e0138898. https://doi.org/10.1371/journal.pone.0138898
[16]	Ma, X., Ma, J., Li, H., Jiang, Q. and Gao, S. (2016) RTRC: A Reputation-Based Incentive Game Model for Trustworthy Crowdsourcing Service. China Communications, 13, 199-215. https://doi.org/10.1109/CC.2016.7897544
[17]	Wang, Y., Li, L. and Liu, G. (2015) Social Context-Aware Trust Inference for Trust Enhancement in Social Network Based Recommendations on Service Providers. World Wide Web, 18, 159-184. https://doi.org/10.1007/s11280-013-0241-5
[18]	Peng, L., Yu, X.Y., Yang, L. and Zhang, T. (2014) Crowdsourcing Fraud Detection Algorithm Based on Ebbinghaus Forgetting Curve. International Journal of Security and Its Applications, 8, 283-290. https://doi.org/10.14257/ijsia.2014.8.1.26
[19]	Yelp Dataset (n.d.). https://www.yelp.com/dataset

Full-Text