葉阿勇，孟玲玉，趙子文，刁一晴，張嬌美

（1.福建師范大學數(shù)學與信息學院，福建 福州 350007；2.福建省網(wǎng)絡安全與密碼技術重點實驗室，福建 福州 350007）

1 引言

近幾年來，隨著具有定位功能的智能終端和移動通信技術的迅猛發(fā)展，各種基于位置的服務（LBS,location based service）日益普及，現(xiàn)已覆蓋國民經(jīng)濟和社會生活的方方面面，如導航、興趣點查詢與推薦、外賣、簽到、社交網(wǎng)絡等[1]。然而，LBS 為人們的日常生活帶來極大便利的同時，也產(chǎn)生了位置隱私泄露問題。其中尤其突出的是，位置服務提供商可能會利用數(shù)據(jù)挖掘等技術，從用戶提交的位置信息中非法獲取用戶的敏感信息，如家庭/工作地址、消費水平、健康狀況、生活習慣等[2]。

地理不可區(qū)分性[3]隱私保護模型是目前LBS 位置隱私保護中常見的方法，它將差分隱私[4]引入幾何空間中，克服了傳統(tǒng)k-匿名等模型普遍存在“依賴于攻擊者背景知識而導致其安全性無法嚴格證明”的缺點。地理不可區(qū)分性模型是通過極坐標系下的Laplace 擾動機制向用戶位置添加受控噪聲，使攻擊者幾乎無法區(qū)分近似位置與真實位置的差異，從而將用戶真實位置保護在一個半徑為r的圓形區(qū)域內(nèi)。位置差分隱私的定義是建立在嚴格數(shù)學統(tǒng)計模型上，并可通過調(diào)整隱私參數(shù)來控制隱私保護水平，因此備受關注。然而，現(xiàn)有的位置差分隱私保護研究仍然存在以下兩方面的問題。

1)現(xiàn)有的位置差分保護機制僅適用于單次或零星查詢，多次查詢?nèi)杂锌赡鼙┞队脩舻恼鎸嵨恢?。因為連續(xù)查詢的位置間存在時空相關性，服務查詢不僅會消耗當前位置的隱私成本，而且也會增加其他位置的隱私消耗，即差分隱私具有序列組合特性。因此，單個位置滿足ε-差分隱私，并不能確保軌跡滿足ε-差分隱私。

2)現(xiàn)有的差分隱私保護技術并沒有很好地解決隱私風險與服務質(zhì)量間的矛盾問題；位置差分隱私中，每個擾動的位置輸出具有一定的隨機性，隱私預算越小，隱私保護程度越高，但是該位置的服務質(zhì)量會越差。隱私風險與服務質(zhì)量顧此失彼，難以得到平衡。

位置預測是指通過觀察已公開的信息（如歷史發(fā)布的軌跡）來預測用戶當前的位置。由于預測機制與用戶當前的真實位置無關，不會給攻擊者提供更多有用信息，因此隱私損失非常小，甚至可視為0。因此本文嘗試利用預測機制替代差分擾動，以節(jié)省隱私開銷，即降低隱私風險。基于上述分析，本文提出一種基于預測和滑動窗口的軌跡差分隱私保護機制，主要貢獻如下。

1)提出一種融合預測擾動的差分查詢機制，以降低連續(xù)查詢的隱私開銷。首先，利用馬爾可夫鏈和指數(shù)擾動機制預測滿足差分安全和時空相關性約束的查詢位置。然后，引入服務相似地圖機制檢測預測位置的可用性，如果滿足可用性要求，則采用預測位置查詢，否則使用差分擾動的位置查詢。

2)設計基于w滑動窗口的軌跡隱私預算分配機制，確保軌跡中任意連續(xù)的w次查詢隱私消耗累計不超過ε，即確保軌跡滿足ε-差分隱私，從而解決連續(xù)查詢的位置隱私安全問題。

3)設計基于敏感度地圖的位置隱私差異化保護機制。通過允許用戶自定義位置的敏感度，實現(xiàn)隱私預算的量身定制，進一步提高隱私預算的利用率。

4)利用真實數(shù)據(jù)集對本文方案進行實驗分析，驗證方案的有效性。

2 相關工作

在過去的幾年中，研究者已提出許多的位置隱私保護方案和技術。根據(jù)保護機理的不同，本文將其分為匿名和擾動兩大類。

