论文标题
与单位状态反馈的吞吐量最佳分散调度，用于一类排队系统
Throughput Optimal Decentralized Scheduling with Single-bit State Feedback for a Class of Queueing Systems
论文作者
论文摘要
由资源挑战的无线互联网（IoT）的中等访问控制动机（IoT），我们考虑了排队调度的问题，并减少了队列状态信息。特别是，我们考虑了具有$ n $传感器节点的时间间隔的调度模型，具有配对依赖性，以便节点$ i $和$ i + 1，〜0 <i <n $无法一起传输。我们制定了新的吞吐量 - 最佳调度策略，只需要我们称为“基于排队的非空格（QNB）策略”的每个队列中空的空位。我们提出了一种策略剪接技术，以结合小型网络的调度策略，以构建大型网络的吞吐量 - 最佳策略，其中一些也旨在低延迟。对于$ n = 3，存在$ QU的最佳QNB调度策略。但是，我们表明，对于$ n> 4，$没有QNB策略在容量区域的所有到达率向量上都是最佳的sum-quesue长度。 然后，我们将结果扩展到更一般的干扰约束类别，我们称之为群集（COC）冲突图。我们考虑了两种类型的COC网络，即集合线（LAOC）和恒星（SOC）网络的线性阵列。我们为这些类别的网络制定了QNB策略，研究其稳定性和延迟属性，并提出和分析技术以减少在整个网络中散布的状态信息量以进行调度。在SOC环境中，我们提出了一个吞吐量的策略，该策略仅使用网络中节点可以通过在频道上感测活动（或缺乏）信息来收集的信息。我们的吞吐量 - 最佳性结果依赖于两个新的参数：Lyapunov漂移引理特别适应了排队长度 - 不可思议的策略，以及用于表现出强稳定性的优先排队分析。
Motivated by medium access control for resource-challenged wireless Internet of Things (IoT), we consider the problem of queue scheduling with reduced queue state information. In particular, we consider a time-slotted scheduling model with $N$ sensor nodes, with pair-wise dependence, such that Nodes $i$ and $i + 1,~0 < i < N$ cannot transmit together. We develop new throughput-optimal scheduling policies requiring only the empty-nonempty state of each queue that we term Queue Nonemptiness-Based (QNB) policies. We propose a Policy Splicing technique to combine scheduling policies for small networks in order to construct throughput-optimal policies for larger networks, some of which also aim for low delay. For $N = 3,$ there exists a sum-queue length optimal QNB scheduling policy. We show, however, that for $N > 4,$ there is no QNB policy that is sum-queue length optimal over all arrival rate vectors in the capacity region. We then extend our results to a more general class of interference constraints that we call cluster-of-cliques (CoC) conflict graphs. We consider two types of CoC networks, namely, Linear Arrays of Cliques (LAoC) and Star-of-Cliques (SoC) networks. We develop QNB policies for these classes of networks, study their stability and delay properties, and propose and analyze techniques to reduce the amount of state information to be disseminated across the network for scheduling. In the SoC setting, we propose a throughput-optimal policy that only uses information that nodes in the network can glean by sensing activity (or lack thereof) on the channel. Our throughput-optimality results rely on two new arguments: a Lyapunov drift lemma specially adapted to policies that are queue length-agnostic, and a priority queueing analysis for showing strong stability.
