基于軌跡聚類的連續(xù)查詢隱私保護方法

呂 鑫，趙連成，余記遠，譚 彬，曾 濤，陳 娟

1.河海大學 計算機與信息學院，南京210098

2.華能瀾滄江水電股份有限公司，昆明650214

隨著網(wǎng)絡技術的飛速發(fā)展和智能移動終端的全面普及，各類智能應用已經(jīng)深入到人們的日常生活中，其中基于位置的智能應用服務是最常用的一類服務?；谖恢玫姆眨↙ocation Based Service，LBS）是指用戶基于自身的地理位置發(fā)起一種服務請求，服務提供商返回給用戶與位置息息相關的服務。典型的LBS 應用[1-3]包括地圖類應用、興趣點檢索、GPS 導航和位置感知社交網(wǎng)絡等，極大地提高了人們的生活質量。然而，人們在享受LBS服務帶來便利的同時，也存在著隱私泄露的風險。用戶在請求位置服務過程中通常需要提供一些與自身相關的信息，例如：身份信息、個人空間位置、查詢時間、查詢內容等信息。攻擊者可能會搜集用戶的請求數(shù)據(jù)和歷史位置數(shù)據(jù)等敏感信息，根據(jù)這些信息和關聯(lián)規(guī)則推斷出用戶的活動范圍，進一步推測出生活習慣、家庭住址、接觸人群等詳細的隱私信息，對用戶財產(chǎn)安全造成危害。

隱私問題是阻礙LBS進一步發(fā)展的主要障礙之一，用戶期望在保護自身信息安全的同時，享受優(yōu)質的位置服務。當前，因位置隱私泄露導致用戶財產(chǎn)受到損失的事件時有發(fā)生，位置隱私保護技術越發(fā)重要。為解決攻擊者易利用查詢與位置間關聯(lián)概率發(fā)起攻擊的問題，Zhang 等人[4]基于差分隱私的概念，提出了一種概率不可區(qū)分的安全機制，進而設計了一種位置轉換方案用以混淆查詢與發(fā)起位置間的關聯(lián)，并通過理論分析與實驗驗證了所提方法的性能。王嘉慧等人[5]提出的網(wǎng)格擴增法，以網(wǎng)格邊緣的形式自底向上地快速擴建匿名區(qū)，在保證查詢結果正確性的同時，減少了查詢處理的成本。為了防止訪問者試圖獲取被訪問者不希望泄露的隱私信息，張伊璇等人[6]建立了一個隱私保護模型，該模型計算訪問者進行善意訪問的概率，與隱私信息擁有者的容忍程度相比較，再決定是否通過訪問者的訪問請求。

以上方法是針對用戶單次查詢場景下的隱私保護問題。然而在連續(xù)查詢場景下，攻擊者可以根據(jù)連續(xù)查詢過程中匿名集合的變化，從而判斷出用戶的真實位置。如圖1 所示，在首次與第二次查詢中，匿名集合都包含了用戶A和用戶D，可推斷出真實用戶為用戶A或用戶D；在第二次與第三次查詢中，匿名集合都包含用戶A和用戶H，可推斷出真實用戶為用戶A或用戶H；綜合三次查詢，即可判斷出用戶A 為真實查詢用戶，并得到用戶A的移動軌跡。除此之外，攻擊者還可以利用時空相關性確定匿名區(qū)域的范圍，從而縮小用戶真實位置的所在區(qū)域。因此，針對快照LBS的經(jīng)典匿名方法不能直接應用于連續(xù)LBS 的用戶軌跡隱私保護。Chen 等人[7]對單次快照位置查詢的k 匿名方法進行了擴展，將初始的匿名區(qū)域擴展到所有連續(xù)查詢中包含相同的k個用戶的區(qū)域，以保證k 個用戶在不同方向上的移動，增加了匿名區(qū)域的混淆度。Zhang等人[8]提出了一種不確定連續(xù)協(xié)作用戶發(fā)現(xiàn)算法，該方法利用網(wǎng)格區(qū)域的不確定性單元和協(xié)作用戶隱藏查詢用戶身份，且所有查詢結果均由協(xié)作用戶提供，查詢方無需與LBS服務器進行交互，從而實現(xiàn)了良好的隱私保護效果。Peng等人[9]提出由用戶在不同時間不同地點，發(fā)布亂序假查詢，使得連續(xù)位置是亂序的，攻擊者難以排序識別正確的軌跡，提高了用戶軌跡隱私的安全性。Zhang等人[10]基于Markov預測，提出了一種匿名位置預測方案。該方案同時考慮了查詢概率匿名性與匿名位置可鏈接性，解決了已有方法在連續(xù)匿名場景下查詢概率匿名難以鏈接的問題，因此該方案可有效抵御統(tǒng)計攻擊與推斷攻擊。此外，王斌等人[11]提出了一種ε-敏感程度不可區(qū)分的隱私保護方法，以解決用戶移動過程中的敏感程度漸進導致隱私泄露的問題。該方法基于差分隱私理論并結合Voronoi圖劃分，通過添加噪聲數(shù)據(jù)以滿足ε-敏感程度不可區(qū)分，并進一步優(yōu)化了噪聲添加數(shù)量，在有效抵御利用敏感程度漸進發(fā)起的攻擊的同時，保證了服務質量。

