申 超, 孫丹丹, 張洪欣(北京郵電大學 電子工程學院, 北京 100876)

?

基于AP選擇及自適應切換的負載均衡算法

申 超, 孫丹丹, 張洪欣
(北京郵電大學 電子工程學院, 北京 100876)

針對無線局域網(wǎng)中無線接入點容易過載的問題, 提出一種基于無線接入點的選擇及自適應切換的負載均衡算法。通過RSSI(

Signal Strength Indication)值, MAC(Media Access Control)幀發(fā)送時延選擇接入點, 同時對無線站點的突發(fā)流量做出積極應對措施, 用最小限度接入點的切換達到均衡整個網(wǎng)絡負載的目的。該算法能明確選擇信道空閑的無線接入點, 均衡接入點負載, 降低數(shù)據(jù)包的發(fā)送時延。與傳統(tǒng)方法相比, 該算法使系統(tǒng)的總吞吐量提高13.6%。

無線局域網(wǎng)； 負載均衡； 接入點選擇

0 引 言

當前, 基于IEEE802.11無線局域網(wǎng)(WLAN： Wireless Local Area Network)技術的快速發(fā)展, 通過無線接入互聯(lián)網(wǎng)的方式受到越來越多人的青睞。在學校、 公司以及公共場所都有WLAN的存在, 并呈現(xiàn)出迅猛增長的狀態(tài)。WLAN作為有線局域網(wǎng)的延伸帶給用戶更多的便利, 但隨著無線局域網(wǎng)中無線站點(STA： Station)的增多, 其移動性及數(shù)據(jù)流量的波動性導致整個網(wǎng)絡的負載發(fā)生較大變化, 無線接入點(AP： Access Point)所使用的信道出現(xiàn)分配不均的情況[1], 繼而造成了整個網(wǎng)絡信道資源的浪費。

基于以上情況, 筆者提出了一種負載均衡算法。該算法分兩個層次： 首先, STA選擇RSSI(Received Signal Strength Indication)值大于某閾值的AP作為可關聯(lián)AP, 再從可關聯(lián)AP中選擇發(fā)送數(shù)據(jù)包的平均時延最小的AP接入[2]； 其次, 通過監(jiān)控WLAN中AP的負載信息, 當任意一個AP負載超過閾值時觸發(fā)全局負載均衡, 使STA切換到低負載AP上; 最后, 通過NS2仿真, 從負載均衡前后AP吞吐量的變化驗證了上述算法的可行性。

1 問題分析及算法設計

1.1 問題分析

圖1 IEEE 802.11 WLAN體系結構Fig.1 The IEEE 802.11 WLAN Architecture

802.11體系結構的基本構件模塊是基本服務集(BSS: Basic Service Set), 一個BSS通常包含一個或多個無線站點和一個AP。在基礎設施WLAN中(見圖1), 每個AP會覆蓋較廣的范圍(圖1中灰色部分), AP與AP之間必然存在相當大的重疊。以往的AP接入方式是STA根據(jù)掃描到的AP信息, 選擇信號強度最強的未加密或已認證的AP接入(SSS: Strongest Signal Strength)[3]。在圖1所示的情況下, 以上述方式接入網(wǎng)絡會使大部分STA接入到AP2上, 而AP1、 AP3則只有少數(shù)STA接入。AP2過載導致BSS2的網(wǎng)絡長時間處于阻塞狀態(tài), 延時增加, 數(shù)據(jù)包遺失率變大, 網(wǎng)絡服務質(zhì)量(QoS: Quality of Service)變差, 而BSS1及BSS3卻處于低速率狀態(tài), 因此, 整個WLAN的信道有效利用率偏低。

另外, 現(xiàn)實生活中網(wǎng)絡流量波動較大, 與AP關聯(lián)的STA的實時網(wǎng)絡流量可能因用戶需求的改變而出現(xiàn)較大的改變。所以, 不僅要從AP接入的角度上考慮負載均衡, 還需從網(wǎng)絡的實時流量變化及全局的角度考慮無線局域網(wǎng)的負載均衡。

1.2 數(shù)學描述

1.2.1 AP的接入選擇

AP與STA的距離d、 RSSI(VRSSI)值及單位距離上能量的絕對值A之間的關系可表示為

