基于緩存的時變道路網(wǎng)最短路徑查詢算法

黃 陽 周 旭 楊志邦 余 婷 張 吉 曾源遠 李肯立

1(湖南大學(xué)信息科學(xué)與工程學(xué)院 長沙 410082) 2(之江實驗室 杭州 311100)

近年來，隨著現(xiàn)代綜合化交通運輸體系結(jié)構(gòu)的改變，無線通信網(wǎng)絡(luò)安全的快速發(fā)展，具有定位功能、提供地圖服務(wù)的設(shè)備在物聯(lián)網(wǎng)中被廣泛應(yīng)用.利用基于位置服務(wù)來獲取從指定源點到目標(biāo)點的最短路徑查詢結(jié)果已經(jīng)逐漸成為主流的查詢方式.尤其是面臨緊急情況出行時，人們往往選擇旅行時間最短的路徑作為行駛路線，但是現(xiàn)實世界道路網(wǎng)中街道旅行時間具有時變性，交通狀況并不穩(wěn)定，會面臨道路臨時修建、雷雨天氣等突發(fā)事件，導(dǎo)致街道的旅行時間發(fā)生動態(tài)的改變.盡管已經(jīng)存在許多求解最短路徑的方法，但是能否高速有效地實現(xiàn)檢索動態(tài)道路網(wǎng)中旅行時間不確定的最短路徑仍面臨如下問題：

1) 查詢結(jié)果的時效性與查詢請求響應(yīng)速度的平衡問題.文獻[4]提出無索引方法，在保證路徑權(quán)重有效的情況下，通過服務(wù)器計算2點之間成本最小的路徑，但在非大規(guī)模圖上執(zhí)行路徑查詢?nèi)孕杌ㄙM幾秒鐘，其查詢性能有待提高.為解決查詢耗時長的問題，文獻[5]提出預(yù)構(gòu)建全局索引的算法，以加速最短路徑查詢.雖然引入全局索引的查詢技術(shù)能夠快速響應(yīng)查詢請求，但索引維護開銷較大，將面臨索引未完成更新，路況就可能發(fā)生了新的變化的情況，導(dǎo)致查詢結(jié)果不適用路況而變得無效.

2) 查詢響應(yīng)速度與服務(wù)器工作負載的平衡問題.當(dāng)?shù)缆肪W(wǎng)處于查詢高峰期時，查詢請求的峰值可達百萬次，此時服務(wù)器將產(chǎn)生極高的工作負載、延遲查詢的響應(yīng)時間.雖然可以通過部署更多的服務(wù)器解決負載過高的問題，但成本昂貴，并非所有公司都可以承擔(dān).該挑戰(zhàn)在可以保證查詢結(jié)果有效性的無索引算法中尤為突出.為提高大規(guī)模路徑的查詢效率，可利用緩存中的數(shù)據(jù)來提升查詢請求的響應(yīng)能力，減少服務(wù)器工作負載.文獻[7]通過引入緩存技術(shù)啟發(fā)式地將動態(tài)圖中收益值最大數(shù)據(jù)替換緩存中無效路徑來提高緩存命中率，加速查詢效率.然而該方法只適用于單路徑更新的場景.文獻[8]利用歷史日志信息將查詢頻率高的數(shù)據(jù)預(yù)加載到緩存來提高緩存命中率.而復(fù)用歷史日志信息中的高頻路徑來構(gòu)建緩存，并不適用于時變道路網(wǎng)場景，主要是因為過往數(shù)據(jù)不具備時效性，不能應(yīng)對動態(tài)變化的場景，導(dǎo)致緩存命中率降低，命中的路徑也因數(shù)據(jù)失效而出現(xiàn)結(jié)果偏差，繼而影響用戶體驗.

例如，在偏遠地點

A

開設(shè)一場萬人以上的大型演唱會，那么在演唱會當(dāng)天會存在上萬次前往地點

A

的路徑查詢請求

.

若是基于歷史信息的緩存策略，偏遠地區(qū)的數(shù)據(jù)不會預(yù)存入緩存，緩存則不會命中有關(guān)地點

A

的查詢請求，從而只在代理服務(wù)器中執(zhí)行查詢

.

此時，若出現(xiàn)大量與地點

A

相關(guān)的查詢，將導(dǎo)致服務(wù)器負荷驟增，系統(tǒng)整體的查詢性能變差

.

若此時提供一種可以實時識別查詢頻率高的路徑并用來替換緩存中的低效的路徑，則可以有效地避免上述情況的發(fā)生

.

意味著在演唱會當(dāng)天，緩存中的數(shù)據(jù)能夠及時且有效地應(yīng)答多條前往地點

A

的路徑查詢請求，以減少代理服務(wù)器的計算量

.

此外，當(dāng)?shù)攸c

A

的查詢頻率變低后，緩存中與

A

相關(guān)的數(shù)據(jù)則會自動被其他高頻率數(shù)據(jù)置換.

通常采用15 min為一個時鐘間隔來更新緩存數(shù)據(jù)，該方式得以有效應(yīng)用，是因為一段時間內(nèi)路況的變化非常小，短時間內(nèi)可以維持命中路徑的準(zhǔn)確性.因此采用實時更新緩存數(shù)據(jù)的方式不僅可以提高緩存命中率，減少服務(wù)器的運行成本，還可以提高命中數(shù)據(jù)結(jié)果的有效性.

綜上分析，在具有時變特征的道路網(wǎng)中，一個良好的基于緩存的最短路徑查詢算法是能夠支持最短路徑快速查詢和提高緩存命中率的必要條件.因此，本文設(shè)計了一個盡可能最大化利用緩存的算法來支持最短路徑查詢.并在緩存存儲策略中，將路徑共享能力計算方法和差異多樣性技術(shù)相結(jié)合，用于減小緩存中冗余數(shù)據(jù)的占用容量，提高緩存命中率.此外，緩存中的數(shù)據(jù)存儲結(jié)構(gòu)具有數(shù)據(jù)弱相關(guān)、結(jié)構(gòu)緊湊的優(yōu)點，不僅可以減少數(shù)據(jù)的存儲空間，還可以實現(xiàn)動態(tài)數(shù)據(jù)的快速維護、加快路徑的檢索速度.

本文主要貢獻有3個方面:

1) 提出的新緩存存儲結(jié)構(gòu)包含用于存儲節(jié)點的鄰接點索引、記錄路徑節(jié)點的位圖索引以及記錄路徑基本信息的路徑信息索引.該結(jié)構(gòu)新穎之處在于其存儲空間較小，索引間可獨立地維護緩存中的數(shù)據(jù);

2) 提出一種緩存存儲策略，其不僅顯著地減少了緩存中的冗余數(shù)據(jù)，還可以有效且實時地識別出存入緩存的最短路徑，以提高緩存命中率.