另外，在LBS 連續(xù)查詢場景下，用戶的屬性信息也易于被攻擊者獲取進而被用于分析推斷用戶的真實位置甚至軌跡，針對此，Zhang等人[12]提出了基于粒子群優(yōu)化算法（PSO）的屬性泛化隱私保護方案。該方案利用PSO算法的特性提升了泛化過程的效率。另外，Zhang等人[13]還基于CP-ABE 方法提出了一種新型屬性匿名方案，以抵御推斷攻擊并解決第三方服務器不可信的問題。進一步地，在屬性泛化的基礎上，王斌等人[14]利用同態(tài)加密實現(xiàn)了秘態(tài)屬性泛化，解決了已有方法可被攻擊者利用屬性進行追蹤的問題，同時秘態(tài)處理過程進一步保護了用戶的隱私。

分析了以上方法可以看出現(xiàn)有的連續(xù)查詢位置隱私保護方法，存在構建的匿名區(qū)域過大、用戶等待時間較長等缺點。因此，連續(xù)查詢隱私保護方法仍具有研究價值，且應重點考慮多用戶節(jié)點的廣播與響應，協(xié)作匿名區(qū)的合理，查詢位置的干擾，保障連續(xù)場景下的用戶軌跡隱私安全。針對以上問題，本文提出基于時空聚類的連續(xù)查詢隱私保護方法。該方法支持近鄰緩存的用戶之間的協(xié)作，發(fā)布假查詢模糊用戶的真實軌跡，通過使用聚類生成的興趣區(qū)，進行假查詢來擾亂真實軌跡點，最后使用混淆度來衡量該算法的擾亂程度。

1 相關知識

1.1 LBS下的隱私保護技術

假位置和k 匿名技術是LBS 下經(jīng)典的隱私保護技術，本文算法也是在上述兩種技術的基礎上進一步進行了研究，下面對這兩種隱私技術做相關介紹。

圖1 LBS場景下的連續(xù)查詢過程

假位置技術是干擾技術中常用的一類技術，是指用戶選擇或生成一系列虛假位置，干擾用戶的真實位置后，發(fā)起位置服務請求。假位置技術對于虛假位置的產(chǎn)生，可根據(jù)假位置數(shù)量，分為錨點位置和虛假地址集。錨點的定義是像一個迅速定位器的標記。錨點位置是與用戶真實位置有著一定距離的位置點，既可能是真實存在的用戶位置點也可能是區(qū)域上任意位置點。用戶在發(fā)起查詢請求時，選擇錨點位置代替自己真實的地理位置，當用戶接收到LBS服務器返回查詢結果集之后再通過自身與錨點位置的距離，進行求精篩選得到最佳的查詢結果。

