基于差分隱私的連續(xù)位置隱私保護(hù)機(jī)制

李洪濤，任曉宇，王潔，馬建峰

（1.山西師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，山西 臨汾 041099；2.西安電子科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，陜西 西安 710071）

1 引言

移動(dòng)智能設(shè)備和定位技術(shù)的快速發(fā)展給移動(dòng)用戶帶來了各種類型的基于位置的應(yīng)用，為人們的生活帶來諸多便捷。然而，由于移動(dòng)用戶在享受便捷服務(wù)的時(shí)候需要向基于位置的服務(wù)（LBS，location based service）提供他們的位置信息，使大量用戶位置信息被不可信的第三方獲取，可能使用戶遭受嚴(yán)重的位置隱私泄露問題，危害用戶的隱私安全。針對位置隱私保護(hù)技術(shù)，相關(guān)學(xué)者進(jìn)行了大量研究。目前，多數(shù)位置隱私保護(hù)技術(shù)以k-匿名或l-多樣性為基礎(chǔ)，此類技術(shù)是將用戶的真實(shí)位置泛化成一個(gè)區(qū)域，實(shí)現(xiàn)位置信息的隱私保護(hù)。其中，文獻(xiàn)[1]基于用戶的單一敏感屬性設(shè)計(jì)了個(gè)性化k-匿名模型與KAUP（k-anonymity algorithm for personalized quasi-identifier attributes），提高了數(shù)據(jù)發(fā)布過程中的隱私保護(hù)程度。文獻(xiàn)[2]提出一種基于l-多樣性大數(shù)據(jù)隱私保護(hù)方法，采用NER（named entity recognition）方法將數(shù)據(jù)表示為結(jié)構(gòu)化形式，進(jìn)而對數(shù)據(jù)進(jìn)行匿名化，實(shí)現(xiàn)對隱私數(shù)據(jù)的保護(hù)。抑制和擾亂技術(shù)也是近些年使用較多的保護(hù)方法。抑制技術(shù)的主要思想是不發(fā)布用戶的敏感位置信息。文獻(xiàn)[3]提出了一種基于信息熵的軌跡抑制隱私保護(hù)算法，通過函數(shù)計(jì)算抑制敏感位置點(diǎn)的最低代價(jià)，選擇合理的抑制方式對原始數(shù)據(jù)集中包含敏感點(diǎn)的序列進(jìn)行抑制。擾亂技術(shù)是將真實(shí)位置通過一定的變換生成假位置，達(dá)到保護(hù)真實(shí)位置的目的。文獻(xiàn)[4]基于假位置隱私方法，提出了一種最大最小假位置選擇（MMDS,maximum and minimum dummy selection）方案，使攻擊者很難結(jié)合邊信息過濾一些假位置，對位置信息進(jìn)行隱私保護(hù)。以上幾種隱私保護(hù)技術(shù)都有一定的局限性和缺點(diǎn)，攻擊者可以通過長期的觀察、挖掘和分析等方法獲取用戶的位置隱私信息[5-7]，因此這些技術(shù)無法抵抗相關(guān)攻擊背景知識(shí)攻擊。

