基于差分隱私的軌跡隱私保護(hù)方案

陳思，付安民，蘇铓，孫懷江

（1.南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇 南京 210094；2.南京理工大學(xué)后勤服務(wù)中心，江蘇 南京 210094；3.中國科學(xué)院信息工程研究所，北京 100093）

1 引言

隨著物聯(lián)網(wǎng)、智能穿戴設(shè)備和全球定位系統(tǒng)（GPS,global positioning system）定位技術(shù)的快速發(fā)展，基于位置服務(wù)技術(shù)得到廣泛應(yīng)用，如移動(dòng)用戶通過終端來租借共享單車、查詢周邊的美食、享受外賣與線上打車服務(wù)等，這些基于位置的服務(wù)能夠使用戶獲取周邊的實(shí)時(shí)信息，并為其提供高質(zhì)量的生活方式。然而，軌跡數(shù)據(jù)具有隱私含義，因?yàn)樗銐蚓_，敵手可能由此得到用戶的住址、工作信息和個(gè)人生活習(xí)慣等隱私數(shù)據(jù)[1]。例如，一旦公共衛(wèi)生機(jī)構(gòu)公開發(fā)布用于流行病跟蹤的軌跡統(tǒng)計(jì)數(shù)據(jù)，這些敏感數(shù)據(jù)可能會(huì)在用戶不知情的情況下被保留或被攻擊者用于其他目的[2]；公共衛(wèi)生機(jī)構(gòu)利用軟件應(yīng)用獲取的位置數(shù)據(jù)進(jìn)行病毒傳播的追蹤，有利于預(yù)防和阻止疾病大流行，但是軌跡數(shù)據(jù)的公開發(fā)布和使用卻伴隨著一系列倫理和隱私問題，難以預(yù)防一些網(wǎng)絡(luò)攻擊者重復(fù)利用并竊取用戶隱私的事件發(fā)生[3]。因此，如何在保護(hù)用戶隱私的情況下使用軌跡數(shù)據(jù)是一個(gè)關(guān)鍵挑戰(zhàn)[4-5]。

目前，軌跡隱私保護(hù)的研究已經(jīng)具有一定的積累，其中k-匿名和差分隱私技術(shù)等被廣泛應(yīng)用在位置隱私保護(hù)領(lǐng)域[6]。k-匿名是最早被用于保護(hù)軌跡隱私的技術(shù)，操作簡(jiǎn)單。智能移動(dòng)設(shè)備與用戶綁定，例如，某些移動(dòng)應(yīng)用程序直接獲取用戶位置信息，而k-匿名方法要求某一用戶的位置記錄至少與其他k-1 個(gè)位置記錄不可區(qū)分，采用匿名方法進(jìn)行隱私保護(hù)，但是其需要基于一些特殊的攻擊假設(shè)，會(huì)增加服務(wù)器的負(fù)載和網(wǎng)絡(luò)傳輸開銷，影響位置服務(wù)質(zhì)量[7-8]。即使使用唯一標(biāo)識(shí)符而不是名稱，大多數(shù)用戶行為仍可被輕而易舉地追溯，因此差分隱私技術(shù)應(yīng)運(yùn)而生。差分隱私由Dwork 等[9-10]提出，通過嚴(yán)格的數(shù)學(xué)定義對(duì)發(fā)布數(shù)據(jù)進(jìn)行隨機(jī)擾動(dòng)，使在統(tǒng)計(jì)意義上攻擊者即使擁有一定的背景知識(shí)（如用戶的性別、郵政編碼等），也無法識(shí)別一條記錄（如ID、姓名等）是否在原數(shù)據(jù)表中，從而達(dá)到隱私保護(hù)目的。該技術(shù)優(yōu)點(diǎn)在于不需要特殊的攻擊假設(shè)、不關(guān)心攻擊者擁有的背景知識(shí)，同時(shí)給出了量化的分析來定義隱私泄露風(fēng)險(xiǎn)[11-13]。許多學(xué)者對(duì)差分隱私技術(shù)進(jìn)行了大量的研究與探討，根據(jù)不同場(chǎng)景下軌跡隱私保護(hù)需求提出眾多隱私保護(hù)方法[14-21]。

然而，現(xiàn)有軌跡隱私保護(hù)工作存在以下困難。1) 個(gè)人用戶精確的位置數(shù)據(jù)被利用在法律上是敏感的，那么機(jī)構(gòu)如何構(gòu)建高效采樣機(jī)制來收集用戶軌跡數(shù)據(jù)。2) 即使是群體聚合的軌跡數(shù)據(jù)也會(huì)有暴露隱私的風(fēng)險(xiǎn)，采用什么樣的軌跡數(shù)據(jù)擾動(dòng)混淆機(jī)制，可以有效抵抗具有背景知識(shí)的敵手攻擊。3) 如何高效地提高軌跡數(shù)據(jù)發(fā)布的統(tǒng)計(jì)精度，增強(qiáng)公開發(fā)布的軌跡數(shù)據(jù)的可用性?？傊?，目前并沒有克服上述所有困難的軌跡隱私保護(hù)方案。

