基于预测位置的移动用户位置隐私保护研究

李晓会+余建桥

摘要：近年来，位置隐私保护技术成为学术界研究的热点。文章提出一种基于预测位置的位置隐私保护方案。该方案当用户运行速度较高时采用预测位置作为用户查询的位置信息，以解决高速运动时由于查询时间引起的查询结果与需求结果不符的问题。实验表明，预测位置模型适用于用户运动速度不同的情况，抗攻击能力更强，服务质量更好。

关键词：预测位置；位置隐私；基于位置的服务；k-匿名；移动用户

中图分类号：TP301 文献标识码：A 章编号：1009-3044（2016）25-0022-04

Abstract： The location privacy protection technology has aroused general interest in recent years. This paper puts forward a location privacy protection scheme that bases on users predicted location. When a user is in high-speed operation， it takes the predicted location as the user current location， so as to solving the problem of inconsistent between the provided information and the demanded information， which is resulted from the different query time. The experiments show that the predicted location model is suitable for the situations with different users speed. At the same time， it has higher anti-attack capability and better service quality.

Key words： predicted location； location privacy； location-based services； K-anonymity； mobile users

1 概述

随着具有GPS定位的移动设备的普及与发展，使得基于位置的服务[1]（Location Based Service， LBS）得到很大发展。LBS需要用户发送位置信息给LBS服务提供商来获得各种服务[2，3]。移动用户查询中由于位置频繁变换，使LBS不间断追踪用户当前位置，导致用户位置信息越来越多地暴露给LBS服务提供商。如果攻击者得到这些位置信息，会推断出用户敏感信息，造成用户隐私泄露，因此提供LBS服务时保护用户的位置隐私至关重要。

为了解决位置隐私保护问题，许多位置匿名方法已经被提出[4-6]. 这些方法分为基于可信匿名服务器[5，7-11]和基于移动设备[12]的两种结构。目前使用比较多的是基于可信匿名服务器结构。匿名服务器将用户发送的确切位置泛化为匿名区域，使攻击者不能确定用户真实位置来保护用户位置隐私。然而这些方法大多根据用户发出查询时位置构造匿名区域，没有考虑移动用户的运动性引起的位置变动，造成服务器返回结果偏离用户实际需求。

在假设用户不处于路口区域且运动速度超过设定值情况下，使用用户经过平均响应时间预测到达的位置作为用户位置信息来构造匿名区域，最大程度降低由查询响应时间引起的位置变动。

2 位置匿名系统结构

2.1 位置匿名

近年来，针对LBS用户的位置隐私保护，已经有许多位置匿名技术被提出[4]。其中最常用的是空间隐匿[4，6，8-10]和假位置[13]技术。空间隐匿技术大多使用位置k-匿名模型，该模型由Gruteser M[4]等人首次提出。其基本思想是当用户提出位置服务请求时，将用户的精确位置替换成一个覆盖其他k-1个用户的空间区域，使服务请求用户不能与其他k-1个用户区分开来。由于该文献k值是系统设定不符合位置隐私个性化需求及没有考虑位置k-匿名带来的中心攻击问题，所以文献[5]，[6]分别提出可自行定制的k-匿名模型和使用尽可能小的网格构建尽可能小的匿名空间区域模型。但文献[6]没有考虑用户的移动性，文献[5]也仅适用于用户移动速度较慢的情况。为此，文献[7]在文献[5]的基础上提出一种基于V-grid模型的位置隐私保护方法。文献[8]针对文献[6]提出一种随机匿名的位置隐私保护方法。

但以上文献大多采用用户查询时所在位置构造匿名区域，未考虑用户的移动性给位置隐私带来的影响.文献[7]虽然引入用户的移动速度，但选用的与前一次更新位置的差值时间不符合移动用户真实查询响应时间。移动用户高速运动时具有短时间行驶长位移特点，使现有位置匿名方法存在由查询响应时间引起查询结果与需求结果不符问题，需要选用更符合移动用户运动规律的位置来构造匿名区域。

2.2 位置匿名系统结构

由于基于移动设备的两层结构需要客户端具备较高性能，因此目前位置匿名中使用比较多的是三层中心服务器结构。三层中心服务器结构包括移动客户端（mobile client， MC）、位置匿名服务器（location anonymous server， LAs）、LBS服务器（LBS server， LBSs）三部分，如图1所示。MC与LAs之间的通信经过加密认证，对攻击者来说是完全保密的；LAs与LBSs之间的通信是半可信的，攻击者可能窃听、截取通信信息[8]。

3 基于预测位置的位置隐私保护模型

3.1 系统结构

