霍 崢，王衛(wèi)紅，曹玉輝

(河北經(jīng)貿(mào)大學(xué) 信息技術(shù)學(xué)院，石家莊 050061)(*通信作者電子郵箱huozheng123@gmail.com)

PTDC:路網(wǎng)環(huán)境中感知隱私的軌跡數(shù)據(jù)采集技術(shù)

霍 崢*，王衛(wèi)紅，曹玉輝

(河北經(jīng)貿(mào)大學(xué) 信息技術(shù)學(xué)院，石家莊 050061)(*通信作者電子郵箱huozheng123@gmail.com)

針對路網(wǎng)環(huán)境中移動對象軌跡隱私泄露以及語義位置同質(zhì)性攻擊等問題，提出了一種路網(wǎng)環(huán)境中感知隱私的軌跡數(shù)據(jù)采集(PTDC)算法。首先，通過興趣位置(POI)訪問人次的信息墑計(jì)算路網(wǎng)中POI的敏感性；其次，根據(jù)頂點(diǎn)間敏感性和距離的混合差距，定義了θ-邊權(quán)，并建立路網(wǎng)空間的圖模型、定義了k-θ-D匿名模型以抵御語義位置同質(zhì)性攻擊；最后，以無向圖的廣度優(yōu)先遍歷為基礎(chǔ)，設(shè)計(jì)了滿足POI語義差異性的匿名算法，將用戶的敏感采樣位置用匿名區(qū)域取代，并衡量了PTDC算法處理后數(shù)據(jù)的可用性。通過實(shí)驗(yàn)對PTDC算法進(jìn)行了驗(yàn)證，并和自由空間中的基于語義位置的隱私保護(hù)算法——YCWA進(jìn)行了比對。理論上講，YCWA算法的隱私保護(hù)度低于PTDC算法。實(shí)驗(yàn)表明，PTDC算法的信息丟失率平均在15%左右，空間范圍查詢誤差平均在12%左右，略遜于YCWA算法；然而，PTDC算法的運(yùn)行時(shí)間在5 s以內(nèi)，遠(yuǎn)遠(yuǎn)優(yōu)于YCWA算法，可滿足實(shí)時(shí)在線數(shù)據(jù)采集的需求。

路網(wǎng)；隱私保護(hù)；軌跡數(shù)據(jù)；數(shù)據(jù)采集；語義位置

0 引言

近年來，移動定位技術(shù)、基于位置的服務(wù)的發(fā)展及智能手機(jī)的普及使得大量的移動位置數(shù)據(jù)被各機(jī)構(gòu)采集和存儲。從數(shù)據(jù)挖掘與知識發(fā)現(xiàn)的角度來講，大量的個(gè)人位置數(shù)據(jù)價(jià)值很高，可協(xié)助政府機(jī)構(gòu)及各種商業(yè)機(jī)構(gòu)作出與位置服務(wù)相關(guān)的決策。例如，如何規(guī)劃公交車路線使得乘客數(shù)量與行進(jìn)路線達(dá)到最優(yōu)化？哪個(gè)商業(yè)地段人流量較大適合開設(shè)商鋪等。但是軌跡中包含的信息可能導(dǎo)致個(gè)人隱私的泄露，比如，該用戶所處的位置的泄露、用戶的行進(jìn)軌跡的泄露等。所謂個(gè)人隱私，指的是個(gè)人不愿被外界知曉的信息，如個(gè)人的健康狀況、政治信仰、興趣愛好等[1]。針對這些問題，學(xué)者們對查詢隱私保護(hù)技術(shù)和位置隱私保護(hù)技術(shù)進(jìn)行了深入的研究，并得出一些重要的結(jié)論。近年來，軌跡隱私保護(hù)技術(shù)得到了研究者們的關(guān)注。然而，在數(shù)據(jù)發(fā)布過程中的軌跡隱私保護(hù)假設(shè)服務(wù)器或數(shù)據(jù)收集機(jī)構(gòu)都是可信的，將原始軌跡數(shù)據(jù)可直接發(fā)送給數(shù)據(jù)收集者。甚至有些智能手機(jī)在用戶不知情的情況下，每隔一段時(shí)間向手機(jī)生產(chǎn)商發(fā)送一個(gè)位置數(shù)據(jù)。若原始數(shù)據(jù)泄露，會導(dǎo)致大量用戶的隱私泄露，文獻(xiàn)[2]指出：由于隱私泄露導(dǎo)致的各種社會事件層出不窮。

