基于“温度”的无线Mesh网络负载均衡路由协议研究

杨峰　杨艳华　彭杰　吴启祥

摘要：为了解决无线Mesh网络路由开销过大和负载不均的问题，分析了无线Mesh网络的网络架构和业务特点，并提出了一种基于“温度”的无线Mesh网络负载均衡路由机制。在建立路由时为每个节点设置一个温度数值，并依据该数值确定数据的路由方向，进而选择负载较轻的备选路由节点，以确定最终的路径，从而有效控制网络中的路由开销，在保障网络负载均衡的同时提高了无线Mesh网络的整体路由效率。

关键词：无线Mesh网络 温度值 负载均衡 路由机制

1 无线Mesh网络概述

无线Mesh网络（WMN，Wireless Mesh Network）是一种新型的宽带无线网络架构，它不同于传统的无线网络，可以看成是无线局域网（WLAN，Wireless Local Area Network）和Ad Hoc网络的融合[1]。无线Mesh网络节点之间以完全对等的无线连接方式构成网状网络，这大大提高了网络部署的延展性。

WMN的网络架构如图1所示，包括网状网端口节点（MPP，Mesh Point with a Portal）、网状网节点（MP，Mesh Point）、网状网接入节点（MAP，Mesh Access Point）和用户终端节点（STA，Station）。其中，MAP实现STA接入Mesh网络的功能；MPP实现Mesh网络与外部网络的互通功能。

WMN与传统无线网络最大的区别是：WMN网络中的节点相互作为其邻居节点的路由器，通过节点转发，可实现网络内部节点之间和内部节点与外部网络之间的通信。WMN网络中的节点既可以作为数据转发实体，又可以作为连接到其他有线网络的桥接器。

对于用户终端节点来说，WMN的骨干部分主要是为用户提供稳定的无线接入功能，所以通常WMN的骨干Mesh节点是固定不动的，网络架构以及数据路由方式与Ad Hoc网络还是有所不同[2]。另外，用户接入Mesh网络主要的目的是通过网关节点接入Internet，故可以预计网络的主要业务存在于各节点与网关节点之间[3]。由于WMN网络的这些特点，因此如何为WMN中的业务选择一条最佳的传输路由，将直接影响WMN的数据传输效率[4]。

2 研究现状

由于WMN继承了Ad Hoc的许多特性，因而适用于移动自组网的路由协议常被引入使用[5-7]。目前，主流的Ad Hoc路由协议是自组网按需距离矢量路由（AODV，Ad hoc On-demand Distance Vector Routing）协议，它是数据驱动的距离矢量协议。其特点是按需维护路由信息，该方法最大程度地减少了维护的路由信息数量，但由于在没有路由时需要执行路由学习查找过程，增大了数据的传输时延以及网络中寻路信息的数量。尤其是对于频繁上下线的用户来说，路由信息将频繁改变，这大大增加了网络的路由开销，严重影响了网络的整体性能。

此外，虽然无线Mesh网络与Ad Hoc网络的拓扑结构类似，但路由技术还是有本质区别[8]。文献[9]首先给出一种分层的部署场景模型及相关假设，并在此基础上利用混合整数线性规划（MILP，Mixed Integer Linear Programming）方法对测量报告（MR，Measurement Report）部署问题进行形式化描述；然后提出一种基于网络流的MR部署贪心算法NF Greedy，该算法以迭代的方式从MR候选位置集中选择权重最大的节点进行相应的节点部署，通过一系列仿真实验将NF Greedy算法与现有算法进行对比，实验结果表明该算法与基于MILP的算法相比，虽然所部署的MR数量略多，但是能够适用于较大规模的WMN。文献[10]提出了一种针对无线Mesh网络的具有公平性拥塞控制策略，与IEEE 802.11e EDCA相比，在有效缓解网络拥塞的同时，可以保证高优先级业务与低优先级业务之间的公平性，使整个系统吞吐量提高了6.3%，防止了“饿死现象”的发生，并通过仿真证明了该算法的有效性。

由于Ad Hoc网络路由技术的主要目标是为了适应网络快速变化的拓扑结构，且设备的业务也受能量限制，因此重点关注路由的节能问题。而无线Mesh网络拓扑相对稳定，大容量、高传输可靠性和低时延是路由设计的首要目标。

3 基于“温度”的WMN负载均衡路由

机制

上述文献通过不同方面对WMN的路由协议进行研究，以优化网络性能。本文针对WMN的网络架构和业务特点，提出了一种基于“温度”值的无线网状网负载均衡路由管理方法，可以有效减少网络中的路由开销，保障网络路由的负载均衡，提高路由的建立效率。本文的主要思想来源于空调的制冷效果，空调制冷的特点如下：

（1）距离空调越近温度就越低；反之，越远的温度就越高。

