多网关无线Mesh网络干扰与负载感知路由选择方法

摘要

本发明涉及一种多网关无线Mesh网络干扰与负载感知路由选择方法，该方法如下：建立多网关网络模型，获取网络拓扑信息并依此为网络节点分配不同的权值；通过网络拓扑信息及无线链路的衰落特性，推导网络中链路信号与干扰噪声比SINR的分布特性，进而计算链路的中断概率和中断速率；获取Mesh路由器节点缓存包数量，并计算网关节点容量占比；针对客户端业务和Internet业务设计具有保序性的路由度量，并对AODV路由协议进行修改；在有客户端业务和Internet业务请求时，网络依据路由协议中的路由度量为不同业务选路。本发明考虑了网络干扰因素和负载分布信息，能够有效降低网络干扰，实现网络负载均衡，提高网络吞吐量。

说明书

技术领域

本发明涉及无线Mesh网络路由技术领域，更具体地，涉及一种多网关无 线Mesh网络干扰与负载感知路由选择方法。

背景技术

无线Mesh网络具有高带宽、快速部署、易于安装、维护简单等优势，作 为一种可以解决“最后一公里”宽带Internet接入问题的新兴技术，正受到全 球范围的标准化组织以及各学术研究机构的广泛关注。无线Mesh网络在灾难 恢复临时组网、楼宇自动化等应用领域具有重要的应用。

无线Mesh网络流量的突发性容易造成网络负载分布不均，引起网络拥塞， 影响网络通信性能。尤其在Internet业务和客户端业务共存时，网络中的网关 和其他一些节点如中央节点容易形成瓶颈节点，导致阻塞。具有负载感知的路 由选择方法能够避免流量过于集中，进而均衡网络负载分布，提高资源利用率。 从目前国内外的研究现状来看，无线Mesh网络的路由选择问题的研究大部分 集中于骨干无线Mesh网络或客户端Mesh网络领域，针对多网关无线Mesh网 络路由选择方法的研究较少且存在问题：大多数是以到网关的最小距离为选路 依据，没有考虑网络干扰和负载等因素，网络性能得不到充分发挥；或者只是 对网络节点缓存数据量进行了初步衡量，没有考虑网络中的干扰因素；或者是 存在非保序性和网关探测包等问题，造成大量的额外开销，在网络流量大的场 景下难以提升网络性能。

香农容量是在确定性信道条件下得到的信道容量，是一个确定值。但实际 上，信道状态是一个不断变化的随机过程。对于信道功率增益随机变化的信道， 当发送端不知道信道的具体增益时，无论发送端以任何传输速率发送数据，接 收端都有可能无法正确译码，即错误概率非0。这是由于存在信道增益所支持 的信道容量低于发送端传输速率的可能。这时若要错误概率始终为0，当且仅 当发送端传输率始终为0。此时可以定义中断容量，也叫中断速率，当以此作 为传输速率时，信道能以(1-p)的概率承载业务，p为中断概率。现有中断概率 的计算仍以链路接收端的SNR(Signal to Noise Ratio)门限值作为接收端是否成 功接收的依据。

综上，多网关无线Mesh网络路由度量的设计有必要针对非保序性和网关 探测包等开销问题，考虑网络节点承载业务量、链路中断速率以及网关特性等 因素，在降低网络干扰的同时，实现网络负载均衡，提升网络吞吐量性能。

发明内容

本发明要解决的技术问题是提供一种能够有效降低网络干扰，实现网络负 载均衡，提高网络吞吐量的多网关无线Mesh网络干扰与负载感知路由选择方 法。

为解决上述技术问题，本发明的多网关无线Mesh网络干扰与负载感知路 由选择方法的步骤如下：

步骤1)建立多网关网络模型，获取网络拓扑信息，根据网络节点到网关的最 小距离，为多网关无线Mesh网络中的网络节点分配不同的权值；

节点j的权值Rank_j由式(1)给出：

式中：GW表示网关集合；dist(j,GW)表示网络节点j与网关集合中所有网关节 点之间欧氏距离的最小值；R_h表示节点的载波感知范围；V表示路由器节点集 合；ω₁、ω₂和ω₃分别表示不同节点的权值，其中ω₁＞ω₂>ω₃，表示离网关越近的 节点被赋予的权值越大；

