Opportunistic Relay Selection with Limited
Feedback
Caleb K. Lo, Robert W. Heath, Jr. and Sriram Vishwanath
Wireless Networking and Communications Group
Department of Electrical and Computer Engineering
The University of Texas at Austin, Austin, Texas 78712-0240
Email: [clo, rheath, sriram]@ece.utexas.edu
Abstract— It has been shown that a decentralized relay selec-
tion protocol based on opportunistic feedback from the relays
yields good throughput performance in dense wireless networks.
This selection strategy supports a hybrid-ARQ transmission ap-
proach where relays forward parity information to the destina-
tion in the event of a decoding error. Such an approach, however,
suffers a loss compared to centralized strategies that select relays
with the best channel gain to the destination. This paper closes
the performance gap by adding another level of channel feedback
to the decentralized relay selection problem. It is demonstrated
that only one additional bit of feedback is necessary for good
throughput performance. The performance impact of varying
key parameters such as the number of relays and the channel
feedback threshold is discussed. An accompanying bit error rate
analysis demonstrates the importance of relay selection.
I. INTRODUCTION
Message forwarding in multihop networks occurs over in-
herently lossy wireless links and coding strategies are needed
to meet the network QoS requirements. Hybrid-ARQ is such a
coding strategy that is especially effective in dense networks,
as intermediate nodes can act as relays, forwarding parity
information to the destination. If the destination detects uncor-
rectable packet errors and broadcasts a retransmission request
to the network, the relays are well-positioned to transmit parity
information more reliably than the source.
Relay selection techniques have been studied extensively in
recent years [1]–[8]. In our previous work on this topic, we
proposed a decentralized selection strategy for relay selection
in dense mesh networks [14], where decoding relays contend
to forward parity information to the destination using rate-
compatible punctured convolutional (RCPC) codes [10].
Our random access-based approach, which is based on op-
portunistic feedback [9], is distinct from centralized strategies
that select the relay with the best instantaneous channel gain
to the destination [7], [8]. Such centralized strategies, though,
yield better throughput than our decentralized approach.
Caleb K. Lo was supported by a Microelectronics and Computer Devel-
opment (MCD) Fellowship and a Thrust 2000 Endowed Graduate Fellowship
through The University of Texas at Austin. Robert Heath was supported
in part by the National Science Foundation under grant CNS-626797, the
Office of Naval Research under grant number N00014-05-1-0169, and the
DARPA IT-MANET program, Grant W911NF-07-1-0028. Sriram Vishwanath
was supported by the National Science Foundation under grants CCF-055274,
CCF-0448181, CNS-0615061 and CNS-0626903.
To close this performance gap, we propose a refinement of
our selection strategy via channel feedback. In our previously
proposed approach, if a decoding relay successfully sends a
“Hello” message to the source in a minislot, it is declared to
be the “winner” for that minislot. The source then randomly
chooses a relay among the set of all “winners.” In this paper,
we refine the relay selection among the set of all “winners” by
biasing the selection towards those relays with channel gains
to the destination that are above a particular threshold. For
example, if the set of “winners” consists of one relay with a
channel gain above the threshold and one relay with a channel
gain below the threshold, the relay with a channel gain above
the threshold is more likely to be chosen by the source than
the other relay.
We briefly discuss how our previously proposed relay selec-
tion strategy differs from the notion of multiuser diversity [11],
[12]. The basic premise behind multiuser diversity is that in a
system with many users with independently fading channels,
the probability that at least one user will have a “good” channel
gain to the transmitter is high. Then, the user with the best
channel gain to the transmitter can be serviced, which will
yield the maximum throughput. In our setup, the analogous
approach would be to always choose the decoding relay that
has the best channel gain to the destination to forward parity
information. Our decentralized approach, though, allows any
decoding relay to have a chance of being selected to forward
parity information as long as it sends at least one “Hello”
message to the source and wins at least one minislot.
II. SYSTEM MODEL
Consider the setup in Fig. 1. Each relay operates in a half-
duplex mode and is equipped with a single antenna. We use
boldface notation for vectors. SNR represents the signal-to-
noise ratio. |h|2 denotes the absolute square of h. Q(·) is the
standard Q-function, and Pr(X ≤ x) denotes the probability
that a realization of the random variable X is at most x.
Transmission occurs over a set of time slots {t1, ..., tm}
which are of equal duration. We use the ARQ/FEC strategy
in [10]. Initially, the source has a k-bit message w that is
encoded as an n-bit codeword x. The source chooses code-
rates from a RCPC code family, say {R1, R2, ..., Rm} where
R1 > R2 > · · · > Rm.
http://arxiv.org/abs/0704.0805v1
Tx Rx
Relay
Relay
Relay
Relay
Relay
hg,rht,g
Relay
Relay
Fig. 1. Relay network.
Before t1, the source and destination perform RTS/CTS-
based handshaking to achieve synchronization. During t1, the
source transmits a subset x1 of the bits in x such that x1 forms
a codeword from the rate-R1 code. The destination observes
yr,1 = ht,rx1 + nr,1 (1)
while relay i ∈ {1, 2, ...,Kr} observes
yi,1 = ht,ix1 + ni,1. (2)
Here, ht,i is a Rayleigh fading coefficient for the channel
between the source and node i, while ni,j is additive white
Gaussian noise with variance N0 at node i during time slot
tj . We assume that all fading coefficients are constant over
a time slot and vary from slot to slot; we also assume that
fading and additive noise are independent across all nodes. In
addition, we assume that all nodes have no prior knowledge
of fading coefficients and use training data to learn them.
The destination attempts to decode yr,1. If decoding is suc-
cessful, the destination broadcasts an ACK message to all of
the relays and the source. Otherwise, the destination broadcasts
a NACK message; the source now has to select one of the
relays to forward additional parity information that will assist
the destination in recovering w.
III. RELAY SELECTION VIA LIMITED FEEDBACK
We briefly review our proposed relay selection strategy in
[14]. The framing structure for our relay selection strategy is
shown in Fig. 2. We assume in Fig. 2 that the destination sends
a NACK after t1 and t2 to trigger the relay contention process.
Let Rsel denote the set of relays that can participate in the con-
tention process. If relay i ∈ Rsel, then relay i has successfully
recovered w and has a channel gain to the destination |hi,r|2
that is above a threshold ηopp. Relay i can determine |hi,r|2
by listening to the destination’s NACK, which is embedded in
a packet that contains training data.
All relays in Rsel use the same K minislots for feedback
to the source. During minislot b, each relay i ∈ Rsel sends a
“Hello” message to the source with probability pi. We refer to
Source
Framing
Relay
Framing
Framing
Rate-R1
Listen Listen
Transmit
Chosen
Relay ID
Listen Listen
Transmit
Chosen
Relay ID
Listen
Contention
Minislots
Contention
Minislots
Listen Listen Listen
Chosen Relay
Tx Rate-R2
Other Relays
Listen
Listen Listen
Listen
ACK or
Listen Listen Listen
ACK or
Listen Listen
Fig. 2. Framing structure for decentralized selection strategy.
this approach as a 1-bit strategy, where the “Hello” message is
an ID number that has been assigned to each relay. Successful
contention occurs during minislot b if exactly one relay i ∈
Rsel sends a “Hello” message. The source then declares that
relay as the “winner” for minislot b. After minislot K , the
source randomly selects one of the “winners” it; if there are
no “winners,” the source will transmit during t2.
In this work, we modify the 1-bit strategy by appending
a check bit to the “Hello” message; the check bit is set to
‘1’ only if |hi,r|2 > βopp for βopp > ηopp. Again, successful
contention occurs during minislot b if exactly one relay i ∈
Rsel sends a “Hello” message. We refer to this approach as a
2-bit strategy.
After minislot K , if either all of the “winners” sent a check
bit of ’0’, all of the winners sent a check bit of ’1’, or there
are no “winners,” the 2-bit strategy reduces to the 1-bit strat-
egy. Otherwise, the source will randomly select one of the
“winners” it that sent a check bit of ’1’ with probability
q > 0.5; one of the “winners” it that sent a check bit of
’0’ is randomly selected with probability 1 − q. Thus, the
2-bit strategy refines the 1-bit strategy by further biasing the
selection process in favor of the relays with the best channel
gains to the destination.
During t2, relay it (or the source) transmits a subset x2 of
the bits in x such that x1 ∪ x2 forms a codeword from the
rate-R2 code in the RCPC family. The destination combines
yr,1 with
yr,2 = hit,rx2 + nr,2 (3)
and attempts to decode yr,1∪yr,2 based on the rate-R2 code. If
unsuccessful decoding occurs again, the destination broadcasts
another NACK and the contention process repeats until either
the destination successfully recovers w or the rate-Rm code
has been used without successful decoding.
To compute the dimensionless effective rate Ravg of this
strategy, we use [10, equation (16)]
Ravg =
P + lAV
where lAV is the average number of additionally transmitted
bits per P information bits. Here, M is the memory of the
mother code for the RCPC family. We refer to Ravg as the
throughput of this strategy in the rest of this paper.
For simulation purposes, we employ the path loss model
described in [8]; thus, the received energy at node i is
Ei = |hb,i|2Ex (5)
= (λc/4πd0)
2(db,i/d0)
−µEx (6)
where Ex is the energy in the transmitted signal x. Here, λc
is the carrier wavelength, d0 is a reference distance, db,i is
the distance between transmitting node b and receiving node
i, and µ is a path loss exponent.
We adopt similar simulation parameters as those in [8].
Here, we employ a carrier frequency fc = 2.4GHz, d0 = 1m,
dt,r = 100m and µ = 3, where dt,r is the distance between
the source and the destination. We then uniformly distribute
Kr = 20 relays in the region between the source and the
destination such that each relay i is di,r < dt,r units from the
destination. We also use the WiMAX signaling bandwidth,
which is roughly 9 MHz [15]; given a noise floor of -204
dB/Hz this yields a noise value N0 = −134 dB. BPSK modu-
lation is used for all packet transmissions, and all of the relays
and the destination use ML decoding.
We use the codes of rates {4/5, 2/3, 4/7, 1/2, 1/3} from
the M = 6 RCPC family in [10]. We perform concatenated
coding, where the outer code is a (255, 239) Reed-Solomon
code with symbols from GF (28); this code can correct at
most 8 errors. The mother code for the RCPC family is a rate-
1/3 convolutional code with constraint length 7 and generator
polynomial (145 171 133) in octal notation.
In this section and in Section IV, we define the average
received SNR at the destination as follows. Assume that the
source uses a transmit energy of Et(γ) during time slot t1
that yields an average SNR γ at the destination; then, all
transmitting nodes will use a transmit energy of Et(γ) during
all subsequent transmission cycles.
Fig. 3 compares the throughput yielded by the 1-bit and
2-bit strategies. We also plot the throughput yielded by the
GPS-based HARBINGER method [8] and by a centralized
strategy that always selects the decoding relay with the best
instantaneous channel gain to the destination to forward parity
information. We have K = 10 minislots. For the 1-bit and 2-bit
strategies, we set ηopp = −91dB; we also set βopp = −86dB.
We set the feedback probability pi = 0.3 for both strategies.
In addition, we set the “winner” selection probability q = 0.75
for the 2-bit strategy. We see that the 2-bit strategy closes the
performance gap between the 1-bit strategy and the centralized
approach. Thus, using a limited amount of channel feedback
improves the performance of our relay selection strategy.
We also observe that the 1-bit and 2-bit strategies offer
comparable performance to the HARBINGER method. Note
that the 2-bit strategy outperforms the HARBINGER method
for some values of the received SNR. The intuition behind
this result is that the HARBINGER method optimizes the av-
erage received SNR at the destination by selecting the closest
2 3 4 5 6 7 8 9 10
average received SNR (dB)
RCPC family with M = 6, rates {4/5, 2/3, 4/7, 1/2, 1/3}, d
 = 100m
