劉向宇，許世惠琳，夏秀峰，宗傳玉，朱 睿，李佳佳

(沈陽(yáng)航空航天大學(xué) 計(jì)算機(jī)學(xué)院，沈陽(yáng) 110136)

近年來，定位技術(shù)和移動(dòng)感知技術(shù)的快速發(fā)展產(chǎn)生了大量的移動(dòng)軌跡數(shù)據(jù)。例如，車輛行駛GPS數(shù)據(jù)或?qū)Ш杰浖?shù)據(jù)形成了用戶的軌跡數(shù)據(jù)。通過對(duì)軌跡數(shù)據(jù)進(jìn)行發(fā)布共享、分析和挖掘，可以得到大量有價(jià)值的信息和知識(shí)，用于交通路線設(shè)計(jì)或城市規(guī)劃等。軌跡共享和分析在給城市建設(shè)和用戶日常生活帶來便利的同時(shí)，也給用戶的個(gè)人隱私帶來了巨大的安全隱患。如果對(duì)軌跡數(shù)據(jù)不加限制的直接發(fā)布，一旦這些數(shù)據(jù)被惡意攻擊者獲取，則攻擊者可通過數(shù)據(jù)挖掘等技術(shù)獲取到軌跡信息中蘊(yùn)含的家庭住址、生活習(xí)慣或健康狀況等用戶個(gè)人隱私信息，給用戶的隱私安全帶來嚴(yán)重威脅[1-3]。因此，針對(duì)發(fā)布軌跡的隱私保護(hù)十分必要，其主要目的在于保護(hù)發(fā)布軌跡中用戶個(gè)人隱私安全，同時(shí)保證發(fā)布軌跡集仍具有較高的數(shù)據(jù)可用性。

圖1a所示為用戶u軌跡T的信息，其中(li,ti)表示用戶于ti時(shí)刻在位置li處進(jìn)行位置簽到。圖1b顯示了軌跡T在路網(wǎng)中的位置。軌跡T為用戶u從家出發(fā)前往醫(yī)院的軌跡，對(duì)于用戶u而言，該軌跡屬于其個(gè)人隱私。然而，如果數(shù)據(jù)擁有者在不對(duì)其進(jìn)行任何處理的情況下直接發(fā)布，則導(dǎo)致攻擊者可輕易獲得該敏感軌跡，造成用戶的軌跡隱私泄露。

圖1 軌跡T的軌跡信息及其假軌跡在路網(wǎng)中的分布情況

針對(duì)上述問題，本文提出一種面向路網(wǎng)時(shí)空約束的軌跡隱私保護(hù)算法，根據(jù)軌跡在路網(wǎng)中的時(shí)空特性生成滿足路網(wǎng)時(shí)空約束、符合用戶軌跡模式的假軌跡，從而更好地保護(hù)軌跡隱私。

1 相關(guān)工作

現(xiàn)有的軌跡隱私保護(hù)技術(shù)主要分為基于泛化的軌跡隱私保護(hù)、基于抑制的軌跡隱私保護(hù)和基于假軌跡的軌跡隱私保護(hù)3種。泛化法是指將軌跡上的位置點(diǎn)擴(kuò)展為1個(gè)匿名區(qū)域使攻擊者識(shí)別出用戶的概率降低；抑制法通過對(duì)軌跡數(shù)據(jù)進(jìn)行有選擇的發(fā)布實(shí)現(xiàn)對(duì)用戶敏感軌跡的保護(hù)；假軌跡法一般以向真實(shí)軌跡中添加虛假軌跡來達(dá)到混淆攻擊者的目的。

軌跡k-匿名作為基于泛化的軌跡隱私保護(hù)的常用方法之一，其主要思想是通過可信的第三方匿名服務(wù)器選擇k-1條與用戶軌跡相似的其他用戶軌跡來對(duì)用戶軌跡進(jìn)行混淆，保護(hù)用戶軌跡隱私安全。Zhu等[4]提出一種基于偏好感知的軌跡匿名算法(PTPP)，該算法先根據(jù)用戶軌跡移動(dòng)模式、用戶熟悉度和位置受歡迎程度對(duì)用戶偏好進(jìn)行建模，再自適應(yīng)選擇合適的位置與用戶原始軌跡上的位置點(diǎn)構(gòu)建匿名域。Ye等[5]提出一種基于路網(wǎng)的l-多樣性算法。算法先通過可信第三方匿名服務(wù)器對(duì)路網(wǎng)進(jìn)行區(qū)域劃分，并構(gòu)建每個(gè)子區(qū)域內(nèi)的通用軌跡數(shù)據(jù)庫(kù)，再?gòu)能壽E數(shù)據(jù)庫(kù)中選擇l-1條距用戶軌跡最近的其他軌跡構(gòu)建匿名域。Hwang等[6]提出一種綜合r-匿名、k-匿名、s-道路分段的時(shí)間混淆算法對(duì)用戶軌跡隱私進(jìn)行保護(hù)。算法首先構(gòu)建用戶歷史軌跡數(shù)據(jù)集，再由可信第三方匿名服務(wù)器從中選擇與用戶當(dāng)前軌跡相似的軌跡構(gòu)建軌跡匿名域，在對(duì)軌跡數(shù)據(jù)進(jìn)行發(fā)布時(shí)，打亂發(fā)布位置的時(shí)間順序來對(duì)攻擊者進(jìn)行混淆。Chiba等[7]發(fā)現(xiàn)現(xiàn)有的軌跡匿名方法中有些匿名域內(nèi)位置發(fā)生了變化，導(dǎo)致發(fā)布后軌跡集信息損失增大，故提出一種在一定范圍內(nèi)允許位置和時(shí)間不匹配的算法以減少位置距離修改，提高發(fā)布后軌跡的數(shù)據(jù)可用性。

