基于路径权值的多信道负载均衡路由算法

马少飞， 曲家庆， 严 鹏， 田 华

(1.上海无线电设备研究所, 上海 200090; 2.上海水文总站, 上海 200232)

基于路径权值的多信道负载均衡路由算法

马少飞1， 曲家庆1， 严 鹏1， 田 华2

(1.上海无线电设备研究所, 上海 200090; 2.上海水文总站, 上海 200232)

针对水文监测系统无线Mesh网络中传输数据流量大、路由节点固定的特点，提出基于路径权值的多信道负载均衡路由算法，通过对每条链路容量进行预测，以Dijkstra准则选择最优路径，达到对负载流量均衡分配、提高网络吞吐量的目的。OPNET仿真结果表明：新算法使信道资源得到充分利用，比AODV算法网络吞吐量提高了3倍，具有更小的传输延迟。

网络； 负载均衡； 多信道

0 引言

智慧海洋工程以实现海洋资源共享、海洋活动协同，挖掘新需求，创造新价值，达到智慧经略海洋为目的，要建设智慧海洋必须以完善的海洋信息采集与传输体系为基础，《长江口海洋环境多模监测网关键技术研究与应用示范》课题，采用多模通信技术，在海上移动网络覆盖不到的区域建立无线Mesh专网，满足视频、图像等大数据的可靠传输，通过无线Mesh专网与商用网络的无缝融合，为近海海域提供Internet接入服务，实现长江口海洋环境监测数据传输。

针对无线Mesh网络的研究涵盖了从应用层到物理层的各个层次[1-2]，主要是根据网络的实际应用设计合适的协议和算法，其路由算法大多沿用Ad hoc网络协议[3]，如DSR[4]，AODV[1，5]，DSDV等。文献[4]和文献[5]提出的AODV协议和DSR协议是两种被广泛应用的源发起按需路由协议，具有较低的路由开销且实现简单，但二者均以最小跳数作为路由判据，得到的往往不是最佳路由，其泛洪广播占用了较大的无线信道带宽，增加了分组的发送等待时延，在无线Mesh网络中，节点通常是静止的，由于AODV和DSR路由协议没有考虑负载均衡的情况，当数据业务增大时，处于中心位置的节点就会发生拥堵。文献[6]虽然考虑了负载均衡机制，但其网络节点都处于单信道环境，无法发挥无线Mesh网络多信道条件下的性能优势。

如果采用以上传统算法作为长江口海洋环境监测系统无线Mesh网络的路由算法，将会面临节点容量不足、视频传输延迟大、数据传输速率低等问题，难以满足系统需求。

本文根据海洋环境监测系统传输数据量大、区域广等特点，同时考虑了负载均衡和多信道的使用，提出了一种基于路径权值的多信道负载均衡路由算法，以经典的Dijkstra算法为节点选择最优路径，提出了链路负载的预测方法，最后利用OPNET仿真平台对AODV算法和新算法的性能进行了对比。结果证明，新算法比AODV算法网络吞吐量提高了约三倍，且具有更小的传输延迟。

1 海洋环境监测网

海洋环境监测网是在海上无线Mesh专网，如图1所示，每个观测站是无线Mesh网络中的一个节点，负责收集海洋环境数据终端的数据并将其通过无线Mesh网络传输到陆上监测中心。在网络覆盖区域内，每个无线Mesh网络终端通过观测站组成的网络与其它终端通信，在陆上监测中心建立无线Mesh网络与Internet、移动网络的网关，实现海上终端的上网功能。

图1 海洋环境监测网络示意图

多信道无线Mesh网络主要包括无线路由器、无线接入路由器和网关三部分。无线路由器为传输数据选择到监测中心的最优路径；无线接入路由器具有路由功能的同时，还能提供无线提供接入服务；网关通过有线链路将Mesh网与Internet连接，为用户提供宽带接入服务。对于海上观测站的无线Mesh网络节点来说，只需要无线路由器和无线接入路由器。

2 算法研究

2.1路径权值分配

无线Mesh网络节点传输数据时有多条路径可供选择，本文以Dijkstra算法作为选择最优路径的准则。定义一条路径的权值W为该路径上所有链路的最小权值，表示该路径的带宽受到其瓶颈链路的限制，所以在路径选择时，节点优先选择权值最大的路径。

对网络中各个链路的负载φ视为已知，得到链路i的容量为

(1)

式中：B为信道带宽；In(i)表示链路i干扰范围内的所有链路。可以看出，链路i上的负载越大，它所能分享到的信道带宽就越大；反之在链路i干扰范围内其他链路的负载越大，它分享到的带宽就越小，式(1)表示链路i的带宽占有情况。用φ′(i)表示链路i的当前负载，得到链路i的剩余容量为

(2)

在选择路由时，将W(i)作为每个链路的权值。

2.2负载均衡原理

当网络中的节点数目增加或数据业务量增大时，网络吞吐量及性能受到限制，负载均衡的目的是将网络负载分配到网络中有足够带宽资源的节点，降低网络拥塞的可能性，提高网络吞吐量，减小数据传输延迟[6-8]。

a) 为每个负载依次选择第1条最佳路；

b) 再为其选择第2条最佳路由；

……

