Viet Nam National University, Ha Noi University of Engineering and Technology Lam Sinh Cong Network Coding On Cooperative Relay Networks Branch: Electronics and Telecommunications Technology Major: Electronics Engineering Code: 60 52 70 Master Thesis Summary Ha Noi-2012 Contents Abstract 1 1 Introduction 1 1.1 Introduction to cooperative relay networks . . . . . . . . . . . . . . . . . . . 1 1.1.1 The relay protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.2 Advantages of Cooperative Diversity Relaying Networks . . . . . . . 2 1.2 Introduction to Network Coding . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2.1 Non-Binary and Binary Network Coding . . . . . . . . . . . . . . . . 3 1.2.2 Advantages of Network Coding . . . . . . . . . . . . . . . . . . . . . 3 1.2.3 Weaknesses of Network Coding . . . . . . . . . . . . . . . . . . . . . 3 1.3 Cooperative Diversity Relaying Networks using network coding . . . . . . . . 3 2 System models 5 2.1 Traditional Relay Multiple-Wireless Networks . . . . . . . . . . . . . . . . . 5 2.2 Single Relay Networks using Network Coding . . . . . . . . . . . . . . . . . 6 2.3 Multiple-Relay Networks using Network Coding . . . . . . . . . . . . . . . . 8 3 Outage Probability Calculations 9 3.1 Mutual Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.2 Outage Probability Definition . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.3 Outage Probability of Multiple-Relay Networks . . . . . . . . . . . . . . . . 11 3.3.1 Traditional Decode-and-Forward relaying . . . . . . . . . . . . . . . . 11 3.3.2 Selection Decode-and-Forward relaying . . . . . . . . . . . . . . . . . 12 3.4 Outage Probability of Single Relay Networks using Network coding . . . . . 12 3.5 Outage Probability of Multiple-Relay Networks using Network Coding . . . . 16 Conclusions and Future Works 19 i Bibliography 19 ii List of Figures 2.1 A traditional single relay network . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 A traditional multiple-relay network . . . . . . . . . . . . . . . . . . . . . . . 6 2.3 Network coding in single relay network . . . . . . . . . . . . . . . . . . . . . 7 2.4 Multiple-relay network using network coding . . . . . . . . . . . . . . . . . . 8 3.1 The direct link between the input and the output . . . . . . . . . . . . . . . 10 3.2 Outage probability of a direct link . . . . . . . . . . . . . . . . . . . . . . . . 11 3.3 Outage Probability of fixed and selection DF relay . . . . . . . . . . . . . . . 13 3.4 The degraded system model of a single relay network based on NC . . . . . . 13 3.5 The degraded system model of a single relay network based on NC . . . . . . 14 3.6 Outage probability of the single relay network with and without network coding 15 3.7 Link s1 r1 is in outage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.8 Outage probability of relay networks with different scenarios . . . . . . . . . 18 iii Abstract In communication, Cooperative Diversity Relaying refers to devices communicating with one another with the help of relays in order to increase the performance of the network. However, in one timeslot, the relay only transmits the signal of one source. Therefore, Network Coding is introduced to improve the throughput of the network. Combining Cooperative Relay Network and Network Coding should be studied to achieve significant benefits and overcome some weakness. In this thesis, we consider the effect of Network Coding on Cooperative Relay Network. We propose to use Selection Decode-and-Forward instead of Traditional Decode-and-Forward protocol at the relay. We also use the instantaneous channel gains to calculate the outage probability of the proposal system model. The rest of the thesis is organized as follows. In Chapter II, the system model of a multiple-relay network is described. The outage probability is calculated in Chapter III. Finally, the conclusions and the future works are drawn in Section IV. Chapter 1 Introduction 1.1 Introduction to cooperative relay networks In recent years, MIMO (multi-input multi-output) technology based on spatial diversity and spatial diversity has attracted attention in wireless communication because it greatly improves the reliability, the throughput and the transmission rate without additional bandwidth nor requiring higher transmitter power. However, this technique requires both the transmitter and the receiver to have multi-antennas, and all channels must be independent. In practice, users do not often achieve full-rank MIMO because they either do not have multiple-antennas installed on a small-size devices, or the propagation environment cannot support MIMO, for example, there is not enough scattering. Even if the users have enough antennas, full-rank MIMO is not guaranteed because the links between several antenna elements are often correlated. To overcome the limitations in diversity gain MIMO, a new communication paradigm which uses an intermediate node to generate independent channel between the user and the base station was introduced. The intermediate node often called relay node receives the signal transmitted from the user and forward it to the base station. And this paradigm is called Cooperative Diversity Relaying Network. 1 1.1.1 The relay protocols A key aspect of the cooperative communication process is the processing of the signal received from the source node carried out by the relay. These different processing schemes depend on the protocols of the relays which can be generally categorized into fixed relaying schemes, selection relaying protocol (adaptive relaying schemes) and incremental relaying protocol. 1.1.2 Advantages of Cooperative Diversity Relaying Networks Cooperative Diversity Relaying refers to devices communicating with one another with the help of relays in order to increase the performance of the network [3]. Thereby, the relay channel can be considered as an auxiliary channel to the direct channel between the source and destination. In Cooperative Diversity Relaying, the user can guarantee the maximum diversity which is equal the number of the relays plus the direct link, i.e being the minimum cut at each source. It means that the limitation of MIMO technique has been overcome. However, in cooperative relay network, we are able to use one or more relays, but in one timeslot, the relay only transmits the signal of one source. 1.2 Introduction to Network Coding As discussed in the previous section, in a typical network, information is transmitted from the source node to each destination node through a chain of intermediate nodes by a method known as store-and-forward. In this method, the intermediate node only processes and transmits a unique signal at one time without overlapping, thus slow down the through. In order to increase the throughput of the network, network coding technique was introduced in [5] and then further devel- oped in [6], as a new paradigm which exploits the characteristics of the broadcast communication channel to combine several input signals into one output signal at the intermediate node. 2 1.2.1 Non-Binary and Binary Network Coding In binary network coding, the intermediate node uses XOR operator to consolidate the received messages transmitted form sources. In non-binary network coding, each intermediate node uses a linear equation to combine the inputs and the destination uses the system of linear equation to decode the received messages. 1.2.2 Advantages of Network Coding Increasing throughput achieved by increasing the efficiency of packet transmission is the most well-know benefit of network coding. 1.2.3 Weaknesses of Network Coding The main issue of using network coding is that if a transmission error occurs, it could affect the detecting and coding at the intermediate node, and the destination node could receive useless information. Besides, synchronization and transmission delay among the incoming data streams at the input of the intermediate node or destination node are also significant issues that need to be considered when network coding is applied. The transmitted data can not be recovered until all the neces- sary information is received. These are not big problems for non-real time services (e.g data and voice transmission), but they are should be considered carefully for real time services (e.g video transmission,...). 1.3 Cooperative Diversity Relaying Networks using net- work coding The most common example of NC-based network model is two-source one-relay topology, as shown in Figure 2.3. In this topology, two sources transmit their signals to the relay and the destination using broadcast technique. Then, the relay combines its received signals into a unique signal and sends it to destination. The traditional Decode-and-Forward (DF) protocol is often used 3 at the relay which decodes the messages from its input nodes before sending them to its output nodes. Often, the links between the sources and relay are assumed to be error-free so that the relay decodes the received messages successfully [3, 11–13]. In [14], taking into account of link errors, the relay is assumed to perform DF without error checking and the network codes are designed for error correction. In this thesis, instead of using DF relaying as in [14], we propose to use selection DF relaying at the relay. The selection DF relaying protocol is designed to overcome the shortcomings of DF relaying when the measured SNR at the relay falls below a threshold such that the relay becomes unable to decode the messages, the source simply continues its direct transmission to the destination using repetition coding [15]. In addition, we use Maximum Ratio Combining (MRC) at the destination. Finally, we analyze the performance of the proposed scheme in terms of outage probability by using the instantaneous channel gains. The analysis is based on a newly developed method for exact calculation of the outage probability [16]. 4 Chapter 2 System models 2.1 Traditional Relay Multiple-Wireless Networks In this section, we will discuss about end-to-end signal of the selection Decode-and-Forward relay. Relaying is assumed to operate in the time division mode having two phases (two time slots): the relay-receive phase and the relay-transmit phase. The total received signal at the destination is given by equation (2.1) and (2.2) √        ysi d   Ps hsi d 0  xsi  nsi d   = √   +   (2.1) yri d 0 Ps hri d xri nri d or √        ysi d   Ps hsi d 0  xsi  nsi d   = √   +   (2.2) ysi d 0 Ps hsi d x si nsi d Equatio Now, we consider a wireless network system model using two sources-and-one relay, as show in Figure 2.1. In this system model, the relay shares timeslot for both source S1 and S2 . Therefore, it require 4 timeslots to complete a transmission process. In order to increase the network’s throughput by reducing the number of timeslots, we increase the number of relay. Figure 2.2 shows a relay network using two relays (R1 , R2 ) with selection-DF protocol relaying information for two sources (S1 , S2 ) to the destination [18]. It is clear that it requires at least 3 time slots in order to complete a transmission process. 5 S1 (1) x1 (2)x1 R N4 (4)x2 S 2 (3)x 2 Figure 2.1: A traditional single relay network x1 R1 S1 x2 D S2 R2 Figure 2.2: A traditional multiple-relay network In this thesis, we review the calculation of the cumulative distribution function (cdf) of instan- taneous channel gains of various wireless links in a diversity relay network, which was published by the author of this thesis and his co-author in [16, 19]. 2.2 Single Relay Networks using Network Coding Figure 2.3 shows a single relay network with two sources using network coding [20]. • In timeslot 1: – S1 sends its signal x1 to both relay and destination by using broadcast mode. 6 S1 x1 hs1d hs1r hrd R x1  x2 D hs2 r hs2d S2 x2 Figure 2.3: Network coding in single relay network – The relay can or cannot decode x1 . • In timeslot 2 – If R can not decode x1 , S1 repeats sending x1 to D, thus D receives x1 on 2hs1 d – If R can decode x1 , S1 will do nothing in timeslot 2 and R store x1 in it and waits for x2 In the meantime – S2 transmits its signal x2 to relay and destination using broadcast mode. – R can or cannot decode x2 – If R cannot decode x2 , S2 repeats sending x2 to D, thus D receives x2 on 2hs2 d • In timeslot 3 – If the relay is unable to decode neither x1 nor x2 , it must be silent. – If the relay only decodes xi , it will forward xi to destination. – If the relay decodes x1 and x2 , successfully, it combines x1 and x2 by using XOR operator before sending it to the destination. When all source-relay links are perfect, the destination decodes the received messages by using algorithm: x1 ⊕ x1 ⊕ x2 = x2 or x2 ⊕ x1 ⊕ x2 = x1 7 Because of using less time slot than system model depicted in Figure 2.1, it indicate that system model can improve the throughput of the networks. Comparing with the system model depicted in figure 2.2, it cannot save any time slot, but we can save one relay. 2.3 Multiple-Relay Networks using Network Coding Figure 2.4 shows a multiple-relay network using coding in the cooperative relays, it is considered as a technique to improve the robustness. The system model under analysis is given by the multiple- access relay channel, where two source nodes, S1 and S2 , communicate with destination with the help of two relays R1 and R2 . The notation used for this system and their operation are the same S1 h s1d x1 R1 h r1 d x1  x2 x1  x2 MRC D R2 h r2 d x2 hs2r2 hs2d S2 Figure 2.4: Multiple-relay network using network coding in Session 2.2 for relay R1 and R2 . At destination, we use MRC to combine the signals from R1 and R2 in to a better signal of higher SNR. I hope that this may improve the robustness of the network. Note that, if both relays R1 and R2 are not able to decode the messages of source Si , Si repeats its transmission to the destination by using repetition code. In chapter 3, we will show that by using MRC, the performance of the network is increased. 8 Chapter 3 Outage Probability Calculations 3.1 Mutual Information The instantaneous capacity of the system is given by the instantaneous mutual information contained in the input-output vectors Xs and Yd for fixed channel realization matrix A, and it is I(Xs ; Yd |A) = h(Yd ) − h(Yd |Xs ) = h(Yd ) − h(AXs |Xs ) − h(N ) (3.1) Therefore [21] ARXs A∗   1 I(Xs ; Yd |A) = log2 det(Im + ) (3.2) M +1 RN where M is the number of relays; and the covariance matrices of the input signal and the noise are, respectively RXs = E{Xs Xs∗ } = Ps I and RN = E{N N ∗ } = N0 I 3.2 Outage Probability Definition In this section, we define the outage probability of direct transmission between two nodes. The received signal at the destination is given by y[n] = x[n]h[n] + w[n] 9 Figure 3.1: The direct link between the input and the output Where x[n], h[n] and w[n] are transmitted signal, channel gain, and Addition White Gaussian Noise (AWGN), respectively. We assume that h is independent and identically distributed. Thus, the maximum average information between the input and the output is given by using (3.2) with M = 0, A = h, SN R = P/No : I = log(1 + SN R|h|2 ) in which SN R is the received signal-noise ratio at the destination. The outage event of the information rate for a given threshold Rth is defined as: I ≤ Rth and equivalently [15] 2Rth − 1 |h|2 < = µth (3.3) SN R µth is called the channel power threshold. Then the outage probability is expressed as: Phout ij (µth ) = P (|hij |2 < µth ) (3.4) For Rayleigh fading, |hij |2 is exponentially distributed, with the probability density function (pdf) and cumulative density function (cdf) being respectively given by:     1 µ −µ fhij (µ) = exp − and Fhij (µ) = 1 − exp (3.5) µij µij µij Then, the outage probability is written as follow by combing (3.4) and (3.5)   µth Phout (µth ) = Fhij (µth ) = 1 − exp − (3.6) ij µij 10 Outage probability of one direct link 0 10 −1 10 Outage Probability µij=1 µij=2 −2 10 µ =3 ij −3 10 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 µth Figure 3.2: Outage probability of a direct link 3.3 Outage Probability of Multiple-Relay Networks 3.3.1 Traditional Decode-and-Forward relaying The maximum average mutual information between the input and the two outputs is expressed as below   1 1 IDF = min log(1 + γsd ), log(1 + γsd + γrd ) (3.7) 2 2 Then the instantaneous channel gain is |hDF |2 = min |hsd |2 , |hsd |2 + |hrd |2  (3.8) Then the outage probability of this model is given by [16] out PDF (µth ) = 1 − P (|hDF |2 > µth ) = 1 − P (|hsr |2 > µth )P (|hsd |2 + |hrd |2 > µth )   1 = 1 − (1 − Fsr (µth )) 1 − (µsd Fsd (µth ) − µrd Frd (µth )) (3.9) µsd − µrd where µth is calculate by using equation (3.3). 11 3.3.2 Selection Decode-and-Forward relaying The information rate of a selection DF relay network in this case can be expressed as below [22]:    1 log(1 + 2γ  si d ), γsi ri < γth  2 ISDF i = (3.10)   21 log(1 + γs1 d + γr1 d ), γsi ri ≥ γth   Because there is no correlation between the signals transmitted from source to the relays and from the relays to destination; and equal power from the sources and the relays, the instantaneous channel gain between the source and the destination is   2|hsi d |2 , |hsi ri |2 < µth   2 |hSDF i | = (3.11)  |hs1 d |2 + |hr1 d |2 , |hsi ri |2 ≥ µth   The probability of the event that the instantaneous channel gain falls below the threshold |hSDF i |2 < µth is out PSDF (µth ) = P (|hSDF |2 ≤ µth ) = P (2|hsi d |2 < µth )P (|hsi ri |2 < µth ) + P (|hsi ri |2 > µth )P (|hsi d |2 + |hri d |2 < µth ) (3.12) So, its outage probability under Rayleigh fading condition is [16] out µth 1 − Fsr (µth ) PSDF = Fsd ( )Fsr (µth ) + {µsd Fsd (µth ) − µrd Frd (µth )} (3.13) 2 µsd − µrd in which µth is defined as in equation (3.3). 3.4 Outage Probability of Single Relay Networks using Network coding We analyze all events which cause system outage. 12 −1 10 −2 10 −3 10 Outage Probability −4 10 −5 Fixed Decode−and−Forward Relay 10 Selection Decode−and−Forward Relay −6 10 −7 10 0 0.005 0.01 0.015 0.02 0.025 0.03 0.035 0.04 0.045 0.05 µth Figure 3.3: Outage Probability of fixed and selection DF relay • Link s1 r is in outage, then the source s1 repeats transmitting its signal to D. The system model in Figure 2.3 is degraded to the one which is depicted in Figure 3.4 S1 x1 hs1d hrd R x2 D hs2 r hs2d S2 x2 Figure 3.4: The degraded system model of a single relay network based on NC 13 Therefore, the outage probability of this degraded model is given by: p1 (µth ) =P (|hs1 r |2 < µth )P (2|hs1 d |2 < µth ) (3.14) • Link s1 r and s2 r are free of errors. It means that the relay decodes fully the sources’ messages, and then combine them into a unique signal before sending it to the destination. The system is in outage if both link s1 d and s2 d are in failure. The outage probability in this case is expressed as follows: p2 (µth ) =P (|hs1 r |2 > µth )P (|hs1 d |2 < µth ) P (|hs2 r |2 > µth ) P (|hs2 d |2 < µth ) + P (|hs2 d |2 > µth )P (|hrd |2 < µth )  (3.15) • Link s1 r is free of error, link s2 r is in outage, then the source s2 repeats transmitting its signal to D. In this case, the relay only sends the signal of the source s1 . The system model in this case is as shown in 3.5 S1 x1 hs1d hs1r hrd R x1 D hs2d x2 S2 Figure 3.5: The degraded system model of a single relay network based on NC Therefore, the outage probability in this case is given by: p3 (µth ) =P (|hs1 r |2 > µth )P (|hrd |2 + |Ps1 d |2 < µth )P (|hs2 r |2 < µth ) (3.16) 14 out (µ ) is calculated as follow: Finally, the outage probability of the system is PSDF th out PSDF (µth ) = p1 (µth ) + p2 (µth ) + p3 (µth ) (3.17) In which µth is the threshold which can be calculated from equation (3.3). In a Rayleigh fading environment, by using 3.6, we have:  p1 (µth ) = Fs1 r (µth )Fs1 d ( µ2th )           p2 (µth ) = (1 − Fs1 r (µth ))Fs1 d (µth )  (3.18)  (1 − Fs2 r (µth ))(Fs2 d (µth ) + (1 − Fs2 d (µth ))Frd (µth ))         p3 (µth ) = 1−Fs1 r (µrd Frd (µth ) − µs d Fs d (µth ))Fs r (µth )   µsr −µs d 1 1 1 2 −1 10 −2 10 Outage Probability −3 10 Traditional Multiple−Relay Wireless Network Only direct link Single Relay Network using Network Coding −4 10 −5 10 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1 µth Figure 3.6: Outage probability of the single relay network with and without network coding 15