異構(gòu)網(wǎng)絡(luò)中基于Stackelberg博弈的資源分配方案

胡弦鋒，鄭 霖

(桂林電子科技大學(xué) 通信與信息學(xué)院，廣西 桂林 541004)

?

異構(gòu)網(wǎng)絡(luò)中基于Stackelberg博弈的資源分配方案

胡弦鋒，鄭 霖

(桂林電子科技大學(xué) 通信與信息學(xué)院，廣西 桂林 541004)

針對(duì)異構(gòu)網(wǎng)絡(luò)中資源分配問題，文中結(jié)合用戶業(yè)務(wù)需求多樣性，提出了一種基于Stackelberg博弈的資源分配方案。在該方案中，互聯(lián)代理節(jié)點(diǎn)(Agent Node)作為領(lǐng)導(dǎo)者(Leader)制定價(jià)格策略，用戶作為跟隨者(Follower)，根據(jù)自身業(yè)務(wù)需求，在多互聯(lián)節(jié)點(diǎn)間進(jìn)行接入選擇，以滿足自身QoS需求。文中證明了在代理節(jié)點(diǎn)的價(jià)格確定后，用戶之間非合作博弈納什均衡點(diǎn)的存在性。仿真結(jié)果表明，所提出的資源分配方案，可以提高網(wǎng)絡(luò)總的帶寬利用率，提升用戶對(duì)帶寬接入的滿意程度。

異構(gòu)網(wǎng)絡(luò); 無線資源分配; Stackelberg博弈; 多點(diǎn)接入

在異構(gòu)融合的網(wǎng)絡(luò)環(huán)境下，用戶通常被多個(gè)無線網(wǎng)絡(luò)覆蓋，通過接入不同的網(wǎng)絡(luò)來滿足自身的QoS需求。但帶寬資源[1]、頻譜資源[2]和功率資源[3]等網(wǎng)絡(luò)資源是有限的，每個(gè)用戶都希望在網(wǎng)絡(luò)中獲得最好的服務(wù)體驗(yàn)，這就造成了用戶之間對(duì)網(wǎng)絡(luò)資源的競(jìng)爭(zhēng)。同時(shí)，網(wǎng)絡(luò)運(yùn)營(yíng)者也希望通過合理的網(wǎng)絡(luò)資源分配，來提高網(wǎng)絡(luò)的吞吐量和網(wǎng)絡(luò)資源利用率，所以對(duì)無線資源的管理和分配，成為異構(gòu)網(wǎng)絡(luò)融合關(guān)鍵技術(shù)研究的重點(diǎn)之一。

異構(gòu)無線網(wǎng)絡(luò)進(jìn)行聯(lián)合無線資源管理[4](Joint Radio Resource Management，JRRM)主要分為集中式，分布式和混合式管理模式。在分布式的管理模式下，用戶選擇如何接入網(wǎng)絡(luò)、網(wǎng)絡(luò)如何分配無線資源，是影響用戶QoS和網(wǎng)絡(luò)性能的主要因素，常用的網(wǎng)絡(luò)選擇和資源分配方法可以分為多屬性決策法[5-6]、最優(yōu)化方法[7]、馬爾科夫鏈法[8]、模糊邏輯法[9-10]和博弈論方法[11-13]等。

本文提出利用Stackelberg博弈模型，在無線自組織網(wǎng)絡(luò)與蜂窩網(wǎng)融合的情況下，對(duì)網(wǎng)絡(luò)帶寬資源進(jìn)行分配。處于自組織網(wǎng)絡(luò)中的移動(dòng)用戶(Mobile Users)，可以同時(shí)向多個(gè)同時(shí)處于蜂窩網(wǎng)的代理節(jié)點(diǎn)(Agent Nodes)申請(qǐng)帶寬資源，如圖1所示。代理節(jié)點(diǎn)通過網(wǎng)絡(luò)定價(jià)，來影響移動(dòng)用戶的帶寬策略，使自身效用最大化。在本文中，不僅考慮了不同優(yōu)先級(jí)用戶對(duì)帶寬的競(jìng)爭(zhēng)、代理節(jié)點(diǎn)與用戶相互之間的交互，同時(shí)，也對(duì)代理節(jié)點(diǎn)和所競(jìng)爭(zhēng)代理節(jié)點(diǎn)的網(wǎng)絡(luò)狀態(tài)進(jìn)行考慮，制定出最優(yōu)價(jià)格策略。文中證明了在代理節(jié)點(diǎn)制定價(jià)格策略后，移動(dòng)用戶所制定的效用函數(shù)滿足凹函數(shù)的特性，保證了移動(dòng)用戶間構(gòu)成的非合作博弈納什均衡的存在，最后利用分布式迭代算法，使系統(tǒng)收斂到均衡點(diǎn)。仿真結(jié)果表明，本文所提算法提升了移動(dòng)用戶的QoS滿意度，提高了網(wǎng)絡(luò)帶寬利用率。