m) 找到第M条路由或者不存在可用的路由。

把N×M次的寻路操作称为一轮寻路，得到负载Tn的第m条期望负载：

(3)

(4)

(5)

一轮寻路结束后，每个链路上的负载都得到了准确的预测，利用新的预测结果计算各个链路的容量C，就可能找到更优的信道分配和路由方案，整个路由算法流程如图2所示。

图2 算法流程图

3 实验结果与分析

在OPNET仿真平台中，对文献[3]的AODV算法与本文提出的算法进行了仿真，验证本文算法性能。仿真场景为25个节点随机均匀分布在网络当中，每个节点配有两块无线网卡，整个网络共有12个不同信道，每个信道带宽为11 Mbps，在网络中随机选择20对节点为它们分配不同的CBR UDP负载，数据流从第10 s依次开始到100 s结束。定义网络在时刻t的吞吐量

(6)

式中：N为网络中端到端链路的个数；Ti(t)为第i条链路在时刻t内收到的所有数据比特数。定义第i条链路的平均延迟

(7)

式中：K为该链路i在仿真时间内收到的数据包总数；Ti(t)为该链路上的第k包的延迟，其中包括排队等待时间和数据传输时间。

图3是网络吞吐量随时间关系，横轴表示时间，纵轴表示网络吞吐量(Mbps)，AODV算法的吞吐量大致在4 Mbps左右趋于饱和，当网络饱和时无线节点将处于避退状态，吞吐量将会降低。

图3 网络吞吐量

本文的新算法采用多信道的网络将干扰划分到了不同的信道上，大大减少了通信碰撞概率，可以使网络整体吞吐量提高3倍以上。同时由于新算法在选路时考虑了负载的平衡，并将优化后的路径信息反馈给信道进行重新分配，从而使网络中的信道资源得到更充分的利用。图4是20个节点的平均传输延迟，为了能直观地分析延迟状况，将不存在通路的传输延迟统一设为2 s，可以看到，对于采用AODV算法的单信道网络，第6个和第12个路径由于没有可用路径而不能相互通信，可见单信道无线网络的实际容量是很低的，而本文提出的算法的网络是多信道网络，这20个节点都能正常传输，而且采用新算法比AODV算法具有更小的延迟，且算法的最大延迟不超过0.35 s。

图4 节点传输延迟

4 结论

本文的路由算法采用Dijkstra算法选择最优 路径，并提出负载平衡路由策略，同时采用多信道网络传输，将网络负载均衡地分配到高质量的路径上。与AODV算法相比，网络吞吐量提高了3倍；具有更小的数据传输延迟；由于是多信道网络，即使有20个节点时也能正常传输。基于算法的优点，采用本文算法的无线Mesh网络能够容纳更多节点，数据传输速率更高，时延更短，为长江口海洋环境监测系统传输视频、图像等大数据提供了有力的保证。此外，Dijkstra算法虽是最优路径选择的经典算法，但其在时间效率和空间效率等方面存在严重不足，这也是本文今后需要研究改进的方向。

[1] 王月姣.无线Mesh网络路由协议研究[D].上海：上海交通大学, 2008： 4-13.

[2] 沈强,方旭明,宋文.无线Mesh网络路由协议研究[J] 数据通信, 2005,(4): 30-33.

[3] Bruno R, Conti M, Gregori E. Mesh Networks: Commodity Multihop Ad Hoc Networks[J]. IEEE Communications Magazine, 2005, 43(3): 123-131.

[4] Majumder K, Sarkar S.K. Performance Analysis of AODV and DSR Routing Protocols in Hybrid Network Scenario[C]. India Conference (INDICON), Annual IEEE, 2009: 1-4.

[5] Perkins C, Belding-Royer E, Das S. Ad Hoc On-demand Distance Vector (AODV) Routing[R]. IETF RFC 3561, 2003(3): 3-6.

[6] 王颖. 无线Mesh网络中负载均衡机制的研究[D].长沙：湖南大学, 2010: 7-20.

[7] 陈祥.无线自组织网络负载均衡路由研究[D].成都：电子科技大学, 2007: 16-19.

[8] Manikantan D, Shila, Anjali T. Load-aware Traffic Engineering for Mesh Networks[C]. Proceedings of 16th International Conference on Computer Communications and Networks. IEEE press, 2007: 1701-1704.

AMulti-channelLoadBalanceRoutingAlgorithmBasedonPathWeigh

MAShao-fei1,QUJia-qing1,YANGPeng1,TIANHua2

(1.Shanghai Radio Equipment Rasearch Institude, Shanghai 200090, China;2.Shanghai Hydrological Sation, Shanghai 200232, China)

For the characteristics of heavy traffic and fixed router node in wireless mesh network of hydrological monitoring system, a multi-channel load balance routing algorithm based on path weight is proposed. By forecasting capacity of each link and choosing the optimal path with Dijkstra criterion, the load traffic is balanced and network throughput is increased. The simulation result on OPNET shows that the new algorithm is three times higher than AODV for network throughput, has smaller propagation delay and makes full use of the channel resources.

network; load balance; multi channel

1671-0576(2017)02-0056-04

2016-11-23

马少飞(1991-)，男，硕士，主要从事信息与信号处理技术研究。

TN911.7

A