朱順痣,黃 亮,周長利,馬 櫻

(1.廈門理工學院計算機與信息工程學院,福建廈門 361024;2.國家計算機網(wǎng)絡(luò)應急技術(shù)處理協(xié)調(diào)中心,北京 100029;3.華僑大學計算機科學與技術(shù)學院,福建廈門 361021)

?

一種基于興趣點分布的匿名框KNN查詢方法

朱順痣1,黃 亮2,周長利3,馬 櫻1

(1.廈門理工學院計算機與信息工程學院,福建廈門 361024;2.國家計算機網(wǎng)絡(luò)應急技術(shù)處理協(xié)調(diào)中心,北京 100029;3.華僑大學計算機科學與技術(shù)學院,福建廈門 361021)

針對利用匿名框?qū)崿F(xiàn)的興趣點K近鄰(KNN)查詢帶來的通信開銷大、時延長等問題,提出了基于單一興趣點Voronoi圖劃分和四叉樹層次化組織的KNN查詢方法.該方法根據(jù)興趣點層次信息有針對性的構(gòu)造查詢匿名框用來獲取詳細查詢信息,在保護位置隱私的同時,降低了查詢通信開銷,同時注入虛假查詢保護了用戶的真實查詢內(nèi)容隱私.最后分別采用模擬地理數(shù)據(jù)和真實地理數(shù)據(jù)進行理論分析和有效性驗證.

位置隱私;基于位置的服務(wù);匿名框;K近鄰查詢

1 引言

基于位置的服務(wù)(Location-Based Service,LBS)推動了移動智能終端各類型應用的快速發(fā)展.基于位置的查詢服務(wù)是目前廣泛被用戶使用的服務(wù)類型之一,用戶利用攜帶的智能終端獲取所需的查詢服務(wù),典型的兩種查詢方式分別為K近鄰(KNearest Neighbor,KNN)查詢和R范圍查詢[1～3].然而,用戶獲取查詢結(jié)果前必須提供自身位置信息,位置越精確查詢結(jié)果質(zhì)量越高,但用戶的隱私也越容易暴露.移動用戶隱私可以分為位置隱私和查詢內(nèi)容隱私兩類[4～8],在查詢過程中,理想查詢狀態(tài)是既不讓其它任何實體知道其所在位置,也不讓其它實體知道他的查詢內(nèi)容.位置k匿名[9～13]是實現(xiàn)位置隱私保護的有效方法之一,該方法構(gòu)造包含k個不同用戶位置的匿名框,用匿名框代替全部用戶實際位置發(fā)起查詢.對于查詢內(nèi)容隱私,用戶利用匿名框查詢時也需保證查詢請求內(nèi)容不少于l種[14],避免查詢內(nèi)容隱私直接泄露給如LBS服務(wù)器等其它實體.

然而,匿名框查詢需要返回匿名框內(nèi)及其周圍的多個興趣點作為候選集合供用戶選擇,這會增大數(shù)據(jù)通信開銷.這是因為上述傳統(tǒng)的構(gòu)造匿名框查詢方法并沒有考慮興趣點的分布情況.如圖1所示,用戶構(gòu)造了一個1NN查詢匿名框(虛線矩形框),根據(jù)該匿名框LBS返回給用戶uk的興趣點不僅包括P3,還有P1、P2、P4和P5,這些興趣點都可能是用戶查詢的目標.

Voronoi圖[15]是一種平面空間目標點之間的中垂線分割方法,如圖1實線劃分所示,利用該圖可以表示空間目標位置遠近關(guān)系.位于興趣點P3劃分單元(實線凸多邊形)內(nèi)的用戶uk一定距離P3最近.因此,在上述1NN查詢中,如果用戶知道興趣點的Voronoi劃分情況,則將目標興趣點P3置于匿名框內(nèi),并要求LBS服務(wù)器只查詢返回匿名框內(nèi)興趣點描述信息,因此無需返回傳統(tǒng)匿名框查詢要返回的其他興趣點P1、P2、P4和P5的描述信息.

文獻[16]提出了能夠解決上述問題的一種方案2PASS,然而該方法在擴展到KNN查詢過程中,由于將同一地圖中多類不同興趣點共同進行Voronoi圖劃分,使得用戶需要對比更多的其他類型興趣點來找到最近的K個目標興趣點.因此,本文提出單一興趣點Voronoi劃分方法,并利用四叉樹組織該圖,便于用戶快速找到KNN目標興趣點并構(gòu)造查詢匿名框,該方法能夠在降低通信開銷的同時,保護用戶位置隱私和查詢內(nèi)容隱私.

