• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Parallel and Distributed Systems, IEEE Transactions on >Minimum Latency Broadcast Scheduling in Duty-Cycled Multihop Wireless Networks
【24h】

Minimum Latency Broadcast Scheduling in Duty-Cycled Multihop Wireless Networks

机译：占空比多跳无线网络中的最小延迟广播调度

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

摘要

Broadcast is an essential and widely used operation in multihop wireless networks. Minimum latency broadcast scheduling (MLBS) aims to find a collision-free scheduling for broadcast with the minimum latency. Previous work on MLBS mostly assumes that nodes are always active, and, thus, is not suitable for duty-cycled scenarios. In this paper, we investigate the MLBS problem in duty-cycled multihop wireless networks (MLBSDC problem). We prove both the one-to-all and the all-to-all MLBSDC problems to be NP-hard. We propose a novel approximation algorithm called OTAB for the one-to-all MLBSDC problem, and two approximation algorithms called UTB and UNB for the all-to-all MLBSDC problem under the unit-size and the unbounded-size message models, respectively. The approximation ratios of the OTAB, UTB, and UNB algorithms are at most 17vert Tvert, 17vert Tvert +20, and (Delta +22)vert Tvert, respectively, where vert Tvert denotes the number of time slots in a scheduling period, and Delta denotes the maximum node degree of the network. The overhead of our algorithms is at most constant times as large as the minimum overhead in terms of the total number of transmissions. We also devise a method called Prune to further reduce the overhead of our algorithms. Extensive simulations are conducted to evaluate the performance of our algorithms.
机译：广播是多跳无线网络中必不可少且广泛使用的操作。最小等待时间广播调度（MLBS）旨在找到具有最小等待时间的广播的无冲突调度。以前关于MLBS的工作主要假设节点始终处于活动状态，因此不适合于占空比大的场景。在本文中，我们研究了占空比多跳无线网络中的MLBS问题（MLBSDC问题）。我们证明了所有MLBSDC问题和所有MLBSDC问题都是NP难题。我们分别针对单位大小和无边界消息模型分别提出了一种针对OTBS的新型近似算法OTAB，针对全部MLBSDC提出了两种称为UTB和UNB的近似算法。 OTAB，UTB和UNB算法的近似比率分别最多为17vert Tvert，17vert Tvert +20和（Delta +22）vert Tvert，其中vert Tvert表示调度周期中的时隙数，而Delta表示网络的最大节点度。就传输总数而言，我们算法的开销最多是最小开销的恒定时间。我们还设计了一种称为Prune的方法来进一步减少算法的开销。进行了广泛的仿真，以评估我们算法的性能。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号