萬(wàn) 濤,王璐瑤,岳世鑫,廖維川

(1. 華東交通大學(xué)信息工程學(xué)院,江西 南昌 330013;2. 華東交通大學(xué)理學(xué)院,江西 南昌 330013)

1 引言

近年來(lái),移動(dòng)群智感知(Mobile Crowd Sensing,MCS)作為一種新的感知模式,在學(xué)術(shù)界和工業(yè)界受到了越來(lái)越廣泛的關(guān)注。與傳統(tǒng)的傳感器網(wǎng)絡(luò)相比,群智感知由于其突出的優(yōu)勢(shì)而具有巨大的潛力,如時(shí)空覆蓋范圍廣,成本低,具有良好的可擴(kuò)展性等[1]。因此,移動(dòng)群智感知技術(shù)被廣泛應(yīng)用于多個(gè)領(lǐng)域。例如,用于檢測(cè)城市空氣污染的參與式傳感器系統(tǒng)HazeWatch[2];用于提供道路交通信號(hào)時(shí)間表相關(guān)信息并建議有效的道路規(guī)劃的服務(wù)軟件SignalGuru[3];用于對(duì)移動(dòng)目標(biāo)的軌跡預(yù)測(cè)和跟蹤的解決方案CrowdTracker[4]等。

然而,在感知數(shù)據(jù)的過(guò)程中,用戶將消耗如電源,網(wǎng)絡(luò)流量和時(shí)間等資源。此外,信息共享還將帶來(lái)潛在的隱私威脅,從而導(dǎo)致用戶參與度降低[5]。因此在移動(dòng)群智感知中,為了招募足夠數(shù)量的參與者去提供有效的感知數(shù)據(jù),合理的激勵(lì)機(jī)制的設(shè)計(jì)變得尤為重要。

目前,激勵(lì)機(jī)制可以主要分為離線激勵(lì)和在線激勵(lì)。離線激勵(lì)機(jī)制要求感知平臺(tái)等待足夠的用戶提交其投標(biāo),然后選擇中標(biāo)者來(lái)完成感知任務(wù)。Yang等人[6]提出一種采用Stackelberg博弈的基于拍賣(mài)的離線激勵(lì)機(jī)制,但是離線激勵(lì)機(jī)制需要等待所有用戶出價(jià),并且不能接受新用戶的出價(jià)。隨即Zhao等人[7]根據(jù)在線多階段拍賣(mài)模型設(shè)計(jì)了兩種在線激勵(lì)機(jī)制,該機(jī)制通過(guò)設(shè)定初始門(mén)檻來(lái)選擇贏家。但是,在線激勵(lì)機(jī)制需要通過(guò)歷史經(jīng)驗(yàn)設(shè)置閾值來(lái)選擇贏家。Long等人[8]應(yīng)用離線和在線兩種方法相結(jié)合的兩階段拍賣(mài)激勵(lì)機(jī)制來(lái)選擇獲獎(jiǎng)?wù)?該機(jī)制設(shè)置了靜態(tài)選擇獲獎(jiǎng)?wù)卟?dòng)態(tài)支付獎(jiǎng)勵(lì),以克服不公平現(xiàn)象并激勵(lì)用戶及時(shí)完成任務(wù)。

離線和在線激勵(lì)分別有各自的不足之處,且由于已有激勵(lì)機(jī)制中,感知平臺(tái)大多根據(jù)預(yù)算和報(bào)價(jià)來(lái)選出獲勝者用戶,無(wú)法確定用戶上傳的感知數(shù)據(jù)的價(jià)值。因此,本文提出了一種基于平臺(tái)興趣度的移動(dòng)群智感知激勵(lì)機(jī)制模型(Platform-interest-based Incentive Policy for Mobile Crowd Sensing, PIP)。本文的主要貢獻(xiàn)有以下三點(diǎn):

