滿足本地化差分隱私的眾包位置數(shù)據(jù)采集

霍崢 張坤 賀萍 武彥斌

摘 要：針對(duì)位置數(shù)據(jù)眾包采集中個(gè)人位置隱私泄露的問題，提出了一種滿足本地化差分隱私的位置數(shù)據(jù)眾包采集方法。 首先，使用逐點(diǎn)插入法構(gòu)造維諾圖，對(duì)路網(wǎng)空間進(jìn)行分割;然后，采用滿足本地化差分隱私的隨機(jī)擾動(dòng)的方式對(duì)每個(gè)維諾格中的位置數(shù)據(jù)進(jìn)行擾動(dòng);再次，設(shè)計(jì)了一種在擾動(dòng)數(shù)據(jù)集上進(jìn)行空間范圍查詢的方法，獲得對(duì)真實(shí)結(jié)果的無偏估計(jì);最后，在空間范圍查詢下進(jìn)行了實(shí)驗(yàn)驗(yàn)證，并與保護(hù)隱私的軌跡數(shù)據(jù)采集（PTDC）算法進(jìn)行了對(duì)比，算法查詢誤差率最壞不超過40%，最好情況在20%以下，運(yùn)行時(shí)間在8s以內(nèi)，在隱私保護(hù)度高于PTDC算法的前提下，上述參數(shù)優(yōu)于PTDC算法。

關(guān)鍵詞：本地化差分隱私;道路網(wǎng)絡(luò);維諾格;位置數(shù)據(jù);移動(dòng)對(duì)象

中圖分類號(hào)： TP311.13

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-9081（2019）03-0763-06

Abstract： To solve the problem of privacy leakage in crowdsourced location data collection， a locally differentially private location data collection method with crowdsourcing was proposed. Firstly， a Voronoi diagram constructed by point-by-point insertion method was used to partition the road network space. Secondly， a random disturbance satisfying local differential privacy was used to disturb the original location data in each Voronoi grid. Thirdly， a designed spatial range query method was applied to noisy datasets to get the unbiased estimation of the actual result. Finally， experiments were carried out on spatial range queries to compare the proposed algorithm with PTDC （Privacy-preserving Trajectory Data Collection） algorithm. The results show that the query error rate is no more than 40%， and less than 20%in the best situation， and the running time is less than 8 seconds， which are better than those of PTDC algorithm while the proposed method has a higher degree of privacy preserving.

Key words： local differential privacy; road network; Voronoi grid; location data; moving object

0 引言

隨著定位技術(shù)和移動(dòng)定位設(shè)備的發(fā)展，越來越多的位置數(shù)據(jù)被采集后，用來進(jìn)行位置數(shù)據(jù)分析和挖掘。眾包數(shù)據(jù)采集應(yīng)運(yùn)而生。所謂眾包數(shù)據(jù)采集是指：使用人們的群體數(shù)據(jù)完成眾多的數(shù)據(jù)挖掘任務(wù)，使挖掘結(jié)果能更好地服務(wù)于人們的生活。例如，高德地圖目前每天產(chǎn)生的軌跡數(shù)據(jù)中，有72%都來自眾包，也就是使用地圖的用戶。然而，位置數(shù)據(jù)包含大量的敏感信息，用戶通常情況下會(huì)無償?shù)刎暙I(xiàn)自己的位置數(shù)據(jù)，卻承擔(dān)著個(gè)人隱私泄露的巨大風(fēng)險(xiǎn)，隨著人們對(duì)個(gè)人隱私問題的關(guān)注，使用這種數(shù)據(jù)采集方式的發(fā)展趨勢并不樂觀。制約眾包位置數(shù)據(jù)采集的關(guān)鍵問題是移動(dòng)對(duì)象的個(gè)人隱私問題。

