Separation of Routing and Scheduling in Backpressure-Based Wireless Networks
Preprint
Abstract
Backpressure routing and scheduling, with its throughput-optimal operation guarantee, is a promising technique to improve throughput in wireless multi-hop networks. Although backpressure is conceptually viewed as layered, the decisions of routing and scheduling are made jointly, which imposes several challenges in practice. In this work, we present Diff-Max, an approach that separates routing and scheduling and has three strengths: (i) Diff-Max improves throughput significantly, (ii) the separation of routing and scheduling makes practical implementation easier by minimizing cross-layer operations; i.e., routing is implemented in the network layer and scheduling is implemented in the link layer, and (iii) the separation of routing and scheduling leads to modularity; i.e., routing and scheduling are independent modules in Diff-Max, and one can continue to operate even if the other does not. Our approach is grounded in a network utility maximization (NUM) formulation and its solution. Based on the structure of Diff-Max, we propose two practical schemes: Diff-subMax and wDiff-subMax. We demonstrate the benefits of our schemes through simulation in ns-2.Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- A Novel Architecture for Reduction of Delay and Queueing Structure Complexity in the Back-Pressure AlgorithmIEEE/ACM Transactions on Networking, 2011
- Queue Back-Pressure Random Access in Multihop Wireless Networks: Optimality and StabilityIEEE Transactions on Information Theory, 2009
- Fairness and Optimal Stochastic Control for Heterogeneous NetworksIEEE/ACM Transactions on Networking, 2008
- Greedy primal-dual algorithm for dynamic resource allocation in complex networksQueueing Systems, 2006
- A tutorial on cross-layer optimization in wireless networksIEEE Journal on Selected Areas in Communications, 2006
- Dynamic power allocation and routing for time-varying wireless networksIEEE Journal on Selected Areas in Communications, 2005
- Providing quality of service over a shared wireless linkIEEE Communications Magazine, 2001
- Scheduling and performance limits of networks with constantly changing topologyIEEE Transactions on Information Theory, 1997
- Dynamic server allocation to parallel queues with randomly varying connectivityIEEE Transactions on Information Theory, 1993
- Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networksIEEE Transactions on Automatic Control, 1992