基于區間區域的位置隱私保護方法

宋國超，初廣輝，武紹欣

山東科技大學 計算機科學與工程學院，山東 青島266590

1 引言

目前，基于個人消費者需求的智能化，LBS（Location Based Services）[1-2]將伴隨無線通信技術和GPS 技術（Global Positioning System）的發展，需求呈大幅度增長趨勢。用戶通過提供位置服務的APP 連接無線通信可以隨時隨地定位自己的位置來獲取相應的服務[3-4]。例如，出行時獲取的導航服務（高德地圖），查找娛樂餐飲場所的生活服務（百度糯米），以及查找附近的人的社交服務（微信）等。據報告顯示[5]，全球LBS（Location Based Service）和RTLS（Real-Time Location Systems）市場規模預計將從2015 年的113.6 億美元增長到2020 年的549.5 億美元，CAGR（Compound Annual Growth Rate）為37.1%。

具體來說，用戶實時請求LBS 服務時，將自己的精確位置和查詢請求發送給LSP（Location Service Providers），LSP將查詢到的符合用戶需求的結果返回給用戶。盡管LSP能夠提供各種位置感知的優質服務，但是LSP可能會為了自己的利益泄露用戶的信息給其他不法分子，威脅用戶的人身和財產安全[6-7]。LBS服務存在著很大的安全隱患，而用戶對位置服務的使用規模還在不斷地增長，所以位置隱私的安全問題成為一個巨大的挑戰[8-10]。

目前，一種被廣泛采用的位置保護機制是k -匿名[11-13]。該機制采用集中式系統架構，借助匿名服務器選取k-1 個其余位置，連同用戶位置一同發送給LBS服務器，保證用戶真實位置被識別出來的概率為1/k。

在實際方案中，匿名服務器需要查詢歷史請求記錄構建候選匿名位置集。這樣保證了選取的位置的合理性。然而，現有的大多數研究工作沒有考慮到檢索龐大的歷史記錄帶來的時間開銷問題。并且，隨著用戶請求位置服務數目的增加，檢索歷史記錄中的數據會越來越耗時，影響匿名保護效果，降低了位置服務的即時優越性。

幸運的是，本文構建區間區域，將其進行Geohash編碼[14]，這樣做既考慮了選取位置的相似性，又借助編碼檢索避免了時間滯后性，加快檢索速度，給用戶提供更加快速安全的位置服務。另外，本文還考慮了用戶的隱私需求，為用戶提供了個性化的隱私保護的位置服務。借助Geohash編碼生成候選匿名位置集，如果候選匿名位置集中的位置點個數不滿足用戶要求的隱私保護程度k 值時，采用虛假位置生成技術。而且在生成虛假位置時，均勻地將區間區域分成k 份，在每一塊區間區域內進行隨機選擇。這樣既保證了生成虛假位置的均勻分布，又增加了攻擊者識別出真實用戶的難度，很好地保護了用戶的位置隱私。如果候選匿名位置集中的位置點個數大于k 值，使用位置篩選算法來選取k 個位置點，該算法加快了選取位置點的速度，減少了時間開銷。

本文的貢獻總結如下：

（1）本文借助Geohash 編碼原理，提出了基于區間區域用來構建候選匿名位置集，采用了集中式服務架構實現個性化k-匿名模型來進行位置隱私保護。

（2）本文提出了全覆蓋的虛假位置生成算法來解決候選匿名位置集中的位置點個數不滿足用戶的隱私保護需求k 值。這里，全覆蓋意味著將用戶所在的區間區域劃分為k-1 等份，在每一個劃分的子區域內隨機選擇一個位置，而且選擇與道路最近的交叉點來避開不合理的位置（河流、湖泊等），保證了選取的位置覆蓋了整個區間區域。

（3）當候選匿名位置集超過k 值，采用位置篩選算法來選取位置點構成匿名位置集發送給LSP。

2 相關工作

