基于位置語義的路網位置隱私保護

陳慧1,2,3，秦小麟1,3

(1. 南京航空航天大學計算機科學與技術學院，江蘇 南京 211106；2. 南京信息工程大學電子與信息工程學院，江蘇 南京 210044；3. 江蘇省物聯網與控制技術重點實驗室，江蘇 南京 211106)

基于位置語義的路網位置隱私保護

陳慧1,2,3，秦小麟1,3

(1. 南京航空航天大學計算機科學與技術學院，江蘇 南京 211106；2. 南京信息工程大學電子與信息工程學院，江蘇 南京 210044；3. 江蘇省物聯網與控制技術重點實驗室，江蘇 南京 211106)

移動用戶在享受基于位置的服務（LBS）的同時受到位置隱私泄露的威脅，因而提供有效的位置隱私保護策略至關重要。傳統的位置隱私保護方法主要采用空間匿名的方式，若攻擊者獲得了更多與匿名空間相關的背景知識，尤其是與位置相關的語義信息，就會嚴重降低匿名效果。為了防止由位置語義分析造成的敏感位置信息泄露，并根據移動用戶活動范圍大多限定為道路網絡的特點，提出一種基于位置語義的路網位置隱私保護方法，充分考慮了用戶的個性化隱私需求，并通過實驗驗證了方法的可行性及有效性。

位置語義；隱私保護；路網；敏感度；普及度

1 引言

近年來，無線通信技術、定位技術及移動對象數據庫管理技術取得了迅速發(fā)展。與此同時，移動計算設備的計算能力和存儲能力也在不斷提高，各種終端如便攜機、個人數字助理、移動電話、傳感器、車載終端等逐漸普及。得益于物聯網的興起，基于位置的服務（LBS,location based service）從早期的應用于緊急情況下快速定位求助者位置逐步擴展到更為廣泛的應用領域[1,2]。在 LBS中，用戶通過移動定位裝置獲取自己的位置信息，并利用位置信息取得相關服務。如個人用戶可以查詢離自己最近的酒店；交通管理部門可以掌握某個時段某段道路上的路況信息；商家可以向位于店鋪附近的客戶發(fā)送電子廣告或優(yōu)惠券等。

在LBS中，用戶將自己的位置信息及服務請求發(fā)送給位置服務器，服務器根據接收到的位置信息對用戶的服務請求進行處理。因此，用戶位置信息的準確性直接決定了LBS的服務質量。盡管服務提供商聲稱自己是安全可靠的，但這種服務方式的自身特點決定了用戶在享受服務的同時，必然會泄露位置信息。根據這些位置信息，攻擊者可以進一步推理分析出用戶的身份、行為、習慣等其他信息，而這些信息往往是用戶不希望泄露的隱私信息。如果服務器受到惡意攻擊，甚至可能服務器本身就是攻擊者，攻擊者從服務器得到用戶的隱私信息，將造成更大的損失。Duckham等[3]指出，位置隱私是一種特殊的信息隱私，強調由個人決定何時、以何種方式、以何種程度將自己的位置信息與別人分享。而位置隱私威脅是指攻擊者在未經授權的情況下，通過定位位置傳輸設備、竊聽位置信息傳輸通道等方式訪問原始的位置數據，并根據這些數據進行推理分析，從而獲取與位置信息相關的個人隱私信息[4]。移動對象位置隱私保護技術能夠確保用戶在享受LBS的同時，保護自己的隱私信息，具有重要意義。

至今，針對LBS中的位置隱私問題，研究者們相繼提出了多種解決方案[5～13]。其中，大部分隱私保護策略采用位置模糊化方法并引入k-匿名思想，將發(fā)出 LBS請求的用戶的精確位置泛化為一個模糊區(qū)域作為匿名空間提交給位置服務器，使該匿名空間中，移動用戶不能與其他至少k?1個用戶相區(qū)分。這類措施降低了用戶被攻擊者推理分析出準確位置的可能性，對位置隱私起到了一定的保護作用。然而，這些方法大多沒有考慮到：攻擊者如果掌握了足夠的有關匿名空間的背景知識，就可以根據這些背景知識推理分析出更多信息，提高攻擊者的攻擊能力，從而嚴重降低匿名空間的隱私度。值得注意的是，匿名空間除了包含移動用戶，還包含很多位置。而這些位置是帶有語義信息的，比如位置的類型（醫(yī)院、學校等）就是一種語義信息。并且，不同類型的位置具有不同的敏感度，比如與公園相比，醫(yī)院是一個更為敏感的位置。此外，不同類型的位置其熱門程度也不同，比如與一個門禁森嚴的軍事基地相比，商場的熱門程度更高，人流量更大，即商場的普及度比軍事基地的普及度高。如果這些豐富的位置語義信息被攻擊者獲得，攻擊者即可根據這些信息排除匿名空間中的一些位置，從而提高攻擊能力。下面通過2個例子更直觀地闡述該問題。

