Network Coding for Efficient Multicast Routing in Wireless Ad-hoc Networks

Network coding is a powerful coding technique that has been proved to be very effective in achieving the maximum multicast capacity. It is especially suited for new emerging networks such as ad-hoc and sensor networks. In this work, we investigate the multicast routing problem based on network coding and put forward a practical algorithm to obtain the maximum flow multicast routes in ad-hoc networks. The "conflict phenomenon" that occurs in undirected graphs will also be discussed. Given the developed routing algorithm, we will present the condition for a node to be an encoding node along with a corresponding capacity allocation scheme. We will also analyze the statistical characteristics of encoding nodes and maximum flow in ad-hoc networks based on random graph theory.     

On the capacity of network coding for random networks

We study the maximum flow possible between a single-source and multiple terminals in a weighted random graph (modeling a wired network) and a weighted random geometric graph (modeling an ad-hoc wireless network) using network coding. For the weighted random graph model, we show that the network coding capacity concentrates around the expected number of nearest neighbors of the source and the terminals. Specifically, for a network with a single source, l terminals, and n relay nodes such that the link capacities between any two nodes is independent and identically distributed (i.i.d.) /spl sim/X, the maximum flow between the source and the terminals is approximately nE[X] with high probability. For the weighted random geometric graph model where two nodes are connected if they are within a certain distance of each other we show that with high probability the network coding capacity is greater than or equal to the expected number of nearest neighbors of the node with the least coverage area.     

Cross-Layer Rate Control, Routing and Scheduling Design for Multicast with Network Coding in Ad Hoc Networks

Network coding is a powerful coding technique that has been proved to be very effective in achieving the maximum multicast capacity. It is especially suited for new emerging networks such as ad-hoc and sensor networks. In this paper, we develop a distributed rate control algorithm for multicast session in ad hoc networks. With random network coding, the algorithm can be implemented in a distributed manner, and work at transport layer to adjust source rates and at network layer to carry out network coding. The scheduling element of our algorithm is a dynamic scheduling policy. The stability of the resulted system is established, and simulation results are provided to support our conclusions.     

Improving the multicommodity flow rates with network codes for two sources

In this work we introduce a construction and analysis of network codes for two sources. The region of achievable rates for this problem is still unknown. The scheme we suggest is based on modifying the multicommodity flow solution and thus improving the achievable rate region, w.r.t the uncoded case. The similarity to the flow problem allows our method to be implemented distributively. We show how the construction algorithm can be combined with distributed backpressure routing algorithms for wireless ad-hoc networks. For both the nondistributed case and the distributed case, the computational complexity of our algorithm for network coding is comparable to that of the parallel multicommodity flow problem. We provide non trivial upper and lower bounds on the performance of our scheme, using random coding techniques.     

Unachievability of network coding capacity

The coding capacity of a network is the supremum of ratios k/n, for which there exists a fractional (k,n) coding solution, where k is the source message dimension and n is the maximum edge dimension. The coding capacity is referred to as routing capacity in the case when only routing is allowed. A network is said to achieve its capacity if there is some fractional (k,n) solution for which k/n equals the capacity. The routing capacity is known to be achievable for arbitrary networks. We give an example of a network whose coding capacity (which is 1) cannot be achieved by a network code. We do this by constructing two networks, one of which is solvable if and only if the alphabet size is odd, and the other of which is solvable if and only if the alphabet size is a power of 2. No linearity assumptions are made.     

A comprehensive survey of network coding in vehicular ad-hoc networks

Network coding is a data processing technique in which the flow of digital data is optimized in a network by transmitting a composite of two or more messages to make the network more robust. Network coding has been used in traditional and emerging wireless networks to overcome the communications issues of these networks. It also plays an important role in the area of vehicular ad-hoc networks (VANETs) to meet the challenges like high mobility, rapidly changing topology, and intermittent connectivity. VANETs consist of network of vehicles in which they communicate with each other to ensure road safety, free flow of traffic, and ease of journey for the passengers. It is now considered to be the most valuable concept for improving efficiency and safety of future transportation. However, this field has a lot of challenges to deal with. This paper presents a comprehensive survey of network coding schemes in VANETs. We have classified different applications like content distribution, multimedia streaming, cooperative downloading, data dissemination, and summarized other key areas of VANETs in which network coding schemes are implemented. This research work will provide a clear understanding to the readers about how network coding is implemented in these schemes in VANETs to improve performance, reduce delay, and make the network more efficient.     

