一种位置服务中基于假位置和几何学的位置隐私保护方法

摘要

本发明提供一种位置服务中基于假位置和几何学的位置隐私保护方法，属于信息安全技术领域。该方法基于DLS算法并采用熵来衡定匿名化程度，不仅考虑可能被攻击者掌握的边信息，还考虑了位置与查询内容和查询时间的相关性即语义系数，同时，使用本发明方法产生的请求报文中的位置信息可以自由选择是否包含用户的真实位置。由于在选择假位置时候考虑了可能被攻击者利用的边信息和位置与查询内容和查询时间的相关性，所以本发明能够有效的实现K匿名，使用户能够获得足够大的熵值，降低用户真实位置暴露的概率。

说明书

技术领域

本发明属于信息安全技术领域，具体涉及一种位置服务中基于假位置和几何学的位置隐 私保护方法。

背景技术

随着现代通信技术、移动终端的高速发展，基于位置服务的应用系统取得了巨大成功。 近几年来，由于基于位置服务(LBS)系统给能给人们的生活带来很大的便捷，因此迅速得 到人们的关注并且广泛用用在各大领域中。在LBS应用系统中，人们利用手持终端(智能手 机、平板)就能轻松的向LBS服务器发起请求，得到自己想要的相关信息。然而，在享受位 置服务带给我们生活便捷的同时，也暴露了很多隐私安全的问题。在基于位置服务中，每一 次提出请求，请求内容中都必需带有用户的精确位置信息，这样LBS提供者才能有效地作高 质量的服务。但是我们不能保证LBS提供者是完全可信的，它有可能暴露用户的相关信息。 K匿名作为解决当前LBS位置隐私安全问题的技术手段，近年来受到了国内外隐私保护领域 研究的广泛关注。所谓K匿名技术就是用户在发送请求时与其它K-1个假位置一起发送给LBS 服务器，便于混淆视听，使得LBS服务器难以从K个位置中辨别出真实的用户的位置。

位置服务中有很多关于位置隐私保护的研究，n-CD是一种保护位置隐私的方法。n-CD 首先将用户感兴趣的区域等分成n份，用户的真实位置位于该区域的中心，然后在每一块扇 形区域随机选择一个位置，最后再以随机选择的n个位置为中心，并且以逆时针方向依次产 生n个圆形区域使其覆盖相应的扇形区域，从而覆盖用户感兴趣的整个区域。当用户给LBS 服务器发送服务请求时，他不需要将自己的准确位置发送给位置服务器，只需将n个圆形区 域的中心及半径发送给位置服务器。虽然上述方法用户发给LBS服务器的位置服务请求不包 括用户的真实位置，能够很好保护用户的位置隐私，但是攻击者还是能知道推测出用户在n 个圆形区域某个重叠区域里，特别当n的取值越大时，n个圆形区域的半径的将会越来越小， 从而使n个圆形区域的重叠区域越来越小，在重叠区域也将会存在越来越少的用户或者只包 含越来越少的位置数目，这将导致用户真实位置暴露的风险将会很高。

Niu等人提出的DLS算法就是一种考虑边信息而选择假位置方法(Niu,B.et al..Achieving  k-anonymity in privacy-aware location-based services[C].IEEE INFOCOM,2014,754–762.)。 DLS算法用熵来衡定用户的隐私级别，熵值越大表明用户的隐私级别越高。DLS方法将其所 服务的区域划分成n×n＝N个大小相同的位置单元，每个位置单元都对应一个历史请求概率 (query probability based on the previous query history)，具体定义如下：

且$\underset{i=1}{\overset{N}{\Sigma }}{p}_i=1$

其中，q_i为所划分区域中第i个位置单元的历史请求概率，N代表LBS服务器服务范围内的 位置单元总数。

