Efficient use of radio spectrum in wireless networks with channel separation between close stations

This paper investigates the problem of assigning channels to the stations of a wireless network so that interfering transmitters are assigned channels with a given separation and the number of channels used is minimized. Two versions of the channel assignment problem are considered which are equivalent to two specific coloring problems - called L(2, 1) and L(2, 1, 1) - of the graph representing the network topology. In these problems, channels assigned to adjacent vertices must be at least 2 apart, while the same channel can be reused only at vertices whose distance is at least 3 or 4, respectively. Efficient channel assignment algorithms using the minimum number of channels are provided for specific, but realistic, network topologies, including buses, rings, hexagonal grids, bidimensional grids, cellular grids, and complete binary trees.