基于Alt-Geohash編碼的k-匿名位置隱私保護方案

摘 要：在對享受基于位置服務（LBS）用戶進行位置隱私保護時，傳統k-匿名技術在執行匿名操作時沒有全面考慮時間開銷和位置背景信息。針對上述問題，提出了一種基于Alt-Geohash編碼的k-匿名位置隱私保護方案（k-anonymous location privacy protection scheme based on Alt-Geohash coding，KLPPS-AGC）。首先，通過位置泛化和Alt-Geohash編碼技術實現對歷史數據的快速檢索；其次，根據歷史查詢概率篩選出能與用戶構建高位置熵的位置；再次，利用海倫公式改善匿名集的位置分散度；最后，構建安全匿名集實現對用戶的位置隱私保護。實驗證明，該方案擁有較低的時間開銷和較高的隱私性。

關鍵詞：基于位置服務；隱私保護；位置隱私；k-匿名；Geohash

中圖分類號：TP18"" 文獻標志碼：A

文章編號：1001-3695（2025）01-038-0276-06

doi：10.19734/j.issn.1001-3695.2024.03.0165

k-anonymous location privacy protection scheme based on Alt-Geohash coding

Abstract：When protecting the location privacy of users who enjoy LBS，traditional k-anonymity techniques often fail to comprehensively consider time costs and location context during anonymization processes.To address this issues，this paper proposed a KLPPS-AGC.Firstly，utilizing location generalization and Alt-Geohash encoding technique enabled rapid retrieval of historical data.Secondly，selecting locations with high location entropy based on historical query probabilities enabled the construction of high location entropy.Furthermore，it enhanced the dispersion of the anonymous set by applying the Haversine formula.Lastly，this paper built a secure anonymous set to protect user’s location privacy.Experiments show that this scheme has lower time cost and higher privacy.

Key words：location-based services （LBS）；privacy protection；location privacy；k-anonymity；Geohash

0 引言

隨著傳感器技術［1］、移動智能終端［2］和無線通信［3］的快速發展，LBS被廣泛應用于多種領域［4，5］。用戶可以通過智能設備定位系統向位置服務提供商（LSP）發送位置查詢，例如查詢附近餐館、醫院、學校或公園等，這在一定程度上便利了用戶生活［6，7］。然而，用戶在享受LBS帶來便利的同時也面臨一定的隱私風險。LBS要求用戶提交實時位置信息，好奇的LSP可能會搜集用戶位置信息，并在用戶不知情的情況下對用戶信息進行分析，從而獲取用戶身份和位置等私人信息［8］。因此，LBS中的位置隱私保護面臨著巨大的挑戰。

在現有位置隱私保護方案中，k-匿名［9］較為常用。該技術的基本思想是將用戶真實位置隱藏在包含k-1個假位置的集合中，攻擊者從匿名集中識別用戶真實位置的概率不高于1/k。文獻［10］在選擇歷史相鄰位置時考慮歷史位置與真實位置之間的距離，濾除過于接近請求用戶的位置，但是該方案只考慮位置之間的最小距離，生成的匿名區域面積可能過大，這將導致查詢精度和服務質量的降低。為此，Alotaibi等人［11］結合最小查詢概率和特定距離半徑選擇假位置，通過距離閾值將匿名區域限制在適當范圍內。然而，這些方案均假設匿名服務器是可信第三方，位置匿名過程均在可信第三方匿名服務器上執行，完全可信的第三方在現實中卻是不存在的。此外，基于k-匿名的位置隱私保護方案在構建候選集時，檢索歷史位置的時間往往隨匿名度的增加而呈現出明顯的增長趨勢，檢索巨大的位置數據可能導致時間開銷過大。為此，Li等人［12］基于Geohash編碼思想，將二維位置坐標轉換為一維字符串，利用編碼前綴實現對歷史位置的快速檢索，將擁有相同編碼前綴的位置納入候選集。然而，該方案并沒有考慮到位置高度。為此，Zhang等人［13］在保留Geohash編碼快速檢索特性的同時將位置高度納入編碼，所選位置不僅與用戶位于同一矩形區間，而且與用戶擁有相似高度，這在一定程度上增加了攻擊者識別用戶真實位置的難度。然而，該方案在構建匿名集時并沒考慮到歷史查詢概率和位置分散度，擁有強大背景知識的攻擊者能夠篩選出部分匿名位置進而導致匿名失敗。

針對上述問題，為解決現有基于k-匿名位置隱私保護方案中存在的時間開銷大、可信第三方帶來的隱私風險以及擁有背景知識攻擊者帶來的推斷風險，本文提出了一種基于Alt-Geohash編碼的k-匿名位置隱私保護方案。為了減少檢索滿足要求的歷史位置所帶來的時間消耗，采用Alt-Geohash編碼算法節省時間開銷；針對第三方匿名服務器帶來的隱私風險，提出了一種去中心化的結構，用戶的匿名化操作均在智能終端上執行；為降低用戶遭受擁有強大背景知識攻擊者的推斷風險，本文在對候選集進行篩選時，不僅考慮了歷史查詢概率，還通過海倫公式對其進行了離散度優化，保證構建的匿名集擁有高位置熵和高分散度。

