The throughput order of multicast traffics with physical-layer network coding in random wireless ad hoc networks

This paper attempts to address the effectiveness of physical-layer network coding (PNC) on the throughput improvement for multi-hop multicast in random wireless ad hoc networks (WAHNs). We prove that the per session throughput order with PNC is tightly bounded as T((nvmR (n))-1) if m = O(R-2 (n)), where n is the total number of nodes, R(n) is the communication range, and m is the number of destinations for each multicast session. We also show that per-session throughput order with PNC is tight bounded as T(n-1), when m = O(R-2(n)). The results of this paper imply that PNC cannot improve the throughput order of multicast in random WAHNs, which is different from the intuition that PNC may improve the throughput order as it allows simultaneous signal access and combination.

Network Coding for TCP Throughput Enhancement over a Multi-Hop wireless Network

The poor performance of TCP over multi-hop wireless networks is well known. In this paper we explore to what extent network coding can help to improve the throughput performance of TCP controlled bulk transfers over a chain topology multi-hop wireless network. The nodes use a CSMA/ CA mechanism, such as IEEE 802.11’s DCF, to perform distributed packet scheduling. The reverse flowing TCP ACKs are sought to be X-ORed with forward flowing TCP data packets. We find that, without any modification to theMAC protocol, the gain from network coding is negligible. The inherent coordination problem of carrier sensing based random access in multi-hop wireless networks dominates the performance. We provide a theoretical analysis that yields a throughput bound with network coding. We then propose a distributed modification of the IEEE 802.11 DCF, based on tuning the back-off mechanism using a feedback approach. Simulation studies show that the proposed mechanism when combined with network coding, improves the performance of a TCP session by more than 100%.

An asymptotically optimal push-pull method for multicasting over a random network

We consider multicast flow problems where either all of the nodes or only a subset of the nodes may be in session. Traffic from each node in the session has to be sent to every other node in the session. If the session does not consist of all the nodes, the remaining nodes act as relays. The nodes are connected by undirected edges whose capacities are independent and identically distributed random variables. We study the asymptotics of the capacity region (with network coding) in the limit of a large number of nodes, and show that the normalized sum rate converges to a constant almost surely. We then provide a decentralized push-pull algorithm that asymptotically achieves this normalized sum rate.

On the capacity improvement of multicast throughput in wireless ad hoc networks with physical-layer network coding

This paper attempts to address the effectiveness of physical-layer network coding (PNC) on the capacity improvement for multi-hop multicast in random wireless ad hoc networks (WAHNs). While it can be shown that there is a capacity gain by PNC, we can prove that the per session throughput capacity with PNC is ? (nR(n))), where n is the total number of nodes, R(n) is the communication range, and each multicast session consists of a constant number of sinks. The result implies that PNC cannot improve the capacity order of multicast in random WAHNs, which is different from the intuition that PNC may improve the capacity order as it allows simultaneous signal reception and combination. Copyright © 2010 ACM.

Preventing pollution attacks in multi-source network coding

Network coding is a method for achieving channel capacity in networks. The key idea is to allow network routers to linearly mix packets as they traverse the network so that recipients receive linear combinations of packets. Network coded systems are vulnerable to pollution attacks where a single malicious node floods the network with bad packets and prevents the receiver from decoding correctly. Cryptographic defenses to these problems are based on homomorphic signatures and MACs. These proposals, however, cannot handle mixing of packets from multiple sources, which is needed to achieve the full benefits of network coding. In this paper we address integrity of multi-source mixing. We propose a security model for this setting and provide a generic construction.

Random network behaviour of protein structures

Geometric and structural constraints greatly restrict the selection of folds adapted by protein backbones, and yet, folded proteins show an astounding diversity in functionality. For structure to have any bearing on function, it is thus imperative that, apart from the protein backbone, other tunable degrees of freedom be accountable. Here, we focus on side-chain interactions, which non-covalently link amino acids in folded proteins to form a network structure. At a coarse-grained level, we show that the network conforms remarkably well to realizations of random graphs and displays associated percolation behavior. Thus, within the rigid framework of the protein backbone that restricts the structure space, the side-chain interactions exhibit an element of randomness, which account for the functional flexibility and diversity shown by proteins. However, at a finer level, the network exhibits deviations from these random graphs which, as we demonstrate for a few specific examples, reflect the intrinsic uniqueness in the structure and stability, and perhaps specificity in the functioning of biological proteins.

Single-Generation Network Coding for Networks with Delay

