袁 健，王 迪，高喜龍，王睿寧，林思劼

1(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093) 2(復(fù)旦大學(xué) 信息科學(xué)與工程學(xué)院 ，上海 200093)

1 引 言

隨著移動(dòng)應(yīng)用技術(shù)的發(fā)展，基于位置的服務(wù)(location based service ,LBS)給人們帶來(lái)了諸多便利，日益受到人們的歡迎[1].用戶在向服務(wù)商請(qǐng)求服務(wù)的過(guò)程中，包含了位置信息、身份信息、個(gè)人興趣等敏感數(shù)據(jù).其中，位置信息以及由位置信息推理出的信息屬于位置隱私[2].與LBS請(qǐng)求內(nèi)容相關(guān)的信息屬于查詢隱私[3]，它們都屬于位置服務(wù)隱私保護(hù)的范疇[4].研究表明，用戶的連續(xù)查詢會(huì)形成基于位置服務(wù)的軌跡信息，攻擊者經(jīng)過(guò)推理分析即可獲取諸如用戶住址、宗教信仰、是否患病等敏感信息[5]，甚至預(yù)測(cè)用戶的下一個(gè)位置[6]，這將會(huì)給LBS用戶造成不可估計(jì)的損失.因此，基于連續(xù)查詢的軌跡隱私保護(hù)技術(shù)成為目前LBS領(lǐng)域的熱點(diǎn)之一.

為了解決位置服務(wù)中的軌跡隱私保護(hù)問(wèn)題，Gedik等人[7]提出了位置K-匿名模型.該模型利用K-匿名算法，保證當(dāng)前用戶與其他(k-1)個(gè)用戶無(wú)法區(qū)分，實(shí)現(xiàn)基于位置服務(wù)的隱私保護(hù).但由于K-匿名自身的劣勢(shì)，其無(wú)法對(duì)攻擊者的背景知識(shí)做出有效估計(jì)，很難設(shè)計(jì)出有效而全面的LBS軌跡隱私保護(hù)模型[8].差分隱私[9]具有背景無(wú)關(guān)性，能夠彌補(bǔ)K-匿名在背景攻擊方面的不足，逐漸被應(yīng)用于LBS軌跡隱私保護(hù)領(lǐng)域.但由于差分隱私過(guò)度依賴隱私預(yù)算，隱私保護(hù)的有效時(shí)長(zhǎng)無(wú)法得到保證[10].

針對(duì)現(xiàn)有算法存在的缺陷，本文提出了基于差分隱私的匿名組LBS軌跡隱私保護(hù)模型K-Differential-Privacy，該模型由兩個(gè)子算法構(gòu)成：與Chord相結(jié)合以快速定位的用戶軌跡劃分定位算法(User Trajectory Partioned Position Algorithm Based On Chord,簡(jiǎn)稱UTPP算法)和基于差分隱私的噪聲匿名組算法(Nosied Anonymous Group Algorithm Based On Differential Privacy ,簡(jiǎn)稱NAGDP算法).經(jīng)實(shí)驗(yàn)驗(yàn)證，噪聲匿名組的設(shè)置提高了LBS軌跡隱私保護(hù)強(qiáng)度，同時(shí)，UTPP算法的采用保證了匿名組的生成速度，優(yōu)化了查詢請(qǐng)求的等待時(shí)間.

2 相關(guān)工作

根據(jù)查詢請(qǐng)求在到達(dá)LBS服務(wù)器之前變換方式的差異，目前，軌跡隱私保護(hù)方法可分為以下3種：基于K匿名泛化的軌跡隱私保護(hù)方法、基于噪聲數(shù)據(jù)的軌跡隱私保護(hù)方法、基于動(dòng)態(tài)假名的軌跡隱私保護(hù)方法[11].

