朱旋 楊麥順 安健 向樂樂 楊薔薇

摘要：激勵(lì)是實(shí)現(xiàn)群智感知（CS）眾包服務(wù)的主要方法，針對(duì)現(xiàn)有方法在服務(wù)過程中沒有充分考慮節(jié)點(diǎn)參與數(shù)量和惡意競(jìng)爭(zhēng)對(duì)群智感知帶來的影響，提出一種基于反拍賣模型的激勵(lì)（RVAIM）方法。首先，研究眾包的激勵(lì)機(jī)制，結(jié)合反拍賣與Vickrey拍賣思想，構(gòu)建面向任務(wù)覆蓋的反拍賣模型；其次，對(duì)模型中涉及的任務(wù)覆蓋、反拍賣選擇和獎(jiǎng)勵(lì)實(shí)施等關(guān)鍵技術(shù)問題進(jìn)行深入分析與研究；最后，從計(jì)算有效、個(gè)人理性、預(yù)算平衡、真實(shí)性和誠(chéng)實(shí)性五個(gè)方面分析RVAIM激勵(lì)方法的有效性。實(shí)驗(yàn)結(jié)果表明，與IMCSS和MSensing激勵(lì)方法相比，RVAIM在有效性和可行性方面均有較好的表現(xiàn)，能夠解決現(xiàn)有方法中的惡意競(jìng)爭(zhēng)問題，并能夠平均提升眾包服務(wù)完成率約21%。

關(guān)鍵詞：

群智感知；眾包；激勵(lì)機(jī)制；反拍賣；Vickrey拍賣

中圖分類號(hào)： TP181 文獻(xiàn)標(biāo)志碼：A

0引言

手機(jī)和Pad等移動(dòng)智能終端除了基礎(chǔ)信息通信功能外，在搭載攝像頭、麥克風(fēng)、GPS（Global Position System）、加速器、陀螺儀、溫濕計(jì)等嵌入式傳感器設(shè)備后還具備強(qiáng)大的數(shù)據(jù)感知能力。群智感知（Crowd Sensing， CS）[1]即是借助攜帶此類智能終端的移動(dòng)用戶，實(shí)現(xiàn)對(duì)用戶或其周邊環(huán)境多維數(shù)據(jù)的快速收集，包括溫度、濕度、地理位置和噪聲水平等信息，并基于這些海量感知信息進(jìn)行統(tǒng)計(jì)和分析，進(jìn)而挖掘出群體的行為模式和服務(wù)關(guān)聯(lián)屬性等信息。

眾包[2]是實(shí)現(xiàn)CS的主要方法，它通過調(diào)動(dòng)大眾的智慧和計(jì)算能力來實(shí)現(xiàn)感知任務(wù)的合理分配和有效覆蓋。然而，用戶在提供眾包服務(wù)的過程中會(huì)消耗自身資源，如電量、網(wǎng)絡(luò)流量和時(shí)間等；同時(shí)因共享位置信息還會(huì)帶來潛在的隱私威脅，致使用戶參與積極性降低。激勵(lì)[3-7]作為實(shí)現(xiàn)CS眾包服務(wù)的主要方式之一，它通過設(shè)計(jì)適當(dāng)?shù)莫?jiǎng)酬措施，來激發(fā)用戶參與眾包服務(wù)的積極性。進(jìn)一步分析國(guó)內(nèi)外相關(guān)研究[2，8-11]可以看出：1）現(xiàn)有的眾包激勵(lì)模型多數(shù)以用戶數(shù)量滿足任務(wù)完成要求為前提，并沒有充分考慮眾包中任務(wù)的參與用戶數(shù)量，在實(shí)際應(yīng)用中可能出現(xiàn)某些任務(wù)的用戶數(shù)量達(dá)不到要求的情況，致使此類任務(wù)無法得到有效完成；2）現(xiàn)有基于拍賣模型的激勵(lì)機(jī)制并沒有深入分析競(jìng)爭(zhēng)中的惡意行為給眾包實(shí)現(xiàn)帶來的影響，容易出現(xiàn)通過虛報(bào)任務(wù)競(jìng)標(biāo)值（低于任務(wù)開銷）增大用戶自身效用等問題，任務(wù)競(jìng)拍過程中公平性的缺失，致使用戶參與眾包服務(wù)的積極性降低。

針對(duì)上述激勵(lì)研究中存在的問題，本文提出一種基于反Vickrey拍賣的激勵(lì)機(jī)制（Reverse Vickrey Auction Incentive Mechanism，RVAIM），以此解決眾包中服務(wù)完成率低和激勵(lì)機(jī)制中惡意競(jìng)爭(zhēng)的問題。

1相關(guān)研究

激勵(lì)機(jī)制是CS系統(tǒng)的重要組成部分。Doan等[12]對(duì)激勵(lì)機(jī)制的設(shè)計(jì)提出兩大挑戰(zhàn)：一是如何招募和保持參與用戶；二是怎樣評(píng)估和計(jì)算參與用戶的貢獻(xiàn)。前者是從用戶角度，要求參與用戶的損耗、興趣等得到滿足；后者是從服務(wù)平臺(tái)角度，要求對(duì)感知數(shù)據(jù)的質(zhì)量和獎(jiǎng)勵(lì)預(yù)算進(jìn)行權(quán)衡。Yang等[2]分別從參與用戶和服務(wù)平臺(tái)角度構(gòu)建了PlatformCentric和UserCentric兩種激勵(lì)模型，前者通過計(jì)算唯一Stackelberg Equilibrium，實(shí)現(xiàn)服務(wù)平臺(tái)效用的最大化，但用戶效用僅依據(jù)時(shí)間因子進(jìn)行計(jì)算，模型應(yīng)用范圍具有局限性；后者則基于反拍賣模型，通過真實(shí)性等四個(gè)經(jīng)濟(jì)特性保證了模型的有效性，但該模型并未考慮用戶可能采用競(jìng)標(biāo)值低于任務(wù)開銷的惡意競(jìng)標(biāo)方式。Tham等[13]為提高用戶參與的公平性和最大化社會(huì)效用，分別提出IDF（Incentive with Demand Fairness）和TIF（Iterative Tank Filling）激勵(lì)機(jī)制。Wu等[4]根據(jù)用戶的歷史服務(wù)可信度提出一種信譽(yù)激勵(lì)機(jī)制。Li等[5]則針對(duì)用戶隱私保護(hù)問題提出兩種關(guān)于加強(qiáng)隱私安全方面的激勵(lì)機(jī)制。

