基于位置隱私保護的空間眾包任務(wù)分配方法

王 琦 高 銘

1(吉林司法警官職業(yè)學(xué)院基礎(chǔ)教研部 吉林 長春 130062) 2(長春理工大學(xué)計算機科學(xué)技術(shù)學(xué)院 吉林 長春 130022)

0 引 言

近年來,隨著4G網(wǎng)絡(luò)的廣泛普及和5G網(wǎng)絡(luò)的快速部署,空間眾包(Spatial Crowdsourcing,SC)[1]在多個領(lǐng)域內(nèi)得到廣泛應(yīng)用。通常,SC是用于執(zhí)行時空任務(wù)的平臺,該平臺接收請求者發(fā)布的基于位置的任務(wù),并根據(jù)眾包工人的工作范圍來匹配適當(dāng)?shù)娜蝿?wù)[2]。為了實現(xiàn)精確高效的任務(wù)匹配,當(dāng)前的解決方案需要將用戶的特定位置暴露在SC服務(wù)器上,例如食品配送應(yīng)用程序中的家庭地址、車輛服務(wù)平臺中的行動軌跡等。然而,作為第三方的SC服務(wù)器可能不被信任,將位置信息外包到SC服務(wù)器引起了人們對隱私泄露的擔(dān)憂[3]。另外,任務(wù)匹配效率也是一個不容忽視的問題,如果任務(wù)匹配效率太低,SC平臺將無法處理大量的任務(wù)匹配請求,用戶體驗將會變差[4]。因此,迫切需要設(shè)計一種安全高效的任務(wù)匹配方案來解決這些問題。

針對現(xiàn)有空間眾包任務(wù)分配方法中存在的問題,提出一種基于位置隱私保護的空間眾包任務(wù)匹配方法,該方法不僅可以保護眾包工人的位置隱私,還可以使SC服務(wù)器有效地執(zhí)行任務(wù)匹配操作。首先,本文方法基于一種虛擬生成算法給眾包工人提供一個虛擬位置,并將虛擬位置發(fā)送到SC服務(wù)器中;然后SC服務(wù)器中使用ε-貪婪算法對平臺中的任務(wù)分配過程進行動態(tài)的批量劃分,提供任務(wù)分配的效率;最后,本文方法采用最大分?jǐn)?shù)分配(Maximum Score Assignment, MSA)策略來對空間眾包任務(wù)進行動態(tài)分配。

1 空間眾包模型

空間眾包由眾包平臺、任務(wù)發(fā)布者和眾包工人組成,如圖1所示。眾包平臺由一系列服務(wù)器組成,SC服務(wù)器在請求者和群組工作人員之間分配交互機制。因此,SC服務(wù)器管理任務(wù),并根據(jù)其要求的位置和執(zhí)行資格將它們分發(fā)給感興趣的眾包工人。然后,服務(wù)器從工人中接收執(zhí)行任務(wù)的結(jié)果,并將聚合結(jié)果發(fā)送回請求者。SC平臺的任務(wù)主要是尋找合適的工人來完成任務(wù),以提高任務(wù)覆蓋率和傭金聚合度。任務(wù)發(fā)布者通過平臺發(fā)布空間任務(wù),這些任務(wù)包含任務(wù)請求者的位置信息和完成任務(wù)的截止日期。此外發(fā)布者還制定了任務(wù)完成的標(biāo)準(zhǔn),以便在眾包工人接受執(zhí)行任務(wù)之前對其進行評估。之后,發(fā)布者從SC服務(wù)器處獲取任務(wù)結(jié)果。發(fā)布者的目標(biāo)是以較低的時間和成本,最大程度地獲得任務(wù)執(zhí)行的質(zhì)量。眾包工人則是接受SC服務(wù)器推給他們的任務(wù),并高效地完成此類任務(wù)以實現(xiàn)獲得獎勵和提高可信度的目標(biāo)。

圖1 空間眾包任務(wù)分配流程

