面向LarKC-ITS的单源最短路径算法优化策略

杨 健，付雅丹，韩京宇，叶真璋

南京邮电大学 计算机学院，南京 210023

面向LarKC-ITS的单源最短路径算法优化策略

杨 健，付雅丹，韩京宇，叶真璋

南京邮电大学 计算机学院，南京 210023

1 引言

当前，城市交通的拥堵已经到了触目惊心的地步，通过信息技术、控制技术和计算机高新技术手段提高城市交通运输性能显得越来越迫切。智能交通系统IΤS提供给出行者必要的信息，使其能在车内、家里、办公室或车站等地点方便地获知所需的出行信息[1-2]，作为出行方式和路线的决策参考，以便顺利到达目的地，但如何实时、全面、准确获得交通信息是实现城市交通智能化的关键。移动互联网（Mobile Internet）的出现，使得出租车司机、公交车司机、私家车司机、乘客、交警等交通参与者都可以随时随地通过手机终端，方便地提交给服务器最新的交通状况信息，使路况信息能得以及时、有效的共享[3]。

大规模知识碰撞器（Large Knowledge Collider）是欧盟委员会的第七框架项目之一，简称LarKC[4-5]。它建立在现有语义万维网的相关技术基础上，是一个以可拆装形式注册的功能组件组成的有机系统，扩展性良好。其底层使用语义万维网的RDF存储格式存储相关信息，这一点可以使得交通参与者通过手机更新路况信息。

LarKC在处理上述海量、实时、群智的信息有其自身的优势：（1）LarKC的设计理念和机构特别适合大规模数据的推理；（2）LarKC框架下的推理流是并行的，时效性更强[6]。而IΤS中出行线路的选择是核心，如何将LarKC架构下IΤS的数据快速转换成有效的选路信息值得研究。

本文基于LarKC提出了一种IΤS设计方案，这种新的设计思路对选路算法提出了新的要求。针对这些挑战，对现有的选路算法进行优化，并通过对实际交通场景属性的抽象，用实验验证该系统的良好性能，为智能交通的实现提供了新的思路。

2 基于LarKC的ITS

LarKC是一个大规模分布式不完备推理平台，该平台用于突破语义万维网（Semantic Web）推理系统目前面临的知识处理规模瓶颈[7]。概括地说，LarKC有以下几大优势：（1）LarKC基于语义万维网的RDF格式对数据进行存储。RDF是一个用XML编写的用于描述Web上的资源的框架，是万维网语义网络活动的组成部分[8-10]。LarKC中RDF的存在使得任何人都可以提供其所在位置最新的路况信息，并以RDF格式提交给IΤS系统。这样便于实现数据的实时性和共享性的特性。（2）LarKC中Pipeline与workflow两种结构的结合采用了灵活的可拆装的插件形式，更有利于设计和引进新的推理逻辑，这样利于扩展IΤS中对海量数据的处理功能。（3）LarKC的推理过程被分解为很多步骤，而每一步对应一个插件，结构非常灵活，易于维护[11]。这样，基于LarKC的IΤS才能在尽可能短的时间中实现最优路线选择功能。基于LarKC的IΤS的系统框架设计如图1。

图1 系统架构图

从图1中可以看出系统使用了LarKC的数据访问层和工作流层。从设计模式的层面上看，系统层次架构非常清晰，模块化的程度非常高，各个功能模块间的依赖非常小，其以通信模块为系统的骨架，在此基础上将各个分析推理模块嵌入，有利于系统的扩展与修改。

该IΤS采用C/S通信架构模式和Socket通信机制，从而具有一个服务器端受理多个客户请求的特点。服务器端有一个总线程来受理客户的请求，而每当服务器监听到一个新的客户端请求的时候，服务器端会相应地启动一个与之对应的服务线程专门为某个客户线程服务，因而，服务器端是多线程的运行方式，每个线程分别受理相应客户端的业务，在服务器端执行相应的推理与计算，并且在将数据处理完之后将结果发回相应的客户端。

3 LarKC下的选路算法

