無線網(wǎng)絡(luò)虛擬化中資源共享的功率分配算法

曹儐，郎文強，陳卓，李云

(1.重慶郵電大學(xué)移動通信技術(shù)重慶市重點實驗室，重慶400065；2.重慶理工大學(xué)計算機科學(xué)與工程學(xué)院，重慶400054)

?

無線網(wǎng)絡(luò)虛擬化中資源共享的功率分配算法

曹儐1，郎文強1，陳卓2，李云1

(1.重慶郵電大學(xué)移動通信技術(shù)重慶市重點實驗室，重慶400065；2.重慶理工大學(xué)計算機科學(xué)與工程學(xué)院，重慶400054)

針對傳統(tǒng)無線網(wǎng)絡(luò)中功率不能動態(tài)分配共享的問題，采用無線網(wǎng)絡(luò)虛擬化，設(shè)計了一種基于博弈的兩階段功率分配方法(G2SPA,game theory based two steps power allocation scheme for wireless network virtualization)，首先利用買賣博弈模擬了服務(wù)提供商(SP,service provide)和移動用戶(MUE,mobile user equipment)之間的相互影響，提出了基于斯坦博格均衡(SE,stackelberg equilibrium)的報價策略。然后，利用拍賣理論對空閑下行功率資源進(jìn)行再分配，采取McAfee機制保證拍賣的誠實性。通過仿真實驗證明G2SPA算法的正確性和有效性。

無線網(wǎng)絡(luò)虛擬化；資源共享；功率分配；博弈論

1 引言

為了更好地為移動用戶(MUE,mobile user equipment)提供服務(wù)，在同一區(qū)域內(nèi)不同的服務(wù)提供商(SP,service provide)往往會部署各自的無線接入點(AP,access point)。然而，這種部署缺乏統(tǒng)一調(diào)度和管理，難以靈活高效共享、分配有限的網(wǎng)絡(luò)資源，從而不同AP間極易出現(xiàn)負(fù)載不均衡的情況，導(dǎo)致資源利用率低。網(wǎng)絡(luò)資源的共建共享能夠減少基礎(chǔ)設(shè)施的重復(fù)建設(shè)和維護(hù)成本，但是，如何合理、高效、公平地分配網(wǎng)絡(luò)資源一直是亟待解決的重要問題。

最近，無線網(wǎng)絡(luò)虛擬化作為一種新型的網(wǎng)絡(luò)體系結(jié)構(gòu)出現(xiàn)在人們的視野中，能夠提供各種QoS保證和高效的網(wǎng)絡(luò)資源分配[1]，得到越來越多的關(guān)注。為了提高無線網(wǎng)絡(luò)虛擬化環(huán)境下的網(wǎng)絡(luò)資源利用率，Belt等[2]設(shè)計了一個動態(tài)嵌入式貪婪算法來進(jìn)行物理資源的分配。為了有效地分配無線資源，Yang等[3]提出了一種卡諾圖式的在線嵌入式算法。Fu等[4]提出了將網(wǎng)絡(luò)虛擬化結(jié)構(gòu)劃分為SP和網(wǎng)絡(luò)操作方(NO,network operator)，SP和NO之間的相互影響看作是斯坦博格博弈，通過證明推測價格中存在納什均衡，使SP提供真實的效用函數(shù)，從而有效地進(jìn)行資源分配。Lv等[5]提出了基于VCG(vickreyclarke-grove)的資源分配機制，該機制通過抑制SP自私性，達(dá)到最大化SP的總收益，同時設(shè)計了Q學(xué)習(xí)競價選擇算法，使SP獲得最優(yōu)的競價策略。Yun等[6]在無線多跳網(wǎng)絡(luò)中提出了一種新的嵌入式算法，有效地利用物理層資源(例如CPU和帶寬)。

