基于位置隐私保护研究综述

秦　波,　唐秋楠,　王美琪

(中国人民大学 信息学院，北京　100872)

基于位置隐私保护研究综述

秦波,唐秋楠,王美琪

(中国人民大学 信息学院，北京100872)

摘要：近年来，随着无线通信技术和定位技术的发展，与基于位置服务(Location-Based Services，LBS)有关的应用受到越来越多人的使用和重视.一方面LBS为人们的生活带来了很大的便利，而另一方面用户的隐私泄露风险也成为最大的安全威胁.用户的隐私主要包括用户时空位置隐私、有关时间序列的轨迹隐私和用户身份隐私.国内外研究学者针对该问题的基于不同的隐私保护技术系统结构提出了诸多解决方法，可分为假名技术、假位置技术和隐匿时空技术，分别保护了用户的身份信息隐私、位置隐私和轨迹隐私.本文对比现有的隐私保护技术，分析了LBS面临的挑战，归纳了现有的研究工作，并指出了未来的研究方向.

关键词：基于位置服务(LBS);隐私保护;假名;假地址;隐匿时空

唐秋楠，女，本科生，研究方向为信息安全.E-mail:shirley3207@sina.com.

王美琪，女，本科生，研究方向为信息安全.E-mail:rucwmq@163.com.

0引言

随着无线通信技术和定位技术的发展，随时随地实现定位已经成为可能，越来越多用户表现出了对这一服务的强烈需求，基于位置服务(LBS)在这个时代受到越来越多的重视.基于位置服务，是指通过电信移动运营商的无线电通讯网络或外部定位方式，获取移动终端用户的位置信息，在地理信息系统(Geographic Information System，GIS)平台的支持下，为用户提供相应服务的一种增值业务.它包括两层含义：首先是确定移动设备或用户所在的地理位置*数据来源：http://www.ctsbw.com/research/2013/0623/2189.html.；其次是提供与位置相关的各类信息服务,意指与定位相关的各类服务系统，简称“定位服务”，另外一种叫法为MPS-Mobile Position Services， 也称为“移动定位服务”系统*数据来源：http://www.zuitech.com/2509.html.,如找到手机用户的当前地理位置，然后在某范围内寻找手机用户当前位置处1 000 m范围内的宾馆、影院、图书馆、加油站等的名称和地址.所以说LBS就是借助互联网或无线网络，在固定用户或移动用户之间，完成定位和服务两大功能.2011年市场研究公司Strategy Analytics发布的报告就称，到2016年基于位置服务的市场将达到100亿美元*数据来源：http：//www.strategyanalytics.com/..

然而，在人们享受基于位置服务带来的便捷的同时，也同样为自己的隐私安全感到担忧：自己的行踪可能被不怀好意的人获取，“自己在哪里”、“做过什么”、“将要做什么”都有可能被追踪.美国著名的以签到形式提供的基于位置服务的网站Foursquare*数据来源： https：//foursquare.com/.，在2010年推出运行于iOS系统上的自动签到功能，在某人到达任何一个曾经去过的地方300 m之内时，其手机客户端就会自动签到.英国伯明翰大学的一个研究团队在2012年开发出了一种算法，将手机上的追踪数据和用户手机里社交圈子中联系人的追踪数据相结合，便能预测用户在24 h之内会去什么地点，平均误差仅为20 m.同时近年来，苹果公司接连爆出通过基于位置服务窃取用户隐私的事件.苹果iOS系统中有一个隐藏较深的目录，该目录有一个英文名称为“加密”的数据库文件，详细记录了用户位置信息、移动的时空轨迹.该文件记录的位置信息精确到了小数点后8位，同时还对位置数据的可信度进行了评估.该文件也并未加密，而是以明文形式放置在一个隐藏较深的位置.另外，立体实景地图也已被应用到导航电子地图中,这些实景导航地图可以360°旋转查看，帮助用户更精确地找到目的地，给用户带来更高效直观的使用体验.数据显示，截至2013年底，我国手机地图导航APP市场累计用户数已达11.5亿户*数据来源：http：//www.qnsb.com/fzepaper/site1/qnsb/html/2014-04/14/content_488490.htm..2010年美国曾经出现过一个名为“Please Rob Me”*数据来源：http：//pleaserobme.com/.的网站，该网站以实时地图的形式把从Twitter上抓取来的用户签到地址显示出来，该网站的创始人警告，窃贼有可能通过这些数据行窃.越来越多的事实表明，基于位置服务在给人们的生活带来便利的同时也给用户的隐私安全带来了极大的威胁，完全安全地享受基于位置服务是不可能的.因此,近年来研究人员一直致力于寻求,在最少暴露个人信息的情况下最多地享受位置服务便利的方法.本文主要分为5个部分：第1节介绍基于位置服务的工作机制和应用模式；第2节介绍现有的基于位置服务的安全威胁；第3节介绍基于位置隐私服务的系统结构和主要技术及对比；第4节归纳总结目前面临的挑战和已有的研究成果，指出未来的可能的研究热点和方向；第5节为结束语，总结全文的内容.

