面向位置服务的用户隐私保护

裴媛媛，石润华，仲 红，张 顺

（1.安徽大学计算智能与信号处理教育部重点实验室，合肥 230039；2.安徽大学计算机科学与技术学院，合肥 230601）

面向位置服务的用户隐私保护

裴媛媛1，2，石润华1，2，仲 红1，2，张 顺1，2

（1.安徽大学计算智能与信号处理教育部重点实验室，合肥 230039；2.安徽大学计算机科学与技术学院，合肥 230601）

传感器技术和移动通信设备的发展使位置服务（LBS）得到广泛应用。与此同时，在服务过程中所产生的隐私问题也成为关注的焦点。为此，针对LBS位置隐私的保护问题，构造一个用户协作的分布式模型，并设计一种新的隐私保护方案。在构建匿名区时，使用贝叶斯Nash均衡思想以及安全多方求和技术以保证用户信息的隐私。在处理查询结果时，引入Voronoi图的方法以提高查询效率。分析结果表明，该方案考虑了用户节点自私和不可信的情况，并且简化了查询过程，在保护隐私的同时可提高服务的整体性能。

位置隐私；用户协作；贝叶斯Nash均衡；安全多方求和；Voronoi图

DO I：10.3969/j.issn.1000-3428.2015.10.005

1 概述

随着无线通信和移动技术的飞速发展，位置服务（Location-based Service，LBS）应运而生。LBS就是将移动设备（如智能手机、平板电脑等）的位置和其他信息整合起来，为用户提供增值服务［1］，其主要的应用背景有：紧急救援服务，如“查询离我最近的医院”；信息娱乐服务，如“查询离我最近的 KTV”；交通导航服务，如“根据行驶道路的拥挤状况选择最优路径”；广告分发服务，如“向某超市餐馆外100 m的用户发送电子优惠券”。显而易见，这些服务能给人们的生活带来便利，但人们在享受高品质服务的同时，也可能泄露了部分个人隐私。例如，攻击者通过窃听，获取用户的位置和查询内容推断出用户的身份，进而获得更多的用户隐私信息。换言之，人们的隐私和安全受到了威胁。一般地，服务质量和隐

私保护程度是一对矛盾体，提供精确位置可享受高质量的服务，而隐私保护又要求不能暴露确定位置。因此，如何在这两点之间达到一个平衡，是多数研究者所要思考的问题。除此之外，文献［1］还列出了在研究位置隐私保护过程中面临的其他挑战，也都是在设计方案时需要考虑的。

近年来，关于位置隐私保护的研究最经典的模型当属k-匿名模型，多数研究也是基于此基础之上，且采用中心服务器结构。该结构就是在用户和服务提供商之间加入了一个可信第三方，即可信匿名服务器，用于将用户精确的位置模糊处理，产生一个保护用户位置的区域。

中心服务器结构降低了客户端的负担，但其缺点也很明显：（1）位置匿名服务器可能成为系统处理上的瓶颈；（2）当位置匿名服务器变得不可信时，将会导致极为严重的后果。为此，本文提出一个无可信第三方，通过用户之间协作完成的分布式位置隐私保护方案。

2 研究进展

在位置隐私保护中有3种常见的设计思想：k-匿名，混合区，虚拟节点。

（1）k-匿名：使用包含 k个节点的一块区域来代替某一具体位置发送给服务提供者，以使得攻击者没有办法确定用户的真实位置。文献［2］提出k-匿名的概念，使用到关系数据库的数据隐私保护中。文献［3］将 k-匿名的概念应用到位置隐私上来，提出位置k-匿名。文献［4］提出个性化 k-匿名算法，针对不同应用背景的隐私需求，但它只简单介绍个性化位置 k-匿名的基本概念和设计的基本思想。所以，文献［5］继续完善，提出一套完整的体系结构。文献［6］使用博弈论的方法获取 k-匿名，解决了节点密度低时如何保证达到 k-匿名的问题。

（2）混合区：指定一个区域作为混合区，在进入该区域内所有节点同时改变自己的假名，之后，监听者则不能再继续跟踪下去，因为它没有办法确定新旧假名之间的映射。关于这方面的研究最初是文献［7-8］提出混合区的结构，并使用熵的概念来分析其隐私性。文献［9］提出了一个时空数据的 k-匿名模型，它将混合区思想与k-匿名结合起来，对前面的混合区模型进行完善，但它们都没考虑实际的道路网络分布情况。文献［10］提出基于道路网络的一个混合区方案，它将混合区由理论矩形变化到道路网络并加入了多种影响因素。文献［11］提出流量感知多混合区的放置算法，考虑了道路流量分布不均匀情况下，在何处安放混合区，以使其效益达到最大的问题。文献［12］提出分布式混合区算法，它是从用户角度出发，根据博弈论的思想，决定是否加入某混合区，使自已利益最大化。