Dwork 等[8]于2006 年提出了差分隱私保護(hù)模型，其因良好的隱私保護(hù)強(qiáng)度成為一種主流的技術(shù)，通過對原始查詢結(jié)果添加隨機(jī)噪聲，使在數(shù)據(jù)集中添加或刪除某一條數(shù)據(jù)對查詢結(jié)果不產(chǎn)生影響，從而讓攻擊者很難通過多次查詢反推某條真實(shí)數(shù)據(jù)，實(shí)現(xiàn)隱私保護(hù)。Chen 等[9]將差分隱私保護(hù)機(jī)制應(yīng)用于位置數(shù)據(jù)保護(hù)，通過對位置數(shù)據(jù)加入Laplace 噪聲，實(shí)現(xiàn)對位置數(shù)據(jù)的隱私保護(hù)?；魨樀萚10]對自由空間和路網(wǎng)空間分別構(gòu)造了噪聲四分樹和噪聲R-樹，通過添加Laplace 噪聲保護(hù)位置數(shù)據(jù)，但沒有考慮2 個(gè)連續(xù)時(shí)刻位置數(shù)據(jù)間的相互影響。吳云乘等[11]采用差分隱私位置保護(hù)模型，把已知生成位置時(shí)真實(shí)位置的后驗(yàn)概率與真實(shí)位置概率的比值作為滿足差分隱私的條件提出了DPLRM（differential privacy location release mechanism）。Xiao 等[12]將地圖轉(zhuǎn)換為帶權(quán)無向圖，給位置區(qū)域分配隱私級(jí)別，在文獻(xiàn)[11]的基礎(chǔ)上，用馬爾可夫鏈表示2 個(gè)連續(xù)位置的關(guān)系，提出基于差分隱私的位置保護(hù)方案。然而，現(xiàn)有的差分隱私解決方法多數(shù)沒有考慮位置間的關(guān)聯(lián)，即使對用戶所有位置進(jìn)行保護(hù)，攻擊者也會(huì)根據(jù)地理拓?fù)洹r(shí)序關(guān)系等方法獲取用戶隱私信息。

針對以上問題，本文提出了一種差分隱私位置保護(hù)機(jī)制（DPLPM,differential privacy location protect mechanism），該機(jī)制能有效保護(hù)位置隱私和最大化數(shù)據(jù)可用性。本文主要貢獻(xiàn)如下。

1) 根據(jù)路網(wǎng)的拓?fù)潢P(guān)系，對敏感位置周圍路段進(jìn)行隱私級(jí)別劃分，提出道路隱私級(jí)別（RPL,road privacy level）劃分算法（本文簡稱為RPL 算法）。

2) 提出DPLPM，構(gòu)建位置樹結(jié)構(gòu)并給位置信息分配隱私預(yù)算，為敏感路段添加符合差分隱私機(jī)制的Laplace 噪聲，實(shí)現(xiàn)位置信息的隱私保護(hù)。

3) 理論分析和實(shí)驗(yàn)結(jié)果證明，所提機(jī)制能夠較好地保護(hù)位置隱私和最大化數(shù)據(jù)可用性。

2 相關(guān)定義及其概念

2.1 差分隱私的相關(guān)定義

定義1鄰近數(shù)據(jù)集。設(shè)數(shù)據(jù)集有相同的屬性結(jié)構(gòu)，兩者僅相差一條記錄，即，則稱D和D' 為鄰近數(shù)據(jù)集。

定義2差分隱私。給定鄰近數(shù)據(jù)集D和D'，并已知某查詢算法A，若算法A在數(shù)據(jù)集D和D'的任意輸出結(jié)果O滿足不等式(1)，則稱算法A滿足ε-差分隱私。

隱私預(yù)算ε用來控制算法A在2 個(gè)鄰近數(shù)據(jù)集輸出相同結(jié)果的概率比例，它表明隱私保護(hù)的程度，即ε越小，隱私保護(hù)程度越高，當(dāng)ε=0 時(shí)，隱私保護(hù)程度達(dá)到最高。

定義3全局敏感度。設(shè)函數(shù)f:D→Rd，輸入一個(gè)數(shù)據(jù)集，輸出d維實(shí)數(shù)向量，對于任意臨近數(shù)據(jù)集D和D'，稱GFf為函數(shù)f的全局敏感度。

2.2 Laplace 機(jī)制

Laplace 機(jī)制通過向確切的查詢結(jié)果中加入服從Laplace 分布的隨機(jī)噪聲來實(shí)現(xiàn)ε-差分隱私，主要面向數(shù)值型查詢結(jié)果。記初始位置下尺度參數(shù)為b的Laplace 分布為Lap(b)，其概率密度函數(shù)為

定義4Laplace 機(jī)制。給定數(shù)據(jù)集D，設(shè)有函數(shù)f:D→ed，其敏感度為Δf，那么隨機(jī)算法A(D)=f(D)=Y提供ε差分隱私，其中Y～Lap(Δf/ε)為隨機(jī)噪聲，服從尺度參數(shù)為 Δf/ε的Laplace 分布。

2.3 數(shù)據(jù)可用性

