基于用戶可靠性的眾包系統(tǒng)任務(wù)分配機(jī)制

施 戰(zhàn)，辛 煜，孫玉娥，黃 河,4

(1.蘇州大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 蘇州 215006； 2.北京遙感信息研究所，北京 100011；3.蘇州大學(xué) 城市軌道交通學(xué)院，江蘇 蘇州 215137； 4. 中國科學(xué)技術(shù)大學(xué) 蘇州研究院, 江蘇 蘇州 215123)(*通信作者電子郵箱sunye12@suda.edu.cn)

基于用戶可靠性的眾包系統(tǒng)任務(wù)分配機(jī)制

施 戰(zhàn)1，辛 煜2，孫玉娥3,4*，黃 河1,4

(1.蘇州大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 蘇州 215006； 2.北京遙感信息研究所，北京 100011；3.蘇州大學(xué) 城市軌道交通學(xué)院，江蘇 蘇州 215137； 4. 中國科學(xué)技術(shù)大學(xué) 蘇州研究院, 江蘇 蘇州 215123)(*通信作者電子郵箱sunye12@suda.edu.cn)

針對現(xiàn)有研究對眾包系統(tǒng)中用戶可靠性考慮不足的問題，假設(shè)每個用戶針對不同類型任務(wù)具有不同的可靠性，并在此基礎(chǔ)上設(shè)計了一種基于用戶可靠性的眾包系統(tǒng)任務(wù)分配機(jī)制。首先，以任務(wù)發(fā)布者的收益最大化為優(yōu)化目標(biāo)，利用貪心技術(shù)，設(shè)計了一種高效的任務(wù)分配機(jī)制，即每次選擇一個能帶來最大收益的任務(wù)分配方案；其次，設(shè)計了一種基于歷史信息的用戶可靠性更新機(jī)制，用戶可靠性的更新由用戶歷史可靠性和當(dāng)前完成任務(wù)的質(zhì)量兩部分決定，并將支付給用戶的最終報酬與用戶的可靠性掛鉤，以激勵用戶持續(xù)高質(zhì)量地完成任務(wù)；最后，從任務(wù)發(fā)布者的總效益、任務(wù)完成率和用戶可靠性三個方面分析設(shè)計機(jī)制的有效性。實驗結(jié)果顯示，與ProMoT方法相比，所提出的方法在有效性和可行性方面均有較好的表現(xiàn)，并能夠提升任務(wù)發(fā)布者的總效益約16%，同時可以解決現(xiàn)有方法中的用戶不可靠問題，提高了眾包系統(tǒng)的可靠性和任務(wù)發(fā)布者的總收益。

任務(wù)分配；可靠性；眾包；收益最大化

0 引言

近年來，眾包(crowdsourcing)受到工業(yè)界和學(xué)術(shù)界的極大關(guān)注。在眾包系統(tǒng)中，任務(wù)發(fā)布者并不是將任務(wù)分配給固定的員工完成，而是采用開放的方式將特定任務(wù)通過專門的發(fā)布平臺(如Amazon Turk)分配給隨機(jī)出現(xiàn)的工人完成。任務(wù)發(fā)布者通過眾包系統(tǒng)可以充分利用互聯(lián)網(wǎng)上的用戶資源，發(fā)現(xiàn)新的創(chuàng)意或解決遇到的各類技術(shù)難題，以降低公司的運(yùn)營成本或提高公司的創(chuàng)新能力。

目前，眾包在很多領(lǐng)域已經(jīng)得到了廣泛的應(yīng)用，并涌現(xiàn)出大量商用的眾包平臺。例如，利用眾包平臺對機(jī)器翻譯的結(jié)果進(jìn)行質(zhì)量評估、識別海量圖像進(jìn)行分類以及評價網(wǎng)上商品的好壞等。然而，眾包系統(tǒng)的發(fā)展也面臨著挑戰(zhàn)。由于眾包系統(tǒng)中的任務(wù)完成者，也就是用戶，是一個不確定的大眾群體，使得用戶完成任務(wù)的質(zhì)量無法得到保證。部分自私的用戶可能會為了自身利益，提交低質(zhì)量甚至虛假的隨機(jī)數(shù)據(jù)給平臺。因此，為了保證眾包系統(tǒng)的性能，必須設(shè)計出高效的任務(wù)分配機(jī)制，挑選出最合適的用戶完成任務(wù)，從而保證任務(wù)的完成質(zhì)量。

