基于无线Mesh网络的集中式自愈路由算法研究*

张 颉，柴继文 ，王 海，刘 悦，阎 波

(1.国网四川省电力公司电力科学研究院，四川 成都 610072；2.电子科技大学 通信与信息工程学院，四川 成都 611731)

0 引言

无线Mesh网络是一种多跳、具有自组织和自愈特点的宽带无线网络结构。与传统网络相比，它能够提供更大的便利性和更强的可靠性，能够更好地适应不断变化的网络状况以及提供优化的网络性能[1，2]。

当前无线Mesh网络路由算法寻路过程一般伴随洪泛现象造成网络性能下降。另外，由于无线链路的不稳定性使得路由的可靠性得不到保障。针对上述问题，已经有不少学者做了相关研究。文献[3]提出一种基于最优搜索模型限制下一跳节点搜索区域的方法，抑制了网络中的洪泛现象；文献[4]则通过限制Hello帧的周期性广播来达到降低路由开销的目的。但上述两种方法都需要获取地理位置信息；文献[5]中利用分级地址结构，设计了一种不需要地理位置信息的定向广播寻路方法，但该方法过度依赖于Root节点建立的树状路由，鲁棒性较差。在保证路由可靠性方面，多路径路由是一种行之有效的方法[6-9]，并且，节点不相交多路径相比于链路不相交多路径在负载均衡及路由可靠性方面更有优势[8]，但获取节点不相交多路径的过程通常较为复杂，并且多路径路由的质量得不到保障。

集中式路由[10]是人们在控制与转发分离的基础上提出的一种新的路由方法，目前的研究主要集中在IP网络，针对无线Mesh网络的研究较少。文献[11]中提出一种由网关节点为网内通信连接计算最优路的路由算法RDR(Root Driven Routing)，但到网关节点的路由仍然采用广播方式建立，并且由网关节点计算最优路的方式进一步加重了网关节点的负担，其性能并不理想。本文引入集中式路由的思想，设计了一种由Root节点为任意节点对之间计算最优路及备份路的路由算法CSRP，该算法在寻路和自愈过程不存在洪泛现象，另外，加入Root节点动态切换机制以提高网络的稳定性。

1 网络模型及研究思路

1.1 网络模型

假设网络中各节点随机分布在一个矩形区域内，并且具有如下性质：(1)网络内网关节点和Root节点唯一。(2)节点静止或具有弱移动性。(3)每个节点有惟一的标识。(4)所有节点平等，具有相同的计算、通信能力。

节点运动均遵循运动模型(Random Way Point，RWP)[12]，该模型可以描述为：节点在运动空间A内随机选取目的点D，随机选取v作为此次运动的速度，其速率在(vmin，vmax)范围内选取，匀速从起始点S沿直线运动到D，并以时间PauseTime保持静止，这样完成一次运动过程，如此重复。

1.2 研究思路

现有无线Mesh网络路由算法一般采用分布式的路由方式，这种分布式的路由方式保证了网络的可靠性，然而却导致了寻路洪泛等问题。尤其在网络负荷较重的场景下，进一步加重了网络的负担，严重影响网络的性能。

集中式路由是一种由路由控制平台统一计算路由信息的路由方法，各节点负责收集拓扑信息并且向路由控制平台通告，路由控制平台根据当前网络拓扑使用Dijkstra算法为节点间计算路由，节点根据计算的路由消息转发报文。在集中式路由方法中各节点不再具备寻路能力，因此需要预先构建一种具备保护功能的路由机制，使得节点的路径失效后都有立即可用的备份路径。

多路径路由通过路径信息的冗余性来保证主路由失效后分组传输的有效性。多路径通常分为节点不相交多路径和链路不相交多路径，如图1所示，但节点不相交多路径策略能够保证备份路由和主路由具有最大不相关性，更能保证路由的可靠性。

因此，在CSRP路由算法中由Root节点(路由控制平台)汇聚全网拓扑，为源目节点间计算路由，并结合节点不相交多路径策略提升网络的性能。

图1 多路径传输模型

2 CSRP路由算法

CSRP路由算法分为链路状态信息上传、路径选择及分组转发、路由自愈3个阶段，下面分别加以介绍。

2.1 链路状态消息上传

各节点在建立起到Root节点的路由后会首先将与各邻居节点之间的链路状态信息(包含邻居地址列表及其对应的链路质量度量值)发送给Root节点，Root节点以此掌握全网拓扑信息。

另外，各节点每隔QueryInterval查询一次邻接链路的链路状态，在式(1)和式(2)两个条件任意一个满足时向Root节点上传链路状态信息。

即节点的邻居节点发生变化。例如，有新的节点与当前节点建立邻居关系或者某个邻居节点拆除了与当前节点的邻居关系。

即节点与某个邻居节点I间的链路累计变化值大于阈值。

另外，各节点如果连续次查询链路状态未满足式(1)和式(2)上传条件，仍上传链路状态消息以探测根路由的有效性。

