Cellular network configuration with co-channel and adjacent-channel interference constraints

Design of cellular networks has drawn much recent interest from the OR scientific community. A challenging issue is the handling of channel interference constraints. Co-channel interference occurs when the same channel is reused within a threshold distance. Adjacent-channel interference occurs when two channels with adjacent or nearby frequencies are used in the same cell tower. We present a mathematical programming formulation for this channel allocation problem with both types of interference constraints-it also includes decisions on location of cell towers. Our focus is on the special case where a cell tower and/or channel can interfere with at most two other towers/channels. By establishing theoretical properties for channel allocation amongst towers under this circumstance, we develop an efficient solution procedure. An iteration of the procedure uses a heuristic to locate the cell towers, then allocates the channels to the towers using a polynomial-time algorithm, and finally improves this allocation using a simulated annealing procedure. The iterative steps are embedded within an external simulated annealing method. This nested simulated annealing procedure provides encouraging computational results compared to a standard commercial solver like ILOG CPLEX 8.1. The major contribution of the work is the simultaneous consideration of co-channel and adjacent-channel interference constraints.