异构网络无线资源管理中的非合作博弈

　　收稿日期:2007-10-26　收修改稿日期:2007-12-11　基金项目:国家自然科学基金项目(60496315,60672059,60502023)资助;国家“八六三”计划项目(2006AA01Z233)资助.　作者简介:陈明欣,男,1979年生,博士研究生,主要研究方向为无线局域网和无线Ad hoc 的M AC 协议,异构无线网络的呼叫接纳控制和负载均衡;朱光喜,男,1945年生,教授,主要研究方向为网络、数字视频编码等;刘　干,男,1969年生,博士,主要研究方向为宽带无线通信与多媒体系统.

异构网络无线资源管理中的非合作博弈

陈明欣,朱光喜,刘　干

(华中科技大学电子与信息工程系,武汉光电国家实验室(筹),湖北武汉430074)E-mail:gxz hu@mail.hu st.edu.cn

摘　要:蜂窝网与无线局域的网融合网络可以为移动用户提供宽带连接以及可靠的服务质量保证.本文在这样的无线融合网络中提出非合作的博弈模型,用于网络的无线资源管理.首先,一个长期的博弈被提出用于指导两种网络对各类业务的带宽分配.然后,在此带宽分配的基础上,一个短期的博弈又被提出用于指导两种网络的呼叫接纳控制策略.通过求取这两个博弈的纳什均衡,可以使两种网络所获得的总效用都达到最大.

关键词:异构无线;博弈论;无线资源管理;接纳控制

中图分类号:T N 929.5　　　　　文献标识码:A 　　　　　　文章编号:1000-1220(2009)03-0446-05

Noncooperative Game for Radio Resource Management in Heterogeneous Wireless Networks

CHEN M ing -xin ,ZHU G uang -x i ,LI U Gan

(Depar tment of E lec tronics &I nf ormation Eng ineer ing ,H uaz hong Univ er sity o f S cience and T echnology ,W uhan N ational L aboratory f or Opto -elec tronics ,W uhan 430074,China )

Abstract :T he integ rat ed W L AN and cellular net wo rks w ill pro vide hig h -bandw idth connectiv ity with quality -of -serv ice (Q o S )

suppor t to mobile users in a seamless manner.We present a no nco oper ativ e g ame for ra dio reso ur ce m anag ement (i.e.,band-width allo cat ion and admission co nt ro l )in such a hetero geneo us w ir eless access env ir onment .First ,a long -ter m noncoo per a-tiv e game is used to o btain the bandw idth allo catio ns t o v arious tra ffics fro m the different a ccess netwo rks.Seco nd,ba sed on the obtained bandw idth allocation ,anot her sho rt -ter m no nco oper ativ e g ame is for mulated to obtain the admission contr ol .T he N ash equilibriums fo r bo th gam es g iv e the optimal radio resour ce management w hich max imizes the t otal utilities of each net-wo rk.

Key words :hetero geneo us w ir eless netwo r ks;game t heo ry ;r adio r esour ce manag ement;admissio n co ntro l

1　引　言

下一代无线网络的显著特点就是多种无线接入技术的融合为移动用户提供宽带连接以及可靠的服务质量保证.在这样的异构网络中,包括带宽分配和接纳控制的无线资源管理必须既满足移动用户的要求,又满足服务供应商的要求.

在异构环境中,不同的运营商管理着不同的网络,他们的目标都是获得最大的收益,在这种竞争的环境下,非合作的博弈将是分析无线资源管理的有效的方法.

近几年,博弈论被广泛地应用于无线网络中的资源管理.文献[1]将CD M A 网络中的接纳控制和速率分配描述成一个非合作的博弈.文献[2]通过CDM A 网络中接纳控制的博弈公平而有效地为网络中的各类业务分配资源.文献[3]提出了将网络和移动终端同时作为参与者的博弈模型,用于解决CDM A 网络中的接纳控制问题.此外,博弈论还被用于解决CDM A 网络的功率控制问题[4-8].然而,以上的研究工作都是运用博弈论解决单一网络中的资源分配问题.

最近,博弈论也渐渐用于异构无线网络中.文献[9]用博