例1 假設Bob剛結束治療從診所出來，發(fā)出一個查詢請求，查找離自己最近的咖啡店。為了保護Bob的當前位置隱私，為其構造了一個匿名空間。假設該匿名空間中包含10個位置，其中有5個都與診所相關，那么攻擊者將Bob定位到診所的可能性明顯增加。而診所恰恰是Bob不想讓別人知道的位置，因此診所對Bob來說是敏感的位置。

例2 同樣以例1中的Bob為例，假設構造的匿名空間中包含2個位置，一個是Bob所在的診所，另一個是一座廢棄的工廠。那么，攻擊者在獲得了匿名空間中這2個位置的語義信息后，很容易排除掉廢棄的工廠，從而將Bob定位在診所。

例1中構造的匿名空間之所以隱私度低，是因為其中包含了多個敏感度較高的位置，從而提高了攻擊者推理分析的準確性。即使用戶不在敏感位置，如果把用戶所在位置和敏感位置放在一起構成匿名空間，一旦被攻擊，則被懷疑在這些敏感位置的可能性也會增加。而這同樣是用戶不愿意接受的，因為用戶并不希望自己被誤認為在敏感位置。例2中所構造的匿名空間之所以隱私度低，是因為其中包含了普及度低的位置。

另一方面，同一類型的位置對不同的人所包含的語義信息是不同的。在上述例子中，假設Bob是一名醫(yī)生，這時，診所對于Bob并不是一個敏感位置。

由此可見，匿名空間的隱私度受位置語義的影響，而位置語義又是因人而異的。因此，本文提出的位置隱私保護方法，在構造匿名空間的過程中，將位置的語義信息作為一個重要的考察因素。

此外，現有的隱私保護策略普遍存在以下2點局限性。

1)大部分是針對歐式空間提出的，并不適用于路網空間。而現實生活中，移動用戶的活動范圍更多被限制在道路上。

2)大部分在滿足用戶的個性化隱私需求方面存在不足。一些方法中用戶的隱私需求是固定的。另一些方法即使允許用戶設定隱私需求，通常也只能對匿名空間的k值進行設定。而在實際問題中，除k值外，還有很多其他因素，比如用戶所處的環(huán)境、用戶本人的特征等都與匿名空間的隱私度息息相關。

針對上述問題，本文的貢獻主要有以下幾方面。

1)提出了一種隱私度量方法，該方法在度量匿名空間隱私度時將位置的語義信息作為重要的評價因素。

2)滿足用戶的個性化隱私需求。

3)提出了一種適合路網空間的位置隱私保護方法。

2 相關工作

目前已有的移動對象隱私保護方法主要分為以下幾類。

1)基于策略的方法（policy-based scheme），這類方法主要是研究用戶位置隱私策略，具體探討特定的地址信息應該何時公布給哪些對象。

2)空間匿名方法（spacial cloaking scheme），這類方法是較早提出的一類位置隱私保護方法，其本質是用一個空間區(qū)域來表示用戶的真實位置。其中，使用最多的是位置 k-匿名模型（location k-anonymity model）。該模型由美國卡內基梅隆大學的Sweeney[14]提出，最早在關系數據庫的數據發(fā)布隱私保護中得到使用。k-匿名模型的主要思想是使一條數據表示的個人信息與其他至少k?1條數據不能區(qū)分。Gruteser[15]將 k-匿名思想引入位置隱私保護，提出了位置k-匿名模型。位置k-匿名的主要目的是使一個移動對象的位置無法與其他k?1個移動對象的位置相區(qū)分。Mokbel[16]提出一種Casper方法，采用一種金字塔數據結構搜索用戶生成匿名集。

3)位置擾動方法（obfuscation scheme），這類方法的主要思想是通過在真實位置周圍添加假位置或某些固定位置，或對真實位置按照某種策略進行變換，從而降低真實位置的精確度。Kido[17]通過生成假位置來降低真實位置的精確度，達到保護位置隱私的目的。Duckham[18]采用添加固定位置（如岔路口）的方法實現對真實位置的擾動。Ardagna[19]采用3種擾動技術（擴大范圍、轉移重心、縮小范圍）中的一種或多種對真實位置實施擾動。

4)基于加密的方法（cryptography-based schemes），這類方法在用戶端將位置通過設定的加密策略進行完全的轉換，使服務器可以處理用戶的查詢請求，但無法獲知用戶的真實位置。Ghinita[20]提出一種基于隱私信息檢索（PIR,private information retrieval）的方法，無需用戶信任任何第三方匿名器即能返回準確結果。但該方法僅支持隱私最近鄰查詢，且計算代價較高。

