Channel allocation in cellular radio networks

In this article, two efficient heuristic algorithms are suggested for the channel allocation problem which minimizes the average blocking probability of the whole network subject to the co-channel, adjacent-site and co-site interference constraints, given the number of available channels. We convert this problem into a convenient form using the piecewise linearization technique and the concept of pattern, and apply Lagrangean relaxation and subgradient optimization techniques. Computational experiments show that this procedure provides high-quality solutions with information about their error ranges for networks with special compatibility matrices. We also suggest a general procedure using a GOS (grade of service) updating scheme, and provide encouraging computational results. (C) 1997 Elsevier Science Ltd.