基于K匿名泛化的軌跡隱私保護(hù)方法的主要思想是：將連續(xù)的n次查詢視為n個(gè)獨(dú)立的 LBS 服務(wù)請(qǐng)求，即分別為這n次查詢構(gòu)建匿名空間.時(shí)空偽裝[12]是實(shí)現(xiàn)該方法的主要技術(shù)，它指用一個(gè)空間區(qū)域CR(Clocking Region)來(lái)代替用戶的真實(shí)位置；或通過(guò)延遲響應(yīng)時(shí)間，使時(shí)空區(qū)域內(nèi)的用戶數(shù)量足夠多，使得攻擊者無(wú)法推斷出真實(shí)用戶.針對(duì)單獨(dú)的查詢請(qǐng)求，該方法能夠有效地保護(hù)基于位置服務(wù)的用戶隱私.而軌跡信息與連續(xù)查詢相關(guān)，在進(jìn)行連續(xù)查詢請(qǐng)求時(shí)，時(shí)空偽裝方法易受到最大速度攻擊以及連續(xù)查詢攻擊.前者指利用移動(dòng)用戶的最大速度和多個(gè)連續(xù)時(shí)刻的偽裝區(qū)域，推斷出查詢用戶位置的攻擊方式；后者指利用偽裝區(qū)域匿名集的交集推斷出查詢用戶位置的攻擊方式.為了抵制最大速度攻擊，Cheng等人[13]提出Delaying和Patching方案，其中，Delaying通過(guò)延遲請(qǐng)求來(lái)實(shí)現(xiàn)，Patching通過(guò)擴(kuò)大偽裝區(qū)域來(lái)實(shí)現(xiàn).這兩種方案均降低了LBS的服務(wù)質(zhì)量.為了抵制連續(xù)查詢攻擊，Xu 等人[14]首先提出一個(gè)支持連續(xù)空間查詢的K-匿名隱藏區(qū)生成算法KAA.Michaela等人[15]提出MaskIt方法，用隱式馬爾科夫模型對(duì)攻擊者獲取的敏感信息進(jìn)行建模.Agir 等人[16]利用有向圖對(duì)用戶在連續(xù)位置上變換的概率進(jìn)行建模，以此來(lái)估計(jì)用戶在下一個(gè)位置上的隱私級(jí)別.雖然以上改進(jìn)方法均能夠支持連續(xù)查詢，但由于基于K匿名泛化的軌跡隱私保護(hù)方法以K-匿名為基礎(chǔ)，其無(wú)法對(duì)攻擊者的背景知識(shí)做出有效估計(jì)，難以設(shè)計(jì)出有效、全面的軌跡隱私保護(hù)模型[4,17].

基于噪聲數(shù)據(jù)的軌跡隱私保護(hù)方法的主要思想是：將若干假位置(dummy)包含在發(fā)送的LBS請(qǐng)求中來(lái)保護(hù)真實(shí)位置，使攻擊者無(wú)法分辨出用戶位置的真假.其中，假位置是指用戶的周邊位置.該方法的隱私保護(hù)程度和服務(wù)質(zhì)量與真假位置的距離有關(guān).因此噪聲數(shù)據(jù)的添加機(jī)制是該方法的核心.Kido等人[18]將真實(shí)位置隨機(jī)移動(dòng)后作為假位置，但該加噪機(jī)制產(chǎn)生的假位置與用戶真實(shí)的移動(dòng)特征不符，攻擊者很容易區(qū)分出真假位置.針對(duì)這一問(wèn)題，Suzuki等人[19]在生成虛假位置點(diǎn)時(shí)加入了移動(dòng)速度、路網(wǎng)等約束條件.Kato等人[20]認(rèn)為移動(dòng)用戶不會(huì)始終連續(xù)性移動(dòng)，因此其在生成噪聲數(shù)據(jù)點(diǎn)時(shí)會(huì)讓移動(dòng)對(duì)象根據(jù)周邊的環(huán)境隨機(jī)地產(chǎn)生一些停頓，以防止攻擊者區(qū)分出真假位置.但是，真實(shí)場(chǎng)景中會(huì)遇到各種隨機(jī)事件，影響用戶的行為，因此，如何設(shè)計(jì)良好的加噪機(jī)制成為該方法的一個(gè)挑戰(zhàn).此外，上述方法對(duì)攻擊者的背景知識(shí)的假設(shè)較為保守，當(dāng)攻擊者獲得較多背景知識(shí)時(shí)，軌跡隱私保護(hù)無(wú)法得到保障.

基于動(dòng)態(tài)假名的軌跡隱私保護(hù)方法的主要思想是：用戶在發(fā)送LBS請(qǐng)求時(shí)使用假名(pseudonym)來(lái)代替真實(shí)身份.但移動(dòng)用戶在路網(wǎng)中是公開可見的，長(zhǎng)時(shí)間使用同一假名無(wú)法有效保護(hù)用戶的隱私.因此，F(xiàn)reudiger等人[21]提出了基于 mix-zone 的動(dòng)態(tài)假名技術(shù)，該技術(shù)的實(shí)質(zhì)是讓第三方改變用戶在指定區(qū)域內(nèi)的假名.其中，如何構(gòu)建mix-zone區(qū)域是該技術(shù)的關(guān)鍵.Palanisamy等人[22]基于用戶在路網(wǎng)上的運(yùn)動(dòng)模式，提出MobiMix，針對(duì)現(xiàn)實(shí)中可能被攻擊者利用的背景知識(shí)，利用不規(guī)則多邊形及其組合建立單個(gè)mix-zone區(qū)域.但現(xiàn)實(shí)中需要部署多個(gè)mix-zone區(qū)域才能有效保護(hù)軌跡隱私.基于此，Xu等人[23]提出一種多個(gè)mix-zone區(qū)域的部署方案.但基于動(dòng)態(tài)假名的方法需要第三方機(jī)構(gòu)集中地對(duì)用戶的假名進(jìn)行修改，而第三方的可靠性則決定了該方法的有效性.