3) 提出了基于緩存的時變道路網(wǎng)最短路徑查詢算法(cache-based time-varying shortest path query, CTSPQ).其巧妙地借助緩存存儲結(jié)構(gòu)的特性，提高了最短路徑在緩存中的查詢速度.

在真實的數(shù)據(jù)集上進行大量實驗，驗證了本文提出的策略以及查詢方法的有效性.

1 相關(guān)工作

1.1 最短路徑查詢

近年來，最短路徑查詢問題被廣泛應(yīng)用在各行各業(yè)，其變體問題被廣泛用來研究，如查找從給定源點到目標(biāo)點最短路徑的單源點對(single pair shortest path, SPSP)問題、查找給定頂點到圖中每個頂點最短路徑的單源點(single source shortest paths, SSSP)問題以及查詢圖中所有頂點最短路徑的全對(all-pairs shortest path, APSP)問題.但是在道路網(wǎng)中檢索最短路徑的花費時間仍舊高，如常用的Dijkstra算法的時間復(fù)雜度為

O

(

m

+

n

log

n

).

為解決大規(guī)模網(wǎng)絡(luò)上最短路徑查詢耗時長的問題，文獻[5,12-17]提出了支持快速檢索最短時間/油耗/距離路徑問題的索引結(jié)構(gòu)，縮小了最短路徑查詢理論與實踐之間的差距.文獻[14]設(shè)計的HoD(highways-on-disk)索引結(jié)構(gòu)通過采用較小的I/O消耗成本來回答單原點距離(single source distance, SSD)和SSSP等查詢問題，但HoD僅適用于數(shù)據(jù)變換頻率低的情況.文獻[15]通過使用關(guān)系數(shù)據(jù)庫管理系統(tǒng)解決了SSSP查詢慢的問題，但是當(dāng)網(wǎng)絡(luò)中的數(shù)據(jù)或者結(jié)構(gòu)發(fā)生變化時，該方法將耗較長的時間重新計算節(jié)點之間的關(guān)系.

文獻[16]給出了維護索引結(jié)構(gòu)時間復(fù)雜度的理論上下界，最優(yōu)下界與網(wǎng)絡(luò)中頂點數(shù)量呈線性關(guān)系，但在節(jié)點數(shù)量非常龐大的網(wǎng)絡(luò)中才能表現(xiàn)出線性優(yōu)勢。文獻[17]利用隨機化技術(shù)提出了一個有效預(yù)測路徑距離的方法.是通過以空間換時間的方法來構(gòu)建索引，雖然可以通過部署大量服務(wù)器提高查詢速度，但運行成本高、可擴展性較差.

1.2 緩存管理

緩存具有快速交換數(shù)據(jù)的能力，文獻[18-25]利用緩存技術(shù)減少大規(guī)模最短路徑查詢時間.即預(yù)先構(gòu)建一個緩存區(qū)，若緩存中的數(shù)據(jù)能夠直接應(yīng)答查詢請求并返回結(jié)果，則無需采用代理服務(wù)器計算路徑，從而加快系統(tǒng)整體的響應(yīng)速度.故利用緩存加速查詢的關(guān)鍵點在于查詢請求在緩存中命中率.

現(xiàn)有提升緩存命中率的策略主要有3種：動態(tài)緩存策略、靜態(tài)緩存策略及混合緩存策略.靜態(tài)策略將根據(jù)歷史日志中查詢頻繁的路徑對緩存進行更新，該策略的數(shù)據(jù)無法應(yīng)對突發(fā)事件，不適用于本文.動態(tài)策略包括最近最少使用(least recently used, LRU)和最不經(jīng)常使用(least frequently used, LFU)等，LRU策略是將新路徑置換緩存中最近最久未使用的路徑的策略，LFU策略則是將當(dāng)前時間使用次數(shù)最多路徑置換緩存中使用次數(shù)最少的路徑，以此來提高緩存命中率.文獻[19]設(shè)計了最短旅行時間的路徑緩存(shortest travel-time path cache, TPC)算法，用于計算時變道路網(wǎng)中旅行時間最短的路徑，但路徑能否加入緩存依賴于緩存已有節(jié)點.文獻[20]提出的最短路徑緩存(shortest-path-cache, SPC)方法，雖然能回答查詢頻繁高的路徑，但面對突發(fā)狀況時的查詢將不具備穩(wěn)定性.混合緩存策略將靜態(tài)策略和動態(tài)策略相結(jié)合來更新緩存.

除此之外，文獻[22]利用寄存器設(shè)計了通用的框架來生成時序關(guān)鍵路徑，減少了相同查詢請求的計算次數(shù)，但其存儲空間較小.文獻[23]引入的Cache-Oblivious模型為多級內(nèi)存系統(tǒng)設(shè)計算法提供了理論基礎(chǔ).該模式是專門為標(biāo)準(zhǔn)的兩級I/O模型設(shè)計的算法，但需要小心地調(diào)優(yōu)它們所運行的系統(tǒng)的參數(shù).文獻[6]提出了批量處理最短路徑的算法，首先將查詢請求生成云狀查詢集，再利用緩存統(tǒng)一查詢以減少查詢次數(shù).文獻[8]不僅考慮了日志路徑的查詢頻率，還通過路徑的覆蓋范圍來衡量最短路徑的影響力，將高影響力的路徑存儲入緩存，進而提高其命中率.文獻[24]設(shè)計了路徑緩存規(guī)劃系統(tǒng)，將緩存中部分匹配的查詢請求結(jié)果的路徑作為返回用戶端路徑的子路徑段，以此減少服務(wù)器對整條路徑的計算量.文獻[25]不再關(guān)注網(wǎng)絡(luò)節(jié)點之間的組織情況，而是通過邊來構(gòu)造路徑緩存，首先定位查詢請求點在緩存中的候選邊，由邊之間連接得到最短路徑.雖然上述緩存技術(shù)可以加速最短路徑查詢、平衡索引維護的時間和路徑查詢速度的關(guān)系，但僅有少部分文獻涉及時變道路網(wǎng)中最短路徑查詢的緩存策略，因此在高度動態(tài)網(wǎng)絡(luò)中，利用緩存設(shè)計高速、有效應(yīng)答路徑查詢方法變得十分重要.

1.3 基于差異多樣性的路徑規(guī)劃

提高緩存命中率的常規(guī)方法是將高頻率路徑加入緩存，但高頻路徑往往存在大量重復(fù)路徑段.為減少冗余數(shù)據(jù)存入緩存，本文采用差異多樣性技術(shù)來避免緩存存儲大量相似的路徑.現(xiàn)在有關(guān)差異性的研究多集中在數(shù)據(jù)新穎度，或者多目標(biāo)空間Skyline查詢的問題上，但不適用于本文的場景.雖然也有學(xué)者研究路徑多樣性問題，但并不能完全移植到當(dāng)前問題，因為在道路網(wǎng)中求解具有差異多樣性的路徑是一個NPC問題，除此之外，在不同場景下處理數(shù)據(jù)方式不一，時間復(fù)雜度也不相同.

