朱素霞，劉抒倫，孫廣路

（哈爾濱理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150080）

1 引言

隨著智能手機(jī)和5G 網(wǎng)絡(luò)的普及，移動(dòng)設(shè)備可以運(yùn)行更復(fù)雜的程序，并以更快的速度、更低的時(shí)延傳輸信息，這為物聯(lián)網(wǎng)的發(fā)展提供了堅(jiān)實(shí)的基礎(chǔ)。物聯(lián)網(wǎng)中基于位置的服務(wù)（LBS,location-based service）[1-2]從僅應(yīng)用于導(dǎo)航類軟件，到逐漸應(yīng)用于社交、游戲等產(chǎn)品，目前已應(yīng)用于越來越多的領(lǐng)域。由于LBS 要求用戶將位置數(shù)據(jù)提供給相應(yīng)的服務(wù)提供商或第三方數(shù)據(jù)提供者，因此如何保護(hù)用戶的位置隱私成為LBS 的主要關(guān)注點(diǎn)[3]。數(shù)據(jù)在向服務(wù)商提交的過程中涉及網(wǎng)絡(luò)傳輸、數(shù)據(jù)采集等多重隱私泄露風(fēng)險(xiǎn)，用戶的隱私信息可能會(huì)隨著軌跡數(shù)據(jù)的發(fā)布而被泄露。軌跡隱私信息一旦暴露，用戶將遭受的最大威脅便是敏感位置泄露，這可能導(dǎo)致攻擊者獲取用戶的真實(shí)地理信息，并根據(jù)背景知識(shí)推測出用戶地理軌跡，進(jìn)一步獲得興趣愛好、行為習(xí)慣等重要用戶隱私信息。文獻(xiàn)[4]中記載了30 個(gè)基于位置應(yīng)用中有15 個(gè)應(yīng)用[5]泄露用戶的位置信息給攻擊者或分析服務(wù)器。文獻(xiàn)[6]表明MySpace 有3.6 億用戶信息被泄露。文獻(xiàn)[7]使用基于Twitter 社交網(wǎng)絡(luò)應(yīng)用數(shù)據(jù)分析了用戶的敏感信息，如工作單位的具體位置等。因此，敏感位置信息的泄露可能會(huì)使用戶處于不利的地位。

近幾年，許多位置隱私保護(hù)機(jī)制被提出[8-9]，用于解決LBS 或持續(xù)的位置共享，而差分隱私因其具有嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)基礎(chǔ)，并嚴(yán)格定義了攻擊者的背景知識(shí)，在軌跡保護(hù)研究領(lǐng)域受到了廣泛的關(guān)注。但是，現(xiàn)有基于差分隱私的軌跡保護(hù)機(jī)制存在以下2 個(gè)問題。

1)現(xiàn)有連續(xù)軌跡保護(hù)機(jī)制可以保證軌跡的隱私性，但是大部分沒有考慮不同位置因敏感度不同而需要不同的隱私預(yù)算。對(duì)軌跡中的不同位置分配相同的隱私預(yù)算，會(huì)導(dǎo)致隱私預(yù)算的浪費(fèi)。例如，對(duì)不需要高強(qiáng)度保護(hù)的位置點(diǎn)分配了高強(qiáng)度保護(hù)對(duì)應(yīng)的隱私預(yù)算，使該位置點(diǎn)被過度保護(hù)。使用相同的隱私預(yù)算對(duì)位置點(diǎn)進(jìn)行保護(hù)，還會(huì)導(dǎo)致軌跡的可用性變差。例如，在不需要高強(qiáng)度保護(hù)的位置點(diǎn)進(jìn)行高強(qiáng)度保護(hù)，因此分配給該位置點(diǎn)的隱私預(yù)算較小，使該位置點(diǎn)的噪聲較大，從而導(dǎo)致軌跡的可用性變差。

2)大部分現(xiàn)有的隱私保護(hù)方法只考慮了軌跡的時(shí)間和空間對(duì)軌跡可用性的影響，忽略了軌跡的相似性對(duì)軌跡可用性的影響[10]。圖1 中有3 條軌跡，分別為真實(shí)軌跡、干擾軌跡1 和干擾軌跡2，每條軌跡由4 個(gè)位置點(diǎn)組成。干擾軌跡1 和干擾軌跡2中的各個(gè)干擾位置到其對(duì)應(yīng)的真實(shí)位置的距離都相同。干擾軌跡1 穿過了真實(shí)軌跡，形成了與干擾軌跡2 完全不同的干擾軌跡。當(dāng)LBS 中用戶發(fā)布的位置和干擾軌跡1 類似時(shí)，干擾軌跡就會(huì)不斷穿過真實(shí)軌跡，這會(huì)對(duì)軌跡的可用性和真實(shí)性造成嚴(yán)重影響。在真實(shí)位置的隱私預(yù)算較小的前提下，干擾位置與真實(shí)位置距離較遠(yuǎn)，會(huì)出現(xiàn)該干擾點(diǎn)特別突出的情況。攻擊者可以對(duì)軌跡數(shù)據(jù)采用噪聲濾波等手段過濾異常軌跡、恢復(fù)真實(shí)位置，導(dǎo)致保護(hù)失效。如果用戶發(fā)布的位置類似于干擾軌跡2，即使隱私預(yù)算較小，也會(huì)盡量使干擾軌跡與真實(shí)軌跡形狀相似，不會(huì)使該干擾點(diǎn)被過濾掉而導(dǎo)致保護(hù)失效。

圖1 條軌跡間形狀的對(duì)比

