江 頡,傅超儀

(浙江工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,杭州 310000)

1 引 言

隨著移動(dòng)設(shè)備和GPS定位技術(shù)的不斷發(fā)展,基于位置服務(wù)(LocationBasedServices,LBS)的應(yīng)用領(lǐng)域得到不斷的擴(kuò)展[1].從最初為用戶(hù)提供社交、旅行以及一些綜合生活服務(wù)等方面的增值業(yè)務(wù)到目前的智能交通、醫(yī)療定位和物流監(jiān)控等,深入到社會(huì)的各個(gè)層面.然而,在享受位置服務(wù)帶來(lái)的便利的同時(shí),用戶(hù)位置隱私保護(hù)問(wèn)題也不容忽視[2,3].通常位置服務(wù)提供商(LocationServiceProvider,LSP)首先必須獲取到用戶(hù)的位置信息才能夠提供服務(wù),其中不僅包含用戶(hù)的位置信息,還能夠通過(guò)截取用戶(hù)請(qǐng)求內(nèi)容獲知用戶(hù)其他的隱私信息,如醫(yī)療信息、生活方式等[4-6].如果LSP并非完全可信或者被惡意者攻擊,用戶(hù)的隱私信息就面臨著泄露的風(fēng)險(xiǎn)[7].同時(shí)一些惡意的用戶(hù)通過(guò)加入匿名組[8]的方式來(lái)獲取用戶(hù)的位置信息和查詢(xún)內(nèi)容用于鑒別用戶(hù)的身份,進(jìn)而獲得用戶(hù)的隱私信息.因此,如何在享受基于位置服務(wù)的同時(shí),避免隱私信息泄露是急需解決的問(wèn)題.

針對(duì)上述在位置服務(wù)中用戶(hù)隱私信息泄露的問(wèn)題,本文采用用戶(hù)協(xié)作的方式同時(shí)結(jié)合第三方服務(wù)器提出一種基于查詢(xún)分片用戶(hù)協(xié)作的位置隱私保護(hù)方法.該方法主要是通過(guò)對(duì)用戶(hù)的查詢(xún)請(qǐng)求進(jìn)行分片的形式來(lái)保護(hù)用戶(hù)的隱私信息.第三方服務(wù)器在查詢(xún)過(guò)程中無(wú)法得知用戶(hù)的相關(guān)信息.同時(shí)由于查詢(xún)過(guò)程在用戶(hù)端完成,在一定程度上降低了第三方服務(wù)器的開(kāi)銷(xiāo).

2 相關(guān)工作

近年來(lái),為了解決LBS中存在的隱私信息泄露的問(wèn)題,研究者們提出許多相關(guān)的隱私保護(hù)方案.Gruteser等[9]最早提出位置k匿名的思想,即在用戶(hù)發(fā)起查詢(xún)的匿名區(qū)域內(nèi)還至少包含k-1個(gè)其他用戶(hù),使得位置服務(wù)器無(wú)法準(zhǔn)確地識(shí)別出具體用戶(hù).在此基礎(chǔ)上,陸續(xù)地提出基于第三方服務(wù)器的模型用于解決用戶(hù)隱私問(wèn)題.Mokbel等[10]提出使用基于第三方服務(wù)器將用戶(hù)精確的位置信息模糊化為匿名區(qū)域用于發(fā)送請(qǐng)求.Gedik等[11]提出一種個(gè)性化的k匿名模型,用戶(hù)能夠指定最低匿名級(jí)別并通過(guò)可信的第三方服務(wù)器來(lái)進(jìn)行位置的匿名化處理.Zhang等[12]針對(duì)于第三方服務(wù)器在移動(dòng)用戶(hù)數(shù)量很大的情況下存在的性能問(wèn)題,提出一種新型的混合框架用于平衡第三方服務(wù)器和移動(dòng)用戶(hù)之間的負(fù)載.

