Static frequency assignment in cellular networks

A cellular network is generally modeled as a subgraph of the triangular lat tice. In the static frequency assignment problem, each vertex of the graph is a base station in the network, and has associated with it an integer wei ght that represents the number of calls that must be served at the vertex b y assigning distinct frequencies per call. The edges of the graph model int erference constraints for frequencies assigned to neighboring stations. The static frequency assignment problem can be abstracted as a graph multicolo ring problem. We describe an efficient algorithm to multicolor optimally an y weighted even or odd length cycle representing a cellular network. This r esult is further extended to any outerplanar graph. For the problem of mult icoloring an arbitrary connected subgraph of the triangular lattice, we dem onstrate an approximation algorithm which guarantees that no more than 4/3 times the minimum number of required colors are used. Further, we show that this algorithm can be implemented in a distributed manner, where each stat ion needs to have knowledge only of the weights at a small neighborhood.