目前針對眾包系統(tǒng)中的任務(wù)分配問題主要可以分為以下幾類：文獻(xiàn)[1]針對異質(zhì)感知任務(wù)的成本問題，提出了一種動態(tài)招募用戶的任務(wù)分配模型，并驗證了所提出算法的高效性；文獻(xiàn)[2]針對不同用戶的任務(wù)選擇情況，設(shè)計了一種分布式的感知任務(wù)分配模型；文獻(xiàn)[3]考慮了移動群智感知中公平高效的任務(wù)分配，并解決了最小最大聚合感知時間問題；文獻(xiàn)[4]提出了一種誠實的拍賣機(jī)制并致力于平臺的效益最大化；文獻(xiàn)[5]設(shè)計了一種基于中樞節(jié)點的多任務(wù)分發(fā)算法，實驗結(jié)果證明該算法可以提高任務(wù)的完成速度。然而，上述研究都沒有考慮用戶的可靠性問題。不同的用戶由于自身能力、對待任務(wù)的認(rèn)真程度等因素的不同，完成任務(wù)的質(zhì)量并不相同。也就是說，存在著用戶可靠性的問題。平臺在分配任務(wù)時應(yīng)該盡可能地挑選高可靠性的用戶完成任務(wù)。針對這一問題，目前對于眾包中用戶可靠性的研究主要有以下兩個方面：1)基于用戶聲譽(yù)機(jī)制的研究。把用戶的信譽(yù)值看作是眾包平臺判別用戶完成任務(wù)質(zhì)量高低的重要指標(biāo)，并且基于用戶的可靠程度進(jìn)行任務(wù)分配。比如在文獻(xiàn)[6-7]提出了一種基于用戶信譽(yù)值的激勵機(jī)制，并通過仿真實驗驗證了激勵機(jī)制的有效性。文獻(xiàn)[8]針對眾包系統(tǒng)中的激勵和信譽(yù)機(jī)制的研究，設(shè)計了激勵機(jī)制和信譽(yù)機(jī)制來確保用戶盡最大努力的高質(zhì)量的完成任務(wù)。文獻(xiàn)[9]中Zhang等提出了基于用戶信譽(yù)值的任務(wù)分配機(jī)制。文獻(xiàn)[10]中He等提出了一種基于任務(wù)位置的最優(yōu)任務(wù)分配算法，利用用戶的信譽(yù)值和用戶的位置進(jìn)行任務(wù)分配。2)激勵機(jī)制設(shè)計。給予用戶適當(dāng)?shù)莫剟羁梢约ぐl(fā)用戶的工作潛力，進(jìn)而保證了結(jié)果數(shù)據(jù)的質(zhì)量。文獻(xiàn)[11]提出了以平臺為中心和以用戶為中心的兩種不同的感知系統(tǒng)模型并設(shè)計了與模型相適應(yīng)的激勵機(jī)制；文獻(xiàn)[12]設(shè)計了一種離散的激勵機(jī)制并實現(xiàn)了平臺效益的最大化；文獻(xiàn)[13]設(shè)計了一種基于反向拍賣的激勵機(jī)制；文獻(xiàn)[14]提出了一種基于最優(yōu)的錦標(biāo)賽模型，并設(shè)計了相應(yīng)的激勵機(jī)制；文獻(xiàn)[15]結(jié)合反拍賣與Vickery拍賣思想，提出一種基于反拍賣模型的激勵方法。上述研究均假設(shè)每個用戶完成不同任務(wù)的可靠性都是相同的。然而這點在實際的眾包系統(tǒng)中并不成立。由于用戶所具備的技能不同，所以完成不同類型任務(wù)的可靠性應(yīng)該也是不同的，因此還需要設(shè)計新的任務(wù)分配機(jī)制以解決該問題。

