CN102612109A

CN102612109A - 基于拓扑优化和降低干扰的无线Mesh网络路由信道联合分配方法

Info

Publication number: CN102612109A
Application number: CN2011100219373A
Authority: CN
Inventors: 黄书强; 周玉宇
Original assignee: Individual
Current assignee: Individual
Priority date: 2011-01-19
Filing date: 2011-01-19
Publication date: 2012-07-25

Abstract

本发明公开了一种基于拓扑优化和降低干扰的无线Mesh网络路由信道联合分配方法，本发明在信道分配时采用“拓扑结构优化-最大流路由-链路分组-组分配信道”的路由信道联合算法，可以有效的解决信道分配中的抖动问题以及路由效率问题，以提高系统的吞吐量和效率。利用最大流最小割原理对网络结构拓扑进行优化，在保持公平性的同时尽可能提高吞吐量。通过拓扑结构优化之后，参与信道分配的链路数减少，干扰和冲突减少，使得后面的信道分配效率大大提高，降低路由维护的成本，提高系统效率。路由之后，通过二段信道分配算法，可以实现路由算法和信道分配的有效联合。该算法可以避免信道分配中局部调整可能引起的整体抖动问题，信道分配的效率更高，大大提升网络的性能。

Description

基于拓扑优化和降低干扰的无线Mesh网络路由信道联合分配方法

技术领域

本发明涉及Mesh网络拓扑结构优化和信道分配领域，特别涉及一种基于拓扑优化和降低干扰的无线Mesh网络路由信道联合分配方法。

背景技术

无线Mesh网络因其低成本、灵活性以及易用性等特点使得其应用越来越广泛，无线Mesh网络可以部署在各种特定的场合，采用有限的基础设施就可以提供无处不在的网络接入服务。一个无线Mesh局域网是由一些网状节点组成的，见图1和图2所示，这些节点通过无线接口来实现网络的多跳连接。

当前WMN面临的主要问题之一是，当在邻近区域多链路同时传输时，它们相互之间会产生干扰并导致网络性能下降。为解决这个问题，WMN使用多个正交信道模式，节点通过多个网络接口在不同的信道上同时传输和接收，并且在邻近区域可以同时多路传输。这种多信道模式可显著提高WMN的吞吐量，但由于信道分配受到可用信道和接口的数目、网络拓扑和通信需求等诸多因素的限制，特别是由于可用信道数目的限制，传输干扰并不能被完全消除，仍成为影响网络吞吐量的一个重要因素。

IEEE 802.11b/g和IEEE 802.11a标准分别定义为3和12个正交信道在多接口WMNS中使用，多信道将很大的提高网络吞吐量。多接口WMN的最重要设计问题之一是信道分配问题，来解决每个射频接口怎样分配信道。好的信道分配策略，将会提高网络吞吐量，但不适当的信道分配策略将会导致吞吐量下降，因为信道分配策略中存在多信道隐藏终端问题，网络拓扑不连通导致网络分割和分配带宽时没有保证用户的公平性。

当前的无线节点装置在同一节点上采用多个射频，每个射频设计成可以转换成多个正交信道，这样多个信道在一个区域可以同时发射，使得信道之间的干扰减轻，因而系统的吞吐量也随着得到提高。但由于信道分配受到可用信道和接口的数目、网络拓扑和通信需求等诸多因素的限制，由于可用信道的限制，传输干扰并不能被完全消除，仍成为影响网络吞吐量的一个重要因素。

信道分配策略也要考虑整个网络连通性，当两个相邻节点分配相同的信道时，这两个节点才能相互间通信。邻近节点在冲突域中用相同的信道传输数据应该被限制，邻节点的链路将会相互干扰导致整个网络吞吐量下降。信道分配策略也决定在网络链路上的可用带宽，在干扰范围内分配相同信道的链路不能同时传输数据并且它们共同分享信道的最大容量。

在多信道无线网状网信道分配策略的目标是为每个网络接口分配一个射频信道。在一个信道分配策略中需要满足下面3个主要的限制条件：(1)分配给每个无线mesh网络节点的信道数目受到节点接口数的限制。(2)两个节点包含一条虚拟链路并且这条链路承载了一些负载，那么这两个节点至少要分配一个相同的信道。(3)在干扰域内，分配相同信道的链路预期负载总和不能超过信道的总容量。

在前面提出信道分配策略中都受到条件(1)的限制，当一个节点射频接口选择一个信道时，信道分配策略不要只依赖于链路干扰范围内节点间的信息。在信道分配策略中忽略信道间相互依赖关系，可能会增加违背(1)限制条件，例如节点分配不同信道数大于它的射频接口数，通常解决的方法是对信道分配进行调整即通过递归方法替换先前信道分配，可能导致整个网络重新进行信道分配。这样则会导致网络的延时。

