滿足本地化差分隱私的眾包位置數據采集

霍崢 張坤 賀萍 武彥斌

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

關鍵詞：本地化差分隱私;道路網絡;維諾格;位置數據;移動對象

中圖分類號： TP311.13

文獻標志碼：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 引言

隨著定位技術和移動定位設備的發展，越來越多的位置數據被采集后，用來進行位置數據分析和挖掘。眾包數據采集應運而生。所謂眾包數據采集是指：使用人們的群體數據完成眾多的數據挖掘任務，使挖掘結果能更好地服務于人們的生活。例如，高德地圖目前每天產生的軌跡數據中，有72%都來自眾包，也就是使用地圖的用戶。然而，位置數據包含大量的敏感信息，用戶通常情況下會無償地貢獻自己的位置數據，卻承擔著個人隱私泄露的巨大風險，隨著人們對個人隱私問題的關注，使用這種數據采集方式的發展趨勢并不樂觀。制約眾包位置數據采集的關鍵問題是移動對象的個人隱私問題。

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

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

本文主要研究本地化差分隱私技術在空間位置數據收集上的應用，具體來說，本文的主要貢獻如下：

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

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

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

4）最后，通過實驗對本文提出的方法進行了驗證，證明本文提出的方法在數據可用性、算法效率及可擴展性上具有優勢。

1 相關工作

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

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

2 預備知識

下面介紹本文算法的預備知識。

2.1 系統結構

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

本文研究問題的系統結構如圖1所示。客戶端的數據經過擾動之后發送給服務器，服務器端包含地圖劃分、用戶分組、查詢結果優化三個模塊。其中查詢結果優化模塊可幫助服務器用擾動后的位置數據獲取較為精確的空間范圍查詢結果。

2.2 本地化差分隱私技術

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

定義1給出了LDP的定義。

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

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

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

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

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

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

2.3 攻擊模型

攻擊者可能是來自于系統結構中的任意一方。本文假設服務器也是不可信的，即，服務器也可能想要獲知移動對象的位置。攻擊者最大的目的就是獲取移動用戶的精確位置。攻擊模式可能是窺探、背景知識關聯、服務器與移動用戶串謀等多種方式。

3 滿足本地化差分隱私的位置數據采集算法

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

數據流向如圖3所示。

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

3.1 基于維諾格的路網劃分

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

3.2 滿足本地化差分隱私的位置數據擾動

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

下面將證明算法1的隱私保護度和數據可用性。

3.3 查詢結果的估計

經過擾動后的數據主要用來進行空間范圍查詢。如何在擾動數據上獲得較為精確的查詢結果是本節的內容。

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

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

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

假設區域R中的用戶數占維諾格內用戶總數的比例為π，則，發送真實位置的用戶比例及發送虛假位置的用戶比例分別為：

4 實驗分析

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

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

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

4.1 相對誤差

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

采用文獻[6]中用到的相對誤差來衡量空間范圍查詢的精確度，這也是空間衡量空間范圍查詢精確度的典型標準。用A（q）表示在原始數據上執行查詢q的結果，用（q）表示在擾動數據上執行查詢q的結果，相對誤差可表示為：

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

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

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

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

4.2 運行時間

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

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

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

5 結語

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

參考文獻（References）

[1] 黃毅，霍崢，孟小峰.CoPrivacy：一種用戶協作無匿名區域的位置隱私保護方法[J].計算機學報，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] 霍崢，王衛紅，曹玉輝.PTDC：路網環境中感知隱私的軌跡數據采集技術[J].計算機應用，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.）