黃 陽(yáng) 周 旭 楊志邦 余 婷 張 吉 曾源遠(yuǎn) 李肯立

1(湖南大學(xué)信息科學(xué)與工程學(xué)院 長(zhǎng)沙 410082) 2(之江實(shí)驗(yàn)室 杭州 311100)

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

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

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

例如，在偏遠(yuǎn)地點(diǎn)

A

開(kāi)設(shè)一場(chǎng)萬(wàn)人以上的大型演唱會(huì)，那么在演唱會(huì)當(dāng)天會(huì)存在上萬(wàn)次前往地點(diǎn)

A

的路徑查詢(xún)請(qǐng)求

.

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

A

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

.

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

A

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

.

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

.

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

A

的路徑查詢(xún)請(qǐng)求，以減少代理服務(wù)器的計(jì)算量

.

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

A

的查詢(xún)頻率變低后，緩存中與

A

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

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

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

本文主要貢獻(xiàn)有3個(gè)方面:

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

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

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

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

1 相關(guān)工作

1.1 最短路徑查詢(xún)

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

O

(

m

+

n

log

n

).

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

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

1.2 緩存管理

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

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

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

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

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

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

K

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

K

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

K

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

.

其中存入緩存的

K

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

.

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

K

并非固定數(shù)值.

2 定 義

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

Table 1 Summary of Notation

2.1 基本定義

定義1.

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

.

時(shí)變道路網(wǎng)

G

=(

V

,

E

,

W

,

T

)，其中

V

和

E

分別表示

G

的節(jié)點(diǎn)集和邊集，節(jié)點(diǎn)

v

∈

V

，邊

e

=(

v

,

v

)∈

E

，函數(shù)

W

:

E

×

T

→

RV

表示邊集

E

在時(shí)刻

T

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

e

=(

v

,

v

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

w

(

v

,

v

)

.

定義2.

最短路徑

.

給定道路網(wǎng)

G

=(

V

,

E

,

W

,

T

)，

G

上從

v

到

v

的所有路徑中，具有最短旅行時(shí)間的路徑

P

，被稱(chēng)為最短路徑

P

，其中節(jié)點(diǎn)

v

,

v

∈

V.

定義3.

查詢(xún)請(qǐng)求

.

在道路網(wǎng)

G

=(

V

,

E

,

W

,

T

)上，由用戶終端發(fā)出查詢(xún)請(qǐng)求

Q

，用于查詢(xún)從

v

∈

V

到

v

∈

V

的最短路徑

P

.

其中

v

稱(chēng)為

Q

的查詢(xún)?cè)袋c(diǎn)，

v

稱(chēng)為

Q

的查詢(xún)目標(biāo)點(diǎn)

.

定義4.

緩存空間容量

.

給定緩存

C

，

C

中所有最短路徑的集合為

ψ.

其中，

C

的空間容量為|

C

|，

C

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

ψ

|≤|

C

|

.

定義5.

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

.

給定緩存

C

和查詢(xún)請(qǐng)求

Q

,完全命中表示

C

的最短路徑集

ψ

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

v

,

v

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

P

)={

P

,|(

v

∈

P

,)∧(

v

∈

P

,)∧ (

v

≠

v

),

P

,∈

ψ

}；部分命中表示

ψ

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

v

或

v

的最短路徑，部分命中

v

的路徑集可形式化為ц(

v

)={

P

,|(

v

∈

P

,)∧(

v

?

P

,),

P

,∈

ψ

}；否則稱(chēng)為未命中，即

ψ

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

v

或

v

的最短路徑

P

，未命中可形式化為?

P

∈

ψ

