1 Introduction

Wireless sensor network (WSN) technology is rapidly advancing and many experimental and commercial deployments are taking place in the recent years. Some of the reported pilot trials reveal that deployment lifetime and data yields in real WSNs are far from being satisfactory, e.g., 50% at the Redwood network [17], 58% at the Great duck island [16] and 68% at the volcano network [20]. These trials highlight the fact that energy efficiency and data reliability in WSN are major concerns requiring further investigation. Reliability is directly related to energy efficiency. Footnote 1 In automatic retransmission request (ARQ) schemes, for example, a large number of retransmissions has to be made in order to achieve absolute reliability for poor quality radio links. This can be quite energy-inefficient as the number of transmissions are linearly correlated with the sensor wake-up time, which is in turn a major sensor energy consumer [11].

Our recent experience in deploying WSN applications [7, 19] also indicates that occasional packet losses are tolerable. The reliability is actually determined by the quality of an ensemble of the sensed data delivered at the sink, rather than the reliability of individual data sample. This suggests a coarse level of reliability. Thus, if the requirement is changed such that each data packet is successfully delivered only with probability β < 1, rather than with probability one (absolute reliability), we have the potential benefit of saving transmissions and therefore energy.

To gain a better insight into WSN reliable data delivery, we introduce a new notion, the statistical reliability, as a common quality of service (QoS) measure for sensor data streaming applications. This reliability notion is defined as follows

\(\user2{Statistical\,reliability}\) with level β is a QoS level where during every predetermined time window, a predetermined size of random sensed data are delivered to the sink node from every source, each with a probability of at least β.

The motivation for our new definition is to include energy efficiency into the reliability notion. This is consistent with the recent ideas of balancing between reliability and energy expenditure [4, 6, 9]. In practice, a predetermined reliability level β is achieved by controlling the maximum number of retransmissions (e.g. RetryLimit_ variable in ARQ). Using a statistical reliability objective, when designing a reliable transport protocol, is significant for WSN since it reduces the number of transmissions compared to absolute reliability. Consequently, sensor data delivery operations are more energy efficient and the WSN deployment lifespan is increased. We are the first to introduce a precise definition and analysis of ARQ protocols with Statistical reliability. A previous approach of non-absolute reliability, ESRT [4], is defined in the average sense and is analysed only approximately.

Statistical reliability is applicable to a wide range of WSN applications such as environment (temperature, humidity), agriculture (water tank, irrigation), and urban living (electricity/water use, petrol price, traffic report). In these applications, a statistical reliability of 90–95% is sufficient. However, we also note that statistical reliability is not suitable for time/event critical applications such as bushfire and battlefield monitoring where very high reliability is required at all cost.

The implicit ARQ (iARQ) mechanism bears a distinct advantage for WSN since acknowledgement (ACK) transmissions can be saved. However, there is a potential issue in multi-hop paths with asymmetric links. We demonstrate that radio asymmetry is nonnegligible in real WSN and has a potentially devastating impact, the “avalanche effect”, on energy consumption of reliable data delivery with implicit ACKs. We propose a combined implicit and explicit ARQ protocol (ieARQ) to overcome the negative impact of asymmetric radio links in wireless sensor networks. We are the first to analyse the avalanche effect and coined this term.

Using our theoretical models, we compare the energy efficiencies of common reliability protocols and propose new improvements to save energy over the standard ARQ protocols. These new protocols eliminate the large number of retransmissions of ARQ under the avalanche effect. Our analysis shows that selective repeat hop-by-hop ARQ (srARQ) is the most efficient protocol across the board. However, srARQ is infeasible in WSN due to buffer and processing constraints.Footnote 2 Extensive performance evaluations point to a new hybrid strategy of energy efficient and statistically reliable transport (eESRT) with combined ieARQ. This eESRT + ieARQ protocol starts with streaming a larger than required sensed data without recovery until some threshold hop H_sw, which is dependent on measured network conditions; then it switches to combined implicit and explicit ARQ. The eESRT + ieARQ protocol is proved to be both energy-efficient and computation-feasible.

The rest of the paper is organized as follows. A brief survey of related work is given in Sect. 2. We present rigorous analyses on the energy efficiency of a comprehensive set of statistically reliable data delivery protocols in Sect. 3 and in the Appendix. Simulation results validate our theoretical models and provide insight to the design of eESRT + ieARQ protocol in Sect. 4. Field trials confirm our findings in Sect. 5. Our contributions are concluded in Sect. 6.

2 Related work

