一種路網環境中的軌跡隱私保護技術

霍 崢 王 騰

1(河北經貿大學信息技術學院 河北 石家莊 050061)2(中國電子科技集團第54研究所衛星導航系統與裝備技術國家重點實驗室 河北 石家莊 050000)

?

一種路網環境中的軌跡隱私保護技術

霍 崢1王 騰2

1(河北經貿大學信息技術學院 河北 石家莊 050061)2(中國電子科技集團第54研究所衛星導航系統與裝備技術國家重點實驗室 河北 石家莊 050000)

不經過隱私處理直接發布軌跡數據會導致移動對象的個人隱私泄露，傳統的軌跡隱私保護技術用聚類的方法產生軌跡k-匿名集，只適用在自由空間環境，并不適用于道路網絡環境中。針對上述問題設計了一種路網環境中的軌跡隱私保護方法，將路網環境中的軌跡模擬到無向圖上，并將軌跡k-匿名問題歸結到無向圖的k-node劃分問題上。證明了圖的k-node劃分是NP-完全問題，并提出貪心算法解決此問題。通過實驗驗證了該算法的匿名成功率平均接近60%，最高可達80%以上。

路網 軌跡 隱私保護 數據發布

0 引 言

隨著移動定位技術的迅速發展，出現了大量的帶有移動定位功能的設備，同時也產生了大量的位置數據，位置數據按采樣時間排序形成了軌跡數據。針對軌跡數據的分析和挖掘可以支持多種與移動相關的應用[1-2]。然而，軌跡數據含有豐富的時空信息，針對軌跡數據的分析和挖掘可能導致軌跡數據中包含的個人私密信息泄露。隨著各行各業對軌跡數據應用需求的增長，軌跡隱私保護技術已成為國內外的研究熱點之一[3-5]。研究者們對自由空間中的軌跡隱私保護技術進行了研究，提出了多種基于聚類的軌跡k-匿名技術[6-8]?；诰垲惖膋-匿名技術不適用在路網空間中，且不能合理地分配匿名不成功的軌跡，從而增大了信息丟失。本文針對路網空間的特性，提出一種路網環境中的軌跡隱私保護技術，將軌跡及軌跡之間的關系模擬到無向圖上，將軌跡k-匿名問題轉化為軌跡圖上的k-node劃分問題。本文證明了k-node劃分問題是NP-完全問題，設計了一個貪心算法實現了軌跡圖的k-node劃分，進而實現了軌跡k-匿名。與現有的軌跡隱私保護技術相比，該方法可以解決路網環境中的軌跡隱私保護問題，且該方法能夠系統地解決軌跡k-匿名中刪除的軌跡數量等問題，因此匿名成功率和數據可用性較高，本文通過實驗對算法的可用性和算法效率進行了驗證。

1 問題定義

1.1 預備知識

下面對軌跡等概念進行形式化定義。

定義1 (軌跡) 某個移動對象Op的軌跡是采樣位置按照采樣時間排序的序列，即T={(x1,y1,t1),(x2,y2,t2),…，(xn,yn,tn)}，其中，(xi,yi)表示移動對象Op在ti時刻所處位置的坐標。

定義2 (同步軌跡) 兩條軌跡Tp和Tq是同步軌跡，當且僅當這兩條軌跡在同一采樣時間都有采樣位置。一組軌跡是同步的，則這組軌跡中的每兩條軌跡都是同步的。若兩條軌跡是同步軌跡，同一采樣時間的采樣位置稱為“對應位置”。采用歐幾里德距離來衡量軌跡之間的距離。

定義3 (軌跡距離) 給定兩條同步軌跡Tp和Tq，其軌跡距離是其對應位置的歐幾里德距離的平均值，計算如下：

(1)

其中(xpi,ypi,ti)和(xqi,yqi,ti)分別表示軌跡Tp和Tq在ti時刻的采樣位置。兩條軌跡的采樣位置從t1時刻開始，至tn時刻為止。

