TFR-resm:一种基于可变区域相似点的新型轨迹隐私保护方法

任仲昊 耿雪冬 刘浩然

(山东科技大学计算机科学与工程学院 山东 青岛 266590)

0 引 言

在高速发展的当今社会，随着信息通信技术的不断发展，智能设备的不断更新换代，人们在使用便捷的互联网和网络定位的同时，隐私泄露事件也时有发生，因此基于位置服务(LBS)已受到广泛的关注[1-3]。因为用户通过智能定位设备向服务器发送请求消息，服务器若想提供位置服务，需要获取用户的详细的位置信息和请求内容，但这些信息容易被攻击者获取[4]，导致用户的隐私泄露，这样不仅限制了位置服务的发展，也影响了广大人群的日常生活，因此，保护隐私是至关重要的。

隐私保护主要分为位置隐私保护与轨迹隐私保护。位置隐私保护主要针对当前位置点进行隐私保护，而轨迹隐私保护，顾名思义，是针对用户移动轨迹[5]中的请求信息进行有效的保护。本文方法主要是通过用户之间的协作，构建K-匿名区域生成假轨迹[6]，进而完成真实用户的伪装，达到隐私保护的目的。

在隐私保护中，隐私保护方法虽多样，但是其隐私保护不能够面面俱到，主要的缺陷在于以下几个方面：在构建匿名区域时，选择使用K-匿名原则[7]，若当时信息请求用户处于人口稀少的区域，会导致匿名区域中大多为不存在的虚拟点；若处于极端的地形[8]，如湖泊、海洋等也十分容易暴露；匿名区域的中心是否为信息请求用户也是一个值得关注的问题，因为站在攻击者的角度上，首先考虑中心点是否为真实用户；最后，在构建轨迹时，若虚拟轨迹与真实轨迹的位置点个数或者移动方向偏差过多也容易导致隐私泄露。

基于以上的问题，TFR-resm(Two-dimensional Fluctuates in Range-Resemblance)方法在轨迹隐私保护上的创新主要体现在以下几个方面：

(1) 避免直接使用信息请求用户参与信息的发送，本文将使用相似用户代替信息请求用户发送消息，有效地降低隐私泄露的概率，即使攻击者在掌握相关背景知识的情况下，依然不会找到真实的用户，因为真实的用户不存在于请求信息压缩包中。

(2) 虚拟位置生成是绝大多数隐私保护方法都需要用到的技术。生成虚拟位置就需要划定匿名区域，本文提出除去匿名区域中心的RMC-匿名区域法，该方法可以有效地解决信息请求用户为匿名区域中心的问题。

(3) 为了能够构建与真实轨迹相似度高的隐私混合轨迹，本文提出波动距离与波动角度，波动距离用于限制真实轨迹和混合轨迹在行动过程中的距离差，波动角度使得真实轨迹与混合轨迹在一定方向上高度一致，使得真实轨迹与混合轨迹相似度高。

(4) 在轨迹方面，本文使用相似用户与虚拟用户相结合的方法构建混合轨迹，在构建轨迹时，本文提出一种新的SMTA方法用来构建混合轨迹，该方法的优势在于能够构建与真实用户相似度高的混合轨迹。

1 相关工作

目前，轨迹隐私保护技术[9]主要分为泛化法、抑制法、假数据法三类。泛化法的轨迹隐私保护技术指将轨迹上所有的采样点都泛化为对应的匿名区域，以达到隐私保护的目的。抑制法的轨迹隐私保护技术是指根据具体情况有条件地发布轨迹数据，并且不发布轨迹上的某些敏感隐私或频繁访问的位置以实现隐私保护。假数据的轨迹隐私保护技术是指通过添加假轨迹对原始数据进行干扰，同时又要保证被干扰的轨迹数据的某些统计属性不发生严重失真。近些年，这些方法与技术在隐私保护方面得到了广泛的应用。

