一种降低干扰的无线Mesh网络信道分配与路由联合优化系统与方法

摘要

本发明公开了一种降低干扰的无线Mesh网络信道分配与路由联合优化系统与方法，它包括信道分配步骤和路由寻路步骤：（1）计算最短跳数并分层；（2）计算邻居数与节点负载；（3）根据干扰权重按照启发式信道分配方法进行信道分配；（4）中间节点接收路径请求消息，计算上一跳MCDI并进行累加，计算MCDI的时候考虑流内和流间干扰；（5）将得到的值与路由表中存储的值进行比较，对MCDI值最小的路径请求消息进行回复并建立路径。本发明提出一种基于链路负载权重的静态信道分配方法，达到最小化网络中链路之间的干扰的目的，再在路由选择中充分考虑流内干扰和流间干扰因素，得到最优路径，提高网络中的吞吐量，减小延时。

说明书

技术领域

本发明涉及多射频多信道无线Mesh网络信道分配及路由优化，尤其涉及一种降低干扰的无线Mesh网络信道分配与路由联合优化系统与方法。

背景技术

无线Mesh网络以其特殊的网状结构、高覆盖率、高可靠性等特点受到了越来越高的关注，越来越广泛地应用于无线通信，被认为是未来无线通信发展的关键技术。无线Mesh回传网络架构图如图1所示。但是随着无线Mesh网络中的应用对数据传输性能的要求日益提高，使得对无线Mesh网络的容量、延迟等要求也越来越高。

面对这一问题，业界提出各种解决方法：多射频多信道技术、网络编码技术和动态成簇技术等，都能一定程度上的提高无线Mesh网络性能。而多射频多信道技术对性能提升最为明显，如何进行有效快速正确的信道分配仍是无线Mesh网络的一个难点问题。因此对信道分配方法的研究具有较高的理论研究价值和实际应用前景。信道分配方法分为静态信道分配方法、动态信道分配方法和混合信道分配方法。静态信道分配方法是指为射频口分配的信道固定不变或在一个相当长的时期内保持不变；动态信道分配方法是指为任意射频端口分配任意信道，并且射频端口的信道并不是固定的，而是可以进行动态转换；混合信道分配方法结合了静态信道分配和动态分配的特点，节点的一部分射频接口分配的信道固定不变，另一部分射频端口分配的信道则可以根据传输需要进行动态转换。

申请号为201210123432.2的专利公开了一种多信道多射频无线Mesh网络中分布式信道分配方法，该专利定义了一种判据WA_ETT，在给链路分配信道时候，计算这条链路在每一个信道上的WA_ETT大小，然后选择WA_ETT最小的信道分配给链路，在路由过程中采用路由度量判据EWCETT作为路由判据；这种方案在寻路过程中分配信道，在网络中存在多条数据流的时候，甚至数据流之间的公共结点比较多的时候，该方案对公共结点的信道分配数越多，那么对节点的接口数要求越高，如果每个节点装备过多的接口，成本太高，而且方案中计算EWCETT来决定选择最优路径的方法只适合源路由，不适合逐条路由，有局限性。而本发明首先根据节点拓扑，采用节点优先级和密集度来为链路计算负载权重，然后根据负载权重分配信道，这种静态分配信道的方式充分的利用了网络资源，在网络中实际传输数据流的时候也不会对网络拓扑有影响，对接口数目的要求不高，节约成本，而且在信道分配完成之后，本发明在计算度量的时候考虑路径上流内干扰和流间干扰的问题，发明中计算最优路径使用的MCDI(Metric of Channel Diversity Index，信道多样性指数度量)度量适合各种路由协议，可扩展性比较好。

申请号为201110021937.3的专利公开了一种基于拓扑优化和降低干扰的无线Mesh网络路由信道联合分配方法，该方案首先通过基于流量感知和流量公平分配的拓扑结构贪婪算法将拓扑结构转化为树形结构，形成优化后的拓扑结构，然后对优化后的Mesh拓扑结构利用AODV进行路由选择，然后对链路进行二步启发式信道分配算法，该方案中对于网络拓扑需要进行优化，将拓扑首先转换成树状结构，这种结构变化会导致网络拓扑的逻辑连接关系和实际连接关系不符，很可能导致相邻节点之间反而需要经过多跳才能到达，增加了传输延时，同时这种树状结构网络中所有的流量，无论是出网入网还是网内的数据都需要通过根节点转发，会导致根节点周围负载严重。而本发明中是通过网关节点的位置来为不同的节点设置不同的优先级并考虑到节点周围的邻居数来计算链路负载，从而来实现信道分配，考虑到了网络中的流量样式问题，同时本发明不改变网络的拓扑连接情况，根据拓扑来为链路分配信道，网络中的数据不会全部从根节点转发，减小了根节点的负载，然后在路由过程中加入流内干扰和流间干扰，信道分配和路由选择联合优化实现性能的提升。

