无线Mesh 网络负载与干扰感知传输时间路由度量

王继红，石文孝，尚 硕，许银龙，李玉信，王春悦

(吉林大学 通信工程学院，长春130012)

0 引 言

无线Mesh 网络(Wireless Mesh networks，WMN)是能够解决“最后一公里”瓶颈问题的新型网络架构［1］。WMN 有很多重要应用，比如:灾难恢复、国土安全、会议中心等临时按需组网;在难以部署光缆地区提供通信连接;更主要的应用是为密集城区提供宽带Internet 接入，为蜂窝基站系统提供低成本回程网络等［2］。因此WMN 受到了学术界和业界的广泛关注。路由问题是WMN 面临的一大技术挑战，决定了业务的端到端性能，进而影响网络容量。路由问题的核心是选取合理的路由度量进行路径的计算和决策。

目前已经有文献为WMN 提出各种路由度量。跳数［3］是多跳无线网络中广泛使用的路由度量，网络通常选择跳数最少的路径进行数据包的传输;ETX(Expected transmission count)度量［4］考虑链路丢包率，使用一条链路上成功传输一个数据包所需要的期望传输次数(包括重传)来反映链路质量;ETT(Expected transmission time)度量［5］通过整合链路传输速率改进ETX，但是ETX和ETT 都没有考虑到干扰对路径选择的影响;WCETT(Weighted cumulative expected transmission time)度量［5］考虑了信道多样性，将ETT 度量扩展到多收发信机多信道网络场景，但是信道多样性反映的是流内干扰，流间干扰未纳入考虑;MIC(Metric of interference and channel switching)度量［6］在协议模型下同时考虑了流内、流间干扰、链路的丢包率和传输速率;IAWARE(Interference aware routing metric)度量［7］在物理干扰模型下使用接收信号功率衡量流内、流间干扰，更准确地捕捉干扰的加性特性。这些度量大多独立地衡量流内干扰和流间干扰，导致度量非保序或引入可调参数等问题。CATT(Contention aware transmission time)度量［8］统一描述流内干扰和流间干扰，避免了上述问题。INX(Interferer neighbors count)度量［9］考虑了链路的递交率和传输速率，使用干扰邻居的传输速率来衡量负载，但是文献［9］规定每条链路的传输速率相同，都使用标称数据速率。因此，INX 度量与考虑链路递交率的CATT 度量从本质上来说是相同的，且INX 和CATT 度量均未考虑负载对路由的影响，网络可能会将数据流路由到网络中的重负载区域，影响数据流的传输，甚至形成网络瓶颈。因此本文在有效继承CATT和INX 路由度量统一描述流内、流间干扰的基础上，提出负载与干扰感知传输时间LIATT(Load and interference－aware transmission time)路由度量。LIATT 使用节点处的缓存队列长度捕捉负载，使用邻区平均负载强度捕捉干扰，实现有效的网络负载均衡与干扰感知，提升网络整体性能。

1 CATT 与INX 路由度量

首先对现有CATT 和INX 路由度量进行介绍。文献［8］中提出的CATT 路由度量统一捕捉流内干扰和流间干扰，链路l 的CATT 度量由式(1)给出:

式中:Nl为与链路l 上的传输相干扰的链路集合，包括链路l本身;Lj是节点j 的包长度，对于网络中所有节点取值相同，如512 B 或1024 B;Rj是节点j 的发包速率，对于网络中所有节点，Rj取相同值，即信道的标称数据速率，比如802.11 b/g 的2 Mbit/s 或11 Mbit/s，这样Lj/Rj是个常数。因此，CATT 路由度量衡量的是链路l 的干扰邻居数，即干扰范围内使用相同信道的链路数，包括链路l 本身。

当考虑链路丢包时，CATT 路由度量扩展为CATTLD，链路l 的CATTLD度量由式(2)给出:

式中:ETXl表示链路l 的期望传输次数。

