基于位置服务的隐私保护综述

魏兴民 杜鹏懿

摘  要：随着社会的发展，技术快速进步，高精度的定位设备使得我们能够使用多种不同类型的基于位置服务（LBS）。这些设备获得的位置信息包括十分隐私的个人信息，所以隐私保护成了现在基于位置服务最重要的问题之一。本文总结了三种基于位置服务的隐私保护方法，包括使用仿真品的匿名通信技术，使用人造的仿真品位置信息，让服务提供者不能区分哪一个是真实的用户信息。点对点的空间隐形方法，用户使用自己的对等体作为代理，这些对等体将用户的查询消息转发给服务提供者，实现了空间隐形。空间和时间隐藏方法，是通过权衡空间分辨率和时间分辨率，来满足指定的匿名性要求。最后提出了自己的一些创新的研究思路和解决方案。

关键词：隐私保护;基于位置服务;匿名;点对点;空间隐藏;时间隐藏

中图分类号：TP309       文献标识码：A 文章编号：2096-4706（2019）08-0154-04

Abstract：With the development of society，technology advances rapidly，highly accurate positioning devices enable us to entertain many different types of location-based services （LBS）. But location information obtained by these devices includes deeply personal information. Therefore，the protection of privacy has been one of the most significant issues of location-based services. This paper reviews three privacy protection methods for location-based services（LBS），including anonymous communication technique using dummies，this method use dummies together with real user information，so the service provider can’t distinguish which one is the real user information. Peer-to-Peer （P2P） spatial cloaking algorithm，in which user’s peers act as agents，they forward user’s queries to service provider，thus this method achieves spatial cloaking. Spatial and temporal cloaking method，in which spatial resolution and temporal resolution is traded off to meet specify anonymity requirement. Finally，this paper proposed some innovative research ideas and solutions.

Keywords：privacy protection;LBS;anonymity;P2P;spatial cloaking;temporal cloaking

0  引  言

近年来，计算机网络和通信技术的飞速进步使得移动互联网得到了迅速发展，随之而来的位置服务使人们的生产和生活方式发生了很大变化。位置数据被用于各种不同类型的基于位置服务（LBS），如随时都可网上预约滴滴出租车等。利用位置服务，用户可先把真实位置信息提供给服务提供者，再从服务提供者那里获取服务。发送数据之后用户不能删除或者修改已经发送的信息，即用户不能防止服务提供者根据存储的真实位置数据分析用户的运动模式。针对位置服务出现的隐私泄露问题，必须采取措施进行隐私保护。本文对以往的一些基于位置服务的隐私保护方法进行总结，然后提出自己的创新研究思路与解决方案。

1  基于位置服务（LBS）的位置隐私

A.Beresford和F.Stajano将位置隐私定义为防止其他团体根据某个人现在或者过去的位置进行学习的能力[1]，且认为一个系统能够获得位置数据侵犯了个人隐私。

在基于位置服务中，用户发送的信息至少由用户ID和用户真实位置信息组成。本文假设用户的ID不与用户的隐私信息相连接，可使用假名。尽管用户的ID是隐藏的，仍可能通过位置数据侵犯用户隐私。如某人每天在固定时间都会一个地方，如果这样的位置数据被累积起来被分析，那么便可推知此人的住址。為保护位置隐私，需匿名化位置数据。其匿名性的程度需考虑以下方面：

（1）普遍性。指对象存在于整个区域中。当所有的用户居住在相同的区域中，普遍性意味着对象存在于整个区域中，服务提供者可以指定用户。另一方面，当用户居住在不同的区域中，服务提供者指定用户很困难。因此，普遍性增强了整个区域中用户的位置匿名性。

（2）拥挤性。指大量的对象存在于一个区域中，这源自M.Gruteser和D.Grunwald提出的k-anonymous[2]。用户在一个区域中发送位置信息给服务提供者。当许多用户生活在这个区域中，服务提供者很难指定某一个用户。这样就增强了一个区域中用户的位置匿名性。普遍性保证了每个用户的位置匿名性，但拥挤性只保证了局部用户的位置匿名性。

