一个精度k-Anonymity磅的框架

文摘

在k-anonymity算法实现隐私保护,取代的起始位置k用户下的中心区域的路线从起始位置到隐匿的中心区域可能是非线性的,这将为用户带来了不便。提出了一种新的匿名服务器框架,我们添加电子地图和导航的功能比原来的基于框架的k-anonymity磅。除了最初的任务,包括计算下的中心区域和实际的查询结果对应的查询 ,新架构的匿名服务器将计划实际路径从查询的起始位置隐匿的中心地区并返回新的结果的集合 为用户 。此外,本文改进的算法计算的路线使其更符合实际情况的道路网络操作。最后,我们证明实验演示的方法的重要性。

1。介绍

k-anonymity技术(1- - - - - -4)解决了隐私保护在LBS(基于位置的服务)的实时查询。k-anonymity方法的工作过程如下。

用户发送一个查询请求(匿名服务器),和消息的请求 ,在这的起始位置的要求,是请求的内容,即目的地,k是匿名的水平,是暂时容忍,是空间的宽容。会发现其他k1用户,叫隐身算法,和发送消息 磅的是隐形的中心区域和是查询的集合k用户和 。磅返回查询结果 , ,为。如发现在对应于 ,计算欧氏距离来 ,修改字段与距离有关 ,并发送 用户 。查询的起始位置和消息保护k-anonymity技术,所以磅不知道和 ,但和 。

就业k-anonymity算法的路线来不确定性是欧几里得距离来 ,即,直线距离计算从返回的查询结果磅。但在实践中,存在着许多其他非线性路线,如图1。它显示了状态由k-anonymity技术处理后,在其中是隐形的中心区域; , , ,和 ,分别表示用户;和 , , ,和表示台词来 。在这个图中, , , ,和都是非线性的。特别是在人烟稀少的地区或低峰值,为了得到k匿名的层面上,时间和空间公差扩大时,线往往是更多的非线性。如果司机不熟悉周围的道路条件,最后一行从隐形地区用户看起来非常有价值。

ride-hailing磅作为一个例子。用户发送 为,起始位置,相当于吗 ,和目标位置,相当于吗 。作为发送 磅被隐身算法处理后。磅的线的计划来和调用驱动程序的位置取用户。但是司机不知道线来 。这同样适用于导航磅。如果不熟悉他的周围不在家或工作场所,用户通常不知道路径从开始位置到下区域。如图2,用户在社区或学校或工厂,必须经过门口到达的位置吗 。这条线从来等于 ,这显然是非线性的。

因此,有必要实现准确地从起始位置到最后一行的中心隐匿区基于已知k-anonymity算法。但涉及用户隐私的最后一行不能被磅,我们提出一个框架来解决这个问题。本文的贡献如下:

在本文中,我们提出一个新的框架,电子地图和导航功能部署在其计划的路线最后一行从起始位置隐匿的中心区域;

我们的计划更容易实现匿名的水平k在人烟稀少的地区或低高峰期不受空间影响而宽容比其他方案;

我们设计的体系结构,包括三个部分:通信部分、事务处理部分,和地图导航部分;

我们发现的缺点和局限性k-anonymity算法在新提出的改进算法;

最后,我们通过实验证明这种方法重要的演示。

剩下的纸是组织如下。部分2概述相关的工作。部分3描述了电子地图及其相关背景知识导航。部分4提出的新框架,描述了体系结构的添加导航的功能细节,之后,提出了规划的方法从起始位置到最后一行下。同时,我们分析新方法中存在的问题和改进它。部分5讨论了该方法在理论上的优势。部分6通过实验证明了性能。部分7是一个简单的结论和未来的工作的描述。

2。相关工作

