轨迹发布中基于时空关联性的假轨迹隐私保护方案

雷凯跃，李兴华，刘海，裴卓雄，马建峰，李晖

（西安电子科技大学网络与信息安全学院，陕西 西安 710071）

轨迹发布中基于时空关联性的假轨迹隐私保护方案

雷凯跃，李兴华，刘海，裴卓雄，马建峰，李晖

（西安电子科技大学网络与信息安全学院，陕西 西安 710071）

从轨迹的整体方向、轨迹中相邻位置的时间可达及移动距离对单条轨迹中相邻位置间的时空关联性和轨迹间的相似性进行分析，提出了一种基于时空关联性的假轨迹隐私保护方案。安全性分析表明所提方案能有效混淆假轨迹与真实轨迹，避免攻击者识别出假轨迹。大量实验表明，所提方案在仅需较少计算时间的同时，能确保生成的假轨迹与真实轨迹具有相似性，从而有效保护轨迹发布中用户的轨迹隐私。

轨迹发布；隐私保护；假轨迹；时空关联性；轨迹泄露

1 引言

基于位置的服务(LBS,location-based service)[1,2]是指与用户指定地理位置密切相关的信息服务，如用户可利用Google Latitude等应用查询指定位置的美食、酒店等信息。随着LBS的广泛应用，用户不再局限于享受实时的查询服务，而是更广泛地应用由位置序列构成的轨迹发布[3,4]，如物流公司保存自己的运输轨迹，用于分析其运输路线是否合理；市政部门收集出租车运行轨迹用于路网建设或交通管理。

然而，人们在享受便捷的LBS的同时，也面临着隐私被窃取的风险。用户发布的轨迹中往往包含大量的时空信息。这就使恶意攻击者可通过分析这些时空信息，结合自己掌握的背景知识，非法获取用户的兴趣爱好、宗教信仰、身体状况、家庭及工作地址等个人隐私，甚至给用户带来经济损失或威胁用户的人身安全。因此，轨迹发布中的隐私保护受到了国内外学者的广泛关注。

现有的轨迹发布隐私保护方法可分为3种：假轨迹[5～8]、轨迹k-匿名[9～11]和轨迹抑制[12,13]。与后2种方法相比，假轨迹隐私保护方法无需可信第三方，且能保留完整的轨迹信息，因此，常被用于保护轨迹发布中的用户轨迹隐私。

然而，现有的假轨迹隐私保护方案在假轨迹的生成过程中，不仅未结合实际的地貌、路况等因素考虑单条轨迹中相邻位置间的时空关联性，也忽略了轨迹之间的时空关联性。因此，若用户采用现有假轨迹方案保护自己的真实轨迹，攻击者就能利用单条轨迹中相邻位置间的时空关联性和轨迹之间的时空关联性，识别出某些假轨迹，甚至直接获取用户的真实轨迹。如图1所示，若在请求时间间隔内不可达，则攻击者就能以较大概率识别出轨迹1是假轨迹；轨迹3的整体移动方向与轨迹1和轨迹2相反，攻击者也会以较大概率推测出轨迹3是假轨迹。此外，由于C1的出入度为4，攻击者就可能会将C1作为移动枢纽，从而将轨迹2识别为用户的真实轨迹。本文也通过大量的实验证明了现有假轨迹隐私保护方案仅能以不高于15%的成功率保护用户的真实轨迹。

图1 轨迹关系

针对上述问题，本文从轨迹的整体方向、轨迹中相邻位置的时间可达及移动距离对单条轨迹中相邻位置间的时空关联性和轨迹间的时空关联性进行分析，提出了一个假轨迹隐私保护方案。本文的主要贡献如下。

1) 针对现有的假轨迹隐私保护方法，利用时间可达性和出入度提出了一个假轨迹识别方案。大量实验表明，所提假轨迹识别方案在误判率仅为23%的情况下，能够识别出85%的假轨迹。这证明了现有假轨迹方案并不能有效保护用户的轨迹隐私。

2) 从整体和局部的角度考虑了单条轨迹中相邻位置间的时空关联性以及轨迹之间的时空关联性，提出了一个假轨迹隐私保护方案。安全性分析表明，所提方案能混淆真实轨迹和假轨迹。