目前的位置隱私保護策略大多是針對歐式空間提出的，較少給出面向路網的隱私保護方案[21]。Chow[22]提出一種面向路網的位置隱私保護方法，將用戶位置模糊化為若干相鄰的路段，并在構造匿名集時考慮查詢代價和查詢質量。Palanisamy[23]提出一種利用動態(tài)假名機制混合區(qū)域在道路網絡中實現混淆的匿名技術。然而，上述方法在構造匿名集時并未考慮匿名集中位置的語義信息。Damiani[24]指出傳統的k-匿名方法無法保護敏感的位置，由此提出了一種匿名方法解決社交網絡位置分享應用中的敏感位置泄露問題。Yigitoglu[25]提出了一種適合道路網絡的社交網絡位置分享應用中保護敏感信息的方法。上述2種方法僅以位置的普及度來判斷位置的敏感程度，并未考慮不同位置對不同用戶的敏感程度。

針對LBS中的位置隱私保護問題，本文給出一種面向道路網絡的位置隱私保護方法，在匿名集構造過程中引入位置的語義信息。具體地，在考慮位置普及度的同時，考慮不同位置對不同用戶的敏感度，進而考察匿名區(qū)域對不同用戶的隱私度。此外，允許用戶設置個性化的隱私需求。

3 背景知識與問題定義

3.1 系統結構

位置隱私保護策略中采用的位置匿名體系結構主要分為3類：獨立結構、中心服務器結構和分布式點對點結構[26]。本文采用的是中心服務器結構，如圖1所示。該結構的主要特點在于，在客戶端和位置服務器之間增加了一個可信第三方，即匿名服務器。當用戶發(fā)出查詢請求時，將自己的精確位置、查詢內容以及隱私需求一起發(fā)送給匿名服務器。匿名服務器根據用戶的隱私需求對用戶的精確位置進行匿名處理，并將處理后生成的匿名位置與查詢內容一起提交給位置服務器。位置服務器計算出候選查詢結果，并發(fā)送給匿名服務器。匿名服務器對查詢結果進行分析處理，最后將經過求精處理的查詢結果返回給用戶。本系統中，為了構造有效的匿名集，匿名服務器需要保存當前的地圖信息以及道路信息，并實時更新道路中移動用戶的信息。

圖1 中心服務器結構

3.2 位置語義信息

本文提出的匿名算法將查詢請求用戶的真實位置隱藏于多條鄰接的路段中，即由多條鄰接路段構成匿名集RS，且該集合滿足用戶的個性化隱私需求。整個道路網絡表示為一個連通圖G=(V,E)，其中，V是頂點的集合，表示路段的端點以及鄰接路段的交點；E是邊的集合，表示路段。每一條路段Segi( sid,s,t )∈E是道路網絡中的一條邊，其中，sid是路段的編號，s和t分別表示路段的起點和終點。

本文主要從位置的語義信息出發(fā)，探討位置語義對位置隱私的影響，下面給出所涉及的語義信息定義。

定義1位置。用pos(lid,sid,x,y,tp)表示道路上的位置，其中：lid是位置的編號，sid是該位置所在路段的編號，(x,y)表示該位置的坐標，tp表示該位置所屬的類型。所有位置劃分為n種類型，則TP={tp1,tp2,…,tpn}為n種位置類型的集合。

定義 2位置普及度。系統為每個位置類型tpi∈TP設置一個普及度 poptpi，用來表示該位置的熱門程度，則POP={poptp1,poptp2,…,poptpn}是所有位置類型所對應的普及度的集合。

定義 3位置敏感度。用戶為每個位置類型tpi∈TP設置一個敏感度sentpi，用來表示該位置相對該用戶的敏感程度，則 SENu={sentp1,sentp2,… ,sentpn}是所有位置類型相對用戶 u所對應的敏感度的集合。

3.3 用戶隱私需求

本方法允許用戶定制個性化的隱私需求，主要有以下3方面。

1)匿名集中的移動用戶數量(RS.UN)。要求能夠使用戶在匿名集中至少與其他k?1個用戶無法區(qū)分。該需求源于經典的k-匿名需求，是位置隱私保護中最常用也是最基本的需求。

2)匿名集中的路段數量(RS.SN)。要求匿名集中路段的數量不能少于用戶設定的數值。如果匿名集中的路段數量過少，比如僅包含一條路段，那么即使匿名集中有多個移動用戶，攻擊者的攻擊難度也顯著降低了。

3)匿名集的隱私度。要求匿名集中盡可能多地包含對該用戶而言不敏感的位置。

此外，匿名集的普及度也是一個重要的隱私需求，要求匿名集中盡可能多地包含普及度高的位置，即人們經常光顧的位置。普及度較低的位置很容易被攻擊者排除，從而降低攻擊難度。為方便分析，本系統中的普及度由系統自定義，因此不屬于個性化隱私需求范疇。