（3）虚拟节点：指产生假的位置信息，代替真实位置发送给LBS，或者与真实位置一起发送过去，达到混淆的目的。文献［13］提出虚拟节点的匿名技术，但它没有具体考虑虚拟节点移动轨迹的限制。文献［14］使用虚拟节点保护移动轨迹，解决了上面的问题，且提出了 2种生成虚拟轨迹的方案。2010年，文献［15］把虚拟节点应用到一个混合匿名系统中，这样减少了用户操作并提高系统性能。文献［16］提出一个关于隐私保护的混合算法，在模糊区域产生过程中加入虚拟节点以达到k-匿名。目前多数关于虚拟节点的方法，是与 k-匿名或混合区的思想结合起来，以达到更为满意的位置隐私保护的效果。

另外，还有基于PIR的位置隐私保护算法，如文献［17-18］，通过对查询进行加密以及数据库记录置乱等方式进行。但由于其加解密过程中产生的计算和通信代价都很大，因此进一步的研究并不多。

上述3种主要思想在已有研究中都存在一些问题。如混合区中每个用户假名的变换、保存状态信息以及通知应用服务器新用户的到达等，需要花费不少代价，而且可能导致服务质量的下降。单个节点产生虚拟节点，利用假位置查询，则隐私性不高。k-匿名的使用大多需要借助可信第三方。因此，本文在k-匿名方法的基础上，通过用户协作的方式，并以虚拟节点为辅助，弥补了上述设计思想中的不足，并且使隐私匿名度得到提高。

3 本文方案

本文提出的方案是基于分布式结构，包括客户端和服务提供商两部分。具体如图1所示，不同于原先的独立式结构，它考虑了全局信息，通过用户之间的协作来完成，主要涉及三方面内容：（1）如何找到满足用户匿名需求的节点数；（2）怎样求取多个节点的密度中心作为锚点；（3）怎样才能方便地获得用户的查询结果候选集以及最后筛选出精确解。

图1 分布式用户查询服务模型

（1）用户模型：对于用户来说，需要保证攻击者是没有办法把他的位置以及查询结果与其标识符具体的对应起来。本文通过选取一个锚点，以此隐藏用户真实的位置信息。进而，所有用户的查询内容都与锚点的坐标位置对应起来。例如，假设用户U1，U2，…，Un，各点真实位置坐标分别为（χ1，y1），（χ2，y2），…，（χn，yn），其中所有用户协作选取的锚点U0坐标为（χ0，y0）。假定原查询请求分别为：U1：（（χ1，y1），Initial-Q1），U2：（（χ2，y2），Initial-Q2），…，Un：（（χn，yn），Initial-Qn）。则有了锚点 U0后实际查询请求分别为：U1：（（χ0，y0），Q1），U2：（（χ0，y0），Q2），…，Un：（（χ0，y0），Qn）。其中Qi定义如下：

定义1 查询Qi定义为：Qi=｛（χ0，y0），t，reqi，mi｝，其中，（χ0，y0）表示查询输入的位置信息，在本文方案中指的是锚点坐标；t表示提出查询的时刻；reqi表示第i个用户请求查询的内容；mi表示查询处理过程中返回的候选集内节点个数，mi的值越大，返回的节点个数越多，也越有利于用户找到最优的结果，但处理效率会降低，这由用户具体权衡。

定义2 关于匿名区k-AR的表示如下：k-AR=｛gid，k，anchor｝，其中，gid表示匿名组的编号；k表示匿名区内用户节点的个数；anchor表示匿名区的锚点，是通过求取区域的密度中心获得的，每个用户都可使用该位置提出服务请求。

（2）攻击者模型：攻击者可以在网络中窃听到节点的查询内容和返回的查询结果，但不可以篡改。然后再根据事先获取的一些知识，以一定的概率推理出某个查询对应的用户隐私信息。

3.1 查询预处理

假定用户U1作为算法的发起者，发出寻找用户节点共同构建匿名组的请求Discoνer，如算法1所示。U1首先生成新的组编号 gid，发送广播消息＜gid，h＞，h初始设为一个最大值，表示路由转发的最大跳数。之后，等待邻居节点的响应＜res，Ui＞，把发回响应消息的用户节点 Ui加入集合 S中且跳数更改为h-1，继而判断或者h=0时，查找用户节点的步骤完成，否则利用其相邻节点进行下一跳的广播。

