一種路網(wǎng)環(huán)境下LBS隱私保護算法

左正魏,潘巨龍,魏琳琳

(中國計量學(xué)院 信息工程學(xué)院,浙江 杭州 310018)

一種路網(wǎng)環(huán)境下LBS隱私保護算法

左正魏,潘巨龍,魏琳琳

(中國計量學(xué)院 信息工程學(xué)院,浙江 杭州 310018)

近年來,基于位置服務(wù)(LBS)的應(yīng)用越來越廣泛.用戶在享受這種位置服務(wù)帶來的方便快捷之同時,也要承擔(dān)可能暴露自身隱私信息(如位置等)的風(fēng)險.目前,很多工作已經(jīng)在諸如保護用戶隱私信息方面取得了重大進展,但大多是集中于歐氏空間下的隱私保護技術(shù),而路網(wǎng)環(huán)境下的隱私保護研究相對較少.針對路網(wǎng)環(huán)境下用戶邊權(quán)分布不均的問題,提出了基于啞元的邊權(quán)均衡算法,即在保證匿名集中各路段鄰近性的同時,以生成啞元的方式均衡各邊邊權(quán)分布.這樣既能最大程度降低查詢代價,又能使邊權(quán)分布不會太分散.最后,通過實驗驗證了本算法的有效性,同時顯示該算法還能有效防止邊權(quán)分布不均引發(fā)的推斷攻擊.

位置服務(wù)LBS;路網(wǎng);邊權(quán);隱私保護

網(wǎng)絡(luò)技術(shù)、移動終端及地理信息系統(tǒng)(GIS)等技術(shù)的相互結(jié)合促使基于位置服務(wù)(location based services,LBS)的誕生.在LBS中,用戶向第三方服務(wù)提供者(third service provider,TSP)發(fā)出查詢請求,此請求攜帶自己的位置信息,服務(wù)提供者向用戶提供所請求的服務(wù),如用戶請求查找離自己最近的加油站等.在此服務(wù)過程中,用戶的隱私信息如位置等可能面臨泄漏的危險.隱私簡而言之就是不希望被別人知道的信息,曾經(jīng)有過某人利用GPS技術(shù)跟蹤別人的報道.隨著LBS應(yīng)用的普及,用戶隱私問題也將引發(fā)很大的擔(dān)憂,如文獻[1-2]中所提到的.于是LBS用戶的隱私保護問題被提了出來,目前,很多工作集中于歐氏空間下的用戶隱私保護,如文獻[3-12]等等,主要有假數(shù)據(jù)法、K-匿名模型及空間泛化等等,但路網(wǎng)環(huán)境下的研究相對較少.

在歐氏空間下用戶的移動方向是任意的,但實際情況中,用戶往往是沿著特定的路線如道路移動的,這時以前的很多隱私保護方法將遇到問題.圖1描繪了在歐幾里得空間下,采用某個現(xiàn)有傳統(tǒng)技術(shù)的匿名結(jié)果如圖(a)陰影部分,但是,在公路網(wǎng)絡(luò)環(huán)境下的圖(b)顯示,當采用相同的匿名技術(shù)時,匿名集中很有可能僅有一條路段,這樣,用戶q的位置信息將很容易被攻擊者跟蹤,使該用戶的位置隱私受到威脅.

于是,路網(wǎng)環(huán)境下的LBS隱私保護成為必須要解決的問題.在路網(wǎng)環(huán)境下,用戶沿著特定的道路網(wǎng)絡(luò)移動,這種情形下典型的隱私保護方法是K-匿名、L-路段長度技術(shù)[13],即形成的匿名路段集必須滿足至少有K個用戶,并且其總長度至少為L.這種算法顯然沒有考慮路段邊權(quán)分布問題.

圖1 歐式空間與路網(wǎng)環(huán)境匿名效果Figure 1 Anonimity in Euclidean and Road network space

1 相關(guān)工作