根據上述分析，對用戶的隱私需求做如下定義。

定義 4隱私需求。對一個發(fā)出匿名請求的用戶u，其隱私需求用PRu(UN,SN,SENu)表示。其中，UN是用戶自定義的匿名集中移動用戶數量下限；SN是用戶自定義的匿名集中路段數量下限；SENu是用戶自定義的一組位置敏感度，根據個性化的隱私需求，相同類型的位置對不同用戶的敏感度是不同的。

3.4 問題定義

在本文系統中，對攻擊者做出如下假設：1)攻擊者擁有地圖和路段信息；2)攻擊者擁有移動用戶的位置信息，但不知道移動用戶的身份；3)攻擊者可以獲知路段上移動用戶的數量；4)攻擊者沒有用戶的背景信息。此外，本文假設匿名服務器對用戶來說是可信的。

因此，本文需要解決的問題歸結為根據用戶的個性化隱私需求，以及與位置語義信息相關的普及度、敏感度等隱私需求，將用戶的真實位置隱藏在由多條相鄰路段構成的集合中，為用戶構造一個匿名集RS。

4 基于位置語義的匿名方法

4.1 隱私度量

根據上述分析，顯然，匿名集中的位置所帶有的語義信息直接影響匿名集的隱私度。因此，在度量一個匿名集的隱私度時，除了考慮匿名集所包含的移動對象數量以及路段的條數，還要考慮該匿名集的語義信息。本文分別用區(qū)域普及度和區(qū)域敏感度來表示位置的語義信息對匿名集的影響。

定義 5區(qū)域普及度。一個區(qū)域reg的普及度POPreg，由該區(qū)域中所包含位置的普及度確定，其值為其中，|TP|為區(qū)域 reg中所含位置類型的總數；NumPos(reg)為區(qū)域reg中所含位置的數量。

定義6區(qū)域敏感度。一個區(qū)域 reg的敏感度SENreg，由該區(qū)域中所包含位置的敏感度確定，其值為

式（1）和式（2）共同給出基于位置語義的匿名區(qū)域隱私度量標準。

定義7區(qū)域隱私度。一個區(qū)域 reg的隱私度PRMreg由區(qū)域普及度和區(qū)域敏感度共同確定，其值為

4.2 基于位置語義的匿名集構造

根據用戶定義的隱私需求選擇合適的相鄰路段構造匿名集，主要解決的問題是如何確定哪些路段是可選的。本文采用邊選擇邊判斷的策略，其主要思想是：每次在候選路段中選擇一條路段，使當前匿名集關于區(qū)域隱私度條件是最優(yōu)的；每選擇出一條路段，判斷當前匿名集是否符合隱私需求。

匿名集由包含匿名請求用戶所在路段在內的若干相鄰路段構成，因此，從用戶所在的路段出發(fā)，將該路段選為匿名集 RS中的第一條路段。每選出一條路段，判斷當前匿名集是否滿足用戶定義的隱私需求。若滿足，則將當前匿名集作為最終的匿名集返回；若不滿足，則找出當前匿名集中所有路段的相鄰路段，在這些路段中選擇一條最優(yōu)路段加入當前匿名集。這里，所謂最優(yōu)路段是指由該路段構成的匿名集關于區(qū)域隱私度條件在候選路段中是最優(yōu)的。當一個匿名區(qū)域的普及度越高，同時敏感度越低時，這個匿名區(qū)域的隱私度就越高。顯然，這里選出的路段應使當前匿名集的區(qū)域隱私度PRMRS最大。根據上述原則，每次向當前匿名集增加一條路段，直至匿名集滿足隱私需求。

算法1給出了最優(yōu)路段選擇算法偽代碼。該算法的輸入參數為當前匿名區(qū) CRS、相鄰路段集合SEGS以及位置敏感度集合SENS。算法1首先對相關參數進行初始化（算法1第1）行）；然后將每條相鄰路段分別加入當前匿名區(qū)，計算合并區(qū)域的區(qū)域普及度、區(qū)域敏感度和區(qū)域隱私度（算法1第2）～6）行），并記錄區(qū)域隱私度最大的路段作為當前最優(yōu)路段（算法1第7）行）；最后返回最優(yōu)路段（算法1第9）行）。

算法1最優(yōu)路段選擇算法（OPTSEG）

輸入：當前匿名區(qū)CRS，相鄰路段集合SEGS，位置敏感度集合SENS

輸出：最優(yōu)路段BESTSEG

1)BESTSEG=Φ; MAX=0;

2)for each Seg in SEGS

3)將Seg賦值給e;

4)PR=POP(CRS∪e);

5)SR=SEN(CRS∪e);

7)用MAX記錄MR的當前最大值，并將對應的e賦值給BESTSEG;

8)end for

9)return BESTSEG

