﻿ 时空众包中多目标优化任务分配

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

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.

1. 引言

Figure 1. The workflow of a spatio-temporal crowdsourcing platform

—提出了LWS_NSGA_II算法来解决多目标优化问题，以最大化平台的效用和众包工人的效用。

—根据任务难度值，通过激励策略鼓励众包工人执行位于不受欢迎地区的众包任务，以改善感测数据的覆盖范围。

—真实数据的实验表明，该算法在多目标优化问题上实现社会福利最大化是有效可行的。

2. 相关工作

3. 问题定义

Table 1. Frequently used notations

3.1. 众包工人

$f\left(x\right)=\omega \cdot {\text{e}}^{\alpha \cdot {\text{e}}^{\gamma \cdot x}}$ (1)

1) 信任度：在公式(1)中，x是Gompertz函数的变量。本文通过将x替换为 ${x}_{i}$ 获得 $t{r}_{i}$${x}_{i}$ 由式(2)计算。

$t{r}_{i}\left({x}_{i}\right)=\omega \cdot {\text{e}}^{\alpha \cdot {\text{e}}^{\gamma \cdot {x}_{i}}}$ (2)

${x}_{i}=\frac{pr{o}_{i}+RI{F}_{i}+\underset{j=1}{\overset{nu{m}_{i}}{\sum }}{}_{{q}_{j}^{i}\in {Q}_{i}}{q}_{j}^{i}\cdot {\delta }_{j}}{1+\underset{j=1}{\overset{nu{m}_{i}}{\sum }}{\delta }_{j}}$ (3)

${\delta }_{j}=\left\{\begin{array}{ll}1,\hfill & \text{\hspace{0.17em}}\text{\hspace{0.17em}}j=nu{m}_{i}\hfill \\ {\text{e}}^{-\frac{1}{j}},\hfill & 1\le j (4)

2) 能力值：我们获得 $a{b}_{i}$ 通过将等式(1)中的x替换为 ${y}_{i}$${y}_{i}$ 由式(5)计算。

$a{b}_{i}\left({y}_{i}\right)=\omega \cdot {\text{e}}^{\alpha \cdot {\text{e}}^{\gamma \cdot {y}_{i}}}$ (5)

${y}_{i}$ 是等式(5)的输入，并且 $a{b}_{i}$ 随着 ${y}_{i}$ 增长而增长。 ${y}_{i}$ 可以通过公式(6)计算。

${y}_{i}=\frac{po{s}_{ij}+\underset{j=1}{\overset{nu{m}_{i}}{\sum }}{}_{{q}_{j}^{i}\in {Q}_{i}}{q}_{j}^{i}\cdot {\delta }_{j}}{1+\underset{j=1}{\overset{nu{m}_{i}}{\sum }}{\delta }_{j}}$ (6)

3) 众包工人的得分：本文根据众包工人的信任度 $t{r}_{i}$ 和能力值 $a{b}_{i}$ 来计算。得分 $sc{o}_{i}$ 代表 ${w}_{i}$ 的综合得分。它由公式(7)计算。

$sc{o}_{i}={\epsilon }_{1}\cdot t{r}_{i}+{\epsilon }_{2}\cdot a{b}_{i}$ (7)

3.2. 众包任务

$di{f}_{ij}={\omega }_{1}\cdot d{t}_{ij}+{\omega }_{2}\cdot se{v}_{j}$ (8)

4. 激励机制

4.1. 系统模型

${u}_{ij}={p}_{ij}-{c}_{ij}+\rho \cdot Ro{P}_{ij}$ (9)

$Ro{P}_{ij}$${w}_{i}$ 执行 ${t}_{j}$ 时的额外奖励或惩罚。参数 $\rho$ 表示系统参数，并且在我们的模型中