弈模型解决了异构无线网络中移动终端的网络选择问题.Niyato 在[10]中提出了基于合作的博弈架构,用于异构无线网络中的带宽分配.此后,他又在[11]中提出了基于非合作的博弈架构,用于异构无线网络中的无线资源管理.然而,N iy a-t o 提出的博弈架构都没有将网络中的业务类型进行区分.本文提出了一种新的异构无线网络中基于博奕的无线资源管理策略,其目的是通过有效的带宽分配和接纳控制使网络的总效用最大化.本文将无线资源管理的问题分为两个部分:在网络级,将有限的资源合理地分配给各类不同的业务,为解决此问题,本文首先建立一个长期的博弈模型,通过求解纳什均衡(N ash equilibrium )获得合理的带宽分配策略;在呼叫级,对新呼叫请求进行有效的接纳控制,为解决此问题,本文在获得合理带宽分配的基础上建立一个短期的博弈模型,通过求解纳什均衡获得最佳的呼叫接纳控制策略.

2　长期的博弈

考虑如下页图1所示的异构无线网络,由一个U M T S 的蜂窝网络和一个IEEE802.11的无线局域网(W L AN )组成,

小型微型计算机系统Jo urnal of Chinese Co mput er Sy st ems 2009年3月第3期V ol.30N o.32009

WL A N 完全被蜂窝网覆盖.假定网络中的所有业务分为语音、视频和数据三类.图中N 1、N 2、N 3表示重叠覆盖区域三类业务的在线呼叫数,N 4、N 5、N 6表示非重叠覆盖区域的三类业务的在线呼叫数,N i (i ={1,…,6})是在某个策略周期内的统计值,一个策略周期内指的是带宽分配的策略保持不变的一个时间段.令c i (i ={1,2,…,6})表示蜂窝网分配给N i (i ={1,2,…,6})的带宽,令w i (i ={1,2,3})表示W L A N 分配给N i (i ={1,2,3})的带宽,则必然有

∑6

i =1c i ≤B c ,∑6

i =1

w i ≤B w ,其中B c 和B w 分别表示蜂窝网和WL A N 的总带宽

.

图1　异构无线网络区域分布

Fig.1　Ser vice ar eas in a heter og eneo us w ir eless netw or ks

首先,一个呼叫的效用函数定义如下:

U =B ・ln(A ・X )　　　

(1)

其中A 和B 分别表征效用函数的形状和尺度,X 表示呼叫所获得的带宽.(1)满足效用函数在有效区间内[1/A ,+∞)是一个凹函数的普遍特征.假定移动终端都是双模的,即处在重叠覆盖区域的移动终端可以在两种网络间进行垂直切换,而且移动终端总是倾向于能给予更多带宽的网络,这样,在稳定的情况下,两种网络给予重叠区域内同一类呼叫的带宽是相同的.

对两种网络而言,移动用户是它们共同的资源,为了使自身的收益最大化,它们之间必然存在竞争,因此可以用一个长期的非合作博弈来描述,下面给出长期的非合作博弈的表达式:

参与者:图1中所示的两种网络,即蜂窝网和WL A N .策略集:蜂窝网的策略集是c i (i ={1,2,…,6}),WL A N 的策略集是w i (i ={1,2,3}).

支付函数:蜂窝网的支付函数是将c i 的带宽分配给每类呼叫时蜂窝网中所有在线呼叫的效用的总和,W LA N 的支付函数是将w i 的带宽分配给每类呼叫时WL A N 中所有在线呼叫的效用的总和.

根据前面的说明,可以得到两种网络在分别采用策略集c i (i ={1,2,…,6})和w i (i ={1,2,3})情况下,蜂窝网的支付函数:

U Cellular =N 1B 1

N 2B 2N 3B 3ln N 4B 1ln A 1

c 4N 4+N 5B 2ln A 2

c 5

N 5+N 6B 3ln A 3

c 6

N 6

(2)以及WL A N :

U w lan =N 1B 1ln A 1c 1+w 1N 1-N 1B 1ln A 1

c 1

N 1+N 2B 2ln A 2c 2+w 2N 2-N 2B 2ln A 2

c 2

N 2+N 3B 3ln A 3c 3+w 3N 3-N 3B 3ln A 3

c 3

N 3

(3)(c i *,w j )什均衡,则必然有