Grutester和格5)首次引入k-anonymity磅,介绍找到一个可信的k用户一组和伦敦商学院无法区分他们一些查询问题,保护用户的隐私。匿名程度越大k隐私保护的能力就越强;许多文献专注于提高匿名的水平k区,包括找到一个更好的裹在最大时间和空间的约束宽容。的CliqueCloak算法(1,6定位一个小团体隐身在一个图表位置。的鬼马小精灵系统(7,8)使用quardtree-based金字塔执行位置匿名化技术,可实现快速隐身。PrivacyGrid隐身算法(9,10将地图分为许多细胞,每一个网格单元是一个矩形区域。至于的位置请求起源于候选人隐匿区。如果匿名条件满足的区域,区域将被选为候选人隐匿区。否则,它将扩大候选人隐身领域。文献[1,7,9)旨在增加匿名的水平k通过改进算法与隐匿区。有时,在稀疏的人口密集地区,它仍然无法实现匿名的水平k最大的时间和空间范围的宽容。在这样的情况下,介绍了虚拟位置。虚拟位置的想法(11- - - - - -13)是使用米虚拟位置和c真实用户实现k-anonymity, 。的方法层次聚类(14]试图使用集群技术来提高发现的效率k1用户。但在所有这些方法中存在的问题从一开始的路线位置请求是隐形的中心区域可能比直线更复杂,更有可能的非线性。然而,在现有的方法中,根据欧氏距离公式计算路线,这将导致QoS的衰落,特别是对于一些磅相关路线规划,如ride-hailing,外卖或导航。

一些文献[15- - - - - -17)关注道路网络的隐私保护。马等。15]提出根据泰勒多边形划分道路网络和使用SpaceTwist技术保护隐私在连续查询。太阳et al。16)提出了一个location-label-based方法满足l-diversity要求,道路网的介绍和参与许多细胞。虽然两(15,16]介绍了道路网络,目的是(15泰勒)是形成多边形和的目的16)是形成多样性的一个领域。马等。15]提到使用道路网络形式来计算实际的距离来和排名返回的结果,但它并没有给出具体的导航和如何处理问题在导航如环或十字路口。在这篇文章中,地图和导航的功能准确指导过去的路线,帮助找到最合适的k1用户k-anonymity算法。

3所示。背景知识

3.1。导航在道路网络的场景

移动互联网和智能手机的快速发展,许多移动应用的出现,给我们的生活带来巨大的方便。磅是其中之一,POI搜索的服务(的兴趣点)附近或提供导航电子地图和定位装置的技术在移动客户端。导航道路网络,其中的一个服务,包括两个主要部分:路径规划和位置指导。导航模型有三种形式:离线模式,在线实时请求模式,两种模式的结合。离线模式需要专用设备,电子地图和导航软件设置,所以不访问伦敦商学院和泄漏隐私磅,但价格昂贵。在网上实时请求模式,移动客户端与伦敦商学院连续查询的问题,这将增加服务器的负担。第三种模式是第一个两种模式的结合。由客户端和服务器架构。客户端负责的位置,产生查询请求磅,使位置根据磅的返回路线信息指导。服务器的功能是接收和响应客户机的请求和计划的路径。 When the server finishes planning the path and sends the guidance information to the client, the client will start navigation according to the location guidance and positioning technology by GPS or IP, and the whole process does not visit the server except that the current position deviates from the planned path. The third mode is convenience and cheap and can be implemented by downloading a client application to setup on a mobile device. So, the third mode is widely used. In the first mode, the user issues the continuous query at equal intervals and forms a query trajectory ,在这我代表第i个用户, 表示位置的时间 ,和查询位置发布的用户吗我。在第三个模式中,只有当的轨迹是稀疏的路线偏离计划的路线,和请求。轨迹是 ,在这很小,甚至只等于1。第一个模式和第三个模式都属于连续查询。在本文中,我们将讨论改善k-anonymity隐私保护的两种模式。

两种模式的工作过程如下:(1)客户端输入起点和目的地和产生查询请求磅(2)磅计划开始药水到目的地的路线和指导路线和位置信息发送给客户端(3)客户端启动导航根据指导信息(4)如果当前位置偏离计划的路径或一个固定片消费,客户端rerequests磅到步骤1

3.2。缩写和变量的定义

缩写包括摘要如表所示1。

本文中涉及的变量如表所示2。

3.3。k-Anonymity在道路网

