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

呙维; 龚健雅; 朱欣焰

美国《工程索引》（EI）核心期刊
美国《剑桥科学文摘》（CSA）收录期刊
荷兰斯高帕斯数据库（Scopus）收录期刊
英国INSPEC数据库（SA）收录期刊

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

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

呙维, 龚健雅, 朱欣焰

文章导航 > 武汉大学学报 ● 信息科学版 > 2009 > 34(7): 864-868

呙维, 龚健雅, 朱欣焰. 一种基于层次拓扑模型的分布式最短路径算法[J]. 武汉大学学报 ● 信息科学版, 2009, 34(7): 864-868.

引用本文:

呙维, 龚健雅, 朱欣焰. 一种基于层次拓扑模型的分布式最短路径算法[J]. 武汉大学学报 ● 信息科学版, 2009, 34(7): 864-868.

GUO Wei, GONG Jianya, ZHU Xinyun. An Efficient Distributed Shortest Path Algorithm with Hierarchically Structured Topographical Model[J]. Geomatics and Information Science of Wuhan University, 2009, 34(7): 864-868.

Citation:

GUO Wei, GONG Jianya, ZHU Xinyun. An Efficient Distributed Shortest Path Algorithm with Hierarchically Structured Topographical Model[J]. Geomatics and Information Science of Wuhan University, 2009, 34(7): 864-868.

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

¹武汉大学测绘遥感信息工程国家重点实验室,武汉市珞喻路129号430079

基金项目: 国家973计划资助项目(2006CB701305)

详细信息

作者简介:
呙维,博士生,现从事分布式计算、雷达干涉测量、智能目标识别与提取等研究。

中图分类号: P208

An Efficient Distributed Shortest Path Algorithm with Hierarchically Structured Topographical Model

¹ State Key Laboratory of Information Engineering in Surveying,Mapping and Remote Sensing,Wuhan University,129 Luoyu Road,Wuhan 430079,China

Funds: 国家973计划资助项目(2006CB701305)

摘要: 为整合已有的不同地点的GIS路径服务,实现网络拓扑数据的全局最短路径查询,提出了一种基于层次拓扑模型的分布式最短路径算法,并且着重针对网络传输和计算效率问题,提出了两种优化方法。
- 分布式计算 /
- GIS /
- 最短路径 /
- 层次拓扑模型
Abstract: The route computation module is one of the most important functional blocks in a dynamic route guidance system.Although various algorithms exist for finding the shortest path,they are faced with the networks in the same server without distributed environment.We present an efficient distributed hierarchical routing algorithm that finds a near-optimal route and evaluate it on a large city road network,which consists of a lot of small networks which are placed on different servers.Solutions provided by this algorithm are compared with the stand-alone traditionally by hierarchical routing solutions to analyze the same and different points.We propose two novel but simple heuristic to substantially improve the performance of the hierarchical routing algorithm with acceptable loss of accuracy.The improved distributed hierarchical routing algorithm has been found to be faster than a local A* algorithm.
- distributed computing /
- GIS /
- shortest path /
- distributed hierarchical routing

[1]	李改肖, 吕程, 彭认灿, 董箭. 一种利用双侧凸包扩张模型的路径快速规划算法 . 武汉大学学报 ● 信息科学版, 2021, 46(1): 58-64. doi: 10.13203/j.whugis20180469
[2]	徐斌, 张艳. 地下水化学类型分区的GIS空间分析模型 . 武汉大学学报 ● 信息科学版, 2019, 44(6): 866-874. doi: 10.13203/j.whugis20170295
[3]	刘海燕, 庞小平. 利用GIS和模糊层次分析法的南极考察站选址研究 . 武汉大学学报 ● 信息科学版, 2015, 40(2): 249-252+257.
[4]	李青元, 李洪省, 刘皓晨. GIS符号库数据模型抽象及其交换格式研究 . 武汉大学学报 ● 信息科学版, 2008, 33(6): 565-568.
[5]	陈鹏, 孟令奎, 宋杨. 三维GIS中基于空间拓扑约束条件的R树研究 . 武汉大学学报 ● 信息科学版, 2007, 32(4): 347-349.
[6]	汤仲安, 史文中. 矢量GIS平面随机线元等概率密度误差模型的概率算法 . 武汉大学学报 ● 信息科学版, 2006, 31(8): 736-739.
[7]	王涛, 蔡晓斌, 陈晓玲, 吴玮. 基于RS/GIS技术与数值计算的库岸边坡稳定性研究 . 武汉大学学报 ● 信息科学版, 2005, 30(10): 917-920.
[8]	朱永清, 李占斌, 崔灵周, 鲁克新. 基于GIS流域地貌形态特征分形与计算方法研究 . 武汉大学学报 ● 信息科学版, 2005, 30(12): 1089-1091.
[9]	黄慧. 基于边-节点和原子属性的多比例尺GIS数据模型 . 武汉大学学报 ● 信息科学版, 2004, 29(12): 1067-1070.
[10]	王新洲, 汤仲安, 陈志辉. GIS中不规则样条拟合曲线的ε_m模型带 . 武汉大学学报 ● 信息科学版, 2004, 29(1): 58-62.
[11]	翁敏, 毋河海, 杜清运, 蔡忠亮. 基于公交网络模型的最优出行路径选择的研究 . 武汉大学学报 ● 信息科学版, 2004, 29(6): 500-506.
[12]	汤仲安, 王新洲, 纪现华. 矢量GIS平面随机线元误差模型建模机理 . 武汉大学学报 ● 信息科学版, 2004, 29(11): 968-972.
[13]	王晏民, 李德仁, 龚健雅. 一种多比例尺GIS方案及其数据模型 . 武汉大学学报 ● 信息科学版, 2003, 28(4): 458-462.
[14]	童小华, 刘大杰, 龚健雅. GIS中宗地面积的平差模型与方案探讨 . 武汉大学学报 ● 信息科学版, 2003, 28(2): 182-187.
[15]	童小华, 史文中, 刘大杰. GIS中数字化数据误差的分布检验与处理 . 武汉大学学报 ● 信息科学版, 2000, 25(1): 79-84.
[16]	王喜春, 边馥苓, 何勇. 域分析、域模型在GIS中的应用 . 武汉大学学报 ● 信息科学版, 2000, 25(5): 437-442.
[17]	张保钢, 朱凌, 朱光. GIS中位置信息的通用数据质量模型及其质量控制 . 武汉大学学报 ● 信息科学版, 1999, 24(2): 134-137,141.
[18]	孟令奎, 边馥苓, 刘玉贤. GIS环境下污水管网设计流量的快速计算 . 武汉大学学报 ● 信息科学版, 1997, 22(1): 16-20.
[19]	孟令奎, 边馥苓, 陈晓宁. 基于GIS的城市雨水管网优化设计模型研究 . 武汉大学学报 ● 信息科学版, 1996, 21(4): 361-365.
[20]	李德仁, 彭美云, 张菊清. GIS中线要素的定位不确定性模型研究 . 武汉大学学报 ● 信息科学版, 1995, 20(4): 283-288.