基于位置服務中時空關聯的隱私保護方案

李維皓，丁晟，孟佳潔，李暉

（西安電子科技大學網絡與信息安全學院，陜西 西安 710071）

1 引言

移動智能終端的普遍應用為用戶提供了便利的生活方式，其中基于位置服務的應用更是受到廣大用戶的喜愛，例如，美團外賣、大眾點評、微博等應用軟件。用戶可以在智能終端安裝各種基于位置服務的應用程序，這為用戶的日常生活帶來了無往不利的便捷。然而，用戶在享受LBS帶來的便利時，自身的隱私信息也在使用各類應用的過程中泄露給服務提供商，惡意用戶通過獲取發送請求的內容分析出用戶的隱私信息，例如，ID地址、工作、生活習慣甚至健康狀況。為了保證用戶在享有服務的同時，不泄露用戶個人的隱私信息，保護移動用戶的位置信息已經成為當下眾多學者們研究的課題之一。

現有的隱私保護方案主要分為2類，基于可信匿名中心的隱私保護方案[1]和基于移動終端的隱私保護方案[2～4]。利用可信匿名中心來完成用戶和服務提供商之間的交互，減少了移動終端在計算和存儲上的壓力，然而可信匿名中心成為系統性能和安全性的瓶頸，從而無法避免單點泄露的問題。當下移動終端不斷智能化，在處理能力和存儲能力都有著跨越式的提高，能夠高效、準確地完成基本的處理、計算和存儲任務，實現相應的功能，相比之下，沒有可信匿名中心的參與，基于可信匿名終端的方案有效地避免了單點泄露問題，在隱私保護方面有著更明顯的優勢。根據隱私保護方案技術的不同，主要分為位置偏移和模糊技術[5,6]、空間匿名技術[7,8]、群組協作技術[9,10]以及基于密碼學技術的隱私保護方案[11,12]。其中位置偏移和模糊技術的安全性較低、執行簡單，群組協作技術需要較高的假設前提，而密碼學技術較高的安全性需要依靠強大的計算處理能力，并且十分耗時。綜合考慮，空間匿名技術避免了較高的計算量和較低的安全性等弊端，能夠在用戶的智能終端實現較高的隱私保護，包含位置隱私和查詢隱私。相較于位置隱私，查詢隱私是通過用戶發送的查詢內容來分析、推斷，進而得到用戶潛在的隱私信息，查詢內容背后潛在的用戶隱私則被視為查詢隱私。例如，用戶查詢附近的醫院，那么該用戶很有可能是一名病患。在移動社交網絡中，用戶的查詢隱私和位置隱私都是現有隱私保護方案需要考慮、設計來實現保護的方面。

在隱私保護方案中，背景信息的存在成為攻擊者推斷用戶真實信息的一項必不可少的條件，然而有些方案并未考慮背景信息的存在[13]，或不全面地考慮背景信息[7,8]，單一考慮地圖中的歷史查詢概率，而忽略了在每個特定時間點的概率分布情況。從而為攻擊者提供了可乘之機，通過分析、推斷背景信息和發布的請求信息之間的關聯，得到隱藏在請求信息后的用戶隱私。因此，在設計隱私保護方案時，背景信息的存在是不容忽略的。

基于偽位置生成的隱私保護方案，即時空關聯的隱私保護方案，利用空間匿名技術來保護用戶的位置信息，輕量級的算法能夠成功并高效地運行在移動智能終端，從而很好地避免了可信匿名中心的存在和單點泄露問題。此方案首先利用維諾多邊形將地圖分割為若干個多邊形，進而通過用戶的移動模型來預測用戶在下一個時間段可能出現的位置，并通過該位置的POI（point of interest）來決定前一時刻的請求內容。本文創新點共分為以下3個方面。

1) 區別于現有方案，不僅考慮了背景信息的存在，同時分別考慮了在不同的時間點上每一個位置的查詢概率。

2) 考慮時空關聯性，避免了攻擊者通過分析在特定時間點發送請求的可能性以及移動用戶在特定位置發送請求的合理性來推斷用戶的隱私信息。