另外，目前的軌跡隱私保護(hù)技術(shù)有：添加噪聲數(shù)據(jù)[3-4]、軌跡片段抑制[5]及k-匿名技術(shù)[6-10]。其中，軌跡k-匿名是最常用的技術(shù)，該技術(shù)將k條軌跡上對應(yīng)的采樣位置匿名在同一個(gè)區(qū)域中。然而，軌跡k-匿名技術(shù)存在如下問題：第一，軌跡k-匿名形成的匿名區(qū)域是由用戶軌跡上的采樣位置構(gòu)成的，因此，匿名區(qū)域中的位置極可能因缺乏多樣性而導(dǎo)致用戶的隱私泄露。如圖1(a)所示，在路網(wǎng)環(huán)境中，將路段v0→v1→v2→v3→v4上的T1,T2,T3三條軌跡匿名為圖1(b)所示的效果，達(dá)到軌跡3-匿名，即便如此，攻擊者很容易知曉任一用戶的行進(jìn)路線，因?yàn)?條軌跡都在路網(wǎng)中的同一條路徑上。第二，單純的軌跡k-匿名并不適用于路網(wǎng)空間中的軌跡隱私保護(hù)，這是由于在路網(wǎng)空間中，攻擊者的背景知識更加豐富，文獻(xiàn)[11]指出：地圖上的道路特征(單行道、岔路口)、人流量的密度、移動對象的最大運(yùn)行速度等信息都可作為攻擊者的背景知識。

圖1 路網(wǎng)中的軌跡3-匿名

在路網(wǎng)環(huán)境中，僅有語義位置才可能泄露用戶的個(gè)人隱私，其他位置并不會泄露用戶的個(gè)人隱私。文獻(xiàn)[3]提出了一種路網(wǎng)環(huán)境中添加假位置的軌跡隱私保護(hù)技術(shù)，然而，路網(wǎng)信息是攻擊者掌握的背景知識，通過路網(wǎng)信息很容易分析哪些是假位置，帶來隱私泄露風(fēng)險(xiǎn)。針對上述問題，本文提出感知隱私的軌跡數(shù)據(jù)采集方法PTDC。與軌跡k-匿名技術(shù)不同，該方法不對移動對象的軌跡進(jìn)行匿名，而是對地圖上的興趣位置進(jìn)行匿名，根據(jù)軌跡的行進(jìn)方向、道路特征等信息，將用戶的軌跡實(shí)時(shí)匿名，并將匿名后的數(shù)據(jù)發(fā)送給服務(wù)器或數(shù)據(jù)收集機(jī)構(gòu)。該方法可在路網(wǎng)環(huán)境背景知識豐富的情況下，達(dá)到軌跡匿名的效果。從數(shù)據(jù)可用性的角度來講，本文的做法也是可行的，這是由于對大多數(shù)位置數(shù)據(jù)分析來說，并不需要查詢某個(gè)移動對象的確切位置，僅需查詢某一區(qū)域內(nèi)移動對象的數(shù)量即可，即，在空間范圍查詢上的誤差率越小越好。

具體來說，本文的主要貢獻(xiàn)如下：

1)本文提出一種感知隱私的軌跡數(shù)據(jù)采集方法PTDC，可在移動對象運(yùn)行過程中，實(shí)時(shí)對軌跡上的采樣位置進(jìn)行匿名，數(shù)據(jù)采集機(jī)構(gòu)也無法獲得原始數(shù)據(jù)，降低了隱私泄露的風(fēng)險(xiǎn)；

2)本文提出了一種k-θ-D匿名模型以抵御語義位置同質(zhì)性攻擊。該匿名模型的隱私保護(hù)度至少為k，且k個(gè)被匿名的興趣位置的敏感性差異盡可能大，以抵御語義同質(zhì)性攻擊。

3)針對k-θ-D匿名模型，提出了一種基于廣度優(yōu)先遍歷的滿足興趣位置差異性的匿名算法。

4)在真實(shí)數(shù)據(jù)集上對PTDC方法的數(shù)據(jù)可用性、空間范圍查詢誤差率及運(yùn)行時(shí)間進(jìn)行了實(shí)驗(yàn)驗(yàn)證，實(shí)驗(yàn)結(jié)果表明PTDC算法的數(shù)據(jù)可用性和空間查詢誤差率均和自由空間中的YCWA(You Can Walk Alone)算法有可比性，且運(yùn)行效率遠(yuǎn)遠(yuǎn)優(yōu)于YCWA算法，能滿足實(shí)時(shí)在線處理的需求。

1 預(yù)備知識

下面介紹本文算法的預(yù)備知識。

1.1 系統(tǒng)結(jié)構(gòu)

