基于轨迹聚类的连续查询隐私保护方法

吕 鑫，赵连成，余记远，谭 彬，曾 涛，陈 娟

1.河海大学 计算机与信息学院，南京210098

2.华能澜沧江水电股份有限公司，昆明650214

随着网络技术的飞速发展和智能移动终端的全面普及，各类智能应用已经深入到人们的日常生活中，其中基于位置的智能应用服务是最常用的一类服务。基于位置的服务（Location Based Service，LBS）是指用户基于自身的地理位置发起一种服务请求，服务提供商返回给用户与位置息息相关的服务。典型的LBS 应用[1-3]包括地图类应用、兴趣点检索、GPS 导航和位置感知社交网络等，极大地提高了人们的生活质量。然而，人们在享受LBS服务带来便利的同时，也存在着隐私泄露的风险。用户在请求位置服务过程中通常需要提供一些与自身相关的信息，例如：身份信息、个人空间位置、查询时间、查询内容等信息。攻击者可能会搜集用户的请求数据和历史位置数据等敏感信息，根据这些信息和关联规则推断出用户的活动范围，进一步推测出生活习惯、家庭住址、接触人群等详细的隐私信息，对用户财产安全造成危害。

隐私问题是阻碍LBS进一步发展的主要障碍之一，用户期望在保护自身信息安全的同时，享受优质的位置服务。当前，因位置隐私泄露导致用户财产受到损失的事件时有发生，位置隐私保护技术越发重要。为解决攻击者易利用查询与位置间关联概率发起攻击的问题，Zhang 等人[4]基于差分隐私的概念，提出了一种概率不可区分的安全机制，进而设计了一种位置转换方案用以混淆查询与发起位置间的关联，并通过理论分析与实验验证了所提方法的性能。王嘉慧等人[5]提出的网格扩增法，以网格边缘的形式自底向上地快速扩建匿名区，在保证查询结果正确性的同时，减少了查询处理的成本。为了防止访问者试图获取被访问者不希望泄露的隐私信息，张伊璇等人[6]建立了一个隐私保护模型，该模型计算访问者进行善意访问的概率，与隐私信息拥有者的容忍程度相比较，再决定是否通过访问者的访问请求。

以上方法是针对用户单次查询场景下的隐私保护问题。然而在连续查询场景下，攻击者可以根据连续查询过程中匿名集合的变化，从而判断出用户的真实位置。如图1 所示，在首次与第二次查询中，匿名集合都包含了用户A和用户D，可推断出真实用户为用户A或用户D；在第二次与第三次查询中，匿名集合都包含用户A和用户H，可推断出真实用户为用户A或用户H；综合三次查询，即可判断出用户A 为真实查询用户，并得到用户A的移动轨迹。除此之外，攻击者还可以利用时空相关性确定匿名区域的范围，从而缩小用户真实位置的所在区域。因此，针对快照LBS的经典匿名方法不能直接应用于连续LBS 的用户轨迹隐私保护。Chen 等人[7]对单次快照位置查询的k 匿名方法进行了扩展，将初始的匿名区域扩展到所有连续查询中包含相同的k个用户的区域，以保证k 个用户在不同方向上的移动，增加了匿名区域的混淆度。Zhang等人[8]提出了一种不确定连续协作用户发现算法，该方法利用网格区域的不确定性单元和协作用户隐藏查询用户身份，且所有查询结果均由协作用户提供，查询方无需与LBS服务器进行交互，从而实现了良好的隐私保护效果。Peng等人[9]提出由用户在不同时间不同地点，发布乱序假查询，使得连续位置是乱序的，攻击者难以排序识别正确的轨迹，提高了用户轨迹隐私的安全性。Zhang等人[10]基于Markov预测，提出了一种匿名位置预测方案。该方案同时考虑了查询概率匿名性与匿名位置可链接性，解决了已有方法在连续匿名场景下查询概率匿名难以链接的问题，因此该方案可有效抵御统计攻击与推断攻击。此外，王斌等人[11]提出了一种ε-敏感程度不可区分的隐私保护方法，以解决用户移动过程中的敏感程度渐进导致隐私泄露的问题。该方法基于差分隐私理论并结合Voronoi图划分，通过添加噪声数据以满足ε-敏感程度不可区分，并进一步优化了噪声添加数量，在有效抵御利用敏感程度渐进发起的攻击的同时，保证了服务质量。

