基于无线Mesh网络技术.doc

1、目录第一章绪 论11.1 研究背景和意义11.2 无线Mesh网络简介31.3 无线Mesh网络应用领域51.4 本文的主要研究内容61.5 论文的组织结构7第二章无线Mesh网流量负载均衡综述102.1 流量负载均衡的意义102.2 研究现状及分析122.2.1 网关部署及其协作机制132.2.2 路由协议142.3 流量负载均衡研究挑战172.4 本文研究的立足点182.4.1 网关部署算法182.4.2 负载感知的路由度量192.4.3 多路径流量分配策略192.5 本章小结20参考文献2122第一章 绪 论本章首先阐述论文研究的背景和意义，介绍无线Mesh网技术的特点和应用领域，然后叙

2、述本文的研究目标与内容，最后给出了全文的内容安排和论文的组织结构图。1.1 研究背景和意义进入21世纪，新科技革命迅猛发展，信息科学和技术发展方兴未艾。无线通信技术更是得到了飞速的发展，新技术不断出现，其中蜂窝移动通信系统已经向第三代和第四代系统演进，“无线城市”建设高潮席卷全球大中城市。国家中长期科学和技术发展规划纲要(2006-2020)中已经明确将宽带无线移动通信、下一代网络等核心技术作为我国信息技术的主要发展方向之一，其中无线Mesh网技术被视为下一代无线接入技术，是前沿技术中的重点。相对于有线接入方式，无线接入方式灵活方便，能更好地支持移动计算等无线业务，因而得到越来越广泛的应用，目

3、前形成了包括无线局域网(WLAN, Wireless Local Area Network)，基于无线城域网的宽带无线接入(BWA, Broadband Wireless Access)技术等多种形式。传统的无线接入系统中一般采用单跳的方式进行连接，很难适应接入系统节点增多和覆盖范围扩大的需求。然而不断增多的接入用户需求、不断扩大的覆盖范围需求、日益增长的接入业务需求，以及频谱资源日趋拥挤的现状，都对接入系统的可扩展性(Scalability)、覆盖能力(Coverage)、能量优化(Power Efficiency)、频谱有效性(Spectrum Efficiency)及QoS支持能力等提出

4、了更高的要求 此处引用一般为经管类、文法类等参考文献。因此，寻找一种能够完美地结合接入用户的分布形态、基本不受节点规模增加和覆盖范围扩大的限制、具有可持续增长的系统容量、便于扩展、易于部署的新型接入技术已成为不少学者的研究目标。无线Mesh网(WMN, Wireless Mesh Network)既是一种新型宽带无线接入系统，又是一种由无线链路连接路由器和终端设备组成的静态多跳无线网络。它可以看作是WLAN和Ad hoc的融合，具有可靠性、自组织性和自愈性等特点；它是一种解决“最后一公里”网络接入问题的多点对多点的分布式网络1。与传统无线接入技术相比，无线Mesh网络具有以下优势：(1) 无线

5、Mesh网络具有自组织、自愈、自均衡，可靠性高等特点，还提供了更大的冗余机制和通信负载平衡功能；(2) 很容易实现非视距传输，大大扩展了应用领域和覆盖范围，信号避开了障碍物的干扰，传送畅通无阻，消除了盲区；(3) 组网更加灵活，在传统无线网络基础上增加少量无线设备即可完成无线Mesh网组网，网络更具柔韧性和可行性，网络利用率大大提高；(4) 兼容多种类型接入方式，连接到Internet只需几个接入点，大大减少网络建设成本。基于无线Mesh网络技术的先进性和重要性，其理论及应用研究已成为国际学术及工业界研究热点。我国非常重视无线Mesh网络技术的发展。清华大学已在校园内建立了一个实证网络，中国科

6、学院院计算所、中国科技大学、上海交通大学、西安交通大学、哈尔滨工业大学、中南大学等单位也积极开展了相关研究工作。国家自然科学基金委员会已经审批了多项无线Mesh网络相关的重点课题和面上课题；在国家发展改革委员会的下一代互连网示范工程中，也部署了无线Mesh网络相关的课题；无线Mesh网络相关研究也得到了“863”、“973”计划资助。经过一段时间的发展，无线Mesh网络技术研究与应用已经取得了阶段性的进展，在多跳路由算法、高效MAC协议、网络性能优化等方面产生了一系列研究成果。但是，无线Mesh网络技术的全面应用仍然要解决很多极具挑战性的问题，如有限的网络容量、路由、漫游、负载均衡、QoS以及

