# A Hybrid Routing Protocol for Underwater Acoustic Networks

Roberto Petroccia, João Alves

► To cite this version:

Roberto Petroccia, João Alves. A Hybrid Routing Protocol for Underwater Acoustic Networks. 17th Annual Mediterranean Ad Hoc Networking Workshop (Med-Hoc-Net 2018), Jun 2018, Capri Island, Italy. pp.94-101. [hal-01832535](https://hal-inriaHal)
# A Hybrid Routing Protocol for Underwater Acoustic Networks

Roberto Petroccia and João Alves

NATO STO Centre for Maritime Research and Experimentation, La Spezia, Italy
{roberto.petroccia,joao.alves}@cmre.nato.int

***Abstract***—This paper presents a new packet-forwarding mechanism for underwater acoustic networks. The solution, termed MPR-Light, combines the *modus operandi* of the Multi-Point Relay (MPR) protocol and of the Enhanced Flooding (EFlood), both described in [1]. MPR-Light aims at providing the robustness of a flooding solution in the presence of unreliable and asymmetric acoustic links, while reducing the network load and energy consumption at each node. No periodic control messages are transmitted by each data source or relay nodes. Any additional control data used to find the best relay towards the final destination is appended to regular data packets. Similarly to MPR, relay nodes are selected according to (recent) historical information considering different metrics, i.e. link quality, link liveliness and symmetry. When no information is available at a node, the EFlood approach is used. The performance of MPR-Light has been compared with that of MPR and EFlood during the CommsNet13 sea trial, organised by the NATO Centre for Maritime Research and Experimentation (CMRE) and conducted off the coast of the Palmaria island (La Spezia, Italy) in September 2013. A heterogeneous network of 12 nodes was deployed. Our results show that MPR-Light, using an hybrid strategy, is able to significantly reduce the overhead and energy consumption in the network while maintaining similar or better performance in terms of packet delivery ratio and end-to-end latency with respect to MPR and EFlood.

***Index Terms***—Underwater Acoustic Network, Routing, Flood-
ing, Multi-Point Relay, Hybrid Routing, MPR, MPR-Light.

## I. INTRODUCTION

*Underwater Acoustic Networks* (UANs) are an enabling technology in a wide spectrum of different collaborative scenarios that find application to science, security, and commercial activities. The scenarios of interest include (among others) environmental monitoring, prediction of and reaction to natural disasters, surveillance for defence applications and port safety, off-shore oil and gas, aquaculture, geological and oceanographic science [2], [3]. Most of these applications require coverage of large areas where nodes cannot directly communicate with each other and appropriate routes have to be found to connect a given source to the intended destination. Radio frequencies typically used over the air are not usable in practice under water, and optical signals are greatly attenuated. Acoustics are therefore the main technology used for underwater communications. However, acoustic communications in water are characterised by many challenges that are specific to the considered underwater environment: Long propagation delays, low bandwidth, sound speed variability, channel gain

fluctuations, and many other environmental impairments [4]. Moreover, rapidly varying conditions of the acoustic channel, coupled with self noise from the nodes (very commonly experienced when using moving platforms generating propulsion and flow noise) may give rise to time-varying link reliability and asymmetric links. This asymmetry is rarely encountered in terrestrial radio networks, but can be common and has severe impact in UANs.

Given all these challenges, the design of a routing protocol which is robust, energy-efficient and well adapted to the bandwidth constraints of the underwater channel is surely a challenging task. Various solutions have been proposed in the past aiming at selecting the best set of relay nodes to be used over a given link (see Section II). Depending on the selected approach, this relay set could be composed of a single node (typical of handshaking mechanisms), multiple nodes (multi-point relay solutions) or all the possible neighbour nodes (traditional flooding schemes). In the presence of unreliable and asymmetric acoustic links, higher robustness in packet delivery can be obtained when multiple (or all) neighbour nodes are used as relays. This usually comes at the price of increasing packet duplicates, incurring in a high energy consumption and usage of resources that poorly scale with the network size.

In this paper, we present a new distributed hybrid routing protocol (MPR-Light) for UANs, combining the multi-point relay strategy of the MPR protocol and the more robust flooding approach of EFlood. MPR-Light does not assume the presence of any special node in the network (e.g. common collection point: the sink) and is designed to work in any network configuration. It does not require the transmission of control messages to select the next hop relay(s) and it makes use of historical information to route packets around connectivity voids and shadow zones. Additional information is appended to regular data packets (slightly increasing the message size) to determine link quality, link liveliness and symmetry for the various neighbour nodes. When the network operation starts and no information is available, a more traditional flooding approach (EFlood) is used. After collecting the information piggybacked in the data packets, a subset of neighbours is selected to relay the messages using the same MPR metrics detailed in [1], thus reducing the network load and energy consumption at each node. The collected data is considered valid for a given time window, thus leaving the possibility for
MPR-Light to go back to the EFlood strategy if no “fresh”
data is received.

The performance of MPR-Light has been evaluated during
the CMRE CommsNet13 sea trial, measuring metrics such as
packet delivery ratio, end-to-end packet latency, introduced
overhead and energy consumption. CommsNet13 was con-
ducted off the coast of the Palmaria island (La Spezia, Italy)
in September 2013 with the deployment of a network of up
to 12 nodes, including both static and mobile assets. The
performance of MPR-Light has been compared to that of MPR
and EFlood.

Our results show that by mixing the usage of multi-point
relay and regular flooding strategies, MPR-Light is able to
obtain better packet delivery ratio performance with respect
to the other two approaches, while reducing the overhead and
energy consumption in the network. Additionally, MPR-Light
offers a stable and reliable solution which is able to scale to
scenarios with an increasing number of nodes, in the presence
of a heterogeneity of devices, i.e. bottom-moored, surface and
underwater nodes, either static and mobile.

The rest of the paper is organised as follows. Previous work
on underwater multi-hop routing is summarised in Section II.
In Section III we describe MPR-Light in detail. Section IV
illustrates experimental results. Finally, Section V concludes
the paper.

II. RELATED WORK

Different routing protocols for UANs have been presented
and discussed in the past [5], [6], [7]. We can divide most
of these solutions in two categories: 1) hop-by-hop and
2) flooding-based.

