满足本地化差分隐私的众包位置数据采集

霍峥 张坤 贺萍 武彦斌

摘 要：针对位置数据众包采集中个人位置隐私泄露的问题，提出了一种满足本地化差分隐私的位置数据众包采集方法。 首先，使用逐点插入法构造维诺图，对路网空间进行分割;然后，采用满足本地化差分隐私的随机扰动的方式对每个维诺格中的位置数据进行扰动;再次，设计了一种在扰动数据集上进行空间范围查询的方法，获得对真实结果的无偏估计;最后，在空间范围查询下进行了实验验证，并与保护隐私的轨迹数据采集（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.）