一種路網(wǎng)環(huán)境中的軌跡隱私保護(hù)技術(shù)

霍 崢 王 騰

1(河北經(jīng)貿(mào)大學(xué)信息技術(shù)學(xué)院 河北 石家莊 050061)2(中國(guó)電子科技集團(tuán)第54研究所衛(wèi)星導(dǎo)航系統(tǒng)與裝備技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室 河北 石家莊 050000)

?

一種路網(wǎng)環(huán)境中的軌跡隱私保護(hù)技術(shù)

霍 崢1王 騰2

1(河北經(jīng)貿(mào)大學(xué)信息技術(shù)學(xué)院 河北 石家莊 050061)2(中國(guó)電子科技集團(tuán)第54研究所衛(wèi)星導(dǎo)航系統(tǒng)與裝備技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室 河北 石家莊 050000)

不經(jīng)過(guò)隱私處理直接發(fā)布軌跡數(shù)據(jù)會(huì)導(dǎo)致移動(dòng)對(duì)象的個(gè)人隱私泄露，傳統(tǒng)的軌跡隱私保護(hù)技術(shù)用聚類的方法產(chǎn)生軌跡k-匿名集，只適用在自由空間環(huán)境，并不適用于道路網(wǎng)絡(luò)環(huán)境中。針對(duì)上述問(wèn)題設(shè)計(jì)了一種路網(wǎng)環(huán)境中的軌跡隱私保護(hù)方法，將路網(wǎng)環(huán)境中的軌跡模擬到無(wú)向圖上，并將軌跡k-匿名問(wèn)題歸結(jié)到無(wú)向圖的k-node劃分問(wèn)題上。證明了圖的k-node劃分是NP-完全問(wèn)題，并提出貪心算法解決此問(wèn)題。通過(guò)實(shí)驗(yàn)驗(yàn)證了該算法的匿名成功率平均接近60%，最高可達(dá)80%以上。

路網(wǎng) 軌跡 隱私保護(hù) 數(shù)據(jù)發(fā)布

0 引 言

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

1 問(wèn)題定義

1.1 預(yù)備知識(shí)

下面對(duì)軌跡等概念進(jìn)行形式化定義。

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

定義2 (同步軌跡) 兩條軌跡Tp和Tq是同步軌跡，當(dāng)且僅當(dāng)這兩條軌跡在同一采樣時(shí)間都有采樣位置。一組軌跡是同步的，則這組軌跡中的每?jī)蓷l軌跡都是同步的。若兩條軌跡是同步軌跡，同一采樣時(shí)間的采樣位置稱為“對(duì)應(yīng)位置”。采用歐幾里德距離來(lái)衡量軌跡之間的距離。

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

(1)

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

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

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

1.2 問(wèn)題定義

在定義問(wèn)題之前，先介紹在路網(wǎng)環(huán)境中可能遭遇的兩種攻擊模式。

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

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

軌跡k-匿名技術(shù)可以抵御上述兩種攻擊類型，軌跡-匿名是指將k條軌跡匿名在同一個(gè)匿名集中，最終發(fā)布的匿名集是各個(gè)采樣時(shí)刻由k個(gè)用戶共享的匿名區(qū)域。對(duì)于背景知識(shí)攻擊來(lái)說(shuō)，由于軌跡k-匿名將各個(gè)時(shí)刻的采樣位置匿名為包含k個(gè)用戶位置的匿名區(qū)域，攻擊者沒(méi)有辦法將背景知識(shí)與一個(gè)區(qū)域中的多個(gè)位置連接起來(lái)。軌跡k-匿名對(duì)觀察攻擊同樣有效：假定攻擊者觀察到Op在某個(gè)時(shí)刻出現(xiàn)在某個(gè)位置，攻擊者還是無(wú)法從發(fā)布的k個(gè)用戶的匿名軌跡中直接識(shí)別出Op的軌跡。

然而，把k條軌跡匿名會(huì)造成嚴(yán)重的信息丟失。因此，軌跡隱私保護(hù)技術(shù)的關(guān)鍵問(wèn)題是：如何在保護(hù)軌跡隱私的前提下將信息丟失降到最低。本文提出一種方法將軌跡隱私保護(hù)問(wèn)題歸結(jié)到一個(gè)圖的k-node劃分問(wèn)題上，該問(wèn)題是一個(gè)NP-完全問(wèn)題，本文提出一種貪心算法來(lái)構(gòu)造軌跡k-匿名集。

定義5 (軌跡k-匿名) 給定移動(dòng)對(duì)象數(shù)據(jù)庫(kù)D，發(fā)布的軌跡數(shù)據(jù)庫(kù)D*是D的匿名版本，需滿足以下兩個(gè)條件：

? 發(fā)布數(shù)據(jù)庫(kù)D*中每條軌跡的采樣位置都至少和其它k-1條軌跡匿名在同一個(gè)匿名集中。

? 發(fā)布數(shù)據(jù)庫(kù)D*相對(duì)于原始數(shù)據(jù)庫(kù)D的信息丟失最小。