7、安全问题等等。在某些领域，无线Mesh网络的相关技术标准尚未形成，对其关键技术展开研究将大有可为，也有希望取得具有自主知识产权的创新性成果。无线Mesh网技术应用日益广泛，国际国内相继应用无线Mesh网技术来解决大规模的无线接入问题。如：美国旧金山和费城的无线城市计划，新加坡的“智能国家”计划，台湾地区的“移动台北”计划以及北京、上海、武汉、深圳、天津等城市正在实施的“无线城市”计划。广泛的应用给无线Mesh网技术提出了很多挑战性的问题，对无线Mesh网络的性能进行分析研究，构建无线Mesh网络的性能模型，优化网络设计方案，无疑对无线Mesh网络的发展具有重要意义。鉴于无线Mesh网技术研究的

8、重要意义，本论文研究无线Mesh网性能优化技术，着重从实现流量负载均衡的角度提升网络吞吐量及服务质量。同时，国家自然科学基金项目“无线Mesh网中基于网络演算理论的QoS保证研究”（60873082）为本论文研究工作的展开提供了良好的软件、硬件环境。1.2 无线Mesh网络简介无线Mesh网是无线多跳传输网络，其中有三种类型的节点： 网关、Mesh路由器和Mesh终端。网关不仅具有Mesh路由器的功能，而且与Internet直接通过有线电缆相连，是无线Mesh网与Internet连通的桥梁。图1-1为无线Mesh网络的一种典型拓扑结构。如图所示，多个Mesh路由器和网关节点组成网络主干，称之为

9、无线Mesh网的无线骨干层(网)。它们之间通过IEEE 80211或其他无线技术相连，并且具有自动配置、自我愈合功能。这些Mesh路由器之间可以点对点或多次跳转相连，从而构成Mesh结构。网关路由器通过有线电缆与Internet相连，这样，整个骨干网就可以与Internet连通。与Mesh路由器采用相同无线技术的客户端可以直接和骨干网中的某个Mesh路由器相连，从而接入Internet；同时，骨干网提供对移动客户端在Mesh路由器之间的无缝切换支持。对于使用不同无线技术的其他客户端，可以通过先与基站相连，再通过基站转接到Mesh骨干网，如蜂窝网设备、WiMAX客户端设备和无线传感器网络。Mes

10、h终端用户的数据经由Mesh路由器的多跳传输到达网关，再通过网关的转发实现终端的Internet访问。因此，骨干网的性能对终端用户访问Internet的服务质量(Quality of Service, QoS)有重要影响。图 一1无线Mesh网典型拓扑结构无线Mesh网体系结构上的特点，使其具有一些传统无线网络结构所没有的优势，主要表现在以下几方面4, 5：(1) 兼容性好无线Mesh网可以通过相应的网关与Internet、WiFi局域网、公共电话网等网络相连，网络中的无线终端用户也可以连接到其他网络。(2) 前期投资少铺设一个新的网络，首先考虑的是覆盖范围。在无线Mesh网络中不需要基站。少

11、了前期的基站勘测，建设基站等基础设施的昂贵费用，对网络服务商来说，前期投资很低。(3) 可靠性高在传统的点对多点网络中，节点的接入采用了星型结构，多个节点将首先接入到一个中心点，若其中某一个中心点出现了故障，将会影响到整个网络的正常工作。而无线Mesh网络为网状结构，每个节点可使用的链路数大大增加，且每个节点都具有选路功能，其中一条链路出了故障，节点可以自动转移到其他可选链路，使得网络的可靠性有了很大程度的提高。此外，由于无线Mesh网不需要建立大型基站及发射塔，并且具有自我修复的功能，因此消除了因个别通讯设备，如基站及发射塔的故障而导致整个系统通讯受阻的隐患。这样在发生任何重大的意外事件或自

12、然灾害时，即使一部分网络设备受损，也不会造成整个网络的瘫痪。(4) 可扩展性好与星型网络相比，无线Mesh网是一种无中心网络，网络节点具有自组织、自我管理能力，若需要加入新节点，网络可以自动建链，自动搜索路由，简化了网络扩展的工作量，也大大提高了网络覆盖范围。(5) 维护简便Mesh结构简化了网络的维护与升级，每个节点都有多条可选路由，使得局部地区的升级与扩容不会影响到整个网络的运行，方便了网络的维护与操作。无线Mesh网的这些优点使其在各种无线网络建设中得以广泛的应用，但是，面对不断增多的接入用户需求、不断扩大的覆盖范围需求、日益增长的接入业务需求，无线Mesh网在网络性能、服务公平性、Qo

