（通信与信息系统专业论文）无线自组织网络流量负载均衡算法研究与实现.pdf

摘要 摘要 无线自组织网络，即a dh o e 网络，是一种网络中所有节点地位平等，并且不 需要任何中心控制节点的移动通信网络。网络流量的负载均衡( l o a db a l a n c e ) 技术，是把通信流量在多条有效路径之间尽可能平衡地分摊，以提高网络吞吐量、 优化网络效率地一种方法。 本文所研究的课题，是在分级树形无线自组织网络中实现一种负载均衡算法。 在这种特殊的网络结构中，整个网络由多个自组织子网构成，不同于自组织予网 内部的流量管理策略，本文所研究的是在子网间多条路径上的网络流量负载均衡 技术，以期尽可能地在网络层根据路径负载的实时状态，动态调整网间流量在不 同路径上的分配，并在项目特定平台下对算法进行实现和测试。 本文的主要工作包括： 1 介绍无线自组织网络，特别是分级树形无线自组织网络的结构特点，分析 无线自组织网络中的路由协议，尤其是现有的使用负载均衡技术的协议原理、适 用的网络环境以及各种协议存在的局限性； 2 结合特定网络环境的特点，对负载均衡技术进行改进，引入基于网络路径 负载感知的负载均衡方法，在分析比较现有负载感知技术优缺点的基础上，提出 适用于无线自组织网络的探测报文负载感知算法； 3 分析项目实现平台l i n u x 系统对负载均衡技术的支持，对l i n u x 网络子系 统的路由转发部分进行深入探讨，选择满足网络环境需求的负载均衡算法，并结 合网络路径负载感知技术提出完整的负载感知算法； 4 在项目平台l i n u x 系统中对算法进行实现，并在测试环境中对实现的算法 进行验证，结合测试结果分析算法对网络吞吐量和网络效率带来的影响，并总结 在l i n u x 系统中实现负载均衡策略的方法。 关键字：无线自组织网络，负载均衡，负载感知，l i n u x 系统 a b s t r a c t a b s t r a c t w i r e l e s ss d f - o r g a n i z e dn e t w o r k ，s oc a l l e da dh o en e t w o r k , i sa k i n do fs p e c i a l m o b i l ec o r a m u n i c a t i o nn e t w o r k , w h i l ea l ln o d e si nn e t w o r ka r ep e e rt oe a c ho t h e ra n d w i t hn on e e do fc e n t r a lc o n t r o ln o d e 1 1 1 cn e t w o r k1 1 a m c1 0 a db a l a n c et e c h n i q u e i sa k i n do f m e t h o dt os p l i tt h ec o m m t m i c a l i o nf l o wi n t os e v e r a la v a i l a b l ep a t h se q u a l l y , t o i m p r o v et h en e t w o r kt h r o u g h p u ta n d u t i l i z et h en e t w o r ke f f i c i e n c y , 盯垃t a s ko ft h i sp a p e ri st oi m p l e m e n tal o a db a l a n c ea l g o r i t h mi nt h el e v e l e d a r c h i t e c t u r e 仃t o p o l o g yw i r e l e s ss e l f - o r g a n i z e dn e t w o r k n l i ss p e c i a l n e t w o r k s t r u c t u r ec o n s i s t so fm a n ys e l f - o r g a n i z e ds u b - n e t w o r k d i f f e r e n tw i t ht r a 目丘cc o n t r o l s t r a t e g yi n s i d et h en e t w o r k ，t h et e c h n i q u es t u d i e db yt h i sp a p e rf o c u s e s0 1 1t h e a d m i n i s t r a t i o no fi n t e r - n e t w o r kt r a m c w h i c hb a l a n c e st h ei n t e r - n e t w o r k1 0 a do nt h e p a t hc o n n e c t i n gd i f f e r e n ts u b - n e t w o r k s 1 1 圮t e c h n i q u ed y n a m i c a l l ym o d i f i e st h e d i s t r i b u t i o no f t r a 伍co nt h ea v a i l a b l ep a t h s ，a c c o r d i n gt ot h el o a ds t a t o so f t h o s ep a t h s i nr e a lt i m e n 地m a i nt a s ko f t h i sp a p e ri n c l u d i n g ： 1 i n t r o d u c ew i r e l e s ss e l f - o r g a n i z e dn e t w o r k , e s p e c i a l l yt h ec h a r a c t e r i s t i co f l e v e l e da r c h i t e c t u r e 慨t o p o l o g yw i r e l e s ss e l f - o r g a n i z e dn e t w o r k , a n a l y z em u t i n g p r o t o c o lu n d e rt h i sk i n do fn e t w o r k , p a r t i c u l a r l yt h ep r i n c i p l eo fp o p u l a rl o a db a l a n c e t e c h n i q u e s ，a n dt h es u i t a b l en e t w o r ke n v i r o n m e n to ft h e s et e c h n i q u e s ，a n dt h e i r s h o r t a g e s 2 i m p r o v et h el o a db a l a n c et e c h n i q u ew h i l et a k i n gt h ec h a r a c t e r i s t i c o ft h e n e t w o r ki n t oc o n s i d e r a t i o n , t 脚bad e e p1 0 0 ko f t h e1 0 a db a l a n c et e c h n i q u ew i t h 辩煅o f t h el o a d0 nt h ep a t h , a f t e ra n a l y s i so ft h ep o p u l a rl o a ds e n s et e c h n i q u e ，ad e t e c t i o n p a c k e tl o a d 嗣m s ea l g o f i t h mw i l lb ed e v i s e dw h i c hi sf i t t i n g t h es p e c i f i cn e t w o r k a r c h i t e c t u r e 3 a n a l y z et h el i n u xp l a t f o r m ss u p p o r to f t h cl o a db a l a n c et e c h n i q u e , a n dh a v e ac o m p r e h e n s i v ed i s c u s s i o no f t h el i n u xs y s t e m sr o u t i n gs u b s y s t e m , m a k ea c h o i c eo f s u i t a b l el o a db a l a n c ea l g o r i t h m , a n dt h ec o m p l e t el o a db a l a n c ew i t hl o a d 副强硝 t e c h n i q u ew i l lb ep r e s e n t e d 4 i m p l e m e n tt h ea l g o r i t h mi nt h el i n u xp l a t f o r m , a n dv a l i d a t et h ea l g o r i t h m u n d e rt h et e s t i n ge n v i r o n m e n t , a n a l y z et h ee f f e c tt ot h en e t w o r kt h r o u g h p u ta n dt h e n e t w o r ke f f i c i e n c yb r o u g h tb yt h ea l g o r i t h mc o m b i n i n gt h et e s t i n gr e s u l t , a n d s u n u 姐r i z et h ew h o l ep a p e ri nt h ee n d n 摘要 k e yw o r d ：s e l f - o r g a n z e a ln e t w o r k , l o a db a l a n c e ，l o a d n 辩，l n u xs y s t e m 图目录 图1 1 图2 - 1 图3 1 图3 2 图3 - 3 图3 _ 4 图3 - 5 图3 6 图3 - 7 图4 1 图4 2 图4 3 图4 - 4 图4 - 5 图4 - 6 图4 7 图乒8 图4 9 图4 1 0 图4 1 1 图4 - 1 2 图4 - 1 3 图5 - 1 图5 - 2 图5 3 图孓4 图5 5 图5 _ 6 图目录 多级子网互联区域覆盖逻辑图3 分级树形网络级别结构图一7 分级树形无线自组织网络拓扑图1 5 探测分组时间间隔示意图1 8 负载感知探铡报文格式2 1 多径选择随机算法示意图2 4 多径选择轮流算法示意图2 5 多径选择设备轮流算法示意图。2 6 多径选择加权随机算法示意图一2 7 负载均衡控制模块系统结构图2 9 负载均衡控制模块整体流程图。3 1 网内普通节点路径探测过程流程图3 3 网内普通节点探测响应报文处理流程图3 4 网关节点对路径负载探测请求报文处理流程图3 5 探测报文数据结构3 6 n e t l i n k 消息报文一般格式3 8 多径选择n e u i n k 控制报文格式3 9 n e t l i n k 消息数据结构4 0 加权随机算法原理示意图4 1 加权随机算法路由信息数据库4 2 多径选择权值比例线结构图：4 3 多径选择算法主要数据结构一4 4 测试网络拓扑图4 5 n e t f i i t e r 主要数据结构4 8 测试软件p r t g 主界面5 0 负载感知算法测试网络流量示意图5 1 路径p a t h l 负载感知测试结果5 2 路径p a t h 2 负载感知测试结果5 2 图目录 图5 7 图5 8 图5 9 图5 1 0 图5 1 1 图5 1 2 加权随机算法注册结果5 3 路由缓存测试结果5 4 控制模块性能测试网络流量示意图5 5 未使用控制模块节点g w l 接口e 1 。h o 流量图5 6 使用控制模块后网关g w l 接口e t h o 流量图5 7 使用控制模块后网关g w 2 接口日。h 0 流量图5 7 缩略语 w l a n a p 珏i f 峭n e t k t r p r t r c r a r r a d r r a 纾? 己4 e c 皿 a b r d l a r 缩略语 w i f e l c s sl o c a la r e an e t w o r k a c c e s sp o i n t h t e m e te n g i n e e r i n gt a s kf o r c e m o b i l e a dh o cn e t w o r k i n g k e r n e lt r e er o u t i n gp r o t o c o l r o u t i n gt a b l e r o u t i n gc a c h e r a n d o ma l g o r i t h m r o u n dr o b i n a l g o r i t h m d e v i c er o u n dr o b i n a l g o r i t h m w e i g h t e dr a n d o ma l g o r i t h m e q u a lc o s tm u l t i - p a t h a s s o c i a t i v i t y - b a s e dr o u t i n g d y l l a m j ol o a d - a w a r er o u t i n g 无线局域网 接入点 互联网工程任务组 移动a d h o c 网络 核心树路由协议 路由表 路由缓存 随机算法 轮流算法 设备轮流算法 加权随机算法 等价多径 基于联合的路由 动态负载感知路由 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：丞垂盔一 醐。印年j 月哆日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：段表知导师签名： 醐：刁年s 月乡日 钐哆 第一章引言 1 1 无线自组织网络概述 第一章引言 无线自组织网络，又常称为a d h o c 网络，是一种以无线信道为物理媒介，无 中心且其中所有节点地位对等的移动通信网络。 无线自组织网络的网络结构不同于普通无线网络，我们一般提及的移动通信 网络都是有中心的，需要基于预设的网络基础设施才能运行。比如蜂窝移动通信 系统，需要覆盖服务区基站的支持；无线局域网w l a n ( v n t r e l e s sl o c a la r e a n e t w o r k ) 中，使用固定在建筑物上的接入点a p ( a c c e s sp o i n t ) 作为有线网与无 线网之间的连接桥梁。这些移动通信网络发展成熟，数据传输速率不断提高，基 本可以满足人们无线通信需要。但是缺点也显而易见，移动节点只有在预先安装 配置好的支撑节点的覆盖范围内才能通信，对于有些特殊场合，有固定中心的网 络结构就不能满足要求了。比如，在民用中，地震水灾后的抢险救灾工作，普通 移动通信网络基础设施遭到破坏，无线自组织网络可以快速建立应急网络；在某 些偏远地区，由于造价或者地理环境因素无法架设通信基础设施，还有在一些l 临 时会议中，会议完毕后就不再有通信需要的，无线自组织网络都可以灵活的满足 这些情况下通信的需要；在军事应用中，无线自组织网络本身的机动性、健壮性 和灵活性都非常适合在战场环境中快速建立高抗毁性的移动通信网络。 无线自组织网络的研究起源于军事通信的需要，已经持续了三十多年的时间。 早在1 9 7 2 年，美国d a r p a ( d e f e n s e a d v a n c e d r e s e a r c h p r o j e c t a g e n c y ，国防部 先进计划研究局) 就开始了分组无线网( p r n e t ，p a c k e tr a d i on e l w c i r k ) 项目， 主要研究应用于战场环境下数据通信的分组无线网。1 9 9 4 年，d a r p a 启动的全 球移动通信信息系统( g l o m o ，g l o b l em o b i l ei n f o r m a t i o ns y s t e m ) 项目，在已有 成果上进一步深入研究满足现代军事应用需要的、可以快速展开以及高抗毁性的 移动通信信息系统，并一直延续至今。无线自组织网络是一种特殊的移动通信网 络，网络中所有节点地位平等，没有中心控制节点，网内节点不但具有普通移动 终端所需的功能，更重要的是具有分组转发能力，对通信数据进行中继。与普通 移动通信网络相比，无线自组织网具有以下特点【l l ： 1 动态拓扑。网内节点可以任意移动，并且可以随时开机或者关机，因此网 电子科技大学硕士学位论文 络拓扑可能时刻在发生动态变化，并且变化快速随机，无法预知。 2 分布式控制。无线自组织网络中没有严格的中心控制节点，所有节点地位 平等，任何一个节点都可以随时加入和离开网络，并且节点发生故障不会影响到 整个网络的运行，具有很强的抗毁性。 3 网络结构自组织。网络的布设和展开不需要依赖任何预设的网络设施，节 点通过分布式算法协调各自的行为，各节点初始化自身后就可以交互控制信息快 速自动形成一个独立的网络。 4 受限带宽。相比有线链路，无线链路具有很多特有的干扰因素，比如信道 的共享接入、信号衰减以及噪声干扰等，这些都会显著降低无线链路的通信能力， 并且由予无线环境的变化，这种无线链路所能提供的带宽也是在发生变化的。 5 安全性差。相比有线网络，无线自组织网络由于使用无线信道和分布式控 制方式，因此更容易被劫听、遭受欺骗攻击和拒绝服务攻击。对信道加密和进行 用户认证等安全措施都是在无线自组织网络中需要特别考虑的问题。 6 能源受限。无线自组织网络中部分或所有节点都是依靠电池或者其它容易 耗尽的方式进行供电的，节点所进行的操作都应该把节省能源考虑在内。 i e t f ( i n t - n e te n g i n e e r i n gt a s kf o r c 宅，互联网工程任务组) 于1 9 9 7 年成立 m a n e t ( m o b i l ea dh o cn e t w o r k i n g ，移动a dh o c 网络) 工作组四，主要负责无 线自组织网络相关协议的标准化工作。m a n e t 工作组早期进行的研究集中在自 组织网络单播路由协议及其性能评定方面，提出了一些路由协议草案，有些协议 已经成为正式的r f c ( r e q u e s t f o r c o m m e n t ，请求评论) 文档。适用于自组织网 络的路由协议一类继承有线网络中路由协议的特点，依据表驱动的思想，周期性 的进行路由更新维护，另一类针对无线自组织网络特点提出新的方法，其中最重 要的是按需驱动的路由协议，只在源节点有通信需要的时候才启动路由发现的过 程。 1 2 网络流量负载均衡技术概述 网络流量的负载均衡，基本原则是要达到每条有效路径所分摊的流量相同， 当然，现实网络申要做到每条路径负载完全相同是不实际的，只能尽量靠近这种 理想状态。如果某条路径的负载过重，就需要转移一部分流量到负载较轻的路径 上。在避免路径过早拥塞的同时，可以提高网络出口的转发速度，从而达到提高 网络吞吐量的目的。但是各个路径传输的数据瞬息万变，负载情况时刻在发生变 2 第一章引言 化，一条负载较重的路径，可能一段时间后就通信量大幅度减少，此时网络中的 负载均衡管理应该提高该路径的流量分配，根据路径实时的负载情况对流量分摊 做出动态的调整，这时就需要有一种实时反映路径负载状态的机制，即路径负载 感知算法。 目前的网络流量负载均衡技术的研究，尤其是无线自组织网络领域方面该技 术的研究，主要集中在同二- 网络内部多条路径的利用j 这类负载均衡技术都要与 网内路由技术相结合，以提供负载均衡算法中所需要的参数。 1 3 课题背景 本课题研究的主要内容，来源于数字化移动网络先期技术应用系统项目中的 信息传输分系统子项目部分。作为应用系统的通信基础部分，该子项目的研究重 点是基于无线自组织网络的信息传输分系统，主要集中在搭建一种可随时移动、 快速组网、自愈能力强的数据无线传输网络，为上层应用提供通信平台。 图1 - 1 多级予网互联区域覆盖逻辑图 3 电子科技大学硕士学位论文 信息传输分系统根据多级网络结构的需求，将自组织网络划分为多个无线通 信子网。每个子网具有相对的独立性，适应于由各个建制单元独立担任网络组建、 运行维护，以及建制单元内的通信。子网之间按照上下级建制关系进行互连，构 成一个与上下级建制关系相吻合的树状网络结构，使得上下级问的通信成为除子 网内通信外的最直接、传输路径最短的通信。图1 1 所示为用区域覆盖示意图表 示的具有三级结构的多级子网互连自组织网络。 各级网络除内部的自组织和通信外，还通过网间信道互连，接入到上级网络， 实现上下级网络间的互连互通，以及通过上一级网络实现同级网络间的互通。为 了提高网络的健壮性，子网间互连还应考虑多点接入问题。将网络划分成若干相 对独立的予网，有利于进行路由选择，网络控制，信道接入控制和带宽分配等。 然而，这些功能的实现与子网间共存、隔离技术密切联系，需要考虑信道、频率 等有限的无线资源在子网间合理的分配。在扩频、跳频通信体制下采用合理的信 道访问技术，既要能保证各子网公平占用信道，又要充分利用有限的频率资源， 实现子网间无障碍互联互通。为了实现子网互连，该项目通过节点控制器实现双 信道机的方式，在网络层实现不同信道之间的路由和中继，从而隔离不同的无线 通信体制，为各级网络具备独立选择适合自己的通信方式及覆盖半径提供便利条 件。 本文研究的主要内容就是在这样一种网络背景下的网闻流量负载均衡技术。 1 4 课题目标 从对项目网络环境的介绍中可以看出，在不同子网之间可能存在多个网关节 点，而该项目中网内节点在与子网外部节点通信时，仅使用多个网关节点中的一 个进行网间流量转发，不能做到充分利用多条有效路径提高传输速率，因此单个 网关节点的转发能力成为网络吞吐量的瓶颈，网络效率不高 本文所要进行的研究就是网内节点在与子网外部节点通信时，将这种网间流 量在多个网关节点之问尽可能平衡地分配，使网间流量不受限于某一个网关节点 的转发能力。由于每一个网内节点到子网外部的通信流量是异步进行的，即对任 意一个网内节点来说，网络中时刻存在着一定的背景流量，如何“平衡地”将流 量在网间多条有效路径上分配，这种分配的依据也是本文研究的重点。因此文中 提出的算法并不是简单的将流量平均在各条路径上，而需要保证在对流量分配后， 各个网问路径上负载尽可能的“平衡”，不能够一条负载过重而另外一条负载过轻， 4 第一章引言 并且要根据网间通信流量的变化，在路径负载不平衡时，动态调整流量分配使得 各条路径之间再次达到平衡状态。 1 5 论文的组织安排 本文总体安排如下： 第一章首先分析无线自组织网络结构特点和负载均衡技术，然后介绍课题的 来源背景，说明课题研究的内容与目标； 第二章从分析分级树形无线自组织网络结构的特点开始，讨论与负载均衡技 术密切相关的自组织网络路由技术，分析现有的结合了负载均衡技术的路由协议 的优点与局限性，特别是对采用各种负载感知方法的网内路由协议进行分析比较； 第三章引入适用于项目网络结构的网络层负载感知算法，并分析项目实现平 台l i n u x 系统所支持的负载均衡策略，提出完整的负载均衡算法； 第四章介绍在l i n u x 系统中负载均衡算法的实现； 第五章对实现的算法进行测试验证，说明算法对网络吞吐量和效率的影响， 以及算法适用的环境和不足之处； 第六章总结论文的主要工作，并说明有待进一步研究的问题。 电子科技大学硕士学位论文 第二章分级树形无线自组织网络与负载均衡综述 不同于一般无线自组织网络结构，分级树形无线自组织网络结构是种为了 适应项目需求、符合特殊级别建制的网络结构。本章从普通自组织网络开始，分 析分级树形网络结构的特别之处，和适用于无线自组织网络的路由协议，以及采 用负载均衡技术的路由协议，并讨论现有协议的优点与局限性。 2 1 分级树形无线自组织网络 2 1 1 常见无线自组织网络结构 无线自组织网络具有两种典型的拓扑结构：平面结构和分级结构【3 】。 平面结构是最简单的一种拓扑结构，所有的网内节点地位平等，每一个节点 都需要知道到达其他所有节点的路由，所以到达任意一个目的节点都会存在多条 路径，理论上不存在瓶颈，网络具有较强的健壮性。但是无线自组织网络中节点 移动频繁，网络拓扑经常会发生动态变化，为了保证各个节点的路由信息正确性， 就需要交互大量的路由控制信息。 分级结构中，网络被划分为簇。簇就是一个小规模的网络，包含一个簇头和 若干个簇成员，整个网络以簇为子网组成。每个簇中的簇头形成一个高一级的网 络，在高一级的网络中，又可以再次分簇，形成更高一级的网络，直至最高级。 在这种分级结构中，簇头节点负责不同簇之间数据的转发，簇成员节点功能简单， 只需要知道本簇内所有节点的路由，目的地为其他簇内簇成员的数据交给簇头节 点即可，由于不需要维护复杂的路由信息，大大减少了网络中路由控制信息的数 量。簇头节点可以预先指定，或者使用选举算法在簇成员中选举产生分级结构 的网络结构灵活多变，具有很好的扩展性和很强的抗毁性，缺点是维护分级结构 需要节点执行簇头选举算法，簇头节点可能成为网络瓶颈。 无线自组织网络两种典型的拓扑结构各自的特点决定了其适用环境，在网络 规模较小时，可以采用简单的平面式结构；而当网络规模较大时，分级结构就是 更合适的选择。 6 第二章分级树形无线自组织网络与负载均衡综述 2 1 2 分级树形网络结构 基于对多种无线互连模型的优点与缺点的分析，并结合信息传输系统的需求， 信息传输分系统项目中提出了一种新的无线自组织互连模型分级树形互连模 型。 根据按级别建制通信的原则，模型将传输系统按照特殊建制要求分成不同级 别的网络，各级网络内部有多个独立的同级自组织网络( 顶层除外) ，每一个自组 织网按照建制归属，通过网关节点与其上级网络实施互连，而同级网络之间原则 上不存在直接互连关系，而是通过上级网络( 一级或者多级上级网络) 实现同级 网络的互连。所以，所有子网之间呈现出树状互连拓扑，如图2 - 1 所示。 图2 - 1分级树形网络级别结构图 该图表示的是个三级系统，系统是由一个顶级、若干二级和若干三级无线 自组织网络构成的多层结构的通信网络。其中的每个网络都是由多个无线节点构 成自组织网络，既实现网络内部的信息传输，又可与上层和下层网络实现信息的 传输。这种组网结构具有如下特点： 1 分级树形互连结构。子网间的互连关系只存在于上下级网络间。同级网络 7 电子科技大学硕士学位论文 之间不实现直接互连，一方面，可以减少网络的互连关系和网关节点类型及数目， 另一方面，可以简化网间路由的设计。这种结构设计，可以较好地配合级别建制 和通信路由的规定。并且，简单的网间的互连和路由关系趋于简单、易于实现。 2 多种区域覆盖类型。顶级网络具有超长距离的无线覆盖，例如5 0 1 0 0 k m 的无线覆盖范围，及实现对整个自组织区域的覆盖，实现与二级网络的互连互通。 二级网络具有中等距离的覆盖范围，如1 0 3 0 k m 的无线覆盖范围。既实现对所 属多个下级网络的互连，也实现与上级网络的互连。三级网络具有较小距离的覆 盖，如5 i o k m 的无线覆盖范围，构成一个个独立的自组织网络，通过高层网络 实现网间互连互通。 3 多种通信体制：在分级结构的组网结构中，各个层次可结合各自的通信需 求，如信道速率、无线覆盖半径等因素，独立选择和采用适当的无线通信方式和 通信体制，如顶级网络采用覆盖范围大、通信速率高的通信体制，二级网络采用 超短波高速跳频数传电台、三级网络采用覆盖半径较小、重量轻、适宜背负的小 型扩频电台等，这为整个网络的组网带来灵活性和适用性。因为各层是多个独立 的自组织网络，层阃是上层对下层的接入，这将涉及到不同通信体制的互连。 4 移动与网络自组织：网络能够根据当前的通信环境，在各种节点地理位置 分布的情况下，由节点自动探测通信环境、发现邻居、掌握网络拓扑。通过网络 节点的自组织，自动而快速地实现组网。当节点与无线信道覆盖范围外的节点进 行通信时，由其它节点提供通信中继，从而延伸网络的通信范围，同时，提供中 继的节点不能因中继而阻塞自己的通信。网络节点可移动，发生通信拓扑结构变 化时，网络能掌握拓扑结构的动态变化，采用动态路由技术，通过路由的动态调 整，实现动态拓扑结构变化下的通信。 在分级树形无线互连模型中，子网间的互连转化为上下级网络间的接入互连 问题。其互连关系是有多个子网与一个上层的子网的互连。层间的互连具有两个 方面的内容：物理互连和逻辑互连。所谓物理互连是指不同子网间的节点能够在 物理层和链路层上互通；而逻辑互连是指上、下层网络问在网络层建立其映射关 系，从而实现真正意义上的自组织。 2 2 无线自组织网络路由协议 相比有线传输方式，无线自组织网络使用的无线信道所处的电磁环境复杂， 无线信道误码率高，并且信道数据速率低，这些特点都限制了有线网络上成熟的 8 第二章分级树形无线自组织网络与负载均衡综述 路由协议在无线网络中的应用，而i e t f 下的m a n e t 工作组，主要负责适用于 无线自组织网络的相关路由协议的标准化工作。 2 - 2 1 无线自组织网络常用路由协议 针对无线自组织网络的特性提出的路由协议，作为无线自组织网络的关键技 术，引起了广泛的关注： m t f 的m a n e r 工作组专注于无线自组织网络路由技术 的研究，提出了许多协议草案，如d s r 4 1 ，a o d v 【5 1 等路由协议。根据路由触发 原理，目前路由协议大致可以分为先验式( p r o a c t i v e ) 路由协议、反应式( r e a c t i v e ) 路由协议和混合式路由协议3 种。 先验式路由协议又称为表驱动( 1 a b l e - d r i v e n ) 路由协议，类似于传统的路由 协议，每个节点维护张到达网内所有其他节点的路由表，对于发送到任意节点 的数据包，立刻就可以通过查找路由表找到路由信息。先验式路由协议通过周期 性的发送路由通告报文，主动发现路由，保证所维护路由表的实时性与正确性 但是对于网内节点移动频繁的情况时，特别是规模较大的网络，就需要传输大量 的路由控制报文，使得路由表能够及时更新，删除过时失效的路由信息，维护正 确的网络拓扑。 先验式路由协议优点是转发数据包时延小，缺点也显而易见，需要大量的控 制信息交互，占用宝贵的无线链路资源，尤其是大规模网络中节点移动频繁时， 路由协议收敛代价高昂且速度缓慢，所以，先验式路由协议适用于小规模网络。 常见的先验式路由协议包括d s d v ( d e s t i n a t i o n - s e q u e n c e dd i s t a n c ev e c t o r ，目的 节点序列距离向量) ，w r p ( w i r e l e s sr o u t i n gp r o t o c o l ，无线路由协议) 和h s r ( h i e r a r c h i c a ls t a t er _ o u t i n g ，分级状态路由) 等路由协议。 反应式路由协议又称为按需( o n - d e m a n d ) 路由协议，是种在需要时才发 起路由建立过程的路由协议。在网络初始化时，节点并不知道整个网络的路由信 息。当源节点有发送到目的节点的数据时，源节点发起到目的节点的路由查找过 程，在获得准确的路由后，源节点才开始发送数据的过程。所以，节点保存的路 由信息可能仅仅是整个网络的一小部分，而不是整个网络的拓扑。 反应式路由协议所需要的控制信息少，占用更少的无线链路资源，但是由于 发送数据前的路由建立过程耗时，肯定会带来额外的数据发送的延时。所以，反 应式路由协议不适合实时性要求高的情况常见的反应式路由协议包括d s r ( d y n a m i cs o u r c er o u t i n g ，动态源路由协议) 和a o d v ( a dh o eo n - d e m a n d 9 电子科技大学硕士学位论文 d i s t a n c ev e c t o r ，a dh o e 按需距离向量路由协议) 。 2 2 2 分级树形网络结构中的网内路由协议 结合超短波自组织网络拓扑结构变化慢、网络直径较小、链路层可给出局部 拓扑结构的特点，基于超短波信道的自组织协议采用o s p f 算法可取得较好的性 能：节点链路层已经掌握了各自为中心的网络拓扑结构，部分信息的汇集就可获 得网络的拓扑结构( 邻居关系的相容和互补关系) 。而且，网络直径较小，无需额 外的开销，位于网络“中心”位置的节点几乎可以随时给出网络的拓扑结构信息。 当网络的拓扑结构没有发生变化时，网络层已不需要再周期性的与邻居节点发送 h e l l o 消息沟通了，因为链路层已经完成了这一功能，并且比网络层自己产生h e l l o 更“及时”可靠。当网络拓扑结构发生变化时，无需网络层的探测，链路层可直 接触发网络层产生相应动作。而且超短波信道的网络直径不大，拓扑结构变化的 扩散可以很快完成。 2 2 3 分级树形网络结构中的网问路由协议 在分级树形自组织网络中，节点的移动、网关的移动、子网的移动和网关改 变等都可以使自组织网络的拓扑发生变化，这种拓扑的变化不仅发生于子网内部 也存在于子网问，在网内自组织发生变化的同时也影响了子网间的自组织。在现 有的自组织网络的研究的各种文献中，基本上都没有涉及网间自组织的概念，这 些问题不仅是分级树形自组织网络的特殊问题，在无线网络的取得了长足发展的 今天，新的无线网络还在不断涌现，自组织网络的网间自组织问题已经凸现出来， 而相应的研究工作还未真正开展起来。 一一 分级树形自组织网络中的每一级的子网内都有自己内部的自组织协议和路由 算法，但网间组成的结构上发生的拓扑结构变化，以及由此引起的网问路由变化， 超出了网内自组织协议的作用范围，需要一个作用于全网范围的自组织协议，即 网间自组织路由协议。网间自组织协议工作在子网内部自组织协议之上，负责建 立和管理子网间互连的拓扑结构，子网的移动和网间拓扑结构的变化，最终形成 网问路由和中继。网间互连的形成的拓扑结构远比节点间的拓扑结构复杂，子网 移动和节点移动对拓扑结构的影响和对路由的影响变得更加难以把握。 层次、树形网间互连结构上的网问路由是一种简单路由。基本的路由方式是： 子网内部的路由在子网内部实现、子网间的路由由网关利用树形拓扑结构的特点 第二章分级树形无线自组织网络与负载均衡综述 实现。同级子网间的通信，将通过上级子网中继来实现，满足通信路由的需要。 该树形网间路由是一种基于上级子网的路由，利用“无线移动自组织互连网技术 及实验系统研制”项目中提出的核心树自组织动态路由协议( k t r p ，k e r n e l t r e e a o u t i n gp r o t o c 0 1 ) 思想，加以扩展构成的网问路由算法。其基本算法是；每一级 的子网需掌握接入到自已的下级子网、网关位置的部分路由信息。以及上级网关 位置信息，在网间实现中继和路由。网关节点感知子网的接入、收集子网的路由 信息，向上级网关、上级子网的内部节点通告。子网内部的节点通过自组织协议 在子网内部向其它所有节点扩散该子网路由信息。 2 3 使用负载均衡技术的路由协议 对无线自组织网络中的路由协议的研究，正如前文对网问路由协议的分析中 指出的那样，基本上都是集中于网内部分，所讨论的负载均衡技术，也是局限于 网内节点之间。无线自组织网络内部节点移动频繁，针对内部节点的负载均衡算 法就需要考虑时常发生变化的有效路径，而分级树形网络结构中的网关节点相对 稳定，尽管存在这样的不同，对适用于网络内部的负载均衡方法以及路由协议的 研究仍然值得网间负载均衡算法借鉴。 进行负载均衡控制前需要对网络中有效路径已有负载进行判断，做为控制流 量分割比例的依据。而测量的方式基本可以分为两大类：基于链路层的和基于网 络层的。基于链路层的方式需要涉及底层网络设备驱动模块的操作，因为要得到 网络接1 2 1 发送、接收队列信息，或者是路径的基本状态信息；而基于网络层的方 式不需要链路层的参与，所有路径探测工作都在网络层完成，由于负载均衡控制 一般在网络层实现，这种方式简化了实现过程，但也有其难以回避的难以达到实 时性的问题。接下来通过对几种典型的协议进行分析比较，说明各种方式的优缺 点。 2 3 1 典型负载均衡路由协议 a b r ( a s s o c i a t i v i t y b a s e dr o u t i n g ，基于联合的路由) 算法【6 l ，是一个较早把 路径上的负载作为路由选择度量值的算法，但是a b r 算法仅仅利用经过节点的 路由数量来衡量负载，并且作为次要的度量值。a b r 算法没有一个准确测量路径 负载的方法，未曾考虑每一个数据会话的多种流量负载，而且也没有把路径负载 看作路由选择过程中的重要因素。 电子科技大学硕士学位论文 d l a r 基于流( p e rf l o w ) ：以源与目的m 地址对作为区别业务流的唯一标识， 属于相同源和目的m 地址之间的流量都会选择同一条路径； 基于连接( p e rc o n n e c t i o n ) ：即使是在相同的源与目的节点之间，每一次 建立新的连接时，都会重新选择下一跳节点。用于区别连接的标识符被称为5 位 组，包括源1 1 、目的i p 、第四层协议、第四层协议的源端口和目的端口； 第三章基于负载感知动态负载均衡控制模块的设计 基于分组( p e rp a c k e t ) ：基于分组的方式是一种最简单的方式，对于每一 个分组都将进行一次路径的重新选择，即使是在同一个连接的通信中，每一个分 组选择的路径都可能不一样。 三种方式的优缺点明显。基于流和基于连接的方式适合面向连接的第四层协 议，比如t c p ：基于分组的方式适合无连接的第四层协议，比如u d p 。基于流的 方式只能用源与目的m 地址对进行业务流区分，对相同源和目的节点之间多种上 层应用程序的通信不能在多条路径上分摊流量，对于两个节点之间进行多种业务 交互时提升网络性能缺乏灵活性；而基于分组的方式首先不适用于使用t c p 通信 的上层程序，会因为到达的分组乱序极大的降低t c p 的性能，而且这种局限于使 用u d p 的方式对于每一个分组都进行一次路径重新选择的过程，无疑要比另外两 种方式更加消耗本地资源，对于依靠电池供电的移动节点，相比其它两种方式就 存在过分耗能的缺点。 对于一次通信，l i n u x 会先查看路由缓存中是否有匹配项，如果有，则直接 对数据进行路由处理；如果没有，l i n u x 把在路由表中查找到的匹配项添加到路 由缓存中，以便于下一次对到该目的地的数据转发时，不用再次查找路由表。 对于2 6 1 2 之前的内核版本，对数据包路由时，一旦在路由缓存中找到对应 的匹配项，l i n u x 网络子系统便不会继续到路由表中查找。这对于相同应用程序 发送的数据，每次在查找了路由缓存后就找到了匹配项，然后路由转发出去，甚 至没有进一步的在路由表中进行查找，自然不必说在路由表中多条到达目的地路 径上进行负载均衡。所以在l i n u x 系统构建的路由器中实现负载均衡，应该是把 流量分摊策略应用于路由缓存表，而2 6 1 2 以后的内核版本才真正实现了对缓存 表负载均衡策略的应用。 3 4 2l i n u x 系统缓存多径选择策略 l i n u x 系统2 6 1 2 版本以后的内核提供了对四种基于路由缓存的负载均衡策 略的支持。 1 随机算法( r a n d o ma l g o r i t h m ) 。随机算法是一种最简单的算法，该算法 在多条路径中进行随机选择例如图3 -