馮慧斌，翁鯤鵬，余根堅（.閩江學院計算機科學系，福州35008；.富春通信股份有限公司通信技術研究院，福州350003）

基于勢力場博弈的無線網(wǎng)絡視頻流速率控制模型?

馮慧斌1，翁鯤鵬2，余根堅1
（1.閩江學院計算機科學系，福州350108；2.富春通信股份有限公司通信技術研究院，福州350003）

多媒體通信中如何對視頻流量速率進行高效公平分配是提升無線網(wǎng)絡性能的重要手段。應用勢力場博弈模型來研究無線網(wǎng)絡視頻流速率分配機制，根據(jù)視頻流特性建立了基于流量信噪比和流量速率為參數(shù)的勢力場效用函數(shù)，提出了基于勢力場博弈的無線網(wǎng)絡視頻流速率控制模型。證明了模型的納什均衡存在性及唯一性，并提出了勢力場博弈模型納什均衡的分布式求解算法。數(shù)值仿真驗證了勢力場博弈的納什均衡存在性，仿真結果表明了提出的模型能保證不同視頻流量間公平的速率分配，且由于提出的算法執(zhí)行方式是分布式的，能有效減輕網(wǎng)絡的負載。

無線網(wǎng)絡；多媒體通信；視頻流；速率控制；勢力場博弈；納什均衡

1 引言

隨著無線網(wǎng)絡的不斷應用和部署，在無線網(wǎng)絡中提供視頻和音頻等時延敏感的多媒體業(yè)務成為可能。多媒體通信中不僅要保證多媒體業(yè)務的QoS需求，而且也要保障多媒體視頻流量間的速率公平地分配。保障視頻流量等實時多媒體流間速率分配的公平性是無線網(wǎng)絡服務提供者一個重要的目標，也是保障整個無線網(wǎng)絡QoS的重要基礎。

無線網(wǎng)絡多媒體流量速率控制源于傳統(tǒng)通信網(wǎng)絡速率控制。文獻［1］研究了通信網(wǎng)絡速率控制問題，提出了分布式的通信網(wǎng)絡速率控制優(yōu)化框架，證明了網(wǎng)絡速率控制模型及算法穩(wěn)定性。隨著網(wǎng)絡越來越復雜，近年來很多研究人員應用博弈論研究網(wǎng)絡流量速率分配及控制。文獻［2］應用博弈論研究了寬帶通信網(wǎng)絡流量帶寬分配問題，提出了基于議價的通信網(wǎng)絡帶寬分配機制及框架。文獻［3］應用博弈論研究了無線局域網(wǎng)流量速率控制問題，提出了基于博弈論的流量控制算法，證明了網(wǎng)絡流量速率控制模型的納什均衡存在性及唯一性。通信網(wǎng)絡流量速率控制不僅包括彈性流量，而且也存在著大量時延敏感多媒體流量，如果假設網(wǎng)絡流量都為時延敏感多媒體流量，則網(wǎng)絡流量控制問題就成為多媒體通信流量速率控制問題。文獻［4］研究了視頻流端到端的速率控制機制，提出了基于對數(shù)的TRFC（TCP Friendly Rate Control）機制，能有效準確地估計網(wǎng)絡可用帶寬及顯著地提升視頻流媒體的平滑度。文獻［5］應用博弈論研究了視頻編碼中的最優(yōu)化碼率控制，提出了基于兩層的碼率控制算法。文獻［6］研究H.264框架中的速率控制，通過引入基本單元及線性預測模型，能自適應地對視頻流碼率進行控制。視頻編碼中的速率控制及相關模型的研究可見文獻［7，8］。文獻［9］應用信息論研究了多用戶多接入無線視頻通信中的最優(yōu)資源分配問題，應用貪婪算法對最優(yōu)資源分配策略進行求解，并給出了可獲得的視頻質(zhì)量的上界。文獻［10］應用合作博弈研究了多媒體流量管理策略，應用納什議價來實現(xiàn)多媒體用戶流量間帶寬分配。