Classical ARQ protocols used for land-line networks comprise three basic schemes: send-and-wait (SW), go-back-N (GBN) and selective repeat (SR) [5, 8, 12, 23]. With SW, the transmitter waits for an ACK or a timeout before its next transmission. With GBN and SR, the transmitter sends packets continuously. However, to prevent buffer overflow at the receiving node, the number of unacknowledged transmissions is kept below a preset size of N packets. GBN and SR are implemented by a sliding window of size W, where W is determined by N and the round trip time (RTT) estimator. The objective is to keep a continuous stream of transmissions, hence utilizing channel capacity while maintaining lower packet delay.

All three ARQ protocols can operate hop-by-hop (HBH) or end-to-end (E2E). With respect to packet delay, E2E is better than HBH for small error rate, and worse for high error rate [18]. To the best of our knowledge, the relationship between HBH and E2E with respect to energy-efficiency has not been studied.

In [18], an absolute reliable data delivery protocol called PSFQ (pump slowly, fetch quickly) has been proposed for reliable code distribution in WSN. PSFQ performs controlled pumping and intermediate nodes use hop-by-hop recovery ARQ based on negative acknowledgment (NACK).

In [15], the authors investigate the tradeoff between having reliability implemented at MAC, transport and application layers. The proposed reliable multi-segment transport (RMST) combines MAC layer ARQ with transport layer NACK-based schemes to provide guaranteed delivery. This work differs from ours in that they focus on absolute reliable data delivery. However, most WSN sensor applications do not require 100% guaranteed data delivery. Moreover, such absolute reliability may incur significant overhead.

Reliable communication mechanisms with the objective of minimizing energy efficiency were studied in [6]. EPB (energy per bit) was introduced to characterize the energy efficiency, identify an optimal bound, and conclude that lazy loss detection (i.e., selective repeat) ARQ is the most energy efficient as an absolute reliable data delivery protocol. In our analysis, we adopted transmitted packet number as energy efficiency indicator (on packet level instead of bit level) in conjunction with statistical reliability instead of absolute reliability.

Event-to-sink reliable transport (ESRT) is presented in [4] for sensed data streaming applications not requiring absolute reliability. The reliability level of the protocol has been analyzed and simulated with NS2. In this paper, the energy efficiency of ESRT is analyzed as well. Our analysis reveals that its energy efficiency deteriorates exponentially with the path length. As a result, we propose a hybrid scheme combining eESRT (a modified ESRT) and implicit hop-by-hop ARQ with significant improvement on energy efficiency.

Since energy saving is one of the main concerns of WSN, it has been proposed in e.g., [6, 22] to avoid explicit ACK packets by utilizing the overhearing phenomenon of radio broadcast. That is, detecting the acknowledgments from the forwarding transmissions. This iARQ mechanism has a potential of energy saving. However, as our analysis [10] shows, iARQ could be problematic when the radio links are asymmetric. In [14], we proposed combining ieARQs to overcome this problem and achieve energy savings in such scenarios. In this paper, we integrate the ieARQ scheme into the proposed hybrid system that dynamically switch between eESRT and ieARQ mechanisms according to a dynamic hop threshold H_sw to achieve energy efficiency under a statistical reliability constraint.

3 Energy efficiency and statistical reliability

A large variety of statistically reliable data delivery protocols are specified below. To improve the energy efficiency of WSN, these specified protocols, which are variants of conventional ones, adapt the maximum number of retransmissions to the channel error rate and the required statistical reliability β.

For selecting a good generic candidate for a WSN protocol stack we analyze the energy efficiency of these protocols. For the sake of modeling and analysis, consider a single path with h + 1 sensors labeled \(0,1,\ldots,h\) and the corresponding h link hops from a sensor source to the sink node as depicted in Fig. 1. To reflect real signal fading of wireless channels we allow nonreciprocal links between adjacent sensors as well as fading dependency between adjacent links.

Fig. 1
figure 1

A single route with transmission failure probabilities

Full size image

For every i, the probabilities that a transmission from node i to node i + 1 and from node i + 1 to node i are received successfully are denoted by 1 − p i and 1 − q i , respectively. We assume that reception failures are spatial dependent but time independent. Spatial dependency means that the reception of a transmission from node i ≥ 1 at node i + 1 is correlated with the reception at node i − 1. Specifically, for every transmission of node i ≥ 1, let r i denote the conditional probability of the following reception event:

$$ r_i \mathop{=}\limits^{def} Pr[\hbox{Success at node } i-1 | \hbox{Success at node } i+1]. $$

Time independent means that a reception failure of a transmission from node i at time t is independent of a reception failure of another transmission from the same node at time t 1 ≠ t. We also assume that transmitter power and topology are controlled so as to limit the transmission range within only one hop away.

For notational brevity, for every probability, \(p, \bar{p}\) denotes 1 − p.

