基于MDF-Nearest算法的轨迹隐私保护方法

耿雪冬

摘 要：传统轨迹匿名方法在匿名集生成时没有考虑用户多种特征属性，在信息攻击下无法有效保护真实位置;在轨迹形成方面因没有将余弦角度和轨迹间距离作为形成的依据，导致某些虚假轨迹无法有效保护真实轨迹。为改善以上问题，构建一种依据用户多重特征信息构建的匿名集以保证匿名有效性;采用协作用户的真实轨迹并计算相似性，从而生成虚假轨迹相似性高的MDF-Nearest算法。实验结果表明，该方法随着k值的变大与生成轨迹数量的增多，隐私保护效果逐渐改进;与传统k匿名方法相比，该算法时间开销降低41.7%，而隐私保护程度可提高至97.1%。因此该方法能以较低的时间开销，提供质量可靠的位置服务，保护用户信息。

关键词：轨迹匿名;多重特征;余弦角度;轨迹间距离;MDF-Nearest算法

DOI：10. 11907/rjdk. 192030 开放科学（资源服务）标识码（OSID）：

中图分类号：TP309.7 文献标识码：A 文章编号：1672-7800（2019）009-0188-04

Trajectory Privacy Protection Method Based on MTF-Nearest+Algorithm

GENG Xue-dong

（College of Computer Science and Engineering， Shandong University of Science and Technology， Qingdao 266590， China）

Abstract：The traditional trajectory anonymity method does not take the users multiple feature attributes into account when generating the anonymous set， which leads to inefficient protection of the real position under the information attack. Whats more， the angle and the inter-track distance are not formed in the trajectory formation， and thus real trajectory cannot be effectively protected. This paper proposes an anonymous set based on the users multiple feature information to ensure the validity of the anonymity. The real trajectory of the collaborative user is used and the similarity is calculated to generate a false trajectory with high similarity. The experimental results show that with the value of k and the number of generated trajectories increases， the effect of privacy protection is better. Compared with the traditional k-anonymous method， the time cost of the algorithm is reduced by about 41.7%， while the degree of privacy protection is increased to about 97.1%. The method can provide high quality location services and protect user information with low time overhead.

Key Words： trajectory anonymity; multiple feature; cosine angle; distance between tracks; MDF-Nearest algorithm

0 引言

随着全球定位和无线通信技术的快速发展，公众享受到更便捷的出行方式，接触到更多陌生的场景，也因此催生了日益頻繁的基于位置的服务（Location Based Service，LBS）请求;然而在享受服务的同时，用户位置信息容易被不法分子获取，带来安全隐患。因此，如何兼顾良好的位置服务及高效的位置隐私保护成为当前研究热点与重点。

目前轨迹隐私保护方法主要有3种类型：①基于生成假轨迹的方法[1-2];②基于抑制信息发布的方法[3-4];③基于信息泛化的方法[5-6]。常用典型方法是k匿名方法[7]。文献[8-9]提出一种划分区域的保护方法，将用户活动区域分为两部分区域，但导致用户很难获得高质量的服务，且需防御各种攻击，如位置链接攻击[10]等;文献[11]利用差分算法完成了l-轨迹隐私保护;文献[12]提出一个拥有k个用户的k-匿名区域共享方案，通过加入其它k-1个相似用户连续查询请求达到保护的目的;文献[13]提出一种高效的轨迹隐私保护方法，基于用户真实地图背景及行为模式的相关特征构建其余k-1条虚假协作轨迹，保证轨迹隐私安全;文献[14]提出一种新的用户集匿名区域算法，但因算法实现需要知道用户未来位置，但未来位置难以有效预测，所以该算法并不具有现实性;文献[15]通过真假轨迹条件共同生成轨迹集;文献[16-17]利用连续查询中的需求建模，通过加密方式保证安全;文献[18]通过生成虚拟假人估计生成虚拟轨迹以保护真实轨迹;文献[19]通过预测和假位置机制获得k-1个混淆位置，将其匿名发送实现隐私保护;文献[20]选出多个满足时间关系的匿名候选者，用其轨迹代替真实轨迹以请求服务，实现保护目的;文献[21]通过基于差分隐私发布机制实现隐私信息保护。