因此，本文通過建立時(shí)間泛化和空間分割的軌跡數(shù)據(jù)處理模型，設(shè)計(jì)了一種基于差分隱私的軌跡隱私保護(hù)（TPPDP,trajectory privacy protection based on differential privacy）方案，不僅能夠增強(qiáng)軌跡數(shù)據(jù)的可用性，量化軌跡數(shù)據(jù)的隱私保護(hù)程度，還能有效抵抗基于一定背景知識(shí)的攻擊者的攻擊。本文的主要貢獻(xiàn)如下。

1) 現(xiàn)有軌跡隱私保護(hù)方案都是單獨(dú)采用一種差分隱私機(jī)制，TPPDP 使用差分隱私的指數(shù)機(jī)制和Laplace 機(jī)制進(jìn)行雙重?cái)?shù)據(jù)隨機(jī)擾動(dòng)，適用于空間分割、軌跡發(fā)布的不同階段，不僅可以量化隱私泄露的風(fēng)險(xiǎn)程度，在抵御具有一定背景知識(shí)的敵手攻擊的同時(shí)，安全性也比單獨(dú)使用一種機(jī)制大大提升。

2) 為了提高軌跡數(shù)據(jù)發(fā)布的查詢精度，響應(yīng)查詢范圍的誤差邊界，設(shè)計(jì)了一個(gè)有效的預(yù)判機(jī)制，減少異常軌跡數(shù)據(jù)發(fā)布的風(fēng)險(xiǎn)，在提高數(shù)據(jù)安全性的前提下，進(jìn)一步保證發(fā)布的公共衛(wèi)生軌跡數(shù)據(jù)的可用性。

3) 結(jié)合軌跡數(shù)據(jù)的敏感特征，充分考慮采樣數(shù)據(jù)真正代表整個(gè)區(qū)域人口的可行性，設(shè)計(jì)了一個(gè)新的時(shí)間泛化和空間分割的高效采樣模型，使用k-means 聚類算法進(jìn)行抽樣數(shù)據(jù)處理，進(jìn)而提高算法執(zhí)行效率。

4) 理論上分析了TPPDP 方案滿足差分隱私，并使用微軟公司發(fā)布的真實(shí)軌跡數(shù)據(jù)進(jìn)行仿真測(cè)試。測(cè)試結(jié)果表明，TPPDP 方案在滿足隱私保護(hù)的同時(shí)具有較高的數(shù)據(jù)效用，并表現(xiàn)出良好的性能。

2 相關(guān)工作

為了解決用戶軌跡數(shù)據(jù)的泄露問題，學(xué)者們已進(jìn)行了大量的研究與探討。Chen 等[14]根據(jù)蒙特利爾地區(qū)公共交通機(jī)構(gòu)發(fā)布的數(shù)據(jù)，在差分隱私模型下，提出了一種有效的數(shù)據(jù)依賴的隱私保護(hù)算法，在數(shù)據(jù)處理中利用前綴樹的固有約束來進(jìn)行約束推理，從而產(chǎn)生更好的效果，這是第一個(gè)差分隱私模型應(yīng)用于發(fā)布大量軌跡數(shù)據(jù)的解決方案，缺點(diǎn)是該算法依賴于嚴(yán)格的軌跡場(chǎng)景進(jìn)行實(shí)現(xiàn)，在實(shí)施過程中有較大局限性。

隨后，越來越多的學(xué)者著手設(shè)計(jì)軌跡隱私保護(hù)的框架模型。He 等[15]針對(duì)GPS 設(shè)備可能導(dǎo)致的大量個(gè)人和人口流動(dòng)的數(shù)據(jù)泄露，提出了一種基于個(gè)人原始GPS 軌跡合成移動(dòng)數(shù)據(jù)的框架，以差分隱私技術(shù)得到理想的隱私保護(hù)的效果，還提供了具體的建模方案，使用分層參考系統(tǒng)對(duì)原始軌跡進(jìn)行離散化處理，使用方向加權(quán)抽樣來提高效用。Cao 等[16]提出了一種靈活的“l(fā)-軌跡隱私保護(hù)”的安全模型，以確保每一段長度軌跡都受到隱私保護(hù)，利用分層設(shè)計(jì)思想來滿足軌跡隱私，并基于4 個(gè)真實(shí)數(shù)據(jù)集進(jìn)行仿真實(shí)驗(yàn)，證明該算法是高效的。上述研究工作偏重于差分隱私的框架模型設(shè)計(jì)，主要是針對(duì)歷史軌跡數(shù)據(jù)集進(jìn)行處理，不能很好地適應(yīng)軌跡數(shù)據(jù)的動(dòng)態(tài)特征。

