倪巍偉 , 李靈奇 , 劉家強(qiáng)

1(東南大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院,江蘇 南京 211189)

2(計(jì)算機(jī)網(wǎng)絡(luò)和信息集成教育部重點(diǎn)實(shí)驗(yàn)室(東南大學(xué)),江蘇 南京 211189)

近年來(lái),隨著位置服務(wù)(location based service,簡(jiǎn)稱LBS)的普及和人們對(duì)個(gè)體隱私的日益重視,保護(hù)位置隱私近鄰查詢得到了研究者的持續(xù)關(guān)注[1?7].路網(wǎng)環(huán)境保護(hù)位置隱私近鄰查詢以其貼近真實(shí)生活和路網(wǎng)約束的復(fù)雜,成為保護(hù)位置隱私查詢研究的重要方向.基本思想是:通過(guò)隱匿機(jī)制,將隱藏后查詢者位置及查詢請(qǐng)求提交LBS服務(wù)器,服務(wù)器返回候選POI(point of interest)集合,供查詢者從中甄選目標(biāo)查詢結(jié)果.從隱藏技術(shù)角度,這些方法可分為4類:位置干擾(location obstruction)、空間變換(space transformation)、空間混淆(spatial cloaking)和PIR(private information retrieval)技術(shù).

面向路網(wǎng)的保護(hù)位置隱私近鄰查詢主要采用空間混淆技術(shù)將查詢者位置泛化為混淆區(qū)域(公路子網(wǎng))提交服務(wù)器處理,通過(guò)擴(kuò)大搜索空間返回候選解集,實(shí)現(xiàn)保護(hù)查詢者位置隱私的近鄰查詢.例如:文獻(xiàn)[8,9]利用可信第三方服務(wù)器對(duì)查詢者的真實(shí)位置進(jìn)行匿名,并將匿名區(qū)域及查詢請(qǐng)求提交服務(wù)器,服務(wù)器擴(kuò)展邊界節(jié)點(diǎn)的鄰接區(qū)域查找匿名區(qū)域的k近鄰,這種方法具有保護(hù)強(qiáng)度可調(diào)節(jié)、服務(wù)器端處理可調(diào)控的優(yōu)點(diǎn);文獻(xiàn)[10]提出利用可信匿名服務(wù)器構(gòu)建路網(wǎng)泰森圖,根據(jù)路網(wǎng)泰森單元(network voronoi polygon,簡(jiǎn)稱NVP)包含的路段數(shù),采取不同匿名策略對(duì)用戶真實(shí)位置進(jìn)行匿名保護(hù)的方法;文獻(xiàn)[11]采用PIR技術(shù),提出了基于全局路網(wǎng)泰森圖和KD-Tree的保護(hù)位置隱私近鄰查詢方法.基于 PIR技術(shù)可以提供較高的隱私保護(hù)強(qiáng)度,但服務(wù)器端全局泰森圖和KD-Tree索引構(gòu)建過(guò)程復(fù)雜,存儲(chǔ)消耗大,且k近鄰查詢時(shí)客戶端與服務(wù)器端需要多輪迭代.服務(wù)器端主要采用增量式路網(wǎng)擴(kuò)張法(incremental network expansion,簡(jiǎn)稱INE)和基于泰森圖的近鄰查找法實(shí)現(xiàn)路網(wǎng)近鄰查詢.增量式路網(wǎng)擴(kuò)張法對(duì)查詢者位置所在路網(wǎng)區(qū)域進(jìn)行廣度優(yōu)先搜索,直到區(qū)域中近鄰POI的數(shù)目滿足查詢需求;基于泰森圖的近鄰查詢法利用路網(wǎng)泰森圖查找最近鄰,根據(jù)泰森多邊形(Voronoi polygon)的鄰接多邊形查找其k近鄰.搜索空間的擴(kuò)大和復(fù)雜路網(wǎng)結(jié)構(gòu)限制,加劇了LBS服務(wù)器端查詢開(kāi)銷.已有研究大都通過(guò)在服務(wù)器端構(gòu)建POI集合關(guān)于全局路網(wǎng)的索引結(jié)構(gòu),提高服務(wù)器端處理效率.

已有的基于空間混淆的保護(hù)位置隱私路網(wǎng)近鄰查詢方法主要存在以下問(wèn)題.

(1) 可信第三方服務(wù)器容易成為系統(tǒng)性能和隱私安全的瓶頸.

(2) 路網(wǎng)規(guī)模龐大,使得服務(wù)器端全局路網(wǎng)索引規(guī)模較大,隱私保護(hù)需求導(dǎo)致服務(wù)器端近鄰搜索范圍擴(kuò)大,查找路網(wǎng)索引的代價(jià)激增.

(3) 查詢目標(biāo)POI在路網(wǎng)的位置分布不均衡,服務(wù)器端對(duì)全局路網(wǎng)索引的無(wú)差異使用,導(dǎo)致低頻訪問(wèn)區(qū)域?qū)?yīng)的索引結(jié)構(gòu)利用率低,這部分索引結(jié)構(gòu)增加了全局索引的規(guī)模,降低了路網(wǎng)高頻訪問(wèn)區(qū)域查詢的性能.

針對(duì)上述問(wèn)題,提出了基于Voronoi-R*索引的保護(hù)位置隱私路網(wǎng)k近鄰查詢方法VRS-PNN(Voronoi-R*based privacy-preservingknearest neighbor query over road networks),主要貢獻(xiàn)如下.

(1) 提出了查詢客戶端與LBS服務(wù)器間兩次交互的路網(wǎng)隱私保護(hù)近鄰查詢機(jī)制,實(shí)現(xiàn)不依賴可信第三方的路網(wǎng)位置隱私保護(hù),避免依賴可信第三方導(dǎo)致的隱私泄露威脅.

(2) 提出了基于路網(wǎng)區(qū)域查詢請(qǐng)求頻度的分段式查詢處理策略,為頻繁請(qǐng)求區(qū)域設(shè)計(jì)了Vor-R*樹(shù)局部路網(wǎng)索引結(jié)構(gòu),并定制了查詢策略.在降低服務(wù)器端索引存儲(chǔ)規(guī)模的同時(shí),提升了索引利用率,提高了查詢處理效率.

