Quentin Vey

Alain Pirovano

Jose Radzik

AEGATS2016 25 Routing protocol assessment for AANETs

In this paper, we propose to use AANETs (Aeronautical Ad-hoc NETworks) to complement currently used communication systems. An AANET is a network in which every node (aircraft or ground station) is able to relay data to and from other nodes. It allows to extend the range of a ground station by using other aircraft as relays, thus establishing multihops paths between an aircraft and the ground.

The main contribution of our study is the performance assessment of classic routing protocols by simulation with replayed real aircraft trajectories.

The results of these simulations can serve as reference for further studies. Furthermore, under nominal conditions, AODV has the best performances in terms of reachability. These results demonstrates the interest of AANET as a communication system for civil aviation, and call for further studies to improve the performances of routing algorithms.

INTRODUCTION

Datalink communication systems for civil aviation are facing two challenges : the increasing number of flight increases the volume of data to transfer between aircraft and ground, and newly proposed applications will generate more data per aircraft. As a consequence, the current air-ground datalink communication systems will be saturated, and new communication systems will be required.

In an AANET, civil aircraft use air-to-air links to build a network, and they can use this multihop network to communicate with each other. Some ground station can be added to this network and allow communication between any aircraft in the network and services on the ground (see fig. 1). These AANETs are a subclass of Mobile Ad-hoc NETworks (MANETs), and share properties with Vehicular Ad-hoc NETworks (VANETs) [START_REF] Garcia | Aeronautical air-ground data communications: current and future trends[END_REF].

AANETs are envisioned in the long term as a communication system enabling new peer-to-peer services for en-route aircraft such as wind-networking [START_REF] Rodionova | Trajectory prediction in north atlantic oceanic airspace by wind networking[END_REF] or automatic conflict resolution. Such new applications are however not mature enough today, so AANETs are considered in the middle term as a complementary solution to more conventional air-ground communication systems (e.g. satellite links or cellular systems) [START_REF] Vey | Aeronautical Ad Hoc Network for Civil Aviation[END_REF]. This paper will thus focus on the performance of AANETs for air-ground communications.

Because of the nodes mobility, one of the main challenges in MANETs is routing, i.e. the process used to determine the succession of relays between the sender of a packet and its destination. Several protocols have been proposed for AANETs (e.g. ARPAM [START_REF] Iordanakis | Ad-hoc routing protocol for aeronautical mobile ad-hoc networks[END_REF], AeroRP [START_REF] Jabbar | Aerorp: A geolocation assisted aeronautical routing protocol for highly dynamic telemetry environments[END_REF], GLSR [START_REF] Medina | A geographic routing strategy for north atlantic in-flight internet access via airborne mesh networking[END_REF] ...), and they have been evaluated against classical routing algorithms in simulations (AODV for the two first given examples). However, to our knowledge, no actual routing protocol have been assessed in simulations with real aircraft trajectories.

We present in this paper the results of simulations of selected classical routing algorithms in AANET with replayed aircraft trajectories. These algorithms are well known in MANETs, and are often used as a reference to assess the performances of emerging routing algorithms.

The study presented in this paper used replayed aircraft trajectories, which come from aicraft flying through the NATs (North Atlantic Tracks [START_REF] Vey | Aeronautical Ad Hoc Network for Civil Aviation[END_REF]). This particular airspace has been chosen as an example of structured traffic. Previous studies on this routing issue used either random aircraft movements patterns, or a shortest path (i.e. orthodromic) trajectory between departure and arrival airports. This paper is organized as follow: related work is presented in 2, the routing problem is described in 3. The protocols and their adaptation to our case are described in 4. The experimental settings are described in 5 and the results are presented in 6 then discussed in 7. Our conclusion summarizes our findings, and future works are described.

RELATED WORK

The feasibility of an AANET has already been studied, for example in [START_REF] Medina | A geographic routing strategy for north atlantic in-flight internet access via airborne mesh networking[END_REF] and [START_REF] Besse | RESEAUX AD HOC AERONAU-TIQUES[END_REF].

