无线网络负载均衡的干扰感知路由度量

李 雪，郁进明，史雨雨（东华大学 信息科学与技术学院，上海 201620）

无线网络负载均衡的干扰感知路由度量

李 雪，郁进明，史雨雨
（东华大学 信息科学与技术学院，上海 201620）

无线信道干扰和负载分布不均匀严重影响无线网络的网络吞吐量、端到端延时等。在已有的路由度量的基础上，充分继承其通过邻居节点负载描述干扰强度的优势，进一步分析节点负载的影响，提出负载均衡的干扰感知路由度量，将干扰邻居节点的数量、负载和距离综合作用结果作为流间干扰强度，使用节点处的平均队列长度捕捉节点负载，并改进期望传输时间消除链路的不对称性，实现负载均衡和干扰感知，避开热点区域。同时将LBIA合并入路由协议。仿真结果表明：该路由度量可以有效地实现网络负载均衡，提升网络整体性能。

无线网状网；路由度量；负载均衡；干扰感知

0 引言

在无线网络中，无线网状网（WMN）［1］因其综合了传统的AdHoc和WLAN的优势，作为3G蜂窝系统和无线局域网的替代方案，成为有前景的下一代无线网络。而路由问题一直是面临的技术挑战之一，为了保证端到端的通信性能，进而获得较高的网络容量，作为路由问题的核心，有效的路由度量对于找到高吞吐量的路径是必不可少的。

1 相关工作

决定路由协议性能最关键的部分是路由度量的设计，找到具有高数据速率、低丢包率和低水平干扰的路径，是衡量路由度量好坏的标准。针对多接口多信道WMN路由度量研究已经广泛展开。HOP［2］作为最早的路由度量机制已经广泛应用到无线多跳网络；ETX［3］引入丢包率来测量链路质量；ETT［4］在 ETX的基础上考虑传输速率，但ETT和ETX均未考虑干扰对于路径选择的影响；MIC［5］是干扰感知路由度量，将延伸到同时考虑流间干扰和流内干扰，还有链路丢包率和传输速率。

ILA（Interference-Load Aware routing metric）［6］用邻居节点的平均负载来衡量流间干扰的强度，但平均负载并不能真实反映流间干扰水平，对路径选择造成不小的偏差。此外ILA未考虑节点本身负载，且基于ETT，会造成链路质量不准确估计。

2 ILA路由度量

首先对现有的干扰负载感知路由度量进行简要介绍，如式（1）所示：

其中，p为路径，n为链路数，m为链路l上的节点数。MTI（Metric of Traffic Interference）捕捉流间干扰如式（2）所示，CSC（Channel Switching Cost）捕捉流内干扰。参数α是用来权衡流内干扰和流间干扰的权重。

其中，ALLij（Average Interference Load）是在信道 C上节点i、j之间干扰邻居节点的平均负载。ETT用来确定传输速率和丢包率的差别。AIL描述干扰节点的邻居节点活跃性，定义为：

其中，ILij（C）是干扰邻居的负载，用平均队列长度来表示。

CSC通过给定使用同一信道的连续链路更高的权重来减少流内干扰，下文将详细讨论。

ILA路由度量捕捉了流间和流内干扰，但仍存在局限性。

3 LBIA路由度量

本文提出负载均衡的干扰感知路由度量（Load Balanced Interference-Aware Routing Metric，LBIA），有以下改进：

（1）通过干扰邻居节点距离对干扰邻居节点负载的计算进行优化，得到更准确的干扰水平。

（2）通过节点负载，选择负载较小的节点作为传输路径，节省等待队列传输的时间，得到较低的端到端延迟。

（3）对原ETT进行改进，消除传输不对称性，提高合理性，正确评估链路质量。

链路l的LBIA定义为：

LBIA由 3部分组成：NIL（Neighbout Interference Load）为邻居干扰节点表征的流间干扰程度，是邻居干扰节点的数量、负载和与受干扰节点间的距离共同作用的结果；NL（Node Load）为被干扰节点自身的负载，由缓存队列的长度来捕捉负载；CSC为流内干扰大小。这样通过关注通信负载、节点负载、丢包率、传输速率、流内干扰和流间干扰，突破现有路由度量的有限性。

3.1 ETT的改进

ETT是应用最广泛的路由度量，但不对称性使得高估链路质量，对路由选择造成偏差，如式（6）所示：

其中，S是数据包大小，Bl是链路l的带宽，ETX如式（7）所示：

其中，df为前向传输比率，是邻居节点周期内成功接收到探测包的比率；dr为反向传输比率，是节点在相反方向成功接收到相应邻居节点的广播探测包。邻居节点周期性地交换小探测包，进而算出ETX，找到有最大传输速率的路径。

但这将导致链路质量估计不准确。式（7）中 df与 dr的权重相等，而实际传输中前向传输节点传送的数据包远大于反向传输收到的ACK数据包，并且反向ACK数据包的链路损失小，导致通信的不对称性，如图1所示。