As pointed out in [6], link error rate probabilities are readily available for the transport layer from the link quality indicator (LQI) defined by IEEE standard 802.15.4 [1] which are highly correlated. LQI is implemented on Chipcon CC2420 [2] and used on MicaZ and Telos sensors.

Unlike strict reliability used in [6] for code distribution application, this paper concerns with data streaming applications requiring only statistical reliability. As discussed in Sect. 1, statistical reliability is less stringent than strict reliability and leads to more energy efficient transport protocols.

The overall energy consumption is an important parameter which is not easily measured in real implementations, since it depends on a variety of factors. We have chosen to focus on measuring just the energy consumed by transmissions, since this it is a clearly defined parameter and is straightforward to measure. Further, it is directly affected by the new protocols we propose in our paper. Energy consumption of other system components, including higher layer protocols, will also be affected by our proposed algorithms. However, these energy components will strongly depend on the particular hardware/system implementations and are not within the scope of our paper (nor page limitations).

In this paper, the energy efficiency of statistically reliable data delivery protocols is evaluated by the expected number packet transmissions. We believe that the interested reader will be able to take our results on transmission energy usage, and integrate them into their implementation specific energy measurements for higher layer components. We point out that this is common practice taken in a number of other related publications, including [6, 22].

Given a transport protocol, π, its normalized energy consumption, E π, is defined as the expected number of transmissions (sensed and ACK packets) required for delivering one sensed data with probability β from source to sink.

3.1 Energy efficiency of ESRT: E_ESRT

With ESRT [4], a sufficiently large number of sensed data packets are sent out within each unit time interval from source sensor nodes toward the sink without any acknowledgment (ACK) or retransmissions. The number of packets sent out per unit time, defined as the reporting frequency rate f in [4], from the source is determined by an outer-loop protocol between the source and the sink nodes aimed at receiving a required mean frequency rate f at the sink. In this paper, the source reporting frequency rate f is determined analytically as a function of the statistical reliability β and the hop count between the source and destination.

Observe that at each hop, the reporting frequency rate f is reduced on the average by factor of 1 − p, where p is the link packet error rate. Thus, the reporting frequency rate f at the source sensor increases exponentially with the path length and so is the overall number of transmissions. As our analysis shows, for paths longer than some threshold, ESRT becomes energy-inefficient and the number of transmissions clogs the WSN. This phenomenon has been pointed out in [4]. In this subsection, we present quantitative analysis on the energy efficiency of ESRT based on our theoretical model.

The ESRT protocol label is denoted by π = ESRT. With ESRT, retransmission is replaced with a much larger reporting frequency rate f at the source used for backups. Let L_ESRT(β) be the frequency rate f limit required for each sensed data to satisfy a successful delivery probability β.

Proposition 1

For the ESRT protocol, \( L_{\rm ESRT}(\beta) = \left\lceil {\frac{\log(1-\beta)}{\log\left(1 - \prod_{i=0}^{h-1}\bar{p}_i\right)}} \right\rceil, \) and

$$ E_{\rm ESRT} = L_{\rm ESRT}(\beta) \left(1+\sum_{i=1}^{h-2} \prod_{k=0}^{i-1}\bar{p}_{k}\right) $$
(1)

where \(\lceil x \rceil\) is the smallest integer larger than or equals x.

Proof

See Appendix.

Observe that when β approaches one, L_ESRT(β) approaches infinity and so is E_ESRT. The explanation is simple; for any finite L_ESRT(β), there is a positive probability that all L_ESRT(β) transmissions will fail.

3.2 Energy efficiency of SW E2E ARQ: E e2e ARQ

The SW E2E ARQ protocol label is denoted by π = ARQ with a superscript of e2e and all temporal notations above are redefined. Let L e2e ARQ(β) be the limit on the number of transmissions and retransmissions required for each sensed data to achieve a successful delivery with probability β.Footnote 3

Proposition 2

For the SW E2E protocol, \(L_{\rm ARQ}^{e2e}(\beta) = \left \lceil {\frac{\log(1-\beta)}{\log\left(1-\prod_{i=0}^{h-1}\bar{p}_i\right)}}\right\rceil,\) and

$$ \begin{aligned} E_{\rm ARQ}^{e2e} =& {\frac{1- \left(1- \prod_{i=0}^{h-1} \bar{p}_i \bar{q}_i \right)^{L_{\rm ARQ}^{e2e}(\beta)}} {\prod_{i=0}^{h-1} \bar{p}_i \bar{q}_i}} \left[ 1+ {\sum_{i=0}^{h-2} \prod_{k=0}^i} \bar{p}_k \right.\\ &+ \left. \left(\prod_{k=0}^{h-1} \bar{p}_k\right) \left(1 + {\sum_{i=0}^{h-2}} \prod_{k=0}^i \bar{q}_{h-1-k}\right) \right]. \end{aligned} $$
(2)