(3) 實(shí)現(xiàn)了所提保護(hù)位置隱私路網(wǎng)近鄰查詢機(jī)制,并設(shè)計(jì)了實(shí)驗(yàn)驗(yàn)證算法的有效性和性能.

本文第1節(jié)描述問(wèn)題并介紹相關(guān)概念.第2節(jié)介紹VRS-PNN方法的架構(gòu)和流程.第3節(jié)介紹VRS-PNN方法的查詢客戶端處理方法.第4節(jié)介紹VRS-PNN方法服務(wù)器端查詢處理過(guò)程.第5節(jié)對(duì)VRS-PNN方法的性能進(jìn)行分析.第6節(jié)進(jìn)行實(shí)驗(yàn)分析.最后總結(jié)全文,并展望下一步工作.

1 問(wèn)題描述及相關(guān)概念

1.1 問(wèn)題描述

路網(wǎng)環(huán)境保護(hù)位置隱私近鄰查詢的關(guān)鍵問(wèn)題表現(xiàn)在兩個(gè)方面:查詢者/發(fā)起者位置隱私保護(hù)效果以及隱私保護(hù)近鄰查詢處理的效率.

目前,已有研究主要采用空間混淆技術(shù),通過(guò)可信匿名服務(wù)器對(duì)查詢用戶的位置進(jìn)行匿名,并將匿名區(qū)域發(fā)送LBS服務(wù)器,可信匿名服務(wù)器接收LBS服務(wù)器返回的候選集,并將結(jié)果反饋查詢者.對(duì)可信匿名服務(wù)器的依賴,源于查詢客戶端不掌握路網(wǎng)信息,即便客戶端獲取LBS服務(wù)器反饋的包含真實(shí)查詢目標(biāo)的候選POI集合,也無(wú)法采用非路網(wǎng)環(huán)境直接計(jì)算查詢者位置到各候選POI直線距離的方法甄別目標(biāo)查詢結(jié)果.然而可信匿名服務(wù)器難以尋找,且匿名服務(wù)器容易成為查詢性能和隱私安全瓶頸.

在近鄰查詢處理方面,路網(wǎng)結(jié)構(gòu)的復(fù)雜性和位置隱私保護(hù)需求使得LBS服務(wù)器端處理代價(jià)較大,在服務(wù)器端構(gòu)造索引完成近鄰查詢是常用的方法,已有研究主要采用構(gòu)造全局索引的方法,LBS服務(wù)器端預(yù)先計(jì)算并存儲(chǔ)整個(gè)路網(wǎng)區(qū)域POI的索引,LBS服務(wù)器接收到查詢請(qǐng)求時(shí),通過(guò)查找索引完成查詢.然而整個(gè)路網(wǎng)區(qū)域POI索引規(guī)模較大,且索引的構(gòu)造未考慮查詢目標(biāo)在路網(wǎng)的實(shí)際分布,索引利用率低,導(dǎo)致LBS服務(wù)器端近鄰查詢效率方面的缺陷.

1.2 算法思想

針對(duì)前述路網(wǎng)環(huán)境位置隱私保護(hù)與查詢處理依賴可信第三方存在的缺陷,考慮設(shè)計(jì)空間混淆以及查詢處理與反饋機(jī)制,實(shí)現(xiàn)無(wú)需可信第三方介入的位置隱私保護(hù)和路網(wǎng)k近鄰查詢.針對(duì)LBS服務(wù)器端對(duì)全局索引結(jié)構(gòu)無(wú)差異利用導(dǎo)致的查詢處理效率低的問(wèn)題,將服務(wù)器端全局路網(wǎng)劃分為一組基本單元區(qū)域,設(shè)計(jì)區(qū)域局部索引結(jié)構(gòu),實(shí)現(xiàn)LBS服務(wù)器端兼顧區(qū)域查詢頻度的分段式查詢處理,提高查詢處理效率.

基本思路:查詢客戶端向LBS服務(wù)器發(fā)送區(qū)域路網(wǎng)查詢請(qǐng)求,根據(jù)LBS服務(wù)器返回結(jié)果對(duì)查詢者所在路段的節(jié)點(diǎn)進(jìn)行空間混淆,以保護(hù)查詢者位置隱私.具體方法是將查詢者所在路段的節(jié)點(diǎn)作為目標(biāo)對(duì)象進(jìn)行l(wèi)-路段多樣性匿名[12],生成包含查詢者所在路段兩端節(jié)點(diǎn)的一組路段節(jié)點(diǎn)序列.

LBS服務(wù)器根據(jù)查詢客戶端提交的路段節(jié)點(diǎn)序列中節(jié)點(diǎn)所在區(qū)域選擇不同的查詢策略:對(duì)頻繁請(qǐng)求的路網(wǎng)區(qū)域,設(shè)計(jì)Vor-R*索引結(jié)構(gòu),實(shí)現(xiàn)基于Vor-R*局部索引的快速近鄰查找;對(duì)非頻繁請(qǐng)求區(qū)域,采用常規(guī)INE方法查找近鄰,解決全局索引規(guī)模大以及索引利用率低帶來(lái)的查詢效率低的缺陷.

1.3 相關(guān)概念

本文采用超圖路網(wǎng)劃分法[13]將LBS服務(wù)器端的路網(wǎng)區(qū)域劃分為若干個(gè)基本單元.每個(gè)基本單元設(shè)置命中率,命中率隨查詢者對(duì)基本單元的請(qǐng)求次數(shù)更新.敘述方便起見(jiàn),引入下述定義.

定義1(基本單元).服務(wù)器端采用超圖路網(wǎng)劃分法將路網(wǎng)劃分為n個(gè)單元區(qū)域,即n個(gè)基本單元,單元區(qū)域內(nèi)的所有POI構(gòu)成該基本單元的POI集合.

定義2(基本單元命中次數(shù)).若查詢者提交LBS服務(wù)器的匿名路網(wǎng)區(qū)域落在某基本單元區(qū)域內(nèi),該基本單元的命中次數(shù)加1.

