随着移动通信和定位技术的不断发展，基于位置服务(location based services, LBSs)逐渐深入到人们的日常生活。然而人们在享受这种服务带来便利的同时，又不可避免地要面对隐私泄露问题。针对这一问题，研究者提出了以k-匿名^[1]、l-多样性^[2]、用户协作^[3]、锚点^[4]和PIR^[5]等为主的基于快照服务的隐私保护方法。但是这些方法均不能有效地保护连续位置服务中的轨迹隐私。针对这一情况，研究者分别从单元泛化^[6]、轨迹聚类^[7]和全局轨迹相似^[8]等方面提出轨迹隐私保护方法。Gao等详细分析并总结了这些方法，发现它们更适合对已生成的轨迹加以保护，并不能有效的保护实时连续位置服务中的用户隐私^[7]。学者又陆续提出了基于匿名^[9-13]和mix-zone^[14-16]的隐私保护方法。尽管这些实时的隐私保护方法能够有效保护用户的位置，但是在掌握用户移动方式的情况下，攻击者还是能够通过产生的轨迹差异识别出用户的真实轨迹，进而获得用户隐私。因此，本文基于轨迹匿名和实时连续位置服务隐私保护的特点，提出了一种相似轨迹实时生成方法，通过实时生成相似轨迹完成轨迹匿名，弥补轨迹隐私保护方法无法适应实时服务，以及实时连续服务隐私保护方法无法保障轨迹匿名的不足。

1 隐私保护系统架构

由于移动通信设备计算能力有限，本文采用三层中心服务器架构。如图 1所示，该架构包含3个实体：移动用户(mobile user, U)，匿名服务器(anonymous servers, AS)，服务提供商(location service provider, LSP)。U携带定位设备(例如：智能手机、GPS定位模块)，能够精确定位自身位置并与LSP交互，进而享受位置依赖服务。但是，U的通信和计算能力有限。AS负责计算相似轨迹位置，具有较强的计算和数据处理能力。LSP能够为User或AS提供服务，具有极强的数据分析和处理能力。本文假设U和AS是可信的，而LSP是半可信的，即LSP在严格执行协议和算法的前提下，同时使用收集到的位置信息和背景知识推断U的敏感信息，甚至LSP可能将U的敏感信息出卖给不友好的第三方。

定义1 连续位置服务是指User向LSP发起多次请求，并获得连续服务反馈的过程。这些请求可表示为Q=(ID, L_i, I, P)。其中：ID表示用户的身份标识；L_i=(x_i，y_i)表示查询设备所处位置；I表示时间间隔；P表示查询兴趣点，如：餐厅、医院等。

定义2 轨迹差异识别攻击是指攻击者通过获取用户的移动速度、移动方向等移动信息，比较识别出移动用户产生轨迹的攻击方法。其攻击成功概率可表示为

${P_s} = {\rm{max}}\sum\limits_{i = 1}^k {{\rm{sim}}} ({t_i},{t_m})$

式中：t_m为攻击者根据移动信息建立的轨迹，sim表示轨迹相似性。

2 相似轨迹实时生成方法

相似轨迹实时生成方法的基本原理就是通过实时产生相似的虚假轨迹完成轨迹匿名。为实现相似轨迹匿名，需要经过初始匿名位置选择、相似轨迹位置计算和生成位置筛选等3个步骤。其中初始匿名需选择分布在多个兴趣点区域中的位置，以降低产生伴随轨迹的概率。

定义3 轨迹r-匿名是指LSP同时获得包括真实轨迹t在内的至少r条相似轨迹，这些轨迹使得LSP无法通过轨迹长度和轨迹方向之间的差异，识别出t的隐私保护过程。

定义4 伴随轨迹是指用户行进过程中经过共同的兴趣点，这些兴趣点可被校正整合为同一轨迹的r条相似轨迹。

定义5 相似轨迹位置区域是一个相似位置集合，是在方向偏差和相似度阈值内，以二元二次方程4个根为顶点建立的区域。连接前次匿名位置与该区域内任一位置可建立相似轨迹。