13、S等方面面临很多困难。由于无线Mesh网终端用户的行为特性，网络流量大部分是经网关节点通往Internet的。同时，无线骨干网中网关节点及其性能也是有限的。由此导致，无线Mesh网存在下列显著特点：(1) 网络中大部分流量汇聚于网关，网关常常成为网络性能的瓶颈6；(2) 离网关较近的节点能得到较好的服务质量，较远的节点得到的服务质量较差，各节点间存在服务质量的不公平性7-9。为达到无线Mesh网的性能优化，各项技术必须考虑并适应无线Mesh网的上述特点。这些特点也为无线Mesh网相关技术的研究指明了方向。1.3 无线Mesh网络应用领域由于无线Mesh网所具有的特殊优点使得它在各种无线接入通信

14、领域都占据了重要的一席之地。其主要应用领域有4, 10：(1) 无线接入城域网2004年，世界上第一个无线城市美国“无线费城”开始建设。此后，世界其他地方的无线城市计划陆续出台，芝加哥、休斯敦、巴黎、伦敦、新加坡等地都开始了规模不一的无线城市建设。目前，国内的一些城市，如北京、上海，以及长三角和珠三角的一些经济较发达城市，无线城市建设正在实施。无线Mesh网在一定程度上突破了“热点”对Wi-Fi应用的制约，成为无线城市建设的主流技术。(2) 校园网2006年清华大学建成基于无线Mesh网技术的实证网络，2007年民族大学利用无线Mesh网技术，通过30台MSR1000Mesh路由器实现了整个校

15、园的“全无线”覆盖。无线Mesh网技术在各大学校园网中得到了大规模的应用。高校无线网络采用无线Mesh网技术适合校园网地域范围大、用户多、通信量大、覆盖要求高等特点。无线Mesh网技术可以实现室内、室外、礼堂、宿舍、图书馆、公共场所等之间的无缝漫游。(3) 医院医院建筑物的构造密集复杂，一些区域要防止电磁辐射。布线比较困难，对网络的健壮性要求很高：如有重要活动(如手术)，任何网络故障都将会带来灾难性的后果。采用无线Mesh网正好能够解决这些问题，无线网络拓扑调整简单，而且网络的健壮性和高带宽也更适合医院等公共场所部署。(4) 旅游休闲场所无线Mesh网非常适用于偏远或不发达地区通信，如旅游场所

16、、度假村、汽车旅馆等。在这些地区，由于造价、地理环境等原因往往没有或者有限的有线通信设施，而又需要为用户提供宽带无线Internet访问。无线Mesh网能够以最低的成本为这些场所提供宽带服务。(5) 需要快速部署或临时安装的场所对于那些需要快速部署或临时安装的地方，如展览会、交易会、灾难救援等，无线Mesh网络是最经济有效的组网方法，可以将成本降到最低。此外，无线Mesh网在交通11、铁道12、矿井13、建筑等行业及场所也得到了广泛的应用，并产生了巨大的经济效益。1.4 本文的主要研究内容无线Mesh网体系结构的特点决定了由网关和Mesh路由器构成的无线骨干层是影响网络性能的关键。因此，本文关

17、注无线骨干层的网络性能优化，并尝试从流量负载均衡的角度提高无线Mesh网的吞吐量以及各项服务质量。由于无线Mesh网终端用户层不是本文讨论的重点，所以下文提及的无线Mesh网均指其无线骨干层。针对如何提高无线Mesh网流量的负载均衡，本文分别从无线Mesh网的设计阶段和运行阶段研究相关技术，采用不同的策略优化网络流量的负载均衡。在网络设计阶段，强调网关节点的负载均衡部署，在网络运行前考虑流量的负载均衡往往能达到“事半功倍”的效果；在网络运行阶段，通过设计负载感知的路由协议及其关键技术实现Mesh路由器以及网关节点的负载均衡，并提高网络服务质量。围绕网关节点及Mesh路由器负载均衡优化问题，本文

18、主要研究以下内容：(1) 对无线Mesh网的网关部署问题展开深入研究。提出负载均衡的网关部署模型，定义负载均衡的度量指标，设计基于遗传算法的网关数量及网关负载均衡双重优化的网关部署算法。(2) 研究无线Mesh网的网关部署费用，提出满足QoS约束费用最小且负载均衡的网关部署问题，定义网关的部署性价比指标，并基于网关部署性价比提出实现费用及负载均衡优化的网关部署算法。(3) 研究网关部署问题与图论支配集理论的相关性，并把本文研究的网关部署问题转化为扩展的最小权支配集问题，基于支配集理论提出求解算法。(4) 基于无线Mesh网具有自相似性的流量特征，应用自相似流量的可预测性，研究具有负载自适应的路