針對(duì)上述兩點(diǎn)問題，本文首先利用相對(duì)熵設(shè)計(jì)了一種位置敏感的隱私級(jí)別實(shí)時(shí)計(jì)算算法，根據(jù)發(fā)布位置的敏感度的不同，為不同敏感度的位置實(shí)時(shí)分配隱私級(jí)別；其次，將該隱私級(jí)別實(shí)時(shí)計(jì)算算法與本地化差分隱私相結(jié)合，建立σ?隱私模型；最后，提出了基于K-means 的形狀相似差分隱私（DPKTS,differential privacy based onK-means shape similarity）軌跡保護(hù)機(jī)制，該機(jī)制在保證各個(gè)發(fā)布位置隱私性的前提下，通過聚簇與提高軌跡形狀相似性，獲得更好的軌跡可用性。

2 相關(guān)工作

針對(duì)LBS 中的敏感位置信息，研究者已經(jīng)提出了很多隱私保護(hù)方法，依據(jù)采用的核心思想可將其大致分為4 類，即泛化、混合區(qū)、抑制和擾亂[11]。其中，泛化是將原始軌跡上的敏感位置替換成一個(gè)區(qū)域，從而起到保護(hù)位置隱私的目的。k?匿名是一種最常用的泛化手段，它將真實(shí)位置信息替換成至少包含k個(gè)用戶的空間區(qū)域。文獻(xiàn)[12]提出了一種雙k機(jī)制，通過將k個(gè)查詢位置發(fā)送到不同的匿名器以實(shí)現(xiàn)k?匿名。文獻(xiàn)[13]在k?匿名的基礎(chǔ)上針對(duì)敏感的數(shù)據(jù)集提出了一種改進(jìn)的K-means 算法?；旌蠀^(qū)是對(duì)軌跡中的某些位置用假名代替，以阻止用戶軌跡隨著時(shí)間變化的可追溯性，使攻擊者不能獲取用戶的真實(shí)位置信息。文獻(xiàn)[14]提出了一種基于用戶流的算法來估計(jì)圖中節(jié)點(diǎn)間的遷移率，并針對(duì)遷移率的攻擊方法，對(duì)傳統(tǒng)的混合區(qū)進(jìn)行了改進(jìn)。抑制是在發(fā)布位置時(shí)對(duì)某些敏感位置進(jìn)行屏蔽或時(shí)延等。文獻(xiàn)[15]提出了2 種基于頻次的軌跡發(fā)布方法，分別通過抑制整個(gè)缺陷軌跡和特定的局部抑制實(shí)現(xiàn)隱私保護(hù)。擾亂即位置擾動(dòng)，它將各個(gè)時(shí)間點(diǎn)的真實(shí)位置通過替換或添加噪聲等方式生成假的位置，以隱藏用戶的真實(shí)位置，是一種被廣泛應(yīng)用的位置隱私保護(hù)機(jī)制。文獻(xiàn)[16]提出了一種動(dòng)態(tài)假名方案，用于構(gòu)造移動(dòng)用戶的備用可能路徑以保護(hù)其位置隱私。文獻(xiàn)[17]提出了一種新穎的基于擾動(dòng)的方案，即使在顯示用戶身份時(shí)也可以保護(hù)連續(xù)LBS 的查詢隱私。