由上可知，基于K匿名泛化的軌跡隱私保護(hù)方法具有K-匿名本身帶來(lái)的無(wú)法抵抗背景知識(shí)攻擊的缺陷；基于噪聲數(shù)據(jù)的軌跡隱私保護(hù)方法需要尋找一個(gè)有效的加噪機(jī)制，同時(shí)需要優(yōu)化背景知識(shí)假設(shè)理論；基于動(dòng)態(tài)假名的軌跡隱私保護(hù)方法過(guò)于依賴第三方機(jī)構(gòu)，無(wú)法保障隱私安全.因此，基于噪聲數(shù)據(jù)的位置擾亂技術(shù)在LBS領(lǐng)域日益受到重視[24].與基于噪聲數(shù)據(jù)的軌跡隱私保護(hù)方法中以假位置代替真位置的思想不同，它主要是利用位置加噪算法對(duì)每個(gè)時(shí)刻的真實(shí)位置添加隨機(jī)噪聲，生成擾亂位置點(diǎn)，實(shí)現(xiàn)軌跡隱私保護(hù)[25].為了刻畫位置擾亂方法中噪聲與隱私間的關(guān)系，差分隱私的概念被引入.差分隱私的定義由Dwork在2006年提出[26].在該定義下，數(shù)據(jù)集的計(jì)算處理結(jié)果對(duì)于數(shù)據(jù)集中具體某個(gè)記錄的變化是不敏感的，單條記錄是否存在于數(shù)據(jù)集中，對(duì)計(jì)算結(jié)果的影響微乎其微.它主要解決傳統(tǒng)隱私保護(hù)模型的兩個(gè)缺點(diǎn)：其一，差分隱私假設(shè)攻擊者可獲得除目標(biāo)記錄之外的所有信息，即假設(shè)攻擊者可獲得所有背景知識(shí)，并以此為基礎(chǔ)構(gòu)建隱私保護(hù)模型，無(wú)需再針對(duì)不同背景知識(shí)信息，構(gòu)建相應(yīng)模型；其二，差分隱私建立在堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)之上，對(duì)隱私保護(hù)進(jìn)行了嚴(yán)格的定義并提供了量化評(píng)估方法，使得不同參數(shù)處理下的數(shù)據(jù)集所提供的隱私保護(hù)水平具有可比較性[27].傳統(tǒng)差分隱私保護(hù)主要針對(duì)統(tǒng)計(jì)數(shù)據(jù)庫(kù)的隱私泄露問(wèn)題，而位置隱私保護(hù)則不同，其無(wú)法應(yīng)用傳統(tǒng)數(shù)據(jù)庫(kù)隱私保護(hù)中的統(tǒng)計(jì)特性.基于此，Chatzikokolakis 等人[28]對(duì)差分隱私進(jìn)行了擴(kuò)展，使其能夠適用于位置隱私保護(hù)，基于此，他們提出了基于Geo-Indistinguishability[10]的軌跡隱私保護(hù)算法.該算法使用差分隱私來(lái)刻畫實(shí)體間的差異性，利用拉普拉斯機(jī)制進(jìn)行加噪，通過(guò)提交噪聲點(diǎn)來(lái)隱藏真實(shí)用戶的信息.為了盡可能地利用隱私預(yù)算，保證軌跡隱私不被攻擊者獲取，Chatzikokolakis[29]又提出一種基于預(yù)測(cè)機(jī)制的軌跡隱私保護(hù)算法.但當(dāng)差分隱私本身的隱私參數(shù)累積超過(guò)給定的隱私預(yù)算后，在一定程度上會(huì)造成隱私泄露問(wèn)題.因而，當(dāng)用戶的查詢量累積到一定程度后，差分隱私算法無(wú)法從根本上解決軌跡隱私泄漏問(wèn)題[24]，使得隱私保護(hù)的有效時(shí)長(zhǎng)無(wú)法得到保障.

為了解決隱私預(yù)算過(guò)度依賴所導(dǎo)致的隱私保護(hù)時(shí)效有限的問(wèn)題，本文提出NAGDP算法，將K-匿名算法中的匿名組思想融入到差分隱私的噪聲生成算法中.該算法以不暴露真實(shí)查詢用戶的位置為目的，通過(guò)拉普拉斯機(jī)制在給定參數(shù)范圍內(nèi)生成多個(gè)噪聲用戶.利用噪聲用戶來(lái)請(qǐng)求服務(wù)，使攻擊者無(wú)法識(shí)別出真實(shí)用戶，以實(shí)現(xiàn)真實(shí)用戶的軌跡隱私保護(hù).由于在用戶請(qǐng)求服務(wù)過(guò)程中多次涉及相關(guān)用戶的定位過(guò)程，而現(xiàn)有的基于差分隱私的軌跡隱私保護(hù)算法并未涉及該領(lǐng)域的內(nèi)容.因此，Ghinita等人[30]提出了基于Hibert-Curve[31]的空間定位算法，但該算法只能實(shí)現(xiàn)位置隱私保護(hù).針對(duì)軌跡隱私保護(hù)中用戶位置變化的不定時(shí)性以及連續(xù)性特點(diǎn)，本文提出UTPP算法，以降低更新空間的代價(jià).通過(guò)相關(guān)實(shí)驗(yàn)證實(shí)，K-Differential-Privacy模型克服了現(xiàn)有基于差分隱私的軌跡隱私保護(hù)方法對(duì)隱私預(yù)算過(guò)度依賴的缺點(diǎn)，其中，UTPP定位算法的使用也使得用戶的服務(wù)質(zhì)量得到了明顯的提升.