本文使用圖2所示的系統(tǒng)架構(gòu)。該架構(gòu)包括客戶端、隱私保護(hù)服務(wù)器兩個(gè)組件?？蛻舳藢⒃嘉恢脭?shù)據(jù)發(fā)送給隱私保護(hù)服務(wù)器，在隱私保護(hù)服務(wù)器中完成數(shù)據(jù)預(yù)處理及隱私保護(hù)兩個(gè)處理。匿名后的數(shù)據(jù)直接形成可發(fā)布數(shù)據(jù)，可供其他應(yīng)用程序進(jìn)行挖掘或統(tǒng)計(jì)。即使數(shù)據(jù)采集部門也無法獲得原始軌跡數(shù)據(jù)，隱私暴露風(fēng)險(xiǎn)降低。

圖2 感知隱私的軌跡數(shù)據(jù)收集系統(tǒng)結(jié)構(gòu)

1.2 相關(guān)定義

定義1 軌跡。軌跡T是采樣位置按時(shí)間排序構(gòu)成的序列T={(x1,y1,t1),(x2,y2,t2),…,(xn,yn,tn)}，每個(gè)采樣位置表示為一個(gè)三元組(xi,yi,ti)，其中，(xi,yi)表示采樣位置的坐標(biāo)，ti表示該位置的采樣時(shí)間。

定義2 興趣位置(Point Of Interest, POI)。興趣位置是地理信息系統(tǒng)中的術(shù)語，指一切可以抽象為點(diǎn)的語義地理對象，尤其是一些與人們生活密切相關(guān)的地理實(shí)體，如學(xué)校、銀行、餐館、加油站、醫(yī)院、超市等。

定義3 路網(wǎng)空間。路網(wǎng)空間用無向加權(quán)圖G=(V，E，W)表示。其中：V表示頂點(diǎn)的集合，興趣位置和道路連接點(diǎn)被視作頂點(diǎn);E是邊的集合，若頂點(diǎn)vi和vj之間有一條不經(jīng)過任何其他頂點(diǎn)就可以連接起來的路徑，則稱vi和vj之間有邊(vi,vj);W表示圖G的權(quán)值的集合。

1.3 路網(wǎng)空間中的攻擊模式

本節(jié)提出了三種路網(wǎng)中的攻擊模式。

第一種 敏感興趣位置攻擊。路網(wǎng)環(huán)境中的地圖信息是公開的，攻擊者可以獲取任意經(jīng)緯度對應(yīng)的興趣位置。當(dāng)移動對象運(yùn)行至敏感位置附近時(shí)，會暴露其位置隱私。即使其在靠近某個(gè)敏感興趣位置時(shí)關(guān)閉位置服務(wù)，攻擊者依然可以根據(jù)移動對象的運(yùn)行軌跡推導(dǎo)出其所訪問的敏感位置。

第二種 語義位置攻擊。為了防止上述敏感興趣位置攻擊，可將幾個(gè)興趣位置匿名在同一個(gè)匿名區(qū)域中。若有些位置是路網(wǎng)上不可達(dá)的，則可能造成隱私保護(hù)不足的情況。極端情況下，匿名區(qū)域中僅有一個(gè)可達(dá)的語義位置，移動對象的位置就泄露了。圖3所示為一個(gè)位置3-匿名區(qū)域，攻擊者很容易推斷出移動對象不可能在湖泊或無人自然保護(hù)區(qū)中，移動對象在醫(yī)院的敏感信息也遭到泄露。

第三種 語義位置同質(zhì)性攻擊。若匿名區(qū)域中的興趣位置敏感性相近，則仍可能導(dǎo)致隱私的泄露。例如，將幾個(gè)敏感度都很高的醫(yī)院、賓館、酒吧匿名在一起，同樣會造成用戶的隱私泄露。

上述三種攻擊類型中，語義位置同質(zhì)性攻擊是最強(qiáng)的攻擊模式。如果隱私保護(hù)算法能夠抵御語義位置同質(zhì)性攻擊，則可抵御上述三種攻擊模式。

圖3 興趣位置3-匿名區(qū)域

2 PTDC算法

與之前的軌跡隱私保護(hù)算法不同，PTDC算法不對軌跡數(shù)據(jù)匿名，而是對路網(wǎng)環(huán)境中的興趣位置進(jìn)行匿名。PTDC算法的處理過程如圖4所示。

圖4 PTDC算法架構(gòu)

其中，POI敏感性計(jì)算模塊負(fù)責(zé)計(jì)算地圖上各個(gè)POI的敏感性，根據(jù)得到的POI敏感性及用戶的隱私需求，由POI匿名區(qū)域生成模塊生成地圖上的匿名區(qū)域。這兩個(gè)模塊的處理可離線完成。此外，PTDC算法在對用戶位置數(shù)據(jù)匿名之前，先對用戶的當(dāng)前位置進(jìn)行評估，如果可能暴露其隱私，則需對該位置進(jìn)行實(shí)時(shí)匿名。