3) 通過分析計算數據集Geolife得到用戶在相鄰時間段可能前進的位置，預測用戶在下一個時間段可能出現的位置，從而決定前一個時間段的查詢內容。這一創新點成功地考慮了查詢內容和位置之間的可行性，提高了偽位置對攻擊者的混淆程度。

2 相關工作

本節根據是否有可信匿名中心的參與，分析、介紹現有的隱私保護方案中使用的技術以及存在的問題。

2.1 基于可信匿名中心方案

目前，在基于位置服務的隱私保護方案中，大多數的方案都需要依靠可信匿名中心的參與來完成隱私保護的全過程。k-匿名技術是最為廣泛應用的一項技術，其中將用戶真實的位置信息和k?1個虛假的用戶信息發送給移動服務提供商，在暴露給服務提供商的位置信息中保證用戶的真實位置信息和其他的虛假位置信息不可區分，從而實現對位置信息的保護[1,14]。l-多樣性[15]作為k-匿名的一種擴展，要求隱匿區域內至少包含一種隱私信息。可信匿名中心介于移動用戶和服務提供商之間，移動用戶將信息發送到可信匿名中心進行匿名處理，然后將匿名處理后的信息發送給服務提供商來換取服務信息。Beresford等[16]提出了Mixzone的概念，在Mixzone中的用戶不需要更新自己的位置信息，從而不需要和服務提供商進行交互，避免了多次交互泄露的隱私信息。Palanisamy等[17]利用Mixzone的概念，在用戶離開Mixzone時對其進行假名更換，攻擊者不能通過分析進入Mixzone和離開該區域的關聯性來獲取用戶的真實信息。Meyerowitz等[18]通過緩存用戶請求的服務信息來避免和服務提供商的多次交互，通過減少交互次數保護了用戶的隱私信息。Xu等[19]提出了一種基于感知的隱私保護模型，利用信息熵來衡量位置區域的受歡迎程度，并且利用四叉樹來分離請求信息和特定用戶，針對不同的分類提供個性化的隱私保護。

2.2 非基于匿名中心方案

隨著科技的進步，當下的移動智能終端具有強大的計算、處理能力和大容量的存儲空間。近幾年來，基于移動終端的隱私保護方案也被不斷提出[3,20,21]。相較基于匿名中心的隱私方案，此類方案的架構中不需要任何可信第三方的參與，完全避免了可信第三方潛在的安全和性能隱患。CAP[2]利用四叉樹對地圖進行細粒度的劃分，并利用Hilbert曲線對地圖進行遍歷。該方案考慮了道路的多樣性，但并未將移動用戶的運動模式考慮在內。SMILE[3]利用k-匿名技術來度量用戶的隱私程度，在基于遇見的位置服務中，通過獲取用戶位置信息前綴的散列值，從而避免了將用戶的個人信息泄露給服務提供商。Fawaz等[22]提出了一個新型的隱私保護框架，能夠針對每一個應用程序來實現細粒度的隱私保護，并且不需要依靠任何的可信第三方。

3 準備工作

為了方便后文的閱讀和理解，本節主要介紹文中所需要用到的一些基本概念、研究動機和基本解決方案。

3.1 基本概念

1) 查詢內容

移動用戶發送服務請求給服務提供商，其中主要包含用戶的身份信息、位置信息、查詢內容和時間戳。這不僅保護了用戶的位置信息，同時避免了查詢內容所導致的隱私泄露問題，即查詢隱私[23]。在現有的隱私保護方案中，將用戶的隱私主要分為位置隱私和查詢隱私。例如，用戶請求附近 1 km以內的加油站，其中加油站被視為查詢內容，查詢內容所代表的隱私稱為查詢隱私。攻擊者通過分析用戶發出的查詢內容，推斷出用戶的隱私信息，相較位置隱私，查詢隱私同樣需要保護。

2) 位置信息

