路網(wǎng)環(huán)境下基于Unit模型的位置隱私保護方法

趙逢達,房秀秀,李賢善

1(燕山大學(xué) 信息科學(xué)與工程學(xué)院,河北 秦皇島 066004)2(河北省軟件工程重點實驗室,河北 秦皇島 066004)3(北京聯(lián)合天成價值網(wǎng)絡(luò)科技有限公司,北京 100089)

1 引 言

基于位置的服務(wù)(Location Based Services,LBS)又稱定位服務(wù),也就是指服務(wù)提供商通過移動網(wǎng)絡(luò)和定位技術(shù)獲取查詢用戶的位置坐標,并將與該位置相關(guān)的服務(wù)信息傳送給查詢用戶[1].位置服務(wù)是一把雙刃劍,讓人們的生活變得更加便利的同時,其信息泄露也給用戶的生活造成諸多的威脅.因此保護查詢用戶的地理位置不被泄露迫在眉睫.

研究者已經(jīng)進行了大量基于位置隱私保護的研究[2-6].位置隱私保護技術(shù)主要是在不影響服務(wù)質(zhì)量的前提下,對查詢用戶的位置信息進行模糊化處理.這些技術(shù)中最基本的、重要的位置隱私保護技術(shù)是K-匿名模型[2].

Km等人較早提出了路網(wǎng)環(huán)境下的RE和HE匿名查詢處理框架[7],Random edge ordering(RE)是隨機的選取路網(wǎng)模型中的邊作為匿名區(qū)域.Hilbert edge ordering(HE)首先是對邊的中點作希爾伯特取值,并將該值作為邊排序主鍵.依據(jù)希爾伯特值相近,二維圖中邊鄰近的原理,將希爾伯特值相近的邊作為一組作為匿名區(qū)域.Ma等人提出了基于Voronoi的網(wǎng)絡(luò)圖[8],將大網(wǎng)絡(luò)劃分為小的Voronoi區(qū)域.它提前計算好內(nèi)存里的中間結(jié)果,然后根據(jù)緩存好的結(jié)果自己構(gòu)造查詢答案.Wang和Liu提出了一種以X-Star為基礎(chǔ)的匿名方法[9],可以為移動用戶達到最優(yōu)的查詢處理成本和高隱私保護之間的平衡.然而,X-Star顯示出較低的匿名化成功率.Kim等人改進了X-star算法[10],結(jié)合Hilbert曲線提出了H-star算法.基于Hilbert曲線的H-star算法對星形節(jié)點進行排序,并根據(jù)匿名度K將它們加載到桶中.盡管該算法有一些改進,但是它具有與X-star相同的問題.

Li 等人提出了一種新類型的可逆位置匿名機制[11],有效地支持多級位置隱私.鄭淼等人在網(wǎng)絡(luò)擴張技術(shù)算法的基礎(chǔ)上[12],提出了一個內(nèi)部含有環(huán)的無向圖,用于防止匿名區(qū)域內(nèi)只包含一條路徑的情況,并結(jié)合環(huán)和樹的結(jié)構(gòu)特征,為查詢用戶提供更隱秘的匿名空間.周長利等人在注入虛假查詢和構(gòu)造查詢匿名組的方法上[13],提出了抗查詢內(nèi)容關(guān)聯(lián)攻擊和抗運動模式推斷攻擊的軌跡隱私保護方法.

Liu等人設(shè)計了兩個啟發(fā)式算法以策略性地選擇mix zone位置[14].一般來說,盡管mix zone模型保護了用戶連續(xù)查詢的隱私,但是用戶所享受的服務(wù)受到一定的限制,這可能對于一些用戶是不能接受的.H.J.Cho等人提出了一種位置隱私保護監(jiān)控算法[15],應(yīng)用在保護路網(wǎng)中MkkNN查詢的軌跡隱私中.Yong Wang為單個用戶和一批用戶提出了Snet層次結(jié)構(gòu)[16].每個Snet被視為匿名單元.雖然Snet層次結(jié)構(gòu)可以加速隱私保護過程,但是Snet層次結(jié)構(gòu)不能及時更新,從而降低了匿名成功率.

以上這些隱私保護方法,可以保護用戶的位置不受攻擊,但是匿名效率和匿名成功率均不太理想.因此為了更好地保護路網(wǎng)環(huán)境下查詢用戶的位置隱私,提高匿名成功率以及提高匿名效率.本文提出了Unit結(jié)構(gòu),并將該結(jié)構(gòu)Hilbert 編碼相結(jié)合組成新的路網(wǎng)模型.本文的主要內(nèi)容總結(jié)如下：

