A Distributed Maximal Link Scheduler for Multi Tx/Rx Wireless Mesh Networks

Abstract

The capacity of Wireless Mesh Networks (WMNs) has significantly increased with the recent addition of multiple transmit (Tx) and receive (Rx) (MTR) capability or smart antennas. This capacity increase however is predicated on an efficient link scheduler. The aim of any scheduler is to derive a superframe comprising of smallest number of slots that affords each link one or more transmission opportunities. Unfortunately, deriving a minimal superframe length is equivalent to solving the NP-complete, MAX-CUT problem. To this end, there are a number of centralized schedulers, but only a handful of distributed schedulers. However, each of these distributed schedulers has its own drawbacks; either they do not guarantee maximal activated links or do not guarantee all links are activated. Henceforth, in this paper, we add to the state-of-the-art by proposing a novel distributed scheduler, called Algo-d, which approximates the MAX-CUT problem in a distributed manner using only local information. In fact, this is the first distributed solution for MAX-CUT problem. Through theoretical analysis and simulation, we show that Algo-d achieves the following performance: 1) Algo-d schedules on average 12\% fewer and 46.5\% more links in each time slot than two centralized algorithms, and 2) Algo-d schedules 28\% more links than ROMA and 270\% more links than JazzyMAC; both state-of-the-art distributed schedulers for MTR WMNs.