OPTIMIZATION IN WIRELESS NETWORK DESIGN

A standard model, suitable for planning purposes, identifies a wireless network with a set of transmitting and receiving antennas scattered over a territory. Such antennas are characterized by a position (geographical coordinates and elevation) and by a number of radio-electrical parameters. The network design process consists in establishing locations and suitable radio-electrical parameters of the antennas. The resulting network is evaluated by means of two basic performance indicators: (1) network coverage, that is the quality of the wanted signals perceived in the target region and (2) network capacity, that is the ability of the network to meet traffic demand. On the basis of quality requirements and projected demand patterns, suitable target thresholds are established for both indicators. In principle, coverage and capacity targets should be pursued simultaneously, as they both depend on the network configuration. However, to handle large real-life instances, conventional network planning resorts to a natural decomposition approach, which consists in performing coverage and capacity planning at different stages. In particular, the network is designed by first placing and configuring the antennas to ensure the coverage of a target area, and then by assigning a suitable number of frequencies to meet (projected) capacity requirements. The final outcome can be simulated and evaluated by an expert, and the whole process can be repeated until a satisfactory result is obtained (Figure 1). Future change in demand patterns can be met by increasing sectorization (i.e., mounting additional antennas in a same site), by selecting new sites, and by assigning additional transmission frequencies).

 
Figure 1: Phases of the conventional planning approach.

The network planning process requires an adequate representation of the territory. In the past years, the standard approach was to subdivide the territory into equally sized hexagons and basic propagation laws were implemented to calculate field strengths. By straightforward analytical computations, these simplified models could provide the (theoretical) position of the antennas and their transmission frequencies. Unfortunately, the approximations introduced by this approach were in most cases unacceptable for practical planning, as the model does not take into account several fundamental factors (e.g., orography of target territories, equipment configurations, actual availability of frequencies and of geographical sites to accommodate antennas, etc.). Furthermore, the extraordinary increase of wireless communication quickly resulted in extremely large networks and congested frequency spectrum, and asked for a better exploitation of the available band. It was soon apparent that effective automatic design algorithms were necessary to handle large instances of complex planning problems, and to improve the exploitation of the scarce radio resources. These algorithms were provided by mathematical optimization. Indeed, already in the early 1980s, it was recognized that the frequency assignment performed at the second stage of the planning process is equivalent to the Graph Coloring Problem (or to its generalizations). The graph coloring problem consists in assigning a color (= frequency) to each vertex (= antenna) of a graph so that adjacent vertices receive different colors and the number of colors is minimum. The graph G = (V, E) associated with the frequency assignments of a wireless network is called interference graph, since edge uv  E represents interference between nodes u  V and v  V and implies that u and v cannot be assigned the same frequency. The graph coloring problem is one of the most known and well studied topics in combinatorial optimization. A remarkable number of exact and heuristic algorithms have been proposed over the years to obtain optimal or suboptimal colorings. Some of these methods were immediately at hand to solve the frequency assignment problem.

The development of mathematical optimization methods triggered the introduction of more accurate representations of the target territories. In particular, also inspired by standard Quality-of-Service (QoS) evaluation methodologies, the coarse hexagonal cells were replaced with (the union of) more handy geometrical entities, namely the demand nodes introduced by Tutschku, and with the now universally adopted testpoints (TP). In the TP model, a grid of approximately squared cells is overlapped to the target area. Antennas are supposed to be located in the center of testpoints: all information about customers and QoS in a TP, such as traffic demand and received signals quality, are aggregated into single coefficients. The TP model allows for smarter representations of the territory, of the actual antennas position, of the signal strengths, and of the demand distributions. This in turn permits a better evaluation of the QoS and, most important, makes it possible to construct more realistic interference graphs, thus leading to improved frequency assignments. Indeed, by means of effective coloring algorithms, it was possible to improve the design of large real-life mobile networks  and also of analogue and digital broadcasting networks.

Finally, basing on the TP model, it was also possible to develop accurate models and effective optimization algorithms to accomplish the first stage of the planning process, namely the coverage phase, to establish suitable positions and radio-electrical parameters for the antennas of a wireless network.

In recent years, thanks to the development of more effective optimization techniques and to the increase of computational power, a number of models integrating coverage and capacity planning have been developed and applied to the design of global system for mobile (GSM) , universal mobile telecommunication system (UMTS), Analog and Digital Video Broadcasting  networks.

SIMULATION RESULTS | Capacity Planning and Design

The average-based design models lead us to much smaller estimates of required capacity. Therefore, they run the risk of not being able to guarantee acceptable performance for many real-time applications such as voice or video where jitter must also be taken into account. We currently do not have design models that can take jitter into account so we need to evaluate whether the jitter remains acceptable in a system designed with an average delay method.

In this section, we present simulation results to study the delays encountered by the individual voice and video sources under various provisioning scenarios and compare them with the required delays for voice and video, respectively. We used ns-2 to conduct simulations. In this section, we only consider AF subclasses where multiple sources send packets to each subclass, and packets of each subclass are served in the order of their arrival while sharing bandwidth between the subclasses using PDD scheduling. The simulation model for AF class is shown in Figure 1. We simulate a voice source using a two state on–off model where it generates packets with a deterministic inter-arrival time of 15 ms in the on-state. On-periods are exponential with rate 2.5 and off-periods are also exponential with a rate 1.67. Each packet is of size 120 bytes. The video source is modeled using deterministic batch arrivals with batch inter-arrival time of 33 ms. The number of packets in a batch are geometrically distributed with an average of five packets. In each burst, the last packet has size distributed as uniform (0,1000) bytes. All other packets have 1000 bytes.

 
Figure 1: Simulation model for AF class.

