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).

Les réseaux mobiles Ad hoc (MANETs) visent à permettent à des noeuds mobiles de communiquer sans aucun support d'infrastructure. Les MANETs dispersés entrent dans la catégorie des réseaux tolérants aux délais (DTN), qui sont des réseaux connectés par intermittence et où il n'y a aucun chemin de bout-en-bout persistant à n'importe quel temps donné. Nous proposons, d'abord, un nouveau protocole de transport fiable pour les DTNs basé sur l'utilisation d'accusés de réception ainsi que le codage linéaire aléatoire. Nous modélisons l'évolution du réseau conformément à notre plan en utilisant l'approche fluide. Nous obtenons le temps de transfert d'un fichier en fonction de certains paramètres optimaux obtenus par l'approche d'évolution différentielle. Deuxièmement, Nous proposons ainsi et étudions un nouveau mécanisme d'ACK augmenté, pour améliorer le transport fiable pour les DTNs, pour les cas unicast et multicast. Nous nous servons du codage linéaire aléatoire aux relais pour que les paquets puissent atteindre la destination plus rapidement. Nous obtenons la fiabilité basée sur l'utilisation Global Sélective ACKnowledgement. Enfin, nous abordons le problème de l'estimation de propagation des fichiers dans les DTNs avec livraison directe et le routage épidémique. Nous estimons et suivons le degré de propagation d'un message dans le réseau. Nous fournissons la base analytique à notre cadre d'évaluation avec des aperçus validés en se basant sur des simulations. En plus, nous utilisons le filtre de Kalman et Minimum- Mean-Squared Error (MMSE) pour suivre le processus de propagation et trouvons que le filtre de Kalman fournit des résultats plus précis par rapport à MMSE / Mobile Ad hoc NETworks (MANETs) aim at making communication between mobile nodes feasible without any infrastructure support. Sparse MANETs fall into the class of Delay Tolerant Networks which are intermittently connected networks and where there is no contemporaneous end-to-end path at any given time. We first, propose a new reliable transport scheme for DTNs based on the use of ACKnowledgments and random linear coding. We model the evolution of the network under our scheme using a fluid-limit approach. We optimize our scheme to obtain mean file transfer times on certain optimal parameters obtained through differential evolution approach. Secondly, we propose and study a novel and enhanced ACK to improve reliable transport for DTNs covering both unicast and multicast flows. We make use of random linear coding at relays so that packets can reach the destination faster. We obtain reliability based on the use of so-called Global Selective ACKnowledgment. We obtain significant improvement through G-SACKs and coding at relays. Finally, we tackle the problem of estimating file-spread in DTNs with direct delivery and epidemic routing. We estimate and track the degree of spread of a message in the network. We provide analytical basis to our estimation framework alongwith insights validated with simulations. We observe that the deterministic fluid model can indeed be a good predictor with a large of nodes. Moreover, we use Kalman filter and Minimum- Mean-Squared-Error (MMSE) to track the spreading process and find that Kalman filter provides more accurate results as compared to MMSE

Optimising the throughput performance for wireless networks is one of the challenging tasks in the objectives of communication engineering, since wireless channels are prone to errors due to path losses, random noise, and fading phenomena. The transmission errors will be worse in a multihop scenario due to its accumulative effects. Network Coding (NC) is an elegant technique to improve the throughput performance of a communication network. There is the fact that the bit error rates over one modulation symbol of 16- and higher order- Quadrature Amplitude Modulation (QAM) scheme follow a certain pattern. The Scattered Random Network Coding (SRNC) system was proposed in the literature to exploit the error pattern of 16-QAM by using bit-scattering to improve the throughput of multihop network to which is being applied the Random Linear Network Coding (RLNC). This thesis aims to improve further the SRNC system by using Forward Error Correction (FEC) code; the proposed system is called Joint RLNC and FEC with interleaving. The first proposed system (System-I) uses Convolutional Code (CC) FEC. The performances analysis of System-I with various CC rates of 1/2, 1/3, 1/4, 1/6, and 1/8 was carried out using the developed simulation tools in MATLAB and compared to two benchmark systems: SRNC system (System-II) and RLNC system (System- III). The second proposed system (System-IV) uses Reed-Solomon (RS) FEC code. Performance evaluation of System IV was carried out and compared to three systems; System-I with 1/2 CC rate, System-II, and System-III. All simulations were carried out over three possible channel environments: 1) AWGN channel, 2) a Rayleigh fading channel, and 3) a Rician fading channel, where both fading channels are in series with the AWGN channel. The simulation results show that the proposed system improves the SRNC system. How much improvement gain can be achieved depends on the FEC type used and the channel environment.