定義3(基本單元命中率).給定時(shí)間內(nèi),基本單元的命中率為該段時(shí)間基本單元的命中次數(shù)與LBS服務(wù)器接受查詢請(qǐng)求總次數(shù)的比值.

定義 4(路網(wǎng)泰森單元)[14].某基本單元的POI集合為{P1,P2,…,Pm},Pi的路網(wǎng)Voronoi單元的定義如下:NVP(Pi)={q|dist(q,Pi)

定義5(基本單元的路網(wǎng)泰森單元集(networkvoronoidiagram,簡(jiǎn)稱NVD))[14].某基本單元的POI集合為{P1,P2,…,Pm},該基本單元的路網(wǎng)泰森單元集

定義6(鄰接NVP[14]).對(duì)P1,P2兩個(gè)POI,若NVP(P1)與NVP(P2)存在相同的邊界點(diǎn),則稱NVP(P1)與NVP(P2)鄰接,P1與P2互為1近鄰.

2 VRS-PNN算法處理流程

VRS-PNN算法查詢處理流程如圖1所示,步驟如下.

(1) 查詢者向LBS服務(wù)器發(fā)送包含其位置的匿名區(qū)域及參數(shù)m(LBS需返回的最小路段數(shù));

(2) LBS服務(wù)器查找匿名區(qū)域所在的基本單元(若匿名區(qū)域與多個(gè)基本單元存在交集,選取與匿名區(qū)域重疊面積最大的基本單元),將該基本單元的命中次數(shù)加1(匿名區(qū)域通常遠(yuǎn)小于基本單元,即便匿名區(qū)域覆蓋超過(guò)一個(gè)基本單元,也可以進(jìn)行類似處理,更新相關(guān)基本單元命中數(shù));

(3) LBS服務(wù)器查找匿名區(qū)域包含的所有路段,生成并返回路段集合Segs(如果路段數(shù)小于m,沿路網(wǎng)邊界節(jié)點(diǎn)擴(kuò)展,直到路段數(shù)達(dá)到m);

(4) 查詢者從Segs中選取l個(gè)路段的節(jié)點(diǎn)Pi(i=1,2,…,l),使得查詢者所在路段滿足l-路段多樣性[12](保證查詢者所在路段被推斷的可能性低于1/l),將查詢請(qǐng)求序列Q({P1,P2,…,Pl},k)提交LBS服務(wù)器;

(5) LBS服務(wù)器接收查詢序列Q,分析Q中路段節(jié)點(diǎn)所在的基本單元,對(duì)頻繁請(qǐng)求單元,利用預(yù)先構(gòu)建的Vor-R*索引,查詢計(jì)算路段節(jié)點(diǎn)的近鄰POI集合;否則,使用路網(wǎng)增量擴(kuò)張查找方法查詢相應(yīng)路段節(jié)點(diǎn)的近鄰POI集合;

(6) 將Q的近鄰查詢結(jié)果返回查詢客戶端;

(7) 客戶端根據(jù)查詢者真實(shí)位置篩選準(zhǔn)確路網(wǎng)k近鄰.

Fig.1 Querying process圖1 處理流程

3 VRS-PNN算法客戶端處理方法

不依賴可信匿名服務(wù)器進(jìn)行查詢者位置隱私保護(hù)的難點(diǎn)在于查詢客戶端不掌握查詢者所在區(qū)域的路網(wǎng)分布信息,而路網(wǎng)信息存儲(chǔ)在LBS服務(wù)器端,因此查詢者需要從服務(wù)器端獲取局部路網(wǎng)信息,以便完成自身位置的保護(hù).

采取查詢客戶端向LBS服務(wù)器提交兩次查詢請(qǐng)求的方式完成保護(hù)位置隱私近鄰查詢.

· 第1階段:客戶端向LBS服務(wù)器提交匿名區(qū)域{AR,m},獲取局部路網(wǎng)信息,其中,AR為客戶端生成的查詢者所在匿名區(qū)域,m為路段數(shù),LBS服務(wù)器查詢AR覆蓋的路段.若匿名區(qū)域AR內(nèi)路段數(shù)不小于m,將AR內(nèi)的路段信息返回客戶端;否則,從匿名區(qū)域的邊界節(jié)點(diǎn)進(jìn)行路網(wǎng)擴(kuò)張查詢直到獲取路段數(shù)大于m,將擴(kuò)充后的路段信息返回查詢客戶端.

· 第2階段:客戶端根據(jù)LBS服務(wù)器反饋的路段生成包含查詢者所在路段節(jié)點(diǎn),且滿足l-路段多樣性的匿名查詢序列,并將查詢序列及近鄰數(shù)k提交LBS服務(wù)器.

第1階段:隨機(jī)生成的匿名區(qū)域如圖2所示,Pu為用戶真實(shí)位置,通過(guò)兩個(gè)隨機(jī)數(shù)r1,r2確定正方形區(qū)域的左下端點(diǎn)P1和右上端點(diǎn)P2,正方形匿名區(qū)域的大小需滿足查詢者對(duì)位置匿名強(qiáng)度的要求(通過(guò)參數(shù)R設(shè)置).

Fig.2 Anonymized area at client side圖2 客戶端匿名區(qū)域

第2階段:客戶端收到LBS服務(wù)器返回的路段{seg1,seg2,…segm},將其真實(shí)位置所在路段的兩個(gè)端點(diǎn)加入待查詢序列Query中,再隨機(jī)選取l-2個(gè)路段節(jié)點(diǎn)加入Query中,生成查詢者所在路段滿足l-路段多樣性的匿名查詢序列,具體見(jiàn)算法1.

算法1.用戶位置隱匿算法.

輸入:路段信息{seg1,seg2,…segm},l;

輸出:查詢序列Query{P1,P2,…,Pl}.

圖3為查詢客戶端根據(jù)服務(wù)器返回的區(qū)域路網(wǎng)信息生成的查詢序列示意,矩形ABCD為客戶端向服務(wù)器端發(fā)送的匿名區(qū)域,Pu為查詢者真實(shí)位置,{ni|i=1,…,7}為客戶端生成的查詢序列,n1和n2為Pu所在路段的兩個(gè)端點(diǎn),ni(3≤i≤7)為客戶端在區(qū)域路網(wǎng)中隨機(jī)選取的節(jié)點(diǎn).

Fig.3 Node sequence illustration with l-diversity (l=7)圖3 l-路段多樣性節(jié)點(diǎn)序列生成示意圖(l=7)

性質(zhì)1.查詢者位置Pu所在路段節(jié)點(diǎn)n1和n2包含于向LBS服務(wù)器發(fā)送的匿名查詢序列中,則LBS服務(wù)器返回的候選結(jié)果集S一定包含Pu的路網(wǎng)k近鄰POI.

證明:設(shè)n1的路網(wǎng)k近鄰POI集為M1,n2的路網(wǎng)k近鄰POI集為M2;將Pu的路網(wǎng)k近鄰POI集合分為兩個(gè)子集S1和S2,S1為途經(jīng)節(jié)點(diǎn)n1的路網(wǎng)近鄰POI集,S2為途經(jīng)n2的路網(wǎng)近鄰POI集.假設(shè)存在Qk,Qk為Pu的第k近鄰,滿足Qk?M1且Qk?M2.若Qk∈S1,設(shè)為M1∪M2中離Pu第k近的POI,則有

查詢客戶端獲取LBS服務(wù)器返回的候選結(jié)果集后,只需將其所在路段節(jié)點(diǎn)的k近鄰集合作為候選結(jié)果集進(jìn)行篩選計(jì)算.由于客戶端缺乏路網(wǎng)信息,無(wú)法計(jì)算其真實(shí)位置到各候選POI的路網(wǎng)距離,因此LBS服務(wù)器返回的查詢序列Q中添加每個(gè)查詢位置到其各個(gè)近鄰POI路徑上的第一個(gè)路段節(jié)點(diǎn)信息,以便客戶端計(jì)算查詢者位置距離候選POI的路網(wǎng)距離(具體見(jiàn)第4.3節(jié)),客戶端根據(jù)LBS服務(wù)器返回的信息計(jì)算查詢者的真實(shí)k近鄰POI.客戶端篩選查詢結(jié)果的流程見(jiàn)算法2.

算法2.k近鄰結(jié)果集篩選算法.

輸入:用戶位置Pu所在路段的兩個(gè)節(jié)點(diǎn)n1和n2的kNN結(jié)果集M1和M2;

輸出:用戶真實(shí)位置的k近鄰結(jié)果集RS.

4 VRS-PNN服務(wù)器端處理方法

保護(hù)位置隱私路網(wǎng)近鄰查詢中,LBS服務(wù)器處理代價(jià)大的重要原因是保護(hù)查詢者位置隱私導(dǎo)致查詢范圍擴(kuò)大.考慮根據(jù)各基本單元的命中率,對(duì)不同的基本單元采取不同的查詢策略:對(duì)命中率較高的基本單元,構(gòu)建基本單元泰森圖,并基于R*樹(shù)[15]構(gòu)建基本單元內(nèi)POI關(guān)于泰森圖的索引結(jié)構(gòu)Vor-R*.由于R*樹(shù)在插入節(jié)點(diǎn)時(shí)采取組合策略,使用多個(gè)參數(shù)作為選擇標(biāo)準(zhǔn),而R樹(shù)在插入節(jié)點(diǎn)時(shí)僅考慮面積參數(shù);在分割節(jié)點(diǎn)的過(guò)程中,R*樹(shù)采取拓?fù)浞指畈呗曰谥荛L(zhǎng)選擇分割軸,最小化空間重疊大小;因此,R*樹(shù)的空間重疊度相比于R樹(shù)更小,查詢時(shí)效率優(yōu)于R樹(shù),可以有效提升頻繁查詢區(qū)域的處理效率.對(duì)命中率較低的基本單元,采用INE方法獲取查詢序列的k近鄰.

