分布式多级道路网的动态融合与联合路径规划方法

摘要

本发明涉及分布式多级道路网的动态融合与联合路径规划方法，可有效解决充分利用网络上分布的道路网数据源，提高导航系统服务能力，改善服务质量的问题。该方法是由硬件体系结构、软件体系结构、道路网层次目录结构和算法的步骤构成，本发明提出的分布式多级道路网的动态联合路径规划方法是网络环境下多源导航电子地图数据融合的一种新的实现途径，能有效克服传统的面向数据的融合方法的不足，在保证各数据源的独立性和私密性的前提下，本方法能充分地利用网络上多个数据源的道路网完成路径规划，大大提高导航系统的服务能力，改善服务质量。

说明书

一、技术领域

本发明涉及导航服务，地理空间信息系统，特别是一种分布式多级道路网的动态融合与联合路径规划方法。

二、背景技术

道路网是智能交通系统和位置服务应用中最重要的地理要素，是整个导航电子地图的骨架。导航电子地图的主用用途在于通过道路网完成路径规划，在此基础上向用户提供导航服务。基于道路网的路径规划是导航系统的核心功能。传统的导航系统是独立的，其导航的能力取决于它本身的道路网的特性，如覆盖区域、数据精度和数据质量等。随着我国城市规模的扩大和交通事业的发展，道路网越来越庞大。一个独立的导航系统难以存储涵盖大区域(如全国)全部等级的道路网数据。网络环境下，可能存在很多分布在各处的道路网数据源(通常以数据库的形式存在)，这些数据源分属不同的导航系统。如果导航系统不仅能够利用自己的道路网，同时也能利用网络上的其它道路网，必将大大提高导航服务的能力，改善导航服务的质量。

对多个道路网数据源的利用，现有的方法一般是直接从各数据源获取道路网的全部数据，对这些数据进行融合，生成一个新的道路网，之后在新的道路网上进行路径规划。这是一种事前的、静态的面向数据的融合方法。这种方法存在以下问题：(1)当数据源较多且各数据源的数据量较大时，融合之后的道路网的数据量会非常大，导航系统可能不堪重负；(2)某数据源发生变化后，要重新进行融合才能将变化反映到新的道路网上，现势性不强；(3)从商业利益的角度考虑，道路网作为极具商业价值的资源，数据完全共享的代价太大。因此，现有方法的改进势在必行。

三、发明内容

针对上述情况，为克服现有技术的缺陷，本发明之目的就是提供一种分布式多级道路网的动态融合与联合路径规划方法。可有效解决充分利用网络上分布的道路网数据源，提高导航系统服务能力，改善服务质量的问题。

本发明解决的技术方案是，根据导航用户终端的请求在网络上实时地选择参与路径规划的道路网，分别进行局部的路径规划，并以Web服务的形式向外提供路径规划的结果，再把这些局部路径规划结果进行综合处理，形成完整的路径规划结果。由于参与路径规划的道路网一般是分布的、多等级的、实时选择的，因此称该方法为分布式多级道路网的动态融合与联合路径规划(简称为联合路径规划)，据此，本发明采用如下技术方案：该方法是由硬件体系结构、软件体系结构、道路网层次目录结构和算法的步骤构成，硬件体系结构是由分布在网络上的导航用户终端、导航服务器和道路网服务器构成，导航用户终端、导航服务器和道路网服务器之间通过互联网进行交互；软件体系结构由导航用户节点、导航服务节点和道路网服务节点通过互联网构成，导航用户节点对应于硬件体系结构中的导航用户终端，导航服务节点对应于导航服务器，道路网服务节点对应于道路网服务器；道路网层次目录结构根据道路网的覆盖区域之间的包含关系确定；算法的步骤是，通过道路网层次目录结构找到覆盖区域同时涵盖起始点和目标点的道路网(称为顶层道路网)，在顶层道路网和它的下层道路网中搜索联合路径规划的起始道路要素，即与起始点的距离小于给定阈值的最近道路要素，在顶层道路网和它的下层道路网中搜索联合路径规划的目标道路要素，即与目标点的距离小于给定阈值的最近道路要素，之后，同时启动搜索轨迹上所有道路网服务节点的路径规划服务，路径规划服务的输入参数是起始点在道路网中的最近道路要素和搜索轨迹中前一个道路网的最近道路要素在道路网中的匹配道路要素，最后将各道路网服务节点的路径规划结果合并，得到联合路径规划的结果。

本发明提出的分布式多级道路网的动态融合与联合路径规划方法是网络环境下多源导航电子地图数据融合的一种新的实现途径，能有效克服传统的面向数据的融合方法的不足，在保证各数据源的独立性和私密性的前提下，本方法能充分地利用网络上多个数据源的道路网完成路径规划，大大提高导航系统的服务能力，改善服务质量。

