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

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

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

2.網絡文化與數字傳播北京市重點實驗室，北京 110101

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

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

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

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

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

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

1 相關工作

路徑混淆一般用來解決車輛在軌跡信息傳輸過程中產生的數據泄露問題，其利用車輛自身的計算和空間存儲能力來提高車輛進行軌跡信息交換中的隱私保護效果。混淆的目的就是對目標車輛及其周邊車輛的軌跡信息進行交叉從而保護目標車輛。

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

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

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

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

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

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

2 本文方法

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

2.1 軌跡熵

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

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

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

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

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

當車輛運行過程途經M個交叉路口并進行路徑混淆時，目標車輛真實軌跡和周圍聯合產生的真假軌跡的總數N最少為：

車輛總軌跡熵S表示為：

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

2.2 路徑混淆算法

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

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

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

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

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

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

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

算法1基于車輛自適應混淆算法

2.3 車輛自適應時間窗口算法

基于時間窗口ω模型的軌跡隱私保護機制設計如下：時間窗口初始時間輸入St=(d1,d2,…,dt)，輸出為每個時刻測量值T=(t1,t2,…,tt)∈T。機制Γ由n個子機制組成，其中機制Γ中包含t個獨立隨機數，機制Γ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）相除，得到時間窗口公式：

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

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

其中，Ru表示下一時刻目標車輛覆蓋范圍內周圍用戶的總數量。

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

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

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

算法2車輛自適應時間窗口算法

3 實驗結果與分析

3.1 實驗數據及環境

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

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

表1 仿真參數設置Table 1 Simulation parameters

3.2 VATW混淆算法評估

圖2～圖4展示了本文方案在不同實際場景下，目標車輛在經過交叉路口時車輛軌跡熵變化。圖2表示VATW方案車輛在相同時間范圍內軌跡熵的變化情況。在該實驗條件下如果攻擊者想要攻擊目標車輛時，此時攻擊者需要判斷的行駛軌跡至少有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

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

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

圖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的狀態。從軌跡跟蹤的成功率來說，在目前的算法中雖然無法做到杜絕一切跟蹤，但可以通過該算法將攻擊者的跟蹤率進行無限降低，直到趨于零。

3.3 可用性分析

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

圖8 劃分子區域對合謀攻擊率的影響Fig.8 Effect of dividing sub-regions on colluding attack rate

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

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

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

圖10 數據損失Fig.10 Data loss

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

4 結束語

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