1基于位置服务的工作机制和应用模式

1.1　LBS系统模型

基于位置服务的参与方有定位系统、用户(移动设备)、网络服务提供商和基于位置服务提供商，如图1所示.

图1　基于位置服务系统模型Fig.1　System structure of location-based services

(1) 定位系统

通常包括基站定位系统、GPS卫星定位系统、无线定位系统和小区识别码定位系统.用户通过这些系统提供的位置信息发起基于位置服务请求.

(2) 用户(移动设备)

移动用户通过蜂窝基站或者无线热点接入互联网，通过定位系统提供的信息发起位置服务请求.

(3) 网络服务提供商

网络服务提供商为使用移动设备的用户和基于位置服务提供商提供数据传输的承载网络.

(4) 基于位置服务提供商

基于位置服务提供商在网络上部署服务器，为用户提供不同类型的基于位置服务.服务器接受包含用户位置信息的基于位置服务请求，对接收到的信息进行计算处理并返回结果给相应的用户.

基于位置服务由移动通信网络和计算机网络结合而成，用户在移动终端发起位置服务请求，通过移动通信网络经过网关到达LBS服务平台，服务平台根据用户请求和用户当前位置做出处理，返回终端.

1.2　LBS的应用模式

LBS的应用模式目前有休闲娱乐模式、生活服务模式、交友互动模式、业务服务模式等几种基本模式[1-7].

(1) 休闲娱乐模式

签到(Check-in)模式： 国外主要是以Foursquare为主，类似的还有Gowalla*数据来源：http：//blog.gowalla.com/.、Whrrl*数据来源：http：//whrrl.com/.等;而国内则有“街旁”*数据来源：http：//jiepang.com/.、“在哪”等.用户的使用方式是主动签到，商家为了鼓励签到会附送积分金币等.

游戏模式： 国外的代表是Mytown；国内则是16Fun*数据来源：http：//www.wiselinc.com/..即在游戏中显示现实生活中存在的建筑，如商场等，使用游戏币就可以购买这些建筑物和道具.它具有消费和互动，比签到模式更具粘性.

(2) 生活服务模式

周边生活服务的搜索： 以点评网或者生活信息类网站与地理位置服务相结合的模式，如大众点评网*数据来源：http：//www.dianping.com/.、台湾的“折扣王”等，主要体验在于工具性的实用特质.

与旅游的结合： 旅游具有明显的移动特性和地理属性，LBS和旅游的结合是十分紧密的，可以在旅游的地方发起位置服务请求，如查询攻略或周边景点价格，代表是切客网*数据来源：http：//www.qieke.com/..

会员卡与票务模式： 实现一卡捆绑多种会员卡信息的形式，同时加入电子会员卡形式，更加方便快捷，充分地使用户感受到大量的优惠信息聚合，代表是国内的Mokard(M卡)及票务类型的Eventbee.

(3) 交友互动模式

地点交友，即时通讯：不同的用户因为在同一时间处于同一地理位置，用户可以通过发起位置服务请求来进行交友活动，代表是兜兜友*数据来源：http：//ddy.me/.、微信“摇一摇”、QQ“附近的人”、陌陌*数据来源：http：//www.immomo.com/.等.

以地理位置为基础的社区服务：即居民社区生活服务，代表是“区区小事”.

(4) 业务服务模式

美国的GroupTabs*数据来源：http：//grouptabs.xmartin.de/.： 使用这个应用的用户到一些签约商家，比如超市，到达后使用GroupTabs的手机应用进行签到.当签到的数量达到一定值后，所有进行过签到的用户就可以得到一定的折扣和优惠，使用户并没有提前参加团购，却能享受团购服务的目的.

ShopKick*数据来源：http：//www.shopkick.com/index.：当用户进入指定的商场，完成指定的行为或者到达指定位置后便赠送虚拟点数用以兑换商品.ShopKick与之前所提到的游戏模式恰好是相反的两种服务，游戏模式是将现实虚拟化，ShopKick是将虚拟现实化.

2LBS的安全威胁

从用户关注的隐私角度可以将隐私分为时空位置隐私、关于时间序列的位置隐私即轨迹隐私和用户身份隐私.时空位置隐私风险是，用户如果被精确定位，那么用户与当前所在地有关的兴趣爱好等信息有可能在查询信息中被获取，如通过获取用户最近去过的医疗服务或者娱乐场所了解用户的健康状况、喜好、外出活动的时间和范围.轨迹隐私是当用户的位置连续更新的时候，用户有被跟踪的风险.用户身份隐私是指用户的身份信息可能会因位置或查询内容的泄露而被人获知.

从LBS整个数据传输路线来看，存在隐私风险的主要有外部的攻击者、系统内部(包括服务器和系统管理人员)和用户自身等方面.

