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

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

0 引言

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

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

為解決連續(xù)查詢中的軌跡隱私保護問題，已研究出多種軌跡隱私保護技術(shù)，主要分為虛假軌跡法、軌跡抑制法和軌跡泛化法3 種［8-9］。這3 種技術(shù)各有優(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ù)分析用戶敏感數(shù)據(jù)，從而獲得利益。

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

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

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

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

基于組的方法屬于一種軌跡泛化法，可在連續(xù)查詢中保護用戶軌跡隱私。該方法根據(jù)用戶隱私需求k，將查詢用戶與附近的k-1 個用戶劃分在一個組，使分組中的用戶共享匿名區(qū)域，并且在連續(xù)快照中k 個用戶始終保持在相同的分組內(nèi)［12］。如圖2 所示，在連續(xù)查詢中用戶A 滿足4-匿名。將ti作為用戶提交初始查詢的時刻，匿名服務(wù)器將從用戶A 附近選擇3 個用戶形成一個組{A,B,C,D}。在后續(xù)查詢ti+1中，匿名服務(wù)器只需根據(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)生許多額外的候選結(jié)果，這將增加網(wǎng)絡(luò)傳輸負擔(dān)及匿名服務(wù)器對候選結(jié)果求精的計算開銷，使服務(wù)質(zhì)量變差。因此，如何在泛化方法中尋找隱私與服務(wù)質(zhì)量的平衡點具有重要的現(xiàn)實意義。

2 軌跡隱私保護方法

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

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

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

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

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

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

其中，P=Aheight+Awidth。匿名集在查詢中的總扭曲度表示為：。當(dāng)匿名查詢到達時，匿名算法會將查詢用戶與其它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 基于位置預(yù)測的軌跡隱私保護技術(shù)

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

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

Fig.4 Snet hierarchy圖4 Snet 層次結(jié)構(gòu)

3 展望

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

4 結(jié)語

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