基于連續(xù)最鄰近查詢的緩存位置隱私保護算法*

賈媛媛, 史志才, 方 凱, 許華根

(1.上海工程技術(shù)大學(xué) 電子電氣工程學(xué)院,上海201620;2.上海市信息安全綜合管理技術(shù)研究重點實驗室,上海 200240)

0 引 言

隨著移動物聯(lián)網(wǎng)的迅速發(fā)展,移動終端設(shè)備、無線傳感器網(wǎng)絡(luò)定位技術(shù)的興起[1],基于位置服務(wù)(location-based service,LBS)為人們帶來了巨大便利?？臻g查詢是最重要的LBS之一。根據(jù)空間限制,空間查詢可以分為最近鄰(nearest neighbor,NN)查詢和R范圍查詢(R range query)[2]。

為了避免空間位置查詢暴露移動用戶的敏感信息,文獻(xiàn)[3]中提出將查詢結(jié)果和相應(yīng)的有效區(qū)域(VR)緩存在客戶端緩存中,以緩解上述問題。在文獻(xiàn)[4]提出在移動客戶端和LBS服務(wù)器之間部署代理以構(gòu)建有效區(qū)域(EVR)。其中代理提供估計的EVR,通過緩存基于先前查詢創(chuàng)建的EVR來回答對相同對象感興趣的后續(xù)查詢。盡管文獻(xiàn)[4]中的代理部署和EVR成功設(shè)置完成,但是NN查詢的EVR增長緩慢,導(dǎo)致較低的緩存命中率。文獻(xiàn)[5]通過使用基于希爾—伯特曲線的分布式索引對無線廣播系統(tǒng)中的窗口進行查詢,但是沒有考慮保護用戶的位置隱私。目前針對連續(xù)查詢位置隱私保護問題,主要分為兩類結(jié)構(gòu)[6]：點對點和基于可信第三方(trusted third party,TTP)的中心服務(wù)器結(jié)構(gòu)。

為了避免客戶端計算量過大,本文提出計算包含NN結(jié)果的候選集框任務(wù)由第三方可信匿名服務(wù)器承擔(dān)。

1 系統(tǒng)架構(gòu)

采用基于第三方可信匿名服務(wù)器的系統(tǒng)架構(gòu)。系統(tǒng)架構(gòu)由三部分組成：1)LBS服務(wù)器。 2)第三方可信匿名服務(wù)器。 3)移動客戶端。如圖1所示。

圖1 系統(tǒng)架構(gòu)

2 EVR樹

第三方可信服務(wù)器基于NN查詢歷史記錄和可用數(shù)據(jù)對象構(gòu)建NN查詢的EVR。它維護一個對象高速緩存和一個索引結(jié)構(gòu)：用于NN查詢的EVR樹,如圖2所示。EVR樹是由EVR組成的R樹,其中每個EVR都包裹在最小邊界框(MBR)中。EVR由相對于數(shù)據(jù)對象的區(qū)域頂點和指向高速緩存中相應(yīng)對象的指針組成。緩存對象包含以下信息{ID,(x,y),eID,cell_flag,Object_info}。假設(shè)每個數(shù)據(jù)對象p具有唯一的ID。(x,y)是p的二維坐標(biāo)。eID表示相應(yīng)EVR的ID,而cell_flag表示p是否位于完全緩存的單元中。Object_info中的對象包含p的基本信息。例如,餐館包括烹飪類型,營業(yè)時間,電話號碼等。當(dāng)將p的EVR插入EVR樹時,將更新相應(yīng)對象的eID。類似地,一旦p所在的覆蓋單元變?yōu)橥耆咚倬彺?則cell_flag設(shè)置為true。使用該信息,當(dāng)必須替換p時,可以從EVR樹中移除相應(yīng)的EVR或?qū)⑼耆彺娴膯卧謴?fù)為未緩存。

圖2 EVR樹索引

3 NN查詢緩存位置隱私保護方法

3.1 總體方法

當(dāng)接收到NN查詢時,第三方服務(wù)器首先嘗試使用EVR樹來回答查詢。如果匿名服務(wù)器不能回答查詢,通過虛擬選擇算法向LBS服務(wù)器提交一個或兩個2NN查詢。將接收到的NN查詢擴展為2NN查詢的基本原理是,根據(jù)文獻(xiàn)[7]的理論結(jié)果,最近的對象和第二最近的對象之間的距離有利于構(gòu)建最近對象的EVR。通過利用LBS服務(wù)器返回的對象,可以擴展現(xiàn)有的對象或創(chuàng)建新的EVR。這里給定一個對象p,它的EVR用EVR(p)表示。第三方可信匿名服務(wù)器執(zhí)行的處理步驟如下：

步驟1 匿名服務(wù)器通過執(zhí)行一般的R樹搜索操作來檢查NN查詢位置(xq,yq)是否在EVR樹的任何EVR中。如果是,請轉(zhuǎn)到步驟7。

步驟2 匿名服務(wù)器將收到的NN查詢擴展為具有相同查詢位置(xq,yq)的2NN查詢,并將2NN查詢通過虛擬選擇算法形成空間k—匿名區(qū)域提交給LBS服務(wù)器。令p1和p2分別為q的最近和第二近的對象。