另外，在LBS 连续查询场景下，用户的属性信息也易于被攻击者获取进而被用于分析推断用户的真实位置甚至轨迹，针对此，Zhang等人[12]提出了基于粒子群优化算法（PSO）的属性泛化隐私保护方案。该方案利用PSO算法的特性提升了泛化过程的效率。另外，Zhang等人[13]还基于CP-ABE 方法提出了一种新型属性匿名方案，以抵御推断攻击并解决第三方服务器不可信的问题。进一步地，在属性泛化的基础上，王斌等人[14]利用同态加密实现了秘态属性泛化，解决了已有方法可被攻击者利用属性进行追踪的问题，同时秘态处理过程进一步保护了用户的隐私。

分析了以上方法可以看出现有的连续查询位置隐私保护方法，存在构建的匿名区域过大、用户等待时间较长等缺点。因此，连续查询隐私保护方法仍具有研究价值，且应重点考虑多用户节点的广播与响应，协作匿名区的合理，查询位置的干扰，保障连续场景下的用户轨迹隐私安全。针对以上问题，本文提出基于时空聚类的连续查询隐私保护方法。该方法支持近邻缓存的用户之间的协作，发布假查询模糊用户的真实轨迹，通过使用聚类生成的兴趣区，进行假查询来扰乱真实轨迹点，最后使用混淆度来衡量该算法的扰乱程度。

1 相关知识

1.1 LBS下的隐私保护技术

假位置和k 匿名技术是LBS 下经典的隐私保护技术，本文算法也是在上述两种技术的基础上进一步进行了研究，下面对这两种隐私技术做相关介绍。

图1 LBS场景下的连续查询过程

假位置技术是干扰技术中常用的一类技术，是指用户选择或生成一系列虚假位置，干扰用户的真实位置后，发起位置服务请求。假位置技术对于虚假位置的产生，可根据假位置数量，分为锚点位置和虚假地址集。锚点的定义是像一个迅速定位器的标记。锚点位置是与用户真实位置有着一定距离的位置点，既可能是真实存在的用户位置点也可能是区域上任意位置点。用户在发起查询请求时，选择锚点位置代替自己真实的地理位置，当用户接收到LBS服务器返回查询结果集之后再通过自身与锚点位置的距离，进行求精筛选得到最佳的查询结果。

k 匿名是泛化技术中典型技术之一。2003年，学者Gruteser M等[15]提出将k 匿名应用到位置隐私的概念，将用户位置泛化成区域，且区域中包含k 个位置，用户位置与其他k-1 个邻近用户位置不可区分，称为位置k匿名。用户发起位置服务的时候，会泛化一片区域代替用户真实位置，区域满足k 匿名后，发送位置服务提供商，提供商返回结果集，用户再筛选最合适的结果。

1.2 LBS下的位置隐私攻击类型

在LBS场景下，伪装用户攻击和区域中心攻击都是攻击者常使用的攻击类型。本文算法也考虑了攻击者使用上述攻击方式来获取位置隐私的情况，下面对这两种攻击做相关介绍。

伪装用户攻击主要是指在用户匿名区域中，攻击者可伪装成除用户外的其他k-1 个用户，导致匿名效果降低。伪装用户的数量越多越不利于查询用户的位置隐私安全。当用户移动到这样的匿名区域时，用户的真实位置就很有可能被攻击者获取。针对用户协作式的匿名方案，此类攻击更具有威胁性。

区域中心攻击是指攻击者可以通过某一种方式，获取用户的匿名区域范围，并针对匿名区域的中心点位置发起攻击，不断扩大攻击范围，来推断用户的真实位置。如图2 所示，用户在通信时，由于通信方向的不固定，用户易处于区域中心附近。攻击者不断在中心位置进行范围攻击，覆盖多次出现的通信用户，再结合其他知识背景，从而推断出用户的位置点及轨迹。

图2 区域中心攻击示意

2 基于轨迹聚类的连续查询隐私保护方法

2.1 基本思路

