基于移動趨勢的軌跡隱私保護研究綜述

（曲阜師范大學 計算機學院，山東 日照 276826）

0 引言

隨著移動設備的普及，基于位置的服務（Location-Based Service，LBS）廣泛應用于人們日常生活［1］。通過定位設備獲得位置信息，移動用戶可享受位置服務提供商（Location Services Provider，LSP）的各類服務，如在社交網絡中搜索附近的人，使用導航功能到達目的地等［2］。一般而言，用戶可向LSP 發送快照查詢和連續查詢［3］。如“查找距離我最近的醫院”這類查詢就是快照查詢，用戶只需在當前位置提交一次查詢請求便可獲得所需服務。連續查詢由同一用戶在連續時間內提交多個快照查詢組成，如在接下來的30 分鐘內尋找距離我最近的醫院。

然而在查詢過程中，用戶將位置和查詢提交給LSP后，不知道LSP 如何處理自己的位置信息，這為個人敏感隱私泄露埋下隱患［4］。惡意攻擊者可根據用戶的位置信息窺探用戶隱私。顯然，在連續查詢中，用戶個人隱私泄露情況要比快照查詢更嚴重。攻擊者可跟蹤用戶的連續查詢獲得用戶軌跡，而軌跡中的位置信息具有時間和空間相關性，有助于攻擊者推斷用戶的日常行為特征，造成個人敏感信息泄露［5］。因此，連續查詢中的隱私保護更為重要［6-7］。

為解決連續查詢中的軌跡隱私保護問題，已研究出多種軌跡隱私保護技術，主要分為虛假軌跡法、軌跡抑制法和軌跡泛化法3 種［8-9］。這3 種技術各有優缺點，本文研究軌跡泛化法。首先介紹軌跡隱私概念及基于組的方法優缺點，然后歸納基于移動趨勢方法，最后對未來工作進行展望。

1 軌跡隱私問題

1.1 基本概念

軌跡是指移動用戶的位置按時間先后順序連接起來形成的路線［10］。可將軌跡模型表示為三維空間中的折線。線段兩端分別為用戶在相鄰時間的位置點pi=(xi,yi,ti)，其中(xi,yi)是用戶在地理空間中的坐標，ti表示時間戳。n個連續位置序列組成的軌跡可表示為T:p1→p2→…→pn。

隱私指個人不愿他人知道不想公開的信息。隱私具有較強的主觀性，每個人對隱私的理解不同，定義標準也不同，所以不存在統一界定的隱私，但每個人都不想將一些私密的信息公開或被他人竊取，因此保護隱私不被泄露成為一個重要課題。然而，隨著科技的不斷發展，保護個人隱私變得越來越困難。用戶會在不經意間公開大量個人信息，攻擊者利用所獲得的各類信息，通過數據挖掘技術分析用戶敏感數據，從而獲得利益。

軌跡隱私是由用戶的軌跡暴露所引起的，攻擊者可根據所獲得的軌跡分析并推斷軌跡中包含的敏感信息，如根據用戶經常訪問的位置以及訪問過的敏感位置推斷用戶的興趣愛好等。因此，保護軌跡隱私不被泄露十分重要［11］。

1.2 連續查詢中的軌跡隱私保護

在連續查詢中，軌跡數據是動態變化的。在可信的中心服務器架構中，匿名服務器需要以較高的速率處理大量實時位置。雖然連續查詢由多個連續的快照查詢組成，但由于軌跡所具有的時間和空間關聯性，不能直接將快照查詢隱私保護技術用于連續查詢。如圖1 所示，用戶A 在不同時刻ti和ti+1分別形成2 個不同的匿名集{A,B,C,D}和{A,E,F,G}。對于每個快照，攻擊者只能以1/4 的概率識別查詢提出者，位置隱私得到保護。但將兩個匿名集關聯使2 個匿名集取交集，就可清楚看到用戶A 為查詢提出者。更嚴重的是，將匿名區域連接起來便可獲得A 的大致軌跡。同時，如果每次位置更新時都重新為用戶構建匿名集，將加重匿名服務器計算開銷，使匿名服務器成為系統瓶頸，為此需開發很多新技術用于保護連續查詢中的軌跡隱私。

Fig.1 K-anomity圖1 位置k-匿名

