基于位置服务中连续实时查询场景下的隐私保护方法

摘要

本发明公开了一种基于位置服务中连续实时查询场景下的隐私保护方法，主要解决现有位置匿名方法对用户隐私保护程度不高的缺陷。其实现步骤为：1.建立一个由用户、定位设施、位置服务器构成的通信系统框架；2.用户首次利用位置的单点评分函数选定若干假位置；3.用户将真实位置和若干假位置组成位置集发送给位置服务器；4.用户后续利用位置之间的连续点评分函数选定若干假位置，并将真实位置和若干假位置组成位置集发送给位置服务器。本发明通过综合考虑单点位置的访问热度、访问时间分布和连续位置的访问次序、访问时间分布这些因素，启发式地生成假位置来实现位置匿名，有效地保护了用户的位置隐私，可用于连续位置查询和导航服务。

说明书

技术领域：

本发明属于无线网络技术领域，涉及位置隐私的保护，可应用于连续位置查询和导航 服务。

背景技术：

基于位置的服务，是随着无线网络技术的进步和移动终端的普及而发展起来的给用户 提供基于其位置信息的一种增值服务。利用基于位置的服务，用户可以更加准确、高效地 同周围的人或物建立起自己相应的联系，从而更好地融入周围环境，例如，用户通过向服 务运营商发起问询，可以在当前位置查询离自己最近的餐馆或者公交车站等。

但是，在用户享受基于位置的服务带来的便利的同时，其隐私也可能已经暴露给了不 可信的第三方。例如，用户在公交站台通过手机向服务运营商发送一条请求，来查询离自 己当前位置最近的银行网点，在这种场景下，用户可能会泄露自己当前的位置信息，以及 由其位置推出的其它相关信息，比如财务状况、出行安排等；如果用户多次地进行位置查 询，服务运营商会得到更多关于用户的位置信息，通过大量相关信息的综合分析，可能会 造成用户隐私的严重泄露。因此，基于位置服务的安全问题必须得到重视。

目前常见的一些位置隐私保护方法主要有基于位置模糊的方法和基于位置匿名的方 法。其中：

在基于位置模糊的方法中，用户通过提交偏移位置或者向实际轨迹中加入噪声实现差 分隐私等来达到保护用户隐私的目的。但是，位置信息的模糊化会提供给用户不精确的位 置信息，造成基于位置服务质量的降低；当基于位置服务的质量要求较高时，这种方案就 会受到限制，难以保证用户隐私的充分安全。

在基于位置匿名的方法中，一般将用户的真实位置隐藏在若干假位置之中，保障用户 的位置隐私。其中，k－匿名是指当用户的位置被隐藏在k个位置中且每个位置被认为是 等概率出现时的状态。一般的基于位置匿名的方案主要考虑单一位置的隐私保护，并不考 虑连续实时查询的场景，但是，在日常生活中，用户常常进行的是连续实时的查询，这样， 在拥有用户大量边信息的运营服务商面前，针对单点位置隐私保护的方案，用户很难真正 地达到k－匿名的隐私保护程度。

在上述方法中，由于均没有考虑基于位置服务中连续实时查询的场景，当运营服务商 利用自己拥有的大量边信息，比如，查询时间、查询次数、查询地点的先后次序等，结合 起来进行分析，用户的位置隐私可能就会泄露，从而可能带来更多的安全问题。

发明内容

本发明的目的在于针对上述已有技术的不足，提出一种基于位置服务中连续实时查询 场景下的隐私保护方法，通过使用户在向位置服务器请求位置服务时，利用自己以往的知 识启发式地生成由其真实位置和若干假位置组成的位置集构成的轨迹序列，实现有效的位 置匿名，提高用户的隐私程度，保证用户安全。

为实现上述目的，本发明的技术方案包括如下：

(1)建立一个由用户、定位设施、位置服务器构成的通信系统框架，其中：

用户，用于通过3G或4G蜂窝网或WiFi与定位设施和位置服务器进行通信，缓存公 开位置数据集R；

定位设施，用于协同用户GPS模块实现定位；

位置服务器，用于接收用户的查询并为其提供相关的位置服务；

