ACTA AERONAUTICAET ASTRONAUTICA SINICA >
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)
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.
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 . DOI: 10.7527/S1000-6893.2015.0071
[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