一种基于层次拓扑模型的分布式最短路径算法.doc

 第 34 卷 第 7 期 2009 年 7 月 武 汉 大 学 学 报 · 信 息 科 学 版 Geo matics a nd Info r matio n Science of Wuha n U niver sit y Vol . 34 No . 7 J uly 2009 文章编号 :167128860 (2009) 0720864205 文献标志码 : A 一种基于层次拓扑模型的分布式最短路径算法 维1 龚健雅1 朱欣焰1 呙 ( 1 武汉大学测绘遥感信息工程国家重点实验室 ,武汉市珞喻路 129 号 ,430079) 摘 要 :为整合已有的不同地点的 GIS 路径服务 ,实现网络拓扑数据的全局最短路径查询 ,提出了一种基于 层次拓扑模型的分布式最短路径算法 ,并且着重针对网络传输和计算效率问题 ,提出了两种优化方法 。 关键词 :分布式计算 ; GIS ;最短路径 ;层次拓扑模型 中图法分类号 : P208 最短路径问题已经得到了广泛的应用 ,但是 针对的数 据 都 位 于 同 一 地 点 , 而 由 于 数 据 的 归 属和目前 GIS 互 操 作 的 发 展 , 拓 扑 数 据 一 般 都 分布在不 同 的 地 方 , 并 且 由 不 同 的 服 务 提 供 商 提供最短路径服务进行维护 ,传统的最短路径研 究并没有考虑这种情况 。本文研究如何将散布在 不同地点上的最短路径服务组合起来 ,形成一种 全局拓扑意义上的更为强大 、范围更广的最短路 径服务 。 单机最短路径问题在国内外都已经有了很多 研究 ,大体可以分为基于平面图和基于层次图的 最短路径算法 。E. W. Dij k st ra 在 1959 年提出的 Dij k st ra 算法是平面图算 法中 最 为经 典的 , 且 已 被广泛 使 用 。文 献 [ 1 ] 提 出 了 一 种 层 次 图 模 型 Hi Ti 模型 。这些算法能有效地加快大型网络最 短路径查询时间 ,但是其数据全部位于本地 ,没有 考虑分布式最短路径查询 。针对本文提出的最短 路径问题 ,国内外的研究还很少 ,文献 [ 2 ] 虽然提 出了该问题 ,并对解决方法进行了简单的叙述 ,但 是没有给出具体的算法和详细分析 。文献 [ 3 ,4 ] 研究的分布式多级道路网还是位于同一空间数据 库中 ,分布式仅仅是指提供服务以供远程用户调 用 。本文将首先给出分布式环境下的层次网络模 型相关定义 ,由该定义引出分布式虚拟层次图创 建算法 ,然后给出针对该算法的优化方法 ,最后给 出原型系统运行图和最终查询时间表 ,并进行相 关评价和分析 。 1 分布式环境下的层次网络模型定 义 传统层次网络模型的建立是按一定的规则将 一个大型网络划分为若干子网络 ,而分布式层次 路由与此不同的是已知若干小型网络组织成一个 具有层次关系的网络 ( 每个局部拓扑网络自然形 成层次网络中的子网 ,而不需要另行划分) ,主要 思想是分布式子网通过边界上的同名点来进行衔 接 ,这些子网中的衔接点 ,本文称为外接点 。同名 点确定准则是通过 拓扑 网 络上 的属 性和 空 间信 息 ,可以人工和自动判断 。自动判断是通过两个 点的空间距离 ,如果小于阈值则认为是同一点 ;人 工判断是在自动判断的基础上加上属性信息的判 断 。每个子网都拥有若干外接点 ,如果将这些外 接点提取出来 ,按照一定的规则进行组织 ,就可以 形成一个跨越全部子网 、位于其上的高层网络 ,从 而形成分布式环境下的层次网络模型 ,分布式最 短路径算法将以此模型为基础来实现 。 定义 1 ( 图 定 义) G = ( N , L , W ) 是 双 向 图 , N ( G) = N = { N i | 1 ≤i ≤n} 是该图的节点集 合 , n 代表了节点数 。L ( G) 是边集合 , L ij 代表了 节点对 N i , N j 。W ( G) = { W ij | W ij = f ( L ij ) } 为边的权重 , W ij 表示边 , L ij 代表了边的权值 , f 是 代价函数 。S ij ( G) 代表了起点是 N i 、终点是 N j 的最短路径上的节点集 合 。S W ij ( G) 代 表 了最 短路径值 。 收稿日期 :2009205220 。 项目来源 :国家 973 计划资助项目 ( 2006 CB701305) 。 定义 2 ( 外接点 、关系定义) 设图集合 S G = 3 优化方法 { G1 , G2 , , Gm } , Gn 是 双 向 加 权 图 。 Rij ( S G) = {〈 N q , N w 〉| N q ∈ N i ∧