Download the full-sized PDF of Non-bifurcated routing and scheduling in wireless mesh networksDownload the full-sized PDF



Permanent link (DOI):


Export to: EndNote  |  Zotero  |  Mendeley


This file is in the following communities:

Graduate Studies and Research, Faculty of


This file is in the following collections:

Theses and Dissertations

Non-bifurcated routing and scheduling in wireless mesh networks Open Access


Other title
Wireless Mesh Network
Type of item
Degree grantor
University of Alberta
Author or creator
Mahmood, Abdullah-Al
Supervisor and department
Elmallah, Ehab (Computing Science)
Examining committee member and department
MacGregor, Mike (Computing Science)
Ardakani, Masoud (Electrical and Computer Engineering)
Lin, Guohui (Computing Science)
Turgut, Damla (Electrical Engineering and Computer Science, University of Central Florida)
Department of Computing Science

Date accepted
Graduation date
Doctor of Philosophy
Degree level
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.
License granted by ABDULLAH-AL MAHMOOD ( on 2010-09-21T01:38:56Z (GMT): Permission is hereby granted to the University of Alberta Libraries to reproduce single copies of this thesis and to lend or sell such copies for private, scholarly or scientific research purposes only. Where the thesis is converted to, or otherwise made available in digital form, the University of Alberta will advise potential users of the thesis of the above terms. The author reserves all other publication and other rights in association with the copyright in the thesis, and except as herein provided, neither the thesis nor any substantial portion thereof may be printed or otherwise reproduced in any material form whatsoever without the author's prior written permission.
Citation for previous publication

File Details

Date Uploaded
Date Modified
Audit Status
Audits have not yet been run on this file.
File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 761443
Last modified: 2015:10:12 12:39:53-06:00
Filename: Mahmood_Abdullah-Al_Fall 2010.pdf
Original checksum: 0b33e160b51f1dbcde6ccb60c0b20982
Well formed: true
Valid: true
File title: main.dvi
Page count: 135
Activity of users you follow
User Activity Date