基于本地化差分隐私的时序位置发布方案研究

康海燕，冀源蕊

（北京信息科技大学信息管理学院信息安全系，北京 100192）

1 引言

随着GPS定位技术和可穿戴设备的广泛应用，基于位置的服务（Location Based Service，LBS）可以提供诸如实时位置共享、路线导航和兴趣点查询等服务，为人们的生活提供了便利.与此同时，这些移动设备不断记录着用户的位置数据，LBS服务通过收集并发布这些位置数据可以为数据分析提供基础数据，结合数据挖掘和机器学习等技术对位置轨迹大数据的分析，企业可以用挖掘有价值的商业信息，政府部门可以通过分析交通数据进行道路规划［1］，在COVID-19疫情防控背景下，政府部门可以通过对用户位置数据的收集和分析实现接触者追踪和疫情传播监控［2］.然而位置数据中包含大量个体的隐私信息，如果不加保护直接发布会造成大量用户的隐私泄露，用户对隐私问题的顾虑限制了其分享个人位置数据的意愿，阻碍了位置大数据的收集和分析工作，因此针对位置数据发布时的隐私保护研究具有必要性.

最早用于解决位置数据隐私发布的方案是k-匿名技术，如Gedik等［3］提出的匿名位置发布方法，通过对轨迹Ti在任意时刻采样，使得在该时刻内，至少有k-1条轨迹在相应的位置能和Ti泛化在同一区域内然而k-匿名理论面临的最大问题是，一旦攻击者能力超过了预先的假设，就能够进一步区分等价类内的不同记录，实现去匿名化.由Dwork等［4］提出的差分隐私技术因其严格的数学定义备受青睐，是目前最受欢迎的隐私保护技术，在隐私保护的数据分析与数据发布领域应用广泛［5］.而在位置轨迹隐私发布背景下，基于差分隐私模型的研究同样取得了许多成果［6～17］.然而现有的差分隐私模型下位置轨迹发布的方案存在以下不足：（1）现有方案基于第三方LBS服务可信的前提假设，对收集到的位置数据进行集中加噪处理后再发布，没有考虑第三方服务器不可信的情况.（2）现有方案在隐私保护选择上不够灵活，只允许用户根据单一的隐私预算决定隐私保护程度.（3）现有方案将轨迹发布看作一系列连续位置的发布，没有考虑连续提交多个位置数据的情况下时序关联对位置隐私发布的影响.

为了解决以上问题，本文进行了深入研究，主要贡献如下：（1）提出一种定制隐私策略位置扰动算法（Customized Privacy policy Location Perturbation algorithm，CPLP），允许用户在本地对位置数据加噪后上传给LBS服务器，通过定制隐私策略实现多隐私因子支持.（2）结合隐马尔可夫模型提出一种时序关联位置隐私发布算法（Temporal Relational Location Privacy publishing algorithm，TRLP），解决时序关联对位置隐私发布的影响.（3）在GeoLife数据集和Gowalla数据集上通过大量的对比实验验证了该模型的可用性.

2 研究现状

2.1 中心化差分隐私位置数据发布

中心化差分隐私模型下的位置数据发布形式包括空间直方图、地理位置熵和轨迹数据集.空间直方图是位置轨迹发布的经典形式，差分隐私模型通过对空间直方图添加随机噪声，发布加噪后的直方图来抵御攻击者对于数据集中是否包含某用户的推测攻击.然而直接对构成直方图的每个网格单元添加噪声导致查询结果的误差太大，为了提高任意范围内查询结果的精度，通常采用四叉树［9］对划分后的网格提供索引服务，树中的每个节点代表本区域范围内的位置轨迹数目，由于该数目涉及用户的位置隐私，通过对节点计数查询添加噪声实现差分隐私，在响应用户的计数查询时，采用类似索引树的查询模式自上而下在四叉树中搜索与该查询节点匹配的节点集合，根据加噪后的节点计数结果进行回答.为了解决位置数据分布不均衡导致四叉树中添加噪声过大的问题，Hay等［10］提出一种基于k-叉平均树的位置数据构建方法，使得划分后直方图各个区间内位置轨迹数目比较均衡，同时通过最优线性无偏估计对其进行一致性修正，降低中间节点造成的查询噪声误差.Zhang等［11］提出一种基于不完全四叉树的位置发布方法PrivTree，通过对高维空间数据进行合理的划分摆脱了加入噪声时树高的影响，并采用局部敏感度和近似误差的方法降低噪声误差.为了解决轨迹中多个单元的子轨迹被重复计数导致大范围内轨迹聚集查询误差较大的问题，Xie等［12］提出了层次化模型（Euler Histograms Tree，EHT），通过降低子轨迹重复带来的查询误差以支持矩形空间聚集查询.除了直接发布位置轨迹的计数信息，位置相关统计信息还包括位置熵（Location Entropy，LE），位置熵以熵的形式衡量地理位置受用户欢迎的程度，熵越大，说明该地理位置越受用户欢迎.为了防止攻击者根据发布的位置熵直方图推测出某个用户的位置隐私，To等［13］采用拉普拉斯机制对位置熵进行噪声处理，注入噪声的规模由全局敏感度决定，为了解决全局敏感度导致噪声过大的问题，采用本地敏感度或平滑敏感度的方法代替全局敏感度.