图1 ETX中数据包不对称性问题

A节点有两条可能的路线，A-B-D或A-C-D。因ETX分配给前向和反向链路相同的权重，所以得到式（8）：

故路径A-B-D和A-C-D路由度量值相等，但根据数据包和大小不对称性，合理地看出链路（A，B）比链路（A，C）性能更好。借鉴参考文献［7］，提出改进 ETT，如式（9）所示：

Bi链路 i的传输速率，S是数据包大小，S/Bi评估出通过链路i传输一个数据包期望时间。改进的ETT很好地消除了传输的不对称性，对基于ETT的LBIA网络性能有很大提高，能够正确评估链路质量。以下公式中ETT均为式（8）。

3.2 NIL邻居干扰负载

NIL邻居干扰负载为：

其中，ETTij（C）是节点 i、j在信道 C上的期望传输时间，ILij为邻居干扰负载。由节点间距离的路径损耗，干扰邻居节点负载和数量表征为：

其中，Load是干扰邻居节点的负载，用平均队列长度来度量，即数据包的数量。PL是路径损耗，ΣNlLoad/10∧（PL/10）为各干扰邻居节点负载经过路径损耗后的负载之和，Nl（C）如式（4）所示，是干扰节点i、j干扰邻居集合。

PL路径损耗为：

其中，d为节点与干扰邻居节点间的距离，davg为两个单跳节点间的平均距离，n为跳数，λ为波长。邻居节点数量一定时，干扰强度随邻居节点与被干扰节点的距离增大而减小。被干扰节点与邻居节点距离一定时，干扰节点数量和负载越少干扰越小。因此流间干扰水平与邻居干扰节点的数量、负载和节点间距离相关。α为权重参数，定义为：

3.3 NL节点负载

被干扰节点负载为：

其中，Li为节点负载，由平均队列长度表示。它表明节点自身负载强度，决定缓存包等待时间与通信能力的强弱，避开重负载区域，提升网络的吞吐量，保证网络性能。

3.4 流内干扰

流内干扰和流间干扰同时存在于WMN中，LBIA中NIL捕捉流间干扰，为了捕捉流内干扰，将 CSC应用于LBIA，与ILA类似。使用不同信道传输数据的节点比始终使用同一信道的节点有更低的流内干扰水平，因此给使用同一信道的连续链路更高的权重，定义为：

其中，CH（i）表示分配给节点i传输的信道，prev（i）是在路径p上节点i的前一跳。设节点i配有多个信道。当节点i向下一节点传输时应使用不同于之前接收到的数据的信道以消除流内干扰。若节点i仍使用接收到数据的信道，则分配更高的权重；若节点i在传输和接收数据时使用不同的信道，则分配一个较低的权重，所以0≤w1≤w2。

综上，LBIA继承了ILA度量描述流内、流间干扰的优势，将干扰与被干扰节点间的距离引入流间干扰估计，得到邻居干扰节点数量、负载和距离多重作用的流间干扰强度，使用节点处的平均队列长度捕捉节点负载，并且通过改进期望传输时间来消除链路的不对称性，这样LBIA度量兼备负载均衡和干扰感知的能力，能够准确地识别出重干扰重负载的区域，避开“热点”区域，合理分配路由，达到提高网络吞吐量，减少端到端时延的目的。

4 LBIA度量的实现

4.1 AODV的修改

对 AODV［8］路由协议进行改进，以 LBIA值取代跳数，即选择LBIA值最小的路径进行数据传输。

4.2 ETX参数获取

利用AODV的HELLO消息来计算ETX。每个节点向邻居节点广播周期性HELLO消息，即1 s，TTL值为1。每个节点记录在w秒内接收的消息，即可算出df和

一条路径的ETX是该路径上所有链路的ETX之和，继而得出ETT。

4.3 负载参数获取

载波侦听会阻止相互干扰范围内两个节点同时传输。节点传输速率会随着同时开始广播连续数据包的节点增多，逐渐低于单独传播速率。据此可通过广播速率判断两节点是否处于相互干扰范围内。

HELLO消息包含当前负载信息。每个节点保存一张记录其邻居节点及其负载的表。当一个节点接收到从邻居节点发来的HELLO消息，它将与邻居表进行核查。若该邻居已经在表中，则更新其负载，否则将该邻居加入邻居表内。如果一个节点从一个邻居节点接收3个连续HELLO消息失败，将会从邻居表内把该邻居节点移除。这样，就可以用邻居表中的负载信息来计算干扰邻居的负载，同时获得节点自身的负载。

5 性能仿真与结果分析

本文采用NS2［10］仿真工具进行仿真实验，将 ILA和MIC作为比较，对LBIA性能进行验证。将NS2模块进行扩展，以支持多信道多接口和改进的AODV路由协议。

5.1 仿真场景和参数设置

用于NS2仿真的场景参数设置如表1所示。

表1 仿真场景参数设置

5.2 LBIA性能仿真及分析

