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

doi:10.7527/S1000-6893.2015.0071

Abstract

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

CLC Number:

V44
TP393

YAN Hongcheng, ZHANG Qingjun, SUN Yong. Link assignment problem of navigation satellite networks with limited number of inter-satellite links[J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2015, 36(7): 2329-2339.

References

[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.

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

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	Qian YANG, Haoran ZHENG, Xianda CHENG, Wei DONG. Optimization design method for hot air anti⁃icing system based on bleed air control [J]. Acta Aeronautica et Astronautica Sinica, 2023, 44(S2): 729285-729285.
[2]	Jiezhong DONG, Wuli CHU, Haoguang ZHANG, Bo LUO, Song YAN. Flow control mechanism of diffuser cascade with wavy leading⁃edge based on causal network analysis [J]. Acta Aeronautica et Astronautica Sinica, 2023, 44(19): 128336-128336.
[3]	Yougang XIAO, Xiangna MAN, Guohua WU, Qizhang LUO. Surveying and mapping path planning method for UAV-borne SAR considering terains [J]. Acta Aeronautica et Astronautica Sinica, 2023, 44(17): 328143-328143.
[4]	Bing WANG, Runyuan ZOU, Zhening CHANG. Aircraft takeoff mass estimation method based on improved simulated annealing algorithm [J]. Acta Aeronautica et Astronautica Sinica, 2023, 44(16): 328090-328090.
[5]	Guohua WU, Tianyu WANG. Large-scale constellation TT&C resource scheduling algorithm based on adaptive simulated annealing [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2023, 44(12): 327759-327759.
[6]	Chao LIANG, Li YANG, Chengsheng PAN, Yaowen QI. Multi-QoS constraints routing algorithm based on satellite network dynamic resource graph [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2023, 44(1): 326422-326422.
[7]	ZOU Ziyuan, CHEN Qifeng. Decision tree-based target assignment for confrontation of multiple space vehicles [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(S1): 726910-726910.
[8]	HAN Kai, DONG Richang, SHAO Fengwei, GONG Wenbin, CHANG Jiachao. Dynamic topology optimization of navigation satellite inter-satellite links network based on improved genetic algorithm [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(9): 326095-326095.
[9]	SUN Gang, PENG Shuang, CHEN Hao, WU Jiangjiang, LI Jun. Multi-objective optimization method oriented to integrated scenario of TT & C resources and data transmission resources [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(9): 326114-326114.
[10]	ZHENG Shuai, WANG Zihan, ZHAO Haoran, YANG Pengtao, HONG Jun. Layout optimization method of aircraft fuel gauging sensor based on differential evolution algorithm [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(8): 125809-125809.
[11]	JING Tao, TIAN Xitian. Multi-objective optimization method for aircraft tolerance allocation based on Monte Carlo-adaptive differential evolution algorithm [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(3): 425278-425278.
[12]	LUO Qing, ZHANG Tao, SHAN Peng, ZHANG Wentao, LIU Zihao. Generating reconfiguration blueprints for IMA systems based on improved Q-learning [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(8): 525792-525792.
[13]	ZHANG Junfeng, YOU Lubao, YANG Chunwei, HU Rong. Arrival sequencing and scheduling based on multi-objective Imperialist competitive algorithm [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(6): 324439-324439.
[14]	SUN Gang, CHEN Hao, PENG Shuang, DU Chun, LI Jun. Multi-objective optimization algorithm for satellite range scheduling based on preference MOEA [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(4): 524475-524475.
[15]	HE Cheng, MA Dongli, JIA Yuhong, YANG Muqing, CHEN Gang. Multi-objective optimization design for joined-wing SensorCraft [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(12): 224761-224761.