上述應用博弈論研究多媒體流量控制的文獻都是假設流量是自私且理性的，流量之間不存在合作關系。本文假設網(wǎng)絡中流量自私地非合作博弈同時具有理性合作的趨勢，因此可借鑒勢力場博弈模型來研究新型的無線網(wǎng)絡視頻流速率分配機制，定義了博弈模型中的視頻流效用函數(shù)，提出了基于勢力場博弈的無線網(wǎng)絡視頻流速率控制模型，證明了提出的模型納什均衡存在性和唯一性，在此基礎給出了求解勢力場博弈納什均衡的視頻流分布式速率控制算法。數(shù)值仿真驗證了勢力場博弈的納什均衡存在性，仿真結果表明了提出的模型及分布式算法能保證不同視頻流量間公平的速率分配。

2 勢力場博弈模型

勢力場博弈簡稱PG（Potential Game），是非合作博弈論中的一種重要博弈模型。假設策略式非合作博弈模型G=｛I，S，｛φ（q）q∈I｝｝，其中I代表博弈參與者的集合，S代表參與者的策略空間集合即S≡S1×S2×…SI，定義φ（q）：S→R代表第q個博弈參與者的效用函數(shù)，其大小由所有博弈參與者的策略來決定。由于博弈每一個參與者為了最大化自身效用，必須根據(jù)所有博弈對手的策略選擇把自身選擇策略的范圍限定可用策略空間的子集內(nèi)，因此，可在上述基礎上給出勢力場博弈模型的具體定義。

定義1策略博弈模型G=｛I，S，｛φ（q）q∈I｝｝是一個勢力場博弈模型必須滿足下述兩個條件之一。

（1）存在著一個函數(shù)P：S→R使得對于所有的博弈參與者q∈I和策略向量（sq，s-q），（s′q，s-q）滿足等式

（2）存在一個函數(shù)P：S→R使得對于所有的博弈參與者q∈I和策略向量（sq，s-q），（s′q，s-q）滿足不等式

則可稱函數(shù)P：S→R為勢力場函數(shù)，滿足上述任一條件的策略博弈模型稱之為勢力場博弈模型。

在策略式非合作博弈模型中最重要的目標是證明模型的純策略納什均衡存在性和唯一性，但實際上并不是所有的策略式非合作博弈模型都存在純策略納什均衡，而且即使存在納什均衡，求解出唯一納什均衡也是非常困難的。而作為非合作策略博弈的一種特殊例子——勢力場博弈的納什均衡存在性和唯一性證明則相對簡單，文獻［11］給出了勢力場博弈的存在性和唯一性的證明定理。

定理1假設G=｛I，S，｛φ（q）q∈I｝｝是一個勢力場博弈模型，函數(shù)P：S→R為勢力場博弈的效用函數(shù)，如果集合S是一個完備的非空凸集，函數(shù)P在集合S上是一連續(xù)可微嚴格凸函數(shù)，則勢力場博弈模型G存在著納什均衡，且納什均衡是唯一的。

3 系統(tǒng)模型

假設網(wǎng)絡（如Wi-Fi網(wǎng)絡）中有N=｛1，2，…，N｝個節(jié)點通過無線接入點與不同異構網(wǎng)絡中的接收端進行通信，網(wǎng)絡中的節(jié)點si通過無線接入點向接收視頻流的目的節(jié)點Di傳輸視頻序列，系統(tǒng)示意圖如圖1所示。由于所有節(jié)點都必須共享公用的無線信道，即意味著無線節(jié)點必須競爭網(wǎng)絡資源來進行通信，假設信道帶寬是有限的且不能滿足所有節(jié)點發(fā)送視頻流的需求，接入點則必須制定相應的機制來給不同節(jié)點分配信道帶寬從而保證流量的服務質(zhì)量。由于假設所有節(jié)點發(fā)送都是視頻流量，而視頻流最重要的質(zhì)量指標為視頻流的率失真，因此在此

先引入將要使用視頻的率失真模型。

視頻序列在網(wǎng)絡傳輸過程中由于數(shù)據(jù)量過大必須對其進行壓縮，在量化過程中必須在失真、均方差錯誤和碼率3個特性中尋找平衡，通常來說高碼率可導致較小的失真，而低碼率可導致較大的失真。針對不同的視頻編碼標準研究人員提出了不同的率失真模型。不失一般性，引入常見的兩參數(shù)率失真模型，其表達式如下所示：

