融合語義信息的最優位置選擇算法

中圖分類號： TO309 文獻標志碼： ADOI： 10. 13705 / j. issn. 1671-6841. 2023263

文章編號： 1671-6841（2025）04-0088-07

Abstract： Currently， the widespread application of location services poses challenges to personal information security. In response， researchers explored various strategies for location privacy protection， with algorithms incorporating semantic information emerging as a key focus. A new idea for selecting location centers was proposed using semantic information， integrating this concept with semantic distance to choose the optimal anonymous candidate set， thereby ensuring the semantic and physical diversity of the location set. Experimental results demonstrated that compared with DLS， Enhanced-DLS， and MMDS algorithms， the method maintained diversity in both semantic and physical aspects， effectively reducing the accuracy of location data and protecting user privacy.

Key words： location privacy; semantic information; location center; anonymous candidate set

0 引言

在當前數字化社會的背景下，基于位置的服務（ location-based service，LBS） 和定位技術得到了廣泛應用，進而使用戶位置隱私的問題受到了關注。 在眾多應用場景中，如社交網絡、個性化廣告推送、導航與路徑規劃等，常常涉及對用戶位置信息的收集與應用。 用戶的位置數據含著極高的隱私性和敏感度，能透露個體的日常行為模式、偏好，甚至是精確的位置和行動軌跡等信息。 不當的信息使用或泄露可能導致用戶面臨嚴重的安全威脅、經濟損失，以及隱私權的侵犯。 鑒于這些潛在的后果和風險，確保位置信息的嚴密保護與妥善管理顯得至關重要。

相關工作

為了保護用戶位置隱私，國內外學者提出了如匿 名 集 合 [ 1- 2] 、 差 分 隱 私 [ 3- 4] 、 位 置 混 淆 [ 5- 6] 以 及 同態加密[ 7] 等相關技術，目的是通過不同策略降低個人位置信息的可識別性和追蹤風險。 Gruteser 等[ 8]首次把 k -匿名概念引入位置隱私保護領域，通過構建一個含 k-1 個鄰近位置的集合隱藏真實位置。

在上述位置隱私保護方法的基礎上，Niu 等[ 9]提出了基于熵度量的 DLS（ dummy location selection，DLS）算法，實現 k -匿 名 的 同 時，通 過 Enhanced-DLS算法確保選擇的位置點均勻分布于各區域。 王潔等[ 10] 提出 了 MMDS （ maximum and minimum dummyselection，MMDS）算法，保證了位置集合的語義，然后根據查詢概率和地理位置的物理分散性得到最終假位置集合，解決了攻擊者能夠排除部分虛假位置的問題。 楊洋等[ 11] 提出一種矩形區域的 k -匿名位置隱私保護方法，用矩形區域范圍代替用戶位置進行匿名。 文獻[12-14]結合地理位置語義和其他背景信息降低用戶位置泄露的概率。 文獻[15-17] 結合概率分布、位置信息和 k -匿名，優化了啞元位置的生成和選取。 文獻[18] 結合路網環境，提高算法對用戶位置的保護能力。 然而， k -匿名技術的局限在于它通常僅關注位置的地理屬性，忽視了位置的語義信息，對抗背景知識攻擊的效果有限，這可能使攻擊者能夠通過長期分析來揭露用戶的具體位置。

上述提到的解決方案雖然能夠有效應對真實用戶匿名區域生成和啞元位置選擇的問題，但它們在位置選擇時缺乏對語義多樣性的考慮，無法很好地平衡物理分散性和數據多樣性，存在潛在的用戶隱私泄露風險。 因此，本文提出了一種融合語義距離的位置中心選擇算法，以期更有效地保護位置隱私。本研究的主要貢獻如下。

1） 選擇物理位置候選集合，使集合中位置之間的相互距離盡可能遠，提高位置集合的物理分散性。2） 計算語義相似距離，提高最終位置候選集合的語義多樣性。3） 通過理論分析和實驗結果的驗證，所提出的方案能夠較好地提高位置隱私的安全性、降低位置數據的準確度。

2 系統模型

2. 1 系統架構