2.1 POI敏感性計(jì)算

要將POI匿名為一個(gè)區(qū)域，首先需計(jì)算每個(gè)POI的敏感性，即，該位置能暴露用戶多少隱私。例如，如果將地圖上鄰近的3個(gè)不同的醫(yī)院匿名在一起，攻擊者還是知曉該用戶患了某種疾病。據(jù)觀察，一個(gè)POI的敏感性通常與它的“流行度”有關(guān)，即，訪問該P(yáng)OI的用戶是少數(shù)還是普遍。例如，一條道路的敏感性較低，這是由于任何人都可以行進(jìn)在這條道路上。本文采用熵的方式定義POI的敏感性。

從定義中可以看出：敏感性越高的POI，其暴露用戶隱私的可能性越大，其熵越小，也就是重復(fù)訪問的人次越少；敏感性越低的POI，其熵越大，也就是重復(fù)訪問的人次越多。

2.2 POI匿名區(qū)域生成

算法將路網(wǎng)模擬到無向圖G=(V,E,W)上，給定用戶的隱私需求k，隱私保護(hù)技術(shù)需對地圖上的POI進(jìn)行匿名，每個(gè)匿名區(qū)域中至少包含k個(gè)POI。然而，傳統(tǒng)的軌跡k-匿名技術(shù)無法抵御語義位置同質(zhì)性攻擊。本文定義了一種k-θ-D匿名模型可抵御此類攻擊，具體定義如下。

定義5 k-θ-D匿名。給定路網(wǎng)G=(V,E,W)和隱私保護(hù)度k，k-θ-D匿名是指對路網(wǎng)中POI的匿名需滿足以下條件：1)每個(gè)匿名區(qū)域中至少包含k個(gè)POI；2)k個(gè)POI的敏感性差異盡可能大；3)k個(gè)POI之間的距離盡可能近。

上述條件1)和2)是為了保證隱私保護(hù)的程度，條件3)是為了保證生成的匿名區(qū)域面積盡可能小，使得采集到的數(shù)據(jù)有較高的數(shù)據(jù)可用性。為了保證匿名模型能滿足條件2)和條件3)的要求，本文定義了θ-邊權(quán)以同時(shí)衡量頂點(diǎn)的敏感性差異及距離兩個(gè)參數(shù)，具體定義如下：

匿名算法的目的是：將距離較近且敏感性差異性較大的k個(gè)頂點(diǎn)構(gòu)成匿名區(qū)域。根據(jù)θ-邊權(quán)的定義，將與θ-邊權(quán)較大的邊相關(guān)聯(lián)的頂點(diǎn)放入匿名區(qū)域中。首先，將圖G中與每個(gè)頂點(diǎn)相關(guān)聯(lián)的邊，按其θ-邊權(quán)值由大到小進(jìn)行排序。從頂點(diǎn)vi出發(fā)，按廣度優(yōu)先搜索算法進(jìn)行匿名。依次訪問與其鄰接的頂點(diǎn)vi1，vi2,…，按θ-邊權(quán)大小將頂點(diǎn)依次納入匿名區(qū)域，直到找到k-1個(gè)頂點(diǎn)為止。如果一次廣度優(yōu)先搜索找到的vi是一個(gè)路口(通常其敏感性值接近于0)，則不計(jì)數(shù)，可作為另外一個(gè)出發(fā)點(diǎn)作廣度優(yōu)先搜索尋找頂點(diǎn)，直到找到k-1個(gè)頂點(diǎn)為止。

如果將與vi相鄰接的所有節(jié)點(diǎn)都遍歷完也不足k個(gè)頂點(diǎn)，則按遍歷vi鄰接點(diǎn)的順序依次遍歷vi1，vi2，…的鄰接點(diǎn)，直到找到k-1個(gè)頂點(diǎn)為止。將構(gòu)成匿名區(qū)域的頂點(diǎn)和邊從圖G中刪除。如圖5所示，假設(shè)用戶給定k=3，從頂點(diǎn)v1出發(fā)，按照θ-邊權(quán)值的大小，先將頂點(diǎn)v2放入匿名集，再將頂點(diǎn)v4放入匿名集。此時(shí)，匿名集中包含了k個(gè)頂點(diǎn)，匿名區(qū)域即由(v1,v2,v4)構(gòu)成，將頂點(diǎn)v1,v2,v4及和它們相關(guān)聯(lián)的邊從圖G中刪除。繼續(xù)從圖G中任意頂點(diǎn)出發(fā)進(jìn)行上述操作，直到圖中不存在k個(gè)以上頂點(diǎn)為止。

圖5 加權(quán)路網(wǎng)

