SYSTEM PERFORMANCE VARIABLES

We begin by presenting our metrics results in a comparative way, to show that they can give a good insight into the model performance. In Figure 1 we show the four previously defined performance metrics for the scenario with low population density and flat terrain and with low traffic requirements. We can see that the percentage of connected users  increases with the the number of sites. There are additional connected users with relay topology and even more with mesh topology. We can also see that the increase in the number of sites reduces the number of users per base station, i.e., reduces efficiency. The percentage of frame occupancy shows that as the number of sites increases, every base station has a lower number of users connected to it and this causes a lower frame occupancy. With many base stations, the frame occupancy is really low. We can see that a mesh solution has a higher occupancy up to four active sites. This is because it increases the number of connected users but consumes more resources because of multihop links.

 
Figure 1: Results comparison for low density—flat scenario and low traffic requirements.

The equivalent transmission profile clearly shows that a PMP topology has a higher spectrum efficiency than a mesh or relay solution. This is because multihop topologies require more capacity due to multiple hops. In PMP topology this parameter remains almost constant, which means that the addition of new base stations allows the inclusion of more users but does not improve link quality. We analyze that this is caused by the reduction of the transmission power of some base stations due to interference restrictions. The increase of link efficiency with the number of sites for mesh and relay topologies, means that users reduce the number of hops to reach the nearest base station. The similarity between mesh and relay topology means that with many active sites, there are paths with at most two hops for some users. As the number of sites is higher, there is a low use of multihop links.

Automatic and Optimized Cell-Mesh Planning in WiMAX RESULTS

Our goal is to define the best conditions to cover rural remote users by the usage of PMP and multihop topologies. We defined four scenarios with different population density and topographical condition. We also defined three different set of values for traffic requirements classified as low, medium, and high requirements, presented in Table 1. Finally, we included in the results PMP, relay, and mesh topologies.

Table 1: Traffic Parameters for Different Requirements 

Traffic Requirements	Rgranted	Rvoice	Rbe	ρ
Low	20,000	24,000	10,000	0.025 Erl
Medium	60,000	24,000	40,000	0.025 Erl
High	120,000	24,000	80,000	0.050 Erl

We use the following metrics to deeply analyze the performance of the solutions found by the optimization algorithm and compare the different topologies considered.

•  as previously defined.
• The ratio between the number of connected users and the number of used base stations (|C_u|/|B_u|). This is the value  previously defined before normalization.
• Average frame occupancy percentage: This variable determines how much of the frame is occupied on every base station. This variable is important to measure if a multi-point solution can improve a PMP solution.
• Equivalent modulation and coding schema: In WiMAX standard [22], there are several levels of transmission profiles defined, ranging from 1/2 BPSK to 3/4 64QAM. Every transmission profile is defined by the coding factor and the modulation factor. We define a quantity by the product of these two values, equivalent to the amount of bits that are sent within one QAM symbol into an OFDM symbol. The lowest value is 0.5 and the higher value is 4.5. We calculate the average value for all the users connected to every base station. An average value near 4.5 means that the solution has a high spectrum efficiency, equivalent to say that all users have the best link conditions possible.

In Figure 1, we present a solution for the low population density and flat terrain scenario with PMP topology. Dark triangles represent sites location. Each antenna in every site is represented by its radiation pattern with a black line indicating its orientation. The connection from users to base stations is represented by a solid line with the same color of the radiation pattern. Information text near the base station indicates the site index, the frame occupancy percentage, and the base station transmission power. In Figure 2 we present a mesh topology solution for the same terrain shown in Figure 1. Every site includes all the base stations that were used on the PMP solution. The information about each site is the site index and the average frame occupancy percentage of all base stations used. Gray curves represent terrain heights.

 
Figure 1: Example solution for a PMP topology.

 
Figure 2: Example solution for a mesh topology.

In the following we discuss the behavior of each one of the performance metrics with respect to the number of sites. We focus then on the number of users that can connect to the system as a function of traffic requirements and the terrain characteristics for all three topologies. We finally discuss the optimization objective function. We found interesting to split multihop solutions into relay and mesh, because when the mesh solution performs near the relay solution, it means that the relay solution as proposed in study group IEEE 802.16j  could be enough over a full mesh solution.

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.

Advanced Search Algorithm | AUTOMATIC CELL CONFIGURATION

The optimization method described in the previous section is well suited for an initial planning and in cases where the level of completeness or accuracy of input data is limited. For a detailed optimization that takes the full set of input data into account, a search approach is proposed. That is, the space of possible configurations denoted as search space is explored to find the point in the search space that is optimal with respect to a certain criterion. This point is denoted as global optimum. Exhaustive search traverses the complete search space in a systematic manner. As all points in the search space are visited, with exhaustive search it is guaranteed to find the global optimum. The search space is very large for typical applications in network planning. For each site there can easily be several hundreds of possible configurations. Furthermore, configurations of different sites cannot be considered independently, so that the amount of possible network configurations grows expotentially with the number of sites. Hence targeting this area, an exhaustive search is too time-consuming and local search algorithms are commonly used for network optimization purposes.

Local search algorithms start at some point in the search space denoted as initial solution and subsequently move from the present to neighboring solutions, if they fulfill some criterion, i.e., appear to be better or more promising. Local search algorithms cannot guarantee to find the global optimum. The objective of the search algorithm—developed or tailored for a particular problem—is to find a solution that is at least close to the global optimum. Local search algorithms are thus often classified as heuristics.