傳統(tǒng)無線網(wǎng)絡(luò)中，功率分配一直是一個十分重要的問題[7～9]。然而，目前關(guān)于無線網(wǎng)絡(luò)虛擬化中的資源分配算法研究大部分集中在帶寬和CPU的分配，而對于功率資源分配還沒有引起足夠的重視，其主要原因在于功率資源不能在物理節(jié)點(如AP)之間共享。但是，利用無線網(wǎng)絡(luò)虛擬化，多個SP可以共存于同一AP共享網(wǎng)絡(luò)資源。因此，如何根據(jù)MUE的需求，將AP的下行功率合理高效地分配給各個SP，是一個重要但尚未得到充分研究的內(nèi)容，這正是本文的出發(fā)點。

文獻(xiàn)[10]利用買賣博弈，在協(xié)作通信中的中繼節(jié)點上進(jìn)行功率分配。文獻(xiàn)[11]利用拍賣的方法，設(shè)計了認(rèn)知無線電中頻譜的分配方法。文獻(xiàn)[12]推導(dǎo)基于納什均衡的價格，在此基礎(chǔ)上提高了無線網(wǎng)絡(luò)虛擬化的分配效率。鑒于博弈論作為一種平衡各方利益制定策略的有效工具，在無線網(wǎng)絡(luò)資源分配中被廣泛采用，本文將博弈論作為解決問題的手段，設(shè)計了一種基于博弈的兩階段功率分配方法。

本文主要貢獻(xiàn)為通過無線網(wǎng)絡(luò)虛擬化，將多個SP共存于同一AP共享網(wǎng)絡(luò)資源，提出了一種針對無線網(wǎng)絡(luò)虛擬化環(huán)境下的功率分配算法G2SPA，該算法能夠最大化SP和MUE的收益，對不同負(fù)載SP的功率資源進(jìn)行調(diào)度，實現(xiàn)資源共享。

2 系統(tǒng)模型

參考文獻(xiàn)[12]，本文采用的無線網(wǎng)絡(luò)虛擬化架構(gòu)如圖1所示。在虛擬化環(huán)境下，多個SP共存于同一個物理AP上，為各自的MUE提供服務(wù)。不同的虛擬AP服務(wù)不同的SP，而在實際情景中只有一個物理AP連接所有的MUE。SP負(fù)責(zé)MUE的接入，分配下行功率。NO負(fù)責(zé)管理無線接入，獲取信道狀態(tài)、SP和用戶的身份信息，根據(jù)一定規(guī)則(如投入、股份)給各個虛擬AP初始分配下行功率，并根據(jù)SP總的資源需求通過拍賣進(jìn)行資源再分配。本文根據(jù)上述模型，考慮如何在單一的物理接入點上對所有SP和用戶進(jìn)行有效的下行功率分配和資源共享。

圖1 無線網(wǎng)絡(luò)虛擬化框架

不失一般性，假設(shè)網(wǎng)絡(luò)中共有n個SP和m個MUE，定義第i個SP為Si，Si連接第j個MUE用 Mij表示。Si下有mi個MUE，那么向Si請求下行功率，假設(shè)信道為高斯加性白噪聲信道，則Mij的傳輸速率為

顯然，每一個Mij都想獲得更高傳輸速率。一般地，近似認(rèn)為傳輸距離和信道狀態(tài)在一個時隙或一次傳輸中保持不變，因此，下行功率就成為對傳輸速率最主要的影響因素。

本文提出了買賣報價方案來解決第1個問題和第2個問題，然后根據(jù)各個SP的功率總需求，NO執(zhí)行拍賣，在超負(fù)載與輕負(fù)載的SP之間進(jìn)行功率資源的再分配，從而解決第3個問題。

3 買賣博弈和拍賣博弈的分析

本文提出基于博弈的功率分配方法分為2個階段。首先，Si與Mij進(jìn)行協(xié)商，確定最優(yōu)下行功率及其代價。接下來，Si根據(jù)負(fù)載情況，通過NO購買或出售功率資源。下面分別介紹第1階段Si和 Mij之間的買賣博弈(G1)和由NO執(zhí)行SP之間的第2階段功率拍賣(G2)。

3.1 買賣博弈

3.1.1 MUE(買方)的分析

定義Mij為買方(bij)，Si為賣方(si)，bij的收益為

其中，ijβ表示單位傳輸速率的增益，。