算法2給出了基于位置語義的匿名集構造算法偽代碼。該算法的輸入參數為發(fā)起匿名查詢請求的用戶U、用戶請求的查詢Q以及由用戶定義的隱私需求PRu。在隱私需求PRu中，用戶根據自己的實際情況，定義了匿名集中至少需包含的移動用戶數量 PRu.UN、至少需包含的路段條數 PRu.SN，更重要的是給出每種位置類型相對自己的敏感度PRu.SENu。算法2首先將發(fā)出請求的用戶所在的路段放入匿名集RS（算法2第3）行），如果此時RS不滿足用戶隱私需求中的PRu.UN和PRu.SN，則循環(huán)執(zhí)行如下步驟直至RS滿足PRu.UN和PRu.SN條件為止（算法2第4）行）：1）將當前RS中所有路段的相鄰路段放入集合R中（算法2第5）行）；2）對R中的每一條路段ei，計算區(qū)域RS∪ei的隱私度，選擇區(qū)域隱私度最大的一條路段加入匿名集RS（算法2第6）、7）行）。

算法 2基于位置語義的匿名集構造算法（LSBASC）

輸入：用戶U，查詢Q，隱私需求PRu

輸出：匿名集RS

1)RS=Φ;

2)將用戶所在的路段賦值給BestEdge;

3)將BestEdge放入匿名集RS;

4)while NumUser(RS)lt; PRu.UN or NumSeg(RS)lt; PRu.SN

5)R=FindEdges(RS);

6)BestEdge=OPTSEG(RS,R,PRu.SENu);

7)將BestEdge放入匿名集RS;

8)R=Φ;

9)end while

10)return RS

下面以用戶User為例闡述上述具體過程。為分析方便，這里僅給出6條路段，如圖2所示。路段旁邊用一對值(Segi,num)表示路段的編號以及該路段上當前的移動用戶數量。圖中User所在的位置由箭頭標識。設置TP={tp1,tp2,tp3,tp4}，其中，tp1=醫(yī)院，tp2=酒吧，tp3=商場，tp4=學校。設定 poptp1=0.3，poptp2=0，poptp3=0.4，poptp4=0.3。用戶定義的隱私需求為 PRu(UN,SN,SENu)，其中，PRu.UN=50，PRu.SN=3，PRu.SENu={0.5,0.3,0.2,0}。根據算法步驟，首先將User所在的路段Seg1加入匿名集RS中，由于 NumUser(RS)=10，NumSeg(RS)=1，不滿足隱私需求，繼續(xù)執(zhí)行算法步驟：將與Seg1鄰接的路段Seg2、Seg3和Seg4加入集合R，根據區(qū)域隱私度量標準分別計算得到 PRM(RS∪Seg2)=1.263，PRM(RS∪Seg3)=1.87，PRM(RS∪Seg4)=1.133，根據計算結果選擇 Seg3加入匿名集 RS。此時，由于NumUser(RS)=40，NumSeg(RS)=2，仍然不滿足隱私需求，繼續(xù)執(zhí)行算法選擇鄰接路段。將與 Seg1和Seg3鄰接的路段Seg2和Seg4加入集合R，計算得到PRM(RS∪Seg2)=1.737，PRM(RS∪Seg4)=1.733，因而將 Seg2加入匿名集RS。此時，NumUser(RS)=60，NumSeg(RS)=3，已滿足隱私需求，算法結束，返回RS={Seg1,Seg2,Seg3}作為用戶User的匿名集。

本文提出的匿名方法主要考慮位置語義對匿名空間隱私度的影響，將位置語義信息作為主要因素構造匿名空間。因此，匿名集的隱私度主要由區(qū)域隱私度決定，而區(qū)域隱私度僅與匿名集中位置語義有關，對服務質量沒有直接影響。在匿名集構造過程中所考慮的k值和匿名集大小，僅為滿足用戶隱私需求而設置的限值，并不是影響服務質量的主要因素。值得注意的是，本方法中匿名集的構造是一個路段數量不斷增加的過程，而路段數量直接決定候選集大小，最終影響服務質量。因此，在具體操作過程中，需對路段數量設置上限。

5 實驗及結果分析

本文算法實驗硬件環(huán)境為3.20 GHz的Intel四核 CPU，4 GB內存。操作系統平臺是 Microsoft Windows 7 Professional。

5.1 實驗數據集和參數設置

實驗數據采用德國Oldenburg市的公路網絡數據[27,28]，共包括6 105條道路，7 035個頂點。利用Brinkhoff[29]的基于網絡的移動對象生成器生成了10 000個均勻分布的移動用戶，為了評估算法的匿名性能，用戶數考察范圍為5 000～25 000。同時，通過修改數據生成器，在擬生成的位置數據屬性中增加一維語義信息，生成了4種類型（包括醫(yī)院、酒吧、商場及學校）的10 000個在公路網絡中均勻分布的感興趣點（位置）。另外，實驗設置了1 000個發(fā)出匿名請求的移動用戶。