In [START_REF] Besse | RESEAUX AD HOC AERONAU-TIQUES[END_REF], the author focuses on the radio transmission in an AANET. He first establishes the required range to ensure a given connectivity, then he proposes a point to point radio transmission mechanism. The end-to-end performance is however only evaluated with an ideal shortest-path routing algorithm.

In [START_REF] Medina | A geographic routing strategy for north atlantic in-flight internet access via airborne mesh networking[END_REF], the authors propose a geographic routing algorithm with load balancing between ground station. The performances of this routing algorithm are however not compared to another known algorithm, so it is difficult to tell the merit .

THE ROUTING PROBLEM IN AANETS

Routing

Routing is the process of selecting a route (i.e. a sequence of relays in the network, illustrated by dotted arrows in fig. 1) in order to reach a given destination. It is a central problem in networks, especially in MANETs, because it handles the end to end delivery.

A routing algorithm generally sends packets between specific nodes known as routers to exchange the required information for the route computation (in an ad-hoc network, any node can be a router). This signalization traffic is usually sent on the same links as the application data. As a consequence, it should be minimized in order to maximize the link resource available for the useful data.

Routing algorithms can be classified according to several characteristics. One of the most important of these characteristics is the moment the route resolution is performed : it can either be reactive, which means that the routes are only computed when actually needed, or it can be proactive, which means that routes are computed before actually being required.

Reactive routing algorithms generate usually less signalization because only the required routes are resolved, but this comes at the expense of a longer delay when sending the first message to a given destination because this route has to be found first. This delay is also observed when a route is broken and a new route must be re-computed.

Proactive routing algorithms on the other hand have routes toward reachable nodes immediately available, but pay a heavier price in term of signalization.

Specificities of routing in AANETs

The following specific properties of AANETs have a strong influence on the performances of routing algorithms:

• Node density : in AANETs, and especially in oceanic regions, the aircraft density is well structured. The node density is high along the airways, and low outside these areas. This means that mobility model with random positions and mobility are not representative of the conditions of a real AANET. Because of the wind conditions, the routes, re-computed twice a day, generally differ from the shortest-path route by a thousand kilometers [START_REF] Vey | Aeronautical Ad Hoc Network for Civil Aviation[END_REF].

• Node movement : in AANETs, aircraft can travel at speeds up to 1000 km/h. The movement of the nodes will generate route failures.

• Number of nodes in the network : on a typical day, an AANETs over the north Atlantic corridor can count more than 600 aircraft simultaneously. This implies that the routing protocols used in AANETs has to be scalable.

• Size of the network : an AANET can span over thousands of kilometers. This means that a single station is not enough to manage the whole network continuously, so the AANET must be distributed in order to autonomously recover from network disruptions.

These specificities make of AANETs a particular class of networks and justifies the study of routing algorithms in their particular conditions. Other studies (such as [START_REF] Iordanakis | Ad-hoc routing protocol for aeronautical mobile ad-hoc networks[END_REF], [START_REF] Jabbar | Aerorp: A geolocation assisted aeronautical routing protocol for highly dynamic telemetry environments[END_REF] [6]) of AANETs have not studied them with realistic trajectories, so the real impact of node density and node speed was not taken into account in these study.

CONSIDERED ROUTING PROTOCOLS

We selected three well-known routing protocols, namely AODV (Ad-hoc On demand Distance Vector [START_REF] Perkins | Ad hoc on-demand distance vector (aodv) routing (rfc3561)[END_REF]), DYMO (Dynamic MANET On-demand routing protocol [START_REF] Ehrenreich | Implementing and evaluating the dymo routing protocol[END_REF]) and BATMAN (Better Approach To MANet routing [START_REF] Johnson | A simple pragmatic approach to mesh routing using batman[END_REF]). AODV and DYMO are typical examples of reactive routing algorithms, and BAT-MAN is a well-known proactive routing algorithm.

