This paper presents a design for a throughputefficient online relay selection scheme for dualhop multirelay cooperative networks. Problems arise with these networks due to unpredictability of the relaying link quality and high timeconsumption to probe the dualhop link. In this paper, we firstly propose a novel probing and relaying protocol, which greatly reduces the overhead of the dualhop link estimation by leveraging the wireless broadcasting nature of the network. We then formulate an opportunistic relay selection process for the online decisionmaking, which uses a tradeoff between obtaining more link information to establish better cooperative relaying and minimizing the time cost for dualhop link estimation to achieve higher throughput. Dynamic programming is used to construct the throughputoptimal control policy for a typically heterogeneous Rayleigh fading environment, and determines which relay to probe and when to transmit the data. Additionally, we extend the main results to mixed Rayleigh/Rician link scenarios, i.e., where one side of the relaying link experiences Rayleigh fading while the other has Rician distribution. Numerical results validate the effectiveness and superiority of our proposed relaying scheme, e.g., it achieves at least 107% throughput gain compared with the state of the art solution.
1. Introduction
C
ooperation between nodes is emerging as one of the most interesting paradigms in wireless systems
[1]
. Improvements in energy efficiency, transmission reliability and network coverage have led to coopartive nodes being highly recommended for deployment in emerging wireless networks such as machinetomachine
[2]
and vehicular adhoc networks (VANETS)
[3]
.
Generally, there are multiple cooperative nodes acting as relaying nodes. The proper choice of relay node can substantially improve the efficiency of the wireless network and ensure that the target performance metrics at the destination are satisfied
[4
,
5]
. Many studies have undertaken research on performance bound analysis of opportunistic relaying (OR). The outage probability of OR is analyzed in
[6]
. The impacts of outdated channel estimates for the performances of opportunistic relay selection are discussed in
[7]
. The differences between relay selection and relay ordering for decodeand forward (DF) two hop relay networks are discussed in
[8]
. In
[9]
, the author investigate the performance of the bestworse relay selection strategy in a two way cooperative nonregenerative relay network, where the relay is selected to maximize the worst Signal to Noise Ratio (SNR) of two links. However, these studies show the achievable throughput gain of OR without considering the overhead of CSI information acquisition.
Probebased relay selection schemes focus on the practical implementation issue, and achieve system throughput gain while taking the link observation cost into consideration. In
[10]
, the author considers the opportunistic cooperative networking problem, focusing on whether or not relaying should be performed when candidate relays are available. A direct link between the source and the destination is required in their model, to help coordination during the relay probing. Recently, cooperative relay selection in cognitive radio network has been considered in
[11]
, where secondary users are treated as positive potential cooperators for the primary users. The relays are probed sequentially, and an optimal stopping formulation is applied to derive the optimal selection policy.
In this paper, we consider throughputefficient relay probing and selection in dualhop cooperative networks, focusing on the challenging scenario where the destination is outside of the source's transmission range. The main differences between our study and previous work can be highlighted within the context of our main contributions, and are summarized as follows.
1) We propose a new probing and relaying protocol, which reduces the time cost for probing relay dualhop links by flexibly leveraging the wireless broadcasting nature of the network. In contrast in
[10]
, a timeefficient link quality is acquired on the assumption that a direct link between the source and destination exists; while in
[11]
, intuitive sequentially probing is applied, which results in a high observation cost.
2) We derive a throughputoptimal online relay selection policy for a typical Rayleigh propagation environment, and the results are later extended to the more complicated case of mixed Rayleigh/Rician fading. In contrast to
[10]
and
[11]
, we consider a more practical scenario, where the channel conditions of the sourcerelay (SR) and relaydestination (RD) link, as well as links across different relays, are diverse and do not necessarily have identical distributions.
3) An efficient algorithm is proposed for deriving the relay probing sequence. We show numerically that it achieves an optimal sequence of 100% with 10000 randomly and independently generated settings, and thus is highly likely to be the optimal choice. The probing sequence is calculated in
O
(1) with this algorithm, rather than the previous brute force search which requires exponential computational complexity. Previous studies have considered the links to be identical
[10]
or assumed that a predetermined sequence is available
[11]
, in order to avoid the problem of probing sequence acquisition.
The remainder of this paper is organized as follows. The system model and problem statement are presented in Section II. The proposed online control policy is described in Section III. Section IV extends the main results to a mixed Rayleigh/Rician fading environment. The results of the performance evaluation are reported in Section V. Finally, Section VI concludes our work.
2. System Model and Problem Statement
 2.1 Network Scenario
