基于网络编码和自适应速率且保证服务质量的无线广播调度外文翻译资料

英语原文共 12 页，剩余内容已隐藏，支付完成后下载完整资料

基于网络编码和自适应速率且保证服务质量的无线广播调度

Hang Shen and Guangwei Bai

摘要-网络编码对于实时应用程序的无线广播至关重要。大多数已有的方法都对应用程序的要求（例如，单个约束类型或相同约束级别）或者数据传输（例如，理想信道，固定传输速率，或数据包长度）做出了强假设，以便于促进形式化和解决。这些假设限制了先前方法的适用性。这篇文章研究了通过具有网络编码和速率选择功能的无线网络来提供保证服务质量的广播调度，着重于减少广播完成的延迟，同时最大化满足异构期限和可靠性要求的分组接收数量。首先，构建了一个多速率图模型来制定最优广播调度问题，这已被证明是NP-hard。然后，提出一种自适应图压缩的策略，以在不牺牲性能的情况下显著减少计算负担。此外，为每个广播提供了一个近似框架。在该框架中，编码策略和速率选择可以表述为可调节复杂度的团问题。最后，设计了一种渐进式团搜索算法来对每个广播做出决策。仿真结果表明，与典型的启发式算法相比，该算法以较低的复杂度实现了显著的性能提升。

索引词--广播调度，无线网络，网络编码，速率适配，QoS敏感的应用程序。

I. 引言

随着无线网络和移动计算的普及，已经出现了许多新兴应用，包括实时视频广播，移动虚拟现实，移动云游戏和基于位置的服务，这些应用对用户具有非常大的吸引力。但是，这些应用程序具有严格的QoS（服务质量）要求，如[1] - [3]。数据包的丢失会导致通信损坏，例如图像干扰和冻结；高延迟会导致数据可用性降低，例如连续的基于位置的查询的异步性。

研究已经表明，网络编码可以显著提高通信性能[4]。[5]首次尝试在无线环境中执行网络编码。在该方案中，每个节点通过机会监听获得其邻居的分组接收状态，而中继站可以利用本地信息独立地编码多个分组，从而增加了每次传输中携带的数据量。无线数据分发是网络编码的一个重要应用。当一个服务器通过广播/多播的方式将数据包分发给多个客户端时，可以通过使用网络编码来显著减少完成延迟。目前，关于如何最小化广播过程中的数量[6]，[7]和成本[8]，[9]，以及如何提高及时性[10] - [13]和可靠性[14]，[15]，已经取得了技术和理论上的成果。但是，这些方案中的大多数要么取决于特定的应用要求（包括单个约束类型或相同的约束级别），要么对数据传输（包括固定的传输速率或数据包大小，或者没有数据包丢失的理想信道）进行了强假设，这在很大程度上降低了实用性。

在多速率无线网络中，节点可以动态选择传输速率，这将直接影响吞吐量，及时性，可靠性和成本方面的指标[16] - [18]。较低的速率可能导致吞吐量降低[19]；除了降低传送比率[20]之外，高速率可能会使相邻节点之间无法完成监听[21]。另一个挑战是不同的期限和可靠性要求。由于这些绩效指标之间存在复杂的关系，因此每个决策都可能影响其后续决策。如果我们遵循最大化编码增益的原则，则很可能会发生由于QoS（服务质量）约束而导致的数据包故障；而使用最小截止时间优先策略[13]会降低编码增益。这些约束和挑战，以及随时间变化的链路质量和很高的计算复杂性，使得调度QoS（服务质量）受限的广播成为一个具有挑战性的问题。寻找一种合理地进行速率选择和编码决策的方法已成为一个重要问题。

我们在图1中提供一个示例来说明我们的动机，其中服务器s需要分别向四个客户端d₁，d₂，d₃和d₄发送数据包p₁，p₂，p₃和p₄。图1(a)给出了客户端d_i拥有的和需要的一组数据包，分别由H_i和R_i表示。图1(b)提供了每个所需数据包在其目的地的截止时间，以及在时间t₀以第z个可用传输速率r_z传输的数据包通过链路lt;s, d_igt;的预期接收率（用theta;_z，i(t)表示）。假设1)，每个原始数据包的长度为L = 10 k，以及假设2)，在传输中采用冗余方案以确保成功传输数据包。对于这种情况，根据[5]，[13]，[22]的常见方法是发送已编码的数据包p₁oplus;p₂oplus;p₃oplus;p₄来最大化可以解码该数据包的客户端数量。但是，这不是一个好的选择，因为选择任何一种速率并不能保证所有包都可以在它被要求的期限内。例如，如果选择r₁ = 1 kbps，则此编码数据包的预期广播延迟为

Fig. 1. Motivation illustration. (a) Packet reception status. (b) Deadlines and packet reception ratios.

这错过了p₁，p₂和p₃的最后期限，因为它们的预期目的地无法在其接收期限内获得足够的数据来恢复数据包。稍后我们将给出详细的量化。同样，d₁不能用r₂在4 s内获得p₁；d₂不能用r₄在9 s内获得p₂。一个我们能选择的替代方法是先以速率r₄发送p₁，其中d1将在4 s内获得p₁。为了简化问题，我们暂时假设第二个广播的数据包接收率保持不变。接下来，如果以速率r₃发送冗余之后的编码分组p₂oplus;p₃oplus;p₄，则d₂，d₃和d₄将在6.25s内获得它们想要的分组。这是其中一种不会在截止期限内丢包的解决方案。