文獻[29-30]基于閾值剪枝策略來測量路徑的差異多樣性，以此減少路徑查詢以及比較路徑之間相似性的次數(shù).其中，文獻[29]結(jié)合閾值約束條件，返回

K

條不僅可以兼顧查詢結(jié)果總得分還能兼顧查詢結(jié)果多樣性的數(shù)據(jù)，既除掉了結(jié)果集中相似的數(shù)據(jù)又保證了結(jié)果的質(zhì)量.但這種用精確查找的方式來獲取最優(yōu)結(jié)果的耗時較長，與本文提高用戶響應(yīng)速度的目標(biāo)背離.文獻[30]通過結(jié)合相似度閾值精心地設(shè)計了算法的下界，以計算從查詢源點到目標(biāo)點的前Top-

K

條不相似的最短路徑，有效地減少了搜索空間并顯著提高了效率.不同于文獻[29-30]，本文在引入差異多樣性策略的同時，采用貪心思想實現(xiàn)最大化存入緩存的

K

條最短路徑的收益，進而減少服務(wù)器的計算量

.

其中存入緩存的

K

條路徑來自不同查詢結(jié)果，是互不相關(guān)的路徑集合，這些路徑既存在差異性，又存在共同節(jié)點，便于路徑緊密聯(lián)系

.

此處，緩存中的路徑數(shù)量

K

并非固定數(shù)值.

2 定 義

本節(jié)重點介紹基于緩存的時變道路網(wǎng)最短路徑查詢的相關(guān)理論.表1描述了基本符號.

Table 1 Summary of Notation

2.1 基本定義

定義1.

時變道路網(wǎng)模型

.

時變道路網(wǎng)

G

=(

V

,

E

,

W

,

T

)，其中

V

和

E

分別表示

G

的節(jié)點集和邊集，節(jié)點

v

∈

V

，邊

e

=(

v

,

v

)∈

E

，函數(shù)

W

:

E

×

T

→

RV

表示邊集

E

在時刻

T

的權(quán)重映射函數(shù)，其中邊

e

=(

v

,

v

)的時間權(quán)重為

w

(

v

,

v

)

.

定義2.

最短路徑

.

給定道路網(wǎng)

G

=(

V

,

E

,

W

,

T

)，

G

上從

v

到

v

的所有路徑中，具有最短旅行時間的路徑

P

，被稱為最短路徑

P

，其中節(jié)點

v

,

v

∈

V.

定義3.

查詢請求

.

在道路網(wǎng)

G

=(

V

,

E

,

W

,

T

)上，由用戶終端發(fā)出查詢請求

Q

，用于查詢從

v

∈

V

到

v

∈

V

的最短路徑

P

.

其中

v

稱為

Q

的查詢源點，

v

稱為

Q

的查詢目標(biāo)點

.

定義4.

緩存空間容量

.

給定緩存

C

，

C

中所有最短路徑的集合為

ψ.

其中，

C

的空間容量為|

C

|，

C

中數(shù)據(jù)的占用空間為|

ψ

|≤|

C

|

.

定義5.

完全命中、部分命中及未命中

.

給定緩存

C

和查詢請求

Q

,完全命中表示

C

的最短路徑集

ψ

中至少存在一條包含節(jié)點

v

,

v

的最短路徑，完全命中的路徑集可形式化為ц(

P

)={

P

,|(

v

∈

P

,)∧(

v

∈

P

,)∧ (

v

≠

v

),

P

,∈

ψ

}；部分命中表示

ψ

中至少存在一條包含節(jié)點

v

或

v

的最短路徑，部分命中

v

的路徑集可形式化為ц(

v

)={

P

,|(

v

∈

P

,)∧(

v

?

P

,),

P

,∈

ψ

}；否則稱為未命中，即

ψ

中不存在包含節(jié)點

v

或

v

的最短路徑

P

，未命中可形式化為?

P

∈

ψ

,(

v

?

P

)∧(

v

?

P

)∧(

v

≠

v

),其中，完全命中意味著

ψ

中至少存在一條最短路徑的子路徑作為

Q

的結(jié)果

.

由文獻[20]提出的最優(yōu)子路徑性質(zhì)可知，最短路徑的子路徑也是最短路徑，故完全命中獲得的路徑可以保證命中結(jié)果的準(zhǔn)確性

.

定義6.

連接路徑

.

給定最短路徑

P

,和

P

′,′，節(jié)點

v

,

v

∈

P

,，

v

,

v

∈

P

′,′，存在子路徑〈

v

→…→

v

〉?

P

,和〈

v

→…→

v

〉?

P

′,′,?表示路徑間的包含關(guān)系

.

通過

v

連接2條子路徑組成一條從

v

到

v

再到

v

的新路徑，該路徑稱為連接路徑

JPath

(

v

,

v

)=〈

v

→…→

v

→…→

v

〉

.

其中連接路徑

JPath

(

v

,

v

)可近似為最短路徑

P

，用于應(yīng)答查詢請求

Q

，減少服務(wù)器的計算量

.

2.2 問題定義

本節(jié)給出CTSPQ問題的形式化定義.

定義7.

CTSPQ

(

G

,

v

,

v

,

C

,

T

,

T

)

.

給定節(jié)點

v

,

v

∈

G

，

C

為時刻

T

的緩存，

T

為每條最短路徑在

C

中滯留的最長時間

.

記

ψ

為時刻

T

之前存入

C

的

n

條最短路徑集合，

Ω

為時刻

T

待存入

C

的

m

條最短路徑集合，

Sh

為

Pi

∈(

ψ

∪

Ω

)的共享能力，

t

為

Pi

存入

C

的時刻

.

0-1變量

x

表示

Pi

是否存儲于

C

中，

x

=1表示

Pi

存于

C

中，

x

=0表示

Pi

未存

C

中，并記

X

=(

x

1,

x

2,…,

x

(+))

.

CTSPQ的目標(biāo)是最大化緩存

C

中最短路徑集

ψ

的收益

B

(

ψ

,

Ω

,

T

,

T

)，并以在線的形式在

C

中快速規(guī)劃出一條從

v

到

v

的最優(yōu)最短路徑

P

，使得服務(wù)器的計算量最小

.

其中，

B

(

ψ

,

Ω

,

T

,

T

)滿足：

(1)

緩存技術(shù)之所以能提高路徑查詢速度是因為其可以降低服務(wù)器對數(shù)據(jù)庫的讀操作

.

因此，能否較好地解決CTSPQ問題取決于

C

中

ψ

的收益，即緩存收益越大，命中越高

.

此外，加入緩存

