基于拍賣模型的移動群智感知網絡激勵機制

劉媛妮，李垚焬，李慧聰，李萬林，張建輝，趙國鋒,3

（1. 重慶郵電大學通信與信息工程學院，重慶 400065；2. 國家數字交換系統工程技術研究中心，河南 鄭州 450002；3. 重慶市高校光通信與網絡重點實驗室，重慶 400065）

1 引言

移動群智感知[1]技術的出現，使人們可以利用大量的智能終端隨時隨地感知和獲取周圍環境信息。在感知數據的過程中，為提高用戶參與感知任務的積極性，需要設計相應的激勵機制[2]，使盡可能多的用戶參與到感知活動中，保證感知任務按時按需完成。目前，移動群智感知的激勵形式根據回報方式主要分為基于金錢式的激勵形式和非金錢式的激勵形式。基于金錢式的激勵形式通過報酬支付的方式回報參與者的感知數據，非金錢式的激勵形式主要包括娛樂游戲的激勵[3-6]、信譽值的激勵機制[7-8]、虛擬積分激勵[9-11]等。針對這些激勵形式，Reddy等[12]指出基于報酬支付的激勵形式效果更好。基于博弈論的方法是報酬支付激勵的主要方式，而拍賣機制則是其核心，如逆向拍賣、組合拍賣、多屬性拍賣、全付拍賣、雙向拍賣等。通常，設計一個合理的基于拍賣模型的激勵機制需要考慮個體理性（individual rationality）、真實性（truthfulness）、社會福利（social welfare）、計算有效性（computation efficiency）等特性[13]。總之，激勵形式研究如何對參與者進行各種形式的報酬激勵、娛樂激勵、精神激勵、榮譽激勵等，以滿足參與者的心理需求，促使其加入感知任務中。

在群智感知中，激勵機制的目標是激勵盡可能多的參與者去執行感知任務，即提高參與率。從時間維度考慮，感知平臺不僅希望參與者參與到感知任務中，還希望其能夠在感知活動中保持參與的長期性。然而，由于參與者的自私性和不確定性，使基于拍賣模型的移動群智感知激勵機制的設計面臨一定的挑戰。自私性在于，移動群智感知中的智能終端用戶受限于設備自身的處理能力、存儲空間、電池能量等，從而不愿意無償地參與感知活動。不確定性在于，參與者的感知能力取決于感知設備的能力、主觀的個人感受等因素，同時人的隨機移動或突發狀況會導致用戶感知活動的中斷，降低任務完成率。進一步地，感知平臺通過招募新的感知用戶來完成被中斷的任務，這種方式將會造成平臺支付成本的增加。為吸引更多的用戶參與，大量的激勵機制[14-19]被提出，然而大多數研究工作[17-19]都假設被選擇執行任務的用戶均能完成感知任務，即任務覆蓋與任務完成為同等概念。針對因人的不確定性而導致的用戶隨機退出的情況，通過設計預防的激勵機制促使用戶在系統中呆得時間更久，較少考慮用戶退出后具體的應對措施。

為了解決上述問題，本文提出了一種基于拍賣模型的移動群智感知網絡激勵機制。首先，為保證激勵機制的真實性，盡可能提高用戶在系統中的感知時間，提出了一種基于逆向拍賣的激勵模型（IMRA, incentive mechanism based on reverse auction），在平臺預算可行的前提下最大化用戶效用，提高用戶參與感知的積極性及任務覆蓋率。進一步地，考慮到用戶不確定性將會導致用戶中途退出、降低任務完成率的問題，提出一種基于用戶雙向交互的激勵機制（UBIM, users’ bidirectional-interaction incentive mechanism），使中途退出的用戶可以將未完成的感知任務轉售給新用戶，盡可能在不增加平臺成本的前提下提高任務完成率。本文的貢獻主要包括以下幾點。

1) 提出了一種基于逆向拍賣的激勵模型IMRA。針對在贏標者選擇過程中，滿足一定覆蓋條件下的用戶選擇是NP-hard問題的情況，提出了一種以任務為中心的贏標者選擇算法，來提高用戶效用和任務覆蓋率，該算法的計算復雜度為多項式時間。在報酬支付階段，采用基于臨界價格的報酬支付算法，根據用戶執行的任務采用按時間比例分享規則對用戶進行任務獎勵，激勵用戶在感知活動中的停留時間，并最大化用戶效用。

2) 針對用戶中途退出的情況，提出了基于用戶雙向交互的激勵模型UBIM，通過設計動態雙向拍賣過程，使臨時退出的感知用戶將未完成的感知任務轉售給新的感知用戶，并針對單周期內用戶匹配問題，提出了基于二部圖的用戶匹配算法，在不增加平臺成本的同時提高任務完成率。

