基于路徑混淆的實時軌跡隱私保護方法

李鳳云，郭 昊，畢遠國，李亦寧

1.東北大學 計算機科學與工程學院，沈陽 110169

2.網(wǎng)絡(luò)文化與數(shù)字傳播北京市重點實驗室，北京 110101

3.曼尼托巴大學 科學學院，加拿大 曼尼托巴 溫尼伯 MB R3T 2N2

近年來，隨著一些新興科技領(lǐng)域（如工業(yè)智能化、人工科技化、機器學習化以及高清晰率的圖像識別技術(shù)等）的迅速發(fā)展，使得車聯(lián)網(wǎng)技術(shù)得到突飛猛進的發(fā)展[1]。車聯(lián)網(wǎng)以降低事故發(fā)生率，提升交通效率為設(shè)計初衷，目前已成為智能交通系統(tǒng)的重要組成部分，推動自動駕駛、數(shù)據(jù)共享發(fā)展的關(guān)鍵環(huán)節(jié)，具有重要的研究意義和應(yīng)用價值。

在車聯(lián)網(wǎng)領(lǐng)域下，行駛的車輛會利用車輛間、車－路邊單元及相關(guān)設(shè)備進行信息傳輸，該信息中存在海量的敏感信息[2]。擁有目標車輛歷史軌跡信息的攻擊者可以在車輛進行軌跡服務(wù)請求時利用無線信道截取車輛間通信信息，這些攻擊者可以根據(jù)所截取的部分信息與目標車輛進行聯(lián)系，根據(jù)軌跡信息與目標車輛歷史軌跡的關(guān)聯(lián)度進行判斷是否為所要跟蹤車輛[3]。這些軌跡信息的泄露可能會對用戶的一些敏感信息造成極大侵害，例如目標用戶的家庭住址、健康情況、個人愛好和曾出現(xiàn)過的一些敏感位置等[4]。由此可見，信息安全是目前車聯(lián)網(wǎng)技術(shù)中亟需解決的安全問題。

隱私泄漏問題嚴重地提高了軌跡數(shù)據(jù)發(fā)布的風險，降低了服務(wù)提供商發(fā)布車輛軌跡數(shù)據(jù)的熱情。著眼于軌跡信息隱私保護領(lǐng)域下，在實際的城市交通路況中，由于交叉路口路況信息復(fù)雜，影響車輛軌跡規(guī)劃的條件眾多，信息體量大，處理難度高，如何在此場景下保護軌跡數(shù)據(jù)并提高預(yù)測精度，是本文的研究重點。

目前對于實時軌跡數(shù)據(jù)安全的研究仍處于初級階段，在該階段國內(nèi)外尚未有統(tǒng)一高效的隱私保護體系。因此車輛軌跡數(shù)據(jù)所涉及到的隱私保護問題是當前國內(nèi)外學者關(guān)注的重點。在此車聯(lián)網(wǎng)技術(shù)體系下，攻擊者獲取車輛軌跡數(shù)據(jù)的途徑[5]：一是通過截取用戶軌跡信息的傳輸通道；二是通過與第三方服務(wù)器進行同謀攻擊，可直接從數(shù)據(jù)庫獲取車輛的軌跡信息。

針對軌跡數(shù)據(jù)發(fā)布所產(chǎn)生的軌跡隱私泄露問題，為了對車輛原始軌跡進行實時的隱私保護，本文提出一種車輛混淆路徑軌跡保護方法。車輛軌跡達到自定義的軌跡保護閾值后，減少車輛混淆，解決了路徑混淆開銷大的問題。同時，設(shè)計一種基于車輛路徑混淆算法來增加車輛在路口路徑混淆的機會，提高車輛軌跡保護程度。

1 相關(guān)工作

路徑混淆一般用來解決車輛在軌跡信息傳輸過程中產(chǎn)生的數(shù)據(jù)泄露問題，其利用車輛自身的計算和空間存儲能力來提高車輛進行軌跡信息交換中的隱私保護效果?；煜哪康木褪菍δ繕塑囕v及其周邊車輛的軌跡信息進行交叉從而保護目標車輛。

