Throughput Optimal Decentralized Scheduling of Multi-Hop Networks with End-to-End Deadline Constraints: II Wireless Networks with Interference
Throughput Optimal Decentralized Scheduling of Multi-Hop Networks with End-to-End Deadline Constraints: II Wireless Networks with Interference
复制标题
具有端到端时限约束的多跳网络吞吐量最优分散调度：II 存在干扰的无线网络
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
E. Modiano
中科院分区：
文献类型：
--
作者：
Rahul Singh;P. Kumar;E. Modiano
考虑服务于多个流的多跳无线网络，其中无线链路干扰约束由链路干扰图描述。对于这样的网络，我们设计的路由调度策略，最大限度地提高网络的端到端的及时吞吐量。流$f$的及时吞吐量被定义为流$f$的分组在其截止期限内到达其目的地节点$d_f$的平均速率。
我们的政策有几个令人惊讶的特点。首先，我们表明，一个单独的数据包，是目前在一个无线节点$iin V$的最佳路由调度决策仅仅是一个函数，它的位置，和“年龄”。因此，无线节点$i$不需要“全局”网络状态的知识以便最大化及时吞吐量。我们注意到，相比之下，在背压路由策略下，一个节点只需要知道它的邻居队列长度，以保证最大的稳定性，因此是分散的。关键的区别在于，在我们的设置中，一旦数据包的“年龄”超过了最后期限，数据包就会失去效用，从而使优化及时吞吐量的任务比确保网络稳定性更具挑战性。当然，由于这一关键区别，最大化及时吞吐量所涉及的决策过程也比确保网络范围的队列稳定所涉及的决策过程复杂得多。鉴于此，我们的结果有些令人惊讶。
Consider a multihop wireless network serving multiple flows in which wireless link interference constraints are described by a link interference graph. For such a network, we design routing-scheduling policies that maximize the end-to-end timely throughput of the network. Timely throughput of a flow $f$ is defined as the average rate at which packets of flow $f$ reach their destination node $d_f$ within their deadline.
Our policy has several surprising characteristics. Firstly, we show that the optimal routing-scheduling decision for an individual packet that is present at a wireless node $iin V$ is solely a function of its location, and "age". Thus, a wireless node $i$ does not require the knowledge of the "global" network state in order to maximize the timely throughput. We notice that in comparison, under the backpressure routing policy, a node $i$ requires only the knowledge of its neighbours queue lengths in order to guarantee maximal stability, and hence is decentralized. The key difference arises due to the fact that in our set-up the packets loose their utility once their "age" has crossed their deadline, thus making the task of optimizing timely throughput much more challenging than that of ensuring network stability. Of course, due to this key difference, the decision process involved in maximizing the timely throughput is also much more complex than that involved in ensuring network-wide queue stabilization. In view of this, our results are somewhat surprising.