群智感知中基于反拍賣模型的眾包激勵方法

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

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

關(guān)鍵詞：

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

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

0引言

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

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

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

1相關(guān)研究

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

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

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

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

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

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

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

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

uj=xj（pj-cj）（1）

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

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

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

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

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

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

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

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

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

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

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

3激勵機(jī)制

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

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

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

3.1.1任務(wù)覆蓋

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

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

定義4任務(wù)覆蓋條件。在競標(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的總獎勵設(shè)置值。

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

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

程序前

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

步驟2根據(jù)Bj=（Tj，bj）統(tǒng)計用戶參與競標(biāo)的任務(wù)集Γ′及每個任務(wù)τi的競標(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é)束。

程序后

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

3.1.2反拍賣選擇

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

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

∑nik=1bkVk≤1（4）

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

定義6競標(biāo)勝利者條件。競標(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ù)的競標(biāo)，即wj為競標(biāo)勝利者。

在競標(biāo)者數(shù)量ni≥2的任務(wù)集中，考慮每個任務(wù)τi中可能有多個優(yōu)勝者且只有一個競標(biāo)勝利者，為計算τi的優(yōu)勝者集Si′，依據(jù)bj/Vj對τi中每個競標(biāo)者wj進(jìn)行排序；為得到此類任務(wù)集的優(yōu)勝者集Ws″，需依據(jù)勝利者條件對Si′作進(jìn)一步判斷，以選出τi的最終優(yōu)勝者集Si″，下面給出反拍賣選擇算法的簡要實現(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）用于對參數(shù)bj/Vj升序排序*/

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

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

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

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

Si″ ← Si″∪{wj}；

Ws″ ← Ws″∪Si″；

ENDFOR

步驟3計算每個任務(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用于計算參數(shù)bj/Vj的次低者*/

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

步驟5結(jié)束。

程序后

3.1.3獎勵實施

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

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

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

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

定義8獎勵。服務(wù)平臺在任務(wù)結(jié)束后對優(yōu)勝者實施獎勵，優(yōu)勝者wj的獎勵值pj表示為：

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

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

算法3獎勵實施算法（Reward Implementation Algorithm， RIA）。

程序前

步驟1計算額外獎勵值及總獎勵設(shè)置值

FOR （所有τi∈Γ′） DO

/*Γ′表示被參與競標(biāo)的任務(wù)集，Γ′Γ*/

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

2）計算VΓ=∑τi∈Γ′vi；/*VΓ表示任務(wù)集Γ′的總獎勵設(shè)置值*/

ENDFOR

步驟2計算優(yōu)勝者的獎勵值

Ws=Ws′∪Ws″；

/*Ws表示任務(wù)集Γ′的優(yōu)勝者集*/

FOR （所有wj∈Ws） DO

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

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

3）根據(jù)式（6）計算獎勵值pj；

4）P=∑wj∈Wspj；/*支付總獎勵值*/

ENDFOR

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

IF （P>VΓ） THEN

Ws ← ，P ← 0；

ELSE 服務(wù)平臺啟動任務(wù)；

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

步驟5結(jié)束。

程序后

3.2演算實例

3.3有效性分析

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

引理1RVAIM是計算有效的。

4實驗結(jié)果與分析

實驗從兩個方面對RVAIM的性能進(jìn)行評估：

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

2）可行性分析。考察RVAIM激勵作用、抑制惡意競爭和任務(wù)覆蓋方面的性能。

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

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

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

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

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

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

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

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

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

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

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

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

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

5結(jié)語

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