基于四叉树结构的增量近邻查询方法

庄礼金

（广东理工学院，广东肇庆，526100）

0 引言

传感器技术和移动通讯设备飞速发展，使位置服务得到广泛的应用。位置是将移动通信设备的位置和其他信息整合起来，为用户提供增值服务，即用户将当前位置信息和查询请求内容发送给位置服务器，以获得查询位置服务，其中最主要的位置服务有：广告分发服务；交通导航服务；信息娱乐服务等等。攻击者能够根据位置数据的时空敏感特性推测出用户的个人信息、位置信息等。用户获取位置服务既有利又有弊，因而位置隐私问题亟待解决。

现有的位置隐私保护方法主要分为3类：基于加密法、基于政策法和基于扭曲法的位置隐私保护[1]。目前，许多研究者致力于基于扭曲法的位置隐私保护的隐私需求和服务质量之间寻找一个平衡点。Yiu等人提出SpaceTwist的查询方法[2]是用代理查询点代替目标用户进行查询处理，目标用户根据自身的隐私需求在兴趣点候选集中选取k个近邻兴趣点。由于目标用户直接选取代理查询点进行查询处理，没有构造匿名区域，其计算代价和通信代价较低，但是目标用户查询处理过程中没有和其他用户进行协作，没有达到k-匿名。文献[3]提出一种基于SpaceTwist的k-匿名增量近邻查询位置隐私保护算法，该算法是目标用户根据自身的隐私需求与路网环境构造匿名区域进行查询处理。文献[4]采用客户服务器系统结构，容易实现的同时造成共享资源浪费。目标用户利用四叉树索引划分路网节点构建匿名区，请求路网和兴趣点位置信息，增加查询通信开销。文献[5]提出的CoPrivacy方法在构建匿名用户组时，假设用户彼此之间的协作是可信的，没有考虑到用户之间存在不可信的情况。本文提出的基于四叉树结构的增量近邻查询方法是研究目标用户如何根据自身的隐私需求构造匿名区域，在匿名区域中使用博弈论选取锚点进行查询处理。

1 位置隐私保护方法

1.1 构建匿名区域

SpaceTwist方法采用分布式结构，在目标用户附近随意选取一个点作为代理查询点进行查询请求。由于不确定目标用户所在区域的节点密度，攻击者容易攻击节点稀疏的用户。目标用户在请求位置服务时，需构造合理的匿名区域进行查询处理。匿名区域不能随机选取，若匿名区域过大，则代理用户与位置服务器的通讯开销会不可控。因此，目标用户在进行查询请求前，需构造合理的匿名区域。

本文采用四叉树结构将目标用户所在的区域以十字递归形式不断分割成4个大小相等的正方形区域，四叉树的每个节点最多有4个子节点，每个节点代表一个正方形区域。K-匿名机制是将目标用户泛化一个区域，该区域包含k-1个不同但相关的用户节点，从而使第三方无法在区域中辨别目标用户。为了防止最近邻攻击，目标用户在进行查询请求时，所发送的位置信息不是当前的坐标位置，而是当前所在的匿名区域，其匿名区域必须满足k-匿名机制，第三方要识别目标用户的位置信息的概率为1/k。如图1所示。

图1 四叉树结构

目标用户在构造匿名区域时要确认区域内的用户节点是否大于或等于k，若该区域的用户节点数大于或等于k，则该区域为目标用户构造的匿名区域。构造匿名区域的算法如算法1所示。

算法1：

输入：四叉树根节点pnode，目标用户的坐标l，隐私需求K

输出：匿名区域节点snode

Su=0；//初始化匿名区域的用户节点Su

if node leafnode==false

//判断当前节点是否为叶子节点

Num.push(pnode) //将当前节点进栈

for i=4 downto 1 do //判断目标用户所在的节点

if pnode.children[i]!=0 //查找用户所在的节点

算法1进行递归判断

endif

endfor

else while Su

snode=pushnode() //出栈

endwhile

endif

return snode

2 基于四叉树结构的增量近邻查询方法

在分布式结构中，k匿名的位置隐私方法是在匿名区域内选取一个节点作为一个代理查询点，使得第三方无法在k个匿名区域中识别目标用户。SpaceTwist方法进行查询处理时，其查询结果总是以锚点为中心不均匀分布，降低位置查询的查全率。本文采用博弈论计算锚点,提高攻击者推测目标用户坐标信息的难度。在查询处理过程中，目标用户首先通过四叉树结构构建匿名区域，采用博弈论计算锚点0U ，以0U 为中心向位置服务器发起增量近邻查询请求，位置服务器逐步增量返回兴趣点候选集。

算法2 查询处理算法

输入：目标用户1U ，兴趣点集为C，锚点为0U ，单次返回兴趣点个数β，位置查询内容为CS；

输出：兴趣点候选集V

dist(ip,1U )//兴趣点与用户位置之间的距离

3 性能分析

（1）隐私保护度分析：采用四叉树结构构建匿名区域，其匿名区域满足k-匿名机制，增加用户的隐私保护度。攻击者若想攻击目标用户，必须在匿名区域的k个用户中识别目标用户，从而攻击者很难获取用户信息，增加了隐私保护度。之后，利用博弈论计算锚点，确保目标用户节点信息和锚点信息不同但相关，保护匿名区域内各个用户节点的隐私，确保信息的传输安全。

（2）服务质量分析：本文的服务质量分析主要从查询效率和查询精确度进行分析。从查询效率来看，分布式结构为基于四叉树结构的增量近邻查询方法提供负载均衡的保障，解决集中式结构系统性能的瓶颈。 近邻查询方法考虑到兴趣检索点在锚点的反方向分布不均的问题，以博弈论计算锚点并进行增量近邻查询方法，可以获取锚点反方向的兴趣点。显然在这种情况下，位置服务质量比其他算法明显要高。

表1 展示各种方法的性能比较

从表1中可以看出，本文方法综合性能较好：（1）匿名成功率：本文方法在查询预处理中，通过四叉树结构构建匿名区域，使用博弈论计算锚点，确保目标用户和锚点在匿名区域中。而SpaceTwist不需要考虑匿名区域，直接选取匿名用户组进行查询处理；经典K-匿名方法使用可信第三方，没有考虑到用户节点密度过大或过小问题。（2）查准率：经典K-匿名方法在进行查询处理过程中，只要找到一个近邻的兴趣节点就结束检索。SpaceTwist方法在查询过程中，没有考虑到兴趣节点在锚点的反方向分布。本方法是在经典K-匿名方法和SpaceTwist方法的基础上，进行增量近邻查询，在考虑锚点反方向的同时返回k个近邻检索的兴趣节点。

4 总结

本文采用分布式结构解决可信第三方的性能瓶颈和集中攻击的问题，通过四叉树结构构造匿名区域，用博弈论计算锚点，平衡服务质量和位置隐私，利用增量近邻查询方法提高查询准确度。