在無(wú)第三方服務(wù)器方式的位置隱私保護(hù)方法中,Yiu等[13]提出一種SpaceTwist方案,用戶(hù)使用隨機(jī)選取的錨點(diǎn)代替用戶(hù)的真實(shí)位置向位置服務(wù)器發(fā)起查詢(xún),最后根據(jù)返回的查詢(xún)結(jié)果與真實(shí)位置進(jìn)行計(jì)算得到精確的查詢(xún)結(jié)果.雖然該方案避免了第三方服務(wù)器的使用,但是由于缺少用戶(hù)間的協(xié)作,無(wú)法達(dá)到k匿名的效果.黃毅等[14]在此基礎(chǔ)上進(jìn)行了改進(jìn),提出了Coprivacy方案.采用用戶(hù)協(xié)作的方式形成匿名組并將匿名組的密度中心作為錨點(diǎn)代替用戶(hù)的真實(shí)位置來(lái)發(fā)起查詢(xún).針對(duì)于錨點(diǎn)可信度的問(wèn)題,Zhou等[15]提出一種基于敏感位置多樣性的錨點(diǎn)生成方法.該方法根據(jù)用戶(hù)的訪(fǎng)問(wèn)次數(shù)和時(shí)間來(lái)選擇敏感位置形成多樣性區(qū)域,通過(guò)將其質(zhì)心作為錨點(diǎn)位置來(lái)增加用戶(hù)位置的多樣性.為了實(shí)現(xiàn)加密查詢(xún),Peng等[16]提出一種基于希爾伯特曲線(xiàn)變換的隱私保護(hù)方法,用戶(hù)利用希爾伯特曲線(xiàn)將真實(shí)的位置進(jìn)行轉(zhuǎn)換,第三方服務(wù)器收集到足夠的位置信息后形成匿名區(qū)域發(fā)送給LSP,LSP端采用維諾圖進(jìn)行近鄰算法查詢(xún),最后將查詢(xún)到的興趣點(diǎn)再利用希爾伯特曲線(xiàn)進(jìn)行轉(zhuǎn)換返回給用戶(hù).沈楠等[17]提出一種基于保序加密的網(wǎng)格化位置隱私保護(hù)方案,該方案通過(guò)將用戶(hù)的查詢(xún)范圍進(jìn)行網(wǎng)格化處理,再結(jié)合保序加密技術(shù)實(shí)現(xiàn)用戶(hù)位置信息透明的情況下完成查詢(xún).林少聰?shù)萚18]提出一種基于坐標(biāo)變換的k匿名位置隱私保護(hù)方法,向服務(wù)器發(fā)送變換后的坐標(biāo),服務(wù)器在不知道用戶(hù)真實(shí)坐標(biāo)的情況下完成請(qǐng)求服務(wù).

針對(duì)于在查詢(xún)過(guò)程中依賴(lài)第三方服務(wù)器來(lái)完成匿名處理以及在形成匿名組過(guò)程中無(wú)法保證協(xié)作用戶(hù)可信度的問(wèn)題,本文提出一種基于查詢(xún)分片用戶(hù)協(xié)作結(jié)合第三方服務(wù)器的位置隱私保護(hù)方法.通過(guò)將請(qǐng)求分片,處理結(jié)果由不同的匿名組用戶(hù)發(fā)送給位置服務(wù)器,降低了匿名組中存在不可信協(xié)作用戶(hù)時(shí)隱私信息泄露的風(fēng)險(xiǎn).同時(shí),第三方服務(wù)器在查詢(xún)過(guò)程中負(fù)責(zé)生成用戶(hù)查詢(xún)所需的錨點(diǎn)信息,其本身不參與任何匿名處理,避免了在其受到惡意攻擊時(shí)用戶(hù)隱私信息泄露的風(fēng)險(xiǎn).

3 基于切片加密的用戶(hù)協(xié)作位置隱私保護(hù)方案

3.1 系統(tǒng)架構(gòu)

本文在一定區(qū)域內(nèi)用戶(hù)自組織網(wǎng)絡(luò)的基礎(chǔ)上添加中心服務(wù)器,系統(tǒng)結(jié)構(gòu)主要由用戶(hù)(User)、中心服務(wù)器(CS)和位置服務(wù)器(LSP)三個(gè)部分組成,如圖1所示.

User是一組具有定位功能的移動(dòng)終端,包括通信協(xié)議模塊、位置匿名模塊、數(shù)據(jù)安全等級(jí)設(shè)置模塊、請(qǐng)求處理模塊和查詢(xún)處理模塊.其中通信協(xié)議模塊用于在形成匿名組的過(guò)程中向近鄰的用戶(hù)發(fā)起請(qǐng)求以及向位置服務(wù)器發(fā)起查詢(xún)請(qǐng)求Ql并獲得查詢(xún)結(jié)果.在通信協(xié)議模塊中,用戶(hù)支持P2P通信和無(wú)線(xiàn)互聯(lián)網(wǎng)通信.其中P2P通信主要用來(lái)與其他移動(dòng)用戶(hù)進(jìn)行自組織通信,無(wú)線(xiàn)互聯(lián)網(wǎng)通信用來(lái)向位置服務(wù)器發(fā)起查詢(xún)并取得查詢(xún)結(jié)果.