3 K-Differential-Privacy模型

K-Differential-Privacy模型的核心思想是：以拉普拉斯機(jī)制為基礎(chǔ)生成噪聲，在用戶指定的隱私保護(hù)參數(shù)范圍內(nèi)確定若干個(gè)噪聲用戶，將其設(shè)定為匿名用戶組，并以匿名組的身份去請(qǐng)求服務(wù).與傳統(tǒng)的K-匿名方法相比，K-Differential-Privacy模型最大的不同之處在于，實(shí)際提交的匿名組不包含真正的查詢用戶，同時(shí)，結(jié)合了差分隱私的思想，使攻擊者在給定隱私參數(shù)范圍內(nèi)無(wú)法區(qū)分真實(shí)用戶與噪聲用戶.

3.1 基于Chord算法的用戶自組織網(wǎng)絡(luò)

Ghinita 等人[32]實(shí)現(xiàn)了一種基于Chord算法的用戶自組織網(wǎng)絡(luò)系統(tǒng)，如圖1所示.

圖1 基于Chord的用戶自組織網(wǎng)絡(luò) Fig.1 User self-organization network base on Chord

系統(tǒng)內(nèi)用戶通過(guò)集群的方式自組織一個(gè)Chord網(wǎng)絡(luò)系統(tǒng)，Chord上的每個(gè)用戶節(jié)點(diǎn)是當(dāng)前集群的頭節(jié)點(diǎn).該節(jié)點(diǎn)擁有一個(gè)包含m(用戶的希爾伯特值)位的指向其他節(jié)點(diǎn)的指針路由表，路由表中包括：

·指向該節(jié)點(diǎn)的直接前驅(qū)和直接后繼節(jié)點(diǎn)指針；

·一個(gè)用來(lái)提高容錯(cuò)率的后繼鏈表，包含節(jié)點(diǎn)n的數(shù)個(gè)后繼節(jié)點(diǎn)指針；

·一個(gè)存儲(chǔ)有距離當(dāng)前節(jié)點(diǎn)距離為2i(i=0,1,2,…,m-1)的節(jié)點(diǎn)所在集群頭節(jié)點(diǎn)的指針鏈表(不包含已存儲(chǔ)的節(jié)點(diǎn)).

在如圖1所示的基于Chord的用戶系統(tǒng)架構(gòu)中，以用戶U12為例進(jìn)行分析，其存儲(chǔ)路由表如表1所示：

表1 用 戶U12路由表Table 1 Routing Table for user U12

每個(gè)集群的大小應(yīng)根據(jù)當(dāng)前希爾伯特空間內(nèi)的用戶數(shù)目決定，每個(gè)集群節(jié)點(diǎn)的數(shù)目應(yīng)限制在α到3α-1之間，其中α為系統(tǒng)參數(shù)，當(dāng)前集群內(nèi)節(jié)點(diǎn)數(shù)目達(dá)到集群最大值時(shí)應(yīng)考慮各個(gè)割分集群[32].文獻(xiàn)[30]實(shí)現(xiàn)了一種基于Hibert-Curve的用戶排序方法，在此基礎(chǔ)上，用戶可獲取希爾伯特曲線空間內(nèi)唯一希爾伯特值.

3.2 K-Differential-Privacy模型概述

K-Differential-Privacy模型如圖2所示，主要包括兩個(gè)子算法：用戶軌跡劃分定位算法UTPP與基于差分隱私的噪聲匿名組算法NAGDP：

圖2 K-Differential-Privacy流程圖Fig.2 Flowchart for K-Differential-Privacy

K-Differential-Privacy模型的具體工作流程如下：

Step1.LBS服務(wù)器對(duì)服務(wù)區(qū)域內(nèi)所有用戶啟用Hibert排序，并使用戶維持一個(gè)基于Chord算法的自組織網(wǎng)絡(luò)；

Step2.用戶U1向服務(wù)器請(qǐng)求LBS；

Step3.系統(tǒng)根據(jù)U1所處位置，啟用UTPP算法，得到用戶U1在Hibert-Curve空間內(nèi)唯一標(biāo)志；

Step4.根據(jù)新入用戶標(biāo)志，更新集群，得到新的用戶自組織網(wǎng)絡(luò)；

