《战术自主蜂群网络优化中的时延与收敛速度》美空军36页报告

该研究项目解决了下一代自主蜂群网络系统的分布式控制和优化的挑战，其中快速变化和超动态的网络状态（如网络拓扑结构、频谱和信道状态信息、数据缓冲区排队状态等）需要分布式优化算法的快速收敛和低延时。最近基于PI对网络控制和优化的研究，利用二阶信息（SOI），在这个研究计划中，我们提出了一系列新的分布式算法技术，与传统方法相比，在收敛速度和排队延迟方面都有数量级的改进，同时达到了同样的可证明的网络效用优化。

具体来说，我们在这个项目中的研究任务集中在基于动量（Heavy-ball）的联合拥堵控制和多路径路由（部分SOI）的EMANE仿真实现上。我们提出的研究计划采取了一种综合的、整体的方法，从数学建模、优化理论、控制理论、排队理论和随机分析等领域吸取技术。拟议的研究不仅将推进我们在下一代复杂网络的算法设计方面的知识，而且还将通过探索基于SOI的网络控制和优化的新领域来满足一般网络研究界的关键需求。

所提出的方法将影响广泛的应用，如机载网络和无人机系统的图像/视频，特别是在控制和优化行动不能承受大的延迟和缓慢收敛的系统。将寻求与AFRL进行实质性的合作，以促进这一研究工作的潜在过渡途径。

图1：在高度动态的无线网络下，无人机系统通信有严格的延迟要求。

引言

背景和动机：

随着部署在战场上的通信网络的激增以及它们所产生的大量移动数据，今天的无线网络技术正被拉伸到极限。不仅战术信息的爆炸性增长要求不断增加网络容量，大规模无线网络的复杂协调也在实时控制和优化中引入了严格的延迟和收敛速度要求。为了设计高效的优化算法来应对新兴的战术无线网络，一个关键的方面是有效地处理拥塞控制和链路调度之间的交叉互动，包括在协议栈层内和跨协议栈。因此，近年来出现了对战术无线网络的低延迟和快速转换的联合拥堵控制和调度算法的迫切需求。此外，联合拥塞控制和路由优化不仅是信息网络设计的要求，也是许多复杂网络运行的核心问题，如智能电网需求响应[1-3]、供应链管理[4-7]、交通网络流量控制[8, 9]，仅举几例。

一个动机示例：为了说明快速收敛、低延迟和分布式设计的重要性，我们在此以无人机系统网络为例。控制和优化无人机系统网络的一大挑战来自于快速变化和高度动态的网络状态（如网络拓扑结构、频谱/信道状态、数据缓冲区排队状态等），这使得传统的拥堵控制、路由和频谱访问技术变得无效（见图1的说明性例子）。这种高度动态的性质需要网络控制和优化算法的快速收敛。否则，在完成缓慢的收敛过程后，网络拓扑结构、频谱/信道状态信息和排队状态很可能被大大改变，使所有的计算结果和控制行动变得过时和无用。

使网络控制问题更加严重的是，控制行动与需要实时传输大量数据的时间密切相关（例如，无人机系统图像或视频监控等）。因此，当数据到达量激增时，需要低延迟的网络控制算法来避免过度延迟和大量的丢包（由于超时事件）。否则，可能会发生突然的大规模网络中断，这不仅会导致大范围的不便，而且会导致毁灭性的战斗失败甚至是生命损失。此外，机载网络的地理规模大，网络子系统之间物理层技术的异质性，以及快速响应时间的要求，意味着控制和优化算法既不能集中，也不能有高的复杂性。这就要求开发出完全分布式的算法，以规避单点故障问题，简单易行，又能达到可证明的优化性能。

目前的技术状况：

由于移动数据需求的快速增长，近年来出现了大量关于资源分配的工作，旨在使无线网络中的网络效用最大化（例如，见[10-13]，和[14]的调查）。这导致了一个优雅的数学分解框架，"松散耦合 "的拥堵控制、调度和路由算法自然而然地出现。这些算法不需要关于到达或信道状态的统计知识。相反，它们只依赖队列长度和信道状态信息来做出控制决策。这些算法也与非线性优化理论中的拉格朗日对偶分解框架和子梯度方法有内在联系[10, 11]，其中（按比例）队列长度可以被解释为拉格朗日对偶变量，队列长度更新起到子梯度方向的作用。

尽管这些基于队列长度的算法（QLA）具有吸引人的特点，但它们受到了几个关键的限制。首先，在现有的QLA框架中，已经证明了效用优化差距O(1/K)可以通过排队延迟的O(K)惩罚来实现，其中K>0是一个系统参数。因此，一个小的效用优化差距需要一个大的K，并导致大的排队延迟。为了解决这一局限性，近年来有大量的工作（如[13，15-17]等）集中在减少这些方案的排队延迟上（后面对相关工作有更深入的讨论）。同时，在现有的QLA框架中，基于队列长度的权重调整忽略了目标函数轮廓的曲率，并且在每次迭代中使用小的步长[10-13]，这导致收敛速度不理想。为了解决这个问题，最近提出了一些二阶拥塞控制和路由/调度算法来提高收敛速度（见，例如，[18，19]）。然而，由于其复杂的算法结构，这些二阶方法需要更大的信息交换开销，并且不能随着网络规模的扩大而很好地扩展。现有方法的这些限制促使我们在这个项目中追求一种新的重球设计。