k-匿名[5]是目前最被廣泛應用的位置隱私保護機制。其思想是采用一個包含至少k-1 個用戶的區(qū)域來替代用戶的實際位置，用于向LBS 請求服務。在該定義中，用戶的身份至少與k-1 個人不可區(qū)分，從而有效地解決不可信服務器帶來的身份隱私泄露問題。例如，Niu 等[6]提出了一種虛擬位置選擇算法來實現(xiàn)LBS 中用戶的k-匿名性。Hwang 等[7]提出了一種基于歷史軌跡的時間模糊算法。在該算法中，TTP 在選定k-1 條歷史軌跡后，擾動每個查詢軌跡的時間序列，產(chǎn)生空間和時間的雙重混淆。Wang等[8]對位置k-匿名的有效解決方案進行了研究，并定義了一種用于初始化位置k-匿名的概率模型PkA(probabilistick-anonymity framework)，也證明了DLS(dummy-location selection)算法屬于PkA。

位置擾動是指用戶請求LBS 時，以假位置替代或者混合自身的真實位置，從而保護位置隱私。例如，文獻[9]提出一種基于假查詢的連續(xù)位置服務隱私保護機制，該機制根據(jù)鄰居節(jié)點的運動速率和方向預測將來的軌跡；在此基礎上，選出軌跡與查詢用戶相近的k-1 個鄰居節(jié)點；在匿名處理時，通過發(fā)動這些鄰居節(jié)點插入假查詢，來構(gòu)造虛假的連續(xù)查詢。Andres 等[3]基于差分隱私的思想提出了地理不可區(qū)分性的位置隱私模型，并設計了一種極坐標下的Laplace 機制產(chǎn)生假位置，以實現(xiàn)位置隱私保護。文獻[10]在文獻[3]的基礎上將差分隱私機制看成是最優(yōu)化問題，提出了一種基于δ-spanner 的近似解決方案。Xiao 等[11]用馬爾可夫鏈表示位置上的時序關系，并重新定義相鄰數(shù)據(jù)集的概念，提出了一種基于凸包的差分隱私位置發(fā)布機制。Hua 等[12]提出了在短時間連續(xù)查詢時，基于差分隱私的位置隱私保護方法，解決了連續(xù)查詢時隱私風險與查詢次數(shù)成線性增長的問題。吳云乘等[13]基于馬爾可夫概率轉(zhuǎn)移矩陣，分析了發(fā)布位置對當前真實位置和之前真實位置的影響，提出了一種差分隱私位置發(fā)布機制（DPLRM,privacy location release mechanism），以保護用戶的位置和軌跡隱私。Chatzikokolakis 等[14]提出一種預測擾動機制（PM,predictive mechanism for mobility trace），利用預測位置替代真實位置，解決連續(xù)查詢的隱私與可用性的兩難問題。

3 背景知識

3.1 位置差分隱私

定義1ε-差分隱私。?x，x'∈X，在查詢機制M下輸出的位置o，若滿足式(1)，則稱算法M滿足ε-差分隱私

其中，M(x)(o)為原始輸入x在擾動機制M下輸出結(jié)果為o的概率，該定義表明2 個原始輸入越接近，則輸出同一位置的概率越高，即2 個源位置不可區(qū)分，從而達到保護用戶位置隱私的目的；ε為一個距離單位的隱私預算，代表隱私保護的程度，ε越小，隱私保護程度越高，當ε=0 時，隱私保護程度最高，表示沒有泄露用戶的任何隱私。

