基于势力场博弈的无线网络视频流速率控制模型✴

冯慧斌，翁鲲鹏，余根坚（.闽江学院计算机科学系，福州35008；.富春通信股份有限公司通信技术研究院，福州350003）

基于势力场博弈的无线网络视频流速率控制模型✴

冯慧斌1，翁鲲鹏2，余根坚1
（1.闽江学院计算机科学系，福州350108；2.富春通信股份有限公司通信技术研究院，福州350003）

多媒体通信中如何对视频流量速率进行高效公平分配是提升无线网络性能的重要手段。应用势力场博弈模型来研究无线网络视频流速率分配机制，根据视频流特性建立了基于流量信噪比和流量速率为参数的势力场效用函数，提出了基于势力场博弈的无线网络视频流速率控制模型。证明了模型的纳什均衡存在性及唯一性，并提出了势力场博弈模型纳什均衡的分布式求解算法。数值仿真验证了势力场博弈的纳什均衡存在性，仿真结果表明了提出的模型能保证不同视频流量间公平的速率分配，且由于提出的算法执行方式是分布式的，能有效减轻网络的负载。

无线网络；多媒体通信；视频流；速率控制；势力场博弈；纳什均衡

1 引言

随着无线网络的不断应用和部署，在无线网络中提供视频和音频等时延敏感的多媒体业务成为可能。多媒体通信中不仅要保证多媒体业务的QoS需求，而且也要保障多媒体视频流量间的速率公平地分配。保障视频流量等实时多媒体流间速率分配的公平性是无线网络服务提供者一个重要的目标，也是保障整个无线网络QoS的重要基础。

无线网络多媒体流量速率控制源于传统通信网络速率控制。文献［1］研究了通信网络速率控制问题，提出了分布式的通信网络速率控制优化框架，证明了网络速率控制模型及算法稳定性。随着网络越来越复杂，近年来很多研究人员应用博弈论研究网络流量速率分配及控制。文献［2］应用博弈论研究了宽带通信网络流量带宽分配问题，提出了基于议价的通信网络带宽分配机制及框架。文献［3］应用博弈论研究了无线局域网流量速率控制问题，提出了基于博弈论的流量控制算法，证明了网络流量速率控制模型的纳什均衡存在性及唯一性。通信网络流量速率控制不仅包括弹性流量，而且也存在着大量时延敏感多媒体流量，如果假设网络流量都为时延敏感多媒体流量，则网络流量控制问题就成为多媒体通信流量速率控制问题。文献［4］研究了视频流端到端的速率控制机制，提出了基于对数的TRFC（TCP Friendly Rate Control）机制，能有效准确地估计网络可用带宽及显著地提升视频流媒体的平滑度。文献［5］应用博弈论研究了视频编码中的最优化码率控制，提出了基于两层的码率控制算法。文献［6］研究H.264框架中的速率控制，通过引入基本单元及线性预测模型，能自适应地对视频流码率进行控制。视频编码中的速率控制及相关模型的研究可见文献［7，8］。文献［9］应用信息论研究了多用户多接入无线视频通信中的最优资源分配问题，应用贪婪算法对最优资源分配策略进行求解，并给出了可获得的视频质量的上界。文献［10］应用合作博弈研究了多媒体流量管理策略，应用纳什议价来实现多媒体用户流量间带宽分配。

上述应用博弈论研究多媒体流量控制的文献都是假设流量是自私且理性的，流量之间不存在合作关系。本文假设网络中流量自私地非合作博弈同时具有理性合作的趋势，因此可借鉴势力场博弈模型来研究新型的无线网络视频流速率分配机制，定义了博弈模型中的视频流效用函数，提出了基于势力场博弈的无线网络视频流速率控制模型，证明了提出的模型纳什均衡存在性和唯一性，在此基础给出了求解势力场博弈纳什均衡的视频流分布式速率控制算法。数值仿真验证了势力场博弈的纳什均衡存在性，仿真结果表明了提出的模型及分布式算法能保证不同视频流量间公平的速率分配。

2 势力场博弈模型