集中式架構的服務器模型由移動用戶、第三方可信匿名（ trusted third party，TTP） 服務器和 LSP（ lo-cation services platform，LSP ） 平 臺 三 部 分 組 成，由 于系統依賴第三方服務器的可靠性，很容易陷入瓶頸。TTP 本身存儲著大量真實的用戶位置信息，如果服務器受到攻擊，會對用戶造成嚴重的損失，甚至導致整個隱私保護方案的失效。 因此，本文使用分布式架構（ peer to peer， P2P ） ， 僅 由 移 動 用 戶 和 LSP 組成，不需要可信的第三方匿名服務器，鄰居位置的選擇和請求查詢服務都是在移動客戶端完成的。

P2P 架構主要由 GPS 衛星定位系統、Wi-Fi 接入點（ access point，AP） 、移動用戶和 LSP 組成，其主要功能如下。

1） GPS 衛星定位系統為移動終端提供當前位置的地理信息。

2） Wi-Fi 接入點為移動終端提供位置語義信息。

3） 移動用戶是指有移動設備的人類實體。 移動用戶從 Wi-Fi 接入點獲取區域內（ 包括真實位置在內）的位置信息，將真實位置藏匿在匿名候選集中發送給 LSP 服務平臺。

4） LSP 服務平臺接收到用戶請求后，對匿名候選集中的位置全部進行查詢，將結果返給移動終端。

2. 2 相關定義

定義 1 用戶的真實位置 l_real 。 包括用戶位置的經度、緯度和位置名稱。

定義 2 匿名度 k 。 表示每次向 LSP 服務器發送匿名集合的長度，并且攻擊者能夠識別出真實位置的概率為 1/k 。

定義 3 物理距離候選集 。表示滿足物理距離的位置集合。

定義 4 語義距離候選集 l_k-1} 。 表示滿足語義多樣性的位置集合。 最終的位置候選集 RS 包括語義距離候選集 S₂ 和真實位置l real 。

2. 3 語義距離計算方法

采用編輯 距 離 （ edit distance） 來 計 算 語 義 距 離dis_sem ，編輯距離是衡量兩個字符串相似度的方法，較大的編輯距離意味著更低的相似度。 當計算兩個字符串間的編輯距離時，首先要建立一個動態規劃矩陣。 在這一矩陣 D 中， D[i，j] 是字符串之間的編輯距離，在本文中每個編輯操作（ 如插入、刪除、替換）的成本設定在 0 和 1。

設有字符串 A=a₁a₂…a_n 和 B=b₁b₂…b_n ， 若a_?i=b_?i ， 則替換操作的成本為 0;若字符不同，則替換操作的成本為 1。 因此，語義距離 dis_sem 表示將 A 轉化成 B 的最小變動次數。

2. 4 物理距離

通常用位置之間的距離和來測量位置候選集所覆蓋的范圍，即

其中： d（c_i，c_j） 表示位置 c_i 和 c_j 之間的距離。

然而，在選擇鄰居位置時，使用距離之和的方式可能不如距離乘積更好，距離乘積的方式能更好地擴展匿名區域。 即

在圖 1 中， A 是用戶的真實位置， B 是距離 A 最遠的鄰居位置。 假設有兩個選擇來分配第三個鄰居位置（ C 或 N ）。 如果根據距離之和來選擇位置，則C 和 N 被選中的概率相同。 然而，從隱私的角度來看，選擇 C 比選擇 N 更有利，因為 C 將進一步擴大匿名區域。 因此，本文選擇使用位置間距離乘積的方式選擇鄰居位置。 在這種情況下， CA?CBgt;NA ·NB ， 選擇 C 作為虛擬位置。

圖 1 物理距離

Figure 1 Physical distance

2. 5 匿名區域面積

匿名區域面積 D 是由假位置點 k 組成的凸包面積。 凸包是給定點集內部的最小凸多邊形。 k 個位置點被用于隱私保護，而凸包的面積是衡量匿名程度的一個指標。 隨著凸包面積的增加，匿名程度也隨之提高，從而能更好地保護用戶的隱私。 凸包面積的計算可以使用鞋帶公式[ 19] ，即

其中： m 表示位置候選集 RS 最外層位置點的個數。

2. 6 用戶隱私需求