本章介紹了空間隱身技術和Geohash 編碼應用的相關工作。

2.1 空間隱身技術

空間隱身技術[15]通過擴大空間區域來降低用戶的真實位置精度。最具影響力的技術是位置k -匿名，使用區域內其他k-1 個位置來隱藏用戶真實位置。

Gruteser和Grunwald[16]提出了一種自適應的空間隱身算法來實現位置k -匿名，該算法利用四叉樹進行時空隱身。但是，這種方法有幾個假設，比如它對所有請求都設定相同的k 值，這在實際中是不現實的，因為大多數用戶在不同的情景下會有不同的隱私需求。

為了解決以上缺陷，Mokbel等人[17]提出了具有代表性的基于Casper 模型的空間隱身方法。該模型通過傳輸用戶定義的k 值來提供用戶對位置隱私的偏好。并通過四叉樹將空間劃分為H 層，每一層都保留了整個空間結構的信息，有效地提高了匿名性能。然而該模型需要過多的協作、可信的用戶，因此在用戶較少的區域，由于缺少足夠的虛擬位置而導致匿名區域的構建失敗成為一個主要缺陷。

為了解決用戶較少區域的位置隱私問題，Ni等人[18]提出了一種在稀疏區域內構造匿名區域的K-SDCA 算法。該算法通過選擇歷史查詢概率高、地理分布相對均勻、匿名服務器請求內容差異較大的虛擬用戶來實現k-匿名，具有較高的安全性和較高的效率。但是，該方法不考慮檢索歷史查詢記錄的開銷。因此，該算法耗時較長，影響了LBS的服務質量。

文獻[19]提出了兩個生成虛假位置的規則：（1）每個虛假位置的查詢頻率應與用戶真實位置的查詢頻率相似；（2）在這些位置的查詢頻率保持不變的前提下，這些位置應盡可能地分散。然而，由于算法的過程發生在移動客戶端上，計算量相對較大，并且對移動客戶端的計算能力和存儲空間要求很高。

文獻[20]考慮到查詢概率和匿名區域的面積，將位置隱私泄露問題表示成多目標優化問題，運用低復雜度的虛假位置選擇方案生成k-1 個虛假位置實現k -匿名。雖然該方法降低了某些位置點被過濾掉的可能性，但由于算法的過程發生在移動客戶端上，計算開銷大。

文獻[21]提出了基于聚類的k-匿名位置隱私算法來消除異常值，構造匿名集保護用戶位置。該算法平衡了隱私保護安全性與位置服務查詢質量之間的沖突。然而，由于聚類算法的迭代過程，時間開銷沒有得到優化。

SpaceTwist[22]是經典的不借助第三方匿名服務器的位置隱私保護算法，它使用錨來代替用戶的真實位置。此外，用戶可以根據他們的位置信息獲得準確的結果。雖然該算法實現了保護位置隱私，但隱私保護水平不高。

文獻[23]提出了一種基于映射的位置隱私信息檢索技術稱為MaPIR，該技術使用位置降維函數將用戶真實位置映射到地理空間內生成冗余位置，保護用戶隱私信息。根據地球赤道周長40 400 km，位置上的每個有效數字代表相應的距離范圍，從而將位置的經緯度映射成了一維的數字，實現了位置降維。該技術可以提高檢索速度，但是卻不能提供個性化的位置隱私保護。

而本文借助以二分法原理為核心的Geohash 編碼技術，可以快速檢索歷史請求記錄數據庫。同時，運用虛假位置生成算法和位置篩選算法為用戶提供快速的自主的個性化的位置隱私保護。

2.2 Geohash編碼應用

Geohash編碼是將二維的經緯度坐標點轉換為一維的字符串，某一個字符串表示了某一個矩形區域。也就是說在這個矩形區域中的所有經緯度點都共享一套編碼也就是字符串。