基于組的方法屬于一種軌跡泛化法，可在連續查詢中保護用戶軌跡隱私。該方法根據用戶隱私需求k，將查詢用戶與附近的k-1 個用戶劃分在一個組，使分組中的用戶共享匿名區域，并且在連續快照中k 個用戶始終保持在相同的分組內［12］。如圖2 所示，在連續查詢中用戶A 滿足4-匿名。將ti作為用戶提交初始查詢的時刻，匿名服務器將從用戶A 附近選擇3 個用戶形成一個組{A,B,C,D}。在后續查詢ti+1中，匿名服務器只需根據組{A,B,C,D}中用戶更新的位置數據重新計算匿名區域，不需要重新為A 尋找新的組。

Fig.2 Method based on group圖2 基于組的方法

這種方法可以抵抗連續查詢攻擊和采樣攻擊，在連續查詢中有效保護用戶的軌跡隱私，甚至可以在用戶位置泄露的情況下保護用戶的查詢不被泄露。但是，正如圖2（b）所示，由于用戶的查詢方向不一致，在一段時間后，組內用戶覆蓋的匿名區域會變得非常大。雖然匿名區域越大包含的用戶數越多，攻擊者識別查詢用戶的概率越低，但也會增加LSP 的計算開銷，產生許多額外的候選結果，這將增加網絡傳輸負擔及匿名服務器對候選結果求精的計算開銷，使服務質量變差。因此，如何在泛化方法中尋找隱私與服務質量的平衡點具有重要的現實意義。

2 軌跡隱私保護方法

為解決基于組的方法帶來的弊端，研究者將用戶的移動趨勢引入到軌跡隱私保護方法中?；谝苿于厔莸姆椒ǚ譃榛谝苿臃较蚝突谖恢妙A測的軌跡隱私保護技術。

2.1 基于移動方向的軌跡隱私保護技術

在基于組的方法中，由于匿名集中用戶移動方向不同，在后續連續查詢中，用戶的匿名區域會逐漸變大，這降低了LBS 的服務質量。因此，構建K-匿名集時有必要考慮用戶的移動方向。

Shin 等［13］在匿名過程中引入用戶移動方向，選擇移動方向與用戶查詢方向相同的k個用戶以確保k-匿名。然而該方法要求過于嚴格，具有相同方向的k個用戶可能導致過大的匿名區域。后來作者放寬限制，匿名集中的用戶只要滿足P(Q=ui|D=r?d)≤1/k即可。也就是說，找到后驗概率分布小于或等于的一組用戶，這樣攻擊者就無法從匿名集中識別出實際的查詢請求者了。其中，Q=ui表示查詢的請求者為ui，D=r?d表示查詢請求r的移動方向為d。然而，該方法僅考慮用戶初始查詢時的方向，忽視了后續連續快照的匿名區域大小，無法使服務質量達到全局最優。

為使用戶在查詢生命周期中匿名區域面積達到最優，Pan 等［14］提出一種貪心匿名算法。該方法首先根據匿名集中用戶的移動方向、速度以及查詢時間，預測出連續查詢中每個快照的匿名區域；然后根據預測的匿名區域，利用位置扭曲度確定最終的匿名集。如圖3 所示，R1 包含3 個用戶的匿名區域，假設這3 個用戶維持原來方向前進，那么t2時刻，用戶的匿名區域將為R2。對每個區域R，位置扭曲度可以表示為：

其中，(Lx-,Ly-)和(Lx+,Ly+)分別為匿名區域R在t時刻的左下角和右上角坐標，Aheight和Awidth為整個空間的寬和高。用戶在查詢有效期內的總位置扭曲度可表示為：

其中，P=Aheight+Awidth。匿名集在查詢中的總扭曲度表示為：。當匿名查詢到達時，匿名算法會將查詢用戶與其它k-1 個未匿名的用戶組成一個匿名集，使匿名集中的位置扭曲度達到最小。但該方法忽略了現實的運動環境，移動方向會實時變化，使用移動方向判斷未來匿名區域的大小誤差很大。

Fig.3 Greedy anonymous method圖3 貪心匿名法