軌跡抑制通過刪除用戶軌跡中敏感或頻繁出現(xiàn)的位置信息實(shí)現(xiàn)對(duì)軌跡數(shù)據(jù)有選擇的發(fā)布，防止攻擊者通過此類信息對(duì)用戶軌跡隱私安全造成威脅。Yao等[8]提出基于擾亂的數(shù)據(jù)隱私保護(hù)算法，通過刪除軌跡上關(guān)鍵位置序列中的某些移動(dòng)位置點(diǎn)使軌跡數(shù)據(jù)滿足隱私保護(hù)要求。Chen等[9]提出基于局部抑制的軌跡隱私保護(hù)方案，有選擇地刪除用戶局部軌跡中的位置點(diǎn)，在保護(hù)用戶軌跡隱私安全的同時(shí)提高發(fā)布軌跡的數(shù)據(jù)可用性。趙婧等[10]提出一種基于軌跡頻率抑制的軌跡隱私保護(hù)方法來對(duì)用戶軌跡進(jìn)行處理，在保護(hù)用戶軌跡隱私安全的同時(shí)提高數(shù)據(jù)可用性和算法性能。

假軌跡方法指不借助第三方服務(wù)器生成與用戶原始軌跡相似的假軌跡，并將原始軌跡與假軌跡一起發(fā)布來對(duì)攻擊者進(jìn)行混淆。假軌跡隱私保護(hù)技術(shù)具有實(shí)現(xiàn)簡(jiǎn)單、能保留較完整軌跡信息、不需可信第三方服務(wù)器等特點(diǎn)，因此在實(shí)際研究中應(yīng)用廣泛。假軌跡方法最早由Kido等[11]提出基本思想。LEI等[12]在此基礎(chǔ)上提出通過隨機(jī)法和旋轉(zhuǎn)法生成假軌跡，隨機(jī)法指隨機(jī)生成一些位置點(diǎn)，并將它們按時(shí)間順序連接得到與用戶原始軌跡相似的假軌跡。旋轉(zhuǎn)法則是以用戶原始軌跡為基礎(chǔ)，選擇軌跡上某些采樣位置點(diǎn)為軸點(diǎn)對(duì)原始軌跡進(jìn)行旋轉(zhuǎn)，旋轉(zhuǎn)后得到的軌跡即為生成的假軌跡。林鄧偉等[13]提出一種基于用戶真實(shí)軌跡的虛假軌跡生成方法，主要通過建立用戶軌跡的馬爾科夫模型，并融入攻擊者的背景信息，來抵御攻擊者通過背景知識(shí)攻擊來竊取用戶軌跡隱私。Dai等[14]提出一種在路網(wǎng)環(huán)境下分段生成假軌跡的軌跡隱私保護(hù)算法。該算法通過第三方可信匿名服務(wù)器生成假位置，再將生成的假位置與上一時(shí)刻真位置連接得到假軌跡段，最后將假軌跡段按時(shí)間順序連接得到假軌跡，算法有效提高了用戶軌跡的隱私保護(hù)程度。LEI等[15]提出一種基于時(shí)空關(guān)聯(lián)性的假軌跡隱私保護(hù)方案。該方案從軌跡整體方向、軌跡間相似性和軌跡上相鄰位置間時(shí)空關(guān)聯(lián)性進(jìn)行分析，使生成的假軌跡可有效與真實(shí)軌跡進(jìn)行混淆，防止攻擊者識(shí)別出假軌跡，有效保護(hù)發(fā)布軌跡隱私安全。

但現(xiàn)有的針對(duì)發(fā)布軌跡的隱私保護(hù)方法在生成假軌跡時(shí)沒有充分考慮軌跡在路網(wǎng)中存在的時(shí)空約束條件，所以生成的假軌跡很容易因不滿足現(xiàn)實(shí)路網(wǎng)約束條件被攻擊者識(shí)別出來，從而導(dǎo)致用戶原始軌跡信息泄露。故本文提出面向路網(wǎng)時(shí)空約束的軌跡隱私保護(hù)算法解決上述問題。

2 預(yù)備知識(shí)和問題定義