利用混淆軌跡數(shù)據(jù)法進行隱私信息保護時，常見解決方法為K-匿名保護模型，該保護模型由Sweeny[6]首次提出并應(yīng)用于可信服務(wù)器數(shù)據(jù)庫內(nèi)，經(jīng)泛化處理后的標識型數(shù)據(jù)將與其他K-1個數(shù)據(jù)項產(chǎn)生混淆。K-匿名保護模型為經(jīng)典的NP-hard問題，該思想具有積極的理論意義和實施價值，并為后續(xù)的研究奠定了理論基礎(chǔ)。K-匿名保護模型首次被Gruteser[7]應(yīng)用于位置信息保護場景中，此后該模型均基于此基礎(chǔ)上進行發(fā)展。Yang等人[8]在后續(xù)研究中將非真實位置數(shù)據(jù)加入數(shù)據(jù)庫中，并用以向隱私保護對象的真實車輛附近構(gòu)造出大小為K的匿名集。

數(shù)據(jù)泛化處理的思想被Hegg等人[9]進行了延續(xù)性的應(yīng)用，在泛化思想的基礎(chǔ)上對時空進行區(qū)分，移動車輛的位置被延展至合適的區(qū)域。數(shù)據(jù)泛化作為軌跡K-匿名保護模型的核心技術(shù)，通過泛化處理車輛運行的軌跡信息，相關(guān)位置數(shù)據(jù)映射入匿名區(qū)域[10]。Wang等人[11]基于K-匿名的概念，對軌跡聚類算法加入了線性處理的方式，利用數(shù)學公式計算其距離。雖然經(jīng)過聚類后的軌跡數(shù)據(jù)更易于處理，但由于受到實際場景下道路復(fù)雜條件制約，對于軌跡隱私保護的效果仍未有良好的解決辦法。

此外，Mahdavifar等人[12]提出了重聚類算法對上述缺陷進行改進，通過組混淆后進行聚類再組內(nèi)擾亂。該處理方式可提升重聚類攻擊的抵御能力，但數(shù)據(jù)經(jīng)聚類混淆后，可用性也隨之降低。Huo等人[13]將匿名集合進行構(gòu)建時，提出用模型圖表示車輛軌跡上位置間的關(guān)系，并在匿名集合的構(gòu)建過程中應(yīng)用了圖論思想，但方法未考慮到軌跡方向?qū)τ诩蠘?gòu)建的影響。Gao等人[14]將方向變量納入研究范圍，在其圖論模型構(gòu)建時關(guān)聯(lián)與其方向一致的車輛數(shù)據(jù)，為軌跡之間方向與距離賦權(quán)并重新構(gòu)建軌跡模型。

針對不同策略中的第三方服務(wù)器，Bimeyer等人[15]利用一個檢測框架來識別檢測依賴于被覆蓋節(jié)點范圍的發(fā)布位置和由該計算結(jié)果產(chǎn)生的期望位置。Connell等人[16]則基于似然性模型提出通過車輛之間位置以及運動軌跡，目的是檢測車輛隱私泄露中存在的偽擁塞和拒絕擁擠兩種攻擊，此框架具有較高的車輛位置點的檢測率。Zhou等人[17]引入路邊輔助單元（road side unit，RSU）對實時車輛提供分布式處理服務(wù)減少通信過程中產(chǎn)生的物理損耗。

實時數(shù)據(jù)軌跡隱私保護的目的通常是對實時軌跡數(shù)據(jù)進行匿名化處理，現(xiàn)有軌跡數(shù)據(jù)的信息傳遞通常是通過車輛之間的短途通信或者借助路邊單元和第三方可信服務(wù)器[18]。但是目前所依賴的服務(wù)器沒有辦法保障百分之百的安全性，所以利用車輛之間的短途通信對車輛的軌跡進行區(qū)域范圍的保護，從而減少通過第三方泄露軌跡的風險。針對區(qū)域范圍內(nèi)的軌跡隱私保護可以減少攻擊者通過數(shù)據(jù)庫增加的背景知識。

