基于用戶相關性的差分隱私軌跡隱私保護方案

摘 要：在使用位置查詢服務時需要提供用戶真實位置信息，導致用戶信息泄露。大部分研究只針對單個用戶的隱私保護，而忽略了多用戶之間的相關性。針對軌跡隱私保護中多用戶相關性的問題，提出了一種基于用戶相關性的差分隱私軌跡隱私保護方案。首先，構建歷史軌跡樹，利用變階馬爾可夫模型預測用戶軌跡，從軌跡集合中生成一組高可用性的軌跡數據集；其次，根據用戶軌跡之間的相關性獲取一組關聯性較低的預測軌跡集；最后，通過自定義隱私預算的方法，根據用戶不同的隱私需求動態調整每個位置點的隱私預算并為發布軌跡添加拉普拉斯噪聲。實驗結果表明：與LPADP算法相比，該算法的執行效率提升了10%～15.9%；與PTPP和LPADP算法相比，該算法的數據可用性提升了11%～16.1%，同時提升了隱私保護程度。

關鍵詞：位置隱私；軌跡隱私保護；差分隱私；變階馬爾可夫模型

中圖分類號：TP309.2 文獻標志碼：A 文章編號：1001-3695（2024）07-038-2189-06

doi： 10.19734/j.issn.1001-3695.2023.10.0539

Differential privacy trajectory privacy protection scheme based on user correlation

Abstract： When using location-based services， users need to provide their real location information， which may lead to the leakage of user information. Most research only focuses on the privacy protection of individual users， while ignoring the correlation among multiple users. This paper proposed a differential privacy trajectory protection scheme based on user correlation for trajectory privacy protection issues involving multiple users. Firstly， it constructed a historical trajectory tree and used a variable-order Markov model to predict user trajectories， generating a set of highly usable trajectory datasets from the collection of trajectories. Secondly， it obtained a set of predicted trajectories with lower correlation based on the inter-user trajectory correlations. Finally， by customizing the privacy budget method， it dynamically adjusted the privacy budget for each location point according to different user privacy needs and added Laplacian noise to the published trajectories. Experimental results show that compared to the LPADP algorithm， this algorithm improves execution efficiency by 10%～15.9%. Compared to both PTPP and LPADP algorithms， it enhances data usability by 11%～16.1%， while also increasing the level of privacy protection.

Key words：location privacy; trajectory privacy protection; differential privacy; variable-order Markov model

0 引言

近年來，隨著互聯網技術、GPS技術和移動設備的飛速發展，基于位置的服務（location-based service，LBS）已經被廣泛應用于人們的生活中［1］。以用戶日常使用較為廣泛的移動導航為例，用戶將自己的位置信息發送給位置服務提供商來獲取所需的信息。然而服務商在向用戶提供服務的同時，也會收集大量的用戶位置和軌跡信息。

服務商在接收大量用戶數據后，會分析不同用戶之間的相關性，這些相關性表現為共同愛好、工作地點等［2］，而且服務商并不總是可信的，自身服務器漏洞或者遭受黑客攻擊后，可能會導致用戶的位置信息泄露［3， 4］。服務商通過分析位置數據可以推斷出用戶的敏感信息，如家庭狀況、工作地址和身份信息等。因此，保護位置隱私對用戶的日常生活非常重要。

現在的軌跡隱私保護方法大多針對單一用戶的軌跡隱私保護，而忽略了用戶之間的相關性。圖1為三個用戶某次出行的軌跡信息，攻擊者經過分析得知他們經常一起去圖書館和電影院，攻擊者就可以根據他們對三個用戶的先驗知識來確認他們的社會關系。所以，這種軌跡的相互關聯應該被隱藏起來，以保護用戶之間的社交關系，從而保護他們的隱私。

