Keywords

1 Introduction

An Aeronautical Ad hoc NETwork (AANET) is an ad hoc network in which inflight aircraft can act as senders, receivers and relays for digital data transmissions. They are studied as a complement to traditional aeronautical communication systems such as satellite or cellular systems [1].

The feasibility of an AANET for air-ground communications over the North Atlantic Tracks (NATs) has already been demonstrated in previous studies [2], and several routing algorithm have been proposed. Amongst them, we have proposed Node Density TBR (NoDe-TBR), an innovative and promising solution. As described in [3], it presents better performances in terms of reachability and delay than classical routing algorithms for a fraction of the signalization traffic volume.

In this paper, we present an assessment NoDe-TBR with two types of applications proposed by civil aviation authorities. This assessment has been conducted by simulation in a realistic environment, with replayed aircraft trajectories and realistic access layers. A periodic transmission of several parameters of the Flight Data Recorders (FDR) is used in the first experiment. The associated data traffic consists only in air\(\rightarrow \)ground transmissions. A set of relevant air traffic control applications have been simulated in the second experiment. These latter generate a data traffic in both directions between aircraft and ground stations.

The rest of the paper is organized as follow: Section 2 describes NoDe-TBR. The settings used in the simulations are described in Sect. 3. The experiment with the FDR application and the experiment with the air traffic control applications are described and analyzed respectively in Sects. 4 and 5. Finally, our conclusions are given in Sect. 6

2 NoDe-TBR

NoDe-TBR is a trajectory-based routing protocol proposed and described in details in [3]. We present here a short description of its main features.

2.1 TBR

NoDe-TBR is based on the concept of Trajectory-Based Routing (TBR) [4]. In TBR, a geographic trajectory (geopath) is computed by the sender. The full geopath that a packet has to follow is carried in its header (source routing), and the relays forwards it on a route matching this geopath (see Fig. 1). It can be seen as an evolution of cartesian routing, where the forwarding is based only on the position of the destination.

Fig. 1.
figure 1

General principle of TBR.

Full size image

A TBR routing protocol has two independent parts:

  • A geopath computation algorithm;

  • A forwarding algorithm.

The geopath computation algorithm must take into account the properties of the network (node movement, geographic distribution of the nodes...). The forwarding algorithm is used to select the next hop amongst the neighbors each time a packet is forwarded.

2.2 Geopath Computation

In NoDe-TBR, the geopath design is based on two assumptions. First, the higher the aircraft density along the geopath is, the higher the delivery probability will be. Second, the shorter the geopath is, the higher the delivery probability will be. Hence the geopath computation method used in NoDe-TBR takes into account the local aircraft density as well as geographical length of the geopath.

In the rest of the paper, d denotes the aircraft density. It can be computed with a kernel density estimation [3] (an example of such density map is shown in Fig. 2).

Fig. 2.
figure 2

Aircraft density map (greyscale: dark = high density).

Full size image

Definition. From the previous assumptions, it can be concluded that the geopath should minimize a quantity of the form \(\frac{l}{d}\) with l the length of the geopath, and d the aircraft density (the aircraft density is a function of the position). The geopath between a sender S and a destination D is defined as a function \(\gamma : [0;1] \rightarrow \mathbb {R}^2 \) such that:

  • \(\gamma (0) = \text {Position of S}\)

  • \(\gamma (1) = \text {Position of D}\)

  • \(\gamma \) minimizes the integral (1)

$$\begin{aligned} \int _0^1 \Vert \gamma _i'(t)\Vert \cdot i(\gamma (t)) dt \end{aligned}$$
(1)

Consequently, \(\gamma \) is a minimizing geodesic between S and D. i is an “index” function used to take into account the aircraft density. In NoDe-TBR, we have:

$$\begin{aligned} \begin{array}{l|rcl} i: &{} [0;1] &{} \longrightarrow &{} \mathbb {R} \\ &{} t &{} \longmapsto &{} \frac{1}{D + d(\gamma (t))^\alpha } \end{array} \end{aligned}$$
(2)

In (2), D is the average aircraft density over the whole map, and \(d: \mathbb {R}^2 \rightarrow \mathbb {R}\) is the function associating the aircraft density to each point of the map. \(\alpha \) is an exponent that can be used to fine-tune the behavior of the algorithm.