在无线网状网中，终端接入的主要目的是接入Internet，可以预计网状网网关节点（端口节点）的業务量将是最繁重的。距离端口节点近的Mesh节点由于要为其他节点提供转发业务，因此业务量也较重；距离端口节点较远的Mesh节点由于承担的转发业务较少，或者仅仅为终端提供接入功能，因此业务量较少。

（2）使用空调时，为了保持室内的制冷效果，通常将门窗密闭以防止冷气扩散。

在无线网状网中，路由的建立和维护的过程中会产生大量的路由开销。如果不对这些开销进行控制，扩散到外网，不仅浪费了网络资源，而且会对外网产生一些不必要的干扰。因此，需要采用一种机制将域内的路由信息限制在本Mesh网络内部。

基于以上两个方面启示，本文的路由机制步骤如下：

（1）网状网端口节点广播声明消息

网状网组网完成后，所述端口节点向网状网内部周期广播一个网状网端口节点也称为根节点的声明消息（RANN，Root Announcement），声明自己为端口节点。该声明消息包含的内容如下：

◆源地址（产生RANN消息的节点地址）：MPP节点地址。

◆本节点地址：本节点的IP地址。

◆上一跳地址：这里初始值设置为MPP节点。

◆温度值：网状网节点的默认值是一个足够大的正整数。当MPP节点产生RANN消息向外广播时，将其温度值修改为0。

◆跳数值TTL：该TTL值是为了防止RANN消息被无限转发。RANN消息每走一跳，TTL值减1，当TTL值为0时，RANN消息停止转发。根据网络的规模设置一个合适的TTL值，如网络的节点数为10，则TTL值为15基本可以满足网络中的所有节点都能接收到RANN消息。

（2）端口声明消息处理

网状网内的Mesh节点收到RANN消息后，根据温度值判断是否已经接收过该RANN消息，如果已经接收过，则丢弃该消息；否则，接收该消息。

节点收到RANN消息后提取其温度值，与本节点的温度值进行比较，当该温度值不小于本节点的温度值时，则丢弃该消息；否则，接收该消息。

接收该RANN消息，提取其源地址、上一跳地址、温度值、TTL值。

建立本节点到上一跳节点的路由，将RANN消息中本节点地址加到本节点的路由表的上一跳地址。将该消息的温度值加1，作为本节点的温度值。

同时，向上一跳节点单播返回一个路由回复消息（RREP，Route Reply）。该RREP消息包含的内容如下：

◆源地址（产生该RREP消息的节点地址）：本节点地址。

◆上一跳地址：本节点地址。

◆下一跳地址：向本节点转发RANN消息的节点地址，即RANN消息中的上一跳地址。

◆目的地址：产生RANN消息的节点地址，该路由回复消息RREP最终会转发给节点MPP。

然后将RANN消息的源地址不变，上一跳地址更新为本节点的地址，温度值更新为本节点的温度值加1，TTL值减1，并向与本节点相连的节点转发该RANN消息。

（3）路由回复消息RREP的处理

提取其下一跳地址，与本节点地址进行比较，如果一致，则接收该消息；否则，丢弃该消息。

节点接收该消息后，提取其上一跳地址，添加到本地路由表的下一跳地址，建立到发送该消息的节点的路由。如果本节点是MPP节点，则销毁该消息；如果本节点不是MPP节点，则转发该RREP消息，具体步骤如下：

◆将RREP消息的下一跳地址设置为本地路由表的上一跳地址。

◆将RREP消息的上一跳地址设置为本地节点的地址。

◆沿下一跳地址方向转发该RREP消息。

（4）路由建立过程完成后，节点的路由表里就存储了到端口节点的路由，同时保存了到温度值较高且路由回复信息由其转发的节点之间的路由。

（5）域内各节点向周围一跳节点发送一个信标帧，包含自己的温度值和IP地址。收到周围节点发送来的信标帧后，获取周围节点的IP地址和温度值以确定冷源的方向。

（6）Mesh节点收到数据包后，查看该数据包的目的地址是否为Mesh内部地址。如果不是，则将该数据包转发给其周围温度值较低的节点，直到接收数据包的节点为端口节点，再由端口节点转发到外网。

如果该数据包的目的地址是Mesh内部地址，首先查找本地路由表，若没有到该目的地址的路由，则将该数据包转发给其周围温度值较低的节点，当周围有多个温度值一样的节点时，通过比对周围温度值较低节点的负载情况，选择负载较轻的节点作为下一跳节点，以保障网络的负载均衡。直到找到路由，将数据包送至目的地。

4 具体实施方式

下面将结合实例来说明本文的具体实施方式。

实例1：网内节点与网外节点之间的通信（节点MP8与节点X通信）（见图2）

具体步骤如下：

（1）依据端口节点MPP的声明信息及网络内部节点对该消息的回复，以节点MPP为冷源的树状路由在网络中建立，并为网内各Mesh节点分配了温度值。

（2）节点之间进行温度值的交互，确定冷源的方向。

