时空众包中多目标优化任务分配
Multi-Objective Task Assignment in Spatio-Temporal Crowdsourcing
摘要: 随着移动网络的快速发展以及配备各种内部传感器的移动设备的普及，时空众包已成为解决基于位置的传感任务的新兴范例。在现有研究中，时空众包系统主要最大化平台效用。为了最大化社会福利，本文提出了一种多目标优化任务分配(MOO-TA)模型，以最大化平台和众包工人的效用，激励众包工人执行偏远地区任务，扩大数据覆盖率。本文提出一种组合算法LWS_NSGA_II，结合传统的线性加权求和(LWS)算法和带精英策略的快速非支配排序遗传算法(NSGA_II)算法，以搜索针对多目标优化任务分配问题的所有可选择的帕累托最优解供平台选择。通过在真实数据集上进行比较实验，评估了该方法的有效性和可行性。
Abstract: 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.
文章引用：吴胜男. 时空众包中多目标优化任务分配[J]. 计算机科学与应用, 2021, 11(3): 549-560. https://doi.org/10.12677/CSA.2021.113056

参考文献

[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. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[5] Zhang, X., Yang, Z. and Liu, Y. (2018) Vehicle-Based Bi-Objective Crowdsourcing. IEEE Transactions on Intelligent Transportation Systems, 19, 3420-3428. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[10] Deb, K. (2005) Multi-Objective Optimization. In: Burke, E.K. and Kendall, G., Ed., Search Methodologies, Springer, Berlin, Heidelberg, 273-316. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[15] Liu, Y. and Li, X. (2015) Heterogeneous Participant Recruitment for Comprehensive Vehicle Sensing. PLoS ONE, 10, e0138898. [Google Scholar] [CrossRef] [PubMed]
[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. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[19] Yelp Dataset (n.d.).
https://www.yelp.com/dataset