基于网格和密度的匿名空间查找算法

施洪洁

【摘要】LBS匿名模型中的关键问题在于如何寻找满足匿名条件的匿名空间，匿名空间越大，空间内用户数越多，攻者能判断出目标用户的概率越小，即匿名度越好，但是同时，增大的匿名空间也增大了用户位置精确度的损失，服务器返回的候选结果集与用户的真实请求结果之间的差距越大，即服务质量就越差，反之，较小的匿名空间服务质量增强，而匿名度较弱。因此，匿名空间查找方法的原则是在匿名度和服务质量之间需找一个最佳的平衡点，本文首先指出了目前最典型的匿名空间查找算法过程中产生的大量的空间冗余现象是因为空间划分精度太粗，而且没有考虑用户分布情况，因此，本文引入网格和密度的概念，提出了基于网格和密度的匿名空间查找算法。

【关键词】位置服务 查询隐私 k-匿名 网格和密度 最小匿名空间

【中图分类号】TP309 【文献标识码】A 【文章编号】2095-3089（2016）11-0249-01

Interval Cloak产生的大量的空间冗余现象是由于空间划分精度太粗和没有考虑用户分布情况，体现用户分布不均匀的状态就是密度的概念，而空间网格化是为了提高空间划分的精度。本节将在地理信息系统中应用比较成熟的网格技术，对空间进行网格划分，以网格为一个计算单元，再根据用户分布密度，在用户分布相对密度最大的范围内寻找合适的匿名集。

一、算法原理

在地理信息系统中，网格数据模型被用来分析空间特征，由于其数据结构简单，且成本低廉等优势，在地理空间分析中得到了广泛应用。网格数据模型中，空间被规则的划分为网格，每个网格的位置由网格的行列号来表示，网格的值表示这个位置上物体的类型或状态。本节提出的基于网格和密度的（GDB， Grid and Density？鄄Based）匿名空间查找算法基本思想是首先将整个空间映射为m×n网格，提高空间计算的精度，再利用空间用户分布相对密度公式，计算用户分布相对密度，在用户分布密度最大的范围内寻找满足匿名条件的匿名集，根据密度概念，容易得知，同一k匿名要求下，用户分布密度越大，匿名空间越小，正是利用这个原理，GDB在用户分布密度最大的范围内寻找满足匿名条件的最小匿名空间。

二、剥离冗余边缘

对于最小包含空间S2的空间冗余部分，本小节定义了用户分布相对密度公式，根据此公式，计算各网格用户分布相对密度，然后由远及近用户分布密度由小到大依次剥离其冗余边缘，为避免用户过于密集，匿名空间过小导致的位置隐私泄露，限定条件匿名空间的最小粒度为Smin。

根据用户分布相对密度矩阵，以用户u为中心，由远及近依次删除用户分布相对密度最小的行或列，直到剥离某条边缘后，得到的匿名空间不满足匿名条件。

三、敏感度约束

为了满足LBS（p， k）匿名条件，需在MASSA算法过程中加入p敏感约束，称为p-MASSA算法，针对一般LBS（p， k）匿名提出的算法称为p1-MASSA算法，针对增强的LBS（p， k）匿名提出的算法称为p2-MASSA算法。

与空间用户分布矩阵类似，对于用户提交的敏感查询和非敏感查询，分别用1和0来表示，构建匿名区域内用户查询敏感度矩阵，矩阵每个坐标的值表示对应网格内敏感查询的个数，为了简化计算，将匿名集中敏感查询所占比例不超过p的条件修改为匿名集中敏感查询个数不超过floor（k×p），仍以上面的例子为例，假设查询敏感度矩阵如矩阵Sid，若用户敏感度要求为0.3，即空间内敏感查询的个数不超过floor（4×0.3）=1，根据矩阵Sid可知阴影区域内敏感查询个数为1，满足匿名条件，则直接将该空间返回。

算法描述了基于增强的LBS（p， k）匿名空间查找算法。1行，Q集状态初始化，4～8行，在匿名度条件、匿名空间最小粒度条件满足的前提下，若敏感查询个数大于floor（k×p），则根据用户分布密度矩阵和敏感度矩阵依次删除用户分布密度最小，敏感度最大的网格内的查询，9～12行，若While循环退出时敏感查询个数不超过floor（k×p），则将此时Q内的所有查询标记flag修改为true，表示该集合内的查询满足敏感度条件，查询都能被处理，之后算法过程不需考虑查询敏感性，与MASSA算法过程相同，找到合适的匿名空间并将其返回，13～15行，否则，表示匿名失败，拒绝此次查询请求。

四、总结

本文分析了目前最典型的匿名空间查找算法在查找过程中产生的大量的空间冗余现象，提出了基于网格和密度的最小k匿名空间查找算法，首先将空间划分为m×n网格，其次，根据用户所处网格邻域空间内的用户数对空间进行迭代分割，找到最小包含空间，然后根据用户分布密度矩阵一次剥离用户分布密度最小的边，找到最小匿名空间。最后，在MASSA算法内加入了p敏感约束，并构建了查询敏感度矩阵，根据第3章提出的一般LBS（p， k）匿名模型和增强的LBS（p， k）匿名模型，分别提出了p1-MASSA算法和p2-MASSA算法，p1-MASSA算法最小以空间边缘为一个处理单位，p2-MASSA算法最小以一个网格为处理单位，先删除敏感度最大的网格，在敏感度要求较高的情况下，提高了匿名成功的可能性。

参考文献：

[1]刘洋.位置服务：冬去春未来[J]. 环球财经， 2011， 12（7）： 99-101.

[2]潘晓，肖珍，孟小峰.位置隐私研究综述[J]. 计算机科学与探索， 2007， 1（3）： 268-281.

[3]魏琼，卢炎生.位置隐私保护技术研究进展[J]. 计算机科学， 2008， 35（9）： 21-25.

[4]谈嵘， 顾君忠， 林欣， 等. 基于用户隐私保护的区域多对象聚集问题[J]. 计算机应用， 2011.