一種滿足差分隱私的軌跡數據安全存儲和發布方法

吳萬青 趙永新 王 巧 底超凡

(河北大學網絡空間安全與計算機學院 河北保定 071000) (河北省高可信信息系統重點實驗室(河北大學) 河北保定 071000) (wuwanqing8888@126.com)

隨著互聯網的快速發展，許多電子設備融入現實生活，例如智能手機、智能手環等.但是在享受大數據便利的同時，也面臨著隱私安全隱患.一些基于位置服務(location based services, LBS)應用軟件在用戶未知情的情況下，采集用戶的地理位置信息并發布，不僅造成用戶的位置隱私泄露，而且有可能造成更多的敏感信息泄露，如用戶的生活習慣、宗教信仰等.據微軟統計報告，有一半以上的用戶擔心自己在使用基于LBS的應用程序時泄露自己的隱私.因此在用戶使用LBS時，如何實現位置軌跡數據的安全分享與發布，保護用戶的個人隱私成為一個重要問題.

為解決位置隱私保護這一問題，國內外許多學者紛紛置身于此問題之中.2002年Sweeney等人提出K-匿名理論[1].文獻[1]中定義了偽標識符和K-匿名性，廣泛應用于軌跡匿名和隱私保護.2003年Gruteser等人將K-匿名的理論引入到位置隱私保護，提出一種空間位置隱藏方法[2].該方法的思想是通過空間隱藏方法隱藏單個用戶與其他K-1個用戶的地理位置使之無法區分，但是這種方法必須在特定情形下才能實現，所以用戶不能根據自己的需求設置不同K值和需要隱藏的區域.2009年Chow等人提出一種個性化K-匿名模型[3]，該方法是基于用戶出現在隱藏區域相等的概率下提出的一種模型，但當用戶出現的概率不等時，該模型不能很好地反映用戶隱私的保護程度.

許多學者基于K-匿名模型，相繼提出了K-匿名模型的變體.2006年Wang等人提出(X,Y)-匿名的概念，其中X，Y表示2個不相交的屬性集合[4].該方法主要在處理敏感數據時增加了限制條件，在屬性組X中屬性相同的情況下，每一組X均需要對應至少K個不同敏感屬性組Y中的值.2007年Zhang等人提出了(K,e)-匿名模型，目的處理敏感數值型數據，其思想為在每個等價類中元組個數不能低于K個，每個等價類中的敏感屬性的取值范圍不能低于給定的閾值e[5].Machanavajjhala等人在2007年提出l-多樣化模型[6]，這一方法是通過熵值定義數據的多樣性及變化特征，要求在準標識符相同的情況下，敏感數據滿足一定的多樣化要求，保證了敏感數據的多樣性，但是敏感數據如何分布該方法并未考慮.而t-貼近模型的提出解決了這一問題[7-8].t-貼近模型定義了一個閾值t，并要求等價類中敏感屬性的分布和整個表的敏感屬性分布的距離不能超過閾值t.

K-匿名模型優勢在于攻擊者能力不超過假設的前提下，能夠以較小的代價保證同一等價類中記錄的不可區分性，但當攻擊者能力超過假設范疇，攻擊者就可以進一步區分等價類中不同的記錄，從而實現去匿名化，造成背景知識攻擊.l-多樣化模型雖然在一定程度上處理了K-匿名缺乏多樣性的問題，但是該模型仍不能抵御概率推理攻擊，若敏感屬性分布不均勻時，導致實現該技術困難.t-貼近模型作為l-多樣化模型的改進，解決了針對敏感屬性的攻擊，但是仍無法抵御背景知識的攻擊，而且面對不同的敏感屬性值時缺乏保護水平的靈活性.

