基于Voronoi-R*的隱私保護路網(wǎng)k 近鄰查詢方法?

倪巍偉 , 李靈奇 , 劉家強

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

2(計算機網(wǎng)絡和信息集成教育部重點實驗室(東南大學),江蘇 南京 211189)

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

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

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

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

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

(3) 查詢目標POI在路網(wǎng)的位置分布不均衡,服務器端對全局路網(wǎng)索引的無差異使用,導致低頻訪問區(qū)域對應的索引結構利用率低,這部分索引結構增加了全局索引的規(guī)模,降低了路網(wǎng)高頻訪問區(qū)域查詢的性能.

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

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

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

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

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

1 問題描述及相關概念

1.1 問題描述

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

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

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

1.2 算法思想

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

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

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

1.3 相關概念

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

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

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

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

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

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

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

2 VRS-PNN算法處理流程

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

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

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

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

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

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

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

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

Fig.1 Querying process圖1 處理流程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

算法2.k近鄰結果集篩選算法.

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

輸出:用戶真實位置的k近鄰結果集RS.

4 VRS-PNN服務器端處理方法

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

4.1 Vor-R*索引結構

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

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

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

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

Table 1 POI information表1 POI信息

LBS服務器對各個基本單元內的POI進行編號,將編號及其位置信息存儲到POI表中(見表2).在構建基本單元NVD的過程中,將所有NVP信息保存到NVD表中(見表3),表中存儲POI編號、NVP(Pi)邊界點、NVP(Pi)內部路段節(jié)點、鄰接POI信息,每個POI的NVP邊界點按順時針順序存儲.

Table 2 POI table表2 POI表

Table 3 NVD table表3 NVD表

以基本單元內POI的NVP的最小外接矩形為葉子節(jié)點構建R*樹.Vor-R*樹的構造過程如下.

(1) 構建基本單元內所有POI的路網(wǎng)泰森圖;

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

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

①在R*樹中查找待插入對象NVPi的合適的葉子節(jié)點Leaf;

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

③根據(jù)節(jié)點向上調整樹的結構;

④ 若根節(jié)點分裂,插入新的根節(jié)點,分裂后的兩個節(jié)點分別為樹的孩子節(jié)點.

對圖6所示區(qū)域劃分,Vor-R*索引樹結構如圖7所示,中間節(jié)點存儲所有子節(jié)點矩形的輪廓最小外接矩形,葉子節(jié)點存儲最小外接矩形內部NVP對應的POI編號,并指向NVD表POI編號所在位置.由于R*樹的節(jié)點之間區(qū)域重疊區(qū)域較小,服務器端查詢路段節(jié)點最近鄰時可以避免搜索多余的子樹,能夠快速獲得路段節(jié)點所在NVP的邊界節(jié)點信息,根據(jù)這些信息,可以計算判定目標位置的準確所在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*索引結構圖

4.2 服務器端局部Vor-R*索引更新

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

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

LBS服務器端索引構建策略如下.

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

(2) 若Amt

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

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

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

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

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

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

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

輸出:最近鄰POI結果集R.

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

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

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

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

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

(5) 如果i

在篩選候選集、計算路段節(jié)點準確k近鄰的過程中,需要計算路段節(jié)點到各個候選POI的最短路徑距離,然后選取最近的k個POI作為路段節(jié)點的準確k近鄰.在計算路段節(jié)點到候選POI的距離時,LBS服務器預計算NVP邊界節(jié)點間的距離,以降低路段節(jié)點到POI的距離計算量.

在查詢最近鄰POI的基礎上,進一步查找某個路段節(jié)點k近鄰POI的主要流程見算法4.

算法4.KNN查詢算法.

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

輸出:k近鄰POI結果集RS.

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

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

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

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

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

5 算法性能分析

本節(jié)從LBS服務器端和查詢客戶端計算復雜度的角度,分析VRS-PNN方法的效率.對LBS服務器端以單個路段節(jié)點為查詢對象,分別分析頻繁請求基本單元和非頻繁請求基本單元的處理效率.

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

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

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

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

6 實驗分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

7 結 論

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