隨著應(yīng)用程序的發(fā)展，針對(duì)軌跡隱私的研究開始注重隱私保護(hù)系統(tǒng)的設(shè)計(jì)。Gursoy 等[17]將隱私保護(hù)和完整的位置跟蹤進(jìn)行合成，提供了一種綜合隱私保護(hù)系統(tǒng)Ada Trace。這是一個(gè)可擴(kuò)展的系統(tǒng)，針對(duì)差分隱私和彈性位置攻擊提供了一個(gè)效用感知的功能，Ada Trace 在4 個(gè)階段中執(zhí)行特征提取、噪聲注入和特征合成，部署在真實(shí)環(huán)境進(jìn)行使用。Drakonakis 等[18]開發(fā)了LPAuditor 系統(tǒng)，該系統(tǒng)是一個(gè)檢查位置公開，衡量用戶面臨隱私風(fēng)險(xiǎn)信息的系統(tǒng)，并利用Twitter 數(shù)據(jù)和公共應(yīng)用程序接口（API,application programming interface）進(jìn)行測(cè)試。LPAuditor 除了實(shí)現(xiàn)更高的粒度，還引入了一種集群方法，可以解決GPS 讀數(shù)或用戶移動(dòng)引起的空間位移問題。Yang 等[19]將位置隱私保護(hù)和區(qū)塊鏈結(jié)合，確定了傳統(tǒng)人群感知系統(tǒng)中可以披露的3 種方式，并提出了一種新穎的區(qū)塊鏈?zhǔn)诫[私保護(hù)人群感應(yīng)系統(tǒng)，該系統(tǒng)需要基于獎(jiǎng)勵(lì)的任務(wù)分配過程，使用區(qū)塊鏈技術(shù)的匿名特征來隱藏用戶的身份信息。上述隱私保護(hù)系統(tǒng)可以達(dá)到一定的隱私保護(hù)作用，但是在進(jìn)行大量的位置泛化或匿名處理后再進(jìn)行軌跡發(fā)布，會(huì)降低位置服務(wù)的有效性。

在基于差分隱私技術(shù)的軌跡隱私保護(hù)中，比較經(jīng)典的方案是Hua 等[20]和Li 等[21]提出的方案。Hua等[20]假設(shè)原始軌跡數(shù)據(jù)具有相同的時(shí)間戳，通過概率性統(tǒng)計(jì)合并相似節(jié)點(diǎn)形成新軌跡數(shù)據(jù)集，結(jié)合Laplace 機(jī)制設(shè)計(jì)新軌跡發(fā)布算法 TSTDA（time-serial trajectory data algorithm），該算法既保持了比較高的數(shù)據(jù)效用，又可以應(yīng)用到大規(guī)模軌跡隱私保護(hù)場(chǎng)景。Li 等[21]針對(duì)現(xiàn)有隱私保護(hù)算法使用隨機(jī)和無限制的噪聲導(dǎo)致用戶隱私泄露的問題，提出了一種包含有界噪聲約束和差分隱私技術(shù)結(jié)合的算法 NGTMA（noise generation and trajectory merging algorithm），實(shí)現(xiàn)了較高的數(shù)據(jù)可用性。但這些研究工作未考慮時(shí)間屬性，且不允許所有用戶在同一時(shí)間移動(dòng)，沒有建立時(shí)間和空間的關(guān)聯(lián)性，不能很好地適應(yīng)流行病環(huán)境下的軌跡隱私保護(hù)場(chǎng)景。

因此，針對(duì)上述問題，本文通過建立基于差分隱私的時(shí)間泛化和空間分割采樣模型，借助差分隱私保護(hù)的思想，設(shè)計(jì)了一種新的軌跡隱私保護(hù)方案，在增強(qiáng)公共衛(wèi)生數(shù)據(jù)的可用性的同時(shí)，能夠高效抵抗基于背景知識(shí)的攻擊者的攻擊。

3 方案設(shè)計(jì)

本文提出的TPPDP 方案適用于物聯(lián)網(wǎng)背景下移動(dòng)用戶的軌跡隱私保護(hù)場(chǎng)景，核心思想是在保證用戶隱私的同時(shí)，提高軌跡發(fā)布數(shù)據(jù)的有效性，同時(shí)具有較高的執(zhí)行效率。

本文先給出TPPDP 模型及流程設(shè)計(jì)，然后重點(diǎn)闡述TPPDP 方案的2 個(gè)核心子算法：軌跡處理子算法和數(shù)據(jù)發(fā)布子算法。表1 給出了系統(tǒng)參數(shù)及其含義。

表1 系統(tǒng)參數(shù)及其含義

3.1 模型及流程設(shè)計(jì)

為保護(hù)用戶的動(dòng)態(tài)軌跡隱私，TPPDP 進(jìn)行時(shí)間屬性處理，并建立時(shí)間和位置屬性之間的關(guān)聯(lián)模型。

TPPDP 模型如圖1 所示，包括時(shí)間泛化、空間分割、軌跡優(yōu)化和軌跡發(fā)布4 個(gè)步驟，其中時(shí)間泛化和空間分割構(gòu)成軌跡處理子算法TraPro，軌跡優(yōu)化和軌跡發(fā)布構(gòu)成軌跡發(fā)布子算法TraRel。

圖1 TPPDP 模型

首先，對(duì)原始軌跡數(shù)據(jù)集進(jìn)行時(shí)間屬性的泛化，相近時(shí)間節(jié)點(diǎn)的用戶合并在同一區(qū)域，形成采樣軌跡數(shù)據(jù)集。然后，在同一時(shí)間戳的用戶通過聚類方法進(jìn)行分組，利用差分隱私的指數(shù)機(jī)制計(jì)算該組的核心位置，該組內(nèi)移動(dòng)用戶坐標(biāo)被泛化成核心位置，對(duì)移動(dòng)用戶的軌跡有一定的隱私保護(hù)。接著，合并記錄并刪除異常軌跡數(shù)據(jù)。最后，在統(tǒng)計(jì)結(jié)果加入差分隱私的Laplace 噪聲，混淆統(tǒng)計(jì)數(shù)目的真實(shí)性進(jìn)行發(fā)布。

3.2 軌跡處理子算法

軌跡處理子算法TraPro 負(fù)責(zé)處理動(dòng)態(tài)軌跡數(shù)據(jù)，聯(lián)合時(shí)間和空間，有效消除連續(xù)的軌跡數(shù)據(jù)帶來的隱私泄露風(fēng)險(xiǎn)。TraPro 由時(shí)間泛化和空間分割2 個(gè)步驟組成。

3.2.1 時(shí)間泛化

與傳統(tǒng)采集固定時(shí)間戳的靜態(tài)軌跡數(shù)據(jù)不同，TraPro 通過對(duì)時(shí)間屬性的泛化操作，處理動(dòng)態(tài)軌跡數(shù)據(jù)集，并完成采樣軌跡數(shù)據(jù)集的準(zhǔn)備工作，具體實(shí)現(xiàn)過程如下。

1) k-means 聚類算法通過預(yù)先設(shè)定的k值及每個(gè)類別的初始質(zhì)心對(duì)相似的數(shù)據(jù)點(diǎn)進(jìn)行劃分，將一天分成k個(gè)時(shí)間段，初始k個(gè)點(diǎn)是根據(jù)不同實(shí)驗(yàn)軌跡數(shù)據(jù)集特性進(jìn)行選擇的。為保證軌跡數(shù)據(jù)發(fā)布的精度，若用戶的移動(dòng)速度較快，較短時(shí)間內(nèi)行動(dòng)在不同區(qū)域，k就需要取較大數(shù)值，反之亦然。通過劃分后的均值迭代優(yōu)化獲得最優(yōu)的聚類結(jié)果，選定k個(gè)中心的初值，針對(duì)不同時(shí)刻的i和j，對(duì)應(yīng)時(shí)間t之間的歐氏距離為

