Multi-hop wireless mesh networks (WMNs) provide a cost-effective means to enable broadband wireless access (BWA) services to end users. Such WMNs are required to support different classes of traffic where each class requires certain quality of service (QoS) levels. The research direction undertaken in this thesis considers the development of enhanced routing and scheduling algorithms that enable WMNs to support various QoS metrics for the served traffic.
A fundamental class of routing problems in WMNs asks whether a given end-to-end flow that requires certain bandwidth, and benefits from routing over a single path (also called non-bifurcated routing), can be routed given that some ongoing flows are being served in the network. In the thesis, we focus on the development of combinatorial algorithms for solving such incremental non-bifurcated problems for two types of WMNs:
1. WMNs where mesh routers use contention-based protocol for medium access control (MAC), and
2. WMNs where mesh routers use time division multiple access (TDMA) for MAC.
For WMNs employing contention-based MAC protocols, we present a novel non-bifurcated routing algorithm that employs techniques from the theory of network flows. The main ingredient in our algorithm is a method for computing interference-constrained flow augmenting paths for routing subscriber demands in the network.
For WMNs employing TDMA, we develop a number of joint routing and scheduling algorithms, and investigate the use of such algorithms to maximize the number of served flows. In chapter 4, we consider a throughput maximization problem in the well-known class of grid WMNs. We present an iterative algorithm that strives to achieve high throughput by considering routing and scheduling a pair of distinct flows simultaneously to the gateway in each iteration.
In chapter 5, we explore joint routing and scheduling in TDMA-based WMNs with arbitrary topologies, and devise an algorithm that can deal with arbitrary interference relations among pairs of transmission links. In particular, our devised algorithm solves a generalized problem where a cost value is associated with using any possible time-slot on any transmission link, and a minimum cost route is sought along which a new flow can be scheduled without perturbing existing slot assignments.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:AEU.10048/1424 |
| Date | 11 1900 |
| Creators | Mahmood, Abdullah-Al |
| Contributors | Elmallah, Ehab (Computing Science), MacGregor, Mike (Computing Science), Lin, Guohui (Computing Science), Ardakani, Masoud (Electrical and Computer Engineering), Turgut, Damla (Electrical Engineering and Computer Science, University of Central Florida) |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | en_US |
| Detected Language | English |
| Type | Thesis |
| Format | 761443 bytes, application/pdf |
| Relation | A.-A. Mahmood, E. S. Elmallah, and A. Kamal. Non-bifurcated routing in wireless multi-hop mesh networks. In LCN 07: Proceedings of the 32nd IEEE Conference on Local Computer Networks, pages 279286, October 2007., A.-A. Mahmood and E. S. Elmallah. Joint non-bifurcated routing and scheduling in wireless grid mesh networks. In BROADNETS 2009: Proceedings of Sixth International Coference on Broadband Communications, Networks, and Systems, pages 17, September 2009., A.-A. Mahmood and E. S. Elmallah. Incremental routing and scheduling in wireless grids. In Global Telecommunications Conference, 2009. IEEE GLOBECOM 2009., pages 16, November-December 2009., A.-A. Mahmood and E. S. Elmallah. An algorithm for incremental joint routing and scheduling in wireless mesh networks. In IEEE Wireless Communications and Networking Conference, 2010. . WCNC 2010., pages 16, April 2010. |
Page generated in 0.0022 seconds