一种新型的高吞吐量路由量度

肖晓丽，黄  敏，张卫平

 (长沙理工大学 计算机与通信工程学院，湖南 长沙，410004)

摘  要：在期望吞吐量路由量度的基础上，研究路径负载状况和链路干扰范围对路径性能的影响，将介质访问控制子层(Media access control，MAC)接口平均等待队列长度和MAC层向物理层递交数据的速率作为节点负载加入到路由量度中, 提出一种用于无线Mesh网络(Wireless mesh network)的新型路由量度，并将该量度应用于动态源路由协议DSR(Dynamic source routing protocol)协议中；通过仿真实验研究该路由量度中权值系数β的取值对网络性能的影响，并在仿真网络性能β最优时，分析比较期望吞吐量度和新型路由量度在网络吞吐量和数据包端到端延迟方面的性能。仿真结果表明：在数据流量较大、网络负载较大的多射频多信道无线Mesh网络中，新型的路由量度能够提供比期望吞吐量路由量度更准确的链路及路径性能的估计，使得基于该路由量度的路由协议能够选择数据位总传输延迟最小和总节点负载最小的路径，能够避开网络中的繁忙路径和拥塞节点，从而有效地提高网络吞吐量，降低数据包端到端延迟，实现网络的负载平衡。⊙

关键词：无线Mesh网络；路由量度；吞吐量；负载平衡⊙

中图分类号：TP393        文献标识码：A         文章编号：1672-7207(2009)02-0458-06

Novel and high throughput routing metric

XIAO Xiao-li, HUANG min, ZHANG Wei-ping

(College of Computer and Communication Engineering, Changsha University of Science and Technology,

 Changsha 410004, China)

Abstract: Based on the expected throughput metric(ETP)，two important parameters of MAC layer, the average length of waiting queue of MAC(Media access control) interface layer and the transfer rate of packet frame from MAC layer to physical layer, were chosen as node’s loading and added into metric. A novel and high throughput metric was presented for wireless mesh networks. The metric took into account the interference range and node’s loading between links, and was used in source routing protocols such as DSR(Dynamic source routing protocol). By simulating experiments the influence of parameter β of the metric on network performance was studied, the performance was analyzed and compared between expected throughput (ETP) and the metric when the influence of parameter is the best. The simulation results show that the new metric can avoid congestion of nodes and busy paths in the network, and it can greatly improve routing performance in terms of end-to-end delay and throughput, perform the loading balance of network effectively, and it is a suitable routing metric in the multi-radio and multi-channel wireless mesh network with heavy traffic and loading compared to ETP.

Key words: wireless mesh network; routing metric; throughput; loading balance

无线Mesh网络(Wireless mesh network)是一种新型的无线通信网络，它具有自组织性和自愈的特点，是一种多跳的宽带无线网络，也是一种高容量、高速率的分布式网络^[1]。路由协议是无线Mesh网络的关键技术之一，而路由量度是影响路由协议性能的关键参数，其中, 基于何种路由量度进行路由选择是提高网络性能的关键。因此, 路由量度问题一直是无线Mesh网络路由协议研究领域的热点问题^[2-3]。当前无线Mesh网络中典型的路由量度包括Hop count，ETX，ETT，WCETT和MIC等。其中：Hop count只反映了网络中的路径长度，没有考虑数据包丢失率和链路带宽；ETX的计算是基于丢包率的，因而它直接影响到路径的吞吐量；ETT的缺陷在于它没有完全捕获网络中的流内干扰和流间干扰，并且ETX和ETT都没有考虑无线Mesh 网络中的多信道因素，从而也就不可能找到信道多样性好的路径来提升网络容量；WCETT量度可能导致路由环路和网络不稳定；MIC路由量度与一个新的先验式路由协议LIBRA相结合实现了网络的负载平衡。由于MIC量度只考虑了干扰节点的数量而不是干扰节点的负载，可能会选择具有高ETT值、吞吐量低的性能较差的路径^[4-9]。Mhatre等^[10]提出了一种应用于多射频多信道无线Mesh网络中的路由量度——期望吞吐量(Expected throughput，ETP)。该路由量度主要是针对ETX和ETT路由量度应用于多射频多信道无线Mesh网络中时均没有捕获到802.11DCF的带宽共享机制对链路质量所带来的影响而提出的^[11-12]。ETP直接计算了与一条链路的吞吐量相关的主要数据量。与ETX和ETT相比较， ETP针对802.11MAC层竞争的影响提供了一个更准确的模型，它通过考虑活跃链路间MAC层的交互作用来评估无线链路及路径的质量，从而提供了一个更准确的路径性能的估计。但是，该量度对长度较长的路径进行了保守估计，也没有考虑网络中节点的负载状况对路径性能的影响。