滿足差分隱私的位置擾動(dòng)方法研究逐漸成為軌跡數(shù)據(jù)隱私保護(hù)的熱點(diǎn)。差分隱私概念由Dwork等[18-19]于2006 年提出，通過添加少量高斯或指數(shù)分布的隨機(jī)噪聲來擾動(dòng)數(shù)據(jù)庫查詢的真實(shí)答案，從而保護(hù)隱私。其主要思想是降低數(shù)據(jù)集中添加或刪除某一條數(shù)據(jù)對(duì)查詢結(jié)果的影響，從而讓攻擊者很難通過多次查詢推理數(shù)據(jù)集中的某條真實(shí)數(shù)據(jù)，即假設(shè)攻擊者能夠獲得除目標(biāo)記錄外所有其他記錄的最大背景知識(shí)。在此假設(shè)下，差分隱私對(duì)基于各種背景知識(shí)的攻擊具有很好的保護(hù)效果，因?yàn)檫@些背景知識(shí)不可能提供比最大背景知識(shí)更豐富的信息。差分隱私可大致分為以下2 類[19-22]：中心化差分隱私和本地化差分隱私。中心化差分隱私將原始數(shù)據(jù)集中到一個(gè)數(shù)據(jù)中心，然后發(fā)布滿足差分隱私的相關(guān)統(tǒng)計(jì)信息，因此中心化差分隱私對(duì)敏感信息的保護(hù)始終基于一個(gè)前提，即可信的第三方數(shù)據(jù)收集者，保證第三方數(shù)據(jù)收集者不會(huì)竊取或泄露用戶的敏感信息。但是，在實(shí)際應(yīng)用中，無法找到絕對(duì)安全的第三方數(shù)據(jù)收集者。本地化差分隱私是將數(shù)據(jù)的隱私化處理過程轉(zhuǎn)移到每個(gè)用戶上，使用戶能夠單獨(dú)地處理和保護(hù)個(gè)人敏感信息?；诒镜鼗罘蛛[私的軌跡數(shù)據(jù)隱私保護(hù)大致可以分為2 個(gè)方面：歷史數(shù)據(jù)的發(fā)布[23-28]和實(shí)時(shí)位置數(shù)據(jù)的發(fā)布[29-30]。實(shí)時(shí)位置數(shù)據(jù)的發(fā)布機(jī)制因其可以應(yīng)用于各種基于位置服務(wù)的商業(yè)軟件，從而有較高的應(yīng)用價(jià)值和研究價(jià)值。

文獻(xiàn)[29]基于差分隱私的Geo-Indistinguishability機(jī)制，提出一種可以使隱私級(jí)別適應(yīng)于多種區(qū)域的方法。文獻(xiàn)[31]將差分隱私保護(hù)的發(fā)布機(jī)制利用線性規(guī)劃技術(shù)進(jìn)行優(yōu)化，提出了一種滿足地理不可分辨性的δ-spanner 解決方案。文獻(xiàn)[30]利用馬爾可夫鏈表示軌跡上各個(gè)位置點(diǎn)的時(shí)序關(guān)系，重新定義了相鄰數(shù)據(jù)集這個(gè)概念，提出一種基于敏感度外殼的差分隱私位置發(fā)布機(jī)制。文獻(xiàn)[32]為了解決當(dāng)前發(fā)布位置對(duì)以前真實(shí)位置的影響，提出了一種基于時(shí)空相關(guān)性的差分隱私軌跡保護(hù)機(jī)制。文獻(xiàn)[33]通過對(duì)軌跡上敏感位置點(diǎn)及其附屬敏感點(diǎn)的保護(hù)，并結(jié)合用戶軌跡位置的敏感度和用戶隱私保護(hù)的要求和隱私預(yù)算，提出了一種基于互相約束的個(gè)性化差分隱私保護(hù)方法。文獻(xiàn)[34]設(shè)計(jì)了一種基于霧計(jì)算和k?匿名的軌跡保護(hù)方案，用于連續(xù)查詢中的實(shí)時(shí)軌跡隱私保護(hù)和軌跡發(fā)布中的離線軌跡數(shù)據(jù)保護(hù)。

然而，現(xiàn)有的實(shí)時(shí)差分隱私位置發(fā)布機(jī)制大部分僅保證了軌跡的隱私性，并沒有針對(duì)不同敏感度的位置分配不同的隱私預(yù)算，且沒有考慮發(fā)布位置形成的軌跡形狀，造成軌跡可用性變差。

3 預(yù)備知識(shí)

表1 總結(jié)了本文的常用符號(hào)。

3.1 發(fā)布位置定義

為了獲得狀態(tài)概率轉(zhuǎn)移矩陣，需要將軌跡GPS坐標(biāo)轉(zhuǎn)換為不同時(shí)刻的狀態(tài)，而將GPS 坐標(biāo)轉(zhuǎn)換為狀態(tài)，需要先形成坐標(biāo)系。將地理形狀按照同比例形式放入直角坐標(biāo)系，并將軌跡的經(jīng)/緯度位置坐標(biāo)轉(zhuǎn)化為直角坐標(biāo)系內(nèi)坐標(biāo)。將地圖劃分成網(wǎng)格后，通過統(tǒng)計(jì)歷史軌跡數(shù)據(jù)可以得到概率轉(zhuǎn)移矩陣。根據(jù)文獻(xiàn)[30,32]中的網(wǎng)格劃分方法，本文將網(wǎng)格設(shè)置為長寬均為0.34 km 的正方形，網(wǎng)格中的位置的編號(hào)格式如圖2 所示。整個(gè)坐標(biāo)系的編號(hào)規(guī)則為：從左到右依次遞增，從下到上依次遞增。

圖2 位置發(fā)布時(shí)的地圖定義

3.2 差分隱私

差分隱私是對(duì)原始數(shù)據(jù)或原始數(shù)據(jù)查詢結(jié)果添加隨機(jī)噪聲，使最終結(jié)果與真實(shí)結(jié)果盡可能相像，且最大限度地減少識(shí)別其記錄的機(jī)會(huì)。差分隱私中使用了相鄰數(shù)據(jù)集的概念：如果結(jié)構(gòu)相同的2 個(gè)數(shù)據(jù)集D和D'有且僅有一條數(shù)據(jù)不同，那么這2 個(gè)數(shù)據(jù)集被稱為相鄰數(shù)據(jù)集。下面，給出差分隱私的形式化定義。

定義1差分隱私[18-19]。給定相鄰數(shù)據(jù)集D和D'及在D和D'上的一個(gè)算法A，若算法A在D和D'上的任意輸出結(jié)果O滿足式(1)，則說明算法A滿足差分隱私。

其中，參數(shù)εt是t時(shí)刻的差分隱私預(yù)算，表示t時(shí)刻的隱私保護(hù)程度。εt越大，說明t時(shí)刻的隱私保護(hù)程度越低；當(dāng)εt趨近于0 時(shí)，則說明t時(shí)刻算法A在相鄰數(shù)據(jù)集D和D′上輸出結(jié)果相差不多，此時(shí)算法A不會(huì)泄露數(shù)據(jù)集中任何數(shù)據(jù)的敏感信息。

然而，軌跡數(shù)據(jù)中每一時(shí)刻的位置信息均可能屬于敏感信息，因此軌跡數(shù)據(jù)隱私中并不存在傳統(tǒng)的相鄰數(shù)據(jù)集概念。本文借鑒文獻(xiàn)[20-21,30]中對(duì)軌跡隱私保護(hù)中差分隱私的定義，即已知t時(shí)刻的發(fā)布位置為ot，根據(jù)發(fā)布位置，推斷當(dāng)前時(shí)刻真實(shí)位置的后驗(yàn)概率Pr(tlt|ot)除以當(dāng)前時(shí)刻真實(shí)位置的先驗(yàn)概率Pr(tlt)的值滿足差分隱私定義，描述為

其中，εt是t時(shí)刻真實(shí)位置所在區(qū)域的差分隱私預(yù)算。因此發(fā)布位置ot是經(jīng)過隱私化處理的數(shù)據(jù)，滿足本地化差分隱私的概念，即由用戶進(jìn)行隱私化處理。

若設(shè)定的隱私保護(hù)預(yù)算為ε，實(shí)際保護(hù)后的隱私保護(hù)預(yù)算為ε'，若ε＜ε′，則實(shí)際的隱私保護(hù)強(qiáng)度小于設(shè)定的隱私保護(hù)強(qiáng)度。

3.3 信息熵及相對(duì)熵

信息熵是系統(tǒng)對(duì)信息量的期望，信息量是對(duì)信息的度量，而信息量與具體發(fā)生的事件有關(guān)。信息量的大小與隨機(jī)事件的概率有關(guān)，概率越小的事件發(fā)生后產(chǎn)生的信息量越大，概率越大的事件發(fā)生后產(chǎn)生的信息量越小。信息量定義為

其中，p(x)為事件發(fā)生的概率，負(fù)號(hào)是為了保證信息量大于或等于0。

信息量用于度量一個(gè)隨機(jī)事件發(fā)生后所帶來的信息，而信息熵則是在結(jié)果產(chǎn)生之前對(duì)可能產(chǎn)生的信息量的期望，即考慮該隨機(jī)變量的所有可能取值。信息熵也常用來衡量一個(gè)系統(tǒng)的復(fù)雜程度，系統(tǒng)越復(fù)雜，信息熵越大；反之，一個(gè)系統(tǒng)越簡單，可能出現(xiàn)的情況種類越少，則信息熵越小。信息熵定義為

其中，p(xi)為事件發(fā)生的概率，與信息量的計(jì)算式相同，信息熵計(jì)算式中的負(fù)號(hào)也是為了保證信息熵大于或等于0。與信息熵不同，相對(duì)熵是用來衡量2 個(gè)概率分布之間的差異，又稱為 KL 散度（Kullback-Leibler divergence），定義為

根據(jù)式(5)可知，相對(duì)熵具有如下性質(zhì)。

1)如果2 個(gè)分布p(xi)和q(xi)相同，那么相對(duì)熵等于0。

