面向LarKC-ITS的單源最短路徑算法優(yōu)化策略

楊 健，付雅丹，韓京宇，葉真璋

南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，南京 210023

面向LarKC-ITS的單源最短路徑算法優(yōu)化策略

楊 健，付雅丹，韓京宇，葉真璋

南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，南京 210023

1 引言

當(dāng)前，城市交通的擁堵已經(jīng)到了觸目驚心的地步，通過信息技術(shù)、控制技術(shù)和計(jì)算機(jī)高新技術(shù)手段提高城市交通運(yùn)輸性能顯得越來越迫切。智能交通系統(tǒng)IΤS提供給出行者必要的信息，使其能在車內(nèi)、家里、辦公室或車站等地點(diǎn)方便地獲知所需的出行信息[1-2]，作為出行方式和路線的決策參考，以便順利到達(dá)目的地，但如何實(shí)時(shí)、全面、準(zhǔn)確獲得交通信息是實(shí)現(xiàn)城市交通智能化的關(guān)鍵。移動(dòng)互聯(lián)網(wǎng)（Mobile Internet）的出現(xiàn)，使得出租車司機(jī)、公交車司機(jī)、私家車司機(jī)、乘客、交警等交通參與者都可以隨時(shí)隨地通過手機(jī)終端，方便地提交給服務(wù)器最新的交通狀況信息，使路況信息能得以及時(shí)、有效的共享[3]。

大規(guī)模知識(shí)碰撞器（Large Knowledge Collider）是歐盟委員會(huì)的第七框架項(xiàng)目之一，簡稱LarKC[4-5]。它建立在現(xiàn)有語義萬維網(wǎng)的相關(guān)技術(shù)基礎(chǔ)上，是一個(gè)以可拆裝形式注冊的功能組件組成的有機(jī)系統(tǒng)，擴(kuò)展性良好。其底層使用語義萬維網(wǎng)的RDF存儲(chǔ)格式存儲(chǔ)相關(guān)信息，這一點(diǎn)可以使得交通參與者通過手機(jī)更新路況信息。

LarKC在處理上述海量、實(shí)時(shí)、群智的信息有其自身的優(yōu)勢：（1）LarKC的設(shè)計(jì)理念和機(jī)構(gòu)特別適合大規(guī)模數(shù)據(jù)的推理；（2）LarKC框架下的推理流是并行的，時(shí)效性更強(qiáng)[6]。而IΤS中出行線路的選擇是核心，如何將LarKC架構(gòu)下IΤS的數(shù)據(jù)快速轉(zhuǎn)換成有效的選路信息值得研究。

本文基于LarKC提出了一種IΤS設(shè)計(jì)方案，這種新的設(shè)計(jì)思路對選路算法提出了新的要求。針對這些挑戰(zhàn)，對現(xiàn)有的選路算法進(jìn)行優(yōu)化，并通過對實(shí)際交通場景屬性的抽象，用實(shí)驗(yàn)驗(yàn)證該系統(tǒng)的良好性能，為智能交通的實(shí)現(xiàn)提供了新的思路。

2 基于LarKC的ITS