1)構(gòu)建路網(wǎng)模型.將路網(wǎng)中復(fù)雜的路段關(guān)系映射為平面的路網(wǎng)有向圖,根據(jù)路網(wǎng)有向圖的連通性,將道路網(wǎng)絡(luò)抽象為Unit結(jié)構(gòu),基于Hilbert排序以提供更有效的隱私保護服務(wù).

2)基于Unit路網(wǎng)模型提出一種新的有效的位置隱私保護算法,每個查詢用戶可以依據(jù)自己需求提出不同的隱私要求.

3)該算法考慮到了人口稀少的地區(qū)難以找到k個用戶而導(dǎo)致查詢失敗的情況,為不滿足k要求的匿名區(qū)域添加假用戶,以達到提高匿名成功率的目的.

2 系統(tǒng)模型

2.1 系統(tǒng)模型

本文采用的是最常使用的中心匿名服務(wù)器結(jié)構(gòu),該系統(tǒng)模型由移動用戶端,中心匿名服務(wù)器端(AZ),位置服務(wù)提供商(LBS)三部分構(gòu)成.匿名服務(wù)器在查詢用戶和服務(wù)提供商的中間,為兩者提供非?？煽康陌踩ㄐ沛溄?如圖1所示.

用戶登錄該系統(tǒng)后,首先與匿名服務(wù)中心建立安全的連接,并通過此連接移動用戶不斷更新他們的位置信息并發(fā)送到匿名服務(wù)中心.當一個用戶提出查詢問題,匿名服務(wù)中心接受此查詢及用戶的精確位置信息,接著,匿名中心根據(jù)用戶的位置信息生成匿名區(qū)域R,并把匿名區(qū)域R發(fā)送給服務(wù)提供商.然后LBS根據(jù)接受到的位置查找興趣點,并返回查找到的所有興趣點給匿名中心.最后,AZ依據(jù)用戶具體位置過濾結(jié)果集,將精確的查詢結(jié)果發(fā)送給移動用戶.

2.2 位置隱私模型

位置隱私保護模型要求移動用戶在匿名區(qū)域內(nèi)是無法被辨認的,這就要用到位置k-匿名的概念.

定義1.位置K-匿名 移動用戶所在的匿名區(qū)域必須至少包含k-1個不同的移動用戶.

定義2.位置隱私參數(shù)(K;Lmax;Tmax)為滿足移動用戶不同的隱私要求,每位用戶可以設(shè)置這三種不同的隱私參數(shù).

K為位置K-anonymity模型的匿名水平.換言之,每個匿名區(qū)域都應(yīng)該包含至少k個不同的用戶,并且K值越大,用戶的隱私越不容易泄露.用戶被攻擊的概率為1/K.若匿名中心服務(wù)器找不到k個用戶,則查詢失敗.

Lmax為匿名區(qū)域的最大長度,以確保LBS提供服務(wù)的服務(wù)質(zhì)量,匿名區(qū)域的長度不能超過最大長度,否則查詢失敗.

Tmax為時間容忍度,表示從用戶提出查詢到匿名結(jié)束,用戶所能容忍的最長時間.如果匿名處理時間超過最長時間,則查詢失敗.

需要注意的是,匿名區(qū)域的最小長度也是匿名隱私參數(shù)之一,不過,為了簡化隱私參數(shù)模型,本文不考慮匿名區(qū)域的最小長度.

定義3.位置匿名化 由Q表示查詢用戶U提交的基于地理位置服務(wù)的查詢信息.位置匿名化就是采用滿足U的隱私參數(shù)的匿名區(qū)域來替換Q中包含的移動用戶的確切位置信息.

表1 專有名詞的縮略詞和符號的解釋
Table 1 Interpretation of acronyms and symbols

AZ匿名服務(wù)器AnonymizerLBSLBS服務(wù)服務(wù)器AEL匿名區(qū)域 Anonymizing Edge ListAS匿名集合 Anonymous SetK匿名隱私參數(shù),匿名區(qū)域最少包含的移動用戶數(shù)Lmax匿名區(qū)域的長度

如表1列出了文章中出現(xiàn)的符號和縮寫所代表的含義.

2.3 路網(wǎng)模型

圖2表示的是真實的道路網(wǎng)絡(luò)結(jié)構(gòu)圖,圖3是從道路圖中抽象出的二維路網(wǎng)模型.路網(wǎng)模型由帶權(quán)的有向圖G=(N,E)表示,N代表路網(wǎng)的節(jié)點集合,E代表路網(wǎng)邊的集合.N中的節(jié)點n代表道路的交叉點.E中的每條邊e包含兩個節(jié)點,邊e的權(quán)重由W(e)表示.W(e)可由邊的長度或者是一個節(jié)點到另一個節(jié)點所用的時間表示,本文使用前者表示權(quán)重.如圖3所示帶權(quán)重的路網(wǎng)模型,邊n1n2的權(quán)重是3,端點是n1,n2.用戶的位置采用實心圓點表示,邊的端點采用空心圓點表示.