2)不對(duì)稱性，即DKL(p||q)≠DKL(q||p)。

3)DKL(p||q)≥0。

根據(jù)相對(duì)熵的性質(zhì)可知，只有當(dāng)p(xi)=q(xi)時(shí)，其值為0。若p(xi)和q(xi)略有差異，其值就會(huì)大于0，因此相對(duì)熵的值越小，則表明2 個(gè)概率分布之間的差異越小。

4 軌跡形狀相似性與軌跡可用性

為了描述2 條軌跡在視覺上的相似度，本文通過Fréchet 距離來衡量2 條軌跡的形狀相似性。Fréchet 距離最早由Fréchet 提出，隨后由Alt 等[35]給出了計(jì)算方法。如前文所述，大多數(shù)位置發(fā)布機(jī)制沒有考慮軌跡形狀對(duì)于軌跡可用性的影響，因此為了提高軌跡的可用性，本文從軌跡形狀相似性方面進(jìn)行優(yōu)化，通過計(jì)算Fréchet 距離衡量2 條軌跡之間的相似度，F(xiàn)réchet 距離越小，2 條軌跡之間越相似；反之，2 條軌跡之間越不相似。Fréchet 距離離散化的表示形式為

其中，A和B分別為2 條曲線，t為時(shí)間點(diǎn)，A(α(t))、B(β(t))分別為曲線上A和B在t時(shí)刻的采樣點(diǎn)，d(A(α(t)),B(β(t)))為2 個(gè)采樣點(diǎn)之間的歐氏距離。在每次采樣中，t離散地遍歷區(qū)間[0,1]，得到該種采樣下的最大距離max{d(A(α(t)),B(β(t)))}。離散Fréchet距離是連續(xù)Fréchet 距離的近似，當(dāng)曲線選取的離散點(diǎn)足夠多時(shí)，則近似等于連續(xù)Fréchet 距離。

假設(shè)某時(shí)刻可能的發(fā)布位置為ot，真實(shí)位置為zt，則本文將這2 個(gè)位置之間的距離作為誤差評(píng)價(jià)，可以描述為

如果發(fā)布位置與真實(shí)位置距離誤差為零，則說明2 個(gè)位置點(diǎn)重合，即發(fā)布位置與真實(shí)位置重合；反之則說明發(fā)布位置與真實(shí)位置不重合。

特別地，對(duì)于長度為n的軌跡，同樣以距離誤差[27,36]為基礎(chǔ)定義軌跡可用性，如式(7)所示，距離誤差TA 為發(fā)布位置與真實(shí)位置的均方根誤差之和，可以描述為

對(duì)某條發(fā)布軌跡而言，其距離誤差TA 越大，說明其與真實(shí)軌跡重合度越低，從而其可用性也就越差。因此，可以通過計(jì)算發(fā)布軌跡的距離誤差來判斷軌跡的可用性。

通過計(jì)算Fréchet 距離衡量發(fā)布軌跡和真實(shí)軌跡的形狀相似度，通過距離誤差計(jì)算發(fā)布軌跡的可用性，發(fā)布軌跡與真實(shí)軌跡間的形狀相似度越大，距離誤差就會(huì)越小，則發(fā)布軌跡的可用性就會(huì)越高。

5 σ?隱私模型