為了解決上述問題，本文假設(shè)每個用戶針對不同類型的任務(wù)具有不同的用戶可靠性，并以任務(wù)發(fā)布者的利益最大化為優(yōu)化目標(biāo)，設(shè)計了一種高效的基于用戶可靠性的眾包系統(tǒng)任務(wù)分配機(jī)制。首先，將所研究的任務(wù)分配問題抽象為一個整數(shù)規(guī)劃問題；然后，采用貪心技術(shù)，實現(xiàn)了用戶和任務(wù)之間的高效匹配。除此之外，還設(shè)計了一種用戶可靠性的更新機(jī)制以及一種基于用戶可靠性的報酬計算機(jī)制，以激勵用戶高質(zhì)量地完成任務(wù)。最后，通過仿真實驗對所設(shè)計機(jī)制的性能進(jìn)行了驗證。

1 問題模型

本章將給出基于用戶可靠性的眾包任務(wù)分配模型，并對所研究的問題給出形式化的描述。

1.1 系統(tǒng)模型

假設(shè)所研究的眾包系統(tǒng)由一個任務(wù)發(fā)布者、一個眾包任務(wù)分配平臺和若干系統(tǒng)用戶(即工人)組成。在每個任務(wù)分配周期，任務(wù)發(fā)布者首先在平臺上發(fā)布n個任務(wù)，用集合T={t1,t2,…,tn}表示。由于所處的地理位置、要求的用戶技能等因素的不同，所以集合T中的任務(wù)是異質(zhì)的。對于每個任務(wù)ti∈T，可以用ti={Di,bi}來表示，其中Di是任務(wù)描述，包括ti的任務(wù)具體要求(如，技能要求等)，而bi則表示任務(wù)ti報價，即任務(wù)發(fā)布者在用戶完成任務(wù)后所愿意支付的最高報酬。用戶在閱讀完任務(wù)描述后，會將滿足要求且感興趣任務(wù)作為自身的任務(wù)請求發(fā)送給平臺。假設(shè)系統(tǒng)中共有m個用戶，且這些用戶也是異質(zhì)的。這些異質(zhì)的用戶由于所具備的技能、對待任務(wù)的認(rèn)真程度等因素的不同，完成任務(wù)的質(zhì)量是不同的。所以，對于用戶集合W中的每個用戶j∈W可以表示為j={Rj,Cj,Tj}，其中Rj表示用戶j的可靠性，每個ci, j∈Cj表示用戶j高質(zhì)量完成任務(wù)ti所需的成本，Tj是用戶j提交給平臺的感興趣任務(wù)集合。由于每個用戶完成不同任務(wù)的可靠性也可能不同，所以本文假設(shè)Rj是一個集合，每個ri,j∈Rj表示用戶j完成任務(wù)ti的可靠性；ri, j反映了用戶j以往完成與ti同類任務(wù)的情況，可靠性ri, j越高，說明用戶j以往完成此類任務(wù)的質(zhì)量越高。

平臺在收到用戶的任務(wù)請求之后，會根據(jù)一定的分配規(guī)則，完成用戶與任務(wù)之間的匹配。為了保證任務(wù)的完成質(zhì)量，本文假設(shè)每個任務(wù)可以同時分配給不超過l個用戶去完成，而每個用戶在每個任務(wù)分配階段最多只會分配到一個任務(wù)。為了盡可能地保證每個任務(wù)都能夠分配到用戶并被高質(zhì)量地完成，平臺將會從任務(wù)的參與用戶數(shù)和參與用戶的可靠性兩個方面來合理地選擇用戶并分配任務(wù)。最后，任務(wù)發(fā)布者在用戶在完成任務(wù)后會根據(jù)任務(wù)的完成質(zhì)量，計算每個用戶應(yīng)得的報酬。至此，一個任務(wù)分配周期結(jié)束。

1.2 問題描述

本文要在考慮用戶可靠性的基礎(chǔ)上，設(shè)計一種眾包系統(tǒng)任務(wù)分配機(jī)制，以任務(wù)發(fā)布者利益最大化為優(yōu)化目標(biāo)，實現(xiàn)用戶與任務(wù)的最優(yōu)匹配。

本文用yi,j={0,1}表示任務(wù)ti是否可以被分配給用戶j：若任務(wù)ti可以被分配給用戶j，則yi, j=1，否則yi, j=0。同理，用xi,j={0,1}表示任務(wù)ti是否分配給用戶j：若ti分配給了用戶j，則xi, j=1，否則xi, j=0。