本文針對現(xiàn)實情況對車輛進行路徑混淆?；谲壽E混淆技術(shù)，利用車輛在短時間內(nèi)出現(xiàn)軌跡重合的情況進行交叉，并將情況進行延續(xù)，通過更改目標車輛發(fā)送的軌跡時間或路徑信息從而使目標車輛的真實軌跡得以隱藏。由于這些參數(shù)的更改在短時間內(nèi)無法被攻擊者察覺，從而實現(xiàn)軌跡隱私保護。通過車輛的自適應(yīng)時間窗口對地理位置相鄰的車輛范圍再進行時間窗口劃分，以車輛通過該路口所用時長作為隱私保護劃分的范圍，增加目標車輛在此時間范圍的混淆機會。該方案在保護車輛軌跡隱私的同時降低了發(fā)布軌跡數(shù)據(jù)中的數(shù)據(jù)延遲并且更接近實時發(fā)布。

2 本文方法

針對用戶實時軌跡在交叉路口進行軌跡隱私保護開展研究，基于路徑混淆和時間窗口相結(jié)合的方法，提出了一種新型的自適應(yīng)時間窗口算法?；诨煜Ｐ偷能壽E熵閾值和自適應(yīng)時間窗口范圍來選擇目標車輛的最適混淆車輛組，有效地保護目標車輛在軌跡混淆過程中產(chǎn)生的軌跡信息，從而使得攻擊車輛無法準確跟蹤找到目標車輛的完整軌跡。

2.1 軌跡熵

軌跡熵是從信息熵引用而來。熵表示了一種不確定性，可以用概率函數(shù)來表示：

其中，x表示為事件，p(x)為x事件發(fā)生的概率；h(x)是關(guān)于x概率分布的一個函數(shù)。

由于軌跡熵依賴于目標車輛在運行過程中的真實軌跡和在混淆算法下的虛假軌跡情況，隨機變量x取決于車輛行駛過程經(jīng)過交叉路口的路段數(shù)量，其概率分布為：

所以在不考慮復(fù)雜情況條件下，x的概率分布結(jié)果服從均勻分布b，目標車輛在路口的軌跡熵S表示為：

其中，l表示兩個車輛之間的距離。

當車輛運行過程途經(jīng)M個交叉路口并進行路徑混淆時，目標車輛真實軌跡和周圍聯(lián)合產(chǎn)生的真假軌跡的總數(shù)N最少為：

車輛總軌跡熵S表示為：

針對目前由于聚集產(chǎn)生的車輛軌跡信息的體量大、容錯多、交通狀況復(fù)雜等問題，本文在自身可操作的情況下盡可能減少在LBS服務(wù)提供商或可信任第三方服務(wù)器上的軌跡信息傳輸，利用車輛自身的計算和空間存儲能力來提高車輛軌跡信息交換時的保護效果。其中，混淆組就是在車輛行駛過程中位于目標車輛附近的其他車輛構(gòu)成的滿足一定條件的車輛組群。

2.2 路徑混淆算法

在實際交通路況中，傳統(tǒng)的車輛路徑混淆方法是在將車輛軌跡信息上傳到通信設(shè)備或第三方服務(wù)器時引入時間延遲，用來保護車輛在混淆過程中產(chǎn)生的軌跡信息安全。但加入時間延遲對實時車輛來說會導(dǎo)致所需服務(wù)無法及時響應(yīng)。

基于以上問題本文提出了一種車輛自適應(yīng)時間窗口算法（vehicle adaptive time window algorithm，VATW），該方法能夠進行實時操作，并可以根據(jù)車輛之間短程通信檢索到時空信息，同時在連續(xù)和針對實時位置更新的情況下提供軌跡隱私保護。VATW就是利用車輛之間的DSRC（dedicated short range communications）通信進行模糊軌跡跟蹤。具體來講，通過車輛短程通信的混淆組車輛會在適當?shù)臅r候，為彼此產(chǎn)生相互模糊的軌跡路徑。在交叉路口道路條件下，且實時更新和高精度的位置變化情況下，VATW具有很強的隱私保護性能。

如圖1所示，假設(shè)有即將靠近交叉路口的4輛車可自行計算其滿足的自適應(yīng)車輛混淆保護機制。當目標車輛在抵達交叉路口時，計算該目標車輛的軌跡熵閾值是否滿足S

圖1 多車輛路徑混淆的現(xiàn)實場景Fig.1 Real-world scenario of multi-vehicle path confusion

之后，車輛D在該位置點建立車輛混淆組，并通過車輛短程通信廣播目標車輛將建立混淆組的消息。接收到目標車輛的廣播請求后，臨近車輛計算當前時刻車輛運行速度是否與目標車輛速度相近。