另一方面,用戶在提交查詢請求時為了保證身份信息與位置隱私的不可關(guān)聯(lián),通常使用假名來替代用戶真實身份.史敏儀等[17]針對文獻[18]中存在的假名失效的缺陷提出了敏感區(qū)域移動用戶的位置隱私保護方法.Palanisamy B[19]和Freudiger J[20]分別針對文獻[18]中存在的缺陷提出了相應的假名使用方法.Mano[21]等提出了一種動態(tài)假名更換方案,用來保護移動用戶的軌跡隱私.Yu等[22]提出了一種擴展假名更換區(qū)域MixGroup,顯著提高了假名在保護用戶位置隱私時的效能.Lin[23]在其著作中詳細論述了基于密碼技術(shù)的假名更換方法,用以有效保護用戶位置隱私.

2 預備知識

給定n個興趣點,可以利用Voronoi圖將其劃分成n個單元,鄰近單元間沒有重疊區(qū)域,位于劃分單元內(nèi)的用戶與該興趣點位置最近.如圖2所示,我們給每個頂點Pi賦予權(quán)值(Li,Ci),Li代表位置坐標,Ci代表興趣點的類型,如醫(yī)院、加油站等.

本文方法采用“用戶-服務(wù)器”架構(gòu)[20],該架構(gòu)用戶獲取LBS服務(wù)流程如圖3所示的四步.

如圖3所示,用戶首先請求輕量化興趣點分布信息,然后根據(jù)返回的信息構(gòu)造合適的匿名框,將要查詢的目標興趣點包含在匿名框內(nèi)發(fā)起查詢請求.用戶通過第3步控制匿名框內(nèi)興趣點數(shù)量,從而控制第4步返回消息數(shù)量.

3 興趣點KNN查詢

對于興趣點的1NN查詢,用戶只需要根據(jù)興趣點分布信息即可快速構(gòu)建匿名框,然而對于興趣點的KNN查詢則用戶需要比對較多的其他興趣點,K值越大比對的額外興趣點數(shù)量就會越多.解決該問題的方法就是構(gòu)造同類興趣點Voronoi圖劃分,并組織成輕量化、層次化的結(jié)構(gòu)發(fā)送給用戶,便于用戶快速查找到K個目標興趣點及其分布情況,這個工作是由LBS服務(wù)器來完成的.

3.1 四叉索引樹

對地理區(qū)域進行網(wǎng)格劃分是描述興趣點位置的有效方法之一,其中金字塔形的組織形式能夠體現(xiàn)平面空間區(qū)域間的層次化結(jié)構(gòu)[24].如圖4所示,從全局地圖出發(fā),將地理空間每次劃分成四個網(wǎng)格,如此迭代劃分下去得到4h-1個網(wǎng)格(h是劃分深度),直至滿足一定的粒度,并建立層次化索引表.圖4在全局地圖上將同類興趣點(如加油站)利用Voronoi圖劃分為4×4網(wǎng)格.

由此,每個興趣點唯一屬于一個網(wǎng)格,在網(wǎng)格劃分粒度不同時,一個網(wǎng)格可能會包含多個興趣點.通常情況下,在粒度較小時每個興趣點的劃分單元可能覆蓋多個網(wǎng)格,這意味著處于不同網(wǎng)格內(nèi)的用戶,可能處于同一個Voronoi劃分單元內(nèi),即在不同網(wǎng)格內(nèi)的用戶可能距離同一個興趣點最近.

這樣,每個網(wǎng)格都可以用和該網(wǎng)格有重疊部分的Voronoi劃分單元來表示,以便處于該網(wǎng)格的用戶能夠知道距離自己最近的興趣點是哪個.

由此,以金字塔形狀組織的興趣點可以表示成是一個四叉樹型的索引結(jié)構(gòu),每層網(wǎng)格以順時針方向為編號順序,如圖5描述了圖4的四叉樹結(jié)構(gòu),樹的葉子結(jié)點就是最底層網(wǎng)格,每個底層網(wǎng)格用與之有重疊區(qū)域的Voronoi劃分單元的興趣點來描述,便于處在該網(wǎng)格內(nèi)用戶掌握興趣點分布情況后構(gòu)造查詢匿名框.上述每類興趣點四叉索引樹可以用TreeCi表示,其中Ci表示興趣點類型.

每一層的每個網(wǎng)格都用其左上角坐標(xlt,ylt)和右下角坐標(xrb,yrb)表示,用戶確定自己所在最底層網(wǎng)格(即所在葉子結(jié)點),則執(zhí)行如下算法1,搜索四叉樹.

算法1 用戶所在結(jié)點查詢算法(用戶端)

輸入:以Ti為根結(jié)點的地圖四叉樹TreeCi,用戶位置坐標locuk,葉子結(jié)點網(wǎng)格面積Sleaf

輸出:四叉樹TreeCi的某個結(jié)點ni

1. Procedure begins:

2. 獲取根結(jié)點T的每個孩子結(jié)點ni

3. if孩子結(jié)點ni的面積>Sleafthen

4. for每個孩子結(jié)點ti∈Tdo