2  使用仿真品的匿名通信技术

M.Gruteser和D.Grunwald提出匿名使用基于位置服务[2]，用户发送的位置数据，精度被减少，然后被发送给服务提供者，如图1所示，位置数据的精度用灰色区域表示，服务提供者只能学习到用户位置的模糊的细节，这就增强了位置匿名性。但问题是通过追踪几分钟的数据，观察者能够很容易地理解用户的移动。因为位置数据创造出了一个粗略的轨迹。（b）用户产生两个与（a）不同的仿真品，它们能与真实的位置数据向不同的方向移动，因为其他用户同时发送位置数据，用户更加安全。

（a）准确率缩减

（b）虚拟生成

2.1  基本过程

为解决可追踪问题，这篇文章提出了一个新的基于位置服务匿名通信技术，用户发送包含噪声的位置数据给服务提供者。噪声包括一组被称作“仿真品”的假的位置数据[3]。如图2所示，服务的过程如下：

（1）一个基于位置服务（LBS）用户从GPS设备获得自己的位置信息r。

（2）仿真品在位置1和位置2处产生。

（3）用户创造一个服务请求消息S，包括位置数据r、1和2，发送S给服务提供者。

（4）服务提供者创造一个服务应答消息R，R应答接收到的所有位置数据，并且把R发送给用户。

（5）用户接收R，并且只从R中抽取出必要的数据。用户知道真实的位置数据，但服务提供者不知道。所以服务提供者不能从接收到的一组位置数据中识别出用户真实的位置数据。这样匿名服务就完成了。

2.2  仿真品生成算法

仿真品生成算法的主要目的是使观察者不能区别真实位置数据和仿真品。一般而言，每个对象在固定时间内的移动是有限的。如果随机产生仿真品，那么很容易发现真实位置数据和仿真品之间的区别，因为使用基于位置服务（LBS）需要位置数据是连续的。仿真品不能表现得和真实的位置数据完全不同。本文提出两种不同的仿真品生成算法，来防止服务提供者发现真实的位置数据。

在领域内移动（MN）：如图3（a）所示，仿真品的下一个位置是由仿真品的当前位置的邻域决定的。用户的通信设备记住每个仿真品之前的位置，然后设备根据仿真品之前的位置产生新的仿真品位置。

在有限领域内移动（MLN）：如图3（b）所示，仿真品的下一个位置也是由仿真品当前的位置决定的。但是下一个位置也被当前区域的密度所限制。这个算法是自适应的，首先，用户的通信设备获得其他用户的位置数据。然后，设备根据记忆产生仿真品，这和MN算法一样。接着，如果有很多用户在生成的小区域中，设备再一次产生仿真品。这个过程重复很多次。

3  点对点（P2P）空间隐形算法

3.1  算法概述

C.Y.Chow等人提出了用于匿名的基于位置服务（LBS）的空间隐形算法[4]，主要解决目前基于位置服务（LBS）的隐私问题，用户向服务提供者报告他们真实的位置信息来获得想要的服务。本文提出了点对点（P2P）空间隐形算法，主要思想是在查询任何基于位置服务前，移动用户先使用单跳通信或多跳路由和他的对等点形成一个组。然后空间隐形区域被计算为覆盖整个组用户的区域。提出的P2P空间隐形算法支持按需模式和主动模式两种类型的操作。实验表明，使用按需模式操作比使用主动模式操作具有更低的通信开销和更好的服务质量，但按需模式需要更长的响应时间。

3.2  算法介绍

在基于位置服务（LBS）中，用户需要把他的真实位置数据发送给服务器。假如服务器不可靠，用户的位置隐私将被侵犯。目前已经有不少方法被提出来[5-7]解决此问题。一个可信的第三方被用作中间件，来把用户的位置模糊化到一个空间区域中，以获得k匿名性，即一个用户不能从另外k-1个用户中区别开来。这样的集中式隐私保护策略有两个缺点：