Given the communication traffic profile (between air and ground) and the position of the nodes, messages are expected to be forwarded along routes between aircraft and ground station. AODV and DYMO seem well suited to this case because intermediary nodes can construct routes toward the source of a route resolution and toward its destination during the route discovery phase, even if they are neither the source or the destination of this particular route (see 4.1 and 4.2). In our setup a ground station is always part of a route, so the required signalization is reduced because the intermediary nodes will not require a route resolution toward the ground when they have data to send. DYMO is expected to have a lower signalization data volume than AODV thanks to its path accumulation mechanism.

BATMAN, an effective proactive routing algorithm, has been preferred over OLSR because of its scalability [START_REF] Johnson | A simple pragmatic approach to mesh routing using batman[END_REF].

These classic routing algorithms were selected because they have been widely studied in a variety of networks, and we want to assess their performances in the context of AANETs with replayed aircraft trajectories.

The rest of section describes the general working principle of each routing protocols.

AODV

Ad-hoc On demand Distance Vector (AODV [START_REF] Perkins | Ad hoc on-demand distance vector (aodv) routing (rfc3561)[END_REF]) is a reactive routing algorithm which performs route discovery on demand, and handles route maintenance while they are in use. It uses sequence numbers in order to ensure loop-freeness and manage the freshness of the information: each node has a sequence number which is incremented during specific actions and is included in control packets. A node can thus detect stale information by comparing the address/seqNum pair it has previously recorded with the pair of the received packet.

Route discovery is performed when a packet is generated and there is no route entry toward its destination. A "route request" packets (RREQ) is broadcasted to the whole network, in a flood-like manner. These RREQ contains the address of the source of the request, its current sequence number, the address of the requested destination and the last known sequence number for the destination. Each node receiving this packet adds a route entry toward the source of the RREQ and re-broadcast the RREQ if it can't answer it. When this RREQ reaches the destination or a node with a fresh enough route entry, a "route reply" packet (RREP) is generated and sent "unicastly" to the source node. Each node forwarding this RREP also records a route entry toward the destination. Once a route discovery has been completed, every node on the path between the source of the RREQ and the generator of the RREP is aware of a route toward the requested destination, and also of a route toward the source of the request. Because AODV uses symmetric links (e.g. to transmit RREP), a mechanism involving periodic "hello" messages is used to detect neighbors which are reachable through a symmetric link. Broken links are detected in the same way, and they trigger the sending of a route error message (RERR).

AODV features a rate limitation for control messages: no more than 10 control messages can be sent per second. However, given the geographic positions of the aircraft in our scenario, there is sometimes a significant amount of aircraft that could not be reached (e.g. flying alone on a remote route). In consequence, if the ground station tries to reach every aircraft, it will keep sending RREQ even though they are doomed to fail, these request being repeated while there are messages to send. This constant flow of control messages can reach the rate limit in the nodes close to ground stations, so any further control message is dropped, including RREQ which could succeed.

DYMO

The Dynamic MANET On-demand routing protocol (DYMO, [START_REF] Ehrenreich | Implementing and evaluating the dymo routing protocol[END_REF]), also called AODVv2, is an evolution of AODV. It uses the same mechanism of RREQ and RREP but add a "path accumulation" mechanism : each node forwarding a routing message (RREQ or RREP) can add its own address in the packets header. Thus, any node receiving this packet learns the route toward the requested destination or the source of the RREQ, and also toward every other node on the route. This reduces the required number of route resolution and control packets for every intermediary node. A second difference is that it does also not use the "hello" messages from AODV, but relies instead on received RREQ and RREP in order to detect broken links .

BATMAN

BATMAN (Better Approach To MANet routing, [START_REF] Johnson | A simple pragmatic approach to mesh routing using batman[END_REF]) is a proactive protocol, so it uses a radically different mechanism. In BATMAN, each node broadcasts regularly an "Originator Message" (OGM), which is a small signalization packet. This OGM is then flooded in the whole network. It contains the originator address, and the originator sequence number. This sequence number of a given node is increased each time this node sends an OGM, and is used by the other nodes receiving this OGM to keep track of outdated informations.

