基于网格偏移的分散位置隐私保护方法

徐俊仪

（广东工业大学计算机学院，广州 510006）

0 引言

随着移动通信技术的快速发展，用户能够通过移动设备精确定位所在的位置，基于位置的服务（LBS，Location-Based Service）将移动通信设备的位置和其他信息整合起来，为用户提供增值服务[1]。用户获得位置服务的过程[2]，将自身的位置信息泄露给了LBSs，或者攻击者在这个过程中截获用户的请求获取相应的信息[3]。

目前针对位置服务的隐私保护方法主要有2种结构：分布式点对点结构和第三方匿名服务器结构[4]。分布式点对点结构是用户之间进行协作，在用户端实现位置隐匿，将隐匿请求信息发送给LBSs获取服务；第三方匿名服务器结构是在用户和LBSs之间添加一个匿名服务器（AS，Anonymous Server），用户只需要将请求信息发送给AS，AS负责对用户的请求进行匿名处理，AS向LBSs获取信息后，筛选符合用户需求的内容，发送给用户[5]。

根据隐私保护方案技术的不同，主要分为群体协作技术[6-9]、空间匿名技术[10-11]、位置偏移和模糊技术[12-13]，以及基于密码学技术[14-17]的隐私保护方案。模糊技术和位置偏移的方法比较简单，具有较好的服务质量，安全性比较低；密码学技术能够保证较高的安全性，但是需要有比较强大的计算处理能力；群体协作技术对区域的人群和网络有一定的要求。

当需要使用第三方匿名服务器的时候，现有的多是采用密码学工具来确保用户请求的安全性，使得LBSs和AS难以获得用户的个人身份信息和查询信息。但是加密操作存在比较大的计算量，查询请求的过程比较长，容易导致用户服务质量下降，如响应时间的延长。其次，现有的AS对用户的请求进行的k匿名，是在请求位置的附近搜索k-1个位置，k个位置满足l-多样性，在人群稀少的地图区域，需要搜索较大的范围才能确定匿名区域或者直接匿名失败，因为需要满足k匿名的要求。因此本文提出一种基于网格偏移的分散位置隐私保护方法，使LBSs和AS难以获得用户的确切信息，并且在进行查询请求的时候有较低的时间开销。为了有较高的位置分散度，在AS进行匿名的时候，根据历史查询数据，选取查询内容不一样的k-1个网格位置，并且保证选择的位置尽量偏移匿名集合中的位置，将构成匿名集合发送给LBSs进行查询。

1 系统结构

本文所提方法的系统结构如图1所示，包含了四个部分，分别是用户user，匿名服务器AS，功能服务器（Function Server，FS）和位置服务器 LBSs。

User是具备定位功能的移动设备的用户，能够通过GPS获取user所在的位置loc，user以loc为基础，构造一个矩形区域，计算偏移网格区域后将请求信息发送给AS。user向FS获取周期更新的基础网格Grid，Grid 可以表示为{（x0，y0）,r,TIME}，（x0,y0）表示了Grid的起始真实坐标，r表示单个网格的宽度，TIME是Grid的标识。

图1基于不可信匿名服务器的系统结构

AS是第三方匿名服务器，其收集和保存了用户的请求信息，对于用户的请求，负责在历史查询数据中搜索符合条件的请求信息构造k匿名集合发送给LBSs，同时也负责对LBSs返回的数据进行筛选。在本方法中，AS不可信。

FS的作用是周期更新基础网格Grid的信息，对于User和LBSs获取Grid的请求，获取身份信息，响应基础网格信息Grid。

LBSs是一个大型的位置服务器，记录了兴趣点（Point Of Interest，POI）信息，负责对请求信息进行响应，将搜索的结果信息发送给AS进行筛选。

2 方法的原理

本文方法包括了四个过程：user网格化处理、AS匿名处理、LBSs查询结果、筛选结果。以下就每个过程进行详细说明。

2.1 User网格化处理