本文采用文獻(xiàn)[12]的定義來測量本文數(shù)據(jù)可用性。假設(shè)t時(shí)刻發(fā)布位置是Ot，其真實(shí)位置是Zt，本文采用Ot和Zt之間的歐氏距離作為誤差評價(jià)，即

特別地，對于長度為|W|的軌跡，本文同樣以距離誤差為基礎(chǔ)衡量數(shù)據(jù)可用性，如式(5)所示。RMSE等于位置上處于敏感區(qū)域的真實(shí)位置與其發(fā)布位置之間的均方根誤差和。RMSE 越大，表示數(shù)據(jù)可用性越差。

其中，∏Zt為指示函數(shù)，當(dāng)Zt為敏感位置時(shí)，指示函數(shù)∏Zt的值等于1，否則該值等于0。

3 系統(tǒng)結(jié)構(gòu)和威脅模型

3.1 系統(tǒng)結(jié)構(gòu)

本文的系統(tǒng)結(jié)構(gòu)如圖1 所示，主要包括三部分：客戶端、隱私保護(hù)處理器和位置服務(wù)處理器。客戶端主要通過GPS 定位模塊獲取用戶位置，并將位置存儲(chǔ)至數(shù)據(jù)庫中；隱私保護(hù)處理器分為數(shù)據(jù)劃分模塊、連續(xù)位置數(shù)據(jù)保護(hù)模塊和數(shù)據(jù)庫，數(shù)據(jù)劃分模塊將連續(xù)位置劃分隱私級(jí)別，并將經(jīng)過隱私級(jí)別劃分的數(shù)據(jù)存儲(chǔ)至數(shù)據(jù)庫，連續(xù)位置數(shù)據(jù)保護(hù)模塊對數(shù)據(jù)庫中的位置提供差分隱私保護(hù)；位置服務(wù)處理器根據(jù)連續(xù)位置保護(hù)模塊提出的查詢請求，獲得位置信息查詢反饋，并將查詢結(jié)果存儲(chǔ)至數(shù)據(jù)庫中。

圖1 系統(tǒng)結(jié)構(gòu)

針對用戶位置隱私泄露問題，本文提出一種基于差分隱私的連續(xù)位置保護(hù)機(jī)制。在客戶端，GPS定位模塊獲取用戶位置數(shù)據(jù)，并將其上傳至數(shù)據(jù)庫，數(shù)據(jù)劃分模塊用RPL 算法對位置數(shù)據(jù)劃分隱私級(jí)別；假設(shè)隱私保護(hù)處理器是可信任的第三方，連續(xù)位置數(shù)據(jù)保護(hù)模塊從數(shù)據(jù)庫中獲取經(jīng)過隱私級(jí)別劃分的數(shù)據(jù)，通過DPLPM 添加基于差分隱私的Laplace 噪聲，并生成位置集合；位置服務(wù)處理器向連續(xù)位置數(shù)據(jù)保護(hù)模塊提出查詢請求，連續(xù)位置數(shù)據(jù)保護(hù)模塊將查詢結(jié)果反饋至位置服務(wù)提供商；位置服務(wù)提供商在提供服務(wù)之后，將數(shù)據(jù)存儲(chǔ)至數(shù)據(jù)庫。

3.2 威脅模型

本文假設(shè)攻擊者會(huì)不定時(shí)攻擊用戶的位置數(shù)據(jù)。很多位置服務(wù)提供商都有不同程度的安全保障，但當(dāng)其服務(wù)器或數(shù)據(jù)庫受到攻擊時(shí)，用戶的位置數(shù)據(jù)等隱私信息就可能被泄露?；谶@個(gè)假設(shè)，本文提出的隱私威脅模型如圖2 所示。智能手機(jī)、便攜電腦和近場通信（NFC,near field communication）等便攜設(shè)備獲取用戶位置數(shù)據(jù)，并將連續(xù)位置數(shù)據(jù)傳送至服務(wù)器端進(jìn)行處理，進(jìn)而從位置服務(wù)提供商處獲取服務(wù)。攻擊者可以通過攻擊服務(wù)器端或直接攻擊位置服務(wù)提供商，獲取用戶隱私信息。

