一种LBS中的轨迹隐私保护方法

摘要

本发明提出一种简单有效的轨迹隐私保护方法，属于信息安全技术领域，本方法计算成本较低，实用性强。该方法基于DLS算法并引入边轨迹概率这一定义，综合考虑了LBS单次请求和连续请求的情况，在单次请求的情况下能有效地保护用户的位置隐私，在连续请求的情况下能有效地保护用户的轨迹隐私。本发明所提供的方法解决了传统的K匿名技术用于LBS连续请求所带来的相关隐私安全问题。

说明书

技术领域

本发明属于信息安全技术领域，具体涉及一种LBS中的轨迹隐私保护方法。

背景技术

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

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$

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

在基于DLS算法的LBS系统中，LBS服务器需要统计出服务区域每个位置单元内用户发送 位置服务请求的历史概率，然后发布这份概率信息，这样每个用户都可以得到位置请求历史 概率。当用户需要某种位置服务时，用户首先利用GPS等定位装置获得自己的准确位置，根 据位置请求历史概率获得当前所处位置发送位置服务请求的历史概率，然后根据用户的匿名 度要求K，从位置地图中寻找出2K个与当前位置发送请求历史概率接近的候选位置，最后计 算从该2K个候选位置中选择的所有可能K-1个位置和用户真实位置构成的K个位置的熵值，选 择使熵值最大的K个位置作为用户向LBS服务器发送的位置信息。

但是，用DLS算法选择出的K个位置的概率集合的熵值H可能远小于理论上可实现的 最优的K个位置相应的概率集合的熵值。若熵值远小于最大值的时候，说明选择出的K-1个 假位置的某些位置概率和用户真实位置的概率相差甚远，这样轻而易举的就能排除掉那些概 率特小以及概率特别大的若干个位置，不利于用户端隐私的保护。

发明内容

本发明的目的是提供一种LBS中的轨迹隐私保护方法，本方法基于DLS算法并引入边 轨迹概率这一定义，综合考虑了LBS单次请求和连续请求的情况，在单次请求的情况下，该 方法能有效地保护用户的位置隐私；在连续请求的情况下能有效地保护用户的轨迹隐私。

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

一种LBS中的轨迹隐私保护方法，其流程如图1所示，具体包括以下步骤：

步骤1.初始化：用户端输入值包括：隐私度K，用户的真实位置d₁，区别是单次请求还 是连续请求的参量flag，请求相对时间t，当前匿名区域A(即当前请求假位置的选择范围)， 匿名阈值ε及距离阈值s_t，其中ε≥0.7×K，距离阈值s_t的大小与用户的请求速度及请求时间 的间隔相关，s_t指用户端可接受的在同一连续请求的相邻两次请求提交时所在位置的距离最 大值；用户端根据输入值判断是单次请求还是连续请求：flag＝0时为单次请求，flag＝1时为 连续请求；进一步的，若为连续请求，当前请求相对时间t＝0时说明当前请求为该连续请求 的第一次请求，t≠0则说明当前请求为连续请求中的非第一次请求；

若当前请求是单次请求或连续请求的第一次请求，则执行步骤2；若当前请求是连续请 求的非第一次请求，则执行步骤3；

步骤2.用户端根据输入值flag及请求相对时间t判断出本次请求是单次请求或是连续请 求的第一次请求后，向PIDS(pseudonym identity server)申请PID值，获得PID值后向LP (LBS provider)递交PID以验证其合法性，验证通过后如果是单次请求，则LP返回给用户 端历史点概率表P，若是连续请求的第一次请求，则LP返回用户端历史点概率表P和边轨迹 概率表E；用户端根据设置的匿名区域A，提取位于匿名区域A中的各位置单元的历史点概 率，并按其值由小至大的顺序汇于序列S中，执行步骤2-1；

步骤2-1.用户端从表P中提取出当前真实位置下的历史点概率p_L，在序列S中生成匿名 滑动窗序列W，所述序列W包含有K个元素且匿名滑动窗内概率点集合的匿名度D∈ [K-ε,K]，概率值p_L位于当前滑动窗内；将选定的匿名滑动窗内的K个位置点概率对应的K个 位置信息发送至LP完成位置请求；

若匿名滑动窗在滑动过程中使得概率值p_L脱离出滑动窗，或者滑动窗内的元素个数小于 K，则K匿名滑动窗序列W生成失败，执行步骤2-2；

步骤2-2.若匿名滑动窗序列生成失败，用户端将修改匿名区域A及K值，重新执行步 骤1发起请求；

