Today’s communication systems are in need of spectrally efficient and high throughput techniques more than ever because of high data rate applications and the scarcity and expense of bandwidth. To cope with increased data rate demands, more base stations are needed which is not cost and energy efficient in cellular networks. It has been shown that wireless relay networks can provide higher network throughput and increase power efficiency with low complexity and cost. Furthermore, network resources can be utilized more efficiently by using network coding in relay networks. A wireless relay network in which multiple nodes exchange information with the help of relay node(s) is called a multi-way relay channel (MWRC). MWRCs are expected to be an integral part of next generation wireless standards. The main focus of this dissertation is the investigation of transmission schemes in an MWRC to improve the throughput and error performance. An MWRC with full data exchange is assumed in which a half-duplex relay station (RS) is the enabler of communication. One of the challenges with signal demodulation in MWRCs is the existence of ambiguous points in the received constellation. The first part of this dissertation investigates a transmission scheme for full data exchange in MWRC that benefits from these points and improves its throughput by 33% compared to traditional relaying. Then an MWRC is considered where a RS assists multiple nodes to exchange messages. A different approach is taken to avoid ambiguous points in the superposition of user symbols at the relay. This can be achieved by employing complex field network coding (CFNC) which results in full data exchange in two communication phases. CFNC may lead to small Euclidean distances between constellation points, resulting in poor error performance. To improve this performance, the optimal user precoding values are derived such that the power efficiency of the relay constellation is highest when channel state information is available at the users. The error performance of each user is then analyzed and compared with other relaying schemes. Finally, focusing on the uplink of multi-way relay systems, the performance of an MWRC is studied in which users can employ arbitrary modulation schemes and the links between the users and the relay have different gains, e.g. Rayleigh fading. Analytical expressions for the exact average pairwise error probability of these MWRCs are derived. The probability density function (PDF) and the mean of the minimum Euclidean distance of the relay constellation are closely approximated, and a tight upper bound on the symbol error probability is developed. / Graduate

Network coding is a technique used to increase the capacity of a network by combining messages sent over the network. The combined messages could be separated by using sufficient original messages which were used to combine the messages. Network coding can be implemented in different layers of the 051 stack, but to date a complete comparison between different implementations of network coding has not been done. The goal of this dissertation is to implement a wireless node model with network coding in the MAC layer and evaluate the performance characteristics of reference networks that implement the new node model. This will serve as the first step of a greater goal, namely finding the most favourable position in the 051 stack to implement network coding. The characteristics of the different implementations of network coding are presented in this dissertation. Simulations were done in OPNET® to find further attributes concerning the implementation of network coding in the MAC layer. The simulation process used is presented and explained, and the results from the simulations are analysed. Network coding in the simulations was implemented opportunistically. The results show that the more often different nodes send frames to the coding node, the better network coding performs. The work contributes to finding the best layer for implementing network coding for its increased throughput. A benchmark network was created so that network coding could be implemented in all the layers of the 051 stack, and then be compared to each other. An implementation of network coding in the MAC layer was simulated and analyzed. We conclude that, because there are so many different purposes for which networks are used, a single instance of network coding is unlikely to be similarly beneficial to all purposes. There still remains work to find the most favourable position for network coding in the 051 stack for all the different types of network coding. / Thesis (M. Ing. (Computer and Electronical Engineering))--North-West University, Potchefstroom Campus, 2011

