0 引言

定位技术、无线通信技术以及移动智能设备(如智能手机、平板电脑)的普及产生了海量位置数据, 这为基于位置的服务(LBS)奠定了基础. LBS是与位置信息相关的服务请求, 它把用户位置信息和查询请求一同发送给位置服务提供商并得到服务结果.典型的LBS服务包括车辆导航、路径规划、兴趣点搜索等.连续查询持续地向LBS服务器发送位置信息, 并获取服务结果(如在车辆行驶过程中连续寻找周边最近的加油站、饭店等).

然而, 用户在享受LBS带来便利的同时, 个人隐私泄露问题也不可回避.攻击者根据用户发起的连续查询, 收集这些位置信息, 再重构出用户轨迹, 从而推测出用户的工作地、居住地, 甚至用户的行为模式等敏感信息.更糟糕的是, LBS服务器可能会因经济利益而把人们的私人信息出售给恶意第三方, 如房地产中介、广告提供商等, 从而对人们的日常生活造成困扰.许多用户会因注重自己的隐私信息而对LBS服务器持保留的态度.因此, 在为用户提供高质量的实时查询服务的同时如何保障用户的个人隐私不泄露, 成为了一个关键问题.

许多学者提出了多个方案来保护轨迹隐私, 例如用虚假轨迹技术^[1-2].考虑图 1这样的场景, 用户$U$在公路上行驶时发现汽油快耗尽了, $U$想知道最近的加油站在哪里, 为此$U$在$t_{1}$、$t_{2}$和$t_{3}$时刻分别进行了查询.为了防止泄露自己的位置信息, $U$使用虚假轨迹方法^[1]在当前位置附近生成了一些虚假位置以混淆自己的真实位置.令$D_j^{t_i}$表示第$j$条虚假轨迹在第$t_{i}$时刻的一个假位置(设定用户隐私偏好$k=3$, $j\in[1, 2]$, $i\in[1, 3]$), 所生成的虚假位置连同用户真实位置以及用户查询请求一起发送给LBS服务器, 并最终得到查询结果.然而, 这个方法暴露出了几点不足, 需要改善.第一, 在$t_{2}$时刻, 用户$U$所在位置和$(k-1)$个假位置所形成的匿名区域太小(例如, 虚假位置和用户真实位置均处于同一个居民小区内), 攻击者很容易推测出用户$U$的真实位置.第二, 在$t_{3}$时刻所形成的匿名区域太大, 增加了系统的计算开销, 降低了用户的服务质量.第三, 该方法忽略了实际环境因素, 如在$t_{3}$时刻$D_1^{t_3}$位置位于湖泊当中, 这种情况显然不可能发生, 这就很容易被拥有背景知识的攻击者排除掉, 从而增大推测出用户位置的概率.第四, 此方法没有充分考虑实时情景下相邻时刻位置之间的关系, 例如, 在[$t_{2}$, $t_{3}$]时间段内, 用户$U$行驶的路程设定为700 m($U^{t_2}$与$U^{t_3}$之间的直线距离为700 m), 对应时刻下轨迹$T_{1}$行驶路程为650 m, 而轨迹$T_{2}$行驶路程为1 300 m, 具有背景知识的攻击者根据路网的限速等条件就可以推测出在这段时间内行驶的合理路程范围应该是600 m至800 m, 因此攻击者有理由断定$T_{2}$是假轨迹.

鉴于此, 本文提出了一个新方案, 用以提升用户轨迹隐私的保护程度.首先, 考虑到不同地点在历史数据库中的出现频度不同, 在生成假位置/假轨迹时选择与真实位置相似性较高的若干地点作为候选位置; 其次, 候选位置在一个用户可控的范围之内进行挑选, 而不一定靠近某个真实位置, 这样即可以避免候选位置与用户位置聚集在小范围区域内, 又能防止候选位置与用户位置距离过远, 使得服务质量和隐私均得到保障; 最后, 考虑了实际环境下相邻时刻位置间的关系, 使得生成的假轨迹更加合理以便混淆用户轨迹, 提高轨迹隐私保护程度.