dx(x,x')是測量矩陣，不同的dx(x,x')模型可以解決不同應用場景的差分隱私問題。如數(shù)據(jù)庫查詢隱私保護模型中[4]，dx(x,x')=1 表示2 個統(tǒng)計數(shù)據(jù)庫x和x'僅相差一條紀錄。該模型保證數(shù)據(jù)集中增加和刪除任意一條記錄都不會影響輸出的結(jié)果，即無法得知數(shù)據(jù)集中是否存在某條記錄，從而達到保護數(shù)據(jù)隱私的目的。該定義只是理論上的一個模型，而要實現(xiàn)具體的保護則需要噪聲機制的介入。對于數(shù)值型數(shù)據(jù)和非數(shù)值型數(shù)據(jù)，主要的噪聲機制分別為Laplace擾動機制和指數(shù)擾動機制，具體說明如下。

定義2Laplace 擾動。對于數(shù)據(jù)集D上的任意一個函數(shù)f：D→Rd，若函數(shù)f的輸出結(jié)果滿足式(2)，則f滿足ε-差分隱私。

其中，Δf為查詢函數(shù)的敏感度。Laplace 分布的位置參數(shù)為0，尺度參數(shù)為。

定義3指數(shù)擾動。給定一個可用函數(shù)f:(Dn×R)→Ω，r是可用函數(shù)輸出域range 中的一個實體對象，若函數(shù)f的輸出結(jié)果滿足式(3)，則f滿足ε-差分隱私。其中，S(f)為可用函數(shù)的全局敏感度，對象被選中的概率正比于可用函數(shù)f的打分。指數(shù)機制以正比于的概率返回實體對象。

若dx(x,x')=d2(x,x')，則代表2 個地理位置間的歐氏距離，此時該模型可用于保護LBS 位置查詢時的隱私泄露問題，本文稱其為ε-地理不可區(qū)分性，該定義等價于歐氏距離空間中的ε-差分隱私。

定義4ε-地理不可區(qū)分性[3]。對于任意滿足d2(x,x')≤r的2 個位置x和x'，若在查詢機制M下輸出的位置集o滿足式(4)，則稱M滿足ε-地理不可區(qū)分性。

其中，M(x)(o)是在查詢機制M中，位置x輸出位置o的概率。ε為一個距離單位的隱私預算，則任意半徑r的隱私預算為ε=εr，此時用戶的真實位置被保護在半徑為r的圓中。可以看出，2 個位置的地理距離越近，生成相同查詢位置o的概率越相似，地理位置越不可區(qū)分，隱私保護程度越高。進一步，利用其極坐標下的Laplace 機制產(chǎn)生滿足ε-地理不可區(qū)分性的噪聲位置（假的查詢位置），實現(xiàn)該模型的隱私保護。

此外，ε-差分隱私具有序列組合特性，即如果每個發(fā)布機制Mi滿足εi-差分隱私，則Mi的一個序列應用則滿足∑εi-差分隱私。此性質(zhì)指出，當查詢機制應用n次LBS 查詢服務時，每個噪聲位置的隱私預算為ε，則軌跡的隱私預算為nε。

定義5w連續(xù)序列ε-差分隱私。假設用戶的軌跡為Z={z1,z2,z3,...,zn}，其中zi為在查詢機制Mi下輸出的假查詢位置，并且Mi滿足εi-差分隱私。對于其中任意一個w個時間戳的連續(xù)位置序列子集{zi-w+1,…,zi}，若其隱私預算之和滿足式(5)，則用戶的軌跡隱私滿足w連續(xù)序列ε-差分隱私。

定義6δ-位置集[11]。假設用戶在t時刻有n個可能的位置，令表示用戶在各個位置的概率值，則δ-位置集為累積概率值不少于1-δ的最小位置集，即

直觀而言，δ-位置集是用于刪除可能位置集中概率比較低的位置點。

3.2 相似地圖

LBS 中，用戶通過向服務提供商提供自身位置獲取相關服務。但是由于地理位置的空間特征，不同位置的查詢結(jié)果可能是相同或相似的。因此定義服務相似度，具體如下。

定義7位置的服務相似度[15]。假設有2 個位置g和h，則它們的服務相似度定義為

其中，(xi,yi)是位置i的坐標，Rm(x,y)是在坐標(x,y)處查詢的top-m個興趣點的排序結(jié)果集，是集合元素的數(shù)量。

通過服務相似度對地圖進行服務相似性分區(qū)[15]，將查詢結(jié)果相同的位置集（服務相似度為1）合并成一個區(qū)域，即同一個分區(qū)內(nèi)的任一位置的查詢結(jié)果是相同的。因此相似地圖定義如下。

定義8相似地圖。給定一個服務區(qū)域S，若S=Si∪S，Si∩Sj=?，以及對其中任意的p1,p2∈Si,sim(p1,p2)=1，則稱S為相似地圖。顯而易見，在同一相似區(qū)域Si的任意位置的查詢結(jié)果是相同的。

選取某一地區(qū)的870 km2區(qū)域內(nèi)分布的麥當勞餐廳位置，并將該區(qū)域劃分為一個300×290 的網(wǎng)格，每網(wǎng)格的面積為100 m×100 m，并取top-3結(jié)果集，生成相似區(qū)域（用同一灰度值進行標識），如圖1 所示。

定義9位置正確率。查詢機制M的位置正確率為其中，R(p)表示在真實位置p處查詢的興趣點的結(jié)果集，M(p)表示真實位置p在查詢機制M下輸出的假位置查詢點，S[.]表示集合數(shù)量。

圖1 相似區(qū)域

4 系統(tǒng)方案

根據(jù)觀察發(fā)現(xiàn)，預測位置往往隨機分布在真實位置的周邊，攻擊者無法根據(jù)預測位置推測出用戶的真實位置，因此可以將預測機制視為一種隨機擾動。由于預測機制的隱私開銷非常小，甚至趨近于0，因此利用預測機制替代差分擾動能夠有效降低連續(xù)查詢的隱私開銷。其次，隱私具有差異化，為不同的語義位置分配不同的隱私預算，能夠有效提高隱私預算利用率。例如，可以為醫(yī)院/家庭等敏感位置分配較小的預算，而公園/商場等公共區(qū)域分配較大預算，從而實現(xiàn)隱私預算的合理分配，節(jié)省隱私開銷。再者，由于查詢位置具有時空關聯(lián)性，單個位置滿足ε-差分隱私，并不能確保軌跡隱私安全。因此基于上述觀察，本文提出一種基于預測和滑動窗口的軌跡差分隱私保護機制，主要包含以下策略。

1)隱私預算量身定制

該機制允許用戶自定義位置敏感度，并依此量身定制隱私預算，進一步提高軌跡隱私預算的利用率。

2)預測擾動