U cellular (c *1,c *2,c *3,c *4,c *5,c *6,w *1,w *2,w *

3)≥

U cellular (c 1,c 2,c 3,c 4,c 5,c 6,w *1,w *2,w *3)　　P c 1,c 2,c 3,c 4,c 5,c 6

(4)

U w lan (c *1,c *2,c *3,c *4,c *5,c *6,w *1,w *2,w *

3)≥

U w lan (c *1,c *2,c *3,c *4,c *5,c *

6,w 1,w 2,w 3)　　P w 1,w 2,w 3(5)为了得到纳什均衡,我们采取以下的方法:将w i (i ={1,

2,3})看作常数,求使蜂窝网的支付函数最大化的策略集c i (i ={1,2,…,6}),即

M ax imiz e :U cellular (c 1,c 2,c 3,c 4,c 5,c 6)Subj ect to :

∑6

i =1

c i ≤B c

(6)

同样将c i (i ={1,2,…,6})看作常数,求使W LA N 的支付函数最大化的策略集w i (i ={1,2,3}),即

M ax imiz e :U w lan (w 1,w 2,w 3)

Subj ect to :∑3

i =1

w i ≤B w

(7)最后联立两组方程,求出纳什均衡.

为了求解(6)和(7),我们采用拉格朗日(L ag ra ng ian)算子法,(6)的拉格朗日函数定义如下:

L (c i ,K )=U cellular (c i )-K ・

∑6

i =1

c i -B c 　　　(8)

其中K 是拉格朗日算子,将(8)分别对c i (i ={1,2,…,6})

和K 求导,得到

c 1+w 1N 1B =c 2+w 2N 2B 2=c 3+w 3N 3B 3=c 4N 4B 1=c 5N 5B 2=c 6

N 6B 3∑6

i =1

c i =B c (9)

同样,(7)的拉格朗日函数定义如下:

L (w i ,K )=U w lan (w i )-K ・∑3

i =1

w i -B w 　　　(10)

将(10)分别对w i (i ={1,2,3})和K 求导,得到

c 1+w 1N 1B =c 2+w 2N 2B 2=c 3+w 3

N 3B 3∑3i =1

w i =B w (11)

联立(9)和(11),就可以求出纳什均衡.特别地,可以得到

　c *1=(B c +B w )N 1B 1

(N 1+N 4)B 1+(N 2+N 5)B 2+(N 3+N 6)B 3

-w *1

(12)447

3期　　　　　　　陈明欣等:异构网络无线资源管理中的非合作博弈　　

则在重叠覆盖区域的一个语音呼叫所能获得的带宽为

B 1-o =

c *1+w *

1

N 1

=(B c +B w )B 1

(N 1+N 4)B 1+(N 2+N 5)B 2+(N 3+N 6)B 3

(14)

而在非重叠区域的一个语音呼叫所能获得的带宽为

B 1-no =c *4N 4=(B c +B w )B 1

(N 1+N 4)B 1+(N 2+N 5)B 2+(N 3+N 6)B 3

(15)

可见,它们所获得的带宽是相同的,这说明在该博弈中,蜂窝网络不会为了获得更多的呼叫而将更多的带宽分配给重叠覆盖区域,影响到非重叠区域的呼叫的服务质量.换句话说,不会因为网络间的竞争而是使呼叫受到区别对待,对任意一个呼叫,无论它是处在重叠区域还是非重叠区域,它都能获得相同的带宽,因此,博弈的结果对呼叫来说是公平的.

3　短期的博弈

基于效用的呼叫接纳控制策略(Call admission contr ol ,CA C )的基本思想是:当有新呼叫请求时,网络先预测接纳新呼叫后的总效用,如果总效用增加则接纳新呼叫,否则拒绝新呼叫.然而网络中在线呼叫的数目是一个随机数,某一时刻在线呼叫的数目使网络的总效用最大,若此时对所有的新呼叫请求都拒绝,则当有呼叫离开却没有新呼叫补充时,信道就会出现相对空闲,从而降低网络的总效用,带来损失.为了降低这一潜在损失,在基于效用的呼叫接纳控制中,一个新呼叫的效用函数要在(1)的基础上增加一个修正项,使网络能够暂时地接纳更多的呼叫,而在线呼叫数的期望能使网络获得最大的效用.另一方面,网络中在线的呼叫数过多也会降低网络的总效用,因此修正项的加入也不能使网络中最大的在线呼叫数目过多.显然,此修正项与新呼叫的到达率相关,当新呼叫到达率越高时,信道相对空闲的概率越小,此时修正项应该越小,从而降低最大的在线呼叫数目.在极限情况下,当新呼叫到达率为无穷大时,只要有呼叫离开就立即会有新呼叫补充进来,因此只需要采取传统的基于效用的接纳控制策略,修正项应该为零.综上所述,两种网络中新呼叫的效用函数定义如下:

U (X ,K )=B ・ln(A ・X )+K ・ex p(-K )　　　

(16)

其中K 是新呼叫的到达率,系数K 表示网络的呼叫接纳

控制策略对到达率的敏感程度.

假定网络中的某类业务当前有n 个在线呼叫,则还能接纳新呼叫的条件是接纳后的网络总效用大于接纳前的网络总效用,即

　(n +1)B ln A ・B n +1+K ・ex p(-K )≥n B ln A ・B

n

(17)

其中B 宽,在下文中分别用c 和w 表示在蜂窝网和WL A N 中分配给此类业务的总带宽.由(17)可以得到能容纳此类呼叫的最大数目n max .假定在重叠覆盖区域到达的某类新呼叫中,有Q 的概率首先请求接入蜂窝网,(1-Q )的概率首先请求接入

WL A N ,只有在被拒绝时才请求接入另一个网络.若两种网络对此类呼叫的阻塞概率分别为C c 和C w ,则它们的等价呼叫

到达率为

K c =Q ・K +(1-Q )・K ・C w 　　　

(18)K w =Q

・K ・C c +(1-Q )・K 　　　(19)

建立如图2所示的M ar kov 模型来分析网络性能.

图2　呼叫的M ar kov 模型F ig .2　M arko v mo del for session

图中L 是只有一个在线呼叫时的呼叫离开率,即L =1/T ,其中T 为此类呼叫的平均持续时间.根据以上的M arko v 模型,我们可以得到在重叠覆盖区域,两种网络对此类呼叫的阻塞概率为

C c =

∏n ma x

-

c

i =1

K c

i ・L c

1+∑n max

-c k =1∏k

i =1K c i ・L c ,C w =∏n ma x

-

w

i =1

K w

i ・L w

1+∑n max -w

k =1∏

k

i =1K w

i ・L w

(20)此类呼叫在线数目的期望为

E (n c )=∑n

ma x -c j =1j ・∏j

i =1K c

i ・L c

1+∑n m a x -c k =1∏

k i =1K c i ・L c E (n w )=∑n

max -w j =1j ・∏j

i =1K w

i ・L w

1+∑n ma x -w k =1∏

k i =1K w i ・L w

(21)最后,可以得到两种网络在总效用的期望

E (U c )=E (n c )B ln A ・c

E (n c )

　　　(22)

E (U w )=E (n w )B ln A ・

w

E (n w )

　　　(23)

根据(16)～(23),可以得到E (U c )和E (U w )是关于K c 和K w 的函数,即

E (U c )=g c (K c ,K w )　　　(24)

E (U w )=g w (K w ,K c )　　　

(25)图3(见下页)给出了当K =0.2呼叫/秒,Q =0.,L c =L w

=0.003呼叫/秒,c =4M bps,w =3M bps,A =0.025和B =10时两种网络在重叠区域的此类呼叫的总效用随系数K c 和K w 的变化.从图中可以看到,当K w 取某个值时,存在一个最佳的K c 使蜂窝网的总效用达到最大,且当K w 的取值不同时,最佳的K c 也不同;同样,当K c 取某个值时,也存在一个K w 使WL A N 的总效用达到最大,且当K c 的取值不同时,最佳的K w 值也不同.

可见,为了使总效用最大,一个网络采取的最佳策略还与另一个网络采取的策略有关.因此,可以用一个博弈模型来描述两种网络在采取的策略上的关系,下面给出非合作的短期博弈的表达式:

448　　　　　　　　　小　型　微　型　计　算　机　系　统

　　　　　　　2009年