Liu 等人[24]提出了地理哈希方法，用于構建GIS（Geographical Information System）領域分布式內存的分布式空間索引。該技術提高了空間數據的讀寫性能，為高性能地理空間計算提供了堅實的技術基礎。

Li等人[25]提出了一種基于NoSQL 數據庫系統的位置感知WBAN數據監測系統，該系統基于Geohash空間索引，能夠高效地處理基于位置的醫療信號監測查詢。這種新穎的數據分析方法有利于促進醫療分析服務的快速發展。

Guo等人[26]提出了自適應Hilbert-Geohash編碼方法叫做AHG 地理網格系統。AHG 通過網格劃分層次結構，可以直接表示被編碼對象的位置和近似大小以及相應的編碼長度。該方法除了具有加速空間查詢的能力外，還具有良好的穩定性和可擴展性，已成功地應用于高性能地理信息系統HiGIS中的多個空間查詢工具中。

由于Geohash編碼技術通過將地理坐標編碼，可以進行快速的空間近鄰點檢索功能，避免了復雜空間計算的時間開銷，能夠加快檢索速度，常常被運用于地理空間數據檢索領域內。另外，通過編碼將用戶精準位置映射到空間區域中，可以有效地保護用戶的位置隱私信息，非常實用。所以，采用Geohash 編碼技術既可以減少時間開銷，又可以提供安全的位置服務。

目前，提出的位置隱私保護方案都各有特點，為了抵御攻擊者的背景攻擊，通常借助匿名服務器檢索歷史請求記錄來構造虛假位置實現k -匿名機制，雖然這種策略取得了很好的匿名保護效果，但是大多數策略忽略了檢索歷史數據帶來的時間開銷，從而導致提供位置服務的速度變慢，影響了用戶的體驗度。

針對這樣的問題，本文結合Geohash 編碼的便捷性，提出了一種能夠快速檢索的位置隱私保護方案，該方案將用戶真實位置泛化到區間區域內，對區間區域坐標轉換成漢明碼。通過對漢明碼進行檢索比較，篩選出相同編碼的候選匿名位置集。為了給用戶提供私人定制的匿名保護，對候選匿名位置集中的位置根據k 值進行不同的處理，提交滿足用戶要求的匿名位置集。仿真實驗證明，本文方法不但能夠加快匿名處理時間，而且還可以給用戶提供個性化的隱私保護，更加符合實際情景，具有很大的應用前景。

3 預備知識

本章描述了相關定義和系統架構。

3.1 相關定義

首先，介紹位置k-匿名的概念。

定義1（位置k -匿名[16]）位置k 匿名，將用戶位置與其他k-1 個無法區分的位置發送給LSP，使得用戶真實位置被識別成功的概率低于1/k 。這個概念是由Gruteser等人提出的。這里，k 代表了隱私要求，由用戶定義。

本文中，用戶發送的位置查詢信息定義如下。

定義2（位置請求信息LQU） 位置查詢信息是由用戶發送的，用來請求位置服務的信息。它是一個四元組LQU＜Uid,Uloc,T,QC ＞，分別代表用戶ID，用戶位置，當前查詢時間和查詢內容。這里的Uloc是個二元組＜lat,lng ＞，分別表示用戶位置的經度和緯度。

匿名服務器對用戶真實位置Uloc進行保護，構造匿名位置集代替位置查詢信息LQU發送給LBP。匿名位置集定義如下。

定義3（匿名位置集AS） 匿名位置集是由k 個位置構成的集合，包含用戶真實位置和其余k-1 個由匿名服務器產生的位置。它是一個多元組，經過匿名服務器匿名處理構造AS,LQU變成了匿名請求AQU＜Uid,AS,T,QC ＞發送給LSP來請求服務。

為了保護位置隱私信息，將一個位置坐標擴展成區間區域，利用區域內的歷史請求位置信息來進行保護。具體地，區間區域定義如下。

定義4（區間區域）將位置的經緯度坐標分別映射到一個區間范圍所表示的區域稱為區間區域。