軌跡k-匿名可以抵御上述兩種攻擊模式：對(duì)于發(fā)布數(shù)據(jù)庫(kù)D*來(lái)說(shuō)，即使攻擊者知曉多少條軌跡匿名在同一個(gè)匿名集中以，其識(shí)別一條軌跡的概率小于1/k。

2 隱私保護(hù)算法

2.1 數(shù)據(jù)預(yù)處理

數(shù)據(jù)預(yù)處理階段需要完成下述兩個(gè)任務(wù)：軌跡起始及終止點(diǎn)識(shí)別、構(gòu)建軌跡等價(jià)類。

軌跡起始及終止點(diǎn)識(shí)別：移動(dòng)對(duì)象的一條完整的軌跡中可能包含多個(gè)長(zhǎng)時(shí)間的停留。軌跡起始及終止點(diǎn)識(shí)別就是要識(shí)別哪些采樣位置屬于長(zhǎng)時(shí)間停留，哪些采樣位置是軌跡的終止位置。如果移動(dòng)對(duì)象Op在某個(gè)采樣位置的停留時(shí)間超過(guò)事先設(shè)定的閾值tht，就認(rèn)為Op的軌跡在這個(gè)停留位置終止了，下一個(gè)采樣位置成為Op的新軌跡的起始位置。

構(gòu)建軌跡等價(jià)類：由于軌跡k-匿名僅僅能夠?qū)⒊霈F(xiàn)在相同時(shí)間段的軌跡匿名在同一個(gè)匿名集中。為了能夠擴(kuò)大同一個(gè)時(shí)間段內(nèi)軌跡等價(jià)類中所含軌跡的數(shù)量，需要把起始時(shí)間在[tds1,tds2]范圍內(nèi)，及終止時(shí)間在[tde1,tde2]范圍內(nèi)的軌跡放入同一個(gè)等價(jià)類中。軌跡等價(jià)類的定義如下。

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

2.2 軌跡圖構(gòu)建

本節(jié)首先介紹軌跡圖的定義，然后介紹軌跡圖的構(gòu)建過(guò)程。

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

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

2.3 軌跡匿名

為了控制每個(gè)軌跡匿名集中的軌跡數(shù)量，系統(tǒng)的對(duì)匿名失敗的軌跡進(jìn)行分配，文章把軌跡k-匿名問(wèn)題歸結(jié)到圖劃分問(wèn)題上。通過(guò)對(duì)圖中頂點(diǎn)的劃分來(lái)構(gòu)建軌跡匿名集。最理想的情況是：劃分后的每個(gè)子圖是一個(gè)包含k個(gè)頂點(diǎn)的連通分量，并且耗費(fèi)最少。

2.3.1k-node劃分

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

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

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

? 對(duì)任意i,k≤|Vi|≤2k-1且|Di|

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

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

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

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

下面證明k-node劃分是一個(gè)NP-完全問(wèn)題。

定理1 k-node劃分問(wèn)題是一個(gè)NP-完全問(wèn)題。

2.3.2 貪心算法

已經(jīng)證明了k-node劃分是NP-完全問(wèn)題，本節(jié)就采用一種貪心方法找到軌跡圖的一個(gè)k-node劃分。

TG是一個(gè)有n個(gè)頂點(diǎn)的圖，通過(guò)下述GreedyFindC算法可以將圖TG進(jìn)行k-node劃分。對(duì)于TG中的每個(gè)連通分量，調(diào)用算法GreedyFindC，直到TG中沒(méi)有任何連通分量的頂點(diǎn)數(shù)大于或等于k。算法中有兩個(gè)子圖集合，子圖集合RS保存了所有可能構(gòu)成軌跡k-匿名集的子圖；子圖DS保存了不足k個(gè)頂點(diǎn)的子圖，需要被刪除。在算法GreedyFindC中，采用一種貪心策略來(lái)劃分TG?；舅枷刖褪钦业竭厵?quán)最小的邊，將它作為子圖的邊，除非刪除這條邊會(huì)造成一個(gè)新的頂點(diǎn)數(shù)小于k的連通分量。算法從圖中權(quán)值最小的邊出發(fā)，這條邊關(guān)聯(lián)的兩個(gè)頂點(diǎn)構(gòu)成連通分量C，頂點(diǎn)入棧SC,和連通分量C相鄰接的所有頂點(diǎn)放入集合X中。當(dāng)連通分量C中的頂點(diǎn)數(shù)小于k時(shí)，每次找到和C相關(guān)聯(lián)的，且邊權(quán)最小的那條邊加入新的連通分量，頂點(diǎn)放入C。當(dāng)連通分量C中的頂點(diǎn)數(shù)達(dá)到k時(shí)，試著將C從連通分量Gi中刪除。在刪除之前，首先檢查刪除掉C之后是不是會(huì)構(gòu)成新的頂點(diǎn)數(shù)小于k的連通分量，如果是，就嘗試換一條邊加入連通分量C，再次檢查。檢查完畢之后發(fā)現(xiàn)無(wú)論怎樣都會(huì)產(chǎn)生新的頂點(diǎn)數(shù)小于k的連通分量，那么還是回到最初的那條邊，然后從Gi中將C刪除。GreedyFindC算法如下：