反拍賣模型是經(jīng)濟(jì)可行的，可解決用戶退出和預(yù)算平衡兩個(gè)典型激勵(lì)問題[14]。為此，基于反拍賣模型的激勵(lì)機(jī)制得到深入研究與廣泛應(yīng)用。Zhang等[8]考慮用戶之間存在合作關(guān)系，依據(jù)服務(wù)平臺(tái)數(shù)量及用戶競(jìng)標(biāo)數(shù)量的不同，分別提出SSModel（Singlerequester Singlebid）、SMModel（Singlerequester Multiplebid）和MMModel（Multiplerequester Multiplebid）三種激勵(lì)模型，其中SSModel是UserCentric模型[2]的一個(gè)特例，SMModel是SSModel的一般形式，MMModel綜合了服務(wù)平臺(tái)與用戶兩種競(jìng)爭(zhēng)方式，但三個(gè)激勵(lì)模型均沒有考慮任務(wù)競(jìng)拍過程中的惡意競(jìng)爭(zhēng)問題。Zhao等[6]根據(jù)用戶參與任務(wù)的時(shí)機(jī)，結(jié)合非負(fù)子模函數(shù)特性，提出兩種在線激勵(lì)機(jī)制。Gao等[7]則針對(duì)如何依據(jù)位置條件選擇參與用戶的問題，提出一種可實(shí)現(xiàn)用戶長(zhǎng)期參與的激勵(lì)機(jī)制。

通過以上分析，目前激勵(lì)機(jī)制主要從數(shù)據(jù)質(zhì)量、區(qū)域覆蓋和獎(jiǎng)勵(lì)預(yù)算等角度進(jìn)行設(shè)計(jì)，即依據(jù)激勵(lì)條件直接對(duì)用戶進(jìn)行篩選，而沒有充分考慮任務(wù)的實(shí)際參與用戶數(shù)量及用戶競(jìng)爭(zhēng)中的惡意行為，容易出現(xiàn)因任務(wù)沒有適宜用戶參與而導(dǎo)致任務(wù)沒有完成的問題和因任務(wù)競(jìng)標(biāo)中的惡意競(jìng)爭(zhēng)行為而導(dǎo)致用戶參與積極性降低的問題。

2面向任務(wù)覆蓋的反拍賣激勵(lì)模型

2.1構(gòu)建激勵(lì)模型

如圖1所示，面向任務(wù)覆蓋的反拍賣激勵(lì)模型主要由三個(gè)組件構(gòu)成：服務(wù)請(qǐng)求者、服務(wù)平臺(tái)和服務(wù)提供者。其中，服務(wù)請(qǐng)求者是感知任務(wù)（簡(jiǎn)稱任務(wù)）的發(fā)布者；服務(wù)提供者是任務(wù)的執(zhí)行者，即眾包用戶；而服務(wù)平臺(tái)是眾包實(shí)現(xiàn)的核心組件，負(fù)責(zé)任務(wù)與用戶的細(xì)粒度匹配，其包括任務(wù)覆蓋、反拍賣選擇和獎(jiǎng)勵(lì)實(shí)施三個(gè)模塊。通過任務(wù)覆蓋模塊和反拍賣選擇模塊依次對(duì)參選的服務(wù)請(qǐng)求者進(jìn)行選擇，以選出參與任務(wù)的優(yōu)勝者集；在任務(wù)結(jié)束后，通過獎(jiǎng)勵(lì)實(shí)施模塊對(duì)優(yōu)勝者集中的用戶實(shí)施獎(jiǎng)勵(lì)。其中，在反拍賣過程中，服務(wù)平臺(tái)被視為任務(wù)的拍賣者，而服務(wù)提供者被視為任務(wù)的競(jìng)拍者。首先，服務(wù)請(qǐng)求者向服務(wù)平臺(tái)請(qǐng)求執(zhí)行任務(wù)集Γ ={τ1，τ2，…，τm}（m≥2，m∈N+）；同時(shí)給出獎(jiǎng)勵(lì)集V={v1，v2，…，vm}。其中，vi為任務(wù)τi的獎(jiǎng)勵(lì)設(shè)置值，τi之間相互獨(dú)立且τi不可再分。其次，服務(wù)平臺(tái)向可能對(duì)Γ感興趣的服務(wù)提供者候選集W={w1，w2，…，wn}（n≥2，n∈N+）發(fā)布任務(wù)，服務(wù)提供者wj根據(jù)自身偏好及能力選擇任務(wù)子集TjΓ，并向服務(wù)平臺(tái)遞交任務(wù)競(jìng)標(biāo)二元組Bj=（Tj，bj），其中bj為Tj的競(jìng)標(biāo)值總和。假設(shè)wj獨(dú)立完成Tj，任務(wù)開銷為cj≥0（bj≥cj），且cj和Bj為私有信息，即對(duì)其他服務(wù)提供者是透明的。最后，服務(wù)平臺(tái)通過任務(wù)覆蓋模塊和反拍賣選擇模塊選出優(yōu)勝者集WsW，并將競(jìng)標(biāo)結(jié)果反饋給每個(gè)參選用戶；同時(shí)決定每個(gè)優(yōu)勝者wj的獎(jiǎng)勵(lì)值pj≥bj。在wj完成Tj且向服務(wù)平臺(tái)提交感知數(shù)據(jù)后，服務(wù)平臺(tái)向其支付pj，并在Γ 結(jié)束后，將任務(wù)集的執(zhí)行結(jié)果反饋給服務(wù)請(qǐng)求者。假設(shè)每個(gè)優(yōu)勝者wj（wj∈Ws）會(huì)執(zhí)行Tj，并會(huì)完成Tj中所有任務(wù)τi（τi∈Tj）；同時(shí)感知數(shù)據(jù)的質(zhì)量滿足服務(wù)平臺(tái)要求。