移動用戶在發送請求服務時，根據服務需求，需要將用戶當前所處的位置信息發送給相關的服務提供商，以便獲取相關的服務信息。本文提到的位置信息是指在請求服務時，用戶所處的位置坐標。用戶利用智能終端中的GPS定位模塊獲取當前的位置坐標，隱私保護方案旨在保護用戶的位置信息不被泄露，從而避免非法用戶推測出用戶的真實敏感信息。

3) POI

POI指的是在某一個位置點區別于坐標信息來辨別該位置的點。例如，Alice在麥當勞請求周圍公交車站，那么麥當勞就是該位置的POI，而該位置的坐標則是位置信息，公交車站是查詢內容。

從某種程度上來講，POI和查詢內容在語義上具有重合性，例如，上述的例子中，麥當勞是該位置的POI，公交車站則是查詢內容。然而從公交車站的位置坐標來說，公交車站是該位置的POI。綜上所述，POI是位置坐標上基礎建設（或其他能夠區別辨識的設施）的語義內容，能夠作為用戶進行查詢的關鍵字，成為查詢內容。

4) 背景信息

隨著科技發展信息的海量增加，任何一個具有計算、處理和存儲功能的個體都能夠獲取到地圖中用戶所處區域的歷史查詢數據，其中包含了某個地點曾經以及當前發生的請求記錄，該地的查詢概率以及該地點所位于的商圈和 POI（Google地圖）。現有的隱私保護方案單一地考慮了背景信息中歷史數據的集合，未關注到某個特定時間點的查詢概率以及與該時間點相鄰時間點的查詢概率。本文所涉及的背景信息是通過Google地圖的API來獲取區域內每個位置的查詢概率，并將背景信息存儲于智能終端中。

3.2 研究動機

現有的隱私保護方案忽略了背景信息的存在，從而給用戶的隱私帶來的潛在威脅，即使某些方案考慮到背景信息也可能會被惡意用戶獲取來推斷用戶的隱私，但是通常都只單一地考慮某一個位置的歷史查詢概率，而忽略了在不同時間點之間、時間和空間之間存在的關聯性。通過一個簡單的例子來解釋研究動機，如圖1所示。選取地圖的一部分，其中，[0, 20]×[0, 20]是用戶的請求區域，虛線表示地圖中的道路情況，12∶00am，用戶Alice位于位置(5, 5)。基于背景信息所能提供的道路信息，與該區域連通的道路有且只有 2條，它們分別是[0,10]×[0,10]→[10,20]×[0,10]和[0,10]×[0,10]→[0,10]×[10,20]，其中第一條路通往餐館（如肯德基、麥當勞、星巴克），第二條路通往酒吧。首先，在偽位置生成的隱私保護方案中，如果選取的偽位置是一間酒吧，那么在時間戳為12∶00am的時候發送請求給服務提供商，攻擊者則可以根據在該時間酒吧不營業的原因將該偽位置過濾掉，因此，需要考慮時間和位置所代表的POI之間的可行性。其次，為了保護Alice的位置信息，將 Alice的隱身空間設置為[0,10]×[0,10]，基于用戶的心理，在用戶想要請求相應的服務時，一定是在下一個時間點或將來某個時間段要去的位置，那么在該位置發送的查詢內容一定是在時間允許情況下可達的，即用戶極有可能請求附近存在的POI。在圖1右側，用戶將要去的地方一定是他的請求區域[0, 20]×[0, 20]中，而非區域以外的位置，那么用戶的查詢內容應該存在于該查詢區域。同理，如果選取的偽位置周圍的可達范圍內只有餐館和酒吧2種POI，那么如果發送的查詢內容為醫院，則會被攻擊者判定該位置為虛假位置，即需要考慮到查詢內容和所選取位置之間的關聯性。

現有的基于偽位置生成的隱私保護方案總是根據概率分布來選取相應的偽位置，而并未考慮到在不同的時間點所選取到的偽位置并不具有足夠的說服力，即午餐時間，在酒吧發送請求的可能性遠小于在辦公室請求周邊餐館的可能性。同時，用戶請求身邊并不存在的POI也將會被攻擊者判定為虛假的位置，即午餐時間，在城南請求城北的公園的可能性很小。

