LITERATURE SURVEY

An in-depth survey which covers the research activities and open issues from physical layer to applications, and from mobility management to power management, from designs with single channel single radio device to those with multiple channel multiple radio devices. However, most of the existing researches about wireless mesh networks are based on IEEE 802.11 standard. The routing and MAC layer protocols designed for 802.11 standard-based wireless mesh network cannot be used directly or efficiently for WiMAX mesh networks. And not much work has been done on WiMAX mesh networks. In this section, we will introduce the routing and scheduling related work on WiMAX mesh networks.

COORDINATED DISTRIBUTED SCHEDULING

The main idea of the coordinated distributed scheduling is to coordinate the transmission of MSH-DSCH messages over transmission opportunities in a collision-free manner. Through the exchanges of collision-free MSH-DSCH over control subframes, collision-free data slot reservations in the data subframes can be achieved.

To achieve the goal of collision-free MSH-DSCH transmission, nodes will exchange 2-hop or 3-hop neighborhood scheduling information with each other. Because nodes shall run the scheduling algorithm independently, a common algorithm has been specified in the standard for each node in the neighborhood to calculate the same schedule. The algorithm is random and predictable by dynamically constructing the seeds of a random number generator for each node according to a common rule. In particular, the seed for a given node is constructed based on its unique node ID and the index of the candidate transmission opportunity. The most important parameters that have significant impacts on the performance of coordinated distributed scheduling are Xmt Holdoff Exponet (3 bits) and Next Xmt Xm (5 bits). They can be used to control the contention on the transmission opportunities and improve bandwidth utilization.

Due to the importance of the coordinated distributed scheduling on the network performances, an analytical framework is needed to assess the performance of the scheduling scheme. Cao et al. analytically investigated how the channel contention is correlated with the total node number, exponent value, and network topology. With the assumption that the transmit time sequences of all the nodes in the control subframe form statistically independent renewal processes, they developed methods for estimating the distributions of the node transmission interval and connection setup delay. The analytical method will be helpful for evaluating upper layer performance like throughput and delay. They implemented the coordinated distributed scheduling module in NS-2 and showed that their analytical model is quite accurate under various scenarios, including both single hop and multihop networks.

Based on Cao’s analytical model, Bayer et al. presented an enhancement of the model. In particularly, they evaluated the scalability of the coordinated distributed scheduling. A scalability problem was observed that leads to poor performance in dense networks and aggravates QoS provisioning. The problem may result from the election-based transmission timing mechanism for scheduling the transmission of MSH-DSCH messages. They propose a dynamic adaptation mechanism to counteract the scalability problem, in which the parameter Xmt Holdoff Exponet is dynamically and locally adjusted according to the network contention and the status of a node. The Next Xmt Xm is used as a contention indicator. If Next Xmt Xm used by the node or its neighbors exceeds a specified threshold, the Xmt Holdoff Exponet is increased. The status of a node is defined according to its transmission activity, if it is BS or if it is a sponsor node. Significant UDP throughput increase is observed with the application of the adaptation mechanism for both single and multiple hop network scenarios.

In the 802.16 standard and the above analytical work, it is assumed that the control messages can be transmitted without collision in the extended neighborhood (2-hop or 3-hop). However, such kind of interference model may not hold in practice. Zhu and Lu investigate the performance of coordinated distributed scheduling under a realistic interference model [12]. Extensive simulations were conducted to evaluate the reception collision performance of the scheduling mechanism. It was reported that the collision ratio of control messages can be as high as 20 percent for 2-hop extended neighborhood. They studied how to deal with the collision problem by appropriate configuration of parameters such as Xmt Holdoff Exponent.

MESH NETWORK ENTRY MECHANISM

The standard specifies network entry mechanism to find sponsor nodes and establish links with neighbors. In this chapter, the network entry mechanism is used as one of the alternatives to establish traffic routes for WiMAX mesh networks. Upon entering the mesh network, a new SS searches for MSH-NCFG to acquire coarse synchronization with the network. Once the physical layer has achieved synchronization, the MAC layer can acquire network parameters for the MSH-NCFG message. Meanwhile, the SS can builds a physical neighbor list, from which the SS can select a potential sponsor node out of the eligible sponsor nodes. How to select the sponsor node is not specified in the standard. The selection method will be discussed in more details later in this chapter. The SS then synchronizes its time to the potential sponsor node and sends a network entry request message to the potential sponsor node. If the candidate sponsor node accepts the request and opens a sponsor channel, the channel is ready for use to register with the BSs. After the SS is authorized to enter the network by the BS, it can request bandwidth from the BS via the sponsor node and can also establish links with the SSs other than the sponsor node.