四、附图说明

图1为本发明的硬件体系结构示意图。

图2为本发明的软件体系结构示意图。

图3为本发明的道路网覆盖区域的包含关系示例图。

图4为本发明的道路网层次目录结构示例图。

图5为本发明的复杂道路网覆盖区域的包含关系示例图。

图6为本发明的复杂道路网层次目录结构示例图。

五、具体实施方式

以下结合具体情况和实施例对本发明的具体实施方式作详细说明。

由图1-图6所示，本发明在具体实施中，是由硬件体系结构、软件体系结构、道路网层次目录结构和算法的步骤四个方面构成，具体是：

(1)硬件体系结构

完成联合路径规划，需要分布在网络上的导航用户终端(PDA、便携式电脑、台式电脑、手机等)、导航服务器和道路网服务器共同参与，它们构成了如图1所示的硬件体系结构。导航用户终端通过互联网与导航服务器进行交互，导航服务器也通过互联网与道路网服务器进行交互。

导航服务器是向导航用户终端提供包括路径规划服务在内的导航服务的地方。网络上可以有多个导航服务器存在。导航用户终端用于向导航服务器发送服务请求并向用户显示服务结果。对于路径规划服务，导航用户终端向导航服务器发送路径规划的起始点和目标点等参数。道路网服务器是指存放道路网数据库的服务器。网络上可以有多个道路网服务器存在。道路网服务器和导航服务器在硬件上可以是重合的，即一个服务器可以同时存放道路网数据库并提供导航服务。

(2)软件体系结构

图1是从硬件的角度给出的体系结构，从软件的角度看，则具有如图2所示的体系结构，由导航用户节点、导航服务节点和道路网服务节点通过互联网构成。显然，导航用户节点对应于图1所示的硬件体系结构中的导航用户终端，导航服务节点对应于导航服务器，道路网服务节点对应于道路网服务器。

道路网服务节点由道路网数据库和在其基础上构建的路径规划服务、最近道路服务和道路匹配服务构成。

导航服务节点是联合路径规划服务的入口点和具体实施者。导航服务节点从导航用户节点接收路径规划的起始点和目标点需求参数，通过道路网目录服务搜索参与联合路径规划的道路网服务节点，启动这些道路网服务节点的路径规划服务，将服务结果进行综合处理，形成最终的联合路径规划的结果返回给导航用户节点。

导航服务节点必须向道路网服务节点提供道路网注册服务。通过道路网注册服务，道路网服务节点将自己的道路网元数据提交给导航服务节点。由导航服务节点根据参与注册的道路网元数据维护一个道路网层次目录结构。

(3)道路网层次目录结构

道路网的覆盖区域是道路网元数据的数据项之一。根据覆盖区域之间是否存在包含关系，在导航服务节点可以将参与注册的道路网组织成层次目录结构。

图3是一组道路网覆盖区域的包含关系的示例，道路网M1的覆盖区域包含M2的覆盖区域和M3的覆盖区域，M2的包含M4和M5的，M3的包含M6和M7……Mn，n为自然整数，根据这样的覆盖区域的包含关系，可将道路网M1、M2、M3、M4、M5、M6和M7组织成如图4所示的道路网层次目录结构，图中的箭头表示包含关系。

图3所示的道路网覆盖区域的包含关系只是一种理想的情况，实际情况可能更加复杂，更常见的情况是，相同(或近似相同)的区域存在两个甚至多个道路网。譬如，图5所示的情况在图3的基础上增加了复杂度，具体来说，存在与道路网M2的覆盖区域相同的道路网M2′，存在与道路网M6的覆盖区域相同的道路网M6′。M2′和M6′在图5中用虚线表示。

根据图5所示的道路网的覆盖区域的包含关系，可以组织成如图6所示的层次目录结构。

(4)算法的步骤

联合路径规划算法是指导航服务节点在收到导航用户节点的路径规划请求后开始执行的算法，主要步骤如下：

第一步：通过道路网层次目录结构找到覆盖区域同时涵盖起始点和目标点的道路网(或道路网集合)，对于道路网集合，根据道路网的等级、精度等属性排序，再依次选取一个道路网。