根據(jù)任務(wù)的分配方式,空間眾包可以分為兩種不同的SC類型[13],即工人選擇任務(wù)(Worker-Selected Tasks, WST)模式和服務(wù)器分配任務(wù)(Sever-Assigned Tasks, SAT)模式。在WST模式下,SC服務(wù)器在線發(fā)布空間任務(wù),在其附近的工人可以任意選擇任務(wù),工人僅在選擇執(zhí)行所需任務(wù)時才報告其位置,不需實時向SC服務(wù)器顯示其位置。然而,由于服務(wù)器對任務(wù)分配沒有任何控制,系統(tǒng)很難實施最優(yōu)的任務(wù)分配策略。相比之下,在SAT模式下,SC服務(wù)器根據(jù)工人的具體位置將基于位置的任務(wù)分配給最近的工人,使整體任務(wù)分配最大化。但是,此模式的缺點是,為了有效地分配任務(wù),需要工人不斷向服務(wù)器更新其位置, 這可能造成隱私泄露。本文針對SAT模式下的隱私威脅問題,通過生成有用的虛擬位置代替工人真實位置在SC服務(wù)器中進行更新,用于及時獲得任務(wù)分配。

2 安全高效的眾包任務(wù)分配方法

現(xiàn)有的空間眾包任務(wù)分配方法中,在任務(wù)分配率和工人位置隱私之間存在著很高的折中。當(dāng)系統(tǒng)追求較高的任務(wù)分配率時,工人隱私信息面臨泄露的風(fēng)險。而一些位置隱私方法為服務(wù)器提供虛擬位置以保護工人隱私,但不可避免地會導(dǎo)致較低的任務(wù)分配率或延遲分配任務(wù)。為了解決這個難題,本文提出一種基于位置隱私保護的空間眾包任務(wù)分配方法,該方法采用虛擬技術(shù)對眾包工人的位置信息進行保護,利用基于動態(tài)批次匹配的任務(wù)分配方法來提高任務(wù)分配率,從而實現(xiàn)最大化分配的任務(wù)數(shù)量并防止任何隱私泄露。下面給出基于位置隱私保護的眾包任務(wù)分配方法的總體流程:

(1) 假設(shè)工人在其實際位置周圍生成三個虛擬位置(A、B和C),以這三個虛擬點為頂點構(gòu)造三角形,計算三角形的質(zhì)心位置作為工人的偽位置p(xp,yp)。

(2) 將眾包工人的偽位置發(fā)送到SC服務(wù)器,SC服務(wù)器將利用偽位置來計算工人與目標(biāo)任務(wù)之間的距離,其定義為:

(1)

式中:dist為歐氏距離;t(xt,yt)為目標(biāo)任務(wù)的位置。

(3) 為避免因固定批量大小產(chǎn)生的分配效率低的問題,以平臺用戶最小平均等待時間為目標(biāo),采用ε-貪婪算法對分配過程進行動態(tài)批量劃分;

(4) 最后,SC服務(wù)器依據(jù)就近原則進行動態(tài)任務(wù)分配。

2.1 基于虛擬技術(shù)的位置隱私保護模型

本文采用虛擬技術(shù)用于解決眾包工人位置隱私的保護問題。虛擬技術(shù)是空間眾包環(huán)境中一種廣泛使用的位置隱私保護方法,它通常將若干個生成的假位置數(shù)據(jù)以及用戶的實際位置發(fā)送給SC服務(wù)器來迷惑攻擊者。SC服務(wù)器對所有接收到的位置數(shù)據(jù)進行任務(wù)匹配。在這種情況下,由于SC服務(wù)器無法區(qū)分真實位置和錯誤位置數(shù)據(jù),因此工人位置的隱私信息得以有效地保護。但是,這種模式下的空間眾包任務(wù)匹配效率太低,無法滿足當(dāng)前的任務(wù)需求。為了解決這個問題,提出一種新的位置隱私保護模型,該模型考慮了從眾包工人到任務(wù)所需的行進距離,通過將偽位置(3個虛擬位置的質(zhì)心點)發(fā)送給SC服務(wù)器,而不是發(fā)送真實位置來隱藏人群工人的真實位置。而任務(wù)將根據(jù)偽位置成功分配。

當(dāng)每次眾包工人更新位置時,虛擬位置可以通過隨機生成3個虛擬位置的質(zhì)心計算得到。但是,該方式獲得的虛擬位置比較任意,可控性低,且與任務(wù)的匹配性差。為了能夠在空間眾包中采用虛擬計算生成位置,并滿足真實位置匿名區(qū)域的要求,本文設(shè)計一種虛擬位置生成算法,該算法通過設(shè)定約束條件將隨機產(chǎn)生的虛擬位置限定在一定的范圍內(nèi)。圖2給出了虛擬位置生成算法及應(yīng)用流程。

圖2 虛擬位置生成及應(yīng)用流程