User设定进行查询请求的参数，包括最小匿名区域MIN_AREA，查询内容类型type，隐私保护度k，查询半径radius。隐私保护度k指示了AS进行匿名操作的时候总共需要k个查询内容不同的位置点，type说明了查询的类型，MIN_AREA规定了user需要生成的矩形区域面积应不小于该值，radius表明了以查询位置点为中心进行搜索的范围大小。

user向FS发送消息获取基础网格信息Grid。user通过移动设备获得自身准确的位置loc，随机生成一个值范围为 0～1的数b，将 loc向随机方向偏移 sqrt（MIN_AREA）*b 得到位置 loc’，根据 loc’生成矩形区域Rect=（{x1,y1）（,x2,y2）}，（x1,y1）表示了矩形区域左下角的坐标，（x2,y2）表示了矩形区域右上角的坐标。

根据基础网格Grid，位置（xi,y）i计算偏移网格坐标（ci,r）i如公式（1）所示，其中r为基础网格中的单个网格宽度。Rect根据公式（1）计算得到偏移网格坐标Rect'，Rect'={（c1,r1）（,c2,r2）}。

将Rect'，用户隐私保护度k，用户请求类型type以及匿名化id，基础网格标识TIME和查询半径radius组成消息Mu_as发送给AS进行匿名处理，Mu_as={id,Rect',type,k,TIME,radius}。

2.2 AS匿名处理

AS对收到的Mu_as消息提取偏移网格坐标Rect'，隐私保护度k，用户类型type，根据Rect'计算请求的中心坐标（cu,ru），将[（cu,ru）,typeu]添加到γ，γ表示匿名后的位置集合。

在历史数据库中搜索与type不同的k-1个请求类型typei，0

任意一个n边形都可以划分为n-2个三角形，多边形的面积通过计算每个三角形的面积求和来获得，三角形的面积s根据公式（2）求得，p是三角形的半周长，a,b,c分别是三角形的三条边。

对typei（0

经过计算可以得到k-1个请求类型不同的最分散的网格坐标（ci,ri）,0

构造 Mas_sp消息，Mas_sp={γ，TIME}，发送给 LBSs进行查询。

2.3 LBSs查询结果

LBSs收到消息Mas_sp后，根据TIME向FS发送请求，获取基础网格信息Grid，将γ中每个typei的网格坐标（ci，ri）还原为真实坐标。

根据每个坐标（xi，yi）和typei以及查询半径检索s个POI结果，POIi={（xj,yj）,infoj}，0<=j

2.4 筛选结果

AS接收到Msp_as消息后，在历史请求列表中找到请求用户user所请求的类型typeu，将该类型的查询结果网格集βu发送给 user，Mas_u={βu}。

User从Mas_u中提取POI的信息，根据基础网格Grid，对偏移网格坐标（ci,ri）根据公式（4）转换为真实坐标（xi,yi），由于提交给AS的是偏移后的位置坐标，因此存在部分的POI是不符合user需求的，因此需要根据用户的所在的位置（xu,yu）计算（xi,yi）距离用户的远近，将不在radius范围的POI舍弃，将符合的POI结合相关info展示给user。

3 安全性和实验结果分析

3.1 安全性分析

本文假设LBSs和AS会提供正常的服务响应用户的请求并且具备良好的对外安全性，但是会收集用户的查询请求，试图通过数据挖掘的方法探索用户的隐私信息。

对于AS而言，其能够获取的是用户的id和网格偏移信息Rect’={（c1,r1）,（c2,r2）}，根据该网格信息，AS难以直接得知用户的位置信息，只知道用户id的请求内容以及相对基础网格的网格坐标。如果AS恶意获取了基础网格Grid，由于user对位置进行了偏移，并且发送给AS的是矩形区域，user可以在任何一个网格位置内，因此AS能够识别用户所在位置的概率为，当基础网格划分得越细，也即是r越小，用户端的生成匿名区域相比MIN_AREA够大，那么攻击者需要更高的成本来识别用户的准确位置。

