• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>International journal of ad hoc and ubiquitous computing >The impact of mobility on the time complexity for deterministic broadcasting in radio networks
【24h】

The impact of mobility on the time complexity for deterministic broadcasting in radio networks

机译：移动性对无线电网络中确定性广播的时间复杂度的影响

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

摘要

We study the time complexity for deterministic broadcasting algorithms in mobile radio networks. The broadcast operation consists of a source node successfully communicating its message to every other node. In multi-hop radio networks such as MANETs, the message may traverse multiple other nodes. Nodes have no prior knowledge besides the number n of nodes in the network and its diameter D. The problem we address has been extensively studied for static networks. Our work quantifies the impact of mobility. We consider three families of graphs: undirected graphs of constant contention degree, undirected graphs of non-constant contention degree and directed graphs of non-constant contention degree. We prove the lower bounds of Ω(n log n) time slots for the first family, Ω( n~2/D~2 logD + D) time slots for the second and Ω(n~2 log D + n log D) for the third. At the time of writing, the corresponding tightest lower bounds derived in the static case are, respectively, Ω(D log n), Ω (n log n/log n/D) and Ω(n log D).
机译：我们研究了移动无线电网络中确定性广播算法的时间复杂度。广播操作由一个源节点成功地将其消息传递给其他每个节点组成。在诸如MANET的多跳无线网络中，消息可能会遍历多个其他节点。除了网络中的节点数n及其直径D外，节点没有任何先验知识。我们针对静态网络已广泛研究了这个问题。我们的工作量化了流动性的影响。我们考虑三类图：恒定竞争程度的无向图，非恒定竞争程度的无向图和非恒定竞争程度的有向图。我们证明了第一个家庭的Ω（n log n）时隙的下界，第二个家庭的Ω（n〜2 / D〜2 logD + D）时隙和Ω（n〜2 log D + n log D）的下限第三。在撰写本文时，在静态情况下得出的相应最严格的下限分别是Ω（D log n），Ω（n log n / log n / D）和Ω（n log D）。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号