Advanced
Throughput-efficient Online Relay Selection for Dual-hop Cooperative Networks
Throughput-efficient Online Relay Selection for Dual-hop Cooperative Networks
KSII Transactions on Internet and Information Systems (TIIS). 2015. Jun, 9(6): 2095-2110
Copyright © 2015, Korean Society For Internet Information
  • Received : November 19, 2014
  • Accepted : May 03, 2015
  • Published : June 30, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Yuan Lin
Institute of Communication Engineering, PLAUST Nanjing, China
Bowen Li
School of Software and TNLIST, Tsinghua University Beijing, China
Hao Yin
Beijing Institute of Electronic System Engineering Beijing, China
Yuanzhi He
Beijing Institute of Electronic System Engineering Beijing, China

Abstract
This paper presents a design for a throughput-efficient online relay selection scheme for dual-hop multi-relay cooperative networks. Problems arise with these networks due to unpredictability of the relaying link quality and high time-consumption to probe the dual-hop link. In this paper, we firstly propose a novel probing and relaying protocol, which greatly reduces the overhead of the dual-hop link estimation by leveraging the wireless broadcasting nature of the network. We then formulate an opportunistic relay selection process for the online decision-making, which uses a tradeoff between obtaining more link information to establish better cooperative relaying and minimizing the time cost for dual-hop link estimation to achieve higher throughput. Dynamic programming is used to construct the throughput-optimal 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.
Keywords
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 machine-to-machine [2] and vehicular ad-hoc 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 decode-and forward (DF) two hop relay networks are discussed in [8] . In [9] , the author investigate the performance of the best-worse relay selection strategy in a two way cooperative non-regenerative 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.
Probe-based 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 throughput-efficient relay probing and selection in dual-hop 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 dual-hop links by flexibly leveraging the wireless broadcasting nature of the network. In contrast in [10] , a time-efficient 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 throughput-optimal 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 source-relay (S-R) and relay-destination (R-D) 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 dual-hop 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 Ri , i = 1, 2,..., N , and the source can choose any of the relays for data relaying.
PPT Slide
Lager Image
System model
The links between S - R and R - D as well as the links across relays are subject to independent and non-identical fading. Let
PPT Slide
Lager Image
denote the average SNR of the S - R and R - D links, respectively. When the instantaneous dual-hop link qualities for relay Rn (i.e.,
PPT Slide
Lager Image
are available, the instantaneous achievable rate of the half-duplex DF relaying transmission is given by [12 , 13] :
PPT Slide
Lager Image
For a typical multipath propagation environment, the received SNR γ is distributed exponentially with p.d.f:
PPT Slide
Lager Image
where
PPT Slide
Lager Image
is the average received SNR, and the CDF is given by:
PPT Slide
Lager Image
- 2.2 Probing and Relaying Protocol
In dual-hop 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 dual-hop 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 tRD and a SIFT(Short Inter Frame Time) τ ' . The SIFT τ ' > tRD can guarantee the reception of a CTS packet if current node is selected by D.
PPT Slide
Lager Image
Time structure of probing and relaying protocol
We assume that D decides to select relay Rn 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 tRS = tSR is needed for the CTS packet to arrive at S , so during the remainder of the slot ∆ − 2 tSR , 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
PPT Slide
Lager Image
. The probing sequence is a permutation of each of the K relays, where
PPT Slide
Lager Image
and ⎿·⏌ is a round-down function. The sequence is the maximum number of probing steps in each slot, and
PPT Slide
Lager Image
denotes the corresponding kth relay in Φ m . During the tth slot, under the policy πm , if D decides to select the current relay node
PPT Slide
Lager Image
, k = 1, 2,..., K , then, the instantaneous reward of achievable rate is given by
PPT Slide
Lager Image
, where c = 2×( tSR ) is a constant.
The average system throughput is then given by:
PPT Slide
Lager Image
where
PPT Slide
Lager Image
, and Ck = 1 - - 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.:
PPT Slide
Lager Image
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 kth 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 kth relay in a dual-hop DF relaying system could be described using Equ. (1) as given in Equ. (6):
PPT Slide
Lager Image
In Equ. (6),
PPT Slide
Lager Image
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 Kth probing,
PPT Slide
Lager Image
is given by :
PPT Slide
Lager Image
where
PPT Slide
Lager Image
is the end-to-end SNR of the dual-hop DF relaying system, whose CDF is given by:
PPT Slide
Lager Image
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:
PPT Slide
Lager Image
where
PPT Slide
Lager Image
are the average received SNR of the S - R and R - D channels, respectively, and
PPT Slide
Lager Image
.
The expected reward of
PPT Slide
Lager Image
, ( 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
PPT Slide
Lager Image
where
PPT Slide
Lager Image
is the exponential integral function given in [ [14] , Eq. (8.211.1)].
For 0 < k < K
PPT Slide
Lager Image
The online control rule can then be given as follows. D probes a potential relay node
PPT Slide
Lager Image
based on the probing order Φ m , and obtains an instantaneous reward after the kth probe. D then compares the value of
PPT Slide
Lager Image
with the value of
PPT Slide
Lager Image
and decides to stop and select the current relay if
PPT Slide
Lager Image
, otherwise it continues to probe the next relay node.
Therefore, the corresponding stop rule πm can be given by a threshold sequence
PPT Slide
Lager Image
, where the thresholds are given by:
PPT Slide
Lager Image
- 3.2 Optimal Probing Order
In a dual-hop relaying system with N relay nodes, the set of all possible probing orders is given by |Ψ|= M = N !. Each element in Ψ , that is
PPT Slide
Lager Image
, 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 probing-based online relaying schemes.
Guess: Rank the relays in descending order
PPT Slide
Lager Image
. This is the optimal probing order for a half-duplex 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 two-hop 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
PPT Slide
Lager Image
Distribution of relay numbers
Distribution of probing costs
PPT Slide
Lager Image
Distribution of probing costs
PPT Slide
Lager Image
Distribution of simulation point
Our opportunistic relay selection scheme is summarized in Alg. 1 .
PPT Slide
Lager Image
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 relay-mobile link is considered to have Rayleigh fading, while the base station-relay link is observed to be a Rician link because of a strong line-of-sight (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] :
PPT Slide
Lager Image
where
PPT Slide
Lager Image
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
PPT Slide
Lager Image
and mean values
PPT Slide
Lager Image
, respectively. Here we define
PPT Slide
Lager Image
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:
PPT Slide
Lager Image
For the asymmetric fading channel scenario, we define
PPT Slide
Lager Image
for simplicity, to obtain
PPT Slide
Lager Image
and
PPT Slide
Lager Image
as given in Equ.(15) and Equ.(16):
For k = K
PPT Slide
Lager Image
For 0 < k < K
PPT Slide
Lager Image
where
PPT Slide
Lager Image
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 time-efficient 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 state-of-art 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 dual-hop links of each relay are observed in each probing step, the probing cost is tSR + tRD = 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 Ri and Ri 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 two-hop 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 two-hop 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.
PPT Slide
Lager Image
Average throughput versus normalized probing duration( Rayleigh/Rayleigh )
PPT Slide
Lager Image
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 two-hop 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 two-hop are with Rayleigh fading.
PPT Slide
Lager Image
Average throughput versus the number of relays(Rayleigh/Rayleigh)
PPT Slide
Lager Image
Average throughput versus the number of relays( Rayleigh//Rician)
6. Conclusion
In this paper, we proposed a probing-based opportunistic relaying protocol for dual-hop cooperative networks. Online control framework is developed to achieve throughput-optimal 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.
References
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 “Machine-to-Machine(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 Codes-based Date Transmission Technique for Multicast Services in Vehicular Ad-hoc Networks,” KSII Transactions on Internet and Information Systems 7 (4)
Wu D. , Zhu G. , Zhu L. , Ai B. 2012 “Trust-based Relay Selection in Relay-based Networks,” KSII Transactions on Internet and Information Systems 6 (10)
An B. , Duy T. T. , Kong H. Y. 2009 “A Cooperative Transmission Strategy using Entropy-based Relay Selection in Mobile Ad-hoc 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 DF-based 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 two-way cooperative relay networks in Nakagami channels,” Wireless personal communications 71 (3) 2045 - 2065    DOI : 10.1007/s11277-012-0922-x
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 14-19, 2013 175 - 179
Gamal A. E. 1979 “Capacity theorems for the relay channel,” IEEE Transactions on Information Theory 25 (5) 572 - 584    DOI : 10.1109/TIT.1979.1056084
Host-Madsen 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 amplify-and-forward 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 McGraw-Hill