本文的贡献总结如下.

(1) 设计了一个新的轨迹隐私度量"标准", 基于该度量标准可计算新方案所取得的隐私保护程度.

(2) 提出了DTG算法, 达到了轨迹$k$-匿名的效果.该算法结合了传统的空间匿名和虚假轨迹两种方法, 并引入信息熵模型, 使得在每一时刻生成$(k-1)$个逼真的假位置.

(3) 提出了EnDTG算法, 进一步提高了轨迹$k$-匿名隐私保护程度.该算法在DTG算法基础上, 引入了位置可达性约束.除了第一个时刻外, 在其他每个时刻下的$(k-1)$个假位置具有较高的混淆程度, 同时还满足了位置可达性要求, 这样形成的假轨迹更加合理.

(4) 采取真实数据集对所提方案与现有主流方案进行了对比实验.评价结果表明, 本文提出的新方案在隐私保护方面要优于其他的方案.

本文余下部分组织如下:第1节讨论轨迹隐私保护的一些相关工作; 第2节形式化地定义问题; 第3节介绍本文所提出的方案; 第4节展示实验结果与分析; 第5节总结全文.

1 相关工作

近几年来, 轨迹隐私保护的研究已经取得了显著的进步, 文献[3]总结了最新的隐私保护技术并将它们划分为空间匿名^[4-6]、混合区域^[7-8]和虚假轨迹^[1-2]等技术.近来, 差分隐私技术和加密技术也被用于保护轨迹隐私.

在基于空间匿名技术中, 借助可信的位置匿名器, 通过位置匿名算法模糊用户精确位置, 将精确位置变成匿名区域来减少用户位置信息的分辨度.文献[5]提出了Interval Cloaking匿名算法, 该算法采取四叉树结构存储用户位置信息, 四叉树的最底层叶子节点的划分以最小匿名面积作为标准, 每次更新均需要采用递归算法, 从上到下对区域进行四叉树划分, 以求得匿名区域.文献[4]介绍了一个系统框架, 该系统框架可以根据隐私要求让用户匿名获取快照查询和连续查询服务.文献[9]用在一个匿名区域内依据最大行驶速度确定用户位置的方法来解决连锁攻击问题.

混合区域技术综合采用混合区和假名两种技术.当用户进出混合区时变化其假名来保护用户的轨迹信息.在混合区中, 所有用户都不允许将自身位置信息发送给LBS服务器, 这样攻击者无法将用户进入与离开混合区的事件相联系, 从而保护了用户的隐私.文献[8]提出了一个基于路网的混合区框架以保护行驶在路网上移动用户的位置隐私, 该框架考虑了路网拓扑结构、用户群体统计、用户移动模式特征等因素.在实际路网上, 为了减少因混合区过多而造成用户服务中断的影响, 文献[7]优化了对混合区的设置, 限制了混合区的数量.

假轨迹技术方案并不依赖于位置匿名器, 而是在客户端上为每条轨迹产生多条相似的虚假轨迹, 从而保护用户轨迹.文献[1]采用旋转方案, 通过旋转虚假轨迹和用户轨迹之间的角度产生虚假轨迹集, 从而实现轨迹$k$-匿名效果.文献[2]考虑拥有背景知识的攻击者与各个位置点之间距离这个问题, 设计了两个虚假位置选择算法, 生成逼真的假位置来达到$k$-匿名效果.然而, 这些算法只考虑了在单一时刻情景下对用户位置隐私的保护, 并没有扩展到在实时场景中对用户轨迹的保护.