所提出的虛擬位置生成算法計算過程如下:首先確定眾包工人的實際位置h(xh,yh);其次根據(jù)實際位置設(shè)定一個范圍區(qū)間,假定設(shè)置的單位尺度為R,則虛假位置的范圍為以實際位置為圓心、3R為半徑的圓內(nèi)。然后,在設(shè)定的范圍內(nèi)均勻地劃分28個位置點用于構(gòu)造虛擬點集合,其中位于水平或垂直方向的相鄰2點的距離為R;最后,從虛擬點集合中依次地隨機選出A、B和C三個點,為了避免重復(fù),選擇下一個點時將已被選擇的點移出集合。虛擬位置生成算法在眾包工人的設(shè)備上本地運行,以便在沒有第三方參與的情況下訪問他們的確切位置。舉例說明,當(dāng)眾包工人在本地設(shè)備中將R設(shè)定為300 m,則意味著生成的虛假位置的最大可能距離在距離工人實際位置900 m的半徑范圍內(nèi),并且所有虛假位置都位于最大可能距離區(qū)域內(nèi)。

2.2 基于動態(tài)批次處理的任務(wù)分配模型

空間眾包中的中心問題是任務(wù)分配,任務(wù)分配旨在將任務(wù)分配給合適的工人,以使分配的任務(wù)和工人的總加權(quán)值最大化或工人的總移動距離最小化。一般而言,空間眾包中的任務(wù)和工作可能會動態(tài)出現(xiàn),任務(wù)分配需要立即或在短時間內(nèi)執(zhí)行,即動態(tài)任務(wù)分配(Dynamic Task Assignment, DTA),其定義如下:假定空間眾包平臺中的任務(wù)集合和工人集合表示為T={t1,t2,…,tn}、W={w1,w2,…,wm},平臺初始化時沒有任何任務(wù),且工人和任務(wù)會隨時動態(tài)到達(dá)。 DTA問題是要在任務(wù)和工人之間找到滿足時空約束和不變約束的分配策略M,使得總效用U最大化或使總移動成本C最小化。

DTA通常分為實時模式和批處理模式。實時模式幾乎無法確保分配效率,因為分配后通常會出現(xiàn)更好的匹配對象。如今,大多數(shù)方法都通過設(shè)置特定的時間窗口值來將批處理模式用作固定框架,如圖3所示。本文模型使用批處理匹配方法分配任務(wù)。系統(tǒng)將在短時間內(nèi)保留當(dāng)前請求,以允許其他請求出現(xiàn)在系統(tǒng)中以生成批處理。由于任務(wù)包含不同的類型,且工人具有不同的專業(yè)知識,因此,本文采用最大分?jǐn)?shù)分配(Maximum Score Assignment, MSA)策略來探索任務(wù)分配問題。

圖3 動態(tài)任務(wù)分配的匹配模式

假定sp表示第p個任務(wù)分配時的分?jǐn)?shù),用于衡量系統(tǒng)分配任務(wù)的質(zhì)量。若眾包工人具備的技能與任務(wù)類型吻合,則會得到較高的sp分?jǐn)?shù),否則得到較低的sp分?jǐn)?shù)。給定一個包含若干個時刻的時間段Time={time1,time2,…},Si表示時刻timei內(nèi)所有匹配任務(wù)的分?jǐn)?shù)之和:

(2)

式中:q表示timei內(nèi)任務(wù)匹配數(shù)。則時間段Time內(nèi)的總分?jǐn)?shù)為:

(3)

MSA問題就是使時間段Time內(nèi)任務(wù)分配的總分?jǐn)?shù)最大化。此外,本文將工人的出行距離納入分配過程中,以最大程度地減少工人的總出行距離。通過計算工人w和空間任務(wù)t之間的歐氏距離,將距離近的工人賦予較高的優(yōu)先級。下面給出任務(wù)匹配模型的目標(biāo)和約束函數(shù):

(4)

式中:cj,k和wj,k分別表示工人wj和空間任務(wù)tk之間的距離和得分;xj,k表示狀態(tài)函數(shù)。xj,k定義為:

(5)

由于目標(biāo)函數(shù)和所有約束條件都是線性的,屬于二次規(guī)劃問題,因此,本文使用CPLEX求解器在多項式時間內(nèi)求解此優(yōu)化問題。