3) 大量的实验表明，本方案在具有较低计算开销的同时，与现有假轨迹隐私保护方法相比，具有更低的真实轨迹隐私泄露率，有效保护轨迹发布中的用户轨迹隐私。

2 相关工作

轨迹k-匿名方法是指在轨迹发布前由匿名服务器挑选出k–1条与用户真实轨迹无法区分的轨迹，通过将k条轨迹中对应时刻的位置泛化为相应的匿名区域形成路径来实现轨迹隐私保护。Xu等[9]提出利用其他用户的历史足迹选择k–1条轨迹，并形成相应的匿名区。随后，王超等[10]针对现有的轨迹匿名算法在计算轨迹相似性时忽略轨迹形状因素，产生的匿名轨迹集合可用性相对较低这一问题，不仅考虑轨迹的时间和空间要素，更加入了轨迹的形状因素，提出一个基于轨迹位置形状相似性的隐私保护方案。王爽等[11]将线性轨迹转化为不确定区域的思想引入轨迹数据的隐私处理，提出了不确定轨迹隐私保护方案。该方案利用布朗运动模型，将轨迹泛化成一个更为真实的轨迹区域，并将相似度高的轨迹域聚合成等价类进行数据的隐匿和发布。

但是，轨迹k-匿名隐私保护方法需要引入一个可信的第三方作为匿名服务器，而在现实环境中完全可信的第三方难以找到。这就使轨迹k-匿名隐私保护方法具有较低的实用性。

轨迹抑制方法是指对在轨迹发布前去除某些敏感或被频繁访问的位置。Terrovitis等[12]假设攻击者拥有部分真实轨迹，提出在轨迹发布时抑制处于敏感区域的位置，使轨迹泄露的风险不高于用户设置的隐私保护阈值。其中，区域的敏感度是根据区域内用户数量与总用户数量的比值进行计算。赵婧等[13]基于轨迹频率，通过对有问题的轨迹添加假数据和利用隐私关联度和数据效用之间的关系对轨迹数据进行局部处理的方法，提出了2种轨迹抑制隐私保护方案。

然而，如何找到合理抑制的位置信息仍是轨迹抑制隐私保护方法有待解决的关键问题，并且，如果抑制的位置过多会造成信息损失。这也限制了轨迹抑制隐私保护方法的可用性。

假轨迹方法是指由用户自己生成k–1条与真实轨迹相似的假轨迹，并与真实轨迹构成含有k条轨迹的集合进行发布，其基本思想最早是由Kido等[14,15]提出的。在他们的方案中，用户可利用其前后两次请求产生的假位置[15～17]形成假轨迹来保护自己的真实轨迹。You等[15]针对某一时刻对应的位置数量和轨迹集合总的轨迹数量，提出了2种假轨迹生成方案。在第一种方案中，用户首先决定假轨迹的起点和终点，然后在起点和终点之间随机生成与真实轨迹运行模式相似的假轨迹；第二种方案则是以用户真实轨迹为基准，通过选取真实轨迹上的位置点作为旋转轴点，对真实轨迹进行旋转生成假轨迹；Lei等[6]提出在旋转后得到的轨迹上增加交叉点的方法来增加假轨迹数量，从而提高用户真实轨迹的隐私保护等级。Wu等[7]不仅考虑了真实轨迹与假轨迹之间的距离，还考虑了假轨迹之间的距离。它们通过扰动[5]生成的假轨迹，使最终形成的轨迹集合能满足用户的隐私保护需求。李凤华等[8]对用户行动模式和轨迹相似性等特征可能被敌手获取情形下的轨迹隐私保护方案进行研究，以用户真实轨迹为基础，通过轨迹旋转保证用户行动轨迹的相似性，最后将该轨迹上的各个点偏移至附近的最接近真实的服务请求概率[18]的位置，生成假轨迹。

然而，现有的假轨迹隐私保护方法不仅未考虑单条轨迹中相邻位置间的时空关联性，也忽略了轨迹之间的时空关联性，使攻击者在误判率仅为23%的情况下，能以85%的概率识别出假轨迹，甚至直接获取到用户的真实轨迹。

3 预备知识

3.1 基本概念

