异构网络中基于Stackelberg博弈的资源分配方案

胡弦锋，郑 霖

(桂林电子科技大学 通信与信息学院，广西 桂林 541004)



异构网络中基于Stackelberg博弈的资源分配方案

胡弦锋，郑 霖

(桂林电子科技大学 通信与信息学院，广西 桂林 541004)

针对异构网络中资源分配问题，文中结合用户业务需求多样性，提出了一种基于Stackelberg博弈的资源分配方案。在该方案中，互联代理节点(Agent Node)作为领导者(Leader)制定价格策略，用户作为跟随者(Follower)，根据自身业务需求，在多互联节点间进行接入选择，以满足自身QoS需求。文中证明了在代理节点的价格确定后，用户之间非合作博弈纳什均衡点的存在性。仿真结果表明，所提出的资源分配方案，可以提高网络总的带宽利用率，提升用户对带宽接入的满意程度。

异构网络; 无线资源分配; Stackelberg博弈; 多点接入

在异构融合的网络环境下，用户通常被多个无线网络覆盖，通过接入不同的网络来满足自身的QoS需求。但带宽资源[1]、频谱资源[2]和功率资源[3]等网络资源是有限的，每个用户都希望在网络中获得最好的服务体验，这就造成了用户之间对网络资源的竞争。同时，网络运营者也希望通过合理的网络资源分配，来提高网络的吞吐量和网络资源利用率，所以对无线资源的管理和分配，成为异构网络融合关键技术研究的重点之一。

异构无线网络进行联合无线资源管理[4](Joint Radio Resource Management，JRRM)主要分为集中式，分布式和混合式管理模式。在分布式的管理模式下，用户选择如何接入网络、网络如何分配无线资源，是影响用户QoS和网络性能的主要因素，常用的网络选择和资源分配方法可以分为多属性决策法[5-6]、最优化方法[7]、马尔科夫链法[8]、模糊逻辑法[9-10]和博弈论方法[11-13]等。

本文提出利用Stackelberg博弈模型，在无线自组织网络与蜂窝网融合的情况下，对网络带宽资源进行分配。处于自组织网络中的移动用户(Mobile Users)，可以同时向多个同时处于蜂窝网的代理节点(Agent Nodes)申请带宽资源，如图1所示。代理节点通过网络定价，来影响移动用户的带宽策略，使自身效用最大化。在本文中，不仅考虑了不同优先级用户对带宽的竞争、代理节点与用户相互之间的交互，同时，也对代理节点和所竞争代理节点的网络状态进行考虑，制定出最优价格策略。文中证明了在代理节点制定价格策略后，移动用户所制定的效用函数满足凹函数的特性，保证了移动用户间构成的非合作博弈纳什均衡的存在，最后利用分布式迭代算法，使系统收敛到均衡点。仿真结果表明，本文所提算法提升了移动用户的QoS满意度，提高了网络带宽利用率。

图1 网络模型

1 系统模型

考虑在无线自组织网络和蜂窝网融合的架构[14]下，有m个代理节点位于蜂窝网边缘，在代理节点的覆盖范围内有n个移动用户。由于多模终端的出现，移动用户可以同时接入多个代理节点，向多个代理节点申请网络资源。网络资源大致可以分为带宽资源、功率资源等，文中蜂窝网总带宽用B表示。不同移动用户业务类型不同，所以不同移动用户有各自的业务优先级，设定移动用户优先级集合为θ={θ1,θ2,…,θn}，同时，不同业务优先级的用户具有不同的带宽需求，设定移动用户带宽需求集合为R={r1,r2,…,rn}。代理节点通过定价来影响移动用户的带宽策略，设P={p1,p2,…,pm}为所有代理节点价格策略集合。

由于移动用户都希望通过制定相应的带宽策略，来使自己的收益最大化，这种自私的行为使得移动用户之间的竞争构成了一个非合作博弈，非合作博弈往往会引起网络的低效性。但是，通过代理节点的引导，可以有效提高网络的性能。

1.1 基于Stackelberg 贝叶斯博弈的资源分配

Stackelberg模型中主要要素有：领导者、跟随者、效用函数和行动策略。

领导者：将代理节点定义为领导者(Leader)，领导者根据自身能耗约束和竞争对手策略变化，来制定自己的价格策略，使自身利益最大化。

跟随者：将自组织网络中的移动用户定义为跟随者(Follower)，跟随者在领导者作出决策后，根据领导者的价格策略，来制定自身的带宽需求策略。

行动策略：移动用户的策略是向代理节点申请带宽，而代理节点的策略是制定带宽价格，从而使自身在为其他节点服务中获取更高的利益。

效用函数：是研究博弈的一个重要衡量手段。对于代理节点，效用函数为所出售带宽给自己带来的经济效益。对于移动用户，效用不仅要考虑所得带宽给自己带来的利益，同时还得考虑购买带宽所产生的开销。