Step5.啟用NAGDP算法，對(duì)用戶U1位置進(jìn)行極坐標(biāo)系的轉(zhuǎn)換[33]；

Step6.根據(jù)系統(tǒng)參數(shù)k,ε生成用戶U1的k個(gè)噪聲點(diǎn)；

Step7.以Step6的噪聲點(diǎn)在自組織網(wǎng)絡(luò)中逼近尋找k個(gè)用戶，生成匿名組；

Step8.用戶U1所在集群頭節(jié)點(diǎn)向LBS服務(wù)器請(qǐng)求查詢，獲取服務(wù).

3.3 UTPP算法

為了減少用戶請(qǐng)求LBS時(shí)的等待時(shí)間，K-Differential-Privacy模型基于分布式架構(gòu)構(gòu)建用戶自組織網(wǎng)絡(luò).在網(wǎng)絡(luò)中，每個(gè)用戶都擁有唯一標(biāo)識(shí)，用于查找和定位相關(guān)用戶.為此，考慮采用Ghinita等人提出的基于Hilbert-Curve[31]的希爾伯特曲線空間，對(duì)用戶位置進(jìn)行排序[30].文獻(xiàn)[31]提出的Hibert-Curve經(jīng)過(guò)有限次迭代，總能將區(qū)域內(nèi)元素劃分至相互隔離的四邊形區(qū)域，并且由一條曲線貫穿區(qū)域內(nèi)所有分隔空間.基于以上特點(diǎn)，為了保證用戶標(biāo)識(shí)的唯一性，本文以用戶在曲線上出現(xiàn)的先后順序作為用戶標(biāo)識(shí)，同時(shí)采用基于Chord的用戶自組織網(wǎng)絡(luò)對(duì)擁有標(biāo)識(shí)符的用戶進(jìn)行維護(hù).

任一區(qū)域內(nèi)的日常通勤LBS用戶軌跡較為固定，在該背景下，用戶的移動(dòng)區(qū)域維持在固定范圍內(nèi)，該部分用戶的希爾伯特空間排序較為穩(wěn)定.因此，如何對(duì)用戶新軌跡進(jìn)行分割定位成為本算法的核心.當(dāng)用戶外出旅游到達(dá)一個(gè)陌生地時(shí)，該地的劃分位置所用的服務(wù)器上未存儲(chǔ)該用戶的信息，本文采用H-Space(S)表示當(dāng)前用戶自組織網(wǎng)絡(luò)中所存儲(chǔ)的相關(guān)用戶在希爾伯特曲線空間內(nèi)的信息，其中，ULoc表示當(dāng)前新用戶的位置信息，且ULoc?H-Space(S).此時(shí)，排序算法需考慮如何獲取新用戶的標(biāo)識(shí)符.綜上，本文提出適應(yīng)于軌跡隱私保護(hù)的基于Chord的定位算法UTPP，其算法流程如圖3所示.

圖3 UTPP流程圖Fig.3 Flowchart for UTPP

UTPP算法的工作流程如下：

Step1.啟動(dòng)用戶的希爾伯特排序過(guò)程，對(duì)當(dāng)前區(qū)域內(nèi)所有用戶進(jìn)行排序，形成Hibert-Curve空間，并以用戶自組織網(wǎng)絡(luò)維持；

Step2.在已有排序號(hào)的情況下，當(dāng)有用戶發(fā)起LBS請(qǐng)求時(shí)，查詢當(dāng)前用戶在Hibert-Curve曲線空間內(nèi)的位置序列號(hào)(Serial Number in H-Space(S),簡(jiǎn)稱SNIHS).若用戶在Hibert-Curve曲線空間內(nèi)的SNIHS未被占用，直接返回SNIHS作為用戶標(biāo)識(shí)符(ID of User,簡(jiǎn)稱IDOU)；否則執(zhí)行Step3；

Step3.當(dāng)前用戶標(biāo)志位所對(duì)應(yīng)的用戶組所包含的用戶未達(dá)到隊(duì)內(nèi)上限，執(zhí)行用戶入組策略，得到用戶組內(nèi)標(biāo)號(hào)(ID in Group,IDIG)，進(jìn)而得到IDOU；否則執(zhí)行Step4.若使用用戶組標(biāo)志(Flag of Group,FOG)表示SNIHS是否被占用，則Step2與Step3可用如式(1)表示：

(1)

Step4.對(duì)于新入組用戶U1執(zhí)行新一輪的Hibert排序過(guò)程，獲取IDOU.

針對(duì)Step 3中的隊(duì)內(nèi)上限問(wèn)題，由于構(gòu)造每個(gè)劃分區(qū)域的迭代曲線時(shí)，曲線的迭代不超過(guò)4次，因此，與執(zhí)行入隊(duì)策略后直接查找用戶的代價(jià)相比，在n個(gè)已完成希爾伯特排序的用戶空間內(nèi)添加新用戶，所耗費(fèi)的資源應(yīng)滿足公式(2)，具體如(2)所示：

