Analysis of Markov Chains and Algorithms for Ad-Hoc Networks

adhoc网络的马尔可夫链和算法分析dana Randall，首席研究员，佐治亚理工学院项目摘要本提案中概述的第一个研究方向涉及马尔可夫链设计和分析中的核心开放性问题。首先是改进用于分析收敛速率的分解技术。分解是一种强大的工具，可以将复杂的链分解成更易于分析的小块。接下来，该提案研究了列联表或满足规定行和列和约束的非负积分矩阵的新采样算法。我们计划探索细胞有界泛化，其中矩阵中的条目被进一步约束以满足给定的上界。这些表在统计学中有应用，并且细胞有界的情况包括经过充分研究的计算机科学应用，例如用给定度序列近似永久和采样二部图。第二个提出的方向是研究自组织网络上协议的行为。在互联网和网络图的背景下，具有已知度序列的采样图是一个重要的挑战，从业者试图在度满足推测幂律的图上开发有效的协议。另一个研究重点将是为传感器网络设计节能协议，以保证连通性和高效性能。自适应功率拓扑控制算法是在这种情况下建立网络的一种局部方法，但很少有人了解图的稀疏性和功率优化之间的权衡。此外，迄今为止的大多数分析都是基于无线占用空间的磁盘模型的理想化假设进行的。拟议的研究将探讨这些权衡和更现实的足迹假设。智力优势：马尔可夫链蒙特卡罗在许多学科中仍然是研究大型组合系统的流行方法。最近在分析它们的收敛率方面的发展已经为许多基本的采样问题建立了第一个严格的多项式时间算法。通过开发分析这些链的新方法和设计解决特定应用的新算法，仍有许多进一步研究的机会。虽然从数学角度很好地理解了收敛率，但仍然需要系统地推导其运行时间的多项式边界的新方法。剩下的挑战包括为各种应用开发新的采样算法，并设计新的工具来帮助分析。这仍然是理论计算机科学可以影响其他科学学科的最重要领域之一，因为目前大量的计算资源被花费在非严格的抽样启发式上。随着互联网和无线设备成为核心工具，自组织网络在算法领域日益突出。有很大的机会开发严格的协议，这些协议在广泛的操作假设下是健壮的。更广泛的影响：这项研究将通过教育部分得到补充。从2005年秋季开始，P.I.将主持DIMACS特别关注离散随机系统的组织委员会，专注于这一领域的跨学科研究。除了将相关领域的主要研究人员聚集在一起的典型讲习班之外，还将有促进更广泛影响的讲习班。一个这样的研讨会将为使用聪明的启发式的实践者提供拓展，希望合作将导致更快的严格算法的设计；另一门课程将专注于马尔可夫链在计算机科学其他领域的应用，包括用于研究互联网和网络图的谱方法。

Analysis of Markov Chains and Algorithms for Ad-Hoc NetworksDana Randall, Principal InvestigatorGeorgia Institute of TechnologyProject SummaryThe 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 wirelessfootprints. 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.