势力场博弈简称PG（Potential Game），是非合作博弈论中的一种重要博弈模型。假设策略式非合作博弈模型G=｛I，S，｛φ（q）q∈I｝｝，其中I代表博弈参与者的集合，S代表参与者的策略空间集合即S≡S1×S2×…SI，定义φ（q）：S→R代表第q个博弈参与者的效用函数，其大小由所有博弈参与者的策略来决定。由于博弈每一个参与者为了最大化自身效用，必须根据所有博弈对手的策略选择把自身选择策略的范围限定可用策略空间的子集内，因此，可在上述基础上给出势力场博弈模型的具体定义。

定义1策略博弈模型G=｛I，S，｛φ（q）q∈I｝｝是一个势力场博弈模型必须满足下述两个条件之一。

（1）存在着一个函数P：S→R使得对于所有的博弈参与者q∈I和策略向量（sq，s-q），（s′q，s-q）满足等式

（2）存在一个函数P：S→R使得对于所有的博弈参与者q∈I和策略向量（sq，s-q），（s′q，s-q）满足不等式

则可称函数P：S→R为势力场函数，满足上述任一条件的策略博弈模型称之为势力场博弈模型。

在策略式非合作博弈模型中最重要的目标是证明模型的纯策略纳什均衡存在性和唯一性，但实际上并不是所有的策略式非合作博弈模型都存在纯策略纳什均衡，而且即使存在纳什均衡，求解出唯一纳什均衡也是非常困难的。而作为非合作策略博弈的一种特殊例子——势力场博弈的纳什均衡存在性和唯一性证明则相对简单，文献［11］给出了势力场博弈的存在性和唯一性的证明定理。

定理1假设G=｛I，S，｛φ（q）q∈I｝｝是一个势力场博弈模型，函数P：S→R为势力场博弈的效用函数，如果集合S是一个完备的非空凸集，函数P在集合S上是一连续可微严格凸函数，则势力场博弈模型G存在着纳什均衡，且纳什均衡是唯一的。

3 系统模型

假设网络（如Wi-Fi网络）中有N=｛1，2，…，N｝个节点通过无线接入点与不同异构网络中的接收端进行通信，网络中的节点si通过无线接入点向接收视频流的目的节点Di传输视频序列，系统示意图如图1所示。由于所有节点都必须共享公用的无线信道，即意味着无线节点必须竞争网络资源来进行通信，假设信道带宽是有限的且不能满足所有节点发送视频流的需求，接入点则必须制定相应的机制来给不同节点分配信道带宽从而保证流量的服务质量。由于假设所有节点发送都是视频流量，而视频流最重要的质量指标为视频流的率失真，因此在此

先引入将要使用视频的率失真模型。

视频序列在网络传输过程中由于数据量过大必须对其进行压缩，在量化过程中必须在失真、均方差错误和码率3个特性中寻找平衡，通常来说高码率可导致较小的失真，而低码率可导致较大的失真。针对不同的视频编码标准研究人员提出了不同的率失真模型。不失一般性，引入常见的两参数率失真模型，其表达式如下所示：

其中，参数α＞0和β＞0由视频流的内容特性来决定。由式（3）可知率失真是视频流码率的减函数，图2给出了率失真与视频流码率的关系示意图，从图也可以看出，随着R（即视频流速率）的值不断增大，率失真的值变得越来越小。

在视频处理和编码领域中，信噪比（PSNR）是一个比均方误差（MSE）更普遍使用的度量指标，而且视频流媒体的率失真与视频源的PSNR存在着直接的关系，对于给定的率失真D，其对应的信噪比的表达式可用如下所示的表达式来求解：

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

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

4 基于势力场博弈的视频流速率控制模型

假设网络中的N个节点同时发送视频流媒体给接入点，用Ri表示用户流量i∈N的速率，则R=［R1，…，RN］代表网络中的视频流量速率向量。每一个视频流用户的目标是选择相应的流量速率Ri去进行博弈最大化自身收益，用户流量的博弈策略空间可表示为C｝，其必须满足两个条件：所有用户流量速率不大于信道的带宽且流量速率是非负的。用户流量在策略空间定义相应的效用函数，与单纯的网络速率控制不一致的，本文考虑的是视频流媒体的速率控制，所以效用函数必须考虑视频流的度量指标，与网络速率控制一致的是效用函数必须和网络流量速率相关。假设视频流在网络中所获的信噪比和流量造成网络的拥塞程度为收益的主要度量指标，则可定义如下所示的效用函数：