空间直方图和位置熵的缺陷在于丢弃了用户轨迹的时序信息，无法满足数据使用者对序列进行深入分析的需求，而直接发布轨迹数据可以在最大程度上保留轨迹的时序特征.目前有基于树重构和轨迹聚类等多种差分隐私轨迹发布方法.如Chen等［14］提出一种基于前缀树的轨迹差分隐私保护方法，通过构造加噪前缀树并为加噪前缀树中每个节点计数添加噪声实现差分隐私.霍峥等［15］在噪音树的基础上分别针对自由空间和路网空间提出了两种差分隐私轨迹数据发布方法.基于聚类的轨迹发布方法［16］在位置精度高，候选位置集合规模大的情况下更适用.这种方法采用分阶段处理的思想，将长度为的轨迹集处理分为个阶段，在每个阶段对所有位置进行聚类分组，使用聚类中心点代替该聚类中的真实位置点，通过在聚类中心点的随机化和轨迹计数的随机化过程中引入随机化噪声实现差分隐私，最后发布扰动后的数据集.如Zhao等［17］提出的差分隐私轨迹聚类算法TLDP（Trajectory Location Data Protection），通过将Laplace噪声添加到轨迹计数中来抵抗连续查询攻击.

2.2 本地化差分隐私研究现状

与传统的差分隐私［4］技术相比，本地化差分隐私技术已经成为一种更为健壮的隐私保护模型，与传统的中心化差分隐私不同，该技术的核心思路是在本地给用户数据添加满足本地化差分隐私的扰动，将扰动后数据传输给第三方数据收集者，再通过一系列查询操作得到有效的结果.本地化差分隐私的目标在于解决服务器不可信场景下数据的安全采集与分析问题.本地化差分隐私中常用的扰动机制是随机响应，如杨高明等提出一种满足本地化差分隐私约束的关联属性不变后随机响应扰动方法［18］.除此以外还有压缩机制Compression［19］和扭曲机制Distortion［20］.这些扰动机制在频数统计、均值估计和机器学习等学术领域有大量应用［21］.除了学术研究以外，本地化差分隐私在工业界也有所应用，如苹果公司将该技术应用在操作系统ios 10上以隐私保护的方式收集用户的统计数据［22］，谷歌公司同样使用该技术从Chrome浏览器上采集用户的行为统计数据［23］.

3 背景知识

3.1 位置数据建模

本文使用两种坐标系来表示用户的位置点.一种是状态坐标系，将原始地图划分成多个网格，使得每个网格单元表示用户的一个位置状态.另一种是地图坐标，通过二维经纬度坐标点来表示用户的位置.

这两种坐标系之间可以互相转化，状态坐标中每个网格单元的索引可以由经纬度表示，从而对应到地图坐标上.如图1所示，横坐标表示向东方向数据，纵坐标表示向北方向数据，网格表示位置状态.

图1 状态坐标系和地图坐标转化示意图

对于位置域S={s1，s2，…，sN}，记si(1≤i≤N)代表图上的第i个网格单元，该网格单元表示为一个单位向量，其中第i个元素为1，其余N-1个元素为0，用二维向量xt表示t时刻用户在地图坐标上的位置，xt[0]表示该位置点的经度，xt[1]表示该位置点的维度，与t时刻用户在状态坐标上的真实位置互相对应，位置查询f(s)：s→R2表示网络坐标中位置点到地图坐标的映射，以图1为例，设用户位置域S={s1，s2，…，s56}，若用户在t时刻真实位置状态为s10，则s10=[0，0，0，0，0，0，0，0，0，1，…，0]，对应地图坐标xt=[3，5]，即s10的维度坐标为3，经度坐标为5，存在位置查询f(s10)=[3，5].