$\left\{\begin{array}{cc}0<\rho <\frac{{v}_{ij}-{p}_{ij}}{Ro{P}_{ij}},& Ro{P}_{ij}>0\\ 0<\rho <\frac{{c}_{ij}-{p}_{ij}}{Ro{P}_{ij}},& Ro{P}_{ij}<0\end{array}$

${p}_{ij}$ 由公式(10)计算。

${p}_{ij}=\theta \cdot {\text{e}}^{\frac{-1}{{q}_{ij}}}\cdot {B}_{j}$ (10)

$\theta$ 是系统参数，其中 $\frac{{c}_{ij}}{{B}_{j}}\cdot {\text{e}}^{\frac{1}{{q}_{ij}}}<\theta \le {\text{e}}^{\frac{1}{{q}_{ij}}}$

${w}_{i}$ 执行 ${t}_{j}\left({t}_{j}\in {\phi }_{i}\right)$ 的成本由公式(11)给出。

${c}_{ij}={c}_{ij}^{m}+{c}_{ij}^{s}$ (11)

$Ro{P}_{ij}=Su{b}_{ij}^{sco}+Su{b}_{ij}^{pr}+Su{b}_{ij}^{dif}-Fin{e}_{ij}^{pt}$ (12)

$Su{b}_{ij}^{sco}=\sigma \cdot {\text{e}}^{\frac{-1}{sc{o}_{i}}}\cdot {p}_{ij}$ (13)

$Su{b}_{ij}^{pr}$ 是根据公式(14)表示的隐私敏感度值计算出的额外奖励。

$Su{b}_{ij}^{pr}=\left\{\begin{array}{ll}\beta \cdot {\text{e}}^{\frac{-1}{|p{r}_{i}-p{r}_{\mathrm{min}}|}}\cdot {p}_{ij},\hfill & p{r}_{\mathrm{min}} (14)

$Su{b}_{ij}^{dif}=\eta \cdot {\text{e}}^{\frac{-1}{di{f}_{ij}}}\cdot {c}_{ij}$ (15)

$Fin{e}_{ij}^{pt}=\left\{\begin{array}{ll}0,\hfill & p{t}_{ij}^{\mathrm{min}}\le p{t}_{ij}\le p{t}_{ij}^{\mathrm{max}}\hfill \\ \lambda \cdot {\text{e}}^{\frac{-1}{|p{t}_{ij}-p{t}_{ij}^{\mathrm{min}}|}}\cdot {p}_{ij},\hfill & \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}p{t}_{ij}p{t}_{ij}^{\mathrm{max}}\hfill \end{array}$ (16)

$\stackrel{¯}{{u}_{ij}}$${w}_{i}\left({w}_{i}\in S\right)$ 执行 ${t}_{j}$ 时带给平台的实际效用，由公式(17)计算。

$\stackrel{¯}{{u}_{ij}}={v}_{ij}-{p}_{ij}-\rho \cdot Ro{P}_{ij}$ (17)

${v}_{ij}$ 表示 ${w}_{i}\left({w}_{i}\in S\right)$ 通过感测 ${t}_{j}$ 为平台带来的贡献。 $\rho$ 参数表示系统参数 $\left\{\begin{array}{cc}0<\rho <\frac{{v}_{ij}-{p}_{ij}}{Ro{P}_{ij}},& Ro{P}_{ij}>0\\ 0<\rho <\frac{{c}_{ij}-{p}_{ij}}{Ro{P}_{ij}},& Ro{P}_{ij}<0\end{array}$

4.2. 多目标优化任务分配

$U=\underset{{w}_{i}\in S}{\sum }\underset{{t}_{j}\in T}{\sum }{u}_{ij}$ (18)

$\stackrel{¯}{U}=\underset{{w}_{i}\in S}{\sum }\underset{{t}_{j}\in T}{\sum }\stackrel{¯}{{u}_{ij}}$ (19)

LWS_NSGA_II算法用于解决多目标优化任务分配(MOO-TA)问题。它是传统的线性加权求和(LWS)算法和带精英策略的快速非支配排序遗传算法(NSGA_II)算法的组合算法。LWS算法的输出用作NSGA_II算法的输入，以便找到尽可能多的帕累托最优解。

4.2.1. 线性加权求和(LWS)算法

$UF=\mu \cdot U+\left(1-\mu \right)\cdot \stackrel{¯}{U}$, (20)

$\mu$ 权重因子的作用是平衡这两个目标，U以及 $\stackrel{¯}{U}$

Table 2. The traditional linear weighted Summation (LWS) algorithm

4.2.2. LWS_NSGA_II算法

LWS算法直接将输出解决方案作为NSGA_II的初始种群的一部分，即为算法3：LWS_NSGA_II算法。通过LWS算法获得的解并不是全部的Pareto最优解，因为在每次迭代中，基于贪婪的线性加权求和算法可以实现接近最优的解，而不是最优解。此外，线性权重策略不能保证找到针对多目标优化问题的Pareto解，尤其是对于非凸解空间。相反，NSGA_II算法是一种启发式方法，可以实现尽可能多的帕累托最优解。通过LWS算法直接获得输出解决方案，作为NSGA_II算法初始种群的一部分。因此，它被称为LWS_NSGA_II算法。它可以有效地加速融合并获得满意的解决方案(表3)。

Table 3. LWS_NSGA_II algorithm

5. 实验评估

5.1. 实验装置

5.2. MOO-TA的性能

Figure 2. Effect of different constant parameter ρ

Figure 3. The result of LWS_NSGA_II

Figure 4. The allocation solution results of different algorithms

6. 总结

[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

Top