综上所述，目前无线Mesh网络的不足之处是传输干扰影响吞吐量和信道分配不合理影响工作效率。

发明内容

本发明所要解决的技术问题是提供一种基于拓扑优化和降低干扰的无线Mesh网络路由信道联合分配方法，避免干扰合理分配信道，优化无线Mesh网络的使用效率。

为解决上述技术问题，本发明采用的技术方案为：一种基于拓扑优化和降低干扰的无线Mesh网络路由信道联合分配方法，包括以下步骤：

1)信号传输开始；

2)优化拓扑结构，将传输的信号通过一种基于流量感知和流量公平分配的拓扑结构贪婪算法转化为树结构，形成优化后的Mesh拓扑结构；

3)对所述优化后的Mesh拓扑结构利用AODV协议进行路由选择，AODV路由协议快速自适应动态链路状况，使之根据发送数据分组的需要进行路由发现，根据网络拓扑结构按需建立路由表内容，即动态链路；

4)对上述动态链路进行干扰避免的二步启发式信道分配算法；第一步，链路-组绑定；第二步，组道分配；

5)流量缩放；

6)信号分配结束。

所述步骤2)中，假定所有的物理链路容量和节点链路容量在一个正常范围[a，b]内，不会出现链路相差过大的情况；同时，为了减少跳数所带来的延时效应，本发明假定同一层之间的节点不进行通信，节点是逐层转发，不考虑网关内部节点之间的通信，只考虑节点和网关之间的数据交互。

所述步骤3)中，在路由发现过程中，主要根据RREQ请求报文和RREP应答报文来进行。在路由维护过程中，主要根据Hello消息和RERR消息来进行。

所述优化后的Mesh拓扑结构在进行路由发现时，消息不在同层之间传播。

所述步骤4)中，所述链路组绑定，即根据链路流量情况，根据利用率将链路进行分组，同时对组进行合并使得节点分配的链路不超过接口数限制。

所述步骤5)中，所述组道分配将组根据干扰情况进行信道分配，保证一次分配成功，避免局部信道调整引起整体抖动。

本发明相对于现有技术，具有以下有益效果：本发明在信道分配时采用“拓扑结构优化-最大流路由-链路分组-组分配信道”的路由信道联合算法，可以有效的解决信道分配中的抖动问题以及路由效率问题，以提高系统的吞吐量和效率。利用最大流最小割原理对网络结构拓扑进行优化，在保持公平性的同时尽可能提高吞吐量。通过拓扑结构优化之后，参与信道分配的链路数减少，干扰和冲突减少，使得后面的信道分配效率大大提高，降低路由维护的成本，提高系统效率。路由之后，通过二段信道分配算法，可以实现路由算法和信道分配的有效联合。该算法可以避免信道分配中局部调整可能引起的整体抖动问题，信道分配的效率更高，大大提升网络的性能。

附图说明

图1是现有Mesh网络结构图；

图2是现有的Mesh网络的拓扑结构图；

图3是传统信道分配局部调整所引起的连锁反应的反馈图；

图4是优化的Mesh网络的拓扑结构图；

图5是本实施例的Mesh网络的拓扑结构图；

图6是本发明的流程结构图。

具体实施方式

下面结合实施例及附图对本发明作进一步详细的描述，但本发明的实施方式不限于此。

如图6所述，为本发明的流程结构图；1)信号传输开始；2)优化拓扑结构，将传输的信号通过一种基于流量感知和流量公平分配的拓扑结构贪婪算法转化为树结构，形成优化后的Mesh拓扑结构；3)对所述优化后的Mesh拓扑结构利用AODV协议进行路由选择，AODV路由协议快速自适应动态链路状况，使之根据发送数据分组的需要进行路由发现，根据网络拓扑结构按需建立路由表内容，即动态链路；4)对上述动态链路进行干扰避免的二步启发式信道分配算法；第一步，链路-组绑定；第二步，组道分配；5)流量缩放；6)信号分配结束。

在本实施案例中，首先利用最大流最小割原理对网络结构拓扑进行优化，其具体过程为：

假定层次化Mesh结构模型中，链路ij的链路容量为C_ij，i节点自身产生的流量为f(i)，假定节点的容量大于或等于其上行链路容量。本算法就是要把网状网结构转化为树结构，转化过程中一方面需要保持节点流量分配公平性，另一方面需要尽可能提高网络吞吐量，在转化过程中，充分利用了网络流量图中的最大流最小割原理，即网络的最大流量小于或等于该有向图的最小割的容量之和。