圖1 網(wǎng)絡(luò)模型

1 系統(tǒng)模型

考慮在無線自組織網(wǎng)絡(luò)和蜂窩網(wǎng)融合的架構(gòu)[14]下，有m個(gè)代理節(jié)點(diǎn)位于蜂窩網(wǎng)邊緣，在代理節(jié)點(diǎn)的覆蓋范圍內(nèi)有n個(gè)移動(dòng)用戶。由于多模終端的出現(xiàn)，移動(dòng)用戶可以同時(shí)接入多個(gè)代理節(jié)點(diǎn)，向多個(gè)代理節(jié)點(diǎn)申請(qǐng)網(wǎng)絡(luò)資源。網(wǎng)絡(luò)資源大致可以分為帶寬資源、功率資源等，文中蜂窩網(wǎng)總帶寬用B表示。不同移動(dòng)用戶業(yè)務(wù)類型不同，所以不同移動(dòng)用戶有各自的業(yè)務(wù)優(yōu)先級(jí)，設(shè)定移動(dòng)用戶優(yōu)先級(jí)集合為θ={θ1,θ2,…,θn}，同時(shí)，不同業(yè)務(wù)優(yōu)先級(jí)的用戶具有不同的帶寬需求，設(shè)定移動(dòng)用戶帶寬需求集合為R={r1,r2,…,rn}。代理節(jié)點(diǎn)通過定價(jià)來影響移動(dòng)用戶的帶寬策略，設(shè)P={p1,p2,…,pm}為所有代理節(jié)點(diǎn)價(jià)格策略集合。

由于移動(dòng)用戶都希望通過制定相應(yīng)的帶寬策略，來使自己的收益最大化，這種自私的行為使得移動(dòng)用戶之間的競(jìng)爭(zhēng)構(gòu)成了一個(gè)非合作博弈，非合作博弈往往會(huì)引起網(wǎng)絡(luò)的低效性。但是，通過代理節(jié)點(diǎn)的引導(dǎo)，可以有效提高網(wǎng)絡(luò)的性能。

1.1 基于Stackelberg 貝葉斯博弈的資源分配

Stackelberg模型中主要要素有：領(lǐng)導(dǎo)者、跟隨者、效用函數(shù)和行動(dòng)策略。

領(lǐng)導(dǎo)者：將代理節(jié)點(diǎn)定義為領(lǐng)導(dǎo)者(Leader)，領(lǐng)導(dǎo)者根據(jù)自身能耗約束和競(jìng)爭(zhēng)對(duì)手策略變化，來制定自己的價(jià)格策略，使自身利益最大化。

跟隨者：將自組織網(wǎng)絡(luò)中的移動(dòng)用戶定義為跟隨者(Follower)，跟隨者在領(lǐng)導(dǎo)者作出決策后，根據(jù)領(lǐng)導(dǎo)者的價(jià)格策略，來制定自身的帶寬需求策略。

行動(dòng)策略：移動(dòng)用戶的策略是向代理節(jié)點(diǎn)申請(qǐng)帶寬，而代理節(jié)點(diǎn)的策略是制定帶寬價(jià)格，從而使自身在為其他節(jié)點(diǎn)服務(wù)中獲取更高的利益。

效用函數(shù)：是研究博弈的一個(gè)重要衡量手段。對(duì)于代理節(jié)點(diǎn)，效用函數(shù)為所出售帶寬給自己帶來的經(jīng)濟(jì)效益。對(duì)于移動(dòng)用戶，效用不僅要考慮所得帶寬給自己帶來的利益，同時(shí)還得考慮購(gòu)買帶寬所產(chǎn)生的開銷。

1.2 移動(dòng)用戶效用函數(shù)