Network coding-aware flow control in wireless ad-hoc networks with multi-path routing

In this paper, we study a flow control problem considering network coding in wireless ad-hoc networks with multi-path routing. As a network coding scheme, we use XOR network coding, in which each node bitwise-XORs some packets received from different sessions, and then broadcasts this coded packet to multiple nodes in a single transmission. This process can reduce the number of required transmissions, and thus can improve network utilization, especially if it is used with appropriate network coding-aware protocols. Considering this XOR network coding, we formulate an optimization problem for flow control that aims at maximizing network utility. By solving the optimization problem in a distributed manner, we implement a distributed flow control algorithm that provides the optimal transmitting rate on each of multiple paths of each session. The simulation results show that our flow control algorithm performs well exploiting the advantages of network coding and provides significant performance improvement.     

An algebraic approach to network coding

We take a new look at the issue of network capacity. It is shown that network coding is an essential ingredient in achieving the capacity of a network. Building on recent work by Li et al.(see Proc. 2001 IEEE Int. Symp. Information Theory, p.102), who examined the network capacity of multicast networks, we extend the network coding framework to arbitrary networks and robust networking. For networks which are restricted to using linear network codes, we find necessary and sufficient conditions for the feasibility of any given set of connections over a given network. We also consider the problem of network recovery for nonergodic link failures. For the multicast setup we prove that there exist coding strategies that provide maximally robust networks and that do not require adaptation of the network interior to the failure pattern in question. The results are derived for both delay-free networks and networks with delays.     

Optimal Unicast Capacity of Random Geometric Graphs: Impact of Multipacket Transmission and Reception

We establish a tight max-flow min-cut theorem for multi-commodity routing in random geometric graphs. We show that, as the number of nodes in the network n tends to infinity, the maximum concurrent flow (MCF) and the minimum cut-sparsity scale as θ(n²r³(n)/k), for a random choice of k = ω(n) source-destination pairs, where n and r(n) are the number of nodes and the communication range in the network respectively. The MCF equals the interference-free capacity of an ad-hoc network. We exploit this fact to develop novel graph theoretic techniques that can be used to deduce tight order bounds on the capacity of ad-hoc networks. We generalize all existing capacity results reported to date by showing that the per-commodity capacity of the network scales as θ(1/r(n)k) for the single-packet reception model suggested by Gupta and Kumar, and as θ(nr(n)/k) for the multiple-packet reception model suggested by others. More importantly, we show that, if the nodes in the network are capable of (perfect) multiple-packet transmission (MPT) and reception (MPR), then it is feasible to achieve the optimal scaling of θ(n²r³(n)/k), despite the presence of interference. In comparison to the Gupta-Kumar model, the realization of MPT and MPR may require the deployment of a large number of antennas at each node or bandwidth expansion. Nevertheless, in stark contrast to the existing literature, our analysis presents the possibility of actually increasing the capacity of ad-hoc networks with n even while the communication range tends to zero!     

A Cross-Layer Admission Control Framework for Wireless Ad-Hoc Networks using Multiple Antennas

Unlike single omnidirectional antennas, multiple antennas offer wireless ad-hoc networks potential increases in their achievable throughput and capacity. Due to recent advances in antenna technology, it is now affordable to build wireless devices with more than one antenna. As a result, multiple antennas are expected to be an essential part of next-generation wireless networks to support the rapidly emerging multimedia applications characterized by their high and diverse QoS needs. This paper develops an admission control framework that exploits the benefits of multiple antennas to better support applications with QoS requirements in wireless ad-hoc networks. The developed theory provides wireless ad-hoc networks with flow-level admission control capabilities while accounting for cross-layer effects between the PHY and the MAC layers. Based on the developed theory, we propose a mechanism that multiple antenna equipped nodes can use to control flows' admissibility into the network. Through simulation studies, we show that the proposed mechanism results in high flow acceptance rates and high network throughput utilization.     

Capacity Assignment in Bluetooth Scatternets – Optimal and Heuristic Algorithms