We consider a typical dualhop cooperative network as depicted in
Fig.1
. The system contains a source, denoted by
S
, which attempts to transmit data to a destination, denoted by
D
. The destination
D
is not within a single hop from
S
, and thus needs the assistance of the relaying nodes located between them. There exists
N
relay nodes, denoted by
R_{i}
,
i
= 1, 2,...,
N
, and the source can choose any of the relays for data relaying.
System model
The links between
S

R
and
R

D
as well as the links across relays are subject to independent and nonidentical fading. Let
denote the average SNR of the
S

R
and
R

D
links, respectively. When the instantaneous dualhop link qualities for relay
R_{n}
(i.e.,
are available, the instantaneous achievable rate of the halfduplex DF relaying transmission is given by
[12
,
13]
:
For a typical multipath propagation environment, the received SNR
γ
is distributed exponentially with p.d.f:
where
is the average received SNR, and the CDF is given by:
 2.2 Probing and Relaying Protocol
In dualhop cooperative relaying networks, it is inefficient to probe each relay individually, particularly when there are a large number of relays. In this paper we exploit the broadcasting nature of wireless networks and propose a new probing and relaying protocol, which reduces the probing cost of the dualhop relaying system as much as possible. In this way, these channel conditions of the first hop links can be obtained when relays receive the broadcast packet from D. Therefore only the channel conditions of the second hop need to be probed. As illustrated in
Fig.2
, the duration of one slot is ∆ . When
S
wants to send data, it firstly broadcasts an RTS packet within the control channel, which contains a probing sequence. After receiving the RTS packet, the relay obtains the channel conditions of the
S

R
links with channel estimation. Each relay then updates the packet with its own channel condition and forwards it to
D
individually based on the probing sequence. After receiving the RTS packets,
D
obtains the CSI of the
S

R
links within the RTS packet and the channel conditions of the
R

D
links from channel estimation. Based on this information,
D
makes a decision as to whether to select the current relay or to continue the receiving and probing process. The transmit interval of each packet is
τ
, which contains a packet transmission time
t_{RD}
and a SIFT(Short Inter Frame Time)
τ
^{'}
. The SIFT
τ
^{'}
>
t_{RD}
can guarantee the reception of a CTS packet if current node is selected by D.
Time structure of probing and relaying protocol
We assume that
D
decides to select relay
R_{n}
after
n
rounds of probing, and then sends back a CTS packet. After the CTS packet reaches the relays, and all remaining relays stop sending RTS packets. An additional time of
t_{RS}
=
t_{SR}
is needed for the CTS packet to arrive at
S
, so during the remainder of the slot ∆ − 2
t_{SR}
−
nτ
,
S
delivers its packets through the selected relay to
D
.
 2.3 Problem formulation
The set of all possible probing orders is given by Ψ = [Φ
_{1}
,Φ
_{2}
,...,Φ
_{m}
,...,Φ
_{M}
],｜Ψ｜=
M
=
N
! , where the probing sequence is
. The probing sequence is a permutation of each of the
K
relays, where
and ⎿·⏌ is a rounddown function. The sequence is the maximum number of probing steps in each slot, and
denotes the corresponding
k^{th}
relay in Φ
_{m}
. During the
t^{th}
slot, under the policy
π_{m}
, if
D
decides to select the current relay node
,
k
= 1, 2,...,
K
, then, the instantaneous reward of achievable rate is given by
, where
c
= 2×(
t_{SR}
) is a constant.
The average system throughput is then given by:
where
, and
C_{k}
= 1 
kβ

c
^{*}
, which is the normalized available sending time. The problem is then how to find the optimal
π_{m}
which maximizes the system throughput, i.e.：
3. Online Control policy
In this section, we focus on deriving the optimal control policy for maximizing the system throughput. We firstly establish the optimal opportunistic relaying strategy for a given probing sequence, which employs dynamic programming. An efficient approach for acquiring the probing sequence is later proposed.
 3.1 Optimal Control Policy
We derive the optimal control policy as the solution to the stopping problem. After probing the
k^{th}
relay, the expected achievable rate reward can be defined as the maximum value of the instantaneous achievable rate when D choose current relay, or the expected reward if
D
continues probing the next relay node. For example, the expected achievable rate reward obtained after probing the
k^{th}
relay in a dualhop DF relaying system could be described using Equ. (1) as given in Equ. (6)：
In Equ. (6),
is the expected reward if
D
continues probing the next relay node. It is reasonable that
D
will send back a CTS packet in the last probing step (
D
has to choose a relay, otherwise the transmission reward will be zero). Therefore, after the
K^{th}
probing,
is given by :
where
is the endtoend SNR of the dualhop DF relaying system, whose CDF is given by：
In a typical multipath propagation environment with flat Rayleigh fading channels, the CDF can be further solved by substituting Equ. (3) into Equ. (8) as follows:
where
are the average received SNR of the
S

R
and
R

D
channels, respectively, and
.
The expected reward of
, (
k
= 1, 2,...,
K
 1) for a given probing sequence can then be retrospectively deduced using Equ.(6). Specifically, the optimal control policy can be derived as follows：
For
k
=
K
where
is the exponential integral function given in [
[14]
, Eq. (8.211.1)].
For 0 <
k
<
K
The online control rule can then be given as follows.
D
probes a potential relay node
based on the probing order Φ
_{m}
, and obtains an instantaneous reward after the
k^{th}
probe.
D
then compares the value of
with the value of
and decides to stop and select the current relay if
, otherwise it continues to probe the next relay node.
Therefore, the corresponding stop rule
π_{m}
can be given by a threshold sequence
, where the thresholds are given by：
 3.2 Optimal Probing Order
In a dualhop relaying system with
N
relay nodes, the set of all possible probing orders is given by Ψ=
M
=
N
!. Each element in Ψ , that is
, is a permutation of each of the
K
relays. The brute force search of optimal probing sequence results in exponential computation effort with respect to the number of relays.
Therefore, finding the optimal probing sequence in a computation efficient way is critical for implementing probingbased online relaying schemes.
Guess:
Rank the relays in descending order
. This is the optimal probing order for a halfduplex DF relaying system.
In this paper, we have undertaken an extensive simulation study to verify the optimality of the descending probing order. Specifically, we performed 10000 independent runs and calculated the suitability of the order derived by our guess compared with the optimal probing sequence derived by a brute force search. In each run, the SNR mean, probing cost and the number of relay were randomly generated from a range of values. Specifically, the average SNR of twohop links were chosen between 1 to 10 dB, randomly. The probing cost was randomly selected from 0.001 to 0.009, and the number of relay changes from 4 to 8. The statistics relating to the relay number and probe cost is given in
Table 1
,
Table 2
. The distribution of different average SNR, probing cost and relay numbers for each chosen simulation point is given in
Fig. 3
. The final results reveal 100% suitability.
Distribution of relay numbers
Distribution of relay numbers
Distribution of probing costs
Distribution of probing costs
Distribution of simulation point
Our opportunistic relay selection scheme is summarized in
Alg. 1
.
4. Extensions to Asymmetric Fading Condition
In some cases, links in relay networks may experience separate fading conditions. For example, the WINNER II project
[15]
confirms the existence of different (mixed Rayleigh/Rician) fading conditions. In
[16]
and
[17]
, the relaymobile link is considered to have Rayleigh fading, while the base stationrelay link is observed to be a Rician link because of a strong lineofsight (LoS) component.
Motivated by these facts, we considered the scenario where the
S

R
links experience independent Rayleigh fading and the
R

D
links experience independent Rician fading. The p.d.f. of the received instantaneous SNR distribution over a typical Rician fading channel is given by
[18]
:
where
is the zeroth order modified Bessel function of the first kind. Here we consider
γ
as the sum of squares of two statistically independent Gaussian random variables which have the same variance
and mean values
, respectively. Here we define
as the sum of the squares of the mean values, and the Rice factor
K
=
S
^{2}
/ 2
σ
^{2}
, accordingly.
With the help of
[14]
, Eq. (3.351.1)] and the definition of I
_{0}
(
x
) , the CDF is given by:
For the asymmetric fading channel scenario, we define
for simplicity, to obtain
and
as given in Equ.(15) and Equ.(16):
For
k
=
K
For 0 <
k
<
K
where
is the SNR threshold. The calculation of Equ.(15) and Equ.(16) are presented in Appendix I and Appendix II, respectively.
5. Performance Evaluation
In this section, we evaluate the performance of our proposed timeefficient probing and opportunistic relaying scheme (denoted as “tepor” during the description of simulation results) by numerical experiments. The random selection scheme, where the user randomly selects a relay as the cooperator for each slot, is used as the benchmark. Two other algorithms are also used for performance comparison. The first algorithm is the stateofart algorithm proposed in
[11]
, known as optimal stopping. It probes the relays one by one, and applies an optimal stopping formula to decide when to stop probing. Since the dualhop links of each relay are observed in each probing step, the probing cost is
t_{SR}
+
t_{RD}
= 2
τ
. Note that the probing sequence is undiscussed in
[11]
. We assume that a random relay sequence is used in optimal stopping. The second algorithm for comparison is called revised optimal stopping, where the probing sequence is determined with our proposed relay ranking approach.
The numerical results reported in this section are averaged over 100 simulation groups, with each lasting for 100 independent runs. At the beginning of each group, the SNR mean of each link (including both
S
−
R_{i}
and
R_{i}
−
D
for 1 ≤
i
≤
N
) is generated independently and uniformly according to a given range. Later, during the simulation group, the actual SNRs for different links are generated independently according to Rayleigh and Rician distribution with corresponding SNR mean in each run.
Fig. 4
and
Fig. 5
show the the relationship between average throughput and the normalized probing duration when twohop links have same or different fading conditions. The number of relay nodes is set at
N
= 10 , the Rician factor is set at 5, and the average SNR is chosen randomly between
[5

10]
, and
β
is within the range [0.01,0.09]. The graph shows that the average throughput decreases as the probing cost increases. The optimal stopping scheme and revised optimal stopping scheme show even worse performance than the random selection method when the probing cost is large (
β
= 0.08 or
β
= 0.09 ). This is because the time used for data transmission decreases. Additionally, the graph shows that our proposed scheme achieves higher throughput gains than the other three schemes (up to 133.6 % compared with the random selection scheme, and up to 140% and 134.6% over the optimal stopping and revised optimal stopping scheme, when
β
= 0.09 and the links of twohop are with Rayleigh fading). The simulation results show that we should choose a shorter probing cost as long as it satisfies the channel estimation requirement.
Average throughput versus normalized probing duration( Rayleigh/Rayleigh )
Average throughput versus normalized probing duration( Rayleigh//Rician)
Fig. 6
and
Fig. 7
consider the relationship between the average throughput and the number of relays when twohop links have same or different fading distribution s. We set
β
= 0.05 , the average SNR is obtained from
[5
,
10]
, and the number of relays is changed from 2 10 . We observe that the average throughput increases linearly as the number of relays increases for our tepor scheme, optimal stopping scheme and revised optimal stopping scheme. This is because the more candidate relays we have, the higher possibility that we can select a relay with better channel conditions, and further increase the average throughput. The result shows little change when the random selection scheme is used, because of the arbitrariness of selection. The figure also shows that the increase is particularly obvious when the number of relays is small, and finally becomes flat as the number of relays increases. This is mainly due to the increase of time cost to probe each relay node. It also shows that our proposed scheme achieves up to 127.2% throughput gains over the random selection scheme, and up to 111.9% and 109.9% over the optimal stopping and revised optimal stopping scheme, even when
N
= 3 , and the links of twohop are with Rayleigh fading.
Average throughput versus the number of relays(Rayleigh/Rayleigh)
Average throughput versus the number of relays( Rayleigh//Rician)
6. Conclusion
In this paper, we proposed a probingbased opportunistic relaying protocol for dualhop cooperative networks. Online control framework is developed to achieve throughputoptimal real time relay selection. We show that the optimal relaying rule has a threshold structure; and propose a best guess on the optimal probing sequence, which is validated by extensive simulations. These results indicate that the user could easily make the right decisions on when and which relay to use simply by comparing the current observed link quality with the threshold. Simulation results show that our proposed scheme yields substantial throughput gain over other approaches. We also analyze the impact of different parameters on the system performance.
BIO
Yuan Lin received her B.S. degree and M.S. degree from PLA University of Science and Technology, Nanjing, China in 2008 and 2011 respectively. She is currently pursuing his Ph.D degree in PLA University of Science and Technology. Her current research interests include wireless communication, satellite communication and relay selection.
Bowen Li received his B.S. degree in wireless communication and Ph.D degree in communication and information system from Institute of Communication Engineering at the PLA University of Science and Technology, China, in 2007 and 2012 respectively. He is currently a Postdoctoral Fellow in the School of Software and TNLIST, Tsinghua University. His main research interests include stochastic optimization, energy efficient wireless design and cognitive networking.
Hao Yin received the BS and MS degree from Nanjing University of Posts and Telecommunications in 1982 and 1987, the Ph. D degrees from Beijing Institute of Technology. He is currently a professor at Institute of Electronic System Engineering, China. He has published widely in the areas of communication networks. His current research interests include wireless communication, satellite communication and complex environment communication network theory.
Yuanzhi He received her B.S. degree and M.S. degree from PLA University of Science and Technology, Nanjing, China. She is currently a professor at Beijing Institute of Electronic System Engineering, Beijing, China. Her research interests focus on satellite communication, satellite network and wireless network.
Laneman J. N.
,
Tse D. N.
,
Wornell G. W.
2004
“Cooperative diversity in wireless networks: Efficient protocols and outage behavior,”
IEEE Transactions on Information Theory
50
(12)
3062 
3080
DOI : 10.1109/TIT.2004.838089
Booysen M. J.
,
Gilmore J. S.
,
Zeadally S.
,
Rooyen G. J. V.
2012
“MachinetoMachine(M2M)Communication in Vehicular Networks,”
KSII Transactions on Internet and Information Systems
6
(2)
Zhou Y.
,
Fei Z. S.
,
Huang G. S.
,
Yang A.
,
Kuang J. M.
2013
“A Distributed LT Codesbased Date Transmission Technique for Multicast Services in Vehicular Adhoc Networks,”
KSII Transactions on Internet and Information Systems
7
(4)
Wu D.
,
Zhu G.
,
Zhu L.
,
Ai B.
2012
“Trustbased Relay Selection in Relaybased Networks,”
KSII Transactions on Internet and Information Systems
6
(10)
An B.
,
Duy T. T.
,
Kong H. Y.
2009
“A Cooperative Transmission Strategy using Entropybased Relay Selection in Mobile Adhoc Wireless Sensor Networks with Rayleigh Fading Environments,”
KSII Transactions on Internet and Information Systems
1
(3)
Bletsas A.
,
Khisti A.
,
Reed D. P.
,
Lippman A.
2006
“A simple cooperative diversity method based on network path selection,”
IEEE Journal on Selected Areas in Communications
24
(3)
659 
672
DOI : 10.1109/JSAC.2005.862417
Soysa M.
,
Suraweera H. A.
,
Tellambura C.
,
Garg H. K.
2012
“Partial and Opportunistic Relay Selection with Outdated Channel Estimates,”
IEEE Transactions on Communications
60
(3)
840 
850
DOI : 10.1109/TCOMM.2012.12.100671
Ju MC
,
Kim IM
2012
“Joint relay selection and relay ordering for DFbased cooperative relay networks,”
IEEE Transactions on Communications
60
(4)
908 
915
DOI : 10.1109/TCOMM.2012.030712.1001762
Ji B.
,
Song Kang
,
Huang Yongming
,
Yang Luxi
2013
“A cooperative relay selection for twoway cooperative relay networks in Nakagami channels,”
Wireless personal communications
71
(3)
2045 
2065
DOI : 10.1007/s112770120922x
Gong X.
,
Chandrashekhar T.
,
Zhang J.
,
Poor H. V.
2012
“Opportunistic cooperative networking: To relay or not to relay?”
IEEE Journal on Selected Areas in Communications
30
(2)
307 
314
DOI : 10.1109/JSAC.2012.120209
Jing T.
,
Zhu S.
,
Li H.
,
Cheng X.
,
Huo Y.
“Cooperative relay selection in cognitive radio networks,”
in Proc. of IEEE Conf. on Computer Communications
April 1419, 2013
175 
179
HostMadsen A.
,
Zhang J.
2005
“Capacity bounds and power allocation for wireless relay channels,”
IEEE transactions on Information Theory
51
(6)
2020 
2040
DOI : 10.1109/TIT.2005.847703
Gradshteyn I. S.
,
Ryzhik I. M.
,
Jeffrey A.
,
Zwillinger D.
,
Technica S.
1965
Table of integrals, series, and products
Narandzic M.
,
Schneider C.
,
Thoma R.
,
Jamsa T.
,
Kyosti P.
,
Zhao X.
“Comparison of scm, scme, and winner channel models,”
in Proc. of IEEE Conf. on Vehicular Technology
2007
413 
417
Maham B.
,
Hjorungnes A.
2009
“Performance analysis of amplify and forward opportunistic relaying in rician fading,”
IEEE Signal Processing Letters
16
(8)
643 
646
DOI : 10.1109/LSP.2009.2021683
Suraweera H. A.
,
Louie R. H.
,
Li Y.
,
Karagiannidis G. K.
,
Vucetic B.
2009
“Two hop amplifyandforward transmission in mixed rayleigh and rician fading channels,”
IEEE Communications Letters
13
(4)
227 
229
DOI : 10.1109/LCOMM.2009.081943
Proakis J.
2001
Digital Communications
McGrawHill