其中，參數(shù)α＞0和β＞0由視頻流的內(nèi)容特性來決定。由式（3）可知率失真是視頻流碼率的減函數(shù)，圖2給出了率失真與視頻流碼率的關系示意圖，從圖也可以看出，隨著R（即視頻流速率）的值不斷增大，率失真的值變得越來越小。

在視頻處理和編碼領域中，信噪比（PSNR）是一個比均方誤差（MSE）更普遍使用的度量指標，而且視頻流媒體的率失真與視頻源的PSNR存在著直接的關系，對于給定的率失真D，其對應的信噪比的表達式可用如下所示的表達式來求解：

把式（3）代入式（4）化簡可得

其中，γi=2ln255-lnαi，Ri表示視頻流的速率大小。

4 基于勢力場博弈的視頻流速率控制模型

假設網(wǎng)絡中的N個節(jié)點同時發(fā)送視頻流媒體給接入點，用Ri表示用戶流量i∈N的速率，則R=［R1，…，RN］代表網(wǎng)絡中的視頻流量速率向量。每一個視頻流用戶的目標是選擇相應的流量速率Ri去進行博弈最大化自身收益，用戶流量的博弈策略空間可表示為C｝，其必須滿足兩個條件：所有用戶流量速率不大于信道的帶寬且流量速率是非負的。用戶流量在策略空間定義相應的效用函數(shù)，與單純的網(wǎng)絡速率控制不一致的，本文考慮的是視頻流媒體的速率控制，所以效用函數(shù)必須考慮視頻流的度量指標，與網(wǎng)絡速率控制一致的是效用函數(shù)必須和網(wǎng)絡流量速率相關。假設視頻流在網(wǎng)絡中所獲的信噪比和流量造成網(wǎng)絡的擁塞程度為收益的主要度量指標，則可定義如下所示的效用函數(shù)：

其中，第一項代表用戶流量使用傳輸速率Ri的所獲收益，其為流量信噪比的嚴格凸函數(shù)，參數(shù)ai＞0表示流量i對信噪比的敏感程度；第二項代表用戶使用傳輸速率Ri所需支付成本，考慮到表示網(wǎng)絡中所有流量使用的累計帶寬，由于網(wǎng)絡流量所需帶寬總量大于信道帶寬C時，接入點必須丟棄數(shù)據(jù)包來保證網(wǎng)絡正常運行，通過收取相應的費用從而達到懲罰網(wǎng)絡中節(jié)點自私行為，參數(shù)bi＞0表示流量i對網(wǎng)絡丟包率敏感程度。流量的收益減去其所需支付的成本即為流量所獲總效用。

根據(jù)上述定義，可以給出視頻流媒體速率控制博弈的模型VFG=｛I，S，U｝，具體描述如下。

（1）博弈參與者（I）：N個視頻流媒體用戶。

（2）博弈策略（S）：博弈參與者的策略為Ri，用戶博弈策略空間為

（3）效用函數(shù)（U）：

根據(jù)式（7）寫出φ（Ri，R-i）和φ（R′i，R-i）的表達式并相減可得

把式（7）代入式（8）整理可得

同樣地，把博弈模型VFG的效用函數(shù)表達式相減可得

把式（6）代入式（10）并整理可得

從上述可以看出，非合作策略博弈模型效用函數(shù)的變化與提出的勢力場博弈模型的效用函數(shù)相等。因此，可建立如下所示的勢力場博弈模型，博弈模型Γ=｛Ω，Χ，φ（·）｝的具體描述如下。

（1）博弈參與者（Ω）：N個視頻流媒體用戶。

（2）博弈策略（Χ）：博弈參與者的策略為Ri，用戶博弈策略空間為

根據(jù)第2節(jié)的定義，可得提出的視頻流媒體博弈模型Γ是一個勢力場博弈模型，從而建立了基于勢力場博弈的無線網(wǎng)絡視頻流速率控制模型，模型的效用函數(shù)如式（7）所示。

5 納什均衡分析

