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

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 increase however is predicated on an effective link scheduler. The aim of any scheduler is to derive a superframe comprising the smallest number of slots that affords each link one or more transmission opportunities. In particular, the scheduler is required to solve an instance of the NP-complete, MAX-CUT problem, in each time slot. 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.