擁塞管理模型在網絡對抗中的應用
2012-04-29 00:00:00潘偉
計算技術與自動化 2012年3期
摘要：分析一種在通訊網絡中進行擁塞管理的經濟模型。這個模型由用戶的效用函數和用戶對擁塞的延時敏感函數組成，并引入經濟學中邊際消費的概念來分析網絡系統的全局最優性。通過分析表明當用戶的效用函數均為線性且用戶對延時的敏感系數不等時所得到的全局最優點不是內點，即資源沒有達到最優分配，這可由改變效用函數的形式和使用戶對延時的敏感系數相等來彌補。數值算例說明了此種分析方法的正確性。
關鍵詞：擁塞； 效用函數； 延時敏感性； 邊際消費； 全局最優性
中圖分類號：TP393.07 文獻標識碼：A
The Application of Artillery Confrontation Networks based on the Model of Congestion Management
PAN Wei
（Electric Detection Department， Shenyang Artillery Academy， Shenyang110867，China）
Abstract：This paper analyzes an economic model of congestion control for a communication network. The model consists of the users’ utility functions and the functions of users’ sensitivity to delay. It applies the concept of marginalcost pricing to analyze the global optimality of the system. From the analysis， it shows that the interior point is not the global optimal point when the users’ utility functions are linear and the coefficients of the sensitivity to delay are not the same， so the resource allocation is not optimal. This can be settled by choosing some proper utility functions and making the sensitivity of the users’ to delay be same. Numerical examples certifies the validity of the analysis.
Key words：congestion；utility function；sensitivity to delay；marginal cost；global optimality
1引言
近幾年來，通訊網絡中通信量管理和通信量模型的研究已取得很大進展，流量控制是今天高速網絡資源和通信量管理的一個重要組成部分，流量控制是調整輸入端的傳送速率（即時鏈路容量）為網絡有效帶寬的最有效方法之一，同時網絡管理者常常利用流量控制協助進行擁塞控制，而制定合理的網絡資源分配原則以及網絡價格機制是流量控制的一種非常重要的手段。從經濟學角度分析通信網絡的流量控制和計費管理正逐漸成為一個非常有吸引力的研究方向。
網絡價控問題的研究直到近十多年來才引起眾多科學家們的注意，價控策略及流量管理策略的研究仍處在初級階段。劍橋大學統計實驗室Frank Kelly教授，寫了大量有關網絡資源分配和網絡定價的文章[1—7]，對網絡資源的生產容量與成本的關系進行了討論，同時假設用戶以達到盈余的最大而自愿選擇服務和付費為原則，給出了每個用戶分配的帶寬與用戶每單位時間所需付費金額成比例的這樣一個網絡資源分配和定價的最優化策略。
在經濟學理論中關于資源分配問題有一個很重要的概念——邊際消費，指在一個資源系統中，每個用戶所花費的價格除了與內部效應（由自身引起）有關外還與外部效應（由其他用戶引起）有關。本文的模型與 Kelly所提出模型的不同之處在于在模型中除了含有用戶的效用函數以外還有用戶對延時的敏感函數，用戶的敏感函數表示用戶對網絡擁塞反應的敏感性程度。
2系統模型
Kelly提出網絡系統中用戶可視為路由，與所對應的鏈路相連[2]，每名用戶的流量通過效用函數來反映，該函數是關于用戶速率的單調凸增函數。另外，用戶對延時是敏感的，一個用戶每個信息包的延時花費與信息包阻斷用戶的通道所導致的延時是成比例的。用戶的總延時即為用戶在用戶的通道上每種資源的延遲的總和。一種資源的延時被假設為基于所有用戶總流程的凹增函數，因而這里不涉及到優先級（可區分服務）。
計算技術與自動化2012年9月
第31卷第3期潘偉：擁塞管理模型在網絡對抗中的應用
本文以Kelly、Maulloo和Tan[8]（以下用KMT代替）提出的模型為出發點來分析網絡系統。考慮網絡源端集合（標記為j∈J）和用戶集合（標記為r∈R），這里每個r都是j的一個子集。設xr表示用戶r的速率，用戶r的效用函數記為Ur（xr）。用戶r由于擁塞而產生的延時所花費的費用為hr·d，假設用戶的平均延時d是相等的。設每個信息包（不考慮用戶）在資源j上經歷的平均延時等于Dj（yj），這里yj=∑r：j∈rxr為用戶的總速率，用戶r每單位時間的凈效用為：
Ur（xr）—hrxr∑J：j∈rDj（yj） （1）
網絡資源的全局最優分配問題可由下式表示：
max F（x，y）：=∑rUrxr—∑rhrxr∑J：j∈rDj（yj）
s.t.∑r：j∈rxr=yj，j∈Jxr≥0，r∈R（2）
對于一個只有一個源端的網絡，式（1）中給出的用戶凈效用表達式是MackieMason和Varian所闡述的一個特例[9]。
3價控策略的一階導數條件
KMT模型的內容與Stidham[10]， Rump 和Stidham[11]提出的模型相類似，其目的是通過一種基于對網絡中每個源端收取擁塞通行費的分散算法來解式（1）。概括地說，就是每名用戶r通過調整其速率以使式（1）最大化。通過設置使每個源端的使用費用等于作用在流程的這種資源邊際增加的外部影響，在總體最理想的方式下，促使單一用戶行為的最優化。更確切地說，是希望選擇基于一種資源的最佳擁塞費用，以形成Nash均衡流量分配，也是對問題（1）的一個理想的解決途徑。
對此問題的討論通常為邊際費用定價的特例，即一名用戶支付的總價格等于該用戶所用系統強加的邊際成本。邊際成本包含有二個部分：內部作用（在這種情況下為延時花費）由用戶的感知引起；外部作用由單一用戶強加給了所有其他用戶：處于問題中的用戶流量的邊際增加造成的所有用戶的總延時費用的增加。
考慮如下的Lagrangean問題：
L（x，y，μ）=∑rUr（xr）—∑rhrxr∑j：j∈rDj（yj）—
∑jμj（∑r：j∈rxr—yj）=∑r[Ur（xr）—
xr∑j：j∈r（hrDj（yj）+μj）]+∑jμjyj（3）
因此總體最理想的流量分配x將使每名用戶的流量xr滿足使下式最大化，
Ur（xr）—xr∑j：j∈r（hrDj（yj）+μj） （4）
考慮相關函數的可導性，下述一階KarushKuhnTuckerLagrange （KKTL）條件使問題（1） 最優是必要的：
U''r（xr）=∑j：j∈r（hrDj（yj）+μj）xr>0（5）
或
U''r（xr）≤∑j：j∈r（hrDj（yj）+μj）xr=0（6）
對所有的r∈R
yj=∑s：j∈sxs
μj=（∑s：j∈shsxs）D''j（yj）（7）
4邊際費用定價的不規則性
對經典的模型作如下假設：
假設1用戶的效用函數Ur（xr）均是可導的凸增函數。
假設2延時函數Dj（yj）均是可導的凹增函數。
由于式（2）的目標函數對于x=（xr，r∈R）不是嚴格凸的，模型不能滿足全局優化的規則性。通過列舉一些經濟模型來說明分類占優并不是一個罕見的現象，而是與收益和消費的選擇密切相關。換句話說，不能僅假設選擇合適的參數而使內點最優，實際上這樣的參數也是不存在的。問題的關鍵是由延時函數的非凹性導致目標函數的非凸性所致，而不在于約束條件的存在性。
含有一個源端和多個用戶的網絡系統在網絡應用中十分普遍，為了分析邊際消費的不規則性，考慮兩個用戶共用一個網絡源端的情況。目標函數如下：
F（x1，x2）=U1（x1）+U2（x2）—f（x1，x2） （8）
其中f（x1，x2） 表示系統中兩用戶的延時消費函數，本文只關注f（x1，x2）是關于延時函數的線性函數。即如下式所示：
f（x1，x2）=（h1x1+h2x2）D（x1+x2）（9）
因為僅有一個源端，D的下腳標被忽略。
假設用戶r 的每單位流量的延時消費函數為Hr（x1+x2），r=1，2，系統總的 延時消費是：
f（x1，x2）=x1H1（x1+x2）+x2H2（x1+x2）（10）
假設 Hr（y）是可導的凹增函數，很容易檢驗f（x1，x2） 是關于x1 和x2的凹函數。做如下的預測：
Δ：=2fx212fx22—2fx1x22（11）
需檢驗Δ的非負性。設
2fx21=2A+C，2fx22=2B+C，
2fx1x2=A+B+C
其中
A=H′1（x1+x2），B=H′2（x1+x2），
C=x1H″1（x1+x2）+x2H″2（x1+x2）
可以推出
Δ=（2A+2B）2—（A+B+C）2
=—（A—B）2
當A=B，即H''1（x1+x2）=H''2（x1+x2）時上式是0。因此，可以證明總的延時消費函數不是關于x1 和 x2的凹函數。實際上這個條件表明，在可行區間內f（x1，x2）對每點都不是凹的，除非兩用戶的 延時函數關于x的一階導數相同。在f（x1，x2）是關于延時函數的線性函數時，當且僅當h1=h2時，即用戶對延時的敏感性相同時， 才有可能使f（x1，x2）為非凸函數。
延時函數的非凹性能導致目標函數的一階導數條件在最優資源分配中是不充分的，因為資源的最優分配可能與用戶效用函數的不同形式有關。
考慮每個用戶的效用函數如下：
U1（x1）=k1x1，U2（x2）=k2x2
點對（x1，x2）的軌跡為 直線，則
x1+x2=y
y 資源的最優流量分配問題如下： max F（x，y）=k1x1+k2x2—x1H1（y）— x2H2（y） s.t.x1+x2=yx1≥0，x2≥0 由于目標函數和約束條件都是線性的，一個特殊的情況是x1，x2其中之一為 y，另一變量為0。 由一階導數條件，上述方程滿足 k1—H1（y）=k2—H2（y） 沿著這條直線，總流量y 和目標函數F（x1，x2）均為常數F（x1，x2）=u.。在這條直線上有兩個特殊的點（y，0），和 （0，y）， 滿足 F（y，0）=F（0，y）（12） 又因為F（y，0）≤F（x*1，0），F（0，y）≤F（0，x*2）（其中x*r 是用戶r 的最優流量分配），如果y滿足式（12），那么目標函數F（x1，x2）的系統最優解將受到單一用戶最優解的影響，這將在后面的討論中以數值例子加以說明。 用戶的效用函數Ur（xr）都是線性的，如果Ur（xr）是嚴格凸的，且其凸的程度超過延時函數的非凹的程度，可使內點為最優點。 5數值算例 以數值例子來說明邊際消費的不規則性，并給出解決的措施以使資源分配達到合理的優。 （1）U1（x1）和U2（x2）均為線性的且 h1≠h2 資源的最優流量分配問題如下： max F（x，y）=16x1+9x2— 4x11—x1—x2—x21—x1—x2 s.t.x1+x2<1x1≥0，x2≥0 一階導數條件的解為1=0.218，2=0.354。 單一用戶的最優解為x*1=0.5，x*2=0.667。 相應的目標函數的值分別為F（1，2）=3.81， F（x*1，0）=4，F（0，x*2）=4。 因而內點不是最優點，系統的最優解受到單一用戶最優解的影響，因而系統流量沒有達到最優分配，如圖1所示。 圖1當U1（x1）=16x1，U2（x2）=9x2時 的目標函數曲線 （2）U1（x1） 是嚴格凸的， U2（x2）是線性的且 h1=h2 資源的最優流量分配問題如下： max F（x，y）=2log （x1+1）+x2—x110—x1—x2—x210—x1—x2 s.t.x1+x2<10x1≥0，x2≥0 一階導數條件的解為1=1，2=5.837。 單一用戶的最優解為x*1=4.675，x*2=6.837。 相應的目標函數的值分別為F（1，2）=5.58，F（x*1，0）=2.59，F（0，x*2）=5.195。 因而內點是最優點，系統流量達到了最優分配，如圖2所示。 圖2當U1（x1）=2log （x1+1）U2（x2）=x2時 的目標函數曲線 （3）U1（x1） 是嚴格凸的， U2（x2）是線性的且 h1=h2： 資源的最優流量分配問題如下： max F（x，y）=3log （x1+1）+2log （x2+1）—x110—x1—x2—x210—x1—x2 s.t.x1+x2<10x1≥0，x2≥0 一階導數條件的解為1=3.8，2=5.86。 單一用戶的最優解為x*1=5.386，x*2=4.675。 相應的目標函數的值分別為F（1，2）=5.86， F（x*1，0）=4.395，F（0，x*2）=2.594。 因而內點是最優點，系統流量達到了最優分配，如圖3所示。 6結論 通過以上的數值例子可以看出，用戶對延時的敏感性不同，用戶的效用函數選擇不當都會導致網絡流量資源分配的不合理性，即導致“邊際消費”現象的發生，這只會使部分用戶單獨使用網絡時達到最優，而不能實現系統的總體消費最優，因而沒有達到資源的合理分配，不能激發更多的用戶使用網絡。如果用戶的效用函數選取得當，而且網絡規定用戶對延時的敏感性相同，即敏感系數相等，那么就使系統的內點為全局最優點，從而達到了資源的合理分配。可見，通過討論目標函數的特性來分析系統的資源配置，具有重要的現實意義，可幫助管理者制定更加合理的網絡規則，從而為其帶來更多收益。 圖3當U1（x1）=3log （x1+1），U2（x2）=2log （x2+1） 時的目標函數曲線 參考文獻 [1]F. Kelly， Charging and rate control for elastic traffic[J].European Transactions on Telecommunications， 1997，（8）：33—37. [2]F .Kelly， A. K. Maulloo， D. K. H. Tan Rate control in communication networks： shadow prices， proportional fairness， and stability[J].Journal of the Operational Research Society，1998，（49）：237—252. [3]R. Gibbens， F. Kelly Resource pricing and the evolution of congestion Control[J].Automatica， 1999，（35）：1969—1985. [4]R. Gibbens， F. Kelly Distributed connection acceptance control for aconnectionless network[J].Proc. 16th Int. Teletraffic Congr，1999：238—251. [5]F. Kelly Models for a selfmanaged Internet[J].Phil. Trans. R. Soc. Lond，2000，358：2335—2348. [6]F. Kelly， P. Key， S. Zachary Distributed admission control[J].IEEE J.Selected Areas Commun， 2000：789—801. [7]F. Kelly， Mathematical modelling of the Internet[J].Proc. 4th International Congress on Industrial and Applied Mathematics， 2000：1042—1049. [8]K.Balachandran， S. Radhakrishnan Extensions to class dominance Characteristics[J].Management Science，1994，（40）：1353—1360. [9]J.MacKieMason， H.Varian.Pricing congestible network resources[J].IEEE Journal on Selected Areas in Communications， 1995，（13）：1141—1149. [10]S. Stidham Pricing and capacity decisions for a service facility： stability， and multiple local optima[J].Management Science， 2002，（38）：1121—1139. [11]C.Rump， S.Stidham Stability and chaos in a service facility with adaptive customer response to congestion[J].Management Science，2003，44：246—261.
