Search

The fundamental result of linear network coding asserts the existence of an optimal code on an acyclic single-source multicast network when the symbol field is sufficiently large. The restriction to acyclic networks turns out to stem from the customary structure of the symbol alphabet as a field. Adopting data units belonging to a discrete valuation ring (DVR), that is, a PID with a unique maximal ideal, much of the network coding theory extends to cyclic single-source multicast networks. Convolutional network coding is the instance of DVR-based network coding when the DVR consists of rational power series over the symbol field. Meanwhile, a field can be regarded as a degenerate DVR since it is a PID with the maximal ideal 0. Thus the conventional field-based network coding theory becomes a degenerate version of the DVR-based theory. This paper also delves into the issue of constructing optimal network codes on cyclic networks. Inspired by matroid duality theory, a novel method is devised to take advantage of all existing acyclic algorithms for network code construction. It associates every cyclic network with a quadratically large acyclic network so that essentially every optimal code on the acyclic network directly induces one on the cyclic network. [ABSTRACT FROM AUTHOR]

Cross-layer optimization is a key step in wireless network design that coordinates the resources allocated to different layers in order to achieve globally optimal network performance. Existing work on cross-layer optimization for wireless networks often adopts simplistic physical-layer models for wireless channels, such as treating interference as noise or interference avoidance. This crude modeling of physical layer often leads to inefficient utilization of resources. In this paper, we adopt a deterministic channel model proposed in refid="ref1"/, refid="ref2"/, a simple abstraction of the physical layer that effectively captures the effect of channel strength, broadcast and superposition in wireless channels. This model allows us to go beyond “treating interference as noise” and as a consequence are able to achieve higher throughput and utility. Within the network utility maximization (NUM) framework, we study the cross-layer optimization for wireless networks based on this deterministic channel model. First, we extend the well-studied conflict graph model to capture the flow interactions over the deterministic channels and characterize the feasible rate region. Then we study distributed algorithms for general wireless multi-hop networks with both link-centric formulation and node-centric formulation. The convergence of algorithms is proved by applying Lyapunov stability theorem and stochastic approximation method. Further, we show the convergence to the bounded neighborhood of optimal solutions with probability one under constant step sizes and constant update intervals. Our numerical evaluations validate the analytical results and show the advantage of deterministic channel model over simple physical layer models such as treating interference as noise. [ABSTRACT FROM AUTHOR]