用戶發(fā)出的隱私需求包括 3個參數，即（PRu.UN,PRu.SN,PRu.SENu）?？紤]實際隱私保護中，隱私需求的路段數不可能無限制增加，實驗中需要設置最大值，表示為PRu.SNmax。所有實驗參數設置見表1所示。

表1 參數設置

5.2 算法性能評價標準

實驗從匿名成功率、平均匿名執(zhí)行時間、相對匿名度及相對空間粒度4個方面對提出算法進行評價。

1)匿名成功率，即算法成功匿名的消息數在所有移動用戶提出的匿名請求的消息數中所占的比例[26]。該指標反應位置匿名算法對匿名請求的響應能力，匿名成功率越高，匿名算法越好。

2)平均匿名執(zhí)行時間，即在統計平均意義上，位置匿名器對用戶真實位置進行匿名處理所花費的時間。該指標能夠用來衡量位置匿名算法的運行效率，平均匿名時間越短，算法匿名執(zhí)行效率越高。

3)相對匿名度，指匿名執(zhí)行后匿名集中包含的用戶數量與用戶位置隱私要求中的用戶數量（PRu.UN）的比值[26]，即用公式表示為

在匿名成功的情況下，相對匿名度的值大于等于 1。一般地，隨著相對匿名度值的增加，匿名效果提高。

4)相對空間粒度，指匿名器針對用戶匿名請求所限定的可容忍的最大匿名路段數 PRu.SNmax與匿名執(zhí)行后匿名集中包含的路段數的比值[26]，用公式表示為

相對空間粒度越大，意味著在滿足隱私需求的前提下，匿名空間越小，更接近最優(yōu)解。因此，相對空間粒度越大越好。

5.3 實驗結果分析

1)匿名成功率。圖3給出了匿名成功率相對于道路網總的移動用戶數、隱私需求的移動用戶數量以及隱私需求的路段數的變化情況。圖3(a)結果顯示，道路網移動用戶數越多，越有利于匿名執(zhí)行，匿名成功率越高。這不難理解，因為用戶數量越多，分布在各個道路上的用戶也越多，隱私需求越容易滿足，匿名成功率得到提高。反之，當用戶數量少到一定程度，導致各個道路上的用戶很少，在執(zhí)行匿名請求過程中，當匿名集中路段數達到可容忍的最大限度時，很難保證匿名集中用戶數同時滿足要求，導致匿名失敗。

在圖 3(b)中，隨著隱私需求的用戶數PRu.UN的增加，匿名成功率下降。當道路網用戶數在 10 000，PRu.UN、PRu.SN和PRu.SNmax分別設定為30、6和20情況下，匿名成功率不到50%。可見，隱私需求的用戶數不宜設置過大。而從圖3(c)中可以看出，無論是道路網用戶數相對較多還是相對較少，隱私需求的路段數 PRu.SN的變化并未帶來匿名成功率的較大變化。因此，為了減小匿名執(zhí)行計算負擔，從匿名成功率角度考慮，PRu.SN不需要設定得過大。

圖3 匿名成功率

2)平均匿名執(zhí)行時間。根據圖4，在道路網上的移動用戶數一定的情況下，隨著隱私需求用戶數PRu.UN的增加或者隱私需求路段數PRu.SN的增加，平均匿名執(zhí)行時間將增加。進一步，從圖4(b)可知，這種平均匿名執(zhí)行時間增加的程度隨著道路網上的用戶數的增多而顯得更為明顯。其原因在于：當道路網上的用戶數明顯較多時，算法在判斷鄰近路段的選擇所涉及的區(qū)域匿名度的計算隨著隱私需求路段數的增加而需耗費更多的時間。另一方面，圖 4顯示，在相同隱私需求條件下，即隱私需求用戶數相同、隱私需求路段數相同，道路網上移動用戶數量越大，平均匿名執(zhí)行時間越短。原因在于：當道路網上的移動用戶數量越大，在同等路段選擇時，隱私需求的用戶數更容易滿足，節(jié)省了判斷計算時間。

圖4 平均匿名執(zhí)行時間

3)相對匿名度。圖5給出了相對匿名度與隱私需求用戶數PRu.UN的關系。圖中結果顯示，隨著PRu.UN的增大，相對匿名度略微減小，但在匿名成功的情況下，均大于等于 1。而在匿名失敗的情況下，相對匿名度小于 1，這正是圖中當道路網上的移動用戶數為10 000時，PRu.UN為30和35所對應的情形。因為對于這2種情形，匿名失敗的情況可能較多，而被統計在內。同時可看出，隨著道路網上的用戶數增加，算法的匿名效果提高。