当前应用于无线Mesh网络中的典型路由量度都过多地考虑了流内干扰和流间干扰，而没有详细地考虑路径的负载状况对路径性能的影响。因此，有必要在路由量度设计中添加路径负载状况。 MIC量度虽然没有考虑路径负荷状况，但是，它可以通过一个基于虚拟节点的复杂路由协议来实现，实现代价过高。可见，通过何种方法实现对路径负载状况的考虑是当前路由量度研究的一个重要问题。为此，本文作者在期望吞吐量路由量度的基础上，考虑链路的干扰范围和节点负载，设计了一种新型的路由量度。

1  新型路由量度的设计

针对期望吞吐量路由量度所存在的缺陷，首先在ETP路由量度中添加对链路的干扰范围，然后，提出Mesh网络中节点负载的定义，并将该定义与ETP路由量度相结合，从而得到改进的期望吞吐量路由量度。

1.1  考虑链路干扰范围的吞吐量路由量度

以图1所示拓扑结构图为例说明对ETP路由量度的改进效果。假设路径ABCDEF上节点A有数据发往节点F，链路上所示数字为链路所使用的信道。假设链路的干扰范围为2跳以内，则链路A-B与B-C由于均在对方的干扰区域内，所以，它们不能同时发送数据；而链路A-B与E-F虽然都运行在相同信道1上，但彼此均不在对方的干扰区域内，所以，可以同时发送和传输数据；链路B-C与E-F的情况与链路A-B与E-F的情况相同。因此，将该属性添加到ETP路由量度中，并将改进的ETP路由量度命名为M。

图1  描述内部链路间干扰的拓扑结构图

Fig.1  Topology describing interference

但是，该路由量度仍然没有考虑到网络中节点的负载状况对路径性能的影响。

1.2  Mesh网络中节点负载的定义

在无线Mesh网络中，当网络节点或者网络区域负载过大甚至拥塞时，节点的性能指标主要在路由层和MAC 层，剩余能量出现明显变化。人们在研究无线Mesh网络中节点的负载时，也主要是从这3个方面进行研究，提出了许多探测参数和探测方法。在本文中，选择MAC层的2个重要参数来考虑节点的负载，即MAC 层接口平均等待队列长度和MAC层向物理层递交数据的速率。其中，MAC层接口平均等待队列长度反映的是上层数据包递交到 MAC 层后，在等待被MAC层递交到物理层进行发送时的等待队列状况；而MAC层向物理层递交数据的速率反映了MAC层信道的繁忙程度。因为只有节点竞争到了信道之后，缓存在 MAC层接口队列的数据包才能够被递交到物理层的收发信机上进行发送。参考这个参数可以及时、准确地反映MAC 层对信道的竞争状况。所以，选取MAC层的这2个参数来估计节点的负载状况是合理、可行的。

1条特定路径P上节点i的负载定义如下：

某条特定路径P上总的节点负载即为该条路径上所有节点负载的累加。

           。              (3)

由此，通过定义1条路径上总的节点负载，就可以将其与路由量度相结合，从而实现无线Mesh网络中基于路径的负载平衡，提高网络性能。

1.3  新型的期望吞吐量路由量度

基于无线Mesh网络中典型路由量度WCETT的加权累加的思想，将改进的路由量度与节点负载的定义相结合，从而得到了改进的期望吞吐量路由量度。但是，它要求选择所有候选路径中M最大的路径；而从路径上节点的负载状况看，它要求选择所有候选路径中总的节点负载最小的路径。因此，本文将M取倒数，并通过权值系数β(0≤β≤1)将这两者很好地结 合，从而得到改进的期望吞吐量路由量度方法NETP，其路由量度n_NETP定义如下：

因此,基于新路由量度的路由算法在选择最佳路径时，所有候选路径中具有最小n_NETP的路径将被选择，这意味着选择数据位总传输延迟最小、总节点负载最小的路径。

