宋亞楠，仲 茜，曲光亮，李興立

(1. 清華大學(xué)計算機科學(xué)與技術(shù)系，北京 10008 4；2. 72241部隊，濟南 25002 9)

多基站協(xié)作無線資源分配方法

宋亞楠1,2，仲 茜2，曲光亮2，李興立2

(1. 清華大學(xué)計算機科學(xué)與技術(shù)系，北京 10008 4；2. 72241部隊，濟南 25002 9)

現(xiàn)有基于效用的無線網(wǎng)絡(luò)資源分配方法大多未考慮網(wǎng)絡(luò)整體效用最優(yōu)的問題，只關(guān)注基站內(nèi)的資源分配最優(yōu)化，沒有將基站選擇問題與基站內(nèi)資源分配問題相結(jié)合。鑒于此，提出一種基于效用的多基站協(xié)作無線資源分配方法，將無線網(wǎng)絡(luò)資源分配劃分為2個階段，即基于擁塞度選擇基站與基于邊際效用實現(xiàn)基站內(nèi)的資源分配。仿真實驗結(jié)果表明，在268次基站選擇中，該方法與效用最優(yōu)的基線方法有218次相同，占81.3%，但其平均用時只有0.066 s，遠低于基線方法的0.926 s，從而驗證了該基站選擇方法的合理性，以及基站內(nèi)資源分配方法的有效性和高效性。

效用；效用函數(shù)；邊際效用；無線網(wǎng)絡(luò)；資源分配；多基站協(xié)作

1 概述

效用(utility)資源分配方法[1-2]克服了傳統(tǒng)的基于帶寬共享的分配方法[3-4]在滿足用戶對網(wǎng)絡(luò)服務(wù)質(zhì)量(Quality of Service, QoS)需求方面的不足，成為網(wǎng)絡(luò)資源分配研究的熱點。效用原本是經(jīng)濟學(xué)中的概念，由文獻[5]引入到網(wǎng)絡(luò)研究中，表示用戶對網(wǎng)絡(luò)服務(wù)質(zhì)量的滿意程度。隨著無線網(wǎng)絡(luò)的高速發(fā)展[6]，無線網(wǎng)絡(luò)中利用效用的資源分配問題逐漸引起了研究人員的重視，出現(xiàn)了許多有價值的研究成果[7-8]。特別是文獻[9]在文獻[8]的基礎(chǔ)上，提出了統(tǒng)一形式的效用函數(shù)和多業(yè)務(wù)下基于效用的資源分配方法，是較有效的無線網(wǎng)絡(luò)資源分配方法。然而上述方法只關(guān)注單一無線基站的資源分配，忽略了基站選擇對網(wǎng)絡(luò)整體效用的影響，無法獲得網(wǎng)絡(luò)整體效用最大化。并且，資源分配方法的速度較低，在實際應(yīng)用中存在一定的實用性問題。

為了克服目前方法的不足，本文提出了一種兩階段多基站協(xié)作無線網(wǎng)絡(luò)資源分配方法，該方法首先基于擁塞度選擇基站，與傳統(tǒng)的基于信號強度的基站選擇方法[10]相比，該方法綜合應(yīng)用信號強度、資源總量、資源需求量等參數(shù)，更全面合理；然后利用高速的基于邊際效用的資源分配方法[2]實現(xiàn)各個基站內(nèi)的資源分配。

2 基本概念

定義1 效用函數(shù)是效用的量化表示形式，記作U(ri)，ri為服務(wù)i分配到的資源參數(shù)(如帶寬)。

定義2 邊際效用指在一定時間內(nèi)消費者增加一個單位商品或服務(wù)所帶來的新增效用。

定義3 邊際效用函數(shù)是相關(guān)網(wǎng)絡(luò)資源參數(shù)與邊際效用間的映射關(guān)系，記作u(ri)，是U的導(dǎo)函數(shù)。