數(shù)據(jù)收集者收集了移動(dòng)對(duì)象的位置數(shù)據(jù)，并對(duì)大量的數(shù)據(jù)進(jìn)行分析和挖掘，得出某些結(jié)論便于優(yōu)化城市道路規(guī)劃、制定商業(yè)決策等。然而，在上述數(shù)據(jù)采集方式中，有兩個(gè)重要的假設(shè)：第一，移動(dòng)對(duì)象愿意提供精確的位置給數(shù)據(jù)采集者;第二，數(shù)據(jù)收集者是可信的，不會(huì)惡意出售數(shù)據(jù)或者將數(shù)據(jù)泄露給第三方。但是，上述兩個(gè)假設(shè)在大多數(shù)情況下是不成立的，這是因?yàn)椋旱谝?，隨著人們對(duì)個(gè)人隱私的關(guān)注，越來越多的用戶并不愿意共享自己的精確位置數(shù)據(jù);第二，大量數(shù)據(jù)收集者是不可信的，社會(huì)上出現(xiàn)了很多服務(wù)提供商出售用戶的個(gè)人數(shù)據(jù)，從而導(dǎo)致隱私泄露的嚴(yán)重問題。即使數(shù)據(jù)收集者可信，惡意攻擊者也可能攻擊數(shù)據(jù)收集者的服務(wù)器，導(dǎo)致大量的個(gè)人數(shù)據(jù)泄露的嚴(yán)重情況。根據(jù)上述分析，用戶更加希望數(shù)據(jù)在離開設(shè)備之前，就已經(jīng)進(jìn)行了隱私保護(hù)處理，即使數(shù)據(jù)收集者也無法獲取用戶的精確數(shù)據(jù)。

在目前的研究工作中，文獻(xiàn)[1]和[2]提出了一種基于假位置的保護(hù)隱私的位置數(shù)據(jù)采集方法，用戶在發(fā)送自己的真實(shí)位置的同時(shí)，發(fā)送若干個(gè)根據(jù)某種規(guī)則產(chǎn)生的假位置進(jìn)行混淆;文獻(xiàn)[3]提出了一種基于數(shù)據(jù)泛化的感知隱私的數(shù)據(jù)采集方法。每個(gè)用戶在發(fā)送自己的數(shù)據(jù)之前，先找到匿名組匿名，然而，達(dá)到最佳匿名效果是NP（Non-deterministic Polynomial）-難問題。上述兩種方法都無法達(dá)到強(qiáng)隱私保護(hù)的效果。近年來出現(xiàn)的本地化差分隱私技術(shù)（Local Differential Privacy， LDP）[4]是解決該問題的最佳方法。本地化差分隱私模型中，客戶端首先對(duì)原始數(shù)據(jù)進(jìn)行擾動(dòng)，然后再發(fā)送給數(shù)據(jù)收集服務(wù)器，數(shù)據(jù)收集服務(wù)器在擾動(dòng)的數(shù)據(jù)上作分析統(tǒng)計(jì)，得到有效的分析結(jié)果。在此過程中，即使數(shù)據(jù)收集服務(wù)器也無法得到用戶精確的位置數(shù)據(jù)，從而實(shí)現(xiàn)了個(gè)人位置隱私保護(hù)。

本文主要研究本地化差分隱私技術(shù)在空間位置數(shù)據(jù)收集上的應(yīng)用，具體來說，本文的主要貢獻(xiàn)如下：

1）提出了一種滿足本地化差分隱私的位置數(shù)據(jù)眾包采集方法。在不暴露移動(dòng)對(duì)象精確位置的前提下，服務(wù)器可在擾動(dòng)的數(shù)據(jù)上進(jìn)行空間范圍查詢等操作，保護(hù)了移動(dòng)對(duì)象的位置隱私。

2）提出了一種基于維諾圖的路網(wǎng)空間劃分方法，并將本地化差分隱私的擾動(dòng)方法應(yīng)用在各個(gè)維諾格中，擾動(dòng)原始位置數(shù)據(jù)，并證明該擾動(dòng)方法是滿足ε-本地化差分隱私的。

3）提出了一種在擾動(dòng)后數(shù)據(jù)上估算空間范圍查詢計(jì)數(shù)值的方法，該方法可獲得對(duì)空間范圍查詢計(jì)數(shù)值的無偏估計(jì)。

4）最后，通過實(shí)驗(yàn)對(duì)本文提出的方法進(jìn)行了驗(yàn)證，證明本文提出的方法在數(shù)據(jù)可用性、算法效率及可擴(kuò)展性上具有優(yōu)勢。

1 相關(guān)工作