Dans cette thèse, nous nous intéressons à l’application du codage réseau pour garantir la qualité de service (QoS) dans les réseaux sans fil multi-sauts. Comme le support de transmission est partagé, les réseaux sans fil souffrent de l’impact négatif des interférences sur la bande passante. Il est alors intéressant de proposer une approche basée sur le codage réseau qui prenne en compte ces interférences durant le processus de routage. Dans ce contexte, nous proposons d’abord un algorithme minimisant l’impact des interférences pour des flux unicast tout en respectant la bande passante qu’ils exigent. Puis, nous le combinons avec le codage réseau afin d’augmenter le nombre des flux acceptés et avec le contrôle de topologie pour améliorer davantage la gestion des interférences. Nous montrons par simulation l’intérêt de combiner les trois domaines : codage réseau, gestion des interférences et contrôle de topologie. Nous abordons également la gestion du délai pour les flux multicast et utilisons le codage réseau basé sur les générations (GBNC) qui combine les paquets par bloc. La plupart des travaux portant sur le GBNC considèrent une taille de génération fixe mais à cause des variations de l’état du réseau le délai de décodage et de récupération du bloc de paquets peut varier, dégradant la QoS. Pour résoudre ce problème, nous proposons une méthode qui ajuste la taille de la génération de façon dynamique pour respecter un certain délai de décodage avec prise en compte des contextes réseau et contenu. De plus, nous améliorons notre approche pour contrecarrer les pertes des acquittements. Puis, nous proposons de l’utiliser dans un réseau de domicile pour la diffusion de vidéo à la demande. Notre solution améliore la QoS et la qualité d’expérience pour l’utilisateur final sans équipement additionnel. Finalement, nous abordons un sujet plus théorique dans lequel nous présentons un nouveau réseau basé sur le schéma Butterfly pour des flux multi-sources multi-destinations. Nous caractérisons la taille du buffer du nœud source en utilisant la théorie des files d’attente et montrons qu’elle correspond aux résultats de simulation. / In this thesis we deal with the application of Network Coding to guarantee the Quality of Service (QoS) for wireless multi-hop networks. Since the medium is shared, wireless networks suffer from the negative interference impact on the bandwidth. It is thus interesting to propose a Network Coding based approach that takes into account this interference during the routing process. In this context, we first propose an algorithm minimizing the interference impact for unicast flows while respecting their required bandwidth. Then, we combine it with Network Coding to increase the number of admitted flows and with Topology Control to still improve the interference management. We show by simulation the benefit of combining the three fields: Network Coding, interference consideration and Topology Control. We also deal with delay management for multicast flows and use the Generation-Based Network Coding (GBNC) that combines the packets per blocks. Most of the works on GBNC consider a fixed generation size. Because of the network state variations, the delay of decoding and recovering a block of packets can vary accordingly degrading the QoS. To solve this problem, we propose a network-and content-aware method that adjusts the generation size dynamically to respect a certain decoding delay. We also enhance it to overcome the issue of acknowledgement loss. We then propose to apply our approach in a Home Area Network for Live TV and video streaming. Our solution provides QoS and Quality of Experience for the end user with no additional equipment. Finally, we focus on a more theoretical work in which we present a new Butterfly-based network for multi-source multi-destination flows. We characterize the source node buffer size using the queuing theory and show that it matches the simulation results.