文献［9］提出的INX 路由度量使用干扰邻居的传输速率来衡量负载，链路l 的INX 度量由式(3)给出:

式中:ETTl表示链路l 的期望传输时间;|Nl|为与链路l 上的传输相干扰的链路数;S 为数据包大小，与式(1)中的Lj含义相同;Rl为链路l 的数据传输速率，文献［9］中所有链路都使用相同的标称数据速率，则Rl与式(1)中的Rj含义相同。由式(3)可以推导出如下表达式:

因此得出结论:INX 与考虑链路递交率的CATTLD路由度量在本质上是相同的，均反映了干扰链路传输对链路l 上数据包传输的影响情况。

当考虑链路负载时，CATT 路由度量扩展为CATTL2D，链路l 的CATTL2D度量由式(6)给出:

式中:τj表示包的传输尝试率，其余参数的含义与式(1)相同。实际上CATTL2D度量可以理解为使用干扰邻居的冲突感知传输时间之和来表示负载，但是文献［8］没有给出τj的取值或获取参数值的方法。

CATT 是一种保序［6］的路由度量，统一描述流内干扰和流间干扰。CATT 路由度量的优势在于:

(1)可以避免路由度量的非保序性或使用复杂映射算法解决保序性问题。对于非保序路由度量，不能使用Dijkstra 和Bellman－Ford 等有效算法计算出最小权重路径和非回环路由。使用映射算法实现保序性会增加路由算法的复杂度。

(2)可以避免引入可调参数。对于带有可调参数的路由度量，需研究这些可调参数如何影响网络整体性能以及如何根据不同网络拓扑或业务类型合理调整参数值，这在实际应用中很难实现。

CATT 路由度量仍存在以下局限:

(1)没有考虑节点处缓存包排队的情况，新到达包必须等待队列中前面的包服务完毕后才有传输机会。

(2)没有考虑到邻居的负载影响。邻居的负载越重，发生信道竞争的概率越大;没有负载(即不进行任何传输)的邻居不会产生干扰。CATT没有捕捉到这点，因此在某些情况下CATT 可能会放大干扰。

2 路由度量

2.1 LIATT 路由度量

本文充分继承了CATT 度量的优势，统一描述流内干扰和流间干扰影响，同时使用节点处的缓存队列长度捕捉负载，使用邻区平均负载强度捕捉干扰，提出了一种保序的负载与干扰感知传输时间路由度量LIATT。链路l 的LIATT 度量由式(7)～式(10)给出:

路径p 的LIATT 度量由式(11)给出:

式中:Tl表示链路l 的实际传输速率;NLl是链路l的平均负载，使用链路端点处的缓存队列长度表示;|Nl|表示干扰链路集合Nl中的干扰链路数，不包括链路l 本身;p 表示数据包经过的路由路径，网络会选择LIATT 度量值最小的路径进行数据包的传输。可以理解为节点j 排空缓存队列所需的传输时间，即干扰邻居j 的数据包总期望传输时间，其值越大表示与链路l 竞争的机会越大，对链路l 上数据传输的影响也就越大。由于节点业务负载随时间变化较大，容易产生路由震荡问题，因此采用干扰链路集合中各链路的期望传输时间标准差对负载进行平滑，同时也能更准确地衡量链路l 邻区中的干扰。综合以上分析，提出的LIATT 路由度量同时具备干扰感知和负载均衡的能力，能够识别出网络中的重干扰和重负载区域，指导网络在路由选择时避开这样的区域，从而提升网络的吞吐量。

2.2 考虑链路递交率的E－LIATT 路由度量

LIATT 度量是在假设链路无丢包的理想情况下提出的。实际上链路递交率会受到干扰等不稳定因素影响并随时间变化，网络不能保证所有数据正确完整的递交。因此应考虑链路递交率对路由选择的影响，此时，LIATT 度量可扩展为ELIATT，如式(12)所示:

式中:ETXl表示链路l 的期望传输次数;LIAl由式(9)给出;df和dr分别表示链路l 的前、反向递交率。

