Routing Optimisation for Aeronautical Networks, Coursework Example

Front matter

The democratization of air transport and the continuous increase in the number of flights increase the need for digital ground-on-board communications (Zhang et al., 2022). Indeed, a direct consequence of the increase in air traffic is that the total volume of data generated increases, all the more so as new application needs appear at the same time.

Problem definition

The increase concerns both data link communications and voice communications. The systems used to manage the latter reaching saturation (whether in terms of available frequency or in terms of human processing of this data), the current trend is towards a transfer of certain services to digital media, therefore leading to an increase in the volume of data generated by each aircraft (Eddy et al., 2009). The introduction of pilot data link communications illustrates this transfer of voice communications previously transmitted using analog radios (clearance, for example). According to Zhang et al.,2022, these two factors, an increase in the number of flights and an increase in the volume of data generated per aircraft, contribute to the congestion of existing systems. It is estimated that the current systems will be saturated around 2025.

Methodology

First, we must create a graph representing the possible routing paths between the airplanes and the ground stations (GS). Each airplane will be represented as a node in the graph, and the edge between the two nodes will represent the link between the two airplanes. The weight of the edge will be the transmission rate between the two airplanes, as given in the table in your question.

Next, we can use one of the following algorithms to find the optimal routing path:

We can use Dijkstra’s algorithm for the single-objective optimization problem (maximum end-to-end data transmission rate). This algorithm will find the shortest path (in terms of transmission rate) from the source node (the airplane) to the destination node (the ground station).

For the multiple-objective optimization problem (maximum end-to-end data transmission rate and minimum end-to-end latency), we can use the A* algorithm. This algorithm is a Dijkstra’s algorithm extension that also considers the node delay. The distance between the two nodes can be used as a heuristic function to direct the search in the direction of the ideal path.

import csv

from collections import defaultdict

import heapq

import math

# from google.colab import files

# uploaded = files.upload()

The create_graph function takes a graph, a start node, and an end node as input, and returns the optimal path and the cost of the path (in this case, the transmission rate) between the start and end nodes. It uses a priority queue and the Dijkstra’s algorithm to find the shortest path from the start to the end node. The graph is represented as a dictionary, with the keys being the nodes and the values being a list of tuples containing a neighbor node and the weight of the edge between the two nodes.

# Function to create the graph from the input data

def create_graph(filename):

graph = defaultdict(list)

with open(‘./’ + filename, ‘r’) as csvfile:

reader = csv.reader(csvfile)

next(reader)  # Skip the header row

for row in reader:

flight_no = row[0]

altitude = float(row[2])

lat = float(row[3])

lon = float(row[4])

# Calculate the 3D distance between the airplane and the ground stations

distance_to_LHR = calculate_3D_distance(lat, lon, altitude, 51.4700, 0.4543, 81.73)

distance_to_EWR = calculate_3D_distance(lat, lon, altitude, 40.6895, 74.1745, 8.72)

# Add edges to the graph for both ground stations

add_edge(graph, flight_no, ‘LHR’, distance_to_LHR)

add_edge(graph, flight_no, ‘EWR’, distance_to_EWR)

return graph

# Function to add an edge to the graph

def add_edge(graph, src, dest, weight):

graph[src].append((dest, weight))

The Haversine function takes the latitude, longitude, and altitude of two points as input and returns the 3D distance between them in meters. It first converts the latitudes and longitudes to radians and then uses the Haversine formula to calculate the distance on the surface of a sphere. Finally, it adds the difference in altitude to get the 3D distance.

# Function to calculate the 3D distance between two points

def calculate_3D_distance(lat1, lon1, alt1, lat2, lon2, alt2):

# Convert the latitudes and longitudes to radians

lat1 = math.radians(lat1)

lon1 = math.radians(lon1)

lat2 = math.radians(lat2)

lon2 = math.radians(lon2)

# Calculate the 3D distance using the Haversine formula