在本文中，將用戶的時(shí)空數(shù)據(jù)表示為(l，t)，這里t指時(shí)間，l=(x，y)為用戶的位置點(diǎn)坐標(biāo)，x和y分別表示經(jīng)度、緯度。軌跡是用戶通過不斷移動(dòng)產(chǎn)生的時(shí)空數(shù)據(jù)序列，記作T={(l1,t1),(l2,t2),…,(ln，tn)}，軌跡上采樣位置點(diǎn)數(shù)量為該條軌跡的軌跡長(zhǎng)度。將包含多條用戶軌跡的軌跡集稱為原始軌跡集，原始軌跡集TS={T1,T2,…,Tm}，Ti為原始軌跡集中第i條待發(fā)布的用戶軌跡，記為Ti={(li1,t1),(li2,t2),…,(lin，tn)}。原始軌跡集經(jīng)本文算法處理后，得到包含待發(fā)布用戶軌跡和對(duì)應(yīng)假軌跡的發(fā)布軌跡集PTS。發(fā)布軌跡集PTS={T1,T12,…,T1j,…,T2,T21,…,T2j,…,Tm，Tm1,…,Tmj,…}。其中，Tij={(li1(j),t1),(li2(j),t2),…,(lin(j),tn)}表示軌跡Ti的第j條假軌跡，(lia(j),ti)表示Tij的第a個(gè)簽到數(shù)據(jù)。

定義1 敏感軌跡和敏感軌跡攻擊。將用戶不希望別人知道的軌跡稱為敏感軌跡。攻擊者以較大概率識(shí)別出用戶的敏感軌跡，導(dǎo)致用戶軌跡隱私泄露，稱為敏感軌跡攻擊。

定義2 軌跡k-匿名。給定一條用戶敏感軌跡Ti，當(dāng)發(fā)布軌跡集中存在k-1條假軌跡與Ti的簽到數(shù)據(jù)時(shí)間序列一致時(shí)，則Ti與其他軌跡在該時(shí)間段內(nèi)相互之間不可區(qū)分，稱Ti滿足軌跡k-匿名。

定義3 軌跡泄露率。給定原始軌跡集TS，用|TS|表示TS中軌跡數(shù)量，|TS′|表示被攻擊者識(shí)別出的軌跡數(shù)量，則軌跡泄露率如式(1)所示

(1)

定義4 位置距離。給定某時(shí)刻用戶敏感軌跡上位置點(diǎn)li=(xi，yi)，假軌跡上對(duì)應(yīng)時(shí)刻位置點(diǎn)li′=(xi′,yi′)，將位置距離定義為兩點(diǎn)間的歐氏距離，則位置距離如式(2)所示

(2)

定義5 軌跡距離。給定用戶敏感軌跡Ti={(li1,t1),(li2,t2),…,(lin，tn)}和假軌跡Tij={(li1(j),t1),(li2(j),t2),…,(lin(j),tn)}，則兩軌跡間的軌跡距離如式(3)所示

(3)

定義6 相似軌跡。給定敏感軌跡Ti，假軌跡Tij，距離范圍閾值α、β，若滿足α≤dis(Ti，Tij)≤β，則認(rèn)為軌跡Ti和Tij是相似軌跡。

定義8 信息損失。給定原始軌跡集TS和發(fā)布軌跡集PTS。其中m為TS中軌跡數(shù)量，軌跡Ti∈TS,特征軌跡Ti′∈PTS。則基于TS發(fā)布軌跡集PTS導(dǎo)致的信息損失如式(4)所示

(4)

問題定義：給定原始軌跡集TS、軌跡匿名閾值k、距離范圍閾值α、β，通過生成滿足路網(wǎng)時(shí)空約束條件的假軌跡，構(gòu)建符合軌跡k-匿名的發(fā)布軌跡集PTS，在保護(hù)軌跡隱私安全性的同時(shí)保證發(fā)布軌跡集的數(shù)據(jù)可用性最大化。

3 路網(wǎng)軌跡隱私保護(hù)

本節(jié)提出一種面向路網(wǎng)時(shí)空約束的軌跡隱私保護(hù)算法(A trajectory privacy protection algorithm satisfying the spatio-temporal constraints in road networks,TPPST)，如算法1所示。算法1的主要思想是：首先，通過候選假位置生成算法，根據(jù)路網(wǎng)道路分布情況為原始軌跡集中每條敏感軌跡上采樣位置點(diǎn)生成滿足路網(wǎng)時(shí)空約束條件的候選假位置集；其次，根據(jù)候選假軌跡生成算法，將候選假位置集中位置按時(shí)間順序連接得到滿足路網(wǎng)時(shí)空約束條件的候選假軌跡集，并從中篩選得出k-1條滿足距離范圍約束且與敏感軌跡間軌跡距離最接近的假軌跡；最后，將敏感軌跡與假軌跡合并為一個(gè)發(fā)布軌跡匿名集進(jìn)行發(fā)布。在該匿名集內(nèi)，每條軌跡上的采樣位置點(diǎn)都可與其他軌跡上相同時(shí)刻的位置點(diǎn)構(gòu)成位置匿名集，防止攻擊者識(shí)別出敏感軌跡中的任意位置點(diǎn)，從而推測(cè)出用戶的完整敏感軌跡。由于本算法既要保證生成假軌跡的合理性與真實(shí)性，又要保證發(fā)布軌跡的隱私安全，所以生成的每條假軌跡都應(yīng)在滿足路網(wǎng)軌跡時(shí)空約束條件的同時(shí)符合用戶的軌跡模式以實(shí)現(xiàn)對(duì)攻擊者的混淆。