Proof

See Appendix.

Note that L e2e ARQ (β) and L ESRT (β) are equal and for the extreme case of h = 1, E e2e ARQ  = E ESRT , as expected. Also, for β→1, L e2e ARQ (β) → ∞.

3.3 Energy-efficiency of SW hop-by-hop ARQ: E ARQ

With SW HBH ACK ARQ, reliability is assured in every hop. If a transmitter receives an ACK from its subsequent node before the preset timeout occurs, it transmits a new packet; otherwise, it retransmits the preceding packet. A receiver transmits an ACK for every packet it receives successfully including for duplicates. It is worth noting that when a packet is received successfully for the first time, it is forwarded regardless of its ACK outcome. By convention, duplicates are not forwarded.

Since the reliability requirement is of some level β, the number of retransmissions in each hop is bounded by some N(β) derived below. Using the minimum upper bound is important for energy saving.

Due to relatively high error rates of wireless links in WSN, SW HBH ACK ARQ [15] seems as an attractive candidate. However, considering the energy used for ACKs, an implicit SW HBH ACK (SW HBH iACK ARQ), described below, could be more efficient.

Unlike ESRT protocol, where the number of transmissions increases exponentially with the path length, the number of transmissions with HBH ARQ increases linearly. Thus, SW HBH ARQ is expected to outperform ESRT for paths shorter than some threshold. This threshold certainly depends on the link error rates. Indeed, in the ideal case with no errors, ESRT incurs no transmission overhead whereas SW HBH ARQ does.

The SW HBH ARQ protocol label is denoted by π = ARQ. Let L ARQ(i, β) be the limit on the number of transmissions and retransmissions required at link hop i for each sensed data to achieve a successful delivery with probability β.

Proposition 3

For the SW HBH protocol, \(L_{\rm ARQ}(i,\beta) = \left\lceil {\frac{\log\left(1-\beta^{1/h}\right)}{\log(p_i)}} \right\rceil, \) and

$$ E_{\rm ARQ} = \sum_{i=0}^{h-1} {\frac{1 - (1- \bar{p}_i \bar{q}_i)^{L_{\rm ARQ}(i,\beta)}}{\bar{p}_i \bar{q}_i}}\;\left(1+\bar{p}_i\right) $$
(3)

Proof

See Appendix.

3.4 Energy efficiency of SW HBH Oriented iARQ: E oiARQ

Traditional SW HBH ARQ use explicit ACK messages which consumes energy. Explicit ACKs are required for wired links; however, with wireless links, the transmitter can “overhear” the forwarding transmission and interpret it as an implicit ACK. Clearly, the sink node is required to send an explicit ACK. Transmissions and retransmissions are as with SW HBH ARQ. This ARQ version, referred to as SW HBH iARQ in this paper, has been proposed in [21].

If packet errors on the upstream and downstream links are highly correlated, the energy saving with SW HBH iARQ is apparent since ACKs are almost free. Since the distance and the landscape between a node and its close neighbors are most likely similar, the reception qualities are expected to be highly correlated.

A potential issue arising out of our NS2 simulation is the retransmission timeout setting. Unlike explicit ARQ where ACK is sent immediately by the hardware, in iARQ, timeout depends on the forward queues.

Another potential issue with iARQ is an “avalanche” effect demonstrated in our work [14], where unnecessary retransmissions are generated all the way down to the sink due to miss-interpretation of a packet transmission role. One way to prevent the “avalanche” effect is by using an orientation bit in the packets which signifies if it is used as an upstream ACK only. Specifically, we define an orientation bit in the packet header. If the orientation bit in a transmitted packet is zero, the packet serves as a forward packet and an implicit ACK; otherwise, it serves as an implicit ACK only.

When node i is scheduled to relay a data packet from node i − 1 to node i + 1, it initially transmits the packet in broadcast mode with orientation bit set to zero. After it receives an iACK from node i + 1, if further iACK is required from node i − 1, node i switches the orientation bit to one before retransmitting the packet (now serve as iACK to node i − 1 only). In this case node i + 1, knowing that this is an iACK, does not need to acknowledge such retransmissions, hence stopping the avalanche.

The SW HBH Oriented iARQ protocol label is denoted by π = oiARQ and all temporal notations above are redefined. Let L oiARQ(i, β) be the minimum number of transmissions required at link hop i for each sensed data for successful delivery with probability β.

Proposition 4

For the SW HBH iACK protocol, L oiARQ(i, β) = L ARQ(i, β), and