(2)用户在t₁时间向位置服务器生成并发送由其真实位置L₁和(k-1)个假位置组成的 位置集合：

(2a)用户计算选定的t₁时间预存位置数据集R中每个位置的访问热度值pop(w)、访 问时间分布timp(w,t₁)和单点评分函数值f_SES(w,t₁)＝pop(w)*timp(w,t₁)，其中，w为位置 数据集R中选定的位置；

(2b)用户计算t₁时间真实位置L₁的单点评分函数值f_SES(L₁,t₁)＝pop(L₁)*timp(L₁,t₁)；

(2c)用户根据预存位置数据集R中所有位置的单点评分函数f_SES(w,t₁)与真实位置L₁的单点评分函数f_SES(L₁,t₁)之间的差值绝对值val(w,t₁)，将预存位置数据集R的对应位置由 小到大排列，选出前(k-1)个位置作为选定的假位置，得到包含其真实位置L₁和(k-1)个 假位置组成的时间t₁下位置集合DS₁，随机地安排位置集合DS₁中位置的次序，并将位置集 合DS₁发送给位置服务器，其中，k为用户自定义的整形参数；

(3)用户在t_i时间向位置服务器生成并发送由其真实位置L_i和(k-1)个假位置组成的 位置集合：

(3a)用户在预存位置数据集R中选出n(k-1)个假位置组成的候选位置集合RS，其 中，n为用户自定义的整形参数；

(3a1)用户计算选定的t_i时间预存位置数据集R中每个位置的访问热度值pop(w)、 访问时间分布timp(w,t_i)和单点评分函数值f_SES(w,t_i)＝pop(w)*timp(w,t_i)，其中， i＝2,3,…,s，s为用户查询的次数；

(3a2)用户计算t_i时间真实位置L_i的单点评分函数值f_SES(L_i,t_i)＝pop(L_i)*timp(L_i,t_i)；

(3a3)用户根据预存位置数据集R中所有位置的单点评分函数f_SES(w,t_i)与真实位置 L_i的单点评分函数f_SES(L_i,t_i)之间的差值绝对值val(w,t_i)，将预存位置数据集R的对应位置 由小到大排列，选出前n(k-1)个位置作为选定的假位置，得到候选位置集合RS；

(3b)用户在候选位置集合RS中选出(k-1)个假位置组成的位置集合：

(3b1)用户计算当前时间t_i候选位置集合RS中每个位置rs_i与上一时间t_i-1已发送的位 置集合DS_i-1中每个位置ds_i-1之间的连续点评分函数的值f_CES(ds_i-1,rs_i,t)，其中，时间差 t＝t_i-t_i-1；

(3b2)用户计算当前时间t_i的真实位置L_i与上一时间t_i-1下的真实位置L_i-1之间的连续 点评分函数的值f_CES(L_i-1,L_i,t)；

(3b3)用户根据步骤(3b1)中得到的连续点评分函数f_CES(ds_i-1,rs_i,t)和步骤(3b2) 中得到的连续点评分函数f_CES(L_i-1,L_i,t)之间的差值绝对值val(ds_i-1,rs_i,t)，将候选位置集合 RS的对应位置由小到大排列，选出前(k-1)个作为选定的假位置，得到假位置集合；

(3c)用户将真实位置L_i和步骤(3b3)中得到的假位置集合组成时间t_i下的位置集合 DS_i，随机地安排该位置集DS_i中位置的次序，并将位置集DS_i发送给位置服务器。

本发明与现有技术相比具有如下优点：

1)本发明由于使用用户以往的位置数据集，在选定假位置时，综合考虑了单点位置 的访问热度、访问时间分布和连续位置的访问次序、访问时间分布等，能实现更有效的位 置匿名，提高了用户的隐私程度；

2)本发明由于在用户端完成位置隐私保护操作，不牵涉可信第三方，减少了通信开 销，进一步提高了用户的隐私程度；

3)本发明由于在选定若干假位置时，首先高效筛选多于需要数目的假位置，再从中 选定需要数目的假位置，这样的二次挑选机制，增强了发明的灵活性，避免了额外时延， 从而保证了用户向位置服务器请求位置服务的高效性。

