（计算机应用技术专业论文）道路网物体移动模式的研究.pdf

摘要 摘要 目前，道路交通问题己成为人们关注的焦点之一。为了有效地解决这一问题， 智能交通系统( 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 s ，i t s ) 得到了越来越多的关注和研 究，其研究的内容非常广泛，主要涉及道路网络模型的研究，物体移动规律的研究 及时空数掘索引的研究等内容。 基于上述背景，本文研究了物体的移动轨迹。首先，本文通过对区域序列轨迹 模型的研究，结合道路网物体的移动特点，提出了一个基于路段序列的轨迹表示模 型。这一轨迹模型是区域序列轨迹模型的一个拓展，能更详细地描述物体在道路网 中的移动情况。其次，本文通过路段序列的轨迹模型，研究了物体移动轨迹的实时 跟踪和查询策略，这为研究路段的时白j 代价奠定了基础。最后，本文通过提取物体 轨迹的时间信息，研究了道路路段的时间代价函数，以便实时预测物体行驶路径的 时问代价。在此基础上，本文研究了物体行驶路径的动态优化策略及物体到站时目j 的实时更新策略。以上研究作为智能交通系统研究的一部分，可为人们的出行安排 提供有价值的参考。 关键词：智能交通系统，最短路径，模式匹配，道路网，移动模式 a b s t r a c l a b s t r a c t n o w a d a y s ，t r a f f i cp r o b l e mh a sb e c o m eam a j o rc o n c e r nt op e o p l e i no r d e rt os o l v e t h ep r o b l e me f f e c t i v e l y ，i n t e l l i g e n t t r a n s p o r ts y s t e m ( i t s ) h a sb e e ni n t r o d u c e d t h e r e s e a r c hs c o p eo fi t si sv e r yl a r g e ，i tf o c u s e sm a i n l yo ns t u d yo fr o a dn e t w o r km o d e l ，0 n m o v i n go b j e c ta n d o i li n d e x i n gt e c h n i q u e so f s p a t i o t e m p o r a ld a t a b a s e do nt h i sc o n t e x t ，t h i sp a p e rs t u d i e st h et r a j e c t o r i e so fm o v i n go b j e c t s f i r s to f a l l ， t h ep a p e rh a sp r o p o s e dam o b i l i t yp a t t e r nw h i c hi sas e q u e n c eo fr o a ds e g m e n t s ，b y s t u d y i n gat r a j e c t o r ym o d e lw h i c hi sas e q u e n c eo f a r e a s c o m p a r et ot h es e q u e n c eo f a r e a s ， t h em o b i l i t y p a t t e r nc a nd e s c r i b et h em o v e m e n to fo b j e c t sm o r ep r e c i s e l yi nar o a d n e t w o r k s e c o n d l y ，o nu s i n gt h em o b i l i t yp a t t e r n ，t h ep a p e rh a sp r o p o s e ds o m em e t h o d st o t r a c ka n dq u e r yt h et r a j e c t o r i e so ft h em o v i n go b j e c t s i ti sab a s i st os t u d yt h et i m ec o s to f r o a ds e g m e n t f i n a l l y b ye x t r a c t i n gt i m ei n f o r m a t i o no ft r a j e c t o r i e s ，t h ep a p e rh a s p r o p o s e dam e t h o dt oc o m p u t et h et i m ec o s tf u n c t i o no fr o a ds e g m e n t ，w h i c hc a nb eu s e d t op r e d i c tt h et i m ec o s to f am o v i n gp a t h w i t ht h i sf u n c t i o n ，t h ep a p e rh a sp r o p o s e daw a y t oo p t i m i z et h em o v i n gp a t hd y n a m i c a l l ya n daw a yt ou p d a t et i m ei n f o r m a t i o nt e m p o r a l l y b e f o r er e a c h i n gt h ed e s t i n a t i o n a sap a r to fi t ss t u d y t h i sr e s e a r c hc o u l do f f e ru s e f u l i n f o r m a t i o nf o rp e o p l e st r i p 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 ts y s t e m s ，t h es h o r t e s tp a t h ，r o a dn e t w o r k ，m o b i l i t yp a t t e r n a n dp a t t e r nm a t c h n 学位论文独创性声明： 本人所呈交的学位论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工 作的同事对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。如不实，本人负全部责任。 论文作者( 签名) ： 学位论文使用授权说明 年月 日 河海大学、中国科学技术信息研究所、国家图书馆、中国学术 期刊( 光盘版) 电子杂志社有权保留本人所送交学位论文的复印件或 电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子 文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外， 允许论文被查阅和借阅。论文全部或部分内容的公布( 包括刊登) 授权 河海大学研究生院办理。 论文作者( 签名) ：年月日 第一牵绪论 第一章绪论 随着车辆的增多，道路交通压力只益增大，尤其是城市交通，经常出现交通捌 挤堵塞的情况。作为交通问题有效的解决手段之一，智能交通系统( i n t e l l i g e n t t r a n s p o r ts y s t e m s ，i t s ) 得到了很多的研究，它是将先进的信息技术、数据通信传输 技术、电子传感技术、电子控制技术及计算机处理技术等有效地集成并运用于整个 地面的交通管理系统，是一种大范围全方位发挥作用的实时、准确、高效的综合 交通运输管理系统l l j 。智能交通系统最初是在以监控为主体的交通工程( 包括交通 管理) 基础上发展起来的，开始只进行道路和车辆智能化管理的研究，目前所研究 的领域已逐渐涉及到铁路，水运及航空等各种交通方式，旨在形成一整套为用户及 交通管理部门提供道路交通信息的新型交通系统，i t s 的“智能化”主要体现在以下三 个方面： l 。车辆能依靠自身的智能系统在不同的道路上安全高效地行驶。 2 道路网依靠自身的智能系统实时调节交通流量，使道路达到最佳的通行状 念，减少阻塞。 3 交通控制管理中心依靠智能交通系统，实时监控道路和车辆状况，及时处 理交通事故，保障道路顺畅。 1 1 选题背景 目前，我国的道路交通状况形势不容乐观，尤其是道路交通安全，据统计， 2 0 0 2 年至2 0 0 3 年问，我国因交通意外死亡的人数在1 0 万以上。同时，相对于机动 车数量的不断增加，相应的道路建设速度却相对滞后，这使得道路交通状况不断恶 化，得不到有效地控制。这一交通棚挤问题在我国的城市中显得尤为突出。另外， 交通系统是一个复杂的综合系统，依靠传统的交通管理方式，单从道路和车辆的角 度考虑，很难解决交通拥堵、事放频发、环境污染等近年来不断恶化的问题。过 去，为了解决交通拥挤的问题，通常是通过不断修建新的道路来加以解决的。然 而，城市土地资源是相对有限的，尤其是在今天的城市建设中，城市土地可谓是寸 土寸金，修建新道路的代价巨大，因此，修建新的道路不是理想的解决方案。以美 国为首的发达国家在城市建设的过程中，注意到了这一问题的存在，为了有效地解 i l f 海人学坝i ： f 究生论文 决这一问题，并对道路交通网络进行有效的管理和规划，美国首先提出了智能交通 系统的发展方案。智能交通系统通过对多种高新技术的集成，将道路、驾驶员和车 辆等有机地结合到了一起，有望彻底改善城市交通状况，大幅度提高城市交通的营 运效率。作为i t s 两个重要组成部分的a t m s ( 高级交通管理系统) 和a t i s ( 高级出行 信息系统) ，其主要任务分另j 是进行交通信号的控制和对驾驶员迸行合理的路径诱 导，其中多种方案可供选择。 近年来，随着信息技术，卫星定位技术，无线通讯技术，计算机技术及传感技 术等的不断发展和深入研究，智能交通系统的研究和发展得到了不断的完善。其相 关的研究内容主要有，地理信息系统，时空数掘库技术，数据挖掘技术及道路网模 型等内容。 地理信息系统( 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 ) 是计算机科学、地理学、 测量学和地图学等多门学科的交叉，它是以地理空间数据库为基础，采用地理模型 分析方法适时提供多种空扫j 的和动念的地理信息，为地理研究和地理决策服务的计 算机技术系统1 4 】f 5 1 。 从表现形式来看，g i s 表现为计算机软硬件系统，其核心是管理、计算、分析 地理坐标位置信息及相关位置上属性信息的数据库系统。它表达的是空间位置及所 有与位置相关的信息，所以，g i s 又是地球空矧实体的再现和综合，其信息的基本表 达形式是各种二维或三维数字地图。因此，g i s 也可简单定义为“用于采集、模拟、 处理、检索、分析和表达地理空间数据的计算机信息系统” 6 - g l 。从系统角度看，在 未来的几十年内。地理信息将向着数据标准化( i n t e r o p e r a b l e ，g i s ) ，数据多维化 ( 3 d & 4 dg i s ) ，系统集成化( c o m p o n e n tg l s ) ，系统智能化( c y b e rg i s ) ，平台网络化 ( w e b g i s ) 和应用社会化( 数字地球) 的方向发展。 由于智能交通系统需要对道路网中所有的移动物体进行管理，因而必须具备管 理海量时空数据的能力，这就使得空问数据库的研究变得十分重要。空问数据库的 存储和管理是实现智能交通系统的关键技术之一，所有的服务，如查询，预测等都 是对所存储数据进行操作和挖掘分析来获得的。为了有效地提高系统查询和存储数 据的能力，时空数掘索引结构 2 1 - 2 9 1 的研究一直是科学界所关注的重点，目前空间数 据存储最常用的是r 树1 3 i 系列的索引结构。时空数掘库作为一个用于管理空自j 静态及 动态数据的系统，与传统的数据库管理系统相比，时空数据库涉及对现实世界大量 2 第一章绪论 空问对象的处理。首先，是对空间对象之间的空白j 关系的处理( 如相交、相邻、包含 等) ；另外出于空间对象的几何形状往往是不规则的，加上他们之问的关系复杂， 因此，系统的存储和计算量巨大。其次，是对空问对象的空间操作，例如交叉点、 邻接物及包含物，计算的代价比起传统的选择或连接操作复杂、运算量巨大，这也 与空触对象形状的不规整有关。 另外，为了实现智能化的交通管理和预测，空白j 数据挖掘技术i 加l 至关重要，对 于海量的时空数据1 3 9 j 1 4 2 j ，系统必须雾有能力作出适当的分析，并有效地提取出相关 的信息，以便用来指导和管理地区的交通系统，并帮助相关的地区管理部门对道路 建设做出有效的规划。 1 2 研究现状 随着移动通讯技术和定位技术的发展，基于位置的服务l b s ( l o c a t i o nb a s e d s e r v i c e ) 得到越来越多的应用，这是智能交通系统的一个重要组成部分。l b s 是以 定位技术为基础的服务，其工作原理是：用户终端如p d a ，车载电脑等移动设备， 采用全球卫星定位系统，实时获取用户位置，并通过移动通讯网络把位置信息上传 至服务器；另一方面，服务器会根据用户发出的服务请求作出响应，并把相应的服 务信息( 最佳行驶路线，离目标的最近距离等等) 透过移动通讯网络发回至用户终 端1 2 1 。简单的结构如图1 1 所示： 图1 i 智能交通系统示意圉 事实上，这一服务系统主要是对车辆提供各类导航服务，因此其必须跟踪车辆 的地理位胃。a l m i n a s 9 l 等人2 0 0 4 年在m o b i l ea n du b i q u i t o u ss y s t e m s ：n e t w o r k i n g 鬟 慕文f慕文f i f 海人学颅i ：研究生论土= a n ds e r v i c e 会议中提出了一种基于c s 结构的跟踪系统，客户端通过g p s 定位得知 其准确的地理位嚣，并通过移动网络上传给服务器，为了得到每个用户的实时位 置。其数掘库信息必然实时更新。同时为了避免错误的用户位置影响应用服务，客 户端通过定时获取并上传自身的位置情况，来保证系统跟踪物体的误差在个设定 的范围之内。 实时跟踪物体的移动位置，事实上就是种对物体移动轨迹的跟踪，对于移动 对象不同的跟踪策略而言，其对服务器性能的影响是各不相同的，目前主要的跟踪 策略包括：基于点的跟踪，基于向量的跟踪和基于路段的跟踪”o 1 川。研究者在文章1 9 1 中介绍了这些不同的跟踪策略，以及其性能的比较。从结果来看，基于点的跟踪方 式简单，但更新频率较高。基于路段的跟踪与基于向量跟踪更新频率相当，但考虑 路段的可延伸性，通过对于底层路网的改造之后，基于路段的跟踪策略可以使得系 统数掘库更新频率大幅度下降。 物体轨迹方面的研究主要是通过区域序列1 1 2 q5 1 柬描述的，在此基础上，文章 1 6 ，l7 提出了用字符串的形式来处理时问序列的方案并给出了相关的匹配算法。另 外，文章 1 8 ，1 9 ，2 0 都在此基础上提出了物体轨迹的挖掘方案，旨在预测物体的移 动轨迹。 另外，由于本文研究的是道路网上的移动物体，因此对于道路网的研究也是不 可或缺的道路网不仅限制了物体的移动空间，其相关的交通规则和约束条件更限 制了物体的移动方式，比如，物体的运动方向。同时，由于道路网路段的方向性， 和道路交通的实时性，道路网中最短距离计算也是目前研究的一个重点。目前，道 路网研究主要是通过图论来展丌的，主要的研究模型有结点模型和超点模型等。 本文通过对上述内容的分析和研究，提出了一个基于路段序列的轨迹表示模 型，这是轨迹区域序列模型的个拓展，能更好地描述物体的移动轨迹。同时，通 过路段序列轨迹中的时间信息，本文研究了物体最优行驶路径的预测方案等内容。 本文所研究的移动物体具体是指道路网内的移动车辆。在后面的论述中，移动物体 泛指移动车辆。 1 3 研究意义 本文通过路段序列的轨迹模型，研究了物体移动轨迹的跟踪和查询策略。同时 根据轨迹的时间信息，本文研究了道路路段的时问代价。根据已有的研究可知，路 4 第一章缔论 段的时间代价是随着时问，移动物体数量，路段通行能力和天气等因素的变化而变 化的。本文对于路段时间代价的研究不考虑天气的因素。根据路段的时知代价函 数，本文首先研究了物体最优行驶路径的预测方案：其次，本文研究了物体到站时 问的实时更新策略；最后，本文研究了物体行驶路径的动念优化方案。以下是上述 研究的主要意义， 首先，根据物体移动轨迹的跟踪和查询策略，人们可以快速地找到符合查询模 式的移动物体，这对于了解和监控道路交通状况有十分重要的意义，比如，可以通 过查询某一特定时自j 段内路段上移动物体的数量来了解当时道路路段的交通状况。 这一信息能给交通拥挤状况的研究提供有价值的参考。同时，轨迹的查询策略可以 帮助人们更好地研究移动物体在道路网中的分布情况。 其次，根掘物体最短路径的预测方案，人们可以根掘自己的出行时甘j 找到最优 的行驶路径，以便快速地达到出行的目的地。事实上，这一预测方案是根据路段的 时间代价函数给出的，事实上，方案给出的最优行驶路径已经考感了各路段的交通 状况，因此，这一方案的应用可以提高路网整体的交通运行能力。 最后，根据对物体到站时日j 的实时预测方案，人们可以快速而全面地了解各公 共交通工具到达站点的时剃，这时l 8 j 信息，可以帮助人们有效地规划自己的出行 路线。 总而言之，本文的工作对于城市道路交通状况的研究具有十分重要的参考价 值，尤其是对于交通的出行安排，它具有重要的提罨意义。 1 4 本文的主要工作 由前面的论述，可以知道，本文重点研究的是物体移动轨迹的跟踪，查询和预 测方案。作为智能交通系统研究的一个部分，本文的研究具有十分重要的应用价 值。以下是本文所做的主要工作，第一，通过与区域序列轨迹模型的比较，本文论 述了路段序列轨迹模型的优越性。第二，通过路段序列的轨迹表示模型，本文研究 了物体轨迹的查询和跟踪策略。第三，通过对移动轨迹时问信息的分析，本文研究 了道路网内路段的时间代价，并给出了路段时间代价函数的计算方法。基于路段的 时间代价函数，本文给出了物体行驶路径的动态优化方案及物体到站时问的实时预 测方案。 i i i 海人学颀i ：l o f 究生论文 从第二部分起，所研究的内容都是本文的重点，本文将通过理论分析来阐明文 中所提出的研究方案具有可行性和优越性，在此基础上，本文给出了一些具体的研 究方案及相关算法。以下是具体的章节安排： 第一章，绪论，主要介绍了与本课题相关的研究背景、研究意义、国内外的研 究现状及本文的主要工作。 第二章，简单介绍了区域序列的轨迹表示模型。通过结合道路网物体的移动特 点，本文提出了一个基于路段序列的轨迹模型，并分析了路段序列的轨迹模型相对 于区域序列轨迹模型的优点。 第三章，通过物体路段序列的轨迹表示模型，比较系统地分析了物体移动轨迹 的跟踪和查询方案。 第四章，通过对轨迹时问信息的分析，研究了路段的时间代价函数，并给出了 物体最优行驶路径的预测方案。 第五章，总结全文，并给出了一些后续的研究计划。 6 第_ 二章物体移动轨透的表d 模型 第二章物体移动轨迹的表示模型 出于物体在运动时其位置是连续变化的，而连续地记录移动物体的位置信息会 很快地耗完计算机的存储空间，更不要说计算机如何对物体进行查询等操作了。因 此，在实际应用中，为了研究物体的移动轨迹，一般都是通过离散地记录物体位置 来进行的。在这种研究方式下，物体的移动轨迹可以通过位置序列柬进行描述，其 精度取决于位置信息的密度。随着卫星定位技术的发展，物体的位黄信息可以通过 g p s 系统来获得。这一技术支持j 下是目静移动物体研究的基础。同时，出于移动物 体通过g p s 系统接收到是物体的地理位置坐标，因此，物体的移动轨迹可以最简单 地通过一串地理位置坐标来进行描述。然而，在实际应用中，物体轨迹的跟踪和查 询往往是通过给定具体的区域或者路段来进行的。也就是兑，基于坐标序列的轨迹 模型在实际应用中没有很高的应用价值。 2 1 基于区域序列的轨迹模型 在实际生活中，物体的运动情况通常可以分为两类，一，物体在其所处的空问 内，运动方式不受限制，比如海豚，其在海洋中的运动方式可以认为是不受限制 的。二，物体在其所处的空问内，运动方式受到限制，比如机动车辆，其运动受到 道路网的限制。事实上，物体受限运动可以被看作是物体不受限运动的一个特例。 一般情况下，人们在查询物体的位置信息时，往往不关注物体具体的坐标信息，而 只关心物体所在的区域信息。因此，物体的移动轨迹可以通过一个区域序列i l5 】来进 行描述。同时，运动空日j 的区域划分可以根据实际研究的需要柬进行。 2 1 1 轨迹的区域序列表示 这一轨迹模型假定物体的位置信息是定时更新的，位置更新的时i 日j 闻隔也被称 为一个时间单位( t i m e u n i 0 。它取值的大小决定了物体移动轨迹的表示精度。图2 1 给出了物体o 移动轨迹的一个示意。其中，物体所在的空间被划分为了a ，b ，c ， d ，e 和f 等六个区域，其中轨迹中的黑点表示的是物体移动位置的每一次更新。这 里假定移动物体配备有定位接收装置，其每一次位置的更新都是通过全球定位系统 g p s 来实现的。 河海人学颂i ：研究生论丘= l i l2 1 物体扫：区域问的移动轨迹i 笙l 出图可知，物体o 的移动轨迹可以通过下式来表示，如下所示： 根据式2 1 可以知道，物体轨迹是一个字符串表示，同时由于物体的位置信息 更新是定时的，因此，轨迹中同一连续的区域序列也就隐含了物体在此区域上的运 动时问。如轨迹中的a a 区域序列就表明了物体在连续两次位置更新时，都处在区域 a 中，基于这一情况，本模型认为物体在区域a 上的运动时l 日j 即为两个时日j 单位。基 于这一点，那么轨迹表达式就可以通过结合相应的时| 日j 参数来进行拓展。 下面模型将结合正则表达式，给出物体轨迹的表示方案。现假定物体所在的空 间被划分为一个有限的区域集合，每个区域都由有限字母集中的一个字母来唯一 地进行标识，同时，轨迹中每一位嚣更新的时| 日j 间隔都是相同的。为了方便起见， 现假定时间单位为1 分钟，另外假定变量集合为p ，并且n u = m ，同时令 f = z o o 。那么物体的移动轨迹就可以通过下式来进行表示， t r a j e c t o r y ( d ) = 焉 巧) 岛 正 晶 瓦 ( 2 2 ) 其中，j 表示的是移动物体o 所在的空问区域，s l ；7 ：表示的是移动物体在区域 s 上的运动时问。在下面具体的实例中，a ，b ，c ，是中的标示符， x ， y ， z 是变量集u 中的变量标示符。为了方便起见，下面将省略时问参数，物体的移动轨 迹只用简单的区域序列五j ，j 。来表示。 2 1 2 轨迹的查询描述 。 一个自然的查询过程就是利用f = z o o 中的证则表达式来构建物体的移动模 式，然后，通过物体移动轨迹与移动模式的匹配柬查询和跟踪符合要求的移动物 体。假定现有一移动模式e = d x + a s + x ，加号表示物体在区域上至少有一次位 第二章物体移动辘迹的表示模型 置信息的更新。假如现有一物体的移动轨迹为厂彳a c b c ，通过分析就可以知道该轨 迹与给出的移动模式e 相匹配，因为模式包含一个单词为口 曲 x ，将交量 x 设为c ，就可以显而易见的发现两者是匹配的。然而，变量的赋值有时候会引起混 淆。比如，移动模式的正则表达式占= 6 捌 工) + f ，那么轨迹6 口f 就可以给出模式 的两个的匹配，一是6 x c ，此时变量 x 必须为a ，第二个匹配就b z t c ，此时变 量 x 可以放任意赋值。为了构建安全可靠的模式，即每一个与移动模式匹配的单 词，其变量的赋值是明确的，模型对移动模式采用了更严谨的定义方式。 定义：物体的移动模式就是一个在集合r = z u ，上的花则表达式p ，其中每一个 尸的变量都应出现在语言l ( p l 所表示的每一个单词中。 上述定义保证了所有在移动模式中的变量都会在查询过程中得到一个相关的赋 值。假如，现有一个移动模式p = 纠6 ) + 柏j ) + 被用来查询和跟踪移动物体轨 迹，那么在所有符合该模式的轨迹中，变量 x 就会出现在所有表达式构成的单词 集合l ( p ) 中，也就是说只要给定的轨迹与模式相匹配，那么变量就会被唯一的赋 值。物体轨迹具体的查询过程是通过构建查询模式来进行的。在给出查询模式的表 述之前，模型将移动模式变量的集合定义为f a r 护) 。 查询模式q 可用一个二元组( _ p ， c i ，c 2 ，一c ，) ) 柬表示，其中p 表示物体的移动模 式， c i ，c 2 ，c ， 表示一组限制条件，比如毛s ：，其中s i5 ：u 比r ( p ) ，查询结 果可用r 甜曲( q ) 来表示。 在此基础上，模型给出了轨迹匹配的一个数学描述。假定物体d 的移动轨迹存 在一个映射v ：u 叶z ，且其符合下面的两个属性， 1 v 满足所有限制条件e ，i = l ，2 一，n 2 o z r a j 属于“p ) ) 那么就称物体0 r e s u l t ( q 1 ，即找到了符合查询模式的移动物体。其中，查询模式 中的限制条件可以用来限定变量的赋值，比如 工a 。对于给定的查询模式，变量 的取值范围可用幽( z ) 表示，它表示变量所有可能的取值。 9 i i i 海人学坝i 。研究生论文 2 1 3 轨迹的查询操作 在了解了上述的概念之后，文章下面将介绍模型对于轨逊查询的具体方案，该 方案主要分为两步：第一，根掘所给定的物体移动模式p ，构建一个有限状态的自 动机。第二，利用有限自动机来匹配物体的移动轨迹。匹配过程也是模式p 中变量 的一个赋值过程。具体的操作如下， 因为移动模式p 是集合i 上的正则表达式，所以第一步就是根据模式p 构建一 个状态不确定的有限自动机n f a ( n o n - d e t e r m i n i s t i cf i n i t es t a t ea u t o m a t o n ) n r ，其中 坼接受所有模式p 所对应的f 语言集。第二，根据r 构建一个新的自动机心， 它将检查上的物体移动轨迹t 是否匹配，并同时给变量进行赋值，其中 ，啦p ) ) 。 从根本上讲，以是，的扩展，扩展的基础主要有两点：( i ) 假定变量 x 没有 条件约柬，在轨迹匹配过程中，变量 x 标识了区域2 ，那么就将变量 的值赋 为口。( i i ) 保存自动机每一个状态所需绑定的变量。舨定义如下， 1 设s t a t e s ( n x ) ：的状念集，那么可以知道m 以s ( 以) = s t a t e s ( n ，) ”l ， 其实它表示了所有可能的，的状念与模式，中变量的赋值之间的关联。自动 机从的一个状态在此可用 来表示。 2 设帆的接受状态集为a c c e p t ( n ，) ，可以知道口c c 酬) = 叩c 甲r ) x z 7 ”。 3 设煺上的状态转移函数为晚，可以知道区是r 的状念转移函数屏的变型， 具体如下， 如果8 a s , ，口) = 墨是有限自动机n r 上的一个区域转换，其中口，那 么龟( ( s ，v ) = 。换句话说，这里的转换与绑定的变量无关。 如果屏 ， 工) = s j 是j 上的一个转换，其中 x u ，那么可知 i 如果v x ) 盯， x 与口被条件绑定 最( ) 2 如果v 泡x ) = 口 ( 2 3 ) 【不定值，除上述情况之外 只要救的接受状态 实现，那么所输入的轨迹就是匹配的，同时，模式 中的变量也会取得相对应的值。实时检查物体的移动轨迹是否与查询的轨迹模式匹 1 0 第一二章物体咎动轨迹的表4 ；模型 配，并不需要像上面一样建立一个完整的自动机，而只需要逐步检查物体移动所生 成的轨迹，对变量作相应的赋值，看其是否能与模式相匹配。下面将给出一个实例 来进行说明， 例i ：假定移动模式p = 0 扣) + 置0 陋) + ，图2 2 给出了该模式所构成的自动机，它 将用于识别语言集三p ) 中的所有单词，其中知是初始状态，和墨结束状念。 l t l2 2 移动模式( a p ) + 每x + ( a m ) + 的何限自动帆气 假定现有一移动物体，依次接收到自身的区域位置信息如下：4a ，b ，b ，c 和a 。 现根据上述自动机进行匹配，表2 1 的每一行表示了在依次读入相关状态之后的自 动机中的状念，同时，也对其中的变量x 取值作了分析。表中用对接收的状态进 行了加粗，这也表明了该轨迹跟所要查询的轨迹模式相匹配，即其为一个成功的匹 配。 表2 i 移动物体轨迹的匹配过科 输入状态 在m 中所获得的状态 a a 【2 】 ， a 【2 】b 岛， x ：j ) ， ， a 【2 】b 2 】 ， ， a 【2 】b 【2 】c a 【2 】b 2 1 c a 河海人学坝l 埘究生论文 从对例l 的分析可以看出，在对输入轨迹作相关的匹配时，需要存储自动机同 一状态上变量不同的赋值，如表中第5 行所示，变量固x 可取a 或者b 。在最坏的情 况下，处理过程需要同时存储i 册，甜( ，】i 习个状态，即表示需要存储为了达到结束 状态的变量有可能的所有赋值。 随着数掘库和查询数量的增大，存储大量相关的信息束持续处理匹配过程对计 算机来讲丌销是巨大的。因此在具体的应用中，需要限制模式语言表达的能力以便 降低内存的需求。换句话说，就是需要限制变量的赋值范围。比如在上例中，给定 限制条件 x “， j 6 ，那么可以知道，轨迹最终的匹配结果只有一个，且变量 只有个唯一的赋值，即 x = c 。 2 2 道路网模型概述 由于本文研究的是道路网内物体的移动模式。物体在道路网上的运动是一种受 限运动。事实上，道路网上的物体是沿着道路网的路段来移动的。因此，在展丌对 物体移动模式的研究之前，需要对道路网模型进行一些地分析和研究，以便有效地 给出道路网物体移动模式的研究模型。道路网模型作为智能交通系统研究中的一个 重点，能有效地将现实世界的道路结构抽象成计算机所能识别的数据模型。下面本 文将给出道路网研究的一些基本内容，主要包括空| b j 数据模型，道路网模型的定义 及其抽象结构。 2 2 1 空间数据模型 数据模型是连接现实世界和计算机世界的桥梁，它是现实世界的一种数学抽 象，通过对现实事物一些基本特征的概括，提取出一定的抽象规则，以便用来描述 客观事物及其联系。这种描述包括数据内容的描述和各类实体数据之间联系的描 述。事实上，数掘模型是数据表达的概念模型，是描述数据的一种手段。 在g i s 研究领域中，由现实世界到g i s 的抽象过程可以通过三个不同层次的表 示模型柬描述，它们分别是概念模型，逻辑数掘模型，物理数据模型1 5 1 。根掘这种 划分，建模过程可分为三步，一，选择一种数据模型来对现实世界的数据进行概括 和描述；二，选择一种数掘结构束表达该数据模型；三，选择一种适合于记录该数 据结构的文件格式。 第一二章物体移动轨迹的表刁；模型 数掘模型设计的目的是将客观事物抽象成计算机可以表示的形式。概念数据模 型着重是获得对客观现实的一个j 下确认识，是一个面向用户、面向现实世界的数据 模型。它主要描述系统中数据的概念结构，按用户的观点来对数据和信息建模，是 现实世界到信息世界的第一层抽象。逻辑数据模型面向机器世界，用于描述系统中 数据结构，主要研究数掘的操作以及操作后数据完整性等问题。这类模型通常有严 格的形式化定义，而且常常会加上一些限制和规定，以便于机器的实现。物理数据 模型是数掘抽象的最底层，主要包括空间数据的物理组织，存取方法和数掘库总体 存储结构等内容。索引文件就是常用的存取方法，常规的索引方法有b - t r e e ，四叉 树、r - t r e e 等。 对于空问数据库而言，数据模型是一条或一组用于标识和表示空间参照对象的 舰则。空间数据模型是关于现实世界中空间实体及其相互联系的概念，它为空白j 数 据的组织和空间数据库的设计提供了基本的参考和方法。空h j 数掘模型通常可分为 两大类：对象模型和场模型。 在空间数据模型中，一条河流，可以按比例表示为一条一维的曲线，一口井可 以表示成零维的点，这些都是对象模型的例子。对象模型很适合表示离散的、有固 定形状的空f b j 实体，如湖泊、道路网和城市。这种对象模型是概念化的，可以采用 矢量( v e c t o r ) 数据结构将其映射到计算机系统中。矢量数掘结构将区域映射成多边 形，线条映射为多线，点映射为点。 相对于对象模型，场( f i e l d ) 模型通常用于表示连续的或无固定形状的概念，例如 温度场或云区，一个场就是一种函数，它将基本参照框架映射到一个属性域上。对 于温度来说，最常用的属性域是摄氏和华氏。在计算机中，场模型是用栅格( r a s t e r ) 数据结构来实现的。栅格数据结构把基本空闯划分成均匀的网格。出于场值在空问 上是连续的，所以每个栅格的值一般采用位于这个格子内所有场点的平均值表示。 场的其它常用数据结构还有不规则三角网、等高线和点网格等。 道路网作为交通地理信息系统【”1 的核心研究对象之一，对其构建空问数掘模型 是交通地理信息系统实现的基础。目前随着智能交通系统的发展，作为辅助城市交 通管理与规划的有效技术手段，交通地理信息系统g i s - t 在i t s 中占有举足轻重的 地位。特别地，通过与g p s 、无线通讯、i n t e m e t 和虚拟现实等高新技术的有机结 合，它不但可以储存、管理和更新交通网络中的数据库，而且可以辅助交通网络规 i l 海人学顾l 研究生论文 划，进行交通信息管理。它可以建立广泛的、实时的数字交通信息服务体系，实现 全数字化交通信息的实时发布、储存与检索，为交通实时数据管理、空i 日j 分析、网 络优化、车辆智能导航、客货运输调度及居民出行等提供有效的技术支持。通常情 况下，g i s t 主要涉及三种空间数据模型，区域模型，指的是在跨越空i 日j 时表示连 续交化现象的模型； 离散实体模型，简单的说，就是研究离散的实体( 点、线或多 边形) 及其相关属性的集合的抽象表达；网络模型，代表拓扑连接的嵌于地表的线 性网络变化的抽象表达i 憎l 。 上述三种交通系统的数据模型几乎包括了所有交通系统研究所用到的数据模 型。道路网在交通系统数据模型中常用许多具有多种属性的线段来表示，道路网中 的各种标志性建筑则可用离散的点来表示，交通网络分析则可利用线性代数来进行 分析，这些方法对实现道路交通系统的计算机表示起到了一定的作用。在交通领域 中，围绕以弧和点的概念建立的网络模型是最受关注的。 2 2 2 道路网结点模型 众所周知，道路网是由高速公路，普通道路，高架桥，桥梁，隧道等道路元素 通过各式连接所购成的一个交通网络。根据图论的相关知识，道路网可以被简单地 表示为一个无向图g ( v ，l ) ，如图2 3 所示，其中v 表示道路网结点的集合，l 表示 道路网路段的集合。 v t v 2 幽2 3 道路叫简单抽象模型g lv l 1 基于无向图道路网模型只是简单地描述了道路网的一个几何属性，主要给出了 道路网中结点和路段的连接情况。众所周知，道路网是受一定的交通规则约束的， 因此，道路网模型除了要表示道路网的几何属性之外，还需要表示道路网的交通信 息。交通信息主要包括道路的交通代价、路段约束、路口约束和转弯代价等内容。 1 4 第_ 二章物体移动轨迹的表1 i 换型 这些交通信息对于道路网本身是没有太多意义的，它们的意义在于给出了道路网与 其上移动物体之间的相互关系。下面将简单地给出这些交通信息的相关含义， 交通代价对于道路网上的移动物体来说，可以是道路路段的长度，也可以是移 动物体在其上运行所需的时白j 。路段约束可以用柬描述移动物体在该路段上行驶的 方向，或用来描述移动物体在该路段上的速度限制，或用来描述路段对于移动物体 类型的限制，另外，其也可以用束描述路段上移动物体行驶时日j 的限制，如移动物 体只有在周一到周五的时间内可在此路段上行驶，因为周术此路段可能为步行街。 路口约束主要是描述了移动物体在相邻的路段之日j 是否可以通行，转弯等信息。转 弯代价和交通代价相似，可以用来表示移动物体转弯所需的时间。 通过上述的分析，可以发现图2 3 所给出的道路网模型是无法用来描述这些交 通信息的。为了尽可能地描述这些交通信息，文章需要对上述抽象模型进行拓展， 这罩很自然地会联想到有向图模型，因为有向图可以很好地表示道路网路段的方向 性。图2 4 给出了一个基于图2 3 的有向图g ( v ! d ) 其中v 表示道路网结点的集 合，d 表示道路网有向路段的集合。 蹦2 4 道路埘肯舟钧单小惑酗 如图2 4 所示，连接道路网结点v i 和v 2 的路段矾是一个单向行驶路段，同理， 以也是连接道路网结点坞和v ，的一个单向行驶路段。另外，通过与图2 3 的简单比 较，就可以发现有向图相对于无向图而言，由于路段数量明显多于无向图，所以在 存储路段时会占用更多的存储空间。 当然，这旱给出的有向图模型并不能表达上述所有的交通信息，事实上，上述 交通信息的表达可以通过定义相关的对象化空间数据模型来解决。下面通过给出路 段的空间数据结构来加以说明。图2 5 给出了路段的一个简单的空问数据结构， 5 i 一 智f 矽、 州海人学坝i ：研究生论史 d a t as t r u c t u r eo f r o a d _ s e g m e n t d 删来唯一的标识某一路段 l e n g t h ，来表示道路路段的长度 s t a r t ，圳来表示路段的起始点位置p o i n t e n d ，圳来表示路段的终点位置p o i n t v e l o c i t y ， 川来表示路段对丁移动物体的速度限制 t i m ec o n s t r a i n t s 。 ，h j 米表示路段的时间限制 o b j e c tc o n s t r a i n t s + ，h j 米表示路段对丁移动物体类叩j 的限制 幽2 5 路段的卒问数据结构 由图2 5 可以看出，道路网交通信息，如交通代价，路段约束等都可以通过定义相 关的对象化空自j 数据结构来加以表达。在给出了上述交通信息的一般表述之后，下 面来进一步分析如何利用模型束表示路口约束的交通信息。图2 6 给出了一个描述 路口约束的示意图。 一i i f l 一 玎一占支：确三；一c j | 厂 b 幽2 6 路u 约束永卷幽 根据图2 6 所示的路口约束示意图，可以简单地给出一个道路网有向图模型柬描述 上述道路的基本构架，如图2 7 所示， c 幽2 7 道路嘲自向捌模型 第- 二章 物件移动轨迹的表4 ；模型 分析图2 ，7 可以发现，所给出道路网模型并不能很好地表示路口约束的交通信息。 原因在于路径( b o a ) 在图2 6 中是被禁止的，然而图2 7 所给出的模型表示了路段 ( b o ) 和路段( o - a ) 是可以连通的，因此，图2 7 所示的道路网模型并不能反映这一道 路网中的路口约束信息。为了有效地表示道路网路口约束的交通信息，文章将给出 目前研究的两个主要方案，一就是对有向图模型进行拓展，以便其能表示道路网路 口约束的交通信息：二就是将路口结点作为超点( s u p e r - n o d e ) 来处理，这一方法事实 上与给出路段对象化数据结构的方法相似，超点其实就是路口结点的一个对象化空 间数据结构。下面将通过两个独立的小节来加以阐述。 2 2 3 结点扩展模型 通过上一节的分析可以看到，简单的有向图道路网模型并不能有效地表达道路 网路口约束的交通信息。事实上进一步分析，可以发现，只要对现有的有向图模型 进行一定拓展，就能解决路口约束的表示问题。在给出拓展模型之静，需要先来分 析移动物体在道路结点处的运行情况。为了清晰地给出一个物体在道路路口处的运 动情况，现将图2 6 中的道路路口d 划分成四个小区域柬分析，如图2 8 所示， + b 豳2 8 道路州路uo 的示意幽 图2 8 将路口o 划分成了p l ，d 2 ，0 3 ，0 4 等四个部分，由图可知从路段( b - 0 4 ) 过来 的移动物体，禁止进入路路段( d i a ) ，由于结点o i 和d 4 在这里是相互独立的，那么 模型就可以通过有向线段币的存在性来表示该路口左转弯的约束条件。图2 9 是该 实例的一个结点拓展模型的示意图。 1 7 河海人学坝i ：l i j f 究生论文 幽2 9 坌；! i 点拓艟摸墅 这一模型是将结点d 分裂成结点o i ，0 2 ，仍和g l 来处理的，出于路段( o c ) 为 单向行驶路段，因此，在图2 9 中，结点仍被省略了。通过这一方式，拓展后的道 路网模型就能有效地表示道路网的路口约束信息。然而，这一模型也有其自身的缺 点，通过与图2 7 给出的模型示意图相比较可以发现，这一拓展模型的结点和路段 都增加了，且随着制约条件的增加，该道路网模型需要傲更多的分裂处理，这就会 大大增加孩道路网模型对于图计算和处理的复杂性，因此，该模型对于系统的存储 和计算都有较高的要求。这就是说，在处理复杂的道路网时，该模型往往会因为需 要作过多的结点处理而影响到模型的数据处理效率。 2 2 4 道路网超点模型 为了保持道路网模型