参与者:蜂窝网和WL A N .

策略集:蜂窝网的策略集是K ci (i ={1,2,3}),W LA N 的策略集是K w i (i ={1,2,3}).

支付函数:蜂窝网的支付函数是采用策略集K ci (i ={1,2,3})时蜂窝网中所有在线呼叫所获得的总效用的期望,W L A N 的支付函数是采用策略集K wi (i ={1,2,3})时WL A N 中所有在线呼叫所获得的总效用的期望

.

图3　网络的总效用随系数K 的变化

Fig.3　T otal utilities o f cellular and W L AN v s.K 如果一组纯策略(K ci *,K w j *)是该博弈的一个纳什均衡,则必然有

g ci (K *ci ,K *wi )≥g ci (K ci ,K *

w i )　P K ci 　i =1,2,3

(26)g w i (K *w i ,K *ci )≥g w i (K w i ,K *

ci )　P K w i 　i =1,2,3

(27)

为了求短期博弈的纳什均衡,我们采取倒推法.即先根据长期博弈的结果(即带宽的分配情况),利用(1)定义的效用函数求得最佳的在线呼叫数n op t -ci 和n op t -wi

,即

n op t -ci =ar g max n ci

n ci ・B i ・ln A i ・c i

n

ci

　　　

(28)

n op t -w i =ar g max n w i

n w i ・B w i ・ln A w i ・w i

n

w i

　　　(29)

然后令E (n ci )=n op t -ci 和E (n w i )=n op t -w i ,联立方程组(20)和(21),解出最大的呼叫数目n max -ci 、n max -w i 和阻塞率C ci 、C w i ,再通过(18)和(19)计算出K ci 和K w i 后,最后通过不等式(17)取等号后的等式就能得到最佳的系数K ci 和K w i .

综上所述,新的基于效用的呼叫接纳控制策略如下:当有新呼叫请求时,利用(1)和(16)以及本网络纳什均衡的策略集K 预测接纳新呼叫后的网络总效用,若总效用增加则接纳新呼叫,否则拒绝新呼叫,在判决的同时更新呼叫到达率K .

4　仿真与结果

考虑如图1所示的网络架构,长期博弈的参数设置如表1

所示,在线呼叫数N i (i ={2,…,6})保持不变,而N 1则从10到50变化.短期博弈的参数设置如表2所示,在重叠覆盖区域到达的此类呼叫中,首先选择蜂窝网接入的所占的比例从0.5到0.8变化.

表1　长期博弈的参数设置

T able 1　Pa rameter config urat ion o f lo ng -t erm g ame

语音视频数据重叠区域呼叫个数N 1=10～50N 2=30N 3=30非重叠区域呼叫个数

N 4=5N 5=5N 6=5A 0.0250.050.05B 10

205

B c 8M b ps B w

7M b ps

表2　短期博弈的参数配置

T able 2　P aram eter co nfigur atio n o f shor t-ter m g ame

蜂窝网

W LAN

L 1(呼叫/秒)

0.03

0.03

A 1

0.025B 1

10

分配给语音的带宽

4M bps 3M bp s 长期非合作博弈的纳什均衡结果如图4所示,可以看到,随着重叠覆盖区域的在线语音数呼叫越来越多,蜂窝网和

图4　长期博弈中N ash 均衡随N 1的变化F ig.4　N ash equilibr ium o f lo ng-t erm g ame v s.N 1

WL A N 都会划分越来越多的带宽给此类业务,同时压缩分配

给其它业务的带宽.在使网络总效用最大化的同时也使异构

网络中的同一类呼叫能获得相同的带宽.图5给出了长期博

图5　长期博弈中异构网络总效用的对比

F ig.5　T o tal ut ility o f heter og eneo us w ir eless netw or ks

under long -ter m game

449

3期　　　　　　　

陈明欣等:异构网络无线资源管理中的非合作博弈　　

弈中异构网络总效用的对比,其中带‘$’的曲线表示网络采取固定的带宽划分策略,即总是按照N 1=10时的纳什均衡结果划分带宽.可以看到随着N 1的增加,按照纳什均衡结果动态划分带宽的策略可以获得更多的网络总效用

.

图6　短期博弈中N ash 均衡随呼叫到达率的变化Fig.6　N ash equilibrium o f shor t-ter m g ame

