WMN中一种基于干扰感知的负载均衡路由协议*

毛誉熹，卢汉成，卢 昊

(中国科学技术大学电子工程与信息科学系，安徽合肥230027)

0 引言

无线 Mesh网络(WMN，Wireless Mesh Networks)利用无线多跳网状拓扑为用户提供到Internet的宽带接入。由于其易于维护、较强的鲁棒性和可靠的服务覆盖率，无线Mesh网络作为3G蜂窝系统和无线局域网的替代方案，吸引了越来越多的兴趣［1］。特别是，近年来随着无线网络设备性能的提升，无线Mesh网络越来越多地用来承载具有QoS(Quality of Service)约束的应用业务，如高质量视频流媒体，声音，实时数据等，这些业务对带宽、延时、延时抖动等形式的QoS的有严格的要求。

无线Mesh网络中对提供QoS机制的问题研究很活跃［2－4］，包括拥塞控制、QoS路由协议和 MAC协议、QoS跨层协议设计及信令机制等多个方面。无线Mesh网络中的干扰是影响无线网络容量和可扩展性的重要因素。与有线网络相比，无线网络最大的特点是无线信道的共享特性。无线网络中的干扰引起网络容量下降，因此在无线资源分配和路由时，避免热点区域，选择干扰较小的路径，可以获得更高的频谱效率［5］。

1 相关工作

传统的基于“最小跳数”的路由判据无法考虑链路质量，不能有效地避免拥塞区域并且公平性很差，导致所找到路径的吞吐量大大低于最大可用吞吐量［2］。文献［6］提出一种用于多信道无线Mesh网络的路由判据WCETT，通过计算信道传输速率，并考虑了流内干扰，但仍然没有考虑流间干扰。在计算流内干扰时WCETT忽视了一种情况，即当两个链路的距离足够远时，这两个链路能够同时进行传输。文献［7］对WCETT进行了改进，从信道多样性、干扰感知和负载均衡的角度考虑，提出了路由判据WCETTR－LB。文献［5］提出了用于超宽带无线网络的IA－AODV(Interference Aware－based Ad－Hoc On Demand Distance Vector)协议，该协议可以选择干扰最小的路径，但该方法没有考虑流内干扰。文献［8］中选择平均SIR最大路径的干扰感知路由协议，但是这种方法没有考虑所选信道的拥塞情况。在文献［9］中，路由判据MIC同时考虑流间干扰和流内干扰，但是MIC只包含可能发生干扰节点的个数，而没有考虑到实际的负载和具体的干扰情况。

2 路由判据－PIL

为了衡量无线Mesh网络中的干扰，文中提出一种路由选择判据PIL。PIL反映了无线Mesh网络流间干扰和流内干扰。它包含两个部分:流间干扰和拥塞水平LIC(Level of Interference and Congestion)和流内干扰水平LII(Level of Inter－flow Interference)。

2.1 流间干扰和拥塞水平LIC

无线Mesh网络性能受到不同链路之间相互干扰的影响，无线网络干扰可以分为流内干扰和流间干扰。属于不同数据流上的两个链路，如果使用同一信道并在彼此干扰范围内，那么这两个链路则存在流间干扰。在这里考虑一个链路对两跳邻居范围内链路的干扰情况，定义节点i对信道c的占用率如下:

式中，Ri(c)是节点i的邻居节点集合，vijc表示从节点i的到节点j的数据速率，bijc表示从节点i的到节点j的链路带宽。定义链路l对已有链路产生的干扰大小为:

式中，Nl(c)为链路l的发送节点两跳范围内邻居节点集合。LIC反映了链路l对已有数据流产生的干扰水平，这种干扰大小与两跳范围内邻居节点的负载有关。

2.2 流内干扰水平LII

除流间干扰之外，属于同一流的链路也会相互竞争使用无线信道。如果属于同一个路径上两个链路使用同一信道，而且在彼此干扰范围内，那么这两个链路就存在流内干扰。文献［10］对流内干扰进行了深入研究，发现流内干扰程度与路径节点跳数有直接关系。现对无线网络路径有效带宽和跳数的关系进行仿真。仿真场景采用线性拓扑网络，节点MAC层协议采用802.11协议分布式协调功能，所有节点使用同一信道，无线链路速率为2 Mb/s。相邻节点的距离为230 m，无线传输半径为250 m，载波侦听范围为550 m。

图1中圆点曲线是仿真得到的没有流间干扰时归一化路径有效带宽与跳数的关系。从图1中可以看出当跳数小于4时，随着跳数的增加，路径有效带宽显著下降。所以，设计Mesh网络路由判据时必须考虑由流内干扰对网络性能的影响。

图1 归一化路径有效带宽与跳数的关系Fig.1 Normalized path bandwidth vs.hops

结合仿真结果，并根据文献［10］中路径有效带宽与路径跳数的关系，采用以下公式描述流内干扰水平:

