Simple and Effective Scheduling in Wireless Networks Under the Physical Interference Model

Date Added: Jul 2010
Format: PDF

In this paper, the authors study the problem of maximizing the number of concurrent requests and the problem of minimizing the number of time-slots needed to schedule all requests in wireless networks under the physical interference model. It has been proved that both problems are NP-complete. Thus, either approximation algorithms with guaranteed approximation factors or effective heuristics with practically good performances are desirable. They focus on the latter and present simple and effective heuristic algorithms for these two problems. Extensive experiments show that the algorithm for the first problem outperforms the best approximation algorithm by 62% − 72% on average and the two algorithms for the second problem give the best results among existing algorithms.