1)通過(guò)對(duì)任務(wù)候選參與者們興趣度的評(píng)估來(lái)確定參與者們的自身價(jià)值以及對(duì)平臺(tái)的吸引力,不僅考慮了任務(wù)開(kāi)支對(duì)選擇獲勝者的參考價(jià)值,同時(shí)從更多維度去提供選擇參與者的依據(jù)。

2)由于平臺(tái)對(duì)興趣度的評(píng)估由所提供數(shù)據(jù)的質(zhì)量以及參與者努力度直接決定,且興趣度直接影響任務(wù)報(bào)酬的分配,因此,為了獲取更多的任務(wù)報(bào)酬,候選參與者將會(huì)不斷提高自身努力程度以及提升上傳數(shù)據(jù)的質(zhì)量。

3)通過(guò)將離線和在線拍賣(mài)結(jié)合的兩步驟拍賣(mài)激勵(lì)機(jī)制不僅能吸引更多數(shù)量的參與者,還能夠有效的避免由于參與者接收任務(wù)是動(dòng)態(tài)隨機(jī)的,不同用戶到達(dá)時(shí)間可能不同以及必須通過(guò)歷史經(jīng)驗(yàn)閾值來(lái)選擇贏家等問(wèn)題。

2 系統(tǒng)框架

本文提出的PIP模型系統(tǒng)框架和感知流程如圖1所示。該系統(tǒng)包括服務(wù)請(qǐng)求者、感知平臺(tái)(服務(wù)器)以及任務(wù)參與者這3個(gè)部分。服務(wù)請(qǐng)求者結(jié)合自身情況向感知平臺(tái)發(fā)出任務(wù)請(qǐng)求,感知平臺(tái)將感知任務(wù)以及預(yù)算下達(dá)給候選參與者們并產(chǎn)生對(duì)候選參與者的興趣度,在目標(biāo)感知區(qū)域內(nèi)候選參與者們將收集到的感知數(shù)據(jù)以及所需開(kāi)支匯報(bào)給感知平臺(tái),感知平臺(tái)結(jié)合離線和在線機(jī)制,通過(guò)兩步驟動(dòng)態(tài)拍賣(mài)的方法對(duì)獲勝者進(jìn)行選擇,并給與其相應(yīng)的激勵(lì),最后服務(wù)器將數(shù)據(jù)處理后返回感知結(jié)果給服務(wù)請(qǐng)求者。

圖1 PIP激勵(lì)機(jī)制模型

3 PIP模型構(gòu)建

在本節(jié)中,具體介紹基于興趣度的感知激勵(lì)機(jī)制的模型構(gòu)建。PIP模型構(gòu)建包括兩個(gè)階段:第一階段感知平臺(tái)通過(guò)任務(wù)候選參與者們上傳的數(shù)據(jù)質(zhì)量與努力度對(duì)他們進(jìn)行興趣度評(píng)估;第二階段候選參與者通過(guò)兩步驟動(dòng)態(tài)拍賣(mài)的方法競(jìng)選出獲勝者,并由感知平臺(tái)向其支付相應(yīng)報(bào)酬。

3.1 興趣度評(píng)估

感知任務(wù)發(fā)布后,感知平臺(tái)將會(huì)考慮候選任務(wù)參與者是否符合該任務(wù)需求,并計(jì)算他們各自的興趣度的值。假設(shè)感知平臺(tái)在觀察任務(wù)參與者時(shí)將會(huì)產(chǎn)生一個(gè)對(duì)該任務(wù)參與者的興趣度Ii,這個(gè)值反映出每個(gè)候選參與者Ui(i∈N)在返回感知數(shù)據(jù)之后獲得的感知平臺(tái)對(duì)其價(jià)值的評(píng)估,興趣度計(jì)算如下

Ii=QiEi

(1)

