We consider practical network coding, a useful generalization of routing, in multi-hop multicast wireless networks. The model of interest comprises a set of nodes transmitting data wirelessly to a set of destinations across an arbitrary, unreliable, and possibly time-varying network. This model is general and subsumes peer-to-peer, ad-hoc, sensory, and mobile networks. It is first shown that, in the singlehop case, the idea of adaptively matching code-on-graph with network-on-graph, first developed in the adaptive-network-coded-cooperation (ANCC) protocol, provides a significant improvement over the conventional strategies. To generalize the idea to the multi-hop context, we propose to transform an arbitrarily connected network to a possibly time-varying “trellis network,” such that routing design for the network becomes equivalent to path discovery in the trellis. Then, exploiting the distributed, real-time graph-matching technique in each stage of the trellis, a general network coding framework is developed. Depending on whether or not the intermediate relays choose to decode network codes, three practical network coding categories, progress network coding, concatenated network coding and hybrid network coding, are investigated. Analysis shows that the proposed framework can be as dissemination-efficient as those with random codes, but only more practical.
TopIntroduction
We consider multi-hop multicast data transmission in a general wireless network. The model of interest here comprises a set of nodes transmitting data wirelessly to a set of common destinations across an arbitrary, unreliable and possibly time-varying network. Our model is very general, and subsumes many specialized networks including peer-to-peer, ad-hoc, sensory and mobile networks.
Essential to network operation is user cooperation, where multiple nodes share resources to collaboratively accomplish a communication or computation task. User cooperation, arranged possibly in the physical, MAC, network, and application layer, or across these layers, is particularly important to the wireless scenario: While a single wireless channel may be useless due to fading or shadowing, combined together a set of channels may become useful again. The fundamental question we ask is: How do users cooperate in an efficient and trust-worthy manner? Because of the dynamic and unreliable nature of the underlying wireless network, an algorithm must be de-centralized and self-adaptive to be practical, scalable and robust.
In attacking this challenge, we resort to the recently-developed technology of network coding (Ahlswede, Cai, Li & Yeung, 2000; Li, Yeung & Cai, 2003; Zhang, Liew & Lan, 2006; Katti et al 2006), which is a form of user cooperation by nature. Traditional store-and-forward routing fails to exploit network capacity. By allowing intermediate relaying nodes to perform simple coding functions across different packets coming from different up-streams, network coding provides new capabilities to routing, and opens the possibility to achieve optimal network throughput. For example, in the renowned example of the butterfly network (Figure 7 in (Ahlswede, Cai, Li & Yeung, 2000)), the two receivers will each receive 1 symbol per cycle if the traditional store-and-forward routing is used, 1.5 symbols per cycle if time-sharing is used in combination with routing, but 2 symbols per cycle (which is also the max-flow min-cut bound of this network) if network coding is used. Hence, network coding is also known as generalization of routing}, or, intelligent routing.
Network coding was initially introduced to maximize the end-to-end throughput in lossless networks. Here, by lossless, we mean that the links have transmission rates limited by some positive number called the link capacity, but are otherwise free from noise and outage. Recent work has come to look at more practical networks such as the Internet and wireless networks.
From the practical point of view, network coding is more appealing to wireless networks than wireline networks. This is because the coding operation performed at each intermediate router, although presumably simple and fast, could amount to an unacceptably large complexity and delay for today's ultra-fast networks that typically operate at gigabits per second or faster. Comparatively, wireless networks are much slower and far less reliable, and can therefore take advantage of the diversity gain enabled by network coding without sacrificing other performance aspects. Furthermore, the wireless media actually makes network coding cheaper, since broadcasting (almost always needed for network coding) is achieved at no additional cost over unicast.
On the other hand, the wireless media also imposes two constraints on the design and operation of network codes:
- (1)
For wireline networks, it is in general beneficial for each out-edge of a network node to carry its own specific function of the in-edges symbols, namely, the coding function is edge-dependent or in the point-to-point mode (Appuswamy, Franceschetti & Zeger, 2006). For wireless networks, due to the broadcast nature of wireless media, every out-edge symbol carries the same function of the in-edges symbols, forcing the coding function to be node-dependent or in the broadcast-mode.
- (2)
Due to the possibility of random fading, link outage and node mobility, the topology of a wireless network may be continually changing. What this implies on network coding design is the need for a distributed and adaptive algorithm.