基于轨迹聚类的连续查询隐私保护方法以用户兴趣区作为混淆查询区域（Fake Query Track Based on Users"Interest Region，FQTIR）并在移动过程中形成轨迹聚类，用户从多跳对等近邻点收集有用信息，并发出假查询来扰乱攻击者。在用户移动过程中，假查询区域的选择有着很重要的作用，若假位置区域距离用户过近，达不到保护效果；假位置区域距离用户过远，容易被攻击者识别。本文采用了密度聚类算法，考虑轨迹中时间和空间两个因素，通过对多个用户的位置进行密度聚类，生成一定时间段内访问频率较高的区域（即兴趣区，Region of Interest，ROI），进而在移动过程中形成轨迹聚类，由此提出一种基于轨迹聚类的连续查询隐私保护方法。通过这种方式，将用户的真实位置区域转换为虚假的匿名区域，打破提交的连续匿名区域的相关性。

2.2 定义

本文邻居节点的选择范围由用户密度决定，用户密度由跳数、匿名区域内的用户数等参数决定。每个用户可以指定参数来满足隐私需求，可以在任何时间更改隐私配置文件Hmax的设置。下面对整个区域的平均用户密度、参与协作的用户密度、隐私配置文件Hmax进行定义和介绍。

定义1 对于一个区域中用户分布数D，以每一次广播的响应用户数Di作为样本，任意两个用户通过单跳或多跳通信可达，整个区域的平均用户密度d 为：

定义2 C 为用户间通信可达的区域，用户u ∈C，u 的h 领域定义为：

定义3 对用户u ∈C，du的初始值为用户u 的1跳邻域范围响应用户数。nu是D( u,1) 内用户有效密度的个数。用户u 计算并更新du公式为：

定义4 最大可容忍跳数值Hmax，用户覆盖越广，响应的时间延迟随着跳数值的增加而增加，过大的时间延迟将造成严重的通信成本。

定义5 用户兴趣区指一个或多个用户在一定时间段内访问频率较高的一定区域。

定义6 哑元区域指一个或多个用户在一定时间段内所有可以作为假位置的点的集合。

定义7 时间阈值Ts，聚类半径为Rsp，Eps 是ε 邻域的最大半径，本文设置Eps=Rsp，假设样本集D=( x1,x2,…,xm)，

ε 邻域：对于xj∈D ，其ε 邻域包含样本集D 中与xj的距离不大于ε 的子样本集，即Ns( xj)={xj∈D|distance( xi,xj)≤ε} ，这个子样本集的个数记为|Ns( xj)|。

核心对象：对于任一样本xj∈D，如果其ε 邻域对应的Ns( xj)至少包含MinPts 个样本，即| Ns( xj)|≥MinPts，则xj是核心对象。

定义8 混淆度用来衡量算法的隐私保护程度，其表示为用户在一段移动过程中发出虚假查询次数与用户发出总查询的次数比值。计算公式为：

2.3 方法的提出

移动用户与有限跳数内的邻居通信并共享有效信息，当用户拥有了共享信息数据后，可以生成一个匿名区域，模糊自身的当前位置，再向位置服务提供商发起查询。当移动到下一个位置时，本地搜索有效信息数据，检查该位置是否包含在收集的ASR（Anonymizing Spatial Region，匿名空间区域）中。若当前位置包含在收集的ASR 中时，用户则选择该位置点对应的兴趣区发起混淆查询；若不包含在收集的ASR 中，用户将重新与多跳邻居通信并共享有效信息，再进行上述匿名过程，实现轨迹聚类以达到对轨迹隐私的保护。结合具体示例（图3）来阐述本文所提的方法步骤。

图3 基于用户兴趣区的假查询轨迹

轨迹上的红星( L1～L6)表示用户u 的足迹，黑色实心圆点表示其他用户的位置。圆圈表示近邻点与用户u 共享所请求的匿名区域，圆圈内的点表示相应的匿名集。蓝色矩形框( R1～R6)表示用户发出假查询的哑元区域。以下为结合图3示例的方法过程：

（1）协作请求。用户在初始位置L1时，从近邻点收集信息，u 首先广播请求响应，1 hop 近邻用户a、b、c、d收到u 的请求，并与u 共享有效信息，包括兴趣点，k 匿名区域，同样扩展至2 hop 近邻用户。