步骤2)根据式(2)、式(3)分别计算网络中任一通信链路(u,v)的中断概率 P_out(u,v)和任一节点j所在通信链路的中断速率C_out(j)：

$P_{\mathrm{out}}(u,v)=1-\underset{w\in \eta \left(v\right)}{\Pi }(\left(\frac{P_t\left(u\right)·{\mu }_u}{{\gamma }_{\mathrm{th}}·\tau \left(w\right)·P_t\left(w\right)·{\mu }_w+P_t\left(u\right)·{\mu }_u}\right)·\exp (-\frac{N_0·{\gamma }_{\mathrm{th}}}{P_t\left(u\right)·{\mu }_u}))---\left(2\right)$

C_out(j)＝(1-P_out(u,v))·B·log₂(1+γ_th)      (3)

式中：η(v)表示节点v的干扰节点集合，该集合定义为节点v感知到网络中对 其造成干扰的节点集合；w表示干扰节点集合中的干扰节点；P_t(u)表示通信节 点u的发送功率；μ_u表示通信链路(u,v)信道功率增益h_u(v)的均值；γ_th为通信 链路(u,v)接收端正确译码的SINR门限值；τ(w)表示节点w的分组产生率； P_t(w)表示干扰节点w的发送功率；μ_w表示各干扰节点与通信链路接收端的信道 功率增益h_w(v)的均值；N₀表示噪声功率；B是正交信道的信道带宽；

步骤3)根据式(4)计算任一网关节点k的容量占比Ra_k：

${\mathrm{Ra}}_k=\frac{\mathrm{Qlength}\left(k\right)}{\mathrm{Gqlen}}---\left(4\right)$

式中：Qlength(k)表示网关节点k在有路由请求时的缓存队列长度；Gqlen表示 网关最大队列长度；

步骤4)根据式(5)、式(6)分别计算节点j针对客户端业务的具有保序性的 路由度量Metric(p)和针对Internet业务到网关节点k的具有保序性的路由度量 Metric(p,k)，并依此对AODV协议进行修改，在AODV路由协议处理路由请求 和路由应答时依据该路由度量更新路由表；

$\mathrm{Metric}\left(p\right)=\underset{j\in p}{\Sigma }\frac{\mathrm{Qlength}\left(j\right)·{\mathrm{Rank}}_j}{C_{\mathrm{out}}\left(j\right)}---\left(5\right)$

式中：p表示源端到目的端的路由路径；Qlength(j)表示节点j在有路由请求时 的缓存队列长度；Rank_j表示节点j的权值；C_out(j)表示节点j所在通信链路的中 断速率；

$\mathrm{Metric}(p,k)=\underset{j\in p}{\Sigma }\frac{\mathrm{Qlength}\left(j\right)·{\mathrm{Rank}}_j}{C_{\mathrm{out}}\left(j\right)}+{\mathrm{Ra}}_k·\frac{L_{\mathrm{gw}}}{R_{\mathrm{gw}}}---\left(6\right)$

式中：(p,k)表示源端到网关节点k的路由路径；Qlength(j)、Rank_j、C_out(j)含义 与式(5)相同；Ra_k表示网关节点k的容量占比；L_gw表示固定的数据包大小； R_gw表示与网关节点相连的链路数据速率；

步骤5)在有客户端业务或Internet业务请求时，网络依据路由协议中的路由度 量为不同业务选路；针对客户端业务，源端向目的节点发起路由请求，目的节 点将最优路径信息返回至源端；最优路径为源端与目的节点之间所有路径中链 路路由度量之和最小的路径；针对Internet业务，源端向网络中每个网关分别 发送路由请求，每个网关将到该网关的最优路径信息返回至源端，在源端进行 比较，选择到最优网关的最优路径；最优路径为源端与各网关之间所有路径中 链路路由度量之和最小的路径。

本发明的有益效果：

1、通过获取网络拓扑信息记录网络节点位置等信息。由于网络中距离网关 较近的节点相比网络中距离网关较远的节点承受较多的业务量的概率更大，因 此对网络中与网关距离不同的节点进行不同处理，避免当Internet业务和客户 端业务同时存在时网关节点或距离网关较近的节点由于出现较大业务量所导致 的阻塞。