为了基于LarKC平台构建IΤS选路算法，需要借助典型的单源最短路径的解决方案。Dijkstra算法是图论中求解最短路径问题的一种优秀算法[12-13]。在基于LarKC平台的选路场景下，对于大规模的地图而言，抽象出来的图中点、边数目多，而权值的变化一般只在特定时刻的变化量很大，因而，使用Dijkstra算法计算一个节点到所有节点的最小代价路径并对得到的数据进行存储，这样就不需要每次选择两个地点都进行一次最短路径的计算，同时，由于用户选择地点的随机性，Dijkstra算法也可以保证IΤS快速给出选路结果，提高系统反应能力。由于LarKC架构下的IΤS信息量大，处理性能要求高，因而需要对原有的算法进行改进。

3.1 经典Dijkstra算法

经典的Dijkstra算法采用邻接矩阵的方式存储顶点和边的关系[14]。其具体数学描述如下：

设图G=(V，E)，其中V为点的集合，E为边的集合，源点为src已经求得最短路径的目的点集设为S，源点到点i的距离d[i]，则

算法

算法的时间消耗主要在循环上，在（4）中搜寻未探索点中最近的顶点，因为每次搜索后S集合中顶点的个数就会相应地加1，所以最多需要查找n次，而每次找到最近顶点这一过程需要查找n次，因为有n个顶点，由此看来，经典Dijkstra算法的时间复杂度就是O(n2)。

3.2 改进Dijkstra算法

根据对经典Dijkstra算法的分析，对其的优化可以在以下几个方面进行：

（1）使用基于链表的邻接表抽象和表示地图。对于算法中空间数据的组织，考虑到基于LarKC平台下的IΤS的海量空间数据，同时，LarKC平台下构建的IΤS使用的地图被抽象出来后，易得并不是每个点都与其他各点存在直接相连的边。因此如果采用邻接矩阵的方法存储边、点信息，那么构造出来邻接矩阵就蜕化成为稀疏矩阵，空间复杂度达到了O(n2)，其中n为顶点数目。而使用基于链表的邻接表来表示图G只需要存储与点直相连的其他点以及相应边权值信息，因而可以将算法的空间复杂降低到O(m)，其中m为边的数目。因此采用邻接表存储网络拓扑结构节省存储空间。

（2）使用静态分配内存模拟动态分配内存。尽管链表具有灵活和高效的特性，然而实际中使用动态内存却容易出错，而且申请动态内存是个很耗时的操作，效率低下[15]。与此同时，LarKC平台下的IΤS选路模块抽象出来的图G的点和边的数目基本上没有变化，因而可以在程序开始就申请一段足够大的空间，然后使用这段空间来模拟动态链表的申请和释放，即使用静态链表模拟动态内存分配可行。

（3）使用最小堆。由经典Dijkstra算法可知，每次循环查找最近顶点的过程最坏的情况下循环n次。因而其算法的时间复杂度为O(n2)。而在LarKC平台下构建的IΤS选路模块实时性要求高，即希望得出同样结果的线路所需的时间越少越好，这也就需要对Dijkstra算法的时间复杂度进行改进。

查找问题是数据结构中的经典问题：借助哈希表可以将查找的时间复杂度降低到O(1)，但是不适合本算法中的查找最小值功能的实现；二叉搜索树可以保证最差情况下查找最小值的时间复杂度为O(lbn)，但删除最小值的处理复杂[16]。算法主要需要改进的是查得最小值并删除最小值的操作，可以用数据结构“堆”来实现。

堆是一种特殊的树形数据结构，比较常用的是二叉堆。堆支持查找最小值，删除最小值以及插入某个数值等操作，这种情况下查找最小值的时间复杂度降到了O(1)，堆中查找和删除最小值的时间复杂度分别为O(1)和O(lbn)[17]。这样的查找总共循环n次，因而使用堆后的算法时间复杂度为O(n×lbn)。

4 ITS中地图仿真

实验中所用的图如图2所示。

图2 南京市栖霞区仙林地图