新路由量度很好地保留了ETP所有的特征和属性，同时，通过考虑链路的干扰范围、节点的负载状况对路径性能的影响，从而提高了ETP的性能。因此，基于该路由量度的路由算法，使源节点倾向于选择那些运行在相同信道上的链路间干扰较小且更加独立的路径来作为路由路径。这样，有效地避开了网络中的拥塞区域，实现了网络的负载平衡，提高了网络性能。所以，该路由量度是一个适用于多射频多信道无线Mesh网络的好的路由量度。

2  新路由量度实现中的关键问题

实现新路由量度的关键问题就是链路n_NETP的计算。假设网状节点以IBSS模式来运行，这样，就可以使用Beacon messages。假设每个节点都有1个监视源自该节点的所有链路健康状况的机制，且假设节点r的1个父节点为s，源自节点r与其父节点s之间的链路用i表示，那么，链路i的位速率r_i以及数据包成功率p_i^(f)和p_i^(r)就可以在链路i的源节点r上获得。为了实现该目标，使用周期性的广播或单播探询包来估计数据包丢失率^[13-15]。每个节点r将源自该节点的所有活跃链路的信息(即链路的位速率r_i和链路的数据包成功率p_i^(f) 和p_i^(r))嵌入在它的Beacon messages中并进行编码。通常，1条链路位于另一条给定链路的竞争域中，但是，该条链路的Beacon messages不能被给定链路的节点解码的情况是可能发生的，因为干扰区域大于传输区域。为了研究简便，假设1个节点能够对在其竞争域内的所有节点的Beacon messages信息解码，这样它的邻居节点就能够恢复该信息。将节点r所收集到的竞争链路的位速率和数据包成功率信息与节点s上对应的信息相结合，节点r就完全获得了链路i的竞争域。于是，通过使用这个结合的信息，节点r就能够使用(1)计算节点r和s之间的所有潜在链路的M。

3  新路由量度的性能

根据路由量度设计所需重点考虑的3个因素对新路由量度进行性能分析。

a. 路由的稳定性。新路由量度是基于无限Mesh网络中链路在MAC层的位速率和节点在MAC层的相关性能指标进行测量。无线Mesh网络与Ad hoc网络不同，其节点移动性较低。只要保证无线Mesh网络中的节点不要过于频繁地移动，新路由量度就能够保证路径权值的稳定性，即能够保证路由的稳定性。

b. 保证最小权值路径具有最好的性能。新路由量度选择策略选择的是源节点到目的节点的所有候选路径中n_NETP最小的路径，即意味着选择了网络中数据位总传输延迟最小、总节点负载最小的路径。显然，这样的路径具有最好的性能。

c. 存在有效的算法找到最小权值路径。因为ETP量度本身就是针对多信道无线Mesh网络而设计的，其固有的属性就决定了该量度及基于该量度的改进量度都是不保序的^{[9, 16]}。因此，新路由量度是不保序的，它像WCETT一样应用于源路由协议中, 能通过有效算法找到最小权值路径。

4  仿真实验

在NS-2网络仿真器中，将期望吞吐量路由量度ETP和改进的期望吞吐量路由量度应用于DSR协议中进行仿真实验，从而研究新路由量度中权值系数β的取值对网络性能的影响；并在网络性能的β取值最优时，分析比较ETP与新路由量度的性能^[17]。

选用25个无线Mesh网络节点，采用5×5平面网格式拓扑分布在 1 km×1 km 的范围内，如图2所示。所有节点均配置2块802.11 g的无线网卡，并采用文献[12]中所示的信道分配方法使其分别工作在2个互不干扰的信道上(如信道6和11)。任意相隔的2个节点之间的距离设定为200 m，节点的无线通信距离设定为250 m，干扰距离设定为500 m。整个系统仿真的时间为600 s。通信的业务类型为TCP，数据流量为FTP方式，速率设置为3 Mb/s。

图2  拓扑结构

Fig.2  Network topology

在仿真实验中，设置图2中的边界节点为数据发送的源节点，即节点4, 5, 14, 15, 20, 21, 22, 23, 24这9个节点为数据发送的源节点；节点0为网关节点。所有数据包的目的节点都是网关节点0，其余节点均为中继节点。

在实验过程中，首先随机选择1个数据源节点发起路由请求，路由建立之后便开始数据传输过程。随后，发起路由请求和进行数据传输的源节点数逐渐增多，最终9个源节点同时传输数据。所有源节点的目的节点都是网关节点0。同时，选取2个最能反映网络性能的指标即网络吞吐量和端到端延迟来对其进行性能分析。图3~6所示均为50次实验结果的均值。

4.1  路由量度中权值系数β的取值对网络性能的影响