定义6 不可到达位置是指生成的虚假位置l′∈T，其中T表示LSP获得的所有历史轨迹集合。

2.1 相似轨迹位置计算

通过计算相似轨迹位置，获得满足生成相似轨迹的位置集合，并经过位置筛选建立相似轨迹。关于相似轨迹位置计算，本文借鉴Gao等关于相似轨迹区段计算的基本思想^[7]，利用平行距离量化轨迹长度，夹角距离量化方向，使用两者之和来量化相似程度。在生成位置的过程中，根据初始匿名位置，计算至少r-1个虚假轨迹来完成轨迹匿名。以两条轨迹为例阐述相似轨迹生成方法。

假设用户A和虚假用户B分别以p_a和p_b为初始位置建立匿名组，若要计算B的虚假位置p_b+1，且连接用户A、B的相邻查询位置能够产生相似轨迹，需要通过p_a、p_b和A的后续查询位置p_a+1使用平行距离和夹角距离建立方程，进而计算得出p_b+1的位置。令L_a和L_b是分别以p_a、p_a+1和p_b、p_b+1为两端位置的轨迹长度，θ表示用户制定的两条轨迹之间存在的夹角阈值。由于p_a+1已知，通过式(1)、(2) 联立建立关于p_b+1的二元二次方程，从而计算获得p_b+1。获取相似轨迹位置区域计算所需要的平行距离和夹角距离公式可分别表示为

${d_{||}} = \left\| {{\mathit{\boldsymbol{p}}_{a + 1}} - {\mathit{\boldsymbol{p}}_a}} \right\| - \left\| {{\mathit{\boldsymbol{p}}_{b + 1}} - {\mathit{\boldsymbol{p}}_b}} \right\|$

(1)

${d_\theta } = {\rm{sin}}\left( {{\rm{arccos}}\frac{{\mathit{\boldsymbol{A}} \cdot \mathit{\boldsymbol{B}}}}{{\left\| {{\mathit{\boldsymbol{p}}_{a + 1}} - {\mathit{\boldsymbol{p}}_a}} \right\| - \left\| {{\mathit{\boldsymbol{p}}_{b + 1}} - {\mathit{\boldsymbol{p}}_b}} \right\|}}} \right)$

(2)

式中：A, B表示用户A、B的移动向量；ω_‖、ω_θ分别代表平行距离和夹角距离的权重，由于两个距离公式均对轨迹相似程度产生影响，因此ω_‖, 、ω_θ的默认值设定为1。其中两条轨迹之间的相似程度可表示为

${\rm{sim}}\left( {\mathit{\boldsymbol{A}},\mathit{\boldsymbol{B}}} \right) = \frac{1}{{{\rm{1 + Dist}}({L_a},{L_b})}}0 ＜ {\rm{sim}}\left( {\mathit{\boldsymbol{A}},\mathit{\boldsymbol{B}}} \right) \le 1$

(3)

两个轨迹区段之间的轨迹距离可表示为

${\rm{Dist}}({L_a},{L_b}) = {\omega _{||}}{d_{||}} + {\omega _\theta }{d_\theta }$

(4)

2.2 筛选生成位置

为降低攻击者识别虚假位置的概率，需对生成的轨迹相似位置加以筛选。本文主要针对生成位置的实际可到达性加以描述。如图 2所示的虚假用户U，经过计算后可获得由A、B、C 3个位置组成的相似轨迹位置区域。由于U与A之间存在建筑物阻挡，U与C之间存在河流阻挡。根据可到达情况，AS只能选择B作为匿名位置，建立匿名组。

综合初始匿名、相似轨迹位置计算和筛选生成位置的思想，设计了相似轨迹生成算法。

算法1  相似轨迹生成算法

输入：用户当前查询位置p_i+1与前次位置p_i以及虚假前次位置p_j

输出：p_j+1位置集合，该集合中位置满足轨迹匿名

1) Procedure:AS收到请求Q;