（2）服务结果查询。当用户移动到L2时，检查L2是否包含在收集的ASR 中，若发现L2处于hop 数为2的用户g 接收到的ASR 区域，则从g 接收到的存储记录中获取其LBS 需求的服务数据，并执行步骤（3）发起假查询。若未从存储记录中查到对应结果，则向位置服务商发起查询请求，并返回结果。用户移动到L3、L4、L5、L6时，执行步骤与L2类似。

（3）假查询。用户在位置L2时，根据DBSCANIR提取的兴趣区，选择L2对应的兴趣区R2，在哑元区域内选择合适的假位置发出查询请求。

（4）邻近用户信息更新。当邻近用户的缓存信息超过有效时间期限或邻近用户变化量达到阈值，则执行步骤（1）重新发起协作请求。

当用户当前位置包含在共享的数据信息中，用户可以在本地搜索ROI。通过虚假的ASR( R2,R3,R5,R6)进行位置查询，满足了每个快照查询的用户k 匿名要求，并且通过模糊技术，阻止了攻击者重建用户的轨迹，保护了用户的轨迹隐私。

在上述方法过程中，为减少通信成本，针对该邻近用户共享信息的存储问题，设计了一种基于缓存机制的位置查询算法；用户位置在变化的同时，匿名区域也随之变化，为保证用户共享信息的有效性，设计了一种基于近邻区域用户密度的位置更新；为提高混淆度，假查询应位于位置查询频率较高的区域，针对用户兴趣区的提取问题，设计了一种基于密度聚类的兴趣区提取算法。

2.3.1 基于缓存机制的位置查询算法

用户指定近邻用户个数k ，k 越大，组建的用户群越广，用户获得直接查询结果可能性越高。缓存数据包括查询兴趣点、位置标识、查询历史信息、近邻区域用户密度。首先用户取得个人位置点t ，发出查询，并且设置广播跳数h。当近邻用户接收响应消息，将查询消息内容与缓存历史信息做置换对比，当缓存内容满足查询需求时，不再继续构建用户组。查询需求不满足的情况下，继续组建近邻用户组；接收到响应消息的近邻用户，更新集合P，将新发现的近邻用户存入。比较k 和集合P 中用户个数，当k 小于集合P 用户个数，协作用户数达到满足要求。否则增加h，发现更多协作用户。在用户组中选择代理用户，向服务器发送查询请求，完成查询过程。具体步骤如下：

（1）用户请求。用户设置跳数h，将已发现的近邻用户置于集合P 。然后广播近邻用户发现消息，等待近邻用户响应。更新接收到响应消息的用户集合，比较k 和集合P 的用户个数n。若集合中用户个数小于k，则需要增加h 值，直到达到Hmax值。通过广播用户发现获得更多的近邻用户。近邻用户接收到响应消息后，更新已发现用户集合P。最后将多次更新后的已发现用户集合P 发送给请求用户。

（2）用户响应缓存。用户发出查询消息，消息内容为查询请求m 和广播跳数h 为1，将消息m 与集合P中广播跳数h 为1 的所有近邻用户的缓存信息中内容做比较，如果缓存内容满足查询，则即刻将缓存内容发送给请求用户，结束算法过程。否则增加广播跳数h，继续比较。接收到查询内容的近邻用户，检查h 值，如果h 大于1，说明接收到的消息需要多跳广播，近邻用户将h 减1后，继续广播。等待近邻用户的比较结果。

算法1 基于缓存机制的位置查询算法

输入：查询用户u，隐私需求k，跳数h，最大可容忍跳数值Hmax，响应用户数du，代理用户Ua，用户个数n。

输出：邻近用户集合P，单次查询结果SQR。

1.UserRequestCache(u,k,h,Hmax,du)

2.h=1，P ←∅，

3.while h ≤Hmaxdo

4.broadcast request to peers with h，du

5.P ←P ⋃{the received cachedData，h} //收集响应的协作用户数据

6.if k ＜n then

7.AnonySet ←u ⋃（k-1 nearest）//更新匿名集合

8.else

9.h=h+1

10.end if

11.end while