因此，Dwork等人在2006年提出差分隱私技術，很好地解決了背景知識攻擊及推理攻擊的問題[9-10].該方法的主要思想是在數據庫中添加噪聲，達到攻擊者無法識別其中任意一個數據是否在該數據庫中.該技術是一種新的隱私保護技術，具有健強的數學基礎，可以提供嚴謹的數學證明[11].差分隱私技術的提出，受到廣大隱私保護領域研究者的關注，并廣泛應用于支持隱私保護的數據挖掘和數據發布領域[12].2012年Andrés等人提出基于位置的差分隱私擴展模型，并生成一個在隱私預算范圍內不會受攻擊的匿名位置[13].但是由于生成的匿名位置與用戶的真實位置之間的距離無法預測，所以不能保證LBS的服務質量.2013年Dewri等人利用Hilbert分布的匿名集獲得高質量服務[14].但是匿名位置和真實位置沒有相似性，攻擊者很容易區分開.2018年Gursoy等人提出一種名為DP-Star的軌跡隱私保護框架[15].該框架構建了一個密度感知網絡，可以確保添加噪聲之后滿足差分隱私的需求，保持數據的空間密度，并采用中值長度估計方法保護用戶軌跡，生成了既保留了差分隱私性質又高效能地合成軌跡.2019年Deldar等人提出一種稱為PDP-SAG的差分隱私機制[16]，用于解決移動對象的非時空敏感屬性，為了使添加噪聲頻率一致，對個性化差分隱私結構上的屬性噪聲值進行一致處理.

由于軌跡數據具有高維性，不僅包含時間戳信息，也包含位置信息.為了滿足大量軌跡數據存儲與發布，Chen等人在2012年首次提出將差分隱私應用于發布大量順序數據的方案，采用一種基于混合粒度前綴樹結構(SeqPT)存儲軌跡數據[17].在節點計數中加入Laplace噪聲，以確定子樹是否能繼續在相應的節點上繼續增長，并利用前綴樹的固有一致性約束性質進行約束推理.但是時間戳的增多導致樹高也會增高，計算量隨著樹的高度增加而增加，而SeqPT模型并不適用于高維時空數據集.2018年Khalil等人提出一種加噪前綴樹模型[18]，并引入一種稱為SafePath的算法，該算法引入可變高度和等級分類樹改進了SeqPT，減少了空節點生成的可能性.雖然該算法提高了大型和稀疏數據集的效率，但是在處理真正的高維屬性的時空數據時，不僅分類樹會增加隱私預算，而且發布的軌跡數據集的可用性較低.2019年Zhao等人提出一種SR-樹結構代替R樹的最小外界矩形，Cons-SRT算法雖然抵御了非位置敏感信息攻擊，但是由于樹過高導致查詢效率下降[19].

為此，為了處理樹高的增加導致查詢效率下降的問題，本文提出一種基于差分隱私的噪聲前綴樹結構應用于軌跡數據的存儲與發布.本文首先通過軌跡的時間特性以及速度和方向的特征，劃分出不同時間戳的軌跡等價類.其次采用Hilbert曲線對各個軌跡等價類中的位置點進行標號劃分，并計算每個等價類的中心點.然后由前綴樹的節點存儲該中心點，根據移動用戶的軌跡特征，從而獲取軌跡的時空特性，保證了軌跡數據的存儲與發布.最后利用差分隱私技術對節點存儲的敏感數據添加噪聲.

本文的貢獻有3個方面：

1) 不僅考慮軌跡的時間特性,而且通過計算軌跡間的速度距離和方向距離構建軌跡等價類，并提出一種滿足差分隱私性質的軌跡數據發布算法.為防止攻擊者通過軌跡背景知識和上下文信息獲得隱私數據，本文采用差分隱私技術對敏感數據進行加噪.

2) 證明本文提出的隱私保護方案滿足差分隱私性質，并進一步降低了軌跡數據的時間復雜度.

3) 使用真實的數據庫進行試驗，評測本文提出方案的效率和效用.證明文本的方案使得合并軌跡時間更少，并確保軌跡數據的可用性.

1 問題陳述

1.1 軌跡概念

定義1.軌跡.軌跡是指移動對象經過的一系列二維時空點的集合：

T={id,(l1,t1),(l2,t2),…,(l|T|,t|T|)},

(1)

其中，|T|為軌跡軌跡中位置點個數，即軌跡的長度，t1