本文從位置數(shù)據(jù)隱私保護(hù)技術(shù)、本地化差分隱私的應(yīng)用兩個(gè)方面對(duì)國內(nèi)外研究現(xiàn)狀進(jìn)行梳理。位置隱私保護(hù)技術(shù)是指：在用戶利用位置信息獲取基于位置服務(wù)的過程中，保護(hù)其精確位置不泄露。位置隱私保護(hù)技術(shù)可分為三大類：k-匿名方法、加密法、擾動(dòng)法。文獻(xiàn)[5]提出了一種保護(hù)隱私的位置數(shù)據(jù)采集技術(shù)。該方法中，個(gè)體之間通過點(diǎn)對(duì)點(diǎn)方式通信，對(duì)各自的位置數(shù)據(jù)進(jìn)行交換、k-匿名等隱私保護(hù)處理之后，再將位置數(shù)據(jù)發(fā)送給不可信的數(shù)據(jù)收集方。文獻(xiàn)[1]提出了一種無匿名區(qū)域的位置隱私保護(hù)方法，該方法通過用戶之間的協(xié)作形成k-匿名區(qū)域，匿名組內(nèi)的用戶采用該組的密度中心代替真實(shí)位置發(fā)出查詢，并增量地從服務(wù)器獲得近鄰查詢結(jié)果。文獻(xiàn)[3]提出了一種基于加密方法的位置隱私保護(hù)技術(shù)，移動(dòng)對(duì)象在運(yùn)行過程中會(huì)收到一個(gè)密鑰序列，作者設(shè)計(jì)了貪心密鑰選擇算法和加密機(jī)制，軌跡數(shù)據(jù)在被收集之前，先對(duì)軌跡上的位置加密。文獻(xiàn)[2]和文獻(xiàn)[3]是兩種保護(hù)隱私的位置數(shù)據(jù)采集技術(shù)。其中，文獻(xiàn)[2]提出一種方法，使得每個(gè)移動(dòng)對(duì)象發(fā)送真實(shí)位置的同時(shí)隨機(jī)添加若干假位置，以達(dá)到擾動(dòng)精確位置的目的。文獻(xiàn)[3]采用傳統(tǒng)的位置k-匿名方式在客戶端對(duì)用戶位置進(jìn)行匿名，研究重點(diǎn)在于如何構(gòu)造匿名集，以防止攻擊者根據(jù)移動(dòng)對(duì)象的位置分布密度進(jìn)行攻擊。

近年來出現(xiàn)的本地化差分隱私技術(shù)是在客戶端進(jìn)行數(shù)據(jù)隱私保護(hù)的有力手段，普遍應(yīng)用在數(shù)值數(shù)據(jù)擾動(dòng)后的中間值估計(jì)[6]及非數(shù)值數(shù)據(jù)擾動(dòng)后的top-k值估計(jì)[7]中。近來，本地化差分隱私技術(shù)在位置數(shù)據(jù)采集中也有應(yīng)用。文獻(xiàn)[8]提出了一種個(gè)性化的本地化差分隱私技術(shù)解決位置隱私保護(hù)的問題。針對(duì)各個(gè)用戶不同隱私保護(hù)需求度的要求，提出了安全區(qū)域的概念，每個(gè)用戶指定自己能容忍的安全區(qū)域，隨后，采用本地化差分隱私技術(shù)對(duì)用戶的安全區(qū)域進(jìn)行擾動(dòng)，使得攻擊者能夠識(shí)別出某個(gè)用戶的安全區(qū)域的概率小于某個(gè)閾值。文獻(xiàn)[9]提出了一種使用LDP技術(shù)進(jìn)行位置數(shù)據(jù)采集的架構(gòu)。用戶把數(shù)據(jù)發(fā)送給一個(gè)可信的原子服務(wù)提供者，它負(fù)責(zé)用隱私參數(shù)ε將位置數(shù)據(jù)按照滿足差分隱私的空間分割（Private Spatial Division， PSD）的方式進(jìn)行采集和更新。隨后，PSD信息存儲(chǔ)在服務(wù)器端，用于響應(yīng)請求者發(fā)出的請求。

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

下面介紹本文算法的預(yù)備知識(shí)。

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