图3和图4所示分别表示β为0.1，0.3，0.5，0.7和0.9时新路由量度的吞吐量性能和数据包端到端延迟。结果表明：随着网络中发送数据的源节点个数逐渐增多，网络吞吐量也随之增大，数据包延迟也逐渐增加；并且当β为0.3时，网络吞吐量最优，延迟最小；而当β为0.9时，网络吞吐量最小，延迟最大。从总体上说，β较小时的性能要明显优于β较大时的性能，这是802.11DCF带宽共享机制所致。因为运行在相同信道上的不同速率的链路间相互竞争，必然使得高速链路随着低速链路对信道的竞争而降低其传输速率，从而导致总体网络性能下降。因此，无线Mesh网络的性能主要是受路径上链路间竞争的影响，路径上总的节点负载状况对其影响是次要的。

β: 1—0.1; 2—0.3; 3—0.5; 4—0.7; 5—0.9

图3  不同β取值下的网络吞吐量比较

Fig.3  Comparison of throughputs with different β

β: 1—0.1; 2—0.3; 3—0.5; 4—0.7; 5—0.9

图4  不同β取值下的端到端延迟比较

Fig.4  Comparison of end-to-end delays with different β

此外，当β为0.3时，其网络吞吐量和端到端延迟要优于β为0.1时的性能。这说明虽然路径上节点的负载状况对网络性能的影响是次要的，但也要对其予以适当考虑，尤其是在网络负载较大时，其影响尤为突出，因此，在下面的实验中将β取为0.3。

4.2  ETP与新路由量度的性能分析与比较

图5和图6所示分别表示β为0.3时ETP和新路由量度的吞吐量和数据包端到端延迟方面的性能，其中，NETP为新的路由尺度量度方法。结果表明：当发送数据的源节点数目较少(≤3)时，ETP路由量度在这2方面的性能要略优于新路由量度性能；但是，当发送数据的源节点数逐渐增多(≥4)时，新路由量度在这2方面的性能要明显优于ETP路由量度性能。而且随着发送数据的源节点数逐渐增多，在网络吞吐量方面，新路由量度的增长速度较快，而ETP路由量度的增长速度较平稳；而在端到端延迟方面，情况则刚好相反。

1—ETP; 2—NETP

图5  吞吐量比较

Fig.5  Comparison of throughputs

1—ETP; 2—NETP

图6  端到端延迟比较

Fig.6  Comparison of end-to-end delays

造成上述现象的原因主要是：当发送数据的源节点数较少(≤3)时，网络上节点的负载都较小，其对路径性能影响很小，此时，路径的性能主要受路径上运行在相同信道上的链路间的竞争的影响，所以，此时ETP路由量度的性能要略优于新路由量度的性能；但是，当发送数据的源节点数逐渐增多(≥4)时，网络上数据流量增多，运行在相同信道上的链路数也增大，对信道的竞争激烈程度增加，干扰增大；同时，网络中很可能出现某些负载较大的繁忙节点。这些繁忙节点由于大量的数据包涌入，不但处理速度降低，导致报文延迟增大，而且会产生严重的阻塞和丢包现象。新路由量度由于合理地考虑了链路的干扰范围及节点的负载状况对路径性能的影响，从而在进行路径选择时能够很好地避开网络中的拥塞节点和繁忙路径，选择那些运行在相同信道上的链路间干扰较小且更加独立的路径来传输数据。所以，此时新路由量度的性能明显优于ETP路由量度的性能。因此，新路由量度适用于数据流量较大，网络性能负载较大的多射频多信道无线Mesh网络，此时，对网络性能的提升比对ETP路由量度的性能提升更加明显。

5  结  论

a. 提出了一种新型的路由量度, 该量度考虑了链路干扰范围，解决了ETP量度对流间干扰的保守估计，这样会更有效地利用网络带宽，大大提高网络吞吐量。

b. 新路由量度考虑了节点负载状况对链路及路径性能的影响，把MAC 层接口平均等待队列长度和MAC层向物理层递交数据的速率作为节点负载加入到路由量度中。基于该量度的路由算法在选择最佳路径时，将选择所有候选路径中具有最小n_NETP的路径，即意味着选择数据位总传输延迟最小、总节点负载最小的路径，能够很好地避开网络中的拥塞节点和繁忙路径，从而提高了网络吞吐量，降低了数据包端到端延迟，有效地实现了网络的负载平衡。

c. 该路由量度适用于数据流量较大、网络负载较大的多射频多信道无线Mesh网络。

