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

0 引言

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

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

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

1 軌跡隱私問題

1.1 基本概念

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

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

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

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

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

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

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

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

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

2 軌跡隱私保護(hù)方法

為解決基于組的方法帶來的弊端，研究者將用戶的移動(dòng)趨勢(shì)引入到軌跡隱私保護(hù)方法中?；谝苿?dòng)趨勢(shì)的方法分為基于移動(dòng)方向和基于位置預(yù)測(cè)的軌跡隱私保護(hù)技術(shù)。

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

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

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

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

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

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

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

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

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

2.2 基于位置預(yù)測(cè)的軌跡隱私保護(hù)技術(shù)

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

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

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

3 展望

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

4 結(jié)語

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