（电磁场与微波技术专业论文）无线mesh网分布式信道分配技术的研究.pdf

南京邮电大学 硕士学位论文摘要 学科、专业：工学电磁场与微波技术 研究方向：无线通信与电磁兼容 作者：2 0 0 7 级研究生刘跃 指导教师：朱洪波 题目：无线m e s h 网分布式信道分配技术的研究 英文题目：r e s e a r c ho nt e c h n o l o g i e so fd i s t r i b u t e dc h a n n e la s s i g n m e n t i nw i r e l e s sm e s hn e t w o r k s 主题词：无线m e s h 网，网络容量，分布式信道分配 k e y w o r d s ：w i r e l e s sm e s hn e t w o r k s ，c a p a c i t y , d i s t r i b u t e d c h a n n e l a s s i g n m e n t i 、 摘要 多接口、多信道技术是提高无线m e s h 网性能的重要方法，而无线接口上的信道分配 问题是影响无线m e s h 网性能的关键。为了有效利用信道资源，必须设计合理的信道分配 算法，在保证节点间连通性的同时提高网络的吞吐量。 本文首先对无线m e s h 网容量和节点间连通性做了数值分析，通过与仿真结果的比较 分析证明了数值解的有效性。随后本文提出了两种适用于多接口、多信道无线m e s h 网的 分布式信道分配算法。首先提出了一种不区分链路的分布式信道分配算法b d c a ( b a c k b o n e a s s i s t e dd i s t r i b u t e dc h a n n e l a s s i g n m e n t ) ，该算法选取吞吐量和时延作为性能标准，主要分 为随机分配和辅助分配两个步骤。在随机分配中，每个节点随机选择信道，可能会造成两 个邻接点由于没有公共信道而失去连接，为了保证网络的连通性该算法采用了辅助分配。 利用仿真软件n s 2 验证了该算法可以有效提高网络性能，在与集中式信道分配方案的对比 中证明了该算法的可行性。随后针对区分链路的情况，本文提出了一种基于链路速率的分 布式信道分配算法d r d c a ( d a t ar a t eb a s e dd i s t r i b u t e dc h a n n e la s s i g n m e n t ) 改善网络性 能。该算法将低速单跳路径转变为高速多跳路径，使得无线m e s h 网中的流量可以同时在 不同的高速信道中传输。仿真结果表明，该算法在包投递率和端到端时延方面都有较好的 改善。 关键词：无线m e s h 网，网络容量，分布式信道分配 a b s t r a c t t h ed e p l o y m e n to fm u l t i i n t e r f a c em u l t i c h a n n e li nw i r e l e s sm e s hn e t w o r k s ( w m n s ) i sa p r o m i s i n ga p p r o a c ht oi m p r o v et h ep e r f o r m a n c e h o w e v e r ，t h ea s s i g n m e n to fc h a n n e l st ot h e r a d i oi n t e r f a c e si sc r i t i c a lt ot h ep e r f o r m a n c e t oe f f i c i e n t l yu t i l i z et h ea v a i l a b l ec h a n n e l s ，a p r o p e rc h a n n e la s s i g n m e n ta l g o r i t h m i s r e q u i r e dt ob a l a n c et h en e t w o r kc o n n e c t i v i t ya n d i m p r o v et h ea g g r e g a t et h r o u g h p u t i nt h i st h e s i s ，m e t h o d sf o rm a t h e m a t i c a l l ye v a l u a t i n gc a p a c i t ya n dc o n n e c t i v i t yo f 删s a r ed e s c r i b e da n dt h em a t h e m a t i c a le x p r e s s i o n sa r ev a l i d a t e dt h r o u g hc o m p a r i s o nw i t h s i m u l a t i o nr e s u l t s t h e nt w od i s t r i b u t e dc h a n n e la s s i g n m e n ta l g o r i t h m sf o rm u l t i i n t e r f a c e m u l t i c h a n n e l 、7 | 矿v n sa r ep r o v i d e d f i r s t l yb d c a ( b a c k b o n ea s s i s t e dd i s t r i b u t e dc h a n n e l a s s i g n m e n t ) w h i c hd o e sn o td i f f e r e n t i a t el i n k si sp r o v i d e d t h r o u g h p u ta n dd e l a ya r et w o m e t r i c su s e dt oe v a l u a t et h ep e r f o r m a n c e t h ea l g o r i t h mt a k e st w os t r a t e g i e s ：r a n d o m a s s i g n m e n ta n da s s i s t e da s s i g n m e n t i nr a n d o ma s s i g n m e n te a c hn o d er a n d o m l yc h o o s e sa s e to f c h a n n e l sa n dt w on e i g h b o r sm a yl o s ea l le d g ed u et ot h el a c ko fac o m m o nc h a n n e l t oe n s u r e n e t w o r kc o n n e c t i v i t y , a s s i s t e da s s i g n m e n ti sp r o v i d e d t h ep e r f o r m a n c eo ft h ea l g o r i t h mi s e x a m i n e di nr e a l i s t i ce n v i r o n m e n t st h r o u g hn s 2 s i m u l a t i o nr e s u l t ss h o wt h a tb d c a s i g n i f i c a n t l yi m p r o v e sn e t w o r kp e r f o r m a n c ea n dp e r f o r m sc o m p a r a b l et o t h eb e s tk n o w n c e n t r a l i z e ds c h e m e t h e nd r d c a ( d a t ar a t eb a s e dd i s t r i b u t e dc h a n n e la s s i g n m e n t ) w h i c h d i f f e r e n t i a t el i n k sa n da s s i g nc h a n n e l sb a s e do nd a t ar a t eo fc e r t a i nl i n k si sp r o p o s e dt oa l l e v i a t e p e r f o r m a n c ea n o m a l yi nm u l t i - i n t e r f a c em u l t i - c h a n n e lw m n s b ye x p l o i t i n gm u l t i p l ec h a n n e l s ， d r d c aa l t e r sal o w r a t es i n g l e - h o pp a t ht oah i g h - r a t em u l t i h o pp a t h a sar e s u l t ，al a r g e v o l u m eo ft r a f f i c si nw m n sc a l lb es i m u l t a n e o u s l yd e l i v e r e dv i am u l t i p l en o n o v e r l a p p i n g c h a n n e l sa sw e l la sh i g h 。r a t el i n k s e x t e n s i v es i m u l a t i o nr e s u l t ss h o wt h a td r d c ao u t p e r f o r m s e x i s t i n gs c h e m ei nt e r m so fp a c k e td e l i v e r yr a t i oa n de n d - t o - e n dd e l a y k e y w o r d s ：w i r e l e s sm e s hn e t w o r k s ，c a p a c i t y ，d i s t r i b u t e dc h a n n e la s s i g n m e n t i l 目录 摘要i a b s t r a c t i i 目 录i i i 第一章绪论1 1 1 研究背景l 1 2 无线m e s h 网简介l 1 2 1 无线m e s h 网的网络架构1 1 2 2 无线m e s h 网的技术优势与关键问题2 1 2 3i e e em e s h 组网。4 1 3 论文的主要内容与组织结构5 第二章无线m e s h 网的网络容量分析7 2 1a dh o e 网络容量的研究进展7 2 2 无线m e s h 网容量的研究进展8 2 3 无线m e s h 网容量分析9 2 3 1 模型建立9 2 3 2 吞吐量与连通性分析1 0 2 3 3 仿真结果与分析。1 3 2 4 本章小结1 4 第三章无线m e s h 网的信道分配策略1 5 3 1 无线m e s h 网中信道分配问题的引入1 5 3 2 无线m e s h 网与蜂窝网中信道分配问题的比较1 7 3 3 无线m e s h 网信道分配中的关键问题1 7 3 4 无线m e s h 网信道分配方案的研究现状19 3 4 1 固定信道分配方案2 0 3 4 2 动态信道分配方案2 1 3 4 3 混合信道分配方案一2 2 3 5 本章小结2 3 第四章无线m e s h 网分布式信道分配技术的研究2 4 4 1 分布式信道分配技术简介2 4 4 2 问题引入及模型建立2 5 4 3d b c a 算法描述2 8 4 3 1 随机分配2 8 4 3 2 辅助分配2 9 4 3 3 相关讨论3 0 4 4 仿真结果3 1 4 4 1 场景建立31 4 4 2 性能指标的仿真一3 l 4 4 3 不同路由协议下b d c a 算法的分组级仿真3 3 4 5 本章小结3 5 第五章无线m e s h 网中基于速率的分布式信道分配算法3 7 5 1 问题引入3 7 i 5 2 基于速率的分布式信道分配算法3 8 5 2 1 建立生成树3 9 5 2 2d r d c a 算法的性能指标3 9 5 2 3d r d c a 算法描述4 l 5 3 仿真结果分析4 2 5 4 本章小结4 5 第六章总结与展望4 6 致谢4 7 参考文献4 8 攻读硕士学位期间发表的论文5 1 i v 南京邮电大学硕士研究生学位论文 第一章绪论 1 1 研究背景 第一章绪论 近年来无线通信技术得到了大力的发展，涌现了诸如3 g 移动通信技术、m a n e t 、i e e e 8 0 2 1 1 无线局域网等众多研究热点。无线m e s h 网( w i r e l e s sm e s hn e t w o r k s ，w m n s ) 是 一种新兴的无线网络技术，无线m e s h 网可以为移动用户提供灵活的自适应无线网络连接。 互联网业务提供商和其他终端用户能够藉此以合理的成本建立高速、可靠的无线宽带业务 接入。这种方案比传统的无线网络更有优势，包括更广的网络覆盖范围、低成本的网络安 装。现已成为自组织、自配置无线网中最具发展潜力的组网技术之一【l 】。 在技术研究方面，无线m e s h 网发展迅猛，许多高校构建了一些实验性测试平台。例 如r o o f n e t 2 】是一个由m i t 开发出来的实验性8 0 2 1 1 b g 无线m e s h 网，该网络在剑桥大学 中可以为用户提供宽带互联网接入。除了高校研究测试平台之外，一些著名的公司通过在 多个城市部署无线m e s h 网来展开研究，著名的无线m e s h 网有s t r i x 系统【3 1 、l e i d e l l 【4 】等。 在商业应用方面，无线m e s h 网的部署随着宽带互联网接入需求的增长而快速发展， 已经有互联网业务提供商( i s p ) 在城区和郊区部署了无线m e s h 网并提供宽带无线业务【5 】。 通过与其他各种无线接入技术相结合，无线m e s h 网的应用场景包括家庭宽带网络、企业 网、城域网和智能传输系统网络等。在公共安全领域，无线m e s h 网可以提供移动性、可 靠性、灵活性和高带宽支持，是满足执法机构和政府部门特定需求的最有发展潜力的方案 之一；在自动化领域，无线m e s h 网可以为构建先进的自动化系统提供高效、廉价的解决 方案【6 1 。 然而随着研究和应用的进一步深入，无线m e s h 网技术在不断进步的同时由于其自身 的复杂技术特性也带来了更多亟待解决的问题。 1 2 无线m e s h 网简介 1 2 1 无线m e s h 网的网络架构 无线m e s h 网由两种节点组成【1 】：m e s h 路由器和m e s h 客户端。m e s h 路由器除了提供 基本的路由、网关和网桥功能外，每个m e s h 路由器还具有增强的路由能力以支持m e s h 南京邮电大学硕士研究生学位论文 第一章绪论 组网功能。为了改进网络的灵活性，一个m e s h 路由器可以利用相同的无线接入技术来建 立多个无线接口，也可以利用不同的无线技术来建立多个无线接口，通过多跳方式的通信， m e s h 路由器能以较低的传输功率而达到与传统网络相同的覆盖。 m e s h 客户端必须具有m e s h 组网的功能，同时它也可以作为一个路由器。m e s h 客户 端一般只有一个无线接口，不存在网关和网桥的概念，其结构相对于m e s h 路由器简单因 而具有更高的灵活性。 m e s h 路由器构成了无线m e s h 网的网络框架，各个m e s h 客户端通过m e s h 路由器来 接入网络，并与其他m e s h 客户端直接进行m e s h 组网。与传统的a dh o e 网络不同，m e s h 网络架构引入了一种分级结构，该分级结构通过功耗不受限的专用m e s h 路由器来实现， 而传统的a dh o c 网络则是一个隔离的自配置网络。 网关路由器 ，一，一一一一一、 、 f i n t e r n e t ) 1 2 2 无线m e s h 网的技术优势与关键问题 无线m e s h 网的架构使其具备了很多技术优势，主要有以下三个方面7 1 ： 1 ) 易于多技术融合 2 南京邮电大学硕士研究生学位论文 第一苹绪论 无线m e s h 网大幅度增强了网络通信的可靠性并且易于网络融合，它可以应用到各种 无线接入技术中，同时支持多种无线射频接入技术。例如基于i e e e8 0 2 1 l 协议的w i f i 和基于i e e e8 0 2 1 6 协议的w i m a x 。通过综合的无线m e s h 网，终端用户就可以同时使用 多种无线网络，从而可以为集成各种不同的无线网络提供灵活性。 2 ) n 络性能优异 无线m e s h 网是一种动态的自组织、自配置网络，网络中的每个节点能够自动判断并 更新网络相关配置，可以实现无缝的多跳互联。基于无线m e s h 网架构而构建的网络，可 以弥补基于数字用户线的传统w l a n 架构中的很多不足之处。无线m e s h 网中的无线骨干 结构可以同时支持内部流量和外部流量，还可以支持多径传输，从而可以以更低的成本实 现更广的覆盖。由于每个节点都拥有多跳路径传输，因此无线m e s h 网具有很好的网络健 壮性，如果某个节点出现故障，无线m e s h 网可以通过其他中继节点来转发数据流量。通 过短距离传输，无线m e s h 网可以提高传输速率，从而提高功耗利用率，且相同频率的信 道还可以被两个链路在短距离内实现空间复用。 3 ) 高商业价值 无线m e s h 网可以在大范围内快速部署，其布线工程极小，从而大大减少了建网和部 署的工作量，使得无线m e s h 网可以按照更低的成本来构建网络，进行合理调整。这些都 使其具备了足够的市场竞争力。 由于无线m e s h 网的技术优势，近年来学术界以及各大通信企业对其展开了大力研究。 无线m e s h 网的独特性能对网络架构设计和通信协议的开发提出了很大的挑战，其关键技 术问题总结如下【l 】： 射频技术。近年来研究人员提出了多种改进无线网络容量与灵活性的射频技术，例如 智能天线、m i m o 系统和多射频多信道系统。虽然这些射频技术本身具有动态控制能力， 被认为是将来无线通信的关键之一，但这些射频技术本身还未成熟，它们都需要高层协议 的支持，特别是m a c 层协议与路由协议。而且由于其自身的复杂性和成本太高导致无法 在商业上得到广泛的应用。 o 延展性。已经部署的无线m e s h 网必须能够处理大型网络拓扑，同时不会大量增加网 络运行的负荷。如果没有延展性的支持，无线m e s h 网的网络性能会随着发送端和接收端 之间跳数的增加而产生显著下降。例如，路由协议可能无法获取可靠的路由路径，传输层 协议可能失去连接，m a c 层协议可能带来吞吐量严重下降。为了保证无线m e s h 网的延展 性，从m a c 层到传输层的协议都必须支持延展性。 安全性。无线局域网的安全方案近年来出现了很多，现有的一些w l a n 、a dh o c 网络 3 南京邮电大学硕士研究生学位论文 第一苹绪论 安全方案可以适当改进，以适应无线m e s h 网的要求。但无线m e s h 网架构中没有一个中心 信任授权点来分配公共密钥，造成了这些方案本身还不够成熟，不足以胜任无线m e s h 网 的需要。 移动性。在无线m e s h 网中，为了支持移动m e s h 客户端，必须设计先进的物理层和组 网技术，以应对移动用户终端经常出现的快速衰减情况。除此以外还需要低延迟切换和位 置管理算法，以提高移动过程中的服务质量。 连通性。无线m e s h 网的很多优点都来自于其连通性。拓扑控制的算法和路由协议可 以显著改善无线m e s h 网的性能。为了保证可靠的连通性，必须设计有效的网络自组织和 拓扑控制算法。 网络融合。现有网络技术在不同网络技术的融合上存在局限性，因此，为了提高无线 m e s h 网的性能并为不同厂商的产品之间提供互操作性，必须提高网络路由器中多个无线接 口的集成性能和相应网关、网桥的功能。 带宽和q o s 保证。与传统的a d h o e 网络不同，无线m e s h 网中的大多数应用都是带有 q o s 保证的带宽服务。由于无线m e s h 网提供的网络服务在可靠文件传输和实时多媒体业 务中是不同的，不同的网络服务带来了不同的q o s 需求。因此，除了端到端的传输时延和 公平性，更多的性能标准如时延抖动、总吞吐量、丢包率等必须考虑在通信协议中。 网络管理工具。为了监控整个网络的性能，并维护网络的正常运行，无线m e s h 网中 需要灵活的、可扩展的网络管理工具。无线m e s h 网的主要网络管理包括：带宽提供：安 装安全和服务质量方案；支持业务级协议；网络功能变更；计费、账单和报告。以上这些 性能在无线m e s h 网中可以自动进行管理，从而可以使无线m e s h 网实现快速部署。 无线m e s h 网的自身特性和影响其性能的关键因素带来了众多富有挑战性的难题。尽 管近年来无线m e s h 网的研究取得了一定的进展，但是仍然有众多难题亟待解决，例如： 无线m e s h 网的理论容量目前还未知：从m a c 层到传输层的各类协议仍需改进；新的网 络管理方案缺乏安全性等。 1 2 3i e e em e s h 组网 根据目标网络类型和应用需要，i e e e 目前有多个标准组织正在为无线m e s h 网开发新 的标准规范，本节简要介绍目前研究最为广泛的i e e e8 0 2 1 l sm e s h 组网的相关工作。 i e e e8 0 2 1 1 标准主要负责规范无线局域网的物理层和m a c 子层协议。i e e e8 0 2 1 1 系列的所有标准都是关于单跳通信网络的，因此这些标准不适合多跳、多信道和多射频的 4 南京邮电大学硕士研究生学位论文 第一苹绪论 网络。i e e e 成立了8 0 2 1 l s 任务组【8 】来专门解决w l a n 的多跳传输问题，专门负责研究基 于i e e e8 0 2 1 1 标准的m e s h 网络部署、配置和运行。该任务组的目标是通过定义物理层和 m a c 层协议，来对采用m e s h 组网的w l a n 实现标准化，以便在自配置无线m e s h 网拓扑 结构中提供广播、多播、单播传输。在i e e e8 0 2 1 1 s 网络中，无线m e s h 网定义为一组通 过无线链路连接的m e s h 点，这些点具有自动拓扑学习能力和动态路由选择功能。i e e e 8 0 2 1 l s 利用i e e e8 0 2 1 1 e 增强型分布式信道接入技术作为媒体接入机制的基础。增强型 m a c 是从原始的8 0 2 1 1 标准中提取出来的，与现有的w l a n 设备兼容。为了提高多跳通 信网络的吞吐性能和信道利用率，在i e e e8 0 2 1 1 s 标准中提出了m e s h 内拥塞控制和多信 道公共信道框架。通过每个m e s h 节点，m e s h 内的拥塞控制就变成了一个局部问题。在i e e e 8 0 2 1 1 s 中默认的混合无线m e s h 协议融合了被动按需路由发现机制的灵活性和主动路由机 制的高效率。 除了i e e e8 0 2 1 l sm e s h 组网，近年来i e e e8 0 2 1 6m e s h 组网也成为研究热点。目前 i e e e8 0 2 1 6 标准中发展的m e s h 模式还不能与原先的点对多点模式兼容，为此i e e e8 0 2 1 6 工作组成立了8 0 2 1 6 j 任务组，主要负责规范物理层和m a c 子层协议，以便在城域范围内 提供宽带无线服务。 1 3 论文的主要内容与组织结构 本文的主要内容如下： 首先，本文对无线m e s h 网的关键问题做了简要总结，研究了无线m e s h 网的网络容量。 通过建立简化模型，对无线m e s h 网容量做了一定的数值分析，数值解与仿真结果有着良 好的近似； 其次，介绍了无线m e s h 网中的信道分配技术。借鉴h y a c i n t h 方梨2 3 】【2 刀的思想，提出 了一种分布式信道分配算法b d c a ，仿真结果表明：随着可用信道数的增加，b d c a 算法 支持的最大吞吐量增加，平均时延逐步减小并且保持了较高的包投递率；通过比较分析说 明b d c a 算法具有良好的可行性； 最后，结合无线m e s h 网和分布式信道分配算法的特点，借助链路的优先权提出了一 种基于链路速率的分布式信道分配算法d r d c a ，通过对比仿真验证了d r d c a 算法在包 投递率和端到端时延方面的良好特性。 全文的组织结构如下： 第一章为绪论，主要介绍了论文的研究背景，简要介绍了无线m e s h 网的关键问题和 南京邮电大学硕士研究生学位论文 第一章绪论 研究进展。 第二章重点研究了无线m e s h 网的网络容量问题。首先介绍了a d h o e 网络和无线m e s h 网网络容量的研究进展，随后结合相关文献通过建立模型对无线m e s h 网容量做了一定的 数值分析，并将数值解与仿真结果做了比较分析。 第三章由无线m e s h 网的特点引入其信道分配问题，阐述了无线m e s h 网中信道分配的 目的、关键问题和设计难点。结合现有文献，对已有的信道分配算法做了分类总结。 第四章提出了一种分布式信道分配算法b d c a ，b d c a 算法不区分无线m e s h 网中的 不同链路，选取了吞吐量和时延作为b d c a 算法的性能指标，对b d c a 算法的一些关键 问题做了讨论。利用仿真软件n s 2 对b d c a 算法进行了仿真实现。考察了可用信道数和 节点接口数对网络总吞吐量和平均时延的影响。通过选取不同的路由协议考察了b d c a 算 法支持的最大吞吐量、平均时延和包投递率情况。最后将b d c a 算法与集中式信道分配方 案做了简要比较，证明了b d c a 算法的可行性。 第五章首先对具有不同速率链路无线m e s h 网的性能做了一定的分析，提出了基于链 路速率的分布式信道分配算法d r d c a 。对比仿真分析表明：d r d c a 算法可以有效改善 无线m e s h 网的性能，在包投递率和端到端时延方面都有一定的改善。 最后是对全文的总结和展望。 6 南京邮电大学硕士研究生学位论文第二章无线m e s h 网的网络容量分析 第二章无线m e s h 网的网络容量分析 无线网络包括大量相互通信的节点。网络容量分析与评估是规划设计无线网络的基础 性工作。通过对无线网络合理的建模、分析，获得影响无线网络容量的关键因素才能有的 放矢地提升网络性能。当前，随着分布式自组网在商用通信环境中的大规模实施，对这一 类网络容量的分析工作逐渐成为研究热点。 2 1a dh o e 网络容量的研究进展 迄今已有很多关于a dh o c 网络容量的研究文献。鉴于a dh o c 网络与无线m e s h 网的相关 性，关于a dh o c 网络容量的研究成果可以应用到无线m e s h 网中。本节对a dh o c 网络容量研 究中具有里程碑性质的研究文献做简要介绍。 e g u p t aa n der k u m a r 在 9 1 中推导了给定模型下a dh o c 网络容量的上下边界。主要结 论有：假设一个无线网络由随机分布的以个相同节点构成，每个节点可以在固定范围内发 送w b p s 。在没有干扰的情况下，每个节点对随机选择的目的节点的吞吐量五( 甩) 为 。( 喜) b p s ；如果将节点放置在单位圆的适当位置并选择合适的流量格式和合理的传 q n l o g r 输范围，单位时i b q 内网络的比特距离积为o ( w f 石) b p s 。因此即使在一个优化的模型中， 对一个远端目的节点的平均吞吐量也仅仅为o ( 旱) 伽。为了提高网络容量，文献【9 1 中提出 了一条重要准则：每个节点必须只和邻节点通信。为了实现这个准则文献【9 】中采用了两个 主要方案：采用中继节点可以显著提高吞吐量；节点必须分成多簇。这就是说，两个非邻 接节点间通信必须通过中继节点或者分簇。无论是a dh o c 网络还是无线m e s h 网都是分布式 系统，因而分簇与中继节点的选择都有很大的难度。 文献【l o 】指出对于一个固定的a dh o c 网络，网络性能主要受限于直接通信的长距离节点 对，因为这种情况下节点对间存在严重的干扰。这就决定了通信节点间的距离不能超过 玎 的量级，而长距离通信的节点必须通过大量中继节点，跳数的量级为刀。网络中的大多 数流量为中继流量，所以相互通信的节点实际吞吐量很小。为了克服这一限制，文献【1 0 】 南京邮电大学硕士研究生学位论文第二苹无线m e s h 网的网络容量分析 中提出了类似文献【9 】中的想法，它通过利用节点的移动性来增 j f l a d h o c 网络容量。只有当 目的节点靠近时，源节点才会发送数据包。借助节点的移动性，每个节点只与邻近的节点 通信。文献【9 ，l o 】中提出的方法只适用于相对理想的模型，它们的主要缺陷是没有合适的路 由协议支持。不同的m a c 层协议、功率控制和路由协议影响着无线网络的容量。而这些因 素在文献【9 l o 】中都被忽略了。文献【9 1 中存在另一个缺陷：理论边界的推导都是基于渐近分析。 这些结果并不能给出指定节点数目的网络的准确容量，特别是节点数目较少的情况。原因 是渐近分析中的网络规模和节点密度与任何实际大小的无线m e s h 网都不匹配。不论无线 m e s h n 女d 何部署，网络规模和节点密度都不可能无限大。文献【l o 】提出的方案也有缺陷：传 输时延相对较大并且节点可能需要很大的缓冲区。文献【1 1 】在文献【9 l o 】的基础上研究 j a d h o c 网络端到端时延对其容量的影响，得出了最大可容许时延和网络传输容量之间的一些定 量关系：端到端时延d 存在一个关键值，该值随着节点数目刀缓慢增长，比例可以用函数 ( 玎力) 近似。如果d 低于关键值，节点的移动性对网络容量影响很小。如果d 高于关键值， 网络容量将随着节点的移动性而增加，比例约为j 乃。 大量类似的研究表明：自组网的容量受到诸多因素的影响，例如，网络结构与拓扑、 传输模式、网络节点密度、每个节点所用的信道数量、发送功率等级以及节点的移动性等。 对于网络容量和以上诸多因素之间关系的清晰理解会为网络协议的发展以及网络结构的 设计提供指导。 2 2 无线m e s h 网容量的研究进展 关于a dh o c 网络容量的研究成果极大的推动了无线网络容量的研究。由于无线m e s h 网和a dh o c 网络本身的差异，a dh o c 网络容量的研究成果并不能完全适用于无线m e s h 网。 因此，无线m e s h 网还需要进一步的分析。 自组网分布式特性也给网络容量的分析带来了困难。自组网拓扑形式的任意性使得很 难获得精确的容量表达。虽然在具体网络中可能会得到网络的精确容量，但显然这种表示 的意义有限。因此，当前大部分关于自组网容量分析都用到了渐进容量来表示。而对于具 体网络而言，精确容量只是用渐进容量的常系数和低阶项进行表达。为了区别于类似a dh o c 网络渐进容量的研究成果，文献【1 2 】提出了“瓶颈冲突域”这一关键概念，利用这一概念计算 出无线m e s h 网的精确容量而非渐进分析。文中指出：第i 条链路的冲突域可以理解为在第i 条链路传送信息时必须的一组链路的集合；与对于，z 个节点的无线m e s h 网，每个节点的吞 南京邮电大学硕士研究生学位论文 第二章无线m e s h 网的网络容量分析 吐量随节点数目的增加而下降的量级为o ( 形) ；对于特定的路由协议和节点数目，可计算 得出任意节点吞吐量的上边界。 借助瓶颈冲突域这一重要概念，无线m e s h n 容量的研究得n t 快速发展，文酬1 3 】 计算了链状结构无线m e s h 网的容量。文献【1 4 1 中提出了一种新的基于环形无线m e s h 网的容 量分析方法：通过分析该模型中冲突域的最大流量负载而计算得出的网络容量的上边界为 o ( w n ) 。虽然这一结论与其他文献类似，但是该文献得出了另一个重要结论：网络容量 的上边界是传输范围和网络半径大小比值的函数。 另一方面，在无线m e s h 网容量优化方面也获得了很大进展，现有的研究主要是基于无 线m e s h n 关键因素的优化：例如时延、公平性、拓扑结构等等。文献【1 5 】中联合研究了包时 延与网络容量，得出了时延影响下无线m e s h 网容量的一些有益结论。文中分析指出网关节 点路由器作为无线m e s h 网接入i n t e m e t 的最后一跳具有很大的时延，这一特点使其成为无线 m e s h 网中最大的瓶颈。如果将无线m e s h 网分成多簇，簇间流量随着m e s h 路由器数量的增 加而大大降低。当网络中流量接近网络容量的理论上边界时，包投递时延的增幅非常显著。 文中提出通过采用多信道多射频的无线m e s h 网可以显著减少时延增加容量。此外通过加强 网关节点路由器的容量有助于提高网络容量。文献【1 6 】中提出无线m e s h n 的容量必须考虑公 平性因素，公平性因素保证了网络资源的合理利用；文中首先计算了基于i e e e8 0 2 1 1m a c 协议下无线m e s h 网冲突域的有效负荷，其后分析了公平性对网络容量的影响并提出算法计 算了无线m e s h 网的网络容量。 下面我们在上述文献的基础上，结合“瓶颈冲突域”等相关概念，分析无线m e s h 网的 网络容量。 2 3 无线m e s h 网容量分析 2 3 1 模型建立 本节分析的无线m e s h 网模型由两种节点构成：在可变边长为z 的正方形区域内，咒个 独立随机分布的m e s h 客户端；m 个均匀分布m e s h 路由器，相互间距离相等将整个网络 划分为多个正方形。所有的m e s h 路由器和m e s h 客户端有相同的传输范围，。整个无线 m e s h 网是一个多跳网络，远距离m e s h 路由器不必与m e s h 客户端直接通信，m e s h 客户端 通过多跳方式建立连接。图2 1 是系统模型的示意图。由于m e s h 路由器均匀分布，我们 只分析其中一个m e s h 路由器和与其相关的一组m e s h 客户端即可。 o 南京邮电大学硕士研究生学位论文 第二章无线m e s h 网的网络容量分析 网关节点 m e s h 路由器 m e s h 客户端 图2 - 1 系统模型示意图 网络中存在两种数据流：m e s h 路由器与m e s h 客户端间的流量；m e s h 客户端间的流量。 鉴于m e s h 客户端间的流量类似于a dh o c 网络的情况，而m e s h 路由器充当了网关节点并借此 通过多跳方式保持了网络的连通性，本节主要分析m e s h 路由器与m e s h 客户端间的流量。为 了分析的方便，我们对数据流做了进一步简化：假设所有流量由m e s h 客户端发送至m e s h 路由器，反方向的流量实质是一样的。另外，我们忽略了节点间的相互干扰和边界节点的 问题，而实际中这些因素对网络的吞吐量影响很大。仿真环境基于i e e e8 0 2 1 1 b ，采用文 献【l7 】中提出的路由协议：m f r ，该协议中m e s h 客户端选择邻节点中离m e s h 路由器最近的节 点发送数据。传输层协议为t c p 协议。 2 3 2 吞吐量与连通性分析 首先我们计算该场景中当单个m e s h 客户端节点发送数据，在传输范围，内能够与其建 立联系节点的平均数以。根据模型容易得出在面积4 内m e s h 客户端节点密度p ： 彳= ，2( 2 1 ) d ：旦( 2 2 ) p 2 一a l z z ) 力。近似等于半径为传输范围r 的单位圆内的节点数即： ? l n = 缈2 = 三= 乒一 ( 2 - 3 ) 定义转发节点刀，为任一发送数据的m e s h 客户端其邻节点中靠近网关节点的数目。根据系 统模型中节点的分布特性，粗略估算以，为的一半即： 南京邮电大学硕士研究生学位论文 第二章无线m e s h 网的网络容量分析 旷等2 寺。万j ( 2 4 ) 空间位置独立分布的节点可以用泊松分布来近似，n f 这里也用泊松分布近似。由于刀，本 身具有均值意义，因此五= 玎- r 。由此得出任一发送数据的m e s h 客户端其邻节点中靠近网 关节点的数目为七的概率为： p = 孚 5 ) 一 r戽 发送数据的m e s h 客户端无法与网关节点通信的概率，即k = 0 的概率为： p f ( o ) = e ”7 那么无法与网关节点通信的m e s h 客户端的平均值为： ( 2 6 ) = n 易= t i e 1 7 ( 2 7 ) 发送至网关节点的数据包每一跳的距离由路由算法决定，在m f r 算法【1 7 中等于邻节 点中离网关节点方向最近的距离d 。我们可以将距离源节点吐处的节点f 的连通性定义为： f l 1 p 。( f ) = ( 1 一只) 4 ( 2 8 ) 为了计算上述概率，我们计算盔的均值： 上式中，我们对 旁进行了取整近饥吼 c 争私 由此我们得到 ( 2 9 ) ( 2 1 0 ) ( 1 吆) 一而d gm d - ( 1 唱声沪南眦( 2 2 ( ，o 。一而d g r 旷而d g 】+ 。2 。2 ， ”p 矗一志m 脚 卜2 上。 p 一 ，“扑d 伊 拓p。 | i 砌 卜2 上 p d“扑， 目 撕p。 南京邮电大学硕士研究生学位论文 第二章无线m e s h 网的网络容量分析 我们可以得到平均跳数h ： 连接概率p 。和连接的节点数目为： = 阱旦d g 弓 p 。= ( 1 - p ，) 6 ( 2 1 3 ) ( 2 1 4 ) n 。= p 。r (