导航星座网络路由算法研究

南京大学学报(自然科学版) ›› 2018, Vol. 54 ›› Issue (3): 529–537.

导航星座网络路由算法研究

李子璇，严志博，赵康僆 *，李文峰

发布日期:2018-05-23
作者简介:南京大学电子科学与工程学院，南京，210093
基金资助:
国家自然科学基金(61401194)，中央高校基本科研专项资金(021014380064)，江苏高校优势学科建设工程

Performance evaluation of routing algorithms in navigation constellation networks

Li Zixuan, Yan Zhibo, Zhao Kanglian*, Li Wenfeng

Published:2018-05-23
About author:School of electronic science and engineering, Nanjing University, Nanjing, 210093, China

摘要/Abstract

摘要： 导航星座网络具有拓扑动态变化，物理链路间断可用，时延较长，信道误码率较大，以及星间链路资源与星上处理资源有限等特点。在导航星座网络中，实际传输的数据流量种类多样，且往往分布不均。其链路调度一般都是事先规划好的，具有可预测性和周期性，相较一般的卫星通信网络，具有更强的规律性。如何应对导航星座网络中的各种问题并利用导航星座网络的独特特性，实现数据的高效传输，选用合适的路由算法十分关键。目前，针对卫星网络的路由算法多数基于通信卫星星座来开展研究，针对带有指向性天线分时隙通信的导航星座网络的算法不太多，本文对已提出的几种具有代表性的空间路由算法进行分析，并选取最短时延下最少跳数路由和连接图路由进行重点研究，通过OPNET对路由机制的性能进行仿真评估，得出有关导航星座网络中路由算法的适用性准则，为导航星座网络中路由算法的设计和选用提供参考。

关键词: 导航星座网络, 路由算法, OPNET, 端到端时延, 路由计算次数

Abstract: Constellation network of Global Navigation Satellite System (GNSS) is characterized by particular features, such as dynamic topology, intermittent usability of physical link, long propagation delay, high bit error rate of channel, limited onboard processing capabilities, and restricted inter-satellite link resources. In navigation constellation network, different types of traffic are required to be transferred according to a variety of demands. The traffic distribution tends to imbalance under practical circumstances. Beyond that, Navigation constellation network topology has strong predictability and periodicity, on account of its strict and deterministic inter-satellite link scheduling. Compared to conventional satellite communication networks, it presents more distinct regularity. To make the best use of limited resources and attain the overall efficient transmission of data, it is critical to deploy an appropriate routing algorithm, dealing with all these challenges and exploiting characteristics particularly possessed by GNSS. So far, magnitude routing algorithms have been issued, mainly focused on satellite communication networks, while not many are particularly aimed at GNSS with time slot allocation of crosslinks equipped with directional antennas. Therefore，this paper targets at above-mentioned navigation constellation network with specific topological features and takes an analysis of several relevant and typical routing algorithms. Then route of minimum number of hops of the least delay and contact graph routing (CGR) are selected to be further studied, of which the performances are evaluated in different scenarios built by network simulation software OPNET. End-to-end delay and routing calculations are chosen to be the two standards for assessment. Finally, some criterions about the applicability of routing algorithms in navigation constellation network are drawn, which can be good references to the adoption or development of the efficient routing algorithms in GNSS.

李子璇, 严志博, 赵康僆, 李文峰. 导航星座网络路由算法研究[J]. 南京大学学报(自然科学版), 2018, 54(3): 529–537.

Li Zixuan, Yan Zhibo, Zhao Kanglian, Li Wenfeng. Performance evaluation of routing algorithms in navigation constellation networks[J]. Journal of Nanjing University(Natural Sciences), 2018, 54(3): 529–537.

参考文献

