Abstract
Abstract-Underwater acoustic networks are envisaged to be the enabling technology for oceanographic data collection, pollution monitoring, offshore exploration and tactical surveillance applications. Unique characteristics of underwater acoustic channels such as large propagation delays and high bit error rates pose a challenge to designing reliable and efficient communication protocols. In this paper, we propose an opportunistic acknowledgement scheme suited for Stop and Wait ARQ protocols and demonstrate using simulations that it achieves better latency and energy efficiency than traditional non-opportunistic schemes for both one and two-dimensional multi-hop acoustic channels.
*Center for Telecommunications Value-chain Research
Trinity College Dublin (Republic of Ireland) tNetwork Technology Department, Institute for Infocomm Research (Singapore) Email: {audreyberger@example.org, audreyberger@example.org and audreyberger@example.org}
*Center for Telecommunications Value-chain Research
Abstract-Underwater acoustic networks are envisaged to be the enabling technology for oceanographic data collection, pollution monitoring, offshore exploration and tactical surveillance applications. Unique characteristics of underwater acoustic channels such as large propagation delays and high bit error rates pose a challenge to designing reliable and efficient communication protocols. In this paper, we propose an opportunistic acknowledgement scheme suited for Stop and Wait ARQ protocols and demonstrate using simulations that it achieves better latency and energy efficiency than traditional non-opportunistic schemes for both one and two-dimensional multi-hop acoustic channels.
I. INTRODUCTION
Many applications have been envisaged for underwater sensor networks, including seismic monitoring, tactical surveillance and equipment monitoring and fault detection. To realize these applications, we may borrow many design principles and tools from ongoing, ground-based terrestrial sensor research. Acoustic communication is a promising candidate for underwater communication since radio is not suitable for underwater usage because of extremely limited propagation. However, there exist some fundamental differences between the radio and acoustic media, e.g., (a) long and variable propagation delay and (b) high and variable bit error rate (BER) in the latter that pose research challenges in underwater sensor networking [1] , [2] .
I. INTRODUCTION
In a typical underwater sensor network, sensor nodes are interconnected via wireless links to one or more underwater sinks that are responsible for reliably relaying data to a surface station. While direct communication between sensor and sink nodes (long range, high power) is simple, multi-hop (short-range, low power) communication using complex protocols may be necessary, for example, in military surveillance applications, where operational covertness and low power consumption are critical requirements.
I. INTRODUCTION
To establish reliable multi-hop communication, an automatic repeat request (ARQ) procedure is required to manage the retransmission of erroneously received / lost data packets. Since current acoustic modem technology typically supports half-duplex mode, the method of choice for current ARQ implementations is the simple Stop and Wait (S&W) protocol where each transmitted packet has to be acknowledged before the next packet can be transmitted. This can be simply achieved by explicitly transmitting an acknowledgement packet (typically of much smaller size than data packet) per successfully received data packet in a single-hop link.
I. INTRODUCTION
However, in a multi-hop channel, due to the broadcast nature of the medium, if a node transmits a packet and hears its next-hop neighbour transmitting it forward, it is an implicit acknowledgement that the packet has been successfully received by its neighbour, hence nullifying the need for explicit acknowledgement. While this may be more efficient (e.g. in terms of bits transmitted per data packet and/or waiting time for acknowledgements) than explicit acknowledgement in terrestrial wireless links with very low BER, it may not be so for acoustic links with substantially higher BER. In addition, while acknowledgement may be implemented on a per-hop or end-to-end basis, the former is expected to be more efficient for high BER acoustic links.
I. INTRODUCTION
Hence, in this paper, we propose a per-hop hybrid implicit/explicit acknowledgement scheme for S&W ARQ in a multi-hop acoustic channel, and demonstrate its efficacy in one-and two-dimensional architectures suitable for long range, underwater surveillance applications.
II. RELATED WORK
Variants of S&W have been proposed [3] , [4] , [5] , [6] for single-hop communication links to improve its efficiency by transmitting blocks of packets, rather than a single packet, thus making better utilisation of the time spent in waiting for the acknowledgements. However, to the best of our knowledge, ARQ mechanisms for multi-hop communication is much less studied [7] , [8] .
II. RELATED WORK
Recently, in [9] , the author conducted a statistical analysis of protocol efficiency for a class of S&W protocols, leading to an optimal packet size in terms of hop-length, bit rate and expected BER under typical underwater channels. As in [3] , [4] , [5] , [6] , this work considers S&W schemes based on transmitting groups of packets for which selective acknowledgements are generated. A similar analysis was conducted in [10] , which additionally accounted for cross-layer interactions with medium access control layers and forward error correction. However, the above analyses were conducted over single-hop acoustic links.
II. RELATED WORK
On the other hand, multi-hop end-to-end ARQ (e2e-ARQ) concepts (as opposed to S&W which is a per-hop (PH-ARQ) mechanism) were proposed recently in [7] , [8] primarily to handle node mobility in beyond 3G terrestrial access networks. An e2e RelayARQ protocol is proposed in [7] that allows relay or intermediate nodes to seamlessly "leave and join" without breaking the end-to-end connection by maintaining a common protocol state between all nodes. A multi-hop ARQ mechanism (M-ARQ) is proposed in [8] by coupling a PH-ARQ protocol with an e2e-ARQ. Although e2e-ARQ protocols may perform better in terms of reliability and efficiency than PH-ARQ, the added complexity may not be suited for implementation in underwater networks comprising energystarved sensor nodes. In addition, node mobility may not be a critical issue in underwater networks. Therefore, we focus our efforts on devising a S&W protocol suited for multi-hop communication in underwater networks. Consider an n-hop acoustic channel comprising a source node, sink node and n-I relay nodes as shown in Fig. 1(a) . One of the distinguishing features of underwater acoustic communication is spatially-varying channels, which is characterized here by the BER along each hop j, pj.
II. RELATED WORK
When a packet of b bits is transmitted over hop j, the corresponding packet error probability pj(b), is:
II. RELATED WORK
The time required for this packet to arrive at its intended recipient node (either node j-1 or j+1) comprises the transmission delay t = bir and the propagation delay, tp = llc, where r is the transmission rate of the channel, I is the hop-length (m) and c is the speed of sound (m/s). We consider two types of packets in this study, namely data packets of bD bits and acknowledgement (ACK) packets of bA (<< bD) bits each, with transmission times given by tD = bDIr and tA = bAir respectively.
B. Stop and Wait (S&W) ARQ
With S&W ARQ, the transmitter sends a packet and waits for the acknowledgment. Once it arrives, the transmitter moves on to a new packet; otherwise, if it does not arrive within a pre-specified duration, called the time-out, the packet is retransmitted. Due to the high BER of acoustic channels, the acknowledgement may be lost and this will trigger an unnecessary retransmission after the time-out. To reduce unnecessary transmission (hence, energy consumption) of data packets which have already been received, we apply the following rule:
B. Stop and Wait (S&W) ARQ
Rule 1: Whenever a relay node j receives a packet from node j-1, it transmits an ACK packet if its previous data transmission is already acknowledged. On the other hand, (non-relay) node 1 (n+1) only transmits data (ACK) packets.
B. Stop and Wait (S&W) ARQ
The design of the acknowledgement procedure is important since, in addition to energy-efficiency, it also determines the latency-efficiency of the ARQ mechanism, where a longer waiting time before the next packet can be transmitted indicates lower efficiency. The acknowledgement procedure can be done implicitly through the data packet itself or explicitly through an ACK packet. These mechanisms will be described in the subsequent sections.
B. Stop and Wait (S&W) ARQ
1) Implicit Acknowledgement (IMP): Consider the transmission of a data packet (bD bits) over hop j from node j to node j+1. Since the transmission is isotropic, this packet may also be received at node j-I and serve as an implicit ACK for its transmission. The corresponding packet error probability over hop j-I (or probability of unsuccessful acknowledgment for node j-1's transmission) is:
B. Stop and Wait (S&W) ARQ
If node j-1 is not acknowledged after a time-out interval, TO IMp=2(tp+tD), it retransmits the data packet. We denote this ARQ scheme by IMP.
B. Stop and Wait (S&W) ARQ
2) Explicit Acknowledgement (EXP): Since acoustic channels are characterized by high BER, a substantial proportion of implicit ACK packets may be erroneously transmitted, triggering retransmission of data packets that consumes energy and hence should be minimized. One way to achieve this is to define an explicit ACK protocol (EXP) that piggybacks the ACK packet to each data packet. In this way, the corresponding probability of unsuccessful acknowledgment for node j-1's transmission is reduced to:
B. Stop and Wait (S&W) ARQ
Pj-1(bA) = 1 (1 _ pj_ )bA. However, the corresponding time-out interval is increased to TO,EXP=2(tp + tD + tA). Although the improvement in the likelihood of successful acknowledgment comes at the expense of longer time-out intervals, the relative performance of IMP and EXP in terms of latency-and energy-efficiency depends on the choice of system parameters.
B. Stop and Wait (S&W) ARQ
Hence, our objective in this study is to design an acknowledgement scheme for S&W ARQ that maximizes the latency-efficiency and/or energy-efficiency (i.e. minimizes the energy consumption) for data delivery in a multi-hop acoustic communication system. Quantitatively, for the delivery of a single data packet from node 1 to node n+I for the system shown in Fig. l(a) , we evaluate the delivery time (Td), total time required for all transmissions to cease (Ta) and the total number of bits transmitted (B). The metric T1 measures the latency-efficiency while B measures the energy-efficiency of the acknowledgement scheme.
IV. OPPORTUNISTIC ACKNOWLEDGEMENT SCHEMES FOR MULTI-HOP ACOUSTIC COMMUNICATION
To determine an optimally-efficient acknowledgement scheme, it is necessary to obtain analytic expressions for each metric in terms of the channel parameters. While it is straightforward to derive the packet delivery time Td analytically for a multi-hop communication system, it is complex to do so for (Ta, B). Hence, we assume that the latter quantities may be approximately minimized by minimizing the corresponding per-hop quantities.
IV. OPPORTUNISTIC ACKNOWLEDGEMENT SCHEMES FOR MULTI-HOP ACOUSTIC COMMUNICATION
Let us assume that a new packet has just been received successfully at node j+1 from node j. With S&W ARQ, the Fig. 1 using the parameters defined in Table I. A. Spatially-invariant channel
IV. OPPORTUNISTIC ACKNOWLEDGEMENT SCHEMES FOR MULTI-HOP ACOUSTIC COMMUNICATION
We consider a one-dimensional n-hop acoustic channel that is suitable for long-range sensing / surveillance applications, as shown in Fig. 1(a) . We assume that the channel is spatiallyinvariant (i.e., BER pj = p), simulate the delivery of a single data packet (bD Kbits) and evaluate (Td, B, T,) averaged over 10000 runs.
IV. OPPORTUNISTIC ACKNOWLEDGEMENT SCHEMES FOR MULTI-HOP ACOUSTIC COMMUNICATION
To demonstrate the effectiveness of our proposed opportunistic acknowledgement schemes, we consider 5 x 10-6<p<5 x 10-5 which is within the typical interval [11] for acoustic channels and also includes (Pi, Pe) as given in the LHS of Fig. 2 .
IV. OPPORTUNISTIC ACKNOWLEDGEMENT SCHEMES FOR MULTI-HOP ACOUSTIC COMMUNICATION
The results obtained for n=6 and bD = 2 Kbits are shown in the RHS of Fig. 2 and Fig. 3 , alongside the corresponding values of (p*D pe) used by the HYB-LAT and HYB-ENE schemes respectively.
IV. OPPORTUNISTIC ACKNOWLEDGEMENT SCHEMES FOR MULTI-HOP ACOUSTIC COMMUNICATION
As expected, the performance of each scheme is degraded as the channel quality is worsened. For B and Tc, we observe that there exists a crossover point (denoted by p*) for which IMP outperforms EXP when channel conditions are better (p < p*) and vice versa. Since HYB-LAT and HYB-ENE select IMP when channel conditions are better and EXP otherwise, optimal performance can be achieved with HYB-LAT (HYB-ENE) if p* = P* (Pe = p*). In fact, we observe that p' p* and therefore, HYB-LAT gives the best performance in terms of (B, T,) for the range of channel conditions considered.
IV. OPPORTUNISTIC ACKNOWLEDGEMENT SCHEMES FOR MULTI-HOP ACOUSTIC COMMUNICATION
On the other hand, such a crossover point does not exists for the metric Td, and IMP delivers the packet within a shorter duration than EXP under all channel conditions. This is expected since Td depends only on the per-hop transmission and propagation delay and is independent of the acknowledgement scheme employed. Since an ACK packet is piggy-backed to each data packet with EXP, it incurs a larger transmission delay (tD+tA) compared with IMP (tD) and therefore, each packet will be delivered quicker with IMP. Hence where p is the mean BER over the n-hops. The corresponding results of Fig. 3 for the spatially-invariant random channel are plotted in Fig. 4 . Finally, we extend the one-dimensional string topology in Fig. l(a) to two dimensions, where several one-dimensional multi-hop communication channels converge to a common sink to form a two-dimensional network, as shown in Fig. 1(b schemes to ensure reliability through packet retransmissions and acknowledgements is important. In this paper, we proposed an opportunistic acknowledgement scheme suited for Stop and Wait ARQ protocols and demonstrated using simulations that it can offer better latency and energy efficiency than traditional non-opportunistic schemes for both one and two-dimensional multi-hop acoustic channels.
IV. OPPORTUNISTIC ACKNOWLEDGEMENT SCHEMES FOR MULTI-HOP ACOUSTIC COMMUNICATION
While we have considered single packet transmissions in this study, the opportunistic acknowledgement scheme may be applied for transmission of a group of packets [9] to achieve better performance. In addition, we also plan to incorporate this scheme for the comparison of a single path routing scheme with ARQ and a multi-path redundancy routing scheme for the virtual sink architecture proposed in [12] .
IV. OPPORTUNISTIC ACKNOWLEDGEMENT SCHEMES FOR MULTI-HOP ACOUSTIC COMMUNICATION
3.2r 

{'paper_id': '18417919', 'title': 'A Multi-hop ARQ Protocol for Underwater Acoustic Networks', 's2_url': 'https://api.semanticscholar.org/CorpusID:18417919', 'source': 'S2ORC'}