1 預備知識

1.1 問題描述及隱私風險

在LBS中，當用戶想要從LSP獲得有關查詢的結果時，就必須向不受信任的LSP發送與位置相關的查詢。在該過程中往往存在以下問題：

a）時間開銷方面。在基于k-匿名的隱私保護方案中，構建候選集時往往需要檢索龐大的歷史位置數據庫，檢索歷史數據庫構建候選集的時間往往隨匿名度的增加而增加，尤其是在基于距離計算的檢索方法中，這將在一定程度上降低位置服務的及時性。

b）匿名處理方面。大多方案過于依賴第三方匿名服務器，匿名服務器完成了對用戶位置匿名的全部操作。然而，第三方匿名服務器存儲了所有用戶的位置信息，難免存在不可信的第三方泄露用戶的位置信息的情況，這將給用戶帶來一定的隱私風險。

c）推斷攻擊方面。用戶在與LSP進行交互時，部分好奇的LSP或其他獲取了位置匿名集的攻擊者很容易根據背景知識推斷出用戶的真實位置進而竊取用戶的位置隱私。以隨機生成的匿名集為例，某些位置可能處于河中或無人區中，攻擊者根據掌握的地圖信息很容易將這些位置過濾掉。此外，攻擊者在分析匿名集的位置分布時，可以通過聚類的方式對其進行過濾，這在一定程度上增加了用戶位置隱私泄露的風險。綜上，攻擊者的推斷攻擊模型可以形式化地表述為

其中：h為攻擊者通過背景知識采取的操作；k′是攻擊者通過h過濾掉的匿名位置數量。

1.2 基本思想

針對上述問題，本文致力于構建一個去中心化的位置隱私保護框架，并設計一種基于Alt-Geohash編碼的k-匿名位置隱私保護方案。具體設計目標如下：為保證用戶在進行LBS中的及時性，方案利用Alt-Geohash編碼實現對k-匿名中候選集的檢索。Alt-Geohash編碼能夠對位置進行降維編碼，通過匹配前綴實現對歷史位置的快速檢索；為降低中心服務器帶來的隱私風險，提出了一種去中心化的結構，用戶位置的匿名化操作均在用戶的智能終端設備上完成，全程無第三方服務器的參與，這在一定程度上降低了用戶位置隱私泄露的風險；為應對擁有背景知識的攻擊者對用戶位置進行推測所帶來的隱私風險，在對候選集進行優化時，考慮了位置單元的歷史查詢概率；同時，為避免匿名集的位置分布過于集中，方案通過海倫公式對匿名集進行了離散度的優化?；谠撍枷?，本文提出了KLPPS-AGC的系統結構，如圖1所示，主要由Wi-Fi接入點（access point，AP）、用戶和位置服務提供商組成。目前，Wi-Fi覆蓋面較廣，計算能力和存儲能力也較強。系統中Wi-Fi AP可提供網絡支持，計算并存儲當前覆蓋范圍內所有位置的歷史查詢概率。

在移動網絡的不斷發展下，智能終端的存儲能力和計算能力也不斷地加強。系統中，用戶擁有具有強大存儲能力和計算能力的智能設備，用戶在智能設備上完成位置的匿名查詢和對查詢結果的過濾。位置服務提供商是LBS中不可或缺的部分，可以根據用戶的請求內容為用戶檢索出滿足要求的結果并返回給用戶。

1.3 相關定義

為進一步便于對本文的理解，下面給出了KLPPS-AGC方案的一些相關定義。

定義1 位置匿名集（location anonymity set，AS）。位置匿名集包含了用戶的真實位置和k-1個匿名位置，基本組成形式為AS=（loc1，…，locu，…，lock），其中locu為用戶的真實位置。

定義2 歷史查詢概率。將Wi-Fi AP覆蓋范圍內的地圖區域進行網格劃分，如圖2所示，每個網格代表一個位置單元，計算每個位置單元的歷史查詢概率，公式如下：

定義3 歐氏距離。歐氏距離表示某一位置loci（xi，yi）到其他位置locj（xi，yi）的距離，其中x，y代表位置的緯度和經度。計算公式如下：

定義4 海倫公式。海倫公式應用于多邊形面積的求解。將計算多邊形面積轉換為求解多個三角形面積和。三角形的面積利用三條邊長可以直接求出，公式如下：

其中：m是三角形的半周長；a、b、c為三角形的三條邊。

2 位置隱私保護方案KLPPS-AGC