19、由度量及路由协议，从而促进网络流量在节点间均衡负载。(5) 研究多路径路由中具有提升网络流量负载均衡的路径流量分配算法，讨论流量负载均衡与服务质量之间的关系，基于网络演算理论对多路径传输中的端到端时延及抖动展开分析，提出时延及抖动优化的多路径流量分配策略，使网络在流量负载均衡下进一步优化端到端的QoS。1.5 论文的组织结构本论文共分八章，各章节内容安排如下：第一章为绪论。介绍了本文的研究背景和意义，介绍无线Mesh网技术及其应用领域，最后给出了本文的主要研究内容及本论文的组织结构。第二章分析了当前无线Mesh网流量负载均衡方面的研究现状，并重点分析了网关部署策略及路由协议对流量负载均衡的意义

20、。参考文献部分列出了本论文参考的主要论文和资料。致谢部分对导师和各位师友所提供的帮助表示衷心的感谢。最后部分给出了攻读博士学位期间主要的研究成果。本文以无线Mesh网中流量负载均衡优化为主线展开研究。由于无线Mesh网中网关及Mesh路由器的重要作用，无线Mesh网作为整体流量的负载均衡的实现既要考虑网关之间流量负载均衡，又要考虑Mesh路由器之间的流量负载均衡。因此，分两条线索展开负载均衡具体技术的研究。围绕网关之间流量负载均衡，深入研究网络设计阶段的网关负载均衡部署算法；围绕Mesh路由器流量负载均衡，深入研究具有负载感知能力的路由度量及其协议，以及多路径路由中的路径流量分配策略，路由协议

21、技术的相关研究也有利于实现网关负载均衡。论文的组织结构如下图所示。图 一2 论文的组织结构图中南大学博士学位论文 第二章 无线Mesh网流量均衡负载综述第二章 无线Mesh网流量负载均衡综述无线Mesh网骨干层由网关和Mesh路由器组成，其网络服务质量是影响无线Mesh网性能的关键。无线Mesh网流量负载均衡不仅要求网关之间的负载均衡，也要求Mesh路由器之间的负载均衡。本文针对无线Mesh网流量负载均衡的研究工作分别从网关负载均衡和Mesh路由器负载均衡展开。在探讨具体的解决方法与技术之前，我们对无线Mesh网流量负载均衡相关课题展开了大量的调研，以期在前人的研究基础上取得进一步的拓展。本章

22、阐述无线Mesh网中流量负载均衡的意义、研究现状、以及本文研究的立足点。2.1 流量负载均衡的意义无线Mesh网中网关不仅具有Mesh路由器的功能，还与Internet直接通过有线电缆相连，是无线终端用户与Internet连接的桥梁。无线Mesh网大部分流量通过网关在无线终端与Internet之间往来，而且流量具有不对称性14，大部分是Internet通往无线终端的流量，因为终端用户无线接入网络的主要目的是从Internet索取资源。因此，无线Mesh网中大部分流量承载于数目有限的网关节点上，网关节点流量负载不均衡将导致下述问题：(1) 负载过重的网关不能保证所有终端用户的服务质量。由于无线M

23、esh网中存在服务质量的不公平性7-9，离网关较近的终端用户可以得到较好的服务。对离网关较远的终端用户，网关负载过重导致服务质量难于保证；(2) 负载较轻的网关不能充分利用其资源为更多的终端用户提供服务。为优化性能以及降低路由复杂性，无线Mesh网往往划分成互不相交的多个簇，每个簇由一网关担当簇头为簇内的节点提供服务，因此每一个网关节点所服务的终端用户数量是相对固定的，负载较轻的网关节点不能利用其剩余的处理能力为更多的用户服务；(3) 由于网关节点是无线Mesh网性能的瓶颈6，即使网络流量远远低于其最大容量，网关节点负载的不均衡也会导致较差的网络服务质量15。如图2-1所示，两个网关节点的无线

24、Mesh网中，Mesh路由器A-E的汇聚流量通过网关G1到达有线网络，网关G2为Mesh路由器H、I、J提供服务。由于G1服务的Mesh路由器节点较多，其承载的流量可能超过其最大负载能力。相反的是，G2承载的流量较少，但不能为其它Mesh路由器提供服务。此时，G1与G2的负载不均衡将导致网络整体吞吐量及性能下降。图 二1 网关负载不均衡示例因此，无线Mesh网中网关之间的流量负载均衡对网络吞吐量以及服务质量有重要影响。为促进网关流量负载均衡，可以从两方面展开。其一，在网络设计阶段，针对无线Mesh网的流量特征有预见性地部署网关节点，在流量相对集中的区域，部署性能较好或者数量较多的网关节点；其二