每個用戶有一個隱私需求 s ，用二元組 （k，u） 表示， k 代表匿名度，在每次查詢中，服務器能夠獲得真實位置，以及 k-1 個鄰居位置，并且攻擊者識別真實位置的概率不超過 1/k 。 u 代表語義差異度，表示任意兩個位置之間的語義距離 dis_sem 必須大于等于一個最小可接受值 u ，即 dis_sem（l_i，l_j）_min?u ， 以確保假位置集合中位置的語義多樣性。

2. 7 安全值-θ

安全值- ?θ 是用于衡量位置集 RS 與真實位置語義差異的度量標準，計算公式為

其中： 是位置候選集中的任意兩個位置; ξ_l 是語義多樣性的默認閾值。結果集 RS 稱為安全值- ?θ 集合，安全值- ?θ 越大，表示生成的假位置集具有更大的語義差異度。

3 算法設計

本文提出的 位 置 候 選 集 生 成 算 法 MM-DLS（ maxmin-dummy location selection，MM-DLS） 由 以 下兩個算法實現：算法 1 采用最大最小距離生成物理距離候選集 S_ν1 ;在算法 2 中，通過計算候選集合 S_ν1 中位置間的編輯距離生成語義距離集合 S_ν2 。 最終將真實位置 l_real 與語義距離候選集合 S_Φ2 合并成為位置候選集合 RS 。

3. 1 算法 1

使用算法 1 計算正方形區域中位置地理坐標的中心，得到 2k 個位置中心，根據物理距離將盡可能遠的對象作為位置中心。 首先，將真實位置 l_real 作為第一位置中心，然后選擇距離第一位置中心最遠的樣本作為第二位置中心。 對于第二個位置中心之后的每一個位置中心，計算該點與所有位置中心的距離，選擇乘積最大的點作為下一個位置中心。 在確定所有位置中心之后，將包括 2k 個位置中心的樣本集合作為物理距離候選集 S_ν 。 算法 1 偽代碼描述如下。

算法 1 計算物理距離并獲取虛擬位置集 S_ν1 輸入： 位置數據集 S_n ， 用戶隱私需求 k 。

輸出： 生成位置候選集合 S_ν 。1） k_?1=2k，S_?1=NULL_?? 2） 將真實位置 l_real 作為第一位置中心 Z1 。3） S_n=S_n-l_real，k₁=k₁-1 。4） 找到距離 Z1 最遠的位置 l_i ， 該位置被視為第二個位置中心 Z2。5） S_nS_nl₂，S₁S₁∪l₂，k₁=k₁-1 。6） for i in range （k₁） 7） dis_max=0 8） for each l_i in S_n

9） if l_j not in S_Ω1

10） dis = haversine （l_i，l_j） for l_j in S_ν1

11） dis_all=dis_max?dis_max

12） ifdis_allgt;dis_max

13） dis_max=dis_all

14）

15） S_I=S_I∪l_i

16） end if

17） end if

18） end for

19） end for

20） return S₁

3. 2 算法 2

在物理位置候選集 S_ν1 的基礎上，通過計算編輯距離，從 S_ν1 中篩選出與真實位置語義距離相差最大的 k-1 個位置，形成語義距離候選集 S_Φ2 。 最終，將語義距離候選集 S_ν2 和真實距離 l_real 合并，形成最終候選集 RS 。 其中計算語義距離采用編輯距離的方法進行計算，計算編輯距離偽代碼描述如下。

算法 2 計算語義編輯距離

輸入： 位置 l_i ， 位置 l_j 。

輸出： 語義距離 dis_sem 。

1） S_i=l_i，S_j=l_j 。

2） S_i=a₁a₂…a_i，S_j=a₁a₂…a_j

3） n_?1=length（S_?i），n_?2=length（S_?j）， 。

4） if n₁=0 or n₂=0

5） return 0。

6） end if

7） 構造 n₁+1 行， ψ_n2+1ψ 列矩陣 D 。

8） for i from 0 to n_?1

9） D[i][0]=i

10） end for

11） for j from 0 to n₂

12） D[0][j]=j

13） end for

14） for i from 1 to n₁

15） for j from 1 to n₂

16） ifS[i-1]=S[j-1]

17） cost=0

18） else

20） 19）

21） end for

22） end for

23） dis_sem=D[n₁][n₂]，

24） return dis_sem 。

3. 3 安全性分析

