A Classification Framework for Scheduling Algorithms in Wireless Mesh Networks

Scheduling MAC-layer transmissions in multi-hop wireless networks is an active and stimulating area of research. There are several interesting algorithms proposed in the literature in the problem space of scheduling for multi-hop wireless networks, specifically for (a) WiMAX mesh networks, (b) long distance multi-hop WiFi networks, and (c) Vehicular Ad-hoc Networks (VANETs). In general, these algorithms have several dimensions in terms of the assumptions made, the input space considered and the solution space generated. In this context, the goal of this survey is three-fold. Firstly, we classify the scheduling algorithms proposed in the literature based on following parameters: problem setting, problem goal, type of inputs and solution technique. Secondly, we describe different scheduling algorithms based on this classification framework. We specifically cover the state-of-the-art scheduling mechanisms proposed for generic multi-channel, multi-radio wireless mesh networks and in particular scheduling algorithms for WiMAX mesh networks, long distance mesh networks and vehicular ad-hoc networks. We describe scheduling algorithms which consider scheduling data, voice as well as video traffic. Finally, we compare these algorithms based on our classification parameters. We also critique individual mechanisms and point out the practicality and the limitations, wherever applicable. We observe that, the literature in the domain of scheduling for wireless mesh network is quite extensive, in terms of depth as well as breadth. Our classification framework helps in understanding the pros and cons of various aspects of scheduling for wireless multi-hop (popularly known as wireless mesh) networks. We also list desirable properties of any scheduling mechanism and use our classification framework to point out the open research issues in the space of scheduling for wireless mesh networks.