The paradigm of network coding was introduced as a means to conserve bandwidth (or equivalently increase throughput) in information flow networks. Network coding makes use of the fact that unlike physical commodities, information can be replicated and coded together at the nodes of the network. As a result, routing can be strictly suboptimal in many classes of information flow networks compared to network coding. Network-error correction is the art of designing network codes such that the sinks of the network will be able to decode the required information in the presence of errors in the edges of the network, known as network-errors. The network coding problem on a network with given sink demands can be considered to have the following three major subproblems, which naturally also extend to the study of network-error correcting codes, as they can be viewed as a special class of network codes (a) Existence of a network code that satisfies the demands (b) Efficient construction of such a network code (c) Minimum alphabet size for the existence of such a network code. This thesis primarily considers linear network coding and error correction and in- vestigates solutions to these issues for certain classes of network coding and error correction problems in acyclic networks. Our contributions are broadly summarised as follows. (1) We propose the use of convolutional codes for multicast network-error correc- tion. Depending upon the number of network-errors required to be corrected in the network, convolutional codes are designed at the source of the multicast network so that these errors can be corrected at the sinks of the networks as long as they are separated by certain number of time instants (for which we give a bound). In con- trast to block codes for network-error correction which require large field sizes, using convolutional codes enables the field size of the network code to be small. We discuss the performance of such networks under the BSC edge error model. (2)Existing construction algorithms of block network-error correcting codes require a rather large field size, which grows with the size of the network and the number of sinks, and thereby can be prohibitive in large networks. In our work, we give an algorithm which, starting from a given network-error correcting code, can obtain an- other network code using a small field, with the same error correcting capability as the original code. The major step in our algorithm is to find a least degree irreducible poly- nomial which is coprime to another large degree polynomial. We utilize the algebraic properties of finite fields to implement this step so that it becomes much faster than the brute-force method. A recently proposed algorithm for network coding using small fields can be seen as a special case of our algorithm for the case of no network-errors. (3)Matroids are discrete mathematical objects which generalize the notion of linear independence of sets of vectors. It has been observed recently that matroids and network coding share a deep connection, and several important results of network coding has been obtained using these connections from matroid theory. In our work, we establish that matroids with certain special properties correspond to networks with error detecting and correcting properties. We call such networks as matroidal error detecting (or equivalently, correcting) networks. We show that networks have scalar linear network-error detecting (or correcting) codes if and only if there are associated with representable matroids with some special properties. We also use these ideas to construct matroidal error correcting networks along with their associated matroids. In the case of representable matroids, these algorithms give rise to scalar linear network- error correcting codes on such networks. Finally we also show that linear network coding is not sufficient for the general network-error detection (correction) problem with arbitrary demands. (4)Problems related to network coding for acyclic, instantaneous networks have been extensively dealt with in the past. In contrast, not much attention has been paid to networks with delays. In our work, we elaborate on the existence, construction and minimum field size issues of network codes for networks with integer delays. We show that the delays associated with the edges of the network cannot be ignored, and in fact turn out to be advantageous, disadvantageous or immaterial, depending on the topology of the network and the network coding problem considered. In the process, we also show multicast network codes which involve only delaying the symbols arriving at the nodes of the networks and coding the delayed symbols over a binary field, thereby making coding operations at the nodes less complex. (5) In the usual network coding framework, for a given set of network demands over an arbitrary acyclic network with integer delays assumed for the links, the out- put symbols at the sink nodes, at any given time instant, is a Fq-linear combination of the input symbols generated at different time instants where Fq denotes the field over which the network operates. Therefore the sinks have to use sufficient memory elements in order to decode simultaneously for the entire stream of demanded infor- mation symbols. We propose a scheme using an ν-point finite-field discrete fourier transform (DFT) which converts the output symbols at the sink nodes at any given time instant, into a Fq-linear combination of the input symbols generated during the same time instant without making use of memory at the intermediate nodes. We call this as transforming the acyclic network with delay into ν-instantaneous networks (ν is sufficiently large). We show that under certain conditions, there exists a network code satisfying sink demands in the usual (non-transform) approach if and only if there exists a network code satisfying sink demands in the transform approach.

