一種面向路網時空約束的軌跡隱私保護技術

劉向宇，許世惠琳，夏秀峰，宗傳玉，朱 睿，李佳佳

(沈陽航空航天大學 計算機學院，沈陽 110136)

近年來，定位技術和移動感知技術的快速發展產生了大量的移動軌跡數據。例如，車輛行駛GPS數據或導航軟件數據形成了用戶的軌跡數據。通過對軌跡數據進行發布共享、分析和挖掘，可以得到大量有價值的信息和知識，用于交通路線設計或城市規劃等。軌跡共享和分析在給城市建設和用戶日常生活帶來便利的同時，也給用戶的個人隱私帶來了巨大的安全隱患。如果對軌跡數據不加限制的直接發布，一旦這些數據被惡意攻擊者獲取，則攻擊者可通過數據挖掘等技術獲取到軌跡信息中蘊含的家庭住址、生活習慣或健康狀況等用戶個人隱私信息，給用戶的隱私安全帶來嚴重威脅[1-3]。因此，針對發布軌跡的隱私保護十分必要，其主要目的在于保護發布軌跡中用戶個人隱私安全，同時保證發布軌跡集仍具有較高的數據可用性。

圖1a所示為用戶u軌跡T的信息，其中(li,ti)表示用戶于ti時刻在位置li處進行位置簽到。圖1b顯示了軌跡T在路網中的位置。軌跡T為用戶u從家出發前往醫院的軌跡，對于用戶u而言，該軌跡屬于其個人隱私。然而，如果數據擁有者在不對其進行任何處理的情況下直接發布，則導致攻擊者可輕易獲得該敏感軌跡，造成用戶的軌跡隱私泄露。

圖1 軌跡T的軌跡信息及其假軌跡在路網中的分布情況

針對上述問題，本文提出一種面向路網時空約束的軌跡隱私保護算法，根據軌跡在路網中的時空特性生成滿足路網時空約束、符合用戶軌跡模式的假軌跡，從而更好地保護軌跡隱私。

1 相關工作

現有的軌跡隱私保護技術主要分為基于泛化的軌跡隱私保護、基于抑制的軌跡隱私保護和基于假軌跡的軌跡隱私保護3種。泛化法是指將軌跡上的位置點擴展為1個匿名區域使攻擊者識別出用戶的概率降低；抑制法通過對軌跡數據進行有選擇的發布實現對用戶敏感軌跡的保護；假軌跡法一般以向真實軌跡中添加虛假軌跡來達到混淆攻擊者的目的。

軌跡k-匿名作為基于泛化的軌跡隱私保護的常用方法之一，其主要思想是通過可信的第三方匿名服務器選擇k-1條與用戶軌跡相似的其他用戶軌跡來對用戶軌跡進行混淆，保護用戶軌跡隱私安全。Zhu等[4]提出一種基于偏好感知的軌跡匿名算法(PTPP)，該算法先根據用戶軌跡移動模式、用戶熟悉度和位置受歡迎程度對用戶偏好進行建模，再自適應選擇合適的位置與用戶原始軌跡上的位置點構建匿名域。Ye等[5]提出一種基于路網的l-多樣性算法。算法先通過可信第三方匿名服務器對路網進行區域劃分，并構建每個子區域內的通用軌跡數據庫，再從軌跡數據庫中選擇l-1條距用戶軌跡最近的其他軌跡構建匿名域。Hwang等[6]提出一種綜合r-匿名、k-匿名、s-道路分段的時間混淆算法對用戶軌跡隱私進行保護。算法首先構建用戶歷史軌跡數據集，再由可信第三方匿名服務器從中選擇與用戶當前軌跡相似的軌跡構建軌跡匿名域，在對軌跡數據進行發布時，打亂發布位置的時間順序來對攻擊者進行混淆。Chiba等[7]發現現有的軌跡匿名方法中有些匿名域內位置發生了變化，導致發布后軌跡集信息損失增大，故提出一種在一定范圍內允許位置和時間不匹配的算法以減少位置距離修改，提高發布后軌跡的數據可用性。

