面向室內實時路徑規劃的最短路徑緩存算法

文/胡睿婷 刁明光

隨著現代社會的信息化，人們對于出行質量的要求與日俱增，而在線電子地圖的發展為人們的這一需求提供了可能。現階段的在線室內導航應用主要依賴路網實現有效，快速的室內路徑規劃，并通過在本地服務器緩存路徑規劃結果，避免了通過全局服務器重新計算，節省了計算代價和通訊代價。

針對大規模室外路網尋找最短路徑的問題,不少學者提出了利用網絡緩存達到路網中快速查詢的目的。

但室內空間的實際道路狀況由于存在道路空間狹窄，障礙物較多，單程路徑規劃距離短的特點，其路網相較于室外路網，其節點總數規模較小，網絡拓撲結構也更為簡單，所以其已緩存的最短路徑中重合度較高。

經典的支持最短路徑查詢的緩存技術主要有LRU（least-recently—used)，HQF（highest-query-first）和SPC（shortest-path-cache）方法。LRU（least-recently—used)方法以有限空間保存最近的查詢來提升查詢效率，HQF（highest-query-first）算法則始終保持查詢頻率高的最短路徑優先被查詢；而SPC（shortest- path-cache）方法忽略了不同查詢中節點重復存儲的問題，導致了有限的緩存空間被重復節點大量占用。

這三種主流路徑緩存查詢技術主要以查詢頻率，查詢時間，查詢代價為主要查詢指標，在路徑緩存中進行全局查詢。

但在室內路徑規劃中，現有查詢技術主要存在以下兩個不適應問題：

（1）考慮人行走的速度一定，首次發現偏離最短路徑所花費時間較短，發現偏離時的位置與原路徑距離較近，上述三種算法都忽略了在當前路徑規劃中發生路徑偏離時，相鄰兩次查詢在地理位置上存在相關性的問題。

（2）室內空間的方位較室外空間更難以辨別，考慮人行走的方向性與行走習慣，當發現偏離原有最短路徑時，更傾向于及時對原有局部路徑進行短程回歸而非更換最短路徑，因此查詢到的最新路徑往往與上一次查詢到的路徑規劃結果重合度較高。

因此在面向室內路徑實時規劃的緩存查詢算法中，應以路徑在地理位置與網絡拓撲結構方面的相關性為指標，優先緩存當前規劃路徑相關性更高的最短路徑。

本文提出了一種基于路徑相關性代價模型的LPR（Least-Path-Related）緩存構造算法，用于在室內路徑實時規劃過程中發生路徑偏離時度量查詢緩存中保存的最短路徑的代價；通過對實時規劃路徑與緩存路徑的相關性建模，對緩存中的最短路徑進行動態更新；最后，基于真實室內路網數據集進行實驗和分析，驗證了本文所建方法的有效性。

1 路徑相關性緩存代價模型建立

根據上述問題分析，以參照本次查詢為基準的上一次最短路徑查詢結果為當前路徑，在所有緩存路徑中，其包含的節點相對當前路徑的重要程度越高，該路徑與當前路徑的相關性越大，包含本次查詢的最短路徑結果的可能性也越大。則以路徑相關性為查詢代價更新緩存，實現了在短時間內提升相鄰兩次路經查詢的命中率。

1.1 節點相關性

度中心性[1]、接近中心性、特征向量中心性[2]等是節點重要性評價[3,4,5,6,8]中主要的量化指標，但在節點重要性評價方法[7]中，其重要性主要相對于當前結點所在整體路網中的所有節點，為了度量節點與當前路徑的相關性，將節點的重要性指標轉化相對于當前規劃路徑中節點的相關性指標。

圖1：命中率與緩存容量

圖2：時間節省率與緩存容量

1.1.1 相對度中心性

相對度中心性是指網絡中節點與當前路徑節點直接連接的邊數。

式中，Pa,b表示緩存路徑，Ps0,t0表示當前規劃路徑，δij表示與節點i 是否與規劃路徑節點j 相交，若相交，則δij=1，否則為 0。相對度中心性是研究節點相對中心性最直接的度量指標，其值越大，表明節點對于當前路徑參考價值越高。

1.1.2 相對接近中心性

相對接近中心性是指節點到其他所有規劃路徑節點的最短路徑長度之和的倒數。

式中，dist(i,j)為該節點之間到規劃路徑節點的最短路徑長度,n 為規劃路徑的節點數。相對接近中心性反映在一次路徑規劃中節點與規劃路徑之間的接近程度，用來度量節點與規劃路徑的位置相關性，其值越大，表明節點相關性越高，節點的影響及服務范圍越廣，節點在未來重新規劃時仍然有效的概率越大。

1.1.3 特征向量相對中心性

通過鄰接節點的相關性來衡量本節點的相關性。此指標對于遠程相關節點仍具有較高影響力。

