防止暴露位置攻擊的軌跡隱私保護(hù)

劉向宇，陳金梅，夏秀峰，Manish Singh，宗傳玉，朱 睿

（1.沈陽航空航天大學(xué)計算機(jī)學(xué)院，沈陽110136；2.惠靈頓理工學(xué)院信息與商科學(xué)院，新西蘭下哈特5010）

0 引言

近年來，隨著定位技術(shù)和位置感知設(shè)備的發(fā)展，移動用戶的位置和軌跡信息被大量地收集和發(fā)布。對于軌跡信息的挖掘和分析，產(chǎn)生了許多新型的應(yīng)用。例如，通過分析特定區(qū)域中用戶的軌跡信息可以幫助投資者進(jìn)行商業(yè)決策，比如在哪里建立商場；同時，政府機(jī)構(gòu)可以通過分析城市中的車輛軌跡來優(yōu)化交通管理系統(tǒng)和交通路線的設(shè)計，發(fā)現(xiàn)不合理的道路規(guī)劃。雖然發(fā)布軌跡信息在與其相關(guān)的決策和應(yīng)用中發(fā)揮了極大的作用，但是也存在著嚴(yán)重的個人隱私泄露威脅，如果惡意攻擊者獲取到軌跡信息，就可以通過數(shù)據(jù)挖掘技術(shù)獲取到用戶軌跡數(shù)據(jù)中的隱私信息：家庭住址、工作單位、興趣愛好、生活習(xí)慣和健康狀況等，將給用戶帶來嚴(yán)重后果［1-2］。因此，對軌跡信息的隱私保護(hù)受到了國內(nèi)外學(xué)者的廣泛關(guān)注。

目前軌跡隱私保護(hù)技術(shù)大致分為三類：假軌跡、軌跡泛化和軌跡抑制。其中，假軌跡隱私保護(hù)方法具有機(jī)制簡單、計算量小、不需要可信的第三方實體，且能保留完整的軌跡信息等特點，在實際研究中得到了廣泛的應(yīng)用。但是現(xiàn)有的假軌跡保護(hù)方法在生成假軌跡時沒有考慮用戶的暴露位置，可能會降低軌跡的隱私保護(hù)程度甚至直接泄露用戶的真實軌跡。

圖1（a）為用戶的真實軌跡tr，其中l(wèi)2為用戶t2時通過微博發(fā)布動態(tài)顯示的位置，攻擊者可以獲取此信息。當(dāng)用戶發(fā)布軌跡時，使用現(xiàn)有的假軌跡隱私保護(hù)方法來隱匿該軌跡，軌跡匿名要求是3-匿名，即識別真實軌跡的概率不大于1/3。例如圖1（b）中的d1和d2為采用文獻(xiàn)［3］中的隨機(jī)法生成的兩條假軌跡，和真實軌跡tr組成軌跡集來進(jìn)行軌跡匿名。然而，由于攻擊者知道用戶t2時出現(xiàn)在位置l2，而軌跡d2在t2時沒有經(jīng)過位置l2，故攻擊者可識別出其為假軌跡，從而識別真實軌跡的概率變?yōu)?/2，大于軌跡隱私要求的1/3，導(dǎo)致軌跡隱私泄露。本文將這種攻擊方式定義為暴露位置攻擊（具體定義后文給出）。

針對此問題，本文提出了一種假軌跡隱私保護(hù)算法，其基本思想是構(gòu)建k-1 條與真實軌跡相似且包含暴露位置的假軌跡來隱匿真實軌跡。值得一提的是，軌跡隱私保護(hù)既意味著整個軌跡不被識別，也意味著軌跡中的敏感位置（除暴露位置外的其他位置）不被識別。圖1（c）為添加假軌跡后的軌跡集。每條假軌跡都包含暴露位置l2。實驗結(jié)果表明，本文算法可以有效保護(hù)用戶的真實軌跡。