利用馬爾可夫鏈和指數(shù)擾動機制獲得滿足高可用性、差分安全和時空相關性約束的預測位置，并引入服務相似地圖校驗預測位置的可用性。該策略利用預測的假位置替代差分擾動，從而有效降低預算開銷，并進一步提高服務質(zhì)量。

3)基于w滑動窗口的隱私預算分配機制

采用w滑動窗口機制分配連續(xù)查詢中各位置點的隱私預算，確保軌跡中的任意w個時間戳（位置點）的隱私消耗累計不超過ε，即確保軌跡滿足ε-差分隱私。

具體查詢過程如算法1 所示。

算法1基于預測和滑動窗口的軌跡差分隱私保護機制

輸入Q(t-1),L(t-1),p,mapsen,U,θ,w,α,δ,mapsim,ε,C,E,N

輸出z

算法1 中，θ為用戶設置的敏感度閾值；p為用戶的真實位置;p.pl 為真實位置的敏感度；lookup為查詢函數(shù)，即通過查找敏感度地圖mapsen，獲取p.pl；L(t-1)為用戶在前一時刻的可能位置集；Q(t-1)為用戶在前一時刻的可能位置概率；w為滑動窗口；δ為δ-位置集的參數(shù)；α為用戶設置的服務相似度閾值；mapsim為相似地圖；ε為用戶設置的軌跡隱私預算之和；C、E和N分別為隱私預算分配機制中用戶設置的參數(shù)；U為狀態(tài)轉(zhuǎn)移概率矩陣；prediction(U,εe,δ,Q(t-1),L(t-1))為基于馬爾可夫鏈和指數(shù)擾動機制的預測機制，詳見算法2；test(l,α,mapsim,p,εθ)為基于服務相似度的檢測函數(shù)，詳見算法3；N(εN，p)為當隱私預算為εN時，位置p在地理不可區(qū)分性的擾動機制中輸出噪聲位置，即z。在算法1 中，首先根據(jù)用戶的真實位置獲取位置的敏感度。如果位置的敏感度小于用戶設置的閾值θ，則檢測成功，直接利用用戶的真實位置獲取服務（算法1 的①～③）；否則通過隱私預算分配機制，分別獲取預測機制和檢測函數(shù)的隱私預算εe和εθ（算法1 的⑤～⑥）。算法1 的⑦～⑨是利用該預測機制獲取預測位置點l，并檢測預測位置的可用性。如果檢測成功，直接采用預測的位置作為查詢點；否則，通過隱私預算分配機制，獲取地理不可區(qū)分性的隱私預算εN，并進行隨機擾動，即N(εN,p)，將噪聲位置作為當前的查詢位置（算法1 的⑩～?）。

4.1 敏感度處理

文獻[13]認為只有與敏感位置直接相連的語義位置才具有敏感度。然而，從隨機擾動的分布角度看，那些靠近敏感位置的語義位置，即使與敏感位置不直接相連，仍然存在暴露敏感位置的風險，因此也應分配一定的敏感度。因此，本文考慮了位置點間的整體連通性，根據(jù)距離和出入度將敏感位置的隱私級別分別輻射給附近節(jié)點。首先，獲取敏感位置附近具有隱私級別的位置節(jié)點集，即連接集neighborSet。然后，將地圖轉(zhuǎn)化為無向圖，根據(jù)距離和出入度，則任意位置g與敏感位置a的等價距離為g.eDis=ED(c-1)，其中，ED為g與a的歐氏距離，c為兩位置節(jié)點間最短路徑所經(jīng)過的節(jié)點數(shù)-1。進一步地，neighborSet={g|g.eDis＜b}，其中b為用戶設置的閾值。最后，為敏感位置a的連接集neighborSet 中的任意位置g分配隱私敏感度，如式(9)所示。