5. 由孩子結(jié)點范圍坐標(xlt,ylt)和(xrb,yrb)找到locuk所在網(wǎng)格及表示該網(wǎng)格的結(jié)點ni

6. TreeCi←ni為根結(jié)點的子樹

7. 調(diào)用算法1,參數(shù)為(TreeCi,locuk,Sleaf)

8. returnni

9. End Procedure

3.2KNN查詢流程

對于每一類興趣點,LBS服務(wù)器都為之構(gòu)造一個上一小節(jié)描述的興趣點分布四叉索引樹,用戶在第1步請求周圍興趣點分布信息時,在真實目標興趣點請求中注入虛假興趣點查詢請求,比如用戶目標興趣點是查詢周圍最近的K個加油站,同時注入餐廳、醫(yī)院興趣點分布情況查詢作為虛假請求.表1詳細說明了圖3中KNN查詢完整流程.請求格式為(uk1‖CT‖sigkeyu(CT)‖Ekeylbs(Quk)),其中uk1是用戶的一個假名,CT為當前時間,sigkeyu(CT)表示用戶利用私鑰keyu做的簽名,以便LBS服務(wù)器來驗證其合法性,Ekeylbs(Quk)表示用戶以LBS服務(wù)器的公鑰keylbs加密查詢請求Quk發(fā)送給LBS服務(wù)器,Quk=(C1,C2,…,C3)主要為查詢興趣點類型Ci,Quk中有一個是用戶真正要查詢的目標興趣點.

LBS收到用戶請求后,驗證簽名sigkeyu(CT)的合法性,據(jù)此解密出查詢請求Quk,并返回Quk中所有興趣點類型Ci的四叉索引樹,返回信息可表示為(LBSid‖TreeC1,TreeC2,…,TreeCn),其中TreeCi為用戶目標興趣點的四叉索引樹.

用戶根據(jù)LBS服務(wù)器返回信息,找到自己目標興趣點的四叉索引樹TreeCi,執(zhí)行算法1逐層搜索直至找到自己所在的網(wǎng)格,即葉子結(jié)點,根據(jù)葉子結(jié)點中存儲的興趣點權(quán)值Pi:(Li,Ci)信息找到距離自己最近的興趣點Pk,并以此為出發(fā)點根據(jù)3.3小節(jié)中定義1和定理1,找到距離Pk最近的其他K-1個興趣點,并構(gòu)造包含這K個興趣點的匿名框.

表1 KNN查詢流程表

用戶根據(jù)算法1返回的用戶所在網(wǎng)格結(jié)點ni來構(gòu)造匿名框,算法如算法2所示.

算法2K近鄰興趣點查找及匿名框生成算法(用戶端)

輸入:算法1返回的用戶所在網(wǎng)格結(jié)點ni,KNN查詢請求

輸出:包含K個目標興趣點在內(nèi)的匿名框CRuk

1. Procedure begins:

2. for 每個Pi∈nido //依據(jù)圖7找到ni內(nèi)興趣點

3. Array1←計算dist(uk,Pi)

4.p←min{Array} //用戶在最近Pi的劃分單元內(nèi)

5. heap←AN1(p)// 參見定義1; 小頂堆heap

6. Array2←AN1(p)

7. if |heap|

8. Array3←Array2

9. for 每個Pj∈Array3 do //下一階興趣點

10. heap←AN1(Pj)

11. Array4←AN1(Pj)

12. 清空Array2 //保存新找到的下一階興趣點

13. Array2←Array4

14. neighbor←在heap中找到前K個興趣點

15. 構(gòu)造包含neighbor中全部興趣點位置的矩形匿名框CRuk

16. returnCRuk

17. End Procedure

算法2的主要思想是以用戶所在Voronoi圖劃分單元的興趣點為起始點逐階搜索下一級興趣點,直至找到距離用戶最近的K個興趣點.圖4中的虛線框為根據(jù)算法2構(gòu)造的5NN匿名框.用戶在提交查詢時,不僅給出要查詢的匿名框內(nèi)目標興趣點,同時還要求返回幾類虛假查詢興趣點的描述信息,保護用戶查詢內(nèi)容隱私.在算法2的執(zhí)行過程中,執(zhí)行頻度最高的語句為第3、10和11行,其時間復雜度為O(n).顯然,空間復雜度也取決于問題規(guī)模n,為O(n).

3.3 性能分析

(1)查詢準確性

用戶根據(jù)自身位置確定所在網(wǎng)格(即算法1),然后根據(jù)所在網(wǎng)格找到所在興趣點Voronoi圖劃分單元(即找到距離自己最近的興趣點),并由此劃分單元逐步擴展到鄰近劃分單元確定最近的K個興趣點(即算法2)的過程中,需要保證兩個算法的正確性.