指导是在客户机上执行的路径,不访问磅,直到当前位置偏离了道路,位置的过程指导不会泄漏隐私磅。只有在路径规划过程中,用户的隐私可能泄露给磅。所以和k-anonymity算法介绍步骤(1)和步骤(2)之间切断之间的直接通信客户端和磅在上面的工作过程,以及体系结构如图3。但现有方法的缺陷,从起始位置隐匿的中心区域可能是非线性的,无法抵达一条直线。在一些磅,如ride-hailing,外卖,或者导航,最后路径规划显得很重要。因此,本文提出一种新方法,可以计划最后路径根据真实路面网络和提供更准确的服务。

4所示。这种新方法

计划最后从起始位置准确地隐匿的中心区域,我们添加电子地图和导航功能。目前,许多电子地图和导航功能提供免费或免费使用移动互联网用户至少10公里,如谷歌地图、百度地图,高德牌地图。所以,我们可以介绍这些功能进行功能规划路线。引入新功能后,之间的交互和伦敦商学院并没有改变。所以,带来的隐私保护能力执行k-anonymity算法并没有改变。实现更好的QoS,即计划最后路线根据真实路面网络情况的唯一目的是引入新功能,这并不影响隐私保护的效率。应该强调,唯一保留的一部分地图路径规划的功能,即。,finding the route between the starting node and the ending node, and other functions such as searching points of interests is not be involved.

4.1。的架构是

由三个服务器的体系结构:CS(通信服务器),TPS(事务处理服务器),和MNS(地图导航服务器),如图3。CS负责与外部通信包括用户和伦敦商学院和内部包括TPS和MNS。TPS主要执行k-anonymity算法,产生请求的规划路径的起始位置MNS隐匿的中心区域,并接收从MNS与位置相关的信息指导。MNS的功能主要是接收该请求TPS和返回的路径规划的指导信息。

4.2。k-Anonymity算法的新架构

k-anonymity算法在新架构的工作过程如下:(1)用户产生并发送请求 它(2)CS接收请求,并将它转发给TPS(3)TPS执行k-anonymity算法:①找到k1用户的范围和然后调用位置隐身算法和获得的位置隐匿的中心区域 ;②创建一组组合查询的内容是什么k用户和 ;③发送消息 CS,然后提交来磅(4)磅返回查询结果 ,在这 , , 指示的路线来 ,和意义的指导信息(5)MNS返回查询结果其中包括路线指导和位置信息TPS,也就是说, (6)MNS返回查询结果其中包括路线指导和位置信息TPS,也就是说, (7)在收到查询结果和 ,TPS提取信息关于通过CA。并将其发送给他/她的关系遵循以下公式: (8)根据用户启动导航和(9)如果当前位置偏离路径或一个固定的时间片结束后,将rerequest计划路线和步骤1。

4.3。新方法中存在的问题

在上述方法中,引入新功能的组合和k-anonymity算法成为可能,位置隐私保护和最后一行计划准确,保证QoS的同时保护隐私。新技术的优点是,它使得k-anonymity算法摆脱空间的限制宽容。这意味着,在颞公差的范围,它是更容易找到k - 1用户比其他方案通过增加空间公差没有影响QoS,这使得匿名的水平k变得更大或获得k用户比以前更容易。

但仍然存在一些问题的新方法。在讨论这个问题之前,我们首先明确一条路的开始节点和结束节点(18),然后被描述为一个道路 ,在这起始节点和吗结束节点。路线往往是由许多道路。然后,我们定义一个路线 (19]。一般来说,用户经常从某个位置开始在一条路的开始节点,去目的地位于其他位置道路不是结束节点。所以,假设路线起点位置通过许多通往目的地的道路然后是路线被定义为

我们称之为路线的关键节点。

根据上面的定义,我们可以定义以下路线:

然后,从(3)和(4),我们可以推断(5):

现在让我们开始研究的问题。一个是显示在图4(一),红线表示的路线和黑色的路线 。我们把为例。根据新方法,用户将开始按照路线导航 :

之间没有交集和 。如果路线这么长时间,是超越时间的限制宽容吗或空间公差的用户,即它遵循以下公式: 在哪里表示路径上的所有节点 , ,在哪里路径上的节点数量吗和从节点上的速度吗来 。

在公式(7一个)和(7 b),和不同于和尽管所有的公差。颞宽容,反映了从产生的用户请求和响应时间要求,他接收到返回的消息是一种宽容,等于时间花在路线,它是由地图的导航能力约束部署在第三方提供的,如谷歌和百度。意味着最大的直线距离起始位置隐匿的中心地区,表示真正的路线的长度 。例如,在图5,蓝色的车之间的直线距离和橙色汽车非常短,但是它们之间的路线很长,高速公路的长度。