在利用KLPPS-AGC實現對用戶的位置隱私保護過程中。首先，用戶需要請求當前位置并執行如算法1所示的位置泛化算法，將位置泛化在區間；然后，執行如算法2所示的區間Alt-Geohash編碼算法為區間進行編碼操作，并根據該編碼執行如算法3所示的反向檢索算法，從歷史數據中檢索出滿足要求的位置構建候選集；最后，執行如算法4所示的位置過濾算法優化候選集并生成最終的安全匿名集。

2.1 位置泛化算法

在位置泛化算法中，用戶需要請求定位并獲取當前位置的坐標信息locu（latu，lonu，altu），該算法根據用戶所在的區域類型為用戶選擇不同的隨機數范圍并將用戶的經緯度坐標泛化為相應的區間。對于位于人口密集區域的用戶，為了提高查詢精度，需要將位置泛化在較小的區間內，該算法在［0，0.01］生成四個隨機數r1、r2、r3、r4，并利用這四個隨機數對用戶的經緯度坐標執行加減操作，經該操作后，用戶的經緯度坐標被泛化在（［latu-r3，latu+r1］，［lonu-r4，lonu+r2］）。對于位于人口稀疏區域的用戶，為提高隱私保護效果，需要將位置泛化在更大的區域內，此時該算法需要在［0，0.025］生成四個隨機數并計算得出相應的區間。

算法1 位置泛化算法

輸入：用戶位置的經緯度坐標locu（latu，lonu）；區域類型typecv。

輸出：區間region。

1 if typecv=0 //用戶位于人口密集的城市

2 ranger=［0，0.01］

3 else//用戶位于人口稀少的鄉村

4 ranger=［0，0.025］

5 在范圍ranger中生成四個隨機數r1、r2、r3、r4

6 根據經緯度坐標和隨機數計算得到區間并返回region

算法1的輸入對象為用戶的經緯度坐標locu和區域類型，目的是根據不同區域選擇相應的范圍為用戶生成四個隨機數并得到最終的泛化區間region。其中，第1、2行是對人口密集區域的判定，在符合條件時得到的隨機數ranger為［0，0.01］；第3、4行是對人口稀疏區域的判定，在符合條件時得到的隨機數為［0，0.025］；第5行在隨機數范圍內生成四個隨機數，這四個隨機數可用于第6行中對經緯度坐標的加減操作，經第5、6行生成的區間經緯度分別都向前向后波動，這防止了攻擊者對區間的對稱性猜測，同時，生成的區間也是在相當客觀的范圍內。

2.2 區間Alt-Geohash編碼算法

在得到用戶的位置區間后，用戶執行區間Alt-Geohash編碼算法生成區間的Alt-Geohash編碼，該編碼由經緯度的Geohash編碼和位置高度的高度編碼組成。該算法首先將地球的緯度和經度初始化為［-90，90］和［-180，180］；然后對經度區間和緯度區間進行Geohash編碼，通過判定經緯度區間與地球經緯度范圍的中值的關系給出相應的二進制編碼，并對地球經緯度范圍進行相應的更新，在該步驟中對地球經緯度范圍進行不斷的迭代，并給出經度二進制編碼和緯度二進制編碼，直到經緯度區間不滿足條件為止；其次，將經緯度的二進制編碼交錯排列并根據Base32編碼表［14］將其分組轉換為Geohash編碼；最后，根據本文所選數據集的特點，將用戶的高度與100相除取整后將取整結果加入到Geohash編碼中，得到區間最終的Alt-Geohash編碼。

算法2 區間Alt-Geohash編碼算法

輸入：區間region（［lat1，lat2］，［lon1，lon2］）；用戶位置坐標的高度altu。

輸出：用戶區間的Geohash和AGu。

1 初始化經緯度范圍lngregion和latregion為［-180，180］和［-90，90］

2 while true do

3 計算lonregion的中值lonmid和latregion的中值latmid

4 if lon1，lon2均大于中值lonmid

5" 給出編碼1到list1并更新lonregion的下限為lonmid

6 elif lon1，lon2均小于或等于中值lonmid

7" 給出編碼1到list1并更新lonregion的上限為lonmid

8 if lat1，lat2均大于中值latmid

9" 給出編碼1到list2并更新latregion的下限為latmid

10elif lat1，lat2均小于或等于中值latmid

11" 給出編碼1到list2并更新latregion的上限為latmid

12 述某一條件不滿足時跳出并結束循環

13 合并list1和list2為list，分組轉換為Geohash并對高度進行編碼

14 合并Geohash和高度編碼并返回Geohash和AGu