随着计算速度的提高与安全算法的更新, 密码学进入了轨迹隐私保护领域.文献[10]提出了一种支持隐私位置相关查询的隐私信息检索框架, 该框架不必使用第三方可信匿名服务器.文献[11]使用同态加密技术取得了很好的隐私效果, 唯一不足的是它的计算开销远大于传统隐私保护技术.文献[12]在车载网络中运用加密机制来提高轨迹隐私保护程度.文献[13]进一步分析了文献[11]的计算开销, 认为仅仅加密部分数据就能提升性能.

2 问题定义

令轨迹$T$表示一个长度为$n$的移动对象的位置序列, $T=\{ID, D^{t_1}, D^{t_2}, \cdots, D^{t_n}, \}$, 其中ID是对象标识, $D^{t_i}$表示该对象在$t_{i}$时刻的位置.如前所述, 拟生成的虚假轨迹既要与真实轨迹有一定的差异性, 又必须具备充分的合理性, 否则易于被攻击者发现.换句话说, 拟生成的虚拟轨迹中相邻时刻的位置间距离应该不会显著偏离真实位置之间的真实距离.因此, 本文提出了位置可达性概念.

定义1(位置可达性)  令$U$和$T_{x}$分别表示移动对象的真实轨迹和虚假轨迹, $U^{t_i}$和$D_x^{t_i}$分别为这两个轨迹上第$i$个位置点, $\beta$表示距离阈值, dis($\cdot$, $\cdot$)表示两点之间的欧氏距离.则给定位置点$D_x^{t_i}$满足位置可达性, 当且仅当

$ \begin{align} \frac{|\rm {dis}(D_x^{t_{i-1}}, D_x^{t_i})-\rm {dis} (U^{t_{i-1}}, U^{t_i})|}{\rm {dis}(U^{t_{i-1}}, U^{t_i})}\leq \beta \end{align} $

(1)

成立.

位置可达性使得拟生成的某个位置不会过分偏离真实位置.当生成一组虚假位置时, 还需要从整体上考虑所生成数据的隐私性.这其中, 信息熵的度量标准被广泛采用^[14-15].本文扩展了这个概念, 提出了$k$-匿名集信息熵.

定义2(k-匿名集信息熵)  在$t_{i}$时刻, 令$p_{j}$表示$k$-匿名集中第$j$个位置的查询概率, $P$表示该匿名集中所有位置的查询概率之和($P=\sum\nolimits_{j=1}^kp_j)$.然后归一化匿名集中所有查询概率, 即$q_{j}=p_{j}/P$.因此, 该时刻的$k$-匿名集信息熵可以通过公式

$ \begin{align} H^{t_i}=-\sum\limits_{j=1}^ k q_j\times \rm {log}_2q_j \end{align} $

(2)

定义.

由于一条轨迹包含多个位置点, 为了从整体上考虑拟生成轨迹的隐私性, 本文基于信息熵提出了轨迹熵的概念.

定义3(轨迹熵)  考虑一个包含$n$个点的轨迹, 其轨迹熵($HT$)定义为

$ \begin{align} HT=\frac{1}{n}\sum\limits_{j=1}^ n(H^{t_i}-\rm {log}_2k)^2, \end{align} $

(3)

其中log$_{2}k$为$k$-匿名集中最大信息熵.

易知, 当HT越小, 则用户轨迹的隐私程度越高; 反之, 用户轨迹不确定性程度越低.

3 提出的新方案

本节首先介绍系统架构, 然后再介绍DTG算法和EnDTG算法, 最后分析安全性.

3.1 系统架构

由于实时位置/轨迹隐私保护方案^[14]需要消耗大量计算资源, 全部工作在移动客户端上完成并不可行.因此, 本文采用集中式架构作为方案的系统架构.该架构包括客户端、可信位置匿名服务器和LBS服务器, 如图 2所示.客户端是指用户携带的移动设备, 如智能手机、电脑或者相关车载设备.可信位置匿名服务器包含历史数据库、匿名化模块和结果处理模块:历史数据库保存历史用户轨迹和每个单元格的查询概率; 匿名化模块接收客户端发送过来的位置和查询请求(请求包括隐私等级$k$、查询内容等信息), 然后去除身份标识(如ID), 并根据用户隐私需求将包含有精确位置/轨迹的查询混淆于匿名集中一起发送给LBS服务器; 结果处理模块接收LBS服务器返回的候选集, 筛选正确结果传回给客户端. LBS服务器能够为用户提供不同类型的基于位置服务, 例如位置搜索等.