由于路網(wǎng)環(huán)境下用戶隱私問題受到越來越多的關(guān)注,各種保護算法被提了出來,但又各有其局限性.文獻[14]僅依賴于Casper匿名算法[15],而Casper主要應(yīng)用于歐氏空間下,故也繼承了歐氏空間算法的局限性.文獻[16]提出了層次化結(jié)構(gòu)模型,但由于該模型是靜態(tài)的,不能抵御重放攻擊.為了滿足相互性,文獻[18]為所有用戶設(shè)置一個靜態(tài)化的K-匿名參數(shù),顯然這不能滿足用戶的個性化需求,而且當用戶需要比給定K更小的隱私需求時,其降低了查詢服務(wù)質(zhì)量.Wang等人[17]提出了X-Star子圖匿名模型，其基本思想是將路網(wǎng)圖轉(zhuǎn)換為節(jié)點是子圖的星狀圖,而其節(jié)點子圖的度至少為3.X-Star雖然能滿足相互性,但最后所得匿名結(jié)果集中的路段總長度可能很長,從而增加了查詢處理開銷.Kim等人對X-Star進行了擴展,結(jié)合Hilbert曲線提出H-Star算法.H-Star算法將Star節(jié)點按照Hilbert曲線進行編號,將Star節(jié)點按K值要求分裝入bucket中.此算法雖然有些改進,但與X-Star有著同樣的問題,即匿名結(jié)果集中路段可能太長,導(dǎo)致查詢代價增大.周至賢等人提出了K-匿名、L-路段長度匿名算法.該算法要求最后形成的匿名集中包含至少K個用戶,且所有路段的長度不能少于L.該算法全面考慮了服務(wù)質(zhì)量與查詢代價的平衡,但沒有考慮用戶在地理上的分布問題.為了解決此問題,孫嵐等人提出了近鄰算法NA,其思想是利用關(guān)聯(lián)度來保證最后生成的匿名集中各路段邊權(quán)分布均衡,但它犧牲了一部分鄰近性,導(dǎo)到查詢開銷增大.

2 基礎(chǔ)知識與相關(guān)定義

2.1 相關(guān)定義

如果把公路網(wǎng)絡(luò)抽象出來,用一個帶權(quán)的無向圖G表示,這時便可以用一個三元組(V,E,W)來表示公路網(wǎng)絡(luò).其中,V表示頂點集合,vi屬于V,表示公路網(wǎng)中的節(jié)點i,也即路的交點或拐點.邊集用E表示,eij代表頂點vi與vj之間的邊.而W代表各邊權(quán)值的集合,邊eij的權(quán)值即該邊上的用戶數(shù)目用Wij表示.

定義1 關(guān)聯(lián)度

假如一個用戶向LBS服務(wù)提供者發(fā)送某個請求R,運用某個匿名算法來處理用戶的位置信息,最后生成一個匿名路段集S,?e∈S,稱邊e與匿名路段集S的關(guān)聯(lián)度為rel(S,e),其公式定義如下:

(1)

其中，e.w—邊e權(quán)值,也即邊e上的用戶數(shù)目.顯然,關(guān)聯(lián)度的范圍為0到1之間,且邊的關(guān)聯(lián)度正比于e.w,也就是該邊上的用戶數(shù)量.邊e的關(guān)聯(lián)度正好反映了該邊上用戶被攻擊者識別的概率.關(guān)聯(lián)度越大,用戶被識別的可能性也相應(yīng)增大,位置隱私泄露的風(fēng)險也越高.當匿名路段集中用戶所在的邊rel(S,e)值很大,也即用戶分布很不均勻時,攻擊者就能較容易識別出用戶所在的路段,從而造成隱私泄露.可見路網(wǎng)環(huán)境下也必須考慮用戶的分布均勻性問題,否則由前述可知,可能會帶來推斷攻擊,讓用戶的隱私受到威脅.

定義2 信息熵

信息熵是衡量匿名邊集中邊權(quán)分布是否均衡的一個指標,其值越大,則匿名集中各邊的關(guān)聯(lián)度越均衡,也即集合中各條邊的權(quán)重分布也越均衡,則抵抗邊權(quán)分布不均所引起的推斷攻擊的能力也越強.其定義如下:

Entropy(S)=∑e∈Srel(S,e)×log[A(S,e)].

(2)

定義3 開放節(jié)點

在匿名集S中,一個頂點v如果滿足以下條件:與v相交的所有邊都包含在S中,則稱點v是閉合節(jié)點,否則稱其是開放節(jié)點.

2.2 用戶分布不均引發(fā)的問題

正如前面所討論的,在路網(wǎng)環(huán)境下,很多歐氏空間下的傳統(tǒng)隱私保護算法將遇到問題.路網(wǎng)環(huán)境下最典型的隱私保護算法是周至賢教授提出的K-匿名加上L-路網(wǎng)長度算法[13].該算法提出選取的匿名路段集在滿足K-匿名的情況下,其總長度不得低于L.此算法雖然考慮了服務(wù)質(zhì)量與查詢代價的平衡,但它并沒有注意到用戶在地理上的分布情況,由此可能引發(fā)隱私泄露問題.如圖2所示:

圖2 邊權(quán)分布不均示例Figure 2 Uneven distribution of wedge weight

