| Wireless Mesh Networks (WMN's), in the form of WiFi (802.11x) or WiMax (802.16x), or their integrations have been proposed as an effective communication alternative for ubiquitous last mile wireless broadband access. They can be viewed as a hybrid between traditional cellular, point-to-point wireless systems, and ad-hoc networks. They offer more flexibility, mobility, coverage and expandability compared to their traditional counterparts at the expense of complex architecture and deployment structure. Though WMNs hold great promise in abetting network ubiquity, there still remain several challenges in the design and development of WMN's to support diverse services with different quality of service (QoS) requirements and large scale deployment. The focus of this dissertation is to address some of the core issues that directly affect the QoS in terms of delay, throughput, and fault tolerance.;First we look at the deployment problem of the placement of wired gateways. This aspect of WMNs has a significant impact on the network's throughput performance, cost and capacity to satisfying the quality of service requirements. In the context of gateway placement, the QoS is influenced by the number of gateways, the number of nodes served by each gateway, the location of the gateways, and the relay load on each wireless router. While finding an optimal solution to simultaneously satisfy all the above constraints is known to be an NP -hard problem, near optimal solutions can be found within the feasibility region in polynomial time using various heuristic methods. In the initial part of this dissertation, we first present a near optimal heuristics algorithm for gateway placement that facilitates QoS provisioning and fault tolerance in WMNs. We then investigate fault tolerance and recovery problems in WMNs. We present a fault recovery algorithm that can exploit the known geometry of a regular cellular mesh network. While keeping the QoS metrics intact, we consider a post-deployment fault recovery algorithm and pre-deployment fault tolerance planning. |
