This thesis is concerned with the channel assignment (CA) problem in multi-channel
multi-interface wireless mesh networks (M2WNs). First, for M2WNs with general topologies,
we rigorously demonstrate using the combinatorial principle of inclusion/exclusion
that the CA solution space can be quantified, indicating that its cardinality is greatly
influenced by the number of radio interfaces installed on each router. Based on this analysis,
a novel scheme is developed to construct a new reduced search space, represented
by a lattice structure, that is searched more efficiently for a CA solution. The elements
in the reduced lattice-based space, labeled Solution Structures (SS), represent groupings
of feasible CA solutions satisfying the radio constraints at each node. Two algorithms
are presented for searching the lattice structure. The first is a greedy algorithm that
finds a good SS in polynomial time, while the second provides a user-controlled depthfirst
search for the optimal SS. The obtained SS is used to construct an unconstrained
weighted graph coloring problem which is then solved to satisfy the soft interference
constraints.
For the special class of full M2WNs (fM2WNs), we show that an optimal CA solution
can only be achieved with a certain number of channels; we denote this number as the
characteristic channel number and derive upper and lower bounds for that number as a
function of the number of radios per router. Furthermore, exact values for the required
channels for minimum interference are obtained when certain relations between the number
of routers and the radio interfaces in a given fM2WN are satisfied. These bounds are
then employed to develop closed-form expressions for the minimum channel interference
that achieves the maximum throughput for uniform traffic on all communication links.
Accordingly, a polynomial-time algorithm to find a near-optimal solution for the channel
assignment problem in fM2WN is developed.
Experimental results confirm the obtained theoretical results and demonstrate the
performance of the proposed schemes.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:OOU.#10393/20155 |
| Date | 12 August 2011 |
| Creators | González Barrameda, José Andrés |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | English |
| Type | Thèse / Thesis |
Page generated in 0.0023 seconds