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 AND CELL PLANNING MODEL

The second problem is to find the set of active base stations, their orientation, and transmission power to achieve the optimum coverage and capacity assignment to users. The problem is separated into two parts.

1 Transmission Towers Construction

We define the concept of Transmission tower as a fixed set of active base stations placed at one active site. One site can have many transmission towers but only one of them can be active. We try to explore different alternatives for the number of antennas, their transmission power, orientation, and radiation pattern. After we build them, the problem reduces to choose one of them from every available active site.

The process begins with a set of candidate sites. We discard candidate sites with very low coverage. Also, if there are two sites with similar coverage, we discard the one with the lowest coverage. To build the transmission towers at one site, we begin placing one omni-directional antenna with the maximum transmission power. If this base station is not saturated, i.e., all covered users can connect to it, then we create several transmission towers with one single antenna and different transmission powers, chosen from a set of discrete values. We use also 120° and 180° sectorized antennas.

On the other case, if the first omni-directional antenna base station is saturated, i.e., not all covered users can connect because of capacity restrictions, then we build a set oftransmission towers composed of several antennas with 120° and 180° sectors. We use all possible combinations of transmission power and sectors to build several options for the site. We solve coverage and capacity assignment by previously described algorithms to find the orientation of each set of active base stations. We finally remove redundanttransmission towers from the set of available ones. We solve this for every site to get a set of transmission towers and a matrix that keeps a record of the users that connect to each one of them. This information is used in the optimization process.

2 Optimization Process

In this process, we try to find the set of active transmission towers to optimize coverage and connect the highest number of users. We fix the number of sites during one execution of the algorithm to find the best solution. After that, we increment the number of sites and run the algorithm once again. At the beginning, we start from an empty solution, then we try to improve it by activating, deactivating, or moving transmission towers. We do this every iteration using a probabilistic model to decide if a new solution is chosen or not over the current one. However, we keep track of the best solution that has been reached so far. The iterative process has two main components:

• Building of a new solution: In this process, we start from the current solution and try to improve it by a randomly chosen modification. Our modifications are based on those presented in Ref. [20]. We can deactivate any active transmission tower and activate any inactive transmission tower. We deactivate an activetransmission tower randomly by assigning a deactivation probability inversely proportional to the number of users connected to it. We activate a new transmission tower randomly by assigning an activation probability proportional to the number of uncovered users that could connect to it. A new solution is analyzed for a feasible channel assignment by trying several combinations to reduce interference. We fix the number of available channels. We finally use the channel combination that has the lowest interference level, represented by the highest number of connected users.
• Optimization process: This algorithm iterates, comparing the new candidate solution and the current solution. This is the core process for simulated annealing, in which a new candidate solution replaces the current solution according to the improvement and the temperature of the system. If the candidate solution is better than the current solution, it is accepted. Otherwise, it has an acceptance probability that depends on how bad is the new solution with respect to the current solution and the temperature of the system. This process keeps track of the current solution and the best solution ever found.

The metric used to decide the performance of a solution is the percentage of users that could connect to any base station. It means that a better solution has more connected users than a previous one. We must recall, that other optimization criteria are included in the inner process.

• Interference is reduced during the building of a candidate solution by choosing the lowest interference channel assignment, i.e., each new candidate solution tries to increase the number of connected users with the minimal interference.
• For the iteration process we add and remove base transmission towers to the new candidate solution. If we have two solutions with similar number of connected users, we choose the one with the lowest number of base stations. This way we reduce the cost related to the number of base stations.
• The QoS guarantees are included in the User-Base station assignment model, where we try to connect users to base stations according to their spectrum efficiency. Also, in the Capacity assignment model, if we connect a user to a base station, we guarantee that the requirements are satisfied.

PROBLEM DESCRIPTION | Automatic and Optimized Cell-Mesh Planning in WiMAX

We look for the optimum conditions required by a fixed broadband wireless access system to cover remote rural users. We extend cellular automatic cell planning models to build an automatic cell planning tool. Our goal is to design a system to provide access to remote rural users under realistic conditions considering data networks. And also to find out how multihop topologies can improve over PMP. We describe these issues in the following.