多條軌跡Ti構成的集合為軌跡集D，表示為D={T1,T2,…,Tn}.

(2)

當pt=0時，軌跡Ti和Tj不是同步軌跡；當pt=100時，軌跡Ti和Tj具有相同的起始和結束時間.我們定義time(Ti,Tj)表示2條軌跡的重疊時間戳，即：

(3)

定義4.軌跡等價類距離矩陣TDM.軌跡等價類距離矩陣為n階對稱矩陣

(4)

其中，dij表示軌跡Ti和Tj的距離.

定義5.離散Fréchet距離[21].設2條曲線A={a1,a2,…,am}，B={b1,b2,…,bn}由多個離散位置點點組成，則2條曲線的序列組合可以表示為L={(a1,b1),(a2,b2),…(am,bn)}，定義L為所有序列對中最大距離.則離散Fréchet距離可以表示為

(5)

定義6.軌跡方向距離[20].2條軌跡Ti和Tj滿足pt>0，我們用disto(Ti,Tj)表示這2條軌跡的方向距離，即：

(6)

定義7.軌跡速度距離[20].2條軌跡Ti和Tj滿足pt>0，我們用distv(Ti,Tj)表示這2條軌跡的速度距離，即：

(7)

定義8.軌跡距離.2條軌跡?Ti,Tj∈D，D為軌跡數據集.當2條軌跡Ti和Tj滿足pt>0，那么軌跡間距離Dist(Ti,Tj)定義為

Dist(Ti,Tj)=δdF(Ti,Tj)+
α×disto(Ti,Tj)+β×distv(Ti,Tj),

其中，disto(Ti,Tj),distv(Ti,Tj)分別由式(6)和式(7)所得，α和β分別代表方向距離和速度距離的權重值，滿足α,β∈[0,1],α+β=1.

1.2 差分隱私

定義9.ε-差分隱私[12].給定數據集D和其相鄰數據集D′(2個數據集中最多相差一條記錄)，函數f的任意輸出S滿足：

Pr[f(D)=S]≤Pr[f(D′)=S]×eε,

(8)

則稱函數f滿足ε-差分隱私，其中隱私預算ε>0.

隱私預算ε表示隱私保護程度，由數據擁有者指定.ε越大，數據可用性越大，提供的隱私保護程度越低;ε越小，數據可用性越小，提供的隱私保護程度越高、相鄰數據集D和D′查詢結果的概率分布越相似，攻擊者更難以判斷數據集中的某一元素.

定義10.全局敏感度[22].設2個相鄰數據集D和D′至多相差一條記錄，函數f:D→Rd的全局敏感度：

(9)

其中，R表示映射空間，d表示函數f輸出的維度.全局敏感度直接影響噪聲添加量，在相同的預算ε下，函數f的全局敏感度越大，添加的噪聲越多，導致數據可用性降低.

定義11.拉普拉斯機制[9].設查詢函數f:D→Rd滿足ε-差分隱私機制，對函數f的輸出添加拉普拉斯噪聲，即

(10)

其中,算法A提供ε-差分隱私保護.產生拉普拉斯噪聲機制的密度函數為

(11)

定義12.序列組合性[23].給定一個數據集D和n個函數f1,f2,…,fn，每個函數fi(1≤i≤n)滿足εi-差分隱私，則函數組合F(f1(D1),f2(D2),…,fn(Dn))滿足∑εi-差分隱私.對于

必有：

(12)

定義13.并行組合性[23].假設Di(1≤i≤n)，是原始數據集D中彼此不相交的子集，對每個子集Di作用一個差分隱私函數fi，其隱私保護參數為εi，函數組合F(f1(D1),f2(D2),…,fn(Dn))提供(maxεi)-差分隱私保護.則稱函數fi在D上的并行組合滿足(maxεi)-差分隱私.

1.3 其他背景知識

前綴樹[17]是哈希樹的一種變體結構，通過對每一層節點進行遍歷，減少不必要的節點比較，從而提高檢索效率.