附图说明

图1是本发明使用的通信系统框架图；

图2是本发明的实现流程图；

图3是在位置服务器实施基于位置访问热度的攻击下，用本发明和现有三种方法测试 用户位置隐私的保护程度结果图；

图4是在位置服务器实施基于位置访问时间分布的攻击下，用本发明和现有三种方法 测试用户位置隐私的保护程度结果图；

图5是在位置服务器实施基于连续位置访问次序的攻击下，用本发明和现有三种方法 测试用户位置隐私的保护程度结果图；

图6是在位置服务器实施基于连续位置访问时间分布的攻击下，用本发明和现有三种 方法测试用户位置隐私的保护程度结果图。

具体实施方案

本发明的核心思想是在基于位置服务中连续实时查询场景下，用户使用以往的位置数 据集合，综合考虑单点位置的访问热度、访问时间分布和连续位置的访问次序、访问时间 分布等，启发式地生成假位置集合，用来隐藏用户的真实位置，使位置服务器难以利用边 信息获取用户的位置隐私，提高用户隐私程度。

参照图2，本发明基于位置服务中连续实时查询场景下的隐私保护方法，其实现步骤 如下：

步骤1，建立通信系统框架。

参照图1，本步骤建立的通信系统包括：用户、定位设施、位置服务器。其中，用户 与定位设施和位置服务器均通过3G或4G蜂窝网或WiFi进行双向无线连接。

所述用户，包含应用模块、数据库模块和GPS模块三个功能模块；应用模块主要用于 生成并发送位置集合给位置服务器，GPS模块主要用于向定位设施查询位置信息并向应用 模块提供用户的地理位置信息，数据库模块主要用于存储和管理用户的历史位置信息；

所述定位设施，主要包含GPS模块，该GPS模块主要用于对用户的查询进行响应并 返回用户的地理位置信息；

所述位置服务器，包含数据库模块和应用模块两个功能模块；数据库模块主要用于存 储用户查询的历史位置信息和其他相关信息，应用模块主要用于接收用户的位置查询并为 用户返回位置信息数据。

步骤2，用户在t₁时间发送位置集时，计算预存位置数据集R中所有位置的单点评分函 数。

(2a)用户根据位置数据集R中单个位置w的访问次数vis(w)和所有位置总的访问次 数sum(R)，得到位置w的访问热度值pop(w)＝vis(w)/sum(R)；

(2b)用户将一天时间分成24个区间，每个区间范围为1个小时，计算数据集中单 个位置w在每一区间上的访问次数vis(w,v)和该位置总的访问次数sum(w)，得到该位置w 在每一区间的访问频率visp(w,v)＝vis(w,v)/sum(w)，由此得到该位置w的访问分布 TD(w,v)，其中，v为选定的时间区间；

(2c)用户用当前时间t₁的数值作为正态分布的期望、1作为正态分布的方差，得到时 间区间v的正态分布N(v；t₁,1)；

(2d)用户根据步骤(2b)得到的位置w访问分布TD(w,v)与步骤(2c)得到的正态 分布N(v；t₁,1)，计算位置数据集R中单个位置w在t₁时间下的访问时间分布timp(w,t₁):

$timp(w,t_1)=1/\left({\Sigma }_{v}N\right(v;t_1,1)*{\log }_2(\frac{N(v;t_1,1)}{TD(w,v)})+{\Sigma }_{v}TD(w,v)*{\log }_2(\frac{TD(w,v)}{N(v;t_1,1)}\left)\right),$

其中，*表示相乘；

(2e)用户根据步骤(2a)得到的位置w访问热度值pop(w)与步骤(2d)得到的位置 w访问时间分布timp(w,t₁)，计算预存位置数据集R中每个位置的单点评分函数 f_SES(w,t₁)＝pop(w)*timp(w,t₁)。

步骤3，用户在t₁时间生成位置集合，并将位置集合发送给位置服务器。