外部攻击者窃取信息的方式可以有被动和主动两种形式.被动攻击中攻击者被动地收集用户位置信息，在此基础上来估计用户的真实地址.攻击者可以利用用户所处环境的背景知识、用户的社会关系和隐匿空间算法的漏洞等信息来推测相关信息，典型的攻击类型有基于语义的攻击[8]、区域中心攻击、区域边界攻击[9]、伪装用户攻击、社会工程攻击[10]等.主动攻击中，攻击者不但被动收集用户位置信息而且主动发恶意信息给用户，从而迫使用户位置隐私保护方法失效，以获取用户真正的位置，典型的攻击类型有诱探位置信息攻击、洪水攻击[11]等.

系统内部和用户自身的隐私泄露主要是有两种情况：人员方面和系统方面.人员方面，有用户自身主动公布自己位置的情况，或者用户和其他用户共享位置信息时，其他用户将信息泄露出去的情况；有系统管理员窃取信息或者内部人员不规范操作导致信息泄露的情况.系统方面，基于位置服务器、定位系统都存在着信息泄露的风险.

3现有的隐私保护主要技术及对比

3.1　LBS相关隐私定义

与LBS应用相关的隐私在不同的应用场景下有不同的侧重点，如某人患有某种隐私疾病不希望别人知道，需要去相关专科医院治疗却不知道路线，使用位置服务查询路线，那么这位用户关注的位置隐私实际上是他的个人信息而不是所在的位置或者移动的轨迹；而在另一个场景下，某用户外出旅行，在陌生环境下不知道路线，使用LBS查询，那么这位用户关注的位置隐私则是他所在的位置和行动的路线且是否会被他人获取.LBS请求主要包括用户标识、位置和服务请求内容这3个方面.因此LBS的隐私即为这3个方面的隐私.

3.2　LBS隐私保护技术

LBS隐私保护技术包括LBS隐私保护系统结构和LBS隐私保护算法.

3.2.1LBS隐私保护系统结构

目前的隐私保护系统结构主要有独立结构、中心服务器结构和点对点结构等3种.

3.2.1.1独立结构

独立结构[12]是仅由移动客户和位置数据库服务器组成的客户端/服务器结构，如图2所示.这种结构中，移动用户直接和LBS提供商通信.因此要求用户的移动设备具有定位能力而且拥有强大的计算能力和存储能力.由于用户是和LBS服务器直接单独联系，无法掌握全局信息，故位置匿名效果较差.

图2　独立结构Fig.2　Non-cooperative architecture

3.2.1.2中心服务器结构

中心服务器结构[13-15]是在移动用户和LBS服务器之间加入可信的第三方中心服务器，用来实现中间的位置匿名和查询结果处理,如图3所示.中心服务器的主要作用是：①收集用户发起的LBS请求并且记录用户位置信息；②根据用户个性化匿名保护需求结合已保存的信息，采用不同的匿名算法进行位置匿名；③代替用户向LBS服务器发出服务请求，并得到返回结果.中心服务器的优点是减少了用户端的计算量，缺点是当有大量用户发起请求时服务器有可能成为系统的瓶颈;而且作为整个系统的关键,对服务器的可信度和可用性要求极高，用户需要承担服务器不安全带来的安全风险.

图3　中心服务器结构Fig.3　Centralized architecture

3.2.1.3点对点结构

点对点结构中，移动用户通过固定的通信设备进行沟通，如基站,如图4所示.移动用户彼此匿名参与，是平等的.当用户发起LBS请求时，该用户的终端会根据已经收集到的其他用户的信息生成一个隐匿空间来代替自身的精确位置，并发送给LBS的提供商，这里进行了类似于服务器的工作.该模式的优点是不需要可信的第三方服务器，缺点是对用户的移动设备计算能力要求较高.

图4　点对点结构Fig.4　Peer-to-peer architecture

3.2.1.4隐私保护系统结构对比

隐私保护系统结构对比如表1所示.

表1　隐私保护系统结构对比Tab.1　Comparison of privacy protection systems

3.2.2LBS隐私保护算法

用户发出的LBS请求可以表示为一个三元组(用户身份信息UserID，位置Location，查询Query)，再加上发出请求的时间(轨迹)，每一个服务请求相关的元素就有4项.隐私保护算法就应从这4个方面出发进行保护.因此，隐私保护算法可以分为用户身份信息隐私保护技术、位置隐私保护技术、查询隐私保护技术和轨迹隐私保护技术.

3.2.2.1用户身份信息隐私保护技术

这一技术的典型代表为假名技术[16].假名技术是对用户标识进行保护的一种方法：让用户在发送请求的时候使用一个虚假的用户身份来代替真实的用户身份，以达到混淆LBS提供商的用户身份和位置对应关系的目的.这种技术的代表是混淆区域技术(Mix-zone)[17],如图5所示.该技术将区域划分为普通应用区域和位置混淆区域，进入混淆区域前用户使用的是假名，混淆区域中所有用户都不可以将自身信息发送给LBS提供商，在离开混淆区域之前用户要更换假名.混淆区域技术的缺点在于限制用户在混淆区域内使用LBS，那么对于一些需要持续提供位置信息的服务比如导航就不能使用了；同时，对于用户的统一混淆区域设置不能满足用户的个性化需求，这也是实际应用中的一个重要问题.

