基于无线Mesh网络流量优先级的拥塞及速率控制协议

1、 基于无线mesh网络流量优先级的拥塞及速率控制协议 许邦超，陈世平（上海理工大学光电信息与计算机工程学院，上海200093）摘要：在无线mesh网络中，为了确保更高的网络吞吐量，避免拥塞和保持流量间的公平，提出了无线mesh网络流量优先级的拥塞及速率控制模型。在处理拥塞时，通过限制下游节点的可用传输速率来实现。协议采用拥塞度计算速率分配和优先级交通，以确保更高的网络吞吐量和保证交付的实时流量，是一种全新的分布式拥塞控制方案。ns-2模拟实验证明：该算法提高了网络整体吞吐量，满足了数据流的公平性和对交通延时的约束。关键词：无线mesh网络；拥塞控制；流量优先级doi：10.11907/rjdk

2、.151436tp393 ：a ：1672-7800（2015）007-0179-05基金项目：国家自然科学基金项目（61170277，61472256）；上海市教委科研创新重点项目（12zz137）；上海市一流学科建设项目（s1201ylxk）作者简介：许邦超(1988-)，男，安徽铜陵人，上海理工大学光电信息与计算机工程学院硕士研究生，研究方向为无线网络、计算机网络、云计算；陈世平(1964-)，男，浙江绍兴人，上海理工大学光电信息与计算机工程学院教授、博士生导师，研究方向为计算机网络、分布式计算、云计算。0引言无线网状网络（wmn）为大规模传输技术，其中涵盖了大部分未解决的网络问题，如灵

3、活、适应性和可重构1-4，成本效益俱佳。在无线mesh网络中，节点是网格路由器和网状客户端，其中无线路由器具有最低流动性，形成无线网状网路的骨干，通过网络访问这两个网和传统客户端。本文提出了无线mesh网络的分布式拥塞控制机制，以确保更高的网络吞吐量，同时避免拥塞和保持数据流的公平，实现实时和非实时业务并存。此技术涉及3个基本参数：数据包到达率、服务率和缓冲区占用。基于这些基本参数，计算一个节点，确定3种不同状态的拥挤度：无拥塞、预计拥塞和拥塞。在预期的拥塞状态下，下游节点根据其流量限制上游的可用传输速率。在拥塞状态中，下游节点按比例缩小上游节点之间的可用率，以增加可用的缓冲区，缓解拥堵。此外

4、，介绍了每个节点处理实时和非实时业务的两个队列。因此，通过拥挤度计算、速率分配和优先级流量，确保更高的网络吞吐量和保证交付的实时交通。1系统模型1.1网络模型建立一个网络图gn=（vn，en）的无线网状网，其中vn=1，n是一组节点（网络客户端、网状路由器和网关），en=（i，j）：i，jen是集合节点之间的双向链路。骨干网的路由器节点通过有线链路连接到互联网，称为网关节点。客户端节点获取连接到骨干网的边缘路由器网。1.2节点模型和传输流分类优先级的网络流量分类，以提供基于优先级的处理。本文分出两个不同的业务等级：实时交通类（rt类）和非实时通信类（nrt类）。rt类被分配到高优先级的实时流量

5、，而对于nrt业务，低延时不是太重要。高优先通信类需要有更高的吞吐量和低延迟约束。为了区分流量类别，网格节点增加了交通类标识符到本地数据包，并将它们放在适当的队列中。该标识符代表交通类中的每个数据包。一个中间节点接收在输入队列中，根据其通信类发送到不同的业务类别组。1.3wmn拥塞为了了解拥堵wmn情况，对各种交通负荷下100个节点进行ns-2实验。实验中吞吐量的变化如图1所示。随着负载的增加，端至端的吞吐量也呈线性增加，但达到最大值时，开始随着负载减少。在图2中，端至端的延迟也有类似曲线，并与提供的负载呈指数关系。经过分析负载与吞吐量的函数关系和负载与延迟特性的函数关系，得出4种不同的工作区

6、域，如图3和图4所示，交通负载在系统上的过程通过以下4种工作区域：无拥塞，低吞吐量、低时延（nc，lt，ld）：最初时交通流量低，无网络拥堵，快速地提供数据包，但吞吐量较低；预计拥塞，高吞吐量、低时延（ac，ht，ld）：交通量增加，达到网络吞吐量的最高水平，但走向拥塞；拥塞，高通量、高延迟（c，ht，hd）：当网络不能处理流量过大的分组时，拥塞发生，导致分组丢失和更高的端至端延迟；拥塞，低吞吐量、高延时（c，lt，hd）：由于流量输入状态恶化，进一步增加负载，更多的数据包在拥塞节点吞吐量下降，部分移动数据包从源到目的地被浪费。2系统协议本文拥塞控制机制依赖于本地的可用节点信息。协议采用逐跳信