kn≤4n

(2)

當(dāng)組內(nèi)排序值超過(guò)4時(shí)，查找新用戶的代價(jià)實(shí)際超過(guò)新的希爾伯特排序過(guò)程所產(chǎn)生的代價(jià).為此，限定每個(gè)組隊(duì)列上限為4.當(dāng)組內(nèi)用戶達(dá)到上限，啟用新一輪的希爾伯特排序.

3.4 NAGDP算法

3.4.1 噪聲獲取

NAGDP算法以差分隱私噪聲生成算法為核心，在一定程度上擺脫了傳統(tǒng)差分隱私對(duì)隱私預(yù)算的過(guò)度依賴問(wèn)題.Chatzikokolakis等人在Geo-Indistinguishability[10]算法中針對(duì)位置差分隱私保護(hù)提出了一種改進(jìn)的拉普拉斯加噪方法.該方法以x0代表用戶真實(shí)位置,使隱私保護(hù)參數(shù)ε>0，對(duì)任意噪聲點(diǎn)x，噪聲函數(shù)的概率密度函數(shù)的兩種表示方式如公式(3)和公式(4)所示.

(3)

(4)

其中，ε2/2π是一個(gè)標(biāo)準(zhǔn)化因子，d(x,x)表達(dá)二維空間中兩個(gè)位置點(diǎn)的歐氏距離.公式(3)與公式(4)分別為噪聲函數(shù)在正常二維坐標(biāo)系與極坐標(biāo)系下的表示.

基于r、θ的獨(dú)立性[10]，通過(guò)Dε(γ,θ)對(duì)r、θ積分，來(lái)表示Dε(γ,θ)關(guān)于r、θ的邊緣分布函數(shù)，具體如公式(5)和公式(6)所示：

(5)

(6)

由于Dε,θ(θ)的連續(xù)性，θ的取值范圍為[0,2π).對(duì)于r的計(jì)算如公式(7)所示:

(7)

θ=random[0,2π)

(8)

z=random[0,1)

(9)

(10)

通過(guò)公式(8)、公式(9)和公式(10)，可以得到對(duì)應(yīng)具體查詢用戶位置的噪聲點(diǎn).

3.4.2 NAGDP算法描述

NAGDP算法具體流程如圖4所示.

圖4 NAGDP流程圖Fig.4 Flowchart for NAGDP

算法執(zhí)行步驟如下：

Step1.用極坐標(biāo)(rU,θU)表示查詢用戶的位置參數(shù)；

Step2.查詢當(dāng)前用戶的噪聲參數(shù)是否達(dá)到系統(tǒng)要求的k值,若是，執(zhí)行Step 5，否則執(zhí)行Step 3；

Step3.根據(jù)公式(8)和公式(10)，得到生成噪聲點(diǎn)的兩個(gè)參數(shù)：rN,θN；

Step4.根據(jù)rN,θN, 得到實(shí)際噪聲坐標(biāo)點(diǎn)xi，執(zhí)行Step 2；

Step5.根據(jù)k個(gè)噪聲點(diǎn)，獲取匿名組用戶，形成匿名組.

NAGDP算法將每一次的用戶查詢看作前后不相關(guān)的查詢，因而需要指定隱私參數(shù)k以及ε，k為匿名組中包含的噪聲用戶的個(gè)數(shù)，ε為隱私保護(hù)參數(shù)[10]，在算法實(shí)際執(zhí)行中，該參數(shù)描述的是與真實(shí)用戶的距離r.用戶的每次查詢請(qǐng)求首先經(jīng)過(guò)自身的處理，生成k個(gè)滿足隱私參數(shù)要求的噪聲點(diǎn).由于噪聲點(diǎn)位置并不是提交請(qǐng)求的用戶的位置，所以利用噪聲點(diǎn)逼近的匿名組成員位置與噪聲點(diǎn)之間存在距離差，因此NAGDP的隱私參數(shù)ε指定的距離信息r1應(yīng)小于用戶實(shí)際指定的距離信息r2.假設(shè)最終希爾伯特排序后的劃分格邊長(zhǎng)為l,則r2與r1的關(guān)系式應(yīng)如公式(11)所示：

(11)

由于地理位置因素等特點(diǎn)，生成的噪聲點(diǎn)附近可能不存在相關(guān)用戶(如噪聲點(diǎn)在海中心).在這種情況下，可以預(yù)先排除不符合要求的噪聲點(diǎn)，啟動(dòng)新一輪的噪聲點(diǎn)生成算法，直至利用噪聲點(diǎn)生成最終的實(shí)際查詢匿名組，此時(shí)，查詢用戶的一次NAGDP算法完成.

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

