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

呂 鑫，趙連成，余記遠(yuǎn)，譚 彬，曾 濤，陳 娟

1.河海大學(xué) 計(jì)算機(jī)與信息學(xué)院，南京210098

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

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

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

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

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

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

1 相關(guān)知識(shí)

1.1 LBS下的隱私保護(hù)技術(shù)

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

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

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

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

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

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

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

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

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

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

2.1 基本思路

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

2.2 定義

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

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

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

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

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

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

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

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

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

核心對(duì)象：對(duì)于任一樣本xj∈D，如果其ε 鄰域?qū)?yīng)的Ns( xj)至少包含MinPts 個(gè)樣本，即| Ns( xj)|≥MinPts，則xj是核心對(duì)象。

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

2.3 方法的提出

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

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

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

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

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

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

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

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

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

2.3.1 基于緩存機(jī)制的位置查詢算法

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

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

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

算法1 基于緩存機(jī)制的位置查詢算法

輸入：查詢用戶u，隱私需求k，跳數(shù)h，最大可容忍跳數(shù)值Hmax，響應(yīng)用戶數(shù)du，代理用戶Ua，用戶個(gè)數(shù)n。

輸出：鄰近用戶集合P，單次查詢結(jié)果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} //收集響應(yīng)的協(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）//近鄰緩存信息命中查詢請(qǐng)求，返回查詢結(jié)果

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

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

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

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

輸出：響應(yīng)用戶數(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 //當(dāng)有新用戶加入或離開更新位置列表

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

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

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

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

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

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

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

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

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é)點(diǎn)

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

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

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

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

6.send Fake Query(ASR)

7.else if

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

9.send a live query

10.end if

11.else

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

13.send Query(ASR)

14.end if

15.end

3 實(shí)驗(yàn)分析

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

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

表2 實(shí)驗(yàn)參數(shù)

3.1 混淆度

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

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

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

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

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

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

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

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

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

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

3.2 平均處理時(shí)間

在實(shí)驗(yàn)中時(shí)間周期是指從用戶構(gòu)建匿名區(qū)域的時(shí)刻到用戶收到LBS興趣點(diǎn)的時(shí)刻。

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

圖9 混淆度為0.5的算法處理時(shí)間對(duì)比

圖10 混淆度為0.7的算法處理時(shí)間對(duì)比

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

圖11 算法間處理時(shí)間對(duì)比

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

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

3.3 平均通信消息量

移動(dòng)用戶的通信成本主要由鄰近節(jié)點(diǎn)廣播協(xié)作的消息量成本和向位置服務(wù)商查詢的消息量成本兩部分組成。因?yàn)槿绻脩粜枰獔?zhí)行多次廣播請(qǐng)求響應(yīng)，總體的通信成本就會(huì)增加。

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

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

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

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

圖15 算法間通信消息量對(duì)比

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

4 結(jié)束語

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