（1）集中式的第三方可能成为系统的瓶颈或者单点故障。

（2）集中式的第三方具有位置信息的全部知识和所有的用户查询，可能因第三方入侵引入严重的隐私威胁。

本文提出点对点的（P2P）的空间隐形算法，移动用户采用点对点空间隐形算法能够保护他们的隐私，而不用寻求集中式的第三方的帮助。除了集中式方法的缺点，这个算法还有以下事实：

（1）大部分移动设备的计算能力和存储容量都以很快的速度增长。

（2）P2P通信协议，比如IEEE 802.11和蓝牙已经被广泛部署。

（3）许多基于P2P信息共享的新应用已经快速成型，比如合作信息访问[8，9]和P2P空间时间查询处理[10，11]。

文章提出的P2P空间隐形算法能够以按需模式和主动模式操作。在按需模式中，当移动客户端需要从基于位置的数据库服务器那里获得信息时，就执行隐形算法。另一方面，在主动模式中，移动客户端定期在周围寻找，以发现预期数量的对等体。因此，在任何时候移动客户端想要从基于位置的数据库服务器那里检索信息时，都能够把真实位置隐藏到空间区域中。文章的主要贡献为：

（1）引入了一个分布式系统架构来为移动用户提供匿名的基于位置的服务。

（2）提出了第一个空间隐形算法来为移动用户享受高质量的基于位置的服务，而不使他们的隐私受到威胁。

（3）提供了實验证据来说明提出的算法在响应时间方面的有效性，它对大规模移动客户也具有伸缩性，并且是有效的，它能为移动客户提供高质量的服务而不需要真实的位置信息。

4  通过空间和时间隐藏来匿名使用基于位置服务（LBS）

4.1  算法概述

匿名能够提供很高程度的隐私，使得使用服务的用户不需要处理服务提供者的隐私策略，并且减少了服务提供者保护隐私信息的需要。然而，确保匿名使用基于位置服务，需要用户传输的精确位置信息不能被很容易地用来重新识别对象。这篇文章提出了一个中间件架构和算法，它们能够被集中式的位置代理服务使用。这个自适应的方法沿着空间和时间维度调整位置信息的分辨率，来满足规定的匿名性限制，基于给定的区域中可能使用位置服务的实体。

4.2  算法介绍

M.Gruteser和D.Grunwald提出通过空间和时间隐藏来匿名使用基于位置服务[2]，研究了一种专注于最小化收集原理的方法。在这个方法中，基于位置的服务只收集和使用去个性化的数据，即匿名数据[12]，并承诺对两方都有利。对服务提供者而言，匿名数据会产生更少的开销。它可以不经用户同意，被收集，处理，然后分发给第三方。

实际的匿名需要对象不能从位置数据中被重新鉴别。如一个发送给地图服务的消息，它由网络地址，用户ID和用户当前位置的坐标组成。用户ID和网络地址是重新鉴别首先考虑要用的信息。对于匿名服务使用，用户的ID可以被省略。网络地址问题可以被Crowds[13]或者Onion Routing[14]这样的机制解决，它提供了发送者匿名性。如果位置信息被记录下来并且连续地分布，这个隐私问题便增大了。LBS中的匿名性必须在网络中的多个协议栈层次得到解决，这取决于怎样的实体可以被信任。这篇文章在应用层解决匿名性问题，通过让服务提供者访问匿名位置数据，即位置信息被充分改变来防止重新鉴别。文章的主要贡献是：

（1）一个位置匿名性正式的度量。

（2）一个自适应的基于四叉树的算法，它能够降低位置信息的空间分辨率来满足一个指定的匿名性限制。

（3）一個算法，它能够通过降低时间分辨率来提高空间分辨率，以满足同样的匿名性限制。

（4）一个评价这些算法预期分辨率的方法，它是基于交通模型，交通模型由地图材料和汽车交通计数组成。

5  研究思路与解决方案