3.3 基本解決方案

根據以上提出的研究動機，提出了基于偽位置生成的時空關聯的隱私保護方案，能夠更好地保護用戶的位置隱私和查詢隱私。該方案包含了2個算法，算法1是地圖分割算法，不同于現有方案中單一考慮地圖中的查詢概率，而忽略了在特定時間點不同的位置具有不同的查詢概率的情況，算法1首先從Google地圖中的popular time中獲取到在特定的時間段某一個具體位置的概率情況，然后通過在特定時段發送請求的可能性對地圖進行第一層的過濾，得到了若干個位置點。接著，基于第一層過濾后的位置點，利用維諾圖將地圖分割為若干個不規則的維諾多邊形，每一個維諾多邊形中有且只有一個離散的位置存在（維諾圖的性質）。通過選取與用戶所在的維諾多邊形共邊的維諾多邊形，保證了待選的離散位置單元能夠盡可能遠，且與用戶的位置單元不相鄰。從而過濾掉和用戶所在的維諾多邊形公共邊的位置單元，并將算法1最后得到的位置單元集作為算法2的輸入。

算法2為偽內容生成算法，其中包含選取偽位置和偽查詢內容。為了避免攻擊者分析用戶在相鄰時間段的位置可達性，通過數據集 Geolife得到轉移矩陣來推測每一個位置單元在相鄰的2個時間點之間的移動概率，通過選取概率高的位置單元所處的POI為前一時刻想要請求的查詢內容，作為偽查詢內容，結合算法1所得到的位置單元集合，尋找偽查詢位置相臨近的位置作為偽位置單元。最終，用戶將自身的真實信息和偽位置以及偽查詢內容一起發送給服務提供商來換取服務。

3.4 移動模型

利用二維坐標空間來表示地圖信息，將地圖劃分為M個大小相同的單元，即其中，。如圖2所示，單元C4的向量可表示為

X= [4 ,6]T，其中X[1] = 4,X[2 ]= 6。

圖2 二維坐標空間

根據用戶的移動模型，利用隱馬爾可夫模型[24,25]來描述用戶在時間不同時位置的關聯性。用戶將處理過的位置信息暴露給服務提供商，攻擊者通過觀測發送出的信息對用戶的真實信息進行推斷。

在時間點t，利用向量tP來表示用戶位置的概率分布，其中，表示向量Pt中的第i個元素，Ci∈Map。通過轉移矩陣MA來定義用戶從一個位置移動到另一個位置概率，在矩陣MA中存在元素maij，其中，i表示矩陣中的第i行，j表示矩陣中的第j列。

已知t?1時刻用戶的位置向量Pt?1，從而通過轉移矩陣可得知t時刻用戶的位置向量Pt，Pt=Pt?1MA。假設當前地圖上存在5名移動用戶，如圖2所示，分別位于地圖中的{C2,C4,C6,C8,C9}，則可以得到以下的概率向量。

Pt=[00.2 0 0.2 0 0.2 0 0.2 0.2 …0]

為了更好、更準確地獲取轉移矩陣MA，有研究者對用戶在不同時間點的具體位置信息進行了采集[26,27]，利用數據集Geolife[22]中的位置信息，計算出轉移矩陣MA。在數據集Geolife中，研究者收集了 182名用戶在北京三環內、每隔 1～60 s所處的位置信息，其中每一個位置信息包含了經、緯度和當前的時間戳，歷時3年。通過該數據庫所提供的位置信息Pt?1和Pt，通過Pt=Pt?1MA可進一步推算出矩陣，即轉移矩陣MA默認為已知的。

根據隱馬爾可夫模型，用戶的每一個狀態取決于前面的有限狀態，即用戶在t時刻的位置取決于t?1時刻的位置信息。利用這一特性，通過轉移矩陣獲知用戶下一時刻可能出現的位置，并將該位置的 POI作為當前時刻的查詢內容。其中，轉移矩陣MA的獲取是通過現有數據庫的訓練學習后得到的矩陣，能夠利用該矩陣推測得到用戶下一時刻的位置信息。