3.2 位置隐私攻击

在位置隐私发布的研究背景下，针对位置的隐私攻击可视为根据发布的扰动位置推测出某时刻用户真实位置的过程，本文采用隐马尔可夫模型对该过程进行建模.每一时刻用户的真实位置是不可观测的，对应隐马尔可夫模型中的隐藏状态，经过隐私保护处理（如4.2中的CPLP算法）后发布的位置数据可由攻击者直接观察得到，对应隐马尔可夫模型中的观测状态，记矩阵M∈[0，1]N×N为用户的位置状态转移矩阵，矩阵中的元素mij表示由位置状态si转移到位置状态sj的概率大小，在后续隐私保护位置扰动算法设计中，假设矩阵M可根据用户的历史位置数据训练得到.在位置攻击模型中，t时刻用户的位置状态可以通过概 率 分 布pt∈[0，1]1×N表 示，其 中代表t时刻用户真实位置位于si的可能性大小，假设t时刻用户以相同的概率分布于位置集合S={s1，s3，s4，s6}中，则此时用户的位置概率分布表示为pt=[1/4，0，1/4，1/4，0，1/4，0，0，...，0].再使用和分别表示攻击者观察扰动输出zt前后该时刻位置状态的先验概率和后验概率.t时刻的先验概率可以通过前一时刻t-1的后验概率结合状态转移矩阵M计算得到，即后验概率可根据式（1）中的贝叶斯公式计算，其中表示隐马尔可夫模型的发射概率，即在给定真实位置概率分布的情况下输出扰动位置为zt的概率.

假设攻击者掌握的背景知识包括隐马尔可夫模型的状态转移矩阵和初始概率分布，则攻击者可以推测出t时刻用户可能出现的位置，表现为该时刻先验概率大于0的位置，将这个区域定义为时序关联域Ct，如定义1所示.

定义1时序关联域.时序关联域Ct代表t时刻用户所有可能出现的位置集合，即0，si∈S}.

3.3 本地化差分隐私

本地化差分隐私模型基于严格的数学背景，形式化定义如下所示.

