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.