式中，α是一个与网络拓扑有关的常量，n是路径的跳数。这样定义的理由是当路径跳数小时(n≤α)，这些链路相距比较近，链路之间产生流内干扰，跳数越大流内干扰越严重，那么LII越大。当跳数足够大时(n≥α)，同一流上相距足够远的链路不会产生相互干扰，流内干扰保持不变，因此LII值为固定值。

利用LII通过公式Bavailable=LII·Blink可以得到没有流间干扰时路径有效带宽，其中Blink是链路带宽。图1是仅考虑流内干扰，由LII估计的理论归一化有效带宽和仿真结果比较(α=4)。对比结果表明LII能有效反映无线Mesh网络中流内干扰。

2.3 路由判据PIL

为了描绘无线Mesh网络中一个路径干扰情况，同时考虑该路径上流内干扰和流间干扰。结合LIC和LII定义路由判据:路径干扰水平PIL:

式中，p表示无线网络中从源节点到目的节点的一条路径。在PIL中，LICl表示该路径上链路l对已有链路造成的流间干扰的大小。LII反映了该路径上流内干扰大小。PIL综合反映了流间干扰和流内干扰。IA－DSR协议通过路由判据PIL实现两个目的:①避开网络中的“热点区域”，控制网络拥塞，减小网络平均端到端时延，达到负载均衡的目的;②减小流间干扰，提高路径的吞吐量。下面将具体描述IA－DSR路由协议。

3 IA－DSR协议设计

文中通过改进动态源路由协议DSR(Dynamic Source Routing)实现了提出的PIL路由判据，并提出基于干扰感知的负载均衡路由协议IA－DSR。IA－DSR建立在DSR协议基础上，采用与DSR协议类似的路由机制。

在IA－DSR中，节点在MAC层周期性检测该节点信道利用率信息。每个节点周期性地向邻居节点广播该节点信道占用率信息和第一跳邻居节点的信道占用率信息。每个节点接收到这些信息后，便可得到该节点一跳邻居和两跳邻居节点的负载信息，利用式(2)得到该节点的LIC值。

IA－DSR分为两个部分:路由发现和路由维护。IA－DSR协议与DSR协议主要区别体现在路由发现过程中，具体的路由发现过程如下:

1)IA－DSR协议中源节点通过发送一个路由请求数据包(RREQ)，发起到目的节点的路由请求。与DSR协议不同的是，IA－DSR协议中，需要在RREQ数据包中增加一个干扰LIC字段，用于记录该链路受到的干扰值。

2)当节点接收到发往目的节点的路由请求数据包RREQ后，则在RREQ中添加本节点LIC信息，并发送给其邻居节点。

3)当RREQ到达目的节点时，目的节点得到该路径上所有节点LIC值。目的节点收到的每个RREQ，都代表一条从源节点到目的节点的可行路径，并且可以从RREQ的LIC字段获知每条路径的流间干扰信息。目的节点为每个路由请求包都生成一个路由应答包RREP，然后将完整路径信息及其LIC值返回给源节点。

4)源节点收到RREP后，根据RREP数据包中包含的路径信息得到路径跳数并根据式(3)得到LII，结合RREP中的干扰信息LIC计算路径干扰信息PIL，并记录在路由表中。当源节点需要发送数据包时，如果其路由表中已有到达目的节点的路径，则选择这条对已有数据流干扰值最小的路径。

为使路由协议能够适应无线Mesh网络拓扑及负载的动态变化，除了采用与DSR协议相同的路由维护机制外，IA－DSR协议周期性地将所有节点的路由表清空，然后重新发起一次路由发现过程进行路由更新。

4 性能仿真及结果分析

本节采用NS2［11］网络仿真器进行仿真实验，并对基于干扰感知的负载均衡路由协议IA－DSR的性能进行实验验证。在仿真实验中，比较对象是AODV路由协议和一种新的干扰感知路由协议ALIR［12］。现在以下仿真场景中对这三种协议进行性能仿真和比较。

4.1 仿真场景和参数设置

1)仿真拓扑结构采用8×8网格拓扑，64个节点均匀分布在1 500 m×1 500 m的区域内，相邻节点距离为200 m。节点传输半径为250 m，载波侦听范围为550 m。

2)网络中有5条CBR(Constant Bit Rate)数据流，数据包大小为1 000 bytes，每条CBR数据流的源节点和目的节点随机选择。每条CBR数据流负载由20 kb/s增加到420 kb/s时，测试网络各项性能。

3)无线节点MAC层协议采用802.11协议分布式协调功能。无线链路速率设为2 Mb/s。每次仿真时间为100 s。α的取值为4。

为了减小网络仿真时仿真随机数种子的选取对实验结果的影响，在实验中对每个数据点取5次不同随机数种子情况下的实验结果的平均值作为最终结果。

4.2 仿真结果分析

图2、图3、图4和图5分别给出了在AODV路由协议、ALIR协议和IA－DSR协议下，平均吞吐量、分组投递率、平均端到端时延和归一化寻路开销随CBR数据速率变化的关系。