Root节点收到链路状态信息后，会更新全网拓扑信息。另外，各节点上传的链路状态信息通过ACK确认机制来确保上传成功，如果一次传输未成功，则在QueryInterval时间后再次上传。

2.2 路径选择及分组转发流程

当要发送分组时，节点首先查询路由表项中是否有到达目的节点的路由信息。如果有，按照当前路由信息直接发送至目的节点；如果没有，查询是否有到达Root节点的路由信息。

如果不存在到Root节点的路由，则需要首先请求到Root节点的路由，在此过程中使用序列号机制保证任何时候节点间都无环路。每个节点都保持着自己的一个序列号，这个序列号通过PREQ被发送到其他节点，其他节点只处理序列号更大的PREQ。请求到Root节点路由的具体步骤如下：

步骤(1)：向所有邻居节点发送路由查询帧。

步骤(2)：邻居节点收到路由查询帧后查看自身根路由是否有效，如果有效，回复有效确认帧，否则回复无效确认帧。

步骤(3)：如果节点接收到有效确认帧，则从回复有效确认帧的邻居节点中随机选取一个节点向其发送路由请求帧PREQ。

步骤(4)：如果没有收到有效确认帧，向其所有邻居节点发送路径请求帧PREQ。

步骤(5)：节点收到 PREQ后，首先检查 PREQ是否包含了一个更大的序列号，如果不是，丢弃该帧。如果是，再检查根路由有效，如果有效，上传 PREQ至Root节点，否则，重复步骤(1)～(4)。

步骤(6)：Root节点收到 PREQ。

Root节点收到序列号更大的PREQ后，计算源节点到Root节点的最优路及节点不相交的备份路，分别将最优路和备份路封装成PNTF帧，并沿各自路径发送到源节点，中间节点及源节点建立路由。

如果源节点存在根路由信息，将分组Mesh帧头中PathReq字段置1，表示请求源节点到目的节点的路由。如果传输采用根路由的备份路由，需要将Mesh帧头中IsSparePath字段也置1，表示需要重新请求源节点到Root节点的路由，然后将分组发送到Root节点。

Root节点接收到分组后的处理流程如下：

2.3 路由自愈流程

在CSRP算法中，各节点到Root节点的路由采用节点不相交的备份路进行备份，而到其他节点的路由采用根路由进行备份。下面以图例的方式详细说明利用备份链路进行自愈的流程。

图2 根路由自愈机制

根路由失效后的自愈过程如图2所示。以节点I为例，到根节点的主路由为 I-F-D-A-R，备份路由为IG-B-R。某一时刻，F探测到F-D链路发生失效后，会立刻通过自身的根路由F-G-B-R发送链路失效报文LinkPerr给Root节点，并向源节点I返回PERR错误报文，Root节点收到LinkPerr失效报文后，从全网拓扑中删除失效链路，随后F将缓存在本地的分组通过F-GB-R发送至R，I在收到PERR错误报文后，会删除本地路由表中的最优路由，将需要发送的分组切换至备份路I-G-B-R继续传输，并在Mesh帧头中标记为使用备份路发送。当分组到达Root节点时，Root节点查询到数据是由备份路由传输到达，会计算Root节点R到I的当前全局最优路由和备份路由，并将计算结果通过PNTF报文发送到I，I在收到PNTF报文后，会更新本地的最优路由和备份路由，后续分组通过当前的最优路由IG-B-R为传输。

对于到网内其他节点路由的自愈流程如图3所示，源节点为 F，目的节点为 H，最优路由为 F-G-H。G探测到链路G-H失效后，会立即返回PERR给源节点F，并利用本地的根路由(主路由或备份路由)将链路失效报文 LinkPerr和数据帧发送至 Root节点，Root节点收到LinkPerr报文后，从全网拓扑中删除失效链路，并将接收到数据帧后转发到目的节点H。源节点收到PERR错误报文后，删除失效路由表项，将后续数据利用根路由(主路由或备份路由)发送，并在Mesh帧头中设置路由请求标记，Root节点接收到数据帧后重新计算F和H间的当前最优路由，并将其通过路径消息报文PIFM发送至源节点F。F收到解析PIFM后得到最优路径，并将最优路径封装成PNTF帧，向目的节点H发送PNTF路由通告消息，中间节点和目的节点建立路由，后续数据将通过新建立最优路由传输。

图3 网内通信链路自愈机制

3 仿真及结果分析

为了验证CSRP路由算法的有效性，仿真实验中将时延、包递交率和路由开销(定义路由开销为路由协议分组字节总和占网络传输数据字节总和的比例)作为评价指标，对不同网络负荷、链路失效场景下CSRP、HWMP和RDR的网络性能仿真结果进行比较和分析。仿真软件为NS-3[13]，仿真参数如表1所示，节点随机均匀分布在网络覆盖范围内，网关节点位于网络覆盖区域的左上角，Root节点初始时刻位于网络的中心。仿真结果均为统计30次取平均的结果。

