Channel assignment with separation in wireless networks based on regular plane tessellations

The large development of wireless services and the scarcity of the us- able frequencies require an efficient use of the radio spectrum which guarantees interference avoidance. The Channel Assignment (CA) problem achieves this goal by partitioning the radio spectrum into disjoint channels, and assigning channels to the network base stations so as to avoid interference. On a flat region without geo- graphical barriers and with uniform traffic load, the network base stations are often placed according to a regular plane tessellation, while the channels are permanently assigned to the base stations. This paper surveys the CA problem on grid network topologies, where the plane is tessellated by regular polygons. Interference between two base stations at a given distance is avoided by forcing the channels assigned to such stations to be separated by a gap which is proportional to the distance be- tween the stations. Under these assumptions, the CA problem can be modeled as a suitable coloring problem. Formally, given an undirected graph G = (V , E) and a vector (?1 , ?2 , . . . , ??-1 ) of positive integers, an L(?1 , ?2 , . . . , ??-1 )-coloring of G is a function f from the vertex set V to a set of nonnegative integers such that |f (u) - f (v)| >= ?i , if d(u, v) = i, 1 <= i <= ? - 1, where d(u, v) is the distance (i.e. the minimum number of edges) between the vertices u and v. An opti- mal L(?1 , ?2 , . . . , ??-1 )-coloring for G is one minimizing the largest used integer over all such colorings. This paper surveys efficient algorithms for finding optimal L(2, 1)- and L(2, 1, 1)-colorings of honeycomb, square, and cellular grids.