以上方法在选择匿名用户集时，没有考虑用户相关属性，导致用户匿名集中，除了位置相近之外，其它属性不能完美掩盖，所以无法完成对用户的相似保护;另外单服务器的方式容易造成隐私信息泄露，攻击者可通过窃取消息获得用户大致范围请求。

针对以上问题，本文在双中间处理器的架构下，引入MDF-Nearest（Multi-dimensional Feature）算法，将用户多重属性转化为相应特征值，运用矩阵运算方法选取最相近用户匿名集合，并通过角度与距离的联合计算选择相似轨迹，将协作用户与用户真实轨迹结合，实现用户轨迹匿名隐私保护。双服务器的应用可有效解决单一服务器隐私泄露的风险，而MDF-Nearest方法的匿名选择和轨迹生成可实现对用户轨迹的有效保护。

1 轨迹隐私保护模型及相关定义

1.1 系统模型

系统运行过程包括：①用户首先通过MDF-Nearest方法聚合除用户外的k-1个用户，将真实用户位置与协作用户位置一同发送到中间服务器上;②用户将k个用户位置和服务请求分别发送到不同服务器上，两个服务器分别接收部分信息，并通过随机生成的编号保持其相同编号属于同一用户;③LBS服务器在接收中间服务器转发来的信息后，将相应请求的应答信息返回至中间处理器，中间处理器将其原封不动地返回;④用户端只接收自己在相应位置的结果信息，将信息求精后返回给用户。

该系统模型的优点是攻击者不能从单个中间处理器上获得任何有效信息，即使中间服务器共谋，在获得信息后，由于采用的是假名，在没有经过用户端处理之前，无法得知真实用户位置信息。同时，LBS服务器在服务器端也无法整合两个服务器传来的数据，保证了用户信息数据安全。该系统由用户、中间处理器和LBS服务器构成。

携带智能终端设备的用户可通过多种方式接入网络，并通过响应设备在不同时间、不同地点请求不同的服务。

中间处理器指介于用户和LBS服务器之间的处理器实体，任务是接受用户传来的信息，发送数据到LBS服务器，保证用户信息隐私。

LBS服务器是一个服务提供者，该服务器可以根据发送来的请求信息，搜寻结果后返回给发送方。

1.2 相关定义

（2） 轨迹间距离。设轨迹泛化完成后[T′]={T1，T2，…，T3}，则T和[T′]在[ti，ti+1]的距离为：[D（Tti，ti+1，Tti，ti+1）=][mti-nti2+mti+1-nti+12]。轨迹T和[T′]之间的距离为：

（3） 轨迹k匿名。设有多条轨迹的集合S，当集合S中某条轨迹与其它k-1条轨迹不可分时，则集合S满足轨迹k匿名。

2 隐私保护方法

2.1 MDF-Nearest 匿名集生成方法

使用用户匿名集的目的是为了防止中间处理器被攻击者攻击造成隐私泄露，同时增加中间处理器可防止用户端直接与LBS服务器进行通讯，以免造成LBS服务器隐私泄露。因此，用户端在发送位置时，首先要进行混淆处理。用户端匿名集生成主要思想包括：①用户通过定位设备获得自己真实位置所在区域;② 依据该区域，通过用户端混淆算法生成符合要求的位置点集合;③ 随机给集合中的位置点编号，然后发送至中间处理器，再经由中间处理器处理后发送至LBS服务器。

2.2 基于多特征的MDF-Nearest伪代码

MDF-Nearest算法

输入：用户位置点[P（xi，yi）]，查询内容[（Content）]，用户所在区域[（GUD）]，时间[（Ti）]

输出：根据用户需求及其它多个特征属性结合生成的最相近位置点集合

