Online scheduling and routing with end-to-end deadline constraints in multihop wireless networks
Online scheduling and routing with end-to-end deadline constraints in multihop wireless networks
复制标题
多跳无线网络中具有端到端期限约束的在线调度和路由
DOI：
10.1145/3492866.3549729
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Ghaderi, Javad
中科院分区：
文献类型：
--
作者：
Tsanikidis, Christos;Ghaderi, Javad
我们考虑在多跳无线网络中调度时限约束的数据包。具有任意截止日期和权重的数据包到达并被发送到不同的节点。目标是设计在线准入、路由和调度算法，以最大限度地提高在截止日期内到达目的地的数据包的累积权重。在无线网络的一般干扰图模型下，我们提供了（γ， R）竞争的在线算法，即它们至少达到最优离线算法值的1/γ分数，并且不超过容量超过一个因子R≥1。具体来说，当RC = Ω（Ψ*log（ΔρL））时，我们的算法可以实现γ = O（Ψ*log（ΔρL）/R），其中ρ为数据包最大权值与最小权值的比值，Lis为数据包最长路由的长度，C为最小链路容量或通道数。其中Δ为最大值degreeandΨ*为干涉图的局部团盖数。我们的结果直接转化为许多感兴趣的网络，例如，在单跳干扰网络中，Ψ* =2，在有线网络（无干扰）的情况下，Ψ* =1。我们进一步提供了下界，表明我们的结果在许多情况下是渐近最优的。最后，我们提出了大量的模拟，表明我们的算法比以前的方法提供了显着的改进。
We consider scheduling deadline-constrained packets in multihop wireless networks. Packets with arbitrary deadlines and weights arrive at and are destined to different nodes. The goal is to design online admission, routing, and scheduling algorithms in order to maximize the cumulative weight of packets that reach their destinations within their deadlines. Under a general interference graph model of the wireless network, we provide online algorithms that are (γ, R)-competitive, i.e., they achieve at least 1/γfraction of the value of the optimal offline algorithm, and do not exceed the capacity by more than a factor R ≥ 1. In particular, our algorithm can achieveγ = O(Ψ*log(ΔρL)/R) when RC = Ω(Ψ*log(ΔρL)), whereρis the ratio of maximum weight to minimum weight of packets,Lis the length of the longest route of packets, and C is the minimum link capacity or the number of channels. Here, Δ is themaximum degreeandΨ*is thelocal clique cover numberof the interference graph. Our results translate directly to many networks of interest, for example, in one-hop interference networks,Ψ* =2, and in the case of wired networks (no interference),Ψ* =1. We further provide lower bounds that show that our results are asymptotically optimal in many settings. Finally, we present extensive simulations that show our algorithms provide significant improvement over the prior approaches.
登录
查看更多内容
用于支持多跳网络中端到端硬期限的时空路由
DOI：
--
发表时间：
2019
期刊：
Performance evaluation (Print)
影响因子：
--
作者：
Xin Liu;Weichang Wang;Lei Ying
通讯作者：
Lei Ying
无线传感器网络的端到端延迟约束路由和调度
DOI：
10.1109/icc.2011.5962517
发表时间：
2011
期刊：
2011 IEEE International Conference on Communications (ICC)
影响因子：
--
作者：
Qing Wang;Pingyi Fan;D. Wu;K. Letaief
通讯作者：
K. Letaief
当最大独立集和最大匹配算法在亚线性时间内运行时
DOI：
10.4230/lipics.icalp.2019.17
发表时间：
2019
期刊：
ArXiv
影响因子：
--
作者：
Sepehr Assadi;Shay Solomon
通讯作者：
Shay Solomon
图的局部团覆盖
DOI：
--
发表时间：
2012
期刊：
影响因子：
--
作者：
R. Javadi;Zeinab Maleki;B. Omoomi
通讯作者：
B. Omoomi
具有端到端时限约束的多跳网络吞吐量最优分散调度：II 存在干扰的无线网络
DOI：
--
发表时间：
2017
期刊：
arXiv.org
影响因子：
--
作者：
Rahul Singh;P. Kumar;E. Modiano
通讯作者：
E. Modiano