2、通过信道功率增益计算通信链路的SINR(Signal to Interference plus Noise  Ratio)值，并将此作为通信链路接收端是否能够成功接收数据包的依据，本方法 提升了以SNR为依据衡量链路质量的准确性。本方法可以在IEEE802.11b/g频 谱内有限的信道资源下，降低网络内数据流间干扰，增加并行数据流传输个数， 提升网络容量。

3、通过推导SINR的累积分布函数CDF(Cumulative Distribution Function)， 避免了SNR没有考虑网络干扰带来的问题，以此获取链路的中断概率和中断速 率，将其纳入路由度量中进行路由选择。本发明考虑了网络干扰因素和负载分 布信息，能够有效降低网络干扰，实现网络负载均衡，提高网络吞吐量。

4、通过衡量多个网关的容量占比的大小，进一步选择最优的网关。本方法 可以避免网络流量在某个网关节点处过于集中的问题，从而达到均衡网关节点 处负载的目的。

附图说明

下面结合附图和具体实施方式对本发明作进一步详细说明。

图1为本发明多网关无线Mesh网络干扰与负载感知路由选择方法总体流 程图；

图2为本发明多网关网络示意图；

图3为节点权值示意图；

图4为路由度量保序性说明图；

图5为针对不同业务的路由选择流程图；

图6为多网关网络选路示意图。

具体实施方式

下面结合附图对本发明作详细的描述：

如图1所示，本发明的一种多网关无线Mesh网络干扰与负载感知路由选 择方法具体包括以下步骤：

步骤1)建立多网关网络模型，按照网络拓扑信息为多网关无线Mesh网络中的 网络节点分配不同的权值；

本发明考虑具有两类节点的多网关无线Mesh网络场景：路由器节点和网 关节点。多网关网络如图2所示。路由器节点组成了无线Mesh骨干网，并作 为用户与Internet通信的中继，通过网关有线连接到Internet，有线链路的带宽 不受限制。每个网络节点配置多个网络接口卡和多个信道，本发明用G＝(V,E) 表示Mesh骨干网，V表示Mesh路由器节点集合，E表示所有的链路集合。GW 表示网关集合，g为网关个数，R_h为节点载波感知范围。按照建立的多网关网 络模型，根据网络节点到网关的最小距离为网络节点分配不同的权值，节点j 的权值Rank_j由式(1)给出：

式中：dist(j,GW)表示网络节点j与网关集合中g个网关节点之间欧氏距离的最 小值；R_h表示节点的载波感知范围；ω₁、ω₂和ω₃表示与网关不同距离的节点的 权值。令ω₁＞ω₂>ω₃，表示给距网关较近的网络节点分配较大的权值，以减小该 网络节点作为中继节点承载流量的概率。本发明拟定的节点权值为：ω₁＝1， ω₂＝0.8，ω₃＝0.3，在不同的网络环境下可以合理调整该参数。如图3所示，网 关节点具有最大的网络权值，除此之外，在网关节点载波感知范围内的节点具 有较大的节点权值，其他节点具有较小的节点权值。

步骤2)根据网络拓扑信息及无线链路的衰落特性，推导链路SINR的分布特性 ——累积分布函数CDF，进而计算链路的中断概率和中断速率；

(1)所述的链路SINR值表达式γ(u,v)如式(2)所示，

$\gamma (u,v)=\frac{P_t\left(u\right)·h_u\left(v\right)}{N_0+{\Sigma }_{w\in \eta \left(v\right)}\tau \left(w\right)·P_t\left(w\right)·h_w\left(v\right)}---\left(2\right)$

式中：N₀表示噪声功率；P_t(u)表示通信节点u的发送功率；η(v)表示节点v的 干扰节点集合，该集合定义为节点v感知到网络中对其造成干扰的节点集合；τ(w) 表示节点w的分组产生率，由文献【Interference Aware Routing in Multi-Radio  Wireless Mesh Networks】知节点w的分组产生率为设定的周期时间内(一般为 10s左右)的归一化发包速率，即节点发包速率与标称数据速率(标称数据速 率为网络支持的最大传输速率，如2Mbps、11Mbps等)的比值，当节点w以 全速率发包时τ(w)等于1，当节点w不发包时τ(w)等于0；P_t(w)表示干扰节点w 的发送功率；h_u(v)表示通信链路(u,v)的信道功率增益；w表示干扰节点集合中 的干扰节点；h_w(v)表示干扰节点w与通信链路接收端的信道功率增益，链路的 信道功率增益服从负指数分布，其累积分布函数H(x)由式(3)给出：

