星间链路数量受限的导航卫星网络链路分配问题
收稿日期: 2014-08-22
修回日期: 2015-03-11
网络出版日期: 2015-03-13
基金资助
国家自然科学基金 (91438102)
Link assignment problem of navigation satellite networks with limited number of inter-satellite links
Received date: 2014-08-22
Revised date: 2015-03-11
Online published: 2015-03-13
Supported by
National Natural Science Foundation of China (91438102)
对星间链路数量非常有限、需要同时满足星间测距和星间通信需求的导航卫星网络的链路分配问题进行了研究。首先,分析了导航卫星网络的特点,并设计了一种基于有限状态自动机(FSA)的拓扑处理机制。然后,将星间测距需求作为一个约束,以星间通信的延时性能为优化目标,将导航卫星网络的链路分配问题建模为一个多目标优化问题。最后,针对建立的多目标优化问题,分别提出一种基于首次改善(FI)的本地搜索算法和基于模拟退火(SA)的启发式优化算法以对链路分配问题进行求解,并提出一种基于分支交换策略的新链路分配生成方法。仿真结果表明,通过FI算法和SA算法获得的优化链路分配的网络延时性能均得到了改进,且SA算法的性能要优于FI算法;同时,FSA的状态持续时间的减小有利于获得网络延时性能好的链路分配。
燕洪成 , 张庆君 , 孙勇 . 星间链路数量受限的导航卫星网络链路分配问题[J]. 航空学报, 2015 , 36(7) : 2329 -2339 . DOI: 10.7527/S1000-6893.2015.0071
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.
[1] Maine K, Anderson P, Bayuk F. Communication architecture for GPS III[C]//Proceedings of 2004 IEEE Aerospace Conference. Piscataway, NJ: IEEE Press, 2004: 1532-1539.
[2] Fernandez F A. Inter-satellite ranging and inter-satellite communication links for enhancing GNSS satellite broadcast navigation data[J]. Advances in Space Research, 2011, 47(5): 786-801.
[3] Lin J M, Yang J, Wang Y K. Optimizing algorithm for the scheduling of GNSS crosslink: a matrix transform approach[C]//Proceedings of the 2nd China Satellite Navigation Conference, 2011: 467-471 (in Chinese). 林金茂, 杨俊, 王跃科. 基于矩阵变换的GNSS星间链路最优规划算法[C]//第二届中国卫星导航年会文集, 2011: 467-471.
[4] Wang H, Chen Z, Zheng J, et al. A new algorithm for onboard autonomous orbit determination of navigation satellites[J]. The Journal of Navigation, 2011, 64(S1): 162-179.
[5] Wang Y, Liu B, Yu W R, et al. Routing algorithm for navigation constellation based on evolving graph model[J]. Chinese Space Science and Technology, 2012(5): 76-83 (in Chinese). 王彦, 刘波, 虞万荣, 等. 基于演化图的导航星座星间路由算法[J]. 中国空间科学技术, 2012(5): 76-83.
[6] Fall K. A delay-tolerant network architecture for challenged internets[C]//Proceedings of the 2003 Conference on Applications, Technologies, Architectures , and Protocols for Computer Communications. New York: ACM, 2003: 27-34.
[7] Lin C, Dong Y W, Shan Z G. Research on space internetworking service based on DTN[J]. Journal of Computer Research and Development, 2014, 51(5): 931-943 (in Chinese). 林闯, 董扬威, 单志广. 基于DTN的空间网络互联服务研究综述[J]. 计算机研究与发展, 2014, 51(5): 931-943.
[8] Harathi K, Krishna P, Newman-wolfe R E, et al. A fast link assignment algorithm for satellite communication networks[C]//Proceedings of Twelfth Annual International Phoenix Conference on Computers and Communications. Piscataway, NJ: IEEE Press, 1993: 401-408.
[9] Noakes M D, Cain J B, Nieto J W, et al. An adaptive link assignment algorithm for dynamically changing topologies[J]. IEEE Transactions on Communications, 1993, 41(5): 694-706.
[10] Hong S C, Byoung W K, Chang-gun L, et al. FSA-based link assignment and routing in low-earth orbit satellite networks[J]. IEEE Transactions on Vehicular Technology, 1998, 47(3): 1037-1048.
[11] Werner M. Topological design, routing and capacity dimensioning for ISL networks in broadband Leo satellite systems[J]. International Journal of Satellite Communications, 2001, 19(6): 499-527.
[12] Fraire J A, Madoery P G, Finochietto J M. On the design and analysis of fair contact plans in predictable delay-tolerant networks[J]. IEEE Sensors Journal, 2014, 14(11): 3874-3882.
[13] Fraire J A, Finochietto J M. Routing-aware fair contact plan design for predictable delay tolerant networks[J]. Ad Hoc Networks, 2015, 25(Part B): 303-313.
[14] Shi L Y, Xiang W, Tang X M. A link assignment algorithm applicable to crosslink ranging and data exchange for satellite navigation system[J]. Journal of Astronautics, 2011, 32(9): 1971-1977 (in Chinese). 石磊玉, 向为, 唐小妹. 一种兼顾卫星导航系统星间观测及通信的链路分配算法[J]. 宇航学报, 2011, 32(9): 1971-1977.
[15] Li Z D, He S B, Liu C H, et al. An topology design method of navigation satellite constellation inter-satellite links[J]. Spacecraft Engineering, 2011, 20(3): 32-37 (in Chinese). 李振东, 何善宝, 刘崇华, 等. 一种导航星座星间链路拓扑设计方法[J]. 航天器工程, 2011, 20(3): 32-37.
[16] Jain S, Fall K, Patra R. Routing in a delay tolerant network[C]//Proceedings of the 2004 Conference on Applications, Technologies, Architectures and Protocols for Computer Communications. New York: ACM, 2004: 145-157.
[17] Cormen T H, Leiserson C E, Rivest R L, et al. Introduction to algorithms[M]. Pan J G, Gu T C, Li C F, et al. translated. 2nd ed. Beijing: China Machine Press, 2006: 366-369, 686-687 (in Chinese). Cormen T H, Leiserson C E, Rivest R L, 等. 算法导论[M]. 潘金贵, 顾铁成, 李成法, 等, 译. 2版. 北京: 机械工业出版社, 2006: 366-369, 686-687.
[18] Pióro M, Medhi D. Routing, flow, and capacity design in communication and computer networks[M]. San Francisco: Morgan Kaufmann Publishers, 2004: 169-170.
[19] Suman B, Kumar P. A survey of simulated annealing as a tool for single and multiobjective optimization[J]. Journal of the Operational Research Society, 2006, 57: 1143-1160.
/
| 〈 |
|
〉 |
CJA