a = math.sin((lat2 – lat1) / 2)**2 + math.cos(lat1) * math.cos(lat2) * math.sin((lon2 – lon1) / 2)**2

c = 2 * math.atan2(math.sqrt(a), math.sqrt(1 – a))

distance = 6371 * c  # Earth’s radius in kilometers

# Calculate the altitude difference

altitude_difference = abs(float(alt2) – float(alt1))

# Calculate the 3D distance

distance = math.sqrt(distance**2 + altitude_difference**2)

return distance

The find_optimal_path function builds the optimal path by following the prev values from the end node and then reverses the path to get the correct order. Finally, it returns the path as a list of nodes and the cost of the path (in this case, the transmission rate) as a single value.

def find_optimal_path(graph, start, end):

# Initialize the priority queue with the start node and a distance of 0

queue = [(0, start)]

# Initialize a dictionary to store the distances from the start node to each node

distances = {start: 0}

# Initialize a dictionary to store the previous node in the optimal path for each node

prev = {}

# Initialize a set to store the visited nodes

visited = set()

# Loop until the queue is empty

# print(queue)

while queue:

# Get the node with the smallest distance from the queue

distance, node = heapq.heappop(queue)

# Skip the node if it has already been visited

if node in visited:

continue

# Mark the node as visited

visited.add(node)

# Update the distances and prev values for the neighbors of the node

for neighbor, weight in graph[node]:

if neighbor not in distances or distance + weight < distances[neighbor]:

distances[neighbor] = distance + weight

prev[neighbor] = node

heapq.heappush(queue, (distance + weight, neighbor))

# Build the optimal path by following the prev values from the end node

path = []

current = end

while current != start:

path.append(current)

current = prev[current]

path.append(start)

path.reverse()

return path, distances[end]

Experiments and Discussion

The code below reads the data from the CSV file creates the graph using the create_graph function, and then finds the optimal routing path for each airplane using the find_optimal_path function. It prints the flight number, optimal path, and transmission rate for each airplane.

Note that this code assumes that the end node is always ‘LHR.’ If we want to find the optimal path to ‘EWR’ instead, we can simply change the end node in the call to ‘find_optimal_path.’

# Loop through each item in the CSV data

with open(‘NA_13_Jun_29_2018_UTC13.CSV’, ‘r’) as f:

reader = csv.reader(f)

next(reader)  # Skip the header row

for row in reader:

# Get the flight number, timestamp, altitude, latitude, and longitude

flight_number = row[0]

timestamp = row[1]

altitude = float(row[2])

latitude = float(row[3])

longitude = float(row[4])

# Create the graph

graph = create_graph(‘NA_13_Jun_29_2018_UTC13.CSV’)

# Find the optimal path from the start node to the end node

path, cost = find_optimal_path(graph, flight_number, ‘LHR’)

# Print the results

if cost < 1000:

print(f”Flight number: {flight_number}”)

print(f”Optimal path: {path}”)

print(f”Transmission rate: {cost}”)

print()  # Add a blank line for readability

Flight number: BA179

Optimal path: [‘BA179’, ‘LHR’]

Transmission rate: 116.51386922623958

Flight number: BA225

Optimal path: [‘BA225’, ‘LHR’]

Transmission rate: 103.1817809400002

Flight number: BA239

Optimal path: [‘BA239’, ‘LHR’]

Transmission rate: 104.50400837569065

Flight number: BA287

Optimal path: [‘BA287’, ‘LHR’]

Transmission rate: 104.63341594436687

Flight number: BA49

Optimal path: [‘BA49’, ‘LHR’]

Transmission rate: 118.95384084340549

Flight number: DL209

Optimal path: [‘DL209’, ‘LHR’]

Transmission rate: 560.2297041411565

Flight number: UA919

Optimal path: [‘UA919’, ‘LHR’]

Transmission rate: 104.59025204032109