7、号通知上游节点拥塞和下游节点可支持的速率，然后上游节点调整自己的传输速率。拥塞检测模块在检测拥堵节点时需考虑本地节点的输入流速率、输出流量速率和缓存占用。通过速率调整模块计算上游节点速率，拥塞信号模块向上游节点发出修改后的速率，以减轻下游节点的拥堵状态。2.1拥塞检测为了精确测量节点vi拥塞程度，本文定义了节点vi两个参数：q_avg_vi（平均队列长度）和cd_vi（拥塞度）。假设节点vi当前队列大小为q_cur_vi，则平均队列尺寸使用ewma（指数加权移动平均）算法计算：q_avg_vi=(1-)q_avg_vi+q_cur_vi(1)其中是权重因子。为了找到参数的有效值，通过改变的值来

8、衡量数据包在下游节点的数量，其中上游节点数在2-5个是可变的，如表1所示。最佳的结果选择较小的值来实现。模拟中，=0.15。节点vi的拥堵度表示为cd_vi，拥塞度定义为平均分组业务时间（t_serv_vi）与平均分组到达间隔时间（t_arr_vi），在预定的时间间隔中的比率，见公式（2）：平均到达间隔时间t_arr_vi定义为上游两个邻近数据分组到达之间的时间间隔，平均分组业务时间t_serv_vi定义为节点vi的数据分组平均处理时间。数据包t_serv_vi所描述时段是数据包进入队列的瞬间，链路层确认被接收或重传，达到最大次数后丢弃该分组。因此，t_serv_vi占据了退避延迟、信道忙和物

9、理传输延迟。为了测量各节点vi的t_arr_vi和t_serv_vi，使用ewma（指数加权移动平均）算法。拥塞度cd_vi反映当前拥塞的强度。当分组到达间隔时间比所述分组业务时间小，则拥塞度大于1，节点经历拥塞；当拥塞度小于1，则表明负载提供给该节点的空间不超过节点的转发能力。拥塞检测算法计算监控节点的拥塞度cd_vi和比较所述节点的平均队列大小q_avg_vi，具有最大队列阈值q_max_vi的节点拥塞状态归类为以下中的一个：（1）无拥塞状态：q_avg_viq_max_vi和cd_vi1。该状态下无拥堵是由于平均队列占用水平低于队列阈值。（2）预计拥塞状态：q_avg_vi1。当分组到达

10、速率大于离开速率，则表示可能在不久的将来发生拥塞。（3）拥塞状态：q_avg_viq_max_vi和cd_vi1。如果队列平均长度超过了预定的最大阈值，则该节点是拥堵的。2.2速率调整网络模型中，每个节点vi从它上游速度为rate_in_vj（up_vi）的节点vj（up_vi）接收数据包，并计算上游节点vj（up_vi）的平均输入速率rate_avg_vj，见公式（3）：rate_avg_vj(up_vi)=(1wq)rate_avg_vj(up_vj)+wqrate_in_vj(up_vi)(3)其中0wq1是一个常数。流量总体输入速率标为total_in_vi，表示节点vi所有上游节点v

11、j（up_vi）的平均输入速率的总和。平均队列长度q_avg_vi和拥塞程度cd_vi，节点vi检测拥堵、上游节点rate_avg_vj（up_vi）平均输入速率、节点vi（rate_ou来自www.lw5u.comt_vi）平均输入率，收集信息计算目标速率rate_tr_vj（up_vi），以避免或减轻拥堵。下面的算法，总结了拥塞检测和速率调整的过程。拥塞检测率调整算法：输入量：q_max_vi，t_arr_vi，t_serv_vi，每个上游节点vj的速率rate_in_vj(up_vi)输出量：拥塞状态和rate_tr_vj(up_vi)初始化节点信息计算q_avg_vi，cd_vi，ra

12、te_avg_vj(up_vi)，total_rinifq_avg_viq_max_viandcd_vi1thennocongestionendififq_avg_vi1then拥塞检测和速率调整机制在一个固定时间间隔呈周期性。节点vi通过获取平均队列尺寸q_avg_vi、平均到达时间t_arr_vi、平均业务时间t_serv_vi来检查拥塞状态。本文算法对不同拥堵状态反应如下：（1）只要一个节点的缓存占用没有充分利用，则被确认为（nc，lt，ld）区域，不发送任何速率调整的通知给上游数据流。（2）当新的节点开始活跃在节点vi的邻点或某些上游节点产生更多的流量，分组到达间隔时间减少，反映在vi

13、的拥塞度将增加，并且节点vi进入（ac，ht，ld）区域，在这种情况下，节点vi经历了早期的拥堵。为了避免拥堵，节点vi分发上游节点之间最大允许输出速度，以确保网络操作在预期的运转区域，如图3所示。（3）当平均队列长度超过最大队列阈值时，节点vi达到永久拥塞，进入（c，lt，hd）区域，如图3所示。这种情况下，上游节点的传输率积极降低以减少分组数据包丢失，并迅速缓解拥塞。上游节点的目标速率缩小是基于节点vi的输出速率和拥塞程度。本文提出的方法中，下游节点优先级的调度数据包需考虑其流量类型。为此，下游节点对每个业务类型维持虚拟队列（vqnrt用于nrt类，vqrt用于rt类）。一旦接收数据包，下

