基于轨迹方向的轨迹隐私保护算法

邱 明，皮德常

（南京航空航天大学 计算机科学与技术学院，南京 210016）

1 引 言

随着各种各样移动定位设备的普及，基于位置的服务（Location Based Services，LBS）［1－2］在日常生活中的用处越来越广泛．但在LBS给人们带来各种便利的同时，也有人发现越来越多的人由于LBS而在无意中泄露出自己的身份、行为模式、兴趣爱好等隐私信息［3］．如果这些隐私信息被不法分子获得，那么后果将无法想象．在位置服务中，用户的位置精确程度决定着服务的质量，所以如何在保证服务质量的前提下实现用户的隐私保护是研究的热点．

隐私保护作为一个新兴的研究热点，一直都倍受关注．Kido和Yanagisawa［4］在2003年提出采用一种在用户周围生成虚假用户的方法来实现用户的隐私保护．虽然此方法没有考虑到连续查询时会出现的隐私泄露问题，但这给很多人打开一个思路，随后You和Peng［5］从用户轨迹出发介绍了两种生成虚假用户的方法：随机生成法（Random Pattern Scheme）和旋转模式生成法（Rotation Pattern Scheme）．

此外，Sweeney［6］采用泛化的思想，提出了轨迹隐私保护中最常用的k－匿名模型，该技术的核心思想是将准标识符进行泛化，并且一次性发布k条不可区分的记录，使得攻击者无法将获得的隐私消息和用户的具体身份进行正确的匹配，从而保护了用户的个人隐私．Terrovitis等人［7］从数据发布时有选择性地发布数据这个角度，提出了基于抑制法的轨迹隐私保护技术，它是指在轨迹数据发布的时候对预发布的数据进行选择，将某些位置信息不予以发布来实现轨迹隐私保护［8－9］．

2 假轨迹方法

2．1 假轨迹方法概述

假位置方法是在位置隐私保护技术中一种广泛使用的简单有效的方法．假位置方法即在位置数据发布时使用假位置来代替真实的位置以获取服务的技术［10］．相似地，在轨迹数据隐私保护中，同样可以使用假轨迹法，假轨迹法的核心思想是给每一条轨迹生成多条相近的假轨迹来减小真实轨迹被暴露的概率．例如，在表1中存储了原始轨迹数据，移动对象O1，O2，O3在t1，t2，t3时刻的位置存储在数据库中，形成了3条轨迹．

表1 原始数据Tab．1 Primary data

表2是对原始数据进行假轨迹扰动后的结果．经过假轨迹扰动后的表2中共含有6条假轨迹，其中O1，O2，O3分别是移动对象O1，O2，O3的假名．O4，O5，O6是生成的假轨迹的假名，每条轨迹被暴露的概率都降为了1／2．很容易发现随着生成的假轨迹的数目的增加，轨迹被暴露的概率将会减小．

表2 用假轨迹法干扰后的轨迹数据Tab．2 Trajectory data with dummies

一般来说，假轨迹方法要考虑以下几个方面：

（1）假轨迹的数量．假轨迹的数量越多，披露风险越低，但是同时对真实数据产生的影响也越大，因此假轨迹的数量通常根据用户的隐私需求选择折衷数值；

（2）轨迹的空间关系．从攻击者的角度看，从交叉点出发的轨迹易于混淆，因此应尽可能产生相交的轨迹以降低披露风险；

（3）假轨迹的运行模式．假轨迹的运动模式要和真实轨迹的运动模式相近，不合常规的运行模式容易被攻击者识破．

2．2 假轨迹方法的实现

针对上述3种要求，出现了两种生成假轨迹的方法：随机模式生成法和旋转模式生成法．

（1）随机生成法．随机生成一条连接起点到终点、连续运行且运行模式一致的假轨迹．

（2）旋转模式生成法．以移动用户的真实轨迹为基础，以真实轨迹中的某些采样点为轴点进行旋转，旋转后的轨迹为生成的假轨迹．旋转点的选择和旋转角度的确定需要和信息扭曲度进行关联权衡．旋转模式生成法生成的假轨迹与真实用户的运动模式相同，并和真实轨迹有交点，难以被攻击者识破．

