Routing and Scheduling for WiMAX Mesh Networks

In addition to the mandatory implementation of point-to-multipoint (PMP) mode, WiMAX networks can be optionally configured to work in Mesh mode, to achieve increased reliability, coverage, and reduced network costs. Although IEEE 802.16 standards specify several quality of service (QoS) schemes and related message formats for WiMAX networks, the problems of scheduling algorithms for both PMP and Mesh mode are left unsolved. Routing algorithms for WiMAX networks are outside the scope of the standard work as well. In this chapter, we investigate the issues of routing and scheduling for WiMAX mesh networks. We overview the mesh mechanisms specified in the IEEE 802.16 standard and survey the existing research on scheduling and routing for WiMAX mesh networks. Then both distributed and centralized routing algorithms are studied, and their effectiveness on alleviating potential network congestion is compared. The scheduling problem is mathematically modeled by taking into account the interference constraints. Solutions are developed which can maximize the utilization of network capacity subject to fairness constraints on the allocation of scarce wireless bandwidth.

INTRODUCTION

In today’s telecommunications, networking and services are changing in a rapid way to support next generation Internet (NGI) user environment. Wireless networks will play an important role in NGI. Wireless broadband networks are being increasingly deployed and used in the last mile for extending or enhancing Internet connectivity for fixed or mobile clients located on the edge of the wired network.

With high data rate, large network coverage, strong QoS capabilities, and cheap network deployment and maintenance costs, WiMAX is regarded as a disruptive wireless technology and has many potential applications. It is expected to support business applications, for which QoS support will be a necessity. Depending on the applications and network investment, WiMAX network can be configured to work in different modes, point-to-multipoint (PMP) or Mesh mode. An illustration of PMP and mesh mode is presented in Figure 1. For example, the network can have a simple base station (BS) working in PMP mode and serving multiple subscriber stations (SSs) if the potential SSs can be covered by the BS. Mesh topology is an optional configuration for WiMAX networks. In the Mesh mode, traffic demands are aggregated at a set of SS nodes which are equipped with 802.16 interfaces. Subsequently, the traffic demands at SS nodes are delivered to a set of BSs nodes which functions in the PMP mode. These BS stations can be connected by a backhaul and connected to Internet access point (IAP) nodes. An amendment to the IEEE 802.16 specifications (where WiMAX is based) is IEEE 802.16j, Multihop Relay Specification. IEEE 802.16j is being developed by IEEE 802.16’s Relay Task Group. It is expected to extend reach/coverage through relaying. 

 

Figure 1: WiMAX (a) PMP network and (b) mesh network architectures.

Wireless mesh network offers increased reliability, coverage, and reduced network costs. There are extensive research, standardization, and commercial development activities on mesh networks. For example, several IEEE special task groups have been established to define the requirements for mesh networking in wireless personal area networks (WPANs), wireless local area networks (WLANs), and wireless metropolitan area networks (WMANs). A brief description of the standardization activities. Wireless mesh networks can be a prospective solution for broadband wireless Internet access in a flexible and cost-effective manner. However, wireless mesh networks also raise a number of research challenges, e.g., network routing, scheduling, QoS support, network management, etc. Those challenges are faced by WiMAX mesh networks without exception. WiMAX Mesh mode is defined with OFDM for frequency between 2 and 11 GHz and time division multiple access (TDMA) is used in the Medium Access Control (MAC) layer to support multiple users. Unlike the single hop wireless networks, routing algorithms are required to determine routes for the connections between a SS and a BS. As WiMAX networks operate synchronously in a time-slotted mode, it is also necessary to allocate time slots without collision over the network to achieve assigned bandwidth for each connection. More challenging is that the routing and scheduling for WiMAX networks are tightly coupled. The routing and scheduling problem for WiMAX networks is different from 802.11-based mesh networks. In the 802.11-based mesh networks, the MAC layer is contention-based; routing algorithms and MAC layer protocols can be designed and operated separately.

Although IEEE 802.16 standards specify several QoS schemes and related message formats, the problems of scheduling algorithms for both PMP and Mesh mode are left unsolved. Routing algorithms for WiMAX networks are outside the scope of the standard work as well. In this chapter, we will investigate the issues of routing and scheduling in WiMAX mesh networks. Both distributed and centralized routing algorithms will be studied, and their effectiveness on alleviating potential network congestion will be compared. The scheduling problem will also be mathematically modeled by taking into account the interference constraints. Solutions are developed to maximize the utilization of network capacity subject to fairness constraints on allocation of scarce wireless resource among the SSs.

CONCLUSIONS AND RECOMMENDATIONS | Relay-Assisted Mobile WiMAX

Achieving high throughputs with low outage probability in a large cell is a challenge, but this drives effective deployment with MIMO and multihop relay techniques, which have been intensively explored in this chapter. We have analyzed the effective relay efficiency. For relay systems without radio resource sharing, a higher relay SNR gain was required. This implies that the system requires a higher transmit power at the RS. In contrast, radio resource sharing offers high potential for a mobile WiMAX network when relays are deployed. Radio resource sharing is very applicable to MIMO relaying. In addition to multiuser transmission, the relay with radio resource sharing has the potential to achieve optimal multiuser relay gain.

To achieve the practical application of radio resource sharing, a relay system must be based on a topology that fully exploits effective resource assignment based on the spatial separation of nodes. Directional distributed relay topologies were introduced for highly efficient relay deployment. This scheme is fully backward compatible with the current mobile WiMAX standard.

