WiMAX PHYSICAL AND MAC LAYERS

WiMAX PHY is responsible for the transmission of data over the air interface (physical medium). The PHY receives MAC layer data packets through its interface with the lowest MAC sublayer, and transmits them according to the MAC layer QoS scheduling. WiMAX MAC layer comprises of three sublayers, which interact through service access points (SAP) to provide the MAC layer services, as shown in Figure 1. The convergence sublayer (CS) interfaces the WiMAX network with other networks by mapping external network data (from ATM, Ethernet, IP, etc.) to the WiMAX system. MAC common part sublayer (MAC CPS) provides majority of the MAC layer services. The MAC CPS receives data from the CS as MAC service data unit (MAC SDU) and efficiently packs them on to the payload of the MAC packet data unit (MAC PDU) through the process of fragmentation and aggregations. Fragmented parts of MAC SDU are used to fill (aggregate) remnant portions of MAC PDU payloads that cannot accommodate full MAC SDU during package. As WiMAX provides connection-oriented service, MAC CPS is also responsible for bandwidth request/reservation for a requested connection, connection establishment, and maintenance. In the WiMAX standard, bandwidth request/reservation is an adaptive process that takes place on a frame-by-frame basis. This allows more efficient resource utilization and optimized performance. Thus the MAC CPS is required to provide up-to-date data on bandwidth request/reservation for each connection, on a frame-by-frame basis. The MAC CPS also provides connection ID for each established connection and marks all MAC PDUs traversing the MAC interface to the PHY with the respective connection ID. This sublayer also performs QoS scheduling by deciding the orders of packet transmissions on the PHY, based on the service flow decided during connection establishments. Privacy sublayer provides authentication to prevent theft of services, and encryption to provide security of services.

 
Figure 1: WiMAX Protocol stack.

The ensemble of the activities of the three sublayers of the WiMAX MAC layer constitutes the MAC layer services. MAC layer services can broadly be categorized into two: periodic and aperiodic activities. Periodic activities are fast- or delay-sensitive types of activities and are carried out to support ongoing communications, thus they must be completed in one frame duration. Examples include QoS scheduling, packing, and fragmentation. Aperiodic activities are slow- or delay-insensitive types of activities. They are executed when and as required by the system, and are not bounded by frame durations. Examples include ranging and authentications for network entry.

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.