College of IoT Engineering, Hohai University, P.R. China
Received date: December 26, 2015; Accepted date: January 12, 2016; Published date: January 18, 2016
Citation: Gao M, Li J, Li W, Xu N (2016) Delivery Delay Analysis of Selective Repeat ARQ in Underwater Acoustic Communications. Sensor Netw Data Commun 5:134. doi:10.4172/2090-4886.1000134
Copyright: © 2016 Gao M, et al. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
Visit for more related articles at International Journal of Sensor Networks and Data Communications
Despite being the most efficient automatic repeat request (ARQ) protocol, the selective-repeat ARQ (SR-ARQ) is previously thought to be infeasible in underwater acoustic communications owing to the half-duplex property of typical underwater acoustic modems. However, with the help of the juggling-like stop-and-wait (JSW) transmission scheme, it has now become feasible. In this paper, we evaluate the delivery delay (consisting of transmission and resequencing delays) of the SR-ARQ operating over the JSW scheme under the static assumption that the relative radial velocity between the transmitter and the receiver is zero, aiming to provide system designers with a valuable reference for delay evaluation under more general scenarios. We model the underwater acoustic channel as a two-state Discrete Time Markov Channel, and derive the closed-form expression for the delivery delay under heavy traffic situation. Unlike most analytical approaches for the delay analysis of SR-ARQ in terrestrial communications whose computational complexities grow exponentially with round-trip delay, our proposed analytical approach is immune to the round-trip delay. This also makes our approach suitable for terrestrial communications. To highlight the accuracy of our approach, we also provide comparisons between analytical and simulation results.
Underwater acoustic channels; SR-ARQ; Transmission scheme; Radial velocity; Delay analysis
Underwater acoustic communication is deemed as the technique that will be widely used for oceanography, data collection, pollution monitoring, offshore exploration and tactical surveillance applications [1]. However, the characteristics of underwater acoustic channels, such as high bit error rate (BER), large round-trip delay, multipath coherence, as well as the half-duplex property of typical underwater acoustic modems, make the underwater acoustic link very poor [2].
In communication systems, the main error control mechanisms used on a per-hop basis to preserve data integrity include the use of forward-error-correction (FEC) schemes at the physical layer, and the use of automatic-repeat-request (ARQ) techniques at the data link layer. For ARQ protocols, the performance measures typically used are throughput [3,4], delay [5,6] and energy efficiency [7]. Delay analyses for ARQ protocols, especially for the most efficient SR-ARQ, have been extensively performed for terrestrial communications over the past few decades [8,9]. In underwater acoustic communications, however, little work has been done in analyzing the delay of ARQ protocols so far; this is because the least efficient stop-and-wait ARQ (SW-ARQ) and its variants are potentially viewed as the only ones that can be used in half-duplex underwater acoustic links, which make their delay analyses simple and straightforward.
In [10], we have proposed a transmission scheme, known as the juggling-like stop-and-wait (JSW) scheme [10], enabling the use of continuous ARQ protocols over half-duplex underwater acoustic links. Recently, the JSW scheme has been received much attention in the underwater community. For example, Chitre et al. validated the effectiveness of the JSW scheme in [11], and put forward a modification of this scheme when operated in small file scenarios. In [12], a variant of the JSW scheme was proposed, and applied in underwater networks. Also, we proposed a hybrid protocol for underwater acoustic networks by making use of the JSW scheme [13]. It is of importance to analyze the performance of the JSW scheme.
In this paper, we study the SR-ARQ when it is operated over our JSW scheme, focusing on analyzing its delay performance with the aim of providing some useful insights. As reported in [14], the total delay of an ARQ protocol can be attributed to three components, namely, queueing delay, transmission delay, as well as resequencing delay. The queueing delay is the duration from the time a packet arrives at the transmitter until its first transmission attempt, which correlates to the channel behavior and the packet arrival process. The transmission delay is the time from a packet’s first transmission until its successful arrival at the receiver (including all retransmission delays). This component is only related to the channel behavior. The last term is the resequencing delay, which is the most complicated, and defined as the waiting time of the packet in the receiver resequencing buffer. In this case, packets with higher identifiers must wait in the receiver resequencing buffer until all the packets with lower identifiers have been correctly received. Note that “delivery delay” consists of transmission delay and resequencing delay only. In this paper, we study the delivery delay performance of the SR-ARQ by considering both time-varying channel and finite round-trip time. Also, the effect of bursty channel errors is taken into account. For this purpose, we model the underwater acoustic channel by means of the two-state Markov chain that has been extensively used in wireless networks. Some assumptions are made to simplify the formal description; however, they do not affect the generality of the results, as they can be relaxed if needed. We have extended previous studies in terrestrial communications, and derived an exact closedform expression for the delivery delay in the static case where the relative radial velocity between the transmitter and the receiver is zero.
To our best knowledge, it is the first time an attempt has been made to analyze the delay performance of continuous ARQ protocols in half-duplex underwater acoustic links. The objec-tives of this paper are two-fold: 1) to provide system designers with a valuable reference for delay evaluation under more general scenarios in underwater acoustic communications; 2) to provide an alternative effective approach that can also be applied in terrestrial communications, as our proposed analytical approach is insusceptible to round-trip delay, whereas the computa-tional complexities of most existing analytical approaches for the delay analysis of SR-ARQ in terrestrial communications tend to grow exponentially with round-trip delay.
The rest of this paper is organized as follows. In Section 4, we review some related work on the delay analysis of the SR-ARQ. In Section 5, we first introduce the JSW transmission scheme which allows the SRARQ to operate in half-duplex underwater acoustic links. We then develop an analytical model and derive a closed-form expression for the delivery delay of the SR-ARQ under the static assumption. To verify the analytical results from the derivations, we compare them with simulation results in Section 5. Finally, Section 7concludes the paper.
The SW-ARQ and its variants are generally perceived as the only class of ARQ protocols that are suitable for half-duplex underwater acoustic links. As a result, there is no attempt to study the delay performance of continuous ARQ protocols (e.g., go-back-N ARQ (GBN-ARQ) and SR-ARQ) in underwater acoustic communications so far. Nevertheless, there has been extensive research on the delay performance of the SR-ARQ in terrestrial communications, as it is the most efficient among the continuous ARQ protocols. For this reason, we give a brief survey on the existing delay performance analysis of the SR-ARQ protocol in terrestrial communications.
In [5], Konheim assumed a renewal traffic source, and derived the probability generating functions (PGF) for the transport delays and queue lengths of both the GBN-ARQ and SR-ARQ. In [6], Anagnostou and Protonotarios developed an exact analytic approach to analyze the delay performance, and also proposed another approach that is based on the ideal SR-ARQ approximation (i.e., the queueing process is assumed to be dependent on the history of the transmission process). However, the results obtained in [5] and [6] are both based on the assumption of a static channel model; furthermore, the computational complexities of these approaches increase exponentially with the round-trip delay. Rosberg and Shacham [8] derived the distributions of the buffer occupancy and the resequencing delay at the receiver under heavy traffic assumption. In [9], Rosberg and Sidi analyzed the joint distribution of buffer occupancy at the transmitter and the receiver, deriving the mean transmission and resequencing delays under the assumption of a renewal arrival process. By using the flow graph analysis method, the authors in [3] addressed the effect of forward/backward channel memory on ARQ error strategies, and compared GBN-ARQ with SR-ARQ in terms of their throughput efficiency. In [15], Shacham and Towsley investigated the buffer occupancy and resequencing delay in a wireless environment in which a single transmitter and multiple receivers communicate, assuming heavy-traffic conditions and a static channel. Again, the results obtained in [3,8,9] and [15] were still under the assumption of a static channel. Based on the assumption of a nonstationary channel model, Fantacci [16] considered the channel’s time-varying feature, deriving the mean packet delay and the mean queue length of the SR-ARQ for both the zero and the finite round-trip delay cases. However, the author has made a simplifying assumption that the arrival process is Bernoulli.
In [17], Lu and Chang considered both the kth-order Markov model and the gap error model, and investigated how different error statistics would affect ARQ performance with the help of signal flow graphs. In [14], Kim and Krunz considered a time-varying channel with finite round-trip delay and a Markovian traffic source. A mean analysis was developed accordingly for all the ARQ delay contributions. Similarly, Rossi et al. [18] took time-varying channel, finite round-trip delay, and the effect of bursty channel errors into consideration together in their investigation of the SR-ARQ’s delay performance. A closed-form expression for delivery delay was subsequently derived. However, the computational complexities of the analytical approaches presented in [17] and [14] show an exponential increase with round-trip delay.
From the discussion above, we can observe that the main drawbacks of existing analytical approaches include: 1) overly simplified channel model assumptions, 2) very simple arrival process assumption, and/or 3) extremely high computational complexity. More specifically, some approaches are based on the static channel assumption, which results in significant underestima-tion of the delay performance. As is shown in [14], using a time-varying channel model can lead to a remarkable increase in the mean transport delay. The exponential growth in the computational complexity of these approaches with the round-trip delay is also a tiresome issue that makes their usage very difficult in a practical system. Hence, an intuitive and simple expression for the delay calculation is very much needed.
In this section, we briefly describe the JSW transmission scheme, and then characterize the underwater acoustic channel by means of an embedded Markov model. Some assumptions are accordingly made to simplify our analysis. Note that these assumptions can be extended to a more general situation if necessary. We thereafter derive the closedform expression for the delivery delay of the SR-ARQ when it operates over the JSW scheme.
The JSW transmission scheme
Consider a point-to-point, half-duplex underwater acoustic communication system with a transmitter and a receiver. We assume that the transmitter has already acquired the control of the channel successfully, and has a series of packets to send to the receiver. Although the channel is half-duplex, a pair of nodes can still send packets that cross each other in the medium and yet receive each others’ packets correctly, so long as each node has finished its transmission and has switched to listening mode by the time the packet arrives. Based on this property, the transmitter alternates between transmitting a data packet to the receiver, and listening for an earlier packet’s ACK/NAK, while one or more other packets are still in transit. For the receiver, it transmits the ACK/NAK immediately after receiving each data packet. Apart from the time it spends on transmitting the ACK/NAK, the receiver listens for data packet at other times. In order for the scheme to work correctly, an appropriate window size (denoted by s), as well as the appropriate inter-packet spacings (denoted by t_{0}) to transmit the first s packets, must be chosen properly. The flow of the JSW transmission scheme is illustrated in Figure 1 when s=3.
Our focus in this paper is on the static case where the relative radial velocity between the transmitter and the receiver is zero. Thus, the propagation delays in both directions are constant, which we denote by d_{0}. The value of t_{0} is also chosen in such a way that the inter-packet spacing between any two consecutive data packets will be equal to t_{0} throughout the entire session (not just for the first s packets). From Figure 1, we see that the maximum window size s that can be chosen for the static case is given by
(1)
where δ is the transmission time of a data packet, and γ is the transmission time of an ACK/NAK packet, respectively. The value of t_{0} is in turn given by
(2)
As can be seen in Figure 1, the transmitter undergoes a cyclical behavior of alternating between sending a data packet, and listening for an ACK/NAK. We refer to this cyclical behavior as a “Transmit- ACK cycle (TAC)”, whose cycle time is defined to be from the instant when the transmitter starts sending the first bit of the data packet, till the instant when it finishes receiving the last bit of the following ACK/ NAK. All TACs thus have the same cycle time of δ + t0. For more details on how the JSW transmission scheme operates, especially for the dynamic case where the relative radial velocity is non-zero, interested readers are encouraged to refer to [10].
The channel model
The underwater acoustic channel is generally characterized by poor quality physical link, due to time-varying multipath propagation and motion-induced Doppler distortion. As a result, the BER of the underwater acoustic link can vary with time as the propagation conditions change. Errors in the received bit stream are thus inevitable. Here, we model the underwater acoustic channel as a two-state Markov chain (as shown in Figure 2) based on the following assumptions:
• Time is divided into slots, each of which equals to the cycle time of a TAC (i.e., δ + t_{0}).
• The transmitter and the receiver are synchronized with the timeslots (It can be easily implemented using existing underwater synchronization schemes [19,20]); the transmission of a packet occurs at the beginning of a slot.
• The ACK/NAK messages are always received correctly. This can be justified by considering the use of a powerful error-correcting code to guarantee successful receptions with a high probability.
• A packet is released from the transmitter buffer only when an ACK message has been received for its last transmission attempt.
• There is an infinite data source at the transmitter, which implies a heavy-traffic situation.
Two possible channel states are defined, namely, state 0 (quiet, with BER e_{0}) and state 1 (noisy, with BER e_{1}). State 0 represents a channel propagation situation in which the transmitter can correctly receive data packets with a very high probability, while state 1 represents a channel propagation situation in which it is extremely difficult to correctly receive the data packets. The values of e_{0} and e_{1} are dependent on the characteristics of the propagation environment, the transmission modulation scheme, and the detection technique implemented at the receiving end. Of note is the fact that errors in state 1 usually occur in random-length bursts. We also assume that channel state transitions could only occur at the end of the slots with probabilities p_{01} and p_{10}, respectively (see Figure 2). In this way, we do not take into account the fact that in actual non-stationary channels, the state transitions may occur anywhere in time. In particular, our assumption leads to a slight error in the estimation of the probability that a data packet would be received erroneously. As stated in [4], however, this may have a negligible impact on the accuracy of the analysis. With the channel model above, we can derive the following relationships: 1) the average burst length, i.e., the average number of data packets transmitted in state 1, is ; 2) The steady state channel probability in state 0 is ; 3) The steady-state channel probability in state 1 is ; 4) the average channel error rate is
Denote by the transition probability from state i (i=0, 1) to state j (j=0, 1) after k slots. The four possible k-step transition probabilities are then given by [4]:
(3)
(4)
(5)
and
(6)
From the above, it follows that parameters p_{01}, p_{10} and ε completely define the two-state Markov channel model. Parameters Nb and p1 characterize the burstiness of the channel with p_{01} and p_{10} describing the time variation of the channel behavior. The special case p_{1}=p_{01}=1 − p_{10}, corresponds to the two-state block interference (BI) channel model. Evidently, the BI channel model is entirely determined by parameters ε and p_{1}. This paper is based on the assumption that all transmissions in state 0 are error free, while all those in state 1 are erroneous. It is a reasonable assumption which has also been used in [21]. In this case, ε degrades to p_{1}. Note, however, that: 1) the two-state Markov model can be extended to a more common scenario characterized by N_{b}, p_{1} and ε; 2) it can also be extended to account for a higher order Markov chain, which might yield slight improvements in the results, but at the expense of more complicated and tedious computations.
Calculation of delivery delay
Consider a packet of interest (referred to as tagged packet) upon its first transmission. Denote by X (t)=(X_{1}(t), X_{2}(t), . . . , X_{s}(t)) the set of identifiers of those packets that are transmitted during window t. The process (X_{1}(t), X_{2}(t), . . . , X_{s}(t)) governs the evolution of the resequencing buffer occupancy. We refer to the position k (1 ≤ k ≤ s) in each window as column k. Note that, one column corresponds to one slot. Any packet that was unsuccessfully transmitted on column k in window t is assumed to be retransmitted at the same column in window t + 1. Without loss of generality, we assume the tagged packet is transmitted for the first time at slot (denoted by τ ) s in a window, which implies the channel state at τ=0 is 0 (otherwise a retransmission will occur at τ=s). Note that the packets that block the tagged packet in the receiver buffer at the time of its successful reception are those that were transmitted during the same window where the tagged packet was first transmitted and have not been correctly received. Denote by Γ_{p} the period from the instant when the tagged packet is transmitted for the first time on column s to the instant when the tagged packet, as well as all those with lower identifiers in the same window, is correctly received. To find the delivery delay, we define the last blocking packet, satisfying: 1) it is on column j (1 ≤ j ≤ s), and has been transmitted m times until success during Γ_{p}; 2) ∀α ∈ [1, j − 1], there is at least one successful transmission on column α during Γ_{p}; 3) ∀β ∈ [j + 1, s], there is at least one successful transmission on column β within the prior m − 1 transmissions of Γ_{p}. Note that, j=s implies the case where the tagged packet itself, as well as all those with lower identifiers in the same window, will be correctly received at the receiver for the tagged packet’s first transmission.
Let denote the event {the packet on column j has succeeded in the k^{th} transmission}, denote the event {the packet on column j has failed in the k^{th} transmission) , and denote the event {the packet on column j has not been successfully transmitted for m consecutive times, given that the channel state at time τ=0 is 0 (equivalently termed G)}. The probability of the event is given by
(7)
Where
(8)
Note that, for 1 ≤ k ≤ m, Pr {R_{d}|s_{k} } denotes the probability of the event {the data packet has been successfully transmitted, given that the channel state for the transmission is sk (sk=0 or 1)}, defined as
(9)
Hence, (7) can be rewritten as
(10)
To simplify the above expression, we define
(11)
And
(12)
(13)
Inserting into (10), we have
(14)
Further, denote by m|j, G the event {the last blocking packet on column j has been transmitted m times until success during Γp, given that the channel state at time τ=0 is G}. For 1 ≤ α ≤ j − 1, we let α|m, j, G denote the event {there is at least one successful transmission on column α during Γp, given that the channel state at time τ=0 is G}. Also, for j + 1 ≤ β ≤ s, we let β|m, j, G denote the event {there is at least one successful transmission on column β within the prior m −1 transmissions of Γp, given that the channel state at time τ=0 is G}. The probability of the event m|j,G is given by
(15)
where I_{2×2} is a two-by-two identity matrix.
For 1 ≤ α ≤ j − 1, it is easy to see that
(16)
and for j + 1 ≤ β ≤ s,
(17)
It can be easily inferred that, if the event m|j, G takes place, then the events α|m, j, G and β|m, j,G take place concurrently, and vice versa. Given (m, j, G), the delivery delay of the tagged packet, T, can then be expressed as
T=(m − 1)s + F, (18)
where F is the column j where the last blocking packet is transmitted, which is uniformly distributed over the set {1, 2, . . . , s}, and hence Pr
From (15)-(17), we have
(19)
By averaging (19) over all possible sets with regard to m, j and G, we can obtain
(20)
where Pr {G}=p_{0}.
Note that the representation in (20) involves an infinite summation which is somewhat incon-venient. By performing some algebraic manipulations, nevertheless, a simpler formula for E{T } is provided in Appendix II.
In this section, we present the numerical results of the delivery delay obtained using the above analytical results. To validate the accuracy of our analysis, we have simulated the transmission of packets based on the SR-ARQ protocol operating over the JSW transmission scheme, which we have presented in Section 5.1.
In our simulations, the data rate of the underwater acoustic channel is assumed to be 8 kbps, along with d_{0}=0.6667 s, δ=0.064 s, and γ=0.005 s. When varying the value of one parameter, the other parameters are kept at their default values above, unless specified otherwise. We also assume that there is an infinite data source at the transmitter. The total simulation time is set to 1,000,000 s, and all the results presented are averaged over 20 simulation runs. Note that all the obtained delivery delays in this section have been normalized to the transmission time of a data packet, which is different from that of a TAC.
In Figure 3, the mean delivery delay T is shown as a function of the mean channel error rate ε for various values of the average error burst length: N_{b}=3, 5, 10, 15. Here, ε is assumed to range from 0.01 to 0.3. Note that T does not include the queueing time, i.e., the duration from the time a packet arrives at the transmitter until its first transmission attempt. Also, we vary N_{b} by varying the transition probability p_{10} (from state 1 to state 0). A good agreement is observed between simulation and analysis. It can be seen that T increases almost linearly with regard to the mean channel error rate ε. This can be explained as follows. With an ARQ protocol, the delivery delay is mainly affected by the number of retransmissions and the round-trip delay. However, for a given ε, the average number of retransmissions is almost constant. Therefore, the delivery delay is dominated by the round-trip delay, which is independent of the mean channel error rate. Moreover, for a given ε, we can see that, the greater the average error burst length N_{b}, the smaller the mean delivery delay T . This is due to the fact that the probability of encountering a long sequence of slots without errors increases as N_{b} increases.
The impact of the average error burst length N_{b} on the mean delivery delay T is illustrated in Figure 4. Here, we assume that N_{b} varies from 1 to 50, and set the other parameters to their default values. We vary N_{b} by tuning the transition probability p_{10}. Again, the simulation results show good agreement with the analytical results. For each ε, the mean delivery delay T decreases as N_{b} increases, for the same reason as explained above.
Figure 5 demonstrates the significance of the propagation delay d_{0} by contrasting the mean delivery delay for different d_{0} (0.6667 s and 0.3333 s, respectively). As was done previously, ε is varied by changing the parameter p_{10} under a fixed p_{01}. From this figure, one can make the following remarks. Firstly, in both cases, it can be seen that the simulation results match with the numerical results quite well. Secondly, the relationship between the mean delivery delay and the channel error rate exhibits similar trends as what Figure 3 has shown previously. Finally, it can be seen that a smaller d_{0} (which corresponds to a shorter distance between the transmitter and the receiver) results in a lower mean delivery delay. For example, when Nb=3, the mean delivery delay for d_{0}=0.3333 s is much lower than that for d_{0}=0.6667 s. The same conclusion about the mean delivery delay still holds when N_{b}=10. This can be attributed to the fact that, a smaller d_{0} corresponds to a smaller round-trip delay s, hence resulting in a lower mean delivery delay under the condition that both N_{b} and ε are constant.
The mean delivery delay T as a function of the average error burst length is shown in Figure 6 for both d_{0}=0.3333 s and d_{0}=0.6667 s. These results reveal high variation of the mean delivery delay with the mean channel error rate for different d_{0}. As expected, the mean delivery delay for d_{0}=0.3333 s is lower than that for d_{0}=0.6667 s, which is also similar to what we have previously observed in Figure 5. Again, it suggests that delay largely depends on the distance between the transmitter and the receiver in underwater. For a given ε, it can be seen by comparing Figure 6 with Figure 4 that, the varying trend between the mean delivery delay and the average error burst length remains the same.
Accurate delay analysis plays an important role in evaluating the performance of underwater acoustic communication systems. In previous studies, continuous ARQ protocols are perceived to be infeasible in underwater environments due to the half-duplex property of underwater acoustic modems, and thus the existing ARQ approaches have centered around the use of the classic SW-ARQ protocol and its variants, whose delay estimates are simple and straightforward.
In this paper, we operate the SR-ARQ protocol in half-duplex underwater acoustic channel for the first time based on the JSW transmission scheme that was tailored for underwater acoustic communications. Based on the static assumption that the relative radial velocity between the transmitter and the receiver is zero, we first characterize the non-stationary underwater acoustic channel by a two-state Markov channel model, which captures the time-varying and correlated nature of channel errors. Then, we investigate the delivery delay and derive a closed-form expression for the mean delivery delay of the SR-ARQ protocol. Finally, we validate the accuracy of the expressions obtained through simulations. The contributions of the work are: 1) to present an exact delay analysis for the static case, which serves as a valuable reference for delay estimation under dynamic scenarios for underwater acoustic communications; 2) to present a simple and straightforward approach to delay analysis, which can be effectively applied in terrestrial communications as well, because its computational complexity is immune to the round-trip delay.
Our future research will be focused on the following aspects: 1) to evaluate the end-to-end delay performance in underwater network settings; 2) to investigate the energy efficiency when applying the SRARQ protocol in underwater acoustic networks.