3) 對本文提出的IMRA與文獻[15]中的TRAC（truthful auction for location-aware collaborative sensing in mobile crowdsourcing）機制及文獻[19]中的IMC-SS（incentive mechanism for crowdsourcing in the single-requester single-bid-model）機制分別就用戶平均效用、任務覆蓋率、任務完成率和平臺效應 4個方面進行對比。進一步地，從任務完成率和平臺成本這2個指標對UBIM機理模型的有效性進行了分析。實驗結果表明，本文所提激勵模型IMRA可以有效地提高用戶參與感知的積極性和任務覆蓋率，并且在用戶中途退出的情況下，引入UBIM可以提高感知任務的完成率并降低感知平臺的支付成本。

2 相關工作

為了提高用戶的參與率，許多針對用戶自私性的基于拍賣模型的激勵機制被提出，然而，目前的激勵機制更多地考慮如何使感知平臺的效益最大化[20]（如任務的時空覆蓋率、被完成的任務數量、平臺的預算限制等）。文獻[14]提出了一種用于多請求者MCS（mobile crowd sensing）系統的新型集成框架，該框架中的激勵機制基于雙重拍賣模型進行設置，更符合實際中常見的情況。文獻[15]基于逆向競拍框架設計激勵機制TRAC 時，考慮任務與位置的相關性，用戶根據自身所在的位置和感知范圍，競價多個感知任務，平臺根據匯總的競價來選擇贏標者以最小化支付代價。文獻[21]將數據收集者和中繼用戶的協作視為雙用戶合作博弈問題，提出了利用非對稱納什協商方案，激勵用戶進行感知數據的收集。文獻[16]提出了一種單一的逆向組合的拍賣機制，該機制在拍賣過程中考慮了隱私泄露成本，激勵用戶以真實成本參與競拍以保證激勵機制的真實性。文獻[22]提出了一種在線拍賣機制，在系統壽命中進行多輪拍賣，以優化整個系統生命周期內社會成本。Zhao等[23]考慮用戶在到達時刻向平臺提交競價的場景，通過在每個時間周期內選擇合適的用戶子集達到在預算約束下最大化平臺的效用。文獻[24]為在一定的預算前提下鼓勵用戶完成一組二進制的標記工作，通過連續貝葉斯方法對收集的標記進行聚類，并且基于逆向競拍模型設計激勵機制，最終平臺能在一定預算內實現較高的效用。Luo等[25]提出了一種用于多個合作任務的拍賣機制，在服務器獲得目標價值的情況下最小化服務器的支付。文獻[26]在平臺預算的約束條件下最大多個任務的整體效益。這些研究以最大化平臺效用為首要目的，但沒有優先考慮參與者的效益，無法高效地激勵參與者加入感知任務。從用戶的角度出發，在預算可行的前提下以最大化用戶效用為目標設計激勵機制，會起到更好的激勵作用。

針對用戶不確定性，文獻[27]中指出在參與式感知中，激勵用戶長期參與感知活動是至關重要的。該文獻基于VCG(Vickrey-Clarke-Groves)競拍模型設計激勵機制在線選擇用戶，將參與者的報酬根據時間段分多次進行支付，實現了激勵的長期性。文獻[11]為了在滿足最小化平臺支付代價的同時保證較高的參與率，采用逆向拍賣機制選取出價最低的參與者作為贏家并支付，同時引入虛擬參與積分的概念，避免在競價中屢次失敗的參與者退出。文獻[17]提出了2種激勵模型，分別為以平臺為中心的激勵模型和以用戶為中心的激勵模型，前者通過計算唯一的斯塔克爾伯格均衡，最大化平臺效用，用戶僅依據時間因子進行計算；后者基于逆向拍賣模型設計機制Msensing，相比于前者，Msensing具有用戶上報競價的過程，用戶具有一定的主動權。Zhang等[19]考慮多個用戶競標任務的情形，提出了 SS(single-requester single-bid)模型，在此模型的基礎上提出了IMC-SS機制，該機制由工作組選擇、贏標者選擇和報酬支付這 3個階段組成。Jaimes等[18]設計了基于多輪逆向競拍的激勵機制，鼓勵用戶參與需要連續和定期抽樣的感知計劃。該機制在選擇用戶時不僅考慮了用戶的競價也考慮了用戶的地點，實驗結果表明，該機制在實現最優預算利用率的同時確保感知區域被覆蓋并保證每一輪競拍有足夠的用戶。上述研究大都假設贏得任務的用戶能完成任務并上傳數據，激勵機制的目標是促使用戶在系統中的停留時間更長，并未對贏標者在執行任務的過程中退出感知任務的后續動作提出應對措施。在這種情況下，如果平臺重新招募用戶來繼續執行未完成的感知任務，則需要為新招募的用戶支付報酬，導致平臺感知成本增加。