2) 將每個(gè)數(shù)據(jù)點(diǎn)歸類到離它最近的那個(gè)中心點(diǎn)所代表的簇（cluster）中，計(jì)算時(shí)間t的質(zhì)心為

3) 計(jì)算每個(gè)cluster 的新中心點(diǎn)，把距離質(zhì)心最近的那些數(shù)據(jù)點(diǎn)分配給它，移動(dòng)重心的位置到所有屬于它的數(shù)據(jù)點(diǎn)的平均位置上。迭代直到最大的步數(shù)或者前后的距離值之差小于閾值為止，最終cluster 質(zhì)心會(huì)靠近目的地并停止移動(dòng)，得到最接近的時(shí)間cluster 集合，選取其質(zhì)心作為該cluster 的所有軌跡用戶的時(shí)間戳。

4) 采用k-means 聚類算法對(duì)時(shí)間屬性進(jìn)行泛化，將比較接近的時(shí)間合并為同一個(gè)時(shí)間段，即劃分在一個(gè)固定的時(shí)間區(qū)域內(nèi)。通過對(duì)時(shí)間屬性泛化，將其分成n個(gè)固定的時(shí)間段 Δti(i=1,2,…,n)，假設(shè)每條軌跡等長，同一時(shí)間段被認(rèn)為具有相同的時(shí)間點(diǎn)。經(jīng)時(shí)間泛化后的軌跡如圖2 所示。

圖2 時(shí)間泛化后的軌跡

3.2.2 空間分割

目前，常見的空間劃分的方法有網(wǎng)格單元法、二叉數(shù)、八叉樹等空間分割方法[22]。

TPPDP 采用經(jīng)典的指數(shù)機(jī)制和k-means 聚類算法對(duì)采樣數(shù)據(jù)集進(jìn)行空間分割處理，使用滿足特定分布的隨機(jī)抽樣來實(shí)現(xiàn)隱私保護(hù)，包括空間劃分和分區(qū)選擇兩部分。

首先，在空間劃分中，將相同時(shí)間戳t的位置數(shù)據(jù)進(jìn)行分割，采用k-means 聚類算法將該區(qū)域分成k個(gè)子區(qū)域，通過預(yù)先設(shè)定的k值及每個(gè)類別的初始質(zhì)心對(duì)相似的數(shù)據(jù)點(diǎn)進(jìn)行劃分，初始k值根據(jù)不同實(shí)驗(yàn)軌跡數(shù)據(jù)集特性進(jìn)行選擇。然后，利用k-means 聚類算法的處理結(jié)果，對(duì)具有更接近位置數(shù)據(jù)進(jìn)行合并。最后，通過差分隱私的指數(shù)機(jī)制定義一個(gè)效用函數(shù)U，U對(duì)每一種輸出方案計(jì)算出一個(gè)分值，選擇分值最高的分區(qū)，也是最優(yōu)分區(qū)方案。具體過程如下。