文献[10]提出了轨迹(k,e)-匿名模型来抵抗轨迹相似攻击，该算法以轨迹斜率为敏感值进行构建轨迹，不同轨迹为一个等价类和要求不同轨迹的斜率至少是e。从安全角度看，该算法得到的轨迹(k,e)-匿名模型更能抵抗轨迹相似攻击。但由于约束增强，导致信息损失略大。文献[11]提出了一种基于道路网络下分段假轨迹的轨迹隐私保护方法，该方法生成了不同时间内真实轨迹采样位置的伪位置，并在不同时间间隔内生成分段伪轨迹。其劣势在于路网非常复杂，攻击者可能结合路段和背景知识威胁到用户的隐私。文献[12]提出一种基于缓存的用户合作隐私保护方法，移动用户先在合作用户缓存中查找查询内容，当寻找失败时才通过协作的方式向 LSP 发出查询。但是LBS拥有不确定性，它不会一直保持可信任状态。

文献[13]提出了一种基于离线环境中原始跟踪和已发布跟踪之间相互信息的位置跟踪隐私度量，并在给定的实用约束条件下，给出了最小化跟踪级隐私泄漏的最优位置跟踪发布问题。还提出了一个隐私度量来捕获在线设置中的跟踪隐私泄漏，其实现的难点在于计算方面有较高的难度。文献[14]提出了一种新的基于环境的位置隐私度量方法，并提出了一种随机模型，该模型能够捕捉到用户路径上的空间变化，缺点是不适用于多用户和多任务。

文献[15]提出了一种新的思想，针对轨迹隐私问题，基于用户行为模式、轨迹相似度等背景信息增加了实时流量监控。根据k匿名的思想，提出了一种结合交通条件保护轨迹隐私的方法。该文的劣势体现在位置服务，还没有有效的方法来衡量轨迹隐私保护的程度。

针对以上诸多的隐私保护问题，本文提出使用相似位置代替信息请求用户发送请求消息，并且同时按照规则生成相关的虚拟位置点，满足构建虚拟轨迹的数量。在构建轨迹时，真实用户不在任何轨迹内，这样不容易被攻击者获取想要的信息。在每一时刻根据本文提出的波动角度与波动距离，寻找与真实用户高度相似的相似位置，使得生成轨迹时，不容易被攻击者排除，轨迹的每个时间点相似和虚拟点是随机的，这就导致相似位置与虚拟位置点构造隐私轨迹。

2 基础知识

2.1 基础定义

定义1对于已知的地球表面上两个经纬度点，考虑地球椭圆形的外貌，两点之间的实际距离记为SD，即经纬间距，距离计算公式为：

(1)

式中：(Lung1,Lat1)表示A点经纬度；(Lung2,Lat2)表示B点经纬度；a=Lat1-Lat2为两点纬度之差；b=Lung1-Lung2为两点经度之差；6 378.137为地球半径，单位为km。

定义2假设在t时刻位置点为A(Lung1,Lat1)，在t+1时刻位置点为B(Lung2,Lat2)，此时B在纬度Lat2上的投影为B′(Lung2,Lat1)，存在夹角为∠BAB′，该夹角即位置点夹角，计算公式为：

(2)

定义3用p定义一个用户的集合，其中包括位置点(Lung,Lat)、年龄age、性别gender和其他属性，则用户的信息集合记为p{(Lung,Lat),age,gender}。此时假设周围存在的用户，从中选择相似位置点的方法记为相似度，公式为：

(3)

式中：P为两个用户在位置点上的距离S与权重ω1的乘积ω1×S；A为两个用户在年龄上的差值与权重的乘积ω2×(age1-age2)；G为两个用户在性别上与权重的乘积，同性别为0×ω3，否则为1×ω3；省略点表示其他相关的用户特征；u为特征向量的个数。

计算相似度时，计算距离大小与年龄的参数，距离会起决定性作用，所以需要对数据规范化处理，使用最大-最小归一化对原始数据进行线性变换使其规约在0～1之间。转换函数如下：

