UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Network coding based cooperative communications Kandhway, Kundan 2011

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
24-ubc_2011_spring_kandhway_kundan.pdf [ 421.45kB ]
Metadata
JSON: 24-1.0071609.json
JSON-LD: 24-1.0071609-ld.json
RDF/XML (Pretty): 24-1.0071609-rdf.xml
RDF/JSON: 24-1.0071609-rdf.json
Turtle: 24-1.0071609-turtle.txt
N-Triples: 24-1.0071609-rdf-ntriples.txt
Original Record: 24-1.0071609-source.json
Full Text
24-1.0071609-fulltext.txt
Citation
24-1.0071609.ris

Full Text

Network Coding Based Cooperative Communications by Kundan Kandhway B. Tech., Indian Institute of Technology Guwahati, 2008  A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF  Master of Applied Science in THE FACULTY OF GRADUATE STUDIES (Electrical and Computer Engineering)  The University Of British Columbia (Vancouver) February 2011 c Kundan Kandhway, 2011  Abstract Cooperative communications was proposed to enable spatial diversity in small and inexpensive devices. It allows the creation of virtual antenna array through the antennas of the participating users. The benefits offered by cooperation include increase in data rate, robustness against shadowing, decrease in overall transmit power of the system etc. However, when user cooperation is extended to include multiple users or multiple relays, the system suffers from loss in throughput due to increased number of channel use. To overcome this, cooperative communications schemes often make use of network coding which helps trade-off resource allocated for cooperation and system performance. In the first part of the thesis, we propose random network coding based user cooperation scheme in wireless networks. Our scheme is very effective in spreading the information of the pool of cooperating users so that the message can reach the destination via many alternative paths. Also, the proposed scheme is decentralized and the cooperating nodes act independent of the others. Results show that our scheme is resilient to inter-user channel noise and can achieve high diversity gain when number of cooperating users is large. We further enhance the  ii  performance of our scheme for bad user-destination channel by protecting the packets by convolutional coding. This version of our scheme performs better than traditional N user cooperation in terms of both outage and throughput for all userdestination channel conditions when inter-user channel is good. It also shows better robustness to inter-user channel than original scheme. In second part of this thesis, we consider analog network coding based bidirectional relaying system. We develop a scheme to optimally allocate power at the relay nodes such that overall data rate, in transfer of messages between two user nodes is maximized under uncertain channel conditions. We have proposed an iterative solution for rate maximization problem and solve a geometric program at each step. Results show that bidirectional relaying can achieve significantly more data rate than conventional unidirectional relaying scheme at the cost of reduced diversity. Also, addition of more relays makes the system more robust to imperfections in channel.  iii  Preface A version of chapter 3 has been published. K. Kandhway, M. M. Rashid and V. K. Bhargava, “Cooperative Communication in Wireless Uplink Transmissions Using Random Network Coding,” Vehicular Technology Conference Fall (VTC 2010-Fall), 2010 IEEE 72nd , pp.1-5, 6-9 Sept. 2010. I am the primary author and researcher for the above publication. I conducted majority of the tasks including but not limited to identification of the problem, literature review, formulation of problem and developement of novel schemes. I wrote the computer programs, carried out the analysis of the results and prepared the associated manuscript. Dr. Rashid and Prof. Bhargava helped in identification of the problem and, organizing and writing the paper.  iv  Table of Contents Abstract  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  ii  Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  iv  Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  v  List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  xi  Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xii Dedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  1  1.1  Basic Three Node Cooperation . . . . . . . . . . . . . . . . . . .  2  1.2  Scope and Contribution . . . . . . . . . . . . . . . . . . . . . . .  5  1.3  Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . .  6  2 Related Work 2.1  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  7  Network Coding and Cooperative Communication . . . . . . . . .  7  v  2.2  Bidirectional Relaying . . . . . . . . . . . . . . . . . . . . . . .  9  3 Cooperative Communication in Wireless Uplink Transmissions Using Random Network Coding  . . . . . . . . . . . . . . . . . . . . .  11  3.1  Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  11  3.2  System Model and Assumptions . . . . . . . . . . . . . . . . . .  13  3.3  Proposed Scheme . . . . . . . . . . . . . . . . . . . . . . . . . .  13  3.3.1  Encoding . . . . . . . . . . . . . . . . . . . . . . . . . .  14  3.3.2  Decoding . . . . . . . . . . . . . . . . . . . . . . . . . .  17  3.4  Forward Error Correction Through Convolutional Code . . . . . .  18  3.5  Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  18  3.6  Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  30  4 Optimal Resource Allocation for Analog Network Coding Based Bidirectional Relaying  . . . . . . . . . . . . . . . . . . . . . . . . .  31  4.1  Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  31  4.2  Bidirectional Relaying . . . . . . . . . . . . . . . . . . . . . . .  32  4.2.1  System Model . . . . . . . . . . . . . . . . . . . . . . . .  32  4.2.2  Problem Formulation . . . . . . . . . . . . . . . . . . . .  36  4.2.3  Power Allocation . . . . . . . . . . . . . . . . . . . . . .  36  4.3  Unidirectional Relaying . . . . . . . . . . . . . . . . . . . . . . .  41  4.4  Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  45  4.4.1  Comparison of Equal and Optimal Power Allocation . . .  46  4.4.2  Effect of Channel Uncertainty . . . . . . . . . . . . . . .  46  vi  4.4.3  Effect of Noise Variance . . . . . . . . . . . . . . . . . .  54  Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  57  5 Conclusions and Future Work . . . . . . . . . . . . . . . . . . . . .  58  4.5  5.1  Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  58  5.2  Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  59  Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  61  Appendix A Convexity of Problem (4.29)  66  vii  . . . . . . . . . . . . . . . .  List of Figures Figure 1.1  Cooperation through relaying, three node case. . . . . . . . .  3  Figure 1.2  Bidirectional or two way relaying, three node case. . . . . . .  5  Figure 3.1  Flowchart to compute packets, (g p , X p ), 1 ≤ p ≤ 2N, transmitted by the users in the two rounds. Transmission is done following TDMA protocol. 1 ≤ p ≤ N denotes packets transmitted in 1st round and N + 1 ≤ p ≤ 2N denotes packet transmitted in 2nd round. All computations are carried out in the finite field F2s . . . . . . . . . . . . . . . . . . . . . . . . . .  Figure 3.2  Outage performance of the proposed scheme for different values of inter-user signal to noise values . . . . . . . . . . . . .  Figure 3.3  20  Outage performance of different users for the proposed scheme with and without random network coding . . . . . . . . . . .  Figure 3.5  19  Throughput performance of the proposed scheme for different values of inter-user signal to noise values . . . . . . . . . . .  Figure 3.4  15  23  Throughput performance of different users for the proposed scheme with and without random network coding . . . . . . .  viii  24  Figure 3.6  Users with weaker as well as stronger channels are benefited due to network coded cooperation, inter-user channels are 15 db 26  Figure 3.7  Throughput performance of the users, channel of user 1 to destination is fixed at 12 db and inter-user channels are 15 db .  Figure 3.8  Outage performance of the proposed scheme when forward error correction (through convolutional coding) is used. . . . .  Figure 3.9  28  Throughput performance of the proposed scheme when forward error correction (through convolutional coding) is used. .  Figure 4.1  27  29  Rate achieved by the optimal bidirectional and unidirectional relaying schemes compared to equal power allocation for different relay locations . . . . . . . . . . . . . . . . . . . . . .  Figure 4.2  47  BER performance of the optimal bidirectional and unidirectional relaying schemes compared to equal power allocation for different relay locations . . . . . . . . . . . . . . . . . . .  Figure 4.3  48  Rate achieved by optimal bidirectional and unidirectional relaying schemes for different values of channel uncertainties. X-coordinate of relay(s) are fixed at 20 meters. . . . . . . . .  Figure 4.4  49  BER performance of optimal bidirectional and unidirectional relaying schemes for different values of channel uncertainties. X-coordinate of relay(s) are fixed at 20 meters. . . . . . . . .  ix  50  Figure 4.5  Rate achieved by optimal bidirectional and unidirectional relaying schemes for different values of channel uncertainties and different relay locations. . . . . . . . . . . . . . . . . . .  Figure 4.6  52  BER performance of optimal bidirectional and unidirectional relaying schemes for different values of channel uncertainties and different relay locations. . . . . . . . . . . . . . . . . . .  Figure 4.7  53  Rate achieved by optimal bidirectional and unidirectional relaying schemes for different values of noise variances. Xcoordinate of relay(s) are fixed at 50 meters. . . . . . . . . . .  Figure 4.8  55  BER performance of optimal bidirectional and unidirectional relaying schemes for different values of noise variances. Xcoordinate of relay(s) are fixed at 50 meters. . . . . . . . . . .  x  56  Glossary  AWGN Additive white gaussian noise BER  Bit error rate  BPSK  Binary phase shift keying  GP  Geometric program  MIMO  Multiple input multiple output  MRC  Maximum ratio combining  OFDM Orthogonal frequency division multiplexing SNR  Signal to noise ratio  SQP  Sequential quadratic programming  TDMA Time division multiple access  xi  Acknowledgments I thank my supervisor, Professor Vijay K. Bhargava, for his guidance and support. I am grateful to Dr. M. M. Rashid and Mr. S. Mallick for their help during my research. Further I thank the instructors of my courses for helping me understand the basic concepts. I also thank all members of our lab for their friendship and discussions on numerous topics, academic and otherwise. Finally, my deepest thanks go to my family for their constant encouragement and unconditional support through my good and bad times.  xii  Dedication To my family ...  xiii  Chapter 1 Introduction A tremendous increase in mobile phone subscribers has been witnessed in many parts of the world. Customer demand for numerous applications which require high data rate and reliability has fueled a lot of research in this area. The applications like video conferencing, mobile TV, tele medicine and online gaming on hand held devices are few such examples. Wireless channels suffer from various impairments including fading which can create a bottleneck on rate and reliability of transmission. One way to surmount it is to use spacial diversity through Multiple Input Multiple Output (MIMO) systems. However the space and cost limitations in small hand held devices often restrict the use of multiple antennas for transmit or receive diversity. Cooperative and relay based communication is an innovative way to enable spacial diversity in such cases. Users can create spatially distributed virtual antenna array to transmit or receive independent copies of signals in fading environment, thus achieving much needed diversity. Users who  1  partner for cooperation share their resources by transmitting a part or whole of the message transmitted by other users involved in cooperation. Knowledge of relay based communication has been around for a long time. One of the first treatment on the relay channels appeared in [22] and [9]. However, these early studies were limited to relaying in Gaussian channels. Recent studies on relaying and cooperation [20, 24] are motivated by the fading due to multipath nature of the wireless channels. Cooperative system if properly used can increase data rate and decrease the outage of the participating users, which leads to net power savings due to the diversity it offers. Cooperation can also shield mobile users against shadowing, which is an added advantage over MIMO systems.  1.1  Basic Three Node Cooperation  The basic concept of cooperation (through relaying) which takes advantage of broadcast nature of the wireless channel is shown in fig. 1.1. In the first time slot, node 1 transmits the information to the destination. Node 2 which is acting as relay for node 1 will also receive the information and in the next time slot it transmits the same or part of the received information over an independent channel, which leads to diversity in the system. If the cooperation is mutual, nodes 1 and 2 keep changing their roles as active and relay nodes. In some cases, node 2 can be dedicated infrastructure based relay set up by the mobile service provider. Depending on how much processing capability node 2 has (or is willing to expend), different protocols can be followed while relaying. The four major relaying protocols are: Amplify-and-Forward [3], Decode-and-Forward [20], Coded Co2  Figure 1.1: Cooperation through relaying, three node case. operation [17] and Compress-and-Forward [16]. • Amplify-and-Forward: The relay amplifies and retransmits the analog signal it has received in the first time slot from the active user node. The relay need not know the details such as modulation scheme and coding scheme used by the active user node. However, storing and amplifying analog signals is not very easy. • Decode-and-Forward: In this case, the relay demodulates and decodes the signal it has received in the first time slot. Then it forwards the decoded bits 3  to the destination in the second time slot. • Coded Cooperation: In the above two methods the relay repeats the signal they have received from the active user node, while this scheme uses channel coding for cooperation. The relay decodes the message it has received in the first time slot and forwards the parity bits to destination in the next time slot. Cooperative systems using Network Coding may also be included in this category. • Compress-and-Forward: In this technique the relay forwards compressed (often quantized) version of the message it has received from the active user node. The destination has two correlated versions of the same message and hence the concept of (de)coding with side information can be used to estimate the original message. It should be noted that (unidirectional) relaying discussed above leads to loss in spectral efficiency due to the use of additional time slot. To overcome this problem bidirectional or two way relaying was proposed which has its roots in [25]. This scenario is applicable when nodes 1 and 2 (fig. 1.2) have to exchange information in presence of a relay node. In first time slot both the nodes transmit their information simultaneously to the relay. In the next time slot the relay broadcasts the received signal to both of the nodes. Individual nodes can cancel the effect of their own transmitted signal from the signal received from the relay to estimate the message of the other node. Thus we achieve message exchange between two nodes in two time slots, unlike spending two time slots for message transmission 4  Figure 1.2: Bidirectional or two way relaying, three node case. from only one node to the other, attaining higher spectral efficiency in the process. But price to be paid is some loss in spatial diversity relative to unidirectional relaying scheme. To achieve diversity gain in bidirectional relaying scheme we need additional relays, so as to allow the reception of signal from independent paths. If the relay employs amplify and forward strategy, the signal transmitted by the relay in the second time slot is sum total of the signals by both of the nodes. For this reason amplify and forward bidirectional relaying is sometimes said to make use of physical layer network coding.  1.2  Scope and Contribution  • In chapter 3 we consider a network coding based cooperative communication system which falls within the framework of coded cooperation. We 5  propose a novel random network coding based cooperative communication scheme for multi-user scenario and study the outage and throughput performance of the proposed scheme through simulations. To further enhance the performance of the proposed scheme, we allow forward error correction in the network coded packets and study the performance of the improved scheme. • In chapter 4 we consider analog network coding based bidirectional relaying system which can be considered as an amplify-and-forward system. We formulate the problem to maximize rate of data transfer when two user nodes exchange information between each other. We consider the presence of multiple relay nodes and assume imperfect knowledge of channel. Bidirectional relaying is compared with unidirectional amplify-and-forward system under similar assumptions.  1.3  Thesis Organization  Rest of this thesis is organized as follows. Chapter 2 discusses existing literature in the area of network coding and network coding based cooperative communication schemes. Further, work related to amplify-and-forward bidirectional relaying is discussed. In chapter 3 we discuss and analyze the random network coding based cooperative communication scheme. Resource allocation for bidirectional relaying under channel uncertainty is discussed in chapter 4. Finally we draw conclusions and present some possible extensions of this thesis in chapter 5.  6  Chapter 2 Related Work In this chapter we present a survey on the related work. Specifically we focus on network coding based cooperative communications and analog network coding based bidirectional relaying schemes. These areas have attracted lot of interest due to potential benefits they offer.  2.1  Network Coding and Cooperative Communication  Network coding was originally proposed for wired networks [2]. It allows intermediate nodes in the network to linearly combine previously received packets to form a network coded packet. Depending on the network architeture, network coding offers throughput improvement in wired networks apart from robustness against packet loss and delay. An introduction to the concept of linear network coding can be found in [10]. Chou et al. [8] have analyzed the performance of ran-  7  dom network coding on network graphs of commercial internet service providers. Network coding is often blended with cooperative communication protocols due to benefits and flexibility it offers in designing the system. The broadcast nature of wireless channel makes the use of network coding easier. Many authors have studied cooperation schemes aided by network coding. Lai et al. [19] proposed the use of network coded cooperation to reduce transmit powers of mobile units far away from the base station as compared to direct transmission. In addition to decreased transmit power, their system which employed Time Division Multiple Access (TDMA) protocol, achieved reduction in transmission delay from O(N 2 ) to O(N) for N cooperating mobiles. Chen et al. [6] investigated the use of network coding in distributed antenna systems and cooperative communication scenarios. They recommended the use of network coding in cases where long channel codes were not practical. However they suggested that a hybrid system incorporating both network and channel code will further improve the performance of the system. Woldegebreal et al. [26] carried out outage analysis of network coded cooperative communication scheme under noisy inter-user channel and showed that diversity order upto two can be achieved for a group of two cooperating users. Xiao et al. [27] studied a cooperative scheme for three nodes where channel coded version of information generated at each node was combined to form the network coded packet. The destination decodes the data of the cooperating users by iterating between their packets. They showed superior performance achieved by their scheme than when network coding was not used. Haas et al. [13] proposed 8  a “cluster based cooperative coding protocol” applicable in dense wireless sensor networks where link level retransmission of large packets were not allowed. They grouped nodes in the network into cooperating clusters which made use of network coding in their operation. They showed that by choosing clusters of proper size end to end communication between source and destination can be made more reliable.  2.2  Bidirectional Relaying  Three node architecture with bidirectional relaying has been studied by Zhang et al. [29]. The authors assumed that a relay with multiple antennas assisted single antenna sources. They proposed a convex optimization based technique for optimal beamforming and studied the capacity region of their optimal scheme. Koike-Akino et al. [18] pointed out that conventional modulation schemes were not optimal in terms of end-to-end throughput for two way relaying schemes and proposed optimized constellations for that purpose. Zhang et al. [31] devised a power allocation scheme based on mean channel strength for information exchange between two nodes. They maximized the average sum rate of the two users and designed scheme to trade-off outage probability of the participating users. A multi-relay architecture for two way relaying was studied by Nassab et al. [14]. The authors proposed distributed algorithm to compute the beamforming coefficients at each of the relay nodes for two way relaying such that overall transmission power was minimized given some user rate constraints. Zeng et al. in [28] have studied the achievable rate region for such 9  multi-relay networks assuming both channel reciprocity and non-reciprocity. In [30] authors have developed power allocation strategies for multi-relay network when relays transmit at different time slots. Ho et al. [15] addressed power allocation problem for three node amplify-and-forward bidirectional relaying scheme over OFDM link such that the data rate of message exchange between the nodes is maximized. They identified the optimization problem as non convex and solved its dual. To further increase data rate, they proposed tone permutation at the relay node.  10  Chapter 3 Cooperative Communication in Wireless Uplink Transmissions Using Random Network Coding 3.1  Background  Network coding can help extending the user cooperation to multiple users in a convenient way. If N users are cooperating in uplink transmission in a TDMA system, traditional cooperative communication scheme requires a transmission delay of N 2 time slots and allocates (N − 1)/N of the total system resources for cooperation. Network coding can trade off the allocated resources and system performance, reducing the delay required in transmission process. In this chapter, we propose a novel multiuser cooperative communication scheme using random  11  network coding for uplink wireless transmissions. Participating users transmit a linear combination of their new data packet and packets successfully decoded due to preceding transmissions by other users, thus sending new information as well as relaying the information for other users at the same time. The coefficients used for linear combination are selected at random from the finite field used to carry out the network coding. At the base station, original data packets are recovered from the received packets by solving system of linear equations in the finite field. Existing schemes which employ network coding in multi-user cooperative wireless communications have not been able to exploit its full potential – especially, when it comes to making the system robust against inter-user channel noise. This is mainly because deterministic schemes seldom re-encode the network coded packets which make them prone to packet losses due to channel noise. To this end, we propose a cooperative communication scheme that exploits random network coding to spread the information of the pool of cooperating users. This scheme allows the source packets dropped at intermediate nodes to reach the destination through alternative paths thus, achieving better robustness against the effects of noisy inter-user channel. Results from current study show that, even in presence of moderate level of channel noise in inter-user channels, the proposed scheme offers system performance comparable to noiseless inter-user channels. We further improve the network coded cooperation scheme to include forward error correction using convolutional code. This scheme performs very well when channel between users to destination is weak. The schemes presented in this chapter achieve full diversity of N for N cooperating users. 12  3.2  System Model and Assumptions  We consider an uplink transmission scenario where a group of N mobile stations (also termed as users) are cooperating to communicate to the same base station (also termed as destination). Inter-user channels and the user-base station channels are assumed to be Rayleigh flat faded with unit variance. Slow fading scenario is considered where fading coefficient is constant over the transmitted packet. Moreover, fading coefficients are assumed to be perfectly known to the receivers (base station and mobile stations, when they decode signals transmitted by their partners) during packet demodulation and detection. All users are assumed to transmit at different time slots following a TDMA protocol. All the receivers (base station and mobile units as intermediate nodes) are assumed to have single antenna. The proposed scheme falls within the framework of ‘coded’ cooperation [23] where network coding is used.  3.3  Proposed Scheme  When the traditional cooperative scheme is extended to N users in a TDMA system, each of the N users relay information for all other partners once, utilizing N − 1 time slots, (apart from broadcasting its own data in one time slot) thus requiring a delay of N 2 time slots between transmission of new data packets from a particular user. Also, since only one out of the N time slots are used to transmit new data, (N − 1)/N of the total system resources are allocated for cooperation in the traditional cooperative communication system which may not be desirable. The scheme proposed in this chapter can trade off allocated system resources with 13  performance to come up with a cooperation protocol which requires a delay of only 2N between the new transmissions from a user.  3.3.1 Encoding s consecutive bits of packets of length L bits are assumed to be symbols in the finite field F2s for the purpose of network coding [10]. Thus each packet becomes vector of length K = L/s. The steps in the encoding process are shown in the flowchart (fig. 3.1). All the computations were carried out in the finite field F2s . The transmission is divided into two rounds. In the first round of N time slots, each of the users take turn in transmitting a linear combination of their own (new) packet (also termed as information packet) and the packets they have correctly decoded due to transmission of preceding users in this round (packets from preceding users are already network coded). The nth user, 1 ≤ n ≤ N, generates the coefficients, h = (h1 , ..., hn ) (also termed as encoding vector) used for linear combination, randomly from the set F2s − {0}, where each element of the set has equal probability of occurrence. If Mn is the new information packet at this node and {X j , 1 ≤ j < n} are the packets transmitted by preceding users, the nth node computes the network coded packet as Xn = ∑ j=1 h j X j + hn Mn . n−1  (3.1)  It should be noted that if the nth user was unable to successfully decode the packet transmitted from the jth user, h j in h is set to zero to remove the contribution of  14  Figure 3.1: Flowchart to compute packets, (g p , X p ), 1 ≤ p ≤ 2N, transmitted by the users in the two rounds. Transmission is done following TDMA protocol. 1 ≤ p ≤ N denotes packets transmitted in 1st round and N + 1 ≤ p ≤ 2N denotes packet transmitted in 2nd round. All computations are carried out in the finite field F2s  15  the corrupted packet in Xn . For the purpose of decoding network coded packets, it is necessary to send information of how the packets were combined. For ease of decoding it is customary to send the encoding vectors with respect to the original information packets of the source nodes [8]. Denoting the encoding vector with respect to the original information packets at the nth node as gn = (gn1 , ..., gnn ), they can be easily calculated as gni = ∑ j=1 h j gi n−1  gnn = hn .  j  (3.2)  Finally, the nth node transmit the packet (gn , Xn ). Users store the packet transmitted by them for the use in second round. Other users try to decode this transmitted data and if error free packet is received, it is stored, or else it is discarded (and all zero vector is stored instead). In the second round of N time slots, each user transmits a linear combination of all the packets they have correctly decoded in the first round to the base station. Users don’t decode/store the packets transmitted in the second round. The base station decodes and stores the correctly decoded packets in both the rounds. The second round only has added redundancies which are useful in case the channels between users and base station are noisy.  16  3.3.2 Decoding If base station receives the set of packets R = {(g1 , X1 ), (g2 , X2 ), ..., (gP , XP )} then decoding asks for solving the system of linear equations X j = ∑i=1 gi Mi , N  j  (3.3)  where {Mi , 1 ≤ i ≤ N} are the unknowns. Thus we require P ≥ N linearly independent equations to recover N unknowns. Gaussian elimination can be used to solve the system of equations without the need to compute the inverse of the equivalent matrix equation. We carry out all of the computations in the finite field F2s . The scheme is quite robust in the sense that decoding will be successful even though we loose some of the packets due to user-base station channel noise. It should be noted that partial decoding is possible sometimes even if less than N packets are received. For example if the cardinality of R is less than N but it contains one of the packets which is composed of only one of the Mi ’s, then that information packet can be recovered, similarly if R contains two (or more) packets which is composed of only two information packets Mi and M j , then they can be recovered, and so on. Due to the noise in inter-user channel many possibilities for i’s and j’s exist. In other words whenever Gaussian elimination leads to a row with only one element, that information packet can be recovered. Unlike the previous works we have allowed the users to use the partners’ correctly decoded packets in first round of transmission itself. This leads to information spreading to a greater extent because the possibility of data reaching the final  17  destination though alternate paths (i.e. via cooperating users) increases; which in turn improves the robustness of system against inter-user channel noise.  3.4  Forward Error Correction Through Convolutional Code  As we will see in section 3.5, performance of the scheme proposed in this chapter can be improved further when operating at low signal to noise values. In this domain, the packet loss is too high which leads to such a low performance. To protect the packets against impairments of fading in such a situation, we propose using convolutional codes. It has been found that even with this simple coding scheme, we can achieve significant improvement in system performance at low signal to noise ratios (SNRs). At a node, we perform network coding first, this data is then augmented by parity bits generated by convolutional code. While decoding (at other nodes or destination) of the convolutional code viterbi algorithm is used.  3.5  Results  We evaluate the performance of the above network coded cooperative scheme on group of N = 4 cooperating users. Packet size is assumed to be 128 bits and finite field size is 28 (or s = 8). The inter-user channels and channels between the mobiles and the base station are assumed to be Rayleigh flat faded. Fading coefficient is assumed to be constant in the whole packet and independent for different packets. Modulation scheme in the transmission is taken to be Binary Phase Shift Keying (BPSK). It is also assumed that all the receivers are capable of  18  rayleigh channel 2 user, noiseless 4 user nc, 0db 4 user nc, 5db 4 user nc, 10db 4 user nc, 15db 4 user nc, noiseless 4 user, noiseless  0  10  −1  outage probability  10  −2  10  −3  10  −4  10  0  4  8 12 16 20 Eb/No for user to destination channel  24  28  Figure 3.2: Outage performance of the proposed scheme for different values of inter-user signal to noise values detecting the packet errors with certainty. Fig. 3.2 shows outage performance of the scheme proposed in this chapter for varying inter-user channel noise conditions. In the figure, the system outage probability is plotted, which is defined as the ratio between the correctly decoded information packets to the total transmitted information packets for all the N users. 19  0  10  −1  throughput  10  rayleigh channel 2 user, noiseless 4 user nc, 0db 4 user nc, 5db 4 user nc, 10db 4 user nc, 15db 4 user nc, noiseless 4 user, noiseless  −2  10  −3  10  0  4  8 12 16 20 24 Eb/No for user to destination channel  28  Figure 3.3: Throughput performance of the proposed scheme for different values of inter-user signal to noise values  20  In the calculation only the actual information packets generated at the N sources are considered. In the simulation, all the 4 users have same Eb /N0 value for the channel between them and the base station. The scheme is slightly inferior to the traditional four user cooperation scheme (both with noiseless inter-user channels) in terms of outage probabilities. But such a performance is achieved at the cost of more resources with traditional cooperation scheme allocating 3/4th of the total system resource for user cooperation (because each of the users transmit for their 3 partner once). In contrast, the proposed scheme allocates only 1/2 of the total system resource for cooperation. Further, the traditional four user cooperative communication scheme incurs a delay of N 2 = 16 compared to 2N = 8 time slots by the scheme proposed in this chapter. When the inter-user channel is reliable enough, both the traditional and network coded cooperation achieves diversity order of 4 for high signal to noise values of user-destination channel. For different values of the inter-user channel, the scheme proposed in this chapter performs at least as good as the traditional two user cooperative communication scheme. The performance improvement is substantial however for moderate to high signal to noise values of the inter-user channel. More precisely, when the inter-user channel is 15 db or more, the performance achieved is almost as good as the random network coding scheme with noiseless inter-user channel. Thus for the proposed scheme to perform well, searching partners with extremely good interuser channel conditions is not required. Fig. 3.3 shows the throughput performance of the proposed scheme for different conditions of inter-user channels and compares it with Rayleigh channel and 21  traditional two user cooperation (with noiseless inter-user channel). Throughput for the system is defined as the ratio of total number of information packet correctly decoded by the destination to the total number of packets transmitted by all the user nodes in the system. Observations reveal that, at high signal to noise values of the user-destination channel, the system throughout saturates at 0.5 for traditional two user cooperation and proposed scheme in this chapter. This is so because for each new information packet generated at the user nodes, two packet is transmitted by the node. However, for traditional N user cooperation, for each new information packet, N packets are transmitted to the destination hence the system throughput saturates at 1/N = .25 (for N = 4 in our case) for high signal to noise values of user-destination channel. It is clear from fig. 3.2 and fig. 3.3 that for good user-destination channel conditions, traditional N user cooperation has better outage performance at the cost of poor throughput performance. However, when user-destination channel is below 5db, traditional N user cooperation is better than network coded cooperation both in terms of outage and throughput (when both systems have noiseless inter-user channels). Figs. 3.4 displays the outage and fig. 3.5 shows the throughput performance of each of the users involved in network coded cooperation. For the results shown in these figures, the inter-user channel is assumed to be noise free and all the users have equal Eb /N0 value for the channel between them and the base station. We have discussed the possibility of partial decoding when the base station receives less than N = 4 packets from cooperating users. Due to partial decoding, user 1 performs better than user 2, user 2 does better than user 3 and user 3 better 22  0  10  −1  outage probability  10  −2  10  system outage nc user 1,2,3,4 no coop user 1 nc user 2 nc user 3 nc user 4 nc  −3  10  −4  10  0  5 10 15 20 Eb/No for user to destination channel, noiseless inter user channel  Figure 3.4: Outage performance of different users for the proposed scheme with and without random network coding  23  0  10  −1  throughput  10  −2  10  system throughput nc user 1,2,3,4 no coop user 1 nc user 2 nc user 3 nc user 4 nc  −3  10  −4  10  0  5 10 15 20 Eb/No for user to destination channel, noiseless inter user channel  Figure 3.5: Throughput performance of different users for the proposed scheme with and without random network coding  24  than user 4; both in terms of outage and throughput. To explain such a behaviour we can analyze the fraction of total system resources used by the users. User 1 who starts the transmission in the first round will have its packet most probably incorporated in transmission by each of the subsequent users (subject to correct decoding), similarly user 2’s packet is most likely to be present in all but one (first) transmission to the base station, and so on. In second round, however, users get same representation. Thus it can be seen that user 1 utilizes greater portion of the allocated resources than others, then user 2 follows and so on, their performance follow the same trend. Fig. 3.6 shows how the cooperation help share the benefits brought by improved user-destination channel even if some of the participating users are always in shadow region. Figure shows the outage probability of the participating users. Eb /N0 values for all inter-user channels are fixed at 15 db. Also the channel between user 1 and destination has fixed Eb /N0 of 12 db. The link for rest of the three users (2,3 and 4) to the destination are of similar quality. As seen from the figure, the outage of user 1 decreases as the channel quality of its partners (users 2, 3 and 4) improve (even though the channel quality of user 1 is constant). Fig. 3.7 shows the corresponding throughput performance. In figs. 3.8 and 3.9 we analyze the outage and throughput performance of the proposed scheme when forward error correction is used. We have used rate half convolutional code used in Digital Video Broadcasting [1]. The generator polynomials for convolutional code are 171 (Octal) and 133 (Octal). Viterbi algorithm is used for decoding. As seen in the figures, this version of network coded cooper25  0  10  −1  outage probability  10  −2  10  system outage nc user 1 E /N = 12db no coop b  −3  10  o  user 2,3,4 no coop user 1 nc user 2 nc user 3 nc user 4 nc  −4  10  0 5 10 15 20 Eb/No for user to destination channel (user 2,3,4), inter user channel = 15 db  Figure 3.6: Users with weaker as well as stronger channels are benefited due to network coded cooperation, inter-user channels are 15 db  26  0  10  −1  10 throughput  system outage nc user 1 Eb/No = 12db no coop user 2,3,4 no coop user 1 nc user 2 nc user 3 nc user 4 nc  −2  10  −3  10  0 5 10 15 20 Eb/No for user to destination channel (user 2,3,4), inter user channel = 15 db  Figure 3.7: Throughput performance of the users, channel of user 1 to destination is fixed at 12 db and inter-user channels are 15 db  27  rayleigh channel conv rayleigh channel 4 user nc, 7db 4 user conv nc, 7db 4 user nc, 15db 4 user conv nc, 15db 4 user nc, noiseless 4 user conv nc, noiseless 4 user, noiseless  0  10  −1  outage probability  10  −2  10  −3  10  −4  10  0  4  8 12 16 20 Eb/No for user to destination channel  24  28  Figure 3.8: Outage performance of the proposed scheme when forward error correction (through convolutional coding) is used.  28  0  10  −1  throughput  10  rayleigh channel conv rayleigh channel 4 user nc, 7db 4 user conv nc, 7db 4 user nc, 15db 4 user conv nc, 15db 4 user nc, noiseless 4 user conv nc, noiseless 4 user, noiseless  −2  10  −3  10  0  4 8 12 Eb/No for user to destination channel  16  Figure 3.9: Throughput performance of the proposed scheme when forward error correction (through convolutional coding) is used.  29  ation performs much better than the older version and the traditional cooperation in terms of both outage and throughput at low signal to noise values of operation. In high SNR regime, it achieves same throughput performance as traditional cooperation at much better outage.  3.6  Conclusions  In this chapter we proposed a new cooperative communication scheme for multiuser scenario, that exploits random network coding in uplink wireless transmissions. Nodes transmit linear combination of their own data and successfully decoded data from the partners. Our scheme is decentralized, in the sense that each node acts independent of others. The scheme is very robust to inter-user channel noise and achieves almost full diversity (N for N cooperating users) for moderate inter-user channel conditions. For bad user-destination channels, we proposed the use of forward error correction through convolutional codes, to improve throughput and outage performances. Our scheme can be easily modified to design more flexible network coded cooperative communication schemes to tradeoff allocated resources and system performance.  30  Chapter 4 Optimal Resource Allocation for Analog Network Coding Based Bidirectional Relaying 4.1  Background  In conventional (unidirectional) relaying a message is transmitted from the source to the relay in the first time slot and, from the relay to the destination in the second time slot. Thus a total of four time slots are required if two user nodes wish to exchange messages in presence of a single relay node. With the use of network coding based bidirectional relaying message can be exchanged between two user nodes in only two time slots, thus providing the possibility to achieve higher system rate. In the first time slot both the user nodes transmit their message to the  31  relay node(s) on the same physical channel and in the second time slot the relay(s) broadcast the messages to both the user nodes. Similar to one way relaying where the relay can apply stategies like amplify-and-forward and decode-and-forward, in bidirectional relaying the relays can either amplify the signal which they have received in the first time slot or they can try to decode the information received in the first time slot and broadcast it to the user nodes. If amplify-and-forward is used in bidirectional relaying, the setup is very similar to analog network coding. On the other hand if decode-and-forward is used the setup is close to the traditional (digital) network coding. Maximization of overall system rate when two user nodes are involved in information exchange in two time slots and in presence of multiple relays, for analog network coding based bidirectional relaying network is still an open problem in the literature. In this chapter, we develop optimal power allocation strategies for networks employing bidirectional relaying such that the overall system rate is maximized given some power budget. We propose an iterative algorithm which converts the power allocation problem successively to a geometric program, which can be solved efficiently.  4.2  Bidirectional Relaying  4.2.1 System Model This section discusses the system model when two user nodes, N1 and N2 want to exchange information through J assisting relay nodes, R j , j ∈ {1, 2, ..., J}. All 32  the transmitters and receivers are assumed to be single antenna nodes operating in half-duplex manner. We assume all transmissions and receptions are perfectly synchronized. The wireless channel from node x to node y; x, y ∈ {N1 , N2 , R1 , ..., RJ } is denoted by hxy and is modeled as P × N (0, 1), where P = kd −α represents the  path loss (d =distance, α =path loss factor) and N (0, 1) represents zero mean circularly symmetric complex Gaussian random variable with unit variance for flat Rayleigh fading. We consider the general case where channels are non-reciprocal. The receiver is assumed to have imperfect estimate of the channel. The relationship between the estimated channel, hˆ xy and hxy is hxy = hˆ xy + exy .  (4.1)  exy is a complex random variable with zero mean and known variance, σe2xy , representing the uncertainty in the channel from node x to node y. The real and imaginary parts of exy are independent and assumed to have same distribution. The relays employ analog network coding based bidirectional relaying. In the first time slot, both of the user nodes transmit their signal on the same physical channel to all of the relay nodes. The signal transmitted by the user node Ni , i = 1, 2 in the first time slot is tNi =  PNi xi ,  (4.2)  where PNi is the power of the transmitted signal and xi is the signal content of the node Ni (normalized to unit energy). The signal received by the relay node R j , j = 1, 2, ..., J in the first time slot is the superposition of the signals transmitted 33  by both user nodes and is given by  rR j = (hˆ N1 R j + eN1 R j ) PN1 x1 + (hˆ N2 R j + eN2 R j ) PN2 x2 + nR j , j = 1, ..., J. (4.3) Here, nx ∼ N (0, σn2x ) represents the noise at node x; x ∈ {N1 , N2 , R1 , ..., RJ } with variance σn2x . In the second time slot, all of the J relay nodes transmit the scaled version of the signal they have received, to both user nodes simultaneously on the same channel. The signal transmitted by the relay node R j in the second time slot is  tR j =  PR j ηR j rR j ,  (4.4)  where   ηR j =   |hˆ N1 R j |2 PN1 + σe2N  1R j  1 PN1 + |hˆ N2 R j |2 PN2 + σe2N  2R j  PN2 + σn2R  j  1/2   .  (4.5)  The signal received by user node Ni in the second time slot, which is superposition of the signals transmitted by all of the J relay nodes, is given by J  rNi =  ∑ (hˆ R j Ni + eR j Ni )  PR j ηR j rR j + nNi , i = 1, 2.  (4.6)  j=1  After substituting equation (4.3) in (4.6) and removing the self interference term,  34  the received signal at the user node Ni from Nk can be written as rN′ i =  J  ∑ hˆ R N hˆ N R j i  k  J  j  PR j ηR j xk + ∑ hˆ R j Ni eNk R j  PNk  j=1  J  J  + ∑ hˆ R j Ni eNi R j  PR j ηR j xk  PNk  j=1  PR j ηR j xi + ∑ eR j Ni  PNi  j=1  j=1  J  PR j ηR j rR j + ∑ hˆ R j Ni  PR j ηR j nR j + nNi ,  j=1  (4.7)  where k = 2 for i = 1 and k = 1 for i = 2. The signal to noise ratio (SNR) for transmission from user node Nk to Ni is given by  γNk Ni =  ∑Jj=1 hˆ R j Ni hˆ Nk R j ∑Jj=1 |hˆ R j Nk |2 PNk PR j ηR2 j σe2N  kRj  PNk  PR j ηR j  2  + ∑Jj=1 |hˆ R j Nk |2 PNi PR j ηR2 j σe2N R + ∑Jj=1 |hˆ R j Nk |2 PR j ηR2 j σn2R + ∑Jj=1 σe2R i j  j  j Nk  PR j + σn2N  k  (4.8)  where k = 2 for i = 1 and k = 1 for i = 2. As mentioned in [21] the channel measurement noise has worst effect if it is assumed to behave as additive white Gaussian noise (AWGN). Hence, the lower bound to the rate of data transfer from node Nk to Ni can now be written as 1 RNk Ni = log(1 + γNk Ni ), 2  (4.9)  where γNk Ni is defined in (4.8). Assuming BPSK modulation, bit error rate (BER) for the transmission can be calculated as pe = Q( 2 × γNk Ni ), where Q-function is defined as, Q(x) =  ∞ −u2 /2 √1 e du. 2π x  35  (4.10)  .  4.2.2 Problem Formulation The objective is to maximize the overall system rate given the constraint on total power transmitted by users and all of the relays in each time slot, PT . As only the lower bound to the rate of data transfer is available, the optimization problem is lower bounded by the following: minimize PN1 , PN2 , PR j subject to:  RN2 N1 + RN1 N2 PN1 + PN2 ≤ PT ,  (4.11)  ∑Jj=1 PR j ≤ PT , PN1 , PN2 , PR j ≥ 0; j = 1, 2, ..., J.  4.2.3 Power Allocation In the high SNR region, the objective function in problem (4.11) can be written as 1 1 1 1 . R21 + R12 = log{(1 + γ21 )(1 + γ12 )} ≥ log(γ21 γ12 ) = − log 2 2 2 γ21 γ12 (4.12) Since log (.) is a monotonically increasing function, maximization of R21 + R12 is lower bounded by minimization of  1 γ21 γ12 .  36  Hence optimization problem in (4.11)  is lower bounded by, minimize PN1 , PN2 , PR j subject to:  1 1 γ21 . γ12  PN1 + PN2 ≤ PT ,  (4.13)  ∑Jj=1 PR j ≤ PT , PN1 , PN2 , PR j ≥ 0; j = 1, 2, ..., J.  Three Node Network The power allocation optimization problem for the three node network with two user nodes and one relay node can be easily formulated as a geometric program (GP) [7], which can be solved numerically for the three power variables. Power allocation optimization problem for single relay two way relaying systems have been solved previously by dual decomposition of original optimization problem [15]. In [30] it has also been identified as a GP. It is straighforward to see that for single relay case (J = 1),  1 γ21  and  1 γ12  are posynomials, where γ ’s are defined  in (4.8). Problem (4.13) has an objective function which is product of two posynomials (and hence a posynomial) and has posynomial inequality constraints with upper bounds. Thus it is a GP, and can be solved optimally and efficiently by transforming into a convex optimization problem [4]. The optimal powers PN1 , PN2 and PR can be determined numerically by using GP solvers (such as CVX [12]).  37  Multi-relay Network In multi-relay case (J > 1) we fix the user nodes’ powers to make the problem mathematically tractable. The objective function in the optimization problem (4.13) can be approximated by a posynomial. Thus solution can be found by successively approximating the optimization problem as a GP. Let gNk Ni (PR ) and fNk Ni (PR ) denote the denominator and numerator respectively, of γNk Ni defined in (4.8), where PR is a J-tuple containing all the relay nodes’ power variables. Then problem (4.13) can be written as minimize PR subject to:  gN2 N1 (PR ) gN1 N2 (PR ) fN2 N1 (PR ) . fN1 N2 (PR )  ∑Jj=1 PR j  (4.14) ≤ PT ,  PR j ≥ 0; j = 1, 2, ..., J. It can be seen that the objective function in (4.14) is neither a monomial nor a posynomial and hence cannot be formulated as a GP. However the problem can be solved very accurately by local approximation of denominator by monomial which is explained next.  38  Problem (4.14) can be written as, minimize PR  t2 t4 t1 . t 3  subject to: fN2 N1 (PR ) ≥ t1 , fN1 N2 (PR ) ≥ t3 , (4.15)  gN2 N1 (PR ) ≤ t2 , gN1 N2 (PR ) ≤ t4 , t1 ,t2 ,t3 ,t4 > 0, ∑Jj=1 PR j ≤ PT , PR j ≥ 0; j = 1, 2, ..., J.  Due to first and second constraints, problem (4.15) is not a GP. Rest of the constraints and the objective function satisfy the criteria of GP. Therefore, we can convert the problem to a GP by approximating fN2 N1 (PR ) and fN1 N2 (PR ) by cor0  P responding monomials. Details of the procedure can be found in [5]. If fˆN2RN1 (PR )  represents the monomial approximation of fN2 N1 (PR ) around the point PR = P0R , it can be written as J  0  P fˆN2RN1 (PR ) = fN2 N1 (P0R ) ∏  n=1  PRn PR0n  en  ≈ fN2 N1 (PR ),  (4.16)  .  (4.17)  where en =  ∂ fN2 N1 (P0R ) ∂ PRn fN2 N1 (P0R ) PR0n  39  PRn =P0Rn  After some algebraic manipulation  ∂ fN2 N1 (P0R ) ∂ = ∂ PRn ∂ PRn  can be written as, 2  J  ∑ hˆ R j Ni hˆ Nk R j  PNk  PR j ηR j  j=1  ∂ = ∂ PRn =  ∂ fN2 N1 (P0R ) ∂ PRn  PNk ηRn PRn  J  ∑ hˆ R j Ni hˆ Nk R j  PNk  PR j ηR j  ∑  ∑ hˆ R j Ni hˆ Nk R j  PNk  PR j ηR j  j=1  j=1 J  J  PR j ηR j Re(hˆ R j Ni hˆ Nk R j hˆ ∗Rn Ni hˆ ∗Nk Rn ),  j=1  (4.18) where, Re(z) is real part of complex number z and z∗ is complex conjugate of z. 0  P Similarly, monomial approximation fˆN1RN2 (PR ) for fN1 N2 (PR ) can be computed. It  should be noted however, that as we deviate from P0R , the point where approximation was made, the accuracy decreases. Hence we need an iterative approach to 0  0  P P solve problem (4.15) where fˆN2RN1 (PR ) and fˆN1RN2 (PR ) are revised at each iteration.  The algorithm to achieve this is explained in the following.  Step 1: Initialize PR0 j = PT /J, j = 1, 2, ..., J, iter = 1 and obtain itermax , the maximum number of iterations. 0  0  P P Step 2: Find fˆN2RN1 (PR ) and fˆN1RN2 (PR ) following the steps in (4.16) and (4.17).  Step 3: Find optimal PR j , j = 1, 2, ..., J by solving the following geometric pro-  40  ∗  gram minimize PR  t2 t4 t1 . t 3 0  P subject to: fˆN2RN1 (PR ) ≥ t1 , 0  P fˆN1RN2 (PR ) ≥ t3 ,  gN2 N1 (PR ) ≤ t2 ,  (4.19)  gN1 N2 (PR ) ≤ t4 , t1 ,t2 ,t3 ,t4 > 0, ∑Jj=1 PR j ≤ PT , PR j ≥ 0; j = 1, 2, ..., J. Step 4: If  iter = itermax  then goto step 5. else iter = iter + 1, PR0 j = PR j , j = 1, 2, ..., J, goto step 2.  Step 5: Output PR and stop.  4.3  Unidirectional Relaying  Now we discuss conventional unidirectional amplify-and-forward relaying under channel uncertainity. Our objective is to have a unified framework so that we can compare the performance of bidirectional relaying schemes presented in section 41  4.2 with unidirectional relaying. The user node Nk transmits information to the user node Ni (where k = 2 for i = 1 and k = 1 for i = 2) in presence of J assisting relays. As in section 4.2.1 we assume half duplex nodes and perfect synchronization in transmission and reception. In absence of network coding the system is assumed to follow TDMA protocol. The signal transmitted by the user node Nk in first time slot is  uNk =  PNk xk  (4.20)  The signal received by Ni in the first time slot (due to transmission from user node Nk ) is k ˆ vN Ni = (hNk Ni + eNk Ni ) PNk xk + nNi .  (4.21)  The signal received by the relay nodes R j , (1 ≤ j ≤ J) in the first time slot, which is analogous to equation 4.3 is k ˆ vN R j = (hNk R j + eNk R j ) PNk xk + nR j .  (4.22)  In J subsequent time slots, 2nd to (J + 1)th , all the relay nodes transmit one by one to the destination. Similar to equation 4.4, signal transmitted by the relay node R j in the ( j + 1)th time slot is uR j = δR j  PRNjk Ni vR j ,  42  (4.23)  where PRNjk Ni represent power transmitted by relay node R j during information transmission from node Nk to Ni and,   δR j =   1/2  1  |hˆ Nk R j |2 PNk + σe2N R PNk + σn2R k j  j  .  (4.24)  The signal received at destination Ni due to transmission of the relay R j in the ( j + 1)th time slot can be written as R vNij = (hˆ R j Ni + eR j Ni ) PRNjk Ni δR j vR j + nNi  = hˆ R j Ni hˆ Nk R j hˆ R j Ni  PNk  PRNjk Ni δR j xk + hˆ R j Ni eNk R j  PRNjk Ni δR j nR j + eR j Ni  PRNjk Ni δR j xk +  PNk  (4.25)  PRNjk Ni δR j vR j + nNi  Assuming maximum ratio combining (MRC) at the destination, SNR at the receiver node Ni (corresponding to equation 4.8) is given by βNk Ni  J |hˆ N N |2 PNk = 2 k i + ∑ 2 2 ˆ σeN N PNk + σn2N j=1 |hR j Ni | σe k i  i  |hˆ R j Ni |2 |hˆ Nk R j |2 PNk PR jk i δR2 j N N  Nk R j  N N N N PNk PR jk i δR2 j + |hˆ R j Ni |2 σn2R PR jk i δR2 j + σe2R j  PR jk i + σn2N 2 (4.26) N N  j Ni  Similar to section 4.2.1 we assume channel measurement noise to behave as AWGN to find lower bound to the rate of data transfer from node Nk to Ni as  RNk Ni =  1 log(1 + βNk Ni ), J +1  (4.27)  To maximize the rate of data transfer in the information exchange between two  43  .  user nodes, the problem can be written as maximize PN1 , PN2 , PRNj2 N1 , PRNj1 N2 subject to:  1 2 (RN2 N1 + RN1 N2 )  PN1 + PN2 ≤ PT , N N1  ∑Jj=1 PR j2  (4.28)  + ∑Jj=1 PRNj1 N2 ≤ PT ; j = 1, 2, ..., J,  PN1 , PN2 , PRNj2 N1 , PRNj1 N2 ≥ 0; j = 1, 2, ..., J. where RN2 N1 , RN1 N2 are defined in (4.27), PT is the power budget and PRNj2 N1 , PRNj1 N2 are the power transmitted by relay nodes during the transmission from user node N2 to N1 and N1 to N2 respectively. First and second constraints in problem (4.28) are selected such that total energy spent per packet in transmission is same as in bidirectional relaying case in section (4.2.2). This is done to insure fair comparision of the performances of the two schemes. Power is a non negative quantity and hence the last constraint. The rate of information transfer is halved if we consider one round of information exchange between the nodes because a total of 2(J + 1) time slots are used by the nodes, in first J + 1 slots data is transfered from N2 to N1 during which the transmission from N1 to N2 is idle and in next J + 1 time slots the opposite happens. To solve the unidirectinal relaying power optimization problem following approch is taken. Problem (4.28) is not a convex optimization problem as the objective function is non convex function. To make the problem mathematically  44  tractable, we fix PN1 and PN2 , and the resulting problem is, maximize PRNj2 N1 , PRNj1 N2 subject to:  1 2 (RN2 N1 + RN1 N2 ) N N N N ∑Jj=1 PR j2 1 + ∑Jj=1 PR j1 2  (4.29) ≤ PT ; j = 1, 2, ..., J,  PRNj2 N1 , PRNj1 N2 ≥ 0; j = 1, 2, ..., J. It can be shown that problem (4.29) is a convex optimization problem (see Appendix A). Once the convexity of the problem has been established, it can be solved for the power variables numerically, using various well established algorithms such as Gradient Descent Method, Interior Point Method or Sequential Quadratic Programming (SQP) [4]. Here we have used SQP due to fast convergence and robust performance.  4.4  Results  In the simulation the user nodes are fixed at coordinates (0, 0) and (100, 0) meters. The channel between any two nodes x, y ∈ {N1 , N2 , R1 , ..., RJ } is modeled as, hxy = kd −α × N (0, 1) which is Rayleigh flat faded. d is the distance between the nodes, constant k = 1000 and path loss factor α = 4 is chosen. We use a maximum of three relays R1 , R2 and R3 located respctively at (x, 10), (x, 20) and (x, −20) where the x-coordinate, x lie between 0 and 100 metres. The results are shown for J = 1, 3. When one relay is employed we use R1 , and when three relays are employed we use all of R1 , R2 and R3 . The power budget is fixed at PT = 10 45  mW. We have plotted system rate and system BER which is defined as rate and BER averaged over transmissions in both directions and over different channel realizations.  4.4.1 Comparison of Equal and Optimal Power Allocation In figs. 4.1 and 4.2, for varying relay locations, we compare the rate and BER performances of the optimal power allocation scheme proposed for multi-relay bidirectional relaying with equal power allocation at the relay node(s). We assume noise variances at all of the user and relay nodes as σn2x = 10−12 . Further, for these results all channel uncertainties are assumed to be zero, i.e. σe2xy = 0. The figures also show the results of unidirectional relaying. Figs. 4.1 and 4.2 show that the proposed power allocation scheme performs better in terms of rate and much better in terms of BER than equal power allocation at the relays. Although bidirectional relaying scheme beats unidirectional relaying in terms of data rate (for same number of relays), the BER performance of unidirectional relaying scheme is much better than bidirectional relaying scheme. It should be noted that there is only a single graph for optimal and equal power allocation for single relay unidirectional relaying because they give the same solution, which is using whole power budget PT at the only relay.  4.4.2 Effect of Channel Uncertainty In figs. 4.3 and 4.4 we show the rate and BER performances of the optimal bidirectional and unidirectional relaying schemes with varying uncertainity, for number  46  rate nc 1 relay rate nc 3 relays rate nc 1 relay equal pow rate nc 3 relays equal pow rate uni 1 relay rate uni 3 relay rate uni 3 relay equal pow  6 5.5 5  system rate  4.5 4 3.5 3 2.5 2 1.5 1 25  30  35  40  45 50 55 60 x−coordinate of relay(s)  65  70  75  Figure 4.1: Rate achieved by the optimal bidirectional and unidirectional relaying schemes compared to equal power allocation for different relay locations  47  −1  10  −2  10  −3  system BER  10  −4  10  ber nc 1 relay ber nc 3 relays ber nc 1 relay equal pow ber nc 3 relays equal pow ber uni 1 relay ber uni 3 relays ber uni 3 relays equal pow  −5  10  −6  10  −7  10  25  30  35  40  45 50 55 60 x−coordinate of relay(s)  65  70  75  Figure 4.2: BER performance of the optimal bidirectional and unidirectional relaying schemes compared to equal power allocation for different relay locations  48  3  system rate  2.5  2  rate nc 1 relay rate nc 3 relays rate uni 1 relay rate uni 3 relays  1.5  1  0.5 0 10  1  2  10  10 2  σh  3  10  2  NN  /σe decreasing uncertainty →  1 2  xy  Figure 4.3: Rate achieved by optimal bidirectional and unidirectional relaying schemes for different values of channel uncertainties. Xcoordinate of relay(s) are fixed at 20 meters.  49  4  10  −1  10  −2  system BER  10  −3  10  ber nc 1 relay ber nc 3 relays ber uni 1 relay ber uni 3 relays −4  10  0  10  1  2  10  10 2  σh  3  10  2  NN  /σe decreasing uncertainty →  1 2  xy  Figure 4.4: BER performance of optimal bidirectional and unidirectional relaying schemes for different values of channel uncertainties. Xcoordinate of relay(s) are fixed at 20 meters.  50  4  10  of relays J = 1, 3. Variance of uncertainty in all the channels are assumed to be the same. In both the figures x-axis represents σh2N  1 N2  /σe2xy , where σh2N  1 N2  is the  variance for channel between nodes N1 and N2 , and σe2xy is the channel uncertainty variance for all the channels. We compare the system rates when σh2N  1 N2  /σe2xy = 2  and 104 , i.e. channel uncertainties are at two extremes. We adopt relative decrease in rate as the criteria to evaluate the schemes. When number of relays are one and three, the decrease in system rate is 23% and 20% for bidirectional relaying scheme. These numbers are 24% and 18% respectively in case of unidirectional relaying. Clearly in both the cases adding more relays makes the system more robust to channel uncertainty (cost to be paid is incresed system complexity). Also for the case of multiple relays, unidirectional relaying is slightly more robust than bidirectional relaying. From the BER plot of fig. 4.4 it can be concluded that unidirectional relaying is more robust to channel uncertainty than bidirectional relaying (cost involved is reduced absolute system throughput). In figs. 4.5 and 4.6 we study the rate and BER performance of bidirectional and unidirectional relaying schemes with uncertain channels (such that σh2N  1 N2  /σe2xy =  10, uncertainties in all the channels are same). Noise variance at all the nodes is fixed such that σn2x = 10−12 . It can be seen from fig. 4.5 that for a given relay location and value of J, absolute decrease in system rate is less in case of unidirectional relaying than bidirectional relaying. Simple calculation show that same is true even for relative decrease in system rate. Addition of relays in cases of both bidirectional and unidirectional relaying reduces the relative decrease in rate which asserts the conclusion drawn from fig. 4.3 that more relays leads to better 51  rate nc 1 relay rate nc 1 relay uncert rate nc 3 relays rate nc 3 relays uncert rate uni 1 relay rate uni 1 relay uncert rate uni 3 relay rate uni 3 relay uncert  6 5.5 5  system rate  4.5 4 3.5 3 2.5 2 1.5 1 25  30  35  40  45 50 55 60 x−coordinate of relay(s)  65  70  75  Figure 4.5: Rate achieved by optimal bidirectional and unidirectional relaying schemes for different values of channel uncertainties and different relay locations.  52  −1  10  −2  10  −3  system BER  10  −4  10  ber nc 1 relay ber nc 1 relay uncert ber nc 3 relays ber nc 3 relays uncert ber uni 1 relay ber uni 1 relay uncert ber uni 3 relay ber uni 3 relay uncert  −5  10  −6  10  −7  10  25  30  35  40  45 50 55 60 x−coordinate of relay(s)  65  70  75  Figure 4.6: BER performance of optimal bidirectional and unidirectional relaying schemes for different values of channel uncertainties and different relay locations.  53  robustness to channel uncertainty. Finally, the figures show that relay(s) placed mid-way between the two nodes leads to best performance in terms of BER and rate. Such a position mitigates the path loss to the best extent possible.  4.4.3 Effect of Noise Variance Figs. 4.7 and 4.8 show the rate and BER performance of the bidirectional and unidirectional relaying schemes for varying channel noise conditions. For the simulation, relay(s) are fixed such that their x-coordinates are 50 meters. The xaxis in figures represent σh2N  1 N2  /σn2x . The noise variance at all of the nodes, σn2x are  considered to be the same. For the results here, the channel uncertainty variances for all channels are set to zero. As seen in fig. 4.7 bidirectional relaying clearly beats unidirectional relaying in terms of system rate but the opposite is true if we compare them in terms of BER (fig. 4.8). Additional relays in bidirectional scheme leads to further increase in rate and increases diversity achieved by the system too. However, in the case of unidirectional relaying, although diversity increases with addition of relays, the system rate decreases due to increased channel use. The order of diversity achieved by unidirectional scheme is always greater than that achieved by bidirectional scheme with same number of relays due to exsistance of the direct path in unidirectional scheme (additional path leads to more spatial diversity). Due to half duplex nature of the nodes, direct path is absent in the bidirectional relaying method (since both user nodes transmit simultaneously in first time slot).  54  12 rate nc 1 relay rate nc 3 relays rate uni 1 relay rate uni 3 relay  10  system rate  8  6  4  2  0  0  5  10  15  2 σh  NN  2 /σn  1 2  20  25  30  35  40  in dB, increasing SNR →  x  Figure 4.7: Rate achieved by optimal bidirectional and unidirectional relaying schemes for different values of noise variances. X-coordinate of relay(s) are fixed at 50 meters.  55  0  10  ber nc 1 relay ber nc 3 relays ber uni 1 relay ber uni 3 relays  −1  system BER  10  −2  10  −3  10  −4  10  −5  10  0  5  10  15  2 σh  NN  2 /σn  1 2  20  25  30  35  40  in dB, increasing SNR →  x  Figure 4.8: BER performance of optimal bidirectional and unidirectional relaying schemes for different values of noise variances. X-coordinate of relay(s) are fixed at 50 meters.  56  4.5  Conclusions  In this chapter we have proposed an optimal power allocation scheme for analog network coding based multi-relay bidirectional relaying system in which the relays assist two user nodes in message exchange. The relays employ amplifyand-forward strategy on the received signal. Our objective was to maximize the overall rate of data transfer between the users nodes given some power budget. We also assume imperfect knowledge of channel at user and relay nodes. The problem can be formulated as a geometric program which can be solved efficiently. The results show that bidirectional relaying systems can achieve substantially high data rate than conventional unidirectional amplify-and-forward systems at the cost of reduced diversity. Further, addition of relays make the system robust against channel imperfections but the price to be paid is increased system complexity.  57  Chapter 5 Conclusions and Future Work 5.1  Conclusions  In this thesis we considered network coding based cooperative communications schemes. Broadcast property of wireless networks make them ideal for application of network coding. Whether digital or analog, network coding enhances throughput of the network and reduces delay in successive transmissions by user nodes. In first part of this thesis we proposed a random network coding based multiuser cooperative communication scheme in which the cooperating nodes transmit linear combination of their new data packet and the packets successfully decoded due to transmissions by other partners. Each node acts independent of others in selecting the coefficient used for linear combination. The proposed scheme achieves high diversity gain and has better throughput performance than tradi-  58  tional N user cooperation when channel between users and destination is good (at the cost of increased outage). To improve the performance of the scheme for bad user-destination channel we used convolutional coding based forward error correction. The enhanced scheme not only shows better robustness to inter-user channel noise but also has better outage and throughput performance than traditional N user cooperation. We further investigated analog network coding based bidirectional relaying system and developed optimal power allocation scheme to maximize the rate of data transfer between two user nodes which are assisted by multiple relays. We assume imperfect knowledge of channel while allocating the power. The results show that bidirectional relaying achieves significantly more data rate than unidirectional relaying. However, unidirectional relaying is more robust to channel noise and achieves better diversity gain. Also, addition of more relays makes the system more robust to channel uncertainties in case of both bidirectional and unidirectional relaying. In case of multiple relays, unidirectional scheme is more robust to channel imperfections than bidirectional relaying.  5.2  Future Work  The work presented in this thesis can be extended in the following directions • In chapter 3 there is a possibility to develop joint network coding, channel coding multi-user cooperative communications scheme. For three node scenario, such a technique was developed by Xiao et al. [27].  59  • In the bidirectional relaying system considered in chapter 4 OFDM can be incorporated. Then power should be distributed optimally among the subcarriers. • Recently some work has been done on channel estimation for three node bidirectional relaying network [11]. Authors note that resources expended in channel estimation leads to reduction in capacity of such networks. Developing low complexity channel estimation algorithms for multiple relay network and analyzing data rate reduction compared to unidirectional relaying may be interesting extensions. • It will also be interesting to analyze how the performance of bidirectional relaying schemes will be affected if the transmission and reception by the user and relay nodes are not perfectly synchronized. The assumption of perfectly synchronous transmission and reception may not be true in practical scenario due to different geographical locations of nodes and finite speed of electromagnetic waves.  60  Bibliography [1] Framing structure, channel coding and modulation for digital terrestrial television. DVB Document A012, June 1996. → pages 25 [2] R. Ahlswede, N. Cai, S. Y. R. Li, and R. W. Yeung. Network information flow. IEEE Trans. on Info. Theory, 46:1204–16, July 2000. → pages 7 [3] S. Berger, M. Kuhn, A. Wittneben, T. Unger, and A. Klein. Recent advances in amplify-and-forward two-hop relaying. IEEE Communications Magazine, 47(7):50 –56, July 2009. → pages 2 [4] S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge Univ. Press, 2004. → pages 37, 45, 67 [5] S. Boyd, S. Kim, L. Vandenberghe, and A. Hassibi. A tutorial on geometric programming. Optimization and Engineering, 8:67–127, 2007. → pages 39 [6] Y. Chen, S. Kishore, and J. Li. Wireless diversity through network coding. In IEEE Wireless Communications and Networking Conference, 2006, volume 3, pages 1681–86, April 2006. → pages 8 61  [7] M. Chiang. Geometric programming for communication systems. Foundations and Trends in Communications and Information Theory, 2 (1-2):1–154, July 2005. → pages 37 [8] P. Chou, Y. Wu, and K. Jain. Practical network coding. In Allerton Conference on Communication, Control, and Computing, Oct. 2003. → pages 7, 16 [9] T. Cover and A. Gamal. Capacity theorems for the relay channel. IEEE Trans. on Info. Theory, 25(5):572 – 584, Sep. 1979. → pages 2 [10] C. Fragouli, J. Le Boudec, and J. Widmer. Network coding: an instant primer. SIGCOMM Comput. Commun. Rev., 36:63–68, Jan. 2006. → pages 7, 14 [11] H. Gacanin, T. Sjodin, and F. Adachi. On channel estimation for bi-directional analog network coding in a frequency-selective fading channel. EURASIP Journal on Wireless Communications and Networking, Jan. 2011. → pages 60 [12] M. Grant and S. Boyd. CVX: Matlab software for disciplined convex programming, version 1.21. http://cvxr.com/cvx, Oct 2010. → pages 37 [13] Z. J. Haas and T.-C. Chen. Cluster-based cooperative communication with network coding in wireless networks. In Military Communications Conference (Milcom), pages 2082 –2089, Nov. 2010. → pages 8  62  [14] V. Havary-Nassab, S. Shahbazpanahi, and A. Grami. Optimal distributed beamforming for two-way relay networks. IEEE Trans. on Signal Processing, 58(3):1238–1250, March 2010. → pages 9 [15] C. K. Ho, R. Zhang, and Y.-C. Liang. Two-way relaying over ofdm: Optimized tone permutation and power allocation. In IEEE International Conference on Communications, pages 3908 –3912, May 2008. → pages 10, 37 [16] R. Hu and J. Li. Exploiting slepian-wolf codes in wireless user cooperation. In IEEE 6th Workshop on Signal Processing Advances in Wireless Communications, pages 275 – 279, June 2005. → pages 3 [17] T. Hunter and A. Nosratinia. Diversity through coded cooperation. IEEE Tran. on Wireless Commun., 5(2):283 – 289, Feb. 2006. → pages 3 [18] T. Koike-Akino, P. Popovski, and V. Tarokh. Optimized constellations for two-way wireless relaying with physical network coding. IEEE Journal on Selected Areas in Commun., 27(5):773–787, June 2009. → pages 9 [19] H. Q. Lai, A. S. Ibrahim, and K. Liu. Location-aware cooperative communications utilizing linear network coding. In IEEE Global Telecommunications Conference, 2008, pages 1–5, Nov. 2008. → pages 8 [20] J. N. Laneman, D. N. C. Tse, and G. W. Wornell. Cooperative diversity in wireless network: Efficient protocols and outage behavior. IEEE Trans. Info. Theory, 50(12):3062–80, Dec. 2004. → pages 2 63  [21] M. Medard. The effect upon channel capacity in wireless communications of perfect and imperfect knowledge of the channel. IEEE Trans. on Info. Theory, 46(3):933 –946, May 2000. → pages 35 [22] E. C. V. D. Meulen. Three-terminal communication channels. Advances in Applied Probability, 3(1):120–154, Spring 1971. → pages 2 [23] A. Nosratinia, T. E. Hunter, and A. Hedayat. Cooperative communication in wireless networks. IEEE Communications Magazine, 42(10):74–80, Oct. 2004. → pages 13 [24] A. Sendonaris, E. Erkip, and B. Aazhang. User cooperation diversity part i and part ii. IEEE Trans. Commun., 51(11):1927–48, Nov. 2003. → pages 2 [25] C. E. Shannon. Two-way communication channels. In Proc. Fourth Berkeley Symp. Math. Satist. Probab., volume 1, pages 611–644, 1961. → pages 4 [26] D. Woldegebreal and H. Karl. Network-coding-based adaptive decode and forward cooperative transmission in wireless networks: Outage analysis. In 13th European Wireless Conference, April 2007. → pages 8 [27] L. Xiao, T. Fuja, J. Kliewer, and D. Costello. A network coding approach to cooperative diversity. IEEE Trans. on Info. Theory, 53(10):3714–22, Oct. 2007. → pages 8, 59 [28] M. Zeng, R. Zhang, and S. Cui. Achievable rate region of distributed 64  beamforming for two-way relay networks. In Asilomar Conference on Signals, Systems, and Computers, Nov. 2010. → pages 9 [29] R. Zhang, Y. C. Liang, C. C. Chai, and S. Cui. Optimal beamforming for two-way multi-antenna relay channel with analogue network coding. IEEE Journal on Selected Areas in Commun., 27(5):699–712, June 2009. → pages 9 [30] X. J. Zhang and Y. Gong. Adaptive power allocation in two-way amplify-and-forward relay networks. In IEEE International Conference on Communications, pages 1 –5, June 2009. → pages 10, 37 [31] Y. Zhang, Y. Ma, and R. Tafazolli. Power allocation for bidirectional af relaying over rayleigh fading channels. IEEE Commun. Letters, 14(2): 145–147, Feb. 2010. → pages 9  65  Appendix A Convexity of Problem (4.29) It is easy to verify that contraints of the problem form a convex set. If we show that the objective function is a concave function, then maximization of a concave function within a convex feasible region is a convex optimization problem. In problem (4.29) we have fixed PN1 = PN2 = PT /2; the concavity of objective function in problem (4.29) can be established in the following steps. • Equation (4.26) can be written as J  βNk Ni = a + ∑ f j (PRNjk Ni ), j=1  66  (A.1)  where, b j PRNjk Ni  f j (PRNjk Ni ) = a=  c j PRNjk Ni + d  ,  |hˆ Nk Ni |2 PNk , σe2N N PNk + σn2N k i  i  (A.2)  b j = |hˆ R j Ni |2 |hˆ Nk R j |2 PNk , c j = |hˆ R j Ni |2 σe2N R PNk δR2 j + |hˆ R j Ni |2 σn2R δR2 j + σe2R N , k j  j  j i  d = σn2N . 2  Now, all the constants a, b j , c j , d > 0 hence,  ∂ ∂ PRNjk Ni  f j (PRNjk Ni ) =  db j (c j PRNjk Ni + d)2  > 0 ∀PRNjk Ni > 0,  (A.3)  < 0 ∀PRNjk Ni > 0.  (A.4)  and  ∂2  f j (PRNjk Ni ) = Nk Ni 2 ∂ PR j  −2db j c j  (c j PRNjk Ni + d)3  From (A.3) and (A.4) it is clear that f j (PRNjk Ni ) is a concave increasing function. Sum of concave functions is a concave function, thus βNk Ni defined in (A.1) is a concave function. • The composition rule in [4] (page 84) states that a function f = h(g(.)) is concave if h(.) is concave and non-decreasing in concerned domain and g(.) is concave. Since, log (.) is concave and nondecreasing function for all positive arguments; and (1 + βNk Ni ) is concave taking only positive values, 67  we can invoke the above composition rule to ascertain that RNk Ni =  1 J+1 log(1 + βNk Ni )  defined in (4.27) is a concave function.  • It is easy to see that the objective function in problem (4.29), being sum of two concave functions RN2 N1 and RN1 N2 , is a concave function. Problem (4.29) requires maximization of a concave function over a convex set formed by intersection of linear inequalities and hence is a convex optimization problem.  68  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0071609/manifest

Comment

Related Items