定義14.前綴樹.一個前綴樹PT的結構可以被定義為PT=(Root,E,V)，其中Root表示前綴樹PT的虛擬根且Root(PT)∈V；E代表前綴樹節點之間邊的集合；V表示前綴樹節點的集合且v∈V.前綴樹中的節點存儲聚合后的軌跡位置點，在前綴樹上同一個父節點下的所有軌跡序列都有相同的前綴.

定義15.Hilbert曲線.Hilbert空間填充曲線是一種無限迂回發展的空間填充曲線[24]，空間填充曲線是指用一條連續的曲線填滿一個封閉的區域.

圖1分別展示了一階、二階的Hilbert曲線圖：

Fig.1 Hilbert curve圖1 Hilbert曲線圖

1.4 攻擊模型

定義16.背景知識和上下文敏感信息攻擊.背景知識通常是關于特定用戶或數據集的相關信息.在一些文獻中如文獻[25]提出的攻擊模型大多屬于背景知識攻擊的范疇，背景知識又稱查詢記錄鏈接攻擊.

表1中給出3個用戶user1,user2,user3的活動軌跡以及出行方式，假設攻擊者通過觀察得到其中一用戶的出行方式Subway，然后與數據集中的記錄建立連接，可得知該用戶user2的出行方式符合條件，從而也可以得到user2的軌跡以及其他相關的敏感信息.

Table 1 The Information of Users

2 滿足差分隱私的軌跡數據發布方案

2.1節介紹原始軌跡數據的預處理；2.2節介紹Hilbert曲線處理軌跡等價類；2.3節提出一個加噪前綴樹的存儲結構；2.4節介紹基于前綴樹的差分隱私保護算法；2.5節介紹了數據的查詢過程；2.6節對提出的算法進行分析.其算法流程圖見圖2.

Fig.2 Flowchart of trajectory data publishing algorithm圖2 軌跡數據發布算法流程圖

2.1 原始軌跡數據預處理

在數據預處理階段，本文需要完成2個步驟：

1) 識別軌跡的起始時間和終止時間.在軌跡數據集中，我們需要識別每條軌跡的起始時間和終止時間來構造軌跡等價類.本文我們設定一個時間閾值Δt作為時間間隔，并規定在該閾值中的軌跡都視為同一個軌跡等價類.例如，設置閾值Δt為10 min，當且僅當起始時間為[9:00,9:10]，終止時間為[10:00,10:10]的所有軌跡視為同一個軌跡等價類.因此存在軌跡等價類中的軌跡滿足pt>0.

2) 構建軌跡等價類.為保證在相同時間段中的軌跡能夠得到隱私保護，本文采用構建軌跡等價類方法，將第一步中的軌跡匿名在同一個匿名集中.考慮到實際場景中，為了減少軌跡數據的損失，可以適當將時間閾值Δt擴大，保證所有的軌跡得到匿名保護.

算法1描述了軌跡數據預處理過程.

算法1.軌跡數據預處理.

輸入：原始軌跡數據集D={T1,T2,…,T|D|},Δt；

輸出：軌跡等價類EC、軌跡等價類距離矩陣TDM、軌跡時間重疊率矩陣PT.

①EC=?，TDM，PT為空矩陣;

② for eachTi∈D

③ ifTi的開始和結束時間在規定范圍內

then

④Ti存入EC，EC={T1,T2,…,Tp}

(p≤n);

⑤ end if

⑥ end for

⑦ forTi,Tj∈EC,i=1:p

⑧ forj=i+1:p

⑨ 利用式(1)和式(6)計算Ti和Tj的pt值及距離Dist(Ti,Tj);

⑩pti,i=tdmi,i=0;

算法1的行①～⑥為構建軌跡等價類，此過程僅判斷每條軌跡是否在規定的范圍內，軌跡數據集中有n條軌跡，則需要判斷n次，因此可以在時間O(n)內完成.行⑦～為構建軌跡等價類的距離矩陣，構造距離矩陣需要計算n(n-1)/2次軌跡間的距離，則此過程可以在時間O(n2)內完成.因此算法1的完成時間在O(n2)內.由于存儲到矩陣TDM和PT中，因此空間復雜度為O(n2).