如圖1 所示，假設一用戶位置經緯度坐標為（50，30），其紅線部分為區間區域為（[40，57]，[23，40]），其中50屬于區間[40，57]，該區間稱為經度區間，30屬于區間[23，40]，該區間稱為緯度區間。

圖1 區間區域例子

根據地球投影坐標系原理，將地球上的任意一點都能使用經緯度來表示。由于地球的橢球形狀的特點，不同地區的經緯度變化所覆蓋的區域大小也不盡然相同。而且，據計算，1 緯度大約能表示111 km 的距離。為了減少通信開銷，本文中，區間的變化范圍不會超過1。

將用戶發送請求時的精準位置映射到區間區域之后，利用Geohash 編碼來檢索區域內的歷史查詢位置，現將Geohash編碼定義如下。

定義5（Geohash編碼）Geohash編碼是將二維的經緯度坐標轉換成一維的字符串的過程。該字符串稱為geohash 碼，表示某一個矩形區域。也就是說在某個矩形區域內，所有的二維經緯度坐標共享相同的編碼。

將位置坐標進行編碼之后，會按照反向檢索的方式來查找相近的位置。

定義6（反向檢索[24]）反向檢索是，根據某用戶的geohash 碼，查找第三方的歷史查詢記錄，找出與之相同編碼對應位置的過程。

如圖2 所示，用戶所在的區間區域的geohash 編碼為“wtw3v”，反向檢索數據庫，對應的第一個和最后一個的位置編碼是完全相同的。

圖2 反向檢索例子

3.2 系統架構

本文采用了中心式系統架構。該架構包含的部件有位置請求用戶、可信的匿名服務器[22]和位置服務提供商，如圖3所示。請求過程為：

（1）需要進行位置請求的用戶通過移動終端來發送位置請求信息給匿名服務器。

（2）匿名服務器將信息通過匿名算法變成匿名請求信息。

（3）匿名服務器將匿名請求信息發送給位置服務提供商。

（4）位置服務提供商根據發送來的請求信息通過查詢位置數據庫返回查詢結果給匿名服務器。

（5）匿名服務器將結果進行過濾處理。

（6）匿名服務器將過濾結果返回給用戶。

其中，起到保護用戶位置隱私的關鍵部件是可信的匿名服務器，其功能為：

（1）能夠快速響應位置查詢請求，減輕移動用戶端的計算開銷，提高服務質量。

（2）通過匿名算法構造隱身區域保護用戶隱私，避免隱私泄露。

圖3 系統架構圖

（3）過濾LBS返回的查詢結果，減少通信開銷。

4 算法設計

本章詳細描述了算法的實現過程。本文算法實現需要借助可信的匿名服務器。

4.1 位置泛化階段

用戶發送請求位置服務時，會將自己的精準位置發送給匿名服務器。根據區間區域的原則，匿名服務器首先將用戶的經緯度位置泛化到區間區域內。借助隨機數，隨機產生4 個0 到0.025 隨機數，將用戶位置的經度和緯度分別減去和加上任意一個隨機數，最終構成用戶區間區域。例如：假設用戶位置為(lat,lng)，四個隨機數分別為r1,r2,r3,r4，那么用戶區間區域為([lat-r3,lat+r1],[lng-r4,lng+r2])。

對于位置泛化，需要說明以下三點：

（1）產生隨機數的范圍設定在0到0.025的原因是，地理位置1 緯度大約對應111 km 的距離，0.025 大約對應2.5 km，對于最大范圍是經緯度前后波動各0.025°，則表示的區域范圍大約是：（0.05/0.025）×2.5 km×（0.05/0.025）×2.5 km=25 km2，相當于250個100平的房子占地面積的大小，這個范圍也是相當客觀的。

