Optimization Process | AUTOMATIC CELL CONFIGURATION

The basic structure of the local search algorithm that has been developed for an optimization of WiMAX networks is depicted in Figure 1.

 
Figure 1: Local search algorithm for WiMAX network optimization.

The algorithm comprises the basic elements of a local search method that have been presented in the previous section. The local search starts from an initial solution, which can for example be the current configuration of the network to be optimized, a manually planned solution, or a solution suggested by the fast heuristics presented in the previous section.

At the beginning of each search step, the search neighborhood is generated. At first a cluster of cells is selected for which parameter changes are considered. Based on the selected cells the search neighborhood is generated and explored to yield a new solution.

The quality of a certain solution is assessed by a performance analysis. The choice of the method depends on the particular application and is a trade-off between accuracy and speed of the optimization process. From the results of the performance analysis, a cost value is generated by means of a cost function. The cost function is basically a linear combination of the evaluated quantities. In addition, penalty components are added if certain thresholds are exceeded for any of the different cost function components (e.g., coverage probability below some design target). The search process can be guided by appropriately setting weights for the different cost function components.

As a search paradigm either a descend method or a Tabu search can be applied. The Tabu list is maintained independent of the selected search paradigm. The search paradigm only influences the way in which the search is terminated. In case of the descend method, the search process is terminated if no improvement could be found. For the Tabu search, nonimproving moves are accepted to escape from local minima. The Tabu search is terminated once no improving moves were found for a certain number of search steps.

The performance of the local search method strongly depends on the applied performance evaluation. The choice between the methods is a trade-off between accuracy and running time. The basic static method is the fastest but as was shown has some weaknesses in terms of accuracy of results. The presented statistical methods significantly outperform the latter method in accuracy of results but even if implemented efficiently are of higher computational complexity, especially if the experimental analysis is applied for evaluating quantities per pixel. The local search optimization presented in this section can be extended to yield a hybrid method which makes use of two methods for performance evaluation. The exploration of the neighborhood is split into two parts. In a first step, the neighborhood is explored by the use of a simple and fast basic performance evaluation method. As a result a list of candidate solution is generated. The list is sorted with respect to cost values. The next candidate solution is selected from this list using a more accurate but also more time consuming advanced performance evaluation. Either the first improving solution from the list or the best solution from a subset of most promising solutions (“short list”) is selected.