更具体地说，在这个项目中，我们开发了一个基于重球的权重调整方案，在不影响网络效用性能和不增加任何计算复杂性的情况下，大幅减少队列长度，提高收敛速度。我们的方法是基于将队列长度与权重分离的巧妙想法，然后使用一个权重更新方案，该方案只利用前一个时隙的权重变化的一个更多的记忆槽。令人惊讶的是，我们表明这个简单的方案提供了两个控制自由度，使我们能够实现效用优化、低延迟以及快速收敛。

从历史上看，重球法是由Polyak在20世纪60年代首次提出的[20]，用于解决无约束的凸优化问题，其最初的目标是加速梯度下降法的收敛。重球法的基本思想是，不是只使用当前迭代的（子）梯度信息和完全不记忆过去迭代的轨迹，而是使用当前梯度（类似于 "势"）和上一步的更新方向（类似于 "动量"）的线性组合来计算搜索方向。该方法是由物理学中描述重体在势场中运动的二阶常微分方程（ODE）激发的，并可被视为该方程的离散版本，因此被称为 "重球（HeavyBall）"。在[21]中已经表明，通过适当地权衡当前的 "势 "和 "动量"，该算法对目标轮廓不敏感，这导致了更快的收敛。事实上，收敛加速的优势是我们在无线网络跨层优化中采用重球方法的第一个基本理由。但令人惊讶的是，我们随后的研究表明，采用重球思想的好处远远超出了收敛加速的范围。

然而，我们注意到，由于一些技术上的挑战，为无线网络中的效用最大化问题开发一个基于重球的解决方案并不简单。首先，由于重球法最初是为无约束的静态优化问题设计的，目前还不清楚如何为无线网络效用最大化修改重球法，因为无线网络是一个有约束的随机优化问题，问题结构要复杂得多。其次，与QLA设计中队列长度和拉格朗日对偶变量之间的明显联系不同，重球法与可观测的网络状态信息（如队列长度、信道状态等）之间的关系是未知的。因此，在重球法下，延迟和网络效用之间的权衡仍然是一个开放的问题。第三，由于包含了过去的迭代值，重球方法的算法结构与QLA方法不同。因此，QLA中用于建立吞吐量-优化和效用-延迟权衡的传统技术并不适用。因此，在重球方法的性能分析中需要新的分析技术。

技术贡献：

本项目的主要贡献是，我们首次开发了一个基于重球的无线网络效用优化框架，克服了上述的技术挑战。我们建立了一系列关于大幅减少延迟和快速收敛的新分析结果，同时保留了效用优化的特点。本文的主要结果和技术贡献如下：

在重球思想的启发下，我们提出了一个新的权重调整方案，用于无线网络中的联合拥塞控制和路由/调度。我们的工作不仅提供了重球算法和可观察的网络状态信息（队列长度和信道状态）之间的协同作用，允许在实践中简单实现，它还扩展和概括了经典的重球方法，从无约束的静态优化到约束的随机网络效用优化范式，从而推进了数学优化理论中重球方法的先进性。
在我们的基于重球的联合拥堵控制和调度方案下，有一个β参数化的动量（β∈[0，1]是一个系统参数，通常选择接近1），我们表明，延迟是（1-β）-QLA方法的小数部分。更具体地说，我们的理论分析表明，可以用O((1-β)K)+O((1+β)√K)的排队延迟成本实现效用最优差距O(1/K)，其中参数K与重球法的步长成反比。此外，在β被选为β=1-O(1/ √ K)的K的渐进制度中，我们的重球算法实现了[O(1/K), O( √ K)]效用-延迟权衡，这明显优于众所周知的QLA方法的[O(1/K), O(K)]权衡。
鉴于参数K和β，我们表明我们基于重球的算法的收敛时间扩展为O[log(√ K) (- log-1 (1 + β - √ β))]。结合前面的结果，我们提出的重球算法提供了一个重要而优雅的三方权衡关系，由K和β中的两个控制旋钮控制。最值得注意的是，通过权衡收敛速度，同时实现效用最优和低延迟。我们注意到，这种重要的三向权衡关系迄今在文献中尚未被发现。
除了理论结果，本项目的一个重点是开发高保真的基于EMANE的模拟，以测试和验证我们上述的理论结果和见解。在这个项目中，我们已经成功地开发了一个基于Shim层的EMANE跨层仿真平台来测试我们的HeavyBall算法。我们基于EMANE的仿真结果表明，所有的理论预测在高保真仿真中是可以观察到的。此外，值得一提的是，我们的基于EMANE的跨层仿真平台具有很强的通用性，对于AFRL所重视的其他基于EMANE的无线网络跨层仿真来说，可以具有独立的利益。