在这种情况下,我们将决定放弃k-anonymity算法,找到下一个用户。因此,公式(7一个)和(7 b)可以用来帮助判断用户是否可以被接受的k用户k-anonymity算法。现在让我们以一个例子来解释这种情况。假设的道路是一个高速公路,有两个单行道A和B,如图5。蓝色的点代表了汽车街B,和橙色的是那些街头的虚线表示隐匿区。如果车街B问题请求,根据上述原则,马路上汽车将废弃的路线的长度从隐匿的中心区域橙色位置太长(我们假设高速公路是无限和隐匿的中心区域位于街B)。

第二个图所示4 (b)。在图中,有一个环之间的路线和 ;也就是说,路线包括 。在这种情况下, , ,和路线和如下:

然后,路线是

我们可以看到节点在路线出现了两次 ,这条路线的形成一个环。事实上,我们观察到的实线来如下:

也就是说,在这种情况下,之前的位置出现在第二次被削减,只保留其余部分从第二个 。

第三个病例是图所示4 (c)。讨论第三情况之前,让我们回顾一些知识:(1)电子地图上道路网络的表示。对象(在地图上被安排在着重多层次19- - - - - -21]。取 (21)模式为例,有两个层次,分别上层和下一个,如图6。图6(一)显示了道路上杆等主要道路,和图6 (b)显示的低水平,如二级公路。Na代表上层的节点和Nb低层次图6。(2)路径搜索的规则:当导航开始,系统将获得当前导航设备在移动客户端和反对派的搜索路径规划上的位置和沿着路线从当前位置。如果当前位置偏离了路线,系统将rerequest计划的路径。现在让我们回到第三例。在图4 (c),主要道路B包括两条路H, H F .道路总是保持同一个方向与主要道路B, F和道路偏离大路B的二级公路G运行一段距离后的主要道路。对这个职位 ,它位于道路h .附近有一些线重叠之间的路线和 ,但它不形成一个环,而不是继续运行直到大路B但→二级公路G。假设道路 ;然后根据上面的定义,我们可以描述的路线从来在图4 (c),如下所示: 但事实上,我们只是观察到真正的路径 。根据路径搜索导航的原理,认为当前位置 ,然后导航系统将开始导航的位置出现在第一次没有第二个 。在公式(12),当前位置出现在第一次没有被阴影覆盖图。但是如果我们删除第一在 ,的公式将变成如下: 根据路径搜索的规则,系统将搜索当前位置在公式(覆盖着阴影13),第二次出现在公式(12),并开始按照其余的线 ,这是实际的路线。

第二个第三个情况比较,我们可以发现两种情况的实际路线都是如下: 所以第三例的方法适用于第二。因为在公式(14)属于路线 ,没有开始或结束或关键节点并没有显式地表示路线,同时减少一个节点首先出现在所示公式(13)是更容易和更简单的比切断前一行的位置第二次出现在公式所示(14)。此外,根据路径搜索的原理,我们知道在过去的两种情况,公式(13)相当于公式(14),所以我们决定使用公式(13),向用户返回路线。从图的情况下4,我们可以得出这样的结论:有两种方法来解决现有的三个问题。一个适用于第一种情况对应算法1和其他的最后两个对应的算法2。该算法1是用来判断用户是否符合条件和是否他/她可以的k用户在隐身算法,如图4(一)。算法2用于处理情况与十字路口或环,如图4 (b)和4 (c)。改进后的算法如下。

5。分析性能

介绍了电子地图和导航的新功能,带来了许多优势,主要体现在以下两个方面。

5.1。计划最后准确的距离

满足的要求k水平,k-anonymity扩大算法的时间和空间宽容,使得最后距离下的中心区域k起始位置似乎是线性的,有时特别是空间宽容成为大稀疏区,往往是更多的非线性。如果用户不熟悉周围的环境,知道定路线从用户中心变得更加重要。这种新方法提供了详细的计划,计划路线。

5.2。增加k-Anonymity水平