其中，g.pl 表示節(jié)點g分配的隱私敏感度。

為了計算方便，本文將地圖網(wǎng)格化。然后，利用上述過程計算地圖中各區(qū)域的敏感度，生成敏感度地圖mapsen。mapsen存儲于手機端，用戶可以在離線階段獲取位置的敏感度。

4.2 預測機制

預測機制主要由基于馬爾可夫鏈和指數(shù)擾動機制的預測機制和基于服務相似性的檢測機制兩部分構(gòu)成。

針對預測機制的部分，本文利用馬爾可夫鏈刻畫用戶真實位置間的時序相關性，其中，狀態(tài)轉(zhuǎn)移概率矩陣U表示真實位置在區(qū)域間的轉(zhuǎn)移可能性，如狀態(tài)轉(zhuǎn)移概率矩陣U中元素uij表示用戶從第i個區(qū)域移動到第j個區(qū)域的概率。這里假設狀態(tài)轉(zhuǎn)移概率矩陣U可事先在歷史記錄上計算得到。假設用戶在t-1 時刻產(chǎn)生的可能位置集為，其概率值為，通過狀態(tài)轉(zhuǎn)移概率矩陣計算出t時刻的可能位置為，其概率值為，其中Q(t)=Q(t-1)U。由于通過轉(zhuǎn)移矩陣計算t時刻位置集中的一些元素的概率較低，因此本文用δ-位置集（見定義6）過濾概率較低的元素，得到候選集ΔXt。然而對于選擇ΔXt中的元素作為預測位置點，需要選擇概率較高的元素。為了隱私性，本文選取指數(shù)機制對其選擇，即E(εe):ΔXt→l，其中，εe為指數(shù)選擇機制的隱私預算；打分函數(shù)為，m為δ-位置集中的元素個數(shù)。具體算法如算法2 所示。該機制對輸出結(jié)果添加了噪音，但是概率高的元素仍以較大的概率輸出，從而使輸出結(jié)果更加隱私并更合理。

算法2預測機制

輸入L(t-1),Q(t-1),U,δ,mapsim,p,ε,E,w

輸出l

通過隱私預算分配機制，本文分別獲取指數(shù)機制的隱私預算εe（算法2 的③）。E(εe,ΔXt)為隱私預算為εe時，通過指數(shù)擾動機制在ΔXt中輸出預測位置l。在算法2 中，本文首先利用馬爾可夫鏈計算當前時刻的可能位置集，再利用δ-位置集ΔXt過濾其中概率較低的位置點，最后采用指數(shù)機制選出當前預測位置。

針對檢測的部分，為了評估預測位置的服務質(zhì)量，本文提出一種基于服務相似性的檢測函數(shù)。其中基于服務相似性的檢測函數(shù)θ(εθ,α,l)為

其中，l是預測位置；sim(p,l)是位置p與l的服務相似度；B={0,1}是布爾函數(shù)，輸出“0”表示預測成功，“1”表示預測失敗；Lap(εθ)表示隱私預算為εθ時Laplace 擾動值。由于檢測函數(shù)必然會泄露用戶部分的位置隱私，為了保證安全，本文在檢測函數(shù)中也引入Laplace 的擾動機制。雖然檢測函數(shù)用掉一部分隱私預算，但是其相對滿足ε-地理不可區(qū)分性的擾動隱私預算值較小，因此節(jié)省了隱私預算，同時提高了服務質(zhì)量。服務器預先生成相似地圖mapsim，供客戶端下載，從而在離線階段通過相似地圖檢測2 個位置的服務相似度。對于該檢測機制，其具體過程如算法3 所示。

算法3檢測機制

輸入α,l,mapsim,p,C,ε,w

輸出O

算法3 中，l為預測的位置。算法3 利用算法2預測輸出的預測位置l，與真實位置進行服務相似度的檢測。如果滿足可用性需求記為0，否則記為1，并相應輸出。

4.3w序列滿足ε-差分隱私的隱私預算分配機制

從查詢機制可知，每個位置在指數(shù)擾動階段、檢測函數(shù)檢測階段和地理不可區(qū)分性的擾動階段分別需要分配的隱私預算為εe、εθ和εN。如果一個時間戳的假位置預測成功，利用預測位置作為查詢位置。生成查詢位置的過程共經(jīng)歷了指數(shù)擾動機制和檢測函數(shù)2 個階段，因此花費的隱私預算為εe+εθ。如果檢測失敗，則利用地理不可區(qū)分性的擾動產(chǎn)生查詢點，其經(jīng)歷了3 個階段，因此花費的隱私預算為εe、εθ和εN之和，則有

