Scalable algorithms for wireless link schedulings in multi-channel multi-radio wireless networks
Authors:
- 1 April 2013
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 0743166X,p. 2121-2129
Abstract
For wireless link scheduling in multi-channel multi-radio wireless networks aiming at maximizing (concurrent) multi-flow, constant-approximation algorithms have recently been developed in [11]. However, the running time of those algorithms grows quickly with the number of radios per node (at least in the sixth order) and the number of channels (at least in the cubic order). Such poor scalability stems intrinsically from the exploding size of the fine-grained network representation upon which those algorithms are built. In this paper, we introduce a new structure, termed as concise conflict graph, on the node-level links directly. Such structure succinctly captures the essential advantage of multiple radios and multiple channels. By exploring and exploiting the rich structural properties of the concise conflict graphs, we are able to develop fast and scalable link scheduling algorithms for either minimizing the communication latency or maximizing the (concurrent) multi-flow. These algorithms have running time growing linearly in both the number of radios per node and the number of channels, while not sacrificing the approximation bounds.Keywords
This publication has 13 references indexed in Scilit:
- Weighted wireless link scheduling without information of positions and interference/communication radii2011
- Multiflows in multi-channel multi-radio multihop wireless networks2011
- 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
- Joint Channel Assignment and Routing for Throughput Optimization in Multiradio Wireless Mesh NetworksIEEE Journal on Selected Areas in Communications, 2006
- Architecture and algorithms for an IEEE 802.1 1 -based multi-channel wireless mesh network2005
- Routing and interface assignment in multi-channel multi-interface wireless networks2005
- Centralized channel assignment and routing algorithms for multi-channel wireless mesh networksACM SIGMOBILE Mobile Computing and Communications Review, 2004
- Smallest-last ordering and clustering and graph coloring algorithmsJournal of the ACM, 1983