对于图4所示，节点A为网关，数字为链路容量，单位为Mbps。除节点A外，如果其它所有节点自身产生的流量f(i)相等，那么对拓扑结构进行转化的过程如下：

(1)从网关节点开始，逐层对图结构进行剪枝。通过删除一些边，使得每个节点只与一个上层节点相连；

(2)首先节点A、B、C、D、F的转发路径已经确定，需要对第二层的节点E进行处理，要在EB和EC中选择一条路径进行数据转发。那么此时如果通过EB转发，B、D、E每个节点最多分配的带宽是链路BA的链路容量除以下层节点数，即54/3＝18Mbps。如果通过EC转发，B、C、E每个节点最多分配的带宽是链路BA的链路容量除以下层节点数，即48/3＝16Mbps，基于最大化用户带宽和吞吐量贪婪思想，这个时候应该EB，删除EC。

(3)处理下一层，对节点H和I进行路径选择。EB已删除，那么节点H的流量必定经过节点B，如果1节点选择链路IE时候，节点B、D、E、G、H、I最多分配的带宽是BA链路容量除以下层服务节点总数，即54/6＝9Mbps。如果I节点选择链路IF，节点C、F、I、J最多分配的带宽是CA链路容量除以下层服务节点总数，即48/4＝12Mbps，基于最大化用户带宽和吞吐量贪婪思想，这个时候应该IF，删除IE。同理H节点应该选择路径HE，删除HD。

(4)处理下一层，需要先处理节点N，因为节点M和O都必须经过B和C，只有节点N有可能选择B或者C。通过计算最大可能分配带宽，得知节点N选择NI，删除NH。同理可得节点M选择MH，节点O选择OI。

(5)链路选择过程中，保持拓扑连通性，保持每个节点都处于一条源节点到目的节点的链路上。

整个网络经拓扑结构优化后，利用AODV协议进行路由选择。AODV是一种典型的按需路由协议，是根据发送数据分组的需要进行路由发现，网络拓扑结构和路由表内容是按需建立的，这种路由协议路由开销较小，只在必要的时候才进行路由发现，给网络带来的负载很小。由于本发明优化的拓扑结构，流量变化不大的时候，拓扑结构变化也不大，分配的信道也不会发生太大变化，反之对路由影响也不大，网络相对稳定，所以适合利用AODV路由来处理。仅当节点失效或者流量剧烈抖动的时候才需要重新进行拓扑结构的调整以及路由发现。AODV路由协议包括路由发现和路由维护两个过程，路由发现过程中，主要根据RREQ请求报文和RREP应答报文来进行。路由维护过程中，主要根据Hello消息和RERR消息来进行，维护本地连接性和路由过期以及路由删除，路由修复等任务。基于本发明拓扑结构，在进行路由发现时，消息不在同一层之间传播。AODV路由协议提供对动态链路状况的快速自适应，处理开销和存储开销小，具有良好的性能。

通过拓扑结构优化的ADOV路由算法获得了整个网络链路初始负载状况，给定整个网络虚拟链路的预期负载后，本发明基于干扰避免的信道分配信道分配方法分以下几步：

(a)链路-组绑定策略，在分层的基础上对每层的链路进行分配组，并通过网络拓扑控制进行链路组绑定优化，此阶段主要目的是保证分配给每个节点的信道数目不能超过其接口数目；

(b)组信道分配策略，在链路组绑定基础上进行组信道分配，主要目的是最小化每个冲突域链路带宽总利用率即最小化每个信道的干扰量；

(c)确定最大缩放因子，获得一个信道分配成功的可调度流量集合。在确定最大缩放因子时，尽可能利用平滑的方法消除一些比较大的缩放因子孤立点，尽可能降低最大缩放因子。其具体过程为：

A、链路-组绑定策略

变量进行说明。L(e)∈N，e∈E表示链路e绑定的组号。初始把每条链路e的组L(e)＝0即链路e没有绑定组。neigh(u)定义节点u可以通信的节点集合。给u相关联的链路绑定不同的组数不会超过节点u的接口数K，因此可以说节点相关联链路所绑定的组集合是可行的。G(u)表示节点u相关联链路绑定不同组的集合。把链路带宽利用率表示为

即链路e在潜在冲突域内所有链路e₀的流量f(e₀)，包含自身和各自链路容量比的总和。最后把组中最大链路带宽利用率作为组链路带宽利用率。因此在第三阶段把分配相同组的链路将分配同一个信道，组链路带宽利用率将表示冲突域链路带宽总利用率，这也是信道分配算法所得到的最终结果。