1.2 移动用户效用函数

移动用户对带宽的竞争，构成了非合作博弈关系。用户根据效用函数制定带宽需求策略，以使自身利益最大化，通常用户效用函数由两部分组成：带宽所带来的收益和获得收益所产生的花销。对于移动用户i(i=1,2,…,n)，其效用函数Fi(p,qi,q-i)可以表示为

Fi(p,qi,q-i)=Ui(qi)-Ci(p,qi)

(1)

其中，qi表示用户i的带宽策略集合；q-i表示其他用户的带宽策略集合，式(1)中前一项为带宽给用户带来的收益，这里采用对数效用函数形式[15]来表示

(2)

式中，qij为移动用户i向代理节点j申请的带宽量；θi为移动用户的优先级，由于用户业务优先级的不同，不同移动用户对带宽资源的竞争力不同。移动用户业务优先级越高，在带宽竞争中越有竞争力。式(1)后一项表示用户开销，为

(3)

式中，pj为代理节点j的定价；Dij表示用户i到代理节点j的距离因子，由于距离会使用户产生额外开销，所以Dij>1，离代理节点越近，由距离产生的开销越小，Dij越小，这里引入距离因子来反映距离给用户带来的开销。于是，用户i的效用函数可以表示为

(4)

1.3 移动用户纳什均衡点及证明

定理 当代理节点公布定价策略P={p1,p2,…,pn}后，移动用户的非合作博弈存在唯一纳什均衡解[16]。

证明 根据博弈论可知，博弈论模型满足以下两个条件，则存在纳什均衡：(1)策略空间在欧几里得空间中是非空的，有界的闭集；(2)效用函数在其策略空间上是连续的凹函数。

显然，任意用户 的带宽策略空间是在欧几里得空间中的有界闭集，同时，用户的效用函数在其策略空间上是连续的，下面证明效用函数为凹函数。首先，对任意用户效用函数求一阶偏导，得

(5)

对式(5)求二阶偏导数，得

(6)

显然，用户效用函数二阶导数<0，是严格的凹函数，所以用户间的博弈存在纳什均衡。

1.4 代理节点的效用函数

对于代理节点，其效用函数不仅要考虑出售带宽所带来的收益，而且需要考虑带宽成本和能耗成本，任意代理节点j效用函数可以表示为

(8)

Gj(pj,q)=(pj-c-ej)

(9)

2 算法过程描述

本文采用分布式迭代算法，使移动用户和代理节点达到均衡点。在任意K时刻，代理节点公布制定的价格策略后，移动用户通过一个简单的动态模型，来调节自身带宽策略。具体移动用户i的带宽变化策略可以描述为

(10)

其中，k为时间变量；αi为移动用户i调节带宽的步长。由于效用函数凹函数的特性，保证了迭代算法最终收敛到稳定的纳什均衡点。在K+1时刻，代理节点制定新一轮的定价，通过对式(9)求价格一阶导数，并令其为零，可以得到代理节点的最优价格策略。

3 仿真与分析

仿真考虑蜂窝网和自组织网络融合的架构下，在蜂窝网中有3个代理节点，代理节点的覆盖范围为500 m，在代理节点覆盖范围内随机分布了6个移动用户，用户通过多接入技术向代理节点申请带宽，其信息如表1所示，每个用户对不同代理节点的初始带宽策略均0。蜂窝网的总带宽B=25 Mbit·s-1，单位带宽成本 设为0.1。仿真中，移动用户调整带宽策略步进均为0.1，即α1=α2=…=0.1。代理节点单位带宽能耗分别为e1=0.03，e2=0.04，e3=0.02，单位nW/Mbit。

表1 用户参数

首先，对代理节点的出价策略进行分析，图2为代理节点的出价策略变化情况，从图中可以看出，随着博弈的进行，代理节点的价格策略不断变化，最终收敛到一个定值，即纳什均衡点。

图2 代理节点价格策略

图3给出代理节点在迭代过程中负载的变化情况。其中，代理节点单位带宽能耗越小，其吞吐量越大，反之，其吞吐量越小，这使得吞吐量在代理节点间得到均衡，避免了个别代理节点能量过早耗尽，而退出网络。

图3 代理节点吞吐量的变化

图4～图5显示的是用户满意度对比。本文定义用户满意度为用户所分配的带宽与该用户带宽需求量的比值。从图中可以看出，由于用户优先级、所处位置和带宽需求量不同，不同用户满意度不同。相比于不区分用户业务特性的算法，本算法根据用户业务各自的需求特性因地制宜地为每个用户分配带宽，提高了用户满意度。

图4 本算法用户满意度的变化

图5 对比算法用户满意度的变化

图6显示的是网络带宽利用率的对比。从图中可以看出，不区分用户业务特性的算法的总体带宽利用率不到75%，而本文所提算法的带宽利用率超过了80%，提高了网络总体的带宽利用率。

图6 网络带宽利用率对比

