1

Bitwise Retransmission Schemes for Resources
Constrained Uplink Sensor Networks

arXiv:1707.09696v1 [cs.IT] 31 Jul 2017

Mohamed A. M. Hassanien, Pavel Loskot, Salman M. Al-Shehri, Tolga Numanoǧlu, and Mehmet Mert

Abstract—Novel bitwise retransmission schemes are devised
which retransmit only the bits received with small reliability.
The retransmissions are used to accumulate the reliabilities
of individual bits. Unlike the conventional automatic repeat
request (ARQ) schemes, the proposed scheme does not require
a checksum for the error detection. The bits to be retransmitted
are reported as a combination number, or two synchronized
random number generators (RNGs) at the transmitter and
receiver are used to greatly compress the feedback message.
The bitwise retransmission decisions and/or combining can be
performed after the demodulation or after the channel decoding
at the receiver. The bit-error rate (BER) expressions are derived
for the case of one and two retransmissions, and verified by
computer simulations. Assuming three specific retransmission
strategies, the scheme parameters are optimized to minimize
the overall BER. For the same number of retransmissions and
packet length, the proposed schemes always outperform the
frequently used stop-and-wait ARQ. The impact of feedback
errors is also considered. Finally, practical designs of the bitwise
retransmissions for data fusion from sensor nodes in Zigbee, Wifi
and Bluetooth networks are presented.
Index Terms—Automatic repeat request, data fusion protocol,
feedback signaling, performance analysis, retransmissions.

I. I NTRODUCTION
It is well-known that feedback cannot improve the information theoretic capacity of memoryless channels [1]. However, the availability of feedback can greatly simplify the
encoding and decoding complexity [2]. A good example of
such schemes with the reduced implementation complexity
due to feedback are the ARQ retransmission schemes [3],
[4]. The retransmission schemes are optimized to trade-off
the reliability (e.g., the BER), the throughput (or equivalently,
delay) and the implementation complexity [5] or the energy
consumption [6]. For instance, the retransmissions can comprise a smaller number of bits than in the original packet.
The incremental redundancy hybrid ARQ (IR-HARQ) or typeII HARQ schemes progressively reduce the coding rate of
the forward error correction (FEC) code with each additional
retransmission at the expense of increasing the decoding
delay and reducing the throughput [7]. The retransmission
decision delays in HARQ schemes were reduced in [8] by
exploiting the structure of tail-biting convolutional codes. The
permutations of bits in the retransmitted packets are used in
MAH, PL and SMA are with the College of Engineering, Swansea
University, Bay Campus, Swansea SA1 8EN, United Kingdom (email:
{mohmmedali25,salman777881}@hotmail.com, p.loskot@swan.ac.uk)
TN and MM are with Aselsan A.S., Communications and IT Division,
Ankara, Turkey (email: {tnumanoglu,mmert}@aselsan.com.tr)
Corresponding author: Pavel Loskot, tel.: +44 1792 602619, fax: +44 1792
295676

[9] and [10] to improve the reliability of ARQ schemes. A
holistic design of the complexity-constrained type-II hybrid
ARQ schemes with turbo codes is considered in [11]. The joint
design of FEC coding for forward data delivery and reverse
feedback signaling is studied in [12] and [13]. The IR diversity
and the time-repetition (TR) diversity are compared in [14].
The time and superposition-coding packet sharing between
two independent information flows is optimized in [15]; the
latter is shown to have a slightly better performance at the
expense of larger design and implementation complexity. Such
transmission sharing strategies can significantly outperform
the conventional HARQ schemes when signal-to-noise ratio
(SNR) is sufficiently large [15]. Assuming Gaussian transmission codebooks, the achievable throughput of the HARQ
schemes are compared to the ergodic channel capacity in
[15], and to the delay-limited channel capacity in [14]. The
transmission powers of ARQ schemes are optimized in [14].
Since the received packets typically contain only a few
transmission errors, the retransmission efficiency can be improved by the partial ARQ schemes [16]. A truncated type II
hybrid ARQ over block fading channels is considered in [17].
In addition to ARQ schemes exploiting a variable number
of retransmissions, the variable rate ARQ schemes optimize
the number of bits in each retransmission [14], [18], [19].
The number of retransmission bits required for a successful
decoding is estimated from the mutual information in [19]
and [15]. The pre-defined retransmission patterns are assumed
in [16]. The reactive rate-adaptive ARQ strategies [7] usually
outperform the proactive strategies [18]. The FEC coding
to recover from the transmission errors may be preferred
to the ARQ retransmissions in case of multimedia [20].
Except the stop-and-wait ARQ schemes, the go-back-N ARQ
retransmissions are optimized, for example, in [21]. A multibit feedback signaling to improve the ARQ performance is
considered in [22] and [15]. Other papers account for more
realistic design constraints such as a noisy feedback [14], [17],
and the channel estimation in [16]. It is shown in [14] that the
errors of 1 and 2-bit feedback messages can be neglected if
their bit error probability is less than 10−3 , or if these errors are
compensated by a non-uniform allocation of the transmission
powers. Furthermore, the repetition diversity appears to be
more robust to feedback errors than the IR-HARQ [14].
In our conference paper [22], we assumed a multi-bit
error-free feedback to evaluate the performance trade-offs
between the throughput and the reliability of the segmentationbased and the bitwise ARQ retransmission schemes. Both
schemes were found to outperform the stop-and-wait ARQ
with the bitwise ARQ providing larger reliability gains than

2

the segmentation-based ARQ, albeit at the expense of a greater
complexity of the feedback signaling. In this paper, we revisit
the selective bitwise retransmission scheme proposed in [22] to
carry out more rigorous performance analysis and to optimize
its design. Recall that the proposed scheme aims to accumulate
the reliabilities of the least reliable individual bits in the
received packet, so it does not require the cyclic redundancy
check (CRC) bits to make the retransmission decisions. It
can be combined with other FEC coding schemes where
the bit reliability is evaluated either before or after the FEC
decoding. From the implementation point of view, it is useful
to keep the number of retransmitted bits as well as the
number of retransmissions constant, for example, to maintain
a constant transmission delay and throughput for each data
packet. However, a variable rate scheme that retransmits all
bits having their reliability below a given threshold is also
investigated. The bits with small reliabilities are reported back
to the sender using either a binomial combination number,
or using a deterministic sequence of bit-permutations. Our
analysis assumes multi-bit error free feedback signaling, however, we also evaluate the conditions when such assumption
is justifiable. Finally, we consider a more specific systemlevel design of the proposed bitwise retransmission scheme
to be employed in an uplink data collection scenario from
the resources-constrained sensors to a data fusion access point
assuming time-sharing of the transmission channel among the
network nodes. The resulting transmission protocol creates
fully occupied packets with the retransmitted bits having a
higher priority than the newly arrived information bits.
The rest of this paper is organized as follows. System model
is introduced in Section II. The mathematical theoretic analysis
of the proposed bitwise retransmission scheme is carried out
in Section III. The retransmission protocols are presented and
optimized in Section IV. The uplink data fusion bitwise ARQ
scheme is designed in Section V. Conclusions are given in
Section VI.

The design and analysis of the proposed bitwise retransmission scheme assumes a point-to-point duplex communication
link between a source node and a destination node. As shown
in [14], the feedback errors in ARQ schemes can be neglected
provided that their probability of error is sufficiently small.
Hence, in our analysis, we assume the error-free feedback,
and in Section IV, we estimate the acceptable probability
of feedback bit errors when such assumption is justified in
practice.
Assuming that M-ary modulation is used for transmission
from the source to the destination node, prior to the FEC
decoding, the reliability of the received bit bi can be calculated
as [23],
Pr(bi = 0|y)
, i = 1, 2, . . . , log2 M
Pr(bi = 1|y)

where h is a residual attenuation, possibly after the (multipath)
equalization, and w is a zero-mean sample of AWGN. The loglikelihood ratio (LLR) (1) can be then rewritten as,

∑s∈S(bi =0) exp −|y − hs|2/N0
(2)
Λ(bi |y) = log
∑s∈S(bi =1) exp (−|y − hs|2/N0 )
where the M-ary modulation constellation is partitioned as,
S = S(bi = 0) ∪ S(bi = 1), depending on the value of the i-th
bit bi in modulation symbols, N0 is the power spectral density
of the AWGN, and | · | denotes the absolute value.
The LLR (1) can be also used as the soft-input decisions
to the FEC decoder. On the other hand, we can also use the
soft-output decisions produced by the decoder to make the
retransmission decisions. In this case, the sums in (2) are
done over the corresponding codewords mapped to sequences
of M-ary modulation symbols, and the sums in (2) are often
approximated using the formula, log ∑i exp(−ai ) ≈ min(ai ).
In order to simplify the analysis and illustrate the main
concepts, in the sequel, we consider a binary antipodal
modulation. Generalization to higher order modulations is
straightforward by scaling the demodulated binary symbols
by appropriate constants computed for a given M-ary modulation√scheme. Hence, √
assume the transmitted binary symbols
S1 = Eb and S2 = − Eb , so the received N-bit packet can
be written as,
ri = S ji + wi , i = 1, 2, . . . , N
where S ji ∈ {S1 , S2 }, and the zero-mean
AWGN samples wi

