首页> 外文期刊>Distributed Computing >On the effect of the deployment setting on broadcasting in Euclidean radio networks
【24h】

On the effect of the deployment setting on broadcasting in Euclidean radio networks

机译:关于部署设置对欧几里得无线电网络中广播的影响

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

摘要

The paper studies broadcasting in radio networks whose stations are represented by points in the Euclidean plane (each station knows its own coordinates). In any given time step, a station can either receive or transmit. A message transmitted from station v is delivered to every station u at distance at most 1 from v, but u successfully hears the message if and only if v is the only station at distance at most 1 from u that transmitted in this time step. A designated source station has a message that should be disseminated throughout the network. All stations other than the source are initially idle and wake up upon the first time they hear the source message. It is shown in [17] that the time complexity of deterministic broadcasting algorithms depends on two parameters of the network, namely, its diameter (in hops) D and a lower bound d on the Euclidean distance between any two stations. The inverse of d is called the granularity of the network, denoted by g. Specifically, the authors of [17] present a deterministic broadcasting algorithm that works in time O (Dg) and prove that every broadcasting algorithm requires time. In this paper, we distinguish between the arbitrary deployment setting, originally studied in [17], in which stations can be placed everywhere in the plane, and the new grid deployment setting, in which stations are only allowed to be placed on a d-spaced grid. Does the latter (more restricted) setting provide any speedup in broadcasting time complexity? Although the O (Dg) broadcasting algorithm of [17] works under the (original) arbitrary deployment setting, it turns out that the lower bound remains valid under the grid deployment setting. Still, the above question is left unanswered. The current paper answers this question affirmatively by presenting a provable separation between the two deployment settings. We establish a tight lower bound on the time complexity of deterministic broadcasting algorithms under the arbitrary deployment setting proving that broadcasting cannot be completed in less than time. For the grid deployment setting, we develop a deterministic broadcasting algorithm that runs in time , thus breaking the linear dependency on g.
机译:该论文研究了无线电网络中的广播,其站点由欧几里得平面中的点表示(每个站点都知道自己的坐标)。在任何给定的时间步长中,站都可以接收或发送。从站v传输的消息将传递到每个与u距离不超过1的站u,但只有当v是在此时间步中传输的距离u的距离不超过1的唯一站时,u才能成功听到该消息。指定的源站具有应在整个网络中传播的消息。源以外的所有站最初都处于空闲状态,并在第一次听到源消息时唤醒。在[17]中表明,确定性广播算法的时间复杂度取决于网络的两个参数,即其直径(跳数)D和任意两个电台之间的欧几里得距离的下限d。 d的倒数称为网络的粒度,用g表示。具体来说,[17]的作者提出了一种确定性的广播算法,该算法在时间O(Dg)内起作用,并证明每种广播算法都需要时间。在本文中,我们区分了最初在[17]中研究的任意部署设置,在该部署中可以将站放置在飞机上的任何位置,而在新的网格部署设置中,只允许将站放置在d-间隔的网格。后者(更严格)的设置是否可以提高广播时间的复杂性?尽管[17]的O(Dg)广播算法在(原始)任意部署设置下工作,但事实证明,下限在网格部署设置下仍然有效。尽管如此,上述问题仍然没有答案。通过在两个部署设置之间提供可证明的分隔,当前论文肯定地回答了这个问题。我们在任意部署设置下确定性广播算法的时间复杂度上设置了一个严格的下限,证明了广播不能在短时间内完成。对于网格部署设置,我们开发了一种确定性的广播算法,该算法可以及时运行,从而打破了对g的线性依赖性。

著录项

  • 来源
    《Distributed Computing》 |2016年第6期|409-434|共26页
  • 作者单位

    Technion Israel Inst Technol, Fac Ind Engn & Management, Haifa, Israel;

    Northeastern Univ, Coll Comp & Informat Sci, Boston, MA 02115 USA;

    Weizmann Inst Sci, Dept Comp Sci & Appl Math, Rehovot, Israel;

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

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号