圖2 真實路網(wǎng)圖Fig.2 Real road network

定義4.節(jié)點的度dG(n).節(jié)點n所連接的邊的條數(shù).

定義5.終節(jié)點.該節(jié)點只與一條邊相連,dG(n)= 1.

定義6.邊界頂點.給定路網(wǎng)G中的部分線段集S,S中的邊界上的節(jié)點,即該節(jié)點一段連接的是S內(nèi)的線段,另一端連接的線段不屬于S或者該頂點所連接的邊全部屬于S.

圖3 二維路網(wǎng)模型Fig.3 Road network

本文的主要內(nèi)容就是開發(fā)出一個安全高效的可擴展的位置匿名模型.下面先介紹兩種基本的匿名模型,即隨機抽樣模型和網(wǎng)絡(luò)擴展模型,并由此引出新的匿名模型概念.

1)隨機抽樣模型.移動用戶向AZ傳遞查詢q(k,l,s,t),通過一次次的循環(huán),匿名模型隨機的選取S空間下的一條條邊,直到同時滿足(k,l)的要求,并將這些邊作為移動用戶新的匿名位置.如圖4所示,移動用戶(k,l)=(5,5).隨機抽樣模型在這個S區(qū)域內(nèi)隨機的選取幾條邊(共包含5個移動用戶),如圖中的粗線部分.

2)網(wǎng)絡(luò)擴展模型.下面考慮另一種極端情況,通過擴展混淆u的具體位置[17]:依據(jù)Dijkstra算法,通過計算相對于u所在邊的網(wǎng)絡(luò)距離逐漸添加相鄰的邊,直到滿足u的隱私需求.如圖5所示,將加粗的4條距離u所在位置最近的邊逐步添加到匿名區(qū)域內(nèi).

在隱私要求相同的情況下,隨機抽樣模型得到的匿名區(qū)域均勻地散布在S區(qū)域內(nèi),等同于在不同的線段中提出一系列查詢,因此造成查詢處理的成本比較高.該方法的優(yōu)點是它具有很強的抗推理攻擊能力,因為道路集是隨機選取的.與此相反,網(wǎng)絡(luò)擴展模型得到的匿名區(qū)域呈現(xiàn)的是一種緊湊結(jié)構(gòu).這種結(jié)構(gòu)產(chǎn)生的查詢處理成本最小,并且在查詢處理過程中,

n1n2n3n4n5n6n7n8n9n10n11n12n13n14n15n16u1u2u3u4u5n1n2n3n4n5n6n7n8n9n10n11n12n13n14n15n16u1u2u3u4u5圖4 隨機抽樣位置匿名模型Fig.4 Anonymous model of random sampling locations圖5 網(wǎng)絡(luò)擴展位置匿名模型Fig.5 Anonymous model of network extension location

擴展網(wǎng)絡(luò)是局部進行的,導(dǎo)致成本進一步降低.但是,該模型抵抗攻擊的能力很低,因為網(wǎng)絡(luò)擴展過程遵守best-first搜索模式,其可能被攻擊者使用反向工程攻擊.以上這兩種模型的匿名處理時間都比較長,容易導(dǎo)致總的查詢時間大于T,從而導(dǎo)致查詢失敗.

2.3.1 Unit結(jié)構(gòu)

考慮到上述兩種模式的優(yōu)缺點,本文提出一種基于Hilbert曲線編碼的位置匿名模型,即Unit路網(wǎng)模型.目的是實現(xiàn)較低的位置匿名處理成本和較高的抵抗攻擊能力之間的最佳平衡.具體地,Unit路網(wǎng)模型主要通過兩個階段達到這種平衡：

1)它將與同一節(jié)點相鄰的邊組織在一起.這么做的好處是預(yù)先構(gòu)建最小匿名單元,達到降低位置匿名成本的目的.

2)采用Hilbert曲線對最小匿名單元進行編碼,根據(jù)HilbertID值對匿名區(qū)域擴展,這樣避免了中心攻擊,提高了模型的抗攻擊能力.

歐式空間下的Casper算法是一個基于網(wǎng)格的位置K匿名算法[18].Casper算法將全部的空間均等的分成若干個小網(wǎng)格,每個小網(wǎng)格被稱作匿名度.本文依據(jù)該思想,將路網(wǎng)也同樣分成若干個小的區(qū)域,每個區(qū)域內(nèi)包含多條邊,并將這些小的區(qū)域作為最小匿名單元,本文將最小匿名單元稱作Unit.

定義7.Unit 對于給定的路網(wǎng)圖G=(N,E),Unit是G的子圖,表示為Un=(n,Bs,Es),其中n表示Unit的中心節(jié)點,Bs是Unit的邊界頂點集合,Es表示Unit包含的邊的集合,Es中所有的邊都與n相連.

