PTDC:路網環境中感知隱私的軌跡數據采集技術

霍 崢，王衛紅，曹玉輝

(河北經貿大學 信息技術學院，石家莊 050061)(*通信作者電子郵箱huozheng123@gmail.com)

PTDC:路網環境中感知隱私的軌跡數據采集技術

霍 崢*，王衛紅，曹玉輝

(河北經貿大學 信息技術學院，石家莊 050061)(*通信作者電子郵箱huozheng123@gmail.com)

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

路網；隱私保護；軌跡數據；數據采集；語義位置

0 引言

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

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

圖1 路網中的軌跡3-匿名

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

具體來說，本文的主要貢獻如下：

1)本文提出一種感知隱私的軌跡數據采集方法PTDC，可在移動對象運行過程中，實時對軌跡上的采樣位置進行匿名，數據采集機構也無法獲得原始數據，降低了隱私泄露的風險；

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

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

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

1 預備知識

下面介紹本文算法的預備知識。

1.1 系統結構

本文使用圖2所示的系統架構。該架構包括客戶端、隱私保護服務器兩個組件。客戶端將原始位置數據發送給隱私保護服務器，在隱私保護服務器中完成數據預處理及隱私保護兩個處理。匿名后的數據直接形成可發布數據，可供其他應用程序進行挖掘或統計。即使數據采集部門也無法獲得原始軌跡數據，隱私暴露風險降低。

圖2 感知隱私的軌跡數據收集系統結構

1.2 相關定義

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

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

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

1.3 路網空間中的攻擊模式

本節提出了三種路網中的攻擊模式。

第一種 敏感興趣位置攻擊。路網環境中的地圖信息是公開的，攻擊者可以獲取任意經緯度對應的興趣位置。當移動對象運行至敏感位置附近時，會暴露其位置隱私。即使其在靠近某個敏感興趣位置時關閉位置服務，攻擊者依然可以根據移動對象的運行軌跡推導出其所訪問的敏感位置。

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

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

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

圖3 興趣位置3-匿名區域

2 PTDC算法

與之前的軌跡隱私保護算法不同，PTDC算法不對軌跡數據匿名，而是對路網環境中的興趣位置進行匿名。PTDC算法的處理過程如圖4所示。

圖4 PTDC算法架構

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

2.1 POI敏感性計算

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

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

2.2 POI匿名區域生成

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

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

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

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

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

圖5 加權路網

匿名算法如算法1所示，加權路網圖采用鄰接表存儲結構，與每個頂點相關聯的邊按照θ-邊權值由大到小排列。

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

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

輸出：匿名區域A1,A2, … ,An。

1)

選取圖G中一個頂點vi加入匿名集；

2)

While(圖G中剩余頂點個數>k-1) do

3)

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

4)

廣度優先遍歷頂點vj1;

5)

if (vj1是交叉路口)

6)

廣度優先遍歷vj1的下一個鄰接點;

7)

then將訪問的頂點加入當前匿名集中;

8)

將訪問頂點與和其相關聯的邊刪除;

9)

end for

10)

廣度優先遍歷與vi相鄰接的點vi1，vi2,…;

11)

end while

12)

return匿名區域

之所以采用廣度優先遍歷是因為深度優先遍歷生成的匿名區域面積較大，影響了數據可用性，本文在實驗中進行了驗證。

2.3 位置實時匿名

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

1) 若該地址為路網上某個POI，將其送進位置實時匿名模塊進行匿名處理；

2) 若該位置是一般道路，則需根據其與位置匿名區域的距離作相應處理。

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

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

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

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

1)

for (i=1;i<=G中頂點個數;i++)

2)

將Li進行反向地址解析;

3)

if(Li是POI)

4)

根據Li的經緯度判斷其屬于匿名區域Ai;

5)

用Ai替換Li發送給數據收集方;

6)

else

7)

直接將Li發送給數據收集方;

8)

end for

3 隱私保護度分析與數據可用性評估

本節對PTDC算法的隱私保護度和數據可用性進行分析。其隱私保護度可由定理1說明。

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

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

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

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

4 實驗分析

實驗采用北京市路網數據[11]，該數據集有北京市約17萬個路網頂點及43萬余條邊。軌跡數據采用真實數據集Geolife。該數據集采集了155個志愿者在北京市的8 000多條軌跡，該數據集中大約包含230萬條采樣位置信息，采樣位置主要分布在北京市五環區域內。實驗機器處理器為Intel i5處理器，4 GB內存，Windows 7操作系統。

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

4.1 數據可用性衡量

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

圖6 數據可用性衡量

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

4.2 空間范圍查詢誤差

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

圖7 空間范圍查詢誤差率

4.1節和4.2節的實驗是針對自由空間中軌跡隱私保護算法和路網環境中軌跡隱私保護算法進行的比對實驗。顯然，路網環境中的軌跡隱私保護算法的隱私保護度更高，因此，雖然PTDC算法的表現略差于YCWA算法，但PDTC算法更符合實際需求，隱私保護度也更高。

4.3 算法運行時間

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

圖8 兩種算法運行時間對比

5 結語

本文提出了一種路網環境中感知隱私的軌跡數據采集技術。首先計算路網上POI的敏感性，然后在路網上對POI進行k-θ-D匿名生產匿名區域，最后，區分用戶實時位置的敏感性，將敏感位置用匿名區域取代。通過實驗驗證了本文提出算法信息丟失率較低，且針對范圍查詢的誤差率較低。在今后的工作中，需在下述兩個方面對算法進行改進：1)結合文獻[13]中提到的軌跡數據處理的滑動窗口技術，探索k-θ-D匿名算法的更優化算法，提高算法的運行效率；2)改進POI敏感度的計算方法，使其能夠更真實地反映現實世界中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] 霍崢,孟小峰.軌跡隱私保護技術研究[J].計算機學報，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] 趙婧,張淵,李興華,等.基于軌跡頻率抑制的軌跡隱私保護方法[J].計算機學報,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:一種移動社交網絡中的軌跡隱私保護方法[J].計算機學報,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] 數據堂.數據產品[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。

國家自然科學基金資助項目(61502279)；河北省自然科學基金資助項目(F2015207009)；河北省高等學校青年拔尖人才計劃項目(BJ2016019)；出國留學擇優資助項目(C2015003042)。

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

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.