A single-source network is said to be memory-free if all of the internal nodes (those except the source and the sinks) do not employ memory but merely send linear combinations of the incoming symbols (received at their incoming edges) on their outgoing edges. Memory-free networks with delay using network coding are forced to do inter-generation network coding, as a result of which the problem of some or all sinks requiring a large amount of memory for decoding is faced. In this work, we address this problem by utilizing memory elements at the internal nodes of the network also, which results in the reduction of the number of memory elements used at the sinks. We give an algorithm which employs memory at all the nodes of the network to achieve single- generation network coding. For fixed latency, our algorithm reduces the total number of memory elements used in the network to achieve single- generation network coding. We also discuss the advantages of employing single-generation network coding together with convolutional network-error correction codes (CNECCs) for networks with unit- delay and illustrate the performance gain of CNECCs by using memory at the intermediate nodes using simulations on an example network under a probabilistic network error model.

Interference Alignment as a Tool in Network Coding as Applied to Distributed Storage

In this paper, we outline an approach to the task of designing network codes in a non-multicast setting. Our approach makes use of the concept of interference alignment. As an example, we consider the distributed storage problem where the data is stored across the network in n nodes and where a data collector can recover the data by connecting to any k of the n nodes and where furthermore, upon failure of a node, a new node can replicate the data stored in the failed node while minimizing the repair bandwidth.

On network coding for acyclic networks with delays

Problems related to network coding for acyclic, instantaneous networks (where the edges of the acyclic graph representing the network are assumed to have zero-delay) have been extensively dealt with in the recent past. The most prominent of these problems include (a) the existence of network codes that achieve maximum rate of transmission, (b) efficient network code constructions, and (c) field size issues. In practice, however, networks have transmission delays. In network coding theory, such networks with transmission delays are generally abstracted by assuming that their edges have integer delays. Using enough memory at the nodes of an acyclic network with integer delays can effectively simulate instantaneous behavior, which is probably why only acyclic instantaneous networks have been primarily focused on thus far. However, nulling the effect of the network delays are not always uniformly advantageous, as we will show in this work. Essentially, we elaborate on issues ((a), (b) and (c) above) related to network coding for acyclic networks with integer delays, and show that using the delay network as is (without adding memory) turns out to be advantageous, disadvantageous or immaterial, depending on the topology of the network and the problem considered i.e., (a), (b) or (c).

Generalized bidirectional multi-pair multi-antennawireless network coding