1) 使用經(jīng)典的k-means 方法對(duì)位置進(jìn)行劃分，在每個(gè)時(shí)間戳上根據(jù)它們的成對(duì)歐氏距離將原始位置數(shù)據(jù)劃分為N組，而k-means 的分區(qū)為P～。如果N的數(shù)目比較大，代表分配到很多區(qū)域，軌跡的精度損失也更少，計(jì)算代價(jià)會(huì)隨之增加。

2) 在ti時(shí)刻，所有的移動(dòng)用戶都被集中在區(qū)域L里，這時(shí)區(qū)域L可以被分割成g個(gè)候選分區(qū)簇，候選分區(qū)可以形成一個(gè)集合τ。

3) TraPro 定義一個(gè)效用函數(shù)U，對(duì)每一個(gè)候選的分區(qū)P τ∈都賦予一個(gè)效用值，選擇效用值越高的分區(qū)。模型中，=1,2,…,g)表示第i個(gè)分組的位置質(zhì)點(diǎn)，其效用函數(shù)為

其中，

4) 針對(duì)第i個(gè)候選分區(qū)Pi∈τ，效用函數(shù)滿足ε-差分隱私的指數(shù)機(jī)制。根據(jù)分值選擇分區(qū)方法，同時(shí)得到該分區(qū)的中心位置。

經(jīng)過TraPro 處理后，形成m個(gè)子簇，計(jì)算出每個(gè)子簇的簇心，最佳劃分可以使軌跡數(shù)據(jù)點(diǎn)效用損失最小。TraPro 如算法1 所示。

算法1TraPro

輸入D

輸出DG

在已知的廣義區(qū)域里，存在m個(gè)互不相關(guān)的移動(dòng)用戶，原始軌跡出現(xiàn)雜亂無章的狀態(tài)。對(duì)原始軌跡數(shù)據(jù)集進(jìn)行TraPro 處理后，每個(gè)子簇都有對(duì)應(yīng)的中心，如圖3 所示。

圖3 TraPro 處理后的軌跡

3.3 數(shù)據(jù)發(fā)布子算法

數(shù)據(jù)發(fā)布子算法TraRel 負(fù)責(zé)提供軌跡數(shù)據(jù)發(fā)布前的優(yōu)化操作，簡(jiǎn)單差分隱私處理會(huì)導(dǎo)致發(fā)布數(shù)據(jù)的可用性降低，而TraRel 包含2 個(gè)步驟：軌跡優(yōu)化和軌跡發(fā)布，有效保證較高的可發(fā)布的軌跡數(shù)據(jù)效用。

3.3.1 軌跡優(yōu)化

軌跡優(yōu)化重點(diǎn)檢查原始軌跡數(shù)據(jù)集在哪類新產(chǎn)生的數(shù)據(jù)集里存在，并運(yùn)行預(yù)判機(jī)制，刪除異常軌跡，降低發(fā)布空軌跡的風(fēng)險(xiǎn)性，增加軌跡發(fā)布的有效性。

假設(shè)Ω為廣義的區(qū)域，針對(duì)同一Δti，模型中假設(shè)cluster 中所有移動(dòng)用戶的位置坐標(biāo)被泛化為這個(gè)位置，在該時(shí)刻的所有位置數(shù)據(jù)點(diǎn)，都可以被認(rèn)為是32 個(gè)位置質(zhì)點(diǎn)，那么，在64 個(gè)固定的時(shí)間戳，會(huì)產(chǎn)生3264條可能的軌跡數(shù)，這個(gè)數(shù)據(jù)覆蓋了所有的軌跡發(fā)布的可能性，通過泛化的方法，保護(hù)了移動(dòng)用戶隱私，不過也會(huì)帶來大量的資源消耗。

由于產(chǎn)生一些并不存在的異常假軌跡數(shù)據(jù)會(huì)降低LBS 的可用性，軌跡優(yōu)化算法將每個(gè)進(jìn)行處理后的軌跡數(shù)據(jù)與真實(shí)軌跡數(shù)據(jù)進(jìn)行對(duì)比，統(tǒng)計(jì)合并后的真實(shí)軌跡的記錄數(shù)Real，當(dāng)發(fā)現(xiàn)Real=0 時(shí)，認(rèn)為該條軌跡為異常流行病軌跡數(shù)據(jù)并刪除，進(jìn)一步減少發(fā)布空軌跡的風(fēng)險(xiǎn)性，增加軌跡發(fā)布的有效性。軌跡優(yōu)化步驟增強(qiáng)了軌跡數(shù)據(jù)發(fā)布的可用性，1) 對(duì)原始數(shù)據(jù)集和產(chǎn)生的新的軌跡數(shù)據(jù)集進(jìn)行對(duì)比合并，列舉出真實(shí)存在流行病的軌跡的記錄數(shù)；2) 如果監(jiān)測(cè)到記錄數(shù)為0，說明新的軌跡數(shù)據(jù)為空軌跡，判斷該條軌跡為異常數(shù)據(jù)，不進(jìn)行發(fā)布，提高軌跡數(shù)據(jù)可用性，進(jìn)一步加強(qiáng)公共衛(wèi)生數(shù)據(jù)的服務(wù)質(zhì)量。軌跡優(yōu)化過程如表2 所示。