算法2的輸入對象為從算法1中得到的區間region以及用戶位置坐標的高度altu，目的是生成方便進行候選集檢索的區間Alt-Geohash編碼。其中，第1行對地球經緯度范圍進行了初始化。第2～7行在while循環體中對經度區間進行迭代編碼，通過判定經度區間與地球經度范圍的關系給出了相應的二進制編碼，當經度區間大于地球經度范圍的中值時，給出二進制編碼1并將其傳入經度二進制列表list1中，隨后將地球經度范圍的下限更新為中值。當經度區間小于地球經度范圍的中值時，給出二進制編碼0并將其傳入經度二進制列表list1中，隨后將地球經度范圍的上限更新為中值。第8～11行按照類似于對經度區間的迭代操作對緯度區間進行迭代編碼，最后得到緯度二進制列表list2。第12行給出判定條件，當地球經度范圍或緯度范圍不滿足經緯度迭代條件時結束循環。第13行將list1和list2按照經緯經的順序交錯排列并存儲于新列表list中，隨后對該列表的二進制數從左到右進行分組，每五位一組并將每組的二進制數轉換為十進制數。隨后將十進制數轉換為對應的Base32編碼即得到經緯度區間的Geohash編碼。然后將高度與100相除取整得到高度編碼。在對經緯度區間的迭代編碼過程中，由于區間本身就是一個數值范圍，所以無須用戶自定義編碼的精度。第14行合并Geohash編碼和高度編碼得到區間的Alt-Geohash編碼。

2.3 反向檢索算法

用戶在得到區間的Alt-Geohash編碼后，根據其Geohash編碼長度對歷史位置進行相同精度的Alt-Geohash編碼。該算法在檢索歷史位置時采用邊編碼邊判斷的方法構建候選集，當歷史位置的Alt-Geohash編碼與用戶的區間Alt-Geohash編碼相同時，將該位置納入候選集CLS。當候選集數量等于4k-4時，則返回候選集。若候選集數量不足則擴大到周圍八個網格中，并檢索出與網格擁有相同區間Alt-Geohash編碼的位置，直至候選集數量達到4k-4。

算法3 反向檢索算法

輸入：locu；AGu；Geohash；歷史位置集合HLS和hls；匿名度k。

輸出：候選集CLS。

1 for i in HLS do

2 "根據Geohash的長度計算AGi

3 "if AGi=AGu

4" "將i加入CLS并把i從hls中移除

5" "當候選集數量等于4k-4時結束循環

6 if num！=4k-4

7 "計算用戶區間周圍八個網格的Alt-Geohash編碼

8 for i in hls do

9 "將與網格擁有相同編碼的位置納入CLS

10 "當候選集數量等于4k-4時結束循環并返回CLS

算法3的輸入對象是用戶的位置坐標locu（latu，lonu，altu）、來自算法2的用戶經緯度的Geohash編碼和區間Alt-Geohash編碼、歷史位置集合以及用戶自定義的匿名度k，目的是從歷史位置集合中快速檢索出與用戶擁有相同編碼的位置構建候選集。其中，第1～5行在循環體內根據Geohash編碼的長度對歷史位置執行相同精度的編碼操作，并將與用戶擁有相同編碼的位置納入候選集，在候選集數量足夠時結束該循環；第6、7行是在候選集數量不足時計算出周圍八個網格的編碼；第8、9行通過遍歷找到位于周圍八個網格且與網格擁有相同編碼的位置并加入候選集；第10行在候選集數量足夠時結束檢索并返回候選集CLS。

2.4 位置過濾算法

位置過濾算法從查詢過濾和離散度兩方面對候選集進行優化。在對候選集進行查詢概率優化前，用戶從Wi-Fi AP處接收到區域地圖的歷史查詢信息，整個地圖空間區域被劃分為10×10的網格區域。用戶根據背景信息獲取當前所在位置單元的查詢概率，同時遍歷CLS并獲取所有位置的查詢概率，選出與用戶當前位置單元具有相似查詢概率的位置，經查詢概率優化后的位置集合具有不可區分性。隨后，該算法利用海倫公式迭代地從位置集合中選出能與用戶位置構建出最大區域面積的位置，最后將用戶位置隨機插入經上述兩次優化得到的位置集合中并得到用戶的最終安全匿名集。

算法4 位置過濾算法

輸入：locu；CLS；區域地圖歷史查詢概率信息Mapp；匿名度k。

輸出：匿名集AS。

1 for i in CLS do

2 "將與用戶具有相似歷史查詢概率的位置納入cls

3 for i in cls do

4 "將距離locu最遠的位置點加入集合A并將該點從cls中移除

5 while len （A）lt;k-1 do

6 "for i in cls do

7nbsp; "B=A+［i］

8" "按照位置點與locu的極角對B進行升序排序，并根據海倫公式計算集合B與locu組成的區域面積area

9" "將能組成最大面積的位置加入集合A并從cls中移除

10" "將locu隨機插入A并作為AS返回匿名集