(4)

式中：X为要归一化的数据；Xmax为全体样本数据的最大值；Xmin为全体样本数据的最小值。

定义4假设真实轨迹与虚假轨迹一共有k条，第ti→ti+1时刻，真实轨迹的经纬距离为disti，虚拟轨迹第j条轨迹的经纬距离为distij，则轨迹距离差与两线段角度θi表示相似度，即轨迹相似度，公式为：

(5)

s.t.Dist=max(disti,distij)

定义5信息熵[16-17]是跟所有可能性有关系的，每个可能事件的发生都有个概率。信息熵就是发生一个事件我们得到的信息量大小。在数学上，信息熵其实是信息量的期望，其公式如下：

(6)

式中：p(xi)代表随机事件xi的概率。

2.2 相似用户

本文为了能够有效地保护真实用户轨迹，避免构建的虚拟轨迹被攻击者所识破，提出相似用户的概念，使用相似用户代替真实用户与其他位置点一起发送请求消息。为了能够更加有效地保护信息请求用户的隐私，该相似用户也是真实存在的一名用户，该方法的优点在于，即使攻击者获取到真实用户的相关信息，相似用户也可以混淆攻击者的视线，因为相似用户代替真实用户发送消息并且也是真实存在的用户。为了能够寻找到满足要求的相似用户，本文给出了相关定义，通过定义3，计算轨迹初始化时间戳t0时刻得出相似用户。

相似用户的数据特征获取方法一般来说有两种，一种是当用户使用某服务软件或平台时，搜索当前用户周围存在的真实用户，搜索到的真实用户即注册使用过该服务的用户，可以通过简单的操作获取基本特征信息(可参考WeChat、QQ等)；另一种是通过信任第三方(TTP)获取用户数据，TTP的数据收集模块[18]可以获取所有用户的轨迹信息，可以轻易得到周围用户的特征信息。

相似用户与真实用户在各特征数据上需要高度一致，为了实现该目的，当使用数据时，首先要对数据进行处理，本文使用PCA降维技术和bridge线性回归法，除去与本文实验不相关的特征数据，并使用定义3计算相似性。假设真实用户为男性，发送的信息请求为寻找男士单身俱乐部，若此时的相似用户为女性，在性别上就不符合现实情况。攻击者通过其相关手段获取到用户需要发送的信息，当选择的相似用户为女性时，该相似用户起不到有效的保护作用。

当相似用户代替真实用户的请求消息时，此时就需要考虑相似用户保护。本文认为相似用户依然是不会存在隐私泄露风险的，原因有两点：(1) 攻击者的攻击是有指向性的，攻击者会针对某一用户进行攻击，专门对自己的目标进行信息收集，使用相关技术进行推测，获取用户的相关信息，对额外的相似用户不会进行较多研究，因为相似用户不是其真正的目标。(2) 在形成轨迹时，只是在初始位置拥有真实的相似用户，在接下来的构建中，将会依照本文提出的波动角度与波动距离生成相似位置点，该点代替真实用户发送消息，因此轨迹中真实用户与相似用户会进行重新命名。

假设当前为轨迹初始化阶段，如图1所示，当信息请求用户发送消息时，开始搜索周围存在的真实用户，并使用本文定义的用户相似度，得出图1结论，可以看出用户fen Cheng的相似度高于其他存在的真实用户，则使用该用户代替真实用户发送消息。

图1 用户相似度

2.3 波动角度与波动距离

本文构建轨迹的核心问题就是如何在初始化时间戳后寻找后继的相似位置点，只有相似位置点足够满足要求才能更好地保护信息请求用户的隐私。因此，如图2所示，若想构建与真实轨迹高度相似的轨迹[19]，准确的波动距离与波动角度是非常有必要的。波动距离和波动角度的计算可以概括为三步。第一步，依照本文提出的规则寻找相似位置点，如图2所示。第二步，计算真实用户在相邻两个时间戳所移动的轨迹和纬度形成的夹角。第三步，给与相似位置点和真实用户相同的移动距离和移动角度，并加入波动距离与波动角度，使得形成扇形环区域，该区域为下一相似位置点的生成区域。