對(duì)于差分隱私位置擾亂算法，為不同位置分配相同的隱私預(yù)算并不合理，一方面會(huì)造成隱私預(yù)算的浪費(fèi)，另一方面會(huì)造成位置節(jié)點(diǎn)的可用性變差。根據(jù)差分隱私的定義，隱私預(yù)算越少，保護(hù)強(qiáng)度越大，因此應(yīng)為敏感位置分配較少的隱私預(yù)算，為不敏感位置分配較多的隱私預(yù)算。根據(jù)不同位置點(diǎn)與理想狀態(tài)的相對(duì)熵得到不同的敏感度，而不同的敏感度需要不同的隱私級(jí)別，本文提出了一個(gè)位置敏感的隱私級(jí)別實(shí)時(shí)計(jì)算算法，并將其與隱私預(yù)算結(jié)合，建立σ?隱私模型。

5.1 發(fā)布位置集合

通過對(duì)數(shù)據(jù)集中歷史軌跡進(jìn)行統(tǒng)計(jì)，并根據(jù)前文提到的發(fā)布位置定義，將GPS 數(shù)據(jù)與地圖中預(yù)設(shè)的格子對(duì)應(yīng)起來，得到狀態(tài)轉(zhuǎn)移矩陣。由于一個(gè)系統(tǒng)的某些因素在轉(zhuǎn)移中的第n次結(jié)果只受第n?1 次的結(jié)果影響，即只與當(dāng)前所處狀態(tài)有關(guān)，而與過去狀態(tài)無關(guān)。因此可以根據(jù)狀態(tài)轉(zhuǎn)移矩陣，在當(dāng)前時(shí)刻推測下一時(shí)刻可能位置的集合PRN，并對(duì)PRN 進(jìn)行擴(kuò)充，擴(kuò)充規(guī)則為：以PRN 中的點(diǎn)形成凸包，求出凸包的中心點(diǎn)，以該中心點(diǎn)為圓心，通過控制半徑的大小來擴(kuò)充整個(gè)集合，判斷某一點(diǎn)是否屬于可能發(fā)布位置的集合中。判斷規(guī)則為

其中，p表示要判斷的點(diǎn)，PRN.cfc 表示集合PRN的凸包的中心點(diǎn)，dis(a,b)表示a 點(diǎn)與b 點(diǎn)間的距離，r.length 表示圓的半徑，p.ic 表示判斷結(jié)果，只有p.ic=?1 時(shí)，該點(diǎn)才為集合中的點(diǎn)。擴(kuò)充規(guī)則可以簡化為：以集合PRN 的凸包的中心點(diǎn)為圓心，選定一個(gè)值為半徑，圓內(nèi)的點(diǎn)的并集。半徑的值越大，集合越大。擴(kuò)充后的集合為PRNN={pr1,…,prm}。

擴(kuò)充規(guī)則具體如圖3 所示。

圖3 中灰色的區(qū)域?yàn)榭赡馨l(fā)布的位置區(qū)域，如上述規(guī)則所示，如果發(fā)布位置的中心與圓心距離大于圓的半徑，則該位置不能被擴(kuò)充到集合中。圖3中，位置a 的中心與圓心的距離大于圓的半徑，則位置a 不屬于可發(fā)布位置集合中，虛線為圓心到位置的距離，加粗的線為圓的半徑。

圖3 擴(kuò)充規(guī)則

5.2 隱私級(jí)別計(jì)算

如果歷史數(shù)據(jù)被敵手獲得，敵手可以推測出狀態(tài)轉(zhuǎn)移矩陣，進(jìn)而可以根據(jù)狀態(tài)轉(zhuǎn)移矩陣得到下一時(shí)刻可能存在位置的集合PRN，并根據(jù)PRN 大概率得到下一時(shí)刻的位置節(jié)點(diǎn)，因此本文采用信息熵來衡量敵手獲得可能存在位置集合后能獲得多少信息，并根據(jù)敵手獲得的信息量設(shè)定不同的敏感度。首先設(shè)定一個(gè)理想狀態(tài)，在該狀態(tài)下即使被敵手獲得可能存在位置集合，也無法大概率得到下一時(shí)刻的位置節(jié)點(diǎn)。

理想狀態(tài)具體解釋如下。假設(shè)有2 個(gè)路口R 和S，路口R 和S 分別有2 條岔路，其中旅行者在路口R去往每條岔路的概率為(1/2,1/2)，在路口S 去往每條岔路的概率為(1/4,3/4)，由于信息熵是對(duì)“不確定現(xiàn)象”的數(shù)學(xué)化度量，旅行者在路口S 與在路口R 相比，顯然在路口R 的選擇更加不確定，而在路口S則大概率會(huì)去往第二條岔路，因此，如果去往各個(gè)岔路的概率是平均分布的概率分布，則岔路口的去向具有更大的不確定性。因此本文中提到的理想狀態(tài)是一個(gè)大小與集合PRNN 相同，且每一個(gè)位置點(diǎn)的概率都為1/m的位置點(diǎn)的集合，因?yàn)檫@種理想狀態(tài)具有比PRNN 的概率分布更大的不確定性。

本文采用相對(duì)熵描述集合PRNN與理想狀態(tài)的概率分布差異，并以相對(duì)熵與理想狀態(tài)的信息熵的比值作為真實(shí)位置點(diǎn)的敏感度，可以描述為

其中，r(xi)為理想狀態(tài)中某一個(gè)事件的概率，p(xi)為PRNN 中某一個(gè)事件的概率，q(xi)為PRNN 中的某一個(gè)事件在理想狀態(tài)中對(duì)應(yīng)事件的概率。式(9)中分母為理想事件概率分布的信息熵；分子為相對(duì)熵，對(duì)應(yīng)理想事件與實(shí)際事件概率分布的信息熵的差值。因此，敏感度S表示實(shí)際事件距離理想事件所需信息熵占理想事件信息熵的比值。