每個用戶完成任務(wù)后均會給任務(wù)發(fā)布者帶來一定的收益。由于不同用戶的可靠性不同，所以不同用戶所能帶來的利益也不同。假設(shè)用戶高質(zhì)量完成任務(wù)ti所能帶來的利益為vi，那么用戶j完成任務(wù)ti所能帶來的利益可以用函數(shù)f(i,j)表示，且滿足0≤f(i,j)≤vi。在本文中，取f(i,j)=ri, jvi，0≤ri, j≤1。用Wi表示所有分配給任務(wù)ti的用戶集合，那么任務(wù)發(fā)布者從任務(wù)ti所能獲得的收益為：

(1)

其中，pi,j為用戶j完成任務(wù)ti后獲得的報酬。為了激勵用戶更好地完成任務(wù)，所設(shè)計的機(jī)制在用戶的任務(wù)完成質(zhì)量和實際報酬之間建立關(guān)聯(lián)，使得完成任務(wù)質(zhì)量越高的用戶，獲得的報酬越多。因此，采用的具體報酬計算方式為：

pi,j=ri, jbi

(2)

用戶完成任務(wù)的質(zhì)量越高，可靠性越高。從式(2)不難看出，用戶完成任務(wù)的質(zhì)量越高得到的報酬也越高，可以激勵用戶認(rèn)真完成任務(wù)。

綜合式(1)和(2)，可以進(jìn)一步得到：

(3)

本文的最終的優(yōu)化目標(biāo)是使任務(wù)發(fā)布者的收益最大化，可以規(guī)約為式(4)所示的整數(shù)規(guī)劃問題：

s.t.

(4)

2 基于用戶可靠性的眾包系統(tǒng)任務(wù)分配機(jī)制

本章將給出所設(shè)計機(jī)制的具體實現(xiàn)細(xì)節(jié)。所設(shè)計的機(jī)制主要包含兩部分：基于用戶可靠性的任務(wù)分配機(jī)制和用戶可靠性的更新機(jī)制。

2.1 基于用戶可靠性的任務(wù)分配機(jī)制

為了解決式(4)所示的整數(shù)規(guī)劃問題，本文采用貪心技術(shù)，設(shè)計了一種基于用戶可靠性的眾包任務(wù)分配機(jī)制。在所設(shè)計的機(jī)制中，眾包平臺在收到所有用戶的任務(wù)請求后，會以任務(wù)發(fā)布者的收益最大化為優(yōu)化目標(biāo)，實現(xiàn)用戶和任務(wù)之間的匹配。所設(shè)計的任務(wù)分配機(jī)制如算法1所示。

算法1 基于用戶可靠性的眾包任務(wù)分配機(jī)制。

輸入：用戶集合W和任務(wù)集合T；

輸出：任務(wù)分配結(jié)果X={xi, j}ti∈T, j∈W。

1)

for{每個ti∈T}

2)

{

3)

for{每個用戶j∈W}

4)

{

5)

設(shè)置xi, j=0；

6)

}

7)

}

8)

While (T≠?且W≠?)

9)

{

10)

設(shè)置umax=0；

11)

for{每個ti∈T}

12)

{

13)

for{每個用戶j∈W}

14)

{

15)

if(ri, j(vi-bi)≥umax)

16)

{

17)

設(shè)置umax=ri, jyi, j(vi-bi)；

18)

設(shè)置tmax=i,wmax=j；

19)

}

20)

}

21)

}

22)

if(umax>0)

23)

{

24)

設(shè)置xtmax,wmax=1；

25)

從集合W中刪除用戶j；

26)

if(tmax已經(jīng)分配給了l個用戶)

27)

從集合T中刪除任務(wù)tmax；

28)

}

29)

else

30)

ReturnX;

31)

}

32)

ReturnX;

算法1的輸入為初始的用戶集合W和任務(wù)集合T，在平臺將任務(wù)分配給用戶后，將任務(wù)分配結(jié)果X={xi, j}ti∈T, j∈W作為輸出返回給用戶。