在某個(gè)時(shí)刻，大量的移動(dòng)設(shè)備用戶持有一條由其移動(dòng)設(shè)備產(chǎn)生的位置數(shù)據(jù)，不可信的服務(wù)器欲獲知某個(gè)區(qū)域內(nèi)的移動(dòng)對(duì)象的個(gè)數(shù)及分布情況，由于隱私泄露的顧慮，用戶不會(huì)發(fā)送自己的精確位置給服務(wù)器，而是發(fā)送一個(gè)經(jīng)過算法擾動(dòng)的非原始數(shù)據(jù)。在僅能獲取用戶擾動(dòng)數(shù)據(jù)的情況下，服務(wù)器或者第三方數(shù)據(jù)分析者通過某種計(jì)算方式獲取較為精確的統(tǒng)計(jì)結(jié)果。

本文研究問題的系統(tǒng)結(jié)構(gòu)如圖1所示。客戶端的數(shù)據(jù)經(jīng)過擾動(dòng)之后發(fā)送給服務(wù)器，服務(wù)器端包含地圖劃分、用戶分組、查詢結(jié)果優(yōu)化三個(gè)模塊。其中查詢結(jié)果優(yōu)化模塊可幫助服務(wù)器用擾動(dòng)后的位置數(shù)據(jù)獲取較為精確的空間范圍查詢結(jié)果。

2.2 本地化差分隱私技術(shù)

差分隱私（Differential Privacy， DP）技術(shù)是目前已知的最強(qiáng)的隱私保護(hù)模型[10-11]，然而，差分隱私只能對(duì)集中式數(shù)據(jù)進(jìn)行隱私保護(hù)處理，即：需要一個(gè)可信第三方收集精確數(shù)據(jù)，然后再進(jìn)行隱私保護(hù)處理。本地化差分隱私（Local Differential Privacy， LDP）與傳統(tǒng)的差分隱私技術(shù)不同，它不需要可信第三方，數(shù)據(jù)在流出移動(dòng)對(duì)象設(shè)備之前就已經(jīng)被擾動(dòng)過。再者，一般情況下，每個(gè)用戶分享的數(shù)據(jù)并不多，這也符合差分隱私的設(shè)定環(huán)境。由于這些優(yōu)勢，本地化差分隱私作為新興的隱私保護(hù)技術(shù)，關(guān)于其應(yīng)用領(lǐng)域[12]與算法改進(jìn)的研究[13]近幾年吸引了研究者們的注意。

定義1給出了LDP的定義。

定義1 本地化差分隱私（LDP）。某個(gè)隨機(jī)算法A滿足ε-LDP，當(dāng)且僅當(dāng)對(duì)于任意兩個(gè)值l，l′∈L，對(duì)于任意O∈Range（A）：

其中，概率P[]是基于算法A的隨機(jī)程度的。

也就是說，不管用戶持有數(shù)據(jù)的具體值是多少，對(duì)于不可信的數(shù)據(jù)收集者來說，接收到的數(shù)據(jù)相差不大。換句話說，根據(jù)接收到的擾動(dòng)后的數(shù)據(jù)，攻擊者或數(shù)據(jù)收集方在具有任何背景知識(shí)的情況下，都無法獲知用戶的原始數(shù)據(jù)。

定義2 維諾圖。由一組連接兩鄰點(diǎn)直線的垂直平分線組成的連續(xù)多邊形組成。其中，每個(gè)連續(xù)多邊形為一個(gè)維諾格v。v中只包含一個(gè)點(diǎn)，稱為生成元。v的內(nèi)點(diǎn)到該生成元距離小于到其他生成元的距離，且邊界上的點(diǎn)到其生成元的距離相等。

圖2展示了維諾圖對(duì)路網(wǎng)空間的劃分。其中，實(shí)心黑點(diǎn)為路網(wǎng)上的道路交叉點(diǎn)，實(shí)線表示路網(wǎng)中的道路，虛線表示維諾格的邊界。在維諾格v1中，包含4個(gè)移動(dòng)對(duì)象，如三角形所示。