值得注意的是,Es是與n相連的部分邊,而不是全部的邊.因此,節(jié)點n可能是多個Unit的中心節(jié)點.每個Unit中邊是不相重疊的,彼此是獨立的.劃分Unit的方法將在后面詳細描述.

定義8.Lunit Unit中所有邊的長度和的最大長度.

Unit作為AEL的最小組成單元,由于AEL具有最大值限制,因此Unit的長度也不能超過某個特定的值.Lunit的值是唯一且固定的.絕大多數(shù)Unit包含多條邊,但不排除個別的邊長度大于Lunit.對于這種長度大于Lunit的邊,本文將該邊作為單獨的一個Unit.

將圖6按照上述Unit定義分割路網(wǎng)圖,結(jié)果如圖7.Unit(a)對應(yīng)的邊界頂點集合Bs=(n3,n7,n8,n9),邊集Es={(n3,n9),(n7,n9),(n8,n9)},中心節(jié)點是n9.類似地,對Unit(b),對應(yīng)的邊界頂點集合Bs={n3,n4,n5},邊集Es={(n3,n4),(n5,n4)},中心節(jié)點是n9.另外,如果兩個Unit共享同一個中心節(jié)點,則稱這兩個Unit為相鄰Unit.

圖6 路網(wǎng)模型Fig.6 Road network

通常,具有較大度的頂點在道路網(wǎng)絡(luò)中起到更重要的作用.因此,本文選擇相交的節(jié)點和與該節(jié)點相連的邊構(gòu)建Unit.下面是構(gòu)建路網(wǎng)模型的步驟.

圖7 Unit路網(wǎng)模型Fig.7 Unit road network

第一,為使Unit包含盡可能多地邊,本文根據(jù)它們的度,按照降序?qū)?jié)點排序.

第二,根據(jù)節(jié)點的順序,將節(jié)點n和與n相連的邊構(gòu)成一個Unit.根據(jù)本文定義7,將Unit中的節(jié)點n定義為中心節(jié)點.

圖8 Hilbert曲線4×4Fig.8 Hilbert curve 4×4

第三,本文通過使用圖8所示的Hilbert曲線將Unit的中心節(jié)點映射成希爾伯特ID.由于一些單元具有相同的中心節(jié)點,它們具有相同的Hilbert ID.因此,按照第三步中的順序重新標記生成的Unit.如果兩個Unit具有相同的希爾伯特ID,則它們的編號是相鄰的.

在第三步中,按照Hilbert曲線對Unit進行排序,采用的是希爾伯特空間填充曲線的方法,將每個節(jié)點的2D坐標變換為1D值.圖8通過使用希爾伯特曲線4x4分割2D空間.如果兩個點在2D空間中非常臨近,那么它們在1D變換中也接近的概率非常高.將節(jié)點的坐標值由二維變?yōu)橐痪S,這樣可以讓匿名過程變得更加方便.因此本文采用Hilbert編碼方法.下面是Unit路網(wǎng)模型構(gòu)建的偽代碼.

算法1.Unit路網(wǎng)模型構(gòu)建算法

輸入:G=(N,E)

輸出:Unit1,Unit2,Unit3,…,Unitn

(1)Listnode ← Sorted nodes

(3) sumlength ← 0 // Unit中邊的總長度

(5) If e 不屬于任何 Unit

(6) sumlength ← sumlength+L(e)

(7) If(sumlength < Lunit)||(E(Uniti)= ?)

(8) E(Uniti)←e,flag(e)=1,flag(curnode)=1

(9) Else sumlength← sumlength-L(e)

(10) End If

(11) End If

(12) End For

(13) If flag(curnode)==1

(14) N(Uniti)← curnode

(15) End If

(16)End For

(18) If flag(e)=0

(19) E(Unitj)← e

(20) End If

(21)End For