$$ \begin{aligned} E_{\rm oiARQ} =\;&{{\frac{1-(1- \bar{p}_0 \bar{q}_0)^{L_{\rm oiARQ}(0,\beta)}}{\bar{p}_0 \bar{q}_0}}}\\ &+ {\sum_{i=1}^{h-1} {\frac{1-(1- \bar{p}_i \bar{q}_i r_i)^{L_{\rm oiARQ}(i,\beta)}}{\bar{p}_i \bar{q}_i r_i}}}\\ &+ {{\frac{1 - (1- \bar{p}_{h-1} \bar{q}_{h-1})^{L_{\rm oiARQ}(h-1,\beta)}}{\bar{p}_{h-1} \bar{q}_{h-1}}} \times \bar{p}_i.} \end{aligned} $$
(4)

Proof

See Appendix.

Observe that for spatial dependency of r i  = 1, SW HBH oiARQ saves all the ACKs of SW HBH ARQ except for the ACKs from the sink.

3.5 Energy efficiency of combined-ieARQ: E ieARQ

Another way to prevent the “avalanche” effect is to combine ieARQ. Upon the first reception of a specific packet by node i, the node forwards the packet to i + 1 serving also as an iACK for node i − 1. For all subsequent receptions of the same packet, the node sends an eACK rather than an iACK.

Note that when a timeout occurs at node i, the packet is re-forwarded to node i + 1. At the same time, it is also being interpreted by node i − 1 as another iACK. Nevertheless, such interpretation is harmless since it does not create an avalanche.

The main difference between oiARQ and ieARQ springs from the following scenario. Suppose that an iACK transmitted by node i is not received by both nodes, i − 1 and i + 1; and a retransmission from node i − 1 arrives at node i before a timeout fires at i. With ieARQ, node i sends an eACK; whereas with oiARQ, it sends an iACK with the orientation bit set to one. Although, the bit informs node i + 1 that it is an iACK to node i − 1, it can still use the packet if it had not received it yet. Such events reduce the packet failure probability compared to ieARQ.

The energy consumption of ieARQ, E ieARQ(β), is readily available from the energy consumption of SW HBH ARQ with eACK, E ARQ(β).

Compared to SW HBH ARQ with eACK, ieARQ saves one eACK in each node i = 1, ..., h − 1. The number of sensed data transmissions with both protocols are the same. Therefore, the following proposition is implied.

Proposition 5

For the ieARQ protocol,

$$ E_{\rm ieARQ}(\beta) = E_{\rm ARQ}(\beta) - (h-1). $$
(5)

3.6 Energy efficiency of E2E SR ARQ: E e2esrARQ

As discussed earlier, SW ARQ protocols have minimal buffer requirements, but their channel utilization and packet delay are not efficient. To improve the utilization and packet delay, continuous transmissions are used by GBN and SR. The improvement is at the expense of buffer size, which is not suitable for some sensors, e.g., MICA2 motes have only 4 KB [3].

To avoid unnecessary delays, it is common practice in wired networks to transmit an ACK (with GBN) or a negative ACK (NACK, with SR), upon every received packet. However, to save energy, the version proposed here sends a single ACK/NACK for a batch of packets.

GBN and SR have an HBH and E2E versions. Due to buffer size limitations in sensor nodes, E2E could be more attractive for some nodes since it would not stress the buffers at the relay nodes.

To track lost packets, both protocols use sequence numbers (SN) to label the sensed data packets. With SR ARQ, each transmitter transmits all available data constantly without waiting for a NACK. To prevent buffer overflow at the receiving nodes, a sliding window of size W described above is used. SR ARQ uses NACKs rather than ACKs indicating which packets should be retransmitted. When a NACK arrives, the source retransmits only the NACK’ed packets.

In our version of SR ARQ, the receiver sends a single NACK packet for every batch of K newly received packets. That is, duplicate packets are not counted for NACK triggering. Each NACK packet comprises the list of SN requested by the receiver along with the highest SN received. Thus, NACKs are sent also if packets are not lost. Furthermore, from the highest SN received and the NACK’ed packets, the source can compute the receiver buffer occupancy and maintain a count of the unacknowledged packets.

Additionally, to save unnecessary retransmissions, the receiver maintains the number of NACKs sent for each packet and limits its number by some upper bound N(β) derived below. Note that unlike with other protocols, the maximum number of retransmissions cannot be controlled by the source.

Timeout can be controlled either by the transmitter or by the receiver. When a timeout fires at the receiver, it retransmits its last NACK; when a timeout fires at the transmitter, it returns to its transmission state at the last received NACK.

Buffer occupancy of SR ARQ and GBN ARQ described below have been derived in [12] and [23]. Here, we derive its energy-consumption.