從式(1)可得到, AP與STA的距離越遠, STA所接收的RSSI值就越低, 相應的信道的傳輸質(zhì)量就會越差。較佳的VRSSI值在0～-50 dbm之間。為獲得較好的傳輸速率及服務質(zhì)量, STA接入AP的VRSSI值應大于-70 dbm。因此, 默認設定可關聯(lián)的信號強度閾值為-70 dbm。

在802.11 DCF(Distributed Coordination Function)模型中, STA成功發(fā)送一個MAC幀的時間Tt為

其中TDIFS為分布式幀的時間間隔,TSIFS為短幀間的時間間隔,FRTS為請求發(fā)送RTS控制幀的大小,FCTS為允許發(fā)送CTS控制幀的大小,FDATA為MAC數(shù)據(jù)幀的大小,FACK為確認幀的大小,R為信道傳輸速率, 信道繁忙產(chǎn)生的n次平均回退時間[4]

其中Wmin和Wmax分別表示退避窗口的最小值和最大值,Tslot為時隙時間。

導致數(shù)據(jù)包遺失的原因主要有兩個： 擁塞遺失和無線遺失?；?02.11 DCF模型及GE(Gilbert-Elliott)數(shù)據(jù)包遺失模型[5], 假設每個數(shù)據(jù)包的最大傳送次數(shù)為N次, MAC幀的擁塞遺失概率為Pj, MAC層的傳送遺失概率為Pm, 則接收端應用層所感受到的傳輸遺失概率

因此, STA成功發(fā)送一個MAC 數(shù)據(jù)幀的實際期望時間為

此時, AP的吞吐量為

由于STA與AP的關聯(lián)是在RSSI值較高的AP中進行選擇, 數(shù)據(jù)在MAC層的傳輸才有保障。為簡化分析過程, 這里假設AP的無線遺失概率為一個較小的定值。當AP變擁塞時, 擁塞概率Pj變大, 成功發(fā)送幀的時間Tt就會變長, 系統(tǒng)吞吐量變小。

由上述分析可知, AP的接入選擇包含以下兩方面：

1) 從掃描到的AP中選擇大于RSSI閾值的AP；

2) 對選擇的AP進行輪詢測試, 選擇成功發(fā)送MAC幀平均時間最小的AP相關聯(lián)。

1.2.2 AP的切換

為更好地掌握WLAN中的網(wǎng)絡變化, 實時統(tǒng)計所有AP的負載信息及STA的信息, 在圖1所示的網(wǎng)絡體系結構中加入無線控制器(AC: Access Controller)。通過對有限的無線資源進行分配和管理, 在保證網(wǎng)絡用戶和業(yè)務QoS的前提下, 最大限度地提升無線射頻資源的利用率和整個WLAN網(wǎng)絡的系統(tǒng)容量[6], 從而更好地實現(xiàn)全局負載均衡。筆者把一定時間段內(nèi)STA的MAC幀發(fā)送時延均值作為STA的負載, 把該時間段內(nèi)AP 的MAC幀發(fā)送時延均值作為AP的負載[7]。下文均用“負載”代表上述含義, 不再贅述。

根據(jù)AP的性能為每個AP設置一個負載閾值, 通過AC實時監(jiān)控AP的負載情況, 當任意一個AP負載超過閾值時, 觸發(fā)AP切換, 使STA由信道競爭激烈的AP切換到信道相對空閑的AP, 實現(xiàn)全局負載均衡。其數(shù)學描述如下:

1) 存在一個AP的集合A={A1,A2,…,Am};

2) 存在一個STA集合D={D1,D2,…,Dn};

3)Dj的平均網(wǎng)絡負載為Tj;

4) 有一個m×n的矩陣S={sij}, 其中sij表示Ai到Dj的信號強度, 如果Dj無法接收到Ai的信號, 則該sij的值為0;

5) 根據(jù)信號強度矩陣S和信號強度閥值h, 將大于h且不等于0的sij的值賦值為1, 其他值賦值為0, 可以得到關聯(lián)約束矩陣C={cij};

6) 每個STA都必須與一個AP建立關聯(lián);

7) 每個AP的負載Li等于與之建立關聯(lián)的所有STA負載的平均值。

