A distributed scheduling framework for multi-user diversity gain and quality of service in wireless mesh networks

Wireless multi-hop, mesh networks are being considered as a candidate for wireless backhaul networks which carry data traffic between access networks and the wired Internet. Although existing scheduling algorithms have been adopted for the wireless backhaul networks, they do not yield good performance. In this paper, we study the computational complexity of finding the optimal link schedule for the wireless mesh networks with time-division-duplexing (TDD) operations. We show that the problem of finding the optimal schedule for the mesh networks is #P-complete. Consequently, we propose a heuristic distributed scheduling algorithm and a link utility function for wireless mesh networks. Performance analysis shows that our proposed framework is of linear-time complexity and the proposed utility function makes the long-term throughput allocation converge to the desired level which is proportional to the requirements specified by the routing protocol in use to guarantee quality of service (QoS). Moreover, we show that our framework maintains strong temporal correlation of interference, which is required to ensure proper channel predictions for distributed scheduling and power control. Finally, we compare our scheduling algorithm with a previously proposed "tree" scheduling and a centralized "ideal" scheduling. Simulation results reveal that the proposed algorithm achieves high efficiency in terms of network objective as well as the overall network throughput.