轨迹由用户的不断移动而产生由时间和位置组成时空序列。本文将轨迹表示为：traj= {＜loc1(x1,y1),time1＞,＜loc2(x2,y2),time2〉,… ＜locn(xn,yn),timen＞},其中，loci(xi,yi)表示在timei时刻的位置坐标，1≤i≤n。当轨迹发布时，由用户生成k−1条假轨迹与真实轨迹trajreal组成的轨迹集合为Trajs={traj1,traj2,…,tarjk−1,trajreal}；表示集合Trajs中的元素个数。

本文借用图论中出入度的概念来表示轨迹集合中以各位置为起点或终点的路径数量。即出度表示在轨迹集合中，以第i条轨迹traji的第j个位置为起点的路径数量；入度则表示在轨迹集合中，以第i条轨迹traji的第j个位置为终点的路径数量。

3.2 攻击模型

在轨迹发布中，攻击者的目的是推测出某些假轨迹，降低用户的轨迹隐私保护需求，甚至直接识别出用户的真实轨迹，从而非法获取用户的个人隐私信息。本文假设攻击者可以获取用户发布的所有轨迹移动完整路径，掌握地图知识，且能够利用地图接口计算轨迹中前后相邻位置的移动距离和到达时间。攻击者识别假轨迹的能力可从以下2个方面进行度量。

1) 误判率τ。表示攻击者将用户的真实轨迹识别为假轨迹的概率。样本空间由轨迹集合Trajs表示，用E表示样本容量。若用E′表示将用户真实轨迹识别为假轨迹的样本数，那么

其中，Trajs′⊆Trajs。

3.3 隐私度量标准

定义1轨迹移动方向相似性。假设loci−1、loci和loci+1是任意一条轨迹traj中相邻的3个位置，令表示它们形成的2个方向向量。此时，这2个方向向量形成的方向夹角θ满足

那么，轨迹集合Trajs中的轨迹移动方向相似度为

定义2轨迹泄露率。假设用户发布的轨迹集合为Trajs，当攻击者利用其具有的轨迹识别能力对轨迹集合Trajs识别后，用户真实位置在任意时刻（timei）的泄露概率为

那么，用户真实轨迹的泄露率为

其中，m表示真实轨迹中方向夹角的个数。

4 攻击方案

为了证明现有假轨迹隐私保护方案忽略了单条轨迹中相邻位置间的时空关联性以及轨迹之间的时空关联性，本文利用相邻位置间的可达时间和各位置的出入度提出一个假轨迹识别方案。该方案包含时间可达性识别和出入度识别2个步骤。

4.1 时间可达性识别

针对轨迹集中的每条轨迹，依次检查该条轨迹中相邻位置是否满足时间可达性。即将该轨迹中相邻位置坐标发送至地图接口，从地图接口分别获取相邻位置间的可达时间mapTime。随后利用公布时间间隔pubTime（对于具有n个点的轨迹traj，可被划分为n−1段路径，即每相邻两点构成一段路径，那么每条轨迹最多进行n−1次比较)。最终根据对比结果，判断该条轨迹是否为假轨迹。对于任意一条轨迹traji∈Trajs，其时间可达性识别步骤如下。

Step1若mapTime＞＞pubTime，即用户在实际环境中，形成该段路径所需的时间较长（如相邻2个位置分别位于河的两岸）。此时，将该条路径判定为假轨迹；否则，进入Step 2。

Step2设定识别阈值δt。当时，就判定该段路径为可疑路径。分别统计每条轨迹中可疑轨迹的段数numi。

Step3计算可疑轨迹的段数numi占该条轨迹中总路径段数的比例。当时，该条轨迹被识别为假轨迹。其中，δt_all为阈值。

4.2 出入度识别

出入度识别是利用发布的轨迹集合中各位置的出入度值，对假轨迹进行识别。其基本步骤如下。

Step1统计轨迹集合中每条轨迹上各个点的出入度。用Di和Ci分别表示轨迹traji∈Trajs上各个位置的出度总和以及入度总和，即

其中，n表示轨迹traji上位置的数量。

Step2计算轨迹集合的平均出度DaverageOut和平均入度DaverageIn，即