算法2描述了算法1中行⑨求軌跡間距離Dist(Ti,Tj).

算法2.多特征軌跡距離算法(multi-feature trajectory distance algorithm).

輸入：等價類EC的任意2條軌跡P和Q，P={(x1,y1),(x2,y2),…,(xp,yp)}，Q={(x1,y1),(x2,y2),…,(xq,yq)}，軌跡時間同步率矩陣PT、方向距離權重α和速度距離權重β；

輸出：Dist(P,Q).

①δdF(P,Q)=disto(P,Q)=distv(P,Q)=?;

② 初始化一個p×q矩陣的矩陣C，其元素初始值均為-1;

③ fori=1 top

④ forj=1 toq

⑤ ifci,j>-1

⑥ returnci,j;

⑦ else ifi==0&&j==0

⑧δdF(P,Q)=Euclid(P,Q);

⑨ else ifi>0&&j==0

⑩ 遞歸計算ci-1,j的值，δdF(P,Q)=

max(ci-1,j,Euclid(P,Q));

max(ci,j-1,Euclid(P,Q));

δdF(P,Q)=max(min(ci-1,j,

ci-1,j-1,ci,j-1),Euclid(P,Q));

disto(P,Q);

distv(P,Q);

Dist(P,Q)=δdF(P,Q)+

α×disto(P,Q)+β×distv(P,Q);

通過算法1和算法2完成對軌跡等價類的構建.2.2節介紹軌跡等價類的處理過程.

2.2 處理軌跡等價類

2.2.1 Hilbert曲線軌跡的劃分

1) 通過計算軌跡之間的pt值和軌跡之間的距離Dist(Ti,Tj)，將原始數據集D劃分成不同的軌跡等價類ECi.根據每個等價類ECi位置點集Li，計算各個位置點集Li的Hilbert曲線階數order.

算法3.軌跡劃分算法(DPRD).

輸入：等價類ECi、位置點集合L={L1,L2,…,L|T|}、總隱私預算ε、劃分區域子集中k個位置點；

② 由軌跡等價類ECi得到每個位置點集Li;

④ for each 位置點集Li

⑥ end for

⑦ 生成n條Hilbert曲線;

⑧ for each Hilbert curve

2.2.2 軌跡的聚合

算法4.軌跡的聚合過程(TPOP).

④ for eachT∈D

⑤ for eachLi∈EC

⑦ end for

⑨ end for

⑩ end for

2.3 加噪前綴樹的存儲結構

前綴樹是一種可以用來存儲大量字符串的樹形結構[17]，它的優點可以利用字符串的公共前綴來節省存儲空間，最大限度地減少無謂的字符串比較，提高數據的查詢效率.本節主要介紹前綴樹存儲軌跡數據的操作步驟：

2) 選擇合適的節點.向前綴樹中插入一條新軌跡時，首先從根節點開始向下遍歷，比較要插入軌跡的第1個軌跡點，確定該軌跡點是否存在于第2層的節點中，如果存在就繼續向下遍歷下一層，直到遍歷到某個節點沒有相同前綴的位置點，則在當前節點vi下生成新的子節點vi+1存儲軌跡數據.如果第1個位置點不存在前綴樹中，則生成根節點的子節點，將軌跡的第1個位置點存入到該節點中，然后繼續創建新的節點，將剩下所有的軌跡點依次存入新創建的節點中.最后對所有的位置點做步驟2)中相同的操作，直至所有的位置點存入到前綴樹中.

3) 更新父節點.在前綴樹中，如果子節點中不存在要存入軌跡的第1個位置點，則不需要更新除根節點以外其他節點信息.若插入的軌跡與前綴樹上節點存儲的軌跡有相同的前綴，則需要更新根節點和當前路徑上的所有節點的信息，用于計數通過位置點的所有移動對象.

介紹一個構造前綴樹的例子，如圖3所示:

Fig.3 Prefix tree圖3 前綴樹

Fig.4 Insert a new trajectory in the prefix tree圖4 在前綴樹中插入一條新的軌跡