（2）隨機產生四個隨機數，是為了防止攻擊者預測出用戶的精準位置，對用戶精準位置進行了保護。若設置一個隨機數，經度和緯度分別向前，向后波動，根據其區間的對稱性，該波動的幅度很容易推算出來，從而用戶的經緯度坐標也就暴露了。同樣地，如果設置兩個隨機數，經緯度根據同樣的方法也是可以推算出來的，所以這里會隨機產生4個隨機數，成功地避開了區間對稱的特性，使得用戶的位置不容易被預測出來。

（3）通常，隨機數的產生是服從正態分布，也就是說產生的數值大部分是在0.012 5 左右波動的，接近0 和0.025 的隨機數占的比例較少。按照數值平均波動0.012 5來計算，則區間區域的平均大小為：（0.025/0.025）×2.5 km×（0.025/0.025）×2.5 km=6.25 km2。

4.2 Geohash編碼階段

用戶的區間區域確定了之后，計算該區域的Geohash編碼。下面是其編碼生成的偽代碼。

算法1 Geohash 編碼算法（Geohash coding algorithm）

輸入：區間區域([lat1,lat2],[lng1,lng2])

輸出：geohash 編碼，geohash 碼長度

1. lat range=[-90,90],lng range=[-180,180]；

2. geohash=φ,code=φ；

3. lat mid=sum(lat range)/2；

4. lng mid=sum(lng range)/2；

5. While TRUE

6. if lng1 ＜=lng mid and lng2 ＜=lng mid //經度

7. code ←code ∪{0}；

8. lng range[1]=lng mid；

9. else if lng1 ＞lng mid and lng2 ＞lng mid

10. code ←code ∪{1}；

11. lng range[0]=lng mid；

12. else break

13. end if

14. if lat1 ＜=lat mid and lat2 ＜=lat mid //緯度

15. code ←code ∪{0}；

16. lat range[1]=lat mid；

17. else if lat1 ＞lat mid and lat2 ＞lat mid

18. code ←code ∪{1}；

19. lat range[0]=lat mid；

20. else break

21. end if

22. End While

23. 根據表1 中base32 映射表，將code 中的0，1 編碼成geohash；

24. Return geohash,geohash 碼的長度

Geohash 編碼算法首先按照Geohash 編碼的原則，對區間區域進行編碼。一旦區間區域表示的范圍不被劃分區間完全覆蓋時，跳出編碼過程。這樣做的原因有兩個：（1）位置數據是浮點數類型，一般保留小數點后5到7 位的精度；（2）預處理階段得到的區間區域本身就是一個數值范圍，并且數值波動小，最大的上下浮動也只是0.05，在迭代的過程中限制的精度。滿足這兩個條件，區間區域的編碼自身便有精度的限制，不需要用戶去自定義設定，而且，編碼產生的長度不會過長，也不會過短，避免區域過大或過小。

另外，返回geohash 碼的長度是為了進行下一階段位置檢索，用來保護用戶的位置隱私。

4.3 反向檢索位置階段

用戶真實位置進行了Geohash編碼之后，反向檢索位置首先根據真實用戶geohash 碼長度，對第三方歷史記錄中的單個位置經緯度進行相同精度的Geohash 編碼。然后進行檢索，選出與之相同編碼的位置，并進行去重操作，即重復的位置、將與用戶真實位置相同的位置刪除掉，最后統計位置個數，并與用戶指定的k 值進行比較，若與k 值相同，則將其位置點構成匿名位置集AS，發送給LSP；若小于k 值，則執行4.4節虛假位置生成階段；若大于k 值，則執行4.5 節位置篩選階段，篩選合理的k 個位置，滿足用戶隱私需求。

4.4 虛假位置生成階段

通過Geohash 編碼檢索出來的位置點個數小于用戶隱私需求k 值時，采用虛假位置生成算法，生成k 個位置進行位置隱私保護。虛假位置生成算法的主要思路是在用戶區間區域內均勻地生成k 個位置，其偽代碼如下。

算法2 虛假位置生成算法（Dummy locations generating algorithm）