在位置匿名模塊中,User根據(jù)自己的隱私需求設(shè)置個(gè)性化隱私保護(hù)參數(shù)k和s.其中k表示匿名參數(shù),即用戶(hù)與其他k-1個(gè)協(xié)作用戶(hù)無(wú)法準(zhǔn)確區(qū)分.s表示用戶(hù)匿名區(qū)域半徑.位置匿名模塊主要作用是根據(jù)用戶(hù)設(shè)置隱私保護(hù)參數(shù)將通信協(xié)議模塊中得到的用戶(hù)組成匿名組.

圖1 位置隱私保護(hù)框架Fig.1 Framework of location privacy protection

在數(shù)據(jù)安全等級(jí)設(shè)置模塊中,User可以根據(jù)安全等級(jí)定義同時(shí)結(jié)合自身的隱私保護(hù)需求對(duì)查詢(xún)請(qǐng)求Ql的內(nèi)容進(jìn)行安全等級(jí)的設(shè)置.

在請(qǐng)求處理模塊中,User通過(guò)將CS返回的錨點(diǎn)信息代替用戶(hù)的真實(shí)位置信息,同時(shí)根據(jù)設(shè)置的安全等級(jí)以及分片規(guī)則對(duì)Ql進(jìn)行分片處理.

查詢(xún)處理模塊主要用于向位置服務(wù)器發(fā)起位置近鄰查詢(xún),同時(shí)對(duì)位置服務(wù)器返回的結(jié)果與自身的真實(shí)位置進(jìn)行計(jì)算和過(guò)濾,得到精確的近鄰查詢(xún)結(jié)果.

CS主要由錨點(diǎn)生成模塊和歷史用戶(hù)信息模塊構(gòu)成,其中錨點(diǎn)生成模塊根據(jù)用戶(hù)請(qǐng)求Qc中的密度中心及區(qū)域半徑η計(jì)算得出最小匿名區(qū)域,在最小匿名區(qū)域內(nèi)進(jìn)行錨點(diǎn)生成算法得到最佳錨點(diǎn)信息返回給User.歷史用戶(hù)信息模塊用于在錨點(diǎn)生成的過(guò)程中提供歷史用戶(hù)的信息.

LSP是為用戶(hù)提供各種LBS服務(wù)的大型位置服務(wù)數(shù)據(jù)庫(kù).它通過(guò)接收User發(fā)送過(guò)來(lái)的請(qǐng)求信息,根據(jù)請(qǐng)求的內(nèi)容在其數(shù)據(jù)庫(kù)中搜索到相應(yīng)的興趣點(diǎn)信息,并將查詢(xún)結(jié)果處理后,返回給User.

3.2 數(shù)據(jù)安全等級(jí)設(shè)置

用戶(hù)可以根據(jù)安全等級(jí)定義[19],即根據(jù)信息價(jià)值來(lái)定義其重要程度.并結(jié)合自身的隱私保護(hù)需求來(lái)對(duì)查詢(xún)請(qǐng)求Ql進(jìn)行安全等級(jí)設(shè)置.例如用戶(hù)的位置信息L和身份信息ID′屬于個(gè)人的敏感信息,如果泄露,會(huì)直接暴露用戶(hù)的隱私,可以將其設(shè)置為高安全等級(jí).用戶(hù)的查詢(xún)內(nèi)容Content屬于關(guān)聯(lián)信息,如果泄露,攻擊者可能通過(guò)查詢(xún)內(nèi)容來(lái)推測(cè)出用戶(hù)的生活習(xí)慣等,可以將其設(shè)置為中安全等級(jí).查詢(xún)Ql中的匿名參數(shù)k和匿名組標(biāo)識(shí)符gid為公共信息,可以將其設(shè)置為低安全等級(jí).如表1所示.

表1 安全等級(jí)定義Table 1 Definition of security level

3.3 查詢(xún)請(qǐng)求分片

客戶(hù)端在用戶(hù)設(shè)置數(shù)據(jù)安全等級(jí)后對(duì)查詢(xún)請(qǐng)求進(jìn)行分片.在分片的過(guò)程中,高安全等級(jí)的內(nèi)容包含用戶(hù)的敏感信息,如果與中安全等級(jí)的關(guān)聯(lián)信息切分在一起會(huì)大大增加用戶(hù)隱私泄露的概率.所以可以將敏感信息與關(guān)聯(lián)信息分別與公共信息切分在一起.同時(shí)將用戶(hù)通過(guò)散列函數(shù)產(chǎn)生的唯一識(shí)別碼ID添加到每一個(gè)分片后的請(qǐng)求片段中用于在位置服務(wù)器端請(qǐng)求重組.