3 問題定義

本文所提方案的激勵過程如圖1所示。首先，利用基于逆向拍賣的激勵模型IMRA提高用戶效用及任務覆蓋率，并通過設計合理的報酬支付方式，保證激勵機制的真實性。進一步地，針對感知用戶在執行任務過程中需要臨時退出，感知平臺招募新用戶導致其支付成本增加的問題，本文提出基于用戶交互的雙向競拍激勵模型，使中途退出的用戶可以將未完成的感知任務轉售給新的感知用戶，并在不增加平臺成本的前提下保證任務的完成率。本框架只考慮兩輪的感知用戶招募，不再考慮UBIM過程中新用戶繼續退出的情況，即UBIM過程中感知任務的轉售成功則代表該感知任務將會被完成。否則，UBIM過程將會由于第i輪中用戶的退出而被觸發第(i+1)輪的UBIM招募過程，在最壞情況下，該過程可能會被無限循環。考慮基于拍賣模型的移動群智感知網絡中的感知平臺需要從多個用戶中選擇用戶集來滿足感知任務的覆蓋需求。設集合為群智感知平臺發布的感知任務集，m為總任務數，τx∈Γ為任務集中每個單獨的任務，設其開始時間為si，截止時間為di。設用戶完成感知任務τx所需的時間為tx，任務τx的價值為Vx，并且dx-sx≥tx。定義U= {u1,u2,… ,un} 為對任務感興趣的用戶集，用戶ui(i= 1 ,2,… ,n)上報的任務子集為Γi?Γ，用戶競價為bi，定義Bi=(Γi,bi)為用戶ui的任務競價對。參見文獻[15,19]，本文給出以下定義。

圖1 基于拍賣模型的移動群智感知網絡激勵機制框架

定義1 任務覆蓋。若任務τx的贏標者數量numx≥ 1，則表示該任務被覆蓋，numx= 1 代表有一人執行任務。

定義2 賣方用戶。設為圖1中UBIM階段的賣方用戶，即對IMRA階段未被完成的任務感興趣，愿意參與數據感知的用戶。

定義3 買方用戶。設為圖1中UBIM階段的買方用戶，即在IMRA階段中贏得感知任務但在執行任務的過程中臨時退出感知的用戶。

4 基于逆向拍賣的激勵機制

4.1 IMRA過程問題描述

基于逆向拍賣的激勵機制中群智感知平臺與用戶的互動過程如圖2所示，具體步驟如下。

圖2 群智感知平臺與用戶互動過程

表1 本文所用符號及其含義

2) 用戶有休眠和投標這2種決策，用以決定是否參與感知任務。休眠指用戶不參與感知任務，此處通過引入感知任務0，當用戶選擇感知任務0時，即為休眠，其效用為 0。決定投標的用戶ui上報任務競價對Bi=(Γi,bi)，其中，Γi(Γi?Γ)為用戶上報的任務子集，bi為用戶針對該任務子集上報的競價，即用戶ui的逆向競拍價格。

4) 贏標者執行感知任務，提交感知數據至感知平臺。

5) 感知平臺根據贏標者ui的任務完成情況對其支付報酬pi。

用戶ui的效用為其參與感知任務得到的報酬pi與其感知成本ci的差值，即

感知平臺的效用為任務的總價值v(S)與所有贏標者的總報酬支付之間的差值，即

逆向拍賣的問題為，預算有限的前提下，最大化用戶效用，其形式化描述和約束條件為

其中，B為平臺的預算，且B≤v(S)。

由式(3)可知，基于逆向拍賣的激勵機制需解決2個問題：1) 確定拍賣成功的用戶，在最小化社會成本的同時最大化任務覆蓋；2) 設計合理的報酬支付方法，激勵用戶按照其執行感知任務的真實估價進行競價。

4.1.1 贏標者選擇問題

定理1 贏標者選擇問題為NP-hard問題。

證明為了證明此問題是NP-hard問題，首先介紹加權多任務集覆蓋問題的概念，該問題已被Yang 等[28]證明為NP-hard問題。

加權多任務集覆蓋問題的一個實例如下。設有n個子集Y= {Y1,Y2,… ,Yn}，其基本元素為E= {e1,e2,… ,em}，以及正整數K和m元組(w1,w2,… ,wm)。加權多任務集覆蓋問題為判斷是否存在一個包含了K個子集的集合，使每一個元素ex(ex?E)至少被覆蓋的次數為wx。

