A time-slot and channel assignment algorithm in OFDM/TDMA wireless mesh networks

In order to use the available capacity of OFDM/TDMA wireless mesh networks as efficiently as possible, the maximum number of simultaneous transmissions must be scheduled in such a way that collisions are avoided. In order to achieve this goal, we introduce a scheduling algorithm that assigns both time slots and channels to wireless transmission links in a conflict free manner. For the scheduling of both time slots and channels, we introduce a new extended conflict graph consisting of two graphs, one weighted and claw-free, the other not weighted and not claw-free. For the purpose of maximizing the total throughput of the network, we propose an algorithm that finds the maximum independent set of the graphs. Since the second extended graph is not always claw-free, we introduce a greedy algorithm that finds an approximate maximum independent set of the second graph in polynomial time. Comparisons are made using our proposed algorithm and the exact graph coloring algorithm. As the simulation results show, the greatest throughput is achieved using the proposed algorithm.