根據(jù)敏感度確定PRNN 中各個(gè)點(diǎn)的隱私級(jí)別，規(guī)則如下。確定PRNN 中的點(diǎn)k是否屬于PRN，如果k點(diǎn)不屬于PRN，則k點(diǎn)的隱私級(jí)別為s/m；如果k點(diǎn)屬于PRN，則該點(diǎn)的隱私級(jí)別為(1?S)k.pr，k.pr 為k點(diǎn)對(duì)應(yīng)狀態(tài)轉(zhuǎn)移矩陣中的值。上述規(guī)則可以總結(jié)為，對(duì)于屬于PRN 的點(diǎn)，分配較高的隱私級(jí)別；對(duì)于不屬于PRN 的點(diǎn)，分配較低的隱私級(jí)別。因?yàn)镻RN 中的點(diǎn)是下一時(shí)刻大概率會(huì)出現(xiàn)的位置，所以對(duì)于大概率出現(xiàn)的位置應(yīng)分配更高的隱私等級(jí)，對(duì)于下一時(shí)刻小概率出現(xiàn)的位置，應(yīng)分配更低的隱私等級(jí)。

位置敏感的隱私級(jí)別實(shí)時(shí)計(jì)算算法如算法1所示。

5.3 建立差分隱私模型

在本地差分隱私預(yù)算基礎(chǔ)上，結(jié)合位置敏感的隱私級(jí)別實(shí)時(shí)計(jì)算算法，本文提出了σ?隱私模型。

定義2位置σ?隱私。如果一個(gè)發(fā)布位置能夠滿足σ?隱私，則該點(diǎn)的差分隱私預(yù)算ε和隱私級(jí)別pl 滿足

由式(10)可知，在σ相同的情況下，隱私級(jí)別pl 越大，則為該位置分配的隱私預(yù)算ε越小。根據(jù)差分隱私的原理可知，一個(gè)位置的隱私級(jí)別越大，其保護(hù)強(qiáng)度就會(huì)越大；反之，保護(hù)強(qiáng)度越小。當(dāng)pl=1 時(shí)，ε=σ。由于本文算法是實(shí)時(shí)分配可能發(fā)布位置的隱私級(jí)別，發(fā)布位置之前要計(jì)算可能發(fā)布位置集合中各個(gè)位置的隱私級(jí)別，因此隱私模型不能太復(fù)雜，以免使算法的時(shí)間復(fù)雜度過高。

6 基于K-means 的形狀相似差分隱私軌跡保護(hù)機(jī)制

為了解決連續(xù)軌跡隱私保護(hù)機(jī)制軌跡可用性較差的問題，本文提出了一種基于K-means 的形狀相似差分隱私軌跡保護(hù)機(jī)制。該機(jī)制首先要保證軌跡中每個(gè)發(fā)布位置的隱私性，其次通過K-means 算法使發(fā)布軌跡的方向與真實(shí)軌跡相似，優(yōu)化軌跡形狀相似性，提高軌跡的可用性。

6.1 隱私預(yù)算

根據(jù)軌跡數(shù)據(jù)中差分隱私的定義，隱私預(yù)算是發(fā)布位置的后驗(yàn)概率與先驗(yàn)概率的比值，而發(fā)布位置的先驗(yàn)概率和后驗(yàn)概率都需要通過馬爾可夫概率轉(zhuǎn)移矩陣得到。下面，說明如何獲得馬爾可夫概率轉(zhuǎn)移矩陣。

本文使用一階馬爾可夫鏈模擬用戶真實(shí)位置之間的相關(guān)性，并通過統(tǒng)計(jì)用戶的歷史記錄得到狀態(tài)轉(zhuǎn)移矩陣M。M是一個(gè)二維矩陣，矩陣中的元素mij表示用戶從第i個(gè)區(qū)域轉(zhuǎn)移到第j個(gè)區(qū)域的概率。

假設(shè)用戶真實(shí)位置區(qū)域集合為TL={tl1,…,tlt}，利用差分隱私位置發(fā)布機(jī)制處理后，生成的擾亂區(qū)域集合為DL={dl1,…,dlt}。利用馬爾可夫狀態(tài)轉(zhuǎn)移概率矩陣M，結(jié)合本文提出的位置敏感的差分隱私位置發(fā)布機(jī)制，對(duì)t時(shí)刻存在的位置進(jìn)行推測，并構(gòu)建t時(shí)刻的真實(shí)位置可能發(fā)布的集合PL={pl1t,和每個(gè)位置的先驗(yàn)概率值的集合其中，n為集合中元素的個(gè)數(shù)。當(dāng)t時(shí)刻的擾亂位置dlt發(fā)布后，就可以根據(jù)此擾亂位置推測出t時(shí)刻的真實(shí)位置tlt，即發(fā)布位置的后驗(yàn)概率Pr(tlt|dlt)，并將各個(gè)時(shí)刻的后驗(yàn)概率形成集合為計(jì)算后驗(yàn)概率，考慮如何求得t時(shí)刻的差分隱私位置發(fā)布概率矩陣Rt。設(shè)t時(shí)刻發(fā)布的位置區(qū)域集合為PRNN={pr1,…,prm}。矩陣Rt是一個(gè)維度為n×m的矩陣，元素為t時(shí)刻真實(shí)區(qū)域到發(fā)布的擾亂區(qū)域?yàn)榈母怕手?。則位置的后驗(yàn)概率為

通過式(11)，可以得到每個(gè)區(qū)域位置的后驗(yàn)概率，進(jìn)而得到每個(gè)位置的隱私預(yù)算，并判斷該區(qū)域的隱私預(yù)算是否小于預(yù)設(shè)的預(yù)算。本文將各個(gè)區(qū)域的隱私預(yù)算形成一個(gè)隱私預(yù)算集合ept={ep1t,…,epmt}。

