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

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

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

關鍵詞：

群智感知；眾包；激勵機制；反拍賣；Vickrey拍賣

中圖分類號： TP181 文獻標志碼：A

0引言

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

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

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

1相關研究

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

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

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

2面向任務覆蓋的反拍賣激勵模型

2.1構建激勵模型

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

2.2激勵機制的特性

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

uj=xj（pj-cj）（1）

其中：uj為wj的獎勵值與開銷的差值，xj代表wj是否為優勝者。假設當xj=1時，表示wj為優勝者（wj∈Ws）；當xj=0時，表示wj未贏得任務競拍。

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

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

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

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

1）計算有效。一個機制是計算有效的是指該機制的運行可以在一個多項式時間內完成。

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

3）預算平衡。如果服務平臺效用是非負的，那么該服務平臺是預算平衡的。

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

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

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

3激勵機制

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

3.1激勵機制的設計

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

3.1.1任務覆蓋

定義3任務完成。若任務τi的優勝者數量ni′≥1，則表示該任務完成。

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

定義4任務覆蓋條件。在競標者數量ni=1的任務τi中，服務提供者wj成為該任務的優勝者需滿足任務覆蓋條件，該條件表示為：

bj≤∑Lk=1vk（3）

其中：L表示在任務子集Tj中的任務數量，∑Lk=1vk=Vj表示Tj的總獎勵設置值。

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

算法1任務覆蓋算法（Task Covering Algorithm， TCA）。

程序前

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

步驟2根據Bj=（Tj，bj）統計用戶參與競標的任務集?！浼懊總€任務τi的競標者數量ni；

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

IF （ni=1） THEN

IF （滿足式（3）） THEN

Ws′ ← Ws′∪{wj}；

IF （ni≥2） THEN

轉到算法2；

ENDFOR

步驟4輸出Ws′；

步驟5結束。

程序后

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

3.1.2反拍賣選擇

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

定義5優勝者條件。在競標者數量ni≥2的任務τi中，競標者wj成為該任務的優勝者需滿足條件為：

∑nik=1bkVk≤1（4）

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

定義6競標勝利者條件。競標者wj參選的任務子集TjΓ，假設初始Tj內的任務數為numj，滿足優勝者條件的總任務數為numj′。若numj=numj′，則wj贏得Tj內所有任務的競標，即wj為競標勝利者。

在競標者數量ni≥2的任務集中，考慮每個任務τi中可能有多個優勝者且只有一個競標勝利者，為計算τi的優勝者集Si′，依據bj/Vj對τi中每個競標者wj進行排序；為得到此類任務集的優勝者集Ws″，需依據勝利者條件對Si′作進一步判斷，以選出τi的最終優勝者集Si″，下面給出反拍賣選擇算法的簡要實現過程。

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

程序前

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

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

1）Sort（bj/Vj）；/*函數Sort（bj/Vj）用于對參數bj/Vj升序排序*/

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

/*若wj∈Ws′，則wj優先進行計算*/

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

IF （wj滿足（numj=numj′）） THEN/*優勝者條件*/

Si″ ← Si″∪{wj}；

Ws″ ← Ws″∪Si″；

ENDFOR

步驟3計算每個任務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}；

/*函數second_arg min用于計算參數bj/Vj的次低者*/

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

步驟5結束。

程序后

3.1.3獎勵實施

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

定義7額外獎勵。在“多人執行”任務中，每個任務τi為其競標勝利者wj=j″設置額外獎勵，額外獎勵值Aτi表示為：

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

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

定義8獎勵。服務平臺在任務結束后對優勝者實施獎勵，優勝者wj的獎勵值pj表示為：

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

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

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

程序前

步驟1計算額外獎勵值及總獎勵設置值

FOR （所有τi∈?！洌?DO

/*Γ′表示被參與競標的任務集，?！洇?/

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

2）計算VΓ=∑τi∈?！鋠i；/*VΓ表示任務集?！涞目偑剟钤O置值*/

ENDFOR

步驟2計算優勝者的獎勵值

Ws=Ws′∪Ws″；

/*Ws表示任務集?！涞膬瀯僬呒?/

FOR （所有wj∈Ws） DO

1）根據j″統計wj為競標勝利者的次數j；

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

3）根據式（6）計算獎勵值pj；

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

ENDFOR

步驟3預算平衡判斷

IF （P>VΓ） THEN

Ws ← ，P ← 0；

ELSE 服務平臺啟動任務；

步驟4輸出pj；/*任務結束后支付給優勝者*/

步驟5結束。

程序后

3.2演算實例

3.3有效性分析

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

引理1RVAIM是計算有效的。

4實驗結果與分析

實驗從兩個方面對RVAIM的性能進行評估：

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

2）可行性分析?？疾霷VAIM激勵作用、抑制惡意競爭和任務覆蓋方面的性能。

4.1實驗環境及參數設置

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

模擬實驗中的參數設置如表1所示。獎勵設置值、任務競標值和競標任務數分別為各自參數值范圍內的隨機數。

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

4.2激勵機制有效性分析

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

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

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

4.3激勵機制可行性分析

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

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

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

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

5結語

本文針對現有的眾包激勵機制中因任務沒有適量用戶參與而使任務無法完成和因任務競爭中缺乏公平性而導致用戶參與積極性低的問題，構建了面向任務覆蓋的反拍賣激勵模型，并在該模型的基礎上，將反拍賣與Vickrey拍賣進行結合，提出一種基于反拍賣眾包激勵機制RVAIM。實驗結果表明，該機制不僅能夠有效解決現有激勵方法中缺乏公平性問題，而且能夠有利于提升眾包服務完成率，平均可提升約為21%。本文提出的RVAIM為眾包激勵機制的設計提出了新的設計思路，即在服務平臺預算平衡的條件下，綜合考慮服務平臺的任務完成率和服務提供者的參與積極性，進而獲得較好的眾包應用效果。

參考文獻：

[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.