Hop-by-hop protocols are usually designed to reduce the
number of packets broadcasted in the network with respect
to the flooding-based approach. Handshaking mechanisms are
typically adopted to find the next hop relay and to tune the
parameters of the data exchange. Short control messages are
exchanged between the transmitting node and the possible
relay nodes to find the best available option, e.g. FBR [8],
CARP [9], SUN [10]. Although reducing the number of packet
broadcasts in the network, this class of protocols require the
presence of symmetric links over the paths connecting the
source node(s) to the destination node(s). Additionally, due
to this exchange of control information, these solutions can
impose long latency and less robust solutions. Protocols like
FBR and SUN are based on the assumption that if a link
is good to exchange short control messages, it will also be
good for data packets, even if data packets are usually much
longer and more prone to decoding errors. CARP tries to
overcome this problem using a power control mechanism to
select reliable links for both control and data messages. This
approach requires, however, a fine tuning of the transmission
power which is not available on many of the current commer-
cial acoustic modems. CARP also requires the presence of
symmetric links along the path towards the destination node.

Flooding-based protocols usually increase the robustness of
packet delivery and do not require the presence of symmetric

links. This comes at the price of increasing the number
of packets broadcasted in the network. Various strategies
have been investigated to reduce the number of acoustic
transmissions in water. These strategies usually assume the
knowledge of the position of the destination node in order to
control the packet flow towards the right area. Vector-Based
Forwarding (VBF) [11] routes packets only to nodes residing
in a constrained “pipe” of given width in the direction of
the common collection point (sink). The pipe surrounds a
virtual line (a vector) between the packet source node and
the sink. The efficiency of the protocol strictly depends on the
critical determination of the radius of the pipe. The protocol
presented in [12] enhanced the VBF approach by including
energy information in the relay selection mechanism, so to
extend the network lifetime. The performance of this protocol
still depends on the correct determination of the radius of the
forwarding pipe, and suffers from high overhead.

A different approach is presented in [13] where the *Direc-
tional Flooding-based Routing* (DFR) is described. Each node
decides whether to forward the packet or not, depending on
the angle formed by the sender, the forwarder and the final
destination. The decision is made by comparing this angle with
a reference angle carried by the packet. The varying conditions
of the underwater channel are addressed by changing the
reference angle on a hop-by-hop basis according to the link
quality. However, determining geographic information under
water can be difficult and it could require high cost/overhead.
To address this issue, some protocols have been designed to
use only partial geographic information. This is the case of
DBR, the *Depth Based Routing* protocol [14], where only
depth (distance from the surface<fnref n="1" />) is used to decide if a packet
should be forwarded or not. Each node that receives a data
packet forwards it only if its depth is less than that of the
sender. Before forwarding the data packet, a node holds it for a
time that depends on the difference between its own depth and
that of the sender. In particular, the larger the vertical distance,
the smaller the holding time, so that nodes that are closer to
the surface (i.e. closer to the sink) are the first to forward the
data. While holding, a node listens to the transmissions on
the channel. If it overhears that the packet that it is about to
broadcast is transmitted by another node, the node drops that
packet.

Similarly to DBR, HydroCast [16] and VAPR [17] use
node depth information to determine the forwarding decisions.
HydroCast tries to find a set of possible relays that maximise
“expected packet advance” [18], while limiting the number of
forwarding nodes to reduce redundant transmissions. VAPR
uses the same forwarding set selection algorithm of Hy-
droCast. In this case, however, nodes know their next-hop
neighbour towards the sink thanks to the surface reachability
information flooded from the sink via periodic beaconing.

All these protocols limit the selection of relay nodes to the
ones providing a positive advancement (i.e. distance reduction)

<footnote n="1">¹This information can be easily determined with greater accuracy using on-board sensors [15].</footnote>
towards the destination. This may incur in the possibility to
drop the packets at dead-end nodes, even if a stable path
between source and the destination exists, passing through
node(s) not providing such a positive advancement. Addi-
tionally, all the solutions presented so far are designed for
networks where there is a common collection point receiving
all the generated data and do not support the possibility to
route packets between any pair of nodes in the network. This
restricts the usage of these solutions to specific scenarios.