圖2 隱私威脅模型

4 本文機(jī)制描述

本文常用符號(hào)如表1 所示。

表1 常用符號(hào)

4.1 RPL 算法

在數(shù)據(jù)劃分模塊，改進(jìn)道路隱私級(jí)別劃分算法，結(jié)合岔路口位置提出RPL 算法。圖3(a)為真實(shí)區(qū)域的路網(wǎng)示意，○表示路口i，表示真實(shí)位置，表示用戶當(dāng)前所處位置，2 個(gè)路口間的虛線表示路口可直達(dá)。假設(shè)用戶會(huì)選擇最短路徑到達(dá)目的位置。圖3(b)統(tǒng)計(jì)了到達(dá)不同的目的位置最少需要經(jīng)過路口的個(gè)數(shù)。其中，用戶自定義初始敏感位置集合為SLinitial={sl1,sl2,…,slsl}，對應(yīng)的隱私級(jí)別集合為PLinitial={pl1,pl2,…,plpl}。PLinitial中元素的取值范圍為[0,1]，值越大表示敏感位置隱私級(jí)別越高。

圖3 路網(wǎng)示意及到達(dá)不同的目的位置需要經(jīng)過路口的個(gè)數(shù)

假設(shè)v為初始敏感位置，其隱私級(jí)別為v.pl，v的鄰接位置集合為neighborSet，g是neighborSet 中的一個(gè)位置，v與g的距離為g.dis，則g的隱私級(jí)別為

從式(6)可知，g.dis 越大，g.pl 就越小，即距離敏感位置越遠(yuǎn)的點(diǎn)隱私級(jí)別越小。若g.dis=0，即g與初始敏感位置v重合，則取其本身的隱私級(jí)別和分配的隱私級(jí)別中較大者作為新的隱私級(jí)別；若g.dis≠0，即g為初始非敏感位置，則其隱私級(jí)別為g.pl。

已知用戶初始敏感位置，根據(jù)圖3(a)計(jì)算該位置的隱私級(jí)別，步驟如下。確定初始集合SLinitial中的位置v至路口i的路段上是否存在用戶的第二個(gè)敏感位置，若不存在，則計(jì)算位置v與i之間的距離dis(v,i)=R，當(dāng)R<η時(shí)，輸出位置v與i的路段v→i；當(dāng)R≥η時(shí)，輸出距離為η的路段。若位置v至路口i的路段上存在用戶的第二個(gè)敏感位置g，則先根據(jù)式(6)計(jì)算位置g的隱私級(jí)別，并與g的初始隱私級(jí)別進(jìn)行比較，取其中較大者作為位置g的最終隱私級(jí)別，此時(shí)，輸出的敏感路段為兩段，即v至g的路段v→g，以及g至路口i的路段g→i。用戶道路隱私級(jí)別劃分算法如算法1 所示。

算法1RPL 算法

輸入路網(wǎng)G=，路網(wǎng)的區(qū)域劃分M={SLinitial,NSLinitial}，初始敏感位置集合SLinitial，每個(gè)敏感位置對應(yīng)的隱私級(jí)別集合PLinitial，距離閾值η

輸出敏感路段及其隱私級(jí)別

如果在初始敏感位置v到路口的路段上出現(xiàn)用戶自定義的另一個(gè)一級(jí)初始隱私位置，則直接輸出位置v到路口的全部路段。

4.2 差分隱私位置保護(hù)機(jī)制

在位置數(shù)據(jù)保護(hù)模塊，采用位置樹結(jié)構(gòu)，基于差分隱私保護(hù)模型提出DPLPM。本文構(gòu)建位置樹反映路網(wǎng)實(shí)際情況。v表示初始敏感位置，i表示路口。路網(wǎng)結(jié)構(gòu)轉(zhuǎn)換為位置樹如圖4 所示。

1) 如圖4(a)所示，敏感位置周圍有2 條路通往路口i，轉(zhuǎn)換為樹結(jié)構(gòu)后，包含一個(gè)根節(jié)點(diǎn)、2 個(gè)葉子節(jié)點(diǎn)。