The E2E SR ARQ protocol label is denoted by π = srARQ with a superscript of e2e, and let K denote the batch size of each NACK. Although the protocol uses some sliding window of size W, the window size is irrelevant for deriving the limit on the number of transmissions and retransmissions, L e2esr (β), since only failed packets are retransmitted.

Let \(a = 1-\prod_{i=0}^{h-1}\bar{p}_i, b = 1-\prod_{i=0}^{h-1}\bar{q}_i\) and Define,

$$ \begin{aligned} E[X_0] &= \!\!\! \sum_{n=1}^{L_{\rm sr}^{e2e}(\beta)+1} a^{n-1} \sum_{k=n-1}^{L_{\rm sr}^{e2e}(\beta)} \!\!\! \left(\begin{array}{cc} L_{\rm sr}^{e2e}(\beta)\\ k\\ \end{array}\right) (1-b)^k b^{L_{\rm sr}^{e2e}(\beta)-k} \\ E[Y_h] &= \sum_{n=1}^{L_{\rm sr}^{e2e}(\beta)} a^{n} \sum_{k=n-1}^{L_{\rm sr}^{e2e}(\beta)} \left(\begin{array}{c} L_{\rm sr}^{e2e}(\beta)\\ k\\ \end{array}\right) (1-b)^k b^{L_{\rm sr}^{e2e}(\beta)-k}. \end{aligned} $$

Proposition 6

For the E2E SR ARQ protocol, \(L_{\rm sr}^{e2e}(\beta) = \left \lceil {\frac{\log\left(1 + (1-a) - \beta\right)}{\log\left(a(1-b) + b\right)}}\right\rceil, \) and

$$ \begin{aligned} E_{\rm srARQ}^{e2e}(\beta) =\;& E[X_0] \left(1+ \sum\nolimits_{i=0}^{h-2} \prod\nolimits_{k=0}^i \overline{p}_k \right)\\ &+ E[Y_h] \left(1+\sum\nolimits_{i=1}^{h-1} \prod\nolimits_{k=1}^i \overline{q}_{h-k}\right)/K. \end{aligned} $$
(6)

Proof

The proof is given in [13].

3.7 The energy-efficiency of HBH SR ARQ: E srARQ

The HBH SR ARQ protocol label is denoted by π = srARQ. The expected number of transmissions for each hop with HBH SR ARQ, E srARQ, is a special case of E2E SR ARQ with h = 1. The total number of expected transmissions is

$$ E_{\rm srARQ} = h [E_{\rm srARQ}^{e2e}|_{h=1}] $$
(7)

3.8 Energy efficiency of E2E GBN ARQ: E e2egbnARQ

With GBN ARQ, each transmitter transmits continuously all available data using a sliding window of size W described above. To save energy, the receiver sends a single ACK packet for every batch of K packets received successfully. The ACK specifies the next expected SN packet implying that all packets with lower SNs have been received. Upon receiving an ACK, the transmitter backs to the expected packet and retransmits that packet and all the following packets.

Although a reliability level less than one may be required, GBN cannot limit the number of retransmissions due to its inherent structure. Thus, the protocol may transmit more packet than its reliability level requires.

Since the transmitter backs to the packet specified by the ACK, the receiver is not required to buffer packets received out of order. The transmitter, on the other hand, is required to buffer all un-ACK’d packets.

The E2E GBN ARQ protocol label is denoted by π = gbnARQ with a superscript of e2e, the sliding window size is set to W and the batch size of each ACK is set to K. Note that when the batch ACK size K > 1, the relation between RTT and the ideal W should given in multiples of K packets since the receiver waits for K new packets before transmitting an ACK. Ideally, given RTT and K, the ideal W is the number of batches, each of which comprise K packets, that can be transmitted during RTT. Implied is that W = n × K, for some positive integer n. Also recall that with E2E GBN ARQ. setting a maximum number of retransmissions per packet is infeasible.

Propostion 7

For the E2E GBN ARQ protocol,

$$ \begin{aligned} E_{\rm gbnARQ}^{e2e} =\,& {\frac{1}{\prod_{i=0}^{h-1} \bar{p}_i^W \bar{q}_i}} \left[ 1+ {\sum_{i=0}^{h-2} \prod_{k=0}^i} \bar{p}_k^W \right.\\ &+ \left. {\frac{(\prod_{k=0}^{h-1} \bar{p}_k^W)}{K}} \left(1 + {\sum_{i=0}^{h-2} \prod_{k=0}^i} \bar{q}_{h-1-k}\right) \right]. \end{aligned} $$
(8)

Proof

The proof is given in [13].

3.9 Energy efficiency of HBH GBN ARQ: E gbnARQ