軌跡抑制通過刪除用戶軌跡中敏感或頻繁出現的位置信息實現對軌跡數據有選擇的發布，防止攻擊者通過此類信息對用戶軌跡隱私安全造成威脅。Yao等[8]提出基于擾亂的數據隱私保護算法，通過刪除軌跡上關鍵位置序列中的某些移動位置點使軌跡數據滿足隱私保護要求。Chen等[9]提出基于局部抑制的軌跡隱私保護方案，有選擇地刪除用戶局部軌跡中的位置點，在保護用戶軌跡隱私安全的同時提高發布軌跡的數據可用性。趙婧等[10]提出一種基于軌跡頻率抑制的軌跡隱私保護方法來對用戶軌跡進行處理，在保護用戶軌跡隱私安全的同時提高數據可用性和算法性能。

假軌跡方法指不借助第三方服務器生成與用戶原始軌跡相似的假軌跡，并將原始軌跡與假軌跡一起發布來對攻擊者進行混淆。假軌跡隱私保護技術具有實現簡單、能保留較完整軌跡信息、不需可信第三方服務器等特點，因此在實際研究中應用廣泛。假軌跡方法最早由Kido等[11]提出基本思想。LEI等[12]在此基礎上提出通過隨機法和旋轉法生成假軌跡，隨機法指隨機生成一些位置點，并將它們按時間順序連接得到與用戶原始軌跡相似的假軌跡。旋轉法則是以用戶原始軌跡為基礎，選擇軌跡上某些采樣位置點為軸點對原始軌跡進行旋轉，旋轉后得到的軌跡即為生成的假軌跡。林鄧偉等[13]提出一種基于用戶真實軌跡的虛假軌跡生成方法，主要通過建立用戶軌跡的馬爾科夫模型，并融入攻擊者的背景信息，來抵御攻擊者通過背景知識攻擊來竊取用戶軌跡隱私。Dai等[14]提出一種在路網環境下分段生成假軌跡的軌跡隱私保護算法。該算法通過第三方可信匿名服務器生成假位置，再將生成的假位置與上一時刻真位置連接得到假軌跡段，最后將假軌跡段按時間順序連接得到假軌跡，算法有效提高了用戶軌跡的隱私保護程度。LEI等[15]提出一種基于時空關聯性的假軌跡隱私保護方案。該方案從軌跡整體方向、軌跡間相似性和軌跡上相鄰位置間時空關聯性進行分析，使生成的假軌跡可有效與真實軌跡進行混淆，防止攻擊者識別出假軌跡，有效保護發布軌跡隱私安全。

但現有的針對發布軌跡的隱私保護方法在生成假軌跡時沒有充分考慮軌跡在路網中存在的時空約束條件，所以生成的假軌跡很容易因不滿足現實路網約束條件被攻擊者識別出來，從而導致用戶原始軌跡信息泄露。故本文提出面向路網時空約束的軌跡隱私保護算法解決上述問題。

2 預備知識和問題定義

在本文中，將用戶的時空數據表示為(l，t)，這里t指時間，l=(x，y)為用戶的位置點坐標，x和y分別表示經度、緯度。軌跡是用戶通過不斷移動產生的時空數據序列，記作T={(l1,t1),(l2,t2),…,(ln，tn)}，軌跡上采樣位置點數量為該條軌跡的軌跡長度。將包含多條用戶軌跡的軌跡集稱為原始軌跡集，原始軌跡集TS={T1,T2,…,Tm}，Ti為原始軌跡集中第i條待發布的用戶軌跡，記為Ti={(li1,t1),(li2,t2),…,(lin，tn)}。原始軌跡集經本文算法處理后，得到包含待發布用戶軌跡和對應假軌跡的發布軌跡集PTS。發布軌跡集PTS={T1,T12,…,T1j,…,T2,T21,…,T2j,…,Tm，Tm1,…,Tmj,…}。其中，Tij={(li1(j),t1),(li2(j),t2),…,(lin(j),tn)}表示軌跡Ti的第j條假軌跡，(lia(j),ti)表示Tij的第a個簽到數據。

定義1 敏感軌跡和敏感軌跡攻擊。將用戶不希望別人知道的軌跡稱為敏感軌跡。攻擊者以較大概率識別出用戶的敏感軌跡，導致用戶軌跡隱私泄露，稱為敏感軌跡攻擊。

定義2 軌跡k-匿名。給定一條用戶敏感軌跡Ti，當發布軌跡集中存在k-1條假軌跡與Ti的簽到數據時間序列一致時，則Ti與其他軌跡在該時間段內相互之間不可區分，稱Ti滿足軌跡k-匿名。