BANDWIDTH ALLOCATION AND GRANT MECHANISMS

In the 802.16 standard, flexible bandwidth allocation and grant mechanisms have been defined for PMP mode to guarantee the QoS of various service flows. Those mechanisms include periodically polling, real-time polling, nonreal-time polling, contention-based bandwidth request scheme, poll-me bit, bandwidth stealing, and piggyback. However, the bandwidth request and grant mechanisms can not be used in Mesh mode due to the multihop networking in Mesh mode. In WiMAX Mesh mode, all the communications in the links in the network are controlled by three ways, i.e., using a centralized scheduling algorithm, using a distributed scheduling algorithm within each node’s extended neighborhood, or using a combination of these two types of algorithms.

In the coordinated distributed scheduling algorithm, all stations (BS and SSs) coordinate their transmissions in their extended two-hop neighborhood. Coordinated distributed scheduling does not rely on the operation of a BS and transmissions are not necessarily directed to or from the BS. Within the constraints of the coordinated schedules, uncoordinated distributed scheduling can be used for fast and ad-hoc setup of schedules on a link-by-link basis with directed requests. Grants of the uncoordinated schedules need to ensure that the resulting data transmissions do not cause collisions with the data and control traffic scheduled by the coordinated scheduling algorithms.

Although distributed scheduling algorithms are more scalable, they are inefficient in QoS guarantee. On the other hand, centralized scheduling ensures collision-free scheduling over the links in the network, typically in a more optimal manner than the distributed scheduling method. Therefore better QoS support and network bandwidth utilization can be achieved. In this chapter centralized scheduling will be the only scheduling algorithm studied.

Centralized Scheduling

With the centralized scheduling algorithm, transmission schedule for the SSs is defined by the BS. The BS determines the flow assignments from the resource requests from the SSs. Subsequently, the SSs validate the MSH-CSCH schedule and determine the actual schedule from these flow assignments. The assignments determined by the BS extends to those SSs not directly connected to the BS. Intermediate SSs are responsible for forwarding bandwidth requests for SSs listed in the routing tree that are further from the BS (i.e., more hops from the BS) and the MSH-CSCH message from the BS to their neighbors as required. The SS resource requests and the BS assignments are both transmitted during the schedule control subframe. Centralized scheduling ensures that transmissions are coordinated to ensure collision-free scheduling over the links in the routing tree to and from the BS. The centralized scheduling will persist over a duration that is greater than the cycle time to relay the new resource requests and distribute the updated schedule.

Determination of the flow assignment and routing tree is outside the scope of the standard.

Distributed Scheduling

Coordinated distributed scheduling ensures that transmissions are scheduled in a manner that does not rely on the operation of a BS, and that is not necessarily directed to or from the BS. In the coordinated distributed scheduling mode, all the stations (BS and SSs) need coordinate their transmissions in their extended two-hop neighborhood. The coordinated distributed scheduling mode uses some or the entire control portion of each frame to regularly transmit its own schedule and proposed schedule changes on a PMP basis to all its neighbors. Within a given channel all neighbor stations receive the same schedule transmissions. All the stations in a network have to use the same channel to transmit schedule information in a format of specific resource requests and grants.

Within the constraints of the coordinated schedules (distributed or centralized), uncoordinated distributed scheduling can be used for fast, ad-hoc setup of schedules on a link-by-link basis. Uncoordinated distributed schedules are established by directed requests and grants between two nodes, and shall be scheduled to ensure that the resulting data transmissions (and the request and grant packets themselves) do not cause collisions with the data and control traffic scheduled by the coordinated distributed nor the centralized scheduling methods.

The major differences between coordinated and uncoordinated distributed scheduling are in the portions where the MSH-DSCH messages are transmitted. In the coordinated case, the MSH-DSCH messages are scheduled in the control subframe in a collision-free manner. In the uncoordinated case, MSH-DSCH messages are transmitted in data subframes and may collide.

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.