首先,在算法1中,用戶根據(jù)圖5 的LBS服務(wù)器返回的網(wǎng)格劃分信息及輕量興趣點分布信息,結(jié)合自身位置不斷縮小自己所在網(wǎng)格,直到滿足閾值Sleaf要求.由于在該過程中,用戶通過某一四叉樹的每個網(wǎng)格左上角坐標(xlt,ylt)和右下角坐標(xrb,yrb)運算,算法1第5行可以精確計算出用戶所在四個網(wǎng)格中的一個,然后以該網(wǎng)格為出發(fā)點迭代繼續(xù)確定所在下一級網(wǎng)格,此過程相對簡單.

然后,在算法2中,用戶根據(jù)圖5所示的網(wǎng)格和興趣點Voronoi圖層疊關(guān)系找到所在網(wǎng)格ni中的所有興趣點,確定距離自己最近的目標興趣點,并以此興趣點為生成元的Voronoi圖劃分單元V(Pi)為出發(fā)點,找到其他K-1個目標興趣點.在此過程中用戶根據(jù)如下定義1和定理1可以確定周圍1階鄰近興趣點集合,如果不足K個,則在2階鄰近興趣點集合繼續(xù)找,直到找到K個興趣點.

定義1 一般地,給定Voronoi圖內(nèi)任意興趣點Pi,如果其1階近鄰興趣點集合可以表示為:AN1(Pi)={Pk|V(Pi)與V(Pk)有公共邊},那么Pi的n(n≥2)階近鄰興趣點集為:ANn(Pi)={Pk|V(Pj)與V(Pk)有公共邊,Pj∈ANn-1(Pi)}.

定理1[25]Voronoi圖內(nèi)任意劃分單元V(Pi)內(nèi)任意點q的第K個近鄰興趣點一定包含在集合AN1(Pi)∪AN1(Pi)∪…∪ANk-1(Pi)中.

定理2[25]Voronoi圖內(nèi),每個劃分單元平均有6個1階鄰近劃分單元.

這個過程還存在一個問題,根據(jù)定理1,用戶在找K個興趣點的過程中,需要把V(Pi)的K階鄰近興趣點都找到(算法2第5～14行),這會帶來一定時延.通常情況下,由于多數(shù)用戶設(shè)置KNN興趣點查詢時,K通常取值為1～30,由定理2可知,當V(Pi)的鄰近單元及下一階鄰近單元數(shù)均約為6個時,則滿足6n≥30的最小正整數(shù)n為2,即查找用戶最近的K個目標興趣點,最少可在其所在劃分單元V(Pi)的2階近鄰興趣點集合中找到.

綜上,用戶在可以根據(jù)算法1和算法2確定自己所在網(wǎng)格和所在興趣點劃分單元,并在下限值為2階的鄰近劃分單元中找到K個目標興趣點,由于是逐層搜索鄰近興趣點,因此可以在保證較少通信量的同時獲得正確的K個興趣點查詢結(jié)果.然后構(gòu)造包含這K個興趣點的匿名框,發(fā)送給LBS服務(wù)器,LBS服務(wù)器返回匿名框中興趣點的詳細描述信息,因此查詢是有目標的,有效降低通信量.

(2)隱私安全性

和傳統(tǒng)匿名框方法實現(xiàn)的k匿名性不同,本方法用戶不必考慮匿名框中用戶數(shù)量.這是因為用戶在構(gòu)造匿名框時,可能不在匿名框內(nèi).當K=3時,圖6中的虛線匿名框可能是處于匿名框外用戶uk構(gòu)造的,因為匿名框只需覆蓋距離P5最近的其他2個興趣點P1、P3即可,不必考慮用戶位置.

因此本方法的k匿名性取決于匿名框覆蓋目標興趣點Voronoi圖劃分單元內(nèi)的用戶數(shù)量,假設(shè)在沒有注入虛假查詢的情況下,則查詢Qi來自該匿名框覆蓋CRk的某個劃分單元V(Pi)∈CRk的概率可以表示為pQi→V(Pi),則構(gòu)造該匿名框發(fā)起一次查詢Qi的信息熵可以用式(1)表示:

(1)

則處于劃分單元V(Pi)內(nèi)的用戶uk∈V(Pi)是提出該KNN查詢Qi的用戶的聯(lián)合信息熵可以用式(2)表示:

(2)

在現(xiàn)有文獻中通常認為背景知識包括用戶分布情況、用戶提交的興趣點查詢請求集合及各類興趣點四叉索引樹.由式(1)和(2)可知,即使攻擊者在掌握一定的背景知識情況下,能夠根據(jù)構(gòu)造的匿名框推斷出用戶真實查詢內(nèi)容,也很難將查詢內(nèi)容對應到劃分單元內(nèi)某個具體用戶身份上.

4 實驗

