軟件定義無線網(wǎng)絡(luò)的負(fù)載均衡算法

陳 鑄，嚴(yán)朝陽，吳廣富，王 林

(1.中國(guó)電子科技集團(tuán)公司第十研究所 成都 628007. 2.重慶郵電大學(xué) 移動(dòng)通信技術(shù)重點(diǎn)實(shí)驗(yàn)室 重慶 400065)

0 引 言

近年來，移動(dòng)智能終端的數(shù)量與日俱增。根據(jù)中國(guó)互聯(lián)網(wǎng)絡(luò)信息中心第40次中國(guó)互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告，截至2018年12月，中國(guó)手機(jī)網(wǎng)民規(guī)模達(dá)到8.17億，占總網(wǎng)民的98.5%；而在2013年12月，中國(guó)手機(jī)網(wǎng)民的人數(shù)有5億，僅占總網(wǎng)民的80.9%。無線局域網(wǎng)(wireless local area networks，WLAN)因?yàn)槠鋬r(jià)格便宜、高帶寬等優(yōu)點(diǎn)，是移動(dòng)用戶主要無線連接方式。為了適應(yīng)移動(dòng)用戶業(yè)務(wù)的快速增長(zhǎng)，越來越多的無線接入點(diǎn)被建立并廣泛應(yīng)用到家庭、餐廳、超市、機(jī)場(chǎng)等場(chǎng)景。據(jù)不完全統(tǒng)計(jì)，2014年全球約有4 700萬無線接入點(diǎn)，但是在2018年已經(jīng)增加了8倍。

當(dāng)前的802.11設(shè)備的無線接入點(diǎn)(access point，AP)選擇決策是基于接收信號(hào)強(qiáng)度指示(received signal strength indication，RSSI)進(jìn)行實(shí)施的，終端僅選擇關(guān)聯(lián)信號(hào)強(qiáng)度最大的AP[1]。在一些特殊的場(chǎng)景(如會(huì)議室、體育館等)，大量的無線終端試圖在短時(shí)間內(nèi)連接一個(gè)信號(hào)質(zhì)量好的AP，從而導(dǎo)致部分AP超負(fù)載工作，產(chǎn)生低吞吐率和負(fù)載不均等問題，嚴(yán)重影響用戶上網(wǎng)體驗(yàn)；而有些接入點(diǎn)則處于閑置或輕載狀態(tài)，浪費(fèi)了大量無線資源。在當(dāng)前的無線網(wǎng)絡(luò)架構(gòu)下，實(shí)施負(fù)載均衡策略仍存在一些困難。首先，傳統(tǒng)架構(gòu)下的管理機(jī)制缺乏靈活性，很難在已部署的AP上添加新的用戶關(guān)聯(lián)控制機(jī)制；其次，給所有AP配置轉(zhuǎn)發(fā)規(guī)則和避免沖突規(guī)則等方面需要大量投資；最后，由于AP間缺乏協(xié)同，造成鄰近AP信號(hào)之間相互干擾。因此，需要具有集中控制能力的網(wǎng)絡(luò)架構(gòu)，使網(wǎng)絡(luò)變得更具彈性和擴(kuò)展性。

軟件定義網(wǎng)絡(luò)(software defined network，SDN)作為一種新型的網(wǎng)絡(luò)架構(gòu)[2-3]，允許網(wǎng)絡(luò)管理員通過抽象較低級(jí)別的功能管理網(wǎng)絡(luò)，將網(wǎng)絡(luò)中的控制層和數(shù)據(jù)層分開實(shí)現(xiàn)定制編程。在SDN架構(gòu)中，OpenFlow是集中控制器和網(wǎng)絡(luò)轉(zhuǎn)發(fā)設(shè)備的標(biāo)準(zhǔn)通信接口，可以實(shí)現(xiàn)SDN的可編程，允許控制器控制交換機(jī)的行為[4-5]。OpenFlow可以屏蔽不同廠家交換機(jī)的差異，為選擇基礎(chǔ)設(shè)施(交換機(jī)，AP等)提供更多便利。因此，SDN網(wǎng)絡(luò)管理員可以在控制器上編程，將設(shè)計(jì)好的負(fù)載均衡策略應(yīng)用到網(wǎng)絡(luò)中。