2.3 AODV 路由协议的修改及度量参数获取

2.3.1 AODV 路由协议修改

AODV(Ad Hoc on － demand distance vector)［10］路由协议是一种按需路由协议。当有数据包要发送时，节点通过广播路由请求(Routing request，RREQ)包发起路由请求过程，RREQ 包中携带源和目的节点的IP 地址和序列号、初始化为0 的路径跳数值等信息。RREQ 包在向目的节点转发过程中，中间节点更新路径跳数值并建立到源节点的反向路由。当RREQ 包到达目的节点时，目的节点向源节点返回路由应答(Routing reply，RREP)包，更新路径跳数值，建立到目的节点的正向路由。对AODV 路由协议进行了改进，使用路径的LIATT 度量值字段取代跳数字段，当源节点和目的节点之间存在多条路由路径时，选择LIATT 度量值最小的路径进行数据包的传输。

2.3.2 度量参数获取

LIATT 路由的实现需要获取关键参数，具体包括链路的实际传输速率Tl、干扰链路集合Nl和链路递交率d(包括df和dr)，下面给出具体的参数获取方法:

(1)链路的实际传输速率Tl:本文使用包对的方法获取链路的实际传输速率，即节点周期性地发出两个包，一个大包、一个小包，大小包分别为1137 B 和137 B，接收端记录连续接收到两个包的时间差，用大包大小除以时间差即得到链路实际传输速率的估计值。

(2)干扰链路集合Nl:两条链路e1=(u1，v1)和e2=(u2，v2)之间的距离d(e1，e2)定义为链路e1的任一个端点与链路e2的任一个端点距离的最小值，具体表示如下:

式中:d(u1，u2)表示节点u1、u2之间的欧式距离;d(u1，v2)、d(v1，u2)和d(v1，v2)的含义与d(u1，u2)类似。

定义距离小于干扰范围且使用同一信道的两条链路互为干扰链路;一条链路l 的所有干扰链路构成的集合称为干扰链路集合，干扰链路集合不包括链路l 本身。

干扰链路集合采用分布式信息交换方式获得。每条链路的端节点周期性地广播所使用的信道信息，其邻居节点在接收到该广播消息后会添加上自己的信道信息然后重新广播出去。为了防止信道广播消息的洪泛，同时考虑干扰范围与传输范围关系，本文在信道消息中加入跳数限制，使得信道信息只传递给干扰范围内的节点，干扰范围外的节点不需要也无法获得该消息。根据收到的信道信息，节点可以判断出干扰范围内使用相同信道的链路集合，即获取了干扰链路集合。

(3)链路递交率d:链路递交率使用探测包获取［4］。节点每隔时间τ 周期性地向一跳邻居发送探测包，每个探测包记录前w 时间窗内接收到的探测包数Count(w)，则链路的递交率如下:

3 性能评价与分析

本文使用NS－2.35 仿真工具对LIATT 及E－LIATT 路由度量的性能进行了仿真实验。对NS－2 模块进行扩展，以支持多信道多接口和改进的AODV 路由协议。在1000 m×1000 m 区域中部署了5×5 的格形拓扑，每个节点配置3 个网络接口卡，网络可用信道数为3。节点的传输范围为250 m，干扰范围为550 m。所有数据流均为CBR(Constant bit rate)流，包大小为512 B。

3.1 性能评价指标

仿真中使用网络整体吞吐量、网络平均丢包率和平均端到端时延对路由度量性能进行评价。

(1)网络整体吞吐量Thr 定义为网络中所有接收端单位时间内正确接收到的数据量，单位是kbit/s。表达式如式(6)所示:

式中:M 表示网络中的数据流集合;Reci表示流i的接收端在流运行期间接收到的总数据量;Δt 表示网络中第一个数据包发出时间与最后一个数据包接收时间之间的间隔，即网络中数据流运行的总时间。