3.5 隱私度量

現有很多隱私保護方案采用不同的數學工具來衡量位置隱私的程度[4,7,8]，其中信息熵是最為廣泛運用的一種隱私度量。利用信息熵作為隱私度量，具體定義如下。

定義1 已知位置j，則信息熵為

其中，指的是在時刻t，用戶在位置j處請求POIi時的條件概率。

因為信息熵的計算并不需要過高的計算能力，現有的智能終端能夠承載信息熵的計算，從而不需要和可信第三方或其他的用戶終端進行交互，避免了額外的風險。該隱私度量選取的位置概率不同于現有方案單一地考慮用戶在傳統的背景信息下的查詢概率，而是針對某一個特定的時間戳，位置j請求查詢內容為i，其中i表示某一種特定的POI。

4 時空關聯隱私保護方案

本節詳細介紹了時空關聯隱私保護方案所包含的算法，即地圖分割算法和偽內容生成算法，系統結構如圖3所示。圖3中，用戶通過移動終端向GPS獲取位置信息，作為算法的輸入，然后在移動終端中對地圖進行分割，通過維諾多邊形篩選出不相鄰的位置區域，在偽內容生成算法中通過概率和轉移矩陣構造偽位置請求，并通過移動終端發送給LBS服務提供商。

在用戶使用LBS的相關服務時，在不同的需求和客觀條件下，為用戶選取最佳的匿名數目k，例如，在Wi-Fi條件允許的條件下，可以選取較大的k值，而在移動數據流量時則選取較小的k值。

圖3 系統結構

4.1 地圖分割算法

在該算法中，首先需要將地圖劃分為M個位置單元，用戶位于其中某一個位置單元。在t時刻，用戶請求身邊1 km以內的POI，如圖4(a)所示，將地圖等分為8×8個區域，即M=64，每一個區域代表一個位置單元，即Map={C1,C2,… ,C64}。在圖4(a)中，每個單元中不同的灰度代表在t時刻該位置單元的查詢概率，用表示。用戶Alice位于單元C中，該單元在t時刻的查詢概率為。在t

22時刻Ci的查詢概率滿足，其中δ為閾值，并且滿足δ＞0。將選取出來的位置單元存儲在集合α中，該集合中的元素包含了符合要求的位置單元，即α={C3,C5,C15,C22,C24,C25,C36,C41,C43,C46,C56,C58,C61}。在圖4(b)中，選取出來的位置單元用度較高的位置單元表示。

圖4 地圖分割

維諾多邊形對地圖劃分的算法采取 plane sweep，因該算法成熟且不是重點，在此并不贅述，該算法的時間復雜度分析見第5節。

根據集合α中的位置單元構造維諾多邊形，其中每2個相鄰的位置單元連線的中垂線構成了|α|個維諾多邊形，并且每一個多邊形中有且僅有唯一一個離散的位置單元。根據維諾多邊形的性質，已知一個維諾多邊形Vi，與Vi共享一條邊的維諾多邊形則是距離Vi最近的維諾多邊形，那么該多邊形內的點則是距離Vi內的離散點最近的點。在圖4(b)中，用戶Alice所位于的維諾多邊形具有5條邊，那么共用這5條邊的維諾多邊形其中的位置單元則是和Alice鄰近的區域。從集合α中過濾掉這5個相鄰的多邊形，剩余的位置單元構成集合α′，即|||'|5α?α= 。

算法1 地圖分割算法

輸入 位置信息，地圖信息

輸出α′

1) 等分地圖；

2) 選取滿足的區域；

3) 存儲于集合α中；

4) 構造維諾多邊形；

5) 獲知真實用戶所在的維諾多邊形；

6) 刪除具有相鄰邊的維諾多邊形；

7) 篩選過的維諾多邊形存儲于α中；

8)α′作為下一算法的輸入。

4.2 偽內容生成算法

