ROUTING ALGORITHMS | WiMAX Mesh Networks

In this section we will investigate routing and scheduling algorithms for WiMAX mesh networks, with the target application of using WiMAX mesh networks to network cellular BSs and gateways to the Internet. The gateways of general cellular networks can be mobile switching center (MSC) in GSM networks or MSC and serving GPRS support node (SGSN) in WCDMA networks. In this network architecture, the gateways act as 802.16 mesh BSs in the 802.16 backhaul network. They manage the backhaul network and allocate bandwidth to the SSs. The cellular BSs act as 802.16 SSs in the backhaul network. In the remaining part of the chapter, the cellular BSs will be called SSs for simplicity. The SSs forward aggregated traffic from the mobile users to Internet in the uplink direction and deliver traffic to the mobile users from the Internet in the downlink direction via the 802.16 BSs. For simplicity, only uplink traffic with QoS requirement is considered in this chapter. However, the approaches of routing and scheduling can be applied to bidirection traffic. It is assumed that the backhaul topology and traffic demands from the SSs will not change frequently. Therefore, the frequency of updating traffic routes and scheduling will be low. It is feasible and beneficial to use high performance algorithms such as the optimal centralize scheduling and routing algorithms.

CLASSIFICATION

As IEEE 802.16 standards specify the MAC and PHY layer protocols, routing protocols are outside the scope of the standard work. We can identify the following ways of solving routing and scheduling (bandwidth allocation) problems for WiMAX mesh networks:

• Centralized routing and centralized scheduling (CRCS): All the traffic, position information of the stations are sent to the BSs. The BSs jointly solve the routes and schedule problems, and send the routes/schedule information back to the SSs.
• Distributed routing and centralized scheduling (DRCS): SSs distributedly find their routes to the BSs. After the routes are found, the SSs send their information to the BSs. The BSs determine collision-free transmission schedule.
• Distributed routing and distributed scheduling (DRDS): Stations distributively find their routes to the BSs. After SSs find their routes to BSs, they work with their next-hop stations toward the BSs to determine collision-free transmission schedules in a distributed way.
• Hybrid routing and scheduling (HRS): Both routing and scheduling algorithms can be implemented in either a distributed or a centralized way.

In WiMAX mesh networks, distributed scheduling can be used by SSs with their neighbor SSs to reserve time slots. However, the success of reserving time slots will depend on the availability of free time slots not reserved by the centralized scheduling and other neighbor stations. As centralized scheduling has priority over distributed scheduling in WiMAX, it will be easier to provide time slots reservation for end-to-end QoS support. Therefore, we will consider only centralized scheduling in this chapter.

Centralized scheduling algorithm will work together with either centralized or distributed routing algorithms. For the centralized routing algorithm, routing, bandwidth allocation, and scheduling problem can be jointly investigated. We will formulate the joint routing, allocation, and scheduling problem with an optimal mathematical model. The input to the optimal model from the routing point of view will be network connectivity matrix CM, CM_ij = 1 if and only if station i is in the communication range of station j. After the optimal problem is solved, the route from an SS to a BS will be determined.

For the centralized scheduling and distributed routing algorithms, routes from SSs to BSs will be determined first. Then we can also derive network connectivity matrix CM for distributed routing. However, in this case, the station connectivity matrix CM will not only be determined by the communication ranges but also the traffic routes. We have CM_ij = 1 if and only if the link e_ij between station i and station j is in any route of SSs to BSs. Then the connectivity matric CM can be input to the optimization model for centralized scheduling. 

DISTRIBUTED ROUTING

In the WiMAX mesh networks, the BSs will periodically broadcast network configuration messages, which are further forwarded by the neighbor stations. The forwarding process continues toward network edge until the predefined maximum number of hops is reached. For each forwarding neighbor stations, it will add the information of hops from itself to the BSs. Although routing algorithm is not specified in the standards, the distance information together with other local information can be utilized by a new SS to find a route to a BS.

For a new SS to join the WiMAX mesh network, it is required to listen to the network configuration/synchronization from its neighbor stations. After it hears network configuration message at least twice from a station, it can send request to join the network through this station. With the available local information, such as the signal strength, distance between, the new station can select which station to be its sponsor station to a BS. Therefore the distributed routing algorithm can be reduced to find a sponsor station for a route toward a BS. We simply give four methods.

• Random selection (RS): In this method, a new station will choose a neighbor station as its sponsor station randomly among the candidate stations with the same minimum number of hops to a BS.
• Minimum node ID (MID): Among all the neighbor stations with the same minimum number of hops to any BSs, the station with minimum node ID will be selected as the sponsor station.
• Maximum signal strength (MSS): The station with maximum average signal strength will be selected as the sponsor station among the candidate stations, which can achieve higher transmission data rate.
• Minimum aggregate traffic (MAT): To balance traffic routed over the neighbor stations, a new station can also choose the station with minimum aggregated traffic load among the candidate stations.

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.