移動(dòng)用戶對(duì)帶寬的競(jìng)爭(zhēng)，構(gòu)成了非合作博弈關(guān)系。用戶根據(jù)效用函數(shù)制定帶寬需求策略，以使自身利益最大化，通常用戶效用函數(shù)由兩部分組成：帶寬所帶來的收益和獲得收益所產(chǎn)生的花銷。對(duì)于移動(dòng)用戶i(i=1,2,…,n)，其效用函數(shù)Fi(p,qi,q-i)可以表示為

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

(1)

其中，qi表示用戶i的帶寬策略集合；q-i表示其他用戶的帶寬策略集合，式(1)中前一項(xiàng)為帶寬給用戶帶來的收益，這里采用對(duì)數(shù)效用函數(shù)形式[15]來表示

(2)

式中，qij為移動(dòng)用戶i向代理節(jié)點(diǎn)j申請(qǐng)的帶寬量；θi為移動(dòng)用戶的優(yōu)先級(jí)，由于用戶業(yè)務(wù)優(yōu)先級(jí)的不同，不同移動(dòng)用戶對(duì)帶寬資源的競(jìng)爭(zhēng)力不同。移動(dòng)用戶業(yè)務(wù)優(yōu)先級(jí)越高，在帶寬競(jìng)爭(zhēng)中越有競(jìng)爭(zhēng)力。式(1)后一項(xiàng)表示用戶開銷，為

(3)

式中，pj為代理節(jié)點(diǎn)j的定價(jià)；Dij表示用戶i到代理節(jié)點(diǎn)j的距離因子，由于距離會(huì)使用戶產(chǎn)生額外開銷，所以Dij>1，離代理節(jié)點(diǎn)越近，由距離產(chǎn)生的開銷越小，Dij越小，這里引入距離因子來反映距離給用戶帶來的開銷。于是，用戶i的效用函數(shù)可以表示為

(4)

1.3 移動(dòng)用戶納什均衡點(diǎn)及證明

定理 當(dāng)代理節(jié)點(diǎn)公布定價(jià)策略P={p1,p2,…,pn}后，移動(dòng)用戶的非合作博弈存在唯一納什均衡解[16]。

證明 根據(jù)博弈論可知，博弈論模型滿足以下兩個(gè)條件，則存在納什均衡：(1)策略空間在歐幾里得空間中是非空的，有界的閉集；(2)效用函數(shù)在其策略空間上是連續(xù)的凹函數(shù)。

顯然，任意用戶 的帶寬策略空間是在歐幾里得空間中的有界閉集，同時(shí)，用戶的效用函數(shù)在其策略空間上是連續(xù)的，下面證明效用函數(shù)為凹函數(shù)。首先，對(duì)任意用戶效用函數(shù)求一階偏導(dǎo)，得

(5)

對(duì)式(5)求二階偏導(dǎo)數(shù)，得

(6)

顯然，用戶效用函數(shù)二階導(dǎo)數(shù)<0，是嚴(yán)格的凹函數(shù)，所以用戶間的博弈存在納什均衡。

1.4 代理節(jié)點(diǎn)的效用函數(shù)

對(duì)于代理節(jié)點(diǎn)，其效用函數(shù)不僅要考慮出售帶寬所帶來的收益，而且需要考慮帶寬成本和能耗成本，任意代理節(jié)點(diǎn)j效用函數(shù)可以表示為

(8)

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

(9)

2 算法過程描述

本文采用分布式迭代算法，使移動(dòng)用戶和代理節(jié)點(diǎn)達(dá)到均衡點(diǎn)。在任意K時(shí)刻，代理節(jié)點(diǎn)公布制定的價(jià)格策略后，移動(dòng)用戶通過一個(gè)簡(jiǎn)單的動(dòng)態(tài)模型，來調(diào)節(jié)自身帶寬策略。具體移動(dòng)用戶i的帶寬變化策略可以描述為

(10)

其中，k為時(shí)間變量；αi為移動(dòng)用戶i調(diào)節(jié)帶寬的步長(zhǎng)。由于效用函數(shù)凹函數(shù)的特性，保證了迭代算法最終收斂到穩(wěn)定的納什均衡點(diǎn)。在K+1時(shí)刻，代理節(jié)點(diǎn)制定新一輪的定價(jià)，通過對(duì)式(9)求價(jià)格一階導(dǎo)數(shù)，并令其為零，可以得到代理節(jié)點(diǎn)的最優(yōu)價(jià)格策略。

3 仿真與分析