Codage de réseau (NC) a gagné beaucoup d'attention de la recherche comme un candidat potentiel pour résoudre la demande de plus grande efficacité spectrale des communications modernes sans fil. De nombreux travaux de recherche ont étudié la performance des réseaux NC-aidés telles que le débit et la capacité de panne. Cependant, l'analyse de la NC dans des systèmes pratiques où NC est combiné avec d'autres techniques telles que le codage de canal est encore immature pour comprendre pleinement son potentiel de performance. Dans cette thèse, nous nous efforçons de concevoir des récepteurs de haute performance et d'analyser sa performance pour les réseaux de coopération réseau codé dans des scénarios pratiques. Tout d’abord, nous vous proposons deux Itératif Décodage de Réseau /Canal (IDRC) algorithmes pour le canal de relais d'accès multiple (MARC) avec deux systèmes de relais de notables nommés décodage-et-transfert et démoduler et transfert. L'algorithme du RIDC fonctionne sur la base de méthodes de décodage turbo-comme et réduit l'impact du problème de la propagation de l'erreur à l'aide d'un modèle de récepteur de canal courant. Tant parfaite information de la parfait CSI et imparfait CSI au côté récepteur sont étudiées. Nous proposons un procédé pratique qui transmet la version quantifiée des erreurs de décodage de relais à la destination. Il est démontré que les algorithmes proposés réaliser un gain de diversité complète et surpasse les solutions qui ne prennent pas soin de propagation d'erreur significative. Nous montrons également que le nombre de symboles pilotes ne concerne que le gain de codage, mais a un impact négligeable sur l'ordre de la diversité, alors que le niveau de quantification affecte à la fois la diversité et le gain de codage.Deuxièmement, nous proposons un Conjoint Décodage de Réseau/Canal Près Optimal (CDRCPO) algorithme pour le MARC qui permet d'analyser le taux de bits du système d'erreur (BER). L'algorithme de CDRCPO exécute le décodage de réseau et de décodage de canal en une seule étape de décodage du code superbe, qui se compose de tous les états de treillis de code individuel aux sources via NC. En outre, NC combiné avec la sélection de relais (RS) est considéré et l'ordre de diversité possible est étudié à l'aide de l'analyse de panne. Nous montrons analytiquement que la sélection de relais simple (SRS) permet toujours d'obtenir une ordonnance de la diversité et de la sélection de deux relais multiple (MRS) peut obtenir gain de diversité complète que lorsque le nombre de relais sélectionné dépasse le nombre de sources.En fin, nous proposons un protocole dit relais partielle d'améliorer l'efficacité spectrale pour le codage des réseaux de relais assisté canal. Forme-proche expression du BER et l'ordre de la diversité du système sont calculés pour le relais partiel. Nous montrons, par l'analyse et la simulation, qui avec un code convolutif bon, le relais partiel peut obtenir gain de diversité complète et même gain de codage que le classique (complet) relayer protocole fini région signal-sur-bruit alors qu'il obtient une meilleure utilisation du spectre. De plus, nous proposons un nouveau protocole basé sur le relais partiel dans les réseaux de coopération relayant opportunistes et montrons que ce protocole surpasse de manière significative la coopération sur la NC dans certaines circonstances. / Network coding (NC) has gained much research attention as a potential candidate to solve the demand for higher spectral efficiency of modern wireless communications. Many research papers have investigated the performance of NC-aided networks such as throughput and outage capacity. However, the analysis of NC in practical systems where NC is combined with other techniques such as channel coding is still immature to fully understand its potential performance. In this thesis, we aim to design high performance receivers and analyze its performance for network-coded cooperative networks in practical scenarios.Firstly, we propose two Iterative Network/Channel Decoding (INCD) algorithms for the Multiple-Access Relay Channel (MARC) with two notable relaying schemes named Decode-and-Forward (DF) and Demodulate-and-Forward (DMF). The INCD algorithm operates based on turbo-like decoding methods and reduces the impact of the error propagation problem with the aid of a channel-aware receiver design. Both perfect Channel State Information (CSI) and imperfect CSI at the receiver side are investigated. We propose a practical method that forwards the quantized version of the relay decoding errors to the destination. It is shown that the proposed algorithms achieve full diversity gain and significantly outperforms solutions which do not take care of error propagation. We also show that the number of pilot symbols affects only the coding gain but has a negligible impact on the diversity order, while the quantization level affects both the diversity and coding gain.Secondly, we propose a Near Optimal Joint Network/Channel Decoding (NOJNCD) algorithm for the MARC that allows to analyze the system Bit Error Rate (BER). The NOJNCD algorithm performs network decoding and channel decoding in one decoding step of the super code, which comprises of all trellis states of individual code at the sources via NC. Furthermore, NC combined with Relay Selection (RS) is considered and the achievable diversity order is studied with the aid of outage analysis. We analytically show that Single Relay Selection (SRS) always achieves a diversity order two and Multiple Relay Selection (MRS) can achieve full diversity gain only when the number of selected relays exceeds the number of the sources.Last but not least, we propose a so-called partial relaying protocol to improve the spectral efficiency for channel coding assisted relay networks. Closed-form expression of the BER and the system diversity order are computed for partial relaying. We show, by analysis and simulations, that with a proper Convolutional Code (CC), partial relaying can achieve full diversity gain and same coding gain as the classical (full) relaying protocol in finite signal-to-noise ratio region while it obtains a better spectrum usage. Moreover, we propose a new protocol based on partial relaying in opportunistic relaying cooperative networks and show that this protocol significantly outperforms the NC-based cooperation in some circumstances.

