（通信与信息系统专业论文）无线mesh网络中拥塞控制的研究与实现.pdf

中南民族大学硕士学位论文 i 摘 要 下一代无线通信网络的设计目标是灵活方便地为用户提供互联网接入和有服 务质量保障的多媒体宽带业务。 无线 mesh网络正是为此目的而产生的一种能够提 供更大范围的无线接入新技术。但在多媒体业务特别是实时视频业务大量出现的 情况下，由于多跳、信道共享、资源有限、隐藏节点和暴露节点等原因，网络会 发生严重的拥塞现象。因此，本课题针对无线 mesh网络中拥塞控制问题展开了研 究。 针对拥塞控制中的公平性问题， 提出了一种基于公平性的的无线 mesh网拥塞 控制策略。该策略的主要思想是：在 ieee 802.11s 协议中的拥塞控制框架基础上， 结合链路层的带宽占用率和队列的占用率来监测本地拥塞状况，对拥塞进行度量， 并发送拥塞状况给上游节点或者邻居节点。上游节点或者邻居节点接到拥塞状况 后，采取根据各业务流的比例，动态的调整 aifsn 参数，达到公平的解决拥塞控 制的目的。仿真结果表明，该策略与 ieee 802.11e edca相比，在有效缓解网络 拥塞的同时，整个系统吞吐量提高了 6.3%，并且保证了高优先级业务与低优先级 业务之间的公平性，防止了“饿死现象” 。 在 ieee 802.11s 协议的拥塞控制框架基础上，深入分析了自适应速率和“效 能异常现象” ，提出了一种基于速率自适应的无线 mesh 网拥塞控制策略。该策略 的工作流程如下：本地节点根据接收到的功率大小选择可用于传输 data 帧的最 高速率，同时相应的调整竞争窗口以减少“效能异常”的影响。并且对本地节点 进行拥塞状况检测，然后通过 cts（clear to send）帧，将速率信息和拥塞状况反 馈给上游节点或邻居节点。这些节点接到根据收到的拥塞状况信息，调整发送窗 口，并按照发送窗口的大小连续发送多个数据帧，达到速率自适应的目的。仿真 结果表明,该策略与经典的 oar 策略相比，在有效缓解网络拥塞的同时，各节点丢 包率大大减少，整个系统总的吞吐量提高了 17%，并且缓解了“效能异常”现象。 关键词:无线 mesh网；拥塞控制；ieee 802.11s ；速率自适应；公平性 无线 mesh 网络中拥塞控制的研究与实现 ii abstract next generation wireless communications network designed to be more flexible and convenient to provide multimedia broadband with higher quality and qos service. wireless mesh networks is a new technology of next generation wireless communicat- ions network .it can provide a wider range of wireless access. because of multi- hop, channel sharing, limited resources and other reasons, the wireless mesh networks often happen network congestion. when there are too many multimedia services, especially real- time video services, the network congestion becomes more serious. to solve that problem, this thesis does some reach about the congestion control of wireless mesh networks. due to the serious unfairness for the low priority traffic when heavy load in wireless mesh networks, this thesis proposes an approach for congestion control strategy based on fairness. the main idea of the strategy as fellow: implementing the ieee 802.11s congestion control framework; combined occupancy rate of link bandwidth and queues to measure congestion; sending the congestion notifications to the upstream or neighbor nodes；adjusted the aifsn parameters in accordance with the proportion of the business flow. the simulation results show that the strategy is effective and feasible. it not only can smooth the network congestion, but can guarantee the fairness between various classes of priority traffic, meanwhile improve the total throughput 6.3% compared with ieee 802.11e edca mechanism, and avoid the phenomenon of starvation. due to the problem of adaptive rate in congestion control, this thesis proposes an approach for congestion control strategy for adaptive rate, which based on ieee 802.11s congestion control framework. the main idea of the strategy as fellow: the local node choose the highest frame rate in accordance with the received power and adjust the contention window to reduce the performance anomaly effect; through the cts(clear to send) frame to send congestion notifications to the upstream or neighbor nodes; adjust the sending window size to achieve the purpose of rate adaptive. the simulation results show that the strategy is effective and feasible. it not only can smooth the network congestion, but significantly reduce the packet loss rate, meanwhile improve the total throughput 17% compared with oar mechanism, and alleviate the performance anomaly. keywords: wireless mesh networks; congestion control; ieee 802.11s; adaptive rate; fairness 中南民族大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其 他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果 由本人承担。 作者签名： 日期： 年 月 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查 阅和借阅。 本人授权中南民族大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本 学位论文。 本学位论文属于 1、保密，在_年解密后适用本授权书。 2、不保密。 （请在以上相应方框内打“” ） 作者签名： 日期： 年 月 日 导师签名： 日期： 年 月 日 中南民族大学硕士学位论文 1 第 1 章 绪 论 1.1 研究背景 随着通信技术的发展，人们对更高质量、更快捷、更方便的通信网络需求的 不断提高，人们更希望不论任何地方、任何时间、任何人、任何原因、任何方式 下都能够进行快速、准确的进行通信。而传统的无线网络已经不能满足人们的需 求。因此，下一代无线通信网络的设计目标就是更高质量、更快捷、更方便的用 户提供互联网接入和有服务质量保障 qos 的多媒体宽带业务以满足用户的需求。 在无线网络发展过程中， ieee 802.11 的无线局域网( wireless local area network，wlan)和 ad hoc 网络是其中的两个非常典型的网络。无线局域网络通 过在商场、咖啡厅、车站、学校、广场等城市公众环境内安装一定数量的无线网 络接入设备( wireless access point，wap)，把一个大的场所分成很多片区，每个片 区有一个或多个 wap，然后通过有线网络把 wap 连接成一个更大的网络。但是 由于无线局域网接入设备的发射功率有限，它的覆盖范围一般都很小，大概在几 十米左右。虽然通过频展、域展等改进方法可以达到 4- 7 倍，但是范围还是很小。 而且由于建筑物、树木、气候等影响，传输的距离和传输的效果都会很差。为了 增强网络的覆盖能力，可以采用增加接入设备的方法，但是同时也大大增加了建 设成本。同时由于网络大量的接入设备，对网络的管理增加了很大的难度。而 ad hoc 网络技术却能在网络覆盖问题上提供很好的解决方案。ad hoc 网络最初是为 了满足军方的需求，具有抗摧毁性、自组织性、自愈性以及分布式技术等特点。 由于采用分布式技术， 每个节点都能够作为中心节点，可以进行数据的转发与传 输。当网络中某些网络节点收到攻击或者发生故障时，其他的网络节点还可以通 过多跳的方式达到通讯的目的，具有很高的机动性与灵活性。 但是 ad hoc 网络由 于技术复杂，不稳定的等因素，因此在民用化的道路上发展的不是很好。为了解 决更大的覆盖率，以及更高质量的接入的问题，ieee 802.11 委员会提出了一种新 的组网技术即无线 mesh网络（wireless mesh networks, wmn）又称无线网格网、 无线网状网1 。 无线 mesh网络狭义上可以看做是 wlan+ad hoc 网络， 它继承了两种网络 的优点，同时它在应用上又有很大的突破。它不是一项可以单独成系统的技术。 无线局域网、无线个域网、无线城域网、无线广域网、cdma 2000、wimax 都 有无线 mesh网络的发挥巨大作用的平台。资料表明，相对于传统的无线网络，无 线 mesh网具有更好的网络覆盖、频率效率等优点。目前，致力于无线城域网的标 准工作组 ieee 802.16 工作组已经把无线 mesh网写入标准中。3gpp 组织为 tdd 无线 mesh 网络中拥塞控制的研究与实现 2 系统定义了 odma(机会驱动多址接入， opportunity driven multiple access)协议中 也引入了 mesh的思想，进行多跳组网方面的规范2。无线网络是未来 b3g/4g的 潜在技术，具有广泛的应用前景和商业价值。 在过去的 30 多年里，网路发展迅速。随着用户用户数量的迅速增长以及新型 网络应用比如：电影，歌曲的下载、视频/语音聊天、博客、web2.0 等的不断涌现， 使得网络的流量急剧增长。其中除去传统的 www， ftp 等数据流外，还出现了 大量的实时语音、视频等多媒体数据流。当网络中有大量的数据流在无线路由器， 网关等处交汇，给网络的这些 mesh节点造成很大的负担。由于无线网络本身一些 缺陷导致越来越严重的网络拥塞问题逐渐暴露出来。就如坐车遇到堵车一样的情 况。网络上的“堵车”如同生活中的堵车一样令人恼火。治理交通拥挤是现代化 城市持续发展中必须解决的一个重要问题，同样，解决网络拥塞问题也是网络发 展中必须面临的问题。而且由于无线网络带宽的非常稀缺，更不能浪费带宽在拥 塞上，因此拥塞控制刻不容缓。本文就是在无线 mesh网路的基础上对网络的拥塞 控制进行了深入的分析，并针对拥塞控制中的公平性与速率自适应问题展开了深 入的讨论，提出了解决方案并进行了实验仿真。仿真结果表明，提出的拥塞控制 策略是有效的，实用的。 1.2 拥塞控制研究现状 由于拥塞控制的重要性，因此在有线网络和无线网络中就有大量的研究。在 有线网络与非多跳的无线网络中运用最多的就是 tcp 拥塞控制。大多数的拥塞控 制都是在 tcp 的基础上进行改进的，并有较好的效果。但是由于无线 mesh 网的 中不同的链路上的多个信道的传输会相互干扰，产生影响。在一段时间内，无线 信道的质量也会发生频繁的变化。同时，由于这种端到端的 tcp 拥塞控制要求发 送节点发送控制报文分组，这更加重了发送节点的拥塞状况，并且消耗了 mesh节 点的宝贵的能量资源。而且现在多媒体信息主要采用 udp 传输，在有线网络中， udp 造成丢包，大部分是因为网络拥塞问题，但是在无线 mesh 网络中是因为信 道的干扰、干扰、多跳等造成大量的丢包，从而导致误码率高，因此仅仅依靠 tcp 协议进行无线 mesh 网的拥塞控制是不全面的。文献3- 5表明了 tcp 拥塞控制策 略在多跳的 ad hoc 网络中不能很好的工作，效率低下。因此，人们提出了多种针 对多跳的无线 mesh网自身特点的拥塞控制策略。 文献6 引入经济学中的定价理论进行拥塞控制，通过定价函数对拥塞进行度 量。实验结果表明提高了网络的吞吐量，减少了丢包率，但是吞吐量的抖动性比 较大，这可能是由于拥塞策略中定价函数动态的调整节点的速率而导致的。 文献7 提出了 clm- tcp 的拥塞控制策略， 通过 tcp 跨层解决方案来实现无 线 mesh网的拥塞控制。实验结果表明 clm 增强了系统的传输效能。但是实现很 中南民族大学硕士学位论文 3 复杂，且作者也表明下一步要在兼容性方面进行深入研究。 文献8 通过对多信道的业务流的动态分配入手，对拥塞控制进行了分析。文 章的立足点是多信道，多发送与接收器。 文献9 通过在每个节点设置 buffer 来比较 local optimization 和 global optimization来达到最优的流的反应扩散，最终解决拥塞控制。实验结果表明，在 重负载情况下，系统的吞吐量有很大的改进。 文献10 针对 ieee 802.11的mac 层协议只适应单跳的网络的问题， 对mac 层进行修改， 提出了一种 amc 拥塞控制策略来达到解决多跳的 mesh拥塞的问题。 以上的无线 mesh网的拥塞控制都是从某一角度出发，对拥塞控制进行分析， 达到了很好的效果。当然也有些不足。为了在复杂性和性能之间取一个较好的折 中，ieee 802.11s工作组提出了一种简单的拥塞控制方案来解决无线 mesh网的拥 塞问题11。本文就是在此拥塞控制方案的基础上完成的。草案主要包括三个部分： 拥塞度量、拥塞通告、速率控制12 13 14。 （1） 拥塞度量 拥塞度量是拥塞控制的基础，只有拥塞度量实际反映了网络的状况，才能更 好的解决拥塞问题。在标准中提出了两种拥塞度量的方案以供参考。 方案一、基于队列长度的拥塞度量。 首先选定队列长度的最大值与最小值，如果队列长度高于最大值，节点将发 送拥塞通告来通知它的邻居 mesh节点。如果队列长度在下限和上限之间，节点以 概率 p 发送“拥塞通告”给上游 mesh节点。 mix max l- l p= l- l (1.1) 其中：l 是 m e s h 节点的实际的队列长度， mix l为队列的最小值， max l为队列 的最大值。 方案二、基于速率的拥塞度量。 首先通过对每个 m e s h 节点检测自身的有效的传输和接收数据速率，并且检 测两个速率的大小的不同所造成的压力。基于速率的拥塞度量的目的就是为了保 持近似于零的压力。如果这个压力明显增加，这个 mesh节点将发送拥塞通告来通 知它的上游 mesh节点，接收到拥塞通告的 mesh节点将启动速率控制机制来降低 传输速率。如果情况更为严重时，即两种速率的差值很大，说明此 mesh节点压力 很大，通过对邻居 mesh节点进行广播拥塞通告。邻居 mesh节点将根据所接收的 信息来调整传输速率，达到缓解拥塞控制的目的。 （2）拥塞通告 无线 mesh 网络中拥塞控制的研究与实现 4 拥塞通告的发送主要通过拥塞请求帧。此帧通过单播的形式发送，帧中明确 的规定了目标数据速率，上游 mesh节点发过来的速率不能超过这个值。当 mesh 节点发生拥塞时， 一般来说， 上一跳的速率已经超过了这个目标速率， “拥塞通告” 就是要把本地的拥塞状况通知给上一跳的 mesh节点， 告诉它限速用来帮助消除网 络拥塞。 速率控制机制针对每个上游 mesh节点和邻居节点的数据流进行接入分类 （access category，ac） ，这样可以分别对上游邻居和各 ac 进行流控制，有针对 性的进行拥塞控制。 （3）速率控制 ieee 802.11s 草案中提供了两种速率控制机制方案。 方案一、根据本地和邻居范围内的拥塞状况即拥塞度量的情况，动态的调整 ieee 802.11e edca参数。调整的参数可以是 aifsn 或者 cwmin，也可以两者同 时调整。 方案二、通过使用一个带有流量表的整形器。流量整形器对速率控制后的接入 分类的流量时间属性进行控制，并与“拥塞通告”中的平均数据发送速率进行比 较。如果数据包超出规定的范围，那么即使退避时间到，也不会激发数据的发送； 如果数据包符合要求，则当退避时间到就立刻发送数据。通过对数据的流进行整 形，从而达到有计划的发送数据流，达到解决拥塞控制的目的22 23 24 25。 本文首先实现了 ieee 802.11s 的拥塞控制的方案，并对拥塞控制中的公平性 问题和速率自适应问题进行了深入的分析。在研究网络拥塞时，不公平性一直是 造成拥塞，加剧拥塞的一个重要原因，是无线多跳的网络研究热点问题。特别是 对于无线 mesh网，网络拥塞造成的公平性问题尤为显得突出。 文献15 通过多跳的无线 ad hoc网络的tcp的性能进行深入的大量的仿真， 真实了多跳网络中确实存在严重的不公平性，包括水平公平性与垂直公平性。在 单个 tcp 流的分析中，由于多跳的原因，条数越多，吞吐量也会急剧减少。文中 说明了多跳的不公平性，但是没有给出解决方案。 文献16 借鉴了有线网络中的最大、最小公平性的概念。通过最大最小公平 指数来定量的评价各个业务流量间的公平性。实验结果表明减少了网络的不公平 现象。但是文中的流是指相同源节点和目的节点的数据流，有一定的局限性。 文献17 针对多跳的网络中的 mac 协议的输入与输出的公平性进行了研究， 对 mac 协议进行了改进，提出了一种混合的 mac 的思想。但是，本文仅仅从单 个层面上考虑无线信道共享的公平性，有一定的局限性。 文献18 通过利用博弈论对无线 mesh网的公平性进行了详细的分析， 提出了 一种基于公平性的路由算法。利用博弈论选择一个较好的路由，并在 omnet+ 上仿真实现。但是没有考虑到在重负载情况下，无线 mesh网络会急剧恶化。 文献19 对无线 mesh网的 tcp 公平性进行了分析， 并利用 markov链对无线 中南民族大学硕士学位论文 5 mesh网络的 tcp 性能进行建模。根据建模分析总结，无线 mesh网 tcp 公平性的 重要影响因素对改进网络的公平性有重要的知道意义。但是文章没有考虑到拥塞 控制问题。 专利20 核心思路是通过改进媒体接入控制层协议来减小和感知无线通信网 络的拥塞状况。该协议是建立在帧对帧的基础上的，并允许通过信道切换来实现 无线网络的数据业务的传输。因为在该协议中，用于无线通信网络的通信信道切 换的时间被减少到电子速率，所以虽然占用了额外的带宽，但是有效的缓解了网 络拥塞，大大提高了系统的吞吐率。缺点是没有区分接入业务的种类，各种业务 之间的不公平没有考虑。 专利21 公开了一种无线网络的二层拥塞控制方法。具体包括以下步骤：a、 当前网络节点检测自身拥塞情况，并在自身发生拥塞时，执行步骤 b；b、当前网 络拥塞节点向与自身相连的上游网络节点或邻居网络节点发送包含自身拥塞情况 的拥塞控制信息；c、接收到拥塞控制信息的网络节点根据其中包含的拥塞情况， 调整本地节点传输速率。本专利明确了拥塞的检测、信息发送以及拥塞控制的整 个过程，能够直接应用到实际网络中，如无线多跳网包括：无线网状网、移动 ad hoc 网络和无线传感器网络等，从而降低本地拥塞。 但是此专利没有很好的区分各 业务，会产生饿死现象，造成不公平。 最近几年，基于逐跳的拥塞控制22 23 24算法引起了很大的关注，特别是在 ieee 802.11s 标准提案中得以充分体现25 26 27 28。 在 ieee 802.11s 草案中提出了 一种简单的、跳对跳拥塞控制方案来解决拥塞问题。基于 ieee 802.11s 提出的拥 塞控制框架，文献29通过比较各个 mesh节点接收数据速率和发送数据的速率的 大小来检测是否发生拥塞。根据比较的结果，发送拥塞通告；文献30利用“模糊 逻辑控制” 作为拥塞检测方案，提出一种基于跳对跳的二层拥塞控制策略。文献 31引入拥塞定价理论作为拥塞检测与分配带宽的依据。文献32利用反向施压的 拥塞控制策略，达到全局的负载最优化。但是，在网络带宽有限，同时又存在多 个优先级较高的多媒体业务竞争接入时，网络的竞争环境会剧烈的恶化，系统的 吞吐量严重下降等问题。这将使低优先级业务竞争不到资源而发生“饿死现象” 。 因此，在进行拥塞控制的同时应该考虑到不同级别业务的公平性问题。 通过以上无线 mesh网的拥塞控制以及公平性问题分析， 总结他们的优点与缺 点。本文在 ieee 802.11s 拥塞控制框架的基础上，通过区分各优先级业务，动态 的分配网络带宽，达到公平的解决拥塞控制的目的，防止了“饿死现象” 。 为了达到无线 mesh网络利用率最大，应时刻监视网络，根据网络的拥塞状况 的不同，接收的 mesh节点根据信道的质量选择可用的最高传输速率，发送节点同 时同时增大转发速率。近年来国内外对基于 ieee 802.11 的无线 mesh网络进行了 大量研究。在 ieee的标准中，802.11 a /b /g分别利用不同的编码方式可支持多种 无线 mesh 网络中拥塞控制的研究与实现 6 不同的传输速率，如：802.11b 有 1、2、5.5、11mbit/s四种速率33。在多跳网络中 的速率自适应算法主要有如下成果： 文献34 提出了一种建立在能效基础上的， 动态规划的 ad hoc 网络自适应速 率方案。采用跨层的的策略，兼顾物理层的信道状态以及传输层的传输速率。实 验结果表明，相对于 rbar算法，吞吐量增加了 96%并且能量消耗减少了 130%。 文献35 提出了一种联合的自适应速率控制策略。通过联合多种策略检测信 道的方法，选择合适的下一条链路，达到自适应速率控制的目的。但是多种策略 结合，仿真的结果抖动性比较大。 文献36 采用在不同的状况匹配一个固定的速率的值，这个值是根据以前的 网络动态产生的。采用这种方法可以快速找到对应的速率，增加了速率自适应的 灵活性。但是对应的值如何确定还需要进一部的深入研究。 文献37 提出了一种基于能量控制与速率自适应的无线 mesh网的调度优化 算法。通过对每个 mesh节点的能量进行检测来进行速率自适应，最终达到网络的 最优化调度，提高网络的利用率。但是没有考虑到拥塞状况。 为了更高效率的利用网络，基于逐跳、被压的策略运用到了部分速率自适应 协议中，如文献383940。由于在多跳的无线 mesh网络中存在本地流量与转发 流量的竞争，每个 mesh节点不但和信道容量，还和邻居的节点的状况有关。但是 这些算法都没有考虑到拥塞状况41 42 43。针对这些不足，本文在 ieee 802.11s 拥 塞控制框架的基础上，对 oar 进行改进，提出一种速率自适应的拥塞控制策略， 并利用 ns2 仿真实现。 1.3 研究内容与组织结构 本文重点对现有的无线 mesh网的拥塞控制状况进行归纳总结， 并对各拥塞控 制算法进行比较深入的研究。阐述了现有拥塞控制算法的主要思想，优点与不足 之处。在了解现有的拥塞控制算法的基础上，深入研究了 802.11s 提出的拥塞控制 框架，并在此基础上结合公平性问题和速率自适应问题，提出了两种改进的拥塞 控制算法。主要的研究内容如下： （1） 实现了 ieee 802.11s 的拥塞控制框架，并针对无线 mesh网的实际情况， 分析并仿真了“饿死现象”与“效能异常现象” （2） 对 ieee 802.11s 的拥塞控制框架中的拥塞检测方案进行了改进， （3） 针对拥塞控制中的公平性问题，提出了一种基于公平性的的无线 mesh 网拥塞控制策略。该策略的主要思想是：在 ieee 802.11s 拥塞控制框架基础上， 结合链路的带宽占用率和队列的占用率来监测本地拥塞，对拥塞进行度量，并发 送拥塞通告给上游节点或者邻居节点。上游节点或者邻居节点接到拥塞通告后， 采取根据各业务流的比例，动态的调整 aifsn 参数，达到公平的解决拥塞控制的 中南民族大学硕士学位论文 7 目的。仿真结果表明，该策略与 ieee 802.11e edca相比，在有效缓解网络拥塞 的同时，整个系统吞吐量提高了 6.3%，并且保证了高优先级业务与低优先级业务 之间的公平性，防止了“饿死现象” 。 （4）在 ieee 802.11s 协议的拥塞控制框架基础上，深入分析了自适应速率与 “效能异常现象” ，提出了一种基于速率自适应的无线 mesh 网拥塞控制策略。该 策略的工作流程如下：本地节点根据接收到的功率大小选择可用于传输数据帧的 最高速率，同时相应的调整竞争窗口以减少“效能异常”的影响。同时根据本地 mesh节点的拥塞检测的结果，然后通过 cts（clear to send）帧，将速率信息和 拥塞状况反馈给上游 mesh节点或邻居 mesh节点。这些节点接到根据收到的拥塞 通告，调整发送窗口，并按照发送窗口的大小连续发送多个数据帧，达到速率自 适应的目的。仿真结果表明,该策略与 oar 相比，在有效缓解网络拥塞的同时，整 个系统吞吐量提高了 17%，并且缓解了“效能异常”现象。 全文一共分为四章，结构如下： 第 1 章 介绍论文的课题背景，阐明了课题的目的与意义。详细分析了无线 mesh网拥塞控制的研究现状，并介绍了本文的主要工作与组织结构。 第 2 章 提出了一种基于公平性的无线 mesh网拥塞控制，并用 ns2 2.29 进行 仿真实现，实验结果表明，该策略与 ieee 802.11e edca相比，在有 效缓解网络拥塞的同时，整个系统吞吐量提高了 6.3%，并且保证了高 优先级业务与低优先级业务之间的公平性，防止了“饿死现象” 。 第 3 章 提出了一种基于速率自适应的无线 mesh 网拥塞控制，并用 ns2 2.29 仿真实现。仿真结果表明,该策略与 oar 相比，在有效缓解网络拥塞的 同时，整个系统吞吐量提高了 17%，并且缓解了“效能异常”现象。 第 4 章 全面总结论文中所做的工作，并对无线 mesh网络的应用和研究前景进 行展望。 无线 mesh 网络中拥塞控制的研究与实现 8 第 2 章 基于公平性的无线 mesh 网拥塞控制 本章首先对无线 mesh网在高负载状况下的吞吐量进行分析， 发现有严重的不 公平产生，然后提出了一种基于公平性的无线 mesh网拥塞控制策略。文中详细介 绍了拥塞控制策略的描述、实现、仿真，并把改进前与改进后的策略进行对比分 析。仿真结果表明，该策略与 ieee 802.11e edca相比，在有效缓解网络拥塞的 同时，整个系统吞吐量提高了 6.3%，并且保证了高优先级业务与低优先级业务之 间的公平性，防止了“饿死现象” 。 2.1 公平性问题 在无线 mesh 网络中，由于用户终端的不断增加，业务总量也相应的增加， 网络的负载增大。特别是高优先级的语音业务与视频业务的存在，它们大量的掠 夺了网路带宽，使网络容量迅速的达到饱和，在网络的负载达到一定的程度，低 优先级的业务就无法获得网络资源，造成饿死现象，网络失去了公平性44。为了 说明该情况，本节首先对网络饱和情况下的公平性问题进行仿真分析。仿真网络 拓扑如图 2.1 所示,mesh节点 0 发送音频业务流到 mesh 节点 6，mesh节点 1 发送 视频业务流到 mesh节点 7，节点 2 发送尽力而为业务流到节点 8，节点 3 发送背 景业务流到节点 9。以上四个不同优先级的业务流都需要 mesh 接入点 4、5 进行 转发。仿真时间为 50s，带宽为 11mbit/s。 1 9 8 7 6 5 3 2 0 4 图 2.1 网络拓扑 表 2.1 仿真 mesh节点参数配置 参数名称 参数类型 channel type channel wirelesschannel radio propagation model propagation tworayground network interface type wirelessphy mac type 802_11e routing protocol dsdv 中南民族大学硕士学位论文 9 表 2.2 mesh网络物理层参数 参数 数值 slot time 12us sifs time 8us rxtx turnaround time 10us plcp data rate 4mbit/s mac length 50packets plcp header length 48bits cca time 15us propagation delay 1us basic rate 2mbit/s data rate 11mbit/s preamble length 114bits 表 2.2 所示各参数的意义如下： （1）slottime：表示时隙时间大小为 12us，用来定义各种帧之间的时间间隔。 （2）sifs time：表示短帧间间隔为 8us。 （3）rxtxturnaround time： 表示从接收到发送第 1 个符号开始，物理层所需要 的最大时间为 10us。 （4）plcp data rate：当前物理层的 plcp 头长度为 4mbit/s。 （5）mac length：mac 层队列长度为 50packets。 （6）preamble length：当前物理层的前导码长度为 48bits。 （7）plcp header length：当前物理层的 plcp 头长度为 15us。 （8）cca time：在每一时隙内接入媒体时，判断媒体是忙或者空闲所需要的最小 时间的大小为 1us。 （9）propagation delay：一个传输信号从发射点到接收点的时间间隔为 2mbit/s。 （10）data rate：传输数据帧的所采用的速率大小为 11mbit/s。 （11）plcp data rate：当前物理层的 plcp 头在媒体中的传输速率为 114bits。 仿真中设定的业务结构如表 2.3 所示。其中音频业务流优先级最高，定义为 prio_0 等级；多媒体视频流的优先级定义为 prio_1；尽力而为业务流的优先级定义 为 prio_2；背景业务流的优先级定义为 prio_345。表 2.3 中各种业务流的业务量都 比较大，属于网络负载较大的情况。 表 2.3 各业务流的参数 业 务 流 ac 数据包大小/b 数据包间隔 /ms cwmin cwmax txop prio_0 172 30 7 15 0 prio_1 1080 17 15 31 0 prio_2 1500 12 31 1023 0 prio_3 1500 8 31 1023 0 无线 mesh 网络中拥塞控制的研究与实现 10 仿真后，四种业务流的吞吐量如图 2.2 所示： 图 2.2 四种优先级业务吞吐量比较 从试验结果可以发现：高优先级的语音，视频业务流占了整个系统吞吐量的 94.7%，而处于低优先级的尽力而为、背景业务流只占 6.3%。并且 prio_3 的背景 业务流在 0s- 8s、22s- 45s 等时间段内吞吐量为 0，即多次发生“饿死现象” ，因此 存在严重的不公平性。 基于此，本章主要贡献就是针对这一问题，在 ieee 802.11s 标准草案的基础 上，结合 tcp 协议中的 aimd 算法，并参考可预测公平感知路由协议算法46 47 提出一种针对无线 mesh网的公平拥塞控制策略（简称 fccs） 。仿真结果表明，该 策略与 ieee 802.11e edca相比，在有效缓解网络拥塞的同时，整个系统吞吐量 提高了 6.3%， 并且保证了高优先级业务与低优先级业务之间的公平性， 防止了 “饿 死现象” 。 2.2 fccs 策略描述 本文提出的拥塞控制策略是运行在无线 mesh 网的中间节点上，即 mesh ap 或者 mesh routers 节点。这些 mesh节点在网络中主要起数据转发的作用。它们是 最容易发生拥塞的 mesh节点。fccs 策略主要由 3 个部分组成：拥塞度量、拥塞 通告、速率调整。流程图如图 2.3 所示。无线 mesh 网中每个 mesh 节点每隔 0.5s 发出拥塞度量信号， 根据拥塞度量的结果对 mesh节点的拥塞状况进行拥塞等级划 分。当拥塞等级为 0 时，表明网络没有发生拥塞，则通知上游 mesh节点增大发送 中南民族大学硕士学位论文 11 速率，从而增大网络利用率；当拥塞等级为 1 时，表明网络发生轻微的拥塞，则 通知上游 mesh节点降低发送速率，从而解决拥塞；当拥塞等级为 2 时，表明网络 发生严重拥塞，则通知上游 mesh节点和邻居 mesh节点降低发送速率，同时增大 本地节点的转发速率，从而快速解决网络拥塞。 拥塞level=0 向上游节点发送本地 节点拥塞状况通告 y 本次拥塞控制 结束 向上游、邻居节点 发送拥塞控制通告 nn y n y 拥塞度量 拥塞level=1拥塞level=2 上游节点回复 拥塞控制通告 上游节点回复 拥塞控制通告 上游、邻居节点回复 拥塞控制应答 上游节点降低发送 速率(aifsnb) 上游节点增大发送 速率(aifsn+a) 上游、邻居节点降低发 送速率(aifsnb) 向上游节点发送本地 节点拥塞状况通告 开始 图 2.3 fccs 流程图 2.3 fccs 实现 2.3.1 拥塞度量 拥塞度量的目的是通过检测并量化每个 mesh节点状况拥塞的状况， 以便及时 的发现拥塞，并了解拥塞的具体状况。ieee 802.11s 草案提到了两种检测方法：基 于队列长度和基于收、发速率。单一使用以上的两种方法都有不足。因为拥塞的 产生的原因不只和 mesh节点的队列有关，还有链路的信道质量状况有关。因此本 文的思路是结合链路的带宽占用率和队列的占用率来监测拥塞，并进行拥塞度量。 (1) 带宽占用率 由于节点的剩余带宽率可通过物理层的虚拟载波监听节点传输信道的忙与闲 而得到。依据文献48中，网络节点信道忙与信道空闲的比值与信道的占用的带宽 和空闲的带宽，两者近似成正比。考虑到物理层的各种帧等带来的开销，需要适 当的调整系数，mesh节点 n 的剩余带宽remainbw (t) n 近似估计表达式为： 无线 mesh 网络中拥塞控制的研究与实现 12 re( ) t idel mainbw tkbw nspeed t total = , (2.1) 调整后系数： 1500 4438 1500522038 0.8865 data k rtsctsdatamachdrack = + = + = , (2.2) 其中其中 speed bw表示无线 mesh 网物理层的链路带宽速度； idel t表示无线 mesh 网 空闲信道的时间大小； total t表示无线 mesh网信道的统计周期，大小为 0.5s；data 表示无线 mesh网物理层的数据大小为 1500bit； rts 表示无线 mesh网物理层请求 传输的占用的大小， 占用 44bit； cts 表示清除请求的占用的大小， 占用 38bit； ack 分别表示确认帧的大小，占用 38bit；mac hdr 表示无线 mesh网物理层包头的大 小，占用 52bit；ip hdr 表示无线 mesh网物理层 ip 头的大小，占用 20bit。 因此， t 时刻 mesh节点 n 的带宽占用率： _( )- re( ) _( ) _( ) n n bwmax nmainbw t usedrate bw t bwmax n = , (2.3) 其中：bw_max(n)表示 mesh节点 n 的最大带宽. (2) 队列占用率. mesh 节点 n 在 t 时刻的队列占用率等于此时队列的实际大小与队列总的大小 的比值。 ( ) ( ) lt n qrt n ln = , (2.4) 在时间 t（0.5）秒的采样时间内，计算剩余带宽率和队列占用率，来对 mesh 节点进行拥塞度量。为了避免统计中发生变化引起的抖动带来误差的影响，所以 采用“指数加权平均算法”进行数据平滑，利用 mesh 节点 n 在时刻 t 和时刻 t- 1 的不同状态进行信息联合预测估计。 中南民族大学硕士学位论文 13 usedrate_bw (t)=a usedrate_bw (t- 1)+(1- a) usedrate_bw (t) nnnt qr(t)=a qr(t- 1)+(1- a)qr(t) nnnt , (2.5) 则 mesh节点 n 在 t 时刻拥塞程度： _( )( )()/2 nnn usedratebw tcongestionlevel tqr t+= , (2.6) 其值越大则拥塞情况越严重。根据( )01 n congestionlevel t ，的值进行拥塞程度的等级 划分： 表 2.4 拥塞等级划分 拥塞等级 0 1 2 congestionlevel范围 0,0.6 (0.6,0.8 (0.8,1 2.3.2 拥塞通告 根据不同的拥塞等级发送不同的拥塞通告。当拥塞等级为 0 时，表明网络没 有发生拥塞，则通知上游 mesh节点增大发送速率，从而增大网络利用率；当拥塞 等级为 1 时，表明网络发生轻微的拥塞，则通知上游 mesh节点降低发送速率，从 而解决拥塞；当拥塞等级为 2 时，表明网络发生严重拥塞，则通知上游 mesh节点 和邻居 mesh节点降低发送速率，同时增大本地 mesh节点的转发速率，从而快速 解决网络拥塞。 在 ieee 802.11s 协议有三种不同作用的帧： 拥塞请求帧、拥塞答复帧、邻 居拥塞通告帧。这三种控制帧中都没有非常详细的参数指标，但是都提供了一个 名为：时间停止定时器的参数。通过该参数可以更加方便的设置三种帧的结构， 对 ieee 802.11s 拥塞控制进行完善。表 2.5 所示的是一个拥塞请求帧的具体组成。 拥塞请求帧在无线 mesh网络中传输的方式是单播。 在该拥塞请求帧中包含一个最 终的目标传输速率的参数。 表 2.5 拥塞请求帧组成 1 1 20 manager ask speed 在表 2.5 中， “manager”占用一个字节，当值为 5 时，表示为 mesh管理帧； “ask”占用 1 个字节，当值为 6 时，表示为拥塞请求帧。 “speed”占用 20 个字 无线 mesh 网络中拥塞控制的研究与实现 14 节， 用来表示目标传输速率。 在目标传输速率参数中包含了 prio_0、 prio_1、 prio_2、 prio_3 这四个不同优先级的目标传输速率，每个传输速率占用 4 个字节。具体情况 如表 2.6 所示。 表 2.6 目标传输速率的具体组成 2 4 4 4 4 2 congestion level target transmission rate （prio_0） target transmission rate （prio_1） target transmission rate （prio_1） target transmission rate （prio_1） expiration time 其中，拥塞等级 congestion level占用 2 个字节。四种不同优先级的目标传输 速率各占用 4 个字节。时间终止器占用 2 个字节。 mesh 网络中收到拥塞请求帧的节