在基于DLS算法的LBS系统中，LBS服务器需要统计出服务区域每个位置单元内用户发送 位置服务请求的历史概率，然后发布这份概率信息，这样每个用户都可以得到位置请求历史 概率。当用户需要某种位置服务时，用户首先利用GPS等定位装置获得自己的准确位置，根 据位置请求历史概率获得当前所处位置发送位置服务请求的历史概率，然后根据用户的匿名 度要求K，从位置地图中寻找出2K个与当前位置发送请求历史概率接近的候选位置，最后计 算从该2K个候选位置中选择的所有可能K-1个位置和用户真实位置构成的K个位置的熵值，选 择使熵值最大的K个位置作为用户向LBS服务器发送的位置信息。虽然上述方法能够实现K匿 名，保护用户的位置隐私，但该方法所选择的假位置必须包含用户的真实位置。该方法在选 择K-1个假位置时采用了枚举的方法，虽然保证了选择的K个位置熵值是最大的，但是算法复 杂度较高、收敛速度太慢，尤其不能适用于匿名度要求很高的用户。该方法只考虑了可能被 攻击者利用的边信息，但没有考虑位置与查询内容和查询时间的相关性。

发明内容

本发明的目的是提供一种位置服务中基于假位置和几何学的位置隐私保护方法，该方法 基于DLS算法，不仅考虑可能被攻击者掌握的边信息，而且引入了位置与查询内容、查询时 间的相关性即语义系数。

本发明具体采用如下技术方案：

一种位置服务中基于假位置和几何学的位置隐私保护方法，其具体流程如图1所示，包 括以下步骤：

步骤1.初始化：在本方法中，LBS服务器是一个服务提供者，存储着所有服务的数据库 以及负责更新服务数据；当用户发送LBS服务请求时，LBS服务器负责接收用户的服务查询 请求，在数据库中搜索相应的服务数据，然后将搜索结果回馈给用户；

同时，在LBS服务器服务的区域内，LBS服务器负责给每一个位置根据其位置属性进行 分类(如餐厅、商场、学校等)得每个位置的位置类型，并且能够获取全局信息(如用户在每 个位置的历史请求概率)，而且，LBS服务器能够发布其服务范围内每个位置用户发送请求的 历史请求概率及位置类型；

步骤2.用户端从LBS服务器获得相应服务区域内所有位置的位置类型后，为每一种位 置类型在不同时间段内设定一个不同语义系数，设定方法如下：用户端在当前时间、当前位 置类型上发送位置请求的概率越大，则该位置类型在当前时间段的语义系数越大，例如，用 户在晚上下班时间后在商场发送查询请求的概率大于其在写字楼区域发送查询请求的概率， 则在该时间段上“商场”这一位置类型的语义系数大于“写字楼”这一位置类型的语义系数， 具体时间段的划分可根据用户实际需求随时调整；即，语义系数越大表明该位置类型与查询 时间的相关性越大；

步骤3.当用户需要位置服务时，用户端根据自身隐私要求设定合适的匿名度K、位置类 型数目m和感兴趣区域的半径R1，所述感兴趣区域是以用户端真实位置为圆心、R1为半径 的圆形区域；K值越大表明用户的匿名度要求越高，m的设置是为了保证用户发送请求报文 中出现的假位置尽可能不属于同一位置类型，这样能更好的保证用户的位置隐私，且m的取 值不大于该服务区域内的位置类型总数；

步骤4.根据每种位置类型的语义系数以及从LBS服务器那里获得的每个位置的历史请求 概率集合，计算出每个位置当前时间的服务查询概率p_i并汇于概率集合P中，p_i＝q_i·a_i，t，其 中，q_i为服务区域中第i个位置单元的历史请求概率，a_i，t为该位置单元所对应的位置类型在 时间t时的语义系数；

步骤5.将概率集合P中的概率按照位置类型分类得多个概率子集，即每一位置类型对应 一个概率子集；