首先，算法1初始化任務(wù)分配結(jié)果中的所有變量xi, j=0。然后采用迭代的方式進(jìn)行任務(wù)分配且每次迭代完成一個任務(wù)與用戶之間的匹配。在每次迭代時，首先遍歷所有的可行分配，找到一個能帶來最大收益的分配方案。分別用tmax和wmax記錄下能帶來最大收益分配方案的任務(wù)和用戶，并用umax表示該方案所能帶來的收益。umax初始化為0。然后，判斷任務(wù)發(fā)布者的收益是否還能繼續(xù)提升，即判斷umax是否大于0。若umax>0，則通過設(shè)置xtmax,wmax=1將任務(wù)tmax分配給用戶wmax，并從集合W中刪除用戶j。除此之外，如果判斷任務(wù)tmax已經(jīng)分配給了l個用戶，還需要將tmax從集合T中刪除；否則，umax=0則表示任務(wù)發(fā)布者的收益無法繼續(xù)提升，直接返回分配結(jié)果。除此之外，若在迭代過程中發(fā)現(xiàn)用戶集合W或任務(wù)集合T為?，則表示任務(wù)分配已經(jīng)結(jié)束，直接返回分配結(jié)果即可。

2.2 用戶可靠性的更新機(jī)制

在基于用戶可靠性的眾包系統(tǒng)分配機(jī)制中，本文需要用到用戶的可靠性信息來計算任務(wù)分配所能帶來的收益以及最終給用戶的報酬。為了能使用戶的可靠性信息能真實地反映用戶近期完成任務(wù)的質(zhì)量，每次任務(wù)分配結(jié)束后還應(yīng)該根據(jù)本輪用戶的任務(wù)完成質(zhì)量更新該用戶的可靠性信息。

(5)

用戶可靠性更新完成后，下一輪眾包任務(wù)分配開始，更新后的用戶可靠性信息將被用于在下一輪任務(wù)分配中計算收益以及報酬。

3 仿真實驗

本文提出了一種基于用戶可靠性的眾包任務(wù)分配機(jī)制，綜合考慮用戶完成任務(wù)的歷史情況，采用了貪心的思想，實現(xiàn)了用戶和任務(wù)之間的高效匹配。為驗證本文提出機(jī)制的有效性，下面將給出所設(shè)計算法的仿真實驗結(jié)果，并以此來分析和驗證其實際性能。

接下來介紹一下評價算法好壞的相關(guān)指標(biāo)：任務(wù)發(fā)布者的總收益和任務(wù)成交率。任務(wù)發(fā)布者的總收益定義為平臺上所有發(fā)布任務(wù)的收益總和。任務(wù)成交率定義為平臺上分配到用戶的任務(wù)數(shù)量和平臺上所有任務(wù)總數(shù)的比值。

在仿真實驗中，只有一個任務(wù)發(fā)布者，平臺上每個任務(wù)的報價為b∈[3,6]，每個任務(wù)最多分配給l=4個用戶去完成。每個用戶的初始可靠性r=0.5，每個用戶完成任務(wù)的成本為c∈[1,4]，α=0.8。本文提出的任務(wù)分配算法是和文獻(xiàn)[4]中的ProMoT(Profit Maximizing Truthful auction mechanism)進(jìn)行對比實驗的。

3.1 用戶人數(shù)對任務(wù)發(fā)布者總收益有的影響

仿真實驗的第一部分主要分析用戶人數(shù)與任務(wù)發(fā)布者的總收益之間的關(guān)系。在任務(wù)數(shù)n設(shè)置為60的情況下，對兩種方法作對比實驗，用戶數(shù)m與任務(wù)發(fā)布者的總收益之間的關(guān)系如圖1所示。

由圖1可知，本文提出的任務(wù)分配算法優(yōu)于ProMoT，可以使平臺獲得更多的收益，這是因為ProMoT在選擇用戶分配任務(wù)的時候沒有考慮到用戶的可靠性問題。在任務(wù)數(shù)量固定時，兩條曲線的變化趨勢大致相同，隨著用戶人數(shù)的增加，任務(wù)發(fā)布者的總收益也隨之上升。剛開始，平臺上用戶人數(shù)較少，任務(wù)需求的用戶數(shù)大于平臺中用戶總數(shù)。隨著用戶人數(shù)的增加，每個任務(wù)可以分配到的用戶數(shù)也逐漸變多，被完成的任務(wù)數(shù)量也逐漸增多，那么任務(wù)發(fā)布者的總收益也隨之上升。當(dāng)用戶人數(shù)超過一定數(shù)量后，每個任務(wù)都分配到了足夠多的用戶，任務(wù)發(fā)布者的總收益上升的速度變慢，最終任務(wù)發(fā)布者的總收益趨于平緩。