匿名算法如算法1所示，加權(quán)路網(wǎng)圖采用鄰接表存儲結(jié)構(gòu)，與每個(gè)頂點(diǎn)相關(guān)聯(lián)的邊按照θ-邊權(quán)值由大到小排列。

算法1 AnonyGraph(G(V,E),k)。

輸入：路網(wǎng)圖G(V,E)，隱私保護(hù)度k；

輸出：匿名區(qū)域A1,A2, … ,An。

1)

選取圖G中一個(gè)頂點(diǎn)vi加入匿名集；

2)

While(圖G中剩余頂點(diǎn)個(gè)數(shù)>k-1) do

3)

for(j=1;j<=k-1;j++)

4)

廣度優(yōu)先遍歷頂點(diǎn)vj1;

5)

if (vj1是交叉路口)

6)

廣度優(yōu)先遍歷vj1的下一個(gè)鄰接點(diǎn);

7)

then將訪問的頂點(diǎn)加入當(dāng)前匿名集中;

8)

將訪問頂點(diǎn)與和其相關(guān)聯(lián)的邊刪除;

9)

end for

10)

廣度優(yōu)先遍歷與vi相鄰接的點(diǎn)vi1，vi2,…;

11)

end while

12)

return匿名區(qū)域

之所以采用廣度優(yōu)先遍歷是因?yàn)樯疃葍?yōu)先遍歷生成的匿名區(qū)域面積較大，影響了數(shù)據(jù)可用性，本文在實(shí)驗(yàn)中進(jìn)行了驗(yàn)證。

2.3 位置實(shí)時(shí)匿名

當(dāng)用戶在一般道路行進(jìn)的時(shí)候，不會有隱私暴露的風(fēng)險(xiǎn)，此時(shí)，其位置信息可不作處理，直接提供給位置收集服務(wù)器即可。而在訪問某個(gè)POI或者較為敏感的POI時(shí)才有可能泄露隱私。算法的用戶位置評估模塊在接收到一個(gè)位置信息后，將評估該位置是否需要進(jìn)行匿名處理。對收到的位置數(shù)據(jù)進(jìn)行地址反向編譯處理，得到其語義地址：

1) 若該地址為路網(wǎng)上某個(gè)POI，將其送進(jìn)位置實(shí)時(shí)匿名模塊進(jìn)行匿名處理；

2) 若該位置是一般道路，則需根據(jù)其與位置匿名區(qū)域的距離作相應(yīng)處理。

用戶的位置需經(jīng)過匿名處理之后才能發(fā)送給數(shù)據(jù)采集服務(wù)器。由于地圖匿名可以離線完成，因此在移動對象行進(jìn)過程中完成實(shí)時(shí)匿名是可行的。具體匿名算法如算法2所示。

算法2 k-θ-D Anonymity(A1,A2,…,An;Li)。

輸入：匿名區(qū)域A1,A2,…,An，待匿名位置Li；

輸出：匿名后的位置Li′。

1)

for (i=1;i<=G中頂點(diǎn)個(gè)數(shù);i++)

2)

將Li進(jìn)行反向地址解析;

3)

if(Li是POI)

4)

根據(jù)Li的經(jīng)緯度判斷其屬于匿名區(qū)域Ai;

5)

用Ai替換Li發(fā)送給數(shù)據(jù)收集方;

6)

else

7)

直接將Li發(fā)送給數(shù)據(jù)收集方;

8)

end for

3 隱私保護(hù)度分析與數(shù)據(jù)可用性評估

本節(jié)對PTDC算法的隱私保護(hù)度和數(shù)據(jù)可用性進(jìn)行分析。其隱私保護(hù)度可由定理1說明。

定理1 移動對象在運(yùn)行過程中產(chǎn)生實(shí)時(shí)軌跡T={(x1,y1,t1),(x2,y2,t2),…,(xn,yn,tn)}，PTDC算法將用戶的敏感位置用相應(yīng)的匿名區(qū)域取代。該匿名區(qū)域中包含至少k個(gè)POI，用戶在某個(gè)敏感位置被識別的概率為1/k。

證明 假設(shè)攻擊者可以獲取路網(wǎng)背景知識以及隱私處理之后收集到的軌跡信息。給定可發(fā)布的軌跡數(shù)據(jù)庫D*，移動對象的任意敏感位置均被泛化為一個(gè)區(qū)域Ai，其中至少包含k個(gè)路網(wǎng)上的POI，攻擊者識別用戶訪問位置的概率與匿名區(qū)域中包含的POI數(shù)量有關(guān)，因此，每個(gè)敏感位置被識別的概率至多為1/k。

