无线网络虚拟化中资源共享的功率分配算法

2016-07-18曹傧郎文强陈卓李云

通信学报 2016年2期

关键词：传输速率时隙网络资源

曹傧，郎文强，陈卓，李云

(1.重庆邮电大学移动通信技术重庆市重点实验室，重庆400065；2.重庆理工大学计算机科学与工程学院，重庆400054)

无线网络虚拟化中资源共享的功率分配算法

曹傧1，郎文强1，陈卓2，李云1

(1.重庆邮电大学移动通信技术重庆市重点实验室，重庆400065；2.重庆理工大学计算机科学与工程学院，重庆400054)

针对传统无线网络中功率不能动态分配共享的问题，采用无线网络虚拟化，设计了一种基于博弈的两阶段功率分配方法(G2SPA,game theory based two steps power allocation scheme for wireless network virtualization)，首先利用买卖博弈模拟了服务提供商(SP,service provide)和移动用户(MUE,mobile user equipment)之间的相互影响，提出了基于斯坦博格均衡(SE,stackelberg equilibrium)的报价策略。然后，利用拍卖理论对空闲下行功率资源进行再分配，采取McAfee机制保证拍卖的诚实性。通过仿真实验证明G2SPA算法的正确性和有效性。

无线网络虚拟化；资源共享；功率分配；博弈论

1 引言

为了更好地为移动用户(MUE,mobile user equipment)提供服务，在同一区域内不同的服务提供商(SP,service provide)往往会部署各自的无线接入点(AP,access point)。然而，这种部署缺乏统一调度和管理，难以灵活高效共享、分配有限的网络资源，从而不同AP间极易出现负载不均衡的情况，导致资源利用率低。网络资源的共建共享能够减少基础设施的重复建设和维护成本，但是，如何合理、高效、公平地分配网络资源一直是亟待解决的重要问题。

最近，无线网络虚拟化作为一种新型的网络体系结构出现在人们的视野中，能够提供各种QoS保证和高效的网络资源分配[1]，得到越来越多的关注。为了提高无线网络虚拟化环境下的网络资源利用率，Belt等[2]设计了一个动态嵌入式贪婪算法来进行物理资源的分配。为了有效地分配无线资源，Yang等[3]提出了一种卡诺图式的在线嵌入式算法。Fu等[4]提出了将网络虚拟化结构划分为SP和网络操作方(NO,network operator)，SP和NO之间的相互影响看作是斯坦博格博弈，通过证明推测价格中存在纳什均衡，使SP提供真实的效用函数，从而有效地进行资源分配。Lv等[5]提出了基于VCG(vickreyclarke-grove)的资源分配机制，该机制通过抑制SP自私性，达到最大化SP的总收益，同时设计了Q学习竞价选择算法，使SP获得最优的竞价策略。Yun等[6]在无线多跳网络中提出了一种新的嵌入式算法，有效地利用物理层资源(例如CPU和带宽)。

传统无线网络中，功率分配一直是一个十分重要的问题[7～9]。然而，目前关于无线网络虚拟化中的资源分配算法研究大部分集中在带宽和CPU的分配，而对于功率资源分配还没有引起足够的重视，其主要原因在于功率资源不能在物理节点(如AP)之间共享。但是，利用无线网络虚拟化，多个SP可以共存于同一AP共享网络资源。因此，如何根据MUE的需求，将AP的下行功率合理高效地分配给各个SP，是一个重要但尚未得到充分研究的内容，这正是本文的出发点。

文献[10]利用买卖博弈，在协作通信中的中继节点上进行功率分配。文献[11]利用拍卖的方法，设计了认知无线电中频谱的分配方法。文献[12]推导基于纳什均衡的价格，在此基础上提高了无线网络虚拟化的分配效率。鉴于博弈论作为一种平衡各方利益制定策略的有效工具，在无线网络资源分配中被广泛采用，本文将博弈论作为解决问题的手段，设计了一种基于博弈的两阶段功率分配方法。