在該算法中，偽內容主要包含了偽查詢內容和偽位置選取，在地圖分割算法中得到的集合α′的基礎上，偽內容算法需要選取合適的偽位置和偽查詢內容。根據 3.4節，集合α′中有元 素 {C3,C22,C25,C41,C43,C56,C58,C61}，則得到 概率向量其中分別在集合α′中有元素所在的位置定值為，即。已知轉移矩陣MA和概率向量Pt，則通過Pt+1=PtMA得到t+1時刻的概率向量。通過得到的t+1時刻的概率向量Pt+1可以得知集合α′中的位置單元可能去的位置，這些位置所對應的POI相當于在t時刻想要請求的查詢內容。

在該算法的例子中，假設k=4，需要挑k?1個位置單元，即3個位置單元作為偽位置發送給服務提供商。根據概率向量Pt+1中每個位置單元的訪問可能性，從大到小降序選取3個位置單元存儲于集合β={Ca,Cb,Cc}。與地圖對照，得到集合β中每一個位置單元所對應的POI以及和集合α'最鄰近的位置單元分別構成偽查詢內容POIa、POIb、POIc和偽位置Ca′ 、Cb′、Cc′ 。

最后，用戶Alice將自身的位置Ci和查詢內容POIi構成二元組[Ci,POIi]，同樣得到偽位置請求[Ca,POIa]、[Cb,POIb]、[Cc,POIc]。最后通過移動智能終端將這4個二元組和相關信息構造成請求信息，繼而發送給服務提供商來獲取相關的服務信息。

算法2 偽內容生成算法

輸入α′，MA，k

輸出k個查詢請求

1) 已知用戶的位置；

2) 當前時間為t?1；

3) 通過得到tP；

4) 選取k?1個概率向量；

5) 存儲于集合β中；

6) 降序排列β中元素；

7) 對應得到相應的POI；

8) 構造請求；

9) 發送k個請求給LBS服務器。

5 實驗驗證

本節分別從性能驗證以及隱私驗證對所提方案的性能和安全性進行測試和驗證。實驗利用Matlab在PC機（2.9 GHz 英特爾i7 CPU，8 GB內存）上進行模擬仿真并對方案的性能進行實驗驗證。

選取北京三環內 8 km×8 km的地圖，劃分為160×160個位置單元，每個位置單元的大小為50×50的矩形。實驗中參數k指的是k-匿名中發送給服務提供商的請求數量，選取范圍為[3,20]。參數δ是地圖分割算法中的閾值。

5.1 性能驗證

1) 位置單元的數量與集合α/執行時間的關系

在地圖分割算法中，需要對地圖中的位置單元進行過濾，從而所劃分的位置單元越多執行算法所消耗的時間也就越多；隨著地圖中位置單元的數量增加，在構造維諾多邊形時需要計算的離散點也就逐漸增加，故而最終得到的集合α的大小也隨著地圖劃分的粒度逐漸增加，具體結果如圖5所示，在該實驗中選取參數k=5。在地圖劃分算法中，避免用戶參與過多復雜的過程，為了實現最簡便的操作、最合理的隱私保護力度，地圖的粒度由系統根據用戶所需要的k值的大小自動地匹配出相應的粒度。其中用戶所需要的k值和用戶所處的Wi-Fi環境相關，由系統自動選取，不需要用戶參與，大大簡化了操作，方便了用戶。

圖5 隨位置單元的數量不同，α與執行時間的變化情況

2) 參數δ與通信開銷/執行時間的關系

方案利用的是偽位置生成算法，發送給服務提供商的請求信息的條數取決于參數k的值，隨著參數δ的變化，所發送給服務提供商的信息條數是不變的，通信開銷不隨δ的變化而變化。在算法的執行時間中，參數δ的值越大，則對應集合α中的元素就越多，從而在偽位置生成算法中的計算元素則越多，故而隨著δ的增加，算法的執行時間不斷增加，具體變化如圖6所示。

圖6 隨δ不同，通信開銷和執行時間的變化情況

3) 時間與α/執行時間的關系

