賈國慶，裴　冬

(1.青海民族大學(xué) 物理與電子信息工程學(xué)院，青海 西寧 810007；2.中國科學(xué)院上海微系統(tǒng)與信息技術(shù)研究所 無線傳感網(wǎng)與通信重點實驗室，上海 200050）

一種基于異構(gòu)云無線接入網(wǎng)的資源管理方案*

賈國慶1，2，裴冬2

(1.青海民族大學(xué) 物理與電子信息工程學(xué)院，青海 西寧 810007；2.中國科學(xué)院上海微系統(tǒng)與信息技術(shù)研究所 無線傳感網(wǎng)與通信重點實驗室，上海 200050）

基于有限網(wǎng)絡(luò)資源和多用戶隊列的異構(gòu)云無線接入網(wǎng)絡(luò)，分析了兩種不同用戶到達(dá)場景：有突發(fā)用戶到達(dá)和沒有突發(fā)用戶到達(dá)。提出了一種基于異構(gòu)云無線接入網(wǎng)的高穩(wěn)定動態(tài)資源管理方案：針對多隊列的穩(wěn)定性提出了一種基于動態(tài)背壓技術(shù)的框架，利用李雅普諾夫漂移保持用戶需求隊列穩(wěn)定；使用一種基于匈牙利算法的分配方案，以便盡量有效地將網(wǎng)絡(luò)資源分配給各個隊列成員。仿真結(jié)果表明，提出的資源管理方案能夠有效保證多隊列的穩(wěn)定性，相較于傳統(tǒng)的比例公平或隨機(jī)分配算法，系統(tǒng)開銷較小。

異構(gòu)云網(wǎng)絡(luò)；接入控制；無線資源分配；排隊論

0　引言

異構(gòu)網(wǎng)是應(yīng)對日益增長的數(shù)據(jù)傳輸需求挑戰(zhàn)的一種有效途徑。文獻(xiàn)[1]提出了一種新型的無線云接入網(wǎng)絡(luò)，并在文獻(xiàn)[2]中給出了詳細(xì)的描述。之前針對異構(gòu)網(wǎng)資源管理的研究主要分為兩個場景：單接入網(wǎng)的資源分配和多接入網(wǎng)的資源分配。在第一個研究場景中，移動終端只能從單一的接入網(wǎng)中獲取資源[1-3]。在第二個場景中，移動終端可以同時從所有可用的無線接入網(wǎng)絡(luò)中獲取資源，因此也被稱為多尋解方案[4]。之前的研究都集中在提高傳統(tǒng)的多隊列網(wǎng)絡(luò)的延遲性能。一種方法是使用大偏差理論將平均延遲約束轉(zhuǎn)化為等效平均速率，再利用約束條件下的信息理論公式求解優(yōu)化問題[5]；另一種方法是使用李雅普諾夫穩(wěn)定性理論來建立一個高吞吐量的最優(yōu)控制方案，例如計算機(jī)資源優(yōu)化[6]，或?qū)崿F(xiàn)分組交換系統(tǒng)的穩(wěn)定[7-9]。

本文的研究主要集中在基站用戶需求隊列的穩(wěn)定性，采用李雅普諾夫漂移保證隊列的穩(wěn)定性和改進(jìn)的匈牙利來實現(xiàn)更高效的資源分配。

1　系統(tǒng)模型與問題分析

1.1網(wǎng)絡(luò)模型

如圖1所示，本文提出了一種多隊列多服務(wù)的異構(gòu)云無線接入網(wǎng)絡(luò)架構(gòu)。在該架構(gòu)中，將節(jié)點視為隊列并將節(jié)點中等待服務(wù)的用戶視為隊列成員，根據(jù)節(jié)點的流量來調(diào)節(jié)不同節(jié)點用戶的相互轉(zhuǎn)移。

假設(shè)異構(gòu)云無線接入網(wǎng)絡(luò)有 n(n∈{1，2，…，N})個節(jié)點，節(jié)點間有 l(l∈{1，2，…，L})傳輸鏈路。圖2給出了多用戶多服務(wù)系統(tǒng)圖，其中λn表示網(wǎng)絡(luò)外新到達(dá)第n個節(jié)點的數(shù)據(jù)，an表示第n個節(jié)點包括新到達(dá)數(shù)據(jù)和節(jié)點間轉(zhuǎn)移數(shù)據(jù)在內(nèi)的總的數(shù)據(jù)，從節(jié)點a到節(jié)點b的數(shù)據(jù)轉(zhuǎn)移表示為((al，bl)，a，b∈{1，2，…，N})。S(t)∈S表示網(wǎng)絡(luò)的拓?fù)錉顟B(tài)，S是狀態(tài)集。在平穩(wěn)狀態(tài)下，S(t)被認(rèn)為是恒定的。I(t)∈IS表示分配控制決策，IS表示在給定狀態(tài)S下的所有資源分配決策集。該網(wǎng)絡(luò)結(jié)構(gòu)的特點是：S(t)是根據(jù)一個有限狀態(tài)空間 S和時間平均概率的不可約馬爾可夫鏈的拓?fù)錉顟B(tài)。I(t)是一個具有潛在拓?fù)錉顟B(tài)的控制空間的控制決策變量。