Multiple users compete for a common resource like bandwidth to communicate data in interference networks. Existing approaches in dealing with interference limit the rate of communication due to paucity of shared resources. This limitation in the rate gets more glaring as the number of users in the network increases. For example, existing wireless systems either choose to orthogonalize the users (for example, Frequency Division Multiple Access (FDMA) systems or Code Division Multiple Access (CDMA) systems) or treat interference as Gaussian noise at the receivers. It is well known that these approaches are sub-optimal in general. Orthogonalization of users limit the number of available interference-free channels (known as degrees of freedom, abbreviated as DoF) and treating interference as noise means that the receiver cannot make use of the structure in the interfering signals. This motivates the need to analyze alternate transmit and decoding schemes in interference networks. This thesis mainly analyzes transmit schemes that use linear precoding for various configurations of interference networks with some practical constraints imposed by the use of finite input constellations, propagation delays, and channel state availability at the transmitters. The main contributions of this thesis are listed below. Achievable rates using precoding with finite constellation inputs in Gaussian Interference Channels (GIC) is analyzed. A metric for finding the approximate angle of rotation to maximally enlarge the Constellation Constrained (CC) capacity of two-user Gaussian Strong Interference Channel (GSIC) is proposed. Even as the Gaussian alphabet FDMA rate curve touches the capacity curve of the GSIC, with both the users using the same finite constellation, we show that the CC FDMA rate curve lies strictly inside the CC capacity curve at high powers. For a K-user MIMO GIC, a set of necessary and sufficient conditions on the precoders under which the mutual information between between relevant transmit-receive pairs saturate like in the single user case is derived. Gradient-ascent based algorithms to optimize the sum-rate achieved by precoding with finite constellation inputs and treating interference as noise are proposed. For a class of Gaussian interference networks with general message demands, identified as symmetrically connected interference networks, the expected sumspectral efficiency (in bits/sec/Hz) is shown to grow linearly with the number of transmitters at finite SNR, using a time-domain Interference Alignment (IA) scheme in the presence of line of sight (LOS) channels. For a 2×2 MIMO X-Network with M antennas at each node, we identify spacetime block codes that could be coupled with an appropriate precoding scheme to achieve the maximum possible sum-DoF of 4M 3 , for M = 3, 4. The proposed schemes are shown to achieve a diversity gain of M with SNR-independent finite constellation inputs. The proposed schemes have lower CSIT requirements compared to existing schemes. This thesis also makes an attempt to guarantee a minimum throughput when the zero-interference conditions cannot be satisfied in a wireline network with three unicast sessions with delays, using Precoding Based Network Alignment (PBNA). Three different PBNA schemes namely PBNA with time-varying local encoding coefficients (LECs), PBNA using transform approach and time-invariant LECs, and PBNA using transform approach and block time-varying LECs are proposed and their feasibility conditions analyzed.

Optimising the throughput performance for wireless networks is one of the challenging tasks in the objectives of communication engineering, since wireless channels are prone to errors due to path losses, random noise, and fading phenomena. The transmission errors will be worse in a multihop scenario due to its accumulative effects. Network Coding (NC) is an elegant technique to improve the throughput performance of a communication network. There is the fact that the bit error rates over one modulation symbol of 16- and higher order- Quadrature Amplitude Modulation (QAM) scheme follow a certain pattern. The Scattered Random Network Coding (SRNC) system was proposed in the literature to exploit the error pattern of 16-QAM by using bit-scattering to improve the throughput of multihop network to which is being applied the Random Linear Network Coding (RLNC). This thesis aims to improve further the SRNC system by using Forward Error Correction (FEC) code; the proposed system is called Joint RLNC and FEC with interleaving. The first proposed system (System-I) uses Convolutional Code (CC) FEC. The performances analysis of System-I with various CC rates of 1/2, 1/3, 1/4, 1/6, and 1/8 was carried out using the developed simulation tools in MATLAB and compared to two benchmark systems: SRNC system (System-II) and RLNC system (System- III). The second proposed system (System-IV) uses Reed-Solomon (RS) FEC code. Performance evaluation of System IV was carried out and compared to three systems; System-I with 1/2 CC rate, System-II, and System-III. All simulations were carried out over three possible channel environments: 1) AWGN channel, 2) a Rayleigh fading channel, and 3) a Rician fading channel, where both fading channels are in series with the AWGN channel. The simulation results show that the proposed system improves the SRNC system. How much improvement gain can be achieved depends on the FEC type used and the channel environment. / Indonesian Government and the University of Bradford

