| Multi-Radio Multi-Channel (MR-MC) wireless networks is a hot research area in recent years. Multipath routing is attractive for load-balancing, fault-tolerance, and security enhancement. It is a clear perspective of the combination of these two, which will improve both the network performance and the efficiency of the resources utilization. However, constructing and maintaining a set of node-disjoint paths between the data source and the sink, and optimally scheduling the communications without interference, are non-trivial in a dynamic wireless environment. In this dissertation, I jointly consider these two problems.;I first identify the sufficient conditions for the existence of N node-disjoint multipaths, and provide a simple framework for multipath maintenance. This framework is very efficient in time when multipath source routing is employed. My findings can help to conserve network resource by not launching any route discovery when the data source realizes that a new route may not exist, to guide mobile data sources to relocate themselves in order to reconstruct the new multipaths, and to help newly-deployed data sources quickly determine whether the required number of multipaths exist for sure or not and then compute them. The technique proposed is a good complement to the classic max-flow algorithm when node-disjoint multipaths are needed.;After the required multipath communication topology has been obtained, I study the problem of channel scheduling. The complexity of channel scheduling in Multi-Radio Multi-Channel (MR-MC) wireless networks is an open research topic. This problem asks for the set of edges that can support maximum amount of simultaneous traffic over orthogonal channels under a certain interference model. There exist two major interference models for channel scheduling, with one under the physical distance constraint, and one under the hop distance constraint. The complexity of channel scheduling under these two interference models serves as the foundation for many problems related to network throughput maximization. However, channel scheduling was proved to be NP-Hard only under the hop distance constraint for Single-Radio Single-Channel (SR-SC) wireless networks. In my dissertation, I fill the void by proving that channel scheduling is NP- Hard under both models in MR-MC wireless networks. In addition, I propose a polynomial-time approximation scheme (PTAS) framework that is applicable to channel scheduling under both interference models in MR-MC wireless networks. Furthermore, I conduct a comparison study on the two interference models and identify conditions under which these two models are equivalent for channel scheduling. |