1−bit
2−bit
best gain
HARBINGER
Fig. 3. Comparison of 1-bit and 2-bit feedback strategies.
decoding relay to the destination. This method, though, does
not necessarily select the “best” decoding relay that has the
highest instantaneous channel gain to the destination. Also,
the inherent randomness of the 1-bit and 2-bit strategies allows
for the possibility of choosing the “best” decoding relay. Thus,
the HARBINGER method does not necessarily outperform our
selection strategies for all received SNR values.
IV. PERFORMANCE IMPACT OF VARYING SYSTEM
PARAMETERS
A joint optimization of all of the key system parameters
would enable computation of the maximum throughput yielded
by the 1-bit and 2-bit strategies. This optimization, though, is
fairly difficult to perform; instead, in this section we provide
some insight for system designers by varying some of the key
parameters in isolation and illustrating the resulting impact on
the throughput.
Fig. 4 illustrates the throughput of the 2-bit strategy for
various values of the check bit threshold βopp. Here we have
Kr = 10 relays and K = 3 minislots. We have an average
received SNR at the destination of 8dB. We see that if βopp
is close to ηopp, the performance of the 2-bit strategy suffers
since the 2-bit strategy essentially reduces to the 1-bit strategy.
Also, we see that if βopp is too large, the performance of
the 2-bit strategy suffers. This is because the probability of
selecting a decoding relay i such that |hi,r|2 > βopp decreases
as βopp increases, which causes the 2-bit strategy to reduce to
the 1-bit strategy again. Thus, it is apparent that there is an
optimal value of βopp for each value of the average received
SNR that maximizes the throughput of the 2-bit strategy.
Fig. 5 illustrates the throughput of the 1-bit strategy for a
varying number of relay nodes. We have K = 3 minislots
and an average received SNR of 6dB at the destination. We
see that there is an optimal number of relay nodes for which
the throughput is maximized. Note that if the number of relay
nodes is small, the probability that any of them decode the
source message and send a “Hello” message to the source is
also small. On the other hand, if the number of relay nodes
is large, the probability that at least two relays decode the
source message and attempt to send a “Hello” message to the
−98 −96 −94 −92 −90 −88 −86 −84
check bit threshold β
average received SNR of 8dB, K
 = 10, K = 3, p
 = 0.3 