如果只考慮單一軌跡的隱私保護或只考慮兩個用戶間的相關性，有很大的局限性，攻擊者可以通過分析其余相關用戶的軌跡信息，進而分析出需要保護的用戶軌跡。因此，對用戶軌跡信息的保護，不僅要保護用戶的基本位置信息，更要保護用戶軌跡之間的相關性。針對這個問題，本文提出了一種基于用戶相關性的差分隱私軌跡隱私保護方案（multi-user differential privacy，MUDP），考慮多個用戶之間的相關性，通過變階馬爾可夫模型預測用戶的軌跡，然后構建軌跡樹優化算法的執行效率，根據軌跡間的歐氏距離度量軌跡之間的相關性，確定需要保護的軌跡。最后，針對不同位置的隱私需求，合理分配隱私預算。本文算法可以在保證數據可用性的前提下，保護用戶之間的社交關系。本文的主要貢獻如下：

a）針對不同用戶之間的軌跡關聯問題，提出了一種基于差分隱私的軌跡保護方案MUDP，考慮多用戶之間的相關性，提高了隱私保護強度。

b）根據歷史數據建立軌跡樹，同時采用變階馬爾可夫模型動態預測軌跡，提高了查詢效率和模型預測的準確性。

c）個性化分配隱私預算，根據用戶不同的隱私需求動態分配隱私預算，提高了發布軌跡的可用性。

1 相關工作

目前的研究者們針對用戶的軌跡隱私保護提出了一些解決方案，這些方案大致可以分為基于扭曲技術、基于加密技術、基于匿名技術［5］。但是這些方法在面對對手的背景知識攻擊、組合攻擊時，仍無法保證用戶的隱私安全［6］。為了應對上述問題，差分隱私技術被開發出來。差分隱私具有良好的隱私保護強度，是目前主流的隱私保護技術。Dwork［7］在2006年提出了差分隱私的概念，它要求修改單個記錄對查詢結果的影響可以忽略不計。

1.1 針對單一用戶的軌跡隱私保護方案

如今，大部分關于軌跡隱私保護的方案只針對單一用戶軌跡隱私保護問題， Zhang等人［8］通過語義分析為軌跡中的位置點分配隱私級別，并根據隱私級別分配相應的隱私預算，從而平衡隱私和效用。Kou等人［9］設計了一種位置隱私保護算法，提出了一種基于差分隱私的傳感器網絡位置隱私保護方案，在增加噪聲的同時保證了數據的實用性。Bi等人［10］將邊緣節點分布到構造的對應網格中，利用LDP對每個網格的原始位置數據進行擾動，但是該方法對資源的消耗量較大。Xu等人［11］提出了一種基于軌跡分割的方法。其根據位置點的時間關系將用戶軌跡劃分為段，然后將軌跡段劃分為不同的等價類，最后用它們構建軌跡圖和對應的匿名集，增大了軌跡的匿名效率。Wu等人［12］對用戶之間的聯系進行了研究，采用卡爾曼濾波器對用戶軌跡進行預測和修正，最后根據敏感位置添加隱私預算。Qian等人［13］提出了一種基于軌跡相關度的算法，在假位置替換算法的基礎上添加了基于軌跡前綴樹的差分隱私算法，將原始軌跡替換為區間內最優的偽軌跡，然后建立前綴樹，對位置頻率添加噪聲，達到了對軌跡數據集雙重保護的效果，但是沒有考慮軌跡的時空特性，數據可用性稍差。上述方案針對單一用戶的軌跡隱私保護都有很好的效果，然而，這些方法都忽略了用戶之間的相關性，導致隱私泄露問題。

1.2 針對兩個用戶間相關性的軌跡隱私保護方案