根據(jù)上一節(jié)建立的勢力場博弈模型及勢力場效用函數(shù)，本節(jié)分析勢力場博弈模型納什均衡的存在性和唯一性，并對納什均衡的穩(wěn)定性進行相應的分析。由于上一節(jié)定義的視頻流媒體博弈模型Γ是一個勢力場博弈，根據(jù)文獻［11］給出的只要是勢力場博弈模型其必定存在著納什均衡的性質(zhì)，則可得如下所述的引理1。

上述引理表示勢力場博弈模型存在著納什均衡，其可能存在著多個納什均衡，上述條件并不保證納什均衡的唯一性，因為勢力場博弈模型的納什均衡唯一性有更為嚴格的條件。

由于博弈模型的策略空間為Χ=｛R∈RN：Ri≥0 and∑iRi≤C i∈Ω｝，因此可得博弈模型的策略空間是有界的非空凸集。對勢力場博弈模型效用函數(shù)求關于Ri的一階導數(shù)可得

同樣地，對勢力場博弈模型效用函數(shù)求關于Ri的二階導數(shù)可得

同樣，對勢力場博弈模型效用函數(shù)求二階混合偏導數(shù)可得

其中，ones（N）是所有元素都為1的N×N階矩陣。從式（16）可以看出矩陣Ga是正定的，從而可得出勢力場效用函數(shù)是連續(xù)可微嚴格凸函數(shù)。由于集合是一個完備的非空凸集，效用函數(shù)是一個在策略空間集合上是連續(xù)可微嚴格凸函數(shù)，因此在引理的基礎上根據(jù)定理1可給出提出的視頻流速率勢力場博弈模型納什均衡存在性及唯一性定理。

定理2無線網(wǎng)絡視頻流速率控制的勢力場博弈模型Γ=｛Ω，Χ，φ（·）｝，假設博弈參與者為網(wǎng)絡中的N個視頻流媒體用戶流量，每個博弈參與者的策略為Ri，且博弈策略空間為Χ=｛R∈RN：Ri≥0 andC i∈Ω｝，定義提出的勢力場博弈模型的效用函數(shù)為

則上述勢力場博弈模型不僅存在著納什均衡，且模型的納什均衡是唯一的。

從上述定理可知，定義的勢力場博弈模型存在著唯一納什均衡，可把定義的勢力場效用函數(shù)看作系統(tǒng)的Lyapunov函數(shù)，且由于勢力場效用函數(shù)是正定的，因此保證了Lyapunov函數(shù)的正定性，從而使得納什均衡能收斂于系統(tǒng)的穩(wěn)定點。因此，可通過相應的迭代算法來求解納什均衡。常用的勢力場博弈模型納什均衡分布式迭代求解算法有雅可比迭代法，因此也應用雅可比算法來求解勢力場博弈的納什均衡。算法首先在初始點開始進行迭代，第i+1次的策略是由第i次的策略加上效用函數(shù)在策略上的投影與步長大小乘積，算法的具體描述如下。

上述算法中的［x］+=max（x，0），參數(shù)α是迭代算法的步長大小，當算法逐漸收斂到最優(yōu)解時，該最優(yōu)解即為勢力場博弈的納什均衡，因此通過上述算法可分布式地進行迭代進而求得模型的納什均衡。

6 數(shù)值仿真

本節(jié)通過實驗來評估提出的基于勢力場博弈的無線網(wǎng)絡視頻流速率控制模型。假設網(wǎng)絡中有3個節(jié)點連接到無線接入點，網(wǎng)絡中的節(jié)點都能通過通信接口模塊（基于IEEE 802.11技術）接入到無線網(wǎng)絡中，每個節(jié)點都安裝有相應的視頻編解碼器，節(jié)點都同時地發(fā)送實時的視頻序列到接收端，實際的網(wǎng)絡拓撲圖如圖3所示。假設網(wǎng)絡中節(jié)點發(fā)送的視頻序列分別為Carphone、Foreman、Table，且視頻序列包括慢、中或快運動和平滑或復雜場景，視頻序列的編碼框架為H.264，而且通過改變量化參數(shù)或者碼率控制特性，能壓縮不同的碼率視頻從而可獲得不同的視頻質(zhì)量需求。