25、，在网络运行阶段，设计有助于流量负载均衡的路由协议以及网关协作机制。无线Mesh网骨干层由网关和Mesh路由器组成，Mesh路由器之间的流量负载均衡也对网络性能有重要影响。Mesh路由器主要作用是汇聚终端用户产生的流量，并通过多跳传输把数据传送至网关节点。无线Mesh网的多跳传输特性使得Mesh路由器承载的流量包含两部分。其一为Mesh路由器本身所连结的终端用户产生的流量，称为本地流量；其二为来自其它Mesh路由器的转发流量。本地流量是Mesh路由器必须承载的，而转发流量的多少则与路由协议有关。如图2-2所示，Mesh路由器A与网关G、D与G、F与G同时通信，如果使用DSR16、AODV17等

26、选择最短路径作为传输路径的路由协议，那么三条通信流都选择通过Mesh路由器B到达G。但是，随着B流量负载增加，附近区域流量的高度集中导致无线干扰加剧，三条通信流的传输质量将会下降。然而，对于Mesh路由器F，虽然path 1路径较短，但使用path 2能避开节点B周围的流量集中区，具有更好的传输性能，能更好地实现Mesh路由器的流量负载均衡。图 二2 Mesh路由器负载不均衡示例如上所述，Mesh路由器之间的负载不均衡将导致网络流量集中于某些链路，从而形成一些流量高度集中的区域。流量的集中会带来三个问题：(1) 流量集中区易于产生拥塞，数据流传输延时增大，丢包严重；(2) 网络传输的可靠性下降

27、，由于流量集中区的节点周围无线干扰加重，引起大量的数据重传，路由错误以及重路由，导致网络吞吐量的急剧下降；(3) 非流量集中区的网络资源没有得到充分利用，网络的利用率差。因此，与网关流量负载均衡一样，Mesh路由器流量负载均衡对无线Mesh网网络性能优化有重要意义。为实现Mesh路由器之间流量负载均衡，应选择具有负载感知和自适应的路由协议。2.2 研究现状及分析无线Mesh网流量负载均衡依赖于网关以及Mesh路由器上的流量负载均衡。网关部署策略、网关协作机制以及路由协议对网关负载均衡有重要影响。Mesh路由器流量负载均衡需要具有负载感知及自适应的路由协议的支持。鉴于无线Mesh网流量负载均衡对

28、网络性能优化的重要意义，其相关技术已有深入研究，主要集中于负载均衡的路由协议这一领域。遗憾的是，当前具有负载均衡的网关部署策略研究鲜见报道。2.2.1 网关部署及其协作机制网关部署的合理与否是网络性能好坏的重要因素。为实现网关之间流量负载均衡，本文关注无线Mesh网的设计，研究如何合理部署网关节点以实现流量负载均衡，并且提升网络性能和保证网络服务质量。在无线Mesh网中，网关节点越多其性能越好，但是成本也越高。因此，在部署网关节点的同时，应该考虑网络的建设成本。网关部署问题就是在给定的节点中，选择少量的节点作为网关，通过这些网关能为所有终端用户提供QoS保证的服务。网关的合理部署可以提高无线M

29、esh网的各项性能18。已有的研究工作把网关部署问题模型化为线性规划优化问题，并针对不同的约束条件提出网关部署算法。Wong19等提出了最小化通信时延和最小化通信代价的两个独立的网关部署问题，并把问题归结为整数线性规划问题，对这两个问题分别提出基于统计方法的启发式算法。Chandra20等在保证各个节点带宽要求的前提下，试图最小化网关的数量，并提出具有容错能力的贪婪算法来实现它的目标。Bejerano21等采用分簇的思想，把网关部署问题转化为两个问题，并提出不同链路模型下的贪婪算法。Aoun22等提出QoS约束的网关部署贪婪算法Recursive_DS，该算法使用递归调用方法构造满足QoS约束

30、的最小权支配集，以达到网关数量最少；算法每一次迭代基于前一次的网关集合构造最小权支配集，最后得到满足QoS约束的网关数量最少的部署方案。He23等讨论了网关部署中的建设费用问题，并提出有效降低费用的两种启发式算法。Li24等研究吞吐量最大化的网关部署问题，提出基于网格的部署方法，并应用跨层设计方法优化网络吞吐量。Prasad25等人把网关部署问题化为线性规划问题，并提出求解算法OPEN/CLOSE，该算法以网关的最大负载能力从大到小一次选择网关候选节点，形成初始的网关部署方案；为了对网关部署费用进行优化，该算法对费用和网络簇结构进行循环迭代优化，直至不能进一步优化为止；算法对网关部署进行优化的