k 匿名是泛化技術中典型技術之一。2003年，學者Gruteser M等[15]提出將k 匿名應用到位置隱私的概念，將用戶位置泛化成區(qū)域，且區(qū)域中包含k 個位置，用戶位置與其他k-1 個鄰近用戶位置不可區(qū)分，稱為位置k匿名。用戶發(fā)起位置服務的時候，會泛化一片區(qū)域代替用戶真實位置，區(qū)域滿足k 匿名后，發(fā)送位置服務提供商，提供商返回結果集，用戶再篩選最合適的結果。

1.2 LBS下的位置隱私攻擊類型

在LBS場景下，偽裝用戶攻擊和區(qū)域中心攻擊都是攻擊者常使用的攻擊類型。本文算法也考慮了攻擊者使用上述攻擊方式來獲取位置隱私的情況，下面對這兩種攻擊做相關介紹。

偽裝用戶攻擊主要是指在用戶匿名區(qū)域中，攻擊者可偽裝成除用戶外的其他k-1 個用戶，導致匿名效果降低。偽裝用戶的數(shù)量越多越不利于查詢用戶的位置隱私安全。當用戶移動到這樣的匿名區(qū)域時，用戶的真實位置就很有可能被攻擊者獲取。針對用戶協(xié)作式的匿名方案，此類攻擊更具有威脅性。

區(qū)域中心攻擊是指攻擊者可以通過某一種方式，獲取用戶的匿名區(qū)域范圍，并針對匿名區(qū)域的中心點位置發(fā)起攻擊，不斷擴大攻擊范圍，來推斷用戶的真實位置。如圖2 所示，用戶在通信時，由于通信方向的不固定，用戶易處于區(qū)域中心附近。攻擊者不斷在中心位置進行范圍攻擊，覆蓋多次出現(xiàn)的通信用戶，再結合其他知識背景，從而推斷出用戶的位置點及軌跡。

圖2 區(qū)域中心攻擊示意

2 基于軌跡聚類的連續(xù)查詢隱私保護方法

2.1 基本思路

基于軌跡聚類的連續(xù)查詢隱私保護方法以用戶興趣區(qū)作為混淆查詢區(qū)域（Fake Query Track Based on Users"Interest Region，F(xiàn)QTIR）并在移動過程中形成軌跡聚類，用戶從多跳對等近鄰點收集有用信息，并發(fā)出假查詢來擾亂攻擊者。在用戶移動過程中，假查詢區(qū)域的選擇有著很重要的作用，若假位置區(qū)域距離用戶過近，達不到保護效果；假位置區(qū)域距離用戶過遠，容易被攻擊者識別。本文采用了密度聚類算法，考慮軌跡中時間和空間兩個因素，通過對多個用戶的位置進行密度聚類，生成一定時間段內訪問頻率較高的區(qū)域（即興趣區(qū)，Region of Interest，ROI），進而在移動過程中形成軌跡聚類，由此提出一種基于軌跡聚類的連續(xù)查詢隱私保護方法。通過這種方式，將用戶的真實位置區(qū)域轉換為虛假的匿名區(qū)域，打破提交的連續(xù)匿名區(qū)域的相關性。

2.2 定義

本文鄰居節(jié)點的選擇范圍由用戶密度決定，用戶密度由跳數(shù)、匿名區(qū)域內的用戶數(shù)等參數(shù)決定。每個用戶可以指定參數(shù)來滿足隱私需求，可以在任何時間更改隱私配置文件Hmax的設置。下面對整個區(qū)域的平均用戶密度、參與協(xié)作的用戶密度、隱私配置文件Hmax進行定義和介紹。

定義1 對于一個區(qū)域中用戶分布數(shù)D，以每一次廣播的響應用戶數(shù)Di作為樣本，任意兩個用戶通過單跳或多跳通信可達，整個區(qū)域的平均用戶密度d 為：

定義2 C 為用戶間通信可達的區(qū)域，用戶u ∈C，u 的h 領域定義為：

定義3 對用戶u ∈C，du的初始值為用戶u 的1跳鄰域范圍響應用戶數(shù)。nu是D( u,1) 內用戶有效密度的個數(shù)。用戶u 計算并更新du公式為：

定義4 最大可容忍跳數(shù)值Hmax，用戶覆蓋越廣，響應的時間延遲隨著跳數(shù)值的增加而增加，過大的時間延遲將造成嚴重的通信成本。