式中λ 為常數，M(i)為節點i 的鄰接節點集合。特征向量相對中心性反映了節點在相鄰路網中的相關價值，與相對接近中心性相比，其考慮了當前鄰點的相關性。

綜合以上述指標評價路網節點在一次路徑規劃中的路徑相關性，考慮最短路徑節點在路網中起到的單次局部影響，定義節點相關性系數模型定義如下：

式中，Ri 為節點i 的重要度；Cd(i)、Ccc(i)、Ce(i)分別表示離差標準化后的相對度中心性、相對接近中心性、和特征向量相對中心性；α1、α2、α3為上述三個指標的相關系數。采用客觀賦權法[10]Critic 方法對指標參數α1、α2、α3進行多重共線性分析，實現模型信息量的最大化。指標Cj，0＜j ≤3 所包含的信息量表達如下：

式中，δj為第j 個指標的標準差，rjk為指標j 與k 間的相關系數。指標Cj的系數αj可由下列表達式得到：

1.2 路徑相關性緩存代價模型

基于已有的緩存代價模型，定義單位空間的路徑相關性緩存代價模型如下：

式中Ri為路徑Pa,b中節點i 的路徑相關性，當緩存路徑中的節點與當前路徑的相關性越高時，該緩存路徑可以節省的查詢代價越高。緩存容量允許時，把路徑相關性最高的最短路徑Pa,b放人緩存；當緩存未滿時，定義增量的緩存計算公式：

式中S(ψ)表示緩存中所有最短路徑的集合。增量的路徑相關性代價模型給出了放入新路徑時，當前緩存所能夠節省的代價。

2 緩存構造及索引建立算法

基于上述路徑相關性代價模型，利用大頂堆優先將增量代價大的最短路徑放入緩存。緩存構造算法詳細流程如表1所示。

由于每一次路徑規劃都會更新節點相關性集合Ri，并更新倒排索引的詞典順序，而基于磁盤的外部排序算法BSBI 并不適合頻繁更新倒排索引，所以本文的倒排索引構建算法采用SMIPI 算法作為索引構建算法。如表2所示。

3 仿真實驗及結果

以北京市某購物中心1-6 層室內路網為仿真實驗對象，測試基于本文緩存代價模型的緩存構造方法，即LPR（Least-Path-Related）方法。實驗路網數據共包含3032 個節點，測試數據集共357.5KB。實驗中每例測試均包含兩次緩存查詢，將以前一次查詢結果包含的節點為中心，半徑10 米范圍內的所有可連通節點的集合，作為后一次查詢起點的選取范圍。實驗分為本地服務器仿真測試和全局服務器仿真測試。

3.1 本地服務器仿真測試

假設所有最短路徑求解的代價值 Cs,t(Local)=1。圖1中顯示本文所述方法在不同緩存容量下命中率的關系與SPC、HQF、LRU 的對比，由圖1可以看出，隨著緩存容量的增大，所有方法的命中率均有所提升；在緩存容量較小時，本文方法相比其他方法存在明顯優勢；當緩存容量到達一定數量級時，緩存已足夠裝載所有的路徑規劃結果，命中率均區域穩定，但本文方法較其他三種方法命中率更高。

3.2 全局服務器仿真測試

在全局服務器環境下，當本地服務器緩存未查詢到相關結果，則需花費一定的計算代價和通訊代價請求全局服務器求解最短路徑；求解最短路徑所用算法為Dijkstra，代價值Cs,t（Global）=Ds,t為從起點s 到終點t 所經過的邊的最小權值之和．實驗時取每條邊的權值為1。由圖2可以看出，在緩存容量較小時，由于室內路網規模較小，單條路徑所包含的節點數較少，查詢代價與求解最短路徑代價相差不大，本文方法與其他三種方法相比存在一定優勢但差距尚不明顯；但相關最短路徑在緩存中的占比一定，隨著緩存的增大，緩存中最短路徑的平均相關性逐步提升，優先放入高相關性路徑的方法在10-100KB 附近的緩存容量下查詢效率提升速度最快，而緩存容量繼續上升時，查詢效率同樣趨于穩定。

表1

表2

4 結論

本文基于路網的最短路徑緩存查詢技術，針對在室內路徑實時規劃過程中查詢最短路徑緩存時，相鄰兩次查詢的結果路徑存在相關性的問題，提出一種路徑相關性緩存代價模型，并給出了與此模型相適應的緩存構造算法和倒排索引構造算法。最后通過在真實的室內路網中進行了仿真測試，實驗證明，相較于SPC，HQF,和LRU 方法，本文提出的路徑相關性緩存代價模型在實驗中存在明顯的效率優勢。

但由于在倒排索引的構建中，以節點為鍵的索引插入并沒有考慮本文提出的路徑相關性，在后續研究中，可以仍就節點在實時路徑規劃中的這一特性，優化倒排索引的數據結構及算法。