TPPST每次從原始軌跡集TS中獲取一條用戶敏感軌跡Ti進(jìn)行處理。處理時(shí)先通過算法CDL生成Ti上所有采樣位置點(diǎn)的假位置，再將所有采樣位置和假位置一起存入位置候選集Candli中。通過算法CDT得到所有由Candli中位置點(diǎn)組成的滿足路網(wǎng)時(shí)空約束條件和距離范圍要求的假軌跡，并將假軌跡按軌跡距離值升序排列存入假軌跡候選集CandTi中(第3～4行)。最后，將敏感軌跡Ti和CandTi中前k-1條假軌跡存入發(fā)布軌跡集PTS中。當(dāng)TS中所有用戶敏感軌跡都得到滿足要求的k-1條假軌跡后，返回包含所有用戶敏感軌跡和假軌跡的發(fā)布軌跡集PTS(第5～7行)。

算法1.面向路網(wǎng)時(shí)空約束的軌跡隱私保護(hù)算法(TPPST)

輸入：軌跡集TS，軌跡匿名閾值k，距離范圍閾值α、β；

輸出：發(fā)布軌跡集PTS。

1.PTS ← ?;

2.Foreach trajectoryTiinTSdo

3. Candli= CDL(Ti,k,α,β);//包含軌跡上所有采樣位置和假位置信息的候選位置集;

4. CandTi=CDT(Candli,k,α,β);//按軌跡距離值升序排列的候選假軌跡集;

5. PTS←Ti;

6. Select the topk-1 dummy trajectories from CandTito PTS;

7.ReturnPTS;

3.1 軌跡相似性度量

本算法通過假軌跡與對(duì)應(yīng)用戶敏感軌跡間的軌跡距離來對(duì)軌跡相似性進(jìn)行度量。軌跡距離值越小，生成假軌跡與用戶敏感軌跡在軌跡形狀上越相似，越難被攻擊者區(qū)分；軌跡距離值越大，生成假軌跡與原始軌跡間的區(qū)別越大，越容易被攻擊者區(qū)分。但當(dāng)軌跡距離值過小或過大時(shí)，生成假軌跡會(huì)因與原始軌跡過于相似或差別過大而被攻擊者識(shí)別出來，很難起到有效的軌跡隱私保護(hù)效果。所以給定距離范圍閾值α,β，只有軌跡距離值在給定范圍內(nèi)的假軌跡才是用戶軌跡的相似軌跡，才能既在滿足軌跡相似性的同時(shí)滿足軌跡隱私保護(hù)要求。軌跡距離計(jì)算如式(3)所示。當(dāng)且僅當(dāng)滿足式(5)時(shí)，假軌跡才可起到隱私保護(hù)效果，用于對(duì)攻擊者進(jìn)行混淆。

α≤dis(Ti,Tij)≤β

(5)

3.2 候選位置集生成

在算法TPPST中，通過候選假位置生成算法(Candidate dummy location generation,CDL)生成軌跡上采樣位置對(duì)應(yīng)的假位置集，并返回由采樣位置和假位置構(gòu)建的候選位置集。為滿足軌跡隱私保護(hù)要求，生成的假位置點(diǎn)需滿足路網(wǎng)時(shí)空約束條件和距離范圍要求。同時(shí)每個(gè)采樣位置都可與至少1個(gè)假位置點(diǎn)構(gòu)建位置匿名域，實(shí)現(xiàn)對(duì)用戶敏感軌跡上的任一位置點(diǎn)的位置隱私保護(hù)。因此將假位置生成分為以下3個(gè)步驟：確定假位置生成范圍，計(jì)算假位置生成數(shù)量，假位置生成。

CDL算法先遍歷軌跡Ti上所有采樣位置li，確定li的假位置生成范圍Zi并記錄Zi內(nèi)道路密度，刪除道路密度為零的采樣位置點(diǎn)，因?yàn)榇藭r(shí)無(wú)法生成滿足要求的假位置點(diǎn)，故抑制該采樣位置不進(jìn)行發(fā)布(第2～4行)；然后對(duì)所得道路密度數(shù)據(jù)進(jìn)行均一化處理，并通過計(jì)算每個(gè)li處應(yīng)生成的最少假位置數(shù)量Ni(第5行)；接著再次遍歷軌跡Ti上的采樣位置li，先將li的位置信息存入Candli中，在位置li對(duì)應(yīng)的假位置生成范圍Zi內(nèi)隨機(jī)生成Ni個(gè)滿足路網(wǎng)時(shí)空約束的假位置，并將這些假位置的位置信息也存入Candli中，最后返回候選位置集Candli(第6～9行)。

算法2.候選假位置生成算法(CDL)

輸入：原始軌跡Ti，軌跡匿名閾值k，距離范圍閾值α、β；

