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

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

中圖分類號：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 引言

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

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

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

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

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

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

c）個性化分配隱私預(yù)算，根據(jù)用戶不同的隱私需求動態(tài)分配隱私預(yù)算，提高了發(fā)布軌跡的可用性。

1 相關(guān)工作

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

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

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

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

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

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

2 相關(guān)定義

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

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

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

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

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

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

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

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

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

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

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

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

其中：（ln－m+1，…，ln）在統(tǒng)計樣本中出現(xiàn)的概率為

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時，構(gòu)成標準形式馬爾可夫模型。由式（6）可知，當軌跡長度不滿足階數(shù)時，無法預(yù)測下一個位置，此時通過降階進行預(yù)測，直到降至一階。這樣既能體現(xiàn)變階馬爾可夫模型的靈活性，又能保證預(yù)測效率。

3 方案設(shè)計

3.1 系統(tǒng)架構(gòu)

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

3.2 威脅模型

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

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

3.3 MUDP軌跡隱私保護算法

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

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

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

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

3.4 軌跡預(yù)測

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

根據(jù)服務(wù)器中存在的歷史軌跡構(gòu)建出軌跡樹，如圖5所示。

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

PT={PT1，PT2，…，PTk}

PTi={li1，li2，…，lin}

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

算法2 變階馬爾可夫軌跡預(yù)測算法

3.5 獲取關(guān)聯(lián)軌跡

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

3.6 獲取關(guān)聯(lián)數(shù)據(jù)集

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

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

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

PTSa=PTa－DLSIMab≥λ（9）

其中：DLSIMab≥λ表示用戶a的預(yù)測軌跡集中與用戶b相關(guān)度高的軌跡。

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

PTPa=PTSa－RTa（10）

兩集合間相差一條數(shù)據(jù)，即真實軌跡RT，可以構(gòu)成相鄰數(shù)據(jù)集。

3.7 軌跡發(fā)布

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

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

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

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

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

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

3.8 安全性分析

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

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

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

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

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

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

攻擊者無法區(qū)分用戶a和b，隱藏了用戶間的相關(guān)性，因此，保護了用戶之間的相關(guān)性。

4 實驗

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

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

4.1 算法運行時間

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

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

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

4.2 數(shù)據(jù)可用性

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

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

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

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

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

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

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

4.3 隱私保護度

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

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

5 結(jié)束語

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

參考文獻：

［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系統(tǒng)的位置軌跡隱私保護技術(shù)綜述 ［J］. 計算機應(yīng)用研究，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.