Scalable Algorithms for Wireless Link Schedulings in Multi-Channel Multi-Radio Wireless Networks

Abstract—For wireless link scheduling in multi-channel multi-radio wireless networks aiming at maximizing (concurrent) multiflow, 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) multiflow. 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. Index Terms—Link scheduling, multi-channel multi-radio, ap-proximation algorithms. I