图2 波动距离与波动角度

在波动角度方面，由本文的定义可知，当前时间点(假设不是初始时刻)的信息请求用户与其前一时刻信息请求位置连线，然后与其当前点坐标(x,y)中y纬度形成夹角θ，再对当前位置点对纬度映射，形成直角三角形，可以轻易地得出当前夹角θ的大小。一个合适的波动夹角是非常重要的，如果夹角过大，则混合轨迹方向与真实用户轨迹方向偏差过大；若夹角过小，可能会出现轨迹重合问题。

在波动距离方面，波动距离是两个时间戳之间真实用户行动轨迹的经纬间距的变化。波动距离的大小也是非常重要的，因为波动距离过大，导致相似位置点的可取值范围巨大，可能生成的相似位置与真实位置相似度不够，若波动距离过小，会导致相似位置与真实位置在定位有误差的情况下可能是重合的。

除此之外，在考虑到真实用户每次行进距离是没有规则并且长度是不一样的，因此在计算波动距离与波动角度时，需要对其进行不断的更新。因此本文对波动距离与波动夹角形成的扇形环面积定义大小，根据真实情况，将通过设定面积的大小和真实移动距离与角度不断地更新波动角度与波动距离，达到本文的目的。

2.4 虚拟点与RMC-匿名区域

由于代替信息请求用户发送消息的相似位置点只有一个，并且本文方法中，信息请求用户是不存在于混合轨迹中，因此若不加入其他虚拟点，轨迹的数目只有一条。此时若加入虚拟位置点[20]，优点不仅在于轨迹数量的增加，而且每条轨迹是相似位置点与虚拟位置点的组合，就会产生多种与真实轨迹相似的混合轨迹。

虚拟位置点的生成需要按照一定的规则，假设虚拟位置点生成的位置与信息请求用户距离较大，攻击者通过对目标收集的数据可以轻易地排除此虚假位置点，因此，虚拟位置点的生成也是非常重要的。本文选取真实用户位置点所在的区域，在区域内生成包括真实用户和相似用户在内的矩形区域，该矩形区域记为虚拟位置点生成的区域，在矩形内部随机生成所需数量的虚拟点。

为了能够有效地避免真实信息请求用户为矩形匿名区域中心，本文提出新的匿名区域构建方法，即RMC-匿名区域法。首先需要通过以真实用户为中心构建匿名区域，在构建完成匿名区域后，设定一个圆为矩形匿名区域的中心，然后向任意方向移动矩形匿名区域，使其中心的信息请求用户落在矩形内圆的范围外，此时再按照上述的虚拟位置生成方法生成所需的虚拟位置点。

RMC-匿名区域构建步骤(以构建200 m×150 m匿名区域为例)：

步骤1以当前信息请求用户的经纬坐标为中心构建200 m×150 m的匿名区域空间。

步骤2根据匿名区域大小设定内在圆的大小，建议面积大于匿名区域的四分之一。

步骤3保持内在圆与匿名区域矩形相对位置不变，移动匿名区域，使得信息请求用户落在圆外矩形内，即内在圆与矩形匿名区域相异的区间。

步骤4按照规则在匿名区域寻找相似用户和生成虚拟位置点。

如图3所示，图中矩形的面积是通过与真实环境相结合共同确定的。在人口密集的区域，矩形的面积可以相对较小，因为人口稠密，若矩形的面积过大，导致虚拟位置点过于稀疏，攻击者可以根据真实状况排除虚拟位置点，反之亦然。

图3 矩形匿名区域

2.5 混合轨迹构建方法SMTA