得到si向bij分配的最優(yōu)下行功率為

3.1.2 SP(賣方)的分析

由于每個si里往往有多個Mij，那么在G1的過程中，si的總收益為

需要注意的是，Si和Mij之間是典型的非合作博弈，它們不關(guān)心其他MUE從SP獲得多少下行功率以及價格，每個Mij只根據(jù)自己的信道狀態(tài)和單位下行功率價格，為自己請求最優(yōu)，如式(6)所示。在G1過程中，為了最大化滿足MUE對功率的需求，Si暫不考慮功率約束。在G2里，Si再根據(jù)自己的負(fù)載情況，通過拍賣博弈，購買或出售功率資源。

令式(8)等于0，得到si向bij最優(yōu)單位功率價格為

3.1.3 斯坦博格均衡的存在性

實際情景下，SP為了吸引MUE參與買賣博弈，會從最低的價格（即單位下行功率成本），開始逐漸增加價格，直到收益不再增加為止，此時對應(yīng)的價格則是最優(yōu)單位下行功率價格。當(dāng)確定后，根據(jù)式(6)，即可得到最優(yōu)。接下來，本文將構(gòu)建一個簡單的價格更新函數(shù)來證明單位下行傳輸功率價格的收斂性，以快速準(zhǔn)確地制定報價策略。

3.1.4 價格更新函數(shù)

SP通過將單位下行功率價格從成本逐漸增加到最優(yōu)價格，使其收益最大，這意味著將從正數(shù)變?yōu)?，因此可以設(shè)計一個價格更新函數(shù)，每執(zhí)行一次，價格就更新一次，直至收斂發(fā)生就停止。那么

進(jìn)一步描述為

根據(jù)文獻(xiàn)[8]，得知對于所有α≥0，I()α滿足下面的特性。

1)正數(shù)：I(α)＞0；

2)單調(diào)性：當(dāng)α≥α'，則I(α)≥I(α')；

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

買賣博弈(G1)如算法2所示（見附錄B）。在此算法中，首先每個SP通過價格更新函數(shù)，求得最優(yōu)單位下行功率的價格，然后根據(jù)，計算SP分配給每個MUE的最優(yōu)下行功率。

3.2 拍賣博弈

在G1階段，根據(jù)買賣博弈，MUE與SP協(xié)商，從而確定最優(yōu)的下行功率及其單價。但是G1階段，SP沒有考慮功率限制，因此總的功率需求可能會超出初始分配功率，無法完全滿足用戶需求，這種情況定義為SP超負(fù)載。另一方面，如果SP初始分配功率大于總的功率需求，有剩余的功率，定義為輕負(fù)載。

為了提高功率資源利用率，平衡SP的負(fù)載情況，在G2階段，NO執(zhí)行基于McAfee的拍賣機制，對SP的功率資源進(jìn)行再分配。根據(jù)McAfee機制，每個SP必須向NO提供真實的效用函數(shù)才能保證自身的收益最優(yōu)。

SP在經(jīng)歷過G1、G2階段后總收益Usi如下。

超負(fù)載的SP

輕負(fù)載的SP

拍賣博弈如算法3所示（見附錄C）。算法3的輸入是基于算法2的輸出，此算法中，首先確定拍賣雙方，然后執(zhí)行基于McAfee的拍賣機制，最后輸出分配結(jié)果。其中，n表示SP的個數(shù)，I表示買方SP的個數(shù)，J表示賣方SP的個數(shù)。Θ是G2階段功率資源分配的結(jié)果，也就是G2SPA算法的最終結(jié)果。

4 性能評估

為了評估提出的G2SPA算法的正確性和有效性，本文對功率分配、單位功率價格、網(wǎng)絡(luò)中每個用戶的平均傳輸速率和功率資源利用率進(jìn)行仿真驗證和性能評估。

