英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料

LBS中的无曝光精确位置K-匿名算法

摘要

本文解决了当前基于位置的服务（LBS）中的位置隐私保护，其中移动用户为了获得所需的服务，必须向LBS提供商报告确切的位置信息。为了保护用户的隐私，“位置隐藏”已经被提出并且深入研究。它会模糊用户的准确坐标，并将其替换为形状好的遮蔽区域。然而，为了获得这样的匿名空间区域（ASR），几乎所有存在的伪装算法都需要知道所有用户的准确位置。因此，对不将用户准确位置暴露给任何一方的“位置隐藏”的需要迫在眉睫。在本文中，我们提出了这两种非曝光精确位置隐藏算法。它们被设计用于K-匿名算法，这种隐藏基于所有用户报告的网格区域的标识码（ID），而不是直接在其准确坐标上进行隐藏。实验结果表明，我们的算法比现有的隐藏算法更加安全，并不需要所有的用户一直报告他们的位置，并可以生成较小的ASR。

介绍

近年来，电子消费市场见证了智能移动设备的蓬勃发展。这些设备，通常是智能手机和个人数字助理（PDA），配备强大的CPU，大型ROM和RAM，和定位技术（例如，GPS和AGPS）。这些设备无所不在地为移动用户开发新的应用。尤其通过GPS和无线互联网的结合，移动用户可以享受到一种LBS服务，这种服务根据用户所在位置提供动态内容。典型的LBS应用包括最近的兴趣点（POI）查询，位置感知广告和道路导航。为了享受这样的服务，移动用户必须明确地将其准确的位置暴露给服务器。例如，如果用户询问最近的医院，他们必须提供给LBS服务器GPS坐标的准确位置。在这个意义上，用户以位置隐私受到损害的代价换取服务。为了解决这个问题，直观的方法是在移动设备上缓存POI的整个数据集，然后可以在本地解决基于位置的查询。然而，移动设备的资源是有限的。这种方法既不能扩展到大型POI数据集也不能处理数据更新。因此，有人已经提出并研究了一种更为复杂的策略，这种策略称作位置匿名。其目的是允许移动用户在不显示准确位置的前提下请求服务。在沿线提出的各种方法中，位置隐藏是主要的。它根据一些像k-匿名（隐藏区域必须至少包含k个用户）或粒度（隐藏区域的大小必须超过阈值）的匿名度量，模糊了用户的准确位置，并且用一个形状规整的隐藏地区(通常是一个圆形或矩形)替换用户的准确位置。实际上，位置隐藏以牺牲服务为代价实现隐私保护。随着隐藏区域越大，隐私越多越多地保存，但需求的精确性越来越低。因此，大部分现有的位置隐藏研究集中在最小化隐藏区域的大小，同时仍然满足匿名度量。为此，一些位置隐藏算法已经提出了不同的匿名度量标准。但是，要获得ASR并优化其大小，现有算法需要所有用户的精确位置（即坐标）。由于准确的位置正是用户想要隐藏的位置，所有现有的工作本质上都假设参与隐藏过程的所有各方都必须被信任。典型的组织包括位于用户和LBS服务器之间的“匿名者”。然而，实际上，这些组织中的任何一方都可能是恶意的，并且将准确的位置信息暴露给任何一方可能会泄露用户身份或其他敏感信息。在这个意义上，现有的算法应用有限，而且不会将准确的用户位置暴露给任何一方的位置隐藏是迫切需要的。

最近，很多学者集中研究位置隐私保护和许多相关的参考文献。但是他们暴露了用户的准确位置到第三方。在本文中，我们提出了这两个非曝光精确位置隐藏算法。它们被设计用于k匿名，并且基于所有用户报告的网格的ID执行隐藏。

总而言之，我们在本文中的贡献如下。

（1）为了得到这样的隐藏区域而不暴露准确的用户位置，我们提出两种算法。一种是最佳隐藏算法，另一种是随机隐藏算法。两者都不需要所有用户一直报告其位置的信息；当他们移动到一个新的网格区域时，他们只会将其位置的信息报告给集中式匿名器。据我们所知，这是探索位置隐藏问题与所有用户报告的网格的ID（而不是用户的准确坐标）的第一次研究，而且用户可以通过他们自己区分所在的网格区域（不是集中式匿名器）。

(2) 我们的算法可以直接为一个查询而不是单个ASR生成多个ASR。我们提出了一种衡量网格服务质量（QoS）的度量模型。最优隐藏算法使用它来生成带有网格区域的ASR，这些ASR具有最高QoS。因此，该算法生成的多个ASR的总平方尺度小于现有隐藏算法生成的单个ASR。

本文的其余部分进行如下。第二部分讨论LBS中关于位置匿名和隐私保护的现有研究。第三部分介绍了系统架构。第四部分介绍了针对QoS的度量模型和两种在集中式环境生成ASR的算法。实验结果见第五部分，结论和未来工作在第六部分。

相关工作