其中，εi為連續(xù)的LBS 查詢中，第i個查詢位置分配的總隱私預算。若P(B)=0，預測成功，反之預測失敗。從式(11)也可以看出，如果預測失敗，反而花費更多的隱私預算，因此要提高預測成功率，節(jié)省隱私預算。

從差分隱私的序列組合特性可以看出，在連續(xù)的LBS 查詢中，無法保證軌跡的隱私。因此本文考慮將軌跡片段化，引入w滑動窗口機制，使其軌跡滿足w連續(xù)序列ε-差分隱私。首先，w滑動窗口是指用戶連續(xù)查詢的時間戳長度為w的位置序列，其形式如圖2 所示。軌跡中任意一個時間戳為一個窗口，每個窗口對應的隱私預算為εi。其次，設計隱私預算分配機制為εe、εθ和εN分配相應的隱私預算。

圖2 w滑動窗口示意

為了使軌跡滿足ε-差分隱私，引入?yún)?shù)E、C和N調(diào)節(jié)隱私預算，且E+N+C=1，具體預算分配機制如下。

對于指數(shù)擾動機制，每個位置分配到的隱私預算εe為

指數(shù)機制中的打分函數(shù)為f=Q(t)={q1(t),...,qm(t)}，由于序列組合特性，因此δ-位置集中的每個位置分配的隱私預算為。

對于檢測函數(shù)檢測階段，每個位置分配到的隱私預算εθ為

由于隱私具有主觀性，在每一點上進行同等擾動并不合理。不僅用戶對不同語義位置的敏感度不同，而且不同用戶對同一個語義的敏感性也是存在差異。因此，本文引入敏感度量身定制策略，提高隱私預算的利用率。對于敏感度越高的位置，分配較小的隱私預算，即加入越大的擾動噪音，從而獲得更高的隱私保護程度。首先，對于初始值（r,θ）分配相應的隱私預算。其中（r,θ）指半徑為r，敏感度為θ。其次，考慮位置敏感度，敏感度越高，對于噪音擾動階段分配的隱私預算越低，保護半徑越小。因此，對于任意敏感度g.pl，其半徑的選擇為，從而對于滿足地理不可區(qū)分性的擾動，每個位置分配到的隱私預算εN為

其中，E+C≤N且g.pl∈[θ,1]。為了節(jié)省隱私預算，在預測階段的預算值要小于擾動階段的預算值，因此E+C≤N。

5 隱私分析

本節(jié)證明本文查詢機制的發(fā)布軌跡能夠滿足w連續(xù)序列ε-差分隱私。

根據(jù)定義5，本文首先可以證明E(εe)、θ(εθ,α,l)和N(εN)分別滿足εe-差分隱私、εθ-差分隱私和εN-差分隱私。從而，可以進一步證明本文查詢機制Mi滿足εi-差分隱私，其中εi=εβ+εθ+εN。證明過程見附錄。

基于上述分析，本文可以證明軌跡滿足w連續(xù)序列ε-差分隱私，即本文機制的軌跡中任意連續(xù)w個位置的隱私預算之和為ε。形式化表達如定理1所示。

定理1任意一個w個時間戳的連續(xù)發(fā)布位置序列子集{zi-w+1,…,zi}，軌跡隱私保護滿足w連續(xù)序列ε-差分隱私。即

證明首先E(εe)、θ(εθ,α,l)和N(εN)分別滿足εe-差分隱私，εθ-差分隱私和εN-差分隱私，由于本文機制由這3 種機制組合而成，因此查詢機制Mi滿足εi-差分隱私，其中εi=εβ+εθ+εN。因此對于任意w個時間戳的隱私預算之和為

證畢。

6 實驗分析與評估

本文分析了模型參數(shù)在2 種真實數(shù)據(jù)集中對于可用性的影響。同時，將本文方案與DPLRM[13]機制和PM[14]機制進行對比分析，從而驗證本文方案的有效性。

6.1 實驗數(shù)據(jù)集與設置