輸入：用戶區間區域([lat1,lat2],[lng1,lng2])，隱私需求k，用戶真實位置Uloc(lat,lng)

輸出：匿名位置集AS

1. D1=(lat2-lat1)；

2. D2=(lng2-lng1)；

3. Dmax=max(D1,D2)；

4. d1=lat1,d2=ln g1；

5. AS=φ

6. if k%2==0

7. if Dmax==D1

8. for m=0 to k-1 do

9. Lat=random(d1,d1+(D1/(k-1)))；

//從區間(d1,d1+(D1/(k-1)))任選一數賦值給Lat

10. Lng=random(lng1,lng2)；

//從區間(lng1,lng2)任選一數賦值給Lng

11. AS ←AS ∪{(Lat,Lng)}；

12. Lat=d1+(D1/(k-1))；

13. end for

14. else

15. for m=0 to k-1 do

16. Lat=random(lat1,lat2)；

17. Lng=random(d2,d2+(D2/(k-1)))；

18. AS ←AS ∪{(Lat,Lng)}；

19. d2=d2+(D2/(k-1))；

20. end for

21. end if

22. else

23. if Dmax==D1

24. for j=0 to 2 do

25. for i=0 to (k-1)/2 do

26. Lat=random(d1,d1+(D1/(k-1)))；

27. Lng=random(d2,d2+(D2/2))

28. AS ←AS ∪{(Lat,Lng)}；

29. d1=d1+(D1/(k-1))；

30. end for

31. d2=d2+(D2/2)；

32. end for

33. else

34. for j=0 to 2 do

35. for i=0 to (k-1)/2 do

36. Lat=random(d1,d1+(D1/2))；

37. Lng=random(d2,d2+(D2/(k-1)))；

表1 十進制數值對應的base32碼

38. AS ←AS ∪{(Lat,Lng)}；

39. d2=d2+(D2/(k-1))；

40. end for

41. d1=d1+(D1/2)；

42. end for

43. end if

44. end if

45. AS ←AS ∪{(lat,lng)}；

46. Return AS

首先，該算法分別計算經度區間和緯度區間的長度D1和D2，并取出兩者的最大值Dmax，接著，判斷k 值的奇偶性，若為偶數，根據Dmax分為兩種情況，若經度區間的長度較大的話，經度區間均分為k-1 份，在每一份里隨機選取一個位置，緯度取的緯度區間內的任意值，高度與用戶位置高度相同。否則的話，將經度區間均分為k-1 份。若k 為奇數的話，區間長度長的緯度上均分(k-1)/2 份，短的區間內均分2份，在每一子區域內分別隨機選取一個位置點。最后成功構造包含k 個位置的匿名位置集AS。

4.5 位置篩選階段

當反向檢索出來的位置個數大于隱私需求k 值時，要對區間區域內的位置進行篩選。位置篩選算法的偽代碼如下所示。

算法3 位置篩選算法（Locations filtering algorithm）

輸 入：候 選 位 置 集LS ＜(lat1,lng1),(lat2,lng2),…,(latnum,lngnum)＞，用戶真實位置(lat,lng)

輸出：匿名位置集AS

1. 候選位置集中的位置個數為num；

2. A=B=C=D=φ；

3. for i=1 to num do

4. If lati＞lat and lngi＞lng

5. A ←A ∪{(lati,lngi)}；

6. Else if lati＜=lat and lngi＞lng

7. B ←B ∪{(lati,lngi)}；

8. Else if lati＞lat and lngi＜=lng

9. C ←C ∪{(lati,lngi)}；

10. Else

11. D ←D ∪{(lati,lngi)}；

12. End if

13. End for

14. 分別統計列表A、B、C、D 中的位置個數a,b,c,d；

15. 分別從列表A、B、C、D 中隨機選取a(k-1)/num 、b(k-1)/num 、c(k-1)/num 、d(k-1)/num 個位置點添加到匿名位置集AS 中；

16. AS ←AS ∪{(lat,lng)}；