步骤6.若用户需要将其真实位置连同假位置一并发送至LBS服务器，则执行步骤6-1至 步骤6-3；反之，即用户不希望请求报文中包含其真实位置，则执行步骤7；

步骤6-1.用户读取当前位置的服务查询概率p_r及当前时间所处位置类型的语义系数a_r， 并从所处服务区域中除真实位置类型外的剩余位置类型中选择当前时间的语义系数与a_r最接 近的m-1个位置类型；

步骤6-2.对于步骤6-1所选择的每一个位置类型，在其对应的概率子集中选择出与用户 当前位置发送当前查询内容的概率p_r最相近的K个概率，在用户所处真实位置类型对应的概 率子集中选取与概率p_r最相近的K个概率，把所选择的K×m个概率汇于概率集合P中；

步骤6-3.在概率集合P中选择出K-1个概率值，并将所对应的K-1个位置作为假位置连 同用户端真实位置作为K个感兴趣区域的圆心，其半径均为R1，将这K个感兴趣区域作为 位置请求区域发送给LBS服务器，完成用户端位置服务请求的发送；

所述K-1个概率值的选取满足以下条件：在从集合P中任意选取K-1个概率值与用户端 真实位置对应的服务查询概率p_r组成的概率集合中，本步骤所选取的K-1个概率值与用户端 真实位置对应的服务查询概率p_r组成的概率集合的熵值是最大的；

步骤7.若用户不希望请求报文中包含其真实位置，则执行步骤7-1至步骤7-4；

步骤7-1.用户首先将自己感兴趣的圆形区域等分成n个扇形区域，其中n是用户根据自 己的隐私要求设定；用户在其等分的每一区域里选择一个与用户端当前位置的服务查询概率 最接近的位置并记为几何位置，以所选择的n个几何位置为圆心产生n个圆形区域覆盖用户 感兴趣的区域，所述n个圆形区域的半径通过步骤7-1-1至步骤7-1-4所述方法确定：

步骤7-1-1.从n个几何位置中随机选定一个几何位置记为C1，用户所在真实位置为S0， 圆心C1所在扇形区域的剩余两个顶点分别记为Q1、Q2，则圆心C1所对应的半径为 r₁＝D·max{d_1，1，d_1，2，d_1，3}，其中d_1，1、d_1，2、d_1，3分别是圆心C1与点S0、Q1、Q2的直 线距离，D∈(1,1.5]；

步骤7-1-2.以C1所在扇形区域为起始区域，以用户真实位置为圆心按逆时针方向选取与 起始区域相邻的扇形区域，该区域中所选择的几何位置记为C2；若以C1为圆心、r₁为半径 的圆形区域已经覆盖C2所在扇形区域，则圆心C2对应的半径r₂设为零，否则，圆心C2对 应的半径r₂＝D·max{d_2，1，d_2，2，d_2，3}，其中d_2，1、d_2，2、d_2，3分别是圆心C1与点S0、Q2、 Q3的直线距离，D∈(1,1.5]，点Q2、Q3为S2所在扇形区域的除圆心外的两个顶点；

步骤7-1-3.以C2所在扇形区域为起始区域，以用户真实位置为圆心按逆时针方向选取 与起始区域相邻的扇形区域，该区域中所选择的几何位置记为C3；若以C1为圆心、r₁为半 径的圆形区域及C2为圆心、r₂为半径的圆形区域的总区域已经完全覆盖C3所在扇形区域， 则圆心C3对应的半径r₃设为零，否则，圆心C3对应的半径r₃参照r₁的取值方法进行取值；

步骤7-1-4.按上述方法依次对所选择的n个圆形区域的半径进行计算，得n个半径值 r₁、…、r_n；

步骤7-2.设所选择的n个几何位置所包含的位置类型数目为m*，若执行步 骤7-3，否者执行步骤7-4；