,(

v

?

P

)∧(

v

?

P

)∧(

v

≠

v

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

ψ

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

Q

的結(jié)果

.

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

.

定義6.

連接路徑

.

給定最短路徑

P

,和

P

′,′，節(jié)點(diǎn)

v

,

v

∈

P

,，

v

,

v

∈

P

′,′，存在子路徑〈

v

→…→

v

〉?

P

,和〈

v

→…→

v

〉?

P

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

.

通過(guò)

v

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

v

到

v

再到

v

的新路徑，該路徑稱(chēng)為連接路徑

JPath

(

v

,

v

)=〈

v

→…→

v

→…→

v

〉

.

其中連接路徑

JPath

(

v

,

v

)可近似為最短路徑

P

，用于應(yīng)答查詢(xún)請(qǐng)求

Q

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

.

2.2 問(wèn)題定義

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

定義7.

CTSPQ

(

G

,

v

,

v

,

C

,

T

,

T

)

.

給定節(jié)點(diǎn)

v

,

v

∈

G

，

C

為時(shí)刻

T

的緩存，

T

為每條最短路徑在

C

中滯留的最長(zhǎng)時(shí)間

.

記

ψ

為時(shí)刻

T

之前存入

C

的

n

條最短路徑集合，

Ω

為時(shí)刻

T

待存入

C

的

m

條最短路徑集合，

Sh

為

Pi

∈(

ψ

∪

Ω

)的共享能力，

t

為

Pi

存入

C

的時(shí)刻

.

0-1變量

x

表示

Pi

是否存儲(chǔ)于

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ù)器的計(jì)算量最小

.

其中，

B

(

ψ

,

Ω

,

T

,

T

)滿足：

(1)

緩存技術(shù)之所以能提高路徑查詢(xún)速度是因?yàn)槠淇梢越档头?wù)器對(duì)數(shù)據(jù)庫(kù)的讀操作

.

因此，能否較好地解決CTSPQ問(wèn)題取決于

C

中

ψ

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

.

此外，加入緩存

C

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

C

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

v

到

v

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

P

.

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

O

(

n

|

C

|)，是一個(gè)偽多項(xiàng)式問(wèn)題

.

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

.

3 基于緩存的時(shí)變最短路徑緩存查詢(xún)算法

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

v

(

lat

,

lng

)和目標(biāo)點(diǎn)

v

(

lat

,

lng

)的查詢(xún)請(qǐng)求

Q

(步驟①)；通過(guò)查詢(xún)請(qǐng)求模塊將

v

(

lat

,

lng

),

v

(

lat

,

lng

)映射為節(jié)點(diǎn)

v

,

v

∈

G

，以轉(zhuǎn)化為

G

上的查詢(xún)請(qǐng)求，繼而從緩存

C

中獲取

Q

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

Q

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

Q

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

C

(步驟⑨～⑩)

.

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

3.1 緩存管理模塊

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

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

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

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

=〈

v

→

v

→

v

→

v

〉存放節(jié)點(diǎn)的順序?yàn)?p>v

,

v

,

v

,

v

.

當(dāng)存在查詢(xún)請(qǐng)求

Q

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

v

到

v

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

Q

.

如查詢(xún)請(qǐng)求

Q

可由圖2中的

P

應(yīng)答

.

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

v

存儲(chǔ)了3次，

v

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

P

是

P

的子路徑

.

Fig. 2 An example of simple cache storage圖2 簡(jiǎn)單緩存實(shí)例圖

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

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

ANI

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

BMI

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

PII

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

ANI.

ANI

記錄了緩存

C

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

v

,

v

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

.

其中，每個(gè)鄰接點(diǎn)對(duì)在

ANI

中最多存儲(chǔ)一次，表示

C

中至少存在一條從

v

到

v

(或從

v

到

v

)的路徑

.ANI

引用了文獻(xiàn)[8]的模型，它無(wú)需存儲(chǔ)

G

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

C.

以圖3(a)為例，

v

的鄰接點(diǎn)有

v

，

v

和

v

，存在路徑

P

,

P

經(jīng)過(guò)

v

到達(dá)

v

；

P

,

P

經(jīng)過(guò)

v

到達(dá)

v

.

雖無(wú)路徑經(jīng)過(guò)

v

到達(dá)

v

，但存在經(jīng)過(guò)

v

到達(dá)

v

的路徑

P

,

P

和

P

，故

ANI

記錄了鄰接點(diǎn)對(duì)〈

v

,

v

〉的關(guān)系

.

2) 位圖索引

BMI.

BMI

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

P.

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

P

=〈

v

→

v

→

v

〉上的節(jié)點(diǎn)

v

,

v

,

v

在

BMI

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

.

因?yàn)槲粓D可以執(zhí)行二進(jìn)制操作，因此

BMI

可以快速識(shí)別查詢(xún)請(qǐng)求的候選路徑，并快速判斷

