基于位置隐私保护的模糊查询方法

王鑫 余翔湛

摘要：随着基于位置的服务（location-based services，简称LBS）的广泛应用，个人位置信息的保护越来越受到人们关注。在LBS服务中，常常会遇到“谁附近有什么资源”的问题，“谁”代表实体位置，“什么”代表服务请求。在“谁附近有什么”的信息查询服务过程中，如何在保护“谁”的基础上提供相对可靠的服务，将是本文的研究重点。针对这一问题，用模糊集来实现对“谁”的保护，并针对模糊集，提出一种基于位置隐私保护的模糊查询方法，在模糊位置信息的基础上提供相对可靠的服务，并在一定程度上实现了位置隐私保护和位置服务质量之间的平衡。最后，通过相关实验来评估该方法的性能。

关键词：模糊集； 位置隐私保护； 模糊查询； 服务质量

中图分类号：TP393 文献标识码：A文章编号：2095-2163（2013）06-0021-04

0引言

近年来，基于位置的服务（location-based services，简称LBS[1]）不断发展，用以实现物联网中的实时、快速、可扩展的物体位置搜索。但是，由于用户在使用LBS服务时，需要向LBS服务器提供自身的位置信息，而LBS服务器又不是绝对可靠的，有可能将收集的用户位置信息泄露给攻击者，所以在使用LBS服务的同时，服务泄露或非法使用用户位置信息的情况也接踵而来，基于位置的服务给用户的位置隐私带来了极大的威胁。

在LBS服务中，主要有三大目标：你在哪里（空间信息）、你和谁在一起（社会信息）、谁附近有什么资源（信息查询）。本文主要解决“谁附近有什么资源”的问题，首先要明确两个参数：“谁”和“什么”，“谁”代表实体位置，“什么”代表服务请求。

在“谁附近有什么”的信息查询服务过程中，如何在保护“谁”的基础上提供相对可靠的服务，将是本文的研究重点。针对这一问题，本文提出一种基于位置隐私保护的模糊查询方法，在模糊位置信息的基础上提供相对可靠的服务，并于一定程度上实现了位置隐私保护和位置服务质量之间的平衡。

1位置隐私保护服务结构

由于LBS服务器是不可信任的，因此需要在用户和LBS服务器之间添加一个可信任的模糊服务器，该模糊服务器在用户和LBS服务器之间可起到防火墙的作用。由用户、模糊服务器和LBS服务器所组成的位置隐私保护服务结构[2]如图1所示。

该结构中模糊服务器工作如下：

（1）收集用户发送来的位置服务请求信息，将这些信息存储在服务器中；

（2）对用户发送过来的位置服务请求信息中的真实位置信息进行模糊，用空间模糊集进行代替，从而保护实体位置信息，最后将模糊过后的位置服务请求发送给第三方的LBS提供商的位置服务器；

（3）对第三方LBS提供商的位置服务器发回的基于模糊集的服务应答结果集进行接收，并根据用户需求对应答结果集进行过滤，找到相对合理的应答结果，再将此结果发送给用户。

根据位置隐私保护服务结构的要求，首先需要对用户真实位置信息进行模糊。本文采用已有的k-匿名技术[3]来构造实体模糊集，以达到模糊效果。

k-匿名通过概括和隐匿技术[4]，发布精度较低的数据，使得每条记录至少与数据表中其他k-1条记录具有完全相同的标识属性值，从而减少链接攻击所导致的隐私泄露。k-匿名技术可以保证每一个体的敏感属性隐藏在规模为k的群体中，这样，个体能够得到确认的几率将不会超过1/k。目前的k-匿名技术主要是利用两种方法来实现匿名：泛化[5]和隐匿技术。本文采用Datafly泛化算法[6]，根据k-匿名的要求，计算得到每个属性出现的概率，然后对不满足要求的属性做泛化处理，直到该属性满足 k-匿名的要求为止，从而得到规模为k的模糊集。

3基于位置隐私保护的模糊查询方法

利用K-匿名算法构造完实体位置模糊集之后，LBS服务器需要针对整个模糊集来提供“附近有什么”的查询服务，而如何在模糊集基础上提供尽可能良好的服务即成为问题关键。针对这一问题，本文提出一种基于位置隐私保护的模糊查询方法—FCM方法，该方法可以嵌入到LBS服务器当中，通过计算模糊集到附近服务请求点的最短路径长度来提供相对可靠的查询服务，使得在保护实体真实位置的同时，又提供了较为良好的服务。

FCM计算方法是针对模糊集进行计算的，传统Dijkstra算法[7]是针对点进行计算，与其有相似之处，所以本文FCM计算方法借鉴了传统的Dijkstra算法，但是由于Dijkstra算法以起点为中心向外层层扩展，需要遍历计算所有节点，过于繁琐。在实际应用当中，面对大量节点，使用Dijkstra算法查找最短路径时需耗费大量的时间进行数据的比较，搜索速度较慢，效率较低，FCM计算方法对此进行了改进，以降低搜索复杂程度。

