中文摘要：

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

英文摘要：

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.