2.2激勵(lì)機(jī)制的特性

定義1服務(wù)提供者效用。服務(wù)提供者wj的效用uj表示為：

uj=xj（pj-cj）（1）

其中：uj為wj的獎(jiǎng)勵(lì)值與開銷的差值，xj代表wj是否為優(yōu)勝者。假設(shè)當(dāng)xj=1時(shí)，表示wj為優(yōu)勝者（wj∈Ws）；當(dāng)xj=0時(shí)，表示wj未贏得任務(wù)競(jìng)拍。

定義2服務(wù)平臺(tái)效用。服務(wù)平臺(tái)的效用U表示為：

U=∑τk∈Tj（Ws）vk-∑wj∈Wspj（2）

其中：U為已完成任務(wù)的獎(jiǎng)勵(lì)設(shè)置值總和與支付給優(yōu)勝者的獎(jiǎng)勵(lì)值總和的差值，Tj（Ws）表示所有優(yōu)勝者任務(wù)子集的并集。假設(shè)服務(wù)平臺(tái)在接受服務(wù)請(qǐng)求者的任務(wù)集Γ之后，并不會(huì)更改任務(wù)τi對(duì)應(yīng)的獎(jiǎng)勵(lì)設(shè)置值vi。

理想激勵(lì)機(jī)制應(yīng)具備一些經(jīng)濟(jì)特性，包括計(jì)算有效、個(gè)人理性、預(yù)算平衡和真實(shí)性[2，8]。然而，服務(wù)請(qǐng)求者可以通過惡意競(jìng)爭(zhēng)方式打破真實(shí)性且實(shí)現(xiàn)個(gè)人理性，即采用競(jìng)標(biāo)值不大于任務(wù)開銷的競(jìng)標(biāo)方式。例如，在MSensing[2]的演算舉例中，用戶w1以b1=8贏得T1={τ1，τ3，τ4，τ5}的競(jìng)標(biāo)，且p1=9。不妨假設(shè)c1=7，可得u1=2。若w1以b1≤7參與競(jìng)標(biāo)，同樣可得p1=9，且u1=2。雖然w1效用沒有直接增加，但是此類競(jìng)標(biāo)方式有效提升了贏得競(jìng)標(biāo)的概率，即間接實(shí)現(xiàn)了效用的增加。惡意競(jìng)爭(zhēng)行為會(huì)嚴(yán)重影響拍賣的公平性，進(jìn)而降低服務(wù)請(qǐng)求者的參與積極性。鑒于此，本文設(shè)計(jì)的激勵(lì)機(jī)制需滿足以下5個(gè)期望特性。

1）計(jì)算有效。一個(gè)機(jī)制是計(jì)算有效的是指該機(jī)制的運(yùn)行可以在一個(gè)多項(xiàng)式時(shí)間內(nèi)完成。

2）個(gè)人理性。如果服務(wù)提供者效用是非負(fù)的，那么該服務(wù)提供者是個(gè)人理性的。

3）預(yù)算平衡。如果服務(wù)平臺(tái)效用是非負(fù)的，那么該服務(wù)平臺(tái)是預(yù)算平衡的。

4）真實(shí)性。一個(gè)機(jī)制是真實(shí)的是指在不管他人競(jìng)標(biāo)值的情況下，沒有一個(gè)服務(wù)提供者可以通過偏離任務(wù)真實(shí)估計(jì)值（任務(wù)開銷）的競(jìng)標(biāo)值增大自身的效用。

5）誠(chéng)實(shí)性。如果服務(wù)提供者的競(jìng)標(biāo)值為自身的真實(shí)預(yù)判值（不小于任務(wù)開銷），那么該服務(wù)提供者是誠(chéng)實(shí)的。

在5個(gè)期望特性中，計(jì)算有效、個(gè)人理性和預(yù)算平衡為3個(gè)基礎(chǔ)特性，用于確保激勵(lì)機(jī)制是可行的；真實(shí)性和誠(chéng)實(shí)性為兩個(gè)關(guān)鍵特性，用于增強(qiáng)機(jī)制的激勵(lì)效果。真實(shí)性可減輕服務(wù)提供者在競(jìng)拍輸贏等方面的擔(dān)憂，Myerson[15]證明了一個(gè)拍賣是真實(shí)的必須滿足選擇規(guī)則是單調(diào)的和優(yōu)勝者的獎(jiǎng)勵(lì)值是關(guān)鍵值兩個(gè)條件：如果服務(wù)提供者以競(jìng)標(biāo)值bj贏得拍賣，那么以競(jìng)標(biāo)值bj′

3激勵(lì)機(jī)制

拍賣理論[2]對(duì)于激勵(lì)機(jī)制設(shè)計(jì)是一種非常好的理論工具。其中，反拍賣是一種逐級(jí)向下競(jìng)價(jià)，以最低價(jià)成交的拍賣方式；Vickrey拍賣[16]是一種密封且以次高價(jià)成交的拍賣方式。本文采用反拍賣與Vickrey拍賣相結(jié)合方式，進(jìn)而提出RVAIM激勵(lì)機(jī)制，即競(jìng)標(biāo)值次低者將贏得拍賣。

3.1激勵(lì)機(jī)制的設(shè)計(jì)

RVAIM的實(shí)現(xiàn)過程包括3個(gè)步驟：任務(wù)覆蓋、反拍賣選擇和獎(jiǎng)勵(lì)實(shí)施。首先，從競(jìng)標(biāo)者數(shù)量ni=1的任務(wù)集中選出優(yōu)勝者集Ws′；其次，從ni≥2的任務(wù)集中選出優(yōu)勝者集Ws″及每個(gè)任務(wù)的競(jìng)標(biāo)勝利者（定義6）；最后，對(duì)優(yōu)勝者集Ws=Ws′∪Ws″中的每個(gè)服務(wù)提供者計(jì)算獎(jiǎng)勵(lì)值。