The Multi-Point Relay (MPR) protocol overcomes these limitations. MPR is a controlled flooding mechanism where nodes transmits additional control data to collect (recent) historical information on link quality and topology status. It can be used to forward data to any other node and it does not assume any preliminary information on the network. The additional information can be shared via periodic control messages or it can be piggybacked to regular data packets. By requiring the transmission of additional control information, MPR is mainly designed for scenarios where nodes periodically broadcast messages, e.g. telemetry and status information, that can carry the additional required data, thus avoiding the need for additional transmissions. When this is not the case and nodes have a low traffic load<fnref n="2" />, MPR would incur in the transmission of many dedicated control packets, thus resulting in an increased energy consumption at each node. Additionally, when short control messages are the primary means used to determine the link quality and topology status, wrong estimations about the impact on long data packets can be made.

Another protocol that does not require any preliminary knowledge about the network, with the possibility to deliver data to any intended destination is the common flooding protocol. When using this protocol, each node immediately re-transmits a received packet (unless it is a duplicate) without the need of any additional control message. Since each message can be re-transmitted once by any receiving node, the result is a large number of packet transmissions and possible collisions. EFlood [1] enhances the baseline flooding scheme by letting a node wait for a random time before forwarding the packet. This allows EFlood to reduce the probability of collision when multiple nodes forward the same packet but it still incurs in a large number of packet transmissions. Similarly to EFlood, the duplicate reduction flooding-based protocol (called Dflood) presented in [19] uses a backoff time window before forwarding a packet. This time window is continuously adapted when a duplicate is overheard and only a limited number of duplicates is allowed to be forwarded. Both the backoff time window and the maximum allowed number of duplicates are critical parameters and may compromise the ability of delivering packets if not adequately set.

Our proposed protocol, MPR-Light, combines the use of
MPR and EFlood by creating a controlled flooding mechanism
that does not require the use of dedicated control transmis-

sions. This hybrid approach does not assume any preliminary
knowledge about the network and it can be easily employed
in various scenarios and configurations.

III. PROTOCOL DESCRIPTION

In this section we provide the details on the three protocols considered: EFlood, MPR and MPR-Light.

**EFlood:** Flooding is a simple routing solution where every new incoming packet is broadcasted in the network. When a node identifies an incoming packet as one it already forwarded, that packet is discarded. EFlood enhances the common flooding solution with a desynchronisation mechanism to avoid that several packets forwarded at the same time result in collisions at the receiver. If several nodes immediately forward the same incoming packet there is a high probability to incur in a packet collision at the receiver. This is especially true for underwater acoustic networks where the bit rates of the communication devices are low and the packet transmission time and data collision window can be long. For this reason, when a node receives a packet it waits for a random time period before passing it to the MAC layer. This random time depends on the network topology, on the used MAC solution and on the packet transmission delay<fnref n="3" />. Additional delays may be introduced by the MAC, e.g. when the channel is found busy or an error is detected and multiple transmission attempts are performed. Our tests have shown that EFlood remarkably outperforms common flooding. EFlood is particularly robust and reliable for small-scale networks or when a short collision window for the transmitted packets is expected. However, being a flooding-based solution, it introduces a high overhead which rapidly increases when more nodes are added to the network.

**Multi-Point Relay (MPR):** It is based on the periodic dissemination of node status (static or mobile) and neighbour information (who are the neighbours, link symmetry, status of neighbours) by all participants in the network. Such information is then used to select the best relay(s) for a packet that needs to be routed. This restricted flooding approach minimises control data exchanges and does not require a negotiation process. MPR does not rely on power control, channel estimation or signal-to-noise ratio calculations (which are not supported in a standardised way by acoustic modem manufacturers).

Nodes advertise themselves periodically in the network, publishing a list of their neighbours, if a symmetric link to these neighbours exists (i.e. if they find themselves in the neighbour list of a neighbour) and if they are static or mobile. This advertisement is done during normal message transmissions by appending the relevant neighbourhood information to the packets. In case there is no data to output, a simple advertisement message (called HELLO packet) is generated containing the required information. Each node is required to periodically inform its neighbours by transmitting a packet (data or HELLO) within a given window (advertisement time).

<footnote n="2">²This could be the case for environmental monitoring applications where few transmissions per day may be required.</footnote>

<footnote n="3">³This random time is not needed when a Time Division Multiple Access strategy is used at the MAC layer.</footnote>
If $x$ is a node in the network, we call $N_1(x)$ the list of its neighbours, i.e. all the nodes from which $x$ correctly received at least one packet. All the neighbours of neighbours of $x$, which are not members of $N_1(x)$, are called two-hop neighbours and belong to the set $N_2(x)$. If $x$ does not receive any data or HELLO packets from a neighbour $n$ within a given window (expiration time), $x$ updates its lists by removing all the information related to node $n$.