申请号为201310112381.8的专利公开了一种用于多信道无线Mesh网络的链路分配方法，该方案首先通过节点到网关节点的距离里为节点分层，然后为每一层的节点关联的链路计算信道的干扰链路集合，然后根据干扰链路集合计算链路的干扰度和链路的分配指数和节点的分配指数，在满足网卡约束的条件下将一条链路分配到一个或者多个信道上去，但该方案仅仅以网络分层为依据来为每一层关联的链路分配信道，在考虑到接口有限的条件下为链路分配可用信道，没有考虑到网络的流量样式问题，也没有考虑到路由过程中多信道带来的流内干扰和流间干扰问题。而本发明是针对流量样式问题和路由问题是通过对链路负载的计算为不同的链路赋予不同的负载权重，然后将每条链路分配一个固定的干扰最小的信道，从而使得网络中干扰最小化，然后在路由过程中加入了流内干扰和流间干扰考虑，通过信道分配和路由选择的联合优化来提升网络的整体性能。

申请号为US20050057577的专利公开了一种集中式信道分配和路由算法的具体步骤，该方案中首先预估计网络中各链路上的期望负载，并通过估计的负载来给网络中每一条链路分配信道，然后在实际路由的过程中观察是否所有的链路容量能够满足期望负载需求，如果不满足则根据实际的链路容量反馈来重新信道分配，直到信道分配的结果能够满足期望链路负载要求，这种方法在无线Mesh网络中流量变化快速的时候信道重新分配会比较频繁，而这种信道分配过程中带来的波纹效应也会导致信道分配的延时变大，网络收敛较慢，会影响网络的稳定性。而本发明是基于无线Mesh网络流量样式特点进行的静态信道分配，网络的拓扑不变的情况下则信道分配方案不变，减小了网络的变动，同时在路由上的优化不是作为信道分配的反馈，而是为了与信道分配联合路由达到整体干扰最小化的目的。

发明内容

本发明的目的在于克服现有技术的不足，提供一种降低干扰的无线Mesh网络信道分配与路由联合优化系统与方法，达到最小化网络中链路之间的干扰的目的，再在路由选择中充分考虑流内干扰和流间干扰因素，得到最优路径，提高网络中的吞吐量，减小延时。

本发明的目的是通过以下技术方案来实现的：一种降低干扰的无线Mesh网络信道分配与路由联合优化系统，它包括链路信息计算模块、信道分配模块和路由寻路模块，所述的链路信息计算模块用于对输入的初始信息进行计算，链路信息计算模块的输出与信道分配模块连接，信道分配模块的输出与路由寻路模块连接，路由寻路模块输出信道分配结果和源目最优路径。

所述的初始信息包括网络拓扑、根节点、节点信息和可用信道集合。

一种降低干扰的无线Mesh网络信道分配与路由联合优化方法，它包括链路信息计算步骤、信道分配步骤和路由寻路步骤，所述的链路信息计算步骤包括以下子步骤：

S11：输入每个节点的可用网卡数K(u)、网关节点、节点信息、可用信道数集合C(u)和物理拓扑G(V，E)；

S12：采用Dijkstra算法来计算每一个节点到网关节点的最短跳数，并以最短跳数为每一个节点分级，网关节点的级数最高为第一级，网关节点的一跳邻居为第二级，依次往下分，直到所有的节点都被分了层级PL_i,标记为PL_i＝1、2……n，其中PL_i＝1表示路由节点i为网关点，PLi＝n表示路由节点i为距离网关最远节点；

S13：同时每个节点计算自己周围的邻居数NB_i，那么可以通过层级PL_i和邻居数NB_i这两个参数得到每一个节点的节点负载邻居数同时计算出网络的链路负载权重即链路e_ij两端节点负载之和,表示为：

$>w_{e_{\mathrm{ij}}}=\frac{{\mathrm{NB}}_i}{{\mathrm{PL}}_i}+\frac{{\mathrm{NB}}_j}{{\mathrm{PL}}_j};$>

所述的信道分配步骤包括以下子步骤：