Step3当，Ci＜δin·DaverageIn时，就将该轨迹识别为假轨迹。其中，δout和δin表示出入度识别阈值。

4.3 实验评估

这部分实验所用的轨迹数据来自Wikiloc网站注1：http://www.wikiloc.com。，本文首先在该数据集中挑选用户在城市中形成的轨迹数据，然后选用文献[17]提出的假轨迹生成算法——ADTGA生成假轨迹，从而得到轨迹集合。ADTGA生成算法是目前最好的假轨迹生成算法，它在假轨迹生成过程中不仅考虑了真实轨迹与假轨迹之间的距离，还考虑了假轨迹之间的距离。最后，本文再利用上述假轨迹识别方案对生成的轨迹集进行识别。实验环境为：Intel(R) Core(TM) i5-3470@ 3.20 GHz，4 GB内存。算法由C++编程实现，程序运行在 Windows 7环境下。

4.3.1 时间可达性识别效果评估

由图2可知，随着δt和δt_all的增大，误判率和识别率均呈下降状态。这是由于随着δt和δt_all的不断增大，使越来越多假轨迹能满足时间可达性识别条件，它们不会被识别成假轨迹，这就导致了识别率的降低。相应地，误判率也会随着被判断为假轨迹的轨迹数量减少而降低。

4.3.2 出入度识别效果评估

出入度识别阈值δout和δin对出入度识别效果的影响情况如表1所示。在这部分实验，本文设置。这是因为在ADTGA算法生成的假轨迹集合中，各位置具有相同的出度和入度。由于ADTGA算法在生成假轨迹的过程中，每条假轨迹是由真实轨迹旋转得到的。这就使生成的每条假轨迹均与真实轨迹相交。显然，每个交点均会造成出入度的增加。这就导致真实轨迹的出入度总是大于轨迹集合的平均出入度。因此，当出入度识别阈值时，误判率为0。当时，平均出入度与一个大于1的值相乘，得到的结果变大。此时出现真实轨迹出入度小于平均出入度的情况，因此存在误判。

图2 时间可达性识别

表1 δout和δin对出入度识别的影响

4.3.3 所提方案的识别效果评估

本文将时间可达性识别和出入度识别同时用于识别假轨迹，其结果如图3所示。通过表1可知，当δout=δin=1时，出入度攻击具有较高的识别率且误判率为0。因此，此处将出入度阈值设为1。当时，所提假轨迹识别方案的误判率仅为23%，而识别率高达85%。即现有的假轨迹隐私保护方案仅能以15%的成功率保护用户的真实轨迹。

图3 假轨迹攻击方案

5 基于时空关联性的假轨迹隐私保护方案

基于上述假轨迹识别原理，本文还提出了一种基于时空关联性的假轨迹隐私保护方案，在假轨迹生成过程中不仅考虑了每段路径的时间可达性及移动距离，还对轨迹的整体移动方向进行限制。最后还保证在生成的轨迹集合中，每个位置具有相同的出入度。具体过程如下所示。

1) 拟合真实轨迹的整体方向

本文利用最小二乘法拟合真实轨迹的整体方向，从而保证随后生成的假轨迹的移动方向与用户真实轨迹的移动方向相似，使攻击者难以通过移动方向识别出假轨迹。其中，用户真实轨迹的移动方向的斜率为

2) 起止假位置的生成

利用现有的假位置生成方案，分别以真实轨迹的起点和终点为保护点生成假位置集合，并分别从LocSet1和LocSetn中选择假位置，使真实轨迹整体移动方向的斜率l与假轨迹起止点构成的斜率lslope相近且起止点未在已有轨迹中出现。这不仅能限制假轨迹的整体运动方向，还能保证起止位置的出入度均为1。此外，起止位置还需要满足下列条件

这是因为只有保证假轨迹起止点在时间区间内可达，才有可能保证该轨迹中任意相邻两位置能在发布时间间隔内可达，并且，移动距离的控制又使假轨迹与真实轨迹具有相似的移动速度。

3) 中间位置的生成