值得注意的是,當(dāng)前大多數(shù)分配方法采用的是固定批處理大小,這在一定程度上影響了任務(wù)分配的效果。因此,本文采用動態(tài)批量模型,通過設(shè)置一系列的批量大小和一定的策略,使平臺達(dá)到最小平均等待時間。其中,等待時間定義為平臺預(yù)設(shè)的批量時間bs和工人在路上花費的旅行時間Δτ之和:

τ=bs+Δτ

(6)

假定在給定的時間段Time內(nèi),未知數(shù)量的工人和任務(wù)將以隨機順序動態(tài)地出現(xiàn)在平臺上。平臺需要將時間段Time分成g個批量BS={bs1,bs2,…,bsg},其大小可以不同。在每個批處理開始時,平臺生成一個任務(wù)分配實例集O,即包括所有可用的工人W和任務(wù)集合T的動態(tài)二分圖。一旦此批處理結(jié)束,O中匹配成功的工人和任務(wù)將分別從W和R中移除。

為了找到分割批量的最佳策略,本文應(yīng)用ε-貪婪算法進行求解。ε-貪婪算法是一種強化學(xué)習(xí)方法,主要通過在環(huán)境中采取動作,來最大化某累計獎賞。由于動態(tài)批量模型是一個順序決策問題,因此將批量拆分過程建模為參數(shù)未知的馬爾可夫決策過程(Markov Decision Process, MDP)。因而,將O組成的動態(tài)二分圖作為狀態(tài)空間,時間段Time內(nèi)分成的g個批量BS作為行動空間,等待時間作為獎賞函數(shù)。則基于強化學(xué)習(xí)的批量分割可以描述為:個體處于環(huán)境E中,狀態(tài)空間為O,其中每個狀態(tài)o∈O是個體感知到的環(huán)境的描述,個體采取的某個動作bs∈BS作用在當(dāng)前狀態(tài)o上,環(huán)境會根據(jù)當(dāng)前批量大小時的等待時間對個體進行反饋。算法1給出了基于ε-貪婪算法的動態(tài)批量模型。

算法1基于ε-貪婪算法的動態(tài)批量模型

輸入:批量集合BS,時間段Time,獎賞列表R,探索概率ε。

輸出:任務(wù)分配結(jié)果L。

i=1;timei=0

Whiletimei

if rand()<ε

bs從BS中隨機選擇;

else

bs取獎賞列表R中最小等待時間對應(yīng)的批量大小;

end

count(i)=0; τi=0

for 對于timei～timei+bs內(nèi)的工人W和任務(wù)Tdo

利用式(4)將任務(wù)tk分配給工人wj;

L←L∪〈wj,tk,timei〉

利用式(6)計算匹配成功用戶的等待時間τjk;

τi=τi+τjk;

count(i)= count(i)+1

end

τi=τi/ count(i)

利用τi更新獎賞列表R中的最小平均等待時間;

timei=timei+bs

i=i+1

end

3 實 驗

為了驗證本文方法的有效性,本文在Yelp和Foursquare兩個真實數(shù)據(jù)集[14]進行了多個測試。首先評估了引入的位置隱私方法的性能,其次是動態(tài)批處理的空間任務(wù)分配方法進行了評估。所有實驗在環(huán)境為Windows 10系統(tǒng),Intel Core i7-7700 CPU @ 3.60 GHz,RAM 32 GB的電腦中運行,算法是使用Python中的開源庫實現(xiàn)的。

3.1 實驗數(shù)據(jù)集

本文選取了兩個真實數(shù)據(jù)集Yelp和Foursquare進行實驗。Yelp數(shù)據(jù)集是從人口稀疏地區(qū)收集的真實數(shù)據(jù)集,該數(shù)據(jù)集對應(yīng)于亞利桑那州鳳凰城中用戶對餐館評論的集合,包含有70 817個用戶,15 583家餐廳的位置、在不同位置的11 434個簽到位置。在此實驗中,假設(shè)數(shù)據(jù)集中的用戶是將簽到作為其真實位置的眾包工人,而餐廳則被視為空間目標(biāo)任務(wù)位置。Foursquare數(shù)據(jù)集是從人口稠密地區(qū)收集的另一個數(shù)據(jù)集,該數(shù)據(jù)集包含了從2012年4月到2013年2月紐約市的1 083個用戶、38 333個地點和227 428個簽到。用戶被假設(shè)為眾包工人,他們最后一次的簽到被認(rèn)為是真實的地點,與簽到關(guān)聯(lián)的位置被視為任務(wù)位置。

3.2 結(jié)果分析