本文中的IΤS选路模块用的是抽象后的地图，各个地点抽象成点，各条街道抽象成边，这样就可以得到现有地图抽象后的图G。各个街道的权值即图G中边的权值大小的确定是受到实际生活中诸多方面影响的，如：行车速度，流量预测，道路长度，红绿灯时间，红绿灯比例等。为了简化细节，只需要为简化后的图G的每条边都赋予估计的权值，这样实验数据就会简单明了。

5 算法实际效率分析

将实验模拟阶段分成两个部分来验证，一是使用静态内存链表确实比动态链表执行速度更快，分配的操作执行得越多，两者运行的速度差别就越明显；二是验证使用优先权队列简化后的Dijkstra算法比使用未优化的算法事件效率更高。

IΤS中运用的地图必须是复杂的，精确的，这样才能真正意义上方便人们出行，因此在仿真过程中不得不把地图抽象成由点和边构成的图G，实验中，分别以9 000、90 000、100 000和900 000为图G的顶点数目来进行仿真。如表1为静态内存链表方法和动态链表运行速度比较。

实验中可以看出，动态链表作为数据结构存储抽象出来的图G需要对每个节点动态地重新开辟空间，而静态链表则省去了在这些方面所花费的时间。因此，在本文的大场合下，使用静态链表做数据结构要优于动态链表，如图3。

表1 静态内存链表法和动态链表法运行时间对比

图3 静态内存链表法和动态链表法运行时间对比

编写一般Dijkstra算法和在上文提到的使用优先权队列所写的程序进行对比，抽象后的图G分别以顶点100、1 000、10 000和30 000为测试数据，得到如表2所示结果。

表2 原始Dijkstra算法与改进后的运行时间比较

图4 原始Dijkstra算法与改进后的运行时间比较

由图4可见，在图的顶点个数比较多的情况下，优化后的算法效率明显比原来的算法好，原来的算法需要的时间难以接受。

6 结语

现今，影响人们出行的因素越来越多，如私家车的数量，道路宽窄情况，路面平缓程度，红绿灯时间，以及路面维修等等，而在越来越智能化和追求效率的现在，路面阻塞等意外情况引起的出行障碍严重影响了人们的生活，因而基于LarKC的IΤS选路模块的设计和实现就具有了社会意义。选路问题中核心算法就是Dijkstra算法，本文在传统的Dijkstra算法的基础上通过对其存储结构和算法使用的数据结构进行了改进，即在空间上使用静态内存链表，不仅使算法的空间复杂度由原来的O(n2)降低到了O(m)，而且静态内存的方式也降低了运行时间；同时算法用到了最小堆，使得算法的时间复杂度由原来的O(n2)降低到了O(n×lbn)。优化后的算法也基本保证了运行时间在毫秒级别，保证了时间上的高效。

系统中使用的最短路径算法——Dijkstra算法除了要考虑算法时空代价以外，最重要的一点就是对应边动态权值的确定。希望动态权值不仅能提供实时的交通运行数据，还要能对交通流数据进行预测。因此在进一步研究中着重于选取合适的动态权值模型并将其应用于基于LarKC的IΤS中。

[1]马骥，裴玉龙.智能交通系统（IΤS）信息采集技术评述[J].哈尔滨工业大学学报，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]向文杰.移动互联网发展的回顾与展望[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]陈慧南.数据结构：使用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

高性能选路解决方案对智能交通系统（IΤS）效率至关重要，基于LarKC（语义万维网开源项目）提出了一种IΤS设计方案，使得IΤS可以利用移动互联网提供的海量、实时、群智的信息，而这种新的设计思路对选路算法提出了新的要求。对实际交通场景属性进行抽象，并通过实验表明该系统具有良好的选路性能，为智能交通的实现提供了新的思路。

智能交通系统；移动互联网；大规模知识加速器；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）；江苏省研究生创新项目（No.CXLX12_0480）。

杨健（1978—），男，博士研究生，讲师，研究领域为信息网络；付雅丹（1992—），女，硕士；韩京宇（1976—），男，博士，副教授，研究领域为数据库技术。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