輸出：候選位置集Candli。

1.Candli← ?;

2.Foreach sampling locationliinTido

3.Zi=dummy location generation range forli;

4.Z←Zi;

5.N←Ni;//Ni=the number of dummy location forlicalculated by Equation 7;

6.Foreach sampling locationliinTido

7. Insert the sampling location’s information into Candli;

8. GenerateNidummy locations inZiand insert these locations’ information into Candli;

9.ReturnCandli;

將路網(wǎng)道路地圖抽象為一個(gè)無(wú)向圖G(V,E)，路口為無(wú)向圖節(jié)點(diǎn)V，道路為無(wú)向圖邊E。當(dāng)生成的假位置落在路網(wǎng)無(wú)向圖上時(shí)，該假位置也可視為落在路網(wǎng)道路中，滿足路網(wǎng)空間可達(dá)性約束。由于用戶在路網(wǎng)中只能沿路網(wǎng)道路行駛，故用兩點(diǎn)在路網(wǎng)無(wú)向圖中的最短路徑長(zhǎng)度代替歐氏距離表示用戶實(shí)際行駛路程，并用于路網(wǎng)時(shí)間可達(dá)性判斷。由于兩點(diǎn)間最短路徑長(zhǎng)度與歐氏距離相比更接近于用戶實(shí)際行駛路程，故由此得出的路網(wǎng)時(shí)間可達(dá)性判斷更符合實(shí)際。同時(shí)，考慮到軌跡上位置點(diǎn)間具有連通性，因此不能單獨(dú)考慮某位置點(diǎn)與其前一時(shí)刻或后一時(shí)刻位置間的路網(wǎng)時(shí)間可達(dá)性，而應(yīng)綜合考慮其前后時(shí)刻所在位置點(diǎn)共同進(jìn)行判斷。只有當(dāng)位置點(diǎn)同時(shí)滿足與其前后相鄰時(shí)刻位置間的路網(wǎng)時(shí)間可達(dá)性約束時(shí)，該位置點(diǎn)才是滿足要求可用于后續(xù)生成假軌跡的假位置點(diǎn)。路網(wǎng)時(shí)間可達(dá)性由式(6)進(jìn)行判斷，其中S為位置點(diǎn)li-1至li間的最短路徑距離，ti，ti-1表示到達(dá)兩位置的時(shí)間戳，vmax為用戶在路網(wǎng)中的最大速度限制。若用戶在時(shí)間間隔Δt=ti-ti-1內(nèi)以給定路網(wǎng)最大速度限制vmax移動(dòng)的距離大于等于位置li-1至li間的最短路徑距離，則說明用戶可在ti時(shí)刻前到達(dá)位置點(diǎn)li處。同理可推導(dǎo)出第二個(gè)基于距離S的不等式，當(dāng)用戶在時(shí)間間隔Δt=ti+1-ti內(nèi)以最大速度行駛的距離大于位置li至li+1間的最短路徑距離時(shí)，用戶可在ti+1時(shí)刻到達(dá)位置li+1處。為使后續(xù)生成假軌跡滿足距離范圍要求，這里在路網(wǎng)無(wú)向圖的基礎(chǔ)上，將假位置生成范圍進(jìn)一步限制在以采樣位置為圓心，范圍距離閾值α，β為半徑的同心圓的圓環(huán)區(qū)域內(nèi)。

(6)

綜上所述，如圖2所示，本算法將采樣位置li的假位置生成范圍Zi定義為滿足式(6)且在以li為圓心,α、β為半徑的同心圓圓環(huán)區(qū)域內(nèi)的路網(wǎng)無(wú)向圖上。將所有采樣位置li對(duì)應(yīng)的假位置生成范圍Zi存放在位置范圍集Z中。

圖2 假位置生成示意圖

因?yàn)槊總€(gè)采樣位置所處地理環(huán)境內(nèi)道路密度不同，若生成相同數(shù)量的假位置則可能發(fā)生某區(qū)域無(wú)法得到足夠數(shù)量的假位置，而其他區(qū)域生成假位置過于密集等情況，因此本文通過Zi內(nèi)道路密度區(qū)分不同li對(duì)應(yīng)的假位置生成數(shù)量。首先將所有區(qū)域內(nèi)道路密度記為RD={rd1,rd2,…,rdn}，然后以其中最小的道路密度為基準(zhǔn)對(duì)道路密度進(jìn)行均一化處理，處理后得到的結(jié)果為RD′={rd1′,rd2′,…,rdn′}，其中rdi′=rdi/rdmin。通過式(7)計(jì)算每個(gè)采樣位置對(duì)應(yīng)的假位置生成數(shù)量，并對(duì)計(jì)算結(jié)果向上取整，可得出不同li處生成的最少假位置數(shù)量Ni，將所有采樣位置li對(duì)應(yīng)的假位置生成數(shù)量Ni存放在位置數(shù)量集N中。最后在每個(gè)li對(duì)應(yīng)的Zi內(nèi)隨機(jī)生成Ni數(shù)量個(gè)假位置即可。

