车连基础安全 9

第10章

车联网中基于差分隐私的

位置扰动方案10.1引言10.2预备知识和系统模型10.3方案设计10.4方案分析10.5实验本章小结

10.1引

言

计算和通信技术以及云基础设施的最新发展使得在不久的将来实现智慧城市成为可能。车辆可享受的服务也将越来越多。其中，在车辆可以享受的各种服务中，基于位置的服务使车辆可以随时访问与其行踪有关的大量信息。在LBS中，基于位置的服务提供商(LSP)能够基于车辆所处位置为车辆提供有关附近加油站、休息区和酒店等的有用信息。LBS具有众多吸引人的功能，已成为IoV生态系统的重要组成部分[295]。但是，服务提供商可能会从车辆中收集大量的位置信息，这些位置信息可能会被误用于推断驾驶员不希望被知道的敏感信息，例如其家庭住址、政治观点和性取向等[296]。

为了给LBS提供隐私保护，研究人员已经提出了一些利用加密工具的基于加密的方法，例如同态加密和私有信息检索(PIR)[20，297300]。但是，这些方法都需要昂贵的计算成本，并且与现有的LBS不兼容，导致可行性较差[296]。为了提供更可行的解决方案，研究人员已经进行了一系列工作来探索这个问题，主要是把计算的隐私模型(如K匿名[301]、L多样性[302]和T紧凑[303])引入位置隐私中。由于这些方法是基于启发式方法的，因此它们不能提供正式的隐私保证[304306]。为了解决这个问题，将差分隐私[290]应用于二维空间，Andrés等人[140]提出了一种流行的LBS隐私模型，称为地理不可分辨性(Geo-Ind)。

按照这种模型，当用户选择查询LBS时，首先会通过向其添加随机噪声来扰动自己的位置，然后指定检索区域的大小。通过向LSP报告扰动位置和检索大小，用户可以获取周围的附近兴趣点(POI)。与LBS的其他隐私模型相比，Geo-Ind的吸引人之处在于，它可以防止推断出用户的真实位置，同时与对手的先验知识无关。因此，它被用作LBS的几种隐私保护应用的组成部分[307310]，并成为位置隐私事实上的标准。

尽管Geo-Ind可以防止推断位置信息，但在现实世界中，隐私的概念是多维的[311，312]。除了真实位置之外，车辆用户打算隐瞒其位置的行为还可以揭示其他一些隐私信息[313]。具体来说，如果服务提供商可以在LBS查询中识别出车辆已经干扰了自己的位置，即使他无法推断出车辆的真实位置，也可以知道驾驶员隐藏行踪的动机。此外，通过找出车辆用户喜欢何时以及多久扰动一次自己的位置，服务器可以学习隐私偏好[314]来推测驾驶员的个性特征[315–317]。例如，Raber等人[318320]发现，性格外向、思想开放的人倾向于更慷慨地公布自己的确切位置，而神经质和尽职尽责的性格则导致位置混淆的程度更高。有了这些个性信息，服务提供商便可以将针对性的垃圾邮件或诈骗信息发送至车辆以获取商业利润。

更糟的是，Acquisti等人[316321]发现，当个人的隐私偏好被披露时，对手就有可能利用微妙的应用设计来获得意想不到的对用户的见解。例如，他们发现，通过精心设计应用程序的默认共享设置，服务提供商可以制造出一种安全错觉，并令驾驶员愿意披露其敏感信息。

如图10.1所示，这种类型的隐私威胁远远超出了Geo-Ind的控制范围，其中Geo-Ind仅能阻止推断出真实位置，而扰动行为本身却可以揭示更广泛的隐私。但是，通过实验发现，经典的Geo-Ind机制将真实位置扰动到不合理区域的可能性可能超过50%，这导致驾驶员的扰动行为被大量暴露。图10.1应用Geo-Ind造成的隐私泄露

为了解决这些问题，必须保护车辆用户的扰动行为不被识别，本章提出了新的隐私概念以提供增强的隐私保证。注意到LSP识别扰动行为的最可行的简单方法是识别不合理的报告位置，其中该位置几乎不可能出现车辆。因此，至关重要的是确保所报告位置的真实性而不泄露用户的位置信息。为此，设计了一种新颖的隐私保护机制来实现新的隐私定义，并提出了一种算法来保证LBS查询的准确性。本章主要内容如下：