步骤7-3.用户端从概率集合P中将该n个几何位置对应的概率值以及用户端真实位置对 应的概率值剔除后得集合从中选取K-n个概率并将其所对应的K-n个位置连同步骤7-1 所得的n个几何位置作为K个圆形位置服务请求区域的圆心，其半径均为R2＝max{r₁，…， r_n}；将这K个区域作为位置请求区域发送给LBS服务器，完成用户端位置服务请求的发送；

所述K-n个概率值的选取满足以下条件：在从集合中任意选取K-n个概率值与步骤7-1 选取的n个几何位置对应的服务查询概率组成的概率集合中，本步骤所选取的K-n个概率值 与步骤7-1选取的n个几何位置对应的服务查询概率组成的概率集合的熵值是最大的；

步骤7-4.若计算步骤7-1所得n个几何位置对应的位置类型的当前时间语 义系数的平均值，记为

步骤7-4-1.用户端从所处服务区域中除真实位置类型及所选的n个几何位置相应的m* 个位置类型之外的剩余位置类型中选择当前时间语义系数与a最接近的m-m*个位置类型；

步骤7-4-2.针对步骤7-4-1所选择的m-m*个位置类型及所述n个几何位置对应的m*个位 置类型，在每一个位置类型对应的概率子集中选择出与用户当前位置的服务查询概率p_r最接 近的K-n个概率值，把所选择的(K–n)·m个概率值汇于概率集合中；

步骤7-4-3.在概率集合中选择出K-n个概率值，并将所对应的K-n个位置连同步骤7-1 所得的n个几何位置作为K个圆形位置服务请求区域的圆心，所述区域半径均为 R2＝max{r₁，…，r_n}；将这K个区域作为位置请求区域发送给LBS服务器，完成用户端位置 服务请求的发送；

所述K-n个概率值的选取满足以下条件：在从集合中任意选取K-n个概率值与步骤7-1 选取的n个几何位置对应的服务查询概率组成的概率集合中，本步骤所选取的K-n个概率值 与步骤7-1选取的n个几何位置对应的服务查询概率组成的概率集合的熵值是最大的。

概率集合的熵值H由如下公式确定：

其中，f为概率集合的概率值数量，p_j为概率集合的第j个概率值。

本发明的有益效果是：

(1)由于在选择假位置时候考虑了可能被攻击者利用的边信息和位置与查询内容和查询 时间的相关性，所以本发明能够有效的实现K匿名，使用户能够获得足够大的熵值，降低用 户真实位置暴露的概率；

(2)本发明在产生n个圆形区域覆盖用户感兴趣范围时，不仅能够大大降低计算复杂度， 而且使用户的真实位置能够掩藏在更大的某个重叠区域里；

(3)本发明提出的选择假位置的方法使产生的假位置中可以不包括用户的真实位置，从 而提高了攻击者识别出用户真实位置的不确定性。

附图说明

图1为本发明提供的位置隐私保护方法流程图；

图2为本发明实施例的圆形区域CA₁的划分示意图；

图3为本发明实施例的圆形区域CA₂的划分示意图；

图4为本发明实施例的圆形区域CA₃的划分示意图；

图5为本发明实施例的圆形区域CA₄的划分示意图。

具体实施方式

下面结合附图和实施例对本发明做进一步描述。

实施例

本实施例具体采用如下技术方案：

一种位置服务中基于假位置和几何学的位置隐私保护方法，其具体流程如图1所示，包 括以下步骤：

步骤1.初始化：在本方法中，LBS服务器是一个服务提供者，存储着所有服务的数据库 以及负责更新服务数据；当用户发送LBS服务请求时，LBS服务器负责接收用户的服务查询 请求，在数据库中搜索相应的服务数据，然后将搜索结果回馈给用户；

同时，在LBS服务器服务的区域内，LBS服务器负责给每一个位置根据其位置属性进行 分类(如餐厅、商场、学校等)得每个位置的位置类型，并且能够获取全局信息(如用户在每 个位置的历史请求概率)，而且，LBS服务器能够发布其服务范围内每个位置用户发送请求的 历史请求概率及位置类型；

