路網環境下基于Unit模型的位置隱私保護方法

趙逢達,房秀秀,李賢善

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

1 引 言

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

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

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

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

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

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

1)構建路網模型.將路網中復雜的路段關系映射為平面的路網有向圖,根據路網有向圖的連通性,將道路網絡抽象為Unit結構,基于Hilbert排序以提供更有效的隱私保護服務.

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

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

2 系統模型

2.1 系統模型

本文采用的是最常使用的中心匿名服務器結構,該系統模型由移動用戶端,中心匿名服務器端(AZ),位置服務提供商(LBS)三部分構成.匿名服務器在查詢用戶和服務提供商的中間,為兩者提供非常可靠的安全通信鏈接.如圖1所示.

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

2.2 位置隱私模型

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

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

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

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

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

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

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

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

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

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

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

2.3 路網模型

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

圖2 真實路網圖Fig.2 Real road network

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

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

定義6.邊界頂點.給定路網G中的部分線段集S,S中的邊界上的節點,即該節點一段連接的是S內的線段,另一端連接的線段不屬于S或者該頂點所連接的邊全部屬于S.

圖3 二維路網模型Fig.3 Road network

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

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

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

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

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

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

2.3.1 Unit結構

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

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

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

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

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

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

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

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

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

圖6 路網模型Fig.6 Road network

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

圖7 Unit路網模型Fig.7 Unit road network

第一,為使Unit包含盡可能多地邊,本文根據它們的度,按照降序對節點排序.

第二,根據節點的順序,將節點n和與n相連的邊構成一個Unit.根據本文定義7,將Unit中的節點n定義為中心節點.

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

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

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

算法1.Unit路網模型構建算法

輸入: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中心節點編碼

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

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

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

3 基于Unit路網模型的隱私保護方法

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

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

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

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

3.1 H-Unit匿名算法的實現

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

算法2.H-Unit 匿名算法

輸入:查詢 Q

輸出:匿名用戶集合AS,匿名區域AEL

(1)首先根據用戶的精確位置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 路網中每個Unit

(9) If |AS|

(10) ordUc← 從ordUa和ordUb中選擇用戶數量多的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) 調用算法4.2

(29)End If

(30)Return AS,AEL

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

圖9 路網圖Fig.9 Road network

3.2 H-Unit算法的舉例

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

圖10 路網圖劃分舉例Fig.10 Example about the division of the road network

表2 節點度
Table 2 Degree of node

節點nn8n5n1n2n4n6n7n9n10n11n12n3節點度dG(n)543333333322

表3 Unit的中心節點
Table 3 Center node of Unit

UnitUnit1Unit2Unit3Unit4Unit5Unit6Unit7Unit8Unit9中心節點n6n5n2n1n8n7n10n11n9

3.3 產生假用戶的算法

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

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

userAnonymity degree KUnitnumber of usersu73Unit43u154Unit6,Unit75u174Unit6,Unit75u135Unit9,Unit84

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

的隱私參數相同.

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

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

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

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

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

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

算法3.產生假用戶算法

輸入:匿名區域AEL,匿名度K,匿名集AS

輸出:AS

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

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

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

(4) 在邊ei隨機產生位置坐標(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中的用戶數小于k時,算法3將會被調用.在生成假用戶之前先計算需要生成的假用戶數量(步驟1).AZ在AEL中隨機選擇一條邊ei,然后在ei邊上隨機選擇一點,該點的坐標即為生成的假用戶的坐標,這樣才能確保假用戶存在AEL中.如果在AS中不存在該用戶,則將生成的假用戶存入AS中.重復步驟2到步驟6直到滿足步驟2中的條件.

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

4 實驗模擬

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

4.1 實驗環境

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

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

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

4.2 實驗結果分析

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

表5 實驗參數
Table 5 Experiment parameters

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

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

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

SR=|success_msg | / (all_msg)

(1)

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

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

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

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

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

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

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

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

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

5 結 論

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

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

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

1)根據Unit路網模型提出針對連續性查詢的方法.

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