《一种具有拥塞感知功能的CAHWMP路由协议.doc》由会员分享，可在线阅读，更多相关《一种具有拥塞感知功能的CAHWMP路由协议.doc（6页珍藏版）》请在三一办公上搜索。
1、一种具有拥塞感知功能的CA_HWMP路由协议摘要：负载均衡问题一直是无线Mesh网络的重点研究对象，本文提出一种具有拥塞感知功能的CA_HWMP路由协议。在Mesh管理帧中增加负载信息位，使节点知道周围邻居节点的负载情况，把节点负载分为三个等级，选择路径时综合考虑路径代价和邻居节点负载情况。通过负载约束控制机制和选路控制机制，均衡网络流量，避免发生拥塞。仿真结果表明，与HWMP相比，CA_HWMP有效平衡了网络负载，在整体上提升了网络性能。关键词：无线Mesh网络；CA_HWMP；负载约束控制；选路控制；拥塞感知CA_HWMP: A Congestion-aware Routing Proto
2、col Abstract: Load balancing has been a focus of study in Wireless Mesh Networks. A congestion-aware routing protocol named CA_HWMP is proposed in this paper. To make nodes know load of surrounding neighbors, Load information is added to 802.11s management frames. So it can consider both routing met
3、ric and load of neighbors. The node load is divided into three levels. It can balance network traffic and avoid congestion through Load Constraint Control Mechanism and the Routing Control Mechanism. The simulation results show that CA_HWMP can effectively balance the load of network and enhance the
4、 performance of network.Key words: Wireless Mesh Network; CA_HWMP; Load Constraint Control; Routing Control; Congestion-Aware1 引 言无线Mesh网络1根据体系结构可分为三种：骨干网Mesh结构、客户端Mesh结构、混合结构，其中骨干网Mesh结构如图1所示。图1 骨干WLAN Mesh结构图Fig.1 Backbone WLAN Mesh Structure在无线Mesh网络中，骨干网的负载均衡问题一直是重点研究对象。由于骨干网网络流量大、无线信道的使用率很高，极有可
5、能发生网络拥塞以致负载失衡。一旦网络负载失衡，将导致时延增大、丢包率增大、吞吐量下降等严重问题，影响网络的服务质量。为此，很多论文已经提出了一些改进方案。文献2提出一种根据平面坐标位置来部署Mesh路由器，并在AODV基础上改进通过多路径方式实现负载均衡的路由算法，但该算法对Mesh节点的位置要求较高，并且可能存在节点因收不到某个邻居节点的信号而无法通信的情况，故实用性不高。文献3提出了一个负载感知路由算法，把一个WMN划分为多个簇进行负载控制，每个簇动态计算本簇的流量大小，如果某个簇头计算出来的值过大，簇头就增大通过本簇的路由Metric值，使得一部分节点加入其他簇来转发，进而实现负载均衡。
6、文献4使用图形学理论结合启发式算法把节点分划分到不同的区域中。但是文献34中的算法都仅考虑了簇之间的负载均衡，没有考虑簇内部的负载均衡。文献5提出一种名为APTLB的模式，能把重载区域的部分流量引导至某些负载较轻的节点，但是却没有考虑到切换路径后会造成其他节点负载过重的情况。文献67通过多路径来分担负载，为了使不同路径尽可能不相交并且避免数据包乱序，所需的路由开销较大，相应的路由计算、路由管理也更复杂，且不同路径之间极有可能相互干扰。针对上述问题，本文提出一种具有拥塞感知8功能的路由协议CA_HWMP。CA_HWMP由802.11s草案中定义的WLAN Mesh网默认的混合无线Mesh协议HW
7、MP(Hybrid Wireless Mesh Protocol) 改进而来，主要改进思想为：使用节点负载约束控制机制和选路控制机制。设计负载约束控制函数对路由发现及维护过程改进，更新PREQ消息时综合考虑HWMP协议中定义的空时链路度量9和邻居节点负载情况两个因素，对处于重负载状态的节点和即将进入重负载状态的节点处以不同程度的惩罚；同时，在PREQ帧中增加表示负载的信息位，使Mesh节点知道周围邻居节点的负载情况，路径选择时运用选路控制机制，节点能综合考虑周围邻居的负载和各链路的Metric值，均衡网络流量，避免发生拥塞。2拥塞感知路由协议CA_HWMP 2.1节点负载文献3用节点缓冲区待发
8、送数据包的个数与缓冲区总大小的比值来度量节点负载，这种计算方式并不能准确反映节点某时刻的负载。为降低流量突变产生的异常结果所带来的影响，本文使用自回归平滑机制进行处理，节点i在T时刻的负载用(1)式表示： (1)其中，；是测量的时间间隔；是节点i中最大的数据队列长度；是从()到的时间段内节点i的平均数据队列长度。节点周期性地计算自己当前的负载值，通过转发PREQ消息，使周围邻居节点都能知道该节点最新的负载值。根据计算出的负载值把节点的负载状态分为三个等级：green：yellow：red：green、yellow、red三个等级分别表示节点负载较轻、节点负载较大但还未达到重负载状态、节点处于重
9、负载状态。2.2802.11s管理帧结构PREQ：在802.11协议中，PREQ消息是在路由建立、路由维护过程中由源节点向目的节点发送的。如图2，在PREQ帧结构中增加表示节点负载的信息位load，于是节点在收到PREQ时，将Hopcount、TTL分别减1，将当前负载值存到load字段，更新路径Metric信息，再将其广播出去。图2 修改后的PREQ帧结构图Fig.2 The Modified PREQ frame Structure由于目的节点收到PREQ后就已经建立了一条反转路径，目的节点向源节点发送的PREP消息是单播发送的，故PREP的帧结构不作改动。相应地，路由表结构也要增加一项用
10、来保存邻居节点的负载值。更改后的路由表包含如下内容：目的地址、下一跳地址、DSN、Metric、Lifetime、load。2.3负载约束控制函数的设计 由于HWMP协议在路由发现、路由维护过程中以空时链路度量9为路由判据，但这样可能会使网络流量过于集中到某些节点处，导致局部负载过大，降低网络性能。因此设计以下函数，根据节点的负载情况进行一定惩罚，尽量降低再次选中重负载节点的可能性。设节点i的当前负载为，约束因子为，一段链路的空时链路度量为，则负载约束控制函数如(2)式所示：(2)其中根据节点的负载等级取不同的值。如果节点负载处于green状态，取值为0；如果节点负载处于yellow或red状
11、态，取非零值，即根据负载情况进行不同程度的惩罚从而抑制通过本节点的流量。在路由建立及维护时，每个节点计算出自身的并和收到的PREQ中的metric值累加，PREQ到达目的节点时就能得到整条路径的metric值：(3)在构建及维护路由表时，还要结合选路控制机制来决定选择哪条路径建立路由。2.4CA_HWMP协议描述图3 CA_HWMP协议路由建立过程Fig.3 The Route Establishment Process of CA_HWMP在本文方法中，节点在路径建立及维护时要综合考虑邻居节点的负载值和Metric值。如图3所示，源节点S要建立一条到目的节点G的路径，有三条可选路径。B、D、
12、F收到PREQ后先把本节点的负载值保存到PREQ中，再根据负载约束控制函数计算出自身到上一跳节点的，进而累加得到自身到源节点S这条路径的值，更新PREQ后继续转发。G在一轮路由请求过程中分别收到来自B、D、F的PREQ，此时要根据选路控制机制选择一条合适的路径去往S。如果B、D、F都处于red状态，则选择负载值最小的节点作为上一跳；如果B、D、F既有处于red状态，也有处于非red状态的，则在非red状态的节点中选择一个metric最小的作为上一跳节点。G更新自身的路由表后，检查自身是否是该PREQ请求的目的节点。如果是，则沿刚建立的反转路径向源节点S单播发送一个PREP消息，此轮路由请求结束
13、；如果不是，则更新PREQ后继续转发。2.5选路控制机制一次路由请求过程中，节点会收到多个来自邻居节点的PREQ消息，设为PREQ中记录的上一跳节点的负载值，为路由表中记录的负载值，为PREQ中记录的。CA_HWMP协议按如下的算法对PREQ进行处理：IF (路由表中没有到源节点S的路径) 用和节点当前负载值更新PREQ；在路由表中增加一条到源节点S的路由，并记下上一跳节点的负载值；转发PREQ； ELSE IF ()丢弃PREQ；ELSE IF () IF () 用和节点当前负载值更新PREQ；更新路由表中的路由，并记下上一跳节点的负载值；转发PREQ； ELSE丢弃PREQ；ELSE IF
14、()用和节点当前负载值更新PREQ；更新路由表中的路由，并记下上一跳节点的负载值；转发PREQ；ELSE IF() IF (优于路由表中的Path_Metric) 用和节点当前负载值更新PREQ；更新路由表中的路由，并记下上一跳节点的负载值；转发PREQ； ELSE 丢弃PREQ；另外，为了增强路由的稳定性，当收到更小metric的RREQ时，并不立刻转换路径，而是继续用原路径一段时间，当metric差值达到一个临界值时，才转变路径。3协议仿真和结果分析 3.1仿真环境本文采用NS 2 version 2.3310网络模拟器对HWMP和CA_HWMP进行仿真，分析二者在平均端到端时延、丢包率、
15、网络吞吐量方面的差异。仿真环境如表1所示，在一个1200*1200的拓扑图内，随机分布25个节点，带宽取默认值2Mb，MAC层采用802.11规范。采用CBR数据流，每个数据包大小为512字节，数据流速率为20Kbps，其他参数采用ns/tcl/lib/ns-default.tcl文件中定义的默认值。分别对数据流数目为3 10的场景进行仿真对比，实验数据通过8次仿真结果获得。表1 仿真参数表Table 1 Simulation Parameters 路由协议HWMP和CA_HWMP仿真时间60s拓扑区域1200m * 1200m无线传输模型TwoRayGround节点传输距离200m数据流类型
16、CBR(UDP)数据包大小512Bytes最大数据流10数据流发送速率20Kbps3.2结果分析3.2.1 平均端到端时延网络的传输时延D(End-to-End Delay)定义为源节点发送出一个分组到目的节点接收到该分组之间的时间差，结合NS的Trace文件，用(4)式计算传输时延，其中表示第i个分组的传输时延，、分别表示第i个分组的接收时间和发送时间。则平均端到端时延可用(5)式表示，即统计Trace脚本中N个分组的平均传输时延。(4)(5)仿真结果如图4所示：图4 平均端到端时延 Fig.4 Average End-to-End Delay从图中可以看出，当数据流较少时，HWMP和CA_
17、HWMP的平均端到端时延都很小；随着数据流增多，CA_HWMP的平均端到端时延也增大，但优于HWMP协议。3.2.2 丢包率丢包率(Packet Loss)定义了传输期间网络丢失分组的数量占传输的数据总量的比例。在分析Trace文件时，以丢失分组的数量与发送分组的总量的比值来衡量丢包率的大小。(6)式中，NSP(Number of Send Packets)表示节点发送的分组数目，NRP(Number of Receive Packets)表示节点接收到的分组数目。仿真结果如图5所示：图5 丢包率 Fig.5 Loss Rate从图中可以看出，随着数据流增多，在相同数据流的情况下CA_HWMP
18、的丢包率一直低于HWMP。这是由于CA_HWMP选择路径时考虑了邻居节点的负载，能自动从负载较重的节点切换到其他负载较轻的节点上。3.2.3 网络吞吐量网络吞吐量(Throughput)TH是指在不丢包的情况下单位时间内节点可以接收的数据量，应该逐渐增大发送端的数据发送速率，然后计算接收端的吞吐量，直至吞吐量达到最大。在分析Trace文件时，使用以下的计算方式计算吞吐量：(7)式中,TB(i)是指到第i个分组被目的节点接收时已经传输的数据总量，RT(i)是第i个包的接收时间。i m，表示计算从第m个分组到第i个分组的吞吐量，若取m=1则是计算平均吞吐量。仿真结果如图6所示：图6 网络吞吐量 F
19、ig.6 Network Throughput从图中可以看出，数据流较少时，HWMP和CA_HWMP的网络吞吐量几乎相同；随着数据流增多，CA_HWMP的网络吞吐量明显高于HWMP协议。这是由于CA_HWMP在选择路径时考虑了邻居节点的负载，网络负载相对均衡，在不丢包的情况下单位时间内节点可以接收到的数据量比HWMP协议要大。4结论与下一步计划 本文分析了Mesh骨干网负载均衡问题的研究现状，针对HWMP协议缺少负载控制的不足，在路由发现及维护过程中做了改进，提出一种具有拥塞感知功能的CA_HWMP路由协议，避免了因局部负载失衡而导致网络性能下降的现象。仿真结果表明，CA_HWMP协议在整体上
20、提高了网络性能。下一步工作是扩展HWMP协议，使其适用于多网关环境，进行多网关负载均衡的研究。References: 1 Benyamina D, Hafid A, Gendreau M. Wireless Mesh Networks Design A Survey J. Communications Surveys & Tutorials, IEEE, 2012, 14(2): 299-310. 2 Bedi Paramjeet Kaur, Gupta Priyanka, Gupta Tarun Kumar. A congestion-aware and load-balanced geog
21、raphic multipath routing protocol for WMN C. Sustainable Energy and Intelligent Systems International Conference, 2011: 901-907. 3 Kae Won Choi, Wha Sook Jeon, Dong Geun Jeong. Efficient Load-Aware Routing Scheme for Wireless Mesh Networks J. Mobile Computing, 2010, 9(9): 1293-1307. 4 Pandey S, Kada
22、mbi G, Bates S,et al. A load sharing and partitioning system for multihop Wireless Mesh Network with multiple gateways C. Open Systems(ICOS) 2011 IEEE Conference, 2011: 369-374. 5 Algamali M, Wang Jian xin. APTLB: A Practical Approach for Providing Traffic Load-Balancing in Wireless Mesh Networks C.
23、 Wireless Communications, Networking and Mobile Computing,2009. WiCom 09 5th International Conference, 2009: 24-26. 6 Nagesh S, Deepti S, Dharma P. Multipath Routing in Wireless Mesh Networks C. Mobile Adhoc and Sensor Systems (MASS), 2006 IEEE International Conference, 2006: 741-746. 7 Wai-Hong Tar
24、n, Yu-Chee Tseng. Joint Multi-Channel Link Layer and Multi-Path Routing Design for Wireless Mesh Networks C. INFOCOM 2007, 26th IEEE International Conference on Computer Communications, 2007: 2081-2089. 8 Sudip Misra, Subhas Chandra Misra, Isaac Woungang. Congestion Control in Wireless Mesh Networks J. Computer Communications and Networks, 2009: 277-295. 9 D G. Lowe. Distinctive image features from scale-invariant keypoints J. IJCV, 2004, 60(2): 91110. 10 The Network Simulator-ns2 EB/OL. http:/www.isi.edu/nsnam/ns/. 2010