(22)Hilbert(#N,#U) //生成 Hilbert曲線

(23)Merge HilbertId(center node) //對Unit中心節(jié)點編碼

(24)根據(jù)Hilbert ID值對Unit重新排序

(25)Return Unit1,Unit2,Unit3,…,Unitn

算法1描述了構(gòu)建路網(wǎng)模型的過程.首先路網(wǎng)中的節(jié)點根據(jù)中心節(jié)點的度按照降序排序,并且通過AZ存儲在Listnode中(步驟1).AZ依次從Listnode中取出節(jié)點,如果該節(jié)點和它所連接的邊滿足規(guī)定條件,則該節(jié)點和與其連接的部分邊組成一個Unit(步驟2-16).如果邊的長度超過Lunit,則在構(gòu)建Unit的過程中應(yīng)該摒棄該邊,因此有必要檢索遺漏掉的邊.因為漏掉的邊長度太長,并且它不能和其它的邊組成Unit,所以本文將漏掉的邊設(shè)置為單獨的Unit(步驟17-21).如圖7中(c)圖所示,邊(n5,n9)構(gòu)成一個Unit.AZ按照Hilbert曲線對Unit進行排序(步驟22-25).

3 基于Unit路網(wǎng)模型的隱私保護方法

為保護路網(wǎng)環(huán)境下人們的位置,文獻[9,10]使用的方法可以隱藏查詢用戶的精準位置,但它們的匿名成功率低,匿名時間長,不能帶來較好的用戶體驗.為了避免這種巨大的時間成本和較低的匿名成功率,本章基于Unit路網(wǎng)模型提出一種新的H-Unit算法,H-Unit位置匿名算法的操作主要包括兩個階段：

第一階段尋找查詢用戶所在的最小匿名單元Unit并且擴展Unit生成匿名區(qū)域的過程.

第二階段是為提高H-Unit算法的匿名成功率,在匿名區(qū)域內(nèi)隨機添加假用戶的算法.

當用戶u提出匿名度為K的查詢時,AZ第一時間獲取用戶所在的Unit,并得到該Unit的編號.然后,匿名集合由Unit中的所有查詢用戶組成.AZ判斷匿名集合中的用戶數(shù)量,如果匿名集合中的用戶數(shù)量不能滿足查詢用戶的隱私要求,則AZ搜索與查詢用戶所在的Unit相鄰的Unit.重復(fù)上述步驟,直到匿名集合中的用戶數(shù)量滿足查詢用戶的隱私要求或達到匿名區(qū)域長度的上限.如若匿名集合中的用戶數(shù)仍然不滿足用戶的隱私要求,則產(chǎn)生假用戶.如果沒有生成合格的匿名集,相應(yīng)的匿名處理將被終止.如果該查詢在AZ中匿名失敗,則該查詢無法到達LBS.如果該用戶放棄對自己的位置信息進行保護,那么用戶可以直接將精確的位置發(fā)送到服務(wù)提供商.

3.1 H-Unit匿名算法的實現(xiàn)

上面已經(jīng)介紹過H-Unit匿名算法的大致過程,H-Unit匿名算法本文分為兩步來講解:中心匿名服務(wù)器為查詢用戶搜索真實用戶的算法和產(chǎn)生假用戶部分的算法.下面先來詳細介紹匿名服務(wù)器搜索真實用戶的部分算法.

算法2.H-Unit 匿名算法

輸入:查詢 Q

輸出:匿名用戶集合AS,匿名區(qū)域AEL

(1)首先根據(jù)用戶的精確位置l找到用戶所在的邊e,然后找到該邊e所在的Unit的編號ordU.

(2)If(L(AEL≤ Lmax)

(3) AS ←U(UnitordU) AEL← E(UnitordU) //將該Unit中的用戶和邊分別存儲在AS和AEL中

(4)Else Retrun //查詢失敗

(5)End If

(6)If |AS |< K

(7) ordUa ← ordU+1,ordUb ← ordU-1

(8) For 路網(wǎng)中每個Unit

(9) If |AS|

(10) ordUc← 從ordUa和ordUb中選擇用戶數(shù)量多的Unit

(11) If ordUc中存在活躍用戶

(12) If L(AEL)+L(ordUc)> Lmax

(13) break

(14) End If

(15) AS←U(UnitordUc),AEL←UnitordUc)

(16) End If

(17) If ordUc == ordUa && (ordUa-ordU)-(ordU-ordUb)> 1 then

(18) ordUb--

(19) End If

(20) If ordU == ordUb

(21) ordUb--

(22) Else ordUa ++

(23) End If

(24) End If

(25) End For

(26)End If

(27)If kAnony > |AS|

(28) 調(diào)用算法4.2

(29)End If

(30)Return AS,AEL

如上述算法2所示,移動用戶u以 的形式發(fā)送查詢請求Q.當AZ接收到用戶u的查詢請求Q時,AZ將用戶的確切位置l映射到道路網(wǎng)絡(luò)中,找到用戶u所在的邊e.AZ首先找到邊e所在的Unit,并將該Unit作為初始匿名區(qū)域.如果Unit的長度超過AEL的最大長度限制,則查詢失敗(步驟1-4).當AS滿足用戶的擴展條件時,AZ開始擴展用戶的匿名區(qū)域.在擴展的過程中,AZ選擇具有更多用戶的Unit,并且AZ僅考慮具有活躍用戶的Unit(步驟5-26).如果AS中的用戶數(shù)量小于K,則調(diào)用算法2生成假用戶(步驟27-29).最后返回匿名集AS和匿名區(qū)域AEL.

圖9 路網(wǎng)圖Fig.9 Road network

3.2 H-Unit算法的舉例

如圖9為某一路網(wǎng)圖,圖10為Unit子圖的劃分結(jié)果,總共包含9個Unit,這些Unit的右下腳的編號表示其順序(即,Unit4的編號是4等).表2和表3中列出了Unit的每個節(jié)點和中心節(jié)點的度.假設(shè)系統(tǒng)中有4個用戶提出查詢.表4中展示出了這4個查詢用戶的匿名度K,匿名集合Unit及其包含的用戶.結(jié)合上面這些圖和表格,可以找到查詢用戶所在的匿名區(qū)域.

圖10 路網(wǎng)圖劃分舉例Fig.10 Example about the division of the road network

表2 節(jié)點度
Table 2 Degree of node

節(jié)點nn8n5n1n2n4n6n7n9n10n11n12n3節(jié)點度dG(n)543333333322

表3 Unit的中心節(jié)點
Table 3 Center node of Unit

UnitUnit1Unit2Unit3Unit4Unit5Unit6Unit7Unit8Unit9中心節(jié)點n6n5n2n1n8n7n10n11n9

3.3 產(chǎn)生假用戶的算法

在人口密集的商業(yè)區(qū)域,很容易在一定范圍內(nèi)找到k個用戶.但在人口稀少的地區(qū),很難找到k個用戶,特別是當匿名度K很大時.如果AZ在某個時間范圍或區(qū)域內(nèi)找不到k個用戶,則用戶的查詢失敗.因此有必要引入假用戶的概念.即使攻擊者知道在該區(qū)域中存在假用戶,他也不知道哪些用戶是真實的,哪些是假用戶,因此用戶被攻擊的概率仍然是1/k.

表4 用戶匿名的示例
Table 4 Example of user anonymity

userAnonymity degree KUnitnumber of usersu73Unit43u154Unit6,Unit75u174Unit6,Unit75u135Unit9,Unit84

定義9.假用戶 在AEL中隨機產(chǎn)生地理坐標(x,y)作為假用戶的位置坐標.假用戶的位置隱私保護參數(shù)和真實用戶

的隱私參數(shù)相同.

假用戶生成算法(Generate Dummy)主要有兩個方面需要考慮:

1)確定假用戶的位置坐標.生成的假用戶的空間位置要符合大多數(shù)用戶的軌跡規(guī)律,越像真實用戶的位置越好,在路網(wǎng)空間里,如果生成的假用戶的坐標不符合常規(guī),將降低查詢用戶的匿名成功率.

