Conflict Graph Based Concurrent Transmission Scheduling Algorithms for the Next Generation WLAN

Two conflict graph based concurrent transmission scheduling algorithms are proposed in this paper to efficiently solve the spatial TDMA (STDMA) scheduling problem for the next generation WLAN. Firstly, the STDMA scheduling problem for multiple timeslots is formulated as an multiple-step optimization problem. Secondly, a bi-weighted conflict graph is constructed to model the concurrent transmissions’ interference relationships, where the nodes denote the transmission request and the weights of the edges denote the interference level between any two transmission request nodes. If the interference between two transmission nodes is larger than the given interference threshold, then there are no edge between these two nodes. And only the acceptable interferences are modelled as the edges. Finally, a heuristic clique based algorithm (HCBA) and an optimal clique based algorithm (OCBA) are proposed, where HCBA assigns the transmission requests to the multiple timeslots one by one while OCBA assigns the transmission requests to the multiple timeslot once. The performance gap between the optimal one and the suboptimal one is evaluated. Simulation results show that HCBA not only has low complexity but also achieves similar performance comparing to OCBA.