本发明公开了一种基于轨迹预测的隐私保护方法，主要解决现有技术中用户隐私泄露问题。其方案是：查询发起者对查询区域分类、发出协作建群请求；收到该请求的其他用户回复信息给查询发起者；查询发起者根据当前查询次数和隐私保护需求，对回复信息进行筛选、预测，并利用位置出入度和轨迹筛选算法对预测位置进行筛选，将可用预测位置和自己信息形成一个聚集查询集合或最终聚集查询集合发给位置服务器；位置服务器收到该信息后，查找数据库，形成候选结果集返回给各协作用户；各协作用户筛选所需查询结果，并存储于其缓存器。本发明采用运动趋势预测、轨迹筛选算法，在抵御位置关联攻击的同时，更有效抵御轨迹攻击，可用于各种连续查询位置服务中。
(1)建立一个由若干移动用户和位置服务器构成的隐私保护框架；
(2)由手机生产厂商为每部手机安装一个缓存装置，用于用户在查询过程中对有用信息的存储；
(3)查询发起者根据通信距离长短、人口密度大小和时间段的不同，将整个查询大区域划分为当前流行区域CP和当前普通区域CO；
(4)查询发起者发出协作请求，并将其广播给通信范围之内的其他用户；
(5)收到该协作请求信息的用户，将自己当前区域类型与查询发起者的进行对比：
若当前区域类型与查询发起者的区域类型一致或者他们所在区域的中心位置坐标之间的距离在阈值τ∈[0,50]的范围内，则同意该协作建群请求，并将自己的相关信息发送给查询发起者；
否则，拒绝该协作建群请求，且不发送自己的任何信息给查询发起者；
(6)当查询发起者收到至少k-1个用户的回复信息时，查询发起者再利用FFLQ算法对回复信息中的位置信息和查询内容进行筛选，与满足条件的k-1个用户建立协作关系，并获得k-1个协作用户的信息，k∈[4,14]；
(7)查询发起者将这k-1个协作用户的信息和自己的真实查询信息一起进行整理，形成聚集查询集合AQ；
(8)查询发起者根据当前协作请求次数的不同，对聚集查询集合AQ进行相应的处理：
若协作请求次数为1，则查询发起者直接将形成的聚集查询集合AQ发送给位置服务器LBS-S，执行步骤(13)；
否则，查询发起者舍弃该聚集查询集合AQ，并利用CVCG算法判断其自身与k-1个协作用户建立的用户协作群是否依然有效；若有效，则执行步骤(9)，若无效，则跳转到步骤(12)；
(9)查询发起者根据自己上一时刻和当前时刻时间段内的路程、上一时刻的运动趋势和当前时刻的具体查询内容对各协作用户当前时刻的位置信息和查询内容进行预测；
(10)查询发起者根据位置点出/入度的个数，对预测的位置信息进行第一次筛选，保留满足条件的预测信息，舍弃不满足条件的预测信息；按如下步骤进行：
10a)查询发起者从预测聚集查询集合AQSBP中任选各个协作用户的预测信息，并将所选的预测信息和自己的当前时刻信息一起存入到一个预测信息集合PS中：其中IDi表示第i个协作用户最终的身份信息；IDU表示查询发起者U最终的身份信息；
(xpgi,ypgi)表示第i个协作用户第g个预测位置，且1≤g≤m，m≥3；qcpi表示第i个协作用户当前时刻预测的具体查询内容；qcLi表示第i个协作用户上一时刻的具体查询内容；(xcU,ycU)表示查询发起者U当前时刻的真实位置；qccU表示查询发起者U当前时刻的真实具体查询内容；
10b)将查询发起者整理的上一时刻聚集查询集合AQL和上一时刻最终聚集查询集合FAQL分别表示如下：其中(xLi,yLi)表示第i个协作用户上一时刻的位置；(xLU,yLU)表示查询发起者U上一时刻的位置；(xLNt,yLNt)表示上一时刻新加入第t个协作用户的位置；QCLi表示第i个协作用户上一时刻的查询分类；QCLU表示查询发起者U上一时刻的查询分类；qcLU表示查询发起者U上Nt一时刻的具体查询内容；QCL 表示上一时刻新加入的第t个协作用户上一时刻查询分类；
qcLNt表示上一时刻新加入第t个协作用户上一时刻具体查询内容，且t≥1；
10c)查询发起者根据整理的预测信息集合PS、上一时刻聚集查询集合AQL和上一时刻最终聚集查询集合FAQL的信息，分别计算上一时刻聚集查询集合AQL或上一时刻最终聚集查询集合FAQL中满足位置出度要求的预测位置点个数P和预测信息集合PS中满足位置入度要求的预测位置点个数Q：对于上一时刻聚集查询集合AQL或上一时刻最终聚集查询集合FAQL中的每一个位置点，查询发起者都需要计算该位置点与预测信息集合PS中k个位置点间的距离{DLp1,DLp2,...,DLpi,...,DLpk}，且每一次当这k个距离中有不少于k/2个包含在查询发起者设定的距离范围scU±ε，ε∈[5,10]米内时，P的值就增加1，其中DLpi表示上一时刻聚集查询集合AQL或上一时刻最终聚集查询集合FAQL中的任一位置点与预测信息集合PS中的第i个位置点间的距离；
对于预测信息集合PS中的每一个位置点，查询发起者都需要计算该位置点与上一时刻聚集查询集合AQL或上一时刻最终聚集查询集合FAQL中的k个位置点间的距离{DpL1,DpL2,...,DpLi,...,DpLk},且每一次当这k个距离中有不少于k/2个包含在查询发起者设定的距离范围scU±ε，ε∈[5,10]米内时，Q的值就增加1，其中DpLi表示预测信息集合PS中的任一位置点与上一时刻聚集查询集合AQL或上一时刻最终聚集查询集合FAQL中第i个位置点间的距离；
10d)查询发起者根据P和Q的取值，对预测的信息进行相应的处理：
若同时满足P≥k/2和Q≥k/2，则保留该预测信息，并将该预测信息存入一个第一次位置筛选集合FLFS中，即：其中(xpwi,ypwi)表示第i个协作用户第w个预测位置，且1≤w≤m，m≥3；
否则，忽略该预测信息，再在聚集查询集合AQSBP中重新选则其他不同的预测信息，并根据位置点的出/入度个数要求，对新选择的预测位置信息进行第一次筛选；
(11)查询发起者根据其上一时刻和当前时刻的运动方向夹角，对步骤(10)中筛选出的预测位置点进行第二次筛选，并和相应的预测查询内容、自己的信息一起形成一个最终聚集查询集合FAQ发送给位置服务器LBS-S，执行步骤(13)；对第一次筛选出的预测位置点进行第二次筛选，按如下步骤进行：(11a)查询发起者在第一次位置筛选集合FLFS中任意选择各个协作用户的一个预测位置点，并和自己的信息存入一个候选位置点集合CLS中，即IDi表示第i个协作用户的最终身份信息；(xpvi,ypvi)表示第i个协作用户第v个预测位置，且
1≤v≤w；IDU表示查询发起者U的最终身份信息；(xcU,ycU)表示查询发起者U当前时刻的位置i i信息；qcL 表示第i个协作用户上一时刻的具体查询内容；qcp表示第i个协作用户预测的具体查询内容；qccU表示查询发起者U当前时刻的具体查询内容；
(11b)查询发起者整理的上一时刻聚集查询集合AQL和上一时刻最终聚集查询集合FAQL分别表示如下：其中(xLi,yLi)表示上一时刻第i个协作用户的位置；(xLU,yLU)表示查询发起者U上一时刻的位置信息；(xLNt,yLNt)表示上一时刻新加入第t个协作用户的位置；QCLi表示第i个协作用户上一时刻的查询分类；QCLNt表示上一时刻新加入的第t个协作用户上一时刻查询分类；
qcLNt表示上一时刻新加入第t个协作用户上一时刻具体查询内容，且t≥1；qcLi表示第i个协作用户上一时刻具体查询内容；qcLU表示查询发起者U上一时刻具体查询内容；
(11c)查询发起者根据自己的信息，计算上一时刻到当前时刻的运动方向夹角：
(11d)查询发起者根据整理的候选位置点集合CLS和计算出的自己上一时刻与当前时刻的运动趋势ΔθU，计算满足运动趋势要求的预位置点个数E，即对于上一时刻聚集查询集合AQL或上一时刻最终聚集查询集合FAQL中的每一个位置点，查询发起者都需要计算该位置点与候选位置点集合CLS中k个位置点间的夹角，{ΔθL1,ΔθL2,...,ΔθLi,...,ΔθLk}，且每一次当这k个角度中有不少于k/2个包含在查询发起者设定的夹角范围内时，E的值就增加1，其中ΔθLi表示上一时刻聚集查询集合AQL或上一时刻最终聚集查询集合FAQL中的任一位置点与候选位置点集合CLS中的第i个位置点间的夹角，其计算公式为：(11d)查询发起者根据E的取值，对预测的位置信息进行相应的处理：
若E≥k/2，则保留该预测位置点，并将其和相应的预测查询内容一起存储在一个第二次筛选集合SLFS中，即其中(xpfi,ypfi)表示第i个协作用户第f个预测位置，且1≤f≤w；
否则，舍弃该预测位置点，再在第一次筛选集合FLQS中重新选择一个与之前不同的预测位置点，再判断其运动趋势是否满足条件；
(12)查询发起者根据已构建协作群中仍可继续用于协作查询的用户数目多少，选择不同的算法重新构建用户协作群，并对建立的用户协作群中的用户信息进行预测、筛选，按如下步骤进行：
12a)查询发起者根据步骤6c)中q的取值，利用不同的算法构建协作用户群：
若q≥k/2，则利用SDUCT算法来重新组建用户协作群，即查询发起者首先发送“可继续协作”信息给仍可继续用于协作的用户，并与其继续保持联系；发送“不继续协作”信息给不可继续协作的用户，并与其断绝联系，再执行步骤12b)；
若q≤1时，则利用DUCT算法来重新组建用户协作群，即查询发起者直接执行步骤12b)；
12b)查询发起者发出协作建群请求，并广播出去，收到该协作请求信息的第I个协作用户根据自己当前时刻的位置分类信息LCcI、当前所在区域的几何中心坐标(x0I,y0I)c、查询发起者的当前的位置分类信息LCcU和当前所在区域的几何中心坐标(x0U,y0U)c决定是否与其建立协作关系：若LCcI＝LCcU或者(x0I,y0I)c＝(x0U,y0U)c±τ，则同意该协作建群请求，并发送自己的信息给该查询发起者，其中τ∈[0,50]米；
否则，拒绝该协作请求，且不发送自己的任何信息给该查询发起者,I≥1；
12c)查询发起者将收到的第I个协作用户的回复信息UQRI和自己的信息MSU，分别表示如下：UQRI＝{UIDcI,(xcI,ycI),QCcI,qccI,TeI,VcI,hcI,NcI}；
MS＝{MIDc ,UIDc ,(xc ,yc),QCc ,qcc ,Tec ,kc ,Hmaxc}；
其中MIDcU表示查询发起者U当前请求协作信息的编号；UIDcI表示第I个协作用户当前时刻的真实身份信息；UIDcU表示查询发起者U当前时刻的真实身份信息；(xcI,ycI)表示第I个协作用户当前时刻的位置信息；(xcU,ycU)表示查询发起者U当前时刻的位置信息；QCcI表示U I第I个协作用户当前时刻的查询分类；QCc表示查询发起者U当前时刻的查询分类；qcc 表示第I个协作用户当前时刻的具体查询内容；qccU表示查询发起者U当前时刻的具体查询内容；
Tei表示第i个协作用户查询的截止时间；TecU表示查询发起者U当前时刻的查询截止时间；
VcI表示第I个协作用户当前时刻的速度；hcI表示第I个协作用户与查询发起者之间的跳数；
NcI表示当前时刻与第I个协作用户参与建群的用户个数；kcU表示查询发起者U规定的当前查询所需的其他协作用户个数；HmaxcU表示查询发起者U当前查询规定的最大跳数；
hcI≤HmaxcU，表示第I个协作用户与查询发起者之间的跳数hcI应小于等于查询发起者当前查询所规定的最大跳数HmaxcU；
NcI＝0，表示当前时刻与第I个协作用户协作建群的其他用户数目应为0；
TecU＜TeI，表示查询发起者当前的查询截止时间TecU应小于第I个协作用户查询的截止时间TeI；
12e)查询发起者根据设置的条件对回复信息UQRI中的第I个协作用户与查询发起者之间的跳数hcI、当前时刻与第I个协作用户协作建群的其他用户数目NcI和第I个协作用户查询的截止时间TeI进行筛选，并与满足条件的k-1个用户建立协作关系；
再根据自己上一时刻和当前时刻的运动方向夹角，对筛选出的预测位置点再次筛选，选出运动趋势相近的预测位置点，最后将筛选出的预测位置点、预测查询内容和自己的真实信息一起整理，形成一个最终聚集查询集合FAQ发送给位置服务器LBS-S，执行步骤(13)；
(13)位置服务器收到聚集查询集合AQ或者最终聚集查询集合FAQ后，查找自己的数据库，形成候选结果集CRS，并返回给各个协作用户；收到此候选结果集CRS的各个协作用户，根据自己的真实信息，筛选出自己所需的查询结果，并将其记录在缓存器中。
2.根据权利要求1所述的方法，其中步骤(3)中查询发起者根据通信距离长短、人口密度大小和时间段的不同，将整个查询大区域划分为当前流行区域CP和当前普通区域CO，按如下步骤进行：
3a)查询发起者根据通信距离长短将整个查询大区域划分为若干不规则小区域，表示为：R＝{r1,r2,...,rn,...}，其中R指整个大的查询区域，rn指第n个小的不规则区域，n≥1；
3b)查询发起者根据当前时间段和区域中当前人口密度大小将所划分的小区域再划分为当前流行区域CP和当前普通区域CO两类，其中，当前流行区域CP是指在当前时间段内人口密度≥50；当前普通区域CO是指在当前时间段内人口密度≤5。
3.根据权利要求1所述的方法，其中步骤(6)中利用FFLQ算法对回复信息中的位置信息和查询内容进行筛选，按如下步骤进行：U I
6a)将查询发起者U自己的信息UQ和收到第I个协作用户的信息UQ分别表示如下：
其中，UIDcU表示查询发起者U当前时刻的真实身份信息；UIDcI表示第I个协作用户当前时刻的真实身份信息,I≥1；(xcI,ycI)表示第I个协作用户当前时刻的位置信息；(xcU,ycU)表示查询发起者U当前时刻的位置信息；LCcI表示第I个协作用户当前时刻位置分类；LCcU表示查询发起者U当前时刻位置分类；QCcI表示第I个协作用户当前时刻的查询分类；QCcU表示查询发起者U当前时刻的查询分类；qccI表示第I个协作用户当前时刻的具体查询内容；qccU表示查询发起者U当前时刻的具体查询内容；TscI表示第I个协作用户当前时刻的查询开始时间；TscU表示查询发起者U当前时刻的查询开始时间；TecI表示第I个协作用户当前时刻的查询截止时间；TecU表示查询发起者U当前时刻的查询截止时间；VcI表示第I个协作用户当前时刻的查询速度；VcU表示查询发起者U当前时刻的查询速度；(x0I,y0I)c表示第I个协作用户当前所在位置区域的几何中心坐标；(x0U,y0U)c表示查询发起者U当前所在位置区域的几何中心坐标；
(x0 ,y0)c＝(x0 ,y0)c±τ，表示第I个协作用户当前所在区域的几何中心坐标(x0 ,y0I)c应在查询发起者U当前所在区域的几何中心坐标(x0U,y0U)c附近，其中τ∈[0,50]米；
TecU≤TecI，表示查询发起者U当前时刻的查询截止时间TecU应小于等于第I个协作用户当前时刻的查询截止时间TecI；
Vc＝Vc ±μ，表示第I个协作用户当前时刻的速度Vc 应与查询发起者U当前时刻的速度VcU相当，其中μ∈[0,0.5]米/秒；
ΔθcI＝ΔθcU±ξ，表示第I个协作用户当前时刻的运动趋势ΔθcI应接近查询发起者当前时刻U的运动趋势ΔθcU，其中ξ∈[0°,10°]；
其中 表示第I个协作用户当前的运动方向与x轴的夹角，
6c)查询发起者首先设定q为满足四个设置条件的协作用户个数，且将其初始值置为0，再根据设置的四个条件对第I个协作用户信息UQI中第I个协作用户当前所在位置区域的几I I I何中心坐标(x0 ,y0)c、第I个协作用户当前时刻的查询截止时间Tec 、第I个协作用户当前时刻的查询速度VcI和第I个协作用户当前时刻的位置信息(xcI,ycI)进行筛选，每筛选一个，q的值便增加1，最终将满足条件的协作用户信息存储在一个准用户集合WUS中并记录q的最终值；
6d)查询发起者首先设定p为准用户集WUS中所有协作用户查询分类个数，且将其初始值置为0，然后检索整个准用户集合WUS，当QCI≠QCU且QCI≠QCK时，p的值便增加1，记录p的最终值，其中QCK是指第K个协作用户当前的查询分类，K≥1且I≠K；
6e)当p≥L且q≥k-1时，查询发起者在WUS中任选k-1个协作用户信息存入一个一次过滤用户集合FFUS中，其中L表示查询分类的个数，k表示参与本次协作的用户总数。
4.根据权利要求1所述的方法，其中步骤(7)中查询发起者将这k-1个协作用户的信息和自己的真实查询信息一起进行整理，形成聚集查询集合AQ，按如下步骤进行：
7a)查询发起者收集一次过滤用户集合的FFUS中的k-1个协作用户信息MFFUS和自己的U信息UM：
UMU＝{UIDcU,(xcU,ycU),QCcU,qccU,TeU}，
其中UIDci表示第i个查询用户当前时刻的真实身份信息,1≤i≤k-1；UIDcU表示查询发起者U当前时刻的真实身份信息；(xci,yci)表示第i个协作用户当前时刻的位置信息；(xcU,ycU)表示查询发起者U当前时刻的位置信息；QCci表示第i个协作用户当前时刻的查询分类；
QCcU表示查询发起者U当前时刻的查询分类；qcci表示第i个协作用户当前时刻的具体查询内容；qccU表示查询发起者U当前时刻的具体查询内容；Tei表示第i个协作用户的查询截止U时间；Te表示查询发起者U的查询截止时间；
7b)查询发起者整理MFFUS信息和UMU信息，并存入一个聚集查询集合AQ中，即其中UIDL表示协作用户身份信息列表，其形式为：UIDL＝{ID1,ID2,...,IDi,...,IDk-1,IDU}＝{UIDc1,UIDc2,...,UIDci,...,UIDck-1,UIDcU}；
IDi表示第i个协作用户的最终身份信息；IDU表示查询发起者U的最终身份信息。
5.根据权利要求1所述的方法，其中步骤(8)中利用CVCG算法判断该已构建好的用户协作群是否依然有效，按如下步骤进行：
8a)查询发起者根据上一时刻形成的聚集查询集合AQL或最终用户聚集查询集合FAQL中协作用户的身份信息，发出发送当前时刻所在区域的几何中心坐标的通知，收到该通知的各个协作用户将自己当前时刻所在区域的几何中心坐标发送给该查询发起者；
8b)查询发起者收到各个协作用户当前所在区域的几何中心坐标{(x01,y01)c,(x02,y02)c,...,i i k-1 k-1(x0 ,y0)c,...,(x0 ,y0 )c}后，设定M为仍可用于协作的用户个数且其初始值置为0，当(x0i,y0i)c＝(x0U,y0U)c±τ，τ∈[0,50]米时，M的值便会增加1，其中(x0i,y0i)c表示第i个协作用户当前所在区域的几何中心坐标，(x0U,y0U)c表示查询发起者U当前所在区域的几何中心坐标；
6.根据权利要求1所述的方法，其中步骤(9)中根据自己上一时刻和当前时刻时间段内的路程、上一时刻的运动趋势、当前时刻的具体查询内容对各协作用户当前时刻的位置信息和查询内容进行预测，按如下步骤进行：
9a)将查询发起者收集的所有协作用户上一时刻的信息UQL、自己当前时刻的查询信息UQcU和缓存数据CD分别表示如下：CD＝{LRI,PRI,BGI}＝{{LSL,ListsL},{LSC,QCS,qcS,ListsC},ListWL}，其中UIDLi表示第i个协作用户上一时刻的身份信息；UIDcU表示查询发起者U当前时刻的身份信息；(xLi,yLi)表示第i个协作用户上一时刻的位置；(xLU,yLU)表示查询发起者U上一时刻的位置；(xcU,ycU)表示查询发起者U当前时刻的位置；QCLi表示第i个协作用户上一时刻的查询类型；QCcU表示查询发起者U当前时刻的查询类型；qcLi表示第i个协作用户上一时刻的具体查询内容；qccU表示查询发起者U当前时刻的具体查询类型；TsLi表示第i个协作用户上一时刻查询开始时间；TscU表示查询发起者U当前时刻查询开始时间；Tei表示第i个协作用户的查询截止时间；TecU表示查询发起者U当前时刻的查询截止时间；VLi表示第i个协作用户上U i i一时刻的查询速度；Vc表示查询发起者U当前时刻的查询速度；(x0 ,y0)L表示第i个协作用户上一时刻所在区域的几何中心坐标；(x0U,y0U)c表示查询发起者U当前时刻所在区域的几何中心坐标；CD表示缓存数据信息；LRI表示位置服务器返回的信息；PRI表示各个协作用户返回的信息；BGI表示整个查询区域的基本地理信息；LSL表示位置服务器返回的位置信息集合；ListsL表示位置服务器返回的查询结果信息列表；LSC表示各个协作用户返回的位置信息集合；QCS表示各个协作用户返回的查询分类信息集合；qcS表示各个协作用户返回的具体查询内容信息集合；ListsC表示各个协作用户返回的查询结果信息列表；ListWL表示整个查询区域的位置信息列表；
第i个协作用户以其上一时刻的速度VLi行驶路程scU所用的时间：
第i个协作用户在查询发起者当前查询时间段内以其上一时刻速度VLi所行驶的路程：
9c)查询发起者设定N为已构建好的所有协作用户查询分类个数，且N初始值置为0，并检索集合UQL和UQcU，当QCcU≠QCLi且QCLi≠QCLj时，N的值增加1，1≤i≤k-1，1≤j≤k-1-i且i+j＝k-1；
9d)查询发起者根据计算的scU、ΔθcU、tci、si和收集的第i个协作用户上一时刻查询开始时间TsLi，对第i个协作用户上一时刻的运动趋势ΔθLpi和上一时刻与当前时刻时间段内所行驶的第m个可能路程spmi进行预测：若tci+TsLi≤Tei，则ΔθLpi＝ΔθLU±ξ，spmi＝si±ζ且spmi＝scU±ε；
其中ξ是一个角度值且ξ∈[0°,10°]，ζ和ε表示数值不同的两个距离值，且ζ∈[1,5]，ε∈[5,10]，m≥3；
9e)当已构建好的所有协作用户查询分类个数N小于查询发起者设定的查询分类阈值L时，查询发起者根据自己的查询分类QCcU、第i个协作用户上一时刻的查询分类QCLi、第j个协作用户上一时刻的查询分类QCLj和计算的参数N，对第i个协作用户当前时刻的查询分类QCci和具体查询内容qcci进行预测：若QCcU＝QCLi，则舍弃QCLi，赋予QCci一个不同于QCLi的查询分类值QCNi，即QCci＝QCNi，且QCNi≠QCcU,同时赋予qcci一个新的与QCNi相关的具体查询内容qcNi，即qcci＝qcNi；
若QCcU≠QCLi且QCLi＝QCLj，则舍弃QCLi，赋予QCci一个新的不同于QCLi和QCcU的查询分类值QCNi，即QCci＝QCNi，且QCci≠QCLj，同时赋予qcci一个新的与QCNi相关的具体查询内容qcNi，i i即qcc＝qcN；
9f)查询发起者整理所有预测信息，并将其存储在一个预测聚集查询集合AQSBP中：其中IDi表示第i个协作用户最终的身份信息；(xpmi,ypmi)表示第i个协作用户第m个预测位置；QCpi表示第i个协作用户当前时刻预测的查询分类；QCLi表示第i个协作用户上一时刻i i的查询分类；qcp表示第i个协作用户当前时刻预测的具体查询内容；qcL表示第i个协作用户上一时刻的具体查询内容。
7.根据权利要求1所述的方法，其中步骤(12)中查询发起者将筛选出的预测位置点、预测查询内容和自己的真实信息一起整理，形成一个最终聚集查询集合FAQ发送给位置服务器LBS-S，按如下步骤进行：
12f)将查询发起者整理的第二次筛选集合SLFS、所有协作用户上一时刻的信息UQL、自己当前时刻的查询信息UQcU，分别表示如下：其中(xpfi,ypfi)表示第i个协作用户第f个预测位置，1≤f≤w；IDi表示第i个协作用户最终的身份信息；IDU表示查询发起者U最终的身份信息；(xcU,ycU)表示查询发起者U当前时刻的位置信息；qcpi表示第i个协作用户预测的具体查询内容；qcLi表示第i个协作用户上一时刻的具体查询内容；qccU表示查询发起者U当前时刻的具体查询内容；UIDLi表示第i个协作用户上一时刻的真实身份信息；UIDcU表示查询发起者U当前时刻的真实身份信息；(xLi,yLi)表示第i个协作用户上一时刻的位置信息；(xLU,yLU)表示查询发起者U上一时刻的位置信息；QCLi表示第i个协作用户上一时刻的查询分类；QCcU表示查询发起者U当前时刻的查询分类；TsLi表示第i个协作用户上一时刻查询开始时间；TscU表示查询发起者U当前时刻的查询开始时间；Tei表示第i个协作用户的查询截止时间；TecU表示查询发起者U当前时刻的查询截止时间；VLi表示第i个协作用户上一时刻的查询速度；VcU表示查询发起者U当前时刻的查询速度；(x0i,y0i)L表示第i个协作用户上一时刻所在区域的几何中心坐标；(x0U,y0U)c表示查询发起者U当前时刻所在区域的几何中心坐标；
12g)查询发起者在第二次位置筛选集合SLFS中任意选择一个预测位置点，再将该选出的预测位置点与其他的收集信息一起整理存储到一个最终聚集查询集合FAQ中，即其中UIDL表示协作用户身份列表，其形式为UIDL＝{ID1,ID2,...,IDi,...,IDk-1,IDU}＝{UID1,UID2,...,UIDi,...,UIDk-1,UIDU},UQCL表示协作用户查询内容列表,其形式为：(xphi,yphi)表示第i个协作用户第h个预测位置，1≤h≤f。
基于轨迹预测的隐私保护方法
技术领域
[0001] 本发明属于无线网络安全领域，特别涉及一种隐私保护方法，可用于各种连续查询位置服务中。
背景技术
[0002] 位置服务LBS，又称定位服务，其是由移动通信网络和卫星定位系统结合在一起提供的一种增值业务，通过一组定位技术获得移动终端的位置信息，如经纬度坐标数据，并将此位置信息提供给移动用户本人、其他人或者通信系统，来实现各种与位置相关的业务。
[0003] 位置服务可以被应用于不同的领域，与此同时，在移动互联网大发展的趋势下，各类应用也在蓬勃发展。尤其，随着定位技术的快速发展，使得嵌入了位置服务LBS功能的应用得到了广泛的普及，给人们的生活带来了极大的便利。但LBS服务需要获知用户精确的位置信息，其对用户的隐私造成了极大的威胁。所以，在保证用户服务质量的同时，如何有效的保护用户的隐私信息是LBS服务目前所面临的巨大挑战。特别地，由于连续查询场景下用户位置信息之间的时空关联性，其隐私信息更容易泄露，其常常遭遇两种攻击——连续查询攻击和轨迹攻击。为了抵御这两种攻击，学者们提出了许多解决方法:
[0004] 第一种方法是：传统的k-匿名方案k-anonymity。该方案主要用于单点查询中。将该方案直接用于连续查询场景时，其主要存在三个问题：第一，虽然连续查询每个查询位置点都满足k-匿名的要求，但由于连续查询的匿名位置集具有时空联系，导致即使查询的各个时刻都进行了k匿名保护，但其仍易遭受位置关联攻击也叫连续查询攻击，即攻击者将若干个位置集合取交集，就可以很容易的得到或以很大的概率猜测真实查询用户，其过程如图3所示，包括三个图，其中图3(a)表示查询发起者U在ti-1时刻所形成的匿名区域示意图，图3(b)表示查询发起者U在ti时刻所形成的匿名区域示意图，图3(c)表示查询发起者U在ti+1时刻所形成的匿名区域示意图，且每个图都包含U、B、C、D、E、F、G、H这8个用户。图3(a)中实线矩形框表示查询发起者ti-1时刻所形成的匿名区域，其匿名用户集合为{C,E,F,U}；图3(b)中实线矩形框表示查询发起者ti时刻所形成的匿名区域，其匿名用户集合为{D,E,G,U}；图3(c)中实线矩形框表示查询发起者ti时刻所形成的匿名区域，其匿名用户集合为{B,D,H,U}；图3(b)和图3(c)中的虚线矩形框分别表示查询发起者ti-1时刻的匿名用户在ti时刻和ti+1时刻所形成的匿名区域，其匿名用户集合都为{C,E,F,U}，观察这三个虚线矩形框可以看出，随着查询时间的推移ti-1时刻形成的匿名用户集合变得越来越大，同时攻击者收集这三个时刻的匿名用户集合{C,E,F,U}、{D,E,G,U}、{B,D,H,U}，对其取交集就可得出查询的真实用户为用户U。
[0005] 第二，整个连续查询期间的匿名位置集合只是用最初选择的k-匿名位置集，虽然该方法在一定程度上避免了位置关联攻击，但是由于用户移动是动态变化的，所以最初形成的k-匿名位置集会聚集在一起，或者过于分散，从而导致服务质量无法保证。
[0006] 第三，该方法直接用于连续查询中易遭受轨迹攻击，即连续查询每个时刻都进行了匿名保护，但由于连续查询的时空关联性，使得攻击者在一定时间段内可推测出该查询发起者的真实查询轨迹，其原理如图4所示，共包括五个图，其中图4(a)表示t1时刻的匿名区域示意图，图4(b)表示t2时刻的匿名区域示意图，图4(c)表示t3时刻的匿名区域示意图，图4(d)表示t4时刻的匿名区域示意图，图4(e)表示t5时刻的匿名区域示意图，且每个时刻都含有{U,B,C,D,E,F,G,H}8个移动用户，用于查询过程中用户隐私信息保护，其匿名用户集合分别为{U,B,C,G}、{U,B,D,F}、{U,D,H,G}、{U,B,E,F}、{U,D,F,H}，虽然查询发起者U每个时刻的位置信息都进行了4-匿名保护，但在t1-t5时刻连续查询期间内，由于连续查的时空关联性，导致具有丰富背景知识的攻击者即使不知道查询发起者U在各个时刻真实的位置信息，但其仍会以很大的概率推测出该查询发起者U在t1-t5时间段内的运动轨迹，如图4(a)-(e)中贯穿t1-t55个时刻的实线矩形框的红色实线所示。
[0007] 第二种方法是：基于假位置方案，该方案可应用于单点查询和连续查询中。但该方案也存在一些缺点，即在产生假位置点时缺少背景知识的考虑，导致所产生的某些位置点不合理，从而使得攻击者很容易根据背景知识排除掉这些不合理点，最终大大提高攻击概率。即使充分考虑了背景知识，但其选择和产生需要消耗一定的资源，代价太高。同时它们还是虚假位置，没有任何实际意义和实用价值。
[0008] 第三种方法是：基于用户协作方案，该方案可用于单点查询和连续查询中，其具体方法是聚集附近k个用户一起协作完成k-匿名，然后进行查询。该方法在一定程度上保护了用户隐私，但其也存在一定的缺点，即协作用户之间的通信开销相比其他方案较大，同时其很难保证协作用户的隐私。
发明内容
[0009] 本发明的目的在于针对上述已有技术的不足，提出一种基于轨迹预测的隐私保护方法，以同时确保查询用户和其他协作用户的隐私安全性，提高查询的有效性和服务的高质量性。
[0010] 实现本发明的技术方案，包括如下：
[0011] (1)建立一个由若干移动用户和位置服务器构成的隐私保护框架；
[0012] (2)由手机生产厂商为每部手机安装一个缓存装置，用于用户在查询过程中对有用信息的存储；
[0013] (3)查询发起者根据通信距离长短、人口密度大小和时间段的不同，将整个查询大区域划分为当前流行区域CP和当前普通区域CO；
[0014] (4)查询发起者发出协作请求，并将其广播给通信范围之内的其他用户；
[0015] (5)收到该协作请求信息的用户，将自己当前区域类型与查询发起者的进行对比：
[0016] 若当前区域类型与查询发起者的区域类型一致或者他们所在区域的中心位置坐标之间的距离在阈值τ∈[0,50]的范围内，则同意该协作建群请求，并将自己的相关信息发送给查询发起者；
[0017] 否则，拒绝该协作建群请求，且不发送自己的任何信息给查询发起者；
[0018] (6)当查询发起者收到至少k-1个用户的回复信息时，查询发起者再利用FFLQ算法对回复信息中的位置信息和查询内容进行筛选，与满足条件的k-1个用户建立协作关系，并获得k-1个协作用户的信息，k∈[4,14]；
[0019] (7)查询发起者将这k-1个协作用户的信息和自己的真实查询信息一起进行整理，形成聚集查询集合AQ；
[0020] (8)查询发起者根据当前协作请求次数的不同，对聚集查询集合AQ进行相应的处理：
[0021] 若协作请求次数为1，则查询发起者直接将形成的聚集查询集合AQ发送给位置服务器LBS-S，执行步骤(13)；
[0022] 否则，查询发起者舍弃该聚集查询集合AQ，并利用CVCG算法判断该已构建好的用户协作群是否依然有效；若有效，则执行步骤(9)，若无效，则执行步骤(12)；
[0023] (9)查询发起者根据自己上一时刻和当前时刻时间段内的路程、上一时刻的运动趋势和当前时刻的具体查询内容对各协作用户当前时刻的位置信息和查询内容进行预测；
[0024] (10)查询发起者根据位置点出入度的个数，对预测的位置信息进行第一次筛选，保留满足条件的预测信息，舍弃不满足条件的预测信息；
[0025] (11)查询发起者根据其上一时刻和当前时刻的运动方向夹角，对步骤(10)中筛选出的预测位置点进行第二次筛选，并和相应的预测查询内容、自己的信息一起形成一个最终聚集查询集合FAQ发送给位置服务器LBS-S，执行步骤(13)；
[0026] (12)查询发起者根据已构建协作群中仍可继续用于协作查询的用户数目多少，选择不同的算法重新构建用户协作群，并对建立的用户协作群中的用户信息进行预测、筛选，再根据自己上一时刻和当前时刻的运动方向夹角，对筛选出的预测位置点再次筛选，选出运动趋势相近的预测位置点，最后将筛选出的预测位置点、预测查询内容和自己的真实信息一起整理，形成一个最终聚集查询集合FAQ发送给位置服务器LBS-S，执行步骤(13)；
[0027] (13)位置服务器收到聚集查询集合AQ或者最终聚集查询集合FAQ后，查找自己的数据库，形成候选结果集CRS，并返回给各个协作用户；收到此候选结果集CRS的各个协作用户，根据自己的真实信息，筛选出自己所需的查询结果，并将其记录在缓存器中。
[0028] 本发明具有如下优点：
[0029] 1)本发明由于使用了分布式用户协作建群实现匿名的方法，所以有效避免了集中式中可信第三方的单点攻击问题，同时解决了匿名用户寻找和用户是否自愿的问题，进一步增强了用户隐私保护的可能性和可行性；
[0030] 2)本发明由于采用了基于预测的隐私保护算法，不仅可实现对查询发起者自身的隐私保护，而且也可实现对协作用户群中其他用户的隐私保护；
[0031] 3)本发明由于使用了缓存机制，使得用户在查询时变得方便快捷，在一定程度上降低了通信开销、减少了访问查询位置服务器的频率；
[0032] 4)本发明由于在对用户信息进行预测时考虑了各个位置点间的时间可达性、速度相似性、运动趋势相似性、入度与出度个数、相邻查询的时间间隔等因素，能很好的保证预测位置点的准确度和可用性；
[0033] 5)本发明由于使用了动态构建协作用户群的机制，避免了在查询过程中其匿名区域面积出现过大和过小的问题；同时由于对协作群可用性的持续判断，减少了重建用户群的次数，从而大大节省了查询时间、降低了通信开销；
[0034] 6)本发明由于采用了位置k-匿名和查询L-多样度相结合的方法，同时实现了用户位置和查询内容隐私保护；
[0035] 7)本发明由于采用了相似轨迹预测的方法，在保护查询发起者各个时刻位置和查询内容隐私的同时，更好地保护了其运动轨迹隐私，且能有效抵御位置关联攻击和轨迹攻击。
附图说明
[0036] 图1是现有基于用户协作的分布式隐私保护架构图；
[0037] 图2是本发明的实现流程图；
[0038] 图3是本发明中的位置关联攻击示意图；
[0039] 图4是本发明中的轨迹攻击示意图；
[0040] 图5是本发明中的查询内容保护示意图；
[0041] 图6是本发明中的预测位置示意图。具体实施方案
[0042] 本发明的中心思想是采用图1基于用户协作的分布式隐私保护架构，其主要是由查询发起者发出协作建群请求，并进行广播；能收到该协作建群请求并愿意与其进行协作的其他用户回复相应的信息给该查询发起者，然后该查询发起者根据其查询的次数及其隐私保护需要，对返回的信息进行筛选或预测处理，并根据位置点出入度个数要求，对预测的位置信息进行第一次筛选；再根据其上一时刻和当前时刻的运动方向夹角，对第一次筛选出的位置信息进行第二次筛选；最终该查询发起者将各个协作用户的二次筛选预测位置点、预测的查询内容以及自身真实信息一起整理，形成一个聚集查询集合AQ或最终聚集查询集合FAQ，并将其发送给位置服务器。位置服务器根据所收到的内容，查找数据库，形成相应的候选结果集CRS并返回给各个用户。收到该候选结果集的各个协作用户，根据自身的真实信息对该候选结果集进行过滤，筛选出满足其要求的查询结果。同时，所有协作用户将该查询内容及其结果存储于各自的缓存器中，以便自己或其他用户需要。
[0043] 下面结合附图对本发明的实施和效果作详细说明。
[0044] 参照图1，本发明使用的隐私保护框架，包括移动用户和位置服务器LBS-S。该移动用户，是移动互联网中普通的移动用户，其拥有具有缓存装置的移动设备，用于移动通信网络中某个查询发起者发出协作建群请求时，在物理通信距离允许的范围内，实现用户协作群的构建，并最终由该查询发起者将形成的聚集查询集合AQ或最终聚集查询集合FAQ，发送给位置服务器LBS-S。该位置服务器LBS-S,其内部存储着所有LBS服务所需的信息，用于LBS查询服务结果的提供。在位置服务中，其操作应依照LBS系统的相关规则和协议，但不排除其是不诚实且感兴趣的，故在本方案中LBS-S是半可信的，其主要用于用户请求查询结果的提供，即形成候选结果集CRS，并返回给各个协作用户。
[0045] 参照图2，本发明基于上述隐私保护框架进行隐私保护的实现步骤如下：
[0046] 步骤1，查询发起者对整个查询覆盖区域进行分类。
[0047] (1.1)查询发起者根据通信距离长短将整个查询大区域划分为若干不规则小区域,表示为：R＝{r1,r2,...,rn,...}，其中R指整个大的查询区域，rn指第n个小的不规则区域，n≥1；
[0048] (1.2)查询发起者根据当前时间段和区域中当前人口密度大小将所划分的小区域再划分为当前流行区域CP和当前普通区域CO两类，其中，当前流行区域CP是指在当前时间段内人口密度≥50；当前普通区域CO是指在当前时间段内人口密度≤5。
[0049] 步骤2，查询发起者发出请求协作消息。
[0050] (2.1)任意想要协作建群的移动用户，均可发起请求协作消息，广播出去，并等待网络中其他用户的回复；
[0051] (2.2)收到该协作请求信息的第I个协作用户根据自己当前时刻的位置分类信息LCcI、当前所在区域的几何中心坐标(x0I,y0I)c、查询发起者U当前的位置分类信息LCcU和当前所在区域的几何中心坐标(x0U,y0U)c决定是否与其建立协作关系：
[0052] 若LCcI＝LCcU或者(x0I,y0I)c＝(x0U,y0U)c±τ，则同意该协作建群请求，并发送自己的信息给该查询发起者，其中τ∈[0,50](m)；
[0053] 否则，拒绝该协作请求，且不发送自己的任何信息给该查询发起者,其中I表示回复该查询发起者的协作用户个数且I≥1。
[0054] 步骤3，查询发起者利用FFLQ算法对回复信息中的位置信息和查询内容进行筛选，并与满足条件的k-1个用户建立协作关系。
[0055] (3.1)将查询发起者U自己的信息UQU和收到第I个协作用户的信息UQI分别表示如下：
[0056] UQU＝{UIDcU,(xcU,ycU),LCcU,QCcU,qccU,TscU,TecU,VcU,(x0U,y0U)c}；
[0057] UQI＝{UIDcI,(xcI,ycI),LCcI,QCcI,qccI,TscI,TecI,VcI,(x0I,y0I)c}；
[0058] 其中，UIDcU表示查询发起者U当前时刻的真实身份信息；UIDcI表示第I个协作用户当前时刻的真实身份信息,I≥1；(xcI,ycI)表示第I个协作用户当前时刻的位置信息；(xcU,ycU)表示查询发起者U当前时刻的位置信息；LCcI表示第I个协作用户当前时刻位置分类；LCcU表示查询发起者U当前时刻位置分类；QCcI表示第I个协作用户当前时刻的查询内容分类；QCcU表示查询发起者U当前时刻的查询内容分类；qccI表示第I个协作用户当前时刻的具体查询内容；qccU表示查询发起者U当前时刻的具体查询内容；TscI表示第I个协作用户当前时刻的查询开始时间；TscU表示查询发起者U当前时刻的查询开始时间；TecI表示第I个协作用户当前时刻的查询截止时间；TecU表示查询发起者U当前时刻的查询截止时间；VcI表示第I个协作用户当前时刻的查询速度；VcU表示查询发起者U当前时刻的查询速度；(x0I,y0I)c表示第I个协作用户当前所在区域的几何中心坐标；(x0U,y0U)c表示查询发起者U当前所在区域的几何中心坐标；
[0059] (3.2)查询发起者设置如下4个筛选条件：
[0060] (x0I,y0I)c＝(x0U,y0U)c±τ，表示第I个协作用户当前所在区域的几何中心坐标(x0I,y0I)c应在查询发起者U当前所在区域的几何中心坐标(x0U,y0U)c附近，其中τ∈[0,50](m)；
[0061] TecU≤TecI，表示查询发起者U当前时刻的查询截止时间TecU应小于等于第I个协作用户当前时刻的查询截止时间TecI；
[0062] VcI＝VcU±μ，表示第I个协作用户当前时刻的速度VcI应与查询发起者U当前时刻的速度VcU相当，其中μ∈[0,0.5](m/s)；
[0063] ΔθcI＝ΔθcU±ξ，表示第I个协作用户当前时刻的运动趋势ΔθcI应接近查询发起者当前时刻U的运动趋势ΔθcU，其中ξ∈[0°,10°]；
[0064] 其中 表示第I个协作用户当前的运动方向与x轴的夹角，
[0065] 表示查询发起者U当前的运动方向与x轴的夹角；
[0066] (3.3)查询发起者首先设定q为满足四个设置条件的协作用户个数，且将其初始值置为0，再根据设置的四个条件对第I个协作用户信息UQI中第I个协作用户当前所在位置区I I I域的几何中心坐标(x0 ,y0)c、第I个协作用户当前时刻的查询截止时间Tec 、第I个协作用户当前时刻的查询速度VcI和第I个协作用户当前时刻的位置信息(xcI,ycI)进行筛选，每筛选一个，q的值便增加1，最终将满足条件的协作用户信息存储在一个准用户集合WUS中并记录q的最终值；
[0067] (3.4)查询发起者首先设定p为准用户集WUS中所有协作用户查询分类个数，且将其初始值置为0，然后检索整个准用户集合WUS，当QCI≠QCU且QCI≠QCK时，p的值便增加1，记录p的最终值，其中QCK是指第K个协作用户当前的查询分类，K≥1且I≠K；
[0068] (3.5)当p≥L且q≥k-1时，查询发起者在WUS中任选k-1个协作用户信息存入一个一次过滤用户集合FFUS中，其中L表示查询分类的个数，k表示参与本次协作的用户总数。
[0069] 步骤4，查询发起者将这k-1个协作用户的信息和自己的真实查询信息一起进行整理，形成聚集查询集合AQ。
[0070] (4.1)查询发起者收集一次过滤用户集合的FFUS中的k-1个协作用户信息MFFUS和自己的信息UMU：
[0071]
[0072] UMU＝{UIDcU,(xcU,ycU),QCcU,qccU,TeU}，
[0073] 其中UIDci表示第i个查询用户当前时刻的真实身份信息,1≤i≤k-1；UIDcU表示查询发起者U当前时刻的真实身份信息；(xci,yci)表示第i个协作用户当前时刻的位置信息；U U i
(xc ,yc)表示查询发起者U当前时刻的位置信息；QCc 表示第i个协作用户当前时刻的查询分类；QCcU表示查询发起者U当前时刻的查询分类；qcci表示第i个协作用户当前时刻的具体查询内容；qccU表示查询发起者U当前时刻的具体查询内容；Tei表示第i个协作用户的查询截止时间；TeU表示查询发起者U的查询截止时间；
[0074] (4.2)查询发起者整理MFFUS信息和UMU信息，并存入一个聚集查询集合AQ中，即：
[0075]
[0076] 其中：UIDL表示协作用户身份信息列表，其形式为：
[0077] UIDL＝{ID1,ID2,...,IDi,...,IDk-1,IDU}＝{UIDc1,UIDc2,...,UIDci,...,UIDck-1,UIDcU}；
[0078] UQCL表示协作用户查询内容列表，其形式为：
[0079]
[0080] IDi表示第i个协作用户的最终身份信息；IDU表示查询发起者U的最终身份信息。
[0081] 步骤5，查询发起者根据当前协作请求次数的不同，对聚集查询集合AQ进行相应的处理。
[0082] 查询发起者自身拥有一个计数器，用于记录自身发起协作建群请求的次数，且其初始值置为0，每当查询发起者发起一次协作建群请求，该计数器就计数一次；
[0083] 当若该计数器的值为1时，则查询发起者直接将形成的聚集查询集合AQ发送给位置服务器LBS-S，跳转到步骤12-13；
[0084] 否则，查询发起者舍弃该聚集查询集合AQ，执行步骤6。
[0085] 步骤6，对用户协作群的有效性进行判断。
[0086] 查询发起者利用CVCG算法判断已构建好的用户协作群是否依然有效：
[0087] (6.1)查询发起者根据上一时刻形成的聚集查询集合AQL或最终用户聚集查询集合FAQL中协作用户的身份信息，发出发送当前时刻所在区域的几何中心坐标的通知，收到该通知的各个协作用户将自己当前时刻所在区域的几何中心坐标发送给该查询发起者；
[0088] (6.2)查询发起者收到各个协作用户当前所在区域的几何中心坐标{(x01,y01)c,(x02,y02)c,...,(x0i,y0i)c,...,(x0k-1,y0k-1)c}后，设定M为仍可用于协作的用户个数且其初始值置为0，当(x0i,y0i)c＝(x0U,y0U)c±τ，τ∈[0,50](m)时，M的值便会增加1，其中(x0i,y0i)c表示第i个协作用户当前所在区域的几何中心坐标，(x0U,y0U)c表示查询发起者U当前所在区域的几何中心坐标；
[0089] (6.3)根据M的值判断用户协作群是否有效：
[0090] 若M＝k-1，则表明已构建好的用户协作群仍有效，执行步骤7-8；
[0091] 否则，则表明已构建好的用户协作群无效，执行步骤9-10。
[0092] 步骤7，查询发起者对各个协作用户当前时刻的位置信息和查询内容进行预测。
[0093] (7.1)将查询发起者收集所有协作用户上一时刻的信息UQL、自己当前时刻的查询信息UQcU和缓存数据CD分别表示如下：
[0094]
[0095] UQcU＝{UIDcU,(xLU,yLU),(xcU,ycU),QCcU,qccU,TscU,TecU,VcU,(x0U,y0U)c}，[0096] CD＝{LRI,PRI,BGI}＝{{LSL,ListsL},{LSC,QCS,qcS,ListsC},ListWL}，[0097] 其中UIDLi表示第i个协作用户上一时刻的身份信息；UIDcU表示查询发起者U当前时刻的身份信息；(xLi,yLi)表示第i个协作用户上一时刻的位置；(xLU,yLU)表示查询发起者U上一时刻的位置；(xcU,ycU)表示查询发起者U当前时刻的位置；QCLi表示第i个协作用户上一时刻的查询类型；QCcU表示查询发起者U当前时刻的查询类型；qcLi表示第i个协作用户上一时刻的具体查询内容；qccU表示查询发起者U当前时刻的具体查询类型；TsLi表示第i个协作用户上一时刻查询开始时间；TscU表示查询发起者U当前时刻查询开始时间；Tei表示第i个协U i作用户的查询截止时间；Tec表示查询发起者U当前时刻的查询截止时间；VL 表示第i个协作用户上一时刻的查询速度；VcU表示查询发起者U当前时刻的查询速度；(x0i,y0i)L表示第i个协作用户上一时刻所在区域的几何中心坐标；(x0U,y0U)c表示查询发起者U当前时刻所在区域的几何中心坐标；CD表示缓存数据信息；LRI表示位置服务器返回的信息；PRI表示各个协作用户返回的信息；BGI表示整个查询区域的基本地理信息；LSL表示位置服务器返回的位置信息集合；ListsL表示位置服务器返回的查询结果信息列表；LSC表示各个协作用户返回的位置信息集合；QCS表示各个协作用户返回的查询分类信息集合；qcS表示各个协作用户返回的具体查询内容信息集合；ListsC表示各个协作用户返回的查询结果信息列表；ListWL表示整个查询区域的位置信息列表；
[0098] (7.2)查询发起者根据收集的信息计算如下参数：
[0099] 查询发起者U当前查询时间段内行驶的路程：
[0100] 查询发起者U上一查询时刻的运动趋势：
[0101] 第i个协作用户以其上一时刻的速度VLi行驶路程scU所用的时间：
[0102] 第i个协作用户当前时刻位置信息的横坐标：xci＝xLi+VLi*(TecU-TscU)；
[0103] 第i个协作用户当前时刻位置信息的纵坐标：即yci＝yLi+VLi*(TecU-TscU)；
[0104] 第i个协作用户在查询发起者当前查询时间段内以其上一时刻速度VLi所行驶的路程：
[0105] (7.3)查询发起者设定N为已构建好的所有协作用户查询分类个数，且N初始值置U U i i j为0，并检索集合UQL和UQc ，当QCc≠QCL且QCL≠QCL时，N的值增加1，1≤i≤k-1，1≤j≤k-
1-i且i+j＝k-1；
[0106] (7.4)查询发起者根据计算的scU、ΔθcU、tci、si和收集的第i个协作用户上一时刻查询开始时间TsLi，对第i个协作用户上一时刻的运动趋势ΔθLpi和上一时刻与当前时刻时i i i i i U i i间段内所行驶的第m个可能路程spm进行预测：若tc+TsL≤Te，则ΔθLp＝ΔθL±ξ，spm＝s±ζ且spmi＝scU±ε，其中ξ是一个角度值且ξ∈[0°,10°]，ζ和ε表示数值不同的两个距离值，且ζ∈[1,5]，ε∈[5,10]，m≥3。图6给出了该预测方法的一个具体实例，其中图6左侧的6个实心小圆点分别表示U1-U6这6个协作用户上一时刻的位置坐标信息，图6右侧的灰色小圆点分别表示与图6左侧对应的6个协作用户当前时刻的预测位置信息，且同一个协作用户当前时刻所有可能预测位置都包含在一个椭圆区域内，其中用户U1有4个预测的可能位置，用户U2有3个预测的可能位置，用户U3有3个预测的可能位置，用户U4共有4个预测的可能位置，用户U5有3个预测的可能位置，用户U6共有4个预测的可能位置；图6中的虚线段表示在查询发起者U上一时刻与当前时刻的时间间隔内，图6左侧各个协作用户的真实位置点和图6右侧的预测位置点是可达的。
[0107] (7.5)当已构建好的所有协作用户查询分类个数N小于查询发起者设定的查询分类阈值L时，查询发起者根据自己的查询分类QCcU、第i个协作用户上一时刻的查询分类QCLi、第j个协作用户上一时刻的查询分类QCLj和计算的参数N，对第i个协作用户当前时刻的查询分类QCci和具体内容信息qcci进行预测：
[0108] 若QCcU＝QCLi，则舍弃QCLi，赋予QCci一个不同于QCLi的查询分类值QCNi，即QCci＝QCNi，且QCNi≠QCcU,同时赋予qcci一个新的与QCNi相关的具体查询内容qcNi，即qcci＝qcNi；
[0109] 若QCcU≠QCLi且QCLi＝QCLj，则舍弃QCLi，赋予QCci一个新的不同于QCLi和QCcU的查询i i i i j i i分类值QCN ，即QCc＝QCN ，且QCc ≠QCL ，同时赋予qcc一个新的与QCN 相关的具体查询内容qcNi，即qcci＝qcNi；图5给出了该预测方法的一个具体实例，共包括两个图，图5(a)表示各个协作用户上一时刻的信息，图5(b)表示各个协作用户当前时刻的信息，且每个图中分别有7个协作用户，每个协作用户都记录着各自的用户身份信息UID、位置坐标信息(x,y)、查询分类信息QC、具体的查询内容信息qc。同时两个图中由于每个协作用户的位置坐标都不相同，所以满足位置隐私要求，即位置7-匿名，但图5(a)中查询分类只有QC1和QC2两类，故不能满足查询内容隐私保护要求；图5(b)则根据查询发起者的查询分类内容，对各个协作用户当前时刻的查询分类和具体的查询内容进行预测，使得查询内容由原来的QC1、QC2两类变为了
1 2 3 4 5
QC、QC、QC、QC、QC五类，满足了查询内容5-多样度隐私保护要求；
[0110] (7.6)查询发起者整理所有预测信息，并将其存储在一个预测聚集查询集合AQSBP中：
[0111]
[0112] 其中IDi表示第i个协作用户最终的身份信息；(xpmi,ypmi)表示第i个协作用户第m个预测位置；QCpi表示第i个协作用户当前时刻预测的查询分类；QCLi表示第i个协作用户上一时刻的查询分类；qcpi表示第i个协作用户当前时刻预测的具体查询内容；qcLi表示第i个协作用户上一时刻的具体查询内容。
[0113] 步骤8，查询发起者根据位置点出/入度的个数，对预测的位置信息进行第一次筛选。
[0114] (8.1)查询发起者从预测聚集查询集合AQSBP中任选各个协作用户的预测信息，并将所选的预测信息和自己的当前时刻信息一起存入到一个预测信息集合PS中：
[0115]
[0116] 其中IDi表示第i个协作用户最终的身份信息；IDU表示查询发起者U最终的身份信息；(xpgi,ypgi)表示第i个协作用户第g个预测位置，且1≤g≤m，m≥3；qcpi表示第i个协作用户当前时刻预测的具体查询内容；qcLi表示第i个协作用户上一时刻的具体查询内容；(xcU,ycU)表示查询发起者U当前时刻的真实位置；qccU表示查询发起者U当前时刻的真实具体查询内容；
[0117] (8.2)将查询发起者整理的上一时刻聚集查询集合AQL和上一时刻最终聚集查询集合FAQL分别表示如下：
[0118]
[0119] 其中(xLi,yLi)表示第i个协作用户上一时刻的位置；(xLU,yLU)表示查询发起者U上一时刻的位置；(xLNt,yLNt)表示上一时刻新加入第t个协作用户的位置；QCLi表示第i个协作U U用户上一时刻的查询分类；QCL 表示查询发起者U上一时刻的查询分类；qcL表示查询发起者U上一时刻的具体查询内容；QCLNt表示上一时刻新加入的第t个协作用户上一时刻查询分类；qcLNt表示上一时刻新加入第t个协作用户上一时刻具体查询内容，且t≥1；
[0120] (8.3)查询发起者根据整理的预测信息集合PS、上一时刻聚集查询集合AQL和上一时刻最终聚集查询集合FAQL的信息，分别计算上一时刻聚集查询集合AQL或上一时刻最终聚集查询集合FAQL中满足位置出度要求的预测位置点个数P和预测信息集合PS中满足位置入度要求的预测位置点个数Q：
[0121] 对于上一时刻聚集查询集合AQL或上一时刻最终聚集查询集合FAQL中的每一个位置点，查询发起者都需要计算该位置点与预测信息集合PS中k个位置点间的距离{DLp1,DLp2,...,DLpi,...,DLpk}，且每一次当这k个距离中有不少于k/2个包含在查询发起者设定的距离范围scU±ε，ε∈[5,10](m)内时，P的值就增加1，其中DLpi表示上一时刻聚集查询集合AQL或上一时刻最终聚集查询集合FAQL中的任一位置点与预测信息集合PS中的第i个位置点间的距离；
[0122] 对于预测信息集合PS中的每一个位置点，查询发起者都需要计算该位置点与上一时刻聚集查询集合AQL或上一时刻最终聚集查询集合FAQL中的k个位置点间的距离{DpL1,DpL2,...,DpLi,...,DpLk},且每一次当这k个距离中有不少于k/2个包含在查询发起者设定的距离范围scU±ε，ε∈[5,10](m)内时，Q的值就增加1，其中DpLi表示预测信息集合PS中的任一位置点与上一时刻聚集查询集合AQL或上一时刻最终聚集查询集合FAQL中第i个位置点间的距离；
[0123] (8.4)查询发起者根据P和Q的取值，对预测的信息进行相应的处理：
[0124] 若同时满足P≥k/2和Q≥k/2，则保留该预测信息，并将该预测信息和自己的相关信息一起存入一个第一次位置筛选集合FLFS中，即：
[0125]
[0126] 其中xpwi表示第i个协作用户第w个预测位置，且1≤w≤m，m≥3；
[0127] 否则，忽略该预测信息，再在聚集查询集合AQSBP中重新选则其他不同的预测信息，并根据位置点的出/入度个数要求，对新选择的预测位置信息进行第一次筛选。
[0128] 步骤9，查询发起者根据其上一时刻和当前时刻的运动方向夹角，对第一次筛选出的预测位置信息进行第二次筛选。
[0129] (9.1)查询发起者在第一次位置筛选集合FLFS中任意选择各个协作用户的一个预测位置点，并和自己的信息存入一个候选位置点集合CLS中，即
[0130]
[0131] IDi表示第i个协作用户的最终身份信息；(xpvi,ypvi)表示第i个协作用户第v个预测位置，且1≤v≤w；IDU表示查询发起者U的最终身份信息；(xcU,ycU)表示查询发起者U当前时刻的位置信息；qcLi表示第i个协作用户上一时刻的具体查询内容；qcpi表示第i个协作用户预测的具体查询内容；qccU表示查询发起者U当前时刻的具体查询内容；
[0132] (9.2)查询发起者整理的上一时刻聚集查询集合AQL和上一时刻最终聚集查询集合FAQL分别表示如下：
[0133]
[0134] 其中(xLi,yLi)表示上一时刻第i个协作用户的位置；(xLU,yLU)表示查询发起者U上一时刻的位置信息；(xLNt,yLNt)表示上一时刻新加入第t个协作用户的位置；QCLi表示第i个协作用户上一时刻的查询分类；QCLNt表示上一时刻新加入的第t个协作用户上一时刻查询分类；qcLNt表示上一时刻新加入第t个协作用户上一时刻具体查询内容，且t≥1；qcLi表示第i个协作用户上一时刻具体查询内容；qcLU表示查询发起者U上一时刻具体查询内容；
[0135] (9.3)查询发起者根据自己的信息，计算上一时刻到当前时刻的运动方向夹角：
[0136]
[0137] (9.4)查询发起者根据整理的候选位置点集合CLS和计算的自己上一时刻与当前时刻的运动趋势ΔθU，计算满足运动趋势要求的预测位置点个数E，即对于上一时刻聚集查询集合AQL或上一时刻最终聚集查询集合FAQL中的每一个位置点，查询发起者都需要计算该位置点与位置候选位置点集合CLS中k个位置点间的夹角，{ΔθL1,ΔθL2,...,ΔθLi,...,ΔθLk}，且每一次当这k个角度中有不少于k/2个包含在查询发起者设定的夹角范围内时，E的值就增加1，其中ΔθLi表示上一时刻聚集查询集合AQL或上一时刻最终聚集查询集合FAQL中的任一位置点与候选位置点集合CLS中的第i个预测位置点间的夹角，其计算公式为：
[0138] (9.5)查询发起者根据E的取值，对预测的位置信息进行相应的处理：
[0139] 若E≥k/2，则保留该预测位置点，并将其和相应的预测查询内容一起存储在一个第二次位置筛选集合SLFS中，即：
[0140]
[0141] 其中(xpfi,ypfi)表示第i个协作用户第f个预测位置，且1≤f≤w；
[0142] 否则，舍弃该预测位置点，再在第一次位置筛选集合FLFS中重新选择一个与之前不同的预测位置点，并判断其运动趋势是否满足条件。
[0143] 步骤10，查询发起者调用DUCT算法或者SDUCT算法重新构建用户协作群。
[0144] (10.1)查询发起者根据步骤3.3)中q的取值，利用不同的算法构建协作用户群：
[0145] 若q≥k/2，则利用SDUCT算法来重新组建用户协作群，即查询发起者首先发送“可继续协作”信息给仍可继续用于协作的用户，并与其继续保持联系；发送“不继续协作”信息给不可继续协作的用户，并与其断绝联系，再执行步骤(10.2)；
[0146] 若q≤1时，则利用DUCT算法来重新组建用户协作群，即查询发起者直接执行步骤(10.2)；
[0147] (10.2)查询发起者发出协作建群请求，并广播出去，收到该协作请求信息的第I个协作用户根据自己当前时刻的位置分类信息LCcI、当前所在区域的几何中心坐标(x0I,y0I)c、查询发起者的当前的位置分类信息LCcU和当前所在区域的几何中心坐标(x0U,y0U)c决定是否与其建立协作关系：
[0148] 若LCcI＝LCcU或者(x0I,y0I)c＝(x0U,y0U)c±τ，则同意该协作建群请求，并发送自己的信息给该查询发起者，其中τ∈[0,50](m)；
[0149] 否则，拒绝该协作请求，且不发送自己的任何信息给该查询发起者,其中I表示回复该查询发起者的协作用户个数且I≥1；
[0150] (10.3)查询发起者将收到的第I个协作用户的回复信息UQRI和自己的信息MSU，分别表示如下：
[0151] UQRI＝{UIDcI,(xcI,ycI),QCcI,qccI,TeI,VcI,hcI,NcI}；
[0152] MSU＝{MIDcU,UIDU,(xcU,ycU),QCcU,qccU,TecU,kcU,HmaxcU}，
[0153] 其中MIDcU表示查询发起者U当前请求协作信息的编号；UIDcI表示第I个协作用户当前时刻的真实身份信息；UIDcU表示查询发起者U当前时刻的真实身份信息；(xcI,ycI)表示表示第I个协作用户当前时刻的位置信息；(xcU,ycU)表示查询发起者U当前时刻的位置信息；QCcI表示第I个协作用户当前时刻的查询分类；QCcU表示查询发起者U当前时刻的查询分I U类；qcc表示第I个协作用户当前时刻的具体查询内容；qcc表示查询发起者U当前时刻的具体查询内容；Tei表示第i个协作用户查询的截止时间；TecU表示查询发起者U当前时刻的查询截止时间；VcI表示第I个协作用户当前时刻的速度；hcI表示第I个协作用户与查询发起者之间的跳数；NcI表示当前时刻与第I个协作用户参与建群的用户个数；kcU表示查询发起者U规定的当前查询所需的其他协作用户个数；HmaxcU表示查询发起者U当前查询规定的最大跳数；
[0154] (10.4)查询发起者设置如下3个条件：
[0155] hcI≤HmaxcU，表示第I个协作用户与查询发起者之间的跳数hcI应小于等于查询发起者前查询所规定最大跳数HmaxcU；
[0156] NcI＝0，表示当前时刻与第I个协作用户协作建群的其他用户数目应为0；
[0157] TscU＜TeI，表示查询发起者当前的查询截止时间TscU应小于第I个协作用户查询的截止时间TeI；
[0158] (10.5)查询发起者根据设置的条件对回复信息UQRI中的第I个协作用户与查询发起者之间的跳数hcI、当前时刻与第I个协作用户协作建群的其他用户数目NcI和第I个协作用户查询的截止时间TeI进行筛选，并与满足条件的k-1个用户建立协作关系。
[0159] 步骤11，查询发起者形成最终聚集查询集合FAQ发送给发送给位置服务LBS-S。
[0160] (11.1)查询发起者调用步骤3中的FFLQ算法对步骤10中新加入的协作用户信息进行筛选，保留满足条件的用户信息，舍弃不满足条件的用户信息；
[0161] (11.2)查询发起者调用步骤7中的位置信息与查询内容预测算法对步骤10中仍可继续协作的各协作用户当前信息进行预测，记录所预测的协作用户信息；
[0162] (11.3)查询发起者调用步骤8中的位置出/入度筛选算法对步骤(11.2)中的形成的预测位置信息进行第一次筛选，保留满足筛选条件的预测信息，舍弃不满足筛选条件的预测信息；
[0163] (11.4)查询发起者调用步骤9中的运动轨迹筛选算法对步骤(11.3)中筛选出的位置信息进行第二次筛选，保留满足运动趋势要求的预测信息，舍弃不满足要求的预测信息；
[0164] (11.5)查询发起者根据收集的信息、保留的位置预测信息、预测的查询内容以及自己的信息，形成一个最终聚集查询集合FAQ，按如下步骤进行：
[0165] (11.5a)查询发起者整理的第二次位置筛选集合SLFS、所有协作用户上一时刻的信息UQL、自己当前时刻的查询信息UQcU，分别表示如下：
[0166]
[0167]
[0168] UQcU＝{UIDcU,(xLU,yLU),(xcU,ycU),QCcU,qccU,TscU,TecU,VcU,(x0U,y0U)c}；
[0169] 其中(xpfi,ypfi)表示第i个协作用户第f个预测位置，1≤f≤w；IDi表示第i个协作用户最终的身份信息；IDU表示查询发起者U最终的身份信息；qcpi表示第i个协作用户预测的具体查询内容；qcLi表示第i个协作用户上一时刻的具体查询内容；qccU表示查询发起者U当前时刻的具体查询内容；UIDLi表示第i个协作用户上一时刻的真实身份信息；UIDcU表示查询发起者U当前时刻的真实身份信息；(xLi,yLi)表示第i个协作用户上一时刻的位置信息；(xLU,yLU)表示查询发起者U上一时刻的位置信息；(xcU,ycU)表示查询发起者U当前时刻的位置信息；QCLi表示第i个协作用户上一时刻的查询分类；QCcU表示查询发起者U当前时刻的查询分类；TsLi表示第i个协作用户上一时刻查询开始时间；TscU表示查询发起者U当前时刻的查询开始时间；Tei表示第i个协作用户的查询截止时间；TecU表示查询发起者U当前时刻的查询截止时间；VLi表示第i个协作用户上一时刻的查询速度；VcU表示查询发起者U当前时刻的查询速度；(x0i,y0i)L表示第i个协作用户上一时刻所在区域的几何中心坐标；(x0U,y0U)c表示查询发起者U当前时刻所在区域的几何中心坐标；
[0170] (11.5b)查询发起者在第二次位置筛选集合SLFS中任意选择一个预测位置点，再将该选出的预测位置点与其他的收集信息一起整理存储到一个最终聚集查询集合FAQ中，即
[0171]
[0172] 其中UIDL表示协作用户身份列表，其形式为
[0173] UIDL＝{ID1,ID2,...,IDi,...,IDk-1,IDU}＝{UID1,UID2,...,UIDi,...,UIDk-1,UIDU},
[0174] UQCL表示协作用户查询内容列表,其形式为：
[0175]
[0176] (xphi,yphi)表示第i个协作用户第h个预测位置，1≤h≤f；
[0177] (11.6)查询发起者将步骤(11.5)形成的最终聚集查询集合FAQ发送给发送给位置服务LBS-S。
[0178] 步骤12，位置服务器收到聚集查询集合AQ或最终聚集查询集合FAQ后，查找自己的数据库，形成候选结果集CRS，并返回给各个协作用户。
[0179] 步骤13，收到此候选结果集CRS的各个协作用户，根据自己的真实信息，筛选出自己所需的查询结果，并将其记录在缓存器中。
[0180] 以上描述仅是本发明的一个具体实例，并未构成对本发明的任何限制，显然对于本领域的专业人员来说，在了解了本发明内容和原理后，都可能在不背离本发明原理、结构的情况下，进行形式和细节上的各种修改和改变，但是这些基于发明思想的修正和改变仍在本发明的权利要求保护范围之内。