其中，Vi表示混淆組中除目標車輛的車輛速度，V表示目標車輛的速度。ε是目標車輛速度變化。如果附近車輛速度、方向等運動軌跡與目標車輛適配，那么該車輛則向目標車輛發(fā)送加入請求I=(ID,T,V,Va)，其中ID作為標識符，T表示車輛該時刻所在軌跡位置，V、Va分別為車輛的速度和加速度，L是混淆車輛與目標車輛產(chǎn)生虛假軌跡的位置點。

綜上所述，有關(guān)于VATW算法的具體偽代碼如下所示。

算法1基于車輛自適應(yīng)混淆算法

2.3 車輛自適應(yīng)時間窗口算法

基于時間窗口ω模型的軌跡隱私保護機制設(shè)計如下：時間窗口初始時間輸入St=(d1,d2,…,dt)，輸出為每個時刻測量值T=(t1,t2,…,tt)∈T。機制Γ由n個子機制組成，其中機制Γ中包含t個獨立隨機數(shù)，機制Γi在t'時刻的操作，即Γi(di)=ti，且每一個機制Γi都滿足軌跡隱私的保護需求。

由于Γ中的任意時間窗口都滿足獨立隨機性，所以針對時間窗口初始時間St=(d1,d2,…,dt)的任意一個時間點的輸入T=(t1,t2,…,tt)∈T都可以滿足：

同理，對于St的任意一個ω模型的相鄰窗口初始值為S't，且同樣滿足輸出T=(t1,t2,…,tt)∈T：

存在一個i=[1 ,2,…,t],對于1≤x≤t'-w和t'+1≤x≤t，滿足dx=dx'，將公式（8）與（9）相除，得到時間窗口公式：

通過比較發(fā)現(xiàn)，當t'-w+1≤x≤t'時，dx和d'x是相鄰的，因為Γ滿足車輛軌跡隱私，所以根據(jù)差分隱私的定義，機制Γ滿足：

在道路交叉路口所在覆蓋范圍R中，對于該范圍內(nèi)車輛記為u，車輛周圍用戶密度群pu，即目標車輛周圍可覆蓋范圍內(nèi)其他車輛個數(shù)為n(pu,m)，當m=1時，即目標車輛下一時刻短程通信所覆蓋的平均車輛數(shù)目(m≥1),pu通過增加鄰居節(jié)點個數(shù)m來在自身基礎(chǔ)上進行實時更新，此處利用極大似然估計算法來計算短程通信范圍內(nèi)覆蓋的平均車輛數(shù)量：

其中，Ru表示下一時刻目標車輛覆蓋范圍內(nèi)周圍用戶的總數(shù)量。

由于車輛在進行短程通信廣播信息時并不是處于理想環(huán)境下進行的通信傳輸，所以需要考慮非理想情況下的目標車輛的短程通信情況，并且需要考慮接受信息的其他用戶總數(shù)。因此，需要加入損耗因子θ，計算方法為：

顯然，當h值越大時，覆蓋范圍內(nèi)的用戶數(shù)量就會增多，此時目標車輛進行廣播通訊就會導(dǎo)致短程通信產(chǎn)生過多通信鏈路，造成通信開銷增大。

利用算法2，將車輛短程通信覆蓋范圍與時間窗口算法相結(jié)合提出了車輛自適應(yīng)時間窗口算法。其中，車輛的軌跡數(shù)據(jù)存儲在依靠采樣時間排序的隊列中，并為每個車輛的軌跡位置構(gòu)建一個鄰接表，通過指向相鄰車輛節(jié)點而形成一個基于時間事件的距離軌跡關(guān)系網(wǎng)絡(luò)。對于即將到達路口前一時刻時，首先通過目標車輛的短程通信來對這一時刻可覆蓋范圍內(nèi)的，即將到達該采樣時間點的周邊車輛軌跡進行篩選。然后，選擇一個車輛的虛假軌跡點p*，并將該位置點插入到p中。如果找不到合適的周邊車輛位置點L'，將會刪除它的原始位置點集合L，那么該車輛位置則不被選入最終的覆蓋范圍。最后確認發(fā)布的窗口時間為目標車輛通過交叉路口的時間，以該時間范圍作為其他車輛軌跡位置點的選取范圍。