在这项工作中，我们研究了针对QoS（服务质量）敏感应用且基于网络编码和速率适配功能的无线广播调度，目的是缩短广播完成延迟，同时最大化受异类QoS（服务质量）约束的数据包的接收数量。主要贡献可以归纳如下：

1. 提出了一种多速率图模型，来确定编码的数据包和广播速率，并确保在有不同的截止期限和可靠性约束的情况下，所有输出数据包都可以成功地被接收/解码。在此基础上，我们提出了最佳广播调度问题的整数规划公式。

2.为了过滤调度中不必要的搜索，提出了一个截止期限的图压缩策略，然后是每个广播的问题近似框架。利用该框架，设计了一种渐进式团搜索算法，通过参数设置实现计算复杂度的调整。

3 .为了证明我们算法的有效性和实用性，我们进行了一系列模拟实验，其中严格考虑了应用程序的要求，包括客户端的数量和要发送的数据包的数量。在调查和理解性能瓶颈的同时，对不同算法进行了比较和分析，以确定最佳解决方案。

本文的其余部分安排如下：我们将在下一节中简要介绍相关作品。第三节描述并阐述了我们的问题。第四节给出了问题逼近框架和启发式算法。最后，在第六节的总结之前，我们在第五节中介绍了仿真结果和性能分析。

II. 相关作品

尽管许多研究[23] - [26]致力于调度具有QoS要求的无线网络广播，但提出的解决方案可能无法直接应用于网络编码或者是多速率环境。

文献[11]中的工作旨在最小化基于网络编码的多播的平均延迟，而没有考虑延迟保证。文献[27]中基于网络编码的广播策略可以实现具有有限延迟的渐近容量。但是，它假定所有数据包的最后期限都相同。文献[28]中的作者解决了在不可靠的无线链路上调度受延迟约束的流量的问题，并提出了一种可行的最佳编码方案。但是，没有考虑约束级别的影响。文献[29]中的广播方案旨在通过调整编码块来最大化吞吐量，同时满足最后期限。在[30]中提出了一种可靠的无线多播协议，其中可以通过利用实时网络编码来满足数据包的播出期限。尽管及时性或可靠性有所提高，但这两篇文献的方法并未考虑异构约束。

文献[31]中的作者使用成对编码策略来调度具有异构延迟约束和权重的会话间流量，重点关注的是最大化数据包的加权和。参考文献[32]提出了一种由QoS驱动的网络编码多播协议，该协议考虑了缓冲区溢出和延迟违规约束。在文献[13]中提出了一种用于点播的通用编码框架，其中优化目标被抽象为最小限期未命中率的团。尽管它可以根据应用需求进行定制，但由于理想通道的假设，实用性受到了损害。参考文献[22]设计了一种基于最大权重团的编码算法，用于具有延迟约束的无线广播。但是，它缺乏可靠性支持。

以上工作均在传输速率固定的前提下进行。文献[20]考虑了速率选择对预期传输效率的影响。RBAR [33]是一种早期的速率自适应MAC协议，用于在给定信道条件下的最佳吞吐量。文献[34]提供了现有吞吐量最佳编码方案的理论延迟分析，并设计了速率适配方案。相对来说，比较少的研究关注具有速率自适应的QoS受限应用上。RSNC [12]是一种联合速率选择和网络编码方案，用于在满足截止期限要求的同时最大化接收到的数据包数量。作者还提出了一种基于成对编码的轻量级解决方案。尽管有理想的信道假设，但这项工作为设计延迟感知调度机制提供了有价值的参考。在文献[35]中提出了一种用于无线传感器网络的基于网络编码的可靠数据分发方法。目标是实现能源效率并最大程度地减少数据分发的完成时间，而不是提供截止日期保证。

在研究了该领域的现有方法之后，我们意识到，对于不可靠的无线链路上的网络编码和多速率广播调度，要为其提供具有可调整的计算复杂度的异构可靠性和延迟保证，暂时没有很全面的研究。这驱使我们来制定一个切实可行的方案。

III. 最佳广播调度问题

表 I

符号和变量

您可能感兴趣的文章

• 基于校园网的学生作业批阅系统的设计与实现外文翻译资料
• Android平台上基本路由器和交换机配置的移动学习应用程序外文翻译资料
• Java、因特网和管理系统外文翻译资料
• 微信公众号信息服务平台研究外文翻译资料
• 基于Java平台的数据库桥接层Spring框架可靠性研究外文翻译资料
• 第二章：计算机教育的发展外文翻译资料
• 射频识别技术支持的药品监管可追溯系统外文翻译资料
• 基于深度学习算法的人脸识别技术分析外文翻译资料
• Spring Boot实战外文翻译资料
• 基于软系统方法论(SSM)的可持续旅游发展:以印尼西苏门答腊岛巴东班江为例外文翻译资料