針對(duì)本文中的查詢(xún)請(qǐng)求Ql={ID,L′,Content,k,s,gid},其中ID為用戶(hù)的唯一標(biāo)識(shí)碼,L′為錨點(diǎn)信息,Content為查詢(xún)內(nèi)容,k為匿名參數(shù),s為匿名區(qū)域半徑,gid為該匿名組的標(biāo)識(shí)符.根據(jù)3.2節(jié)進(jìn)行安全等級(jí)設(shè)置后,一種可行的分片方式為Ql1={ID,L′,k},Ql2={ID,s},Ql3={ID,Content,gid}.

3.4 基于歷史用戶(hù)的錨點(diǎn)生成算法

在選取錨點(diǎn)的過(guò)程中,通常采用隨機(jī)選取或者使用匿名組密度中心的方式.為了保證錨點(diǎn)信息的安全性和可信度,本文采用基于歷史用戶(hù)的錨點(diǎn)生成算法來(lái)計(jì)算得到錨點(diǎn)信息.通過(guò)聚類(lèi)算法得到歷史用戶(hù)分布密集的區(qū)域,對(duì)聚類(lèi)結(jié)果的位置進(jìn)行權(quán)重的計(jì)算,選擇權(quán)重高的位置信息作為候選結(jié)果返回給用戶(hù).

定義 1.ε鄰域 對(duì)于xi∈D,D為樣本集(x1,x2,…,xm),則xi的鄰域Nε(xi)為樣本集中與xi距離不大于ε的樣本子集,即

Nε(xi)={xi∈D|distance(xi,xj)≤ε}

(1)

定義 2.核心點(diǎn)與邊界點(diǎn) 對(duì)于任一對(duì)象xi∈D,給定一個(gè)整數(shù)MinPts,若在其ε鄰域中至少有MinPts個(gè)對(duì)象,即|Nε(xi)|≥MinPts,則稱(chēng)xi為核心點(diǎn).若一個(gè)對(duì)象不是核心點(diǎn)但在某個(gè)核心點(diǎn)的ε鄰域中,則稱(chēng)該對(duì)象為邊界點(diǎn).

定義 3.簇與噪聲點(diǎn) 將距離在MinPts內(nèi)的所有核心點(diǎn)連接,這些核心點(diǎn)與隸屬于其ε鄰域內(nèi)的邊界點(diǎn)構(gòu)成一個(gè)簇.不在任何簇內(nèi)的對(duì)象為噪聲點(diǎn).

當(dāng)CS接收到用戶(hù)的請(qǐng)求信息Qc={Ldc,η,ε,MinPts},其中Ldc為匿名組密度中心的位置信息,η為區(qū)域半徑,ε為鄰域半徑,MinPts為鄰域密度閾值,通過(guò)調(diào)用錨點(diǎn)生成模塊產(chǎn)生用戶(hù)所需的錨點(diǎn)信息.在具體的實(shí)現(xiàn)中,CS采用DBSCAN算法[20]對(duì)匿名組的最小匿名區(qū)域進(jìn)行基于歷史用戶(hù)位置信息的聚類(lèi)處理.首先,CS根據(jù)用戶(hù)請(qǐng)求中的Ldc及η計(jì)算出匿名組的最小匿名區(qū)域MinArea.根據(jù)ε以及MinPts在最小匿名區(qū)域MinArea進(jìn)行基于歷史用戶(hù)位置信息的聚類(lèi).對(duì)最小匿名區(qū)域內(nèi)的歷史用戶(hù)位置數(shù)據(jù)點(diǎn)進(jìn)行遍歷分類(lèi),得到核心點(diǎn),邊界點(diǎn)和噪聲點(diǎn).在刪除噪聲點(diǎn)后,將距離在MinPts內(nèi)的核心點(diǎn)連接形成一個(gè)簇,將每個(gè)邊界點(diǎn)指派到一個(gè)與之關(guān)聯(lián)的核心點(diǎn)的簇中.

針對(duì)于實(shí)際路況的聚類(lèi)結(jié)果,對(duì)簇中的道路進(jìn)行選擇,如果該道路只有唯一通路,則不做改變；若存在其他的通路則選取其中唯一通路的一段使其滿(mǎn)足泊松分布.對(duì)選取的道路上的位置進(jìn)行用戶(hù)停留數(shù)X大于XT的概率P(X>XT)計(jì)算,計(jì)算公式如(2)所示,