When a node $x$ has a packet to send or relay, it checks if the final destination of the packet is in $N_1(x)$. If this is the case, $x$ transmits the packet to its neighbour node, otherwise it analyses the neighbourhood status to find suitable relays and ranks neighbour nodes according to a metric based on:

- **Connectivity $C(n)$**: Number of connections shown by neighbour node $n$ in $N_1(x)$. It is used as a first indication of a good candidate for message dissemination;

- **Persistence $P(n)$**: Measure of liveliness and/or reliability of the link with neighbour $n$. It is computed based on a historical analysis of the presence of $n$ in $N_1(x)$. Additional physical parameters (like type of node, speed, etc.), if available, can be considered in the computation.

- **Quality $Q(n)$**: Quality of the physical link with neighbour node $n$. This is a placeholder for incorporating low level measurements of the channel provided by the equipment manufacturer.

- **Symmetry $S(n)$**: Binary value to identify a symmetric link. $S(n)$ is 1 if $x$ is listed in the neighbour list on $n$ and vice versa. More granularity in the symmetry value could be envisioned for future implementations.

The node persistence $P$ is computed based on the type of nodes (static or mobile) involved. The rationale is that there should be a lower probability to experience changes in the quality of the link between two static nodes with respect to the case where one or both nodes of the link are mobile.

The merit function $M$ for each node $n$ is then defined as:

$$M(n) = S(n)(K_C C(n) + K_P P(n) + K_Q Q(n)) \quad (1)$$

where $K_C$, $K_P$ and $K_Q$ are weighting factors for connectivity, persistence and quality, respectively.

After ranking the neighbour nodes, $x$ picks the highest scoring one and checks if it guarantees coverage of all the nodes in $N_2(x)$. If that is the case, the highest ranked node will be the only relay. If not, additional relays need to be selected. The list of relay nodes will be expanded with the next highest ranked node that shows connections in $N_2(x)$ not guaranteed by the currently selected relays. The relay selection process continues until coverage of all $N_2(x)$ is guaranteed. If no candidates are available, $x$ stores the packet and forwards it as soon as a possible node relay is found.

Receptions are promiscuous and all traffic is used to update the evaluation parameters. MPR is also designed to work in Delay Tolerant Network (DTN) scenarios storing the packets when a reliable path is not available and trying to forward it when updated and more favourable topology information is received.

Making use of both control and data message to estimate link quality, MPR is based on the assumption that if a link is good to exchange short control messages, it will also be good for data packets. Different metrics should be derived for control and data messages to ensure a better relay(s) selection.

**MPR-Light**: It uses the same information and ranking strategy of MPR but it does not make use of dedicated control messages. The relevant neighbourhood information is only transmitted together with data packets<fnref n="4" />. To cope with possible changes in the network topology (e.g node mobility) and link quality (e.g environmental changes over time), the information received by each node is considered valid only for a given time window (expiration time). After this time the information about that node is no longer considered valid. Additionally, to give higher priority to fresh data, each node monitors the packets received from its neighbours within a given window (inactivity time), which works similarly to the advertisement time. When no data is received from a node $x$ within the inactivity window, the persistence of $x$ is reduced following the same rules of MPR. Similarly, the persistence is increased when a new packets arrives.

Differently from MPR, when no information is available about the neighbour nodes or the merit function fails to obtain any candidate relay nodes, instead of waiting more favourable topology information, MPR-Light sends the message in broadcast to be forwarded by any receiving nodes. Due to link asymmetry, there could be neighbour nodes of $x$ that are not in $N_1(x)$ and $N_2(x)$ but which could correctly receive form $x$ and forward the data.

Although MPR-Light does not require the transmission of control messages, it has been designed to provide that option to the user for scenarios where there are nodes that need to advertise themselves without the need to generate any data message. This is typically the case of a sink node. Sink nodes are usually more capable devices, with larger storage, energy and computational power that are deployed in the network to collect the data from others nodes (typically remote sensors) without generating data on their own. Each sink needs therefore to be able to advertise itself in order to let the others known about its existence in the network.

In such configuration, MPR-Light can be used by enabling the transmission of control messages at the sink. The advertisement time is used to define the periodicity of these transmissions<fnref n="5" />.

## IV. EVALUATION AND COMPARISON

The three protocols have been implemented using the Sapienza University Networking framework for underwater Simulation Emulation and real-life Testing (SUNSET) [20], which is available for freely download.

<footnote n="4">⁴We assume that all data packets have similar size, not considering data packets of different lengths. This can be accomplished by combining together short data messages or by employing a fragmentation solution.</footnote>

<footnote n="5">⁵The typical larger energy budget of the sink node mitigates the effect of the additional energy consumption introduced by the control packet transmission.</footnote>
## A. Performance metrics

Key metrics were evaluated to compare the performance of the routing protocols. We have investigated reliability and robustness in delivering data to the sink, together with the additional delays and overhead introduced in the communications. The following metrics were used to assess the system performance:

1) *Packet delivery ratio (PDR)*, defined as the ratio between packets correctly delivered to the destination nodes (without considering duplicated packets<fnref n="6" />) and the packets generated in the network.

2) *End-to-end latency*, defined as the time between packet generation and the time when it is correctly received by the destination node.