图5　混淆区域Fig.5　Mix-zone

3.2.2.2位置信息隐私保护技术

假位置技术[18]是保护用户位置的方法，是用户使用假的或者错的位置来代替自己的真实位置并加入到服务请求中.具体的实施中，如图6所示，用户会在发送正确地址的同时，按照一定策略生成一组假位置信息一同发送给服务器.该技术的缺点是大量的假地址会增加位置服务器的计算开销和服务请求的等待时间.

图6　假位置Fig.6　Faked locations

地标技术(Landmark)[19]是假位置技术的另一种形式.该技术的操作方法是让用户采用一个标志性的地理位置来代替其真实的位置，并将这个标志性地理位置发送给LBS提供商，LBS提供商只通过这个标志性的地理位置来处理服务请求并返回结果.这种技术的安全性在于攻击者只能获取用户所在位置附近的地标建筑，无法获知真实地址.地标位置越远，隐私保护效果越好，但是过于远又会造成服务质量的下降.

隐匿空间保护技术的主要思想是使用一个通过匿名算法生成的模糊区域来代替用户真实的精确位置，从而将用户隐藏在一定面积的地理区域里.在这个区域同时包含了数量为K的移动用户时，在这个区域上便实现了对用户位置隐私的K-匿名保护.从隐私保护角度来看，面积越大则用户越多，保护效果越好；但其缺点是给服务器带来更大的资源开销，给网络传输带来更多的压力，从而导致服务的质量变得更差.因此获取隐私保护质量和位置服务质量的平衡成为一个重大课题.

文献[20]中由Duckham等人提出的位置隐私保护机制Obfuscation平衡了服务质量和隐私保护之间的关系，是将用户的标识信息暴露给位置数据库服务器，但服务器并不知道用户的位置信息，而且不需要中间服务器.这种保护机制适用于点对点结构.

间隔匿名算法(Interval Cloak)[21]的基本思想为：位置匿名服务器生成一个基于四叉树的结构，使用递归将欧氏平面空间分成4个面积相等的方形区间，不断划分直到所得到系统要求的最小匿名空间是划分出的最小正方形为止，每一个正方形区间都对应着四叉树中的一个节点；系统中的用户在相同的时间间隔内将自己的位置坐标上报给中间服务器，中间服务器不断统计更新每个节点对应区间内的用户数量和坐标.当用户发起LBS查询时，中间匿名服务器检索四叉树为用户生成一个匿名区，从包含用户的四叉树的叶子节点开始向四叉树根的方向搜索，直到找到包含不少于K个用户的节点(包括用户在内)，并把该节点所对应的正方形区间作为用户的一个匿名区.

集团匿名算法(Clique Cloak)[22]是使不同的用户可以指定任意的隐私要求(K-匿名水平).它主要利用图模型形式化定义此问题，并把寻找匿名集的问题转化为在图中寻找1个包含K个用户的集合问题.每个查询定义1个圆形，用户位于圆心.如果2个查询的圆都包含对应的用户，那么把2个查询连起来，并为其建立1个无向图.在无向图中寻找满足K个用户相互连通的小集团，即在图中实现位置K匿名，然后生成一个包含该集团的最小边界矩形，该矩形即为所求匿名区.

匿名算法(Nearest Neighbor Cloak, NNC)[6]是集团匿名算法的一个随机化的变种.其主要思想是：选定用户的位置u后，首先寻找匿名初始集S，S包含u以及u的(K-1)个最近点；其次从S中随机选择一用户u′,然后寻找u′的(K-1)个最近邻点，这些最近邻点组成集合S′,进而得到匿名集S″=S′∪{u}，之所以要包含u，是因为u不一定是u′的最近邻点；最终得到满足K匿名要求的匿名区域是包含S″的最小边界矩形.

希尔伯特匿名算法(Hilbert Cloak)[6]是唯一被证明安全的匿名算法.该算法主要是使用希尔伯特空间填充弧，将二维空间映射到一维数值即希尔伯特值上，通过B+树来索引这些数值.算法将那些一维存储值划分成K(K-匿名)个用户的不同组，给定隐私要求为K的一个用户查询.Hilbert Cloak存储空间中所有用户的希尔伯特值并将这些用户划分成若干个集合，其中所包含的用户数目的上限为(2K-1).用H(U)表示用户的希尔伯特值，ranKu表示用户的希尔伯特值顺序序列，在集合中的用户组成匿名集 AS(anonymizing set),Ku表示用户的K-匿名要求.通过计算起始位置start和最终位置end来确定哪些段成为 AS，并且返回包含 AS 的最小边界矩形.起始位置和最终位置的计算公式是