[1] Maine K P, Anderson P, Langer J. Crosslinks for the next-generation GPS. In: Proceedings of 2003 IEEE Aerospace Conference. Big Sky, MT, USA: IEEE, 2003, 4: 1589-1596. [2] Xu Y, Chang Q, Yu Z J. On new measurement and communication techniques of GNSS inter-satellite links. Science China Technological Sciences, 2012, 55(1): 285-294. [3] 王彦, 刘波, 虞万荣等. 基于演化图的导航星座星间路由算法. 中国空间科学技术, 2012, 32(5): 76-83. (Wang Y, Liu B, Yu W R, et al. Routing algorithm for navigation constellation based on evolving graph model. Chinese Space Science and Technology, 2012, 32(5): 76-83) [4] Wu Y L, Yang J, Chen J Y, et al. Route analysis of satellite constellation based on directional crosslink with narrow-beam antenna. In: Wang Y L, Li T R. Practical Applications of Intelligent Systems. Springer Berlin Heidelberg, 2012: 639-650. [5] 燕洪成, 张庆君, 孙勇. 基于连接图路由算法的导航星座网络路由性能研究. 见: 第五届中国卫星导航学术年会论文集-S8卫星导航模型与方法. 南京, 中国: 中国卫星导航学术年会组委会, 2014. (Yan H C, Zhang Q J, Sun Y. Routing performance evaluation in navigation constellation network based on contact graph routing. In: Proceedings of the 5th China Satellite Navigation Conference Proceedings-S8 Satellite Navigation Modeling and Method. Nanjing, China: Organizing Committee of China Satellite Navigation Academic Conference, 2014.) [6] Bui-Xuan B M, Ferreira A, Jarry A. Evolving graphs and least cost journeys in dynamic network. In: WiOpt’03: Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks. Sophia Antipolis, France: CCSD, 2003. [7] 张之学, 薛峰, 赵金贤等. 基于演化图理论的导航卫星星座动态路由准则及算法. 第七届中国卫星导航学术年会论文集—S07卫星导航增强技术. 长沙, 中国: 中国卫星导航学术年会组委会, 2016: 6. (Zhang Z X, Xue F, Zhao J X, et al. Dynamic routing metrics and algorithms for navigation satellite constellation based on evolving graphic theory. In: Proceedings of the 7th China Satellite Navigation Conference Proceedings-S07 Satellite Navigation Enhancement Technology. Changsha, China: Organizing Committee of China Satellite Navigation Academic Conference, 2016: 6.) [8] Dijkstra E W. A note on two problems in connexion with graphs. Numerische Mathematik, 1959, 1(1): 269-271. [9] Burleigh S. Contact graph routing, IRTF, Internet-Draft draft-burleigh-dtnrg-cgr-00, https://tools.ietf.org/html/draft-burleigh-dtnrg-cgr-00, 2009. [10] Seguí J, Jennings E, Burleigh S. Enhancing contact graph routing for delay tolerant space networking. In: 2011 IEEE Global Telecommunications Conference (GLOBECOM 2011). Kathmandu, Nepal: IEEE, 2011: 1-6. [11] Birrane E, Burleigh S, Kasch N. Analysis of the contact graph routing algorithm: Bounding interplanetary paths. Acta Astronautica, 2012, 75: 108-119. [12] Fraire J A, Madoery P, Finochietto J M. Leveraging routing performance and congestion avoidance in predictable delay tolerant networks. In: 2014 IEEE International Conference on Wireless for Space and Extreme Environments (WiSEE). Noordwijk, Netherlands: IEEE, 2014: 1-7. [13] Bezirgiannidis N, Caini C, Montenero D D P, et al. Contact graph routing enhancements for delay tolerant space communications. In: 7th Advanced Satellite Multimedia Systems Conference and the 13th Signal Processing for Space Communications Workshop (ASMS/SPSC). Livorno, Italy: IEEE, 2014: 17-23. [14] Silva A P, Burleigh S, Hirata C M, et al. A survey on congestion control for delay and disruption tolerant networks. Ad Hoc Networks, 2015, 25: 480-494. [15] Fraire J A, Madoery P, Finochietto J M, et al. Congestion modeling and management techniques for predictable disruption tolerant networks. In: 40th Conference on Local Computer Networks (LCN). Clearwater Beach, FL, USA: IEEE, 2015: 544-551. [16] Yan H C, Zhang Q J, Sun Y. Local information-based congestion control scheme for space delay/disruption tolerant networks. Wireless Networks, 2015, 21(6): 2087-2099. [17] Birrane E J. Congestion modeling in graph-routed delay tolerant networks with predictive capacity consumption. In: 2013 IEEE Global Communications Conference (GLOBECOM). Atlanta, GA, USA: IEEE, 2013: 3016-3022. [18] Fraire J A, Madoery P, Burleigh S, et al. Assessing contact graph routing performance and reliability in distributed satellite constellations. Journal of Computer Networks and Communications, 2017, 2017: 2830542.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed