** Communications and Network** Vol.2 No.2(2010), Article ID:1860,6 pages DOI:10.4236/cn.2010.22014

Performance Analysis of a Threshold-Based Relay Selection Algorithm in Wireless Networks

Department of Information and Communication Engineering, Xi’an Jiaotong University, Xi’an, China

E-mail: nhfly86@gmail.com

Received December 21, 2009; revised February 1, 2010; accepted March 1, 2010

**Keywords:** Relay Selection, Outage Probability, Threshold, Wireless Networks

Abstract

Relay selection is an effective method to realize the cooperative diversity gain in wireless networks. In this paper, we study a threshold-based single relay selection algorithm. A reasonable threshold value is set at each relay node, and the first relay with the instantaneous channel gain larger than the threshold will be selected to cooperate with the source. The exact and closed form expression for its outage probability is derived over independent, non-identically distributed (i.n.i.d) Rayleigh channels. The complexity of the algorithm is also analyzed in detail. Simulation results are presented to verify our theoretical analysis.

1. Introduction

User cooperation is a promising technique to improve the performance of wireless networks [1-3]. One possible approach to realize cooperative diversity is to use distributed space-time coding (DSTC) among participating nodes [4]. However, the design of such code is difficult in practice and is still an open area of research.

Aiming at these problems, Bletsas et al. introduced a novel scheme called opportunistic relaying in [5], where only the “best” relay among all available candidates is selected to cooperate with the source. Analysis in [5,6] proved that this method can provide the same diversity-and-multiplexing tradeoff (DMT) as DSTC. However, as pointed in [5], a distributed relay selection may lead to packet collision which is a cause to fail the procedure, and the centralized approach requires a large number of channel estimations, which is energyinefficient and not practical for resource-constrained networks.

In order to overcome the above-mentioned drawbacks, Hwang and Ko proposed a sub-optimal relay selection algorithm in [7], where a pre-determined threshold is set both at the relay and the destination, and the first relay with equivalent channel gain larger than the threshold is selected. This algorithm can significantly reduce the implementation complexity and power consumptions compared with the conventional opportunistic relaying algorithm. However, reference [7] didn’t present the exact outage probability formula of the algorithm.

In this paper, we follow the basic ideas of [7] while some detailed analyses are presented. The main contribution of our work is that we derive the exact closed form expression for the outage probability of the algorithm over independent, non-identically distributed (i.n.i.d) Rayleigh channels. We will show that this algorithm can achieve the same diversity order as opportunistic relaying, while its complexity in terms of the amount of channel estimations can be reduced obviously.

2. System Model and Basic Assumptions

We consider a half-duplex dual-hop communication system as shown in Figure 1, where there are a source (), a destination () and K relay nodes (,).

There are two types of relay selection, reactive and proactive [6], and we only focus on the latter. That is to say, the “best” relay is chosen prior to the source transmission among a collection of K possible candidates. After this has been completed, a two-phase communication starts. During the first phase, the source transmits and the “best” relay listens, while during the second phase, the “best” relay forwards a version of the received

(1)

signal to the destination using decode-and-forward (DF) protocol [1].

For each link, the channel is assumed to be block flat fading (quasi-static), which remains constant during one frame and varies independently from frame to frame (In our system, one frame is comprised of two phases). The channel gain, i.e., the squared channel strength, between the source and the destination, the source and the kth relay, and the kth relay and the destination are represented by, and, respectively (). The channel coefficients are modeled as zero-mean, independent, circularly-symmetric complex Gaussian random variables, so, and obey exponential distributions and notations, and are introduced to denote their distribution parameters.

In the following analysis, we consider two communication scenarios. For Scenario I, the direct link between the source and the destination doesn’t exist, i.e., the source communicates with the destination only via relaying. For Scenario II, the source can communicate with the destination directly, and the destination combines the two received signals coming from the source and the best relay with a maximal ratio combiner (MRC).

3. Review of the Threshold-Based RelaySelection Algorithm

The relay selection procedure is activated before every source transmission, the operation of the algorithm was described in [7] and we summarize it as follows.

Figure 1. The block diagram of the half-duplex dual-hop system.

Step 1: Initialize k = 0.

Step 2: Set k ← k + 1, if k = K + 1, go to Step 4.

Step 3: If the instantaneous channel gain of the kth relay is larger than the predetermined threshold value, i.e., relay k is selected as the best relay and the algorithm terminates:, otherwise go to Step 2.

Step 4: Evaluate and select node as the best relay.

In the algorithm above, th is the predetermined threshold value and denotes the “best” relay. Note that we use the minimum of the channel gains between the links and to describe the channel quality at relay k, which is consistent with the statements in [6,7].

4. Research of the Threshold-Based RelaySelection Algorithm for Scenario I

4.1. Outage Probability of the Algorithm

Theorem 1: Denoting the required spectral efficiency by R and the average transmit signal-to-noise by SNR, the outage probability of the threshold-based algorithm can be expressed by (1), where.

Proof: Communication through the “best” relay fails due to outage when either of the two hops (from the source to the best relay and from the best relay to destination) fails. Thus the outage probability can be expressed as [8]:

(2)

For each i, letting represent the minimum of and, i.e., , we can see that the probability in (2) depends on the statistical property of.

Recall that the algorithm selects the first relay with the instantaneous channel gain larger than the threshold as the best relay, and if no such relay exists, the best relay is selected as the opportunistic relaying method does, so we have to consider two cases to calculate the probability.

Case 1: The channel gains of all relays are below the threshold.

By using the fact that the minimum of two independent exponential random variables with parameter and is again an exponential random variable with parameter, the probability of case 1 can be calculated as

(3)

For case 1, is the relay node with the largest channel gain and the outage probability conditioned on case 1 is given by

(4)

Case 2: At least one relay has the channel gain lager than th.

This case is the complementary event of case 1 and its probability is given in (5).

(5)

For case 2, is the first relay with channel gain lager than the threshold and the corresponding outage probability formula is expressed as

(6)

So the outage probability conditioned on case 2 is given in (7).

(7)

Finally, the outage probability of the algorithm can be evaluated, using total probability formula, as

(8)

Substituting (3), (4), (5), (7) into (8) and with the help of the following multinomial expansion [9], (1) can be obtained. However, we omit the details of this procedure due to the limitation of space.

(9)

4.2. Discussion on the Results

The result in (1) may be attractive because it indicates that the threshold-based relay selection algorithm can achieve the same outage probability as opportunistic relaying in [6] when a suitable threshold value is determined, despite its simplicity.

Intuitively, to select the threshold value equal to, called outage threshold, is a simple but reasonable choice. Note that depends only on the required spectral efficiency and average transmit signal-to-noise ratio, so th need not to be updated frequently during the communication procedure, which reduces the complexity of the algorithm obviously.

Computer simulations are carried out to validate the analytical expressions. In Figure 2, we compare the outage probability of the threshold-based scheme to that of opportunistic relaying [5] over the channel described in Section 2. To see the differences of the two algorithms clearly, we only give the results for low SNR regimes. In this simulation, we assume the nodes of the whole network are distributed in a 1 × 1 rectangular coordinate system. The source node is located at (0,0) and the destination node at (1,1), K = 4 relay nodes are generated randomly and the mean of the fading coefficient between node i and j is determined by the distance between them, i.e., where the path loss exponent is set to be. We assume R = 1 and set th = 1. As can be seen from the figure, there is an excellent match between the curves of analytical results and simulation ones. The results show that when SNR > 5 dB, i.e., th > γ, the outage probability of threshold-based relay selection algorithm is exactly the same as that of opportunistic relaying, whereas there is a performance loss if SNR < 5 dB, i.e.,. These observations are consistent with the results in (1).

Figure 2 also shows the outage probability for random selection method. It is noticeable that random selection incurs a substantial penalty loss. This is due to the fact that selecting the “best” relay randomly removes potential selection diversity benefits.

Now we consider the complexity of the thresholdbased algorithm in terms of the amount of channel estimations and compare it with that of opportunistic relaying method in [5,6]. The opportunistic relaying needs the 2K number of channel estimations, while the average number of channel estimations of thresholdbased method can be evaluated by (10)^{1}.

(10)

It is not hard to achieve the closed form expression of (10) but this may be not helpful to analyze. Instead, we use numerical calculations to give some intuitive results in Table 1, where we set = 1, = 0.7 () for convenience.

Table 1. Complexity comparison.

Figure 2. The outage probabilities of random selection, opportunistic relaying, and threshold-based algorithm without the direct link.