實(shí)驗(yàn)分別從服務(wù)質(zhì)量[34]與隱私保護(hù)度[34]兩個(gè)方面對(duì)比了基于Geo-Indistinguishability的軌跡隱私保護(hù)算法[29]、MobiHide[32]和本文提出的K-Differential-Privacy模型.其中，基于Geo-Indistinguishability的軌跡隱私保護(hù)算法和K-Differential-Privacy模型都以MobiHide作為系統(tǒng)基礎(chǔ).實(shí)驗(yàn)采用Geo-life與T-Drive[29]數(shù)據(jù)集，這兩個(gè)數(shù)據(jù)集均來(lái)自于微軟亞洲研究所.其中Geo-life收集了183名參與者從2007年4月至2012年8月的數(shù)據(jù)；T-Drive收集了超過(guò)104條記錄的北京市出租車司機(jī)數(shù)據(jù).實(shí)驗(yàn)以周為單位，劃分出不同的查詢用戶，從劃分后的用戶中隨機(jī)抽取每組樣本.本實(shí)驗(yàn)單機(jī)環(huán)境為Inter(R) Core(TM) i7 CPU 3.4GHz，8GB內(nèi)存，window10操作系統(tǒng).

4.1 實(shí)驗(yàn)評(píng)價(jià)指標(biāo)

4.1.1 服務(wù)質(zhì)量

隱私保護(hù)的服務(wù)質(zhì)量由響應(yīng)時(shí)間來(lái)衡量.在相同隱私保護(hù)度下，移動(dòng)對(duì)象獲得的服務(wù)質(zhì)量越高則隱私保護(hù)技術(shù)越成熟[24].

響應(yīng)時(shí)間指的是從用戶發(fā)出LBS請(qǐng)求至用戶獲取服務(wù)的時(shí)間，任意選取n位用戶，記用戶Ui的響應(yīng)時(shí)間為ti，對(duì)任意算法模型的平均響應(yīng)時(shí)間MT(Mean Time,簡(jiǎn)稱MT)，可按公式(12)計(jì)算：

(12)

4.1.2 隱私保護(hù)度

隱私保護(hù)度一般通過(guò)軌跡隱私的披露風(fēng)險(xiǎn)來(lái)反映，披露風(fēng)險(xiǎn)越小，隱私保護(hù)度越高.披露風(fēng)險(xiǎn)與隱私保護(hù)算法和攻擊者所掌握的背景知識(shí)相關(guān).假設(shè)攻擊者可以獲得除實(shí)際查詢用戶之外的所有信息.用Ui表示查詢結(jié)束后，攻擊者是否推斷出實(shí)際查詢用戶.若攻擊者推斷出用戶真實(shí)身份，則Ui=true；否則Ui=false.以Ti作為查詢結(jié)果的統(tǒng)計(jì)量，設(shè)每組樣本實(shí)際查詢用戶數(shù)目為n，對(duì)于N組樣本，披露風(fēng)險(xiǎn)DR(Disclosure Risk)計(jì)算公式如公式(13)所示：

(13)

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

算法中的k為匿名組中所包含的用戶數(shù)目；r為用戶指定的隱私保護(hù)范圍，即在r范圍內(nèi)，攻擊者者無(wú)法區(qū)分真實(shí)用戶與虛假用戶.為了對(duì)比三種隱私保護(hù)模型的服務(wù)質(zhì)量與隱私保護(hù)效果，實(shí)驗(yàn)所使用的系統(tǒng)參數(shù)如表2所示.其中，MobiHide[32]是一種基于K-匿名的位置隱私保護(hù)算法，相關(guān)實(shí)驗(yàn)采用1000組用戶的連續(xù)查詢數(shù)據(jù)作為樣本，每組包含1000位用戶，系統(tǒng)參數(shù)k取20.Geo-indistinguishability軌跡隱私保護(hù)模型[29]采用1000組用戶的連續(xù)48小時(shí)內(nèi)的LBS服務(wù)數(shù)據(jù)作為實(shí)驗(yàn)樣本，系統(tǒng)保護(hù)參數(shù)r取100(m).針對(duì)所提出的K-Differential-Privacy模型，為了保證實(shí)驗(yàn)對(duì)比的有效性，同樣系統(tǒng)參數(shù)k取20，r的取值應(yīng)根據(jù)公式(11)以及每次劃分的希爾伯特空間大小共同確定,采用1000組樣本取均值.

表2 對(duì)比實(shí)驗(yàn)使用參數(shù)Table 2 Used parameters in comparative experiment

4.2.1 服務(wù)質(zhì)量

以響應(yīng)時(shí)間作為3種隱私保護(hù)算法服務(wù)質(zhì)量的衡量標(biāo)準(zhǔn)，實(shí)驗(yàn)采用的系統(tǒng)參數(shù)如表2所示.

從數(shù)據(jù)集Geo-life和T-Drive中挑選1000組樣本，每組隨機(jī)挑選1000位用戶.其中，按照公式(12)，取1000位用戶LBS請(qǐng)求的響應(yīng)時(shí)間進(jìn)行統(tǒng)計(jì).得到每組的平均響應(yīng)時(shí)間.