4.1 Vor-R*索引結(jié)構(gòu)

以基本單元內(nèi)的所有POI為對(duì)象生成基本單元的路網(wǎng)Voronoi圖,并對(duì)基本單元邊界處的NVP予以標(biāo)記,以圖4的路網(wǎng)基本單元為例,{P1,P2,P3,P4,P5}為該單元的POI集合.生成的NVD如圖5所示,與計(jì)算歐氏距離產(chǎn)生的Voronoi圖不同,路網(wǎng)中生成的NVP邊界圖形存在凹多邊形.

Fig.4 Road network圖4 路網(wǎng)圖

Fig.5 Illustration of NVD圖5 路網(wǎng)泰森單元集示意

NVP由邊界點(diǎn)所圍成的區(qū)域構(gòu)成,表1為NVP(Pi)的邊界點(diǎn)及鄰接POI信息.相鄰的兩個(gè)NVP可能存在重復(fù)區(qū)域,如圖5中的P1和P2:P1的NVP邊界為{n1,n2,b3,b2,b1,A},P2的NVP的邊界為{n1,n2,b2,b3,b4,b5,b6},兩者存在交集區(qū)域△b2n2b3,當(dāng)查詢序列Q中的節(jié)點(diǎn)位于n2b2或者n2b3時(shí),存在兩個(gè)最近鄰位置P1和P2.

Table 1 POI information表1 POI信息

LBS服務(wù)器對(duì)各個(gè)基本單元內(nèi)的POI進(jìn)行編號(hào),將編號(hào)及其位置信息存儲(chǔ)到POI表中(見(jiàn)表2).在構(gòu)建基本單元NVD的過(guò)程中,將所有NVP信息保存到NVD表中(見(jiàn)表3),表中存儲(chǔ)POI編號(hào)、NVP(Pi)邊界點(diǎn)、NVP(Pi)內(nèi)部路段節(jié)點(diǎn)、鄰接POI信息,每個(gè)POI的NVP邊界點(diǎn)按順時(shí)針順序存儲(chǔ).

Table 2 POI table表2 POI表

Table 3 NVD table表3 NVD表

以基本單元內(nèi)POI的NVP的最小外接矩形為葉子節(jié)點(diǎn)構(gòu)建R*樹(shù).Vor-R*樹(shù)的構(gòu)造過(guò)程如下.