3.1.1任務(wù)覆蓋

定義3任務(wù)完成。若任務(wù)τi的優(yōu)勝者數(shù)量ni′≥1，則表示該任務(wù)完成。

優(yōu)勝者是被服務(wù)平臺(tái)選定的眾包用戶。若ni′=0，則表示任務(wù)為“無人執(zhí)行”，服務(wù)平臺(tái)只需統(tǒng)計(jì)此類任務(wù)情況并反饋給服務(wù)請(qǐng)求者；若ni′=1，則表示任務(wù)為“一人執(zhí)行”，是任務(wù)完成的最低條件；若ni′≥2，則表示任務(wù)為“多人執(zhí)行”，是任務(wù)完成的理想條件。

定義4任務(wù)覆蓋條件。在競(jìng)標(biāo)者數(shù)量ni=1的任務(wù)τi中，服務(wù)提供者wj成為該任務(wù)的優(yōu)勝者需滿足任務(wù)覆蓋條件，該條件表示為：

bj≤∑Lk=1vk（3）

其中：L表示在任務(wù)子集Tj中的任務(wù)數(shù)量，∑Lk=1vk=Vj表示Tj的總獎(jiǎng)勵(lì)設(shè)置值。

任務(wù)τi有兩種可能為“一人執(zhí)行”情況：1）該任務(wù)只有一個(gè)競(jìng)標(biāo)者wj，且wj滿足任務(wù)覆蓋條件；2）該任務(wù)有多個(gè)參與競(jìng)標(biāo)者，但只有一個(gè)競(jìng)標(biāo)者wj滿足優(yōu)勝者條件（定義5）。為提高任務(wù)完成率，需最大限度保留此類競(jìng)標(biāo)者，下面給出任務(wù)覆蓋算法的簡(jiǎn)要實(shí)現(xiàn)過程。

算法1任務(wù)覆蓋算法（Task Covering Algorithm， TCA）。

程序前

步驟1輸入：Γ，V，Bj，Ws′=；/*輸入任務(wù)集、獎(jiǎng)勵(lì)集及競(jìng)標(biāo)二元組，“”表示空集*/

步驟2根據(jù)Bj=（Tj，bj）統(tǒng)計(jì)用戶參與競(jìng)標(biāo)的任務(wù)集?！浼懊總€(gè)任務(wù)τi的競(jìng)標(biāo)者數(shù)量ni；

步驟3FOR （所有τi∈?！洌?DO

IF （ni=1） THEN

IF （滿足式（3）） THEN

Ws′ ← Ws′∪{wj}；

IF （ni≥2） THEN

轉(zhuǎn)到算法2；

ENDFOR

步驟4輸出Ws′；

步驟5結(jié)束。

程序后

此時(shí)，Ws′是從只有一人競(jìng)標(biāo)的任務(wù)集中選出的優(yōu)勝者集。若wj∈Ws′，考慮wj可能競(jìng)標(biāo)多個(gè)任務(wù)，如果在wj的競(jìng)標(biāo)任務(wù)中包括多人競(jìng)標(biāo)的任務(wù)，則wj仍需要通過反拍賣選擇模塊作進(jìn)一步篩選。

3.1.2反拍賣選擇

在基于反拍賣的激勵(lì)機(jī)制中，服務(wù)平臺(tái)為使自身效用最大化，會(huì)選擇競(jìng)標(biāo)值高而支付獎(jiǎng)勵(lì)值低的服務(wù)提供者，由于此類選擇是典型NPhard（Nondeterministic Polynomial）問題[3]，因此不可能在多項(xiàng)式時(shí)間內(nèi)找到最優(yōu)服務(wù)提供者集。假設(shè)服務(wù)平臺(tái)根據(jù)Vj/bj計(jì)算競(jìng)標(biāo)值，即選擇在單位競(jìng)標(biāo)值上獎(jiǎng)勵(lì)設(shè)置值高的服務(wù)提供者（表示任務(wù)貢獻(xiàn)量大）。同理，服務(wù)平臺(tái)在預(yù)算平衡條件下從候選集W中選出Vj/bj值大且數(shù)量多的服務(wù)提供者是NPhard問題。該問題主要是由于從候選集中直接選擇競(jìng)標(biāo)勝利者集而產(chǎn)生的，為避免此類問題，本文采用一種間接實(shí)現(xiàn)方式，即先利用優(yōu)勝者條件得到每個(gè)任務(wù)的優(yōu)勝者集，再利用競(jìng)標(biāo)勝利者條件對(duì)其進(jìn)行篩選，進(jìn)而得到任務(wù)集的競(jìng)標(biāo)勝利者集。

定義5優(yōu)勝者條件。在競(jìng)標(biāo)者數(shù)量ni≥2的任務(wù)τi中，競(jìng)標(biāo)者wj成為該任務(wù)的優(yōu)勝者需滿足條件為：

∑nik=1bkVk≤1（4）

其中：∑nik=1bkVk表示在任務(wù)τi中每個(gè)競(jìng)標(biāo)者的bj/Vj總和。在反拍賣模塊中，競(jìng)標(biāo)者wj的競(jìng)標(biāo)值通過bj/Vj進(jìn)行計(jì)算，且由小到大進(jìn)行選擇。為最大限度保留“一人執(zhí)行”任務(wù)中的優(yōu)勝者wj，若在該條件的計(jì)算中涉及wj，則wj優(yōu)先進(jìn)行計(jì)算；若此時(shí)任務(wù)τi的優(yōu)勝者數(shù)量ni′=1，由優(yōu)勝者條件可得bj≤Vj，即wj同樣滿足任務(wù)覆蓋條件。

定義6競(jìng)標(biāo)勝利者條件。競(jìng)標(biāo)者wj參選的任務(wù)子集TjΓ，假設(shè)初始Tj內(nèi)的任務(wù)數(shù)為numj，滿足優(yōu)勝者條件的總?cè)蝿?wù)數(shù)為numj′。若numj=numj′，則wj贏得Tj內(nèi)所有任務(wù)的競(jìng)標(biāo)，即wj為競(jìng)標(biāo)勝利者。

