基于无线Ad Hoc的多路径多信道路由度量准则

乔平安，邵 凯，刘运爽

(西安邮电大学计算机学院，陕西西安 710121)

路由度量准则作为路由协议重要的组成部分，一个好的路由度量准则能够提升网络的性能。由于现有路由度量准则大多都针对单信道设计，对于多路径多信道路由协议会导致无效的路由［1］，进而会限制网络的累积吞吐量［2］。本文提出了一种适用于多路径多信道的路由选择准则，仿真结果显示该准则在吞吐量方面优于已有的单信道路由选择准则。

1 基于WCETT的路由选择准则

微软公司Draves提出了一种单路径单信道的路由选择准则［3］，称为加权累计期望传输时间即WCETT准则，WCETT准则综合考虑了带宽等链路性能参数以及最小跳数等因素［4］。

首先，讨论一条路径累计期望传输时间计算，假如从A节点到B节点的链路为i，则该链路的期望传输时间值表示为ETTi，假如S表示分组的长度;B表示链路的实际带宽;N表示一个数据分组成功传输预计需要的次数，则ETT计算过程如下［5］

其中，fa，fb分别为某条链路的前向导通概率以及后向导通概率。则一条路径上所有n条链路的期望传输时间之和为，其中 n 为路由长度，使用式(1)估计一个分组在链路上的预计传输时间。由于受到信道差异的影响，累计期望传输时间ETT并不能完全反映该条路径的优劣，应考虑链路之间的相互干扰。假设一个n条路径，路径使用了k个信道进行传输，数据分组在信道m上的传输时间之和表示为Xm，其中对总吞吐量影响最大的信道可能是受干扰最大的信道，称为瓶颈信道，因此，一条路径的优劣，应是由累计期望传输时间与瓶颈信道传输两个因素来决定的。即WCETT

2 MWCETT路由选择准则

由于WCETT路由选择准则无法反映多信道链路之间的干扰以及数据包通过节点时的拥塞情况，针对该准则的缺点提出了一种适用于多路径多信道的路由选择准则—MWCETT准则。

2.1 MWCETT路由选择准则的确立

所谓多径路由，就是在通过路由算法选择传输路径时，同时选择多条路径，将通信量按照一定的比例分配到不同的路径上同时传输，以提高吞吐量，为方便分析，本文以3条路径为例，这一分析可扩展到≥4条路径。

在节点A，B之间进行通信，需选择3条同时用于传输的最佳路径La，Lb，Lc，在此MWCETT路由选择准则是根据多条路径的合计吞吐量的大小来确定的，影响吞吐量的因素较多，在此主要抓住3个因素:(1)单路径的时延因子。即单条路径上所花费的总时延。(2)路径干扰因子。该因子包括路径内使用相同信道的干扰以及路径间信道间的干扰。(3)数据通过节点时的排队时延因子。该因子是指所发送的数据包经过某节点时排队的迟延。因此，在路由选择时，估算出单路径的时延因子，路径干扰因子以及数据包通过节点时的排队时延因子，通过这些从而确定通信量在多条路径上的分配比例。

假设路径Lk的第i跳期望传输时间ETT表示为ETTki，用SR(Lk)表示路径Lk上所使用的信道。接下来通过单路径时延因子δ，路径干扰因子η，排队时延因子φ这3方面的组合关系获得MWCETT路由选择准则。

2.2 路径干扰因子η的计算

当分组使用多个信道在多条路径上同时传输时，使用相同信道的链路之间不可避免会产生干扰，该种干扰无形之中影响了整个网络的吞吐量。因此，文中希望找到链路之间干扰最小的一些路径，由于受干扰最大的瓶颈信道对网络的吞吐量影响最大，在此将瓶颈信道的传输时间称为路径间的干扰因子η，路径间的干扰因子η反映了多条路径有相同信道的链路之间的干扰，瓶颈信道取决于多路径的负载组合分配。

假设无线路径Lk有Nk个信道，则定义路径在信道j上的累积传输时间Ykj如下

现在定义一个多路径组合的瓶颈信道传输时间，考虑在路径 La，Lb和 Lc上通信量分配(x∶y∶z)，x 分组在路径La上，y分组在路径Lb上以及z分组在Lc上消耗的时间为 x×Yaj+y× Ybj+z×Zcj，这样在 La∪Lb∪Lc中的信道j上每个分组消耗的时间均值Wj(x，y，z)为

从式(4)可看出，通信量分配比例(x∶y∶z)决定了分组在信道上的消耗时间，消耗时间最长的信道为瓶颈信道。如果用Sabc表示路径组合(La，Lb，Lc)上的信道总数，则在通信量分配比例为(x∶y∶z)的情况下瓶颈信道的传输时间为因此多路径信道干扰因子

2.3 路径延时因子δ的计算