用(xs,ys,ts)和(xe,ye,te)分別表示一條軌跡的起始采樣位置和終止采樣位置。起始位置和終止位置在x坐標方向和y坐標方向上可分別表示為兩個位置對(xs,xe)和(ys,ye)。如果兩條軌跡在“時空上沒有任何重疊”，沒有必要計算這兩條軌跡之間的距離，因為這樣的兩條軌跡幾乎不可能被匿名在同一個匿名集中。所謂“時間重疊”是指這兩條軌跡所跨越的時間有交疊，即軌跡T1的結束時間t1e晚于軌跡T2的開始時間t2s。而空間上的重疊用下述定義來描述。

定義4 (s-空間重疊) 給定兩條同步軌跡Tp={(xp1,yp1,t1), (xp2,yp2,tp2), … , (xpn,ypn,tn)} 和Tq={(xq1,yq1,t1), (xq2,yq2,t2), … , (xqn,yqn,tn)} ，若Tp上至少存在一個采樣位置(xi,yi) (i=1, 2, …,n), 滿足xi∈ [xqs,xqe] 或yi∈ [yqs,yqe], 則稱Tp和Tq之間有s-空間重疊, 其中，s(s>0)是Tp和Tq的重疊比例，由重疊采樣位置數與整條軌跡的采樣位置數的比值計算得出。

1.2 問題定義

在定義問題之前，先介紹在路網環境中可能遭遇的兩種攻擊模式。

? 背景知識攻擊:移動對象通過背景知識暴露其所處的位置。比如，兩個移動用戶關于工作地點的談話可能會暴露其中一個用戶日常軌跡的終點或起點。假定攻擊者通過背景知識知曉用戶Op可能會在時刻ti時出現在位置Li,恰好ti是發布的軌跡數據庫D*中，用戶Op的軌跡上的某個采樣位置，這時攻擊者就可以根據這個信息從D*中識別出Op的整條軌跡。這種攻擊模式稱為背景知識攻擊。

? 觀察攻擊:假定攻擊者靜止或者按預定策略運行進行觀察攻擊，假設觀察過程中沒有噪音數據。當攻擊者發現Op出現后,觀察Op至少一個采樣周期以獲得Op在采樣時間時的確切位置。在最壞的情況下，如果Op是該時間段內唯一出現的移動對象，攻擊者可以100%的在發布數據庫D*中識別出Op的整條軌跡。如果同時有N個移動對象出現，且攻擊者沒有其他背景知識，那么識別出Op軌跡的概率下降為1/N，這種攻擊模式稱為觀察攻擊。當然，觀察攻擊者不僅僅指個人，還可能是各種各樣的數據采集器，如商場中的攝像頭、道路上的監控設備等。

軌跡k-匿名技術可以抵御上述兩種攻擊類型，軌跡-匿名是指將k條軌跡匿名在同一個匿名集中，最終發布的匿名集是各個采樣時刻由k個用戶共享的匿名區域。對于背景知識攻擊來說，由于軌跡k-匿名將各個時刻的采樣位置匿名為包含k個用戶位置的匿名區域，攻擊者沒有辦法將背景知識與一個區域中的多個位置連接起來。軌跡k-匿名對觀察攻擊同樣有效：假定攻擊者觀察到Op在某個時刻出現在某個位置，攻擊者還是無法從發布的k個用戶的匿名軌跡中直接識別出Op的軌跡。

然而，把k條軌跡匿名會造成嚴重的信息丟失。因此，軌跡隱私保護技術的關鍵問題是：如何在保護軌跡隱私的前提下將信息丟失降到最低。本文提出一種方法將軌跡隱私保護問題歸結到一個圖的k-node劃分問題上，該問題是一個NP-完全問題，本文提出一種貪心算法來構造軌跡k-匿名集。

