基于貪婪算法的參與式感知激勵(lì)分配機(jī)制

王 程，周 杰,2，杜景林

(1.南京信息工程大學(xué) 電子與信息工程學(xué)院，江蘇 南京 210044；2.日本國(guó)立新瀉大學(xué) 工學(xué)部電氣電子工學(xué)科，新瀉 950-2181)

0 引 言

激勵(lì)機(jī)制對(duì)參與式感知有著重要的意義[1-4]。在有限的激勵(lì)預(yù)算下，任務(wù)發(fā)布者為了獲取特定時(shí)間特定區(qū)域的數(shù)據(jù)向中央服務(wù)器發(fā)出請(qǐng)求，移動(dòng)用戶作為感知數(shù)據(jù)采集者將數(shù)據(jù)發(fā)送給中央服務(wù)器，激勵(lì)預(yù)算就會(huì)分配給被選中的移動(dòng)用戶[5]。文獻(xiàn)[6]首次提出逆向拍賣激勵(lì)機(jī)制，主要思想：參與者收集感知數(shù)據(jù)并且將投標(biāo)價(jià)格和數(shù)據(jù)一起發(fā)送到中央服務(wù)器，中央服務(wù)器會(huì)選擇最低的投標(biāo)價(jià)格的數(shù)據(jù)。這種激勵(lì)機(jī)制是通過(guò)最大化收集數(shù)據(jù)的數(shù)量來(lái)提高感知結(jié)果的精度，但是忽略了數(shù)據(jù)在時(shí)間和空間上的分布，在激勵(lì)預(yù)算不足以獲取足夠的數(shù)據(jù)并且缺失的數(shù)據(jù)集中在某個(gè)區(qū)域中的時(shí)候，由于插值的原因，會(huì)導(dǎo)致數(shù)據(jù)重構(gòu)的結(jié)果不精確。GIA考慮了參與者的位置和感知覆蓋范圍，將GBMCA(greedy budgeted maximum coverage algorithm)和RADP-VPC(reverse auction dynamic pricing)相結(jié)合，增加參與者的人數(shù)并且激勵(lì)參與者移動(dòng)來(lái)擴(kuò)大感知覆蓋范圍[7-9]。文獻(xiàn)[10]提出了兩種系統(tǒng)模型：一種是以平臺(tái)為中心的模型，該模型為參與者提供了報(bào)酬共享的平臺(tái)；另一種是以用戶為中心的模型，用戶可以更好地控制他們收到的報(bào)酬。IEA[11]運(yùn)用進(jìn)化算法迭代優(yōu)化機(jī)制，在有限的預(yù)算約束下，以最大化感知覆蓋范圍為優(yōu)化目標(biāo)，來(lái)選擇有效的參與者，并且提出虛擬報(bào)酬這一概念，激勵(lì)退出感知活動(dòng)的參與者重新加入。然而，以上文獻(xiàn)都沒(méi)有考慮到數(shù)據(jù)的分布情況。針對(duì)以上問(wèn)題，本文提出了一種激勵(lì)機(jī)制，該方法考慮了數(shù)據(jù)的時(shí)空分布，不是通過(guò)最大化感知數(shù)據(jù)的數(shù)量而是根據(jù)數(shù)據(jù)的分布情況，將激勵(lì)預(yù)算分配給提供最有效數(shù)據(jù)的區(qū)域來(lái)最小化感知結(jié)果的平均誤差。在對(duì)平均誤差、數(shù)據(jù)數(shù)量和分布之間的關(guān)系進(jìn)行研究后，發(fā)現(xiàn)較大數(shù)量和更加均勻分布的數(shù)據(jù)可以提高感知結(jié)果的精度。本文將激勵(lì)分配作為優(yōu)化問(wèn)題，通過(guò)貪婪算法對(duì)其進(jìn)行優(yōu)化。

由于激勵(lì)預(yù)算是有限的，收集到的感知數(shù)據(jù)是不可能覆蓋整個(gè)目標(biāo)區(qū)域的，因此文獻(xiàn)[12]使用數(shù)據(jù)插值的方法來(lái)對(duì)缺失的數(shù)據(jù)進(jìn)行重構(gòu)。文章指出，在參與感知系統(tǒng)中，測(cè)量的密度是不均勻的，所以需要激勵(lì)參與者在目標(biāo)區(qū)域收集數(shù)據(jù)，并且需要控制每塊區(qū)域的測(cè)量密度。

1 系統(tǒng)模型

1.1 模型描述