(1) 構(gòu)建基本單元內(nèi)所有POI的路網(wǎng)泰森圖;

(2) 創(chuàng)建空R*樹(shù);

(3) 對(duì)所有的NVP,執(zhí)行下列操作.

①在R*樹(shù)中查找待插入對(duì)象NVPi的合適的葉子節(jié)點(diǎn)Leaf;

② 如果葉子節(jié)點(diǎn)Leaf存在足夠空間,將NVPi添加至節(jié)點(diǎn)Leaf,轉(zhuǎn)步驟③;否則分裂此節(jié)點(diǎn),并對(duì)Leaf和分裂后的新節(jié)點(diǎn)執(zhí)行操作步驟③、步驟④;

③根據(jù)節(jié)點(diǎn)向上調(diào)整樹(shù)的結(jié)構(gòu);

④ 若根節(jié)點(diǎn)分裂,插入新的根節(jié)點(diǎn),分裂后的兩個(gè)節(jié)點(diǎn)分別為樹(shù)的孩子節(jié)點(diǎn).

對(duì)圖6所示區(qū)域劃分,Vor-R*索引樹(shù)結(jié)構(gòu)如圖7所示,中間節(jié)點(diǎn)存儲(chǔ)所有子節(jié)點(diǎn)矩形的輪廓最小外接矩形,葉子節(jié)點(diǎn)存儲(chǔ)最小外接矩形內(nèi)部NVP對(duì)應(yīng)的POI編號(hào),并指向NVD表POI編號(hào)所在位置.由于R*樹(shù)的節(jié)點(diǎn)之間區(qū)域重疊區(qū)域較小,服務(wù)器端查詢路段節(jié)點(diǎn)最近鄰時(shí)可以避免搜索多余的子樹(shù),能夠快速獲得路段節(jié)點(diǎn)所在NVP的邊界節(jié)點(diǎn)信息,根據(jù)這些信息,可以計(jì)算判定目標(biāo)位置的準(zhǔn)確所在NVP.

Fig.6 Region partition illustration of R* tree圖6 路網(wǎng)泰森圖R*區(qū)域劃分示意圖

Fig.7 Structure illustration of index Vor-R*圖7 Vor-R*索引結(jié)構(gòu)圖

4.2 服務(wù)器端局部Vor-R*索引更新

VRS-PNN算法采用LBS服務(wù)器,根據(jù)查詢請(qǐng)求所在基本單元命中率進(jìn)行個(gè)性化查找的分段處理策略,因此需要?jiǎng)討B(tài)維護(hù)各基本單元的命中率,以便階段性進(jìn)行基本單元局部Vor-R*索引的更新.

假設(shè)某時(shí)間段內(nèi),LBS服務(wù)器接收查詢請(qǐng)求總數(shù)為Amt,啟動(dòng)索引更新的查詢請(qǐng)求數(shù)閾值為A0,頻繁請(qǐng)求基本單元的命中率閾值為β.若基本單元的命中率不小于β,該基本單元被標(biāo)注為頻繁請(qǐng)求單元;否則,該基本單元為非頻繁請(qǐng)求單元,為每個(gè)基本單元設(shè)置信號(hào)量flag,標(biāo)注基本單元是否已建立Vor-R*索引.

LBS服務(wù)器端索引構(gòu)建策略如下.

(1) LBS服務(wù)器接收客戶端發(fā)送的匿名區(qū)域AR,并查找AR所在基本單元Reg0(或查找與AR重疊面積最大的基本單元),將Reg0的命中次數(shù)加1,同時(shí),Amt=Amt+1;

(2) 若Amt

(3) 將Amt和所有基本單元的命中次數(shù)均設(shè)為0,返回步驟(1).

LBS服務(wù)器階段性評(píng)估最近階段客戶端查詢請(qǐng)求涉及基本單元的分布頻度,創(chuàng)建或刪除相應(yīng)基本單元的Vor-R*索引,實(shí)現(xiàn)路網(wǎng)區(qū)域訪問(wèn)頻度分布與查詢處理策略的動(dòng)態(tài)匹配.同時(shí),通過(guò)合理的設(shè)置基本單元的Vor-R*索引結(jié)構(gòu)刪除策略,提高服務(wù)器端索引利用率,降低索引存儲(chǔ)與維護(hù)的代價(jià).

4.3 基于查詢序列的近鄰查詢

服務(wù)器端接收到客戶端的查詢序列后,分別查詢l個(gè)路段節(jié)點(diǎn)的最近鄰.對(duì)每個(gè)路段節(jié)點(diǎn),若其位于非頻繁請(qǐng)求基本單元,使用INE方法查詢其近鄰;否則,基于Vor-R*樹(shù)查詢其近鄰.

本節(jié)主要討論落在頻繁請(qǐng)求基本單元中的路段節(jié)點(diǎn)的近鄰查詢過(guò)程.查詢Vor-R*樹(shù)可以得到路段節(jié)點(diǎn)所在的NVP最小外接矩形,由于NVP的最小外接矩形存在重疊區(qū)域,所以搜索樹(shù)結(jié)構(gòu)可能會(huì)得到多個(gè)最近鄰POI,而每個(gè)POI的NVP的邊界點(diǎn)構(gòu)成(凹/凸)多邊形,將NVP內(nèi)部的路段封裝起來(lái),若路段節(jié)點(diǎn)在多邊形內(nèi)部,則此多邊形內(nèi)部的POI為其最近鄰.主要流程見(jiàn)算法3.

算法3.最近鄰查詢算法.

輸入:路段節(jié)點(diǎn)位置Pu(x,y),Vor-R*樹(shù);

輸出:最近鄰POI結(jié)果集R.

利用一個(gè)點(diǎn)的k近鄰一定存在于其k?1近鄰的鄰接POI集合的性質(zhì)[16],計(jì)算路段節(jié)點(diǎn)的k近鄰.LBS服務(wù)器查找Vor-R*樹(shù)獲得查詢序列中路段節(jié)點(diǎn)最近鄰后,根據(jù)上述性質(zhì)計(jì)算路段節(jié)點(diǎn)的候選k近鄰集合.考慮路段節(jié)點(diǎn)的k近鄰可能位于不同基本單元.為了計(jì)算結(jié)果的準(zhǔn)確性,在計(jì)算k近鄰候選集時(shí)增加對(duì)NVP是否位于基本單元邊界的判定.計(jì)算路段節(jié)點(diǎn)的k近鄰候選集流程如下.