考慮時間和空間的關系，在現實生活中，從0∶00開始一直到 24∶00，移動用戶的運動模式不同，從而在不同的時間段有明顯的概率分布，根據數據集中不同時間對應的峰值和低谷決定數據集α的大小，如圖7(a)所示。然而對于執行時間則沒有明確的變化，因為地圖的位置單元數目一定，δ越大則執行時間會增加，而在不同時間點的執行時間并不會有明顯的變化，如圖7所示。

圖7 隨時間不同，α和執行時間的變化情況

4) 構造維諾多邊形的算法復雜度

構造維諾多邊形的方法分為定義法（intersect of halfplanes）、增量（incremental）算法、分治法、plane sweep算法。采用的是plane sweep的方法，該方法在構造維多諾多邊形可以歸約為n個實數的排序問題，則實現該算法的時間計算復雜度為O(nlogn)，同時該算法在現有的4種算法中具有最優的完成效果。

5.2 隱私驗證

通過比較所提隱私保護方案和現有的偽位置生成算法隱私保護方案根據參數k的變化引起泄露概率的變化，為了保證可比性，選取同時保護位置隱私和查詢隱私相類似的隱私保護方案，故而比較了Dummy-Q[28]和TTcloak[29]2個方案，其中最優方案是在理論上的最優值。該方案發送給服務提供商的信息中每一個位置都會有不同的查詢內容，圖 8比較了泄露概率隨著參數k的變化趨勢，隨著參數k的增加泄露概率逐漸降低，因為暴露越多的請求，導致攻擊者越難分析出真實的信息。圖9比較了最優方案和隨機方案的隱私度量，因為隱私度量涉及參數，并未有其他方案涉及該查詢概率，故這2個方案的隱私度量不會隨k的變化而變化。在 TTcloak[29]方案中，為了選取相互不相鄰的偽位置，將隱身區域劃分為4等份，進而在每個等分的區域選取偽位置。當k的取值過大時，在等分線附近容易出現偽位置過于接近的情況。該方案利用維諾多邊形對地圖進行劃分，利用維諾多邊形的性質避免了鄰近位置的選取，不會出現選取的位置處于鄰近區域的情況。

圖8 泄露概率隨參數k的變化趨勢

圖9 隱私度量隨參數k的變化趨勢

6 結束語

在基于位置服務中，提出了一種時空關聯的隱私保護方案，包含了2個算法，即地圖分割算法和偽內容生成算法。地圖分割算法利用維諾圖將地圖劃分為多個維諾多邊形，并且每一個多邊形中有且僅有一個離散點，偽內容生成算法利用移動模型預測用戶在相鄰時間點中將要去的位置來選擇前一個時間的查詢內容，從而有效地避免了時空關聯可能會導致的隱私泄露問題，同時保護了用戶的位置隱私和查詢隱私。最后，本文通過詳細的性能和安全性實驗驗證了所提方案的有效性和安全性。

[1] GEDIK B, LIU L. Protecting location privacy with personalizedk-anonymity∶ architecture and algorithms[J]. IEEE Transactions on Mobile Computing, 2008, 7(1)∶ 1-18.

[2] PINGLY A, YU W, ZHANG N, FU X, et al. Cap∶ a context-aware privacy protection system for location-based services[C]// ICDCS.2009∶ 49-57.

[3] LI X, ZHANG C, JUNG T, QIAN J, et al. Graph-based privacy-preserving data publication[C]//INFOCOM.2016.

[4] CHEN Z, HU X, JU X, et al. Lisa∶ location information scrambler for privacy protection on smartphones[C]//CNS. 2013.

[5] ANDRES M, BORDENABE N, CHATZIKOKOLAKIS K, et al.Geo-indistinguishability∶ differential privacy for location-based systems[C]// CCS. 2013.

[6] PERAZZO P, DINI G. A uniformity-based approach to location privacy[J]. Computer Communications, 2015, 64(1)∶ 21-32.

[7] NIU B, LI Q, ZHU X, et al. Achievingk-anonymity in privacy-aware location-based services[C]// INFOCOM.2014.