C

的路徑數(shù)量有限，若

C

中的數(shù)據(jù)無法應(yīng)答從

v

到

v

的查詢請求，則可從服務(wù)器中查詢并獲取最短路徑

P

.

由式(1)可知，求解緩存最大收益問題的時間復(fù)雜度為

O

(

n

|

C

|)，是一個偽多項式問題

.

其計算成本較高，因此本文將采用貪心思想計算緩存中數(shù)據(jù)的最大收益，以減少構(gòu)建緩存的計算時間

.

3 基于緩存的時變最短路徑緩存查詢算法

本節(jié)首先介紹基于緩存的時變道路網(wǎng)最短路徑查詢算法CTSPQ的總體框架.如圖1所示，框架包含3個模塊：查詢請求檢測模塊、最短路徑評估模塊和緩存管理模塊.首先從用戶終端發(fā)出具有真實地理坐標(biāo)源點

v

(

lat

,

lng

)和目標(biāo)點

v

(

lat

,

lng

)的查詢請求

Q

(步驟①)；通過查詢請求模塊將

v

(

lat

,

lng

),

v

(

lat

,

lng

)映射為節(jié)點

v

,

v

∈

G

，以轉(zhuǎn)化為

G

上的查詢請求，繼而從緩存

C

中獲取

Q

完全命中或部分命中的路徑作為候選路徑集(步驟②～④)；然后，在最短路徑評估模塊判斷候選路徑集中是否存在有效應(yīng)答

Q

的路徑，若是則將一條近似最優(yōu)的路徑返回用戶終端，否則從代理服務(wù)器檢索

Q

的最短路徑，并返回到用戶終端(步驟⑤～⑧)；此外，緩存管理模塊中的緩存結(jié)構(gòu)用于存儲數(shù)據(jù)，緩存存儲策略決定從服務(wù)器獲取的實時最短路徑是否能存入

C

(步驟⑨～⑩)

.

Fig. 1 CTSPQ schematic diagram圖1 CTSPQ框架示意圖

3.1 緩存管理模塊

構(gòu)建索引是加速最短路徑查詢的主要技術(shù)之一，在數(shù)據(jù)的檢索和存儲中起著重要作用.因此本文在本模塊中設(shè)計了便于更新緩存數(shù)據(jù)的索引結(jié)構(gòu)以及提高緩存命中率的路徑緩存存儲策略，以快速響應(yīng)時變環(huán)境下的查詢請求，減少服務(wù)器的工作負載.

如圖1所示，無論執(zhí)行哪個模塊，只要執(zhí)行操作皆離不開緩存中的數(shù)據(jù).即一旦觸發(fā)其他模塊，緩存管理模塊也隨之觸發(fā).

3.1.1 緩存存儲結(jié)構(gòu)

圖2展示了一個簡單緩存最短路徑的例子.根據(jù)圖2(a)的子圖得到了圖2(b)的5條最短路徑，并按照路徑節(jié)點的旅行順序?qū)⒙窂酱嫒刖彺媪斜?，如路?p>P

=〈

v

→

v

→

v

→

v

〉存放節(jié)點的順序為

v

,

v

,

v

,

v

.

當(dāng)存在查詢請求

Q

時，首先判斷緩存列表中的路徑是否存在從由

v

到

v

的子路徑，若是則直接應(yīng)答

Q

.

如查詢請求

Q

可由圖2中的

P

應(yīng)答

.

雖然此存儲方式可應(yīng)答查詢請求，但會導(dǎo)致緩存出現(xiàn)大量的冗余數(shù)據(jù)，如

v

存儲了3次，

v

存儲了4次，甚至出現(xiàn)了冗余路徑，如

P

是

P

的子路徑

.

Fig. 2 An example of simple cache storage圖2 簡單緩存實例圖

Fig. 3 An example of the AMPS storage path圖3 AMPS存儲路徑示意圖

因此，為減少數(shù)據(jù)的存儲空間，本文設(shè)計了一個數(shù)據(jù)弱相關(guān)、結(jié)構(gòu)緊密的緩存存儲結(jié)構(gòu).該結(jié)構(gòu)由存儲節(jié)點的鄰接點索引(adjacency node index,

ANI

)、存儲路徑的位圖索引(bit map index,

BMI

)以及記錄路徑基本信息的路徑信息索引(path information index,

PII

)等3部分組成，并簡稱為AMPS.圖3展示了以AMPS形式存儲圖2中5條最短路徑的例子.1) 鄰接點索引

ANI.

ANI

記錄了緩存

C

中每條路徑節(jié)點的鄰接點關(guān)系，記為鄰接點對〈

v

,

v

〉，并為返回一條有序的最短路徑做準(zhǔn)備

.

其中，每個鄰接點對在

ANI

中最多存儲一次，表示

C

中至少存在一條從

v

到

v

(或從

v

到

v

)的路徑

.ANI

引用了文獻[8]的模型，它無需存儲

G

上所有鄰接點對關(guān)系，減少了冗余數(shù)據(jù)存入

C.

以圖3(a)為例，

v

的鄰接點有

v

，

v

和

v

，存在路徑

P

,

P

經(jīng)過

v

到達

v

；

P

,

P

經(jīng)過

v

到達

v

.

雖無路徑經(jīng)過

v

到達

v

，但存在經(jīng)過

v

到達

v

的路徑

P

,

P

和

P

，故

ANI

記錄了鄰接點對〈

v

,

v

〉的關(guān)系

.

2) 位圖索引

BMI.

BMI

以位圖形式記錄了最短路徑

P.

如圖3(b)所示，存在于路徑上的節(jié)點用“1”標(biāo)注，否則標(biāo)注為“0”，其中路徑

P

=〈

v

→

v

→

v

〉上的節(jié)點

v

,

v

,

v

在

BMI

中被“1”標(biāo)記

.

因為位圖可以執(zhí)行二進制操作，因此

BMI

可以快速識別查詢請求的候選路徑，并快速判斷

C

中數(shù)據(jù)所涉及的節(jié)點

.

以圖3(b)為例快速識別

Q

和

Q

的候選路徑

.

令操作

BMI

(

v

)表示求解節(jié)點

v

所在的路徑集合，請求

Q

通過執(zhí)行

BMI

(

v

)∩

BMI

(

v

)={

P

,

P

}得到完全命中的候選路徑集；而

Q

執(zhí)行

BMI

(

v

)∩

BMI

(

v

)=?，無完全命中的候選路徑集，但可以通過部分命中操作獲取與源點

v

和目標(biāo)點

v

相關(guān)的2個部分命中候選路徑集

BMI

(

v

)={

P

,

P

},

BMI

(

v

)={

P

}，根據(jù)候選路徑集執(zhí)行連接操作獲得應(yīng)答

Q

的連接路徑，即通過

v

連接候選路徑