(1) 利用Vor-R*查詢路段節(jié)點(diǎn)P的最近鄰集合Si(i=1),將Si(i=1)添加至候選集temp_list中;

(2) 對(duì)Si中所有的POI,執(zhí)行步驟(3)、步驟(4);

(3) 若POI所在NVP已被標(biāo)記為邊界NVP,使用INE方法向另一個(gè)基本單元擴(kuò)張查找此POI的(k?i)近鄰集合S′,并保存P到其近鄰POI的最短路徑距離,將S′添加至候選集temp_list;

(4) 若POI所在的NVP未被標(biāo)記為邊界NVP,則將此POI的鄰接POI(已存在于temp_list的POI不計(jì)入內(nèi))分別添加至temp_list和Si+1中;

(5) 如果i

在篩選候選集、計(jì)算路段節(jié)點(diǎn)準(zhǔn)確k近鄰的過(guò)程中,需要計(jì)算路段節(jié)點(diǎn)到各個(gè)候選POI的最短路徑距離,然后選取最近的k個(gè)POI作為路段節(jié)點(diǎn)的準(zhǔn)確k近鄰.在計(jì)算路段節(jié)點(diǎn)到候選POI的距離時(shí),LBS服務(wù)器預(yù)計(jì)算NVP邊界節(jié)點(diǎn)間的距離,以降低路段節(jié)點(diǎn)到POI的距離計(jì)算量.

在查詢最近鄰POI的基礎(chǔ)上,進(jìn)一步查找某個(gè)路段節(jié)點(diǎn)k近鄰POI的主要流程見(jiàn)算法4.

算法4.KNN查詢算法.

輸入:路段節(jié)點(diǎn)Pu(x,y);

輸出:k近鄰POI結(jié)果集RS.

服務(wù)器向客戶端返回l×k個(gè)POI位置信息,而客戶端提交的l個(gè)位置在同一匿名區(qū)域,它們的k近鄰可能存在交集.為了避免重復(fù)的近鄰POI信息傳輸,使用第4.1節(jié)所定義的POI表結(jié)構(gòu).服務(wù)器端返回結(jié)果時(shí),返回各目標(biāo)位置近鄰的Id序列以及Id序列對(duì)應(yīng)的POI信息;同時(shí),服務(wù)器端在計(jì)算路段節(jié)點(diǎn)的k近鄰POI時(shí),保存節(jié)點(diǎn)到各近鄰POI的最短路徑距離以及到近鄰POI最短路徑所經(jīng)過(guò)的第1個(gè)路段節(jié)點(diǎn)(便于客戶端計(jì)算準(zhǔn)確近鄰),與k近鄰POI查詢結(jié)果一起反饋給用戶.圖8為某基本單元的部分路網(wǎng)結(jié)構(gòu),n0為客戶端所提交的某個(gè)路段節(jié)點(diǎn),A為n0的一個(gè)近鄰POI,n0到A的最短路徑為n0n1n2A,則n1為n0到路網(wǎng)近鄰點(diǎn)A路經(jīng)的第1個(gè)節(jié)點(diǎn).

Fig.8 Road distance illustration between query location and its nearer POI圖8 查詢點(diǎn)與近鄰POI的路網(wǎng)最短路徑

表4和表5為服務(wù)器反饋查詢客戶端的查詢結(jié)果.表4中,每個(gè)路段節(jié)點(diǎn)的路網(wǎng)k近鄰序列由k個(gè)三元組組成,元素分別為近鄰POI、MinDist為路段節(jié)點(diǎn)到此POI的最短路徑距離、FirstNode為路段節(jié)點(diǎn)到此POI的最短路徑中經(jīng)過(guò)的第1個(gè)路段節(jié)點(diǎn).表5為表4中各POI和路段節(jié)點(diǎn)與實(shí)際位置坐標(biāo)的映射.

Table 4 k nearest neighbors of l road nodes in Q (l=4,k=3)表4 Q 中l(wèi) 個(gè)路段節(jié)點(diǎn)的路網(wǎng)k 近鄰集(l=4,k=3)

Table 5 Location of POIs and road nodes (l=4,k=3)表5 POI和路段節(jié)點(diǎn)的坐標(biāo)映射表(l=4,k=3)

5 算法性能分析

本節(jié)從LBS服務(wù)器端和查詢客戶端計(jì)算復(fù)雜度的角度,分析VRS-PNN方法的效率.對(duì)LBS服務(wù)器端以單個(gè)路段節(jié)點(diǎn)為查詢對(duì)象,分別分析頻繁請(qǐng)求基本單元和非頻繁請(qǐng)求基本單元的處理效率.

對(duì)于頻繁請(qǐng)求的基本單元,因其索引Vor-R*是預(yù)構(gòu)建好的,每次查詢只需查找索引,基于Vor-R*查詢路網(wǎng)最近鄰的時(shí)間復(fù)雜度為O(logn),n為基本單元內(nèi)的POI數(shù)目.查詢路網(wǎng)k近鄰的計(jì)算量主要消耗在計(jì)算路段端點(diǎn)到候選POI的最短路徑距離,如第4.3節(jié)所述,通過(guò)在LBS服務(wù)器預(yù)計(jì)算NVP各邊界節(jié)點(diǎn)之間的距離,計(jì)算路段節(jié)點(diǎn)到其候選POI的最短距離時(shí)只需進(jìn)行簡(jiǎn)單的求和、比較計(jì)算.考慮路網(wǎng)實(shí)際情況,每個(gè)NVP的邊界節(jié)點(diǎn)個(gè)數(shù)為常量,所以計(jì)算路段節(jié)點(diǎn)到候選POI最短路徑距離的時(shí)間復(fù)雜度為O(C).文獻(xiàn)[16]提出,每個(gè)NVP的鄰接NVP的數(shù)目平均不超過(guò)6.根據(jù)此性質(zhì),路段端點(diǎn)的k近鄰候選結(jié)果集平均大小為6k.本文采用快速排序計(jì)算準(zhǔn)確路網(wǎng)k近鄰,時(shí)間復(fù)雜度為O(6klogk).綜上,計(jì)算每個(gè)路段端點(diǎn)路網(wǎng)k近鄰的復(fù)雜度為O(logn+kC+6klogk),即O(logn+klogk).上述過(guò)程為路段節(jié)點(diǎn)的真實(shí)k近鄰全都位于路段節(jié)點(diǎn)所在基本單元的情形;若路段節(jié)點(diǎn)的部分真實(shí)k近鄰位于其他基本單元,最壞情況為路段節(jié)點(diǎn)所在的NVP為邊界NVP,此時(shí)的計(jì)算量包括查詢一次Vor-R*樹(shù)和利用INE方法查找單個(gè)路段節(jié)點(diǎn)k近鄰.