The length of \(\gamma \) is given by \(l = \int _0^1 \Vert \gamma _i'(t)\Vert dt\) (this is (1) without the index function). The trajectory that minimizes l is the shortest path between S and D. The index function i changes this behavior: the function \(\gamma \) that minimizes (1) is “attracted” by high density areas because i is lower in these areas.

Computation. The geopaths are computed in three steps:

  1. 1.

    The Fast Marching Method (FMM) [5] is used to compute the front propagation time. The seed of the FMM is set to the position of the sender.

  2. 2.

    The minimizing geodesic between the positions of the destination and the sender is then computed with a gradient descent algorithm. This step produces a geopath in the form of a sequence of geographical coordinates (represented in white in Fig. 3).

  3. 3.

    The number of coordinates of the geopath is reduced with the Ramer-Douglas-Peucker algorithm [6].

Fig. 3.
figure 3

Examples of geopaths toward ground stations and associated Voronoi map.

Full size image

Update. Because the spatial aircraft density changes during the day and from day to day, the aircraft density estimation and the geopaths must be regularly updated.

2.3 Routing Protocol

Forwarding Method. Several forwarding method have been assessed in [3], and ADR (Advance Delay Ratio) provides the best performances. This method has been selected for NoDe-TBR. In order to learn the positions of its neighbors (needed to select the next hop), each aircraft uses an Automatic Dependent Surveillance - Broadcast (ADS-B) in/out transceiver. This device broadcasts the position of the aircraft and receives the positions of its neighbors. This equipment is being mandated for airliners.

Signalization Traffic. The NoDe-TBR routing protocol exploits the geopath computation method previously defined in order to forward packets in the network. Because this method involves the use of a density map, signalization data must be exchanged between aircraft so that every aircraft can build a density map.

NoDe-TBR makes use of a positioning system (such as GPS) in order to learn its current position. Airliners are already equipped with such systems.

It remains however necessary to exchange data between aircraft in order to make them aware of the position of the other aircraft that are beyond the radio range. In NoDe-TBR, each aircraft broadcasts periodically an estimation of its future trajectory. These broadcasts are done via a flooding dissemination mechanism to ensure that every node in the network receives the trajectory predictions.

In NoDe-TBR, a periodic refresh policy is used. The refresh interval is set 20 min, approximatively the time required by an aircraft to travel half the radio range while flying at its cruise speed. It has to be noted that one node can compute geopaths toward every other node in the network with the same density map. One can thus consider that the signalization traffic generation is a proactive process in NoDe-TBR.

3 Performance Assessment Settings

3.1 Realistic Access Layer Model

In order to realistically model the point to point communications, we use a modified version of the RP-CDMA protocol. The original RP-CDMA is described in [7] and its performances with classical routing algorithms are studied in [8].

Description of RP-CDMA. RP-CDMA is a protocol which solves the problem of code attribution inherent to CDMA access layer. The payload of a RP-CDMA frame is spread with a randomly selected code, and an identifier for this code is included in the header of the frame (cf. Fig. 4).

This frame structure provides a separation between the signalization channel (headers) and the data channels (payload). If the set of payload codes is large enough, RP-CDMA is mainly limited by header collisions.

Fig. 4.
figure 4

Base structure of a RP-CDMA frame.

Full size image

In order to improve RP-CDMA performances in long-range ad-hoc networks, two modifications have been made to the original protocol. First, an aggregation policy has been implemented in order to increase the size of the payload and reduce the header to payload ratio. Thus the load on the signalization channel is reduced, and the frame losses are reduced. Secondly, p-persistent CSMA is used as access method.

The different parameters that define the behavior of RP-CDMA have been optimized with the method described in [8], and in the same conditions as in this paper. In particular, the optimal maximum frame length is 9000 bits.

Modelisation Assumptions. The RP-CDMA model uses the following conservative assumptions:

  • If two headers collide, then both frames are considered unrecoverable.

  • If there are less than \(maxPayload_{rx}-1\) other frame colliding simultaneously with a given payload, this payload can be decoded. Otherwise, it is not recoverable [9].

  • If the distance between a sender and a receiver is above a given range, the frame is not taken into account.

As demonstrated in [2], a radio range of 350 Km is enough to have an average connectivity over 90% in the North Atlantic flight corridor. Based on this publication and the results in [9], we use the following values: \(maxPayload_{rx} = 25\), \(range = 350\) km and \(bitrate=800\) kb/s.

The length of the RP-CDMA frame header is set to 80 bits. The size of the fixed information control fields is 136 bits, and 46 bits are added for each encapsulated packet. The access layer modules uses FIFO queues to store a maximum of 100 pending packets.

3.2 Simulation Environment

The models are developed and implemented in the simulator OMNeT++ [10]. We use the UDP and IP model from the INET framework [11]. We use custom modules for the traffic generation, the node mobility, the access layers and the routing.

3.3 Node Positions

In this paper, we focus on the North Atlantic Tracks (NAT) [1] because they cover an area where it is impossible to deploy a ground-based communication system. We replay real aircraft position data from Eurocontrol historical traffic repository [12] in order to take into account the diversity of constraints that are applied to aircraft trajectories. Several different days are replayed to add statistic diversity.

Because of the computational cost of the simulation, we have to restrict the simulations to three sets of replayed trajectories, each of them consisting in a one-hour time slot for three different days. The average Instantaneous Aircraft Count (IAC) for each set of trajectories is represented in Table 1.

Table 1. Average IAC for each set of trajectories.
Full size table

In order to match the different possible air routes and hence maximize the probability of delivery, twelve ground stations (represented as black triangles on Fig. 2) are placed on land masses around the area of interest.

3.4 Metrics

In order to quantify the performances of the AANET, the following metrics are defined.

Normalized Reachability. We define reachability as the ability to send packets bidirectionally between an aircraft and a ground station (it is similar to a ping availability).

In an AANET topology, some nodes may not be able to reach a ground station because they are too far from any other nodes, independently of the performance of the routing algorithm. In order to use a metric without this bias, the reachability values are normalized by the “connectivity to the ground”. Let \(\mathbf {G}=(\mathbf {A} \cup \mathbf {S},\mathbf {E})\) be the graph representing our network. The vertices in \(\mathbf {A}\) are the inflight aircraft and those in \(\mathbf {S}\) are the ground stations. The edges \(\mathbf {E}\) are the feasible links. Let \(N_{p}\) be the number of aircraft in \(\mathbf {A}\) for which a path to a ground station exists. The “connectivity to the ground” is defined as \(C = \frac{N_p}{|A|}\).

The normalized reachability is then defined as \(\frac{R}{C}\), with R the ratio of reachable aircraft.

E2E Delay. The end to end (E2E) delay is measured for each received data packet.

E2E AR. The End to End Acknowledged Ratio (E2E AR) is computed from the end-to-end application-level acknowledgements. This metric takes only into account the data messages that are sent while the aircraft is reachable (see previous definition).

P2P AR. The Point to Point Acknowledged Ratio (P2P AR) measures the ratio of packets that are acknowledged over one-hop transmissions.

4 Flight Data Recorder Application

The first application assessed here consists in the transmission of a part of the flight data that are currently only stored in Flight Data Recorders (FDR). It has been notably proposed in [13] after the loss of the flight AF447, for which the wreckage could not be easily located. It would allow the analysis of some flight parameters even if the FDRs can not be recovered.

4.1 Generated Data Traffic

The data traffic generated to model this application consist in UDP datagrams sent toward ground stations. These datagrams are acknowledged by the ground station. These acknowledgements (or the lack thereof) are used by the sender aircraft to detect whether a ground station is reachable.

We simulate three sizes of application messages described in [13]: 9 bytes, 96 bytes and 1536 bytes. One datagram is sent every second.

4.2 Results

The results of this experiment are presented in Figs. 5, 6 and 7. In every graph in this paper the 95% confidence interval are represented by black vertical error bars.

The graph Fig. 5 represents the normalized reachability. We observe two trends, one for the two lowest sizes of data messages, the other for data messages of 1536 bytes. The same segregation can be observed in Fig. 6. Figure 7 displays however similar results for every size of messages.

Fig. 5.
figure 5

Normalized reachability (FDR)

Full size image
Fig. 6.
figure 6

E2E delay (FDR)

Full size image
Fig. 7.
figure 7

E2E AR (FDR)

Full size image

4.3 Discussion

The fact that the normalized reachability does not reach 100% can be explained by the fact that the computation method used to generate the geopath does not guarantee that a path between the sender and the destination exists. Because the probability of finding a relay along the geopath increases with the number of aircraft, the scenarios with the lowest number of aircraft are more heavily impacted.

The difference in terms of reachability and E2E delay observed for the biggest size of messages (1536 bytes = 12288 bits) is explained by the fact that the data message size is larger than the optimal payload size for the layer 2 (9000 bits). Consequently, its performances are worse for the biggest packets. This problem can be solved by implementing packet fragmentation based on a Maximum Transmission Unit (MTU) to 9000 bits.

In every scenario, the E2E AR is high (over 96%). Consequently, the reachability can be used as an effective metric to determine if the AANET can be used to transmit data to a ground station. If an aircraft detects that it is not reachable, it can decide to use an alternative communication system.

In most cases, the performances of our communication system based on AANET are promising for this FDR application: the normalized reachability is around 90% and the average E2E delay is below 200 ms.

5 COCR Air-Ground Applications

The Communications Operating Concept and Requirements for the Future Radio System (COCR [14]) is a document produced by Eurocontrol which defines air traffic control applications. These applications, based on digital communications systems, will complement and partially replace the voice communications that are currently used for air traffic control.

5.1 Generated Data Traffic

The data traffic generated in this experiment reproduces the unicast applications defined for the Oceanic Remote Polar (ORP) areas in [14]. It consists in UDP packets, whose sizes and periods of sending are set according to [14]. We use the values specified for the phase 2 of digital communication deployment. In this phase, the digital communications become the primary mean for air-ground communications. This phase is expected to start in 2020.

In our model, a simple acknowledgement and retransmission mechanism is implemented in the application layer: if no acknowledgement is received after 3 s, then the message is retransmitted.

In order to reduce the load around the ground stations, the ground station application module generate data toward a given aircraft only when the latter is reachable. This behavior prevents the transmission of packets that could anyway not reach their destination and removes an unnecessary load from the network. To that end, the air\(\rightarrow \)ground application traffic doubles as a network probe traffic in order to let a ground station know which aircraft may be reached. In particular, the application called “SURV” in [14] sends a packet towards the ground every five seconds, which ensures that enough air\(\rightarrow \)ground traffic is generated for that purpose.

5.2 Results

The simulations results are presented in Figs. 8, 9 and 10. For the scenario with a low aircraft load, the performances considering the three metrics are similar to the previous experiment. The normalized reachability and the E2E delay of the other scenarios are worse than in the previous experiment.

The P2P AR ratio is represented in Fig. 11.

Fig. 8.
figure 8

Normalized reachability (COCR)

Full size image
Fig. 9.
figure 9

E2E delay (COCR)

Full size image
Fig. 10.
figure 10

E2E AR (COCR)

Full size image
Fig. 11.
figure 11

P2P AR (COCR)

Full size image

5.3 Discussion

Because in this experiment ground stations receive and send data traffic (unlike in the FDR experiment), the radio channel is more loaded in their vicinity than in the rest of the network.

The consequence of this concentration of traffic is illustrated in Fig. 11. For the scenarios “medium number of aircraft” and “high number of aircraft”, there is a clear difference in the P2P AR measured at the ground stations and in the whole network. The scenario “low number of aircraft” displays a P2P AR very close to 1, which shows that the ground stations are far less loaded than in the other scenarios.

The load of the access layers in the scenarios “medium number of aircraft” and “high number of aircraft” explains that the normalized reachability and delay are worse than in the FDR experiment. There are no significant differences for the “low number of aircraft” scenario because the ground stations are not overloaded.

In every scenario, the E2E AR is high (over 98%). As consequence, we can consider that it is also relevant to use this metric in the context of COCR applications in order to determine whether the AANET can be used to reach a ground station.

6 Conclusions

In this paper, we have presented an innovative routing algorithm for AANETs: NoDe-TBR. The performances of this algorithm have been assessed in realistic conditions: on replayed trajectories and with a realistic access layer model. Two sets of applications proposed by the civil aviation authorities have been simulated.

The first one consist in a remote transmission of flight data parameters, for which the data traffic is only generated in the direction air\(\rightarrow \)ground. The simulations results are promising and show that the proposed architecture is an effective data communication system for this application.

The second set of applications generates data in both directions (air\(\rightarrow \)ground and ground\(\rightarrow \)air). In this experiment, the normalized reachability is above 70%. It means that, when used in complement to other communication systems, the AANET can handle the majority of the aircraft in the NAT.