基于AP选择及自适应切换的负载均衡算法

申 超, 孙丹丹, 张洪欣(北京邮电大学 电子工程学院, 北京 100876)



基于AP选择及自适应切换的负载均衡算法

申 超, 孙丹丹, 张洪欣
(北京邮电大学 电子工程学院, 北京 100876)

针对无线局域网中无线接入点容易过载的问题, 提出一种基于无线接入点的选择及自适应切换的负载均衡算法。通过RSSI(

Signal Strength Indication)值, MAC(Media Access Control)帧发送时延选择接入点, 同时对无线站点的突发流量做出积极应对措施, 用最小限度接入点的切换达到均衡整个网络负载的目的。该算法能明确选择信道空闲的无线接入点, 均衡接入点负载, 降低数据包的发送时延。与传统方法相比, 该算法使系统的总吞吐量提高13.6%。

无线局域网； 负载均衡； 接入点选择

0 引 言

当前, 基于IEEE802.11无线局域网(WLAN： Wireless Local Area Network)技术的快速发展, 通过无线接入互联网的方式受到越来越多人的青睐。在学校、 公司以及公共场所都有WLAN的存在, 并呈现出迅猛增长的状态。WLAN作为有线局域网的延伸带给用户更多的便利, 但随着无线局域网中无线站点(STA： Station)的增多, 其移动性及数据流量的波动性导致整个网络的负载发生较大变化, 无线接入点(AP： Access Point)所使用的信道出现分配不均的情况[1], 继而造成了整个网络信道资源的浪费。

基于以上情况, 笔者提出了一种负载均衡算法。该算法分两个层次： 首先, STA选择RSSI(Received Signal Strength Indication)值大于某阈值的AP作为可关联AP, 再从可关联AP中选择发送数据包的平均时延最小的AP接入[2]； 其次, 通过监控WLAN中AP的负载信息, 当任意一个AP负载超过阈值时触发全局负载均衡, 使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根据扫描到的AP信息, 选择信号强度最强的未加密或已认证的AP接入(SSS: Strongest Signal Strength)[3]。在图1所示的情况下, 以上述方式接入网络会使大部分STA接入到AP2上, 而AP1、 AP3则只有少数STA接入。AP2过载导致BSS2的网络长时间处于阻塞状态, 延时增加, 数据包遗失率变大, 网络服务质量(QoS: Quality of Service)变差, 而BSS1及BSS3却处于低速率状态, 因此, 整个WLAN的信道有效利用率偏低。

另外, 现实生活中网络流量波动较大, 与AP关联的STA的实时网络流量可能因用户需求的改变而出现较大的改变。所以, 不仅要从AP接入的角度上考虑负载均衡, 还需从网络的实时流量变化及全局的角度考虑无线局域网的负载均衡。

1.2 数学描述

1.2.1 AP的接入选择

AP与STA的距离d、 RSSI(VRSSI)值及单位距离上能量的绝对值A之间的关系可表示为

从式(1)可得到, AP与STA的距离越远, STA所接收的RSSI值就越低, 相应的信道的传输质量就会越差。较佳的VRSSI值在0～-50 dbm之间。为获得较好的传输速率及服务质量, STA接入AP的VRSSI值应大于-70 dbm。因此, 默认设定可关联的信号强度阈值为-70 dbm。

在802.11 DCF(Distributed Coordination Function)模型中, STA成功发送一个MAC帧的时间Tt为

其中TDIFS为分布式帧的时间间隔,TSIFS为短帧间的时间间隔,FRTS为请求发送RTS控制帧的大小,FCTS为允许发送CTS控制帧的大小,FDATA为MAC数据帧的大小,FACK为确认帧的大小,R为信道传输速率, 信道繁忙产生的n次平均回退时间[4]

其中Wmin和Wmax分别表示退避窗口的最小值和最大值,Tslot为时隙时间。