用戶選擇問題可以轉化為加權多任務集覆蓋問題的一個實例，具體如下。任務集合Γ對應集合E，即任意τj∈Γ對應ej∈E。每一個子集Yi∈Y對應每一個用戶ui∈U上報的任務集iΓ，任務集iΓ中包含的任務對應Yi中的基本元素。每一個元素ex被覆蓋次數至少為wx，則對應為任務jτ至少被wj個用戶覆蓋。這說明加權多任務覆蓋問題能在線性時間內歸約到贏標者選擇問題，即贏標者選擇問題是NP-hard問題的。

證畢。

4.1.2 報酬支付問題

激勵機制需要考慮用戶執行過程的真實性，Myerson[29]證明了一個真實的拍賣機制必須滿足 2個條件，分別選擇規則是單調的和贏標者的獎勵值是臨界價格。單調性即如果用戶以競價bj成為贏標者，那么以仍能成為贏標者，其中代表非真實競標價。臨界價格指的是，如果競標價bj高于臨界價格pj，那么該競標用戶將不會成為贏標者。

因此，對于任意用戶ui，令bi表示用戶對感知成本的真實估價，則任務競價對為用戶的真實競標，將該競標策略下用戶的效用表示為表示用戶的非真實競標，將該競標策略下的用戶效用表示為ui(Bi′)。

4.2 以任務為中心的贏標者選擇算法

針對贏標者選擇NP-hard問題，需要找到一種計算復雜度較低的解決方案。文獻[30]指出，當參加同一感知任務的用戶數量增加時，數據冗余所導致的邊際遞減效應會越發嚴重。因此，在感知任務價值一定的情況下，參與同一任務的用戶越多，每個用戶獲得的報酬越少。本文結合感知數據收集存在邊際遞減效應的現象，假設每個任務由一人執行，在用戶選擇階段，提出以任務為中心的贏標者選擇算法，即對每一個任務，選擇競價與上報的任務總價值的比值最小的用戶作為贏標者。

以任務為中心的贏標者選擇算法的基本思路如下。當任務xτ的競標者數量為1時，若該競標者的競標價bi與上報任務的總價值vi的比值小于 1，則其為任務xτ的贏標者；當任務xτ的競標者數量大于1時，計算每個競標者的競標價bi與其競標任務的總價值vi的比值并升序排列，如式(6)所示。選取比值最小且小于1的競標者作為任務xτ的贏標者。

以任務為中心的贏標者選擇算法的偽代碼如算法1所示。

算法1 以任務為中心的贏標者選擇算法

輸入任務集Γ={τ1,τ2, …,τm}，任務價值集合V= {V1,V2,…,Vm}，用戶任務競價對

輸出贏標集S，贏標集覆蓋的任務集Γ′，以及任意xτΓ′′∈的競標用戶上報的競價與其上報任務總價值的比值的最小值與最大值

初始化S←φ，Γ′′←φ；

1) 根據Bi=(Γi,bi)統計用戶上報的任務集Γ′(Γ′?Γ) ，每一任務的競標用戶集合Uτx及競標者數量ni

11)

4.3 基于臨界價格的報酬支付算法

確定贏標集后，平臺根據用戶的任務完成情況對用戶進行支付，分別考慮用戶正常完成任務和用戶中途退出這2種情況。為了保證激勵的真實性并激勵用戶長時間參與，根據文獻[29]中臨界價格的概念，提出了一種基于臨界價格的報酬支付算法。

考慮用戶正常完成任務和用戶中途退出這2種情況下的支付，在考慮用戶競價bi的同時根據用戶執行的任務采用按時間比例分享規則對用戶進行任務獎勵Tτx。具體地，用戶的支付函數為

其中，Γi′表示用戶ui贏得的任務集合，τx∈Γi′，Tτx表示用戶執行任務τx后得到的任務報酬。Tτx計算式如式(8)所示。

其中，tx表示完成任務τx所需要的時間，Δtx表示用戶ui執行任務τx的時間。如果任務τx的競標者僅有用戶ui一人，且競標成功，在計算Tτx時用代替式(8)中的。基于臨界價格的報酬支付算法的偽代碼如算法2所示。

算法2 基于臨界價格的報酬支付算法

輸入贏標集S，贏標集覆蓋的任務集Γ′，以及任意xτΓ′′∈ 的競標用戶上報的競價與其上報任務總價值的比值的最小值與最大值

輸出報酬支付值pi

初始化pi← 0 ，Γ′′′←φ，Γ′表示被贏標者完成的任務集合；

4.4 理論分析

根據文獻[24]所述，一個可行且有效的競拍機制需滿足計算有效、個體理性、預算平衡和真實性（即激勵相容）4個特性，下面將對IMRA這4個特性進行理論分析。