[8] NIU B, LI Q, ZHU X, et al. Enhancing privacy through caching in location-based services[C]// INFOCOM. 2015.

[9] SHOKRI R, THEODORAKOPOULOS G, PAPADIMITRATIS P, et al.Hiding in the mobile crowd∶ Location privacy through collaboration[J].IEEE Transactions on Dependable and Secure Computing, 2014, 11(3)∶266-279.

[10] 黃毅, 霍崢, 孟小峰. CoPrivacy∶ 一種用戶協作無匿名區域的位置隱私保護方法[J]. 計算機學報, 2011, 34(10)∶ 1976-1985.HUANG Y, HUO Z, MENG X F. CoPrivacy∶ a collaborative location privacy-preserving method without cloaking region[J].Chinese Journal of Comuputers, 2011, 34(10)∶ 1976-1985.

[11] YI X, PAULET R, BERTINO E, et al. Practical approximateKnearest neighbor queries with location and query privacy[J]. IEEE Transactions on Knowledge and Data Engineering, 2016, PP (99)∶ 1-14.

[12] PAULET R, KAOSAR M, YI X, et al. Privacy-preserving and content-protecting location based queries[J]. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(5)∶ 1200-1210.

[13] CHOW C, MOKBEL M, LIU X. Spatial cloaking for anonymous location-based services in mobile peer-to-peer environments[J].GeoInformatica, 2011, 15(2)∶ 351-380.

[14] MOKEL M, CHOW C, AREF W. The new casper∶ query processing for location services without compromising privacy[J]. The IEEE VLDB Journal 2006.

[15] ZHANG X, XIA Y, BAE H. A novel location privacy preservation method for moving object[J]. International Journal of Security and Its Applications, 2015, 9(2)∶ 1-12.

[16] BERESFORD A, STAJANO F. Location privacy in pervasive computing[J]. IEEE Pervasive Computing, 2003, 2(1)∶46-55.

[17] PALANISAMY B, LIU L, Attack-resilient mix-zones over road networks∶ architecture and algorithms[J]. IEEE Transactions on Mobile Computing, 2015, 14(3)∶ 495-508.

[18] MEYEROWITZ J, CHOUDHURY R. Hiding stars with fireworks∶location privacy through camouflage[C]//MobiCom.2009.

[19] XU T, CAI T. Feeling-based location privacy protection for location-based services[C]//CCS. 2009.

[20] MONTAZERI Z, HOUMANSADR A, PISHRO H. Achieving perfect location privacy in wireless devices using anonymization[J]. IEEE Transactions on Information Forensics and Security, 2017,PP (99)∶ 1.

[21] WANG X, PANDE A, ZHU J, et al. Stamp∶ enabling privacy-preserving location proofs for mobile users[J]. IEEE/ACM Transactions on Networking, 2016,24(6)∶3276-3289.

[22] FAWAZ K, SHIN K. Location privacy protection for smartphone users[C]//CCS. 2014.

[23] SHOKRI R, THEODORAKOPOULOS G, TRONCOSO C, et al.Protecting location privacy∶ optimal strategy against localization attacks[C]//CCS. 2012.

[24] GOTE M, NATH S, GEHRKE J. Maskit∶ privately releasing user context streams for personalized mobile applications[C]//SIGMOD. 2012.

[25] SHOKRI R, THEODORAKOPOULOS G, BOUDEC J, et al. Hubaux.Quantifying location privacy[C]//SP. 2011.

[26] ZHENG Y, XIE X, MA W. Geolife∶ a collaborative social networking service among user, location and trajectory[C]//Data Eng. Bull.2010.

[27] CHO E, MYERS S, LESKOVEC J. Friendship and mobility∶ user movement in location-based social networks[C]//KDD. 2011.

[28] PINGLEY A, ZHANG N, FU X, et al. Protection of query privacy for continuous location based services[C]// INFOCOM.2011.

[29] NIU B, ZHU X, LI W, et al. A personalized two-tier cloaking scheme for privacy aware location-based services[C]//ICNC.2015.