實驗場景圖2為一個二維空間，表示實驗中節(jié)點的位置和移動情況，其中X軸表示水平方向，Y軸表示豎直方向，物理AP位于原點處，2個SP（S1和S2）共存其上。每個SP有且只有一個MUE，分別為M11和M21。假設(shè)W、φ均為1，σ2=10-4， k=2。初始分配功率分別為2.0、1.5。物理AP的位置定為(0,0)。仿真由3組實驗構(gòu)成，實驗1驗證單位功率價格的收斂性，實驗2模擬G1階段最優(yōu)功率和最優(yōu)功率價格的變化以及在G2階段的成交情況，實驗3則進(jìn)行網(wǎng)絡(luò)性能的評估。

圖2 實驗場景

在實驗1中，固定M11、M21的位置，M11的坐標(biāo)為(0，50)；M21的坐標(biāo)為(?70，0)。單位下行功率價格的收斂如圖3所示?？梢钥吹剑瑘髢r均從成本開始逐漸提高，這是因為只有如此才能保證買賣可以進(jìn)行，從而保證博弈的有效性。當(dāng)為0.1， β為0.9時，從成本0.1開始逐漸升高，經(jīng)過10次迭代后，穩(wěn)定在0.72處；而為0.1，β為 0.5時，經(jīng)過5次迭代后，穩(wěn)定在0.51處。由此可見，經(jīng)過一定次數(shù)的迭代后，報價將很快穩(wěn)定不再變化，即最優(yōu)報價。同樣地，當(dāng)為0.5，β為0.9時，穩(wěn)定在1.19處；而為0.5，β為 0.5時，則穩(wěn)定在0.83處。另外，實驗數(shù)據(jù)也完全符合理論分析和預(yù)期，證明了該方法的正確、有效。

在實驗2中，M11和M21在第0個時隙時分別位于(0,50)，(?100,0)。β11=0.9，β21=0.5，單位下行功率成本每經(jīng)過一個時隙，M11橫坐標(biāo)x不變，縱坐標(biāo)y增加1，而M21縱坐標(biāo)y不變，橫坐標(biāo)x增加1。假設(shè)總共經(jīng)過30個時隙。

圖3 單位功率價格的收斂

M11最優(yōu)功率需求如圖4(a)所示，可以看出S1分配M11的下行功率隨時間的變化逐漸增大，因為M11是遠(yuǎn)離S1移動的，隨著距離增大，所需功率也會增加。同時，如圖4(b)所示，單位功率價格是隨距離的增大而減小。因為價格越低，越能促使M11購買更多的功率從而提高S1的收益。同樣，圖4(c)和圖4(d)分別表示S2分配M21的下行功率和單位功率價格。M21是向著S2移動的，隨著距離的減小，所需下行功率逐漸減小，單位功率價格逐漸增加。上述結(jié)果驗證了本文在第3部分的理論分析。

圖5表示S1和S2在G2中的成交價，可以看出整個過程分為3個階段。第1個階段，從第0到第10個時隙，此階段的成交價為正，S2作為買方，S1作為賣方。因為此時S2初始分配功率不能滿足M21的功率需求，需要購買額外的功率，而S1則可以出售功率資源。第2個階段，當(dāng)時隙從第11到第18個時隙，由于S1和S2的功率都沒有超出自己初始分配到的功率，不需要額外的功率支持，所以這一過程沒有交易，成交價為0。第3個階段，當(dāng)從第19時隙到第30時隙，此階段的成交價為負(fù)，S1作為買方，S2作為賣方。因為M11逐漸遠(yuǎn)離AP，M21逐漸靠近AP，S1初始分配功率不能滿足M11的功率需求，而S2可以向S1提供功率資源。

本文在無線網(wǎng)絡(luò)虛擬化中，采用博弈方法共享網(wǎng)絡(luò)資源，并根據(jù)實際需求和變化再分配資源。而目前的研究[13,14]，雖然利用博弈方法進(jìn)行資源分配，但僅僅只關(guān)注MUE對資源的需求，以及如何合理地將網(wǎng)絡(luò)資源分配給SP，并沒有考慮利用網(wǎng)絡(luò)虛擬化的優(yōu)勢共享網(wǎng)絡(luò)資源，特別是對網(wǎng)絡(luò)資源的再分配。為了體現(xiàn)G2SPA算法的優(yōu)越性，將實驗3和采用博弈方法且只關(guān)注MUE對功率需求的算法[14]相比較，評估驗證G2SPA的網(wǎng)絡(luò)性能和有效性。