圖5 平均響應(yīng)時(shí)間對(duì)比Fig.5 Comparison for average response time

由于部分方法名過(guò)長(zhǎng)，無(wú)法在圖中完全顯示， Geo-Indistinguishability算法在圖中用Geo表示，K-Differential-Privacy用KDP表示，未使用UTPP算法的K-Differential-Privacy模型用NUTPP-KDP表示.4種方法的平均響應(yīng)時(shí)間MT如圖5所示.

從圖5中可以看出，未使用UTPP算法的K-Differential-Privacy模型的平均響應(yīng)時(shí)間遠(yuǎn)遠(yuǎn)高于其他三種模型；MobiHide模型的平均響應(yīng)時(shí)間最少；完整的K-Differential-Privacy模型與Geo-Indistinguishability模型相比，時(shí)間消耗上略有增加，但總體仍在可接受范圍內(nèi).實(shí)驗(yàn)結(jié)果反映了UTPP定位算法的必要性.

4.2.1 隱私保護(hù)度

針對(duì)連續(xù)查詢，按照表2給定實(shí)驗(yàn)參數(shù)，根據(jù)公式13統(tǒng)計(jì)三種隱私保護(hù)模型的隱私披露情況.對(duì)比結(jié)果如圖6所示.

圖6 三種隱私保護(hù)模型的保護(hù)效果Fig.6 Protection effect of the three kinds of privacy protection models

從圖6可以看出，當(dāng)多組用戶的LBS服務(wù)時(shí)間在24小時(shí)以內(nèi)時(shí)，Geo-Indistinguishability軌跡隱私保護(hù)模型與K-Differential-Privacy模型泄露隱私的概率相差不大,且兩個(gè)軌跡隱私保護(hù)模型的隱私保護(hù)效果較好.然而當(dāng)查詢累積超過(guò)24小時(shí)之后，Geo-Indistinguishability軌跡隱私保護(hù)模型泄露隱私的概率隨時(shí)間的增加而明顯增加.而K-Differential-Privacy則沒(méi)有明顯變化.對(duì)于MobiHide模型，實(shí)驗(yàn)結(jié)果表明，當(dāng)用戶的查詢次數(shù)累積到一定數(shù)量之后，隱私泄露概率隨查詢次數(shù)的增加而明顯增加，可見，位置K-匿名算法無(wú)法有效保護(hù)軌跡隱私.

目前，統(tǒng)計(jì)推理攻擊的時(shí)間跨度遠(yuǎn)遠(yuǎn)大于24小時(shí)[35]，基于Geo-Indistinguishability的軌跡隱私保護(hù)算法僅能在24小時(shí)內(nèi)有效保護(hù)用戶隱私，當(dāng)用戶長(zhǎng)時(shí)間查詢數(shù)據(jù)時(shí)，攻擊者很容易獲得用戶的軌跡隱私信息.本文的K-Differential-Privacy軌跡隱私保護(hù)模型能夠在查詢累積時(shí)長(zhǎng)超過(guò)24小時(shí)的情況下保證軌跡隱私保護(hù)效果.因此，對(duì)于累積查詢時(shí)長(zhǎng)較長(zhǎng)的用戶群，K-Differential-Privacy軌跡隱私保護(hù)模型具有更好的軌跡隱私保護(hù)效果.

5 總結(jié)與展望

針對(duì)LBS的軌跡隱私保護(hù)問(wèn)題，本文提出了一種基于拉普拉斯機(jī)制和匿名組的LBS軌跡隱私保護(hù)算法NAGDP.同時(shí)，為了加快LBS請(qǐng)求服務(wù)的響應(yīng)速度，本文引入了基于差分隱私軌跡隱私保護(hù)的用戶定位算法UTPP.二者共同構(gòu)成軌跡隱私保護(hù)模型K-Differential-Privacy.該模型對(duì)LBS用戶的真實(shí)位置進(jìn)行多輪加噪，以獲取匿名組，并以匿名組的名義請(qǐng)求LBS服務(wù)，克服了差分隱私在軌跡隱私保護(hù)中的隱私預(yù)算過(guò)度依賴問(wèn)題，提升了軌跡隱私保護(hù)效果.

目前，基于差分隱私的LBS軌跡隱私保護(hù)的相關(guān)研究仍處于起步階段.盡管差分隱私無(wú)視攻擊者背景知識(shí)的特點(diǎn)彌補(bǔ)了K-匿名在該方面的缺陷，但現(xiàn)有模型僅是基于位置的拉普拉斯加噪機(jī)制的擴(kuò)展.應(yīng)用范圍更廣、隱私保護(hù)效果更好的軌跡隱私保護(hù)模型仍有待研究.其次，由于本文的定位算法引入了新的組策略，因此，組策略對(duì)劃分集群閾值的影響仍有待進(jìn)一步研究.