在競(jìng)標(biāo)者數(shù)量ni≥2的任務(wù)集中，考慮每個(gè)任務(wù)τi中可能有多個(gè)優(yōu)勝者且只有一個(gè)競(jìng)標(biāo)勝利者，為計(jì)算τi的優(yōu)勝者集Si′，依據(jù)bj/Vj對(duì)τi中每個(gè)競(jìng)標(biāo)者wj進(jìn)行排序；為得到此類任務(wù)集的優(yōu)勝者集Ws″，需依據(jù)勝利者條件對(duì)Si′作進(jìn)一步判斷，以選出τi的最終優(yōu)勝者集Si″，下面給出反拍賣選擇算法的簡(jiǎn)要實(shí)現(xiàn)過程。

算法2反拍賣選擇算法（Reverse Auction Selection Algorithm， RASA）。

程序前

步驟1輸入：Ws″=，Si′=，Si″=；

步驟2IF （ni≥2） THEN/*承接算法1中的步驟3*/

1）Sort（bj/Vj）；/*函數(shù)Sort（bj/Vj）用于對(duì)參數(shù)bj/Vj升序排序*/

2）根據(jù)式（4）計(jì)算Si′ ← Si′∪{wj}；

/*若wj∈Ws′，則wj優(yōu)先進(jìn)行計(jì)算*/

3）FOR （所有wj∈Si′） DO

IF （wj滿足（numj=numj′）） THEN/*優(yōu)勝者條件*/

Si″ ← Si″∪{wj}；

Ws″ ← Ws″∪Si″；

ENDFOR

步驟3計(jì)算每個(gè)任務(wù)Si″中的ji′、 ji″和j*i

1）j′ ← arg min{j|bj/Vj}；

2）j″ ← second_arg min{j|bj/Vj}；

3）j* ← arg max{j|bj/Vj}；

/*函數(shù)second_arg min用于計(jì)算參數(shù)bj/Vj的次低者*/

步驟4輸出Ws″，（ji′， ji″， j*i）；

步驟5結(jié)束。

程序后

3.1.3獎(jiǎng)勵(lì)實(shí)施

依據(jù)Myerson理論[15]，任務(wù)集中的每個(gè)競(jìng)標(biāo)勝利者都應(yīng)得到獎(jiǎng)勵(lì)。目前獎(jiǎng)勵(lì)實(shí)施多數(shù)采用對(duì)任務(wù)集內(nèi)的所有競(jìng)標(biāo)勝利者統(tǒng)一計(jì)算方法，所獲得的獎(jiǎng)勵(lì)值并不能較好反映其任務(wù)中的工作量，影響用戶參與積極性。本文采用依據(jù)任務(wù)逐一計(jì)算獎(jiǎng)勵(lì)值的方法，并區(qū)分優(yōu)勝者類型分別進(jìn)行實(shí)施，其中優(yōu)勝者根據(jù)任務(wù)競(jìng)標(biāo)結(jié)果劃分為兩種類型：競(jìng)標(biāo)勝利者wj（j=j″）和競(jìng)標(biāo)非勝利者wj（j≠j″）。

定義7額外獎(jiǎng)勵(lì)。在“多人執(zhí)行”任務(wù)中，每個(gè)任務(wù)τi為其競(jìng)標(biāo)勝利者wj=j″設(shè)置額外獎(jiǎng)勵(lì)，額外獎(jiǎng)勵(lì)值A(chǔ)τi表示為：

Ati=Vj″·（（bj*/Vj*）-（bj′/Vj′））（5）

其中：bj′/Vj′和bj*/Vj*分別為bj/Vj最低者wj′和最高者wj*的值。Ati可以累加，若wj在Τi中成為競(jìng)標(biāo)勝利者的次數(shù)為j，則wj作為競(jìng)標(biāo)勝利者而得到的總額外獎(jiǎng)勵(lì)值為Aj″=∑jk=1此處也缺少變量名稱，是k=1嗎？請(qǐng)明確。Aτi（τi∈Tj， k∈N+），其中k為Tj中任務(wù)的個(gè)數(shù)。

定義8獎(jiǎng)勵(lì)。服務(wù)平臺(tái)在任務(wù)結(jié)束后對(duì)優(yōu)勝者實(shí)施獎(jiǎng)勵(lì)，優(yōu)勝者wj的獎(jiǎng)勵(lì)值pj表示為：

pj=max{bj，bj+Aj=j″}（6）

由于服務(wù)提供者wj在每個(gè)任務(wù)中的競(jìng)標(biāo)結(jié)果不同，其獎(jiǎng)勵(lì)值也不同：若wj在任務(wù)子集Tj的競(jìng)標(biāo)中全為競(jìng)標(biāo)非勝利者，則pj=bj；反之，若在某些任務(wù)τi（τi∈Tj）中為競(jìng)標(biāo)勝利者，則pj=bj+Aj″。在所有優(yōu)勝者的獎(jiǎng)勵(lì)值計(jì)算結(jié)束后，需要對(duì)服務(wù)平臺(tái)的預(yù)算平衡性進(jìn)行檢驗(yàn)，下面給出獎(jiǎng)勵(lì)實(shí)施算法的簡(jiǎn)要實(shí)現(xiàn)過程。

算法3獎(jiǎng)勵(lì)實(shí)施算法（Reward Implementation Algorithm， RIA）。

程序前

步驟1計(jì)算額外獎(jiǎng)勵(lì)值及總獎(jiǎng)勵(lì)設(shè)置值

FOR （所有τi∈Γ′） DO

/*?！浔硎颈粎⑴c競(jìng)標(biāo)的任務(wù)集，?！洇?/

1）根據(jù)式（5）及（ji′， ji″， j*i）計(jì)算Aτi；/*額外獎(jiǎng)勵(lì)值*/

2）計(jì)算VΓ=∑τi∈Γ′vi；/*VΓ表示任務(wù)集?！涞目偑?jiǎng)勵(lì)設(shè)置值*/