本文将由相似用户与虚拟位置点一同构成的隐私轨迹称为混合轨迹。在构建混合轨迹时，首先要做的是寻找相似位置，相似位置是构建轨迹最为重要的一步。在本文中，为了能够找到与信息请求用户足够相似的相似用户，提出用来寻找相似位置点的相似度，相似度不仅考虑到用户的当前位置，而且为了与真实用户能够高度相似，还考虑到用户的其他特征信息(如性别、年龄等)，用此寻找高度相似的相似位置。

在获取到相似位置后，若想要构建n条混合轨迹，仍然需要生成n-1个虚拟位置点。虚拟位置点在上文中已详细介绍，通过使用信息请求用户为对角线交点的比例矩形生成虚拟位置点。在下一时刻，上一时刻的相似位置与虚拟位置和该时刻的其中任意一个的相似位置与虚拟位置点匹配相连，构成存在相似位置与虚拟位置相结合的混合轨迹。

2.6 轨迹命名

隐私轨迹中，为了保护轨迹不被轻易获取，需要对真实用户赋予假名操作，以避免攻击者直接获取到真实用户的有关信息，这些是轨迹隐私保护中常用的技术，也是保护轨迹隐私的一个常识，但本文有所不同。

在本文的隐私保护中，隐私轨迹中是不存在信息请求用户的，原因在于相似位置是信息请求用户的替代位置，但仍需要对每一条轨迹赋予名字。本文构建一个词袋，当在初始时刻寻找到相似位置点与构建虚拟位置点后，从词袋中随机取出一个名字赋予给每一个相似位置点和虚拟位置点，并且在本文实现对每一条轨迹命名时从词袋中不放回地取出任意名字，避免出现轨迹名字相同的情况。通过赋予名字后，整条轨迹中所有的点都统一使用初始时间戳的名字，达到保护隐私的目的。

3 算法设计

3.1 场景分析

在轨迹隐私保护方法中，算法应该切合实际的应用场景。如图4所示，本文假设张某外出旅行寻找加油站，首先在不知道加油站具体位置时，通过智能设备向服务器发送消息请求。其次，消息通过基站传输，当收到信息请求用户的消息时，此时为了保护信息请求用户张某的个人位置等信息不被泄露，使用本文提出的TDR-resm算法对张某的请求信息进行隐私保护，然后将其发送至LBS，LBS将接收的请求信息在数据库中找到对应的应答，将消息返回。最终通过基站，用户接收到自己请求的加油站位置。

图4 场景应用

通过应用场景分析和综合以往的隐私保护方法可知，本文的轨迹隐私保护方法TFR-resm可以分为三部分：

(1) 构建RMC-匿名区域，寻找相似位置点，生成虚拟位置点。

(2) 在构建好的匿名区域内寻找相似用户，代替其发送信息请求消息。

(3) 通过不同的时间戳和轨迹构建方法SMTA，构建混合轨迹。

3.2 确定波动角度和波动距离

由于原有的隐私轨迹保护的方法与技术不能够有效地保护轨迹隐私，在众多教授学者的不断努力下，通过不同方式的创新改进隐私保护方法，使其能够高效地保护隐私。本文经过研究阅读前人的工作，提出一种保护轨迹隐私的创新方法，而该方法的主要创新体现在寻找相似位置，波动角度与波动距离是寻找相似位置点的重要方法。

在现实生活中，信息请求用户的运动轨迹在每一时刻是不同的(例如方向、速度等)，并且进行信息请求的时间差也是有所差距的，因此若固定的波动距离与角度将会导致扇形环面积差值过大，相似位置点与信息请求用户的相似度变低。

本文为了改进这一问题，将先设定扇形环的面积(该面积的大小根据请求用户真实情况设定)，通过面积不断地调节每一时间戳的波动距离与波动角度。由于需要距离与角度两个参数，我们通过扇形环的弧长公式与面积公式求出该参数：

(7)

