Novel scheduling algorithms for concurrent transmit/receive wireless mesh networks

Recently, in an effort to increase the capacity of Wireless Mesh Networks (WMNs), researchers have begun equipping routers with multiple interfaces/radios, and connecting each one to a directional or smart antenna. A key feature of these routers is their ability to transmit or receive from multiple neighbors simultaneously. Hence, they have orders of magnitude higher capacity than their omni-directional counterparts. This significant capacity increase, however, is predicated upon a link scheduling algorithm that maximizes the number of active links at any given point in time. This paper proposes a number of link activation algorithms that derive maximal bipartite graphs from general topologies. These algorithms provide different trade-offs in terms of computation time and optimality. A key highlight is a greedy algorithm that has a time complexity of O(∣V∣2), where V is the set of routers. Apart from that, we outline two algorithms that use an approximation to the well known maximum cut problem, and also a brute force algorithm, which is capable of deriving an optimal link activation schedule. The output from our algorithms can then be used by a spatial Time Division Multiple Access (TDMA) Medium Access Control (MAC) protocol to schedule concurrent transmitting and receiving links. We have verified our algorithms on various topologies with increasing node degrees as well as node numbers. From extensive simulation studies, we find that our algorithms have good performance in terms of number of links activated, superframe length, and end-to-end packet delay.