本實驗在Windows 7 平臺采用JAVA語言實現(xiàn)上述算法,硬件環(huán)境為3.2GHz Intel Core i5處理器,內(nèi)存大小為4GB.實驗地圖采用美國地名委員會提供的地理數(shù)據(jù)集GDS*http://geonames.usgs.gov/index.html,同時采用Thomas Brinkhoff路網(wǎng)移動節(jié)點數(shù)據(jù)生成器生成的模擬數(shù)據(jù)集TBS*http://iapg.jade-hs.de/personen/brinkhoff/generator/,數(shù)據(jù)集中包含15萬條路網(wǎng)環(huán)境下的用戶軌跡數(shù)據(jù),用戶均勻分布在每條路網(wǎng)上,每個用戶的起點和終點均隨機選取,行進速度受路段限制.LBS服務(wù)器與用戶采用3G網(wǎng)絡(luò)通信帶寬為2Mbps,實際每次返回單個數(shù)據(jù)包為128字節(jié),若每個興趣點信息占用8個字節(jié),除去40字節(jié)的包頭,每個數(shù)據(jù)包包含興趣點個數(shù)為 (128-40)/8=11個.當某一實驗參數(shù)變化時,其他參數(shù)配置均采用默認值配置.本實驗參數(shù)取值范圍及默認值如表2所示.

表2 實驗默認參數(shù)配置

4.1 匿名框構(gòu)造成功率

本文首先考察匿名框構(gòu)造成功率,即成功構(gòu)造匿名框用戶數(shù)量與用戶總數(shù)量之比.本文考察兩個參數(shù)對匿名框構(gòu)造成功率的影響:興趣點多樣性luk和區(qū)域內(nèi)PoI總數(shù)N.

如圖7(a)～(b)所示,當用戶為提高查詢內(nèi)容隱私保護強度而使興趣點多樣性參數(shù)luk不斷增大時,匿名框需要覆蓋更多類型的興趣點,因此匿名框構(gòu)造成功率隨之降低,但成功率通常維持在80%以上,而luk越大,用戶查詢內(nèi)容隱私保護效果越好.因此用戶在提出較高查詢內(nèi)容隱私保護強度時,本方法能夠保證較高的匿名框構(gòu)造成功率.

同理,當區(qū)域內(nèi)興趣點分布較為密集時,用戶更容易構(gòu)造滿足興趣點多樣性需求的匿名框.因此,當區(qū)域內(nèi)興趣點數(shù)量N不斷增加時,匿名成功率不斷提高,而TDS數(shù)據(jù)集的成功率總是高于GDS數(shù)據(jù)集,這是由于GDS數(shù)據(jù)集興趣點分布不均勻,使得用戶在特定區(qū)域內(nèi)興趣點類型不足造成的.

同時,匿名框構(gòu)造成功率直接影響查詢效率,這是由于LBS服務(wù)器需要根據(jù)用戶提交的匿名框為用戶查詢目標興趣點的詳細信息,本文所提出的兩個客戶端算法能否正確、快速運行是快速構(gòu)造高質(zhì)量匿名框的關(guān)鍵.通過實驗我們可以看出,匿名框構(gòu)造成功率較高,在LBS服務(wù)器根據(jù)匿名框返回查詢結(jié)果平均時間相同的情況下,本方法的查詢效率同樣較高.

4.2 平均數(shù)據(jù)通信量

數(shù)據(jù)通信量是指LBS返回查詢結(jié)果的信息量,本節(jié)將本文所提出的方法與LBS中的隱私保護經(jīng)典方法數(shù)據(jù)通信量進行比較.如圖8(a)～(b)所示.當興趣點多樣性luk要求增大時,Pyramid方法[24]和P2P方法[26]都需要找到更多的興趣點,并且由于沒有考慮興趣點的分布情況,查詢過程中返回的興趣點是盲目的,因此帶來了通信數(shù)據(jù)包量較高.本方法在考慮了興趣點分布情況后,使得查詢目的性更強,雖然通信量也隨著luk增長而增高,但本方法通信量明顯低于傳統(tǒng)方法.

同理,當用戶數(shù)量快速增加時,傳統(tǒng)方法數(shù)據(jù)通信量在數(shù)量增加后期快速增長,而本方法的平均數(shù)據(jù)通信量變化并不明顯,其原因是本方法返回的興趣點描述信息是固定的,數(shù)據(jù)通信量主要由定義的luk和K影響.此外,我們還對比了類似方法2PASS[16],如圖9所示,本方法與其取得了類似的通信量變化,比2PASS方法稍低,這是由于本方法采用單一興趣點Voronoi圖構(gòu)造方法,匿名框中虛假查詢興趣點類型用戶數(shù)是可以掌控的,使通信量相對較低.

4.3 查詢準確性