當(dāng)前，研究人員已經(jīng)提出了一些無線網(wǎng)絡(luò)負(fù)載均衡問題的解決方案。文獻(xiàn)[6]考慮了RSSI和無線終端數(shù)量，提出一種最小負(fù)載優(yōu)先(least load first，LLF)策略，用戶終端選擇關(guān)聯(lián)終端數(shù)最小的AP。在全球移動(dòng)通信系統(tǒng)(global system for mobile communications，GSM)網(wǎng)絡(luò)環(huán)境中，因?yàn)槊看握Z音呼叫產(chǎn)生相同的語音流量，選擇終端數(shù)量作為負(fù)載度量標(biāo)準(zhǔn)是合適的。但在WLAN環(huán)境中，由于每個(gè)用戶終端產(chǎn)生的流量具有較大的差異，以蜂窩環(huán)境下的終端數(shù)量去衡量WLAN環(huán)境的負(fù)載量顯然是不合理的。最強(qiáng)信號(hào)強(qiáng)度優(yōu)先(strongest signal first，SSF)方法是802.11的AP關(guān)聯(lián)機(jī)制[7]，該方法被廣泛用在負(fù)載切換策略上[8-9]。802.11k修正案也嘗試著解決負(fù)載均衡問題[10]，需要對(duì)AP和無線客戶端進(jìn)行修改，會(huì)造成額外的硬件開銷。文獻(xiàn)[11]提出了一種控制用戶AP關(guān)聯(lián)的最小帶寬公平分配的解決方案，雖然可以減少負(fù)載不平衡，但是會(huì)造成帶寬分配的不公平。

針對(duì)無線局域網(wǎng)中負(fù)載不均問題，本文提出一種基于軟件定義無線網(wǎng)絡(luò)(software defined wireless network, SDWN)的負(fù)載均衡策略。該策略采用AP帶寬使用占比作為負(fù)載指標(biāo)，利用SDWN控制器，周期性地檢查當(dāng)前網(wǎng)絡(luò)中各AP的負(fù)載狀態(tài)。利用負(fù)載平衡因子判斷當(dāng)前網(wǎng)絡(luò)負(fù)載情況，如果檢測(cè)到網(wǎng)絡(luò)負(fù)載不均，綜合考慮當(dāng)前終端的占用帶寬、AP負(fù)載和終端到AP的RSSI等影響，引導(dǎo)部分終端重關(guān)聯(lián)至輕載AP以平衡網(wǎng)絡(luò)負(fù)載，從而提高用戶服務(wù)質(zhì)量。

1 系統(tǒng)架構(gòu)

不失一般性，假設(shè)當(dāng)前網(wǎng)絡(luò)覆蓋如圖1，各AP覆蓋區(qū)域均有重疊，OpenFlow能使所有AP通過有線基礎(chǔ)設(shè)施與控制器相連。SDWN架構(gòu)如圖2，控制器作為軟件定義網(wǎng)絡(luò)的操作實(shí)體，通過南向接口獲取物理層的資源；并通過北向接口與應(yīng)用層交互以實(shí)現(xiàn)網(wǎng)絡(luò)邏輯?？刂破鲹碛挟?dāng)前無線網(wǎng)絡(luò)的全局視圖，實(shí)時(shí)掌握網(wǎng)絡(luò)拓?fù)渲械馁Y源分布情況。通過控制器，在應(yīng)用層部署負(fù)載均衡策略，使網(wǎng)絡(luò)資源分配更加合理。

SDWN控制器周期性地采集各AP的資源狀態(tài)信息，并評(píng)估當(dāng)前網(wǎng)絡(luò)狀態(tài)的業(yè)務(wù)負(fù)載是否均衡。把AP分為3種狀態(tài)，即輕載AP、均衡AP和超載AP[12]。輕載AP可以接受從鄰近AP卸載過來或者新加入網(wǎng)絡(luò)的終端；超載AP不再接受其他終端的接入，可以把關(guān)聯(lián)該AP的部分終端卸載至輕載AP，以降低該AP的負(fù)載級(jí)別；均衡AP只接受新加入網(wǎng)絡(luò)的終端，不接受從超載AP切換而來的終端。