定義5 用戶興趣區(qū)指一個或多個用戶在一定時間段內訪問頻率較高的一定區(qū)域。

定義6 啞元區(qū)域指一個或多個用戶在一定時間段內所有可以作為假位置的點的集合。

定義7 時間閾值Ts，聚類半徑為Rsp，Eps 是ε 鄰域的最大半徑，本文設置Eps=Rsp，假設樣本集D=( x1,x2,…,xm)，

ε 鄰域：對于xj∈D ，其ε 鄰域包含樣本集D 中與xj的距離不大于ε 的子樣本集，即Ns( xj)={xj∈D|distance( xi,xj)≤ε} ，這個子樣本集的個數(shù)記為|Ns( xj)|。

核心對象：對于任一樣本xj∈D，如果其ε 鄰域對應的Ns( xj)至少包含MinPts 個樣本，即| Ns( xj)|≥MinPts，則xj是核心對象。

定義8 混淆度用來衡量算法的隱私保護程度，其表示為用戶在一段移動過程中發(fā)出虛假查詢次數(shù)與用戶發(fā)出總查詢的次數(shù)比值。計算公式為：

2.3 方法的提出

移動用戶與有限跳數(shù)內的鄰居通信并共享有效信息，當用戶擁有了共享信息數(shù)據(jù)后，可以生成一個匿名區(qū)域，模糊自身的當前位置，再向位置服務提供商發(fā)起查詢。當移動到下一個位置時，本地搜索有效信息數(shù)據(jù)，檢查該位置是否包含在收集的ASR（Anonymizing Spatial Region，匿名空間區(qū)域）中。若當前位置包含在收集的ASR 中時，用戶則選擇該位置點對應的興趣區(qū)發(fā)起混淆查詢；若不包含在收集的ASR 中，用戶將重新與多跳鄰居通信并共享有效信息，再進行上述匿名過程，實現(xiàn)軌跡聚類以達到對軌跡隱私的保護。結合具體示例（圖3）來闡述本文所提的方法步驟。

圖3 基于用戶興趣區(qū)的假查詢軌跡

軌跡上的紅星( L1～L6)表示用戶u 的足跡，黑色實心圓點表示其他用戶的位置。圓圈表示近鄰點與用戶u 共享所請求的匿名區(qū)域，圓圈內的點表示相應的匿名集。藍色矩形框( R1～R6)表示用戶發(fā)出假查詢的啞元區(qū)域。以下為結合圖3示例的方法過程：

（1）協(xié)作請求。用戶在初始位置L1時，從近鄰點收集信息，u 首先廣播請求響應，1 hop 近鄰用戶a、b、c、d收到u 的請求，并與u 共享有效信息，包括興趣點，k 匿名區(qū)域，同樣擴展至2 hop 近鄰用戶。

（2）服務結果查詢。當用戶移動到L2時，檢查L2是否包含在收集的ASR 中，若發(fā)現(xiàn)L2處于hop 數(shù)為2的用戶g 接收到的ASR 區(qū)域，則從g 接收到的存儲記錄中獲取其LBS 需求的服務數(shù)據(jù)，并執(zhí)行步驟（3）發(fā)起假查詢。若未從存儲記錄中查到對應結果，則向位置服務商發(fā)起查詢請求，并返回結果。用戶移動到L3、L4、L5、L6時，執(zhí)行步驟與L2類似。

（3）假查詢。用戶在位置L2時，根據(jù)DBSCANIR提取的興趣區(qū)，選擇L2對應的興趣區(qū)R2，在啞元區(qū)域內選擇合適的假位置發(fā)出查詢請求。

（4）鄰近用戶信息更新。當鄰近用戶的緩存信息超過有效時間期限或鄰近用戶變化量達到閾值，則執(zhí)行步驟（1）重新發(fā)起協(xié)作請求。

當用戶當前位置包含在共享的數(shù)據(jù)信息中，用戶可以在本地搜索ROI。通過虛假的ASR( R2,R3,R5,R6)進行位置查詢，滿足了每個快照查詢的用戶k 匿名要求，并且通過模糊技術，阻止了攻擊者重建用戶的軌跡，保護了用戶的軌跡隱私。