C

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

.

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

Q

和

Q

的候選路徑

.

令操作

BMI

(

v

)表示求解節(jié)點(diǎn)

v

所在的路徑集合，請(qǐng)求

Q

通過(guò)執(zhí)行

BMI

(

v

)∩

BMI

(

v

)={

P

,

P

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

Q

執(zhí)行

BMI

(

v

)∩

BMI

(

v

)=?，無(wú)完全命中的候選路徑集，但可以通過(guò)部分命中操作獲取與源點(diǎn)

v

和目標(biāo)點(diǎn)

v

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

BMI

(

v

)={

P

,

P

},

BMI

(

v

)={

P

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

Q

的連接路徑，即通過(guò)

v

連接候選路徑

P

和

P

獲得答查詢(xún)請(qǐng)求的候選連接路徑

JPath

(

v

,

v

)=〈

v

→

v

→

v

→

v

〉

.

3) 路徑信息索引

PII.

PII

記錄了

ψ

中每條路徑

P

的基本信息〈

t

，

Sh

〉，用于更新緩存

C

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

.

其中

t

表示

P

加入

C

的時(shí)刻、

Sh

表示

P

的共享能力(見(jiàn)定義8)

.

利用

t

計(jì)算

P

在

C

中滯留的時(shí)長(zhǎng)，當(dāng)時(shí)長(zhǎng)超過(guò)

T

時(shí)，從

C

中移除

P

；

Sh

用于判斷

P

是否被新路徑置換，因?yàn)槁窂焦蚕砟芰κ欠从陈窂绞軞g迎程度和重要性的指標(biāo)，是計(jì)算緩存收益的主要影響因素

.

定義8.

路徑共享能力

.

給定道路網(wǎng)

G

=(

V

,

E

,

W

,

T

)上的一條最短路徑

P

=〈

v

→

v

→…→

v

〉，

P

的路徑共享能力記做

Sh

.

歸一化的

Sh

可形式化為

(2)

其中,0≤

μ

，

μ

，

μ

≤1，

μ

+

μ

+

μ

=1；

QS

為當(dāng)前

G

中所有查詢(xún)請(qǐng)求的集合，|

QS

|為

QS

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

QS

|為節(jié)點(diǎn)

v

∈

P

在

QS

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

d

|為節(jié)點(diǎn)

v

∈

V

的度數(shù)；|

E

|表示邊

E

的數(shù)量；|

V

|為節(jié)點(diǎn)集

V

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

P

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

P

|=

n.

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

G

′，令圖2(b)中最短路徑的查詢(xún)請(qǐng)求為查詢(xún)請(qǐng)求集

QS

,

μ

=0

.

4,

μ

=0

.

2,

μ

=0

.

4；故|

QS

|=5,|

E

|=7,|

V

|=7

.

若求解

P

=〈

v

→

v

→

v

→

v

→

v

→

v

〉共享能力，可知

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

.

算法1展示了在時(shí)刻

T

將最短路徑

P

加入緩存

C

的偽代碼

.

假設(shè)

P

的共享能力為

Sh

，首先獲取

C

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

P

上的節(jié)點(diǎn)

v

及其鄰接點(diǎn)

v

+1∈

P

，并將2點(diǎn)添加至

BMI

,

ANI

中，其中，若

ANI

中已存在鄰接點(diǎn)對(duì)〈

v

,

v

+1〉的信息，則無(wú)需對(duì)索引

ANI

進(jìn)行操作(行②～④)

.

最后將

P

的信息〈

T

，

Sh

〉存入

PII

，并返回

C

(行⑤～⑥)

.

算法1.

插入算法

Insert

(

P

,

C

,

T

,

Sh

)

.

輸入：新路徑

P

、緩存

C

、當(dāng)前時(shí)間

T

、共享能力

Sh

；輸出：緩存

C.

①

ANI

,

BMI

,

PII

←

get

(

C

);

/

*從緩存

C

中獲取索引信息*

/

② for each node

v

in

P

③

add

(

ANI

,

BMI

,

v

,

v

,

P

);

/

*分別在

ANI

,

BMI

中添加鄰接點(diǎn)對(duì)〈

v

,

v

+1〉及路徑

v

∈

P

