图 1为基于CCRS的轨迹隐私保护模型，它主要包括用户、匿名器和LBS服务器3类实体，其具体工作过程为：1)用户发送查询时，先确定查询范围内包含的各网格单元标识，并在用户端缓存中查找。如果能找到这些网格单元标识及包含的候选结果集，则返回给用户；否则将未查找到的网格单元标识发送给匿名器。2)匿名器收到用户的这些网格单元标识后，在其缓存中查找匹配。如果匿名器缓存有这些网格单元标识及包含的候选结果集，则返回查询结果；否则基于Markov模型的移动位置预测方法，在匿名器中形成k-匿名域后再发送给LSB服务器查询。3) LBS服务器根据匿名域范围，查询各网格单元内包含的POIs，并将各网格单元标识及包含的候选结果集返回给匿名器。4)匿名器将各网格单元标识及包含的候选结果集更新到缓存，并与用户需要查询的网格单元标识进行匹配。如果相等，则将该网格单元标识及包含的候选结果集发送给用户。5)用户将查询匹配得到的网格单元标识及包含的候选结果集更新到缓存，并将得到的匹配候选结果集进行过滤求精，最后得到精确结果。

图  1  基于CCRS的轨迹隐私保护模型

定义1 缓存隐私度量：根据信息熵对用户位置隐私度的度量，基于缓存的隐私度量可表示为^[13-14]：

式中， $\left| {{G_{{\rm{cache}}}}} \right|$ 表示缓存中能找到的网格单元标识数； $\left| {{G_{{\rm{server}}}}} \right|$ 表示需向LBS服务器查询的网格单元标识数； ${m^2}$ 表示网格单元数目； $H(g)$ 表示真实网格单元标识在查询 $g$ 中的不确定性。在查询过程中，网格单元标识的命中率可表示为：

式(1)可变换为：

可以看出，通过提高缓存命中率可增强用户的位置隐私度。

用户的移动轨迹可以是 $n$ 阶的马尔科夫链，可表示为具有时序性的移动轨迹点序列，每个移动轨迹点 ${p_i}$ 的所处移动位置 ${l_i}$ 只与其前面的n个移动轨迹点 $\left\{ {{p_{i - n + 1}}, {p_{i - n + 2}}, \cdots, {p_{i - 1}}, {p_i}} \right\}$ 相关^[15]：

式中， ${p_i}l = {l_i}$ 表示第 $i$ 次移动轨迹点 ${p_i}$ 的位置是 ${l_i}$ 。

对于前n个移动轨迹点组成的用户轨迹，可预测求解具有最大概率的移动位置：

式中， ${l_p}$ 表示用户移动的预测位置。当有n个候选移动位置时，通过计算所有移动位置 ${l_k}$ 是目标预测位置的概率，以预测用户真实的目标位置 ${l_p}$ 。

图 2所示为基于CCRS的轨迹隐私保护工作过程，主要分为5个步骤，下面将分别进行介绍。

图  2  基于CCRS的轨迹隐私保护工作过程

用户先将查询范围内网格结构定义为：

式中， $({x_1}, {y_1})$ 、 $({x_{\rm{2}}}, {y_{\rm{2}}})$ 表示能确定用户查询范围的两个位置坐标； $m \times m$ 表示划分的网格数目。各网格单元都有唯一的标识 $({x_i}, {y_j})$ ，可表示为：

式中， ${c_i}$ 、 ${r_j}$ 分别为列、行标识， $1 \le i, j \le m$ ； $({x_i}, {y_i})$ 为查询范围内的任意点。

用户根据查询半径 $R$ ，确定需要查询的网格单元标识，并在用户端缓存中查找。如果能找到所有网格单元标识及包含的候选结果集，则直接对候选结果集进行求精，得到精确结果，否则将未找到的网格单元标识形成标识集 ${I_h}$ 。

