彭琦 唐碧华 刘凯明 刘元安

北京邮电大学 电子工程学院 无线电与电磁兼容实验室 100876

一种适用于无线Mesh
骨干网络的负载均衡路由算法

彭琦 唐碧华 刘凯明 刘元安

北京邮电大学 电子工程学院 无线电与电磁兼容实验室 100876

无线Mesh网络（WMNs）以其灵活的配置和低成本的特性极大地扩展了传统无线网络的覆盖范围。路由算法作为无线Mesh网络研究的一个核心，其设计的优劣会给网络的性能造成重要的影响。文章中提出了一种适用于无线Mesh骨干网络的负载均衡路由算法，使网络性能在吞吐量和时延方面得到了一定程度的提升。

1.引言

无线Mesh网络（Wireless Mesh Networks，WMNs）作为一种高速率高容量多点对多点的分布式网络以及解决“最后一公里”问题的可行方案，正逐渐受到越来越多人的关注[1]。WMNs能够和其他网络系统有效地融合，从而快捷、高效地扩展无线网络的覆盖范围。其自组织、自配置和自愈的特性，以及对移动用户的有效管理和跟踪机制，使之成为部署社区宽带网络、企业内部网络和城域网络的理想选择[2]。

WMNs可以提供典型的因特网接入场景，通过部署一个或多个网关节点可以实现WMNs中的节点与外部网络的互联。其骨干网中的节点大都是静止的或者具有很小的移动性。Yang等在文献[3]中证明了先验式的逐跳路由协议最适合于此种类型的Mesh网络，也最能够满足无线Mesh网络的拓扑结构和业务模型。因此我们选用OLSR（optimized link state routing Protocol）[4]协议作为研究的基础。

在本文中，我们根据IEEE802.11s WLAN Mesh网络的特点，提出了一种基于OLSR路由协议的改进算法，该算法分别在OLSR协议的多点中继集合(MPR)选择阶段和路由维护阶段进行了改进，首先通过修改MPR选择策略，使得MPR集的选择结果可以动态地变化，避免了网络中“热区”的出现，从而可以使数据分组更加均匀地在网络中传输，实现网络负载均衡的效果；其次，在路由维护阶段，改进的算法将前一次的MPR计算结果作为备份存入拓扑表中去，这样当网络出现链路断裂或节点拥塞时，就能够快速地根据拓扑表中的信息计算出备份路由，即避免了计算的浪费，又提高网络的健壮性。WLAN的Mesh组网方式，它适用于诸如办公楼、家庭网络等场景。其典型结构可以分为三层。最低一层为“终端用户层”，由用户终端设备组成，包括手机、笔记本电脑、PDA等设备；“终端用户层”之上是“无线Mesh层”，由无线Mesh接入点MAP (Mesh Access Point)和Mesh入口节点MPP(Mesh Portal Point)构成，组成Mesh骨干网，终端用户可以通过该层接入核心网络，如因特网、PSTN等，终端用户之间也可以通过该层进行数据交互；WMN的第三层为“核心网络层”，主要为终端与各种网络互连等提供服务。一种基于IEEE802.11s的典型结构如下图所示：

2.研究背景

2.1 基于IEEE802.11s的WLAN Mesh

IEEE802.11s标准提供了一种

图1 基于802.11s的Mesh网络结构

其中的MPP（Mesh Portal Point）作为网关节点，网络中的节点通过MPP连接到其他网络；MP（Mesh Point）作为第二层路由器，它决定了数据包在Mesh骨干网中的转发；MAP（Mesh Access Point）则提供了传统用户节点的接口。

2.2 OLSR协议简介

OLSR—优化链路状态路由算法,是一种专门为无线分布式网络所设计的表驱动路由算法，它的设计充分的考虑了无线网络对于表驱动路由协议的需求，很好地解决了传统表驱动路由协议和按需驱动路由协议开销较大的问题。OLSR中的节点定期向网络中广播包含该节点周围局部拓扑信息的拓扑控制分组，通过这样的分布式操作过程，每个节点都能够根据其接收到的局部拓扑信息构造出全局子网拓扑，从而进行路由路径的计算。整个OLSR算法的核心可以划分MPR选择、拓扑表的计算和更新以及路由的计算和维护三个部分。

OLSR协议采用了多点中继技术（Multipoint Relaying Technique）[5]作为其构建的基础，只有被选为MPR的节点才向全网广播信息。MPR节点的选取必须满足条件：如果一个节点选择了其部分(也可以是全部)一跳邻居作为它的MPR节点，那么这个节点通过这些MPR节点必须能够到达它所有的两跳邻居，即MPR节点提供对所有两跳邻居的连通性。OLSR中MPR的核心思想就是在某一时刻尽量使用信道状态较好的节点来搭建路由。

3.基于OLSR协议的改进方案

3.1 EOLSR的路由建立过程