start=ranKu-(ranKu-1)modK，

end=start+K-1.

Casper Cloak算法[23]是 Interval Cloak 的一种更复杂的模式.同样采用四叉树划分空间，区别是Interval Cloak 采用逐层划分的方法寻找符合要求的匿名空间，而对于同层节点则不予考虑;Casper Cloak 寻找匿名空间时，首先考虑当前节点能不能满足匿名要求，接着合并相邻节点来判断目前是否满足匿名要求，最后再合并到父节点判断是否满足匿名要求，多了一个合并相邻节点并查询的步骤，使查询更细致.很多时候，满足用户的同一匿名要求时，Casper Cloak 形成的匿名空间比Interval Cloak的要小些.

3.2.2.3查询隐私保护技术

查询内容个性化隐私保护[24]的核心思想是通过L-多样性思想实现.

首先，定义一个查询策略树；其次，向LBS服务器发起个性化服务请求，算法切换个性化的隐私度到K，对查询内容做L-多样性处理，包括真实查询内容在内，额外附加(L-1)条虚拟查询内容，使真实查询意图泄露的概率为1/L；接下来，再对用户隐去用户标识，给所有的信息编号，定义最长服务返回时间等，再计算根据个性化的查询请求，动态确定L的大小，生成查询内容集；最后将前面两步的输出作为请求输入，向LBS服务器提出请求.

3.2.2.4轨迹信息隐私保护技术

轨迹隐私保护技术大致可以分为以下3类[25].

(1)位置泛化法[26-27]

这种方法是把轨迹上需要处理的位置采样点经过匿名算法处理后，变为模糊的匿名区域，从而达到隐私保护的要求，是逐点模糊再连成轨迹，而不是直接对轨迹进行模糊，服务质量要高一些.

(2)假数据法[28]

这种方法通过添加若干的假轨迹数据来对原始的轨迹进行模糊处理，但同时又要保证被干扰或模糊化的轨迹的失真程度在一定范围内.

(3)抑制法[29]

抑制法是在用户运行轨迹上，对那些对用户来说敏感的位置进行抑制而不发送给LBS 服务器，这种方法对于服务质量的影响最大.

表2为3种轨迹隐私保护方法的对比.

表2　轨迹隐私保护方法对比Tab.2　Comparison of trajectory privacy protection technology

3.3　国内外现有LBS隐私保护系统举例

目前已有的LBS隐私保护系统中，主要以中心服务器结构和点对点结构为主.

西安电子科技大学的研究人员提出了一种面向LBS的用户隐私保护系统[30]：采用第三方服务器结构，通过外包云服务器存储来自LBS服务器的加密数据资源，为用户终端提供查询服务，并在提供服务的同时与用户终端之间进行双向身份认证；通过LBS服务器完成系统初始化，为用户终端和外包云服务器提供注册和密钥分发，并为外包云服务器提供加密的位置坐标和详细描述的LBS信息.

为了避免由于第三方服务器不可信造成的安全威胁，美国乔治华盛顿大学的研究学者提出了一种基于点对点模式的LBS隐私保护系统(A Context-Aware Privacy Protection System for Location-Based Services,CAP)[31].该系统的主要思想是先对原有空间的经纬度进行计算，再投影到坐标空间，通过希尔伯特算法实现位置扰动.该系统目前已经在SUSE Linux 11.0和Mac OSX上实现并移植到使用这两类系统的移动终端上.

隐私保护和LBS就像一枚硬币的两面，不可完全兼得：一方面用户希望得到服务平台更好的服务，但实现更好服务的前提是要有精确的定位；另一方面隐私保护技术一直在努力隐藏用户信息，避免隐私泄露.因此研究人员致力于在精确定位和隐私保护之间寻求平衡.在实际的应用中以上的隐私保护技术并不是单一存在的，一般是混合使用.通过以上对隐私保护技术的介绍，可以大致得到隐私保护的特点有以下几点[32-44].

(1)位置隐私信息并不是一个单纯的个体，它包含很多方面的内容，是多维的.那么在进行处理时，应考虑各维度的情况，不能只进行简单的加密处理.

(2)位置信息的即时性.由于请求LBS的用户大多是在移动中的个体，处理数据的效率和速度就十分重要;对于历史信息的处理也尤为关键，为了避免历史信息被攻击者利用，应采取适当方式销毁或者加密历史信息[45].

(3)隐私服务的个性化问题.每一个用户对于隐私的保护程度要求不同，如在休闲娱乐时查询娱乐场所的信息比在医院附近查询医疗有关信息对于隐私的要求就要低些.

4基于位置隐私保护面临的挑战

本文在分析LBS中存在隐私威胁的同时，列举了目前的隐私保护技术，并进行了对比.但位置隐私保护还是一个新兴研究领域，很多具有挑战性的问题还亟待解决[46].