导致数据包遗失的原因主要有两个： 拥塞遗失和无线遗失。基于802.11 DCF模型及GE(Gilbert-Elliott)数据包遗失模型[5], 假设每个数据包的最大传送次数为N次, MAC帧的拥塞遗失概率为Pj, MAC层的传送遗失概率为Pm, 则接收端应用层所感受到的传输遗失概率

因此, STA成功发送一个MAC 数据帧的实际期望时间为

此时, AP的吞吐量为

由于STA与AP的关联是在RSSI值较高的AP中进行选择, 数据在MAC层的传输才有保障。为简化分析过程, 这里假设AP的无线遗失概率为一个较小的定值。当AP变拥塞时, 拥塞概率Pj变大, 成功发送帧的时间Tt就会变长, 系统吞吐量变小。

由上述分析可知, AP的接入选择包含以下两方面：

1) 从扫描到的AP中选择大于RSSI阈值的AP；

2) 对选择的AP进行轮询测试, 选择成功发送MAC帧平均时间最小的AP相关联。

1.2.2 AP的切换

为更好地掌握WLAN中的网络变化, 实时统计所有AP的负载信息及STA的信息, 在图1所示的网络体系结构中加入无线控制器(AC: Access Controller)。通过对有限的无线资源进行分配和管理, 在保证网络用户和业务QoS的前提下, 最大限度地提升无线射频资源的利用率和整个WLAN网络的系统容量[6], 从而更好地实现全局负载均衡。笔者把一定时间段内STA的MAC帧发送时延均值作为STA的负载, 把该时间段内AP 的MAC帧发送时延均值作为AP的负载[7]。下文均用“负载”代表上述含义, 不再赘述。

根据AP的性能为每个AP设置一个负载阈值, 通过AC实时监控AP的负载情况, 当任意一个AP负载超过阈值时, 触发AP切换, 使STA由信道竞争激烈的AP切换到信道相对空闲的AP, 实现全局负载均衡。其数学描述如下:

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

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

3)Dj的平均网络负载为Tj;

4) 有一个m×n的矩阵S={sij}, 其中sij表示Ai到Dj的信号强度, 如果Dj无法接收到Ai的信号, 则该sij的值为0;

5) 根据信号强度矩阵S和信号强度阀值h, 将大于h且不等于0的sij的值赋值为1, 其他值赋值为0, 可以得到关联约束矩阵C={cij};

6) 每个STA都必须与一个AP建立关联;

7) 每个AP的负载Li等于与之建立关联的所有STA负载的平均值。

经过上述定义, 可将整个问题描述为: 根据关联约束矩阵C, 在D中的每个元素找到一个A中元素的映射Ass:D→A, 使Lmax最小[8]

在WLAN网络中, 由于AP切换产生网络时延, 使QoS变差, 甚至会影响用户的使用感受。因此, 应该尽量最小限度地进行AP切换。但是, 要达到式(7)的均衡效果, 必然导致该网络环境下大范围的AP切换。如果在STA接入AP时采用如前所述的AP选择方法, 则导致某个AP过载的主要原因可能是与该AP相关联的某个或多个STA发送的数据流量出现了大幅度的增长。在这种情况下, 只需对个别的AP进行切换即可达到减缓AP过载带来的负面效果。所以, 结合AP选择方法, 可将问题描述为, 在尽量最小限度进行AP切换的前提下使式(7)成立。

1.3 算法描述

1.3.1 AP的接入选择

当新的STA加入该WLAN环境时, 执行以下操作。

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发送多次探测请求帧, 将探测请求帧与返回的探测响应帧时间差的均值作为发送MAC帧的时延估计[10]。

4) 从上述结果中选择成功发送MAC帧平均时间最小的AP, STA向它发送关联请求帧, 请求接入AP。如果收到关联响应帧, 则STA与该AP建立关联, 并定时向AC发送RSSI值sij、 平均负载Tj和关联AP的标签Ai等信息; 如果没有收到关联响应帧, 则等待一段时间, 再从3)开始重新执行。

1.3.2 AP的切换

AP中某个Ax的负载超过负载阈值时, 触发负载均衡算法。