圖1 AP重覆蓋的SDWN系統(tǒng)Fig.1 SDWN system with overlapping APs

圖2 SDWN架構(gòu)Fig.2 Architecture of SDWN

2 負(fù)載均衡算法

2.1 負(fù)載度量標(biāo)準(zhǔn)

在負(fù)載均衡系統(tǒng)中，負(fù)載度量標(biāo)準(zhǔn)是關(guān)鍵要素之一。本文以各AP使用的帶寬占總?cè)萘康谋嚷首鳛楹饬控?fù)載是否均衡標(biāo)準(zhǔn)。

(1)

負(fù)載平衡因子β越小，說明當(dāng)前系統(tǒng)各AP間的使用帶寬資源比率越接近，系統(tǒng)的負(fù)載狀態(tài)越均衡；反之，則說明此時(shí)系統(tǒng)的負(fù)載狀態(tài)不均衡。因此，可以通過仿真或?qū)崪y(cè)數(shù)據(jù)設(shè)置閾值ζ，當(dāng)β<ζ時(shí)，說明當(dāng)前時(shí)刻系統(tǒng)處于負(fù)載均衡狀態(tài)。理想狀態(tài)下，即當(dāng)β=0時(shí)，系統(tǒng)處于完美負(fù)載均衡狀態(tài)。

為了確定當(dāng)前各AP的負(fù)載狀態(tài)，需要把各AP負(fù)載同系統(tǒng)平均負(fù)載作比較，即負(fù)載狀態(tài)判決門限因子φ定義為系統(tǒng)平均負(fù)載，即

(2)

如果APi的負(fù)載小于φ(即Rused_i<φ)，則該APi為輕載AP；如果APi的負(fù)載位于(φ，φ+Δφ)之間(即φφ+Δφ)，則該APi為超載AP。為了平衡網(wǎng)絡(luò)負(fù)載，超載AP需要把與之關(guān)聯(lián)的部分終端卸載至輕載AP。其中，Δφ為預(yù)先設(shè)定的調(diào)整值，一般根據(jù)仿真或?qū)崪y(cè)值確定。圖3是接入點(diǎn)狀態(tài)示意圖，位于灰色區(qū)域的AP2是均衡AP，AP1和AP3分別是輕載AP和超載AP，AP3應(yīng)該把部分負(fù)載移交給AP1以平衡網(wǎng)絡(luò)負(fù)載。

圖3 接入點(diǎn)狀態(tài)示意圖Fig.3 Status of APs

2.2 切換對(duì)象的選擇

在SDWN中，利用位于應(yīng)用層的負(fù)載均衡算法，周期性檢測(cè)當(dāng)前網(wǎng)絡(luò)負(fù)載是否失衡。當(dāng)網(wǎng)絡(luò)處于負(fù)載失衡時(shí)，把超載AP下的部分用戶終端卸載至輕載AP。如果隨機(jī)選擇部分終端進(jìn)行卸載，會(huì)產(chǎn)生大量低效的卸載決策。本文利用負(fù)載平衡因子精確查找候選終端，以盡可能地減少卸載終端數(shù)量。

如果選擇第m個(gè)超載接入點(diǎn)中的第j個(gè)用戶終端UEmj作為候選終端，則UEmj的吞吐率最接近于U值，U=(Rused_m-Rused_avg)×Vtotal_m。其中，Rused_m表示第m個(gè)超載接入點(diǎn)的帶寬使用率，Vtotal_m表示第m個(gè)超載接入點(diǎn)的總帶寬，m=1,2,3,…，j=1,2,3,…。

為候選終端選擇合適的切換AP。需要判斷輕載AP是否具備接收候選終端的條件。

RSSIreceive_k>RSSIneed_min

(3)

Vremain_k_min>Vneed

(4)

(3)—(4)式中：RSSIreceive_k表示候選終端接收到第k個(gè)輕載接入點(diǎn)的信號(hào)強(qiáng)度；RSSIneed_min表示候選終端進(jìn)行卸載所需的最小信號(hào)強(qiáng)度；Vremain_k_min為第k個(gè)輕載接入點(diǎn)所剩帶寬的最小值；Vneed表示候選終端進(jìn)行卸載所需的帶寬。(3)式是為了滿足終端切換所要達(dá)到的信號(hào)強(qiáng)度切換門限；(4)式保證候選終端尋找的AP剩余容量需求。