圖1　異構(gòu)云無線接入網(wǎng)絡(luò)

圖2　多用戶多服務(wù)系統(tǒng)圖

C(I(t)，S(t))={Cab(I(t)，S(t))|a，b∈{1，2，…，N}，a≠b}定義為傳輸速率函數(shù)矩陣，其中 Cab(I(t)，S(t))表示在分配控制 IS和網(wǎng)絡(luò)拓?fù)錉顟B(tài) S下經(jīng)過鏈路(al，bl)的傳輸速率，它是有界的任意值。

1.2隊列模型

用Qn(t)表示在時間間隙t時在第n個節(jié)點等待網(wǎng)絡(luò)服務(wù)的隊列成員數(shù)目，an(t)表示第 n個節(jié)點包括新到達(dá)數(shù)據(jù)和節(jié)點間轉(zhuǎn)移數(shù)據(jù)在內(nèi)的總的數(shù)據(jù)，un(t)表示在時間間隙t時，第n個節(jié)點中獲得網(wǎng)絡(luò)服務(wù)的用戶數(shù)據(jù)，則動態(tài)隊列長度表示式：

a(t)=(a1(t)，a2(t)，…，an(t))和 u(t)=(u1(t)，u2(t)，…，un(t))表示是隨機(jī)事件的一般函數(shù)。表示隨機(jī)事件w(t)的一般函數(shù)表達(dá)式及一個控制行為表達(dá)式為α(t)：αn(t)=an(α(t)，w(t))。每個時隙中由網(wǎng)絡(luò)控制器觀察w(t)并選擇合適的α(t)∈Aw(t)，Aw(t)表示與事件 w(t)的控制空間集。李雅普諾夫漂移是一種有助于網(wǎng)絡(luò)隊列穩(wěn)定并進(jìn)行穩(wěn)定的控制的有效數(shù)學(xué)工具，利用負(fù)李雅普諾夫漂移理論，在馬爾可夫鏈中可以形成一個成熟的的穩(wěn)定理論。

定理1：隊列被稱為強(qiáng)穩(wěn)定，如果有：

即如果隊列有一個有界的時間平均累積，則該隊列強(qiáng)穩(wěn)定。

定理2：如果網(wǎng)絡(luò)中所有獨立隊列是強(qiáng)穩(wěn)定的，則網(wǎng)絡(luò)是強(qiáng)穩(wěn)定的。

本文假設(shè)滿足以下條件時，系統(tǒng)是穩(wěn)定的：

1.3問題的定義

系統(tǒng)的目標(biāo)是找到一個資源分配和調(diào)度方案，最大化減少隊列的延遲和長度，該問題表示為：

2　高穩(wěn)定性動態(tài)資源管理方案

2.1動態(tài)背壓資源管理框架