初始基于信息熵理论将匿名性进行量化，如式（1）所示：

建立博弈模型，经过一系列的统计和推理，得到如式（2）中所示的策略选择：

其中，si表示节点Ui选择的策略；｛C，D｝为供选择的集合，C是合作，即生成剩下的个节点；D是拒绝，即不产生任何虚拟节点；Gi（C）表示节点Ui选择合作所获取的利益；Gi（D）表示节点Ui选择拒绝所获取的利益，详细求解见式（3）和式（4）。

其中，dj（θj）表示每一节点在θj情形下选择D的可能性；ηj表示节点选择D的期望值。

算法1查询预处理

3.2 锚点计算

在一般k-匿名算法中，用一个区域坐标代替某一点位置坐标发送给服务提供商用于查询。而在本文中用区域的锚点来替代。这样，不仅达到了 k-匿名的效果，而且降低了通信代价。在计算锚点时，使用如下公式：

其中，（χ0，y0）是所求锚点的坐标；（χi，yi）为用户节点Ui的坐标。

由式（5）很容易求取锚点的坐标，但为保护用户隐私，本文引入了安全多方计算技术，设计了算法2。这样就可以在不知道每个点的准确坐标情况下，求取所有节点坐标之和，继而得到笔者想要的结果，并且很好地抵御了攻击者窃取位置信息的威胁。

算法2计算锚点

图2 锚点计算过程

假定有6个用户参与锚点计算，根据安全多方求和策略，这些用户秘密选择的计算次序为 U1-U3-U4-U2-U6-U5，每个用户分别对应计算一次，当U5计算完成返回结果给U1，进而 U1便可得到锚点的坐标。

3.3 查询处理

前面匿名的过程已处理完毕，而如何用锚点坐标去查询用户所想要的结果仍很关键。本文采用了 Voronoi图的方法，该方法更加清晰简便。Voronoi图的作用在于当平面中有N个查询结果（对应查询空间内的 N点），对于每个点 Pi，可以很容易找到平面内距离点 Pi比距离其他点更近的区域。据此可以利用它作为查找最优结果的工具。可通过对查询返回结果构造一个Voronoi图，具体如图3所示。图中圆点表示对应查询的多个结果，菱形表示锚点U0。

图3 基于Voronoi图的查询结果

当返回候选结果时，选择锚点所在区域的生成点以及周边相邻的结果作为候选集合发送回去。而对于每个用户节点收到候选结果时，使用同样的方法，判断节点具体落在哪个区域内，就可找到想要的结果。例如，图中五角星表示一用户节点 Ui，明显可以看出，它要查询的精确结果就是 Pi。在该查询处理部分考虑了2种方法，具体如算法3所示（对于查询服务器来说，Ui是未知的，而所有 Pi是已知的）。

算法3查询结果处理

上述2种方法的优缺点如下：（1）从用户本身要求考虑，mi值越大，返回的解也就越多，这样有利于用户挑选出一个较为接近的结果，但同时服务效率可能就不高，反之亦然；（2）确定能为用户找到最精确的结果，但查询时间也许会变长。

4 算法分析

本节主要对本文方案的算法从如下方面来进行分析：

（1）隐私保护度：算法的前2个步骤都保证了隐私度：一是构建匿名区，二是计算锚点。初始时，查找另外k-1个节点，共同组建匿名区，并考虑在节点不足的情况下，使用博弈论的思想产生虚拟节点予以补充，以满足k-匿名。之后，计算锚点时，引入安全多方计算技术保护各节点隐私，不仅对于外部攻击者，而且对于内部伪装在用户间的攻击者，也同样能确保安全传输，不暴露位置。另外，该算法的安全性可以控制，即在节点不足时可以生成虚拟节点补充，而且可以通过生成虚拟节点距离的远近，调控节点到锚点的平均距离（Δχ，Δy），这样就可以根据网络环境的好坏，动态地保护隐私。

（2）匿名成功率：考虑用户节点密度低时，要想找到满足匿名需求的节点就会变得很困难。所以，生成虚拟节点是个不错的办法，但虚拟节点由谁生成是个问题。在考虑节点自私的情况，引入博弈论的思想，这样就保证了算法的成功实行，显然在这种情况下，匿名成功率比其他算法明显要高。