定義5 (軌跡k-匿名) 給定移動對象數據庫D，發布的軌跡數據庫D*是D的匿名版本，需滿足以下兩個條件：

? 發布數據庫D*中每條軌跡的采樣位置都至少和其它k-1條軌跡匿名在同一個匿名集中。

? 發布數據庫D*相對于原始數據庫D的信息丟失最小。

軌跡k-匿名可以抵御上述兩種攻擊模式：對于發布數據庫D*來說，即使攻擊者知曉多少條軌跡匿名在同一個匿名集中以，其識別一條軌跡的概率小于1/k。

2 隱私保護算法

2.1 數據預處理

數據預處理階段需要完成下述兩個任務：軌跡起始及終止點識別、構建軌跡等價類。

軌跡起始及終止點識別：移動對象的一條完整的軌跡中可能包含多個長時間的停留。軌跡起始及終止點識別就是要識別哪些采樣位置屬于長時間停留，哪些采樣位置是軌跡的終止位置。如果移動對象Op在某個采樣位置的停留時間超過事先設定的閾值tht，就認為Op的軌跡在這個停留位置終止了，下一個采樣位置成為Op的新軌跡的起始位置。

構建軌跡等價類：由于軌跡k-匿名僅僅能夠將出現在相同時間段的軌跡匿名在同一個匿名集中。為了能夠擴大同一個時間段內軌跡等價類中所含軌跡的數量，需要把起始時間在[tds1,tds2]范圍內，及終止時間在[tde1,tde2]范圍內的軌跡放入同一個等價類中。軌跡等價類的定義如下。

定義6 (軌跡等價類) 軌跡等價類由起始及終止時間在相近時間段的軌跡構成。兩條軌跡Tp和Tq在同一個等價類中，當且僅當Tp.ts,Tq.ts∈[tds1,tds2]且Tp.te,Tq.te∈[tde1,tde2]。

2.2 軌跡圖構建

本節首先介紹軌跡圖的定義，然后介紹軌跡圖的構建過程。

定義7 (軌跡圖) 軌跡圖TG=(V,E)是一個帶權無向圖，其中，頂點集V表示軌跡，兩個頂點之間有邊，當且僅當兩條軌跡Tp和Tq之間有s-重疊。邊(Tp,Tq)的權值是軌跡Tp和Tq之間的距離。

對軌跡等價類EC構造軌跡圖TG=(V,E)的過程如下所述：初始時軌跡圖的邊集為空，頂點集為軌跡等價類中任意一條軌跡T1，未被加入到軌跡圖中的軌跡放入集合Vleft中。然后，檢查Vleft中的每條軌跡是否和V中的軌跡有s-重疊。如果兩條軌跡Ti和Tj之間有s-重疊，則計算兩條軌跡之間的距離作為這兩條軌跡之間的邊的權值，并將這條軌跡從Vleft移動到V中。如果沒有s-重疊，僅把這條軌跡移動到V中，不需要計算軌跡距離。由于多數軌跡之間并不存在s-重疊關系，因此軌跡圖極可能是由多個連通分量構成的非連通圖。如果兩條軌跡之間沒有s-重疊，也不需要計算軌跡距離，節省了計算資源。

2.3 軌跡匿名

為了控制每個軌跡匿名集中的軌跡數量，系統的對匿名失敗的軌跡進行分配，文章把軌跡k-匿名問題歸結到圖劃分問題上。通過對圖中頂點的劃分來構建軌跡匿名集。最理想的情況是：劃分后的每個子圖是一個包含k個頂點的連通分量，并且耗費最少。

2.3.1k-node劃分

軌跡k-匿名所用到的k-node劃分和k-way劃分不同,其形式化定義如下：

定義8 (k-node劃分) 關于軌跡圖TG的一個k-node劃分是指：將圖TG劃分為若干個連通分量V1,V2,…,Vi及D1,D2,…,Dh，滿足如下條件：