在位置匿名的算法中，目前使用最广泛的是位置K-匿名模型，即保证匿名框至少覆盖K个用户，攻击者无法获知这K个用户的真实位置.这种匿名算法中，在极端情况下K个用户位置都在同一个点上或者都在同一个敏感区域内，如医院、军事区域等时，有隐私泄露风险.文献[47]提出了借鉴数据发布隐私处理的L-差异性思想并应用到位置匿名中，即不但要保证匿名框中隐匿K个用户的信息，也要保证在这个匿名框中有L个不同的位置;同时，文中提及的位置隐私算法都是从保护位置隐私和用户身份隐私出发，没有考虑查询信息的保护，而实际上保证了位置隐私和身份隐私并不能保证查询隐私的安全.因此在位置匿名算法中,不但要满足位置K-匿名同时也要保证查询L-差异性和位置L-差异性，这仍然是具有挑战性的问题.

从隐私的角度来看，目前对于轨迹隐私的研究还不够深入.文献[17]使用了混淆区域概念来研究轨迹隐私保护，但这些算法都是站在保护用户标识的角度，提供的地址信息仍然是真实的信息.文献[48]提出了使用假位置信息来隐藏用户轨迹，仿真(K-1)个假位置来和真实位置构成位置K-匿名保护，但系统形成的这K个位置可能属于只有一个用户的区域，那么这也容易鉴别发出请求的用户.现有的这些位置隐私保护方法中的模糊区域和实际的连续LBS不同，用户随着时间变化形成的模糊区域是相互独立的，当匿名区域中的用户位置概率是不平均分布的时候，区域内不同节点对提出查询的用户的匿名保护程度则不同[49].那么，如何在使匿名区域足够小的同时提供更好的隐私保护是值得探究的问题.

从隐私保护的系统结构来看，在中心服务器结构中，服务器作为系统瓶颈面临着很大的安全风险，成为了攻击者的首选目标，一旦被攻破，隐私保护则无从谈起.同样其他两种结构都存在着用户客户端计算工作量大、网络需求大、隐私保护效果不好的问题.除此之外，点对点模式还存在着临近的用户可信度的问题.

针对目前面对的挑战，部分研究学者又开始研究非K-匿名算法，但目前非K-匿名算法的安全性仍无法和K-匿名算法同日而语[50].同时，位置隐私保护技术正在向基于K-匿名算法和连续查询K-匿名轨迹保护的算法方向发展.文献[51]讨论了使用抑制法对轨迹隐私进行保护的方法；而面对的空间也从基于欧式平面的二维空间向基于道路交通网络的空间发展.文献[52]、文献[53]和文献[54]介绍了有关路网情况下的隐私保护算法.位置隐私服务个性化方面，文献[55]介绍了使用形心偏移法来构造个性化的方法.

5结语

基于位置隐私技术近年来发展迅速，隐私问题也成为了不可避免、要提及的重要话题.国内外大量的文献对于位置隐私保护技术进行了很好的研究，提出了大量有效的算法.本文根据以上线索从LBS的概念、系统结构、应用类型、安全威胁、隐私保护技术和目前存在的问题和挑战等几个方面对基于位置隐私进行了综述，并分析了发展的趋势.总体来说，基于位置隐私技术作为新兴技术仍然有很多值得深入细致研究的地方.

[参考文献]

[1]ILARRI S, MENA E, ILLARRAMENDI A. Location-dependent query processing: Where we are and where we are heading[J]. ACM Computing Surveys (CSUR), 2010, 42(3):12.

[2]PERUSCO L, MICHAEL K. Control, trust, privacy, and security: Evaluating location-based services[J]. IEEE Technology and Society Magazine, 2007, 26(1): 4-16.

[3]SCHILLER J H, VOISARD A. Location-Based Services[M]. San Francisco: Morgan Kaufmann, 2004.

[4]VEIJALAINEN J, WESKE M. Modeling static aspects of mobile electronic commerce environments[M]//Advances in Mobile Commerce Technologies. [s.l.]: IGI Publishing, 2003: 137-170.

[5]BARNES R, LEPINSKI M, COOPER A, et al. An architecture for location and location privacy in internet applications[R]. BCP 160, RFC 6280, 2011.

[6]KALNIS P, GHINITA G, MOURATIDIS K, et al. Preventing location-based identity inference in anonymous spatial queries[J]. IEEE Transactions on Knowledge and Data Engineering, 2007, 19(12): 1719-1733.

[7]XIONG X, MOKBEL M F, AREF W G. Sea-cnn: Scalable processing of continuous k-nearest neighbor queries in spatio-temporal databases[C]//Proceedings of the 21st International Conference on Data Engineering. IEEE, 2005: 643-654.

[8]DAMIANI M L, BERTINO E, SILVESTRI C. The PROBE framework for the personalized cloaking of private locations[J]. Transactions on Data Privacy, 2010, 3(2): 123-148.