目前針對用戶相關性的研究大多只局限于兩個用戶之間的相關性研究。Ou等人［14］通過隱馬爾可夫模型的相似性來量化兩個用戶之間的位置相關性，可以保留一段時間內用戶之間的位置相關性。Wang等人［15］針對空間眾包場景下的軌跡安全發布問題，設計了一種基于差分隱私的隱私保護機制，能夠準確預測每個區間的位置，自適應分配所需的隱私預算，保持軌跡內的時間相關性，實時安全地發布軌跡。Ou等人［16］提出了基于拉格朗日乘數的差分隱私（LMDP）方法來優化隱私預算，通過定義軌跡相關性分數來衡量兩個用戶之間的社會關系。上述研究僅局限于兩個用戶之間的相關性隱私保護，不適用于多用戶之間的隱私保護。目前，關于多軌跡間相關性隱私保護的研究還沒有得到很好的研究。由于社交關系的泄露會對用戶產生巨大的影響，這是一個急需解決的問題。

上述研究都沒有全面、多角度地考慮用戶之間的相關性對軌跡隱私保護的影響，只有部分研究體現了兩用戶間相關性的衡量方式，無法保證多用戶間相關性和用戶個性化的隱私保護需求。因此，本文提出了一種基于多用戶間相關性的個性化軌跡隱私保護算法，利用變階馬爾可夫模型預測用戶軌跡，增強數據可用性的同時保護用戶間的相關性。

2 相關定義

本章介紹本文涉及的基本概念，所用符號如表1所示。

定義1 敏感位置點。包含用戶個人信息較多的位置點稱為用戶敏感位置點。將敏感位置點的集合定義為SL={sl1，sl2，…，sln}，將用戶設定的敏感位置隱私級別表示為PL={pl1，pl2，…，pln}，其中pli∈（0，1）。

定義2 用戶軌跡。當前位置點由經緯度坐標和時間組成，記作l=（loi，lai），其中loi和lai分別代表用戶在i時位置的經度和緯度坐標。用戶軌跡T是由一系列位置點組成的集合，可表示為T={l1，l2，…，ln}，其中n表示軌跡點的個數。

定義3 ε-差分隱私。給定鄰近數據集D和D′，查詢算法M，若算法M在數據集D和D′的任意輸出結果O滿足式（1），則稱該算法滿足差分隱私。

其中：ε為隱私預算，表示隱私保護度，ε越小則隱私保護度越高。

其中：D和D′表示有且僅有一條不同數據的相鄰數據集；‖f（D）－f（D′）‖1表示一階范數距離。

常用的差分隱私保護機制有拉普拉斯機制和指數機制，其中拉普拉斯機制主要用于數值型數據，指數機制主要用于非數值型數據，本文采用拉普拉斯機制添加噪聲。

定義6 軌跡距離。軌跡間的距離用位置點間的平均距離表示，定義如下：

兩條軌跡長度必須相同且定位點相互對應。其中dis（lai，lbi）表示用戶a和b在當前位置點的距離，ω表示位置點的個數。

定義7 變階馬爾可夫模型。馬爾可夫模型可以預測用戶未來可能的位置，而對于m階馬爾可夫模型，用戶的下一個發生時刻位置由前m個位置決定，可用公式表示為

Pr（ln+1|ln，ln－1，…，l1）=

Pr（ln+1|ln，ln－1，…，ln－m+1）（5）

其中：（ln－m+1，…，ln）在統計樣本中出現的概率為

Pr（ln－m+1，…，ln）=Pr（ln－m+1）Pr（ln－m+2|ln－m+1）…Pr（ln|ln－m+1，…，ln－1） （6）

當m=1時，構成標準形式馬爾可夫模型。由式（6）可知，當軌跡長度不滿足階數時，無法預測下一個位置，此時通過降階進行預測，直到降至一階。這樣既能體現變階馬爾可夫模型的靈活性，又能保證預測效率。

3 方案設計

3.1 系統架構

本文系統架構如圖2所示，由用戶、可信第三方服務器（trusted third party，TTP）和LBS提供商三部分組成。TTP位于用戶和LBS服務器之間，用于防止不可信LBS收集用戶信息。本文中TTP的主要作用是收集并處理用戶原始位置信息，將處理后的用戶信息反饋給LBS服務器。LBS無法通過處理后的信息獲取用戶當前位置信息。

