ISTANBUL TECHNICAL UNIVERSITYF GRADUATE SCHOOL OF SCIENCE ENGINEERING AND TECHNOLOGY RELAYING OPPORTUNITIES FOR WIRELESS NETWORKS BY APPLYING NETWORK CODING Ph.D. THESIS Semiha TEDI˙K BAS¸ARAN Department of Electronics and Communications Engineering Telecommunications Engineering Programme APRIL 2019 ISTANBUL TECHNICAL UNIVERSITYF GRADUATE SCHOOL OF SCIENCE ENGINEERING AND TECHNOLOGY RELAYING OPPORTUNITIES FOR WIRELESS NETWORKS BY APPLYING NETWORK CODING Ph.D. THESIS Semiha TEDI˙K BAS¸ARAN (504132305) Department of Electronics and Communications Engineering Telecommunications Engineering Programme Thesis Advisor: Prof. Dr. Günes¸ Zeynep KARABULUT KURT APRIL 2019 I˙STANBUL TEKNI˙K ÜNI˙VERSI˙TESI˙F FEN BI˙LI˙MLERI˙ ENSTI˙TÜSÜ KABLOSUZ AG˘LAR I˙ÇI˙N AG˘ KODLAMALI AKTARMA FIRSATLARI DOKTORA TEZI˙ Semiha TEDI˙K BAS¸ARAN (504132305) Elektronik ve Haberles¸me Mühendislig˘i Anabilim Dalı Telekomünikasyon Mühendislig˘i Programı Tez Danıs¸manı: Prof. Dr. Günes¸ Zeynep KARABULUT KURT NI˙SAN 2019 Semiha TEDI˙K BAS¸ARAN, a Ph.D. student of ITU Graduate School of Science En- gineering and Technology 504132305 successfully defended the thesis entitled “RE- LAYING OPPORTUNITIES FOR WIRELESS NETWORKS BY APPLYING NET- WORK CODING”, which he/she prepared after fulfilling the requirements specified in the associated legislations, before the jury whose signatures are below. Thesis Advisor : Prof. Dr. Günes¸ Zeynep KARABULUT KURT .............................. Istanbul Technical University Jury Members : Prof. Dr. I˙brahim ALTUNBAS¸ .............................. Istanbul Technical University Assoc. Prof. Dr. Enver ÖZDEMI˙R .............................. Istanbul Technical University Assoc. Prof. Dr. Ali Emre PUSANE .............................. Bog˘aziçi University Assoc. Prof. Dr. Serhat ERKÜÇÜK .............................. Kadir Has University Date of Submission : 11 March 2019 Date of Defense : 19 April 2019 v vi To my family, vii viii FOREWORD First of all, I would like to express my sincere gratitude to my advisor Professor Günes¸ Karabulut Kurt for believing my abilities to accomplish this research work. I am kindly grateful for her permanent support, result-oriented perspective, availability, constructive suggestions, and scientific guidance that have played key roles to succeed the works investigated in this thesis. I would also like to thank Prof. Frank Kschishang for his valuable contributions and suggestions to the last part of the thesis. I would like to acknowledge The Scientific and Technological Research Council of Turkey (TUBITAK) for financial support in the project named "Random Network Coding and Designs over GF(q)" under grant no. 113E294 conducted between October 2013 and October 2016. I also acknowledge TUBITAK for financial support based on the Ph.D. Priority Areas Fellowship Program 2211/C since March 2017. I would also like to thank Istanbul Technical University BAP Coordination Unit for financial support. I would like to thank the members of the thesis steering committee, Professor I˙brahim Altunbas¸ and Professor Ali Emre Pusane, for their instructive and valuable contributions during the progression of the dissertation. I specially thank Professor I˙brahim Altunbas¸ for his guidance and constructive comments during my graduate education. I am also very grateful to assist his undergraduate courses which helps to improve my instructor capability. I would like to thank Dr. Özge Cepheli for her friendship and support at the beginning of my graduate education. I would also like to thank my colleagues from ITU Wireless Communication Research Laboratory for their friendship. Finally, I would like to present my special thanks to my parents and sisters for their love, encouragement, and endless support throughout my life. I also appreciate all the support and care of my mom. The major role is of my spouse, Mehmet Bas¸aran, to be extremely supportive of me throughout the thesis process and he has made countless sacrifices to finish this study. April 2019 Semiha TEDI˙K BAS¸ARAN (Telecommunications Engineer) ix x TABLE OF CONTENTS Page 1. INTRODUCTION .............................................................................................. 1 1.1 Background and Motivation ........................................................................... 1 1.2 Literature Overview........................................................................................ 2 1.2.1 Network coding ...................................................................................... 2 1.2.2 Random network coded cooperation ...................................................... 3 1.2.3 Topology awareness in network coding ................................................. 4 1.2.4 Multi-access schemes for network coded cooperation systems ............. 5 1.2.5 Wireless network reliability analysis...................................................... 6 1.3 Organization and Contributions of the Thesis ................................................ 7 2. NETWORK CODED COOPERATION........................................................... 11 2.1 Linear Network Coding.................................................................................. 12 2.1.1 Analog network coding .......................................................................... 15 2.1.2 Random linear network coding .............................................................. 16 2.1.3 Rateless codes in network coding........................................................... 17 2.2 Cooperative Communication Aspect of Network Coded Cooperation .......... 18 2.3 Conventional Network Coded Cooperation.................................................... 20 2.4 Summary and Discussion ............................................................................... 21 3. DECODING FAILURE PROBABILITY ANALYSIS OF RANDOM NETWORK CODED COOPERATION SYSTEMS ........................................... 23 3.1 RNCC Signaling Model ................................................................................. 23 3.1.1 Network model ....................................................................................... 26 3.2 Decoding Failure Probability Analysis of RNCC .......................................... 27 3.2.1 Individual link outages ........................................................................... 27 3.2.2 Calculation of conditional successful decoding probability................... 29 3.2.3 Counting full rank and rank deficient matrices ...................................... 30 3.2.4 Relay operations ..................................................................................... 35 3.3 Numerical Results ......................................................................................... 36 3.3.1 Practical implementation results............................................................. 41 3.4 Summary and Discussion ............................................................................... 45 xi FOREWORD........................................................................................................... ix TABLE OF CONTENTS........................................................................................ xi ABBREVIATIONS ................................................................................................. xiii SYMBOLS............................................................................................................... xv LIST OF TABLES ..................................................................................................xvii LIST OF FIGURES ................................................................................................ xix SUMMARY ............................................................................................................. xxi ÖZET ....................................................................................................................... xxv 4. WIRELESS CHANNEL INDUCED CODING ............................................... 47 4.1 System Model................................................................................................. 47 4.1.1 Conversion of the tripartite network graph to the effective bipartite network graph......................................................................................... 48 4.2 Wireless Channel Induced Coding Solution................................................... 51 4.3 Numerical Results .......................................................................................... 52 4.4 Summary and Discussion ............................................................................... 55 5. NCC-OFDMA SYSTEM.................................................................................... 57 5.1 Joint Subcarrier and Power Allocation in OFDMA Systems for Outage Minimization ................................................................................................. 58 5.1.1 Joint optimization approaches ................................................................ 58 5.1.2 The proposed algorithms ........................................................................ 60 5.1.3 Numerical results.................................................................................... 62 5.2 Single Relay Selection Scheme for NCC-OFDMA System........................... 66 5.2.1 OFDMA extension of network coded cooperation................................. 66 5.2.2 Decoding failure probability analysis of NCC-OFDMA-SRS .............. 69 5.2.3 Min-max single relay selection rule ...................................................... 69 5.2.4 Decoding failure probability analysis of NCC-OFDMA-SRS............... 70 5.2.5 Numerical results.................................................................................... 72 5.3 Summary and Discussion ............................................................................... 74 6. WIRELESS NETWORK RELIABILITY ANALYSIS FOR ARBITRARY NETWORK TOPOLOGIES.................................................................................. 75 6.1 Outage Polynomials of Wireless Networks.................................................... 76 6.1.1 Network outage polynomial calculation based on path enumeration..... 78 6.1.2 Network outage polynomial calculation based on cut-set enumeration . 78 6.1.3 Network outage polynomial calculation based on two-terminal polynomial .............................................................................................. 79 6.1.4 Bounds on the outage polynomial .......................................................... 80 6.1.5 Presence of correlated channels.............................................................. 81 6.2 Diversity Gain and Ergodic Capacity Analyses for Arbitrary Network Topologies ...................................................................................................... 82 6.2.1 Diversity gain analysis............................................................................ 82 6.2.2 Ergodic network capacity ....................................................................... 83 6.3 Numerical Results .......................................................................................... 84 6.4 Summary and Discussion ............................................................................... 89 7. CONCLUSIONS................................................................................................. 93 7.1 On the Efficiency Perspective......................................................................... 93 7.2 On the Fundamental Limits Perspective......................................................... 93 7.3 Future Directions ............................................................................................ 94 REFERENCES........................................................................................................ 95 APPENDICES......................................................................................................... 105 APPENDIX A: An Example of Orbit Counting................................................... 107 CURRICULUM VITAE......................................................................................... 112 xii ABBREVIATIONS AF : Amplify-and-Forward ANC : Analog Network Coding ARQ : Automatic Repeat Request AWGN : Additive White Gaussian Noise CC : Cooperative Communication CSI : Channel State Information DF : Decode-and-Forward DDF : Dynamic Decode-and-Forward FDMA : Frequency-Division Multiple Access HM-OPT : Hungarian Method Based Optimal Solution HM-RC : Hungarian Method Based Reduced Complexity Solution i.i.d. : Independent and identically distributed MDS : Maximum Distance Separable LDPC : Low Density Parity Check LT : Luby Transform NC : Network Coding NCC : Network Coded Cooperation OFDMA : Orthogonal Frequency-Division Multiple Access PNC : Physical Layer Network Coding QPSK : Quadrature Phase Shift Keying R2EHK : Random Rotation and Expansion Based Hopcroft-Karp Algorithm rd : Relay-to-Destination Link RLNC : Random Linear Network Coding RNCC : Random Network Coded Cooperation sd : Source-to-Destination Link SDR : Software Defined Radio SNR : Signal-to-Noise Ratio sr : Source-to-Relay Link TDMA : Time-Division Multiple Access TWRC : Two-Way Relay Channel WiCiC : Wireless Channel Induced Coding XOR : Exclusive-Or xiii xiv SYMBOLS M : The number of source nodes N : The number of relay nodes L : The number of coherence bandwidths ℵ : The number of subcarriers ℵc : The number of subcarriers in each coherence bandwidth q : The field size i : The index of source node j : The index of relay node n : The index of subcarrier Si : ith source node Rj : jth relay node ξn : nth subcarrier D : Destination node xi : The source packet of Si xˆj,i : The detected version of xi at Rj αj,i : The code coefficient of xi at Rj cj : The coded packet of Rj ysirj : The received signal at Rj when Si transmits ysid : The received signal at D when Si transmits yrjd : The received signal at D when Rj transmits hsirj : The channel coefficient between Si and Rj hsid : The channel coefficient between Si and D hrjd : The channel coefficient between Rj and D wsirj : The AWGN component at Rj when Si transmits wsid : The AWGN component at D when Si transmits wrjd : The AWGN component at D when Rj transmits σ2w : The variance of the AWGN component u : The link type (sid, sirj, rjd) Ru : The target transmission rate of link u G : The graph model of given communication network V : Vertex set U : User set S : Source node set R : Relay node set D : Destination node set γ¯sr : The average SNR value of sr link γ¯sd : The average SNR value of sd link γ¯rd : The average SNR value of rd link H : Channel-outage matrix of sr links G : Channel-outage matrix of rd links φsr : Outage probability of sr links φsd : Outage probability of sd links xv φrd : Outage probability of rd links Z : Global encoding matrix of RNCC system A : The network coding matrix D : The diagonal matrix of the direct transmission of sd links Z′ : The updated version of Z B : A matrix part of Z with the size of (N − l)× k C : A matrix part of Z with the size of (N − l)× (M − k) N : Communication network model E : The directed edge set C : A cut-set K : The collection of all cut-sets L : The collection of all minimal cut-sets M : The collection of all minimum cut-sets S : A designated source vertex D : A designated terminal vertex vı : ıth vertex e : th edge η : The number of directed edges p : The outage probability of the link e γ : The average SNR of the link e xvi LIST OF TABLES Page Table 3.1 : Measurement results............................................................................ 45 xvii xviii LIST OF FIGURES Page Figure 2.1 : The classical butterfly network demonstrating the throughput enhancement with NC......................................................................... 13 Figure 2.2 : (a) NC encoder, (b) Destination view. .............................................. 14 Figure 2.3 : TWRC model..................................................................................... 16 Figure 3.1 : The network model with M source nodes, N relay nodes, and a single destination node........................................................................ 24 Figure 3.2 : The decoding failure probability results of RNCC, with respect to changing number of relay nodes, N , and field size, q when M = 2. . 36 Figure 3.3 : The decoding failure probability results of RNCC, with respect to changing number of source nodes, M , and field size, q, whenN = 4. 37 Figure 3.4 : The decoding failure probability results of RNCC with respect to average SNR of sd and sr links when q = 8 and γ¯rd = 5 dB. ............ 38 Figure 3.5 : The decoding failure probability results of RNCC with respect to average SNR of sd and sr links when q = 64 and γ¯rd = 5 dB............ 39 Figure 3.6 : The decoding failure probability results of RNCC with respect to average SNR of sd and rd links when q = 8 and γ¯sr = 5 dB. ............ 40 Figure 3.7 : The decoding failure probability results of RNCC with respect to average SNR of sd and rd links when q = 64 and γ¯sr = 5 dB. .......... 41 Figure 3.8 : The upper theoretical bounds (t ≤ 1) and simulation results of decoding failure probability for q = 2 and γ¯sr = 20 dB over various M, N, and γ¯sd values............................................................ 42 Figure 3.9 : The decoding failure probability results of single relay selection versus N values for varying γ¯sd when M = 4, q = 4, and γ¯sr = γ¯rd = 15 dB. ........................................................................................ 43 Figure 3.10: Implementation setup of RNCC. ....................................................... 43 Figure 3.11: The decoding failure probability results of real tests with simulations versus the average SNR value of sd links, γ′sd when M = N = 3. ....................................................................................... 44 Figure 4.1 : An example of tripartite graph model of the network given in Figure 3.1 when M = 2 and N = 3. .................................................. 49 Figure 4.2 : The effective bipartite graph model of the corresponding tripartite graph. .................................................................................................. 50 Figure 4.3 : The decoding failure probability results of various algorithms presented using symmetric SNR case when γ¯u = γ¯, ∀ u and M = 4, N = 7. .................................................................................. 53 xix Figure 4.4 : The decoding failure probability results of various algorithms presented usingAS1 case where γ¯u →∞, u ∈ hrjd, γ¯u = γ¯, u ∈ hsirj and AS2 case where γ¯u → ∞, u ∈ hsirj , γ¯u = γ¯, u ∈ hrjd for M = 4, N = 7. .............................................................................. 54 Figure 4.5 : The decoding failure probability results of various algorithms presented using symmetric SNR case for varying N values when M = 4. ................................................................................................ 55 Figure 5.1 : (a) Outage probability results of the methods versus noise regime, (b) Total transmit power (TTP) and total excess power (TEP) results of the methods versus noise regime......................................... 63 Figure 5.2 : (a) Outage probability results of the methods according to differentRi = R′ values versus noise regime whenM = 4, ℵ = 8, and L = 8, (b) TTP and TEP results of the methods according to different R values versus noise regime when M = 4, ℵ = 8, and L = 8. ................................................................................................ 65 Figure 5.3 : a) Outage probability results of the methods according to different L values versus noise regime forM = 4, ℵ = 8, andRi = R′ = 2, (b) TTP and TEP results of the methods according to different L values versus noise regime for M = 4, ℵ = 8, and Ri = R′ = 2. ..... 67 Figure 5.4 : The comparison of simulation and theoretical results of the decoding failure probability of NCC-OFDMA-SRS for L = 1, ℵ = 8 over varying values of M and N .............................................. 73 Figure 5.5 : The comparison of simulation and theoretical results of the decoding failure probability of NCC-OFDMA-SRS for M = 4, N = 4, and ℵ = 8 over varying values of L. ...................................... 74 Figure 6.1 : There are six exemplary networks denoted by N1, N2, N3, N4, N5, and N6 which are presented in (a), (b), (c), (d), (e), and (f) respectively. N1, N2, N3, N4, N5, and N6 respectively have 3 edges, 4 edges, 2 edges, 6 edges, 4 edges, and 5 edges. ..................... 85 Figure 6.2 : The comparative results of upper and lower bounds of the outage polynomial of N1. ............................................................................... 86 Figure 6.3 : (a) The capacity polynomials results of N1, (b) The ergodic capacity results of N1.......................................................................... 87 Figure 6.4 : The outage polynomial results of N2 versus ρ. ................................. 88 Figure 6.5 : (a) The capacity polynomials results of N2 (b) The ergodic capacity results of N2.......................................................................... 89 Figure 6.6 : The outage polynomial results of all the networks defined in Figure 6.1. .......................................................................................... 90 Figure 6.7 : The ergodic capacity results of all the networks defined in Figure 6.1........................................................................................................ 91 xx RELAYING OPPORTUNITIES FOR WIRELESS NETWORKS BY APPLYING NETWORK CODING SUMMARY In classical relay-aided communication systems, intermediate nodes are able to store and forward received signals to a destination or other intermediate nodes without modifying the content of the received information packets. However, the next generation communication technologies target high data rate and low latency based on the real-time applications in dense network scenarios. Therefore, the efficient utilization of network resources (power and bandwidth) becomes critical at intermediate nodes in order to both increase the throughput and reduce the transmission delay. Network coding (NC) based on mixing packets at relay nodes is proposed as an efficient solution that meets high throughput and low delay demands. By using NC, an increase in data rate and low transmission latency become possible since NC has a flexible nature for an extension to multi-source multi-relay case by assigning different code sets to each relay. Thus, NC can be considered as an effective tool that serves to all of the network users. Furthermore, it can be used as a promising solution for scalability problems in dense networks. While predetermined code sets are used in conventional NC, code coefficients are generated randomly in random linear network coding (RLNC). In RLNC, code coefficients have a uniform distribution and they are independently chosen from a finite field. RLNC yields a flexible scheduling opportunity based on the dynamically changing network components and provides improved efficiency. As cooperation emerges due to the naturally occurring broadcasting over wireless channels, the applications of NC and RLNC in wireless networks enable network coded cooperation (NCC) and random network coded cooperation (RNCC), respectively. In this thesis, we design and characterize various relaying opportunities considering the efficient usage of three types of resources, namely relay, power, and bandwidth, by applying NC in wireless networks. We initially provide a decoding failure probability analysis framework for RNCC systems and propose a relay selection scheme to alleviate the complexity of the usage of all relay nodes. In addition, we propose a topology-aware NC scheme to improve the system reliability. Besides, minimizing power consumption of the wireless systems while maximizing the number of served users is another contribution of the thesis. Designing bandwidth efficient multiple access schemes for NC in frequency-selective channels is also handled. The final main benefit is the determination of the asymptotic performance limitations of unstructured wireless topologies through relating network reliability perspective with max-flow min-cut theorem. Accordingly, we provide efficient transmission architectures at the relay nodes as a first perspective. A new framework is proposed for computing decoding failure probability of RNCC over wireless channels. The full rank condition of the encoding matrix, xxi indicating the successful decoding of the source symbols at the destination node, is utilized. Also, the results belonging to a single relay case and a relay selection scheme are investigated. The validity of the presented theoretical expressions is demonstrated through identical simulation results. An implementation scenario is also presented to show the practical usage effectiveness of RLNC in real time applications by using software defined radio nodes. Conventional NC and RLNC techniques do not take into account the channel conditions while determining network code coefficients. In addition to the characterization of the performance framework of RNCC systems, we propose a new coding scheme called wireless channel induced coding (WiCiC) by considering channel-awareness for the efficient usage of relay nodes in basic operations. We assume that 1-bit quantized channel state information (CSI) is available at the relay nodes, which is a less strict requirement than full CSI knowledge. In the absence of topology awareness, higher field sizes are required to obtain linearly independent codewords because of the wireless channel impairments for RLNC. Due to operating in binary field, the decoding process of the proposed scheme is quite simple compared to conventional network codes and RLNC in higher order fields. In addition, the proposed WiCiC scheme achieves the exact performance of the exhaustive codeword search providing considerably reduced complexity. Therefore, the introduced coding algorithm is convenient for practical implementation thanks to its lower encoding and decoding complexities in wireless networks. As the second perspective, power efficient solutions are designed for wireless networks by considering the efficient bandwidth utilization. Orthogonal frequency-division multiple access (OFDMA) technique not only provides efficient design freedom for improving spectral and power efficiencies but also overcomes the destructive effects of the frequency-selective channel by exploiting multiuser diversity. It also allows effective assignment of limited radio resources to users. Firstly, the joint assignment problem of subcarriers and limited transmission power is addressed as a combinatorial optimization problem for the OFDMA system. To ensure fairness among users while jointly minimizing the total transmit power, the minimization of the number of outage subcarriers is selected as the objective function. An optimal algorithm based on the application of Hungarian method is proposed by utilizing randomly weighted complete bipartite graphs. A reduced complexity algorithm is presented as well. The proposed algorithms reduce the number of outage users compared to the benchmark works and provide significant power savings. After defining individually efficient usage scenarios of the limited resources, we jointly optimize the utilization of all of them. To exploit frequency diversity gain while ensuring orthogonality among multiple users, OFDMA technique is considered as a multiple access scheme for NCC systems, referred to as NCC-OFDMA. Owing to its natural characteristics, such as allowing scalability and providing robustness to channel impairments, NCC can be easily adapted to dense network deployments. Since OFDMA offers a flexible design on bandwidth usage by letting smart subcarrier allocation schemes in frequency-selective channels, combining NCC with OFDMA enables feasible transmission schemes for efficient resource utilization. A single relay selection (SRS) technique is used to mitigate the complexity of utilizing all relay nodes. This system model is referred to as NCC-OFDMA-SRS. In addition, the asymptotic xxii decoding failure probability expressions of the system are obtained, demonstrating that the achievable maximum diversity gain results are attained. The final goal of the thesis is to determine the outage performance analysis of wireless networks for unstructured network topologies. The performance limitations of an arbitrary network topology, comprised of the links that are prone to errors and erasures, constitute an essential problem. The network reliability perspective of the graph theory is invoked to obtain the network outage polynomial of generalized wireless networks by enumerating paths and cut-sets of its graph representation for both uncorrelated and correlated wireless channels. We evaluate the network outage polynomial by utilizing individual link outages, through the use of path enumeration, cut-set enumeration, and terminal-reliability approaches. A relationship between the max-flow min-cut theorem and key communication performance indicators, namely diversity and coding gains, is established. An ergodic capacity analysis of networks with arbitrary topologies is also provided in terms of network outage polynomial. Accordingly, we provide a comprehensive tool that can be used to specify the asymptotic performance limitations under various implementation schemes. In summary, we propose various efficient resource utilization schemes from the relay, power, and bandwidth perspectives associating with NC in wireless networks. In addition, we present extensive performance analyses of the proposed schemes from the aspects of diversity gain, outage probability, and decoding performance. Accordingly, we introduce an overall relaying approach which is a candidate to be utilized in next generation wireless networks. Furthermore, we obtain the performance bounds of generalized wireless networks by applying the concepts of graph theory. Therefore, the performance bounds that provide an additional insight into the system restrictions can be preferred to improve system efficiency. xxiii xxiv KABLOSUZ AG˘LAR I˙ÇI˙N AG˘ KODLAMALI AKTARMA FIRSATLARI ÖZET Klasik röle (aktarma düg˘ümü) yardımlı haberles¸me sistemlerinde, ara düg˘ümler (röle) aldıkları is¸aretlerin içerig˘ini deg˘is¸tirmeden onları sadece depolar ve dig˘er ara düg˘ümlere ya da alıcı düg˘üme iletir. Gelecek nesil haberles¸me sistemleri ise yüksek veri hızı ve düs¸ük iletim gecikmesi ihtiyaçlarını sag˘lamayı hedeflemektedir. Bu yüzden röle düg˘ümlerindeki is¸lemlerin güç tüketimi ve band genis¸lig˘i kullanımı açısından daha verimli bir s¸ekilde gerçekles¸tirilmesine ihtiyaç vardır. Band genis¸lig˘i ve güç gibi sınırlı ag˘ kaynaklarının röle düg˘ümlerinde etkili bir s¸ekilde kullanılması, veri iletim hızının artırılması ve iletim gecikmesinin düs¸ürülmesi açısından kritik bir öneme sahiptir. Literatürde önerilen ag˘ kodlama (network coding, NC) teknig˘i bahsedilen bu beklentileri kars¸ılayabilme potansiyeli olan etkili bir çözüm olmaya adaydır. NC teknig˘i farklı röle birimlerine farklı kod kümeleri atayabilen, çoklu kullanıcı ve röle durumlarına uyum sag˘layabilen esnek bir yapıya sahiptir. Bu yüzden NC teknig˘i, yog˘un ag˘ kullanıcılarının bulundug˘u durumlarda, ölçeklenebilirlik problemini çözebilecek bir yöntem olarak kullanılmaya uygundur. Ayrıca, NC kullanılarak hem veri iletim hızı artırılabilir hem de düs¸ük iletim gecikmeleri elde edilebilir. Belirlenmis¸ kod kümelerinin kullanıldıg˘ı klasik ag˘ kodlama yapılarından farklı olarak, kod katsayılarının sonlu bir kümeden rastgele seçilerek üretildig˘i rastgele ag˘ kodlama (random linear network coding, RLNC) teknig˘i literatürde önerilmis¸tir. RLNC s¸eması, her bir röle düg˘ümünde, kod katsayılarının belirlenen sonlu bir kümeden es¸it olasılıklı ve bag˘ımsız olarak rastgele üretilmesi prensibine dayanmaktadır. RLNC teknig˘i özellikle durumları dinamik olarak deg˘is¸en ag˘ biles¸enleri olması durumunda, esnek planlama özellig˘i sayesinde verimlilig˘in artırılmasını sag˘lar. NC ve RLNC, kablosuz sistemlere uygulandıg˘ında ise kablosuz kanalın dog˘ası gereg˘i her yöne yayılım yapma özellig˘inden dolayı sırasıyla is¸birlikli ag˘ kodlama (network coded cooperation, NCC) ve is¸birlikli rastgele ag˘ kodlama (random network coded cooperation, RNCC) sistemleri kars¸ımıza çıkmaktadır. Bu tezde, sınırlı olan röle, güç ve band genis¸lig˘i kaynaklarının verimli bir s¸ekilde kullanılmasını amaçlayan çes¸itli aktarma uygulamaları tasarlanmaktadır. Öncelikle, RNCC sisteminin kapsamlı kod çözme bas¸arısızlıg˘ı analizi yapılmaktadır ve klasik NC çalıs¸malarındaki tüm röle düg˘ümlerinin kullanılması gereklilig˘inin getirdig˘i karmas¸ıklık, önerilen tekli röle seçimi teknig˘i sayesinde azaltılmaktadır. Ek olarak, kodlama katsayıları üretilirken ag˘ topolojisinin göz önüne alındıg˘ı yeni bir ag˘ kodlama s¸eması önerilmis¸tir. Servis sag˘lanan kullanıcı sayısının maksimum seviyeye tas¸ınırken minimum güç harcanması, bu tezin bir dig˘er katkısını olus¸turmaktadır. Bu kapsamda frekans seçici kanallarda ag˘ kodlama içeren, band genis¸lig˘i açısından verimli bir çoklu eris¸im s¸eması önerilmis¸tir. Tezin son ana faydası ise, ag˘ güvenilirlig˘i ve maksimum akıs¸ minimum kesinti (max-flow min-cut) teoremi kullanılarak, herhangi xxv bir yapılandırılmamıs¸ kablosuz ag˘ sisteminin kuramsal bas¸arım ve ergodik kapasite limitlerinin belirlenmesidir. Öncelikle, bu tez kapsamında ilk bakıs¸ açısı olarak röle birimlerinin verimli kullanıldıg˘ı iletim teknikleri sunulmaktadır. Kablosuz kanaldaki RNCC sisteminin, kod çözme bas¸arısızlıg˘ı olasılıg˘ını hesaplamak için yeni bir s¸ema önerilmektedir. Kod çözme bas¸arısızlıg˘ı hesaplanırken, kodlama matrisinin tam ranklı olması kos¸ulu kullanılmaktadır. Çok röleli sistem modelinin yanı sıra, hem tek röleli hem de tek röle seçimli durumlara ait teorik ifadeler elde edilmektedir. Bu sonuçların geçerlilig˘i, kapsamlı Monte Carlo benzetimleri ile dog˘rulanmaktadır. Ayrıca, RLNC teknig˘inin gerçek zamanlı sistemlerde kullanım avantajını kanıtlamak amacıyla yazılım tabanlı radyo birimlerinden olus¸an bir uygulama senaryosu tanıtılmaktadır. Geleneksel NC ve RLNC tekniklerinde, kanal durumlarını göz önüne almadan kod katsayıları üretilmektedir. RLNC teknig˘inin kablosuz kanallarda kapsamlı bas¸arım analizinin yanı sıra, röle birimlerinin daha etkin bir s¸ekilde kullanılması amacıyla, kablosuz kanalın bag˘lantı durumlarını göz önünde bulunduran yeni bir kodlama s¸eması üzerine çalıs¸ılmaktadır. Bu dog˘rultuda, ikili tabanda is¸lem yapan, kablosuz kanal tarafından uyarılmıs¸ kodlama (wireless channel induced coding, WiCiC) s¸eması önerilmis¸tir. Önerilen WiCiC s¸emasında, ikili alandaki kod katsayıları kanal durum bilgisi (channel state information, CSI) kullanılarak üretilmektedir. Tam CSI’nın bilindig˘i duruma göre daha az katı bir kural olan 1-bitlik düzeyles¸tirilmis¸ CSI bilgisinin röle birimlerinde mevcut oldug˘u varsayımı kullanılmaktadır. CSI bilgisinin mevcut olmadıg˘ı ya da özellikle kodlama katsayıları üretilirken göz önüne alınmadıg˘ı durumlarda, kablosuz kanaldaki bozulmalardan dolayı bas¸arım kayıplarının önüne geçilmesi için kod katsayılarının daha büyük sonlu kümeden seçilmesi zorunlu hale gelmektedir. Kod katsayılarının ikili alandan seçilmesi, kod çözme karmas¸ıklıg˘ını klasik NC ve RLNC’ye göre önemli oranda azaltmaktadır. Böylece, önerilen WiCiC s¸eması hem kodlama hem de kod çözme karmas¸ıklıg˘ının düs¸ük olması sayesinde pratik gerçeklemelerde kullanılmaya oldukça uygun bir tekniktir. I˙kinci bakıs¸ açısı olarak da güç tüketimi ve band genis¸lig˘inin verimli kullanıldıg˘ı sistemlerin tasarımı üzerine yog˘unlas¸ılmaktadır. Dik frekans bölmeli çoklu eris¸im (orthogonal frequency-division multiple access, OFDMA) teknig˘i, hem spektral hem de güç verimlilig˘inin artırılması için tasarım serbestlig˘i sag˘lamaktadır. OFDMA’deki alt tas¸ıyıcılara güç ve frekans ataması is¸lemi, birles¸imsel optimizasyon problemi s¸eklinde tanımlanmaktadır. Kullanıcılar arasında adaleti garanti eden, kesintideki alt tas¸ıyıcı sayısını ve iletim gücünü en aza indirmeyi amaçlayan bir optimizasyon problemi önerilmis¸tir. Hem en iyi hem de en iyiye çok yakın olan daha düs¸ük karmas¸ıklıg˘a sahip ikinci bir algoritma önerilmis¸tir. Bu iki algoritma, hem kesinti olasılıg˘ı hem de güç tüketimi açısından literatürdeki çalıs¸malara göre önemli avantajlar sag˘lamaktadır. Kısıtlı kaynakların ayrı ayrı verimli kullanılmasına yönelik çalıs¸maların ardından, bu kaynakların kullanımı ortak olarak optimize edilmis¸tir. Çoklu kullanıcılar arasında diklig˘i sag˘layarak frekans çes¸itleme kazancından yararlanmak amacıyla, OFDMA teknig˘i, NCC-OFDMA olarak adlandırılan ag˘ kodlamalı is¸birlikli sistemlerde bir çoklu eris¸im teknig˘i olarak düs¸ünülmüs¸tür. Frekans seçici kanallarda OFDMA, band genis¸lig˘i kullanımında akıllı alt tas¸ıyıcı tahsisine izin veren esnek bir yapıya sahiptir. NCC’nin OFDMA ile birles¸tirilmesi, etkin kaynak kullanımı açısından uygulanabilir iletim yapılarına olanak tanımaktadır. Tek bir röle seçimi (single relay selection, xxvi SRS) teknig˘i, tüm röle düg˘ümlerinin kullanıldıg˘ı duruma göre karmas¸ıklıg˘ı önemli miktarda azaltmaktadır ve bu model, NCC-OFDMA-SRS olarak adlandırılmaktadır. NCC-OFDMA-SRS sisteminin kod çözme bas¸arısızlıg˘ı ifadesinin birinci dereceden yakınsaklıg˘ı türetilmis¸tir ve bu sonuçlar benzetimlerle dog˘rulanmaktadır. Buna ek olarak, maksimum çes¸itleme kazancına eris¸ildig˘ini gösteren asimptotik kod çözme bas¸arısızlıg˘ı ifadeleri elde edilmis¸tir. Tez kapsamında ilgilenilen son konu ise yapılandırılmamıs¸ kablosuz ag˘ların kesinti bas¸arımı analizidir. Kablosuz bag˘lantılar hataya ve bozulmaya yatkın oldug˘u için kablosuz ag˘ların bas¸arım limitlerinin belirlenmesi oldukça önemli ve temel bir problemdir. Bu kapsamda, çizge teorisine ait ag˘ güvenilirlig˘i bakıs¸ açısı, yol sayma ve kesinti kümesi sayma teknikleri kullanılarak hem ilis¸kili hem de ilis¸kisiz kanal durumlarında genelles¸tirilmis¸ kablosuz ag˘lara ait ag˘ kesinti polinomu elde edilmis¸tir. Maksimum akıs¸ minimum kesinti teoremi ile çes¸itleme kazancı ve kodlama kazancı gibi haberles¸me sistemleri için anahtar bas¸arım ölçütleri ilis¸kilendirilmis¸tir. Ayrıca, ag˘ kesinti polinomu kullanılarak raslantısal topolojiler için ergodik kapasite sonuçları elde edilmis¸tir. Bu sayede, yapılandırılmamıs¸ kablosuz ag˘lar için farklı senaryolardaki, hem bas¸arım sonuçları hem de asimptotik bas¸arım limitlerini belirleyebilecek kapsamlı bir hesaplama aracı önerilmis¸tir. Özet olarak, bu tezde kablosuz ag˘lar için NC kullanılarak röle, güç ve band genis¸lig˘i açısından verimli kaynak kullanım s¸emaları sunulmus¸tur. Bu yapılara ait ayrıntılı çes¸itleme kazancı, kesinti olasılıg˘ı ve kod çözme bas¸arısızlıg˘ı olasılıg˘ı sonuçları elde edilmis¸tir. Bu dog˘rultuda, gelecek nesil kablosuz sistemlerde kullanılmaya aday olabilecek çok çes¸itli aktarma uygulamaları önerilmis¸tir. Bu çalıs¸malara ek olarak, çizge teorisi temelleri kullanılarak genelles¸tirilmis¸ kablosuz sistemlere ait bas¸arım sınırları elde edilmis¸tir. Böylece, kablosuz sistemlerin tasarım as¸amasında sistemin verimlilig˘ini artırmak için bu bas¸arım limitleri kullanılabilecektir. xxvii xxviii 1. INTRODUCTION This thesis focuses on various relaying applications by considering the efficient usage of three types of resources, namely relay, power, and bandwidth. The thesis especially aims both to propose a cross-layer optimization scheme for smart relaying in wireless networks and to investigate the system performance utilizing network coding (NC). In addition, the asymptotic performance results of any arbitrary wireless network topology are provided by utilizing individual link outages. This chapter continues with the background and motivation of the thesis. Afterwards, the literature overview about the related works is given. Finally, the organization and the contributions of the thesis are elaborated in the last section. 1.1 Background and Motivation In conventional communication systems, functionalities such as routing, error correction and data storage have been designed in accordance with the principle that network nodes perform transmission independently. However, data flow rates from source to destination nodes in a network can be increased by transmitting combinations of data obtained from different source nodes over the network during the same time interval, different from the classical network architecture where data flows are processed independently. Stemming from the early work [1] including the form of multi-level diversity, this technique is referred to as NC in [2]. NC is able to provide efficient usage of network resources and has been attracting increasing attention in recent years. The application of NC in wireless networks has a disadvantage and an advantage. Firstly, as a disadvantage, error propagation may emerge at destination node due to wireless channel impairments. The initial studies on NC assume error free transmissions [2–4] for wired networks. Although such an assumption may be acceptable for wire-line networks, it is overly optimistic for wireless networks. Secondly, direct links, which may occur in the network, can provide an improved 1 error performance between source and destination pairs and can be considered as an advantage. Whether a direct link, also termed as cooperation link, is present or not depends on the corresponding link qualities. These links provide additional cooperative diversity to improve the error performance of wireless networks [5]. Therefore, when the implementation of NC in wireless networks is designed by considering cooperation links, the system is called network coded cooperation (NCC). NCC has higher diversity gain and increased spectral efficiency compared to NC with the help of cooperative communication (CC). 1.2 Literature Overview In this section, we provide a comprehensive literature overview and present open research problems about the considered issues in the thesis related to NCC from different aspects. Thus, the contributions of the thesis can be easily emphasized as will be defined in the next section. 1.2.1 Network coding NC is a promising transmission scheduling method based on mixing the source packets at intermediate (relay) nodes according to the selected network code type, as proposed in [2]. Transmission of the mixed source packets from relay nodes, contributes to both the power efficiency and the increased throughput of the systems with a transmission bottleneck. In the pioneering works about NC, exclusive-or (XOR) coding schemes are presented to offer better decoding performance [2, 6]. Following these works, higher field sizes are preferred to design conventional NC schemes to serve multiple source nodes. Although operations in higher order fields give the opportunity to enable communication to a large number of source nodes, the associated high decoding complexity is a non-negligible drawback. Conventional NC schemes, such as maximum distance separable (MDS) codes, use the optimum codes that satisfy Singleton bounds for static networks [7]. The parity check matrices of MDS codes are used to determine the network code coefficients [8]. These codes are capable of achieving the maximum decoding performance in static network topologies, however, the performance of MDS codes in dynamic network topologies is not sufficient to yield the necessary reliability levels. 2 We provide the generalized system models of NCC together with the extensive literature overview in Chapter 2. 1.2.2 Random network coded cooperation In next generation wireless communication systems, every user and every device are always expected to be connected to a network from anywhere. This challenging requirement leads to an excessive increase in data traffic. Control and management of such a traffic load are extremely difficult and are expected soon to be a reality with the new dense network deployments. In dense network deployments, user connections instantaneously change, resulting in a dynamic network topology. Accordingly, the centralized controlling of networks may become quite complex. In such cases, random linear network coding (RLNC) can be selected as a special type of NC to set-up a decentralized control architecture [9, 10]. Relay nodes use network code coefficients, which are selected from a q−element (q is a prime power) finite field Fq, to create network-coded symbols. Each relay node randomly determines the coding coefficients and generates network coded symbol without a need for a centralized controller. If the number of users changes in the network, the relay node can only increase the number of coding coefficients. The easy implementation of RLNC at the relay nodes improves its flexibility, making it a feasible solution to address dense network problems. The decoding probability analysis of RLNC is given for erasure channels [11]. The theoretical decoding probability expression of RLNC defined in [11] is an approximation of the exact expression. Another work on RLNC over erasure channels is given in [12], where there is a constraint that the coding coefficients are selected from Fq\{0}. The tightness of the presented bounds is demonstrated with the simulation results of RLNC. In [13], an analysis model for RLNC is proposed to calculate the bounds on the theoretical decoding probability expression. In [12, 13], the bounds on theoretical decoding probability are expressed tightly independent of q in a limited region. In addition to this constraint, the homogenized networks are also studied in which signal-to-noise ratio (SNR) values of direct and cooperation links are accepted as identical. However, this assumption is not widely acceptable for wireless links when calculating the upper bounds on decoding probability. Therefore, [13] does not provide the closed form expressions for generalized wireless channel conditions. On 3 the other hand, tight bounds (upper and lower) of RLNC in which coding coefficients are selected from Fq\{0}, are presented in [14] ignoring source to destination links, for multi-source multi-relay scheme. An optimized framework is proposed to minimize overhearing probability while guaranteeing successful decoding for a legitimate user by transmitting random network coded symbols from a source node over erasure channels in [15]. Predefined delay and reliability constraints are also considered when performing simulations and obtaining theoretical derivations in [15]. The exact decoding probability expressions of RLNC in the field F2 are given by considering erasure patterns [16]. As cooperation emerges due to the naturally occurring broadcasting in wireless links, the application of RLNC in wireless networks enables random network coded cooperation (RNCC). The decoding probability results of RNCC are presented by using coding at source nodes to assist a single relay node [17]. Although there are related studies in the literature [10–17], a comprehensive approach for calculating the successful decoding probability of RNCC under wireless channel conditions still remains an open issue. 1.2.3 Topology awareness in network coding In the literature, there are limited works about topology-aware coding. An NC scheme with limited physical layer awareness is used for rate maximization in [18]. An adaptive NC scheme providing rate maximization is proposed for satellite communication networks for time-varying channels [19]. Another study about NC with physical layer awareness focuses on using multiple interfaces [20]. In [21], the optimal coding schemes, which are based on generator matrix MDS schemes in small field sizes for simple multiple access networks, are obtained. There is also an assumption that each source node is connected to the same number of relay nodes in [21]. The link failures between relay nodes and the destination node are ignored as well. In the previous multicast NC works,failed relay-to-destination links are mostly neglected [18–21]. In addition to this fact, the maximum flow perspective has not been considered in the literature with the integrated channel approach. Although the system 4 model of [21] proposes an efficient coding mechanism, a joint design framework for efficient NC according to channel states has not been taken into account yet. 1.2.4 Multi-access schemes for network coded cooperation systems Increasing data rate demands of wireless network users enforce the efficient usage of spectrum while reducing the transmission power. Transmission of multiple nodes can be ensured by using either time-division multiple access (TDMA) or frequency-division multiple access (FDMA). As an efficient implementation of FDMA, orthogonal frequency-division multiple access (OFDMA) can be used to serve multiple nodes under the condition of frequency-selective channels [22], that may be encountered in both phases. In TDMA networks, NCC are completed in two orthogonal time slots [8]. On the other hand, making use of OFDMA, the system under consideration is able to utilize orthogonal frequency bands. Therefore, the transmission phases can be executed using orthogonal subcarriers, reducing the total transmission time. Furthermore, OFDMA provides frequency diversity by allowing flexible assignment of subcarriers to multiple nodes. OFDMA is a competent technique to provide sufficient design freedom to improve spectral and power efficiencies while overcoming the destructive effects of the frequency-selective channel, by exploiting multiuser diversity and allowing efficient utilization of limited radio resources. The assignment of radio resources, namely subcarriers and the transmission power, is conventionally accomplished with the targets of the maximization of each SNR of each link or sum-rate maximization of the total system [9, 23–31]. In these approaches, waterfilling technique is used to allocate the limited power among subcarriers. However, the weighted sum-rate maximization does not guarantee the maximum number of non-outage subcarriers. On the other hand, with a goal of maximizing the number of non-outage subcarriers, the frequency-selective channel in OFDMA is separated into multiple subcarriers. Different from the majority of the works targeting rate (or SNR) maximization, the minimization of the number of outage users in OFDMA networks through a graph-based approach is considered in [32, 33]. A Hungarian method based subcarrier allocation algorithm is proposed to minimize the outage probability while ensuring fairness with providing theoretical approximation formula [32]. They also propose a 5 subcarrier allocation algorithm, random rotation and expansion based Hopcroft-Karp (R2EHK) algorithm, extended from Hopcroft-Karp algorithm in order to obtain maximum cardinality matching, by using an unweighted bipartite graph without considering power allocation [33]. In [34], a suboptimal power allocation approach is proposed as an extension of R2EHK. Both NCC and OFDMA techniques improve the robustness and provide reliable communication against the fading channel impairments. A system combining NCC and OFDMA, referred to as NCC-OFDMA, is shown to provide a significant diversity gain, through the diversity multiplexing trade-off analysis in [35]. On the other hand, the joint resource allocation problem for NCC-OFDMA systems is an open issue from the aspects of fairness among users, high-level functionalities, and practical implementation. 1.2.5 Wireless network reliability analysis In [36], Shannon and Moore provide a reliability analysis of relay-aided systems by considering the unreliability probabilities of relay nodes. It is proven that the end-to-end reliability of a given network can be increased through these unreliable relay nodes. When a sufficient number of relay nodes is used, the probability of network unreliability approaches to zero [36]. However, transforming a complex network into an equivalent serial-parallel projection may not always be possible. When the serial-parallel representation of a given network is not available, the reliability analysis of generalized networks becomes more challenging. There are various methods proposed to calculate network reliability, including state enumeration, factorizing, path enumeration, and cut-set enumeration [37–40]. Although network reliability is a well-studied subject, its extension to wireless networks is still relatively unexplored [41–45]. As the popularity of wireless communication systems increases compared to their wired counterparts in many different areas, the reliability analysis of wireless communication becomes more important, yet challenging since wireless links are more prone to errors and erasures. Accordingly, an unrealistic deterministic channel model is used when investigating the interference effect of the wireless channels [41]. The reliability analysis of wireless multi-hop networks is conducted regarding shadowing effect of the wireless channel 6 in [42, 43]. However, [42, 43] do not consider the correlation effect of shadowing and this gap is filled by [44]. The reliability analysis of wireless multi-hop networks, which proposes a mathematical model to represent the network reliability of correlated shadowing wireless channel, is given in [45]. Network outage polynomial basically defines the zero capacity of any corresponding graph. The investigation of network capacity is an interesting problem since the maximum capacity of any network is limited by the size of the minimum cut of the graph. Therefore, the ergodic capacity results of any network can be calculated by using capacity polynomials. In the literature, there are some studies about the calculation of capacity polynomials that determine the maximum flow of arbitrary networks with random capacity edges by using subset decomposition method [46,47]. In [46], a subspace decomposition principle is used to determine maximum flow of arbitrary networks with random capacity edges. The maximum flow analysis of arbitrary networks with random edge capacities based on Bernoulli distribution is conducted in [47]. The aforementioned works have focused on obtaining only network reliability expressions without considering any fundamental performance analysis. 1.3 Organization and Contributions of the Thesis In order to meet the expectations of next generation communication systems, the classical transmission techniques must be reconsidered according to the requirements of the parameters including high data rate, low latency, easy implementation and scalability. By increasing the number of connected devices and requiring integration of a diverse set of services, new technology demands arise. Various relaying approaches can be considered to increase throughput and to improve the robustness of the system. NCC is a candidate for smart relaying applications, that can be used in the next generation communication technologies. Due to its natural characteristics such as allowing scalability and providing robustness to channel impairments, NC and NCC can be easily adapted to the target network, alleviating the expected implementation issues in dense network deployments. We plan to show that NC/NCC is a convenient technique for future relaying opportunities to satisfy the requirements of the next 7 generation communication systems through performing both theoretical analyses and simulations in this thesis. The thesis also handles multiple resource scheduling problems (such as OFDMA subcarrier selection, determining transmit power levels of these subcarriers, and selection of relays that aids to reliable communication) for wireless networks. The effects of different coding techniques on the system performance are also determined. Accordingly, we make contributions in terms of efficient usage of limited radio and peripheral resources (power, bandwidth, and time). The performance bounds of arbitrary network topologies are introduced as well. The organization flow and the main contributions of the thesis that provide innovations to the literature and research area are explained below by emphasizing the uniqueness of the thesis from different aspects. Chapter 2 includes the review of NCC systems by explaining the signaling model. In addition to reviewing the state-of-the-art in NCC systems, we aim to provide a comprehensive baseline that helps to compare numerous distinct systems proposed in the literature. We explain the conventional NC types in detail and present an overview of the literature on the applications of NCC. The extensive tutorial about NCC whose substantial parts are given in this chapter is presented in the following book chapter and the journal paper. B1: Basaran, S. T., Heidarpour, A.R., Gokceli, S., Kurt, G.K., Uysal, M., and Altunbas, I., (2018). Implementation of Network Coding in Wireless Systems, Network Coding and Subspace Designs, Springer, pp. 295–317. J1: Basaran, S. T., Kurt, G.K., Uysal, M. and Altunbas, I. (2016). A Tutorial on Network Coded Cooperation, IEEE Communications Surveys and Tutorials, 18(4), 2970–2990. Chapter 3 handles the performance analysis of RNCC systems and also investigates the system performance for both single relay and relay selection schemes. We introduce a generalized framework to analyze the decoding failure performance of RNCC. We also provide the decoding failure probability expressions of single relay and relay selection schemes with reduced complexity due to the simplicity of network topology according 8 to the multi-relay case. We validate the theoretical results with simulations to ensure the reliability of derivations. The study explained in this chapter has been presented in the following journal paper. J2: Basaran, S. T., Gokceli, S., Kurt, G. K., Ozdemir, E. and Yaraneri, E. (2017). Error Performance Analysis of Random Network Coded Cooperation Systems, IEEE Transactions on Wireless Communications, 16(8), 5325–5337. Chapter 4 introduces a channel induced coding policy to maximize successful decoding probability of NC system. The proposed wireless channel induced coding (WiCiC) scheme is induced by the wireless channel while the code coefficients are determined according to channel state information (CSI), also providing the opportunity to operate in binary field. We assume that 1-bit quantized CSI is available at relay nodes. The proposed WiCiC scheme achieves the exact performance of the exhaustive codeword search with considerably reduced complexity. Thus, the presented coding algorithm is convenient for practical implementations thanks to its lower encoding and decoding complexities for wireless relay networks. The study explained in this chapter has been presented in the following journal paper. J3: Basaran, S. T. and Kurt, G.K. Wireless Channel Induced Coding, under review. Chapter 5 includes OFDMA extension of NCC systems along with the proposed subcarrier allocation scheme. We initially propose two joint subcarrier and power allocation algorithms based on Hungarian method. While the first algorithm provides the optimal solution, the second algorithm has a reduced computational complexity and its performance converges to the optimal solution at high SNR values. As for our main contribution, the proposed optimization framework addresses the problem of minimizing the number of outage subcarriers in downlink OFDMA systems, by assigning multiple data rates per user while minimizing the total power over a randomly weighted complete bipartite graph model. The proposed approaches provide power savings compared to the benchmark results in the literature. In the second part of Chapter 5, the decoding failure probability analysis of NCC-OFDMA system with a single relay selection (SRS) technique is presented. This system model is referred to as NCC-OFDMA-SRS and is used to mitigate the complexity of utilizing all relay nodes. Both the theoretical decoding failure probability expressions and the diversity gain of 9 NCC-OFDMA-SRS are obtained when R2EHK algorithm is used to assign subcarriers to users. The theoretical expressions are verified by Monte Carlo simulations. The studies explained in this chapter have been presented in the following journal and the conference papers. J4: Basaran, S.T. and Kurt, G.K. (2016). Joint subcarrier and power allocation in OFDMA systems for outage minimization, IEEE Communications Letters, 20(10), 2007–2010. C1: Basaran, S.T., Kurt, G.K. and Chatzigeorgiou, I. (2018). On the performance of NCC-OFDMA with Single Relay Selection, in Proc. Global Information Infrastructure and Networking Symposium, Thessaloniki, Greece, 23-25 October. Chapter 6 introduces a framework to calculate the network outage polynomial as a tool in order to obtain network outage performance of communication networks. We determine the network outage polynomial of some simple directed networks in both correlated and uncorrelated channels. Accordingly, three methods, namely the path-enumeration method, the cut-set enumeration method, and the terminal reliability based method, are proposed. We derive the diversity and coding gains of a wireless network for arbitrary topology based on its graph properties. We establish a relationship between the max-flow min-cut theorem of graph theory and the diversity gain. In addition, we show that the diversity gain corresponds to the size of the minimum cut of the wireless network graph. We also provide the ergodic capacity analysis of networks in terms of individual link outage probability. In addition, an upper bound for the achievable transmission rate is determined. The work explained in this chapter has been presented in the following journal paper. J5: Basaran, S.T., Kurt, G.K. and Kschishang, F. Wireless Network Reliability Analysis for Arbitrary Network Topologies, IEEE Transactions on Communications, under review. Chapter 7 concludes the thesis by providing the main outcomes and summarizes the contributions of the chapters. We also give suggestions regarding possible research topics for the extension of this work. 10 2. NETWORK CODED COOPERATION In this chapter, our primary motivation is to provide an overview of the state-of-the-art in NCC systems from both NC and CC perspectives while providing details about various code types. The signaling model of NCC is generalized in the next chapters for different application scenarios. In wireless networks, the multi-path fading channel can significantly affect the link quality, making the channel more prone to transmission errors. Furthermore, the number of end-users along with their corresponding data rate requirements constantly increases in wireless networks, while the network resources such as frequency spectrum and power remain limited. Wireless communication systems have a broadcast nature through the use of omnidirectional transmission antennas, enabling several nodes, possibly including the destination to receive multiple replicas of the transmission. They also provide spatial diversity through the independent fading channels between distinct node pairs. CC can exploit the spatial diversity, and it can therefore combat the performance degrading effects of the wireless fading channels. Making use of the broadcast nature of the wireless channel, when the source node transmits, the relay nodes (receiving many copies of the transmission signals) can repeat or process the received signals. The destination may capture the source signal, due to the occurrence of direct link between the source and destination. The destination may also receive the signals transmitted from the relays. At the end of the transmission process, the destination combines all received replicas of the information signal in order to significantly improve the error performance of the system. In classical network set-ups, data flows between source-destination pairs are designed individually, without utilizing from any shared infrastructure. The relay nodes, that enable data flows between source-destination pairs, store and forward the data packets, making use of the well-known law of "commodity flow" paradigm [4]. Although commodity flows can be frequently encountered, (as in the design of vehicular traffic networks), when routing data flows, relay nodes can in fact combine the transmitted 11 information packets, instead of simply storing and forwarding [48]. To combine information packets, relay nodes can utilize different coding techniques. Using such smart relay nodes, the data transmission rates can be increased. In this sense, it can be concluded that NC is an alternative to the routing approaches defined in [49]. In order to obtain full benefit of NC in wireless networks, NC techniques have to be considered jointly with CC to eliminate the destructive effects of wireless channels. For example, the direct link between the source and the destination in addition to the transmission over the relay node, is only natural with the goal of robust and reliable transmission with possibly lower power consumption. The main characteristics of NC and CC are combined in the NCC system. In the first phase of NCC, also called broadcast phase, all source nodes transmit information bearing symbols to both relay and destination nodes. This is enabled by the broadcast nature of the wireless channels, where the direct links between source and destination nodes may exist. Note that the broadcast phase is also referred to as the direct transmission phase [50]. In the second phase of NCC, the relaying phase, the relay nodes transmit the network coded symbols to the destination node. The destination jointly processes the signals received from source and relay nodes in order to correctly estimate the transmitted information packets. The existence of direct links between source nodes and the destination increases the diversity gain of the NCC system compared to the basic NC system where the direct link is not exploited. Note that this conventional NCC system can be easily generalized to multiple destination nodes case in an efficient manner. Based on the preliminary work [51], NCC systems have been attracting great interest from a diverse set of researchers including mathematicians, computer scientists and electrical engineers. In the next section, linear network coding and its various coding types are examined. 2.1 Linear Network Coding In their seminal work, Ahlswede et al. have shown that the maximum network capacity of a network coded system is given by the max-flow min-cut theorem [2]. This theorem states that the maximum amount of data flow transmitted from the source node to the 12 SR1 R2 R3 R4 D1 D2 𝑥1 𝑥2 𝑥1 𝑥2 𝑥1 + 𝑥2 𝑥1 + 𝑥2 𝑥1 + 𝑥2 Figure 2.1 : The classical butterfly network demonstrating the throughput enhancement with NC. destination node is equal to the minimum capacity of network cuts (A cut in graph theory defines a partition of the vertices of a graph into two disjoint subsets.) separating the source and destination, representing the bottleneck of the network. It is proven that the maximum network throughput (i.e. minimum cut) can be achieved for acyclic networks with linear network codes (A cycle of a graph is a subset of the edges of that graph forming a path so that the first node of the path is the same as the node of the path. However, an acyclic graph does not contain any cycle.) [52]. The popularity of the NC approaches is increased among the researchers due to their inherent advantages [53, 54]. The provided benefits of linear NC are explained commonly over a butterfly network shown in Figure 2.1, representing the quintessential network topology, where the advantages of NC is clearly illustrated in [2]. In this set-up, the single source is labeled as S and generates two information packets, x1 and x2. R1, R2, R3, and R4 represent the forwarding relay nodes and the destinations are denoted by D1 and D2. The goal is to transmit the packets, x1 and x2, to both destinations, D1 and D2. When relay nodes only forward the incoming information packets, x1 and x2, it is clear that the link between R3 and R4 creates a bottleneck, enabling the transmission of only x1 (or x2). Instead of simply forwarding received packets, if the relay node processes the incoming packets, the throughput can be increased. Specifically, when R3 forwards x1 + x2, then D1 or D2 receive x1 and x1 + x2 or x2 and x1 + x2, respectively. Noting that (x1 + x2) − x2 = x1 and (x1 + x2) − x1 = x2, it can be deduced that both destinations can simultaneously recover x1 and x2 thanks to encoding at R3. 13 𝑥ͳ 𝑥ʹ 𝑥ܯ ௝ܿൌ෍ ௜ୀଵ ெ ߙ௝ǡ௜𝑥௜  ଶܿൌ෍ ௜ୀଵ ெ ߙଶǡ௜𝑥௜ ଵܿൌ෍ ௜ୀଵ ெ ߙଵǡ௜𝑥௜ ேܿൌ෍ ௜ୀଵ ெ ߙேǡ௜𝑥௜ ௝ (a) 𝑥ͳ 𝑥ʹ 𝑥 ௝ǡ௜𝑥௜  ଶܿൌ෍ ௜ୀଵ ெ ߙଶǡ௜𝑥௜ ଵܿൌ෍ ௜ୀଵ ெ ߙଵǡ௜𝑥௜ ேܿൌ෍ ௜ୀଵ ெ ߙேǡ௜𝑥௜ (b) Figure 2.2 : (a) NC encoder, (b) Destination view. In a more generalized linear NC view, the coded packets are the linear combinations of the input packets. This is illustrated in Figure 2.2 for M source and N relay nodes (N ≥ M ). Here, the ith incoming packet, xi, is detected at the jth relay node, Rj . Rj linearly combines these detected packets as cj = M∑ i=1 αj,ixi, (2.1) where the error free transmission is assumed. Although this is a valid assumption for wired networks, where transmission error rates can be kept negligibly low, this simplifying assumption can be overly optimistic in the presence of wireless communication channels. The coefficients, αj,i, can be obtained from a predetermined MDS code or generated randomly as an RLNC. In order to recover coded M packets with linear network codes, the destination node, D, requires at least M linearly independent combinations of transmitted packets. Conventionally, the Gaussian elimination can be used to solve the set of linear equations over Fq to recover x = [x1, . . . , xM ] from the received packets. It is worth noting here that an erroneous estimate at the relay nodes may cause an error at the destination, due to the error propagation through the wireless network. As another decoding approach, the received signals at both broadcast and relaying phases can be used to perform maximum likelihood detection [55]. Most of the NC systems consider the case where code coefficients are available at D [52, 56]. These systems can be referred to as coherent NC. However, the code coefficients can still be reproduced at the destination, for example by transmitting redundant symbols through the network. These systems are referred to as non-coherent 14 coding [57–60]. In [57], a code construction method is proposed to correct different combinations of errors and erasures in non-coherent RLNC. In [58,59], the asymptotic capacity region of the non-coherent NC is derived for multiple source nodes. The capacity of an NC system when relay nodes perform deterministic or randomized linear non-coherent is calculated in [60]. The NC at relay nodes can also be performed through nonlinear mappings on the received packets in [61]; however, our main focus remains in the linear network codes. Linear network codes can be mainly categorized into three subsections, namely analog network coding (ANC), RLNC, and rateless codes, as will be presented subsequently. 2.1.1 Analog network coding As mentioned earlier, in the majority of the NC techniques, NC is applied at the bit (or symbol) level through the operations in Fq, and the associated performance analyses do not consider any transmission error. An exception to this consideration is ANC that inherently takes the impact of the wireless communication channel into account. In ANC, NC is applied at the signal level meaning that coded symbols are obtained by utilizing received signals, instead of estimated bits or symbols. With the aid of characteristics of wireless communication channels, NC is performed without explicitly receiving transmitted packets; however, a combination of these packets is detected. As the main application example of ANC, two-way relay channel (TWRC) is considered. In the TWRC topology, we have two source-destination pairs S1 and S2 as shown in Figure 2.3. S1 targets to transmit x1 to S2 while S2 targets to transmit x2 to S1 [62]. Using binary linear NC, this operation can be completed in three time slots (as opposed to the four time slot routing solution). However in ANC, the relay node obtains a linear superposition of the transmitted signals in a single time slot. The linear superposition is encountered due to the wireless channel nature. The relay node then transmits a combination of the received signals. Thus, NC is performed over the complex number set (hence the term analog), instead of a finite field Fq. To complete the transmission, ANC takes two time slots instead of the three time slots as in NC approach, as illustrated in Figure 2.3. 15 𝑥1 𝑥2 𝑥1 + 𝑥2 𝑥1 + 𝑥2 S1 R S2 Figure 2.3 : TWRC model. Another variation of ANC is the so-called physical layer network coding (PNC). PNC is based on the demodulation of received signals transmitted from the source nodes in the physical layer [6]. Different from ANC, the modulated signal is decided according to superposition of two received signals sent from the source nodes at the relay node. In PNC, when the relay node receives signals form both S1 and S2 nodes simultaneously (solid lines in Figure 2.3), the relay node are able to jointly estimate the transmitted packets x1 and x2 by simply calculating and transmitting x1+x2. Such a joint detection is possible due to the physical characteristics of the wireless channels. Specifically, the channel gains of source-destination links are highly likely to be distinct values. As for the (almost impossible) same gain case, a joint detection of received bits would not be possible, similar to the rank conditions in linear NC. Once x1 + x2 is detected by both S1 and S2, x2 (x1) can be obtained at S1 (S2) thanks to having a priori knowledge of x1 (x2). Following the seminal works, [62] and [63], there has been a surge of research activities in the field of both ANC and PNC [64, 65]. As examples, in [64], a joint decoding scheme is proposed for PNC in TWRC with reduced complexity. In [65], a two-phase spectrum sharing protocol based on an ANC strategy for TWRC is provided. 2.1.2 Random linear network coding When the network topology varies in time or simply unknown at a centralized controller, RLNC as proposed in [9], can be resorted. RLNC is applied as a linear network code, and RLNC coefficients are selected uniformly and independently from Fq. The principles of linear NC also hold in RLNC [9, 66, 67]. RLNC has several applications including peer-to-peer [68] and multicast communi- cations [69, 70]. In [69], two RLNC based transmission methods are proposed for efficient usage of power and delay reduction for multicast scenarios. The robustness of RLNC is substantiated for Byzantine modification of information symbols in distributed multicast networks. Note that when using deterministic network codes, 16 such as MDS codes, the channel conditions have an impact on the error performance. As preliminary examples, in [71] and [72], the impact of the imperfect propagation conditions are considered where the decoding performance is investigated. In addition, the decoding failure analysis is conducted for RLNC without cooperation links in [72]. 2.1.3 Rateless codes in network coding The network codes can be conventionally designed according to the network topology. The apparent example of this fact is the butterfly network as given in Figure 2.1. For more generalized settings, low density parity check (LDPC) codes or MDS codes such as Reed-Solomon codes are suitable candidates for NC [73]. These conventional techniques have fixed-rate codes. On the other hand, if the relay node decides to transmit signals by considering the channel link quality, rateless codes can be applied. The cluster of rateless codes is ignited by fountain codes, Luby Transform (LT) codes and Raptor codes [74, 75]. Fountain codes produce limitless number of outputs from a given input vector. Each output symbol is generated randomly and independently from the remaining other symbols. LT codes are computationally efficient forms of the fountain codes [74]. The corresponding encoding and decoding schemes are quite simple. Raptor codes are also a class of fountain codes with fast encoding and decoding algorithms. In this technique, before LT coding, precoded input symbols are first encoded with a high-rate code (e.g. an LDPC code). The precoded symbols are then encoded by a suitable LT code with a constant average degree [75]. In the literature, there are many applications of rateless codes for NC in wireless networks [76–85]. In [76], an experimental testbed is implemented to determine the development of fountain codes over mobile communication and satellite links. Rateless coding scheme is extended to multiple input single output systems for additive white Gaussian noise (AWGN) channels [77]. The performance of LT and Raptor codes are compared in [78] for binary symmetric and AWGN channels. In [79], a combined erasure correction code of rateless scheme and feedback channel is proposed to minimize the processing time and memory requirements of transmitter and receiver structures. On-the-fly verification of rateless error codes is investigated by using discrete-log-based hash scheme to authenticate the completeness of downloaded data in [80]. In [81, 82], a fountain code based relaying protocol that improves the system performance, is 17 proposed. The extended version of [82] is given in [83]. Raptor codes are used to adaptively determine the bit rate of the relay node according to the link quality in [83]. In [84], perfect rateless codes are designed for AWGN channels by means of low complexity decoding algorithms consisting of layered encoding and successive decoding. In [85], rateless codes are modified to ensure the properties of unequal error protection and unequal recovery time for applications such as video-on-demand systems. 2.2 Cooperative Communication Aspect of Network Coded Cooperation CC offers a smart approach to exploit the broadcast nature of the wireless channels by increasing the diversity gain of the network, and thus improving the error performance [5, 86]. The diversity gain is one of the main performance metrics of the wireless channels that represents the decay rate of the bit error rate (or outage probability) with respect to the SNR. As SNR goes to infinity, the outage probability (or error rate) of a wireless network is proportional to SNR−d, where d indicates the diversity gain. The diversity gain can also be interpreted as the number of independent fading links between a source node and a destination node. The basic implementation of CC considers a three node network with a source (S), relay (R) and destination (D), where S transmits information symbols to D through R [5, 86]. In classical routing solutions, in the first time slot, S transmits to R. Following the broadcast phase, R estimates the symbol using the received signals from source nodes according to the selected cooperation technique. In the second phase, R transmits the estimated symbol to D to aid source-destination transmission. The diversity gain of such a system is one. However, in wireless communication networks, it is a possibility that there is also a direct link between S and D. The preliminary works on CC propose a way of combining the received signals at the destination. Since there are two independent links between S and D, the diversity gain becomes two in this topology. Doubling the diversity gain significantly improves the error performance of the system. CC schemes can be classified according to the processing strategy at the relay nodes. The widely preferred relaying strategies are the amplify-and-forward (AF) and the decode-and-forward (DF) approaches. In the AF approach, the relay node receives the signal from S and amplifies the signal according to the channel conditions and 18 forwards to the destination [87]. In the DF approach, R first detects the transmitted symbol using the received signal from S, and then modulates and transmits the detected signal to D [88]. Furthermore, there are other prominent forwarding strategies such as compress-and-forward [89] and compute-and-forward [90]. Making an erroneous decision at the relay node remains a critical issue in the CC systems. This erroneous link decision is non-negligible in the end-to-end error performance between S and D nodes. In order to alleviate the associated performance loss, channel-aware demodulators and link adaptive relaying solutions have been proposed [91–95]. In [91], an end-to-end link adaptation and selection method is presented with efficient adaptive modulation and coding scenarios for wireless relay channels. In [92], transmit power adaptation is used to obtain the optimum spectral efficiency while switching between half and full duplex modes at the relay. In [93], a combined rate adaptation and relay selection protocol is proposed for multi-relay channels in DF transmission. In [94], a link adaptation protocol is presented to jointly reduce the number of transmissions for error correction and automatic repeat request (ARQ) schemes. Transmission rates of all transmitting nodes (i.e., source and relay nodes) are jointly determined for multi-hop relay channels with incremental redundancy hybrid ARQ [95]. Note that an erroneous decision at the relay node also constitutes a problem for NCC systems and similar adaptation strategies are considered to alleviate this performance loss due to the error propagation. To combat erroneous decisions at the relay node, dynamic decode-and-forward (DDF) protocol is proposed as a DF extension, in which the transmission functionalities of relays are not fixed [96]. Relay node determines the received signal when to switch from passive mode to cooperation mode based on the received signal quality. DDF does not require knowledge of CSI at source node [96]. Rateless codes can also be used in DDF transmission protocols, which allow dynamic switching between receiving and transmitting phases of the relay node [97–99]. A fountain code based relaying protocol for cooperative sensor networks is proposed in [97]. In [98], rateless codes are used in a DDF protocol. In [99], a robust rateless code based DDF protocol is proposed to remove the error floor stemming from LT encoding. As can be inferred from the leading literature, relay nodes can be switched between 19 receiving and transmitting phases based on the use of rateless codes to improve the performance of CC systems. 2.3 Conventional Network Coded Cooperation Benefits of NC are apparent for multi-source and/or multi-destination relay aided networks [100, 101]. NCC jointly aims to extend the benefits of NC techniques to wireless networks and to exploit the spatial diversity provided by the wireless channels through CC approaches. The existence of direct source-destination links is the main differentiating factor between NC and NCC systems, making NCC solution suitable for wireless networks. The basic NCC transmission protocol is composed of two phases, the broadcast phase and the relaying phase [8]. At first, M source nodes transmit their signals to relay and destination nodes, using either time-division multiplexing [8] or frequency-division multiplexing [35]. Following the reception of source signals at the end of the broadcast phase, the relay nodes detect the transmitted symbols coming from source nodes. The relay nodes then perform NC on detected source symbols and generate network coded symbols. Note that αj,i ∈ Fq denotes NC coefficient of the jth relay node for the ith source node signal. Following the broadcast phase, the relay nodes transmit network coded symbols in the relaying phase. NCC arises from the idea of combining error performance advantages of the CC obtained through the wireless communication channel and the transmission rate advantages of NC. In [51], both NC and cooperation in a distributed antenna set-up are considered. Two distinct scenarios are presented in [51]. In the first scenario, two source nodes transmit their signals to the destination through the use of an assisting antenna that performs NC. In the second scenario, two source nodes first share their information symbols and then perform binary NC. The cooperation among source nodes are referred to as user cooperation. The diversity gain can be doubled, compared to conventional NC systems through the use of cooperation (due to the direct link between S and D) [51]. Based on this fact, the direct source-destination links are utilized to increase the diversity gain of the overall system in NCC protocols, compared to conventional NC approaches. These scenarios are also extended to multiple source multiple relay (referred to as assisting antenna) cases in [51]. Multiple source nodes with a single relay node scheme is considered in [102], where diversity gain of two can 20 be obtained by combining source signals received at the relay node through NC. The work is also extended in [103], where closed-form approximations for the asymptotic symbol error rates and bit error rates are derived for the NCC system. NCC can also be used to prioritize source nodes, through the dedication of network resources according to the priorities of the sources in order to adjust the corresponding diversity gain [104, 105]. In this case, the network code coefficients need to be determined according to the desired diversity gain. 2.4 Summary and Discussion In this chapter, in addition to reviewing the state-of-the-art in NCC systems, a comprehensive baseline that compares various distinct systems proposed in the literature is provided. NCC systems are targeted towards the use of NC techniques in wireless environments. The possible source-destination links increase the diversity gain of the broadcast/multicast systems. The selected network code has a crucial effect on the performance of the overall system. NCC is a suitable candidate for smart routing application, that can be used in next generation communication technologies. Due to its natural characteristics allowing scalability and providing robustness to channel impairments, NCC can be easily adapted to the target network, alleviating the expected implementation issues in dense network deployments. 21 22 3. DECODING FAILURE PROBABILITY ANALYSIS OF RANDOM NETWORK CODED COOPERATION SYSTEMS This chapter introduces RNCC signaling model, the theoretical decoding failure probability analysis of RNCC providing additional cooperative diversity, and corresponding simulation results. From many different perspectives including single relay, multiple relays, and single relay selection schemes, the theoretical decoding failure probability expressions are derived, which fill the void in the RNCC literature. The effectiveness of RLNC is demonstrated for long-term evolution networks in [106,107]. In RLNC, network code coefficients are generated randomly at relay nodes without conforming to any code set for all relay nodes. The coefficients of RLNC are selected from Fq with size q. If the field size is sufficiently large, independent coding vectors of different relays can be obtained. 3.1 RNCC Signaling Model We consider a wireless multi-source multi-relay system with a single destination node as shown in Figure 3.1. There are M source nodes, N relay nodes, and a single destination node denoted by Si, Rj , and D, respectively for i = 1, 2, . . . ,M and j = 1, 2, . . . , N . There are three different types of channel, namely source-to-destination (sd), source-to-relay (sr) and relay-to-destination (rd). The transmission channel coefficient between Si (Rj) and Rj (D) nodes is indicated by hsirj (hrjd). In addition, hsid denotes the channel gain between Si and D. RLNC is used as the coding technique at relay nodes, therefore we encounter RNCC signaling model. The transmission process of RNCC is made up of two orthogonal phases just as classical NCC schemes, namely broadcast and relaying. In the broadcast phase, each source node sends the regarding symbol to relay and destination nodes where xi represents the data packet of Si. The transmitted signal of Si is denoted by x˜i which is the modulated signal of xi. The received signals at relay nodes are given as ysirj = hsirj x˜i + wsirj , (3.1) 23 Dsr link sd link rd link R1 RN SM S1 Figure 3.1 : The network model with M source nodes, N relay nodes, and a single destination node. where the AWGN component at Rj is indicated by wsirj for transmission of modulated signal x˜i. The transmitted signal, x˜i, is received by the destination at the same time due to the inherent wireless channel nature. The received signals at the destination can be expressed as ysid = hsidx˜i + wsid, (3.2) where wsid represents the AWGN component at D. Following the broadcast phase, each relay node detects the received signals and encodes these signals in the relaying phase. The coded packet of Rj can be calculated as a summation in Fq which can be defined as cj = M∑ i=1 αj,ixˆj,i, (3.3) where xˆj,i denotes the detected version of xi at Rj in the broadcast phase. Relay nodes employ RLNC where the coding coefficients, αj,i, are selected independent and identically distributed (i.i.d.) following uniform distribution from a finite field, Fq [9]. αj,i can uniformly and randomly take the values from 0 to q − 1. The field size, q, is an important design parameter which determines the decoding performance of RNCC. After generating network coded symbols, relay nodes perform transmission 24 of the symbols in orthogonal resource blocks to avoid generating interference at the destination. Relay nodes forward cj packets (c˜j also denotes the modulated signal of cj .) to the destination in the relaying phase. The received signal of Rj at the destination can be expressed as yrjd = hrjdc˜j + wrjd, (3.4) where wrjd indicates AWGN component at D, respectively. At the end of the transmission process, destination node decodes received packets by applying Gaussian elimination method [9]. Some packets may not be received at Rj and/or the destination due to the wireless channel impairments, and thus outage events are considered in the calculation of the successful decoding probability of the RNCC. Outage probability is a meaningful metric to measure the quality of transmission which defines the connection status of any transmission link. Here, hu and γ¯u define the channel gain and average SNR of link u, respectively, for u ∈ {sid, sirj, rjd}. The outage probability of link u is determined as φu = Pr { log ( 1 + |hu|2γ¯u ) < Ru } , (3.5) where Pr{·} and Ru indicate the probability function and the target transmission rate of link u to avoid outage status, respectively. The expression in (3.5) can be simplified as φu = Pr { |hu|2 < 2Ru − 1 γ¯u } . (3.6) For Rayleigh block fading channels, hu ∼ CN (0, 1), the expression in (3.6) is transformed into φu = 1− exp ( − ( 2Ru − 1 ) /γ¯u ) . (3.7) Considering three different types of channels occurred between sd, sr, and rd links, we assume that all links of each channel type have the same outage level with φsid = φsd, φsirj = φsr, and φrjd = φrd to simplify the notation. The outage probability of any sd (sr) link is indicated by φsd (φsr) in the broadcast phase. φrd denotes the outage probability of any rd link in the relaying phase. 25 3.1.1 Network model As mentioned above, a cooperative communication set-up is composed of two phases as broadcast and relaying [8]. In the broadcast phase, source nodes transmit information-bearing signals to relay and destination nodes by using orthogonal radio resources. Both relay and destination nodes can detect the transmitted packets due to the broadcast nature of the wireless communication channel. The global encoding matrix of RNCC system is defined as Z := [ D A ] =      d1 0 · · · 0 α1,1 · · · αN,1 0 d2 · · · 0 α1,2 · · · αN,2... ... . . . ... ... . . . ... 0 0 · · · dM α1,M · · · αN,M      T , (3.8) where the first M diagonal entries of Z form an M × M diagonal submatrix, corresponding to the direct transmission of sd links in the broadcasting phase [8]. The remaining entries correspond to the random network coded coefficients generated by relay nodes. If the link between Si and D is in outage, di is equal to zero, otherwise, it is equal to 1 in Fq. We assume that the corresponding relay nodes which successfully decode at least one packet sent from M source nodes are allowed to participate in the relaying phase using RLNC. We also assume that at most one link from source to each relay node fails due to preserving encoding scheme. We give an example of RNCC system with M = 3 and N = 4 to explain the structure of global encoding matrix, Z. After completion of two transmission phases, destination node requires Z matrix to detect the source packets correctly. For instance, the global encoding matrix of this system in error-free case can be constituted as Z =   1 0 0 α1,1 α2,1 α3,1 α4,1 0 1 0 α1,2 α2,2 α3,2 α4,2 0 0 1 α1,3 α2,3 α3,3 α4,3   T . (3.9) As widely accepted in RLNC literature [9,66,67], we assume that the encoding matrix is available at the destination. This approach is called coherent detection. On the other hand, if the destination has no prior knowledge about the encoding matrix, it tries to obtain the coefficients through different ways, such as transmission of pilot symbols from the relay nodes by using the coefficients or placing the coefficients at the beginning of each transmitted packet at the relay nodes. This strategy is referred to as non-coherent NC [57, 59, 60]. Consequently, the destination node needs to have 26 the knowledge about the encoding matrix to successfully decode the received symbols. After that, the knowledge about coding matrix simplifies the decoding procedure at the destination node, and the Gaussian elimination method can be used to decode the received symbols over Fq [9]. If the destination node has minimumM orthogonal code vectors, it is able to obtain all source symbols. The number of orthogonal code vectors can be calculated as the rank of a given encoding matrix. The destination node checks whether the rank condition is met to calculate the decoding failure probability. 3.2 Decoding Failure Probability Analysis of RNCC The theoretical decoding probability expressions of RNCC system can be derived through considering the destructive effects of wireless channel. The field size, q, must be taken into account as another design parameter which affects the decoding probability performance of RNCC. The decoding failure probability is defined as Pfail = 1 − Pd, where Pd represents the successful decoding probability and can be described as Pd := Pr{rank(Z) ≥ M}. The details of the closed form expression of Pd is defined in the next subsections. 3.2.1 Individual link outages The effects of outage status of each type of transmission links (sd, sr, and rd) on decoding probability performance of RNCC are different, and therefore they need to be individually considered. First, we investigate the effect of outage situation of sd links. The probability of k sd links in outage is given by Psd(k) = (M k ) φksd(1− φsd)M−k, (3.10) where M − k sd links are in non-outage state. The outage sd links result in zero elements in the diagonal of the upper matrix of Z (D). If there is no outage sd links, destination node accurately decodes the received signals without the requirement of any encoded symbols. On the other hand, if any sd link is in outage, destination node requires encoded symbols to decode the received packets. The probability that l rd links in fail can be calculated as Prd(l) = (N l ) φlrd(1− φrd)N−l, (3.11) 27 where N − l rd links are available in the system. There might be sr link outages in the system in addition to sd and rd link failures. Outage status of the ith sd link is represented by di = 0, where the rank of Z may be decreased by one. This reduction of the rank causes performance degradation. If any rd link is in outage, the destination loses the related symbol of the corresponding relay that contains a combination of all source symbols. Therefore, the corresponding row of Z is set to all zeros. In the case of a link failure in sr, the corresponding source signal cannot be used by the corresponding relay node in the encoding process, and so only the corresponding entry in matrix, Z, is deleted. Z can be simplified by using the definitions above and the information about k and l, which represent the number of outage links. We may assume that the failed sd (rd) links are the first k (the last l) number of sd (rd) links. That is, the first k diagonal entries of D are zero, while the last l rows of A are zero. The updated version of Z is represented by Z′ and it is used to simplify the derivations of the successful decoding probability of RNCC. The updated encoding matrix is determined as the (M+N)×M block matrix defined as follows Z′ =     0 0 0 IM−k B C 0 0     , (3.12) where B is an (N − l) × k matrix, C is an (N − l) × (M − k) matrix, IM−k is the (M − k) × (M − k) identity matrix, and the zeros appearing in Z′ are zero matrices of appropriate sizes. The rank of the last M − k columns of Z′ is equal to M − k due to the identity matrix, indicated by IM−k in Z′. Therefore, the probability of Z has full rank, M , similar to that of the probability of B has rank k. The corresponding relationship is defined as rank(Z′) = rank(B) + (M − k). (3.13) In other words, the successful decoding probability of RNCC system, which is the probability of Z having full rank, is equal to the probability of B having rank k. Therefore, we consider only B matrix to derive the successful decoding probability of RNCC to reduce the computational complexity of the system. Thus, sr link outages should be considered for B matrix instead of Z. 28 If the link between Si to Rj is in outage, then the (j, i)th entry of the bottom matrix of Z is forced to be zero. We assume that for each relay node at most one of the M incoming links from source nodes is in outage. Therefore, t sr links in fail means that exactly t relays lose a packet, and so exactly t rows of the bottom matrix of Z have precisely one entry forced to be zero with probability φsr. Note that if an rd link fails then we suppose that there is no source which fails when transmitting data to the corresponding relay. That is, we assume that if a row of Z consists entirely of all zeros then that row does not contain any entry which is forced to be zero. We continue with the reduced sized matrix B to obtain the successful decoding probability. The outage probability of an sr link for B is equal to kφsrM since B has k columns. The probability that t sr links are in fail is given by Psr(t) = (N − l t )(kφsr M )t( 1− (kφsr M ))N−l−t , (3.14) where the number of rows and columns of B matrix are equal to N − l and k, respectively. An example of encoding matrix, Z, is defined in (3.9). The parameters are selected as k = 2, l = 1, and t = 1, related with the channel conditions. Accordingly, the corresponding updated encoding matrix of destination node can be written as Z′ =    0 0 0 α1,1 α1,2 α1,3 0 0 0 0 α2,1 α2,2 α2,3 0 0 0 1 α3,1 0 α3,3 0    T , (3.15) where the dashed, dotted, and solid boxes represent the sd, sr, and rd link failures, respectively. 3.2.2 Calculation of conditional successful decoding probability In the previous subsection, the probabilities of the number of link failures of sd, sr, and rd are determined. Now, we consider a particular configuration of k out of M sd, l out of N rd, and t sr link failures. We let Ak,l,t be the set of block matrices of Z for which the entries di of D corresponding to these k sources are zero, the rows of A corresponding to these l relay nodes consist entirely of all zeros, and exactly one entry in each of t rows of A corresponding to these t sources are forced to be zero. We also let Bk,l,t be the set of matrices in Ak,l,t that have full rank, M . For this particular 29 configurations of k sd, l rd, and t sr, the probability of successful decoding at the destination is equal to the ratio, |Bk,l,t||Ak,l,t| , where | · | indicates the cardinality operator. As permuting rows do not change the rank of any matrix, the probability of successful decoding, when k sd link in fail and l rd link in fail, and t sources to relays fail, does not depend on the particular configurations of k, l, and t. 3.2.3 Counting full rank and rank deficient matrices In order to calculate the successful decoding probability of RNCC, all types of link outages and all possible configurations should be considered. Therefore, the successful decoding probability at the destination node is computed through the following expression Pd = ∑ k ∑ l ∑ t P (d |k sd, l rd, t sr)Psd(k)Prd(l)Psr(t), (3.16) where P (d|k sd, l rd, t sr) represents the conditional successful decoding probability for a particular configuration and is given as P (d |k sd, l rd, t sr) = ∑ k,l,t |Bk,l,t| bk,l,t|Ak,l,t| , (3.17) where the sum ranges over all possible configurations of k, l, and t. bk,l,t denotes the number of all possible configurations of k, l, and t. It is clear that bk,l,t = bkblbt where bk, bl, and bt are the respective numbers of all possible configurations of k, l, and t satisfying the required conditions, respectively. We now target to count bt of all possible configurations of t when the numbers k, l, and t are fixed and the configurations of k and l are fixed as well. Let t, which is the number of relays to which the data transformations from sources fail, be a fixed number. For any i, we let ϕi be the number of entries in the ith column of A which are forced to be zero. Therefore, we obtain the following equation ϕ1 + ϕ2 + · · ·+ ϕM = t, (3.18) where ϕi is a non-negative integer. For a fixed solution of ϕ1, ϕ2, . . . , ϕM in (3.18), C(ϕ1, ϕ2, . . . , ϕM) is the number ofN×M matrices, A, whose the ith column contains ϕi number of forced zero entries. It can be calculated as follows: Each column has N entries and ϕ1 zeros in the first column of A may be distributed in (N ϕ1 ) ways. As each 30 row of A can contain at most one forced zero entry, ϕ2 zeros in the second column of A should be distributed to N − ϕ1 rows, which may be done in (N − ϕ1 ϕ2 ) ways. Continuing in this manner, we observe that C(ϕ1, ϕ2, . . . , ϕM) = (N ϕ1 )(N − x1 ϕ2 )(N − (ϕ1 + ϕ2) ϕ3 ) . . . (N − (ϕ1 + ϕ2 + · · ·+ ϕM−1) ϕM ) = N !ϕ1!ϕ2! . . . ϕM !(N − t)! . (3.19) Therefore, the number of all possible configurations of t can be defined as bt = ∑ tC(ϕ1, ϕ2, . . . , ϕM), where the sum ranges over all non-negative integer solutions of (3.18). The above sum expressing bt has (M + t− 1 t ) summands, which is the number of non-negative integer solutions of the (3.18). The set of all permutations of a finite set with M elements forms the symmetric group SM . The details about the definitions of symmetric groups are available in [108]. In our case, by permuting the indices of a solution, the symmetric group, SM , acts on the set of non-negative integer solutions of (3.18). This action corresponds to the permutations of the columns of A, and hence does not change the rank. To be more precise, by permuting columns of the symmetric group, SM , acts on the set {Mϕ1,ϕ2,...,ϕM} where ϕi ranges over all non-negative integer solutions of (3.18) and {Mϕ1,ϕ2,...,ϕM} is the set of all N ×M matrices each of whose ith column contains ϕi forced zero entries and whose rows have at most one forced zero. Note that the set ⋃Mϕ1,ϕ2,...,ϕM , where ϕi ranges over all non-negative integer solutions of the (3.18), consists of all possible configurations of t and also note that |Mϕ1,ϕ2,...,ϕM | = C(ϕ1, ϕ2, . . . , ϕM). (3.20) Suppose that the action of SM on the set of non-negative integer solutions of (3.18) transforms the solution zj to the solution z¯j . Afterward, the corresponding action on the set {Mϕ1,ϕ2,...,ϕM} transforms the set {Mz1,z2,...,zM} to the set {Mz¯1,z¯2,...,z¯M}. Choosing arbitrary matrices as M ∈ {Mz1,z2,...,zM} and M ∈ {Mz¯1,z¯2,...,z¯M}, we have two configurations of t corresponding to M and M. As permuting rows and columns do not change the rank, the numbers |Ak,l,t| and |Bk,l,t| in two configurations of t corresponding to M and M are the same. Therefore, for a fixed t, instead of summation of the probabilities in each of all possible configurations of t, we can take an arbitrary configuration in any matrix lying in any set in each orbit of the action of 31 SM on the set {Mϕ1,ϕ2,...,ϕM}. The conditional successful probability expression given in (3.17), is expressed as P (d |k sd, l rd, t sr)= ∑ k,l 1 bkbl ∑ t otC(ϕ1, ϕ2, . . . , ϕM)|Bk,l,t| bt|Ak,l,t| , (3.21) where ot is the number of elements in the orbit of the solution ϕi under the action SM on the set of non-negative integer solutions of (3.18). The outer sum ranges over all possible configurations of k sd and l rd link failures. The inner sum ranges over the orbits of the action of SM on the set of non-negative integer solutions of (3.18) or over the orbits of the action of SM on the set {Mϕ1,ϕ2,...,ϕM}. That is, the inner sum ranges over ϕ1, ϕ2, . . . , ϕM where one solution ϕi is chosen arbitrarily in each orbit of the action SM on the set of non-negative integer solutions of (3.18). It is clear that in each orbit of the action of SM , there is a unique solution of (3.18) satisfying the conditionϕ1 ≤ ϕ2 ≤ . . . ≤ ϕM . Thus, orbits correspond to the partitions of t. Using the orbit-stabilizer theorem (use, for instance, Theorem 3.19 of [109]), we see that the number of elements of the orbit containing a partition of t is equal to the index of its stabilizer in SM . Given a partition ϕ1 ≤ ϕ2 ≤ . . . ≤ ϕM of t, its stabilizer is the set of permutations a ∈ SM such that a(υ) = ν ⇐⇒ ϕυ = ϕν . Letting δ be the partition of t and F (δ) be the set of {f | ϕf 6= ϕf+1} ∩ {1, 2, . . . ,M − 1}, we see that the order of the stabilizer of δ is given as f1!(f2−f1)!(f3−f2)! · · · (fg−fg−1)!(M−fg)!, where F (δ) = {f1 < f2 < · · · < fg}. Therefore, the number of elements in the orbit of the solution ϕi given as ot = M ! f1!(f2 − f1)!(f3 − f2)! · · · (fg − fg−1)!(M − fg)! , (3.22) where ϕ(δ) is defined as follows ϕ(δ) := f1!(f2 − f1)!(f3 − f2)! · · · (fg − fg−1)!(M − fg)!. (3.23) We provide a numerical example to explain the action of a symmetric group on the set of solutions and its orbits in the Appendix A. The conditional successful decoding probability (3.21) is updated as P (d |k sd, l rd, t sr) = ∑ k,l 1 bkbl ∑ δ∈℘M (t) M ! ϕ(δ)C(δ)|Bk,l,t| bt|Ak,l,t| , (3.24) 32 where the outer sum spans all possible configurations of k and l. Here, ℘M(t) denotes the set of non-negative integer solutions of (3.18) satisfying ϕ1 ≤ ϕ2 ≤ . . . ≤ ϕM . Moreover, if δ := ϕ1 ≤ ϕ2 ≤ . . . ≤ ϕM then it can be defined that C(δ) = N !ϕ1!ϕ2! . . . ϕM !(N − t)! . (3.25) We note that if the action of SM sends a solution ϕi to a solution ϕ¯i, then it can be written as C(ϕ1, ϕ2, . . . , ϕM) = C(ϕ¯1, ϕ¯2, . . . , ϕ¯M). Therefore, we obtain that bt = ∑ δ′∈℘M (t) M ! ϕ(δ′)C(δ′). Note that bt depends only on the values of the numbers k and l. However, it does not depend on how k and l are configured. As permuting all the rows of D and the rows of A do not change the rank of the block matrix, Z, it is clear that the inner sum in (3.24) does not depend on the particular configurations of k and l. Therefore, (3.24) is a sum of bkbl terms each of which is identical. Since each summand is equal to 1bkbl times the inner sum, we see that P (d |k sd, l rd, t sr) = ∑ δ∈℘M (t) M ! ϕ(δ)C(δ) bt ( |Bk,l,t| |Ak,l,t| ) = ∑ δ∈℘M (t) M ! ϕ(δ)C(δ) ∑ δ′∈℘M (t) M ! ϕ(δ′)C(δ′) ( |Bk,l,t| |Ak,l,t| ) . (3.26) The above expressions about sr link failures are described for the global encoding matrix, Z. To reduce the computational complexity, we explore the full rank probability of B as defined in (3.12). The corresponding size of B is considered for each transmission case when calculating the successful decoding probability of RNCC. By using the previously defined expressions, the successful decoding probability of RNCC is given as Pd = ∑ k,l,t P (d |k sd, l rd, t sr)Psd(k)Prd(l)Psr(t) = M∑ k=0 N−k∑ l=0 N−l∑ t=0 ∑ δ∈℘M (t) [(M k )(N l )(N − l t ) M ! ϕ(δ)C(δ) bt ( |Bk,l,t| |Ak,l,t| ) φksd(1− φsd)M−kφlrd(1− φrd)N−l ] × [(kφsr M )t( 1− (kφsr M ))N−l−t ] . (3.27) To calculate |Ak,l,t| and |Bk,l,t|, we assume that the first k diagonals of D are zero entries and the last l rows of A are zero rows. Note that if l > N − k then N − l < k, and therefore |Bk,l,t| = 0, that explains why the index l of the second sum in (3.27) is from 0 to N − k. 33 The |Ak,l,t| and |Bk,l,t| can be found with using matq(·) functions defined in [110]. In [110], the calculation of the number of matrices with a given rank condition is considered while positions of zeros (S) are fixed over a finite field. For fixed positions, these matrices are not defined in polynomials for all cases. In Theorem 3.6 of [110], it is proven that the problem is a polynomial if the same line is at most two zeros. The considered problem yields this constraint. For any integers M,N, and r for any subset S, matq(N,M,S, r) is the number of N ×M matrices over Fq of rank r whose (j, i)th entry is zero if (j, i) is in S [110]. For a fixed partition, δ ∈ ℘M(t), |Ak,l,t| and |Bk,l,t| can be calculated as |Ak,l,t| = k∑ r=0 matq(N − l, k, Sˆδ, r), |Bk,l,t| = matq(N − l, k, Sˆδ,1, k), (3.28) where Sˆδ, and Sˆδ,1 specify, respectively, the first k terms of the partition δ and the last M − k terms of the partition δ while the coordinates of the entries that are forced to zero according the partition δ. Therefore, |Ak,l,t| is equal to the number of elements of the set of (N − l) × k matrices whose t rows contain entries which are forced to zero and whose columns contain these t zeros according to the permutation δ ∈ ℘M(t). Moreover, |Bk,l,t| is equal to the number of elements of the set of (N − l)×k matrices, B with rank k, whose first t rows may contain entries which are forced to zero and whose columns contain these (possibly less than t) zeros according the first k terms of the partition δ ∈ ℘M(t). Recalling the assumptions on the configurations of the positions of k, l, and t, the matrices in Ak,l,t are the block matrices of type Z′, as given in (3.12). Thus, a block matrix Z′ in Ak,l,t is in Bk,l,t if and only if the (N − l)× k submatrix B of Z′ has full rank k. Thus, the successful decoding probability of RNCC given in (3.27) turns into Pd = M∑ k=0 N−k∑ l=0 N−l∑ t=0 [(M k )(N l )(N − l t ) φksd(1− φsd)M−kφlrd(1− φrd)N−l (kφsr M )t × ( 1− (kφsr M ))N−l−t ] ×   ∑ δ∈℘M (t) M ! ϕ(δ)C(δ) ∑ δ′∈℘M (t) M ! ϕ(δ′)C(δ′) ( matq(N − l, k, Sˆδ,1, k) ∑k r=0 matq(N − l, k, Sˆδ, r) ) . (3.29) The number of sr link outages, t, can be less than or equal to N − l, as deduced from (3.29). For each t value, the all possible partitions need to be considered in order to 34 calculate the exact decoding probability of RNCC. Instead of calculation of full rank matrices over all possible t values, an upper bound for the decoding failure probability over t ≤ 1 is given as P ufail = 1− M∑ k=0 N−k∑ l=0 [(M k )(N l ) φksd(1− φsd)M−kφlrd(1− φrd)N−l ( 1− (kφsr M ))N−l−1 ] ×    ( 1− kφsrM ) ∑ δ∈℘M (0) M ! ϕ(δ)C(δ) ∑ δ′∈℘M (0) M ! ϕ(δ′)C(δ′)     matq(N − l, k, Sˆδ,1, k) k∑ r=0 matq(N − l, k, Sˆδ, r)     + (0.5)k ∑ δ∈℘M (1) M ! ϕ(δ)C(δ) ∑ δ′∈℘M (0) M ! ϕ(δ′)C(δ′)     matq(N − l, k, Sˆδ,1, k) k∑ r=0 matq(N − l, k, Sˆδ, r)        . (3.30) 3.2.4 Relay operations In this subsection, we investigate the results of relay operations on successful decoding probability in wireless networks. Single relay case is also considered to alleviate the complexity of activating all relays. We also propose a relay selection scheme to use cooperative diversity without using all relay nodes, which is a standard technique in relay-aided systems in wireless networks [88]. If there are multiple link failures of sd pairs, aid of a single relay cannot cover the rank condition at the destination node. The single relay selection scheme provides performance gain for only a single link failure of sd links. We derive the simplified successful decoding probability expressions for a single relay and the single relay selection cases in this subsection. Firstly, we derive the successful decoding probability expression of single relay case (N = 1) which is a commonly used transmission scheduling in wireless networks due to the simplicity of the implementation. The single relay case makes the expressions much simpler. The single relay is only the capable of increasing the rank of Z up to one extra, as expected. Therefore, the successful decoding probability of a single relay case can be defined as Pd = 1∑ k=0 1−k∑ l=0 1−l∑ t=0 [(M k )(kφsr M )t( 1− (kφsr M ))1−l−t φksd(1− φsd)M−kφlrd (1− φrd)1−l ] × ( 1− (1 q )1−l−t )k . (3.31) 35 4 8 16 32 64 128 25610 -5 10-4 10-3 10-2 10-1 100 Figure 3.2 : The decoding failure probability results of RNCC, with respect to changing number of relay nodes, N , and field size, q when M = 2. Secondly, we choose a non-outage relay for the corresponding source node which is in outage of sd link to increase the rank of Z. Successful decoding probability expression of single relay selection scheme can be expressed as Pd = 1∑ k=0 N−k∑ l=0 (M k )(N l ) φksd(1− φsd)M−kφlrd(1− φrd)N−l ×  1− N−l∑ t=0 (N − l t )(kφsr M )t( 1− kφsrM )N−l−t ((1 q )N−l−t )k   . (3.32) 3.3 Numerical Results We give extensive simulation results supporting theoretical results of decoding failure probability of RNCC system with respect to the different system parameters such as q, γ¯sd, γ¯sr, γ¯rd, M , and N . We consider up to 4 source and relay nodes (M,N ∈ {1, 2, 3, 4}) and also investigate the bound in (3.30) by considering M,N ∈ {10, 15}. The target transmission rate, Ru, is equal to 1. 36 4 8 16 32 64 128 256 10 -4 10 -3 10 -2 10 -1 Figure 3.3 : The decoding failure probability results of RNCC, with respect to changing number of source nodes, M , and field size, q, when N = 4. Firstly, we investigate the effect of the field size, q, on the decoding failure probability, Pfail = 1− Pd, calculated through (3.29), considering different number of relay nodes as given in Figure 3.2. The theoretical and simulation results overlap and through this figure, we deduce important outcomes about RNCC performance. For the symmetric scenario, the average SNR values of sd, sr, and rd links are kept equal to 5 and 10 dB (γ¯ = 5, 10 dB), and two source nodes are considered. Setting the SNR of all links the same value, assists evaluating the effects of the number of relay nodes on decoding failure probability. The increase in q results in improved decoding performance for all N values. While the number of relay nodes increases, lower decoding failure probability levels are obtained thanks to the increasing probability of Z being full rank. If γ¯ is set to 10 dB, better failure performances can be obtained over varying q values compared to γ¯ = 5 dB. The other interesting result of this figure is the error floor formed at high q values. The single relay (N = 1) result defines the worst case in relay usage perspective as also shown in this figure. 37 10 -4 0 0 10 -3 10 -2 5 10 -1 5 10 0 10 10 15 15 20 20 10 -5 10 -4 0 10 -3 10 -2 10 -1 5 5 1 0 10 10 15 15 20 20 theoretical simulation Figure 3.4 : The decoding failure probability results of RNCC with respect to average SNR of sd and sr links when q = 8 and γ¯rd = 5 dB. The number of source nodes, M , is an observable design parameter since the required rank of Z to successfully decode the received packets at the destination node is equal to M . The performance results about the number of source nodes on decoding failure probability are shown in Figure 3.3 with fixed number of relay nodes, N = 4. If the system consists of more source nodes, the number of columns of Z increases, meaning that the rank condition of decoding failure probability, M , increases. This situation causes deterioration in decoding failure probability performance. This is consistent with the numerical and simulation results. The best decoding failure probability result is obtained when M = 2 for both γ¯ = 5 dB and γ¯ = 10 dB in this figure. On the other hand, the increasing field size, q, improves decoding performance for all cases due to the increasing probability of Z having full rank. On the other hand, if q is sufficiently large, the performance does not improve much and the error floors can be encountered. The all results of γ¯ = 5 dB and γ¯ = 10 dB also demonstrate that an increase in SNR results in improved decoding performance, as expected. 38 10-4 0 0 10-3 10-2 5 10-1 5 100 10 10 15 15 20 20 theoretical simulation Figure 3.5 : The decoding failure probability results of RNCC with respect to average SNR of sd and sr links when q = 64 and γ¯rd = 5 dB. We assume symmetric channel condition to accurately investigate the impacts of M , N , and q on the decoding failure probability for various schemes in the previous figures. On the other hand, this assumption may not be reasonable for wireless networks with channel impairments. Thus, we provide comprehensive performance results versus different values of γ¯sd, γ¯sr, and γ¯rd in a similar manner in Figures 3.4, 3.5, 3.6, and 3.7. We also explore the results of simultaneous changes in γ¯sd and γ¯sr values in Figure 3.4 and 3.5 for q = 8 and q = 64, respectively. γ¯rd is assumed to be constant and equal to 5 dB. We easily observe that higher γ¯sd value considerably reduces the decoding failure probability compared to small γ¯sd values for constant γ¯sr values as can be inferred from both the figures. For example, in case of γ¯sd = 0 dB and γ¯sr = 0 dB, we get the decoding failure probability of 3 × 10−1, but if γ¯sd = 20 dB and γ¯sr = 0 dB, the decoding failure probability is equal to 1.8 × 10−3. On the contrary, in case of γ¯sd = 0 dB and γ¯sr = 20 dB, the decoding performance improvement is negligible 39 10 -5 10 -4 0 10 -3 10 -2 10 -1 5 5 100 10 10 15 15 20 20 theoretical simulation Figure 3.6 : The decoding failure probability results of RNCC with respect to average SNR of sd and rd links when q = 8 and γ¯sr = 5 dB. compared to the setting when γ¯sd = 0 dB and γ¯sr = 0 dB. This means that, γ¯sd has more impact than γ¯sr on the decoding failure probability. The effects of joint changes in γ¯sd and γ¯rd are taken into account in Figure 3.6 and Figure 3.7 while γ¯sr = 5 dB. The value of q is fixed to 8 and 64, in Figure 3.6 and Figure 3.7, respectively. Both γ¯sd and γ¯rd have important influences on the decoding failure probability which are clearly shown in the figures. If we carefully analyze these figures, γ¯sd has a slightly more impact than γ¯rd and this difference disappears for high values of γ¯sd and γ¯rd. The larger field size decreases decoding failure probability which can be observed from Figure 3.6 and Figure 3.7. The numerical results of the decoding failure probability analysis for high values of M and N when q = 2 and γ¯sr = 20 dB are shown in Figure 3.8. The upper bound, P ufail, defined in (3.30) closely approximates the simulation results as can be observed from the figure. In the case ofM = N = 10, the upper bound provides a tight approximation to the simulation results for both γ¯sd = 0 and γ¯sd = 10 dB. When M = N = 15, the upper bound closely approximates simulation results for only γ¯sd = 0 dB. On the 40 0 10-6 0 10-5 10-4 10-3 5 10-2 10-1 100 5 1010 1515 2020 theoretical simulation Figure 3.7 : The decoding failure probability results of RNCC with respect to average SNR of sd and rd links when q = 64 and γ¯sr = 5 dB. other hand, for γ¯sd = 10 dB, the upper bound of decoding failure probability becomes inadequate as the impact of terms with t ≥ 2 becomes more apparent. The last performance analysis contains the single relay selection case. The decoding failure probability results are obtained versus N values for different γ¯sd values which are illustrated in Figure 3.9. We take the fixed values ofN = 4, q = 4, and γ¯sr = γ¯rd = 15 dB. With increasing number of relay nodes, the decoding performance considerably improves for all the values of γ¯sd. For high γ¯sd values, satisfying the full rank condition is more likely than the low values. Therefore, the decoding performance improvement due to high γ¯sd values is apparent for all N . 3.3.1 Practical implementation results We set up a real-time RNCC testbed to measure decoding failure probability for single relay case (N = 1) with three source nodes (M = 3) as shown in Figure 3.10. RNCC testbed is implemented with 4 NI USRP-2921 software defined radio (SDR) nodes, where three of them are used as source nodes and the fourth node is used as the 41 0 2 4 6 8 10 12 14 16 18 20 10-4 10-3 10-2 10-1 100 simulation theoretical bound Figure 3.8 : The upper theoretical bounds (t ≤ 1) and simulation results of decoding failure probability for q = 2 and γ¯sr = 20 dB over various M, N, and γ¯sd values. destination. The distance between relay and source pairs are equal to 0.5 m while source and destination pairs are equal to 1 m. For relay node, NI PXIe-5644R Vector Signal Transceiver module that can operate in 65 MHz to 6 GHz frequency range and can support 80 MHz instantaneous bandwidth, is utilized. Moreover, NI PXI-6683H timing and synchronization module, which includes a TCXO oscillator, is used as the time synchronization source. All modules are managed via NI PXIe-1082 chassis. LabVIEW is used as the software tool. To satisfy the orthogonality principle of transmissions, OFDMA technique is utilized while quadrature phase shift keying (QPSK) is selected as the modulation scheme at all nodes. The coding coefficients are selected from F4. We obtain the outage probability of transmission links by using pilot symbols as pseudo-noise (PN) sequences [111]. According to this, the received QPSK symbols are demodulated to bits and each bit sequence of the source node is compared with the transmitted bit sequence. With the corresponding input-output configurations, RNCC system is realized by utilizing OFDMA. 42 2 3 4 510-5 10 -4 10 -3 10 -2 10 -1 10 0 simulation theoretical Figure 3.9 : The decoding failure probability results of single relay selection versus N values for varying γ¯sd when M = 4, q = 4, and γ¯sr = γ¯rd = 15 dB. We simplify the expressions by using three types of channel assumption (γ¯sd, γ¯sr, and γ¯rd), also named as symmetric case, in the previous sections. On the other hand, we also observe the results of relaxing this assumption, defined as asymmetric case, for sd links as shown in Figure 3.11 with M = N = 3. Although there is physically a single relay node, it uses OFDMA principle to behave as three relay nodes and transmits three random network coded symbols. In this figure, we investigate both the effects Figure 3.10 : Implementation setup of RNCC. 43 0 2 4 6 8 10 12 14 16 18 2010 -4 10 -3 10 -2 10 -1 100 Figure 3.11 : The decoding failure probability results of real tests with simulations versus the average SNR value of sd links, γ′sd when M = N = 3. of the asymmetric case of sd links and real-time test results. The solid line indicates the symmetric case implying that all sd links has the same SNR, γ¯sid = γ′sd, while the dashed line denotes the results of the asymmetric case with constant 5 dB difference, where γ¯s1d = γ′sd − 5 dB, γ¯s2d = γ′sd dB, and γ¯s3d = γ′sd + 5 dB. γ′sd is the mean value of γ¯s1d, γ¯s2d, and γ¯s3d. The asymmetric case has only a small performance penalty of 1 dB while γ¯′sd = 10 dB compared to the symmetric case. We obtain five distinct measurement sets forming our testbed refer to as Test-M1, Test-M2, Test-M3, Test-M4, and Test-M5. The average SNR of all measurements are given in Table 3.1. We obtain various SNR results of the measurements due to the effect of different transmit gains of source nodes. The test results show that the signal qualities of different links may vary according to the environmental factors. Although SNR values of each sd link are different from each other, the performance results of these cases are very close to the symmetric case, as shown in Figure 3.11. 44 Table 3.1 : Measurement results. Test-M1 Test-M2 Test-M3 Test-M4 Test-M5 Transmit Gain [dB] 6 9 11 16 18 γ¯s1d [dB] 5.9 8.27 8.8 12.8 14.6 γ¯s2d [dB] 6.6 8.87 9.4 13.6 14.3 γ¯s3d [dB] 8.1 9.53 10 13.5 15.4 3.4 Summary and Discussion In this chapter, the extensive decoding failure probability analysis of RNCC is presented for various cooperative transmission schemes in wireless networks. The theoretical decoding failure probability results of RNCC are derived for a generalized multi-source and multi-relay RNCC system. In addition, the results of single relay and single relay selection cases are also presented. The reliability of the derived theoretical results is supported through the extensive simulation results. Both the theoretical and simulation results are compatible with each other that highlight the contribution of the work. The RNCC testbed, which is established with SDR nodes, is also presented. The demonstrated measurement results emphasize the validity of the theoretical results in real world implementations. 45 46 4. WIRELESS CHANNEL INDUCED CODING In the previous chapter, we introduced a generalized performance analyzing tool to compute decoding failure probability of RNCC system. We also continue to focus on relay node perspective for NC system in this chapter. For this purpose, in order to minimize the number of users in outage, an encoding scheme, which is aware of the network topology, is introduced thanks to the unified graph model of multi-source multi-relay system. First of all, the transition of tripartite graph model to bipartite graph model is explained to obtain the unified graph model. Based on the unified graph model, the WiCiC scheme induced by the wireless channel, while the coding coefficients are determined according to CSI, is introduced. The proposed WiCiC scheme also provides the opportunity to operate in binary field. We assume that 1-bit quantized CSI is available at relay nodes, which is a less strict requirement than full CSI knowledge [13]. In the absence of topology awareness, higher field sizes are required to obtain linearly independent codewords because of the wireless channel impairments in RLNC. Due to operating in F2, the decoding process is quite simple compared to high order fields of RLNC. The proposed WiCiC scheme achieves the exact performance of the exhaustive codeword search with considerably reduced complexity. 4.1 System Model The system model consists of a single relay layer as depicted in Figure 3.1. There are M source nodes, N relay nodes, and a single destination node denoted by Si, Rj , and D, respectively for i = 1, 2, . . . ,M and j = 1, 2, . . . , N . The transmission channel coefficient between Si (Rj) and Rj (D) nodes is indicated by hsirj (hrjd). The source packets can be represented as x = [x1, x2, . . . , xM ]T where xi represents the data packet of Si. To transmit source packets, xi, to the destination node, two orthogonal transmission phases, namely the broadcast phase and the relaying phase, are required. In the 47 broadcast phase, source nodes radiate their symbols to relay nodes. The jth relay node uses the detected version of xi, denoted by xˆj,i, to calculate network coded symbols, cj . This process constitutes the relaying phase. Indicating the NC coefficients by αj,i, the coded packet cj is calculated by the following formula cj = αj,1xˆj,1 ⊕ αj,2xˆj,2 ⊕ . . .⊕ αj,M xˆj,M , (4.1) where ⊕ is the summation operator in F2. The encoding coefficients are selected from F2 that form the coding matrix which can be defined as A = [αj,i]N×M . To investigate the effects of wireless channel impairments on the decoding performance, we use 1-bit CSI knowledge, which quantifies channel quality according to the target transmission rate denoted by Ru for link u. For flat fading channels, the decision rule for the outage status of the link u is defined as u′ = { 1, if {log (1 + |u|2γ¯u ) > Ru } 0, otherwise , (4.2) where u ∈ {hsirj , hrjd} and γ¯u indicates the average SNR of the corresponding link. Therefore, the outage status of link u can be determined through the inequality given in (4.2). The CSI knowledge can be considered as a basic topology discovery information which provides insight into the network. Network topology discovery is a necessary condition to realize many tasks for example monitoring, resource management, and routing [112]. There are practical protocols such as simple network management protocol and border gateway protocol to obtain topology information in higher layers of the OSI model [113]. 4.1.1 Conversion of the tripartite network graph to the effective bipartite network graph Graph representation of the networks helps to form the mathematical model of any communication system, currently used for communication problems such as routing and coverage analysis [114] to enhance any defined performance metric or to design a target system. The corresponding tripartite graph model of the considered system model is depicted in Figure 4.1 for M = 2 and N = 3. The tripartite graph denoted by G1 consists of vertices (transmission nodes) and edges (the connections among nodes), expressed as G1 = (V1, E1) where V1 and E1 represent the node set and the set of all possible edges, respectively. Here, the vertex set given as V1 = {S,R,D} is composed 48 S R  R  S  D  h ′ s 1 r 2 h ′ s 1 r 3 h ′ s 2 r 1 h ′ s 2 r 2 h ′ s 2 r 3 h ′ dr 1 h ′ dr 2 h ′ dr 3 R  h ′ s 1 r 1 Figure 4.1 : An example of tripartite graph model of the network given in Figure 3.1 when M = 2 and N = 3. of three subsets as S,R, and D and they represent source nodes set, relay nodes set, and destination node set, respectively. The cardinality of the subsets of V1 is calculated as |S| = M , |R| = N , and |D| = 1. The straight line and the dotted line indicate the availability of the sr and rd link, respectively, in Figure 4.1. To establish a connection between a source node and the destination node, at least one corresponding sr link must be available and this relay must have a connection with the destination node. The binary channel-state matrices can be constituted by using u′({h′sirj , h′rjd}) values, where the channel-state matrix between source and relay nodes is represented by H = [ h′sirj ] N×M while the channel-state vector between D and all relay nodes is denoted by g = [h′r1d, . . . , h′rNd ]. The diagonal matrix, G, of size N × N , is generated as G = diag(g) where diag(.) constitutes the diagonal matrix of the input vector. The vector notation of the received signals at the destination node can also be expressed as y = G (H A)x, (4.3) where represents the element-wise (Hadamard) product. Based on the wireless transmission channels, the induced coding matrix is defined as ∆ = G (H A). Here, (G(H A))ij = gi(HijAij) is also equal to ((GH) A)ij = (giHij)Aij thanks to the diagonal form of G. Therefore, ∆ can be alternatively expressed as ∆ = (GH) A by using this property. Here, the channel-state matrices, G and H, represent the two layers of the tripartite network graph. We define the composite channel-state matrix expressed as Θ = GH. 49 S S D ̃ 1 D ̃ 2 D ̃ 3 h ′ s 1 r 1 h ′ d r 1 h ′ s 1 r 2 h ′ d r 2 h ′ s h ′ d r 3 h ′ s 2 r 1 h ′ d r 2 h ′ s 2 r 2 h ′ d r 1 h ′ s 2 r 3 h ′ d r 3 h ′ ds 2 r 2 h ′ ds 2 r 3 h ′ ds 1 r 2 h ′ ds 1 r 1 h ′ ds 2 r 1 h ′ ds 1 r 3 1 r 3 Figure 4.2 : The effective bipartite graph model of the corresponding tripartite graph. The graph representation of Θ provides additional insight to determine optimum network code coefficients. There are two channel-state matrices for the tripartite network graph. On the other hand, Θ indicates the composite channel-state matrix representing the effective bipartite network graph of the corresponding tripartite network graph. The effective bipartite graph is denoted as G2 = (V2, E2) where V2 = {S, D˜} as depicted in Figure 4.2. Here, the size of Θ (N × M ) determines the cardinality of the two vertex sets, S and D˜ = {D˜1, . . . , D˜N}, with |S| = M and |D˜| = N . The outage status of the edges of G2 can be determined by the following expression h′sirjd = h ′ sirj ⊗ h′rjd (4.4) where ⊗ denotes the multiplication operator in F2. Therefore, the composite channel-state matrix, Θ is made up of h′sirjd. Accordingly, we can obtain the entries of Θ by using h′sirj and h′rjd. To compromise the encoding matrix, A, Θ is utilized in the next section. For the decoding process, the Gaussian elimination method can be used to obtain source packets (x) at the destination node. At least M linear independent coded symbols are required to correctly decode the received coded symbols (y). In other words, it is necessary that ∆ have full rank to obtain the source signals. Therefore, the decoding failure probability, represented by Pfail, can be defined as Pfail := Pr{rank(∆) < M}. (4.5) 50 Algorithm 4.1: Wireless Channel Induced Coding (WiCiC) 1 A = ( 0 ) N×M 2 Calculate the composite channel-state matrix, Θ = GH 3 Randomly rotate the rows and columns of Θ. The new composite channel matrix is indicated by Θ′. 4 Run the Ford-Fulkerson algorithm by utilizing Θ′ as the input [4] //Mc denotes the output of the Ford-Fulkerson algorithm 5 i← 1,M , repeat ifMc(j∗, i) == 1, A′(:, i) =  1 1 . . . 1︸ ︷︷ ︸ j∗ terms N − j∗ terms ︷ ︸︸ ︷ 0 0 . . . 0   T 1×N else A′(:, i) = [0 0 . . . 0]T1×N 6 Map A′ to A by considering the initial indices of Θ The vector notation of the NC system given in (4.3) determines the decoding performance which depends not only on the selection of network code matrix (A) but also on the channel matrices, G and H. MDS or other maximum rank distance codes give the coding matrix with maximum rank according toM andN . On the other hand, the optimality of the selected code is not valid for dynamic network topologies without using the channel matrices, G and H. Therefore, in the presence of a different topology, the optimum decoding performance of NC system cannot be achieved by the selection of the optimum codes such as MDS or other maximum rank distance codes that satisfy the Singleton bound. Furthermore, RLNC also does not guarantee optimum decoding performance. For this purpose, here, we propose a code design algorithm to enhance the NC system performance in wireless networks. 4.2 Wireless Channel Induced Coding Solution To achieve the optimum performance results for an NC system, we need to maximize rank of ∆ expressed as max A [rank (∆)] through determining coding matrix, A. This expression can be formulated as A∗ = arg max A [rank ((GH) A)] , (4.6) where A∗ represents the optimum solution and rmax = max A [rank ((GH) A)]. We obtain the optimum A regarding G and H to satisfy (4.6) by using the Algorithm 4.1 to determine encoding coefficients at relay nodes. The proposed algorithm uses Θ, composite channel matrix previously expressed as Θ = GH, as the input. The 51 graph representation of Θ is depicted in Figure 4.2. Determining optimum network code coefficients in F2 is the equivalent problem of maximum bipartite matching to minimize the decoding failure probability. The maximum bipartite matching can be obtained by converting the code design problem to the maximum flow problem. The steps of the algorithm are explained in detail as follows. After calculating Θ in Step 2, we obtain Θ′ by randomly rotating the rows and columns of Θ to ensure user fairness among source and relay nodes in Step 3. The Ford-Fulkerson method is used to find the maximum flow given in Step 4. The output of the Ford-Fulkerson method, the matching matrix indicated byMc has the maximum of one non-zero entry in all columns and rows. Based onMc, Step 5 is used to increase the weight of the encoding matrix to increase the number of packets to be mixed at the relay nodes. The non-zero entry of ith column ofMc indicated by Mc(j∗, i) is determined in Step 5, where j∗ represents the associated row index. Then, the ith column of coding matrix, A′, is determined. If there is no non-zero entries in column i, the corresponding column is constituted as all zeros vector. Step 5 is repeated until i = M . In Step 6, we attain A by the reversion of the matrix rotation operation in Step 3. Proposition 4.1. The optimum solution of (4.6), A∗, can be obtained by using the proposed Algorithm 4.1 by making use of the max-flow min-cut theorem where the rank of ∆ is equal to rmax [4]. Proof. Since the Ford-Fulkerson method guarantees the maximum flow of a given network, it can be used to determine the network code coefficients. The flow network version of the corresponding bipartite graph is used to solve the maximum flow problem. Steps 3, 5, and 6 consist of the elementary column and row operations, therefore they do not change the rank of ∆. The approach is optimal in the aspect of end-to-end link availability due to considering both sr channel matrix (H) and rd diagonalized channel matrix (G). 4.3 Numerical Results In this section, extensive simulation results of the proposed algorithm are presented by providing the results of conventional coding schemes for Rayleigh block fading 52 0 2 4 6 8 10 12 14 16 18 2010 -5 10 -4 10 -3 10 -2 10 -1 100 Figure 4.3 : The decoding failure probability results of various algorithms presented using symmetric SNR case when γ¯u = γ¯, ∀ u and M = 4, N = 7. channels where hu ∼ CN (0, 1). The target transmission rate, Ru, is equal to 1. Figure 4.3 provides a performance comparison of the proposed algorithm with the state-of-the-art solutions where M = 4 and N = 7. In this figure, we investigate symmetric SNR case when γ¯u = γ¯, ∀ u. We compare the proposed WiCiC scheme with a GM-MDS code [21] and RLNC with various q values, and the exhaustive search. Among these codes, RLNC at F2 has the worst decoding performance. RLNC has error floors at high SNR for q = 2, 4, and 16, as expected. To obtain a similar decoding performance of WiCiC scheme, RLNC needs to operate in F256. In addition, GM-MDS code provide worse decoding performance than WiCiC. WiCiC achieves the same decoding failure probability of the exhaustive search, as the optimum result. We also investigate the importance of individual H (G) matrix on the decoding performance of WiCiC by considering fully connected rd links (sr links). For the first scheme (fully connected rd links), called AS1, γ¯u → ∞, u ∈ hrjd and γ¯v = γ¯, v ∈ hsirj , are defined. The numerical results of this case are given in Figure 4.4. The whole techniques have better decoding performance in theAS1 scheme given 53 0 2 4 6 8 10 12 14 16 18 2010 -5 10 -4 10 -3 10 -2 10 -1 100 Figure 4.4 : The decoding failure probability results of various algorithms presented using AS1 case where γ¯u →∞, u ∈ hrjd, γ¯u = γ¯, u ∈ hsirj and AS2 case where γ¯u →∞, u ∈ hsirj , γ¯u = γ¯, u ∈ hrjd for M = 4, N = 7. in Figure 4.4 compared to the results shown in Figure 4.3, as expected. On the other hand, for RLNC, it still requires operations over higher values of q to achieve a closer performance to that of the WiCiC scheme. The second scheme is AS2 case (fully connected sr links) where γ¯u → ∞, u ∈ hsirj and γ¯v = γ¯, v ∈ hrjd. There are only rd link outages assuming that the qualities of sr links are perfect. On the other hand, GM-MDS code has the same decoding performance with the proposed scheme requiring higher field sizes (for M = 4, N = 7, and q ≥ 10) for the AS2 case. The performance results of AS2 scheme are almost equal to the symmetric SNR case results presented in Figure 4.3 due to having less effect of sr links compared to rd links on the decoding performance. In Figure 4.5, the effect of the number of relay nodes on the decoding performance is examined in the symmetric structure. We fix the number of source nodes as M = 4. An increase in N improves the decoding performance of the WiCiC, GM-MDS, and exhaustive search schemes, as expected. It can also be deduced that the WiCiC has approximately 1.2 dB better performance at 10−3 level for all conditions. 54 0 2 4 6 8 10 12 14 16 18 10 -4 10 -3 10 -2 10 -1 100 Figure 4.5 : The decoding failure probability results of various algorithms presented using symmetric SNR case for varying N values when M = 4. 4.4 Summary and Discussion In this chapter, we present an encoding algorithm induced by the wireless channel, WiCiC, which is based on the maximum flow concept in relay-aided networks different from conventional network-code selection procedures that also provides optimal decoding performance. We propose a transition from tripartite graph model to its effective bipartite graph model to realize maximum flow. The complexity analysis of the proposed algorithm is evaluated from the encoding and decoding perspectives. The proposed algorithm demonstrates superiority from both encoding and decoding complexity viewpoints compared to previously known schemes. WiCiC scheme is easily implementable at low-capability devices and also achieves lower decoding complexity than RLNC operating in higher fields at similar performance levels. Our proposed scheme has practical applicability owing to its possibilities operating at higher layers, and therefore it can be easily implemented in present communication standards like Wi-Fi and Zigbee. 55 56 5. NCC-OFDMA SYSTEM Chapter 3 and Chapter 4 mainly focus on the efficient usage of relay nodes and the improvement of decoding failure performance of NC/RLNC. In this chapter, the major aim is to demonstrate efficient utilization of bandwidth and power resources. For this purpose, we firstly propose a joint power and subcarrier allocation algorithm for OFDMA systems by considering user fairness in Section 5.1. Then, the OFDMA extension of NCC systems referred to as NCC-OFDMA, which is used as the multiple access scheme, is presented with the proposed detector and relay selection rule in Section 5.2. In the first part of this chapter, the optimization problem of joint power and subcarrier allocation is defined. We then prove that the problem can be turned into an assignment problem in a randomly weighted complete bipartite graph, and show that the Hungarian method (Hungarian method is also known as Kuhn-Munkres algorithm [115, 116].) based matching approach which provides the optimal assignment. However, Hungarian method is a primal dual algorithm that solves linear sum assignment problems in polynomial time via linear programming and in combinatorial optimization [115], proven to be strongly polynomial [116]. Different from waterfilling-based power allocation approaches including [23–28], we consider controlled rate allocation among users in this work. Comparative simulation results demonstrate that the power savings can be achieved with both proposed joint subcarrier and power allocation algorithms according to [33]. In the second part of this chapter, we use OFDMA technique which provides frequency diversity ensuring orthogonality among users for NCC systems. The decoding failure probability results of single relay selection scheme for NCC-OFDMA system are given with diversity gain results. In the literature, NCC systems are generally designed by using TDMA scheme [8, 117]. Contrary to TDMA, OFDMA is the commonly used 57 multiplexing technique in wireless communications. The OFDMA extension of NCC is also investigated as a resource scaling technique in NCC systems [118]. 5.1 Joint Subcarrier and Power Allocation in OFDMA Systems for Outage Minimization Due to the fact that joint subcarrier and power allocation technique can further increase the power savings while minimizing the number of outage subcarriers, each subcarrier is assigned to a single user (i.e., minimizing the outage probability). In this section, we propose two joint subcarrier and power allocation algorithms based on Hungarian method. While the first algorithm provides the optimal solution, the second algorithm promises reduced computational complexity and its corresponding performance approaches to the optimal solution at high SNR region. As per main contribution, the proposed optimization problem addresses the minimizing the number of outage subcarriers problem in downlink OFDMA systems through assigning multiple rates per user while minimizing the total power utilizing a randomly weighted complete bipartite graph model. Equal rate condition is considered for all subcarriers in order to simplify the frame structure for high-level functionalities. 5.1.1 Joint optimization approaches We consider a downlink OFDMA system comprising of a single base station (BS), M mobile users, and ℵ subcarriers. We assume that the channel gains are available at the BS that allocates the subcarriers. There are more subcarriers than mobile users in the network, i.e. ℵ ≥ M , which is a valid assumption for practical network deployment scenarios. ℵc represents the number of subcarriers in each coherence bandwidth with ℵc = ℵ/L, where L denotes the total number of coherence bandwidths in the frequency-selective channel. Furthermore, we assume that the subcarriers locating in the same coherence bandwidth have equal channel gains, and the channel gains of subcarriers locating in different coherence bandwidths are independent [119]. Each subcarrier in all coherence bandwidth can be assigned to only one user. Target transmission rate per subcarrier, Rs, is adjusted as the same. Therefore, distinct user rates can be enabled by performing power allocation with respect to each channel gain. Data rate of each user can be differentiated owing to assigning a different number 58 of subcarriers. Target data rate of Ri = κiRs can be achieved through allocating κi non-outage subcarriers, to user Ui for i = 1, 2, . . . ,M , where the summation of all κi should be lower than or equal to ℵ. The outage probability of subcarrier, ξn, (n = 1, 2, . . . ,ℵ) for user Ui, can be calculated as [33] ps = Pr { 1 ℵc log ( 1 + |Hi,n| 2Pi,n σ2w ) < Rs } , (5.1) where Hi,n and Pi,n represent the channel gain and the allocated power of ξn for Ui, respectively. σ2w stands for the variance of AWGN component. The equal channel gain assumption in the same coherence bandwidth leads to decreased channel capacity by ℵc [33, 119]. We consider Rayleigh block fading channel model with mean zero and unit variance for all communication links. The outage probability of a subcarrier in this channel can be formulated as ps = 1− exp ( −σ 2 w ( 2ℵcRs − 1 ) Pi,n ) . (5.2) ξn is not in outage for Ui if and only if the following condition Pi,n|Hi,n|2 ≥ σ2w ( 2ℵcRs − 1 ) (5.3) holds. In this problem, we aim to minimize the number of outage subcarriers. Using Theorem 2 defined in [33] for the subcarriers with same data rate requirement, the number of outage subcarriers can be minimized by maximum cardinality matching approach. This corresponds to the assignment of the same rate to all subcarriers. ith user needs κi non-outage subcarriers in order to avoid outage status, while minimizing the outage probability. On the other hand, if less than κi subcarriers are assigned to a particular user, the corresponding user undergoes outage. The minimum required power level for ξn to be used by Ui, while ensuring reliable transmission in the network becomes Pi,n ≥ σ2w ( 2ℵcRs − 1 ) |Hi,n|2 = PLi,n. (5.4) Considering the fact that Pi,n = PLi,n is the minimum possible transmit power for Ui corresponding to the subcarrier ξn, ∀ i, and n (providing a complete graph). The subcarrier allocation problem that minimizes the total transmit power while assigning 59 κi subcarriers to Ui turns into min M∑ i=1 ℵ∑ n=1 µi,nPLi,n (5.5a) s.t. ℵ∑ n=1 µi,nPLi,n ≤ PT ∀i = 1, . . . ,M (5.5b) ∑ n µi,n = κi (5.5c) M∑ i=1 κi ≤ ℵ (5.5d) M∑ i=1 µi,n = 1, ∀n = 1, . . . ,ℵ, (5.5e) where µi,n denotes the indicator function regarding the assignment of ξn to Ui. It is expressed as µi,n = { 1, ξn ∈ Ξi 0, otherwise , (5.6) where the subcarrier set Ξi = {ξi1 , ξi2 , . . . , ξiκi} is assigned to Ui for {i1 6= i2 6= . . . 6= iκi} ∈ {1, 2, . . . ,ℵ}. PT , represented in the constraint (5.5b), denotes the total transmit power budget at BS. The constraint in (5.5c) enforces assignment of κi subcarriers to Ui, i.e., |Ξi|= κi. The number of total assigned subcarriers cannot exceed ℵ given in (5.5d). The final constraint (5.5e) describes the condition of assignment of each subcarrier to only one user, which can also be expressed as Ξi ∩ Ξi′ = ∅, if i 6= i′ where i and i′ ∈ {1, 2, . . . ,M}. Note that fairness among users can be enabled by keeping κi the same for all users. 5.1.2 The proposed algorithms Proposition 5.1. The joint subcarrier and power optimization problem defined in (5.5) is a generalized assignment problem over a domain of weighted elements given in (5.5a). It can be solved optimally through the use of Hungarian method considering all user subsets with a computational complexity of O(2Mℵ3). Proof. This system can be modeled as a randomly weighted complete bipartite graph denoted by G = (U ,Ξ, E). The disjoint and independent user and subcarrier sets are represented by U = {U1,U2, . . . ,UM} and Ξ = {ξ1, ξ2, . . . , ξℵ}, respectively. An 60 Algorithm 5.1: Joint Power and Subcarrier Assignment Algorithm Based on Hungarian Method 1 Determine PLi,n values according to (5.4). 2 Expand ith user by κi through vertex expansion in bipartite graphs 3 Run Hungarian method [115, 116] for assignment of subcarriers. // G defines the input of Hungarian method. //Mc denotes the output of the Hungarian technique defined as matching. 4 sort Pi := κi∑ i=1 PLi,n in descending order. 5 U ′ = ∅ andM∗c =Mc 6 for i← 1,M , do 7 repeat 8 if ∑ Ui ∈ {U\U ′} Pi > PT then 9 U ′ = U ′ ∪ {Ui} 10 M∗c =Mc \Mc(U ′) 11 until ∑ Ui ∈ {U\U ′} Pi ≤ PT 12 // OutputM∗c then stop. edge connects user Ui in U to subcarrier ξn in Ξ with a minimum cost of PLi,n. E indicates the set of all possible edges, where |E| = M ×ℵ. A matchingMc is a subset of edges in G andMc ⊆ E . Using the minimum possible power constraint, the optimization problem defined in (5.5) can be converted to a linear sum assignment problem via expanding Ui by κi in this setup. The use of Hungarian method determines the maximum assignment with optimal (minimum) cost by iterating over the elements of U [115, 116]. The computational complexity of Hungarian method is O(ℵ3) [116]. The power constraint in (5.5b) is considered to determine the optimal solution of (5.5), also named as HM-OPT. We use 2M subsets of U exhaustively for a worst case computational complexity of O(2Mℵ3). Therefore, the minimum cost of perfect matching, which is stated in other words as the minimum total transmit power, is provided. We propose a reduced complexity approach as a second algorithm based on a single execution of the Hungarian method to overcome the high complexity introduced through the use of the optimal solution described above. Note that for this case, the solution may not always be feasible because of the total power constraint defined in (5.5b). The proposed algorithm, HM-RC, detailed in Algorithm 5.1, has a complexity 61 of O(ℵ3). The cost of edge between Ui and ξn is equal to PLi,n. Ui is expanded by κi in order to use the Hungarian method given in Step 2 of the proposed algorithm. Step 3 in Algorithm 5.1 runs the Hungarian method targeting the minimization of the total cost of matchingMc. The Hungarian method calculates the minimum cost perfect matching in bipartite graphs [115, 116]. In order to determine the minimum cost of G, the cost of ith user and nth subcarrier is represented by PLi,n. PLi,n values are considered as the inputs of the Hungarian method. After O(ℵ3) mathematical operations, the Hungarian method provides theMc as an output. AlthoughMc defines the subcarrier assignments, we need to check whether power constraint is satisfied or not. If κi∑ n=1 µi,n PLi,n ≤ PT holds, the perfect matching is achieved. Moreover, there are no outage users by the assignmentMc. Otherwise, when the power constraint is not satisfied, it is possible to remove the user(s) with maximum transmission power(s) until the total power does not exceed the limit, PT (Steps 4 to 11 in Algorithm 5.1). These steps define the essential components of the algorithm that guarantee the power constraint in (5b). Following the determination of outage user(s), the reduced version of theMc is denoted byM∗c . After the assignment of power and subcarriers according to PLi,n values, in case of Ui is in outage, ψi = 1, otherwise ψi = 0. The outage probability of the system can be determined as Pout = E [ψi]/M , where E[·] expresses the expectation operator. 5.1.3 Numerical results We conduct extensive simulations using various system parameters to analyze and to compare the performances of three approaches called the optimal solution algorithm having complexity of O(2Mℵ3), referred to as HM-OPT, the reduced complexity approach having complexity of O(ℵ3), referred to as HM-RC, and the benchmark work R2EHK of [33] with a lower complexity of O(ℵ2/3). We consider M = {4, 16} users and ℵ = {8, 128} subcarriers. Transmit power budget is selected as Pt = ℵ. The effects of varying number of coherence bandwidths (L), and varying target transmission rates (Ri = R′) on the outage probability and transmit power are investigated. The comparison of outage probability and power usage performances of these methods is given in Figure 5.1 (a) and (b), respectively, for varying transmission rates. Highly correlated subcarriers with L = 2 are taken into 62 0 5 10 15 20 25 3010 -5 10 -4 10 -3 10 -2 10 -1 100 (a) 0 5 10 15 20 25 30 0 1 2 3 4 5 6 7 8 (b) Figure 5.1 : (a) Outage probability results of the methods versus noise regime, (b) Total transmit power (TTP) and total excess power (TEP) results of the methods versus noise regime. 63 account subject to 1/σ2w. The proposed HM-RC method gives around 4 dB better outage probability performance than the reference algorithm R2EHK [33], while requiring lower transmission power by the utilization of the weighted graph forM = 4 and ℵ = 8. HM-RC performance attains the optimal solution of HM-OPT for high 1/σ2w values. The main reason is that in the HM-RC, the single realization of the Hungarian method is sufficient to achieve the optimal solution, corresponding to the HM-OPT solution in high 1/σ2w regime. However, reaching the optimal solution in the first run of the Hungarian algorithm may not be possible for low 1/σ2w values and distinct user subsets should be considered to attain the optimum performance. In such a case, HM-RC cannot approach to the optimal solution and the corresponding performances of the algorithms diverge. HM-OPT provides only slightly better performance for 1/σ2w values that are lower than 5 dB compared to HM-RC. Notice that the HM-RC algorithm can also achieve the optimal diversity gain, as can be observed from simulation results. The decrease in the variance of noise power improves the outage performance of both benchmark and the proposed algorithms. The transmit power of the benchmark scheme increases up to the power budget with improved outage performance because of the utilization of fixed transmit powers. The required transmission powers of the proposed Hungarian-OPT and Hungarian-RC algorithms, whose bounds are defined in (5b), decrease with noise power variance. Thus, transmission powers of these schemes become very small, asymptotically converging to zero for infinite values of 1/σ2w. The effect of transmission rate on outage probability and power consumption with L = 8 is illustrated in Figure 5.2. We extend the numerical experiments to various transmission rates, Ri = R′. Increasing transmission rate results in requiring more transmission power, therefore the outage probability increases for all algorithms. The outage probability of the system decreases with increased transmission rate for all algorithms. R2EHK presents the worst outage probability performance for all transmission rates. At the same time, HM-OPT provides a negligible performance gain compared to HM-RC for all transmission rates in the noise restricted region. 64 0 5 10 15 20 2510 -4 10 -3 10 -2 10 -1 100 (a) 0 5 10 15 20 25 300 1 2 3 4 5 6 7 8 (b) Figure 5.2 : (a) Outage probability results of the methods according to different Ri = R′ values versus noise regime when M = 4, ℵ = 8, and L = 8, (b) TTP and TEP results of the methods according to different R values versus noise regime when M = 4, ℵ = 8, and L = 8. 65 The effects of varying L can be shown with transmission rate Ri = R′ = 2 in Figure 5.3. It can be seen that the subcarriers are highly correlated for L < N . If the subcarriers are highly correlated when L = 2 or L = 4, the outage performance is worse than the uncorrelated case when L = 8 with ℵ = 8 for all algorithms. The proposed algorithms obtain the best outage probability performance for all L values, compared to R2EHK. The proposed methods guarantee more power savings at all noise regions than R2EHK methods with different L values. The outage probability difference of HM-OPT is negligible compared to HM-RC, if the computational complexity is considered as a constraint. In addition, HM-RC gives better outage performance with substantial power savings compared to the R2EHK algorithm. 5.2 Single Relay Selection Scheme for NCC-OFDMA System In the second part of this chapter, a single relay selection scheme based on min-max relay selection criterion for NCC-OFDMA system is presented with theoretical results. NCC systems using TDMA strategy are generally planned for multiple users. To exploit frequency diversity gain while ensuring orthogonality among multiple users, OFDMA technique is considered for multiple access for NCC systems, referred to as NCC-OFDMA. 5.2.1 OFDMA extension of network coded cooperation The NCC-OFDMA system has M source nodes, N relay nodes, and one destination node. The considered NCC model is depicted in Fig 3.1. The total number of subcarriers is denoted by ℵ, satisfying the condition ℵ > {M, N}. This assumption is realistic since the number of subcarriers is usually more than the number of source and relay nodes. The number of coherence bandwidths of the NCC-OFDMA system, indicated by L, may be smaller than ℵ if the channel is frequency-selective. The transmission process of the NCC-OFDMA system is also completed in two orthogonal phases, broadcast and relaying phases. In the broadcast phase, source nodes radiate their symbols through the wireless channel. Due to the broadcast nature of the wireless channel, the source symbols can be overheard by the relay nodes and the destination node. The SNR values of sr links are assumed to be higher than those of sd links, thus the subcarrier assignment is carried out based on the qualities of sd links. The relaying 66 0 5 10 15 20 25 3010 -4 10 -3 10 -2 10 -1 100 (a) 0 5 10 15 20 25 300 1 2 3 4 5 6 7 8 (b) Figure 5.3 : a) Outage probability results of the methods according to different L values versus noise regime for M = 4, ℵ = 8, and Ri = R′ = 2, (b) TTP and TEP results of the methods according to different L values versus noise regime for M = 4, ℵ = 8, and Ri = R′ = 2. 67 phase follows the broadcast phase. In a single relay selection system, one relay is selected to transmit the combined symbols, referred to as network coded symbols, by using either MDS codes or RLNC. At the end of the two phases, the destination node comprises of source and network coded symbols that are transmitted from the source and relay nodes. Let the frequency domain representation of the nth subcarrier channel gain of link u be given by Hu[n], where u ∈ {sid, sirj, rjd}, i = 1, 2, . . . ,M, j = 1, 2, . . . , N , and n = 1, 2, . . . ,ℵ. It is assumed that Hu[n] has Rayleigh distribution. The received symbols at the j th relay node and destination node in the broadcast phase are expressed as Ysid[n] =Hsid[n]X˜i[n] +Wsid[n] Ysirj [n] =Hsirj [n]X˜i[n] +Wsirj [n], (5.7) where each symbol, X˜i[n], the modulated version of source signal,Xi[n], is transmitted at unit power. The AWGN at the jth relay node and the destination node in the broadcast phase are denoted by Wsirj [n] and Wsirj [n], respectively. The jth relay node detects Xi[n] by using Ysirj [n]. Xˆj,i[n] denotes the detected version of Xi[n] at Rj in the broadcast phase. Then, the selected relay node generates the network coded symbol by first multiplying each Xi[n] by a network coefficient αj,i and then summation of the M multiplications. The coefficients are selected either from an MDS code satisfying the Singleton bound or randomly selected from Fq as in RLNC with sufficiently large q. The network coded symbol of the jth relay node can be calculated as Cj[n] = M∑ i=1 αj,iXˆj,i[n]. (5.8) The received symbol at the destination node in the relaying phase equals to Yrjd[n] = Hrjd[n]Cj[n] +Wrjd[n], (5.9) where Wrjd[n] indicates the AWGN component. Therefore, the destination node contains multiple symbols. The transmission is realized by OFDMA in both phases. The subcarrier selection process is critical to improve the NCC-OFDMA system performance. The R2EHK algorithm, which is used to allocate the subcarriers [33], can achieve the optimal outage probability while providing fairness between all nodes. It exploits both frequency and 68 multiuser diversity and provides the minimum outage probability in OFDMA systems, while providing the diversity gain of L under the condition of L < M ≤ ℵ [33]. Thus, each link has L number of independent transmission channels. In the relaying phase, a single relay is chosen according to Hsirj [n] and Hrjd[n] values, as detailed in the next subsection. 5.2.2 Decoding failure probability analysis of NCC-OFDMA-SRS Before calculating the decoding failure probability of NCC-OFDMA-SRS, it is necessary to calculate the outage probability per link. The outage probability of transmission link ul in the system can be determined as φlu = Pr{log{1 + ∣ ∣H lu[n] ∣ ∣2γ¯lu} < R′}, (5.10) for l = 1, 2, . . . , L, where γ¯lu and R′ denote the average SNR of link ul and target transmission rate of the system, respectively. The instantaneous SNR of link ul is equal to γlu = ∣ ∣H lu[n] ∣ ∣2γ¯lu. And then, φlu can be calculated as φlu = Pr {∣ ∣H lu[n] ∣ ∣2 < γthγ¯lu } , (5.11) where γth = 2R′ − 1. Assuming all channel gains have Rayleigh distribution in the system, the expression in (5.11) becomes φlu = 1− exp ( −γthγ¯lu ) , (5.12) Accordingly, the overall decoding probability can be derived if the outage probability of each link is first calculated. 5.2.3 Min-max single relay selection rule The optimum relay selection rule for NC is the selection of the best relay having the highest SNR link for each source node [120]. However, this selection rule leads to the inefficient use of scarce bandwidth. There is another relay selection technique called min-max relay selection, which aims at maximizing the worst end-to-end (source-to-relay-to-destination) SNR. In [120], the min-max criterion for relay selection gives the optimal performance for NC. Therefore, min-max relay selection criterion is preferred in single-relay selection schemes to maximize the decoding probability of NCC. 69 Before detailing the steps of min-max relay selection, the conceptual variables are defined. The performance of a source-to-relay-to-destination link is dominated by the weakest SNR link. Thus, the reliability of a relay node is determined by the worst SNR of all links that are connected to the relay node. The weakest SNR value of all relay nodes can be determined through the following expression γj = min { . . . , γlsirj , . . . , γ 1 rjd, . . . , γ L rjd } , (5.13) which considers coherence bandwidths. Therefore, there are (M + 1)L different independent SNR values to select each relay node. Through the independent terms in (5.13), the outage probability of the jth relay is written as φγj = 1− exp ( −γthγ¯j ) , (5.14) where γ¯j represents the average value of γj and can be computed as [120] γ¯j = 1 ∑L l=1 ( ∑M i=1 1 γ¯lsirj + 1γ¯lrjd ) . (5.15) Accordingly, the SNR value of the selected relay is defined as γsrs = max{γ1, γ2, . . . , γM}. (5.16) Due to the mutually independent terms of γj , the outage probability of single relay selection can be calculated as φsrs = N∏ j=1 φγj . (5.17) 5.2.4 Decoding failure probability analysis of NCC-OFDMA-SRS At the end of the two phases, the destination node gathers distinct symbols, which can be decoded only if M of them are linearly independent. Therefore, at least M links should be in non-outage out of the M + 1 available links provided that only one relay is selected. Otherwise, the destination node cannot decode the source symbols correctly. By using the success probability, the average decoding failure probability of the NCC-OFDMA-SRS system is calculated as Pfail = 1− (Pr{M links > γth}+ Pr{M + 1 links > γth}) . (5.18) 70 Considering all transmission links in the system, Pfail can be calculated as Pfail = 1− [Pr{M sd links > γth}+ Pr{M − 1 sd links > γth, γsrs > γth}] . (5.19) Theorem 5.1 Consider an NCC-OFDMA system that consists of M source nodes, N relay nodes, and a single destination node where OFDMA uses ℵ subcarriers. If the min-max SRS scheme is employed, the asymptotic decoding failure probability of the NCC-OFDMA-SRS system can be approximated by P asymfail ≈ M∑ i1=1, i2=1, i1 6=i2 γ¯2Lth γ¯Lsi1d γ¯ L si2d . (5.20) The theorem states that the diversity gain of NCC-OFDMA-SRS system, which is independent of the values of M and N , is equal to 2L. Proof. Using (5.19), the decoding failure probability of NCC-OFDMA-SRS system is given by Pfail =1− [Pr{M sd links > γth}+ Pr{M − 1 sd links > γth, γsrs > γth}] = Pr{0 sd link > γth}+ . . .+ Pr{M − 2 sd links > γth}+ Pr{M − 1 sd links > γth, γsrs < γth} ≈ ( M∏ i=1 φLγsid + M∑ i=1 (( 1− φLγsid ) M∏ i′=1 i′ 6=i φLγsi′d ) + . . .+ M∑ i1=1,...,iM−2=1 i1 6=... 6=iM−2 I={i1,...,iM−2} (∏ ∀i∈I ( 1− φLγsid ) M∏ i′=1 i′ 6∈I φLγsi′d ) + M∑ i1=1,...,iM−1=1 i1 6=... 6=iM−1 I={i1,...,iM−1} (∏ ∀i∈I ( 1− φLγsid ) M∏ i′=1 i′ 6∈I φLγsi′d ) φLsrs ) /M, = ( M−2∑ k=0 ( M∑ i1=1,...,ik=1 i1 6=... 6=ik I={i1,...,ik} ∏ ∀i∈I (1− φLsid) M∏ i′=1 i′ 6∈I φLγsi′d ) + M∑ i1=1,...,iM−1=1 i1 6=... 6=iM−1 I={i1,...,iM−1} (∏ ∀i∈I ( 1− φLγsid ) M∏ i′=1 i′ 6∈I φLγsi′d ) φLsrs ) /M (5.21) by using the first order approximation of the theoretical outage probability of R2EHK algorithm given in (14) of [33]. The diversity gain of a communication system is calculated when SNR → ∞. In order to investigate the asymptotic performance and find the diversity gain of NCC-OFDMA-SRS system, we focus only on the dominant terms of Pfail. In the high SNR region, (5.21) is dominated by the first term in the summation. Therefore, (5.21) is approximately equal to P asymfail ≈ M−2∑ k=0 ( M∑ i1=1,...,ik=1 i1 6=... 6=ik I={i1,...,ik} ∏ ∀i∈I (1− φLsid) M∏ i′=1 i′ 6∈I φLγsi′d ) . (5.22) 71 This expression is dominated by the last term of the summation. Thus, it can be further reduced to P asymfail ≈ M∑ i1=1,...,iM−2=1 i1 6=... 6=iM−2 I={i1,...,iM−2} ( ∏ ∀i∈I (1− φLsid) M∏ i′=1 i′ 6∈I φLγsi′d ) . (5.23) If the dominant terms are kept to find the diversity gain, the expression in (5.23) becomes P asymfail ≈ M∑ i1=1,...,iM−2=1 i1 6=... 6=iM−2 I={i1,...,iM−2} ( M∏ i′=1 i′ 6∈I φLγs′id ) . (5.24) Using the first-order Taylor approximation, e−x ≈ 1−x, expression (5.20) is obtained. Thus, the diversity gain of the NCC-OFDMA-SRS scheme is 2L. 5.2.5 Numerical results Comprehensive simulation results based on different system parameters that support the theoretical results are presented in this section. The results of the NCC-OFDMA-SRS system are compared to the results of a system that supports only sd links, given in [33]. For brevity, we refer to the two systems as NCC and SD, respectively, and corresponding results are shown in Figure 5.4 and Figure 5.5 under different system parameters. It is assumed that sr links have 20 dB better average SNR values than sd links to set-up relay-aided communication. The considered assumption is valid since relay nodes are closer to the source nodes than the destination nodes in practical applications. The R2EHK algorithm is used for the assignment of subcarriers in broadcast and relaying phases. It is assumed that only three types of links are available in the system for notational simplicity, γ¯sid = γ¯sd, γ¯sirj = γ¯sr, and γ¯rjd = γ¯rd. The reliability of the theoretical derivations with the simulations is checked and shown to be consistent. The approximation and simulation results of the decoding failure probability of NCC and SD systems against varying M , N , and ℵ values are given in Figure 5.4. The number of coherence bandwidths is fixed to L = 1 to observe the effect of other parameters. In order to increase the visualization of the effects of the system parameters, sd and rd links are assumed to have the same average SNR value, 72 0 5 10 15 20 25 30 35 4010 -5 10 -4 10 -3 10 -2 10 -1 100 Figure 5.4 : The comparison of simulation and theoretical results of the decoding failure probability of NCC-OFDMA-SRS for L = 1, ℵ = 8 over varying values of M and N . expressed as γ¯sd = γ¯rd = γ¯ and sr links have the average SNR of γ¯sr = γ¯ + 20 dB. An increase in the number of source nodes, M , has a negative effect on decoding probability performance without changing the diversity gain. When only sd links are present, lower decoding performance is obtained for all cases. It can be inferred from this figure that the diversity gain of the NCC scheme is equal to 2 when L = 1. On the other hand, the SD system achieves a smaller diversity gain compared to the NCC scheme in the same conditions. Simulation results match well with the theoretical expressions. Figure 5.5 depicts the effect of the number of coherence bandwidths on system performance. It can be seen that the diversity gain of NCC-OFDMA-SRS system depends only on L parameter as given in (5.20). Simulations validate the theoretical results. It can be deduced from the figure that, if L parameter is fixed, the diversity gain does not change. It can be observed that the SD system cannot achieve the same diversity as the NCC system. 73 0 5 10 15 20 25 30 35 4010 -5 10 -4 10 -3 10 -2 10 -1 100 Figure 5.5 : The comparison of simulation and theoretical results of the decoding failure probability of NCC-OFDMA-SRS for M = 4, N = 4, and ℵ = 8 over varying values of L. 5.3 Summary and Discussion In this chapter, we propose Hungarian method based optimization algorithms for minimizing the number of outage subcarriers by jointly reducing the total transmit power in downlink OFDMA systems, through the minimum cost perfect matching over randomly weighted complete bipartite graph, enabling controlled rate assignments among users as the first perspective. The required transmit power level of each user-subcarrier pair is determined according to the outage probability of a subcarrier. The proposed approaches provide power savings compared to the benchmark results in the literature. After that, the signaling model of NCC-OFDMA system is provided. Besides, the performance analysis of NCC-OFDMA-SRS is examined for the first time in the literature. Analytical expressions for both the decoding failure probability and the diversity gain of NCC-OFDMA-SRS are derived. It is proved that the diversity gain of the system depends only on the number of coherence bandwidths by applying the R2EHK algorithm to allocate the subcarriers. Simulation results of the decoding failure probability at the destination node verify the theoretical results. 74 6. WIRELESS NETWORK RELIABILITY ANALYSIS FOR ARBITRARY NETWORK TOPOLOGIES Chapters 3, 4, and 5 mainly concentrate on designing efficient relaying applications in terms of relay nodes, bandwidth, and power. In this concept, the performance evaluation of various optimization schemes and scenarios are explained for wireless channels by utilizing graph theoretic tools. Different from the previous perspective of utilizing graph theory definitions as the auxiliary tools, we relate the prominent graph theory theorem, max-flow min-cut, with the key communication performance metrics, diversity and coding gains. In addition, performance analysis of arbitrary wireless network topologies is provided in this chapter. In [121], error performance of any communication network (coded or uncoded) is represented in terms of the diversity and coding gains under high SNR regime. The diversity gain is defined as a measure of the number of independent copies of the transmitted signal captured by the receiver [122], while coding gain represents the difference in the outage probability curve relative to a benchmark performance while SNR goes to zero [121]. Therefore, the network outage probability can be represented by the diversity and coding gains while SNR goes to zero referred to as high SNR regime. The high SNR performance results are used to determine the performance limits of any communication system. Based on the corresponding SNR value, the outage status can be determined and used as a performance indicator for each link. In case of an outage (where the SNR value falls below a certain threshold), two nodes are deemed to be disconnected; otherwise, they remain connected. Outage probability is a convenient measure of communication system performance [123]. The behavior of the outage probability in the high SNR regime also gives an intuitive understanding of performance limits of the target network [22]. The network outage polynomial gives the probability that the network has zero instantaneous capacity. The investigation of network capacity is an attractive problem 75 since the maximum capacity of any network is restricted by the size of the minimum cut of the graph. In the literature, there are some related studies about the calculation of the capacity polynomials that determine the value of the maximum flow of arbitrary networks with random capacity edges by utilizing subset decomposition method [46, 47]. In [46], a subspace decomposition principle is used to determine the value of the maximum flow of arbitrary networks with random capacity edges. The value of maximum flow analysis of arbitrary networks with random edge capacities is conducted in [47] based on Bernoulli statistics. In this chapter, the network reliability perspective of graph theory is used to obtain the network outage polynomial of generalized wireless networks by enumerating paths and cut-sets of its graph representation for both uncorrelated and correlated wireless channels. A relation is established between the max-flow min-cut theorem and key communication performance indicators. In this chapter, we establish the framework to calculate the network outage polynomial, as a tool to obtain network outage performance of communication networks. An ergodic capacity analysis of networks with arbitrary topologies based on the network outage polynomial is also presented. By using the provided analysis, the optimization of resource utilization can be realized thanks to the information about the diversity gain and the ergodic capacity of any topology in wireless networks. For example, efficient multiple access schemes can be obtained by considering user demands and network limitations (in terms of the diversity gain and the ergodic capacity). 6.1 Outage Polynomials of Wireless Networks Graph representations of communication systems are used to analyze the system performance, hence key graph theory concepts can be matched with the elements of communication systems. In the literature pertaining to wired networks, the link outage probability is generally ignored since links are usually highly reliable. Thus, for wired networks, the connections among nodes can be represented by deterministic edges. The links in wireless channels, on the other hand, are subject to random SNR values. Therefore, the connections between nodes must be modeled probabilistically. We model a communication network N = (V , E , S,D) as a directed acyclic network compromising of a finite vertex set V of communication nodes, a multi-set of η directed 76 edges E = {e1, e2, . . . , eη} ⊆ V×V representing communication links between nodes, a designated source vertex S and a designated terminal vertex D where S,D ∈ V , S 6= D. An edge e from vertex v to vertex w is denoted as v → w. A directed path in N from S to D is a sequence of edges (v0 → v1), (v1 → v2), . . . , (v`−1 → v`) with v0 = S and v` = D. We suppose that there are P distinct paths P1, . . . ,PP inN from S to D. Nodes S and D are said to be connected if P ≥ 1. A subset C ⊆ E of edges whose removal from the network disconnects S and D is called an S-D-separating cut, or simply a cut-set. We suppose that there are ζ distinct cut-sets C1, . . . , Cζ ; the collection of all cut-sets and denoted by K. A cut-set C ∈ K is called minimal if no proper subset of C is itself a cut-set. The collection of all minimal cut-sets is denoted as L. A cut-set C ∈ K is called a minimum cut-set if it is a cut-set of minimum possible size, i.e., having the least number of edges among all cut-sets. The collection of all minimum cut-sets is denoted asM, and the size of any minimum cut-set is denoted as m. Although each minimum cut-set is certainly a minimal cut-set, the converse is not true in general, thusM⊆ L ⊆ K. Network outage term is a suitable measure of a communication system performance, as the overall system performance can be obtained using individual outage probabilities of the links in the system. To enable communication between a source node S and a terminal node D, there must be at least one path from S to D. Thus, we can obtain an overall performance result by considering individual link outages. The network outage polynomial concept, which is proposed for switching networks [36, 124], is also suitable as a performance observation tool for wireless communication. Network outage is random due to the individual link outages. In order to obtain the network outage polynomial for an arbitrary topology, we use three different methods, namely path enumeration, cut-set enumeration, and reliability polynomial calculation. The required method can be selected to realize the target aim, as detailed below. In the following, we consider the network at a given time instant, and denote by p, the probability that link e is in outage at that instant. For example, if the wireless channel gain |h| is assumed to have a Rayleigh distribution, then the outage probability of e is equal to p = 1− exp ( −γ−1 ) , (6.1) 77 where γ represents the average SNR of the link e [122]. Link outages induce a random subgraph of N , called the residual network, with removed edges that are in outage. In the residual network, it may happen that S and D are not connected. The network outage polynomial, which gives the probability that no path exists between S and D in the residual network, is then formally a polynomial function of p1, p2, . . . , pη, denoted by O(p1, p2, . . . , pη). Throughout this chapter, for any positive integer `, we denote the set {1, 2, . . . , `} as [`]. We obtain the network outage polynomial expression through path enumeration, cut-set enumeration, and terminal-reliability approaches in the following subsections. 6.1.1 Network outage polynomial calculation based on path enumeration Firstly, we investigate the path enumeration method to obtain the network outage polynomial. We suppose that the edges, comprising of a path Pυ in N from S to D, are indexed by the set Pυ ⊆ [η], i.e., Pυ = {e :  ∈ Pυ}, υ ∈ [P ]. Let Qυ denote the event that path Pυ is available, i.e., that none of its links are in outage. The outage probability of the network is then given by O(p1, . . . , pη) = 1− Pr{Q1 ∪Q2 ∪ · · · ∪QP}. (6.2) By the principle of inclusion-exclusion [125], we have Pr{Q1 ∪Q2 ∪ · · · ∪QP} = ∑ ı1∈[P ] Pr{Qı1} − ∑ ı1,ı2∈[P ] ı1 6=ı2 Pr{Qı1 ∩Qı2}+ · · · + (−1)β−1 ∑ ı1,ı2,...,ıβ∈[P ] ı1,ı2,...,ıβ distinct Pr{Qı1 ∩Qı2 ∩ · · · ∩Qıβ}+ · · · + (−1)P−1 Pr{Q1 ∩Q2 ∩ · · · ∩QP}. (6.3) Assuming that individual links are in outage (or not) independently, we have Pr{Qı1 ∩Qı2 ∩ · · · ∩Qıβ} = ∏ ∈Pı1∪Pı2∪···∪Pıβ (1− p). (6.4) 6.1.2 Network outage polynomial calculation based on cut-set enumeration Secondly, the network outage polynomial of an arbitrary network can also be calculated by enumerating cut-sets of the network, which is dual to the process of 78 path enumeration. If the edges of any cut-set are all in outage, the network is said to be in outage. We suppose that the edges comprising of a cut-set Cυ are indexed by the set Cυ ⊆ [η], i.e., Cυ = {e :  ∈ Cυ}, υ ∈ [ζ]. Let Bυ denote the event that cut-set Cυ is active, i.e., that all of its links are in outage. The outage probability of the network is then given by O(p1, p2, . . . , pη) = Pr{B1 ∪B2 ∪ · · · ∪Bζ}. (6.5) Again by the principle of inclusion-exclusion, we have Pr{B1 ∪B2 ∪ · · · ∪Bζ} = ∑ ı1∈[ζ] Pr{Bı1} − ∑ ı1,ı2∈[ζ] ı1 6=ı2 Pr{Bı1 ∩Bı2}+ · · · + (−1)β−1 ∑ ı1,ı2,...,ıβ∈[ζ] ı1,ı2,...,ıβ distinct Pr{Bı1 ∩Bı2 ∩ · · · ∩Bıβ}+ · · · + (−1)ζ−1 Pr{B1 ∩B2 ∩ · · · ∩Bζ}, (6.6) where Pr{Bı1 ∩Bı2 ∩ · · · ∩Bıβ} = ∏ ∈Cı1∪Cı2∪···∪Cıβ p. (6.7) 6.1.3 Network outage polynomial calculation based on two-terminal polynomial Finally, we derive the network outage polynomial expressions of a network based on the reliability polynomial concept [124], which is a useful function to reflect the performance of a network. Consider, for any cut-set Cυ, υ ∈ [ζ], the event Eυ that all the edges of Cυ are in outage while all other edges of the network are not in outage. Since Eυ is disjoint from Eυ′ when υ 6= υ′, we have O(p1, . . . , pη) = Pr { ⋃ υ∈[ζ] Eυ } = ∑ υ∈[ζ] Pr{Eυ}. (6.8) Assuming that individual links are in outage (or not) independently, we then have Pr{Eυ} = ∏ ∈Cυ p × ∏ ′∈[ζ]\Cυ (1− p′). (6.9) 79 In the special case where p = p for all  ∈ [η], we have Pr{Eυ} = p|Cυ |(1− p)η−|Cυ |. (6.10) Writing O(p) for the outage polynomial in this case, we get O(p) = ∑ υ∈[ζ] p|Cυ |(1− p)η−|Cυ | = η∑ ı=m Aıpı(1− p)η−ı = (1− p)ηA ( p 1− p ) , (6.11) where A(χ) = ∑ C∈K χ|C| = Amχm + Am+1χm+1 + · · ·+ Aηχη, (6.12) with the coefficient Aı of χı enumerating the number of cut-sets of size ı. It can be inferred from the minimum cut-set definition that Am is equal to the number of distinct minimum cut-sets and Am 6= 0. In addition, Aη is equal to 1. The outage polynomial can be also expressed in terms of the reliability polynomial, denoted by Rel(.), associated with the Conn2(N ) S-D connectedness problem, O(p) = 1−Rel(N , 1−p) [124, Sec. 1.2]. 6.1.4 Bounds on the outage polynomial We may define some simple bounds on the outage polynomial as follows. Utilizing the inequality of (1− p) ≤ 1 in (6.11), we get O(p) ≤ η∑ ı=m Aıpı = A(p). (6.13) To derive another upper bound expression, we can use the fact that every cut-set must contain a minimal cut-set. Since the probability that edges of a cut-set C are in outage is given by p|C|, we get O(p) ≤ ∑ C∈L p|C|. (6.14) We also have the lower bound O(p) ≥ Ampm(1− p)η−m (6.15) which is obtained by retaining just the first term in the expansion O(p) = ∑η ı=mAıpı(1− p)η−ı. 80 6.1.5 Presence of correlated channels In the previous subsections, we assume that the state of each link is independent of the others. This assumption may be unrealistic in many situations (e.g., multi-antenna systems) because of spatial correlation. The correlated channel case needs to be considered to determine the limitations of the wireless networks. We adopt a simple correlation model, as follows. The set E of links is partitioned into disjoint non-empty subsets, B1, B2, . . . , Bf , so that f⋃ ı=1 Bı = E and ı 6=  implies Bı ∩ B = ∅. (6.16) The subset Bı is associated a Bernoulli ({0, 1}-valued) random variable Sı, with Pr{Sı = 1} = ρ. If Sı = 1, the link states (in outage or not) for all links in Bı are chosen to be equal, while if Sı = 0, the link states for the links in Bı are chosen independently at random. Suppose that Bı has size |Bı| = χ, and let Sı be any subset of Bı of size |Sı| = y, where 0 ≤ y ≤ χ. Then, the probability po(χ, y) that the links of Sı are in outage while the links of Bı \ Sı are not in outage is given as po(χ, y) =    ρ(1− p) + (1− ρ)(1− p)χ if y = 0 ρp+ (1− ρ)pχ if y = χ (1− ρ)py(1− p)χ−y otherwise. (6.17) We assume that the random variables S1, . . . , Sf are mutually independent. Note that the previously considered case (of independent link-states) is obtained by considering ρ = 0, or, equivalently, by partitioning E into singleton sets where |Bı| = 1 for all ı. Now, given any subset C ⊂ E of edges (e.g., a cut-set), the probability that all edges of C are in outage while all edges in E \ C are not in outage is given by f∏ ı=1 po(|Bı|, |C ∩ Bı|). (6.18) Thus, the network outage polynomial is obtained as O(p) = ∑ C∈K f∏ ı=1 po(|Bı|, |C ∩ Bı|). (6.19) 81 6.2 Diversity Gain and Ergodic Capacity Analyses for Arbitrary Network Topologies In this section, performance limitations of an arbitrary network are determined via the outage polynomial. Firstly, the expressions for the diversity and coding gains are derived. Secondly, the ergodic capacity is considered. 6.2.1 Diversity gain analysis In order to provide further insight into the obtained outage probability expression, an asymptotic expression of outage probability is derived. The network is in outage if there is no defined path between S and D. Diversity and coding gains are able to represent the network outage probability in the limit as p → 0, referred to as the high SNR regime. As mentioned before, the high SNR performance of any system determines the performance limits of a wireless network. In the high SNR regime, the outage probability expression of an arbitrary given network is given as O(p) ≈ αγ−d, (6.20) where d, the diversity gain, measures the number of independent copies of the transmitted signal that are received at the terminal node, and where α, the coding gain (usually expressed on a decibel scale), is a measure of the performance difference between the expressed system and a baseline system having O(p) ≈ γ−d [126]. For the purposes of the following theorem, we say that two functions f(p) and λ(p) are asymptotically equal, written as f(p) ∼ λ(p), if lim p→0 f(p) λ(p) = 1. (6.21) Theorem 6.1 In a network with outage polynomial O(p) = ∑ηı=mAıpı(1− p)η−ı, O(p) ∼ Ampm. (6.22) Thus, the diversity gain of such a network is equal to the size of a minimum cut-set, i.e., d = m, and the coding gain is equal to the number of distinct minimum cut-sets, i.e., α = Am. 82 Proof. We have lim p→0 O(p) Ampm = lim p→0 Ampm(1− p)η−m + Am+1pm+1(1− p)η−m−1 + · · ·+ pη Ampm = lim p→0 (1− p)η−m + lim p→0 Am+1 Am p(1− p)η−m−1 + · · ·+ lim p→0 1 Am pη−m = 1. (6.23) The value of maximum flow (the size of the minimum cut) can be calculated by enumerating the number of cut-sets in a dual manner for unit capacity graphs. For dense network graphs, the Ford-Fulkerson algorithm can be used to determine the size of the minimum cut value [4]. It is obvious that adding new edges to a network cannot reduce the size of any cut-sets. If newly added edges (e.g., a line-of-sight edge) provide a new edge-disjoint path from S to D, then the cardinality of all cut-sets, and hence the diversity gain of the network, increases by one. 6.2.2 Ergodic network capacity Suppose now that each network link (when not in outage) provides unit transmission capacity. It is well known, e.g., [56], that the instantaneous S-D unicast capacity C is equal to the size of the minimum S-D-separating cut in the network subgraph induced by the links that are not in outage; this transmission rate can be achieved by routing information along edge-disjoint paths between S and D (which, by Menger’s Theorem, exist in sufficient number). As the link-state is random, the instantaneous capacity C is a random variable. Indeed, the outage polynomial O(p) gives the probability that C = 0. It is also clear that C is bounded by m, the minimum cut-set size. As C takes integer values in a bounded set, it has a well-defined expected value, called the ergodic network capacity. For ı ∈ {0, 1, . . . ,m}, the event C = ı arises when all minimal cut-sets C ∈ L contain at least ı links not in outage, and at least one of these cut-sets contains exactly ı links not in outage. In other words, C = ı arises when the minimum number of non-outage links among minimal cut-sets is equal to ı. More precisely, let E ′ denote the set of 83 edges not in outage at a given time instant. For any minimal cut C ∈ L, let δı(C) = { 0 |C ∩ E ′| < ı 1 |C ∩ E ′| ≥ ı (6.24) be the function that indicates whether C contains at least ı edges not in outage. The event C = ı then arises if ∀C ∈ L(δ(C) = 1) (6.25) min C∈L |C ∩ E ′| = ı. (6.26) For every ı, the probability that C = ı is given by some polynomial Cı(p). The ergodic capacity can then be obtained in terms of p, as E[C](p) = m∑ ı=0 ıCı(p). (6.27) When the minimal cut-sets C ∈ L are disjoint, the ıth capacity polynomial can be calculated as follows. For any minimal cut C ∈ L of size |C|, let τ(ı, |C|, p) denote the probability that C contains at least ı links not in outage; thus τ(ı, |C|, p) = ∑ ı′≥ı (|C| ı′ ) p|C|−ı′(1− p)ı′ . (6.28) The probability that every minimal cut contains ı or more links not in outage is then given as∏C∈L τ(ı, |C|, p). The probability that C = ı is then defined as the probability that every minimal cut contains ı or more links in non-outage but not every minimal cut contains ı+ 1 more links in non-outage, namely Cı(p) = ∏ C∈L τ(ı, |C|, p)− ∏ C∈L τ(ı+ 1, |C|, p). (6.29) 6.3 Numerical Results In this section, we present numerical results to clarify the theoretical expressions on the network performance. We provide two instructive examples to clarify theoretical expressions derived in the previous sections. Firstly, consider the example network N1 presented in Figure 6.1 (a) with edges as labeled. In this network, there are η = 3 edges with the size of the minimum cut 84 13 S D e1 e2 e3 (a) N1 S D e1 e2 e3 e4 (b) N2 S D e1 e2 (c) N3 S D e2 e1 e3 e5 e4 e6 (d) N4 S D e1 e2 e3 e4 (e) N5 S D e1 e2 e3 e4 e5 (f) N6 Fig. 1: There are three example networks denoted by N1, N2, N3, N4, N5, and N6 which are presented in (a), (b), (c), (d), and (e), respectively. N1, N2, and N3 respectively have 3 edges, 4 edges, 2 edges, 6 edges, 4 edges and 5 edges. Firstly, consider the example network N1 presented in Fig. 1(a) with edges as labeled. In this network, there are n = 3 edges with the size of the minimum cut m = 1. The cut-sets, minimal cut-sets, and minimum cut-sets are K ={{e1}, {e1, e2}, {e1, e3}, {e2, e3}, {e1, e2, e3}}, L ={{e1}, {e2, e3}}, and M ={{e1}}, respectively. We have A(x) = x+ 3x2 + x3, thus, the outage polynomial for N1 is calculated as O(p) = p(1− p)2 + 3p2(1− p) + p3 = p+ p2 − p3. Figure 6.1 : There are six exemplary networks denoted by N1, N2, N3, N4, N5, and N6 which are presented in (a), (b), (c), (d), (e), and (f) respectively. N1, N2, N3, N4, N5, and N6 respectively have 3 edges, 4 edges, 2 edges, 6 edges, 4 edges, and 5 edges. m = 1. The cut-sets, minimal cut-sets, and minimum cut-sets are K ={{e1}, {e1, e2}, {e1, e3}, {e2, e3}, {e1, e2, e3}}, L ={{e1}, {e2, e3}}, and M ={{e1}}, respectively. (6.30) We have A(χ) = χ+ 3χ2 +χ3, and thus the outage polynomial forN1 is calculated as O(p) = p(1− p)2 + 3p2(1− p) + p3 = p+ p2 − p3. (6.31) The bound expressions are also given by O(p) ≤A(p) = p+ 3p2 + p3 O(p) ≤p+ p2 O(p) ≥p(1− p)2. (6.32) 85 Figure 6.2 : The comparative results of upper and lower bounds of the outage polynomial of N1. Figure 6.2 shows that the given upper bounds become tight when p > 0.5. As p → 0, all bounds have the same outage performance with the exact O(p) expression. In addition, the first order approximation of O(p) given as O(p) ∼ p has a close performance to O(p) along with p. The capacity polynomials of the network can be calculated as C0(p) = O(p) = p+ p2 − p3 C1(p) = 2p(1− p)2 + (1− p)3 = 1− p− p2 + p3. (6.33) By using (6.27), the ergodic capacity of N1 can be found as E[C](p) = 1− p− p2 + p3. (6.34) The obtained capacity polynomials of N1 are presented in Figure 6.3 (a). While p < 0.5, C0(p) is highly probable compared toCı(p) for ı = 1. On the other hand, C1(p)→ 1 in the case of p→ 0. It can be inferred from Figure 6.3 (b), that the average capacity of the network increases while p decreases. In addition, the maximum value of the average capacity of the network is equal to m = 1 for p = 0. 86 (a) (b) Figure 6.3 : (a) The capacity polynomials results of N1, (b) The ergodic capacity results of N1. We give another example to illustrate the correlated case results. The depicted extended graph of Figure 6.1 (a) with 4 edges labeled as N2 is given in Figure 6.1 (b). The network has the following sets: K = {{e1, e2}, {e3, e4}, {e1, e2, e3}, {e1, e2, e4}, {e2, e3, e4}, {e1, e3, e4}, {e1, e2, e3, e4}}, L = {{e1, e2}, {e3, e4}}, M = {{e1, e2}, {e3, e4}}. (6.35) In the uncorrelated case, the outage polynomial can be calculated as O(p) = 2p2(1− p)2 + 4p3(1− p) + p4 = 2p2 − p4, where m = 2 and Am = 2. If the correlated edge assumption given in (6.17) is used, the disjoint correlated edge sets are given as B1 = {e1, e2}, B2 = {e3, e4}. (6.36) where B1 ∪ B2 = E and B1 ∩ B2 = ∅. By using (6.19), the outage polynomial of the correlated case is derived as O(p) = (ρp+ p2 − ρp2) [ 2− ρp− p2 + ρp2 ] . (6.37) The numerical results of (6.37) are presented in Figure 6.4. The uncorrelated case (ρ = 0) has the best outage performance, as expected. When ρ = 0.1, the outage performance is worse than the uncorrelated case. As ρ increases, the outage performance gets worse. When ρ = 0.5, 4-edges network has the close performance 87 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 110 -4 10-3 10-2 10-1 100 Figure 6.4 : The outage polynomial results of N2 versus ρ. of 3-edges system, N1. On the other hand, if ρ is equal to 0.9 it means that highly correlated links are available, the outage performance of 4-edges networks approaches to 2-edges system model labeled as N3 and is depicted in Figure 6.1 (c). The capacity polynomials of N2 can be calculated as C0(p) = p4 + 4p3(1− p) + 2p2(1− p)2 = 2p2 − p4, C1(p) = 4p2(1− p)2 + 4p(1− p)3 = 4p− 8p2 + 4p3, C2(p) = (1− p)4. (6.38) The ergodic capacity of N2 is expressed by E[C](p) = 2− 4p+ 4p2 − 4p3 + 2p4. (6.39) The numerical results of the given polynomials are shown in Figure 6.5 (a). Cı(p)→ 1 in the case of p→ 0. Thus, the maximum value of the ergodic capacity of the network which is shown in Figure 6.5 (b) is equal to m = 2 for p→ 0. In order to obtain further insight about the derivations, the outage polynomial and the ergodic capacity results of N4, N5, and N6 depicted in Figs. 6.1 (d), (e), and (f), respectively, are investigated. By using (6.11), the outage polynomial expressions of 88 (a) (b) Figure 6.5 : (a) The capacity polynomials results of N2 (b) The ergodic capacity results of N2. N4, N5, and N6 can be respectively calculated as O(p) =4p2 − 2p3 − 4p4 + 4p5 − p6, O(p) =4p2 − 4p3 + p4, O(p) =4p3 − 4p4 + p5. (6.40) Here, the three graphs (N4, N5, and N6) have the same coding gain with Am = 4. On the other hand, N4 and N5 have the same diversity gain equal to 2 and the diversity gain of N6 is equal to 3. The ergodic capacity results of the three networks can be respectively given as E[C](p) =2− 5p+ 6p2 − 8p3 + 9p4 − 5p5 + p6, E[C](p) =2− 4p+ 2p2, E[C](p) =3− 5p+ 2p2. (6.41) The outage polynomial and the ergodic capacity results of all the networks shown in Figure 6.1 are presented in Figure 6.6 and Figure 6.7, respectively. It can be shown from Figure 6.6 that N6 has the best outage performance with the highest diversity gain m = 3. The two worst outage performance with m = 1 belongs to N3 and N1, as expected. N2, N4, and N5 have close outage performance results with m = 2. The ergodic capacity results, which are in accordance with the outage polynomial results, are depicted in Figure 6.7. The best performance belongs to N6. 6.4 Summary and Discussion In this chapter, we obtain the performance limits of generalized wireless communication networks by using the concepts of graph theory. We evaluate the 89 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 110 -4 10-3 10-2 10-1 100 Figure 6.6 : The outage polynomial results of all the networks defined in Figure 6.1. network outage polynomial by utilizing individual link outages, through the use of path enumeration, cut-set enumeration and terminal-reliability approaches. For high SNR regime, diversity and coding gains are extracted from the graph model of wireless networks. We prove that the diversity gain of any wireless communication network is minimum cut-set size of the network graph and the coding gain is the number of distinct minimum cut-sets. We also present the ergodic capacity analysis of arbitrary networks to obtain the ergodic capacity polynomials. The theoretical expressions are illustrated by numerical examples. Accordingly, we provide a comprehensive tool that can be used to determine asymptotic performance of unstructured wireless networks and to specify their performance limitations under various implementation schemes. 90 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.5 1 1.5 2 2.5 3 Figure 6.7 : The ergodic capacity results of all the networks defined in Figure 6.1. 91 92 7. CONCLUSIONS This thesis compromises of two main concepts, namely designing efficient system architectures in terms of network resources (relay, power, and bandwidth) and determining asymptotic performance bounds of the unstructured wireless networks. We mainly focus on the efficient usage of limited radio sources, power and bandwidth, as well as relays by the aid of network coding. After providing efficient network coding cooperation schemes, we present a comprehensive tool that can be used to obtain fundamental performance limits of any wireless network topologies in terms of diversity gain for various implementation cases. Hence, the thesis provides significant contributions from not only application perspective but also from asymptotic performance perspective in network coding literature in order to maximize served users as well as reducing the total power consumption and required bandwidth. 7.1 On the Efficiency Perspective The major part of the thesis is compromised of designing resource-efficient network coding structures. Firstly, we have considered eliminating the complexity of utilization of all relay nodes scenario in the system using of relay selection schemes. Then, we have continued with power and bandwidth requirement optimization of multiple users by providing user fairness. We have proposed improved versions of the state-of-the-art algorithms such as Hungarian algorithm, min-max relay selection criterion to realize and achieve the objectives. At the end, we have proposed joint resource allocation schemes by considering smart applications of the relay nodes. 7.2 On the Fundamental Limits Perspective The final part of the thesis concentrates on attaining performance limitations for generalized wireless networks. We have presented both network outage polynomials and ergodic capacity results based on max-flow min-cut theorem. We have 93 derived performance limits of the wireless networks with regard to conventional communication performance metrics, diversity and coding gains. 7.3 Future Directions We provide additional future directions in the following as an extension to the topics investigated in this thesis. • The impact of relay selection techniques in densely populated network scenarios may be examined when the sparsity level of RLNC is tuned. • The conversion from tripartite graph model to bipartite graph model given in Chapter 4, can be extended for multi-hop relaying communication or multiple destination structure. • The asymptotic performance results presented in Chapter 6 can be useful for analyzing the performance of next generation heterogeneous networks. • The considered system models can be revisited to extend multiple-input multiple-output systems. • Considering all the open issues and the potential of the NCC systems in terms of multi-source transmission networks for diverse set of services varying from multiple unicast to multicast distribution scenarios, drastic improvements are expected in this area in the very near future including various extensions to specific applications such as wireless storage or content distribution. 94 REFERENCES [1] Yeung, R.W. (1995). Multilevel diversity coding with distortion, IEEE Trans. Inf. Theory, 41(2), 412–422. [2] Ahlswede, R., Cai, N., Li, S.Y. and Yeung, R. (2000). Network information flow, IEEE Trans. Inf. Theory, 46(4), 1204–1216. [3] Ngai, C.K. and Yeung, R. (2004). Network coding gain of combination networks, Proc. IEEE Inf. Theory Workshop, pp.283–287. [4] Ford, L.R. and Fulkerson, D.R. (1956). Maximal flow through a network, Canadian journal of Mathematics, 8(3), 399–404. [5] Laneman, J. and Wornell, G. (2003). Distributed space-time-coded protocols for exploiting cooperative diversity in wireless networks, IEEE Trans. Inf. Theory, 49(10), 2415–2425. [6] Katti, S., Rahul, H., Hu, W., Katabi, D., Medard, M. and Crowcroft, J. (2008). XORs in the Air: Practical Wireless Network Coding, IEEE/ACM Trans. Netw., 16(3), 497–510. [7] MacWilliams, F. and Sloane, N. (1977). The Theory of Error-correcting Codes, North-Holland mathematical library, North-Holland Publishing Company. [8] Topakkaya, H. and Wang, Z. (2011). Wireless Network Code Design and Performance Analysis Using Diversity-Multiplexing Tradeoff, IEEE Trans. Commun., 59(2), 488–496. [9] Ho, T., Medard, M., Koetter, R., Karger, D.R., Effros, M., Shi, J. and Leong, B. (2006). A Random Linear Network Coding Approach to Multicast, IEEE Trans. Inf. Theory, 52(10), 4413–4430. [10] Trullols-Cruces, O., Barcelo-Ordinas, J. and Fiore, M. (2011). Exact Decoding Probability Under Random Linear Network Coding, IEEE Commun. Lett., 15(1), 67–69. [11] Chiasserini, C.F., Viterbo, E. and Casetti, C. (2013). Decoding Probability in Random Linear Network Coding with Packet Losses, IEEE Commun. Lett., 17(11), 1–4. [12] Seong, J.T. (2014). Bounds on Decoding Failure Probability in Linear Network Coding Schemes with Erasure Channels, IEEE Commun. Lett., 18(4), 648–651. 95 [13] Seong, J.T. and Lee, H.N. (2014). Predicting the Performance of Cooperative Wireless Networking Schemes With Random Network Coding, IEEE Trans. Commun., 62(8), 2951–2964. [14] Khan, A.S. and Chatzigeorgiou, I. (2016). Improved Bounds on the Decoding Failure Probability of Network Coding Over Multi-Source Multi-Relay Networks, IEEE Commun. Lett., 20(10), 2035–2038. [15] Khan, A.S., Tassi, A. and Chatzigeorgiou, I. (2015). Rethinking the Intercept Probability of Random Linear Network Coding, IEEE Commun. Lett., 19(10), 1762–1765. [16] Ferreira, P.J.S.G., Jesus, B., Vieira, J. and Pinho, A.J. (2013). The Rank of Random Binary Matrices and Distributed Storage Applications, IEEE Commun. Lett., 17(1), 151–154. [17] Khan, A.S. and Chatzigeorgiou, I. (2015). Performance analysis of random linear network coding in two-source single-relay networks, Proc. IEEE ICCW, pp.991–996. [18] Shrader, B., Babikyan, A., Jones, N.M., Shake, T.H. and Worthen, A.P. (2011). Rate control for network-coded multipath relaying with time-varying connectivity, IEEE J. Sel. Areas Commun., 29(5), 1106–1117. [19] Ghanem, S.A., Gharsellaoui, A.E., Tarchi, D. and Vanelli Coralli, A. (2017). Physical layer aware adaptive network coding schemes for satellite communications, International Journal of Satellite Communications and Networking, 35(6), 537–549. [20] Moreira, A. and Lucani, D.E. (2015). Coded schemes for asymmetric wireless interfaces: theory and practice, IEEE J. Sel. Areas Commun., 33(2), 171–184. [21] Dau, S.H., Song, W. and Yuen, C. (2015). On simple multiple access networks, IEEE J. Sel. Areas Commun., 33(2), 236–249. [22] Proakis, J.G. (1995). Digital Communications, McGraw-Hill. [23] Jang, J. and Lee, K.B. (2003). Transmit power adaptation for multiuser OFDM systems, IEEE J. Sel. Areas Commun., 21(2), 171–178. [24] Hoo, L.M.C., Halder, B., Tellado, J. and Cioffi, J.M. (2004). Multiuser transmit optimization for multicarrier broadcast channels: asymptotic FDMA capacity region and algorithms, IEEE Trans. Commun., 52(6), 922–930. [25] Huang, J., Subramanian, V.G., Agrawal, R. and Berry, R.A. (2009). Downlink scheduling and resource allocation for OFDM systems, IEEE Trans. Wireless Commun., 8(1), 288–296. [26] Wang, T., Glineur, F., Louveaux, J. and Vandendorpe, L. (2013). Weighted Sum Rate Maximization for Downlink OFDMA With Subcarrier-Pair Based Opportunistic DF Relaying, IEEE Trans. Signal Process., 61(10), 2512–2524. 96 [27] Wang, T., Fang, Y. and Vandendorpe, L. (2013). Power Minimization for OFDM Transmission with Subcarrier-Pair Based Opportunistic DF Relaying, IEEE Commun. Lett., 17(3), 471–474. [28] Zhao, J., Zheng, W., Wen, X. and Zhang, L. (2014). Joint resource allocation in secure two-way relay networks with QoS guarantee and fairness, Proc. IEEE WCNC, pp.1985–1989. [29] Yin, H. and Liu, H. (2000). An efficient multiuser loading algorithm for OFDM-based broadband wireless systems, Proc. IEEE GLOBECOM, pp.103–107. [30] Zhang, Z., He, Y. and Chong, E. (2005). Opportunistic downlink scheduling for multiuser OFDM systems, Proc. IEEE WCNC, pp.1206–1212 Vol. 2. [31] Loodaricheh, R., Mallick, S. and Bhargava, V. (2014). Joint resource optimization for OFDMA cellular networks with user cooperation and QoS provisioning, Proc. IEEE WCNC, pp.1264–1269. [32] Bai, B., Chen, W., Cao, Z. and Letaief, K. (2008). Achieving High Frequency Diversity with Subcarrier Allocation in OFDMA Systems, Proc. IEEE GLOBECOM, pp.1–5. [33] Bai, B., Chen, W., Ben Letaief, K. and Cao, Z. (2011). Diversity-Multiplexing Tradeoff in OFDMA Systems: An H-Matching Approach, IEEE Trans. Wireless Commun., 10(11), 3675–3687. [34] Basaran, S.T., Kurt, G.K., Engin, B. and Altunbas, I. (2015). Joint power and subcarrier allocation in OFDMA systems, Signal Processing and Communications Applications Conference (SIU), 2015 23th, IEEE, pp.2170–2173. [35] Heidarpour, A., Kurt, G.K. and Uysal, M. (2015). Diversity-Multiplexing Tradeoff for Network Coded Cooperative OFDMA Systems, Proc. IEEE ICC, pp.4368–4373. [36] Moore, E. and Shannon, C. (1956). Reliable circuits using less reliable relays, Journal of the Franklin Institute, 262(3), 191 – 208. [37] Bondy, J.A. and Murty, U.S.R. (1976). Graph theory with applications, volume290, Citeseer. [38] Wing, O. and Demetriou, P. (1964). Analysis of probabilistic networks, IEEE Trans. Commun. Tech., 12(3), 38–40. [39] Lin, P.M., Leon, B.J. and Huang, T.C. (1976). A New Algorithm for Symbolic System Reliability Analysis, IEEE Trans. Rel., R-25(1), 2–15. [40] Moskowitz, F. (1958). The analysis of redundancy networks, Transactions of the American institute of electrical engineers, part i: communication and electronics, 77(5), 627–632. 97 [41] Gupta, P. and Kumar, P.R., (1999). Critical power for asymptotic connectivity in wireless networks, Stochastic analysis, control, optimization and applications, Springer, pp.547–566. [42] Bettstetter, C. and Hartmann, C. (2005). Connectivity of wireless multihop networks in a shadow fading environment, Wireless Networks, 11(5), 571–579. [43] Hekmat, R. and Van Mieghem, P. (2006). Connectivity in wireless ad-hoc networks with a log-normal radio model, Mobile networks and applications, 11(3), 351–360. [44] Agrawal, P. and Patwari, N. (2009). Correlated link shadow fading in multi-hop wireless networks, IEEE Trans. Wireless Commun., 8(8). [45] Lu, S., May, J. and Haines, R.J. (2014). Reliability modeling and prediction of wireless multi-hop networks with correlated shadowing, Proc. IEEE PIMRC, pp.1663–1668. [46] Doulliez, P. and Jamoulle, E. (1972). Transportation networks with random arc capacities, Revue française d’automatique, informatique, recherche opérationnelle. Recherche opérationnelle, 6(V3), 45–59. [47] Grimmett, G. and Welsh, D. (1982). Flow in networks with random capacities, Stochastics: An International Journal of Probability and Stochastic Processes, 7(3), 205–229. [48] Yeung, R.W. (2008). Information Theory and Network Coding, Incorporated Springer Publishing Company. [49] Koetter, R. and Medard, M. (2002). Beyond routing: an algebraic approach to network coding, Proc. IEEE INFOCOM, pp.122–130. [50] Guo, B., Liu, Y. and Zhou, C. (2014). Exploit Network Coding Over GF (2q) for Multi-user Cooperative Wireless Networks, International Journal of Wireless Inf. Networks, 21(1), 1–14. [51] Chen, Y., Kishore, S. and Li, J. (2006). Wireless diversity through network coding, Proc. IEEE WCNC, pp.1681–1686. [52] Li, S.Y., Yeung, R. and Cai, N. (2003). Linear network coding, IEEE Trans. Inf. Theory, 49(2), 371–381. [53] Tan, M., Yeung, R.W., Ho, S.T. and Cai, N. (2011). A Unified Framework for Linear Network Coding, IEEE Trans. Inf. Theory, 57(1), 416–423. [54] Nistor, M., Lucani, D., Vinhoza, T., Costa, R. and Barros, J. (2011). On the Delay Distribution of Random Linear Network Coding, IEEE J. Sel. Areas Commun., 29(5), 1084–1093. [55] Di Renzo, M., Iezzi, M. and Graziosi, F. (2013). On Diversity Order and Coding Gain of Multisource Multirelay Cooperative Wireless Networks With Binary Network Coding, IEEE Trans. Veh. Technol., 62(3), 1138–1157. 98 [56] Koetter, R. and Médard, M. (2003). An algebraic approach to network coding, IEEE/ACM Transactions on Networking (TON), 11(5), 782–795. [57] Koetter, R. and Kschischang, F.R. (2008). Coding for errors and erasures in random network coding, IEEE Trans. Inf. Theory, 54(8), 3579–3591. [58] Mohajer, S., Jafari, M., Diggavi, S. and Fragouli, C. (2009). On the capacity of multisource non-coherent network coding, Proc. IEEE ITW, pp.130–134. [59] Siavoshani, M., Mohajer, S., Fragouli, C. and Diggavi, S. (2011). On the Capacity of Noncoherent Network Coding, IEEE Trans. Inf. Theory, 57(2), 1046–1066. [60] Siavoshani, M., Yang, S. and Yeung, R. (2012). Non-coherent network coding: An arbitrarily varying channel approach, Proc. IEEE ISIT, pp.1672–1676. [61] Dougherty, R., Freiling, C. and Zeger, K. (2005). Insufficiency of linear coding in network information flow, IEEE Trans. Inf. Theory, 51(8), 2745–2759. [62] Zhang, S., Liew, S.C. and Lam, P.P. (2006). Hot topic: physical-layer network coding, Proc. ACM MobiCom, pp.358–365. [63] Zhang, S., Liew, S.C. and Lu, L. (2008). Physical Layer Network Coding Schemes over Finite and Infinite Fields, Proc. IEEE GLOBECOM, pp.1–6. [64] Nazer, B. and Gastpar, M. (2011). Reliable Physical Layer Network Coding, Proc. IEEE, 99(3), 438–460. [65] Li, Y., Long, H., Peng, M. and Wang, W. (2014). Spectrum Sharing With Analog Network Coding, IEEE Trans. Veh. Technol., 63(4), 1703–1716. [66] Ho, T., Koetter, R., Medard, M., Karger, D. and Effros, M. (2003). The benefits of coding over routing in a randomized setting, Proc. IEEE ISIT, p.442. [67] Chou, P.A., Wu, Y. and Jain, K. (2003). Practical network coding, Proc. Allerton Conf. Communication, Control, and Computing, Monticello, IL. [68] Wang, M. and Li, B. (2007). R2: Random Push with Random Network Coding in Live Peer-to-Peer Streaming, IEEE J. Sel. Areas Commun., 25(9), 1655–1666. [69] Chiti, F., Fantacci, R., Schoen, F. and Tassi, A. (2013). Optimized Random Network Coding for Reliable Multicast Communications, IEEE Commun. Lett., 17(8), 1624–1627. [70] Ho, T., Leong, B., Koetter, R., Medard, M., Effros, M. and Karger, D.R. (2008). Byzantine Modification Detection in Multicast Networks With Random Network Coding, IEEE Trans. Inf. Theory, 54(6), 2798–2803. [71] Seong, J.T. (2014). Bounds on Decoding Failure Probability in Linear Network Coding Schemes with Erasure Channels, IEEE Commun. Lett., 18(4), 648–651. 99 [72] Chiasserini, C.F., Viterbo, E. and Casetti, C. (2013). Decoding Probability in Random Linear Network Coding with Packet Losses, IEEE Commun. Lett., 17(11), 1–4. [73] Bao, X. and Li, J. (2006). A Unified Channel-Network Coding Treatment for User Cooperation in Wireless Ad-Hoc Networks, Proc. IEEE ISIT, pp.202–206. [74] Luby, M. (2002). LT codes, Proc. IEEE Symposium on Foundations of Computer Science, pp.271–280. [75] Shokrollahi, A. (2006). Raptor codes, IEEE Tran. Inf. Theory, 52(6), 2551–2567. [76] Usman, M. and Dunlop, J. (2005). A Testbed for Assessment of Fountain Codes for Wireless Channels, Proc. European Wireless, pp.1–7. [77] Erez, U., Wornell, G. and Trott, M. (2005). Rateless space-time coding, Proc. IEEE ISIT, pp.1937–1941. [78] Palanki, R. and Yedidia, J.S. (2004). Rateless codes on noisy channels, Proc. IEEE ISIT, p. 38. [79] Beimel, A., Dolev, S. and Singer, N. (2004). RT oblivious erasure correcting, Proc. IEEE ITW, pp.236–241. [80] Krohn, M., Freedman, M. and Mazieres, D. (2004). On-the-fly verification of rateless erasure codes for efficient content distribution, Proc. IEEE Symposium on Security and Privacy, pp.226–240. [81] Castura, J. and Mao, Y. (2006). Rateless coding over fading channels, IEEE Commun. Lett., 10(1), 46–48. [82] Castura, J. and Mao, Y. (2007). Rateless Coding for Wireless Relay Channels, IEEE Trans. Wireless Commun., 6(5), 1638–1642. [83] Liu, X. and Lim, T.J. (2009). Fountain codes over fading relay channels, IEEE Trans. Wireless Commun., 8(6), 3278–3287. [84] Erez, U., Trott, M. and Wornell, G.W. (2012). Rateless Coding for Gaussian Channels, IEEE Trans. Inf. Theory, 58(2), 530–547. [85] Rahnavard, N., Vellambi, B. and Fekri, F. (2007). Rateless Codes With Unequal Error Protection Property, IEEE Trans. Inf. Theory, 53(4), 1521–1532. [86] Nabar, R., Bolcskei, H. and Kneubuhler, F. (2004). Fading relay channels: performance limits and space-time signal design, IEEE J. on Sel. Areas in Commun., 22(6), 1099 – 1109. [87] Zhao, Y., Adve, R. and Lim, T.J. (2006). Symbol error rate of selection amplify-and-forward relay systems, IEEE Commun. Lett., 10(11), 757–759. [88] Laneman, J.N., Tse, D.N.C. and Wornell, G.W. (2004). Cooperative diversity in wireless networks: efficient protocols and outage behavior, IEEE Trans. Inf. Theory, 50(12), 3062–3080. 100 [89] Kim, Y.H. (2008). Capacity of a Class of Deterministic Relay Channels, IEEE Trans. Inf. Theory, 54(3), 1328–1329. [90] Nazer, B. and Gastpar, M. (2008). Compute-and-forward: Harnessing interference with structured codes, Proc. IEEE ISIT, pp.772–776. [91] Can, B., Yomo, H. and De Carvalho, E. (2007). Link adaptation and selection method for OFDM based wireless relay networks, Journal of Commun. and Networks, 9(2), 118–127. [92] Riihonen, T., Werner, S. and Wichman, R. (2011). Hybrid Full-Duplex/Half-Duplex Relaying with Transmit Power Adaptation, IEEE Trans. Wireless Commun., 10(9), 3074 –3085. [93] Yi, N., Ma, Y. and Tafazolli, R. (2013). Joint Rate Adaptation and Best-Relay Selection Using Limited Feedback, IEEE Trans. Wireless Commun., 12(6), 2797–2805. [94] Zhao, L., Mark, J.W. and Yoon, Y.C. (2001). A combined link adaptation and incremental redundancy protocol for enhanced data transmission, Proc. IEEE GLOBECOM, pp.1277–1281. [95] Kim, S.H. and Jung, B.C. (2014). On the Optimal Link Adaptation in Linear Relay Networks With Incremental Redundancy HARQ, IEEE Commun. Lett., 18(8), 1411–1414. [96] Azarian, K., El Gamal, H. and Schniter, P. (2005). On the achievable diversity-multiplexing tradeoff in half-duplex cooperative channels, IEEE Trans. Inf. Theory, 51(12), 4152–4172. [97] Molisch, A., Mehta, N., Yedidia, J.S. and Zhang, J. (2007). Performance of Fountain Codes in Collaborative Relay Networks, IEEE Trans. Wireless Commun., 6(11), 4108–4119. [98] Ravanshid, A., Lampe, L. and Huber, J. (2011). Dynamic Decode-and-Forward Relaying using Raptor Codes, IEEE Trans. Wireless Commun., 10(5), 1569–1581. [99] Tian, S., Li, Y. and Vucetic, B. (2013). A rateless code for dynamic decode-and-forward relaying in wireless relay networks, Proc. IEEE WCNC, pp.3551–3556. [100] Bassoli, R., Marques, H., Rodriguez, J., Shum, K. and Tafazolli, R. (2013). Network Coding Theory: A Survey, IEEE Commun. Surveys Tuts., 15(4), 1950–1978. [101] Di Renzo, M., Iezzi, M. and Graziosi, F. (2013). Error Performance and Diversity Analysis of Multi-Source Multi-Relay Wireless Networks with Binary Network Coding and Cooperative MRC, IEEE Trans. Wireless Commun., 12(6), 2883–2903. [102] Nasri, A., Schober, R. and Uysal, M. (2010). Error Rate Performance of Network-Coded Cooperative Diversity Systems, Proc. IEEE GLOBE- COM, pp.1–6. 101 [103] Nasri, A., Schober, R. and Uysal, M. (2013). Performance and Optimization of Network-Coded Cooperative Diversity Systems, IEEE Trans. Commun., 61(3), 1111–1122. [104] Iezzi, M., Di Renzo, M. and Graziosi, F. (2011). Network Code Design from Unequal Error Protection Coding: Channel-Aware Receiver Design and Diversity Analysis, Proc. IEEE ICC, pp.1–6. [105] Iezzi, M., Di Renzo, M. and Graziosi, F. (2011). Closed-Form Error Probability of Network-Coded Cooperative Wireless Networks with Channel-Aware Detectors, Proc. IEEE GLOBECOM, pp.1–6. [106] Khirallah, C., Vukobratovic, D. and Thompson, J. (2012). Performance Analysis and Energy Efficiency of Random Network Coding in LTE-Advanced, IEEE Trans. Wireless Commun., 11(12), 4275–4285. [107] Vukobratovic, D., Khirallah, C., Stankovic, V. and Thompson, J.S. (2014). Random Network Coding for Multimedia Delivery Services in LTE/LTE-Advanced, IEEE Transactions on Multimedia, 16(1), 277–282. [108] Dummit, D. and Foote, R. (2004). Abstract Algebra, Wiley. [109] Rotman, J. (1999). An Introduction to the Theory of Groups, Graduate Texts in Mathematics, Springer New York. [110] Klein, A.J., Lewis, J.B. and Morales, A.H. (2013). Counting matrices over finite fields with support on skew Young diagrams and complements of Rothe diagrams, Journal of Algebraic Combinatorics, 39(2), 429–456. [111] Mahmoud, H.M., Mousa, A.S. and Saleem, R. (2010). Channel estimation based in comb-type pilots arrangement for OFDM system over time varying channel, Journal of Networks, 5(7), 766–772. [112] Khan, S., Gani, A., Wahab, A.W.A., Guizani, M. and Khan, M.K. (2017). Topology discovery in software defined networks: Threats, taxonomy, and state-of-the-art, IEEE Commun. Surveys Tuts., 19(1), 303–324. [113] Motamedi, R., Rejaie, R. and Willinger, W. (2015). A survey of techniques for Internet topology discovery, IEEE Commun. Surveys Tuts., 17(2), 1044–1065. [114] Deo, N. (2016). Graph theory with applications to engineering and computer science, Courier Dover Publications. [115] Kuhn, H.W. (1955). The Hungarian Method for the assignment problem, Naval Research Logistics Quarterly, 2, 83–97. [116] Munkres, J. (1957). Algorithms for the Assignment and Transportation Problems, Journal of the Society for Industrial and Applied Mathematics, 5(1), 32–38. [117] Peng, C., Zhang, Q., Zhao, M., Yao, Y. and Jia, W. (2008). On the Performance Analysis of Network-Coded Cooperation in Wireless Networks, IEEE Trans. Wireless Commun., 7(8), 3090–3097. 102 [118] Pereira, Z.C., Ton, T.H., Rebelatto, J.L., Souza, R.D. and Uchôa-Filho, B.F. (2018). Generalized Network-Coded Cooperation in OFDMA Communications, IEEE Access, 6, 6550–6559. [119] Wong, C.Y., Cheng, R., Lataief, K. and Murch, R. (1999). Multiuser OFDM with adaptive subcarrier, bit, and power allocation, IEEE J. Sel. Areas Commun., 17(10), 1747–1758. [120] Li, Y., Louie, R.H.Y. and Vucetic, B. (2010). Relay Selection With Network Coding in Two-Way Relay Channels, IEEE Trans. Veh. Technol., 59(9), 4489–4499. [121] Wang, Z. and Giannakis, G.B. (2003). A simple and general parameterization quantifying performance in fading channels, IEEE Trans. Commun., 51(8), 1389–1398. [122] Zheng, L. and Tse, D.N.C. (2003). Diversity and multiplexing: A fundamental tradeoff in multiple-antenna channels, IEEE Transactions on information theory, 49(5), 1073–1096. [123] French, R.C. (1979). The effect of fading and shadowing on channel reuse in mobile radio, IEEE Trans. Veh. Techol., 28(3), 171–181. [124] Colbourn, C.J. (1987). The combinatorics of network reliability, Oxford University Press, Inc. [125] Andrews, G.E. (1994). Number theory, Courier Corporation. [126] Wang, Z. and Giannakis, G.B. (2003). A simple and general parameterization quantifying performance in fading channels, IEEE Trans Commun, 51(8), 1389–1398. 103 104 APPENDICES APPENDIX A : An Example of Orbit Counting. 105 106 APPENDIX A: An Example of Orbit Counting We give an example to explain the action of the symmetric group on the set of solutions and on columns of matrices, and its orbits. Assume that there are M = 3 sources and N = 4 relays. For t = 3, three rows of the 4× 3 matrix A given in (3.8) have (exactly one) forced zeros. How these forced zeros are distributed among the columns of A corresponds to the non-negative integer solutions of the equation ϕ1 + ϕ2 + ϕ3 = 3, where ϕi denotes the number of forced zeros in the ith column of A? The number of such solutions is (3+3−13 ) = 10. They are (ϕ1, ϕ2, ϕ3) =(3, 0, 0), (0, 3, 0), (2, 1, 0), (0, 0, 3), (2, 0, 1), (0, 2, 1), (1, 2, 0), (0, 1, 2), (1, 0, 2), (1, 1, 1). (A.1) The symmetric group of order 3! acts on this set by permuting the solutions. For instance, this action transforms the solution (0, 1, 2) to (2, 0, 1). This means in particular that the solutions (0, 1, 2) and (2, 0, 1) are in the same orbit. We see that the orbits are the following three sets {(3, 0, 0), (0, 3, 0), (0, 0, 3)}, {(2, 1, 0), (2, 0, 1), (0, 2, 1), (1, 2, 0), (1, 0, 2), (0, 1, 2)}, {(1, 1, 1)}. (A.2) Note that the set of all solutions is the disjoint union of these orbits. In each orbit, there is a unique solution such that ϕ1 ≤ ϕ2 ≤ ϕ3. So each orbit corresponds to a partition of 3. For instance, the first orbit corresponds to the partition (0, 0, 3), the second orbit corresponds to the partition (0, 1, 2), and the third orbit corresponds to the partition (1, 1, 1). To calculate the number of elements of each orbit, we need to calculate the index of the stabilizer of each of these partitions. Note that a permutation fixes (0, 0, 3) if and only if it does not move the third solution ϕ3 = 3 (but it may interchange the first two solutions ϕ1 and ϕ2). Thus, the stabilizer of (0, 0, 3) has 2! elements. Therefore the number of elements of the orbit containing (0, 0, 3) is 3!2! = 3.     0 0 0     ,     0 0 0     ,     0 0 0     ,     0 0 0     ,     0 0 0     ,     0 0 0         0 0 0     ,     0 0 0     ,     0 0 0     ,     0 0 0     ,     0 0 0     ,     0 0 0     . (A.3) 107 This number corresponds to the expression M !ϕ(δ) . Consider the partition δ = (0, 0, 3),so that ϕ1 = 0, ϕ2 = 0, and ϕ3 = 3. Then, it can be written as F (p) = {f |ϕf 6= ϕf+1} ∩ {1, 2} = {2}. (A.4) Hence F (δ) = {f1} with f1 = 2 where g = 1 also, and ϕ(δ) : = f1!(f2 − f1)!(f3 − f2)! · · · (fg − fg−1)!(M − fg)! = 2!(3− 2)!, (A.5) where the orbit has M !ϕ(δ) = 3!2!(3−2)! = 3 elements. Now let us explain the action of S3 on the set {M}. For each solution of ϕ1 + ϕ2 + ϕ3 = 3, there is a set in {M}. Indeed, the set is equal to {M} = {M3,0,0,M0,3,0,M0,0,3,M2,1,0,M2,0,1,M0,2,1, M1,2,0,M0,1,2,M1,0,2,M1,1,1} . (A.6) For instance, as the action of S3 on the solutions transforms the solution (2, 0, 1) to the solution (0, 1, 2), it follows that the action of S3 on {M} transforms the set M2,0,1 to the set M0,1,2. Therefore, the orbits of the S3 action on {M} are the following three sets: {M3,0,0,M0,3,0,M0,0,3}, {M2,1,0,M2,0,1,M0,2,1,M1,2,0,M0,1,2,M1,0,2}, and {M1,1,1}. For instance, M2,0,1 is the set of all 4 × 3 matrices whose rows have at most one forced zeros and whose first column has 2 forced zeros and whose second column has no forced zeros and whose third column has one forced zero. Moreover, |M2,0,1| = C(2, 0, 1) = 4!2!0!1!(4−3)! = 12. Indeed, M2,0,1 consists of the following 12 differentmatrices given in (A.3). We also calculate that |M3,0,0| = |M0,3,0| = |M0,0,3| = 4 |M2,1,0| = |M2,0,1| = |M0,2,1| = |M1,2,0| = |M0,1,2| = |M1,0,2| = 12 |M1,1,1| = 24. (A.7) Therefore, in total there are 108 possible configurations of t which is also indicated by bt. If we choose any two sets M and M from the same orbit of the action of S3 on {M} and if we choose any two matrices M ∈ M and M ∈ M, then the number of matrices of rank r of the type of the first matrix M and the second matrix M are the same. To calculate the numbers |Ak,l,t| and |Bk,l,t| for each possible 108 types, it is enough to consider any one of the matrices in any set in each of the orbit. As the orbit sizes are different, in calculating the successful decoding probability for a fixed t = 3, instead of summing over all 108 possibilities, we sum over orbits, resulting in the sum containing 3 summands, but each summand must be multiplied by C(ϕ1, ϕ2, ϕ3)N ′ 108where N ′ is the number of elements in the orbit. To be more precise, letting the orbits be: {(3, 0, 0), (0, 3, 0), (0, 0, 3)}, {(2, 1, 0), (2, 0, 1), (0, 2, 1), (1, 2, 0), (1, 0, 2), (0, 1, 2)}, {(1, 1, 1)}. (A.8) 108 CURRICULUM VITAE Name Surname: Semiha TEDIK BASARAN Place and Date of Birth: BOLU 29.10.1988 E-Mail: tedik@itu.edu.tr EDUCATION: • B.Sc.: 2011, Istanbul Technical University, Electrical-Electronics Engineering Faculty, Department of Electronics and Communications Engineering • M.Sc.: 2013, Istanbul Technical University, Electrical-Electronics Engineering Faculty, Department of Electronics and Communications Engineering PROFESSIONAL EXPERIENCE AND REWARDS: • 2011-2019 Research Assistant at Istanbul Technical University in the Department of Electronics and Communication Engineering • 2017 Visiting Researcher at RWTH Aachen University in the Institute for Communication Technologies and Embedded Systems (ICE) • 2018 Visiting Researcher at Alexander Technological Educational Institute of Thessaloniki (ATEITHE) in Department of Informatics PUBLICATIONS, PRESENTATIONS AND PATENTS ON THE THESIS: • Patent Applications 1. Kurt, G.K., and Basaran, S.T. A Network Coded Cooperative Distributed Wireless Communication and Data Storage Technique, EP3170300B1, US10117132B2, JP2018522511A, PCT/TR2016/050139, Oct. 2018 (Triadic Patent). 2. Kurt, G.K., Uysal, M., Basaran, S.T., and Altunbas, I., Random Network Coding in Orthogonal Frequency Division Multiple Access (OFDMA) Networks Using Control Signaling, PCT/TR2016/050410. • Book Chapters 1. Basaran, S.T., Heidarpour, A., Gokceli, S, Kurt, G.K., Uysal, M., and Altunbas, I. (2018). Implementation of Network Coding in Wireless Systems, in Network Coding and Subspace Designs, 295-317, Springer. 109 • Journals 1. Basaran, S.T., Kurt, G.K., Ozdemir, E., and Yaraneri, E. (2017). Error Performance Analysis of Random Network Coded Cooperation Systems, in IEEE Transactions on Wireless Communications, vol.16, no.8, August. 2. Basaran, S.T. and Kurt, G.K. (2017). I˙s¸birlikli Ag˘ Kodlamalı OFDMA Sistemleri için Röle Seçim Teknikleri, EMO Bilimsel Dergi, c. 7, no.13, s. 17 – 23. 3. Basaran, S.T., Kurt, G.K., Uysal, M. and Altunbas, I. (2016). A tutorial on network coded cooperation, in IEEE Communications Surveys & Tutorials, vol. 18, no. 4, pp. 2970-2990, Fourthquarter. 4. Basaran, S.T. and Kurt, G.K. (2016) Joint Subcarrier and Power Allocation in OFDMA Systems for Outage Minimization, in IEEE Communications Letters, vol. 20, no. 10, pp. 2007-2010, October. 5. Basaran, S.T. and Kurt, G.K. Wireless Channel Induced Coding, under review. 6. Basaran, S.T., Kurt, G.K., and Kschishang, F. Diversity Gain Analysis of Communication Networks Through Network Reliability Concept, under review. • International Conferences 1. Basaran, S.T., Kurt, G.K., and Chatzigeorgiou I. (2018). On The Performance of NCC-OFDMA with Single Relay Selection, in Proc. Global Information Infrastructure and Networking Symposium, Thessaloniki, Greece, 23-25 October. • National Conferences 1. Basaran, S.T., Kurt, G.K., Engin B., Altunbas, I. (2015) Joint Power and Subcarrier Allocation in OFDMA Systems, in Proc. 23rd Signal Processing and Communications Applications Conference (SIU), May. OTHER PUBLICATIONS, PRESENTATIONS AND PATENTS: • Patent Applications 1. Altun, U. Basaran, S.T., Kurt, G.K., and Ozdemir, E. (2018). A Joint Data Transmission and Authentication Technique over the Wireless Multiple Access Channel, applied to Turkish Patent Institute, 2018/ 11274, August. • Journals 1. Basaran, S.T., Kurt, G.K., Gunel, G. O., Schmeink, A., Ascheid, G. and Dartmann, G. (2018). The Safety Analysis: Disagreement of Wireless Communication-Based Consensus, in IEEE Wireless Communications Letters, vol. 7, no. 6, pp. 998-1001, Dec. 2018. 110 2. Ensezgin, T., Gökceli, S., Basaran, S.T., and Kurt, G.K. (2017). Performance Analysis of Deep Space Networks with Network Coded Cooperation, Istanbul University - Journal of Electrical & Electronics Engineering, vol. 17, pp. 3319- 3325, July. 3. Gokceli, S., Alakoca, H., Basaran, S.T. and Kurt, G.K. (2016). OFDMA-based Network Coded Cooperation: Design and Implementation Using Software Defined Radio Nodes, EURASIP Journal on Advances in Signal Processing, November. 4. Cepheli, O., Tedik, S. and Kurt, G.K. (2014). A High Data Rate Wireless Communication System with Improved Secrecy: Full Duplex Beamforming, IEEE Communications Letters, vol. 18, no. 6, pp. 1075-1078, June. 5. Basaran, S.T., Kurt, G.K., and Chatzimisios, P. Energy Efficient Over-the-Air Computation Scheme for the Densely Deployed IoT Networks, under review. • International Conferences 1. Chatzigeorgiou, I., Kurt, G.K., Basaran, S.T., and Khan, A.S. (2019). On the Decoding Failure Probability of Random Network Coded Cooperation, in Proc. IEEE Vehicular Technology Conference, accepted for presentation, 28 April-1 May. 2. Gokceli, S., Basaran, S.T., and Kurt, G.K. (2017). Implementing Cooperative Communication Protocols: Decode and Forward Case Study, in Proc. IEEE International Black Sea Conference on Communications and Networking (BlackSeaCom), Istanbul, Turkey, 5-8 June, 2017. 3. Gokceli, S., Cepheli, O., Basaran, S.T., Kurt, G.K., Dartmann, G., and Ascheid, G. (2017). How Effective is the Artificial Noise Real-Time Analysis of a PHY Security Scenario, in Proc. IEEE Globecom Workshops (GC Wkshps), pp. 1-7. 4. Altun, U., Basaran, S.T., Alakoca, H., and Kurt, G.K. (2017). A testbed based verification of joint communication and computation systems, in 25th Telecommunication Forum (TELFOR), (pp. 1-4). 5. Tekbıyık, K., Basaran, S.T., Gurbuz, U., and Kurt, G.K. (2017). The usage of relay-aided communication techniques in LTE networks: Layer 3 relaying, in 10th International Conference on Electrical and Electronics Engineering (ELECO), Bursa, pp. 642-645. 6. Gokceli, S., Basaran, S.T., and Kurt, G.K. (2016). A Testbed for Image Transmission over a Network Coded Cooperation System, in Proc. International Conference on Software, Telecommunications and Computer Networks, Split, Croatia, 22-24 September. 7. Calik, O., Ensezgin, T., Oztaner, B., Gokceli, S., Basaran, S.T., and Kurt, G.K. (2016). Network Coded Cooperation in Delay Tolerant Networks, in Proc. IEEE Int. Conf. on Wireless for Space and Extreme Environments (WiSEE), Aachen, Germany, 26-29 September. 8. Tedik, S. and Kurt, G.K. (2014) Practical full duplex physical layer network coding, in Proc. IEEE 79th Vehicular Technology Conference (VTC Spring), 1-4. 111 9. Tedik, S. and Kurt, G.K. (2013). Fractionally spaced self-interference canceler for full-duplex communication systems, in Proc. IEEE Symposium on Computers and Communications (ISCC). • National Conferences 1. Cokona, K., Basaran, S.T., Durmaz, E., Oral, E., Ascheid G., Dartmann, G., and Kurt, G.K. (2018). Sönümlemeli Kanalın Çok Etmenli Sistemlerde Konsensüse Ulas¸maya Etkisi in 26th Signal Processing and Communications Applications Conference (SIU), May. 2. Gokceli, S., Tekpınar, M., Topal, O. A., Basaran, S.T., Kurt, G.K. (2016). Full-Duplex Transmission: A Software Defined Radio Implementation in 24th Signal Processing and Communications Applications Conference (SIU), May. 3. Engin, B., Altunbas, I., Basaran, S.T., and Kurt, G.K. (2015). Different Numbers of Subcarrier Allocation in OFDMA Systems via Random Bipartite Graphs, in 23rd Signal Processing and Communications Applications Conference (SIU), May. 4. Tedik, S. and Kurt, G.K. (2013). Full-duplex relaying communication, in 21st Signal Processing and Communications Applications Conference (SIU), April. 112