Here also c_LB/r, c_OO/r, and c_P/r refer to overprovisioning required when, dimensioning for average delays using LB based model, using on–off-based model and Poisson-based model, respectively. Observe that the capacity computed using these models along with PDD-based scheduling for single, five, and ten voice and video sources. Now we use that capacity for the simulation and compare in Figures 2 through 7 the delays for single, five, and ten voice and video sources. We have plotted the observed mean delay and error bars corresponding to twice the sample standard deviation for voice and video sources. We also present a horizontal line showing the required average delay for each source.

 
Figure 2: Delay for single voice source.

 
Figure 3: Delay for single video source.

 
Figure 4: Delay for five voice source.

 
Figure 5: Delay for five video source.

 
Figure 5: Delay for ten voice source.

 
Figure 6: Delay for ten video source.

Note that for the Poisson-based capacity model with single sources, the actual mean delay is many times the target delay, both for voice and video. Moreover, some voice packets can have a delay as high as 400 ms and will be useless at the receiver. For video also, packets can have delays as much as 1 s. Such a capacity planning is not very useful and could lead to unsatisfied customers. When we multiplex five or ten voice and video sources, the average delays get closer to the target delays and for ten sources, they are even acceptable for both voice and video. However, there is still a large variance in the observed delays and voice packets could still have as high as 40 ms and video as high as 100 ms. Note that such high delays could be tolerable if they affect only a small number of packets.

Next, we consider on–off and LB-based design models. Observe that both the approaches provide acceptable delays, average as well as average along with two times standard deviation. The values are smaller than the required delays and hence a significant fraction of packets belonging to voice and video sources will encounter less than required delays. These models remain consistent for single, five, or ten sources and provide acceptable, performance to individual sources. Note that the LB-based model provides delays which are less than the target for both voice and video, although it requires lesser capacity than the on–off-based models. Observe that not only the delays are acceptable but also the variance is quite small.

Based on these results, it can be argued that LB-based model could be used to determine required capacity for a source requesting an average delay QoS. When allocating capacity for a small number of sources, it can achieve the multiplexing gain and provides minimal capacity to meet the required delays.

NETWORK DIMENSIONING AND DESIGN

Designing, deploying, and managing any wireless cellular system requires clear objectives to be identified from the outset. These includes definition of the footprint coverage, the estimated number of users, the traffic load distribution, the penetration and growth rate, and internetwork access and roaming. Mobile WiMAX, which will be deployed like 2G and 3G cellular networks, supports fractional frequency. Fractional frequency reuse takes advantage of the fact that mobile WiMAX user transmit on subchannels and does not occupy an entire channel such as in 3G. The objective of the radio network dimensioning and design activity is to estimate the number of sites required to provide coverage and capacity for the targeted service areas and subscriber forecast. This process is based on many assumption such as uniform distribution of subscribers, homogenous morphology, and ideal site location. The main inputs required for network dimensioning are site equipment-specific parameters, marketing-specific parameters, and licenses regulation and propagation models. Figure 1 shows the flow chart of activities performed in network design and planning, starting from data collection of marketing and design requirement input and achieving the business model to provide a nominal site plan using a network simulation software.

 

Figure 1: The cell planning process.

Mobile WiMAX is designed to complement existing 2G/3G access technologies with an “Always Best Connected” experience with voice and data connections. There is a large range of possible scenarios for the deployment of mobile WiMAX, but main four categories are

• Fixed and mobile operator with enhanced data for GSM evolution (EDGE)/3G who uses mobile WiMAX as a complementary extension for data services
• Mobile only operator with EDGE/3G who uses mobile WiMAX as a complementary extension for data services
• Fixed operator who uses mobile WiMAX to compete with 3G operators for data and voice services
• New entrant who uses mobile WiMAX to move into mobile market—threat to incumbent mobile operator.

WiMAX operates in a mixture of licensed and unlicensed bands. The unlicensed bands are typically the 2.4- and 5.8-GHz bands. Licensed spectrum provides operators control over the usage of the band, allowing them to build a high-quality network. The unlicensed band, on the other hand, allows independence to provide backhaul services for hotspots. Typical area licensed WiMAX spectrum allocations are

• Lower 700 MHz (US) with 2 × 6 MHz channels
• 2.5 GHz Multichannel Multipoint Distribution Service with 15.5 MHz in US and 72 MHz in Canada
• 3.5 GHz Wireless Local Loop with 2 × 2 MHz channel blocks
• 5.8 GHz UNI (license exempt) with 80 MHz allocation

WiMAX access networks are often deployed in point-to-multipoint cellular fashion where a single BS provides wireless coverage to a set of end users stations within the coverage area. The technology behind WiMAX has been optimized to provide both large coverage distances of up to 30 km under line-of-sight (LOS) situations and typical cell range of up to 8 km under NLOS. In an NLOS, a signal reaches the receiver through reflections, scattering, and diffractions. The signals arriving at the receiver consists of many components from direct and indirect paths with different delay spreads, attenuation, polarizations, and stability relative to the direct path. WiMAX technology solves or mitigates the problem resulting from NLOS conditions by using OFDMA, Subchannelization, directional antennas, transceiver diversity, adaptive modulation, error correction, and power control. The NLOS technology also reduces installation expenses by making the under-the-eaves customer premise equipment (CPE) installation a reality and easing the difficulty of locating adequate CPE mounting locations.

Both LOS and NLOS coverage conditions are governed by propagation characteristics of their environment, radio link budget, and path loss. In both the cases, relays help to extend the range of the BS footprint coverage allowing for a cost-efficient deployment and service.