Planning Tools Help Designers Optimize Cellular Networks
The ability of new software to integrate siting, hardware configuration, and frequency planning provides substantial improvements in the quality of service offered by cellular networks.
By: Sebastian Ceria, Dash Optimization; Carlo Mannino and Antonio Sassano, University of Rome "La Sapienza"
Contents
Assessing quality
The problem
A new optimization algorithm
Relaxed requirements
Antenna siting
Evaluating the best network
A more complex approach
Fewer antennas=better quality
Optimization techniques have been applied very successfully for many years for solving a variety of problems arising in the design of telecommunication networks. An optimized design usually results in substantial savings in the cost of equipment, and in an improvement in the reliability of the overall network.
In the last few years researchers have begun exploring some of the most difficult optimization problems arising in the design of cellular networks, namely, antenna siting and frequency assignment. In order to tackle these problems, researchers have started developing new optimization tools specifically targeted at wireless network designs. By using these tools, engineer can achieve substantial improvements in network performance.
Assessing quality
A widely accepted criterion for assessing the quality of the service offered by a cellular network in mobile telephony considers two important factors:
- The area of coverage, i.e. the percentage of the territory which is reached by the signal stronger than a minimum pre-determined field.
- The signal/noise ratios (SNRs) in a set of test points in this area. The fields reaching a test point from different base stations can (and must) overlap and since only one of the base stations will be serve the test point, the other fields will interfere (noise).
The first factor guarantees that the cellular provider can serve any customer in the territory, while the second one measures interference from different antennas at the points in the service area. These criteria are clearly dependent on the configurations of the antennas; the geographical location, height, and beam direction of the antenna; radiation diagrams, power of emission; and the broadcasting frequencies of each antenna in the network.
Whenever the geographical locations and radio-electrical parameters of the antennas are fixed in advance, the SNR depends only on the frequencies assigned to the network. In general, the level of the ratio SA/NB, where SA is the signal emitted by antenna A and NB is the noise generated by antenna B, increases with the distance between the frequencies assigned to antennas A and B.
This fact implies that, in principle, it should be always possible to obtain high quality levels of the service by assigning suitable frequencies to the antennas of the network. Unfortunately, there are only a limited number of frequencies made available to each cellular provider, and a straightforward allocation of such frequencies results in poor service levels.
The problem
The frequency assignment problem (FAP) is the optimization challenge of efficiently assigning a limited number of radio frequencies to the antennas of a cellular network in such a way that quality requirements are satisfied. FAP is a generalization of the famous graph-coloring problem, one of the most difficult problems in "Combinatorial Optimization," the area of operations research that deals with these discrete decision problems.
FAP belongs to the class of most notoriously difficult optimization problems, and there is little hope that we could ever develop efficient algorithms for solving these problems in general. Since the number of available frequencies is generally equally distributed among all competitors, the ability of finding optimized solutions with state-of-the-art algorithms provides the cellular provider with a fundamental competitive advantage: better quality of service.
As an example, consider the network in figure 1A, where the antennas, named from A to E, are in correspondence with the vertices of the pentagon. In order to obtain satisfactory SNRs, we can suppose that antennas corresponding to adjacent vertices must use different broadcasting frequencies. Suppose we need to assign two distinct frequencies to each antenna, to meet traffic demand. Finally, suppose the set of available frequencies is the set {1,2,3,4,5}.
In regards to figure 1A, we can start by assigning to antenna A frequency 1 and 2 and then frequency 3 and 4 to antenna B. Now, we can re-use in antenna C the frequencies assigned to A, namely frequency 1 and 2. We can also re-use in antenna D the frequencies assigned to antenna B, namely 3 and 4. But now, since antenna E is adjacent both to D and A, frequencies 1,2,3 and 4 are not available. So, we have to assign 5 and 6 as the frequencies to E.
An assignment that makes use only of five frequencies is shown in figure 1B. This example shows that, even in the very simple network of Figure 1, a non-optimal assignment can lead to a waste in the frequency resource, making it impossible to satisfy the quality requirements by using the available frequencies.
A new optimization algorithm
As an engineer can easily see from the above example, optimization is critical to avoid wasting frequency resources in a wireless network. A new, called adaptive core search (ACS), has been developed to help engineers perform this optimization.
ACS uses an intelligent search technique to find optimum solutions to FAP. It is also able to identify hard subnetworks, such as clusters of antennas and geographical areas, where it is most difficult to ensure the high quality service required by the provider (cores).
The identification of hard subnetworks is a critical ingredient of ACS. In fact, ACS is based on the recursive solution of a suitable sequence of hard subnetworks. Such solutions are then extended to the remaining part of the network.
The ability of ACS to identify hard subnetworks arises from an internal learning mechanism. During the search in the solution space, ACS collects information about the hardness of each single transmitter. This information is then exploited to extract the hardest subset of transmitters.1
Relaxed requirements
In most areas characterized by an intense traffic demand, it is generally impossible to satisfy all quality requirements with the given number of frequencies. In this case, it becomes critical to decide which requirements can be "relaxed." In this context, ACS can be used to identify hard subnetworks, and use those networks to identify in turn the constraints that must be relaxed.
Once the critical subnetworks have been extracted, however, engineers still need to decide which quality requirements have to be relaxed. Suppose, for example, that A is a critical cell within the critical subnetwork, with a traffic demand equal to 10. This means that we have to assign 10 distinct frequencies to cell A. Now, we can decide that five of these frequencies must be totally protected from interference, while the remaining five can be only partially protected. That is, we can subdivide the required frequencies into different priority classes, each corresponding to a specific quality level. Quality requirements will be relaxed according to priority levels, beginning with the lowest.
Antenna siting
Until now, we have considered geographical and radio-electrical parameters of the antennas as fixed in advance. On the other hand, effectively choosing the correct locations of the antennas among a large number of candidate sites, selecting appropriate radiation diagrams and emission powers can substantially modify the interference pattern of the network. This, in turn, affects the number of frequencies needed to reach a desired service level.
Once again, the number of potential hardware and geographical configurations can be enormous (up to 10 to the power of 4000 for average sized networks). Therefore, an engineer needs efficient tools to identify and evaluate the best possible network.
Siting is defined as the optimization problem of selecting the best hardware and geographical configurations for the base stations of a cellular network, eventually with budget constraints. Additional constraints are related to areas overlapping for hand-over and local connectivity.
In order to solve the siting problem, an engineer can use two different approaches, mainly depending on the size of the network. In the first approach, the problem is formulated as a mixed-integer programming model and then solved by commercial packages (such as Dash Technology' Xpress-MP).
A second approach has been developed for larger networks. In these networks, an effective global analytical search algorithm has been developed. A more sophisticated approach consists of solving a simplified integer model, which provides the tabu search with a good initial solution to be improved.
Evaluating the best network
So, which is the best possible network for a cellular provider? Since our objective is to maximize the quality of the service, an engineer should find a network configuration that efficiently sites antennas and then allocates frequencies in a manner that is consistent with the desired quality of service. This means that the "quality" of the network can be evaluated only after a frequency plan has been devised.
Indeed, siting and frequency assignment, represent two aspects of a single optimization problem. In principle, the two problems should be solved simultaneously. However, the sizes of the instances involved make it unrealistic to attempt the optimal solution of the unified model.
The standard optimization approach consists of first solving the siting problem by optimizing a suitable objective function, related to the cost of placing the antennas, and then the network generated at this stage is input to the frequency planner (Figure 2).
The major drawback of the scheme detailed in figure 2 is that the two modules do not communicate. Once the siting module has dimensioned the network, the control is definitely passed to the planner.
A more complex approach
A more sophisticated optimization approach should take into account the difficulties encountered during the planning phase. In particular, optimization tools employing the ACS algorithm are able to identify hard subnetworks. These subnetworks can then be input to the siting module to be processed again.
It is in fact very likely that local changes in the hardware configuration of the antennas in the subnetwork can simplify the frequency assignment, allowing reaching satisfactory service levels by using a reduced number of frequencies (Figure 3).
Fewer antennas=better quality
The unified optimization approach has been tested in several Italian radio broadcasting networks. The case of the major Italian radio network is very interesting. The original network consists of 857 transmitters, today using 94 different frequencies belonging to the domain {1,…,204}, and serving 94% of the Italian population.
By optimizing over the original network with 857 transmitters, the best assignment is able to serve only 85% of the population. This situation is described in figure 4 where the green color denotes good quality, the yellow just below the threshold, and the red insufficient quality (yellow and red areas correspond to relaxed quality requirements).
By allowing changes in the radio-electrical parameters of the antennas, switching off some of the transmitters (which is equivalent to reduce their power to zero), and applying our siting optimization tool, we were able to find a solution with only 501 active transmitters, which serves 92% of the population (Figure 5).
This fact shows that a drastic reduction in the number of active transmitters can lead to a consistent increase of the quality of the service. In addition, by using only 109 transmitters, our integrated approach was able to find a solution serving 88% of the population.
The mobile side
Similar results have been obtained by applying our approach to mobile telephony networks. In particular, by solving large instances provided by the two major Italian operators we were able to i) reduce the number of frequencies required to ensure the original service level or ii) consistently increase the quality of the offered service. The currently implemented solutions were obtained by a commercially available code.
Reference:
1. C. Mannino and A. Sassano. A enumerative algorithm for the frequency assignment problem, to appear in Discrete Applied Mathematics.
About the Authors:
Sebastian Ceria, president, Dash Optimization; Carlo Mannino, assistant professor, University of Rome "La Sapienza"; Antonio Sassano, Professor, University of Rome "La Sapienza"; Dash Opimization, 115 River Road, Edgewater, NJ 07020. Tel: 201-313-5297, Fax: 201-313-5299.