Scheduling algorithms for multiple channel wireless local area networks

This paper describes algorithms for scheduling traffic in wireless data networks with multiple channels per cell. The paper assumes that a reservation-based medium access control protocol is used. The main objective of the scheduling algorithms is to reduce the computation time while maximizing the utilization of the network resources, thereby improving the system throughput. The scheduling problem is presented as a variant of the bin-packing problem. In this paper, we consider two type of algorithms-contiguous and non-contiguous allocations. The algorithms are studied for wireless networks with single priority traffic and multiple priority traffic. A performance study that considers network utilization, computation time, and the throughput for 10 and 54 Mbps data-streams is presented. The results show that both the proposed algorithms perform better than MULTI-FIT in terms of overall throughput and computation time; and that the non-contiguous allocation performs better than the contiguous algorithm since the former results in smaller number of wasted slots. (C) 2002 Elsevier Science B.V. All rights reserved.