(7)

例如，給定一條包含5個(gè)采樣位置的軌跡和軌跡匿名閾值k=5，軌跡上每個(gè)采樣位置對(duì)應(yīng)的道路密度為RD={3,2,2,4,3}，以其中最小道路密度2為基準(zhǔn)進(jìn)行均一化處理后得到RD′={1.5,1,1,2,1.5}，通過式(7)計(jì)算可知1.5x·x·x·2x·1.5x=4.5x5≥4，將計(jì)算結(jié)果向上取整后可知x=1，則對(duì)應(yīng)假位置生成數(shù)量集合為Ni={2,1,1,2,2}。

3.3 候選假軌跡生成

本節(jié)提出候選假軌跡生成算法(Candidate dummy trajectory generation, CDT)生成敏感軌跡Ti對(duì)應(yīng)的候選假軌跡集CandTi。CDT先將算法CDL生成的候選位置集Candli中的位置通過枚舉法得出所有可能滿足路網(wǎng)時(shí)空可達(dá)性約束的假軌跡，同時(shí)計(jì)算假軌跡與原始軌跡間的軌跡距離，并將所有軌跡信息存入候選假軌跡集CandTi中。候選假軌跡連接方式如圖3所示(第2行)。然后根據(jù)給定的距離閾值α，β對(duì)CandTi中所有候選假軌跡進(jìn)行篩選判斷，若存在軌跡間距離值不滿足軌跡相似性度量公式α≤dis(Ti，Tij)≤β的情況，則從CandTi中刪除該條候選假軌跡(第3～5行)。最后將CandTi中假軌跡按軌跡距離值升序排列后返回(第6-7行)。

圖3 候選假軌跡連接示意圖

算法3.候選假軌跡生成算法(CDT)

輸入：候選位置集Candli，軌跡匿名閾值k，距離范圍閾值α、β；

輸出：候選假軌跡集CandTi。

1.CandTi← ?;

2.Through enumeration method and Candligenerate dummy trajectories and then insertTijto CandTi;

3.Foreach trajectoryTijin CandTido

4.Ifdis(Ti，Tij)not satisfiedα≤dis(Ti，Tij)≤βthen

5. deleteTijfrom CandTi;

6.Sort(asc)CandTiby dis(Ti，Tij);

7.ReturnCandTi;

本文通過枚舉法列舉得出所有可能的候選假軌跡。假設(shè)一條軌跡上有n個(gè)采樣位置點(diǎn)，若為每個(gè)位置點(diǎn)都生成s個(gè)假位置則最多可得到(s+1)n-1條假軌跡，假軌跡數(shù)量隨采樣位置數(shù)呈指數(shù)形式增長(zhǎng)。但這樣得到的假軌跡集中會(huì)存在某些假軌跡上存在過多與采樣位置點(diǎn)相同的位置，增加原始軌跡泄露的風(fēng)險(xiǎn)。故需進(jìn)一步對(duì)得到的假軌跡進(jìn)行篩選，只保留含有一個(gè)采樣位置的假軌跡，刪除其余假軌跡，這樣得到的假軌跡集可在有效對(duì)攻擊者進(jìn)行混淆的同時(shí)，降低軌跡泄露概率。

3.4 算法安全性及復(fù)雜度分析

在本節(jié)中，會(huì)對(duì)算法的安全性和時(shí)間復(fù)雜度進(jìn)行理論分析與證明。

定理1 采用面向路網(wǎng)時(shí)空約束的軌跡隱私保護(hù)算法(算法1)對(duì)原始軌跡集中的每條用戶軌跡進(jìn)行處理后，得到的發(fā)布軌跡集滿足軌跡k-匿名要求。

證明 算法2為原始軌跡集中每條用戶敏感軌跡上所有采樣位置點(diǎn)生成假位置，且通過計(jì)算保證這些假位置連接得到的滿足路網(wǎng)時(shí)空可達(dá)性約束和距離范圍要求的假軌跡至少為k-1條。算法3在生成假軌跡時(shí)不僅使用算法2生成的假位置點(diǎn)還包含原始軌跡上部分采樣位置點(diǎn)，所以最后得到的滿足要求的假軌跡一定多于k-1條。算法1通過調(diào)用算法2和算法3得到所有滿足路網(wǎng)時(shí)空約束和距離范圍要求的假軌跡中軌跡距離值最小的k-1條，使軌跡集中每條原始軌跡均能滿足軌跡k-匿名。綜上，通過算法1生成的發(fā)布軌跡集滿足軌跡k-匿名要求。

算法復(fù)雜度分析：用m、n分別表示原始軌跡集中用戶敏感軌跡數(shù)量和敏感軌跡上采樣位置點(diǎn)數(shù)量。在算法CDL中，生成軌跡上所有采樣位置點(diǎn)對(duì)應(yīng)的滿足路網(wǎng)時(shí)空可達(dá)性約束條件的假位置需n+n·k1/n時(shí)，則算法的時(shí)間復(fù)雜度為O(n·k1/n)。在算法CDT中，通過枚舉法得到所有候選假軌跡并計(jì)算軌跡距離耗時(shí)n!+(k1/n+1)n，算法復(fù)雜度為O(n!)。算法TPPST通過調(diào)用算法CDL和算法CDT得到軌跡集中每條用戶原始軌跡的候選假軌跡集，并從中選擇k-1假軌跡耗時(shí)為m·(n·k1/n+n!)，所以算法TPPST的時(shí)間復(fù)雜度為O(m·n!)。