2)生成假用戶的數(shù)量.在生成假用戶之前,AZ需要先確定生成假用戶的數(shù)量.由于太多的假用戶會導(dǎo)致系統(tǒng)性能下降,但是太少的假用戶無法達到保護用戶隱私的目的.

針對上述的問題,本文將假用戶的位置限制在匿名區(qū)域AEL中,以保證生成的假用戶的位置坐標是有效的.查詢用戶設(shè)定的隱私參數(shù)K的值減去AS中的真實用戶數(shù)量,為所需生成的假用戶的數(shù)量.

如果生成的假用戶均聚類在一起,即使所有的假用戶都符合規(guī)則,那么也會使得每個假用戶之間的位置非常相近,這將會影響隱私保護的效果.為防止這一現(xiàn)象的出現(xiàn),本文采用隨機生成坐標的方式,使得每個假用戶的坐標之間沒有關(guān)聯(lián),并且是隨機分布的,沒有規(guī)律可循.即使攻擊者知道AS中有假用戶的存在,也無法判斷出哪些是假用戶.

文獻[19]中描述的是完全沒有限制的隨機產(chǎn)生假用戶的方法,但本文中產(chǎn)生假用戶的算法是滿足-privacy 隱私要求的.因此,我們提出虛擬用戶生成算法.用戶位置和假用戶位置均受Lmax約束.

算法3.產(chǎn)生假用戶算法

輸入:匿名區(qū)域AEL,匿名度K,匿名集AS

輸出:AS

(1)f= K- |AS| //f表示需要產(chǎn)生假用戶的個數(shù)

(2)For 生成的假用戶數(shù)量< f

(3) 在AEL中隨機選擇一條邊ei

(4) 在邊ei隨機產(chǎn)生位置坐標(x,y)→ 新用戶 u(x,y)

(5) If u(x,y)? AS,AS← u(x,y)

(6) End If

(7)End For

(8)Return AS

當AS中的用戶數(shù)小于k時,算法3將會被調(diào)用.在生成假用戶之前先計算需要生成的假用戶數(shù)量(步驟1).AZ在AEL中隨機選擇一條邊ei,然后在ei邊上隨機選擇一點,該點的坐標即為生成的假用戶的坐標,這樣才能確保假用戶存在AEL中.如果在AS中不存在該用戶,則將生成的假用戶存入AS中.重復(fù)步驟2到步驟6直到滿足步驟2中的條件.