引入新方法后,技术k-anonymity摆脱空间公差时保持时间的限制宽容常数。因此,我们可以扩大下区域的范围和在该地区获得更多的用户。这意味着我们可以得到更高的匿名的水平k。所以,新方法提高了保护隐私的能力。

6。这个实验

实验环境是英特尔®CPU核心™i5 - 825 u @ 1.60 GHz和8.00 GB RAM。我们雇佣托马斯Brinkhoff对象发生器(22)和数据集的基于道路网络的城市奥尔登堡,它包含5835个节点和6065年的边缘(23]。每个实验重复10次,每个指标根据其平均计算。移动对象是10000,时间公差是10年代。图7反映了在不同的成功率k值。图中的四条线,分别代表不同的空间公差,和他们的长度是500米,1000米,1500米,2000米。从图中,我们可以看到的成功率寻找k - 1用户上升空间的增加宽容。当空间公差= 2000 k小于12,成功率达到100%。在旧的体系结构,以满足QoS,空间公差约束在0到1000米的范围1),所以的价值k不能太大,这可能导致匿名水平低。但在新架构的限制是爆发,和空间公差提出没有影响的实际要求最后的路线,可以准确地计划,而变得模糊的增加空间公差在旧建筑。图8显示成功率的关系k,分别在旧建筑和新的。蓝线表示成功率在旧建筑条件下颞公差等于10 s和空间等于1000米。橙色的线,我们可以看到只调整空间公差在某些范围,和成功率可以达到100%。

图9反映出的非线性和数量之间的关系k。蓝线代表非线性数量平均,橙色是最严重的非线性。图中显示,K与非线性数量呈正相关,即越大吗k价值,非线性。因此,增加k从起始位置的路径,隐匿的中心区域往往是非线性的,更不确定,这就意味着新的架构变得更加重要。

图10显示了戒指的数量关系,十字路口,路线 ,分别,是它太长和切断k条件下的空间公差等于1000米。从图中,我们可以看到,增加的k戒指的数量、交叉和路线切断似乎更多。因此,改进算法在实践中是必需的。

7所示。结论和未来的工作

提出了一种新的架构规划的路径,从起始位置是不确定的,隐形的中心区域。这个计划有更多的应用场景,比如taxi-hailing磅,外卖磅,和导航磅。通过实验演示中,我们可以看到,非线性的存在,成为大的概率增加k决定匿名的水平(1]。戒指也存在和改进算法必然是重要的。未来的工作将集中在利用这个架构对隐私保护的新算法和新的应用场景。

数据可用性

本文中的数据是基于城市道路网的奥尔登堡在文献[23]。

的利益冲突

作者宣称没有利益冲突。

引用