3 基于轨迹方向的轨迹隐私保护算法

3．1 系统结构

基于轨迹方向的轨迹隐私保护算法采用的系统结构是基于中心服务器的结构，在移动终端和基于位置的（LBS）服务器之间添加一个可信的中心匿名服务器，用户与中心匿名服务器之间的通信必须加密，而中心匿名服务器之间的通信不需加密，攻击者可以监听，获取消息．此系统结构中请求查询的过程如图1所示．

图1 系统结构图Fig．1 System structure diagram

（1）用户通过各种移动终端将当前位置信息，隐私保护参数及查询内容一起打包发给匿名服务器；

（2）中心匿名服务器将采用基于轨迹方向的轨迹隐私保护算法进行匿名处理后的数据一起打包发给LBS服务器获取服务；

（3）LBS服务器将查询的结果打包发给中心匿名服务器；

（4）中心匿名服务器从获得的结果中挑出用户真正需要的结果发送给用户．

3．2 相关知识

将平面地图划分为若干个100＊100的网格，坐标（x，y）表示用户在地图中的位置，定义用户的查询消息为为身份信息，Ti为i时刻用户的真实位置，而，…为i时刻中心服务器为用户生成的k个假位置，在用户连续运动且连续发出服务请求的t时间内，假设用户的真实轨迹为（T0，T1，T2，…，Tt），对应的虚假轨迹为

定义1 短期泄露风险（Short－term Disclosure，SD）［5］：这个参数是用来保护用户当前位置的．假设给了一组当前位置集合（包含真实位置和虚假位置），SD是成功识别用户真实位置的概率．m是一条轨迹中时间戳数目，Di是i时刻用户的真实位置和虚假位置集合，而｜Di｜是集合Di的大小，则有公式（1）

定义2 长期泄露风险（Long－term Disclosure，LD）［5］：这个参数是用来保护用户轨迹的．假设有n条轨迹，其中有k条轨迹与其他轨迹有交点，剩下的n－k条轨迹与其他轨迹没有交点．其中，k条相交的轨迹可生成Nk条轨迹，则有公式（2）

定义3 局部方向偏移角度（Local Directional Deviation Angle，LDDA）：假设用户的当前位置为Tp，上一个位置为Tp－1，假轨迹中的第m条虚假轨迹当前生成的虚假位置为，且该假轨迹的上一个位置为，那么LDDA就是向量（Tp－1，Tp）和向量，）之间的夹角．

定义4 整体方向偏移角度（Global Directional Deviation Angle，GDDA）：假设用户的当前位置为Tp，起始位置为T0，虚假轨迹中的第m条虚假轨迹当前生成的虚假位置为，且该假轨迹的起始位置为，那么GDDA就是向量（T0，Tp）和向量，）之间的夹角．

定义5 距离偏差（Distance Deviation，DD）：假设用户的当前位置为Tp，上一个位置为Tp－1，虚假轨迹中的第m条虚假轨迹当前生成的虚假位置为，且该假轨迹的上一个位置为，那么DD就是其中dist（a，b）表示a，b两点之间的欧氏距离，｜x｜表示x的绝对值．

定义6 隐私参数（Privacy Parameter，PP）：PP＝（sd，，ld，dmin，dmax，θ，ω，dd），其中sd为短期泄露风险LD最大值；而sd为长期泄露风险SD的最大值，dmin为虚假用户与真实用户之间的最短距离；dmax为虚假用户与真实用户之间的最远距离；θ为LDDA的最大值；ω为GDDA的最大值；dd为距离偏差DD的最大值．

3．3 基于轨迹方向的轨迹隐私保护算法

在生成虚假位置的时候，需要考虑新生成的虚假位置是否满足下述三个原则：

（1）速度一致性原则

虚假用户的速度应与真实用户的速度保持一致，不可比真实用户快太多，也不可慢太多．通过判断DD是否在用户限定的范围内来判断生成的假轨迹是否满足速度一致性原则．