14、游节点保留来自空虚拟队列的数据包头部桶区域，并根据业务类别从头部到尾部增加适当的队列。当数据包成功发送时，缓冲空间被释放，并放置在空虚拟队列的尾部。从上游节点接收到的第一个数据包，下游节点将其分配到相应的虚拟队列中。当数据包被调度要传送时，节点选择来自虚拟队列具有最低权重的数据包。队列vqi传输的每一个数据包i(rt，nrt)，公式如下：其中，pckt_size表示数据包的大小，pckt_priority的值为1nrt业务和2rt业务。因此，调度程序提供的rt交通具有较高优先级，避免了通过轮循（rr）调度的“饥饿”机会。3模拟实验为了评估方案性能，本文采用ns-2模拟器进行模拟。模拟参数设定如

15、下：100节点随机分布在10001000m的正方形区域内，传输范围和载波感测范围分别设为250m、550m，使用路由协议aodv，信道容量设置为11mbps，且假设来自www.lw5u.com所有的节点队列长度为50，信道竞争窗口尺寸的范围是1，63，每个数据包的大小为64字节。源节点发送的数据包个数为530，所提供的负载从5pps（包/秒）到100pps而变化。图5显示了多种网络负载不同协议的吞吐量。对于nocc，随着源节点传输量的增加，网络吞吐量也随之增加。当网络达到饱和时，如果没有使用拥塞控制，那么吞吐量会下降，这是由于碰撞和竞争开销减少。但是，随着llap吞吐量的减少，由于源点自适应地

16、控制网络负载，保证了数据包从相同的源始发而不会自相竞争导致下降。ar-tp还实现了比nocc更高的吞吐量，这是因为上游节点数据包进入网络时速率的调节是通过下游节点进入缓冲器状态，这反映了网络拥塞状态。如图5所示，由于逐跳响应方式，避免了网络拥塞，动态调节数据流量的速率，最大限度地提高了网络的利用效率，因而本文提出的协议优于其它协议。图6和图7表示各种协议的碰撞率。在nocc中，下降速率随着注入数据包的增加和数据源数量的增加而急剧增加。在llap中，因为减少了无用的数据包传输，最终减少了mac碰撞。在ar-tp协议中，所有中间节点使用一个背压机制，使得所述下游节点获取拥塞共享介质，最终降低了冲突

17、的次数。但是，当一个节点试图减轻其拥挤状态时，会使用上游阈值机制，以调节上游节点的缓冲区阈值，增加下行节点速率而不考虑邻近拥塞现象。其结果是，邻域拥挤速度增加，提高了碰撞率。图8显示不同协议的端至端延迟特性比较。在nocc中源点数据速率增加下，端至端延迟的增加是由于数据队列延迟和路径上的竞争延迟所至。在llap中，该入口节点把数据包放入与所述路径区间中连续数据包之间的fhd。所以，增加的端至端延迟是由于该数据排队延迟在入口节点。当队列已满则表示端至端延迟饱和。ar-tp可减少端至端延迟，显著超过nocc和llap，因为它根据网络负载控制节点的传输速率。本文方法中，源节点保持流量速率在一定水平，

18、以使网络工作在最大吞吐量区域。为了评价所提出的流分类性能，假设每个节点都具有不同业务类别：rt和nrt，如图9所示。由于wrr调度确保较低的权重数据包接收更多的网络带宽，因此，要根据每个业务类别的权重来分配网络带宽。rt类具有比nrt类更高的吞吐量。nocc协议不能区分通信类别，它的总吞吐量如图9所示。图10显示了nocc和提出的协议端到端的数据延迟曲线。rt类具有最高优先级，所以在端至端延迟总是比nrt类低。nocc协议对所有业务等级使用一个共同的缓冲器，因此不能确保高优先级的rt业务类低延时。4结语本文提出了wmn一种新型自适应负载和流量优先级敏感的拥塞控制技术，目标是要保持更高的网络吞吐

19、量，同时避免拥堵和给予实时交通优先待遇。本文解决了以下问题：使用3个基本节点参数，分组输入速率，分组业务速率和缓冲器占用情况，以反映节点和它附近的拥塞状态；根据要求限制上游速率比例；把重点放在调度延迟约束上。通过ns-2模拟实验显示：本文协议大大降低了碰撞率，并避免缓冲器下降，增加了传输率和网络吞吐量。最近研究表明，在每个节点使用多个无线广播可以提高带宽利用率，减少wmn邻域竞争。可用信道分配、无线接口邻域的竞争和减轻领域拥堵是一个具有挑战性的问题。基于本文提出的拥塞和速率控制机制，下一步应开发一种智能、动态信道分配策略，以减少拥堵，最大限度地传输流量。参考文献：1alislamaa，raghunathanv.end-to-endcongestio