由文獻(xiàn)[12]可知，當(dāng)子區(qū)域的分配足夠細(xì)致的話，每個(gè)子區(qū)域中的一個(gè)樣本就可以為感知任務(wù)提供足夠的數(shù)據(jù)精度。根據(jù)任務(wù)發(fā)布者的環(huán)境數(shù)據(jù)需求，將感知任務(wù)的整個(gè)區(qū)域和持續(xù)時(shí)間劃分在子區(qū)域集合R={r=1,2,3,…,n}中。在每個(gè)子區(qū)域中，只需要目標(biāo)環(huán)境參數(shù)的一個(gè)樣本。

圖1 參與感知過(guò)程

在目標(biāo)區(qū)域內(nèi)，Z(ri)是變量Z(r)在點(diǎn)ri(i=1,2,3,…,n)處的屬性值。未知點(diǎn)變量Z*(r)是根據(jù)n個(gè)已知的變量值加權(quán)求和后得到的，即

(1)

其中，λi是第i個(gè)位置處的測(cè)量值得未知權(quán)重，表示各空間樣本點(diǎn)觀測(cè)值對(duì)估計(jì)值的貢獻(xiàn)程度。權(quán)重λi取決于測(cè)量點(diǎn)、預(yù)測(cè)位置的距離和周圍f測(cè)量值之間關(guān)系的擬合模型。選取λi需要滿足無(wú)偏性和估計(jì)方差最小這兩個(gè)條件。根據(jù)方程組(2)來(lái)求解權(quán)重系數(shù)λi

(2)

其中，r和ri表示的是未知點(diǎn)和第i個(gè)樣本的位置。μ是拉格朗日常數(shù)。γ(ri,rj)表示變量Z(r)在ri和rj兩點(diǎn)之差的方差的一半，可由式(3)得到

(3)

通過(guò)求解克里金方程組可以得到權(quán)重系數(shù)λi，然后再由式(1)得出估計(jì)值。

本文用ε來(lái)表示感知結(jié)果的平均誤差和所有子區(qū)域R真值的比,誤差主要積累在無(wú)數(shù)據(jù)樣本的子區(qū)域中,有

(4)

根據(jù)式(4)，可以發(fā)現(xiàn)平均誤差是與有數(shù)據(jù)樣本的區(qū)域有關(guān)的。

1.2 樣本數(shù)量和分布與平均誤差之間的關(guān)系

1.2.1 樣本數(shù)量

(5)

1.2.2 樣本分布

(2)不同區(qū)域的數(shù)據(jù)重要性隨著環(huán)境的改變而改變。例如，圖3(b)顯示了市區(qū)噪聲水平的讀數(shù)。噪聲水平在區(qū)域“A1”改變巨大，而區(qū)域“A2”相對(duì)于區(qū)域“A1”改變比較穩(wěn)定。如果大量數(shù)據(jù)是從區(qū)域“A1”收集來(lái)的，那么插值結(jié)果就會(huì)更加準(zhǔn)確。顯然，更高的權(quán)重應(yīng)該給環(huán)境變化劇烈的地區(qū)，例如在圖3(b)的“A1”。

圖3 樣本數(shù)據(jù)在區(qū)域中的分布權(quán)重

將整塊區(qū)域分成區(qū)域集合A={a=1,2,…,n}。用Xa,?a∈A來(lái)表示落在每個(gè)區(qū)域中的樣本集。樣本落在每個(gè)區(qū)域的概率

(6)

除此之外，不同區(qū)域的數(shù)據(jù)的重要性是由環(huán)境數(shù)據(jù)改變的程度決定的。當(dāng)數(shù)據(jù)改變穩(wěn)定的話，那么只需要較少的數(shù)據(jù)樣本就可以獲得準(zhǔn)確的感知結(jié)果。因此，每個(gè)區(qū)域的權(quán)重可由區(qū)域中的數(shù)據(jù)讀數(shù)的標(biāo)準(zhǔn)偏差得到

(7)

(8)

(9)

2 激勵(lì)機(jī)制模型求解

考慮到本文中的優(yōu)化問(wèn)題是和樣本數(shù)量和分布相關(guān)的，那么可以將式(4)中的平均誤差作為目標(biāo)函數(shù)。根據(jù)式(9)

(10)

(11)

步驟1 初始化，賦初值

將所有區(qū)域分成兩個(gè)子集——選中的集S1和未被選中的集S2。在步驟1先把所有的區(qū)域放進(jìn)S2中，S1為空集。

步驟2 每次迭代過(guò)程中區(qū)域的選擇