P

和

P

獲得答查詢請求的候選連接路徑

JPath

(

v

,

v

)=〈

v

→

v

→

v

→

v

〉

.

3) 路徑信息索引

PII.

PII

記錄了

ψ

中每條路徑

P

的基本信息〈

t

，

Sh

〉，用于更新緩存

C

中的數(shù)據(jù)，以保證從緩存中得到有效的查詢結(jié)果

.

其中

t

表示

P

加入

C

的時刻、

Sh

表示

P

的共享能力(見定義8)

.

利用

t

計算

P

在

C

中滯留的時長，當(dāng)時長超過

T

時，從

C

中移除

P

；

Sh

用于判斷

P

是否被新路徑置換，因為路徑共享能力是反映路徑受歡迎程度和重要性的指標(biāo)，是計算緩存收益的主要影響因素

.

定義8.

路徑共享能力

.

給定道路網(wǎng)

G

=(

V

,

E

,

W

,

T

)上的一條最短路徑

P

=〈

v

→

v

→…→

v

〉，

P

的路徑共享能力記做

Sh

.

歸一化的

Sh

可形式化為

(2)

其中,0≤

μ

，

μ

，

μ

≤1，

μ

+

μ

+

μ

=1；

QS

為當(dāng)前

G

中所有查詢請求的集合，|

QS

|為

QS

中請求的數(shù)量；|

QS

|為節(jié)點

v

∈

P

在

QS

的源點集和目標(biāo)點集中出現(xiàn)的次數(shù)；|

d

|為節(jié)點

v

∈

V

的度數(shù)；|

E

|表示邊

E

的數(shù)量；|

V

|為節(jié)點集

V

中節(jié)點的數(shù)量；

P

的節(jié)點數(shù)量為|

P

|=

n.

以圖2舉例說明路徑共享能力的計算方法，記圖2(a)為道路網(wǎng)子圖

G

′，令圖2(b)中最短路徑的查詢請求為查詢請求集

QS

,

μ

=0

.

4,

μ

=0

.

2,

μ

=0

.

4；故|

QS

|=5,|

E

|=7,|

V

|=7

.

若求解

P

=〈

v

→

v

→

v

→

v

→

v

→

v

〉共享能力，可知

類似方法可得其余4條最短路徑的共享能力見圖3(c)

.

算法1展示了在時刻

T

將最短路徑

P

加入緩存

C

的偽代碼

.

假設(shè)

P

的共享能力為

Sh

，首先獲取

C

中AMPS的數(shù)據(jù)(行①)；接著依次遍歷

P

上的節(jié)點

v

及其鄰接點

v

+1∈

P

，并將2點添加至

BMI

,

ANI

中，其中，若

ANI

中已存在鄰接點對〈

v

,

v

+1〉的信息，則無需對索引

ANI

進行操作(行②～④)

.

最后將

P

的信息〈

T

，

Sh

〉存入

PII

，并返回

C

(行⑤～⑥)

.

算法1.

插入算法

Insert

(

P

,

C

,

T

,

Sh

)

.

輸入：新路徑

P

、緩存

C

、當(dāng)前時間

T

、共享能力

Sh

；輸出：緩存

C.

①

ANI

,

BMI

,

PII

←

get

(

C

);

/

*從緩存

C

中獲取索引信息*

/

② for each node

v

in

P

③

add

(

ANI

,

BMI

,

v

,

v

,

P

);

/

*分別在

ANI

,

BMI

中添加鄰接點對〈

v

,

v

+1〉及路徑

v

∈

P

信息*

/

④ end for

⑤

addPII

(

PII

,

T

,

Sh

);

/

*將

P

的信息加入

PII

*

/

⑥ return

C.

以圖3為例，令

T

=1,|

ψ

|=0，此時向

C

中添加共享能力為0

.

511 4的最短路徑

P

=〈

v

→

v

→

v

〉

.

首先從

v

開始，在

ANI

中加入

v

的鄰接點

v

，

v

的鄰接點

v

，在

BMI

中用“1”標(biāo)注

v

∈

P

；然后在

ANI

中加入

v

的鄰接點

v

，

v

的鄰接點

v

，在

BMI

中用“1”標(biāo)注

v

∈

P

；循環(huán)上述步驟，直至用“1”標(biāo)注

v

∈

P

；最后在

PII

中添加

P

的信息〈1,0

.

511 4〉

.

算法2.

刪除算法

Delete

(

P

,

C

,

T

)

.

輸入：刪除路徑

P

、緩存

C

、當(dāng)前時間

T

；輸出：緩存

C.

①

Z

←空棧,

D

←空集合;②

ANI

,

BMI

,

PII

←

get

(

C

);

/

*從緩存

C

中獲取索引信息*

/

③

v

′←

random

(

P

);

/

*隨機獲取

P

上的一個節(jié)點*

/

④

Z.push

(

P

,

v

′,

D

);

/

*將節(jié)點

v

′入棧

Z

*

/

⑤ while 棧

Z

中存在元素時⑥

v

←

Z.pop

();

/

*出棧

Z

中的元素放入

v

*

/

⑦ if節(jié)點

v

′和

v

當(dāng)且僅當(dāng)存在于路徑

P

⑧

delete

(

ANI

,

v

,

v

′ );

/

*在

ANI

中刪除鄰接點對〈

v

,

v

′ 〉的信息*

/

⑨ end if

⑩

D.add

(

v

)；

/

*記錄已刪除的節(jié)點*

/

中的鄰接點入棧

Z

*

/

/

*刪除

PII

,

BMI

中

P

*

/

3.1.2 緩存收益模型

求解緩存最大收益問題是NPC問題，本文首先采用簡單的Baseline策略構(gòu)建緩存數(shù)據(jù).Baseline策略結(jié)合了貪心思想，將路徑共享能力近似為路徑存入緩存的收益，在保證在較高命中率的前提下，減少存儲過程的計算量.Baseline策略首先按照待加入緩存的最短路徑共享能力以從大到小的順序依次加入緩存

C

，直到

C

中無多余空間存入新路徑，因此Baseline的時間復(fù)雜度為

O

(

n

lg

n

)

.

以圖4說明采用Baseline策略構(gòu)建路徑緩存

C

的方法

.

在道路網(wǎng)子圖

G

′上，首先為方便計算

C

中數(shù)據(jù)的占用空間|

ψ

|，舉例時僅考慮

PII

及

ANI

的占用空間

.

令一個節(jié)點的占用空間為1，一條

PII

信息占用空間為2，

T

=6，初始化|

ψ

|=0，|

C

|=16

.

在

T

=1時，待加入

C

的3條最短路徑的共享能力的大小依次是

Sh

>

Sh

>

Sh

.

故首先確定

P

加入

C

需要在

ANI

中增加10個節(jié)點(5個鄰接點對)，故將

