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

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

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

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

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

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

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

0 引言

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

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

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

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

1 問題模型

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

1.1 系統(tǒng)模型

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

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

1.2 問題描述

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

每個(gè)用戶完成任務(wù)后均會(huì)給任務(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后獲得的報(bào)酬。為了激勵(lì)用戶更好地完成任務(wù)，所設(shè)計(jì)的機(jī)制在用戶的任務(wù)完成質(zhì)量和實(shí)際報(bào)酬之間建立關(guān)聯(lián)，使得完成任務(wù)質(zhì)量越高的用戶，獲得的報(bào)酬越多。因此，采用的具體報(bào)酬計(jì)算方式為：

pi,j=ri, jbi

(2)

用戶完成任務(wù)的質(zhì)量越高，可靠性越高。從式(2)不難看出，用戶完成任務(wù)的質(zhì)量越高得到的報(bào)酬也越高，可以激勵(lì)用戶認(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ì)機(jī)制的具體實(shí)現(xiàn)細(xì)節(jié)。所設(shè)計(jì)的機(jī)制主要包含兩部分：基于用戶可靠性的任務(wù)分配機(jī)制和用戶可靠性的更新機(jī)制。

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

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

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

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

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

1)

for{每個(gè)ti∈T}

2)

{

3)

for{每個(gè)用戶j∈W}

4)

{

5)

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

6)

}

7)

}

8)

While (T≠?且W≠?)

9)

{

10)

設(shè)置umax=0；

11)

for{每個(gè)ti∈T}

12)

{

13)

for{每個(gè)用戶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個(gè)用戶)

27)

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

28)

}

29)

else

30)

ReturnX;

31)

}

32)

ReturnX;

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

首先，算法1初始化任務(wù)分配結(jié)果中的所有變量xi, j=0。然后采用迭代的方式進(jìn)行任務(wù)分配且每次迭代完成一個(gè)任務(wù)與用戶之間的匹配。在每次迭代時(shí)，首先遍歷所有的可行分配，找到一個(gè)能帶來最大收益的分配方案。分別用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個(gè)用戶，還需要將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ī)制中，本文需要用到用戶的可靠性信息來計(jì)算任務(wù)分配所能帶來的收益以及最終給用戶的報(bào)酬。為了能使用戶的可靠性信息能真實(shí)地反映用戶近期完成任務(wù)的質(zhì)量，每次任務(wù)分配結(jié)束后還應(yīng)該根據(jù)本輪用戶的任務(wù)完成質(zhì)量更新該用戶的可靠性信息。

(5)

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

3 仿真實(shí)驗(yàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語

本文針對(duì)眾包系統(tǒng)中的任務(wù)分配機(jī)制進(jìn)行了研究，主要解決了已有研究中存在的未充分考慮用戶的可靠性問題，特別是用戶針對(duì)不同類型的任務(wù)具有不同的可靠性的問題。研究首先以任務(wù)發(fā)布者的收益最大化為優(yōu)化目標(biāo)，采用貪心技術(shù)，設(shè)計(jì)了一種基于用戶可靠性的任務(wù)分配機(jī)制。然后設(shè)計(jì)了一種用戶可靠性的更新機(jī)制和報(bào)酬計(jì)算機(jī)制，以激勵(lì)用戶高質(zhì)量地完成任務(wù)。最后，通過仿真實(shí)驗(yàn)證明了所設(shè)計(jì)任務(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] 徐哲,李卓,陳昕.面向移動(dòng)群智感知的多任務(wù)分發(fā)算法[J].計(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ù)值的激勵(lì)機(jī)制[J].電子與信息學(xué)報(bào),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ù)的移動(dòng)眾包系統(tǒng)的在線激勵(lì)機(jī)制[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] 朱旋,楊麥順,安健,等.群智感知中基于反拍賣模型的眾包激勵(lì)方法 [J].計(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。

國(guó)家自然科學(xué)基金面上項(xiàng)目(61572342, 61672369)；江蘇省自然科學(xué)基金資助項(xiàng)目(BK20151240, BK20161258)；中國(guó)博士后科學(xué)基金資助項(xiàng)目(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.