一種基于興趣點(diǎn)分布的匿名框KNN查詢方法

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

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

?

一種基于興趣點(diǎn)分布的匿名框KNN查詢方法

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

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

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

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

1 引言

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

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

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

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

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

2 預(yù)備知識(shí)

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

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

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

3 興趣點(diǎn)KNN查詢

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

3.1 四叉索引樹

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

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

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

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

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

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

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

輸出:四叉樹TreeCi的某個(gè)結(jié)點(diǎn)ni

1. Procedure begins:

2. 獲取根結(jié)點(diǎn)T的每個(gè)孩子結(jié)點(diǎn)ni

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

4. for每個(gè)孩子結(jié)點(diǎn)ti∈Tdo

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

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

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

8. returnni

9. End Procedure

3.2KNN查詢流程

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

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

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

表1 KNN查詢流程表

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

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

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

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

1. Procedure begins:

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

3. Array1←計(jì)算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 每個(gè)Pj∈Array3 do //下一階興趣點(diǎn)

10. heap←AN1(Pj)

11. Array4←AN1(Pj)

12. 清空Array2 //保存新找到的下一階興趣點(diǎn)

13. Array2←Array4

14. neighbor←在heap中找到前K個(gè)興趣點(diǎn)

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

16. returnCRuk

17. End Procedure

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

3.3 性能分析

(1)查詢準(zhǔn)確性

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

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

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

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

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

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

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

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

(2)隱私安全性

和傳統(tǒng)匿名框方法實(shí)現(xiàn)的k匿名性不同,本方法用戶不必考慮匿名框中用戶數(shù)量.這是因?yàn)橛脩粼跇?gòu)造匿名框時(shí),可能不在匿名框內(nèi).當(dāng)K=3時(shí),圖6中的虛線匿名框可能是處于匿名框外用戶uk構(gòu)造的,因?yàn)槟涿蛑恍韪采w距離P5最近的其他2個(gè)興趣點(diǎn)P1、P3即可,不必考慮用戶位置.

因此本方法的k匿名性取決于匿名框覆蓋目標(biāo)興趣點(diǎn)Voronoi圖劃分單元內(nèi)的用戶數(shù)量,假設(shè)在沒有注入虛假查詢的情況下,則查詢Qi來自該匿名框覆蓋CRk的某個(gè)劃分單元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)有文獻(xiàn)中通常認(rèn)為背景知識(shí)包括用戶分布情況、用戶提交的興趣點(diǎn)查詢請(qǐng)求集合及各類興趣點(diǎn)四叉索引樹.由式(1)和(2)可知,即使攻擊者在掌握一定的背景知識(shí)情況下,能夠根據(jù)構(gòu)造的匿名框推斷出用戶真實(shí)查詢內(nèi)容,也很難將查詢內(nèi)容對(duì)應(yīng)到劃分單元內(nèi)某個(gè)具體用戶身份上.

4 實(shí)驗(yàn)

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

表2 實(shí)驗(yàn)?zāi)J(rèn)參數(shù)配置

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

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

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

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

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

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

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

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

4.3 查詢準(zhǔn)確性

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

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

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

4.4 隱私安全性

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

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

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

5 結(jié)論及展望

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

[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ìn)展[J].計(jì)算機(jī)學(xué)報(bào),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]葉阿勇,林少聰,馬建峰,等.一種主動(dòng)擴(kuò)散式的位置隱私保護(hù)方法[J].電子學(xué)報(bào),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ù)查詢隱私保護(hù)研究[J].計(jì)算機(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]劉華玲,鄭建國,孫辭海.基于貪心擾動(dòng)的社交網(wǎng)絡(luò)隱私保護(hù)研究[J].電子學(xué)報(bào),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].計(jì)算機(jī)應(yīng)用研究,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ì)算隱私保護(hù)訪問控制[J].電子學(xué)報(bào),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]王麗娜,彭瑞卿,趙雨辰,等.個(gè)人移動(dòng)數(shù)據(jù)收集中的多維軌跡匿名方法[J].電子學(xué)報(bào),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)境中基于匿名蜂窩的位置隱私保護(hù)[J].浙江大學(xué)學(xué)報(bào)(工學(xué)版),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é)點(diǎn)查詢方法[J].計(jì)算機(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]史敏儀,李玲娟.移動(dòng)用戶位置隱私保護(hù)方案研究[J].計(jì)算機(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í)空數(shù)據(jù)庫新理論[M].北京:科學(xué)出版社,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月出生,福建東山人,廈門大學(xué)博士,廈門理工學(xué)院計(jì)算機(jī)與信息工程學(xué)院教授、院長.主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘、信息推薦、隱私保護(hù)和系統(tǒng)工程.

E-mail:szzhu@xmut.edu.cn

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

周長利 男,1985年3月出生,黑龍江省哈爾濱人,哈爾濱工程大學(xué)博士,華僑大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院講師.主要研究領(lǐng)域?yàn)槲恢秒[私保護(hù)、網(wǎng)絡(luò)與信息安全.

E-mail:zhouchangli666@163.com

馬 櫻 男,1982年1月出生,湖南邵陽人,電子科技大學(xué)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)專業(yè)博士,廈門理工學(xué)院計(jì)算機(jī)與信息工程學(xué)院講師.主要研究方向?yàn)榛谕诰虻能浖こ?、大?shù)據(jù)、云計(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;責(zé)任編輯:孫瑤

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

TP311

A

0372-2112 (2016)10-2423-09

??學(xué)報(bào)URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.10.021