圖5 相對匿名度與隱私需求用戶數PRu.UN的關系

4)相對空間粒度。圖6給出了相對空間粒度與隱私需求用戶數PRu.UN的關系。從圖6可以看到，隨著PRu.UN的增大，相對空間粒度同樣呈現下降趨勢，且變化較明顯。原因在于：PRu.UN的增大將直接導致匿名集中路段數的增加，從而降低相對空間粒度。同時，圖6顯示，在較少的隱私需求用戶數條件下能夠獲得較高的相對空間粒度，意味著適當低的隱私需求用戶數能夠獲得較優(yōu)的匿名空間。另一方面，道路網上移動用戶數量的增加也能夠帶來更大的相對空間粒度。

圖6 相對空間粒度與隱私需求用戶數PRu.UN的關系

此外，選取了Chow[22]針對路網的LBS隱私保護提出的匿名集構造方法（PG算法），通過考察平均區(qū)域隱私度，進行了性能比對。圖7給出了平均區(qū)域隱私度與隱私需求用戶數 PRu.UN、感興趣點數及用戶數的關系。由圖7可知，在隱私需求用戶數 PRu.UN、感興趣點數及用戶數變化的情況下，本文 LSBASC算法構造的匿名區(qū)域其隱私度均高于PG算法構造的匿名區(qū)域隱私度。原因在于：PG算法沒有考慮位置語義在構造匿名集過程中的影響，而本文LSBASC算法在構造匿名集過程中充分考慮了位置普及度和敏感度，使構造的匿名區(qū)域的隱私度明顯提高。

6 結束語

本文給出了一種基于位置語義的路網位置隱私保護方法，該方法解決了現實道路網上的移動用戶在發(fā)出 LBS請求時如何進行個性化位置隱私保護的問題。與傳統的位置隱私保護策略不同的是，本算法考慮了位置語義對匿名效果的影響，在定義了區(qū)域敏感度、區(qū)域普及度的基礎上，給出了一種基于位置語義的匿名區(qū)隱私度度量，并以此為標準構造匿名集，使所構造的匿名集滿足用戶的個性化隱私需求。通過基于真實數據及模擬數據的大量實驗，結合與其他匿名方法進行的對比實驗，證明了本文方法的可行性及有效性。

圖7 平均區(qū)域隱私度

[1]CHEN X,PANG J. Protecting query privacy in location-based services[J]. GeoInformatica,2014,18(1): 95-133.

[2]周傲英,楊彬,金澈清,等. 基于位置的服務：架構與進展[J]. 計算機學報,2011,34(7): 1155-1171.ZHOU A Y,YANG B,JIN C Q,et al. Location-based services: architecture and progress[J]. Chinese Journal of Computers,2011,34(7):1155-1171.

[3]DUCKHAM M,KULIK L. Location privacy and location-aware computing[J]. Dynamic amp; Mobile GIS: Investigating Change in Space and Time,2006,3: 35-51.

[4]MOKBEL M F. Privacy in location-based services: state-of-the-art and research directions[C]//The 8th International Conference on Mobile Data Management (MDM’07). Mannheim,Germany,c2007:228.

[5]GRUTESER M,GRUNWALD D. Anonymous usage of location-based services through spatial and temporal cloaking[C]//The First International Conference on Mobile Systems,Applications,and Services. c2003: 31-42.

[6]MOKBEL M F,CHOW C Y,AREF W G. The new casper: Query processing for location services without compromising privacy[C]//VLDB. c2006:763-774.

[7]KALNIS P,GHINITA G,MOURATIDIS K,et al. Preventing location-based identity inference in anonymous spatial queries[J]. IEEE Transactions on Knowledge and Data Engineering,2007,19(12):1719-1733.

[8]MASCETTI S,BETTINI C,WANG X S,et al. ProvidentHider: an algorithm to preserve historical k-anonymity in LBS[C]//The 10th IEEE International Conference on Mobile Data Management. Taipei,China,c2009:172-181.

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

[10]TRAN M T,ECHIZEN I,DUONG A D. Binomial-mix-based location anonymizer system with global dummy generation to preserve user location privacy in location-based services[C]//2010 International Conference on Availability,Reliability and Security. c2010: 580-585.

[11]PAN X,XU J L,MENG X F. Protecting location privacy against location-dependent attacks in mobile services[J]. IEEE Transactions on Knowledge and Data Engineering,2012,24(8): 1506-1519.

[12]PAN X,MENG X F. Preserving location privacy without exact locations in mobile services[J]. Frontiers of Computer Science,2013,7(3):317-340.

[13]KACHORE V A,LAKSHMI J,NANDY S K. Location obfuscation for location data privacy[C]//2015 IEEE World Congress on SERVICES.c2015: 213-220.