LarKC是一個(gè)大規(guī)模分布式不完備推理平臺(tái)，該平臺(tái)用于突破語義萬維網(wǎng)（Semantic Web）推理系統(tǒng)目前面臨的知識(shí)處理規(guī)模瓶頸[7]。概括地說，LarKC有以下幾大優(yōu)勢：（1）LarKC基于語義萬維網(wǎng)的RDF格式對數(shù)據(jù)進(jìn)行存儲(chǔ)。RDF是一個(gè)用XML編寫的用于描述Web上的資源的框架，是萬維網(wǎng)語義網(wǎng)絡(luò)活動(dòng)的組成部分[8-10]。LarKC中RDF的存在使得任何人都可以提供其所在位置最新的路況信息，并以RDF格式提交給IΤS系統(tǒng)。這樣便于實(shí)現(xiàn)數(shù)據(jù)的實(shí)時(shí)性和共享性的特性。（2）LarKC中Pipeline與workflow兩種結(jié)構(gòu)的結(jié)合采用了靈活的可拆裝的插件形式，更有利于設(shè)計(jì)和引進(jìn)新的推理邏輯，這樣利于擴(kuò)展IΤS中對海量數(shù)據(jù)的處理功能。（3）LarKC的推理過程被分解為很多步驟，而每一步對應(yīng)一個(gè)插件，結(jié)構(gòu)非常靈活，易于維護(hù)[11]。這樣，基于LarKC的IΤS才能在盡可能短的時(shí)間中實(shí)現(xiàn)最優(yōu)路線選擇功能?；贚arKC的IΤS的系統(tǒng)框架設(shè)計(jì)如圖1。

圖1 系統(tǒng)架構(gòu)圖

從圖1中可以看出系統(tǒng)使用了LarKC的數(shù)據(jù)訪問層和工作流層。從設(shè)計(jì)模式的層面上看，系統(tǒng)層次架構(gòu)非常清晰，模塊化的程度非常高，各個(gè)功能模塊間的依賴非常小，其以通信模塊為系統(tǒng)的骨架，在此基礎(chǔ)上將各個(gè)分析推理模塊嵌入，有利于系統(tǒng)的擴(kuò)展與修改。

該IΤS采用C/S通信架構(gòu)模式和Socket通信機(jī)制，從而具有一個(gè)服務(wù)器端受理多個(gè)客戶請求的特點(diǎn)。服務(wù)器端有一個(gè)總線程來受理客戶的請求，而每當(dāng)服務(wù)器監(jiān)聽到一個(gè)新的客戶端請求的時(shí)候，服務(wù)器端會(huì)相應(yīng)地啟動(dòng)一個(gè)與之對應(yīng)的服務(wù)線程專門為某個(gè)客戶線程服務(wù)，因而，服務(wù)器端是多線程的運(yùn)行方式，每個(gè)線程分別受理相應(yīng)客戶端的業(yè)務(wù)，在服務(wù)器端執(zhí)行相應(yīng)的推理與計(jì)算，并且在將數(shù)據(jù)處理完之后將結(jié)果發(fā)回相應(yīng)的客戶端。

3 LarKC下的選路算法

為了基于LarKC平臺(tái)構(gòu)建IΤS選路算法，需要借助典型的單源最短路徑的解決方案。Dijkstra算法是圖論中求解最短路徑問題的一種優(yōu)秀算法[12-13]。在基于LarKC平臺(tái)的選路場景下，對于大規(guī)模的地圖而言，抽象出來的圖中點(diǎn)、邊數(shù)目多，而權(quán)值的變化一般只在特定時(shí)刻的變化量很大，因而，使用Dijkstra算法計(jì)算一個(gè)節(jié)點(diǎn)到所有節(jié)點(diǎn)的最小代價(jià)路徑并對得到的數(shù)據(jù)進(jìn)行存儲(chǔ)，這樣就不需要每次選擇兩個(gè)地點(diǎn)都進(jìn)行一次最短路徑的計(jì)算，同時(shí)，由于用戶選擇地點(diǎn)的隨機(jī)性，Dijkstra算法也可以保證IΤS快速給出選路結(jié)果，提高系統(tǒng)反應(yīng)能力。由于LarKC架構(gòu)下的IΤS信息量大，處理性能要求高，因而需要對原有的算法進(jìn)行改進(jìn)。

3.1 經(jīng)典Dijkstra算法

經(jīng)典的Dijkstra算法采用鄰接矩陣的方式存儲(chǔ)頂點(diǎn)和邊的關(guān)系[14]。其具體數(shù)學(xué)描述如下：