式中：l是弧长；θ是真实用户相邻点与当前纬度扇形圆心角；R是真实用户两时间戳距离，视为扇形半径。为了能够更好地得出波动距离与波动角度，本文将扇形环面积近似为等腰梯形，则计算公式为：

(8)

式中：R为真实用户相邻时间戳的真实距离；θ为真实用户相邻点与纬度夹角；ΔR为波动距离；Δθ为波动角度；h为等腰梯形高；S为人工设置的扇形环面积。

在构建轨迹时，扇形环的面积是已知的常量，用户可以根据当前位置的真实情况进行设定，假若在人口密集的区域，可以给扇形环面积设置小的值，这样可以生成更有效的相似位置。反之，人口稀疏区域可以设置大的值。

3.3 相似位置寻找与虚拟位置点生成

在轨迹构建中本文使用到相似位置点与虚拟位置点，混合轨迹是由若干相似位置点和虚拟位置点组成。接下来本文将详细讲述如何计算生成相似位置点与虚拟位置点。相似位置点与虚拟位置点的生成是按照本文提出的算法公式得出，相似位置点是由相似度并通过计算每一时间戳的波动距离与波动角度确定相似位置点的生成区域而生成的。而虚拟位置点是按照矩形匿名区域的规则生成的，具体如算法1中所示。

算法1虚拟位置点算法

输入：信息请求用户user(x,y)，轨迹数量k，矩形面积Q。

输出：相似位置点集合S，虚拟位置点集合V。

1. 初始化S,V为空集合

2.t=0

3.P=KdTree(user,n)

4. 根据式(3)，计算求得集合P中n个近邻点中与信息请求用户最相似的点S0,S0为相似位置点的初始值。

5.la/lb=C

6.Q=la*lb

7. Foriinrange(k) do

8.v=random(user(Δx,Δy))

9.v∈V

10. End for

11. Ift>0 do

12. 由式(8)计算可获得波动距离Δd和波动角度Δθ

13.st=random(area(Δθ,Δd))

14.st∈S

15. End if

16. 重复生成虚拟位置点的步骤，在每一时刻都生成相似位置点集合V。

17. ReturnV,S

由算法1可知，生成相似位置点和虚拟位置点时，为了快捷地寻找相似用户，避免遍历整个数据集，首先，通过使用KdTree算法求得相近的n个用户，再通过式(3)，得出其中最优的相似用户。其次，通过矩形匿名区域生成虚拟位置点。当初始化后，使用式(8)计算波动距离与波动角度，得出其他时刻的相似位置点，并且同时生成虚拟位置点，这样就可得到轨迹在该时刻的相似位置点和虚拟位置点集合。

定理1算法1的时间复杂度为O(nlogn)。

证明1在算法1中主要的工作为轨迹初始化时寻找相似用户，本文寻找近邻的方法为KdTree算法，因此该算法的时间复杂度体现在KdTree算法上。通过分析KdTree算法可知算法1的时间复杂度，由于KdTree的结构为二叉树，本文通过分析二叉树的特征结合KdTree的特点能够得出算法的复杂度，记为O(nlogn)，在此处logn底数取值为2，因此算法1的复杂度为O(nlogn)。

3.4 构建混合轨迹

混合轨迹的构建是本文的核心，构建轨迹使用到诸多的元素。首先，为了使信息请求用户隐私不泄露，使用相似点代替信息请求用户，而相似位置点不是随意生成的，需要一定的规则，这就是本文提出的波动距离与波动角度。其次，因为位置点只有一个，但生成轨迹是多条，所以要生成虚拟位置点，虚拟位置点的生成也是受到一定原则约束，因为生成的虚拟位置点若与信息请求用户相差甚远，则容易排除。最后，为了能够更好地保护隐私，本文构建轨迹时需要每条轨迹中既有相似位置点也需要有虚拟位置点，这样避免攻击者因为获取用户的一些背景知识而排除过多的混合轨迹。

轨迹构建过程(以构建3条轨迹为例)：