由于視頻的信噪比是與參數(shù)γi和βi相關，因此可以通過離線訓練來估計參數(shù)的值。假設對每一個視頻序列使用H.264進行編碼，文獻［12］給出了各種不同視頻序列最優(yōu)的參數(shù)如表1所示，其中各視頻序列的最小帶寬需求分別為202.554、228.168、297.781（kbit／s），且假設接入點信道帶寬容量C在執(zhí)行算法是固定不變的。

圖4給出了網(wǎng)絡中信道帶寬不斷變化時不同視頻序列流量在提出的分配算法與集中式最優(yōu)分配算法所分配的流量速率的比較示意圖。從圖可以看出，全局最優(yōu)分配算法相對于提出的分配算法能使得視頻流Carphone和Foreman獲得更多的帶寬分配，且對視頻流Table來說全局最優(yōu)分配算法所獲帶寬僅略小于提出的分配算法，從總體上來說全局最優(yōu)分配算法比提出的分配算法能對信道帶寬進行最優(yōu)的分配，但集中最優(yōu)分配算法實現(xiàn)最優(yōu)分配的基礎是需要擁有網(wǎng)絡中的節(jié)點全部信息，因此對無線網(wǎng)絡中接入點來說負載較大。而相對于全局最優(yōu)分配算法，從圖4可以看出，隨著信道帶寬不斷變化，提出的分配算法能使得各視頻流分配的速率差異很小，因此提出的分配算法相比全局最優(yōu)分配算法具有更好的公平性，而且提出的算法只需要無線網(wǎng)絡中節(jié)點的局部信息，其對無線網(wǎng)絡負載相比于全局集中式分配算法也更少。

圖5 給出了隨著網(wǎng)絡中的信道帶寬不斷變化時不同視頻序列流量在提出的分配算法與集中式最優(yōu)分配算法所獲信噪比的比較示意圖。從圖可知，全局最優(yōu)分配算法比提出的分配算法能使視頻流獲得較高的信噪比，但集中最優(yōu)算法需要擁有網(wǎng)絡中的結點全部信息，因此對網(wǎng)絡中說負載較大。而相對于全局最優(yōu)分配算法，提出的分配算法相比全局最優(yōu)分配算法具有較好的公平性，而且提出的算法只需要無線網(wǎng)絡中節(jié)點的局部信息，其對網(wǎng)絡負載相比于最優(yōu)分配算法也較少。

7 結束語

本文應用勢力場博弈研究了無線網(wǎng)絡視頻流速率控制模型，根據(jù)視頻流特性建立了基于信噪比和流量速率的勢力場效用函數(shù)，提出了基于勢力場博弈的無線網(wǎng)絡視頻流速率控制模型，證明提出的模型納什均衡存在性及唯一性，并給出了勢力場博弈模型納什均衡的分布式求解算法。仿真比較了提出的算法與集中式最優(yōu)分配算法性能，仿真結果表明提出的算法比集中式最優(yōu)分配算法更能保證流量間的公平帶寬分配，且由于提出的算法執(zhí)行方式是分布式的，其并不需要網(wǎng)絡中節(jié)點擁有網(wǎng)絡全局信息，因此能有效減輕網(wǎng)絡的負載。本文研究的網(wǎng)絡是具有固定接入點的無線網(wǎng)絡，對于無固定接入點的無線多跳網(wǎng)絡以及基于認知無線電的無線網(wǎng)絡視頻流量速率控制及分配，需要進一步研究。

［1］Kelly F，Maulloo A，Tan D.Rate control for communication networks：shadoWprices，proportional fairness and stability［J］.Journal of the Operational Research Society，1998，49（3）：237-252.

［2］Yaiche H，Mazumdar R，Rosenburg C.A game theoretic framework for bandwidth allocation and pricing in broadband networks［J］.IEEE／ACMTransactionson Networking，2000，8（5）：667-678.

［3］Dimitrios T，Tansu A，Nick B.Game Theoretic Rate Control for Mobile Devices［C］／／Proceedings of the 2009 International Conference on Game Theory for Networks.Istanbul，Turkey：IEEE，2009：646-652.

［4］Panagiotis P，Vassilis T.L-TFRC：An End-to-End congestion controlmechanisMfor video streaming over the internet［C］／／Proceedings of 2007 IEEE Global Telecommunications Conference.San Francisco，CA，US：IEEE，2007：309-312.