用戶q所在的路段v4v5是該網(wǎng)中用戶非常密集的路段之一,用mij表示路段ViVj上的用戶數(shù).假設(shè)在滿足用戶隱私需求的情況下,路段v4v5、v5v8、v3v4構(gòu)成了一個隱匿邊集,那么攻擊者已知路段用戶分布情況下可以猜測出q在路段v4v5上的概率為m45/(m45+m58+m34),如圖2的情況,此值接近于1,這便意味著用戶q與路段v4v5匹配的概率很高,位置隱私將受到威脅.本文針對以上問題提出一種基于啞元,也即偽用戶的邊權(quán)均衡算法,可有效地解決上述問題,并通過實驗驗證了該算法的有效性.

3 基于啞元的邊權(quán)均衡算法

3.1 查詢代價模型

找到離用戶最近的K個目標是一個典型的K近鄰查詢,該查詢中,用戶若直接提供自己的精確位置,稱為普通K近鄰查詢.若用戶的真實位置被泛化成一個匿名路段集,則稱此查詢?yōu)楸Ｗo隱私的K近鄰查詢,簡稱為隱私K近鄰查詢.對于這樣一種查詢,我們的目標是要找到查詢的候選結(jié)果集,其中包含了用戶所需的真實查詢結(jié)果.為方便起見,我們將此過程分為兩步:第一步是范圍內(nèi)查詢,即找到匿名路段集S里面的所有目標并將其加入到候選結(jié)果集中;第二步是外部查詢,即對于匿名集S中的每一個開放節(jié)點,運用K近鄰查詢,找到離開放節(jié)點最近的K個目標并將其加入到候選結(jié)果集中.圖3描繪了這兩個過程.

圖3 隱私K近鄰查詢Figure 3 Privacy K nearest neighbor query

假設(shè)用E(S)代表匿名集S中的邊數(shù),V0(S)表示匿名集中開放節(jié)點數(shù),R表示整個路網(wǎng)中所有路段數(shù),T表示整個路網(wǎng)中所有查詢目標,第一步為范圍內(nèi)查詢,即查詢S中所有路段的目標節(jié)點,我們可以用路段數(shù)來衡量其查詢代價,即E(S).第二步,對于每個開放節(jié)點,找到一個目標需要平均搜索R/T路段,所以找到K個目標即需搜索(R/T)×K條路段,故對于所有開放節(jié)點,搜尋的路段數(shù)為Vo(S)×K×R/T,這便是第二步的查詢代價衡量標準.綜上所述,我們有如下隱私查詢代價衡量公式

(3)

3.2 算法設(shè)計

正如上文所說,該算法首先是保證了路段之間的地理相近,也即每次選取離目標用戶在地理上最近的路段加入匿名集中,然后才是通過生成啞元的方式解決權(quán)值分布問題.故而本算法能生成最緊湊的匿名路段集,也就是能使查詢處理開銷最優(yōu),同時也保證了權(quán)值分布的均衡性.為此提出了各邊與目標用戶所在邊的相似度指數(shù)IoS(e),定義如下:

(4)

其中，m—目標用戶所在邊的邊權(quán)值,即用戶數(shù),e.w—邊e的權(quán)值,S—匿名路段集.相似度指數(shù)反映了各邊與目標用戶所在邊的權(quán)值差異性,IoS越小,權(quán)值分布越均勻;反之越分散.基于啞元的邊權(quán)隱私保護算法通過控制相似度指數(shù)小于某個閾值,從而控制邊權(quán)分布.該算法首先將路網(wǎng)中的各邊按距離目標用戶所在邊的網(wǎng)絡(luò)距離進行排序,每次選取離目標邊最近的邊加入匿名集中,首先檢查其權(quán)值是否滿足相似度指數(shù)閾值要求,若不滿足,則隨機生成最少數(shù)量的啞元(偽用戶)使得其滿足IoS(e)

Input: user U, query Q,IoSuOutput:S

1: Sorting all edges according to the network distance

2:e←the road segment contains the user U

3:S←{e}

4: while NumUser(S)

5: BestEdge←{e′|e′ is inSande′ is adjacent toSin the sorted sequence}

6: IfIoS(BestEdge)>u, Randomly generatendummies to satisfy IoS(BestEdge)≦u

7:S←S ∪ BestEdge

8: end while

9: returnS

4 實驗及結(jié)論