6.2 位置發(fā)布算法描述

為了使發(fā)布軌跡與真實(shí)軌跡方向盡可能一致，首先利用K-means 算法，對(duì)PRNN 中的位置點(diǎn)進(jìn)行聚類，選擇與真實(shí)軌跡方向最相近的簇為備選集合；然后對(duì)備選集合內(nèi)的位置點(diǎn)根據(jù)式(6)計(jì)算t時(shí)刻與t?1 時(shí)刻真實(shí)位置的軌跡與發(fā)布位置的軌跡的Fréchet 距 離，并 形 成 Fréchet 距 離 集 合frt={fr1t,…,frmt}；最后選擇符合隱私預(yù)算且Fréchet距離最小的位置點(diǎn)作為發(fā)布位置點(diǎn)。位置發(fā)布算法如算法2 所示。

算法2位置發(fā)布算法

輸入真實(shí)位置的轉(zhuǎn)移概率矩陣M，軌跡的隱私保護(hù)預(yù)算ε={ε1,…,εt}，圓的半徑r，t?1 時(shí)刻的真實(shí)位置tlt?1，t時(shí)刻的真實(shí)位置tlt，t?1 時(shí)刻的干擾位置dlt?1

6.3 算法分析

位置發(fā)布算法的運(yùn)算時(shí)間是對(duì)集合PRN 擴(kuò)展的時(shí)間、對(duì)集合PRNN 聚簇的時(shí)間以及運(yùn)算Fréchet距離的時(shí)間之和。其中，對(duì)PRN 擴(kuò)展的時(shí)間與理想狀態(tài)的大小有關(guān)，對(duì)PRNN 聚簇的時(shí)間與簇頭個(gè)數(shù)有關(guān)，運(yùn)算Fréchet 距離的時(shí)間與簇內(nèi)位置的個(gè)數(shù)有關(guān)。

在隱私和可用性方面，由于采用了滿足差分隱私的保護(hù)機(jī)制，并且引入了相對(duì)熵和K-means 算法，既可以使t時(shí)刻的發(fā)布位置滿足εt差分隱私，又能使發(fā)布軌跡與真實(shí)軌跡盡可能相似。因此，在保證隱私的前提下，算法選擇使發(fā)布軌跡與真實(shí)軌跡方向相似，且使軌跡形狀也相似的位置點(diǎn)作為發(fā)布位置，在滿足軌跡隱私性的前提下，通過軌跡形狀相似性提高了軌跡的可用性。

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

本文采用數(shù)據(jù)集Geolife 和Gowalla 對(duì)DPKTS進(jìn)行實(shí)驗(yàn)分析。Geolife 數(shù)據(jù)集包含182 個(gè)用戶于2007 年4 月到2012 年8 月在北京活動(dòng)的真實(shí)數(shù)據(jù)，一共有1 7621條軌跡。Gowalla數(shù)據(jù)集包含了15 116個(gè)用戶于2009 年2 月到2010 年10 月在加州范圍內(nèi)移動(dòng)社交網(wǎng)站上簽到的數(shù)據(jù)，共6 442 890 個(gè)簽到位置。對(duì)上述2 個(gè)數(shù)據(jù)集，抽取用戶編號(hào)、時(shí)間戳、經(jīng)度和緯度作為新的數(shù)據(jù)集。

實(shí)驗(yàn)的環(huán)境如下：Intel i7-9700K 3.6 GHz，16.00 GB 內(nèi)存，Microsoft Windows 10 操作系統(tǒng)，算法均在Pycharm2018 下實(shí)現(xiàn)。

對(duì)于DPKTS，本文主要分析隱私模型參數(shù)σ及簇頭個(gè)數(shù)對(duì)軌跡可用性的影響、理想狀態(tài)的大小對(duì)運(yùn)算時(shí)間的影響，以及簇頭個(gè)數(shù)對(duì)運(yùn)算時(shí)間的影響。在衡量σ對(duì)軌跡用性的影響時(shí)，本文將DPKTS 與PIM（planar isotropic mechanism）[30]和DPLRM（differentially private location release mechanism）[32]進(jìn)行對(duì)比。這2 種對(duì)比方法都是基于差分隱私的實(shí)時(shí)軌跡保護(hù)方法，且DPLRM 考慮了時(shí)序相關(guān)性。

首先，針對(duì)σ對(duì)發(fā)布軌跡可用性的影響進(jìn)行實(shí)驗(yàn)分析。在DPKTS 中，σ與傳統(tǒng)差分隱私中的隱私保護(hù)預(yù)算ε等價(jià)。如圖4 所示，DPKTS 的可用性較好，因?yàn)镈PKTS 對(duì)位置是敏感的，而不同位置的敏感度不同，所以針對(duì)不同位置設(shè)定不同隱私級(jí)別且通過K-means 算法得到與真實(shí)軌跡方向最相似的備選集合，并以軌跡形狀相似性為優(yōu)化目標(biāo)，從而提高了軌跡的可用性，所以DPKTS 的軌跡可用性明顯優(yōu)于其他方法。PIM 并沒有考慮軌跡的可用性，僅對(duì)發(fā)布位置做了基于差分隱私的處理，所以軌跡可用性一般。DPLRM 的軌跡可用性較PIM 略好，這是因?yàn)镈PLRM 在滿足差分隱私的同時(shí)，還對(duì)軌跡中的半馬爾可夫模型進(jìn)行優(yōu)化。但由于DPLRM沒有針對(duì)軌跡可用性進(jìn)行優(yōu)化，軌跡可用性比DPKTS 略差。不同方法在Geolife 數(shù)據(jù)集上的表現(xiàn)均優(yōu)于在 Gowalla 數(shù)據(jù)集的表現(xiàn)，這是因?yàn)镚eolife 數(shù)據(jù)集采樣頻率更高，細(xì)粒度更好，所以結(jié)果更精確。