12.return P

13.end

14.UserResponseCache（message，P） //查询邻近用户缓存

15.while（message-request hit cached information）//近邻缓存信息命中查询请求，返回查询结果

16.return SQR

17.end while

18.end

19.UserAgentQuery(u,h) //代理用户发起查询

20.if h ≤1

21.Ua←u //由代理用户发起查询

22.else if h ＞1

23.h ←h-1

24.forward message to the next hop user

25.endif

26.return SQR

27.end

2.3.2 基于近邻区域用户密度的位置更新算法

用户进行初始化查询前，设置周期，用作定期更新近邻区域的用户密度参数。新用户加入现有的集合，或者现有用户的离开时，更新近邻用户的位置集合Q 。计算各自用户的密度，更新跳数范围内的du。通过周期性更新和分享位置能够保证查询用户周围的变动，避免发送多次响应消息造成通信开销。位置更新过程的伪代码如下：

算法2 基于近邻区域用户密度的位置更新算法

输入：相邻用户位置AUL，位置更新信息LUM ，邻近用户位置集合Q。

输出：响应用户数du，位置更新集合LUL。

1.LocationUpdate(AUL,LUM)

2.set the initial value，user location，update cycle t

3.initial proximity parameter list is empty

4.while t

5.if（new users join，existing users leave）

6.generate and send the location-update //当有新用户加入或离开更新位置列表

7.end if

8.return LUL

9.put LUM in Q

11.di←d //赋值用户有效密度

12.update AUL，change di

13.if parameter list change，update du

15.end if

16.return du

17.end while

18.end

在计算完近邻用户密度，以用户密集区域优先划分十字区域，作为用户提高协作效率的遍历区域。在用户从近邻范围内发起协作请求时，首先将协作范围按一定的结构存储，便于用户构建匿名区域。如图4 所示，字母表示区域编号，生成一个满四叉树，树中每个用户代表划分的区域，根部用户表示最大平面区域；用户位置和用户所在区域相对应。将平面空间区域视为一个正方形，十字递归分割直到分割成的每个正方形空间的a小于一个给定阈值。首先，生成满四叉树，避免在用户位置区域插入时需要重新分配内存，加快插入速度。然后插入用户位置区域到叶子用户中并将空的用户所占内存空间释放掉。将用户位置信息存储在完全包含它的最小矩形用户中，不存储在它的父用户节点中，每个用户位置区域只在树中存储一次，避免存储空间的浪费。若区域内存在多个子用户，即代表该区域内部可以划分的更小区域。表1为图4中各用户所对应区域位置统计表。

图4 用户位置与所在区域

表1 各区域用户分布

2.3.3 基于密度聚类的兴趣区提取算法

兴趣区指一个或多个用户在一定时间段内访问频率较高的一定区域。以轨迹中所有运动点的列表为样本，首先确定样本的邻域，将首个样本运动点加入核心对象的集合中，通过邻域参数( )Eps,MinPts 确定核心对象的邻域。然后在未访问的样本集合中，取下一个核心对象，重复确定邻域的过程，最后标记这些样本的类别，合并生成类别簇。伪代码如下：

算法3 基于密度聚类的兴趣区提取算法

输入：运动点集合M ，聚类邻域最大半径Eps，最小邻居节点数MinPts，用户所在节点P。

输出：类别簇列表clusterList。

1.DBSCANIR(M,Eps,MinPts)

2.mark all points in M as unclassified

3.clusterList ←empty list //建立类别簇列表

4.for each unclassified point P in M

5.mark P as classified

6.neighborPts←QueryNeighborPoints(M,P,Eps,MinPts)//查询到邻居节点赋值给邻居节点集合

7.if neighborPts is not NULL then

8.clusterList add neighborPts

9.for each cluster C in clusterList

10.for each cluster C′ in clusterList

11.if C and C′ are different clusters then

12.if MergeClusters( C ,C′ )is TRUE then

13.clusterList remove C′

14.return clusterList

15.QueryNeighborPoints(M,P,Eps,MinPts) //查询邻居节点

16.cluster ←empty list

17.for each point Q in data

18.if distance( P,Q )＜eps then

19.cluster add Q

20.if cluster.size ＞MinPts then