第二步：通过道路网服务节点的最近道路服务找到距离起始点最近的道路要素(道路要素是现实世界中的道路在数据库中的表达，由路段和其两端的节点构成，是构成道路网的基本单元)，如果二者之间的距离足够小(小于给定的阈值)，那么该道路要素就可以作为联合路径规划的起始道路要素。否则，在包含在当前道路网覆盖区域内的下层道路网中继续搜索联合路径规划的起始道路要素。从下层道路网中选择一个道路网(称之为子道路网)，通过子道路网服务节点的道路匹配服务找到当前道路网中的最近道路要素在子道路网中的匹配道路要素，通过子道路网服务节点的最近道路服务找到子道路网中距离起始点最近的道路要素。如果子道路网中的最近道路要素和起始点的距离小于给定阈值，那么它就可以作为联合路径规划的起始道路要素。否则，在与子道路网同一层的其他道路网中以及它们的下一层道路网中继续按照类似的方法搜素，直到找到与起始点的距离小于给定阈值的最近道路要素，将其作为联合路径规划的起始道路要素。在搜索联合路径规划的起始道路要素的过程中，会形成从顶层道路网(其覆盖区域同时涵盖起始点和目标点的道路网)到起始道路要素所在道路网的搜索轨迹，搜索轨迹的节点为道路网搜索节点；

第三步：通过道路网服务节点的最近道路服务找到距离目标点最近的道路要素，如果二者之间的距离足够小(小于给定的阈值)，那么该道路要素就可以作为联合路径规划的目标道路要素。否则，在包含在当前道路网覆盖区域内的下层道路网中继续搜索联合路径规划的目标道路要素。从下层道路网中选择一个道路网(称之为子道路网)，通过子道路网服务节点的道路匹配服务找到当前道路网中的最近道路要素在子道路网中的匹配道路要素，通过子道路网服务节点的最近道路服务找到子道路网中距离目标点最近的道路要素。如果子道路网中的最近道路要素和目标点的距离小于给定阈值，那么它就可以作为联合路径规划的目标道路要素。否则，在与子道路网同一层的其他道路网中以及它们的下一层道路网中继续按照类似的方法搜素，直到找到与目标点的距离小于给定阈值的最近道路要素，将其作为联合路径规划的目标道路要素。在搜索联合路径规划的目标道路要素的过程中，会形成从顶层道路网到目标道路要素所在道路网的搜索轨迹。

第四步：在完成搜索后，同时启动搜索轨迹上所有道路网服务节点的路径规划服务，路径规划服务的输入参数是道路网中的最近道路要素和搜索轨迹中前一个道路网的最近道路要素在道路网中的匹配道路要素。最后将各道路网服务节点的路径规划结果合并，得到联合路径规划的结果。

本发明在具体实施中，所称的相关技术由以下具体给出：1道路网数据

(1)道路网元数据

道路网服务节点通过导航服务节点的道路网注册服务向道路网服务节点提交自己的道路网元数据。道路网元数据的主要数据项如下表：

  数据项  说明  标识  道路网数据源的唯一标识  覆盖区域  道路网的覆盖区域  最小比例尺  道路网所属地图的最小比例尺  最大比例尺  道路网所属地图的最大比例尺  最小道路等级  道路网中最小的功能道路等级  最大道路等级  道路网中最大的功能道路等级  服务节点  道路网服务节点的网络引用

(2)道路网搜索节点

在搜索联合路径规划的起始道路要素(目标道路要素)的过程中，会形成从顶层道路网到起始道路要素(目标道路要素)所在道路网的搜索轨迹。搜索轨迹的节点(称之为道路网搜索节点)由道路网元数据、起始点在道路网中的最近道路要素、搜索轨迹中前一个节点的道路网的最近道路要素在道路网中的匹配道路要素三部分构成，此外，为了方便沿着搜索轨迹回溯，还需要加上道路网搜索父节点(即道路网搜索节点在搜索轨迹中的前一个节点)。道路网搜索节点的结构如下表所示：

2道路网服务节点的基本服务

道路网服务节点是对道路网数据源的封装，为了参与联合路径规划，必须向外以Web服务的形式提供路径规划服务、最近道路服务、道路匹配服务等基本服务。

(1)路径规划服务

路径规划是指在道路网的支持下找到起始点(或起始道路要素)和目标点(或目标道路要素)之间的最优路径。导航服务节点本身是没有路径规划的能力的，它能做的是选择道路网服务节点，调用它们的路径规划服务。因此，道路网服务节点的路径规划服务是导航服务节点的联合路径规划服务的基础。

路径规划服务的输入参数：起始点(或起始道路要素)、目标点(或目标道路要素)等。

路径规划服务的输出参数：作为路径规划结果的道路要素的集合。

路径规划的算法已经很成熟，常用的有Dijkstra算法、A*算法等经典算法，可以直接利用。

(2)最近道路服务