如圖3所示，對任一節(jié)點n，其隊列模型包括：新到的數(shù)據(jù) λn，轉(zhuǎn)移數(shù)據(jù) Dn，隊列長度 Qn，網(wǎng)絡(luò)服務(wù)量 un。在多個節(jié)點的隊列的基礎(chǔ)上進(jìn)行無線資源的分配，時間間隙t表示時間為[t，t+1)。所有的節(jié)點都會存在新到用戶數(shù)據(jù)，且相互獨立。而轉(zhuǎn)移用戶數(shù)據(jù)則與節(jié)點及其相鄰節(jié)點的數(shù)據(jù)流量有關(guān)，新到數(shù)據(jù)服從泊松分布，且E[λn(t)]=λn。由此根據(jù)不同的節(jié)點流量，可以將動態(tài)隊列分為以下3種情況：

(1)節(jié)點只有新到數(shù)據(jù)，沒有轉(zhuǎn)移數(shù)據(jù)，則隊列為Qn(t+1)=max[Qn(t)-un(t)，0]+λn(t)，an(t)=λn(t)；

(2)節(jié)點流量較大，會轉(zhuǎn)移部分?jǐn)?shù)據(jù)Dn(t)到相鄰節(jié)點，Qn(t+1)=max[Qn(t)-un(t)，0]+λn(t)-Dn(t)，an(t)=λn(t)-Dn(t)；

(3)節(jié)點流量較小，會從相鄰的節(jié)點中得到部分?jǐn)?shù)據(jù)Dn(t)，Qn(t+1)=max[Qn(t)-un(t)，0]+λn(t)+Dn(t)，an(t)=λn(t)+ Dn(t)。

圖3　典型節(jié)點的數(shù)據(jù)隊列圖

(1)選擇合適的資源控制I(t)策略來優(yōu)化如下目標(biāo)：

根據(jù)各節(jié)點的隊列長度和服務(wù)速率，使用改進(jìn)的匈牙利算法來實現(xiàn)更好的效用匹配。

(2)根據(jù)式(4)即時更新隊列數(shù)據(jù)。

首先介紹背壓控制策略wn(t)。假設(shè) wn(t)表示是一個概率分布為 π(w)的平穩(wěn)過程，wn(t)在集合 Ω中取值，對任意 wn(t)∈Ω，π(t)表示關(guān)聯(lián)隊列長度 Qn(t)和到達(dá)數(shù)據(jù)an(t)的概率函數(shù)，且：

除了隊列需要穩(wěn)定的 Qn(t)，本文也使用一個輔助的隨機(jī)相關(guān)量 y(t)，它的時間平均值會小于或接近特定值y*，假設(shè) y(t)的下界為 ymin，因此任意時隙以及任何可能的分配控制策略都會存在E{y(t)}≥ymin。

定理 3：假設(shè)有 L(Q(t))，ymin，E[L(Q(0))]＜∞，則存在常數(shù) B≥0，V≥0，ε≥0和 ymin，使得對任意時隙和所有的隊列值，有：

則所有的隊列都是穩(wěn)定的，而且若V≥0，ε≥0，有：

任一時隙，網(wǎng)絡(luò)觀察當(dāng)前的隊列長度值Qn(t)和到達(dá)數(shù)據(jù)量 an(t)，然后用匈牙利算法來匹配 Qn(t)和 an(t)，以減少Δ(Q(τ))+VE{y(t)|Q(τ)}表示的漂移值。

2.2針對多隊列的李雅普諾夫漂移技術(shù)

2.3針對資源分配的改進(jìn)匈牙利算法

將 an(t)和 Qn(t)視為由 wn(t)控制的配對問題，配對問題由U和V兩部分組成，以及帶有權(quán)重的邊集合E。假定ai(t)∈V，i∈1，2，…，N，Qj(t)∈U，j∈1，2，…，N，則 xij為n×n單位陣。假設(shè)在一個時隙內(nèi)一個用戶終端只能與一個基站相連接，即表示對相同的邊矩陣任一行列中僅有一個值為 1，通過匈牙利算法來調(diào)制 xij以匹配相應(yīng)的an(t)和 Qn(t)來實現(xiàn)：