3.2 威脅模型

本文假設位置服務提供商不可信，當其數據庫受到惡意攻擊者攻擊時，用戶的軌跡數據等信息可能被泄露。本方案的威脅模型如圖3所示。

用戶通過GPS等定位服務獲取自身位置信息，并將軌跡數據發送到TTP服務器進行處理，處理后的數據從位置服務提供商處獲取服務。幾乎所有的LBS提供商都會搜集用戶的個人數據，如位置信息、身份信息、興趣愛好等，攻擊者通過攻擊TTP服務器或直接攻擊位置服務提供商后獲取用戶各種信息，導致用戶的隱私泄露。

3.3 MUDP軌跡隱私保護算法

MUDP算法首先根據TTP中的歷史軌跡構建軌跡樹，當用戶發起查詢請求時，根據用戶原始軌跡構建預測軌跡集合，然后通過相關度閾值θ判斷不同用戶間的軌跡相關度。

如圖4所示，若不存在相關用戶，則根據預測軌跡集構建相鄰軌跡集，根據用戶不同的隱私需求分配隱私預算并發布軌跡；若存在相關用戶，即兩用戶間的相關度大于θ，則兩用戶為相關用戶，這時需要保護用戶間的相關性。根據變階馬爾可夫模型預測用戶軌跡，得到用戶軌跡預測集PT。經過模型預測后，根據相似度SIM值判斷不同用戶之間的相關度，得到用戶預測軌跡保存集PTS。最后，根據用戶不同的隱私需求分配隱私預算并發布軌跡。

算法1 MUDP軌跡隱私保護算法

上述算法中：第1行利用變階馬爾可夫模型得到當前用戶的預測軌跡集；第2行獲取相關用戶軌跡；第3～13行基于第2行計算結果Da非空，這時從相關用戶預測軌跡中選出符合要求的關聯軌跡集，之后根據相關性閾值獲得相關性較低的軌跡，最后構建相鄰數據集，為發布軌跡添加拉普拉斯噪聲后發布；第14～18行基于第2行計算結果Da為空，這時無相關用戶軌跡，需根據當前用戶預測軌跡構建相鄰數據集，從預測軌跡保存候選集中選出的發布軌跡，然后為發布軌跡添加拉普拉斯噪聲后發布。

3.4 軌跡預測

構建一個最大m階的軌跡樹TT，軌跡樹的最大深度為m+1。樹中每個分支代表服務器中的一條歷史軌跡，根節點只存儲歷史軌跡的總條數，除根節點外，每個子節點由一個位置點和位置點出現的次數組成。假設用戶的歷史移動軌跡如表2所示。

根據服務器中存在的歷史軌跡構建出軌跡樹，如圖5所示。

當用戶發起請求時，通過部分匹配算法依次在軌跡樹TT中匹配用戶當前軌跡。從起始位置點開始，使用變階馬爾可夫模型預測用戶下一位置點。如果對應的軌跡能夠在TT中匹配，則使用當前階數的馬爾可夫模型進行預測，并將所有可能的結果存儲在位置候選Z′中。m階預測完成后，如果匹配到對應位置，則根據真實位置預測下一位置點;否則，刪除與用戶當前位置時間間隔最長的位置后重新匹配。重復上述步驟，直到生成所有預測位置點。之后將Z′中的位置點連接，獲得預測軌跡組成的集合PT。PT可以表示為

PT={PT1，PT2，…，PTk}

PTi={li1，li2，…，lin}

其中：lin表示用戶i在時間n時所在的位置點；PTi表示某一條預測軌跡。

算法2 變階馬爾可夫軌跡預測算法

3.5 獲取關聯軌跡