如前3.3小節(jié)所述,由于用戶的算法1和算法2的查找方式為基于Voronoi圖劃分單元的逐層遞進查找,當用戶查找K近鄰興趣點時,最大會查找某個劃分單元的K階鄰近單元,這會帶來通信量的極大上升,進而使有效時間內(nèi)獲取的準確查詢結(jié)果數(shù)量下降.但通過分析可以發(fā)現(xiàn),由于Voronoi圖的鄰近單元平均數(shù)量特點,使得在實際查找近鄰興趣點過程中通?？梢圆怀^2階近鄰單元就可以找到K個目標興趣點.

如圖10所示,當K值不斷增大時,表明用戶需要一次找到更多的鄰近興趣點,不同數(shù)量用戶分布在地圖空間時,查詢的準確率并沒有明顯的下降,而是穩(wěn)定在80%以上,這表明在K值不斷增大的查詢過程中,所有查詢均沒有查找K階鄰近單元,而是在2階鄰近單元內(nèi)找到了K個目標興趣點,從而使有效時間內(nèi)的查詢準確率保持穩(wěn)定,符合分析的結(jié)果.

通過類似方法,我們將本文所提出的方法與經(jīng)典方法2PASS、新近提出的類似查詢方法KAWCR[27]和Singoes[28]進行了比較,如圖11所示,發(fā)現(xiàn)本文方法具有同等較高的查詢準確率,且略高于經(jīng)典算法2PASS.

4.4 隱私安全性

信息熵是離散事件集合的平均信息量,通常,處在劃分單元V(Pi)內(nèi)的用戶,當構(gòu)造K=3的匿名框發(fā)起查詢時,如圖6所示,由劃分單元面積占總面積的比計算可得,真實發(fā)起查詢的用戶處于匿名框P1,P3,P5的概率分別約為0.4,0.3,0.3,則由式(1)計算可知其信息熵值約為H(Qi)=H(0.4,0.3,0.3)≈1.57bit,由此進一步可知,當用戶查詢的興趣點數(shù)量K增大時,其信息熵的變化如圖12所示.

由圖12可知,本方法構(gòu)造匿名框查詢的信息熵隨用戶查詢興趣點數(shù)量增大而穩(wěn)步增大,攻擊者對于匿名框查詢的不確定性隨之升高,隱私保護效果越好.導致信息熵升高的主要原因是,當K增大時,匿名框需要覆蓋的劃分單元數(shù)量增多,因此離散事件數(shù)量增大,并且更為重要的是,每個離散事件的概率分布相對均勻,使得攻擊者的不確定性不斷增加.而傳統(tǒng)構(gòu)造匿名框的方法Pyramid其信息熵基本保持穩(wěn)定,這是由于該方法未考慮興趣點分布,只構(gòu)造包含用戶在內(nèi)的匿名框造成的.

聯(lián)合信息熵是攻擊者確定處于某個劃分單元內(nèi)的用戶可能性的度量.由3.3節(jié)隱私安全性分析可知,從攻擊者角度看,要進一步確定某個單元內(nèi)用戶是否為真實發(fā)起查詢的用戶,其聯(lián)合信息熵值會進一步增加.這是由于處于某個劃分單元內(nèi)的用戶有多個,因此進一步增大了攻擊者的不確定性,使隱私保護性能更好.如圖13所示：本方法聯(lián)合信息熵值隨興趣點查詢數(shù)量增加而穩(wěn)步增加,符合性能分析的結(jié)果；Pyramid的聯(lián)合信息熵也略有增加,但是在K增長過程中依然保持穩(wěn)定,是此類方法沒有考慮興趣點分布所造成的缺陷.

5 結(jié)論及展望

為了提高KNN興趣點查詢效率,本文提出單一興趣點Voronoi圖劃分方法,該方法首先將同類興趣點劃分成Voronoi單元,然后利用四叉樹進行層次化組織,當用戶需要該信息時,將層次化信息發(fā)送給用戶,以便用戶快速找到KNN興趣點并構(gòu)造匿名框.最終,用戶向LBS服務(wù)器提交匿名框,并只返回匿名框內(nèi)幾類興趣點詳細描述信息.該方法一方面能夠有效降低興趣點返回數(shù)據(jù)包量、提高匿名框構(gòu)造速度,同時能夠保護用戶的位置隱私和查詢內(nèi)容隱私,性能分析和對比實驗表明,本方法具有良好的工作效率.

[1]Palanisamy B,Liu L,Lee K,et al.Anonymizing continuous queries with delay-tolerant mix-zones over road networks[J].Distributed and Parallel Databases,2014,32(1):91-118.

[2]周傲英,楊彬,金澈清,等.基于位置的服務(wù):架構(gòu)與進展[J].計算機學報,2011,34(7):1155-1171.

Zhou Aoying,Yang Bin,Jin Cheqing,et al.Location-based services:Architecture and progress[J].Chinese Journal of Computers,2011,34(7):1155-1171.(in Chinese)