P

加入

C

時|

ψ

|=10+2<|

C

|；接著

P

是

P

的子路徑，只需增加

PII

信息，加入

C

時|

ψ

|=12+2<|

C

|；最后判斷

P

加入

C

還需在

ANI

中新增鄰接點對〈

v

,

v

〉，占用4個空間，而|

ψ

|+4=18>|

C

|，故

P

不被加入

C.

此時緩存中的共享能力總和為0

.

861 9+0

.

695 2=1

.

557 1，并且可以應(yīng)答路網(wǎng)上

v

～

v

之間的查詢請求

.

雖然采用Baseline策略可以減少構(gòu)建緩存的計算量，但是無法避免子路徑等冗余數(shù)據(jù)存入緩存，如

P

是

P

的子路徑

.

然而道路網(wǎng)中訪問頻率高的路徑，其子路徑也往往具有較高的訪問頻率，這些子路徑極易存入緩存

.

因此在第3

.

1

.

3節(jié)改進了Baseline策略

.

Fig. 4 Example diagram of TSPC strategy圖4 TSPC策略實例圖

3.1.3 改進存儲策略

本節(jié)為優(yōu)化Baseline策略提出了時變最短路徑緩存(time-varying shortest path cache, TSPC)策略.該策略在Baseline的基礎(chǔ)上結(jié)合了差異多樣性技術(shù)，在保證緩存路徑有效的前提下，盡可能使得緩存中的任意2條路徑不相似，以減少緩存中的冗余數(shù)據(jù)，達到提高緩存命中率的效果.

衡量數(shù)據(jù)相似度常用的方法為Jaccard相似系數(shù)，但Jaccard適用于衡量路徑重合度而差異性.故本文改進相似度度量方法來判斷緩存路徑的相似性.

定義9.

相似度度量

.

給定最短路徑

P

和

P

以及相似度約束值

τ

，

P

和

P

相似度為

(3)

其中,|

S

(

P

)∩

S

(

P

)|表示

P

和

P

具有一樣節(jié)點的數(shù)目；min(|

P

|,|

P

|)表示

P

和

P

之中擁有較少節(jié)點數(shù)量的數(shù)值；

τ

的取值范圍為[0,1]

.

與Jaccard略為不同，本文相似度度量方法選擇min(|

P

|,|

P

|)作為分母，它可以清楚地感知較多節(jié)點數(shù)目的路徑能夠作為較少節(jié)點數(shù)目路經(jīng)的共享路徑

.

其中，

τ

值的大小決定緩存中路徑間最高相似度，

τ

值越大冗余數(shù)據(jù)越多

.

TSPC策略的最壞時間復(fù)雜度為

O

(

kn

+

n

lg

n

)，其中

k

表示|

ψ

|=

k

，

n

表示在時刻

T

待加入緩存的最短路徑數(shù)量，

O

(

n

lg

n

)表示排序的時間復(fù)雜度，

O

(

kn

)表示構(gòu)建

k

條互不相似最短路徑的最大開銷

.

而最優(yōu)時間復(fù)雜度是

O

(

n

lg

n

)，即共享能力最大的前

k

條最短路徑兩兩不相似

.

以圖4為例說明TSPC策略構(gòu)建緩存

C

的方法

.

為方便與Baseline策略進行比對，TSPC的初始條件與Baseline一致，除此之外，令

τ

=0

.

7

.

當(dāng)

T

=1時，首先對待加入

C

的3條最短路徑按照其共享能力排序，即

Sh

>

Sh

>

Sh

.

由TSPC策略可知，先將

P

加入緩存

C

，此時|

ψ

|=12<|

C

|；接著判斷

P

與

C

中路徑集

ψ

的相似度，由

Sim

(

P

，

P

)=1>

τ

可知，

C

拒絕

P

的加入；接著判斷

P

與

C

中

ψ

的相似度，即

Sim

(

P

,

P

)=2

/

3<

τ

，此時將

P

加入

C

需在

ANI

中新增鄰接點對〈

v

,

v

〉，占用空間為|

ψ

|+4=16≤|

C

|，故將

P

加入

C.

雖然緩存的共享能力總和為0

.

861 9+0

.

523 8=1

.

385 7<1

.

557 1(Baseline策略1

.

557 1)，但緩存

C

中的數(shù)據(jù)不僅可以應(yīng)答B(yǎng)aseline策略可應(yīng)答的查詢，還可以通過構(gòu)建連接路徑應(yīng)答與

v

有關(guān)的查詢請求，提高了緩存的命中率

.

此外，當(dāng)

T

=7時，待加入

C

的2條最短路徑的共享能力為

Sh

>

Sh

.

首先由

T

-

T

=1可知，在1時之前加入

C

的路徑已逾時，故清空緩存

C

，|

C

|=0

.

接著將

P

加入

C

，空間容量|

ψ

|=10<|

C

|，然后判斷

P

與

C

中

ψ

的相似度，

Sim

(

P

,

P

)=2

/

3<

τ

滿足約束條件，還需在

ANI

中增加鄰接點對〈

v

,

v

〉、

PII

中增加基本信息，|

ψ

|+4=14<|

C

|，故可將

P

加入

C.

算法3.

TSPC更新緩存算法

Update

(

C

,

P

,

T

,

T

,

τ

)

.

輸入：緩存

C

、最短路徑

P

、當(dāng)前時間

T

、最大滯留時間

T

、相似度閾值

τ

；輸出：緩存

C.

①

Z

←空優(yōu)先隊列,

D

←空優(yōu)先隊列;②

Sh

←根據(jù)式(2)計算路徑

P

的共享能力;③ for each

Pi

in

C

④ if

T

-

t

≥

T

⑤

Delete

(

Pi

,

C

,

T

,

Sh

);

/

*刪除路徑

Pi

*

/

⑥ else if

Sim

(

Pi

,

P

)>

τ

且

Sh

<

Sh

⑦

Z.push

(

Pi

);

/

*將路徑

Pi

入隊

Z

*

/

⑧ else if

Sh

<

Sh

⑨

D.add

(

Pi

);

/

*將路徑

Pi

入隊

D

*

/

⑩ end if

/

*刪除緩存

C

中與

Z

有關(guān)的路徑*

/

/

*將

P

加入緩存

C

*

/

/

*將緩存

C

中與

Z

相關(guān)的路徑刪除*

/

/

*出隊

D

中的路徑并刪除緩存

C

與其相關(guān)的數(shù)據(jù)，直至緩存容量滿足|

C

|≥|

ψ

+

P

|*

/

3.2 查詢請求檢測模塊

本模塊用于識別緩存中可應(yīng)答查詢請求的候選路徑集.在位置坐標(biāo)評估時需執(zhí)行節(jié)點映射操作，是因為真實地理空間中的坐標(biāo)是連續(xù)不斷的，而現(xiàn)有的存儲設(shè)備無法將所有坐標(biāo)點存入存儲設(shè)備，所以首先將連續(xù)坐標(biāo)點映射成離散點.