逐一为每条假轨迹生成其第2个到第n–1个位置。在生成假轨迹的第个位置时，以真实轨迹的第i–1和i个位置之间的欧式距离r+random为半径(random表示随机数)，以假轨迹第i–1个位置为圆心作圆。在lslope所在直线的两侧，每间隔θ°选择一个候选位置，构成假位置候选集合，直至网格边界与lslope所在直线的夹角达到阈值，如图4所示。假位置候选集为图4中阴影部分。然后再在候选集合LocSet′中随机选择假位置。这样不仅保证生成的假位置具有随机性，而且不能避免出现中间位置突然远离整体轨迹的情况。其中，，d是网格的边长。

图4 假位置候选集

4) 对完整的假轨迹进行整体方向的检查

在生成完整的假轨迹后，拟合假轨迹的整体移动方向的斜率为

随后，将假轨迹的整体移动方向的斜率ldummy与真实轨迹的整体移动方向的斜率l进行对比。如果斜率相近，则进行时间及移动距离的判断。如果不满足，则重新生成假轨迹。

5) 对假轨迹的每段路径进行时间可达性和移动距离检查

对任意第d条假轨迹trajd的第i个位置和第i+1位置形成的路径进行时间可达性检查和移动距离检查，若

不成立，则记录下不满足要求的路径段数num。如果num＞δ(n−1)，则表示不满足要求的轨迹数过多，此时重新生成假轨迹；否则，该条轨迹即为所生成假轨迹。其中，δd、δt和δ为检查阈值。

利用上述方案，直到生成k–1条假轨迹。综上所示，本文所提的基于时空关联性的假轨迹生成算法如下。

算法1基于时空关联性的假轨迹生成算法

输入轨迹

输出轨迹集合

5.1 安全性分析

当用户采用本方案生成假轨迹时，本文首先拟合用户真实轨迹的整体移动方向，计算其斜率。随后在假轨迹起止位置的生成过程中，本文通过计算斜率比，避免出现假轨迹与真实轨迹移动方向相反的情况。当斜率比不断接近1时，就能保证虚假移动路径的整体方向与用户真实路径的移动方向平行，使攻击者难以利用移动方向识别出假轨迹。并且，本方案还能保证起止位置构成的路径能在发布时间间隔内可达，并利用移动距离使用户在假轨迹与真实轨迹上具有相近的移动速度。这样可避免攻击者在获知用户采用某种交通工具时，利用该类交通工具的移动速度通过计算可达时间识别出假轨迹。当为每条假轨迹生成中间位置时，本文首先生成候选假位置时，还保证任意2条轨迹不会相交。在遵循上述同样的原则对假轨迹进行合理轨迹段比例检查。攻击者从每个时刻观察到的位置数目即为轨迹的数量k。此时，用户真实轨迹的泄露率为

满足用户的隐私保护需求。综上所述，当攻击者与用户具有相同的假轨迹识别能力时，用户采用本方案能有效保护自己的真实轨迹。

5.2 实验分析

为了便于进行有效性分析，本部分实验仍采用4.3节中介绍的实验数据与实验环境。本文从实验数据集中随机选择不同的轨迹作为用户真实移动轨迹，随后采用本文提出的基于时空关联性的假轨迹生成算法生成假轨迹，形成轨迹集合。最后，再利用第4节提出的假轨迹识别方案对生成的轨迹进行识别，从而表明所提的基于时空关联性的假轨迹隐私保护方案能有效保护用户的真实轨迹。

5.2.1 轨迹数量k对轨迹泄露概率的影响

本文利用第4节提出的假轨迹识别方法对本方案生成的轨迹集合进行识别，从而说明本文方案能有效保护用户的轨迹隐私。在这部分实验中本文设置，实验如图5所示。当攻击者利用单条轨迹中的时空关联性以及轨迹间的时空关联性对生成轨迹集合进行识别后，并不能识别出假轨迹。此时用户的真实轨迹隐私保护等级仍为，满足用户隐私保护需求。而攻击者利用上述时空关联性对由ADTGA算法生成的轨迹集合进行识别时，最好的情况是k=15和k=18时，还剩下2条假轨迹未被识别出。此时，用户的真实轨迹隐私保护等级仅为，远大于。这就说明了本文方案能有效保护用户的轨迹隐私。

图5 利用时空关联性识别后剩下的轨迹数量