图2～图4分别给出在改变网络中流数情况下，LBI-A、ILA、MIC下网络整体吞吐量、平均丢包率和平均端到端时延的仿真结果。

图4 平均端到端时延与流数的关系

由图2和图3看出，随着流数逐渐增多，平均流吞吐量均有所下降。LBIA平均流吞吐量始终高于 ILA、MIC。流数为6时，LBIA的值为8.5 kb/s，与MIC相比提高了15％。其中MIC最低，因其未动态检测干扰并且为考虑通信负载，而且 MIC中的 ETT还高估了链路质量。ILA虽也基于ETT，由于将干扰和负载考虑在内，其值较MIC有所提升。网络平均流吞吐量与平均丢包率之间存在互补关系［11］，如图3所示，LBIA的值始终低于 MIC和ILA，这与图2得出的结论是一致的。当流数为8时，LBIA的值为 17％，比MIC降低了 10.5％。从图4看出，平均端到端时延随着流数的增多呈现上升趋势，其中LBIA的平均端到端时延增长速度最慢，且始终处于MIC和 ILA之下。流数为 10时，LBIA的值比 MIC降低46.23％。以上表明，LBIA能够较好地均衡通信负载，感知有重负载和干扰的拥塞区域，有效地分配网络通信，以免数据包缓冲很长时间，达到提高网络吞吐量和降低端到端时延的目的。

6 结论

本文在分析ILA的基础上，继承了其利用负载描述流间干扰的优势，通过考虑邻居干扰节点的距离、数量和负载的共同影响以及源节点本身的负载，消除度量的不对称性，提出负载均衡的干扰感知路由度量LBIA，并且将LBIA应用于修改的AODV路由协议。仿真结果验证了LBIA相对于MIC和ILA的优势，可以有效地提高网络吞吐量，降低端到端时延和丢包率，提高网络的整体性能。

［1］黄旭，王子欧，季爱明.基于 ZigBee无线 Mesh网络的温湿度测量系统［J］.微型机与应用，2014，33（9）：89-91.

［2］WILLIAM S.Dataand computer communications［M］.NewJersey：PrenticeHall，1997.

［3］COUTO D S J D，AAUAYO D，BICKET J，et al.Ahighthrough put path metric for multi－hop wireless routing［C］.The 9th MobiCom，San Diego，USA，2003：134-146.

［4］DRAVES R，PADHYE J，ZILL B.Routing in multi-radio，multi-hop wireless mesh networks［C］.MobiCom，Philadelphia，USA，2004：114－128.

［5］Yang Yaling，Wang Jun，ROBIN K.Interference aware load balancing for multihop wireless networks［C］.The Proceedings of the IEEE Workshop on Wireless Mesh Networks，Santa Clara，USA，2005.

［6］SHILA D M，ANJALI T.Load aware traffic engineering for meshnetworks［J］.Computer Communications，2008，31（7）：1460-1469.

［7］GENETZAKIS M，SIRIS V.Acontention-aware routing metric for multi-ratemulti-radio mesh networks［C］.Sensor，Mesh and AdHoc Communications and Networks，2008：242-250.

［8］蔺绍良，龙海南.基于稳定性的 AODV路由协议研究与仿真［J］.微型机与应用，2013，32（20）：48-50.

［9］孙志.基于WCETT的多信道WMN路由量度的研究［J］.通信技术，2013，46（6）：82－84.

［10］于斌等.NS2与网络模拟［M］.北京：人民邮电出版社，2007.

［11］杜辉.无线 Mesh网络路由协议研究［D］.武汉：武汉科技大学，2010.

Load balanced and interference-aw are routing metric for w ireless mesh netw orks

Li Xue，Yu Jinming，Shi Yuyu
（College of Information Science＆amp；Technology，Donghua University，Shanghai 201620，China）

Wireless channel interference and uneven distribution of load affect network throughput and end-to-end delay in WMN.Based on ILA，LBIA is proposed.It inherits advantage of describing the extent of interference by the load of neighbor nodes and further analyzes the influence of the node load.The inter-flow interference extent is measured by the combined result of number，load of interfering neighbor nodes and the distance between nodes and neighbor nodes.The buffer queue length of the node is used to capture traffic load.The expected transmission time is improved to remove the asymmetry of the link.Eventually it can balance the load，be aware of interference and avoid the hot area.The simulation results show that the LBIA routing metric can effectively achieve load balancing and improve the whole network performance.

WMN；routing metric；load balancing；interference-aware

文献标识码：A 文章编号：1674-7720（2015）22-0064-04

李雪，郁进明，史雨雨.无线网络负载均衡的干扰感知路由度量［J］.微型机与应用，2015，34（22）：64-67.

2015-07-22）

李雪（1990-），女，工学硕士，主要研究方向：WMN无线通信系统，通信系统建模与仿真等。

郁进明（1965-），男，副教授，硕士生导师，主要研究方向：无线信道系统及其相关应用，无线传感网等。

史雨雨（1990-），女，工学硕士，主要研究方向：Z igBee无线通信系统，路由算法与协议等。