3) *Route length*, defined as the number of hops needed to deliver a new data packet to the intended destination.

4) *Number of relays per generated packet*, defined as the ratio between the number of nodes forwarding a data packets and the number of packets generated in the network. It provides a measure of how many nodes are trying to forward the generated data packet.

5) *Overhead per bit*, defined as the ratio between the total number of bits (control and data) transmitted in the network and the number of bits correctly delivered to the destination node. When summing the delivered bits, duplicated packets are ignored. This metric provides a measure of how many bits have to be pushed into the channel to correctly deliver one bit of data to the sink.

6) *Energy per bit*, defined as the ratio between the energy consumed by the network and the number of bits correctly delivered to the final destination. The energy consumed in the network is obtained considering the transmission/reception of all the messages (including copies of the same message). When computing the delivered bits, the reception of duplicated packets is ignored.

## B. Scenarios and settings

The CommsNet13 sea trial was organised by CMRE and experiments were conducted from September 9 to September 22, 2013 off the coast of the Palmaria island, in the South-West part of the gulf of La Spezia, Italy. Twelve nodes, static and mobile, were deployed as shown in Figure 1a, while Figure 1b shows the sound speed profile collected in the morning of September 20, 2013. It is a typical down-refracting summer profile and similar measurements were collected during the various days of the trial.

The configuration of the nodes was as follows.

* **LOON.** The Littoral Ocean Observatory Network, consisting of 4 bottom-mounted tripods with acoustic modems, all cabled to shore (nodes with IDs 1 through 4). A PC on the shore station was used to control the modem operations. Each modem is deployed at 1.5 m from the sea floor, at a depth of ~ 28 m.

* **Gateway.** One communications gateway buoy, temporarily moored with recoverable mooring tackle (node 5). Its acoustic modem was deployed at a depth of ~ 5 m.

* **Alliance.** The NATO Research Vessel Alliance working as a static node with an acoustic modem deployed over board at a depth of ~ 5 m (node 6).

* **WaveGlider.** One WaveGlider surface vehicle with communications gateway payload (node 9). Its acoustic modem was deployed at a depth of ~ 5 m.

* **eFolaga.** Three eFolaga [21] Autonomous Underwater Vehicles (AUVs) with communications payload (nodes 7, 8 and 10).

* **Manta.** Two Manta portable systems [22], deployed from Rigid-Hull Inflatable Boats (RHIBs), to temporarily increase the scale of the network (nodes 11 and 12). For each Manta, the acoustic modem was deployed at a depth of ~ 5 – 10 m.

All nodes were equipped with Evologics S2CR 18/34 acoustic modems. The site where the underwater network was deployed is a broad plateau approximately 30 m under sea surface. The seabed in this area is predominantly mud. It is located along the major current direction between potential sources of pollution to the South and the marine protected areas to the North. Therefore, the position of the network is ideal for environmental monitoring applications.

The performance of the three protocols was compared considering three different setups (referred below as Experiment 1, Experiment 2 and Experiment 3) where 5, 9 and 12 nodes were deployed, respectively.

During the field experiments we have focused mainly on the case where all the nodes had to report data to a control station. The task of this control station was to monitor the status of the network and identify possible misbehaviour or errors on the nodes. Node 1, cabled to the shore station and accessible via radio, was selected as the control node, while all other devices were generating and relaying data. Table I shows the nodes used for the three different experiments and the day when the tests for each specific scenario were conducted.

<table><caption>Table I: Nodes and date information for the three different experiments.</caption><thead><tr><td>Experiment</td><td>Node IDs</td><td>Date</td></tr></thead><tbody><tr><td>1</td><td>1 – 5</td><td>September 18</td></tr><tr><td>2</td><td>1 – 9</td><td>September 20</td></tr><tr><td>3</td><td>1 – 12</td><td>September 21</td></tr></tbody></table>

The generated traffic followed a Constant Bit Rate (CBR) pattern with a packet generated by each source node every 40 s, 80 s and 110 s for the three setups, thus resulting on average in one packet generated in the network every 10 s. For all protocols, the acoustic channel reservation was implemented with a Carrier Sensing Multiple Access (CSMA) scheme [23] without acknowledgement. The CSMA header contains the packet type along with the sender and destination addresses. The length of the header is 3 B. The additional

<footnote n="6">⁶Duplicated messages could result from flooding and from the use of multiple relays at each node. Multiple copies of the same messages could be in fact delivered to the final destination, following different routes.</footnote>
<figure><img src="image_1.png" /><figcaption>Figure 1: Setting of the CommsNet13 experiments.</figcaption></figure>

control information added by MPR and MPR-Light to each data packet is 3 B. The data payload size was 47 B resulting in a full data packet size of 50 B for EFlood (including CSMA header) and 53 B for MPR and MPR-Light (including CSMA header and protocol control information). The length of the control packet transmitted by all nodes when using MPR and by node 1 when using MPR-Light was 6 B (CSMA header and protocol control information). We used the maximum bit rate offered by the Evologics S2CR 18/34 acoustic modem, i.e. 480 bps, when bypassing the built-in medium access control mechanism. All experiments were performed at the low-medium transmission power level, resulting in a power consumption of 8 W during transmissions. Power consumption for reception was 0.5 W.