Greater efficiencies in spectrum use can be achieved by coupling channel-quality information in the resource-allocation process. However, this study is heavily dependent upon realistic application environments. Channel modeling becomes critical to reflect application environments. With this purpose, a multihop relay measurement campaign was performed and is presented in this chapter. The measurement results have been analyzed and compared with several statistical and standardized models. It was found that the 802.16d model only matched well to the BS–RS link in terms of path loss and antenna-height correction factor. For the BS–MS link, the WINNER models were a good match to the shadowing, and the COST 231 Hata and WI models were useful for predicting path loss. The RS–MS link was also well matched by the WINNER shadowing values, but none of the path-loss models considered were a good match to any of individual measurement locations.

To demonstrate the potential of the directional distributed relay architecture in a realistic outdoor environment, a site-specific ray-tracing propagation model is used. Results show that, compared to a relay system without resource sharing, the implementation of resource sharing improves capacity significantly. For the OFDMA multiuser transmission, it is ideal to adopt flexible channelization and MIMO LA on different users, and multihop relay with efficient radio resource management.

MULTIHOP STUDY BASED ON RAY-TRACING

As mentioned before, a major issue for radio resource sharing is the interference. Greater efficiencies in spectrum use can be achieved by coupling channel-quality information in the resource-allocation process. Ray-tracing is an effective tool for network setup, evaluation, and optimization. To demonstrate the potential of the proposed resource sharing framework, a site specific ray-tracing propagation model is used in this section to provide realistic environment specific propagation data for the BS–MS, BS–RS, and RS–MS links.

The ray-tracing tool used in this work was verified with measurement data, and has been used in many previous WLAN and WiMAX system evaluations. The ray-tracing model takes individual buildings, trees, and terrain contours into account and determines specific multipaths based on scattering and diffraction. Mobile transitions from LoS to NLoS are naturally handled by the algorithms. In this study, we can easily utilize the ray tracer to establish the typical multihop relay application scenarios, such as coverage hole and cell edge. Also, it can directly demonstrate interference paths and strengths which is more suitable for studies presented in previous sections.

SIMULATION SCENARIO

Because mobile terminals are allowed to move freely at street level in the MWA scenario, local surrounding large and small obstructions and terrain contours result in path loss, shadowing, and multipath fading. Interferences from other signals also distort the transmitted signal in an unpredictable and time-varying fashion.

A realistic MWA scenario is now analyzed based on a region of Central Bristol, United Kingdom (Figure 10.16a). A single BS location was chosen on the roof top of a tall central building (30 m above ground level). Eighty-five MS units were distributed over this geographic area at street level with heights of 1.5 m. The BS with 3-sectors was assigned an EIRP of 57.3 dBm (based on a 15 dBi 1200 sector BS antenna). First, the raw multipath components (MPCs) are created using the above ray-tracing tool. Based on isotropic ray-traced channel data, the ETSI specific antenna beam patterns are then incorporated via spatial convolution. Figure 1 presents the distribution of received power from the BS to the surrounding region at street level. A severe coverage hole is clearly visible, and this is mainly caused by variations in the terrain height. Two methods could be used to achieve acceptable WiMAX coverage in this macrocell. First, a second BS could be deployed in the coverage hole. However, this would add to the infrastructure costs and hence it may be more effective to deploy an RS node.

 

Figure 1: Simulated macrocell in Bristol, United Kingdom.

Figure 2 shows the locations of MSs and their affiliations to either the BS or RS. The locations of BS, RS and MSs are overlaid on a terrain map of Bristol city-centre. For each MS a line is drawn to indicate whether communication occurs via the BS or RS. The choice of connection type depends on the received SINR. At a given location, signal power is obtained by sum of all received MPCs, which are transmitted by an assigned BS sector. Interferences are caused by MPCs which comes from either RS (for BS access) or BS (for RS access) if interfering users occupy same frequency resource as the detect user. It should be noted that in NLoS conditions the MS may connect to an adjacent sector since this is determined by the direction of the strongest path.

 

Figure 2: BS and RS radio resource location.

Figure 2 also demonstrates subchannel allocation for a 3-users OFDMA operating with a 5 MHz channel bandwidth, based on 512-FFT DL PUSC (Partial Usage of Sub-Channels) OFDMA TDD profile as specified in 802.16e. For the 512-FFT DL PUSC OFDMA, a total of 15 subchannels are mapped (after renumbering and permuting) in one OFDMA symbol. Each sector has access to one-third of the total number of subcarriers. There are 3 groups (one per sector), with 5 subchannels in each group. Each subchannel comprises 2 clusters (14 physical subcarriers in each cluster). This results in a total of 420 subcarriers in each OFDMA symbol (360 data bearing carriers and 60 pilot carriers). When the RS is used to connect to an MS, a certain number of timeslots (or alternatively subchannels) must be assigned in the covering sector to support the BS–RS link. Here we assume that BS–RS link and BS–MS link (taken from the sector covering the RS) are in group #3. When radio resource sharing is applied, a number of RS–MS and BS–MS links are supported simultaneously using the same resources. For all the RS–MS links, and also the BS–MS links where the antenna beam is steered away from the RS, it is possible to share group #1. Group #2 is used for those MSs that connect to one of the BS sectors (i.e., but not the sector coving the RS); these can be located near to the RS if required.