多跳无线网络中具有端到端截止时间约束的在线调度与路由

《IEEE Transactions on Networking》：Online Scheduling and Routing With End-to-End Deadline Constraints in Multihop Wireless Networks

多跳无线网络中截止约束分组的在线调度算法设计，通过干扰图模型分析实现累积权重最大化，竞争比γ与R相关，适用于单跳无线及有线网络，仿真验证优于先前方法。

　　

摘要：

我们研究了在多跳无线网络中调度具有截止时间限制的数据包的问题。这些数据包具有任意的截止时间和权重，并且会到达不同的节点。我们的目标是设计在线准入、路由和调度算法，以最大化在截止时间内到达目的地的数据包的累积权重。在无线网络的一般干扰图模型下，我们提供了在线算法，其竞争强度为(γ,R)，即它们至少能够实现最优离线算法价值的1/γ部分，并且不会使容量超出R ≥ 1的倍数。特别是，当RC = Ω(ψ?log(ΔρL)/R)时，我们的算法可以实现γ = O(ψ?log(ΔρL)/R)的竞争强度。其中，ρ是数据包的最大权重与最小权重的比值，L是最长路径的长度，C是最小链路容量或信道数量。Δ是干扰图的最大度数，ψ?是局部团覆盖数。我们的结果可以直接应用于许多感兴趣的网络，例如，在单跳干扰网络中，ψ? = 2；在有线网络（无干扰）的情况下，ψ? = 1。我们进一步提供了下界证明，在许多情况下我们的结果是渐进最优的。最后，我们通过广泛的仿真证明了我们的算法相比现有方法有显著改进。

引言

由于实时应用的兴起，例如物联网（IoT）、车辆网络和其他信息物理系统，通信网络中实时流量的调度问题变得非常重要。在这些应用中，需要通过有线或无线网络传输对时间敏感的数据包。要满足这些数据包的截止时间要求，就需要摒弃传统的仅关注吞吐量的调度器。尽管在“单跳”无线网络[2]、[3]、[4]、[5]、[6]、[7]和多跳“有线”网络[9]、[10]、[11]中调度实时流量方面取得了最新进展，但多跳无线环境仍然非常具有挑战性。在这种环境中，决策空间要大得多，因为它涉及到数据包的传输路径、网络中任何时刻可用的非干扰链路集合，以及数据包在预定链路上传输的具体时间槽。在某个链路上调度数据包将影响未来其他链路的决策。此外，通常认为并非所有数据包都同等重要。考虑数据包之间的不同奖励（权重）使问题变得更加复杂。本文在多跳无线网络中调度具有截止时间限制的数据包方面取得了重要进展，目标是最大化在截止时间内到达目的地的数据包的总奖励。我们为这一问题提供了一个通用框架，用于设计一般干扰图下的在线算法。