### C. Link quality information

Before presenting the results collected at sea, it is worth to briefly discuss the link quality experienced during CommNet13 since this has a directly impact on the protocol performance. Figure 2 presents the PDR over the various links for the Experiment 2 scenario. Each entry (i, j) of the matrix displays the ratio between the packets transmitted by node with ID i and the ones correctly received at node with ID j. Errors in the delivery of these messages are only due to the acoustic channel since no concurrent transmissions were performed. Two relevant packet sizes were considered for link analysis: 6 B for control messages (on the left) and 50 B for data messages (on the right). This data set was collected on September 20, 2013, before performing the routing tests. Similar link quality performance was experienced also during the other days.

The links have been categorised in 5 classes. A colour has

been assigned to each class depending on the PDR value, moving from green for high PDR to red for low PDR. It can be immediately seen that a lower link quality is experienced for longer data packets with respect to shorter ones. This validates the fact that for this network scenario the usage of short control messages to select the best next hop relay could lead to less accurate or wrong decisions. Additionally, the presence of highly asymmetric links can be seen. A very evident example is represented by node 2 for data messages. This node is able to effectively deliver data messages to nodes 4-8 but it only has a good reception link with nodes 1 and 8. Looking at the control data, instead, node 2 has much better incoming links, leading to the selection of this node as a good relay, at the price of an incorrect delivery of many data messages. When looking at the data packets, asymmetric links can be noted for nodes 3, 6, 7 and 8.

### D. At sea results

This Section reports about the results collected at sea during the CommsNet13 trial for the three scenarios shown in Table I. Table II shows the results obtained for Experiment 1 where 5 nodes (ID 1-5) were used. The tests for this scenario were conducted on September 18, 2013. MPR-Light outperforms both MPR and EFlood in terms of PDR, end-to-end latency, overhead per bit and energy per bit. In this scenario, nodes 2, 3 and 4 have a poor outgoing link to node 1 for data, and they should use node 5 as relay. Since MPR takes decisions based also on the link quality for the control messages, in many cases node 2 sends the data packet directly to node 1, instead of using node 5 as relay. This results in a lower PDR for MPR with respect to the other protocols. Having a very limited number of possible relay nodes, EFlood suffers more
<figure><img src="image_2.png" /><figcaption>Figure 2: Link quality information during CommsNet13.</figcaption></figure>

<table><caption>Table II: CommsNet13 results: Experiment 1.</caption><thead><tr><th>Metric</th><th>MPR-Light</th><th>MPR</th><th>EFlood</th></tr></thead><tbody><tr><td>Packet delivery ratio</td><td>0.85</td><td>0.74</td><td>0.81</td></tr><tr><td>End-to-end latency [s]</td><td>5.0</td><td>5.5</td><td>5.1</td></tr><tr><td>Route length [hops]</td><td>1.67</td><td>1.6</td><td>1.7</td></tr><tr><td>Max Route length [hops]</td><td>2</td><td>3</td><td>3</td></tr><tr><td>Relay nodes</td><td>0.9</td><td>0.65</td><td>2.1</td></tr><tr><td>Overhead per bit</td><td>1.5</td><td>2.0</td><td>3.8</td></tr><tr><td>Energy per bit [J/b]</td><td>0.03</td><td>0.04</td><td>0.07</td></tr></tbody></table>

for any collision when forwarding the data, leading also to slightly longer routes. When using MPR-Light, each node uses broadcast transmissions only for the very first packet. As soon as metrics on the neighbours are collected, node 5 is used as relay and unicast transmissions are triggered. By reducing the number of data packet collisions and not waiting for better information before forwarding the packets, MPR-Light is able to obtain shorter delays in delivering the intended data with respect to the other protocols. MPR results in the highest end-to-end delays since it employs control messages, increasing the occupancy of the acoustic channel, and it holds the data packets without forwarding until favourable topology information is collected. As expected, when each node is transmitting additional control messages (MPR) or multiple data packet duplicates (EFlood) higher overhead per bit and higher energy consumption is experienced. This is particularly evident in the case of EFlood, since data packets are longer than control packets and more nodes are used as relays.

Table III shows the results for Experiment 2 where 9 nodes (IDs 1-9) were deployed. The tests for this scenario were conducted on September 20, 2013. Similar trends to the previous scenario can be noticed. When increasing the number of nodes and extending the area of operations, more packets are generated and relayed in the network, thus resulting in a larger number of relay nodes and longer routes with respect to Experiment 1 for all the considered protocols. Being provided with more reliable links for data packets, MPR is able to perform better relay selection obtaining a PDR similar to the one of MPR-Light and EFlood. When using MPR, in 2%