2) 如圖4(b)所示，敏感位置周圍有3 條路通往路口i，轉(zhuǎn)換為樹結(jié)構(gòu)后，包含一個(gè)根節(jié)點(diǎn)、3 個(gè)葉子節(jié)點(diǎn)。

3) 如圖4(c)所示，在敏感位置周圍的路段上，有一個(gè)敏感位置g，轉(zhuǎn)換為樹結(jié)構(gòu)后，深度為2，包含一個(gè)根節(jié)點(diǎn)、一個(gè)子節(jié)點(diǎn)、2 個(gè)葉子節(jié)點(diǎn)。

圖4 路網(wǎng)結(jié)構(gòu)轉(zhuǎn)換為位置樹

依次類推，將路網(wǎng)轉(zhuǎn)換為位置樹。

根據(jù)差分隱私定義可知，隱私預(yù)算越小，對數(shù)據(jù)的隱私保護(hù)程度越大，以位置樹的高度為基礎(chǔ)，對隱私預(yù)算進(jìn)行分配。

其中，q為2 個(gè)敏感位置間隱私級(jí)別比值，即其應(yīng)分配隱私預(yù)算的比值。位置v為隱私級(jí)別最高的敏感位置，相應(yīng)地，v.pl 最大，即g.pl

下面，根據(jù)路網(wǎng)示意構(gòu)建位置樹結(jié)構(gòu)，根據(jù)樹的高度分配隱私預(yù)算，添加Laplace 噪聲，實(shí)現(xiàn)對用戶位置數(shù)據(jù)的保護(hù)。首先，以位置v為根節(jié)點(diǎn)構(gòu)建位置樹，若構(gòu)建樹的高度為1，則將隱私預(yù)算ε平均分配至用戶的t個(gè)敏感位置；若樹的高度大于1，則按照式(7)分配隱私預(yù)算，并根據(jù)隱私預(yù)算為每個(gè)位置加入符合差分隱私機(jī)制的Laplace 噪聲Laplace Noisy(εt)。差分隱私位置保護(hù)機(jī)制如算法2所示。

算法2DPLPM

輸入路網(wǎng)G=，隱私預(yù)算ε={ε1,ε2,…,εh}，噪聲樹的高度h，噪聲值N={N1,N2,…,Nh}，初始敏感位置v，真實(shí)位置Zt，敏感路段上敏感位置數(shù)t

輸出位置集合W

5 差分隱私證明和算法分析

5.1 差分隱私證明

給定隱私預(yù)算ε，本節(jié)證明RPL 算法和DPLPM均滿足ε-差分隱私。

RPL 算法不能以差分隱私機(jī)制中數(shù)據(jù)集的概念來定義，因?yàn)閷τ谖恢煤臀恢秒[私來說，用戶的每個(gè)位置都是需要被保護(hù)的，本文假設(shè)已知某時(shí)刻的發(fā)布位置Ot，根據(jù)已發(fā)布的位置判斷真實(shí)位置的后驗(yàn)概率為Pr(Zt|Ot)，即

由差分隱私定義可知，RPL 算法滿足ε-差分隱私。

在DPLPM 中，加入Laplace 噪聲，即符合ε-差分隱私，證明過程如下。

證明已知Laplace 機(jī)制的概率密度函數(shù)為，設(shè)px表示Al(x,f,ε)的概率密度函數(shù)，py表示Al(y,f,ε)的概率密度函數(shù)，則對于某個(gè)輸出值Z，有

可知，RPL 算法和DPLPM 均滿足ε-差分隱私。證畢。

5.2 算法分析

1) 時(shí)間復(fù)雜度。假設(shè)連續(xù)位置數(shù)據(jù)中共有n個(gè)位置，在RPL 算法中，最耗時(shí)的部分是遍歷所有位置，其時(shí)間復(fù)雜度為O(n)=n；在DPLPM 中，最耗時(shí)的部分是將隱私預(yù)算分配給每層樹結(jié)構(gòu)，再將每一層的隱私預(yù)算分配給敏感路段中的每一個(gè)位置，其時(shí)間復(fù)雜度為O(n)=ht。總體來說，本文所提算法計(jì)算消耗較小。