OLSR协议中MPR选择机制通常采用基于贪婪策略的启发式算法，这种方法在传统的Ad-Hoc网络中能够取得令人满意的效果，但是在无线Mesh骨干网络中，节点通常具有较小的移动性，网络拓扑也基本固定，这样在网络中用同样的算法进行多次MPR集合选择的结果基本上是固定的，据此形成的网络拓扑框架也没有变化。这样就造成了两方面的问题，一方面是网络资源的严重浪费，因为根据OLSR协议的规定，数据包只会通过MPR节点进行转发，这样就会导致无线Mesh网络中其他大量节点闲置；另一方面，当网络负载增加时，MPR节点的负担加重，很容易形成网络中的“热区”，造成网络瓶颈，从而影响整个网络的性能。针对上述问题，我们提出了一种改进型的路由算法EOLSR(Enhanced OLSR)，该算法修改了OLSR协议中的MPR选择策略，并引入了备份路由机制，在选择MPR集时，除了考虑到其对于两跳邻居的连接性外，还要考虑节点当选为MPR的概率，并在拓扑表中记录MPR的改变，当MPR选择发生变化时，先前的MPR路径就作为备份存入拓扑表中，并在网络发生拥塞时通过本地计算快速得到备份路由，从而缓解主路径的负担。

为了表征节点当选为MPR的优先级并实现网络的负载均衡，我们在节点的邻居表中分别加入三个参数，一个MPR概率参数α、一个MPR标识参数β和一个连通度参数γ。其中α参数是一个 形式的变量，分母M是一个累加计数，表示网络中一共进行MPR计算的次数，每进行一次MPR计算，M的值就加1。N表示该节点当选为MPR的次数，初始化为0，该节点每当选一次MPR，N的值加1，反之则不变；参数β是一个标志位，用来表示此节点在上一次计算中是否当选为MPR节点，如果是则置1，反之置0。连通度参数γ表示该邻居可以连接到的两跳邻居节点数目，即该邻居节点对于两跳邻居的连通性。修改后的邻居表如下所示：

图2 修改后的节点邻居表

通过邻居表中的参数，我们可以在选择MPR集合时，计算一个节点的MPR优先级参数D(y)，参数D(y)越大表示优先级越高。D(y)的计算如式（1）所示：

因为MPR集的选择是一个NP完全的问题，所以MPR集的选择并不需要追求最优化，但是为了达到更好的效果，MPR集合一定要足够小。用公式（1）进行计算时，如果两个节点在上一次计算中均未当选为MPR节点，即β为0，则只比较它们的连通度参数γ，待选节点的连通度越大，最终得到的MPR集合就会相应的越小。若β不为0，则在考虑连通度的同时，还需要考虑节点当选为MPR的概率，从而选择合适的节点。计算出的优先级参数D(y)通过HELLO信息传递给所有的邻居节点，这样邻居节点在进行MPR集合选择的时候就可以根据此参数来选择合适的MPR节点。

为了使结果更加准确，进一步提高网络的性能。我们在计算的同时考虑到节点的当前负载情况，如果节点当前负载大于某一预设值时，就不再选用该节点作为中继节点，即将HELLO信息中的Willingness字段设置为WILL_NEVER，表示该节点不会被选为MPR节点，这样做能有效地避开网络中的一些负载过高的节点，从而提高网络的性能。

这样，我们可以将MPR选择的流程形式化描述如下：

Algorithm: MPR_selection (x,N, N2)

Input: X: An arbitrary node

N1: Symmetric 1-hop neighbors of X N2: 2-hop neighbors of X with only symmetric neighbors in N1

Output: MPR: MPR set of node X

1 Begin

2 Start with an empty MPR set

3 Add to MPR the nodes of N1 that are the only ones able to reach a node in N2

4 Exclude the covered nodes by the last step from N2

5 Delete the nodes whose loadis larger than a given value

6 While N2 is not empty

{

7 select the node of N1 that has the highest D(y) which is calculated from formula (1)mentioned above. At the same time,increase the value of N and M by 1 and setβ as 1

8 Add to MPR the selected node

9 Exclude the covered nodes by the selected node from N2

}

10 End

3.2 EOLSR的路由维护过程

经过上面对MPR选择策略的修改，我们可以使MPR集合的选择在Mesh骨干网络中的节点间动态地变化，为了避免计算浪费，同时也为了提高网络的健壮性，在一次新的MPR选择过程结束后，如果一个原来在MPR集合中的节点在此次计算中没有当选，即，且此节点对于两跳邻居的连通度γ没有发生明显地变化，即（δ表示最大误差），则通过这个节点的路由可以作为备份路由，存入拓扑表中。并通过TC（Topology Control）拓扑控制信息广播出去，为了区分主路径和备份路径，我们在TC信息中添加了一个Flag字段，当一个中间节点收到TC信息后，就将TC信息中的新当选MPR作为主路径，原MPR作为备份存入到拓扑表中。