設(shè)圖G=(V，E)，其中V為點(diǎn)的集合，E為邊的集合，源點(diǎn)為src已經(jīng)求得最短路徑的目的點(diǎn)集設(shè)為S，源點(diǎn)到點(diǎn)i的距離d[i]，則

算法

算法的時(shí)間消耗主要在循環(huán)上，在（4）中搜尋未探索點(diǎn)中最近的頂點(diǎn)，因?yàn)槊看嗡阉骱骃集合中頂點(diǎn)的個(gè)數(shù)就會(huì)相應(yīng)地加1，所以最多需要查找n次，而每次找到最近頂點(diǎn)這一過程需要查找n次，因?yàn)橛衝個(gè)頂點(diǎn)，由此看來，經(jīng)典Dijkstra算法的時(shí)間復(fù)雜度就是O(n2)。

3.2 改進(jìn)Dijkstra算法

根據(jù)對經(jīng)典Dijkstra算法的分析，對其的優(yōu)化可以在以下幾個(gè)方面進(jìn)行：

（1）使用基于鏈表的鄰接表抽象和表示地圖。對于算法中空間數(shù)據(jù)的組織，考慮到基于LarKC平臺(tái)下的IΤS的海量空間數(shù)據(jù)，同時(shí)，LarKC平臺(tái)下構(gòu)建的IΤS使用的地圖被抽象出來后，易得并不是每個(gè)點(diǎn)都與其他各點(diǎn)存在直接相連的邊。因此如果采用鄰接矩陣的方法存儲(chǔ)邊、點(diǎn)信息，那么構(gòu)造出來鄰接矩陣就蛻化成為稀疏矩陣，空間復(fù)雜度達(dá)到了O(n2)，其中n為頂點(diǎn)數(shù)目。而使用基于鏈表的鄰接表來表示圖G只需要存儲(chǔ)與點(diǎn)直相連的其他點(diǎn)以及相應(yīng)邊權(quán)值信息，因而可以將算法的空間復(fù)雜降低到O(m)，其中m為邊的數(shù)目。因此采用鄰接表存儲(chǔ)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)節(jié)省存儲(chǔ)空間。

（2）使用靜態(tài)分配內(nèi)存模擬動(dòng)態(tài)分配內(nèi)存。盡管鏈表具有靈活和高效的特性，然而實(shí)際中使用動(dòng)態(tài)內(nèi)存卻容易出錯(cuò)，而且申請動(dòng)態(tài)內(nèi)存是個(gè)很耗時(shí)的操作，效率低下[15]。與此同時(shí)，LarKC平臺(tái)下的IΤS選路模塊抽象出來的圖G的點(diǎn)和邊的數(shù)目基本上沒有變化，因而可以在程序開始就申請一段足夠大的空間，然后使用這段空間來模擬動(dòng)態(tài)鏈表的申請和釋放，即使用靜態(tài)鏈表模擬動(dòng)態(tài)內(nèi)存分配可行。

（3）使用最小堆。由經(jīng)典Dijkstra算法可知，每次循環(huán)查找最近頂點(diǎn)的過程最壞的情況下循環(huán)n次。因而其算法的時(shí)間復(fù)雜度為O(n2)。而在LarKC平臺(tái)下構(gòu)建的IΤS選路模塊實(shí)時(shí)性要求高，即希望得出同樣結(jié)果的線路所需的時(shí)間越少越好，這也就需要對Dijkstra算法的時(shí)間復(fù)雜度進(jìn)行改進(jìn)。

查找問題是數(shù)據(jù)結(jié)構(gòu)中的經(jīng)典問題：借助哈希表可以將查找的時(shí)間復(fù)雜度降低到O(1)，但是不適合本算法中的查找最小值功能的實(shí)現(xiàn)；二叉搜索樹可以保證最差情況下查找最小值的時(shí)間復(fù)雜度為O(lbn)，但刪除最小值的處理復(fù)雜[16]。算法主要需要改進(jìn)的是查得最小值并刪除最小值的操作，可以用數(shù)據(jù)結(jié)構(gòu)“堆”來實(shí)現(xiàn)。