2) 隱私性。根據(jù)DPLPM，t時(shí)刻發(fā)布位置Ot使當(dāng)前位置Zt滿足ε-差分隱私，即軌跡W中，每一個(gè)位置都滿足ε-差分隱私，可知軌跡W滿足ε-差分隱私。

3) 數(shù)據(jù)安全性。本文經(jīng)過數(shù)據(jù)劃分模塊和連續(xù)位置數(shù)據(jù)保護(hù)模塊的處理后，將數(shù)據(jù)上傳至位置服務(wù)提供商，位置服務(wù)提供商不能獲得用戶原始數(shù)據(jù)，所以攻擊者不能通過位置服務(wù)提供商對用戶進(jìn)行攻擊；本文采用差分隱私保護(hù)模型抵御背景知識(shí)攻擊，攻擊者無法根據(jù)用戶的行為模式和地理拓?fù)潢P(guān)系推斷出用戶的真實(shí)位置，并根據(jù)用戶的隱私級(jí)別分配不同的隱私預(yù)算，實(shí)現(xiàn)對用戶位置數(shù)據(jù)的保護(hù)。

4) 數(shù)據(jù)可用性。本文通過式(5)對數(shù)據(jù)可用性進(jìn)行分析。由式(5)可知，影響數(shù)據(jù)可用性主要有以下3 個(gè)因素。①軌跡長度。軌跡長度越長，需要考慮的時(shí)刻越多，使發(fā)布位置與真實(shí)位置之間的距離越大，即數(shù)據(jù)可用性越差。②敏感位置Zt與發(fā)布位置Ot的歐氏距離，距離越大，RMSE 越大，數(shù)據(jù)可用性越差。③指示函數(shù)∏Zt的值，即判斷位置Zt是否為敏感位置，若為敏感位置，則∏Zt=1，否則，∏Zt=0，數(shù)據(jù)可用性最高。本文所提RPL 算法使敏感軌跡長度降到最低，同時(shí)由概率比值可得真實(shí)位置與發(fā)布位置之間的距離為eε，通過控制隱私預(yù)算減少兩者的距離，由此可知，本文在數(shù)據(jù)可用性方面是最優(yōu)的。

6 實(shí)驗(yàn)與分析

6.1 實(shí)驗(yàn)設(shè)置

本節(jié)測試本文所提DPLPM 的性能。實(shí)驗(yàn)使用Python 實(shí)現(xiàn)，在3.60 GHz CPU、8 GB RAM 的Windows 10 平臺(tái)上運(yùn)行，實(shí)驗(yàn)數(shù)據(jù)集為真實(shí)位置數(shù)據(jù)集Geolife[13]和Gowalla[14]。將DPLPM 和FPT（final private trajectory）算法[15]、基于頻繁駐留點(diǎn)的加噪（NFRP,noisy of frequent resident points）算法[16]進(jìn)行比較，從隱私保護(hù)程度、算法運(yùn)行時(shí)間和數(shù)據(jù)可用性3 個(gè)方面判斷本文算法的優(yōu)劣性。

6.2 實(shí)驗(yàn)結(jié)果與分析

6.2.1 隱私保護(hù)程度

本節(jié)實(shí)驗(yàn)分析了本文所提DPLPM 的隱私保護(hù)程度，通過用戶自定義和式(6)計(jì)算隱私級(jí)別pl、由仿真實(shí)驗(yàn)結(jié)果選出距離閾值η、初始敏感區(qū)域SLinitial大小k和隱私預(yù)算ε，比較本文算法和FPT算法、NFRP 算法在Geolife 數(shù)據(jù)集和Gowalla 數(shù)據(jù)集上的隱私保護(hù)程度。

k=4，pl=0.25 時(shí)，距離閾值η對隱私保護(hù)程度的影響如圖5 所示。

圖5 η對3 種算法隱私保護(hù)程度的影響

從圖5 可知，3 種算法的隱私保護(hù)程度都隨著η的增大而減小。根據(jù)式(5)可知，隨著輸出路段距離的不斷增大，位置的隱私級(jí)別不斷下降，即隱私保護(hù)程度減小。