從表4中,容易得到|ASu13|

4 實驗?zāi)M

在本節(jié)中,為評估文中提出的Unit路網(wǎng)模型以及對應(yīng)的匿名算法和查詢處理算法在真實道路網(wǎng)絡(luò)的有效性,將H-Unit匿名算法與文獻[19]中的Random edge ordering(RE)and Hilbert-based ordering(HE)兩種算法進行比較.

4.1 實驗環(huán)境

實驗運行在4GB RAM的硬件配置64位Core i5處理器的Microsoft Windows7操作系統(tǒng).實驗采用的開發(fā)語言是C,并使用g(版本號:4.9.3)編譯器完成代碼編譯.

本次研究使用的實驗數(shù)據(jù)集來自舊金山的真實道路網(wǎng)絡(luò)[20],其中包括10萬個移動用戶和5萬條路段.路網(wǎng)圖中邊的權(quán)重設(shè)置為邊的長度.用戶和興趣點的位置遵循均勻分布.

本文從10萬個用戶中隨機生成查詢用戶,測試中心匿名服務(wù)器的匿名處理性能和LBS匿名查詢處理效果.

4.2 實驗結(jié)果分析

在本節(jié)中,對中心匿名服務(wù)器為查詢用戶產(chǎn)生匿名區(qū)域的過程進行實驗,并對實驗結(jié)果做出詳細的分析.實驗中使用的參數(shù)數(shù)據(jù)如表5中所示.例如參數(shù)K和Lmax的值分別選自3-30,100-900,這樣設(shè)置實驗參數(shù)是為得到更好的實驗比較結(jié)果.匿名度K,如果在匿名區(qū)域中只有一兩個人,查詢用戶很容易被攻擊,則匿名查詢是無意義的,因此,K的值必須大于2.當K大于30時,實驗所得的對比效果和K等于30相差無異,因此我們在3-30之間選擇K的值.路網(wǎng)中總共有100k個用戶,從這些用戶中隨機選取查詢用戶,查詢用戶的數(shù)量如表中所示.Unit最大長度等于500是固定值,如果下面的實驗中沒有具體描述,則各變量使用默認值.下文中提到的匿名時間是查詢用戶匿名時間總和.重復(fù)運行每個實驗多次,將平均值作為評估結(jié)果.

表5 實驗參數(shù)
Table 5 Experiment parameters

參數(shù)名稱參數(shù)值默認值用戶數(shù)量100k100k查詢用戶數(shù)量1k,5k,10k,20k,30k,40k,50k30k匿名度 K[3,30][10-15]AEL最大長度Lmax100,200,300,400,500,600,700,800,900700Unit最大長度500m500m

下面從兩個方面對Unit路網(wǎng)框架進行評估:匿名成功率和匿名時間.

定義10.匿名成功率.中心匿名服務(wù)器對移動用戶成功匿名的數(shù)量占查詢用戶總數(shù)的比率[7],如公式(1)所示.

SR=|success_msg | / (all_msg)

(1)

公式(1)中,all_msg表示查詢用戶的總數(shù)量,success_msg表示匿名成功的用戶總和.匿名成功率越高,相應(yīng)的算法性能越好.文中的H-Unit匿名算法和RE、HE算法的測試結(jié)果均是在同一機器,相同配置的環(huán)境下產(chǎn)生的.

定義11.匿名時間.實驗中所描述的匿名時間是指中心匿名服務(wù)器對移動用戶總的匿名時間和[7].

為得到更好的位置隱私保護效果,匿名時間應(yīng)該越短越好.因為移動用戶的查詢等待時間是有限的,匿名時間越短,留給LBS服務(wù)器搜索興趣點的時間越長,查詢請求的成功率越高.

圖11 匿名時間評估Fig.11 Cloaking time evaluation

圖11顯示了這三種算法的用戶總匿名時間.可以看出,在相同的條件下H-Unit算法的匿名時間比HE和RE算法的匿名時間短很多.其中最主要的原因是Unit匿名模型中匿名服務(wù)器在搜索移動用戶時,不在是逐條邊的檢索,而是以Unit為單位進行檢索邊上的用戶.因此中心匿名服務(wù)器檢索移動用戶的速度提高了.查詢用戶的匿名時間主要受到查詢用戶設(shè)定的匿名度K和AEL的最大限制長度的影響,查詢用戶的數(shù)量對匿名時間幾乎是沒有影響的.如圖11中(c)可以看出,當用戶數(shù)等于50000時所使用的匿名時間,大約是用戶數(shù)等于10000所使用時間的五倍.這是由于中心匿名服務(wù)器是對查詢用戶按照查詢請求提交的時間順序,依次按照順序進行逐個匿名處理,因此查詢用戶的數(shù)量對匿名時間是沒有影響的.