S21：将链路负载按照大小顺序排列，然后按照启发式信道分配方法从链路负载权重最大处开始进行信道分配，其中每条链路在分配信道时需要计算一个干扰权重CID，干扰权重CID为在干扰范围内使用相同信道的其他链路的链路负载权重之和，表示为：

$>\mathrm{CID}=\frac{1}{2}\underset{e_{\mathrm{ij}},e_{\mathrm{uv}}\in E,e_{\mathrm{ij}}\ne e_{\mathrm{uv}}}{\Sigma }\left[I\left(e_{\mathrm{ij}}{e}_{\mathrm{uv}}\right)(w_{e_{\mathrm{ij}}}+w_{e_{\mathrm{uv}}})\right],$>

式中，I(e_ije_uv)表示链路e_ij和链路e_uv存在干扰，当且仅当两条链路在干扰范围内，互为潜在干扰链路，并且都分配了相同链路，表示为：

链路两个节点为i和j的链路L按照以下子步骤来分配信道：

S211：如果K(i)≠Φ且节点K(j)≠Φ，则为链路L分配信道c，c∈{c|c＝C(i)∩C(j)}，如果c不唯一，则选择集合c中干扰权重CID最小的信道；

S212：如果K(i)≠Φ，但是K(j)＝Φ，则在节点j已经分配了的信道中选择干扰权重CID最小的信道c分配给节点i，即为链路L分配信道c；

S213：如果K(j)≠Φ，但是K(i)＝Φ，则在节点i已经分配了的信道中选择干扰权重CID最小的信道c分配给节点j，即为链路L分配信道c；

式中，Φ为空集，K(j)＝Φ表示为节点j没有可用网卡；

S22：信道分配完毕；

所述的路由寻路步骤包括以下子步骤：

S31：当源节点需要发送数据的时候，源节点广播路径请求消息PREQ开始寻路过程；

S32：中间节点接收到路径请求消息PREQ之后，计算当前节点上一跳的信道多样性指数度量MCDI并累加路径请求消息PREQ中的MCDI，将得到的值与路由表中存储的MCDI值进行比较，如果较小，则保存该值并更新路径请求消息PREQ中的MCDI，继续转发路径请求消息PREQ；如果较大，则丢弃此路径请求消息PREQ，所述的MCDI表示为：

>

式中，MCDI(p)表示路径p上的信道多样性指数度量，i为路径p中任意节点，α和β为权重因子，用于平衡流内干扰和流间干扰在整个MCDI中所占权重，CDP_i为信道多样性感知参数，ETT_i为当前链路的期望传输时间，EWT_i为当前链路的期望等待时间，CDP_i可表示为：

$>{\mathrm{CDP}}_i=\frac{n_{i,\mathrm{hop}}}{n_{\mathrm{ch}}},$>

式中，n_i,hop表示节点i在路径p上的跳数，如果节点i到源节点的跳数超过3，则该值为3，如果不足3，则该值为到源节点的跳数；n_ch表示节点i与对应前三跳节点间形成的三跳链路使用不同信道的个数，如果节点i与对应前三跳节点间形成的三跳链路使用不同信道的个数超过3，则该值为3，如果小于3，则该值为不同信道个数；

ETT_i和EWT_i的关系可表示为：

$>{\mathrm{EWT}}_i=\underset{e_{\mathrm{ab}}\in I\left(e_{\mathrm{pre}\left(i\right)i}\right)}{\Sigma }{\mathrm{ETT}}_{e_{\mathrm{ab}}},$>

式中，e_pre(i)表示节点i与上一跳节点之间的链路，I(e_pre(i)i)表示对链路产生干扰的所有链路的集合；

S33：当目的节点收到多个路径请求消息PREQ的时候，计算所有上一跳的MCDI并累加路径请求消息PREQ中的MCDI，对MCDI值最小的PREQ进行路径回复信息PREP的回复，建立起路径上MCDI值最小的路径；

S34：路径选择结束，开始数据传输。

当链路的两个端点邻居数NB_i越多优先级别越高链路负载权重就越大，反之两个端点邻居数NB_i越少优先级别越低所述的链路负载权重就越小。

所述的信道多样性感知参数CDP_i用于减小流内干扰，所述的当前链路的期望传输时间ETT_i和当前链路的期望等待时间EWT_i用于减小流间干扰。

所述的权重因子α为流内干扰系数，所述的权重因子β为流间干扰系数，α+β＝1。

