Abstract

Over the last decade, the wireless telephony market has experienced significant changes due to an increase in consumer demand, competition and rapid technological changes which reduced the effective life cycle of network infrastructures. Under these conditions, sustaining the growth and profitability of operations has been increasingly dependent on the efficient management of the available resources. In this research, we examine optimization problems that arise in the design and upgrade processes of the wireless component of GSM type cellular networks, namely, the antenna positioning problem (APP) and the frequency allocation problem (FAP). APP examines the deployment of antennas throughout the service area. We propose integrated problem formulations that bring together the variety of design criteria raised both by practitioners and in the academic literature. In addition, current practices mostly use a sequential decomposition of the design process whereby the APP solution becomes a fixed input to FAP, as the simultaneous optimization would be too complex to tackle for realistic instances. In order to integrate the design process, we propose a partial incorporation of frequency allocation considerations within APP, with a limited increase in problem complexity. Frequency management focuses on allocating a very limited radio spectrum so as to optimize the quality of service. This problem is first examined in the context of static networks, for which we develop an adaptive Tabu Search algorithm that dynamically combines several operators and search mechanisms to minimize network interference. As for Frequency Hopping networks, frequency management also entails determining the hopping sequences in addition to determining the frequency allocation. We analyze this problem for three levels of network synchronization and develop heuristic procedures to determine the parameter setting that will optimize the hopping sequences. In addition, for fully-synchronized networks, we propose to sidestep the sequence generation procedure currently used in the GSM standard, to directly generate optimized sequences. The optimization problems considered in this work are intractable, with realistic instances being of large size and being based on estimated data. Therefore, heuristic optimization techniques are considered for solving them. We use real-life networks provided by telecom operators to test the problem formulations and the proposed optimization algorithms.