3　仿真實驗

仿真中，有5個節(jié)點和充足的用戶終端數(shù)據(jù)。在沒有突發(fā)數(shù)據(jù)到達(dá)的情況下，新到達(dá)的數(shù)據(jù)服從泊松分布，到達(dá)速率均為λ=2/3；在有突發(fā)數(shù)據(jù)到達(dá)的情況下，新到數(shù)據(jù)同樣服從泊松分布，且速率也為λ=2/3，只是在某一時間節(jié)點會到達(dá)大量的用戶數(shù)據(jù)。先到先服務(wù)是隊列成員獲得網(wǎng)絡(luò)服務(wù)的準(zhǔn)則，各信道狀態(tài)S(t)在同一時隙相互獨立，且其概率設(shè)定為20%。各節(jié)點的服務(wù)速率是固定的，網(wǎng)絡(luò)的總服務(wù)速率為 r=1，為了計算簡便，假定各節(jié)點的最大容量均為10，并給定相應(yīng)的服務(wù)質(zhì)量標(biāo)準(zhǔn)。

本文做了兩種不同場景下的仿真，在第一種場景中，用戶終端數(shù)據(jù)隨機(jī)到達(dá)5個節(jié)點，由此可以得到某一時隙網(wǎng)絡(luò)的總效用結(jié)果；在第二種場景中，200個用戶終端數(shù)據(jù)到達(dá)一個節(jié)點，由此可以得到某一時隙節(jié)點的平均開銷結(jié)果和隊列長度。本文將所提出的方案與隨機(jī)分配策略、最短優(yōu)先策略和比例公平策略進(jìn)行了對比，且在第二種場景中，當(dāng) V=25時，設(shè)定不同的突發(fā)用戶數(shù)據(jù)量，仿真結(jié)果如圖4～圖6所示。

圖4　所有節(jié)點的總效用

圖4給出了第一種場景下的仿真結(jié)果，從圖中可以看出，當(dāng)V接近40時，隊列趨于穩(wěn)定。

圖5給出了沒有突發(fā)用戶數(shù)據(jù)的場景，設(shè)節(jié)點服務(wù)率 r(AP5)＞r(AP4)＞r(AP3)＞r(AP2)＞r(AP1)，且 r(AP3)比r(AP2)略大。從圖5可以看出，當(dāng)V∈[35，50]時，各個用戶隊列趨于穩(wěn)定，節(jié)點的服務(wù)速率越大，隊列穩(wěn)定的越快。然而，盡管AP3的服務(wù)速率比AP2略高，AP3的平均開銷卻比AP2要低一些，這表明平均開銷并非僅由節(jié)點服務(wù)速率決定。當(dāng)隊列趨于穩(wěn)定后，各節(jié)點隊列的平均開銷依然維持在較低值。

圖6給出了沒有突發(fā)用戶數(shù)據(jù)場景下不同方案的總開銷，結(jié)果表明本方案中隊列會更快趨于穩(wěn)定，且有更低的開銷，比隨機(jī)分配策略和比例公平策略要好，僅次于最短優(yōu)先策略。

圖5　各節(jié)點的平均開銷

圖6　不同方案的總開銷

4　結(jié)論

本文研究異構(gòu)的資源管理問題，重點分析了擁擠用戶時的隊列穩(wěn)定性問題，以及用戶對無線資源的需求，并提出了一種新的高穩(wěn)定的動態(tài)資源管理方案。與其他研究不同之處是，本文假定各節(jié)點的容量是有限的，并進(jìn)而提出了一種新的用戶隊列模型，在此基礎(chǔ)上，分析了兩種不同場景下的資源管理問題并進(jìn)行了仿真實驗。仿真結(jié)果表明，本文基于李雅普諾夫漂移和匈牙利算法的異構(gòu)云無線接入網(wǎng)絡(luò)資源管理方案，相較于傳統(tǒng)的隨機(jī)分配、比例公平以及最短有限方案而言，在隊列的穩(wěn)定性以及開銷上有更好的性能。