1. b . Gedik和l .刘”位置隐私在移动系统:一个个性化的匿名化模型,”学报》第25届IEEE国际会议分布式计算系统(ICDCS ' 05),页6 - 10,哥伦布,哦,美国,2005年6月。视图:出版商的网站|谷歌学术搜索
2. b·r·罗西尼和b s先生,”建模k-anonymity附近隐私保护的框架环境敏感磅,”通信在计算机和信息科学卷,250年,第193 - 187页,2011年。视图:出版商的网站|谷歌学术搜索
3. l . i Shan-Ping z h·杨,x林,“匿名水平适应算法来满足资源约束k-anonymity LBS服务,“浙江大学学报,45卷,不。7,1154 - 1160年,2011页。视图:谷歌学术搜索
4. a . Masoumzadeh j . Joshi和h·a·卡里,”伦敦商学院(k, T)匿名:时空匿名方法基于位置的服务用户,”诉讼的ACM Sigspatial国际会议上先进的地理信息系统2009年11月,西雅图,华盛顿。视图:出版商的网站|谷歌学术搜索
5. m . Gruteser和d·格“匿名使用基于位置的服务通过时空隐身,”学报第一国际会议在移动系统中,应用程序和Services-MobiSys美国,旧金山,CA, 2003年5月。视图:出版商的网站|谷歌学术搜索
6. p .尚和s . r . Balasundaram”,一个高效的小团体斗篷防守位置无关的攻击在基于位置的服务,它把算法”《2014年国际会议乌特迪尔,ACM拉贾斯坦邦,2014年11月。视图:出版商的网站|谷歌学术搜索
7. m . f . Mokbel c . y . Chow, w·g·奥”新卡斯珀:位置服务的查询处理不影响隐私,”美国第32国际会议上非常大的数据基础,页763 - 774,首尔,韩国,2006年9月。视图:谷歌学术搜索
8. m·f·Mokbel c . y . Chow, w·g·奥”新卡斯珀:privacy-aware定位数据库服务器,”IEEE国际会议数据工程学报》上IEEE,伊斯坦布尔,土耳其,2007年4月。视图:出版商的网站|谷歌学术搜索
9. p . Pesti b, l . Liu, t . Wang”支持匿名位置查询与privacygrid移动环境,”《国际会议在万维网上2008年4月,ACM,北京,中国,。视图:出版商的网站|谷歌学术搜索
10. c . y . Chow r·施莱格尔问:黄,和d s . Wong“用户定义隐私网格系统连续定位服务,“IEEE移动计算,14卷,不。10日,2158 - 2172年,2015页。视图:出版商的网站|谷歌学术搜索
11. h . Kido, y平贺柳泽,t .佐藤晴”的匿名通信技术使用基于位置服务的假人,”《国际会议上普及服务2005年7月,希腊圣托里尼岛。视图:出版商的网站|谷歌学术搜索
12. x刘,刘k, l .郭李x和y,“对策论方法在基于位置的服务,实现k-anonymity”2013年IEEE INFOCOM学报》上2013年4月,IEEE,意大利都灵,。视图:出版商的网站|谷歌学术搜索
13. 李妞妞,问:x朱、g .曹和h·李,“实现k-anonymity privacy-aware定位服务,”IEEE INFOCOM学报》上IEEE,多伦多,加拿大,2014年4月。视图:出版商的网站|谷歌学术搜索
14. z .问:他和g·陈,“改善k-anonymity基于层次聚类的位置隐私保护算法,”应用力学和材料,卷599 - 01、1553 - 1557年,2014页。视图:出版商的网站|谷歌学术搜索
15. 周c, c, s .杨”voronoi-based位置保护隐私的方法连续查询在磅,”国际期刊的分布式传感器网络,11卷,不。第三条ID 326953, 2015。视图:出版商的网站|谷歌学术搜索
16. h . g .太阳,d .廖h . Li,常诉,“L2P2: location-label基于隐私保护的磅,”未来一代计算机系统卷,74年,第384 - 375页,2017年。视图:出版商的网站|谷歌学术搜索
17. w .甄”,研究优化top-k连续空间对象的查询算法在道路网络,”第二届信息技术和机电一体化工程研讨会论文集重庆,中国,2016年5月。视图:出版商的网站|谷歌学术搜索
18. 问:王歌,x”,有效使用分层路由在大型公路网络社区,”IEEE智能交通系统,12卷,不。1,第140 - 132页,2011。视图:出版商的网站|谷歌学术搜索
19. g . r . Jagadeesh这位、t . Srikanthan和k·h·奎克“启发式技术加速等级道路网络,路由”IEEE智能交通系统,3卷,不。4、301 - 309年,2002页。视图:出版商的网站|谷歌学术搜索
20. 朱j .冯y:向井亚纪,t .渡边,“多级道路网综合管理和运输网络,”在计算机科学的课堂讲稿卷,3683年,第683 - 677页,2005年。视图:出版商的网站|谷歌学术搜索
21. a . Shokoufandeh d . Macrini迪金森,k . Siddiqi和s . w . Zucker“索引层次结构使用图像光谱,”IEEE模式分析与机器智能,27卷,不。7,1125 - 1140年,2005页。视图:出版商的网站|谷歌学术搜索
22. t . Brinkhoff”生成基于网络的移动对象的框架。”GeoInformatica》第六卷,没有。2、153 - 180年,2002页。视图:谷歌学术搜索
23. m . Stonebraker j . Frew k·嘉德斯,j .梅雷迪思“红杉2000存储基准,”ACM SIGMOD记录,22卷,不。2,2 - 11,1993页。视图:出版商的网站|谷歌学术搜索

版权

版权©2019方郑等。这是一个开放分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。