5.2.2 轨迹数量k对轨迹相似度的影响

轨迹的移动方向相似度表现了假轨迹与真实轨迹的轮廓相似程度，能在一定程度上反映用户真实轨迹的隐私保护等级。具体实验结果如图6所示。总体来说，随着k的改变，本文方案生成的轨迹集合的相似度σ保持不变，且均在0.5以下。从3.3节中可知，σ越低，表明生成的轨迹集合中各轨迹间的运动方向就越相似。这也说明了本方案能预防攻击者利用各轨迹的移动方向识别出虚假移动路径。

图6 k对轨迹相似度的影响

5.2.3 轨迹数量k对方案执行时间的影响

本文简要分析轨迹数量k对本文所提出的假轨迹生成方案在计算开销上的影响，实验结果如图7所示。由于生成的假轨迹数量随着k的增大而增多，这就使本方案所需的计算时间也随之增加。然而当k=20时，本方案成功为用户生成假轨迹所需的计算时间仅仅需要0.38 s。这说明本文方案具有良好的实用性。

图7 k 对方案运行时间的影响

综上所述，本方案在具有较低计算开销的同时，与现有假轨迹隐私保护方案相比，还能混淆真实轨迹与假轨迹间的时空关联性，从而有效保护轨迹发布中用户的轨迹隐私。

6 结束语

本文通过大量实验首先证明现有假轨迹隐私保护方案仅能以不高于15%的成功率保护用户的真实轨迹。而造成上述问题的原因是现有假轨迹隐私保护方案不仅未考虑单条轨迹中相邻位置间的时空关联性，也忽略了轨迹之间的时空关联性，使攻击者能正确识别出某些假轨迹，乃至推测出用户的真实轨迹。针对上述问题，本文从轨迹的整体方向、轨迹中相邻位置的时间可达及移动距离对单条轨迹中相邻位置间的时空关联性和轨迹之间的时空关联性进行分析，提出了一个假轨迹隐私保护方案。安全性分析表明，所提方案能混淆真实轨迹和假轨迹间的时空关联性，使攻击者难以识别出假轨迹。大量实验也表明，本文方案在具有较低计算开销的同时，与现有假轨迹隐私保护方法相比，能降低用户真实轨迹的隐私泄露率，有效保护轨迹发布中的用户轨迹隐私。

[1]KRUMM J.A survey of computational location privacy[J].Personal and Ubiquitous Computing,2009,13(6):391-399.

[2]霍峥,孟小峰.轨迹隐私保护技术研究[J].计算机学报,2011,34(10):1820-1830.ZHENG H,MENG X F.A survey of trajectory privacy-preserving techniques[J].Chinese Journal of Computers,2011,34(10):1820-1830.

[3]CHOW C Y,MOKBEL M F.Trajectory privacy in location-based services and data publication[J].ACM SIGKDD Explorations Newsletter,2011,13(1):19-29.

[4]ZHANG Z,SUN Y,XIE X,et al.An efficient method on trajectory privacy preservation[C]//International Conference on Big Data Computing and Communications.Springer International Publishing,2015:231-240.

[5]YOU T H,PENG W C,LEE W C.Protecting moving trajectories with dummies[C]//2007 International Conference on Mobile Data Management.IEEE,2007:278-282.

[6]LEI P R,PENG W C,SU I J,et al.Dummy-based schemes for protecting movement trajectories[J].Journal of Information Science and Engineering,2012,28(2):335-350.

[7]WU X,SUN G.A novel dummy-based mechanism to protect privacy on trajectories[C]//2014 IEEE International Conference on Data Mining Workshop (ICDMW).IEEE,2014:1120-1125.

[8]李凤华,张翠,牛犇,等.高效的轨迹隐私保护方案[J].通信学报,2015.36(12):114-123.LI F H,ZHANG C,NUI B,et al.Efficient scheme for user’s trajectory privacy[J].Journal on Communications,2015,36(12):114-123.

[9]XU T,CAI Y.Exploring historical location data for anonymity preservation in location-based services[C]//The 27th Conference on Computer Communications.IEEE,2008.