圖1 真實軌跡tr、隨機(jī)法生成的tr的假軌跡和tr的匿名軌跡集Fig.1 Real trajectory tr，dummy trajectories of tr generated by random algorithm and the anonymized trajectory set TRS of tr

1 相關(guān)工作

軌跡k-匿名是軌跡隱私保護(hù)方法之一，其主要思想是由匿名服務(wù)器挑選k-1 條其他用戶的軌跡與該用戶軌跡組成軌跡集，且這k 條軌跡無法區(qū)分。Monreale 等［4］提出了一種基于空間泛化和k-匿名的方法對原始GPS 軌跡進(jìn)行轉(zhuǎn)換，在已有的軌跡數(shù)據(jù)集中實現(xiàn)真正的匿名；Xu 等［5］使用不同移動用戶的歷史足跡來形成匿名區(qū)域，并構(gòu)建k-1 條歷史軌跡；Abul等［6］提出NWA（Never Walk Alone）方法，并通過軌跡聚類和空間轉(zhuǎn)移實現(xiàn)(k，δ)-anonymity；Huo 等［7］提出YCWA（You Can Walk Alone）方法，通過對軌跡上停留點泛化來保護(hù)軌跡隱私。

軌跡抑制法是指選擇性地發(fā)布軌跡數(shù)據(jù)，將敏感或頻繁訪問的位置去除。Gruteser 等［8］根據(jù)某個區(qū)域的用戶訪問量將地圖劃分為敏感區(qū)域和非敏感區(qū)域，當(dāng)用戶進(jìn)入到敏感區(qū)域時，抑制或推遲更新其位置，非敏感區(qū)域不受控制；Terrovitis 等［9］提出通過抑制處于敏感區(qū)域的位置來使軌跡泄露的風(fēng)險低于用戶設(shè)定的隱私保護(hù)閾值；趙婧等［10］提出基于軌跡頻率處理軌跡數(shù)據(jù)來保護(hù)軌跡隱私。

假軌跡隱私保護(hù)的主要思想是由用戶自己生成k-1 條假軌跡，與真實軌跡組成軌跡集進(jìn)行發(fā)布，其基本思想最早是由Kido 等［3，11］提出；Lei 等［12］通過隨機(jī)模式和旋轉(zhuǎn)模式來生成假軌跡；Wang 等［13］通過算法求出最佳旋轉(zhuǎn)角度來生成假軌跡，并將部分?jǐn)?shù)據(jù)信息存儲在霧結(jié)構(gòu)中進(jìn)行物理控制，保證用戶的隱私；雷凱躍等［14］生成假軌跡時考慮了軌跡中相鄰位置的時間可達(dá)性和時空關(guān)聯(lián)性；Wu 等［15］考慮了用戶的移動模式，基于重力模型定義了連續(xù)位置熵和軌跡熵來度量軌跡保護(hù)程度，并基于此提出了假軌跡隱私保護(hù)方法。

然而現(xiàn)有的假軌跡隱私保護(hù)算法在生成假軌跡時沒有考慮用戶的暴露位置，使得攻擊值很容易利用暴露位置識別出某些假軌跡，甚至真實軌跡。本文以此為出發(fā)點，設(shè)計假軌跡隱私保護(hù)方案。

2 預(yù)備知識

