Applying graph coloring in resour ce coordination for a high-density wireless environment

In a high density wireless environment, channel interference among users of many overlapped Basic Service Sets (OBSSs) is a serious problem. Our solution for the problem relies on a resource coordination scheme that utilizes the spatial distribution of the transceivers for channel reuse and time-slot division multiplexing for downlink transmission sharing among all participating BSSs. In this paper we show that an OBSS environment can be modeled by a planar graph and the OBSS group coordination assignment problem can be considered as a vertex coloring problem whose solution involves at most four colors. The graph coloring solution algorithm for the OBSS group coordination assignment is presented. The actual coloring is demonstrated, using a heuristics of Maximum Degree First. Performance simulation results of the coordination algorithm are also presented.