pl=0.25，η=20 時(shí)，初始敏感區(qū)域SLinitial大小k對隱私保護(hù)程度的影響如圖6 所示。

圖6 k對3 種算法隱私保護(hù)程度的影響

圖6 可知，3 種算法的隱私保護(hù)程度都隨著k的增大而減小。這是因?yàn)槊舾形恢迷蕉?，則所需的隱私預(yù)算越多，即隱私保護(hù)程度越小。

k=4，η=20 時(shí)，隱私級(jí)別pl 對隱私保護(hù)程度的影響如圖7 所示。從圖7 可知，隨著pl 的增加，3 種算法隱私保護(hù)程度都在增加。這是因?yàn)殡[私級(jí)別pl 越大，為其分配的隱私預(yù)算越小，即隱私保護(hù)程度要越大。

圖7 pl 對3 種算法隱私保護(hù)程度的影響

k=4，η=20，pl=0.25 時(shí)，隱私預(yù)算ε對隱私保護(hù)程度的影響如圖8 所示。從圖8 可知，隨著ε的增加，3 種算法隱私保護(hù)程度都在減少，由差分隱私定義可得，隱私預(yù)算越大，隱私保護(hù)程度越小。

此外，從圖5～圖8 可以看出，在不同參數(shù)下，本文所提算法的隱私保護(hù)程度都優(yōu)于其他2 種算法。

圖8 ε對3 種算法隱私保護(hù)程度的影響

6.2.2 數(shù)據(jù)可用性

本文用RMSE 衡量數(shù)據(jù)可用性。本節(jié)實(shí)驗(yàn)分別在Geolife 數(shù)據(jù)集和Gowalla 數(shù)據(jù)集上運(yùn)行，對比了本文所提DPLPM、FPT 算法和NFRP 算法的數(shù)據(jù)可用性。其中，F(xiàn)PT 算法通過構(gòu)建噪聲前綴樹實(shí)現(xiàn)對位置數(shù)據(jù)的保護(hù)，NFRP 算法根據(jù)統(tǒng)計(jì)后的流量圖中邊的流量值添加噪聲。

k=4，pl=0.25 時(shí)，距離閾值η對RMSE 的影響如圖9 所示。

圖9 η對3 種算法RMSE 的影響

從圖9 可知，3 種算法的RMSE 都隨著η的增大而增大。NFRP 算法的可用性最差，因?yàn)樵撍惴ㄖ粸槟骋晃恢玫慕?jīng)緯度添加噪聲；FPT 算法的位置數(shù)據(jù)可用性相對較好，但FTP 算法較多地對空節(jié)點(diǎn)添加噪聲；DPLPM 考慮了位置連續(xù)性之間的影響，數(shù)據(jù)可用性是最好。

pl=0.25，η=20 時(shí)，初始敏感區(qū)域SLinitial大小k對DPLPM、FPT 算法和NFRP 算法RMSE 的影響如圖10 所示。

圖10 k對3 種算法RMSE 的影響

從圖10 可知，3 種算法的RMSE 都隨著k的增大而增大。這是因?yàn)槲恢脗€(gè)數(shù)的增大會(huì)導(dǎo)致隱私預(yù)算增多，添加的噪聲也增加，即數(shù)據(jù)可用性變差。NFRP 算法的可用性最差，DPLPM 可用性最好，而FPT 算法介于二者之間。

k=4，η=20 時(shí)，隱私級(jí)別pl 對DPLPM、FTP算法和NFRP 算法RMSE 的影響如圖11 所示。

從圖11 可知，3 種算法的RMSE 都隨著pl 的增大而增大。這是因?yàn)殡S著隱私級(jí)別的增大需要添加的噪聲增加，數(shù)據(jù)可用性變差。DPLPM 的可用性最好，F(xiàn)PT 算法次之，NFRP 算法最差。

圖11 pl 對3 種算法RMSE 的影響

6.2.3 算法運(yùn)行時(shí)間

本節(jié)實(shí)驗(yàn)在Geolife數(shù)據(jù)集和Gowalla數(shù)據(jù)集上運(yùn)行DPLPM、FPT 算法和NFRP 算法，對比3 種算法的運(yùn)行時(shí)間。