Dans cette thèse, nous avons envisagé l’utilisation des codes en métrique rang pour des applications de communication sans fil en général, et les réseaux de capteurs en particulier. Après avoir introduit les codes en métrique rang, ces codes, qui ont été proposés dans le contexte de la cryptographie, sont adaptés par la suite pour la correction d’erreurs. Pour cela, une étude est faite sur le comportement de ces familles de codes dans un scénario de transmission sans fil en utilisant le codage réseau. Dans ce contexte, trois types d’erreurs sont considérés : le bruit de fond, les erreurs injectés dans le réseau par un utilisateur malveillant et les effacements qui peuvent être dus aux pannes des nœuds. L’analyse qui a été faite sur la famille des codes Low Rank Parity Check (LRPC) a montré que ces derniers sont plus adaptés aux réseaux de capteurs sans fil par rapport aux codes Gabidulin utilisés dans la littérature. Cette analyse a été généralisée dans le contexte multi-sources et a montré que les codes LRPC sont plus efficaces dans ce contexte. Ces contributions apportent un nouveau souffle à l’utilisation des codes en métrique rang et offrent des perspectives de poursuite intéressantes. / In this thesis, we have considered the rank metric codes for wireless sensor networks. Firstly, we have introduced the rank metric codes. Then, we adapted these codes, which were originally dedicated to cryptography applications, for error correction. To this end, we have studied the behavior of the family of rank metric codes in a wireless communication scenario using network coding. In this context, three types of errors are considered, background noise, errors injected into the network by a malicious user and erasures caused by node failures. Our analysis of the Low Rank Parity Check codes (LRPC) has shown that they are more suited to wireless sensor networks and they perform better than Gabidulin codes used in the literature. This analysis has been generalized in the multisource context and has shown that LRPC codes are more efficient in this context compared to Gabidulin codes. These contributions give a new incentive for the use of rank metric codes and offer interesting perspectives.

