0 引言

在无线Mesh网络中，信道分配和路由协议是较为关键的问题，且二者联系紧密。如何协调其关系以更好地利用网络资源、提升网络性能是当前研究热点之一。对于信道分配的分类，按照网络中Mesh节点（Mesh Point，MP）射频接口数量的不同，可分为单射频信道分配和多射频信道分配。由于后者能带来更大的网络吞吐量，因此应用更为广泛^[1]。此外，若根据信道更新频繁程度，又可分为静态信道分配、动态信道分配和混合信道分配^[2]。而对于路由选择，按照路由建立和业务请求之间的关系，可以分为先验式路由协议^[3]、反应式路由协议^[4]和混合式路由协议^[5]。

传统的无线Mesh网络中，信道分配和路由选择是分开进行的，一般先进行信道分配，再执行路由选择。当网络拓扑以及业务流量相对稳定时，该方式可以充分地利用网络资源。然而一旦网络拓扑或链路负载发生变动，以上方法无法根据实时信息调整资源配置，致使资源利用率大幅降低，甚至出现节点孤立，影响正常的数据传输。

针对上述问题，近年来出现了诸多关于融合信道分配和路由选择的研究，大致可分为集中式^[6]和分布式^[7]两类，其中分布式路由算法不需要中央处理节点，且可避免因单个节点失效导致整个网络崩溃的危险，因此得到更为广泛的研究和应用。本文主要针对多射频多信道(Multi-Radio Multi-Channel，MRMC)无线Mesh网络中网络负载及节点位置实时变化等实际场景，在混合无线网状路由协议（Hybrid Wireless Mesh Routing Protocol，HWMP）反应式路由基础上，设计了一种新的混合信道分配的分布式路由算法（Routing based on Hybrid Channel Assignment，RHCA）。

1 信道分配方案

由于本文提出的RHCA方案基于动态网络设计，因此信道分配策略应采用动态分配或混合分配。考虑到混合分配方案具有更好的网络连通性，故选择后者。

1.1 系统模型

本文无线Mesh网络模型如图1所示，采用网格型网络拓扑，共设置32个节点，相邻节点间距170 m。且本文的信道分配过程只考虑如何减小链路干扰，达到以数据流为单位的链路干扰最小化信道分配。其余诸如网络负载等因素的影响则在路由选择时考虑。干扰模型方面采用文献[8]中的协议干扰模型，如图2所示，当链路e_i、e_j节点间跳数不少于两跳时，才认为二者无相互干扰。虽然该模型是一个NP问题，但其信道分配模型融合于路由算法中，具体分配方式将在后文中详述。

1.2 接口分配策略和通信协调机制

在接口分配上，所有节点均固定使用一个无线射频接口搭配标号为1的信道作为固定接口，用于传递网络管理消息，当网络负载较重时亦可传送数据。其余接口全部用于数据传输，称为动态接口(Dynamic Radio Interface，DRI)，其分配信道在传输过程中可实时切换。

另外，本文的通信协调机制主要通过分析网络中的相邻节点DRI信道分配、路径请求（Path Request，PREQ）消息帧前两跳DRI信息以及各个节点Metric信息等，得到与下一跳链路干扰最小的信道。该机制在路由过程中实施。当源节点发送PREQ，寻得最优路径之后，目的节点在回复路径响应（Path Reply，PREP）消息过程中逐一节点绑定通信接口，并分配信道。

1.3 接口释放机制

本文对源节点的接口释放机制进行了如下设计。在开始发起数据业务后，数据流监听模块随即启动，并设置监听标志位tags为1，表示监听有效。当收到路径错误消息报文（Path Error，PERR）时，需要重新寻路，于是释放现有路径上节点所用接口。若没有收到PERR则将每次监听时刻同当前源节点最新发送数据时刻做差值，如果该差值小于设定阈值，表示源节点仍在发送数据，否则认为发送完毕，tags置零，监听停止，并发送CHCLR，同时等待CLRACK。若源节点收到CLRACK，则执行接口释放操作，否则重发CHCLR报文；若超过规定重发次数后仍未收到CLRACK，则直接执行接口释放操作。