Gustav 等［15］提出方向速度動態匿名算法，該算法選擇具有相似方向、相似速度和相同傳輸模式的用戶實現軌跡k-匿名。令兩個用戶位置分別為l(xi,yi)和l(xj,yj)，相對于原始位置l(x0,y0)，兩個用戶查詢角度可表示為θi和θj。根據定義的角度方向相似性simθ可計算如下：

在匿名過程中，匿名集中用戶要滿足simθ(q,q')≤θ，q和q'表示查詢，θ為AS 根據歷史數據確定的閾值。該方法雖然考慮到用戶交通方式的不同，但同樣忽視了移動方向及速度變化的可能性，對處理用戶動態改變路線情況不夠靈活，無法解決突發事件影響。

2.2 基于位置預測的軌跡隱私保護技術

由于在復雜環境中用戶的移動方向不停地改變，移動方向不再適合作為用戶的移動趨勢，所以研究者提出基于位置預測的方法，通過挖掘歷史數據中的運動規律預測用戶未來可能到達的位置。Monreale 等［16］考慮移動用戶群體模式，提出基于軌跡模式的位置預測方法，但是該方法忽略用戶間的相似性，預測精度不高；李雯等［17］提出基于運動趨勢的移動對象預測算法，根據歷史軌跡建立馬爾可夫模型預測用戶的移動位置，并采用用戶運動趨勢進一步完善預測結果，但該方法沒有考慮多個移動用戶的局部相似性。目前已有多種預測模型應用于位置預測中，如神經網絡、貝葉斯網絡、馬爾可夫模型等，但是還沒有最優的解決方法，需要根據不同情況選擇不同的預測模型；Liu 等［18］通過融合多種預測模型以增強預測結果的準確度；張少波等［19］將馬爾可夫模型預測的位置應用于軌跡隱私保護，使用預測的位置形成匿名區域。

在道路網絡中，Wang 等［20］提出一種基于Snet 層級結構的隱私保護方法。該方法預先將道路網絡抽象為加權有向圖G=(V,E)；然后根據歷史記錄計算的轉移概率構建Snet 層次結構，每一個Snet 單元都可作為用戶的匿名單元；為確保匿名集中的用戶可以長期處于同一個Snet 中，該方法根據用戶移動趨勢、速度及到邊界點的距離選擇匿名用戶。其中，用戶的移動趨勢使用當前Snet 及相鄰Snet的馬爾科夫鏈進行建模。如圖4 所示，將道路構建為4 層的Snet 層次結構，其中點集V={v1,v2,...,v7}代表路口，邊為兩個路口之間的線段，每一條邊都代表一個Snet 單元。例如snetS12由 邊(v3,v5)和(v4,v5)構成，其中，(v3,v5)為SnetS03，(v4,v5)為SnetS04。其轉移矩陣表示用戶的移動趨勢。轉移矩陣中第一行為邊(v3,v5)到S11及S13的轉移概率，第二行為邊(v4,v5)到S11及S13的轉移概率。在構建匿名集時，用戶的移動趨勢將作為一個重要因素選擇合格的匿名者。但上述方法沒有給出概率預測失誤后的解決方案，并忽視了現實交通環境，如交通狀況及十字路口對移動用戶的影響。

Fig.4 Snet hierarchy圖4 Snet 層次結構

3 展望

基于移動趨勢的軌跡隱私保護方法可有效減少泛化法帶來的匿名區域過大問題?，F實交通環境較為復雜，用戶的速度變化、交通擁堵程度以及無意間的行駛錯誤都可能導致用戶匿名區域變大，從而降低用戶服務質量。如何將這些因素考慮到移動趨勢中，使用戶臨近未來位置，是基于移動趨勢的軌跡隱私保護方法重要的研究方向。此外，現在的方法往往將全部用戶作為研究對象，但用戶的運動規律通常與移動對象種類相關，這就導致預測模型可能對某個種類的用戶移動趨勢預測不準確。因此，需將移動用戶進行分類分析，增強不同模型對個體運動的適應性。

4 結語

本文對基于移動趨勢的軌跡隱私保護技術進行了綜述。首先介紹了軌跡和軌跡隱私概念，指出連續查詢中基于組的軌跡隱私保護優缺點，介紹了基于移動趨勢的軌跡隱私保護方法，然后分別對基于移動方向和位置預測的軌跡隱私保護技術進行了歸納總結，展望了未來的研究方向。