1 SCENARIO DESCRIPTION

We suppose a set of potential users, which are placed on real villages and country houses. Users are not necessarily uniformly distributed. We suppose that all the users have the same traffic requirements, they are fixed and have an external energy source. Every region corresponds to a real place in Colombia.

• High population density, flat terrain: This scenario represents a city with uniformly distributed users, with shadowing caused by surrounding obstacles. One base station covers many users and usually operates saturated. There are also usually several base stations on the same site.
• Medium population density, medium mountainous rural region: This scenario represents a typical rural region, where some of the users are uniformly distributed and some of them are placed on small towns or near roads or trails. We suppose that some of those users cannot be easily covered because of nearby obstacles.
• Medium population density, mountainous rural region: We suppose a user distribution similar to the previous scenario. We suppose the existence of high mountains and rivers that cause deep canyons. There are several users with difficult coverage conditions, i.e., there are no privileged places that can cover a high percentage of the region.
• Low population density, flat terrain: We suppose users widely separated from others. This is common in regions dedicated to agriculture, pasture lands, and forestry. In this case the main problem is caused by the long distance links. We also suppose some places with higher population concentration over the region average such as small villages.

2 DATA MODELS

Data models differ from voice systems in many ways. There are different QoS requirements, they are based on packet multiplexing and there are different transmission schemas that depend on link quality. QoS requirements for data networks include several criteria such as delay, delay variation, and guaranteed data rates. Base stations make use of statistical multiplexing to increase system capacity. An analysis of different transmission flows and the resources assignment problem. The base stations perform a process known as packet scheduling to assign transmission opportunities to packets. Some packets can have priority over others, to allow transmission of more urgent packets. Schedulers and multiplexing models for data traffic are difficult to use in the design process. Data networks like WiFi and WiMAX support AMC. As users have different spectrum efficiency values, they might require different number of slots on transmission frames to achieve the same data rate.

3 DIFFERENT TOPOLOGIES TO SOLVE THE PROBLEM: PMP, MESH, RELAY

In PMP, a user connects to a single base station using a direct link. It chooses which base station to connect to from a set of available base stations, depending on link quality and available capacity. In multihop networks, information can go through several links until it reaches the base station. Packets transmitted through multiple hops have higher delay and require more capacity, i.e., multihop topologies extend coverage at the expense of more capacity consumption. Operation of multihop networks makes use of spatial reuse, controlled by a scheduler. Two different links on the same channel can transmit simultaneously if they do not interfere with each other. Our assumption is that there is only one active link among all links belonging to paths that end on the same base station, but links of users connected to different base stations can be active simultaneously even though they use the same channel.

In multihop topologies, users must decide not only which base station to connect to, but also the path that the packets should follow. The amount of resources required at every hop is not the same, as different links can have different modulation and coding schema. In our case, a certain node chooses the route that requires the lowest amount of resources. We limit our problem to routes up to two hops in relay topologies and up to five hops in mesh networks. A larger number of hops would be prohibitive in terms of delay and resources consumption.

AUTOMATIC CELL PLANNING

Wireless design has a high complexity because of the random characteristics and the shared nature of wireless medium. A cell planning example based on WiMAX standard, even though it is not based on automatic cell-based planning. A complete synthesis of automatic cell planning process is presented. The model uses a multiobjective function, built by a weighted sum of functions, each one representing signal coverage, capacity, system growth capabilities, and cost. The decision variables are channel assignment, sites location, and transmission power. Because of the nonlinear characteristics of this model, author uses genetic algorithms to solve it.

There is a general description of the optimization problem related to wireless network design. It presents a simplified model for global system for mobile communications (GSM) cell planning based on the activation or deactivation of a set of candidate base stations. There are other models based on multiobjective functions. Authors solve the problem by iteratively changing the transmission power used by base stations to guarantee signal reception and interference reduction. They use heuristic techniques and artificial intelligence algorithms in the solution process. Automatic cell planning based on artificial intelligence algorithms. Makes a comparison among different techniques, showing a better performance of tabu search over the other techniques. The variation of the height of antennas and the transmission power by using genetic algorithms, but they do not consider capacity criteria. Particle swarm optimization is used with an optimization criteria similar to that.

