首页> 外文会议>Distributed computing >Opportunistic Information Dissemination in Mobile Ad-hoc Networks: The Profit of Global Synchrony
【24h】

Opportunistic Information Dissemination in Mobile Ad-hoc Networks: The Profit of Global Synchrony

机译:移动自组织网络中的机会主义信息传播:全球同步的收益

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

摘要

The topic of this paper is the study of Information Dissemination in Mobile Ad-hoc Networks by means of deterministic protocols. We characterize the connectivity resulting from the movement, from failures and from the fact that nodes may join the computation at different times with two values, α and β, so that, within α time slots, some node that has the information must be connected to some node without it for at least β time slots. The protocols studied are classified into three classes: oblivious (the transmission schedule of a node is only a function of its ID), quasi-oblivious (the transmission schedule may also depend on a global time), and adaptive. The main contribution of this work concerns negative results. Contrasting the lower and upper bounds derived, interesting complexity gaps among protocol-classes are observed. More precisely, in order to guarantee any progress towards solving the problem, it is shown that β must be at least n - 1 in general, but that β ∈ Ω{n~2/log n) if an oblivious protocol is used. Since quasi-oblivious protocols can guarantee progress with β ∈ O(n), this represents a significant gap, almost linear in β, between oblivious and quasi-oblivious protocols. Regarding the time to complete the dissemination, a lower bound of Ω(nα + n~3/log n) is proved for oblivious protocols, which is tight up to a polylogarithmic factor because a constructive O(nα + n~3 log n) upper bound exists for the same class. It is also proved that adaptive protocols require Ω(nα + n~2), which is optimal given that a matching upper bound can be proved for quasi-oblivious protocols. These results show that the gap in time complexity between oblivious and quasi-oblivious, and hence adaptive, protocols is almost linear. This gap is what we call the profit of global synchrony, since it represents the gain the network obtains from global synchrony with respect to not having it.
机译:本文的主题是通过确定性协议研究移动自组织网络中的信息传播。我们描述了由于运动,故障以及节点可能在不同时间以两个值α和β参加计算的事实而导致的连通性,因此,在α时隙内,某些具有信息的节点必须连接到一些没有它的节点至少有β个时隙。研究的协议分为三类:遗忘的(节点的传输调度仅是其ID的函数),准遗忘的(传输调度也可能取决于全局时间)和自适应的。这项工作的主要贡献涉及负面结果。与导出的上下限相反,在协议类之间观察到有趣的复杂性差距。更确切地说,为了保证解决该问题的任何进展,表明一般而言,β必须至少为n-1,但是如果使用了遗忘协议,则β∈Ω{n〜2 / log n)。由于准遗忘协议可以保证随着β∈O(n)的进行,因此这表示了遗忘协议和准遗忘协议之间的显着差距,即β几乎是线性的。关于完成传播的时间,对于遗忘的协议证明了Ω(nα+ n〜3 / log n)的下限,由于具有建设性的O(nα+ n〜3 log n),它被限制为一个多对数因子。同一类存在上限。还证明了自适应协议需要Ω(nα+ n〜2),这是最佳的,因为可以为准遗忘协议证明匹配的上限。这些结果表明,遗忘协议和准遗忘协议(因此是自适应协议)之间的时间复杂度差距几乎是线性的。这个差距就是我们所说的全球同步收益,因为它代表了网络从全球同步中获得的收益。

著录项

  • 来源
    《Distributed computing》|2010年|p.374-388|共15页
  • 会议地点 Cambridge MA(US);Cambridge MA(US)
  • 作者单位

    Institute IMDEA Networks, Leganes, Spain,LADyR, GSyC, Universidad Rey Juan Carlos, Mostoles, Spain;

    LIP6, Universite Pierre et Marie Curie - Paris 6, Paris, France;

    Department of Computer Science, Rutgers University, Piscataway, NJ, USA,LADyR, GSyC, Universidad Rey Juan Carlos, Mostoles, Spain;

    Department of Computer Science, Technion, Haifa, Israel;

  • 会议组织
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类 计算机的应用;
  • 关键词

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号