Lors d'une communication dans un réseau, les nœuds intermédiaires se contentent en général de retransmettre les paquets de données qu'ils reçoivent. Grâce au codage de réseau (NC), ces nœuds intermédiaires peuvent envoyer des combinaisons linéaires des paquets qu'ils ont reçus. Ceci permet une meilleure exploitation de la capacité du réseau et une plus grande robustesse à l'égard de pertes.Cette thèse s'intéresse à une implantation du NC en lien avec TCP (TCP-NC). Grâce à la redondance introduite par le NC, une partie des pertes liées à des liens sans fils peut être compensée. Elle propose en particulier un mécanisme d'adaptation de la redondance introduite par le codage de réseau. Une première partie de cette thèse est consacrée à l'analyse de la dynamique de TCP-NC avec Random Early Detection (RED) comme mécanisme de gestion des files d'attente en utilisant les outils d'optimisation convexe et issus de l’automatique. Nous caractérisons l'équilibre du réseau et les propriétés de stabilité de TCP-Reno en présence de NC. Dans une seconde partie, cette thèse propose un algorithme d'adaptation de la redondance introduite par NC. Dans TCP-NC avec redondance adaptative (TCP-NCAR), cet ajustement se fait grâce à un schéma de différenciation des pertes, qui estime la répartition des pertes entre erreurs de transmission dues aux liens sans fils et pertes liées à la congestion. Les propriétés d'équilibre et de stabilité de TCP-NCAR/RED sont caractérisées. Les résultats théoriques et de simulation montrent que TCP-NCAR adopte une redondance proche de l'optimum quand les taux de perte de paquets sur les liens sans fils sont petits. En outre, le modèle linéarisé autour de l'équilibre montre que TCP-NCAR augmente la taille de la région de stabilité de TCP-Reno. / Communication networks today share the same fundamental principle of operation: information is delivered to their destination by nodes intermediate in a store-and-forward manner.Network coding (NC) is a technique that allows intermediate nodes to send out packets that are linear combinations of previously received information. The main benefits of NC are the potential throughput improvements and a high degree of robustness, which is translated into loss resilience. These benefits have motivated deployment efforts for practical applications of NC, e.g., incorporating NC into congestion control schemes such as TCP-Reno to get a TCP-NC congestion protocol. In TCP-NC, TCP-Reno throughput is improved by sending a fixed amount of redundant packets, which mask part of the losses due, e.g., to channel transmission errors. In this thesis, we first analyze the dynamics of TCP-NC with random early detection (RED) as active queue management (AQM) using tools from convex optimization and feedback control. We study the network equilibrium point and the stability properties of TCP-Reno when NC is incorporated into the TCP/IP protocol stack. The existence and uniqueness of an equilibrium point is proved, and characterized in terms of average throughput, loss rate, and queue length. Our study also shows that TCP-NC/RED becomes unstable when delay or link capacities increases, but also, when the amount of redundant packets added by NC increases. Using a continuous-time model and neglecting feedback delays, we prove that TCP-NC is globally stable. We provide a sufficient condition for local stability when feedback delays are present. The fairness of TCP-NC with respect to TCP-Reno-like protocols is also studied. Second, we propose an algorithm to dynamically adjust the amount of redundant linear combinations of packets transmitted by NC. In TCP-NC with adaptive redundancy (TCP-NCAR), the redundancy is adjusted using a loss differentiation scheme, which estimates the amount of losses due to channel transmission errors and due to congestion. Simulation results show that TCP-NCAR outperforms TCP-NC in terms of throughput. Finally, we analyze the equilibrium and stability properties of TCP-NCAR/RED. The existence and uniqueness of an equilibrium point is characterized experimentally. The TCP-NCAR/RED dynamics are modeled using a continuous-time model. Theoretical and simulation results show that TCP-NCAR tracks the optimal value for the redundancy for small values of the packet loss rate. Moreover, simulations of the linearized model around equilibrium show that TCP-NCAR increases the size of the TCP-Reno stability region. We show that this is due to the compensator effect of the redundancy adaptation dynamics to TCP-Reno. These characteristics of TCP-NCAR allow the congestion window adaptation mechanism of TCP-Reno to react in a smooth way to channel losses, avoiding some unnecessary rate reductions, and increasing the local stability of TCP-Reno.

Most current-generation P2P content distribution protocols use fine-granularity blocks to distribute content in a decentralized fashion. Such systems often suffer from a significant variation in block distributions, such that certain blocks become rare or even unavailable, adversely affecting content availability and download efficiency. This phenomenon is further aggravated by peer dynamics which is inherent in P2P networks. In this thesis, we quantitatively analyze how network coding may improve block availability and introduce resilience to peer dynamics. Since in reality, network coding can only be performed within segments, each containing a subset of blocks, we explore the fundamental tradeoff between the resilience gain of network coding and its inherent coding complexity, as the number of blocks in a segment varies. As another application of the resilience of network coding, we also devise an indirect data collection scheme based on network coding for the purpose of large-scale network measurements.

