Analysis of Markov Chains and Algorithms for Ad-Hoc Networks

Ad-Hoc 网络的马尔可夫链和算法分析

• 批准号: 0515105
• 负责人: Dana Randall
• 金额: $ 20万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-07-15 至 2008-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0515105&HistoricalAwards=false
• 关键词: Analysis; Markov; Chains; Algorithms; Ad

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.

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