中国空间科学技术

›› 2012, Vol. 32 ›› Issue (5): 76-83.doi: 10.3780/j.issn.1000-758X.2012.05.012

• 技术交流 • 上一篇    

基于演化图的导航星座星间路由算法

 王彦, 刘波, 虞万荣, 赵宝康   

  1. （国防科学技术大学计算机学院，长沙410073）
  • 收稿日期:2011-07-26 修回日期:2012-01-16 出版日期:2012-10-25 发布日期:2012-10-25
  • 作者简介:王彦 1989年生，2009年毕业于西安交通大学计算机科学与技术专业，现为国防科学技术大学计算机科学与技术专业博士研究生。研究方向为计算机网络、无线通信及纠错码。
  • 基金资助:

    国家自然科学基金（61103182），国家863计划（2010AA7010203）资助项目

RoutingAlgorithmforNavigationConstellationBasedonEvolvingGraphModel

WANG  Yan, LIU  Bo, YU  Wan-Rong, ZHAO  Bao-Kang   

  1. (CollegeofComputer,NationalUniversityofDefenseTechnology,Changsha410073)
  • Received:2011-07-26 Revised:2012-01-16 Published:2012-10-25 Online:2012-10-25

PDF (PC)

1676

被引次数

14

摘要： 针对装配指向性天线、具有确定性链路调度的导航星座，对星座网络拓扑处于非连通条件下的星间路由问题进行研究。首先，基于演化图理论对星座的动态网络拓扑结构进行建模分析，给出相应的数据结构描述。然后，提出计算最早到达路径的路由算法，给出了路由算法的具体步骤，并分析了算法的复杂性。最后，在算法模拟中，给出了最早到达路径的平均时间开销和跳数开销，并讨论了路径起始时刻对最早到达路径的影响。

关键词: 星间链路, 拓扑连通性, 演化图, 路由算法, 导航星座

Abstract: Fornavigationconstellationequippedwithdirectionalantennaswhichperformsdeterministiclinkscheduling,inter-satelliteroutingprobleminnotfully-connectedconstellationwasstudied.Firstly,thedynamictopologyofnavigationconstellationwasmodeledbasedontheevolvinggraphtheory,andthecorrespondingdatastructurewasgivenlater.Secondly,aroutingalgorithmtocomputetheearliestjourneywasproposed,thenthestepsandthecomplexityofthealgorithmwerediscussed.Finally,theaveragetimecostandaveragehopsofearliestjourneywereshownbysimulationundergivenparameters.Theimpactof startingtimeonearliestjourneywasalsodiscussed.

Key words: Inter-satellitelink, Topologicalconnectivity, Evolvinggraph, Routingalgorithm, Navigationconstellation