定义2ε-本地化差分隐私［21］.给定n个用户，每个用户对应一条记录，对于随机化算法A，其定义域为Dom(A)，值域为Ran(A)，若算法A在任意两条记录t和t'(t，t'∈Dom(A))上得到相同输出结果(o(o⊆Ran(A)))的概率满足Pr(A(t)=o)≤eεPr(A(t')=o)，则称算法A满足ε-本地化差分隐私.

本地化差分隐私技术通过控制任意两条记录输出结果的相似性来确保算法的隐私性，即根据随机化算法A的某个输出结果无法推测出输入数据为哪一条记录，根据3.2节中位置隐私攻击的描述，位置隐私发布的目标就是确保攻击者不能根据已发布的扰动位置推测出某个时刻用户的真实位置，也就是保证时序关联域中任意两个位置不能被攻击者区分出来，基于此本文提出ε-不可区分性的定义，表示时序关联域内的差分隐私.

定义3ε-不可区分性.对于时序关联域中相邻的两个位置si和sj，在随机化算法A的作用下，若对任意输出o⊆Ran(A)，存在Pr(A(si)=o)≤eεPr(A(sj)=o)成立，则称随机化算法A满足不可区分性.

定义3中参数ε非负，表示隐私保护的程度，该参数越小隐私保护的程度越高.由于定义2只是理论模型，而要实现具体的位置差分隐私则需要噪声机制的介入，Laplace机制是实现差分隐私最常用的方法，该机制建立在l1-敏感度（l1-norm Sensitivity）的基础上，相关定义如下：

定义4l1-敏感度［4］.对于查询f(s)：s→R2，l1-敏感度指f(x1)-f(x2)的最大l1范式值，如式（2），其中x1和x2是相邻数据集中的两个元素.

定义5Laplace机制［4］.对于查询f(s)：s→R2，查询函数的敏感度为Δf，如果查询算法A满足式（3），则算法A具有ε-不可区分性，所添加的噪声符合位置参数为0，尺度参数为Δf/ε的拉普拉斯分布.其中，敏感度Δf表示两个相邻位置查询结果的最大l1范式值.

位置隐私保护中另一种高效的扰动机制是Xiao等［24］提出的平面各向同性扰动机制（Planar Isotropic Mechanism，PIM），该机制基于计算几何学［25］中凸包（Convex Hull）和各向同性位置（Isotropic Position）的定义构造凸包敏感度，并基于K-机制［25］生成噪声.

定义6凸包［25］（Convex Hull）.对于给定集合X={x1，x1，…，xn}，包含X中所有点的凸集称作X的凸包，记作Conv(X)，凸包可以用X中所有点的线性组合来构造.

定义7各向同性位置［25］（Isotropic Position）.若凸集K⊆Rd满足式（4），则称K位于各向同性位置上，式中LK表示每个单位向量的各向同性常数.

定义8凸包敏感度［24］（Sensitivity Hull）.对于位置s和查询f(s)：s→R2，凸包敏感度K是Δf的凸包，如式（5）所示，Δf表示时序关联域中两个位置点x1和x2的查询差值.

定义9K-机制［25］（K-norm Mechanism）.对于给定的查询函数f(s)：s→Rd以及凸包敏感度K，若任意扰动输出z的概率分布满足式（6），则称其满足K-机制，式中表示凸包敏感度，Γ()表示伽马函数，‖·‖K表示凸包敏感度的闵可夫斯基范数.

4 本地化差分隐私时序位置发布模型

为了解决位置数据发布时存在的隐私泄露问题，本文设计了一种基于本地化差分隐私的时序位置发布模型，如图2所示，模型主要思想为允许用户在本地进行隐私策略的定制，根据定制的隐私策略对时序关联的位置数据添加噪声后发布，实现位置数据发布时的隐私保护.

图2 本地化差分隐私时序位置发布模型

在用户端，模型由两个主要算法构成，分别是基于定制隐私策略的位置扰动算法CPLP和基于隐马尔可夫模型的时序关联位置隐私发布算法TRLP.将经过隐私保护处理后的时序位置进行发布，并上传给LBS服务器，用于后续的位置大数据分析工作.

4.1 定制隐私策略

本文参考Blowfish Privacy［26］来设计位置隐私发布时的定制隐私策略.Blowfish Privacy是一种针对统计数据集的定制隐私保护方案，使用无向图的节点表示需要保护的数据集，边表示对两个数据集提供不可区分性，用户可以在本地通过定制无向图来决定隐私保护程度，然而Blowfish Privacy并不能直接应用在位置数据中，因此结合3.1中定义的位置网格坐标，将定制隐私引入位置数据的隐私保护发布中，提出隐私策略的定义，如定义9所示.

定义10隐私策略.隐私策略表示为一个无向图G=(S，ξ)，其中S是无向图的节点，代表网格坐标中需要保护的位置状态点，ξ是无向图的边，代表为两个节点提供ε-不可区分性.

图3展示了几种不同的隐私策略，如图3（a）表示一种宽松的隐私策略，图中所有节点都没有连线，表示可以直接发布用户真实位置，不提供位置隐私保护（仍然需要提供匿名隐私保护），图3（b）的隐私策略为区域内部分位置点之间提供不可区分性，但不要求对图中所有节点提供不可区分性.与图3（b）相比，图3（c）的隐私要求更为严格，需要保护所选区域内所有位置点之间的隐私性，表现为一个全连接图，这种隐私策略适用于对隐私需求很高的用户.

除了选择图3所示的隐私保护级别外，若用户需要更严格的隐私策略，还可进一步通过定制隐私策略的粒度调整隐私保护级别，粒度代表所保护最小位置范围.模型为用户提供如图4所示三种粒度的隐私策略，分别是PGk9，PGk16，PGk25，下标中的数字表示隐私策略的粒度，图4中黑色边框表示提供隐私保护的最小位置范围，以PGk9为例，该隐私策略表示网格坐标中每9个网格单元（3×3）内所有位置点彼此完全连接，即在该区域内所有点之间都有连接路径，是一个3×3的全连接图，需要保证该区域内所有位置点不可区分.

图3 定制隐私策略示意图

图4 三种隐私策略粒度示意图

为了将定制隐私策略应用到位置差分隐私中，本文结合定义1中的时序关联域Ct，给出时序关联域隐私策略的定义.定义11时序关联域隐私策略.t时刻的时序关联域隐私策略是隐私策略G在时序关联域中Ct的子图，只包含属于时序关联域Ct中的边，即GC=(C，ξC)，其中C⊆S且ξC⊆ξ.

在传统差分隐私定义中，相邻数据集（neighboring databases）被定义为只相差一条记录的两个数据集，在定制隐私策略的背景下，引入相邻节点的概念.

定义12相邻节点集合N(s).位置s的相邻节点是指和s有公共边连接的一系列节点集合，记作N(s)，则有N(s)={s'|dG(s，s')=1，s'∈S}，用dG(si，sj)表示隐私 策略上点si和sj之间的距离，该距离可通过两点间最短路径数计算.

结合时序关联域隐私策略，本文提出{ε，G}-位置差分隐私的定义，通过确保时序关联域隐私策略中每一对相邻节点的ε-不可区分性，使得攻击者无法区分时序关联域隐私策略中的相邻位置点.

定义13{ε，G}-位置差分隐私.给定一个随机化算法A，对于时序关联域隐私策略中所有相邻节点s和s'，若对于任意的输出z⊆Ran(A)，存在Pr(A(s)=z)≤eεPr(A(s')=z)成立，则认为s和s'满足{ε，G}-位置差分隐私.