由定義6求出兩條軌跡之間的歐氏距離，若已知用戶a和b的兩條軌跡分別為Ta和Tb，如果Tdis（Ta，Tb）<θ，則表示兩條軌跡之間存在關聯性，其中θ表示距離閾值。將軌跡數據庫D={Ta，Tb，…，Tn}中所有符合Tdis（Ta，Tb）<θ的軌跡存入集合Da中，Da表示用戶a的關聯軌跡集合。

3.6 獲取關聯數據集

已知兩個用戶a和b經過變階馬爾可夫模型的預測后得到的預測軌跡集分別為PTa和PTb，且兩用戶真實軌跡間的距離Tdis（Ta，Tb）<θ，則軌跡相關性計算公式表示為

其中：Lcov（lai，lbi）表示在i時刻兩用戶的位置協方差；Lvar（lai）表示在i時刻用戶a的位置方差。

獲取用戶間的軌跡相關度SIM值后根據SIM值大小判斷預測軌跡的相關性。相關性閾值為λ，當SIM<λ時，兩預測軌跡集相關性低，則可將兩預測軌跡集保存在用戶預測軌跡保存集PTS中；若SIM≥λ，則需在PTa和PTb中篩選其中LSIM<λ的軌跡，這時用戶預測軌跡保存集PTSa可表示為

PTSa=PTa－DLSIMab≥λ（9）

其中：DLSIMab≥λ表示用戶a的預測軌跡集中與用戶b相關度高的軌跡。

上文構建的軌跡保存集中包含用戶的真實軌跡RT，則預測軌跡保存候選集可表示為

PTPa=PTSa－RTa（10）

兩集合間相差一條數據，即真實軌跡RT，可以構成相鄰數據集。

3.7 軌跡發布

假設用戶自定義敏感位置集為SL，對應隱私級別集為PL，根據用戶定義的敏感位置構建的Voronoi圖如圖6所示。Voronoi圖中，用戶當前所在位置到每個單元格中心點的距離小于到達其他單元格中心的距離。由此可以通過單元格中心（敏感位置）的隱私級別計算出用戶當前位置的隱私級別。

如圖6所示，用戶的某條出行軌跡為：從住宅區域出發經過政府到達公司。假設用戶當前位置為v，用戶附近敏感位置集為A，p為A中的元素，p的隱私級別為PLp，則當前位置的隱私級別可以表示為

其中：dis（p，v）表示p和v之間的歐氏距離；A={dis（p，v）<r}，r為用戶設定的隱私范圍閾值。由式（11）可知，距離敏感位置越近，隱私級別越高。

計算出每個位置點的隱私級別之后，為每個位置點分配隱私權重。隱私等級越高的位置，需要更高級別的隱私保護，而差分隱私中隱私預算和隱私保護水平成負相關。由此，可以得到隱私預算分配公式：

根據式（12）循環計算每個位置的隱私預算，從PTP中選出一條軌跡作為發布軌跡，為每個位置添加拉普拉斯噪聲后發布。

算法3 個性化差分隱私加噪算法

3.8 安全性分析

證明1 個性化差分隱私加噪算法中添加拉普拉斯噪聲滿足差分隱私。

拉普拉斯噪聲是滿足拉普拉斯分布的隨機值的集合，其基本原理是在數據中加入服從Lap（Δf/ε） 的噪聲，使加入噪聲后的數據滿足差分隱私。

在算法3中加入拉普拉斯噪聲，滿足差分隱私，證明過程如下：

相鄰數據集PTP和PTS分別記為D1和D2，其輸出軌跡為O，則有

證明2 MUDP算法保護了不同用戶之間的軌跡相關性。

假設用戶a的真實軌跡為RTa，用戶b的真實軌跡為RTb，其中RTa，RTb∈PTS，經過MUDP算法處理后的發布軌跡OT∈PTP，攻擊者的先驗概率為Pr（RT），后驗概率為Pr（RT|OT），則有

攻擊者無法區分用戶a和b，隱藏了用戶間的相關性，因此，保護了用戶之間的相關性。

4 實驗