[2-5]，將網(wǎng)絡(luò)業(yè)務(wù)分為彈性業(yè)務(wù)和非彈性業(yè)務(wù)。彈性業(yè)務(wù)(如Web、Email等)和非彈性業(yè)務(wù)(如VoIP、IPTV等)如圖1所示。

圖1 彈性、非彈性業(yè)務(wù)的邊際效用函數(shù)曲線

3 模型與求解

3.1 模型應(yīng)用場景

圖2為典型的具有資源控制實體功能的無線網(wǎng)絡(luò)示意圖，無線基站1有效區(qū)域中的用戶數(shù)量遠比無線基站2有效區(qū)域中的用戶多，更易產(chǎn)生擁塞。當(dāng)擁塞發(fā)生時，其重疊區(qū)域中的用戶終端1、終端2、終端3就可能選擇或切換到無線基站2，以獲得整體網(wǎng)絡(luò)效用最大。

圖2 具有資源控制實體功能的無線網(wǎng)絡(luò)示意圖

如圖2所示，多基站(網(wǎng)絡(luò))協(xié)作資源分配由資源控制實體負責(zé)實現(xiàn)，如果協(xié)作資源分配的基站集合過大，會導(dǎo)致較大延遲，考慮到用戶終端的基站選擇具有局部性，因此，可以采用局部資源控制實體實現(xiàn)基站集合內(nèi)的協(xié)作資源分配，文獻[11]中對上述問題進行了研究。

基于圖2描述的無線網(wǎng)絡(luò)場景，本文提出了一種兩階段基于效用的無線網(wǎng)絡(luò)資源分配方法，該方法不僅可以實現(xiàn)基站內(nèi)資源分配效用最大，同時也可以確保最大化全網(wǎng)效用。第一階段為基于擁塞度的基站選擇。此階段中的相關(guān)數(shù)由基站發(fā)送給資源控制實體，由其協(xié)助用戶終端選擇為其提供服務(wù)的基站。第二階段基于邊際效用的資源分配方法實現(xiàn)各基站內(nèi)的最優(yōu)化資源分配。

3.2 無線基站選擇

移動通信和集成電路等技術(shù)飛速發(fā)展，影響與改變了傳統(tǒng)無線網(wǎng)絡(luò)中的單一接入技術(shù)，多種網(wǎng)絡(luò)接入技術(shù)相互融合的異構(gòu)無線網(wǎng)絡(luò)逐漸出現(xiàn)并成為未來無線網(wǎng)絡(luò)的發(fā)展趨勢，同時無線移動終端能支持的服務(wù)類型也越來越豐富，譬如普通智能手機都支持多模功能和多種接入網(wǎng)絡(luò)選擇等。隨著異構(gòu)網(wǎng)絡(luò)的發(fā)展，實現(xiàn)無隙漫游目標(biāo)的提出令基站選擇問題變得更廣泛。目前較常用的方法是基于信號強度的方法，即選擇信號強度最好的基站作為服務(wù)基站。

信道質(zhì)量(Channel Quality, CQ)是無線信道通信質(zhì)量的重要指標(biāo)，無線信道質(zhì)量的值越大，表示信道質(zhì)量越好，反之亦然。無線信道質(zhì)量估算通常基于某些重要的無線網(wǎng)絡(luò)性能參數(shù)，如信噪比(Signal to Noise Ratio, SNR)、信干噪比(Signal-to-Interference plus Noise Ration, SINR)、信噪失真比(Signal-to-Noise plus Distortion Ratio, SNDR)等。除了與上述參數(shù)有關(guān)外，還與無線通信系統(tǒng)的傳輸(調(diào)制)方案有關(guān)。如使用CDMA(Code Division Multiple Access)方案的無線通信系統(tǒng)使用的估算方法與采用OFDM(Orthogonal Frequency Division Multiplexing)方案的估算方法不同，同時它也與接收器類型有關(guān)，其中還需要考慮各種對通信性能產(chǎn)生損害的因素，如多普勒頻移、信道估算誤差、干擾等。通常在所采用的傳輸方案和相關(guān)約束條件間進行綜合權(quán)衡確定估算參數(shù)。文獻[12]給出了一個基于SNR的無線信道強度估算方法。