在上述方法過程中，為減少通信成本，針對該鄰近用戶共享信息的存儲問題，設計了一種基于緩存機制的位置查詢算法；用戶位置在變化的同時，匿名區(qū)域也隨之變化，為保證用戶共享信息的有效性，設計了一種基于近鄰區(qū)域用戶密度的位置更新；為提高混淆度，假查詢應位于位置查詢頻率較高的區(qū)域，針對用戶興趣區(qū)的提取問題，設計了一種基于密度聚類的興趣區(qū)提取算法。

2.3.1 基于緩存機制的位置查詢算法

用戶指定近鄰用戶個數(shù)k ，k 越大，組建的用戶群越廣，用戶獲得直接查詢結果可能性越高。緩存數(shù)據(jù)包括查詢興趣點、位置標識、查詢歷史信息、近鄰區(qū)域用戶密度。首先用戶取得個人位置點t ，發(fā)出查詢，并且設置廣播跳數(shù)h。當近鄰用戶接收響應消息，將查詢消息內容與緩存歷史信息做置換對比，當緩存內容滿足查詢需求時，不再繼續(xù)構建用戶組。查詢需求不滿足的情況下，繼續(xù)組建近鄰用戶組；接收到響應消息的近鄰用戶，更新集合P，將新發(fā)現(xiàn)的近鄰用戶存入。比較k 和集合P 中用戶個數(shù)，當k 小于集合P 用戶個數(shù)，協(xié)作用戶數(shù)達到滿足要求。否則增加h，發(fā)現(xiàn)更多協(xié)作用戶。在用戶組中選擇代理用戶，向服務器發(fā)送查詢請求，完成查詢過程。具體步驟如下：

（1）用戶請求。用戶設置跳數(shù)h，將已發(fā)現(xiàn)的近鄰用戶置于集合P 。然后廣播近鄰用戶發(fā)現(xiàn)消息，等待近鄰用戶響應。更新接收到響應消息的用戶集合，比較k 和集合P 的用戶個數(shù)n。若集合中用戶個數(shù)小于k，則需要增加h 值，直到達到Hmax值。通過廣播用戶發(fā)現(xiàn)獲得更多的近鄰用戶。近鄰用戶接收到響應消息后，更新已發(fā)現(xiàn)用戶集合P。最后將多次更新后的已發(fā)現(xiàn)用戶集合P 發(fā)送給請求用戶。

（2）用戶響應緩存。用戶發(fā)出查詢消息，消息內容為查詢請求m 和廣播跳數(shù)h 為1，將消息m 與集合P中廣播跳數(shù)h 為1 的所有近鄰用戶的緩存信息中內容做比較，如果緩存內容滿足查詢，則即刻將緩存內容發(fā)送給請求用戶，結束算法過程。否則增加廣播跳數(shù)h，繼續(xù)比較。接收到查詢內容的近鄰用戶，檢查h 值，如果h 大于1，說明接收到的消息需要多跳廣播，近鄰用戶將h 減1后，繼續(xù)廣播。等待近鄰用戶的比較結果。

算法1 基于緩存機制的位置查詢算法

輸入：查詢用戶u，隱私需求k，跳數(shù)h，最大可容忍跳數(shù)值Hmax，響應用戶數(shù)du，代理用戶Ua，用戶個數(shù)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} //收集響應的協(xié)作用戶數(shù)據(jù)

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) //代理用戶發(fā)起查詢

20.if h ≤1

21.Ua←u //由代理用戶發(fā)起查詢

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ū)域用戶密度的位置更新算法

用戶進行初始化查詢前，設置周期，用作定期更新近鄰區(qū)域的用戶密度參數(shù)。新用戶加入現(xiàn)有的集合，或者現(xiàn)有用戶的離開時，更新近鄰用戶的位置集合Q 。計算各自用戶的密度，更新跳數(shù)范圍內的du。通過周期性更新和分享位置能夠保證查詢用戶周圍的變動，避免發(fā)送多次響應消息造成通信開銷。位置更新過程的偽代碼如下：

算法2 基于近鄰區(qū)域用戶密度的位置更新算法