其中，第一项代表用户流量使用传输速率Ri的所获收益，其为流量信噪比的严格凸函数，参数ai＞0表示流量i对信噪比的敏感程度；第二项代表用户使用传输速率Ri所需支付成本，考虑到表示网络中所有流量使用的累计带宽，由于网络流量所需带宽总量大于信道带宽C时，接入点必须丢弃数据包来保证网络正常运行，通过收取相应的费用从而达到惩罚网络中节点自私行为，参数bi＞0表示流量i对网络丢包率敏感程度。流量的收益减去其所需支付的成本即为流量所获总效用。

根据上述定义，可以给出视频流媒体速率控制博弈的模型VFG=｛I，S，U｝，具体描述如下。

（1）博弈参与者（I）：N个视频流媒体用户。

（2）博弈策略（S）：博弈参与者的策略为Ri，用户博弈策略空间为

（3）效用函数（U）：

根据式（7）写出φ（Ri，R-i）和φ（R′i，R-i）的表达式并相减可得

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

同样地，把博弈模型VFG的效用函数表达式相减可得

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

从上述可以看出，非合作策略博弈模型效用函数的变化与提出的势力场博弈模型的效用函数相等。因此，可建立如下所示的势力场博弈模型，博弈模型Γ=｛Ω，Χ，φ（·）｝的具体描述如下。

（1）博弈参与者（Ω）：N个视频流媒体用户。

（2）博弈策略（Χ）：博弈参与者的策略为Ri，用户博弈策略空间为

根据第2节的定义，可得提出的视频流媒体博弈模型Γ是一个势力场博弈模型，从而建立了基于势力场博弈的无线网络视频流速率控制模型，模型的效用函数如式（7）所示。

5 纳什均衡分析

根据上一节建立的势力场博弈模型及势力场效用函数，本节分析势力场博弈模型纳什均衡的存在性和唯一性，并对纳什均衡的稳定性进行相应的分析。由于上一节定义的视频流媒体博弈模型Γ是一个势力场博弈，根据文献［11］给出的只要是势力场博弈模型其必定存在着纳什均衡的性质，则可得如下所述的引理1。

上述引理表示势力场博弈模型存在着纳什均衡，其可能存在着多个纳什均衡，上述条件并不保证纳什均衡的唯一性，因为势力场博弈模型的纳什均衡唯一性有更为严格的条件。

由于博弈模型的策略空间为Χ=｛R∈RN：Ri≥0 and∑iRi≤C i∈Ω｝，因此可得博弈模型的策略空间是有界的非空凸集。对势力场博弈模型效用函数求关于Ri的一阶导数可得

同样地，对势力场博弈模型效用函数求关于Ri的二阶导数可得

同样，对势力场博弈模型效用函数求二阶混合偏导数可得

其中，ones（N）是所有元素都为1的N×N阶矩阵。从式（16）可以看出矩阵Ga是正定的，从而可得出势力场效用函数是连续可微严格凸函数。由于集合是一个完备的非空凸集，效用函数是一个在策略空间集合上是连续可微严格凸函数，因此在引理的基础上根据定理1可给出提出的视频流速率势力场博弈模型纳什均衡存在性及唯一性定理。

定理2无线网络视频流速率控制的势力场博弈模型Γ=｛Ω，Χ，φ（·）｝，假设博弈参与者为网络中的N个视频流媒体用户流量，每个博弈参与者的策略为Ri，且博弈策略空间为Χ=｛R∈RN：Ri≥0 andC i∈Ω｝，定义提出的势力场博弈模型的效用函数为

则上述势力场博弈模型不仅存在着纳什均衡，且模型的纳什均衡是唯一的。

从上述定理可知，定义的势力场博弈模型存在着唯一纳什均衡，可把定义的势力场效用函数看作系统的Lyapunov函数，且由于势力场效用函数是正定的，因此保证了Lyapunov函数的正定性，从而使得纳什均衡能收敛于系统的稳定点。因此，可通过相应的迭代算法来求解纳什均衡。常用的势力场博弈模型纳什均衡分布式迭代求解算法有雅可比迭代法，因此也应用雅可比算法来求解势力场博弈的纳什均衡。算法首先在初始点开始进行迭代，第i+1次的策略是由第i次的策略加上效用函数在策略上的投影与步长大小乘积，算法的具体描述如下。