3.3 基于效用的無線網(wǎng)絡(luò)資源分配模型

文獻[2]給出本文的分配模型：

其中，Ui為第i個基站的效用值；Ci為基站i的總資源數(shù)；n為基站數(shù)；Ri為第i個基站被分配的資源，通常為時域或頻域資源。

基站內(nèi)部的資源分配模型由下式描述：

3.4 彈性、非彈性業(yè)務(wù)的邊際效用與效用函數(shù)

3.4.1 彈性業(yè)務(wù)的邊際效用函數(shù)與效用函數(shù)

彈性業(yè)務(wù)的邊際效用與效用函數(shù)如下：

其中，r為無線網(wǎng)絡(luò)資源；q為信號強度；b為有效資源。通過λ可調(diào)整效用增長的快慢，通過μ可調(diào)整基本可用狀態(tài)(邊際效用最大)的資源量。

3.4.2 非彈性業(yè)務(wù)的邊際效用函數(shù)與效用函數(shù)

非彈性業(yè)務(wù)的邊際效用與效用函數(shù)如下：

其中，σ表示梯度；μ表示邊際效用最大時的資源。

關(guān)于上述效用函數(shù)的具體特征和相關(guān)參數(shù)的確定方法請參見文獻[2]。

3.5 模型求解

與模型定義相適應(yīng)，采用兩階段求解方法，式(1)模型求解方法的過程描述如下：

輸入T={tk|1≤k≤Nt，tk為第k個網(wǎng)絡(luò)流，Nt為網(wǎng)絡(luò)流數(shù)量}；BS={bsi|1≤i≤Nbs，bsi為第i個基站，其作用距離為di，Nbs為基站數(shù)量}

輸出S={rk| 1≤k≤Nt，rk為分配給tk的資源}

(1)確定每個無線網(wǎng)絡(luò)流tk的候選基站集合BSk，在BSk中選擇基站bsi將tk加入其流集合Ti。

(2)在每個基站bsi中，將資源分配給Ti中的每個流，T為基站i中流的集合。

3.5.1 基站選擇方法

定理 當(dāng)向某個基站增加一個網(wǎng)絡(luò)流時，式(2)模型的最優(yōu)總效用值不會降低。

證明：設(shè)在增加流tk之前，式(2)模型的最優(yōu)解為{ri|0＜i＜k-1}，此時的總效用值為Uk-1。增加流tk之后，顯然解{r1, r2, …,rk-1, 0}為式(2)的可行解，取該解時的總效用值仍為Uk-1，所以增加tk后的最優(yōu)模型總效用值Uk-1≤Uk。證畢。

隨著擁塞度的提高，式(2)模型總效用的增速通常會越來越低。因為隨著網(wǎng)絡(luò)流的增加，需要將其他流的資源調(diào)整給新增流，由于非彈性流調(diào)節(jié)能力有限(要么滿足其資源需求，要么不分配給它資源)，因此通常需通過調(diào)整彈性流的資源來實現(xiàn)；當(dāng)擁塞度增大時，每個彈性流的資源占用量呈下降趨勢，觀察圖1(a)，可以發(fā)現(xiàn)資源占用量越小，減少單位資源，效用下降就越大，其增速也就越低。這一點在下文的實驗結(jié)果中得到了驗證。基于以上分析，本文方法在為流選擇基站時總選擇擁塞度最低的基站，從而在流增加的同時保證總效用增長速度最快。

基站選擇方法的描述如下：

輸入BSk={bski|bski為tk的候選基站}

輸出bsk為選中的基站

(1)tk發(fā)送接入請求至BSk中每一個候選基站bski。

(2)對于BSk中每一個候選基站bski分別就tk的請求通知資源控制實體。