（2）临近原则

虚假用户的位置与真实用户的位置不可太近也不可太远，因为当虚假用户距离真实用户太远之时，虚假用户无法很好地起到隐私保护的作用；而虚假用户距离真实用户太近又容易造成真实用户的轨迹隐私泄露．所以虚假用户应在真实用户周围的一个环形区域内．

（3）方向一致性原则

生成的假轨迹的方向要与真实用户的轨迹大致相同，包括局部方向相似以及整体方向相似．分别通过判断LDDA和GDDA是否在用户限定的范围内来判断假轨迹与真实轨迹是否满足局部方向相似和整体方向相似．

基于以上原则，本文提出了一种基于轨迹方向的轨迹隐私保护算法（Trajectory Privacy

Preserving Algorithm Based on Trajectory Direction，TPPA－TD）．

1．Algorithm：TPPA－TD

2．Input：User’s position sequence（T0，T1，T2，…，Tp）

Dummies position information

Privacy parameters pp＝（sd，，ld，dmin，dmax，ldda，gdda，dd）；

3．Output：The set of dummies position information

4．BEGIN

5．IF（p＝＝0）

6．k＝1／min（ld，sd）－1

7．FOR m＝1To k

8．REPEAT

9．REPEAT

11．UNTIL（dmin＜＝dist（Tp，）＜＝dmax） ／／dist（x，y）返回x与y之间的距离

12．Calculation SD by formula 3－1

13．Calculation LD by formula 3－2

14．UNTIL（SD＜＝sd＆＆LD＜＝d）

15．END FOR

16．ELSE

17．FOR m＝1To k

18．REPEAT

19．REPEAT

21．UNTIL（dmin＜＝dist（Tp，）＜＝dmax）

22．Calculation SD by formula 3－1

23．Calculation LD by formula 3－2

25．／／CAngle（x，y，m，n）返回向量（x，y）和向量（m，n）之间的夹角

27．Calculation DD＝｜dist（Tp－1，Tp）－dist

28．UNTIL（SD＜＝sd＆＆LD＜＝ld＆＆LDDA＜＝ldda＆＆GDDA＜＝gdda＆＆DD＜＝dd）

29．END FOR

30．END IF

31．END

4 实验结果与分析

算法采用Java编写，实验环境为Microsoft Windows 7Professional操作系统，处理器为3．20GHZ的Intel Core i5－3470CPU，内存为4GB．

实验数据来自Thomas Brinkhoff路网中的移动对象数据生成器［11］和德国古登堡市地图．将地图划分为100＊100的单元格，用单元格的中心位置来表示位置，在同一单元格中的不同位置默认为相同位置．

图2中给出了两种算法的结果，左图为本文提出的TPPA－TD的运行结果，右图为随机生成法的运行结果．实验参数ld＝20%，sd＝25%，θ为30，ω为30，dd为100，dmin为150，dmax为240，两图中的红色轨迹均为用户的真实轨迹，其余四条均为假轨迹．从图中可以看出，由于考虑到了用户的运行速度以及运行方向等因素，TPPA－TD生成的假轨迹与随机生成法生成的假轨迹相比更为逼真，更不容易被攻击者利用速度攻击等手段识破假轨迹．

图2 两种算法结果Fig．2 The results of two algorithms

图3为两种算法生成的假轨迹数目和随ld的变化情况对比，横坐标为ld的取值，纵坐标为算法生成的假轨迹数目，实验轨迹为生成器生成的一条包含4个位置的轨迹．其余参数：θ为30，ω为30，dd为100，dmin为150，dmax为240．

图3 生成的假轨迹数目与ld的关系Fig．3 The relationship between ld and the number of dummies

图4为两种算法生成的假轨迹数目和随sd的变化情况对比，横坐标为sd的取值，纵坐标为算法生成的假轨迹数目，实验的轨迹为一条包含4个位置的轨迹．其余参数：θ为30；ω为30，dd为100，dmin为150，dmax为240．