定義3 軌跡泄露率。給定原始軌跡集TS，用|TS|表示TS中軌跡數量，|TS′|表示被攻擊者識別出的軌跡數量，則軌跡泄露率如式(1)所示

(1)

定義4 位置距離。給定某時刻用戶敏感軌跡上位置點li=(xi，yi)，假軌跡上對應時刻位置點li′=(xi′,yi′)，將位置距離定義為兩點間的歐氏距離，則位置距離如式(2)所示

(2)

定義5 軌跡距離。給定用戶敏感軌跡Ti={(li1,t1),(li2,t2),…,(lin，tn)}和假軌跡Tij={(li1(j),t1),(li2(j),t2),…,(lin(j),tn)}，則兩軌跡間的軌跡距離如式(3)所示

(3)

定義6 相似軌跡。給定敏感軌跡Ti，假軌跡Tij，距離范圍閾值α、β，若滿足α≤dis(Ti，Tij)≤β，則認為軌跡Ti和Tij是相似軌跡。

定義8 信息損失。給定原始軌跡集TS和發布軌跡集PTS。其中m為TS中軌跡數量，軌跡Ti∈TS,特征軌跡Ti′∈PTS。則基于TS發布軌跡集PTS導致的信息損失如式(4)所示

(4)

問題定義：給定原始軌跡集TS、軌跡匿名閾值k、距離范圍閾值α、β，通過生成滿足路網時空約束條件的假軌跡，構建符合軌跡k-匿名的發布軌跡集PTS，在保護軌跡隱私安全性的同時保證發布軌跡集的數據可用性最大化。

3 路網軌跡隱私保護

本節提出一種面向路網時空約束的軌跡隱私保護算法(A trajectory privacy protection algorithm satisfying the spatio-temporal constraints in road networks,TPPST)，如算法1所示。算法1的主要思想是：首先，通過候選假位置生成算法，根據路網道路分布情況為原始軌跡集中每條敏感軌跡上采樣位置點生成滿足路網時空約束條件的候選假位置集；其次，根據候選假軌跡生成算法，將候選假位置集中位置按時間順序連接得到滿足路網時空約束條件的候選假軌跡集，并從中篩選得出k-1條滿足距離范圍約束且與敏感軌跡間軌跡距離最接近的假軌跡；最后，將敏感軌跡與假軌跡合并為一個發布軌跡匿名集進行發布。在該匿名集內，每條軌跡上的采樣位置點都可與其他軌跡上相同時刻的位置點構成位置匿名集，防止攻擊者識別出敏感軌跡中的任意位置點，從而推測出用戶的完整敏感軌跡。由于本算法既要保證生成假軌跡的合理性與真實性，又要保證發布軌跡的隱私安全，所以生成的每條假軌跡都應在滿足路網軌跡時空約束條件的同時符合用戶的軌跡模式以實現對攻擊者的混淆。

TPPST每次從原始軌跡集TS中獲取一條用戶敏感軌跡Ti進行處理。處理時先通過算法CDL生成Ti上所有采樣位置點的假位置，再將所有采樣位置和假位置一起存入位置候選集Candli中。通過算法CDT得到所有由Candli中位置點組成的滿足路網時空約束條件和距離范圍要求的假軌跡，并將假軌跡按軌跡距離值升序排列存入假軌跡候選集CandTi中(第3～4行)。最后，將敏感軌跡Ti和CandTi中前k-1條假軌跡存入發布軌跡集PTS中。當TS中所有用戶敏感軌跡都得到滿足要求的k-1條假軌跡后，返回包含所有用戶敏感軌跡和假軌跡的發布軌跡集PTS(第5～7行)。

算法1.面向路網時空約束的軌跡隱私保護算法(TPPST)

輸入：軌跡集TS，軌跡匿名閾值k，距離范圍閾值α、β；

輸出：發布軌跡集PTS。

1.PTS ← ?;

2.Foreach trajectoryTiinTSdo

3. Candli= CDL(Ti,k,α,β);//包含軌跡上所有采樣位置和假位置信息的候選位置集;

4. CandTi=CDT(Candli,k,α,β);//按軌跡距離值升序排列的候選假軌跡集;

5. PTS←Ti;

6. Select the topk-1 dummy trajectories from CandTito PTS;

7.ReturnPTS;

3.1 軌跡相似性度量

