（通信与信息系统专业论文）拓扑控制在wmn吞吐性能优化中的应用研究.pdf

摘要 多接口多信道w m n ( 无线m e s h 网) 作为下一代无线网络接入的 一项关键技术，已成为了当前的研究热点。其中对网络吞吐容量的改 善问题是一项重要工作。本文针对网关部署以及网络拓扑控制对 w m n 吞吐性能的影响，做了较深入的分析并提出了相应的改进方 案。 。 针对w m n 中的流量经骨干路由器聚集后大多是通过少量网关 至因特网，容易在网关处生成网络吞吐性能瓶颈的问题，首先考虑采 用对网关和路由器作等效节点化处理，利用无线通信阴影效应的对数 正态分布模型，设计加权目标函数保证节点的连通性和覆盖率，得 到候选网关节点的位置部署；在此基础上根据网关部署的约束条件和 网络生成连通图，设计基于度权值的树集分割算法，选择出满足吞 吐需求、有较好连通性的候选节点担任网关，并采用了多网关互连的 模式解决网关间负载均衡的问题。 另外针对当前m 删的底层拓扑结构较复杂，传输干扰和功耗较 大，路由开销大且效率低等问题，设计了一个基于d e l a u n a y 三角剖 分的拓扑生成算法，以满足网络拓扑部署所需的连通性、平面性和稀 疏性等要求，达到简化w m n 的布局设置目标。同时提出一种基于节 点位置的贪婪转发路由算法，通过节点局部性监测链路缓存和可退避 转发数据的方法，解决链路节点失效或拥塞，路由回路等问题。 最后，利用网络仿真工具n s 2 在多种网络场景下对提出的树集 分割算法和联合拓扑控制和路由的叭仆i 优化策略进行性能评估。仿 真结果表明它们在网络吞吐量与资源利用率等方面较之其它协议有 所提高。 关键词无线m e s h 网，吞吐容量，网关部署，拓扑控制 a bs t r a c t m u h i i n t e r f a c em u l t i c h a n n e lw m n ( w i r e l e s sm e s hn e t 、o r k s ) i sa k e ya c c e s st e c h n o l o g y i nt 1 1 e n e x t g e n e r a t i o nw i r e l e s sn e 似o r k ， a n d b e c o m e sah o ts u b ie c ti nc u r r e n tr e s e a r c h 0 i n eo ft h e s ei m p o r t a n tw o r k s i si m p r o v et h et h r o u 曲p u tc a p a c i 妙i nt h i sp 印e r w em a k ead e p t hs t u d y o ft h eg a t e w a yd e p l o y m e n ta n dt h en e t w o r kt o p o l o g yc o n t r 0 1f o rt h e t h r o u g h p u tp e r f o r m a n c eo fw n i n c o r r e s p o n d i n g l y w ef i g u r eo u ts o m e s c h e m e st oi m p r o v et h i sp r o je c t i naw m n ，t h et r a 伍ci sa g g r e g a t e da tm e s hr o u t e ra r l dm o s to f t h e m f o n v a r d e dt o w a r d st h ei n t e m e tt h r o u 曲g a t e w a y t h u se a s i l yl e a d st oa b o t t l e n e c kf o rn e t w o r kp e r f o m a n c ea tg a t e w a y a i m e dt ot h i sp r o b l e m ， f i r s t l y c o n s i d e rt h e g a t e w a y a n dm e s hr o u t e ra st h ea l i k en o d e e q u i v a l e n t l y t h e n u s et h e l o g a r i m m - n o n n a l d i s t r i b u t i o nm o d e lo f s h a d o wa a e c ti nw i r e l e s sc o m m u n i c a t i o nt od e s i g naw e i 曲t e do b je c t i v e 如n c t i o nt og u a r a n t e et h ec o r u l e c t i v i 够a n dc o v e r a g eo fn o d e s ，a t t a i n e dt h e d e p l o y m e n tl o c a t i o no fc a n d i d a t eg a t e w a y ； b a s e do ft h e g e n e r a t e d c o n n e c t i v i t y 伊a p ho ft h en e 铆o r ka n dt h ec o n s t r a i n t so ft h eg a t e w a y d e p l o y m e n t ，c o n s i d e r ah e u r i s t i ct i e e - s e t p a r t i t i o na l g o r i t b a s e do n d e 伊e e w e i 曲t e dt og e tag o o dc h o i c eo fn o d e sw i t hh i 曲t h r o u g h p u ta n d b e t t e rc o n n e c t i v i t ) ，a c ta s g a t e w a yc o n f i g u r a t i o n a c c o r d i n g l y ，a d o p t a s o l u t i o no fm u l t i g a t e w a ya s s o c i a t i o nt oc o p ew i t hl o a db a l a n c i n ga m o n g t h e m i na d d i t i o n ，b e c a u s eo ft h ec o m p l e xt o p l o g yl i e smu n d e r l y i n g i n 五阻s t r u c t u r eo ft h ew m n ，a n do w i n gt ot h ep r o b l e m so fl a 玛e r t r a n s m i s s i o ni n t e r f e r e n c ea n dp o w e rc o n s u m p t i o n ，h i g hr o u t i n go v e r h e a d w ed e v e l o pat o p o l o g y g e n e r a t i o na l g o r i t h m b a s e do nd e l a u n a y t r i a n g u l a t i o nt om e e tt h en e e d so fc o n n e c t i v i 吼p l a n a ra n ds p a u r s er e q u i r e d b yt h ed e p l o y m e n to fn e t w o r kt o p o l o g y ，s oa st os i m p l i 矽t h el a y o u ts e ti n w m n a tt h es a m et i m e ，a l s op r o p o s e dag r e e d yf o n a r d i n gr o u t i n g a l g o r i t h mb a s e do nn o d el o c a t i o nt os o l v et h ep r o b l e m sh a p p e n sw h e n l i n kf a i l u r e so rn o d ec o n g e s t i o n ，r o u t i n gl o o p sa n ds oo n ，b ym e a n so f m o n i t o rt i l el i m ( c a c h eo fn o d e sa n dd a t at i a n s m i s s i o nb a c k o f f i nc o n c l u s i o n ，w ev a l i d a t e da n da n a l y s e do u rs t r a t e g yi d e a sa n d a c h i e v e dac e i r t a i ni m p r o v e m e n te 疗e c tf o rt h r o u g h p u ti nd i f f e r e n ts c e n a r i o u n d e rn s 2s i m u l a t i o n k e yw o i t d s w m n ，t h r o u 曲p u tc 印a c i t y ，g a t e w a yd e p l o y m e n t ， t o p o l o g yc o n t r o l i i i 符号说明 w m nw i r e l e s sm e s hn e t 、v o r k b sb a s es t a t i o n p m pp o i n tt om u l t i p o i n t q o sq u a l i 够o fs e r v i c e c s m c as 呷! s e n s e m u l t i p l ea c c e s s 埘t hc o l l i s i o n a v 0 l d a n c e m i m o m u l t i p l e - i n p u tm u l t i p l e - o u t p u t 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 nm u l t i p l e x i n g m a c am u l t i a d ( 1 r e s sa c c e s sc o l l i s i o na v o i d t x i 之xt m s m i t r e c e i v e c dc o l l i s i o nd o m a i n m g a m u l t i g a t e w a ya s s o c i a t i o n c o m p o wc o m m o np o w e r l m s tl o c a lm i n i m u ms p a n 玎jn gt r e e c b t cs 0 n e 土a s e d d i s t m u t e d t o p o l o g y c o n t r o l a l g o n t n m r n gr e l a t i v en e i 曲b o r l l o o d 研a p h g gg a b r i e lg r a p h g a f g e o g r 印h i c a la d a p t i v ef i d e l 时 l e a c hl o w e n e 唱ya d a p t i v ec l u s t e r i n gh i e r a r c h y t s pt r e es e tp a n i t i o n i g wi n t e m e tg a t e 、v a y m rm e s hi b u t e r c b rc 0 n s t 锄n sb i tr a t e t d tt a i l o r e dd e l a u l l a yt r i 锄g u l a t i o n b g fb a c k r a r dg r e e d yf o n v o r d i n g v i 无线m e s h ( 网状) 网 基站 点对多点 服务质量 载波监听多路访问 冲突防止 多输入多输出 正交频分复用 冲突避免的多址接 入 传送接收 冲突域 多网关互连 统一功率 本地最小生成树 基于锥角的分布式 拓扑控制算法 相关邻近图 g a b r i e l 图 地理自适应算法 低功耗自适应集簇 分层型协议 树集分割 互联网关 m e s h 路由器 固定码率 修剪的d e l a u n a y 三 角剖分 可退避的贪婪转发 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：i 虱丝至垦 日期：翌卑年月上日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 日期：捌年月上日 硕+ 学位论文 第一章绪论 第一章绪论弟一早珀t 匕 伴随着社会需求的日益增长，各种无线通信应用正在向社会生活的各个领域 渗透，成为引领整个信息通信产业发展的强大动力。新一代宽带无线移动通信网 代表了信息技术的主要发展方向，并且成为已具备实施条件的国家科技重大专项 之一。由于目前各种无线技术层出不穷，业界专家普遍认为，不同无线网络从 多元竞争走向多元融合已成为无线通信发展的必由之路【2 捌。无线m e s h 网络 1 4 j ( w m n ，w i r e l e s sm e s hn e t 、) l ，o r k ) 作为新一代宽带无线接入网络模式，能够融合 现有的多种无线网络，很好的顺应了无线通信的发展趋势。随着无线网络应用的 飞速发展和网络信息需求的急剧膨胀，w m n 主干网络吞吐容量的保证逐渐成为 研究中的关键问题。本文将从网关的部署优化和引入拓扑控制的信道分配等方面 寻求提升网络吞吐能力的解决方案。 1 1 研究背景 在传统无线网络中，终端用户必须通过直接访问基站( b s ，b a s es t a t i o n ) 或接 入点( a p ，a c c e s sp o i n t ) 才能进行无线连接。要在拓展无线网络覆盖的过程中尽 可能降低接入网建设成本，就必须突破点对多点( p m p ，p o i n tt om u l t i p o i n t ) 的传 统蜂窝覆盖结构和无线局域网( w l a n ，w i r e l e s sl o c a ja r e an e t 、o r k ) 的传统热点 覆盖结构。w m n 技术作为新一代的无线接入网技术应运而生。 w m n 具有容量大、组网灵活且成本低廉等优点。与传统的无线网络不同， w m n 中的每个节点都可以转发其他节点的信息，各节点可以通过相邻节点以多 跳的方式连接到骨干网。因此，w m n 被快速商业化，并广泛应用于各种环境【5 6 】， 如宽带家庭网络、社区网络、建筑物自动控制、高速城域网和企业网等。 随着无线网络的飞速发展，网上信息急剧膨胀，导致网络资源特别是带宽资 源出现需求大于供给的现象【7 ，8 】；网上的用户也在快速地增长，他们共享着网络 吞吐容量，如何在这些用户之间进行公平的分配成为一个非常重要的问题。 在w m n 中，各个数据流在连接建立和数据传输的整个过程中都会竞争有限 的带宽资源，提高网络吞吐容量、减少流之间的干扰成为w m n 研究中的重要内 容问题，是确保用户间公平共享w m n 网络资源的关键。网络吞吐性能衰竭的直 接后果是网络中瓶颈增多，分组丢失率提高，严重后果则是网络性能降低，甚至 整个网络系统发生崩溃。w m n 的无线多跳，高误码率和射频干扰等特点，增加 了带宽问题的复杂性。如何在w m n 中对通信节点进行合理部署，形成优化的拓 硕士学位论文第一章绪论 扑结构，实现各种信息在不同用户之间公平高效地分配和传输的同时提高网络的 吞吐量，是一个极具挑战性的课题【9 1 。 1 2 国内外研究现状 w m n 作为下一代的无线宽带接入技术，其应用研究已经取得了较大发展， 北电、m o t o r o l a 、f i r “d e 等已推出了一些满足市场需要的产品和技术。但其更为 广阔的应用仍存在诸多的挑战，其中之一就是m e s h 路由器( m r ，m e s hi b u t e r s ) 和网关( i g w ，1 1 1 t e m e tg a t e w a y s ) 的位置部署，w m n 的通信节点一般都是相对静 止的，网络的拓扑结构对通信覆盖、吞吐容量及q o s 都有影响，而拓扑结构的 控制又是与功率调节和信道选择密不可分的；同时，由于w m n 中大部分的流量 都是经i g w 到因特网的，即使网中m r 都提供足够吞吐容量，也容易在i g w 处 产生瓶颈导致拥塞，网关部署问题的解决对网络性能提升也有重要作用。 目前对w m n 的研究大多集中在信道调度、路由方式、容量估计问题和性能 分析、跨层设计、资源分配管理等方面。而对w m n 网关部署和拓扑控制的研究 才起步不久，主要研究成果有： 1 2 1 网关优化对w m n 性能影响研究 在无线m e s h 网中，网关节点的分布以及连接对整体网络的性能有重要影响。 网络体系的设计包括许多问题，如：网络节点的网卡配置，m r s 和i g w s 的放置 等等。网卡配置确定着节点吞吐容量而不同的m r 和i g w 位置导致不同网络拓扑 和体系结构。因为所有因特网流量都要通过w m n 中其中一个i g w ，有可能在那 产生拥塞，即使每个m r 提供足够吞吐容量。因此i g w 的部署对网络性能有关键 影响。i g w 的部署问题包含i g w 应该放在哪里，怎样最小化i g w 的数量和 m r i g w 的路径长，同时又能满足m r 的因特网吞吐容量需求。此外，还有多网 关应用时的负载均衡问题和公平性问题。 在文献【1 0 】中，论述了网关部署的问题，包括能满足q o s 需求的最小网关数。 提出一种近乎最佳的多项式时间的递归计算最小权重支配集( d o m i n a t i n gs e t s ) 算 法，同时一致地保留了q o s 需求。每个节点无关于网络的大小而向在仅仅几跳内 的附近网关发送。要优化性能，w m n 要划分成若干不相交的簇，包括所有网络 的节点。在每个簇内，簇头作为网关，连接到有线骨干。文献【1 1 】中，因为网关 节点易成为网络中的瓶颈，因此利用排队论的模型来对网关的延迟和吞吐量进行 分析。根据一个概率随机排队模型m d 1 ，分别得到线性拓扑和格状拓扑下网关 的瓶颈延迟和吞吐量。文献【1 2 仲基于大多数无线m e s h 网的传统模型中，都是移 动设备只通过一个可用网关连接至骨干。本文提出了一个可替换模型一多网关连 2 硕十学位论文第一章绪论 接模型m g a ，移动设备允许通过不止一个的网关连接。这将比单连接模型有更 好的容量，公平性，多样性和安全性。文献【1 3 】中，从空间多样性的角度，考虑 通过减轻干扰，提升w m n 的网络容量的问题。本论文主要关注在与因特网接入 的网关节点上的下行流传输上，在基于接收信号强度的测量上，构建一个虚拟协 调系统来确定有最小流间干扰传输的路径集。基于不干扰路径集上，网关节点再 确定其要调度传输的不同连接的帧顺序。这种方法只需要较小的网关处节点代码 的修改，并不需要另外的硬件支持。文献 1 4 】中，作者提出了一种运行于w m n 中的q m e s h 用户网关分配框架。可以动态管理网关处分配。q m e s h 可以为每一 移动用户管理两类决策1 ) 何时在两个网关间切换2 ) 选择哪个网关进行迁移。 q m e s h 管理网关切换是通过一个透明运行在m e s h 中的低开销的信号协议来实现。 它监视应用流的q o s 以确定切换时间，探测随后进程中的q o s 以选择侯选切换目 标。协议有效性的关键是它的自适应方式，执行探测1 ) 要求减轻负载相对应的距 离2 ) 要求满足q o s 的频率。 文献【1 5 】中，无线多跳网络一般表现出低公平性的特点，离网关越远的节点 容易遭受饥饿，在这个问题上大多的研究展现在公平性的概念上( 如：时间公平 性与带宽公平性；分配公平性和最大最小公平性等等) ，而很少关注到怎样才能 达到所要的公平性。本篇论文于是提出了一个基于隐反馈的网关限制机制，约束 所有的流到它们的公平性分配流量上来。文献【1 6 】中，阐述了在多跳无线m e s h 网 中为使吞吐量优化的网关放置问题。提出了一个基于网格的，使用跨层吞吐优化 的网关部署方法。这个方法也可以扩展到多信道多射频下的网络。基于网格部署 模式的就是，首先划分整个部署区为口6 个网格。只把网关放在网格的交叉点处。 尽一切可能将这k 个网关部署联系起来，有g 。6 个。然后以一定算法评估其中具 最大吞吐量的连接。文献【1 7 】论文提出了一种域分割模式来达到一种在负载均衡 和域间移动性的折衷以减少主机移动带来的负面影响。构建一个负载均衡的方式 在i g w s 中的负载分布和m s s 的因特网移动性间提供一个折衷。这种方式不仅平 衡域间流量负载而且相应的执行适当的移动性操作以支持合意的域间移动。有效 减轻由于域间移动引起的负面影响。 1 2 2w m n 中拓扑控制对吞吐性能影响研究 拓扑控制在无线网络研究中的重要性：首先，拓扑控制是一种重要的节能技 术；其次，拓扑控制保证覆盖质量和连通质量；再次，拓扑控制能够降低通信干 扰、提高m a c 协议和路由协议的效率、为数据融合提供拓扑基础；此外，拓扑 控制能够提高网络的可靠性、可扩展性等其他性能。合理的网络拓扑结构是w m n 进行高效路由和调度的前提，是优化和平衡网络整体性能的基础。总之，拓扑控 硕七学位论文第一章绪论 制对网络性能具有重大的影响，因而对它的研究具有十分重要的意义。 文献【1 8 】提出了一个基于簇的多径拓扑控制和信道分配算法( c o m t a c ) ，该算 法对信道分配和拓扑控制功能进行分开设计，从而减少了流冲突，使用基于簇的 方法解决了全局同步操作问题保证了网络的连通性，同时以少量代价获得了广播 功能支持，但该文献只考虑到了信道分配的一个方面。文献【1 9 】提出了一种联合 拓扑控制和路由( j t c r ) 协议用于多接口多信道无线m e s h 网，以同时利用信道的多 样性和空间复用，通过分布式的方式协调节点的发射功率、网卡的信道分配及多 个节点间的路由选择。文献f 2 0 】提出首先形成局部拓扑结构，期望通过对局部拓 扑的研究，找出什么样的局部拓扑才具有好的网络性能，进而为拓扑控制策略提 供明确的控制目标，然后形成全局拓扑。但是，如何实时获取拓扑控制所需要的 网络状态信息以进行拓扑结构的动态自适应调整的研究成果较少，使得结合拓扑 控制进行联合优化调度和路由的进一步研究受到了相应的制约。 文献【2 l 】认为通过功率控制减小发射半径和通过睡眠调度减小工作网络的 规模，在节省能量的同时，可以在一定程度上提高网络的吞吐能力。文献【2 2 提 出了一种基于节点度算法的基本思想是：给定节点度的上限和下限，每个节点动 态地调整自己的发射功率，使得节点的度数落在上限和下限之间。但是，基于节 点度数的算法一般难以保证网络的连通性。文献【2 3 】基于邻近图的功率控制算法 的基本思想是：设所有节点都使用最大发射功率发射时形成的拓扑图是g ，按照 一定的邻居判别条件求出该图的邻近图g ，每个节点以自己所邻接的最远节点来 确定发射功率。文献 2 4 提出了一种较有影响的功率控制算法，h e e d 的基本思 想是：根据对作为第一因素的剩余能量和作为第二因素的簇内通信代价的综合考 虑，周期性地通过迭代的办法实现分簇。h e e d 用最小平均可达功率( a m r p ) 作 为当某个节点被选为簇头时的簇内通信代价的度量。a m r p 是指一个簇内所有其 他节点与簇头通信所需的最小功率的平均值。y o u i l i s 和f a h m y 认为，根据a m r p 选择簇头优于根据距离选择簇头。文献【2 5 】研究了分布式自组织无线通信网的组 网问题，提出了一种充分利用网络拓扑结构信息的优化组网算法。该算法具有网 络控制节点数少、节点之间通信链路简化等优点。在组网后规定网络通信路由的 情况下，利用c s m a 作为信道传输协议，对网络中节点之间通信的吞吐率进行了 分析，在给定节点平均通信业务量的条件下，分析了整个网络的吞吐率，推导了 模型参数的估值公式。文献 2 6 认为定向天线能够提高无线网格网络( w m n ) 的空 间复用率，因而影响了w m n 的容量。用渐进的分析方法对使用定向天线的骨干 帅仆i 的容量进行了研究，分析了定向天线对容量的影响，并推导出网格路由器 平均吞吐量上限。结果表明在接入点数量达到一定的门限时，定向天线的使用有 效地增大了网络的容量。 4 硕十学位论文 第一章绪论 1 3 研究目的和意义 由于采用多跳中继的网状结构，w m n 解决了有限发射功率下覆盖范围和数 据吞吐量优化的两难问题，系统具有容量大、可靠性高、组网灵活且成本低廉等 优点，已成为下一代无线宽带接入研究的热点。因特网的爆炸式增长和无线网络 技术的快速发展对无线数据传输提出了更多的需求。对于w m n 来说，如何公平、 有效地利用带宽资源，从而满足不同终端用户多样的服务需求是至关重要的。 w m n 的共享介质、多跳的特性增加了问题解决的复杂度。 本论文的主要目标是通过对影响w m n 吞吐性能的两个方面网关部署、 节点拓扑控制的分析，提出新的网关部署优化及网络拓扑控制策略。对一给定的 w m n 网络，合理地确定网关部署方案，在满足用户通信时延、带宽以及网关相 关属性约束( 如网关的度，簇度数) 的前提下，使得网关数量最少、网关间负载均 衡以及总体通信代价最小；通过调节w m n 节点的发射功率，在保证网络的连通 性和覆盖性的同时，降低邻近互相干扰，提升节点的并发传输性能，尽可能地均 衡节点间的数据转发任务，优化网络整体性能。这些目标的实现对于突破网关的 瓶颈，提高w m n 的吞吐容量，解决无线多跳通信节点间的公平性问题，满足网 络中不同q o s 要求和推动w m n 的应用具有重要的理论指导意义和实际意义。 1 4 主要研究内容 本论文致力于w m n 吞吐性能的改进研究，主要关注于业界较少研究的两个 方面网关的部署优化、网络的拓扑控制。针对当前的一些网关部署所带来的 网络覆盖连通问题，负载均衡和网关瓶颈问题，经济部署与w 川吞吐容量扩充 的矛盾问题，提出一种基于度权值的树集分割网关部署和优化算法；并针对传 统网络部署不能很好的适应动念网络拓扑的变化，结构复杂，路由开销大，效率 低等问题，设计一种基于位置的联合拓扑控制和路由的策略。论文的研究内容主 要包括以下几个方面： ( 1 ) 网关部署和拓扑控制对w m n 网络吞吐性能的影响 给定一个二层的w m n 模型，在满足节点部署的覆盖性和连通性要求下，从 定性和定量两方面考察不同网络拓扑结构( 随机的、规则的、规则下混沌的) 对吞 吐性能的影响，并分析网关处产生的瓶颈问题和“流不公平性 问题，以期找到 解决问题的方案。 ( 2 ) 基于度权值的树集分割网关部署 首先对网关和路由器作等效节点化处理，利用无线通信阴影效应的对数正 态分布模型，设计加权目标函数保证节点的连通性和覆盖率，得到候选网关节点 硕十学位论文第一章绪论 的位置部署；在此基础上根据网关部署的约束条件和网络生成连通图，设计启发 性基于度权值的树集分割算法，选择出满足吞吐需求、有较好连通性的候选节 点担任网关设置。并给出在网关处解决“流不公平性”和“负载均衡的问题的 方案。 ( 3 ) 设计一种联合拓扑控制和路由的w m n 优化策略 在多跳m e s h 的网中，拓扑控制和路由选择间的密切交互会影响整体网络的 吞吐性能。混合型删中，由于骨干节点的静态部署和移动终端的动态分布， 不能预先设定网络的拓扑结构，只能在网络的运行中通过拓扑控制算法进行控制 和优化。平面d e i a u n a y 三角剖分为构造均匀分布的网络提供了很好的方法，我 们在此基础上设计一新的t d t 拓扑构造算法以得到能很好满足网络连通性、平 面性、稀疏性、低成本等的部署结构。继而，本文提出一个基于节点位置的可退 避的贪婪转发路由算法，充分利用前面得到的t d t 良好拓扑性能，降低路由开 销，提升路由效率，并保证在网络链路故障和拥塞时的可靠性和扩展性。 ( 4 ) 性能评估 对提出的网关优化算法和拓扑控制机制进行性能分析和仿真验证。 1 5 论文构成 论文分五章，后续章节的组织结构如下： 第二章节点部署和拓扑构成对w m n 网络吞吐性能的影响。在满足节点部 署的覆盖性和连通性要求下，从定性和定量两方面考察不同网络拓扑结构对吞吐 性能的影响，并分析网关处产生的瓶颈问题和“流不公平性 问题，以期找到解 决问题思路； 第三章一种基于度权值的树集分割网关部署和优化算法。给出一种基于 度权值的树集分割算法，选择出满足吞吐需求、有较好连通性和覆盖率的候选 节点担任网关设置。并从网关处解决“流不公平性和“负载均衡”的问题，最 后通过仿真模拟对该算法进行性能评估： 第四章联合拓扑控制和路由的w m n 优化。设计一种基于三角剖分的网络 拓扑化简算法减少构成图边的稠密性，并提出一个可靠灵活，基于地理位置 的可退避贪婪路由算法。最后通过仿真模拟和性能分析对上述机制进行评估验 证： 第五章结论与展望。对本文所作研究进行总结，同时提出后继工作的方向。 6 硕士学位论文 第二章 网关部署与拓扑控制对w m n 吞吐性能的影响 第二章网关部署与拓扑控制对删吞吐性能的影响 自从香农创建信息理论以来，无线信道吞吐容量估计就成为无线通信系统发 展的基础性研究课题之一。容量估计理论对于提高网络效率、增强网络业务保障 能力具有重要的理论价值。由于无线网状网采用了灵活的组网手段与先进的无线 通信技术，j 下确的容量估计算法能够确保异构网融合效率，增强网络的可扩展性。 但无线自组织网中众多不确定因素增加了问题的复杂性：一方面无线网信道属于 竞争信道，移动节点拓扑动态性较强，个别节点位置的变化可能会极大影响网络 容量；另一方面，分布式环境下节点之间协同计算行为较为复杂，使无线自组织 环境下网络容量估计理论遇到了很大的挑战。本章将在两个影响网络吞吐容量的 关键性问题网关部署设置和网络节点拓扑控制上对其进行较为深入的理论分 析，剖析技术难点和不足，探索出行之有效的解决方案。 2 1w m n 干扰模型和吞吐容量分析 2 1 1 干扰模型 w m n 的网络环境层面决定了算法的节点流量、拓扑和移动方式等因素。现 有算法在考虑吞吐量优化时，往往采用两种网络约束条件：( 1 ) 约定式网络约束 ( a r b i t r a r yn e t w o r km o d e l ) ：约定式约束指定网络拓扑形态和流量形态，有的模型 还对节点之间的数据交互特点进行约束；( 2 ) 随机式网络约束( r a n d o mn e t 、v o r k m o d e l ) ：随机式网络约束与约定式恰恰相反，并不限定网络拓扑和网络的流量形 态。其中，约定式约束可以根据特定的网络拓扑和流量形态提出链路调度算法， 得到较高的吞吐量。但是，约定式环境的适应性较差，一旦流量或拓扑形态发生 变化，调度算法需要根据已知的网络环境参数进行调整，本质上是一种需要动态 调整的集中式算法。随机式约束不依赖具体的网络环境，也不需要根据网络环境 参数的变化而进行调整，本质上是一种静态分布式算法。 许多研究人员根据无线自组织网的网络参数对性能的影响，对分布式无线网 络环境的容量估计理论展开研究。其中，具有代表性的是g u p t a 和k u m a r l 2 i j 所提 出的多跳无线网“逼近容量或渐近容量( a s 舯p t o t i cc a p a c 时) ”问题。所谓渐近容 量是一种理想情况，即节点数目趋于无穷的极限模型。由于无线信道具有广播特 性，需要对节点之间的干扰行为建模。 从网络层次的概念来看，网络干扰模型一方面要考虑无线信道属于物理层和 7 硕十学位论文第二章 网关部署与拓扑控制对w m n 吞吐性能的影响 媒体接入层( m a c ) ；信道的调度属于接入层，而由于跨层技术或流量公平性等因 素影响，模型也会受到应用层的影响；容量优化一般从网络层来考虑优化，并以 调度模型和干扰模型为基础；如果考虑其他因素如节能设计、跨层设计等，则需 要根据应用目标建立优化模型，因此属于应用层的范畴。本论文主要考虑物理层 和媒体接入层的干扰模型。 无线网络的干扰主要来自两个方面：一是信号干扰；二是数据干扰。信号干 扰是由于无线信道本身不稳定性和传输距离的限制导致无法接收数据；数据干扰 是由于无线信道的广播特性导致的数据碰撞。目前，容量分析模型中的干扰模型 主要考虑数据干扰。干扰模型中，一般用无向图表示双向信道，有向图表示单向 信道，也有的模型采用双向的有向图表示双向信道，以保证模型的通用性。由于 无线网状网的数据干扰模型与无线信道技术( m i m o 、o f d m ) 、无线网接入协议 ( c s m a 、m a c a ) 等技术密切相关。因此，采用不同技术体制的接入协议，其干 扰模型亦不相同。 目前，绝大多数文献按照3 种类型的干扰模型来讨论分布式环境下的网络容 量问题，分别是发送模型( t x m o d e l ) 、协议模型( p r o t o c 0 1 m o d e l ) 和发送接收( t x r x ) 模型1 27 1 ，如图2 一l 所示。 不少于2 跳 。z = = j 窿 u | v lt 1 2v 2 f 扰模型小恿图，从丘到石分刖是芨迭模型、协议模型利发送琢收筏型 图2 1干扰模型示意图 ( 1 ) 发送模型( t 。一m o d e l ) 在发送模型中，节点“能够成功向节点w 发送数据的充分必要条件是：所 有需要发送数据的节点w 都满足式( 2 1 ) 的条件。其中，吠甜，w ) 表示节点“和节点 w 之间的距离，2 0 表示容差，州z ，) 表示节点甜的接收半径。 坝甜，w 皿( 1 + ) ( 朋馏( ) + 阳馏( w ) ) ( 2 - 1 ) 模型的优点在于：( 1 ) 与目前c s m a 方式较为接近；( 2 ) 由于不存在r t s c t s 模型中“暴露终端 问题，分析结论较为接近理论上界。但是模型的缺点在于， 要求感知距离大于发送距离，需要采用功率控制的方式对发送距离和感知距离进 行调整，以适应模型的约束条件。即 吠材，w 砭( 1 + ) ( 阳馏( “) + m 缸( w ) )( 2 2 ) 8 第二章网关部署与拓扑控制对w m n 吞吐性能的影响 当，口恤默( w ) 朋甥( 甜) 时，天线感知距离在设计工艺上可能难以达到要求， 此时，模型约束条件不能够成立。 ( 2 ) 协议模型( p r o t o c o lm o d e l ) 协议模型从数据接收方角度考虑无干扰的充要条件。当节点“需要向节点v 发送数据时，节点1 ，能够成功接收数据的充分必要条件是：1 ) 节点，在节点 的 传输范围之内，即故“，v ) 婴口暇“) ；2 ) 所有数据发送节点w 都满足 项w ，1 ，眨( 1 + ) 政“，d 。 从充分必要条件来看，协议模型要求节点能够按照距离远近对数据包进行区 分，克服噪声的影响。但是对无线通信系统而言，协议模型属于理想模型，实际 系统中较难实现。另外，协议模型不适用于具有功率控制功能的网络，当节点的 通信半径不同时，协议的充要条件不能成立，协议模型的通用性不强。 ( 3 ) 发送接收模型( t 。r xm o d e l ) 发送一接收模型没有像前两个模型一样明确发送节点或接收节点，令p l _ ( 甜，d 表示一条边并且产生了一次数据发送过程( 并不明确区分节点材和节点，谁是发 送节点，谁是接收节点) ，模型无冲突数据发送的充要条件是： d ( p l ，p 2 眨2 其中，d ( p i ，p 2 ) 是指两条边p l 和p 2 之间任意两点之问的最小跳数。发送接收 模型对应于c s m c a 协议，可以是r t s c t s 的情况。发送接收模型最接近实 用情况，同时也适用于基于竞争的信道协议。但是在t d m a 体制中，由于时隙 长度是相同的，而i 玎s c t s 属于短帧，将会直接导致t d m a 的接入效率会大大 降低。发送接收模型的缺点是c s m a c a 协议依靠r t s 和c t s 报文的交互，导 致暴露终端的节点不仅不允许发送数据，也不能接收数据，模型与实际理想容量 上界之间存在偏差。 ( 4 ) 针对多信道多接口的扩展 对于多信道多接口的扩展模型，其本质上依然以发送一接收模型( t x r x m o d e l ) 为基础。文献【2 8 】提出了一种解决方案，对其进行了进一步的约束： 1 ) 不能超过最大的无线接口数目，此约束对应于式( 2 3 ) ； 2 ) 不能超过最多的信道数目，此约束对应于式( 2 4 ) ： 3 ) 不能超过每个信道所能承受的最大带宽，此约束对应于式( 2 5 ) 。 9 ( p ) 烈p ) ，e ， ( 2 3 ) j e l ) c 9 硕十学位论文第二章网关部署与拓扑控制对w m n 吞吐性能的影响 ( 2 - 4 ) ( 2 5 ) 其中舒( p ) 钒p ) 尼如) ，颤p ) 是在链路p 的信道f 上的流速率，c 永) 是在链路p 信道f 上的容量，e 是数据链路集合，o c 是j 下交信道集合以v ) 是节点，上的射频 数f 是干扰链路的集合， ( p ) 是链路p 的接受节点，f 俐是链路p 上的发送节点。 2 1 2 吞吐容量分析 这罩将主要理论分析无线m e s h 网络中基于分布式调度机制的容量问题，对 分布式网络中约定式网络和随机式网络的理论吞吐量上限进行理论建模和研究 分析，给出影响系统吞吐量的理论公式。 ( 1 ) 分布式调度机制下的m e s h 约定式网络容量分析 在确定性网络协议模型中，传输范围是确定的。假设节点石在第m 个子信 道上向节点石传输信息，则对于其他同时在该子信道发送的节点，满足如下公 式则可复用： 陬屿i ( 1 + ) 噶 ( 2 - 6 ) 其中是同信道复用时能无干扰传输时设置的保护冗余量，它和节点数量， 传输损耗特性等密切相关。如果节点x 在某时隙于某个子信道上向距离为，的 节点进行发送，那么同时隙同子信道上，周围，范围内不能进行接收。假 设有，1 个节点均匀分布在单位圆平面上，网络在丁秒共发送砌丁比特信息，源节 点和目标节点之间平均距离为z ，每个节点可以在m 个子信道的任何一组子集 上进行传输，其中第m 个子信道的吞吐量为每秒( 1 鲫纠协比特。对于业务 流量6 来说，其满足1 9 鱼玎丁，假设该业务量从源节点经过共办( 6 ) 个节点跳转到 目的节点，每跳的距离为才，依据文献 2 l 】的分析推导，分布式无线m e s h 网络 中约定式网络传输容量砌z 上界可以表示为： h z s 鱼上形石 石 ( 2 - 7 ) 从上面的公式可知，对于约定性网络来说，路由长度、传输对二维有效面积 的消耗和节点总数这三点限制了传输容量不超过d ( w 万) 比特米秒。 ( 2 ) 分布式调度机制下的m e s h 随机式网络容量分析 在无线m e s h 的随机性网络中，节点位置和业务类型都是随机的，一个节点 l o 硕士学位论文第二章网关部署与拓扑控制对、 仆仆i 吞吐性能的影响 随机且均匀分布在单位面积的平面圆上。每节点随机选择希望发送每秒m 疗) 比特 的数据到目的节点，假设随机性网络中所有节点一致，传输范围，相同，满足： ? 巧i ! 芗& l 碱l ( 1 + ) 广( 2 - 8 ) 则认为节点x 在第，z 个子信道上向节点x i 进行的发送，可以被节点成 功接收。在分布式网络中吞吐容量会随着节点数增加而减少。如果假设一个分组 数据包经过的平均距离为z ，) 是平均传输范围。那么分组数据包经过的平均 跳数不小于z 彦( 刀) ，每秒每个节点至少为其他节点生成了z n 以) 肛( 刀) 比特的业务 量，总业务吞吐量至少为z 佩0 ) 彦( 门) 比特每秒。而这疗个节点有形比特每秒的容 量，那么就要求z 烈 沙( 巧) 9 ，得到吞吐容量上界为： u 门) f 旷，( ”) 上( 2 9 ) 上式的右边随着“门) 线性增加的，这说明应该减少分组数据包经历的节点跳 数，从而减少其他节点作为中继节点的负担以增加系统吞吐量。然后上式作为 r ( 聆) 的函数是一个不可达上界，这是因为该式没有涉及到空间复用的限制：靠近 接收机的节点必须处于空闲状态来避免发生碰撞导致丢包。由于碰撞，增加“门) 引起的损失和，( 以) 呈平方关系，所以减少多跳负担和增加空间复用、频率复用的 要求是冲突的，当将两个因素联合分析时，应尽量减少玎力) 的值