步骤3.针对LBS服务区域内所划分的所有位置单元，每个位置单元区域的中心位置定 义为当前位置单元的顶点；若其中两顶点的距离不大于距离阈值s_t且两点在真实的地图上有 路径，则将两点连线连线，该连线成为该两顶点的边轨迹；每条边轨迹的两个顶点所处位置 单元的历史请求频率之和作为此边轨迹的请求频率，定义边轨迹概率为该边轨迹的频率值与 服务区域中所有边轨迹频率值之和的比值，把所有边轨迹概率值汇于边轨迹概率表E中；

用户端根据输入值flag及请求相对时间t判断出本次请求是连续请求的非第一次请求后， 令用户端当前需要提交的请求是该连续请求中的第i次，不失一般性地假设用户端第i-1次的 请求已经成功提交，且向LP提交申请时包含的K个位置坐标集合为L_i-1＝{d_i-1,1，d_i-1,2，…， d_i-1,K}，用户端根据边轨迹概率表E得出用户在提交第i-1次请求至第i次请求时间段的真实 轨迹的边轨迹概率q_L；

步骤3-1.用户端将当前时刻匿名区域A中，除当前真实位置点之外，在该连续请求的第 i-1次请求中已向LP提交过请求的共计m个位置点赋权值L.prior＝1，剩余位置点赋权值 L.prior＝0；针对所述权值L.prior＝1的每一个位置点，将其与集合L_i-1中所有位置点相连得l 条轨迹，剔除其中边轨迹长度大于距离阈值s_t或无法在真实地图上实现的轨迹后，从中选取 其边轨迹概率值与真实轨迹概率值q_L最接近的一个；由此得m个边轨迹概率及相应边轨迹；

步骤3-2.将当前时刻匿名区域A中，除去真实位置点及所述m个权值L.prior＝1的位置 点之外的剩余位置点的历史点概率汇于集合A'中；将第i-1次请求的位置集合L_i-1中，除去已 经选择出的真实边轨迹和m条边轨迹的始点之外剩余的K-m-1位置点汇于集合L'_i-1中，其中， 定义每一条边轨迹位中位于集合L_i-1中的端点为边轨迹始点，其另一端点为终点；

步骤3-3.针对位置点集合L'_i-1中的每一个位置点构建一个相应的轨迹概率集合T'，所述 轨迹概率集合具体构建方法如下：相应位置点指向集合A'中所有位置点而得的边轨迹概率值 中，剔除其中边轨迹长度大于距离阈值s_t或无法在真实地图上实现的轨迹所对应的边轨迹概 率后，即构成该点概率值的轨迹概率集合T'；从所构建的每一个边轨迹概率集合T'中随机选 取一个边轨迹概率值对应的边轨迹，共选取K-m-1条边轨迹且保证所有边轨迹的终点均不重 合，执行步骤3-4；

步骤3-4.把所选取的K-m-1个边轨迹概率与步骤3-1所得的m个轨迹概率值及用户端真 实轨迹概率结合，构成包含K个元素的轨迹概率集合T_f，计算集合T_f的匿名度D；

若匿名度D∈[K-ε,K]，则用户端将步骤3-3所选择的K-m-1条轨迹的终点位置与匿名区 域A中所述m个权值L.prior＝1的位置及用户端当前真实位置共K个位置点发送至LP服务 器，完成请求的发送；

若则将所选的K-m-1条边轨迹记的组合方式存档；则执行步骤3-5；

步骤3-5.从步骤3-3构建的轨迹概率集合T'中重新随机选取终点不重合的K-m-1条边轨 迹至所得K-m-1条边轨迹的组合方式尚未存档时止，执行步骤3-4；若穷尽K-m-1条轨迹的 所有组合方式后，依然无法使得匿名度D∈[K-ε,K]，则用户端设置请求相对时间t＝0，执行步 骤2，把此次请求作为连续请求的第一次请求继续处理。

本发明的有益效果是：

本发明提供的方法针对单次请求大大降低了时间复杂度，连续请求的时候从整体上保护 了用户的轨迹隐私安全。尤其在处理连续请求的时候，通过以下两点大大增强轨迹隐私安全： 1)在选择假轨迹的时候优先选择已经选过的位置，这样选择出的轨迹图就会有很多相交的位 置点，而不是相互独立的K条轨迹，从而攻击者猜测出用户真实的轨迹概率远远小于1/K；2) 当没有找到合适的K-1条假轨迹的时候，用户端会重置请求相对时间t＝0，并采用连续请求的 第一次请求的处理方法继续处理。