本文主要贡献为通过无线网络虚拟化，将多个SP共存于同一AP共享网络资源，提出了一种针对无线网络虚拟化环境下的功率分配算法G2SPA，该算法能够最大化SP和MUE的收益，对不同负载SP的功率资源进行调度，实现资源共享。

2 系统模型

参考文献[12]，本文采用的无线网络虚拟化架构如图1所示。在虚拟化环境下，多个SP共存于同一个物理AP上，为各自的MUE提供服务。不同的虚拟AP服务不同的SP，而在实际情景中只有一个物理AP连接所有的MUE。SP负责MUE的接入，分配下行功率。NO负责管理无线接入，获取信道状态、SP和用户的身份信息，根据一定规则(如投入、股份)给各个虚拟AP初始分配下行功率，并根据SP总的资源需求通过拍卖进行资源再分配。本文根据上述模型，考虑如何在单一的物理接入点上对所有SP和用户进行有效的下行功率分配和资源共享。

图1 无线网络虚拟化框架

不失一般性，假设网络中共有n个SP和m个MUE，定义第i个SP为Si，Si连接第j个MUE用 Mij表示。Si下有mi个MUE，那么向Si请求下行功率，假设信道为高斯加性白噪声信道，则Mij的传输速率为

显然，每一个Mij都想获得更高传输速率。一般地，近似认为传输距离和信道状态在一个时隙或一次传输中保持不变，因此，下行功率就成为对传输速率最主要的影响因素。

本文提出了买卖报价方案来解决第1个问题和第2个问题，然后根据各个SP的功率总需求，NO执行拍卖，在超负载与轻负载的SP之间进行功率资源的再分配，从而解决第3个问题。

3 买卖博弈和拍卖博弈的分析

本文提出基于博弈的功率分配方法分为2个阶段。首先，Si与Mij进行协商，确定最优下行功率及其代价。接下来，Si根据负载情况，通过NO购买或出售功率资源。下面分别介绍第1阶段Si和 Mij之间的买卖博弈(G1)和由NO执行SP之间的第2阶段功率拍卖(G2)。

3.1 买卖博弈

3.1.1 MUE(买方)的分析

定义Mij为买方(bij)，Si为卖方(si)，bij的收益为

其中，ijβ表示单位传输速率的增益，。

得到si向bij分配的最优下行功率为

3.1.2 SP(卖方)的分析

由于每个si里往往有多个Mij，那么在G1的过程中，si的总收益为

需要注意的是，Si和Mij之间是典型的非合作博弈，它们不关心其他MUE从SP获得多少下行功率以及价格，每个Mij只根据自己的信道状态和单位下行功率价格，为自己请求最优，如式(6)所示。在G1过程中，为了最大化满足MUE对功率的需求，Si暂不考虑功率约束。在G2里，Si再根据自己的负载情况，通过拍卖博弈，购买或出售功率资源。

令式(8)等于0，得到si向bij最优单位功率价格为

3.1.3 斯坦博格均衡的存在性

实际情景下，SP为了吸引MUE参与买卖博弈，会从最低的价格（即单位下行功率成本），开始逐渐增加价格，直到收益不再增加为止，此时对应的价格则是最优单位下行功率价格。当确定后，根据式(6)，即可得到最优。接下来，本文将构建一个简单的价格更新函数来证明单位下行传输功率价格的收敛性，以快速准确地制定报价策略。

3.1.4 价格更新函数

SP通过将单位下行功率价格从成本逐渐增加到最优价格，使其收益最大，这意味着将从正数变为0，因此可以设计一个价格更新函数，每执行一次，价格就更新一次，直至收敛发生就停止。那么

进一步描述为

根据文献[8]，得知对于所有α≥0，I()α满足下面的特性。

1)正数：I(α)＞0；

2)单调性：当α≥α'，则I(α)≥I(α')；

3)可扩展性：对于e＞1，eI(α)≥I(eα )。