(2)网络平均丢包率Err 定义为网络中所有接收端未正确接收到的包数与发送端发送的总包数的比值。表达式如式(17)所示:

式中:N表示网络中所有正确接收的数据包集合，|N|表示集合中的总包数;Ntotal表示网络中所有发送端发送的总包数。

(3)端到端时延定义为数据包从开始发送到被接收端正确接收所需要的时间，平均端到端时延D 取为网络中所有数据包端到端时延的平均值。表达式如式(18)所示:

式中:τj表示数据包j 的端到端时延。

3.2 LIATT 性能仿真及分析

首先固定节点发包速率，改变网络中的流数，观察流数变化对网络性能的影响。CATT 和LIATT 度量下的网络整体吞吐量、网络平均丢包率和平均端到端时延的仿真结果如图1 所示。

图1 不同流数下CATT 与LIATT 的性能比较Fig.1 Performance comparison between CATT and LIATT with varying flow numbers

图1 (a)表明随着流数的增多，网络整体吞吐量几乎呈线性增长。由图1(a)可以看出，LIATT度量的网络整体吞吐量始终高于CATT 度量，当网络中流数达到3 时，CATT 度量下的网络整体吞吐量达到660.08 kbit/s，LIATT 度量下的网络整体吞吐量达到710.19 kbit/s，吞吐量提高了7.6%。网络平均丢包率与网络整体吞吐量之间存在互补关系，如图1(b)所示。由图1(b)可以看出，LIATT 度量下的网络平均丢包率始终低于CATT 度量，这与由图1(a)得出的结论是一致的。图1(c)给出了两种度量下的平均端到端时延仿真结果，随着网络中流数的增多，平均端到端时延基本上呈现递增的趋势，但是LIATT 度量下的平均端到端时延始终低于CATT 度量，当网络中流数达到3 时，CATT 度量下的平均端到端时延为0.4486 s，LIATT 度量下的平均端到端时延为0.2953 s，平均端到端时延降低34.2%。这表明LIATT 度量能较好地均衡网络中的负载，感知重负载干扰区域，使网络在为数据流选路时避开这些区域、能迅速传递这些数据流，从而实现提高网络吞吐量性能和降低平均端到端时延的目的。

固定网络中的流数，改变节点的发包速率，观察发包速率改变对网络性能的影响。由于篇幅限制，这里仅给出流数取为5 时的仿真结果，当流数取为其他值时结果类似。同样使用网络整体吞吐量、网络平均丢包率和平均端到端时延来评价CATT 和LIATT 路由度量的性能，仿真结果如图2所示。

图2(a)表明随着节点发包速率的增大，网络整体吞吐量几乎呈线性增长。由图2(a)可以看出，LIATT 度量的整体网络吞吐量始终高于CATT度量，当节点发包速率达到256 kbit/s 时，CATT度量下的网络整体吞吐量达到1003.12 kbit/s，LIATT 度量下的整体网络吞吐量达到1123.86 kbit/s，吞吐量提高了12%。

由图2(b)可以看出，LIATT 度量下的网络平均丢包率始终低于CATT 度量，与图2(a)结论一致。图2(c)为两种度量下的平均端到端时延仿真结果，随着节点发包速率的增大，平均端到端时延呈现线性增长的趋势，但是LIATT 度量下的平均端到端时延始终低于CATT 度量，当节点发包速率达到256 kbit/s 时，CATT 度量下的平均端到端时延为0.416747 s，LIATT 度量下的平均端到端时延为0.318450 s，平均端到端时延降低23.6%。上述仿真结果同样证明了LIATT 度量在提升网络性能方面的优势。

图2 不同发包速率下CATT 与LIATT 的性能比较Fig.2 Performance comparison between CATT and LIATT with varying packet sending rates

图3 E－LIATT 与LIATT 网络整体吞吐量对比Fig.3 Total network throughput comparison between E－LIATT and LIATT

最后对考虑链路递交率的E－LIATT 与LIATT 进行了简单的性能比较，图3 给出了两种度量下网络整体吞吐量的仿真结果。