在位置隱私保護中，如果 k 個位置處于聚集區域，則減少搜索范圍可輕松地獲取真實位置，這時k -匿名只是滿足數量上的要求，而未達到實際的匿名效果。 在 MM-DLS 方法中，位置候選集是在算法1 的基礎上生成的，并均勻分布在匿名區域中。 因此，真實位置與其他 k-1 個位置區分的概率為1/k ， 從而滿足匿名效果。

在語義攻擊中，攻擊者可以根據鄰居位置的語義關系來推斷查詢用戶的隱私信息。 地名的語義差異越大，位置的語義多樣性就越好。 在算法 2 中，通過選擇距離真實位置語義距離最大的 k 個位置，形成語義距離位置候選集，從而滿足地理語義多樣性的要求。

綜上所述，所提出的方法滿足物理多樣性和語義多樣性的要求，能夠有效保護位置隱私。

4 仿真結果與分析

4. 1 實驗設置

為了驗證 MM-DLS 算法在選擇最優位置時的有效性和性能，本研究在真實的位置數據集上進行了實 驗。 實 驗 數 據 集 的 選 取 范 圍 包 括 緯 度 從39.95^° 到 40.00^° ，經度從 116.30^° 到 116.35^° 的地理坐標范圍，該數據集包含了 36 663 個位置信息點，覆蓋了北京市海淀區的大部分區域。

為了更好地分析數據， 將該地區劃分成一個10×10 的網格，并通過圖 2 對數據分布情況進行可視化展示。

圖 2 Geolife 數據熱力圖

Figure 2 Geolife data heatmap

此外，考慮到 Geolife 數據集[ 20] 中的位置點未提供相關的位置語義信息，采用高德地圖來獲取這些位置的相關語義信息以便進行實驗研究。

實驗使用 Python 語 言 編 寫，在 Intel Core i5 處理器和 8 GB 內存的計算機上運行。 開發環境選用了 Pycharm， 同 時 使 用 了 pandas、 numpy 和 scikit-learn 等多個開源庫。 語義差異度為 8，語義距離閾值范圍為[3，14] 。

4. 2 結果分析

本文采用物理分散性和語義分散性這兩個度量標準來衡量匿名集 RS 的質量，將 MM-DLS 算法與同樣使用位置技術的 DLS 算法[ 9] 、Enhanced-DLS 算法[ 9] 和 MMDS 算法[ 10] 進行比較。

4. 2. 1 物理分散性 本文從三個方面對算法生成位置集的物理分散程度進行評估：最小距離、最大距離和匿名區域面積。 當位置集合 RS 中位置間的最小距離、最大距離和匿名區域面積越大時，說明選取的位置在區域內分布得越均勻。

實驗將 MM-DLS 算法、DLS 算法、Enhanced-DLS算法和 MMDS 算法進行了比較，結果如圖 3、圖 4、圖5、圖 6 所示。

圖 3 最小距離

Figure 3 Minimum distance

如圖 3 所示，隨著 k 的增加，四種算法生成的位置點間最小距離均呈現下降的趨勢。 MM-DLS 算法的最小距離顯然比其他三種算法要大。 因為 MM-DLS 算法優先選擇與真實位置距離最遠的點作為中心，重視位置間的物理分散性。 相較而言，DLS 算法主要依據位置的查詢概率熵形成候選集，而不考慮物理距離。 而 Enhanced-DLS 和 MMDS 算法盡管考慮了物理距離，但在計算位置查詢概率熵時可能排除了遠距離位置，導致它們的最小距離隨 k 的增大而趨近于 DLS 算法。 實驗結果表明，本文方法在保持物理位置分散性方面表現更佳。

如圖 4 所示，當 k?3 時，MM-DLS 算法位置之間的最大距離最大。 這是因為該算法初步以距離最遠的點作為位置中心，進而以最終的位置中心形成物理距離候選集，確保位置間距離。 圖 5 和圖 6 表明，當 k 較小時，MM-DLS 算法產生的匿名區域面積大于其他三種算法。 當 k 較 大 時， MM-DLS 算 法、Enhanced-DLS 算法和 MMDS 算法的匿名區域面積相似，且面積均大于 DLS 算法。 這主要是由于本文提出的算法在保障位置分散性的同時，也確保了興趣點類別的多樣性。 Enhanced-DLS 算法在考慮歷史查詢概率后，再考慮位置點間距離，而 DLS 算法則僅側重于位置的歷史查詢概率。 MMDS 算法在進行位置選擇時，首先考慮了語義差異度大的位置，而在現實生活中，位置距離較遠的地點，其語義差異度通常是較大的。