买卖博弈(G1)如算法2所示（见附录B）。在此算法中，首先每个SP通过价格更新函数，求得最优单位下行功率的价格，然后根据，计算SP分配给每个MUE的最优下行功率。

3.2 拍卖博弈

在G1阶段，根据买卖博弈，MUE与SP协商，从而确定最优的下行功率及其单价。但是G1阶段，SP没有考虑功率限制，因此总的功率需求可能会超出初始分配功率，无法完全满足用户需求，这种情况定义为SP超负载。另一方面，如果SP初始分配功率大于总的功率需求，有剩余的功率，定义为轻负载。

为了提高功率资源利用率，平衡SP的负载情况，在G2阶段，NO执行基于McAfee的拍卖机制，对SP的功率资源进行再分配。根据McAfee机制，每个SP必须向NO提供真实的效用函数才能保证自身的收益最优。

SP在经历过G1、G2阶段后总收益Usi如下。

超负载的SP

轻负载的SP

拍卖博弈如算法3所示（见附录C）。算法3的输入是基于算法2的输出，此算法中，首先确定拍卖双方，然后执行基于McAfee的拍卖机制，最后输出分配结果。其中，n表示SP的个数，I表示买方SP的个数，J表示卖方SP的个数。Θ是G2阶段功率资源分配的结果，也就是G2SPA算法的最终结果。

4 性能评估

为了评估提出的G2SPA算法的正确性和有效性，本文对功率分配、单位功率价格、网络中每个用户的平均传输速率和功率资源利用率进行仿真验证和性能评估。

实验场景图2为一个二维空间，表示实验中节点的位置和移动情况，其中X轴表示水平方向，Y轴表示竖直方向，物理AP位于原点处，2个SP（S1和S2）共存其上。每个SP有且只有一个MUE，分别为M11和M21。假设W、φ均为1，σ2=10-4， k=2。初始分配功率分别为2.0、1.5。物理AP的位置定为(0,0)。仿真由3组实验构成，实验1验证单位功率价格的收敛性，实验2模拟G1阶段最优功率和最优功率价格的变化以及在G2阶段的成交情况，实验3则进行网络性能的评估。

图2 实验场景

在实验1中，固定M11、M21的位置，M11的坐标为(0，50)；M21的坐标为(−70，0)。单位下行功率价格的收敛如图3所示。可以看到，报价均从成本开始逐渐提高，这是因为只有如此才能保证买卖可以进行，从而保证博弈的有效性。当为0.1， β为0.9时，从成本0.1开始逐渐升高，经过10次迭代后，稳定在0.72处；而为0.1，β为 0.5时，经过5次迭代后，稳定在0.51处。由此可见，经过一定次数的迭代后，报价将很快稳定不再变化，即最优报价。同样地，当为0.5，β为0.9时，稳定在1.19处；而为0.5，β为 0.5时，则稳定在0.83处。另外，实验数据也完全符合理论分析和预期，证明了该方法的正确、有效。

在实验2中，M11和M21在第0个时隙时分别位于(0,50)，(−100,0)。β11=0.9，β21=0.5，单位下行功率成本每经过一个时隙，M11横坐标x不变，纵坐标y增加1，而M21纵坐标y不变，横坐标x增加1。假设总共经过30个时隙。

图3 单位功率价格的收敛

M11最优功率需求如图4(a)所示，可以看出S1分配M11的下行功率随时间的变化逐渐增大，因为M11是远离S1移动的，随着距离增大，所需功率也会增加。同时，如图4(b)所示，单位功率价格是随距离的增大而减小。因为价格越低，越能促使M11购买更多的功率从而提高S1的收益。同样，图4(c)和图4(d)分别表示S2分配M21的下行功率和单位功率价格。M21是向着S2移动的，随着距离的减小，所需下行功率逐渐减小，单位功率价格逐渐增加。上述结果验证了本文在第3部分的理论分析。