Fig.5 Insert a new trajectory in the prefix tree圖5 在前綴樹中插入一條新的軌跡

2.4 基于前綴樹的差分隱私保護算法

通過遍歷整個前綴樹可以獲得每條軌跡路徑以及路徑上移動對象的數量，并能判斷出某個區域的密集程度和一些上下文非位置敏感信息.同時考慮到軌跡在時間和空間上的特性，若攻擊者采取背景知識攻擊和推理連接攻擊，很容易獲得移動對象的敏感信息，造成隱私泄露.為保證新軌跡的發布質量和可用性，我們使用前綴樹結構存儲軌跡數據，然后利用差分隱私技術對新軌跡位置點上的原始軌跡數、移動對象的數量等信息添加噪聲，用于保護軌跡數據的隱私性.

算法5.基于前綴樹的差分隱私保護算法(TDPP).

① 創建一個高度為h的前綴樹PT；

③ fori≤h

⑤θi=k×i-1+b;

⑥ for 每一個節點vi的孩子節點vi+1

⑧ ifvi+1.count≤θithen

⑨ 節點vi+1存入到前綴樹PT中;

⑩sum=sum+vi+1.count;

2.5 數據的查詢過程

除根節點外，前綴樹的每個節點存儲一個位置點，從根節點的子節點到葉子節點的路徑構成一條軌跡，因此加噪前綴樹支持對軌跡路徑的查詢.其查詢的具體過程步驟為：

1) 從根節點開始向下訪問包含軌跡位置點的所有節點.取出要查詢軌跡的第1個位置點，然后檢索前綴樹中根節點的子節點是否存儲該位置點.如果該位置點存在，則將節點中的移動對象的噪聲計數值添加到查詢結果中.如果查詢的位置點不存在節點中，則查詢結束.

2) 將要查詢的位置點依次取出，然后根據步驟1)依次檢索位置點是否存在前綴樹的節點中，并將移動對象的噪聲計數值添加到查詢結果中.直至全部位置點檢索完成.

3) 返回所有的查詢結果和計數值總和.

Fig.6 The query process of the prefix tree圖6 前綴樹的查詢過程

2.6 算法分析

本節我們對提出的模型進行隱私性分析和數據可用性分析.

2.6.1 隱私性分析

軌跡隱私保護的衡量標準是通過攻擊者能在發布軌跡集中識別出該軌跡概率的大小.為此我們證明所提出的方案滿足差分隱私性質.

引理1.軌跡區域劃分算法(TRD)在整個軌跡數據集上可以保證|T|×ε-差分隱私.

(13)

根據引理1，我們得到定理1.

定理1.整個方案過程消耗的隱私預算小于等于ε，即ε=εe+εl，本文方案滿足ε-差分隱私保護.

2.6.2 數據的可用性

本文中的數據可用性分析主要分2個階段：軌跡預處理階段以及軌跡數據存儲到前綴樹.因此在軌跡預處理階段中，我們將信息丟失率DOP作為本文衡量數據可用性的標準.當刪除的軌跡數據占等價類中軌跡總數的比值越小，說明數據可用性越高，即：

(14)

其中，nEC表示等價類的數量，mi為每個等價類中所要刪除的軌跡數量.

在軌跡數據存儲到前綴樹階段中，我們引入定義17和18作為數據可用性的衡量標準，在保證數據隱私性的情況下，相對誤差和平均樹高誤差越低，則說明數據的可用性越高.

定義17.相對誤差.對于計數查詢Q，本文采用相對誤差衡量加噪后發布的數據集D′對比于原始數據集D中數據的可利用率[26]：

(15)

其中，thr是一個閾值，用于防止在極小計數查詢的情況下，分母為0，即Q(D)=0.

定義18.平均樹高誤差.對于計數查詢Q，本文采用平均樹高誤差衡量隱私保護后的數據集D′對比于原始數據集D中數據的可用性[27]：

(16)

3 實驗分析

