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

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

0 引 言

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

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

為了避免客戶(hù)端計(jì)算量過(guò)大,本文提出計(jì)算包含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)移動(dòng)客戶(hù)端。如圖1所示。

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

2 EVR樹(shù)

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

圖2 EVR樹(shù)索引

3 NN查詢(xún)緩存位置隱私保護(hù)方法

3.1 總體方法

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

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

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

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

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

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

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

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

3.2 EVR創(chuàng)建

當(dāng)EVR樹(shù)索引不能回答具有位置(xq,yq)的NN查詢(xún)時(shí),匿名服務(wù)器將為查詢(xún)對(duì)象p1創(chuàng)建一個(gè)新的EVR,如下所示。首先,將NN查詢(xún)擴(kuò)展為2NN查詢(xún),并將2NN查詢(xún)通過(guò)虛擬選擇算法提交給LBS服務(wù)器。在獲得2NN查詢(xún)的對(duì)象p1和p2(其中dis(q,p1)< dis(q,p2))之后,可信匿名服務(wù)器首先通過(guò)建立一個(gè)以q為中心的圓C1來(lái)創(chuàng)建EVR。作為半徑,其中r1=(dis(q,p2)- dis(q,p1))/2。設(shè)p1的位置為(x1,y1)。接下來(lái),將另一個(gè)具有查詢(xún)位置(x1,y1)的2NN查詢(xún)提交到LBS服務(wù)器。顯然,最接近位置(x1,y1)的對(duì)象是p1。讓這個(gè)新的2NN查詢(xún)的第二個(gè)最接近的對(duì)象是位置為(x3,y3)的p3。類(lèi)似地,如圖3所示,匿名服務(wù)器以中心(x1,y1)和半徑r2構(gòu)建另一個(gè)圓C2,其中r2=dis(p1,p3)/2。然后,以q為原點(diǎn),以θ為q與p1之間的夾角,創(chuàng)建7個(gè)頂點(diǎn)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擴(kuò)建

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

圖4 EVR創(chuàng)建

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

圖5 EVR的擴(kuò)展

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

3.4 虛擬選擇算法

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

4.1 實(shí)驗(yàn)環(huán)境

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

這里使用兩個(gè)性能指標(biāo)：客戶(hù)端緩存命中率和服務(wù)器負(fù)載?？蛻?hù)端緩存命中率表示緩存的EVR和VR在移動(dòng)客戶(hù)端的有效性以及移動(dòng)設(shè)備資源消耗。服務(wù)器負(fù)載定義為L(zhǎng)BS服務(wù)器上的總計(jì)算時(shí)間。

4.2 緩存命中率的分析

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

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

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

如圖7(a)所示,隨著移動(dòng)速度的增加,服務(wù)器負(fù)載逐漸變大,由于用戶(hù)提交更多查詢(xún),客戶(hù)端緩存的命中率低,LDQ算法在所有移動(dòng)速度下均表現(xiàn)不佳。服務(wù)器端負(fù)載隨著緩存大小的增加而減少,如圖7(b),這是因?yàn)楸疚姆椒ㄊ褂镁彺鎸?duì)象可以直接回答許多客戶(hù)端的查詢(xún),從而降低服務(wù)器負(fù)載。

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

4.4 安全性分析

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

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

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

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