首页> 外文期刊>Algorithmica >Faster Deterministic Communication in Radio Networks
【24h】

Faster Deterministic Communication in Radio Networks

机译:无线电网络中更快的确定性通信

获取原文
获取原文并翻译 | 示例

摘要

We study the communication primitives of broadcasting (one-to-all communication) and gossiping (all-to-all communication) in known topology radio networks, I.e., where for each primitive the schedule of transmissions is precomputed based on full knowledge about the size and the topology of the network. We show that gossiping can be completed in O(D + ((△log n)/(log△-log log n)) time units in any radio network of size n, diameter D, and maximum degree △ = Ω(log n). This is an almost optimal schedule in the sense that there exists a radio network topology, specifically a △ -regular tree, in which the radio gossiping cannot be completed in less than Ω(D +(△log n)/(log △)) units of time. Moreover, we show a D + O ((log~3n)/(log log n)) schedule for the broadcast task. Both our transmission schemes significantly improve upon the currently best known schedules by Gasieniec, Peleg, and Xin (Proceedings of the 24th Annual ACM SIGACT-SIGOPS PODC, pp. 129-137, 2005), I.e., a O(D +△ log n) time schedule for gossiping and a D + O(log~3 n) time schedule for broadcast. Our broadcasting schedule also improves, for large D, a very recent O(D + log~2 n) time broadcasting schedule by Kowalski and Pelc.
机译:我们研究了已知拓扑无线电网络中广播(单向通信)和八卦(全向通信)的通信原语,即,对于每个原语,都基于对大小的充分了解来预先计算传输时间表以及网络拓扑。我们证明在任何大小为n,直径为D,最大度为△=Ω(log n的无线电网络)中,闲聊可以以O(D +((△log n)/(log△-log log log n))时间单位完成。 )。就存在无线电网络拓扑结构(尤其是△-规则树)的意义而言,这几乎是一个最佳调度,在该拓扑中,无法以小于Ω(D +(△log n)/(log△)的速率完成无线闲聊。 ))的时间单位。此外,我们显示了广播任务的D + O((log〜3n)/(log log n))时间表。我们的两种传输方案都比Gasieniec,Peleg,和Xin(第24届ACM SIGACT-SIGOPS PODC年度会议论文集,第129-137页,2005年),即,闲聊时间为O(D +△log n),D + O(log〜3 n)时间对于大型D,我们的广播时间表还改进了Kowalski和Pelc的最近O(D + log〜2 n)时间广播时间表。

著录项

  • 来源
    《Algorithmica》 |2009年第2期|226-242|共17页
  • 作者单位

    AG Genominformatik, Technische Fakultaet, Universitaet Bielefeld, Bielefeld, Germany;

    Department of Informatics, The University of Bergen, P.B. 7800, Bergen 5020, Norway;

    Simula Research Laboratory, P.B. 134, Lysaker 1325, Norway;

  • 收录信息 美国《科学引文索引》(SCI);美国《工程索引》(EI);
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

    centralized radio networks; broadcasting; gossiping;

    机译:集中式无线电网络;广播;闲聊;

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号