(3)資源控制實體分別計算候選基站bski的擁塞度cdki。

(4)資源控制實體指定cdki最小的bski作為bsk。

根據(jù)文中的定義，擁塞度可由如下式計算：cdi=，綜合考慮了信號強度、資源總量、資源需求量，比當(dāng)前使用基于信號強度的方法更為合理。擁塞度的值由基站通知用戶終端。

3.5.2 基站內(nèi)資源分配方法

本文中基站內(nèi)資源分配模型是對文獻[2]中基于邊際效用資源分配模型的改進，主要考慮了無線網(wǎng)絡(luò)的特點。

其中，u為U的邊際效用函數(shù)。由式(5)和式(6)可以推出式(2)中模型最優(yōu)解的必要條件。

必要條件 對于任意數(shù)i 和 j (i≠j, i, j∈[1, N])，式(2)中模型全局最優(yōu)解必需滿足如下約束：

根據(jù)上述必要條件給出模型求解方法：

(1)式(2)模型求解方法

(2)非彈性流解的選擇方法

式(2)模型求解方法中第2)步的主要問題是如何選擇非彈性邊際效用函數(shù)的有效資源，使總效用最大。為典型的組合優(yōu)化問題，文中通過貪婪算法進行求解。

3)存儲結(jié)果，結(jié)束。

第2)步中選取符合條件的最大vi′主要為了收斂速度快，并使資源和盡量接近最大可用資源量。

4 實驗結(jié)果與分析

為了驗證方法的求解效果和速度，設(shè)計了如下仿真實驗。

4.1 實驗設(shè)置

選擇4類網(wǎng)絡(luò)業(yè)務(wù)，分別是彈性業(yè)務(wù)VoIP、IPTV和非彈性業(yè)務(wù)TCP、HTTP業(yè)務(wù)。實驗中設(shè)置4個基站(BS1、BS2、BS3、BS4)，如圖3所示，作用距離為1.2，信道強度為[0,1]間的隨機數(shù)。實驗時，各流相繼在陰影區(qū)域出現(xiàn)，其橫縱坐標(biāo)為[0,2]間的隨機數(shù)。文獻[2]設(shè)置最大有效資源(實驗中為帶寬)為64 00 2、107、108和107，最小有效資源量為64 000、0、0和0，Ci為109。

圖3 實驗基站布局示意圖

4.2 參與對比的方法

基線方法：當(dāng)網(wǎng)絡(luò)流在目標(biāo)區(qū)域中出現(xiàn)時，嘗試將其分配到每個候選基站，使用本文方法在基站內(nèi)實現(xiàn)分配，然后選擇總效用最大的基站完成最終的分配。

方法1：本文方法。

方法2：將本文方法第1階段的基站選擇方法更換為傳統(tǒng)的基于信道質(zhì)量的無線基站選擇方法，其他與本文方法相同。

上述3種方法的主要不同體現(xiàn)在基站選擇上，這是實現(xiàn)全網(wǎng)效用最優(yōu)的關(guān)鍵?；€方法直接采用了純基于效用的方法，通過輪詢各個候選基站，實現(xiàn)效用最優(yōu)的基站選擇，理論上具有最優(yōu)的基站選擇結(jié)果；方法1采用了基于無線網(wǎng)絡(luò)擁塞度的方法，該方法是一種基于效用的啟發(fā)式基站選擇方法；方法2采用了基于信道質(zhì)量的方法，這是目前實際中常采用的基站選擇方法。通過對上述方法在基站選擇、求解總效用和求解用時上進行比較，驗證本文方法的有效性、高效性和實用性。

4.3 結(jié)果分析

4.3.1 基站分配方法分析