附图说明

图1为本发明提供的LBS中的轨迹隐私保护方法流程图。

具体实施方式

一种LBS中的轨迹隐私保护方法，其流程如图1所示，具体包括以下步骤：

步骤1.初始化：用户端输入值包括：隐私度K，用户的真实位置d₁，区别是单次请求还 是连续请求的参量flag，请求相对时间t，当前匿名区域A(即当前请求假位置的选择范围)， 匿名阈值ε及距离阈值s_t，其中ε≥0.7×K，距离阈值s_t的大小与用户的请求速度及请求时间 的间隔相关，s_t指用户端可接受的在同一连续请求的相邻两次请求提交时所在位置的距离最 大值；用户端根据输入值判断是单次请求还是连续请求：flag＝0时为单次请求，flag＝1时为 连续请求；进一步的，若为连续请求，当前请求相对时间t＝0时说明当前请求为该连续请求 的第一次请求，t≠0则说明当前请求为连续请求中的非第一次请求；

若当前请求是单次请求或连续请求的第一次请求，则执行步骤2启用KSW算法；若当 前请求是连续请求的非第一次请求，则执行步骤3启用CKAT算法；

步骤2.用户端根据输入值flag及请求相对时间t判断出本次请求是单次请求或是连续请 求的第一次请求后，向PIDS服务器申请PID值，获得PID值后向LP递交PID以验证其合 法性；验证通过后，如果是单次请求，则LP返回给用户端历史点概率表P，若是连续请求的 第一次请求，则LP返回用户端历史点概率表P和边轨迹概率表E；用户端根据设置的匿名区 域A，提取位于匿名区域A中的各位置单元的历史点概率，并按其值由小至大的顺序汇于序 列S中，执行步骤2-1；

步骤2-1.用户端从表P中提取出当前真实位置下的历史点概率p_L，并按以下方法生成匿 名滑动窗序列W，所述序列W包含K个元素：

(1)若匿名区域A中点概率值小于p_L的个数小于(K-1)/2，则将序列S中概率值最小的 K个点概率作为初始匿名滑动窗序列W，计算当前滑动窗内概率点集合的熵H及匿名度D； 若匿名度D∈[K-ε,K]，则选定当前滑动窗序列所包含的K个位置点概率，否则，将匿名滑动 窗在序列S中向右移动一个元素位置，直到滑动窗内的概率点集合的匿名度D∈[K-ε,K]且概 率值p_L位于当前滑动窗内时止，并选定当前滑动窗序列所包含的K个位置点概率；将选定的 匿名滑动窗内的K个位置点概率对应的、包含有用户端真实位置的K个位置信息发送至LP 完成位置请求；

根据信息论的相关定义，概率集合的熵值H及匿名度D由如下公式确定：

$H=-\underset{j=1}{\overset{K}{\Sigma }}\left[q_j{\log }_2{q}_j\right],q_j=\frac{p_j}{\underset{j=1}{\overset{K}{\Sigma }}{p}_j},$D＝2^H

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

当匿名滑动窗在滑动过程中使得概率值p_L脱离出匿名滑动窗，或者滑动窗内的元素个数 小于K时，则匿名滑动窗序列W生成失败，执行步骤2-2；

(2)若匿名区域A中点概率值大于p_L的个数小于(K-1)/2，则将序列S中概率值最大的 K个点概率作为初始匿名滑动窗序列W，计算当前滑动窗内概率点集合的熵H及匿名度D， 若匿名度D∈[K-ε，K]，则选定当前滑动窗序列所包含的K个位置点概率，否则，将匿名滑动 窗在序列S中向左移动一个元素位置，直到滑动窗内的概率点集合的匿名度D∈[K-ε,K]且概 率值p_L位于当前滑动窗内时止，并选定当前滑动窗序列包含的K个位置点概率；将选定的K 个位置点概率对应的、包含有用户端真实位置的K个位置信息发送至LP完成位置请求；

若滑动窗在滑动过程中使得概率值p_L脱离出滑动窗，或者滑动窗内的元素个数小于K， 则匿名滑动窗序列W生成失败，执行步骤2-2；

(3)若匿名区域A中点概率值小于或者大于p_L的个数均大于(K-1)/2，则在序列S中以 p_L为中心向其两边展开选择K个点概率作为初始匿名滑动窗序列，计算当前滑动窗内概率点 集合的熵H及匿名度D；若匿名度D∈[K-ε,K]，则选定当前匿名滑动窗序列包含的K个位置 点概率，否则，将匿名滑动窗在序列S中向右移动一个元素位置，直到滑动窗内的概率点集 合的匿名度D∈[K-ε,K]且概率值p_L位于当前滑动窗内时止，并选定当前滑动窗序列包含的K 个位置点概率；将选定的K个位置点概率对应的、包含有用户端真实位置的K个位置信息发 送至LP完成位置请求；