The HBH GBN ARQ protocol label is denoted by π = gbnARQ.

The expected number of transmissions for each hop with HBH GBN ARQ, E gbnARQ, is a special case of E2E GBN ARQ with h = 1. The total number of expected transmissions is

$$ E_{\rm gbnARQ} = h [E_{\rm gbnARQ}^{e2e}|_{h=1}] $$
(9)

4 Simulations and performance analysis

Extensive simulations are conducted to verify our analytical models and gain further insight into the problem. Detailed performance analyses lead to the optimal design of the eESRT + ieARQ protocol.

4.1 Simulation settings

The simulation setup consists of a sensor field of 73 nodes using ns-2. These nodes are deployed in nine concentric circles centred at the sink. The nodes are positioned on the spokes originating from the sink. The spokes are at 45 degrees from each other. We used the destination-sequenced distance-vector (DSDV) routing protocol and the two-ray ground propagation model with controlled packet loss rate in each hop. The radio interface in our simulation is 802.11 DCF MAC with RTS/CTS disabled for packets of size 40 bytes.

Every node generates packets at rate 0.5 per second. The traffic is scheduled such that each spoke takes turn to transmit eliminating any potential interference. Note that such light traffic model is typical for WSN applications. It reduces the collision and congestion effect, not included in our analytical model.

Recall that we propose to tune the maximum number of retransmissions ( RetryLimit in 802.11) in order to achieve a predetermined reliability level β. In WSN the maximum number of transmissions is also affected by link loss rate. In the simulations, the actual link packet loss has been estimated and the maximum number of transmission, L π(p, β), is set as function of the actual link loss p and the target reliability β. We have verified that the realised reliability for each simulation run was above the target β. For ARQ-related protocols, the retransmission timeout is set to be twice the CSMA backoff period.

The purpose of the simulation is to validate our theoretical results for symmetric and asymmetric links for the symmetry case. Thus, the simulations are done for symmetric links only. However, note that our field trails, described in Sect. 5, do contain asymmetric links; and they demonstrate the correctness and effectiveness of our proposed scheme for the asymmetric case. In our ns-2 simulation, the link loss is assumed symmetric since asymmetric links are hard to simulate without changing the ns-2 module propagation code. For this paper simulation, we focused on layer 2 and above, without modifying the physical layer code.

4.2 Performance comparisons

Simulation results on the expected number of transmissions are depicted in Figs. 2, 3, 4 along with the analytical model predictions. All simulation results, for ESRT, SW HBH ARQ, SW HBH ieARQ, are obtained with a 95% confidence interval. It can be seen that our models predict the number of transmissions with reasonable accuracy. Beside model verification the ns-2 simulations also provide insight into the energy efficiency performances of reliable data transport protocols.

With respect to energy-efficiency, it is expected that SR HBH ARQ (srARQ) is the most energy efficient. This is indeed confirmed by the graphs generated by our analysis as shown in Figs. 2, 3, 4. These figures demonstrate clearly that srARQ outperforms all other protocols across the board. For reliable links, i.e., p i  = q i ≤ 0.01, ESRT is equally efficient for path lengths smaller than some threshold. For p i  = q i  = 0.01, the threshold is six hops and for p i  = q i  = 0.005, the threshold is 11 (not shown in the figures).

Fig. 2
figure 2

Energy efficiencies for p = 0.05

Full size image
Fig. 3
figure 3

Energy efficiencies for p = 0.20

Full size image
Fig. 4
figure 4

Energy efficiencies for p = 0.45

Full size image

Although the figures are depicted for statistical reliability of β = 0.95, spatial dependency r i  = 0.7, packet error rates in both directions p i =qi=p,   where p = 0.05, 0.20, 0.45, ACK/NACK batch size of K = 4, and a sliding window size of W = 12, the relative merit of each protocol is similar for all practical set of parameters.

For some WSNs, srARQ may incur too high buffer and processing penalties. For such WSNs, ieARQ emerges as the most energy efficient protocol except for path lengths less than some threshold, where ESRT is better. The threshold depends on the link reliability. For p i  = q i  = 0.01, ESRT is better for path lengths less than or equals five; For 0.01 ≤ p i  = q i  < 0.45, ESRT is better for a single hop path; and for p i  = q i ≥ 0.45, ESRT is always worse. The dominance of ESRT for short paths when the links is very reliable is explained by the fact that the required number of redundant sensed data can be predicted well and trades-off the overhead of the ACK at the sink node.

4.3 The eESRT + ieARQ algorithm