We present in this subsection examples of applications that can be implemented using aeronautical ad-hoc networks (Zhang et al., 2022). We have seen that aeronautical ad-hoc networks allow peer-to-peer communications, so we can consider setting up applications that take advantage of it. The authors propose distributed mechanisms for automatic conflict resolution (in the aeronautical sense).

The proposed methods are based on the exchange of information between aircraft (information on their future trajectories in particular). These applications make it possible to reduce air traffic controllers’ workload or implement autonomous control of air traffic (performed by the planes themselves).

Meteorological applications could also take advantage of these peer-to-peer communications. For example, the authors propose a system called “wind networking,” in which the aircraft measures the strength and direction of the winds. This information is then transmitted to other aircraft so that the latter can precisely calculate their time of passing certain waypoints, thus improving the prediction and detection of conflicts.

Air-ground applications

An example of an air-ground application consists of a continuous real-time automatic transmission of flight parameters, normally recorded in Flight Data Recorders, commonly called “black boxes.” This would make it possible to analyze the disaster, even if the aircraft wreckage is not located or inaccessible.

Three scenarios are defined in the report by Zhang et al. (2022), each corresponding to a different volume of data exchanged:

• 10 bytes/s: just the coordinates for latitude, longitude, and height;
• 100 bytes/s: essential parameters;
• 1550 bytes/s: all FDR parameters.

This report also identifies the problem of pointing high-gain satellite antennas when the aircraft is in abnormal flight situations (strong roll, for example). This would make it impossible to send FDR data when it is most crucial (Zhang et al., 2022). An aeronautical ad-hoc network equipped with omnidirectional antennas would not suffer from this problem. We define several sets of “datalink” applications that air traffic control services and pilots use in different flight domains.

These applications concern, for example:

• various clearances (authorizations given to pilots);
• flight information services;
• alert messages;
• flight plan information;
• weather and weather information (textual or graphic);

Aeronautical ad-hoc networks in the literature