步驟3 位置服務(wù)提供商從數(shù)據(jù)庫中查詢用戶查詢范圍內(nèi)的POI,獲取查詢結(jié)果,并將其返回給匿名器,當(dāng)從LBS服務(wù)器獲取p1和p2時,匿名服務(wù)器在EVR樹中搜索EVR(p1)。如果找到EVR(p1),請轉(zhuǎn)到步驟6。

步驟4 可信匿名服務(wù)器生成另一個帶查詢位置(x1,y1)的2NN查詢,其中(x1,y1)是p1的位置。顯然,(x1,y1)最近的對象是p1。設(shè)第二個最近的對象(x1,y1)為p3,運行算法EVR-Creation以基于p1,p2和p3創(chuàng)建p1的EVR。

步驟5 將p1和EVR(p1)分別插入對象緩存和EVR樹。轉(zhuǎn)到步驟7。

步驟6 使用q,p1和p2,以及算法EVR-Extension擴展現(xiàn)有EVR(p1)。將更新的EVR(p1)重新插入EVR樹。

步驟7 匿名服務(wù)器將應(yīng)答對象p1和相應(yīng)的EVR(p1)返回給移動客戶端。

3.2 EVR創(chuàng)建

當(dāng)EVR樹索引不能回答具有位置(xq,yq)的NN查詢時,匿名服務(wù)器將為查詢對象p1創(chuàng)建一個新的EVR,如下所示。首先,將NN查詢擴展為2NN查詢,并將2NN查詢通過虛擬選擇算法提交給LBS服務(wù)器。在獲得2NN查詢的對象p1和p2(其中dis(q,p1)< dis(q,p2))之后,可信匿名服務(wù)器首先通過建立一個以q為中心的圓C1來創(chuàng)建EVR。作為半徑,其中r1=(dis(q,p2)- dis(q,p1))/2。設(shè)p1的位置為(x1,y1)。接下來,將另一個具有查詢位置(x1,y1)的2NN查詢提交到LBS服務(wù)器。顯然,最接近位置(x1,y1)的對象是p1。讓這個新的2NN查詢的第二個最接近的對象是位置為(x3,y3)的p3。類似地,如圖3所示,匿名服務(wù)器以中心(x1,y1)和半徑r2構(gòu)建另一個圓C2,其中r2=dis(p1,p3)/2。然后,以q為原點,以θ為q與p1之間的夾角,創(chuàng)建7個頂點V1(xnew1,ynew1),V2(xnew2,ynew2),V3(xnew3,ynew3),V4(xnew4,ynew4),V5(xnew5,ynew5),V6(xnew6,ynew6)和V7(xnew7,ynew7)由以下等式表示

圖3 EVR的創(chuàng)建

xnew1=xq+r1cos(θ+π/2),ynew1=yq+r1sin(θ+π/2)

xnew2=xq+r1cos(θ-π/2),ynew2=yq+r1sin(θ-π/2)

xnew3=xq+r1cos(θ+3π/4),ynew3=yq+r1sin(θ+3π/4)

xnew4=xq+r1cos(θ-3π/4),ynew4=yq+r1sin(θ-3π/4)

xnew5=xq+r1cos(θ+π),ynew5=yq+r1sin(θ+π)

xnew6=x1+r2cos(θ-π/2),ynew6=y1+r2sin(θ-π/2)

xnew7=x1+r2cos(θ+π/2),ynew7=y1+r2sin(θ+π/2)

3.3 EVR擴建

如前所述,當(dāng)匿名服務(wù)器接收到提交的2NN查詢位置為(x1,y1)的對象p1和位置為(x2,y2)的對象p2時,它首先檢查是否緩存了EVR(p1)。如果是,則通過以下步驟調(diào)用算法EVR-Extension以更新EVR。首先,匿名服務(wù)器從EVR樹中檢索現(xiàn)有的EVR(p1)。讓(xold,yold)為EVR(p1)的形心,并按照3.2節(jié)中給出的方法構(gòu)建圓C1,如圖4所示。

圖4 EVR創(chuàng)建

以(xold,yold)作為原點,θ作為q與p1之間的夾角,進行計算,如圖5所示。如下確定5個頂點v1(xext1,yext1),v2(xext2,yext2),v3(xext3,yext3),v4(xext4,yext4)和v5(xext5,yext5)的坐標(biāo)。然后,使用5個頂點v1,v2,v3,v4和v5擴展原始EVR(p1)。5個頂點坐標(biāo)確定如下

圖5 EVR的擴展

xext1=xq+r1cos(θ+π/2),yext1=yq+r1sin(θ+π/2)

xext2=xq+r1cos(θ-π/2),yext2=yq+r1sin(θ-π/2)

xext3=xq+r1cos(θ+3π/4),yext3=yq+r1sin(θ+3π/4)

xext4=xq+r1cos(θ-3π/4),yext4=yq+r1sin(θ-3π/4)

xext5=xq+r1cos(θ+π),yext5=yq+r1sin(θ+π)