經(jīng)過上述定義, 可將整個問題描述為: 根據(jù)關聯(lián)約束矩陣C, 在D中的每個元素找到一個A中元素的映射Ass:D→A, 使Lmax最小[8]

在WLAN網(wǎng)絡中, 由于AP切換產(chǎn)生網(wǎng)絡時延, 使QoS變差, 甚至會影響用戶的使用感受。因此, 應該盡量最小限度地進行AP切換。但是, 要達到式(7)的均衡效果, 必然導致該網(wǎng)絡環(huán)境下大范圍的AP切換。如果在STA接入AP時采用如前所述的AP選擇方法, 則導致某個AP過載的主要原因可能是與該AP相關聯(lián)的某個或多個STA發(fā)送的數(shù)據(jù)流量出現(xiàn)了大幅度的增長。在這種情況下, 只需對個別的AP進行切換即可達到減緩AP過載帶來的負面效果。所以, 結合AP選擇方法, 可將問題描述為, 在盡量最小限度進行AP切換的前提下使式(7)成立。

1.3 算法描述

1.3.1 AP的接入選擇

當新的STA加入該WLAN環(huán)境時, 執(zhí)行以下操作。

1) 打開無線接入開關后, 通過主動掃描2.4～2.485 GHz上的各個信道, 向掃描得到的各個AP廣播探測請求幀, 通過AP的探測響應幀獲得AP的BSSID(Basic Service Set Identifier)、 SSID(Service Set Identifier)、 RSSI等信息[9]。同時, 把AC中的相應信息更新。

2) 通過掃描得到的AP的RSSI值跟RSSI閾值相比較, 選出高于RSSI閾值的AP作為候選AP。

3) STA依次向候選AP發(fā)送多次探測請求幀, 將探測請求幀與返回的探測響應幀時間差的均值作為發(fā)送MAC幀的時延估計[10]。

4) 從上述結果中選擇成功發(fā)送MAC幀平均時間最小的AP, STA向它發(fā)送關聯(lián)請求幀, 請求接入AP。如果收到關聯(lián)響應幀, 則STA與該AP建立關聯(lián), 并定時向AC發(fā)送RSSI值sij、 平均負載Tj和關聯(lián)AP的標簽Ai等信息; 如果沒有收到關聯(lián)響應幀, 則等待一段時間, 再從3)開始重新執(zhí)行。

1.3.2 AP的切換

AP中某個Ax的負載超過負載閾值時, 觸發(fā)負載均衡算法。

1) 根據(jù)AC中的信息得到STA與AP的已關聯(lián)矩陣O={oij}, 如果Ai與Dj相關聯(lián), 則oij的值為1; 否則, 為0。

4) 由公式U=C-O得到均衡約束矩陣。

5) 將均衡約束矩陣U的第x行的uij的值設置為0, 記為U′, 即從均衡約束矩陣中去除對過載AP的考慮。

6) 根據(jù)U′得到可切換的STA列表LSTA及每個STA對應的目的AP列表LAP, 將LSTA中的STA按其負載Tj由大到小排列, 將LAP中的AP按其負載Vi由小到大排列。

7) 計算LSTA中負載最大的STA與對應的LAP中負載最小的AP相關聯(lián)后該AP的負載, 如果該負載未超過負載閾值, 則使其發(fā)生切換, 從LSTA中刪除該STA并更新Vi; 反之, 從LSTA中刪除該STA, 并嘗試切換下一個STA。

8) 重復6)、 7), 直到負載均衡。

2 實驗仿真及分析

圖2 仿真網(wǎng)絡拓撲結構Fig.2 The simulation network topology

為驗證該負載均衡方法的正確性和有效性, 利用NS2仿真工具進行驗證。利用NS2中提供的CMU無線模型[11], 以圖2所示的網(wǎng)絡拓撲進行仿真。此模擬情景成員包含一個有線節(jié)點(N0)、 3個AP(AP0,AP1,AP2), 以及10個STA(S0,S1,…,S9)。該仿真場景的覆蓋面積是500×500 m, 實驗中AP的覆蓋范圍彼此間存在重疊區(qū)域[12]。其中AP1所覆蓋的范圍內(nèi)所包含的STA最多, 但在重疊區(qū)域存在多個STA。仿真時間為120 s, 實驗期間安排每個STA與有線節(jié)點N0進行數(shù)據(jù)交換, 通過調(diào)整STA數(shù)據(jù)包生成時間間隔, 使AP1、AP2、AP3的節(jié)點負載各不相同。圖2中所示的路由器節(jié)點又具有AC的功能, 它能實時獲取該無線局域網(wǎng)的實時狀況[13], 并實現(xiàn)AP切換算法。