收集到的軌跡數(shù)據(jù)可用于密集區(qū)域發(fā)現(xiàn)等應(yīng)用。將單個(gè)位置泛化為一個(gè)匿名區(qū)域，不可避免地會丟失信息。本文采用原始位置的識別率定義信息丟失率IL，也就是從一個(gè)匿名區(qū)域中識別出某個(gè)移動對象位置的概率，如下述公式所示：

其中:n表示移動對象的個(gè)數(shù)，m表示每個(gè)移動對象的采樣位置數(shù)，即軌跡中所包含的采樣點(diǎn)的數(shù)目。如果移動對象Oi在tj時(shí)刻的采樣位置泛化為匿名區(qū)域，該采樣位置的識別度從1下降到1/area(Oi,tj)，其中，area(Oi,tj)表示匿名區(qū)域的面積。信息丟失是衡量隱私保護(hù)算法的重要指標(biāo)之一。信息丟失越多，隱私保護(hù)算法處理之后的數(shù)據(jù)可用性就越低。

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

實(shí)驗(yàn)采用北京市路網(wǎng)數(shù)據(jù)[11]，該數(shù)據(jù)集有北京市約17萬個(gè)路網(wǎng)頂點(diǎn)及43萬余條邊。軌跡數(shù)據(jù)采用真實(shí)數(shù)據(jù)集Geolife。該數(shù)據(jù)集采集了155個(gè)志愿者在北京市的8 000多條軌跡，該數(shù)據(jù)集中大約包含230萬條采樣位置信息，采樣位置主要分布在北京市五環(huán)區(qū)域內(nèi)。實(shí)驗(yàn)機(jī)器處理器為Intel i5處理器，4 GB內(nèi)存，Windows 7操作系統(tǒng)。

本文對算法的信息丟失率、范圍查詢相對誤差及算法運(yùn)行時(shí)間進(jìn)行了測試。本文的方法與在自由空間中的隱私保護(hù)方法YCWA[8]進(jìn)行了對比實(shí)驗(yàn)。YCWA算法是在自由空間中基于語義位置保護(hù)的軌跡隱私保護(hù)算法，與本文提出的PDTC算法具有可比性。

4.1 數(shù)據(jù)可用性衡量

本節(jié)主要展示YCWA算法(具體包括DiverseClus和GridPartiton兩個(gè)算法，本文只選取性能較好的DieverseClus進(jìn)行比對實(shí)驗(yàn))和PDTC算法(基于深度優(yōu)先遍歷的算法簡寫為DFS(Depth-First Search)，基于廣度優(yōu)先遍歷的算法簡寫為BFS(Bread-First Search))在數(shù)據(jù)可用性上的對比實(shí)驗(yàn)，隱私參數(shù)k取值為4,6,8,10,12。實(shí)驗(yàn)結(jié)果如圖6所示。

圖6 數(shù)據(jù)可用性衡量

信息丟失主要是由空間泛化造成的，即，將一個(gè)采樣位置泛化為匿名區(qū)域，匿名區(qū)域面積的大小也是衡量算法的性能指標(biāo)之一。圖6(a)展示了兩個(gè)算法匿名區(qū)域的平均面積大小。可以看出，由于BFS和DFS算法是在路網(wǎng)上進(jìn)行POI匿名，其匿名區(qū)域平均面積大于YCWA算法。盡管如此，BFS算法的信息丟失率并非很高，圖6(b)展示了信息丟失率與隱私參數(shù)之間的關(guān)系，從實(shí)驗(yàn)結(jié)果可看出，算法的信息丟失率隨著隱私參數(shù)的增加而增加。在路網(wǎng)環(huán)境中的隱私保護(hù)算法BFS的信息丟失率雖然比自由空間中的算法YCWA略高，但是其信息丟失率仍然在20%以下，尤其當(dāng)隱私參數(shù)為4時(shí)，其信息丟失率僅在11%左右。這是由于BFS算法的信息丟失完全是由空間泛化造成的，而YCWA算法中有些不能被泛化的采樣位置需要被抑制，這也造成了信息丟失。而DFS算法在兩個(gè)參數(shù)上表現(xiàn)較差，因此PTDC算法以廣度優(yōu)先遍歷算法為基礎(chǔ)。

4.2 空間范圍查詢誤差

圖7展示了空間范圍查詢誤差率的對比結(jié)果。從實(shí)驗(yàn)結(jié)果可以看出雖然在兩種查詢上YCWA算法比PTDC算法的查詢誤差率低，但是PTDC算法的誤差率一直控制在20%以內(nèi)。兩個(gè)算法在DAI查詢上的誤差率均高于在PSI查詢上的誤差，這是由于DAI查詢的選擇性更強(qiáng)。

圖7 空間范圍查詢誤差率