引理1 IMRA是計算有效的。

證明算法1中的for循環（算法1中2)～16)）的時間復雜度為O(m)，算法 1中 9)的排序算法的時間復雜度為O(nlogn)，因此，算法1的時間復雜度為O(mnlogn), 即算法 1的時間復雜度為多項式時間。算法2中的第一個for循環（算法2中1)～7)）的時間復雜度為O(m)，第二個for循環（算法2中8)～12)）的時間復雜度為O(n)，因此，算法2的時間復雜度為O(n)，即算法2的時間復雜度為多項式時間。綜上所述，IMRA的時間復雜度為多項式時間，即IMRA是計算有效的。

證畢。

引理2 IMRA是個體理性的。

證明若用戶ui競標失敗，其則；若用戶ui競標成功，其則。綜上，用戶效用大于0，滿足個體理性。證畢。

引理3 IMRA是預算平衡的。

證明算法 2中 13)～15)保證，當支付的報酬不大于完成任務的總價值時，才會啟動任務，此時，平臺效用大于或等于 0，否則任務啟動失敗，平臺效用為0，因此該機制滿足預算平衡。

證畢。

引理4 IMRA滿足真實性。

證明分別從單調性和臨界價格兩方面證明。單調性：由于將從小到大進行排序，若用戶成為贏標者，當用戶以競標時，由于不變，用戶ui同樣可成為贏標者。

臨界價格：假設參與競標任務xτ的用戶數不小于2，用戶ui以競價bi成為贏標者，則其支付如果用戶ui以大于pi的值作為競標價，那么則因可得那么用戶u將不能贏得任務τ，故ix若用戶以大于pi的值作為競標價將不會成為贏標者，因此，該機制滿足激勵相容特性。

證畢。

綜上所述，IMRA滿足計算有效、個體理性、預算平衡和真實性。

5 基于用戶交互的雙向競拍機制

5.1 UBIM過程問題描述

基于用戶交互的雙向競拍機制（UBIM）的交互過程如圖3所示。該交互過程有3個交互主體，分別為買方用戶賣方用戶和感知平臺，具體交互過程如下。首先，需要中途退出的買方用戶即感知數據請求方在平臺發布感知任務需求，賣方用戶即感知數據提供方在得知具體的任務需求后，向感知平臺提交感知計劃。假設用戶交易的總時間周期為T，即t= 1,2,3,…,T。每一個用戶有其特定的感知類型為用戶到達和離開的時間，并且假設用戶的最大到達-離開時間間隔為I，稱之為最大等待耐心。對于買方用戶wi=bi，為買方用戶對感知數據的競價，表示不高于此價購買感知數據，對于賣方用戶wj=sj，為賣方用戶對感知數據的要價，表示不低于此價賣出感知數據。在每個時間周期t內，買方用戶和賣方用戶通過用戶匹配策略進行匹配，確定贏標者。贏標買方用戶將贏標賣方用戶推薦給平臺，賣方用戶將感知數據發送給平臺，完成感知任務后，贏標買方向將平臺原先支付給買方用戶的報酬支付給賣方用戶，向贏標賣方支付報酬pi。因此，買方效用為賣方效用為

圖3 基于用戶交互的雙向競拍機制交互過程

5.2 基于雙向拍賣的動態激勵模型

雙向拍賣機制的主要思想如下。假設總拍賣周期為T，即t= 1,2,3,…,T，在每個周期t內，分別將到達的買方用戶和賣方用戶加入集合B(t)和S(t)中。在拍賣階段，通過設計匹配規則選擇出贏標買方用戶集BW(t)和贏標賣方用戶集SW(t)。進一步地，為提高用戶參與競拍的積極性，對于未進入贏標集而其離開時間di＞t的用戶可作為生存者進入下一周期，根據文獻[31]，令SNTB(t)和SNTS(t)分別表示周期t內的買方生存者和賣方生存者，否則，未進贏標集的用戶為失效者，不能再參與競拍，將其加入集合h(t)內。

在用戶交易的單個時間周期t內，對買方用戶與賣方用戶進行匹配，以最大化任務完成率為目標，該目標可表示為

約束條件為

其中，式(9)表示激勵目標是完成盡可能多的感知任務，以提高任務完成率。若買方用戶與賣方用戶匹配成功，式(11)與式(12)分別表示在周期t內任意一個買方用戶或賣方用戶至多可與一個賣方用戶或買方用戶匹配成功。當時，表示欲中途退出的用戶通過第二輪的招募將其感知任務成功轉售給，即參與第一輪招募的感知用戶退出后，其未完成的任務將由負責完成。此處不再考慮第二輪用戶的退出導致任務無法被完成再進行第三輪甚至后續第N(N→∞)輪的新用戶招募的無限循環的過程。因此，可以假設在第二