圖1 用戶人數(shù)與任務(wù)發(fā)布者的總收益之間的關(guān)系(n=60)

3.2 任務(wù)數(shù)量對任務(wù)發(fā)布者總收益的影響

圖2給出了用戶數(shù)量保持為200不變的條件下，任務(wù)數(shù)量與任務(wù)發(fā)布者總效益之間的關(guān)系。從實驗結(jié)果可以看出，本文提出的基于用戶可靠性的任務(wù)分配算法較之文獻(xiàn)[4]中的ProMoT對平臺收益提升幫助更大。這是因為ProMoT僅僅考慮了當(dāng)前用戶報價的高低，忽略了用戶在完成任務(wù)時的可靠性問題。在用戶數(shù)量一定的情況下，隨著平臺上發(fā)布任務(wù)數(shù)量的增加，任務(wù)發(fā)布者的總收益也隨之上升。但是，當(dāng)平臺上發(fā)布任務(wù)數(shù)量超過一定數(shù)量后，任務(wù)所需求的用戶數(shù)量超過了平臺上的用戶數(shù)量，任務(wù)發(fā)布者的總收益上升速度逐漸降低，最終趨于平穩(wěn)。

圖2 任務(wù)數(shù)與任務(wù)發(fā)布者總收益之間的關(guān)系(m=200)

3.3 用戶人數(shù)對任務(wù)成交率的影響

為了驗證不同任務(wù)數(shù)量對任務(wù)成交率的影響，對任務(wù)數(shù)量進(jìn)行實驗對比，分別針對n=40，n=50和n=60進(jìn)行實驗驗證，實驗對比結(jié)果如圖3所示。從實驗結(jié)果可以看出，當(dāng)n=60時，平臺上任務(wù)成交率最高。在任務(wù)數(shù)量固定的情況下，隨著用戶數(shù)量的增加，每個任務(wù)都能夠分配到用戶，任務(wù)成交率也在不斷提高。當(dāng)用戶人數(shù)超過一定數(shù)量后，因為平臺上符合任務(wù)要求的用戶已經(jīng)分配到任務(wù)，剩下的任務(wù)沒有用戶符合要求,所以最終任務(wù)成交率會達(dá)到一個平穩(wěn)的趨勢。

圖3 用戶人數(shù)與任務(wù)成交率之間的關(guān)系

3.4 可靠性更新系數(shù)α對任務(wù)發(fā)布者總收益的影響

仿真實驗的第四部分主要分析可靠性更新系數(shù)α與任務(wù)發(fā)布者總收益之間的關(guān)系。在系數(shù)α分別設(shè)置為0.5、0.6、0.7、0.8和0.9五種情況下，系數(shù)α與任務(wù)發(fā)布者總收益之間的關(guān)系如圖4所示。

在該實驗中沒有選取更小的可靠性更新系數(shù)α，這是因為本文希望在用戶的可靠性更新過程中，用戶的歷史可靠性占主要部分。從實驗結(jié)果可以看出，隨著系數(shù)α的增加，任務(wù)發(fā)布者總收益也呈現(xiàn)上升的趨勢。當(dāng)α=0.8時，任務(wù)發(fā)布者總收益達(dá)到最大；當(dāng)α>0.8時，該可靠性更新方法就退化為傳統(tǒng)的可靠性更新方法，所以為了提高整個眾包平臺中任務(wù)發(fā)布者的總效益，設(shè)定α=0.8。

圖4 可靠性更新系數(shù)α與任務(wù)發(fā)布者總收益之間的關(guān)系

4 結(jié)語