17. Return匿名位置集AS

該算法首先將候選位置集中的位置根據用戶真實位置經緯度分為四類，再根據相應的比例來選取各類中的位置點，最后連同用戶位置添加到匿名位置集AS，發送給LSP，請求位置服務。

4.6 安全性分析

在某些情況下，攻擊者可能會與某些惡意用戶或位置服務提供商進行合作，以獲取合法用戶的位置請求信息。幸運的是，本文的方法可以成功地抵制攻擊者的共謀攻擊。

通常，如果成功推斷真實用戶位置的概率不隨著共謀團體數目的增加而增加，則說明該方法可以抵抗共謀攻擊。

下面對本文提出的方法進行了詳細的安全性分析。

定理本文提出的方法可以抵制共謀攻擊。

證明首先，若攻擊者與某一惡意用戶謀和，攻擊者猜測出真實用戶的概率也是1/k 。因為本文將用戶的經緯度位置擴展到區間區域內，并進行編碼，在歷史請求記錄中選擇與用戶區間區域編碼相同的位置來進行匿名保護，而且，攻擊者只擁有與謀和用戶的歷史請求記錄，卻不清楚被攻擊用戶的歷史請求記錄。所以，攻擊者只能隨機猜測真實用戶的位置，這樣，識別出真實用戶的概率為1/k。甚至，當攻擊者與多個用戶進行謀和時，也不能降低猜測出真實用戶的概率。因為，在本文方法中，用戶與用戶之間是相互獨立的，互不影響，所以本文方法可以抵制攻擊者與惡意用戶的謀和攻擊。

然后，若攻擊者與位置服務提供商進行共謀，由于本文方法在產生區間區域時使用了隨機數，虛假位置的產生和位置篩選都存在隨機的因素，而匿名集的產生是沒有規律可循的，所以攻擊者無法根據匿名集來推測出用戶的真實位置，猜測概率仍然是1/k。

綜上所述，本文提出的方法是可以成功地抵御謀和攻擊的。

5 仿真實驗驗證與分析

為驗證本文所提位置隱私保護方法的有效性，使用Python 編程語言實現算法來進行仿真實驗驗證。位置數據來自Geolife 數據集[27]，該數據集收集了從2007 年4月到2012年8月182個用戶的軌跡數據。這些數據包含了一系列以時間為序的點，每一個點包含經緯度、海拔等信息。包含了17 621 個軌跡，總距離120 多萬公里，總時間48 000多小時。這些數據不僅僅記錄了用戶在家和在工作地點的位置軌跡，還記錄了大范圍的戶外活動軌跡，比如購物、旅游、遠足、騎自行車。仿真實驗主要關注算法處理數據的時間開銷以及生成匿名區域的匿名保護效果。

5.1 處理數據時間開銷

目前，大多數的技術通過距離計算來挑選候選匿名位置集。圖4比較了本文使用的Geohash編碼技術與曼哈頓距離[28]以及歐氏距離[29]處理數據的時間開銷。歐氏距離公式為：

圖4 候選位置數據量與時間開銷關系圖

實驗中，將某一用戶的第一條位置數據作為該用戶真實位置，其余的作為歷史數據用來挑選匿名位置集，運行100次取平均值作為輸出結果進行比較。

如圖4 所示，隨著數據量的增加，三種方法的時間開銷都會增加，而Geohash編碼明顯在時間開銷方面具有卓越的優勢。當數據量達到900條時，花費的時間還不足0.2 s。由于編碼只是將二維的數據變成一維的字符串，不需要進行計算。而基于距離的檢索，則需要進行距離計算，花費的時間就會大大增大。尤其是，采用歐式距離計算時，存在乘法運算，更是加大了時間開銷。因此，通過Geohash 編碼檢索，可以快速地進行匿名處理，從而給用戶提供快速便捷的服務。

5.2 算法執行效率分析