算法前3步为用户端选择的协作用户在真实用户区域内与在可信时间内能够到达的用户集合算法步骤，步骤4-11表示将每一个符合区域与时间的用户进行多维特征计算，首先获取相同可达时间内协作用户位置及相关特征或属性，建立一个矩阵，矩阵行列分别表示协作用户及其属性，将全部属性作为列值，某一协作用户若有该属性，则加注标记;若没有，不加标记。该矩阵每加入一条新的用户，便对其进行一次随机行变换，该过程可以在[O（n）]时间内完成。步骤12指将结果集发送给中间处理器。

2.3 中间处理器多轨迹生成方法

中间处理器根据用户端发来的轨迹点匿名集合，根据中间处理器存储的历史轨迹消息处理集合点，根据时间可达性、余弦角度和轨迹距离公式实现多轨迹匿名生成;然后将生成的k条轨迹发送给LBS服务器，LBS服务器根据中间处理器发来的信息提供服务，再将请求应答信息发送至中间处理器，由中间处理器下发至用户端，用户从用户端接受自己真实的请求应答信息。

2.4 基于中间处理器的轨迹生成保护算法

3 实验及分析

3.1 试验设备参数

实验主要从查找最匹配用户的协作用户、中间处理器进行匿名与轨迹生成处理， 以及向LBS服务器发送查询请求等方面进行测试，再与k匿名算法进行仿真实验比较。实验数据集由Brinkhoff随机生成器生成，以英国纽卡斯尔市交通网络图（区域面积为27km*29km）作为输入，生成了1 000条轨迹数据。查询对象数据随机分布，本实验随机选择一个点作为模拟用户的点，对算法相关属性进行测试。实验硬件环境为：AMD  A8-5550m  CPU@2.1GHz  4 Cores，4.00GB內存，操作系统为Microsoft Windows 10 64 bit操作系统，采用Anaconda平台，用Python语言实现。

3.2 实验结果分析

本文通过试验验证算法有效性，从响应时间和隐私保护度两方面与不同k值的传统k-匿名算法进行比较，传统k-匿名保护算法的隐私保护度指标仅与k值有关。两种算法对比结果如图2所示。

从图2可以看出，当用户在选择自己相近匿名协作用户时，随着k值的不断增大，系统响应时间随之增加。随着k的变化，传统k-匿名算法在选择用户时，由于数据增多，计算量不断攀升;而本文采取的算法虽然随着k值增大，开销时间也在增长，但增长幅度比较缓慢，与传统k-匿名方法相比，本文算法在响应时间上时耗较少。

在不同方式的轨迹隐私保护算法中，系统响应时间与相应用户隐私保护程度是一对矛盾体。因此，在保证系统响应时间的前提下提升隐私保护程度是反映算法优劣的重要指标。图3展示的是本文算法与传统k-匿名算法在隐私保护度上的对比。

由图3可以看出，本文提出的MDF-Nearest算法与传统k-匿名算法在k值较小时相比，二者差距并不是很大，但是随着用户数量的增多，MDF-Nearest算法对用户的保证程度明显增大。这是因为到达一定数量时，根据角度及轨迹距离等多种条件生成的相似性高的轨迹数量不断增多，所以，k值越大，MDF-Nearest算法对于用户轨迹保护程度越好。

4 结语

本文主要针对传统轨迹匿名算法在匿名区域形成和轨迹聚合混淆时，由于未能考虑用户特征及轨迹形成条件，容易造成攻击者识别出用户轨迹的问题，提出了一种利用集合用户多重特征属性、角度和轨迹距离生成虚假轨迹的方法，提高了用户可分辨难度，并根据余弦角度和轨迹距离进一步生成更加接近真实轨迹的虚假轨迹，使攻击者无法重构用户真实轨迹，从而提高轨迹保护性。同时，通过用户轨迹保护度还可衡量虚假轨迹隐私泄露程度。试验表明，该方法能够获得较好的轨迹隐私保护。

下一步将考虑在构造用户轨迹方面，如何更好地将用户历史轨迹特征与真实位置点请求结合起来，还将充分考虑时空关联性以便生成迷惑性更高的虚假轨迹，以及如何提高用户位置点匿名集合的可信性、混淆性与可用性，更有效地提高用户服务质量。