圖4 σ 對(duì)軌跡可用性的影響

本文還分析了簇頭個(gè)數(shù)對(duì)軌跡可用性的影響，當(dāng)理想狀態(tài)數(shù)目為121、σ為1 時(shí)，分別計(jì)算不同簇頭數(shù)對(duì)于方法可用性的影響結(jié)果，如圖5 所示。隨著簇頭數(shù)的增加，軌跡可用性逐漸變差。這是因?yàn)殡S著簇頭數(shù)的增加，每個(gè)簇中可選擇的位置點(diǎn)變少，且DPKTS 選擇與真實(shí)軌跡方向最相似的簇，所以當(dāng)簇頭數(shù)增加時(shí)，簇內(nèi)位置點(diǎn)變少，軌跡可用性降低。

圖5 簇頭數(shù)對(duì)軌跡可用性的影響

圖6 展示了不同數(shù)據(jù)集上隱私保護(hù)強(qiáng)度的對(duì)比結(jié)果，其中橫坐標(biāo)為設(shè)定的隱私保護(hù)強(qiáng)度，縱坐標(biāo)為實(shí)際隱私保護(hù)強(qiáng)度，ε′值越小，說明保護(hù)強(qiáng)度越好。從圖6(a)可以看出，DPKTS 的隱私保護(hù)強(qiáng)度與PIM 的隱私保護(hù)強(qiáng)度接近，最壞的情況是在σ=0.4 時(shí)，此時(shí)也只比PIM 降低了約2.6%，這是因?yàn)镈PKTS 旨在提高軌跡可用性，而PIM旨在提高軌跡的保護(hù)強(qiáng)度，忽略了軌跡的可用性。與同樣旨在提高軌跡可用性的 DPLRM 相比，DPKTS 具有更好的隱私保護(hù)強(qiáng)度。當(dāng)σ=0.6 時(shí)，DPKTS 比DPLRM 的隱私保護(hù)強(qiáng)度提高了2.0%。在圖6(b)中，由于所使用的數(shù)據(jù)集時(shí)序相關(guān)性較弱，采樣率較低，使不同方法的隱私保護(hù)強(qiáng)度更接近，可以看出DPKTS 對(duì)時(shí)序相關(guān)更強(qiáng)的數(shù)據(jù)有更好的表現(xiàn)。

其次，分析理想狀態(tài)的大小對(duì)運(yùn)算時(shí)間的影響，實(shí)驗(yàn)中聚類時(shí)的簇頭數(shù)為3，結(jié)果如圖7 所示。從圖7 中可以看出，運(yùn)算時(shí)間與理想狀態(tài)的數(shù)目成正比，即理想狀態(tài)數(shù)目越多，運(yùn)算時(shí)間越多。這是因?yàn)槔硐霠顟B(tài)數(shù)目越多，計(jì)算位置點(diǎn)的敏感度所需要的時(shí)間越多，計(jì)算各個(gè)位置點(diǎn)的隱私級(jí)別所需要的時(shí)間越多，在聚類后，簇中節(jié)點(diǎn)數(shù)也會(huì)增加，所以理想狀態(tài)數(shù)目越多，運(yùn)算時(shí)間越長。

圖6 隱私保護(hù)強(qiáng)度

圖7 理想狀態(tài)數(shù)目對(duì)運(yùn)算時(shí)間的影響

最后，分析簇頭數(shù)對(duì)運(yùn)算時(shí)間的影響，結(jié)果如圖8 所示。實(shí)驗(yàn)中，分別以不同理想狀態(tài)大小進(jìn)行實(shí)驗(yàn)，并對(duì)不同理想狀態(tài)數(shù)目設(shè)定多組實(shí)驗(yàn)，以不同簇頭數(shù)進(jìn)行實(shí)驗(yàn)。由圖8 可知，當(dāng)理想狀態(tài)數(shù)目為121、簇頭數(shù)為1 時(shí)，運(yùn)算時(shí)間最少；當(dāng)理想狀態(tài)數(shù)目為441、簇頭數(shù)為2 時(shí)，運(yùn)算時(shí)間最少。每一種理想狀態(tài)下，都有可以使運(yùn)算時(shí)間最少的簇頭數(shù)，因此設(shè)定不同理想狀態(tài)數(shù)目時(shí)，需要選用不同的簇頭數(shù)，不能使用相同簇頭數(shù)。但是，當(dāng)理想狀態(tài)數(shù)目逐漸變多時(shí)，簇頭數(shù)也應(yīng)逐漸變多，才可使預(yù)算時(shí)間最小。

圖8 簇頭數(shù)對(duì)運(yùn)算時(shí)間的影響

8 結(jié)束語

針對(duì)位置服務(wù)中軌跡隱私保護(hù)問題，本文通過實(shí)時(shí)計(jì)算真實(shí)位置的相對(duì)熵衡量其敏感度，并根據(jù)敏感度為可能發(fā)布位置分配不同的隱私級(jí)別；通過結(jié)合節(jié)點(diǎn)隱私級(jí)別與差分隱私預(yù)算建立σ?隱私模型；利用K-means 獲得與真實(shí)軌跡方向一致的位置備選集合，使用Fréchet 距離來計(jì)算不同軌跡之間的相似程度，實(shí)現(xiàn)了一種基于形狀相似的K-means 差分隱私軌跡保護(hù)機(jī)制。實(shí)驗(yàn)結(jié)果表明，本文方法在保證軌跡隱私性的前提下，提高了軌跡的可用性。