位置匿名作为一种保护移动计算用户隐私的解决方案，尤其是在LBS方面，已经吸引了深入研究。目的是让移动用户能够请求服务而不暴露其位置。在各种匿名技术中，位置隐藏是主要的。它向服务器发送包含正版用户位置的伪装区域（通常是圆形或矩形）并且足够大以满足一些隐私度量。两个最广泛采用的指标是k匿名—这个地区必须至少包含k个用户，以便真正的请求用户与至少k-1个具有相同隐藏区域和粒度的其它用户不可区分，该区域的面积必须超过阈值。Interval Cloak是早期的隐藏技巧之一。匿名者用四叉树对用户进行索引。为了形成查询用户的ASR，Interval Cloak将四叉树下降到包含至少k个用户的最上面的节点(包括查询用户)。该节点的范围作为ASR返回。Casper Cloak与Interval Cloak相似，但是有两大差异。第一，Casper Cloak通过使用哈希表来识别和评估四叉树的叶子级别。第二，它不是立即回溯到父象限，而是检查两个相邻的象限，看看它们与用户象限的组合是否包含k个（或更多）用户。盖迪克和刘考虑了一个个性化的匿名模型，并提出了Clique-Cloak，它构建了一个集团图，将可以共享同一个隐藏区域。当客户不断的时候，他们解决了这个问题，请求位置隐藏并开发了最佳隐藏技术来抵抗追踪分析攻击。

值得注意的是，所有这些隐形方法（即Interval Cloak, Casper Cloak, and Clique-Cloak）都要求使用者将准确的坐标公开到信任的集中式匿名器。胡和徐提出了一种非曝光隐蔽算法来生成ASR。该算法基于移动用户之间的邻近信息来执行，而不是直接在它们的坐标上。算法使用的邻近信息是相邻对等体的WiFi接收信号强度（RSS）或来自其对等体的信标信号的到达时间差（TDOA）（时间越短越接近）。据我们所知，Android智能手机接收的WiFi RSS来自WiFi接入点（AP）。通常Android手机在AP模式下不工作。TDOA只能由基站测量。而TDOA只是与手机和基站相连接。因此，手机不能使用TDOA来确定其同级之间的邻近信息。所以他们的算法不能用于采用Android操作系统的智能手机。吴等人提出了一种Guess-Answer隐藏算法，用户和服务器之间的交互来产生ASR。服务器猜测一个ASR并将其提供给用户。 用户告诉他们对服务器的猜测ASR的相对方向。服务器猜测新的ASR与答案，并给他们给用户。用户回答这项工作将继续进行，直到用户进入被猜测的ASR。他们的算法可以在没有第三个中央匿名器的情况下工作，但它不属于匿名性，用户的位置可以通过用户的IP获得。

在服务器端，为了支持位置隐藏，还对掩盖区域进行了空间查询处理。莫克贝尔等人提出的Casper框架由匿名器和查询处理器组成。处理器评估掩蔽区域的空间查询，并将结果的超集返回给客户端进行进一步过滤。程等人提出了基于位置不确定性的类似框架，其中返回的结果是概率结果。

除了位置隐藏之外，还提出了其他匿名技术。 假名解除了用户身份和位置之间的映射，以便服务器只接收没有用户身份的位置。然而，这种技术仅限于不需要用户身份的那些基于位置的服务。特别是，缺少用户身份使得这些服务的计费成为不可能。虚拟机产生假的用户位置（称为虚拟人），并将它们与真实的用户位置组合在请求中。然而，通过监视用户的长期运动模式，服务器可以将真实位置与虚拟人区分开。你等从长远来看，通过为虚拟物产生一致的运动模式来增强这种技术。最近，有人提出的SpaceTwist，用户反复发出来自虚拟对象的kNN查询，它们称为锚点，直到保证真实位置的kNN结果为止。 Ghinita等提出了一种基于私人信息检索（PIR）的类似框架。框架分区空间成网状细胞,然后用户请求内容在细胞内定位。由于PIR，用户可以请求加密哪个单元而接受正确的内容。通过为每个单元格设置适当的内容，该框架可以支持近似和精确的NN查询。此外，该框架被显示为防止相关攻击，但是该框架不属于k-匿名。

系统架构

在本节中，我们将给出系统中的空间切割，隐私威胁模型和系统架构。在我们的算法中，由LBS系统提供的空间被分成小的矩形区域。这样的矩形区域可以称为网格区域。他们的宽度和高度是一样的。每个网格区域都标有ID。ID由X和Y组成，因此网格区域可以标记为ID（?，?）。所有用户的位置都标有坐标?（?，?）。该区域的宽度为系统给出的Delta;X。该区域的高度为系统给定的Delta;Y。如果Delta;?和Delta;?太小，就会降低匿名程度。 如果Delta;?和Delta;?太大，则会增加网络负载。 通常，Delta;?和Delta;?由大多数用户对ASR的最低要求设定。整个空间的原点是（?0，?0）。 当我们有?（?，?）时，我们可以通过（1）计算出ID（?，?）。公式（1）如下：

