Distributed Scheduling With Centralized Coordination for Scalable Wireless Mesh Networking

A coordinated carrier sense multiple access (C-CSMA) scheme is developed to schedule packet transmissions in multihop wireless networks. It integrates distributed scheduling and centralized coordination at different time scales. At a small time scale, a distributed scheduling algorithm, which is incorporated into CSMA, runs on each node to determine key parameters for CSMA. These parameters are optimized by ensuring multiple network attributes, i.e., average link date rate, node transmission probability, and the conditional probability of a link being selected for transmission, approaching their corresponding optimal values at a large time scale, e.g., a few seconds. Such optimal values are obtained from a centralized algorithm running on a portal node. The algorithm collects topology, link, and traffic information from the network at a large time scale and determines the attributes above to fulfill the optimal tradeoff between throughput and fairness. Since the distributed algorithm is shepherded by the centralized algorithm, C-CSMA has high scalability: first, it achieves long-term optimal performance with low information collection overhead; second, it schedules packet transmissions in a distributed way and responds quickly to changes in networks. It is proved that network attributes resulting from the distributed scheduling algorithm converge to optimal values provided by the centralized algorithm. Simulation experiments demonstrate that the convergence speed is fast. Moreover, extensive simulation results show that C-CSMA achieves much higher throughput, better fairness, and lower delay than existing scheduling schemes under different carrier sensing thresholds and traffic conditions.