4.1節(jié)和4.2節(jié)的實(shí)驗(yàn)是針對自由空間中軌跡隱私保護(hù)算法和路網(wǎng)環(huán)境中軌跡隱私保護(hù)算法進(jìn)行的比對實(shí)驗(yàn)。顯然，路網(wǎng)環(huán)境中的軌跡隱私保護(hù)算法的隱私保護(hù)度更高，因此，雖然PTDC算法的表現(xiàn)略差于YCWA算法，但PDTC算法更符合實(shí)際需求，隱私保護(hù)度也更高。

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

圖8展示了算法運(yùn)行時(shí)間的對比。從圖中可以看出，YCWA算法的時(shí)間復(fù)雜度遠(yuǎn)遠(yuǎn)高于PTDC算法。由于YCWA算法是基于聚類的，隨著簇中對象個(gè)數(shù)的增加，YCWA算法的時(shí)間逐漸減少。PTDC是基于圖遍歷的算法，隨著匿名區(qū)域中POI數(shù)量的增加，回退的可能性更大，算法的運(yùn)行時(shí)間更長。從PTDC算法的運(yùn)行時(shí)間來看，其完全可以滿足在線實(shí)時(shí)收集位置數(shù)據(jù)的需求。

圖8 兩種算法運(yùn)行時(shí)間對比

5 結(jié)語

本文提出了一種路網(wǎng)環(huán)境中感知隱私的軌跡數(shù)據(jù)采集技術(shù)。首先計(jì)算路網(wǎng)上POI的敏感性，然后在路網(wǎng)上對POI進(jìn)行k-θ-D匿名生產(chǎn)匿名區(qū)域，最后，區(qū)分用戶實(shí)時(shí)位置的敏感性，將敏感位置用匿名區(qū)域取代。通過實(shí)驗(yàn)驗(yàn)證了本文提出算法信息丟失率較低，且針對范圍查詢的誤差率較低。在今后的工作中，需在下述兩個(gè)方面對算法進(jìn)行改進(jìn)：1)結(jié)合文獻(xiàn)[13]中提到的軌跡數(shù)據(jù)處理的滑動窗口技術(shù)，探索k-θ-D匿名算法的更優(yōu)化算法，提高算法的運(yùn)行效率；2)改進(jìn)POI敏感度的計(jì)算方法，使其能夠更真實(shí)地反映現(xiàn)實(shí)世界中POI的敏感性。

References)

[1] ZHENG Y. Trajectory data mining: an overview [J]. ACM Transactions on Intelligent Systems and Technology, 2015, 6(3): Article No. 29.

[2] 霍崢,孟小峰.軌跡隱私保護(hù)技術(shù)研究[J].計(jì)算機(jī)學(xué)報(bào)，2011,34(10):1820-1830.(HUO Z, MENG X F. A survey of trajectory privacy-preserving techniques [J]. Chinese Journal of Computers, 2011, 34(10): 1820-1830.)

[3] DAI J, HUA L. A method for the trajectory privacy protection based on the segmented fake trajectory under road networks [C]// Proceedings of the 2015 2nd International Conference on Information Science and Control Engineering. Washington, DC: IEEE Computer Society, 2015: 13-17.

[4] CHEN R, LI H, QIN A K, et al. Private spatial data aggregation in the local setting [C]// Proceedings of the 2016 IEEE 32nd International Conference on Data Engineering. Washington, DC: IEEE Computer Society, 2016: 289-300.

[5] 趙婧,張淵,李興華,等.基于軌跡頻率抑制的軌跡隱私保護(hù)方法[J].計(jì)算機(jī)學(xué)報(bào),2014,37(10):2096-2106.(ZHAO J, ZHANG Y, LI X H, et al. A trajectory privacy protection approach via trajectory frequency suppression [J]. Chinese Journal of Computers, 2014, 37(10): 2096-2106.)

[6] CAI Z F, YANG H X, SHUANG W, et al. A clustering-based privacy-preserving method for uncertain trajectory data [C]// Proceedings of the 2014 IEEE 13th International Conference on Trust, Security and Privacy in Computing and Communications. Washington, DC: IEEE Computer Society, 2014: 1-8.

[7] HAN P I, TSAI H P. SST: privacy preserving for semantic trajectories [C]// Proceedings of the 2015 16th IEEE International Conference on Mobile Data Management. Washington, DC: IEEE Computer Society, 2015: 80-85.

[8] HUO Z, MENG X, HU H, et al. You can walk alone: trajectory privacy-preserving through significant stays protection [C]// International Conference on Database Systems for Advanced Applications, LNCS 7238. Berlin: Springer, 2012: 351-366.