Fig. 4. Throughput as a function of check bit threshold.
source in each minislot is also large; thus, a collision is likely
to occur in each minislot.
Fig. 6 also illustrates the effect on the performance of the
1-bit strategy of varying the number of relay nodes. Instead
of considering the throughput, though, we consider the bit
error rate (BER); we focus on transmission during time slot
t2 where the rate-2/3 code from the RCPC family is used. Here
we have K = 2 minislots and we set the feedback threshold
ηopp = −98dB. Again, we notice that the performance of the
1-bit strategy suffers when the number of relay nodes is either
small or large.
V. BER ANALYSIS
Assume that we employ Viterbi decoding at the relays and
at the destination. Recall that P is the puncturing period of the
RCPC family. Let Pd be the probability that an incorrect path
of weight d is selected by the Viterbi decoder, and let dfree
be the free distance of the member of the RCPC family that
is currently being used for decoding. Also, let cd be the total
number of non-zero information bits on all paths of weight d.
From [10, equation (9)] we see that the bit error rate Pb can
4 6 8 10 12 14 16 18 20
0.475
0.485
0.495
0.505
0.515
number of relays K
average received SNR of 6dB, K = 3 minislots, p
 = 0.3  
Fig. 5. Throughput as a function of number of relay nodes.
2 4 6 8 10 12 14 16 18 20
0.065
0.075
0.085
0.095
0.105
number of relays K
average received SNR of 4dB, K = 2 minislots, p
 = 0.3