v s .sessio n arr iv al r ate

短期非合作博弈的纳什均衡结果如图6所示,可以看到,在总到达率相同的情况下,随着Q 的增加,蜂窝网的呼叫到达率越来越高,W L A N 的呼叫到达率越来越低,因此,蜂窝网为了避免在线呼叫数过多则降低系数K c ,而W L AN 为了获得更多的呼叫则提高系数K w .此外,图中K =0.2呼叫/秒和K =0.22呼叫/秒时的不同结果也表明,在总到达率不同的

情

图7　短期博弈中网络总效用随呼叫到达率的变化

Fig.7　T otal utilities of cellular and W L A N under shor t -t erm g ame 况下,两种网络的纳什均衡策略也不相同.图7给出了在K =0.2呼叫/秒时采取博弈和不采取博弈的网络效用对比,其中带‘o ’的曲线表示不采取博弈(即K c =K c =0时)的网络效用.从图中可以看到,采取博弈后,两种网络的效用都保持在相对较高的值,且不随Q 的变化而变化.

5　结束语

本文提出了一种新的异构无线网络中基于博奕的无线资源管理策略,首先,提出一个长期的非合作博弈用于指导两种网络对各类业务的带宽分配.然后,在长期博弈的带宽分配基础上,又提出一个短期的非合作博弈用于指导两种网络的基于效用的呼叫接纳控制策略.通过求取这两个博弈的纳什均衡,可以使两种网络所获得的总效用最大化.References :

[1]Lin Hai -tao ,C hatterjee M ,Das S K ,et al .ARC :an integrated

admis sion and rate control fram ew ork for competitive w ireles s CDM A data netw ork s using noncooperative games [J ].IEEE T ransactions on M obile Compu tin g,M ay-June 2005,4(3):243-258.

[2]Virapanich aroen J ,Benjapolakul W .Fair -efficient th res hold pa-rameters selection in call admiss ion control for CDM A mobile mu ltimed ia com munications u sing game th eoretic fram ew ork [C].CCNC ø05,Jan.2005,439-444.

[3]Rousk as A N ,Kikilis A A ,Rats iatos S S .Adm ission control

and pricing in competitive w ireles s netw or ks b as ed on non-coop-erative game theory[C].W CNC ø06,vol.1:205-210.[4]Kosk ie S,Gajic Z.A nash gam e algorithm for SIR-based pow er

con tr ol in 3G wireless CDM A netw ork s [J ].IEE E /ACM T rans-actions on Netw orking ,Oct .2005,13(5):1017-1026.[5]M u sku M R,Chronopoulos A T,Popes cu D C.J oint r ate and

pow er con tr ol w ith pricing[C].GLOBECOM ø05.

[6]Alpcan T,Basar T ,Dey S.A power con trol gam e based on out-age probabilities for multicell w ireles s data netw orks [J ].IEEE T rans actions on W ireles s Commu nications,April 2006,5(4):0-9.

[7]M eshk ati F,M ung Chiang,Poor H V,et al.A game-theoretic

approach to energy-efficient pow er control in multicarrier CD-M A sys tems [J ].IEEE Journal on Selected Areas in C om muni-cations,June 2006,24(6):1115-1129.

[8]Fattahi A R,Pagan ini F.New econ omic per spectives for re-source allocation in wir eless netw orks [C ].Proceedings of American Control Conference ,J une 2005,6:3960-3965.[9]Antoniou J os eph ina,Pits illid es Andreas.4G conver ged environ-men t:m od elin g network selection as a game[C].M obile and

Wir eless Com munications Su mmit,J uly 2007,1-5.

[10]Niyato D,Hoss ain E.A cooperative game framew ork for band-w idth allocation in 4G heterogeneous wireless n etw orks [C ].ICC ø06,June 2006,9,4357-4362.

[11]Niyato D,Hoss ain E.A noncooper ative game-theoretic frame-w ork for radio r esour ce managem ent in 4G heterogeneou s w ire-less acces s n etw orks [J ].IEEE T ran sactions on M obile Comput-ing,2008,7(3):332-345.

450　　　　　　　　　小　型　微　型　计　算　机　系　统　　　　　　　2009年