Abstract Interplanetary communication networks comprise orbiters, deep-space relays, and stations on planetary surfaces. These networks must overcome node mobility, constrained resources, and significant propagation delays. Opportunities for wireless contact rely on calculating transmit and receive opportunities, but the Euclidean-distance diameter of these networks (measured in light-seconds and light-minutes) precludes node discovery and contact negotiation. Propagation delay may be larger than the line-of-sight contact between nodes. For example, Mars and Earth orbiters may be separated by up to 20.8min of signal propagation time. Such spacecraft may never share line-of-sight, but may uni-directionally communicate if one orbiter knows the other's future position. The Contact Graph Routing (CGR) approach is a family of algorithms presented to solve the messaging problem of interplanetary communications. These algorithms exploit networks where nodes exhibit deterministic mobility. For CGR, mobility and bandwidth information is pre-configured throughout the network allowing nodes to construct transmit opportunities. Once constructed, routing algorithms operate on this contact graph to build an efficient path through the network. The interpretation of the contact graph, and the construction of a bounded approximate path, is critically important for adoption in operational systems. Brute force approaches, while effective in small networks, are computationally expensive and will not scale. Methods of inferring cycles or other librations within the graph are difficult to detect and will guide the practical implementation of any routing algorithm. This paper presents a mathematical analysis of a multi-destination contact graph algorithm (MD-CGR), demonstrates that it is NP-complete, and proposes realistic constraints that make the problem solvable in polynomial time, as is the case with the originally proposed CGR algorithm. An analysis of path construction to complement hop-by-hop forwarding is presented as the CGR-EB algorithm. Future work is proposed to handle the presence of dynamic changes to the network, as produced by congestion, link disruption, and errors in the contact graph. We conclude that pre-computation, and thus CGR style algorithms, is the only efficient method of routing in a multi-node, multi-path interplanetary network and that algorithmic analysis is the key to its implementation in operational systems.
Highlights ► We provide a complexity analysis of graph based routing in interplanetary. ► We extend graph-based routing to include a hybrid source-path algorithm. ► We demonstrate the benefits of path encoding with system-level cost functions. ► Pre-configured, graph-based routing enables high delay interplanetary networks.
Analysis of the contact graph routing algorithm: Bounding interplanetary paths
Acta Astronautica ; 75 ; 108-119
2012-02-03
12 pages
Article (Journal)
Electronic Resource
English
Analysis of the contact graph routing algorithm: Bounding interplanetary paths
Online Contents | 2012
|Online Contents | 2011
Enhanced Contact Graph Routing (ECGR) MACHETE Simulation Model
Online Contents | 2013