本算法通過假軌跡與對應用戶敏感軌跡間的軌跡距離來對軌跡相似性進行度量。軌跡距離值越小，生成假軌跡與用戶敏感軌跡在軌跡形狀上越相似，越難被攻擊者區分；軌跡距離值越大，生成假軌跡與原始軌跡間的區別越大，越容易被攻擊者區分。但當軌跡距離值過小或過大時，生成假軌跡會因與原始軌跡過于相似或差別過大而被攻擊者識別出來，很難起到有效的軌跡隱私保護效果。所以給定距離范圍閾值α,β，只有軌跡距離值在給定范圍內的假軌跡才是用戶軌跡的相似軌跡，才能既在滿足軌跡相似性的同時滿足軌跡隱私保護要求。軌跡距離計算如式(3)所示。當且僅當滿足式(5)時，假軌跡才可起到隱私保護效果，用于對攻擊者進行混淆。

α≤dis(Ti,Tij)≤β

(5)

3.2 候選位置集生成

在算法TPPST中，通過候選假位置生成算法(Candidate dummy location generation,CDL)生成軌跡上采樣位置對應的假位置集，并返回由采樣位置和假位置構建的候選位置集。為滿足軌跡隱私保護要求，生成的假位置點需滿足路網時空約束條件和距離范圍要求。同時每個采樣位置都可與至少1個假位置點構建位置匿名域，實現對用戶敏感軌跡上的任一位置點的位置隱私保護。因此將假位置生成分為以下3個步驟：確定假位置生成范圍，計算假位置生成數量，假位置生成。

CDL算法先遍歷軌跡Ti上所有采樣位置li，確定li的假位置生成范圍Zi并記錄Zi內道路密度，刪除道路密度為零的采樣位置點，因為此時無法生成滿足要求的假位置點，故抑制該采樣位置不進行發布(第2～4行)；然后對所得道路密度數據進行均一化處理，并通過計算每個li處應生成的最少假位置數量Ni(第5行)；接著再次遍歷軌跡Ti上的采樣位置li，先將li的位置信息存入Candli中，在位置li對應的假位置生成范圍Zi內隨機生成Ni個滿足路網時空約束的假位置，并將這些假位置的位置信息也存入Candli中，最后返回候選位置集Candli(第6～9行)。

算法2.候選假位置生成算法(CDL)

輸入：原始軌跡Ti，軌跡匿名閾值k，距離范圍閾值α、β；

輸出：候選位置集Candli。

1.Candli← ?;

2.Foreach sampling locationliinTido

3.Zi=dummy location generation range forli;

4.Z←Zi;

5.N←Ni;//Ni=the number of dummy location forlicalculated by Equation 7;

6.Foreach sampling locationliinTido

7. Insert the sampling location’s information into Candli;

8. GenerateNidummy locations inZiand insert these locations’ information into Candli;

9.ReturnCandli;

將路網道路地圖抽象為一個無向圖G(V,E)，路口為無向圖節點V，道路為無向圖邊E。當生成的假位置落在路網無向圖上時，該假位置也可視為落在路網道路中，滿足路網空間可達性約束。由于用戶在路網中只能沿路網道路行駛，故用兩點在路網無向圖中的最短路徑長度代替歐氏距離表示用戶實際行駛路程，并用于路網時間可達性判斷。由于兩點間最短路徑長度與歐氏距離相比更接近于用戶實際行駛路程，故由此得出的路網時間可達性判斷更符合實際。同時，考慮到軌跡上位置點間具有連通性，因此不能單獨考慮某位置點與其前一時刻或后一時刻位置間的路網時間可達性，而應綜合考慮其前后時刻所在位置點共同進行判斷。只有當位置點同時滿足與其前后相鄰時刻位置間的路網時間可達性約束時，該位置點才是滿足要求可用于后續生成假軌跡的假位置點。路網時間可達性由式(6)進行判斷，其中S為位置點li-1至li間的最短路徑距離，ti，ti-1表示到達兩位置的時間戳，vmax為用戶在路網中的最大速度限制。若用戶在時間間隔Δt=ti-ti-1內以給定路網最大速度限制vmax移動的距離大于等于位置li-1至li間的最短路徑距離，則說明用戶可在ti時刻前到達位置點li處。同理可推導出第二個基于距離S的不等式，當用戶在時間間隔Δt=ti+1-ti內以最大速度行駛的距離大于位置li至li+1間的最短路徑距離時，用戶可在ti+1時刻到達位置li+1處。為使后續生成假軌跡滿足距離范圍要求，這里在路網無向圖的基礎上，將假位置生成范圍進一步限制在以采樣位置為圓心，范圍距離閾值α，β為半徑的同心圓的圓環區域內。