ID?（??，??）和ID?（??，??）之间的距离是一个自然数，可以由|?? - ??| 和|?? - ??| （|?|表示?的绝对值）。例如，ID（3,2）的网格区域与ID（3,3）的网格区域之间的距离是| 3 - 3 | 和| 2 - 3 |; 结果是1.我们不使用欧几里得距离，因为我们的定义1的距离代表层数，我们可以用它来逐层扩展搜索。

图1描绘了由三个实体组成的系统架构：移动用户，匿名者和LBS服务器。我们将首先讨论用户隐私概要中的隐私威胁模型和隐私设置，然后描述我们系统中的每个实体。

图1 系统架构

3.1隐私威胁模型。我们假设中央匿名器是可信的，但不是100％。它不会泄露用户的位置信息，但可能被对手攻击，对手可能会捕获匿名者，尽管概率很低。但是，我们对LBS提供商（LBS服务器）的可信赖性没有任何假设。

3.2用户隐私简介。所有用户在隐私设置文件中以?，?min的形式指定其隐私权要求，其中?表示所需的匿名级别，?min表示隐藏区域所需的最小面积。换句话说，用户想要找到至少包含?个用户的ASR，并且具有至少?min的面积。重要的是要注意，查询用户可以在任何查询的开始时间更改其隐私配置文件，以确保它指定的隐私设置在不同的情况下实现其所需的隐私保护。

3.3移动用户。所有的移动用户都配备有用于与匿名者进行通信的无线网络接口卡，例如GPRS，WCDMA和CDMA2000。所有用户还配备了GPS或AGPS设备来确定其位置，表示为坐标（?，?）。 系统中的所有用户可以使用（1）自己计算自己所在的网格区域的ID（而不是匿名器）。如果它们进入一个新的网格区域，它们会将它们的新网格区域的ID和之前的网格区域的ID发送给匿名者。当用户想用匿名查询的东西时，他们会将?，?min，查询内容及其网格区域ID发送到匿名器。 当查询结果从匿名器返回时，它们通过其坐标过滤无用的POI以获得最后的结果。

3.4匿名者。匿名器具有用于记录每个网格区域的用户数的表或阵列。当用户发送新的ID时，会更新在以前的网格区域和新的网格区域用户的总数。它只记录每个网格区域的用户总数，并且不记录“哪个用户正在哪个网格区域”。因此，如果匿名者被对手攻击，对手知道准确的坐标是非常困难的。当用户想要查询时，匿名者为它们生成ASR，然后将查询与ASR发送到LBS服务器。LBS服务器将查询结果发送回匿名器。匿名者通过查询用户的网格区域ID从结果中删除无用的信息，然后向用户提供有用的信息。

3.5 LBS服务器。嵌入在LBS服务器内的隐私感知查询处理器能够处理具有多个隐藏区域的基于位置的查询，用于一次查询。由于查询处理器不知道确切的用户位置以及用户所处的哪个子站，所以它只能计算ASR中所有子ASR的兴趣点（POI）的候选集（CS），其中包括准确答案的用户。

生成ASR算法

在本节中，我们给出了LBS服务器查询算法的主要思想，QoS的测量模型，两个定义和两个生成的ASR算法。

4.1 LBS服务器上的查询算法。 图2描述了LBS服务器查询算法的原理。 查询的ASR由三条被斜线绘制的孤立子程序库组成。 LBS服务器不知道用户正在使用哪个subASR，所以它必须扩展所有的距离为?的subASR，以获取搜索POI的区域。 LBS服务器查询算法的细节超出了本文的范围。

图2：LBS服务器查询算法的原理

4.2 测量模型。为了减小CS的大小，扩展子系统的总和必须最小。扩展子系统的总和由网格数量和网格区域之间的距离决定，因此接近查询用户网格区域并且拥有更多用户的网格区域最适合制作ASR。

如果隐藏的网格区域?中的用户总数不小于?（用户的匿名程度），?的总平方度量小于?min（ASR要求的最小平方度量 查询用户），距离是更大的决定性因素。因此，我们选择?中每个网格区域距离最小的网格区域。QoS的度量是

如果?的用户总数小于?，为了减少扩展子机制，网格区域的用户数量是决定性因素。QoS的度量是

当网格区域的用户小于?与the总用户的差异时，这意味着我们必须选择多个网格区域添加到?。所以用户和距离都是决定性的因素。由于数量比距离更重要，我们将“users /?”的系数设置为2.因此QoS为2 *用户/? 1 / sum（?）。

当网格区域的用户不少于?与?总用户之间的差异时，这意味着我们只需要选择一个网格区域即可添加到?。所以QoS只是由距离之和决定的。由于“2 * users /? 1 / sum（?）”不大于3，为了使QoS大于“2 * users /�

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[26515]，资料为PDF文档或Word文档，PDF文档可免费转换为Word