Bluetooth enables portable electronic devices to communicate wirelessly via short-range ad-hoc networks. Initially Bluetooth will be used as a replacement for point-to-(multi)point cables. However, in due course, there will be a need for forming multihop ad-hoc networks over Bluetooth, referred to as scatternets. This paper investigates the capacity assignment problem in Bluetooth scatternets. The problem arises primarily from the special characteristics of the network and its solution requires new protocols. We formulate it as a problem of minimizing a convex function over a convex set contained in the matching polytope. We develop an optimal algorithm which is similar to the well-known flow deviation algorithm and that calls for solving a maximum-weight matching problem at each iteration. A centralized heuristic algorithm with a relatively low complexity is also developed. Then, since in an ad-hoc network there is no central authority that is responsible for network optimization, a distributed heuristic algorithm is proposed. Finally, numerical results are presented and it is shown that the heuristic algorithms usually converge to results that are relatively close to the optimal results.     

Delay analysis in practical wireless network coding

Network coding provides a powerful mechanism for improving performance of wireless networks. In this paper, we present an analytical approach for end‐to‐end delay analysis in wireless networks that employs inter‐session network coding. Prior work on performance analysis in wireless network coding mainly focuses on the throughput of the overall network. Our approach aims to analyze the delay of each flow in the network. The theoretical basis of our approach is network calculus. In order to use network calculus to analyze the performance of traffic flows in the network, we have to address three specific problems: identifying traffic flows, characterizing broadcast links, and measuring coding opportunities. We propose solutions for these problems and discuss the practical issues when applying the approach in practice. We make three main contributions. First, we obtain theoretical formulations for computing the queueing delay bounds of traffic flows in wireless networks with network coding. Second, with the formulations, we figure out the factors that affect the queueing delay of a flow and find that first‐in first‐out scheduling cannot fully exploit the benefit of network coding. Third, in order to exploit our findings, we introduce a new scheduling scheme that can improve the performance of current practical wireless network coding. Copyright © 2012 John Wiley & Sons, Ltd.     

基于MC13192的家庭传感器网络的设计

ZigBee是一种低成本、低功耗、短距离的无线网络技术，非常适合家庭组网。介绍了以ZigBee芯片MC13192为核心组建的低功耗家庭无线传感器网络。重点阐述该网络的系统结构，微型节点的硬件实现和低功耗模式的选择，自组织组网和系统工作流程。     

基于共享路径和网络编码的光组播容量优化

为了降低光组播路由 的光域网络编码代价和提高达到理论最大光组播容量的 概率,提出一种基于共享链路和网络编 码的优化光组播容量方法。首先设计一种从多条源－ 宿最短路径中选择能达到最大光组播容量的最短路径簇,然后在 最短路径簇中计算路径的共享度,选择共享度高的组播路径传输网络编码信息,构造网络编 码次数最少的光组播编码子图, 解决传统的网络编码组 播路由和最大共享度链路组播路由中存在的网络编码次数过多和达到最大光组播容量概率过 低的问 题。仿真结果表明:本文提出的方法具有最低的网络编码代价,能以最大的概率达到光组播 理论最大容量。     

Insufficiency of linear coding in network information flow

It is known that every solvable multicast network has a scalar linear solution over a sufficiently large finite-field alphabet. It is also known that this result does not generalize to arbitrary networks. There are several examples in the literature of solvable networks with no scalar linear solution over any finite field. However, each example has a linear solution for some vector dimension greater than one. It has been conjectured that every solvable network has a linear solution over some finite-field alphabet and some vector dimension. We provide a counterexample to this conjecture. We also show that if a network has no linear solution over any finite field, then it has no linear solution over any finite commutative ring with identity. Our counterexample network has no linear solution even in the more general algebraic context of modules, which includes as special cases all finite rings and Abelian groups. Furthermore, we show that the network coding capacity of this network is strictly greater than the maximum linear coding capacity over any finite field (exactly 10% greater), so the network is not even asymptotically linearly solvable. It follows that, even for more general versions of linearity such as convolutional coding, filter-bank coding, or linear time sharing, the network has no linear solution.     

Reliable flow with failures in a network