由于更新后的EVR可能會變成凹面多邊形,因此,采用Melkman算法計算更新后的EVR的凸面多邊形,以刪除不必要的頂點并獲得更大的區(qū)域大小。凸多邊形用作p1的最終更新EVR。可以參考文獻(xiàn)[8]獲得所提出算法的證明。

3.4 虛擬選擇算法

本文提出一種虛擬選擇算法增強用戶隱私。根據(jù)用戶需要查詢的單元格,生成實際的虛擬位置,匿名器選擇K個單元形成隱藏區(qū)域,該區(qū)域可以隱藏真實用戶的位置,以混淆不受信任的LBS服務(wù)器。從單元格中選擇虛擬位置。在此算法中,Cr是真實位置；k是k—匿名相關(guān)的輸出集的大??；Cp是包含所有候選單元格的集合,C是包含當(dāng)前實際位置和k-1個所選虛擬位置的輸出集。在算法開始時,用戶Alice需要將集合R中的所有單元格與M進行比較,并獲得集合Cp。此后,Alice可以從Cp中隨機選擇k-1個單元格作為其虛擬位置。將k-1個選定的單元格和Cr組合在一起作為輸出集C。

虛擬選擇算法：

Input:R,M,n,Cr,k

Output:C

1)for (i=1;i≤n2,i≠r;i++) do

2)if (Ci?M) then

3)Ci→Cp;

4)end if

5)end for

6)Cr→C;

7)selectk-1 cells fromCprandomly→C。

4 實驗性能與安全性分析

4.1 實驗環(huán)境

算法采用Java實現(xiàn),實驗運行平臺為Windows 7操作系統(tǒng),Intel?CoreTMi5—8265U處理器、8GB內(nèi)存,實驗數(shù)據(jù)采用研究業(yè)界認(rèn)可的Thomas Brinkhoff路網(wǎng)數(shù)據(jù)生成器[9],輸入德國Oldenburg城市的交通網(wǎng)絡(luò)圖。EVR樹的大小設(shè)置為服務(wù)器緩存大小的22 %。參照了文獻(xiàn)[10]中的移動模型對仿真參數(shù)進行設(shè)置。

這里使用兩個性能指標(biāo)：客戶端緩存命中率和服務(wù)器負(fù)載?？蛻舳司彺婷新时硎揪彺娴腅VR和VR在移動客戶端的有效性以及移動設(shè)備資源消耗。服務(wù)器負(fù)載定義為LBS服務(wù)器上的總計算時間。

4.2 緩存命中率的分析

主要針對本方案中的緩存命中率分析。將本文提出的算法與文獻(xiàn)[11]中的LDQ算法進行對比,實驗結(jié)果表明客戶端緩存命中率隨著緩存大小的增加而增加,如圖6(a),這與實際相符。對于NN查詢,如圖6(b),移動速度快會降低緩存命中率。這是因為移動速度越高,移動客戶端越頻繁地移出緩存的EVR或VR,從而提交更多查詢。但是,與LDQ算法相比,本文方法優(yōu)勢明顯。

圖6 兩種算法緩存命中率結(jié)果分析

4.3 服務(wù)器負(fù)載分析

如圖7(a)所示,隨著移動速度的增加,服務(wù)器負(fù)載逐漸變大,由于用戶提交更多查詢,客戶端緩存的命中率低,LDQ算法在所有移動速度下均表現(xiàn)不佳。服務(wù)器端負(fù)載隨著緩存大小的增加而減少,如圖7(b),這是因為本文方法使用緩存對象可以直接回答許多客戶端的查詢,從而降低服務(wù)器負(fù)載。

圖7 服務(wù)器負(fù)載對比結(jié)果分析

4.4 安全性分析

當(dāng)用戶向位置服務(wù)提供商發(fā)送查詢請求,并且匿名器端緩存所有結(jié)果數(shù)據(jù)時,用戶直接從緩存中提取 POIs。在此過程中,用戶不會與位置服務(wù)提供商進行交互,位置服務(wù)提供商無法從用戶獲取任何信息。

如果用戶無法獲取緩存中的結(jié)果數(shù)據(jù),則匿名器將形成隱藏區(qū)域并發(fā)送給位置服務(wù)器。即使位置服務(wù)器識別隱藏區(qū)域中的所有用戶,但隱藏區(qū)域至少有k個用戶,因此它可以猜測指定用戶的概率只有1/k。

5 結(jié)束語

本文提出一種基于緩存候選結(jié)果集的連續(xù)位置隱私保護方法,利用緩存思想和基于虛擬選擇算法進行k—匿名技術(shù),減少用戶與 LBS 服務(wù)之間的交互。實驗結(jié)果顯示,與LDQ方案比較,本文算法能減少 LBS 服務(wù)器的開銷,提高緩存命中率,但本文虛擬選擇算法選擇以前未查詢過的虛擬位置。因此,在下一步工作中,將會考慮從單元中選擇對緩存率有更多貢獻(xiàn)的位置產(chǎn)生虛擬位置,以進一步提高用戶的位置隱私。