如果S2中的區(qū)域r被選中，那么就從S2移動(dòng)到S1，形成一個(gè)新集S1，那么式(11)目標(biāo)函數(shù)的變化為

(12)

ir是區(qū)域r中最低的激勵(lì)需求。式(11)目標(biāo)函數(shù)每單位激勵(lì)的變化為

(13)

每次迭代過(guò)程中，選擇提供最有效數(shù)據(jù)的區(qū)域r，那么區(qū)域r就從S2移動(dòng)到S1。將激勵(lì)ir分配到選中的區(qū)域r，最低激勵(lì)需求的參與者將數(shù)據(jù)發(fā)送到中央服務(wù)器后獲得報(bào)酬。

步驟3 循環(huán)

耗盡激勵(lì)預(yù)算B或者所有區(qū)域已被選中，則終止算法，否則一直重復(fù)步驟2。

3 仿真實(shí)驗(yàn)

3.1 程序設(shè)置

本文將從固定的無(wú)線傳感器網(wǎng)絡(luò)收集的環(huán)境感知數(shù)據(jù)作為真值，并且利用從公園收集的軌道數(shù)據(jù)[15]來(lái)模擬參與者的移動(dòng)軌道，這個(gè)軌道數(shù)據(jù)集包含了41個(gè)參與者在特定一天中的移動(dòng)軌道。下面本文采取以下步驟來(lái)設(shè)置實(shí)驗(yàn)：

(1)設(shè)置區(qū)域R和激勵(lì)需求ir：本文將矩形感知區(qū)域分成4×4的區(qū)域，將持續(xù)時(shí)間分成24個(gè)時(shí)間點(diǎn)，因此|R|=16×24=384。把41個(gè)參與者的移動(dòng)軌道放入這個(gè)感知區(qū)域，每個(gè)參與者的激勵(lì)需求在[1,20]中隨機(jī)生成，通過(guò)參與者的軌道和激勵(lì)需求來(lái)計(jì)算ir,?r∈R。

3.2 仿真結(jié)果

圖4 仿真結(jié)果

ε=0.3777-0.0642α-0.1247β

(14)

通過(guò)這個(gè)表達(dá)式，可以發(fā)現(xiàn)樣本分布要比樣本數(shù)量對(duì)平均誤差的影響更大。圖4(b)表示根據(jù)式(14)得出的預(yù)測(cè)誤差。真實(shí)誤差和根據(jù)40 000個(gè)樣本集得出的預(yù)測(cè)誤差之間只有0.021的差距，這個(gè)差距是非常小的，在接受范圍之內(nèi)。

本文將12月8號(hào)收集的溫度數(shù)據(jù)作為真值，將本文方法與逆向拍賣機(jī)制和IEA的性能進(jìn)行比較。圖4(a)和圖4(b)表示隨著激勵(lì)需求B的變化，這兩種方法在所選區(qū)域中的平均誤差和樣本數(shù)量。

從圖4(c)可以看出，當(dāng)預(yù)算不夠時(shí)，本文方法的平均誤差與逆向拍賣機(jī)制和IEA的差距越來(lái)越大。當(dāng)預(yù)算在20的時(shí)候，逆向拍賣的誤差是0.248，IEA的誤差是0.22，而本文方法的誤差只有0.193(比逆向拍賣機(jī)制少了22%，比IEA少了13%)，這是因?yàn)楸疚姆椒ㄔ跀?shù)據(jù)分布均勻的區(qū)域給了更高的激勵(lì)來(lái)收集數(shù)據(jù)。

從圖4(d)可以看出，本文方法所需要的區(qū)域比逆向拍賣機(jī)制和IEA都要的少，給足夠的預(yù)算，3種方法的數(shù)據(jù)精度是差不多的。本文方法所需要的數(shù)據(jù)樣本比逆向拍賣機(jī)制的少42%，比IEA少26%，減少了移動(dòng)設(shè)備的能量消耗，為每個(gè)參與者增加了72%的激勵(lì)，這樣可以鼓勵(lì)移動(dòng)用戶提供高質(zhì)量的數(shù)據(jù)。

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