不同的位置隐私保护技术需要不同的系统结构，目前位置k-匿名技术多采用中心服务器结构，另外考虑到移动用户与LBS服务器之间的通信带宽非常有限，传输大的结果集时需要花费较高的响应时间，不能满足LBS的实时性。因此采用三层中心服务器结构。

3.2 基于预测位置模型

预测位置模型（PLM）中LAs维护一份存储用户基本信息的用户信息表，每个用户对应表中一条记录，当用户首次连接LAs时，LAs为用户新建一条记录。LAs同时存储空间区域内各路口位置信息，用IS表示路口的集合，，li表示第i个路口位置。由于用户行至路口时速度可能都会有较大变化，不适于根据速度来计算预测位置，因此我们将路口位置li处理为半径内的圆形区域CR，路口区域，在IR中采用用户真实位置作为其位置信息。

为了计算方便，首先将空间区域划分成大小相等的网格，Gi，j表示i行j列的网格，某一网格或几个相邻网格的面积构成网格区域（grid region， GR），与网格区域相邻的网格的集合构建相邻网格集（grid set， GS）。如下图图2所示，若当前用户所在网格为G3，3，则 GR={G3，3}， GS={G2，3， G3，2， G3，4， G4，3}。若 G4，3 与 G3，3合并，那么GR={G3，3， G4，3}， GS={G2，3， G3，2， G3，4， G4，2， G4，4， G5，3}。

3.3 相关定义

定义1平均响应时间T。用户的查询响应时间是用户发出查询请求到接收到服务器响应之间的时间，用表示。，其中t1表示LAs对用户位置进行匿名时间，t2表示LBSs查询得出RCS的时间，t3表示LAs对RCS进行筛选结果的时间，表示三方的通信时间。平均响应时间为用户之前查询时间的平均值，用T表示，。当移动用户向LAs发送查询请求信息时会将此前统计的平均响应时间T一起打包发送给LAs。

定义 2真实位置&预测位置。真实位置是t时用户当前所在位置，用表示；预测位置是指LAs根据用户当前速度预测经过平均响应时间T后到达的位置，用表示。预测位置的计算公式可表示为：

（1）式中v表示用户当前移动速度，T为用户发送的平均响应时间。

定义 3位置信息。位置信息是LAs存储的用户位置，用LI表示。LAs对用户位置进行位置匿名时，根据服务器存储的用户位置信息构造匿名区域。首先LAs将用户发来的真实位置进行存储，其次判断用户是否在路口及是否超过设定速度值决定用户预测位置的计算与存储，最后根据存储的位置信息表中预测位置是否为空判断取真实位置亦或预测位置作为用户位置信息。

定义 4位置信息可靠度。位置信息可靠度是位置信息距离用户收到服务器响应时所在位置的远近程度，以R表示，公式如下：

其中p为系统设定的距离收到服务器响应时所在位置的半径长度，根据城市环境和公路环境的不同取值不同。px为查询时预测的位置距离服务器响应时真实所在位置的距离长度。对R的计算根据px值不同分两种情况：当时将R设为0，当时按公式计算，R值越大表示位置信息可靠度越高，其中px值可用两点间欧氏距离表示。

4 基于预测位置的位置匿名保护算法

4.1 位置匿名保护算法

在使用预测位置模型（PLM）后，用户的匿名区域搜索算法为：

4.2 抗攻击性能分析

假设有一个请求LBS的移动用户u，经过位置匿名后匿名区域内用户为{u，u1，u2，……，uk-1}，则攻击者猜测该请求为真实用户u请求的概率为1/k。

采用基于预测位置模型（PLM）算法后，由于攻击者猜测的位置也有可能为用户的预测位置，所以攻击者猜测出用户u的真实位置的概率为1/（2k），小于没有采用基于预测位置模型算法时的概率，因此可以说采用基于预测位置模型算法后对抵抗攻击者攻击有明显效果。

攻击者可以利用各种信息获得匿名区域及区域内用户数，对以往的若攻击者知晓某一区域内只有一个用户，则可判断该请求为用户所发，在PLM模型中却不能。因为该区域有可能是根据区域外某用户的预测位置构造的，真实的提出请求用户并未在匿名区域内，加大攻击者攻击难度。

5 实验结果与分析

5.1 实验环境及参数

实验环境为Windows 7操作系统，处理器为intel i5-3470，主频为3.2GHz，内存空间为4G。实验使用Thomas Brinkhoff [14]开发的基于网络的移动对象生成器随机生成移动结点作为评估对象，模拟它们在德国古登堡市地图上的行驶。

在实验模型中，选定15*15km2作为实验区域，并将其划分为50*50的网格形状，路网移动对象生成器生成随机分布的5000个移动用户，并从这些移动对象中随机产生500个查询请求用户。实验中令匿名值k改变，而其他参数取默认值并且保持不变，分别对速度为10m/s和20m/s的用户进行实验。实验参数的范围及默认值如表2所示。

