0 引言

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

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

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

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

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

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

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

1.2 隊(duì)列模型

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

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

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

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

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

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

1.3 問題的定義

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

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

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

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

    (1)節(jié)點(diǎn)只有新到數(shù)據(jù)，沒有轉(zhuǎn)移數(shù)據(jù)，則隊(duì)列為Q_n(t+1)=max[Q_n(t)-u_n(t)，0]+λ_n(t)，a_n(t)=λ_n(t)；

    (2)節(jié)點(diǎn)流量較大，會(huì)轉(zhuǎn)移部分?jǐn)?shù)據(jù)D_n(t)到相鄰節(jié)點(diǎn)，Q_n(t+1)=max[Q_n(t)-u_n(t)，0]+λ_n(t)-D_n(t)，a_n(t)=λ_n(t)-D_n(t)；

    (3)節(jié)點(diǎn)流量較小，會(huì)從相鄰的節(jié)點(diǎn)中得到部分?jǐn)?shù)據(jù)D_n(t)，Q_n(t+1)=max[Q_n(t)-u_n(t)，0]+λ_n(t)+D_n(t)，a_n(t)=λ_n(t)+D_n(t)。

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

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

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

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

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

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

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

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

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

3 仿真實(shí)驗(yàn)

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

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

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

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

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

4 結(jié)論

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

參考文獻(xià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.