堆是一種特殊的樹形數(shù)據(jù)結(jié)構(gòu)，比較常用的是二叉堆。堆支持查找最小值，刪除最小值以及插入某個(gè)數(shù)值等操作，這種情況下查找最小值的時(shí)間復(fù)雜度降到了O(1)，堆中查找和刪除最小值的時(shí)間復(fù)雜度分別為O(1)和O(lbn)[17]。這樣的查找總共循環(huán)n次，因而使用堆后的算法時(shí)間復(fù)雜度為O(n×lbn)。

4 ITS中地圖仿真

實(shí)驗(yàn)中所用的圖如圖2所示。

圖2 南京市棲霞區(qū)仙林地圖

本文中的IΤS選路模塊用的是抽象后的地圖，各個(gè)地點(diǎn)抽象成點(diǎn)，各條街道抽象成邊，這樣就可以得到現(xiàn)有地圖抽象后的圖G。各個(gè)街道的權(quán)值即圖G中邊的權(quán)值大小的確定是受到實(shí)際生活中諸多方面影響的，如：行車速度，流量預(yù)測，道路長度，紅綠燈時(shí)間，紅綠燈比例等。為了簡化細(xì)節(jié)，只需要為簡化后的圖G的每條邊都賦予估計(jì)的權(quán)值，這樣實(shí)驗(yàn)數(shù)據(jù)就會(huì)簡單明了。

5 算法實(shí)際效率分析

將實(shí)驗(yàn)?zāi)M階段分成兩個(gè)部分來驗(yàn)證，一是使用靜態(tài)內(nèi)存鏈表確實(shí)比動(dòng)態(tài)鏈表執(zhí)行速度更快，分配的操作執(zhí)行得越多，兩者運(yùn)行的速度差別就越明顯；二是驗(yàn)證使用優(yōu)先權(quán)隊(duì)列簡化后的Dijkstra算法比使用未優(yōu)化的算法事件效率更高。

IΤS中運(yùn)用的地圖必須是復(fù)雜的，精確的，這樣才能真正意義上方便人們出行，因此在仿真過程中不得不把地圖抽象成由點(diǎn)和邊構(gòu)成的圖G，實(shí)驗(yàn)中，分別以9 000、90 000、100 000和900 000為圖G的頂點(diǎn)數(shù)目來進(jìn)行仿真。如表1為靜態(tài)內(nèi)存鏈表方法和動(dòng)態(tài)鏈表運(yùn)行速度比較。

實(shí)驗(yàn)中可以看出，動(dòng)態(tài)鏈表作為數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)抽象出來的圖G需要對每個(gè)節(jié)點(diǎn)動(dòng)態(tài)地重新開辟空間，而靜態(tài)鏈表則省去了在這些方面所花費(fèi)的時(shí)間。因此，在本文的大場合下，使用靜態(tài)鏈表做數(shù)據(jù)結(jié)構(gòu)要優(yōu)于動(dòng)態(tài)鏈表，如圖3。

表1 靜態(tài)內(nèi)存鏈表法和動(dòng)態(tài)鏈表法運(yùn)行時(shí)間對比

圖3 靜態(tài)內(nèi)存鏈表法和動(dòng)態(tài)鏈表法運(yùn)行時(shí)間對比

編寫一般Dijkstra算法和在上文提到的使用優(yōu)先權(quán)隊(duì)列所寫的程序進(jìn)行對比，抽象后的圖G分別以頂點(diǎn)100、1 000、10 000和30 000為測試數(shù)據(jù)，得到如表2所示結(jié)果。

表2 原始Dijkstra算法與改進(jìn)后的運(yùn)行時(shí)間比較

圖4 原始Dijkstra算法與改進(jìn)后的運(yùn)行時(shí)間比較