5.2 结果分析

通过实现PLM模型算法及文献[7]中V-grid模型算法的空间匿名，比较两种模型隐私算法的位置信息可靠度、匿名成功率来查看PLM模型算法的有效性。

图3为移动用户不同行驶速度下的位置信息可靠度。当用户低速v=10m/s行驶时，PLM算法与V-grid算法都采用用户的当前位置构造匿名区域，因此位置信息可靠度相差不大。从图3（b）看到RLM模型算法相比V-grid模型有更高的位置信息可靠度。这是因为匿名值k越大，一般而言需构造的匿名区域也越大，查询响应时间也更长。当用户以高速v=20m/s行驶时，由于V-grid算法根据当前时间与最近一次更新位置时间差值计算用户位置，因此时间上会与真实查询响应时间有偏差。而PLM中用户设定匿名值k后平均查询响应时间与真实查询响应时间偏差不大，因此PLM的位置信息可靠度要高于V-grid算法。

通过对比可以知道，在用户运行速度较快的情况下，预测位置模型可以产生很好的隐私保护效果。而当用户速度不高时，PLM模型算法与V-grid模型算法性能相差不大。

图4为不同速度情况下随着匿名值k的增长匿名成功率的变化。一方面从（a）（b）两图看到，随着匿名值的增大，两种算法的匿名成功率都呈下降趋势。这是因为当匿名值k增大，匿名服务器需要寻找更多的用户构建匿名区域，而有时区域内或许没有足够多的请求用户，从而导致匿名成功率下降。另一方面通过观察（a）（b）两图，PLM算法相比V-grid算法匿名成功率相对更高。这是因为PLM采用的平均响应时间比V-grid采用的与上一次更新时间的差值更接近真实查询时间，但由于同样存在偏差，因此两算法匿名成功率相比效果不是很明显。

6 结束语

位置隐私保护的研究对于基于位置的服务的广泛应用有着十分重要的意义。针对高速运动的用户提出一种基于预测位置的位置隐私保护方法，以保护用户的查询质量。理论仿真证明，在隐私保护度较高的条件下，PLM算法与V-grid方法相比，在位置信息可靠度和匿名成功率上都有一定优势，因此在用户运动速度较高的情况下，基于预测位置的位置隐私保护方法具有较好的隐私保护性能。

参考文献：

[1] 周傲英， 杨彬， 金澈清，等. 基于位置的服务：架构与进展[J]. 计算机学报， 2011，24（7）：1155-1171.

[2] Krumm J. A survey of computational location privacy[J]. Personal & Ubiquitous Computing， 2009， 13（6）： 391-399.

[3] Jiao X， Yu L X， Yang X C， et al. A Location Privacy Preserving Approach on Road Network[J]. Chinese Journal of Computers， 2011， 34（5）：865-878.

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

[5] Mokbel M F， Chow C Y， Aref W G. The new Casper： query processing for location services without compromising privacy[C]// International Conference on Very Large Data Bases. VLDB Endowment， 2006： 763-774.

[6] Kalnis P， Ghinita G， Mouratidis K， et al. Preventing Location-Based Identity Inference in Anonymous Spatial Queries[J]. Knowledge & Data Engineering IEEE Transactions on， 2007， 19（12）： 1719-1733.

[7] 司超， 徐红云. 基于V-grid模型的位置隐私保护方法[J]. 计算机工程， 2012， 38（12）： 276-278.

[8] Yang S， Ma C. Random anonymity method for location privacy protection[J]. Harbin Gongcheng Daxue Xuebao/journal of Harbin Engineering University， 2015， 36（3）： 374-378.

[9] Song D， Sim J， Park K， et al. A privacy-preserving continuous location monitoring system for location-based services[J]. International Journal of Distributed Sensor Networks， 2015， 11（2）： 1-10.

[10] Kim Y K， Hossain A， Hossain A A， et al. Hilbert-order based spatial cloaking algorithm in road network[J]. Concurrency & Computation Practice & Experience， 2013， 25（1）： 143–158.

[11] Cao W， Lv X U， Liu Y B， et al. The LBS system based on polygonal cloaking region[J]. 2015.

[12] Jung K， Jo S， Park S. A game theoretic approach for collaborative caching techniques in privacy preserving location-based services[C]// International Conference on Big Data & Smart Computing. IEEE， 2015： 59-62.

[13] Niu B， Li Q， Zhu X， et al. Enhancing privacy through caching in location-based services[C]// Computer Communications. IEEE， 2015： 1017-1025.

[14] Brinkhoff T. A Framework for Generating Network-Based Moving Objects[J]. Geoinformatica， 2002， 6（2）： 153-180.