文獻[32]證明，一種雙向拍賣機制雖然不可能同時滿足計算有效、個體理性、預算平衡和真實性這4個特性，但可以滿足其中的部分屬性，其中，個體理性、預算平衡和真實性3種屬性是雙向拍賣機制可信性和有效性的基本保證。此外，設計的機制需滿足計算有效，即在單個時間周期內用戶的匹配可在多項式時間內輸出結果。

5.3 單周期內基于節點度和邊權值的用戶匹配算法

多用戶匹配問題可以被看作二部圖(V,E)的一對一匹配問題，其中，V表示買賣雙方，E表示用戶的競標情況。若買方用戶與賣方用戶有邊相連則表示賣方用戶對買方所持有的任務進行了競標。用戶匹配問題可運用整數規劃方法進行描述, 由于式(11)～式(13)的限制，式(9)可以簡化為 0-1 規劃問題。0-1規劃問題已被證明為是NP完全問題[33]，因此，用戶匹配問題為NP完全問題。

在基于節點度和邊權值的用戶匹配算法中，為保證較高的任務完成率，將買方節點按節點的度升序排列，節點度低的優先匹配。在匹配過程中，每條邊有一個權值W=bi-sj，為使所有參與者效用總和最大，將權值最大且不小于0的邊對應的用戶作為贏標者。設B(t)與S(t)分別表示在周期t內到達的買方用戶集和賣方用戶集，|B(t)|和|S(t)|分別表示用戶集B(t)中買方用戶數和用戶集S(t)中賣方用戶數，BW(t)和SW(t)分別表示在周期t內的贏標買方用戶集和贏標賣方用戶集。基于節點度和邊權值的用戶匹配算法的偽代碼如算法3所示。用戶匹配成功后，為保證激勵的真實性，在交易中，定義交易

算法3 基于節點度和邊權值的用戶匹配算法

輸入B(t)，S(t)，V=B(t) ∪S(t)

輸出BW(t)，SW(t)

5.4 雙向激勵機制理論分析

本節通過理論分析證明設計的動態激勵機制滿足個體理性，激勵相容和計算有效。

引理5 本文提出的動態激勵方法滿足個體理性。

證明對于任意一個買方用戶ub∈ub，若其沒i有成為贏標者，其效用u(uib) = 0 ，若其被選為贏標者，其效用因此，對于任意一個買方其效用。綜上所述，對于任意一個買方用戶，本文提出的動態激勵算法是個體理性的。

證畢。

引理6 本文的雙向拍賣算法是激勵相容的。

證明當且僅當以下條件被滿足時，拍賣算法是激勵相容的：1) 其任務分配方法是單調的；2) 每個競拍成功的用戶都得到了臨界價格的報酬。

首先，證明其單調性：假設n(n≥ 2 )個賣方用戶競標買方用戶ub的任務，在任務分配中，賣方用

i戶贏得感知任務，若其以競標，且因為bi不變，則賣方用戶同樣可贏得任務。

其次，證明每個贏標者都支付(得到)了臨界價格：對于任意一個以競價sj贏得任務的賣方用戶對其支付若用戶以大于p的值i作為競價，那么有則由成為贏標者的基本條件bi≥sj可知用戶將不會成為贏標者，因此，每個賣方用戶都得到了臨界價格。同理可證，每個買方都支付了臨界價格。

證畢。

引理7 本文的雙向拍賣算法是計算有效的。

證明算法3中1) 的排序算法時間復雜度為O(|B(t) |log|B(t) |)，for循環（算法 3中 2)～14)）的時間復雜度為O(|B(t) ||S(t) |log|S(t) |)，因此算法3的時間復雜度為O(|B(t) ||S(t) |log|S(t) |)。由算法3的時間復雜度的分析，可得出在線競拍算法的時間復雜度為O(T|B(t) |(|B(t) |+|S(t) |log|S(t)|))。因此，動態激勵方法可在多項式時間內輸出結果。

證畢。

6 實驗驗證與分析

6.1 對比算法

為了驗證本文所提IMRA機制的性能，將其分別與文獻[15]中的TRAC（truthful auction for location-aware collaborative sensing in mobile crowdsourcing）機制及文獻[19]中的 IMC-SS（incentive mechanism for crowdsourcing in the single-requester single-bid-model）機制進行對比。進一步地，通過實驗對比，分別使用UBIM招募用戶與使用IMRA機制時平臺招募新用戶下的任務完成率和平臺成本這2個指標，來分析本文雙向激勵機制的有效性。

