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

倪巍偉 , 李靈奇 , 劉家強

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

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

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

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

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

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

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

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

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

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

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

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

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

1 問題描述及相關概念

1.1 問題描述

路網環境保護位置隱私近鄰查詢的關鍵問題表現在兩個方面:查詢者/發起者位置隱私保護效果以及隱私保護近鄰查詢處理的效率.

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

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

1.2 算法思想

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

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

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

1.3 相關概念

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

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

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

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

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

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

定義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服務器發送包含其位置的匿名區域及參數m(LBS需返回的最小路段數);

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

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

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

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

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

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

Fig.1 Querying process圖1 處理流程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.1 Vor-R*索引結構

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

Fig.4 Road network圖4 路網圖

Fig.5 Illustration of NVD圖5 路網泰森單元集示意

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

Table 1 POI information表1 POI信息

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

Table 2 POI table表2 POI表

Table 3 NVD table表3 NVD表

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

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

(2) 創建空R*樹;

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

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

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

③根據節點向上調整樹的結構;

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

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

Fig.6 Region partition illustration of R* tree圖6 路網泰森圖R*區域劃分示意圖

Fig.7 Structure illustration of index Vor-R*圖7 Vor-R*索引結構圖

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

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

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

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

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

(2) 若Amt

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

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

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

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

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

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

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

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

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

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

(2) 對Si中所有的POI,執行步驟(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

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

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

算法4.KNN查詢算法.

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

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

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

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

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

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

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

5 算法性能分析

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

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

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

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

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

6 實驗分析

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

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

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

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

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

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

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

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

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

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

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

對LBS服務器端分段式查詢處理策略的效果進行分析,采用客戶端向服務器端同時隨機發送100次不同位置的近鄰查詢的方式,對比VRS-PNN方法和VDNN方法的服務器端處理效率.VRS-PNN方法的頻繁請求閾值設為0.6,統計得出這些查詢共涉及服務器端20個基本單元,實驗結果如圖14所示,VRS-PNN方法的服務器端查詢處理效率顯著優于VDNN方法.原因在于:LBS服務器接收到大量查詢時,不同于VDNN對所有查詢請求基于全局路網索引的無差異檢索處理,VRS-PNN方法區分頻繁路網區域和非頻繁路網區域,并動態維持各個頻繁基本單元的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為客戶端處理效率隨參數k、POI數目N的變化趨勢.由圖可知:客戶端處理時間隨近鄰數k的增長緩慢上升,維持在數十微秒級別,且處理時間受POI數目N的影響不顯著.所提方法適用于目前手機、導航儀等客戶端設備.

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

7 結 論

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