Coded packet networks allow for proactive injection of redundant packets to compensate for packet loss. Link metrics are usually based on the estimated transmission counter (ETX). This metric is used to determine the expected number of coded packets needed, but does not make guarantees for a specific decoding probability. In this paper we show that relying on the ETX metric leads to a surprisingly high probability that decoding is not possible. Based on this result, we derive a redundancy scheme to allow for an adjustable decoding probability. In a third step, we extend this scheme to also consider the reliability of link quality estimates themselves. We provide a numerically stable and hardware-accelerated implementation of our redundancy scheme, and compare all approaches in a simulated environment. Finally, we show the effect of the new redundancy scheme on different transport layer protocols in a wireless setup with random linear network coding.

We propose a new model for the wireless broadcast advantage based on a polymatroid structure. This model is a generalization of the predominating hypergraph model. The polymatroid structure yields a general max-flow min-cut characterization of multicast rate regions, which applies to a large variety of channel, physical layer, and medium access models. It includes the state-of-the-art hypergraph flow regions with lossless and lossy hyperarcs, i.e., Shannon rate models and packet erasure networks. Additionally, it generalizes to various other rate regions, e.g., the cut-set outer bounds for networks of a large variety of independent broadcast channels, including networks of independent Gaussian multiple-input multiple-output channels, and the capacity regions for networks of independent deterministic broadcast channels, which can in general not be modeled by the hypergraph flow model. We propose a dual decomposition approach for network utility optimization problems on the polymatroid broadcast flow region, which subsumes existing dual decomposition approaches based on lossless and lossy hypergraph flow regions. Our approach significantly simplifies the decomposition, especially for lossy hypergraph models in packet erasure networks, by fully exploiting the inherent polymatroid structure of the wireless broadcast. Additionally, it can be directly used to fully characterize and evaluate the cut-set bounds for networks of independent broadcast channels with polymatroid structure without previous knowledge about the relevant cuts.

In this paper we propose an end-to-end feedback mechanism for intra-session random linear network coding with opportunistic routing in wireless packet networks with lossy links. We focus on bidirectional network coding, i.e., forward and reverse flows between two nodes are coded together, which is key for efficient utilization of the wireless medium as it allows intermediate nodes to relay traffic in both directions with a single transmission. We analyze the performance in terms of decoding and acknowledgement times in a three-node network when nodes are fully backlogged. The results are compared to the theoretic lower bound obtained by solving the network's flow formulation. In addition, we derive symmetric injection rates from the these results which the network should be able to sustain. The evolution of source backlogs and decoding/acknowledgement over time are simulated, demonstrating that backlogs remain bounded. The insight gained will help in developing a generalized feedback model for coded wireless mesh networks, which is to the best of our knowledge an open problem.

This paper addresses utility maximization problems in the half-duplex two-way multiple-input multiple-output (MIMO) relay channel, where the relay uses the decode-and-forward strategy. Perfect channel information at all nodes and a time division duplex communication protocol with per node peak power constraints for every protocol phase are assumed. For this scenario, we show how solutions to the considered class of problems can efficiently be determined by means of a dual decomposition approach.

We consider uni- and bidirectional communication in the half-duplex multiple-input multiple-output (MIMO) relay channel. Assuming perfect channel state information at all nodes and the use of time division duplex communication protocols with a peak power constraint for every protocol phase, we propose a dual decomposition approach to efficiently determine the cut-set bound and the maximum achievable decode-and-forward rate for the Gaussian MIMO relay channel. A general outer bound on the rate regions that can be achieved in the restricted two-way MIMO relay channel is established, and we present an achievable rate region based on the decode-and-forward scheme which is a superset of several previously derived achievable rate regions. Finally, it is shown how the stated outer bound and achievable rate region can also be evaluated by means of the proposed dual decomposition approach, and we discuss how our work may be used for designing optimal protocols.

We study the throughput region of random access in coded wireless packet networks. We propose a distributed and robust fixed point algorithm that determines whether given coded information flow requirements are feasible with random access and computes the minimal required attempt probabilities supporting these requirements. Combined with linear coding subgraph and flow optimization, this yields a distributed algorithm for joint network coding and random access optimization for multicast networks. Numerical examples show that the proposed method reduces the gap of existing approaches to the optimal solution significantly.

We study wireless multicasting from two sources to two destinations with the assistance of a single half-duplex relay. The objective is to evaluate the throughput and error performance of different analog and digital relay schemes with linear network coding at the relay. The analog relay node forwards either a scaled version of the received signal to the destinations, or alternatively, first filters the received signals to generate a linear Minimum Mean Squared Error (MMSE) estimate, which is subsequently forwarded. The digital relay scheme first detects the source transmissions, combines the packets with a network code, and forwards the resulting symbols to the destinations. For all schemes the destinations recover the source and relay signals by first applying linear MMSE filters, followed by decoding of the source bits. The performance of the schemes are compared in terms of normalized throughput (bits per channel use accounting for the delay due to the relay) and uncoded error probability, given a normalized power constraint. Both narrowband and wideband transmission schemes are considered. Our results show that the analog relay schemes outperform the digital network coding scheme with respect to both throughput and error probability because of error propagation through the relay. Numerical results are presented, which illustrate throughput-reliability trade-offs for all schemes considered.

We consider multicast communications from a single source to multiple destinations through a wireless network with unreliable links. Random linear network coding achieves the min-cut flow capacity; however, additional overhead is needed for end-to-end error protection and to communicate the network coding matrix to each destination. We present a joint coding and training scheme in which training bits are appended to each source packet, and the channel code is applied across both the training and data. This scheme allows each destination to decode jointly the network coding matrix along with the data without knowledge of the network topology. It also balances the reliability of communicating the network coding matrices with the reliability of data detection. The throughput for this scheme, accounting for overhead, is characterized as a function of the packet size, channel properties (error and erasure statistics), number of independent messages, and field size. We also compare the performance with that obtained by individual channel coding of training and data. Numerical results are presented for a grid network that illustrate the reduction in throughput due to overhead.