无线网络中分布式贪婪调度算法的调度效率

我们考虑在简单冲突约束下无线网络中的分布式调度问题。我们将分布式调度算法的效率定义为能够使得在分布式调度策略下的吞吐量至少等于效率乘以在集中式策略下能够实现的最大吞吐量的最大数值（比例）。对于一般的干扰模型，我们首先假设所有的流量只使用网络的一跳，证明了分布式调度算法的效率下限。我们还证明了这个下限是紧的，意味着对于任何大于下限的比例，我们可以找到一个拓扑和一个到达率向量，使得在贪婪调度策略下网络是不稳定的。然后我们将结果推广到更一般的多跳流量场景，并通过引入优先级或调节器来证明类似的调度效率结果可以在基本贪婪调度算法中建立。