ENDFOR

步驟2計(jì)算優(yōu)勝者的獎(jiǎng)勵(lì)值

Ws=Ws′∪Ws″；

/*Ws表示任務(wù)集?！涞膬?yōu)勝者集*/

FOR （所有wj∈Ws） DO

1）根據(jù)j″統(tǒng)計(jì)wj為競(jìng)標(biāo)勝利者的次數(shù)j；

2）Aj″=∑jk=1Aτi（τi∈Tj， k公式中并未見含有k的變量？如何理解，書寫正確嗎？請(qǐng)明確。∈N+）；/*總額外獎(jiǎng)勵(lì)值*/

3）根據(jù)式（6）計(jì)算獎(jiǎng)勵(lì)值pj；

4）P=∑wj∈Wspj；/*支付總獎(jiǎng)勵(lì)值*/

ENDFOR

步驟3預(yù)算平衡判斷

IF （P>VΓ） THEN

Ws ← ，P ← 0；

ELSE 服務(wù)平臺(tái)啟動(dòng)任務(wù)；

步驟4輸出pj；/*任務(wù)結(jié)束后支付給優(yōu)勝者*/

步驟5結(jié)束。

程序后

3.2演算實(shí)例

3.3有效性分析

為說明RVAIM滿足第2章中設(shè)置的期望特性，分別從計(jì)算有效、個(gè)人理性、預(yù)算平衡、真實(shí)性和誠(chéng)實(shí)性5個(gè)方面給予證明。

引理1RVAIM是計(jì)算有效的。

4實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)從兩個(gè)方面對(duì)RVAIM的性能進(jìn)行評(píng)估：

1）有效性分析。對(duì)比RVAIM與其他激勵(lì)機(jī)制在期望特性方面的性能，作為參照，與IMCSS（Incentive Mechanism for Crowdsourcing in the SSmodel）[8]和MSensing（Myerson Sensing）[2]激勵(lì)機(jī)制進(jìn)行比較。

2）可行性分析?？疾霷VAIM激勵(lì)作用、抑制惡意競(jìng)爭(zhēng)和任務(wù)覆蓋方面的性能。

4.1實(shí)驗(yàn)環(huán)境及參數(shù)設(shè)置

通過Matlab設(shè)計(jì)模擬實(shí)驗(yàn)，實(shí)現(xiàn)了本文中的激勵(lì)模型。為便于比較，使用和文獻(xiàn)[2]和[8]基本相同的實(shí)驗(yàn)環(huán)境和參數(shù)設(shè)置。實(shí)驗(yàn)環(huán)境為Windows 10 PC、Intel Core i7 3.1GHz處理器、8GB內(nèi)存。

模擬實(shí)驗(yàn)中的參數(shù)設(shè)置如表1所示。獎(jiǎng)勵(lì)設(shè)置值、任務(wù)競(jìng)標(biāo)值和競(jìng)標(biāo)任務(wù)數(shù)分別為各自參數(shù)值范圍內(nèi)的隨機(jī)數(shù)。

為驗(yàn)證n的變化情況，假設(shè)m=100；為驗(yàn)證m變化的情況，假設(shè)n=100；為計(jì)算服務(wù)提供者wj的效用，假設(shè)任務(wù)開銷cj=bj/2。實(shí)驗(yàn)運(yùn)行總次數(shù)不低于100次，數(shù)據(jù)結(jié)果取其平均值。

4.2激勵(lì)機(jī)制有效性分析

1）運(yùn)行時(shí)間。首先通過運(yùn)行時(shí)間對(duì)激勵(lì)機(jī)制的計(jì)算有效性進(jìn)行評(píng)估。如圖3（a）所示，隨著m增長(zhǎng)，RVAIM的運(yùn)行時(shí)間近似于O（m2）增長(zhǎng)，而IMCSS和MSensing為線性增長(zhǎng)；如圖3（b）所示，隨著n增長(zhǎng)，3種激勵(lì)機(jī)制的運(yùn)行時(shí)間都近似于O（n2）增長(zhǎng)。總體上，3種激勵(lì)機(jī)制的運(yùn)行時(shí)間比較接近，RVAIM略低于IMCSS是因?yàn)槠浣馑氵^程依據(jù)任務(wù)進(jìn)行，需要對(duì)任務(wù)及競(jìng)標(biāo)者進(jìn)行雙重循環(huán)。

2）服務(wù)提供者平均效用。服務(wù)提供者平均效用通過優(yōu)勝者總效用與優(yōu)勝者數(shù)量之比進(jìn)行計(jì)算，用于評(píng)估激勵(lì)機(jī)制的個(gè)人理性。如圖4所示，RVAIM在服務(wù)提供者平均效用方面優(yōu)于IMCSS和MSensing，這主要是因?yàn)镽VAIM中競(jìng)標(biāo)勝利者的額外獎(jiǎng)勵(lì)A(yù)ti是可以累加的，促使優(yōu)勝者的總效用較大。在圖4（a）中，隨著m增長(zhǎng)，服務(wù)提供者的任務(wù)選擇會(huì)更廣泛，競(jìng)爭(zhēng)性降低導(dǎo)致優(yōu)勝者數(shù)量的不斷增長(zhǎng)，當(dāng)m>n時(shí)，總效用達(dá)到最大。隨著m進(jìn)一步增長(zhǎng)，優(yōu)勝者數(shù)量會(huì)逐漸趨近于n（圖6（a）），且服務(wù)提供者為贏得競(jìng)標(biāo)會(huì)選擇bj/Vj偏小的任務(wù)，這樣優(yōu)勝者總效用會(huì)減少，進(jìn)而出現(xiàn)服務(wù)提供者平均效用降低現(xiàn)象。在圖4（b）中，隨著n增長(zhǎng)，3種激勵(lì)機(jī)制中服務(wù)提供者平均效用都出現(xiàn)下降現(xiàn)象，主要原因是由于優(yōu)勝者數(shù)量保持增長(zhǎng)，而優(yōu)勝者總效用基本保持不變所引起的。