輸入：相鄰用戶位置AUL，位置更新信息LUM ，鄰近用戶位置集合Q。

輸出：響應用戶數(shù)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

在計算完近鄰用戶密度，以用戶密集區(qū)域優(yōu)先劃分十字區(qū)域，作為用戶提高協(xié)作效率的遍歷區(qū)域。在用戶從近鄰范圍內發(fā)起協(xié)作請求時，首先將協(xié)作范圍按一定的結構存儲，便于用戶構建匿名區(qū)域。如圖4 所示，字母表示區(qū)域編號，生成一個滿四叉樹，樹中每個用戶代表劃分的區(qū)域，根部用戶表示最大平面區(qū)域；用戶位置和用戶所在區(qū)域相對應。將平面空間區(qū)域視為一個正方形，十字遞歸分割直到分割成的每個正方形空間的a小于一個給定閾值。首先，生成滿四叉樹，避免在用戶位置區(qū)域插入時需要重新分配內存，加快插入速度。然后插入用戶位置區(qū)域到葉子用戶中并將空的用戶所占內存空間釋放掉。將用戶位置信息存儲在完全包含它的最小矩形用戶中，不存儲在它的父用戶節(jié)點中，每個用戶位置區(qū)域只在樹中存儲一次，避免存儲空間的浪費。若區(qū)域內存在多個子用戶，即代表該區(qū)域內部可以劃分的更小區(qū)域。表1為圖4中各用戶所對應區(qū)域位置統(tǒng)計表。

圖4 用戶位置與所在區(qū)域

表1 各區(qū)域用戶分布

2.3.3 基于密度聚類的興趣區(qū)提取算法

興趣區(qū)指一個或多個用戶在一定時間段內訪問頻率較高的一定區(qū)域。以軌跡中所有運動點的列表為樣本，首先確定樣本的鄰域，將首個樣本運動點加入核心對象的集合中，通過鄰域參數(shù)( )Eps,MinPts 確定核心對象的鄰域。然后在未訪問的樣本集合中，取下一個核心對象，重復確定鄰域的過程，最后標記這些樣本的類別，合并生成類別簇。偽代碼如下：

算法3 基于密度聚類的興趣區(qū)提取算法

輸入：運動點集合M ，聚類鄰域最大半徑Eps，最小鄰居節(jié)點數(shù)MinPts，用戶所在節(jié)點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)//查詢到鄰居節(jié)點賦值給鄰居節(jié)點集合

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) //查詢鄰居節(jié)點

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

基于上述的三個算法和方法具體步驟，用戶使用列表存儲自身的歷史信息或保存從其他鄰居點接收到的共享數(shù)據(jù)。為保證緩存信息的有效性，當ASR 生成時，分配一個時間戳T ，時間戳和當前系統(tǒng)之間的間隔決定了存儲數(shù)據(jù)的過期時間t 。同時，周期性地更新鄰近用戶的位置集合Q，來保證集合Q 中所有的鄰近用戶處于可響應狀態(tài)。當用戶在新位置發(fā)起查詢時，首先遍歷ASR 中是否有查詢結果，若有則反饋給用戶，并在多個興趣區(qū)中，選擇當前位置的對應區(qū)域發(fā)出假查詢；若緩存是空的，或者興趣區(qū)不存在，則發(fā)起協(xié)作廣播構建ASR，使得LBS查詢符合k 匿名，以保護隱私。偽代碼如下：

算法4 基于軌跡聚類的連續(xù)查詢隱私保護方法

輸入：緩存信息列表List，興趣區(qū)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 //在興趣區(qū)中選擇一個區(qū)域發(fā)出假查詢

6.send Fake Query(ASR)

7.else if

8.establish an ASR by using SingleQuery //使用快照查詢位置算法構建匿名區(qū)域

9.send a live query

10.end if

11.else

12.establish an ASR by using SingleQuery //使用快照查詢位置算法構建匿名區(qū)域

13.send Query(ASR)

14.end if

15.end

3 實驗分析

