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

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

1 引言

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

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

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

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

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

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

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

2 系統(tǒng)框架

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

圖1 PIP激勵機制模型

3 PIP模型構建

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

3.1 興趣度評估

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

Ii=QiEi

(1)

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

(2)

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

(3)

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

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

(4)

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

(5)

(6)

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

(7)

3.2 參與者競選與激勵

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

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

Ri=Bpre×Ii

(8)

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

(9)

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

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

(10)

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

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

(11)

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

4 仿真及分析

4.1 仿真設置

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

表1 參數(shù)設置表

4.2 實驗結果分析

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

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

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

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

圖3 平臺效益的比較

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

圖4 運行時間的比較

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

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

5 結束語

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