OR/MS Today - April 2002 Frequency Allocation Canadian Telecom Makes the Right Call by Jean-Marie Bourjolly, Leslie Déjoie, Ke Ding, Oumar Dioume and Michel Lominy Frequency allocation has been solved by a number of operations researchers in various settings. While there is an abundance of technical papers on this subject, there are few publications related to real-life implementations. This article presents the problem from the point of view of the telecommunications operators as well as from that of the OR modelers. It documents a successful solution devised by our university-industry team, a solution that has been tested and fully implemented on existing cellular networks. Prestige Telecom is a medium-size telecommunications firm located in Montreal. Its core competency has been to act as an engineering, furnishing and installation subcontractor to large corporations such as Bell Canada and Nortel. At the end of 1995, management decided to embark on a program that would allow the company to tap into the world market of small- to medium-size operators by offering them engineering services that would range from occasional consulting contracts, limited in scope, to the full management of their networks. This marked an ambitious and bold move on the part of a relatively modest player in the field of telecommunications. The central element of Prestige Telecom's strategic plan was to create an R&D group that would back up its engineering endeavors and serve as a weapon for market penetration and retention in the sectors of fixed and wireless telephony. The hiring of the first author as an external consultant to the R&D group was geared toward pooling engineering field expertise with academic knowledge in algorithm design, in a cross-fertilization fashion. In short, we collectively were set to do operations research. The main outcome of our university-industry collaboration has been the creation of DOCAF, a frequency allocation computer package for AMPS (analog), TDMA IS-136 (digital AMPS) and GSM networks. DOCAF (bundled with Atoll, a radio frequency planning tool produced by FORSK, a French firm), has so far been sold to operators in Cameroon, Denmark, Egypt, France, Gabon, the Ivory Coast, Madagascar, Spain and Uruguay, and was awarded the 2001 First Prize for Practice by the Canadian Operational Research Society [14]. The Frequency Allocation Problem involves more than a presumably "optimal" allocation of frequencies to a set of cells. Indeed, the problem faced by the operators of cellular phone networks is to maximize their profit while offering the best possible service to their customers. More specifically, they seek to design, build and maintain cost-effective networks that have enough capacity to handle as many calls as possible, and that offer at the same time good voice quality, limited occurrence of dropped calls and limited call rejection. It follows that a host of other problems have to be solved prior to the frequency allocation per se and concurrently with it. Moreover, what the operators truly want is a suite of optimization-based decision-support systems bundled with a graphical user interface with geographical information system (GIS) capabilities, that enables them to visualize the problems and their solutions, and to easily assess various scenarios. Mobile telecommunications networks can carry hundreds of thousands of calls with a limited number of frequencies that typically can be as low as 60 or less in GSM. Such a feat is achieved through solving a sequence of difficult design problems: Partition the territory to be covered into sites; partition each site into cells—typically, one to three; determine the location and transmission power of the Base Transceiver Stations (BTSs); determine the configuration of the corresponding antennas (gain, height, tilt) through which the calls to and from each cell will be received or transmitted. Dimension the air interface, i.e., determine the proper number of transmitters-receivers (TRXs), hence the proper number of frequencies that will be used in each cell so as to satisfy traffic demand and a given quality of service. Allocate to each cell the number of frequencies that is required in some "optimal" way. Dimension the fixed part of the mobile network, i.e., determine the capacity of the links between its various components (Base Transceiver Stations, Base Station Controllers, Main Switch Centers, Points of Interconnect), and the capacity of the link with the so-called Public Switched Telephone Network (PSTN), i.e., the good old fixed telephone network (see Figure 1). Figure 1: View of a cellular network in relation to the PSTN. Ideally, these problems should be solved all together through a single global model. In practice, each one of them is sufficiently large and challenging to justify the above sequential decomposition, coupled with the use of heuristics. Partitioning the territory into cells allows one to use several times each available frequency, thereby increasing the capacity of the network. This does not come cost free, however. Using a same frequency or adjacent frequencies in several cells results in some interference, the level of which depends on many factors such as the distance between the cells, the transmission powers and the antenna gains, together with the antenna heights and tilts, the topography of the land, its natural features (trees, spans of water, e.g.) and its occupancy (high or low concentration of buildings; presence or absence of glass, concrete or steel buildings, etc). Interference affects voice quality; beyond a certain threshold, it will cause a call to be interrupted. Interference, therefore, must be kept in check since its effect is to reduce both quality of service and network capacity. Cell partitioning is a juggling exercise in which one is seeking to address two conflicting issues, covering and capacity. Indeed, consider the two extreme cases that consist of covering a given area with a small number of large cells, or with a large number of small cells. Networks built according to the former configuration cost less in terms of equipment, but have lower capacity and experience a serious problem: they require more transmitter power output and higher antennas. As a consequence, every signal is stronger, goes farther and interferes with signals coming from distant cells. The latter configuration is associated with higher capacity, but also with higher equipment cost and frequent hand-offs or hand-over. At the boundary of a cell, service and control of a given mobile are frequently handed over to a neighboring cell; when this phenomenon occurs too often, it tends to eat up capacity. Thus, cell partitioning and antenna location are not simply additional partitioning and location problems. They must address a host of physical and technical constraints that have to do with wave propagation, and the characteristics and limitations of the equipment being used. Network dimensioning accepts as input the network's topology, its relationships with other cellular networks and with the PSTN, the forecast demand for each ordered pair of origin and destination, and the quality of service, typically expressed as a maximum blocking probability, i.e., the probability of not being able to carry a call to destination. This is an integer nonlinear optimization problem that can be viewed as a special case of fixed hierarchical network dimensioning [8], a difficult teletraffic engineering problem. Actually, a good dimensioning of a cellular network cannot be done without considering it as part of a super-network that encompasses the other cellular and fixed networks to which it is linked [7]. That can be carried out with a dimensioning tool such as CAPLAN, e.g., a software package developed by Prestige Telecom. Air interface dimensioning is also a teletraffic engineering problem in which—given the area covered by each active BTS, a level of quality of service (e.g. 2 percent call blocking rate) and a traffic density map that indicates the amount in Erlang of offered traffic per unit area—one calculates the number of logical circuits needed for carrying the calls. This value in turn translates into a number of TRXs that depends on the technology at hand. In Frequency- and in Time-Division-Multiple-Access networks, two simultaneous calls are carried either by two different frequencies (FDMA) or by two different time-slots of a same frequency (TDMA). AMPS is based on FDMA. In digital systems such as TDMA IS-136 and GSM, each frequency is divided into a number of time-slots so that it can carry several calls. Note that the frequency allocation problem does not apply to the Code-Division-Multiple-Access technology (CDMA) that uses a single, wide-band frequency without time-division to carry all simultaneous calls in which each call is identified with a "code." Frequency allocation has been studied extensively for AMPS and GSM networks by researchers in combinatorial optimization. This is not surprising since FDMA and TDMA, unlike CDMA, lend themselves to a sequential decomposition of the covering vs. capacity global problem, enabling a mathematical definition of frequency allocation that evacuates all teletraffic engineering considerations. As a matter of fact, frequency allocation has been modeled as a graph-coloring problem in which nodes represent TRXs, and the presence of an edge forces one to allocate different "colors," i.e., frequencies, to the corresponding nodes because otherwise, there would be too much co-channel interference taking place there. The available frequencies being contiguous in a given spectrum, choosing two different frequencies is equivalent to enforcing a frequency separation of at least one. This model is a crude approximation that was refined with the consideration of T-coloring [5] (see [1], e.g.). With T-coloring, it is possible to take into account the necessity of maintaining separations of at least two, three, etc. Typically, one wants, for instance, to forbid co-channel and adjacent channel interference, i.e., one seeks to force a separation of at least two within any cell. This model can be further refined by considering a list of forbidden frequencies for each TRX. In these models, one addresses the assignment of several frequencies to a cell by considering individually each TRX of the cell, which greatly increases the size of every instance. Such a degree of detail is not imposed by the real-life problem. This can be contrasted with Frequency Hopping, a feature of GSM networks by which the frequency used by a TRX is allowed to change a great number of times within one second [2]. In the latter case, it is imperative to consider separately each TRX. Three objective functions have often been considered: 1. minimize the number of frequencies used, 2. minimize the frequency span; and 3. minimize the total co-channel and adjacent channel interference. The first two objectives may be useful in the so-called green field scenario, i.e., when planning for a new network. Otherwise, the conditions of the telecommunications license together with the technology at hand determine the number of frequencies and the frequency span. In this case, the third objective function is widely used. Another objective may be to minimize the maximum interference occurring in the cells of the network. This is also useful for Frequency Hopping [2]. As for the data, besides the matrix of separation constraints, the set of locally blocked frequencies and the set of forced conditions, two square matrices indexed by the cells are given, namely the co-channel and the adjacent channel interference matrices. They contain, for each ordered pair of cells, a number that is supposed to measure the interference created, say, in the first cell, by the use in both cells of either an identical frequency or two adjacent frequencies. This also is an approximation of reality. Actually, the signal emitted at a BTS can be measured almost everywhere, taking into account the propagation loss. It follows that for any cell i, one should globally consider the set of all other cells j for which an interference is created at i when i and j use either an identical frequency or adjacent frequencies. This is why, when operating a network, one generally proceeds as follows: Divide the area to be covered into "pixels" of 20 meters by 20 meters. Measure or estimate the power of the signal received at each pixel from each BTS. It is, of course, extremely expensive to measure the signal strengths at every pixel. An alternative is to use a planning tool such as Atoll. The estimation is carried out by using some wave propagation algorithm after calibrating it for the area under study. For each pixel, the "best" signal in terms of strength or quality determines the BTS that will cover it. Every other signal is considered as interfering with the best one. Let C denote the strength of the best signal and let I denote the total strength of all interfering signals. C/I represents the relative strength of the best signal. The higher the value of C/I, the better. One seeks to maximize the total value of C/I or to minimize the relative size of the total area affected by some undesirable level of interference, i.e., the total area for which the value of C/I is lower than a target value. Figure 2: An alternate view of a cellular network. The adjacent and co-channel matrices are obtained after aggregating the information measured or estimated at the pixels of each cell. The net result of this aggregation is to approximate one-to-many relationships with pair-wise relationships. We have described the technical context in which the frequency allocation problem arises. Reviewing this material was motivated by the conviction that the knowledge of the physical workings of this real-life problem—which are too often overlooked—can make all the difference between providing a good or a mediocre solution. As a case in point, in the instance submitted by France Telecom to researchers worldwide ([12]; DOCAF is X11, which means that it obtained the second best result with respect to the main criterion), the strengths of the signals received at each pixel were provided. It was necessary as a first step to build the interference matrices, because it would have been prohibitively costly time-wise and memory-wise to process each pixel individually. But it was equally necessary to correct somehow the distortions created by the aggregation process. Failure to do so may have been the cause of the huge discrepancies observed between the best and the not so good solutions ([10]; see [12]). Problem Definition The frequency allocation problem in GSM (and in TDMA-based networks, in general) can be described as follows. Given a list of cells, the number of TRXs required in each cell, the spectrum of available frequencies, a set of locally blocked frequencies for each cell, a list of forced conditions, a list of co-cell and co-site channel separation requirements and a list of channel separation requirements for "neighboring" cells, and given co-channel and adjacent channel interference matrices between any two cells, allocate the available frequencies to the cells so that (1) each cell receives the required number of (not locally blocked) frequencies; (2) all forced and separation requirements are met; and (3) the sum of the interference occurring between pairs of cells is minimal. ([1] contains a similar definition and a mathematical formulation expressed in terms of the TRXs.) The real problem that GSM and TDMA IS-136 operators must solve is even more complex because the frequencies can be assigned different roles. When k frequencies are allocated to a cell, one of them must carry the transmission control signal on its first time slot. Such a frequency is called Broadcast Control Channel (BCCH) in GSM and Digital Control Channel (DCCH) in TDMA IS-136; the other frequencies, if any, will only carry regular traffic. They are called Traffic Channels (TCHs) in GSM and Digital Traffic Channels (DTCs) in TDMA IS-136. It follows that a frequency used as BCCH/DCCH can carry up to seven/two user communications instead of eight/three for a TCH/DTC. Because the control function is critical, the frequencies that are the least involved in interference will be chosen to carry signaling and control. Some operators address this problem by partitioning the available spectrum so as to keep aside a number of frequencies that will only be used as BCCH/DCCH. In GSM networks, one rarely imposes a separation of more than two in a given cell. In AMPS networks on the other hand, the equipment usually imposes a separation of 17 for the frequencies that are handled by a same antenna. The frequency bands used in AMPS are arranged in columns, and it is customary to allocate the frequencies in one or more blocks, each block being taken from one column. While this procedure may be convenient for manual allocation and for physical implementation, it adds a hard constraint to the problem, a constraint that many operators are unwilling to drop for fear of upsetting the technicians who perform the implementation by tuning the cavities, or simply because they are change-avert. Heuristics DOCAF encompasses two optimization modules, one for AMPS and one for GSM and TDMA IS-136, that are implementations of Tabu Search heuristics. In each case, the overall procedure contains the following three components: an initial solution generator based on DSATUR [3, 4, 1], that provides a good starting solution to the Tabu Search component. the Tabu Search component itself. an adaptive memory engine [9]. A pool of good solutions is maintained; they are combined in a genetic algorithm fashion in order to create (presumably) promising starting solutions for further runs of Tabu Search. Frequency Allocation in Practice As stated at the beginning, frequency allocation is but one among several problems that must be solved by the telecommunications operators. Not surprisingly then, these are not so much interested in individual modules. They are seeking to acquire combinations of software packages that altogether will help them to obtain good global solutions. Three kinds of tools are of particular importance to them: 1. dimensioning (CAPLAN, e.g), 2. automatic frequency planning (DOCAF, e.g.), and 3. radio frequency planning with wave propagation models and GIS-based capabilities for displaying graphically and interactively all the layers of the networks under study (e.g., Atoll). Since it is virtually impossible to be a world leader in all three domains, developers have been well advised to forge alliances. Such an alliance between Prestige Telecom and FORSK has resulted in the integration of DOCAF with Atoll. Figures 3 and 4 represent a fictitious network built on the geographical data of an existing city, a cellular network of which we have redesigned. Atoll has been used in both cases for the propagation study and the graphical display. In Figure 3, the frequency allocation has been carried out by the so-called reuse pattern, a traditional procedure still used by some operators, that does not measure up to current optimization packages. The frequency plan of Figure 4 is the work of DOCAF. Figure 3: Interfered areas - FA based on a 3/9 reuse pattern. Map produced by Atoll. Figure 4: Interfered areas - FA determined by DOCAF. Map produced by Atoll. DOCAF has been thoroughly evaluated by several important cellular network operators, including Mobistar (Belgium) [13] and Bouygues Telecom (France) [11], which provided us with a comprehensive evaluation report. In the former case, it has been compared with AGORA, arguably one of the best frequency allocation packages in the world. In the latter case, it was compared with "the best AFP tools on the market." We attribute the success of this work to the multidisciplinary of our university-industry team, that has enabled us to bridge the gap between the understanding of the problem's physical workings and the modeling requirements, in the true tradition of operations research. References R. Borndörfer, A. Eisenblätter, M. Grötschel, A. Martin, "Frequency Assignment in Cellular Phone Networks," Annals of Operations Research, 1998, pp. 73-93. J.M. Bourjolly, S. Touhami, L. Déjoie, K. Ding, O. Dioume, M. Lominy, "Frequency Hopping in GSM Cellular Networks," to appear in the Proceedings of the 5th INFORMS Conference on Telecommunications, Boca Raton, Fla., March 2000. D. Brelaz, "New methods to color the vertives of a graph," Communication of the ACM, 1979, Vol. 22, pp. 169-174. D. Costa, "On the use of some known methods for T-colorings of graphs," Annals of Operations Research, 1993, Vol. 41, pp. 343-358. M. Cozzens, F.S. Roberts, "T-colorings of graphs and the channel assignment problem," Congressum Numerantium, 1982, Vol. 35, pp. 191-208. M. Dell'Amico, M. Trubian, "Applying Tabu Search to the Job-shop Scheduling Problem," Annals of Operations Research, 1993, Vol. 41, pp. 231-252. O. Dioume, L. Déjoie, J.M. Bourjolly, "Mobile and PSTN Communication Services: Up-Front Integration," 15th International Teletraffic Congress, Washington, D.C., June 1997. O. Dioume, A. Girard, F. Soumis, "Dimensioning Telephone Networks with Budget Constraints," Communication Systems, 1993, Vol. 1, pp. 149-177. Y. Rochat, E. Taillard, "Probabilistic Diversification and Intensification in Local Search for Vehicle Routing," Journal of Heuristics, 1995, pp. 147-167. Alexandre Caminada, private communication, April 3, 2000. Bouygues Telecom, "Bilan des tests menes sur DOCAF." Aug. 31, 1999, Prestige Telecom's internal document. France Telecom, "Benchmarking on Frequency Planning - Results on 31 January 2000," (www.cs.cf.ac.uk/User/Steve.Hurley/benchmark_results3.pdf). Mobistar: "Evaluation de l'outil d'affectation automatique de frequences DOCAF," April 20, 1999, Prestige Telecom's internal document. Canadian Operational Research Society, "CORS Competition on the Practice of OR," (www.cors.ca/handbook/awards/practice.htm). Jean-Marie Bourjolly is an associate professor at Concordia University in Montreal. Leslie Déjoie, Ke Ding, Oumar Dioume and Michel Lominy are researchers at AirTel Communications, Inc., a spin-off partner of Prestige Telecom, Ltd. Ph.D. student Souheyl Touhami contributed to the preparation of the paper. This research was supported by the National Research Council of Canada (Industrial Research Aid Program), by the Natural Sciences and Engineering Research Council and by Mathematics of Information Technology and Complex Systems (MITACS), one of Canada's Networks of Centers of Excellence. Table of Contents OR/MS Today Home Page OR/MS Today copyright © 2002 by the Institute for Operations Research and the Management Sciences. All rights reserved. Lionheart Publishing, Inc. 506 Roswell Rd., Suite 220, Marietta, GA 30060 USA Phone: 770-431-0867 | Fax: 770-432-6969 E-mail: lpi@lionhrtpub.com URL: http://www.lionhrtpub.com Web Site © Copyright 2002 by Lionheart Publishing, Inc. All rights reserved.