式中， $n$ 为移动轨迹上的连续查询点次数。最后用户将需要查询的网格单元标识集 ${I_h}$ 、随机生成的密钥 ${K_u}$ 、用户当前位置 ${L_h}$ 和运动方向 ${D_h}$ 、网格结构 ${\rm{Grids}}$ 以及查询内容 ${\rm{Content}}$ 组成用户的请求消息，并使用匿名器的公钥 ${\rm{P}}{{\rm{K}}_a}$ 对请求消息进行非对称加密形成 ${\rm{MS}}{{\rm{G}}_{ua}}$ 发送给匿名器。

当匿名器收到 ${\rm{MS}}{{\rm{G}}_{ua}}$ 后，先用自己的私钥 $S{K_a}$ 对 ${\rm{MS}}{{\rm{G}}_{ua}}$ 解密，获得标识集 ${I_h}$ ，然后在匿名器缓存中查找。如果能找到网格单元标识及包含的候选结果集，则返回给用户端。否则匿名器对未查找到的网格单元标识进行匿名处理。匿名时采用基于Markov模型的移动位置预测方法，预测用户在移动过程中的下一个查询位置。最后根据该预测位置形成匿名域，以提高下次查询的命中率。

基于Markov模型的移动位置预测主要从移动用户历史轨迹中获取一些有意义的物理位置，并通过统计概率模型来预测该用户的移动位置。本文利用文献[16]中提出的基于时间距离约束的网格聚类算法，先将用户的历史轨迹数据映射到定义的网格，获得所有停留点集合 ${\rm{SP}} = \left\{ {{\rm{s}}{{\rm{p}}_1}, {\rm{s}}{{\rm{p}}_2}, \cdots, {\rm{s}}{{\rm{p}}_n}} \right\}$ ，并以sp作为输入，通过聚类方法聚集成停留区域集合 $R = \left\{ {{r_1}, {r_2}, \cdots, {r_N}} \right\}$ ，其中 ${r_i}$ 是一个停留点 ${\rm{s}}{{\rm{p}}_i}$ 的集合。然后可将用户移动轨迹表示为连续的轨迹序列 ${\rm{Tra}} = \left\langle {{r_i}, \cdots, {r_j}} \right\rangle $ ( ${r_i}, {r_j} \in R$ )。因此，通过输入用户每条历史轨迹序列，可获得移动对象的历史停留区域序列 ${\rm{Tra}} = \left\{ {{r_1}, {r_2}, \cdots, {r_N}} \right\}$ ，它也可表示为状态变量序列 $X = \left\{ {{x_1}, {x_2}, \cdots, {x_N}} \right\}$ ，且每个停留区域对应一个状态。如果移动对象潜在的停留区域数目为 $m$ ，则它的状态空间集合为 $S = \left\langle {{s_1}, {s_2}, \cdots, {s_m}} \right\rangle $ 。最后用户根据这些状态，建立用户的状态转移矩阵 ${\bf{Pr}} = {\bf{Pr}}(\mathit{\boldsymbol{R}}[i], \mathit{\boldsymbol{R}}[j])$ 。根据文献[17]基于运动趋势的移动对象预测算法，对每一个停留区域计算其移动概率，取其概率值最大的为 ${R_p}$ ，并根据如下公式计算预测移动位置 ${l_p}$ ：

当获得移动用户下一个查询位置 ${l_p}$ 后，匿名器根据用户需要查询的网格单元标识集 ${I_h}$ 和网格结构 ${\rm{Grids}}$ ，选择 $k$ 个用户所在的网格单元形成匿名区域 ${\rm{Region}}$ 。最后匿名器将匿名域 ${\rm{Region}}$ 、网格结构 ${\rm{Grids}}$ 以及查询内容 ${\rm{Content}}$ 组成新的查询请求消息，并使用LBS服务器公钥 ${\rm{P}}{{\rm{K}}_S}$ 对它们进行非对称加密形成 ${\rm{MS}}{{\rm{G}}_{as}}$ ，再发送给LBS服务器。

