近年来，移动定位技术、基于位置的服务的发展及智能手机的普及使得大量的移动位置数据被各机构采集和存储。从数据挖掘与知识发现的角度来讲，大量的个人位置数据价值很高，可协助政府机构及各种商业机构作出与位置服务相关的决策。例如，如何规划公交车路线使得乘客数量与行进路线达到最优化？哪个商业地段人流量较大适合开设商铺等。但是轨迹中包含的信息可能导致个人隐私的泄露，比如，该用户所处的位置的泄露、用户的行进轨迹的泄露等。所谓个人隐私，指的是个人不愿被外界知晓的信息，如个人的健康状况、政治信仰、兴趣爱好等[1]。针对这些问题，学者们对查询隐私保护技术和位置隐私保护技术进行了深入的研究，并得出一些重要的结论。近年来，轨迹隐私保护技术得到了研究者们的关注。然而，在数据发布过程中的轨迹隐私保护假设服务器或数据收集机构都是可信的，将原始轨迹数据可直接发送给数据收集者。甚至有些智能手机在用户不知情的情况下，每隔一段时间向手机生产商发送一个位置数据。若原始数据泄露，会导致大量用户的隐私泄露，文献[2]指出：由于隐私泄露导致的各种社会事件层出不穷。
另外，目前的轨迹隐私保护技术有：添加噪声数据[3-4]、轨迹片段抑制[5]及k-匿名技术[6-10]。其中，轨迹k-匿名是最常用的技术，该技术将k条轨迹上对应的采样位置匿名在同一个区域中。然而，轨迹k-匿名技术存在如下问题：第一，轨迹k-匿名形成的匿名区域是由用户轨迹上的采样位置构成的，因此，匿名区域中的位置极可能因缺乏多样性而导致用户的隐私泄露。如图 1(a)所示，在路网环境中，将路段v0→v1→v2→v3→v4上的T1, T2, T3三条轨迹匿名为图 1(b)所示的效果，达到轨迹3-匿名，即便如此，攻击者很容易知晓任一用户的行进路线，因为3条轨迹都在路网中的同一条路径上。第二，单纯的轨迹k-匿名并不适用于路网空间中的轨迹隐私保护，这是由于在路网空间中，攻击者的背景知识更加丰富，文献[11]指出：地图上的道路特征(单行道、岔路口)、人流量的密度、移动对象的最大运行速度等信息都可作为攻击者的背景知识。
|
图 1 路网中的轨迹3-匿名 Figure 1 Trajectory 3-anonymity under road network constraint |
在路网环境中，仅有语义位置才可能泄露用户的个人隐私，其他位置并不会泄露用户的个人隐私。文献[3]提出了一种路网环境中添加假位置的轨迹隐私保护技术，然而，路网信息是攻击者掌握的背景知识，通过路网信息很容易分析哪些是假位置，带来隐私泄露风险。针对上述问题，本文提出感知隐私的轨迹数据采集方法PTDC。与轨迹k-匿名技术不同，该方法不对移动对象的轨迹进行匿名，而是对地图上的兴趣位置进行匿名，根据轨迹的行进方向、道路特征等信息，将用户的轨迹实时匿名，并将匿名后的数据发送给服务器或数据收集机构。该方法可在路网环境背景知识丰富的情况下，达到轨迹匿名的效果。从数据可用性的角度来讲，本文的做法也是可行的，这是由于对大多数位置数据分析来说，并不需要查询某个移动对象的确切位置，仅需查询某一区域内移动对象的数量即可，即，在空间范围查询上的误差率越小越好。
具体来说，本文的主要贡献如下：
1) 本文提出一种感知隐私的轨迹数据采集方法PTDC，可在移动对象运行过程中，实时对轨迹上的采样位置进行匿名，数据采集机构也无法获得原始数据，降低了隐私泄露的风险；
2) 本文提出了一种k-θ-D匿名模型以抵御语义位置同质性攻击。该匿名模型的隐私保护度至少为k，且k个被匿名的兴趣位置的敏感性差异尽可能大，以抵御语义同质性攻击。
3) 针对k-θ-D匿名模型，提出了一种基于广度优先遍历的满足兴趣位置差异性的匿名算法。
4) 在真实数据集上对PTDC方法的数据可用性、空间范围查询误差率及运行时间进行了实验验证，实验结果表明PTDC算法的数据可用性和空间查询误差率均和自由空间中的YCWA(You Can Walk Alone)算法有可比性，且运行效率远远优于YCWA算法，能满足实时在线处理的需求。
1 预备知识下面介绍本文算法的预备知识。
1.1 系统结构本文使用图 2所示的系统架构。该架构包括客户端、隐私保护服务器两个组件。客户端将原始位置数据发送给隐私保护服务器，在隐私保护服务器中完成数据预处理及隐私保护两个处理。匿名后的数据直接形成可发布数据，可供其他应用程序进行挖掘或统计。即使数据采集部门也无法获得原始轨迹数据，隐私暴露风险降低。
|
图 2 感知隐私的轨迹数据收集系统结构 Figure 2 Architecture of privacy-preserving trajectory data collection system |
定义1 轨迹。轨迹T是采样位置按时间排序构成的序列T={(x1, y1, t1), (x2, y2, t2), …, (xn, yn, tn)}，每个采样位置表示为一个三元组(xi, yi, ti)，其中，(xi, yi)表示采样位置的坐标，ti表示该位置的采样时间。
定义2 兴趣位置(Point Of Interest, POI)。兴趣位置是地理信息系统中的术语，指一切可以抽象为点的语义地理对象，尤其是一些与人们生活密切相关的地理实体，如学校、银行、餐馆、加油站、医院、超市等。
定义3 路网空间。路网空间用无向加权图G＝(V，E，W)表示。其中：V表示顶点的集合，兴趣位置和道路连接点被视作顶点; E是边的集合，若顶点vi和vj之间有一条不经过任何其他顶点就可以连接起来的路径，则称vi和vj之间有边(vi, vj); W表示图G的权值的集合。
1.3 路网空间中的攻击模式本节提出了三种路网中的攻击模式。
第一种 敏感兴趣位置攻击。路网环境中的地图信息是公开的，攻击者可以获取任意经纬度对应的兴趣位置。当移动对象运行至敏感位置附近时，会暴露其位置隐私。即使其在靠近某个敏感兴趣位置时关闭位置服务，攻击者依然可以根据移动对象的运行轨迹推导出其所访问的敏感位置。
第二种 语义位置攻击。为了防止上述敏感兴趣位置攻击，可将几个兴趣位置匿名在同一个匿名区域中。若有些位置是路网上不可达的，则可能造成隐私保护不足的情况。极端情况下，匿名区域中仅有一个可达的语义位置，移动对象的位置就泄露了。图 3所示为一个位置3-匿名区域，攻击者很容易推断出移动对象不可能在湖泊或无人自然保护区中，移动对象在医院的敏感信息也遭到泄露。
|
图 3 兴趣位置3-匿名区域 Figure 3 POI 3-anonymity area |
第三种 语义位置同质性攻击。若匿名区域中的兴趣位置敏感性相近，则仍可能导致隐私的泄露。例如，将几个敏感度都很高的医院、宾馆、酒吧匿名在一起，同样会造成用户的隐私泄露。
上述三种攻击类型中，语义位置同质性攻击是最强的攻击模式。如果隐私保护算法能够抵御语义位置同质性攻击，则可抵御上述三种攻击模式。
2 PTDC算法与之前的轨迹隐私保护算法不同，PTDC算法不对轨迹数据匿名，而是对路网环境中的兴趣位置进行匿名。PTDC算法的处理过程如图 4所示。
|
图 4 PTDC算法架构 Figure 4 Architecture of PTDC algorithm |
其中，POI敏感性计算模块负责计算地图上各个POI的敏感性，根据得到的POI敏感性及用户的隐私需求，由POI匿名区域生成模块生成地图上的匿名区域。这两个模块的处理可离线完成。此外，PTDC算法在对用户位置数据匿名之前，先对用户的当前位置进行评估，如果可能暴露其隐私，则需对该位置进行实时匿名。
2.1 POI敏感性计算要将POI匿名为一个区域，首先需计算每个POI的敏感性，即，该位置能暴露用户多少隐私。例如，如果将地图上邻近的3个不同的医院匿名在一起，攻击者还是知晓该用户患了某种疾病。据观察，一个POI的敏感性通常与它的“流行度”有关，即，访问该POI的用户是少数还是普遍。例如，一条道路的敏感性较低，这是由于任何人都可以行进在这条道路上。本文采用熵的方式定义POI的敏感性。
定义4 敏感性。设L是地图上某兴趣位置，v(L)={u1, u2, …, um}是一组访问过L的用户，用pi表示每个用户ui访问L的次数，
从定义中可以看出：敏感性越高的POI，其暴露用户隐私的可能性越大，其熵越小，也就是重复访问的人次越少；敏感性越低的POI，其熵越大，也就是重复访问的人次越多。
2.2 POI匿名区域生成算法将路网模拟到无向图G=(V, E, W)上，给定用户的隐私需求k，隐私保护技术需对地图上的POI进行匿名，每个匿名区域中至少包含k个POI。然而，传统的轨迹k-匿名技术无法抵御语义位置同质性攻击。本文定义了一种k-θ-D匿名模型可抵御此类攻击，具体定义如下。
定义5 k-θ-D匿名。给定路网G＝(V, E, W)和隐私保护度k，k-θ-D匿名是指对路网中POI的匿名需满足以下条件：1) 每个匿名区域中至少包含k个POI；2) k个POI的敏感性差异尽可能大；3) k个POI之间的距离尽可能近。
上述条件1) 和2) 是为了保证隐私保护的程度，条件3) 是为了保证生成的匿名区域面积尽可能小，使得采集到的数据有较高的数据可用性。为了保证匿名模型能满足条件2) 和条件3) 的要求，本文定义了θ-边权以同时衡量顶点的敏感性差异及距离两个参数，具体定义如下：
定义6 θ-边权。给定路网无向图G=(V, E，W), 顶点的权值wv1, wv2, …, wvn表示该顶点的敏感性；边(vi, vj)的权值wij可以表示为：
匿名算法的目的是：将距离较近且敏感性差异性较大的k个顶点构成匿名区域。根据θ-边权的定义，将与θ-边权较大的边相关联的顶点放入匿名区域中。首先，将图G中与每个顶点相关联的边，按其θ-边权值由大到小进行排序。从顶点vi出发，按广度优先搜索算法进行匿名。依次访问与其邻接的顶点vi1, vi2, …，按θ-边权大小将顶点依次纳入匿名区域，直到找到k-1个顶点为止。如果一次广度优先搜索找到的vi是一个路口(通常其敏感性值接近于0)，则不计数，可作为另外一个出发点作广度优先搜索寻找顶点，直到找到k-1个顶点为止。
如果将与vi相邻接的所有节点都遍历完也不足k个顶点，则按遍历vi邻接点的顺序依次遍历vi1，vi2，…的邻接点，直到找到k-1个顶点为止。将构成匿名区域的顶点和边从图G中删除。如图 5所示，假设用户给定k＝3，从顶点v1出发，按照θ-边权值的大小，先将顶点v2放入匿名集，再将顶点v4放入匿名集。此时，匿名集中包含了k个顶点，匿名区域即由(v1, v2, v4)构成，将顶点v1, v2, v4及和它们相关联的边从图G中删除。继续从图G中任意顶点出发进行上述操作，直到图中不存在k个以上顶点为止。
|
图 5 加权路网 Figure 5 Weighed road network |
匿名算法如算法1所示，加权路网图采用邻接表存储结构，与每个顶点相关联的边按照θ-边权值由大到小排列。
算法1 AnonyGraph(G(V, E), k)。
输入：路网图G(V, E)，隐私保护度k；
输出：匿名区域A1, A2, …, An。
1)选取图G中一个顶点vi加入匿名集；
2)While(图G中剩余顶点个数＞k-1) do
3) for(j=1; j＜=k-1; j++)
4) 广度优先遍历顶点vj1;
5) if (vj1是交叉路口)
6) 广度优先遍历vj1的下一个邻接点;
7) then将访问的顶点加入当前匿名集中;
8) 将访问顶点与和其相关联的边删除;
9) end for
10) 广度优先遍历与vi相邻接的点vi1，vi2, …;
11) end while
12) return匿名区域
之所以采用广度优先遍历是因为深度优先遍历生成的匿名区域面积较大，影响了数据可用性，本文在实验中进行了验证。
2.3 位置实时匿名当用户在一般道路行进的时候，不会有隐私暴露的风险，此时，其位置信息可不作处理，直接提供给位置收集服务器即可。而在访问某个POI或者较为敏感的POI时才有可能泄露隐私。算法的用户位置评估模块在接收到一个位置信息后，将评估该位置是否需要进行匿名处理。对收到的位置数据进行地址反向编译处理，得到其语义地址：
1) 若该地址为路网上某个POI，将其送进位置实时匿名模块进行匿名处理；
2) 若该位置是一般道路，则需根据其与位置匿名区域的距离作相应处理。
用户的位置需经过匿名处理之后才能发送给数据采集服务器。由于地图匿名可以离线完成，因此在移动对象行进过程中完成实时匿名是可行的。具体匿名算法如算法2所示。
算法2 k-θ-D Anonymity(A1, A2, …, An; Li)。
输入：匿名区域A1, A2, …, An，待匿名位置Li；
输出：匿名后的位置Li′。
1) for (i=1; i＜=G中顶点个数; i++)
2) 将Li进行反向地址解析;
3) if(Li是POI)
4) 根据Li的经纬度判断其属于匿名区域Ai;
5) 用Ai替换Li发送给数据收集方;
6) else
7) 直接将Li发送给数据收集方;
8) end for
3 隐私保护度分析与数据可用性评估本节对PTDC算法的隐私保护度和数据可用性进行分析。其隐私保护度可由定理1说明。
定理1 移动对象在运行过程中产生实时轨迹T={(x1, y1, t1), (x2, y2, t2), …, (xn, yn, tn)}，PTDC算法将用户的敏感位置用相应的匿名区域取代。该匿名区域中包含至少k个POI，用户在某个敏感位置被识别的概率为1/k。
证明 假设攻击者可以获取路网背景知识以及隐私处理之后收集到的轨迹信息。给定可发布的轨迹数据库D*，移动对象的任意敏感位置均被泛化为一个区域Ai，其中至少包含k个路网上的POI，攻击者识别用户访问位置的概率与匿名区域中包含的POI数量有关，因此，每个敏感位置被识别的概率至多为1/k。
收集到的轨迹数据可用于密集区域发现等应用。将单个位置泛化为一个匿名区域，不可避免地会丢失信息。本文采用原始位置的识别率定义信息丢失率IL，也就是从一个匿名区域中识别出某个移动对象位置的概率，如下述公式所示：
| $IL=\frac{\sum\limits_{i=1}^{n}{\sum\limits_{j=1}^{m}{(1-1/area({{O}_{i}},{{t}_{j}}))}}}{n\times m}$ |
其中:n表示移动对象的个数，m表示每个移动对象的采样位置数，即轨迹中所包含的采样点的数目。如果移动对象Oi在tj时刻的采样位置泛化为匿名区域，该采样位置的识别度从1下降到1/area(Oi, tj)，其中，area(Oi, tj)表示匿名区域的面积。信息丢失是衡量隐私保护算法的重要指标之一。信息丢失越多，隐私保护算法处理之后的数据可用性就越低。
4 实验分析实验采用北京市路网数据[11]，该数据集有北京市约17万个路网顶点及43万余条边。轨迹数据采用真实数据集Geolife。该数据集采集了155个志愿者在北京市的8 000多条轨迹，该数据集中大约包含230万条采样位置信息，采样位置主要分布在北京市五环区域内。实验机器处理器为Intel i5处理器，4 GB内存，Windows 7操作系统。
本文对算法的信息丢失率、范围查询相对误差及算法运行时间进行了测试。本文的方法与在自由空间中的隐私保护方法YCWA[8]进行了对比实验。YCWA算法是在自由空间中基于语义位置保护的轨迹隐私保护算法，与本文提出的PDTC算法具有可比性。
4.1 数据可用性衡量本节主要展示YCWA算法(具体包括DiverseClus和GridPartiton两个算法，本文只选取性能较好的DieverseClus进行比对实验)和PDTC算法(基于深度优先遍历的算法简写为DFS(Depth-First Search)，基于广度优先遍历的算法简写为BFS(Bread-First Search))在数据可用性上的对比实验，隐私参数k取值为4, 6, 8, 10, 12。实验结果如图 6所示。
|
图 6 数据可用性衡量 Figure 6 Data utility measurement |
信息丢失主要是由空间泛化造成的，即，将一个采样位置泛化为匿名区域，匿名区域面积的大小也是衡量算法的性能指标之一。图 6(a)展示了两个算法匿名区域的平均面积大小。可以看出，由于BFS和DFS算法是在路网上进行POI匿名，其匿名区域平均面积大于YCWA算法。尽管如此，BFS算法的信息丢失率并非很高，图 6(b)展示了信息丢失率与隐私参数之间的关系，从实验结果可看出，算法的信息丢失率随着隐私参数的增加而增加。在路网环境中的隐私保护算法BFS的信息丢失率虽然比自由空间中的算法YCWA略高，但是其信息丢失率仍然在20%以下，尤其当隐私参数为4时，其信息丢失率仅在11%左右。这是由于BFS算法的信息丢失完全是由空间泛化造成的，而YCWA算法中有些不能被泛化的采样位置需要被抑制，这也造成了信息丢失。而DFS算法在两个参数上表现较差，因此PTDC算法以广度优先遍历算法为基础。
4.2 空间范围查询误差该实验评估了在轨迹数据集D*与原始数据集D上执行空间范围查询的误差率，也是隐私保护算法常用的衡量标准之一。实验对两种空间范围查询[12]——PSI(Possibly-Sometimes-Inside)和DAI(Definitely-Always-Inside)的查询误差率进行了测试，相对误差的计算公式为：
|
图 7 空间范围查询误差率 Figure 7 Query error rate of range count query |
图 7展示了空间范围查询误差率的对比结果。从实验结果可以看出虽然在两种查询上YCWA算法比PTDC算法的查询误差率低，但是PTDC算法的误差率一直控制在20%以内。两个算法在DAI查询上的误差率均高于在PSI查询上的误差，这是由于DAI查询的选择性更强。
4.1节和4.2节的实验是针对自由空间中轨迹隐私保护算法和路网环境中轨迹隐私保护算法进行的比对实验。显然，路网环境中的轨迹隐私保护算法的隐私保护度更高，因此，虽然PTDC算法的表现略差于YCWA算法，但PDTC算法更符合实际需求，隐私保护度也更高。
4.3 算法运行时间图 8展示了算法运行时间的对比。从图中可以看出，YCWA算法的时间复杂度远远高于PTDC算法。由于YCWA算法是基于聚类的，随着簇中对象个数的增加，YCWA算法的时间逐渐减少。PTDC是基于图遍历的算法，随着匿名区域中POI数量的增加，回退的可能性更大，算法的运行时间更长。从PTDC算法的运行时间来看，其完全可以满足在线实时收集位置数据的需求。
|
图 8 两种算法运行时间对比 Figure 8 Run time comparison of two algorithms |
本文提出了一种路网环境中感知隐私的轨迹数据采集技术。首先计算路网上POI的敏感性，然后在路网上对POI进行k-θ-D匿名生产匿名区域，最后，区分用户实时位置的敏感性，将敏感位置用匿名区域取代。通过实验验证了本文提出算法信息丢失率较低，且针对范围查询的误差率较低。在今后的工作中，需在下述两个方面对算法进行改进：1) 结合文献[13]中提到的轨迹数据处理的滑动窗口技术，探索k-θ-D匿名算法的更优化算法，提高算法的运行效率；2) 改进POI敏感度的计算方法，使其能够更真实地反映现实世界中POI的敏感性。
| [1] | ZHENG Y. Trajectory data mining:an overview[J]. ACM Transactions on Intelligent Systems and Technology, 2015, 6(3):Article No. 29. |
| [2] | 霍峥, 孟小峰. 轨迹隐私保护技术研究[J]. 计算机学报, 2011, 34(10): 1820-1830. (HUO Z, MENG X F. A survey of trajectory privacy-preserving techniques[J]. Chinese Journal of Computers, 2011, 34(10): 1820-1830.) |
| [3] | DAI J, HUA L. A method for the trajectory privacy protection based on the segmented fake trajectory under road networks[C]//Proceedings of the 20152nd International Conference on Information Science and Control Engineering. Washington, DC:IEEE Computer Society, 2015:13-17. |
| [4] | CHEN R, LI H, QIN A K, et al. Private spatial data aggregation in the local setting[C]//Proceedings of the 2016 IEEE 32nd International Conference on Data Engineering. Washington, DC:IEEE Computer Society, 2016:289-300. |
| [5] | 赵婧, 张渊, 李兴华, 等. 基于轨迹频率抑制的轨迹隐私保护方法[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.) |
| [6] | CAI Z F, YANG H X, SHUANG W, et al. A clustering-based privacy-preserving method for uncertain trajectory data[C]//Proceedings of the 2014 IEEE 13th International Conference on Trust, Security and Privacy in Computing and Communications. Washington, DC:IEEE Computer Society, 2014:1-8. |
| [7] | HAN P I, TSAI H P. SST:privacy preserving for semantic trajectories[C]//Proceedings of the 201516th IEEE International Conference on Mobile Data Management. Washington, DC:IEEE Computer Society, 2015:80-85. |
| [8] | HUO Z, MENG X, HU H, et al. You can walk alone:trajectory privacy-preserving through significant stays protection[C]//International Conference on Database Systems for Advanced Applications, LNCS 7238. Berlin:Springer, 2012:351-366. |
| [9] | HUO Z, MENG X, ZHANG R. Feel free to check in:privacy alert against hidden location inference attacks in GeoSNs[C]//International Conference on Database Systems for Advanced Applications, LNCS 7825. Berlin:Springer, 2013:377-391. |
| [10] | 霍峥, 孟小峰, 黄毅. PrivateCheckIn:一种移动社交网络中的轨迹隐私保护方法[J]. 计算机学报, 2013, 36(4): 716-725. (HUO Z, MENG X F, HUANG Y. PrivateCheckIn:trajectory privacy-preserving for check-in services in MSNS[J]. Chinese Journal of Computers, 2013, 36(4): 716-725.) |
| [11] | 数据堂. 数据产品[DB/OL]. [2017-01-06]. http://www.datatang.com/product/product.html. |
| [12] | TRAJCEVSKI G, WOLFSON O, HINRICHS K, et al. Managing uncertainty in moving objects databases[J]. ACM Transactions on Database Systems, 2004, 29(3): 463-507. DOI:10.1145/1016028 |
| [13] | AI-HUSSAENI K, FUNG B C M, CHEUNG W K. Privacy-preserving trajectory stream publishing[J]. Data and Knowledge Engineering, 2014, 94(Part A): 89-109. |
| [14] | GUO M, JIN X, PISSINOU N, et al. In-network trajectory privacy preservation[J]. ACM Computing Surveys, 2015, 48(2):Article No. 23. |