圖 4 最大距離

圖 6 較大時匿名區域面積

Figure 6 Anonymity region area for big values of k

因此，本文提出的 MM-DLS 算法在與其他三種算法進行比較時，仍然具有較好的物理分散性。

4. 2. 2 語義多樣性 本研究對比了 MM-DLS 算法、

DLS 算法和 Enhanced-DLS 算法的語義多樣性。 實驗通過分析候選集中的語義多樣性，計算了 θ 位置安全值，結果展示如圖 7 所示。

圖 7 安全值-θ

Figure 7 safe value-θ

如圖 7 所示，隨著 k 值增加，MM-DLS 和 MMDS算法的安全值-θ 接近于 1，符合語義多樣性的要求，而 DLS 和 Enhanced-DLS 算 法 的 安 全 值-θ 相 對 較低。 這是因為 DLS 和 Enhanced-DLS 算法主要關注鄰居位置間的查詢概率，忽略了語義信息。 高查詢概率的位置多在熱點區域，其語義相似性較高，導致這兩種算法的語義多樣性較差，安全值-θ 低。

本文通過實驗對比表明，所提出的 MM-DLS 算法在選取鄰居位置時展現出更佳的物理分散性和語義多樣性，有效避免了攻擊者利用地理語義信息特征對用戶發起攻擊。 因此，該方法能有效保護用戶的位置隱私。

5 結語

針對傳統假位置隱私保護方案未充分考慮攻擊者背景知識的問題，本文提出了一種融合語義的最優位置選擇算法 MM-DLS。 這一算法在保護用戶隱私方面考慮了語義信息與物理分布等多重因素，從而有效降低攻擊者推斷出用戶真實位置的可能性。首先利用距離乘積方法找到滿足物理多樣性要求的物理位置候選集合 S_ν ; 隨后，算法通過計算 S_ν1 中位置與真實位置之間的語義距離，篩選出語義距離較遠的 k-1 個位置，與真實位置一同構成最終的匿名集合。 這樣構成的匿名集合既符合物理多樣性的要求，也滿足語義多樣性的標準。

實驗從最小距離、最大距離、匿名區域面積及安全值-θ 四個維度對本文的 MM-DLS 算法與 DLS 算法、Enhanced-DLS 算 法、 MMDS 算 法 進 行 了 比 較。結果表明，MM-DLS 算法在鄰居位置選擇過程中有效保護了真實位置隱私，同時在物理分散性和語義多樣性方面展現了優異性能，形成了高質量的位置集合，提高了算法效率和可擴展性。 然而，該算法未考慮位置查詢概率信息，可能不足以抵御擁有查詢概率背景知識的攻擊者，因此位置隱私保護的研究還要進一步深入。

參考文獻：

[1] 馮亞平， 康海燕. 基于緩存的位置隱私保護方法研究 [ J] . 鄭州大學學報（ 理學版） ， 2019， 51（4） ： 49-55. FENG Y P， KANG H Y. A location privacy preserving method based on caching[ J] . Journal of Zhengzhou university （ natural science edition） ， 2019， 51（ 4） ： 49-55.

[2] PENG W P， MA D， SONG C， et al. A K-anonymous location privacy-preserving scheme for mobile terminals [ EB / OL] . （ 2023-12-11） [ 2024-01-15] . https：∥publications. eai. eu / index. php / el / article / view / 4468 / 2745.

[3] GAO H F， ZHANG Z Q， ZHAO H W. Personalized privacy protection based on space grid in mobile crowdsensing[ J] . Applied sciences， 2023， 13（23） ： 126.

[ 4] ZHU L， LEI T T， MU J Q， et al. Differential privacybased spatial-temporal trajectory clustering scheme for LBSNs[ J] . Electronics， 2023， 12（18） ： 3767.

[ 5] KOU K Q， LIU Z B， YE H， et al. A location privacy protection algorithm based on differential privacy in sensor network[ J] . International journal of embedded systems， 2021， 14（5） ： 432-442.

