（计算机应用技术专业论文）城市道路网模型研究.pdf

摘要 随着社会的发展，交通问题日益突出，人们对智能交通系统投入了越来越多的关 注，其中道路网模型作为智能交通系统的基础成为研究热点。目前，在大多数的研究 中，道路网作为空间网络被抽象为图模型。考虑到道路网的丰富特征、属性和复杂性 ( 如道路的转弯限制等交通约束) ，常规图模型己不能满足要求。因此，出现了结点 连接模型和伪二重图模型。这些模型以增加图中结点和弧数量为代价表示部分交通约 束( 如转弯限制) ，使得基于图算法的空间查询效率降低。 针对上述问题，一种超点模型提出将交通约束集中在各结点上，并以约束矩阵形 式表示。本论文在完善超点模型基础上，进行了以下几方面的实现：1 、使用扩展的 u m l 工具对道路网进行建模，利用图形来描述真实世界各个对象的符号表示。2 、给 出了与概念模型匹配的数据模型，通过融合代价弧与约束矩阵的标识符减少了数据冗 余。3 、对超点模型支持基于道路网的查询算法结合空间数据索引进行了研究。 论文最后对超点模型和结点连接模型进行了存储空间、查询支持等方面的模拟实 验与比较。结果显示，对同一道路网的表示，超点模型的存储开销小于后者；对连续 最近邻查询和区域查询，在超点模型上的实验效率均高于后者。表明超点模型不仅对 道路网和交通信息有着良好的表示，还能提高基于道路网的查询效率。 关键词：智能交通系统，交通地理信息系统，空间数据模型，道路网模型，r - t r e e a b s t r a c t a st h ep r o b l e mo ft r a n s p o r t a t i o ni si n c r e a s i n gt o d a y ，t h ei n t e l l i g e n tt r a n s p o r t a t i o n s y s t e m i s a r o u s i n gm o r ea n dm o r ea t t e n t i o n b e i n gt h eb a s i co ft h ei n t e l l i g e n t t r a n s p o r t a t i o ns y s t e m ，t h er o a dn e t w o r km o d e lb e c o m e st h ef o c u so ft h er e s e a r c h a t p r e s e n t ，r o a dn e t w o r ka sas p a t i a ln e t w o r ki sa b s t r a c t e dt ob eag r a p hi nm o s to ft h e r e s e a r c h e s c o n s i d e r i n gt h eu s u a lg r a p hc a n n o tm e e tt h ed e m a n do ft h ea m p l ef e a t u r e s 、 a t t r i b u t e sa n dc o m p l e x i t yo ft h er o a dn e t w o r k ，t h e r e a p p e a rn o d e - l i n km o d e la n d p s e u d o d u a lg r a p hm o d e l t h e s em o d e l sc a nd e s c r i b et h ep a r tt r a n s p o r tr e s t r i c t i o n ，b u tt h e i n c r e m e n to ft h en o d e sa n dt h ea r c sq u a n t i t ym a k e st h ec o s to ft h eg r a p ha l g o r i t h m i n c r e a s eg r e a t l y t os o l v et h ep r o b l e ma b o v e ，a s u p e r - n o d em o d e li sp r e s e n t e d t h i sm e t h o d c o n c e n t r a t e st h et u r nr e s t r i c t i o no ne a c hn o d ea n du s e sr e s t r i c t i o nm a t r i xr e p r e s e n t a t i o n b a s e do np e r f e c t i n gt h es u p e r - n o d em o d e l ，t h i st h e s i sm a d es o m ei m p l e m e n ta sf o l l o w s ：1 t h ee x t e n tu m li n s t r u m e n ti su s e dt om o d e lt h en e t w o r k ，t h es y m b o lr e p r e s e n t a t i o n so f t h er e a lw o r l do b j e c t sa r ed e s c r i b e dw i t l lg r a p h i c 2 ad a t am o d e ls u i t e dt ot h ec o n c e p t u a l m o d e li s p r o p o s e d d a t ar e d u n d a n c yi s r e d u c e db ym e r g ec o s t - a r c sa n dt h en o d e i d e n t i f i c a t i o n so f c o n s t r a i n t m a t r i x 3 s o m eo ft h eq u e r ya l g o r i t h mb a s e do nt h er o a d n e t w o r ki sm e n d e dw i t hi n t e g r a t i n gt h er e s e a r c ho fs p a t i a ld a t ai n d e x s i m u l a t i o ne x p e r i m e n t so n s t o r a g es p a c ea n dq u e r ys u p p o r ta r ep r o c e s s e do n s u p e r - n o d em o d e la n dn o d e - l i n km o d e li nt h el a s to ft h i st h e s i s t h er e s u l t ss h o wt h a tt h e s t o r a g ec o s to ft h es u p e r n o d er e p r e s e n t a t i o nm e t h o di sl e s st h a nt h a to ft h el a t t e r ，a n dt h e c o n t i n u o u sn e a r e s tn e i g h b o rs e a r c ha n dr a n g eq u e r yo nt h es u p e r - n o d em o d e li sm o r e e f f i c i e n tt h a nt h el a t t e r t h ee x p e r i m e n t si n d i c a t et h a tt h es u p e r - n o d em o d e lc a nn o to n l y r e p r e s e n tt h er o a dn e t w o r ka n dt r a n s p o r t a t i o ni n f o r m a t i o nw e l l ，b u ta l s ol e a dt oa ne f f i c i e n t q u e r yp r o c e s s k e y w o r d s ：i n t e l l i g e n tt r a n s p o r t a t i o ns y s t e m ，g e o g r a p h i ci n f o r m a t i o ns y s t e mf o r t r a n s p o r t a t i o n ，s p a t i a ld a t am o d e l ，r o a dn e t w o r km o d e l ，r t r e e i i 学位论文独创性声明： 本人所呈交的学位论文是我个人在导师指导下进行的研究工作及取 得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论 文中不包含其他人已经发表或撰写过的研究成果。与我一同工作的同事 对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 如不实，本人负全部责任。 论文作者( 签名) ：翌毯九舞月 夕日 学位论文使用授权说明 河海大学、中国科学技术信息研究所( 含万方数据库) 、国家图书 馆、中国学术期刊( 光盘版) 电子杂志社有权保留本人所送交学位论文 的复印件或电子文档，可以采用影印、缩印或其他复制手段保存论文。 本人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论 文外，允许论文被查阅和借阅。论文全部或部分内容的公布( 包括刊登) 授权河海大学研究生院办理。 论文作者( 签名) ： 至堑丝力口6 年6 y l 锣e t 1 1 研究背景 第一章绪论 随着经济的发展和城市化进程的加快，交通管理出现了突出的矛盾，即车辆增长 的速度远远高于道路和其它交通设施的增长速度，交通系统的复杂性和拥挤度与日俱 增，对社会经济生活和生态环境造成了很大影响。随着现代计算机、信息、通讯技术 及安全系统技术的发展，交通管理部门越来越多地试图借助智能交通系统( i n t e l l i g e n t t r a n s p o r t a t i o ns y s t e m ，简称i t s ) 这新技术来促进交通顺畅、改善道路安全。 智能交通系统将先进的信息技术、定位导航技术、数据通信技术、电子传感器技 术、自动控制技术、图像处理技术、计算机网络技术、人工智能技术、运筹管理学等 有效地综合运用于交通运输管理体系，加强了车辆、道路、使用者三者之间的联系， 从而实现交通运输服务和管理的智能化，在综合集成思想指导下，建立一种大范围、 全方位、实时、准确、高效的综合交通运输管理系统，是一个多学科和多技术的大型 综合化系统工程 1 i t 2 1 1 3 4 1 。从定义上来看，智能交通系统研究范围极广，基本上用来 解决当前交通领域各种问题的方法都是智能交通系统研究内容。 交通地理信息系统( g e o g r a p h i ci n f o r m a t i o ns y s t e mf o rt r a n s p o r t a t i o n ，简称g i s t ) 是智能交通系统的个重要组成部分。它建立在各种交通运输网络基础上，通过数据 库与空间分析相结合的方法，描述交通运输网络和网上运输流，并反映运输网中所存 在的问题。交通地理信息系统的定义是指收集、存储、管理、综合分析和处理空间信 息和交通信息的计算机硬件系统，是地理信息系统( g e o g r a p h i ci n f o r m a t i o ns y s t e m ， 简称g i s ) 技术在交通领域的延伸，也是g i s 与多种交通信息分析和处理技术的集成， 它将为交通各部门提供一个功能强大的空间信息服务和管理工具【l 】。 围绕着g i s t 产生了较多的研究课题，不同的研究课题涉及到的g i s t 的功能也 有所区别。但最终目的都是在空间上直观明了地显示以公路和车辆为对象的交通信 息，为这些信息的深层次挖掘和后续信息服务及辅助决策提供空间属性上的支持，最 终使交通过程中的各使用主体都参与到智能交通中来，最大限度的利用现有道路交通 基础设施。 g i s t 所管理的交通领域空间数据包括：道路网、道路宽度、道路等级、路名、 公交线路、交通设施等静态交通信息和交通拥堵状况、交通事故、交通管制信息等动 态交通信息以及基础地理信息数据等，其中以道路网络为核心的交通领域空间数据具 有丰富的特征、属性和复杂性【3 】，因此必须建立一套适用于交通领域内空间数据的特 定的道路网数据模型。 所需建立的道路网数据模型不仅要能描述真实世界的道路网，还应该能很好地支 持基于道路网的各种查询操作，提高系统性能。现在很多的道路网模型研究多是关注 于模型的描述性能，但从模型支持道路网查询的能力方面着手研究的还不多。本文的 研究内容就是建立一种能描述真实世界道路网且能对其上查询操作提供良好支持的 道路网模型。 1 2 国内外研究现状 国内外关于道路网的空间网络模型研究大多是以图论为研究基础的。道路网能比 较容易的被建模为图，这样网络上的空间问题就能被转化为图论问题。图建模的方法 是非常重要的，因为该方法描述了模型反映真实生活的接近程度。在采用由结点和边 组成的常规图模型为道路网建模时，交叉路口和端点由结点表示，连接这些结点的道 路由边表示。简单的表示法可以用无向图附加连通矩阵来表示道路网，无向图表示了 道路和交叉路口，连通矩阵则表示了这些道路的连通状况，但这种方式不能表示道路 的单向线等重要的信息。 因此有很多研究使用有向图表现道路网。空间网络的最重要的概念是对象之间的 连通性【4 】，通过图的表示，这样的要求常规图模型可以完成。但是道路网具有特殊性， 很多查询要受限于它的交通信息，所以交通信息也是同样需要被表示的。使用常规图 模型很难构建有转弯限制的模型【5 1 1 6 7 1 ，很多不同的方法被用来建模转弯代价和限制。 k i r b y 和p o t s 8 】使用了一种扩展的网络表示法。每个交叉路口分裂为虚结点，由虚边 连接。转弯代价被指派到虚边。这种方法的问题是图中的结点和边大量增加。这增加 了数据存储量以及大多数空间问题的计算时间，因为这种空间问题的复杂性是图中结 点数的函数。 为了处理这个问题，j i a n g 等【9 】提出一种基于连接的数据结构，一个结点连接表 被用来表示路网的连接性，另一个连接连接表被用来表示路网的连通性和转弯限制。 类似的结构有很多【1o 】【l l 】，如蔡先华等人【1 2 】提出的几何网络点一弧矢量数据模型和王杰 臣等人【1 3 】使用的结点弧段联合结构表示法。相对于扩展的网络表示法，这类表示法 在存储规模上是有了一定的减小，但在路网规模达到一定程度时，某些算法的运行时 间将令人无法接受。 w i n t e r 等人【1 4 】【1 5 】提出了一个可供选择的方法。他们介绍了伪二重图的概念，交 叉路口或端点间的路段被建模为结点，这些路段间的连接被建模为边。相对于扩展方 法，存储的结点数量减少了。而且模型可以支持没有修改过的图查询，例如d o k s t r a 算法。伪二重图方法也允许u 型转弯和循环遍历出现在算法的计算结果中，使用扩 展方法通常是排除这些特性的。然而：即使在伪二重图中，为了表现真实道路情形， 结点有时也不得不被分裂。分裂结点增加了数据的存储量和图算法的计算时间。而且 伪二重图的计算基于基础图，要存储两张图，这也增加了数据的存储。 为了解决表示转弯限制这个问题，f e n g 等人【1 6 】提出了一种超点模型，采用了一 个复杂的结点表示法来减少数据库中结点和交通弧的冗余。这种表示法能较好的表示 道路约束，而且对于各种查询算法也有很好的支持。本文将以超点模型为基础，对其 进行一些发展和完善，使其能更好的支持查询操作。 1 3 研究的主要内容和意义 1 3 1 研究的主要内容 、：? ：| ，：i ? ，? 摹t - ：| 囊0 一，? 。y ，；。 查询操作 t 支持 i 物理数据模型 t组织 i ，? 。? ，。i 。 j ：? ? ? ? ，麓幺? r 一k 隧移雾磐荔鹈剿； t 转化 、t ? t i t t j j ，j j 。，! _ j t 。一t ：4 ：一：1 7 j概念( 数据) 模型 t抽象 j 现实世界 图i - i 数据建模 论文以交通地理信息系统技术为研究的科学依据，并借鉴国内外相关研究成果， 从以下几方面进行研究： 1 模型研究的理论基础。主要研究分析了三方面的内容：交通地理信息系统技 术相关概念及其发展；空间数据模型及道路网模型；空间索引结构。根据道路网的特 殊性和现实应用的要求，提出了道路网模型评价的标准。关于道路网模型的研究，从 道路网模型的描述方式对道路网分类，具体比较分析了几个典型道路网模型，研究了 它们的优点和不足。 2 道路网超点模型完善和实现的研究。通过对现实道路网的分析与应用要求， 对比参照模型，在超点模型的基础上从以下几方面进行完善和实现：对概念模型进行 了部分修改，对模型从理论上进行了分析和评价，在概念模型的基础上使用扩展的 u m l 语言对道路网建模，并建立了数据模型。 3 道路网的查询操作研究。分析了基于道路网的常用操作，如区域查询、最近 邻查询、+ 连续最近邻查询等，对基于道路网的部分查询算法结合对空间数据索引的研 究做了改进。 4 实验设计和分析。根据超点模型的特点，设计了两个实验，分别在超点模型 和结点连接模型上进行连续最近邻查询和区域查询，通过比较c p u 时间对其性能进 行测试，并作分析评价。 如图1 1 ，数据建模的过程就是从现实世界抽象出本质的内容表现为概念模型， 然后对概念模型进行转化，建立数据模型，在经过组织存储管理的物理模型上支持实 际应用的查询等操作。本文的主要工作就是研究概念模型，对概念模型进行部分的改 进，在此基础上建立了数据模型，对查询算法进行了一些修改，通过实验验证模型的 优点( 图1 1 中灰色部分即是本文的主要工作) 。 1 3 2 研究的意义 道路网是可以用g i s 进行分析处理的地理空间对象，道路网络模型是交通规划、 建设、管理与服务的基础。一个好的路网模型的建立与应用，不但可以方便道路网络 基础数据的管理、网络分析，同时能够提高数据处理效率，节约存储数据空间，可以 为道路网络信息相关分析、智能交通服务准备一种高效数据结构，也有利于提高道路 网络的一些相关查询应用服务的算法效率。 路网模型是一种概念数据模型，它是数据库设计和建立的基础和核心。现实世界 的道路网融合了很多交通信息和空间信息，属性繁多，约束性强，运行其上的移动对 象也要受限于此。所以，建立一种能描述真实世界道路网的路网模型就成为了必要。 为了支持查询等操作，只有概念模型是不够的。在概念模型的基础上建立数据模 型，针对节约存储数据空间，设计一种既能表示模型的概念又有利于查询操作的数据 结构也是非常重要的，它与概念模型在数据库管理系统上的具体实现有关。 1 4 论文结构 本章是对论文的研究背景、研究现状及研究内容的一个概述，其余章节组织如下： 第二章道路网建模基础知识，对道路网建模的相关知识，包括交通地理信息系统、 空间数据模型及道路网模型进行了一定的介绍，还分析提出了模型评价标准，同时分 类研究了已有的一些典型模型。 第三章道路网超点模型的完善和实现，对超点模型及其上的相关算法进行了详细 阐述和改进，增加了结点标示符，修改了约束矩阵，方便查询操作对结点的查找，在 连续最近邻算法中增加了到目标点最短路径的查找。除此，还详细对比说明了超点模 型的特点。 第四章道路网查询操作，空间网络有三种常用的查询：单遍扫描查询、连接查询 和网络分析查询。按这三种常用查询对超点模型支持查询的能力作了分析和研究。 第五章实验设计和分析，根据超点模型的特点，对超点模型设计了两个实验，以 验证其优异性。同时，对实验结果进行了比较和分析。 第六章总结和展望，对全文的工作进行总结，并对进一步工作进行了展望。 第二章道路网模型相关研究 交通地理信息系统的核心对象之一是道路网，对道路网这种空间网络建立空间数 据模型是交通地理信息系统实现的基础。因此下面将分别对交通地理信息系统和空间 数据模型进行探讨，并在空间数据模型的基础上进步讨论道路网模型和适用于道路 网的物理数据模型。同时分类研究现有道路网模型的各种典型模型。 2 1 相关知识 2 1 1 交通地理信息系统 由于交通本身所具有的动态性、复杂性，使得g i s 技术在交通领域的应用与其他 领域相比具有很大的差异，这也使得交通地理信息系统被强化为一个专有名词【l 7 1 。随 着目前智能交通系统的蓬勃发展，作为辅助城市交通管理与规划的有效技术手段， g i s t 在i t s 中占有举足轻重的地位，已成为g i s 应用的个发展热点。特别地，通 过与g p s 、无线通讯、i n t e r n e t 、虚拟现实等高新技术的有机结合，它不但可以储存、 管理和更新交通网络中的数据库，而且可以辅助交通网络规划，进行交通信息管理； 它建立了广泛的、实时的数字交通信息服务体系，实现全数字化交通信息的实时发布、 储存与检索，为交通实时数据管理、空间分析、网络优化、车辆智能导航、客货运输 调度及居民出行等提供有效的技术支持。 通常情况下g i s t 中主要涉及三类空间数据模型：区域模型，即在跨越空间时表 示连续变化的现象；离散实体模型，也就是离散的实体( 点、线或多边形) 及其相关 属性的集合的抽象表达；网络模型，代表拓扑连接的嵌于地表的线性网络变化的抽象 表达【1 引。 由于交通系统自身的特性，应用于交通系统的数据模型几乎都没有超出上述三种 模型的范围。在对交通模型进行表达的时候，可以用许多具有多种属性的线段代表道 路网，用离散点代表各种道路网中的标志性地物，用线性网络代数对交通网络进行分 析，这些方法对实现道路交通系统的计算机表示起到了一定的作用。在交通领域中， 围绕以弧和点的概念建立的网络模型起的作用是最重要的。 2 1 2 空问数据模型 数据模型是连接现实世界和计算机世界的桥梁，它是以一定方式组织起来的、有 6 足够的抽象性和概括性的、对客观事物及其联系的描述【1 9 l 。这种描述包括数据内容的 描述和各类实体数据之间联系的描述。事实上数据模型是数据表达的概念模型，是描 述数据的手段。 在g i s 研究领域，由现实世界到g i s 的抽象过程可划分为三个层次表示模型： 概念模型，逻辑数据模型，物理数据模型【5 1 【1 9 】。根据这种划分，数据建模过程分为三 步：选择一种数据模型来对现实世界的数据进行组织；选择一种数据结构来表达该数 据模型；选择一种适合于记录该数据结构的文件格式。 数据模型设计的目的是将客观事物抽象成计算机可以表示的形式。概念数据模型 着重获得对客观现实的_ 个正确认识，是面向用户、面向现实世界的数据模型。它主 要描述系统中数据的概念结构，按用户的观点来对数据和信息建模，是现实世界到信 息世界的第一层抽象。 逻辑数据模型用于机器世界，主要描述系统中数据的结构，对数据的操作以及操 作后数据完整性问题。这类模型通常有严格的形式化定义，而且常常会加上一些限制 和规定，以便于机器上的实现。 物理模型是数据抽象的最底层，主要包括空间数据的物理组织，空间存取方法和 数据库总体存储结构等。索引文件就是常用的存取方法，常规的索引方法有b - t r e e 、 四叉树、r - t r e e 等。 对于空间数据库，数据模型是一条或一组用于标识和表示空间参照对象的规则。 空间数据模型是关于现实世界中空间实体及其相互联系的概念，它为描述空间数据的 组织和设计空间数据库模式提供基本方法。空间数据模型通常分为两大类：对象模型 和场模型。 对于一条河流，可以按比例将其表示为一条一维的曲线，一口井可以表示成零维 的点，这些都是对象模型的例子。对象模型很适合表示离散的、有固定形状的空间实 体，如湖泊、道路网和城市。这种对象模型是概念化的，可以采用矢量( v e c t o r ) 数 据结构将其映射到计算机中。矢量数据结构将区域映射成多边形，线条映射为多线， 点映射为点。 场( f i e l d ) 模型通常用于表示连续的或无固定形状的概念，例如温度场或云区， 一个场就是一种函数，它将基本参照框架映射到一个属性域上。对于温度来说，最常 用的属性域是摄氏和华氏。在计算机中，场模型是用栅格( r a s t e r ) 数据结构来实现 的。栅格数据结构把基本空间划分成均匀的网格。由于场值在空间上是连续的，所以 每个栅格的值一般采用位于这个格子内所有场点的平均值表示。场的其它常用数据结 构还有不规则三角网、等高线和点网格等。 区域i d主要树种区域边界 f s l松树 【( 0 ，2 ) ，( 4 ，2 ) ，( 4 ，4 ) ，( 0 ，4 ) 】 f s 2 冷杉【( 0 ，0 ) ，( 2 ，0 ) ，( 2 ，2 ) ，( o ，2 ) 】 f s 3 橡树【( 2 ，o ) ，( 4 ，0 ) ，( 4 ，2 ) ，( 2 ，2 ) 】 ( a ) 林分地图 ( b ) 对象观点( c ) 场观点 图2 - 1 对象场的二分法 图2 1 是依据树种划分森林区域的一种理想情况，每个树种区域是一个矩形，每 个矩形有唯一的标识符和一个非空间属性树种的名称。这样就把森林建模成一个 对象模型，每个矩形对应一个树种。从场模型的角度，森林可以建模成一个函数f o 该函数的定义域是森林占据的地理空间，而值域是树种名称的集合。函数f 是个分段 函数，它在树种相同的地方取值恒定，而在树种发生变化时改变取值。 2 1 3 道路网模型定义 道路网数据模型是对道路相关信息进行描述的数据模型，它可以支持多种查询操 作。道路网信息描述了各路段的起始点、结束点及路段间的连接性。而交通信息不同 于道路网信息，它描述了道路的交通代价、路段约束、路口约束和转弯代价等内容。 本文所提及的道路网应更准确的称为交通网，即在单纯的道路网信息之上附加了交通 信息的道路网。 道路网上的移动对象( 如行驶的车辆) 在作匀速运动时，交通代价可以是路段长； 或者可以是在每一交通路段上的行驶时问；也可以是其它的方面，如道路的通行费等。 g 1 q y y y q 9 9 泛 沁 m g q g 盘 g q 树 杉 树 松 冷 橡 一 一 一 1 i 、，”冯 道路有通行条件，很多道路是单向通行的，且有很多高等级道路以隔离带划分为 两条道路，均是单向通行，在拓扑网中表现为有向性。不仅如此还有其它限制，如大 型货车禁止在细小道路中通行；很多地方对时间上也有限制，如某条道路早上8 ：0 0 至晚上9 ：0 0 货车禁止通行，某条道路平时可以通车，但是周末和节假日是步行街， 汽车禁止通行。这些对最短路径计算均有很大的影响。 4 | j 上 0 卜一4 - j卜一 ，膏 l 图2 - 2 路口约束示意图 2 1 4 空间数据的物理模型 交通网在道路交叉点处有各种各样的限制 条件，最为常见的就是禁止向左转弯，如图2 2 所示转弯( 1 - 0 4 ) 是禁止的，所以在计算最短路 2 径时不能从道路( 1 - 0 ) 转到道路( o - 4 ) 。有时并没 有交通规则说向哪里转弯不行，但是有潜在的 禁止转弯规则。比如图2 2 中的( 1 - 0 ) 是单向通 行，只能从l 到0 向2 和3 通行，不能从2 、3 、 4 向l 通行，而且不允许( 1 - 0 1 ) 这样的u 型转 弯。 索引是对被索引数据集中数据的某一方面属性的一种结构化描述数据，它使得在 对数据集进行查询时，不需要遍历数据集，只通过对索引数据的访问就完全能够得到 查询结果，或者得到包含全部查询结果的较小的数据集【5 1 。建立索引的目的是为了提 高对大量数据查询、检索、分析和处理的效率，在g i s 中得到广泛应用的成熟技术是 r - t r e e 及其变种。我们在实验中将以r - t r e e 作为道路网的空间索引结构，所以现在对 r - t r e e 进行一些介绍。 r - t r e e 是一个高度平衡树，它是b t r e e 在k 维上的自然扩展。r t r e e 中用对象的最小 外包矩形( m i n i m u mb o u n d i n gr e c t a n g l e ，简称m b r ) 来表示对象。r - t r e e 有以下几条 特性【5 】【2 0 】【2 l 】： 1 每个叶结点包含m 至m 条索引记录( 其中m m 2 ) ，除非它是根结点。 2 一个叶结点上的每条索引记录了( i ，元组标识符) ，i 是最小外包矩形，在空 间上包含了所指元组表达的k 维数据对象。 3 每个非叶结点都有m 至m 个子结点，除非它是根结点。 4 对于非叶结点中的每个条目( i ，字结点指针) ，i 是在空间上包含其子结点中 矩形的最小外包矩形。 5 根结点至少有两个子结点，除非它是叶结点。 6 所有叶结点出现在同一层。 7 所有m b r 的边与一个全局坐标系的轴平行。 9 r 5 ( a ) 线段的空间位置和其限定矩形( b ) r t r e e 索引结构 图2 - 3 线段的r 。t r e e 索引结构 每个结点能包含的对象或子结点个数的最大值称结点容量，即m 。m 取决于数 据在硬盘驱动器上的存储参数，如磁盘页面的容量，通常树的每个结点对应一个磁盘 页面，m 选取使得一个结点填充满或小于一个磁盘页的数值；m 取决于数据库的操 作，若数据库仅仅( 或大部分) 只需要查询而较少更新，m 应该取较大的值，降低 r - t r e e 的高度，从而加快搜索速度，但这样会容易引起溢出；若数据库需要经常更新 或调整，则m 应该取较小的值。通常m 取值在2 - m 2 之间选择。 r t r e e 的搜索性能取决于两个因素：覆盖和交叠。树的某一层的覆盖是指这一层 所有结点的m b r 所覆盖的全部区域。覆盖是对静态空间的一个间接衡量。树中某一 层的交叠是指在该层上被多个与结点关联的矩形所覆盖的全部空间区域。交叠使得查 找一个对象时必须访问树的多个结点。 m b r 并不等于实际对象，故r - t r e e 不能完全响应一个查询请求，除非数据库中 的对象就是m b r 。r - t r e e 常常用来处理与查询对象的m b r 相交的数据库对象的初步 筛选。 r - t r e e 能够根据搜索条件：一个矩形，迅速找到与该矩形相交的所有空间对象集 合。当数据量巨大，矩形框相对于全图很小时，这个集合相对于全图数据集大为缩小， 在这个缩小的集合上再处理各种复杂的搜索，效率就会大大提高。 2 2 模型评价标准 很多研究对建立模型都有着各自的标准，但大多数的研究都关注与模型对道路网 的描述能力。我们建立模型的目的是支持各种空间操作，所以论文以此为基础，参考 各种研究，给出本文模型评价的标准。 标准1 尽可能的表现道路网信息。 概念数据模型着重获得对客观现实一个正确的认识，真实世界需要被尽可能的表 现。理想地，一个信息系统对它的虚拟世界中问题的回答和真实世界中的精确答案应 l o 相一致。道路网的概念模型是对道路网的认识和抽象，模型最基础的要求要能表现道 路信息，即道路、道路间的交叉口及道路长。 标准2 尽可能表示道路网上的交通信息。 前面我们已经讨论过道路网上的另一类重要的信息：交通信息。道路网的信息种 类和交通信息的管理方式都会影响基于模型所提供的功能的效率【l6 ，为了支持空间操 作，只能表示道路信息的模型是远远不足的。为了表示真实道路网，表明可能引起变 化的外部环境信息是重要的，这是有关谁应该对变化负责的信息【z 引。模型应能识别 有单向线属性的连接、交通限制、连接问的转弯信息或连接问的连通条件【2 2 j 等交通 信息。随着社会的发展，附加于道路网上的信息越来越多，表示道路网上的交通信息 是模型评价的另一个重要标准。 标准3 支持道路网信息的稳定和响应交通信息的改变。 道路网是一种相对稳定的线性系统，道路常常被期望有个坚固的生命期，但是道 路上的交通信息是经常改变的，建立的模型要能支持这些信息的改变【2 3 】。这里就产生 了一个矛盾：相对稳定的道路网信息和经常改变的交通信息的表示。前面提到了交通 信息包括交通代价、路段约束、路口约束和转弯代价等，一些交通信息需要周期性的 或触发性的更新，如某双向线路段在交通高峰期转为单向线，而路网信息很少需要更 新，在短时期内，修建或拆除的路段还是有限的，所以路网信息基本是静态的。因此， 静态信息应由一个有效的索引结构管理，和道路地图相关的交通信息的变化不应该打 乱结构的稳定性。模型应即能支持道路网信息的稳定性还要能对交通信息的改变有快 速的响应。 标准4 存储数据最小化。 当真实世界的概念被抽象出来时，这些数据被存储于计算机上，为了使查询能被 高效的处理，它们必须被最小化。随着城市规模的不断扩大，道路网的规模也不断扩 大。现在的道路网数据库中的数据量巨大，无法一次全部放到主存中，空间网络上的 很多操作要通过多次的i o 操作来实现【5 1 ，在合理的索引下通过减小存储的数据冗余刁 能提高算法的效率。 标准5 有效支持相关查询。 最后，还有一个重点因素应在建立模型的考虑范围之内：模型应能提供关于道路 的动态信息和静态信息的空间查询，如最近邻查询。模型的优劣程度直接影响了查询 算法的性能，从而间接影响应用系统的性能。质量的一个重要方面就是不考虑数据应 用的模型是不能被评估的【2 2 1 ，这是指在评价模型的质量时要考虑模型的实际应用。所 以模型对空间相关查询的支持能力是建立模型时应重点考虑的地方。 以上是总结归纳出的模型评价标准，下面我们将以此标准评价和建立模型。 2 3 道路网模型分类及典型模型分析 按照道路网的描述方法，可以把道路网分为如下两种类型：2 d 模型和图模型， 其中图模型按照道路网的组成内容还可分为：路段模型和路径模型。与2 d 模型相比， 图模型抽象度较高，结构简单、紧凑，计算效率更高。而且，图模型表达了道路网的 本质，脱离了欧氏空间，有利于查询的计算处理。 为方便区分，把无拐点的直线道路称为分割段，若干分割段连接成的一个路口到 路口的道路称为路段，具有现实中名称的完整道路称为路径。除分割段是直线段表示 以外，路段和路径都是折线段表示的。 2 3 i2 d 模型 2 d 表示是欧氏空间的一种坐标表示法。2 d 模型【2 4 】【2 5 】使用分割段表示，可以基 本捕捉现实世界的所有真实细节，能够方便的对其上的移动物体( 如车辆) 定位。但 抽象程度不够，需要存储的数据量过多，且因很多空间查询的计算需要基于路径长或 代价，所以这种表示法在查询计算中的应用不是很多。 如图2 4 所示就是一个2 d 道路网模型。典 型的如s p e i 6 y s 等人【2 4 】应用的2 d 模型。 道路网由二元组r n 2 d = ( s ，c ) 表示。s 是 分割段或路段的集合，每个集合元素s 包含一 个四元组( p 。，p e ，m ，p r o p ) ，p 。和p e 分别是分割 段的起点和终点坐标，m 表示了以下交通信 息：当m = l - 1 时，分割段为一单向线，由p 妣 向p j p 。通行；当m = 2 0 时，分割段为双向线， 2 时道路上允许u 型转弯，0 时禁止u 型转弯。 a 图2 42 d 模型 p r o p 由二元组( p r o p e r t y ，v a l u e ) 构成，v a l u e 表示路况信息，当0 v a l u e _ l 时，路况较差，会降低车速。p r o p e r t y 则 表明这种路况只是某一方向上的情况，还是双方向的情况或者是其它特殊情况。 表2 1 分割段信息 s p sp e m p r o p a b( 4 6 3 9 , 2 4 81 )( 4 7 1 4 ，1 9 2 5 )2 ( p r b 。o t h ，u , 、6 7 ) ) b z( 4 7 1 4 ，1 9 2 5 )( 4 7 1 7 ，1 5 9 9 )2 t l tp r b 。p o t h ，1 5 ) ，0 r ；二。，1 1 ) ) z c( 4 7 1 7 ，1 5 9 9 )( 4 9 0 6 ，10 8 6 )一1 ( p r 。e 。s ，1 ) ) b l( 4 7 1 4 ，1 9 2 5 )( 5 1 2 8 ，1 8 2 2 )1 ( p r 。s ：，1 2 ) ，( p c 。，1 1 ) ) 1 2 表2 2 连接矩阵 a bb lb z a b1l1 b l000 b z1o 1 如表2 1 所示，第二行( p r e 、。) 表示b z 路段在s e 方向有一些颠簸，第四行( p r 兰。) 表示b l 路段在s e 方向的公路不平坦。 c 是一个连接集合，每个集合元素c 由三元组( p ，s 。，n i x ) 构成。p 指明了连接点c 的位置；s 。是所有连接于p 点的分割段s 的集合；m x 是一个连接矩阵，表明每一对属于 s o 的分割段( s l ，s 2 ) 是否可从s l 到达s 2 ，值为1 时可连通，0 时不可连通。m x 不仅被用来 指示分割段的连接性问题，它还可以反映连接点上的某些交通规则。 模型能满足标准1 ，但对某些交通信息如转弯代价无法表示，且存储数据量大， 不能符合模型评价标准的其它几方面。 2 3 2 路段模型 路段表示法是一种比较直观的道路网图模型。图的表示有两种方法：一种是无向 图 2 6 】，因表示信息少，不足以描述道路信息，所以研究较少；另一种是有向图，可 以实现单、双向线的概念。现在常用的最简单的路段模型是结点弧表示法，这种常规 图表示法无法表述转弯代价等交通信息，所以研究者们基于结点弧表示法提出了许多 不同的改进方法【9 】【1 2 】【1 3 】【1 6 】【2 4 】【2 7 】，针对转弯限制进行了建模。 2 3 2 1 结点连接模型 s p e i 6 y s 等人【2 4 】使用2 d 模型的同时，提出了一种结点连接模型，道路网r n o = ( g ，c o 乏) 。g = ( v ，e ) 是有向图，v 是顶点即交叉路1 3 的集合，e 是边即路段的集合。 一条边e 是由一个四元组( v 。，v c ，w ，1 ) 构成，v 。和v 。分别是e 的起点和终点；w 被称为 路重，表示e 在路网中的行驶长度，即在考虑路况的条件下，相等耗时行驶在标准路 况下的路程长；l 是边的长度，捕捉e 在路网中的实际路长。“双边”关系c o 乏捕捉表 示同一条路的一对边，其上允许u 型转弯，即c o 之表示了允许u 型转弯的双行线。如 图2 5 ( b ) 中，z b l 和b 2 z 7 就是一对双边关系。 该模型除能表示路况信息，还能表示如单双行、u 型转弯等交通规则。但在表示 交通规则信息时，需要增加结点和边的数量，使得查询算法的代价变高。在图2 - 5 ( a ) 中，由于c z 和b c ( 即b l n m c ) 为单向线，而z b 是双向线，且z b 不能向b l 转 弯，所以b 点被表示为5 个点。 b i ( a ) 2 d 模型( b ) 结点连接模型 图2 5 结点连接模型的生成 这种方法的好处是网络中不包括转弯延迟和禁止，通过任何普通的数据结构和算 法，路径查询问题都能够被解决。但是这种方法的缺点是很明显的，即结果网络比原 始的巨大得多，需要更多的计算时间和内存，而且网络更新很耗时，这也是棘手的问 题。模型以增加结点和弧的数量为代价来实现对标准2 的要求，但这样做必然不符合 标准4 对存储量最小化的要求，而且也导致不能符合保障结构稳定性的第3 点要求。 2 3 2 2 伪二重图模型 w i n t e r 等改进了一种基于结点弧的数据结构伪二重图。基本图g = ( n ，e ) ， n 和e 分别是结点和边的集合。g 是一个无向图，基于基本图作了一个映射，十字路 口间的边被建模为结点，如果两个基础边是连通的，那它们所映射出的两个结点问被 建模为边。 ( a ) 完全伪二重图( b ) 受限伪二重图 图2 - 6 伪二重图 图2 - 6 ( b ) 表示的是一个受限的伪二重图，完全伪二重图( 图2 - 6 ( a ) ) 的每条道路 上均是允许u 型转弯。在实际情况中，基本所有的道路上都禁止u 型转弯，所以采 用受限的伪二重图来表示道路网，道路上不允询：u 型转弯。 1 4 相对于结点连接方法，伪二重图可以直接在边上表示转弯代价。而且该方法允许 常规图算法运行于其上而不作修改，例如最短路径算法。伪二重图也允许在算法的计 算结果中循环遍历同一路口，如果使用扩展网络方法通常是排除这些特性的。 然而，为了表示真实道路情形，伪二重图需要存储原始图，即其是双图表示的， 增加了数据的存储量。且其图算法有时要访问原始图，增加了计算时间。 2 3 3 路径模型 路径表示法以现实世界中的整条道路作为基本描述单元，对道路网进行建模。城 市地图是由有名字的道路组成的，而不是由其上的交叉路1 2 或路段组成的。而且很多 的位置表示法是与道路上的距离标志相关的，所以选择路径作为基本描述单元可以更 好的抽象现实世界，但这方面的研究还不是很多。 现有的关于路径模型的描述多针对于移动对象位置管理方面，典型的如g i i t i n g 在预测位置时给出的模型【2 8 】【2 7 】【3 们，具体描述如下。 g = ( r ，j ) ，r 是路径r o u t e 的集合，j 是路径间交叉路口j u n c t i o n 的集合。r o u t e 是由五元组( 标识号i d ，路径长l ，折线段c ，k i n d ，s t a r t ) 表示，k i n d 表示路径的单双向信 息，s t a r t 中有两种情况( s m a l l e r ，l a r g e