（3）效率：就整个查询过程来说，算法 1是节点搜索构建匿名区的过程，所牵涉到的计算都是轻量级的，计算复杂度低。算法2是一个高效的安全多方算法，其通信代价及轮次均为 O（n）。在算法 3中，用Voronoi进行查询处理时，主要分两步，第1步的V图已通过离线过程构造好，直接定位就可找到返回的候选结果，所以复杂度为 O（1），第2步则需根据返回的候选结果集合用户自己构造Voronoi图，复杂度为O（m lb m），m为返回的候选结果个数。所以，查询处理效率较高。

进一步，将本文方案与其他主流方案进行了详细比较，其结果如表1所示。

表1 方案性能比较

由表1可以明显看出本文方案综合性能较强：

（1）安全性：表1中第1种方案，需要一个可信的第三方。而当第三方变得不可信时，它的隐私将受到严重威胁。第 2种方案选取一个锚点用于查询，但它没有达到k-匿名。第3种方案获得了 k-匿名，但没有考虑计算锚点时位置信息的泄露问题。

（2）匿名成功率：这主要针对在用户节点密度低的情况下，第 1种方案显然没有考虑这种情况，第2种不需生成匿名区。

（3）公平性：表1中前3种方案都没有考虑到用户的公平性问题，针对不同用户的主观需求应付出不同的代价。可信第三方：只有第1种需要可信第三方。

（4）效率：第1种方案由于需要返回一个结果集合交给匿名服务器处理，当查询用户过多时，效率会很低。第2种和第3种查询方法一样，都是使用增量近邻查询，能确保找到精确解，需要查询时先对数据库中查询结果按照与锚点的远近进行排序，之后多次提出查询，且每次都需构造供应空间和需求空间进行比较，这些都是在线过程，因而影响了查询效率。

5 结束语

本文采用了分布式的思想，通过用户之间协作，并考虑节点不足情况下，使用贝叶斯Nash均衡算法产生虚拟节点，以完成 k-匿名区域的构建。匿名区生成后，计算锚点，用它来代替区域进行查询处理。在计算锚点坐标值时，引入安全多方求和技术，避免了各点坐标值的泄露。最后，利用Voronoi图思想进行LBS查询，与传统的查询算法相比，更加便利。分析结果表明，本文方案达到了k-匿名的效果，保证了隐私，可使服务质量以及整体系统性能得到提升。

未来研究工作将考虑多服务提供商的情况。此外，目前多数研究方法都是从客户端进行处理，因此，下一步将研究从服务提供者的数据库入手提高安全性和效率。

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

［2］ Sweeney L.k-anonymity：A Model for Protecting Privacy［J］.International Journal on Uncertainty，Fuzziness and Know ledge-based Systems，2002，10（5）：557-570.

［3］ Gruteser M，Grunwald D.Anonymous Usage of Locationbased Services Through Spatial and Temporal Cloaking［C］//Proceedings of the 1st International Con-ference on Mobile Systems，Applications and Services.San Francisco，USA：ACM Press，2003：31-42.

［4］ Gedik B，Liu Ling.A Customizable k-anonymity Model for Protecting Location Privacy［C］//Proceedings of the 1st International Conference on Distributed Computing System s.Columbus，USA：IEEE Com puter Society，2005：620-629.

［5］ Gedik B，Liu Ling.Protecting Location Privacy with Personalized k-anonymity：Architecture and Algorithms［J］.Mobile Computing，2008，7（1）：1-18.

［6］ Liu Xinxin，Liu Kaikai，Guo Linke，et al.A Gametheoretic Approach for Achieving k-anonymity in Location Based Services［C］//Proceedings of INFOCOM’13. Turin，Italy：IEEE Press，2013：2985-2993.

［7］ Beresford A R，Stajano F.Location Privacy in Pervasive Com puting［J］.Pervasive Computing，2003，2（1）：46-55.

［8］ Beresford A R，Stajano F.M ix Zones：User Privacy in Location-aware Services［C］//Proceedings of Pervasive Computing and Communications Workshops.Vienna，Austria：IEEE Press，2004：127-131.

［9］ Zacharouli P，Gkoulalas-Divanis A，Verykios V S.A kanonymity Model for Spatio-temporal Data［C］//Proceedings of ICDEW’07.Washington D.C.，USA：IEEE Press，2007：555-564.

［10］ Palanisamy B，Liu L.Mobimix：Protecting Location Privacy with Mix-zones over Road Networks［C］// Proceedings of ICDE’11.Hannover，Germany：IEEE Press，2011：494-505.