[9]GHINITA G, KALNIS P, SKIADOPOULOS S. Prive: Anonymous location-based queries in distributed mobile systems[C]//Proceedings of the 16th International Conference on World Wide Web. ACM, 2007: 371-380.

[10]CHE Y, CHIEW K, HONG X, et al. SALS: semantics-aware location sharing based on cloaking zone in mobile social networks[C]//Proceedings of the 1st ACM SIGSPATIAL International Workshop on Mobile Geographic Information Systems. ACM, 2012: 49-56.

[11]NERGIZ M E, ATZORI M, SAYGIN Y, et al. Towards trajec-tory anonymization:A generalization-based approach[J]. IEEE Transactions on Data Privacy, 2009, 2(1):47-75.

[12]CHENG R, ZHANG Y, BERTINO E, et al. Preserving user location privacy in mobile data management infrastructures[M]//Privacy Enhancing Technologies. Berlin: Springer, 2006: 393-412.

[13]GRUTESER M, GRUNWALD D. Anonymous usage of location-based services through spatial and temporal cloaking[C]//Proceedings of the 1st International Conference on Mobile Systems, Applications and Services. ACM, 2003: 31-42.

[14]XIAO Z, MENG X, XU J. Quality aware privacy protection for location-based services[M]//Advances in Databases: Concepts, Systems and Applications. Berlin: Springer, 2007: 434-446.

[15]HONG J I, LANDAY J A. An architecture for privacy-sensitive ubiquitous computing[C]//Processing of the 2nd International Conference on Mobile Systems, Applications, and Services. ACM, 2004, 177-189.

[16]CHAUM D. Untraceable electronic mail, return addresses, and digital pseudonyms[J]. Communications of the ACM, 1981: 24(2):84-90.

[17]BERESFORD A R, STAJANO F. Location privacy in pervasive computing[J]. IEEE Pervasive computing, 2003, 2(1): 46-55.

[18]HEECHANG SHIN, ATLURI V, VAIDYA J. A profile anonymization model for privacy in a personalized location-based service environment[C]// Proceedings of the 9th International Conference on Mobile Data Management. IEEE, 2008: 73-80.

[19]SHIN K G, JU X, CHEN Z, et al. Privacy protection for users of location-based services[J]. IEEE Wireless Communications, 2012, 19(1): 30-39.

[20]DUCKHAM M, KULIK L. A formal model of obfuscation and negotiation for location privacy[M]//Pervasive Computing. Berlin: Springer, 2005: 152-170.

[21]CHOW C Y, MOKBEL M F, LIU X. A peer-to-peer spatial cloaking algorithm for anonymous location-based service[C]//Proceedings of the 14th Annual ACM International Symposium on Advances in Geographic Information Systems. ACM, 2006: 171-178.

[22]BAMBA B, LIU L, PESTI P, et al. Supporting anonymous location queries in mobile environments with privacygrid[C]//Proceedings of the 17th International Conference on World Wide Web. ACM, 2008: 237-246.

[23]MOKBEL M F, CHOW C Y, AREF W G. The new casper: Query processing for location services without compromising privacy[C]//Proceedings of the 32nd International Conference on Very Large Data Bases. ACM, 2006: 763-774.

[24]CHOW C Y, MOKBEL M F, LIU X. Spatial cloaking for anonymous location-based services in mobile peer-to-peer environments[J]. GeoInformatica, 2011, 15(2): 351-380.

[25]霍峥, 孟小峰. 轨迹隐私保护技术研究[J]. 计算机学报, 2011(10)：1820-1830.

[26]XU T, CAI Y. Exploring historical location data for anonymi-ty preservation in location-based services[C]//Proceedings of the 27th Conference on Computer Communications. IEEE, 2008: 547-555.

[27]TERROVITIS M, MAMOULIS N. Privacy preserving in the publi-cation of trajectories[C]//Proceedings of the 9th International Conference on Mobile Data Management. IEEE, 2008:65-72.

[28]LU R, LIN X, LIANG X, et al. A dynamic privacy-preserving key management scheme for location-based services in vanets[J]. IEEE Transactions on Intelligent Transportation Systems, 2012, 13(1): 127-139.

[29]FREUDIGER J, SHOKRI R, HUBAUX J P. Evaluating the privacy risk of location-based services[M]//Financial Cryptography and Data Security. Berlin: Springer, 2012: 31-46.

[30]朱辉, 李晖, 高丽娟, 等. 面向基于位置服务的用户隐私保护系统及方法: 中国,CN104219245A[P]. 2014-12-17.

[31]PINGLEY A, YU W, ZHANG N, et al. Cap: A context-aware privacy protection system for location-based services[C]//Proceedings of the 29th IEEE International Conference on Distributed Computing Systems. IEEE, 2009: 49-57.

[32]魏琼, 卢炎生. 位置隐私保护技术研究进展[J]. 计算机科学, 2008(09)：21-25.

[33]EL DEFRAWY K, TSUDIK G. Privacy-preserving location-based on-demand routing in MANETs[J]. IEEE Journal on Selected Areas in Communications, 2011, 29(10): 1926-1934.