(2)

所以某個(gè)位置Pi的權(quán)重值I(Pi)如公式(3)所示,

I(Pi)=U·P(X>XT)

(3)

其中U為Pi所在的道路所具有的權(quán)重,如公式(4)所示,

(4)

其中R(vi)為道路頂點(diǎn)vi的訪(fǎng)問(wèn)頻率權(quán)值,degout(vi)為輸出度.

最后CS將權(quán)重值高的位置信息返回給用戶(hù)作為其錨點(diǎn)信息.

在用戶(hù)接收到CS返回的結(jié)果之前,用戶(hù)需要設(shè)定一個(gè)安全距離SD用于表示錨點(diǎn)距離用戶(hù)真實(shí)位置的最短距離.在接收到CS返回結(jié)果后,分別計(jì)算這些錨點(diǎn)與用戶(hù)真實(shí)位置的距離dis,選取其中dis>SD且距離用戶(hù)真實(shí)位置最近的錨點(diǎn)信息.如果所有的dis

3.5 方案流程

基于查詢(xún)分片用戶(hù)協(xié)作的位置隱私保護(hù)方法處理主要分為6個(gè)步驟：匿名組構(gòu)建、獲取錨點(diǎn)信息、請(qǐng)求分片、廣播請(qǐng)求與片段重組、位置近鄰查詢(xún)以及返回結(jié)果和過(guò)濾,如圖2所示.

圖2 基于查詢(xún)分片用戶(hù)協(xié)作的位置隱私保護(hù)方法流程圖Fig.2 Flow chart of location privacy protection method based on query fragment and user collaboration

步驟1.匿名組構(gòu)建 首先,不在任何匿名組內(nèi)的移動(dòng)用戶(hù)rq發(fā)起成立匿名組的請(qǐng)求廣播,然后通過(guò)廣播FROM_GROUP消息來(lái)發(fā)現(xiàn)鄰居節(jié)點(diǎn),其中FROM_GROUP為,gid為匿名組的組編號(hào),id為消息序列,h為廣播跳數(shù).當(dāng)鄰居節(jié)點(diǎn)p接收到請(qǐng)求FROM_GROUP時(shí),首先根據(jù)消息序列id檢查是否為重復(fù)請(qǐng)求,如果為重復(fù)請(qǐng)求,則回復(fù)一個(gè)ACK確認(rèn)消息.否則根據(jù)h值來(lái)進(jìn)行不同的處理.如果h=1,鄰居節(jié)點(diǎn)將自己的信息加入到節(jié)點(diǎn)集合中返回給移動(dòng)用戶(hù)rq.如果h>1,則p將h減1并將FROM_GROUP廣播給其他的鄰居節(jié)點(diǎn),待收集到全部的響應(yīng)后將節(jié)點(diǎn)集合發(fā)送移動(dòng)用戶(hù)rq.如果最終鄰居集合中的用戶(hù)數(shù)量不滿(mǎn)足匿名參數(shù)k,移動(dòng)用戶(hù)p繼續(xù)廣播直到找到k-1個(gè)用戶(hù)為止.最后移動(dòng)用戶(hù)rq根據(jù)設(shè)置的最小查詢(xún)半徑來(lái)調(diào)節(jié)匿名區(qū)域.

步驟2.獲取錨點(diǎn)信息 當(dāng)用戶(hù)rq完成匿名組的建立后,向CS發(fā)送一個(gè)獲取錨點(diǎn)的請(qǐng)求Qc,CS接收到請(qǐng)求后通過(guò)錨點(diǎn)生成模塊生成用戶(hù)所需的錨點(diǎn)信息返回給用戶(hù).

步驟3.請(qǐng)求分片 首先用戶(hù)rq在返回的錨點(diǎn)信息中選取合適的錨點(diǎn)后確定分片數(shù)N,然后在返回的鄰居節(jié)點(diǎn)集合中隨機(jī)選取與分片數(shù)N相同數(shù)量的鄰居節(jié)點(diǎn){p1,p2,…,pN}用于發(fā)送消息片段集合.然后將這些信息及錨點(diǎn)信息一起廣播給匿名組內(nèi)的其他用戶(hù).接著根據(jù)3.2中設(shè)置的數(shù)據(jù)安全等級(jí)以及分片規(guī)則將用戶(hù)的查詢(xún)請(qǐng)求Ql進(jìn)行分片,處理流程如算法1所示.