最近道路服务是指在道路网中查找离给定位置最近的道路要素。所谓“最近”，一般是指给定位置和道路要素的垂直距离最近。最近道路的理想情况是给定位置就在道路上，或者和道路具有邻接性，即二者的距离为零，这是具有现实意义的。比如，车载导航中，车辆的当前位置(作为路径规划的起始点)肯定在某条道路上。又如，位置服务中的兴趣点(作为路径规划的目标点)通常位于道路边上。

最近道路服务的输入参数：位置。位置参数一般是经纬度坐标，也可以是点要素、线要素或者面要素。

最近道路服务的输出参数：离给定位置最近的道路要素。

(3)道路匹配服务

道路匹配服务是给定道路网中的道路要素，在另一个道路网中查找与该道路要素表示相同道路实体的道路要素。导航服务节点挑选参与联合路径规划的道路网服务节点时，需要调用道路匹配服务作为决策的依据；与此同时，道路匹配服务的结果也是导航服务节点对各道路网服务节点的路径规划服务结果进行综合处理的基础。

道路匹配服务的输入参数：待匹配的道路要素(来自外部的道路网)。

道路匹配服务的输出参数：在道路网中与输入的道路要素匹配的道路要素。

常用的匹配算法分为3大类：拓扑匹配，是通过计算候选同名实体的拓扑关系度量作为匹配依据；几何匹配，是通过计算几何相似度来进行同名实体的匹配；语义匹配，是通过比较候选同名实体的语义信息完成匹配。

3道路网目录服务

道路网目录服务在道路网层次目录结构的基础上，在注册过的所有道路网中或者在给定道路网的下层道路网中查找覆盖区域同时包含两个位置(或要素)的道路网集合。

(1)道路网覆盖服务

在注册过的所有道路网中查找覆盖区域同时包含两个位置(或要素)的道路网集合。

道路网覆盖服务的输入参数主要有：位置1(要素1)、位置2(要素2)。

道路网覆盖服务的输出参数：覆盖区域同时包含两个位置(或要素)的道路网元数据集合。

(2)子道路网覆盖服务

在给定道路网的下层道路网中查找覆盖区域同时包含两个位置(或要素)的道路网集合。

子道路网覆盖服务的输入参数主要有：给定道路网元数据、位置1(要素1)、位置2(要素2)。

子道路网覆盖服务的输出参数：覆盖区域同时包含两个位置(或要素)的给定道路网的子道路网元数据集合。

4联合路径规划算法

具体而言，联合路径规划算法由联合路径规划主算法、道路网搜索子算法和联合路径规划执行子算法构成。联合路径规划主算法中调用了道路网搜索子算法和联合路径规划执行子算法。

4.1联合路径规划主算法

算法的输入参数：起始点，目标点

算法的输出参数：用道路要素集合表示的联合路径规划的结果

算法依赖的固定参数：起始点与最近道路的距离阈值(简称为起始阈值)，目标点与最近道路的距离阈值(简称为目标阈值)

算法的步骤：

(1)以起始点和目标点为输入参数调用道路网覆盖服务，找到覆盖区域同时包含起始点和目标点的顶层道路网元数据集合。

(2)对顶层道路网元数据集合排序，排序的规则可视具体情况而定。一种可能的排序规则是按照覆盖区域的面积由小到大排列。还可能兼顾道路网的道路等级。

(3)从顶层道路网元数据集合中取出每一顶层道路网元数据，执行如下的循环操作：

(3.1)以顶层道路网元数据、起始点、起始阈值为输入参数调用道路网搜索子算法(见4.2小节)，得到起始点道路网搜索节点。若起始点道路网搜索节点为空，则结束本轮循环，进入下一轮循环。

(3.2)以顶层道路网元数据、目标点和目标阈值为输入参数调用道路网搜索子算法(见4.2小节)，得到目标点道路网搜索节点。若目标点道路网搜索节点为空，则结束本轮循环，进入下一轮循环。

(3.3)以顶层道路网元数据、起始点道路网搜索节点和目标点道路网搜索节点为输入参数调用联合路径规划执行算法(见4.3小节)，返回路径规划结果。算法结束。

4.2道路网搜索子算法

算法的输入参数：顶层道路网元数据，给定位置(起始点或目标点)，给定位置和最近道路要素的距离阈值(简称阈值)

算法的输出参数：道路网搜索节点(搜索轨迹上的最后一个节点)

算法依赖的固定参数：一个以道路网搜索节点为元素的栈

算法的步骤：

(1)构造起始搜索节点

获取顶层道路网元数据的服务节点的引用，以给定位置为输入参数调用其最近道路服务，得到顶层道路网最近道路要素。