[34]HU H, LEE D L. Range nearest-neighbor query[J]. IEEE Transactions on Knowledge and Data Engineering, 2006, 18(1): 78-91.

[35]余荣芳. 位置服务隐私保护技术的研究与应用[D].南京：南京理工大学, 2013.

[36]王璐, 孟小峰. 位置大数据隐私保护研究综述[J]. 软件学报, 2014(04)693-712.

[37]潘晓, 肖珍, 孟小峰. 位置隐私研究综述[J]. 计算机科学与探索, 2007(03)268-281.

[38]郭艳华. 位置服务中轨迹隐私保护方法的研究[D].武汉：华中师范大学, 2011.

[39]谈嵘. 位置隐私保护及其在基于位置的社交网络服务中的应用研究[D].上海：华东师范大学, 2013.

[40]车延辙. 基于位置服务中用户位置隐私保护关键技术研究[D].杭州：浙江大学, 2013.

[41]屈浩. 基于轨迹隐私的匿名方法研究[D].成都：电子科技大学, 2013.

[42]张浩. 基于位置服务的信息隐私保护技术研究[D].合肥：中国科学技术大学, 2014.

[43]娄绿林. 基于位置服务(LBS)的隐私保护方案研究[D].昆明：昆明理工大学, 2013.

[44]郭晓丽. 基于位置服务的移动对象隐私保护技术研究[D].哈尔滨：哈尔滨工程大学, 2013.

[45]GHINITA G, KALNIS P, KHOSHGOZARAN A, et al. Private queries in location-based services: Anonymizers are not necessary[C]//Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. ACM, 2008: 121-132.

[46]CHENG R, ZHANG Y, BERTINO E, et al. Preserving user location privacy in mobile data management infrastructures[M]//Privacy Enhancing Technologies. Berlin: Springer, 2006: 393-412.

[47]GEDIK B, LIU L. Location privacy in mobile systems: A personalized anonymization model[C]//Proceedings of the 25th IEEE International Conference on Distributed Computing Systems. IEEE, 2005: 620-629.

[48]KIDO H, YANAGISAWA Y, SATOH T. An anonymous communication technique using dummies for location-based services[C]//Proceedings of the International Conference on Pervasive Services. IEEE, 2005: 88-97.

[49]KANG H E, MENG W U. Protecting location privacy with personalizedK-anonymity[J]. Journal of Nanjing University of Posts and Telecommunications (Natural Science), 2012(6): 014.

[50]贾金营, 张凤荔. 位置隐私保护技术综述[J]. 计算机应用研究, 2013(03)：641-646.

[51]王家波. 基于位置服务的轨迹隐私保护技术研究[D].杭州：杭州电子科技大学, 2014.

[52]侯士江. 基于空间K-匿名的位置隐私保护技术研究[D].秦皇岛：燕山大学, 2014.

[53]薛姣, 刘向宇, 杨晓春, 等. 一种面向公路网络的位置隐私保护方法[J]. 计算机学报, 2011(05)： 865-878.

[54]LUPER D, CAMERON D, MILLER J A, et al. Spatial and temporal target association through semantic analysis and GPS data mining[C]//Proceedings of the 2007 International Conference on Information and Knowledge Engineering. IKE, 2007:251-257.

[55]许隽. 基于位置服务中个性化位置隐私保护模型与算法的研究[D].广州：华南理工大学, 2013.

(责任编辑李艺)

Review on location privacy protection research

QIN Bo,TANG Qiu-nan,WANG Mei-qi

(SchoolofInformation,ReminUniversityofChina,Beijing100872,China)

Abstract:In recent years, with the development of wireless communication technology and mobile positioning technology, applications relating to location-based services (LBS) are increasingly taken seriously and used widely. On the one hand, LBS brings people considerable convenience; on the other hand, it becomes a non-negligible security threat that users’ privacy, mainly including location privacy, trajectory privacy and identity privacy, could be leaked out. Many solutions on the basis of different structures of privacy protection system have been proposed by researchers at home and abroad, which can be divided into pseudonym, faked locations and spatial and temporal cloaking, protecting users’ identity privacy, location privacy and trajectory privacy respectively. In this paper, we contrast the existing privacy protection technologies and analyze challenges LBS is facing. At the same time, we conclude the existing researches and give directions for future research.

Key words:location-based services;privacy protection;pseudonym;faked locations;spatial and temporal cloaking

作者简介：秦波，女，博士，讲师，研究方向为信息安全.E-mail:bo.qin@ruc.edu.cn.

基金项目：国家自然科学基金面上项目(61370190，61173154，61472429)；中国人民大学中央高校基础科研基金(14XNLF02)

收稿日期：2015-06

中图分类号：TP391

文献标识码：ADOI:10.3969/j.issn.1000-5641.2015.05.002

文章编号：1000-5641(2015)05-0014-14