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

《基于演化图的导航星座星间路由算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、76中国空间科学技术ChineseSpaceScienceandTechnology2012年10月第5期基于演化图的导航星座星问路由算法王彦刘波虞万荣赵宝康(国防科学技术大学计算机学院，长沙410073)摘要针对装配指向性天线、具有确定性链路调度的导航星座，对星座网络拓扑处于j}连通条件下的星间路由问题进行研究。首先，基于演化图理论对星座的动态网络拓扑结构进行建模分析，给出相应的数据结构描述。然后，提出计算最早到达路径的路由算法，给出了路由算法的具体步骤，并分析了算法的复杂性。最后，在算法模拟中，给出了最早到达路径的平均时间开销和跳数开销，并讨论了路径起始时刻对最早到达路径的影响。关键词星

2、间链路拓扑连通性演化图路由算法导航星座DOI：10．3780／j．issn．1000一758X．2012．05．D121引言近年来，全球卫星导航系统在国民经济和国防军事等领域的应用日益广泛和深入，推动着其技术的不断进步和功能的持续完善。美国的GPS率先实现了星间链路，并且计划在GPSIII中装配指向性天线，并引入路由转发机制，以提升星间链路数据通信性能[1]。总结国外卫星导航系统的发展经验，在星座内建立星间链路，并利用星间链路进行星间测距和数据通信，以实现星座的自主运行是一种发展趋势[2]。本文针对导航星座星问数据通信的需求，对导航星座星问路由相关问题展开研究。针对基于星间链路的卫星星座系统

3、星问路由问题，国内外众多学者已进行了大量的研究工作，但大多数工作都是针对用于承载地面用户数据流量的卫星通信系统的星问路由问题，鲜有学者针对导航星座进行星问路由研究。文献[3]提出了一种基于地面站集中式的导航星座星问路由算法，其假设条件是：星座系统的星间链路资源丰富，一颗卫星可在同一时刻与其他多颗卫星建立星间链路，确保星座网络拓扑在任意时刻处于全连通状态。但在星间链路资源受限的情况下，一颗导航卫星无法同时建立并维持多条星间链路，将持续进行星间链路切换并导致星座网络拓扑处于非连通状态，上述方法将难以有效地解决星问路由问题。为降低导航星座星间数据通信对地面站的依赖，星上在线计算的路由算法是未来发展

4、的必然趋势。本文针对装配指向性天线、具有确定性链路调度的卫星导航星座系统，充分分析了由卫星在轨飞行及星间链路调度切换所导致的星座动态变化的网络拓扑结构，引入演化图模型[4]，对星座动态变化的网络拓扑结构进行建模，提出一种星间最早到达路径的路由算法，再给定导航星座构型及星间链路调度方案，对算法进行模拟验证。国家自然科学基金(61103182)，国家863计划(2010AA7010203)资助项目收稿日期：2011一07—26。收修改稿日期：2012一01—162012年10月中国空间科学技术2导航星座动态网络拓扑结构的演化图建模2．1场景描述图1给出了6个连续时间间隔的导航星座网络拓扑结构快照

5、，每个时间间隔长度固定为出。为简化描述，图1中只给出了导航星座中的一部分导航卫星及这些导航卫星之间建有的星问链路。如图1所示，将导航卫星分别记为A、B、C、D、E、F和G；以A与C之间的星间链路为例，将导航卫星间的星间链路记为ISL(A，C)。在每个时间间隔内，导航星座中的每颗卫星或选择与另一颗特定的卫星建立一条全双工的星间链路，或处于空闲状态；但不能同时与多颗卫星建立星间链路，故在每个时间间隔内导航星座网络拓扑都处于非连通状态[5]。由于导航星座具有确定性的星间链路调度，星座中的每颗导航星都可获得当前时间间隔内和后续一定时间间隔内整个导航星座网络拓扑信息。观察图1，在从o～6△￡的每个时间

6、间隔内，导航星座的网络拓扑结构都是固定不变的，但都处于非连通状态；且在任意一个时间间隔内，A与G之间都未建立星间链路。由于在同一时刻，每颗卫星至多只能建立一条星间链路，故不可能在导航星座网络拓扑结构不发生变化的一个时间间隔内找到一条从A至G的路径。然而，可通过导航星座网络拓扑结构随着每个时间间隔的变化，在时域空间中找到从A至G的路径。例如，在o～出内，从A出发到达C，在2△￡～3△￡内，再从C出发就可到达G。吐出二黉：’太i、茶船2出二：鞴、：jk＼、二，，≥‘赣jB，

7、、菸’卜i◇、擎工A弋：惑一，、、懿+——◆。、翰、：A警、lbo。。。．卜镰＼。cE。遥瑚／／＼＼，、o、占簧：：?占鬻

8、：、?D、黔’G黔3州出i瓠BF，誊幂。赣?。f5船6出≮醚L～F，．勘、二懿≮瓤j，恚。。／黟、。0cE1L_篾≮峻A、爱窨、、黔。-、～斌D、黢，卜—一懿G黟。冀：j≯。j≯≥G黔?图1不同时间间隔内导航星座网络拓扑结构快照Fig．1Snapshotstakenatdifferenttimeintervalsofthenetworktop0109yofnavigationconstellation2．2导