圖4 最優(yōu)功率需求及最優(yōu)功率價格

圖5 S1和S2之間的成交價格p12

實驗3設(shè)置了5個SP（S1, S2,S3, S4,S5），初始分配功率分別為5.0、2.0、1.0、1.0、1.0。單位下行功率成本均為0.50。每個MUE隨機接入斷開，初始位置隨機，MUE隨機移動，假設(shè)經(jīng)過100個時隙。因為執(zhí)行一次隨機實驗不具有代表性，所以執(zhí)行實驗3的100次取平均值。圖6給出采用文獻(xiàn)[14]的算法和采用G2SPA算法的網(wǎng)絡(luò)傳輸速率?？梢钥闯?，相比文獻(xiàn)[14]的算法，執(zhí)行G2SPA算法每個用戶的平均傳輸速率大約提升了50%，在第55個時隙達(dá)到了55%，這是因為當(dāng)網(wǎng)絡(luò)中出現(xiàn)負(fù)載不均衡時，G2SPA算法通過采用拍賣機制進(jìn)行資源的再分配，使輕負(fù)載的SP能夠向超負(fù)載SP提供多余功率，從而滿足MUE的需求，提高了整體網(wǎng)絡(luò)傳輸速率。

圖7表示功率資源利用率的對比，可以看出，G2SPA算法要優(yōu)于文獻(xiàn)[14]的算法，執(zhí)行G2SPA算法功率資源利用率最高達(dá)到了88%。同樣是因為當(dāng)不同SP之間出現(xiàn)負(fù)載不均衡時，G2SPA算法使不同負(fù)載SP之間進(jìn)行功率資源的調(diào)度，極大提高了功率資源利用率。

圖6 網(wǎng)絡(luò)平均傳輸速率

圖7 功率資源利用率

5 結(jié)束語

本文提出了一種在無線網(wǎng)絡(luò)虛擬化環(huán)境下的功率分配算法G2SPA，有效地解決了多SP如何動態(tài)共享物理AP資源的問題。通過G2SPA算法，確定了SP與MUE之間所需功率和單位下行功率價格，同時解決了在不同負(fù)載SP之間進(jìn)行功率資源的再分配問題。本文利用博弈尋求SP和MUE的最優(yōu)策略，達(dá)到斯坦博格均衡，實現(xiàn)利益最大化。接下來，NO根據(jù)各個SP的功率需求，利用拍賣理論在負(fù)載不同的SP之間進(jìn)行資源的調(diào)度，從而提高功率資源的利用率。最后，通過大量仿真實驗，證明了功率分配算法G2SPA的正確性和有效性。

附錄A 算法1：價格更新函數(shù)

附錄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

A

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

2015-03-10；

2015-05-25

長江學(xué)者和創(chuàng)新團(tuán)隊發(fā)展計劃基金資助項目(No.IRT1299)；重慶市基礎(chǔ)與前沿研究計劃基金資助項目(No.cstc2015jcyjA40048)；重慶郵電大學(xué)青年科學(xué)研究基金資助項目(No.A2014-94)；重慶市教委科學(xué)技術(shù)研究基金資助項目(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)

曹儐（1983-），男，重慶人，重慶郵電大學(xué)講師，主要研究方向為網(wǎng)絡(luò)虛擬化、軟件定義網(wǎng)絡(luò)、資源管理和網(wǎng)絡(luò)協(xié)議設(shè)計及性能分析。

郎文強（1992-），男，安徽阜陽人，重慶郵電大學(xué)碩士生，主要研究方向為無線網(wǎng)絡(luò)虛擬化。

陳卓（1980-），男，重慶人，重慶理工大學(xué)副教授，主要研究方向為云計算、數(shù)據(jù)中心網(wǎng)絡(luò)、無線傳感器網(wǎng)絡(luò)。

李云（1974-），男，四川西充人，重慶郵電大學(xué)教授，主要研究方向為無線通信、軟件定義網(wǎng)絡(luò)。