当网络中的主路径断裂或节点发生拥塞的时候，以及相邻节点的丢失或重建和接口信息发生变化导致需要重新计算路由的时候，我们就可以使用存储在拓扑表中的备份信息通过本地计算快速地计算出备份路由，从而保证网络发送信息的通畅。计算备份路由的过程按照下面的流程进行：

首先，从一跳邻居开始计算，将拓扑表里作为备份的MPR节点存入路由表中去，目的地址和下一跳地址都是这些MPR节点；其次，在路由表中记录距离源节点为h=h+1跳的目标节点的路由项。以下的算法从距离为1跳开始执行，每次跳数增加1，如果在路由计算中没有发现新的路由，那么该算法就停止：对于拓扑表中的一行如果MPR Selector节点的地址不等于路由表中的任何一个目的节点地址，并且，TC信息发送节点地址等于路由表中的目的节点地址而且跳数为h，那么就在路由表中生成一条新的路由，目的节点地址=MPR Selector节点地址，下一跳节点地址=所对应h跳路由的下一跳节点地址，最后，计算完成，将计算出的备份路由存入路由表中，备份路由的计算过程如图3所示。

图3 备份路由的计算过程

经过上述改进，在节点相对固定的WMNs骨干网络中，MPR集的选择结果可以扩展到更大的范围，从而使分组业务可以在全网范围内更加均衡地分布，网络资源也可以得到更加充分地利用，避免了“热区”的出现，在一定程度上实现了网络负载均衡；备份路由机制的引入，既避免了计算的浪费，又可以在网络拥塞时缓解网络负担，从而提高了网络的健壮性。

4.仿真分析

为了定量的分析改进协议的性能，我们使用OPNET[6]对EOLSR进行了建模和仿真，网络拓扑采用了分层结构，上层节点基本固定，下层节点具有一定的移动性；在一个大小为1000*1000的网络场景中，分布50个节点，每个节点随机的选择自己的运动方向，运动速度为5m/s，随着仿真时间的推移，分别使用10，20，30，40，50个通信源节点来发送数据，仿真使用了802.11 MAC协议，并采用了恒定比特率（CBR）的传输，每个数据包的大小为512字节。仿真中我们将本文中提出的改进型协议EOLSR与原OLSR协议和按需源路由协议DSR分别在端到端平均时延和网络吞吐量方面进行了对比。仿真结果如下图所示：

图4 三种协议的端到端平均时延对比

图5 三种协议的网络吞吐量对比

图4 和图5分别显示了三种不同协议的端到端时延和网络吞吐量随着网络中业务量增大的变化趋势。从图中我们可以看出，改进型的协议EOLSR在时延和吞吐量方面均取得了一定程度的改善，因为EOLSR协议考虑到了全网范围的负载均衡，因而能够使负载在骨干网络中更加均匀地分布，降低了碰撞和丢包的概率；而网络一旦发生拥塞或链路断裂，备份机制的引入又使得该协议又能够快速地计算出备份路由传输数据，保证了数据传输的连续性，这样就减小了数据传输端到端传输的时延，同时也提高了网络吞吐量。

5.结论

本文在分析无线Mesh网络特征的基础上，提出了一种基于OLSR协议的改进算法，该算法克服了原协议应用在无线Mesh网络中易形成“热区”的问题，使网络负载可以更加均衡地分布，充分地利用网络资源；并在路由维护阶段引入了备份机制，通过备份信息快速计算备份路由，提高网络健壮性。仿真结果也表明了改进的协议能够有效地提高网络的吞吐量并减低端到端平均时延。

[1] F.Akyildiz, Xudong Wang, Weilin Wang. Wireless mesh networks: a survey[J] Computer Networks 2005 5(47):445-487

[2]傲丹，方旭明.无线网格网关键技术及其应用[J].电讯技术.2005（2）：16-22

[3] Yang Yaling, Wang Jun. Design guidelines for routing metrics in multihop wireless networks[C] Proceedings of the 27th IEEE Communications Phoenix. USA,2008: 2288 - 2296

[4]T.Clausen, K.Jacquet, A.Laouiti,Optimized Link State Routing Protocol,IETF Internet RFC 3626

[5]Qayyum A, Viennot L, Laouiti A Multipoint Relaying: An efficient technique for flooding in mobile wireless networks[C]Proceedings of the 35th Annual Hawaii International Conference.Hawaii: IEEE,2001

[6]陈敏.OPNET网络仿真[M].清华大学出版社.2004

10.3969/j.issn.1001-8972.2011.02.040

国家863计划项目(2008AA01Z211)和国家自然科学基金(60802033,60873190)资助课题

彭琦(1987- ) 男，硕士，北京邮电大

学，主要研究方向是无线Mesh网络的路由协议。

无线Mesh网络; 路由协议; 负载均衡