3.2 虚假轨迹生成算法DTG

算法1描述了虚假轨迹生成的详细步骤.为了避免所生成的虚假位置过于集中, 以减少用户位置被推测出来的概率, 本文首先基于用户真实位置$U^{t_i}$和最小匿名区域面积$A_{\min}$来确定匿名区域CR的大小以及位置(行1-5);然后计算在匿名区域中所有单元格的查询概率; 最后调用GenerateResult算法返回$t_{i}$时刻的虚假位置点集合(行6-8).针对不同时刻分别调用算法1即可生成关于整个轨迹的虚假轨迹集合.

算法1  虚假轨迹生成算法
输入:  最小匿名区域面积$A_{\min}$, 用户位置$U^{t_i }$, 用户隐私偏好$k$, 单元格边长$m$
输出:  虚假位置集DummyList
1:生成一个随机整数$d$, $d\in [1, k]$;
2: $N\leftarrow d+\left\lceil {\frac{A_{\min } }{m^2}} \right\rceil $;
3: $a\leftarrow \sqrt N $, $b\leftarrow \left\lceil {N/a} \right\rceil $;
4:生成两个随机整数$\alpha $和$\beta $, $\alpha \in [0, a]$, $\beta \in [0, b]$;
5:构造匿名区域$CR$, 其长为$a\times m$, 宽度为$b\times m$; 左下角在长轴距离$U^{t_i}$为$\alpha \times m$, 在宽轴距离$U^{t_i}$为$\beta \times m$;
6:构造概率集$Q=\{q_{1}, q_{2}, \cdots, q_{a\times b}\}$, 其中$q_{i}$是$CR$中第$i$个单元格所对应的查询概率;
7: CellListCR中$4k$个查询概率最接近$U^{t_i}$所处单元格的查询概率的单元格;
8: return GenerateResult (CellList, $U^{t_i}$, $k$, $s)$.

GenerateResult算法见算法2.首先从CellList中选出$s$组TempList$_{j}$, 每组各包含$(2k-1)$个随机挑选的单元格, 以及用户位置, 并由公式(2)计算每组TempList的匿名集信息熵$H_{j}$; 再将具有最大匿名集信息熵的TempList放入CandidateList中(行1-5);最后, 从CandidateList选出$s$组DistanceList$_{j}$, 每组各包括$(k-1)$个单元格和用户位置, 最终返回DS$_{j}$最大的一组DistanceList$_{j}$作为位置集返回(原因是这一组单元格较为分散(行6-11)).

算法2  生成结果集GenerateResult
输入:  单元格列表CellList, 当前时刻用户位置$U^{t_i }$, 用户隐私偏好$k$, 组数$s$
输出:   $t_{i}$时刻的虚假位置集DummyList
1: for $j=1$ to $s$ do
2:   TempList$_{j}\longleftarrow U^{t_i}$; 以及从CellList中随机选出的$(2k-1)$个单元格$D^{t_i}$;
3:   通过公式(2)计算TempList$_{j}$的匿名集信息熵$H_{j}$;
4: end for
5: CandidateList$\longleftarrow$argmax$_ {\rm{Templist}_j}H_j$;
6: for $j=1$ to $ s$ do
7:   DistanceList$_{j}\longleftarrow U^{t_i}$以及从CandidateList中随机选出的$(k-1)$个单元格;
8:   $DS_j \longleftarrow \sum\nolimits_{c_i , c_l \in \rm {Dis\!\tan \!ceList}_j , i<l} {\rm {dis}(c_i , c_l )} $;
9: end for
10: DummyList$\longleftarrow\rm {argmax}_ {\rm{DistanceList}j} DS_{j}$;
11: return DummyList;

