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.
