随着智能手机和无线网络的广泛应用，移动应用近年来呈现出爆炸式的增长。据统计2014年全球移动应用的使用量增长了76%[1]。至2014年底，谷歌Play拥有143万款应用，AppleStore拥有121万款应用[2]，其中基于位置的服务(Location-basedService,LBS)备受用户青睐。以百度地图为例，从2012年成立至今，用户数从最初7000万增长到超2亿活跃用户[3]，它提供的定位、导航、查询等位置信息服务为现代生活带来了极大的便利。然而，用户提交的位置服务请求和自己的位置信息在一定程度上会对个人的隐私造成泄露风险[4][5]。一方面，对某些用户而言，其位置信息本身就是隐私数据；另一方面，攻击者可以根据位置信息来推测用户的个人身份、工作性质、健康状况或者兴趣爱好等隐私信息[6]-[9]。
近年来，学术界对位置隐私保护问题进行了广泛的研究，并提出了一系列保护方法。从已有的位置隐私保护技术来看，可以将其分为四类，即空间模糊化、虚拟对象、隐私信息检索(PrivacyInformationRetrieval,PIR)和差分隐私保护。其中，空间模糊化技术是将用户的真实位置模糊成一个满足用户个性隐私需求的空间，并用模糊后的空间代替精确位置提交给位置信息服务器处理；虚拟对象技术将虚拟的对象与真实对象混合在一起作为位置服务请求发送者，使攻击者无法实现位置与用户的准确映射，这种方法的研究重点在于如何合理的选择虚拟对象；PIR技术是基于不可信数据库提出的隐私保护技术，它能实现用户访问服务器的同时阻止服务器获知用户访问内容，提供了高水平的隐私保护，该技术最大的挑战在于设计一个好的检索算法来加快检索效率和降低存储空间；差分隐私是近年来提出的一种新的隐私保护定义，由于其独立于攻击者的背景知识，并提供了严格的、可证明的隐私保护，成为目前隐私保护领域的一个研究热点。
本文首先分析LBS系统所面临的隐私泄露风险，然后对以上四类隐私保护技术的基本原理和实现方法进行综述，通过对已有研究成果的梳理，详细分析和比较这些技术的优缺点，最后探讨位置隐私保护技术在未来的研究方向。
2.LBS的基本结构与威胁分析
2.1.LBS的基本结构
Figure1.BasicframeworkofLBSsystem
端。用户及查询结果的位置信息由定位系统提供。可见，位置信息是LBS网络中传输的最核心数据，也是位置隐私保护的对象。
2.2.LBS面临的隐私泄露威胁
(1)物理威胁：攻击者直接攻击传输网络或者服务器等物理设备获取用户最原始的位置信息；
(2)推理威胁：攻击者在获得用户的位置信息后，利用观察、推理、挖掘等技术推断出关于用户的隐私信息[13]；
(3)联合攻击：攻击者在获得用户位置信息后联合用户使用的其他移动应用等外部资源，对用户隐私进行更深度的挖掘。例如，攻击者可以联合用户的社交网络信息来挖掘用户朋友的隐私信息[14]。
显然，物理威胁只涉及到用户的物理位置信息，推理威胁会危及到用户的个人身份信息，联合攻击则影响到了用户的整个生活环境。位置隐私的泄露是导致以上威胁的根本原因。
3.位置隐私保护技术
近年来，学术界对位置隐私保护的研究取得了丰富的成果，各种隐私保护理论与模型在位置隐私保护中得到应用。本节对已有的位置隐私保护技术进行梳理和比较。
3.1.空间模糊化
从实际应用效果来看，空间匿名技术能够为位置隐私保护提供了一个个性化的解决方案，但其缺点在于对区域的人口密度比较敏感。另外，匿名器的处理性能及其自身的安全性都会影响到空间匿名技术的应用效果。
Figure2.DatastructureofCaspermodel
(a)(b)
Figure3.Relativelocationattack.(a)Forwarddeducing;(b)Backwarddeducing
Figure4.RequirementsofiCliqueCloak
3.2.虚拟对象(Dummy)
Dummy[23]-[26]的保护方式简单来说就是用户在提交位置服务请求时，将自己的真实位置和几个虚假位置一起提交给LBS服务器，LBS服务器针对所有提交的位置分别进行查询处理，将所有结果返还给用户，用户再根据自己的真实位置进行筛选。在Dummy的方法中，如何选择虚拟对象的位置是一个关键问题。对此，文献[24]提出了虚拟对象在分布上的一般性要求，包括分散性、稠密性和均匀性。
Figure5.Circle-baseddummy
Figure6.Grid-baseddummy
Dummy的生成方式解决了Casper模型过于依赖区域人口密度的缺点，但其自身的缺点也不可忽视，PAD算法中取得虚拟位置的方法过于规则化，而忽略了实际的地理特征。例如，按照这种规则化的方式选取的虚拟位置可能在现实环境中根本不可能有活动对象出现，那么这个虚拟位置就失去了混淆攻击者的功能。类似的，如果攻击者预先掌握了一些背景知识，例如地理环境、区域人口密度、运动最大速度等，即可实施背景知识攻击[27][28]，将这些背景知识与获取的用户位置信息结合来推断用户的位置隐私和其他隐私信息。因此，为了阻止背景知识攻击，在选取虚拟位置时要使虚拟位置更接近真实对象的运动特点和规律。
(1)
使用Dummy的位置隐私保护机制的优点在于能够摆脱对现实环境的过度依赖，无论在人口密集区
Figure7.DummyselectioninDLS
还是稀疏区都能较好地满足用户的隐私需求，提高了匿名化的成功率。但这些方法共同的不足在于，攻击者所掌握的背景知识是难以量化和准确建模的，因此在选取虚拟对象时往往忽略了对背景知识的考虑或者仅仅根据特定的背景知识假设提出针对性的解决方案，这样的保护机制无法应对基于新的背景知识的攻击。
3.3.隐私信息检索
在服务器中储存了整个地区的地图和兴趣点(pointsofinterest,POIs)信息，LBS根据索引结构将DB划分为几个子数据库DB1,DB2,…,PIR处理器根据用户的请求对DB1,DB2,…进行查询，并将结果返还给用户。在信息查询过程中，PIR处理器就像一个黑盒子自动完成查询而不让服务器知道它访问了哪些子数据库。因此，这类方法的研究重点在于如何设计索引结构和访问顺序从而减少执行的检索复杂度和储存空间。文献[34]利用Hilbert空间曲线将POI的二维存储方式转化为H值的一维存储方式，减少了存储空间，并将POI根据H值的大小按照B+-tree的结构来组织，以便简化检索次数。文献[33]则将存储区
Figure8.LBSwithhardware-basedPIR
域用网格表示，并用Hilbert值表示每个网格单元，同时建立了3个数据库DB1,DB2,DB3来分别存储POI的不同信息。DB1按照H值的顺序存储每个网格单元中POI的数量信息，DB2按照H值存储每个POI的ID、坐标和指向DB3的指针，DB3存储了每个POI的其他详细信息。这样的存储结构能够在不遍历整个数据库的前提下高效地进行kNN(kNearestNeighbor)查询。首先根据用户的位置信息在DB1中查找kNN，然后在DB2中确定kNN的ID和坐标，并根据指针在DB3中获取kNN的详细信息。除此之外，还为每个查询建立了查询计划，保证每个查询都按照同样的顺序和次数进行检索，以避免外部的模式攻击。
3.4.差分隐私
差分隐私是由Dwork在2006年提出的一种新的隐私安全定义[41]。它能够保证数据集的查询结果对某个具体记录的变化不敏感，因此，一个记录存在于一个数据集里，就像它不存在于数据集里一样安全，攻击者无法通过观察和计算查询结果来推测用户的隐私信息[42]。差分隐私的定义[43]为：设随机算法M，Range(M)为M所有可能的输出集合，对于任何两个邻近数据集D1和D2，以及Range(M)的子集，若算法M满足：
则称算法M提供ε-差分隐私保护，其中ε称为隐私保护预算。从原理上看，隐私实质上是将数据集的精确查询结果转化为一个分布，使得对两个邻近数据集进行查询得到相同结果的概率几乎相同。Laplace机制[44]和指数机制[45]是两种最基本的差分隐私实现机制。其中，Laplace机制用于查询结果为数值型的情况，指数机制则用于保护非数值型查询结果。
由于差分隐私无需考虑攻击者掌握的任何背景知识，并能提供严格可证明的隐私保护，因此在隐私保护数据发布[46]-[49]和隐私保护数据挖掘[50]-[54]等方面得到广泛的研究和应用。显然，差分隐私更适用于保护多用户的聚合信息，在只涉及单个用户的位置隐私保护问题上并不合适。根据差分隐私的定义，用户位置的变化对查询结果的影响须微乎其微，这使得查询变得毫无意义。为解决这一问题，文献[55]将差分隐私与k-anonymity结合起来，提出了一种混合模型，对于由k个位置构成的匿名集合，在提交位置时要求以相近的概率（小于）输出k个位置中的任意一个。该模型的主要问题在于，匿名集合的选取对最终的隐私保护结果影响过大。
为此，文献[56]利用差分隐私的定义，提出了一种地域不可区分模型(Geo-Indistinguishability)。该模型基于位置隐私保护的现实，认为用户位置的微小变化应该对查询结果影响很小，但当用户位置变化较大时，查询结果可以有较大的变化，因此可以根据用户位置的变化程度来设定相应的隐私保护水平。Geo-Indistinguishability的定义为：设X表示用户可能的位置集合，Z表示可能发布的位置集合，d(·,·)表示欧氏距离，对于任意两个位置和并且，若算法K满足：
如何降低噪声量是差分隐私在应用中无法回避的问题。文献[57]认为，Geo-Indistinguishability模型在保护单个位置(用户只进行一次查询)时是有效的，但一个用户往往会进行多次查询，连续的位置变化会形成轨迹，如果将Geo-Indistinguishability独立地应用到每个位置上，所产生的噪声量将是不可接受的。根据差分隐私中位数机制(medianmechanism)[58]的基本思想，充分利用查询之间的关联关系，可以有效提高隐私保护预算的利用效率，因此，文中提出了一种针对位置保护的可预测差分隐私机制。该机制由预测函数、加噪机制和测试机制构成。预测函数根据先前提交的位置来预测当前须提交的新位置，然后由测试机制来测试与用户当前位置的距离是否在某个阈值之内，如果是，则直接提交，否则才调用加噪机制来产生新的位置。由于仅在调用加噪机制时才消耗隐私保护预算，所以可极大地提高预算利用率，降低噪声。另外，文献[59]针对降噪问题提出了一种面向位置数据发布的差分隐私保护算法
Figure9.Privacylevelvarieswithr
(PriLocation)。位置数据发布的内容通常包括用户到过的位置集及其统计频次，如果直接应用差分隐私来保护发布的内容，将会因为位置频次的稀疏性导致噪声量过大。PriLocation算法由位置聚类、权重干扰、位置选择等三个操作构成，首先根据距离将所有位置划分到k个簇中，每个位置则泛化为其所在的簇；然后将每个用户的位置统计频次转化为簇的频次统计，并用Laplace噪声进行干扰；最后利用指数机制从涉及的簇中选择位置作为用户到过的位置。由于簇的数量要远小于位置的数量，使得加入噪声的次数急剧减少，从而降低了噪声量。
差分隐私的主要优点在于它对攻击者所掌握的背景知识完全免疫，能够为用户提供强健的隐私保护。但从其在位置隐私保护中的应用效果来看，在有些方面还有待继续深入的研究，包括：(1)在处理高敏感度查询时，添加的噪声过大，会极大地降低数据的可用性；(2)给定的隐私预保护算会限制数据查询次数；(3)计算复杂度普遍较高。
3.5.小结
总的来看，空间模糊化和虚拟对象技术相对成熟，能够较好地达到数据安全性和可用性的平衡，在目前来说，实用性相对较好；PIR技术由于基于密码学基础，能够提供高水平的隐私保护，但计算代价高是其主要劣势，因此主要更适合于安全级别要求较高的场合；差分隐私能够提供可控的和可证明的隐私保护，但噪声大进而影响到数据可用性是有待继续研究的问题。
4.未来的研究方向
位置隐私保护是一个相对年轻的研究领域，从目前的研究现状来看，在理论基础和实现技术等许多方面尚有待深入研究。同时，随着移动通信业务的不断推陈出新，位置隐私保护也必将面临更多的挑战，其未来的研究方向主要包括以下几个方面：
(1)隐私保护参数的设置与优化
位置隐私保护技术在理论上都是基于一些隐私保护模型，例如k-anonymity[19]、l-diversity[60]、t-closeness[27]、m-invariance[61]、p-confidentiality[62]、ε-DP[43]等，其隐私保护水平都是由相应的隐私保护参数来调节的。如何通过对这些参数的设置来达到隐私保护水平和服务水平的最佳平衡，即如何寻求隐私保护参数的最优解，是一个需要继续研究的问题，它可能涉及到对用户的调查、对行为和心理的评估，以及对现实环境的分析等。
Table1.Comparisonbetweenlocationprivacypreservingtechniques
(2)个性化的位置隐私保护方案
在现实当中，对隐私保护的需求往往因用户或地域的不同而有很大的区别。但目前的位置隐私保护方案大多并没有考虑这些多样化的需求，隐私保护系统往往工作在某种统一的设置下。虽然有些研究已经意识到这个问题并提出了相应的解决方法[63][64]，但这些方法大多工作在特定的环境下，还不具备一般通用性。设计细粒度的、支持不同层次的隐私水平的个性化隐私保护方案是未来的一个研究方向[65]。
(3)社交网络中的位置隐私保护
社交网络的风靡对隐私保护提出了新的挑战[66]。在移动互联网中，位置数据与图片、文字、音频数据结合在一起，一般的结构化数据转变为非结构化数据，同时，采用实名认证的移动社交网络将个人身份信息与位置信息进行了绑定，社交网络中与用户之间的互动则导致隐私暴露的范围扩大。传统的隐私保护方法并不能适应这些新的变化，研究社交网络的位置隐私保护方法是未来的一个重要的研究方向。
5.结束语
基金项目
国家自然科学基金项目(61304067)；湖北省自然科学基金项目(2014CFB354)；中央高校基本科研业务费专项资金(31541511301)。