本文涉及的變量說明如下：位置是地圖上的一個興趣點（醫(yī)院、餐廳、商店、銀行等），表示為l=(x，y)，其中：x為經(jīng)度，y為緯度。直接使用l代表位置。一條軌跡是由n個具有時空特性的位置組成的序列，可以將真實軌跡表示為tr={(l1，t1)，(l2，t2)，…，(ln，tn)}，假軌跡表示為d={(l'1，t1)，(l'2，t2)，…，(l'n，tn)}，其 中(li，ti)表 示 用 戶ti時 在 位 置li簽 到，且1 ≤i ≤n。| tr |表示軌跡的長度。由tr和k-1 條假軌跡組成的軌跡集為TRS={tr，d1，d2，…，dk-1}。

定義1暴露位置。 給定一條真實軌跡tr={(l1，t1)，(λ，tλ)，…，(ln，tn)}，λ 為用戶在tλ時通過移動設(shè)備發(fā)布至社交網(wǎng)絡(luò)且所有人可知的位置，此時稱λ 為tr 在tλ時的暴露位置。該條軌跡中可以有多個暴露位置，用EL={(λ1，tλ1)，(λ2，tλ2)，...(λm，tλm)}(m ＜n)表示tr 的 暴 露位置集。軌跡中除暴露位置外的其他位置為敏感位置。

如圖1（a）所示，l2為暴露位置，軌跡中的其他位置｛l1，l3，l4，l5｝為敏感位置。

定義2暴露位置攻擊。假設(shè)攻擊者知道用戶軌跡中的某些位置，當(dāng)其利用這些位置進(jìn)行隱私攻擊時，稱為暴露位置攻擊。

例如用戶針對tr發(fā)布的軌跡集為TRS，tr的暴露位置集為EL，攻擊者利用暴露位置(λi，tλi)∈EL 作為先驗知識對軌跡集TRS 進(jìn)行攻擊，當(dāng)TRS 中某條軌跡在tλi時刻未經(jīng)過暴露位置λi時，可識別出其為假軌跡，從而導(dǎo)致用戶軌跡隱私泄露。如圖1（b）所示，攻擊者利用l2攻擊，軌跡d2在t2時未經(jīng)過位置l2可識別出其為假軌跡。

定義3軌跡泄露率TE。假設(shè)用戶發(fā)布的軌跡集為TRS，攻擊者利用其背景知識對TRS 進(jìn)行識別，推測出用戶真實軌跡的概率。

其中|TRS'|表示被攻擊者識別為假軌跡的數(shù)量。

定義4平均位置泄露率ALE。假設(shè)用戶針對tr 發(fā)布的軌跡集為TRS，tr 的長度為n，暴露位置集為EL，個數(shù)為m（m＜n），除暴露位置外的其他時刻ti對應(yīng)的位置集為Li，在這個時刻泄露真實位置的概率為1/Li，那么對于整個軌跡而言，平均位置的泄露率為：

定義5（p，k）-anonymity。給定tr 的軌跡集TRS，軌跡匿名閾值p、k（p≤k），如果TRS 中任一敏感位置的位置泄露率不大于，軌跡泄露率不大于，則認(rèn)為軌跡集TRS 滿足（p，k）-anonymity。

如圖1（c）所示的軌跡集滿足（2，3）-anonymity。

定義6位置距離。給定兩個位置li和lj，位置距離定義為位置間的歐氏距離。

定義7軌跡距離。給定兩條軌跡tr1={l1，l2，…，ln}，，軌跡距離定義如下：

定義8軌跡距離閾值。給定兩條軌跡tr1和tr2，若α ≤TDist(tr1，tr2)≤β，則認(rèn)為tr1和tr2之間的軌跡距離滿足軌跡距離閾值(α，β)。

問題1 給定用戶真實軌跡tr，暴露位置集EL，軌跡距離閾值(α，β)，軌跡隱私要求閾值（p，k），采用假軌跡隱私保護(hù)方法使得生成的軌跡集滿足（p，k）-anonymity。

3 基于假軌跡的隱私保護(hù)算法

本文提出的基于假軌跡的軌跡隱私保護(hù)（Dummy-based Trajectory Privacy Protection，DTPP）算法的主要思想是生成k-1 條假軌跡與真實軌跡組成可供發(fā)布的軌跡集，代碼如算法1 所示。該算法既要求保護(hù)軌跡，又要求保護(hù)位置，所以每一條假軌跡既要盡可能地在形狀上與真實軌跡相似，又要增加軌跡集中敏感位置處的假位置數(shù)。DTPP 首先通過候選假軌跡生成算法DTC（Dummy Trajectory Candidate）得到Score 值降序排列的假軌跡候選集第2）行）。Score是一個啟發(fā)式函數(shù)，其值度量了假軌跡在軌跡相似性和位置多樣性兩方面的影響。Score 值越大表明該假軌跡與真實軌跡越相似，且能提供更多的假位置。然后循環(huán)選擇Score 值最大（即在Candtr頂端）的假軌跡加入到軌跡集中，直到生成k-1條假軌跡（第3）～5）行）。DTPP 生成軌跡集后，依次判斷每個敏感位置處的位置數(shù)是否滿足位置匿名閾值p，若不滿足，說明用戶該敏感位置處的假位置無法使軌跡集滿足（p，k）-anonymity（第7）～9）行），需要將其抑制，才能保證用戶的隱私安全。最后DTPP返回軌跡集合（第10）行）。

算法1 假軌跡隱私保護(hù)算法DTPP。

輸入 真實軌跡tr，暴露位置集EL，軌跡匿名閾值（p，k），軌跡距離閾值(α，β)；

輸出 包含k條軌跡的軌跡集。

3.1 軌跡度量

本文使用軌跡相似性（表示為Sim（d，tr））和位置多樣性（表示為Div（d，TRS））來度量假軌跡的影響，為了最大化假軌跡的作用效果，本文設(shè)計了如式（5）所示的啟發(fā)式來選擇假軌跡。

軌跡相似性Sim（d，tr）的定義如式（6）所示，它顯示了假軌跡與真實軌跡之間的形狀相似度，通過假軌跡與真實軌跡對應(yīng)位置間的位置距離的方差來度量。為了與語義信息相匹配，通過對其取倒數(shù)即可達(dá)到“Sim（d，tr）越大，假軌跡與真實軌跡越相似”的效果。

位置多樣性Div（d，TRS）的定義如式（7）所示，它表示加入假軌跡后，軌跡集中有數(shù)量變化的位置集數(shù)占總位置集數(shù)的比例。其中div(l'i，Li)表示位置集Li在添加假位置l'i后的數(shù)量變化，有變化為1，無變化為0。

3.2 生成假軌跡候選集

在DTPP 算法中，通過候選假軌跡生成算法DTC（見算法2）生成候選假軌跡。本文通過連接假位置構(gòu)造假軌跡，試想一條有s 個敏感位置的軌跡，每個敏感位置處產(chǎn)生m 個假位置，如果使用枚舉法來產(chǎn)生假軌跡，則有ms條軌跡，假軌跡數(shù)量隨著敏感位置數(shù)呈指數(shù)增長?？紤]到真實軌跡具有時空特性，假軌跡相鄰位置間應(yīng)滿足時空可達(dá)性，所以本文根據(jù)假軌跡相鄰位置間是否可達(dá)把假軌跡候選集建模為有向圖，正式化為 圖G={V，E}。V={(v10，v11，…，v1m)，(v20，v21，…，v2m)，…，(vn0，vn1，…，vnm)}，其中：vi0為真實位置，vij為假位置；E 是邊的集合，表示軌跡中相鄰位置間可達(dá)。時空可達(dá)性由式（8）判斷，vmax是用戶在真實軌跡中的最大速度。很明顯，如果式（8）不成立，則說明用戶ti時從vij出發(fā)不能在ti+1之前到達(dá)位置vi+1，j。

如圖2 所示，為圖1（a）中的軌跡和其假位置候選集構(gòu)成的軌跡有向圖，其中位置v20為暴露位置。如果兩個位置點可達(dá)，則兩個位置之間有一條邊。

圖2 軌跡有向圖Fig.2 Trajectory directed graph

為了便于計算假軌跡與真實軌跡的軌跡相似性和軌跡距離，同時實現(xiàn)有向圖的建立，采用如圖3 所示的鄰接表存儲結(jié)構(gòu)。其中：id 為位置的邏輯地址；vij為位置；Dist=dist(vi.j+1，vi0)為假位置與對應(yīng)真實位置之間的位置距離；Reach 為該位置在(ti+1-ti)內(nèi)可以到達(dá)的位置集合，在這里不直接存儲位置，而是存儲位置的邏輯地址，節(jié)省存儲空間。

圖3 軌跡有向圖的存儲結(jié)構(gòu)Fig.3 Storage structure of trajectory directed graph

算法2 候選假軌跡生成算法DTC。

輸入 真實軌跡tr，暴露位置集EL，位置匿名閾值p，軌跡距離閾值(α，β)；

輸出 假軌跡候選集Candtr。

在算法2 中，由于每條假軌跡都是以真實軌跡中的第一個位置l0或Candl0中的假位置為起始位置，以真實軌跡的最后一個位置ln或Candln中的假位置為結(jié)束位置，因此，通過在圖G上以li∈{l0∪Candl0}為開始節(jié)點進(jìn)行深度優(yōu)先遍歷便可得到所有可能的假軌跡（第5）、6）行）。若假軌跡與真實軌跡之間的距離滿足軌跡距離閾值(α，β)，計算該條軌跡的Score值，將其加入到假軌跡候選集Candtr中（第7）～10）行）。

接下來通過軌跡有向圖生成算法TDG（Trajectory Directed Graph，見算法3）介紹軌跡有向圖的建立，首先將li和Candli合并為Vi，得到有向圖中所有的點（第3）、4）行）。然后判斷相鄰位置vij和vi+1，j間的時空可達(dá)性，若可達(dá)，則存在邊最后得到有向圖G（第5）～14）行）。

算法3 軌跡有向圖生成算法TDG。

輸入 真實軌跡tr，假位置候選集Candl；

輸出 軌跡有向圖G。

3.3 生成假位置候選集

本節(jié)介紹候選假位置生成算法DLC（Dummy Location Candidate）生成假位置候選集?？紤]到真實生活中，攻擊者很容易從網(wǎng)上獲取到地圖信息，所以他可以根據(jù)軌跡中位置所處的地理環(huán)境特征來識別假位置，從而排除假軌跡。例如，如果攻擊者捕獲到軌跡集中的某條軌跡的某個位置是湖泊，則可以推斷出該條軌跡為假軌跡。因此，本文使用地圖中真實且有意義的位置點作為假位置來保護(hù)軌跡隱私。

為了提高程序的運行效率，本文通過網(wǎng)格劃分地圖。根據(jù)軌跡距離閾值(α，β)將網(wǎng)格單元大小設(shè)置為2β。如圖4（a）所示，如果敏感位置正好在網(wǎng)格中心，則只需要查找一個網(wǎng)格；如圖4（b）所示，若敏感位置不在網(wǎng)格中心，也只需要查找4個網(wǎng)格，大大縮短了查詢時間。

在算法DLC 中，首先根據(jù)軌跡距離閾值上限β 將地圖劃分為網(wǎng)格單元大小為2β×2β 的網(wǎng)格（第2）行）。對于軌跡中的位置，若為暴露位置，則其假位置候選集為?（第4）、5）行）；若為敏感位置，根據(jù)位置坐標(biāo)查找網(wǎng)格并遍歷其中的位置l'i，若，則將l'i加入到候選集Candli中（第6）～10）行）。記|Candli|為位置候選集中位置的個數(shù)，若|Candli|＜p，則將真實軌跡中該位置刪除（第11）、12）行）。因為當(dāng)|Candli|＜p 時，說明li處于地理位置密度稀疏區(qū)域，無法生成足夠多的假位置來隱匿用戶的真實位置，只能將其抑制。

圖4 不同敏感位置的查詢網(wǎng)格Fig.4 Query girds of different sensitive locations

算法4 候選假位置生成算法DLC。

輸入 真實軌跡tr，暴露位置集EL，位置匿名閾值p，軌跡距離閾值上限β；

輸出 假位置候選集Candl。

3.4 算法的安全性、復(fù)雜度理論分析

假設(shè)用戶軌跡的長度為n，有m 個暴露位置，s 個敏感位置，那么n=s+m。

定理1采用基于假軌跡的軌跡隱私保護(hù)算法（算法1）對用戶軌跡進(jìn)行保護(hù)后，得到的軌跡集滿足(p，k)-anonymity。

證明 軌跡中有s 個敏感位置，軌跡匿名閾值為（p，k）。算法4 為每個敏感位置生成假位置候選集，若其候選集中的位置數(shù)小于位置匿名閾值p，則將該位置刪除，所以軌跡中剩余的敏感位置處的位置數(shù)至少為p。算法2 生成假軌跡候選集，假設(shè)每個敏感位置處有p 個位置，理論上有ps條軌跡，而實際中，由于不只有p個位置，軌跡數(shù)會更多，足夠產(chǎn)生k條軌跡。算法1 通過調(diào)用算法2，啟發(fā)式地選擇假軌跡，直到軌跡集中有k 條軌跡，并且判斷軌跡集中敏感位置處的位置匿名程度，若不滿足p，將該敏感位置刪除，從而保證軌跡集中的敏感位置都滿足p 匿名。綜上，通過算法1 生成的軌跡集滿足（p，k）-anonymity。

算法復(fù)雜度分析：在算法DLC 中，敏感位置通過查詢網(wǎng)格獲取假位置候選集，假設(shè)|Dl|為查詢網(wǎng)格中的假位置數(shù)量，因為算法的時間復(fù)雜度為s ?|Dl|+m，s ?|Dl|?m，所以復(fù)雜度為O(s ?|Dl|)。在算法TDG 中，需要n ?(|Candli|+1)2時間生成有向圖，其中|Candli|為每個敏感位置的候選位置數(shù)，時間復(fù)雜度為O(n ?(|Candli|+1)2)。在算法DTC 中，首先調(diào)用算法DLC，然后調(diào)用TDG，最后執(zhí)行深度優(yōu)先遍歷獲取假軌跡候選集，最多耗時(|Candli|+1)s，即任意相鄰位置間都滿足時空可達(dá)性，當(dāng)假位置數(shù)量過多時，可能導(dǎo)致有向圖很龐大，但是其執(zhí)行時間最多與前人算法中的枚舉方式時間相同。實際上，通過實驗可以發(fā)現(xiàn)，此種情況發(fā)生的概率很小，所以算法DTC的 時 間 復(fù) 雜 度 為O(Max(n ?(|Candli|+1)2，(|Candli|+1)s))。DTPP 算法通過調(diào)用算法DTC 獲取k-1條假軌跡，DTPP 執(zhí)行一次DTC，之后更新Candtr中的Score 值，耗時為n ?(|Candli|+1)2+(|Candli|+1)s+(k-2)|Candtr|，所 以DTPP 算 法 的 時 間復(fù)雜度為O(Max(n ?(|Candli|+1)2，(|Candli|+1)s))。

4 實驗評估與分析

本章對提出的假軌跡隱私保護(hù)算法進(jìn)行性能分析和評價。實驗中用戶的軌跡數(shù)據(jù)來自斯坦福大學(xué)復(fù)雜網(wǎng)絡(luò)分析平臺公開的兩個真實數(shù)據(jù)集Brightkite和Gowalla，同時也得到了這兩個數(shù)據(jù)集所在州California 的地圖數(shù)據(jù)，包括21 047 個節(jié)點和21 692 條邊。本文從兩個軌跡數(shù)據(jù)集中分別選取了5 000個用戶的5 000條軌跡數(shù)據(jù)進(jìn)行實驗，表1顯示了實驗數(shù)據(jù)的其他相關(guān)信息。

表1 實驗數(shù)據(jù)統(tǒng)計信息Tab.1 Statistics of datasets

首先通過實驗獲得本文DTPP 算法中最優(yōu)軌跡距離閾值；然后通過與基于重力模型的假軌跡隱私保護(hù)方法（記為GM）［15］和基于隨機(jī)法的假軌跡隱私保護(hù)方法（記為SM）［10］進(jìn)行比較來分析本文算法的性能；最后評估本文算法涉及的參數(shù)對算法的影響。在測試中：匿名閾值k和p的取值范圍分別是［6，27］（默認(rèn)為15）、［3，9］（默認(rèn)為3），暴露位置集|EL|取值范圍為［1，4］（默認(rèn)為1）。

本實驗的軟硬件環(huán)境如下：1）硬件環(huán)境：Intel Core i5 2.33 GHz，4 GB DRAM。2）操作系統(tǒng)平臺：Microsoft Windows 7。3）編程環(huán)境：Java，IDEA。

4.1 最優(yōu)軌跡距離閾值

本節(jié)通過測試DTPP 算法在不同軌跡距離下的軌跡相似性、平均位置泄露率和運行時間來獲得最優(yōu)軌跡距離閾值(α，β)。

由圖5 可知：1）隨著軌跡距離的增大，軌跡相似性逐漸降低，平均位置泄露率逐漸降低，運行時間逐漸增加。這是因為隨著軌跡距離的增加，更多的假位置加入到軌跡集中，而所有的假軌跡都要經(jīng)過暴露位置，導(dǎo)致軌跡相似性降低；相應(yīng)地，平均位置泄漏率減小，運行時間增加。2）當(dāng)軌跡距離為2 km時，雖然軌跡相似性很高，但平均位置泄漏率卻很大，Gowalla數(shù)據(jù)集甚至達(dá)到了60%；當(dāng)軌跡距離大于6 km 時，軌跡相似性在減小，但平均位置泄露率基本穩(wěn)定于20%。3）當(dāng)軌跡距離小于6 km 時，本文DTPP 算法的運行時間在4 s 以內(nèi)，所以本文把軌跡距離閾值設(shè)為(α，β)=（3，6）。4）從兩個數(shù)據(jù)集比較上來看，Gowalla 數(shù)據(jù)集在軌跡相似性和平均位置泄露率方面比Brightkite 略好，但運行時間比Brightkite 稍長，這是因為Gowalla 數(shù)據(jù)集中的位置分布密度要略高于Brightkite 數(shù)據(jù)集。

圖5 軌跡相似性、平均位置泄漏率和運行時間隨軌跡距離的變化Fig.5 Trajectory similarity，average location disclosure rate and running time varying with trajectory distance

4.2 性能分析

本節(jié)通過軌跡泄露率、軌跡相似性和算法運行時間來比較DTPP 算法、GM 和SM 的性能。由圖6～8 可知：1）軌跡相似性隨著軌跡數(shù)量的增多而減小。DTPP 算法的軌跡相似性比GM 算法低約5%，這是因為DTPP 算法考慮了暴露位置，導(dǎo)致假軌跡與真實軌跡對應(yīng)位置之間的位置距離差異性較GM 算法要大一些，而GM 算法考慮了用戶的移動模式，產(chǎn)生的假軌跡與真實軌跡更為相似，但算法DTPP 的軌跡相似性卻遠(yuǎn)高于SM 算法，是SM 算法的4 倍左右。2）當(dāng)軌跡中存在暴露位置時，由于DTPP 算法考慮了暴露位置，攻擊者無法利用此信息識別假軌跡；而GM 算法在生成假軌跡時，與真實軌跡沒有交點，導(dǎo)致攻擊者可以利用暴露位置100%識別出真實軌跡；SM 隨機(jī)生成假軌跡，所以可能經(jīng)過暴露位置，但平均軌跡泄露率卻高達(dá)約50%。3）三個算法的運行時間隨著軌跡數(shù)的增多而增加。DTPP 算法的運行時間與RM 算法相差不大，都低于5 s，但遠(yuǎn)低于GM 算法。這是因為GM 算法在生成假軌跡時，應(yīng)用枚舉法列舉所有可能的假軌跡，其運行時間隨著位置數(shù)呈指數(shù)增長，而DTPP 算法通過構(gòu)建合理的數(shù)據(jù)結(jié)構(gòu)縮減了假軌跡候選集，節(jié)省了運行時間。

綜上所述，可以得出DTPP 算法在考慮暴露位置的同時，能保持較高的軌跡相似性且花費很少的運行時間，所以DTPP算法能有效保護(hù)用戶的真實軌跡。

4.3 參數(shù)評估

本節(jié)通過實驗評估DTPP 算法涉及的參數(shù)對算法性能的影響。

圖6 軌跡相似性隨k的變化Fig.6 Trajectory similarity varying with k

圖7 軌跡泄漏率隨k的變化Fig.7 Trajectory disclosure rate varying with k

圖8 運行時間隨k的變化Fig.8 Running time varying with k

首先評估暴露位置數(shù)|EL|對軌跡相似性和運行時間的影響。由圖9可知：1）當(dāng)暴露位置數(shù)|EL|在（1，3）區(qū)間時，軌跡相似性隨著暴露位置數(shù)的增加而減?。划?dāng)|EL|＞3 時，軌跡相似性隨著暴露位置數(shù)的增加而增大。這是因為開始時暴露位置數(shù)的增加導(dǎo)致軌跡之間的位置距離差異增大，當(dāng)暴露位置數(shù)增加到一定程度后，軌跡之間重合的部分變多，軌跡相似性相應(yīng)提高。2）DTPP 算法的運行時間隨著暴露位置數(shù)的增加較大幅度地降低，當(dāng)暴露位置數(shù)大于2時，運行時間均低于1 s。這是由于暴露位置數(shù)的增多導(dǎo)致生成候選假位置集和假軌跡集時間大幅減少。

