04-05-2011, 11:11 AM
Toward Practical Opportunistic Routing With Intra-Session Network Coding for Mesh Networks
Abstract
We consider opportunistic routing in wireless meshnetworks. We exploit the inherent diversity of the broadcastnature of wireless by making use of multipath routing. Wepresent a novel optimization framework for opportunistic routingbased on network utility maximization (NUM) that enables usto derive optimal flow control, routing, scheduling, and rateadaptation schemes, where we use network coding to ease therouting problem. All previous work on NUM assumed unicasttransmissions; however, the wireless medium is by its naturebroadcast and a transmission will be received by multiple nodes.The structure of our design is fundamentally different; this is dueto the fact that our page link rate constraints are defined per broadcastregion instead of links in isolation. We prove optimality andderive a primal-dual algorithm that lays the basis for a practicalprotocol. Optimal MAC scheduling is difficult to implement, andwe use 802.11-like random scheduling rather than optimal in ourcomparisons. Under random scheduling, our protocol becomesfully decentralized (we assume ideal signaling). The use of networkcoding introduces additional constraints on scheduling, and wepropose a novel scheme to avoid starvation. We simulate realistictopologies and show that we can achieve 20%–200% throughputimprovement compared to single path routing, and several timescompared to a recent related opportunistic protocol (MORE).Index Terms—Broadcast, fairness, flow control, multipathrouting, network coding, opportunistic routing, rate adaptation,wireless mesh networks.
I. INTRODUCTION
ONE of the main challenges in building wireless meshnetworks [1]–[3] is to guarantee high performance despitethe unpredictable and highly variable nature of the wirelesschannel. In fact the use of wireless channels presents someunique opportunities that can be exploited to improve the performance.For example, the broadcast nature of the medium canbe used to provide opportunistic transmissions as suggested in[4]. In addition, in wireless mesh networks, there are typicallymultiple paths connecting each source destination pair, henceusing some of these paths in parallel can improve performance[5], [6].However, most of the existing work on optimal wireless protocoldesign (cf. [7]) ignores the broadcast nature of the channel. Instead, a transmitter selects a priori the next-hop for a packet,and if the selected next-hop has not received the packet, thepacket is retransmitted (even though another next-hop neighbormay have received it correctly). The routing is not opportunistic(as in [4]), and the diversity of the broadcast medium is ignored.The main focus of this paper is the optimal use of both multiplepaths and opportunistic transmission.We use intra-sessionnetwork coding [8] to simplify the problem of scheduling packettransmissions across multiple paths, as others have done [5], [6],[9]. We propose a network optimization framework that optimizesthe rate of packet transmissions between source and destinationpairs.In order to use the resources of a wireless mesh network efficiently,the system needs to take into account: 1) the existence ofmultiple paths; 2) the unreliable nature of wireless links; 3) theexistence of multiple transmission powers and rates (which inturn affects the probability of correct packet reception); 4) thebroadcast nature of the channel; 5) competition among manyflows; 6) fairness and efficiency. Observe that optimizing acrossall these parameters implies optimizing across multiple layers ofthe networking stack; for example, the choice of transmissionpower and rate is typically done at the physical layer, whereascoordination among different flows is typically done at the networklayer. As we shall see, it is important to perform suchcross-layer optimizations to achieve optimal performance.We use an optimization framework to design a distributedmaximization algorithm.We account for transport layer controlsand address questions of fairness by maximizing the aggregateutility of the end-to-end flows, where we associate a utility functionwith a flow. Because we use network coding, our optimizationleverages existing theory [9], [10]. Our algorithm isa primal-dual algorithm [11]. The primal formulation expressesthe optimization problem as a function of the rates of the variousflows in the network; the dual formulation uses as variablesthe queue lengths (per flow and per node). The main advantageof using the dual formulation of the optimization problemis that the dual variables (also referred as shadow prices) relateto queue lengths and can be directly used by back-pressurealgorithms for flow control [7], [12]. As a simple example,a large number of queued packets for a particular flow at aninternal node can be interpreted that the path going throughthat node is congested and should be avoided. The main advantageof using the primal-dual formulation is that it adaptsthe primal variables (i.e., flow rates) more slowly, hence, allowsTCP-like window-based rate control modeling (as originallymentioned by Erylimaz et al. [12]).We propose a novel algorithmfor cross-layer optimization and prove, using Lyapunovfunctions, that it converges to the optimal rate allocation. Despite using similar optimization techniques to prior work(e.g., [7] and [11]–[14]), the solution to our problem is very different.We define rate constraint for each set of broadcast receivers.Consequently, dual variables are related to these broadcastsets and allow us to adjust the level of opportunism as afunction of a congestion in the rest of the network.The proposed optimization framework is difficult to implement;indeed, the joint scheduling, rate, and power controlproblem is NP-hard [15]. Additionally, current wireless MACprotocols use uncontrolled randomized channel scheduling.Wepropose a distributed heuristic based on the optimal algorithm.We show that, even in the absence of optimal channel scheduling,the other aspects of the optimization problem (i.e., flowselection and transmission rate selection) still give performanceadvantages. Hence, our heuristic hints toward an implementationin practical systems. The fundamental idea behind ouralgorithm (and of its distributed implementation) is to assigncredits to nodes, transfer credits between nodes, and scheduleon the basis of credits (see Section III for more details).The main contributions of our paper are as follows:• We propose a network wide optimization algorithm thatmaximizes rate-based global network performance andextends previous work by incorporating broadcast/opportunisticrouting, multipath routing, and fairness/ratecontrol (Sections II and III). We introduce a notion ofvirtual packets, called credits, that enable us to decouplerouting and flow control from actual packet transmissionsand delivery. We prove the optimality of the algorithm.• Based on the optimization algorithm, we give a distributedimplementation (assuming ideal signaling) of routing, rateadaptation, and flow control for networks with randomscheduling (Section III-C) that outperforms existing algorithms.We prove that our algorithms extends and outperformsa recent proposal, MORE [5]. The distributed algorithmcan be used with the current 802.11 MAC and, indeed,is MAC-independent.• Practical network coding schemes use finite generationsizes. We show that a naive approach for schedulinggenerations may lead to starvation. We propose a novelheuristic, and we demonstrate that it circumvents networkstarvation (Section IV-A).• We demonstrate that rate selection is important for optimizingperformance in 802.11a networks (Section IV-B).We confirm the findings from [5] that such optimizationsare not necessary for 802.11b networks.• Using simulation on realistic topologies, we show we canachieve 20%–100% throughput improvement with our distributedimplementation compared to single path routing,and 20%–300% compared to MORE [5] (Section V).1
Download full report
http://research.microsoftpubs/104951/main.pdf