[3]Ghinita G.Privacy for location-based services[J].Synthesis Lectures on Information Security,Privacy,& Trust,2013,4(1):1-85.

[4]葉阿勇,林少聰,馬建峰,等.一種主動擴散式的位置隱私保護方法[J].電子學報,2015,43(7):1362-1368.

Ye Ayong,Lin Shaocong,Ma Jianfeng,et al.An active diffusion based location privacy protection method[J].Acta Electronica Sinica,2015,43(7):1362-1368.(in Chinese)

[5]潘曉,郝興,孟小峰.基于位置服務(wù)中的連續(xù)查詢隱私保護研究[J].計算機研究與發(fā)展,2010,47(1):121-129.

Pan Xiao,Hao Xing,Meng Xiaofeng.Privacy preserving towards continuous query in location-based services[J].Journal of Computer Research and Development,2010,47(1):121-129.(in Chinese)

[6]劉華玲,鄭建國,孫辭海.基于貪心擾動的社交網(wǎng)絡(luò)隱私保護研究[J].電子學報,2013,41(8):1586-1591.

Liu Hualing,Zheng Jianguo,Sun Cihai.Privacy preserving in social networks based on greedy perturbation[J].Acta Electronica Sinica,2013,41(8):1586-1591.(in Chinese)

[7]唐科萍,許方恒,沈才樑,等.基于位置服務(wù)的研究綜述[J].計算機應用研究,2012,29(12):4432-4436.

Tang Keping,Xu Fangheng,Shen Caiheng,et al.Survey on location based service[J].Application Research on Computer,2012,29(12):4432-4436.(in Chinese)

[8]陳丹偉,邵菊,樊曉唯,等.基于MAH-ABE的云計算隱私保護訪問控制[J].電子學報,2014,42(4):821-827.

Chen Danwei,Shao Ju,Fan Xiaowei,et al.MAH-ABE based privacy access control in cloud computing[J].Acta Electronica Sinica,2014,42(4):821-827.(in Chinese)

[9]Hashem T,Kulik L,Zhang R.Countering overlapping rectangle privacy attack for moving kNN queries[J].Information Systems,2013,38(3):430-453.

[10]Ngo C N,Dang T K.On efficient processing of complicated cloaked region for location privacy aware nearest-neighbor queries[A].Proceedings of Information and Communication Technology[C].Berlin Heidelberg:Springer,2013.101-110.

[11]Chow C Y,Mokbel M F,Liu X.Spatial cloaking for anonymous location-based services in mobile peer-to-peer environments[J].GeoInformatica,2011,15(2):351-380.

[12]王麗娜,彭瑞卿,趙雨辰,等.個人移動數(shù)據(jù)收集中的多維軌跡匿名方法[J].電子學報,2013,41(8):1653-1659.

Wang Lina,Peng Ruiqing,Zhao Yuchen,et al.Multi-dimensional trajectory anonymity in collecting personal mobility data[J].Acta Electronica Sinica,2013,41(8):1653-1659.(in Chinese)

[13]徐建,徐明,林欣,等.路網(wǎng)限制環(huán)境中基于匿名蜂窩的位置隱私保護[J].浙江大學學報(工學版),2011,45(3):429-439.

Xu Jian,Xu Ming,Lin Xin,et al.Location privacy protection through anonymous cells in road network[J].Journal of Zhejiang University (Engineering Science),2011,34(5):865-878.(in Chinese)

[14]Pingley A,Zhang N,Fu X,et al.Protection of query privacy for continuous location based services[A].Proceedings of IEEE INFOCOM[C].USA:IEEE PRESS,2011.1710-1718.

[15]朱良,孫未未,荊一楠,等.基于Voronoi圖的路網(wǎng)k聚集最近鄰居節(jié)點查詢方法[J].計算機研究與發(fā)展,2011,48(z2):533-540.

Zhu Liang,Jing Yinan,Sun Weiwei,et al.Voronoi-based aggregate nearest neighbor query processing in road networks[J].Journal of Computer Research and Development,2011,48(z2):533-540.(in Chinese)

[16]Hu H,Xu J.2PASS:Bandwidth-optimized location cloaking for anonymous location-based services[J].IEEE Transactions on Parallel and Distributed Systems,2010,21(10):1458-1472.

[17]史敏儀,李玲娟.移動用戶位置隱私保護方案研究[J].計算機技術(shù)與發(fā)展,2014,51(10):151-154.

Shi Minyi,Li Lingjuan.Study on location privacy protection scheme for moving objects[J].Computer Technology and Development,2014,51(10):151-154.(in Chinese)

[18]Huang Leping,Yamane L,Mastsuura K,et al.Silent cascade:enhancing location privacy without communication QoS degradation[A].Proceedings of the 3rd International Conference on Security in Pervasive Computing[C].Berlin Heidelberg:Springer,2006.165-180.