k=4，pl=0.25 時(shí)，距離閾值η對DPLPM、FPT算法和NFRP 算法運(yùn)行時(shí)間的影響如圖12 所示。

從圖12 可知，隨著η的增加，3 種算法的運(yùn)行時(shí)間都隨之增加。因?yàn)镈PLPM 只需要提供加噪，所以DPLPM 運(yùn)行時(shí)間是最少的。

圖12 η對3 種算法運(yùn)行時(shí)間的影響

pl=0.25，η=20 時(shí)，初始敏感區(qū)域SLinitial大小k對DPLPM、FPT 算法和NFRP 算法運(yùn)行時(shí)間的影響如圖13 所示。

圖13 k對3 種算法運(yùn)行時(shí)間的影響

從圖13 可知，隨著k的增加3 種算法的運(yùn)行時(shí)間都隨之增加。FTP 算法在2 個(gè)數(shù)據(jù)集上的運(yùn)行時(shí)間都是最長的，而NFRP 算法次之，DPLPM 的運(yùn)行時(shí)間是最短的。

k=4，η=20 時(shí)，隱私級(jí)別pl 對DPLPM、FTP算法和NFRP 算法運(yùn)行時(shí)間的影響如圖14 所示。

從圖14 可知，隨著pl 的增加，3 種算法的運(yùn)行時(shí)間都在增加。FPT 算法在2 個(gè)數(shù)據(jù)集上運(yùn)行時(shí)間都最長，NFRP 算法次之，DPLPM 的運(yùn)行時(shí)間最短。

圖14 pl 對3 種算法運(yùn)行時(shí)間的影響

6.3 相關(guān)工作比較

本文所提DPLPM 與其他方法的比較如表2 所示。文獻(xiàn)[17]提出一種基于隱私拆分的軌跡隱私保護(hù)方法，建立單點(diǎn)位置的發(fā)布對查詢軌跡的前向和后向隱私風(fēng)險(xiǎn)評估機(jī)制，通過拆分查詢軌跡，消除軌跡中位置間的相關(guān)性，但沒有控制隱私預(yù)算，同時(shí)使算法開銷增大。文獻(xiàn)[12]提出一種差分隱私保護(hù)方法，根據(jù)時(shí)間相關(guān)性，使用馬爾可夫鏈預(yù)測前一個(gè)位置對后一個(gè)位置的影響，考慮了路網(wǎng)中的位置連續(xù)性，但沒有對隱私預(yù)算進(jìn)行合理分配。文獻(xiàn)[18]將不規(guī)則樹引入差分隱私方法中，減少連續(xù)查詢時(shí)噪聲疊加帶來的查詢精度下降問題，但沒有考慮位置間的相關(guān)性。文獻(xiàn)[19]提出AC-TFIDF（adaptive clustering based TFIDF）算法，根據(jù)重要位置點(diǎn)在不同時(shí)刻的分布狀況，選擇聚類中心代替原始位置，生成發(fā)布位置，但沒有考慮路網(wǎng)實(shí)際情況。

表2 相關(guān)工作比較

7 結(jié)束語

本文研究了連續(xù)位置隱私保護(hù)問題，基于差分隱私機(jī)制，提出了一種連續(xù)位置隱私保護(hù)機(jī)制。在位置數(shù)據(jù)劃分模塊提出了隱私級(jí)別劃分算法，根據(jù)路網(wǎng)關(guān)系計(jì)算其相鄰位置的隱私級(jí)別，使攻擊者無法推斷出用戶隱私位置；在位置數(shù)據(jù)保護(hù)模塊提出差分隱私位置保護(hù)機(jī)制DPLPM，根據(jù)道路關(guān)系映射位置樹，根據(jù)樹的高度為敏感路段分配隱私預(yù)算，并添加符合差分隱私機(jī)制的Laplace 噪聲，保護(hù)了用戶的位置信息。理論分析證明，本文算法均滿足ε-差分隱私。仿真實(shí)驗(yàn)證明，本文所提DPLPM 有較好的隱私保護(hù)程度和較高的數(shù)據(jù)可用性。