Tài liệu Network coding on cooperative relay networks

Contents Abstract 1 1 Introduction 1 1.1 1.2 1.3 Introduction to cooperative relay networks . . . . . . . . . . . . . . . . . . . 1 1.1.1 The relay protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.2 Advantages of Cooperative Diversity Relaying Networks . . . . . . . 5 Introduction to Network Coding . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2.1 Non-Binary and Binary Network Coding . . . . . . . . . . . . . . . . 8 1.2.2 Advantages of Network Coding . . . . . . . . . . . . . . . . . . . . . 9 1.2.3 Weaknesses of Network Coding . . . . . . . . . . . . . . . . . . . . . 11 Cooperative Diversity Relaying Networks using network coding . . . . . . . . 13 2 System models 15 2.1 Traditional Relay Multiple-Wireless Networks . . . . . . . . . . . . . . . . . 16 2.2 Single Relay Networks using Network Coding . . . . . . . . . . . . . . . . . 20 2.3 Multiple-Relay Networks using Network Coding . . . . . . . . . . . . . . . . 22 3 Outage Probability Calculations 24 3.1 Mutual Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.2 Outage Probability Definition . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.3 Outage Probability of Multiple-Relay Networks . . . . . . . . . . . . . . . . 27 3.3.1 Traditional Decode-and-Forward relaying . . . . . . . . . . . . . . . . 27 3.3.2 Selection Decode-and-Forward relaying . . . . . . . . . . . . . . . . . 29 3.4 Outage Probability of Single Relay Networks using Network coding . . . . . 32 3.5 Outage Probability of Multiple-Relay Networks using Network Coding . . . . 36 Conclusions and Future Works 42 iii Bibliography 43 iv List of Figures 1.1 Frequency Diversity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Space Diversity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Cooperative relay network . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4 An example of Network Coding . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.5 An example of Non-linear Network Coding . . . . . . . . . . . . . . . . . . . 8 1.6 An example of linear Network Coding . . . . . . . . . . . . . . . . . . . . . . 9 1.7 The butterfly network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.8 The weakness of Network Coding . . . . . . . . . . . . . . . . . . . . . . . . 12 2.1 A traditional single relay network . . . . . . . . . . . . . . . . . . . . . . . . 19 2.2 A traditional multiple-relay network . . . . . . . . . . . . . . . . . . . . . . . 19 2.3 Network coding in single relay network . . . . . . . . . . . . . . . . . . . . . 20 2.4 Multiple-relay network using network coding . . . . . . . . . . . . . . . . . . 22 3.1 The direct link between the input and the output . . . . . . . . . . . . . . . 25 3.2 Outage probability of a direct link . . . . . . . . . . . . . . . . . . . . . . . . 27 3.3 Outage Probability of fixed and selection DF relay . . . . . . . . . . . . . . . 32 3.4 The degraded system model of a single relay network based on NC . . . . . . 34 3.5 The degraded system model of a single relay network based on NC . . . . . . 35 3.6 Outage probability of the single relay network with and without network coding 36 3.7 Link s1 r1 is in outage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.8 Outage probability of relay networks with different scenarios . . . . . . . . . 41 v 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 The sharp increase in the number of mobile subscribers which needs large bandwidth for multimedia applications anywhere and anytime requires the network service providers to optimize and develop the current technologies in order to ensure that the Quality of Services (QoS) is always satisfied. Diversity scheme are used to improve the reliability of a message signal by transmitting multiple version of the same signal over different communication channels. Because of time-varying channel conditions, the diversity plays an important role in combating fading and co-channel interference. Diversity techniques are divided into the following types: time diversity, frequency diversity, space diversity, polarization diversity, muiltiuser diversity! [1] . • Time diversity: The transmitter sends the same data at different time instants or a redundant error correcting code is added into the messages before transmitting. Repetition coding is one of the most popular types of time diversity. 1 • Frequency diversity: The signal transmitted by using different frequency channels on a single antenna. At the destination, it requires the number of receivers as the number of frequencies used at the transmitter. It therefore requires more spectrum usage. Transmitter 1 Transmitted signal antenna Receiver 1 Recovered signal antenna Transmitter 2 Receiver 2 Figure 1.1: Frequency Diversity • Spatial diversity. The signal is transmitted over different path by using several antennas at the transmitter in order to allow multiusers to share a spectrum and avoid co-channel interference. Figure 1.2: Space Diversity • Polarization diversity: The same messages are transmitted and received by using antennas with different polarization. A diversity combining technique designed to combine the multiple received signals at the destination is used in this case. 2 • Multiuser diversity: In this technique, the transmitter and receiver rely on the quality of the link between the transmitter and each receiver in order to selects the best partner. 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. 3 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. In Fixed relaying protocols, the relay either amplifies what it receives, or fully decodes, re-encodes, and re-transmits the source message. These fixed relaying options are called amplify-and-forward (AF) and decode-and-forward (DF), respectively. Amplify and Forward is the protocol in which the relay receives the signal form the source and amplifies it before forwarding to the destination. While, Decode-and-Forward relay decodes and re-encodes the received message before sends it to the destination. Note that the decoded signal at the relay may be incorrect. If an incorrect signal is forwarded to the destination, the decoding at the destination is meaningless [2]. Therefore, sometimes the relay must be silent because it can not detect the presence of the signal or the signal quality is not good enough for the relay to decode fully the messages. Selection relaying (SR) protocol is designed to overcome the shortcomings of DF relaying when the measured SNR at the relay falls below a threshold that the relay becomes unable to decode the message, the source simply continues its direct transmission to the destination using repetition coding or other more powerful codes. In incremental relaying (IR) protocol, the relay only transmits upon a neg4 ative feedback from the destination. Fixed relaying makes inefficient use of relay channel resources when operating at high rates because the relays repeat all the time, and under good transmission conditions this is un-necessarily. In IR networks, the destination sends a one-bit ACK to the source and the relay if it can successfully decode message from the source, otherwise it sends a NACK to signal it fails to decode the message. Only when the relay receives a NACK and if it is able to decode the source message, it will forward the message to the destination by employing AF relaying. The destination receiver then uses maximum ratio combining (MRC) of the signal from the source and the relay to build up its receive SNR until it can successfully decode the message. This is equivalent to using the well known repetition coding technique to combat deep fading situations. 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. Figure 1.3 shows a network model using M relays. The operation of this model can be divided into M + 1 time slots. In the first time slot, the source sends its messages to the relays and the destination using the broadcast method. The relay i relies on the defined protocol to receive and process the source message before retransmitting it to the destination in timeslot i. The presence of the signal is decided at the destination by comparing the 5 measured SNR with a threshold. R1 R2 Direct link S Broadcast mode RM D Broadcast mode Figure 1.3: Cooperative relay network The operation of each relay is independent of the others, so that there is no correlation among all channels. We will show that the diversity gain and the robustness of this system model is increased significantly. It is clear that the destination can not decode a source’s messages if and only if all links connecting the M relays and that source to the destination are in outage. Assuming that the outage probabilities of these links are the same, and denoted by p. Then the probability of system outage event is pout = pM +1 . In [4], the diversity gain is defined as D, − log P SN R→∞ log SN R lim (1.1) in which P is the outage probability, SN R is the signal to noise ratio. Then D= − log P M +1 ≈M +1 SN R→∞ log SN R lim (1.2) Equation 1.2 indicates that 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 6 has been overcome. However, in cooperative relay network shown in figure 1.3, 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 developed 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. Figure 1.4: An example of Network Coding In figure 1.4, both N1 and N2 want to send their signal to node N4 using 7 broadcast mode. When network coding is applied, the intermediate node will combine these signals into an output before retransmitting to the destination. The question are how the intermediate node combine them and how the destination node detect the received messages. When we study on the protocol of the intermediate node, we can divide network coding into binary and non-binary network coding. 1.2.1 Non-Binary and Binary Network Coding In binary network coding showed in figure 1.5, the intermediate node uses XOR operator to consolidate the received messages transmitted form sources. Because XOR operator is only used to add two binary bits, the input data S1 x1 R S2 x1  x2 D x2 Figure 1.5: An example of Non-linear Network Coding must be in binary form. It means that the data must be decoded over GF (2) and it only supports two sources. The main benefit of non-linear network coding is simple and can be easily implemented by a hardware. However, it is sub-optimal [7]. It means that, the diversity order of system does not change 8 when we increase the number of relays. 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. Figure 1.6 is an example of linear network coding with two sources and one relay. a1 and a2 are elements of GF (2q ); x1 and x2 are decoded over GF (2q ). One drawback of using network S1 x1 R S2 a1 x1  a2 x2 D x2 Figure 1.6: An example of linear Network Coding coding over non-binary fields may be higher complexity, since computations in large finite fields are more complex than over the binary field. Therefore, it also causes worse transmission delay and more bandwidth consumption. [8]. So that, in general case, we cannot conclude which better linear or non-linear network coding. In this thesis, we only concentrate on binary network coding. 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. To prove this point, 9 we consider a typical model of network coding which is called the butterfly network (see Figure 1.7) [9]. S b1 1 b1 b2 S b1 b2 1 2 b1 b2 3 b1 2 3 b1 b 2 b1 b2 b1  b2 4 b2 4 D2 D1 b2 D1 b1  b2 (a) D2 (b) Figure 1.7: The butterfly network In this network, the source node S wants to send its signal in the form bits b1 and b2 to two destination nodes D1 and D2 over different output channels by using multi-cast mode. Figure 1.7a indicate that b1 is sent on channel (s, 1) and b2 is sent on channel (s, 2). The received signal at the intermediate nodes 1 and 2 are b1 and b2 , respectively. In turn, node 1 (or 2) broadcast their signal to destination D1 and node 3 ( or D2 and node 3) by using two channels (1, D1 ) and (1, 3) (or (2, D2 ) and (2, 3)). Now, we consider the input and output of the node 3. There are two input channels but only one output channel (3,4). Normally, node 3 has to choose either b1 or b2 to send to the node 4. Suppose the b1 is sent to the node 4 by using link (3, 4) as in 10 Figure 1.7a. To complete the transmission, the node 4 broadcast b1 to the destination D1 and D2 . Finally, at the node D2 , both b1 and b2 are received. While, at node D1 , two copies of b1 are received, therefore the problem is that b2 cannot be recovered. (b1 ⊕ b2 ) ⊕ b1 = (b1 ⊕ b1 ) ⊕ b2 = b2 However, if network coding is applied at node 3 as shown in 1.7b, this problem may be solved. In Figure 1.7b, node 3 receives both b1 and b2 then combines them into a unique signal by using modulo 2 addition before retransmitting it to node 4. Then, the signal at the destination D1 are b1 ⊕ b2 and b1 . In order to recover b2 , we add b1 ⊕ b2 and b1 by using module 2 operator. It is similar to recover b1 at the destination D2 . This network model illustrates an important point: If network coding is not applied at node 3, in order to send both b1 and b2 to D1 and D2 , we must use more capacity at channel (3, 4) or more timeslot. So that, we may conclude that network coding can increase throughput for broadcast network. 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 [10]. Considering the scenario shown in Figure 1.7, the channel between the source S and the intermediate node 2 is faded. It mean that node 2 is unable to decode the received messages successfully. Then, it could send incorrect messages to 11 node 3 and the destination D2 . Therefore, combing and encoding the signals transmitted from node 1 and node 2 at node 3 is incorrect even when the channels s − 1 and 1 − 3 are perfect. After several transmission phases, there are two messages at the destination D1 : b1 (correct or incorrect) and b1 ⊕ b2 (incorrect). It means that b1 is detected by using incorrect messages. b1 S 1 b2 b2 2 3 b1 1b1 2b2 b2 4 D1 1b1 2b2 D2 Error dectection Figure 1.8: The weakness of Network Coding 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 necessary 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 12 time services (e.g video transmission,...). 1.3 Cooperative Diversity Relaying Networks using network coding As discussion above, both cooperative diversity relaying and network coding have advantages and weaknesses thus combining cooperative relaying with channel coding should be studied to achieve significant benefits and overcome some drawbacks. In an NC-based network, a source node sends messages to a destination node via a number of relay nodes whereby an intermediate node first encodes the messages received from its input nodes into a new message and then sends this message to its output nodes. By decoding its inputs, the destination node can recover the original messages sent by the source node. The most common example of NC-based network model is two-source onerelay 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 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 13 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]. 14 Chapter 2 System models In theory, the relay node can operate in both time-division (TD) and frequency-division (FD). If the frequency-mode method is applied, the bandwidth W is divided into a bandwidth of αW where the relay node listens and (1 − α)W where the relay transmits. The destination node pays attention the whole bandwidth W. Similarly, if the time-division mode is applied, then for a given time window D, in the relay-receive phase, the relay uses a fraction of time αD to received the messages from its source and uses the remaining time (1 − α)D of the window to send the received messages to its destination. It is clear that from an information-theoretic point of view, there is no different between TD mode and FD mode for the fixed channel gain case. In fading channels, however, the TD mode has more benefit than the FD mode because can be adjusted to the instantaneous channel conditions, whereas α is often fixed in the FD mode [17]. So, in this thesis, we only deal with the relays operating in the TD mode. In fixed DF relaying, the relay decodes the received message from the source and sends it to the destination. The decoded message at the relay can be 15 correct or incorrect. If an incorrect signal is transmitted to the destination, the decoding at the destination is meaningless. It is clear that the diversity order of this scheme is only one, because the performance of the system is limited by the worst of the source−relay and source−destination links. Selection relaying (SR) protocol is designed to overcome the shortcomings of DF relaying when the measured SNR at the relay falls below a threshold that the relay becomes unable to decode the message, the source simply continues its direct transmission to the destination using repetition coding or other more powerful codes. In this thesis, we only consider the relay using selection Decode-and-Forward protocol in Time-Division mode. 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. In phase 1 called the relay-receive phase, the sources S1 , S2 transmit the N -symbol message to both the destination D and the relays R1 ,R2 , i.e, the broadcast mode is applied. We assume that the transmitted power of each relay is constant, then the received signals at the relay R1 ,R2 and destination 16