21.mark P as core points

22.return cluster

23.return NULL

24.MergeClusters（cluster A，cluster B）//合并聚类簇

25.merge ←false

26.for each point Q in B

27.if point Q is core point and A contains Q then

28.merge ←true

29.for each points Q′ in B

30.A add Q′

31.break

32.return merge

基于上述的三个算法和方法具体步骤，用户使用列表存储自身的历史信息或保存从其他邻居点接收到的共享数据。为保证缓存信息的有效性，当ASR 生成时，分配一个时间戳T ，时间戳和当前系统之间的间隔决定了存储数据的过期时间t 。同时，周期性地更新邻近用户的位置集合Q，来保证集合Q 中所有的邻近用户处于可响应状态。当用户在新位置发起查询时，首先遍历ASR 中是否有查询结果，若有则反馈给用户，并在多个兴趣区中，选择当前位置的对应区域发出假查询；若缓存是空的，或者兴趣区不存在，则发起协作广播构建ASR，使得LBS查询符合k 匿名，以保护隐私。伪代码如下：

算法4 基于轨迹聚类的连续查询隐私保护方法

输入：缓存信息列表List，兴趣区ROI 。

输出：queryResult。

1.QueryResult(List,ROI)

2.if Find (List,ROI) then

3.ROI ←getROI(List,ROI)

4.if Num of fake ASR ≠0 then

5.ASR ←Choose an ASR in ROI //在兴趣区中选择一个区域发出假查询

6.send Fake Query(ASR)

7.else if

8.establish an ASR by using SingleQuery //使用快照查询位置算法构建匿名区域

9.send a live query

10.end if

11.else

12.establish an ASR by using SingleQuery //使用快照查询位置算法构建匿名区域

13.send Query(ASR)

14.end if

15.end

3 实验分析

实验采用Java 语言作为编程语言，运行环境为Window 7操作系统，Intel Core i5-2405M四核处理器，6 GB 内存。分别使用真实数据集、Oldenburg 模拟数据集[16]和Geolife 数据集[17]对算法FQTIR 进行实验。在混淆度、平均处理时间、平均通信消息量三个方面与Peng等人[9]提出的CTPP（Collaborative Trajectory Privacy-Preserving Scheme）算法和仅实现k 匿名的连续快照协作算法（Baseline）[9]进行对比分析。

在取样真实数据集时，若按照实际数据中每0.5 秒采样，用户位置点十分密集，每一个后续位置点都必然存在查询用户的已有区域数据中，导致实验中的混淆度指标无法区分。因此对真实数据集按照每30秒轨迹点取样进行实验。实验场景是移动用户在道路上进行移动，每个移动用户的传输范围定义为100～300 m。k 匿名需求设定为3到15，连续通信广播跳数h 从1到7，用户数从2 000到5 000。实验参数范围和默认值如表2所示。

表2 实验参数

3.1 混淆度

通过发出虚假查询来模糊用户轨迹，虚假查询的数量越多，暴露给服务器的隐私信息越少，攻击者重构轨迹的可能性就越低。通过混淆度η 评估隐私保护效果。

在取真实数据集时，为保证数据取样合理，因此取了多组数据，15秒为一组，30秒为一组，60秒为一组，进行验证。最后选定每30秒轨迹点取样组，效果最佳。

在图5中，用户查询次数越多混淆度也会越高。随着k 值的增加，η 随之增大。图6中，FQTIR算法在真实数据的整体运行效果比在Oldenburg数据集上运行效果稍差，混淆度略高。因为北京市的路网类似棋盘状的布局，用户分布比较均匀，没有特别的密集区域，用户需要更多的多跳通信满足k 匿名要求，从而使得轨迹被区域覆盖的概率增大。而Oldenburg数据会形成特定的密集和稀疏区域，因此利于用户协作。

图5 不同查询次数的混淆度对比

图6 不同数据集的混淆度对比

假设用户发出了5 次假查询，图7 为5 次假查询区域的选择过程。图7的最后一张子图是5次假查询区域的结合，可以看出用户的片段轨迹是完全可以被假查询区域覆盖，用户的隐私存在威胁。