式中,Qi和Ei分別表示的是該任務(wù)候選參與者Ui上傳的數(shù)據(jù)質(zhì)量與努力度。候選參與者的質(zhì)量和努力度越高,平臺(tái)對(duì)其產(chǎn)生的興趣越大。感知數(shù)據(jù)質(zhì)量Qi將由其發(fā)布感知數(shù)據(jù)的可信度、完整性和時(shí)效性來(lái)決定。將參與者上傳的數(shù)據(jù)質(zhì)量因子Ci用其完整性和時(shí)效性表示為Ci=[Ci1,Ci2],并與他們對(duì)應(yīng)的各因素權(quán)重Wi=[Wi1,Wi2]T相乘進(jìn)行質(zhì)量Qi的計(jì)算,即Qi=Ci·Wi。其中,數(shù)據(jù)的完整性Ci1體現(xiàn)了候選參與者上傳感知數(shù)據(jù)的完整程度,計(jì)算為

(2)

數(shù)據(jù)的時(shí)效性體現(xiàn)的是在有限的任務(wù)時(shí)間范圍內(nèi)任務(wù)參與者上傳數(shù)據(jù)的及時(shí)程度,假設(shè)規(guī)定在有限的時(shí)間范圍[0,Tn]內(nèi)必須上傳感知數(shù)據(jù),參與者接受任務(wù)的起始時(shí)刻為T(mén)s,上傳感知數(shù)據(jù)至服務(wù)器的時(shí)刻為T(mén)u,則任務(wù)感知?dú)v時(shí)Tall=Tu-Ts,計(jì)算如下

(3)

式中,參與者Ui的任務(wù)感知?dú)v時(shí)總時(shí)長(zhǎng)越短,其工作的時(shí)效性就越高。

本文將采用熵權(quán)法進(jìn)行不同指標(biāo)的權(quán)重確定。熵權(quán)法的基本思路是根據(jù)指標(biāo)變異性的大小來(lái)確定客觀權(quán)重。一般來(lái)說(shuō),若某個(gè)指標(biāo)的信息熵越小,表明指標(biāo)值得變異程度越大,提供的信息量越多,在綜合評(píng)價(jià)中所能起到的作用也越大,其權(quán)重也就越大。相反,某個(gè)指標(biāo)的信息熵越大,表明指標(biāo)值得變異程度越小,提供的信息量也越少,在綜合評(píng)價(jià)中所起到的作用也越小,其權(quán)重也就越小。熵權(quán)法賦權(quán)首先進(jìn)行數(shù)據(jù)標(biāo)準(zhǔn)化,將各個(gè)指標(biāo)的數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理。假設(shè)對(duì)質(zhì)量因子Ci數(shù)據(jù)標(biāo)準(zhǔn)化后的值Yi=[Yi1,Yi2,],其中

(4)

根據(jù)信息論中信息熵的定義,一組數(shù)據(jù)的信息熵Eik計(jì)算為

(5)

(6)

努力度Ei代表該候選參與者Ui在接收感知任務(wù)以后所付出努力的程度,計(jì)算為

(7)

3.2 參與者競(jìng)選與激勵(lì)

本文采用兩個(gè)步驟的動(dòng)態(tài)拍賣(mài)的方法競(jìng)選出獲勝者并支付報(bào)酬。感知平臺(tái)將結(jié)合離線和在線機(jī)制,將拍賣(mài)過(guò)程分為兩個(gè)步驟。其中第一步是樣本初篩,此步驟采用離線機(jī)制接收一組候選參與者。當(dāng)候選者出價(jià)不符合平臺(tái)的標(biāo)準(zhǔn)時(shí),將會(huì)被初步淘汰。第二步是候選者競(jìng)爭(zhēng)及報(bào)酬支付,采取在線機(jī)制,通過(guò)候選者帶來(lái)的平臺(tái)效益計(jì)算出平均平臺(tái)效益,作為獲勝者選拔的一個(gè)重要指標(biāo)。最終將報(bào)酬分發(fā)給競(jìng)選中的獲勝者。獎(jiǎng)勵(lì)分配的具體步驟如下:

