A randomized saturation degree heuristic for channel assignment in cellular radio networks

In this paper, we investigate the channel assignment problem, that is, the problem of assigning channels (codes) to the cells of a cellular radio netw ork so as to avoid interference and minimize the number of channels used. T he problem is formulated as a generalization of the graph coloring problem. We consider the saturation degree heuristic, first proposed as a technique for solving the graph coloring problem, which was already successfully use d for code assignment in packet radio networks. We give a new version of th is heuristic technique for cellular radio networks, called randomized satur ation degree (RSD), based on node ordering and randomization. Furthermore, we improve the solution given by RSD by means of a local search technique. Experimental results show the effectiveness of the heuristic both in terms of solution quality and computing times.