引用本文
王继红, 石文孝, 尚硕, 许银龙, 李玉信, 王春悦. 无线Mesh网络负载与干扰感知传输时间路由度量. 45(1): 297-303
WANG Ji-hong, SHI Wen-xiao, SHANG Shuo, XU Yin-long, LI Yu-xin, WANG Chun-yue. Load and interference-aware transmission time routing metric for wireless mesh networks. Journal of Jilin University Engineering and Technology Edition, 45(1): 297-303  
Permissions
Copyright©2015, 吉林大学学报编辑部
版权所有.吉林大学学报编辑部
无线Mesh网络负载与干扰感知传输时间路由度量
王继红, 石文孝, 尚硕, 许银龙, 李玉信, 王春悦
吉林大学 通信工程学院,长春 130012
石文孝(1960-),男,教授,博士生导师.研究方向:无线资源管理技术,无线Mesh网络技术,光无线通信.E-mail:swx@jlu.edu.cn

作者简介:王继红(1986-),女,博士研究生.研究方向:无线Mesh网络技术.E-mail:wangjihong07@126.com

基金:国家自然科学基金项目(61373124)
摘要

提出了无线Mesh网络负载与干扰感知传输时间LIATT(Load and interference-aware transmission time)路由度量,有效继承了CATT(Contention aware transmission time)和INX(Interferer neighbors count)路由度量统一描述流内和流间干扰的优势。LIATT使用节点处的缓存队列长度捕捉负载,使用邻区平均负载强度捕捉干扰,实现有效的网络负载均衡与干扰感知,避免将数据包路由到网络负载和干扰较重区域而导致拥塞的问题。利用NS-2仿真软件进行的性能评价表明:本文路由度量能有效实现网络负载均衡,提升网络整体性能。

关键词: 通信技术; 无线Mesh网络; 路由度量; 负载均衡; 干扰感知
中图分类号:TN92 文献标志码:A 文章编号:1671-5497(2015)01-0297-07
Load and interference-aware transmission time routing metric for wireless mesh networks
WANG Ji-hong, SHI Wen-xiao, SHANG Shuo, XU Yin-long, LI Yu-xin, WANG Chun-yue
College of Communication Engineering, Jilin University, Changchun 130012, China
Abstract

A Load and Interference-Aware Transmission Time (LIATT) routing metric is proposed. It inherits the advantage of describing intra-flow and inter-flow interference uniformly. The buffer queue length of node is used to capture traffic load, and the average load of adjacent areas is used to capture interference, thus, achieving the load-balancing function and interference-aware function, which can avoid routing packets into heavy load and intense interference area. Simulation with NS-2 software is carried out to evaluate the performance of the proposed LIATT routing metric. Results show that the LIATT routing metric can effectively achieve load balancing and improve the whole network performance.

Keyword: communication; wireless mesh networks; routing metric; load balancing; interference-aware
引言

无线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路由度量统一捕捉流内干扰和流间干扰, 链路 的CATT度量由式(1)给出:

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

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

式中: 的期望传输次数。

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

式中: 含义相同。由式(3)可以推导出如下表达式:

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

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

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

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

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

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

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

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

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

2 路由度量
2.1 LIATT路由度量

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

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

式中: 表示数据包经过的路由路径, 网络会选择LIATT度量值最小的路径进行数据包的传输。 可以理解为节点 邻区中的干扰。综合以上分析, 提出的LIATT路由度量同时具备干扰感知和负载均衡的能力, 能够识别出网络中的重干扰和重负载区域, 指导网络在路由选择时避开这样的区域, 从而提升网络的吞吐量。

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

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

式中: 的前、反向递交率。

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路由的实现需要获取关键参数, 具体包括链路的实际传输速率 下面给出具体的参数获取方法:

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

(2)干扰链路集合 的任一个端点距离的最小值, 具体表示如下:

式中: 类似。

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

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

(3)链路递交率d:链路递交率使用探测包获取[4]。节点每隔时间τ 周期性地向一跳邻居发送探测包, 每个探测包记录前 则链路的递交率如下:

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)所示:

式中: 表示网络中第一个数据包发出时间与最后一个数据包接收时间之间的间隔, 即网络中数据流运行的总时间。

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

式中: 表示网络中所有发送端发送的总包数。

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

式中: 的端到端时延。

3.2 LIATT性能仿真及分析

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

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

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

图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 不同发包速率下CATT与LIATT的性能比较Fig.2 Performance comparison between CATT and LIATT with varying packet sending rates

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

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

由图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

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

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

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

4 结束语

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

The authors have declared that no competing interests exist.

参考文献
[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. [本文引用:1] [JCR: 0.859]
[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. [本文引用:1]
[3] Stallings William. Data and Computer Communications[M]. New Jersey: Prentice Hall, 1997. [本文引用:1]
[4] Couto D S J D, Aauayo D, Bicket J, et al. A high-throughput path metric for multi-hop wireless routing[C]∥The 9th MobiCom, San Diego, USA, 2003: 134-146. [本文引用:2]
[5] Draves R, Padhye J, Zill B. Routing in multi-radio, multi-hop wireless mesh networks[C]∥MobiCom, Philadelphia, USA, 2004: 114-128. [本文引用:2]
[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. [本文引用:2]
[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. [本文引用:1]
[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. [本文引用:1]
[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. [本文引用:1] [JCR: 1.231]
[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. [本文引用:1]
[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. [本文引用:1] [JCR: 0.712]
[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. [本文引用:1] [JCR: 2.395]