图 3描述了一个DTG算法的运行样例.地图区域被栅格化为多个单元格, 白色单元格表示查询概率为0, 灰色单元格表示查询概率大于0, 且不同图案表示查询概率的高低.为简化表示, 只画出用户位置$U^{t_i}$附近一些单元格的查询概率.红色虚线构成匿名区域CR.令$k=3$, 在图 3(a)中, CellList$=\{A\sim L\}$; 经过信息熵计算后, 得CandidateList=$\{A$, $B$, $C$, $E$, $H, U^{t_i}\}$; 最后, 在综合考虑各点相互之间的距离之后, 得到该时刻的DummyList$=\{U^{t_i}, B, E\}$. 图 3(b)描述了在3个不同时刻所生成的虚假位置集合.

3.3 增强型虚假轨迹生成算法EnDTG

算法1在每个时间点单独生成虚假位置集合, 这样做的效率较高.但是, 由于该算法并未考虑到相邻位置之间的空间相关性, 可能会被拥有背景知识的攻击者攻击.例如, 在图 1中, $D_2^{t_1}$与$D_2^{t_2}$之间的欧氏距离是真实距离的两倍.因此, 考虑引入位置可达性模型使得新生成的轨迹更加合理.

EnDTG算法(算法3)新增了对$CR$中所有单元格的位置可达性检验(行1-8), 只有满足可达性要求的单元格才能被放入到LRList中; 然后从LRList选出4$k$个查询概率最接近$U^{t_i }$所处单元格的查询概率的单元格并将其放入CellList(行9)$; $最后调用GenerateResult算法(算法2), 生成最终满足条件的DummyList(行10).例如, 在图 3中的$t_{2}$时刻$D_1^{t_2 } $位置点不满足位置可达性, 因此对$D_1^{t_2 } $进行调整, 调整后效果如图 4所示.因此, 不同时刻使用EnDTG算法生成的位置点构成的轨迹集$T_{1}$和$T_{2}$更加合理有效.

算法3  增强型虚假轨迹生成算法EnDTG
输入: 在$t_{i}$和$t_{i-1}$时刻的用户位置$U^{t_i }$和$U^{t_{i-1} }$, $t_{i}$时刻的匿名区域CR$_{i}$, 用户隐私偏好$k$, 组数$s$, $t_{i-1}$时刻的虚假位置$D_j^{t_{i-1}}(j\in [1, k-1]), \beta$
输出: $t_{i}$时刻的虚假位置集DummyList
1: Dis$_{U}\longleftarrow$dis($U^{t_{i-1}}, U^{t_i}$);
2: foreach $c\in $CR do
3:  for $ j=1$ to $(k-1)$ do
4:     if $\frac{|\rm {dis}(D_{j}^{t-1}, c)-\rm {Dis}_U|}{\rm {Dis}_U}\leq \beta$ then
5:       LRList$\longleftarrow$LRList$\cup\{c\}$;
6:     end if
7:   end for
8: end for
9: CellList$\longleftarrow$LRList中4$k$个查询概率最接近$U^{t_i}$所处单元格的查询概率的单元格;
10: return GenerateResult(CellList, $U^{t_i}$, $k$, $s)$;

3.4 时间复杂度分析

时间复杂度是衡量算法性能的一个重要指标.对于DTG算法而言, 比较耗时有3部分:第一部分需要寻找出4$k$个查询概率, 该部分操作的时间复杂度为O(ablog(ab)), 其中ab为CR中总的单元格个数; 第二部分从CellList选取$s$组的TempList$_{j}$进行信息熵计算, 该部分操作的时间复杂度为$O(s)$; 第三部分从CandidateList选取$s$组的DistanceList$_{j}$进行距离之和计算, 该部分操作的时间复杂度为$O(sk^2$), 其中$k$表示用户隐私偏好.因此, DTG算法的总时间复杂度为O((ab)log(ab)+$s$(1+$k^2$)).