本文提出的在預(yù)算約束條件下的參與感知激勵(lì)機(jī)制可以達(dá)到更高的數(shù)據(jù)精度。與現(xiàn)有的激勵(lì)機(jī)制不同，本文方法不僅考慮了樣本的數(shù)量還考慮了樣本的分布。本文研究并用公式表示平均誤差，樣本數(shù)量和樣本分布之間的關(guān)系。將平均誤差最小化問(wèn)題轉(zhuǎn)化為每塊區(qū)域的激勵(lì)分配優(yōu)化問(wèn)題，提出了一個(gè)貪婪激勵(lì)分配算法來(lái)解決優(yōu)化問(wèn)題。大量真實(shí)數(shù)據(jù)集的模擬驗(yàn)證了該機(jī)制的有效性。與現(xiàn)有的逆向拍賣機(jī)制和IEA進(jìn)行仿真結(jié)果對(duì)比，驗(yàn)證了本文的激勵(lì)分配機(jī)制可以增加感知數(shù)據(jù)的精度，提高參與者的利益。

[1]CHENLongbiao,LIShijian,PANGang.Smartphone:Pervasivesensingandapplications[J].ChineseJournalofComputers,2015,38(2):423-438(inChinese).[陳龍彪,李石堅(jiān),潘綱.智能手機(jī):普適感知與應(yīng)用[J].計(jì)算機(jī)學(xué)報(bào),2015,38(2):423-438.]

[2]RugeL,AltakrouriB,SchraderA.Soundofthecity-conti-nuousnoisemonitoringforahealthycity[C]//InternationalWorkshoponSmartEnvironmentsandAmbientIntelligence.IEEE,2013:670-675.

[3]DevarakondaS,SevusuP,LiuH,etal.Real-timeairqualitymonitoringthroughmobilesensinginmetropolitanareas[C]//TheACMSIGKDDInternationalWorkshoponUrbanComputing.ACM,2013:1-8.

[4]WANGHao.Resarchonincentivetechnologyinparticipatorysensingnetwork[D].Harbin:HarbinEngineeringUniversity,2014:13-14(inChinese).[王浩.參與感知網(wǎng)絡(luò)激勵(lì)技術(shù)研究[D].哈爾濱:哈爾濱工程大學(xué),2014:13-14.]

[5]ZHAOLuming.Theresearchandimplementofincentivemecha-nismbasedonparticipatorysensing[D].Beijing:BeijingUniversityofPostsandTelecommunication,2015:7-8(inChinese).[趙露名.基于參與式感知的激勵(lì)機(jī)制的研究與實(shí)現(xiàn)[D].北京:北京郵電大學(xué),2015:7-8.]

[6]LeeJS,HohB.Sellyourexperiences:Amarketmechanismbasedincentiveforparticipatorysensing[C]//IEEEInternationalConferenceonPervasiveComputingandCommunications.IEEE,2010:60-68.

[7]JaimesLG,Vergara-LaurensI,LabradorM.Alocation-basedincentivemechanismforparticipatorysensingsystemswithbudgetconstraints[J].Dissertations&Theses-Gradworks,2012,25(3):103-108.

[8]JaimesLG,Vergara-LaurensI,ChakeriA.SPREAD,acrowdsensingincentivemechanismtoacquirebetterrepresentativesamples[C]//IEEEInternationalConferenceonPervasiveComputingandCommunicationWorkshops.IEEE,2014:92-97.

[9]JaimesLG,Vergara-LaurensI,RaijA.Acrowdsensingincentivealgorithmfordatacollectionforconsecutivetimeslotproblems[C]//Communications.IEEE,2014:1-5.

[10]YangD,XueG,FangX,etal.Crowdsourcingtosmartphones:Incentivemechanismdesignformobilephonesensing[C]//InternationalConferenceonMobileComputingandNetworking.ACM,2012:173-184.

[11]Kumrai T,Ota K,Dong M,et al.An incentive-based evolutionary algorithm for participatory sensing[C]//Global Communications Conference.IEEE,2014:5021-5025.

[12]Mendez D,Labrador M,Ramachandran K.Data interpolation for participatory sensing systems[J].Pervasive & Mobile Computing,2013,9(1):132-148.

[13]WANG Ting.Research on 3D interpolation approaches based on Kriging with anisotropic spatial structures[D].Nanjing:Nanjing Normal University,2013:1-65(in Chinese).[王亭.顧及各向異性的三維Kriging空間插值方法研究[D].南京:南京師范大學(xué),2013:1-65.]

[14]Ji HY,Ohm SY,Min GC.Brightness preservation and image enhancement based on maximum entropy distribution[M]//Convergence and Hybrid Information Technology,2012:365-372.

[15]Solmaz G,Akbas MI,Turgut D.Modeling visitor movement in theme parks[C]//IEEE,Conference on Local Computer Networks.IEEE Computer Society,2012:36-43.