本发明的有益效果是：据无线Mesh网络的这种流量特点及其拓扑信息，提出了一种基于链路负载权重的静态信道分配方法，达到最小化网络中链路之间的干扰的目的，再在路由选择中充分考虑流内干扰和流间干扰因素，得到最优路径，提高网络中的吞吐量，减小延时。

附图说明

图1为无线Mesh回传网络架构图；

图2为本发明系统与方法示意图；

图3为本发明方法流程图；

图4为实施例中计算节点负载和邻居数示意图；

图5为实施例中计算每条链路上的负载权重示意图；

图6为实施例中分配负载最大链路示意图；

图7为实施例中信道分配结果；

图8为实施例中路径选择分析图。

具体实施方式

下面结合附图进一步详细描述本发明的技术方案：本实施例为3*3的网状拓扑下，2个网卡，4个可用信道，网关节点为节点5的信道分配情况。

如图3所示，首先计算每一个节点的邻居数目和等级，每一个节点的NB表示的是节点的邻居数量，PL表示的是节点的层级。

然后计算链路的负载情况，结果如图4所示。在图4中，每一条链路上的数值表示的是每一条链路负载情况。

根据链路负载权重大小关系按照启发式算法从负载最大的链路开始分配信道。如图5所示，从链路负载最大处开始分配，先分配中间四条链路，然后再分配链路负载较小的链路。最终的信道分配结果如图6所示。

在得到信道分配结果之后，便可以再寻路过程中通过路由算法中的MCDI计算来寻求最佳路径。本实施例采用的路由算法为802.11s中定义的HMWP路由协议，将路由协议中的路由判据空时度量替换为本发明中的MCDI。

当网络中有数据需要传输的时候，如图7所示，当节点1需要传输数据给节点6的时候，源节点通过广播PREQ请求，PREQ在达到节点6的过程中计算每一条链路上的MCDI大小，节点6根据计算出来的MCDI大小选择期望传输时间最小的路径作为数据传输路径。

如果从1->6此时有两条路，分别是1->2->5->6和1->2->3->6，第一条路径上三跳之内分别用了三个不同的信道，而第二路径上三跳之内只用了两个信道，很明显，第一条路径的流内干扰要小于第二条路径；而同时第一条路径上的中间两跳2->5->6跟第二条路径上的中间两跳2->3->6相比较，第一条路径上选取的信道4和信道3在两跳的干扰范围内所受到的流间干扰更小；理论分析之后，我们设置流内干扰和流间干扰系数分别为0.5和0.5，并且假定数据在每一跳上的传输时间均相同为ETT，计算两条路径的具体度量值。ETT_i和

首先1->2,在节点2处计算出来的CDP₂＝1(下标为所计算的节点)，由于1->2使用的信道2在两跳干扰范围内有三条使用相同信道的链路，那么1->2的期望等待时间EWT₂＝3ETT，得到MCDI(2)＝0.5*1*ETT+0.5*3*ETT＝2ETT；这个值在第一条路径和第二条路径上是一样的。

路径一上1->2->5使用了两个不同的信道，那么CDP₅＝1，由于2->5使用的信道4在两跳干扰范围内只有一个使用相同信道的链路，那么期望等待时间为EWT₅＝ETT，则MCDI(5)＝MCDI(2)+0.5*1*ETT+0.5*ETT＝3ETT；同时路径二上1->2->3上使用了两个相同的信道，那么CDP₃＝2，由于2->3使用的信道2在两跳干扰范围内有三条使用相同信道的链路，那么2->3的期望等待时间为EWT₃＝3ETT；则可以得到MCDI(3)＝MCDI(2)+0.5*2*ETT+0.5*3ETT＝4.5ETT。

路径一上1->2->5->6使用了三个不同的信道，那么CDP_6inPath1＝1，由于5->6使用的信道3在两跳干扰范围内只有一个使用相同信道的链路，那么期望等待时间为EWT_6inPath1＝ETT，则MCDI(6inPath1)＝MCDI(5)+0.5*1*ETT+0.5*ETT＝4ETT；路径1->2->3->6三跳内使用了两个不同的信道，那么CDP_6inPath2＝3/2，由于3->6使用的信道1在两跳干扰范围内有三条使用相同信道的链路，那么3->6的期望等待时间EWT_6inPath2＝3ETT，则MCDI(6inPath2)＝MCDI(3)+0.5*3/2*ETT+0.5*3ETT＝6.75ETT。

综上可得到两条路径上的期望传输时间分别为4ETT和6.75ETT，节点6会根据计算的出来MCDI选取流间干扰和流内干扰较小的第一条路径作为数据传输路径。