31、思想是，每次关闭(Close)部署费用最大的网关，然后开启(Open)其它若干个网关候选节点供选择，以获取费用优化的部署方案。上述大部分网关部署算法试图在保证QoS的条件下，尽可能地减少网关数量，或者优化某一项QoS性能。但是，欠缺对网关之间流量负载均衡的考虑，网关上流量负载不平衡将会导致，一方面负载重的网关不能为其所服务的客户提供较好的服务质量，另一方面，负载较轻的网关不能充分利用网络资源为更多的客户服务。另外，在不同的地理位置和网络拓扑环境中，部署网关的费用是不同的，网关数量少不一定就是网关部署的费用小，QoS性能的提升也增加了网关部署的成本。因此，已有的研究工作仍需在下述方面进一步完善：

32、(1) 网关之间流量负载应该尽可能均衡，以提高网络吞吐量及网路服务质量(2) 无线Mesh网的网关部署需要前期投资，如何在满足服务质量要求的前提下尽可能节约投资成本具有重要的现实意义；(3) 网关部署方案应该考虑更多的服务质量因素，如与多媒体应用关系密切的传输时延及抖动。此外，网关协作机制对网关负载均衡也有重要影响。为实现网关负载均衡，优化网关部署是网络设计阶段工作的关键，当网络正常运转后，网关之间的协商与合作能进一步提升网络性能。网关是无线Mesh网性能的瓶颈，当单一网关由于负载过重而无法保证网络服务质量时，网关之间的协商与合作对无线Mesh网性能的提高和QoS保证有重要的意义。为实现网关负

33、载均衡，已有的研究工作可分成两类，其一是利用路由协议实现网关之间的切换15, 26-32，使得网络流量均衡负载于各网关；其二是当网关超载时，由超载网关主动与其它网关协商33, 34，减轻负载，网络QoS得到保证。两者各有优劣，第一种方法由Mesh路由器主动发起，可以减轻网关的负担，但容易造成路由不稳定，给网络QoS保证引入更复杂的因素；第二种方法由超载网关主动发起，不仅能充分利用网关资源，而且可以最大限度保证当前会话的服务质量，但灵活性稍显不足。本文尝试在无线Mesh网流量特征分析的基础上，研究合理的满足QoS要求的网关部署方案。基于已有的研究工作，优化无线Mesh网网关之间的流量负载均衡，并

34、考虑网关部署的建设成本。2.2.2 路由协议无线Mesh网路由协议已有深入的研究。由于无线Mesh网骨干层与Ad hoc网络有相似特性，Ad hoc网络的路由协议适当修改后可用于无线Mesh网，主要代表有AODV17, DSR16, TORA35，DSDV36, WRP37等协议。在网络仿真和实际网络的运行过程中，我们发现，当网络的流量达到一定程度的时候，运行这些协议下的网络的性能出现明显的下降，分组传送出现时延增加和丢包率上升的趋势，而此时的网络总流量仍远远低于网络的最大容量。造成上述状况的原因是，这些协议的路由建立机制中没有考虑节点负载均衡问题。在数据传输过程中，中间节点收到分组数据之后并

35、不考虑自己的负载状况，直接进行转发，这使得负载较重的节点的负载得不到缓解，在重负载节点处形成很长的等待队列，从而造成分组的排队等待时延的急剧增加，导致大量的数据分组被丢弃。同时在新的路由请求分组到达时节点也自动加入新的路由成为中间节点，这使得原本负载己经很重的节点又要增加新路由带来的流量，从而进一步加剧节点负载，使得网络性能急剧下降，并导致网络拥塞和瓶颈的出现。另外，这些路由协议在路由选择时，主要考虑的是源端到目的端的“最短路径”，但是“最短路径”不一定就是“最好路径”；同时，路由协议数据分组在转送时具有较高的转发优先级，这些分组到达目的端的先后不能反映所走路径传输能力的好坏。这些因素导致使用

36、这些路由协议时，网络流量可能会集中于某些链路，从而形成一些流量高度集中的区域。流量高度集中于某小区域将引起Mesh节点的负载失衡，从而带来网络性能的下降。因此，为了改善网络性能和充分利用网络的传输能力，在设计无线Mesh网路由协议时应该考虑负载均衡问题。为使路由协议选择路由时避开流量集中区域，国内外研究学者提出了一些负载感知或者链路性能感知的路由度量。Adya38等提出RTT度量方法，制定测量无线链路RTT的机制，并把路径上所有无线链路的RTT之和作为路由协议选择路由的标准；Draves39等提出PktPair度量方法，为减小排队时延对RTT度量的影响, 提出使用背靠背大小包的测量方法来测量链

