網絡效用最優化理論

以下主要介紹網絡效用最優化理論的研究現狀。

文獻 ^[2]  研究傳輸彈性流的通信網絡（比如，提供可用位速率服務的ATM 網絡）的收費，速率控制和路由的問題。從最大和最小的公平率作為一個特殊的例子，作者描述了一個模型。更一般的，收費用户準備好去付費進而影響他們的分配率。在模型的首選版本中，一個用户選擇它將要付的單位時間的費用。其後，根據應用於每單位費用的速率的一個比例公平標準，從而決定用户的速率。當用户選擇的費用和網絡選擇的分配速率達到平衡，系統的最優狀態就實現了。

文獻 ^[3]  分析了針對通信網絡的穩定性和公平性的兩種類型速率控制算法。這些算法提供了對簡單的附加遞增或遞減計劃的大規模網絡的自然歸納，並且在被一個比例公平準則所描述的系統最佳狀態下達到穩定性。在有一個對整個優化問題適當的規劃的條件下，網絡的隱含目標函數提供了一個針對由速率控制算法定義的動態系統的Lyapunov函數。網絡的最優化問題可以投射進原始或對偶形式；這樣很自然的引申出兩類算法。這些算法可以被擁塞指示反饋信號或基於影子價格明確速率所解釋。兩類算法都可以推廣到路由控制和對成比例公平定價提供自然實現。

文獻 ^[2-3]  是網絡效用最優化理論的奠基之作，其後華中師範大學計算機學院的譚連生 ^[5]  教授及其合作者對此理論進行了發展。以下選取他們的論文予以介紹。

文獻 ^[4]  的作者將Frank Kelly的網絡效用最優化模型擴展到雙向流的情形，也就是説，流中的數據包和確認（ACK）共享一個完整的雙向通道。這是一個有趣的推廣。

文獻 ^[6]  指出，在無線網絡中，為了滿足網絡用户的特殊的服務質量（QoS）要求去分配有限的資源是一個挑戰，特別是當用户又不同類型的流量要求，比如硬性的Qos流量，最大努力流，彈性的Qos流量。在這篇文獻裏，作者研發出了基於效用的資源分配算法。這些算法分為三個方面，（1）在硬性的Qos流量與彈性的Qos流量下的資源分配，（2）在最大努力流與彈性的Qos流量下的資源分配，（3）在硬性的Qos流量，最大努力流與彈性的Qos流量下的資源分配，這些算法是通過使用Karush-Kuhn-Tucker 條件解決網絡效用最大化解決的。作者給出了一系列的判定定理去給出同一個框架下發現上述三種情形下的最優解的條件。這些定理之後就擔任這三種算法的設計指南。這些被提出的算法將流量類型，總共的可用的資源以及用户的信道質量考慮進去。作者評估算法的時間複雜度為為多項式時間並且通過數字例子研究了網絡性能。

在文獻 ^[7]  中作者研究了在無線網絡中的最佳資源分配問題，在這裏所有的流量類型被同一個效用方程描述。這個問題被投射進一個網絡效用最優化模型中。作者按用户的效用和流量類型用公式表示出公平指數，然後研究他們的關係。邊際效用遞減原則在經濟學中廣泛使用。在這篇文獻中，作者確立了平等原則和邊際效用遞減原則。通過使用這兩個原則作者發現了對於網絡效用最優化模型的最優解決方案。這些解決方案分別針對總資源充分和不充分兩種情形。作者提出了一些必要的定理和算法去發現針對以上兩種情形最優方案。

文獻 ^[8]  指出，最優化理論和非線性規劃方法已經被成功的運用到因特網去開發高效率的資源分配與擁塞控制方案。在通信網絡中的資源分配問題已經被建模成一個最優化問題：目標是在服從網絡資源限制的條件下去最大化資源綜合效用。然而，對於無線網絡，如何分配軟服務質量流量的資源還是一個重要的設計挑戰。從數學角度講，最大的困難來自於網絡效用最大化過程中軟服務流量的非凹方程。之前的結果只能找出次優的結果。面對這一挑戰，這篇文獻確立了一些關鍵性的定理去發現最優解。然後提出了一個針對軟服務質量的基於效用分配的完整算法，進而得到最優解。

文獻 ^[9]  指出，在網絡中的資源分配被投射進網絡效用最大化問題中。對於有線網絡中的擁塞控制和彈性流量已經有分佈式算法用於解決此問題。然而對於無彈性網絡包括軟服務質量流量的無線網絡的資源分配，這個問題還面臨着挑戰。首先，在無線網絡中，對用户的效用方程建模是很困難的。其次，軟服務質量流量的效用方程通常是非凹的，這樣導致網絡效用最優化問題在數學上很難解決。在和通常的網絡效用最優化理論存在偏差的情況下，這篇文獻提出了一個新奇的最優化模型，並且它的算法對於帶寬的分配接近在無線網絡中用户對於軟服務質量流量的渴望值。作者的模型利用軟服務流量的基本特徵。換言之，它需要一些優先的帶寬但是在正常的操作中允許一些靈活性。與基於效用的方法和解決方案，我們的方法避免通過使用偏愛的帶寬值為每個用户找到準確的效用方程表達式的困難。這加速了現實中無線網絡的操作。文章用實例核實了提出的模型和算法並且證明它的性能優於網絡效用最優化理論方法（NUM approach）。

Frank Kelly教授 ^[1]  的網路效用最優化理論（NUM）問題和解決方法是在滿足連接容量限制的條件下最優化綜合效用。它們是使用個體流的速率向量來表述和解決的。由於現有網路的結構，對於網絡服務提供者，單個流的速率在路由器裏一般上不是直接可測量的。然而，總共的流的速率是很方便獲得和調整的。在這篇文章裏，作者研究了通信網絡的NUM問題，但是從一個路由層的帶寬分配角度。通過使用廣義逆矩陣，作者提出了一個效用最優化路由層帶寬分配的一般模型和它的解決方案。它的目標方程和限制條件使用總的流的速率表示而不是像在NUM問題中使用單一流的速率向量表示。作者發現新提出的模型和Frank Kelly教授提出的NUM模型是等價的,因為它們得到同樣的最優狀態和它們的方案滿足給定的路由計劃.作者也討論了當路由矩陣是滿秩和在網絡中每一個連接有一個單跳流的的特殊情形。作者提出了一個對於後者的因特網基於協議的虛擬網絡的直接應用。作者展示了導出效用最優化總的流的速率向量的數學模型和解決方案，然後用數字實例更進一步的解釋了它們。 ^[10]