在NS2中實現(xiàn)筆者提出的負載均衡算法, 并在上述網(wǎng)絡模型下, 與SSS算法及筆者提出的負載均衡算法進行仿真, 相應筆者得到記錄所有通信過程的Trace文件, 通過awk及gnuplot工具處理相應文件, 其結果如圖3～圖5所示。

圖3 SSS算法分配下各AP的吞吐量Fig.3 AP throughput withSSS algorithm

圖4 筆者算法分配下各AP的吞吐量Fig.4 AP throughput with thealgorithm in this paper

圖5 兩種算法分配下總吞吐量的比較Fig.5 Total throughput of thetwo algorithms

從圖3中可以看出, 在SSS算法分配下各AP之間的吞吐量差別較大。其中AP1的吞吐量最低, 這是由于網(wǎng)絡中的大部分STA與AP1相關聯(lián)所導致的。圖4為在筆者算法分配下各AP的吞吐量, 該算法使3個AP的吞吐量集中維持在了300 kbit/s的水平上。這表明該算法與SSS算法相比, 它有效地改善了整個系統(tǒng)的負載狀態(tài), 使整個系統(tǒng)中各個AP的負載趨于均衡狀態(tài)。圖5為在兩種算法分配下系統(tǒng)總吞吐量的比較, 從圖5可看出, 在SSS算法支配下系統(tǒng)總吞吐量為2 200 kbit/s, 在筆者算法支配下, 系統(tǒng)總吞吐量為2 500 kbit/s, 使系統(tǒng)吞吐量提升了13.6%。

3 結 語

筆者提出了基于AP選擇及自適應切換的無線局域網(wǎng)負載均衡算法。 該算法采用STA的AP選擇接入策略及AC主控的AP切換策略。相對于以往使用的SSS接入方式, 該算法先從接入上選擇信道相對空閑的AP, 然后又對整個網(wǎng)絡的信道利用率進行調(diào)優(yōu), 從整體上實現(xiàn)了無線局域網(wǎng)的負載均衡。

[1]劉志宏. 802.11 無線局域網(wǎng)接入式負載均衡技術研究 [D]. 長沙： 國防科學技術大學計算機學院, 2011. LIU Zhihong. A Study of Association Control Load Balancing in 802.11 Wireless Lans [D]. Changsha: School of Computer, National University of Defense Technology, 2011.

[2]邢光璞. 無線局域網(wǎng)負載均衡優(yōu)化研究 [D]. 合肥： 中國科學技術大學計算機科學與技術學院, 2009. XING Guangpu. Research on Load Balancing Optimization of Wireless LAN [D]. Hefei: School of Computer Science and Technology, University of Science and Technology of China, 2009.

[3]NICHOLSON A J, CHAWATHE Y, CHEN M Y, et al. Improved Access Point Selection [C]∥Proceedings of the 4th International Conference on Mobile Systems, Applications and Services. ACM, Uppsala, Sweden: MobiSys, 2006: 233-245.

[4]JUDD G, STEENKISTE P. Fixing 802.11 Access Point Selection [J]. ACM SIGCOMM Computer Communication Review, 2002, 32(3): 31-31.

[5]柯志亨, 程榮祥, 鄧德雋. NS2仿真實驗----多媒體和無線網(wǎng)絡通信 [M]. 北京： 電子工業(yè)出版社, 2009. KE Zhiheng, CHENG Rongxiang, DENG Dejuan. NS2 Simulation: Multimedia and Wireless Network Communications [M]. Beijing: Publishing House of Electronics Industry, 2009.