信息*

/

④ end for

⑤

addPII

(

PII

,

T

,

Sh

);

/

*將

P

的信息加入

PII

*

/

⑥ return

C.

以圖3為例，令

T

=1,|

ψ

|=0，此時(shí)向

C

中添加共享能力為0

.

511 4的最短路徑

P

=〈

v

→

v

→

v

〉

.

首先從

v

開(kāi)始，在

ANI

中加入

v

的鄰接點(diǎn)

v

，

v

的鄰接點(diǎn)

v

，在

BMI

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

v

∈

P

；然后在

ANI

中加入

v

的鄰接點(diǎn)

v

，

v

的鄰接點(diǎn)

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)前時(shí)間

T

；輸出：緩存

C.

①

Z

←空棧,

D

←空集合;②

ANI

,

BMI

,

PII

←

get

(

C

);

/

*從緩存

C

中獲取索引信息*

/

③

v

′←

random

(

P

);

/

*隨機(jī)獲取

P

上的一個(gè)節(jié)點(diǎn)*

/

④

Z.push

(

P

,

v

′,

D

);

/

*將節(jié)點(diǎn)

v

′入棧

Z

*

/

⑤ while 棧

Z

中存在元素時(shí)⑥

v

←

Z.pop

();

/

*出棧

Z

中的元素放入

v

*

/

⑦ if節(jié)點(diǎn)

v

′和

v

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

P

⑧

delete

(

ANI

,

v

,

v

′ );

/

*在

ANI

中刪除鄰接點(diǎn)對(duì)〈

v

,

v

′ 〉的信息*

/

⑨ end if

⑩

D.add

(

v

)；

/

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

/

中的鄰接點(diǎn)入棧

Z

*

/

/

*刪除

PII

,

BMI

中

P

*

/

3.1.2 緩存收益模型

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

C

，直到

C

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

O

(

n

lg

n

)

.

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

C

的方法

.

在道路網(wǎng)子圖

G

′上，首先為方便計(jì)算

C

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

ψ

|，舉例時(shí)僅考慮

PII

及

ANI

的占用空間

.

令一個(gè)節(jié)點(diǎn)的占用空間為1，一條

PII

信息占用空間為2，

T

=6，初始化|

ψ

|=0，|

C

|=16

.

在

T

=1時(shí)，待加入

C

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

Sh

>

Sh

>

Sh

.

故首先確定

P

加入

C

需要在

ANI

中增加10個(gè)節(jié)點(diǎn)(5個(gè)鄰接點(diǎn)對(duì))，故將

P

加入

C

時(shí)|

ψ

|=10+2<|

C

|；接著

P

是

P

的子路徑，只需增加

PII

信息，加入

C

時(shí)|

ψ

|=12+2<|

C

|；最后判斷

P

加入

C

還需在

ANI

中新增鄰接點(diǎn)對(duì)〈

v

,

v

〉，占用4個(gè)空間，而|

ψ

|+4=18>|

C

|，故

P

不被加入

C.

此時(shí)緩存中的共享能力總和為0

.

861 9+0

.

695 2=1

.

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

v

～

v

之間的查詢(xún)請(qǐng)求

.

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

P

是

P

的子路徑

.

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

.

因此在第3

.

1

.

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

.

Fig. 4 Example diagram of TSPC strategy圖4 TSPC策略實(shí)例圖

3.1.3 改進(jìn)存儲(chǔ)策略

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

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

定義9.

相似度度量

.

給定最短路徑

P

和

P

以及相似度約束值

τ

，

P

和

P

相似度為

(3)

其中,|

S

(

P

)∩

S

(

P

)|表示

P

和

P

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

P

|,|

P

|)表示

P

和

P

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

τ

的取值范圍為[0,1]

.

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

P

|,|

P

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

.

其中，

τ

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

τ

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

.

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

O

(

kn

+

n

lg

n

)，其中

k

表示|

ψ

|=

k

，

n

表示在時(shí)刻

T

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

O