参考文献：

[1] Akyildiz I F, WANG Xu-dong, WANG Wei-lin. Wireless mesh networks: A survey[J].Computer Networks, 2005, 47(4): 445-487.

[2] 杨 林, 郑 刚. 一种集成网络编码的低轨卫星网络多径路由方法[J]. 中南大学学报: 自然科学版, 2007, 38(5): 950-955.
YANG Lin, ZHENG Gang. A multi-path routing scheme integrated with network coding in low earth orbit satellite networks[J]. Journal of Central South University: Science and Technology, 2007, 38(5): 950-955.

[3] 沈 强, 方旭明, 宋 文. 无线Mesh网络路由协议研究[J]. 数据通信, 2005(4): 30-33.
SHEN Qiang, FANG Xu-ming, SONG Wen. Study of routing protocols for wireless mesh network[J]. Data Communications, 2005(4): 30-33.

[4] Draves R, Padhye J, Brian Z. Comparison of routing metrics for static multihop wireless networks[J]. Computer Communication Review, 2004, 34(4): 133-144.

[5] Koksal C E, Balakr H. Quality-aware routing metrics for time-varying wireless mesh networks[J]. IEEE Journal on Selected Areas in Communications, 2006, 24(11): 1984-1994.

[6] Draves R, Padhye J, Zill B. Routing in multi- radio, multi-hop wireless mesh networks[C]//New York: Association for Computing Machinery, 2004: 114-128.

[7] MA Liang, Mieso K. A routing metric for load balancing in wireless mesh networks[C]//Proceedings of the 21st International Conference on Advanced Information Networking and Applications Workshops. Washington D C, 2007: 409-414.

[8] Subramanian A P, Milind M, Miller S. Interference aware routing in multi-radio wireless mesh networks[C]//2nd IEEE Workshop on Wireless Mesh Networks. New York: IEEE Press, 2006: 55-63.

[9] YANG Ya-ling, WANG Jun, Kravets R. Interference-aware load balancing for multihop wireless networks[M]//Department of Computer Science, University of Illinois at Urbana-Champaign, 2005.

[10] Mhatre V P, Lundgren H. MAC-aware routing in wireless mesh networks[C]//Fourth Annual Conference on Wireless on Demand Network Systems and Services. Oberguyrgl: IEEE Press, 2007: 46-49.

[11] De Couto D, Aguayo D, Bicket J, et al. A high-throughput path metric for multi-hop wireless routing[C]//Proceedings of the 9th Annual International Conference on Mobile Computing and Networking. San Diego: ACM Press, 2003: 134-136.

[12] Draves R, Padhye J, Zill B. Routing in Multi-Radio, Multi-Hop wireless mesh networks[C]//Proceedings of the 10th Annual International Conference on Mobile Computing and Networking. Philadelphia: ACM Press, 2004: 114-128.

[13] Heusse M, Rousseau F, Berger-Sabbatel G, et al. Performance anomaly of 802.11b[C]//Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies. New York: IEEE Press, 2003: 836-843.

[14] Choi S, Park K, Kim C. On the performance characteristics of WLANs: revisited[J]. Performance Evaluation Review. New York: ACM Press, 2005, 33(1): 97-108.

[15] Vivek P, Mhatre, Lundgren H. Joint MAC-aware routing and load balancing in mesh networks[C]//International Conference on Emerging Networking Experiments and Technologies. NewYork: ACM Press, 2007: 10-13.

[16] Draves, R. Padhye J, Zill B. Comparison of routing metrics for static multi-hop wireless networks[C]// Proceedings of the 2004 conference on Applications, Technologies, Architectures, and Protocols for Computer Communications. New York: ACM Press, 2004: 133-14.

[17] 杨英杰, 邓会勇, 李 侠. 基于MATLAB/Simulink的粒度分离过程计算机仿真[J]. 中国有色金属学报, 2006, 16(2): 346-350.
YANG Ying-jie, DENG Hui-yong, LI Xia. Simulation of particle separation process based on MATLAB/Simulink[J]. The Chinese Journal of Nonferrous Metals, 2006, 16(2): 346-350.

收稿日期：2008-10-21；修回日期：2008-12-28

基金项目：湖南省教育厅科研基金资助项目(08C101)

通信作者：肖晓丽(1965-)，女，湖南邵阳人，副教授，从事计算机网络与信息安全研究；电话：13647316866；E-mail: ttxxli@163.com