Network coding has emerged as an attractive alternative to routing because of the through put improvement it provides by reducing the number of channel uses. In a wireless scenario, in addition, further improvement can be obtained through Physical layer Network Coding (PNC), a technique in which nodes are allowed to transmit simultaneously, instead of transmitting in orthogonal slots. In this thesis, the design and analysis of network coding schemes are considered, for wireless two-way relaying, multi-user Multiple Access Relay Channel (MARC) and wireline networks. In a wireless two-way relay channel with PNC, the simultaneous transmissions of user nodes result in Multiple Access Interference (MAI) at there lay node. The harmful effect of MAI is the presence of signal set dependent deep channel fade conditions, called singular fade states, under which the minimum distance of the effective constellation at the relay become zero. Adaptively changing the network coding map used at the relay according to channel conditions greatly reduces the impact of this MAI. In this work, we obtain these adaptive PNC maps, which are finite in number ,by completing partially filled Latin Squares and using graph vertex coloring. Having obtained the network coding maps, the set of all possible channel realizations is quantized into a finite number of regions, with a specific network coding map chosen in a particular region and such a quantization is obtained analytically for 2λ-PSK signal set. The performance of the adaptive PNC scheme for two-way relaying is analyzed and tight high SNR upper bounds are obtained for the average end-to-end symbol error probability, in terms of the average error probability of a point-to-point fading channel. The adaptive PNC scheme is generalized for two-way relaying with multiple antennas at the nodes. As an alternative to the adaptive PNC scheme for two-way relaying, a Distributed Space Time Coding (DSTC) scheme is proposed, which effectively re-moves the effect of singular fade states at the transmitting nodes itself without any Channel State Information at the Transmitter (CSIT), and without any need to change the PNC map as a function of channel fade conditions. It is shown that the singular fade states can be viewed equivalently as vector subspaces of C2, which are referred to as the singular fade subspaces. DSTC design criterion to minimize the number of singular fade subspaces and maximize the coding gain is formulated and explicit low decoding complexity DSTC designs are provided. For the K-user MARC, in which K source nodes want to transmit messages to a destination node D with the help of are lay node R, a new PNC scheme is proposed. Use of a many-to-one PNC map with conventional minimum squared Euclidean distance decoding at D, results in a loss of diversity order due to error propagation from the relay node. To counter this, we propose a novel low complexity decoder which offers the maximum diversity order of two. Next, we consider wire line networks and explore the connections between linear network coding, linear index coding and discrete polymatroids, which are the multi-set analogue of matroids. We define a discrete polymatroidal network and show that a fractional vector linear solution over a field Fq exists for a network if and only if the network is discrete polymatroidal with respect to a discrete polymatroid representable over Fq.An algorithm to construct networks starting from certain class of discrete polymatroids is provided. Every representation over Fq for the discrete polymatroid, results in a fractional vector linear solution over Fq for the constructed network. It is shown that a linear solution to an index coding problem exists if and only if there exists a representable discrete polymatroid satisfying certain conditions which are determined by the index coding problem considered. El Rouayheb et. al. showed that the problem of finding a multi-linear representation for a matroid can be reduced to finding a perfect linear index coding solution for an index coding problem obtained from that matroid. Multi-linear representation of a matroid can be viewed as a special case of representation of an appropriate discrete polymatroid. We generalize the result of El Rouayheb et. al. by showing that the problem of finding a representation for a discrete polymatroid can be reduced to finding a perfect linear index coding solution for an index coding problem obtained from that discrete polymatroid.