4 實(shí)驗(yàn)結(jié)果分析

本節(jié)對(duì)提出的面向路網(wǎng)時(shí)空約束的軌跡隱私保護(hù)算法進(jìn)行性能分析和評(píng)估。實(shí)驗(yàn)使用北京市路網(wǎng)地圖數(shù)據(jù)和1個(gè)真實(shí)的北京出租車軌跡集T-Drive。其中，北京市路網(wǎng)數(shù)據(jù)包括17萬(wàn)個(gè)路網(wǎng)頂點(diǎn)及43萬(wàn)余條邊。T-Drive原始軌跡集包含北京大部分區(qū)域的10 357輛出租車一星期內(nèi)的軌跡，總計(jì)72 499條軌跡，涵蓋約1 500萬(wàn)位置點(diǎn)，軌跡中相鄰位置點(diǎn)間的時(shí)間差為5 min。本文對(duì)T-Drive原始軌跡集進(jìn)行處理，選取其中600條軌跡上的部分軌跡數(shù)據(jù)構(gòu)建實(shí)驗(yàn)軌跡數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)數(shù)據(jù)集統(tǒng)計(jì)信息如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)集統(tǒng)計(jì)信息

本文先通過實(shí)驗(yàn)得出面向路網(wǎng)時(shí)空約束的軌跡隱私保護(hù)算法(TPPST)中的最優(yōu)距離范圍閾值。然后通過與基于隨機(jī)法生成假軌跡的隱私保護(hù)方法(簡(jiǎn)稱RM)和基于時(shí)空關(guān)聯(lián)性生成假軌跡的隱私保護(hù)方法(簡(jiǎn)稱STM)比較，分析本算法在運(yùn)行時(shí)間、信息損失和軌跡泄露率方面的性能。在測(cè)試中,軌跡匿名閾值k的取值范圍為[3,18](默認(rèn)為9)，軌跡數(shù)量n的取值范圍為[100,600](默認(rèn)為300)，軌跡長(zhǎng)度l的取值范圍為[5,10](默認(rèn)為7)。

本實(shí)驗(yàn)的軟硬件環(huán)境如下：(1)硬件環(huán)境：Intel Core i5 2.71GHz 8GB DRAM;(2)操作系統(tǒng)：Microsoft Windows 10;(3)編程環(huán)境：Java,Eclipse。

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

本節(jié)通過測(cè)試TPPST算法在不同距離范圍下的軌跡相似度和信息損失來獲取最優(yōu)距離范圍閾值α、β。由于當(dāng)距離范圍過小或過大時(shí),所得實(shí)驗(yàn)結(jié)果均趨于平緩，故選擇波動(dòng)較大區(qū)間作為實(shí)驗(yàn)測(cè)試范圍。

由圖4可知：(1)隨著距離范圍的增大，軌跡相似度逐漸增加，信息損失逐漸減少。這是由于隨著距離范圍的增大，假位置的生成范圍也隨之?dāng)U大，一些原始軌跡上原本因假位置生成范圍內(nèi)道路密度為零而被抑制發(fā)布的采樣位置點(diǎn)，在擴(kuò)大范圍后也生成假位置并參與發(fā)布。由信息損失計(jì)算公式可知，信息損失為原始軌跡集中所有用戶敏感軌跡與發(fā)布軌跡集中對(duì)應(yīng)特征軌跡間軌跡距離和的平均值。隨著距離范圍的擴(kuò)大，特征軌跡上的位置點(diǎn)也隨之變化，部分位置點(diǎn)坐標(biāo)與原始軌跡上對(duì)應(yīng)采樣位置點(diǎn)坐標(biāo)更加接近，因此信息損失逐漸降低。而軌跡相似度主要通過原始軌跡與對(duì)應(yīng)假軌跡間軌跡距離進(jìn)行計(jì)算，隨著更多假位置的生成，計(jì)算時(shí)會(huì)增加該點(diǎn)與對(duì)應(yīng)假位置間的距離差，故軌跡相似度逐漸增加。綜上所述，距離范圍與軌跡相似度成正比,與信息損失成反比。(2)實(shí)驗(yàn)通過對(duì)比在不同軌跡匿名閾值k、軌跡長(zhǎng)度和軌跡數(shù)量的情況下，得出距離范圍變化對(duì)軌跡相似度和信息損失產(chǎn)生的影響。由圖4可知，當(dāng)距離范圍從6 km增大到7 km時(shí)，信息損失明顯下降，且在距離范圍大于7 km時(shí)信息損失的變化趨于平緩。在軌跡相似度隨距離范圍的增加而逐漸增加的過程中，在距離范圍為10 km時(shí)，增加趨勢(shì)明顯減緩。所以本文將距離范圍設(shè)置為[7,10]，在該范圍內(nèi)算法生成的假軌跡可在有效保護(hù)用戶原始軌跡隱私安全的情況下，保持較好的數(shù)據(jù)可用性。

