航空学报 > 2015, Vol. 36 Issue (7): 2329-2339   doi: 10.7527/S1000-6893.2015.0071

星间链路数量受限的导航卫星网络链路分配问题

燕洪成, 张庆君, 孙勇   

  1. 中国空间技术研究院 总体部, 北京 100094
  • 收稿日期:2014-08-22 修回日期:2015-03-11 出版日期:2015-07-15 发布日期:2015-03-13
  • 通讯作者: 燕洪成 男, 博士研究生。主要研究方向: 空间信息网络拓扑优化与路由算法。 Tel: 010-68113006 E-mail: yanhc519@163.com E-mail:yanhc519@163.com
  • 作者简介:张庆君 男, 博士, 研究员, 博士生导师。主要研究方向: 航天器总体设计。 E-mail: ztzhangqj@163.com;孙勇 男, 硕士, 研究员。主要研究方向: 航天器总体设计。 E-mail: syex7501@sohu.com
  • 基金资助:

    国家自然科学基金 (91438102)

Link assignment problem of navigation satellite networks with limited number of inter-satellite links

YAN Hongcheng, ZHANG Qingjun, SUN Yong   

  1. Institute of Spacecraft System Engineering, China Academy of Space Technology, Beijing 100094, China
  • Received:2014-08-22 Revised:2015-03-11 Online:2015-07-15 Published:2015-03-13
  • Supported by:

    National Natural Science Foundation of China (91438102)

摘要:

对星间链路数量非常有限、需要同时满足星间测距和星间通信需求的导航卫星网络的链路分配问题进行了研究。首先,分析了导航卫星网络的特点,并设计了一种基于有限状态自动机(FSA)的拓扑处理机制。然后,将星间测距需求作为一个约束,以星间通信的延时性能为优化目标,将导航卫星网络的链路分配问题建模为一个多目标优化问题。最后,针对建立的多目标优化问题,分别提出一种基于首次改善(FI)的本地搜索算法和基于模拟退火(SA)的启发式优化算法以对链路分配问题进行求解,并提出一种基于分支交换策略的新链路分配生成方法。仿真结果表明,通过FI算法和SA算法获得的优化链路分配的网络延时性能均得到了改进,且SA算法的性能要优于FI算法;同时,FSA的状态持续时间的减小有利于获得网络延时性能好的链路分配。

关键词: 导航卫星网络, 链路分配, 多目标优化, 首次改善, 模拟退火, 网络延时

Abstract:

The link assignment problem of navigation satellite networks is investigated where the number of inter-satellite links is very limited and both crosslink ranging and crosslink communication requirements have to be accommodated. Firstly, the characteristic of navigation satellite networks is analyzed and a topology handling scheme based on finite state automaton (FSA) is presented. Then, the link assignment problem of navigation satellite network is formulated as a multi-objective optimization problem with the crosslink ranging as a constraint and crosslink communication delay as the optimization object. Finally, a local search algorithm based on first improvement (FI) and a heuristic optimization algorithm based on simulated annealing (SA) are presented respectively to solve the formulated link assignment problem. A new link assignment generation method based on branch and exchange strategy is also proposed. Simulation results show that the network delay performances of the optimized link assignment obtained with FI and SA are better than the initial link assignment. And the performance of SA is better than FI. The probability of obtaining a link assignment with good delay performance is higher when the state duration of FSA is small.

Key words: navigation satellite network, link assignment, multi-objective optimization, first improvement, simulated annealing, network delay

中图分类号: