Location-area partition in a cellular radio network

With an increasing population of mobile subscribers, the signalling traffic to control the subscriber mobility expands rapidly. Subscriber mobility is controlled through location registration based on the so-called location area, the basic area unit for paging which consists of a number of cells. There is a tradeoff between the two kinds of signalling traffic: paging and location updating. As location areas include a larger number of cells, the traffic volume for paging increases while that for location updating decreases. Given not only the pattern of call arrivals but also that for subscriber mobility, our problem is to minimise the total signalling traffic by optimally partitioning the whole area into location areas. We show that this problem can be transformed to the so-called clique partitioning problem (CPP). Also we demonstrate the process of implementing the algorithm for solving the CPP for real-world problems defined on the cellular network in Seoul.