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 pr obability of the whole network subject to the co-channel, adjacent-sit e and co-site interference constraints, given the number of available channels. We convert this problem into a convenient form using the pie cewise linearization technique and the concept of pattern, and apply L agrangean relaxation and subgradient optimization techniques. Computat ional experiments show that this procedure provides high-quality solut ions with information about their error ranges for networks with speci al compatibility matrices. We also suggest a general procedure using a GOS (grade of service) updating scheme, and provide encouraging compu tational results. (C) 1997 Elsevier Science Ltd.