首先,以Yelp數(shù)據(jù)集為例,驗證位置隱私方法的有效性。圖4給出了不同的單位尺度為R時用戶虛擬位置的分布情況,其中橫坐標(biāo)為虛擬位置和真實位置之間的間距,縱坐標(biāo)為某一距離區(qū)間內(nèi)的用戶比例?？梢钥闯?當(dāng)R=200 m時,工人的虛擬位置大多位于真實位置的附件,沒有有效地實現(xiàn)真實位置的隱藏。相對而言,當(dāng)R=300 m時,工人的虛擬位置分布向間距更大的區(qū)間偏移,從而能夠?qū)崿F(xiàn)真實位置的隱藏。

圖4 不同單位尺度時虛擬位置的分布

由于本文方法引入了虛擬位置,使得眾包工人在接收到空間任務(wù)后存在一定的行進距離誤差TDE,由式(10)給出:

TDE=|dh-dp|

(7)

(8)

式中:dh和dp分別表示真實位置和虛擬位置與任務(wù)位置之間的距離;ER表示誤差率,即距離誤差占真實行進距離的比例。為了探討TDE對SC服務(wù)器任務(wù)分配的影響,進行了第二個實驗。該實驗選擇R=300,通過設(shè)定工人愿意接受任務(wù)的最大行進距離MTD進行測試,結(jié)果如圖5所示。可以看到,利用真實位置時計算的行進距離誤差率為零,這是可以預(yù)期的。而對于虛擬位置,結(jié)果表明,隨著工人和任務(wù)之間MTD的增加,ER呈下降趨勢,且MTD超過1 km后行進距離誤差率降到2%以內(nèi)的可接受范圍內(nèi),從而說明本文方法計算的虛擬位置在較長距離的任務(wù)分配中影響較小。

圖5 行進距離對任務(wù)分配的影響

第三個實驗在Yelp數(shù)據(jù)集上驗證動態(tài)批量處理對眾包任務(wù)分配的影響。圖6給出了不同固定批量大小時用戶的平均等待時間,其中一個批量的時間單元為10 s。從整體變化趨勢來看,隨著批次大小的增加,平均等待時間先呈下降趨勢,到一定程度后,有上升趨勢。這是因為初始批量太小,無法積累大量的對象進行分配,從而可能將任務(wù)分配給距離較遠(yuǎn)的工人,從而導(dǎo)致分配不合理。同時,如果批量過大,即使每個用戶都更有可能被分配到附近的工作人員,但用戶將花費太多時間等待分配,用戶對平臺的滿意度可能會急劇下降。因此,在這些批量之間必須存在一個最佳臨界點。從圖6中可以看到,本文算法得到的平均等待時間明顯優(yōu)于固定批量大小的最佳效果。

圖6 固定批量和動態(tài)批量的平均等待時間對比

為了進一步驗證本文方法對用戶體驗性的增強效果,將Yelp數(shù)據(jù)集上的測試結(jié)果與TASC方法、DBGM方法、PTA方法進行對比,結(jié)果如圖7所示?？梢钥闯?相較于TASC方法和DBGM方法,本文方法具有一定的優(yōu)勢,能夠以較少的等待時間來增強用戶體驗。在所有對比方法中,PTA方法獲得最佳效果,其原因是該方法采用多個深度學(xué)習(xí)模型通過考慮當(dāng)前工人和任務(wù)位置變化情況來預(yù)測未來工作者的位置和路徑,并使用圖嵌入技術(shù)來估計未來任務(wù)的分布,進而獲得未來可能的最優(yōu)匹配,同時降低了用戶等待時間。

圖7 不同方法下的用戶等待時間

4 結(jié) 語

本文提出一種面向位置隱私保護的空間眾包任務(wù)分配方法,用于解決當(dāng)前空間任務(wù)分配方法中不關(guān)心用戶體驗和工人隱私的問題。為了避免SC服務(wù)器泄露工人位置隱私的現(xiàn)象發(fā)生,本文方法使用虛擬技術(shù)為工人提供了一個虛擬位置,用于替代真實位置。此外,本文使用基于ε-貪婪算法的自適應(yīng)批處理機制將批量匹配方法應(yīng)用于最大分?jǐn)?shù)的空間眾包任務(wù)分配中,以最小化用戶的平均等待時間和工人的行進距離來實現(xiàn)用戶體驗的提高和工人成本的降低。實驗結(jié)果表明,本文方法在保持工人位置隱私的同時提高了任務(wù)分配效率。