This thesis investigates channel-coded physical layer network coding, in which the relay directly transforms the noisy superimposed channel-coded packets received from the two end nodes, to the network-coded combination of the source packets. This is in contrast to the traditional multiple-access problem, in which the goal is to obtain each message explicitly at the relay. Here, the end nodes $A$ and $B$ choose their symbols, $S_A$ and $S_B$, from a small non-binary field, $\mathbb{F}$, and use non-binary PSK constellation mapper during the transmission phase. The relay then directly decodes the network-coded combination ${aS_A+bS_B}$ over $\mathbb{F}$ from the noisy superimposed channel-coded packets received from two end nodes. Trying to obtain $S_A$ and $S_B$ explicitly at the relay is overly ambitious when the relay only needs $aS_B+bS_B$. For the binary case, the only possible network-coded combination, ${S_A+S_B}$ over the binary field, does not offer the best performance in several channel conditions. The advantage of working over non-binary fields is that it offers the opportunity to decode according to multiple decoding coefficients $(a,b)$. As only one of the network-coded combinations needs to be successfully decoded, a key advantage is then a reduction in error probability by attempting to decode against all choices of decoding coefficients. In this thesis, we compare different constellation mappers and prove that not all of them have distinct performance in terms of frame error rate. Moreover, we derive a lower bound on the frame error rate performance of decoding the network-coded combinations at the relay. Simulation results show that if we adopt concatenated Reed-Solomon and convolutional coding or low density parity check codes at the two end nodes, our non-binary constellations can outperform the binary case significantly in the sense of minimizing the frame error rate and, in particular, the ternary constellation has the best frame error rate performance among all considered cases.

Most current-generation P2P content distribution protocols use fine-granularity blocks to distribute content in a decentralized fashion. Such systems often suffer from a significant variation in block distributions, such that certain blocks become rare or even unavailable, adversely affecting content availability and download efficiency. This phenomenon is further aggravated by peer dynamics which is inherent in P2P networks. In this thesis, we quantitatively analyze how network coding may improve block availability and introduce resilience to peer dynamics. Since in reality, network coding can only be performed within segments, each containing a subset of blocks, we explore the fundamental tradeoff between the resilience gain of network coding and its inherent coding complexity, as the number of blocks in a segment varies. As another application of the resilience of network coding, we also devise an indirect data collection scheme based on network coding for the purpose of large-scale network measurements.

Recently, erasure networks have received significant attention in the literature as they are used to model both wireless and wireline packet-switched networks. Many packet-switched data networks like wireless mesh networks, the Internet, and Peer-to-peer networks can be modeled as erasure networks. In any erasure network, path diversity works by setting up multiple parallel connections between the end points using the topological path redundancy of the network. Our analysis of diversity over erasure networks studies the problem of rate allocation (RA) across multiple independent paths, coding over erasure channels, and the trade-off between rate and diversity gain in three consecutive chapters. In the chapter 2, Forward Error Correction (FEC) is applied across multiple independent paths to enhance the end-to-end reliability. We prove that the probability of irrecoverable loss (P_E) decays exponentially with the number of paths. Furthermore, the RA problem across independent paths is studied. Our objective is to find the optimal RA, i.e. the allocation which minimizes P_E. Using memoization technique, a heuristic suboptimal algorithm with polynomial runtime is proposed for RA over a finite number of paths. This algorithm converges to the asymptotically optimal RA when the number of paths is large. For practical number of paths, the simulation results demonstrate the close-to-optimal performance of the proposed algorithm. Chapter 3 addresses the problem of lower-bounding the probability of error (PE) for any block code over an input-independent channel. We derive a lower-bound on PE for a general input-independent channel and find the necessary and sufficient condition to meet this bound with equality. The rest of this chapter applies this lower-bound to three special input-independent channels: erasure channel, super-symmetric Discrete Memoryless Channel (DMC), and q-ary symmetric DMC. It is proved that Maximum Distance Separable (MDS) codes achieve the minimum probability of error over any erasure channel (with or without memory). Chapter 4 addresses a fundamental trade-off between rate and diversity gain of an end-to-end connection in erasure networks. We prove that there exist general erasure networks for which any conventional routing strategy fails to achieve the optimum diversity-rate trade-off. However, for any general erasure graph, we show that there exists a linear network coding strategy which achieves the optimum diversity-rate trade-off. Unlike the previous works which suggest the potential benefit of linear network coding in the error-free multicast scenario (in terms of the achievable rate), our result demonstrates the benefit of linear network coding in the erasure single-source single-destination scenario (in terms of the diversity gain).