算法1.數(shù)據(jù)切片與加密

輸入：用戶(hù)的查詢(xún)請(qǐng)求

輸出：加密后的請(qǐng)求片段

1.//請(qǐng)求用戶(hù)rq

2.Determine(N) // 確定分片數(shù)N

3.廣播分片數(shù)N與隨機(jī)選取的用戶(hù){p1,p2,…,pN}

4.自定義切片規(guī)則ShardRules()

5.For(i=0;i

6. SLD(Qli) //設(shè)置請(qǐng)求內(nèi)容的安全等級(jí)

7. {Qli1,Qli2,…,QliN}←ShardRules(SLD(Qli)) //對(duì)查詢(xún)請(qǐng)求進(jìn)行分片

8.Endfor

步驟4.廣播請(qǐng)求與片段重組 當(dāng)用戶(hù)完成查詢(xún)請(qǐng)求內(nèi)容的分片加密以后,將分片后的請(qǐng)求片段分別發(fā)送給隨機(jī)選中的鄰居節(jié)點(diǎn).待選中的鄰居節(jié)點(diǎn)收集完所有用戶(hù)的請(qǐng)求片段后,就將這些消息片段集FS={q1′,q2′,…,qk′}連同切片數(shù)量N一同發(fā)送給位置服務(wù)器.LSP需要設(shè)置一個(gè)等待時(shí)間wait_time,如果在該時(shí)間段內(nèi)收集到全部的請(qǐng)求片段,則根據(jù)每個(gè)用戶(hù)的唯一標(biāo)識(shí)ID進(jìn)行請(qǐng)求片段的重組.如果在該時(shí)間段內(nèi)沒(méi)有收集到全部的請(qǐng)求片段,則丟棄所有收集的請(qǐng)求片段并發(fā)送消息請(qǐng)求用戶(hù)重新發(fā)送.處理流程如算法2所示.

算法2.廣播請(qǐng)求與消息重組

輸入：用戶(hù)的消息片段

輸出：用戶(hù)的完整查詢(xún)請(qǐng)求

1.//鄰居節(jié)點(diǎn)

2.Collection(FS) //收集其他節(jié)點(diǎn)發(fā)送過(guò)來(lái)的請(qǐng)求片段

3.If(FS.num==k)

4.send(FS) //將收集到的請(qǐng)求片段發(fā)送給LSP

5.Endif

6.//LSP

7.If(CollectionTime

8.For(i=0;i

9.If(FS.gid==gid) //請(qǐng)求片段是否來(lái)自同一個(gè)組

10. {Ql1,Ql2,…,Qlk}←Restruct(FS) //進(jìn)行請(qǐng)求片段的重組

11.Endif

12.Endfor

13.Else

14.get_FS_again()

15.Endif

步驟5.位置近鄰查詢(xún) 當(dāng)LSP完成用戶(hù)請(qǐng)求片段重組后,根據(jù)用戶(hù)的錨點(diǎn)信息以及請(qǐng)求內(nèi)容采用位置近鄰查詢(xún)處理算法在數(shù)據(jù)庫(kù)中將最近的n個(gè)興趣點(diǎn)按距離錨點(diǎn)位置大小進(jìn)行排序后加入到數(shù)組W[n]中,然后將用戶(hù)唯一標(biāo)識(shí)對(duì)應(yīng)興趣點(diǎn)返回給用戶(hù)端.如果用戶(hù)收到的數(shù)組中沒(méi)有滿(mǎn)足條件的,那么就擴(kuò)大搜索范圍,在原來(lái)的基礎(chǔ)上繼續(xù)搜索最近的m個(gè)興趣點(diǎn)返回,直到用戶(hù)找到離真實(shí)位置最近的興趣點(diǎn)[21].

步驟6.返回結(jié)果和過(guò)濾 當(dāng)發(fā)送請(qǐng)求的用戶(hù)接收到位置服務(wù)器返回的結(jié)果集后,將對(duì)應(yīng)的結(jié)果集返回給具體的用戶(hù).用戶(hù)對(duì)數(shù)組中的興趣點(diǎn)進(jìn)行比較,當(dāng)滿(mǎn)足dist(pi,wi)+dist(pi,q)≤dist(q,wi+1)條件時(shí),表明在該數(shù)組中第i個(gè)興趣點(diǎn)是離用戶(hù)真實(shí)位置最近的.處理流程如算法3所示.

算法3.返回結(jié)果與過(guò)濾

輸入：LSP返回的查詢(xún)結(jié)果

輸出：距離用戶(hù)最近的興趣點(diǎn)

1.//移動(dòng)用戶(hù)rq

2.根據(jù)用戶(hù)的唯一標(biāo)識(shí)廣播興趣點(diǎn)

3.get(W[n]) //獲取返回的興趣點(diǎn)

4.For(i=0;i

5.If(dist(pi,wi))+dist(pi,q)≤dist(q,wi+1)

6.W[i]為離用戶(hù)真實(shí)位置最近的興趣點(diǎn)

7.Else

8.get_again(W[n]) //重新獲取W[n]

9.Endif

10.Endfor

3.6 安全性分析

本節(jié)主要從用戶(hù)、CS和LSP三部分來(lái)分析基于查詢(xún)分片用戶(hù)協(xié)作的位置隱私保護(hù)方案的安全性.

情況3.用戶(hù)與CS之間的安全性.在本文的模型中,CS主要用于構(gòu)建用戶(hù)查詢(xún)過(guò)程中的錨點(diǎn)信息.用戶(hù)發(fā)送給CS的請(qǐng)求中只包含匿名組密度中心的位置信息、區(qū)域半徑η、鄰域半徑ε和鄰域密度閾值MinPts,請(qǐng)求內(nèi)容不涉及到用戶(hù)的具體隱私信息.即使CS受到攻擊,攻擊者也無(wú)法獲取到用戶(hù)的隱私.

4 實(shí)驗(yàn)及結(jié)果分析

4.1 實(shí)驗(yàn)環(huán)境

本文的算法采用Java實(shí)現(xiàn),在i7 3.60GHz處理器、8G內(nèi)存Windows7的平臺(tái)上運(yùn)行.實(shí)驗(yàn)的數(shù)據(jù)集采用Thomas Brinkhoff路網(wǎng)數(shù)據(jù)生成器[22]生成,它以城市Oldenburg的交通路網(wǎng)作為輸入,生成模擬移動(dòng)用戶(hù)數(shù)據(jù).實(shí)驗(yàn)中使用數(shù)據(jù)的默認(rèn)參數(shù)值如表2所示.

表2 默認(rèn)參數(shù)Table 2 Default parameters

4.2 實(shí)驗(yàn)結(jié)果分析

4.2.1 基于匿名參數(shù)k變化的性能比較

本實(shí)驗(yàn)使用Oldenburg數(shù)據(jù)集評(píng)估匿名成功率、平均響應(yīng)時(shí)間和近鄰查詢(xún)結(jié)果集3個(gè)參數(shù)隨匿名參數(shù)k增加的變化情況,并與Coprivacy[14]系統(tǒng)中的各個(gè)結(jié)果進(jìn)行了對(duì)比.

圖3 匿名參數(shù)k的影響Fig.3 Effect of anonymous parameter k

在其他參數(shù)保持一致的情況下,將本文中的系統(tǒng)與Coprivacy中的方法在匿名參數(shù)k變化的情況下進(jìn)行比較,k數(shù)值范圍為5至25之間.由圖3(a)可知,本文系統(tǒng)和Coprivacy的匿名成功率都隨著k值的增加而有所降低,因?yàn)樵谝苿?dòng)用戶(hù)人數(shù)保持不變的情況下匿名需求k的值增加導(dǎo)致匿名成功率下降.本文模型的匿名成功率高于Coprivacy模型,原因是本文對(duì)最小匿名區(qū)域進(jìn)行了調(diào)節(jié).由圖3(b)可知隨著k值的增加,兩個(gè)系統(tǒng)的平均響應(yīng)時(shí)間都在變大且本文系統(tǒng)的平均響應(yīng)時(shí)間略高于Coprivacy,因?yàn)樵诒疚牡南到y(tǒng)中需要將請(qǐng)求進(jìn)行分片和重組處理.隨著匿名參數(shù)k值的增加,近鄰查詢(xún)結(jié)果集的大小呈現(xiàn)增長(zhǎng)的趨勢(shì),且本文查詢(xún)結(jié)果集相比Coprivacy更小,因?yàn)楸疚牟捎玫姆椒ú恍枰獙⒉樵?xún)結(jié)果與所有結(jié)果進(jìn)行比較,可以就前面的節(jié)點(diǎn)盡快找到最近的節(jié)點(diǎn),所以查詢(xún)效率更高,如圖3(c)所示.

