AN ENUMERATION ALGORITHM FOR OPTIMAL CLUSTERING OF BASE STATIONS IN MOBILE RADIO COMMUNICATION SYSTEM

Syed Zahid Ali

   In a mobile radio communication system, mobile terminals are free to travel within the service area. In order to track a mobile terminal in a cellular mobile network, the radio coverage area of a network is partitioned into clusters of Base Stations, called Location Areas. As mobile terminals cross the boundaries of Location Areas, a significant overhead `location-updating traffic' is injected into the controlling signalling network. The aim of this paper is to solve the problem of finding optimum Location Areas for a given network such that the load of location-update-signalling traffic on the signalling network is minimized on the basis that the intra-cluster communication is less expensive than the inter-cluster communications. This problem belongs to the family of Non-Polynomial Complete (NP) problems. In this paper, this problem is formulated in terms of an Integer Programming problem and a special tailored Branch and Bound algorithm is applied to find guaranteed optimal solutions. By considering a range of network problems, it is demonstrated that the proposed technique can be applied to solve optimally the real-world network problems.

Keywords: networks, graph theory, optimization, communication system signalling

[full-paper]