图5表示S1和S2在G2中的成交价，可以看出整个过程分为3个阶段。第1个阶段，从第0到第10个时隙，此阶段的成交价为正，S2作为买方，S1作为卖方。因为此时S2初始分配功率不能满足M21的功率需求，需要购买额外的功率，而S1则可以出售功率资源。第2个阶段，当时隙从第11到第18个时隙，由于S1和S2的功率都没有超出自己初始分配到的功率，不需要额外的功率支持，所以这一过程没有交易，成交价为0。第3个阶段，当从第19时隙到第30时隙，此阶段的成交价为负，S1作为买方，S2作为卖方。因为M11逐渐远离AP，M21逐渐靠近AP，S1初始分配功率不能满足M11的功率需求，而S2可以向S1提供功率资源。

本文在无线网络虚拟化中，采用博弈方法共享网络资源，并根据实际需求和变化再分配资源。而目前的研究[13,14]，虽然利用博弈方法进行资源分配，但仅仅只关注MUE对资源的需求，以及如何合理地将网络资源分配给SP，并没有考虑利用网络虚拟化的优势共享网络资源，特别是对网络资源的再分配。为了体现G2SPA算法的优越性，将实验3和采用博弈方法且只关注MUE对功率需求的算法[14]相比较，评估验证G2SPA的网络性能和有效性。

图4 最优功率需求及最优功率价格

图5 S1和S2之间的成交价格p12

实验3设置了5个SP（S1, S2,S3, S4,S5），初始分配功率分别为5.0、2.0、1.0、1.0、1.0。单位下行功率成本均为0.50。每个MUE随机接入断开，初始位置随机，MUE随机移动，假设经过100个时隙。因为执行一次随机实验不具有代表性，所以执行实验3的100次取平均值。图6给出采用文献[14]的算法和采用G2SPA算法的网络传输速率。可以看出，相比文献[14]的算法，执行G2SPA算法每个用户的平均传输速率大约提升了50%，在第55个时隙达到了55%，这是因为当网络中出现负载不均衡时，G2SPA算法通过采用拍卖机制进行资源的再分配，使轻负载的SP能够向超负载SP提供多余功率，从而满足MUE的需求，提高了整体网络传输速率。

图7表示功率资源利用率的对比，可以看出，G2SPA算法要优于文献[14]的算法，执行G2SPA算法功率资源利用率最高达到了88%。同样是因为当不同SP之间出现负载不均衡时，G2SPA算法使不同负载SP之间进行功率资源的调度，极大提高了功率资源利用率。

图6 网络平均传输速率

图7 功率资源利用率

5 结束语

本文提出了一种在无线网络虚拟化环境下的功率分配算法G2SPA，有效地解决了多SP如何动态共享物理AP资源的问题。通过G2SPA算法，确定了SP与MUE之间所需功率和单位下行功率价格，同时解决了在不同负载SP之间进行功率资源的再分配问题。本文利用博弈寻求SP和MUE的最优策略，达到斯坦博格均衡，实现利益最大化。接下来，NO根据各个SP的功率需求，利用拍卖理论在负载不同的SP之间进行资源的调度，从而提高功率资源的利用率。最后，通过大量仿真实验，证明了功率分配算法G2SPA的正确性和有效性。

附录A 算法1：价格更新函数

附录B 算法2：买卖博弈

附录C 算法3：拍卖博弈

[1]WANG X,KRISHNAMURTHY P,TIPPER D,et al.Wireless network virtualization[C]//2013InternationalConferenceonComputing, NetworkingandCommunications(ICNC).SanDiego,c2013: 818-822.

[2]BELT J,AHMADI H,DOYLE L E,et al.A dynamic embedding algorithm for wireless network virtualization[C]//2014 IEEE 80th Vehicular Technology Conference(VTC2014).c2014:1-6.

[3]YANG M,LI Y,ZENG L G,et al.Karnaugh-map like online embeddingalgorithmofwirelessvirtualization[C]//201215th InternationalSymposiumonWirelessPersonalMultimedia Communication(WPMC).c2012:594-598.

[4]FU F,KOZAT U C.Wireless network virtualization as a sequential auctiongame[C]//InternationalConferenceonComputer Communications(INFOCOM).San Diego,c2010:1-9.