2 RHCA路由算法设计

本文提出的RHCA路由算法主要针对网络拓扑不固定和业务负载多变的场景。算法采用分布式信道分配，且通信协调在路由响应阶段完成。由于该方案基于IEEE 802.11s中混合无线网状路由协议HWMP的反应式路由算法改进而来，所以在管理消息帧格式、路由判据、PREP和PREQ等管理信息的广播和接口释放机制方面，基本沿用自HWMP算法。

2.1 路由建立过程

在提出的RHCA路由方案中，当发起一项业务时，源节点先判断是否存在到达目的节点的路由信息，若已存在则只需要按照路由表向目的节点单播PREQ；若没有则发起到目的节点的PREQ广播请求，各节点收到请求后，判断自身是否为目的节点，如果不是则按中间节点处理方式处理PREQ信息，直到目的节点收到请求，进入响应阶段。此后目的节点首先判断收到的消息是否为新的PREQ，若不是则直接丢弃；如果是则按PREQ所寻路径开始单播回复PREP。回复过程中逐跳进行接口绑定和信道分配。当PREP返回至源节点后，链路的双向路径建立完毕，开始数据传输。

2.2 路由维护过程

RHCA算法的路由维护在HWMP基础上，加入了对故障因素的考虑，增加了如下相关操作。

当发现故障时，处于故障上游的节点向源节点单播PERR，源节点接收到PERR后，执行路径上各节点接口释放操作，当上游各节点收到CLRACK后开始广播到目的节点的PREQ重新寻路；而故障下游节点在未收到CHCLR的情况下，若等待超时，则判定为上游节点故障，遂开始执行链路后续节点的接口释放操作。此方案既保证了路由得到修复，又完成了故障节点下游的接口释放，避免了故障链路占用信道资源。

3 性能仿真分析

为了模拟网络多变性，仿真分别在不同的网络负载和网络拓扑下进行，以便考察提出的RHCA方案的平均吞吐量和时延。同时为了便于比较，加入了HWMP路由分别搭配集中式信道分配(Centralized Hyacinth Channel Assignment，C-HYA)和MRMC HWMP(MMHWMP)路由算法结合节点优先级静态信道分配(Nodes Priority Fixed Channel Allocation，NPFCA)两种方案进行对比。仿真系统参数设置如表1所示。所有结果均为采用20个随机种子进行仿真所得平均值，基本符合网络数据统计特性。

3.1 不同网络负载下性能分析

本次仿真采用网络拓扑如图1所示，并设12号节点为根节点。

仿真随机选取5对节点建立固定码率(Constant Bit Rate，CBR)数据传输业务，CBR流速率为600 kb/s到2 Mb/s不等，每组节点在仿真时间内随机选择时间发起业务，并持续50 s，如果从发起业务到仿真结束不足50 s，则以仿真结束时间为准。全网可用正交信道数为6，仿真结果如图3所示。

从图3(a)可以看出，随着CBR流速率的增加，三种算法总吞吐量都呈现递增趋势，而提出的RHCA路由算法所得网络总吞吐量明显高于前两者，尤其在CBR速率为1.6 Mb/s时，其吞吐量较HWMP和MMHWMP分别高约17.7%和13.5%。

由图3(b)可知，随着CBR流速率的增加，三种算法的端到端平均时延也逐步增加，MMHWMP与HWMP方案在CBR流速率为<1.6 Mb/s时平均时延差距不大，当速率大于1.6 Mb/s时差距逐渐拉大； RHCA方案的网络时延显著优于前两者，尤其在CBR流速率为1.8 Mb/s时，分别较MMHWMP和HWMP有约0.06 s和0.12 s的优势。

3.2 动态拓扑及负载场景下性能分析