若滑动窗在滑动过程中使得概率值p_L脱离出滑动窗，或者滑动窗内的元素个数小于K， 则匿名滑动窗序列W生成失败，执行步骤2-2；

步骤2-2.若匿名滑动窗序列生成失败，用户端将修改匿名区域A及K值，重新执行步 骤1发起请求；

步骤3.针对LBS服务区域内所划分的所有位置单元，每个位置单元区域的中心位置定 义为当前位置单元的顶点；若其中两顶点的距离不大于距离阈值s_t且两点在真实的地图上有 路径，则将两点连线连线，该连线成为该两顶点的边轨迹；每条边轨迹的两个顶点所处位置 单元的历史请求频率之和作为此边轨迹的请求频率，定义边轨迹概率为该边轨迹的频率值与 服务区域中所有边轨迹频率值之和的比值，把所有边轨迹概率值汇于边轨迹概率表E中；

用户端根据输入值flag及请求相对时间t判断出本次请求是连续请求的非第一次请求后， 令用户端当前需要提交的请求是该连续请求中的第i次，不失一般性地假设用户端第i-1次的 请求已经成功提交，且向LP提交申请时包含的K个位置坐标集合为L_i-1＝{d_i-1,1，d_i-1,2，…， d_i-1,K}，用户端根据边轨迹概率表E得出用户在提交第i-1次请求至第i次请求时间段的真实 轨迹的边轨迹概率q_L；

步骤3-1.用户端将当前时刻匿名区域A中，除当前真实位置点之外，在该连续请求的第 i-1次请求中已向LP提交过请求的共计m个位置点赋权值L.prior＝1，剩余位置点赋权值 L.prior＝0；针对所述权值L.prior＝1的每一个位置点，将其与集合L_i-1中所有位置点相连得l 条轨迹，剔除其中边轨迹长度大于距离阈值s_t或无法在真实地图上实现的轨迹后，从中选取 其边轨迹概率值与真实轨迹概率值q_L最接近的一个；由此得m个边轨迹概率及相应边轨迹；

步骤3-2.将当前时刻匿名区域A中，除去真实位置点及所述m个权值L.prior＝1的位置 点之外的剩余位置点的历史点概率汇于集合A'中；将第i-1次请求的位置集合L_i-1中，除去已 经选择出的真实边轨迹和m条边轨迹的始点之外剩余的K-m-1位置点汇于集合L'_i-1中，其中， 定义每一条边轨迹位中位于集合L_i-1中的端点为边轨迹始点，其另一端点为终点；

步骤3-3.针对位置点集合L'_i-1中的每一个位置点构建一个相应的轨迹概率集合T'，所述 轨迹概率集合具体构建方法如下：相应位置点指向集合A'中所有位置点而得的边轨迹概率值 中，剔除其中边轨迹长度大于距离阈值s_t或无法在真实地图上实现的轨迹所对应的边轨迹概 率后，即构成该点概率值的轨迹概率集合T'；从所构建的每一个边轨迹概率集合T'中随机选 取一个边轨迹概率值对应的边轨迹，共选取K-m-1条边轨迹且保证每一条边轨迹的终点不重 合，执行步骤3-4；

步骤3-4.把所选取的K-m-1个边轨迹概率与步骤3-1所得的m个轨迹概率值及用户端真 实轨迹概率结合，构成包含K个元素的轨迹概率集合T_f，计算集合T_f的匿名度D；

若匿名度D∈[K-ε,K]，则用户端将步骤3-3所选择的K-m-1条轨迹的终点位置与匿名区 域A中所述m个权值L.prior＝1的位置及用户端当前真实位置共K个位置点发送至LP服务 器，完成请求的发送；

若则将所选的K-m-1条边轨迹记的组合方式存档；则执行步骤3-5；

步骤3-5.从步骤3-3构建的轨迹概率集合T'中重新随机选取终点不重合的K-m-1条边轨 迹至所得K-m-1条边轨迹的组合方式尚未存档时止，执行步骤3-4；若穷尽K-m-1条轨迹的 所有组合方式后，依然无法使得匿名度D∈[K-ε,K]，则用户端设置请求相对时间t＝0，执行步 骤2，把此次请求作为连续请求第一次请求继续处理。