?V1∪V2∪…Vi∪D1∪D2∪…∪Dh=TG;

? 對任意i,k≤|Vi|≤2k-1且|Di|

?Vi∩Vj=φ;Di∩Dj=φ且Di∩Vj=φ;

?Wi表示子圖Ti的權值之和,且Wi的值最小，h盡可能小。

在k-node劃分中，V1,V2,…,Vi構成了軌跡k-匿名集，每個軌跡k-匿名集中包含至少k個頂點，D1,D2,…,Dh表示要被刪除的子圖，因為上述子圖中包含的頂點數都不夠k個，達不到隱私保護參數k的需求。第4個條件表示匿名集中的權值之和應盡可能小，且被刪除的子圖數量應盡可能小。被刪除子圖可能是由下述三個原因產生的：第一種情況：TG是一個由幾個連通分量構成的非連通圖，如果某個連通分量的頂點數小于k，就無法被劃分到其它子圖中，因此被刪除。第二種情況：TG中的連通分量包含的頂點數大于k，但是由于構成k-匿名集后刪除一些頂點，連通分量中剩余的頂點數不足k；第三種情況：整個軌跡圖TG是連通分量，若其頂點數n滿足nmodk≠0，則構成幾個軌跡k-匿名集后，剩下的軌跡就是多余的。

為了達到降低信息丟失的目的，需要對k-node劃分做出如下兩個限制：第一，對于每個劃分好的子圖，其權值之和ICost最小，稱子圖的權值之和為“內部信息丟失”；第二，刪除的子圖越少越好。

下面證明k-node劃分是一個NP-完全問題。

定理1 k-node劃分問題是一個NP-完全問題。

2.3.2 貪心算法

已經證明了k-node劃分是NP-完全問題，本節就采用一種貪心方法找到軌跡圖的一個k-node劃分。

TG是一個有n個頂點的圖，通過下述GreedyFindC算法可以將圖TG進行k-node劃分。對于TG中的每個連通分量，調用算法GreedyFindC，直到TG中沒有任何連通分量的頂點數大于或等于k。算法中有兩個子圖集合，子圖集合RS保存了所有可能構成軌跡k-匿名集的子圖；子圖DS保存了不足k個頂點的子圖，需要被刪除。在算法GreedyFindC中，采用一種貪心策略來劃分TG?；舅枷刖褪钦业竭厵嘧钚〉倪叄瑢⑺鳛樽訄D的邊，除非刪除這條邊會造成一個新的頂點數小于k的連通分量。算法從圖中權值最小的邊出發，這條邊關聯的兩個頂點構成連通分量C，頂點入棧SC,和連通分量C相鄰接的所有頂點放入集合X中。當連通分量C中的頂點數小于k時，每次找到和C相關聯的，且邊權最小的那條邊加入新的連通分量，頂點放入C。當連通分量C中的頂點數達到k時，試著將C從連通分量Gi中刪除。在刪除之前，首先檢查刪除掉C之后是不是會構成新的頂點數小于k的連通分量，如果是，就嘗試換一條邊加入連通分量C，再次檢查。檢查完畢之后發現無論怎樣都會產生新的頂點數小于k的連通分量，那么還是回到最初的那條邊，然后從Gi中將C刪除。GreedyFindC算法如下：

算法1 GreedyFindC(Gi, k)

輸入：連通分量Gi=(V, E); 每個子圖中含有頂點數k；

輸出：含有k個頂點的子圖C；

1: Token=0; X←?;

2: 找到權值最小的邊e=(vs, ve),將vs,ve放入C；

3: Push(SC, vs); Push(SC, ve);//SC是初始化為空的棧；

4: X←和子圖C中的頂點相鄰接的邊x；

5: while |C|

6: if (X=?) then

7: X←和子圖C中的頂點相鄰接的邊x；

8: end if