Two heuristic techniques to solve high complexity nonlinear optimization problems are tabu search and simulated annealing . Use tabu search to solve an integer linear programming problem. A design process which is similar to ours. It uses simulated annealing to choose active base stations from a set of candidate base stations. A similar problem is solved using simulated annealing too.

Previous references are oriented to cellular networks to provide voice services. WiMAX  networks support different adaptive modulation and coding (AMC) schemas according to link quality. It also defines different types of connections ranging from a circuit-like access to a completely random access. In WiFi networks, there are different link conditions as in WiMAX, but there are not different types of flows. Most of the references for the design of WiFi networks, use the position of access points, their transmission power, and the channel assignment as the decision variables.There is a simple but illustrative description of the problems involved in wireless LAN design. A genetic algorithm to solve channel assignment in Wireless LAN Networks.The algorithm modifies transmission power of fixed access points to react to changes in user traffic requirements. The model described uses a heuristic search model to provide coverage and a minimum data rate at test points. Solve the joint problem of access points location and channel assignment.There is a good description of Wireless LAN Network planning. They use a penalty function to avoid placing access points near each other, to increase the probability of a posterior feasible channel assignment solution. The objective function is a weighted sum of a coverage variable, an interference mitigation variable, and a QoS variable. Authors use tabu search to solve the problem.

Consider the problem of locating relay nodes to improve access point covered area. The decision variables are user nodes and relay nodes location. PMP and multihop topologies can be mixed, where an IEEE 802.16 wireless mesh network interconnects a cell-based IEEE 802.11 access network. In more dynamic scenarios, the design process must prepare a feasible scenario for operation. Discuss several issues for channel allocation and transmission scheduling and a connection admission control and a transmission power control for WiMAX networks is presented.

SITE DEPLOYMENT AND CONFIGURATION EXPERIMENTAL RESULTS

We start with an experiment on site selection. There are 55 candidate sites as shown in the left of Figure 1. Each site has three cells.Without loss of generality, it can be assumed that all the cells have the same configuration as given in Table 1. The configuration of subscriber station is given in Table 2.

 
Figure 1: Site deployment before and after optimization.

Table 1: Cell Configuration 

Parameter	Value
TX power (dBm)	40
Operating frequency	2350
Bandwidth (MHz)	10
Antenna gain (dBi)	18
Antenna 3 dB angle	65°
Antenna height (m)	40
Receiver sensitivity (dBm)	−96
Noise figure (dB)	4

Table 2: Configuration of Subscriber Station 

Parameter	Value
TX power (dBm)	23
Antenna gain (dBi)	0
Antenna height (m)	1.5
Receiver sensitivity (dBm)	−100
Noise figure (dB)	7

Inhomogeneous traffic distribution is assumed. Furthermore, we assume that all the candidate sites have equal cost in terms of CAPEX and OPEX. The target is to cover 95 percent of the planning area and 98 percent of the predicted traffic.

The site selection method is applied in this experiment. The obtained result is displayed in the right hand side of Figure 1, which consists of 19 sites (57 cells). This design is (locally) optimal in the sense that one cannot remove a site without violating the coverage constraint, one cannot increase coverage by replacing a site by another site, and one cannot replace two sites by another site without violating the coverage constraint. This experiment shows that significant reduction of deployment cost can be achieved by using the site selection technology.

In the next step, this design with 19 sites (57 cells) is further optimized by applying the advanced search algorithm. The optimization is carried out by changing cell parameters including antenna tilt, azimuth, and TX power to improve the network performance. A main performance measure is SINR. Figure 2 shows the SINR CDF (Cumulative Density Function) of different optimization scenarios.

 
Figure 2 SINR CDF of different designs.