引理1对于随机化算法A，当且仅当时序关联域隐私策略中任意两个节点满足ε-不可区分性时，算法A才满足{ε，G}-位置差分隐私.

4.2 定制隐私策略位置扰动算法

在4.1节中，本文根据定制隐私策略对位置差分隐私模型进行了拓展，提出了{ε，G}-位置差分隐私，本节设计一种基于定制隐私策略的位置扰动算法CPLP，对单一时刻真实位置的查询结果添加噪声，生成扰动位置，在4.4.1节证明所提算法满足{ε，G}-位置差分隐私.对位置数据的扰动可以看作以隐私保护的方式响应查询函数，使得攻击者无法根据扰动后的位置推测出用户的真实位置，具体流程如算法1所示.

算法1定制隐私策略位置扰动算法(CPLP)输入:隐私预算ε,时序关联隐私策略GC t,真实位置s输出:扰动位置z 1. 根据定义12计算相邻位置点集合NP(s):2. Δf G=[]3. FOR i IN range(len(Np(s)))4. FOR j IN range(i，len(Np(s)))5. Δf G.append(f(si)-f(sj))6. END FOR 7. END FOR 8. KI(GC t)=Conv(Δf G)9. 从K(GC t)中采样得到(y1，y2，…，yl)10. 根据式(8)计算矩阵T 11. KI(G)=TK(G)12. 从KI(G)中采样得到z″13. 从Γ(3，ε-1)中采样得到r 14. z″=rT-1z″15. z'←f(s)+z″16. z←find_nearest_location(z')RETURN z

首先是查询函数敏感度的计算.传统差分隐私中查询函数的敏感度代表有无某条数据记录对查询结果的最大影响值，在本文定制隐私策略的背景下，查询函数的敏感度代表查询时序关联隐私策略域中相邻位置节点时查询结果的最大变化值，在定制隐私策略背景下，查询函数的的敏感度计算方法进行对应算法1中步骤1～7，对于t时刻的位置状态s，根据时序关联域隐私策略，结合定义12计算当前时刻真实位置状态在时序关联域隐私策略中相邻位置点的集合NP(s)，用Δf G表示NP(s)中每两个位置查询差值结果的集合，计算公式如式（7）所示.

其次将凸包敏感度应用到定制隐私策略位置扰动的背景中.通过计算Δf G的凸包得到凸包可直观理解为由集合X={x1，x1，…，xn}最外沿的所有点连接所组成的凸多边形表示t时刻查询函数的敏感度，记作隐私策略凸包敏感度，表现为一组二维坐标对.将平面各向同性扰动机制应用到定制隐私策略位置扰动的过程对应算法1中步骤8～11，对于所得的隐私策略凸包敏感度根据定义7将转化为其各向同性位置从集合中均匀采样得到y1，y2，…，yl，代入式（8）中计算矩阵可根据矩阵相乘得来，即在二维平面上一个凸包的各向同性位置可直观理解为保持凸包原始方向不变，以凸包的各个顶点为坐标中心对凸包进行旋转排列构成的图形.

最后是扰动噪声的生成过程.对应算法1中步骤12～14，先从中均匀采样得到z″，再从伽马分布Γ(3，ε-1)中随机产生变量r，此时得到噪声z″=rz″，将得到的结果转换回中得z″=T-1z″，这里的z″就是添加的噪声大小，表现为一个二维向量.算法1中第15步表示对t时刻真实位置状态的查询结果添加噪声，得z'=f(s)+z″.算 法1中 第16步 所 用 到 的 函 数find_nearest_location(z')表示在地图坐标系中找到距离z'最近的真实位置z作为扰动输出返回.记t时刻经过算法1处理后所发布的扰动位置为zt，用Pr(zt|s*t=si)表示发布扰动位置zt的概率大小，根据定义8中的K-机制，使用式（9）计算.

