Practical fast scheduling and routing over slotted CSMA for wireless mesh networks
Takuya Yoshihiro, Taiki Nishimae · 2016
Although Wireless Mesh Networks (WMNs) over CSMA and TDMA MAC have been extensively studied, CSMA still suffers from heavy interference due to hidden terminals, while TDMA has a practical difficulty in accurate time synchronization. Slotted CSMA, in which we assume that CSMA runs within relatively large time-divided slots, could be one of the solutions since it works on loosely synchronized time slots and simultaneously avoids major collision under a properly designed feasible schedule. However, if we apply a schedule generally used in TDMA, there are several inconveniences: First, we need heavy overhead of centralized computation or negotiation among nodes in distributed scheduling. Second, end-to-end packet delivery delay grows large since TDMA requires a large number of slots to achieve collision-free scheduling. In this paper, we propose a new scheduling algorithm for slotted CSMA called CATBS (CSMA-Aware Time-Boundable Scheduling) that requires a smaller number of slots for feasible scheduling, and runs within a bounded time. Incorporating the scheduling, we design a routing protocol that enables flexible paths recomputation with small communication overhead. We consequently achieve a new fully distributed and robust network architecture of WMNs that provides practically high throughput and low delivery delay, which can be implemented on the off-the-shelf IEEE802.11 interfaces.