When srARQ is not a feasible option, the performance comparisons presented in Sect. 4.2 suggests that a hybrid protocol mixing ESRT and ieARQ can perform better than a pure protocol. From the nature of ESRT, it must start at the sensor source where data is sampled. After H_sw hops, which depends on the path length and link error rate, it proceeds with ieARQ. The ieARQ adapts the maximum number of retransmissions in each hop based on the channel error estimations in order to reach a predetermined statistical reliability threshold β. These path length and link quality measures are readily available in most routing protocols such as [22].

The energy efficient and statistically reliable transport with implicit and explicit ARQ (eESRT + ieARQ) protocol is given by the following pseudo code:

eESRT+ieARQ algorithm

p = link_estimate(nexthop);

if (p < 0.01)

  H_sw = 5;

else if (p < 0.45)

  H_sw = 1;

else

  H_sw = 0;

hop = packet->hopcount;

N4_beta = 1; n_trans = 1;

if (hop > H_sw)

  L_beta = log(1-beta^(1/hop))/log(p);

while (n_trans < L_beta) {

    send(nexthop, packet);

    n_trans++;

    timer(wait_for_ieACK);

} // maximum retransmission reached

send(nexhop, packet);

// last transmission without ACK

The simulated average packet delay and energy efficiencies with their 95% confidence interval using ESRT, SW HBH ARQ, SW HBH ieARQ, and the proposed Hybrid eESRT + ieARQ are depicted in Figs. 5, 6 7, 8 for p i  = q i  = 0.05, 0.20, 0.45. The figures demonstrate that ESRT is best with respect to packet delay. Again the simulation results match our theoretical predictions in Fig. 8. Note that there are marginal differences for a loss rate of 50% when the path length exceeds five hops. The debug log generated by ns-2 simulator reveals that packet contention and “race condition” in those cases become an issue due to excessive retransmissions. These practical issues are not considered in our theoretical analysis.

Fig. 5
figure 5

Average packet delay for p = 0.05

Full size image
Fig. 6
figure 6

Average packet delay for p = 0.20

Full size image
Fig. 7
figure 7

Average packet delay for p = 0.45

Full size image
Fig. 8
figure 8

Energy efficiencies of x ARQ protocols

Full size image

These simulation and theoretical results show that the combined implicit and explicit ARQ (ieARQ) scheme overcomes the “avalanche” effect efficiently. These results also demonstrate the advantages of eESRT + ieARQ not only in boosting total energy efficiency, but also in reducing end to end delay.

5 The Field trials

Field trials were conducted outdoor in an open yard, with five MICA2 motes placed in a line 20 m apart. The motes were elevated to 1 m above ground, with transmission power set to 0dBm. We first measured the loss rate of each hop by programming each node to broadcast 3,000 beacon packets to neighbors. The loss rate measured at each hop for each direction is shown in Fig. 9.

Fig. 9
figure 9

Experiment setup

Full size image

Three sets of experiments were conducted.

  • The first experiment is with ESRT (Proposition 1). The actual realized loss rates in the experiment at respective hops were:

    • p = (0.69, 0.19, 0.36, 0.0).

  • The second experiment is with ARQ (Proposition 3). The actual realized loss rates were:

    • p = (0.41, 0.26, 0.34, 0.01), and

    • q = (0.01, 0.5, 0.999, 0.02).

  • The third experiment is SW HBH implicit and explicit ARQ (ieARQ) (Proposition 5). The actual realized loss rates were:

    • p = (0.44, 0.07, 0.15, 0.00), and

    • q = (0.03, 0.26, 1 − 10−6, 0.00).

The experiment results in energy efficiency are shown in Fig. 10 comparing with theoretical analysis. Due to reception variations in different experiments, it is impossible to compare all the protocols under the same conditions as we did in our simulations. We still find the resulting trends from these experiments follow theoretical predictions reasonably well.

Fig. 10
figure 10

Experiment results

Full size image

From the experiments, ESRT is best for 1–2 hops. For longer paths, ARQ has its merit, but ieARQ is the most efficient protocol. These results reaffirm the energy efficiency advantage of the eESRT + ieARQ design.

6 Conclusions

We introduced a new notion of statistical reliability for WSN applications. This signifies a new QoS measure that allows WSN users to control the balance between energy efficiency and data reliability. Under this new paradigm, we conducted rigorous energy efficiency analysis on a comprehensive set of data transport protocols. Our theoretical models were confirmed by extensive simulations and field trials. Performance analyses provided insight into the relationship between energy efficiency and reliability. Based on the gained insight, we designed an optimal strategy that adaptively switches between eESRT and ieARQ to achieve energy efficiency under a statistical reliability constraint. This eESRT + ieARQ protocol is proved to outperform other feasible protocols in energy efficiency, delay reduction, and in overcoming the “avalanche” effect.