The basic procedure of local search is independent of the actual search algorithm applied. Starting from the initial solution in each search step, first a search neighborhood is generated. The search neighborhood is a subset of points from the search space that are close to the current solution, i.e., that have some attributes in common with the current solution. The point that is most appropriate with respect to some criterion is selected from the search neighborhood and accepted as new initial solution for the next search step. If no appropriate new solution is found (or some other stop criterion is fulfilled) the search is terminated. The comparison of points from the search space is carried out by means of cost values associated with them. The cost values are generated from a cost function, in the literature often also referred to as objective function. The objective function maps a given point in the search space to a cost value. The cost value can be a scalar but could also be represented by a vector. In the latter case, an appropriate function to compare cost values needs to be defined.

Local search algorithms are very much application specific. However, several search paradigms have been developed in the last three decades. The simplest search paradigm is the descent method. This method always selects the solution from the neighborhood that has lowest cost. If this value is lower than the lowest value in the last search step, the solution is accepted as a new solution, otherwise the algorithm is terminated. The algorithm hence explores the search space by always moving in the direction of the greatest improvement, so that it typically gets trapped in a local minimum. A local minimum is a solution that is optimal with respect to the search neighborhood but which generally is worse than the global optimum. To escape from local minima, among several others, one widely applied approach is to carry out restarts, that is, the local search is restarted from a new solution that is selected from a different area of the search space. The new start solutions are often selected randomly. If restarts are applied, the algorithm strictly speaking is not a local search algorithm anymore.

Another option for escaping from local minima is to accept also the cost deteriorating neighbors under certain conditions. The most prominent local search paradigms that apply this strategy are simulated annealing and Tabu search.

Simulated annealing is based on an analogy with the physical annealing process. In simulated annealing improving points from the neighborhood are always selected when exploring the search neighborhood, nonimproving points are accepted as new solutions with a certain probability. The probability of acceptance is a function of the level of deterioration, but also gradually decreases during the algorithm execution. The reduction of the probability of acceptance is determined by the cooling scheme.

In contrast to the simulated annealing which comprises randomness, classical Tabu search is deterministic. The basic operation is equivalent to the descent method with the difference that the best point from the neighborhood is also accepted if it is worse than the current solution. In this way the search is directed away from local minima. To avoid a move back to already visited solutions, a Tabu list is introduced. The Tabu list typically contains sets of attributes of solutions that have already been visited. If a point from the neighborhood exhibits one of the sets of attributes stored in the Tabu list, the point is only accepted as new solution if its quality, i.e., cost, exceeds a certain aspiration level. The Tabu list is updated, keeping the individual entries only for a number of iterations. The size of the Tabu list is a very important design parameter of the Tabu search, it in particular needs to be chosen large enough to prevent cycling, but a too large list might introduce too many restrictions. Several enhancements to the basic operation of the Tabu search have been introduced most of which modify the handling of the Tabu list. These include intensification and diversification schemes

Optimization Parameters and Targets | AUTOMATIC CELL CONFIGURATION

Optimization Parameters and Targets

The targets of the radio network optimization are mainly twofold. First target is to minimize the interference caused by the individual cells, while a sufficient coverage over the planning area is maintained. This is in general a trade-off and needs to be balanced, e.g., tilting down the antenna causes lower coverage, but also lower interference in neighboring cells and thus a potentially higher network capacity. Second target is the traffic distribution between cells. It is desirable to maintain similar cell loading of neighboring cells to minimize blocking probabilities and to maximize spare capacity for traffic fluctuations and a future traffic evolution.

The most effective parameter in network optimization is the antenna tilt. Antenna tilts need to be set such that the traffic within the “own” cell is served with maximum link gain, but at the same time the interference in neighboring cells is minimized. The possible tilt angles are typically restricted because of technical and civil engineering reasons. Especially in case of collocated sites with multiband antennas there might be strong restrictions on the possible tilt angles to be taken into account during optimization.

The transmitted pilot channel power and the other common channel powers, which are typically coupled by a fixed offset, are also vital parameters of network optimization. It needs to be assured that these channels are received with sufficient quality by all users in the serving cell. At the same time a minimization of the common channel powers yields significant capacity gains: Firstly, additional power becomes available for other (user traffic) channels, and secondly, the interference is reduced. The gains obtained from reducing the pilot power are often underestimated. It is important to note that in a capacity-limited WiMAX network (e.g., in urban areas) the reduction of pilot power levels by a certain factor also reduces the total transmit power of cells and as a consequence the cell loading by up to the same factor.

Optimization of azimuth angles of sectored sites is of great importance in particular in case of antennas with rather small horizontal beam-width (e.g., 65° vs. 90° in case of three-sectored sites). In this case the difference between antenna gains in direction of the main lobe and the half-angle between neighboring sectors is comparatively large, and cells of neighboring sites might need to be adjusted such that maximum coverage is achieved. It is observed that during optimization azimuth changes are in particular introduced to reduce coverage problems. For possible azimuth angles typically even stronger restrictions apply than for the tilt angles.

The antenna height is also often a degree of freedom for the optimization. Higher antennas can provide better coverage, but on the other hand also cause more interference in neighboring cells. Additional important parameters are the antenna type and the number of deployed sectors at a site. Both parameters are closely coupled, as a larger number of sectors also suggest the use of antenna pattern with smaller horizontal beam-width. The choice of sectorization is typically a trade-off between increased network capacity and higher monetary cost.