图4 生成的假轨迹数目与sd的关系Fig．4 The relationship between sd and the number of dummies

图5为用户轨迹暴露的概率与ld的取值关系图，其中横坐标为ld的取值，纵坐标为用户轨迹暴露的概率，实验轨迹为生成器生成的一条包含4个位置的轨迹．其余参数：θ为30，ω为30，dd为100，dmin为150，dmax为240．从图中我们可以看出当用户的隐私参数ld较大时，TPPA－TD算法与随机生成法这两种算法中用户轨迹被暴露的概率相近，但是当用户的隐私参数ld较小时，TPPA－TD算法中用户的轨迹被暴露的概率将小于随机生成法中用户轨迹被暴露的概率．因此，当用户隐私保护程度较高时，TPPA－TD算法可以更好地保护用户的轨迹隐私．

图5 用户轨迹暴露的概率与ld的关系Fig．5 The relationship between ld and the probability of user’s trajectory being exposed

结合上述三图，我们可以知道在用户要求的隐私保护程度较低时，TPPA－TD生成的假轨迹数目与随机生成法生成的数目相近．此时为了降低响应时间可以采用随机生成法来生成虚假轨迹，而在用户的隐私保护要求较高的时候，TPPA－TD生成的假轨迹数目较多，可以减小用户的真实轨迹被发现的概率；同时，由于考虑到了轨迹的速度以及方向这两个因素，生成的假轨迹也将与真实的轨迹更加相似，可以减小虚假轨迹被攻击者识破的可能性．

5 结 论

针对位置服务中连续查询时的轨迹隐私保护问题，本文提出了基于轨迹方向的轨迹隐私保护算法TPPA－TD，在生成虚假轨迹的时候不仅考虑到用户的速度还考虑到用户的运动方向．与传统的随机生成法相比，在用户隐私保护需求较高的时候，TPPA－TD可以生成更多的假轨迹，同时生成的假轨迹与真实轨迹非常相似，不容易被攻击者所识破，更加符合实际应用的要求．

［1］CHOW C Y，MOKBEL M F．Query－aware location anonymization for road networks［J］．Geoinformatica．2011，15（3）：571－607．

［2］周傲英，杨彬，金澈清，等．基于位置的服务：架构与进展［J］．计算机学报，2011，34（7）：1155－1171．

［3］霍峥，孟小峰．轨迹隐私保护技术研究［J］．计算机学报，2011．34（10）：1820－1830．

［4］KIDO H，YANAGISAWA Y，SATOH T．Protection of location privacy using dummies for location－based services［C］／／The 21st International Conference on Data Engineering Workshops．2005：1084．

［5］YOU T，PENG W，LEE W．Protecting moving trajectories with dummies［C］／／2007International Conference on Mobile Data Management．Mannheim：IEEE，2007：278－282．

［6］SWEENEY L．k－anonymity：A model for protecting privacy［J］．International Journal on Uncertainty，Fuzziness and Knowledge－based Systems，2002，10（5）：557－570．

［7］TERROVITIS M，MAMOULIS N．Privacy preserving in the publication of trajectories［C］／／Proceedings of the 9th International Conference on Mobile Data Management（MDM 2008）．Beijing：2008：65－72．

［8］ABUL O，ATZORI M，BONCHI F，et al．Hiding sensitive trajectory patterns［C］／／Proceedings of the 7th IEEE International Conference on Data Mining Workshops（ICDMW 2007）．Singapore：2007：693－698．

［9］GRUTESER M，LIU X．Protecting privacy in continuous location－tracking applications［J］．IEEE Security and Privacy，2004，2（2）：28－34．

［10］KIDO H，YANAGISAWA Y，SATOH T．An anonymous communication technique using dummies for location based services［C］／／Proceedings of the 21st International Conference on Data Engineering Workshops．2005：1248．

［11］BRINKHOFF T．Generating network－based moving objects［C］／／The 12th International Conference on Scientific and Statistical Database Management．Washington：IEEE Computer Society，2000：253－255．