仿真考慮蜂窩網(wǎng)和自組織網(wǎng)絡(luò)融合的架構(gòu)下，在蜂窩網(wǎng)中有3個(gè)代理節(jié)點(diǎn)，代理節(jié)點(diǎn)的覆蓋范圍為500 m，在代理節(jié)點(diǎn)覆蓋范圍內(nèi)隨機(jī)分布了6個(gè)移動(dòng)用戶，用戶通過多接入技術(shù)向代理節(jié)點(diǎn)申請(qǐng)帶寬，其信息如表1所示，每個(gè)用戶對(duì)不同代理節(jié)點(diǎn)的初始帶寬策略均0。蜂窩網(wǎng)的總帶寬B=25 Mbit·s-1，單位帶寬成本 設(shè)為0.1。仿真中，移動(dòng)用戶調(diào)整帶寬策略步進(jìn)均為0.1，即α1=α2=…=0.1。代理節(jié)點(diǎn)單位帶寬能耗分別為e1=0.03，e2=0.04，e3=0.02，單位nW/Mbit。

表1 用戶參數(shù)

首先，對(duì)代理節(jié)點(diǎn)的出價(jià)策略進(jìn)行分析，圖2為代理節(jié)點(diǎn)的出價(jià)策略變化情況，從圖中可以看出，隨著博弈的進(jìn)行，代理節(jié)點(diǎn)的價(jià)格策略不斷變化，最終收斂到一個(gè)定值，即納什均衡點(diǎn)。

圖2 代理節(jié)點(diǎn)價(jià)格策略

圖3給出代理節(jié)點(diǎn)在迭代過程中負(fù)載的變化情況。其中，代理節(jié)點(diǎn)單位帶寬能耗越小，其吞吐量越大，反之，其吞吐量越小，這使得吞吐量在代理節(jié)點(diǎn)間得到均衡，避免了個(gè)別代理節(jié)點(diǎn)能量過早耗盡，而退出網(wǎng)絡(luò)。

圖3 代理節(jié)點(diǎn)吞吐量的變化

圖4～圖5顯示的是用戶滿意度對(duì)比。本文定義用戶滿意度為用戶所分配的帶寬與該用戶帶寬需求量的比值。從圖中可以看出，由于用戶優(yōu)先級(jí)、所處位置和帶寬需求量不同，不同用戶滿意度不同。相比于不區(qū)分用戶業(yè)務(wù)特性的算法，本算法根據(jù)用戶業(yè)務(wù)各自的需求特性因地制宜地為每個(gè)用戶分配帶寬，提高了用戶滿意度。

圖4 本算法用戶滿意度的變化

圖5 對(duì)比算法用戶滿意度的變化

圖6顯示的是網(wǎng)絡(luò)帶寬利用率的對(duì)比。從圖中可以看出，不區(qū)分用戶業(yè)務(wù)特性的算法的總體帶寬利用率不到75%，而本文所提算法的帶寬利用率超過了80%，提高了網(wǎng)絡(luò)總體的帶寬利用率。

圖6 網(wǎng)絡(luò)帶寬利用率對(duì)比

4 結(jié)束語(yǔ)

本文提出了一種基于Stackelberg 博弈的資源分配算法。該算法通過Stackelberg 模型，分析了不同優(yōu)先級(jí)用戶之間的博弈行為。代理節(jié)點(diǎn)在制定價(jià)格時(shí)，不僅考慮了用戶的帶寬需求，用戶根據(jù)自身位置、優(yōu)先級(jí)和帶寬需求量，通過多接入技術(shù)，有選擇地接入代理節(jié)點(diǎn)，調(diào)整帶寬策略，滿足自己的QoS需求。仿真結(jié)果表明，該算法不僅提高了用戶性能，而且提高了系統(tǒng)帶寬利用率，更符合對(duì)稀缺帶寬資源有效有效利用的要求。

[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] 姜永，陳山枝，胡博.異構(gòu)無線網(wǎng)絡(luò)中基于Stackelberg 博弈的分布式定價(jià)和資源分配算法[J].通信學(xué)報(bào),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

國(guó)家自然科學(xué)基金資助項(xiàng)目(61362006)；廣西無線寬帶通信與信號(hào)處理重點(diǎn)實(shí)驗(yàn)室課題資助項(xiàng)目(GXKL061501)

鄭霖(1974-)，男，博士，教授。研究方向：超寬帶通信等。胡弦鋒(1989-)，男，碩士研究生。研究方向：異構(gòu)網(wǎng)絡(luò)融合與網(wǎng)絡(luò)優(yōu)化。

TN926

A

1007-7820(2016)12-065-04