4.3 时序关联位置隐私发布算法

由于4.2节中所提的定制隐私策略位置扰动算法只能用于单一时刻的位置扰动，而在发布连续时刻的位置数据时，需要考虑时序关联的影响，即发布历史时刻的扰动位置对攻击者预测下一时刻真实位置的影响，图5展示了时序关联位置隐私发布的过程.

图5 时序关联位置隐私发布示意图

根据2.2节中描述的位置隐私攻击模型，攻击者掌握的背景知识包括用户的历史位置数据、用户初始位置的概率分布p1，在此基础上对攻击者的背景知识做最大假设，假设攻击者的背景知识还包括定制隐私策略位置扰动算法CPLP，在这样的情况下，攻击者先验知识（如时序关联域）的计算可以看作隐马尔可夫模型的推理问题（Inference Problem），即攻击者试图结合定制隐私策略位置扰动算法CPLP、当前时刻的马尔可夫模型和当前时刻之前的所有扰动输出推测出当前时刻的真实位置.为了抵御拥有强大背景知识的攻击者对用户位置的推测，本节设计了时序关联位置隐私发布算法TRLP，具体流程如算法2所示.

算法2时序关联位置隐私发布算法(TRLP)输入:隐私预算ε,时序关联隐私策略G,状态转移矩阵M,前一时刻后验概率p+t-1,当前时刻位置s*t输出:每一时刻经算法CPLP扰动后的位置1.p-t=p+t-1M 2.Ct←{si|p-t[i]＞0}3.GC t←G∧Ct 4.zt←CPLP(ε，GC t，s*t)5.根据式(1)计算p+t 6.TRLP(ε，GC t，M，p+t，s*t)//递归调用本算法

算法第1步计算当前时刻的先验概率，每一时刻的先验概率由前一时刻的后验概率与马尔可夫状态转移矩阵M相乘得来；第2步根据先验概率计算t时刻的时序关联域Ct，即攻击者根据历史发布的数据所推测出该时刻用户的所有可能位置集合，第3步将此时的时序关联域和用户的定制隐私策略求交集得到时序关联域隐私策略，第4步中将隐私预算、当前时刻的时序关联域隐私策略和当前时刻真实位置状态代入定制隐私策略位置扰动算法CPLP中，对此时的真实位置进行扰动得到zt，第5步中将扰动位置zt代入式（1）计算t时刻的后验概率p+t，最后在第6步中将时序关联域隐私策略、t时刻的后验概率和t+1时刻的真实位置代入本算法，即递归调用，实现下一时刻扰动位置的发布.该算法的输出为每一时刻经算法CPLP扰动后的位置（算法2中第4步）.

4.4 算法分析

本节分别从隐私安全性和时间复杂度两方面对所提算法进行理论分析.

4.4.1 算法隐私安全性分析

首先证明单一时刻定制隐私策略位置扰动算法CPLP满足{ε，G}-位置差分隐私，由于算法CPLP基于对攻击者能力的最大假设，因此证明算法CPLP满足{ε，G}-位置差分隐私即可保证该时刻所发布位置的隐私性.

定理1算法CPLP满足{ε，G}-位置差分隐私.

证明取∀si，sj∈NP(s)，对于同样的扰动输出z，其概率分布如下：

比较两个概率分布可得：

根据三角不等式，有：

因此可知对于时序关联域隐私策略中任意两个相邻的位置点，算法CPLP满足ε-不可区分性，根据引理1可知算法CPLP满足{ε，G}-位置差分隐私.

证毕.

其次，分析连续时刻位置隐私发布算法TRLP的隐私安全性.根据差分隐私的序列组合性［4］，记A1，…，AT为T个独立的随机化算法，分别表示每一时刻对真实位置的扰动处理，若分别A1，…，AT满足{ε，G}-位置差分隐私，则其组合{A1，…，AT}满足{Tε，G}-位置差分隐私，其中Tε表示所有时刻隐私预算的总和，即连续时刻的位置发布算法TRLP同样满足{ε，G}-位置差分隐私，因此根据连续时刻位置发布算法所得到的轨迹数据具有一定的隐私安全性.

4.4.2 算法时间复杂度分析