3）服務(wù)平臺(tái)效用。服務(wù)平臺(tái)效用依據(jù)優(yōu)勝者選擇的任務(wù)集進(jìn)行計(jì)算，用于評(píng)估激勵(lì)機(jī)制的預(yù)算平衡特性。在圖5（a）中，3種激勵(lì)機(jī)制中的服務(wù)平臺(tái)效用都隨著m增長(zhǎng)而增長(zhǎng)，這主要是由于服務(wù)提供者選擇任務(wù)范圍的擴(kuò)大，更多任務(wù)會(huì)得到完成。同時(shí)，服務(wù)提供者為增大自身效用，會(huì)選擇獎(jiǎng)勵(lì)設(shè)置值高的任務(wù)，也會(huì)促進(jìn)服務(wù)平臺(tái)效用的增加。在圖5（b）中，3種激勵(lì)機(jī)制中的服務(wù)平臺(tái)效用曲線總體為增長(zhǎng)態(tài)勢(shì)，是由于隨著n增長(zhǎng)，優(yōu)勝者數(shù)量會(huì)增加，任務(wù)集完成率會(huì)不斷提升。當(dāng)任務(wù)集飽和后，由于競(jìng)爭(zhēng)性增強(qiáng)，服務(wù)提供者為贏得競(jìng)標(biāo)，會(huì)傾向于選擇獎(jiǎng)勵(lì)設(shè)置值低的任務(wù)，這將導(dǎo)致RVAIM和IMCSS在初始階段出現(xiàn)緩慢降低現(xiàn)象。同時(shí)，IMCSS持續(xù)偏低是因?yàn)槠湓谌蝿?wù)的選擇上以用戶之間的合作為基礎(chǔ)，導(dǎo)致諸多任務(wù)得不到有效的完成。

4.3激勵(lì)機(jī)制可行性分析

1）激勵(lì)作用。如圖6（a）所示，隨著m增長(zhǎng)，由于服務(wù)提供者選擇任務(wù)競(jìng)爭(zhēng)性的降低，導(dǎo)致優(yōu)勝者數(shù)量增長(zhǎng)并逐漸趨近于n；當(dāng)競(jìng)爭(zhēng)性降低時(shí)，服務(wù)提供者會(huì)選擇獎(jiǎng)勵(lì)設(shè)置值高的任務(wù)，而競(jìng)標(biāo)值會(huì)隨之提高，這將增加競(jìng)標(biāo)失敗的概率，因此出現(xiàn)競(jìng)標(biāo)勝利者數(shù)量逐漸減少現(xiàn)象。在圖6（b）中，隨著n增長(zhǎng)，競(jìng)爭(zhēng)性不斷加強(qiáng)，在任務(wù)集Γ趨向于飽和的過程中，只有少數(shù)競(jìng)標(biāo)條件更低的服務(wù)提供者才能贏得競(jìng)標(biāo)，以致優(yōu)勝者數(shù)量出現(xiàn)緩慢增長(zhǎng)；雖然優(yōu)勝者數(shù)量的增長(zhǎng)會(huì)帶動(dòng)競(jìng)標(biāo)勝利者數(shù)量的增長(zhǎng)，但是當(dāng)競(jìng)標(biāo)者所能承受的競(jìng)標(biāo)值已降至最低時(shí)，競(jìng)標(biāo)勝利者數(shù)量會(huì)進(jìn)入一個(gè)相對(duì)穩(wěn)定狀態(tài)。

2）抑制惡意競(jìng)爭(zhēng)。RVAIM通過真實(shí)性和誠(chéng)實(shí)性抑制惡意競(jìng)爭(zhēng)行為，考慮IMCSS和MSensing在真實(shí)性的實(shí)現(xiàn)方法是一致的，RVAIM僅與MSensing進(jìn)行對(duì)比，如圖7所示。實(shí)驗(yàn)中允許服務(wù)提供者的競(jìng)標(biāo)值偏離任務(wù)開銷，且其效用包括直接效用與間接效用。假設(shè)Τj共有20個(gè)競(jìng)標(biāo)者，其中b1=5，c1=4，p1=10， j″=1，bj′=4，bj*=6，競(jìng)標(biāo)值變化±1將影響贏得競(jìng)標(biāo)的概率為±20%。在圖7（a）中，MSensing的競(jìng)標(biāo)者w1可以通過降低競(jìng)標(biāo)值的惡意競(jìng)爭(zhēng)方式增加間接效用，進(jìn)而增加自身效用，而w1在IMCSS中使用相同惡意競(jìng)爭(zhēng)方式只能實(shí)現(xiàn)效用負(fù)增長(zhǎng)，且無法通過提升競(jìng)標(biāo)值增加自身效用，即IMCSS是真實(shí)的。由圖7（b）可以看出，IMCSS中競(jìng)標(biāo)值的穩(wěn)定性優(yōu)于MSensing，且相對(duì)于最大效用時(shí)的競(jìng)標(biāo)值b=5變化幅度相小，這是因?yàn)镮MCSS根據(jù)每個(gè)任務(wù)僅選擇一個(gè)競(jìng)標(biāo)勝利者，且該任務(wù)的優(yōu)勝者無法通過改變競(jìng)標(biāo)值增大自身效用，導(dǎo)致任務(wù)競(jìng)爭(zhēng)中的競(jìng)標(biāo)值相對(duì)集中，即競(jìng)標(biāo)者僅會(huì)選擇近似于真實(shí)預(yù)判值的競(jìng)標(biāo)值，因此，IMCSS可以有效抑制惡意競(jìng)爭(zhēng)行為。