构造起始搜索节点，其道路网元数据为顶层道路网元数据，最近道路要素为顶层道路网最近道路要素，匹配道路要素为空，父节点为空。

将起始搜索节点压入栈。

(2)完成对目录结构中所有道路网的搜索，记录搜索轨迹。循环执行如下步骤：

(2.1)如果栈为空，搜索结束，返回空值。

(2.2)从栈中取出栈顶元素。计算给定位置和栈顶元素的最近道路要素之间的距离，如果距离小于阈值，则返回栈顶元素。

(2.3)以栈顶元素的最近道路要素和给定位置为输入参数调用子道路网覆盖服务，得到子道路网元数据集合。从子道路网元数据集合中取出每一个子道路网元数据，进行如下循环操作：

(2.3.1)以栈顶元素的最近道路要素为输入参数调用子道路网元数据的服务节点的道路匹配服务，得到栈顶元素的最近道路要素在子道路网中的匹配道路要素。若匹配道路要素为空，匹配失败，则结束本轮循环，进入下一轮循环。

(2.3.2)以给定位置为输入参数调用子道路网元数据的服务节点的最近道路服务，得到子道路网中离给定位置最近的道路要素。

(2.3.3)构造道路网搜索节点，其道路网元数据为子道路网元数据，最近道路要素为子道路网中离给定位置最近的道路要素，匹配道路要素为栈顶元素的最近道路要素在子道路网中的匹配道路要素，道路网搜索父节点为栈顶元素。

(2.3.4)将道路网搜索节点压入栈中。

4.3联合路径规划执行子算法

算法的输入参数：顶层道路网元数据，起始点道路网搜索节点，目标点道路网搜索节点

算法的输出参数：以道路要素集合表示的联合路径规划的结果

算法的步骤：

(1)从起始点道路网搜索节点开始沿着其搜索父节点回溯，分别完成其对应道路网从搜索节点的最近道路要素到匹配道路要素的路径规划，并将作为结果的道路要素集合合并。具体的步骤如下：

(1.1)构造空的道路要素集合(命名为“起始点道路要素集合”)。

(1.2)将起始点道路网搜索节点赋值给变量(命名为“当前搜索节点1”)。执行如下循环，循环的条件是“当前搜索节点1”的道路网搜索父节点不为空，即“当前搜索节点1”存在父节点：

(1.2.1)以“当前搜索节点1”的最近道路要素和匹配道路要素为输入参数调用“当前搜索节点1”的服务节点的路径规划服务。

(1.2.2)将上述路径规划的结果加入到“起始点道路要素集合”。

(1.2.3)将“当前搜索节点1”的道路网搜索父节点赋值给“当前搜索节点1”。

(2)从目标点道路网搜索节点开始沿着其搜索父节点回溯，分别完成其对应道路网从搜索节点的匹配道路要素到最近道路要素的路径规划，并将作为结果的道路要素集合合并。具体的步骤如下：

(2.1)构造空的道路要素集合(命名为“目标点道路要素集合”)。

(2.2)将目标点道路网搜索节点赋值给变量(命名为“当前搜索节点2”)。执行如下循环，循环的条件是“当前搜索节点2”的道路网搜索父节点不为空，即“当前搜索节点2”存在父节点：

(2.2.1)以“当前搜索节点2”的匹配道路要素和最近道路要素为输入参数调用“当前搜索节点2”的服务节点的路径规划服务。

(2.2.2)将上述路径规划的结果加入到“目标点道路要素集合”。

(2.2.3)将“当前搜索节点2”的道路网搜索父节点赋值给“当前搜索节点2”。

(3)构造空的道路要素集合(命名为“顶层道路要素集合”)，以“当前搜索节点1”的最近道路要素和“当前搜索节点2”的最近道路要素为输入参数调用顶层道路网元数据的服务节点的路径规划服务，将结果赋值给“顶层道路要素集合”。

(4)将“起始点道路要素集合”、“顶层道路要素集合”和“目标点道路要素集合”的并集作为结果返回。此即为联合路径规划的最终结果。

本发明提出的分布式多级道路网的动态融合与联合路径规划方法是网络环境下多源导航电子地图道路网数据融合的一种新的实现途径，经实践，能有效克服传统的面向数据的融合方法的不足，体现在：(1)道路网数据分布式存储，有效缓解了单个导航系统的存储压力；(2)参与路径规划的任何道路网数据源的变化均能立刻反映到最终的服务结果上，提高了导航服务数据的现势性；(3)每一次服务的结果只是临时性的数据片段，保持了数据整体的私密性，保护了数据源持有者的商业利益，同时也降低了数据共享的门槛。