算法2車輛自適應(yīng)時間窗口算法

3 實驗結(jié)果與分析

3.1 實驗數(shù)據(jù)及環(huán)境

在實驗中分別與兩種車輛交互算法MOP（相互交叉路徑）和OPVC（信息交互路徑）在同應(yīng)用場景下的真實數(shù)據(jù)集France中進行對比實驗。其中，F(xiàn)rance數(shù)據(jù)集為法國克雷泰伊一個環(huán)形道路條件下的車輛行駛軌跡數(shù)據(jù)，軌跡數(shù)據(jù)采樣時間的間隔為1 s，該車輛數(shù)據(jù)集包含有車輛ID信息、時間間隔、車輛類型、位置點坐標、車輛速度。

同時，對VATW算法在相同空間和網(wǎng)絡(luò)環(huán)境下與ASDA（相似區(qū)域）、UUDA（密度相似）和P2P（點對點）方法進行對比實驗。從公式（5）可以得出在計算車輛軌跡熵時，其數(shù)據(jù)分布狀況明顯高于其他算法，本文算法在軌跡保護性能上優(yōu)于其他算法。但也不難從計算結(jié)果中發(fā)現(xiàn)本方案對于目標車輛運行軌跡出現(xiàn)在城市邊界或其他車輛行駛較為稀疏的區(qū)域時，所能達到的隱私保護程度并不高，但是如果目標車輛所處環(huán)境較為復(fù)雜或是在城市交通環(huán)境中，那么本方案的保護效果明顯更好。實驗涉及的參數(shù)設(shè)置如表1所示。

表1 仿真參數(shù)設(shè)置Table 1 Simulation parameters

3.2 VATW混淆算法評估

圖2～圖4展示了本文方案在不同實際場景下，目標車輛在經(jīng)過交叉路口時車輛軌跡熵變化。圖2表示VATW方案車輛在相同時間范圍內(nèi)軌跡熵的變化情況。在該實驗條件下如果攻擊者想要攻擊目標車輛時，此時攻擊者需要判斷的行駛軌跡至少有64條，比相互混淆路徑方案多32條虛假軌跡。

圖2 VATW方案軌跡熵變化Fig.2 Change of trajectory entropy of VATW scheme

圖3 OPVC方案軌跡熵變化Fig.3 Change of trajectory entropy of OPVC scheme

圖4 MOP方案軌跡熵變化Fig.4 Change of trajectory entropy of MOP scheme

對比實驗表明本文方案在保護車輛實時軌跡數(shù)據(jù)方面優(yōu)于相互混淆路徑和相互協(xié)作路徑方案。另外，在前2 min內(nèi)VATW方案下，車輛軌跡熵增長速率比其他兩種方案變化更快，軌跡熵的增長速度表明VATW方案可以在更短時間內(nèi)達到車輛需要滿足的軌跡隱私保護效果。實驗結(jié)果表明部分車輛在達到軌跡隱私保護閾值的情況下，車輛軌跡熵不再增加。這樣就可以減少車輛在進行混淆計算和信息交換時產(chǎn)生的資源損耗。

圖5～圖7實驗表明車輛軌跡跟蹤率與車輛密度之間的關(guān)系。在現(xiàn)實情況下，由于周圍車輛較少而產(chǎn)生的虛假軌跡不足時，導(dǎo)致目標車輛未能達到車輛軌跡熵閾值。相互混淆路徑方案由于算法限制通常只能在每次混淆過程中生成一條虛假軌跡，所以在實驗時間范圍內(nèi)軌跡跟蹤率比相互協(xié)作路徑要低很多。而本文方案在選擇路徑混淆軌跡時增加了目標車輛的混淆機會并增大了車輛軌跡數(shù)據(jù)的可用性。

圖5 VATW方案軌跡成功跟蹤率Fig.5 Tracking success rate of VATW scheme

圖6 OPVC方案軌跡跟蹤成功率Fig.6 Tracking success rate of OPVC scheme

圖7 MOP方案軌跡跟蹤成功率Fig.7 Tracking success rate of MOP scheme

