Vinay's dissertation defense: 2007-11-28 @8:30AM in EBG11

Ph.D. DISSERTATION DEFENSE
Routing and Traffic Engineering in Multi-hop Wireless Networks: An optimization based approach
Vinay Kolar
vinkolar@cs.binghamton.edu
Dept. of Computer Science, SUNY, Binghamton.
Advisor: Dr. Nael Abu-Ghazaleh
Date: Nov 28, 2007, Wednesday  Time: 8:30 A.M.  Room: EB-G11
Abstract

   Multi-hop wireless networks (MHWNs) attract significant interest due to the minimal infrastructure demands and their potential in supporting mobile and pervasive computing. The high demand placed by a growing user base on the limited available bandwidth places a premium on effective communication and networking for MHWNs. The dissertation targets developing a formally grounded approach to solving routing problems in MHWNs, while taking into account the effects of interference. The work builds on recent efforts in the networking community to express a network as an optimization problem, and decomposing the formulation to provide distributed protocols. A successful model can then be applied to: (1) analyze the performance and capacity of existing protocols; (2) develop protocols for traffic engineering and admission for static networks; and (3) develop formally grounded and near-optimal distributed routing protocols.
   In MHWNs, the problem is substantially more complicated than the wired problem because of interference. Interference is exhibited at many levels, leading to effects such as uncontrolled contention and unfairness. The approach taken by the dissertation is to break the problem into multiple layers.
   Firstly, the dissertation proposes a Multi-commodity flow based routing model that produces interference-separated routes. Interactions between multiple routes are analyzed and effective objective function design is proposed that maximizes the throughputand minimizes the end-to-end delay.
   Nevertheless, such a model is directly employable only in smaller networks due to its NP-hard nature. The second contribution of the dissertation is to approximate the routing model to a polynomial time algorithm. A decomposition based approach is followed to formulate a low-complexity model by applying domain-specific heuristics.
   The simplistic scheduler assumptions in the routing model limits its accuracy in practice. A low-complexity scheduling model is proposed to capture the key scheduling interactions in CSMA based schedulers, like IEEE 802.11, and this model is integrated with the routing model.
   An approach to improve the accuracy of the scheduling model, while preserving a low run-time, is presented. “Interaction graphs” are proposed to capture the scheduling characteristics of CSMA based schedulers. Fairness in CSMA based scheduler for contention of the wireless channel is modeled using Renewal Theory and Continuous-time Markov Chain. Finally, throughput estimation models are proposed for various categories of interactions that have been identified in MHWNs.