The literature presents several studies on aeronautical ad-hoc networks; for example, Sampigethaya et al. (2011), (Ayaz et al. (2009), and Hu et al. (2015) define an architecture for aeronautical ad-hoc networks.

As part of the latter, Hoffmann et al. (2010) demonstrated the feasibility of an aeronautical ad-hoc network over the Atlantic Ocean. However, their study was conducted based on trajectories (shortest path between the point of departure and that of arrival) and without taking into account the problems of the physical and link layers.

Perera et al. (2004) demonstrate the feasibility of an aeronautical ad-hoc network in the continental zone and the oceanic zone from real aircraft trajectories. They focus on the relationship between aircraft connectivity and radio link range, concluding that ranges of 150 km in the continental zone and 350 km in the oceanic zone are required to achieve an average connectivity of 90%. The authors propose a physical and link layer architecture adapted to these ports. It should be noted that connectivity is measured geometrically, and does not depend on the performance of the protocols used.

Movement of nodes in an aeronautical ad-hoc network

Our study mainly focused on “cruising” aircraft, which corresponds to the flight domains. We describe in this section the constraints that apply to these devices and a particular case of air traffic.

Separation rules

Civil aviation aircraft must comply with separation rules for safety reasons. The rules presented here describe those that generally apply in the case of commercial aviation; we have chosen not to be exhaustive for the sake of brevity. Vertical separation refers to the difference in altitude between two aircraft (Zhang et al., 2022). The nominal vertical separation for aircraft on a cruise is generally 1000 feet below flight level 290 and 2000 feet above this level.

Horizontal separation (or spacing) refers to the “horizontal” distance between two aircraft. The minimum horizontal separation varies according to the airspace considered. In areas where air traffic control is carried out using radar, the minimum horizontal separation is between 3 and 8 nautical miles. It is increased in the absence of radar coverage, for example, in an oceanic zone: 60 nautical miles between two parallel routes and 10 minutes of flight time between two following aircraft.

Two planes are said to be separated if they respect the criterion of horizontal separation or the criterion of vertical separation with respect to each other. At all times, each plane must be separated from all its neighbors. For airplanes flying under the Instrument Flight Rules regime, i.e., most commercial aviation, the responsibility for this separation is entrusted to the air traffic controllers. The latter can give instructions to the planes and modify their trajectory to resolve future conflicts. To simplify this work, aircraft generally follow predefined airways.

Older data link networks

Air-ground sub-networks

Any network that carries out ground-to-ground transmissions necessarily requires an air-ground sub-network (Hoffmann et al., 2010). Currently, two approaches are used: so-called “cellular” systems, for which radio transmissions take place directly between ground stations and aircraft, and satellite systems, for which a satellite (or a constellation of satellites) serves as a relay between aircraft and ground infrastructure.

Direct link systems

All air-ground communications in this kind of sub-network happen face-to-face between an aircraft and a ground station. These sub-networks are sometimes qualified as “cellular.” Indeed, they owe this name to the fact that the position of the ground stations and their radio range define “cells,” geographical areas outside of which communications to the ground station are impossible (Hu et al., 2015). A cellular system introduces various constraints concerning, for example, the management of frequencies (two adjacent cells must not use the same frequency under penalty of jamming their mutual transmissions) or the handover between two ground stations (Sampigethaya et al., 2011). In addition, advertised capacities must be shared between all devices present in the area covered by a station.

Satellite systems

Satellite communication systems are based on the use of the latter as a relay in air-ground communications. The position of these satellites in orbit around the Earth allows these systems to cover a large geographical area (Zhang et al., 2022). Some companies offer services based on geostationary satellites, which allows them to provide worldwide coverage (except for the polar zones beyond 75° latitude). Operating in the L band, this system offers speeds ranging from 2.0 kbit/s per aircraft to 9.8 kbit/s using an antenna at high gain.

Aeronautical ad-hoc networks

Aeronautical ad-hoc networks form a separate class of networks. We present the definition of aeronautical ad-hoc networks compared with other types. We then describe the interest of this concept that we propose as a complement to traditional means of communication and the specific characteristics encountered during the study of such networks. We also present some examples of possible uses of aeronautical ad-hoc networks, which justify their study and use. We will present the optimization of connections in an aeronautical ad-hoc network through the example of transatlantic traffic.

Definitions

An ad-hoc network is a network in which each node can be a source, a destination, and a relay for the data transported by the network (Sampigethaya et al., 2011). Thus, these networks do not rely on infrastructure. End-to-end transmissions within an ad hoc network generally use one or more relays; the expression “multi-hop network” is also used. Ad-hoc networks can be grouped into classes that have common characteristics.

The class of mobile ad hoc networks includes all ad-hoc networks whose nodes are mobile. This mobility makes dynamic network topology and the use of “wireless” links mandatory. This has led to many works aimed at adapting existing protocols or creating new ones, in particular concerning routing. A vehicular ad hoc network class network is a network whose nodes are land vehicles, generally in motion. This mobility makes the class of vehicular ad hoc networks a subclass of mobile ad hoc networks (Sampigethaya et al., 2011). However, in a vehicular ad hoc network, the movements of the nodes respect certain constraints inherent in road traffic rules. For instance, automobiles are only allowed to travel on roads and are not allowed to travel at high speeds.

Figure 1 – Principle of an aeronautical ad-hoc network.

By analogy with vehicular ad hoc networks for land vehicles, aeronautical ad-hoc networks are defined as ad hoc networks whose nodes are aircraft in flight (Ayaz et al., 2009). We propose to use them as a communication infrastructure for air-air or air-ground “data link” transmissions, in addition to the technologies presented in the introduction of this part. To allow communication between a node of an ad-hoc network and services located in another network, gateway nodes to networks on the ground (called a gateway in the literature) are necessary. Ground stations will be regarded as gateways for exchanges between aircraft and ground services in the context of aeronautical ad hoc networks (Hu et al., 2015).

Characteristics of aeronautical ad-hoc networks

The specification and design of the various protocols required for the functioning of aeronautical ad-hoc networks must consider several factors. We present those that have a strong influence on the work presented in this report.

Mobility

As in all mobile ad hoc networks, the nodes of an aeronautical ad-hoc network are mobile (Ayaz et al., 2009). This imposes the use of dynamic routing algorithms capable of adapting quickly to changes in topology. Aircraft movements are governed by complex traffic rules (rules of the air) and obey economic imperatives (schedules depending on customer demand, minimization of fuel consumption, etc.) (Sampigethaya et al., 2011). Consequently, their modeling is a complex problem. We detail below the solution we have adopted to solve this problem.

Link range

The link range required for aeronautical ad-hoc networks (from 150 km to 450 km) is generally much higher than in other types of ad-hoc networks (for example, 300 m for vehicular ad hoc networks) (Hoffmann et al., 2010).

As opposed to vehicular ad hoc networks where masking due to the environment (buildings, etc.) must be taken into account, aircraft in an aeronautical ad-hoc network have a direct line of sight to other nodes in the network, the transmissions being only masked by the horizon as soon as the airplane is in cruise. Thus, two airplanes in flight at 30,000 feet in altitude are in the direct vision of each other as soon as they are less than 580 kilometers apart (Zhang et al., 2022).

The order of magnitude of the ranges has consequences on the access layers (physical and link layer) in terms of propagation delays and signal power.

Number of nodes

The number of nodes present in an aeronautical ad-hoc network is generally very high compared to the size of the mobile ad-hoc networks studied in the literature. For example, one can observe up to 560 planes present simultaneously in the ocean zone (Hoffmann et al., 2010). This implies that the routing algorithm used is robust to scaling up.

Energy available

As in vehicular ad hoc networks, we do not consider energy a problem on board an aircraft; the aircraft’s engines permanently supply sufficient electrical power for all onboard computers (Ayaz et al., 2009).

We also assume that the computing power available on board is equivalent to that of a desktop computer, the energy, and the space available on board an airliner authorizing the carrying of such equipment.

Conclusion

Aeronautical ad-hoc networks present a certain number of advantages compared to the cellular and satellite systems presented in the introduction of this part.

Coverage of large areas

Thanks to their multi-hop communication capacity, the coverage of an aeronautical ad-hoc network is potentially infinite when the plane density is sufficient and a packet can be relayed a large number of times (Ayaz et al., 2009). If we consider aeronautical ad-hoc networks as a support for ground-on-board communications, then this makes it possible to cover a very large area from a single ground station.

In particular, this makes it possible to cover oceanic areas, unlike a one-hop cellular system which can only be deployed in continental areas.

Little infrastructure required

A corollary of large area coverage is that the number of ground stations required to provide access to control services is lower for an aeronautical ad-hoc network than for a cellular network (Hoffmann et al., 2010). Indeed, thanks to multi-hop communications, the coverage of a ground station that is part of an aeronautical ad-hoc network is equal to the size of this aeronautical ad-hoc network. It is, therefore, not necessary to deploy ground stations over the entire surface of the territory to be covered as in a cellular network. This offers an advantage to aeronautical ad-hoc networks in terms of installation and maintenance costs.

Peer-to-peer communications

Multi-hop transmissions in an aeronautical ad-hoc network are not restricted to air-ground exchanges. Such a network also allows air-air transmissions at more than one hop, which makes it possible to envisage new applications.

Simple embedded equipment

The common solution proposed is only based on omnidirectional transmissions, which can be carried out using simple monopole antennas (Zhang et al., 2022). These antennas are easier to integrate and produce lower aerodynamic drag than high-gain satellite antennas.