[6]楊敏. 集中式WLAN無線資源管理與信道分配算法的研究 [D]. 廣州： 華南理工大學電子與信息學院, 2012. YANG Min. Research on Radio Resource Management and Channel Allocation Algorithm in Centralized WLAN [D]. Guangzhou: School of Electronic and Information Engineering, South China University of Technology, 2012.

[7]王勝靈, 崔勇, 徐恪, 等. WLAN中基于小區(qū)呼吸的多約束負載均衡 [J]. 計算機學報, 2009, 32(10)： 1947-1956. WANG Shengling, CUI Yong, XU Ke, et al. Multi-Constraint Load Balancing Based on Cell Breathing in WLAN [J]. Chinese Journal of Computers, 2009, 32(10): 1947-1956.

[8]楊鑫. 無線局域網(wǎng)負載均衡的研究 [D]. 上海： 上海交通大學電子信息與電氣工程學院, 2005. YANG Xin. Study on Load Balancing of Wireless LAN [D]. Shanghai: School of Electronic Information and Electrical Engineering, Shanghai Jiaotong University, 2005.

[9]KUROSE J F, ROSS K W. 計算機網(wǎng)絡自頂向下方法 [M]. 北京： 機械工業(yè)出版社, 2008. KUROSE J F, ROSS K W. Computer Networking: A Top-Down Approach [M]. Beijing: China Machine Press, 2008.

[10]CASSELL B A, ALPEROVICH T, WELLMAN M P, et al. Access Point Selection under Emerging Wireless Technologies [C]∥Sixth Workshop on the Economics of Networks, Systems, and Computation. San Jose: CA, 2011: 125-131.

[11]趙傳信, 王汝傳, 黃海平, 等. 無線Ad hoc分層攻擊仿真模型 [J]. 計算機工程與應用, 2010, 46(24): 81-84. ZHAO Chuanxin, WANG Ruchuan, HUANG Haiping, et al. Wireless Ad hoc Layered Attack Simulation Mode [J]. Computer Engineering and Applications, 2010, 46(24): 81-84.

[12]KOZISEK S E, COPPAGE C M, MORRILL R J. System and Method for Selecting an Access Point: US, Patent 7,940,735 [P]. 2011-05-10.

[13]胡鳴明. 基于中心控制的集中式WLAN的負載均衡技術研究 [D]. 廣州： 華南理工大學電子與信息學院, 2012. HU Mingming. The Research of the Load Balancing Technology Based on A Center-Controlled Centralized Wireless LAN Architecture [D]. Guangzhou: School of Electronic and Information Engineering, South China University of Technology, 2012.

(責任編輯： 何桂華)

Load-Balancing Algorithm Based on Access Point Selection and Adaptive Handoff in WLAN

SHEN Chao, SUN Dandan, ZHANG Hongxin
(School of Electronic Engineering, Beijing University of Posts and Telecommunications, Beijing 100876, China)

To resolve the problem of access point overload in WLAN (Wireless Local Area Network), a load-balancing algorithm based on the access point selection and adaptive handoff is presented. In the algorithm, RSSI (Received Signal Strength Indication), MAC (Media Access Control) frame transmission delay and other factors are taken into consideration to select the access point. Meanwhile, it makes a positive response to the station of gusty traffic with minimal access point handoff to balance the entire network load. The algorithm can explicitly select the access point of the idle channel, and balance the load of access points. Then it effectively improves system throughput and reduces transmission delay of the packet. Compared with the traditional algorithms, it improves system throughput by 13.6%.

wireless local area network (WLAN); load balance; access point selection

1671-5896(2014)05-0498-06

2014-04-14

國家自然科學基金資助項目(61202399)； 中央高校基本科研業(yè)務費專項資金資助項目(2012RC0310)

申超(1990— ), 男, 山東萊蕪人, 北京郵電大學碩士研究生, 主要從事無線網(wǎng)絡優(yōu)化及生物醫(yī)學信息的獲取、 傳輸與處理技術研究, (Tel)86-13051649294(E-mail)shenchao.bupt@gmail.com；

孫丹丹(1978— ), 女, 北京人, 北京郵電大學講師, 主要從事Ad Hoc網(wǎng)絡協(xié)作通信研究, (Tel)86-10-62282134(E-mail)sdd661@bupt.edu.cn。

TP393.17

： A