9: 找到X中權值最小的邊e=(vi, vj)； Push(SC, vj)；

10: X←和C中結點相鄰接但不包含在C中的邊；

11: if |C| =k and token =0 then

12: Gi←delete-detection (Gi, C);

13: if存在GSi∈Gi且|GSi|

14: C←SC中元素出棧后的剩余元素；

15: if X中僅包含(vs, ve) then

16: token=1; C← (vs, ve);

17: end if

18: else

19: Gi←Gi-C; return C;

20: end if

21: else if |C|>=k 且token=1 then

22: Gi←Gi-C; return C;

23: end if

24: end while

2.3.3 信息丟失衡量

(2)

信息丟失由兩部分構成，一是將一個采樣位置匿名為一個區域，導致數據可用性的下降；二是被刪除的軌跡導致數據完全丟失。在上述公式中，Area(xj,yj,tj)表示采樣位置(xj,yj,tj)對應的匿名區域面積大小，MaxArea表示整個地圖的面積。如果軌跡Ti被刪除，則其所有信息都丟失了，即所有采樣位置都被丟失了。

3 實驗分析

3.1 實驗設置

實驗選取了合成數據和真實數據來衡量算法的可用性和效率。真實數據集名為TRUCKS，它包含了50個卡車33天時間里在希臘雅典周邊建筑地區運輸混凝土的軌跡。另外一個數據集OLDEN是由著名的Brinkhoff Generator生成的，該數據集表示為OLDEN。生成器使用的是Oldenburg的路網數據，整個城市區域的面積為23.57 km×26.92 km，它包含了6 105個節點和7 035條邊。實驗生成了10 000個移動對象在150個時刻的位置數據。

表1展示了兩個數據集在預處理之后的特征。|D|表示在預處理之后的軌跡數目;|Dec|表示每個數據集中的等價類的數目；MaxNo和MinNo分別表示等價類中最多軌跡數目和最小軌跡數目；Ratio表示在每個等價類中軌跡s-重疊的平均比例?？梢钥闯?，TRUCKS數據集比OLDENBURG數據集稀疏,也就是說TRUCKS軌跡集的軌跡數目少，且分布空間更大。

表1 數據集特性

3.2 數據可用性

數據可用性主要用信息丟失來衡量。本文在TRUCKS和OLDENBURG數據集上分別衡量了信息丟失。圖1展示了在兩個數據集上的信息丟失的結果。由于TRUCKS比OLDENBURG稀疏，所以設置了不同的k值。從圖1中可以看出，信息丟失隨著k的增長逐漸增大，這是因為k值越大，匿名區域面積越大，因此信息丟失越大。從另一方面來說，隨著k的增大，匿名失敗率也會增大，刪除的軌跡數目增多，信息丟失也會增大。然而，信息丟失的增長是比較穩定的，也就是說k值的增大不會造成信息丟失的急劇增長。

圖1 信息丟失衡量

匿名成功率是指成功匿名的軌跡數目占所有軌跡數目的比例。實驗分別在TRUCKS和OLDENBURG數據集上測試了匿名成功率，實驗結果展示在圖2中。從圖中可以看出，在OLCENBURG數據集上，盡管匿名成功率隨k的增大而降低，但匿名成功率仍大于65%，最高可達80%。

圖2 匿名成功率

3.3 算法效率

貪心k-node劃分算法是由Java實現的，實驗運行的CPU是1.4 GB Intel Core i5，內存為4 GB，操作系統是Windows 7。

算法耗費13 897 ms預處了OLDENBURG數據集，花費194 732 ms構建了132個軌跡圖。算法預處理TRUCKS數據集耗費了10 072 ms，花費了5 455 ms構建了154個軌跡圖。圖3展示了貪心k-node劃分算法的運行時間。

圖3 算法運行時間