由于FCM需要计算模糊集合到服务请求点的最短路径距离，而对于模糊集合O中的不同点，到附近服务点（如附近餐厅）的最短路径长度也是不一样的，如何在众多的附近服务点中选择合适的服务点返回给用户就成为求解的关键，考虑到服务质量问题，需要首先对模糊集进行划分。

3.1模糊集划分

对模糊集O进行划分，需要构建对于请求点集合Q在关系δ上的划分△。

关系δ定义如下：δ∈O*O，对任意o1，o2∈O，o1δ o2当且仅当min（o1）=min（o2）。o1δ o2可以理解为对于某个请求来说，o1和o2的最短路径距离是相等的。其中函数min描述如下：min：O→Q，min（o） →q1表示对任意o∈O，满足d（o， q1）< d（o， q1），假设q1，q2∈Q，而且d（o， q1）≠d（o， q1）。其中d表示最短路径长度。

根据关系δ，可以得到划分△：

（1）计算实体位置模糊集O中各点到请求集合Q的最短路径距离，得到序对，即oi的最短路径距离的终点是qj；

（2）遍历所有的序对，将终点相同的起点归为一类；

（3）得到划分结果△，其中o∈[o]，对任意o∈O 。

3.2FCM计算方法

在划分的基础上，FCM可以在众多附近服务点中选择最适合的点返回给用户，由此使得服务的可靠性有所提升。

为了便于研究，如图2所示，设置一个虚拟点s，将s和请求集合Q中的点以权重为0.0的边连接起来。

在实际计算中，可以先计算点s到模糊集O中各点的最短路径距离，然后将最短路径逆序，转化为从集合O中各点到虚拟点s的最短路径距离，则逆序后的最短路径中倒数第二个点必然是集合Q中的点。

FCM计算方法描述如下：

算法输入：用来表示二维空间的边权值图G = （V， E）；模糊点集合OV，且实体位置 l∈O；请求点集合 QV

算法输出：

（1）关系δO×O，o1，o2∈O，o1 δ o2当且仅当min（o1） = min（o2）；

（2）序对，C∈（0.0，1.0]表明q为实体请求点的可能程度。

1. 构建图G′=（V′，E′），其中S={s}×QV′=V∪{s}，E′=E∪S 。

2. 假设G′中任意两节点间总会有一条通路，即使不可直达，也可以绕路到达。

3.从s出发，利用贪心策略选择一条可达o1的路径，记录路径长度，作为限界bound。

4.返回s根节点，构建解空间树，定义活节点表PT，解向量为X=（x1，…，xn），xi的取值范围为Si，|Si|=ri。

5.从根结点出发，扩展根结点的r1个孩子节点，从而构成分量x1的r1种可能的取值方式。

6.对每一个孩子结点x，计算根结点到其的路径长度。

7.若某孩子结点的路径长度权值超出bound，则将该孩子结点丢弃，剪掉分支；否则，将该孩子结点加入表PT中。

8.继续扩展，不断重复7过程，直到rn为叶子节点时，检查其路径长度，如果小于bound，则更新bound值。

9.取PT表中的第一个节点作为扩展的根节点，重复5。直到得到一个最优解X=（x1，…，xn），记录最短路径长度，为最终bound′。

10.重复上述过程，可得s到O中其它各点的最短路径距离。

11. 定义second：O→Q，second（o）→vq，其中vq是从s到o的最短路径上的第二个点，这个点必在集合Q中。

12.o1，o2∈O，o1 δ o2当且仅当second（o1） = second（o2），此时划分O/δ构建完毕。

13. if O∈O/δ then（最多的划分是|O|）

14.return ，其中，o∈O ，q=min（o） 。

15. else

16.（if 用户同意标识位置l所在的分类[l]∈O/δ then

17.return ，其中，o∈[l] ，t=min（o） 。

18. else

19.return ，对于不同的Δ， o∈O，使得q=min（o）且 Ci=Area[oi]/Area[O]最大。

FCM方法中3-10步骤计算虚拟点s到模糊集O中各点的最短路径距离，11-12步骤将模糊集O按照关系δ进行划分，13-19步骤在请求集合Q中选择合适的点返回，如果划分O/δ只有一个，那么必然是O（line 13），说明任意o1，o2∈O，o1δ o2，O中任何一个点均可代替实体位置，选择q=min（o） （line 14）成立的点返回。当存在多个划分结果时，如果用户同意标识自己所在的分类[l]属于O/δ （line 16），那么实体所在类中的任意一点可以代替用户位置，选择t=min（o）成立的点返回（line 17）。如果实体不同意标识自己的位置，则返回面积最大类中的任意一点来代替实体位置，即q=min（o）（line 19）。在19步中，Ci =Area（[oi]）/ Area（[O]）表示q为合适请求点的可能性，由于对于模糊集来说，Area（[O]）是恒定的，只需要计算Area（[oi]）来决定Ci的大小，Area（[oi]）表示划分[oi]中对应q点的点的数量。

4仿真实验与结果分析