[14]SAMARATI P,SWEEENEY L. Protecting privacy when disclosing information: k-anonymity and its enforcement through generalization and suppression[J]. International Journal on Uncertainty,Fuzziness and Knowledge-based Systems,2002,10(5): 571-588.

[15]GRUTESER M,GRUNWALD D. Anonymous usage of location-based services through spatial and temporal cloaking[C]// Proceedings of the International Conference on Mobile Systems,Applications and Services (MobiSys’03). San Francisco,USA,c2003: 163-168.

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

[17]KIDO H,YANAGISAWA Y,SATOH T. An anonymous communica-tion technique using dummies for location-based services[C]//IEEE International Conference on Pervasive Services (ICPS’05). Santorini,Breece,c2005:88-97.

[18]DUCKHAM M,KULIK L. A formal model of obfuscation and negotiation for location privacy[C]//The International Conference on Pervasive Computing. c2005:152-170.

[19]ARDAGNA C A,CREMONINI M,SAMAEATI P,et al. An obfuscation-based approach for protecting location privacy[J]. IEEE Transactions on Dependable and Secure Comput,2011,8(1): 13-27.

[20]GHINITA G,KALNIS P,KHOSHGOZARAN A,et al. Private queries in location based services: Anonymizers are not necessary[C]//The 2008 ACM SIGMOD International Conference on Management of Data. c2008:121-132.

[21]李敏,秦志光. 路網環(huán)境下位置隱私保護技術研究進展[J]. 計算機應用研究,2014,31(9): 2576-2580.LI M,QIN Z G.. Survey of location privacy protection over road networks[J]. Application Research of Computers,2014,31(9): 2576-2580.

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

[23]PALANISAMY B,LIU L. MobiMix: protecting location privacy with mix-zones over road networks[C]//The 27th IEEE International Conference on Data Engineering. c2011: 494-505.

[24]DAMIANI M L,SILVESTRI C,BERTINO E. Fine-grained cloaking of sensitive positions in location-sharing applications[C]//IEEE Pervasive Computing. 2011,10(4):64-72.

[25]YIGITOGLU E,DAMIANI M L,ABUL O,et al. Privacy-preserving sharing of sensitive semantic locations under road-network constraints[C]//MDM. c2012:186-195.

[26]潘曉,肖珍,孟小峰. 位置隱私研究綜述[J]. 計算機科學與探索,2007,1(3): 268-281.PAN X,XIAO Z,MENG X F. Survey of location privacy-preserving[J].Journal of Frontiers of Computer Science and Technology,2007,1(3):268-281.

[27]CHEN S,JENSEN C S,LIN D. A benchmark for evaluating moving object indexes[J]. PVLDB,2008,1(2): 1574-1585.

[28]http://www.comp.nus.edu.sg/～spade/benchmark[EB/OL].

[29]BRINKHOFF T. A framework for generating network based moving objects[J]. GeoInfomatica,2002,6(2):153-180.

Location-semantic-based location privacy protection for road network

CHEN Hui1,2,3,QIN Xiao-lin1,3

(1. College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 211106,China;2. School of Electronic and Information Engineering,Nanjing University of Information Science and Technology,Nanjing 210044,China;3. Jiangsu Key Laboratory of Internet of Things and Control Technology,Nanjing 211106,China)

Mobile users suffer location privacy leakage threat as enjoy location-based services (LBS). Therefore,it was important to provide effective policy for location privacy protection. Conventional protection approaches were mainly based on spatial cloaking,which leads to the anonymous effectiveness suffer great reduction if the attacker obtains more background knowledge with respect to the cloaking region,especially semantic information of the location. To prevent sensitive location information leakage for the location semantics being analyzed,and consider the characteristic that most users move on road networks,a location-semantic-based location privacy protection method for road networks was proposed. The proposed method considers users’ personalized privacy requirements well. The feasibility and effectiveness of the proposed method are verified through experiments for many scenarios.

location semantic,privacy protection,road network,sensitivity,popularity

s:The National Natural Science Foundation of China (No.61373015,No.61300052,No.41301047),The Project Funded by the Priority Academic Program Development of Jiangsu Higher Education Institutions,The Important National Science and Technology Specific Project (No.BA2013049)

TP309

A

2015-12-19；

2016-04-11

國家自然科學基金資助項目（No.61373015,No.61300052,No.41301047）；江蘇高校優(yōu)勢學科建設工程基金資助項目；江蘇省重大科技成果轉化基金資助項目（No.BA2013049）

10.11959/j.issn.1000-436x.2016157

陳慧（1981-），女，安徽蕪湖人，南京航空航天大學博士生，南京信息工程大學講師，主要研究方向為移動對象數據庫、隱私保護等。

秦小麟（1953-），男，江蘇蘇州人，南京航空航天大學教授，主要研究方向為分布式數據管理、物聯網、數據安全與隱私保護、大數據管理與分析等。