文章总结： 本文针对多跳无线网络中随机业务与端到端截止期约束下的调度问题，提出minos与gms-pf两种算法。minos通过线性规划联合概率转发与无干扰链路选择实现近最优性能，gms-pf以贪心极大独立集降低计算复杂度并支持分布式实现。实验表明两种算法在有限资源下优于现有方法，适应多种随机业务与网络拓扑。
综合评分： 80
文章分类： 其他
每周文章分享-278
网络与安全实验室
2026年9月29日 23:59
江苏
在小说阅读器读本章
去阅读
在公众号小说中沉浸阅读
每周文章分享
2026.09.28至2026.10.04
标题：Scheduling Stochastic Traffic With End-to-End Deadlines in Multi-Hop Wireless Networks
期刊：IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 25, NO. 7, JULY 2026
作者：Christos Tsanikidis and Javad Ghaderi.
分享人：河海大学——张月
01.
研究背景
多跳无线网络已成为支撑实时视频、车联网和物联网等时延敏感应用的重要通信基础。然而，这些网络面临着随机业务到达与链路相互干扰下的数据包按时交付问题。数据包需要经过多跳转发才能到达目的节点，一旦超过端到端截止期，便会失去应用价值。现有调度方法主要关注吞吐量，或其性能保证随路由长度增加而下降，或依赖无限带宽等渐近假设，难以适用于实际有限资源场景。本文提出了两种调度算法，以最大化截止期内成功交付数据包的加权总和。首先，提出了一种多跳干扰感知近最优调度（MINOS）算法，利用线性规划引导概率转发与无干扰链路集合的随机选择，在满足一定信道数量等条件时实现近最优性能。其次，提出了一种结合概率转发的贪心极大调度（GMS-PF）算法，通过贪心选择可并发传输的链路集合降低计算复杂度，并支持分布式实现，在有限资源条件下提供具有理论保证的调度性能。
02.
关键技术
在本文中，提出了一种面向随机业务和严格端到端截止期的多跳无线网络联合路由与调度方法，以最大化按时交付数据包的加权总和。首先，提出了一种多跳干扰感知近最优调度（MINOS）算法，通过线性规划联合确定数据包转发概率与无干扰链路集合的选择概率，并依据数据包类型、已消耗时间和所在节点实施概率转发。其次，设计了一种结合概率转发的贪心极大调度（GMS-PF）算法，通过贪心选择可并发传输的链路集合，避免对全部独立集进行随机选择所带来的高计算开销，实现多项式时间计算并支持分布式执行。在满足相应随机到达假设及信道数量等条件时，两种算法分别提供近最优性能保证和与网络干扰度相关的近似性能保证。
该方法的创新和贡献如下：
1）本文在随机业务条件下，为存在链路干扰和严格端到端截止期约束的多跳无线网络提供了非渐近的近最优及常数近似结果。与依赖带宽、到达率和运行时间趋于无穷的既有方法不同，所提出的方法在这些参数均有限且满足相应条件时即可获得理论保证，其近似比不随数据包权重或最大路由长度增大而恶化。
2）提出了两种具有不同计算复杂度与性能保证的调度算法：a）多跳干扰感知近最优调度算法利用线性规划协调链路资源分配与概率转发，并预留容量裕量以降低随机流量超出可用资源造成的丢包，从而获得近最优的按时交付收益；b）结合概率转发的贪心极大调度算法利用规模更小的线性规划引导转发，在各时隙、各信道上贪心构建无干扰链路集合，在降低计算复杂度的同时保留可证明的性能保证。
03.
算法介绍
（1）多跳干扰感知近最优调度（MINOS）算法
图1 多跳干扰感知近最优调度算法的执行过程
多跳干扰感知近最优调度算法通过联合设计数据包转发策略和信道资源分配，提高随机业务在端到端截止期内的交付收益。算法利用干扰图描述链路之间的冲突关系：若两条链路之间存在干扰边，则不能在同一时隙、同一信道上同时传输；一个独立集则对应一组可以并发传输的无干扰链路。
如算法1所示，该方法包括线性规划求解、信道分配和在线概率转发三个阶段。首先，根据各类数据包的源节点、目的节点、截止期、权重及平均到达率，求解线性规划，获得转发变量和独立集选择概率。随后，为每个信道随机选择一个独立集，确定各条链路能够使用的信道数量，该分配在本次算法执行期间保持不变。
在线运行阶段，算法根据每个未过期数据包的类型、已消耗时间和当前所在节点，随机选择下一条转发链路。如果选择的是自环，则表示数据包在当前节点等待一个时隙；如果选择的是实际通信链路，则将其加入该链路的待发送集合。每条链路按照已分配的信道数量发送数据包，超过当时可用容量的剩余数据包被丢弃。
（2）线性规划与概率转发机制
线性规划是多跳干扰感知近最优调度算法的核心。设第j类数据包的权重为wj，平均到达率为λj，相对截止期为dj，目的节点为zj。变量f描述该类数据包在年龄为τ时经过链路l的规划流量比例，其中“年龄”表示数据包自到达以来已经经过的时隙数。优化目标为：
该目标最大化规划中按时到达目的节点的数据包加权收益。其中，Inc（zj） 表示进入目的节点的链路集合，包含目的节点自环。提前到达的数据包可以通过自环在目的节点保留，因此也计入按时交付收益。模型通过源节点约束、逐时隙流守恒和非负约束，使转发过程在时间和空间上连续。
为了协调转发需求与信道资源，算法设置以下容量约束：
左侧表示链路上的平均转发需求，右侧表示预留一定裕量后的平均服务能力。系数(1-ε)用于留出容量余量，降低随机到达造成瞬时需求超过可用资源的概率。
获得最优解后，每个信道按照以下混合概率选择独立集：
对于位于节点v、类型为j、年龄为τ的数据包，下一条链路按照以下概率选择：
该式将当前节点各条出链路上的最优转发变量归一化，得到实际执行时的条件选择概率，使数据包的逐跳转发遵循线性规划确定的资源安排。
（3）结合概率转发的贪心极大调度（GMS‑PF）算法
图2 AIADC算法的工作流程
当网络规模增大时，干扰图中的独立集数量可能快速增长，增加多跳干扰感知近最优调度算法的线性规划求解开销。为此，本文提出结合概率转发的贪心极大调度算法，保留概率转发机制，并通过逐时隙贪心选择无干扰链路集合完成信道分配。
如算法2所示，首先求解简化后的线性规划，获得各类数据包的转发变量。在每个时隙，算法根据数据包类型、年龄和所在节点选择下一条链路，并将数据包加入相应的待发送集合。该概率选择方式与前述公式相同，但转发变量来自新的线性规划。
随后，算法依次处理各个信道，从具有待发送数据包的链路中选出一个极大独立集，并在其中每条链路上发送一个数据包。完成当前信道的分配后，更新待发送集合，再为下一信道选择链路。所有信道处理完毕后，丢弃尚未获得传输机会的剩余数据包。
这里的“极大独立集”表示不能再加入其他候选链路而不产生干扰，并不要求其包含的链路数量最多。因此，算法可以通过逐步选择链路并排除冲突邻居完成调度，无需求解最大独立集问题。
（4）邻域容量约束与分布式信道选择
结合概率转发的贪心极大调度算法采用干扰邻域容量约束，替代对各个独立集设置概率变量的方式。其优化目标仍为最大化按时交付的加权收益，核心容量约束为：
其中，Nl包含链路l本身及所有与其存在干扰的链路。该约束限制整个干扰邻域的平均转发需求，使相互竞争的链路保留足够的信道分配空间。模型同时保留原有的源节点、流守恒和非负约束。
由于不再为每个独立集引入变量，新的线性规划规模明显减小。在线调度时，算法可以采用贪心方式构建极大独立集，例如优先选择待发送数据包较多的链路，从而以较低的计算开销完成可并发链路选择。
此外，论文给出了基于随机定时器的分布式信道选择方法。各链路为不同信道设置随机定时器，定时器先到期且未被干扰邻居抢先占用的链路声明使用该信道；当一条链路获得的信道已足以发送其待发送数据包时，便取消剩余定时器。该机制用于分布式实现在线独立集选择。在控制开销足够小等假设下，可获得相应的理论性能保证。
04.
实验结果分析
1. 不同干扰条件下的调度性能验证
图3 单跳干扰与一般干扰条件下的按时交付收益对比
本文分别在8节点的单跳干扰网络和20节点的一般干扰网络中进行实验，以每时隙内按时交付数据包的加权收益作为评价指标。如左图所示，随着信道数量增加，多跳干扰感知近最优调度（MINOS）算法始终获得最高收益，结合概率转发的贪心极大调度（GMS-PF）算法次之，两者均优于基线方法NEMS。
在一般干扰条件下，两种算法同样优于基线方法GIMS，其中MINOS表现最佳。结果表明，所提出的方法能够在不同链路干扰条件下有效利用信道资源，提高满足端到端截止期的数据包交付收益。
2. 不同业务到达分布下的性能分析
图8 100 节点网络中不同配置下的吞吐量和误码率结果
为分析随机业务特征对调度性能的影响，本文比较了二项分布、泊松分布和缩放伯努利分布三种到达模式，并保持各模式的平均到达率一致。评价指标为算法收益与线性规划最优值的比值，该指标给出了算法相对于离线最优调度的近似比下界。
如左图所示，MINOS在二项分布下表现最佳，在泊松分布下获得相近性能；缩放伯努利分布下的性能相对较低，但随着信道数量增加也逐渐接近最优。如右图所示，MINOS的经验近似比下界接近1，GMS-PF约为0.5，二者均高于NEMS。结果验证了所提算法在不同随机到达条件下的有效性。
3. 网络规模与计算开销分析
图11 不同网络规模下的运行时间与近似比对比
本文将网络规模由8个节点、24条链路逐步增加至16个节点、74条链路，考察算法的计算开销和调度性能。如左图所示，在5000个时隙、40个信道条件下，MNOS的运行时间由2.85秒增加至37.47秒，GMS-PF则由11.06秒增加至26.06秒。MINOS在较小网络中运行更快，但随着规模增大，其线性规划求解开销明显上升，GMS-PF在最大测试规模下具有更低的总运行时间。
MINOS在不同网络规模和信道数量下均保持更高的近似比，增加信道数量能够改善两种算法的性能。这说明两种方法在调度收益与计算开销之间具有不同取舍：MINOS具有更好的收益表现，GMS-PF则缓解了网络规模增大带来的计算负担。
4. 不同业务负载下的性能分析
图3 两种信道容量下近似比随业务负载的变化
本文在8节点、10条业务流的网络中，将基础到达率放大20至50倍，分别测试25个信道和125个信道下的算法性能。如图所示，在25个信道条件下，MINOS的近似比约为73.7%—79.8%，GMS-PF约为43.8%—46.9%；当信道数量增加至125时，MINOS提升至80.4%—81.6%，GMS-PF提升至约48.0%—48.1%。
结果表明，在所测试的业务负载范围内，MINOS始终保持更高的按时交付收益，且能够通过增加信道资源进一步改善性能。同时，实际近似比仍会随业务负载变化，理论性能保证并不意味着算法表现完全不受负载影响。
05.
总结
本文针对多跳无线网络中具有严格端到端截止期且链路存在干扰的随机业务调度问题，提出了近最优调度算法MINOS和高效的贪心最大调度与概率转发算法GMS-PF。两种算法通过线性规划、概率转发以及干扰图独立集调度，在有限信道数、有限业务到达率和有限时间范围内实现高效的数据包路由与链路调度。其显著特点是突破了现有方法依赖渐近条件或近似性能随网络参数恶化的局限。理论分析与仿真结果表明，MINOS可获得近最优性能，GMS-PF在降低计算复杂度的同时仍保持良好性能，并在单跳和一般干扰场景下均优于现有NEMS和GIMS方法，体现了对多种随机业务和网络拓扑的良好适应性。
END
==河海大学网络与安全实验室==
微信搜索：Hohai_Network
联系QQ：1084561742
感谢关注！
免责声明：
本文所载程序、技术方法仅面向合法合规的安全研究与教学场景，旨在提升网络安全防护能力，具有明确的技术研究属性。
任何单位或个人未经授权，将本文内容用于攻击、破坏等非法用途的，由此引发的全部法律责任、民事赔偿及连带责任，均由行为人独立承担，本站不承担任何连带责任。
本站内容均为技术交流与知识分享目的发布，若存在版权侵权或其他异议，请通过邮件联系处理，具体联系方式可点击页面上方的联系我。
本文转载自：网络与安全实验室 《每周文章分享-278》