為了驗證本文提出基于啞元的邊權(quán)均衡隱私保護算法的有效性,將該算法(以下簡稱DA)與文獻[13]中提出的貪心算法(GA)及文獻[20]提出的NA進行比較,驗證了本文提出算法在降低查詢處理開銷方面的優(yōu)越性.本實驗用Java語言實現(xiàn),數(shù)據(jù)由路網(wǎng)環(huán)境下Brinkhoff路網(wǎng)生成器基于Oldenburg地圖產(chǎn)生,數(shù)據(jù)集大小如下表1.

表1 實驗參數(shù)

實驗環(huán)境為:Intel(R)Core(TM) i5-3470 CPU @3.2 GHz 3.2 GHz;4.00 GB內(nèi)存;Windows7操作系統(tǒng);Eclipse集成開發(fā)環(huán)境.

4.1 信息熵

信息熵可以反映算法所產(chǎn)生的匿名集中各邊權(quán)值的均衡性,信息熵越大,權(quán)值越均衡;反之則分散.圖4分別為在不同的K值和L值的情況下,算法NA和DA所產(chǎn)生匿名集信息熵的對比,圖中縱坐標表示信息熵,橫坐標分別表示K(用戶數(shù))和L(路段長度),由圖可知,在相同的K或L的情況下,本文所提出的算法DA的信息熵較高,也即邊權(quán)越均衡.

圖4 不同K值和L值下DA及NA信息熵對比Figure 4 Entropy of DA and NA with different K and L

4.2 查詢代價

通過式(3)的查詢代價公式,在不同的K值和L值的情況下對比了GA、NA和DA的查詢處理代價,如圖5.圖5中縱坐標表示查詢代價,橫坐標分別表示K和L,圖中顯示,當需求度K和L增大時,匿名路段集中必然會加入更多的路段,使匿名集中所包含的路段總數(shù)和邊界點數(shù)增加,從而導(dǎo)致查詢代價的增加,所以三種算法產(chǎn)生隱匿邊集所需的查詢處理代價也隨之增加.但由于本算法(DA)是首先保證各邊的鄰近性,再用產(chǎn)生啞元的方式來保證邊權(quán)的均衡性,所以使其產(chǎn)生的匿名邊集比GA還小,從而獲得更佳的查詢處理開銷.而NA由于首先保證邊權(quán)的均衡性,損失了一部分的鄰近性,從而查詢處理代價較大.

圖5 不同K值和L值下DA、GA及NA查詢代價對比Figure 5 Query cost of DA, GA and NA with K and L

4.3 查詢處理時間

在不同的K值的情況下,對GA、NA和DA從查詢時間的角度對比它們的查詢處理開銷,由圖6可知,圖中縱坐標表示查詢時間(ms),橫坐標表示K值.NA由于保證了邊權(quán)的均衡,從而犧牲了查詢代價,其查詢時間較GA更大.但DA在保證匿名邊集的鄰近性上達到了與GA同等的程度,而且由于增加了啞元,使得匿名邊集里的邊數(shù)進一步降低,從而有了更少的查詢處理時間.

圖6 不同K值下DA、GA與NA查詢時間對比Figure 6 Query time of DA,GA and NA with different K

綜上所述,相比于GA與NA,本文提出的基于啞元的邊權(quán)均衡算法(DA),在保證匿名集中各邊的鄰近性的前提下,產(chǎn)生啞元以均衡各邊的權(quán)值,使得其在鄰近性上能達到GA的效果,而又有NA的抵御推斷攻擊的優(yōu)點.不僅如此,由于啞元的引入,使得K匿名性更易滿足,使得匿名結(jié)果集中邊的數(shù)量進一步降低,從而使查詢處理開銷進一步降低.

5 結(jié) 語

本文針對路網(wǎng)環(huán)境下用戶邊權(quán)分布不均而可能引發(fā)隱私泄露的問題,提出了基于啞元的邊權(quán)均衡算法,實驗表明,在同等條件下本算法具有更好的隱私保護性能和較小的查詢代價.下一步的工作重點將放在邊權(quán)均衡算法的優(yōu)化上,以期達到更好的查詢效率,讓用戶在享受最大的隱私保護情況下獲得更好的用戶體驗.

[1] MOKBEL M F. Privacy in location based services: state of the art and research directions[C]//International Conference on Mobile Data Management. Mannheim:IEEE,2007:228-228.

[2] PEDRESCHI D, BONCHI F, TURINI F, et al. Privacy protection: regulations and technologies, opportunities and threats[C]//Mobility, Data Mining and Privacy. Berlin: Springer,2008:101-119.

[3] SHANKAR P, GANAPATHY V, IFTODE L. Privately querying location-based services with sybilquery[C]//Proceedings of the 11th International Conference on Ubiquitous Computing. New York: ACM,2009:31-40.