[9] HUO Z, MENG X, ZHANG R. Feel free to check in: privacy alert against hidden location inference attacks in GeoSNs [C]// International Conference on Database Systems for Advanced Applications, LNCS 7825. Berlin: Springer, 2013: 377-391.

[10] 霍崢,孟小峰,黃毅.PrivateCheckIn:一種移動社交網(wǎng)絡(luò)中的軌跡隱私保護(hù)方法[J].計(jì)算機(jī)學(xué)報(bào),2013,36(4):716-726.(HUO Z, MENG X F, HUANG Y. PrivateCheckIn: trajectory privacy-preserving for check-in services in MSNS [J]. Chinese Journal of Computers. 2013, 36(4): 716-726.)[11] 數(shù)據(jù)堂.數(shù)據(jù)產(chǎn)品[DB/OL]. [2017- 01- 06]. http://www.datatang.com/product/product.html.

[12] TRAJCEVSKI G, WOLFSON O, HINRICHS K, et al. Managing uncertainty in moving objects databases [J]. ACM Transactions on Database Systems, 2004, 29(3): 463-507.

[13] AI-HUSSAENI K, FUNG B C M, CHEUNG W K. Privacy-preserving trajectory stream publishing [J]. Data and Knowledge Engineering, 2014, 94(Part A): 89-109.

[14] GUO M, JIN X, PISSINOU N, et al. In-network trajectory privacy preservation [J]. ACM Computing Surveys, 2015, 48(2): Article No. 23.

PTDC:privacy-awaretrajectorydatacollectiontechnologyunderroadnetworkconstraint

HUO Zheng*, WANG Weihong, CAO Yuhui

(SchoolofInformationTechnology,HebeiUniversityofEconomicsandBusiness,ShijiazhuangHebei050061,China)

Since the problem of trajectory privacy violation and homogeneous semantic location attack of moving objects in road network environment is very serious, a Privacy-aware Trajectory Data Collection (PTDC) algorithm was proposed. Firstly, through visits’ entropy of Points Of Interests (POI), the sensitivity of each POI was computed; secondly, based on the mixture distance of sensitivity and Euclidean distance, θ-weight was defined and a weighted model of vertices and edges in the network environment was established to reach a k-θ-D anonymity, which can resist the semantic location homogeneity attack; finally, based on the bread-first traversal algorithm of undirected graph, an anonymous algorithm was proposed to satisfy the semantic difference of POIs, so that user’s sensitive sampling location was replaced by an anonymous region. Data utility caused by PTDC algorithm was theoretically evaluated. A set of experiments were implemented to test PTDC algorithm, and compare it with the privacy-preserving algorithm named YCWA (You Can Walk Alone) in free space. In theory, the privacy level of YCWA algorithm was lower than PTDC algorithm. The experimental results show that the PTDC algorithm has an average information loss of about 15%, and average range count query error rate of about 12%, which performs slightly worse than YCWA algorithm, while the running time of PTDC algorithm is less than 5 seconds, which is much better than YCWA algorithm. PTDC algorithm meets the needs of real-time online data collection.

road network; privacy-preserving; trajectory data; data collection; semantic location

2017- 03- 29;

2017- 05- 03。

國家自然科學(xué)基金資助項(xiàng)目(61502279)；河北省自然科學(xué)基金資助項(xiàng)目(F2015207009)；河北省高等學(xué)校青年拔尖人才計(jì)劃項(xiàng)目(BJ2016019)；出國留學(xué)擇優(yōu)資助項(xiàng)目(C2015003042)。

霍崢(1982—)，女，河北邯鄲人，講師，博士，CCF會員，主要研究方向：移動對象數(shù)據(jù)庫、隱私保護(hù)； 王衛(wèi)紅(1970—)，女，河北涿州人，教授，博士，CCF會員，主要研究方向：移動協(xié)同計(jì)算、移動云計(jì)算； 曹玉輝(1969—)，男，河北正定人，教授，博士，CCF會員，主要研究方向：資源聚合、移動云計(jì)算。

1001- 9081(2017)09- 2567- 05

10.11772/j.issn.1001- 9081.2017.09.2567

TP311.13

A

This research was partially supported by the National Natural Science Foundation of China (61502279), the Natural Science Foundation of Hebei Province (F2015207009), Young Talents Program in Colleges and Universities of Hebei Province (BJ2016019), the Advanced Program for Study Abroad (C2015003042).

HUOZheng, born in 1982, Ph.D., lecturer. Her research interests include mobile data management, privacy-preserving techniques.

WANGWeihong, born in 1970, Ph. D., professor. Her research interests include mobile collaboration computing, mobile cloud computing.

CAOYuhui, born in 1969, Ph.D., professor. His research interests include resource aggregation, mobile cloud computing.