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

（1. 重慶郵電大學(xué)通信與信息工程學(xué)院，重慶 400065；2. 國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，河南 鄭州 450002；3. 重慶市高校光通信與網(wǎng)絡(luò)重點實驗室，重慶 400065）

1 引言

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

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

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

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

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

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

2 相關(guān)工作

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

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

3 問題定義

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

圖1 基于拍賣模型的移動群智感知網(wǎng)絡(luò)激勵機(jī)制框架

定義1 任務(wù)覆蓋。若任務(wù)τx的贏標(biāo)者數(shù)量numx≥ 1，則表示該任務(wù)被覆蓋，numx= 1 代表有一人執(zhí)行任務(wù)。

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

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

4 基于逆向拍賣的激勵機(jī)制

4.1 IMRA過程問題描述

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

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

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

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

4) 贏標(biāo)者執(zhí)行感知任務(wù)，提交感知數(shù)據(jù)至感知平臺。

5) 感知平臺根據(jù)贏標(biāo)者ui的任務(wù)完成情況對其支付報酬pi。

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

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

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

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

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

4.1.1 贏標(biāo)者選擇問題

定理1 贏標(biāo)者選擇問題為NP-hard問題。

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

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

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

證畢。

4.1.2 報酬支付問題

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

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

4.2 以任務(wù)為中心的贏標(biāo)者選擇算法

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

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

以任務(wù)為中心的贏標(biāo)者選擇算法的偽代碼如算法1所示。

算法1 以任務(wù)為中心的贏標(biāo)者選擇算法

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

輸出贏標(biāo)集S，贏標(biāo)集覆蓋的任務(wù)集?！?，以及任意xτΓ′′∈的競標(biāo)用戶上報的競價與其上報任務(wù)總價值的比值的最小值與最大值

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

1) 根據(jù)Bi=(Γi,bi)統(tǒng)計用戶上報的任務(wù)集?！??！?Γ) ，每一任務(wù)的競標(biāo)用戶集合Uτx及競標(biāo)者數(shù)量ni

11)

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

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

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

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

其中，tx表示完成任務(wù)τx所需要的時間，Δtx表示用戶ui執(zhí)行任務(wù)τx的時間。如果任務(wù)τx的競標(biāo)者僅有用戶ui一人，且競標(biāo)成功，在計算Tτx時用代替式(8)中的?；谂R界價格的報酬支付算法的偽代碼如算法2所示。

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

輸入贏標(biāo)集S，贏標(biāo)集覆蓋的任務(wù)集?！洌约叭我鈞τ?！洹洹?的競標(biāo)用戶上報的競價與其上報任務(wù)總價值的比值的最小值與最大值

輸出報酬支付值pi

初始化pi← 0 ，?！洹洹洹?，?！浔硎颈悔A標(biāo)者完成的任務(wù)集合；

4.4 理論分析

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

引理1 IMRA是計算有效的。

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

證畢。

引理2 IMRA是個體理性的。

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

引理3 IMRA是預(yù)算平衡的。

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

證畢。

引理4 IMRA滿足真實性。

證明分別從單調(diào)性和臨界價格兩方面證明。單調(diào)性：由于將從小到大進(jìn)行排序，若用戶成為贏標(biāo)者，當(dāng)用戶以競標(biāo)時，由于不變，用戶ui同樣可成為贏標(biāo)者。

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

證畢。

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

5 基于用戶交互的雙向競拍機(jī)制

5.1 UBIM過程問題描述

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

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

5.2 基于雙向拍賣的動態(tài)激勵模型

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

在用戶交易的單個時間周期t內(nèi)，對買方用戶與賣方用戶進(jìn)行匹配，以最大化任務(wù)完成率為目標(biāo)，該目標(biāo)可表示為

約束條件為

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

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

5.3 單周期內(nèi)基于節(jié)點度和邊權(quán)值的用戶匹配算法

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

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

算法3 基于節(jié)點度和邊權(quán)值的用戶匹配算法

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

輸出BW(t)，SW(t)

5.4 雙向激勵機(jī)制理論分析

本節(jié)通過理論分析證明設(shè)計的動態(tài)激勵機(jī)制滿足個體理性，激勵相容和計算有效。

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

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

證畢。

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

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

首先，證明其單調(diào)性：假設(shè)n(n≥ 2 )個賣方用戶競標(biāo)買方用戶ub的任務(wù)，在任務(wù)分配中，賣方用

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

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

證畢。

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

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

證畢。

6 實驗驗證與分析

6.1 對比算法

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

6.2 實驗設(shè)置

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

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

表2 IMRA機(jī)制仿真參數(shù)設(shè)置

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

表3 UBIM機(jī)制仿真參數(shù)設(shè)置

6.3 評估指標(biāo)

首先，對本文提出的IMRA機(jī)制與對比方法在用戶平均效用、任務(wù)覆蓋率、任務(wù)完成率和平臺效用這4個方面進(jìn)行比較，然后，對UBIM中提出的動態(tài)激勵機(jī)制從系統(tǒng)效率和社會福利這2個方面進(jìn)行評估。相關(guān)指標(biāo)定義如下。

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

2) 任務(wù)覆蓋率R：定義其中，cov表示被所有贏標(biāo)者覆蓋的任務(wù)數(shù)，m表示總?cè)蝿?wù)數(shù)。

3) 任務(wù)完成率γ：所有贏標(biāo)者完成的任務(wù)數(shù)com與總?cè)蝿?wù)數(shù)m之比，即

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

5) 系統(tǒng)效率μ：完成的請求任務(wù)數(shù)與請求任務(wù)總數(shù)之比，即其中 |BW|表示贏標(biāo)買方的總數(shù)，α表示買方用戶總數(shù)。

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

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

1) 用戶平均效用

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

2) 任務(wù)覆蓋率

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

3) 任務(wù)完成率

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

4) 平臺效用

圖4 用戶平均效用對比

圖5 任務(wù)覆蓋率

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

5) 系統(tǒng)效率

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

6) 社會福利

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

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

圖6 任務(wù)完成率對比

圖7 平臺效用對比

圖8 系統(tǒng)效率對比

圖9 社會福利對比

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

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

7 結(jié)束語

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