Scheduling And Routing Algorithms For Wi-Max Mesh Networks

Applications such as video and audio streaming, online gaming, video conferencing, Voice over IP (VoIP) and File Transfer Protocol (FTP) demand a wide range of QoS requirements such as bandwidth and delay. Existing wireless technologies that can satisfy the requirements of heterogeneous traffic are very costly to deploy in rural areas and "last mile" access. WiMax provides an affordable alternative for wireless broadband access supporting a multiplicity of applications.IEEE 802.16 standards for Wireless Metropolitan Area Networks (WMANs) include a mesh mode of operation for improving the coverage and throughput of the network.The IEEE 802.16 standard provides specifications for the MAC and PHY layers for WiMax. Two critical parts of the MAC layer specification are scheduling and routing, where scheduling resolves contention for band-width and determines the transmission order of users, while the routing is the process of selecting paths in a network along which to send network traffic.In order to provide the coverage and data rates envisioned, even on un-even terrain, the use of multihop communication seems desirable. Hence WiMax supports a mesh mode in which unlike the traditional cellular sys-tems, the nodes can communicate without having a direct connection with the base station.In IEEE 802.16 Mesh network, a node that has a direct connection to backhaul services outside the Mesh network is termed a Mesh Base Station (MBS). All other nodes of a Mesh network are termed Mesh Subscriber Sta-tions (MSS). These nodes are stationary, i.e., the standard does not support mobility. The standard specifies a centralized scheduling scheme for mesh networks. Under this scheme, the MSSs notify the MBS with their data transfer requirements and the quality of their links to their neighbours. The MBS uses the topology information along with the requirements of each MSS to decide the routing and the scheduling. The MAC scheme used is TDMA and the resource allocation is in terms of time slots within a frame. The standard neither specifies an algorithm for scheduling of the slots to different MSSs; nor specifies any routing algorithm. Scheduling and routing will have a significant impact on the performance of the system and will largely decide the end to end QoS to different users.In this thesis, two centralized scheduling algorithms are developed, which are a QoS mechanism and a BS Scheduler for the IEEE 802.16 Mesh mode to ensure meeting the QoS requirements, and a Novel BS Scheduling (NBSS) algorithm for IEEE 802.16 mesh mode. And another routing algo-rithm is also introduced and that is an Adaptive Traffic Load Balancing (ATLB) mechanism.To ensure meeting the QoS requirements, the IEEE 802.16 MBS must run an algorithm to allocate time slots between connections. This algorithm is not defined in the IEEE 802.16 specification, but rather it is open for al-ternative implementations. The proposed QoS mechanism is developed by modifying the default QoS mechanism of the IEEE 802.16 PMP mode. The proposed QoS mechanism is compared against the default Mesh QoS me-chanism of IEEE 802.16. The performance of both methods is determined using simulation. The results of the simulation show that the default QoS mechanism introduces a delay of at least 100 ms, which makes it inappro-priate for real time and multimedia services.The main idea behind NBSS is to provide hybrid differentiated services based on the traffic demand of nodes and priority-based scheduling (PBS), in which a node with lower traffic demand is given a relatively higher prior-ity. Extensive analysis and simulation results show that NBSS can reduce the average delay time of MSS nodes and serve more MSS nodes.The ATLB is introduced to provide a mechanism scheme to drive part of a traffic load from busy APs to light load APs nodes and balance the traf-fic load of WMN. Because the nature of routing algorithm and there is more than one access point AP in a wireless mesh network, the traffic load of each AP is quite different. An AP may be extremely busy during a particular pe-riod while the others are in very light loads, in consequence, of the inherent characteristic of routing algorithm of WMN. A traffic load concentrates on an AP may lead to network congestion, increase the packet loss rate and de-grade the performance of network. ATLB discovers the heavy loaded or overloaded nodes, and then balances the traffic load of WMN. It includes the following two schemes:Traffic Load Detection (TLD) scheme which dis-covers the heavy loaded node, and Traffic Load Balancing (TLB) scheme which guide part of traffic from heavy to light traffic loaded node. A simula-tion process is conducted to measure the performance of ATLB and the re-sults show that the ATLB mechanism can enhance the Performance of WMN.