綜合考慮候選終端來自輕載AP接收的信號(hào)強(qiáng)度和輕載AP的剩余容量，定義加權(quán)值K作為評(píng)判標(biāo)準(zhǔn)。選擇K值最大的AP作為候選終端的切換對(duì)象。

Kk=αXRSSIreceive_k+(1-α)XVremain_k,

XRSSIreceive_k∈(0,1),

(5)

XVremain_k∈(0,1)

(6)

(7)

(5)—(7)式中：Kk為第k個(gè)輕載接入點(diǎn)的K值；α表示接收信號(hào)強(qiáng)度的加權(quán)系數(shù)；XRSSIreceive_k和XVremain_k分別為RSSIreceive_k和Vremain_k進(jìn)行歸一化處理后的參數(shù)；RSSIreceive_k_max為終端接收到第k個(gè)輕載接入點(diǎn)的最大信號(hào)強(qiáng)度；Vremain_k表示第k個(gè)輕載接入點(diǎn)所剩的帶寬；Vtotal_k為第k個(gè)輕載接入點(diǎn)的總帶寬，k=1,2,3,…。

2.3 負(fù)載均衡算法過程

應(yīng)用場(chǎng)景如圖1，控制器需要周期性地檢查當(dāng)前網(wǎng)絡(luò)中的負(fù)載狀況，應(yīng)用所提負(fù)載均衡策略，以便在負(fù)載失衡時(shí)對(duì)部分候選終端進(jìn)行重關(guān)聯(lián)以平衡網(wǎng)絡(luò)負(fù)載。所提負(fù)載均衡算法過程如下。

步驟1SDWN控制器周期性地檢查網(wǎng)絡(luò)中各AP的負(fù)載信息，包括AP的容量信息，AP周期性記錄用戶終端RSSI、用戶關(guān)聯(lián)狀態(tài)和各用戶所需帶寬。

步驟2通過SDWN控制器獲得的網(wǎng)絡(luò)各AP的負(fù)載信息，計(jì)算β值和φ值。若β<ζ，轉(zhuǎn)到步驟1；否則，執(zhí)行步驟3。

步驟3根據(jù)φ值確定網(wǎng)絡(luò)中各AP輕載、均衡或超載狀態(tài)，找出超載AP，并執(zhí)行步驟 4。

步驟4找出超載APi下的候選終端UEj，判斷是否有滿足關(guān)聯(lián)該候選終端接收信號(hào)強(qiáng)度(即(3)式)且容量能滿足候選終端所需帶寬(即(4)式)的AP。如果沒有，則選擇另一個(gè)候選終端；反之，執(zhí)行步驟5。

步驟5通過(5)式找K值最大的AP作為步驟4中候選終端的切換對(duì)象，系統(tǒng)候選終端與AP重關(guān)聯(lián)后，如果β<ζ，轉(zhuǎn)到步驟1；否則，轉(zhuǎn)到步驟4。

3仿真分析

為了驗(yàn)證本文所提算法有效性，在Mininet平臺(tái)上進(jìn)行仿真實(shí)驗(yàn)。在Mininet環(huán)境中部署2臺(tái)AP和4臺(tái)終端，通過Python腳本對(duì)AP進(jìn)行擴(kuò)展，為AP添加信號(hào)強(qiáng)度、可用帶寬和覆蓋范圍3個(gè)屬性。每臺(tái)AP的覆蓋半徑是20 m，每臺(tái)AP的最大吞吐率為80 Mbit/s，信號(hào)強(qiáng)度和傳輸速率隨終端和AP直接距離增大而減小。

為均衡系統(tǒng)負(fù)載設(shè)置一個(gè)固定的閾值ζ，當(dāng)系統(tǒng)負(fù)載高于這個(gè)閾值(β>ζ)時(shí)，負(fù)載均衡算法將被觸發(fā)。通過大量仿真可知，ζ可以設(shè)置為0.025；均衡AP和超載AP的分界線Δφ可以設(shè)置為10%，即負(fù)載超過系統(tǒng)平均負(fù)載10%以上的AP為超載AP，負(fù)載超過系統(tǒng)平均負(fù)載不足10%的AP為均衡AP。

