网络效用最优化理论

分配网络带宽给网络用户后用户的满意程度

网络效用是指分配网络带宽给网络用户后用户的满意程度。网络效用最优化就是设计分配网络资源的方案或算法以使所有网络用户的总的效用最大并且单个网络用户的效用也能让该用户满意。

以下主要介绍网络效用最优化理论的研究现状。

研究现状

文献研究传输弹性流的通信网络（比如，提供可用位速率服务的ATM 网络）的收费，速率控制和路由的问题。从最大和最小的公平率作为一个特殊的例子，作者描述了一个模型。更一般的，收费用户准备好去付费进而影响他们的分配率。在模型的首选版本中，一个用户选择它将要付的单位时间的费用。其后，根据应用于每单位费用的速率的一个比例公平标准，从而决定用户的速率。当用户选择的费用和网络选择的分配速率达到平衡，系统的最优状态就实现了。

文献分析了针对通信网络的稳定性和公平性的两种类型速率控制算法。这些算法提供了对简单的附加递增或递减计划的大规模网络的自然归纳，并且在被一个比例公平准则所描述的系统最佳状态下达到稳定性。在有一个对整个优化问题适当的规划的条件下，网络的隐含目标函数提供了一个针对由速率控制算法定义的动态系统的Lyapunov函数。网络的最优化问题可以投射进原始或对偶形式；这样很自然的引申出两类算法。这些算法可以被拥塞指示反馈信号或基于影子价格明确速率所解释。两类算法都可以推广到路由控制和对成比例公平定价提供自然实现。

文献是网络效用最优化理论的奠基之作，其后华中师范大学计算机学院的谭连生教授及其合作者对此理论进行了发展。以下选取他们的论文予以介绍。

文献的作者将Frank Kelly的网络效用最优化模型扩展到双向流的情形，也就是说，流中的数据包和确认（ACK）共享一个完整的双向通道。这是一个有趣的推广。

文献指出，在无线网络中，为了满足网络用户的特殊的服务质量（QoS）要求去分配有限的资源是一个挑战，特别是当用户又不同类型的流量要求，比如硬性的Qos流量，最大努力流，弹性的Qos流量。在这篇文献里，作者研发出了基于效用的资源分配算法。这些算法分为三个方面，（1）在硬性的Qos流量与弹性的Qos流量下的资源分配，（2）在最大努力流与弹性的Qos流量下的资源分配，（3）在硬性的Qos流量，最大努力流与弹性的Qos流量下的资源分配，这些算法是通过使用Karush-Kuhn-Tucker 条件解决网络效用最大化解决的。作者给出了一系列的判定定理去给出同一个框架下发现上述三种情形下的最优解的条件。这些定理之后就担任这三种算法的设计指南。这些被提出的算法将流量类型，总共的可用的资源以及用户的信道质量考虑进去。作者评估算法的时间复杂度为为多项式时间并且通过数字例子研究了网络性能。

在文献中作者研究了在无线网络中的最佳资源分配问题，在这里所有的流量类型被同一个效用方程描述。这个问题被投射进一个网络效用最优化模型中。作者按用户的效用和流量类型用公式表示出公平指数，然后研究他们的关系。边际效用递减原则在经济学中广泛使用。在这篇文献中，作者确立了平等原则和边际效用递减原则。通过使用这两个原则作者发现了对于网络效用最优化模型的最优解决方案。这些解决方案分别针对总资源充分和不充分两种情形。作者提出了一些必要的定理和算法去发现针对以上两种情形最优方案。

文献指出，最优化理论和非线性规划方法已经被成功的运用到因特网去开发高效率的资源分配与拥塞控制方案。在通信网络中的资源分配问题已经被建模成一个最优化问题：目标是在服从网络资源限制的条件下去最大化资源综合效用。然而，对于无线网络，如何分配软服务质量流量的资源还是一个重要的设计挑战。从数学角度讲，最大的困难来自于网络效用最大化过程中软服务流量的非凹方程。之前的结果只能找出次优的结果。面对这一挑战，这篇文献确立了一些关键性的定理去发现最优解。然后提出了一个针对软服务质量的基于效用分配的完整算法，进而得到最优解。

文献指出，在网络中的资源分配被投射进网络效用最大化问题中。对于有线网络中的拥塞控制和弹性流量已经有分布式算法用于解决此问题。然而对于无弹性网络包括软服务质量流量的无线网络的资源分配，这个问题还面临着挑战。首先，在无线网络中，对用户的效用方程建模是很困难的。其次，软服务质量流量的效用方程通常是非凹的，这样导致网络效用最优化问题在数学上很难解决。在和通常的网络效用最优化理论存在偏差的情况下，这篇文献提出了一个新奇的最优化模型，并且它的算法对于带宽的分配接近在无线网络中用户对于软服务质量流量的渴望值。作者的模型利用软服务流量的基本特征。换言之，它需要一些优先的带宽但是在正常的操作中允许一些灵活性。与基于效用的方法和解决方案，我们的方法避免通过使用偏爱的带宽值为每个用户找到准确的效用方程表达式的困难。这加速了现实中无线网络的操作。文章用实例核实了提出的模型和算法并且证明它的性能优于网络效用最优化理论方法（NUM approach）。

Frank Kelly教授的网路效用最优化理论（NUM）问题和解决方法是在满足连接容量限制的条件下最优化综合效用。它们是使用个体流的速率向量来表述和解决的。由于现有网路的结构，对于网络服务提供者，单个流的速率在路由器里一般上不是直接可测量的。然而，总共的流的速率是很方便获得和调整的。在这篇文章里，作者研究了通信网络的NUM问题，但是从一个路由层的带宽分配角度。通过使用广义逆矩阵，作者提出了一个效用最优化路由层带宽分配的一般模型和它的解决方案。它的目标方程和限制条件使用总的流的速率表示而不是像在NUM问题中使用单一流的速率向量表示。作者发现新提出的模型和Frank Kelly教授提出的NUM模型是等价的,因为它们得到同样的最优状态和它们的方案满足给定的路由计划.作者也讨论了当路由矩阵是满秩和在网络中每一个连接有一个单跳流的的特殊情形。作者提出了一个对于后者的因特网基于协议的虚拟网络的直接应用。作者展示了导出效用最优化总的流的速率向量的数学模型和解决方案，然后用数字实例更进一步的解释了它们。

全国各地天气预报查询

上海市

云南省

云南省

云南省

云南省

云南省