Walker星座中一种新的最短路径路由算法  

New Shortest Path Routing Algorithm for Walker Constellation

作　　者：王莹[1] 胡修林[1] 胡伟圣[1] 曾喻江[1] 

机构地区：[1]华中科技大学电子与信息工程系,湖北武汉430074

出　　处：《小型微型计算机系统》2008年第6期1047-1050,共4页Journal of Chinese Computer Systems

基　　金：武器装备部预研基金项目(51421010705jw0523)资助

摘　　要：利用卫星运行的规律性和星际链路连接的规则性,提出了Walker星座中的缩水最短路径路由算法.算法根据最少跳数下最短路径的路由选择原则,将路由选择分为方向估计与方向选择两个阶段,方向估计阶段给出使得路径跳数最少的节点的两种选择方向,方向选择阶段基于方向估计的成果划定路径搜索的节点空间,最终得到使得路径距离最短的第一选择方向.通过分析与仿真,在算法的运算量与有效性方面将缩水最短路径路由算法与Dijkstra算法进行比较,结果显示,在有效性几乎一致的情况下,缩水最短路径路由算法减小了搜索空间,从而使算法的运算量有了大幅下降.This paper presents a shrinking shortest path routing algorithm（SSPRA）, making use of the characteristics of satellites＇ regular movement and regular array of Inter Satellite Links（ISL）. SSPRA divides routing choice into two phrases： direction estimation phrase and direction decision phrase,according to the principle of shortest path under least hops. In the first phrase, two possible forwarding directions are given because their path hops are least, while in the second phrase the nodes paths possibly pass through are partitioned based on the results of the first phrase. Preferential forwarding direction is decided by searching the possible nodes. SSPRA was compared with Dijkstra algorithm at computation amount and efficiency through simulation. The result is that computation amount of SSPRA is greatly less than that of Dijkstra algorithm because SSPRA reduces search range, at the same time efficiency of two algorithms is almostly uniform.

关 键 词：卫星网络 路由 最短路径 有效性 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]