基于平臺興趣度的移動群智感知激勵機制模型

萬 濤,王璐瑤,岳世鑫,廖維川

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

1 引言

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

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

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

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

1)通過對任務(wù)候選參與者們興趣度的評估來確定參與者們的自身價值以及對平臺的吸引力,不僅考慮了任務(wù)開支對選擇獲勝者的參考價值,同時從更多維度去提供選擇參與者的依據(jù)。

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

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

2 系統(tǒng)框架

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

圖1 PIP激勵機制模型

3 PIP模型構(gòu)建

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

3.1 興趣度評估

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

Ii=QiEi

(1)

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

(2)

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

(3)

式中,參與者Ui的任務(wù)感知歷時總時長越短,其工作的時效性就越高。

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

(4)

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

(5)

(6)

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

(7)

3.2 參與者競選與激勵

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

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

Ri=Bpre×Ii

(8)

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

(9)

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

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

(10)

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

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

(11)

只有當Ui滿足E(W)≥E(W)/W時,該候選者才能成為獲勝者,平臺將會選擇他來完成感知任務(wù),并向其支付相應(yīng)報酬Ri,否則平臺將會拒絕候選者對該任務(wù)的請求。

4 仿真及分析

4.1 仿真設(shè)置

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

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

4.2 實驗結(jié)果分析

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

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

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

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

圖3 平臺效益的比較

由圖4所示,PIP模型在運行時間方面也是優(yōu)于其它兩種模型的。其中OMG模型所需的運行時間最長,因為它將出價過程分為多個階段,每個階段都需要計算密度閾值,參與者可能由于到達和離開任務(wù)的時間的不同而跨越多個階段。本文提出的PIP與ITA模型的運行時間較為接近,主要是由于二者均通過兩階段拍賣來選擇獲勝者參與感知任務(wù),但由于PIP模型第一階段應(yīng)用了離線機制,因此所需的運行時間比ITA短,其運行時間為三個模型中最短的。

圖4 運行時間的比較

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

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

5 結(jié)束語

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