1) 初始位置生成，在真实用户初始位置点的周围一定范围内并且综合相似度度量寻找一个相似位置与2个虚假位置。

2) 为了防止每条混合轨迹中n个位置点发送信息请求时ID相异，在生成初始位置后将对每条混合轨迹赋予一个新的代号，其整条轨迹从始至终使用它。

3) 构建其他位置点，假设当前位置点的时间戳为t2，计算此时间与上一时间的距离，除此之外仍需要计算两者之间的连线与水平线(规定一个正方向为水平线，如正东)之间的夹角。混合轨迹t2，位置点的生成：(1) 确定波动距离；(2) 确定波动角度。

4) 假设此时已经确定波动距离与波动角度，而且真实位置点与水平线的夹角为θ1，两点之间的距离为d1。混合轨迹生成t2位置点，以混合轨迹的t1的位置点画出与水平线夹角θ2，距离为d2的扇形环，从环中随机选择一个位置点，记为混合轨迹t2时刻的相似位置点。

5) 除步骤4)生成的虚拟位置点外，每一时间戳都会生成一个相似位置点，将会随机从3个混合轨迹中选取一条轨迹，将此相似位置点加入该轨迹，方法如步骤6)。

6) 若算法选择该条混合轨迹在t3时刻为相似位置点，则直接连接t2与t3时刻位置点，若下一时刻为虚拟位置点，则如步骤4)，否则如步骤6)。

7) 循环步骤4)-步骤6)，直至轨迹构建结束。

如图5所示，图中有3条轨迹，在矩阵中相似位置点和虚拟位置共有3个，在T1时刻，无论是相似位置点还是虚拟位置点都将随机地匹配下一时刻T2中的任意类型点，递归生成混合轨迹，可以看出，生成的混合轨迹与真实用户的轨迹相似度高，并且真实用户不在混合轨迹中，可以有效地保护真实用户不被攻击。

图5 混合轨迹的生成

算法2生成混合轨迹的算法

输入：相似位置点集合S，虚拟位置点集合V，轨迹数量k，轨迹位置点数n。

输出: 混合轨迹集合Tr。

1) 初始化Point集合为空

2) 由算法1得出相似位置点集合S与虚拟位置点集合V

3) Fori,jinzip(S,V) do

4)Point.extend(i,j)

5) End for

6)Tr={}

7) Deftrack():

8) Foriinrange(k)do

9)Tri,0=random(Point0)

10)Point0.pop(tri,0)

11) End for

12) End def

13) Foriinrange(n)do

14)track()

15) End for

16) ReturnTr

从算法2可知，首先，从算法1中获取的相似位置点集合与虚拟位置点集合中选取各时刻的点，生成某一时间戳时刻的位置点集合，该集合包括一个相似位置点和多个虚拟位置点，其次，生成一个轨迹函数，通过调用n次该函数构建完整的混合轨迹。

定理2算法2的时间复杂度为O(k×n)。

证明2在混合轨迹构建中，组合虚拟位置点与相似位置点，需要遍历轨迹中每一个时刻，假若混合轨迹中共有n个点，则该方法的复杂度为O(n)。在轨迹构造函数中未使用复杂度较高的方法或函数，复杂度为O(k)，最后在生成最终轨迹时，通过循环n次完成，所以算法2的时间复杂度为O(k×n)。

4 实 验

本文使用的数据是gowalla数据集[21]，该数据集由微软研究院发布。其收集了182个用户从2007年4月到2012年8月的轨迹数据，数据按照严格的时间序列，生成了17 621条轨迹，共有48 000多小时的记录。记录了用户的工作地点和户外活动等。该数据集是用来进行用户相似度估算、隐私保护、户外推荐和数据挖掘的切合数据。

本文的实验语言为Python，与语言相对应的软件IDE为PyCharm64位Python3.6版本。IDE的运行环境为：Windows7 64位操作系统，处理器：Pentium(R) Dual-core CPU E5500 2.80 GHz。实验将与假轨迹生成法[22]VR-track和轨迹旋转法[23]ROT-track进行比较，进而体现本文算法的有效性和可行性。