實驗采用Geolife[16]和Gowalla[17]這2 個數(shù)據(jù)集，其中，Geolife 采集了182 個用戶2007 年4 月至2012 年8 月在北京活動的真實數(shù)據(jù)，共包含17 621 條軌跡。數(shù)據(jù)集包含用戶編號、時間戳、經(jīng)度、緯度、海拔等信息。本文從該數(shù)據(jù)集中抽取50 條北京某一地區(qū)的軌跡進行采樣，采樣方法如下。每隔1 min 采取一個樣本點作為用戶的查詢點，如果2 個連續(xù)位置的間隔大于1 min，則該位置被隨機取樣。50 條軌跡采樣后大約有500 個位置。為方便計算，本文將地圖劃分為300 m×300 m 的網(wǎng)格，并將用戶真實位置規(guī)格化到網(wǎng)格中心。Gowalla 采集了15 116 個用戶2009 年2 月至2010 年10 月在移動社交網(wǎng)站上（美國加州范圍內(nèi)）的簽到數(shù)據(jù)。同Geolife 一樣，本文抽取加州范圍內(nèi)的用戶編號、時間戳、經(jīng)度、緯度作為新的數(shù)據(jù)集，并將其地圖劃分為0.89 m ×0.89 m 的網(wǎng)格。

6.2 可用性評估

本文發(fā)現(xiàn)預測成功率會直接影響LBS 的可用性與隱私風險，因此提高預測成功率對基于預測機制的隱私保護方案至關重要。可用性閾值α與預測成功率的函數(shù)關系如圖3 所示，并引入PM 方案進行對比。從圖3 可看出，兩者的成功率都隨著α的升高而逐漸下降，但本文的預測成功率始終明顯高于PM 方案。這是由于在基于服務相似性的檢測函數(shù)中，α越大，滿足可用性要求的位置越少，因此預測成功率必然下降。此外，本文方案采用了馬爾可夫鏈的預測機制，能夠有效提高預測成功率。

本文利用定義9 的軌跡中位置正確率的平均值和真實位置與其發(fā)布位置之間的均方根誤差（RMSE,root mean square error）這2 種測量矩陣去測量的軌跡的可用性。其中，用戶真實軌跡位置和查詢位置軌跡分別為P={p1,p2,…,pn}和Z={z1,z2,…,zn}，則

首先，本文分別分析敏感度閾值θ在Geolife和Gowalla 數(shù)據(jù)集中對RMSE 和位置正確率的影響，結(jié)果如圖4 和圖5 所示。在該實驗中，w=3，α=0.5，ε=1.8，b=500，。從圖4中可以看出，本文方案的可用性隨著θ的升高而提高。θ越高，一方面，在擾動階段每個位置分配到的隱私預算提高，可用性也提高；另一方面，更多位置的敏感度小于θ，從而不需要擾動，因此可用性更好。但是當θ取值為0.16 時，RMSE 為0。這是因為在本文的敏感度劃分方法中，當b設置為500時，地圖內(nèi)區(qū)域的敏感最高為0.15。因此當θ取值為0.16 時，地圖中所有位置都是不敏感位置，直接發(fā)布，因此軌跡的平均RMSE 為0。此外，Geolife數(shù)據(jù)集中的可用性好于Gowalla 數(shù)據(jù)集，因為Gowalla 數(shù)據(jù)集劃分區(qū)域的網(wǎng)格較大，2 個位置間的距離較遠，所以可用性較差。最后，本文的可用性高于PM 方案和DPLRM 方案。首先，本文的預測成功率高于PM 方案。其次，因為PM 方案不考慮隱私的個性化設置，隱私預算的利用率低，擾動不確定性高，可用性差。DPLRM 方案雖然考慮隱私與可用性的平衡，但是在隱私中既考慮發(fā)布位置對當前位置影響，又考慮了對之前位置影響，限制因素較多，并且本文方案中引入了可用性檢測，故可用性高。

圖3 可用性閾值α與預測成功率的函數(shù)關系

從圖5 中可以看出，位置正確率隨著θ的增大而提高。因為從圖4 中得到，θ越大，RMSE 越小，因此位置正確率越高。當RMSE=0 時，正確率最高，接近于1。此外，Geolife 數(shù)據(jù)集中的可用性也高于Gowalla 數(shù)據(jù)集，同時本文的位置正確率也高于DPLRM 方案和PM 方案。

圖4 敏感性閾值θ對RMSE 的影響

圖5 敏感性閾值θ對位置正確率的影響