(1)提出了一个新的隐私定义，称为扰动隐藏(Perturbation-Hidden)，为基于位置的服务提供比Geo-Ind更严格的隐私保证。与Geo-Ind相比，Perturbation-Hidden旨在消除因识别出车辆用户的干扰行为而导致的隐私泄露。

(2)设计了一种隐私保护机制来实现隐私定义。具体来说，就是将地图平面抽象为网格，并以用户指定的属性作为候选集来考虑合理的位置。然后，从数据库领域借鉴差分隐私指数机制，以在离散选择之间生成扰动位置，而不会泄露任何隐私。

(3)为了保证查询的准确性，提出了一种确定检索区域半径的方法。具体来说，就是对查询结果的准确性进行概率分析，然后通过动态规划确定检索半径，以找到给定精度要求的最小值。这样，用户可以自适应地定义LBS查询的准确性。

(4)通过理论分析和实验结果来评估本章方案。首先，从理论上证明隐私保护机制满足Perturbation-Hidden的概念。然后，在模拟和广泛使用的现实世界数据集上进行广泛的实验。结果表明，本章方案可以实现100%合理的扰动位置，同时确保较高的查询精准率和召回率。

10.2预备知识和系统模型

在本节中，首先简单介绍后文中要用到的预备知识，然后介绍后续讨论所依赖的系统模型以及试图实现的隐私目标。表10.1总结了本章常用的符号。

10.2.1差分隐私和地理不可区分性

差分隐私最早提出于统计数据库领域[306]，用来解决聚合查询结果可能导致的隐私泄露问题，是一种可以对隐私提供严格定义与保护的概念。相比于其他隐私定义(K匿名等)，差分隐私具有与攻击者背景知识无关以及能够量化隐私损失等优点。当输入数据集非常接近时，差分隐私要求输出的分布也十分接近以使得攻

击

者

无

法

以

一

个

显

著

的

概

率(SignificantProbability)通过输出来区分输入。差分隐私的定义如下。

定义10.2(地理不可区分性)

随机化算法

K：X→P(Z)满足ε