在本文的算法中，用維諾圖劃分路網(wǎng)空間比用其他方式（如四分樹、KD（K-Dimension）樹、Grid等）劃分路網(wǎng)空間的效果更好。這是由于：1）一個(gè)劃分區(qū)域?qū)τ脩魜碚f就是一個(gè)安全區(qū)域，如果采用前述幾種劃分方法，可能導(dǎo)致劃分區(qū)域中移動(dòng)對(duì)象分布不均勻的問題。2）采用維諾圖的劃分方法能保證每個(gè)維諾格都是移動(dòng)對(duì)象可以訪問的區(qū)域，這是由于一個(gè)維諾格至少包含一個(gè)道路節(jié)點(diǎn)，不會(huì)出現(xiàn)把某個(gè)不可達(dá)區(qū)域劃分為一個(gè)安全區(qū)域的情況，例如河流、湖泊等，然而，采用四分樹或者格劃分時(shí)則可能出現(xiàn)類似的情況。3）采用維諾格作為安全區(qū)域的隱私保護(hù)度更高。這是因?yàn)榫S諾格包含了道路分岔口，攻擊者不能知曉對(duì)移動(dòng)對(duì)象所處的位置或行進(jìn)方向。此前就有用此類思想生成位置k-匿名區(qū)域的方法[14]。

2.3 攻擊模型

攻擊者可能是來自于系統(tǒng)結(jié)構(gòu)中的任意一方。本文假設(shè)服務(wù)器也是不可信的，即，服務(wù)器也可能想要獲知移動(dòng)對(duì)象的位置。攻擊者最大的目的就是獲取移動(dòng)用戶的精確位置。攻擊模式可能是窺探、背景知識(shí)關(guān)聯(lián)、服務(wù)器與移動(dòng)用戶串謀等多種方式。

3 滿足本地化差分隱私的位置數(shù)據(jù)采集算法

滿足本地化差分隱私的位置眾包算法的流程如下：①服務(wù)器將整個(gè)地圖用維諾格進(jìn)行劃分，并存儲(chǔ)維諾格的區(qū)域和相應(yīng)的編號(hào)vi，并將此信息發(fā)布給客戶端知曉;②每個(gè)用戶將自己所處的維諾格編號(hào)vi告知服務(wù)器;③服務(wù)器將處于同一個(gè)維諾格內(nèi)的用戶劃分為一組，并將組消息通知給客戶端;④組內(nèi)的位置數(shù)據(jù)依據(jù)LDP機(jī)制實(shí)施擾動(dòng)，并將擾動(dòng)之后的位置數(shù)據(jù)發(fā)送給服務(wù)器;⑤服務(wù)器利用擾動(dòng)后的位置數(shù)據(jù)及查詢結(jié)果優(yōu)化算法求得最終結(jié)果。

數(shù)據(jù)流向如圖3所示。

本文假設(shè)服務(wù)器是不可信的，服務(wù)器知曉用戶處于哪個(gè)維諾格內(nèi)，但是并不能知曉用戶的精確位置。對(duì)于用戶來說，其所處的維諾格就是其安全區(qū)域。在上述過程中，①～③步為維諾圖劃分及數(shù)據(jù)傳送過程。下面對(duì)維諾格劃分、數(shù)據(jù)擾動(dòng)及空間范圍查詢結(jié)果求精等過程作詳細(xì)闡述。

3.1 基于維諾格的路網(wǎng)劃分

基于維諾格的路網(wǎng)劃分由服務(wù)器完成，然后將劃分情況發(fā)送給客戶端，客戶端根據(jù)劃分情況可知曉其所處的維諾格及編號(hào)，服務(wù)器根據(jù)收到的維諾格編號(hào)情況，將處于同一個(gè)維諾格中的移動(dòng)對(duì)象分為一組。

3.2 滿足本地化差分隱私的位置數(shù)據(jù)擾動(dòng)

擾動(dòng)方法需滿足ε-本地化差分隱私，目前，隨機(jī)響應(yīng)機(jī)制是本地化差分隱私的主流技術(shù)[13]。根據(jù)隨機(jī)響應(yīng)的機(jī)制，給定本地化差分隱私參數(shù)ε，每個(gè)用戶發(fā)送自己真實(shí)位置或m-1個(gè)假位置中的某個(gè)位置的概率分別為：

下面將證明算法1的隱私保護(hù)度和數(shù)據(jù)可用性。

3.3 查詢結(jié)果的估計(jì)

經(jīng)過擾動(dòng)后的數(shù)據(jù)主要用來進(jìn)行空間范圍查詢。如何在擾動(dòng)數(shù)據(jù)上獲得較為精確的查詢結(jié)果是本節(jié)的內(nèi)容。

本文涉及的空間查詢分為以下三種情況：