由图3 可以看出，当节点的发包速率改变时，E－LIATT 度量下的网络整体吞吐量始终高于LIATT，即当考虑链路递交率时，网络整体吞吐量得到明显提升，这主要是由于网络在为数据包选路时会尽量避开丢包严重的链路，减少数据包重传的次数，在相同条件下网络可以传输更多的数据，从而实现网络整体吞吐量的提升。

4 结束语

本文在分析CATT 路由度量优势与局限性的基础上，有效继承其统一描述流内干扰和流间干扰的优势，通过考虑节点的负载因素克服其局限性，提出负载与干扰感知传输时间路由度量LIATT 及考虑链路递交率的路由度量E－LIATT。仿真结果验证了本文路由度量相对于CATT 路由度量的优势。IEEE 802.11 WMN 正交信道数有限，尤其是802.11 b/g 只有3 条正交信道。正交信道数的有限性使得为邻近链路分配不同信道变得很难，邻近链路使用相同信道引起的共干扰会导致网络容量下降，因此仅利用正交信道难以解决干扰问题。部分重叠信道［11－12］的引入为WMN干扰减轻甚至消除带来了新的思路，通过仔细规划部分重叠信道的使用，增加网络中的并行传输数，能显著提升网络容量。我们下一步的工作是研究部分重叠信道下的路由度量，以期进一步降低网络中的干扰，提升网络容量。

［1］Wu Di，Bao Li－chun，Regan Amelia C，et al.Large－scale access scheduling in wireless mesh networks using social centrality［J］.Journal of Parallel and Distributed Computing，2013，73(8):1049－1065.

［2］Subramanian P A，Buddhikot M，Miller S.Interference aware routing in multi－radio wireless mesh networks［C］∥The 2nd IEEE Workshop on Wireless Mesh Networks，Reston，USA，2006:55－63.

［3］Stallings William.Data and Computer Communications［M］.New Jersey:Prentice Hall，1997.

［4］Couto D S J D，Aauayo D，Bicket J，et al.A highthroughput path metric for multi－hop wireless routing［C］∥The 9th MobiCom，San Diego，USA，2003:134－146.

［5］Draves R，Padhye J，Zill B.Routing in multi－radio，multi－hop wireless mesh networks［C］∥MobiCom，Philadelphia，USA，2004:114－128.

［6］Yang Ya－ling，Wang Jun，Kravets Robin.Interference－aware load balancing for multihop wireless networks［C］∥The Proceeding of the IEEE Workshop on Wireless Mesh Networks，Santa Clara，USA，2005.

［7］Subramanian P A，Buddhikot M，Miller S.Interference aware routing in multi－radio wireless mesh networks［C］∥The 2nd IEEE Workshop on Wireless Mesh Networks，Reston，USA，2006:55－63.

［8］Genetzakis M，Siris A V.A contention－aware routing metric for multi－rate multi－radio mesh networks［C］∥The 5th Annual IEEE Communications Society Conference on Sensor，Mesh and Ad Hoc Communications and Networks，San Francisco，CA，United States，2008:242－250.

［9］Langar R，Bouabdallah N，Boutaba R.Mobility－aware clustering algorithms with interference constraints in wireless mesh networks［J］.Computer Networks，2009，53(1):25－44.

［10］Perkins E C，Royer B E.Ad hoc on－demand distance vector routing［S］.IEEE Workshop on Mobile Computing and Systems and Applications，1999.

［11］Sun Wei－feng，Fu Tong，Xia Feng，et al.A dynamic channel assignment strategy based on cross－layer design for wireless mesh networks［J］.International Journal of Communication Systems，2012，25(9):1122－1138.

［12］Ding Yong，Huang Yi，Zeng Guo－kai，et al.Using partially overlapping channels to improve throughput in wireless mesh networks［J］.IEEE Transactions on Mobile Computing，2012，11(11):1720－1733.