资源描述：
《一种基于层次拓扑模型的分布式最短路径算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第34卷第7期2009年7月武汉大学学报·信息科学版GeomaticsandInformationScienceofWuhanUniversityVol.34No.7July2009文章编号:167128860(2009)0720864205文献标志码:A一种基于层次拓扑模型的分布式最短路径算法维1龚健雅1朱欣焰1呙(1武汉大学测绘遥感信息工程国家重点实验室,武汉市珞喻路129号,430079)摘要:为整合已有的不同地点的GIS路径服务,实现网络拓扑数据的全局最短路径查询,提出了一种基于层次拓扑模型的分布式最短路径算法,并且着重针对网
2、络传输和计算效率问题,提出了两种优化方法。关键词:分布式计算;GIS;最短路径;层次拓扑模型中图法分类号:P208最短路径问题已经得到了广泛的应用,但是针对的数据都位于同一地点,而由于数据的归属和目前GIS互操作的发展,拓扑数据一般都分布在不同的地方,并且由不同的服务提供商提供最短路径服务进行维护,传统的最短路径研究并没有考虑这种情况。本文研究如何将散布在不同地点上的最短路径服务组合起来,形成一种全局拓扑意义上的更为强大、范围更广的最短路径服务。单机最短路径问题在国内外都已经有了很多研究,大体可以分为基于平面图和基于层次图的最短路径算
3、法。E.W.Dijkstra在1959年提出的Dijkstra算法是平面图算法中最为经典的,且已被广泛使用。文献[1]提出了一种层次图模型HiTi模型。这些算法能有效地加快大型网络最短路径查询时间,但是其数据全部位于本地,没有考虑分布式最短路径查询。针对本文提出的最短路径问题,国内外的研究还很少,文献[2]虽然提出了该问题,并对解决方法进行了简单的叙述,但是没有给出具体的算法和详细分析。文献[3,4]研究的分布式多级道路网还是位于同一空间数据库中,分布式仅仅是指提供服务以供远程用户调用。本文将首先给出分布式环境下的层次网络模型相关定义
4、,由该定义引出分布式虚拟层次图创建算法,然后给出针对该算法的优化方法,最后给出原型系统运行图和最终查询时间表,并进行相关评价和分析。1分布式环境下的层次网络模型定义传统层次网络模型的建立是按一定的规则将一个大型网络划分为若干子网络,而分布式层次路由与此不同的是已知若干小型网络组织成一个具有层次关系的网络(每个局部拓扑网络自然形成层次网络中的子网,而不需要另行划分),主要思想是分布式子网通过边界上的同名点来进行衔接,这些子网中的衔接点,本文称为外接点。同名点确定准则是通过拓扑网络上的属性和空间信息,可以人工和自动判断。自动判断是通过两个
5、点的空间距离,如果小于阈值则认为是同一点;人工判断是在自动判断的基础上加上属性信息的判断。每个子网都拥有若干外接点,如果将这些外接点提取出来,按照一定的规则进行组织,就可以形成一个跨越全部子网、位于其上的高层网络,从而形成分布式环境下的层次网络模型,分布式最短路径算法将以此模型为基础来实现。定义1(图定义)G=(N,L,W)是双向图,N(G)=N={Ni
6、1≤i≤n}是该图的节点集合,n代表了节点数。L(G)是边集合,Lij代表了节点对。W(G)={Wij
7、Wij=f(Lij)}为边的权重,Wij表示边,Lij代表了边的
8、权值,f是代价函数。Sij(G)代表了起点是Ni、终点是Nj的最短路径上的节点集合。SWij(G)代表了最短路径值。收稿日期:2009205220。项目来源:国家973计划资助项目(2006CB701305)。定义2(外接点、关系定义)设图集合SG=3优化方法{G1,G2,,Gm},Gn是双向加权图。Rij(SG)={〈Nq,Nw〉
9、Nq∈Ni∧Nw∈Nj∧distance(Nq,Nw)=0}代表了所有从Gi到Gj的关系集合;Ωij(SG)={Nq
10、Nq∈N(Rij)∧Nq∈Ni}代表了所有与Gi和Gj相关的外接点集合;Ωq(SG)=
11、3.1分布式虚拟边管理策略在分布式层次最短路径算法的组网步骤中需要得到虚拟边的权值,也就是说需要从子网服务中得到外接点之间的最短距离。对于这个题,可以采用3种方法,分别为静态管理法、完动态管理法和半动态管理法。静态管理法是最直观的方法,通过得到全子图的外节点和外节点之间的最短路径来预先成全局衔接图,并存储到一个全局库中。这种法的优点在于其执行效率很高,因为虚拟层次{Ωq1∨Ωq2∨Ωqi∨Ωqm,q≠i}代表了SG中所有的外接点集合;Ψq(SG)={L(Rq1)∨L(Rq)∨L(Rq)∨L(Rq),i≠q,1≤i≤m}代2im表了SG
12、中所有的关系集合。定义3(虚拟层次图定义)SG={G1,G2Gm},LG={N,L,W}是SG的虚拟层次图,N(LG)={Ω1∨Ω2∨∨Ωm}是LG的节点,L(LG)={
13、(Ni∈Ωq(SG)and不需要进
