Channel assignment for interference avoidance in honeycomb wireless networks

Abstract: 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 and a vector of positive integers, an -coloring of is a function from the vertex set to a set of nonnegative integers such that , if , where is the distance (i.e. the minimum number of edges) between the vertices and . An optimal -coloring for is one minimizing the largest used integer over all such colorings. This paper presents efficient algorithms for finding optimal -, - and -colorings of honeycomb grids. Such colorings use less colors than those needed by the cellular and square grids with the same number of vertices. [Copyright &y& Elsevier]