路径延迟因子δ反映了路径的端对端特性，其计算由单路径的路径质量准则WCETT推导出来。对于有nk个信道有n跳的路径Lk，其WCETT公式为

由式(6)可知，在一条路径上的WCETT值越小，预期的吞吐量越高，为了反映多条路径上分组的累积传输时间，定义路径延时因子δ(x，y，z)为多条路径上WCETT上的加权平均值，如下所示

式中，δ(x，y，z)反映了组合路径 La，Lb，Lc端到端的延时情况。

2.4 排队时延因子

Li为在节点i上等待队列的平均长度，vi为该节点发送数据包的速率，由Liang Ma提出的在路径Lp中节点的负载度［8］可表示为

La，Lb和Lc为3条无线自组网中的路径，则定义该路径中节点排空该队列的累积时间为

式中，φ(x，y，z)反映了组合路径 La，Lb，Lc端到端节点排队时延情况。

2.5 MWCETT准则

由式(5)、式(7)和式(9)可看出，多路径间的干扰因子η，路径延时因子δ，排队时延因子φ取决于负载分配比率x∶y∶z，单一的路径干扰因子η，路径延时因子δ，排队时延因子φ只能反映路径间路径内的干扰，端到端的延迟，或数据包通过节点时的排队延时其中的一种情况，只有综合考虑信道间的干扰，端到端的延迟以及排队时延的特性，才能全面反映路径的变化。因此，提出了一种新的由η，δ以及φ组合的多信道多路径路由选择准则—MWCETT准则。

MWCETT解决了端到端延迟，信道干扰以及排队迟延的问题。MWCETT值越低，路径累积吞吐量就越高。α与β是两个分别满足0≤α≤1，0≤β≤1的可调因子。若β=0，只考虑节点的排队迟延问题。若β选择1，而α≠0且α≠1，该准则只考虑端到端的迟延问题以及信道间的干扰问题。若β选择1，而α=0时该准则只考虑端到端的时延问题;若β选择1，而α=1时该准则只考虑信道的干扰问题。α，β之间的不同取值尝试着在信道干扰因子、端到端延迟因子以及排队迟延因子之间获得均衡。

3 仿真结果及性能分析

对于MSR协议分别应用传统的WCETT路由选择准则以及MWCETT路由选择准则进行性能的验证，在NS2环境下进行实验仿真，仿真环境在2 000×1 500的矩形区域内。对于MWCETT准则取α=0.5，β=0.5，选取3条路径进行传输，实验中业务源CBR(恒定比特率)数目分别为20个和30个。在这两种情况下，分别对WCETT路由准则与MWCETT路由准则下MSR协议的吞吐量进行仿真。

从图1和图2可以看出，在中载和重载下，MWCETT准则下的吞吐量与WCETT准则下的吞吐量变化趋势基本相同。但在路由跳数相同时MWCETT准则的吞吐量要优于WCETT准则，这是由于应用MWCETT准则的MSR协议选择了路径内、路径间信道干扰小、端到端延迟小且排队迟延短的路径进行数据传输，而应用WCETT准则的MSR协议只考虑了单条路径内的干扰以及端到端的迟延情况，所以前者在吞吐量方面会优于后者。

图1 MWCETT与WCETT准则下吞吐量比较(20个数据源)

图2 MWCETT与WCETT准则下吞吐量的比较(30个数据源)

4 结束语

针对已有的WCETT路由准则进行了分析，提出了一种满足无线Ad Hoc网络多径多信道传输的MWCETT路由选择准则，仿真验证了该路由准则在吞吐量方面要优于现有的WCETT路由选择准则，后期将继续完善该路由选择准则，并拓展应用到多路径多信道的无线Mesh网络中。

［1］ Akyildiz I F，Wang X D，Wang W L．Wireless meshnetwork:a survey［J］．Computer Networks，2005，47(4):445 －487．

［2］ 孙志．基于WCETT的多信道WMN路由度量的研究［J］．通信技术，2013，46(6):82 －84．

［3］ 秦裕斌，陈建华，黄晓．无线Mesh网络技术及其应用［J］．通信技术，2009，42(12):144 －146．

［4］ 姜维，唐俊华．随机无线通信信道功率分配策略研究［J］．信息安全与通信保密，2013(1):40－42．

［5］ Akyildiz I F，Wang X D，Wang W L．Wireless meshnetwork:a survey［J］．Computer Networks，2005，47(4):445 －487．

［6］ 王辉，俞能海．无线Ad Hoc网络中多路径负载平衡性能分析［J］．通信学报，2005，26(11):30 －35．

［7］ 杨文静，杨新宇，董翅勇．移动Ad Hoc网络中提高路由稳定性的动态备份多径路由［J］．西安交通大学学报，2010，44(12):16－21．

［8］ Ma L，Denko K M．A routing metric for load － balancingin wireless mesh networks［C］．Niagara Falls，Canada:Advanced Information Networking and Applications Workshops，AINAW，2007:238 －242．