Figure 3. The outage probabilities of opportunistic relaying and threshold-based algorithm without the direct link.

From the results above we can conclude that the threshold-based relay selection algorithm is especially attractive in large networks. Besides that, the lower the threshold value is, the less the number of channel estimations is. However, reducing the threshold will incur a performance loss. Therefore, considering both the performance and complexity, we select the optimal threshold value th equal to. In Figure 3, we compare the outage probability of the threshold-based scheme to that of the opportunistic relaying [5] with th =.

5. Research of the Threshold-Based Relay Selection Algorithm for Scenario II

In this section, we investigate the performance of the algorithm for Scenario II. The channel gain between the source and the destination is denoted by g. For simplicity, we set th =.

Similar to Section 4, we consider two cases and calculate the outage probability as follows.

Case 1: The channel gains of all relays are below the threshold, i.e.,. The probability of this case can be represented by

(11)

In this case, is the relay node with the largest channel gain and the outage event happens if either of the three situations takes place,

(16)

(12)

After some calculations, the outage probability is given by (13).

(13)

Using total probability formula, the outage probability conditioned on case 1 can be expressed as

(14)

Figure 4. The outage probabilities of opportunistic relaying and threshold-based algorithm with direct link.

Case 2: At least one relay has the channel gain lager than th. In this case, the outage probability is obviously zero. That is to say,

(15)

Finally, the outage probability of the algorithm is expressed by (16).

In Figure 4, we compare the outage probability of the threshold-based scheme to that of opportunistic relaying [5] with th = for Scenario II, the simulation conditions are the same as that for Figure 2. Simulation results also validate our analytical conclusions.

6. Conclusions

In this paper, we have studied a threshold-based single relay selection algorithm for wireless networks. The analytical closed form expressions of its outage probability are derived. Through computer simulations we analyze the performances of the algorithm. The results show that this method can achieve the same outage probability as that of opportunistic relaying with a suitable threshold, while its complexity is obviously reduced.

7. References

[1] J. N. Laneman, D. N. C. Tse and G. W. Wornell, “Cooperative Diversity in Wireless Networks: Efficient Protocols and Outage Behavior,” IEEE Transactions on Information Theory, Vol. 50, No. 12, December 2004, pp. 3062-3080.

[2] K. J. R. Liu, A. K. Sadek, W. Su and A. Kwasinski, “Cooperative Communications and Networking,” Cambridge University Press, Cambridge, 2008.

[3] S. Chen, W. Wang and X. Zhang, “Performance Analysis of Multiuser Diversity in Cooperative Multi-relay Networks under Rayleigh-Fading Channels,” IEEE Transactions on Wireless Communications, Vol. 8, No. 7, July 2009, pp. 3415-3419.

[4] J. N. Laneman and G. W. Wornell, “Distributed SpaceTime Coded Protocols for Exploiting Cooperative Diversity in Wireless Networks,” IEEE Transactions on Information Theory, Vol. 49, No. 10, October 2003, pp. 2415-2525.

[5] A. Bletsas, A. Khisti, D. P. Reed and A. Lippman, “A Simple Cooperative Diversity Method Based on Network Path Selection,” IEEE Journal on Selected Areas in Communications, Vol. 24, No. 3, March 2006, pp. 659-672.

[6] A. Bletsas, H. Shin and M. Z. Win, “Cooperative Communications with Outage-Optimal Opportunistic Relaying,” IEEE Transactions on Wireless Communications, Vol. 6, No. 9, September 2007, pp. 3450-3460.

[7] K.-S. Hwang and Y.-C. Ko, “An Efficient Relay Selection Algorithm for Cooperative Networks,” 2007 IEEE 66th Vehicular Technology Conference, Baltimore, 30 September-3 October 2007, pp. 81-85.

[8] A. Bletsas, “Intelligent Antenna Sharing in Cooperative Diversity Wireless Networks,” Ph.D. Dissertation, Massachusetts Institute of Technology, Cambridge, 2005.

[9] F. Xu, C. M. Lau, Q. F. Zhou and D. W. Yue, “Outage Performance of Cooperative Communication Systems Using Opportunistic Relaying and Selection Combining Receiver,” IEEE Signal Processing Letters, Vol. 16, No. 4, February 2009, pp. 237-240.

NOTES

^{1}In fact, the actual amount is less than this, however, we use (10) for simplicity.