相比于DTG算法, EnDTG算法增加了位置可达性检测部分.首先需要对CR中所有单元格的位置是否满足位置可达性要求进行检测, 因此这部分操作的时间复杂度为O(abk); 然后对LRList进行选出最相似的4$k$个单元格操作, 设LRList里的总单元个数为$w$, 那么该操作时间复杂度为O($w$log$w)$; 剩余操作和DTG算法的第二部分、第三部分操作是类似的.因此, 可知EnDTG算法的时间复杂度为O(abk+$w$log$w+s$(1+$k^2$)).

3.5 攻击模型与安全分析

考虑两种类型的攻击者:外部攻击者和内部攻击者.外部攻击者能够窃听可信位置匿名器与LBS服务器之间不安全的无线信道, 从而尝试推断出用户的敏感信息.内部攻击者包含两种类型:一种是能够通过攻击可靠的LBS服务器来获取敏感信息; 另一种是把本身不可控的LBS服务器作为攻击者.在本文中, 由于LBS服务器收集了用户的所有信息, 包括用户的当前位置以及历史的查询请求等, 基于这些内容, 它可能会发起推理攻击推断出用户更多的敏感信息.因此, 本文把LBS服务器当做外部攻击者.

安全性分析将关注本文所提算法是如何抵挡由攻击者发起的一些攻击, 如窃听攻击、联合攻击等.对于窃听攻击而言, 一些常用的加密技术如SSL^[16]可以运用到本方案通信信道上, 可有效地抵御窃听攻击的发生.此外, 本文方案还可以有效抵御联合攻击以及推断攻击.

(1) 抵御联合攻击.联合攻击是指攻击者会联合其他一些用户或者LBS服务器, 从用户提交的$k $个位置中以较高的概率推测出用户的位置.面对攻击者发起的联合攻击, 本文方案采用虚假技术, 用户不需要联合其他用户组成$k$个位置; 并且, 轨迹$k$-匿名确保了攻击者猜测出用户轨迹的概率不超过$1/k$.因此, 能够有效抵御联合攻击.

(2) 抵御推理攻击.推理攻击是指LBS服务器可以通过监视用户发送过的所有服务请求, 包括当前请求和历史请求, 从而提高推测出用户位置信息的概率.在本文方案中, DTG算法与EnDTG算法在同一个时刻里不但选取了具有与用户位置的查询概率最相似的单元格作为候选集, 而且在该候选集中考虑了两两位置间的最大距离之和; 此外, EnDTG算法还引入了位置可达性条件, 使得相邻时刻位置间的距离更近合理有效, 这样攻击者无法提高推测出用户位置的概率.因此, 本文的方案能够有效抵御推理攻击.

4 实验评估 4.1 实验设置

在实验中, 本文选取上海市某12 km$\times $16 km区域进行实验, 并将该区域栅格化操作.划分后的单元格边长$m=100$ m, 连续查询的时间总个数$n=5$, 最小匿名面积$A_{\min}=3$ km$^2$, 组数$s=1 000$, 用户隐私偏好$k$设置为2~30, 其每次增长幅度为2.在数据集方面, 使用真实上海出租车数据集来模拟用户的移动轨迹, 该数据集包括从2015年4月1日至2015年4月30日中每日约10 000条轨迹, 为简化工作, 本文相信在一个区域内有越多的位置点, 则该区域的查询概率就会越高.因此, 本文把一个区域内出租车密度作为该区域的查询概率.

在比较方案中, 将本文提出的DTG算法和EnDTG算法与现有的3种主流算法进行了比较. 3种主流算法为随机Random算法^[17]、根据历史轨迹取得轨迹$k$-匿名保护的足迹(Footprint)算法^[18]以及CaDSA算法^[19].