表2 軌跡優(yōu)化過程

3.3.2 軌跡發(fā)布

在軌跡優(yōu)化處理后，考慮到如果直接發(fā)布這個(gè)統(tǒng)計(jì)數(shù)據(jù)，雖然已經(jīng)達(dá)到一定隱私保護(hù)的目的，但是特別針對(duì)如某些統(tǒng)計(jì)數(shù)為1 的軌跡，如果攻擊方有一定的背景知識(shí)，很容易猜到用戶歸屬從而造成隱私泄露。因此，在進(jìn)行軌跡發(fā)布操作時(shí)，首先統(tǒng)計(jì)原始軌跡的數(shù)目，引入差分隱私的Laplace 機(jī)制，添加Laplace 噪聲到每個(gè)真實(shí)數(shù)據(jù)中，可以抵制具有背景知識(shí)的攻擊者由對(duì)數(shù)據(jù)發(fā)動(dòng)的攻擊。表示噪聲計(jì)數(shù)排序的軌跡；

iC表示的噪聲數(shù)，C1＞C2＞ …＞Ci，具體過程如下。

1) 從集合(C2,C1)開始，根據(jù)Laplace 機(jī)制計(jì)算Ω-軌跡內(nèi)噪聲量位于(Ci+1,Ci)的期望值Numi。f(x,ε)表示Laplace 分布的概率密度函數(shù)。Ω-內(nèi)每條軌跡的真實(shí)計(jì)數(shù)為 0。加上后，的一條軌跡含噪聲量在區(qū)間內(nèi)的概率為，可得

2) TPPDP 從Ω-中隨機(jī)選取不同軌跡的噪聲量并將它們和一起包含在最終輸出集中，噪聲計(jì)數(shù)是這個(gè)區(qū)間內(nèi)的隨機(jī)值，當(dāng)總計(jì)數(shù)達(dá)到原始數(shù)據(jù)集D的大小時(shí)，上述過程停止，并輸出統(tǒng)計(jì)記錄。

對(duì)記錄數(shù)進(jìn)行Laplace 機(jī)制加噪后，形成的數(shù)據(jù)集包括軌跡數(shù)據(jù)集、加噪后記錄數(shù)，這時(shí)只需將處理后的軌跡數(shù)據(jù)集發(fā)布。表3 展示了軌跡發(fā)布過程。

表3 軌跡發(fā)布過程

數(shù)據(jù)發(fā)布子算法TraRel 如算法2 所示。

算法2TraRel

輸入DG

輸出nc

3.4 算法理論分析

TPPDP包含2個(gè)子算法，在軌跡處理的過程中，子算法TraPro 處理時(shí)間和空間數(shù)據(jù)，使用了聚類算法k-means，選取適當(dāng)?shù)膋，將數(shù)據(jù)進(jìn)行分類，時(shí)間復(fù)雜度為Ο(n2)，空間復(fù)雜度為Ο(n)；子算法TraRel的時(shí)間復(fù)雜度為Ο(n)，空間復(fù)雜度為Ο(n)。本節(jié)將TPPDP 與目前經(jīng)典的 2 個(gè)算法 TSTDA[20]和NGTMA[21]進(jìn)行對(duì)比，如表4 所示。

表4 時(shí)空復(fù)雜度分析

如表4 所示，TPPDP 時(shí)間復(fù)雜度比TSTDA 低，體現(xiàn)了本文算法的性能優(yōu)勢(shì)。此外，TPPDP 與NGTMA 時(shí)間復(fù)雜度相同，但是在數(shù)據(jù)發(fā)布前，TPPDP 在軌跡優(yōu)化中增加了異常數(shù)據(jù)去除的步驟，后期不再進(jìn)行異常數(shù)據(jù)處理，對(duì)比NGTMA，TPPDP在提高算法精度的同時(shí)，可以進(jìn)一步節(jié)省算法實(shí)際運(yùn)行時(shí)所消耗的時(shí)間。

4 隱私保護(hù)度分析

本節(jié)首先證明TPPDP 各階段滿足ε-差分隱私，進(jìn)而根據(jù)差分隱私組合特性，證明方案滿足差分隱私。

定理1TPPDP 在軌跡處理環(huán)節(jié)的子算法TraPro 滿足?-差分隱私。由于TraPro 在進(jìn)行原始軌跡處理時(shí)，在k-means 聚類算法的處理結(jié)果上，采用效用函數(shù)進(jìn)行空間劃分的選擇，對(duì)每一種分區(qū)方案計(jì)算實(shí)用性分值，設(shè)q是查詢函數(shù)，u是實(shí)用性效用函數(shù)，分值高的輸出方案具有更大的概率進(jìn)行發(fā)布。下面證明當(dāng)使用查詢函數(shù)q對(duì)子算法TraPro進(jìn)行數(shù)據(jù)查詢時(shí)，輸出結(jié)果滿足差分隱私。

證明對(duì)任意的查詢函數(shù)q和效用函數(shù)u，定義表示與exp(εq(T,r))u(r)成比例的概率選擇r。由的定義可知，是有界的。根據(jù)定義，的概率密度為