為了驗證本方案的可用性，采用真實數據集T-drive［17］和 Shanghai Taxi［18］。T-Driver數據集包含 2008年2月2日至2月8日北京市內10 357輛出租車的 GPS軌跡，采樣時間在30～300 s不等，平均采樣時間為177 s。Shanghai Taxi數據集包含 5 000輛公共汽車和出租車的軌跡數據，平均采樣時間為60 s。這些軌跡數據集都由一個個數據序列組成，每個數據都包含車輛代碼、時間戳和經緯度等信息。為了降低軌跡樹的復雜度，剔除了一些日常生活之外的軌跡，如出差、旅行等，選擇較為密集的軌跡作為實驗數據。

實驗使用Python 3.8對本文方法進行仿真實驗，編程環境為PyCharm，實驗環境為Windows 10操作系統，內存空間為16 GB，處理器為AMD Ryzen 7 4800U。與基于差分隱私的PTPP［19］和LPADP［20］算法進行對比分析實驗。PTPP算法基于地理不可區分性，根據用戶之間關系的強度來控制隱私預算。LPADP算法根據位置數據的檢索難度構造位置隱私樹（LPT），為LPT預測值最大的兩個節點分配合理的隱私預算，并加入拉普拉斯噪聲對位置隱私進行保護。本文將從算法運行時間、數據可用性和隱私保護度三個方面對算法進行分析。每組實驗共進行10次，取所有結果的平均值作為最終結果。

4.1 算法運行時間

算法的運行時間影響算法的效率。在其他條件相同的情況下，算法運行時間越短，算法的執行效率越高。執行效率越高的算法，其執行時間越短，對服務器的運算要求越低。

首先分析軌跡長度對算法運行時間的影響，由圖7可知，MUDP算法在軌跡長度較短時運行時間長于PTPP算法，原因在于MUDP算法需要構建相關軌跡集處理相關用戶的軌跡，故軌跡長度較短時的算法運行時間較長，而隨著軌跡長度的增加，MUDP算法只需在軌跡樹中查找位置點，在軌跡長度達到70時算法運行時間和PTPP算法持平。MUDP算法采用變階馬爾可夫模型，當軌跡長度不滿足階數時降階，與采用標準馬爾可夫模型的LPADP算法相比，節約了算法的運行時間，在軌跡長度為20～100時的運行時間均優于LPADP算法。

另外，分析敏感位置個數對算法運行時間的影響，為了便于分析敏感位置個數對算法運行時間的影響，取用戶的位置敏感度PL=0.4。由圖8可知，MUDP算法的平均運行時間優于PTPP算法，在PTPP算法中隨著敏感位置個數的增加，需要遍歷的位置數量也隨之增加，因此需要消耗更多的時間。MUDP算法中構建了軌跡樹TT，只需要預測軌跡位置和添加噪聲，因此表現出更高的運算效率。而LPADP算法只保護預測值最大的兩個節點，未考慮敏感位置的影響，因此敏感位置個數對其影響較小。算法在T-Driver數據集上的運行時間高于Shanghai Taxi數據集，這是由于T-Driver數據集的劃分區域比Shanghai Taxi數據集更詳細。

4.2 數據可用性

本文采用真實位置與生成位置之間的平均誤差（AE）來衡量軌跡的可用性。假設真實軌跡位置集和最終發布軌跡分別為T和O，T中的元素為li，O中的元素為Oi，則將AE定義為

其中：dis（li，Oi）代表li和Oi之間的歐氏距離。顯然，AE越大，數據可用性越差。

首先分析敏感位置個數對數據可用性的影響，設定PL的值為0.5，每組實驗運行10次，取平均值作為結果。如圖9所示，隨著敏感位置個數的增加，用戶所在位置的敏感度隨之增加，由于添加了更多噪聲，導致位置偏差更大，從而使數據可用性降低。在MUDP算法中，添加噪聲時優化了不同位置的隱私預算的分配方式，數據可用性表現相對更優，剩余兩種算法未針對用戶需求合理分配隱私預算，因此，數據可用性稍差。