［5］Luo Jiancong.On using game theory to optimize the rate control in video coding［J］.IEEE Transactions on Circuits and Systems for Video Technology，2006，16（2）：209-218.

［6］Li ZG，Pan F，LiMK P，etal.Adaptive rate control for H. 264［J］.Journal of Visual Communication and Image Representation，2006，17（2）：376-406.

［7］He Zhihai，Mitra SK.A Linear Source Model and a Unified Rate Control AlgorithMfor DCT Video Coding［J］.IEEE Transactions on Circuits and Systems for Video Technology，2002，12（11）：970-982.

［8］Ding W，Liu B.Rate control of MPEG video coding and recording by rate.quantization modeling［J］.IEEE Transactions on Circuits Systemd for Video Technology，1996，6（1）：12-20.

［9］Shen C，van der Schaar M.Optimal resource allocation for multimedia applications overmultiaccess fading channels［J］. IEEE Transactions on Wireless Communication，2008，7（9）：3546-3557.

［10］Park H，van der Schaar.Bargaining strategies for networked multimedia resourcemanagement［J］.IEEE Transactions on Signal Processing，2007，55（7）：3496-3511.

［11］ScutariG，Barbarossa S，Palomar D P.Potential games：A framework for vector power control problems with Coupled Constraints［C］／／Proceedings of 2006 IEEE International Conference on Acoustics，Speech and Signal Processing. Toulouse，F(xiàn)rance：IEEE，2006：241-244.

［12］Chen Y，Wang B，Liu K J.Multiuser Rate Allocation Games for Multimedia Communications［J］.IEEE Transactions on Multimedia，2009，11（6）：1170-1181.

FENG Hui-bin was born in Suichuan，JiangxiProvince，in 1980. He received the Ph.D.degree froMNanjing University of Posts and Telecommunications in 2010.He is noWa lecturer.His research concerns radio resourcemanagement and cognitive radio network.

Email：35426918＠qq.com

翁鯤鵬（1976—），男，福建福州人，高級工程師，主要從事無線通信及網(wǎng)絡研究工作；

WENG Kun-peng was born in Fuzhou，F(xiàn)ujian Province，in 1976.He is noWa senior engineer.His research concerns wireless communication and network.

余根堅（1969—），男，福建古田人，副教授，主要從事無線通信及信息安全研究工作。

YUGen-jian was born in Gutian，F(xiàn)ujian Province，in 1969. He is noWan associate professor.His research concerns wireless communication and information security.

Wireless Network Video StreaMRate Control Model Based on Potential Game

FENGHui-bin1，WENGKun-peng2，YU Gen-jian1
（1.Department of Computer Science，Minjiang University，F(xiàn)uzhou 350108，China；2.Institute of Communication Technology，F(xiàn)uchun Communication Co.，Ltd.，F(xiàn)uzhou 350003，China）

Efficent and fair rate allocation for video streaMis the importantmeasure to upgrade thewireless network performance inmultimedia communication.In this paper，awireless network video streaMrate controlmodel and algorithMbased on potential game is proposed.The utility function on PSNR and floWrate is constructed according to the video streaMcharacteristic，thus thewireless network video streaMrate control based on potential game is proposed.The existence and uniqueness of the proposedmodel′s Nash equilibriuMis proved theoretically and a distributed algorithMto obtain Nash equilibriuMis proposed.Numerical simulation shows the proposed model can ensures different video streaMfair rate allocation，and it can lessen the network load efficiently.

wireless network；multimedia communication；video stream；rate control；potential game；Nash equilibrium

The National Natural Science Foundation of China（No.61163055）；The Natural Science Foundation of Fujian Province（2011J05155）

TN919.8

A

10.3969／j.issn.1001-893x.2012.11.021

馮慧斌（1980—），男，江西遂川人，2010年于南京郵電大學獲博士學位，現(xiàn)為講師，主要研究方向為無線資源管理、認知無線電網(wǎng)絡；

1001-893X（2012）11-1810-07

2012-06-11；

2012-08-16

國家自然科學基金資助項目（61163055）；福建省自然科學基金資助項目（2011J05155）