用户根据预存位置数据集R中所有位置的单点评分函数f_SES(w,t₁)与真实位置L₁的单 点评分函数f_SES(L₁,t₁)之间的差值绝对值val(w,t₁)＝|f_SES(w,t₁)-f_SES(L₁,t₁)|，将预存位置数 据集R的对应位置由小到大排列，选出前(k-1)个位置作为选定的假位置，得到包含其真 实位置L₁和(k-1)个假位置组成的时间t₁下位置集合DS₁，随机地安排位置集合DS₁中位置 的次序，并将位置集合DS₁发送给位置服务器，其中，k为用户自定义的整形参数。

步骤4，用户在t_i时间发送位置集时，计算预存位置数据集R中所有位置的单点评分函 数。

(4a)用户根据位置数据集R中单个位置w的访问次数vis(w)和所有位置总的访问次 数sum(R)，得到该位置w的访问热度值pop(w)＝vis(w)/sum(R)；

(4b)用户将一天时间分成24个区间，每个区间范围为1个小时，计算位置数据集R 中单个位置w在每一区间上的访问次数vis(w,u)和该位置总的访问次数sum(w)，得到该位 置w在每一区间的访问频率visp(w,u)＝vis(w,u)/sum(w)，由此得到该位置w的访问分布 TD(w,u)，其中，u为选定的时间区间；

(4c)用户用当前时间t_i的数值作为正态分布的期望、1作为正态分布的方差，得到时 间区间u的正态分布N(u；t_i,1)，其中，i＝2,3,…,s，s为用户查询的次数；

(4d)用户根据步骤(4b)得到的位置w访问分布TD(w,u)与步骤(4c)得到的正态 分布N(u；t_i,1)，计算位置数据集R中单个位置w在时间下访问时间分布timp(w,t_i):

$timp(w,t_i)=1/\left({\Sigma }_{u}N\right(u;t_i,1)*{\log }_2(\frac{N(u;t_i,1)}{TD(w,u)})+{\Sigma }_{u}TD(w,u)*{\log }_2\left(\frac{TD(w,u)}{N(u;t_i,1)}\right));$

(4e)用户根据步骤(4a)得到的位置w访问热度值pop(w)与步骤(4d)得到的位置 w访问时间分布timp(w,t_i)，计算预存位置数据集R中每个位置的单点评分函数 f_SES(w,t_i)＝pop(w)*timp(w,t_i)。

步骤5，用户在t_i时间选定候选位置集合。

用户根据预存位置数据集R中所有位置的单点评分函数f_SES(w,t_i)与真实位置L_i的单 点评分函数f_SES(L_i,t_i)之间的差值绝对值val(w,t_i)＝|f_SES(w,t_i)-f_SES(L_i,t_i)|，将预存位置数据 集R的对应位置由小到大排列，选出前n(k-1)个位置作为选定的假位置，得到候选位置集 合RS，其中，n为用户自定义的整形参数。

步骤6，用户在t_i时间计算候选位置集合中连续点评分函数。

(6a)用户将预存位置数据集R中位置ds_i-1到位置rs_i所花费的时间td分为24个区间， 每个区间范围为1个小时，计算在每个区间内的访问次数vis(ds_i-1,rs_i,tp)和从位置ds_i-1到位 置rs_i的总访问次数sum(ds_i-1,rs_i)，得到从位置ds_i-1到位置rs_i在每一区间的访问频率 visp(ds_i-1,rs_i,tp)＝vis(ds_i-1,rs_i,tp)/sum(ds_i-1,rs_i)，由此得到从位置ds_i-1到位置rs_i的访问分 布TD(ds_i-1,rs_i,tp)，其中，tp为选定的区间，ds_i-1为上一时间t_i-1已发送的位置集合DS_i-1中 的位置，rs_i为时间t_i下候选位置集合RS中的位置；

(6b)用户用花费时间t＝t_i-t_i-1的数值作为正态分布的期望、1作为正态分布的方差 得到时间区间tp的正态分布N(tp；t,1)；

(6c)用户根据步骤(6a)得到的访问分布TD(ds_i-1,rs_i,tp)与步骤(6b)得到的正态分 布N(tp；t,1)，计算时间t_i下候选位置集合RS中位置rs_i和上一时间t_i-1已发送的位置集合 DS_i-1中位置ds_i-1之间的连续点评分函数f_CES(ds_i-1,rs_i,t)：