37、路RTT。De Couto40等提出EXT度量，该度量表示发送端发送及重传数据包的期望值，以保证数据包成功到达目的端。文献39对这些路由度量进行实验评估。模拟实验表明，在节点静止情况下，RTT度量受路由内部干扰较大，不稳定；PktPair度量表现稍好，但仍受到路由内部干扰的影响；EXT度量有较好的表现。为实现对无线干扰的感知，Yang41等提出了具有干扰感知能力的路由度量MIC以及路由协议LIBRA，该协议寻找干扰最小的路径作为数据传输路径，一定程度上促进了网络的流量负载均衡。Ma42等从IEEE 802.11 MAC协议网络分配矢量(NAV)中提取节点干扰信息，提出基于IEEE 802.11

38、标准的干扰感知路由度量NAVC以及路由协议DIAR，实现网络性能的优化。Hassanein43等学者定义了节点的活跃度，并以路径中节点的活跃度之和为路由度量提出了Ad hoc网络路由协议LBAR，该协议总是选择负载较轻的路径作为数据传送路径，有利于实现网络的负载均衡。为适用于多天线多信道网络环境，Draves29等学者定义了无线链路的成功传输一个分组的期望时间(ETT)，把路径中所有链路的ETT之和作为评价路径传输能力高低的标准，即路由度量WCETT，并基于该度量提出了适用与多天线多信道环境的路由协议MR-LQSR，网络试验表明在多天线多信道环境中，WCETT优于其它路由度量。无线Mesh网路

39、由协议中，根据使用单条还是多条路径，可以分为单路径路由协议和多路径路由协议。单路径路由协议实现简单，易于管理和配置，但是使用单一路径容易导致流量高度集中于某些节点，带来服务质量的下降。多路径路由协议通过建立多条路径来传输数据流，网络流量分布在多条路径上，更能实现网络的负载均衡，从而提高网络吞吐量，降低网络传输的丢包率、时延和抖动等性能指标，优化网络服务质量。然而，无线Mesh网中多路径路由技术远未成熟，在多路径的发现和维护机制、路径的选取策略、路径间的流量分配等方面仍待进一步完善。国内外专家学者对这些问题从理论和实践上做了深入的研究，并得到了一系列的研究成果，如基于AODV协议的多路径协议AO

40、MDV44和AODV-BR45，基于DSR协议的多路由协议MSR46，基于DSDV协议的多路径协议MDSDV47。这些多路径协议在经典的单路径路由协议的基础上，加入多路径的发现、维护机制实现多路径传输，虽然增加了协议控制开销，但提高了网络吞吐量及各项QoS性能48。在多路径路由协议中，最优路径集的选择是NP难的，路径集的选取应该在协议复杂性与协议性能之间权衡。Papadimitratos49等学者提出启发式算法快速选择具有高可靠性的若干路径构成路径集，并且路径之间相互不交叉，所提出的多路径路由协议DPSP具有较小的复杂性和控制开销，可以降低路由发现的频率。Zafar50等提出具有快速路由故障恢

41、复能力的多路径路由协议SMS，该协议选择较短的若干条路径作为数据传送路径集，且允许其中的路径部分相交。上述多路径路由协议虽然是基于Ad hoc网络的，但仍然适用于无线Mesh网。针对无线Mesh网的流量特征，Nandiraju51等学者提出多路径路由协议MMESH，该协议能有效发现端到端的多条路径，并制定路径间流量分配机制实现网络的流量负载均衡。针对无线Mesh网的体系结构特性及其较稳定的连接特性，Mosko52等学者指出无线Mesh网中的多路径路由协议允许路径相交和路由环路存在能实现更好的网络性能，并在网络仿真实验中验证了该观点。针对无线Mesh网多天线多信道环境，Hieu53等人在使用的路

42、径数量与需要传输的数据量之间权衡，提出具有路径负载均衡的多路径路由协议OEB，该协议有效地降低了协议控制开销，从而提高了网络吞吐量。在多路径路由协议中，路径流量分配策略对网络性能、吞吐量以及流量负载均衡有重要影响。一些学者提出了各种用途的路径流量分配算法，如An54等人提出的适应拓扑动态变化的路径流量分配算法，Li55等提出的避免拥塞的路径流量分配算法，Wang56等提出的基于FEC编码纠错的时延优化的路径流量分配算法，Yin57等提出能量消耗最小化的路径流量分配算法。此外，一些学者尝试从理论上论证多路径路由协议中路由发现、路径选择等机制满足的要求，以及性能的评估模型。Banner等人提出了严

43、谨的理论模型以最大程度降低多路径路由中发生拥塞的可能性，得到理论上性能保证有效方案。Chen58等提出多路径路由的性能分析模型，用于评估多路径传输中的端到端时延、传输可靠性以及负载均衡等情况。综上所述，已有的研究工作尝试从路由度量、路由发现及维护机制、多路径路由等方面实现网络的负载均衡、提高网络吞吐量及性能。然而，无线Mesh网有其特有的体系结构和流量特征，在Ad hoc网络中有效的路由协议在无线Mesh网中可能无法发挥其优点。虽然，已有很多研究工作集中于设计有效的无线Mesh网路由协议，并取得了一些进展，但是仍未有效地实现无线Mesh网的流量负载均衡，其网络性能与服务质量仍可进一步优化。2.