表1給出了實驗中不同業(yè)務(wù)的網(wǎng)絡(luò)流在不同擁塞度下，在各個基站中的分配情況。CD表示擁塞度，單元格中的數(shù)字串為實驗中方法將相應(yīng)業(yè)務(wù)的流分配到各基站的數(shù)量。其中，第1個數(shù)字為方法1的分配結(jié)果，第2個數(shù)字為方法2的分配結(jié)果，第3個數(shù)字為基線方法的分配結(jié)果。由表1的結(jié)果可見，從各基站相應(yīng)流的數(shù)量看，在全部

160組數(shù)據(jù)中，方法1與基線方法有88組相同，占55%。在不相同的數(shù)據(jù)中，除5個值兩者差距較大外(如擁塞度為10時，BS1中HTTP流的分配相差4個)，其他數(shù)據(jù)值的差距都在2個以內(nèi)；方法2與基線方法只有61組相同，占38%，共有19個值超過3，其中，擁塞度為9時BS1中HTTP流和擁塞度為10時BS2中TCP流分配數(shù)量差均達到5。從具體基站選擇情況看，在所有268次選擇中，方法1與基線方法有218次相同，占81.3%；而方法2與基線方法只有168次相同，占67.1%。上述結(jié)果表明，同基于信道質(zhì)量的基站選擇方法相比，本文提出的基站選擇方法的選擇結(jié)果與基線方法更接近，一定程度上驗證了本文基站選擇方法的合理性。

表1 基站選擇結(jié)果

4.3.2 求解效果及分析

各方法求解效果的對比實驗結(jié)果如圖4所示，在實驗中參與對比的3種方法中，基線方法和方法1獲得的總效用相差很小。在各擁塞度下，方法1僅比基線方法低0.28%，方法1在基站選擇結(jié)果上與基線方法有所不同，但因綜合考慮了資源總需求、資源總量、信道質(zhì)量等因素，依然獲得了理想的總效用。而方法2由于基站選擇結(jié)果與前2種方法差異加大，且在選擇時未充分考慮到整體效用最優(yōu)問題，因此總效用較差，比基線方法低7.1%，比方法1低7%。

圖4 求解效果

4.3.3 求解時間及分析

求解速度對資源分配方法至關(guān)重要，決定了所用方法的實用性，尤其是在無線網(wǎng)絡(luò)中，運行時間的好壞直接決定方法的可行與否。如果分配方法需幾分鐘才能完成，即便求解結(jié)果非常好，也不可能在實際中應(yīng)用。圖5在求解時間上對各方法作了對比。

圖5 求解時間

由圖5可見，基線方法由于每次選擇基站要分別計算各候選基站的效用，而其他方法則無需進行這種復(fù)雜計算。因此，基線方法的用時遠高于方法1和方法2，分別為方法1和方法2的12.36倍和12.76倍?；€方法平均耗時為0.926 s，方法1為0.066 s，而方法2只有0.064 s，由于網(wǎng)絡(luò)延遲會大大降低用戶體驗，因此對資源分配方法效率的要求較高，后2種方法資源分配時間均低于0.1 s，只要不是頻繁發(fā)生網(wǎng)絡(luò)切換，不會對用戶應(yīng)用造成影響，基本達到了實際應(yīng)用的要求。

5 結(jié)束語

本文針對無線網(wǎng)絡(luò)中的資源分配問題，提出了一種基于效用的兩階段多基站協(xié)作無線資源分配方法。該方法將資源分配過程分為2個階段，首先根據(jù)擁塞度選擇基站，然后在基站內(nèi)部利用基于邊際效用的方法實現(xiàn)高效的資源分配。實驗結(jié)果表明，本文方法具有良好的求解效果和較高的求解速度。今后將針對其他新型網(wǎng)路，如云計算網(wǎng)絡(luò)、數(shù)據(jù)中心網(wǎng)絡(luò)等，研究針對性的基于效用的資源分配方法。

參考文獻

[1] 宋亞楠, 仲 茜, 胡成臣, 等. 基于效用函數(shù)簇的效用類服務(wù)分層調(diào)度模型[J]. 電子學(xué)報, 2012, 40(2): 247-253.