When a node receives an OGM, it records the sequence number contained in the packet, the originator address and the address of the neighbor node that just sent it. It then uses a ranking procedure to give a rank to this neighbor as a next-hop toward this originator, then defines next hop in the route toward this originator as the highest ranked neighbor. The neighbors are ranked according to the amount of OGM received from them during a given time window. This takes into account the link quality as well as route freshness. The node finally rebroadcasts the OGM, but only if it is received from the best neighbor for this originator.

The period of OGMs generation is a critical parameter, as it controls the refresh rate of the routing information and the volume of signaling data generated. If its value is too low then few control packets are generated, so the network consumption is low, but the routes take time to be refreshed, leading to more routing errors. If its value is high then the sending rate keep the routes updated more frequently, but it increase the generated signalization volume.

In our simulations, this value is optimized for the special case of AANET. Several simulations have been run for different values of this period under a low aircraft density scenario. According to these simulations, the value of 5 s minimized the delay and maximized reachability, and is used in the simulations presented in this paper.

SIMULATION SETTINGS

Simulation environment

We conduct the simulations in the OMNeT++ framework [11]. The model of the nodes uses INET's [12] module for the protocols AODV, DYMO, BATMAN [START_REF] Ariza-Quintana | Implementation of manet routing protocols on omnet++[END_REF], UDP, IP and ideal wireless link. Custom modules are used for the traffic generation and node mobility.

Link model

The link layer is responsible of the point to point transmission (either air-air or air-ground). In order to assess the performances of routing algorithms independently of other factors, we used a simplified model.

The link model used in the simulations presented here is an ideal link, which means that messages are received without error if the sender and the receiver are closer than the maximum range, or they are lost if the distance between sender and receiver is above the maximum range. The delay of this link is equal to the propagation delay plus the transmission duration.This model is very optimistic and corresponds to an omnidirectional antenna.

This model has a FIFO queue of size 100 packets. This means that packets sent or relayed by a given node are dropped if there are 100 packets already waiting at the link layer. Such situation can occur because the link sending capacity is finite whereas packet generation and packet relay are not limited.

In [START_REF] Besse | RESEAUX AD HOC AERONAU-TIQUES[END_REF], the authors have shown that a range of 350 km ensures an average connectivity over 90% in the north Atlantic corridor and that a link capacity of 800 kb/s is an optimum with respect to average throughput per node. The link model of our simulation uses these values.

Node positions

In our study, we focus on the NATs. We use real aircraft position data from Eurocontrol historical traffic repository [START_REF][END_REF], tailored to fit our study case. This use of real aircraft trajectories is driven by the relationship between node spatial distribution and routing protocol performances in MANET [START_REF] Garcia De La Fuente | A performance comparison of position-based routing approaches for mobile ad hoc networks[END_REF]. We found no existing mobility model which take into account all the specificities of civil aviation (from separation rules to random weather events). Several different days were re-played to take into account the statistic diversity while using these real geographic data.

We restrict the simulations to a set of representative time slots because of the computational cost of the simulation. The results presented in this paper are obtained with simulation conducted on the 8h to 9h time slot, for the 2013-09-14, 2014-05-02 and 2015-05-15. These dates present the median number of aircraft per day for their year, and the 8h to 9h time slot corresponds to a medium Instantaneous Aircraft Count (IAC) during the day. Furthermore, this time slot correspond to the end of the eastbound traffic flow, and the beginning of the westbound flow. This is the moment during which the topology of the network seems to vary the most, and is hence the worst-case scenario for routing algorithms.

Twelve ground stations were placed on land masses around the area of interest, in order to match the different possible air routes and maximize the probability of delivery(see fig. 3).

Traffic generation

The generated traffic consists in periodic UDP messages sending (data messages) from aircraft (respectively ground station) to ground stations (respectively aircraft). It mimics the communication between inflight aircraft and the ground. When a data message is received, an application-level acknowledgement is sent (another UDP message).