[4] GRUTESER M, GRUNWALD D. Anonymous usage of location based services through spatial and temporal cloaking[C]//Proceedings of the 1st International Conference on Mobile Systems, Applications and Services. New York: ACM,2003:31-42.

[5] ZHANG C, HUANG Y. Cloaking locations for anonymous location based services: a hybrid approach[J].Geoinformatica,2009,13(2):159-182.

[6] BAMBA B, LIU L, PESTI P, et al. Supporting anonymous location queries in mobile environments with privacygrid[C]//Proceedings of the 17th International Conference on World Wide Web. New York: ACM,2008:237-246.

[7] LI N, LI T, VENKATASUBRAMANIAN S.t-closeness: privacy beyondk-anonymity andl-diversity[C]//Proceedings of the 23rd International Conference on Data Engineering. Istanbul: IEEE,2007:106-115.

[8] SOLANAS A, SEBE F, DOMINGO-FERRER J. Micro aggregation based heuristics for p-sensitive k-anonymity: one step beyond[C]//Proceedings of the 2008 International Workshop on Privacy and Anonymity in Information Society. New York: ACM,2008:61-69.

[9] MASCETTI S, BETTINI C, WANG X S, et al. Providenthider: An algorithm to preserve historical k-anonymity in lbs[C]//Tenth International Conference on Mobile Data Management: Systems, Services and Middleware. Taipei: IEEE,2009:172-181.

[10] ARDAGNA C A, CREMONINI M, DAMIANI E, et al. Location privacy protection through obfuscation-based techniques[C]// Data and Applications Security XXI. Berlin: Springer,2007:47-60.

[11] CHENG R, ZHANG Y, BERTINO E, et al. Preserving user location privacy in mobile data management infrastructures[C]//Privacy Enhancing Technologies. Berlin: Springer Berlin Heidelberg,2006:393-412.

[12] LEE J G, HAN J, WHANG K Y. Trajectory clustering: a partition-and-group framework[C]//Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data. New York: ACM,2007:593-604.

[13] CHOW C Y, MOKBEL M F, BAO J, et al. Query-aware location anonymization for road networks[J].GeoInformatica,2011,15(3):571-607.

[14] KU W S, ZIMMERMANN R, PENG W C, et al. Privacy protected query processing on spatial networks[C]//Proceedings of the 23rd International Conference on Data Engineering Workshop. Istanbul: IEEE,2007:215-220.

[15] MOKBEL M F, CHOW C Y, AREF W G. The new casper: query processing for location services without compromising privacy[C]//Proceedings of the 32nd International Conference on Very Large Data Bases:New York: ACM,2006:763-774.

[16] PENG W C, WANG T W, KU W S, et al. A cloaking algorithm based on spatial networks for location privacy[C]//Proceedings of International Conference on Sensor Networks, Ubiquitous and Trustworthy Computing. Taichung: IEEE,2008:90-97.

[17] WANG T, LIU L. Privacy-aware mobile services over road networks[J].Proceedings of the VLDB Endowment,2009,2(1):1042-1053.

[18] MOURATIDIS K, YIU M L. Anonymous query processing in road networks[J].IEEE Transactions on Knowledge and Data Engineering,2010,22(1):2-15.

A privacy protection algorithm designed for LBS in road networks

ZUO Zhengwei, PAN Julong, WEI Linlin

(College of Information Engineering, China Jiliang University, Hangzhou 310018, China)

In recent years, location based services (LBS) have become more and more popular. However, the user’s privacy information such as his(her) locations is threatened, while the user enjoys the convenience and effectiveness provided by such services. Many different approaches have been raised to protect the user’s privacy under Euclidean space. But these approaches rarely focus on conditions under road networks. Now, we propose an edge weight balancing algorithm. The main idea of this algorithm is to create anonymous sets to guarantee the proximity of all edges and then to generate dummies to balance edge weight. Finally, the experiment verifies that the algorithm is able to resist inference attacks caused by uneven edge weight distributions.

location based services; road networks; edge weight; privacy protection

1004-1540(2015)03-0359-06

10.3969/j.issn.1004-1540.2015.03.020

2015-05-18 《中國計量學(xué)院學(xué)報》網(wǎng)址：zgjl.cbpt.cnki.net

左正魏(1988- ),男,湖北省隨州人,碩士研究生,主要研究方向為LBS隱私保護.E-mail:zzwstriver@163.com 通訊聯(lián)系人：潘巨龍,男,教授.E-mail:pjl@cjlu.edu.cn

TP309

A