44、3 流量负载均衡研究挑战无线Mesh网具有独特的体系结构和流量特征，具有与其它无线网络相似的节点及链路干扰、带宽有限以及传输可靠性低等特点。适应这些特点是各项优化流量负载均衡技术的前提，其研究挑战可总结如下：第一、无线Mesh网中网关节点的性能、部署的数量和位置是影响网络性能的重要因素。对于给定的拓扑结构以及流量分布，在保证终端用户QoS的条件下，如何让网关的部署数量最小、部署费用最小以及流量负载均衡都是难于解决的最优化问题。设计快速有效的算法求解合理的网关部署方案则是专家学者们一直追求的目标。但是，诸如智能天线、多信道等新技术的出现以及要求更高的QoS保证使得问题更加复杂。另外，随着网关服务

45、的用户的增加，网络性能将会变差，如何在用户密集区域部署额外的网关节点以最大化网络吞吐量也是具有挑战性的问题。第二、与其它无线网络一样，无线Mesh网中存在来源于环境及网络自身的很多不可预测因素：(1)无线通信受到很多不同来源的射频干扰，因此其通信环境是高度动态变化及不可预测的；(2)终端用户的移动性带来流量的突发集中是不可控制的，例如在机场登机口，登机前的一段时间流量相对集中，而其它时间流量稀疏；(3)网络的单个节点是不可靠的，可能由于流量过载或其他原因而发生故障；(4)由于终端用户的退出和加入，网络流量分布是动态变化的。而从应用角度来看，数据传输需要以一个稳定可靠的方式进行，因此，无线Mes

46、h网的相关技术应该具有流量均衡能力，尽可能提高网络吞吐量。第三、无线Mesh网作为下一代的无线接入技术，具有覆盖范围大、可扩展性好、兼容异构网络、良好的容错性等优点。具有负载均衡能力的路由协议设计不可与之背道而驰。首先，路由协议复杂性应该较低，不需要全局性的信息支持，网络节点数的增加对协议开销影响不大，这样才能具有良好的可扩展性；其次，路由协议应能对节点故障、链路失效做出快速反应，特别是当某一网关发生故障或者负载过重时，能把相应流量转移到其它邻近网关；再次，路由协议能够选择最有效的路径传输数据，对即将发生的拥塞有感知能力，并且对数据传输有QoS支持或保证。除此以外，终端用户与网关相互通信是无线

47、Mesh网最主要的数据传输模式，与Ad hoc网络的任意两节点间的通信模式有很大的区别，已有的Ad hoc路由协议不能很好的应用到无线Mesh网中，这也给无线Mesh网路由协议设计添加了难度。第四、无线Mesh网应满足应用实时性及可靠性要求。诸如语音聊天、视频会议、远程医疗、网络游戏等多媒体应用日益广泛，正成为广大网民日常生活不可或缺的部分，无线Mesh网必须支持这些多媒体应用。在流量负载均衡提高网络吞吐量的同时，必须保证多媒体应用的QoS，尤其是实时性，保证终端用户流畅的实时体验。由于无线链路的低可靠性和带宽有限特点，特别是当在线用户数量庞大时，网络带宽资源更显不足。在有限的带宽资源下，开发

48、实用性强的技术改善多媒体应用的服务质量更具挑战性59。2.4 本文研究的立足点综上所述，无线Mesh网流量负载均衡包括两方面：网关之间流量负载均衡和Mesh路由器之间流量负载均衡。无线Mesh网流量负载均衡可以从网关部署、网关协作机制以及路由协议等方面着手实现。当前，负载均衡的网关部署方案相关研究较少，满足无线Mesh网流量特征的网关负载均衡部署方案对无线Mesh网性能的优化有重要意义。无线Mesh网路由协议已有广泛研究，在路由发现、维护机制等方面有较多成熟的解决方案，但在路由度量以及多路径路由的路径流量分配等方面仍需针对无线Mesh网的特点展开进一步研究，以促进无线Mesh网流量负载均衡和改善网络的QoS。因此，本文立足于网关部署算法、负载感知的路由度量和多路径流量分配策略三方面研究无线Mesh网的流量负载均衡问题。2.4.1 网关部署算法无线Mesh网的网络设计中，需要确定在哪些位置部署网关节点，并架设有线电缆与Internet相连。由于网关节点的位置以及其所服务的终端用户数量对无线Mesh网性能有很重要的影响，