对于LBSs而言，由于AS对用户id进行了变换，其难以知道用户的身份信息。由于请求信息经过了AS的匿名处理，LBSs能够确定用户的请求内容的概率为1/k。经过了user的匿名区域生成和AS的匿名处理，LBSs识别用户位置的概率为，当k增大，能够识别用户位置的概率会逐渐变小，保护用户的隐私信息。

3.2 实验环境

本文实验使用Thomas Brinkhoff的移动对象生成器（Network-based Generator of Moving Object）[18-19]，以城市Oldenburg生成随机移动对象，本文所提的方法和OPEG方法[14]以及ELPP[16]方法就时间开销、网络通信开销和匿名位置分散度进行实验比较。

本文方法使用Java语言实现，运行在Windows 10操作系统上，CPU为Intel Core i7-7700。内存为8G，默认参数值如表1所示。

表1实验默认参数

城市Oldenburg包含6105个节点，7035条边，长为23572，宽为26915。在该区域内生随机生成7326个POI位置。基于该区域生成3200个随机位置，每个位置模拟请求位置服务。

3.3 实验结果与分析

（1）时间消耗

实验对比了本文方法和OPEG以及ELPP方法所需的时间。时间指的是用户发送查询请求到用户获取查询结果所消耗的时间。如图2所示，随着k值的增加，本文方法消耗的时间逐渐上升，而ELPP方法并没有随着k值的增加而增加，原因是ELPP方法在AS端进行用户匿名操作的时候，只需要在历史查询数据中选择相同Hilbert值的其他位置即可，而本文方法需要计算多边形的面积确定位置之间的分散度，随着k值的增加需要计算更多的三角形面积。而OPEG方法使用保序加密，没有使用k匿名，因此其时间消耗和k不相关，需要使用更多的时间来加解密信息。

图2时间开销的对比

（2）网络通信消耗

网络通信消耗指的是网络上传输信息的数据量大小，由于是模拟位置请求过程和查询过程，而数据量主要指的是LBSs对查询结果返回的POI数量，因此对比不同方法返回给AS的POI数量。

图3网络通信开销对比

如图3所示，由于本文方法生成的k匿名区域是分散的，因此之间的距离更远，对于每个位置都需要在搜索半径之内进行POI的查找，搜索的结果会更多；而ELPP方法匿名位置点比较集中，因此有重复的查询结果，能够有相对较少查询结果；OPEG方法的并不使用k匿名，而是对查询结果直接加密来保护隐私信息，其网络通信开销小。

（3）匿名位置分散度

本文方法在构造k匿名的时候，考虑了匿名位置点的分散程度，分散度越高的位置集合具有更高的面积，所选出来的位置能够分散在各个地方，而不是聚簇在一个范围之内，从而能够提高用户的隐私保护程度，由于OPEG并没有k匿名的过程，因此就匿名面积和ELPP进行比较。计算比值，SM和 SMELPP分别是本文方法和ELPP方法形成的匿名区域面积，β值越大，表示本文方法比ELPP匿名产生的位置更分散。

图4位置分散度比值

如图4所示，随着k的值逐渐增大，β值逐渐增大，表明本文方法生成的匿名集合相比ELPP方法有更大的面积，本文方法匿名位置的分布相对ELPP更加分散，而不是聚簇在一个较小的区域内，当k的值为10的时候，本文方法比ELPP的匿名面积提高了11%，说明本文方法相对ELPP方法能够产生更加分散的匿名位置集合。

4 结语

本文提出一种基于网格偏移的分散位置隐私保护方法。文献[14]和文献[16]为了防止用户的隐私信息泄露给匿名服务器和位置服务器，需要较大的时间开销，产生的匿名位置集合是集中的且容易匿名请求内容单一。本文所提方法根据周期更新的网格信息计算偏移网格区域，匿名服务器根据用户查询请求选择分散的、请求内容多样的网格坐标构成集合，使匿名服务器进行匿名处理和位置服务器进行匿名查询的时候，难以得知用户的隐私信息，并且有较低的时间开销和分布更加分散的匿名位置集合。