Analysis of Markov Chains and Algorithms for Ad-Hoc Networks

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

Analysis of Markov Chains and Algorithms for Ad-Hoc Networks Dana Randall, Principal Investigator Georgia Institute of Technology Project Summary The first research direction outlined in this proposal concerns central open questions in the design and analysis of Markov chains. The first is to improve the decomposition technique for analyzing convergence rates. Decomposition is a powerful tool for breaking a complicated chain into smaller pieces that are more amenable to analysis. Next, the proposal examines new sampling algorithms for contingency tables, or non-negative integral matrices that satisfy prescribed row and column sum constraints. We plan to explore the cell-bounded generalization where the entries in the matrices are further constrained to satisfy given upper bounds. These tables have applications in statistics, and the cell-bounded case includes well-studied computer science applications such as approximating the permanent and sampling bipartite graphs with given degree sequences. The second proposed direction is studying the behavior of protocols on ad hoc networks. Sampling graphs with known degree sequences is an important challenge in the context of the Internet and web graphs, where practitioners are trying to develop efficient protocols on graphs whose degrees satisfy conjectured power laws. An additional research focus will be to design power-efficient protocols for sensor networks that guarantee connectedness and efficient performance. The Adaptive Power Topology Control Algorithm is a local approach to building up networks in this context, but little is understood about the tradeoffs between the sparsity of the graphs and the optimization of power. Moreover, most of the analysis to date has been done only with the idealized assumption of the disk model for wireless footprints. The proposed research will explore these tradeoffs and more realistic footprint assumptions. Intellectual merit: Markov chain Monte Carlo remains a popular method in many disciplines for studying large combinatorial systems. Recent developments for analyzing their convergence rates have established the first rigorous, polynomial time algorithms for many fundamental sampling problems. There remain many opportunities for furthering this research, both by developing new methods for analyzing these chains and designing new algorithms to address particular applications. While convergence rates are well understood from a mathematical perspective, new methods for systematically deriving polynomial bounds on their running times are still required. Remaining challenges include developing new sampling algorithms for various applications and designing new tools to aid their analysis. This remains one of the foremost areas where theoretical computer science can impact other scientific disciplines because of the large amounts of computational resources currently be expended on nonrigorous sampling heuristics. Ad hoc networks are gaining prominence in the field of algorithms as the Internet and wireless devices become central tools. There is great opportunity for developing rigorous protocols that are robust under a wide set of operational assumptions. Broader impact: This research will be supplemented through an educational component. Starting in Fall 2005, the P.I. will be chairing the organizing committee of a DIMACS special focus on Discrete Random Systems, concentrating on this area of interdisciplinary research. In addition to the typical workshops bringing together leading researchers in the relevant areas, there will also be workshops promoting broader impact. One such workshop will provide an outreach to practitioners using clever heuristics in the hopes that collaborations will lead to the design of faster rigorous algorithms; another will focus on applications of Markov chains in other areas of computer science, including spectral methods used to study the Internet and web graphs.