2) 随机选择2r-1个位于不同兴趣点的匿名位置构成集合B；

3) hreshold_sim=min_sim(A, B); threshold_θ=Max_θ;  //设置相似性和夹角阈值；

4) P_s=null;   //目标位置集为空；

5) for every B //对于每个虚假位置；

6) Dist (A, B)=(1-threshold_sim)/threshold_sim;

7) A·B=dot(‖p_i+1-p_i‖, ‖p_j+1-p_jV);

8) d_θ=threshold_θ=${\rm{sin}}\left( {{\rm{arccos}}\frac{{\mathit{\boldsymbol{A}} \cdot \mathit{\boldsymbol{B}}}}{{\left\| {{\mathit{\boldsymbol{p}}_{i + 1}} - {\mathit{\boldsymbol{p}}_i}} \right\| - \left\| {{\mathit{\boldsymbol{p}}_{j + 1}} - {\mathit{\boldsymbol{p}}_j}} \right\|}}} \right)$; //夹角距离；

9) d_‖=Dist(A, B)-threshold_θ=‖p_i+1-p_i‖-‖p_j+1-p_j‖; //平行距离；

10) p_j+1=solve (d_‖, d_θ)); //解关于p_j+1二元二次方程；

11) 使用p_j+1建立位置相似区域；

12) if当前区域可从p_j到达；

13) 随机选择任一位置作为p_c;

14) S=S+ p_c;

15) else

16) break; //匿名失败

17) end if

18) End

19) End Procedure

算法1根据每一个参与前次匿名的位置，计算所得虚假位置保存在S中，在连续匿名过程中重复3)~19)，计算获得能够产生相似轨迹的位置，连接后获得相似的匿名轨迹，最终实现轨迹r-匿名。

3 性能分析与实验验证 3.1 性能分析

由于攻击者是根据移动用户轨迹差异识别目标用户的，其成功概率是${P_s} = {\rm{max}}\sum\limits_{i = 1}^k {{\rm{sim}}} ({t_i},{t_M})$。本文提出的思想是泛化轨迹性，使得对于轨迹集合T中的任一轨迹t与其他r-1条轨迹的相似性相同。因此攻击者的攻击行为可认为是在众多用户中识别出待攻击用户。假设当前范围内存在任意两个移动用户u_i和u_j，经过计算生成两条相似轨迹t_i和t_j。由于轨迹相似，可知攻击者通过轨迹差异识别攻击成功分辨出两条轨迹的概率分别为P_sⁱ和P_s^j，于是有

$P_s^i = {\rm{max}}\sum\limits_{i = 1}^k {{\rm{sim}}({t_i},{t_m})} = {\rm{max}}\sum\limits_{j = 1}^k {{\rm{sim}}({t_j},{t_m})} = P_s^j$

(5)

由此可得u_i=u_j，即用户u_i和u_j无法区分，进而可知攻击者通过轨迹差异识别攻击无法在r条相似轨迹中准确识别出待攻击用户。

为实现轨迹r-匿名，需要在每个连续查询间隔内生成r条相似轨迹。在最好的情况下，其时间复杂度为O(r-1)。若每个生成位置均不可到达则需调整相似参数，此时算法的执行时间复杂度为2O(r-1)。由此，可得出算法1的时间复杂度为O(sum)=O(r-1)+2O(r-1)=O(r-1)。综上，可以认为该算法的时间复杂度取决于用户设定的轨迹匿名阈值和后续相似位置的可到达性。由于相似轨迹实时生成方法是基于欧氏空间提出，可认为在多数情况下能够找到可达的相似轨迹位置。因此，在一般情况下，该算法的时间复杂度为O(r)。

3.2 环境配置

本实验中所涉及方法是在Windows 7系统上使用Matlab 7来进行模拟的，运行环境为1.70GHz Intel Core i5，内存4 GB。实验数据采用BerlinMOD Data Set提供的真实位置数据，并随机选择城市中心位置进行实验验证。同时，本文加入以下方法进行对比：LTPPM^[10]、EGCA^[11]和C_LAPPINQ^[13]，其中LTPPM主要针对轨迹差异识别攻击。表 1为实验中采用的相关参数阈值。

