Channel assignment for interference avoidance in honeycomb wireless networks

The large development of wireless services and the scarcity of the usable frequencies require an efficient use of the radio spectrum which guarantees interference avoidance. The Channel Assignment Problem (CAP) 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 geographical barriers and with uniform traffic load, the network base stations are usually placed according to a regular plane tessellation, while the channels are permanently assigned to the base stations. This paper considers the CAP problem on the honeycomb grid network topology, where the plane is tessellated by regular hexagons. 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 between the stations. Under these assumptions, the CAP problem on honeycomb grids can be modeled as a suitable coloring problem. Formally, given a honeycomb grid $G=(V,E)$ and a vector $(delta_1, delta_2, ldots, delta_{t})$ of positive integers, an $L(delta_1, delta_2, ldots,delta_{t})$-coloring of $G$ is a function $f$ from the vertex set $V$ to a set of nonnegative integers such that $|f(u)-f(v)| ge delta_i$, if $d(u,v) = i, 1 le i le t, $ where $d(u,v)$ is the distance (i.e. the minimum number of edges) between the vertices $u$ and $v$. An optimal $L(delta_1, delta_2, ldots,delta_{t})$-coloring for $G$ is one minimizing the largest used integer over all such colorings. This paper presents efficient algorithms for finding optimal $L(2,1)$-, $L(2,1^2)$- and $L(1^t)$-colorings of honeycomb grids. Such colorings use less colors than those needed by the cellular and square grids with the same number of vertices.