初始网络如图1所示。设置节点移动模型为“Random Way point Mobility Model”^[9]，各节点速率是在0 m/s～2 m/s中均匀分布的随机变量，移动范围限制在图中二维空间内。网络中运行两组CBR数据任务，第一组随机选取5对节点建立CBR数据业务，流速率为500 kb/s，仿真运行5 s后开始发送数据直至结束；仿真运行100 s后，再从余下的节点中随机选取5对节点建立第二组CBR数据业务，流速率仍为500 kb/s，同样持续至仿真结束。仿真时间总共200 s。全网可用正交信道数为6，当仿真开始20 s后，开启移动模型。同时还增加了较为灵活的HWMP路由+公共信道分配（Common channel assignment，CCA）组合，以供参考。仿真结果如图4所示。

从图中可以看出，在仿真前20 s范围内，四种方案都处于稳态，此时本文提出的RHCA方案性能最优；当仿真开始20 s后，移动模型开启，网络拓扑开始变化，部分链路通信中断，使得在40 s～60 s期间，所有方案的吞吐量均有较大幅度下降；而在60 s～100 s之间，随着网络拓扑持续变化，部分节点重新建立连接，使得四种方案吞吐量有不同程度回升，其中以RHCA回升最为明显，最高时甚至超过HWMP+CCA方案近一倍；仿真100 s后，由于引入了5条新数据流，网络整体吞吐量有所上升，同样以RHCA方案升幅最大，其性能领先HWMP-R+CCA约70%。

4 结论

本文主要针对MRMC无线Mesh网络中，网络负载可变以及网络节点可移动的动态场景，在HWMP反应式路由算法基础上，提出了一种融合信道分配和路由选择的RHCA算法。仿真结果表明，此算法无论在网络吞吐量还是端到端平均时延方面均有显著优势。同时仿真结果还验证了在节点可移动的无线Mesh网络中，RHCA较其他三种方案能获得更高的吞吐量，同时具有更好的稳健性。

参考文献

[1] PENG Y，YU Y，GUO L，et al.An efficient joint channel assignment and QoS routing protocol for IEEE 802.11 multi-radio multi-channel wireless Mesh networks[J].Journal of Network and Computer Applications，2013，36(2)：843-857.

[2] Zhang Yang，Luo Jijun，Hu Honglin.Wireless Mesh networking：architectures，protocols and standards[M].New York：Auerbach Publications，2006.

[3] PERKINS C E，WATSON T J.Highly dynamic destination sequenced distance vector routing(DSDV) for mobile computers[C].ACM SIGCOMM’94 Conference on Communications Architectures，1994：234-244.

[4] PERKINS C E，ROYER E M.Ad hoc on demand distance vector(AODV) routing[C].IEEE Workshop on Mobile Computing Systems and Applications，WMCSA(2)，1999：90-100.

[5] RADHAKRISHNAN S，RAO N S，RACHERLA G，et al.DST-A routing protocol for ad hoc networks using distributed spanning trees[C].IEEE Wireless Communications and Networking Conference，WCNC，1999：1543-1547.

[6] AVALLONE S，AKYILDIZ I F，VENTRE G.A channel and rate assignment algorithm and a layer-2.5 forwarding paradigm for multi-radio wireless Mesh networks[J].IEEE/ACM Transactions on Networking，2009，17(1)：267-280.

[7] RANIWALA A，CHIUEH T.Architecture and algorithms for an IEEE 802.11-based multi-channel wireless Mesh network[C].Annual Joint Conference of the IEEE Computer and Communications Societies，INFOCOM(24)，2005：2223-2234.

[8] XU K X，GERLA M，BAE S.How effective is the IEEE 802.11 RTS/CTS handshake in ad hoc networks[C].Global Telecommunications Conference，2002(1)：72-76.

[9] VINOTHINI M，GANDHIMATHI K.Comparison of L-PEDAP routing protocol with random way point mobility model in mobile sensor networks[C].IEEE-International Conference On Advances In Engineering，Science And Management，ICAESM(1)，2012：735-740.