|
|
|
|
|
|
|
Interference and collisions greatly limit the throughput of mesh networks that used contention-based MAC protocols such as 802.11. Significantly higher throughput is achievable if transmissions are scheduled. However, traditional methods to compute such schedules are so computationally complex that they can only be used on small networks. This talk presents results from several recent works on techniques to efficiently compute capacity optimizing schedules. The technique consists of three layers of optimization. The inner-most optimization computes an estimate of the capacity. This optimization is a standard linear or nonlinear constrained optimization. The middle iteration uses the Lagrange multipliers from the inner iteration to modify the space over which inner optimization is performed. This is a graph theoretic optimization known as the maximum weighted independent set problem. The outer-most optimization uses the Lagrange multipliers from the inner-most optimization to find optimal routes. This optimization requires solving several least cost paths problems and several maximum weighted independent set problems. The techniques presented allow optimal schedules and routes to be computed for networks with hundreds and perhaps even a few thousand links, and thus this approach scales to the size of current and planned urban mesh networks. The techniques have been verified on networks generated with a realistic urban propagation simulator, hence, the findings are directly applicable to the networks planned in urban areas such as Philadelphia and San Francisco. In this setting, it is shown that optimal scheduling increases the capacity by between a factor of four and ten over 802.11 CSMA/CA, depending on the density of the mesh routers and gateways.Interference and collisions greatly limit the throughput of mesh networks that used contention-based MAC protocols such as 802.11. Significantly higher throughput is achievable if transmissions are scheduled. However, traditional methods to compute such schedules are so computationally complex that they can only be used on small networks. This talk presents results from several recent works on techniques to efficiently compute capacity optimizing schedules. The technique consists of three layers of optimization. The inner-most optimization computes an estimate of the capacity. This optimization is a standard linear or nonlinear constrained optimization. The middle iteration uses the Lagrange multipliers from the inner iteration to modify the space over which inner optimization is performed. This is a graph theoretic optimization known as the maximum weighted independent set problem. The outer-most optimization uses the Lagrange multipliers from the inner-most optimization to find optimal routes. This optimization requires solving several least cost paths problems and several maximum weighted independent set problems. The techniques presented allow optimal schedules and routes to be computed for networks with hundreds and perhaps even a few thousand links, and thus this approach scales to the size of current and planned urban mesh networks. The techniques have been verified on networks generated with a realistic urban propagation simulator, hence, the findings are directly applicable to the networks planned in urban areas such as Philadelphia and San Francisco. In this setting, it is shown that optimal scheduling increases the capacity by between a factor of four and ten over 802.11 CSMA/CA, depending on the density of the mesh routers and gateways. Bio In 1999, Stephan Bohacek received his Ph.D. in Electrical Engineering from the University of Southern California. His area of specialized was Control Theory. From 1999 to 2002, Dr. Bohacek was with the Department of Mathematics at the University of Southern California. Since 2002, Dr. Bohacek has been an assistant professor with the Department of Electrical and Computer Engineering at the University of Delaware. Dr. Bohacek's current research focuses on wireless networks, especially modeling, simulation, routing, and scheduling for multihop wireless networks. His current interests also include network security and software engineering for networking protocols.
|
|
|
|
|
|
|
|