（计算机软件与理论专业论文）无线局域网负载均衡优化研究.pdf

摘要 摘要 近年柬基于i e e e 8 0 2 1 1 标准h 3 1 系列的无线局域网( w i r e l e s sl o c a la r e a n e t w o r k w l a n ) 技术发展速度迅猛，但在实际应用中也遇到了很多难题，其中 之一则是l b 于无线局域网的站点( s t a t i o n ，s t a ) 特殊的移动性和数据的波动性，经 常导致各个无线接入点( a c c e s sp o i n t ，a p ) 上的负载出现较大差异，如何有效的平 衡各接入点之i 日j 的差异，最大化网络资源的利用，是一个亟待解决的问题，负载 均衡技术就是为解决这一问题而孕育而生的。 目前负载均衡的难点集中在负载信息的判定和收集上。在无线局域网中，除 了业务量以外，业务的q o s ( q u a l i t yo f s e r v i c e ) 需求也是一个很重要的方面。故有 效的评价a p 的负载水平对负载分配是尤其重要的。而在信息收集方面，也应该 本着简单易用的原则，以免引起过多的丌销。之前的研究工作大多在判断的粒度 较为粗糙或在信息收集方面比较复杂，造成在实际应用中，分配负载不合理或算 法开销较大。因此，非常有必要继续研究和探索这一领域的新理论和新方法。 本论文有特色的工作体现在如下几个方面：1 ) 总结以往负载均衡算法所存 在的弊端和不足。提出了一种新的接入式负载均衡算法，算法在s t a 接入时， 能够有效的根据以平均探测时间为权衡标准，合理的选取最优质的a p 进行接入， 改正了以往负载均衡算法所存在的弊端和不足，并根据分析对算法做了进一步的 改进，使其较适应动态变化的网络环境。2 ) 对影响无线局域网性能的因素做了分 析，并提出了相应的优化措施，对无线局域网的负载均衡效果起到推动作用。3 ) 针对s t a 的可移动性和数据量波动性，文中还提出了一种切换式的负载均衡方 法，在网络拓扑结构基本形成之后，根据当前信道忙碌率等信息对a p 的负载进 行的再次调整和分配，使得各a p 之间的负载基本均衡。为了验证算法的正确性 和有效性，本文采用仿真工具加以实验，结果表明文中的两种方法均正确有效， 且在复杂多变的网络环境下更加优于之前的研究工作。 关键词：无线局域网负载均衡平均探测时间信道忙碌率 第1 贝 a b s t r a c t a b s t r a c t i nr e c e n t l yy e a r s ，i e e e 8 0 2 11s t a n d a r ds e r i e so fw l a nt e c h n o l o g yi sg r o w i n g r a p i d l y , a n ds o m ed i f f i c u l tp r o b l e m w a sa l s oe m e r g e d o n eo ft h e mw a st h em o b i l i t y a n dd a t af l u c t u a t i o no fw i r e l e s st e r m i n a lc a u s e dt h el o a do fa pu n b a l a n c e d s ot h e l o a db a l a n c et e c h n i q u ew e r ec o m eu pt or e d u c et h ed i f f e r e n c eo ft h ea p sl o a da n d o p t i m i z et h ep e r f o r m a n c eo f w i r e l e s sn e t w o r k s ， t h ed i f f i c u l t l yo ft h el o a db a l a n c et e c h n i q u ea r et h ej u d g m e n ta n dc o l l e c t i o no f t h el o a di n f o r m a t i o n i n 亿a n b e s i d e st h ev o l u m eo fd a t a , t h en e e do ft h eq o si s a l s oav i t a la s p e c t ，s oj u d g et h el o a do fa pe f f e c t i v e l yi sv i t a lt ot h el o a dd i s t r i b u t i o n n e v e r t h e l e s s ，t h ec o l l e c t i o no fl o a di n f o r m a t i o ni sa l s ob a s e dt os i m p l e n e s sa n d f a c i l i t yi no r d e rt oa v o i dt h eo v e r f u l ls p e n d i n g b u tt h ef o r m e rr e s e a r c hw o r k se i t h e r t o or o u g h n e s st oju d g et h ea p sl o a do rc o l l e c ti n f o r m a t i o nt o oc o m p l e x s o ，i t sv e r y n e c e s s a r yt oc o n t i n u et h er e s e a r c hi nt h ef i e l d t h ec o n t r i b u t i o no ft h i sa r t i c l ei st h r e e - f o l d f i r s t l y , t h ea r t i c l ep r o p o s e dan e w w l a na c c e s sl o a db a l a n c ea l g o r i t h m w h e ns t aa c c e s s i n gt h ew l a n ，i tc a nb a s e o nt h ej u d g eb yt h ea v e r a g ep r o b et i m et oc h o o s et h eb e s ta pt oa c c e s s s e c o n d l y , w e a n a l y s i st h ea f f e c to ft h et h r o u g h p u t o fw l a n ，a n dp r o p o s e dt h ec o r r e s p o n d i n g o p t i m i z a t i o ns c h e m e t h i r d l y , a i m e da tt h em o b i l i t ya n dd a t af l u c t u a t i o no ft h es t a ， t h i sa r t i c l ea l s op r o p o s e dan e wh a n d o f fl o a db a l a n c i n ga l g o r i t h m ，w h e nt h et o p o l o g y h a sa l r e a d yf o r m e d ，t h ea l g o r i t h mc a nr e d i s t r i b u t et h ea p sl o a db yt h ec h a n n e lb u s y r a t i oa n do t h e ri n f o r m a t i o n t h ee x p e r i m e n tp r o v e dt h a t ，t w ok i n d so ft h ea l g o r i t h m a r ee f f e c t i v ea n dc o r r e c t a n de x c e lt ot h ef o r m e rw o r k sw h e nt h en e t w o r ki s c h a n g e f u la n dc o m p l e x k e yw o r d s ：w i r e l e s sl a n ，l o a db a l a n c i n g ，a v e r a g ep r o b et i m e ，c h a n n e lb u s yr a t i o 第l j 页 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的 成果。除己特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或 撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作 了明确的说明。 作者签名 签字日期：乏鳓至堡 | j 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学 拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构 送交论文的复e 件和电子版，允许论文被查阅和借阅，可以将学位论文编入有 关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。本人提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 田公丌口保密( 年) 作者签名逦隧一翮虢掣纽狴 、| 签字日期：签字日期： 6 f 第1 章绪论 第1 章绪论 本章首先对本论文选题的原因和背景进行了总结和归纳。之后，介绍了全文 的研究目的和研究方案。然后对本论文的主要贡献进行介绍。最后是本论文的结 构安排。 1 1背景 随着网络技术的不断发展，网络对人们的生活、学习、工作等方面的影响与 也随之不断增长。局域网络的不断普及，已经成为了人们生活中不可或缺的一部 分，现如今网络已经渗入到了商业，金融，政府，医疗，科研，教育等各个社会 部门。而随着便携式计算机、p d a ( p e r s o n a ld a t aa s s i s t a n t ) 等智能移动终端的逐 渐发展和成熟，人们对随时随地接入网络访问和获取各种信息的要求也愈演愈 烈，由于传统的有线局域网络受到布线等因素的影响，大大限制了移动性和自由 性，不能满足人们当前需求，因此无线局域网络也就因此孕育而生。 无线局域网是计算机网络与无线通信技术相结合的产物。其设计初衷是作为 有线局域网的延伸。无线局域网利用电磁波在空气中发送和接受数据，而无需线 缆介质，却能够提供与有线局域网相同的功能。它是在有线局域网的基础上通过 无线集线器、无线网桥、无线网卡等设备使无线通信得以实现。 与有线网络相比，无线网络存在如下优点【4 j ：1 ) 灵活性。有线网络设备的安 放要受到布线格局的限制。而在无线网络中，只要在信号接受的范围内，无线设 备可以自由的移动，不受地理位置的限制，随时随地都可上网。2 ) 易组建性。在 有线网络中，网络布线成本高，且安装工序比较繁琐，需要安装人员掌握一定的 技术。相比而言，无线网络的无需布线，组建容易方便，只需进行简单的设置即 可，而且要构建一个地理位置上存在障碍的l a n 网络，使用无线网络也更加轻 松简单。3 ) 易扩展性。有线网络的扩展性较差，如果要增加新用户，而原有布线 所预留的端口又不够用的话，就要进行重新布置线缆等工作，耗费大量的时间和 工作量，而无线网络的一台a p 可以支持多个用户同时接入，如果需要新增加用 户，网络不需作任何更改，只要在计算机上安装一张无线网卡即可。 虽然无线局域网技术出现较晚，但却有不短的历史。1 8 9 7 年意大利科学家 m a r c o n i 首次使用无线电波进行信息传输并获得成功，为以后无线网络的构建提 供了可能。上世纪7 0 年代，夏威夷大学的n o r m a n a b r a m s o n 及其同事开创了第 一个基于分组技术的无线电通信网络，该网络被称作a l o h a 网络，这个地面无 第1 章绪论 线电广播系统把该校位于瓦胡。( o a h ui s l a n d ) 上的主机与分布在其他岛上和海洋 船舶上的终端连接了起来，因此被看作是无线局域网络的前身和起源。 到了上世纪8 0 年代末期，随着个人计算机的诞生和发展，真正现代意义上 的无线局域网的随之出现，无线局域网标准化进程也就开始了。1 9 9 7 年5 月，i e e e 制订了第一个无线局域网标准一i e e e8 0 2 1 1 协议，而随之在1 9 9 9 年8 月，i e e e 就推出了新的高速标准8 0 2 1 1 b 和8 0 2 1 1 a 进入高速发展阶段，i e e e 8 0 2 1 1 b 在 2 4 g h z 频段提供最高1 1 m b p s 的速率，i e e e8 0 2 1 l a 则在5 8 g h z 频段提供 5 4 m b p s 的数据传输速率。2 0 0 1 年1 1 月，i e e e 试验性地批准8 0 2 1 1 一引，用以兼 容8 0 2 11 b 和8 0 2 1l a 。与此同时，欧洲电信标准化协会( e t s i ) 的宽带无线电接入 网络( b r a n ) d , 组也着手制订h i p e r t 刨( h i 曲p e r f o r m a n c er a d i o ) 接入标准，并很快 推出h i p e r l a n l 和h i p e r l a n 2 。随着i e e e 8 0 2 11 和h i p e r l a n 家族在技术上的 突破及w l a n 产品成本的大幅下降，使得无线局域网在宽带无线接入中大显身 手。截至目前，采用8 0 2 1 1 和h i p e r l a n 标准的无线局域网已经覆盖了北美和欧 洲越来越多的地区。全球w l a n 市场总销售额达到近2 2 亿美元，每年平均增幅 高达2 0 左右，同时，w l a n 应用范围不断拓展，不仅扩展了有线l a n ，甚至 在某些情况下还能取而代之。 现如今随着无线站点的增多，且流动性和数据量的波动较强，网络负载会发 生变化【7 l 。主要表现在：1 ) 在无线局域网中，当多个无线终端关联同一个无线 接入点，并尝试传输数据时，数据包会经常发生碰撞，无线站点必须等待一段时 间之后再次尝试传输数据，这将会影响整个w l a n 系统的吞吐量数据传输性能。 2 ) 由于无线电波随距离增大而损耗的影响，距离a p 的远近，直接影响到数据终 端的连接速率。在无线覆盖范围内，距离a p 较近的站点，信号强度较强，终端 传输速率也较快。而距离a p 较远的终端，信号强度则较为薄弱，传输速率也就 较慢。这就造成无线终端处在不同位置时，连接速率不一致，影响网络应用。 可见如果不进行网络优化，整个系统的性能和容量将会受到很大的影响，无 线局域网对于网络优化技术的需求逐渐显露。但依靠传统硬件升级的方法并不适 合用于无线局域网中。首先需要优化的a p 个数可能很多，故优化的工作量相对 较大。其次成本高，做硬件升级而去舍弃现有设备，将导致高额资金的投入，而 且硬件升级的结果有可能不能完全满足当前的需求。再次灵活性较差，当一个无 线局域网优化完毕后，很有可能过了一段时间，网络拓扑结构发生了变化，如此 一来前面的优化就没有意义了。 于是，如何在尽量不改变当前网络结构的基础上，提高系统的吞吐量和传输 性能，加强网络数据处理的能力，提高网络的可用性和灵活性，也就成了当今研 究的一大课题。负载均衡【9 】技术就是针对这一课题而孕育而生的无线局域网优化 2 第1 章绪论 技术。无线局域网的负载均衡技术能有效的解决网络拥塞问题，能就近提供网络 服务，实现地理位置无关性，为用户选择更好的访问质量，通过平衡各接入点的 负载，使得每个接入点的资源被充分利用，从而提高整个网络资源的利用率，而 且无需添加任何硬件设备。由此可见，研究负载均衡技术，对提高无线局域网的 网络性能，优化网络结构，节省优化开支有着深远的影响。 本文首先对无线局域网的基本原理、协议标准和组网方式等方面进行概括和 介绍，并对现有的负载均衡思想、方法及优缺点进行了研究，并针对当前高密度 的无线局域网提出了一种接入式负载均衡算法和一种切换式的负载均衡优化算 法，对本文提出的算法进行仿真并详细分析数据和结果。 1 2 论文章节安排 后文的组织如下：第二章简要介绍了无线局域网的协议标准及无线局域网中 的优化等相关工作。第三章提出了一种无线局域网接入式负载均衡算法，以s t a 的通信性能为自，j 提，合理的选择优质的a p 接入。第四章继续根据影响无线局域 网的性能因素，针对s t a 的位置的可移动性和数据量的波动性，提出了一种切 换式负载均衡算法，能有效的分流超载a p 的负载到正常a p 下，从而使得各a p 之间负载基本均衡。第五章是对负载均衡的优化算法进行模拟仿真，并对仿真的 结果进行分析和研究。最后对全文进行总结，并提出了将来的工作。 第2 章背景知识和相关：l 作 第2 章背景知识和相关工作 2 1无线局域网技术标准 2 1 1i e e e8 0 2 1 1 系列协议 i e e e 8 0 2 1 l 是i e e e 于1 9 9 7 年6 月发布的第一代无线局域网标准，是其他 i e e e 8 0 2 11 系列标准的基础。i e e e 8 0 2 1 1 标准工作在2 4 g h z 开放频段，提供 1 m b i t s 和2 m b i t s 的数据传输速率，并且提供异步的和有时间上限的数据传输服 务，并提供多播( 包括广播) 、网络管理和鉴权等服务。 8 0 2 1 1 标准定义了物理层和介质访问子层控制协议的规范，且在物理层和介 质访问予层已经能够完成所有无线局域网的功能，使其无需在对其他协议层再进 行相应的修改，故对上层完全透明。任何l a n 应用、网络操作系统或协议在遵 守i e e e 8 0 2 1 1 标准的无线l a n 上运行时，就如同运行在以太网上一样方便容易。 1 ) i e e e8 0 2 1 1 b i e e e 8 0 2 1 l b 也被称为w i f i 技术，是由i e e e 于1 9 9 9 年9 月批准， i e e e 8 0 2 1 i b 对i e e e s 0 2 1 1 标准进行修改和补充，以支持更高数据传输速率，其 中最重要的改进就是在i e e e 8 0 2 1 1 的基础上增加两种更高的通信速率5 5 m b i t s 和1 1 m b i t s ，因此移动用户可以得到以太网级的网络性能、速率和可用性。当工 作站距离过长或者干扰太大时，传输速率能够从1 1 m b i t s 自动降到5 5 m b i t s ， 或者根据直接扩频技术调整到2 m b i t s 和1 m b i t s i e e e 8 0 2 1 l b 的基本结构、特征和服务仍然由最初的i e e e 8 0 2 1 1 标准定义， i e e e 8 0 2 1 l b 规范只影响i e e e 8 0 2 11 标准物理层，它增加了数据传输速率并增强 了连接的牢固性。 2 ) i e e e8 0 2 1 l a i e e e 8 0 2 1 l a 标准是已经得到广泛应用的i e e e 8 0 2 1 l b 无线联网的后续标准， 8 0 2 1 l a 工作在5 g h z 频段，其物理层速率可以达到5 4 m b i t s ，传输层可以达到 3 2 m b i t s ，采用正交频分复用技术o f d m ( o r t h o g o n a lf r e q u e n c yd i v i s i o n ) 调制数 据，将无线信道分成以低的数据速率并行传输的分频率，然后再将这些频率一起 放回接收端，可提供2 5 m b i t s 的无线a t m 接口和1 0 m b i t s 的以太网无线帧结构 接口，以及时分双工时分多路复用t d d t d m a ( t i m e d i v i s i o n d u p l e x t i m e d i v i s i o n m u l t i p l e a c c e s s ) l 拘接1 2 1 ，支持语音、数据、图像业务，提高了传 第2 章背景知识和相关工作 输速率，改进信号质量，克服干扰。但是，支持8 0 2 1 l a 的芯片还没有完全进去 市场，而且其设备价格昂贵。 3 ) i e e e8 0 2 1 1 9 由于i e e e 8 0 2 1 l a 与目前的i e e e 8 0 2 1 l b 规范之间频段与调制方式不同，使 得两者不能兼容，故8 0 2 1 1 9 就是为这段过渡时期所发展的规范，它构建在既有 的i e e e 8 0 2 1 1 b 物理层与介质层标准的基础上，选择2 4 g h z 频段，传输速率高 于l l m b i t s ，既能适应传统的8 0 2 1 1 b 标准( 在2 4 g h z 频率下提供的数据传输率 为l l m b i t s ) ，也符合8 0 2 1 1 a 标准( 在5 g h z 频率下提供数据传输率5 6 m b i t s ) ， 从而让已有的i e e e 8 0 2 1 1 b 产品的使用者能够以i e e e 8 0 2 1 l g 的产品满足速度升 级的需求。 4 ) 其他 此外i e e e 除了制定上述的三个主要的无线局域网协议之外，还制定和起草 了一系列用于完善无线局域网应用的协议，其中主要包括8 2 0 1 l e ( 对服务等级 ( q u a l i t yo fs e r v i c e ，q o s ) 的支持) ，8 0 2 1 l n ( 草案，更高传输速率的改善，支持多 输入多输出技术( m u l t i - i n p u tm u l t i - o u t p u t ，m i m o ) ) ，i e e e 8 0 2 1 l h ( 欧洲5 g h z 规 范) ，i e e e8 0 2 1 1 i ( 无线网络的安全方面的补充) ，i e e e8 0 2 1 l k ( 规定了无线局域 网络频谱测量规范，体现了无线局域网络对频谱资源智能化使用的需求) 。 2 1 2b l u e t o o t h 蓝牙【lo l 技术是由s i g ( 特别兴趣小组) 制定的一个公共的、无需许可证的规范， 其目的是实现短距离无线数据通信，蓝牙采用快速跳频和自动寻道技术的工作方 式，工作在2 4 g h z 频段上，由于其跳频快、数据包短的优点，使得蓝牙比其他 系统都更加稳定。蓝牙技术主要面向网络中各类数据及语音设备，通过无线方式 连接成一个微微网 ( p i c o n e 0 ，多个微微网之间可以互连成分布式网络，从而方便、 快速的实现各类设备的通信。是一种低成本、短距离的无线连接技术。 2 1 3h o m e r f h o m e r f j 采用共享无线接入协议s w a p ( s h a r e dw i r e l e s sa c c e s sp r o t o c 0 1 ) ，是 无绳电话技术d e c t ( d i g i t a le n h a n c e dc o r d l e s st e l e p h o n e ) 和无线局域网技术相融 合的产物，是针对现有无线通信标准的综合和改进，它使用t d m a + c s m c a 方式，适合语音和数据业务，且工作在2 4 g h z 的i s m 频段，网络上每个节点都 是相对独立，不受中心节点控制的。当进行数据通信时，采用的是i e e e 8 0 2 1 1 规范中的t c p i p 传输协议，当进行语音通信时，则采用数字化泛欧无绳电话 6 第2 章背景知识和相关i ：作 d e c t 规范。 2 1 4i r d a i r d a 1 2 1 是红外线数删r ( i n f r a r e dd a t aa s s o c i a t i o n ) 提出的采用红外线进 行点对点的通信技术，目前这项技术被广泛采用，相应的软硬件技术都比较成熟， 其传输速率可达1 6 m b i t s 。但是i r d a 是一种视距传输技术，中间不能有阻 挡物，且其核心部件一红外线l e d 并不经久耐用。 2 1 5 几种技术的比较 表2 1 几种无线技术的比较 无线技术工作频段最高带宽有效距离价格 i r d a ( 红外 1 1 1 m h z 一 9 6 k b p s - 4 m b p s s 1 0 m便宜 线)1 1 7 m h z b l u e t o o t h ( 蓝 2 4 0 g h z 1 m b p s ( 1 1 ) r s s i m j = l i = 万1 善mz f o ri = 1 m 于是可以得到如下的动态的接入式负载均衡优化策略： 1 ) s t a 在上电启动后，采用主动扫描的模式，在i e e e 8 0 2 1 1 规定的每条 第3 章接入式负载均衡优化没计 信道上向a p 发送探测请求帧，以获得a p 的相关信息。 2 ) a p 在收到探测请求帧后，以探测响应帧来回复s t a 。 3 ) s t a 在收到a p 的探测响应帧后，比较当前a p 探测响应帧中的s s i d 等 信息是否与自己的一致。若不一致，则不进行处理。否则首先对当前 a p 的r s s i 值进行判定，若a p 的r s s i 值大于规定的阀值，则将此a p 为标记为候选a p ，否则不进行标记。 4 ) 在主动扫描完毕后，s t a 根据候选a p 的列表，逐个的向每个a m p 发送 k 个( 一般可以为3 4 次) 探测请求帧，并记录下发送的时间，设发送探 测请求帧的时间为：s i ，s 2 s k 。而s t a 接收到a p 的探测响应帧回复 的时间为：r l ，r 2 r k 。则根据接收和发送的时间之差，可以计算s t a 所发送的探测响应帧的平均时间为： 一t - 终二墨! ! 墨二墨2 ! 生二墨! k ( 3 5 ) 5 ) s t a 根据式( 3 5 ) 计算出向哪个a p 所发送的探测响应帧的平均时间最 小，并选取最小时间的a p ，向其发送关联请求帧，请求与此a p 建立关 联。算法结束。 其算法的交互过程如图3 1 所示： 图3 1 接入式负载均衡算法的交互过程 2 7 第3 章接入式负载均衡优化设计 3 5 算法的改进 这种接入式算法在判定a p 的负载上比起使用s t a 站点数目衡量更加真实有 效，以信道的通信质量为衡量一个a p 当前的负载状况，比基于s t a 站点个数和 r s s i 信息的接入式负载均衡算法更能有效的反映当前a p 的负载情况，避免了 s t a 错误的接入到负载站点个数较少，但是业务量很重的a p 中去。但是由于接 入式负载均衡优化算法是属于被动的负载均衡策略，也即使只在s t a 站点加入 时才进行负载的判断，对s t a 站点接入到a p 后并不再采取任何的优化措施。如 果某个a p 所关联的s t a 站点通信量发生较大波动，通信量不断增加，而导致此 a p 出现超载情况时，没有任何的优化机制能够及时的使得此a p 分流出一部分 s t a 站点，以减小超载a p 的负担，缩短各个a p 之间的差异。故根据分析的结 果，本文继续对上述算法进行改进，当a p 当前不能够有效地提供给s t a 站点良 好服务和通信质量时，s t a 站点可以重新选择新的a p 进行重新关联。其算法的 主要思想如下： 1 ) s t a 在接入时，通过上述的算法选择一个所发送的探测响应帧的平均时 间最短的a p 进行关联。如果关联成功，则s t a 站点启动定时器，并进 入稳定状念。 2 ) 若当f j 订定时器超时，则s t a 进入抉择状态，抉择状态即是指s t a 可以 重新抉择信道上通信量较轻的a p ，故在进入抉择状态的s t a 仍然采用 主动扫描模式，在每条信道上发送探测请求帧，重新获得各个a p 当前 信息。 3 ) s t a 根掘收到的a p 的r s s i 信息进行判断，并把大于某个r s s i 阀值的 a p 标记为候选a p 。 4 ) s t a 向候选a p 发送k 个探测请求帧，并计算平均时间，根据平均探测 的时问找出候选a p 列表中具有最小值的a p 。 5 ) 若当前具有最小探测时间的a p 是s t a 当前所关联的a p ，则说明所关 联的a p 仍然是通信信道负载最轻的a p ，此时s t a 将重新进入稳定状 态。并启动定时器，转2 ) 。否则向最小探测时间的a p 发送关联请求， 并与当前a p 解除关联。若成功关联新的a p ，则此时s t a 进入强制等 待状态。 6 ) 为了防止s t a 由于热点a p 的出现，而导致不断切换引起的乒乓效应， 导致负载抖动的后果，故处于强制等待状态的s t a 必须要强制的等待 一段时间后，才能够进入稳定状态，。若强制等待的时间结束，则s t a 启动定时器，并转2 ) 。 各状态的关系如图3 2 所示： 第3 章接入式负载均衡优化设计 定 结束 图3 2 各状态之间的转换关系 上述算法在s t a 通过接入后，周期性的对当前a p 的信息进行判断，以选择 最佳的a p 进行关联，若出现信道负载更低的a p ，则s t a 自动的切换到此a p 上去，这样的策略能动态的根据当前的网络变化而进行调整，故比单纯的接入式 算法在均衡a p 负载方面能收到更好的效果，且算法方便简单，只需要s t a 发送 若干个探测响应帧就可以判断出结果，实现也主要放在s t a 站点上，因此基本 上无需对a p 端做任何修改，可以有效的减轻a p 端收集信息和信息计算的负担。 但是s t a 在切换时具有盲目性，当一个新的热点a p 进入无线局域网时，会出现 大量s t a 判断出此a p 不仅r s s i 大于阀值，且信道负载最低，故难免会出现s t a 纷纷离丌原有的a p ，而接入到新的a p 中去，同时大量的s t a 的接入，会造成 此a p 负载很重，但是在过了强制等待时间和稳定时间之后，s t a 则又判断出原 先关联的a p 的通信信道负载较轻，于是又重新关联到原先a p 中去，这样s t a 花费大量的时j 剀消耗在切换中，会造成负载的抖动，对网络资源造成极大的消耗， 对s t a 上的业务也造成不良的影响。其主要原因是s t a 在切换时具有片面性和 盲目性，也即判断标准仅仅是从s t a 的自身出发，对整个的网络环境不能准确 掌握，故在切换时，难免出现片面性，故导致负载均衡的效果不佳。且s t a 在 判断某个a p 当前情况时，需要一定量的信息交互，在容易对网络造成拥塞，在 a p 负载都较重时，会对网络性能造成不利的影响。 第3 章接入式负载均衡优化设计 3 6 算法复杂度分析 定理一：在s t a 接入时和接入后优化算法所开销的消息复杂度均为o ( m k ) 证明：假设在最坏的情况下，在s t a 采用主用扫描的方式，获得a p 的相关 信息时候，其所接收到的每个a p 的r s s i 值都大于既定的阀值，则此时s t a 就 需要把a p 全部标记为候选的a p 中去，设当前e s s 中有m 个a p 存在，则根据 算法，s t a 要向这m 个a p 分别发送k 个探测请求帧，以便获得探测的平均时 间。选择最佳的a p 进行接入，则可得s t a 发送探测请求帧的个数共计m k 个。 故在s t a 接入时，算法的消息复杂度为o ( m k ) 。而在s t a 成功关联某个a p 后， 根据算法改进的思想，s t a 站点每隔一段时间周期t ，就要重新获得当前a p 负 载情况和当前网络状况，假设同样在最坏情况下，m 个a p 的r s s i 值也均大于 既定的阀值，则s t a 也同样要发送m k 个消息，来获得当前平均探测时间最小 的a p ，则s t a 共计发出m k 个探测请求帧，故可得在s t a 接入时和接入后算 法的消息复杂度均为o ( m k ) 。 定理二：算法实际的时问复杂度为o ( m k ) 。 证明：同样，在最坏情况下，s t a 站点总共向m 个a p 发送了k 个探测请求 帧，并计算实际平均探测的时间，由异步算法的思想，可以假设任何执行消息的 延迟至多一个时间单位，则算法的时间复杂度主要就是s t a 计算k 个探测帧实 际时问的平均值，并在m 个实际平均时间中找出最小的值的时间复杂度，则可 得s t a 计算平均值的时间为o ( m k ) ，而在这m 个实际平均探测时间中找出最小 值的时间为o ( m ) ，则可得算法的时间复杂度为计算时间和寻找最小值的时间， 也即本文算法的时间复杂度为o ( m k ) 。 3 7小结 在本章中，首先描述了所考虑的网络模型及其假设条件，对问题做了明确描 述，然后根据无线局域网的相关协议将问题进行进一步细化，分析s t a 探测帧 平均时阳j 与无线局域网的网络性能和a p 的负载之间的关系。随之提出了一种新 的无线局域网接入式负载均衡算法，并对算法的利弊做了分析和探讨，根据分析 的结果继续对算法进行扩充和改造，改进了接入式负载均衡优化算法的缺点，使 其在s t a 接入后，也能根据当前的网络状态和a p 的负载选择最合适的a p 重新 进行关联。最后对算法的消息和时间复杂度做了分析。本章的研究工作主要贡献 在：1 ) 在无线终端接入到无线局域网时，站在s t a 端的角度对当前a p 所能提供 的服务质量和当前网络性能做了大致评判，根据评判结果选取相关a p 进行关联。 3 0 第3 章接入式负载均衡优化设计 2 ) 对算法进行改造，即在s t a 接入到a p 后，能根据网络动态的变化，再次选择 最优的a p ，并引入强制等待时间，预防“乒乓效应的产生。下章节将继续 对问题进一步延伸，分析并提出基于a p 的全局性质的负载均衡策略。对算法的 仿真实验可参见第五章节。 第4 章切换式负载均衡优化设计 第4 章切换式负载均衡优化设计 在上一章介绍了本文提出的一种无线局域网接入式负载均衡算法，在s t a 接入到网络时候，能够根据当自仃网络状况，选择合适的a p 进行关联，对a p 的 负载在网络初始时，进行了优化和分配，减轻了切换式负载均衡的压力。并且在 网络结构形成之后，s t a 还能及时进行调节，使其较为适应变化的网络环境。但 是这种仅仅靠s t a 的判断往往具有局部性和片面性，不能根据总体情况出发， 有效提高整个网络性能。为此本章首先分析了影响无线局域网性能的因素，对其 进行仿真验证，对其提出了优化的措施，在此基础上根据先前无线局域网成熟的 模型综合行分析，找出衡量a p 负载和当前局域网性能的关键因素。提出了一种 切换式的负载均衡策略，以信道的忙碌的时间做为衡量b s s 性能的标准，并保 证s t a 在切换后能获得良好的服务质量，控制超载的a p 进行分流。使其在复杂 且多变的网络环境下，能够对a p 的负载进行重新分配和均衡，有效的提高了无 线局域网的性能，减小了闲置的带宽，增强了系统的弹性和容忍度。 4 1影响无线局域网性能的因素分析 在考察无线局域网的性能时，通常需要综合多种因素进行判断，如：系统吞 吐量、媒体接入延迟、丢包率等。选取正确有效地指标，能有效地衡量一个无线 局域网的通信质量。而在这其中，吞吐量为最为重要和广泛应用的指标之一。 在实际环境中，有很多因素都严重影响系统的吞吐量，考察这些因素如何导 致吞吐量的变化，在负载均衡中，通过适当的调节这些因素，会使得负载均衡效 果更加优秀，也有利于对无线局域网系统性能评测。 4 1 1r t s c t s 对话 i e e e 8 0 2 1lm a c 层在基于c s m a c a 的基础上提供了确认帧的机制，如果收 到源节点发送的数据，目的节点都会回复一个a c k 帧确认收到。而没收到确认 帧的源节点则等待一定的退避时间后，再次重传该数据帧，直到次数达到最大限 制为止。而在网络较为拥塞的时候，为了进一步避免碰撞，重复传送数据帧， 8 0 2 1 l 又引入了r t s c t s 机制，也即： 1 ) s t a 在发送数据帧之自i 先发送一个“发送请求( r t s ) ”控制包即给目的站。 2 ) 目的站接受到r t s 后，如果信道空闲，则回发一个“发送响应( c t s ) 控制包表示源站可以继续发送数据。如果检信道忙，则不发送c t s ，这 样可避免不同s t a 同时向同一目的站发送信息。 第4 章切换式负载均衡优化设计 3 ) 如果源站收到c t s 帧，证明信道空闲，它就可以继续发送有用数据。 4 ) 目的站在成功接收后，经过最短帧间隔时间后就回发a c k ，如果在规定 的时间间隔后，源站未能收到a c k ，那么它就可判断出信息发送失败， 可根据需要重发，这样可避免信息丢失。其交互过程如图4 1 所示： 图4 1r t s c t s 交互过程 不仅r t s c t s 能避免数据包的碰撞，还能够有效的减小隐蔽终端的问题， 在仿真试验中，设置r t s c t s 的上限为2 5 6 字节，其中a p l 采用r t s c t s 机制， 而a p 2 不采用此机制，考察r t s c t s 对吞吐量的影响，其中仿真结果如图4 2 r p 一 所不。 侧愀s ) 图4 2r t s c t s 机制对吞吐量的影响 3 4 第4 章切换式负载均衡优化设计 可见a p i 在使用了r t s c t s 机制后，在负载很大的情况下，还能保持比 a p 2 高的吞吐量，证明r t s c t s 机制可以有效的减小数据帧的碰撞，提高吞吐 量。而在无线局域网的优化中，可以通过设置r t s c t s 字节的上限，一旦传送 的字节大于该上限，则自动启动r t s c t s 会话机制，由此减小数据包的碰撞， 优化系统性能。 4 1 2 数据包拆分 如果要发送的数据包很大，可以设置一个拆分的门限，将大的数据包分成若 干个较小的部分分批发送。接收方在接收到所有的分段后，重新将数据包拼装起 来。假设数据包长度为l ，传输中误码率为p b ，可以得到分组传输错误的概率为： 尸，= 1 一( 1 一只) “一傩 由于丢包率即为分组重传次数超过重传次数限制r 的概率，最后得到： = 眵= 1 - ( 1 一) “似 r ( 4 1 ) 由式( 4 1 ) 可见，数据包的长度越小，丢包的概率也就越小。数据包拆分在网 络拥挤或者存在干扰的情况下非常有用，但由于每个分段都需要回复一个a c k 确认，故增加了协议开销。 4 1 3s t a 的工作速率 由于在w l a n 的实际环境中，各s t a 的工作速率不同，所以对系统的性能 影响较大。主要是由于虽然s t a 的工作速率不同，但是各个s t a 在争抢信道的 能力上是相同的，因此高传输速率的s t a 占有信道后，能迅速的发送分组，随 即释放所占用信道。但是低传输速率的s t a 得到信道后，却要花费很长的时间 才能完成整个分组发送的过程，在此期间，如果高速率的s t a 想要发送分组， 只能耐心的等待信道被释放，所以系统信道的时间为低工作速率的s t a 大量占 有，使得高速率用户的吞吐量被极大地抑制，从而也导致了系统的总吞吐量下降。 为了验证s t a 不同工作速率速率所带来的影响，在仿真中，将两个s t a 分别放 在在a p 附近，其中s t a l 工作在1 1m b p s ，在仿真中当s t a 2 也工作在此工作 速率时，两个s t a 有着相同的吞吐量。而通过调节s t a 2 的工作速率至2 m b p s 后，高传输速率的s t a l 吞吐量也随之迅速下降，并仍然和低传输速率的s t a 2 保持一致，由此可见，不同s t a 的工作速率会对系统的吞吐量造成一定影响。 其s t a i 的吞吐量受s t a 2 的速率影响变化如图4 3 所示： 第4 章切换式负载均衡优化设计 卿 三 如 星 f 卜 4 o8 0 01 0 0 0 仿真时问( s ) 图4 3s t a 2 工作在不同速率下s