映射可以將查詢節(jié)點變得規(guī)范，不僅可以快速確定查詢請求能否在緩存中命中路徑，還可以識別同一批次中查詢結(jié)果相同的查詢請求，通過共享一個結(jié)果，減少查詢次數(shù).

為快速定位地理空間坐標(biāo)點在

G

上的位置，本文采用KD-Tree索引映射二者之間的關(guān)系.與基于網(wǎng)格均勻劃分區(qū)域空間的方式不同，KD-Tree將節(jié)點多的區(qū)域分割更加細致，節(jié)點少的區(qū)域分割更加粗糙.以此來提高映射的效率，為批量處理提供條件.在獲取應(yīng)答

Q

的候選路徑集時，只需通過當(dāng)前緩存中BMI的信息查詢與源點

v

和目標(biāo)點

v

相關(guān)的路徑，即獲得部分命中的候選路徑集ц(

v

)和ц(

v

)，以及完全命中的候選路徑集合ц(

P

)

.

3.3 最短路徑評估模塊

本模塊用于評估從查詢請求檢測模塊得到的候選路徑集能否應(yīng)答查詢請求.本模塊可以通過執(zhí)行直接查詢操作(direct query operation, DQO)，選擇一條最優(yōu)路徑應(yīng)答查詢請求，或者通過執(zhí)行連接查詢操作(join query operation, JQO)獲取一條連接路徑用于應(yīng)答查詢請求.若2種操作皆無法獲取應(yīng)答查詢請求的路徑，則只能通過代理服務(wù)器獲取最短路徑.

直接查詢操作DQO表示從ц(

P

)中選擇一條距離當(dāng)前時間最近的最短路徑應(yīng)答

Q

.

DQO可形式化為

DQO

(ц(

P

),

T

,

T

)，滿足：

(4)

連接查詢操作JQO表示從ц(

v

)及ц(

v

)中各任選一條路徑

P

∈ц(

v

),

P

′∈ц(

v

)來組成連接路徑

JPath

(

v

,

v

)應(yīng)答

Q

.

其中，

JPath

(

v

,

v

)需要滿足時間約束

T

以及歐氏距離約束

EDR

(

v

,

v

,

v

)

.

JQO形式化為

JQO

(

v

,

v

,

θ

,

T

,

T

)，滿足：

(5)

其中，JQO引入距離約束閾值

θ

，是因為連接路徑

JPath

(

v

,

v

)的連接點

v

可能偏離最短路徑

P

，并出現(xiàn)在很遠的位置，此時連接路徑的旅行時間將變得不可靠

.

為避免連接路徑的偏離，故設(shè)置歐氏距離比來控制

v

的偏離程度，即：

(6)

表示從

v

到

v

和

v

到

v

的歐氏距離之和與

v

到

v

的歐氏距離比小于

θ.θ

的大小影響連接路徑的旅行時間，

θ

越小連接路徑的長度越趨近于最短路徑，但當(dāng)

θ

=1時并不一定是最短路徑

.

算法4.

查詢算法

CTSPQ

(

C

,

Q

,

G

,

θ

,

T

)

.

輸入：緩存

C

、查詢請求

Q

、道路網(wǎng)

G

、歐氏距離比

θ

、最大滯留時間

T

；輸出：最短路徑

P.

① ц(

v

),ц(

v

)←空棧;

P

←空集;

sign

←false;

PII

,

ANI

,

BMI

←從緩存

C

中

獲取數(shù)據(jù)信息;

②

v

,

v

←

KD

-

tree

(

Q

,

G

);

/

*查詢請求映射*

/

③ ц(

v

)←

BMI

(

v

)；

/

*獲取

v

所在的路徑*

/

④ ц(

v

)←

BMI

(

v

)；

/

*獲取

v

所在的路徑*

/

⑤ if ц(

v

)∩ц(

v

)的路徑集合不為空⑥

P

←

DQO

(

v

,

v

,

T

,

T

);

/

*見式(4)*

/

⑦ return

P

；

/

*返回路徑

P

*

/

⑧ else

⑨

P

←

JQO

(

v

,

v

,ц(

v

),ц(

v

),

θ

)；

/

*見式(5)*

/

⑩ if 存在連接路徑

P

/

*從服務(wù)器獲取路徑*

/

以圖3為例，在時刻

T

發(fā)出查詢請求

Q

，首先將

Q

的源點和目標(biāo)點映射到道路網(wǎng)子圖

G

′上的節(jié)點

v

和

v

，然后在索引

BMI

中執(zhí)行部分命中操作

BMI

(

v

)={

P

,

P

,

P

},

BMI

(

v

)={

P

,

P

,

P

}獲取候選路徑集ц(

v

),ц(

v

)和ц(

P

)，在ц(

P

)中存在路徑

P

滿足|

t

4,3-

T

|<

T

，即滿足DQO約束，故可以直接向用戶端返回路徑

P

.

路徑

P

的旅行次序可以結(jié)合索引

BMI

和

ANI

中的數(shù)據(jù)獲得

.

而獲取旅行次序的過程與刪除過程相似，繼續(xù)以

P

為例說明如何確定路徑走向

.

令

D

記錄已檢索鄰接點的節(jié)點，

Z

記錄已訪問但未檢索鄰接點的節(jié)點，第1步，通過

random

(

P

)函數(shù)隨機獲取節(jié)點

v

為

P

檢索起點，

Z

={

v

}；第2步，根據(jù)

ANI

檢索既在

P

上又是

v

鄰接點的節(jié)點{

v

,

v

}，此時

D

={

v

},

Z

={

v

,

v

}

.

第3步，

Z

出棧

v

，在

P

上

v

的鄰接點集為{

v

},

v

∈

D

已被訪問，且無其他鄰接點，故可確定

P

的一段子路徑為〈

v

→

v

〉，此時

D

={

v

,

v

}、

Z

={

v

}

.

同理，

Z

出棧

v

，找到

v

鄰接點

v

,

v

，而

v

∈

D

已被訪問，得到

P

的另一段子路徑〈

v

→

v

→

v

〉，此時

D

={

v

,

v

,

v

}，

Z

={

v

}

.Z

出棧

v

，其在

P

上的鄰接點為{

v

}，而

v

∈

D

，

Z

=?，已遍歷上的

P

所有節(jié)點，故通過檢索起點

v

連接2條子路徑段可確定

P

的旅行方向為〈

v

→

v

→

v

→

v

〉

.

4 實驗分析

本節(jié)通過在真實數(shù)據(jù)集上進行大量實驗，驗證了所提算法的有效性及可擴展性.

4.1 實驗設(shè)置