算法4的輸入對象是用戶的位置坐標、候選集、地圖查詢概率信息以及匿名度k，目的是選出能構建出擁有高位置熵和高離散度的位置匿名集。其中，第1、2行根據地圖信息從候選集中選出與用戶擁有相似查詢概率的位置并將其加入位置集合cls；第3、4行在集合cls中選出與用戶距離最遠的位置并將其納入新的集合A；第5～9行在循環體中遍歷集合cls并將遍歷的位置與集合A組成新的集合B，計算出該集合中位置與用戶位置的極角，按照極角對該集合中的元素進行升序排序，并根據海倫公式計算出集合B中的位置與用戶位置構建的區域面積大小。選出能構建最大面積的位置并將該位置納入集合A，隨后將該位置從cls中刪除。以圖3為例，此時集合A有loc1、loc2、loc3這三個位置，從cls中遍歷到位置點loc5時，為求出loc5與集合A中的位置點和locu組成區域面積，本文將計算五邊形面積轉換為求三個三角形面積和。因此，S=S1+S2+S3，其中S1，S2，S3可以根據海倫公式計算出其面積的大小。第10行將用戶位置隨機插入集合A并返回匿名集。

3 性能分析

3.1 隱私性分析

本文在匿名保護效果和位置分散度上對KLPPS-AGC進行隱私性分析，其中，根據匿名集的位置熵對匿名保護效果進行了分析，根據匿名集最小距離對位置分散度進行了分析。下面給出具體的定義和分析。

定義5 位置熵［15］。位置熵通常被用來表示位置匿名保護的程度，公式如下：

其中：H代表位置熵;qi表示真實用戶被識別出來的概率。位置熵越大，表明匿名保護效果越好。

定理1 KLPPS-AGC可以抵御推斷攻擊。

證明 推斷攻擊［16］是指攻擊者可以根據背景信息對用戶的隱私進行分析。KLPPS-AGC通過選擇與用戶擁有相似歷史查詢概率的位置來實現對候選集的優化。KLPPS-AGC所生成的匿名集擁有較高的位置熵，匿名位置的歷史查詢概率與請求用戶的歷史查詢概率相似，攻擊者不能根據位置單元的查詢概率對觀測到的信息進行過濾，因此攻擊者不能分析得出用戶的真實位置單元。此外，KLPPS-AGC采用k-匿名技術，匿名集在滿足匿名度的情況下，攻擊者推斷出用戶真實位置的概率不超過1/k。

綜上所述，KLPPS-AGC可以抵御推斷攻擊。

定義6 最小距離［16］。最小距離是度量位置間距離最小值的指標，公式如下：

其中：Q表示符合最小距離原則的位置集合；Li、Lj代表任意兩個位置；dis表示計算兩個位置之間的距離。

定理2 KLPPS-AGC可以抵御位置同質攻擊。

證明 位置同質攻擊［17］是指攻擊者對用戶提交的匿名集中的多個地點進行分析，并以地點間的距離為依據，判斷兩個地點是否在同一個建筑物中。在匿名集相對較小的情況下，匿名位置分布會過于集中，攻擊者可以利用聚類等手段對匿名集進行篩選。KLPPS-AGC在對候選集進行查詢概率優化之后，利用海倫公式在離散度方面對候選集進行了優化，所生成的匿名集擁有較高的分散度，匿名集的覆蓋范圍也隨之增大。攻擊者對匿名集進行同質分析的機會被切斷了，用戶的位置隱私得到了保障。

綜上所述，KLPPS-AGC可以抵御位置同質攻擊。

3.2 實用性分析

本文對KLPPS-AGC進行了實用性分析，具體如下：

首先，相較于傳統k-匿名的位置隱私保護方案，本文引入了Alt-Geohash編碼技術，該技術利用Geohash編碼的降維存儲和快速檢索特性，提高了在對用戶位置進行匿名時從歷史位置數據庫檢索歷史位置構建候選集的速度，這在一定程度上保證了位置服務的及時性，也保證了用戶的體驗。其次，本文在為用戶構建安全匿名集時，考慮到擁有背景知識的攻擊者對匿名集進行分析的情況，為應對攻擊者根據歷史查詢概率和地圖信息對匿名集進行位置推斷攻擊，在構建匿名集時選擇與用戶擁有相似查詢概率的位置。為了降低匿名集的分布特征，從離散度的角度出發，利用海倫公式對匿名集進行篩選，保證了生成的匿名集擁有較高的離散度，提高了實用性。最后，算法的通信主要是發生在用戶和位置服務提供商之間。由于這些通信僅包括簡單的查詢請求和少量的數據傳輸，所以通信量為常數級，記為O（C）。用戶與匿名服務器之間主要傳輸匿名查詢請求和匿名查詢結果，其中，匿名查詢請求包含了安全匿名集，由于用戶在本地設備完成了對候選集的篩選，進一步降低了位置信息的傳輸量，所以，傳輸匿名查詢請求的傳輸通信量主要取決于匿名度K，記為O（KC）。綜上，KLPPS-AGC擁有較高的實用性和可用性。

3.3 時間復雜度分析

本文對KLPPS-AGC的四個算法進行了時間復雜度方面的分析，此外，還對文獻［18，19］中所提出的兩個具有代表性的主流算法進行了時間復雜度分析，具體分析如下。

