Distributed Access Scheduling Algorithms in Wireless Mesh Networks

In this paper we have considered the distributed scheduling problem for channel access in wireless mesh networks. The problem is to assign time-slots for each node in the network to access the control channels so that it is guaranteed that each node can broadcast the control packet to any one-hop neighbor in one scheduling cycle. The objective is to minimize the total number of different time-slots in the scheduling cycle. In the single-channel ad hoc networks, the known best result for this problem is proved to be (K² + 1) in arbitrary graphs and 25K in unit disk graphs with K as the maximum node degree. The original contributions of this paper are that it has taken the large interference range problem into consideration for the first time and proposed two algorithms for the scheduling problem, namely, the one neighbor per cycle (ONPC) algorithm and the all neighbors per cycle (ANPC) algorithm. We prove that the number of time-slots by the second algorithm is upper-bounded by 2K in some special case. The fully distributed versions of these algorithms are given in this paper. Simulation results also show that the performance of ANPC is rather better than ONPC.