6.2 實驗設置

具體實驗場景為感知平臺發布 100個感知任務，且移動群智感知系統中有500個用戶對任務感興趣，首先通過IMRA機制激勵用戶參與感知，然后對于贏標用戶未完成的任務平臺分別直接招募用戶或采用UBIM機制招募用戶參與。

為驗證IMRA機制的有效性與可行性，根據文獻[23,19]，設置感知任務的成本和價值均服從均勻分布。假設中途退出的用戶數占總用戶數的比例為p( 0 ≤p≤ 1) ，若用戶中途退出，則定義其執行任務的時間與完成任務所需時間的比值服從（0,1）均勻分布。IMRA機制仿真參數設置如表2所示。

表2 IMRA機制仿真參數設置

進一步地，為了驗證基于雙向拍賣的動態激勵機制的有效性和可行性，進行仿真實驗，實驗參數如表3所示。假設用戶的等待耐心為I，拍賣總周期T=100，根據文獻[15,22]，設置買賣雙方的報價服從(0,5]均勻分布，單位時間內用戶的到達次數服從泊松分布，到達率為λ，最大等待耐心與到達率的值分別設置為6和10[33]。在激勵用戶參與未被完成的任務時，分別對比了競標用戶數為{10, 20, 30,40, 50, 60, 70, 80, 90, 100}的仿真結果。

表3 UBIM機制仿真參數設置

6.3 評估指標

首先，對本文提出的IMRA機制與對比方法在用戶平均效用、任務覆蓋率、任務完成率和平臺效用這4個方面進行比較，然后，對UBIM中提出的動態激勵機制從系統效率和社會福利這2個方面進行評估。相關指標定義如下。

1) 用戶平均效用：所有贏標者的總效用與贏標者數量的比值，即其中，|S|為贏標者的數量。

2) 任務覆蓋率R：定義其中，cov表示被所有贏標者覆蓋的任務數，m表示總任務數。

3) 任務完成率γ：所有贏標者完成的任務數com與總任務數m之比，即

4) 平臺效用：評估激勵方法預算是否可行的重要評估指標，可根據式(2)進行計算。

5) 系統效率μ：完成的請求任務數與請求任務總數之比，即其中 |BW|表示贏標買方的總數，α表示買方用戶總數。

6)社會福利：所有參與者的效用之和，即

6.4 實驗結果與分析

1) 用戶平均效用

圖4顯示了IMRA和TRAC、IMC-SS的用戶平均效用對比。在圖4(a)中，對于IMRA而言，當任務數較少時，用戶間較強的競爭使贏標者數量較少，任務支付集中在少數用戶，因此，用戶平均效用較高。隨著任務數的增加，用戶的選擇更加廣泛，競爭性降低使贏標用戶數增加，而能被用戶完成的任務的總價值趨于穩定，進而用戶平均效用降低。在圖4(b)中，隨著用戶數的增加，用戶完成的任務數增加，總任務支付增加使用戶平均效用隨之上升。當用戶數的增加使用戶完成的任務數達到飽和時，用戶的平均效用趨于平衡。相較于 TRAC和 IMC-SS而言，TRAC機制與IMC-SS機制的報酬支付只與其競價和任務數相關，而IMRA中任務支付的累加效用使用戶可得到相對較高的任務補償，提高了用戶參與感知任務的積極性。

2) 任務覆蓋率

圖5顯示了3種激勵機制下的任務覆蓋率。從圖5中可以看出，IMC-SS下的任務覆蓋率略低于IMRA下的任務覆蓋率，而當用戶數接近或小于任務數時，TRAC下的任務覆蓋率較低，其原因在于TRAC在贏標者選擇階段貪婪地選擇競價低、上報任務數多的用戶，而在報酬支付階段需找到能包含被支付用戶任務集的用戶。當TRAC在用戶數接近或小于任務數時，很難找到滿足條件的用戶對贏標者進行支付，導致用戶支付失敗，進而出現任務覆蓋率較低的現象。結合用戶效用和任務覆蓋情況，可得，相比TRAC和IMC-SS機制，IMRA下用戶的積極性較高。

3) 任務完成率

圖 6為感知任務完成率的對比。TRAC和IMC-SS這2種機制均假設任務覆蓋即任務完成，因此，其任務完成率與其任務覆蓋率變化趨勢相同，而IMRA考慮用戶的隨機性導致用戶在執行任務時中途退出，造成感知任務未被完成的情況。從圖6(a)中可看出，當用戶數為100時，隨著任務數的增加，3種機制下的任務完成率均呈上升趨勢，且當任務數為10～60時，IMRA下的任務完成率低于TRAC和IMC-SS下的任務完成率。在圖6(b)中，當任務數為 100時，隨著用戶數的增加，TRAC和IMC-SS下的任務完成率都趨近于100%，而在考慮了用戶執行任務過程中可能會中途退出的IMRA下，總有任務未被完成。由此可看出，用戶的隨機性對任務完成會產生影響。