[1]BLAU I，WUNDER G，KARLA I.Decentralized utility maximization in heterogeneous multicell scenarios with interference limited and orthogonal air interfaces[J].EURASIP Journal on Wireless Communications and Networking，2009，20(12)：104-116.

[2]SHEN W，ZENG Q.Resource management schemes for multiple traffic in integrated heterogeneous wireless and mobile networks[C].Proceedings of 17th International Conference on Computer Communications and Networks，US Virgin Islands，2008：1-6.

[3]PEI X，JIANG T，QU D，et al.Radio resource management and access control mechanism based on a novel economic model in heterogeneous wireless networks[J].IEEE Transactions on Vehicular Technology，2010，59(6)：3047-3056.

[4]NIYATO D，HOSSAIN E.Bandwidth allocation in 4G heterogeneous wireless access networks:A non cooperative game theoretical approach[C].Proceedings of IEEE Global Telecommunications Conference，San Francisco，CA，2006：1-5.

[5]TAO M，LIANG Y C，ZHANG F.Resource allocation for delay differentiated traffic in multiuser OFDM systems[J].IEEE Transactions on Wireless Communications，2008，7(6)：2190-2201.

[6]BHATTACHARYA P，GEORGIADIS L，TSOUCAS P.Adaptive lexicographic optimization in multi-class M/GI/1 queues[J].Math.Operat.Res.，1993，18(3)：705-740.

[7]RADUSINOVIC I，PEJANOVIC M，PETROVIC Z.An ILPF cell scheduling algorithm for ATM input-queued switch with service class priority[C].Proceedings of 6th International Conference on Telecommunications in Modern Satellite，Cable and Broadcasting Service，2003，1：26-29.

[8]KUMAR P R，MEYN S P.Stability of queueing networks and scheduling policies[J].IEEE Transactions on Automatic Control，1995，40(2)：251-260.

[9]ANDREWS M，KUMARAN K，RAMANAN K，et al.Providing quality of service over a shared wireless link[J].IEEE Commun.Mag，2001，39(2)：150-154.

A resource management scheme based on heterogeneous wireless network

Jia Guoqing1，2，Pei Dong2
(1.School of Pyhsics and Electronic Information Engineering，Qinghai University for Nationalities，Xining 810007，China；2.Shanghai Institue of Microsystem&Information Technology，Chinese Academy of Sciences，Shanghai 200050，China)

A cloud based HetNet architecture with limited network resources and multiple queues regarding to users′requirements is presented and two different users′arrival scenarios with and without burst traffic are studied.Then a novel High Stable dynamic Resource Management Scheme(HS-RMS)for the HetNet is proposed.Specifically,a dynamic backpressure technique based framework for multiple queues′stability is presented,and then a Lyapunov drift method is applied to keep users′requirement queues stable.A Hungarian algorithm based allocation scheme is provided to allocate resources to each queue member efficiently.Extensive simulations have been done,and results show that the proposed resource allocation scheme is very robust to keep the queues stable and the overhead is low as compared to conventional proportional fairness or round-robin algorithms.

heterogenous network；access control；radio resource allocation；queueing theory

TN911

A

10.16157/j.issn.0258-7998.2016.10.027

中國科學(xué)院上海微系統(tǒng)與信息技術(shù)研究所無線傳感網(wǎng)與通信重點實驗室開放基金（2016002）；青海省自然科學(xué)基金(2016-ZJ-922Q)

（2016-04-28）

賈國慶（1984-），男，博士，副教授，主要研究方向：無線通信物理層關(guān)鍵技術(shù)。

裴冬（1989-），通信作者，男，碩士研究生，主要研究方向：無線通信車聯(lián)網(wǎng)技術(shù)，E-mail：dong.pei@wico.sh。

中文引用格式：賈國慶，裴冬.一種基于異構(gòu)云無線接入網(wǎng)的資源管理方案[J].電子技術(shù)應(yīng)用，2016，42(10)：104-107.

英文引用格式：Jia Guoqing，Pei Dong.A resource management scheme based on heterogeneous wireless network[J].Application of Electronic Technique，2016，42(10)：104-107.