The 802.16 network supports only time division duplex (TDD) in the MESH mode. Figure 1 shows the corresponding frame structure. The time axis is divided into frames of a specified length decided by the mesh BS. Each frame is in turn composed of a control subframe and a data subframe. There are two types of control subframes, namely the network control subframe and the schedule control subframe. Network control subframes are used to transmit network configuration information as well as to allow new nodes to register and join the network. The schedule control subframe is used by nodes to transmit scheduling information, and to request and grant bandwidth for transmission. All data transmissions take place in the data subframe using slots previously reserved by the node for transmission. The control subframe is divided into a number of transmission opportunities and the data subframe is divided into a number of minislots. The length of the control subframe depends on the mesh configuration in use. This decides the number of transmission opportunities in the control subframe and the number of minislots in the data subframe. The MESH mode supports coordinated centralized scheduling, and coordinated as well as uncoordinated distributed scheduling for allocating bandwidth for transmission on individual links in the MESH mode of operation. The mesh configuration specifies a maximum percentage of minislots in the data subframe allocated to centralized scheduling. The remainder of the data subframe as well as any minislots not occupied by the current centralized schedule can be used for distributed scheduling.
Figure 1: MESH frame structure. Abbreviations—MAC, Medium Access Control; PDU, protocol data units.
In centralized scheduling, the bandwidth is managed in a more centralized manner than when using distributed scheduling. Thus, although the computation of the actual transmission schedule is done by the individual nodes independently (in a distributed manner), the grants for each individual node are controlled centrally by the BS in coordinated centralized scheduling (also called centralized scheduling). The BS uses centralized scheduling to manage and allocate bandwidth for transmissions up and down the routing tree (scheduling tree, see Figure 2 for an example) from the BS to the SSs up to a specified maximum hop limit. The routing tree is advertised by the BS periodically using MSH-CSCF messages. The BS in the mesh network gathers resource requests from individual SSs within the maximum hop range. Each SS in the scheduling tree accumulates the requests from its children and adds to it its own requirement for uplink bandwidth before forwarding the request upwards along the scheduling tree (uplink here implies transmission along a link in the scheduling tree from a SS to another SS that is closer to the BS; downlink will be considered to be a transmission down the tree in the opposite direction). The BS collects all the requests and transmits the grants to its children. The grants for each individual SS are then propagated down the scheduling tree hop-by-hop. Nodes use MSH-CSCH messages to propagate requests and grants for centralized scheduling.
Figure 2: Overview of scheduling in the MESH mode.
The grants propagated to the SSs in the scheduling tree do not contain the actual schedule. Each SS computes the schedule using a predetermined algorithm and the parameters obtained from the grant. Using centralized scheduling, transmissions can be scheduled only along the links in the scheduling tree. To reserve bandwidth for transmission on links not in the scheduling tree, distributed scheduling has to be used.
Distributed scheduling is used by a node to reserve bandwidth for transmission on a link to any other neighboring node (also for links included in the centralized scheduling tree). Nodes use distributed scheduling to coordinate their transmissions in their two-hop neighborhood. The nodes use a distributed election algorithm to compete for transmission opportunities in the schedule control subframe. A pseudo-random function (the mesh election algorithm specified in the 802.16 standard), with the node IDs of the competitors and the transmission opportunity number as input determines the winning node. The losing nodes compete for the next DSCH transmission opportunity until they win. The parameter XmtHoldoffExponent of each node determines the magnitude of transmission opportunities a node has to wait after sending a distributed scheduling message (MSH-DSCH) in a won transmission opportunity.
The mean time a node has to wait between two won transmission opportunities for distributed scheduling messages depends on the number of nodes in the two-hop neighborhood, the node's own XmtHoldoffExponent, and the network topology. It show that the time a node has to wait between two distributed scheduling transmission opportunities it wins increases with an increase in the number of two-hop neighbors and moreover with an increase in the value of the XmtHoldoffExponent.
When using coordinated distributed scheduling, the nodes broadcast their individual schedules (available bandwidth resources, bandwidth requests, and bandwidth grants) using transmission opportunities won by the node in the schedule control subframe. The mesh election algorithm ensures that when a node wins a transmission opportunity in the schedule control subframe for transmission, no other node in its two-hop neighborhood will simultaneously transmit. Thus, it is ensured that the scheduling information transmitted by a node in the schedule control subframe can be received by all of the nodes' neighbors. To enable a conflict-free schedule to be negotiated each node maintains the status of all individual minislots in the frame. A minislot at any point in time may be either in status available (node can receive or transmit data in minislot), receive available (node can only receive data in minislot), transmit available (node can only transmit data in the minislot), or unavailable (node may not transmit or receive data in the minislot).
The schedule negotiated using coordinated distributed scheduling is such that it does not lead to conflict with any of the existing data transmission schedules in the two-hop neighborhood of the transmitter. On the other hand, nodes can also establish their transmission schedule by directed uncoordinated requests and grants between two nodes. In contrast to coordinated distributed scheduling requests and grants which are sent in the schedule control subframe, the uncoordinated requests and grants are sent in the data subframe. The latter scheduling mechanism is called uncoordinated scheduling. When a node SS3 wants to reserve slots for transmission to a neighbor node SS4, they exchange scheduling information using slots in the data subframe reserved for transmissions between the two nodes (see Figure 2). Nodes individually need to ensure that their scheduled transmissions do not cause collisions with the data as well as with control traffic scheduled by any other node in their two-hop neighborhood. Transmissions in the data subframe using slots reserved for transmission to a particular neighbor may not be received by all the other neighbors due to other simultaneous transmissions. Thus, the schedule negotiated using the data subframe (uncoordinated scheduling) may not be known to all the neighbors of the nodes involved in the uncoordinated schedule. The neighbors of these nodes may then schedule conflicting transmissions due to lack of the previous uncoordinated schedule information. Hence, uncoordinated scheduling may lead to collisions and is not suitable for long-term bandwidth reservations. Nodes use MSH-DSCH messages to transmit the bandwidth requests grants and negotiate schedules when using distributed scheduling (both coordinated as well as uncoordinated distributed scheduling).
In contrast, centralized scheduling allows the setup of a transmission schedule for transmissions only along links in the scheduling tree, and hence, is not very suitable for enabling a wireless mesh network in the traditional sense. We next outline our novel proposed QoS architecture for bandwidth management in the MESH mode. Without loss of generality and to avoid confusion in the following discussion we assume that the nodes in the mesh network use only distributed scheduling.
The proposed QoS architecture using distributed scheduling is easily extensible and can be adapted for use in centralized scheduling, too. The proposed architecture uses a combination of coordinated distributed scheduling and uncoordinated distributed scheduling to efficiently manage the bandwidth in the network.