如果匿名度K在某一區(qū)間內(nèi)是隨機選取的,則不同算法的匿名時間取值介于在邊界K值所對應(yīng)的匿名時間范圍內(nèi).結(jié)合圖11中(a)和(b)可以看出當匿名度K=[5-7]時,匿名時間大于K=5且小于K=10時的匿名時間.這是因為在其他外界條件相同的前提下,匿名時間只是受到匿名度K的影響.而且隨著K值的增加,中心匿名服務(wù)器檢索到足夠數(shù)量的移動用戶所用時間也越長,因此匿名時間越長.

圖11中(d)顯示出隨著AEL的最大長度的增長,匿名時間是先增加然后減小并且最終趨于穩(wěn)定.當最大長度等于700或800時,匿名時間最短.由圖11中(d)結(jié)合圖12中(c)圖可以得出,在K值相同的情況下,當最大匿名集的長度較小時,匿名成功率較低,也就是中心匿名服務(wù)器還沒有檢索到k個用戶時,AEL的長度就已經(jīng)超過了Lmax,然后匿名結(jié)束,查詢失敗.因此隨著Lmax的增大,中心匿名服務(wù)器檢索得到的用戶數(shù)量越多,所用時間自然也會增加.但是當Lmax增加到AZ可以找到k個用戶,這時Lmax再增加,AZ在檢索用戶的過程中,受到的限制變小,例如當AZ添加Unit1(添加上Unit1的用戶數(shù)量滿足K的要求)進入匿名區(qū)域后得到的AEL的長度大于Lmax,則放棄Unit,再去尋找周圍其他的Unit.若是Lmax足夠大,則可以直接將Unit1添加到AEL中,不需要再浪費時間檢索其他Unit,因此Lmax增加,匿名時間減少并趨于一定的值.

圖12 匿名成功率評估Fig.12 Success ratio evaluation

圖12顯示了匿名度K和AEL最大長度對成功率的影響.顯然,H-Unit算法在相同的匿名度K和長度限制下成功率最高.圖中假用戶的數(shù)量是3萬個查詢生成的總假用戶數(shù).圖12中(a)顯示了在三種匿名度K的情況下,不同長度限制對生成假用戶數(shù)量的影響.圖12中(b)表示了在三種長度限制的情況下,不同匿名度K對生成假用戶數(shù)量的影響.圖12中(c)顯示了當匿名度K=10時,AEL的長度限制對三種算法的匿名成功率的的影響.當匿名度K為一定值時,隨著AEL的長度限制變大,找到k個用戶變得更加容易,因此成功率更高.在圖12中(d)中Lmax=300,匿名度較小時,很容易在特定范圍內(nèi)找到k個用戶.因此,三種算法的成功率是相同的.很容易看出,H-Unit算法的成功率是最高的.

5 結(jié) 論

移動設(shè)備和定位技術(shù)的出現(xiàn)推動了位置服務(wù)行業(yè)的發(fā)展.基于位置的服務(wù)為人們的生活提供了極大的方便,但與此同時用戶的個人隱私問題也引起了人們的關(guān)注.對于如何保護用戶的位置隱私問題,研究者們已經(jīng)提出了多種解決方法,但是大部分的研究背景是基于歐式空間下的,路網(wǎng)環(huán)境下的方法較少而且匿名性能一般.

本文創(chuàng)新性的提出了一種新的路網(wǎng)模型,并針對該路網(wǎng)模型提出了隱私保護算法.H-Unit算法大體分為三個階段:i)構(gòu)建基于Unit的路網(wǎng);ii)采用Hilbert算法將每個Unit的編號映射到HilbertID;iii)選擇鄰近的Unit擴展匿名區(qū)域以滿足用戶的要求.本文還考慮到了在人口稀疏的地方添加假用戶的方式,以提高匿名成功率.廣泛的實驗研究表明,與現(xiàn)有的Hilbert Cloak算法相比,H-Unit實現(xiàn)了較高的匿名成功率和較低的通信成本.

本文主要是針對路網(wǎng)環(huán)境下的位置隱私保護的研究,雖然本文對其中的一些關(guān)鍵問題進行了研究,完成了部分工作.但是路網(wǎng)環(huán)境下的攻擊類型有很多種,用戶的查詢多是連續(xù)性查詢,文中方法針對的是快照查詢.因此今后的工作主要從以下幾個方面開展:

1)根據(jù)Unit路網(wǎng)模型提出針對連續(xù)性查詢的方法.

2)提高該模型的抗攻擊能力,使該算法除抗重現(xiàn)攻擊外的其他類型的推理攻擊.