LBS服务器收到请求消息 ${\rm{MS}}{{\rm{G}}_{as}}$ 后，先使用自己的私钥 ${\rm{S}}{{\rm{K}}_S}$ 解密 ${\rm{MS}}{{\rm{G}}_{as}}$ ，获得 ${\rm{Grids}}$ 、 ${\rm{Region}}$ 和 ${\rm{Content}}$ 。然后LBS服务器根据 ${\rm{Grids}}$ 中 $({x_1}, {y_1})$ 、 $({x_{\rm{2}}}, {y_{\rm{2}}})$ 和 $m$ 恢复用户指定的网格结构，并根据查询内容 ${\rm{Content}}$ 搜索匿名域 ${\rm{Region}}$ 中网格单元包含的POIs，得到 $g$ 个POIs。如果第 $j$ 个POI的位置为 $({x_i}, {y_j})$ $(1 \le i, j \le g)$ ，则可计算它所在的网格单元标识，并可获得每个网格单元标识 $({c_z}, {r_t})$ 包含的兴趣点集。最后，LBS服务器将这些查询到的兴趣点网格集 ${\varphi _r}$ ，形成候选结果集 ${\rm{MSG}}$ ，用匿名器的公钥 ${\rm{P}}{{\rm{K}}_a}$ 进行加密形成消息 ${\rm{MS}}{{\rm{G}}_{sa}}$ 返回给匿名器：

首先，匿名器解密 ${\rm{MS}}{{\rm{G}}_{sa}}$ ，得到匿名域中每个网格单元标识对应的POIs，并将它更新到匿名器缓存。匿名器更新时，根据用户当前位置 ${L_h}$ 和运动方向 ${D_h}$ ，需替换与用户运动方向相反、且距离移动用户下一个目标预测位置 ${l_p}$ 最远的POIs。然后，匿名器将查询到的网格单元标识集 ${\varphi _r}$ 与用户需要查询区域的网格单元标识 ${I_h}$ 进行匹配，找到用户需要查询的网格单元标识及对应的POIs。最后，匿名器使用用户的密钥 ${K_u}$ ，对查询到的网格单元标识及包含的POIs进行对称加密，并组成 ${\rm{MS}}{{\rm{G}}_{au}}$ 返回给查询用户：

用户收到 ${\rm{MS}}{{\rm{G}}_{au}}$ 后，首先用密钥 ${K_u}$ 解密 ${\rm{MS}}{{\rm{G}}_{au}}$ 获得所需查询网格单元中的每个POI的精确位置。然后，用户将得到的网格单元标识及包含的POIs更新到用户端缓存。最后，用户计算在自己查询区域之内的POIs，得到精确查询结果。

在用户初次查询时，因缓存中没有候选结果集，用户发送的查询需经过匿名器匿名后，再转发给LBS服务器查询，LBS服务器收到的查询请求为 ${\rm{MS}}{{\rm{G}}_{as}}$ 。 ${\rm{MS}}{{\rm{G}}_{as}}$ 中包括匿名域 ${\rm{Region}}$ 、查询内容 ${\rm{Content}}$ 以及网格结构 ${\rm{Grids}}$ ，从这些信息中LBS服务器不能获得用户的真实位置。经匿名后的 ${\rm{Region}}$ 中，它至少包含 $k$ 个用户，LBS服务器能成功猜到是指定用户的概率只有 ${\text{1}}/{k}\; $ 。

在用户移动轨迹上后续点的查询过程中，用户可以通过缓存直接得到部分或全部查询结果。如果用户直接从缓存中取得全部结果，他将不必与LBS服务器进行交互，因此，LBS服务器不能获得用户的任何信息。否则，在缓存中没有查找到的网格单元将形成匿名域，再发送给LBS服务器查询，但该匿名域不一定包含用户的真实位置。所以，LSP通过这些连续查询数据不能获得指定的用户和真实位置，CCRS方法能抵制LSP的连续查询推断攻击。

