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)控制方案，例如計算機資源優(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(wèi)(l∈{1，2，…，L})傳輸鏈路。圖2給出了多用戶多服務(wù)系統(tǒng)圖，其中λ_n表示網(wǎng)絡(luò)外新到達(dá)第n個節(jié)點的數(shù)據(jù)，a_n表示第n個節(jié)點包括新到達(dá)數(shù)據(jù)和節(jié)點間轉(zhuǎn)移數(shù)據(jù)在內(nèi)的總的數(shù)據(jù)，從節(jié)點a到節(jié)點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)的特點是：S(t)是根據(jù)一個有限狀態(tài)空間S和時間平均概率的不可約馬爾可夫鏈的拓?fù)錉顟B(tài)。I(t)是一個具有潛在拓?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 隊列模型

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

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

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

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

    定理2：如果網(wǎng)絡(luò)中所有獨立隊列是強穩(wěn)定的，則網(wǎng)絡(luò)是強穩(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ù)D_n，隊列長度Q_n，網(wǎng)絡(luò)服務(wù)量u_n。在多個節(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ù)，則隊列為Q_n(t+1)=max[Q_n(t)-u_n(t)，0]+λ_n(t)，a_n(t)=λ_n(t)；

    (2)節(jié)點流量較大，會轉(zhuǎn)移部分?jǐn)?shù)據(jù)D_n(t)到相鄰節(jié)點，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é)點流量較小，會從相鄰的節(jié)點中得到部分?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)策略來優(yōu)化如下目標(biāo)：

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

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

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

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

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

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

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

    將a_n(t)和Q_n(t)視為由w_n(t)控制的配對問題，配對問題由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è)在一個時隙內(nèi)一個用戶終端只能與一個基站相連接，即表示對相同的邊矩陣任一行列中僅有一個值為1，通過匈牙利算法來調(diào)制x_ij以匹配相應(yīng)的a_n(t)和Q_n(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ù)隨機到達(dá)5個節(jié)點，由此可以得到某一時隙網(wǎng)絡(luò)的總效用結(jié)果；在第二種場景中，200個用戶終端數(shù)據(jù)到達(dá)一個節(jié)點，由此可以得到某一時隙節(jié)點的平均開銷結(jié)果和隊列長度。本文將所提出的方案與隨機分配策略、最短優(yōu)先策略和比例公平策略進(jìn)行了對比，且在第二種場景中，當(dāng)V=25時，設(shè)定不同的突發(fā)用戶數(shù)據(jù)量，仿真結(jié)果如圖4～圖6所示。

    圖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)定，且有更低的開銷，比隨機分配策略和比例公平策略要好，僅次于最短優(yōu)先策略。

4 結(jié)論

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