的前半部分與1）中計(jì)算方式相同，關(guān)鍵是如何計(jì)算i。之前的工作都是假設(shè)移動(dòng)對(duì)象在空間范圍內(nèi)均勻分布，因此誤差較大。本文采用的方法能降低誤差，在3）情況中重點(diǎn)介紹。

3）空間范圍查詢Q的區(qū)域R只在某個(gè)維諾格內(nèi)部。則Q（R）需要評(píng)估區(qū)域R在維諾格內(nèi)部的移動(dòng)對(duì)象個(gè)數(shù)i。下面證明當(dāng)ε取何值時(shí)能保證Q（R）是|R|的無偏估計(jì)。

假設(shè)區(qū)域R中的用戶數(shù)占維諾格內(nèi)用戶總數(shù)的比例為π，則，發(fā)送真實(shí)位置的用戶比例及發(fā)送虛假位置的用戶比例分別為：

4 實(shí)驗(yàn)分析

本文采用真實(shí)數(shù)據(jù)集對(duì)算法進(jìn)行測試。GOWALLA數(shù)據(jù)集來自于Gowalla網(wǎng)站上的用戶簽到數(shù)據(jù)，采集時(shí)段為2009-02—2010-10。BRIGHTKITE數(shù)據(jù)集抓取了Brightkite網(wǎng)站上自2008-04—2010-10的用戶簽到數(shù)據(jù)。路網(wǎng)數(shù)據(jù)采用加利福尼亞州的路網(wǎng)數(shù)據(jù)，該路網(wǎng)包含了21693條邊及104407個(gè)興趣位置。

預(yù)處理之后的實(shí)驗(yàn)數(shù)據(jù)集屬性如表1所示?？梢钥闯觯瑥挠脩裘芏燃芭d趣位置（Point Of Interest， POI）均簽到次數(shù)來看，BRIGHTKITE數(shù)據(jù)集都比GOWALLA數(shù)據(jù)集稀疏。由于BRIGHTKITE數(shù)據(jù)集用戶數(shù)目較GOWALLA數(shù)據(jù)集少，因此，BRIGHTKITE數(shù)據(jù)集的人均簽到次數(shù)較多。

在定理1保證了算法隱私保護(hù)度的前提下，實(shí)驗(yàn)主要從相對(duì)誤差及算法運(yùn)行時(shí)間兩方面展開，并與保護(hù)隱私的軌跡數(shù)據(jù)采集（Privacy-preserving Trajectory Data Collection， PTDC）算法[15]進(jìn)行了對(duì)比。

4.1 相對(duì)誤差

本實(shí)驗(yàn)主要測試在擾動(dòng)數(shù)據(jù)集上的空間范圍查詢的精確度。首先，我們先對(duì)加州路網(wǎng)用維諾圖進(jìn)行劃分，然后，每個(gè)用戶簽到過的位置用本文提出的算法進(jìn)行擾動(dòng)，將擾動(dòng)后的位置發(fā)送給服務(wù)器。實(shí)驗(yàn)主要驗(yàn)證在這些噪聲位置數(shù)據(jù)上進(jìn)行空間范圍查詢的精確度和運(yùn)行時(shí)間。

采用文獻(xiàn)[6]中用到的相對(duì)誤差來衡量空間范圍查詢的精確度，這也是空間衡量空間范圍查詢精確度的典型標(biāo)準(zhǔn)。用A（q）表示在原始數(shù)據(jù)上執(zhí)行查詢q的結(jié)果，用（q）表示在擾動(dòng)數(shù)據(jù)上執(zhí)行查詢q的結(jié)果，相對(duì)誤差可表示為：

其中，s是一個(gè)用來避免查詢Q的選擇性太強(qiáng)的常數(shù)，本實(shí)驗(yàn)中，s=0.001×|D|，其中，|D|表示數(shù)據(jù)集中的采樣位置數(shù)目。本實(shí)驗(yàn)共生成了5個(gè)空間范圍查詢：Q1～Q5，其空間范圍大小分別為實(shí)驗(yàn)數(shù)據(jù)集所在空間面積的5%、10%、15%、20%、40%。每個(gè)查詢分別執(zhí)行50次，最終圖5中展示的是50次查詢的平均相對(duì)誤差。