算法1的時間復雜度主要由生成隨機數的時間復雜度，執行簡單的數學運算和列表操作的時間復雜度兩部分組成。其中，在第一部分中，生成隨機數的時間與取值范圍無關，時間復雜度通常可以看作是O（1）。第二部分中的數學運算主要是簡單的加法和乘法，能夠在常數時間內完成，列表操作包括構建region列表，其操作數量與輸入參數無關，隱藏時間復雜度為O（1）。綜合以上兩點，該算法的時間復雜度可以近似看作是O（1）。

算法2的主要時間消耗在循環部分，該循環會根據經緯度的范圍不斷計算Geohash編碼，其迭代次數取決于用戶坐標經緯度范圍的大小，因此，該部分的時間復雜度可以視為O（n）。此外，算法2還包含一列簡單的數學運算和列表操作，這些操作均可在常數時間內完成。綜上，該算法的時間復雜度為O（n）。

算法3在第一個循環中遍歷歷史位置數據列表中的每一個元素，該循環的時間復雜度可以表示為O（n），其中n是列表的長度。在第二個循環中，算法3不僅遍歷了歷史位置列表，同時還在候選集數量不足時嵌套了一個循環遍歷周圍八個網格的編碼列表，假設該編碼列表的長度為m，因此，該循環的時間復雜度為O（n×m） 。算法3在循環體之外還包括基本的數學計算和函數等，這些都能在常數時間內完成。綜上，算法3在候選集數量足夠時的時間復雜度為O（n），在候選集數量不足時的時間復雜度為O（n×m）。

算法4在進行查詢概率優化時需要計算位置所在網格的歷史查詢概率，這個過程包括對地圖查詢概率信息的讀取和對每個位置進行的索引計算操作，這些操作的時間復雜度可以近似為O（1）。在離散度優化階段，首先需要遍歷經概率優化后的列表，該部分的時間復雜度為O（n），其中n為該列表的長度。然后是為用戶尋找出能構建最大區域面積的位置，該過程在while循環體中，它涉及到對每個位置的極角計算、列表操作，時間復雜度為O（n2）。綜上，算法4的時間復雜度為O（n2）。

文獻［18］主要分為兩個階段：a）假位置構造、語義相似度和查詢概率的計算以及偏移位置的選取，該階段的操作均通過遍歷位置實現相關操作，時間復雜度為O（n）；b）對假位置的篩選，通過嵌套循環準確度量假位置的離散度，時間復雜度為O（n2）。綜上，文獻[18]的時間復雜度為O（n2）。文獻［19］的時間復雜度主要體現在候選集構建階段和位置并集獲取階段，在候選集構建階段，使用了堆棧排序對臨時位置集合中位置點到用戶位置的距離進行排序，時間復雜度為O（n log n），在位置并集獲取階段，堆棧排序的時間復雜度為O（r log r）。其中，r為集合包含的位置點的個數，生成的查詢結果的時間復雜度為O（nm log n），m為每個位置包含的查詢結果的個數，綜上，該算法的時間復雜度為max（O（r log r），O（nm log n））。對比分析發現，本文算法擁有較低的時間復雜度。

4 實驗驗證

4.1 實驗設置

實驗環境：實驗采用PyCharm 2022.3.3的開發平臺，通過Python編程實現算法。實驗運行的硬件環境是AMD Ryzen 7 2.90 GHz處理器，16 GB內存的Windows 11操作系統。

實驗數據：實驗中的位置數據來自Geolife數據集［20］，它收集了2007年4月到2012年8月期間182名用戶的軌跡數據。該數據集的GPS軌跡由一系列帶有時間戳的點組成，每個點都包含緯度、經度和高度等信息。本次實驗中，實驗所選用的位置數據的緯度區域為39.4到41.6，經度區域為115.7到117.4，用戶的整體位置分布如圖4所示。對于每個用戶的軌跡記錄，實驗將用戶的第一個記錄作為真實位置，其余的作為該用戶的真實位置。

實驗參數設置：實驗參數配置情況如表1所示。

4.2 實驗結果與分析

1）處理數據的時間開銷 為了分析Alt-Geohash編碼在檢索歷史數據時的時間開銷，實驗將某一用戶的第一條數據作為用戶的真實請求位置，剩下的數據作為歷史位置數據用以構建位置候選集。

圖5分析了Alt-Geohash編碼在檢索歷史數據時，當候選位置數據量從100增加到900時的時間開銷的變化情況。

通過分析，KLPPS-AGC在采用Alt-Geohash編碼從歷史數據庫中檢索滿足要求的位置構建候選集時，隨著候選位置數據量的增加，檢索數據的時間也有所增加。然而由于Alt-Geohash編碼只是將三維位置坐標信息降維編碼為一維字符串，不需要任何基于距離的計算，所以基于該編碼算法，當數據量達到900條時，總共花費的時間也不足0.1 s。因此，通過Alt-Geohash編碼檢索，可以實現對歷史數據的快速檢索，從而給用戶提供更便捷的服務。