关于算法的时间复杂度，TRLP算法最耗时的地方在于计算每个时刻扰动输出的位置点z，即CPLP算法的输出，而在CPLP算法中，根据每个时刻的时序关联域计算凸包敏感度耗时最大，记凸包的顶点个数为n，时序关联域大小为h，则算法的时间复杂度表示为O(hlog(n)+n2log(h)).

5 实验与分析

5.1 实验数据与环境

本文所使用的实验平台操作系统为Windows 10+64位，开发环境为Pycharm，编程语言为Python 3.8，CPU为Intel（R）Core（TM）i5-7300HQ，内存为8 GB.实验采用两个数据集，分别是微软亚洲研究院的Geo-Life数据集［27］和斯坦福大学复杂网络分析平台公开的真实数据集Gowalla数据集［28］.GeoLife数据集记录了从2007年4月到2012年8月182个用户的轨迹数据，包含一系列以时间为序的包含经纬度、海拔等信息位置点信息，共计包含17621条轨迹.本文提取其中位于北京四环内的轨迹数据，将地图分割成340×340 m2的网格单元，用于马尔可夫状态转移矩阵M的训练.Gowalla数据集中包含196586名用户20个月内在6442890个位置上签到的数据，本文提取该数据集中所有位于洛杉矶的位置数据，将地图分割成370×370 m2的网格单元用于马尔可夫状态转移矩阵M的训练.

5.2 算法可用性度量指标

为了评估本文所提位置隐私发布算法TRLP的可用性，在实验中使用两个度量指标.第一个度量指标是原始位置和扰动位置之间的欧几里得距离Eeu，即原始位置和扰动位置之间的误差，单位为m，该指标是位置隐私发布算法中通用一个的度量指标，Eeu值越小，即误差越小，说明位置隐私发布算法的可用性越高.第二个度量指标是在位置数据集上运行k近邻查询的精度，分别在原始位置数据集和发布的扰动位置数据集上运行k近邻查询，假设在原始位置数据上运行近邻查询的结果为R，在扰动位置上运行k近邻查询结果为R'，则k近邻查询的精度P计算方式如下：k近邻查询是位置数据发布后常用的一种数据分析方法，其目的是查找距离用户最近的k个兴趣点，对于不同的位置扰动算法，k近邻查询的精度越高，说明经过位置隐私发布算法扰动后所得到的轨迹质量越高.

5.3 算法可用性实验

本节分别从两个方面探究所提时序关联位置隐私发布算法TRLP的可用性，一方面探究定制隐私策略的粒度和隐私预算对算法可用性的影响，另一方面探究发布时序位置数据时算法可用性的变化情况.

首先探究定制隐私策略的粒度和隐私预算ε对算法TRLP可用性的影响.在Geolife数据集上选择20个用户150个时刻下的位置进行隐私发布，构造不同粒度的隐私策略（PGk9，PGk16，PGk25），在这三种隐私策略上分别运行TRLP算法30次，以原始位置和扰动位置之间的欧几里得距离Eeu作为算法可用性的度量标准，在ε分别取值0.3，0.5，0.7，1时返回Eeu的平均值，实验结果如图6所示.

图6 定制隐私策略粒度对算法可用性影响

实验结果分析如下：

（1）随着隐私预算的增加，算法TRLP的误差逐渐减小，即可用性越高，说明算法TRLP的可用性随着隐私预算的增加而增强.

（2）在相同隐私预算的情况下，隐私策略的粒度越小，则算法TRLP的误差越小，即算法TRLP的可用性越高，说明可以通过调整隐私策略的粒度来调整算法TRLP中隐私保护程度与可用性之间的平衡.

（3）在不同隐私预算以及不同粒度的隐私策略下，算法TRLP的误差范围均在1 m内，说明算法TRLP具有较高的可用性.

其次探究算法TRLP发布连续位置数据时可用性的变化情况.分别在Geolife和Gowalla两个数据集上选择20个用户100个时刻的位置数据，设置隐私预算ε=0.5，基于三种粒度的隐私策略运行时序关联位置隐私发布算法TRLP，结果如图7所示.

图7 时序关联位置隐私发布

实验结果分析如下：

（1）在Geolife和Gowalla两个真实的位置数据集上运行时序关联位置隐私发布算法TRLP时，随着隐私策略粒度的减小，算法TRLP的误差也随之减小，即可用性逐渐增加.同样说明算法TRLP可以通过调整隐私策略的粒度来调整隐私保护程度与可用性之间的平衡.