步骤2.用户端从LBS服务器获得相应服务区域内所有位置的位置类型后，为每一种位 置类型在不同时间段内设定一个不同语义系数，设定方法如下：用户端在当前时间、当前位 置类型上发送位置请求的概率越大，则该位置类型在当前时间段的语义系数越大，例如，用 户在晚上下班时间后在商场发送查询请求的概率大于其在写字楼区域发送查询请求的概率， 则在该时间段上“商场”这一位置类型的语义系数大于“写字楼”这一位置类型的语义系数， 具体时间段的划分可根据用户实际需求随时调整；即，语义系数越大表明该位置类型与查询 时间的相关性越大；

步骤3.当用户需要位置服务时，用户端根据自身隐私要求设定合适的匿名度K、位置类 型数目m和感兴趣区域的半径R1，所述感兴趣区域是以用户端真实位置为圆心、R1为半径 的圆形区域；K值越大表明用户的匿名度要求越高，m的设置是为了保证用户发送请求报文 中出现的假位置尽可能不属于同一位置类型，这样能更好的保证用户的位置隐私，且m的取 值不大于该服务区域内的位置类型总数；

步骤4.根据每种位置类型的语义系数以及从LBS服务器那里获得的每个位置的历史请求 概率集合，计算出每个位置当前时间的服务查询概率p_i并汇于概率集合P中，p_i＝q_i·a_i，t，其 中，q_i为服务区域中第i个位置单元的历史请求概率，a_i，t为该位置单元所对应的位置类型在 时间t时的语义系数；

步骤5.将概率集合P中的概率按照位置类型分类得多个概率子集，即每一位置类型对应 一个概率子集；

步骤6.若用户需要将其真实位置连同假位置一并发送至LBS服务器，则执行步骤6-1至 步骤6-3；反之，即用户不希望请求报文中包含其真实位置，则执行步骤7；

步骤6-1.用户读取当前位置的服务查询概率p_r及当前时间所处位置类型的语义系数a_r， 并从所处服务区域中除真实位置类型外的剩余位置类型中选择当前时间的语义系数与a_r最接 近的m-1个位置类型；

步骤6-2.对于步骤6-1所选择的每一个位置类型，在其对应的概率子集中选择出与用户 当前位置发送当前查询内容的概率p_r最相近的K个概率，在用户所处真实位置类型对应的概 率子集中选取与概率p_r最相近的K个概率，把所选择的K×m个概率汇于概率集合P中；

步骤6-3.在概率集合P中选择出K-1个概率值，并将所对应的K-1个位置作为假位置连 同用户端真实位置作为K个感兴趣区域的圆心，其半径均为R1，将这K个感兴趣区域作为 位置请求区域发送给LBS服务器，完成用户端位置服务请求的发送；

所述K-1个概率值的选取满足以下条件：在从集合P中任意选取K-1个概率值与用户端 真实位置对应的服务查询概率p_r组成的概率集合中，本步骤所选取的K-1个概率值与用户端 真实位置对应的服务查询概率p_r组成的概率集合的熵值是最大的；

步骤7.若用户不希望请求报文中包含其真实位置，则执行步骤7-1至步骤7-4；

步骤7-1.用户首先将自己感兴趣的圆形区域等分成n＝4个扇形区域，用户在其等分的每 一区域里选择一个与用户端当前位置的服务查询概率最接近的位置并记为几何位置，以所选 择的n个几何位置为圆心产生n个圆形区域覆盖用户感兴趣的区域，所述n个圆形区域的半 径通过步骤7-1-1至步骤7-1-4所述方法确定：

步骤7-1-1.从n个几何位置中随机选定一个几何位置记为C₁，用户所在真实位置为O， 如图2所示，圆形区域CA₁的半径r₁设置为其中和分别代 表点C₁与Q₂、Q₁、O之间的直线距离，D∈(1,1.5]；