In this paper, we focus on increasing the throughput and diversity of network coded MIMO transmissions in bidirectional multi-pair wireless relay networks. All nodes have multi-antenna capability. Pairs of nodes want to exchange messages via a relay having multi-antenna and encoding/decoding capability. Nodes transmit their messages to the relay in the first (MAC) phase. The relay decodes all the messages and XORs them and broadcasts the XORed message in the second (BC) phase. We develop a generalized framework for bidirectional multi-pair multi-antenna wireless network coding, which models different MIMO transmission schemes including spatial multiplexing (V-BLAST), orthogonal STBC (OSTBC), and non-orthogonal STBC (NO-STBC) in a unified way. Enhanced throughputs are achieved by allowing all nodes to simultaneously transmit at their full rate. High diversity orders are achieved through the use of NO-STBCs, characterized by full rate and full transmit diversity. We evaluate and compare the performance of VBLAST, OSTBC, and NO-STBC schemes in one-dimensional 1-pair linear network (one pair of nodes and a relay) and two-dimensional 2-pair `cross' network (two pairs of nodes and a relay).

Performance analysis of adaptive physical layer network coding for wireless two-way relaying

The performance analysis of adaptive physical layer network-coded two-way relaying scenario is presented which employs two phases: Multiple access (MA) phase and Broadcast (BC) phase. The deep channel fade conditions which occur at the relay referred as the singular fade states fall in the following two classes: (i) removable and (ii) non-removable singular fade states. With every singular fade state, we associate an error probability that the relay transmits a wrong network-coded symbol during the BC phase. It is shown that adaptive network coding provides a coding gain over fixed network coding, by making the error probabilities associated with the removable singular fade states contributing to the average Symbol Error Rate (SER) fall as SNR-2 instead of SNR-1. A high SNR upper-bound on the average end-to-end SER for the adaptive network coding scheme is derived, for a Rician fading scenario, which is found to be tight through simulations. Specifically, it is shown that for the adaptive network coding scheme, the probability that the relay node transmits a wrong network-coded symbol is upper-bounded by twice the average SER of a point-to-point fading channel, at high SNR. Also, it is shown that in a Rician fading scenario, it suffices to remove the effect of only those singular fade states which contribute dominantly to the average SER.

Physical Layer Network Coding for the K-User Multiple Access Relay Channel

We propose a Physical layer Network Coding (PNC) scheme for the K-user wireless Multiple Access Relay Channel, in which K source nodes want to transmit messages to a destination node D with the help of a relay node R. The proposed scheme involves (i) Phase 1 during which the source nodes alone transmit and (ii) Phase 2 during which the source nodes and the relay node transmit. At the end of Phase 1, the relay node decodes the messages of the source nodes and during Phase 2 transmits a many-to-one function of the decoded messages. To counter the error propagation from the relay node, we propose a novel decoder which takes into account the possibility of error events at R. It is shown that if certain parameters are chosen properly and if the network coding map used at R forms a Latin Hypercube, the proposed decoder offers the maximum diversity order of two. Also, it is shown that for a proper choice of the parameters, the proposed decoder admits fast decoding, with the same decoding complexity order as that of the reference scheme based on Complex Field Network Coding (CFNC). Simulation results indicate that the proposed PNC scheme offers a large gain over the CFNC scheme.

Wireless Network Coding for MIMO Two-Way Relaying

The design of modulation schemes for the physical layer network-coded two-way MIMO relaying scenario is considered, with the denoise-and-forward protocol which employs two phases: Multiple Access phase and Broadcast phase. It is shown that for MIMO two-way relaying, the minimum distance of the effective constellation at the relay becomes zero when all the rows of the channel fade coefficient matrix belong to a finite number of vector subspaces referred to as the singular fade subspaces. The singular fade subspaces can be classified into two kinds based on whether their harmful effects can be removed or not: (i) the removable and (ii) the non-removable singular fade subspaces. It is shown that network coding maps obtained by the completion of appropriate partially filled Latin Rectangles can remove the harmful effects of all the removable singular fade subspaces. For 2(lambda)-PSK signal set, the removable and non-removable singular fade subspaces are characterized and, it is shown that the number of non-removable singular fade subspaces is a small fraction of the total number of singular fade subspaces and this fraction tends to zero as the constellation size tends to infinity. The Latin Rectangles for the case when the end nodes use different number of antennas are shown to be obtainable from the Latin Squares for the case when they use the same number of antennas. Also, the network coding maps which remove all the removable singular singular fade subspaces are shown to be obtainable from a small set of Latin Squares. The removal of all the singular fade subspaces by properly choosing the network coding map, provides a gain of 5.5 dB over the conventional Exclusive-OR network coding, in a Rayleigh fading scenario with 2 antennas at the end nodes and one antenna at the relay node, for 4-PSK signal set.

Physical layer network coding for two-way relaying with QAM and latin squares

In the design of modulation schemes for the physical layer network-coded two way relaying scenario with two phases (Multiple access (MA) Phase and Broadcast (BC) Phase), it was observed by Koike-Akino et al. that adaptively changing the network coding map used at the relay according to the channel conditions greatly reduces the impact of multiple access interference and all these network coding maps should satisfy a requirement called the exclusive law. In [11] the case in which the end nodes use M-PSK signal sets is extensively studied using Latin Squares. This paper deals with the case in which the end nodes use square M-QAM signal sets. In a fading scenario, for certain channel conditions, termed singular fade states, the MA phase performance is greatly reduced. We show that the square QAM signal sets lead to lesser number of singular fade states compared to PSK signal sets. Because of this, the complexity at the relay is enormously reduced. Moreover lesser number of overhead bits are required in the BC phase. We find the number of singular fade states for PAM and QAM signal sets used at the end nodes. The fade state γejθ = 1 is a singular fade state for M-QAM for all values of M and it is shown that certain block circulant Latin Squares remove this singular fade state. Simulation results are presented to show that QAM signal set perform better than PSK.

Performance analysis of adaptive physical layer network coding for wireless two-way Relaying

The analysis of modulation schemes for the physical layer network-coded two way relaying scenario is presented which employs two phases: Multiple access (MA) phase and Broadcast (BC) phase. Depending on the signal set used at the end nodes, the minimum distance of the effective constellation seen at the relay becomes zero for a finite number of channel fade states referred as the singular fade states. The singular fade states fall into the following two classes: (i) the ones which are caused due to channel outage and whose harmful effect cannot be mitigated by adaptive network coding called the non-removable singular fade states and (ii) the ones which occur due to the choice of the signal set and whose harmful effects can be removed called the removable singular fade states. In this paper, we derive an upper bound on the average end-to-end Symbol Error Rate (SER), with and without adaptive network coding at the relay, for a Rician fading scenario. It is shown that without adaptive network coding, at high Signal to Noise Ratio (SNR), the contribution to the end-to-end SER comes from the following error events which fall as SNR-1: the error events associated with the removable and nonremovable singular fade states and the error event during the BC phase. In contrast, for the adaptive network coding scheme, the error events associated with the removable singular fade states fall as SNR-2, thereby providing a coding gain over the case when adaptive network coding is not used. Also, it is shown that for a Rician fading channel, the error during the MA phase dominates over the error during the BC phase. Hence, adaptive network coding, which improves the performance during the MA phase provides more gain in a Rician fading scenario than in a Rayleigh fading scenario. Furthermore, it is shown that for large Rician factors, among those removable singular fade states which have the same magnitude, those which have the least absolute value of the phase - ngle alone contribute dominantly to the end-to-end SER and it is sufficient to remove the effect of only such singular fade states.