從圖5中可以看出，查詢Q1到Q5在GOWALLA數(shù)據(jù)集上的相對(duì)誤差比在BRIGHTKITE上的誤差小，這是由于BRIGHTKITE數(shù)據(jù)集比GOWALLA數(shù)據(jù)集稀疏。從查詢Q1到查詢Q5，查詢選擇性越來越低，相對(duì)誤差也逐漸減小;另外，隨著ε值的增長，用戶有更高的概率響應(yīng)真實(shí)位置，相對(duì)誤差逐漸降低。

PTDC算法是利用k-匿名技術(shù)保護(hù)隱私的位置數(shù)據(jù)采集算法，其隱私保護(hù)度低于本文提出的滿足本地化差分隱私的位置數(shù)據(jù)采集算法。表2展示了兩個(gè)算法的相對(duì)誤差的對(duì)比情況，兩個(gè)算法均在GOWALLA數(shù)據(jù)集上運(yùn)行，其中ε-LDP算法采用Q5查詢。

從表2的空間范圍查詢誤差率的對(duì)比結(jié)果可以看出，兩個(gè)算法在查詢相對(duì)誤差上差距不大，但理論證明顯示：ε-LDP算法在隱私保護(hù)度上優(yōu)于PTDC算法。

4.2 運(yùn)行時(shí)間

本實(shí)驗(yàn)主要測試算法的可擴(kuò)展性，本實(shí)驗(yàn)主要測試在執(zhí)行查詢分析的服務(wù)器端的運(yùn)行時(shí)間，實(shí)驗(yàn)采用的計(jì)算機(jī)的CPU是2.4GHz i7，內(nèi)存4GB。本實(shí)驗(yàn)將原始數(shù)據(jù)的位置數(shù)據(jù)分別取出25%、50%、75%、100%構(gòu)造4個(gè)新的數(shù)據(jù)集，將查詢Q1在這四個(gè)數(shù)據(jù)集上分別運(yùn)行50次取平均時(shí)間，ε分別取值0.25和1，得到結(jié)果如圖6所示。

從圖5的實(shí)驗(yàn)結(jié)果中可以看出，隨著位置數(shù)據(jù)數(shù)量的增加，運(yùn)行時(shí)間基本上呈線性增加，在最壞的情況下運(yùn)行時(shí)間不超過9s。ε取值對(duì)算法的運(yùn)行時(shí)間幾乎沒有影響。可以預(yù)見，本文提出的算法在數(shù)據(jù)量增加時(shí)，運(yùn)行時(shí)間可呈線性增加。

本文對(duì)ε-LDP算法和PTDC算法的運(yùn)行時(shí)間作了對(duì)比，如表3所示，ε-LDP算法采用Q1查詢。對(duì)于ε-LDP算法來說，參數(shù)ε的大小與隱私保護(hù)度相關(guān);PTDC算法中，參數(shù)k與隱私保護(hù)度相關(guān)。從表3中可以看出，ε-LDP算法的運(yùn)行時(shí)間與算法的隱私保護(hù)度無關(guān)，而PTDC算法的運(yùn)行時(shí)間隨著隱私保護(hù)度的提高增加，ε-LDP算法在運(yùn)行效率上略高于PTDC算法。

5 結(jié)語

隨著人們對(duì)個(gè)人隱私問題的關(guān)注，在數(shù)據(jù)流出用戶設(shè)備之前就進(jìn)行隱私保護(hù)的方式更加安全。本文提出了一種滿足本地化差分隱私的位置數(shù)據(jù)采集方法，使用維諾圖分割路網(wǎng)空間，采用隨機(jī)擾動(dòng)的方式對(duì)每個(gè)維諾格中的位置數(shù)據(jù)進(jìn)行擾動(dòng)。在此基礎(chǔ)上，設(shè)計(jì)了一種在擾動(dòng)數(shù)據(jù)集上進(jìn)行空間范圍查詢的方法，可獲得對(duì)真實(shí)結(jié)果的無偏估計(jì)。最后，通過實(shí)驗(yàn)中對(duì)本文提出的方法進(jìn)行了驗(yàn)證，并與基于k-匿名的保護(hù)隱私方法PTDC進(jìn)行了對(duì)比，ε-LDP算法和PTDC算法的平均查詢相對(duì)誤差相近，然而，ε-LDP算法的隱私保護(hù)度更高。在運(yùn)行時(shí)間上，ε-LDP算法的運(yùn)行時(shí)間較穩(wěn)定，和隱私保護(hù)度無關(guān)。