如图6，本文算法的时间耗时比虚拟轨迹法略高，比旋转轨迹法低。因为在虚拟轨迹法中，虚拟轨迹的构建是寻找该时刻的查询点，以两点的距离建立误差范围，在误差范围内构建匿名区域，生成满足匿名等级的虚拟位置点的数量，而混合轨迹法与其相比，需要遍历寻找相似位置点，在找到相似位置点后，为了能够生成与真实轨迹足够相似的混合轨迹，仍要计算本文提出的相似角度与相似距离，因此耗时要长。由图6可以得出旋转轨迹法比其他方法耗时都要长，原因主要有三方面，即选取最优旋转点、计算平移位置、考虑真实地形。

图6 运行时间对比

在轨迹隐私保护中，轨迹的构建主要有两点。即虚拟轨迹的方向和与真实轨迹之间的距离。有定义4，本文结合轨迹方向和轨迹距离的相似程度度量构建的虚拟轨迹与真实轨迹的相似度。如图7所示，本文的混合轨迹比虚拟轨迹和旋转轨迹与真实用户的轨迹更加相似。虚拟轨迹使用的构建方法未能够严格要求虚拟轨迹的方向，并且构建虚拟位置点的环状区域过于广泛，导致相似度低。在旋转轨迹中，其优势在于轨迹是旋转生成的，轨迹的形状大小是与真实用户轨迹完全一致，但是由于相同的轨迹不能够在同一位置，为了避免轨迹重合需要对轨迹旋转和平移，导致旋转轨迹与真实用户轨迹不能够高度相似。

图7 轨迹相似度

轨迹隐私匿名度主要是使用信息熵进行量化，熵值代表着不稳定性，在隐私保护中，熵值越大代表轨迹隐私保护的效果越佳。如图8所示，旋转轨迹算法的信息熵最低，假设攻击者得到的背景知识能够解读到用户在某一时刻的真实请求信息位置点，攻击者可以由此判断出哪一条轨迹最贴近真实轨迹，出现该问题的原因在于，旋转轨迹法中平移和旋转导致生成的轨迹点与真实用户位置点的地理位置有较大的偏差，容易被排除。本文使用了相似位置代替真实用户发送消息，并且虚假位置是按照严格的生成方式生成，与真实用户在地理位置有相似优势，即使攻击者推测出真实用户的真实位置的模糊区域，但由于相似位置代替真实用户，仍然有效干扰攻击者判断，达到有效保护用户隐私的目的。最后，虚假轨迹法中，轨迹的行进方向与真实轨迹相差较大，虽然能够保护用户的隐私，但是不能像本文算法一样有效。通过对信息熵的分析，可以看出在匿名度低时，效率提高了5%，在匿名度高时，效率提高了15%左右，随着匿名度的逐渐提高，效率差逐渐平缓。

图8 轨迹保护算法信息熵对比

5 结 语

本文针对用户轨迹隐私中轨迹容易暴露问题，提出一种构建虚拟轨迹的新方法。在该方法中，第一步是寻找与真实信息请求用户相似度高的相似用户代替其构建轨迹，并且同时按照生成规则生成多个虚拟位置点，在下一时刻，相似位置点与虚拟点随机组合，如此循环构成相似位置点与虚拟位置并存的混合轨迹，并且给每条轨迹使用同一假名，完全达到轨迹隐私保护的目的。在实验中，通过运行时间、轨迹相似度、匿名度的对比，体现出本文算法对轨迹隐私保护、抵制攻击者的攻击具有高效用。

随着隐私保护数据量越来越大，本文接下来的研究工作的方向为降低寻找相似用户生成相似位置点的复杂度和构建混合轨迹的时间消耗，解决这些问题将会使本文算法更加优化。