本文定義Δq為查詢函數(shù)中最大可能的差異值。數(shù)據(jù)集T中單條記錄變化最多可帶來變化Δq，有

因?yàn)橐话氵x擇Δq≤1 的查詢函數(shù)為q，滿足(2ε)-差分隱私，所以滿足?-差分隱私。

由此得證，子算法TraPro 滿足?-差分隱私。

定理2TPPDP 在數(shù)據(jù)發(fā)布環(huán)節(jié)的子算法TraRel 滿足?-差分隱私。假設(shè)函數(shù)集F具有S(F)的敏感度，且K是將獨(dú)立噪聲添加到F中每個(gè)函數(shù)f的輸出的算法，如果噪聲服從參數(shù)值并且采用的Laplace 分布，則算法K滿足?-差分隱私，由于噪聲在發(fā)布前進(jìn)行添加，對(duì)于同一個(gè)查詢，差分隱私算法輸出結(jié)果必定相同，從而保證軌跡發(fā)布數(shù)據(jù)的安全性。

證明在TPPDP 中，利用條件概率函數(shù)，定義ti為查詢的數(shù)值，針對(duì)兄弟數(shù)據(jù)集T1和T2，有

同時(shí)，根據(jù)條件分布算法可得

使用邊界完成證明

因此，子算法TraRel 滿足?-差分隱私。

定理3TPPDP 滿足?-差分隱私。

證明由于差分隱私的組合特性，TPPDP 包含的2 個(gè)子算法分別滿足?-差分隱私。假設(shè)TraPro滿足?1-差分隱私，TraRel 滿足?2-差分隱私，則可推斷TPPDP 滿足?-差分隱私，此時(shí)ε=ε1+ε2。

5 性能分析

為驗(yàn)證所提TPPDP 的有效性和數(shù)據(jù)可用性，本文基于微軟的Research’s T-Drive 預(yù)研項(xiàng)目數(shù)據(jù)進(jìn)行了相關(guān)實(shí)驗(yàn)[23-24]，其中包含10 357 輛小車一周的軌跡數(shù)據(jù)，在這個(gè)數(shù)據(jù)庫中的點(diǎn)的總數(shù)約為1 500 萬，軌跡的總距離達(dá)9×106km。本節(jié)通過TPPDP 與TSTDA[20]和NGTMA[21]的實(shí)驗(yàn)對(duì)比展示TPPDP 的高效性。

5.1 算法執(zhí)行時(shí)間

本節(jié)將從隱私保護(hù)參數(shù)?和軌跡數(shù)據(jù)集大小兩方面來分析TPPDP 的性能表現(xiàn)。將TPPDP 執(zhí)行時(shí)間與TSTDA 和NGTMA 進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果如圖4 所示。

圖4 隨ε 和軌跡數(shù)據(jù)集變化3 種方案執(zhí)行時(shí)間對(duì)比

由圖4 可以看出，一方面，當(dāng)用戶數(shù)量大小一定時(shí)，隨著ε的增加，隱私保護(hù)能力逐漸降低，計(jì)算量降低，3 種算法的執(zhí)行時(shí)間呈線性減少。另一方面，隨著軌跡數(shù)據(jù)集的增大，計(jì)算量明顯升高，算法執(zhí)行時(shí)間呈線性增加。同時(shí)，由圖4(d)可知，TSTDA 和NGTMA 的運(yùn)算開銷大于TPPDP，時(shí)間代價(jià)高昂，導(dǎo)致運(yùn)行速度較低，TPPDP 在執(zhí)行效率上具有明顯的優(yōu)勢(shì)。

5.2 軌跡合并時(shí)間

為了評(píng)估TPPDP 在軌跡處理階段的表現(xiàn)，在?=0.1 和?=0.5 這2 種情況下進(jìn)行仿真實(shí)驗(yàn)，分析隨著用戶數(shù)量的增加，平均軌跡合并時(shí)間的變化，實(shí)驗(yàn)結(jié)果如圖5 所示。

圖5 軌跡合并時(shí)間對(duì)比

從圖5 可以看出，隨著用戶數(shù)量的增加，3 種隱私保護(hù)方案的軌跡合并時(shí)間都呈上升趨勢(shì)，軌跡合并階段處理操作與隱私參數(shù)的選擇并沒有直接關(guān)系，與TSTDA 和NGTMA 相比，TPPDP 的軌跡合并時(shí)間較小，性能較優(yōu)。

5.3 噪聲產(chǎn)生時(shí)間

為了評(píng)估TPPDP 在軌跡發(fā)布階段的表現(xiàn)，取隱私參數(shù)?=0.1 和?=0.5，測(cè)試平均軌跡噪聲產(chǎn)生時(shí)間隨著用戶數(shù)量的增加而產(chǎn)生的變化，對(duì)比結(jié)果如圖6 所示。實(shí)驗(yàn)結(jié)果表明，與TSTDA 和NGTMA相比，TPPDP 的軌跡噪聲產(chǎn)生時(shí)間較少，執(zhí)行效率較高。

圖6 軌跡噪聲產(chǎn)生時(shí)間對(duì)比

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