3.3 结果比较

如图 3所示，本文提出方法所产生的轨迹与基轨迹之间极为相似，可以实现轨迹匿名。

通常，在轨迹隐私保护中需降低伴随轨迹产生率，以防止攻击者通过共同的兴趣点识别出真实轨迹。从图 4中可以看到，随着匿名值增大，各算法产生伴随轨迹的概率逐渐增加。但本文所提出的方法由于对初始位置加以限制，其伴随轨迹产生率要远低于其他算法。其他算法中LTPPM相对较好，这是由于部分相距较远的协作用户降低了伴随轨迹的产生概率。最后，C_LAPPINQ和EGCA由于随机选择匿名用户，使得伴随轨迹的产生率明显高于另2种算法。

从图 5中可以看到各算法随匿名值增大，匿名用户被攻击者识别的概率逐渐增加。本文所提出的算法由于对生成的虚假位置进行筛选，降低了攻击者成功剔除匿名位置的概率，因而与其他算法相比具有较低的识别率，进一步保护了用户的位置轨迹隐私。EGCA由于随机选择匿名用户，使得其匿名用户识别率最高。C_LAPPINQ和LTPPM由于匿名用户变更以及真实轨迹被匿名轨迹所围绕，使得其识别率要高于本文算法。

在执行效率的对比实验中，根据匿名值变化，查看各算法在执行时间上的差异。同时，查看在连续多次执行过程中，相同匿名值限定下的连续执行时间。最后比较各算法的匿名成功率。下面以3次连续查询为例，查看各算法随匿名值增大导致的执行时间变化。

从图 6中可以看出，直接选择用户匿名的C_LAPPINQ和EGCA方法其执行时间较短，且C_LAPPINQ由于采用预计算的方式，其执行时间最短，但这两种方法均无法有效抵抗轨迹差异识别攻击。LTPPM通过用户协作建立相似轨迹来抵抗轨迹差异识别攻击，该方法既涉及到寻找协作用户，又需对匿名轨迹进行筛选，因此其时间效率受匿名值变化影响最大。本文方法仅处理相似轨迹位置，无需寻找协作用户，与LTPPM相比具有更好的执行效率。

在图 7中可以看到，相同参数连续运行过程中各算法的执行时间。在这些算法中，本文所提出的算法在计算出匿名位置之后，需进行相似轨迹位置筛选，其执行时间要高于直接选择用户进行匿名的C_LAPPINQ和EGCA，但低于查找协作用户建立相似轨迹的隐私保护算法LTPPM。

从图 8中可以看到各算法的匿名成功率。EGCA由于使用单匿名框，其匿名成功率受匿名次数影响较小。LTPPM因需要连续寻找能够参与匿名的协作用户，其匿名成功率急速降低。本文算法同样因为生成位置筛选，使得随连续匿名申请次数增加导致成功率逐渐下降。C_LAPPINQ方法由于采用预计算，其成功率要好于LTPPM与本文方法。

综上，从两组实验的对比中可以看出，本文所提出的相似轨迹实时生成方法尽管在执行效率上优势并不明显(如图 6~8)，但与同类方法相对比该方法能够更好地抵抗轨迹差异识别攻击(如图 4、5)。

4 结论

1) 本文分析了攻击者通过轨迹差异获取用户隐私的攻击行为，利用攻击成功率量化了这种攻击行为。

2) 针对这种攻击行为基于轨迹相似性计算的思想，提出了相似轨迹实时生成方法，利用轨迹方向、轨迹长度的量化以及位置筛选实现了连续位置服务过程中的位置隐私保护。

3) 本文通过性能分析和实验结果比较进一步证明该方法在增强用户位置轨迹隐私的同时具有较好的执行效率。今后的工作将在如何降低AS对执行效率的影响以及提高匿名成功率等方面展开。