1) 根据AC中的信息得到STA与AP的已关联矩阵O={oij}, 如果Ai与Dj相关联, 则oij的值为1; 否则, 为0。

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

5) 将均衡约束矩阵U的第x行的uij的值设置为0, 记为U′, 即从均衡约束矩阵中去除对过载AP的考虑。

6) 根据U′得到可切换的STA列表LSTA及每个STA对应的目的AP列表LAP, 将LSTA中的STA按其负载Tj由大到小排列, 将LAP中的AP按其负载Vi由小到大排列。

7) 计算LSTA中负载最大的STA与对应的LAP中负载最小的AP相关联后该AP的负载, 如果该负载未超过负载阈值, 则使其发生切换, 从LSTA中删除该STA并更新Vi; 反之, 从LSTA中删除该STA, 并尝试切换下一个STA。

8) 重复6)、 7), 直到负载均衡。

2 实验仿真及分析

图2 仿真网络拓扑结构Fig.2 The simulation network topology

为验证该负载均衡方法的正确性和有效性, 利用NS2仿真工具进行验证。利用NS2中提供的CMU无线模型[11], 以图2所示的网络拓扑进行仿真。此模拟情景成员包含一个有线节点(N0)、 3个AP(AP0,AP1,AP2), 以及10个STA(S0,S1,…,S9)。该仿真场景的覆盖面积是500×500 m, 实验中AP的覆盖范围彼此间存在重叠区域[12]。其中AP1所覆盖的范围内所包含的STA最多, 但在重叠区域存在多个STA。仿真时间为120 s, 实验期间安排每个STA与有线节点N0进行数据交换, 通过调整STA数据包生成时间间隔, 使AP1、AP2、AP3的节点负载各不相同。图2中所示的路由器节点又具有AC的功能, 它能实时获取该无线局域网的实时状况[13], 并实现AP切换算法。

在NS2中实现笔者提出的负载均衡算法, 并在上述网络模型下, 与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的吞吐量最低, 这是由于网络中的大部分STA与AP1相关联所导致的。图4为在笔者算法分配下各AP的吞吐量, 该算法使3个AP的吞吐量集中维持在了300 kbit/s的水平上。这表明该算法与SSS算法相比, 它有效地改善了整个系统的负载状态, 使整个系统中各个AP的负载趋于均衡状态。图5为在两种算法分配下系统总吞吐量的比较, 从图5可看出, 在SSS算法支配下系统总吞吐量为2 200 kbit/s, 在笔者算法支配下, 系统总吞吐量为2 500 kbit/s, 使系统吞吐量提升了13.6%。

3 结 语

笔者提出了基于AP选择及自适应切换的无线局域网负载均衡算法。 该算法采用STA的AP选择接入策略及AC主控的AP切换策略。相对于以往使用的SSS接入方式, 该算法先从接入上选择信道相对空闲的AP, 然后又对整个网络的信道利用率进行调优, 从整体上实现了无线局域网的负载均衡。

[1]刘志宏. 802.11 无线局域网接入式负载均衡技术研究 [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]邢光璞. 无线局域网负载均衡优化研究 [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仿真实验----多媒体和无线网络通信 [M]. 北京： 电子工业出版社, 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中基于小区呼吸的多约束负载均衡 [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]杨鑫. 无线局域网负载均衡的研究 [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. 计算机网络自顶向下方法 [M]. 北京： 机械工业出版社, 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)； 中央高校基本科研业务费专项资金资助项目(2012RC0310)

申超(1990— ), 男, 山东莱芜人, 北京邮电大学硕士研究生, 主要从事无线网络优化及生物医学信息的获取、 传输与处理技术研究, (Tel)86-13051649294(E-mail)shenchao.bupt@gmail.com；

孙丹丹(1978— ), 女, 北京人, 北京邮电大学讲师, 主要从事Ad Hoc网络协作通信研究, (Tel)86-10-62282134(E-mail)sdd661@bupt.edu.cn。

TP393.17

： A