數據集TRUCKS比OLDENBURG數據集小，因此，貪心k-node劃分算法在TRUCKS上比在OLDENBURG上的運行的更快。在兩個數據集上，運行時間隨著k的增大而增加，這是由于k的增大會導致劃分時，嘗試刪除一個k個頂點的子圖將花費更多時間。

4 結 語

本文提出了一種路網環境中基于圖劃分的軌跡隱私保護技術，通過將軌跡數據模擬到無向圖中，利用圖的k-node劃分實現軌跡k-匿名，實驗驗證了算法的有效性。

[1] Pan X, Wu L, Hu Z, et al. Voronoi-based spatial cloaking algorithm over road network [C]// 25th DEXA Conference and workshops, September 1-4, 2014, Munich, Germany, Springer, 2014: 273-280.

[2] Pan X, Chen W, Wu L, et al. Protecting personalized privacy against sensitivity homogeneity attacks over road networks in mobile services[J]. Frontiers of Computer Science, 2016, 10(2):370-386.

[3] Chen R, Fung B C M, Desai B C, et al. Differentially private transit data publication: a case study on the Montreal transportation system[C]// 18th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, August 12-16, 2012, Beijing, China, ACM, 2012: 213-221.

[4] Hay M, Rastogi V, Miklau G, et al. Boosting the accuracy of differentially private histograms through consistency[J]. Proceedings of VLDB Endowment,2010,3(1):1021-1032.

[5] Sui P, Wo T, Wen Z, et al. Privacy-preserving trajectory publication against parking point attacks[C]// 2013 IEEE 10th International Conference on Ubiquitous Intelligence and Computing and 2013 IEEE 10th International Conference on Autonomic and Trusted Computing, December 18-21, 2013, Vietri sul Mare, Sorrento Peninsula, Italy, IEEE Computer Society, 2013: 569-574.

[6] Seidl E D, Jankowski P, Tsou M-H. Privacy and spatial pattern preservation in masked GPS trajectory data[J]. International Journal of Geographical Information Science,2016,30(4):785-800.

[7] Cao Y, Yoshikawa M. Differentially Private Real-Time Data Publishing over Infinite Trajectory Streams[J]. Ieice Transactions on Information & Systems, 2016, 99(1):68-73.

[8] Abul O, Bonchi F, Giannotti F. Hiding sequential and spatiotemporal patterns [J]. IEEE Transactions on Knowledge and Data Engineering, 2010, 22(12): 1709-1723.

A TRAJECTORY PRIVACY PROTECTION TECHNOLOGY IN ROAD NETWORK ENVIRONMENT

Huo Zheng1Wang Teng2

1(SchoolofInformationTechnology,HebeiUniversityofEconomicsandBusiness,Shijiazhuang050061,Hebei,China)2(StateKeyLaboratoryofSatelliteNavigationSystemandEquipmentTechnology,No.54Institution,ChinaElectronicsTechnologyGroupCorporation,Shijiazhuang050000,Hebei,China)

Directly publishing trajectory data without privacy processing can result in the disclosure of personal privacy of the moving object. Traditional trajectory privacy protection technology uses the method of clustering to generate trajectory k-anonymous set, which only applies to free space environment and does not apply to road network environment. A trajectory privacy protection method in road network environment was designed to simulate the trajectory in the road network environment to an undirected graph, and the k-anonymity problem was reduced to the k-node partition problem of undirected graphs. It was proved that the k-node partition of the graph is an NP-complete problem and a greedy algorithm was proposed to solve this problem. The anonymous success rate of the algorithm was verified to be close to 60% on average, and the maximum is over 80%.

Road-network Trajectory Privacy protection Data publication

2016-06-02。國家自然科學基金項目(61303017)；河北省自然科學基金項目(F2015207009)；河北省高等學?？茖W研究項目(BJ2016019)?；魨槪v師，主研領域：移動對象數據庫，隱私保護技術。王騰，高工。

TP3

A

10.3969/j.issn.1000-386x.2017.07.057