接下來通過位置抑制比來衡量軌跡匿名閾值中的p 對算法的影響。將位置抑制比定義為軌跡中被抑制位置數(shù)占總位置數(shù)的比例。由圖10 可知：位置抑制比隨著位置匿名閾值p的增大而增大，但位置抑制比沒有超過10%，說明DTPP 算法在滿足位置匿名要求的前提下，不需要抑制太多的位置。

圖9 暴露位置數(shù)|EL|對DTPP的影響Fig.9 Effect of|EL|on DTPP

圖10 位置匿名閾值p對DTPP的影響Fig.10 Effect of p on DTPP

5 結(jié)語

本文首次提出應(yīng)用假軌跡保護(hù)軌跡隱私時考慮用戶的暴露位置，并基于此研究了一種軌跡隱私保護(hù)算法DTPP。該算法基于網(wǎng)格查找假位置候選集，并利用軌跡相鄰位置間的時空可達(dá)性構(gòu)建軌跡有向圖存儲假軌跡候選集，建立了啟發(fā)式規(guī)則選擇假軌跡，使得假軌跡在保護(hù)真實軌跡時具有更好的軌跡相似性?；谡鎸嵻壽E數(shù)據(jù)集進(jìn)行實驗，結(jié)果表明DTPP算法能夠有效保護(hù)軌跡隱私免受暴露位置攻擊。由于本文采用真實地圖上的位置點作為假位置，因而適合保護(hù)分布在地理位置密度較密集區(qū)域中的軌跡。對于分布于地理位置密度稀疏的軌跡，需要抑制敏感位置，導(dǎo)致信息損失較大。針對此問題的解決方式，還需要進(jìn)一步研究。