上述算法中的［x］+=max（x，0），参数α是迭代算法的步长大小，当算法逐渐收敛到最优解时，该最优解即为势力场博弈的纳什均衡，因此通过上述算法可分布式地进行迭代进而求得模型的纳什均衡。

6 数值仿真

本节通过实验来评估提出的基于势力场博弈的无线网络视频流速率控制模型。假设网络中有3个节点连接到无线接入点，网络中的节点都能通过通信接口模块（基于IEEE 802.11技术）接入到无线网络中，每个节点都安装有相应的视频编解码器，节点都同时地发送实时的视频序列到接收端，实际的网络拓扑图如图3所示。假设网络中节点发送的视频序列分别为Carphone、Foreman、Table，且视频序列包括慢、中或快运动和平滑或复杂场景，视频序列的编码框架为H.264，而且通过改变量化参数或者码率控制特性，能压缩不同的码率视频从而可获得不同的视频质量需求。

由于视频的信噪比是与参数γi和βi相关，因此可以通过离线训练来估计参数的值。假设对每一个视频序列使用H.264进行编码，文献［12］给出了各种不同视频序列最优的参数如表1所示，其中各视频序列的最小带宽需求分别为202.554、228.168、297.781（kbit／s），且假设接入点信道带宽容量C在执行算法是固定不变的。

图4给出了网络中信道带宽不断变化时不同视频序列流量在提出的分配算法与集中式最优分配算法所分配的流量速率的比较示意图。从图可以看出，全局最优分配算法相对于提出的分配算法能使得视频流Carphone和Foreman获得更多的带宽分配，且对视频流Table来说全局最优分配算法所获带宽仅略小于提出的分配算法，从总体上来说全局最优分配算法比提出的分配算法能对信道带宽进行最优的分配，但集中最优分配算法实现最优分配的基础是需要拥有网络中的节点全部信息，因此对无线网络中接入点来说负载较大。而相对于全局最优分配算法，从图4可以看出，随着信道带宽不断变化，提出的分配算法能使得各视频流分配的速率差异很小，因此提出的分配算法相比全局最优分配算法具有更好的公平性，而且提出的算法只需要无线网络中节点的局部信息，其对无线网络负载相比于全局集中式分配算法也更少。

图5 给出了随着网络中的信道带宽不断变化时不同视频序列流量在提出的分配算法与集中式最优分配算法所获信噪比的比较示意图。从图可知，全局最优分配算法比提出的分配算法能使视频流获得较高的信噪比，但集中最优算法需要拥有网络中的结点全部信息，因此对网络中说负载较大。而相对于全局最优分配算法，提出的分配算法相比全局最优分配算法具有较好的公平性，而且提出的算法只需要无线网络中节点的局部信息，其对网络负载相比于最优分配算法也较少。

7 结束语

本文应用势力场博弈研究了无线网络视频流速率控制模型，根据视频流特性建立了基于信噪比和流量速率的势力场效用函数，提出了基于势力场博弈的无线网络视频流速率控制模型，证明提出的模型纳什均衡存在性及唯一性，并给出了势力场博弈模型纳什均衡的分布式求解算法。仿真比较了提出的算法与集中式最优分配算法性能，仿真结果表明提出的算法比集中式最优分配算法更能保证流量间的公平带宽分配，且由于提出的算法执行方式是分布式的，其并不需要网络中节点拥有网络全局信息，因此能有效减轻网络的负载。本文研究的网络是具有固定接入点的无线网络，对于无固定接入点的无线多跳网络以及基于认知无线电的无线网络视频流量速率控制及分配，需要进一步研究。

［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，France：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—），男，福建福州人，高级工程师，主要从事无线通信及网络研究工作；

WENG Kun-peng was born in Fuzhou，Fujian Province，in 1976.He is noWa senior engineer.His research concerns wireless communication and network.

余根坚（1969—），男，福建古田人，副教授，主要从事无线通信及信息安全研究工作。

YUGen-jian was born in Gutian，Fujian 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，Fuzhou 350108，China；2.Institute of Communication Technology，Fuchun Communication Co.，Ltd.，Fuzhou 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年于南京邮电大学获博士学位，现为讲师，主要研究方向为无线资源管理、认知无线电网络；

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

2012-06-11；

2012-08-16

国家自然科学基金资助项目（61163055）；福建省自然科学基金资助项目（2011J05155）