This data messages generation is also designed to trigger a response from the reactive routing algorithms in order to generate a meaningful signalization traffic: the period of sending was set to 1 s, low enough to prevent route expiration in the case of reactive algorithm. The size of the data messages generated was set to 9 bytes. The data messages serves also as probes to measure several metrics.

Ground station do not initiate communications, they start sending data messages to a given aircraft only when they have received messages from it. This particular setting is required because of a side effect of the RREQ flood protection mechanism in AODV (see 4.1).

Metrics

Delay

The one-way end-to-end transmission delay is measured with the UDP packets, and recorded in an histogram. The result is presented as D 95 , the maximum delay for 95% of the packets.

Reachability

Reachability is a measure that we define in order to provide a meaningful measure for the application. It is defined as the ability to exchange messages bidirectionnally between a source and a destination. We measure it by sending a probe packet and waiting for its acknowledgement. The node is considered reachable if this acknowledgement is received within a given time (ackT ime), otherwise it is considered unreachable. In this paper, we only consider the reachability between aircraft and ground stations. For the sake of concision and clarity, reachability has the meaning of "reachability with any ground station" in the rest of this paper.

The global reachability is defined as the ratio of reachable aircraft. This global reachability must however be normalized: in the actual topology of our network, some subset of the nodes can not be reached because they are too far from any other nodes. In order to take this point into account and free the measure from this bias, the global reachability is normalized against the "connectivity to the ground" (connectivity has here the meaning used in graph theory). Let G = (A ∪ S, E) be the graph representing our network. The vertices A are the inflight aircraft and S the ground stations, and the edges E are the possible ideal links (i.e. it exists a link when two aircraft are closer than 350 km in our case). Let N p be the number of aircraft in A for which it exists a path to a ground station. We define the "connectivity to the ground" as C = Np |A| Preliminary simulations show that the one-way delay is lower than 1 s for 98% of the packets. We thus set ackT ime to 3 s in this study, large enough to ensure that the measured losses of reachability do not correspond to the transmission and propagation delay, and small enough to provide a sensible value in regard of the requirements of actual services [START_REF]Cocr : Communications operating concept and requirements for the future radio system -version 2[END_REF].

Network routing load

The network load due to the routing signalization is measured by counting routing packets passed from IP modules to MAC modules.

RESULTS

On every graph in this paper, error bars represent 95% confidence interval.

Fig. 4 represents the average normalized reachability. It shows that AODV performs significantly better than DYMO. Given the wide confidence interval of BATMAN, we can only say that its performance in terms of reachability is comparable to the one of DYMO.

The D 95 for the one-way end to end delay for each protocol are presented in table 1. Dymo has the highest delay.

The amount of signalization generated by each protocol is presented in fig. 5. It follows the expected pattern: BATMAN generates significantly more routing control messages than AODV, which generates significantly more signalization than DYMO. This graph shows only the generated signalization volume, the data rate measured at the MAC layer is 124 kB/s for DYMO, 143 kB/s for BATMAN and 163 kB/s for AODV.

The packet hop count histogram, presented in fig 6, shows that DYMO carries a higher ratio of packets on longer routes. BATMAN displays a higher ratio on shorter routes.

DISCUSSION

Although there are no losses at the link layer, the values of reachability presented in the graph 4 do not reach the theoretical maximum of 1. This can be explained by several facts:

• Following the tree topology, the data traffic converges toward a few ground stations. In the vicinity of the ground stations, the link layers are overloaded and packets are dropped.

• Route resolution takes time (specifically in the case of reactive protocols), so the node becomes reachable only some time after they become connected to a ground station (connected as in graph theory sense).

• A route can become unavailable when a link is broken due node movement, even though another path is already available. The route resolution leads to a down time during which the node is unreachable.

The delays presented in table 1 are below the propagation delay to and from a geostationary satellite (around 250 ms). This means that AANETs have an advantage compared to satellite link in terms of delay.