本文采用微軟研究院發布的T-Drives數據庫[28]，該數據集包含一周內10 357輛出租車的軌跡，總位置點約為480萬個.表2為數據集D部分數據的格式，其中路徑編號為移動對象的不同的軌跡，ID為移動對象的標識符，時間戳用于構建軌跡等價類.為驗證本文算法的隱私性和數據的可用性，與Zhao等人提出的NTPT算法[27]進行對照實驗.

Table 2 Partial Data Format of Dataset

本文的實驗環境為Window10，Intel?Xeon?Silver 4214R @ 3.00 GHz，32 GB內存，采用Python和Jupyter NoteBook.

3.1 數據可用性分析

在軌跡預處理部分，本文引入了軌跡的時間特性以及軌跡間的速度距離v和方向距離o，通過計算其軌跡間的距離值，將原始軌跡數據集D劃分成多個時間戳不同的軌跡等價類.

圖7中展示了方向距離的參數α和速度距離參數β分別為(0,1)，(0.4,0.6)，(0.6,0.4)，(1,0)隨著k值增大，信息丟失率的變化趨勢.從圖7可以看出，在相同的k值下，(α,β)=(0,1)或(1,0)的信息丟失率較高于(α,β)=(0.4,0.6)或(0.6,0.4).因為當其中一個參數為0時，其約束條件減少，導致計算軌跡間的相似程度誤差較大，因此在使用Hilbert曲線劃分軌跡等價類時，會產生較高的誤差，造成數據可用性降低.同樣，隨著k值的增加，信息丟失率也隨之增高，因為k值越大，軌跡間的相似程度偏差越大，數據可用性越低.因此，本文實驗中取參數(α,β)=(0.4,0.6)以及k=70.

Fig.7 Data loss rate under different parameters (α，β)圖7 不同參數(α，β)的數據丟失程度

3.1.1 隱私預算對誤差的影響

在不同的隱私預算下，根據不同的查詢長度我們進行2組實驗，查詢長度|Q|分別取值4和8.為了保證實驗數據的真實性，每組查詢對象都是從樹存儲結構中取得，每組實驗測100次，且每組實驗中添加噪聲方式與Zhao等人[28]一致并具有隨機性，最后取得100次結果的平均值做為最終結果.

圖8中分別給出了查詢長度為4和8的平均相對誤差.從圖8(a)和(b)可以看出，在相同的查詢長度下，平均相對誤差隨著隱私預算的增加而減小.這是因為每一層節點的噪聲量隨著隱私預算的增加而減小，所以數據量的相對誤差也隨之減小.同樣，從實驗圖中可以看出平均相對誤差隨著查詢長度的增加而減小，因為隨著查詢長度的增加，導致樹高也在增加，葉子節點中的噪聲量隨著閾值的限制而減小，因此平均相對誤差也逐漸減小.

Fig.8 The effect of privacy budget on the average relative error under different query length Q圖8 查詢長度Q不同時隱私預算對平均相對誤差的影響

通過實驗結果我們可以得出，在相同的隱私預算下，本文的TDPP算法在平均相對誤差上較低于NTPT算法.

3.1.2 樹高對誤差的影響

本組實驗測試了樹高的變化在不同隱私預算下對平均誤差的影響.根據本文的實驗數據和隱私預算的大小，我們設置了3組實驗.由于本實驗前綴樹中存儲的軌跡最長長度為9，所以樹的高度為9.因此在相同的隱私預算下，每組實驗中的樹高取2,4,6,8，并測得每個樹高所對應的樹高誤差值.每組實驗測試100次，取平均樹高誤差作為最終結果.

如圖9(a)～(c)，實驗表明平均樹高誤差隨著樹高的增加而減小.因為隱私預算隨前綴樹的高度增加而減小，所以葉子節點中的噪聲量也會隨之減少.對比3組實驗，平均樹高誤差隨著隱私預算的增加而減小，因為隱私預算的增加導致噪聲量的添加減小，所測得平均樹高誤差也相應減小.從圖9可以看出本文方案的平均樹高誤差同樣較低于NTPT算法.

Fig.9 The effect of height on the average height error under different ε圖9 樹高對平均樹高誤差影響

