Novel scheduling algorithms for concurrent transmit/receive wireless mesh networks
MetadataShow full item record
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.
Showing items related by title, author, creator and subject.
Xu, Y.; Chin, K.; Soh, Sie Teng; Raad, R. (2016)A key advance in enabling higher wireless mesh network capacity is allowing routers to transmit or receive (MTR) from multiple neighbors simultaneously over the same frequency. Achieving this capacity, however, is predicated ...
Chin, Kwan-wu; Soh, Sieteng; Meng, C. (2010)The success of wireless mesh networks hinges on their ability to support bandwidth intensive, multi-media applications. A key approach to increasing network capacity is to equip wireless routers with smart antennas. These ...
Nordin, Syarifah Zyurina (2011)Task scheduling in parallel processing systems is one of the most challenging industrial problems. This problem typically arises in the manufacturing and service industries. The task scheduling problem is to determine a ...