[5]LV X,XIONG A,ZHANG S L,QIU X S.VCG-based bandwidth allocationschemefornetworkvirtualization[C]//2012IEEE Symposium on Computer and Communications(ISCC).Cappadocia, c2012:744-749.

[6]YUN D Y,OK J,SHIN B,et al.Embedding of virtual network requestsoverstaticwirelessmultihopnetworks[J].Computer Networks,2013,57(5):1139-1152.

[7]LI C G,SUN F,JOHN M,CIOFFI,et al.Energy efficient MIMO relay transmissions via joint power allocations[J].IEEE Transactions on Circuits and Systems-II,2014,61(7):531-535.

[8]LI C G,WANG X,YANG L X,et al.A joint source and relay power allocation scheme for a class of MIMO relay systems[J].IEEE Transactions on Signal Processing,2009,57(12):4852-4860.

[9]LI C G,YANG H J,SUN F,et al.Approximate closed-form energy efficient PA for MIMO relaying systems in the high SNR regime[J].IEEE Communications Letters,2014,18(8):1367-1370.

[10]WANG B B,HAN Z,LIU K J R.Distributed relay selection and power control for multiuser cooperative communication networks using stackelberg game[J].IEEE Transactions on Mobile Computing, 2009,8(7):975-990.

[11]SENGUPTA S,CHATTERJEE M.Designing auction mechanisms for dynamic spectrum access[J].Mobile Network and Applications,2008, 13(5):498-515.

[12]FUF,KOZATUC.Stochasticgameforwirelessnetwork virtualization[J].IEEE/ACM Transactions on Networking,2013, 21(1):79-84.

[13]ZHAO JH,WANG J,GONG Y.Joint power and rate control using gametheoryinheterogeneousnetwork[C]//2013International ConferenceonWirelessCommunicationandSignal Processing(WCSP).Hangzhou,China,c2013:1-5.

[14]LI P,ZHU Y.Price-based power control of femtocell networks:a Stackelberggameapproach[C]//2012IEEE23rdInternational Symposium on Personal Indoor and Mobile Radio Communications (PIMRC).Sydney,c2012:1185-1191.

Power allocation in wireless network virtualization based on resource sharing

CAO Bin1,LANG Wen-qiang1,CHEN Zhuo2,LI Yun1
(1.Chongqing Key Lab of Mobile Communications Technology,Chongqing University of Post and Communications,Chongqing 400065,China; 2.College of Computer Science Engineering,Chongqing University of Technology,Chongqing 400054,China)

In traditional wireless network,resource couldn’t be efficiently and flexibly.To this end,wireless network virtualization was used to manage and share resource.A game theory based two steps power allocation scheme for wireless network virtualization,called G2SPA,was proposed,which designed a stackelberg equilibrium(SE)price strategy based on the interactions between SP and mobile user equipment(MUE),and then MacAfee based auction to reallocate leisure resource was performed.The numerous experimental simulation results show that the rightness and effectiveness of G2SPA.

wireless network virtualization,resource sharing,power allocation,game theory

TN929.5

10.11959/j.issn.1000-436x.2016031

2015-03-10；

2015-05-25

长江学者和创新团队发展计划基金资助项目(No.IRT1299)；重庆市基础与前沿研究计划基金资助项目(No.cstc2015jcyjA40048)；重庆邮电大学青年科学研究基金资助项目(No.A2014-94)；重庆市教委科学技术研究基金资助项目(No.KJ1500406,No.KJ1400918,No.KJ1500408)

Program for Changjiang Scholars and Innovative Research Team in University(No.IRT1299),Basic and Advanced Research Projects of Chongqing(No.cstc2015jcyjA40048),The Science Research Project of Chongqing University of Posts and Telecommunications for Young Scholars(No.A2014-94),The Science and Technology Research Project of Chongqing Municipal Education Commission of China(No.KJ1500406,No.KJ1400918,No.KJ1500408)