第一步時(shí)間周期設(shè)置為t=T/2InT,候選參與者獲取返回感知數(shù)據(jù)之后,平臺(tái)將會(huì)考慮參與者出價(jià)是否合理,只有當(dāng)候選參與者報(bào)價(jià)Bi小于等于平臺(tái)支付給他的報(bào)酬Ri,感知平臺(tái)才會(huì)將其納入考量范圍,出價(jià)不合理者將會(huì)面臨淘汰。候選參與者將獲得的報(bào)酬Ri為

Ri=Bpre×Ii

(8)

第二步將計(jì)算候選者帶來(lái)的平臺(tái)效益E(W),根據(jù)平均平臺(tái)效益E(W)/W來(lái)競(jìng)選出該步驟的獲勝者并給予報(bào)酬。感知平臺(tái)為了找到能帶來(lái)平臺(tái)效益高的候選參與者,先將時(shí)間周期t內(nèi)所有參與者匯總到集合W中去,平臺(tái)效益E(W)計(jì)算為

(9)

式中,μ表示一個(gè)可以確定收益遞減梯度的參數(shù),對(duì)數(shù)函數(shù)體現(xiàn)了平臺(tái)對(duì)獲勝者的邊際收益遞減。參與者對(duì)平臺(tái)的整體貢獻(xiàn)C(W)計(jì)算為

C(W)=Dall·∑Qi(Ui∈W)

(10)

該貢獻(xiàn)由候選參與者提交的感知數(shù)據(jù)總量Dall和上傳感知數(shù)據(jù)的質(zhì)量決定。平臺(tái)支付給參與者的總報(bào)酬R(W)計(jì)算為

R(W)=∑Ri(Ui∈W)

(11)

只有當(dāng)Ui滿足E(W)≥E(W)/W時(shí),該候選者才能成為獲勝者,平臺(tái)將會(huì)選擇他來(lái)完成感知任務(wù),并向其支付相應(yīng)報(bào)酬Ri,否則平臺(tái)將會(huì)拒絕候選者對(duì)該任務(wù)的請(qǐng)求。

4 仿真及分析

4.1 仿真設(shè)置

本次實(shí)驗(yàn)使用配置為Inter i7-5557U CPU3.10Ghz處理器和8G內(nèi)存的Win10 64位操作系統(tǒng),在MATLAB 8.5平臺(tái)對(duì)曼哈頓模型[9]進(jìn)行仿真,模擬0.319km×1.135km區(qū)域內(nèi)的縱橫交錯(cuò)的曼哈頓街道。在仿真中計(jì)劃每4m設(shè)置一個(gè)感知節(jié)點(diǎn),感知任務(wù)歷時(shí)1800秒,將隨機(jī)生成800名參與候選人,將預(yù)算設(shè)置為900,參數(shù)設(shè)置見(jiàn)表1。

表1 參數(shù)設(shè)置表

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

本文針對(duì)感知任務(wù)參與人數(shù)、運(yùn)行時(shí)和平臺(tái)效益這三個(gè)方面進(jìn)行了仿真,并與Wang[9]等人提出的在線激勵(lì)機(jī)制模型OMG以及Zhao[7]等人提出的結(jié)合離線與在線的激勵(lì)機(jī)制模型ITA進(jìn)行對(duì)比,以驗(yàn)證PIP激勵(lì)機(jī)制能夠高效的完成移動(dòng)群智感知任務(wù)。

圖2顯示了PIP激勵(lì)機(jī)制模型中候選參與者與計(jì)劃參與者數(shù)量的關(guān)系,候選參與人數(shù)隨計(jì)劃參與人數(shù)的增多而明顯增多。但是由于參與任務(wù)的成本約束,候選參與者的人數(shù)在超過(guò)一定數(shù)量之后增幅變小,整體的人數(shù)的增加速率變得越來(lái)越平緩?？梢酝茰y(cè)適當(dāng)增加任務(wù)計(jì)劃參與人數(shù)能夠提升感知任務(wù)參與者的參與積極性,促使平臺(tái)找到更多合適的參與者,獲取更多高質(zhì)量的感知數(shù)據(jù)從而有利于完成感知任務(wù)。