3）任務(wù)覆蓋。為說明任務(wù)覆蓋模塊的處理效果，僅假設(shè)m=100。在圖8中，初始數(shù)量是指初始任務(wù)集Γ中競(jìng)標(biāo)者數(shù)量ni=1的任務(wù)數(shù)量；任務(wù)覆蓋后數(shù)量是指初始數(shù)量的任務(wù)通過任務(wù)覆蓋模塊后成為“一人執(zhí)行”的任務(wù)數(shù)量；僅符合競(jìng)標(biāo)條件的數(shù)量是指初始數(shù)量的任務(wù)直接通過反拍賣模塊后成為“一人執(zhí)行”的任務(wù)數(shù)量。隨著n增長(zhǎng)，三條曲線均呈現(xiàn)快速下降狀態(tài)，表明競(jìng)標(biāo)者數(shù)量ni=1的任務(wù)隨著競(jìng)標(biāo)者數(shù)量的增長(zhǎng)在迅速減少；當(dāng)n≤200時(shí)，即在任務(wù)集接近于飽和前，任務(wù)覆蓋后數(shù)量持續(xù)保持并近似于初始數(shù)量；同時(shí)明顯高于僅符合競(jìng)標(biāo)條件的數(shù)量，表明任務(wù)覆蓋模塊的作用發(fā)揮是顯著的，即任務(wù)覆蓋模塊在任務(wù)集Γ未飽和前能夠有效提升任務(wù)集的完成率，平均提升約為21%。

通過與IMCSS和MSensing相比，本文方法在計(jì)算有效、個(gè)人理性和預(yù)算平衡方面的性能與IMCSS和MSensing相近，但具有任務(wù)覆蓋范圍廣、激勵(lì)特性全面和抑制惡意競(jìng)爭(zhēng)明顯的優(yōu)點(diǎn)，提高了激勵(lì)機(jī)制的適用性及可靠性。

5結(jié)語

本文針對(duì)現(xiàn)有的眾包激勵(lì)機(jī)制中因任務(wù)沒有適量用戶參與而使任務(wù)無法完成和因任務(wù)競(jìng)爭(zhēng)中缺乏公平性而導(dǎo)致用戶參與積極性低的問題，構(gòu)建了面向任務(wù)覆蓋的反拍賣激勵(lì)模型，并在該模型的基礎(chǔ)上，將反拍賣與Vickrey拍賣進(jìn)行結(jié)合，提出一種基于反拍賣眾包激勵(lì)機(jī)制RVAIM。實(shí)驗(yàn)結(jié)果表明，該機(jī)制不僅能夠有效解決現(xiàn)有激勵(lì)方法中缺乏公平性問題，而且能夠有利于提升眾包服務(wù)完成率，平均可提升約為21%。本文提出的RVAIM為眾包激勵(lì)機(jī)制的設(shè)計(jì)提出了新的設(shè)計(jì)思路，即在服務(wù)平臺(tái)預(yù)算平衡的條件下，綜合考慮服務(wù)平臺(tái)的任務(wù)完成率和服務(wù)提供者的參與積極性，進(jìn)而獲得較好的眾包應(yīng)用效果。

參考文獻(xiàn)：

[1]

JAIMES L G， VERGARALAURENS I J， RAIJ A. A survey on incentive techniques for mobile crowd sensing [J]. IEEE Internet of Things Journal， 2015， 2（5）： 370-380.

[2]

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.

[3]

PHAM H N， SIM B S， YOUN H Y. A novel approach for selecting the participants to collect data in participatory sensing [C]// Proceedings of the IEEE/IPSJ 11th International Symposium on Applications and the Internet. Piscataway， NJ： IEEE， 2011： 50-55.

[4]

WU C， LUO T， WU F， et al. An endorsementbased reputation system for trustworthy crowdsourcing [C]// Proceedings of the 2015 IEEE Conference on Computer Communications Workshops. Piscataway， NJ： IEEE， 2015： 89-90.

[5]

LI Q， CAO G. Providing privacyaware incentives for mobile sensing [C]// Proceedings of the 2013 IEEE International Conference on Pervasive Computing and Communications. Piscataway， NJ： IEEE， 2013： 76-84.

[6]

ZHAO D， LI XY， MA H. How to crowdsource tasks truthfully without sacrificing utility： online incentive mechanisms with budget constraint [C]// Proceedings of the 2014 IEEE Conference on Computer Communications. Piscataway， NJ： IEEE， 2014： 1213-1221.

[7]

GAO L， HOU F， HUANG J. Providing longterm participation incentive in participatory sensing [C]// Proceedings of the 2015 IEEE Conference on Computer Communications. Piscataway， NJ： IEEE， 2015： 2803-2811.

[8]

ZHANG X， XUE G， YU R， et al. Truthful incentive mechanisms for crowdsourcing [C]// Proceedings of the 2015 IEEE Conference on Computer Communications. Piscataway， NJ： IEEE， 2015： 2830-2838.

[9]

WEN Y， SHI J， ZHANG Q， et al. Qualitydriven auction based incentive mechanism for mobile crowd sensing [J]. IEEE Transactions on Vehicular Technology， 2014， 64（9）： 4203-4214.

[10]

LUO T， TAN HP， XIA L. Profitmaximizing incentive for participatory sensing [C]// Proceedings of the 2014 IEEE Conference on Computer Communications. Piscataway， NJ： IEEE， 2014：127-135.

[11]

LEE JS， HOH B. Dynamic pricing incentive for participatory sensing [J]. Pervasive and Mobile Computing， 2010， 6（6）： 693-708.

[12]

DOAN A， RAMAKRISHNAN R， HALEVY A Y. Crowdsourcing systems on the worldwide Web [J]. Communications of the ACM， 2011， 54（4）： 86-96.

[13]

LUO T， THAM CK. Fairness and social welfare in incentivizing participatory sensing [C]// Proceedings of the 9th Annual IEEE Communications Society Conference on Sensor， Mesh and Ad Hoc Communications and Networks. Piscataway， NJ： IEEE， 2012： 425-433.

[14]

GAO H， LIU C， WANG W， et al. A survey of incentive mechanisms for participatory sensing [J]. IEEE Communications Surveys & Tutorials， 2015， 17（2）： 918-943.

[15]

MYERSON R B. Optimal auction design： mathematics of operations research [J]. Mathematics of Operations Research， 1981， 6（1）： 58-73.

[16]

WIKIPEDIA. Vickrey auction [EB/OL]. [20160102]. [20160111]. https：//en.wikipedia.org/wiki/Vickrey_auction.