本文還應該探究在給定軌跡隱私預算，滑動窗口長度與可用性的關系和給定滑動窗口軌跡的隱私預算與可用性的關系。但是二者之間的本質(zhì)問題是相同的，都是探求隱私預算與可用性的關系，因此，本文分析滑動窗口長度對可用性的影響，結(jié)果如圖6 和圖7 所示。在這一系列實驗中，本文假設ε=1.8，b=500，θ=0.01，α=0.5。從圖6 中可以看出，RMSE 隨著滑動窗口w的數(shù)量增大而提高。w越大，每個位置分配的隱私預算越少，則預測成功率越低，并且滿足地理不可區(qū)分性的擾動越大，從而降低了隱私可用性。Geolife 數(shù)據(jù)集中的可用性好于Gowalla 數(shù)據(jù)集，與圖4 的原因相同。本文的可用性高于DPLRM 方案和PM 方案。DPLRM 方案對于發(fā)布位置的約束條件較多，從而導致較遠的位置滿足約束條件，并且本文方案中引入了可用性檢測，可用性高。PM 方案利用前一次的查詢點作為檢測位置點，然而本文中進一步改進利用基于服務相似性檢測以及馬爾可夫模型的預測機制，預測成功率更高，因此可用性最好。

圖6 w滑動窗口對RMSE 的影響

從圖7 中可以看出，位置正確率隨著滑動窗口w數(shù)量的上升而降低，同時Geolife 數(shù)據(jù)集中的可用性也高于Gowalla 數(shù)據(jù)集，此外，本文方案的位置正確率也高于DPLRM 方案和PM 方案。

6.3 系統(tǒng)運行時間評估

圖7 w滑動窗口對位置正確率的影響

圖8 θ對方案運行時間t的影響

本節(jié)評估了本文算法的時間開銷，并與DPLRM 方案比較，如圖8 所示。為了更加方便比較，本文的實驗設置與DPLRM 算法相同，選取數(shù)據(jù)集為Geolife 數(shù)據(jù)集，將北京地圖劃分為大小為0.34 km×0.34 km 的網(wǎng)格，初始敏感位置個數(shù)設為10，并且敏感度計算方法也與DPLRM 相同。從圖8可以看出，本文方案的運行時間遠遠小于DPLRM方案。DPLRM 方案中最耗時的部分在于計算其后驗概率，其復雜度為O(wN3)，其中N為用戶t時刻可能的真實位置區(qū)域個數(shù)和滿足限制條件的發(fā)布區(qū)域個數(shù)?？赡艿恼鎸嵨恢脜^(qū)域個數(shù)也是由馬爾可夫鏈計算的，如果查詢時間較長，則可能的真實位置區(qū)域個數(shù)非常大，在實際應用中需要多個服務器并行計算。而在本文方案中，指數(shù)選擇與地理不可區(qū)分性的計算時間與可能區(qū)域的個數(shù)呈線性增長。此外，利用轉(zhuǎn)移矩陣計算可能位置的概率，這部分計算DPLRM算法也已經(jīng)包括，并且開銷也很低。

7 結(jié)束語

為解決軌跡差分隱私保護中存在的隱私預算與服務質(zhì)量等問題，本文提出一種基于預測和滑動窗口的軌跡差分隱私保護機制。首先，允許用戶自定義位置敏感度，并依據(jù)敏感度量身定制隱私預算，提高預算的利用率。其次，利用馬爾可夫鏈和指數(shù)擾動機制獲得滿足高可用性、差分安全和時空相關性約束等3 個目標的預測位置，并引入服務相似地圖校驗預測位置的可用性。該策略可以有效降低預算開銷，并進一步提高服務質(zhì)量。最后，采用滑動窗口w機制分配連續(xù)查詢中各位置點的隱私預算，確保軌跡中的任意w個時間戳（位置點）的隱私消耗累計不超過ε，從而實現(xiàn)連續(xù)查詢的軌跡滿足ε-差分隱私。今后將考慮研究如何對本文算法進行繼續(xù)優(yōu)化，以提高查詢的可用性。

附錄 查詢機制Mi 滿足ε i-差分隱私證明

對于指數(shù)擾動機制、檢測函數(shù)檢測與噪音擾動機制分別滿足ε-差分隱私，即

則查詢機制Mi滿足εi-差分隱私，其中εi=εβ+εθ+εN。

證明

在預測階段選取的機制為指數(shù)機制，因此E(εe)滿足εe-差分隱私，其中dx(p,p')=1。

在檢測函數(shù)檢測階段，有

因此，?εθ,α,l，檢測函數(shù)檢測θ(εθ,α,l)滿足εθ-差分隱私，其中dx(p,p')=1。

在位置擾動階段選取的機制為基于地理不可區(qū)分性的擾動，因此N(εN)滿足εN-差分隱私。

根據(jù)序列組合特性，εi=εe+εθ+εN。因此，查詢機制Mi滿足εi-差分隱私。

證畢。