(

n

lg

n

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

O

(

kn

)表示構(gòu)建

k

條互不相似最短路徑的最大開(kāi)銷(xiāo)

.

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

O

(

n

lg

n

)，即共享能力最大的前

k

條最短路徑兩兩不相似

.

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

C

的方法

.

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

τ

=0

.

7

.

當(dāng)

T

=1時(shí)，首先對(duì)待加入

C

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

Sh

>

Sh

>

Sh

.

由TSPC策略可知，先將

P

加入緩存

C

，此時(shí)|

ψ

|=12<|

C

|；接著判斷

P

與

C

中路徑集

ψ

的相似度，由

Sim

(

P

，

P

)=1>

τ

可知，

C

拒絕

P

的加入；接著判斷

P

與

C

中

ψ

的相似度，即

Sim

(

P

,

P

)=2

/

3<

τ

，此時(shí)將

P

加入

C

需在

ANI

中新增鄰接點(diǎn)對(duì)〈

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)答的查詢(xún)，還可以通過(guò)構(gòu)建連接路徑應(yīng)答與

v

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

.

此外，當(dāng)

T

=7時(shí)，待加入

C

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

Sh

>

Sh

.

首先由

T

-

T

=1可知，在1時(shí)之前加入

C

的路徑已逾時(shí)，故清空緩存

C

，|

C

|=0

.

接著將

P

加入

C

，空間容量|

ψ

|=10<|

C

|，然后判斷

P

與

C

中

ψ

的相似度，

Sim

(

P

,

P

)=2

/

3<

τ

滿足約束條件，還需在

ANI

中增加鄰接點(diǎn)對(duì)〈

v

,

v

〉、

PII

中增加基本信息，|

ψ

|+4=14<|

C

|，故可將

P

加入

C.

算法3.

TSPC更新緩存算法

Update

(

C

,

P

,

T

,

T

,

τ

)

.

輸入：緩存

C

、最短路徑

P

、當(dāng)前時(shí)間

T

、最大滯留時(shí)間

T

、相似度閾值

τ

；輸出：緩存

C.

①

Z

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

D

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

Sh

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

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

入隊(duì)

Z

*

/

⑧ else if

Sh

<

Sh

⑨

D.add

(

Pi

);

/

*將路徑

Pi

入隊(duì)

D

*

/

⑩ end if

/

*刪除緩存

C

中與

Z

有關(guān)的路徑*

/

/

*將

P

加入緩存

C

*

/

/

*將緩存

C

中與

Z

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

/

/

*出隊(duì)

D

中的路徑并刪除緩存

C

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

C

|≥|

ψ

+

P

|*

/

3.2 查詢(xún)請(qǐng)求檢測(cè)模塊

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

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

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

G

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

Q

的候選路徑集時(shí)，只需通過(guò)當(dāng)前緩存中BMI的信息查詢(xún)與源點(diǎn)

v

和目標(biāo)點(diǎn)

v

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

v

)和ц(

v

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

P

)

.

3.3 最短路徑評(píng)估模塊

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

直接查詢(xún)操作DQO表示從ц(

P

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

Q

.

DQO可形式化為

DQO

(ц(

P

),

T

,

T

)，滿足：

(4)

連接查詢(xún)操作JQO表示從ц(

v

)及ц(

v

)中各任選一條路徑

P

∈ц(

v

),

P

′∈ц(

v

)來(lái)組成連接路徑

JPath

(

v

,

v

)應(yīng)答

Q

.

其中，

JPath

(

v

,

v

)需要滿足時(shí)間約束

T

以及歐氏距離約束

EDR

(

v

,

v

,

v

)

.

JQO形式化為

JQO

(

v

,

v

,

θ

,

T

,

T

)，滿足：

(5)

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

θ

，是因?yàn)檫B接路徑

JPath

(

v

,

v

)的連接點(diǎn)

v

可能偏離最短路徑

P

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

.

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

v

的偏離程度，即：

(6)

表示從

v

到

v

和

v

到

v

的歐氏距離之和與

v

到

v

的歐氏距離比小于

θ.θ

的大小影響連接路徑的旅行時(shí)間，

θ

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

θ

=1時(shí)并不一定是最短路徑

.

算法4.

查詢(xún)算法

CTSPQ

(

C

,

Q

,

G

,

θ

,

T

)

.

輸入：緩存

C

、查詢(xún)請(qǐng)求

Q

、道路網(wǎng)

G

、歐氏距離比

θ

、最大滯留時(shí)間

T

