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