參考文獻(xiàn)（References）

[1] 黃毅，霍崢，孟小峰.CoPrivacy：一種用戶協(xié)作無匿名區(qū)域的位置隱私保護(hù)方法[J].計(jì)算機(jī)學(xué)報(bào)，2011，34（10）：1976-1985.（HUANG Y， HUO Z， MENG X F. CoPrivacy： a collaborative location privacy-preserving method without cloak region [J]. Chinese Journal of Computers， 2011， 34（10）： 1976-1985.）

[2] SEI Y， OHSUGA A. An algorithm for privacy-preserving location data collection by probabilistic dummy generation [J]. IEEE Transactions on Electronics Information and Systems， 2015， ?135（6）： 660-670.

[3] ZHANG L， ZHANG W. Generalization-based privacy-preserving data collection [C]// Proceedings of the 2008 International Conference on Data Warehousing and Knowledge Discovery. Berlin： Springer， 2008： 115-124.

[4] HIGUCHI T， MARTIN P， CHAKRABORTY S， et al. AnonyCast： privacy-preserving location distribution for anonymous crowd tracking systems [C]// UbiComp '15： Proceedings of the 2015 ACM International Joint Conference on Pervasive and Ubiquitous Computing. New York： ACM， 2015： 1119-1130.

[5] GIDOFALVI G， HUANG X， PEDERSEN T B. Privacy： preserving trajectory collection [C]// GIS '08： Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York： ACM， 2008： Article No. 46.

[6] NGUYEN T T， XIAO X， YANG Y， et al. Collecting and analyzing data from smart device users with local differential privacy. 2016， arXiv， Bibliographic Code：2016arXiv160605053N.

NGUYEN T T， XIAO X， YANG Y， et al. Collecting and analyzing data from smart device users with local differential privacy [EB/OL]. [2018-06-19]. https：//arxiv.org/pdf/1606.05053.pdf.

[7] QIN Z， YANG Y， YU T， et al. Heavy hitter estimation over set-valued data with local differential privacy [C]// CCS '16： Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. New York： ACM， 2016： 192-203.

[8] TO H， GHINITA G， SHAHABI C. A framework for protecting worker location privacy in spatial crowdsourcing [C]// Proceedings of the 2014 VLDB Endowment. Berlin： Springer， 2014： 919-930.

TO H， GHINITA G， SHAHABI C. A framework for protecting worker location privacy in spatial crowdsourcing [J]. Proceedings of the VLDB Endowment， 2014， 7（10）： 919-930.

[9] CHEN R， LI H， QIN A K， et al. Private spatial data aggregation in the local setting [C]// Proceedings of the 2016 IEEE 32nd International Conference on Data Engineering. Washington DC： IEEE Computer Society， 2016： 289-300.

[10] DWORK C. Differential privacy [C]// ICALP '06： Proceedings of the 33rd International Conference on Automata， Languages and Programming. Berlin： Springer， 2006： 1-12.

[11] DWORK C， LEI J. Differential privacy and robust statistics [C]// STOC '09： Proceedings of the 41st Annual ACM Symposium on Theory of Computing. New York： ACM， 2009： 371-380.

[12] XIONG S， SARWATE A D， MANDAYAM N B. Randomized requantization with local differential privacy [C]// Proceedings of 2016 IEEE International Conference on Acoustics. Washington， DC： IEEE Computer Society. 2016： 2189-2193.

[13] WARNER S L. Randomized response： a survey technique for eliminating evasive answer bias [J]. Journal of the American Statistical Association， 1965， 60（309）： 63-69.

[14] PAN X， WU L， HU Z， et al. Voronoi-based spatial cloaking algorithm over road network [C]// Proceedings of the 2014 International Conference on Database and Expert Systems Applications. Berlin： Springer， 2014： 273-280.

[15] 霍崢，王衛(wèi)紅，曹玉輝.PTDC：路網(wǎng)環(huán)境中感知隱私的軌跡數(shù)據(jù)采集技術(shù)[J].計(jì)算機(jī)應(yīng)用，2017：37（9）：2567-2571.

（HUO Z， WANG W H， CAO Y H. PTDC： privacy-aware trajectory data collection technology under road network constraint [J]. Journal of Computer Applications， 2017， 37（9）： 2567-2571.）