4.2.2 基于移動(dòng)用戶(hù)數(shù)量變化的性能比較

在其他參數(shù)保持一致的情況下,將本文中的系統(tǒng)與Coprivacy中的方法在移動(dòng)用戶(hù)數(shù)量變化的情況下進(jìn)行比較,移動(dòng)用戶(hù)數(shù)量范圍為1000至9000之間.由圖4(a)和圖4(b)可知,本文系統(tǒng)和Coprivacy的平均響應(yīng)時(shí)間和平均通信量都隨著移動(dòng)用戶(hù)的數(shù)量的增加而減少且趨于相近,因?yàn)殡S著移動(dòng)用戶(hù)數(shù)數(shù)量的增加,單位區(qū)域內(nèi)的密度增加,形成匿名組的速度提高以及形成匿名組過(guò)程中所需要的通信量不斷減少.

圖4 移動(dòng)用戶(hù)數(shù)量的影響Fig.4 Effect of the number of mobile users

4.2.3 查詢(xún)半徑和切片數(shù)量對(duì)于系統(tǒng)性能的影響

實(shí)驗(yàn)觀察查詢(xún)半徑r以及用戶(hù)分片數(shù)量N對(duì)于本文系統(tǒng)平均響應(yīng)時(shí)間以及整個(gè)過(guò)程中的平均通信數(shù)量的影響.由圖5(a)和圖5(b)可知,平均響應(yīng)時(shí)間以及平均通信消息數(shù)量都隨著r和N的增加而增大.這是因?yàn)殡S著查詢(xún)半徑的增加,形成的查詢(xún)范圍也就越大,其所需的時(shí)間開(kāi)銷(xiāo)以及通信開(kāi)銷(xiāo)也就越大.而隨著分片數(shù)N的增大,用戶(hù)將請(qǐng)求信息切分成的消息片段也就越多,需要發(fā)送的用戶(hù)也就越多,所以系統(tǒng)所需要處理的時(shí)間開(kāi)銷(xiāo)和通信開(kāi)銷(xiāo)也隨之增加.