of the cases multicast transmissions are used, while the rest are unicast transmissions. When using MPR-Light instead, 5% of the transmissions are broadcast (especially the very first transmission at each node), 7% are multicast and 88% are unicast. MPR-Light results, therefore, in a larger use of relay nodes and longer routes with respect to MPR. This also explains the similar performance of these two protocols in terms of overhead per bit and energy per bit consumption, even though in MPR-Light no control messages are transmitted by the various data sources. EFlood, making use of more than twice the relay nodes used by the other protocols, results in the highest overhead and energy consumption for similar PDR and end-to-end latency performance.

<table><caption>Table III: CommsNet13 results: Experiment 2.</caption><thead><tr><th>Metric</th><th>MPR-Light</th><th>MPR</th><th>EFlood</th></tr></thead><tbody><tr><td>Packet delivery ratio</td><td>0.82</td><td>0.78</td><td>0.80</td></tr><tr><td>End-to-end latency [s]</td><td>8.2</td><td>9.3</td><td>8.7</td></tr><tr><td>Route length [hops]</td><td>1.75</td><td>1.55</td><td>2.1</td></tr><tr><td>Max Route length [hops]</td><td>3</td><td>4</td><td>4</td></tr><tr><td>Relay nodes</td><td>1.7</td><td>1.4</td><td>3.8</td></tr><tr><td>Overhead per bit</td><td>3.4</td><td>3.4</td><td>7.4</td></tr><tr><td>Energy per bit [J/b]</td><td>0.07</td><td>0.07</td><td>0.15</td></tr></tbody></table>

Table IV reports the results for Experiment 3 where 12 nodes (IDs 1-12) were deployed. The tests for this scenario were conducted on September 21, 2013. In this case three more nodes were added to the same network area used for Experiment 2, thus increasing the network density and the average number of neighbours for each node. More neighbours means more packet duplicates transmitted in the network by EFlood, as it can be noticed by looking at the average number of relay nodes. More transmissions lead to more collisions, longer routes, longer delays and a higher overhead and energy consumption. Although EFlood proves to be a robust solution in terms of packet delivery, when the network size increases the usage of resources may get less affordable. MPR-Light, being more reactive and avoiding the use of control messages at each source node, is able to outperform again the other
protocols. The usage of this hybrid scheme combines the robustness provided by EFlood (same PDR) with the reduced duplicate messages of MPR (more than three times lower than EFlood). Additionally, performing all the relay node selections based on the actual link quality experienced for data transmissions results in more stable and reliable decisions. This allows MPR-Light to obtain a end-to-end latency that is 16% lower than MPR and 15% lower than EFlood.

<table><caption>Table IV: CommsNet13 results: Experiment 3.</caption><thead><tr><th>Metric</th><th>MPR-Light</th><th>MPR</th><th>EFlood</th></tr></thead><tbody><tr><td>Packet delivery ratio</td><td>0.84</td><td>0.79</td><td>0.84</td></tr><tr><td>End-to-end latency [s]</td><td>9.6</td><td>11.4</td><td>11.2</td></tr><tr><td>Route length [hops]</td><td>1.76</td><td>1.58</td><td>2.3</td></tr><tr><td>Max Route length [hops]</td><td>3</td><td>4</td><td>5</td></tr><tr><td>Relay nodes</td><td>1.9</td><td>1.5</td><td>6.4</td></tr><tr><td>Overhead per bit</td><td>3.2</td><td>3.4</td><td>10.4</td></tr><tr><td>Energy per bit [J/b]</td><td>0.06</td><td>0.07</td><td>0.22</td></tr></tbody></table>

## V. CONCLUSIONS

In this paper we presented MPR-Light, an efficient new hybrid routing protocol for UANs. MPR-Light combines the robustness of the EFlood protocol with the capability of MPR to reduce the number of duplicate packets transmitted in the network. Similarly to MPR, in MPR-Light data forwarding exploits link quality information, leading to the selection of nodes that exhibit a history of successful transmissions towards the final destination. MPR-Light does not require the transmission of periodic control messages. It can be used to forward data to any other node of the network and it does not assume any preliminary information on the network. MPR-Light was compared to MPR and EFlood in terms of performance in key selected metrics. Data for the comparison was collected during CMRE CommsNet13 sea trial where a heterogeneous network of up to 12 nodes was deployed, including static and mobile assets. Our results show that MPR-Light effectively outperforms the other two protocols when increasing the network size and enlarging the operational area. For all the considered scenarios, MPR-Light was able to obtain a higher packet delivery ratio, a shorter end-to-end latency and a lower energy per bit consumption with respect to both MPR and EFlood.

## ACKNOWLEDGEMENTS

This work was supported by the NATO Allied Command Transformation (ACT) Future Solutions Branch under the Autonomous Security Network Programme and was made possible using data from the CMRE CommsNet13 sea trial. The authors would like to thank the Captain and crew of the NRV Alliance for the excellent support during the experiments.

## REFERENCES

[1] J. Alves, R. Petroccia, and J. R. Potter, "MPR: multi-point relay protocol for underwater acoustic networks," in Proceedings of the 9th ACM International Conference on Underwater Networks and Systems, ser. WUWNet'14, Rome, Italy, November 12-14 2014.