圖5 分別比較了本文的匿名算法、Casper 算法[17]、DLS 算法[19]、SpaceTwist 算法[22]和基于聚類的k-匿名算法[21]執行時間隨k 值變化的趨勢。這里，待處理的歷史請求記錄為500條。

圖5 算法執行時間與k 值的關系圖

如圖5 所示，隨著k 值的增加，所有的算法執行時間都會增加，而本文算法時間開銷是最少的。具體地，由于不借助第三方匿名服務器，SpaceTwist算法使用客戶端附近的錨點來替換用戶的真實位置，客戶端計算壓力大，算法執行時間最長。Casper算法在生成虛假位置時，產生的匿名區域過大，并且會產生大量冗余的位置，時間開銷要大于其余算法。基于聚類的k-匿名算法與Casper算法的匿名處理時間類似，因為該算法使用了聚類算法，時間開銷較大。而DLS算法在匿名處理時，借助歷史記錄數據庫和查詢概率，充分考慮背景信息，需要進行一輪的2k 個虛假位置候選匿名位置集選擇，算法時間復雜度要優于Casper 算法。而本文實現匿名保護時，借助Geohash編碼檢索、生成虛假位置算法和位置篩選算法，可以快速地提供安全的個性化的位置服務。總之，在匿名算法時間開銷上，本文算法占極大的優勢。

5.3 匿名保護效果分析

匿名熵常用來表示位置匿名保護的程度[30]，公式如下：

其中，pi表示真實用戶被識別出來的概率，H(R)代表匿名熵，匿名熵的值越大，表明匿名保護的效果越好。

圖6 表示的是不同算法的匿名熵與k 值的關系。算法包含隨機算法、Casper算法[17]、DLS算法[19]、MOS算法[20]和區間區域算法。

圖6 匿名熵與k 值的關系圖

如圖6 所示，隨著k 值的增加，所有算法的匿名熵都會增加，而本文算法的匿名熵始終是最大的。隨機算法在指定區域內隨機選擇位置，時間開銷最小，但是匿名保護效果很差。隨機產生的虛假位置不考慮位置的合理性，攻擊者可以過濾掉許多位置，導致匿名保護失敗。Casper算法的匿名保護程度要好一點，因為Casper算法借助第三方匿名服務器的歷史請求信息，能夠增大真實用戶不被識別出來的概率，但是，該算法會產生許多冗余區域，所以它的匿名效果也并不是最優的。而DLS 算法考慮了背景信息，同時，產生的虛假位置都是借助歷史上查詢概率相近的位置，所以匿名熵能高一點。MOS 算法生成的虛假位置盡可能遠離真實用戶，攻擊者不能輕易識別出真實用戶，匿名保護程度要優于DLS算法。而本文的機制在產生虛假位置時，在區間區域內均勻產生虛假位置，并且考慮到位置的合理性，根據實際道路情景信息進行位置調整。在位置篩選時，也選擇了與真實用戶相似的位置點，所以本文的匿名算法比前面算法的匿名保護都要好。

6 結束語

對于現有的k-匿名機制借助匿名服務器檢索數據庫時間開銷大的問題，本文提出了借助Geohash編碼的區間區域位置隱私保護策略。該策略首先將用戶的真實位置泛化到區間區域中，然后根據Geohash編碼原理來檢索相同編碼的位置，再根據用戶的隱私需求，為用戶提供個性化的k-匿名隱私保護服務。仿真實驗表明，本文提出的方法在匿名處理時間具有更好的優越性，同時生成虛假位置算法和位置篩選算法保證了虛假位置的分布盡可能均勻，保證了用戶真實位置被識別出來的概率降低，達到了很好的匿名保護效果。由于挖掘大量的位置信息能夠分析用戶的社會屬性，未來的工作將充分考慮用戶請求位置服務的時間維度，并分析和預測用戶行為模型來完善目前的工作，對不確定的不安全因素提前預防，為用戶提供可預測的動態位置隱私保護。