為了驗證不同隱私預算下AE的大小，將隱私預算設置為0.2～1.4，分別測試不同算法在不同隱私預算下的AE值，分析算法的可用性。每個實驗進行10次，取其平均值作為實驗結果。

如圖10所示，x軸為隱私預算，y軸為AE值。三種算法的AE均隨著隱私預算ε的增大而增大，這是因為隱私預算越大，添加的擾動噪聲越小，導致數據可用性變差。T-Driver數據集AE的平均值大于Shanghai Taxi數據集，這是因為T-Driver數據集的采樣時間不同，數據穩定性較差，導致數據可用性降低。實驗結果表明，本文算法的數據可用性優于其余兩種算法。在隱私預算較小的情況下，PTPP雖然可以通過擾動位置提供一定的隱私保護，但增加的噪聲過大，導致數據可用性過低，而LPADP算法未優化隱私預算分配方式，導致數據可用性波動過大。與之相比，本文算法針對用戶不同的隱私需求分配隱私預算，數據可用性表現更佳。

為了分析預測算法的準確性，將本文所使用的變階馬爾可夫模型與標準馬爾可夫模型、軌跡挖掘模型［21］進行對比，實驗結果如圖11所示。

從算法運行時間分析，變階馬爾可夫模型與標準馬爾可夫模型在軌跡長度4 000以下時，運行時間接近，隨著歷史軌跡數量的增加，變階馬爾可夫模型的運行時間表現更優，原因在于變階馬爾可夫模型相比標準馬爾可夫模型優化了算法的執行效率，在軌跡長度滿足階數時，可以直接預測，無須循環遍歷，而軌跡挖掘模型運行時間更長；在數據可用性上，變階馬爾可夫和標準馬爾可夫模型效果相似。

4.3 隱私保護度

本節分析不同隱私預算對隱私保護程度的影響，實驗在T-Driver和Shanghai Taxi數據集下分別進行，實驗結果如圖12所示。

由圖12可知，由于 T-Driver數據集的數據穩定性優于Shanghai Taxi數據集，所以T-Driver數據集上隱私保護程度的平均值優于Shanghai Taxi。隨著隱私預算的增加，兩種隱私保護算法的隱私保護程度都逐漸減小，但MUDP算法的隱私保護程度始終優于其余兩種算法，原因是MUDP算法通過變階馬爾可夫模型生成的軌跡與真實軌跡更接近，同時個性化的隱私預算分配方法使隱私預算的分配更合理，從而在相同隱私預算下有更高的隱私保護程度。

5 結束語

針對不同用戶間軌跡相關性的隱私保護存在的問題，本文提出了一種基于用戶相關性的差分隱私軌跡隱私保護方案，利用變階馬爾可夫模型預測軌跡，解決了馬爾可夫模型軌跡預測誤差大、準確性低的問題；在用戶相關性上，篩選出相關性較高的軌跡進行處理，使攻擊方無法區分相關用戶；最后個性化的隱私預算分配方法，解決了其他方案隱私預算分配不合理、添加噪聲過大的問題。接下來的研究工作，將針對隱私預算的分配和算法的執行效率作進一步深入研究，進而提高本文方法的數據可用性和執行效率。

參考文獻：

［1］Parmar D，Rao U P. Towards privacy-preserving dummy generation in location-based services ［J］. Procedia Computer Science，2020，171： 1323-1326.

［2］Dootio M A，Lakhan A，Sodhro A H，et al. Secure and failure hybrid delay enabled a lightweight RPC and SHDS schemes in Industry 4. 0 aware IIoHT enabled fog computing ［J］. Mathematical Biosciences and Engineering，2022，19（1）： 513-536.

［3］Peng Tao，Liu Qin，Wang Guojun. Enhanced location privacy preserving scheme in location-based services ［J］. IEEE Systems Journal，2014，11（1）： 219-230.

