• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Information Theory, IEEE Transactions on >Location-Aided Fast Distributed Consensus in Wireless Networks
【24h】

Location-Aided Fast Distributed Consensus in Wireless Networks

机译：无线网络中的位置辅助快速分布式共识

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Existing works on distributed consensus explore linear iterations based on reversible Markov chains, which contribute to the slow convergence of the algorithms. It has been observed that by overcoming the diffusive behavior of reversible chains, certain nonreversible chains lifted from reversible ones mix substantially faster than the original chains. In this paper, the idea of Markov chain lifting is studied to accelerate the convergence of distributed consensus, and two general pseudoalgorithms are presented. These pseudoalgorithms are then instantiated through a class of location-aided distributed averaging (LADA) algorithms for wireless networks, where nodes' coarse location information is used to construct nonreversible chains that facilitate distributed computing and cooperative processing. Our first LADA algorithm is designed for grid networks; for a $ktimes k$ grid network, it achieves an $epsilon $-averaging time of $O(klog (epsilon ^{-1}))$. Based on this algorithm, in a wireless network with transmission range $r$, an $epsilon $-averaging time of $O(r^{-1}log (epsilon ^{-1}))$ can be attained through a centralized algorithm. Subsequently, a distributed LADA algorithm is presented, achieving the same scaling law in averaging time as the centralized scheme in wireless networks for all $r$ satisfying the connectivity requirement; the constructed chain also attains the optimal scaling law in terms of an important mixing metric, the fill time, in its class. Finally, a cluster-based LADA algorith-n-nm is proposed, which, requiring no central coordination, provides the additional benefit of reduced message complexity compared with the distributed LADA algorithm.
机译：现有的关于分布式共识的工作探索了基于可逆马尔可夫链的线性迭代，这有助于算法的缓慢收敛。已经观察到，通过克服可逆链的扩散行为，从可逆链提升的某些不可逆链的混合比原始链的混合快得多。本文研究了马尔可夫链提升的思想，以加速分布式共识的收敛，并提出了两种通用的伪算法。然后，通过用于无线网络的一类位置辅助分布式平均（LADA）算法实例化这些伪算法，其中，节点的粗略位置信息用于构造不可逆链，从而促进分布式计算和协作处理。我们的第一个LADA算法是为网格网络设计的。对于$ ktimes k $网格网络，它的$ epsilon $平均时间为$ O（klog（epsilon ^ {-1}））$。基于此算法，在传输范围为$ r $的无线网络中，可以通过集中式计算获得$ epsilon $的平均时间$ O（r ^ {-1} log（epsilon ^ {-1}））$算法。随后，提出了一种分布式LADA算法，对于所有满足连接性要求的$ r $，在平均时间上都实现了与集中式方案相同的比例定律。就其重要的混合指标（填充时间）而言，构建的链还可以获得最佳的比例定律。最后，提出了一种基于集群的LADA算法-n-nm，与分布式LADA算法相比，该算法不需要中央协调，还具有降低消息复杂度的额外优势。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号