表1 仿真参数

3.1 不同网络负荷下的性能仿真

图4为不同负荷场景下CSRP与HWMP[14]、RDR[11]的性能仿真。

图4 不同负载场景下的性能仿真

3.2 自愈性能仿真

在本小节对比了路由失效场景下CSRP与HWMP、RDR的性能。通信连接数为20，节点移动速率为0～5 m/s之间的随机值，通过设置不同的PauseTime值来模拟网络拓扑变化的剧烈程度。图5中的仿真结果表明：在时延和包递交率方面，节点的移动性越强(PauseTime越小)，CSRP算法相比HWMP、RDR性能提升越明显。这是因为CSRP采用多路径备份策略，当路由失效后可以切换到备用路由进行分组传输，确保时效路由的快速恢复及分组的最小损失。在路由开销方面，如图 5(c)，对于 HWMP，其路由开销主要来源于Root节点的周期性广播和节点的寻路广播，链路越不稳定，重新广播寻路越频繁，路由开销越大。而对于RDR，随着链路逐渐稳定，链路状态消息上传越少，路由开销越小。对于CSRP，其路由开销主要来源于链路状态消息的上传，其路由开销最小，比HWMP和RDR路由开销至少降低67%。

图5 自愈性能仿真

4 结束语

该文将集中式路由方法用于无线Mesh网络，提出了一种集中式自愈路由算法CSRP，在该算法中各节点汇聚链路状态消息至Root节点，由Root节点集中计算最佳路由。相比于传统路由算法的洪泛寻路机制，该算法在很大程度上降低了路由开销。另外，该算法采用多路径备份策略及Root节点切换机制保证路由的可靠性。通过仿真表明，CSRP路由算法较HWMP、RDR路由算法在不同仿真场景下都有明显改善，路由开销至少降低67%，时延平均降低45%，包递交率平均提升8%。在未来的工作中，考虑在网络中加入多个路由控制平台(Root节点)，各路由控制平台之间相互备份，以进一步增加网络的鲁棒性。

[1]BENYAMINA D，HAFID A，GENDREAU M.Wireless mesh networks design-A survey[J].Communications Surveys&Tutorials，2011，14(2)：299-310.

[2]AKYILDIZ I，WANG X D.A survey on wireless mesh networks[J].Communications Magazine，IEEE，2005，43(9)：S23-S30.

[3]秦丹阳，马琳，沙学军，等.移动Ad Hoc网络中路由自愈的实现[J].哈尔滨工业大学学报，2010，42(1)：46-50.

[4]DONG P，QIAN H Y，WEI X F，et al.Beacon-less geographic multipath routing protocol for ad hoc networks[J].Mobile Networks and Applications，2013，18(4)：500-512.

[5]KIM S，CHONG P，KIM D.A location-free semi-directional-flooding technique for on-demand routing in low-rate wireless mesh networks[J].IEEE Transactions on Parallel and Distributed Systems，2014，PP(99)：1-11.

[6]TARIQUE M，TEPE K E，ADIBI S，et al.Survey of multipath routing protocols for mobile ad hoc networks[J].Journal of Network and Computer Applications，2009，32(6)：1125-1143.

[7]郝晓辰，贾楠，刘彬.基于拥塞预知的WSN多径寻优路由协议[J].电子与信息学报，2011，33(5)：1261-1265.

[8]LAL C，LAXMI V，GAUR M S.A node-disjoint multipath routing method based on AODV protocol for MANETs[C].26th IEEE International Conference on Advanced Information Networking and Applications，Fukuoka，2012：399-405.

[9]OBAIDAT M，ALI M，SHAHWAN I，et al.QoS-aware multipath communications over MANETs[J].Journal of Networks，2013，8(1)：26-36.

[10]谭晶，罗军舟，李伟.一种适合低连接度拓扑的集中式保护路由机制[J].软件学报，2013，24(3)：575-592.

[11]LIM A O，WANG X D，KADO Y，et al.A hybrid centralized routing protocol for 802.11s WMNs[J].Mobile Networks and Applications，2008，13(1-2)：117-131.

[12]MUHAMMAD A，ROBERT S.Simulation study of common mobility models for opportunistic networks[C].Simulation Symposium，ANSS 2008，41st Annual，Ottawa，2008：43-50.

[13]IKEDA M，ODA T，KULLA E，et al.Performance evaluation of WMN considering number of connections using ns-3 simulator[C].The Third International Workshop on Methods，Analysis and Protocols for Wireless Communication，Victoria，2012：498-502.

[14]BARI S M S，ANWAR F，MASUD M H.Performance study of hybrid wireless mesh protocol(HWMP)for IEEE 802.11s WLAN mesh networks[C].IEEE International Conference on Computer and Communication Engineering，Kuala Lumpur，2012：712-716.