4) 平臺效用

圖4 用戶平均效用對比

圖5 任務覆蓋率

圖7是群智感知平臺效用的對比。從圖7(a)中可以看出，在用戶數固定時，IMRA和IMC-SS下的平臺效用隨著任務數的增加而增加，并且，相比于IMC-SS，IMRA平臺效用較低，原因有2個：① 用戶的中途退出使得任務未被完成，導致被完成的任務的總價值較低；② 此激勵方法下用戶的報酬支付較高。TRAC下，平臺效用隨著任務數的增加先增加后減少，主要原因在于其在用戶數接近或小于任務數時，任務完成率較低。在圖7(b)中，3種激勵方法的平臺效用為先增加后趨于穩定，是由于隨著用戶數的增長，任務完成率增加，當任務集飽和后，平臺效用不再增加。

5) 系統效率

系統效率為匹配成功的買方用戶數與總買方用戶數之比，反映了感知任務完成率。從圖8(a)可以看出，隨著賣方用戶數的增多，使更多的供給產生更多的選擇，對于買方用戶來說，可以滿足更多的需求，導致更高的系統效率。最后，系統效率的增長速度減慢并趨于穩定，原因是當賣方用戶數穩定時，大部分的買方用戶已經完成了交易，額外的賣方用戶對系統效率貢獻較少。如圖8(b)所示，當拍賣的買賣雙方總數分別為50、100和150時，系統效率隨著等待耐心的增加而增加，原因在于更高的等待耐心將促成更多的買方用戶與賣方用戶匹配成功。從圖8(c)可以看出，系統效率隨著到達率的增加而增加，這是因為更高的到達率將促成更多的競價與要價匹配成功。

6) 社會福利

社會福利反映了經濟效率。如圖 9(a)所示，隨著買方用戶數或賣方用戶數的增加，都會導致社會福利的增加，這是因為更多的用戶會增加競價與要價匹配成功的概率。從圖 9(b)可以看出，當買賣雙方總數分別為50、100和500時，社會福利隨著等待耐心的增加而增加，這是因為更高的等待耐心將促成更多的競價與要價匹配成功。如圖 9(c)所示，社會福利隨著到達率的增加而增加，原因在于隨著到達率的增加將促成更多的競價與要價匹配成功。

7) 未完成任務情況下不同方法的性能對比

圖6 任務完成率對比

圖7 平臺效用對比

圖8 系統效率對比

圖9 社會福利對比

圖10 未完成任務情況下不同方法的性能對比

由圖10(a)可以看出，不論是通過IMRA機制還是通過UBIM機制激勵，用戶參與未被完成的感知任務，均能獲得較高的任務完成率。圖10(b)展示了采用2種不同的機制激勵用戶參與未被完成的任務下的平臺成本，可以看出，對于IMRA機制，平臺成本隨著競標用戶數的增加而增加，相比之下，在UBIM機制下平臺成本較低。

7 結束語

針對移動群智感知網絡中用戶參與感知活動時因自私性、不確定性而導致用戶參與感知活動的積極性不高及用戶中斷感知活動的問題，本文提出基于拍賣模型的激勵機制。首先，從用戶的角度出發，以最大化用戶效用為目的，提出了一種基于逆向拍賣的激勵機制IMRA。在IMRA階段中，提出多項式時間復雜度的用戶選擇算法，并采用按時間比例分享規則的報酬支付方法，在保證激勵真實性的同時提高了用戶效用。其次，針對用戶中途退出的問題，提出基于用戶交互的激勵機制UBIM，通過買方用戶和賣方用戶之間的雙向競拍，使買方用戶可以將未完成的感知任務轉售給賣方用戶，并提出了一種基于節點度和邊權值的用戶匹配算法，提高感知任務完成率和社會福利。最后，理論及實驗分析表明，本文的激勵機制有效地提高了用戶平均效用和任務覆蓋率，并且可以使平臺在一定的成本預算約束的情況下獲得較高的任務完成率。在未來的工作中，將會進一步探索各種不確定因素與用戶退出的隨機性之間的確定性關系模型，如探索電量不足導致用戶退出的隨機性將會服從何種分布，用戶主觀感知決策的變化導致退出的隨機性將會服從何種分布等。另外，在仿真的過程中僅考慮了感知任務的成本、用戶的報價為均勻分布情況下與其他方案的對比，后續將會引入正態分布和指數分布下的對比分析。