地理不可区分性，当且仅当∀x，x'∈X，都有d(K(x)，K(x'))≤εd(x，x')。

地理不可区分性的直观含义是对任何两个接近的位置，混淆机制将它们扰动到同一个位置点的概率也应当十分接近。上述定义中两个位置点间的距离越小，要求的隐私强度越高；如果用户期望在较大的范围内获得更高的隐私水平，则应当选取更小的ε值。

10.2.2系统模型

在本小节中，主要讨论三方面的内容，分别是针对车辆用户的LBS服务过程的系统模型、威胁模型以及本章所提方案的基本设置。

在工作中，车辆用户向服务提供商发送带有位置的LBS查询，以获取附近POI的列表和详细信息(例如找到附近的加油站或酒店)。用户希望从LBS获得实用程序，并可以选择是否将其行踪保密。如果车辆用户喜欢保护位置隐私，可以在自己的真实位置添加噪音，并将此架噪的位置发送给LSP，而如果用户出于便利或LBS固有的隐私与服务质量间的权衡而不愿扰动位置[296]，则可发送自己的真实位置。LBS服务过程的系统模型如图10.2所示。图10.2系统模型

下面讨论LBS服务过程的威胁模型，该模型给出了有关对手的假设。在基于位置的服务中，服务提供商通常被认为是诚实且好奇的，也就是说，他将诚实地回答LBS查询，同时观察接收到的查询中的位置信息，然后尝试了解有关查询用户的更多信息。因此，对手的第一个目标是了解车辆是否在查询中干扰了其位置，第二个目标是如果他判断车辆的位置已被干扰，则通过先验知识进一步推断车辆的真实位置。此外，值得注意的是，服务提供商识别扰动行为的最可行、最简单的方法是识别出不合理的位置，而该位置几乎是不可能出现用户的。因此，在威胁模型中，假设对手根据报告位置的地域合理性可识别出车辆使用者的扰动行为。例如，如果对手识别出地理位置不合理的报告位置，如实际不太可能存在车辆的湖泊、沼泽和崎岖的山脉，则他可判断车辆用户在此查询中已经扰动了自己的位置。

本章将地图平面视为具有欧几里得距离的笛卡尔平面，并将其划分为网格以方便计算机处理。此外，将网格中的一个单元视为位置的基本单位，并将两个特定位置之间的距离定义为其几何中心点之间的欧几里得距离。此外，为建立新模型的研究基础，本章仅讨论单个LBS查询情况下的问题。

10.2.3隐私目标

车辆用户可以基于其隐私偏好选择是否在查询中干扰其位置。如果用户选择干扰位置，则必须从两个方面保护自己的隐私。不仅要求对手无法识别车辆使用者的扰动行为，而且还要求在选择扰动车辆后不能推断出其确切位置，即隐私保护机制要满足Geo-Ind。对隐私目标的描述如下。

定义10.3(扰动隐藏)在LBS的隐私保护中，如果位置扰动机制满足以下属性，则称其满足“扰动隐藏”的要求。

(1)事件隐私属性。对手判断所报告位置是否受到干扰的成功率不超过ψ=max(η1，η2)，其中η1

表示车辆用户在查询时选择位置扰动的概率，η2

表示未选择位置扰动的概率。

(2)推断隐私属性。位置扰动机制满足ε－地理不可区分性。

“扰动隐藏”可以防止由于识别出车辆用户的扰动行为而导致的隐私泄露。事件隐私属性可确保对手无法找到一种更好的方法来确定车辆用户是否扰动了自己的位置，而不是天真地将报告的位置视为始终(或不被)扰动。此外，推断隐私属性可确保一旦正确猜出了车辆用户将自己的位置进行了扰动，对手仍然无法通过可观察的报告位置来推断其真实位置。在图10.2中可以看出，在不敏感的位置时，车辆用户更愿意在不扰动的情况下查询更好的服务质量，这使其仍然可以享受事件隐私属性，而不再需要推断隐私属性。

10.3方

案

设

计

10.3.1扰动方案设计当车辆用户希望在LBS查询中保护自己的隐私时，首先根据其指定的属性选择可能的受扰动位置的合理侯选区域，以满足对“扰动隐藏”事件隐私属性的要求。然后，将差分隐私指数机制应用于地图平面，以满足“扰动隐藏”的推断隐私属性。

下面介绍产生扰动位置的具体方法。当请求用户的真实位置为x0∈R2

且需要获取周围的兴趣点(POI)时，扰动机制产生z∈R2

作为提交位置[308，309]，其中z

是由随机化函数K

选取的一定地图区域δ内满足合理性判别的位置集合Xδ={xi|i∈N*，1≤i≤n}中的某一位置xi，即有z=xi。另外，为了使扰动位置与用户真实位置不同，令x0∉Xδ。如图10.3所示，取δ为用户所在的一块10×10地图平面，其中深色区域代表合理位置，浅色区域代表不合理位置，用户所在位置为x0，除用户所在位置外的深色区域构成Xδ，其中的每一个网格代表xi。扰动机制通过算法

K

汇报混淆位置z

给服务器实现位置扰动，其中z

在Xδ

中产生。在图10.3中可以看到，要确保始终在Xδ

中生成z，车辆应用程序必须获取有关δ

中每个位置的合理性状态的信息。由于此过程的技术性独立于扰动机制，因此将在10.3.3节讨论此问题并详细地描述解决方案。图10.3位置扰动示例

为获取可证明的位置隐私保护水平，随机化函数

K

需满足地理不可区分性，即以x0周围一定区域内的任何位置x'0作为输入产生相同扰动位置z

作为输出的概率相差不超过一个乘数因子eεd(x0，x0')。为了实现这一点，需要使选择xi作为扰动位置的概率随其与x0

间距离的增大而指数减小。

从广义差分隐私[290]的思想中吸取经验，将指数机制应用于地图平面以实现位置扰动，并从类比的角度来理解这种借鉴。传统的指数机制作用于统计数据集，并保护两个最大汉明距离相差不大的数据库。在将其应用于地图平面时，首先需要弄清楚在这种情况下指数机制的本质保护范围。为了对此进行讨论，以车辆用户的位置为基点，并将离散的平面区域

Xδ

抽象为数据库格式。在这种情况下，数据库中的记录可以视为从x0

到Xδ

中所有位置的单位长度的段，如表10.2所示。

表10.2中，ω

为单位距离的长度设定，θi(j)表示从x0到xi

的第j

单位距离向量在以x0

为圆心的极坐标下的偏离角，显然有θi(1)=θi(2)=…=θi(j)；σi∈R*

且当第l号向量是x0与xi之间首尾相接的最后一段向量且ω+d(x0，xi)时0<σi<1，否则σi=1。抽象的示意图如图10.4所示，以4个位置(xi，xl，xv，xn)作为样本来说明

Xδ

和数据集之间的对应关系。图10.4表10.2的图示

由于差分隐私保护，单个记录是否在数据集中不能为攻击者所推断，而单位距离的选取直接决定了数据集中记录粒度的大小，因此采用差分隐私保护后，攻击者无法通过输出判断x0

与其他用户间是否存在任意一段特定的单位长度的距离。例如，当单位距离选取较小(如1m)时，数据集中记录粒度较小，受差分隐私保护的单位距离长度也较小，当ε固定时隐私强度也相应较小；而当单位距离选取较大(如1km)时，数据集中记录粒度较大，受到隐私保护的单位距离长度也较大，在相同的ε下隐私强度也较大。对这一问题的形式化分析在10.4.2节中给出。

为使用户在自身所在范围内始终享有隐私保护，且受保护程度随着与用户距离的增加而减小[140]，定义中Xδ

中每个元素xi

的效用为u(x0，xi)=-d(x0，xi)。由于定义的效用函数u本质上是表10.2中所表示的数据库上计数查询的负值，因此就其敏感性而言，有Δu=1。在这种情况下，ε表示为一个单位长度提供的隐私级别，即一个单位长度的距离。之前研究已经提到隐私级别受测得的单位距离的影响，但没有说明这一特性来源于标准差分隐私及其中的敏感度定义。

接下来，给出选择输出Xδ

内的元素的具体方法，如算法10.1所示。

算法10.1的时间和空间复杂度均为O(n)，其中n=|

Xδ

|。该机制将z

报告为扰动位置，并确定相应的检索范围以获取附近的POI。在10.4.1节中，证明了这种位置扰动机制可以满足“扰动隐藏”的要求。

10.3.2确定检索范围

在要求查询LBS时，车辆用户不仅需要发送其位置，还需要确定使服务器进行检索的检索区域(AOR)。为了与现有应用程序(如AMAP、GoogleMap)兼容，这里将AOR视为一个圆圈。此外，车辆用户还可以选择是否在查询中干扰其位置。如果用户不想隐藏自己的行踪，那么可直接向LSP发送查询，该查询包括用户的真实位置、感兴趣区域的半径(AOI)和所需POI的关键字，以获取查询结果。如果用户想让自己的位置保密，仍然需要向LSP报告位置、AOR的半径以及所需POI的关键字，但是需要仔细处理报告的位置和AOR的半径。就报告的位置而言，如上一部分所述，车辆用户需要调用算法10.1以获得扰动位置z；就AOR而言，由于混淆了真实位置，因此不能简单地将AOR设置为用户的AOI。因为以z为AOR的中心是自然的，所以需要关注AOR的半径并确保查询结果的准确性。

在理想情况下，要求AOR总是包含AOI，此时用户可以获得他期望获得的全部信息。然而，由于扰动位置是以一定概率分布在地图区域δ上随机生成的，且现有研究[140]指出动态地对AOR进行调整以使其总是包含AOI是不安全的(因为这会使攻击者获知用户总是位于AOR内)，因此为了保证用户位置隐私，AOR的设定需要与扰动位置z的产生相独立。基于此，一个LBS应用的精确性定义如下。

定义10.4(LBS应用精确性)一个LBS应用(K，rAOR)是(c，rAOI)精确的，当且仅当对所有位置x∈R2，有C(x，rAOI)被完全包含在C(K(x)，rAOR)内的概率不小于c。其中rAOR与rAOI分别表示AOR与AOI的半径；C(x，r)表示以x

为中心，r

为半径的圆；c为置信因子。目标是在给定(c，rAOI)参数的情况下找到一个合适的rAOR，使得该rAOR在本章所提方案下满足(c，rAOI)精确性。

率Pr(xi

)，则

对

于

z=K(x)有

d(x，z)≤r

的概率至少为

σ(r)=∑xi∈C(x0，r)∩XδPr(xi)，也即当r≥σ-1(α)时，本章所提机制满足文献[323]中提出的(r，α)有用性，其中α∈R且0≤α≤1，为一指定概率。σ-1(α)表示要满足给定的置信水平α、r的取值下界。

显然，如果机制

K

是满足(r，α)有用性的，则当r≤rAOR-rAOI时，LBS应用(K，

rAOR)是(α，rAOI)精确性的，故需要满足rAOR≥rAOI+σ-1(α)，因此令rAOR=rAOI+σ-1(α)以满足精确度需求。在这种情况下，有ζ-1(α)=argmin∑xi∈C(x0，r)∩XδPr(xi)-α

。

然后使用动态规划来计算ζ-1(α)，避免了对算法10.1计算得出的各个位置的相应概率的重复求和。

对于xi∈δ

和xi∉Xδ，Pr(xi)初始化为零。在计算ζ-1(α)的过程中，以每轮一单位长度的步长检验r

逐渐增加时C(x0，r)与δ

的交

点

的

概

率

之

和。累

积

量Prcum表

示

满

足d(x0，xi)≤r

的所有Pr(xi)之和。为此，只要Prcum

尚未满足条件，该算法就连续记录随r增大的Prcum，并记录δ

中各层的起始序数。此外，该算法还记录了各层内的遍历位置。对于每一层中的位置，算法根据x0

与每个位置之间的距离从近到远遍历它们。将一层的顶点位置的概率计入Prcum后，下一轮的层的起始序数增加1。当Prcum第一次大于α

时，此时的r

值为ζ-1(α)时间。

为了在二维平面上实现该算法，将δ表示为矩阵Mδ，其中Mδ

中的每个元素代表相应位置被采样为扰动位置的概率。此外，将x0

在

Mδ中的位置表示为

Mδ(x，y)。该算法的详细信息在算法10.2中给出。

在算法10.2中，列表L

在Mδ

中以Mδ(x，y)为中心记录每层的遍历位置。count记录尚未完全遍历的图层的起始顺序。该算法使用动态规划来找到满足概率要求的r

的最小值，然后计算满足(c，rAOI)精度的rAOI。该算法的时间和空间复杂度均为

O(w)，其中

w是δ

内位置的总数。算法10.2的返回值确定报告给服务器的查询检索半径。

10.3.3扰动方案实现

本小节讨论方案中与实施相关的一些问题。首先描述本章方案在现实世界中的工作过程，然后讨论在IoV中提出该方案的可行性，最后讨论用于客户端应用程序以获取位置合理性状态的解决方案。

本章方案在现实世界中的运作过程如下所述。要查询LBS，车辆用户应首先根据其隐私偏好选择是否混淆其位置。如果用户没有选择混淆，车辆将通过当前的V2X通信(如DSRC、LTEV2X等)将包含真实位置、AOI半径和所需POI关键字的查询直接发送到LSP服务器[313-314]。然后，车辆用户可以从服务器接收附近POI信息的结果以完成服务。如果车辆用户选择混淆位置，则可以通过以下步骤接收LBS的结果。

(1)车辆用户调用算法10.1以获得扰动位置z；

(2)车辆执行算法10.2，以根据用户感兴趣的rAOI获得rAOR；

(3)车辆将z、rAOR和所需POI的关键字发送给服务器；

(4)服务器根据查询在AOR中获取有关POI的信息，然后将结果返回给车辆；

(5)车辆过滤接收到的结果，并将AOI中的POI信息呈现给用户，从而完成服务。

车辆可以在其车载信息娱乐(IVI)系统上部署并执行提出的算法。该系统可以通过将车辆连接到云和其他已连接的服务来提供娱乐和导航等各种应用程序。在IVI系统中，有个集成的头单元(HeadUnit)，它具有自己的处理器、内存和I/O接口，可以安装PC或智能手机支持的操作系统。因此，具有通用集成主机的现代IVI系统可以执行各种数据处理，以向用户提供大量增值服务，如多媒体和LBS等。就车辆执行所提出的算法的可行性而言，要求车辆具有完成服务能力的两个方面，包括计算和数据处理以及与LSP的通信。在计算和数据处理方面，当前的IVI系统通常可以提供导航、音乐和视频播放等服务，涉及编码、解码和着色等复杂任务。

例如，着色算法的平均时间复杂度为O(|Ω|·|chrominance(Ωc)|)，其中Ω

是图像中要进行着色的区域，Ωc

是具有相同色度的像素集[326]。由于提出的算法的最大时间复杂度仅为O(|δ|)，其中δ

是所考虑区域中的一组位置，因此现有IVI系统的集成头单元完全可以处理提出的算法。在通信方面，IoV中的车辆可以通过RSU或基站的数据转发与LSP通信。因此，可以通过各种V2X通信技术(如DSRC、LTEV2X等)进行通信[324，325]。此外，5G技术的兴起使得车辆获得普及服务的难度和效率更高。

注意，本章方案仅要求车辆与服务提供商之间进行一轮通信，通信消耗的带宽开销基本上在2.5KB之内(如10.5.4节所示)，大致相当于0.01s的无损音乐或视频的0.12s。因此，本章方案的通信过程可以通过当前的V2X通信技术和新兴的5G技术轻松完成。

如图10.3所示，要实现隐私保护机制，客户端应用程序需要知道δ中每个位置的合理性状态。由于此任务与机制K无关，并且可以通过各种可能的方法来实现或开发，因此没有给出详细的算法，只是从宏观角度描述了可行的解决方案。

一些先前的著作[327，328]根据每个位置的查询概率来确定位置的合理性。这些研究者认为，如果在特定位置的查询概率非常低，那么这在地理上是不可能的。尽管这个想法很有启发性，但不适用于随机扰动车辆位置的范例。由于行踪保密的车辆用户报告的位置都已被随机扰动，因此没有人(包括LSP)可以得出位置上的真实查询概率分布。此外，当车辆使用者到达其他人之前从未到达的区域时，该方法也是完全失败的。

因此，为避免这些问题，本书作者认为基于地形知识的地理似然性是一种有前途的探索方法。车辆用户可以在本地设置和修改合理性首选项，以控制允许的地形属性，以便扰动位置始终是用户认为自己可能出现的位置。由于可选属性的数量远小于系统中的车辆数量，并且可以在本地处理首选项设置，因此此过程不会揭示车辆用户的隐私。此外，由于地形知识非常直观且几乎固定，因此可以允许LSP或Internet服务提供商(ISP)的基站进行维护，并在需要时将

其

发

送

给

车

辆。他们维护的地形知识可以通过知识工程如GoogleStreetView[329]来获得，也可以通过构建地理标记的地图数据集，然后采用基于机器学习的方法来使其自动完成[330332]。

使用地形知识作为合理性基础的优势在于，由于它是直观且几乎固定的，如果LSP或ISP想要用虚假的地形信息来欺骗车辆，则车辆用户将很容易发现这种欺骗并选择其他提供商来实现服务。企图欺骗用户最终会导致用户流失，这为提供者保持诚实提供了经济激励。

10.4方

案

分

析

且

定理10.1

提出的方案满足扰动隐藏。

证明

将引理10.1和引理10.2结合起来，可以直接证明定理10.1。

10.4.2单位距离设定对方案的影响

10.5实

验

10.4的方案分析肯定了本章所提方案的安全性，本节主要通过实验检查其实用性。首先，在距离误差方面对提出的方案与平面拉普拉斯机制进行分析和比较；然后，将重点放在对不合理的位置的抵抗上，并与平面拉普拉斯机制进行比较；最后，在实际的LBS应用中，研究了当车辆位于北京五环路以内时带宽开销的性能。实验中设定衡量距离的单位长度ω为1m，将δ

划分为粒度为1000×1000的网格平面，其中任何单个单元的边长为ω，各个算法均由Python语言实现，程序运行环境为3.4GHzIntelCorei7(6700CPU)，8GBRAM，操作系统为Windows7(64bit)。

10.5.1扰动位置距离误差

采用距离误差的概念来表示车辆真实位置与所产生扰动位置之间的欧氏距离d(x0，z)，这在隐私保护机制方面也等于z的负效用。由于真实位置和扰动位置之间的距离过长会导致检索半径更长(或者说是更大的AOR)，从而增加了带宽开销，因此有必要对其进行检查并将其性能与其他方案进行比较。同样，由于几乎所有已知的Geo-Ind应用都仅使用从平面拉普拉斯分布中提取的噪声，并且它是实现Geo-Ind的原始且最典型的方法，因而本节将所提出的机制与平面拉普拉斯机制进行比较。

在实验中，分别通过手动调整δ

中不合理位置的比例和隐私参数ε来研究距离误差的变化。对于每对参数组合，测试10000次并计算其距离误差的平均值。为了使讨论具有一般性，假设不合理的位置在地图平面上根据比例均匀分布。实验结果如图10.5所示。图10.5距离误差图

从图10.5中可以看出，在不合理位置均匀分布的情况下，扰动位置与真实位置间的距离与不合理位置在地图平面上的占比没有显著关联，但会随着ε取值的增大而呈指数下降。从图中可知，尽管本章所提方案在对位置进行扰动过程中确保其仅扰动到合理位置，但并没有造成扰动距离的增加。平均来看，本章方案生成扰动位置后与真实位置的距离与平面拉普拉斯机制一致。这也说明本章方案在避免不合理位置的同时保留了平面拉普拉斯机制在隐私与可用性方面的权衡。另一个观察结果是，当ε<0.2时，距离误差随着ε的增加而迅速减小，而当ε>0.5时，随着ε

的变化而变化较小，这为选择ε提供了一个经验法则，即对于本章所提方案来说，ε为0.2~0.5最好。

10.5.2对不可信位置的抵抗性

本小节比较本章所提方案与平面拉普拉斯机制在确保扰动位置合理性方面的性能差异。首先观察当分别调整δ中不合理位置的比例和隐私参数ε

时用户发生的位置扰动为不合理位置的概率。为此，观察所提方案和平面拉普拉斯机制所产生的10000次扰动位置，并计算扰动位置落入不合理位置区域(除以测试总数10000)的比率。然后，比较它们的运行时间，以确定有效的合理位置，其中当平面拉普拉斯机制产生不合理的扰动位置时，它将被重复调用。分别利用这两种方法来产生10000次合理的扰动位置，并计算它们的运行时间平均值。此实验中的其他条件和因素与10.5.5节的条件和因素一致，结果如图10.6所示。

从图10.6(a)中可知，随着地图平面上不合理位置占比的增大，平面拉普拉斯机制将真实位置扰动到不合理位置的趋势逐渐上升，而本章所提方案则始终确保扰动位置位于合理区域。从图10.6(b)中可以看出，两种方案产生扰动位置的合理性与ε值的变化无显著关联。图10.6(c)中的结果表明，当不合理位置占比小于0.5时，两种方案的运行时间非常接近。随着不合理位置占比的增加，平面拉普拉斯机制的时间成本急剧上升，且比本章所提方案要高得多。从而表明，简单地反复使用平面拉普拉斯机制不能有效地实现“扰动隐藏”。由于不合理位置的地形属性是用户指定的，尽管不合理位置的比例在增加，但其在寻找有效扰动位置时的效率将迅速下降。图10.6(d)显示运行时间与ε之间的相关性不显著。

此外，图10.6(a)、(b)还表明，在一定条件下，平面拉普拉斯机制可以产生不合理的扰动位置，发生概率超过50%。具体来说，由于报告位置的合理性可能受到不合理位置的比例的影响，并且与ε没有显著关系，因此可以在图10.6(a)中看到当不合理位置的比例大于0.5时，报告出不合理的扰动位置的百分比将超过50%。由于用户指定了不合理位置的地形属性，因此可以满足此条件，尤其是当用户具有较高的隐私要求或车辆到达某些特定区域(如风景名胜区等)时。与Geo-Ind机制相比，图10.6还表明所提出的"扰动隐藏"方案可以通过确保扰动位置始终位于用户指定的合理区域中来减轻报告不合理扰动位置的问题。这是通过将具有用户指定属性的合理位置作为候选集，然后执行概率采样以报告候选集中的扰动位置来实现的。图10.6对不可信位置抵抗性的比较图10.6对不可信位置抵抗性的比较

10.5.3LBS查询的精准率与召回率

本小节通过实验评估服务提供商返回的结果的准确性和实用性，采用的指标是精准率和召回率。在LBS的上下文中，精准率的概念表示位于AOI中的返回POI占AOR中返回的POI总数的比例，这反映了查询的准确性。召回率表明位于AOI中的返回POI占AOI中全部实际POI的比例，反映了查询的效用。在形式上，用True表示AOI中的POI，用Positive表示AOR中的POI，用TP表示AOI∩AOR中的POI。在这种表示之下，查询结果的精准率等于TP/Positive，查询结果的召回率等于TP/True。

为了评估准确性和查询结果的召回率，从Geolife数据集[333]中统一选择了北京市五环以内的100个位置作为车辆用户的真实位置，并将所有用户至少出现一次的位置设置为合理的区域。然后分别调用算法10.1和算法10.2来生成报告的位置z