由图2可以看出，当网络负载比较低时(＜100 kb/s)，三种路由协议的性能差距不大，这主要是因为网络负载低时三种路由协议都会选择“最小跳数”的路径;当网络负载高时，IA－DSR协议有较好的表现，其平均端到端吞吐量比AODV协议有21%的提升，主要是因为随着网络负载增加，链路之间的干扰会更严重，造成吞吐量下降，而IA－DSR协议在选路时能够感知网络中干扰，从而选择干扰最小的路径，提高网络整体的吞吐量。

图2 平均吞吐量与CBR速率的关系Fig.2 Average throughput vs.CBR rate

图3给出了三种协议下分组投递率随着CBR速率变化的曲线。从图3中可以看出在网络负载较低的情况下(＜100 kb/s)，三种协议均能达到较高的分组投递率。在所有业务负载下，IA－DSR协议的性能始终优于其它两种路由协议。

图4是三种路由协议下平均端到端时延与CBR数据速率的关系。网络负载增加导致数据包排队时延增加，从而导致数据包端到端时延增加。相比AODV协议，IA－DSR协议在最好的情况下(CBR速率为180 kb/s)，时延能够降低68.7%。当CBR速率超过100 kb/s时，AODV协议的平均时延最大，这是因为AODV协议路由选择时没有考虑网络拥塞，导致该路径上时延增加。而IA－DSR在路由选择时考虑到链路的拥塞大小并选择拥塞水平较小的路径，因此可以降低网络平均端到端时延。

图3 分组投递率与CBR速率的关系Fig.3 Packet delivery Ratio vs.CBR rate

图4 平均端到端时延与CBR速率的关系Fig.4 Average end －to－end delay vs.CBR rate

图5是归一化寻路开销与CBR速率的关系。从图5中可看出，IA－DSR协议开销较AODV协议有少量增加，这主要是因为IA－DSR协议引入了报文开销和少量的计算开销。增加的报文开销是由周期性交互负载信息引起的，但平均增加的开销只有10%左右。

图5 归一化寻路开销与CBR速率的关系Fig.5 Normalized routing overhead vs.CBR rate

综合来看，尽管IA－DSR协议开销有所增加，但取得了网络总体吞吐量、端到端延时和投递率性能的总体提升，获得了开销和性能的良好折中。

5 结语

文中对无线Mesh网络中链路之间的干扰进行研究时，综合考虑了流内干扰和流间干扰。在此基础上，提出一种干扰感知的负载均衡路由判据，该路由判据有效结合了无线网络中的流内干扰和流间干扰。结合该路由判据，提出一种基于干扰感知的负载均衡路由协议IA－DSR，该路由协议能够选择干扰最小的路径。仿真结果表明，IA－DSR协议在不显著增加路由开销的情况下，可以有效提高网络整体吞吐量和分组投递率，减少端到端时延。

［1］LIU L，ZHU L，LIN L，et al.Improvement of AODV Routing Protocol with QoS Support in Wireless Mesh Networks［J］.Physics Procedia，2012(25):1133 －1140.

［2］DE COUTO D S J，AGUAYO D，BICKET J.A highthroughput Path Metric for Multi－hop Wireless Routing［J］.Wireless Networks，2005，11(04):419 －434.

［3］LI Y，ZHOU L，YANG Y.Optimization Architecture for Joint Multi－path Routing and Scheduling in Wireless Mesh Networks［J］.Mathematical and Computer Modelling，2011，53(03):458－470.

［4］KIM T S，YANG Y，HOU J C.Resource Allocation for QoS Support in Wireless Mesh Networks［J］.IEEE Transactions on Wireless Communications，2013，12(05):2046 －2054.

［5］DE RANGO F，VELTRI F，FAZIO P.Interference A-ware－based Ad－hoc on Demand Distance Vector(iaaodv)Ultra Wideband System Routing Protocol［J］.Computer Communications，2011，34(12):1475 －1483.

［6］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.New York:ACM，2004:114－128.

［7］孙志.基于WCETT的多信道WMN路由量度的研究［J］.通信技术，2013，46(06):82－84.SUN Z.WCETT－based Routing Metrics for Multi－Channel WMN［J］.Communications Technology.2013，6:82 －84.

［8］FAZIO P，DE RANGO F，SOTTILE C.An On Demand Interference Aware Routing Protocol for VANETS［J］.Journal of Networks，2012，7(11):1728 －1738.

［9］YANG Y，WANG J，KRAVETS R.Designing Routing Metrics for Mesh Networks［EB/OL］.Santa Clara:WiMesh，2005(2005)［2013－12－10］.URL:http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.141.5458.

［10］CHEN L，HEINZELMAN W B.QoS－aware Routing based on Bandwidth Estimation for Mobile Ad hoc Networks［J］.Selected Areas in Communications，IEEE Journal on，2005，23(3):561－572.

［11］Fall K，Varadhan K.The network simulator(ns－2)［EB/OL］.California:ISI，2007(2011 －11－5)［2013 － 12 － 20］.URL:http://www.isi.edu/nsnam/ns.

［12］ZHANG X，LIU Q，SHI D.An average link interference－aware routing protocol for mobile ad hoc networks［C］//Wireless and Mobile Communications.Guadeloupe，French:ICWMC＇07，2007:10 －10.