信道分配算法的链路-组绑定策略将访问每层链路集合，通过这层链路流量从大到小顺序进行分配组。假设每个节点有q个接口，则链路绑定组有三种可能情况：

(1)链路e(v，u)的两个节点v，u，它们的相关联的链路已经绑定的不同组数都小于q。在这种情况，我们绑定一个新的组给链路e(v，u)。

(2)链路e(v，u)两个节点中的一个节点v相关联的链路已经绑定的不同组数等于q，另一个节点u小于q。在这种情况，选择节点v相关联的链路中最小组链路带宽利用率的组和链路e(v，u)绑定。

(3)链路e(v，u)两个节点相关联的链路绑定的不同组数都等于q，这种情况下，有两种情形，(1)两个节点相关联的链路中至少有q条链路已经绑定q个不同的组且这两个节点相关联的链路存在绑定相同的组，这种情形，将最小组链路带宽利用率的组和链路e(v，u)绑定。(2)两个节点相关联的链路中至少有q条链路已经绑定q个不同的组且这两个节点相关联的链路不存在绑定相同组，当要对链路e(v，u)绑定组时，则需要对两个节点相关联的链路中的两个组进行合并。具体过程见图6所示。

B、组信道分配策略

在信道分配策略的第二阶段都为E中每条链路都绑定一个组。接下来就要给每一个组分配一个信道。这个部分的主要目标是最小化每个冲突域链路带宽总利用率即最小化信道干扰量。

首先对组链路带宽利用率从大到小进行排序，然后访问每个组每条边。定义ξ_c为链路被分配为信道c的链路集和P(g)为组为g的链路潜在的干扰链路集合(这些链路没有和组g绑定)。1定义为组g中所有链路所包含的所有终端节点集。在考虑在I中的每个节点干扰范围内的节点u，如果以u为终端节点的链路不属于组g，则把这条链路加进集P(g)中。然后对于每个信道c，计算S(g，c)，S(g，c)定义为分配信道c的链路和P(g)的交集)。如果存在信道c₀，

这说明了组g中所有链路的干扰链路集没有被分配信道c₀，存在多个这样的c₀的时候，我们将选择一个被分配最多链路数的信道(即ξ_c最大的时候)，所以在分配信道c₀的链路中没有与组g中的链路相互干扰。如果不存在这样的信道c₀，分配信道c给组g，最大限度地减少组g中链路的冲突域最大总利用率。

C、确定最大缩放因子

在前面部分的信道分配策略已经计算出每个信道的最大干扰量，把它表示为

下面将通过缩放因子λ对整个网络流量集合进行缩放，可以表示为：

这里f(e)为通过链路e的流量。这样才能保证有一个可调度的流量集，满足

上述实施例仅为本发明的较佳实施例，并非用来限定本发明的实施范围。即凡依本发明内容所作的均等变化与修饰，都为本发明权利要求所要求保护的范围所涵盖。

Claims

1.一种基于拓扑优化和降低干扰的无线Mesh网络路由信道联合分配方法，其特征在于：包括以下步骤：1)信号传输开始；

5)流量缩放：

6)信号分配结束。

2.根据权利要求1所述的基于拓扑优化和降低干扰的无线Mesh网络路由信道联合分配方法，其特征在于：所述步骤2)中，假定所有的物理链路容量和节点链路容量在一个正常范围[a，b]内，不会出现链路相差过大的情况；同时，为了减少跳数所带来的延时效应，本发明假定同一层之间的节点不进行通信，节点是逐层转发，不考虑网关内部节点之间的通信，只考虑节点和网关之间的数据交互。

3.根据权利要求1所述的基于拓扑优化和降低干扰的无线Mesh网络路由信道联合分配方法，其特征在于：所述步骤3)中，在路由发现过程中，主要根据RREQ请求报文和RREP应答报文来进行。在路由维护过程中，主要根据Hello消息和RERR消息来进行。

4.根据权利要求3所述的基于拓扑优化和降低干扰的无线Mesh网络路由信道联合分配方法，其特征在于：所述优化后的Mesh拓扑结构在进行路由发现时，消息不在同层之间传播。

5.根据权利要求1所述的基于拓扑优化和降低干扰的无线Mesh网络路由信道联合分配方法，其特征在于：所述步骤4)中，所述链路组绑定，即根据链路流量情况，根据利用率将链路进行分组，同时对组进行合并使得节点分配的链路不超过接口数限制。

6.根据权利要求4所述的基于拓扑优化和降低干扰的无线Mesh网络路由信道联合分配方法，其特征在于：所述步骤5)中，所述组道分配将组根据干扰情况进行信道分配，保证一次分配成功，避免局部信道调整引起整体抖动。