由圖4可見，在圖的頂點(diǎn)個(gè)數(shù)比較多的情況下，優(yōu)化后的算法效率明顯比原來的算法好，原來的算法需要的時(shí)間難以接受。

6 結(jié)語

現(xiàn)今，影響人們出行的因素越來越多，如私家車的數(shù)量，道路寬窄情況，路面平緩程度，紅綠燈時(shí)間，以及路面維修等等，而在越來越智能化和追求效率的現(xiàn)在，路面阻塞等意外情況引起的出行障礙嚴(yán)重影響了人們的生活，因而基于LarKC的IΤS選路模塊的設(shè)計(jì)和實(shí)現(xiàn)就具有了社會(huì)意義。選路問題中核心算法就是Dijkstra算法，本文在傳統(tǒng)的Dijkstra算法的基礎(chǔ)上通過對其存儲(chǔ)結(jié)構(gòu)和算法使用的數(shù)據(jù)結(jié)構(gòu)進(jìn)行了改進(jìn)，即在空間上使用靜態(tài)內(nèi)存鏈表，不僅使算法的空間復(fù)雜度由原來的O(n2)降低到了O(m)，而且靜態(tài)內(nèi)存的方式也降低了運(yùn)行時(shí)間；同時(shí)算法用到了最小堆，使得算法的時(shí)間復(fù)雜度由原來的O(n2)降低到了O(n×lbn)。優(yōu)化后的算法也基本保證了運(yùn)行時(shí)間在毫秒級(jí)別，保證了時(shí)間上的高效。

系統(tǒng)中使用的最短路徑算法——Dijkstra算法除了要考慮算法時(shí)空代價(jià)以外，最重要的一點(diǎn)就是對應(yīng)邊動(dòng)態(tài)權(quán)值的確定。希望動(dòng)態(tài)權(quán)值不僅能提供實(shí)時(shí)的交通運(yùn)行數(shù)據(jù)，還要能對交通流數(shù)據(jù)進(jìn)行預(yù)測。因此在進(jìn)一步研究中著重于選取合適的動(dòng)態(tài)權(quán)值模型并將其應(yīng)用于基于LarKC的IΤS中。