[19]Palanisamy B,Liu L.Mobimix:Protecting location privacy with mix-zones over road networks[A].Proceeding of IEEE 27th International Conference on Data Engineering(ICDE)[C].Hannover:IEEE PRESS,2011.494-505.

[20]Freudiger J,Shokri R,Hubaux J P.On the optimal placement of mix zones[A].Privacy Enhancing Technologies[C].Berlin Heidelberg:Springer,2009.216-234.

[21]Mano K,Minami K,Maruyama H.Privacy-preserving publishing of pseudonym-based trajectory location data set[A].The Eighth International Conference on Availability,Reliability and Security (ARES)[C].USA:IEEE PRESS,2013.615-624.

[22]Yu R,Kang J,Huang X,et al.MixGroup:Accumulative pseudonym exchanging for location privacy preservation in vehicular social networks[J].IEEE Transactions on Dependable and Secure Computing,2015,PP(99):1-12.

[23]Xiaodong L,Rongxing L.Vehicular Ad Hoc Network Security and Privacy[M].Wiley:IEEE Press,2015.71-89.

[24]Mokbel M F,Chow C Y,Aref W G.The new Casper:query processing for location services without compromising privacy[A].Proceedings of the 32nd International Conference on Very Large Data Bases[C].USA:VLDB Endowment,2006.763-774.

[25]郝忠孝.時空數(shù)據(jù)庫新理論[M].北京:科學出版社,2011.

[26]Chow C Y,Mokbel M F,Liu X.Spatial cloaking for anonymous location-based services in mobile peer-to-peer environments[J].GeoInformatica,2011,15(2):351-380.

[27]Gong Z,Sun G Z,Xie X.Protecting privacy in location-based services using k-anonymity without cloaked region[A].The Eleventh International Conference on Mobile Data Management (MDM)[C].USA:IEEE Press,2010.366-371.

[28]Ma C,Zhou C,Yang S.A voronoi-based location privacy-preserving method for continuous query in LBS[J/OL].International Journal of Distributed Sensor Networks,2015,(2015):Article ID 326953.http://dx.doi.org/10.1155/2015/326953.

朱順痣 男,1973年7月出生,福建東山人,廈門大學博士,廈門理工學院計算機與信息工程學院教授、院長.主要研究領(lǐng)域為數(shù)據(jù)挖掘、信息推薦、隱私保護和系統(tǒng)工程.

E-mail:szzhu@xmut.edu.cn

黃 亮 男,1982年6月出生,湖南隆回人,中國科學院計算技術(shù)研究所博士.目前工作于國家計算機網(wǎng)絡(luò)應急技術(shù)處理協(xié)調(diào)中心,主要研究領(lǐng)域為無線資源管理、異構(gòu)網(wǎng)絡(luò)、集中式無線接入網(wǎng)絡(luò)、移動互聯(lián)網(wǎng).

周長利 男,1985年3月出生,黑龍江省哈爾濱人,哈爾濱工程大學博士,華僑大學計算機科學與技術(shù)學院講師.主要研究領(lǐng)域為位置隱私保護、網(wǎng)絡(luò)與信息安全.

E-mail:zhouchangli666@163.com

馬 櫻 男,1982年1月出生,湖南邵陽人,電子科技大學計算機系統(tǒng)結(jié)構(gòu)專業(yè)博士,廈門理工學院計算機與信息工程學院講師.主要研究方向為基于挖掘的軟件工程、大數(shù)據(jù)、云計算.

A Privacy-Preserving Method Based on PoIs Distribution Using Cloaking Region for K Nearest Neighbor Query

ZHU Shun-zhi1,HUANG Liang2,ZHOU Chang-li3,MA Ying1

(1.SchoolofComputerandInformationEngineering,XiamenUniversityofTechnology,Xiamen,Fujian361024,China;2.NationalComputerNetworkEmergencyResponseTechnicalTeamCoordinationCenterofChina,Beijing100029,China;3.SchoolofComputerScienceandTechnology,HuaqiaoUniversity,Xiamen,Fujian361021,China)

AchievingKNN query with traditional cloaking region brings higher communication cost and delay caused by useless points of interest (PoI) returned,a newKNN query method is proposed.Based on Voronoi diagram division of PoIs and hierarchical index quadtree structure,cloaking region can be constructed purposefully.Due to the targeted query request,the communication cost is decreasing compared with traditional cloaking region methods.And injecting fake query requests makes the query content privacy preserving work.We have verified the effectiveness of our proposal by analysis and experiments.

location privacy;location based service;cloaking region;Knearest neighbor query

2015-04-14;

2015-11-28;責任編輯:孫瑤

國家自然科學基金(No.61373147,No.61502404);福建省自然科學基金(No.2016Y0079,No.2015J05132);福建省教育廳A類項目(No.JA14234)

TP311

A

0372-2112 (2016)10-2423-09

??學報URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.10.021