$H\left(x\right)=\frac{1}{{\mu }_h}·\exp (-\frac{x}{{\mu }_h})---\left(3\right)$

式中：x表示链路的信道功率增益；μ_h是信道功率增益的均值。

(2)根据SINR的表达式及信道功率增益的累积分布函数推导SINR的累积分布 函数CDF；可由式(4)给出：

$\left(\begin{array}{c}F\left(\gamma \right)=P(\gamma (u,v)<\gamma )=P(\frac{P_t\left(u\right)·h_u\left(v\right)}{N_0+{\Sigma }_{w\in \eta \left(v\right)}\tau \left(w\right)·P_t\left(w\right)·h_w\left(v\right)}<\gamma )\\ ={\int }_0^{\infty }P[P_t\left(u\right)·h_u\left(v\right)<(N_0+{\Sigma }_{w\in \eta \left(v\right)}\tau \left(w\right)·P_t\left(w\right)·x_w)·\gamma ]·H_w\left(x\right)\mathrm{dx}\\ =\underset{w\in \eta \left(v\right)}{\Pi }{\int }_0^{\infty }\frac{1}{{\mu }_w}·\exp (-\frac{x_w}{{\mu }_w}){\mathrm{dx}}_w-\\ \underset{w\in \eta \left(v\right)}{\Pi }({\int }_0^{\infty }\exp (-\frac{\tau \left(w\right)·P_t\left(w\right)·x_w·\gamma }{P_t\left(u\right)·{\mu }_u})·\frac{1}{{\mu }_w}·\exp (-\frac{x_w}{{\mu }_w}){\mathrm{dx}}_w·\exp (-\frac{N_0·\gamma }{P_t\left(u\right)·{\mu }_u}))\\ =1-\underset{w\in \eta \left(v\right)}{\Pi }(\left(\frac{P_t\left(u\right)·{\mu }_u}{\gamma ·\tau \left(w\right)·P_t\left(w\right)·{\mu }_w+P_t\left(u\right)·{\mu }_u}\right)·\exp (-\frac{N_0·\gamma }{P_t\left(u\right)·{\mu }_u}))\end{array}\right)---\left(4\right)$

式中：F(γ)表示SINR的累积分布函数；γ(u,v)表示链路(u,v)的接收节点v收到 的SINR值；γ表示SINR累积分布函数的自变量；x_w表示信道功率增益h_w(v) 被积分时的替代变量；H_w(x)表示信道功率增益h_w(v)的累积分布函数；μ_u表示 通信链路信道功率增益h_u(v)的均值；μ_w表示干扰链路信道功率增益h_w(v)的均 值；N₀、P_t(u)、η(v)、τ(w)、P_t(w)、h_u(v)、w、h_w(v)等含义与式(2)相同。

(3)根据SINR的分布特性计算链路的中断概率和中断速率；中断概率定义为当 链路的接收端收到的SINR值低于正确译码的门限值时，接收端无法正确译码 的概率。此时链路的传输速率为香农速率的(1-p)倍，p为中断概率，此时的链 路速率定义为中断容量，也叫中断速率。γ_th为接收SINR门限值(根据要求的 传输特性，如信源编码方式和链路带宽等设定，对于无线Mesh网络而言，γ_th取值在12.5dB-25dB之间)，则中断概率为：

$\left(\begin{array}{c}{P}_{\mathrm{out}}(u,v)P(\gamma (u,v)<{\gamma }_{\mathrm{th}})=F\left({\gamma }_{\mathrm{th}}\right)\\ =1-\underset{w\in \eta \left(v\right)}{\Pi }(\left(\frac{P_t\left(u\right)·{\mu }_u}{{\gamma }_{\mathrm{th}}·\tau \left(w\right)·P_t\left(w\right)·{\mu }_w+P_t\left(u\right)·{\mu }_u}\right)·\exp (-\frac{N_0·{\gamma }_{\mathrm{th}}}{P_t\left(u\right)·{\mu }_u}))\end{array}\right)---\left(5\right)$