图8 为FQTIR 算法的5 次假查询区域，算法通过多个用户不同时间段的轨迹聚类生成多片用户兴趣区域，假查询区域不会过度集中，且与用户轨迹位置无直接性关系，因此用户轨迹点不容易被攻击者识别出来。

图7 CTPP假查询区域

图8 FQTIR假查询区域

与CTPP 进行混淆度（即虚假查询次数与总查询的次数比值）对比，两种算法都进行了5 次假查询，但是FQTIR的假查询区域相对分散，隐私保护效果更好。

3.2 平均处理时间

在实验中时间周期是指从用户构建匿名区域的时刻到用户收到LBS兴趣点的时刻。

在图9和图10中，算法处理时间与混淆度η 值成反比，与CTPP相比，FQTIR平均处理时间相对较少。图11中，Baseline算法的平均处理时间最多，FQTIR算法平均处理时间最少。图12中，FQTIR分别在Oldenburg数据集和Geolife 数据集上的平均处理时间的变化趋势，基本保持稳定。

图9 混淆度为0.5的算法处理时间对比

图10 混淆度为0.7的算法处理时间对比

混淆度值η 越大，表示用户发出假查询的数量越大，则用户可以更多地通过搜索本地缓存的数据，而不是向服务提供商发送请求，因此查询位置的平均处理时间越少。与CTPP 相比，由于FQTIR 在处理假查询时，是在判断用户位置点是否在已有区域同时，就获取了服务数据，然后提交当前对应的聚类区域。数据已按四叉树结构存储完毕。而CTPP需要按广播通信顺序依次判断，且每次遍历均需要返回查询用户，再去选择距离用户所在区域较远的区域。因此FQTIR的平均处理时间较少。

图11 算法间处理时间对比

图12 针对两个数据集的算法处理时间对比

由于Geolife数据集是按时刻0.5秒采样，无法计算混淆度，因此对数据集的数据取样时间上扩大了粒度。处理后的数据集中的位置点不再聚集，搜寻邻居点时，造成处理时间有一定变化。

3.3 平均通信消息量

移动用户的通信成本主要由邻近节点广播协作的消息量成本和向位置服务商查询的消息量成本两部分组成。因为如果用户需要执行多次广播请求响应，总体的通信成本就会增加。

在图13和图14中，随着匿名级别的提高，用户需要向邻居点广播更多的消息，接收更多的响应，所以随着k 值的增大，消息数量也随之增加。如图15所示，FQTIR算法的平均通信消息数量略大于CTPP算法的平均通信消息量。然而在k 值等于7时，FQTIR算法第一次执行，需要执行DBSCANIR 算法完成兴趣区的提取，因此通信消息量明显较高。兴趣区提取完成后，短时间内不用再重复执行DBSCANIR算法，随着k 值的增大，消息数量也增加，但增幅就不再增大。因此，FQTIR算法在保护轨迹隐私方面是可以以较小的通信成本取得更好的效果。Baseline算法需要很多的时间进行广播寻找以及等待邻居点的响应，不计算混淆度，确定匿名区域后，发送假查询。因此，Baseline 算法的平均通信消息量是最少的，但广播与响应时间较长。如图16所示，在真实数据集上，FQTIR 算法分别在Oldenburg 数据集和Geolife 数据集上的平均通信消息量并没有很大的变动，具有较好的普适性。

真实数据集因是连续时间的轨迹点，用户广播与响应都是在很小范围即可完成，所以在与邻居点通信过程中，FQTIR算法消息量是较小的。因此说明在真实移动过程中FQTIR算法是有效的。

图13 混淆度为0.5的算法通信消息量对比

图14 混淆度为0.7的算法通信消息量对比

图15 算法间通信消息量对比

图16 针对两个数据集的算法通信消息量对比

4 结束语

在连续位置查询场景下，本文针对分布式协作方法的查询请求存在重复性且轨迹易被重构的问题，提出了一种基于轨迹聚类的连续查询隐私保护方法。在该方法中，用户缓存了邻近节点共享的位置数据，选取合适的混淆区域代替用户真实位置所在区域发出假查询，将多个时间段的轨迹聚类区域作为假区域，破坏了连续查询的时空相关性，在达到位置隐私需求的同时，降低了查询的时间成本。