［11］ Liu Xinxin，Zhao Han，Pan Miao，et al.Traffic-aware Multiple Mix Zone Placement for Protecting Location Privacy［C］//Proceedings of INFOCOM’12.Orlando，USA：IEEE Press，2012：972-980.

［12］ Du Suguo，Zhu Haojin，Li Xiaolong，et al.M ix Zone in Motion：Achieving Dynamically Cooperative Location Privacy Protection in Delay-tolerant Networks［J］.IEEE Transactions on Vehicular Technology，2013，62（9）：4565-4575.

［13］ Kido H，Yanagisawa Y，Satoh T.An Anonymous Communication Technique Using Dummies for Locationbased Services［C］//Proceedings of Conference on Pervasive Services.Santorini，Greece：IEEE Press，2005：88-97.

［14］ You T H，Peng W C，Lee W C.Protecting Moving Trajectories with Dummies［C］//Proceedings of Conference on Mobile Data Management.Mannheim，Germany：IEEE Press，2007：278-282.

［15］ Tran M T，Echizen I，Duong A D.Binomial-mix-based Location Anonymizer System with Global Dummy Generation to Preserve User Location Privacy in Locationbased Services［C］//Proceedings of Conference on Availability，Reliability，and Security.Krakow，Poland：IEEE Press，2010：580-585.

［16］ Miura K，Sato F.A Hybrid Method of User Privacy Protection for Location Based Services［C］//Proceedings of CISIS’13.W ashington D.C.，USA：IEEE Press，2013：434-439.

［17］ Khoshgozaran A，Shirani-Mehr H.SPIRAL：A Scalable Private Inform ation Retrieval Approach to Location Privacy［C］//Proceedings of M obile Data Management Workshops.Washington D.C.，USA：IEEE Press，2008：55-62.

［18］ Mouratidis K.Strong Location Privacy：A Case Study on Shortest Path Queries［C］//Proceedings of ICDEW’13. Brisbane，Australia：IEEE Press，2013：136-143.

［19］ Yiu M L，Jensen C S，Huang Xuegang，et al.Spacetwist：Managing the Trade-offs Among Location Privacy，Query Performance，and Query Accuracy in Mobile Services［C］//Proceedings of ICDEW’08.Cancun，Mexico：IEEE Press，2008：366-375.

［20］ 黄 毅，霍 峥，孟小峰.CoPrivacy：一种用户协作无匿名区域的位置隐私保护方法［J］.计算机学报，2011，34（10）：1976-1985.

编辑 金胡考

User Privacy Protection for Location-based Service

PEI Yuanyuan1，2，SHI Runhua1，2，ZHONG Hong1，2，ZHANG Shun1，2
（1.Key Laboratory of Intelligent Computing&Signal Processing，Ministry of Education，Anhui University，Hefei 230039，China；2.School of Computer Science and Technology，Anhui University，Hefei 230601，China）

With the development of sensor technology and mobile communication equipments，there appears Locationbased Service（LBS），which is widely used.However，privacy issues，which arise in the enjoyment of the services at the same time，are becoming the focus of research.For privacy protection issues in LBS，this paper proposes a distributed model with users’cooperation and designs a new privacy protection scheme.In this scheme，when constructing the anonymous area，it uses Bayesian Nash equilibrium and secure multiparty summation technologies to ensure the user information privacy.When processing the query results，it introduces the Voronoi map method to increase the query efficiency.Analysis experimental result shows that the proposed scheme gives full consideration to the selfishness and unreliability of users.Hence it not only can provide the protection of user privacy，but also can improve the performance of the services.

location privacy；user collaboration；Bias Nash equilibrium；secure multiparty summation；Voronoi map

裴媛媛，石润华，仲 红，等.面向位置服务的用户隐私保护［J］.计算机工程，2015，41（10）：20-25.

英文引用格式：Pei Yuanyuan，Shi Runhua，Zhong Hong，et al.User Privacy Protection for Location-based Service［J］. Computer Engineering，2015，41（10）：20-25.

1000-3428（2015）10-0020-06

A

TP309

国家自然科学基金资助项目（61173187，61173188，11301002）；安徽省自然科学基金资助项目（11040606M 141，1408085QF107）；安徽大学博士科研启动经费基金资助项目（33190187）；安徽大学“信息安全”新专业基金资助项目（17110099）。

裴媛媛（1991-），女，硕士研究生，主研方向：信息安全；石润华、仲 红，教授、博士生导师；张 顺，讲师、博士。

2014-11-04

2014-12-05E-m ail：992755870@qq.com