對(duì)非頻繁請(qǐng)求基本單元,采用INE方法查詢k近鄰的時(shí)間受POI分布密集程度影響[17](用|N|/|S|描述分布密度,|N|為基本單元內(nèi)POI的個(gè)數(shù),|S|對(duì)應(yīng)基本單元內(nèi)路段數(shù)).文獻(xiàn)[18]驗(yàn)證了POI分布越密集,INE策略越高效:若|N|/|S|≥1,查詢復(fù)雜度為O(k);否則,INE方法效率較低,查詢復(fù)雜度為O(k*|S|/|N|).

上述復(fù)雜度分析為單個(gè)路段節(jié)點(diǎn)的近鄰查詢復(fù)雜度,VRS-PNN服務(wù)器端需要對(duì)查詢序列進(jìn)行處理,總體時(shí)間復(fù)雜度受各個(gè)路段節(jié)點(diǎn)所處基本單元影響.假設(shè)頻繁請(qǐng)求基本單元的路段節(jié)點(diǎn)近鄰查詢復(fù)雜度為O1,非頻繁請(qǐng)求單元的路段節(jié)點(diǎn)近鄰查詢復(fù)雜度為O2,處理查詢序列的最壞時(shí)間復(fù)雜度為l*max(O1,O2).

客戶端計(jì)算主要集中在從候選集篩選準(zhǔn)確路網(wǎng)k近鄰的過(guò)程,由于客戶端接收查詢序列Q的k近鄰候選POI集的同時(shí),也獲取Q中每個(gè)路段節(jié)點(diǎn)到其所有k近鄰POI的最短路徑經(jīng)過(guò)的第一個(gè)路段節(jié)點(diǎn),根據(jù)算法2,計(jì)算時(shí)間主要消耗在快速排序過(guò)程,時(shí)間復(fù)雜度為O(klogk).整個(gè)查詢過(guò)程,查詢客戶端和LBS服務(wù)器間發(fā)生兩輪通信.首先,客戶端向LBS服務(wù)器發(fā)送區(qū)域路網(wǎng)信息請(qǐng)求過(guò)程中,通信代價(jià)為O(1),LBS服務(wù)器向查詢客戶端反饋路網(wǎng)信息的通信消耗為O(m)(m為路段數(shù)量參數(shù));隨后,查詢客戶端向LBS服務(wù)器發(fā)送查詢序列的通信代價(jià)為O(l)(l為查詢序列大小),LBS服務(wù)器將候選結(jié)果返回給客戶端的通信代價(jià)為O(lk).綜上,VRS-PNN方法中查詢客戶端和LBS服務(wù)器間的總通信代價(jià)為O(lk+m).

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