因此，本文提出的TDPP算法不僅在平均相對誤差值上較低于NTPT算法，同樣在平均樹高誤差值上也較低于NTPT算法.因此可以證明出本文的TDPP算法的數據可用性較優于NTPT算法.

3.2 隱私性分析

本文方案在軌跡預處理階段，由于軌跡的時空特性，因此在時間和空間上對軌跡劃分成多個軌跡等價類.考慮到在計算軌跡之間的距離時，參數的改變會影響隱私保護程度，因此在圖10中給出了本文算法在不同的k值下，隱私保護程度在方向距離的參數α和速度距離參數β分別為(0,1)，(0.4,0.6)，(0.6,0.4)，(1,0)時的變化趨勢.

Fig.10 Privacy protection level under different parameters (α，β)圖10 不同參數(α，β)下的隱私保護程度

如圖10所示，隱私保護程度隨著k值的增高而降低，因為聚類的軌跡數量越多，數據的可用性也就越高，但隱私保護程度隨之下降.當參數α,β為(0,1)和(1,0)時，隱私保護程度較低于參數為(0.4,0.6)，(0.6,0.4)時的情況，因為參數為0時，軌跡之間減少一個約束條件，導致軌跡間的相似度下降，攻擊者越容易識別出其中某個軌跡，故隱私保護程度也會隨之降低.當參數α,β為(0.4,0.6)，(0.6,0.4)時，隱私保護程度接近，因為根據不同用戶的保護需求，所提供的不同的隱私保護水平，但在總體上的隱私保護程度是接近一致的.

因此，本文方案不僅考慮了數據的可用性，同時也保證了數據的隱私性.綜上，參數(α,β)取值(0.4,0.6)，k取值70.

為保證軌跡數據的安全性和可控性，本文采用差分隱私技術，并將Laplace噪聲添加到存儲軌跡位置點的節點中.本組實驗測試了不同的樹高在不同的隱私預算下對平均相對誤差和平均樹高誤差的影響.圖11的實驗測試樹高的變化對平均相對誤差的影響，圖12的實驗測試樹高的變化對平均樹高誤差的影響.從這2組實驗中可以看出，平均相對誤差和平均樹高誤差隨著樹高的增加而減小，隨著隱私預算的增加也減小.因此，控制隱私預算的合理分配不僅可以保證軌跡數據的可用性，也能保證數據的隱私性.

Fig.11 The average relative error of different privacy budgets圖11 不同隱私預算的平均相對誤差

Fig.12 The average height error of different privacy budgets圖12 不同隱私預算的平均樹高誤差

4 總結與展望

隨著人們進入大數據時代，位置感知設備在日常生活中發揮重要作用，它主要通過收集用戶的位置信息提供高質量服務，但其中可能也包含大量的敏感信息數據.針對該問題，本文提出一種基于差分隱私的軌跡數據發布方法.根據軌跡大數據的特性以及軌跡路徑的特點，本文提出一種基于前綴樹的存儲結構用于存儲劃分后的軌跡位置點，然后利用TDPP算法對節點中的敏感數據添加噪聲，用于保護軌跡數據隱私.最后，本文在真實數據集上進行了數據可用性和隱私性的實驗，并與NTPT算法進行對照實驗，結果表明，本文算法具有較低的平均相對誤差和平均樹高誤差，優于NTPT算法.

隱私保護是當前社會局勢的一個熱門領域，其中對軌跡數據的隱私保護是一個具有重要意義的研究方向.如今越來越多的“可信”第三方數據收集者并不可信，甚至一些基于位置服務的軟件在用戶不知情的情況下有意或無意地泄露用戶的原始數據，造成大量的數據隱私泄露.考慮軌跡數據的特點，今后的研究工作可以主要針對3個方面：1)數據量大，構建存儲結構應考慮遍歷快，減少存儲空間等特性.2)提高數據的可用性，可減少噪聲量的添加，但需保證數據的隱私性.3)針對第三方收集者，可以考慮本地差分隱私技術對位置或其他敏感信息進行收集和發布，從數據源端遏制用戶信息的泄露.