2）匿名保護效果 圖6對比了KLPPS-AGC、GLPS［21］和LPPS-AGC算法［13］在位置熵方面的不同。隨著k值的增加，所有算法的位置熵都有所增加，而KLPPS-AGC的位置熵始終是最大的。其中，LPPS-AGC僅根據Alt-Geohash編碼來檢索歷史位置構建候選集，忽略了歷史查詢概率，因此該方案擁有較低的位置熵。GLPS構建的匿名集相較于LPPS-AGC擁有更高的位置熵，但相較于KLPPS-AGC還是略低。KLPPS-AGC在構建候選集時考慮了歷史查詢概率，選擇的位置的歷史查詢概率與用戶相似，因此具有更高的位置熵。總體來說，本文算法能夠構建出擁有更高位置熵的匿名集，隱私保護效果最好。

3）位置分散度 圖7比較了KLPPS-AGC和LPPS-AGC［13］以及MMDS［16］在位置分散度方面的不同。通過對比發現，k值越大，這三種算法生成的匿名集中位置之間的最小距離越小，隱私保護強度越低。

LPPS-AGC在生成假位置時，將用戶所在區間均勻劃分為網格，并在網格中隨機生成匿名位置，采用隨機策略生成假位置也使匿名位置集具有隨機性，該算法在離散度方面缺少了一定程度的優化，因此，該算法擁有較低的位置分散度。MMDS雖然考慮了假位置的分散度，但該算法限制了匿名位置的距離范圍，因此該算法相較于LPPS-AGC擁有更低的位置分散度。本文KLPPS-AGC在對候選集進行優化時，引入了海倫公式，保證了構建的匿名集擁有最高的離散度。總體來說，KLPPS-AGC有效地提高了匿名集的位置分散度，減小了用戶遭受位置同質攻擊的風險，隱私保護最有效。

此外，實驗選用了用戶001并設置了匿名度k=5，并將第一個位置數據作為用戶當前的請求位置，其余位置數據作為用戶的歷史位置數據。利用KLPPS-AGC為用戶生成滿足一定隱私需求的安全匿名集，并將生成的匿名集的位置繪制成了位置分布立體圖。位置分布立體圖如圖8所示，其中，紅色代表了用戶位置，其他顏色代表了匿名位置（參見電子版）。通過分析，可以發現在位置分布立體圖中，所生成的匿名集并沒有以用戶為中心，位置分布較為均勻和分散，在這樣的匿名集中，用戶遭受位置同質攻擊的風險在一定程度上有所降低。此外，本文算法由于考慮了用戶的位置高度，所以構建的匿名位置和用戶真實位置具有相似的高度，這在一定程度上混淆了攻擊者，增加了攻擊者識別用戶真實位置的難度。

4）匿名處理時間 圖9分別比較了本文KLPPS-AGC和DLIP［8］以及MMDS［16］在匿名處理時間上的不同。

通過對比發現，三種算法的執行時間都隨k值的增加而增加，而本文算法的時間開銷是最少的，增長也是最慢的。具體地，DLIP因為需要計算語義相似度、歷史查詢概率以及離散度等，所以該算法的運行時間隨k值的增加也快速增長。MMDS由于在考慮位置語義和查詢概率的基礎上，沒有運用較為費時的海倫公式對候選集進行篩選，所以MMDS的運行時間在一定程度上低于DLIP，但是隨著k值的增加，DLIP整體呈現出緩慢的增長趨勢。相較于其他兩種方案，KLPPS-AGC沒有語義的計算，同時利用了Alt-Geohash編碼的快速檢索特性，在一定程度上縮短了匿名處理時間?？傮w來說，KLPPS-AGC在時間開銷方面更具有優勢，效率更高。

5 結束語

現有k-匿名位置隱私保護方案往往忽略了檢索歷史數據帶來的時間開銷問題以及未充分考慮攻擊者擁有各種背景知識信息等問題。本文提出了一種基于Alt-Geohash編碼的k-匿名位置隱私保護方案，利用Alt-Geohash編碼實現了對歷史位置數據的快速檢索，在構建候選集時充分考慮了歷史查詢概率和位置分散度，構建出的匿名集擁有較高的位置熵和較高的位置分散度，有效地抵抗了推斷攻擊和位置同質攻擊。本文主要針對的是快照查詢的用戶的隱私保護，因此，下一步將考慮在連續查詢中對用戶的位置隱私保護。

參考文獻：

［1］鄒永攀，王丹陽，王丹，等.基于多源域對抗遷移學習的可穿戴情緒識別技術［J］.計算機學報，2024，47（2）：1-21.（Zou Yongpan，Wang Danyang，Wang Dan，et al.Wearable emotion recognition technology based on multi-source domain adversarial transfer learning［J］.Chinese Journal of Computers，2024，47（2）：1-21.）

