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

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

南京郵電大學 計算機學院，南京 210023

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

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

南京郵電大學 計算機學院，南京 210023

1 引言

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

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

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

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

2 基于LarKC的ITS

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

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

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

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

3 LarKC下的選路算法

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

3.1 經(jīng)典Dijkstra算法

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

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

算法

算法的時間消耗主要在循環(huán)上，在（4）中搜尋未探索點中最近的頂點，因為每次搜索后S集合中頂點的個數(shù)就會相應地加1，所以最多需要查找n次，而每次找到最近頂點這一過程需要查找n次，因為有n個頂點，由此看來，經(jīng)典Dijkstra算法的時間復雜度就是O(n2)。

3.2 改進Dijkstra算法

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

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

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

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

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

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

4 ITS中地圖仿真

實驗中所用的圖如圖2所示。

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

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

5 算法實際效率分析

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

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

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

表1 靜態(tài)內(nèi)存鏈表法和動態(tài)鏈表法運行時間對比

圖3 靜態(tài)內(nèi)存鏈表法和動態(tài)鏈表法運行時間對比

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

表2 原始Dijkstra算法與改進后的運行時間比較

圖4 原始Dijkstra算法與改進后的運行時間比較

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

6 結(jié)語

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

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

[1]馬驥，裴玉龍.智能交通系統(tǒng)（IΤS）信息采集技術評述[J].哈爾濱工業(yè)大學學報，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]向文杰.移動互聯(lián)網(wǎng)發(fā)展的回顧與展望[J].電信技術，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].計算機工程與應用，2011，47（31）：213-215.

[13]劉志宇，楊柳.一種改進的Dijkstra算法在嵌入式GIS中的應用[J].計算機應用與軟件，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].電腦知識與技術：學術交流，2009，5（5）：3439-3442.

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

[17]Leiserson C E，Rivest R L，Stein C.算法導論（影印版）[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）效率至關重要，基于LarKC（語義萬維網(wǎng)開源項目）提出了一種IΤS設計方案，使得IΤS可以利用移動互聯(lián)網(wǎng)提供的海量、實時、群智的信息，而這種新的設計思路對選路算法提出了新的要求。對實際交通場景屬性進行抽象，并通過實驗表明該系統(tǒng)具有良好的選路性能，為智能交通的實現(xiàn)提供了新的思路。

智能交通系統(tǒng)；移動互聯(lián)網(wǎng)；大規(guī)模知識加速器；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.

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

楊?。?978—），男，博士研究生，講師，研究領域為信息網(wǎng)絡；付雅丹（1992—），女，碩士；韓京宇（1976—），男，博士，副教授，研究領域為數(shù)據(jù)庫技術。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