基于位置隐私保护的模糊查询方法中需要用到FCM算法，该方法在不确定条件下为用户提供尽可能可靠的服务，并利用最短路径长度来作为衡量的标准。通过与传统算法作对比，来验证FCM的运算效率和实用性。

4.1FCM计算方法的实现

设图G =（V， E）中有68个点，580条边，设置模糊测试集如下：Q1={14，21，22，23，24，27，29，30，32，35}， Q2={50，52，54，56，57，58，59，63}，Q3={8，10，11，15，18，19，24，30，32，33，34，36，37，43，47，53，55，62，65，68}设置请求集合为：Q1={67，38，24，65，35，62，31，27，14，11，5，59}。其中， Q1和Q2为相对聚集的点，Q3为随机产生的点，较为分散。在图中加入虚拟点s，由于Q中存在12个点，那么整个图形变为69个点，592条边。根据设定的边权值矩阵来计算s到O1，O2，O3中各点的最短路径。结果如表1，表2，表3所示。结果表明，即便在点数量较多和随机情况下，14和27号请求点依然可以作为结果返回给用户，表明在点数量更大，随机比例更高的情况下FCM算法依然可以保持一定有效性。

综合以上测试结果，表明算法可以在不确定条件下有效返回相关结果，由此达到预期目标。

4.2FCM算法与传统算法的比较

建立5张图G =（V， E），分别用Dijkstra算法、遗传算法[8]和FCM方法计算最短路径，统计各自的搜索速度，如图3所示。

由图3可以看出，当节点数为16时，Dijkstra算法、遗传算法和FCM方法计算最短路径所花费的时间几乎相同，当节点个数为32时，三种方法的响应时间开始有略微差别，当节点数为48时，三种方法开始有明显差别，并且随着节点数的增多，三种方法的响应时间都有大幅提升，但是同等条件下，Dijkstra算法和遗传算法的响应时间的上升幅度明显大于FCM方法，而且这种差距将随节点数的增多而变得更加明显。由此可以得出如下结论：当节点数较少时，三种方法计算最短路径的响应时间差别不大；当节点数目较多时，FCM方法的响应时间更少，具有更好的性能。

5结束语

本文基于位置隐私保护服务结构，实现了在不确定条件下为用户提供相对可靠的位置隐私保护服务请求。在模糊集基础上，利用最短路径长度来作为衡量的标准，解决了在不确定条件下“谁附近有什么”的查询问题，其中“谁”代表实体位置模糊集，然后，本文提出一种基于位置隐私保护的模糊查询方法—FCM，使得在保护了用户位置信息之后，仍旧可以提供较为可靠的服务，实现了位置隐私保护和服务质量的有效平衡。最后，经过实验验证，FCM方法在一定程度节省了存储空间，提高了运行效率，具有一定实用价值。

参考文献：

[1]ASHTON K. That ‘Internet of Things Thing[C]// RFID Journal， 2009.

[2]XIAO Z， MENG X， XU J. Quality-aware privacy protection for location-based services[C]//Proceedings of the International Conference on Database Systems for Advanced Applications.Bangkok.Thailand，2007：113-120.

[3]SAMARATI P， SWEENEY L. Protecting privacy when disclosing information：k- anonymity and its enforcement through generalization and suppression[J]. International Journal on Uncertainty， Fuzziness and Knowledge-based Systems，2002，10（5）：557-570.

[4]MACHANAVAJJHALA A，GEHRKE J， KIFER D. l-diversity： Privacy beyond K-Anonymity[C]//Proceedings of the 22nd International Conference on Data Engineering Atlanta. GA.USA：ACM Press， 2006： 3-8.

[5]ANCO H， LEON W. U-argus and t-argus：software for statistical disclosure control[C]//Proceedings of the Third International Seminar. Statistical Confidentiality，1996：156-163.

[6]SWEENEY L. Computational disclosure control： a primer on data privacy protection[D]. PhD dissertation，： Computer Science Dept. Massachusetts Institute of Technology， 2001.

[7]ZHANG Yonglong. Dijkstra shortest path algorithm optimization [J]. Journal of nanchang institute，2005，1（2）：23-25.

[8]张宁.遗传算法的特点及其应用[J].北京：中国科技论文，2005，3（4）：107-111.

[2]PANDIT N， KALBARCZYK Z， IYER R K. Effectiveness of machine checks for error diagnostics[C]//Lisbon， Portugal： Proceedings of IEEE/IFIP International Conference on Dependable System & Networks， 2009， 7：578-583.

[3]ZHENG Z， LAN Z， PARK B H. System log pre-processing to improve failure prediction[C]//Lisbon， Portugal： Proceedings of IEEE/IFIP International Conference on Dependable System & Networks， 2009， 7：572-577.

[4]HILLER M， JHUMKA A， SURI N. An approach for analysing the propagation of data errors in software[C]//Goteborg， Sweden： International Conference on Dependable System & Networks， 2001， 7：161-170.

[5]李秀敏. 极值统计模型族的参数估计及其应用研究[D]. 天津：天津大学，2007： 13-29.