基于拍賣(mài)模型的移動(dòng)群智感知網(wǎng)絡(luò)激勵(lì)機(jī)制

劉媛妮，李垚焬，李慧聰，李萬(wàn)林，張建輝，趙國(guó)鋒,3

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

1 引言

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

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

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

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

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

3) 對(duì)本文提出的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ī)制分別就用戶(hù)平均效用、任務(wù)覆蓋率、任務(wù)完成率和平臺(tái)效應(yīng) 4個(gè)方面進(jìn)行對(duì)比。進(jìn)一步地，從任務(wù)完成率和平臺(tái)成本這2個(gè)指標(biāo)對(duì)UBIM機(jī)理模型的有效性進(jìn)行了分析。實(shí)驗(yàn)結(jié)果表明，本文所提激勵(lì)模型IMRA可以有效地提高用戶(hù)參與感知的積極性和任務(wù)覆蓋率，并且在用戶(hù)中途退出的情況下，引入U(xiǎn)BIM可以提高感知任務(wù)的完成率并降低感知平臺(tái)的支付成本。

2 相關(guān)工作

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

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

3 問(wèn)題定義

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

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

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

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

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

4 基于逆向拍賣(mài)的激勵(lì)機(jī)制

4.1 IMRA過(guò)程問(wèn)題描述

基于逆向拍賣(mài)的激勵(lì)機(jī)制中群智感知平臺(tái)與用戶(hù)的互動(dòng)過(guò)程如圖2所示，具體步驟如下。

圖2 群智感知平臺(tái)與用戶(hù)互動(dòng)過(guò)程

表1 本文所用符號(hào)及其含義

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

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

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

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

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

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

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

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

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

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

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

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

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

證畢。

4.1.2 報(bào)酬支付問(wèn)題

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

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

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

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

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

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

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

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

輸出贏標(biāo)集S，贏標(biāo)集覆蓋的任務(wù)集Γ′，以及任意xτ?！洹洹实母?jìng)標(biāo)用戶(hù)上報(bào)的競(jìng)價(jià)與其上報(bào)任務(wù)總價(jià)值的比值的最小值與最大值

初始化S←φ，?！洹洹眨?/p>

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

11)

4.3 基于臨界價(jià)格的報(bào)酬支付算法

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

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

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

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

算法2 基于臨界價(jià)格的報(bào)酬支付算法

輸入贏標(biāo)集S，贏標(biāo)集覆蓋的任務(wù)集?！?，以及任意xτ?！洹洹?的競(jìng)標(biāo)用戶(hù)上報(bào)的競(jìng)價(jià)與其上報(bào)任務(wù)總價(jià)值的比值的最小值與最大值

輸出報(bào)酬支付值pi

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

4.4 理論分析

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

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

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

證畢。

引理2 IMRA是個(gè)體理性的。

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

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

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

證畢。

引理4 IMRA滿足真實(shí)性。

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

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

證畢。

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

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

5.1 UBIM過(guò)程問(wèn)題描述

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

圖3 基于用戶(hù)交互的雙向競(jìng)拍機(jī)制交互過(guò)程

5.2 基于雙向拍賣(mài)的動(dòng)態(tài)激勵(lì)模型

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

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

約束條件為

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

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

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

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

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

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

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

輸出BW(t)，SW(t)

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

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

引理5 本文提出的動(dòng)態(tài)激勵(lì)方法滿足個(gè)體理性。

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

證畢。

引理6 本文的雙向拍賣(mài)算法是激勵(lì)相容的。

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

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

i戶(hù)贏得感知任務(wù)，若其以競(jìng)標(biāo)，且因?yàn)閎i不變，則賣(mài)方用戶(hù)同樣可贏得任務(wù)。

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

證畢。

引理7 本文的雙向拍賣(mài)算法是計(jì)算有效的。

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

證畢。

6 實(shí)驗(yàn)驗(yàn)證與分析

6.1 對(duì)比算法

為了驗(yàn)證本文所提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)行對(duì)比。進(jìn)一步地，通過(guò)實(shí)驗(yàn)對(duì)比，分別使用UBIM招募用戶(hù)與使用IMRA機(jī)制時(shí)平臺(tái)招募新用戶(hù)下的任務(wù)完成率和平臺(tái)成本這2個(gè)指標(biāo)，來(lái)分析本文雙向激勵(lì)機(jī)制的有效性。

6.2 實(shí)驗(yàn)設(shè)置

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

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

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

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

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

6.3 評(píng)估指標(biāo)

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

1) 用戶(hù)平均效用：所有贏標(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) 平臺(tái)效用：評(píng)估激勵(lì)方法預(yù)算是否可行的重要評(píng)估指標(biāo)，可根據(jù)式(2)進(jìn)行計(jì)算。

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

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

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

1) 用戶(hù)平均效用

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

2) 任務(wù)覆蓋率

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

3) 任務(wù)完成率

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

4) 平臺(tái)效用

圖4 用戶(hù)平均效用對(duì)比

圖5 任務(wù)覆蓋率

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

5) 系統(tǒng)效率

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

6) 社會(huì)福利

社會(huì)福利反映了經(jīng)濟(jì)效率。如圖 9(a)所示，隨著買(mǎi)方用戶(hù)數(shù)或賣(mài)方用戶(hù)數(shù)的增加，都會(huì)導(dǎo)致社會(huì)福利的增加，這是因?yàn)楦嗟挠脩?hù)會(huì)增加競(jìng)價(jià)與要價(jià)匹配成功的概率。從圖 9(b)可以看出，當(dāng)買(mǎi)賣(mài)雙方總數(shù)分別為50、100和500時(shí)，社會(huì)福利隨著等待耐心的增加而增加，這是因?yàn)楦叩牡却托膶⒋俪筛嗟母?jìng)價(jià)與要價(jià)匹配成功。如圖 9(c)所示，社會(huì)福利隨著到達(dá)率的增加而增加，原因在于隨著到達(dá)率的增加將促成更多的競(jìng)價(jià)與要價(jià)匹配成功。

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

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

圖7 平臺(tái)效用對(duì)比

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

圖9 社會(huì)福利對(duì)比

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

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

7 結(jié)束語(yǔ)

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