Distributed Routing in Networks with Time-Variant Edge Capacities: A Modified Multicommodity Flow Approach 907 views

This research is focused on creating an efficient and effective network flow framework for applications in routing protocols for mobile, unicast communications networks with limited delay tolerance in urban canyons. Urban canyons are environments in which man-made objects interfere with the dependability of network reception. To account for fluctuations in reception, networks in this type of environment are modeled with time-variant edge capacities. To limit delays, algorithms implemented for these types of networks must be distributed. Specifically, we focus on modifying multicommodity flow problems to find routing protocols that can (1) effectively send flow through a network with time-varying edge capacities and (2) operate in a distributed setting. To achieve this, we developed candidate algorithms by both manipulating existing fully polynomial time approximation schemes for multicommodity flow for a time-varying setting and developing new algorithms that can produce a static, robust invariant allocation of flow. These candidate algorithms were initially evaluated through simulations in MATLAB. Then, promising algorithms were assessed through a theoretical analysis that validated performance and suitability observations made during the MATLAB simulations. Finally, a distributed implementation plan was developed.

MS (Master of Science)

multicommodity flow; stochastic subgradient method; communication networks; distributed algorithms; mobile networks; network optimization; wireless communication

English

All rights reserved (no additional license for public reuse)

2013-07-23