［4］Gursoy M E，Liu Ling，Truex S，et al. Differentially private and utility preserving publication of trajectory data ［J］. IEEE Trans on Mobile Computing，2018，18（10）： 2315-2329.

［5］張青云，張興，李萬杰，等. 基于LBS系統的位置軌跡隱私保護技術綜述 ［J］. 計算機應用研究，2020，37（12）： 3534-3544.（Zhang Qingyun，Zhang Xing，Li Wanjie，et al. Overview of location trajectory privacy protection technology based on LBS system ［J］. Application Research of Computers，2020，37（12）： 3534-3544.）

［6］Bolton T，Dargahi T，Belguith S，et al. On the security and privacy challenges of virtual assistants ［J］. Sensors，2021，21（7）： 2312.

［7］Dwork C. Differential privacy ［C］// Proc of the 33rd International Colloquium on Automata，Languages and Programming. Berlin： Springer-Verlag，2006： 1-12.

［8］Zhang Jing，Li Yanzi，Qian Ding，et al. Successive trajectory privacy protection with semantics prediction differential privacy［J］. Entropy，2022，24（9）： 1172.

［9］Kou Kaiqiang，Liu Zhaobin，Ye Hong，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.

［10］Bi Mengnan，Wang Yingjie，Cai Zhipeng，et al. A privacy-preserving mechanism based on local differential privacy in edge computing ［J］. China Communications，2020，17（9）： 50-65.

［11］Xu Jiuyun，Liu Lele，Zhang Ruru，et al. IFTS： a location privacy protection method based on initial and final trajectory segments ［J］. IEEE Access，2021，9： 18112-18122.

［12］Wu Lei，Qin Chengyi，Xu Zihui，et al. TCPP： achieving privacy-preserving trajectory correlation with differential privacy ［J］. IEEE Trans on Information Forensics and Security，2023，18： 4006-4020.

［13］Qian Kun，Li Xiaohui. LBS user location privacy protection scheme based on trajectory similarity ［J］. Scientific Reports，2022，12（1）： 1-12.

［14］Ou Lu，Qin Zheng，Liu Yonghe，et al. Multi-user location correlation protection with differential privacy ［C］// Proc of the 22nd IEEE International Conference on Parallel and Distributed Systems. Piscata-way，NJ： IEEE Press，2016： 422-429.

［15］Wang Qian，Zhang Yan，Lu Xiao，et al. Real-time and spatio-temporal crowd-sourced social network data publishing with differential privacy ［J］. IEEE Trans on Dependable and Secure Computing，2016，15（4）： 591-606.

［16］Ou Lu，Qin Zheng，Liao Shaolin，et al. Releasing correlated trajectories： towards high utility and optimal differential privacy ［J］. IEEE Trans on Dependable and Secure Computing，2018，17（5）： 1109-1123.

［17］Yuan Jing，Zheng Yu，Zhang Chengyang，et al. T-drive： driving directions based on taxi trajectories［C］// Proc of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York： ACM Press，2010：99-108.

［18］Ma Zhuo，Zhang Tian，Liu Ximeng，et al. Real-time privacy-preserving data release over vehicle trajectory ［J］. IEEE Trans on Vehicu-lar Technology，2019，68（8）： 8091-8102.

［19］Li Jiachun，Chen Guoqian. A personalized trajectory privacy protection method ［J］. Computers & Security，2021，108： 102323.

［20］Li Hongtao，Wang Yue，Guo Feng，et al. Differential privacy location protection method based on the Markov model ［EB/OL］.（2021-07-01）. https：//doi.org/10.1155/2021/4696455.

［21］Pan Xiaoying，Zhao Qian，Zhao Pu. Frequent trajectory of pattern mining with spatio-temporal attribute and relationship label ［J］. Computer Engineering and Applications，2019，55（10）： 83-89.