$f_{CES}({\mathrm{ds}}_{i-1},{\mathrm{rs}}_i,t)=1/\left({\Sigma }_{tp}N\right(tp;t,1)*{\log }_2(\frac{N(tp,t,1)}{TD({\mathrm{ds}}_{i-1},{\mathrm{rs}}_i,tp)})+{\Sigma }_{tp}TD({\mathrm{ds}}_{i-1},{\mathrm{rs}}_i,tp)*{\log }_2(\frac{TD({\mathrm{ds}}_{i-1},{\mathrm{rs}}_i,tp)}{N(tp;t,1)}\left)\right).$

步骤7，用户在t_i时间生成位置集合，并将位置集合发送给位置服务器。

(7a)用户根据步骤(6)中得到的连续点评分函数f_CES(ds_i-1,rs_i,t)和真实位置的连续 点评分函数f_CES(L_i-1,L_i,t)间的差值绝对值val(ds_i-1,rs_i,t)＝|f_CES(ds_i-1,rs_i,t)-f_CES(L_i-1,L_i,t)|， 将候选位置集合RS的对应位置由小到大排列，选出前(k-1)个作为选定的假位置，得到假 位置集合，其中，L_i-1为上一时间t_i-1下的真实位置，L_i为当前时间t_i的真实位置；

(7b)用户将当前时间t_i的真实位置L_i和步骤(7a)中得到的假位置集合组成t_i时间下 的位置集合，随机地安排该位置集合中位置的次序，并将位置集合发送给位置服务器。

步骤8，用户确认查询服务是否结束。

用户发送位置集合后，如果用户不再继续查询位置信息，则发送结束；否则，返回步 骤4。

本发明的优点可通过以下仿真实验进一步说明：

1.实验条件设置

条件1，在Gowalla官网下载签到数据集，选取签到位置为纽约的数据组成数据集合， 作为实验的源数据。随机挑选1000条签到轨迹序列发送给仿真位置服务器，并用本发明 和其他三种方法进行位置隐私程度的测试，此过程重复1000次。

条件2，在Intel(R)Celeron(R)G540处理器，Windows7Ultimate操作系统的台式 计算机上测试实验的结果。

条件3，仿真位置服务器使用大量的边信息分别设定以下四种定向攻击破坏用户的位 置隐私：

第一种是基于位置访问热度的攻击，

第二种是基于位置访问时间分布的攻击，

第三种是基于连续位置访问次序的攻击，

第四种是基于连续位置访问时间分布的攻击。

2.实验内容与结果

实验1，用本发明和现有Baseline方法、Caching方法和ICliqueCloak方法对位置服务器 使用的第一种攻击，进行位置隐私保护程度测试，测试结果如图3。

从图3可见，本发明和Caching方法明显优于其他两种方法。当位置数k＝10时，本发明 和Caching方法的平均熵均超过了2.10，而Baseline方法和ICliqueCloak方法的平均熵却不到 1.60，虽然Caching方法的结果优于本发明的结果大概3％，但是这是由于Caching方法着重 考虑了第一种攻击而造成的。

实验2，用本发明和现有Baseline方法、Caching方法和ICliqueCloak方法对位置服务器 使用的第二种攻击，进行位置隐私保护程度测试，测试结果如图4。

从图4可见，本发明的实验结果均优于其他现有方法。

实验3，用本发明和现有Baseline方法、Caching方法和ICliqueCloak方法对位置服务器 使用的第三种攻击，进行位置隐私保护程度测试，测试结果如图5。

从图5可见，本发明的实验结果均优于其他现有方法。

实验4，用本发明和现有Baseline方法、Caching方法和ICliqueCloak方法对位置服务器 使用的第四种攻击，进行位置隐私保护程度测试，测试结果如图6。

从图6可见，本发明和ICliqueCloak方法明显优于其他两种方法，虽然ICliqueCloak方法 的结果优于本发明的结果大概9％，但是ICliqueCloak方法却难以抵抗其他三种攻击。

综上所述，本发明能够更有效地同时抵抗这四种攻击，为用户提供更好的位置隐私保 护。