[2] N. Meratnia, P. J. M. Havinga, P. Casari, C. Petrioli, K. Grythe, T. Husoy, and M. Zorzi, "CLAM—Collaborative embedded networks for submarine surveillance: An overview," in Proceedings of IEEE/OES OCEANS 2011, Santander, Spain, June 6-9 2011, pp. 1-4.

[3] J. Heidemann, M. Stojanovic, and M. Zorzi, "Underwater sensor networks: Applications, advances, and challenges," Royal Society, vol. 370, no. 1958, pp. 158-175, May 2012.

[4] M. Stojanovic and J. Preisig, "Underwater acoustic communication channels: Propagation models and statistical characterization," IEEE Communications Magazine, vol. 47, no. 1, pp. 84-89, January 2009.

[5] P. Casari and M. Zorzi, "Protocol design issues in underwater acoustic networks," Elsevier Computer Communications, vol. 34, no. 17, pp. 2013-2025, November 2011.

[6] T. Melodia, H. Khulandjian, L.-C. Kuo, and E. Demirors, "Advances in underwater acoustic networking," in Mobile Ad Hoc Networking: Cutting Edge Directions, S. Basagni, M. Conti, S. Giordano, and I. Stojmenovic, Eds. Hoboken, NJ: John Wiley & Sons, Inc., March 5 2013, ch. 23, pp. 804-852.

[7] N. Li, J.-F. Martínez, J. M. Meneses Chaus, and M. Eckert, "A survey on underwater acoustic sensor network routing protocols," Sensors, vol. 16, no. 3, p. 414, March 2016.

[8] J. M. Jornet, M. Stojanovic, and M. Zorzi, "Focused beam routing protocol for underwater acoustic networks," in Proceedings of ACM WUWNet 2008, San Francisco, CA, September 15 2008, pp. 75-82.

[9] S. Basagni, C. Petrioli, R. Petroccia, and D. Spaccini, "CARP: A Channel-aware Routing Protocol for Underwater Acoustic Wireless Networks," Ad Hoc Networks, vol. 34, pp. 92-104, 2015.

[10] G. Toso, R. Masiero, P. Casari, O. Kebkal, M. Komar, and M. Zorzi, "Field experiments for dynamic source routing: S2C EvoLogics modems run the SUN protocol using the DESERT underwater libraries," in Proceedings of MTS/IEEE OCEANS 2012, 2012, pp. 1-10.

[11] P. Xie, J. H. Cui, and L. Lao, "VBF: Vector-based forwarding protocol for underwater sensor networks," in Proceedings of Networking, Coimbra, Portugal, May 2006, pp. 178-181.

[12] X. Xiao, X. P. Ji, G. Yang, and Y. P. Cong, "LE-VBF: Lifetime-extended vector-based forwarding routing," in Proceedings of CSSS 2012, Nanjing, China, August 2012, pp. 1201-1203.

[13] D. Shin, D. Hwang, and D. Kim, "DFR: An efficient directional flooding-based routing protocol in underwater sensor networks," Wireless Communications and Mobile Computing, vol. 12, no. 17, pp. 1517-1527, December 2012.

[14] H. Yan, Z. J. Shi, and J.-H. Cui, "DBR: Depth-based routing for underwater sensor networks," in Proceedings of IFIP-TC6 NETWORKING 2008, Singapore, May 5-9 2008, pp. 72-86.

[15] B. Jalving, "Depth accuracy in seabed mapping with underwater vehicles," in Proceedings of MTS/IEEE OCEANS 1999, Seattle, WA, September 13-16 1999, pp. 973-978.

[16] U. Lee, P. Wang, Y. Noh, L. Vieira, M. Gerla, and J.-H. Cui, "Pressure routing for underwater sensor networks," in Proceedings of IEEE INFOCOM 2010, San Diego, CA, March 15-19 2010, pp. 1-9.

[17] Y. Noh, U. Lee, P. Wang, B. S. C. Choi, and M. Gerla, "VAPR: Void-aware pressure routing for underwater sensor networks," IEEE Transactions on Mobile Computing, vol. 12, no. 5, pp. 895-908, 2013.

[18] K. Zeng, W. Lou, J. Yang, and D. R. Brown, "On geographic collaborative forwarding in wireless ad hoc and sensor networks," in Proceedings of WASA 2007, Washington, DC, 2007, pp. 11-18.

[19] R. Otnes and S. Haavik, "Duplicate reduction with adaptive backoff for a flooding-based underwater network protocol," in Proceedings of MTS/IEEE OCEANS 2013, Bergen, Norway, June, 10-13 2013.

[20] SENSES Lab, "SUNSET: Sapienza university networking framework for underwater simulation, emulation and real-life testing," [Online]. Available: http://reti.dsi.uniroma1.it/UWSN_Group/index.php?page=sunset

[21] Graaltech, "Folaga." [Online]. Available: http://www.graaltech.it/en/index.php

[22] LSTS, University of Porto, "Manta communications gateway," http://lsts.fe.up.pt/vehicles/manta

[23] S. Basagni, C. Petrioli, R. Petroccia, and M. Stojanovic, "Optimized packet size selection in underwater WSN communications," IEEE Journal of Oceanic Engineering, vol. 37, no. 3, pp. 321-337, July 2012.