参考文献：

[1] 董玉兰，皮德常. 一种基于假数据的新型轨迹隐私保护模型[J]. 计算机科学， 2017， 44（8）： 124-128.

[2] 雷凯跃，李兴华，刘海，等. 轨迹发布中基于时空关联性的假轨迹隐私保护方案[J]. 通信学报， 2016， 37（12）： 156-164.

[3] 赵婧，张渊，李兴华，等. 基于轨迹频率抑制的轨迹隐私保护方法[J]. 计算机学报，2014，37（10）： 2096-2106.

[5] KOMISHANI E G，ABADI M，DELDAR F. PPTD： preserving personalized privacy in trajectory data publishing by sensitive attribute generalization and trajectory local suppression[J]. Knowledge-Based Systems， 2016， 94： 43-59.

[6] CHEN R，FUNG B C M，MOHAMMED N，et al. Privacy-preserving trajectory data publishing by local suppression[J]. Information Sciences， 2013， 231： 83-97.

[7] EL OUAZZANI Z， El Bakkali H. A new technique ensuring privacy in big data： k-anonymity without prior value of the threshold k[J]. Procedia Computer Science， 2018， 127： 52-59.

[8] 霍峥，孟小峰，黄毅. PrivateCheckIn： 一种移动社交网络中的轨迹隐私保护方法[J]. 计算机学报， 2013， 36（4）： 716-726.

[9] HUANG L，MATSUURA K，YAMANE H，et al. Enhancing wireless location privacy using silent period[C]. IEEE Wireless Communications and Networking Conference， 2005： 1187-1192.

[10] HUANG L， YAMANE H， MATSUURA K， et al. Silent cascade： enhancing location privacy without communication QoS degradation[C]. International Conference on Security in Pervasive Computing， 2006： 165-180.

[11] DING Y，PEDDINTI S T，ROSS K W. Stalking Beijing from Timbuktu： a generic measurement approach for exploiting location-based social discovery[C]. Proceedings of the 4th ACM Workshop on Security and Privacy in Smartphones & Mobile Devices， 2014： 75-80.

[12] CAO Y，YOSHIKAWA M. Differentially private real-time data release over infinite trajectory streams[C]. The 16th IEEE International Conference on Mobile Data Management， 2015： 68-73.

[13] CHOW C Y，MOKBEL M F. Enabling private continuous queries for revealed user locations[C]. International Symposium on Spatial and Temporal Databases， 2007： 258-275.

[14] 李凤华，张翠，牛犇，等. 高效的轨迹隐私保护方案[J]. 通信学报，2015，36（12）：114-123.

[15] WANG Y，XU D，HE X，et al. L2P2： location-aware location privacy protection for location-based services[C]. Proceedings of IEEE INFOCOM， 2012： 1996-2004.

[16] 胡德敏，郑霞. 基于连续查询的用户轨迹 k-匿名隐私保护算法[J]. 计算机应用研究，2017 （11）： 3421-3423+3427.

[17] 周凯，彭长根，何建琼，等. 可证明安全的 LBS 中连续查询的轨迹隐私保护方案[J]. 信息网络安全， 2017 （1）： 43-47.

[18] HAYASHIDA S，AMAGATA D， HARA T， et al. Dummy generation based on user-movement estimation for location privacy protection[J]. IEEE Access， 2018， 6： 22958-22969.

[19] 張少波，刘琴，王国军. 基于位置混淆的轨迹隐私保护方法[J]. 通信学报，2018，39（7）：81-91.

[20] 宋成，张亚东，王磊，等. 基于 DTW 交换查询的轨迹隐私保护方案[J]. 北京邮电大学学报， 2018 （6）： 16.

[21] 吴云乘，陈红，赵素云，等. 一种基于时空相关性的差分隐私轨迹保护机制[J]. 计算机学报，2018， 41（2）：309-322.

（责任编辑：江 艳）