η(v)表示节点v的干扰节点集合。节点j所在通信链路的中端速率为：

C_out(j)＝(1-P_out(u,v))·B·log₂(1+γ_th)      (6)

式中：B是正交信道的信道带宽。

步骤3)获取Mesh路由器节点缓存包数量并计算网关容量占比；

(1)所述的路由器节点缓存包数量为Qlength(j)，表示路由器节点j在有路由请 求时的缓存队列长度；

(2)所述的网关容量占比由式(7)给出：

${\mathrm{Ra}}_k=\frac{\mathrm{Qlength}\left(k\right)}{\mathrm{Gqlen}}---\left(7\right)$

式中：Ra_k表示网关节点k的容量占比；Qlength(k)表示网关节点k在有路由请 求时的缓存队列长度；Gqlen表示网关最大队列长度。

步骤4)通过考虑节点权值、链路中断速率、网关容量占比等因素，针对客户 端业务和Internet业务设计具有保序性的路由度量，并对AODV协议进行修改， 在AODV路由协议处理路由请求和路由应答时依据该路由度量更新路由表，以 实现路由度量的功能；

(1)所述的针对客户端业务的路由度量为：

$\mathrm{Metric}\left(p\right)=\underset{j\in p}{\Sigma }\frac{\mathrm{Qlength}\left(j\right)·{\mathrm{Rank}}_j}{C_{\mathrm{out}}\left(j\right)}---\left(8\right)$

式中：p表示源端到目的端的路由路径；Qlength(j)表示节点j在有路由请求时 的缓存队列长度；Rank_j表示节点j的节点权值；C_out(j)表示节点j所在通信链路 的中断速率；

(2)所述的针对Internet业务到网关节点k的路由度量为：

$\mathrm{Metric}(p,k)=\underset{j\in p}{\Sigma }\frac{\mathrm{Qlength}\left(j\right)·{\mathrm{Rank}}_j}{C_{\mathrm{out}}\left(j\right)}+{\mathrm{Ra}}_k·\frac{L_{\mathrm{gw}}}{R_{\mathrm{gw}}}---\left(9\right)$

式中：(p,k)表示源端到网关节点k的路由路径；Qlength(j)、Rank_j、C_out(j)含义 与式(8)相同；Ra_k表示网关节点k的容量占比；L_gw表示固定的数据包大小； R_gw表示与网关节点相连的链路数据速率；式(9)的第二项表示网关节点k的 网关特性值。

(3)所述的保序性是指：

如图4所示，对于链路a和与a并联的链路b，链路度量值分别为W(a)和 W(b)，与链路a和b有一串联链路c或c’，如果满足W(a)≤W(b)且W(a+c) ≤W(b+c)和W(c’+a)≤W(c’+b)，则W(·)是具有保序性的。

步骤5)在有客户端业务或Internet业务请求时，网络依据路由协议中的路由度 量为不同业务选路；如图5所示，针对客户端业务，源端向目的节点发起路由 请求，目的节点将最优路径信息返回至源端；最优路径为源端与目的节点之间 所有路径中链路路由度量之和最小的路径；针对Internet业务，源端向网络中 每个网关分别发送路由请求，每个网关将到该网关的最优路径信息返回至源端， 在源端进行比较，选择到最优网关的最优路径；最优路径为源端与各网关之间 所有路径中链路路由度量之和最小的路径。

如图6所示，以Internet业务为例，节点s需要与外部Internet网络通信， 图中链路上的数字为该链路的路由度量值，网关节点处的数字为该网关的网关 特性值。节点s向三个网关分别发送路由请求，路由协议通过对路径的路由度 量值进行比较，在源节点s和三网关之间分别选择的最优路径为： s→e→u→v→GW1、s→e→u→v→GW2、s→n→f→k→GW3，对应的路径 的路由度量值分别为1.31、1.18、1.8，因此当三个网关分别将各自的最优路径 信息返回源节点s进行比较时，源节点s会选择网关节点GW2，即选择的最优 路径为s→e→u→v→GW2。

最后需要说明的是，以上实施案例仅用以说明而非限制本发明的技术方案， 尽管参照上述实施案例对本发明进行了详细说明，本领域的普通技术人员应当 理解，依然可以对本发明进行修改或者同等替换，而不脱离本发明的精神和范 围。