由圖5所示，VATW可以在第4 min時將攻擊者的軌跡跟蹤率下降到0.1，比OPVC和相互混淆路徑方案早1 min，這就說明了該方案具有更好的軌跡隱私保護效果。所以即使車輛密度較少時，軌跡跟蹤成功率也可以近乎為趨于0的狀態(tài)。從軌跡跟蹤的成功率來說，在目前的算法中雖然無法做到杜絕一切跟蹤，但可以通過該算法將攻擊者的跟蹤率進行無限降低，直到趨于零。

3.3 可用性分析

圖8展示了VATW算法與其他算法在進行區(qū)域劃分時的車輛軌跡被攻擊成功的示意圖。由于點對點算法不存在車輛軌跡范圍的劃分，所以該算法進行區(qū)域劃分是會造成軌跡攻擊概率的增加，而ASDA和USA是在軌跡隱私保護的基礎(chǔ)上再進行子區(qū)域劃分，可以有效保證車輛被攻擊的概率有所降低。由于本文提出的VATW算法可以通過車輛間的短程通信感知目標車輛的周圍車輛分布密度，并通過添加虛假軌跡位置點進行路徑混淆，從而進一步降低車輛被攻擊的概率。

圖8 劃分子區(qū)域?qū)现\攻擊率的影響Fig.8 Effect of dividing sub-regions on colluding attack rate

圖9是在VATW算法下選擇不同K匿名值時車輛軌跡匿名成功率對比圖。由圖可見，當車輛數(shù)目隨著K匿名值增加時，此時的軌跡匿名成功率就越大；而當K值減少車輛數(shù)目不變時，就會導(dǎo)致車輛軌跡信息匿名失敗的可能。因此，在VATW自適應(yīng)時間窗口內(nèi)選擇合適的K匿名值是至關(guān)重要的。

圖9 K值對匿名成功率的影響Fig.9 Influence ofK value on success rate of anonymity

圖10顯示了四種算法在不同K匿名值下生成的數(shù)據(jù)信息損失率。在軌跡數(shù)據(jù)發(fā)布上傳的過程中信息損失主要來源于K匿名程度，其次是軌跡數(shù)據(jù)的選取密度范圍。軌跡位置點的密度越高，軌跡匿名就越容易，這樣軌跡信息的損失就越少。根據(jù)車輛軌跡隱私保護水平，NWA的信息損失最大，因為基于軌跡K匿名的方法不可避免地會受到維度詛咒的影響。而DLBG和DPAT算法都是基于軌跡段的K匿名隱私保護算法，所以這兩種算法的軌跡信息損失要小于NWA。但是DLBG比DPAT算法數(shù)據(jù)損失高，這是由于隨著軌跡增加DLBG精度就會下降。而DPAT中的截斷策略會減少車輛隱私保護數(shù)據(jù)的維度，從而提高軌跡發(fā)布數(shù)據(jù)的準確性。VATW算法是基于實時車輛軌跡位置點的方法，在本文方案下軌跡隱私保護數(shù)據(jù)的維數(shù)為1，因此VATW生成的軌跡數(shù)據(jù)的信息損失最小。

圖10 數(shù)據(jù)損失Fig.10 Data loss

在針對軌跡數(shù)據(jù)可用性的情況下，本文算法在數(shù)據(jù)損失和平均匿名時間上與傳統(tǒng)的NWA、DLBG和DPAT等方法相比具有更高的可用性。

4 結(jié)束語

針對實時軌跡發(fā)布的隱私保護問題，提出了一種基于路徑混淆的實時軌跡的數(shù)據(jù)發(fā)布隱私保護算法。在構(gòu)建車輛軌跡混淆組中，首先利用車輛的真實軌跡和通過路口時產(chǎn)生的虛假軌跡計算軌跡熵值，并對路口范圍內(nèi)車輛進行假軌跡的匹配，這些假軌跡可以與目標車輛真實軌跡相交的車輛作為軌跡混淆組。滿足該條件的車輛通過自感知時間窗口算法對目標車輛時間范圍內(nèi)滿足條件的車輛進行劃分，從而達到良好的軌跡隱私保護效果，保證實時位置的精確，滿足個性化軌跡保護需求。最后，通過本算法與經(jīng)典算法MOP和OPVC的軌跡熵響應(yīng)時間進行對比分析，實驗結(jié)果驗證了所提算法在短時間范圍內(nèi)有著良好的數(shù)據(jù)效用與隱私保護性能。