4.2 结果分析

(1) k与隐私保护程度.分别对各个方案的单个时刻下的匿名集信息熵和连续查询下的轨迹熵进行了分析. 图 5(a)验证了不同$k$值对单个时刻(本文选取$t_{1}$时刻作为一个例子)信息熵$H^{t_i}$的影响; 图 5(b)展示了不同$k$值对轨迹熵HT的影响.在图 5(a)中, Random算法在所有方案中表现是最差的, 因为它没有考虑位置的查询概率, 使得随机生成的一些假位置很容易落在查询概率很低甚至为0的单元格上, 因而它的信息熵是最小的. Footprint算法的信息熵都要比Random算法的好一些, 原因在于该方案使用了数据库中的用户轨迹充当假轨迹实现轨迹$k$-匿名, 这样避免了选取查询概率很低的单元格作为假位置.本文的DTG算法和EnDTG算法都选取其查询概率与用户查询概率最接近的位置作为虚假位置, 故它们的信息熵较其他方案是最高的.另外, DTG算法的信息熵要略高于EnDTG算法, 这是因为EnDTG牺牲了一些信息熵来满足位置可达性.从图 5(b)中可以看出, DTG算法和EnDTG算法的轨迹熵HT均低于其他方案的轨迹熵.

(2) k与距离之和. 评估了在特定时刻$t_{1}$和整个连续查询过程中$k$与距离之和的关系.如果距离之和越小, 则匿名集中的所有位置聚集在一个小区域内, 越容易暴露用户的位置; 如果距离之和越大, 则匿名集中的所有位置都越分散, 越不容易暴露用户的位置. 图 6(a)分析了特定时刻$t_{1}$下$k$与距离之和的关系; 图 6(b)分析了整个连续查询过程中$k$与平均距离之和的关系.从这两幅图中可以很明显看出, 随着$k$不断增大, $t_1$时刻距离之和与平均距离之和也在不断增大; Footprint算法的$t_1$时刻距离之和与平均距离之和均是最低的, 这是因为它选取距离用户轨迹最近的轨迹作为虚假轨迹; 另外DTG算法的$t_1$时刻距离之和与平均距离之和均要高于EnDTG算法, 原因在于EnDTG算法牺牲了一些距离来考虑位置可达性.

(3) k与位置可达性LR的数量.评价$k$与满足位置可达性LR数量的关系. 图 7(a)验证了在不同的距离阈值$\beta$下, 随着$k$的不断增加, EnDTG算法满足LR数量的变化关系为:当$\beta$不断增加时, LR数量也在不断增加; 当$\beta=0.4$时, LR数量达到了最优方案的效果.因此, 本文在实验中将$\beta$设置为0.4.在图 7(b)中, Random算法的LR数量是最低的, 因为它任何因素都没有考虑, 用户随意生成虚假位置, 因此它的$LR$数量是最低的.可以看出DTG算法和EnDTG算法的$LR$数量要多于其他方案, 这是因为这两种算法认真选取了虚假位置; 另外, EnDTG算法的$LR$数量要多于DTG算法, 这是因为EnDTG算法考虑了$LR$约束条件.

5 结论

本文针对实时轨迹隐私保护的问题, 提出了两个算法:虚假轨迹生成(DTG)算法和增强型虚假轨迹生成(EnDTG)算法. DTG算法使用传统的空间匿名和虚假技术, 引入信息熵模型, 构建$(k-1$)条假轨迹, 实现了轨迹$k$-匿名隐私保护要求. EnDTG算法在DTG算法的基础上考虑了相邻时刻位置间的时空约束关系, 引入位置可达性约束概念, 从而有效地提高了轨迹隐私保护程度.实验结果表明, 相比于现有的方案, DTG算法和EnDTG算法均能取得更高的隐私保护程度.未来工作主要包括引入路网环境, 以及考虑用户的行驶速度因素, 从而进一步提升用户轨迹保护程度.