当用户发送请求消息给匿名器时，用匿名器公钥 ${\rm{P}}{{\rm{K}}_a}$ 对 ${\rm{MS}}{{\rm{G}}_{ua}}$ 进行了非对称加密，侦听者没有匿名器私钥 ${\rm{S}}{{\rm{K}}_a}$ ，不能解密 ${\rm{MS}}{{\rm{G}}_{ua}}$ 得到有用信息。当匿名器将请求消息转发给LBS服务器时，LBS的公钥 ${\rm{P}}{{\rm{K}}_s}$ 对 ${\rm{MS}}{{\rm{G}}_{ua}}$ 进行了非对称加密，同样侦听者没有LBS的私钥 ${\rm{S}}{{\rm{K}}_S}$ ，不能解密 ${\rm{MS}}{{\rm{G}}_{as}}$ 得到有用信息。在候选结果返回用户的过程中，非对称加密函数 $E(\cdot)$ 和对称加密函数 ${\rm{En}}(\cdot)$ 分别对 ${\rm{MS}}{{\rm{G}}_{sa}}$ 、 ${\rm{MS}}{{\rm{G}}_{au}}$ 进行了加密，侦听者没有匿名器的私钥 ${\rm{S}}{{\rm{K}}_a}$ 和用户密钥 ${K_u}$ ，不能解密 ${\rm{MS}}{{\rm{G}}_{sa}}$ 和 ${\rm{MS}}{{\rm{G}}_{au}}$ 。因此，侦听者既不能获得任何有用的信息，更不能得到用户的精确位置，CCRS方法能抵制侦听者的攻击。

实验采用Brinkhoff移动对象生成器^[18]，输入德国奥尔登堡市交通网络图，并生成10 000个移动对象。实验随机选取Bob的移动轨迹作为实验对象，图 3为移动用户Bob的运动轨迹，表 1为实验参数设置。实验运行平台为Windows 7操作系统，Intel(R) Core(TM) i5-4590处理器、4 GB内存。

图  3  移动用户Bob的运动轨迹

当 $n = 30$ 时，对比CCRS中使用Markov与No Markov方案对两级缓存平均命中率的影响。由图 4可知，通过基于Markov模型的移动位置预测进行k-匿名的CCRS比没有使用Markov模型进行k-匿名的缓存命中率要高，同时缓存命中率随着匿名度k的增大而增大。因为通过基于Markov模型移动位置预测方法，可以预测到移动用户的下一个移动点位置，然后根据该位置选择周围 $k$ 个用户所在的网格单元作为匿名域，可以预先将下一点需要查询的网格单元提前进行查询，相对于没有Markov的方法，使用Markov的CCRS方法能提高缓存的命中率。同时匿名度越高，相应缓存中的网格单元标识及包含的候选结果集就越多，在缓存中能找到用户需要查询的网格单元标识的可能性就越大，相应的缓存命中率就高。因此，匿名度k越大，缓存命中率就越高。

图  4  缓存平均命中率对比

图 5为LBS服务器的性能对比图。当 $k = 30$ 时，对比CCRS与Gedik^[9]、Hwang^[10]方案对LBS服务器性能的影响。由图 5可知，在LBS服务器时间开销和通信开销上，随着 $n$ 的增大，CCRS相对于Gedik、Hwang方案优势越大。因为Gedik、Hwang方案中用户发送的查询经匿名器匿名后，都需在LBS服务器中对整个匿名域进行查询，并将查询获得的候选结果集返回给用户。在CCRS方案中，用户端和匿名器使用二级缓存机制，用户发送查询时，首先在二级缓存中查询，只有在缓存中找不到需要查询的网格单元标识时，再经匿名后到LBS服务器中查询，这样有效减少了LBS服务器查询的次数和通信开销。因此，在LBS服务器的时间开销和通信开销上，CCRS方案相对于Gedik、Hwang方案有较大的优势。

图  5  LBS服务器的性能对比

本文提出了一种基于缓存候选结果集的轨迹隐私保护方法，利用缓存思想和基于Markov移动位置预测进行k-匿名的技术，减少用户与LBS服务之间的交互，提高缓存的命中率和用户的轨迹隐私。安全分析表明该方法能抵制连续查询和侦听者的攻击。实验结果显示，与Gedik、Hwang方案比较，CCRS方法能减少LBS服务器的开销。但CCRS方法只考虑用网格单元内用户的数目形成k-匿名域，因此在下一步工作中，将会考虑用户发送查询的概率形成匿名域，以进一步提高用户的位置隐私。