根據(jù)差分隱私模型定義，隱私參數(shù)?用于衡量隱私保護(hù)強(qiáng)度，較小的?提供較高的隱私保護(hù)強(qiáng)度。第4 節(jié)從理論上證明了TPPDP 滿足?-差分隱私，說明算法可以滿足用戶軌跡隱私保護(hù)需求。本節(jié)進(jìn)一步利用互信息（MI,mutual information）[25]來測(cè)試TPPDP 的隱私保護(hù)強(qiáng)度。MI是信息論里一種有用的信息度量，隱私作為一種信息，可以用信息熵進(jìn)行量化，MI 用來測(cè)量2 個(gè)集合之間的相互依賴關(guān)系，表現(xiàn)為猜中某特定用戶的概率。

為了評(píng)估TPPDP 在安全性能上的表現(xiàn)，實(shí)驗(yàn)取不同的隱私參數(shù)?=0.1 和?=0.5，分析3 種方案互信息隨著用戶數(shù)量的變化情況，對(duì)比結(jié)果如圖7 所示。實(shí)驗(yàn)結(jié)果表明，與TSTDA 和NGTMA 相比，TPPDP 算法的互信息值較低，隱私損失度較低，安全性能較好。

圖7 隱私保護(hù)強(qiáng)度對(duì)比

5.5 發(fā)布數(shù)據(jù)效用

TPPDP 采用差分隱私機(jī)制進(jìn)行軌跡數(shù)據(jù)的隱私保護(hù)，會(huì)不可避免地影響軌跡數(shù)據(jù)效用。為了測(cè)試軌跡發(fā)布的數(shù)據(jù)效用，實(shí)驗(yàn)利用豪斯多夫距離（HD,Hausdorff distance）來評(píng)估TPPDP 的軌跡數(shù)據(jù)效用[20]。HD 用來衡量2 個(gè)點(diǎn)集間的距離，被廣泛用于測(cè)量2 個(gè)數(shù)據(jù)集的相似性。通過測(cè)試發(fā)布數(shù)據(jù)集和原始數(shù)據(jù)集之間的HD 判斷數(shù)據(jù)效用，距離值越小，代表2 個(gè)數(shù)據(jù)越相似，數(shù)據(jù)可用性越高，反之亦然。

為了評(píng)估TPPDP 方法在軌跡發(fā)布時(shí)的數(shù)據(jù)效用，計(jì)算合并軌跡前原始軌跡數(shù)據(jù)集的真實(shí)計(jì)數(shù)和Laplace 加噪后計(jì)數(shù)之間的HD。實(shí)驗(yàn)測(cè)量隨著用戶數(shù)量的增加，3 種方案HD 的變化，實(shí)驗(yàn)結(jié)果如圖8所示。實(shí)驗(yàn)結(jié)果表明，一方面，3 種方案隨著?的增加，HD 逐漸變小，隱私保護(hù)算法的數(shù)據(jù)效用增加。這是因?yàn)椋[私參數(shù)?用于衡量隱私保護(hù)程度，?越大意味著發(fā)布數(shù)據(jù)集和原始數(shù)據(jù)集的概率密度函數(shù)相似度越低，隱私保護(hù)強(qiáng)度越弱，數(shù)據(jù)可用性越高。另一方面，與TSTDA和NGTMA相比，TPPDP的HD 更小，和原始數(shù)據(jù)集更相似，具有更高的數(shù)據(jù)效用。

圖8 數(shù)據(jù)效用對(duì)比分析

從上述實(shí)驗(yàn)結(jié)果可以看出，與 TSTDA 和NGTMA 相比，TPPDP 算法執(zhí)行時(shí)間較少，隱私損失度較低，數(shù)據(jù)可用性較高，性能表現(xiàn)整體趨向平穩(wěn)。

6 結(jié)束語

隨著智能移動(dòng)設(shè)備、無線通信及定位技術(shù)的發(fā)展，基于位置服務(wù)的技術(shù)得到了廣泛的應(yīng)用，給人們生活帶來了巨大的便利，服務(wù)器根據(jù)用戶的位置信息和服務(wù)需求，為其提供解決方案，因此用戶提供位置信息越精確，服務(wù)器提供解決方案越理想。本文針對(duì)物聯(lián)網(wǎng)背景下的智能移動(dòng)設(shè)備場(chǎng)景，提出了一種時(shí)間泛化和空間分割相結(jié)合的差分隱私軌跡數(shù)據(jù)發(fā)布方案，不同于現(xiàn)有的方案，本文方案建立了精準(zhǔn)高效的軌跡數(shù)據(jù)采樣模型，通過k-means 對(duì)軌跡數(shù)據(jù)進(jìn)行聚合抽樣，并且能夠提供更強(qiáng)的隱私保護(hù)能力，同時(shí)引入提前預(yù)判機(jī)制，減少發(fā)布空軌跡的風(fēng)險(xiǎn)性，增加軌跡發(fā)布的有效性，保證更好的數(shù)據(jù)可用性。實(shí)驗(yàn)結(jié)果證明了TPPDP 在隱私保護(hù)強(qiáng)度、軌跡數(shù)據(jù)效用和執(zhí)行效率上具有較大的優(yōu)勢(shì)。