4 结束语

本文提出了一种基于Stackelberg 博弈的资源分配算法。该算法通过Stackelberg 模型，分析了不同优先级用户之间的博弈行为。代理节点在制定价格时，不仅考虑了用户的带宽需求，用户根据自身位置、优先级和带宽需求量，通过多接入技术，有选择地接入代理节点，调整带宽策略，满足自己的QoS需求。仿真结果表明，该算法不仅提高了用户性能，而且提高了系统带宽利用率，更符合对稀缺带宽资源有效有效利用的要求。

[1] Yang X, Feng G. Bandwidth reallocation for bandwidth asymmetry wireless networks based on distributed multiservice admission control[J]. IEEE Transactions on Mobile Computing, 2008, 7(7):1311-1324.

[2] Alnwaimi G, Arshad K, Moessner K. Dynamic spectrum allocation algorithm with interference management in Co-existing networks[J].IEEE Communications Letters, 2011, 15(9):932-934.

[3] Chandrasekhar V,Andrews J G,Muharemovic T,et al.Power control in two-tier femtocell networks[J].IEEE Transactions on Wireless Communications,2008,8(8):4316-4328.

[4] Chen Y P, Yang Y. A new 4G architecture providing multimode terminals always best connected services[J]. IEEE Wireless Communications, 2007, 14(2):36-41.

[5] Bari F, Leung V. Multi-attribute network selection by iterative TOPSIS for heterogeneous wireless access[C].Paris:Consumer Communications and Networking Conference, 2007.

[6] Bari F,Leung V. Application of electre to network selection in a hetereogeneous wireless network environment[C].Paris:Wireless Communications and Networking Conference, 2007.

[7] Sibanda C C L, Bagula A B. Network selection for mobile nodes in heterogeneous wireless networks using knapsack problem dynamic algorithms[C].Canada:Telecommunications Forum (TELFOR), 2012.

[8] Gelabert X, Perez-Romero J, Sallent O, et al. A markovian approach to radio access technology selection in heterogeneous multiaccess/multiservice wireless networks[J]. IEEE Transactions on Mobile Computing, 2008, 7(10):1257-1270.

[9] Vinicius D M R, De L G P R, De C M C. Use of fuzzy logic for networks selection in heterogeneous wireless environment[C].Germany:International Conference on Advanced Communication Technology, IEEE, 2012.

[10] Kher S, Somani A K, Gupta R. Network selection using fuzzy logic[C].Porland:2nd International Conference on Broadband Networks,IEEE, 2005.

[11] Niyato D,Hossain E. Radio resource management games in wireless networks: an approach to bandwidth allocation and admission control for polling service in IEEE 802.16[J].IEEE Wireless Communications, 2007,14(1): 27-35.

[12] Luan Z, Qu H, Zhao J. Using game theory for radio resource management of RRC layer in LTE-A[C].Pyeongchang, Korean:14th IEEE International Conference on Advanced Communication Technology,2012.

[13] Yaiche H, Mazumdar R R,Rosenberg C. A game theoretic framework for bandwidth allocation and pricing in broadband networks[J].IEEE/ACM Transactions on Networking, 2000,8(5): 667-678.

[14] Hong Y, Shen L, Xu B. Experimental system for integration of Ad-Hoc and cellular network[C].Beijing:Wireless Communications, Networking and Mobile Computing, 2009.

[15] 姜永，陈山枝，胡博.异构无线网络中基于Stackelberg 博弈的分布式定价和资源分配算法[J].通信学报,2013,34 (1) : 61-68．

[16] Fudenberg D,Tirole J.Game theory[M].Beijing: China Renmin University Press, 2002.

Resource Allocation Scheme Based on Stackelberg Game in Heterogeneous Networks

HU Xianfeng，ZHENG Lin

(School of Communication and Information,Guilin University of Electronic Technology, Guilin 541004,China)

In order to deal with the wireless resource allocation in heterogeneous wireless networks, this paper proposes a resource allocation scheme based Stackleberg game.In this scheme,the relay nodes generate the price strategy as leaders.In order to satisfy their own QoS, the users apply to multiple relay nodes for bandwidth resource simultaneously as followers.In this paper,we have proved the existence of the Nash equilibrium point of the non-cooperative game about the users.The simulation results show that the proposed resource allocation scheme can improve the total system bandwidth utilization and improve the users’ satisfaction degree for bandwidth.

heterogeneous networks；wireless resource allocation；Stackelberg game；multiple access

10.16180/j.cnki.issn1007-7820.2016.12.019

2016- 03- 01

国家自然科学基金资助项目(61362006)；广西无线宽带通信与信号处理重点实验室课题资助项目(GXKL061501)

郑霖(1974-)，男，博士，教授。研究方向：超宽带通信等。胡弦锋(1989-)，男，硕士研究生。研究方向：异构网络融合与网络优化。

TN926

A

1007-7820(2016)12-065-04