算法1 GreedyFindC(Gi, k)

輸入：連通分量Gi=(V, E); 每個(gè)子圖中含有頂點(diǎn)數(shù)k；

輸出：含有k個(gè)頂點(diǎn)的子圖C；

1: Token=0; X←?;

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

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

4: X←和子圖C中的頂點(diǎn)相鄰接的邊x；

5: while |C|

6: if (X=?) then

7: X←和子圖C中的頂點(diǎn)相鄰接的邊x；

8: end if

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

10: X←和C中結(jié)點(diǎn)相鄰接但不包含在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)

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

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)選取了合成數(shù)據(jù)和真實(shí)數(shù)據(jù)來(lái)衡量算法的可用性和效率。真實(shí)數(shù)據(jù)集名為TRUCKS，它包含了50個(gè)卡車33天時(shí)間里在希臘雅典周邊建筑地區(qū)運(yùn)輸混凝土的軌跡。另外一個(gè)數(shù)據(jù)集OLDEN是由著名的Brinkhoff Generator生成的，該數(shù)據(jù)集表示為OLDEN。生成器使用的是Oldenburg的路網(wǎng)數(shù)據(jù)，整個(gè)城市區(qū)域的面積為23.57 km×26.92 km，它包含了6 105個(gè)節(jié)點(diǎn)和7 035條邊。實(shí)驗(yàn)生成了10 000個(gè)移動(dòng)對(duì)象在150個(gè)時(shí)刻的位置數(shù)據(jù)。

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

表1 數(shù)據(jù)集特性

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

數(shù)據(jù)可用性主要用信息丟失來(lái)衡量。本文在TRUCKS和OLDENBURG數(shù)據(jù)集上分別衡量了信息丟失。圖1展示了在兩個(gè)數(shù)據(jù)集上的信息丟失的結(jié)果。由于TRUCKS比OLDENBURG稀疏，所以設(shè)置了不同的k值。從圖1中可以看出，信息丟失隨著k的增長(zhǎng)逐漸增大，這是因?yàn)閗值越大，匿名區(qū)域面積越大，因此信息丟失越大。從另一方面來(lái)說(shuō)，隨著k的增大，匿名失敗率也會(huì)增大，刪除的軌跡數(shù)目增多，信息丟失也會(huì)增大。然而，信息丟失的增長(zhǎng)是比較穩(wěn)定的，也就是說(shuō)k值的增大不會(huì)造成信息丟失的急劇增長(zhǎng)。

圖1 信息丟失衡量

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

圖2 匿名成功率

3.3 算法效率

貪心k-node劃分算法是由Java實(shí)現(xiàn)的，實(shí)驗(yàn)運(yùn)行的CPU是1.4 GB Intel Core i5，內(nèi)存為4 GB，操作系統(tǒng)是Windows 7。

算法耗費(fèi)13 897 ms預(yù)處了OLDENBURG數(shù)據(jù)集，花費(fèi)194 732 ms構(gòu)建了132個(gè)軌跡圖。算法預(yù)處理TRUCKS數(shù)據(jù)集耗費(fèi)了10 072 ms，花費(fèi)了5 455 ms構(gòu)建了154個(gè)軌跡圖。圖3展示了貪心k-node劃分算法的運(yùn)行時(shí)間。

圖3 算法運(yùn)行時(shí)間

數(shù)據(jù)集TRUCKS比OLDENBURG數(shù)據(jù)集小，因此，貪心k-node劃分算法在TRUCKS上比在OLDENBURG上的運(yùn)行的更快。在兩個(gè)數(shù)據(jù)集上，運(yùn)行時(shí)間隨著k的增大而增加，這是由于k的增大會(huì)導(dǎo)致劃分時(shí)，嘗試刪除一個(gè)k個(gè)頂點(diǎn)的子圖將花費(fèi)更多時(shí)間。

4 結(jié) 語(yǔ)

本文提出了一種路網(wǎng)環(huán)境中基于圖劃分的軌跡隱私保護(hù)技術(shù)，通過(guò)將軌跡數(shù)據(jù)模擬到無(wú)向圖中，利用圖的k-node劃分實(shí)現(xiàn)軌跡k-匿名，實(shí)驗(yàn)驗(yàn)證了算法的有效性。

[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。國(guó)家自然科學(xué)基金項(xiàng)目(61303017)；河北省自然科學(xué)基金項(xiàng)目(F2015207009)；河北省高等學(xué)?？茖W(xué)研究項(xiàng)目(BJ2016019)?；魨?，講師，主研領(lǐng)域：移動(dòng)對(duì)象數(shù)據(jù)庫(kù)，隱私保護(hù)技術(shù)。王騰，高工。

TP3

A

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