霍崢 張坤 賀萍 武彥斌

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

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

中圖分類號： TP311.13

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

文章編號：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ù)和移動定位設(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ù)包含大量的敏感信息，用戶通常情況下會無償?shù)刎暙I(xiàn)自己的位置數(shù)據(jù)，卻承擔(dān)著個人隱私泄露的巨大風(fēng)險，隨著人們對個人隱私問題的關(guān)注，使用這種數(shù)據(jù)采集方式的發(fā)展趨勢并不樂觀。制約眾包位置數(shù)據(jù)采集的關(guān)鍵問題是移動對象的個人隱私問題。

數(shù)據(jù)收集者收集了移動對象的位置數(shù)據(jù)，并對大量的數(shù)據(jù)進(jìn)行分析和挖掘，得出某些結(jié)論便于優(yōu)化城市道路規(guī)劃、制定商業(yè)決策等。然而，在上述數(shù)據(jù)采集方式中，有兩個重要的假設(shè)：第一，移動對象愿意提供精確的位置給數(shù)據(jù)采集者;第二，數(shù)據(jù)收集者是可信的，不會惡意出售數(shù)據(jù)或者將數(shù)據(jù)泄露給第三方。但是，上述兩個假設(shè)在大多數(shù)情況下是不成立的，這是因為：第一，隨著人們對個人隱私的關(guān)注，越來越多的用戶并不愿意共享自己的精確位置數(shù)據(jù);第二，大量數(shù)據(jù)收集者是不可信的，社會上出現(xiàn)了很多服務(wù)提供商出售用戶的個人數(shù)據(jù)，從而導(dǎo)致隱私泄露的嚴(yán)重問題。即使數(shù)據(jù)收集者可信，惡意攻擊者也可能攻擊數(shù)據(jù)收集者的服務(wù)器，導(dǎo)致大量的個人數(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ā)送自己的真實位置的同時，發(fā)送若干個根據(jù)某種規(guī)則產(chǎn)生的假位置進(jìn)行混淆;文獻(xiàn)[3]提出了一種基于數(shù)據(jù)泛化的感知隱私的數(shù)據(jù)采集方法。每個用戶在發(fā)送自己的數(shù)據(jù)之前，先找到匿名組匿名，然而，達(dá)到最佳匿名效果是NP（Non-deterministic Polynomial）-難問題。上述兩種方法都無法達(dá)到強(qiáng)隱私保護(hù)的效果。近年來出現(xiàn)的本地化差分隱私技術(shù)（Local Differential Privacy， LDP）[4]是解決該問題的最佳方法。本地化差分隱私模型中，客戶端首先對原始數(shù)據(jù)進(jìn)行擾動，然后再發(fā)送給數(shù)據(jù)收集服務(wù)器，數(shù)據(jù)收集服務(wù)器在擾動的數(shù)據(jù)上作分析統(tǒng)計，得到有效的分析結(jié)果。在此過程中，即使數(shù)據(jù)收集服務(wù)器也無法得到用戶精確的位置數(shù)據(jù)，從而實現(xiàn)了個人位置隱私保護(hù)。

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

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

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

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

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

1 相關(guān)工作

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

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

2 預(yù)備知識

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

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

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

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

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

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

定義1給出了LDP的定義。

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

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

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

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

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

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

2.3 攻擊模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 實驗分析

本文采用真實數(shù)據(jù)集對算法進(jìn)行測試。GOWALLA數(shù)據(jù)集來自于Gowalla網(wǎng)站上的用戶簽到數(shù)據(jù)，采集時段為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個興趣位置。

預(yù)處理之后的實驗數(shù)據(jù)集屬性如表1所示?？梢钥闯?，從用戶密度及興趣位置（Point Of Interest， POI）均簽到次數(shù)來看，BRIGHTKITE數(shù)據(jù)集都比GOWALLA數(shù)據(jù)集稀疏。由于BRIGHTKITE數(shù)據(jù)集用戶數(shù)目較GOWALLA數(shù)據(jù)集少，因此，BRIGHTKITE數(shù)據(jù)集的人均簽到次數(shù)較多。

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

4.1 相對誤差

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

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

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

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

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

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

4.2 運(yùn)行時間

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

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

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

5 結(jié)語

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

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

[1] 黃毅，霍崢，孟小峰.CoPrivacy：一種用戶協(xié)作無匿名區(qū)域的位置隱私保護(hù)方法[J].計算機(jī)學(xué)報，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ī)應(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.）