（3）如果节点MP8有数据包要路由到节点X时，发现X不是Mesh内部节点，则沿着冷源的方向转发路由请求信息到周围温度值低的节点。MP8转发路由请求消息到MP7或MP9，由于MP9、MP6的温度值与MP7一样，因此MP7将转发路由请求消息到MP3或MP2，然后转发路由请求消息到MPP。

（4）对于步骤（3）中的温度值相同的节点，通过比较其待发数据包的数量，选择负载较轻的节点作为下一跳节点。具体来说，当节点MP8发现下一跳节点有多个选项时，发送待发送数据包查询消息给待选的下一跳节点MP7和MP9，这两个节点收到消息后，反馈待发送数据包信息給节点MP8，由节点MP8决定选择哪个节点作为下一跳节点，这种通过比较路由节点负载情况以决定下一跳节点的机制，可有效保障网络的负载均衡。

（5）当每个路由节点选定后，由MPP将路由请求消息转发给与其相连的外网路由器，最终建立节点MP8与节点X之间的路由：MP8→MP7→MP3→MPP→X。

（6）节点MP8沿着建立好的路由发送数据到节点X。

通过这种方式，网内节点与网外节点可以迅速建立路由进行相互通信。对于终端用户来说，通过无线Mesh网络接入Internet是其最终目的。通过这种路由机制，可以使用户快速接入网络，提高入网体验。

实例2：网内节点之间的通信（见图3）

具体步骤如下：

（1）依据端口节点MPP的声明信息及网络内部节点对该消息的回复，以节点MPP为冷源的树状路由在网络中建立，并为网内各Mesh节点分配了温度值。

（2）如果节点MP8要发送数据给节点MP2，首先判断MP2为网络内部节点，然后检查是否有到节点MP2的有效路由。

（3）如果没有到节点MP2的有效路由，则节点MP8立即转发路由请求信息到周围温度值低的节点MP7或MP9，具体选择节点MP7还是节点MP9的方法与实例1中步骤（4）一致。

（4）重复步骤（2）和（3），建立一条MP8→

MP7→MP3→MPP→MP2的路由。

（5）节点MP8沿着建立好的路由发送数据到节点MP2。

通过这种方式，网内节点之间也可以迅速建立路由。由图3可以看出，在节点MP8与节点MP2之间没有建立最短路由，但是在实际组网过程中，网状网节点数量不大。另外，由于作为终端用户接入Mesh的主要目的是通过其接入Internet，所以这种网内节点之间的通信不是业务的主流。基于此，这种路由机制可以满足用户接入Internet和与Mesh内节点之间的通信需求。

5 结论

本文针对WMN的网络架构和业务特点，并结合空调的制冷原理，提出了一种基于“温度”的无线Mesh网络路由机制，在建立路由时为每个节点设置一个温度数值，使得网络的寻路机制方向明确，寻路效率高。通过采用先应式机制，在数据发送之前建立树状路由，并且对数据包的目的节点进行判断，如果数据包的目的节点为网外节点，则直接转发给端口节点，以进一步减小接入时延。在路由建立过程中发送RANN消息时采用广播方式，而其余时间采用单播消息进行路由控制。由于WMN的网络特点，网络扩展的概率较小，因此不需要频繁地广播RANN消息，可以明显降低网络的路由开销，从而保障网络的负载均衡以及提高网络的路由效率。

参考文献：

[1] 刘波，周丹. 无线Mesh网络协议标准研究[J]. 信息技术与标准化， 2009（3）： 27-29.

[2] 张牧，严军荣. 802.11s无线mesh网络研究进展与挑战[J]. 计算机工程与应用， 2010，46（22）： 75-79.

[3] 王东，邵春菊，刘佳. Mesh网络关键技术及组网性能分析[A]. 2008年中国通信学会无线及移动通信委员会学术年会论文集[C]. 2008.

[4] 胡云. 面向Internet接入無线Mesh网络性能分析及协议优化研究[D]. 合肥： 中国科学技术大学， 2011.

[5] 吴玮. Ad Hoc网络拥塞检测与控制的研究[D]. 哈尔滨： 哈尔滨工业大学， 2011.

[6] 沈呈，陆一飞，夏勤，等. 基于节点区分和跨层设计的无线Mesh网路由协议[J]. 东南大学学报： 自然科学版， 2009，39（4）： 700-704.

[7] 王吉喆. 无线Mesh网可靠路由技术研究[D]. 哈尔滨： 哈尔滨工程大学， 2010.

[8] 王晓翔. 无线Mesh网络路由技术研究[D]. 重庆： 重庆大学， 2012.

[9] 吴文甲，杨明，罗军舟. 无线Mesh网络中满足带宽需求的路由器部署方法[J]. 计算机学报， 2014，37（2）： 344-355.

[10] 朱翠涛，王俊. 无线Mesh网络中基于公平性的拥塞控制[J]. 中南民族大学学报： 自然科学版， 2009，28（1）： 85-88.★