首页> 外文期刊>Networking, IEEE/ACM Transactions on >Understanding the Capacity Region of the Greedy Maximal Scheduling Algorithm in Multihop Wireless Networks
【24h】

Understanding the Capacity Region of the Greedy Maximal Scheduling Algorithm in Multihop Wireless Networks

机译:了解多跳无线网络中贪婪最大调度算法的容量区域

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

摘要

In this paper, we characterize the performance of an important class of scheduling schemes, called greedy maximal scheduling (GMS), for multihop wireless networks. While a lower bound on the throughput performance of GMS has been well known, empirical observations suggest that it is quite loose and that the performance of GMS is often close to optimal. In this paper, we provide a number of new analytic results characterizing the performance limits of GMS. We first provide an equivalent characterization of the efficiency ratio of GMS through a topological property called the local-pooling factor of the network graph. We then develop an iterative procedure to estimate the local-pooling factor under a large class of network topologies and interference models. We use these results to study the worst-case efficiency ratio of GMS on two classes of network topologies. We show how these results can be applied to tree networks to prove that GMS achieves the full capacity region in tree networks under the $K$ -hop interference model. Then, we show that the worst-case efficiency ratio of GMS in geometric unit-disk graphs is between ${1 over 6}$ and ${1 over 3}$.
机译:在本文中,我们描述了针对多跳无线网络的一类重要调度方案的性能,称为贪婪最大调度(GMS)。虽然众所周知GMS的吞吐量性能有一个下限,但经验观察表明GMS的性能相当宽松,而且GMS的性能通常接近最佳状态。在本文中,我们提供了许多表征GMS性能极限的新分析结果。我们首先通过称为网络图的局部池因子的拓扑属性来提供GMS效率比的等效表征。然后,我们开发一种迭代过程来估计大型网络拓扑和干扰模型下的本地池因子。我们使用这些结果来研究GMS在两类网络拓扑上的最坏情况效率比。我们展示了如何将这些结果应用于树形网络,以证明GMS在$ K $ -hop干扰模型下实现了树形网络的全部容量区域。然后,我们表明,几何单位圆图中的GMS的最坏情况效率比在$ {1 over 6} $和$ {1 over 3} $之间。

著录项

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号