本節(jié)對(duì)VRS-PNN的效率進(jìn)行實(shí)驗(yàn)分析,實(shí)驗(yàn)數(shù)據(jù)采用美國(guó)加利福尼亞的路網(wǎng)數(shù)據(jù)(路段節(jié)點(diǎn)21 048個(gè),覆蓋21 689條道路,http://www.cs.utah.edu/～lifeifei/SpatialDataset.htm),選取包括2 024個(gè)路段節(jié)點(diǎn)、5 266條道路的路網(wǎng)子區(qū)域(內(nèi)含1 000個(gè)POI).實(shí)驗(yàn)環(huán)境配置如下:Windows7系統(tǒng),3.4GHz Intel Core i7處理器,內(nèi)存容量8GB.

首先,設(shè)計(jì)實(shí)驗(yàn)對(duì)本文提出的Vor-R*樹(shù)索引結(jié)構(gòu)與已有基于路網(wǎng)泰森圖的R樹(shù)索引的查詢性能進(jìn)行對(duì)比分析,構(gòu)建基于基本單元的Vor-R*樹(shù)索引與Vor-R樹(shù)索引,分別基于兩種索引查詢目標(biāo)POI的最近鄰,對(duì)其進(jìn)行性能比較.由于R*樹(shù)相比于R樹(shù)的空間覆蓋和重疊度均比較小,其查詢效率更高.如圖9所示,伴隨著基本單元POI數(shù)目的變化,Vor-R*樹(shù)索引查詢性能始終優(yōu)于Vor-R樹(shù)索引.

Fig.9 Index effectiveness comparsion between Vor-R* and Vor-R圖9 Vor-R*與Vor-R索引性能比較圖

進(jìn)一步分析主要參數(shù)對(duì)VRS-PNN方法性能的影響.圖10為VRS-PNN方法中LBS服務(wù)器處理效率隨參數(shù)l、近鄰參數(shù)k和POI數(shù)目N的變化趨勢(shì).由圖可見(jiàn),服務(wù)器端處理代價(jià)隨參數(shù)l的增長(zhǎng)幾近呈線性增長(zhǎng),與k也呈線性關(guān)系.

Fig.10 Server-side querying cost with increasing l,k and number of POI圖10 參數(shù)l,k,POI數(shù)目對(duì)服務(wù)器端處理效率的影響

圖11所示為客戶端與服務(wù)器間的通信代價(jià)受參數(shù)l和k影響的變化曲線.由圖11可見(jiàn),其通信代價(jià)隨l和k緩慢增長(zhǎng).

將VRS-PNN與文獻(xiàn)[19]基于路網(wǎng)泰森圖的保護(hù)位置隱私近鄰查詢方法VDNN進(jìn)行性能對(duì)比,文獻(xiàn)[19]同樣采用區(qū)域混淆方法,將匿名區(qū)域與路網(wǎng)交點(diǎn)的近鄰查詢結(jié)果返回給客戶端供其篩選最近鄰結(jié)果.對(duì)兩種方法分別順次串行發(fā)起相同的10組查詢,取處理時(shí)間的均值進(jìn)行對(duì)比,圖12為VRS-PNN方法與VDNN方法通信量對(duì)比分析圖,參數(shù)l在VDNN方法中等同于匿名區(qū)域與路網(wǎng)中路段的交點(diǎn)數(shù)目.不同于VDNN直接返回所有交點(diǎn)的k近鄰,VRS-PNN方法生成候選POI集合過(guò)程合并查詢序列中路段節(jié)點(diǎn)的近鄰POI,有效規(guī)避了重復(fù)POI傳輸,VRS-PNN方法的通信代價(jià)低于VDNN.

Fig.11 Communication cost with increasing l and k圖11 參數(shù)l,k 對(duì)通信代價(jià)的影響

Fig.12 Commubication cost comparing with VDNN algorithm圖12 VRS-PNN與VDNN方法的通信量比較

圖13為VRS-PNN與VDNN方法服務(wù)器端k近鄰查找過(guò)程性能對(duì)比.由于Vor-R*樹(shù)查詢性能優(yōu)于Vor-R樹(shù),且VRS-PNN方法僅對(duì)頻繁查詢區(qū)域構(gòu)建局部Vor-R*索引,而VDNN方法在服務(wù)器端構(gòu)建全局路網(wǎng)R樹(shù)索引,因而VRS-PNN方法相較VDNN方法能夠充分降低頻繁檢索區(qū)域的路網(wǎng)近鄰POI查詢消耗.由圖易見(jiàn),VRS-PNN在服務(wù)器端查詢性能優(yōu)于VDNN方法.

Fig.13 Querying workload comparing with VDNN algorithm圖13 VRS-PNN與VDNN方法的服務(wù)器查詢性能比較

對(duì)LBS服務(wù)器端分段式查詢處理策略的效果進(jìn)行分析,采用客戶端向服務(wù)器端同時(shí)隨機(jī)發(fā)送100次不同位置的近鄰查詢的方式,對(duì)比VRS-PNN方法和VDNN方法的服務(wù)器端處理效率.VRS-PNN方法的頻繁請(qǐng)求閾值設(shè)為0.6,統(tǒng)計(jì)得出這些查詢共涉及服務(wù)器端20個(gè)基本單元,實(shí)驗(yàn)結(jié)果如圖14所示,VRS-PNN方法的服務(wù)器端查詢處理效率顯著優(yōu)于VDNN方法.原因在于:LBS服務(wù)器接收到大量查詢時(shí),不同于VDNN對(duì)所有查詢請(qǐng)求基于全局路網(wǎng)索引的無(wú)差異檢索處理,VRS-PNN方法區(qū)分頻繁路網(wǎng)區(qū)域和非頻繁路網(wǎng)區(qū)域,并動(dòng)態(tài)維持各個(gè)頻繁基本單元的Vor-R*索引,對(duì)涉及頻繁基本單元的大量查詢,利用各基本單元的局部Vor-R*索引進(jìn)行查找,避免了對(duì)大量查詢無(wú)差別采用基于全局索引的近鄰查找導(dǎo)致的查詢代價(jià)激增.

Fig.14 Server side batch query performance comparison between VRS-PNN and VDNN圖14 VRS-PNN方法與VDNN方法服務(wù)器端批量查詢效率對(duì)比

最后,對(duì)VRS-PNN方法的客戶端處理性能進(jìn)行實(shí)驗(yàn)分析.VRS-PNN方法客戶端主要開(kāi)銷是對(duì)候選結(jié)果集的篩選,圖15為客戶端處理效率隨參數(shù)k、POI數(shù)目N的變化趨勢(shì).由圖可知:客戶端處理時(shí)間隨近鄰數(shù)k的增長(zhǎng)緩慢上升,維持在數(shù)十微秒級(jí)別,且處理時(shí)間受POI數(shù)目N的影響不顯著.所提方法適用于目前手機(jī)、導(dǎo)航儀等客戶端設(shè)備.

Fig.15 Client-site cost with increasing k and the number of POIs圖15 參數(shù)k、POI數(shù)目對(duì)客戶端處理效率的影響

7 結(jié) 論

本文提出了基于局部索引機(jī)制的保護(hù)位置隱私路網(wǎng)k近鄰查詢方法VRS-PNN,查詢客戶端通過(guò)與LBS服務(wù)器的一輪通信,獲取局部路網(wǎng)信息,生成查詢位置所在路段滿足l-路段多樣性的匿名查詢序列,并將匿名查詢序列提交LBS服務(wù)器,從而避免保護(hù)位置隱私查詢對(duì)可信第三方服務(wù)器的依賴.在LBS服務(wù)器端,提出基于路網(wǎng)基本單元?jiǎng)澐值姆侄问浇彶樵兲幚聿呗?對(duì)頻繁查詢請(qǐng)求路網(wǎng)基本單元,構(gòu)建基于路網(wǎng)泰森多邊形和R*樹(shù)的局部Vor-R*索引結(jié)構(gòu),實(shí)現(xiàn)基于索引的快速查找.對(duì)非頻繁請(qǐng)求路網(wǎng)基本單元,采用常規(guī)路網(wǎng)擴(kuò)張查詢處理.有效降低了索引存儲(chǔ)規(guī)模和基于全局索引進(jìn)行無(wú)差異近鄰查詢的訪問(wèn)代價(jià),在保證查詢結(jié)果正確的同時(shí),提高了LBS服務(wù)器端k近鄰查詢處理效率.下一步,將對(duì)所提索引策略及查詢處理方法在保護(hù)位置隱私連續(xù)路網(wǎng)近鄰查詢中的應(yīng)用進(jìn)行研究.