圖2 候選參與者數(shù)與計(jì)劃參與數(shù)的關(guān)系

本文將提出的PIP模型和與其相關(guān)的其它模型就平臺(tái)效益、運(yùn)行時(shí)間兩個(gè)方面的進(jìn)行了對(duì)比。其中,由圖3所示,平臺(tái)效用整體隨預(yù)算的增長(zhǎng)而線性增長(zhǎng),提出的PIP模型相對(duì)其它兩種模型顯示出很大的優(yōu)越性,因?yàn)樽罱K獲勝者是根據(jù)平臺(tái)效用的均值決定的,平臺(tái)效益被作為候選參與者競(jìng)選的其中一個(gè)指標(biāo),只有當(dāng)該競(jìng)選人產(chǎn)生的平臺(tái)效益大于等于平均平臺(tái)效益時(shí),才有可能被平臺(tái)選擇。

圖3 平臺(tái)效益的比較

由圖4所示,PIP模型在運(yùn)行時(shí)間方面也是優(yōu)于其它兩種模型的。其中OMG模型所需的運(yùn)行時(shí)間最長(zhǎng),因?yàn)樗鼘⒊鰞r(jià)過(guò)程分為多個(gè)階段,每個(gè)階段都需要計(jì)算密度閾值,參與者可能由于到達(dá)和離開(kāi)任務(wù)的時(shí)間的不同而跨越多個(gè)階段。本文提出的PIP與ITA模型的運(yùn)行時(shí)間較為接近,主要是由于二者均通過(guò)兩階段拍賣(mài)來(lái)選擇獲勝者參與感知任務(wù),但由于PIP模型第一階段應(yīng)用了離線機(jī)制,因此所需的運(yùn)行時(shí)間比ITA短,其運(yùn)行時(shí)間為三個(gè)模型中最短的。

圖4 運(yùn)行時(shí)間的比較

數(shù)據(jù)冗余率=(參與者提交的總數(shù)據(jù)量-任務(wù)需求總數(shù)據(jù)量)/參與者提交的總數(shù)據(jù)量,由圖5,隨著整體預(yù)算的增加,總數(shù)據(jù)量增加,三個(gè)模型的冗余率都呈現(xiàn)上升趨勢(shì)。PIP模型通過(guò)感知平臺(tái)對(duì)于參與者評(píng)估以及兩階段拍賣(mài)的競(jìng)選方式有效避免了無(wú)效數(shù)據(jù),結(jié)果表明該模型的數(shù)據(jù)冗余度明顯低于其它兩個(gè)模型。

圖5 數(shù)據(jù)冗余度的比較

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

參與者數(shù)量不足,上傳數(shù)據(jù)質(zhì)量不高以及積極性不高一直是移動(dòng)群智感知系統(tǒng)中實(shí)際面臨的一些問(wèn)題。針對(duì)這些問(wèn)題,本文提出了一個(gè)基于平臺(tái)興趣度的移動(dòng)群智感知激勵(lì)機(jī)制模型。通過(guò)候選參與者對(duì)任務(wù)的努力程度以及上傳數(shù)據(jù)的質(zhì)量量化評(píng)估感知平臺(tái)對(duì)該候選者產(chǎn)生的興趣度,由兩步驟動(dòng)態(tài)拍賣(mài)的方法競(jìng)選出最終獲勝者參與感知任務(wù)并領(lǐng)取相應(yīng)報(bào)酬。仿真結(jié)果表明該機(jī)制具備更短的運(yùn)行時(shí)間,帶來(lái)更高的平臺(tái)效益。未來(lái)將研究如何建立參與者之間的合作機(jī)制以提高感知數(shù)據(jù)的質(zhì)量。