解决基于位置服务（LBS）的隐私问题时，位置匿名很重要。一个观察者可以根据对象的位置信息在一个连续时间内的变化，描述出对象的移动轨迹。但想要描述就需要对象在一段时间内的某个标识不发生变化。否则，观察者只能得到一些孤立的点，并不能辨认哪一个位置信息是属于哪一个对象的。基于此，我觉得在解决LBS时，可使用完全隐藏用户标识的方法，这里的标识包括用户ID，网络地址等各个方面。隐藏用户的ID很简单，可以在每次向服务提供者发送查询时，不发送用户ID，只发送网络地址。要隐藏网络地址，可以使用一些代理，用户把带有网络地址的请求包发送给代理，由代理向服务提供者发送查询。代理接收到服务提供者的响应消息后再转发给用户，这样用户的网络地址对服务提供者而言就隐藏了，但是这个过程需要代理是可信的。

6  结  论

基于位置服务（LBS）的广泛使用也带了很多隐私问题。对于LBS中的位置隐私保护问题，国内外已有大量文献进行了深入研究，本文总结了基于位置服务隐私保护的方法，包括使用仿真品的匿名通信技术，点对点的空间隐形方法以及空间和时间隐藏方法。但诸如如何解决对等点之间的信任问题、如何解决云计算、大数据时代位置隐私保护问题亦需纳入后续的研究之中。

参考文献：

[1] BERESFORD AR，STAJANO F.Location privacy in pervasive computing [J].IEEE Pervasive Computing，2003，2（1）：46-55.

[2] Gruteser，M. and Grunwald，D.Anonymous Usage of Loca-tion-Based Services through Spatial and Temporal Cloaking [C]//Proceedings of the 1st International Conference on Mobile Systems，Applications and Services，San Francisco，2003.

[3] Kido H，Yanagisawa Y，Satoh T. Protection of Location Privacy using Dummies for Location-based Services [C]//International Conference on Data Engineering Workshops. IEEE Computer Society，2005.

[4] Chow C Y，Mokbel M F，Liu X. A peer-to-peer spatial cloaking algorithm for anonymous location-based service [C]//Acm International Symposium on Advances in Geographic Information Systems.ACM，2006.

[5] B.Gedik and L.Liu.A customizable k-anonymity model for protecting location privacy [C]//In Proc.IEEE ICDCS，2005.

[6] M. Gruteser and D. Grunwald. Anonymous Usage of Location-Based Services Through Spatial and Temporal Cloaking [C]//ACM International Conference on Mobile Systems，Applications and Services，2003.

[7] Chi-Yin Chow，Mohamed F. Mokbel，Walid G. Aref. Casper*：Query processing for location services without compromising privacy [J].ACM Trans. Database Syst.，2009，34.

[8] Chow C Y，Hong V L，Chan A T S. Distributed group-based cooperative caching in a mobile broadcast environment [C]//International Conference on Mobile Data Management，2005.

[9] Papadopouli M，Schulzrinne H. Effects of power conservation，wireless coverage and cooperation on data dissemination among mobile devices. In [C]//John Wiley & Sons，Ltd.，2001.

[10] Huang Z，Christian Søndergaard Jensen，Lu H，et al. Skyline Queries Against Mobile Lightweight Devices in MANETs [J].Icde，2006：66.

[11] Ku W S，Zimmermann R，Wang H，et al. ANNATTO：Adaptive Nearest Neighbor Queries in Travel Time Networks [C]//International Conference on Mobile Data Management. IEEE，2005.

[12] Pfitzmann A，Marit Köhntopp. Anonymity，Unobservability，and Pseudonymity — A Proposal for Terminology [J].2001.

[13] Reiter M K，Rubin A D. Crowds：anonymity for Web transactions [J].ACM Transactions on Information and System Security，1998，1（1）：66-92.

[14] GOLDSCHLAG D，REED M，SYVERSON P，et al.Onion routing for anonymous and private internet connections [J].Communications of the ACM，1999，42（2）：39-47.

作者簡介：魏兴民（1984.02-），男，汉族，宁夏固原人，研究生，工程师，研究方向：信息安全。