BATMAN signalization in fig. 5 is one order of magnitude above AODV and DYMO because, as a proactive protocol, it maintains routing information toward every node in the network. With BATMAN, the load generated by each node is proportional to the square of the number of node in the same connected subnet because it rebroadcasts every OGM it receives. So when the network is partitioned, the amount of signaling packets sent by each node is reduced by the square of the size reduction of each subnet, which leads to a great variation in the load generated by BATMAN, hence the wide confidence interval. The reactive protocols generate less signalization than BATMAN and, as expected, DYMO generates less control packet than AODV.

The fig. 6 can be explained by the refresh rate of each protocol : if a protocol has a low refresh rate, it will keep using an old route even though a new shorter one is available. BATMAN, as a proactive routing algorithm, has the highest refresh rate. AODV and DYMO refresh their routes only when a link loss is detected, so they will keep a route while it is functional, even if a new shorter route is now available. AODV performs this link loss detection faster thanks to its hello mechanism whereas DYMO performs it only when it forwards a signalization packet, so AODV has a faster refresh rate than DYMO. The length of the routes illustrates the main interest of AANETs: around 80% of the packets were received after more than 1 hop. It means that the air to air relay capability of AANETs multiplies roughly by 5 the number of reachable aircraft.

CONCLUSION

Three well-known routing algorithms dedicated to MANET have been assessed in AANET simulations with actual aircraft trajectory replay. The results of these simulations have been discussed. The simulation results show that AODV performs better than BATMAN and DYMO in terms of reachability. Even though AODV has a bigger overhead cost than DYMO, the reachability gain offsets this weakness.

The changes introduced by DYMO do not benefit to the network performances in an AANET compared to AODV. BATMAN shows results similar to DYMO, but the load generated by it signalization traffic is so high that it will certainly be unacceptable with non-ideal links. BATMAN and DYMO are not well suited for AANETs.

AODV achieves a 85.6% normalized reachability in oceanic airspace, with an average number of hop per transmission of 3.97 The performances of AODV show that the concept of AANET is relevant as a complementary communication system for air-ground communication, but further improvements of the routing algorithms are required in order to reach a 100% normalized reachability. The hop count distribution also shows that the relaying capacity of AANETs bring as expected a great improvement to the coverage of this communication system compared to a cellular system with the same number of ground stations.

PERSPECTIVE

The results presented in this paper are based on an ideal link model. They must be reproduced with a realistic link layer, taking into account packet losses. We will study the behavior of AANETs with a link model based on RP-CDMA [START_REF] Mortimer | A mac protocol for multihop rpcdma ad-hoc wireless networks[END_REF], specifically tuned for AANETs.

In order to improve the reachability, we are also developing an innovative routing algorithm based on trajectory-based forwarding [START_REF] Niculescu | Trajectory based forwarding and its applications[END_REF]. It will use the actual aircraft density to compute a geographical route (a trajectory) along which the packet will be forwarded. This methods removes the strict dependency between a route and the relays : any aircraft along the trajectory can forward the packet, independently of their position when the trajectory is computed. This removes the problem of route renewal when the network topology changes. This innovative trajectory based routing protocol will make an opportunistic use of equipments already available aboard aircrafts such as GPS positioning and ADS-B traffic monitoring.

Figure 1 :

 1 Figure 1: Routing in an AANET (a route toward the ground station is represented by the arrows).

Figure 2 :

 2 Figure 2: Routes toward a single ground station obtained with AODV in an AANET (the ground station if figured by a black triangle).

Figure 3 :

 3 Figure 3: Aircraft density on the 2014-05-02, 8h to 9h time slot (greyscale). Ground stations are presented as black triangles.

Figure 4 :

 4 Figure 4: Average normalized reachability.

Figure 5 :

 5 Figure 5: Generated signalization volume.

Figure 6 :

 6 Figure 6: Hop count distribution.

Table 1 :

 1 Maximum delay for 95% of the received messages.

	Protocol name D 95
	AODV	100 ms
	BATMAN	100 ms
	DYMO	233 ms