[10]王超,杨静,张健沛.基于轨迹位置形状相似性的隐私保护算法[J].通信学报,2015,36(2):144-157.WANG C,YANG J,ZHANG J P.Privacy preserving algorithm based on trajectory location and shape similarity[J].Journal on Communications,2015,36(2):144-157.

[11]王爽,周福才,吴丽娜.移动对象不确定轨迹隐私保护算法研究[J].通信学报,2015,36(Z1):94-102.WANG S,ZHOU F C,WU L N.Uncertain trajectory privacypreserving method of moving object[J].Journal on Communications,2015,36(Z1):94-102.

[12]TERROVITIS M,MAMOULIS N.Privacy preservation in the publication of trajectories[C]//9th International Conference on Mobile Data Management.IEEE,2008:65-72.

[13]赵婧,张渊,李兴华,等.基于轨迹频率抑制的轨迹隐私保护方法[J].计算机学报,2014,37(10):2096-2106.ZHAO J,ZHANG Y,LI X H,et al.A trajectory privacy protection approach via trajectory frequency suppression[J].Chinese Journal of Computers,2014,37(10):2096-2106.

[14]KIDO H,YANAGISAWA Y,SATOH T.An anonymous communication technique using dummies for location-based services[C]//International Conference on Pervasive Services.IEEE,2005:88-97.

[15]KIDO H,YANAGISAWA Y,SATOH T.Protection of location privacy using dummies for location-based services[C]//21st International Conference on Data Engineering Workshops.IEEE,2005:1248-1248.

[16]LU H,JENSEN C S,YIU M L.Pad:privacy-area aware,dummybased location privacy in mobile services[C]//The Seventh ACM International Workshop on Data Engineering for Wireless and Mobile Access.ACM,2008:16-23.

[17]NIU B,LI Q,ZHU X,et al.Achieving k-anonymity in privacy-aware location-based services[C]//IEEE INFOCOM 2014-IEEE Conference on Computer Communications.IEEE,2014:754-762.

[18]HUO Z,HUANG Y,MENG X.History trajectory privacy-preserving through graph partition[C]//The 1st International Workshop on Mobile Location-Based Service.ACM,2011:71-78.

雷凯跃（1990-），女，天津人，西安电子科技大学硕士生，主要研究方向为位置隐私保护。

李兴华（1978-），男，河南南阳人，博士，西安电子科技大学教授、博士生导师，主要研究方向为隐私保护、网络与信息安全。

刘海（1984-），男，贵州贵阳人，西安电子科技大学博士生，主要研究方向为位置隐私保护和理性密码协议。

裴卓雄（1993-），男，山西运城人，西安电子科技大学硕士生，主要研究方向为位置隐私保护。

马建峰（1963-），男，陕西西安人，博士，西安电子科技大学教授、博士生导师，主要研究方向为信道编码、网络与信息安全、密码学。

李晖（1968-），男，河南灵宝人，博士，西安电子科技大学教授、博士生导师，主要研究方向为密码学、无线网络安全、云计算安全、信息论与编码理论。

Dummy trajectory privacy protection scheme for trajectory publishing based on the spatiotemporal correlation

LEI Kai-yue,LI Xing-hua,LIU Hai,PEI Zhuo-xiong,MA Jian-feng,LI Hui
（School of Cyber Engineering,Xidian University,Xi’an 710071,China）

The spatiotemporal correlation was analyzed between neighboring locations and the trajectories similarity from the movement direction,the reachable time between neighboring locations and the movement distance,and a dummy trajectory privacy protection scheme based on the spatiotemporal correlation was proposed.Security analysis shows that the presented scheme successfully confuses the user’s real trajectory with dummy trajectories,thereby protecting the user’s trajectory privacy.Furthermore,extensive experiments indicate that the presented scheme not only has the limited computation cost,but also ensures that the generated dummy trajectories are similar to the user’s real trajectory.

trajectory publishing,privacy protection,dummy trajectory,spatiotemporal correlation,trajectory leakage

The National Natural Science Foundation of China (No.61372075,No.U1405255,No.61202389,No.61472310)

TP309

A

10.11959/j.issn.1000-436x.2016281

2016-08-16；

2016-09-30

李兴华，xhli1@mail.xidian.edu.cn

资助项目（No.61372075,No.U1405255,No.61202389,No.61472310）