本文針對眾包系統(tǒng)中的任務(wù)分配機(jī)制進(jìn)行了研究，主要解決了已有研究中存在的未充分考慮用戶的可靠性問題，特別是用戶針對不同類型的任務(wù)具有不同的可靠性的問題。研究首先以任務(wù)發(fā)布者的收益最大化為優(yōu)化目標(biāo)，采用貪心技術(shù)，設(shè)計了一種基于用戶可靠性的任務(wù)分配機(jī)制。然后設(shè)計了一種用戶可靠性的更新機(jī)制和報酬計算機(jī)制，以激勵用戶高質(zhì)量地完成任務(wù)。最后，通過仿真實驗證明了所設(shè)計任務(wù)分配機(jī)制的高效性。

References)

[1] LI H, LI T, WANG Y. Dynamic participant recruitment of mobile crowd sensing for heterogeneous sensing tasks [C]// Proceedings of the 2015 IEEE 12th International Conference on Mobile Ad Hoc and Sensor Systems. Washington, DC: IEEE Computer Society, 2015: 136-144.

[2] CHEUNG M H, SOUTHWELL R, HOU F, et al. Distributed time-sensitive task selection in mobile crowdsensing [C] // Proceedings of the 16th ACM International Symposium on Mobile Ad Hoc Networking and Computing. New York: ACM, 2015: 157-166.

[3] ZHAO Q, ZHU Y, ZHU H, et al. Fair energy-efficient sensing task allocation in participatory sensing with smartphones [C]// Proceedings of the 2014 IEEE Conference on Computer Communications. Piscataway, NJ: IEEE, 2014: 1366-1374.

[4] SHAH-MANSOURI H, WONG V W S. Profit maximization in mobile crowdsourcing: a truthful auction mechanism [C] // Proceedings of the 2015 IEEE International Conference on Communications. Piscataway, NJ: IEEE, 2015: 3216-3221.

[5] 徐哲,李卓,陳昕.面向移動群智感知的多任務(wù)分發(fā)算法[J].計算機(jī)應(yīng)用,2017,37(1):18-23.(XU Z, LI Z, CHEN X. Multi-task assignment algorithm for mobile crowdsensing [J]. Journal of Computer Applications, 2017, 37(1): 18-23. )

[6] 芮蘭蘭,張攀,黃豪球,等.一種面向眾包的基于信譽(yù)值的激勵機(jī)制[J].電子與信息學(xué)報,2016,38(7):1808-1815.(RUI L L, ZHANG P, HUANG H Q, et al. Reputation-based incentive mechanisms in crowdsourcing [J]. Journal of Electronics & Information Technology, 2016, 38(7): 1808-1815.)

[7] KATMADA A, SATSIOU A, KOMPATSIARIS I. A reputation-based incentive mechanism for a crowdsourcing platform for financial awareness [EB/OL]. [2016- 11- 19]. http://projectprofit.eu/wp-content/uploads/2016/03/chp3A10.10072F978-3-319-50237-3_2.compressed.pdf.

[8] 王瑩潔,蔡志鵬,童向榮,等.基于聲譽(yù)的移動眾包系統(tǒng)的在線激勵機(jī)制[J].計算機(jī)應(yīng)用,2016,36(8):2121-2127.(WANG Y J, CAI Z P, TONG X R, et al. Online incentive mechanism based on reputation for mobile crowdsourcing system [J]. Journal of Computer Applications, 2016, 36(8): 2121-2127.)

[9] ZHANG Y, VAN DER SCHAAR M. Reputation-based incentive protocols in crowdsourcing applications [C]// Proceedings of the 2012 IEEE INFOCOM. Piscataway, NJ: IEEE, 2012: 2140-2148.

[10] HE S, SHIN D H, ZHANG J, et al. Toward optimal allocation of location dependent tasks in crowdsensing [C]// Proceedings of the 2014 IEEE Conference on Computer Communications. Piscataway, NJ: IEEE, 2014: 745-753.

[11] YANG D, XUE G, FANG X, et al. Crowdsourcing to smartphones: incentive mechanism design for mobile phone sensing [C]// Proceedings of the 18th Annual International Conference on Mobile Computing and Networking. New York: ACM, 2012: 173-184.

[12] JI S, CHEN T. Crowdsensing incentive mechanisms for mobile systems with finite precisions [C]// Proceedings of the 2014 IEEE International Conference on Communications. Piscataway, NJ: IEEE, 2014: 2544-2549.

[13] ZHU X, AN J, YANG M, et al. A fair incentive mechanism for crowdsourcing in crowd sensing [J]. IEEE Internet of Things Journal, 2016, 3(6): 1364-1372.

