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

0 引言

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

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

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

1 軌跡隱私問題

1.1 基本概念

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

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

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

1.2 連續(xù)查詢中的軌跡隱私保護

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

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

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

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

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

2 軌跡隱私保護方法

為解決基于組的方法帶來的弊端，研究者將用戶的移動趨勢引入到軌跡隱私保護方法中。基于移動趨勢的方法分為基于移動方向和基于位置預測的軌跡隱私保護技術。

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

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

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

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

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

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

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

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

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

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

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

在道路網(wǎng)絡中，Wang 等［20］提出一種基于Snet 層級結構的隱私保護方法。該方法預先將道路網(wǎng)絡抽象為加權有向圖G=(V,E)；然后根據(jù)歷史記錄計算的轉移概率構建Snet 層次結構，每一個Snet 單元都可作為用戶的匿名單元；為確保匿名集中的用戶可以長期處于同一個Snet 中，該方法根據(jù)用戶移動趨勢、速度及到邊界點的距離選擇匿名用戶。其中，用戶的移動趨勢使用當前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的轉移概率。在構建匿名集時，用戶的移動趨勢將作為一個重要因素選擇合格的匿名者。但上述方法沒有給出概率預測失誤后的解決方案，并忽視了現(xiàn)實交通環(huán)境，如交通狀況及十字路口對移動用戶的影響。

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

3 展望

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

4 結語

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