have the constant variance, E |wi |2 = σ2w = N0 /(2|h|2 ). Then,
the reliabilities of the received bits are [23],
Λ(bi |ri ) ∝ |ri /σw | ≡ |r̄i |.

II. S YSTEM M ODEL

Λ(bi |y) = log

the reception of modulation symbols can be mathematically
modeled as,
y = hs+ w

(1)

where y is the received M-ary modulation symbol. For equally
probable modulation symbols, assuming coherent detection
in a channel with additive white Gaussian noise (AWGN),

Finally, the SNR per binary modulation symbol is defined
as γb = Eb /N0 . If Rf denotes a fraction of information bits
in the sequence of all bits transmitted from the source to the
destination, for a fair comparison of different schemes with
various rates Rf , we assume the SNR per bit, γb = Eb Rf /N0 .
A. Bitwise retransmissions
After the initial transmission of N-bit data packet, the
destination uses the received bit reliabilities to decide which
Wd binary symbols among N received, 0 ≤ Wd ≤ N, should be
retransmitted, where d = 1, 2, . . . , D denotes the retransmission
index. The retransmission request is a feedback message of
Cd ≥ 1 bits sent to the source node from the destination
node via a reverse (feedback) link. Consequently, after D
retransmissions, the total number of bits sent over the forward
link to the destination is,
D

Nf = N +

∑ Wd
d=1

3

C1

N
t0

C2

W1
t1

t1 + T1

CD

W2
t2 + T2

t2

reverse
link
WD

t3

forward
link

t
tD + TD tD+1

Figure 1. The timings of the proposed bitwise retransmission protocol.

whereas the total number of bits sent from the destination to
the source over the reverse link is,
D

Nr =

∑ Cd .
d=1

For instance, the conventional stop-and-wait ARQ scheme
has the parameters Wd = N and Cd = 1 (ACK or NACK).
The retransmitted bits are combined using a maximum ratio
(MRC) or other combining method to improve their reliability.
The timings of the bitwise retransmission protocol are shown
in Fig. 1 where Td represents the delay until the start of
transmission of the window of Wd retransmitted bits. The
forward transmission rate is then defined as,
N
N
Rf (D) =
(3)
=
N
W
N + ∑D
f
d=1 d
and the reverse transmission rate is defined as,
Nr
∑D
d=1 Cd
.
Rr (D) =
=
D
N + Nr
N + ∑d=1 Cd
Note that the feedback delays Td are not included in the
definition of these rates, since during these time intervals,
both forward and reverse links are possibly available for other
transmissions.
In order to simplify the notation, let W1 = W2 = . . . = WD =
W , and C1 = C2 = . . . = CD = C, and we drop the bit index
within the packet unless stated otherwise. The W least reliable
bits requested for the next retransmission can be identified by
sorting the received bits by their reliabilities. A typical sorting
algorithm has the complexity O(N log N) [24]. The locations
of these W bits within the packet of N bits can be reported
back to the sender by the corresponding binomial number. The
number of bits representing such feedback message is,
 

N
C = log2
W

N
where W
is the binomial number, and ⌈·⌉ is the ceiling
function. More importantly, even though typically C > W , we
always have that, Rf ≫ Rr , as in many other ARQ protocols.
Thus, the multi-bit feedback can be very beneficial to improve
the performance of ARQ protocols [22].
III. P ERFORMANCE A NALYSIS
Given the values of N, W , C, D and γb , we now derive the
average BER of the proposed bitwise retransmission scheme.
We first assume the case of a single retransmission, i.e., D =
1. We optimize the number of feedback message bits C the
forward throughput Rf to minimize the BER, and compare
our scheme to the conventional stop-and-wait ARQ. We then