步骤7-1-2.以C₁所在扇形区域为起始区域，以用户真实位置为圆心按逆时针方向选取与 起始区域相邻的扇形区域，该区域中所选择的几何位置记为C₂；如图3所示，C₂是扇形区域 S₂里选择出的一个几何位置；如果CA₁已经完全覆盖了扇形区域S₂，则圆形区域CA₂的半径r₂设置为0，否则，圆形区域CA₂的半径r₂设置为其中和分 别代表点C₂与Q₂、Q₃和O之间的直线距离，D∈(1,1.5]；

步骤7-1-3.以C₂所在扇形区域为起始区域，以用户真实位置为圆心按逆时针方向选取与 起始区域相邻的扇形区域，该区域中所选择的几何位置记为C3；如图4所示，C₃是扇形区 域S₃里选择出的一个几何位置；如果CA₁和CA₂已经完全覆盖了扇形区域S₃，则圆形区域CA₃ 的半径r₃设置为0，否则，圆形区域CA₃的半径r₃设置为其中和分别代表点C₃与Q₃、Q₄和O之间的直线距离，D∈(1,1.5]；

步骤7-1-4.最后一个扇形区域所选的几何位置记为C₄，如图5所示，C₄是扇形区域S₄里 选择出的一个几何位置，如果CA₁、CA₂和CA₃已经完全覆盖了扇形区域S₄，则圆形区域CA₄的半径r₄设置为0，否则，圆形区域CA₄的半径r₄设置为其中和分别代表点C₄与Q₄、Q₁和O之间的直线距离，D∈(1,1.5]；

步骤7-2.设所选择的n个几何位置所包含的位置类型数目为m*，若执行步 骤7-3，否者执行步骤7-4；

步骤7-3.用户端从概率集合P中将该n个几何位置对应的概率值以及用户端真实位置对 应的概率值剔除后得集合从中选取K-n个概率并将其所对应的K-n个位置连同步骤7-1 所得的n个几何位置作为K个圆形位置服务请求区域的圆心，其半径均为R2＝max{r₁，…， r_n}；将这K个区域作为位置请求区域发送给LBS服务器，完成用户端位置服务请求的发送；

所述K-n个概率值的选取满足以下条件：在从集合中任意选取K-n个概率值与步骤7-1 选取的n个几何位置对应的服务查询概率组成的概率集合中，本步骤所选取的K-n个概率值 与步骤7-1选取的n个几何位置对应的服务查询概率组成的概率集合的熵值是最大的；

步骤7-4.若计算步骤7-1所得n个几何位置对应的位置类型的当前时间语 义系数的平均值，记为a；

步骤7-4-1.用户端从所处服务区域中除真实位置类型及所选的n个几何位置相应的m* 个位置类型之外的剩余位置类型中选择当前时间语义系数与a最接近的m-m*个位置类型；

步骤7-4-2.针对步骤7-4-1所选择的m-m*个位置类型及所述n个几何位置对应的m*个位 置类型，在每一个位置类型对应的概率子集中选择出与用户当前位置的服务查询概率p_r最接 近的K-n个概率值，把所选择的(K–n)·m个概率值汇于概率集合中；

步骤7-4-3.在概率集合中选择出K-n个概率值，并将所对应的K-n个位置连同步骤7-1 所得的n个几何位置作为K个圆形位置服务请求区域的圆心，所述区域半径均为 R2＝max{r₁，…，r_n}；将这K个区域作为位置请求区域发送给LBS服务器，完成用户端位置 服务请求的发送；

所述K-n个概率值的选取满足以下条件：在从集合中任意选取K-n个概率值与步骤7-1 选取的n个几何位置对应的服务查询概率组成的概率集合中，本步骤所选取的K-n个概率值 与步骤7-1选取的n个几何位置对应的服务查询概率组成的概率集合的熵值是最大的。