The site selection targets at optimizing mobile radio networks. It provides flexible methods to modify the configuration of a network in such away that key performance measures are optimized and pivotal performance targets are met.
The working engine behind the site selection is a fast construction and solution of downlink or uplink cell equations for a given network configuration from which most performance measures can be deduced. Based on an analysis of the “permitted configurations,” a preprocessing tree is constructed which contains all partial coefficients of the cell equations which might be relevant for the construction of the downlink/uplink/combined cell equations of an arbitrary permitted network configuration. This preprocessing tree then allows for an efficient accumulation of the coefficients of the equation system which in turn yields a fast calculation of the cell transmit/interference powers/activities from which most performance measures can be deduced. One can observe how many configurations are evaluated by looking at the number of evaluations in the status messages (which are issued about once in a second) when the algorithm is running after preprocessing.
Based on this fast evaluation, an optimization of the network is performed by evaluating all neighboring configurations of the current configuration and moving to the best of them if this improves the current network configuration, where the neighboring configuration deviates from the current configuration with short distance in the searching space. As long as an improvement can be obtained this optimization step is iterated. When no improvement can be found the last configuration is stored as the end design. On top of this basic procedure (construct preprocessing tree—perform descent to local minimum), there is the possibility for a repetition (since when many sites are switched off the coefficients in the preprocessing tree might become more and more irrelevant hence yield too conservative cell equations) and for a division of large problems into smaller ones, where one part of the network is optimized after another in a circular way.
A key role in the simple local descent iteration is played by the comparison operator between configurations. Here the algorithm allows choosing the relevant performance measures/constraints by assigning priorities to them. For example, one often assigns the monetary cost the highest priority and the coverage constraint the second highest (nonzero) priority.
The site selection can be used for optimizing cell parameters and selecting sites/cells. It can start from given configurations or empty/full networks. It can look through neighborhoods with selectable depths and iterate through these neighborhoods with a deterministic steepest or gradient descent, or a greedy random descent. However, this flexibility is at the price of a more complex user interaction. Through a large number of parameters the user has to tell the program what kind of optimization is intended. In addition, in large optimization problems, the preprocessing tree requires a huge amount of computer memory and if a large number of partial interferer coefficients are stored the evaluation can become slow. Partial coefficients which cannot be stored are accumulated in a so-called remainder coefficient. This remainder coefficient can accumulate a large number of small interferer and then makes sure that these interferers are not neglected in the cell equations. This saves computation time and computer memory, but might yield overconservative cell transmit powers/channel activities, when the number of stored coefficients becomes too small or when the interferer which belong to the stored coefficients are not active (e.g., is switched off). In these cases one might have to recalculate the preprocessing tree or allow for a larger number of coefficients within the nodes of the tree. Or one could divide a large problem into smaller ones which also reduces the preprocessing tree.
1 Candidate Sites and Permitted Configurations
The site selection algorithm starts from a description of the permitted network configurations. Such descriptions consist of a set of potential cells (configured cells which might appear in a network design) and subsets of these cells which we call selection sets and choice sets.
The meaning of a selection set is that all potential cells in this set have to appear together in a permitted network configuration or none of them. In a site selection, problem one can think of a selection set as the set of cells which belong to a site: One has to select all of them or none of them. Since selection sets can consist of a single cell, one can also define “cell selection” problems, where individual cells are selected by putting each potential cell into an individual selection set.
The meaning of a choice set is that exactly one of the potential cells in this set has to appear in a permitted network configuration. In a tilt choice problem such a set would consist of all potential cells which model the same cell but with different tilt settings. Defining such a choice set means to tell the optimization kit that it should choose exactly one of these cells for a solution design. Through a choice set which contains only one potential cell one can tell the program that this cell must appear in a solution design.
2 Optimization Algorithm
Given this definition of permitted configurations and the results of the preprocessing, the algorithm can walk through the permitted configurations and try to improve the performance measures of interest during this walk. The permitted configurations are the possible search choices for the optimization algorithm. The user can choose between several different manners of walking towards an optimized configuration by either “local steepest descent,” “local gradient descent,” “random greedy descent,” or “local immediate descent.”
The local steepest descent method evaluates all neighbor network configurations and then replaces the current with the best one found, where the comparison checks the selected performance measures exactly according to their priority.
The local gradient descent method evaluates all neighbor network configurations and then replaces the current one with the best one, where the comparison is based on gradients instead of the absolute values of the performance measures.
The random greedy descent method chooses randomly one new configuration in the neighborhood of the current one and moves to it if it performs better than the old one.
The local immediate descent is an exotic procedure where improvements are immediately accepted and the search continues from the improved configuration. This can speed up the algorithm, but at the cost of perhaps not giving as good results as the above more thorough search methods.
In all cases the walk moves from the current configuration to a configuration within a certain neighborhood of the current one. The neighborhood is defined as all configurations which can be reached by a given number of permitted elementary steps. An elementary step is either changing a given permitted configuration by switching one selection set on or off (adding its cells to the configuration or removing them) or modifying one cell in a choice set (replacing it by another one of the same choice set).
However, increasing the search depth to more than one, usually dramatically increases the computation time because a large number of configurations might have to be considered before accepting a move. This increase can be controlled through algorithm parameter.
3 Performance Evaluation and Comparison
There are two groups of performance measures: Ordinary performance measures and performance constraints, which additionally have a target value which should be reached. The ordinary performance measures are
- ActiveCells: The number of active cells in the evaluated network configuration. (Can be used instead of TotalFirstYearCost if detailed costs are irrelevant.) Small values are better than large ones.
- ActiveSites: The number of active sites. (Can be used instead of TotalFirstYearCost if the detailed costs of the base stations are irrelevant.) Small values are better than large ones.
- MaxOtherCoefficient: The maximum of the nondiagonal coefficients in the coupling matrix. Small values are better than large ones.
- MaxOwnCoefficient: The maximum diagonal coefficient in the coupling matrix. Small values are better than large ones.
- MaxSiteCostPerAccess: The maximum first year cost of one BS location (including hardware) divided by its sum of area and traffic access coverage in percent. Small values are better than large ones.
- MaxUserLoadInPercent: The maximum user load of a cell in the network. Small values better than large ones. If this measure has high priority, the optimization seeks for a configuration in which the maximum user load of a cell is as small as possible.
- OverloadedCells: The number of overloaded cells. Small values are better than large ones.
- TotalFirstYearCost: The most important (nontechnical) performance measure in site selection, namely the total first year cost of a given network configuration. Small values are better than large ones.
The performance constraints are
- AreaCoverageInPercent: The percentage of the area which can be served (i.e., considered pixels which have a large enough receive signal strength from at least one of the active cells) by the network configuration. Its target value is the area coverage defined in the underlying optimization profile. Large values are better than small ones.
- AccessCoverageInPercent: The number of users on the served area of a configuration as a percentage of the number of users in the total considered area. The target value is the access coverage from the underlying optimization profile. Large values are better than small ones.
- MinCoverageGapInPercent: Here one looks at the differences of the area coverage in percent and its target value and the traffic coverage in percent and its target value. The smaller one of these two differences is the MinCoverageGapInPercent. Large values are better than small ones. The target value of this constraint is 0.
- TrafficCoverageInPercent: After solving the cell equations one can assess the number of customers which can be served by the network. The target value is the traffic coverage from the underlying optimization profile. Large values are better than small ones.
Only performance measures are calculated and displayed during the optimization for which the priority is strictly positive. The one with the largest positive value has highest priority, the one with the lowest positive value the lowest priority. The positive priorities should be different.
When two evaluations of network configurations are compared, first the number of violations (i.e., number of performance constraints, where the target is not met) is compared. The configuration with fewer violations is better than the other one.
Next, if both configurations have the same nonzero number of violations, the violation with the highest priority is considered. The configuration where the corresponding performance measure has a better value is considered as better than the other one. If both values agree, the performance measure with a violation and next highest priority is considered, and so on.
If there are no violations or the performance measures of all violated constraints agree, the performance measure with the highest priority is considered: The configuration which has the better value of this performance measure is considered to be better than the other one. If both values agree one looks at the performance measure with the second highest priority, and so on.
Since the steepest descent algorithm accepts only “better” permitted configurations, this evaluation first tries to reach the performance targets and then to optimize the high priority measures.
If the optimization method is set to local gradient descent, the decision whether a neighbor of the current configuration is better than another neighbor of the current configuration is slightly more complex: instead of the absolute values one considers gradients with respect to the current configuration.