圖5 查詢(xún)半徑的影響Fig.5 Effect of query radius

4.2.4 移動(dòng)用戶(hù)數(shù)量和切片數(shù)量對(duì)于系統(tǒng)性能的影響

實(shí)驗(yàn)通過(guò)觀察移動(dòng)用戶(hù)數(shù)量以及用戶(hù)分片數(shù)量對(duì)于本文系統(tǒng)平均響應(yīng)時(shí)間以及整個(gè)過(guò)程中的平均通信數(shù)量的影響.由圖6(a)和圖6(b)可知,隨著系統(tǒng)中移動(dòng)用戶(hù)數(shù)量的不斷增加,用戶(hù)查詢(xún)的平均響應(yīng)時(shí)間和平均通信量都逐漸減少,這是因?yàn)殡S著移動(dòng)用戶(hù)數(shù)量增加,單位區(qū)域內(nèi)的用戶(hù)密度增大,系統(tǒng)形成匿名組的時(shí)間不斷減少,用戶(hù)在形成匿名組過(guò)程中所需要的通信量不斷減少.

圖6 移動(dòng)用戶(hù)數(shù)量的影響Fig.6 Effect of users

5 結(jié)束語(yǔ)

本文提出一種基于查詢(xún)分片的用戶(hù)協(xié)作位置隱私保護(hù)方法,該方法在分布式移動(dòng)點(diǎn)對(duì)點(diǎn)(P2P)的基礎(chǔ)上,通過(guò)將完整的請(qǐng)求信息分片處理,將請(qǐng)求信息根據(jù)用戶(hù)設(shè)置的安全等級(jí)劃分為一系列的請(qǐng)求片段,將請(qǐng)求片段隨機(jī)發(fā)送給匿名組內(nèi)的其他用戶(hù),待收集到匿名組內(nèi)全部用戶(hù)的請(qǐng)求片段以后再發(fā)送給LSP服務(wù)器.服務(wù)器端在k匿名的保護(hù)下無(wú)法準(zhǔn)確區(qū)分具體用戶(hù)的請(qǐng)求信息,從而起到保護(hù)了用戶(hù)的隱私安全的目的.但該方案也存在不足之處,由于需要將用戶(hù)的完整的請(qǐng)求信息進(jìn)行分片和重組處理,增加了該系統(tǒng)的時(shí)間開(kāi)銷(xiāo)以及通信開(kāi)銷(xiāo).所以在未來(lái)的工作中我們將在保護(hù)用戶(hù)隱私信息的前提下,降低系統(tǒng)的整體開(kāi)銷(xiāo)方面進(jìn)行深入的研究.