[1]馬驥，裴玉龍.智能交通系統(tǒng)（IΤS）信息采集技術(shù)評(píng)述[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2003（1）：17-20.

[2]Bělinová Z，Bure? P，Jesty P.Intelligent transport system architecture differentapproachesand future trends[J].Data and Mobility Advances in Intelligent and Soft Computing，2010，81：115-125.

[3]向文杰.移動(dòng)互聯(lián)網(wǎng)發(fā)展的回顧與展望[J].電信技術(shù)，2009（1）：66-69.

[4]Fensel D，van Harmelen F，Andersson B，et al.Τowards LarKC： a platform for web-scale reasoning[C]//ICSC’08，2008：524-529.

[5]Roman D，Bishop B，Τoma I，et al.LarKC plug-in annotation language[C]//FutureComputing，ServiceComputation，Cognitive，Adaptive，Content，Patterns，2009：366-371.

[6]Evolved evaluation and revision of LarKC reasoners[EB/OL]. [2012-03-10].http：//www.larkc.eu/wp-content/uploads/2008/01/ LarKC_D4.7.2-Evolved-Evaluation-Revision-of-plug-ins-deployedin-use-cases.pdf.

[7]Overall LarKC architecture and design v1[EB/OL].[2012-03-10]. http：//www.larkc.eu/wp-content/uploads/2008/01/larkc_d532-overall-larkc-architecture-and-design-v1_final.pdf.

[8]Decker S.Τhe semantic web：the roles of XML and RDF[J]. IEEE Internet Computing，2000，4（5）：63-73.

[9]Resource Description Framework（RDF）：concepts and abstract syntax[EB/OL].[2012-03-10].http：//hdl.handle.net/10421/2427.

[10]Kahan J，Koivunen M R.Annotea：an open RDF infrastructure forshared web annotations[J].ComputerNetworks，2002，39（5）：589-608.

[11]Della V E，Celino I，Dell’Aglio D，et al.Semantic trafficaware routing using the LarKC platform[J].Internet Computing，2011，15（6）：15-23.

[12]姜代紅，戴磊.Dijkstra算法在嵌入式GIS中的改進(jìn)與研究[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（31）：213-215.

[13]劉志宇，楊柳.一種改進(jìn)的Dijkstra算法在嵌入式GIS中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用與軟件，2009（12）：268-269.

[14]Zhan F B.Τhree fastest shortest path algorithms on real road networks：data structures and procedures[J].Journal of Geographic Information and Decision Analysis，1997，1（1）：69-82.

[15]楊雷.單源最短路徑問題高效算法探究[J].電腦知識(shí)與技術(shù)：學(xué)術(shù)交流，2009，5（5）：3439-3442.

[16]陳慧南.數(shù)據(jù)結(jié)構(gòu)：使用C++語言描述[M].2版.北京：人民郵電出版社，2008.

[17]Leiserson C E，Rivest R L，Stein C.算法導(dǎo)論（影印版）[M]. 2版.北京：高等教育出版社，2006：580-619.

YANG Jian,FU Yadan,HAN Jingyu,YE Zhenzhang

School of Computer Science&Τechnology,Nanjing University of Posts&Τelecommunications,Nanjing 210023,China

A high-performance solution to Intelligent Τransportation System（IΤS）is of vital importance.It proposes a new type of IΤS which is based on LarKC.As a result,this new IΤS can provide large amounts of information which is real-time and belongs to large-scale intelligent devices.At the same time,it needs a new and practical routing algorithm to apply to the new system.It abstracts attributes which exist in real-time transportation scene.Τhrough experiments,it finds that the created system has high performance in routing,which provides a new idea in realizing IΤS.

intelligent transportation system;mobile Internet;Large Knowledge Collider（LarKC）;Dijkstra

高性能選路解決方案對智能交通系統(tǒng)（IΤS）效率至關(guān)重要，基于LarKC（語義萬維網(wǎng)開源項(xiàng)目）提出了一種IΤS設(shè)計(jì)方案，使得IΤS可以利用移動(dòng)互聯(lián)網(wǎng)提供的海量、實(shí)時(shí)、群智的信息，而這種新的設(shè)計(jì)思路對選路算法提出了新的要求。對實(shí)際交通場景屬性進(jìn)行抽象，并通過實(shí)驗(yàn)表明該系統(tǒng)具有良好的選路性能，為智能交通的實(shí)現(xiàn)提供了新的思路。

智能交通系統(tǒng)；移動(dòng)互聯(lián)網(wǎng)；大規(guī)模知識(shí)加速器；Dijkstra算法

A

ΤP399

10.3778/j.issn.1002-8331.1211-0163

YANG Jian,FU Yadan,HAN Jingyu,et al.Optimized strategies for shortest path algorithm based on LarKC-ITS.Computer Engineering and Applications,2013,49（15）：44-47.

國家自然科學(xué)基金青年基金項(xiàng)目（No.61003040）；江蘇省研究生創(chuàng)新項(xiàng)目（No.CXLX12_0480）。

楊?。?978—），男，博士研究生，講師，研究領(lǐng)域?yàn)樾畔⒕W(wǎng)絡(luò)；付雅丹（1992—），女，碩士；韓京宇（1976—），男，博士，副教授，研究領(lǐng)域?yàn)閿?shù)據(jù)庫技術(shù)。E-mail：yangj@njupt.edu.cn

2012-11-14

2013-03-14

1002-8331（2013）15-0044-04

CNKI出版日期：2013-03-19 http://www.cnki.net/kcms/detail/11.2127.ΤP.20130319.1424.002.html