［2］曾菊儒，陳紅，彭輝，等.參與式感知隱私保護技術［J］.計算機學報，2016，39（3）：595-614.（Zeng Juru，Chen Hong，Peng Hui，et al.Participatory perceptual privacy protection technology［J］.Chinese Journal of Computers，2016，39（3）：595-614.）

［3］吳紅海，馬華紅，邢玲，等.一種多用戶協作博弈的視頻機會傳輸路由算法［J］.軟件學報，2020，31（12）：3937-3949.（Wu Honghai，Ma Huahong，Xing Ling，et al.A multi-user cooperative game vi-deo opportunity transmission routing algorithm［J］.Journal of Software，2020，31（12）：3937-3949.）

［4］Yan Liang，Li Lei，Mu Xuejiao，et al.Differential privacy preservation for location semantics［J］.Sensors，2023，23（4）：2121.

［5］Nisha N，Natgunanathan I，Xiang Yong.An enhanced location scatte-ring based privacy protection scheme［J］.IEEE Access，2022，10：21250-21263.

［6］Wazirali R.A review on privacy preservation of location-based services in Internet of Things［J］.Intelligent Automation amp; Soft Computing，2022，31（2）：767-779.

［7］Ullah I，Shah M A，Wahid A，et al.ESOT：a new privacy model for preserving location privacy in Internet of Things［J］.Telecommunication Systems：Modeling，Analysis，Design and Management，2018，67（4）：553-575.

［8］Zhang Ai，Li Xiaohui.Research on privacy protection of dummy location interference for location-based service location［J/OL］.International Journal of Distributed Sensor Networks，2022，18（9）.（2022-09-21）.https：//doi.org/10.1177/15501329221125111.

［9］Wang Xiaohan，Luo Yonglong，Liu Shiyang，et al.Subspace k-anonymity algorithm for location-privacy preservation based on locality-sensitive hashing［J］.Intelligent Data Analysis，2019，23（5）：1167-1185.

［10］Guo Xueying，Wang Wenming，Huang Haiping，et al.Location privacy-preserving method based on historical proximity location［J］.Wireless Communications and Mobile Computing，2020，2020：8892079.

［11］Alotaibi R，Alnazzawi T，Hamza N.A new location-based privacy protection algorithm with deep learning［J］.Security and Privacy，2021，4（1）：e139.

［12］Li Hongtao，Xue Xingsi，Li Zhiying，et al.Location privacy protection scheme for LBS in IoT［J］.Wireless Communications and Mobile Computing，2021，2021：9948543.

［13］Zhang Zekun，Sun Xiaoting，Chen Siyang，et al.LPPS-AGC：location privacy protection strategy based on Alt-Geohash coding in location-based services［J］.Wireless Communications and Mobile Computing，2022，2022：3984099.

［14］Li Wenzhe，Liu Kezhong，Jing Guo.Fast data analysis method based on AIS system［C］//Proc of the 7th International Conference on Energy.［S.l.］：Atlantis Press，2018：1449-1455.

［15］Niu Ben，Li Qinghua，Zhu Xiaoyan，et al.Enhancing privacy through caching in location-based services［C］//Proc of IEEE Conference on Computer Communications.Piscataway，NJ：IEEE Press，2015：1017-1025.

［16］王潔，王春茹，馬建峰，等.基于位置語義和查詢概率的假位置選擇算法［J］.通信學報，2020，41（3）：53-61.（Wang Jie，Wang Chunru，Ma Jianfeng，et al.Dummy location selection algorithm based on location semantics and query probability［J］.Journal on Communications，2020，41（3）：53-61.）

［17］Xing Ling，Zhang Dexin，Wu Honghai，et al.Distributed k-anonymous location privacy protection algorithm based on interest points and user social behavior［J］.Electronics，2023，12（11）：2446.

［18］張愛，李曉會，李波.基于假位置選擇的位置隱私脫敏算法［J］.計算機應用研究，2022，39（5）：1551-1556.（Zhang Ai，Li Xiaohui，Li Bo.Location privacy desensitization algorithm based on dummy location selection［J］.Application Research of Computers，2022，39（5）：1551-1556.）

［19］劉振鵬，苗德威，劉倩楠，等.k-匿名下通過本地差分隱私實現位置隱私保護［J］.計算機應用研究，2022，39（8）：2469-2473.（Liu Zhenpeng，Miao Dewei，Liu Qiannan，et al.Location privacy protection through local differential privacy under k-anonymity［J］.Application Research of Computers，2022，39（8）：2469-2473.）

［20］Li Yongjun，Zhu Yuefei，Fei Jinlong，et al.Diverse metrics for robust LBS privacy：distance，semantics，and temporal factors［J］.Sensors，2024，24（4）：1314.

［21］Liu Bin，Zhang Chunyong，Yao Liangwei，et al.GLPS：a Geohash-based location privacy protection scheme［J］.Entropy，2023，25（12）：1569.