當(dāng)前仿真實(shí)驗(yàn)的場(chǎng)景，2個(gè)AP被部署在覆蓋范圍重疊的區(qū)域。最初，只有1個(gè)客戶端與AP1關(guān)聯(lián)，剩下的3個(gè)終端都關(guān)聯(lián)AP2。仿真持續(xù)時(shí)間是300 s，而且每10 s采集1個(gè)平均值，前100 s系統(tǒng)為預(yù)熱時(shí)間，即在前100 s即使負(fù)載失衡時(shí)也不采取負(fù)載均衡算法，100 s后開始執(zhí)行控制器中的負(fù)載均衡算法。

圖4以帶寬的使用占比作為衡量AP負(fù)載的指標(biāo)，該值越大說明當(dāng)前擴(kuò)展服務(wù)集中AP的業(yè)務(wù)負(fù)載越大。在負(fù)載均衡策略觸發(fā)之前的100 s內(nèi)，AP2的負(fù)載大約是AP1的2倍。在剩下的200 s里，由于實(shí)施了負(fù)載均衡策略，與AP2關(guān)聯(lián)的部分終端逐漸重關(guān)聯(lián)到AP1，使AP1和AP2的負(fù)載趨于相等。

圖4 AP的負(fù)載狀況Fig.4 Status of AP load

圖5為系統(tǒng)負(fù)載平衡因子β的變化曲線，前100 s網(wǎng)絡(luò)負(fù)載處于嚴(yán)重失衡狀態(tài)，故β值很大；但在負(fù)載均衡機(jī)制協(xié)調(diào)下，β值持續(xù)減小并在低于門限ζ后趨于穩(wěn)定。

圖5 負(fù)載平衡因子βFig.5 Load balancing factor β under each AP coverage

圖6顯示的是與AP1和AP2關(guān)聯(lián)終端的平均吞吐率。在開始階段，AP1的終端平均吞吐率為33 Mbit/s左右，而AP2的終端平均吞吐率只有12 Mbit/s左右。在100 s的時(shí)候，隨著負(fù)載均衡策略的實(shí)施，終端與AP的關(guān)聯(lián)狀態(tài)發(fā)生了新的變化并趨于穩(wěn)定，與AP2關(guān)聯(lián)的終端平均吞吐率提高了10 Mbit/s左右；與AP1關(guān)聯(lián)的終端的平均吞吐率下降到20 Mbit/s左右，但整個(gè)系統(tǒng)吞吐率有較大提升。

圖6 各AP下終端的平均吞吐率Fig.6 Average throughput rate of terminals

圖7是本文策略與SSF和LLF在終端平均吞吐率方面的比較。在前100 s內(nèi)，由于沒有起動(dòng)負(fù)載均衡策略，因此，3種算法的平均吞吐率完全相同；LLF算法只考慮固定系統(tǒng)流量下的信號(hào)強(qiáng)度，而SSF算法考慮了信號(hào)強(qiáng)度和系統(tǒng)流量，本文綜合考慮了終端占用帶寬、當(dāng)前接入點(diǎn)負(fù)載和當(dāng)前終端接收信號(hào)強(qiáng)度指示信息，因此，可以獲得終端在平均吞吐量方面性能提升。從圖7可以看出，SSF算法比LLF算法在終端平均吞吐量方面提升了7.3%左右；而本文策略又比SSF提升了8.3%左右。

圖7 終端平均吞吐率Fig.7 System average throughput comparison

4 總 結(jié)

為了平衡軟件定義無線網(wǎng)絡(luò)系統(tǒng)負(fù)載，合理利用帶寬資源和提高用戶服務(wù)質(zhì)量，本文提出了一種負(fù)載均衡算法。該算法綜合考慮AP的帶寬余量和信號(hào)強(qiáng)度作為候選終端選擇切換對(duì)象AP依據(jù)。在負(fù)載失衡的網(wǎng)絡(luò)環(huán)境下，使網(wǎng)絡(luò)可以再次快速達(dá)到均衡狀態(tài)。仿真實(shí)驗(yàn)結(jié)果表明，該算法在平衡網(wǎng)絡(luò)負(fù)載、平均系統(tǒng)吞吐率方面都有較好性能。