圖4 軌跡相似度和信息損失隨距離范圍變化

4.2 運(yùn)行時(shí)間

由圖5可知,3個(gè)算法的運(yùn)行時(shí)間均隨著軌跡匿名閾值k、軌跡數(shù)量和軌跡長(zhǎng)度的增加而增長(zhǎng)。STM算法和RM算法的運(yùn)行時(shí)間接近，TPPST算法快于STM算法和RM算法約1.5 s。這是由于TPPST算法通過CDL和CDT算法限定了假位置和假軌跡的生成條件，因此TPPST算法可以更快地生成滿足要求的假軌跡。且由圖5可知，運(yùn)行時(shí)間與軌跡匿名閾值k、軌跡數(shù)量和軌跡長(zhǎng)度值成正比，即要生成的假軌跡和待用戶保護(hù)軌跡上采樣位置數(shù)量越多則運(yùn)行時(shí)間越長(zhǎng)，且隨著生成假軌跡數(shù)量的增加算法耗時(shí)翻倍增加。

圖5 運(yùn)行時(shí)間隨k、軌跡數(shù)量和軌跡長(zhǎng)度變化

4.3 信息損失

由圖6可知,RM算法和STM算法的信息損失始終高于TPPST算法，最高可達(dá)TPPST算法的2倍。這是由于STM算法的假位置生成范圍為將路網(wǎng)地圖網(wǎng)格化后，兩采樣位置間歐氏距離加一個(gè)隨機(jī)數(shù)長(zhǎng)度的網(wǎng)格范圍。RM算法的假位置生成范圍為將路網(wǎng)地圖網(wǎng)格化后距采樣位置2β內(nèi)的網(wǎng)格范圍。由此可以看出RM算法和STM算法生成的假位置點(diǎn)要比TPPST算法生成的假位置點(diǎn)與采樣位置間的位置距離大，因此計(jì)算所得信息損失也更大。由圖6可知，信息損失與軌跡匿名閾值成反比，與軌跡數(shù)量值成正比。由信息損失計(jì)算公式可知，隨著生成假軌跡數(shù)量的增加，敏感軌跡T與發(fā)布軌跡中對(duì)應(yīng)特征軌跡T′間的軌跡距離值會(huì)逐漸減小。在軌跡數(shù)量不變的情況下，信息損失隨著軌跡匿名閾值k的增加而減小。而在軌跡匿名閾值k不變的情況下，隨著原始軌跡數(shù)量的增加，計(jì)算得到的軌跡距離累加和也在不斷增加,且增長(zhǎng)趨勢(shì)大于軌跡數(shù)量的增長(zhǎng)，故信息損失會(huì)隨著軌跡數(shù)量的增加而增加。

圖6 信息損失隨k和軌跡數(shù)量變化

4.4 軌跡泄露率

由圖7可知,當(dāng)發(fā)布軌跡為路網(wǎng)軌跡時(shí)，TPPST算法根據(jù)路網(wǎng)中軌跡的時(shí)空約束條件生成假軌跡，故無(wú)法被攻擊者通過敏感軌跡攻擊識(shí)別出來。RM算法和STM算法的軌跡泄露率接近于100%,遠(yuǎn)高于TPPST算法。這是由于RM算法只是以用戶真實(shí)位置點(diǎn)為基準(zhǔn)隨機(jī)生成假位置點(diǎn)，而STM算法雖然是基于軌跡時(shí)空特性生成假軌跡，但二者均未考慮路網(wǎng)軌跡具有的時(shí)空約束條件，故使用上述兩種算法生成的假軌跡有95%以上的概率會(huì)被攻擊者通過敏感軌跡攻擊識(shí)別出來，導(dǎo)致用戶敏感軌跡隱私泄露。

圖7 軌跡泄露概率隨k和軌跡數(shù)量變化

5 結(jié)語(yǔ)

本文提出一種面向路網(wǎng)時(shí)空約束的軌跡隱私保護(hù)算法(TPPST)，用以解決現(xiàn)有的假軌跡生成軌跡隱私保護(hù)技術(shù)因生成的假軌跡真實(shí)性較差而造成用戶軌跡隱私泄露的問題。該算法在路網(wǎng)無(wú)向圖的基礎(chǔ)上根據(jù)路網(wǎng)軌跡時(shí)空約束條件生成假軌跡，使生成的假軌跡在有效保護(hù)用戶隱私安全的同時(shí),降低發(fā)布后軌跡集的信息損失。實(shí)驗(yàn)基于真實(shí)軌跡數(shù)據(jù)進(jìn)行，所得結(jié)果表明TPPST算法可有效抵御攻擊者的敏感軌跡攻擊，在保護(hù)用戶發(fā)布軌跡隱私安全的情況下保證發(fā)布軌跡具有較好的數(shù)據(jù)可用性。