[14] ZHANG Y, JIANG C, SONG L, et al. Incentive mechanism for mobile crowdsourcing using an optimized tournament model [J]. IEEE Journal on Selected Areas in Communications, 2017, 35(4): 880-892.

[15] 朱旋,楊麥順,安健,等.群智感知中基于反拍賣模型的眾包激勵方法 [J].計算機(jī)應(yīng)用,2016,36(7):2038-2045.(ZHU X, YANG M S, AN J, et al. Crowdsourcing incentive method based on reverse auction model in crowd sensing [J]. Journal of Computer Applications, 2016, 36(7): 2038-2045.)

Taskallocationmechanismforcrowdsourcingsystembasedonreliabilityofusers

SHI Zhan1, XIN Yu2, SUN Yu’e3,4*, HUANG He1,4

(1.SchoolofComputerScienceandTechnology,SoochowUniversity,SuzhouJiangsu215006,China;2.BeijingInstituteofRemoteSensingInformation,Beijing100011,China;3.SchoolofUrbanRailTransportation,SoochowUniversity,SuzhouJiangsu215137,China;4.SuzhouInstituteforAdvancedStudy,UniversityofScienceandTechnologyofChina,SuzhouJiangsu215123,China)

Considering the shortcomings of existing research on the problem of user reliability in crowdsourcing systems, it was assumed that each user had different reliability for different type of tasks, and on this basis, a task allocation mechanism for crowdsourcing system was designed based on the reliability of users. Firstly, an efficient task allocation mechanism was designed by using the greedy technology to maximize the profit of task publishers, and the task allocation scheme with the maximum benefit was chosen every time. Secondly, a mechanism of user reliability updating based on historical information was designed and determined by user historical reliability and the quality of the current task, and the final payment paid to the user was linked with the reliability of the user, so as to motivate the user to finish tasks with high quality continuously. Finally, the effectiveness of the designed mechanisms was analyzed in three ways: the total profit of task publishers, the task completion rate and the user reliability. The simulation results show that compared with ProMoT (Profit Maximizing Truthful auction mechanism), the proposed method is more effective and feasible, and the rate of the total benefit of task publishers is 16% higher. At the same time, it can solve the problem of user unreliability in the existing methods, and increase the reliability of crowdsourcing systems and the total revenue of task publishers.

task allocation; reliability; crowdsourcing; revenue maximization

2017- 03- 27;

2017- 04- 18。

國家自然科學(xué)基金面上項目(61572342, 61672369)；江蘇省自然科學(xué)基金資助項目(BK20151240, BK20161258)；中國博士后科學(xué)基金資助項目(2015M580470, 2016M591920)。

施戰(zhàn)(1992—)，男，安徽亳州人，碩士研究生，主要研究方向：眾包中任務(wù)分配和用戶可靠性； 辛煜(1988—)，男，安徽太湖人，工程師，博士，主要研究方向：遙感圖像處理、人工智能、眾包中任務(wù)分配和用戶可靠性； 孫玉娥(1983—)，女，山東青島人，副教授，博士，主要研究方向：群智感知、無線網(wǎng)絡(luò)資源分配； 黃河(1983—)，男，安徽合肥人，副教授，博士，主要研究方向：頻譜資源分配、群智感知、軟件定義網(wǎng)絡(luò)。

1001- 9081(2017)09- 2449- 05

10.11772/j.issn.1001- 9081.2017.09.2449

TP393.01

A

This work is partially supported by National Natural Science Foundation of China (61572342, 61672369), the Natural Science Foundation of Jiangsu Province (BK20151240, BK20161258), China Postdoctoral Science Foundation (2015M580470, 2016M591920).

SHIZhan, born in 1992, M. S. candidate. His research interests include task allocation and user reliability in crowdsourcing.

XINYu, born in 1988, Ph. D., engineer. His research interests include remote sensing image processing, artificial intelligence, task allocation and user reliability in crowdsourcing.

SUNYu’e, born in 1983, Ph. D., associate professor. Her research interests include crowdsensing, wireless network resource allocation.

HUANGHe, born in 1983, Ph. D., associate professor. His research interests include spectrum resource allocation, crowdsensing, software defined network.