；輸出：最短路徑

P.

① ц(

v

),ц(

v

)←空棧;

P

←空集;

sign

←false;

PII

,

ANI

,

BMI

←從緩存

C

中

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

②

v

,

v

←

KD

-

tree

(

Q

,

G

);

/

*查詢(xún)請(qǐng)求映射*

/

③ ц(

v

)←

BMI

(

v

)；

/

*獲取

v

所在的路徑*

/

④ ц(

v

)←

BMI

(

v

)；

/

*獲取

v

所在的路徑*

/

⑤ if ц(

v

)∩ц(

v

)的路徑集合不為空⑥

P

←

DQO

(

v

,

v

,

T

,

T

);

/

*見(jiàn)式(4)*

/

⑦ return

P

；

/

*返回路徑

P

*

/

⑧ else

⑨

P

←

JQO

(

v

,

v

,ц(

v

),ц(

v

),

θ

)；

/

*見(jiàn)式(5)*

/

⑩ if 存在連接路徑

P

/

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

/

以圖3為例，在時(shí)刻

T

發(fā)出查詢(xún)請(qǐng)求

Q

，首先將

Q

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

G

′上的節(jié)點(diǎn)

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ù)獲得

.

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

P

為例說(shuō)明如何確定路徑走向

.

令

D

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

Z

記錄已訪問(wèn)但未檢索鄰接點(diǎn)的節(jié)點(diǎn)，第1步，通過(guò)

random

(

P

)函數(shù)隨機(jī)獲取節(jié)點(diǎn)

v

為

P

檢索起點(diǎn)，

Z

={

v

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

ANI

檢索既在

P

上又是

v

鄰接點(diǎn)的節(jié)點(diǎn){

v

,

v

}，此時(shí)

D

={

v

},

Z

={

v

,

v

}

.

第3步，

Z

出棧

v

，在

P

上

v

的鄰接點(diǎn)集為{

v

},

v

∈

D

已被訪問(wèn)，且無(wú)其他鄰接點(diǎn)，故可確定

P

的一段子路徑為〈

v

→

v

〉，此時(shí)

D

={

v

,

v

}、

Z

={

v

}

.

同理，

Z

出棧

v

，找到

v

鄰接點(diǎn)

v

,

v

，而

v

∈

D

已被訪問(wèn)，得到

P

的另一段子路徑〈

v

→

v

→

v

〉，此時(shí)

D

={

v

,

v

,

v

}，

Z

={

v

}

.Z

出棧

v

，其在

P

上的鄰接點(diǎn)為{

v

}，而

v

∈

D

，

Z

=?，已遍歷上的

P

所有節(jié)點(diǎn)，故通過(guò)檢索起點(diǎn)

v

連接2條子路徑段可確定

P

的旅行方向?yàn)椤?p>v

→

v

→

v

→

v

〉

.

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

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

4.1 實(shí)驗(yàn)設(shè)置

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

Table 2 Experiment Environment

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

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

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

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

T

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

4.3 實(shí)驗(yàn)結(jié)果

4.3.1 映射

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

G

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

G

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

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

4.3.2 緩存大小

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

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

C

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

在圖6(b)中，隨著緩存容量的增加，TSPC的命中率逐漸趕超Baseline的命中率.是因?yàn)槭芟嗨贫鹊募s束，TSPC緩存的節(jié)點(diǎn)種類(lèi)比Baseline的多，可通過(guò)連接操作得到應(yīng)答查詢(xún)請(qǐng)求的路徑.正因相似度約束，TSPC緩存的數(shù)據(jù)量并不會(huì)因?yàn)榫彺嫒萘康臒o(wú)限擴(kuò)大而增加，緩存中的數(shù)據(jù)量會(huì)維持在一個(gè)范圍內(nèi).

4.3.3 參數(shù)

θ

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

θ

，意味著連接路徑的長(zhǎng)度不會(huì)被無(wú)線延伸，可避免偏差較大的候選路徑.圖7顯示了在不同

θ

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

θ

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

θ

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

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

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

4.3.4 參數(shù)

τ

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

τ

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

τ

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

.

當(dāng)

τ

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

τ

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

τ

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

τ

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

τ

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

5 總 結(jié)

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

作者貢獻(xiàn)聲明

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