• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Parallel and Distributed Systems >Efficient distributed low-cost backbone formation for wireless networks
【24h】

Efficient distributed low-cost backbone formation for wireless networks

机译：用于无线网络的高效分布式低成本骨干网

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

摘要

Backbone has been used extensively in various aspects (e.g., routing, route maintenance, broadcast, scheduling) for wireless ad hoc or sensor networks recently. Previous methods are mostly designed to minimize the size of the backbone. However, in many applications, it is desirable to construct a backbone with small cost when each wireless node has a cost of being in the backbone. In this paper, we first show that previous methods specifically designed to minimize the backbone size may produce a backbone with large cost. Then, an efficient distributed method to construct a weighted backbone with low cost is proposed. We prove that the total cost of the constructed backbone is within a small constant factor of the optimum for homogeneous networks when either the nodes' costs are smooth (i.e., the maximum ratio of costs of adjacent nodes is bounded) or the network maximum node degree is bounded. We also show that, with a small modification, the backbone is efficient for unicast: the total cost (or hop) of the least cost (or hop) path connecting any two nodes using backbone is no more than three (or four) times the least cost (or hop) path in the original communication graph. Our theoretical. results are corroborated by our simulation studies. Finally, we discuss several possible ad hoc network applications of our proposed backbone formation algorithms.
机译：最近，骨干网已经广泛用于无线自组织或传感器网络的各个方面（例如，路由，路由维护，广播，调度）。先前的方法主要是为了最小化骨干网的大小而设计的。然而，在许多应用中，当每个无线节点具有位于骨干中的成本时，期望以较小的成本来构造骨干。在本文中，我们首先表明，专门设计用于最小化骨干大小的先前方法可能会产生成本高昂的骨干。然后，提出了一种高效的低成本构建加权主干的分布式方法。我们证明，当节点的成本是平滑的（即，相邻节点的最大成本比率是有界的）或网络的最大节点度时，构造的骨干网的总成本在同构网络最优值的较小恒定因子之内有界。我们还显示，通过少量修改，骨干网对于单播是有效的：使用骨干网连接任何两个节点的最小成本（或跃点）路径的总成本（或跃点）不超过骨干的三（或四）倍。原始通讯图中的最低成本（或跃点）路径。我们的理论。我们的仿真研究证实了这一结果。最后，我们讨论了我们提出的骨干网形成算法的几种可能的ad hoc网络应用。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号