perform the similar analysis for D = 2 retransmissions before
generalizing the obtained BER expressions to the case of D > 2
retransmissions.
Without any retransmissions (i.e., immediately after the new
data packet of N bits was received), the conditional probability
density function (PDF) of the received bit reliability r̄ can be
written as,
r
√ 2
Eb )
1 No − (r̄No −2
4N
o
e
fr̄ (r̄|S1 , D = 0) =
2r π
√ 2
Eb )
1 No − (r̄No +2
4N
o
fr̄ (r̄|S2 , D = 0) =
e
.
2 π
Since the bits are selected for retransmission based on
their reliability, we first obtain the BER conditioned on the
reliability interval, LD ≤ |r̄| ≤ UD , for some positive constants
UD ≥ LD ≥ 0. This BER is equal to the probability of the error
event ‘ e’ that S1 was transmitted, however, S2 is decided at
the receiver when −UD ≤ r̄ ≤ −LD . With no retransmissions,
the probability of such error event is equal to,

Pr ( e|S1 , D = 0) = Pr −U0 ≤ r̄ ≤ −L0 S1
Z −L0 √Eb

fr̄ (r̄|S1 , D = 0) dr̄
=
√
−U E

 0  b



p
p
L0
U0
2γb
2γb
=Q
+1
−Q
+1
2γb
2γb
R

2

where Q(x) = x∞ √12π e−t /2 dt is the Q-function, and due
to symmetry, we have, Pr (e|S1 , D = 0) = Pr (e|S2 , D = 0).
Assuming the a priori transmission probabilities, Pr (S1 ) =
Pr (S2 ) = 1/2, the overall average BER for L0 = 0 becomes,



p 
p
U0
2γb − Q
2γb
+1
.
(4)
BER0 = Q
2γb

Note that, for U0 → ∞, the BER (4) corresponds to the
√ BER of
uncoded binary antipodal signaling, i.e., BER = Q( 2γb ) [3].
Subsequently, the probability that the reliability of the received
bit is in the interval LD ≤ |r̄| ≤ UD without any retransmissions
is computed as,


P0|S1 = Pr L0 ≤ |r̄| ≤ U0 S1
Z −L0

Z U0

fr̄ (r̄|S1 , D = 0) dr̄
fr̄ (r̄|S1 , D = 0) dr̄ +
L0
−U0






p
p
L0
U0
2γb
2γb
= Q
+1
−Q
+1
+
2γ
2γ
 b
 b




p
p
L0
U0
−1
−Q
−1
.
Q
2γb
2γb
2γb
2γb

=

For L0 = 0, this probability is equal to,






p
p
U0
U0
P0|S1 = 1−Q
2γb
2γb
+1 −Q
−1
2γb
2γb

and P0|S1 → 1 for U0 → ∞. Due to symmetry, and for equally
probable symbols Si , we get, P0 = P0|S1 = P0|S2 . Furthermore,
if Z is the (random) number of bits having the reliabilities in
the interval, 0 ≤ |r̄| ≤ U0 , the mean value of Z, E[Z] = N P0 ,
can be used to optimize the retransmission window size. For
example, by letting W = E[Z], we can control the target BER
after the first retransmission.

4

In general, it is convenient to re-scale the received bits
after every retransmission and subsequent MRC combining to
maintain the constant average energy of the received symbols.
In particular, the received symbol after combining the initially
received sample r̄0 with the retransmitted and scaled samples
r̄d , d = 1, 2, . . . , D, can be written as,
!
D
1
r̄MRC =
r̄0 + ∑ r̄d .
D+1
d=1
In the sequel, let Ld = 0 for ∀d ≥ 0, and, without loss of
generality, we assume that the packet of N symbols S1 was
transmitted.

In the appendix, we show that BER1 can be accurately
approximated as,


p 
p
U0
+ 1) + Q
2γb (
4γb −
BER1 ≈ Q
2γb
n

2
√ 
Ak
−α− (U )γ
∑ √1 + 2Bk e k,1 0 b Q β+k,1 (U0) γb +
k=1

+
√ o
e−αk,1 (U0 )γb Q β−
k,1 (U0 ) γb

where the coefficients Ak and Bk , are given in the appendix,
and the auxiliary functions,
α−
k,d (U) =

A. BER with one retransmission
After the first transmission of the packet of N bits, only
those bits that have the reliabilities in the interval 0 ≤ |r̄| ≤ U0
are requested to be retransmitted. After the first retransmission,
the bit samples are combined as,
 1
2 (r̄0 + r̄1 ) for |r̄0 | ≤ U0
r̄MRC =
r̄0
for |r̄0 | > U0 .
The random variable r̄0 has the PDF, fr̄ (r̄|S1 , D = 0), whereas
the PDF of the random variable r̄1 can be obtained by
conditioning on |r̄0 | ≤ U0 . Since the random received samples
r̄0 and r̄1 are statistically independent, the PDF of r̄MRC is
given by the convolution (denoted as ∗), i.e.,
fr̄MRC (r̄|S1 , D = 1) =
where

fr̄ (r̄|S1 , d = 0)φ1 (r̄,U0 )
 ∗ fr̄ (r̄|S1 , d = 0)
Pr |r̄0 | ≤ U0 S1 , D = 0

φ1 (r̄,U0 ) = η(r̄ + U0 ) (1 − η(r̄ − U0))
and η(r̄) is the unit-step function, i.e., η(r̄) = 1 if r̄ ≥ 0, and
0 otherwise. After some manipulations, the PDF of r̄MRC can
be written as,
fr̄MRC (r̄|S1 , D = 1) =

χ1 (r̄,U0 )

Pr |r̄0 | ≤ U0 S1 , D = 0

where we defined the function,

χd (r̄,U0 )

=

r

r
2

γ
r̄−2 Nb
o
−
4
(d+1)No

1 (d + 1)No
e
×
4
!
rπ
n
(d + 1)No
(U0 − r̄) +
erf
4d
!
r
o
(d + 1)No
erf
(U0 + r̄)
4d

and erf(·) denotes the error function [3].
Assuming that all bits with the reliabilities |r̄0 | ≤ U0 are
retransmitted, and then combined using the MRC, the overall
BER1 after the first retransmission is computed as [3],
BER1

=

=

Pr (e|d = 0, S1 ) Pr (d = 0|S1 ) +
Pr (e|d = 1, S1 ) Pr (d = 1|S1 )
Z −U0
−∞

fr̄ (r̄|S1 , d = 0) dr̄ +

Z 0

−∞

χ1 (r̄,U0 ) dr̄.

α+
k,d (U) =
β−
k,d (U) =

Bk (d + 1)(2 − U/γb)2
2d(1 + 2Bd k )

Bk (d + 1)(2 + U/γb)2

1 − BdγkUb
r
,
2B

1+ d k
2(d+1)

2d(1 + 2Bd k )
β+
k,d (U) =

1 + BdγkUb
r
.
2B

1+ d k
2(d+1)

B. BER with two retransmissions
Consider now the case with two retransmissions. After the
second retransmission, the received bits having the reliabilities
|r̄| ≤ U1 are combined with the retransmitted samples r̄2 . The
threshold value U1 is chosen to be greater than U0 due to improvement of the bit reliabilities after the first retransmission.
More generally, we assume that,
UD−1 ≥ UD−2 . . . ≥ U1 ≥ U0 .
Hence, the bit-samples after two retransmissions can be written
as,
 1
(r̄0 + r̄1 + r̄2 ) for |r̄0 | ≤ U0 , 21 |r̄0 + r̄1 | ≤ U1


 3 1
for |r̄0 | ≤ U0 , 12 |r̄0 + r̄1 | > U1
2 (r̄0 + r̄1 )
r̄MRC =
1

for U0 < |r̄0 | ≤ U1

2 (r̄0 + r̄2 )

r̄0
for |r̄0 | > U1 .
(5)
However, in order to make the analysis mathematically
tractable, we merge the first two conditions in (5), and consider
instead the retransmission scheme,
 1
 3 (r̄0 + r̄1 + r̄2 ) for |r̄0 | ≤ U0
1
r̄MRC =
(6)
for U0 < |r̄0 | ≤ U1
2 (r̄0 + r̄2 )

r̄0
for |r̄0 | > U1

having the upper-bound performance than the scheme (5). The
scheme (6) can be interpreted as making the decision about the
number of retransmissions for each bit already after receiving
the initial data packet of N bits. Even though the scheme (6)
may unnecessarily retransmit some bits even if their reliability
have already reached the desired threshold, our numerical
results indicate that, for D = 2, the performance difference is
not significant (less than 1 dB). Consequently, the number of
retransmissions for each bit can be determined by quantization
of the initial reliabilities |r̄0 | using the thresholds U0 and U1 .
The bits having the reliabilities |r̄0 | ≤ U0 are always combined
with two other retransmitted bits, whereas the received bits

5

with the reliabilities U0 < |r̄0 | ≤ U1 are combined with exactly
one retransmission.
The PDF fr̄MRC (r̄|S1 , d = 2) of r̄MRC , for |r̄| ≤ U0 , is given
as,
χ1 (r̄,U0 )

fr̄MRC (r̄|S1 , d = 2) =
Pr |r̄0 | ≤ U0 S1 , d = 0
and for U0 < |r̄0 | ≤ U1 , it is given as,
fr̄MRC (r̄|S1 , d = 2) =
where
λd (r̄,Ud ,Ud−1 ) =
( q
erf

1
4

q

λ1 (r̄,U1 ,U0 )

Pr U0 < |r̄0 | ≤ U1 S1 , d = 0

(d+1)No
π

exp −



r̄−2

q

γb
No

4
(d+1)No

2 !

×


q

(d+1)No
(d+1)No
(Ud + r̄) + erf
(Ud − r̄) −
4d
4d


q
)
q
(d+1)No
(d+1)No
(Ud−1 + r̄) −erf
(Ud−1 − r̄) .
erf
4d
4d

For |r̄0 | > U1 , the PDF fr̄MRC (r̄|S1 , d = 2) is given by the PDF
fr̄ (r̄|S1 , d = 0). The overall BER2 is obtained using the law of
the total probability, i.e.,
2

BER2

=

∑ Pr (e|d, S1) Pr (d|S1) =
d=0

+

Z 0

−∞

Z −U1
−∞

λ1 (r̄,U1 ,U0 ) dr̄ +

fr̄ (r̄|S1 , D = 0) dr̄

Z 0

−∞

where the auxiliary functions,
θ+−
k,d (U)

=

D −U)
√
+ √1N + Bk (U
d γb

U
√D
2 γb

1+ d k
(d+1)No
D +U)
√1 + Bk (U√
d γb
No

−

2B

1+ d k
(d+1)No
U
√D
2 γb

D +U)
√
+ √1N + Bk (U
d γb
o

2B

1+ d k
(d+1)No

=

|µ(U)|
2

µ(U) =

UD
√ −
γb

θ−−
k,d (U)

o

2B

θ−+
k,d (U) =

θ++
k,d (U) =

U
√D
2 γb

r

(d + 1)No (1 +

√2
No

2Bk
)
d

√kU
+ 2B
γb

1 + 2Bk

and sign(·) is the sign function.
C. BER with multiple retransmissions
For D ≥ 1 retransmissions, the overall BER is calculated as,
D

BERD =

∑ Pr (e|d, S1) Pr (d|S1) .
d=0

χ2 (r̄,U0 ) dr̄

where the probability of the second retransmission
of the

same bit is, Pr (d = 2|S1 ) = Pr r̄ ≤ −U1 S1 , d = 1 . As for one
retransmission, BER2 can be approximated (see the appendix),
√

√ 
U1
BER2 ≈ Q 2γb ( 2γ
+
1)
+ Q 6γb
nb −

√ 
−α (U )γ
Ak
(U
)
e k,2 0 b Q β+
γb
− ∑2k=1 √1+B
0
k,2
k

o
√
−α+
(U
)γ
+ e k,2 0 b Q β−
k,2 (U0 ) γb
n

√ 
−α−
(U
)γ
2 √ Ak
+ ∑t=1 1+2B e k,1 0 b Q β+
(U
)
γb
0
k 
 k,1
√
−α+
(U
)γ
+ e k,1 0 b Q β−
(U0 ) γb
 k,1
√ 
−α−
(U
)γ
+
1
b
− e k,1
Q βk,1 (U1 ) γb

√ o
−α+ (U )γ
− e k,1 1 b Q β−
.
k,1 (U1 ) γb

Recall that, for the sake of mathematical tractability, we
assume that the received bits with their initial reliability within
the interval |r̄| ≤ U0 will be retransmitted D times, the bits with
the reliability in the interval U0 < |r̄| ≤ U1 will be retransmitted
D − 1 times and so on. The number of the received copies
for each reliability range after D retransmissions is shown in
Fig. 2. Consequently, the overall BER can be expressed using
the functions χD (r̄,UD−1 ) and λD (r̄,UD ,UD−1 ) as,
R −U

BERD = −∞ D−1 fr̄ (r̄|S1 , D = 0) dr̄
R0
R0
+ ∑D−1
i=1 −∞ λi (r̄,UD−i ,UD−i−1 ) dr̄ + −∞ χD (r̄,U0 ) dr̄

where the middle term is zero for D = 1 retransmission. This
BER can be accurately approximated as,

p

√ 
UD−1
+
1
+
Q
2γ
(D
+
1)
BERD ≈ Q 2γb 2γ
b
nb −

√ 
Ak
2
q
−
e−αk,D (U0 )γb Q β+
∑k=1
The probability that the received reliability is in the interval
k,D (U0 ) γb
2Bk
1+ D

+
U0 ≤ |r̄| ≤ U1 is evaluated as,
√ o
γb
+ e−αk,D (U0 )γb Q β−
(U
)

0
k,D
n

P1 = Pr |r̄| ≤ U1 S1 , d = 0 Pr (d = 0|S1 ) +
−
√ 
−α
(U

D−1 2
R U1
k,i D−i−1 )γb Q β+ (U
q Ak
+
e
)
γb
∑
∑
D−i−1
k=1
i=1
k,i
Pr |r̄| ≤ U1 S1 , d = 1 Pr (d = 1|S1 ) = −U1 fr̄ (r̄|S1 , D = 0) dr̄
2B
1+ i k
R U1
R U0


√
− U0 fr̄ (r̄|S1 , D = 0) dr̄ + −U1 χ1 (r̄,U0 ) dr̄.
−α+ (U
)γ
+ e k,i D−i−1 b Q β−
k,i (UD−i−1 ) γb


This probability can be efficiently approximation as,
√
−α− (U )γ
− e k,i D−i b Q β+
(UD−i ) γb

√

√
k,i
U0
U0

+ 1) + Q 2γb ( 2γ
− 1)
P1 ≈ Q 2γb ( 2γ
√ o
−α+ (U )γ
b
b
− e k,i D−i b Q β−
.

√

√
k,i (UD−i ) γb
U1
U1
+
1)
−
Q
−
1)
−Q 2γb ( 2γ
2γ
(
b
2γ
b
b
The probability PD that the received reliability is in the interval
UD−1 ≤ |r̄| ≤ UD is evaluated as,
√ 
√
√ 
√
+Q 2 γb − U1 /n γb − Q 2 γb+ U1 / γb
Z UD
Z U0
+

√ 
Ak
e−αk,1 (U0 )γb erf θ+−
(U
)
γ
− ∑2k=1 2√1+2B
0
b
P
=
f
(r̄|S
,
D
=
0)
dr̄
−
fr̄ (r̄|S1 , D = 0) dr̄
k,1
D
r̄
1
k


−UD
−U0
  ++
√ 
√
−α−
(U
)γ
−+
0
b
+erf θk,1 (U0 ) γb + e k,1
erf θk,1 (U0 ) γb
Z UD
D−1 Z UD

 o
√
λ
(r̄,U
,U
)
dr̄
+
χD (r̄,U0 ) dr̄
+
−−
i
D−i
D−i−1
∑
+sign(µ(U0 )) erf θk,1 (U0 ) γb
−UD
−UD
i=1

6

with the third term being zero for D = 1 retransmission. It is
again possible to obtain the approximation of the probability
PD for D > 2. However, the resulting expression is much more
involved than in the case of P1 and P2 , so it is not presented
here.
D. BER for slowly varying fading channels
Since the wireless links are typically subject to time-varying
fading, we can average the BER expressions obtained in the
previous subsection over the time-varying received power, for
example, following the chi-square distribution. In this
 case,
γb
1
the received SNR has the PDF, fγb (γb ) = γ¯b exp − γ¯b , where
γ¯b = E[γb ] is the average SNR. Moreover, we assume that the
SNR variations are sufficiently slow (e.g., assuming that the
nodes are nomadic or even stationary), so the SNR can be
considered to be constant during the first packet transmission
as well as during the subsequent D retransmissions. Then, the
long-term average BER is evaluated using the expectation [3],
BERD =

Z ∞
0

BERD (γb ) fγb (γb ) dγb .

The computationally efficient formula for calculating BERD is
displayed below Fig. 2 on the next page. Similarly, the average
probability PD is evaluated as,
P̄D =

Z ∞
0

PD (γb ) fγb (γb ) dγb .

IV. B ITWISE R ETRANSMISSION P ROTOCOLS
We consider three specific bitwise retransmission strategies
and optimize their parameters to maximize the transmission
reliability rather than to maximize their throughput. We also
verify mathematical formulas derived in the previous section
by computer simulations assuming error-free feedback. This
assumption is revisited at the end of this section.
A. Fixed rate technique
In this design, we assume a constant retransmission window
size W determined as,

 
N 1
−1
W=
D Rf
for a priori given parameters N, D and the forward rate Rf .
Since the window size W is constrained as 1 ≤ W ≤ N, the
1
possible forward rates are restricted to the interval, 1+D
< Rf ≤
1
N
.
Thus,
for
W
=
N,
the
rate
R
=
,
and
the
proposed
f
D+N
1+D
retransmission scheme corresponds to a block repetition code
(BRC) with D repetitions of the original packet. We have the
following proposition.
Proposition 1: For a given SNR, the fixed rate retransmission technique achieves the minimum BER for some specific
value of the rate Rf . The optimum value of Rf minimizing the
BER increases with the SNR.
Prop. 1 can be proved by letting the derivative ( d/ dRf ) BERD
to be equal to zero. For large values of SNR and N, the
forward rate Rf approaches its maximum value of 1, so in such
case, the overhead due to retransmissions can be neglected.

Moreover, when N is large or W = N, the BER of the fixed
rate retransmission scheme approaches the BER of the BRC.
Fig. 3 and Fig. 4 show the BER of the forward link versus
the forward rate Rf for the different number of retransmissions
D at two SNR values γb = 0 dB and γb = 5 dB, respectively.
We observe that the minimum BER value is more pronounced
(i.e., the optimization is more important) for larger values of
SNR. The BER curves in Fig. 3 and Fig. 4 also compare
the simulations with the approximate expressions given in
the previous section; for D > 1, the difference between the
approximate expressions and the simulations is negligible.
The forward rates Rf yielding the minimum BER are shown
in Fig. 5 for the different number of retransmissions D. Finally,
Fig. 6 shows the BER versus the SNR γb for the different
number of retransmissions D assuming that the forward rate
Rf is optimized for each SNR value γb to minimize the
achieved BER. Note again that such optimization becomes
more effective if the SNR is increased.
B. Fixed window technique
As for the fixed rate technique, the retransmission window
size is fixed, and it is determined as,
W = ⌈N P⌋
where the retransmission decision thresholds Ud are set, so
that the probabilities P = P0 = P1 = . . . = PD−1 , which have
been obtained in the previous section, have the same value.
Then, given N, D and W , the forward rate is calculated as,
1
.
Rf =
1 + DW /N
We have the following proposition.
Proposition 2: For a given SNR, the fixed window technique
achieves the minimum BER for some value of the retransmission window size. The optimum window size value decreases
with the SNR.
Prop. 2 can be again proved by letting the derivative,
( d/ dW ) BERD to be equal to zero. When the ratio W /N
approaches unity, the BER of the fixed window technique
approaches the BER of the BRC. On the other hand, when
the ratio W /N approaches zero, the retransmission overhead
can be neglected.
Fig. 7 and Fig. 8 show the BER versus the normalized window size W /N for the different number of retransmissions D
and the SNR values γb = 0 dB and γb = 5 dB, respectively. We
again observe a negligible difference between the approximate
and the simulated BER curves, especially for larger values of
D. In addition, the minimum BER values are more pronounced
when the SNR is increased.
Fig. 9 shows the normalized window size W /N corresponding to the minimum BER for the different number of
retransmissions D. Fig. 10 shows the BER versus the SNR
γb for the different number of retransmissions D assuming
the optimum value of W /N for each γb minimizing the BER.
Note that such minimization of the BER is more effective
when the SNR is large. Finally, for the different number of
retransmission D, Fig. 11 shows the BER for a slowly varying
chi-square distributed, unit-mean received power, provided that
the parameters are optimized to minimize the BER.

7

Figure 2. The quantization levels of the bit reliability with D retransmissions.

BERD ≈ 1 − 12
t



4
γ¯b (UD−1 /γb +2)2

+ ∑ q Ak2B
k=1 1+ Dk

(

×



−1/2

−1/2

1
− 12 1 + γ¯ (D+1)
b
r

1 + γ¯b α−
k,D (U0 ) +

+ 1 + γ¯b(α+
k,D (U0 ) +
(

+1

β+
(U0 ) β+
(U0 )
k,D
√
( k,D√2
2

β−
(U0 ) β−
(U0 )
k,D
√
( k,D√2
2

+

r

1
γ¯b

r


−
β−
k,i (UD−i−1 ) βk,i (UD−i−1 )
√
√
(U
)
+
+ 1 + γ¯b α+
(
+
D−i−1
k,i
2
2


−
β−
D−i ) βk,i (UD−i )
k,i (U
√
− 1 + γ¯b α+
( √2 +
k,i (UD−i ) +
2

C. Fixed threshold technique
Unlike the previous two techniques, the fixed threshold
technique allows for different retransmission window sizes
while assuming the single constant reliability threshold, U0 =
U1 = . . . = UD−1 = U, during each retransmission. Given U, we
obtain the probabilities Pd , d = 1, 2, . . . , D, defined previously,
and calculate the retransmission window sizes as,
Wd = ⌈NPd ⌋ .
The corresponding forward rate is given as,
Rf =

1
.
1 + ∑D
d=1 Wd /N

We have the following proposition.
Proposition 3: For a given SNR, the fixed threshold technique achieves the minimum BER value for some specific
threshold U. This optimum threshold value is increasing with
the SNR.
Prop. 3 can be again proved by letting the derivative,
( d/ dU) BERD to be equal to zero.

1
γ¯b

+ α+
k,D (U0 ) +


+
β+
k,i (UD−i−1 ) βk,i (UD−i−1 )
√
√
(U
)
+
1 + γ¯b α−
(
+
D−i−1
k,i
2
2


+
β+
D−i ) βk,i (UD−i )
k,i (U
√
√
(U
)
+
− 1 + γ¯b α−
(
+
D−i
k,i
2
2

+

2

1
γ¯b

r

+ α−
k,D (U0 ) +
β−
k,D (U0 )
2

2

!−1 )

)

+ α−
k,i (UD−i−1 ) +
1
γ¯b

β+
k,D (U0 )
2

!
 −1

D−1 t

+ ∑ ∑

β+
k,i (UD−i−1 )
2

2



β−
k,i (UD−i−1 )
+ α+
(U
)
+
D−i−1
k,i
2

r

β+
k,i (UD−i )
+ α−
(U
)
+
D−i
k,i
2

2

1
γ¯b

r

β−
k,i (UD−i )
+ α+
k,i (UD−i ) +
2

2

1
γ¯b




q Ak
2B
1+ k
!−1 i

i=1 k=1

!−1

!−1 )

2



×

!−1

.

Fig. 12 and√ Fig. 13 show the BER versus the normalized
threshold U/ Eb for the different number of retransmissions
D and the SNR values γb = 0 dB and γb = 5 dB, respectively.
Since the approximate BER expressions were already verified
for the other two techniques considered, the BER curves in
Fig. 12 and Fig. 13 only show these derived expressions.
We again observe that the minimum BER values are more
apparent when the SNR√is increased. Fig. 14 shows the
normalized thresholds U/ Eb having the minimum BER for
the different number of retransmissions D. Finally, Fig. 15
shows the BER versus the √SNR γb for different D assuming
the optimum thresholds U/ Eb for each SNR γb that achieves
the minimum BER. We again find that
√ minimization of the
BER by optimizing the threshold U/ Eb is more effective
when the SNR is increased.

D. Feedback signaling
There are two main issues when designing practical feedback signaling schemes. The first issue is how to constrain the

8

1

10

sim, D=1
math, D=1
sim, D=2
math, D=2
sim, D=3
math, D=3
sim, D=4
math, D=4

-1.2

D =1
D=2
D=3
D=4

0.95

0.9

Rf

BER

0.85

0.8

10

-1.3

0.75

0.7

PSfrag replacements

eplacements
0.55

0.6

0.65

0.7

0.75
Rf

0.8

0.85

0.9

0.95

Figure 3. The BER versus the forward rate R f for SNR = 0 dB and the
different number of retransmissions D.
10

0.65
0

1

3

4

5

γb [dB]

6

7

8

9

10

0

10

-2

binary, theory
BRC
sim, D=1
math, D=1
sim, D=2
math, D=2
sim, D=3
math, D=3
sim, D=4
math, D=4

-1

10

-2

10

BERD

BER

2

Figure 5. The rate R f yielding the minimum BER versus the SNR γb for the
different number of retransmissions D.

sim, D=1
math, D=1
sim, D=2
math, D=2
sim, D=3
math, D=3
sim, D=4
math, D=4
10

1

-3

-3

10

-4

10

PSfrag replacements

eplacements
10

-4

0.55

0.6

0.65

0.7

0.75
Rf

0.8

0.85

0.9

0.95

1

0

1

2

3

4

5

γb [dB]

6

7

8

9

10

Figure 4. The BER versus the forward rate R f for SNR = 5 dB and the
different number of retransmissions D.

Figure 6. The BERD versus the SNR γb for the different number of
retransmissions D.

number of feedback bits. The second issue is the transmission
errors of feedback bits.
Sending a small number of feedback bits in a dedicated
packet is very inefficient due to the associated protocol overheads. In practice, it is common to reserve a few bits within
the packet payload for the feedback signaling, so the packet
overhead is shared by the feedback as well as data. In such
case, it is beneficial to minimize the number of feedback bits in
order to increase the data payload. Here, we reduce the number
of feedback bits sent from the destination to the source over
the reverse link by considering a deterministic sequence of bit
permutations synchronously generated at the transmitter and at
the receiver to encode the feedback message. Such sequence
is conveniently generated as pseudo-random permutations of
N-tuples, (1, 2, . . . , N), using the two synchronized RNGs. In

addition, the transmitter and the receiver RNGs synchronously
advance by exactly 2C1 permutations every symbol period. For
every generated permutation, the receiver checks whether a
sufficient number of bits with small reliabilities fall into a
predefined window of W bits; for instance, we can assume
that the retransmission window is represented by the the first
W bit positions. When such permutation is found, the feedback
message to notify the source is a binary representation of the
permutation order modulo 2C1 . The source then selects the
corresponding W bits in the packet, and retransmits them to the
destination. In particular, for the window size W , the number
of permutations K searched until the desired one has been
found can be expressed as,
K = 2C1 I + (K mod 2C1 )

9

0.35

0.3

W/N,
W/N,
W/N,
W/N,

D
D
D
D

8

9

=1
=2
=3
=4

0.25
-1.2

BER

W /N

10

0.2

0.15
sim, D=1
math, D=1
sim, D=2
math, D=2
sim, D=3
math, D=3
D=4
PSfragsim,
replacements
math, D=4

-1.3

10

replacements
0

0.2

0.4

W /N

0.6

0.8

0.1

0.05

0
0

1

Figure 7. The BER versus the normalized window size W /N for SNR = 0
dB and the different number of retransmissions D.

1

2

3

4

5

γb [dB]

6

7

10

Figure 9. The normalized window size W /N yielding the minimum BER
versus the SNR γb for the different number of retransmissions D.

-2

0

10

10

binary, theory
BRC
sim, D=1
math, D=1
sim, D=2
math, D=2
sim, D=3
math, D=3
sim, D=4
math, D=4

-1

10

-2

BERD

BER

10
-3

10

sim, D=1
math, D=1
sim, D=2
math, D=2
sim, D=3
math, D=3
sim, D=4
PSfrag
replacements
math,
D=4

replacements
-4

10

0

0.1

0.2

0.3

0.4

0.5

W /N

0.6

0.7

0.8

0.9

Figure 8. The BER versus the normalized window size W /N for SNR = 5
dB and the different number of retransmissions D.

where I is an integer number of the idle symbol periods. The
key property is that,
 
N
C1
(K mod 2 ) ≪
W

N
whereas, on average, E[K] = W
. Hence, the feedback message is only represented by C1 bits. The value of C1 is a design
parameter, and it trade-offs the feedback message size, and the
required delay until the start of the next retransmission [22].
More importantly, given some target BER, the window size
W and the average number of searched permutations E[K] are
decreasing with the SNR. As shown in Fig. 16, E[K] is only
about 30 for all N ≤ 64 when the SNR is at least 10 dB,
and thus, the feedback of C1 = 5 bits can be used to find the
desired permutation during one symbol period.

-3

10

-4

10

0

2

4

γb [dB]

6

8

10

Figure 10. The BERD versus the SNR γb for the different number of
retransmissions D.

The average forward throughput with one retransmission
can be defined as,
N
ζ1 =
.
E[I + 1]
By simulations, we found that there exists an optimum value
C1∗ which minimizes the expected delay E[I + 1], i.e., which
maximizes the throughput ζ1 . This optimum value is given as,
C1∗ = ⌈−0.5 + log2 E[K]⌋
and it is plotted in Fig. 17 for different values of the packet
length N. The corresponding maximum throughput ζ∗1 is
shown in Fig. 18. For comparison, the throughput 1/2 of the
BRC corresponding to the conventional stop-and-wait ARQ
with one retransmission is also shown in Fig. 18. More importantly, we observe that the proposed scheme can achieve better

10

0

-2

10

10
binary, theory
D=1
D=2
D=3

-1

10

math, D=1
math, D=2
math, D=3
math, D=4
-3

10
-2

BER

BER

10

-3

10

-4

10
-4

10

PSfrag replacements

eplacements
-5

10

-5

0

1

2

3

4

5

γb [dB]

6

7

8

9

10

10

0

1

√
3
U/ Eb

2

4

-1.1

15

U/Eb ,
U/Eb ,
U/Eb ,
U/Eb ,

math, D=1
math, D=2
math, D=3
math, D=4

-1.2

10

6

√
Figure 13. The BER versus the normalized threshold U/ Eb for the SNR
γb = 5 dB and the different number of retransmissions D.

Figure 11. The average BER versus the SNR γb over the slowly varying
chi-square distributed transmission power.

10

5

D
D
D
D

=1
=2
=3
=4

10

-1.3

√
U/ Eb

BER

10

-1.4

10

5
-1.5

10

eplacements

-1.6

10

PSfrag replacements
0

0.5

1

√
1.5
U/ Eb

2

2.5

√
Figure 12. The BER versus the normalized threshold U/ Eb for the SNR
γb = 0 dB and the different number of retransmissions D.

throughput than the rate 1/D repetition code for the same
number of retransmissions D, especially at the medium to large
values of SNR. Furthermore, we can show that the throughput
of the fixed window technique in the limit of very large SNR
N
converges to, limγb →∞ ζ1 ≈ N+1
, since limγb →∞ W /N = 0.
Finally, we reconsider the assumption of the error-free feedback which is often adopted in many papers concerning the
ARQ retransmission schemes. Recall that it was shown in [14]
that errors of 1 and 2-bit feedback messages can be neglected
if their bit error probability is less than 10−3. This result can be
readily modified for the case of multi-bit feedback messages
which are utilized in our bitwise retransmission schemes.
In particular, assuming the feedback errors are independent,
and they are occurring with the probability pr , we have the
following proposition.

3

0
0

1

2

3

4

5

γb [dB]

6

7

8

9

10

√
Figure 14. The values of the normalized threshold U/ Eb corresponding
to the minimum BER versus the SNR γb for the different number of
retransmissions D.

Proposition 4: The errors in the feedback messages of C
bits can be tolerated, provided that their bit-error probability
is bounded as,
1/C

pr ≤ 1 − Pmin

where the required minimum probability of the error-free
feedback messages was established in [14] to be, Pmin =
1 − 10−3 = 99.9%.
The proof of Prop. 4 follows from the binomial distribution
of independent and equally probable errors. Hence, the longer
the feedback message, the smaller the feedback bit error
probability pr is required.

11

0

2

10

10
binary, theory
BRC
math, D=1
math, D=2
math, D=3
math, D=4

-1

10

N=8
N=16
N=32
N=64

-2

1

C1∗

BERD

10

10

-3

10

-4

10

replacements

PSfrag replacements
0

0

2

4

γb [dB]

6

8

10

10

Figure 15. The BERD versus the SNR γb for the different number of
retransmissions D.

0

1

2

3

4

5

γb [dB]

6

7

8

9

10

Figure 17. The optimum values C1∗ with D = 1 retransmission versus the
SNR γb and the different packet length N.

9

10

1

N=8
N=16
N=32
N=64

8

10

0.9

7

10

0.8

6

10

5

10

ζ∗1

E[K]

fixed win, N =64
fixed win, N =32
fixed win, N =16
BRC

0.7

4

10

0.6
3

10

0.5

2

10

eplacements

PSfrag replacements
1

10

0

1

2

3

4

5

γb [dB]

6

7

8

9

10

0.4
0

5

γb [dB]

10

15

Figure 16. The expected number of permutations E[K] versus the SNR γb
and the different packet length N.

Figure 18. The throughput ζ∗1 corresponding to the optimum values C1∗ versus
the SNR γb and the different packet length N.

V. DATA F USION A PPLICATION

node technologies: Zigbee 802.15.4, Wifi 802.11b and Bluetooth v. 4.2 802.15.1. The parameters of these three technologies are summarized in Table. I. Their BER expressions have
been obtained by fitting the sum of exponentials (the Prony
method, [25]) to the performance curves reported in [26]. It
is obvious that Zigbee is the most energy efficient technology
for the sensor nodes, and it can operate at small SNR values.
The specific design examples of the bitwise retransmission
schemes with a constant retransmission window size employing the binomial number feedback and the packet segmentation
are listed in Table. II. Therein, p f is the BER of the forward
link, pr is the BER of the reverse link, Nseg is the number
of segments of the disjoint partitioning of the N bit packet,
Wseg is the retransmission window size per segment, and Ctot
is the total length of the feedback message (in bits) required

We now illustrate the use of the proposed bitwise retransmission schemes in a practical scenario of data fusion from
a group of L sensor nodes into a single central access point
(AP). A time-division multiple access (TDMA) protocol with
(L + 1) time slots is used to share the communication channel.
The time-division duplex (TDD) protocol further divides the
available time slots into L uplink time slots to transmit data
from the L sensor nodes, and one time slot is allocated for the
feedback signaling from the AP. Each time slot can carry at
most N bits of information including the protocol overhead.
The AP is assumed not to be battery powered, so the transmit
power in the downlink can be much larger than in the battery
constrained uplink.
More specifically, we consider the following three sensor

12

Table I
T RANSMISSION PARAMETERS OF THE THREE SENSOR NODE TECHNOLOGIES
Zigbee
BER
10−2
10−3
10−4
10−5
10−6
Packet
[bytes]
N [bits]
Segments

Pb (γb ) = 1.5203 e−9.5611γb
γb [dB]
-2.79
-1.16
0.03
0.96
1.73
header
6
payload
127
(6 + 127) × 8 = 1064
14×76, 19×56, 28×38
38×28, 56×19, 76×14
133×8, 152×7, 266×4
532×2, 1064×1

Wifi
Pb (γb )

=

Bluetooth
0.2436 e−0.4997γb
+0.2436 e−0.4997γb
γb [dB]
8.91
10.93
12.30
13.34
14.18
header+CRC
2+2
payload
252
(4 + 252) × 8 = 2048

10.0 e−3.4535γb

Pb (γb )

+1.1066 e−2.0247γb
γb [dB]
3.88
5.43
6.63
7.59
8.37
preamble+header
15–24
payload
1500
(24 + 1500) × 8 = 12192

16×762, 32×381, 48×254
96×127, 127×96, 254×48
381×32, 508×24, 762×16
1016×12, 1524×8, 2032×6
3048×4, 4064×3, 6096×2
12192×1

for the whole packet. Hence, N/Nseg is the segment length,
Wseg Nseg = W is the total number of retransmitted bits, and
Ctot /Nseg is the length of the feedback message per segment.
Furthermore, P̃f is the probability that there are at most Wseg
errors in any segment (i.e., the closer the value of P̃f to 1.0, the
better), and P̃r is the probability that there is at least one error
among the Ctot feedback bits received at the source (i.e., the
probability that the feedback message is received incorrectly
at the source). As shown in the previous section, it is required
that P̃r < Pmin = 10−3 in order to neglect the effect of feedback
errors on the performance. Other system parameters are given
in Table. I including the packet size N and the required SNR
for given values of p f .
We found that, to obtain efficient designs of the proposed
bitwise retransmission schemes, the BER p f of the forward
link should be at most 10−3 , and the BER pr of the reverse
link should be at most 10−5. In terms of the minimum required SNR for bidirectional connections, the Zigbee requires
−1.16 dB and 0.96 dB, the Wifi requires 5.43 dB and 7.59
dB, and the Bluetooth requires 10.93 dB and 13.34 dB,
respectively. Such SNR levels can be satisfied for all three
wireless technologies considered, provided that the reverse link
has 3 dB larger transmit power than the forward link. Such
transmission power unbalances can be readily obtained in the
sensor networks with the centralized mains-powered AP.
Next, we consider scheduling of the packet contents for our
single-cell TDMA/TDD multiple access protocol. We assume
that the parameters W , D, N, L and Ctot are constant, even
though they can be optimized for the uplink and downlink
BERs p f and pr . Recall that all packets have the maximum
length of N bits. In the uplink, the nodes send their data
as well as schedule the retransmitted bits for the previously
transmitted data packets. In the downlink, the AP broadcasts
the retransmission requests to all sensor nodes at once. The
contents in the uplink packets are scheduled following the
following two rules.
1) Include the retransmitted sequences in the order corre-

=

16×128, 32×64, 64×32
128×16, 256×8, 512×4
1024×2, 2048×1

Table II
T HE BITWISE RETRANSMISSION DESIGNS WITH THE CONSTANT WINDOW
SIZE AND THE PACKET SEGMENTATION

pf

pr

Nseg

Wseg

Ctot

P̃f

P̃r

Zigbee

10−3
10−3
10−3
10−4
10−4
10−4
10−4
10−4
10−4
10−4
10−4

10−5
10−5
10−5
10−5
10−5
10−5
10−5
10−5
10−5
10−5
10−5

2
1
1
4
2
2
2
1
1
1
1

3
4
5
1
1
2
3
1
2
3
4

50
36
44
36
20
36
50
11
20
28
36

0.9978
0.9953
0.9992
0.9997
0.9986
1.0000
1.0000
0.9947
0.9998
1.0000
1.0000

Wifi

10−3
10−4
10−4
10−4
10−4
10−4
10−4
10−4
10−4
10−4

10−6
10−6
10−6
10−6
10−6
10−6
10−6
10−6
10−6
10−6

5.0 · 10−4
3.6 · 10−4
4.4 · 10−4
3.6 · 10−4
2.0 · 10−4
3.6 · 10−4
5.0 · 10−4
1.1 · 10−4
2.0 · 10−4
2.8 · 10−4
3.6 · 10−4

1
4
3
2
2
1
1
1
1
1

21
2
2
3
4
4
5
6
7
8

220
92
69
72
92
50
61
72
83
94

0.9928
0.9962
0.9917
0.9965
0.9996
0.9917
0.9984
0.9997
1.0000
1.0000

Bluetooth

10−2
10−3
10−3
10−3
10−3
10−4
10−4
10−4
10−4
10−4
10−4

10−6
10−6
10−6
10−6
10−6
10−5
10−5
10−5
10−5
10−5
10−5

2
2
1
1
1
4
2
2
1
1
1

18
4
6
7
8
1
1
2
2
3
4

256
72
57
65
73
36
20
38
21
31
40

0.9913
0.9960
0.9949
0.9987
0.9997
0.9987
0.9951
0.9998
0.9988
0.9999
1.0000

2.2 · 10−4
9.2 · 10−5
6.9 · 10−5
7.2 · 10−5
9.2 · 10−5
5.0 · 10−5
6.1 · 10−5
7.2 · 10−5
8.3 · 10−5
9.4 · 10−5
2.6 · 10−4
7.2 · 10−5
5.7 · 10−5
6.5 · 10−5
7.3 · 10−5
3.6 · 10−4
2.0 · 10−4
3.8 · 10−4
2.1 · 10−4
3.1 · 10−4
4.0 · 10−4

sponding to the previously transmitted packets. Only one
retransmitted sequence per each previously transmitted
packet can be scheduled.
2) Add data bits from the buffered information blocks to

13

Table III
T HE UPLINK PACKET CONTENTS FOR N = 1064, W = 4, D = 3, Lpac = 10
#
1
2
3
4
5
6
7
8
9
10
11
12
13
14

packet content
D1 (1064)
R1,1 (4), D2 (1060)
R1,2 (4), D2 (4), D3 (1056)
R1,3 (4), R2,1 (4), D3 (8), D4 (1048)
R2,2 (4), R3,1 (4), D4 (16), D5 (1040)
R2,3 (4), R3,2 (4), R4,1 (4), D5 (24), D6 (1028)
R3,3 (4), R4,2 (4), R5,1 (4), D6 (36), D7 (1016)
R4,3 (4), R5,2 (4), R6,1 (4), D7 (48), D8 (1004)
R5,3 (4), R6,2 (4), R7,1 (4), D8 (60), D9 (992)
R6,3 (4), R7,2 (4), R8,1 (4), D9 (72), D10 (980)
R7,3 (4), R8,2 (4), R9,1 (4), D10 (84)
R8,3 (4), R9,2 (4), R10,1 (4)
R9,3 (4), R10,2 (4)
R10,3 (4)

fill in the whole packet of N bits.
Hence, the transmitted packet can contain retransmitted bits
for multiple previously transmitted packets, and also data bits
from multiple information blocks. As an example, assuming
first-in first-out (FIFO) buffering of the information blocks
of Nbuf = N = 1064 bits (Zigbee protocol) with Nseg = 2
segments, Wseg = 2 bits, i.e., the retransmission window of
W = 2 × 2 = 4 bits, D = 3 retransmissions, and in total Lpac =
10 data packets to be transmitted, the packets content schedule
is shown in Table. III. Therein, we use the notation Dl (n) to
denote a sequence of n bits belonging to the l-th information
block, and Rl,d (m) is the sequence of m retransmitted bits in
the d-th retransmission for the l-th information block where
the sequence indexes, 1 ≤ l ≤ Lpac , 1 ≤ n ≤ N, 1 ≤ d ≤ D and
1 ≤ m ≤ W . We have the following proposition.
Proposition 5: For N ≫ DW , Nbuf = N and Lpac ≥ 1, only
the very first information block is completely transmitted in
the first packet whereas all other information blocks are split
into exactly 2 subsequent packets. The D retransmissions
are scheduled into D subsequent packets immediately after
the transmission of the corresponding information block was
completed. Moreover, only the first Lpac transmitted packets
are fully occupied with N bits. The available transport capacity
in the last (D + 1) transmitted packets can be used to transmit
additional information blocks with the progressively shorter
block lengths and/or smaller number of retransmissions.
The main assumption required in Prop. 5 is that the total
number of retransmitted bits D · W is much smaller than the
block length N. If this condition is not satisfied, the packet
structure of the retransmission protocol is less predictable.
We conclude our discussion about the bitwise retransmission
scheme for the uplink data fusion from L sensor nodes by
considering the packets structure in the downlink. According
to Prop. 5, the AP (the data fusion center) sends the retransmission requests for the l-th information block during the time
slots {1, 2, . . . , D}, if l = 1, and {l + 1, l + 2, . . ., l + D}, if l ≥ 2.
However, since the information blocks with the index l ≥ 2 are
transmitted exactly in 2 subsequent packets with the indexes
l and l + 1, the number of retransmission requests contained
in the downlink packet first raises to the maximum value of
D requests per sensor node. The number of the requests then

remain constant until it is gradually decremented to 1 request
in the last (D − 1) transmissions. Consequently, we have the
last proposition.
Proposition 6: The maximum number of sensor nodes
Lmax which can be supported by the proposed retransmission
scheme is bounded as,


N − Novh
Lmax ≤
D ·Ctot

where Novh is the protocol overhead, and Ctot is the total
number of feedback bits per retransmission and sensor node.
For the example presented in Table. III, assuming Novh = 106
bits (10% of N), we have Ctot = 36 bits, so Lmax ≤ 8. A larger
number of sensor nodes can be supported by trading off the
number of feedback bits Ctot with the number of retransmissions. In addition, it is possible that different sensor nodes
set their retransmission parameters differently, for example, to
match the SNR they experience in the uplink and downlink.
In this case, the value of Lmax in Prop. 6 can be calculated
by assuming the maximum total number of feedback bits,
max(D ·Ctot ), allowed per any sensor node.
VI. C ONCLUSIONS

A novel bitwise retransmission scheme was presented to
selectively retransmit only the bits which were received with
a small reliability. The bitwise retransmission decisions as well
as combining can be done either immediately after demodulating the received symbols, or after the channel decoding. In
case of the turbo decoding, the bit reliabilities are available as
the soft-input (i.e., channel output) or the soft-output values
[23]. The locations of the bits to be retransmitted are reported
to the source as a binomial combination number. Since the
proposed scheme does not involve any complex operations, it
does not limit the processing throughput at the receiver nor at
the transmitter.
The analysis presented in the paper assumes uncoded binary
modulation for mathematical tractability and clarity of the
presentation. However, the proposed scheme can be readily generalized to non-binary modulations by appropriately
scaling the demodulated bits. We derived the overall BER
conditioned on the error-free feedback link. The accurate
closed-form BER expressions as well as their computationally
efficient approximations were presented assuming one and two
retransmissions. The approximations were verified by computer simulations. We showed that the bitwise retransmissions
can be optimized for the given SNR, especially in the forward
link, since the BER curves are convex in the transmission rates
as well as in the reliability threshold. In addition to minimizing
the BER as investigated in this paper, it is possible to maximize
the throughput instead.
We next compared the BER and throughput performances of
the three specific retransmission strategies which are referred
to as the fixed rate technique, the fixed window technique,
and the fixed threshold technique. It was shown that, for
the same number of retransmissions, and the same packet
length, the proposed schemes always outperform the repetition
diversity, and, in some cases including the transmissions over
time-varying channels, the performance improvement can be

14

significant. Furthermore, in order to reduce the number of
feedback bits, we proposed to use two synchronized RNGs at
the transmitter and at the receiver which can greatly compress
the transmitted binary feedback sequences at the expense of
larger delays. We also derived a condition when the impact of
feedback errors to the overall performance can be neglected.
We then considered practical design issues of multi-user
bitwise retransmission schemes for data fusion applications
where the sensor nodes forward data packets in the uplink into
a centralized AP. The retransmission requests are broadcasted
to the sensor nodes from the AP in the downlink. Assuming
TDMA/TDD and the Zigbee, Wifi and Bluetooth protocols, we
presented the design examples of retransmission parameters.
These examples suggest that the efficient designs of the bitwise
retransmission schemes can be obtained provided that the BER
of the forward link is below 10−3 and the BER of the reverse
link is below 10−5 . If the bidirectional link has the same or
similar BERs in both directions, the smaller BER in the reverse
link can be readily achieved by increasing the transmit power
in the downlink (i.e., at the AP). We also devised scheduling
of the information and retransmission bits utilizing the FIFO
buffering of the information blocks in order to fully fill up the
transmitted packets. Finally, we calculated the upper bound
on the number of sensor nodes which can be supported by the
proposed bitwise retransmission schemes.

A PPENDIX
We obtain several approximations to efficiently evaluate
the integrals in the BER expressions. The approximations are
based on the Prony approximation of the Q(x) function [25],
2

Q(x) =

2

∑ Ak e−Bk x
k=1

where A1 = 0.208, A2 = 
0.147,B1 = 0.971, and B2 = 0.525.
√
Since erf(x) = 1 − 2Q 2x , assuming positive constants
H > 0, and hi > 0, i = 1, 2, 3, 4, 5, the expressions for BERD
and PD can be approximated using the following expressions.
These approximations are used and verified numerically in the
figures presented in Section IV.

R0

−∞ h1 e

(r̄−h2 )2
h3

≈ ∑tk=1
≈

R0

−

−∞ h1 e

Q(h4 (h5 − r̄)) dr̄

R0

−∞ h1 e

q h1 A k
2 h1 +h4 2 Bk

e

3

−

(r̄−h2 )2
h3

≈ ∑tk=1

A e

dr̄


√
π erfc √



Q(h4 (h5 + r̄)) dr̄

R0

−∞ h1 e

−

(r̄−h2 )2
h3

h1 h3 A k
h3 (1+h3 h4 2 Bk )

≈ √
2

(r̄−h2 )2
−Bk (h4 (h5 −r̄))2
h3
k
2
B h (h −h )2
− k 4 22 5
h2 +h3 h4 2 h5 Bk
1+h3 h4 Bk
h3 (1+h3 h4 2 Bk )

−

2

Ak e−Bk (h4 (h5 +r̄)) dr̄


Bk h4 2 (h2 +h5 )2
−
√
2
2
π erfc √h2 −h3 h4 h52Bk
e 1+h3 h4 Bk
h3 (1+h3 h4 Bk )

RH

−H h1 e

RH

−

(r̄−h2 )2
h3

Q(h4 (h5 − r̄)) dr̄
(r̄−h )2

RH

2
− h2
3
Ak e−Bk (h4 (h5 −r̄)) dr̄
−H h1 e
2
2


B h (h −h )
√ √
− k 4 22 5 n
h2 +H+h3 h4 2 (h5 +H)Bk
h1 A k h3 π
1+h3 h4 Bk
√
e
≈ √
erf
2
h3 (1+h3 h4 2 Bk )
2 1+h
 3 h4 B k

h2 +h3 h4 2 h5 Bk
+sign H − 1+h h 2 B
3 4 k
o
q
h2 +h3 h4 2 h5 Bk
2
1
H
−
+
h
B
×erf
4
k
2
h3
1+h3 h4 Bk

≈ ∑tk=1

−H h1 e

−

(r̄−h2 )2
h3

≈ ∑tk=1

Q(h4 (h5 + r̄)) dr̄

RH

−H h1 e
√

−

(r̄−h2 )2
h3

2

Ak e−Bk (h4 (h5 +r̄)) dr̄

B h 2 (h +h )2
− k 4 22 5
1+h3 h4 Bk

≈ √ h1 h3 Ak π2 e
2 h3 (1+h3 h4 Bk )


o
n 
2
H−h2 +h3 h4 2 (H+h5 )Bk
5 )Bk
√2 +h3 h4 (H−h
√
+
erf
× erf H+h
2
2
h3 (1+h3 h4 Bk )

h3 (1+h3 h4 Bk )

R EFERENCES
[1] Goldsmith A, Varaiya P. Capacity of fading channels with channel side
information. IEEE Trans. Inform. Theory Nov 1997; 43(6):1986–1992.
[2] Cover TM, Thomas JA. Elements of Information Theory. 2nd edn., John
Wiley & Sons, 1991.
[3] Proakis JG. Digital Communications. 4th edn., McGraw-Hill, 2001.
[4] Lin S, Costello DJ. Error Control Coding: Fundamentals and Applications. Prentice-Hall, 1983.
[5] Beh KC, Doufexi A, Armour SMD. Performance evaluation of hybrid
ARQ schemes of 3GPP LTE OFDMA system. Proc. PIMRC, 2007; 1–5.
[6] Wang G, Wu J, Zheng YR. Optimum energy- and spectral-efficient
transmissions for delay-constrained hybrid ARQ systems. IEEE Trans.
Vehic. Tech. Jul 2016; 65(7):5212–5221.
[7] Ji T, Stark W. Rate-adaptive transmission over correlated fading channels. IEEE Trans. Commun. Oct 2005; 53(10):1663–1670.
[8] Pai HT, Han YS, Chu YJ. New HARQ scheme based on decoding of tailbiting convolutional codes in IEEE 802.16e. IEEE Trans. Vehic. Tech.
Mar 2011; 60(3):912–918.
[9] Wengerter C, von Elbwart AGE, Seidel E, Velev G, Schmitt M.
Advanced hybrid ARQ technique employing a signal constellation
rearrangement. Proc. VTC, vol. 4, 2006; 2002–2006.
[10] Jung J, Park H, Lim J. A novel hybrid ARQ scheme based on shift
column permutation bit interleaving for OFDM systems. Proc. VTC,
2006; 1–5.
[11] Chen H, Maunder RG, Hanzo L. A survey and tutorial on lowcomplexity turbo coding techniques and a holistic hybrid ARQ design
example Nov 2013; 15(4):1546–1566.
[12] Lucani DE, Médard M, Stojanovic M. On coding for delay-network
coding for time-division duplexing. IEEE Trans. Inform. Theory Apr
2012; 58(4):2330–2348.
[13] Moreira A, Lucani DE. Coded schemes for asymmetric wireless interfaces: Theory and practice. IEEE J. Select. Areas Commun. Feb 2015;
33(2):171–184.
[14] Makki B, i Amat AG, Eriksson T. On noisy ARQ in block-fading
channels. IEEE Trans. Vehic. Tech. Feb 2014; 63(2):731–746.
[15] Jabi M, Hamss AE, Szczecinski L, Piantanida P. Multipacket hybrid
ARQ: Closing gap to the ergodic capacity. IEEE Trans. Commun. Dec
2015; 63(12):5191–5205.
[16] Ahmed A, Muhammad Z, Mahmood H, Saqib NA. Partial automatic
repeat request transceiver for bandwidth and power efficient multipleinput-multiple-output orthogonal frequency division multiplexing systems 2015; 9(4):476–486.
[17] Malkamäki E, Leib H. Performance of truncated type-II hybrid ARQ
schemes with noisy feedback over block fading channels. IEEE Trans.
Commun. Sep 2000; 48(9):1477–1487.
[18] Modiano E. An adaptive algorithm for optimizing the packet size used
in wireless arq protocols. Wireless Nets. 1999; 5:279–286.
[19] Ahmad RA, Lacan J, Arnal F, Gineste M, Clarac L. Enhancing satellite
system throughput using adaptive HARQ for delay tolerant services in
mobile communications. WTS, 2015; 1–7.
[20] Shih CH, Kuo CI, Shieh CK, Chou YK. Small-block interleaving for
low-delay cross-packet forward error correction over burst-loss channels.
Int. J. Commun. Syst. 2014; 27:3980–3995.

15

[21] Fujii S, Kaneko T, Hayashida Y. Effectiveness of copy-transmission in
Go-Back-N ARQ system with selective repeat in intra-block and with
limited retransmissions. Proc. COMSNETS, 2010; 187–192.
[22] Hassanien MAM, Loskot P. Improving link reliability complexity tradeoff by exploiting reliable feedback signal. Proc. ISWCS, 2010; 775–779.
[23] Biglieri E. Coding For Wireless Channels. Springer, 2005.
[24] Knuth D. The Art of Computer Programm. Addison-Wesley, 1998.
[25] Loskot P, Beaulieu NC. Prony and polynomial approximations for
evaluation of the average probability of error over slow-fading channels.
IEEE Trans. Vehic. Tech. Mar 2009; 58(3):119–138.
[26] Petrova M, Riihijarvi J, Mahonen P, Labella S. Performance study
of IEEE 802.15.4 using measurements and simulations. Proc. WCNC,
vol. 1, 2006; 487–492.