實驗采用Java 語言作為編程語言，運行環(huán)境為Window 7操作系統(tǒng)，Intel Core i5-2405M四核處理器，6 GB 內存。分別使用真實數(shù)據(jù)集、Oldenburg 模擬數(shù)據(jù)集[16]和Geolife 數(shù)據(jù)集[17]對算法FQTIR 進行實驗。在混淆度、平均處理時間、平均通信消息量三個方面與Peng等人[9]提出的CTPP（Collaborative Trajectory Privacy-Preserving Scheme）算法和僅實現(xiàn)k 匿名的連續(xù)快照協(xié)作算法（Baseline）[9]進行對比分析。

在取樣真實數(shù)據(jù)集時，若按照實際數(shù)據(jù)中每0.5 秒采樣，用戶位置點十分密集，每一個后續(xù)位置點都必然存在查詢用戶的已有區(qū)域數(shù)據(jù)中，導致實驗中的混淆度指標無法區(qū)分。因此對真實數(shù)據(jù)集按照每30秒軌跡點取樣進行實驗。實驗場景是移動用戶在道路上進行移動，每個移動用戶的傳輸范圍定義為100～300 m。k 匿名需求設定為3到15，連續(xù)通信廣播跳數(shù)h 從1到7，用戶數(shù)從2 000到5 000。實驗參數(shù)范圍和默認值如表2所示。

表2 實驗參數(shù)

3.1 混淆度

通過發(fā)出虛假查詢來模糊用戶軌跡，虛假查詢的數(shù)量越多，暴露給服務器的隱私信息越少，攻擊者重構軌跡的可能性就越低。通過混淆度η 評估隱私保護效果。

在取真實數(shù)據(jù)集時，為保證數(shù)據(jù)取樣合理，因此取了多組數(shù)據(jù)，15秒為一組，30秒為一組，60秒為一組，進行驗證。最后選定每30秒軌跡點取樣組，效果最佳。

在圖5中，用戶查詢次數(shù)越多混淆度也會越高。隨著k 值的增加，η 隨之增大。圖6中，F(xiàn)QTIR算法在真實數(shù)據(jù)的整體運行效果比在Oldenburg數(shù)據(jù)集上運行效果稍差，混淆度略高。因為北京市的路網(wǎng)類似棋盤狀的布局，用戶分布比較均勻，沒有特別的密集區(qū)域，用戶需要更多的多跳通信滿足k 匿名要求，從而使得軌跡被區(qū)域覆蓋的概率增大。而Oldenburg數(shù)據(jù)會形成特定的密集和稀疏區(qū)域，因此利于用戶協(xié)作。

圖5 不同查詢次數(shù)的混淆度對比

圖6 不同數(shù)據(jù)集的混淆度對比

假設用戶發(fā)出了5 次假查詢，圖7 為5 次假查詢區(qū)域的選擇過程。圖7的最后一張子圖是5次假查詢區(qū)域的結合，可以看出用戶的片段軌跡是完全可以被假查詢區(qū)域覆蓋，用戶的隱私存在威脅。

圖8 為FQTIR 算法的5 次假查詢區(qū)域，算法通過多個用戶不同時間段的軌跡聚類生成多片用戶興趣區(qū)域，假查詢區(qū)域不會過度集中，且與用戶軌跡位置無直接性關系，因此用戶軌跡點不容易被攻擊者識別出來。

圖7 CTPP假查詢區(qū)域

圖8 FQTIR假查詢區(qū)域

與CTPP 進行混淆度（即虛假查詢次數(shù)與總查詢的次數(shù)比值）對比，兩種算法都進行了5 次假查詢，但是FQTIR的假查詢區(qū)域相對分散，隱私保護效果更好。

3.2 平均處理時間

在實驗中時間周期是指從用戶構建匿名區(qū)域的時刻到用戶收到LBS興趣點的時刻。

在圖9和圖10中，算法處理時間與混淆度η 值成反比，與CTPP相比，F(xiàn)QTIR平均處理時間相對較少。圖11中，Baseline算法的平均處理時間最多，F(xiàn)QTIR算法平均處理時間最少。圖12中，F(xiàn)QTIR分別在Oldenburg數(shù)據(jù)集和Geolife 數(shù)據(jù)集上的平均處理時間的變化趨勢，基本保持穩(wěn)定。