(6)

綜上所述，如圖2所示，本算法將采樣位置li的假位置生成范圍Zi定義為滿足式(6)且在以li為圓心,α、β為半徑的同心圓圓環區域內的路網無向圖上。將所有采樣位置li對應的假位置生成范圍Zi存放在位置范圍集Z中。

圖2 假位置生成示意圖

因為每個采樣位置所處地理環境內道路密度不同，若生成相同數量的假位置則可能發生某區域無法得到足夠數量的假位置，而其他區域生成假位置過于密集等情況，因此本文通過Zi內道路密度區分不同li對應的假位置生成數量。首先將所有區域內道路密度記為RD={rd1,rd2,…,rdn}，然后以其中最小的道路密度為基準對道路密度進行均一化處理，處理后得到的結果為RD′={rd1′,rd2′,…,rdn′}，其中rdi′=rdi/rdmin。通過式(7)計算每個采樣位置對應的假位置生成數量，并對計算結果向上取整，可得出不同li處生成的最少假位置數量Ni，將所有采樣位置li對應的假位置生成數量Ni存放在位置數量集N中。最后在每個li對應的Zi內隨機生成Ni數量個假位置即可。

(7)

例如，給定一條包含5個采樣位置的軌跡和軌跡匿名閾值k=5，軌跡上每個采樣位置對應的道路密度為RD={3,2,2,4,3}，以其中最小道路密度2為基準進行均一化處理后得到RD′={1.5,1,1,2,1.5}，通過式(7)計算可知1.5x·x·x·2x·1.5x=4.5x5≥4，將計算結果向上取整后可知x=1，則對應假位置生成數量集合為Ni={2,1,1,2,2}。

3.3 候選假軌跡生成

本節提出候選假軌跡生成算法(Candidate dummy trajectory generation, CDT)生成敏感軌跡Ti對應的候選假軌跡集CandTi。CDT先將算法CDL生成的候選位置集Candli中的位置通過枚舉法得出所有可能滿足路網時空可達性約束的假軌跡，同時計算假軌跡與原始軌跡間的軌跡距離，并將所有軌跡信息存入候選假軌跡集CandTi中。候選假軌跡連接方式如圖3所示(第2行)。然后根據給定的距離閾值α，β對CandTi中所有候選假軌跡進行篩選判斷，若存在軌跡間距離值不滿足軌跡相似性度量公式α≤dis(Ti，Tij)≤β的情況，則從CandTi中刪除該條候選假軌跡(第3～5行)。最后將CandTi中假軌跡按軌跡距離值升序排列后返回(第6-7行)。

圖3 候選假軌跡連接示意圖

算法3.候選假軌跡生成算法(CDT)

輸入：候選位置集Candli，軌跡匿名閾值k，距離范圍閾值α、β；

輸出：候選假軌跡集CandTi。

1.CandTi← ?;

2.Through enumeration method and Candligenerate dummy trajectories and then insertTijto CandTi;

3.Foreach trajectoryTijin CandTido

4.Ifdis(Ti，Tij)not satisfiedα≤dis(Ti，Tij)≤βthen

5. deleteTijfrom CandTi;

6.Sort(asc)CandTiby dis(Ti，Tij);

7.ReturnCandTi;

本文通過枚舉法列舉得出所有可能的候選假軌跡。假設一條軌跡上有n個采樣位置點，若為每個位置點都生成s個假位置則最多可得到(s+1)n-1條假軌跡，假軌跡數量隨采樣位置數呈指數形式增長。但這樣得到的假軌跡集中會存在某些假軌跡上存在過多與采樣位置點相同的位置，增加原始軌跡泄露的風險。故需進一步對得到的假軌跡進行篩選，只保留含有一個采樣位置的假軌跡，刪除其余假軌跡，這樣得到的假軌跡集可在有效對攻擊者進行混淆的同時，降低軌跡泄露概率。

3.4 算法安全性及復雜度分析

在本節中，會對算法的安全性和時間復雜度進行理論分析與證明。