（2）在Geolife和Gowalla两个真实的位置数据集上运行时序关联位置隐私发布算法TRLP时，在三种不同粒度的隐私策略下，连续时刻之间算法TRLP的误差值变化幅度较小，且所有时刻误差值均在1 m内，同样说明算法TRLP可用性较高.

（3）在三种不同粒度的隐私策略下，算法TRLP在Gowalla数据集上的误差Eeu均小于Geolife数据集上的误差Eeu，原因是与Geolife数据集相比，Gowalla数据集收集的用户数据具有明显的移动模式，所以训练的马尔可夫状态转移矩阵M的准确性更高，因此算法TRLP在Gowalla数据集上运行的可用性更高.

5.4 对比实验

本节以文献［24］中的拉普拉斯方法作为基线算法，采用不同的度量指标对算法TRLP与基线算法的可用性进行比较.两种算法主要的差别是计算敏感度的方式以及噪声添加的方式不同，算法TRLP通过定制隐私策略的方法计算敏感度并添加满足噪声，基线算法仅通过计算l1-敏感度给位置数据添加噪声.

首先以原始位置和扰动后位置之间的欧几里得距离Eeu作为度量指标，在Geolife数据集上选择20个用户150个时刻下的位置，基于隐私策略分别运行算法TRLP和基线算法，迭代次数为30次，ε分别取值0.3，0.5，0.7，1时，计算Eeu的平均值，实验结果如图8（a）所示.

其次以k近邻查询的精度P作为度量指标，在Geolife数据集上选择20个用户150个时刻下的位置，设置隐私预算ε=0.5，基于隐私策略PGk9分别运行算法TRLP和基线算法，迭代次数为30次，在扰动前后的位置数据集上运行k近邻查询，根据5.2中的描述计算k近邻查询的精度P.在k∈[50，75，100，125，150]的情况下运行k近邻查询时算法TRLP和基线算法的精度如图8（b）所示.

最后比较算法TRLP与基线算法的时效性，同样在Geolife数据集上选择20个用户150个时刻下的位置，基于隐私策略分别运行TRLP算法和基线算法，迭代次数为30次，返回不同隐私预算下两种算法针对单个时刻运行所需时间的平均值，ε分别取值0.3，0.5，0.7，1时，实验结果如图8（c）所示.

图8 TRLP算法与基线算法对比

实验结果分析如下：

（1）随着隐私预算的增加，算法TRLP和基线算法的误差均逐渐减小，说明算法TRLP和基线算法的可用性均随着隐私预算的增加而增加，然而在同样的隐私预算下，算法TRLP的误差Eeu小于基线算法，即算法的可用更高，说明算法TRLP计算敏感度和添加噪声的方式与基线算法相比冗余更少，即采用定制隐私策略进行敏感度的计算效果更好，因此算法TRLP可以在满足位置差分隐私的同时保证更好的可用性.

（2）基于不同的k值对两种位置隐私发布算法扰动后的轨迹数据进行k近邻查询时，算法TRLP的精度P均高于基线算法，因此将经过算法TRLP扰动后发布的轨迹数据用于k近邻查询时效果更好，说明经过算法TRLP扰动后发布的轨迹数据质量高于基线算法扰动后所发布的轨迹数据质量.

（3）在不同的隐私预算下，算法TRLP和基线算法针对单个时刻位置进行隐私发布所需要的时间都在2毫秒内，说明两种算法都具有一定的实时性，但与基线算法相比，算法TRLP的运行时间较长，因为算法TRLP计算敏感度时需要根据每个时刻的时序关联域计算凸包敏感度，这一步耗时较大.

6 结束语

本文提出了一种基于本地化差分隐私的时序位置发布模型，模型采用了灵活的位置隐私保护方案，即由用户选择系统已设定的多种隐私策略或定制隐私策略，在此基础上设计了定制隐私策略位置扰动算法（CPLP），同时提出一种基于定制隐私策略的时序位置发布算法（TRLP），通过保证用户发布位置的不可区分性从而保证用户的位置隐私.在两个真实的位置数据集上进行实验，验证了与基线相比，算法TRLP具有较好的可用性.今后的研究将考虑如下两个方面：（1）与基线算法相比，算法TRLP的运行时间较长，因此后续工作中需要研究如何在保证算法TRLP可用性的前提下提高其运行速度，从而将算法TRLP扩展到实时位置服务中；（2）在设计定制隐私策略时没有考虑用户不同的移动模式（如交通方式），因此在后续工作中可以将用户的移动模式引入定制隐私策略的设计，根据用户不同移动模式为用户提供更细粒度的隐私保护选择.