路网环境下基于Unit模型的位置隐私保护方法
2018-10-26赵逢达房秀秀李贤善
赵逢达,房秀秀,李贤善
1(燕山大学 信息科学与工程学院,河北 秦皇岛 066004)2(河北省软件工程重点实验室,河北 秦皇岛 066004)3(北京联合天成价值网络科技有限公司,北京 100089)
1 引 言
基于位置的服务(Location Based Services,LBS)又称定位服务,也就是指服务提供商通过移动网络和定位技术获取查询用户的位置坐标,并将与该位置相关的服务信息传送给查询用户[1].位置服务是一把双刃剑,让人们的生活变得更加便利的同时,其信息泄露也给用户的生活造成诸多的威胁.因此保护查询用户的地理位置不被泄露迫在眉睫.
研究者已经进行了大量基于位置隐私保护的研究[2-6].位置隐私保护技术主要是在不影响服务质量的前提下,对查询用户的位置信息进行模糊化处理.这些技术中最基本的、重要的位置隐私保护技术是K-匿名模型[2].
Km等人较早提出了路网环境下的RE和HE匿名查询处理框架[7],Random edge ordering(RE)是随机的选取路网模型中的边作为匿名区域.Hilbert edge ordering(HE)首先是对边的中点作希尔伯特取值,并将该值作为边排序主键.依据希尔伯特值相近,二维图中边邻近的原理,将希尔伯特值相近的边作为一组作为匿名区域.Ma等人提出了基于Voronoi的网络图[8],将大网络划分为小的Voronoi区域.它提前计算好内存里的中间结果,然后根据缓存好的结果自己构造查询答案.Wang和Liu提出了一种以X-Star为基础的匿名方法[9],可以为移动用户达到最优的查询处理成本和高隐私保护之间的平衡.然而,X-Star显示出较低的匿名化成功率.Kim等人改进了X-star算法[10],结合Hilbert曲线提出了H-star算法.基于Hilbert曲线的H-star算法对星形节点进行排序,并根据匿名度K将它们加载到桶中.尽管该算法有一些改进,但是它具有与X-star相同的问题.
Li 等人提出了一种新类型的可逆位置匿名机制[11],有效地支持多级位置隐私.郑淼等人在网络扩张技术算法的基础上[12],提出了一个内部含有环的无向图,用于防止匿名区域内只包含一条路径的情况,并结合环和树的结构特征,为查询用户提供更隐秘的匿名空间.周长利等人在注入虚假查询和构造查询匿名组的方法上[13],提出了抗查询内容关联攻击和抗运动模式推断攻击的轨迹隐私保护方法.
Liu等人设计了两个启发式算法以策略性地选择mix zone位置[14].一般来说,尽管mix zone模型保护了用户连续查询的隐私,但是用户所享受的服务受到一定的限制,这可能对于一些用户是不能接受的.H.J.Cho等人提出了一种位置隐私保护监控算法[15],应用在保护路网中MkkNN查询的轨迹隐私中.Yong Wang为单个用户和一批用户提出了Snet层次结构[16].每个Snet被视为匿名单元.虽然Snet层次结构可以加速隐私保护过程,但是Snet层次结构不能及时更新,从而降低了匿名成功率.
以上这些隐私保护方法,可以保护用户的位置不受攻击,但是匿名效率和匿名成功率均不太理想.因此为了更好地保护路网环境下查询用户的位置隐私,提高匿名成功率以及提高匿名效率.本文提出了Unit结构,并将该结构Hilbert 编码相结合组成新的路网模型.本文的主要内容总结如下：
1)构建路网模型.将路网中复杂的路段关系映射为平面的路网有向图,根据路网有向图的连通性,将道路网络抽象为Unit结构,基于Hilbert排序以提供更有效的隐私保护服务.
2)基于Unit路网模型提出一种新的有效的位置隐私保护算法,每个查询用户可以依据自己需求提出不同的隐私要求.
3)该算法考虑到了人口稀少的地区难以找到k个用户而导致查询失败的情况,为不满足k要求的匿名区域添加假用户,以达到提高匿名成功率的目的.
2 系统模型
2.1 系统模型
本文采用的是最常使用的中心匿名服务器结构,该系统模型由移动用户端,中心匿名服务器端(AZ),位置服务提供商(LBS)三部分构成.匿名服务器在查询用户和服务提供商的中间,为两者提供非常可靠的安全通信链接.如图1所示.
用户登录该系统后,首先与匿名服务中心建立安全的连接,并通过此连接移动用户不断更新他们的位置信息并发送到匿名服务中心.当一个用户提出查询问题,匿名服务中心接受此查询及用户的精确位置信息,接着,匿名中心根据用户的位置信息生成匿名区域R,并把匿名区域R发送给服务提供商.然后LBS根据接受到的位置查找兴趣点,并返回查找到的所有兴趣点给匿名中心.最后,AZ依据用户具体位置过滤结果集,将精确的查询结果发送给移动用户.
2.2 位置隐私模型
位置隐私保护模型要求移动用户在匿名区域内是无法被辨认的,这就要用到位置k-匿名的概念.
定义1.位置K-匿名 移动用户所在的匿名区域必须至少包含k-1个不同的移动用户.
定义2.位置隐私参数(K;Lmax;Tmax)为满足移动用户不同的隐私要求,每位用户可以设置这三种不同的隐私参数.
K为位置K-anonymity模型的匿名水平.换言之,每个匿名区域都应该包含至少k个不同的用户,并且K值越大,用户的隐私越不容易泄露.用户被攻击的概率为1/K.若匿名中心服务器找不到k个用户,则查询失败.
Lmax为匿名区域的最大长度,以确保LBS提供服务的服务质量,匿名区域的长度不能超过最大长度,否则查询失败.
Tmax为时间容忍度,表示从用户提出查询到匿名结束,用户所能容忍的最长时间.如果匿名处理时间超过最长时间,则查询失败.
需要注意的是,匿名区域的最小长度也是匿名隐私参数之一,不过,为了简化隐私参数模型,本文不考虑匿名区域的最小长度.
定义3.位置匿名化 由Q表示查询用户U提交的基于地理位置服务的查询信息.位置匿名化就是采用满足U的隐私参数的匿名区域来替换Q中包含的移动用户的确切位置信息.
表1 专有名词的缩略词和符号的解释
Table 1 Interpretation of acronyms and symbols
AZ匿名服务器AnonymizerLBSLBS服务服务器AEL匿名区域 Anonymizing Edge ListAS匿名集合 Anonymous SetK匿名隐私参数,匿名区域最少包含的移动用户数Lmax匿名区域的长度
如表1列出了文章中出现的符号和缩写所代表的含义.
2.3 路网模型
图2表示的是真实的道路网络结构图,图3是从道路图中抽象出的二维路网模型.路网模型由带权的有向图G=(N,E)表示,N代表路网的节点集合,E代表路网边的集合.N中的节点n代表道路的交叉点.E中的每条边e包含两个节点,边e的权重由W(e)表示.W(e)可由边的长度或者是一个节点到另一个节点所用的时间表示,本文使用前者表示权重.如图3所示带权重的路网模型,边n1n2的权重是3,端点是n1,n2.用户的位置采用实心圆点表示,边的端点采用空心圆点表示.
图2 真实路网图Fig.2 Real road network
定义4.节点的度dG(n).节点n所连接的边的条数.
定义5.终节点.该节点只与一条边相连,dG(n)= 1.
定义6.边界顶点.给定路网G中的部分线段集S,S中的边界上的节点,即该节点一段连接的是S内的线段,另一端连接的线段不属于S或者该顶点所连接的边全部属于S.
图3 二维路网模型Fig.3 Road network
本文的主要内容就是开发出一个安全高效的可扩展的位置匿名模型.下面先介绍两种基本的匿名模型,即随机抽样模型和网络扩展模型,并由此引出新的匿名模型概念.
1)随机抽样模型.移动用户向AZ传递查询q(k,l,s,t),通过一次次的循环,匿名模型随机的选取S空间下的一条条边,直到同时满足(k,l)的要求,并将这些边作为移动用户新的匿名位置.如图4所示,移动用户(k,l)=(5,5).随机抽样模型在这个S区域内随机的选取几条边(共包含5个移动用户),如图中的粗线部分.
2)网络扩展模型.下面考虑另一种极端情况,通过扩展混淆u的具体位置[17]:依据Dijkstra算法,通过计算相对于u所在边的网络距离逐渐添加相邻的边,直到满足u的隐私需求.如图5所示,将加粗的4条距离u所在位置最近的边逐步添加到匿名区域内.
在隐私要求相同的情况下,随机抽样模型得到的匿名区域均匀地散布在S区域内,等同于在不同的线段中提出一系列查询,因此造成查询处理的成本比较高.该方法的优点是它具有很强的抗推理攻击能力,因为道路集是随机选取的.与此相反,网络扩展模型得到的匿名区域呈现的是一种紧凑结构.这种结构产生的查询处理成本最小,并且在查询处理过程中,
n1n2n3n4n5n6n7n8n9n10n11n12n13n14n15n16u1u2u3u4u5n1n2n3n4n5n6n7n8n9n10n11n12n13n14n15n16u1u2u3u4u5图4 随机抽样位置匿名模型Fig.4 Anonymous model of random sampling locations图5 网络扩展位置匿名模型Fig.5 Anonymous model of network extension location
扩展网络是局部进行的,导致成本进一步降低.但是,该模型抵抗攻击的能力很低,因为网络扩展过程遵守best-first搜索模式,其可能被攻击者使用反向工程攻击.以上这两种模型的匿名处理时间都比较长,容易导致总的查询时间大于T,从而导致查询失败.
2.3.1 Unit结构
考虑到上述两种模式的优缺点,本文提出一种基于Hilbert曲线编码的位置匿名模型,即Unit路网模型.目的是实现较低的位置匿名处理成本和较高的抵抗攻击能力之间的最佳平衡.具体地,Unit路网模型主要通过两个阶段达到这种平衡：
1)它将与同一节点相邻的边组织在一起.这么做的好处是预先构建最小匿名单元,达到降低位置匿名成本的目的.
2)采用Hilbert曲线对最小匿名单元进行编码,根据HilbertID值对匿名区域扩展,这样避免了中心攻击,提高了模型的抗攻击能力.
欧式空间下的Casper算法是一个基于网格的位置K匿名算法[18].Casper算法将全部的空间均等的分成若干个小网格,每个小网格被称作匿名度.本文依据该思想,将路网也同样分成若干个小的区域,每个区域内包含多条边,并将这些小的区域作为最小匿名单元,本文将最小匿名单元称作Unit.
定义7.Unit 对于给定的路网图G=(N,E),Unit是G的子图,表示为Un=(n,Bs,Es),其中n表示Unit的中心节点,Bs是Unit的边界顶点集合,Es表示Unit包含的边的集合,Es中所有的边都与n相连.
值得注意的是,Es是与n相连的部分边,而不是全部的边.因此,节点n可能是多个Unit的中心节点.每个Unit中边是不相重叠的,彼此是独立的.划分Unit的方法将在后面详细描述.
定义8.Lunit Unit中所有边的长度和的最大长度.
Unit作为AEL的最小组成单元,由于AEL具有最大值限制,因此Unit的长度也不能超过某个特定的值.Lunit的值是唯一且固定的.绝大多数Unit包含多条边,但不排除个别的边长度大于Lunit.对于这种长度大于Lunit的边,本文将该边作为单独的一个Unit.
将图6按照上述Unit定义分割路网图,结果如图7.Unit(a)对应的边界顶点集合Bs=(n3,n7,n8,n9),边集Es={(n3,n9),(n7,n9),(n8,n9)},中心节点是n9.类似地,对Unit(b),对应的边界顶点集合Bs={n3,n4,n5},边集Es={(n3,n4),(n5,n4)},中心节点是n9.另外,如果两个Unit共享同一个中心节点,则称这两个Unit为相邻Unit.
图6 路网模型Fig.6 Road network
通常,具有较大度的顶点在道路网络中起到更重要的作用.因此,本文选择相交的节点和与该节点相连的边构建Unit.下面是构建路网模型的步骤.
图7 Unit路网模型Fig.7 Unit road network
第一,为使Unit包含尽可能多地边,本文根据它们的度,按照降序对节点排序.
第二,根据节点的顺序,将节点n和与n相连的边构成一个Unit.根据本文定义7,将Unit中的节点n定义为中心节点.
图8 Hilbert曲线4×4Fig.8 Hilbert curve 4×4
第三,本文通过使用图8所示的Hilbert曲线将Unit的中心节点映射成希尔伯特ID.由于一些单元具有相同的中心节点,它们具有相同的Hilbert ID.因此,按照第三步中的顺序重新标记生成的Unit.如果两个Unit具有相同的希尔伯特ID,则它们的编号是相邻的.
在第三步中,按照Hilbert曲线对Unit进行排序,采用的是希尔伯特空间填充曲线的方法,将每个节点的2D坐标变换为1D值.图8通过使用希尔伯特曲线4x4分割2D空间.如果两个点在2D空间中非常临近,那么它们在1D变换中也接近的概率非常高.将节点的坐标值由二维变为一维,这样可以让匿名过程变得更加方便.因此本文采用Hilbert编码方法.下面是Unit路网模型构建的伪代码.
算法1.Unit路网模型构建算法
输入:G=(N,E)
输出:Unit1,Unit2,Unit3,…,Unitn
(1)Listnode ← Sorted nodes
(3) sumlength ← 0 // Unit中边的总长度
(5) If e 不属于任何 Unit
(6) sumlength ← sumlength+L(e)
(7) If(sumlength < Lunit)||(E(Uniti)= Ø)
(8) E(Uniti)←e,flag(e)=1,flag(curnode)=1
(9) Else sumlength← sumlength-L(e)
(10) End If
(11) End If
(12) End For
(13) If flag(curnode)==1
(14) N(Uniti)← curnode
(15) End If
(16)End For
(18) If flag(e)=0
(19) E(Unitj)← e
(20) End If
(21)End For
(22)Hilbert(#N,#U) //生成 Hilbert曲线
(23)Merge HilbertId(center node) //对Unit中心节点编码
(24)根据Hilbert ID值对Unit重新排序
(25)Return Unit1,Unit2,Unit3,…,Unitn
算法1描述了构建路网模型的过程.首先路网中的节点根据中心节点的度按照降序排序,并且通过AZ存储在Listnode中(步骤1).AZ依次从Listnode中取出节点,如果该节点和它所连接的边满足规定条件,则该节点和与其连接的部分边组成一个Unit(步骤2-16).如果边的长度超过Lunit,则在构建Unit的过程中应该摒弃该边,因此有必要检索遗漏掉的边.因为漏掉的边长度太长,并且它不能和其它的边组成Unit,所以本文将漏掉的边设置为单独的Unit(步骤17-21).如图7中(c)图所示,边(n5,n9)构成一个Unit.AZ按照Hilbert曲线对Unit进行排序(步骤22-25).
3 基于Unit路网模型的隐私保护方法
为保护路网环境下人们的位置,文献[9,10]使用的方法可以隐藏查询用户的精准位置,但它们的匿名成功率低,匿名时间长,不能带来较好的用户体验.为了避免这种巨大的时间成本和较低的匿名成功率,本章基于Unit路网模型提出一种新的H-Unit算法,H-Unit位置匿名算法的操作主要包括两个阶段：
第一阶段寻找查询用户所在的最小匿名单元Unit并且扩展Unit生成匿名区域的过程.
第二阶段是为提高H-Unit算法的匿名成功率,在匿名区域内随机添加假用户的算法.
当用户u提出匿名度为K的查询时,AZ第一时间获取用户所在的Unit,并得到该Unit的编号.然后,匿名集合由Unit中的所有查询用户组成.AZ判断匿名集合中的用户数量,如果匿名集合中的用户数量不能满足查询用户的隐私要求,则AZ搜索与查询用户所在的Unit相邻的Unit.重复上述步骤,直到匿名集合中的用户数量满足查询用户的隐私要求或达到匿名区域长度的上限.如若匿名集合中的用户数仍然不满足用户的隐私要求,则产生假用户.如果没有生成合格的匿名集,相应的匿名处理将被终止.如果该查询在AZ中匿名失败,则该查询无法到达LBS.如果该用户放弃对自己的位置信息进行保护,那么用户可以直接将精确的位置发送到服务提供商.
3.1 H-Unit匿名算法的实现
上面已经介绍过H-Unit匿名算法的大致过程,H-Unit匿名算法本文分为两步来讲解:中心匿名服务器为查询用户搜索真实用户的算法和产生假用户部分的算法.下面先来详细介绍匿名服务器搜索真实用户的部分算法.
算法2.H-Unit 匿名算法
输入:查询 Q
输出:匿名用户集合AS,匿名区域AEL
(1)首先根据用户的精确位置l找到用户所在的边e,然后找到该边e所在的Unit的编号ordU.
(2)If(L(AEL≤ Lmax)
(3) AS ←U(UnitordU) AEL← E(UnitordU) //将该Unit中的用户和边分别存储在AS和AEL中
(4)Else Retrun //查询失败
(5)End If
(6)If |AS |< K
(7) ordUa ← ordU+1,ordUb ← ordU-1
(8) For 路网中每个Unit
(9) If |AS| (10) ordUc← 从ordUa和ordUb中选择用户数量多的Unit (11) If ordUc中存在活跃用户 (12) If L(AEL)+L(ordUc)> Lmax (13) break (14) End If (15) AS←U(UnitordUc),AEL←UnitordUc) (16) End If (17) If ordUc == ordUa && (ordUa-ordU)-(ordU-ordUb)> 1 then (18) ordUb-- (19) End If (20) If ordU == ordUb (21) ordUb-- (22) Else ordUa ++ (23) End If (24) End If (25) End For (26)End If (27)If kAnony > |AS| (28) 调用算法4.2 (29)End If (30)Return AS,AEL 如上述算法2所示,移动用户u以 图9 路网图Fig.9 Road network 如图9为某一路网图,图10为Unit子图的划分结果,总共包含9个Unit,这些Unit的右下脚的编号表示其顺序(即,Unit4的编号是4等).表2和表3中列出了Unit的每个节点和中心节点的度.假设系统中有4个用户提出查询.表4中展示出了这4个查询用户的匿名度K,匿名集合Unit及其包含的用户.结合上面这些图和表格,可以找到查询用户所在的匿名区域. 图10 路网图划分举例Fig.10 Example about the division of the road network 表2 节点度 节点nn8n5n1n2n4n6n7n9n10n11n12n3节点度dG(n)543333333322 表3 Unit的中心节点 UnitUnit1Unit2Unit3Unit4Unit5Unit6Unit7Unit8Unit9中心节点n6n5n2n1n8n7n10n11n9 在人口密集的商业区域,很容易在一定范围内找到k个用户.但在人口稀少的地区,很难找到k个用户,特别是当匿名度K很大时.如果AZ在某个时间范围或区域内找不到k个用户,则用户的查询失败.因此有必要引入假用户的概念.即使攻击者知道在该区域中存在假用户,他也不知道哪些用户是真实的,哪些是假用户,因此用户被攻击的概率仍然是1/k. 表4 用户匿名的示例 userAnonymity degree KUnitnumber of usersu73Unit43u154Unit6,Unit75u174Unit6,Unit75u135Unit9,Unit84 定义9.假用户 在AEL中随机产生地理坐标(x,y)作为假用户的位置坐标.假用户的位置隐私保护参数和真实用户 的隐私参数相同. 假用户生成算法(Generate Dummy)主要有两个方面需要考虑: 1)确定假用户的位置坐标.生成的假用户的空间位置要符合大多数用户的轨迹规律,越像真实用户的位置越好,在路网空间里,如果生成的假用户的坐标不符合常规,将降低查询用户的匿名成功率. 2)生成假用户的数量.在生成假用户之前,AZ需要先确定生成假用户的数量.由于太多的假用户会导致系统性能下降,但是太少的假用户无法达到保护用户隐私的目的. 针对上述的问题,本文将假用户的位置限制在匿名区域AEL中,以保证生成的假用户的位置坐标是有效的.查询用户设定的隐私参数K的值减去AS中的真实用户数量,为所需生成的假用户的数量. 如果生成的假用户均聚类在一起,即使所有的假用户都符合规则,那么也会使得每个假用户之间的位置非常相近,这将会影响隐私保护的效果.为防止这一现象的出现,本文采用随机生成坐标的方式,使得每个假用户的坐标之间没有关联,并且是随机分布的,没有规律可循.即使攻击者知道AS中有假用户的存在,也无法判断出哪些是假用户. 文献[19]中描述的是完全没有限制的随机产生假用户的方法,但本文中产生假用户的算法是满足 算法3.产生假用户算法 输入:匿名区域AEL,匿名度K,匿名集AS 输出:AS (1)f= K- |AS| //f表示需要产生假用户的个数 (2)For 生成的假用户数量< f (3) 在AEL中随机选择一条边ei (4) 在边ei随机产生位置坐标(x,y)→ 新用户 u(x,y) (5) If u(x,y)∉ AS,AS← u(x,y) (6) End If (7)End For (8)Return AS 当AS中的用户数小于k时,算法3将会被调用.在生成假用户之前先计算需要生成的假用户数量(步骤1).AZ在AEL中随机选择一条边ei,然后在ei边上随机选择一点,该点的坐标即为生成的假用户的坐标,这样才能确保假用户存在AEL中.如果在AS中不存在该用户,则将生成的假用户存入AS中.重复步骤2到步骤6直到满足步骤2中的条件. 从表4中,容易得到|ASu13| 在本节中,为评估文中提出的Unit路网模型以及对应的匿名算法和查询处理算法在真实道路网络的有效性,将H-Unit匿名算法与文献[19]中的Random edge ordering(RE)and Hilbert-based ordering(HE)两种算法进行比较. 实验运行在4GB RAM的硬件配置64位Core i5处理器的Microsoft Windows7操作系统.实验采用的开发语言是C,并使用g(版本号:4.9.3)编译器完成代码编译. 本次研究使用的实验数据集来自旧金山的真实道路网络[20],其中包括10万个移动用户和5万条路段.路网图中边的权重设置为边的长度.用户和兴趣点的位置遵循均匀分布. 本文从10万个用户中随机生成查询用户,测试中心匿名服务器的匿名处理性能和LBS匿名查询处理效果. 在本节中,对中心匿名服务器为查询用户产生匿名区域的过程进行实验,并对实验结果做出详细的分析.实验中使用的参数数据如表5中所示.例如参数K和Lmax的值分别选自3-30,100-900,这样设置实验参数是为得到更好的实验比较结果.匿名度K,如果在匿名区域中只有一两个人,查询用户很容易被攻击,则匿名查询是无意义的,因此,K的值必须大于2.当K大于30时,实验所得的对比效果和K等于30相差无异,因此我们在3-30之间选择K的值.路网中总共有100k个用户,从这些用户中随机选取查询用户,查询用户的数量如表中所示.Unit最大长度等于500是固定值,如果下面的实验中没有具体描述,则各变量使用默认值.下文中提到的匿名时间是查询用户匿名时间总和.重复运行每个实验多次,将平均值作为评估结果. 表5 实验参数 参数名称参数值默认值用户数量100k100k查询用户数量1k,5k,10k,20k,30k,40k,50k30k匿名度 K[3,30][10-15]AEL最大长度Lmax100,200,300,400,500,600,700,800,900700Unit最大长度500m500m 下面从两个方面对Unit路网框架进行评估:匿名成功率和匿名时间. 定义10.匿名成功率.中心匿名服务器对移动用户成功匿名的数量占查询用户总数的比率[7],如公式(1)所示. SR=|success_msg | / (all_msg) (1) 公式(1)中,all_msg表示查询用户的总数量,success_msg表示匿名成功的用户总和.匿名成功率越高,相应的算法性能越好.文中的H-Unit匿名算法和RE、HE算法的测试结果均是在同一机器,相同配置的环境下产生的. 定义11.匿名时间.实验中所描述的匿名时间是指中心匿名服务器对移动用户总的匿名时间和[7]. 为得到更好的位置隐私保护效果,匿名时间应该越短越好.因为移动用户的查询等待时间是有限的,匿名时间越短,留给LBS服务器搜索兴趣点的时间越长,查询请求的成功率越高. 图11 匿名时间评估Fig.11 Cloaking time evaluation 图11显示了这三种算法的用户总匿名时间.可以看出,在相同的条件下H-Unit算法的匿名时间比HE和RE算法的匿名时间短很多.其中最主要的原因是Unit匿名模型中匿名服务器在搜索移动用户时,不在是逐条边的检索,而是以Unit为单位进行检索边上的用户.因此中心匿名服务器检索移动用户的速度提高了.查询用户的匿名时间主要受到查询用户设定的匿名度K和AEL的最大限制长度的影响,查询用户的数量对匿名时间几乎是没有影响的.如图11中(c)可以看出,当用户数等于50000时所使用的匿名时间,大约是用户数等于10000所使用时间的五倍.这是由于中心匿名服务器是对查询用户按照查询请求提交的时间顺序,依次按照顺序进行逐个匿名处理,因此查询用户的数量对匿名时间是没有影响的. 如果匿名度K在某一区间内是随机选取的,则不同算法的匿名时间取值介于在边界K值所对应的匿名时间范围内.结合图11中(a)和(b)可以看出当匿名度K=[5-7]时,匿名时间大于K=5且小于K=10时的匿名时间.这是因为在其他外界条件相同的前提下,匿名时间只是受到匿名度K的影响.而且随着K值的增加,中心匿名服务器检索到足够数量的移动用户所用时间也越长,因此匿名时间越长. 图11中(d)显示出随着AEL的最大长度的增长,匿名时间是先增加然后减小并且最终趋于稳定.当最大长度等于700或800时,匿名时间最短.由图11中(d)结合图12中(c)图可以得出,在K值相同的情况下,当最大匿名集的长度较小时,匿名成功率较低,也就是中心匿名服务器还没有检索到k个用户时,AEL的长度就已经超过了Lmax,然后匿名结束,查询失败.因此随着Lmax的增大,中心匿名服务器检索得到的用户数量越多,所用时间自然也会增加.但是当Lmax增加到AZ可以找到k个用户,这时Lmax再增加,AZ在检索用户的过程中,受到的限制变小,例如当AZ添加Unit1(添加上Unit1的用户数量满足K的要求)进入匿名区域后得到的AEL的长度大于Lmax,则放弃Unit,再去寻找周围其他的Unit.若是Lmax足够大,则可以直接将Unit1添加到AEL中,不需要再浪费时间检索其他Unit,因此Lmax增加,匿名时间减少并趋于一定的值. 图12 匿名成功率评估Fig.12 Success ratio evaluation 图12显示了匿名度K和AEL最大长度对成功率的影响.显然,H-Unit算法在相同的匿名度K和长度限制下成功率最高.图中假用户的数量是3万个查询生成的总假用户数.图12中(a)显示了在三种匿名度K的情况下,不同长度限制对生成假用户数量的影响.图12中(b)表示了在三种长度限制的情况下,不同匿名度K对生成假用户数量的影响.图12中(c)显示了当匿名度K=10时,AEL的长度限制对三种算法的匿名成功率的的影响.当匿名度K为一定值时,随着AEL的长度限制变大,找到k个用户变得更加容易,因此成功率更高.在图12中(d)中Lmax=300,匿名度较小时,很容易在特定范围内找到k个用户.因此,三种算法的成功率是相同的.很容易看出,H-Unit算法的成功率是最高的. 移动设备和定位技术的出现推动了位置服务行业的发展.基于位置的服务为人们的生活提供了极大的方便,但与此同时用户的个人隐私问题也引起了人们的关注.对于如何保护用户的位置隐私问题,研究者们已经提出了多种解决方法,但是大部分的研究背景是基于欧式空间下的,路网环境下的方法较少而且匿名性能一般. 本文创新性的提出了一种新的路网模型,并针对该路网模型提出了隐私保护算法.H-Unit算法大体分为三个阶段:i)构建基于Unit的路网;ii)采用Hilbert算法将每个Unit的编号映射到HilbertID;iii)选择邻近的Unit扩展匿名区域以满足用户的要求.本文还考虑到了在人口稀疏的地方添加假用户的方式,以提高匿名成功率.广泛的实验研究表明,与现有的Hilbert Cloak算法相比,H-Unit实现了较高的匿名成功率和较低的通信成本. 本文主要是针对路网环境下的位置隐私保护的研究,虽然本文对其中的一些关键问题进行了研究,完成了部分工作.但是路网环境下的攻击类型有很多种,用户的查询多是连续性查询,文中方法针对的是快照查询.因此今后的工作主要从以下几个方面开展: 1)根据Unit路网模型提出针对连续性查询的方法. 2)提高该模型的抗攻击能力,使该算法除抗重现攻击外的其他类型的推理攻击.
3.2 H-Unit算法的举例
Table 2 Degree of node
Table 3 Center node of Unit
3.3 产生假用户的算法
Table 4 Example of user anonymity
4 实验模拟
4.1 实验环境
4.2 实验结果分析
Table 5 Experiment parameters
5 结 论