Fig. 6. Bit error rate as a function of number of relay nodes.
be upper-bounded as
d=dfree
cdPd. (7)
Let γr denote the received SNR at the destination. Since we are
essentially dealing with a binary-input AWGN channel with
binary output quantization, we use [13, equation (12.39b)] to
see that Pb can be further upper-bounded as
d=dfree
p(1− p)
d=dfree
cd · (9)
Since g(γr) = Q(
2γr)(1−Q(
2γr)) is a monotonically
decreasing function for non-negative γr, we see that Pb mono-
tonically decreases for increasing values of the received SNR.
This demonstrates the utility of relay selection, as transmission
from relay nodes will yield a higher average received SNR at
the destination than transmission from the source.
To illustrate this point, consider the following simple ex-
ample. We have the same simulation parameters as in Section
III, except that now we have Kr = 1 relay, K = 1 minislot
and a feedback probability pi = 1. We place this relay at a
location that is 25 meters from the source and 75 meters from
the destination. During time slot t1, the source uses a transmit
energy that is 101dB above the noise floor N0, which yields an
average received SNR at the destination of γt,r = 0.952dB.
We consider the 1-bit strategy here and set ηopp = −91dB.
Consider time slot t2, where we assume that the destination
did not successfully recover w during t1. Now, if the relay is
selected to forward parity information during t2, the average
received energy at the destination is
3 · 108
2.4 · 109
10(−134+101)/10
≈ 1.17 · 10−13.
Thus, we have an average received SNR at the destination of
γ1,r = Er/N0 ≈ 4.7dB.
From [10] we can determine the bit weight enumerating
function (WEF) weights cd for the rate-2/3 code from the
RCPC family. In particular, we see from [10, Table II(c)] that
the only non-zero values of cd are
cd = {12, 280, 1140, 5104, 24640, 108512}
for d = {6, 7, 8, 9, 10, 11}. Now we substitute these values of
cd and d along with γr = γ1,r into (9). We find that the BER
Pb is upper-bounded as Pb < 5.42 · 10−4.
Since Pr(γr < γ1,r) = 0.368, we want to evaluate the
performance of our selection strategy for a wider range of
γr. In particular, we find that Pr(γr < 2) = 0.492; if we
substitute γr = 2 into (9) we have Pb < 0.0688.
On the other hand, assume that the source forwards parity
information during t2. If we substitute γr = γt,r into (9), we
find that the BER Pb is upper-bounded as Pb < 5.55.
Again, since Pr(γr < γt,r) = 0.368, we evaluate the
performance of this approach for a wider range of γr. We
find that Pr(γr < 0.85) = 0.495; if we substitute γr = 0.85
into (9) we have Pb < 64.7. Thus, it is apparent that relay
selection leads to significant gains in BER performance.
Since relaying leads to significantly improved BER perfor-
mance, we want to determine the probability of relay selection
for this example. Here, the relay is selected if it recovers w
in t1 and has a channel gain to the destination |h1,r|2 > ηopp.
Recall our assumption that all channels in our setup undergo
Rayleigh fading. First, the probability that the relay has a
sufficiently high channel gain to the destination is
e−χ/γ1,rdχ (10)
Thus, we only have to consider the probability P1 that the
relay recovers w in time slot t1. From [10, equation (20)], the
probability Perr that the relay cannot recover w in t1 is
Perr < 1−
d=dfree
where the non-zero values of cd are for the rate-4/5 code from
the RCPC family. By using (9), P1 is lower-bounded as
P1 = 1− Perr
= (1 − Pb)n+M (12)
d=dfree
cd · (13)
)d)n+M
In particular, we see from [10, Table II(c)] that the only non-
zero values of cd are
cd = {24, 376, 3464, 30512, 242734, 1890790}
for d = {4, 5, 6, 7, 8, 9}. We have P = 8, n = 2040, M = 6
and the average received SNR at the relay during time slot t1
is γt,1 ≈ 19dB. If we substitute these values of P , n, M and
γr = γt,1 into (13) we see that P1 ≈ 1.
Again, since Pr(γr < γt,1) = 0.368, we evaluate the
performance of our selection strategy for a wider range of
γr. In particular, we find that Pr(γr < 5) = 0.0608; if we
substitute γr = 5 into (13) we see that P1 > 0.851. Thus, we
have a good chance of reaping the benefits of relay selection.
VI. CONCLUSION
In this paper we presented a strategy for improving the
throughput of our previously proposed decentralized relay se-
lection protocol. We modified our protocol by using a limited
amount of channel feedback to close the performance gap be-
tween our protocol and centralized strategies that select the re-
lay with the best channel gain to the destination. To understand
the performance impact of different system parameters, we
presented simulation results and discussed their applicability
to system design. We performed a simple BER analysis to
further illustrate the gains achieved by relaying.
REFERENCES
[1] M. Chen, S. Serbetli and A. Yener. Distributed power allocation for
parallel relay networks. In Proc. of the IEEE Glob. Telecomm. Conf., 3,
St. Louis, MO, November 2005.
[2] Z. Lin and E. Erkip. Relay search algorithms for coded cooperative
systems. In Proc. of the IEEE Glob. Telecomm. Conf., 3, St. Louis,
MO, November 2005.
[3] A.K. Sadek, Z. Han and K.J.R. Liu. A distributed relay-assignment
algorithm for cooperative communications in wireless networks. In Proc.
of the IEEE Intl. Conf. on Commun., 4:1592-1597, Istanbul, Turkey, June
2006.
[4] Y. Zhao, R. Adve and T.J. Lim. Improving amplify-and-forward relay
networks: optimal power allocation versus selection. In Proc. of the Intl.
Symp. on Inform. Theory, 1:1234-1238, Seattle, WA, July 2006.
[5] V. Sreng, H. Yanikomeroglu and D.D. Falconer. Relayer selection
strategies in cellular networks with peer-to-peer relaying. In Proc. of the
IEEE Vehic. Techno. Conf., 3:1949-1953, Orlando, FL, October 2003.
[6] A. Bletsas, A. Khisti, D.P. Reed and A. Lippman. A simple cooperative
diversity method based on network path selection. IEEE J. Select. Areas
Commun., 24(3):659–672, March 2006.
[7] J. Luo, R.S. Blum, L.J. Greenstein, L.J. Cimini and A.M. Haimovich.
New approaches for cooperative use of multiple antennas in ad hoc
wireless networks. In Proc. of the IEEE Vehic. Techno. Conf., 4:2769-
2773, Los Angeles, CA, September 2004.
[8] B. Zhao and M.C. Valenti. Practical relay networks: a generalization
of hybrid-ARQ. IEEE J. Select. Areas Commun., 23(1):7–18, January
2005.
[9] T. Tang and R.W. Heath, Jr. Opportunistic feedback for downlink
multiuser diversity. IEEE Comm. Lett., 9(10):948–950, October 2005.
[10] J. Hagenauer. Rate-compatible punctured convolutional codes (RCPC
codes) and their applications. IEEE Trans. Comm., 36(4):389–400, April
1988.
[11] X. Qin and R.A. Berry. Distributed approaches for exploiting multiuser
diversity in wireless networks. IEEE Trans. Inform. Theory, 52(2):392–
413, February 2006.
[12] P. Viswanath, D.N.C. Tse and R. Laroia. Opportunistic beamforming
using dumb antennas. IEEE Trans. Inform. Theory, 48(6):1277–1294,
June 2002.
[13] S. Lin and D.J. Costello, Jr. Error Control Coding. Pearson Prentice
Hall, Upper Saddle River, NJ, 2004.
[14] C.K. Lo, R.W. Heath, Jr. and S. Vishwanath. Hybrid-ARQ in multihop
networks with opportunistic relay selection. To appear in Proc. of the
IEEE Intl. Conf. on Acoustics, Speech and Sig. Proc., Honolulu, HI,
April 2007.
[15] Wireless MAN Working Group. http://www.wirelessman.org/.
http://www.wirelessman.org/
	Introduction
	System Model
	Relay Selection Via Limited Feedback
	Performance Impact of Varying System Parameters
	BER Analysis
	Conclusion
	References

  It has been shown that a decentralized relay selection protocol based on
opportunistic feedback from the relays yields good throughput performance in
dense wireless networks. This selection strategy supports a hybrid-ARQ
transmission approach where relays forward parity information to the
destination in the event of a decoding error. Such an approach, however,
suffers a loss compared to centralized strategies that select relays with the
best channel gain to the destination. This paper closes the performance gap by
adding another level of channel feedback to the decentralized relay selection
problem. It is demonstrated that only one additional bit of feedback is
necessary for good throughput performance. The performance impact of varying
key parameters such as the number of relays and the channel feedback threshold
is discussed. An accompanying bit error rate analysis demonstrates the
importance of relay selection.

Introduction
	System Model
	Relay Selection Via Limited Feedback
	Performance Impact of Varying System Parameters
	BER Analysis
	Conclusion
	References