圖9 混淆度為0.5的算法處理時間對比

圖10 混淆度為0.7的算法處理時間對比

混淆度值η 越大，表示用戶發(fā)出假查詢的數(shù)量越大，則用戶可以更多地通過搜索本地緩存的數(shù)據(jù)，而不是向服務提供商發(fā)送請求，因此查詢位置的平均處理時間越少。與CTPP 相比，由于FQTIR 在處理假查詢時，是在判斷用戶位置點是否在已有區(qū)域同時，就獲取了服務數(shù)據(jù)，然后提交當前對應的聚類區(qū)域。數(shù)據(jù)已按四叉樹結構存儲完畢。而CTPP需要按廣播通信順序依次判斷，且每次遍歷均需要返回查詢用戶，再去選擇距離用戶所在區(qū)域較遠的區(qū)域。因此FQTIR的平均處理時間較少。

圖11 算法間處理時間對比

圖12 針對兩個數(shù)據(jù)集的算法處理時間對比

由于Geolife數(shù)據(jù)集是按時刻0.5秒采樣，無法計算混淆度，因此對數(shù)據(jù)集的數(shù)據(jù)取樣時間上擴大了粒度。處理后的數(shù)據(jù)集中的位置點不再聚集，搜尋鄰居點時，造成處理時間有一定變化。

3.3 平均通信消息量

移動用戶的通信成本主要由鄰近節(jié)點廣播協(xié)作的消息量成本和向位置服務商查詢的消息量成本兩部分組成。因為如果用戶需要執(zhí)行多次廣播請求響應，總體的通信成本就會增加。

在圖13和圖14中，隨著匿名級別的提高，用戶需要向鄰居點廣播更多的消息，接收更多的響應，所以隨著k 值的增大，消息數(shù)量也隨之增加。如圖15所示，F(xiàn)QTIR算法的平均通信消息數(shù)量略大于CTPP算法的平均通信消息量。然而在k 值等于7時，F(xiàn)QTIR算法第一次執(zhí)行，需要執(zhí)行DBSCANIR 算法完成興趣區(qū)的提取，因此通信消息量明顯較高。興趣區(qū)提取完成后，短時間內不用再重復執(zhí)行DBSCANIR算法，隨著k 值的增大，消息數(shù)量也增加，但增幅就不再增大。因此，F(xiàn)QTIR算法在保護軌跡隱私方面是可以以較小的通信成本取得更好的效果。Baseline算法需要很多的時間進行廣播尋找以及等待鄰居點的響應，不計算混淆度，確定匿名區(qū)域后，發(fā)送假查詢。因此，Baseline 算法的平均通信消息量是最少的，但廣播與響應時間較長。如圖16所示，在真實數(shù)據(jù)集上，F(xiàn)QTIR 算法分別在Oldenburg 數(shù)據(jù)集和Geolife 數(shù)據(jù)集上的平均通信消息量并沒有很大的變動，具有較好的普適性。

真實數(shù)據(jù)集因是連續(xù)時間的軌跡點，用戶廣播與響應都是在很小范圍即可完成，所以在與鄰居點通信過程中，F(xiàn)QTIR算法消息量是較小的。因此說明在真實移動過程中FQTIR算法是有效的。

圖13 混淆度為0.5的算法通信消息量對比

圖14 混淆度為0.7的算法通信消息量對比

圖15 算法間通信消息量對比

圖16 針對兩個數(shù)據(jù)集的算法通信消息量對比

4 結束語

在連續(xù)位置查詢場景下，本文針對分布式協(xié)作方法的查詢請求存在重復性且軌跡易被重構的問題，提出了一種基于軌跡聚類的連續(xù)查詢隱私保護方法。在該方法中，用戶緩存了鄰近節(jié)點共享的位置數(shù)據(jù)，選取合適的混淆區(qū)域代替用戶真實位置所在區(qū)域發(fā)出假查詢，將多個時間段的軌跡聚類區(qū)域作為假區(qū)域，破壞了連續(xù)查詢的時空相關性，在達到位置隱私需求的同時，降低了查詢的時間成本。