定理1 采用面向路網時空約束的軌跡隱私保護算法(算法1)對原始軌跡集中的每條用戶軌跡進行處理后，得到的發布軌跡集滿足軌跡k-匿名要求。

證明 算法2為原始軌跡集中每條用戶敏感軌跡上所有采樣位置點生成假位置，且通過計算保證這些假位置連接得到的滿足路網時空可達性約束和距離范圍要求的假軌跡至少為k-1條。算法3在生成假軌跡時不僅使用算法2生成的假位置點還包含原始軌跡上部分采樣位置點，所以最后得到的滿足要求的假軌跡一定多于k-1條。算法1通過調用算法2和算法3得到所有滿足路網時空約束和距離范圍要求的假軌跡中軌跡距離值最小的k-1條，使軌跡集中每條原始軌跡均能滿足軌跡k-匿名。綜上，通過算法1生成的發布軌跡集滿足軌跡k-匿名要求。

算法復雜度分析：用m、n分別表示原始軌跡集中用戶敏感軌跡數量和敏感軌跡上采樣位置點數量。在算法CDL中，生成軌跡上所有采樣位置點對應的滿足路網時空可達性約束條件的假位置需n+n·k1/n時，則算法的時間復雜度為O(n·k1/n)。在算法CDT中，通過枚舉法得到所有候選假軌跡并計算軌跡距離耗時n!+(k1/n+1)n，算法復雜度為O(n!)。算法TPPST通過調用算法CDL和算法CDT得到軌跡集中每條用戶原始軌跡的候選假軌跡集，并從中選擇k-1假軌跡耗時為m·(n·k1/n+n!)，所以算法TPPST的時間復雜度為O(m·n!)。

4 實驗結果分析

本節對提出的面向路網時空約束的軌跡隱私保護算法進行性能分析和評估。實驗使用北京市路網地圖數據和1個真實的北京出租車軌跡集T-Drive。其中，北京市路網數據包括17萬個路網頂點及43萬余條邊。T-Drive原始軌跡集包含北京大部分區域的10 357輛出租車一星期內的軌跡，總計72 499條軌跡，涵蓋約1 500萬位置點，軌跡中相鄰位置點間的時間差為5 min。本文對T-Drive原始軌跡集進行處理，選取其中600條軌跡上的部分軌跡數據構建實驗軌跡數據集進行實驗，實驗數據集統計信息如表1所示。

表1 實驗數據集統計信息

本文先通過實驗得出面向路網時空約束的軌跡隱私保護算法(TPPST)中的最優距離范圍閾值。然后通過與基于隨機法生成假軌跡的隱私保護方法(簡稱RM)和基于時空關聯性生成假軌跡的隱私保護方法(簡稱STM)比較，分析本算法在運行時間、信息損失和軌跡泄露率方面的性能。在測試中,軌跡匿名閾值k的取值范圍為[3,18](默認為9)，軌跡數量n的取值范圍為[100,600](默認為300)，軌跡長度l的取值范圍為[5,10](默認為7)。

本實驗的軟硬件環境如下：(1)硬件環境：Intel Core i5 2.71GHz 8GB DRAM;(2)操作系統：Microsoft Windows 10;(3)編程環境：Java,Eclipse。

4.1 最優距離閾值

本節通過測試TPPST算法在不同距離范圍下的軌跡相似度和信息損失來獲取最優距離范圍閾值α、β。由于當距離范圍過小或過大時,所得實驗結果均趨于平緩，故選擇波動較大區間作為實驗測試范圍。

由圖4可知：(1)隨著距離范圍的增大，軌跡相似度逐漸增加，信息損失逐漸減少。這是由于隨著距離范圍的增大，假位置的生成范圍也隨之擴大，一些原始軌跡上原本因假位置生成范圍內道路密度為零而被抑制發布的采樣位置點，在擴大范圍后也生成假位置并參與發布。由信息損失計算公式可知，信息損失為原始軌跡集中所有用戶敏感軌跡與發布軌跡集中對應特征軌跡間軌跡距離和的平均值。隨著距離范圍的擴大，特征軌跡上的位置點也隨之變化，部分位置點坐標與原始軌跡上對應采樣位置點坐標更加接近，因此信息損失逐漸降低。而軌跡相似度主要通過原始軌跡與對應假軌跡間軌跡距離進行計算，隨著更多假位置的生成，計算時會增加該點與對應假位置間的距離差，故軌跡相似度逐漸增加。綜上所述，距離范圍與軌跡相似度成正比,與信息損失成反比。(2)實驗通過對比在不同軌跡匿名閾值k、軌跡長度和軌跡數量的情況下，得出距離范圍變化對軌跡相似度和信息損失產生的影響。由圖4可知，當距離范圍從6 km增大到7 km時，信息損失明顯下降，且在距離范圍大于7 km時信息損失的變化趨于平緩。在軌跡相似度隨距離范圍的增加而逐漸增加的過程中，在距離范圍為10 km時，增加趨勢明顯減緩。所以本文將距離范圍設置為[7,10]，在該范圍內算法生成的假軌跡可在有效保護用戶原始軌跡隱私安全的情況下，保持較好的數據可用性。

