Multiflows in multi-channel multi-radio multihop wireless networks
Open Access
- 1 April 2011
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 0743166X,p. 846-854
Abstract
This paper studies maximum multiflow (MMF) and maximum concurrent multiflow (MCMF) in muliti-channel multi-radio multihop wireless networks under the 802.11 interference model or the protocol interference model. We introduce a fine-grained network representation of multi-channel multi-radio multihop wireless networks and present some essential topological properties of its associated conflict graph. By exploiting these properties, we develop practical polynomial approximation algorithms for MMF and MCMF with constant approximation bounds regardless of the number of channels and radios. Under the 802.11 interference model, their approximation bounds are at most 20 in general and at most 8 with uniform interference radii; under the protocol interference model, if the interference radius of each node is at least c times its communication radius, their approximation bounds are at most 2 (⌈π/ arcsin c-1/2c⌉ + 1). In addition, we also prove that if the number of channels is bounded by a constant (which is typical in practical networks), both MMF and MCMF admit a polynomial-time approximation scheme under the 802.11 interference model or under the protocol interference model with some additional mild conditions.Keywords
This publication has 12 references indexed in Scilit:
- Weighted wireless link scheduling without information of positions and interference/communication radii2011
- Approximate Capacity Subregions of Uniform Multihop Wireless Networks2010
- Multiflows in multihop wireless networks2009
- Distributed Strategies for Channel Allocation and Scheduling in Software-Defined Radio Networks2009
- Understanding the Capacity Region of the Greedy Maximal Scheduling Algorithm in Multi-Hop Wireless Networks2008
- Interference-Aware Joint Routing and TDMA Link Scheduling for Static Wireless NetworksIEEE Transactions on Parallel and Distributed Systems, 2008
- Algorithmic aspects of capacity in wireless networksACM SIGMETRICS Performance Evaluation Review, 2005
- Centralized channel assignment and routing algorithms for multi-channel wireless mesh networksACM SIGMOBILE Mobile Computing and Communications Review, 2004
- Characterizing achievable rates in multi-hop wireless networks2003
- Impact of interference on multi-hop wireless network performance2003