In communication networks, there is a growing need for ensuring that networks maintain service despite failures. To meet this need, the concept of a δ-reliable channel is introduced; it is a set of communication channels along a set of paths. The δ-reliable channel meets the requirement that if a link or node fails, failure is limited to a maximum of δ·c (c≡total capacity of the channels, and 0<δ⩽1). A δ-reliable flow is such that the maximum number of flow failures is δ·f (f≡value of the flow) if an edge or vertex of a network fails. The max-flow min-cut theorem of δ-reliable flow is demonstrated for the single-commodity case     

Novel algorithms for the network lifetime problem in wireless settings

One of the major concerns in wireless ad-hoc networks design is energy efficiency. Wireless devices are typically equipped with a limited energy supply sufficient only for a limited amount of time which is reversely proportional to the transmission power of the device. The network lifetime is defined as the time the first device runs out of its initial energy charge. In this paper we study the maximum network lifetime problem for broadcast and data gathering in wireless settings. We provide polynomial time approximation algorithms, with guaranteed performance bounds while considering omnidirectional and unidirectional transmissions. We also consider an extended variant of the maximum lifetime problem, which simultaneously satisfies additional constraints, such as bounded hop-diameter and degree of the routing tree, and minimizing the total energy used in a single transmission. Finally, we evaluate the performance of some of our algorithms through simulations.     

Networks, Matroids, and Non-Shannon Information Inequalities

We define a class of networks, called matroidal networks, which includes as special cases all scalar-linearly solvable networks, and in particular solvable multicast networks. We then present a method for constructing matroidal networks from known matroids. We specifically construct networks that play an important role in proving results in the literature, such as the insufficiency of linear network coding and the unachievability of network coding capacity. We also construct a new network, from the Vamos matroid, which we call the Vamos network, and use it to prove that Shannon-type information inequalities are in general not sufficient for computing network coding capacities. To accomplish this, we obtain a capacity upper bound for the Vamos network using a non-Shannon-type information inequality discovered in 1998 by Zhang and Yeung, and then show that it is smaller than any such bound derived from Shannon-type information inequalities. This is the first application of a non-Shannon-type inequality to network coding. We also compute the exact routing capacity and linear coding capacity of the Vamos network. Finally, using a variation of the Vamos network, we prove that Shannon-type information inequalities are insufficient even for computing network coding capacities of multiple-unicast networks.     

QoE-based routing algorithms for H.264/SVC video over ad-hoc networks

Multi-hop relaying combined with scarcity of wireless resources in ad-hoc networks can deteriorate the quality of service. As a result, one of the major challenges in video streaming over ad-hoc networks is enhancing users’ experience and network utilization. The emergence of scalable video coding standard enables smooth adaptation of video quality to network conditions. In this paper, we study two optimization problems: (1) maximize the global quality of experience of all users and (2) maximize the number of qualified streams. We formulate the both problems as mixed integer linear programming problems. These optimization problems are shown to be NP-hard. Consequently, we propose heuristic algorithms to solve them. Simulation results show that the proposed algorithms can provide the near-optimal video quality while the calculation times are much shorter than the one of optimal solution.     

DynaMO: A Topology-Aware P2P Overlay Network for Dynamic,Mobile Ad-Hoc Environments

Due to the key differences between wired and ad-hoc wireless networks, traditional networking services and techniques are not always easily portable from an infrastructure based network to a wireless environment. One of the most prominent examples is the TCP transport protocol, which performs only poorly in wireless ad-hoc networks. The Peer-to-Peer (P2P) overlay networks recently developed all target the Internet where a lot of performance issues can be neglected or can be completely ignored. In addition, assumptions made for infrastructure based networks cannot be made in an ad-hoc environment, such as a fixed set of nodes which are always available. This article presents a P2P network tailored towards mobile ad-hoc environments. It utilizes proximity information to efficiently generate an overlay structure which reflects the underlying physical network topology. This way, physical routing path lengths stretched by the overlay routing process are reduced. As a novelty it does not rely on a fixed set of nodes and adapts to changes in the physical network topology. A prominent property of the overlay construction process is that the communication overhead is reduced to a minimum. Additionally, the P2P network presented maintains an even Overlay ID distribution which is deliberately given up by some solutions previously developed for wired networks. The basis of this new overlay network is Pastry, a P2P substrate based on the concept of a distributed hash table. Two different bootstrap strategies were developed and analyzed, both explicitly designed to work in dynamic and mobile networks such as ad-hoc networks.