[2] 宋亞楠, 仲 茜, 劉 斌, 等. 基于邊際效用函數(shù)的網(wǎng)路資源調(diào)度[J]. 電子學(xué)報, 2013, 41(4): 632-638.

[3] 董春玲, 朱曉麗, 鄭明春. 分層組播中MAX-MIN公平速率分配算法的運用[J]. 計算機應(yīng)用, 2005, 25(3): 533-535.

[4] 賀 媛, 劉 佳, 曾烈光. 寬帶無線接入網(wǎng)的成比例帶寬分配[J]. 清華大學(xué)學(xué)報, 2008, 48(7): 1131-1134.

[5] Shenker S. Fundamental Design Issues for the Future Internet[J]. IEEE Journal on Selected Areas in Communications, 1995, 13(9): 1176-1188.

[6] 趙 晗. 現(xiàn)代無線通信技術(shù)的發(fā)展現(xiàn)狀及未來發(fā)展趨勢[J].企業(yè)技術(shù)開發(fā), 2011, 30(16): 86, 89.

[7] Song Guocong, Li Ye. Utility-based Resource Allocation and Scheduling in OFDM-based Wireless Broadband Networks[J]. IEEE Communications, 2005, 43(12): 127-134.

[8] Kuo W H, Liao W. Utility-based Resource Allocation in Wireless Networks[J]. IEEE Transactions on Wireless Communications, 2007, 6(10): 3600-3606.

[9] Chen Li, Wang Bin, Chen Xiaohang. U tility-based Resource Allocation for Mixed Traffic in Wireless Networks[C]//Proc. of International Workshop o n Fu ture Media Networks an d IP-based TV. Shanghai, China: [s. n.], 2011: 91-96.

[10] 王 華, 李魯群, 王 力. LTE-A中基于準(zhǔn)入控制的切換決策算法[J]. 計算機工程, 2011, 37(5): 88-90.

[11] 陳 力. B 3G/4G系統(tǒng)中的無線資源分配的研究[D]. 北京:北京郵電大學(xué), 2012.

[12] David R P, Norman C B. A Comparison of SN R Estimation Techniques for the AWGN Channel[J]. IEEE Transacations on Communications, 2000, 48(10): 1681-1691.

編輯 任吉慧

Multi-base-station Cooperation Wireless Resource Allocation Method

SONG Ya-nan1,2, ZHONG Qian2, QU Guang-liang2, LI Xing-li2
(1. Department of Compute Science and Technology, Tsinghua University, Beijing 100084, China; 2. 72241 Unit, Jinan 250029, China)

Most utility based wireless resource allocation methods only focus on the optimal allocation within a base station. Because of ignoring the issue of base station selection, these methods can not achieve the o ptimal utility of wh ole network. Therefore, this paper proposes a utility based multi-base-station cooperati on wireless resource allocation method, which is divided into two stages. In the first stage, base stations are selected according to their congestion degree. And in the second stage, the resource in each base station is allocated according to marginal utility. The simulation experiments show that, between the a pproach and the baseline method, of all the 268 base station selections there are 218 accounting for 81.3% having the same selection result and the average elapse time of the proposed method is only 0.066 s, which is much lower than the baseline method 0.926 s. These facts show the rationality of the base station selection method as well as the efficiency and effectiveness of the resource allocation method.

utility; utility function; marginal utility; wireless network; resource allocation; multi-base-station cooperation

10.3969/j.issn.1000-3428.2014.05.011

國家自然科學(xué)基金資助項目(61202489)。

宋亞楠(1977－)，女，講師、博士研究生，主研方向：無線資源分配，下一代互聯(lián)網(wǎng)絡(luò)；仲 茜，講師、博士；曲光亮，講師、碩士；李興立，工程師。

2013-02-20

2013-04-25E-mail：songyn77@gmail.com

1000-3428(2014)05-0049-05

A

TP393.03

·移動互聯(lián)與通信技術(shù)·