Low Earth Orbit Satellite Network Topology Design

This Python package was created by Millicent Riordan for their third-year project Designing High-Performance Inter-Satellite Link Topologies for Satellite Megaconstellations at Durham University.

Set-Up

System

1. Python version 3.11+
2. To ensure full operation, recommended operating systems include recent versions of Linux (e.g. Ubuntu 18+, similar to the Hypatia simulation software) or macOS 14+ (Sonoma onwards).

Python Dependencies

Dependencies for this package include the Python libraries: astropy certifi configobj ephem geopandas matplotlib networkx numpy plotly pytest scipy sgp4 skyfield, and sphinx.

To install all dependencies automatically, run bash install_dependencies.sh.

Please note that you may have to brew install proj to ensure pip install geopandas is successful.

Modules and Functionality

This package involves numerous functions that are grouped as follows:

• analysis - this module provides function that allow the user to evaluate (and record results of such evaluation) topologies according to various metrics. Furthermore, the topologies analysed can be built with various methods, such as various DCMST construction methods. This module also provides a visualisation function that allows user to view their topology and simulate satellites moving around the Earth.
• cost_function_optimisation_algorithms - this module provides different methods for optimising the cost function weights of the novel algorithm proposed in the final paper. These methods include a randomised search, evolutionary strategy search, and a machine learning-based search.
• data_handling - this module provides basic data handling functions (i.e. methods to read satellite description data, save the topologies generated by functions in satellite_topology_construction_algorithms, and save the results of optimisation functions).
• dcmst_construction_algorithms - this module provides functions for constructing degree-constrained minimum spanning trees (see report for full description).
• metrics - this module provides functions that will calculate various metrics given a graph-representation of a satellite network, such as the average hop count, propagation delay, and link churn.
• satellite_network_attribute_functions - this module allows a user to determine various network attributes, such as the visibility between pairs of satellites, the cost function used by the novel algorithm, and whether satellites are more vulnerable to solar flares.
• satellite_topology_construction_algorithms - this module provides various functions for constructing topologies of given satellite networks. As well as the novel algorithm proposed in the report, +Grid and MDTD topology construction algorithms are provided
• tests - this module provides unit and integration tests for all the modules listed above. Works well with pytest.

More information about the purpose of each function is provided in the documentation of this project, as well as the line by line comments within each function. Each module has been formatted according to PEP-8 standards.

Tutorial and Documentation

Documentation of each function within this Python package can be found here. Should Sphinx documentation need to be "re-generated", please consult this link.

To build topologies for other networks, the package is run python __main__py (when situated in the project directory) with the following arguments:

1. tles_file_name - the name of the file containing a two-line element set (TLE) description of each satellite within the given mega-constellation.
2. constellation - the name of the satellite mega-constellation, e.g. Starlink-550.
3. m - the number of orbits in the mega-constellation (specify m for each shell if more than 1).
4. n - the number of satellites per orbit in the mega-constellation (specify n for each shell if more than 1).
5. i - the inclination degree of orbits (specify i for each shell if more than 1).
6. rev - the mean motion revolutions per day for a satellite within the constellation ((specify rev for each shell if more than 1)).
7. multi - Boolean indicating whether there are multiple shells within the constellation (i.e. if satellites within the same mega-constellation orbit at different altitudes). The +Grid algorithm will produce unexpected results if multi set to True
8. optimise - Boolean indicating whether experiments should be conducted optimising the cost function (used to weight potential ISL connections). Only utilised with novel topology construction algorithm.
9. topology - the name of the algorithm that should be used to construct a topology. Options are plus-grid (+Grid - standard mesh topology and, currently, the only topology design deployed in real-world mega-constellations), x-grid, mdtd (Minimum Delay Topology Design), and novel (algorithm designed and proposed in this paper).
10. isl_terminals - list (heterogeneous hardware) or integer (homogeneous hardware) indicating the number of ISL terminals per satellite within the mega-constellation.
11. snapshot_interval - the number of seconds between each snapshot of the satellite mega-constellation for which a topology is built.
12. dcmst - if the novel algorithm is utilised to construct a topology, this argument indicates the Degree-Constrained Minimum Spanning Tree algorithm with which to construct a DCMST - options include primal, aco (Ant Colony Optimisation), and ga (Genetic Algorithm).
13. optimisation_method - if the novel algorithm is utilised to construct a topology and the user wishes to optimise the cost function (i.e. optimise is True), the user can specify random (random parameter sets) or evolutionary (evolutionary search) as the optimisation method.
14. weights - if the novel algorithm is utilised to construct the topology, but does not require cost function coefficient optimisation, cost function coefficients (for alpha, beta, and gamma) must be provided (all coefficients must be in [0,1]).

Example:

python __main__.py --tles starlink-constellation_tles.txt.tmp --constellation Starlink-550 --m 72 --n 22 --i 53 --rev 15.9 --multi False --optimise True --topology novel --isl_terminals 4 --snapshot_interval 60 --dcmst aco --optimisation_method random

To visualise resulting topologies, use the command python analysis/visualisation.py (make sure to pass the correct constellations to the visualise() function) - see here for more information on using the visualise function.

Arguments must be passed to python analysis/visualisation.py:

1. tles - the name of the file containing a two-line element set (TLE) description of each satellite within the given mega-constellation.
2. location - the location of the files containing the topology representations.
3. constellation_name - the name of the satellite mega-constellation, e.g. Starlink-550.
4. snapshot_interval - the number of seconds between each snapshot of the satellite mega-constellation for which a topology is built.
5. method - the name of the algorithm used construct a topology. Options include plus_grid, mdtd, and novel.
6. topology-type - indicates whether ISLs change over time (i.e. if ISLs disconnect, connect, or reconnect over the course of one orbit). Options include: static (they don't) and dynamic (they do).
7. num_snapshots - the number of constellation snapshots (over one orbital period) for which a topology was built.

Example:

python analysis/visualisation.py --tles kuiper-constellation_tles.txt.tmp --location ./Results/plus_grid/kuiper-630 --constellation_name Kuiper-630 --snapshot_interval 60 --method plus_grid --topology-type static --num_snapshots 97

A "toy example" is provided - the Iridium constellation has relatively few satellites (66 across 6 orbits) when compared with megaconstellations, such as Kuiper, Lightspeed (Telesat) and Starlink. To create topologies for Iridium and visualise them, run bash visualise.sh.

Please see report for full citations/references of papers that algorithms are sourced from.

Recreating Report

To recreate the results in the project's final report, please cd project and run bash report.sh. Please note that this script takes significant execution time. However, a large proportion of this code is automatically parallelised - if you have access to a significant number of CPU cores, this code will run significantly faster over several days. To generate an overview of the results of report.sh, run results.sh to build a csv file. To build the visualisations of the networks (demonstrating the physical nature of the network over time), please run bash visualise.sh to build and display all topologies.

A series of results is provided in project/Results (including benchmarks) with the best results for each algorithm variation (with regard to combinations of DCMST construction algorithm, cost function optimisation method, and constellations) presented in results_overview.csv(generated by command python analysis/build_results_table.py.

Acknowledgements

Please note that certain functions within this code (within the data_handling functions and the plus_grid function) are taken and/or adapted from Hypatia software code. All code not written by this author is clearly cited/referenced with the appropriate licenses displayed in the relevant files. Otherwise, all code has been created, tested, and documented by this author.

© Millicent Riordan