本文實驗環(huán)境見表2，采用的編程語言為Java.此外在相同的環(huán)境下，本文分別對SPC,EPC,Baseline,TSPC策略方法進行了對比測試.

Table 2 Experiment Environment

Fig. 6 Effect of cache size圖6 緩存大小的影響

4.2 數(shù)據(jù)集

本文使用的實驗數(shù)據(jù)集來自文獻[25]，利用加利福尼亞州道路網(wǎng)上的真實數(shù)據(jù)集進行實驗.該網(wǎng)絡(luò)具有真實的興趣點，包含了21 693條邊、21 048個節(jié)點和104 770個興趣點.我們從興趣點中隨機選擇2點作為測試的源點和目標(biāo)點，用于生成時空路徑進行實驗，此外，測試部分的數(shù)據(jù)除了來自文獻[25]之外，還有來自必應(yīng)地圖的實時查詢數(shù)據(jù).在實驗過程中利用必應(yīng)地圖的API作為提供準(zhǔn)確的最短旅行時間的服務(wù)器.在測試之前我們隨機獲取某一時刻的查詢來預(yù)熱緩存.

本文所涉及的實驗若無特殊說明則代表緩存最多可容納的節(jié)點數(shù)為50 000(每個節(jié)點占4 B)，緩存中所有數(shù)據(jù)的總?cè)萘坎怀^1 MB，同一時刻下的查詢請求數(shù)量設(shè)為10 000，構(gòu)建緩存的候選路徑數(shù)量設(shè)為10 000，相似度閾值設(shè)為0.7，距離約束設(shè)為1.05.

T

=15，緩存中路徑滯留時間最大為15 min.

4.3 實驗結(jié)果

4.3.1 映射

將地理坐標(biāo)點映射到道路網(wǎng)

G

的過程中，本文采用了KD-Tree算法.KD-Tree劃分的層級越多，映射結(jié)果越準(zhǔn)確，為了更準(zhǔn)確地識別數(shù)據(jù)，本文對道路網(wǎng)進行了精確的分割識別，在保證結(jié)果正確的前提下，可快速識別基于位置服務(wù)的點在

G

中的位置.圖5描繪了Gird,KD-Tree,linear等方法在不同大小數(shù)據(jù)集下運行的時間.采用KD-Tree方法的映射速度明顯優(yōu)于Gird和linear方法.

Fig. 5 Response time of different mapping methods圖5 不同映射方法的響應(yīng)時間

4.3.2 緩存大小

緩存容量的大小關(guān)乎整個系統(tǒng)的性能.緩存容量越小，命中率越低，但當(dāng)緩存容量過大時，雖然命中率會明顯提高，但會降低查詢速度.

圖6展示了不同緩存大小下SPC,EPC,Baseline,TSPC等算法的查詢響應(yīng)時間以及命中率，其中查詢響應(yīng)時間由映射過程時間以及在緩存中獲取路徑的時間組成.在圖6(a)中，當(dāng)緩存|

C

|>30 000時， 雖然EPC策略在緩存中的總耗時為TSPC,Baseline策略的10%～20%，但EPC在緩存中的命中率是TSPC和Baseline命中率的4%左右.綜合分析，本文策略的整體效率較優(yōu).

在圖6(b)中，隨著緩存容量的增加，TSPC的命中率逐漸趕超Baseline的命中率.是因為受相似度的約束，TSPC緩存的節(jié)點種類比Baseline的多，可通過連接操作得到應(yīng)答查詢請求的路徑.正因相似度約束，TSPC緩存的數(shù)據(jù)量并不會因為緩存容量的無限擴大而增加，緩存中的數(shù)據(jù)量會維持在一個范圍內(nèi).

4.3.3 參數(shù)

θ

分析由三角形三邊關(guān)系可知，在連接操作中引入歐氏距離比閾值

θ

，意味著連接路徑的長度不會被無線延伸，可避免偏差較大的候選路徑.圖7顯示了在不同

θ

下緩存的命中率及路徑查詢結(jié)果的準(zhǔn)確度，

θ

的取值范圍為[1.00，1.10].由圖7(a)可知隨著

θ

約束力度的放寬，以連接路徑的形式應(yīng)答查詢請求的數(shù)量增多，命中率有較大的提升，但結(jié)果會出現(xiàn)較大的偏差.而在允許有10%的偏差下，TSPC和Baseline策略的命中率提升為90%以上，故在誤差允許的范圍內(nèi)使用TSPC和Baseline可提高服務(wù)器的整體運行效率.

Fig. 7 Effect of θ圖7 θ值的影響

Fig. 8 Effect of τ圖8 τ值的影響

4.3.4 參數(shù)

τ

分析圖8顯示了不同相似度閾值

τ

下的命中率以及準(zhǔn)確率，

τ

值大小影響緩存中路徑的多樣性

.

當(dāng)

τ

=0時，表示緩存中的數(shù)據(jù)集不存在相同節(jié)點，也就意味著當(dāng)執(zhí)行查詢操作時，緩存路徑只能進行完全命中操作，此時準(zhǔn)確率達到最高；當(dāng)

τ

=1時，緩存中的存儲的路徑不再受到相似度的約束，而是僅受到緩存容量的限制，即為Baseline操作.如圖8(a)所示，當(dāng)

τ

∈[0.5,0.7]時，TSPC的緩存命中率遠比未采用相似度約束的算法高，故相似度約束可明顯改善小容量緩存的命中率.圖8(b)～(c)顯示了不同

τ

值下命中結(jié)果的準(zhǔn)確率，雖然TSPC和Baseline策略在無誤差情況下的準(zhǔn)確率低于SPC的準(zhǔn)確率，但是在

τ

=0.7時其命中率近似于SPC命中率的3倍，此外在容許存在10%誤差的情況下，準(zhǔn)確率達到90%以上.

5 總 結(jié)

針對時變道路網(wǎng)中在線查詢最短路徑效率慢的問題，本文利用緩存減少服務(wù)器的工作負載，首先為降低數(shù)據(jù)占用緩存空間，設(shè)計了一個緩存存儲結(jié)構(gòu)；其次，為實時地構(gòu)建路徑緩存提出了基于貪心策略和相似度約束的緩存存儲策略，提高了緩存的命中率；最后根據(jù)存儲結(jié)構(gòu)中的索引特性，設(shè)計了一個利用緩存高效應(yīng)答最短路徑查詢的算法.最終通過大量實驗結(jié)果表明了本文所提的算法具有有效性和高效性.

作者貢獻聲明

：黃陽負責(zé)實驗及論文的起草；周旭、楊志邦提出算法優(yōu)化方案，為共同通信作者；余婷、張吉負責(zé)索引設(shè)計及文字潤色；曾源遠、李肯立負責(zé)實驗方案及論文整體架構(gòu)設(shè)計.