[6] KHODAEI M， PAPADIMITRATOS P. Cooperative location privacy in vehicular networks： why simple mix zones are not enough [ J ] . IEEE Internet of Things journal， 2021， 8（10） ： 7985-8004.

[7] ZHENG X D， YUAN Q， WANG B， et al. A homomorphic encryption based location privacy preservation scheme for crowdsensing tasks allocation [ J ] . Wireless personal communications， 2022， 126（1） ： 719-740.

[8] 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 Press， 2003： 163-168.

[9] NIU B， LI Q H， ZHU X Y， et al. Achieving k-anonymity in privacy-aware location-based services [ C ] ∥IEEE INFOCOM 2014-IEEE Conference on Computer Communications. Piscataway：IEEE Press，2014： 754-762.

[10] 王潔， 王春茹， 馬建峰， 等. 基于位置語義和查詢概 率的假位置選 擇 算 法 [ J] . 通 信 學 報， 2020， 41（ 3） ： 53-61. WANG J， WANG C R， MA J F， et al. Dummy location selection algorithm based on location semantics and query probability [ J ] . Journal on communications， 2020， 41（3） ： 53-61.

[11] 楊洋， 王汝傳. 增強現實中基于 LBS 的雙重匿名位置 隱私保護方法[ J]. 南京師大學報（ 自然科學版）， 2018， 41（3） ： 42-46. YANG Y， WANG R C. Double anonymity location privacy protection based on LBS in augment reality[ J] . Journal of Nanjing normal university （ natural science edition） ， 2018， 41（3） ： 42-46.

[12] KUANG L， WANG Y， ZHENG X S， et al. Using location semantics to realize personalized road network location privacy protection[ J] . EURASIP journal on wireless communications and networking， 2020， 2020（ 1） ： 435 - 465.

[13] ZHANG Y B，ZHANG Q Y，LI Z Y，et al. A k-Anonymous location privacy protection method of dummy based on geographical semantics[ J] . International journal of network security，2019，21（6） ：937-946.

[14] 張學軍， 楊昊英， 李楨， 等. 融合語義位置的差分私 有位置隱私保護方法[ J]. 計算機科學， 2021， 48 （8） ： 300-308. ZHANG X J， YANG H Y， LI Z， et al. Differentially private location privacy-preserving scheme with semantic location[ J] . Computer science， 2021， 48（8） ： 300-308.

[15] 楊洋， 胡曉輝， 杜永文. 基于歷史查詢概率的 k -匿名 啞元位置選取 算 法 [ J] . 計 算 機 工 程， 2022， 48（ 2） ： 147-155. YANG Y， HU X H， DU Y W. The k-anonymous dummy location selection algorithm based on historical query probability[ J ] . Computer engineering， 2022， 48 （ 2 ） ： 147-155.

[16] 宋成， 金彤， 倪水平， 等. 一種面向移動終端的 K 匿 名位置隱私保護方案[ J]. 西安電子科技大學學報， 2021， 48（3） ： 138-145. SONG C， JIN T， NI S P， et al. K-anonymous location privacy protection scheme for the mobile terminal [ J ] . Journal of xidian university， 2021， 48（3） ： 138-145.

[17] HUANG G L， DENG K， XIE Z J， et al. Intelligent pseudo-location recommendation for protecting personal location privacy[ EB / OL] . （ 2019-07-05） [ 2023-10-15] . https：∥onlinelibrary. wiley. com / doi / 10. 1002 / cpe. 5435.

[18] 倪巍偉， 馮志剛， 閆冬. 基于路網環分布的隱私保護 近鄰查詢方法[ J] . 計算機學報， 2020， 43（8） ： 1385- 1396. NI W W， FENG Z G， YAN D. Location privacy preserving nearest neighbor query method based on circle distribution on road networks[ J] . Chinese journal of computers， 2020， 43（8） ： 1385-1396.

[ 19] BRADEN B. The surveyor′s area formula[ J] . The college mathematics journal，1986，17（4） ：326-337.

[ 20] ZHENG Y，XIE X，Ma W Y. GeoLife： a collaborative social networking service among user， location and trajectory [ J ] . Bulletin of the IEEE computer society technical committee on data engineering，2010，33（2） ：32-39.