圖4 軌跡相似度和信息損失隨距離范圍變化

4.2 運行時間

由圖5可知,3個算法的運行時間均隨著軌跡匿名閾值k、軌跡數量和軌跡長度的增加而增長。STM算法和RM算法的運行時間接近，TPPST算法快于STM算法和RM算法約1.5 s。這是由于TPPST算法通過CDL和CDT算法限定了假位置和假軌跡的生成條件，因此TPPST算法可以更快地生成滿足要求的假軌跡。且由圖5可知，運行時間與軌跡匿名閾值k、軌跡數量和軌跡長度值成正比，即要生成的假軌跡和待用戶保護軌跡上采樣位置數量越多則運行時間越長，且隨著生成假軌跡數量的增加算法耗時翻倍增加。

圖5 運行時間隨k、軌跡數量和軌跡長度變化

4.3 信息損失

由圖6可知,RM算法和STM算法的信息損失始終高于TPPST算法，最高可達TPPST算法的2倍。這是由于STM算法的假位置生成范圍為將路網地圖網格化后，兩采樣位置間歐氏距離加一個隨機數長度的網格范圍。RM算法的假位置生成范圍為將路網地圖網格化后距采樣位置2β內的網格范圍。由此可以看出RM算法和STM算法生成的假位置點要比TPPST算法生成的假位置點與采樣位置間的位置距離大，因此計算所得信息損失也更大。由圖6可知，信息損失與軌跡匿名閾值成反比，與軌跡數量值成正比。由信息損失計算公式可知，隨著生成假軌跡數量的增加，敏感軌跡T與發布軌跡中對應特征軌跡T′間的軌跡距離值會逐漸減小。在軌跡數量不變的情況下，信息損失隨著軌跡匿名閾值k的增加而減小。而在軌跡匿名閾值k不變的情況下，隨著原始軌跡數量的增加，計算得到的軌跡距離累加和也在不斷增加,且增長趨勢大于軌跡數量的增長，故信息損失會隨著軌跡數量的增加而增加。

圖6 信息損失隨k和軌跡數量變化

4.4 軌跡泄露率

由圖7可知,當發布軌跡為路網軌跡時，TPPST算法根據路網中軌跡的時空約束條件生成假軌跡，故無法被攻擊者通過敏感軌跡攻擊識別出來。RM算法和STM算法的軌跡泄露率接近于100%,遠高于TPPST算法。這是由于RM算法只是以用戶真實位置點為基準隨機生成假位置點，而STM算法雖然是基于軌跡時空特性生成假軌跡，但二者均未考慮路網軌跡具有的時空約束條件，故使用上述兩種算法生成的假軌跡有95%以上的概率會被攻擊者通過敏感軌跡攻擊識別出來，導致用戶敏感軌跡隱私泄露。

圖7 軌跡泄露概率隨k和軌跡數量變化

5 結語

本文提出一種面向路網時空約束的軌跡隱私保護算法(TPPST)，用以解決現有的假軌跡生成軌跡隱私保護技術因生成的假軌跡真實性較差而造成用戶軌跡隱私泄露的問題。該算法在路網無向圖的基礎上根據路網軌跡時空約束條件生成假軌跡，使生成的假軌跡在有效保護用戶隱私安全的同時,降低發布后軌跡集的信息損失。實驗基于真實軌跡數據進行，所得結果表明TPPST算法可有效抵御攻擊者的敏感軌跡攻擊，在保護用戶發布軌跡隱私安全的情況下保證發布軌跡具有較好的數據可用性。