随着互联网的快速发展，许多电子设备融入现实生活，例如智能手机、智能手环等.但是在享受大数据便利的同时，也面临着隐私安全隐患.一些基于位置服务(location based services, LBS)应用软件在用户未知情的情况下，采集用户的地理位置信息并发布，不仅造成用户的位置隐私泄露，而且有可能造成更多的敏感信息泄露，如用户的生活习惯、宗教信仰等.据微软统计报告，有一半以上的用户担心自己在使用基于LBS的应用程序时泄露自己的隐私.因此在用户使用LBS时，如何实现位置轨迹数据的安全分享与发布，保护用户的个人隐私成为一个重要问题.
为解决位置隐私保护这一问题，国内外许多学者纷纷置身于此问题之中.2002年Sweeney等人提出K-匿名理论[1].文献[1]中定义了伪标识符和K-匿名性，广泛应用于轨迹匿名和隐私保护.2003年Gruteser等人将K-匿名的理论引入到位置隐私保护，提出一种空间位置隐藏方法[2].该方法的思想是通过空间隐藏方法隐藏单个用户与其他K-1个用户的地理位置使之无法区分，但是这种方法必须在特定情形下才能实现，所以用户不能根据自己的需求设置不同K值和需要隐藏的区域.2009年Chow等人提出一种个性化K-匿名模型[3]，该方法是基于用户出现在隐藏区域相等的概率下提出的一种模型，但当用户出现的概率不等时，该模型不能很好地反映用户隐私的保护程度.
许多学者基于K-匿名模型，相继提出了K-匿名模型的变体.2006年Wang等人提出(X,Y)-匿名的概念，其中X，Y表示2个不相交的属性集合[4].该方法主要在处理敏感数据时增加了限制条件，在属性组X中属性相同的情况下，每一组X均需要对应至少K个不同敏感属性组Y中的值.2007年Zhang等人提出了(K,e)-匿名模型，目的处理敏感数值型数据，其思想为在每个等价类中元组个数不能低于K个，每个等价类中的敏感属性的取值范围不能低于给定的阈值e[5].Machanavajjhala等人在2007年提出l-多样化模型[6]，这一方法是通过熵值定义数据的多样性及变化特征，要求在准标识符相同的情况下，敏感数据满足一定的多样化要求，保证了敏感数据的多样性，但是敏感数据如何分布该方法并未考虑.而t-贴近模型的提出解决了这一问题[7-8].t-贴近模型定义了一个阈值t，并要求等价类中敏感属性的分布和整个表的敏感属性分布的距离不能超过阈值t.
K-匿名模型优势在于攻击者能力不超过假设的前提下，能够以较小的代价保证同一等价类中记录的不可区分性，但当攻击者能力超过假设范畴，攻击者就可以进一步区分等价类中不同的记录，从而实现去匿名化，造成背景知识攻击.l-多样化模型虽然在一定程度上处理了K-匿名缺乏多样性的问题，但是该模型仍不能抵御概率推理攻击，若敏感属性分布不均匀时，导致实现该技术困难.t-贴近模型作为l-多样化模型的改进，解决了针对敏感属性的攻击，但是仍无法抵御背景知识的攻击，而且面对不同的敏感属性值时缺乏保护水平的灵活性.
因此，Dwork等人在2006年提出差分隐私技术，很好地解决了背景知识攻击及推理攻击的问题[9-10].该方法的主要思想是在数据库中添加噪声，达到攻击者无法识别其中任意一个数据是否在该数据库中.该技术是一种新的隐私保护技术，具有健强的数学基础，可以提供严谨的数学证明[11].差分隐私技术的提出，受到广大隐私保护领域研究者的关注，并广泛应用于支持隐私保护的数据挖掘和数据发布领域[12].2012年Andrés等人提出基于位置的差分隐私扩展模型，并生成一个在隐私预算范围内不会受攻击的匿名位置[13].但是由于生成的匿名位置与用户的真实位置之间的距离无法预测，所以不能保证LBS的服务质量.2013年Dewri等人利用Hilbert分布的匿名集获得高质量服务[14].但是匿名位置和真实位置没有相似性，攻击者很容易区分开.2018年Gursoy等人提出一种名为DP-Star的轨迹隐私保护框架[15].该框架构建了一个密度感知网络，可以确保添加噪声之后满足差分隐私的需求，保持数据的空间密度，并采用中值长度估计方法保护用户轨迹，生成了既保留了差分隐私性质又高效能地合成轨迹.2019年Deldar等人提出一种称为PDP-SAG的差分隐私机制[16]，用于解决移动对象的非时空敏感属性，为了使添加噪声频率一致，对个性化差分隐私结构上的属性噪声值进行一致处理.
由于轨迹数据具有高维性，不仅包含时间戳信息，也包含位置信息.为了满足大量轨迹数据存储与发布，Chen等人在2012年首次提出将差分隐私应用于发布大量顺序数据的方案，采用一种基于混合粒度前缀树结构(SeqPT)存储轨迹数据[17].在节点计数中加入Laplace噪声，以确定子树是否能继续在相应的节点上继续增长，并利用前缀树的固有一致性约束性质进行约束推理.但是时间戳的增多导致树高也会增高，计算量随着树的高度增加而增加，而SeqPT模型并不适用于高维时空数据集.2018年Khalil等人提出一种加噪前缀树模型[18]，并引入一种称为SafePath的算法，该算法引入可变高度和等级分类树改进了SeqPT，减少了空节点生成的可能性.虽然该算法提高了大型和稀疏数据集的效率，但是在处理真正的高维属性的时空数据时，不仅分类树会增加隐私预算，而且发布的轨迹数据集的可用性较低.2019年Zhao等人提出一种SR-树结构代替R树的最小外界矩形，Cons-SRT算法虽然抵御了非位置敏感信息攻击，但是由于树过高导致查询效率下降[19].
为此，为了处理树高的增加导致查询效率下降的问题，本文提出一种基于差分隐私的噪声前缀树结构应用于轨迹数据的存储与发布.本文首先通过轨迹的时间特性以及速度和方向的特征，划分出不同时间戳的轨迹等价类.其次采用Hilbert曲线对各个轨迹等价类中的位置点进行标号划分，并计算每个等价类的中心点.然后由前缀树的节点存储该中心点，根据移动用户的轨迹特征，从而获取轨迹的时空特性，保证了轨迹数据的存储与发布.最后利用差分隐私技术对节点存储的敏感数据添加噪声.
本文的贡献有3个方面：
1) 不仅考虑轨迹的时间特性,而且通过计算轨迹间的速度距离和方向距离构建轨迹等价类，并提出一种满足差分隐私性质的轨迹数据发布算法.为防止攻击者通过轨迹背景知识和上下文信息获得隐私数据，本文采用差分隐私技术对敏感数据进行加噪.
2) 证明本文提出的隐私保护方案满足差分隐私性质，并进一步降低了轨迹数据的时间复杂度.
3) 使用真实的数据库进行试验，评测本文提出方案的效率和效用.证明文本的方案使得合并轨迹时间更少，并确保轨迹数据的可用性.
1 问题陈述
1.1 轨迹概念
定义1. 轨迹.轨迹是指移动对象经过的一系列二维时空点的集合：
T={id,(l1,t1),(l2,t2),…,(l|T|,t|T|)},
(1)
其中，|T|为轨迹轨迹中位置点个数，即轨迹的长度，t1<t2<…<t|T|，id为轨迹的标识符.位置li由二元组(xi,yi)表示，其中xi，yi分别表示移动对象在时空中所在的经度和维度，1≤i≤|T|.
多条轨迹Ti构成的集合为轨迹集D，表示为D={T1,T2,…,Tn}.
定义2. pt%-同步轨迹[20].2条轨迹
和
是同步轨迹，当且仅当这2条轨迹具有相同的时间序列.其中pt值表示时间重叠率，即：
(2)
其中,
当pt=0时，轨迹Ti和Tj不是同步轨迹；当pt=100时，轨迹Ti和Tj具有相同的起始和结束时间.我们定义time(Ti,Tj)表示2条轨迹的重叠时间戳，即：
(3)
定义3. 轨迹等价类.对于任意一条轨迹Ti∈{T1,T2,…,Tp}所在集合是一个轨迹等价类EC，则该轨迹等价类EC中所有轨迹的起始时间为
结束时间
定义4. 轨迹等价类距离矩阵TDM.轨迹等价类距离矩阵为n阶对称矩阵
(4)
其中，dij表示轨迹Ti和Tj的距离.
定义5. 离散Fréchet距离[21].设2条曲线A={a1,a2,…,am}，B={b1,b2,…,bn}由多个离散位置点点组成，则2条曲线的序列组合可以表示为L={(a1,b1),(a2,b2),…(am,bn)}，定义L为所有序列对中最大距离.则离散Fréchet距离可以表示为
(5)
定义6. 轨迹方向距离[20].2条轨迹Ti和Tj满足pt>0，我们用disto(Ti,Tj)表示这2条轨迹的方向距离，即：
(6)
其中,stij和etij分别表示time(Ti,Tj)的开始时间和结束时间；
表示轨迹Ti在第r段的向量，即
轨迹间的夹角θ范围[0,π].
定义7. 轨迹速度距离[20].2条轨迹Ti和Tj满足pt>0，我们用distv(Ti,Tj)表示这2条轨迹的速度距离，即：
(7)
其中,
表示轨迹Ti在第r段向量的速度，即
定义8. 轨迹距离.2条轨迹∀Ti,Tj∈D，D为轨迹数据集.当2条轨迹Ti和Tj满足pt>0，那么轨迹间距离Dist(Ti,Tj)定义为
Dist(Ti,Tj)=δdF(Ti,Tj)+
α×disto(Ti,Tj)+β×distv(Ti,Tj),
其中，disto(Ti,Tj),distv(Ti,Tj)分别由式(6)和式(7)所得，α和β分别代表方向距离和速度距离的权重值，满足α,β∈[0,1],α+β=1.
1.2 差分隐私
定义9. ε-差分隐私[12].给定数据集D和其相邻数据集D′(2个数据集中最多相差一条记录)，函数f的任意输出S满足：
Pr[f(D)=S]≤Pr[f(D′)=S]×eε,
(8)
则称函数f满足ε-差分隐私，其中隐私预算ε>0.
隐私预算ε表示隐私保护程度，由数据拥有者指定.ε越大，数据可用性越大，提供的隐私保护程度越低;ε越小，数据可用性越小，提供的隐私保护程度越高、相邻数据集D和D′查询结果的概率分布越相似，攻击者更难以判断数据集中的某一元素.
定义10. 全局敏感度[22].设2个相邻数据集D和D′至多相差一条记录，函数f:D→Rd的全局敏感度：
(9)
其中，R表示映射空间，d表示函数f输出的维度.全局敏感度直接影响噪声添加量，在相同的预算ε下，函数f的全局敏感度越大，添加的噪声越多，导致数据可用性降低.
定义11. 拉普拉斯机制[9].设查询函数f:D→Rd满足ε-差分隐私机制，对函数f的输出添加拉普拉斯噪声，即
(10)
其中,算法A提供ε-差分隐私保护.产生拉普拉斯噪声机制的密度函数为
(11)
其中,参数λ由全局敏感度Δf和隐私预算ε决定，即
定义12. 序列组合性[23].给定一个数据集D和n个函数f1,f2,…,fn，每个函数fi(1≤i≤n)满足εi-差分隐私，则函数组合F(f1(D1),f2(D2),…,fn(Dn))满足∑εi-差分隐私.对于
必有：
(12)
定义13. 并行组合性[23].假设Di(1≤i≤n)，是原始数据集D中彼此不相交的子集，对每个子集Di作用一个差分隐私函数fi，其隐私保护参数为εi，函数组合F(f1(D1),f2(D2),…,fn(Dn))提供(max εi)-差分隐私保护.则称函数fi在D上的并行组合满足(max εi)-差分隐私.
1.3 其他背景知识
前缀树[17]是哈希树的一种变体结构，通过对每一层节点进行遍历，减少不必要的节点比较，从而提高检索效率.
定义14. 前缀树.一个前缀树PT的结构可以被定义为PT=(Root,E,V)，其中Root表示前缀树PT的虚拟根且Root(PT)∈V；E代表前缀树节点之间边的集合；V表示前缀树节点的集合且v∈V.前缀树中的节点存储聚合后的轨迹位置点，在前缀树上同一个父节点下的所有轨迹序列都有相同的前缀.
定义15. Hilbert曲线.Hilbert空间填充曲线是一种无限迂回发展的空间填充曲线[24]，空间填充曲线是指用一条连续的曲线填满一个封闭的区域.
图1分别展示了一阶、二阶的Hilbert曲线图：
Fig.1 Hilbert curve
图1 Hilbert曲线图
1.4 攻击模型
定义16. 背景知识和上下文敏感信息攻击.背景知识通常是关于特定用户或数据集的相关信息.在一些文献中如文献[25]提出的攻击模型大多属于背景知识攻击的范畴，背景知识又称查询记录链接攻击.
表1中给出3个用户user1,user2,user3的活动轨迹以及出行方式，假设攻击者通过观察得到其中一用户的出行方式Subway，然后与数据集中的记录建立连接，可得知该用户user2的出行方式符合条件，从而也可以得到user2的轨迹以及其他相关的敏感信息.
Table 1 The Information of Users
表1 用户信息
用户轨迹出行方式user1l1→l2→l3Bike,walkinguser2l1→l3→l4Subway,bikeuser3l2→l3→l4Bus,bike
2 满足差分隐私的轨迹数据发布方案
2.1节介绍原始轨迹数据的预处理；2.2节介绍Hilbert曲线处理轨迹等价类；2.3节提出一个加噪前缀树的存储结构；2.4节介绍基于前缀树的差分隐私保护算法；2.5节介绍了数据的查询过程；2.6节对提出的算法进行分析.其算法流程图见图2.
Fig.2 Flowchart of trajectory data publishing algorithm
图2 轨迹数据发布算法流程图
2.1 原始轨迹数据预处理
在数据预处理阶段，本文需要完成2个步骤：
1) 识别轨迹的起始时间和终止时间.在轨迹数据集中，我们需要识别每条轨迹的起始时间和终止时间来构造轨迹等价类.本文我们设定一个时间阈值Δt作为时间间隔，并规定在该阈值中的轨迹都视为同一个轨迹等价类.例如，设置阈值Δt为10 min，当且仅当起始时间为[9:00,9:10]，终止时间为[10:00,10:10]的所有轨迹视为同一个轨迹等价类.因此存在轨迹等价类中的轨迹满足pt>0.
2) 构建轨迹等价类.为保证在相同时间段中的轨迹能够得到隐私保护，本文采用构建轨迹等价类方法，将第一步中的轨迹匿名在同一个匿名集中.考虑到实际场景中，为了减少轨迹数据的损失，可以适当将时间阈值Δt扩大，保证所有的轨迹得到匿名保护.
算法1描述了轨迹数据预处理过程.
算法1. 轨迹数据预处理.
输入：原始轨迹数据集D={T1,T2,…,T|D|},Δt；
输出：轨迹等价类EC、轨迹等价类距离矩阵TDM、轨迹时间重叠率矩阵PT.
① EC=∅，TDM，PT为空矩阵;
② for each Ti∈D
③ if Ti的开始和结束时间在规定范围内
then
④ Ti存入EC，EC={T1,T2,…,Tp}
(p≤n);
⑤ end if
⑥ end for
⑦ for Ti,Tj∈EC, i=1:p
⑧ for j=i+1:p
⑨ 利用式(1)和式(6)计算Ti和Tj的pt值及距离Dist(Ti,Tj);
⑩ pti,i=tdmi,i=0;
pti,j=pt;
tdmi,j=tdmj,i=Dist(Ti,Tj);
end for
end for
return EC={T1,T2,…,Tp}，TDM，PT.
算法1的行①～⑥为构建轨迹等价类，此过程仅判断每条轨迹是否在规定的范围内，轨迹数据集中有n条轨迹，则需要判断n次，因此可以在时间O(n)内完成.行⑦～为构建轨迹等价类的距离矩阵，构造距离矩阵需要计算n(n-1)/2次轨迹间的距离，则此过程可以在时间O(n2)内完成.因此算法1的完成时间在O(n2)内.由于存储到矩阵TDM和PT中，因此空间复杂度为O(n2).
算法2描述了算法1中行⑨求轨迹间距离Dist(Ti,Tj).
算法2. 多特征轨迹距离算法(multi-feature trajectory distance algorithm).
输入：等价类EC的任意2条轨迹P和Q，P={(x1,y1),(x2,y2),…,(xp,yp)}，Q={(x1,y1),(x2,y2),…,(xq,yq)}，轨迹时间同步率矩阵PT、方向距离权重α和速度距离权重β；
输出：Dist(P,Q).
① δdF(P,Q)=disto(P,Q)=distv(P,Q)=∅;
② 初始化一个p×q矩阵的矩阵C，其元素初始值均为-1;
③ for i=1 to p
④ for j=1 to q
⑤ if ci,j>-1
⑥ return ci,j;
⑦ else if i==0&&j==0
⑧ δdF(P,Q)=Euclid(P,Q);
⑨ else if i>0&&j==0
⑩ 递归计算ci-1,j的值，δdF(P,Q)=
max(ci-1,j,Euclid(P,Q));
else if i==0&&j>0
递归计算ci,j-1的值，δdF(P,Q)=
max(ci,j-1,Euclid(P,Q));
else if i>0&&j>0
递归计算ci-1,j，ci-1,j-1，ci,j-1的值.
δdF(P,Q)=max(min(ci-1,j,
ci-1,j-1,ci,j-1),Euclid(P,Q));
else δdF(P,Q)=∞
end if
return δdF(P,Q);
end for
end for
根据式(3)、式(6)计算轨迹间的方向距离
disto(P,Q);
根据式(3)、式(7)计算轨迹间的速度距离
distv(P,Q);
根据定义9得到轨迹间的距离
Dist(P,Q)=δdF(P,Q)+
α×disto(P,Q)+β×distv(P,Q);
return Dist(P,Q).
通过算法1和算法2完成对轨迹等价类的构建.2.2节介绍轨迹等价类的处理过程.
2.2 处理轨迹等价类
2.2.1 Hilbert曲线轨迹的划分
根据轨迹的时间特性和空间特性，我们对轨迹数据集D进行预处理，得到多个不同时间戳的轨迹集合.然后通过计算相同时间戳内的轨迹之间的距离，由此原始数据集D可以划分成时间戳不同的轨迹等价类ECi.最后，我们使用Hilbert曲线对每个轨迹等价类ECi内所有位置点Li进行编号.编号以后，根据位置点从小到大的编号，对于每个等价类ECi的位置点，选取k个点为一组，如果剩余位置点个数不足k个，也将其规定为一组.最终生成新的位置点集
该过程算法可分为3个步骤：
1) 通过计算轨迹之间的pt值和轨迹之间的距离Dist(Ti,Tj)，将原始数据集D划分成不同的轨迹等价类ECi.根据每个等价类ECi位置点集Li，计算各个位置点集Li的Hilbert曲线阶数order.
2) 使用多条Hilbert空间曲线对每个区域Li中的位置点进行标号，根据标号由小到大依次选择k个点划分为多个子集合
将剩余点个数不足k个的位置点划分为一组.
3) 使用差分隐私指数机制选择最小的划分半径，得到可用性较高的划分区域
算法3伪代码为：
算法3. 轨迹划分算法(DPRD).
输入：等价类ECi、位置点集合L={L1,L2,…,L|T|}、总隐私预算ε、划分区域子集中k个位置点；
输出：划分后的位置集
① 初始化
② 由轨迹等价类ECi得到每个位置点集Li;
③
④ for each 位置点集Li
⑤ 计算Li中位置点个数|Li|及Hilbert曲线的阶数
⑥ end for
⑦ 生成n条Hilbert曲线;
⑧ for each Hilbert curve
⑨ 根据差分隐私指数机制中的概率p选择半径
⑩ 输出最优的位置点集
end for
为了使Hilbert值更能逼近移动对象真实位置点，减少Hilbert编码的重复，此时每个区域中就必须有|Li|个网格来容纳这些位置点，所以Hilbert曲线的阶数满足：
2.2.2 轨迹的聚合
对轨迹划分后的集合Li进行下一步操作：将区域子集
内的位置点用该区域的中心点
代替.例如，轨迹等价类EC1中的位置点集合L1，其个数|L1|=8，经过Hilbert曲线划分后成为
假设k=4，则该区域
中的位置点被分为2个互不相交的子集分别为
和
子集中的所有位置点都由该区域的中心点代替.然后对其他等价类进行相同的操作，于是每个轨迹等价类中的位置点集合Li由当前子区域的中心点代替，并生成新的泛化时空的轨迹数据集
算法4描述了该过程.
算法4. 轨迹的聚合过程(TPOP).
输入：原始轨迹数据集D、轨迹等价类EC、位置点集合
输出：聚合后的轨迹数据集
① 初始化轨迹数据集
②
③ 计算集合
中每个子集中心点
④ for each T∈D
⑤ for each Li∈EC
⑥ 用对应的中心点代替当前区域的位置
⑦ end for
⑧
⑨ end for
⑩ end for
在经过算法3和算法4的处理之后，原始轨迹数据集D成为新的聚合轨迹数据集
每个位置点区域都由该区域的中心点来代替.
2.3 加噪前缀树的存储结构
前缀树是一种可以用来存储大量字符串的树形结构[17]，它的优点可以利用字符串的公共前缀来节省存储空间，最大限度地减少无谓的字符串比较，提高数据的查询效率.本节主要介绍前缀树存储轨迹数据的操作步骤：
1) 初始化.首先选择经过预处理后的轨迹集
存入到前缀树中，然后将每条轨迹被遍历的次数存入到节点中.根据前缀树的特性，定义节点的存储结构为
其中表示子区域的中心点，
表示经过该区域的次数，
表示当前中心点所在子集区域的敏感属性，
表示当前区域中包含的移动对象的个数.因为在时间戳内，同一个移动对象可能会产生多个位置点信息，所以我们规定在当前区域中的移动对象个数属于敏感信息.
2) 选择合适的节点.向前缀树中插入一条新轨迹时，首先从根节点开始向下遍历，比较要插入轨迹的第1个轨迹点，确定该轨迹点是否存在于第2层的节点中，如果存在就继续向下遍历下一层，直到遍历到某个节点没有相同前缀的位置点，则在当前节点vi下生成新的子节点vi+1存储轨迹数据.如果第1个位置点不存在前缀树中，则生成根节点的子节点，将轨迹的第1个位置点存入到该节点中，然后继续创建新的节点，将剩下所有的轨迹点依次存入新创建的节点中.最后对所有的位置点做步骤2)中相同的操作，直至所有的位置点存入到前缀树中.
3) 更新父节点.在前缀树中，如果子节点中不存在要存入轨迹的第1个位置点，则不需要更新除根节点以外其他节点信息.若插入的轨迹与前缀树上节点存储的轨迹有相同的前缀，则需要更新根节点和当前路径上的所有节点的信息，用于计数通过位置点的所有移动对象.
4) 加噪处理.经过步骤1)～3)处理后，节点中存储的信息需要进行保护，来抵御攻击者的攻击，所以我们采用拉普拉斯噪声对前缀树的节点计数进行保护.首先，对隐私预算ε采用等差分配方式，每一层的隐私预算为
其中i为前缀树当前层高，h为前缀树的树高，
然后遍历前缀树的每一层，对敏感数据进行添加噪声，并利用阈值限制噪声量的添加.最后将处理后的轨迹数据发布.
介绍一个构造前缀树的例子，如图3所示:
Fig.3 Prefix tree
图3 前缀树
其中前缀树的节点存储轨迹的位置点，位置点所在区域的移动对象个数，子集区域的背景知识和上下文敏感信息以及敏感信息计数值.以节点存储为例，计数值2表示通过中心点所在区域的轨迹个数，其背景知识和上下文敏感信息用sen11表示，计数值4表示原轨迹通过中心点所在区域的个数.
描述插入一条轨迹的过程.如图4所示，对前缀树新增一条轨迹
Fig.4 Insert a new trajectory in the prefix tree
图4 在前缀树中插入一条新的轨迹
按照前缀树的插入过程从根节点向下遍历节点，首先选择轨迹的第1个位置点分别与根节点的子节点进行比较，通过对比发现位置点已经存在根节点的左孩子节点中，并更新该节点的信息和其父节点的信息；然后依次向下找到剩余的位置点
和
通过对比可以看出也已经存在前缀树的节点中，并更新该节点和其所有父节点的信息.最后查找位置点
通过对比发现位置点
不存在前缀树中，因此需要创建新的节点存放该位置点信息，并更新该节点的所有父节点信息.
讨论轨迹插入的另一种情况，如图5所示，对图3中的前缀树插入一条新轨迹
根据前缀树插入过程，首先选取轨迹的第1个位置点
与前缀树根节点的孩子节点进行比较.通过对比，发现根节点的孩子节点中存储的位置点没有
因此生成一个新的孩子节点存储新轨迹的位置点.最后更新相关联的父节点信息.
Fig.5 Insert a new trajectory in the prefix tree
图5 在前缀树中插入一条新的轨迹
2.4 基于前缀树的差分隐私保护算法
通过遍历整个前缀树可以获得每条轨迹路径以及路径上移动对象的数量，并能判断出某个区域的密集程度和一些上下文非位置敏感信息.同时考虑到轨迹在时间和空间上的特性，若攻击者采取背景知识攻击和推理连接攻击，很容易获得移动对象的敏感信息，造成隐私泄露.为保证新轨迹的发布质量和可用性，我们使用前缀树结构存储轨迹数据，然后利用差分隐私技术对新轨迹位置点上的原始轨迹数、移动对象的数量等信息添加噪声，用于保护轨迹数据的隐私性.
本文采用一种隐私预算等差分配模型，并对每一层设置相应的阈值θi限制噪声量的添加.根据前缀树的特性，其父节点计数值等于该节点的所有子节点之和，规定节点vi∈V是节点vi+1∈V的父节点，ci和ci+1分别是节点vi和节点vi+1的计数值，其中i∈[1,h)，则ci≥ci+1.所以本文定义阈值θi=k×i-1+b,k>0,b>0，其中k，b为阈值θi的参数，随着前缀树层数的增高，阈值θi逐渐减少.若添加噪声量的节点计数值超过阈值，则重新选择噪声量添加，直至计数值小于阈值.本文规定整体隐私预算为ε，其中
用于指数机制，所以拉普拉斯噪声添加的隐私预算为每一层分配的隐私预算为其中i为层高，h为树高.
算法5. 基于前缀树的差分隐私保护算法(TDPP).
输入：聚合后的轨迹数据集
位置点集
总隐私预算ε、参数k和b；
输出：发布的轨迹数据集
① 创建一个高度为h的前缀树PT；
② 初始化
③ for i≤h
④
⑤ θi=k×i-1+b;
⑥ for 每一个节点vi的孩子节点vi+1
⑦ vi+1.count=vi+1.
⑧ if vi+1.count≤θithen
⑨ 节点vi+1存入到前缀树PT中;
⑩ sum=sum+vi+1.count;
if sum>vi.count then
break;
end if
end if
end for
while sum≤vi.count do
选择时间戳为ti+1的位置点添加到前缀树PT中;
end while
i++
end for
遍历前缀树PT，并输出轨迹数据集
原始数据集D经过数据预处理之后，得到新的轨迹数据集有
条轨迹，
构建前缀树过程中，轨迹数据集的每条轨迹扫描一次，将其作为从根节点到叶节点的路径插入到前缀树中.因为树高为h，可知最长路径为h，所以构建前缀树的时间复杂度为
由于Hilbert曲线对轨迹位置点进行划分，数据结构中只需要存储位置点的id和每个id对应的映射值，因此轨迹划分算法中的空间复杂度O(n).
算法5对前缀树每个节点添加拉普拉斯噪声，满足
从下向上选择节点并依次添加噪声，直至所有子节点的噪声计数值之和大于等于父节点的噪声值，此时满足差分隐私要求.该过程的时间复杂度为
对于遍历加噪前缀的每一层节点，其时间复杂度为
因为
与
为相邻数据集，故
由于对原始轨迹数据集处理后的轨迹集是按照位置时间戳来划分的，所以就有h≤|Time|.因此整个算法的时间复杂度为
2.5 数据的查询过程
除根节点外，前缀树的每个节点存储一个位置点，从根节点的子节点到叶子节点的路径构成一条轨迹，因此加噪前缀树支持对轨迹路径的查询.其查询的具体过程步骤为：
1) 从根节点开始向下访问包含轨迹位置点的所有节点.取出要查询轨迹的第1个位置点，然后检索前缀树中根节点的子节点是否存储该位置点.如果该位置点存在，则将节点中的移动对象的噪声计数值添加到查询结果中.如果查询的位置点不存在节点中，则查询结束.
2) 将要查询的位置点依次取出，然后根据步骤1)依次检索位置点是否存在前缀树的节点中，并将移动对象的噪声计数值添加到查询结果中.直至全部位置点检索完成.
3) 返回所有的查询结果和计数值总和.
图6所示，对轨迹
进行查询，并返回轨迹的移动对象计数值的查询结果.查询开始，首先从根节点的子节点开始层次遍历，选取查询轨迹的第1个位置点
并将该位置点与根节点的子节点进行匹配，找到第1个存储位置点的节点，将该节点中加噪的移动对象计数值添加到查询结果中.对位置点和做相同操作，依次将查询计数值添加到结果中.最后，将查询得到的结果21返回给用户.
Fig.6 The query process of the prefix tree
图6 前缀树的查询过程
2.6 算法分析
本节我们对提出的模型进行隐私性分析和数据可用性分析.
2.6.1 隐私性分析
轨迹隐私保护的衡量标准是通过攻击者能在发布轨迹集中识别出该轨迹概率的大小.为此我们证明所提出的方案满足差分隐私性质.
本文方案将整体隐私预算ε平均分为2个部分和其中εe用于指数机制进行最优解半径方案的选择，εl用于在构造前缀树中对计数结果添加Laplace噪声.在算法3中，我们采用指数机制选取所需的最优解，保证算法满足ε-差分隐私.根据轨迹的时间戳划分轨迹数据集生成若干个位置点集合，并对每个时间戳的位置点集合执行一次算法2，由差分隐私组合性质可得出引理1：
引理1. 轨迹区域划分算法(TRD)在整个轨迹数据集上可以保证|T|×ε-差分隐私.
算法4是轨迹位置点的聚合过程，由于k值的设定取决于轨迹等价类中的个数，因此k值取值过大导致数据可用性降低，取值过小导致隐私性降低.因此我们规定
表示隐私保护程度：
(13)
其中，
在算法5中，同一层上的所有节点都包含一组不相交的轨迹，根据并行组合性性质，同一层上的节点共享所消耗的隐私预算.每一层的隐私预算消耗为其中h为前缀树的树高，在算法4中消耗的总隐私预算为
根据引理1，我们得到定理1.
定理1. 整个方案过程消耗的隐私预算小于等于ε，即ε=εe+εl，本文方案满足ε-差分隐私保护.
2.6.2 数据的可用性
本文中的数据可用性分析主要分2个阶段：轨迹预处理阶段以及轨迹数据存储到前缀树.因此在轨迹预处理阶段中，我们将信息丢失率DOP作为本文衡量数据可用性的标准.当删除的轨迹数据占等价类中轨迹总数的比值越小，说明数据可用性越高，即：
(14)
其中，nEC表示等价类的数量，mi为每个等价类中所要删除的轨迹数量.
在轨迹数据存储到前缀树阶段中，我们引入定义17和18作为数据可用性的衡量标准，在保证数据隐私性的情况下，相对误差和平均树高误差越低，则说明数据的可用性越高.
定义17. 相对误差.对于计数查询Q，本文采用相对误差衡量加噪后发布的数据集D′对比于原始数据集D中数据的可利用率[26]：
(15)
其中，thr是一个阈值，用于防止在极小计数查询的情况下，分母为0，即Q(D)=0.
定义18. 平均树高误差.对于计数查询Q，本文采用平均树高误差衡量隐私保护后的数据集D′对比于原始数据集D中数据的可用性[27]：
(16)
3 实验分析
本文采用微软研究院发布的T-Drives数据库[28]，该数据集包含一周内10 357辆出租车的轨迹，总位置点约为480万个.表2为数据集D部分数据的格式，其中路径编号为移动对象的不同的轨迹，ID为移动对象的标识符，时间戳用于构建轨迹等价类.为验证本文算法的隐私性和数据的可用性，与Zhao等人提出的NTPT算法[27]进行对照实验.
Table 2 Partial Data Format of Dataset
表2 部分数据集格式
路径编号ID时间戳X坐标Y坐标4075043251013098257974292043241113336.5825566.01
本文的实验环境为Window10，Intel® Xeon® Silver 4214R @ 3.00 GHz，32 GB内存，采用Python和Jupyter NoteBook.
3.1 数据可用性分析
在轨迹预处理部分，本文引入了轨迹的时间特性以及轨迹间的速度距离v和方向距离o，通过计算其轨迹间的距离值，将原始轨迹数据集D划分成多个时间戳不同的轨迹等价类.
图7中展示了方向距离的参数α和速度距离参数β分别为(0,1)，(0.4,0.6)，(0.6,0.4)，(1,0)随着k值增大，信息丢失率的变化趋势.从图7可以看出，在相同的k值下，(α,β)=(0,1)或(1,0)的信息丢失率较高于(α,β)=(0.4,0.6)或(0.6,0.4).因为当其中一个参数为0时，其约束条件减少，导致计算轨迹间的相似程度误差较大，因此在使用Hilbert曲线划分轨迹等价类时，会产生较高的误差，造成数据可用性降低.同样，随着k值的增加，信息丢失率也随之增高，因为k值越大，轨迹间的相似程度偏差越大，数据可用性越低.因此，本文实验中取参数(α,β)=(0.4,0.6)以及k=70.
Fig.7 Data loss rate under different parameters (α，β)
图7 不同参数(α，β)的数据丢失程度
3.1.1 隐私预算对误差的影响
在不同的隐私预算下，根据不同的查询长度我们进行2组实验，查询长度|Q|分别取值4和8.为了保证实验数据的真实性，每组查询对象都是从树存储结构中取得，每组实验测100次，且每组实验中添加噪声方式与Zhao等人[28]一致并具有随机性，最后取得100次结果的平均值做为最终结果.
图8中分别给出了查询长度为4和8的平均相对误差.从图8(a)和(b)可以看出，在相同的查询长度下，平均相对误差随着隐私预算的增加而减小.这是因为每一层节点的噪声量随着隐私预算的增加而减小，所以数据量的相对误差也随之减小.同样，从实验图中可以看出平均相对误差随着查询长度的增加而减小，因为随着查询长度的增加，导致树高也在增加，叶子节点中的噪声量随着阈值的限制而减小，因此平均相对误差也逐渐减小.
Fig.8 The effect of privacy budget on the average relative error under different query length Q
图8 查询长度Q不同时隐私预算对平均相对误差的影响
通过实验结果我们可以得出，在相同的隐私预算下，本文的TDPP算法在平均相对误差上较低于NTPT算法.
3.1.2 树高对误差的影响
本组实验测试了树高的变化在不同隐私预算下对平均误差的影响.根据本文的实验数据和隐私预算的大小，我们设置了3组实验.由于本实验前缀树中存储的轨迹最长长度为9，所以树的高度为9.因此在相同的隐私预算下，每组实验中的树高取2,4,6,8，并测得每个树高所对应的树高误差值.每组实验测试100次，取平均树高误差作为最终结果.
如图9(a)～(c)，实验表明平均树高误差随着树高的增加而减小.因为隐私预算随前缀树的高度增加而减小，所以叶子节点中的噪声量也会随之减少.对比3组实验，平均树高误差随着隐私预算的增加而减小，因为隐私预算的增加导致噪声量的添加减小，所测得平均树高误差也相应减小.从图9可以看出本文方案的平均树高误差同样较低于NTPT算法.
Fig.9 The effect of height on the average height error under different ε
图9 树高对平均树高误差影响
因此，本文提出的TDPP算法不仅在平均相对误差值上较低于NTPT算法，同样在平均树高误差值上也较低于NTPT算法.因此可以证明出本文的TDPP算法的数据可用性较优于NTPT算法.
3.2 隐私性分析
本文方案在轨迹预处理阶段，由于轨迹的时空特性，因此在时间和空间上对轨迹划分成多个轨迹等价类.考虑到在计算轨迹之间的距离时，参数的改变会影响隐私保护程度，因此在图10中给出了本文算法在不同的k值下，隐私保护程度在方向距离的参数α和速度距离参数β分别为(0,1)，(0.4,0.6)，(0.6,0.4)，(1,0)时的变化趋势.
Fig.10 Privacy protection level under different parameters (α，β)
图10 不同参数(α，β)下的隐私保护程度
如图10所示，隐私保护程度随着k值的增高而降低，因为聚类的轨迹数量越多，数据的可用性也就越高，但隐私保护程度随之下降.当参数α,β为(0,1)和(1,0)时，隐私保护程度较低于参数为(0.4,0.6)，(0.6,0.4)时的情况，因为参数为0时，轨迹之间减少一个约束条件，导致轨迹间的相似度下降，攻击者越容易识别出其中某个轨迹，故隐私保护程度也会随之降低.当参数α,β为(0.4,0.6)，(0.6,0.4)时，隐私保护程度接近，因为根据不同用户的保护需求，所提供的不同的隐私保护水平，但在总体上的隐私保护程度是接近一致的.
因此，本文方案不仅考虑了数据的可用性，同时也保证了数据的隐私性.综上，参数(α,β)取值(0.4,0.6)，k取值70.
为保证轨迹数据的安全性和可控性，本文采用差分隐私技术，并将Laplace噪声添加到存储轨迹位置点的节点中.本组实验测试了不同的树高在不同的隐私预算下对平均相对误差和平均树高误差的影响.图11的实验测试树高的变化对平均相对误差的影响，图12的实验测试树高的变化对平均树高误差的影响.从这2组实验中可以看出，平均相对误差和平均树高误差随着树高的增加而减小，随着隐私预算的增加也减小.因此，控制隐私预算的合理分配不仅可以保证轨迹数据的可用性，也能保证数据的隐私性.
Fig.11 The average relative error of different privacy budgets
图11 不同隐私预算的平均相对误差
Fig.12 The average height error of different privacy budgets
图12 不同隐私预算的平均树高误差
4 总结与展望
随着人们进入大数据时代，位置感知设备在日常生活中发挥重要作用，它主要通过收集用户的位置信息提供高质量服务，但其中可能也包含大量的敏感信息数据.针对该问题，本文提出一种基于差分隐私的轨迹数据发布方法.根据轨迹大数据的特性以及轨迹路径的特点，本文提出一种基于前缀树的存储结构用于存储划分后的轨迹位置点，然后利用TDPP算法对节点中的敏感数据添加噪声，用于保护轨迹数据隐私.最后，本文在真实数据集上进行了数据可用性和隐私性的实验，并与NTPT算法进行对照实验，结果表明，本文算法具有较低的平均相对误差和平均树高误差，优于NTPT算法.
隐私保护是当前社会局势的一个热门领域，其中对轨迹数据的隐私保护是一个具有重要意义的研究方向.如今越来越多的“可信”第三方数据收集者并不可信，甚至一些基于位置服务的软件在用户不知情的情况下有意或无意地泄露用户的原始数据，造成大量的数据隐私泄露.考虑轨迹数据的特点，今后的研究工作可以主要针对3个方面：1)数据量大，构建存储结构应考虑遍历快，减少存储空间等特性.2)提高数据的可用性，可减少噪声量的添加，但需保证数据的隐私性.3)针对第三方收集者，可以考虑本地差分隐私技术对位置或其他敏感信息进行收集和发布，从数据源端遏制用户信息的泄露.
[1]Sweeney L. K-anonymity: A model for protecting privacy[J]. International Journal of Uncertainty Fuzziness & Knowledge Based Systems, 2002, 10(5): 557-570.
[2]Gruteser M, Grunwald D. Anonymous usage of location-based services through spatial and temporal cloaking[C] //Proc of the 1st Int Conf on Mobile Systems, Applications and Services. 2003: 31-42.
[3]Chow C Y, Mokbel M F, Aref W G. Casper: Query processing for location services without compromising privacy[J]. ACM Transactions on Database System, 2009, 34(4): 1-48.
[4]Wang Ke, Benjamin CM Fung. Anonymizing sequential releases[C] //Proc of the 12th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York, NY, USA: Association of Computing Machinery, 2006: 414-423.
[5]Zhang Qing, Koudas N, Srivastava D, et al. Aggregate query answering on anonymized tables[C] //Proc of 2007 IEEE 23rd Int Conf on data engineering. Piscataway, NJ: IEEE, 2007: 116-125.
[6]Machanavajjhala A, Kifer D, Gehrke J, et al. l-diversity: Privacy beyond K-anonymity[J]. ACM Transactions on Knowledge Discovery from Data, 2007, 1(1): No.3.
[7]Li Ninghui, Li Tiancheng, Venkatasubramanian S. t-closeness: Privacy beyond K-anonymity and l-diversity[C] //Proc of 2007 IEEE 23rd Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2007: 106-115.
[8]Li Ninghui, Li Tiancheng, Venkatasubramanian S. Closeness: A new privacy measure for data publishing[J]. IEEE Transactions on Knowledge and Data Engineering, 2010, 22(7): 943-956.
[9]Dwork C, Kenthapadi K, McSherry F, et al. Our data, ourselves: Privacy via distributed noise generation[C] //Proc of Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2006: 486-503.
[10]Dwork C, McSherry F, Nissim K, et al. Calibrating noise to sensitivity in private data analysis[C] //Proc of Theory of Cryptography Conf. Berlin: Springer, 2006: 265-284.
[11]Jun Ren, Xiong Jinbo, Yao Zhiqiang, et al. DPLK-means: A novel differential privacy K-means mechanism[C] //Proc of 2017 IEEE 2nd Int Conf on Data Science in Cyberspace (DSC). Piscataway, NJ: IEEE, 2017: 133-139.
[12]Zhu Tianqiang, Li Gang, Zhou Wanlei, et al. Differentially private data publishing and analysis: A survey[J]. IEEE Transactions on Knowledge and Data Engineering, 2017, 29(8): 1619-1638.
[13]Andrés M E, Bordenabe N E, Chatzikokolakis K, et al. Geo-indistinguishability: Differential privacy for location-based systems[C] //Proc of the 2013 ACM SIGSAC Conf on Computer & Communications Security. New York: ACM, 2013: 901-914.
[14]Dewri R. Local differential perturbations: Location privacy under approximate knowledge attackers[J]. IEEE Transactions on Mobile Computing, 2012, 12(12): 2360-2372.
[15]Gursoy M E, Liu Ling, Truex S, et al. Differentially private and utility preserving publication of trajectory data[J]. IEEE Transactions on Mobile Computing, 2018, 18(10): 2315-2329.
[16]Deldar F, Abadi M. PDP-SAG: Personalized privacy protection in moving objects databases by combining differential privacy and sensitive attribute generalization[J]. IEEE Access, 2019, 7: 85887-85902.
[17]Chen Rui, Fung B C M, Desai B C, et al. Differentially private transit data publication: A case study on the montreal transportation system[C] //Proc of the 18th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2012: 213-221.
[18]Al-Hussaeni K, Fung B C M, Iqbal F, et al. SafePath: Differentially-private publishing of passenger trajectories in transportation systems[J]. Computer Networks, 2018, 143: 126-139.
[19]Zhao Xiaodong, Dong Yulan, Pi Dechang. Novel trajectory data publishing method under differential privacy[J]. Expert Systems with Applications, 2019, 138: No.112791.
[20]Yu Qingying, Luo Yonglong, Chen Chuanming, et al. Trajectory similarity clustering based on multi-feature distance measurement[J]. Applied Intelligence, 2019, 49(6): 2315-2338.
[21]Agarwal P K, Avraham R B, Kaplan H, et al. Computing the discrete Fréchet distance in subquadratic time[J]. SIAM Journal on Computing, 2014, 43(2): 429-449.
[22]McSherry F, Talwar K. Mechanism design via differential privacy[C] //Proc of 48th Annual IEEE Symp on Foundations of Computer Science (FOCS’07). Piscataway, NJ: IEEE, 2007: 94-103.
[23]Feng Dengguo, Zhang Min, Ye Yutong. Research on location trajectory publishing technology based on differential privacy model[J]. Journal of Electronics & Information Technology, 2020, 42(1): 74-88 (in Chinese)(冯登国, 张敏, 叶宇桐. 基于差分隐私模型的位置轨迹发布技术研究[J]. 电子与信息学报, 2020, 42(1): 74-88).
[24]Moon B, Jagadish H V, Faloutsos C, et al. Analysis of the clustering properties of the Hilbert space-filling curve[J]. IEEE Transactions on Knowledge and Data Engineering, 2001, 13(1): 124-141.
[25]Fung B C M, Wang Ke, Chen Rui, et al. Privacy-preserving data publishing: A survey of recent developments[J]. ACM Computing Surveys, 2010, 42(4): No.14.
[26]Xiao Xiaokui, Bender G, Hay M, et al. iReduct: Differential privacy with reduced relative errors[C] //Proc of the 2011 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2011: 229-240.
[27]Zhao Xiaodong, Pi Dechang, Chen Junfu. Novel trajectory privacy-preserving method based on prefix tree using differential privacy[J]. Knowledge-Based Systems, 2020, 198: No.105940.
[28]Yuan Jing, Zheng Y,u Zhang Chengyang, et al. T-drive: Driving directions based on taxi trajectories[C] //Proc of the 18th SIGSPATIAL Int Conf on Advances in Geographic Information Systems. New York: Association of Computing Machinery, 2010: 99-108
