负载感知无线Mesh网络部分重叠信道分配系统及方法

摘要

本发明涉及一种负载感知无线Mesh网络部分重叠信道分配系统及方法，该系统及方法首先根据网络中各条流的流量及经过路径，确定网络中需要分配信道的链路及其负载，按照链路负载对各链路进行降序排列，确定链路的信道分配次序；然后重复遍历所有需要分配信道的链路，为各链路分配满足无干扰约束的部分重叠信道，并将各链路划分成不同链路集合；最后将数据传输时间划分成若干调度时隙，每个时隙依次调度一个链路集合，实现无干扰数据传输。由于同一链路集合内链路互不干扰，相互干扰的链路分到不同集合中；相互干扰的链路在不同时隙调度，同一时隙内调度的各链路互不干扰，保证了需要传递负载的链路都得到传输数据的机会，实现无干扰数据传输。

说明书

技术领域

本发明涉及无线通信领域，尤其涉及一种负载感知的IEEE802.11b/g无线 Mesh网络联合部分重叠信道分配与调度系统及方法。

背景技术

无线Mesh网络具有高带宽、快速部署、易于安装、维护简单、前期投资 成本低等优势，能够扩展无线网络的覆盖范围，因此有望成为解决“最后一公 里”接入问题的理想解决方案。

由同信道干扰引发的网络容量下降是无线Mesh网络面临的主要挑战。由 于正交信道数的有限性，尤其是基于IEEE802.11b/g的无线Mesh网络只有3 条正交信道，网络很难避免为相邻链路分配相同信道，因此仅利用正交信道难 以解决干扰问题。部分重叠信道的引入为无线Mesh网络干扰减轻甚至消除带 来了新的思路，通过仔细规划部分重叠信道的使用，可以有效降低网络中的干 扰，增加网络中的并行传输数，能显著提升网络容量。从目前国内外的研究情 况来看，无线Mesh网络中部分重叠信道的规划使用问题尚未得到有效解决。 绝大多数部分重叠信道下的信道分配方案为负载感知信道分配方案，即假设网 络中存在业务统计器，因此网络可以预先获知各链路上的负载。信道分配的任 务就是在给定的这些条件下，沿着流的路径计算获得一种信道分配和链路调度 结果，以完成负载的传递。但是现有信道分配方法存在以下不足：现有信道分 配通常是在媒体接入控制MAC（MultimediaAccessControl）层使用CSMA/CA （CarrierSenseMultipleAccess/CollisionAvoidance）接入机制下进行的，各链 路使用竞争机制进行接入，只有满足信道无干扰约束的链路能同时传输，但是 无干扰约束使得网络无法保证为所有有需要的链路分配信道，链路负载不能得 到有效传递，网络容量受影响较大。因此应当考虑使用联合信道分配与链路调 度的方法，为网络中所有需要传递负载的链路分配信道，将链路划分成不同的 链路集合，使用分时调度方式在不同时隙调度不同链路集合，实现无冲突数据 传输。

发明内容

本发明要解决的技术问题是提供一种负载感知无线Mesh网络部分重叠信 道分配系统及方法，以提升网络负载传输能力、提高无线Mesh网络容量，实 现无干扰数据传输。

为了解决上述技术问题，本发明的负载感知无线Mesh网络部分重叠信道 分配系统包括：

链路信道分配次序确定模块：

设网络中所有网络流的集合为T，需要分配信道的链路集合为L；利用式 （1）计算链路l∈L上的负载load_l；

${\mathrm{load}}_l=\underset{t\in T}{\Sigma }{p}_t\times I_{\mathrm{tl}}---\left(1\right)$

其中t表示网络流中任意一条流，t∈T；p_t表示流t的流量；I_tl为二进制变 量，当流t经过链路l时，Itl=1，否则I_tl=0；

根据链路集合L中各链路上的负载进行降序排列，确定链路的信道分配次 序，链路的负载越重则信道分配的次序越靠前；对于负载相同的多个链路，信 道分配次序随机选取；

信道分配模块：

首先，为链路集合L中负载最重的链路之一分配信道1，并将该链路添加 到已分配信道的链路集合L₁中；然后按照链路信道分配次序依次为链路集合L 中其他链路选取信道；在此过程中，对于其中任一链路i，取链路i与L中所有 已经分配信道的链路之间的无干扰可选信道集合的交集；若所述交集为空，则 不为链路i分配信道；否则选择无干扰可选信道集合的交集中信道号最小的信 道分配给链路i，并将链路i添加到已分配信道的链路集合L₁中；信道分配第 一轮遍历结束后未分配信道的链路集合为L¹=L-L₁；

其次，为链路集合L¹中负载最重的链路之一分配信道1，并将该链路添加 到已分配信道的链路集合L₂中；然后按照链路信道分配次序依次为链路集合 L¹中其他链路选取信道；在此过程中，对于其中链路p，取链路p与L¹中所有 已经分配信道的链路之间的无干扰可选信道集合的交集；若所述交集为空，则 不为链路p分配信道；否则选择无干扰可选信道集合的交集中信道号最小的信 道分配给链路p，并将链路p添加到已分配信道的链路集合L₂中，信道分配第 二轮遍历结束后未分配信道的链路集合为L²=L¹-L₂；

重复上述过程，进行信道分配的第三轮、第四轮遍历，依此类推，直到集 合L中的所有链路均被分配信道，最终形成的已分配信道链路集合为L₁, L₂,…,L_n；

在信道分配过程中，对于链路集合L中任一链路i，其与L中已经分配信 道的任一链路j之间的无干扰可选信道集合U如下：

其中c_j为链路j使用的信道号；τ为链路i的无干扰可选信道与c_j的最小信 道号间隔，τ根据式（3）、式（4）确定；

$\left(\begin{array}{cc}\tau \ge 5& d(i,j)=0\\ R^{\prime }\times \mathrm{Itr}\left(\tau \right)<d(i,j)\le R^{\prime }\times \mathrm{Itr}(\tau -1)& d(i,j)\ne 0\end{array}\right)---\left(3\right)$

$\mathrm{Itr}\left(\tau \right)=k\sqrt{\frac{{\int }_{-\infty }^{+\infty }\mathrm{PSD}\left(f\right)\times \mathrm{PSD}(f-5\times \tau )\mathrm{df}}{{\int }_{-\infty }^{+\infty }\mathrm{PSD}{\left(f\right)}^2\mathrm{df}}}---\left(4\right)$

其中d(i,j)为链路i和j之间的欧式距离；R′表示同信道下的干扰范围；Itr(τ) 表示当链路所使用的信道之间的信道号间隔为τ时的干扰范围缩减比；PSD（f） 表示功率谱密度函数；k为双径传播模型（Two-rayGround传播模型）中的路 径损耗因子，取值为2～4；

链路调度模块：将数据传输时间划分成n个调度时隙，按照L₁→L_n的顺序 每个时隙调度一个链路集合，在每个调度时隙内对相应的链路集合中所有链路 的数据流进行传输，最终实现网络中各链路数据的传输。

本发明的负载感知无线Mesh网络部分重叠信道分配方法包括下述步骤：

1）链路信道分配次序确定：

设网络中所有网络流的集合为T，需要分配信道的链路集合为L；利用式 （1）计算链路l∈L上的负载load_l；

${\mathrm{load}}_l=\underset{t\in T}{\Sigma }{p}_t\times I_{\mathrm{tl}}---\left(1\right)$

其中t表示网络流中任意一条流，t∈T；pt表示流t的流量；I_tl为二进制变量， 当流t经过链路l时，I_tl=1，否则I_tl=0；

根据链路集合L中各链路上的负载进行降序排列，确定链路的信道分配次 序，链路的负载越重则信道分配的次序越靠前；对于负载相同的多个链路，信 道分配次序随机选取；

2）信道分配：

首先，为链路集合L中负载最重的链路之一分配信道1，并将该链路添加 到已分配信道的链路集合L₁中；然后按照链路信道分配次序依次为链路集合L 中其他链路选取信道；在此过程中，对于其中任一链路i，取链路i与L中所有 已经分配信道的链路之间的无干扰可选信道集合的交集；若所述交集为空，则 不为链路i分配信道；否则选择无干扰可选信道集合的交集中信道号最小的信 道分配给链路i，并将链路i添加到已分配信道的链路集合L₁中；信道分配第 一轮遍历结束后未分配信道的链路集合为L¹=L-L₁；

其次，为链路集合L¹中负载最重的链路之一分配信道1，并将该链路添加 到已分配信道的链路集合L₂中；然后按照链路信道分配次序依次为链路集合 L¹中其他链路选取信道；在此过程中，对于其中链路p，取链路p与L¹中所有 已经分配信道的链路之间的无干扰可选信道集合的交集；若所述交集为空，则 不为链路p分配信道；否则选择无干扰可选信道集合的交集中信道号最小的信 道分配给链路p，并将链路p添加到已分配信道的链路集合L₂中，信道分配第 二轮遍历结束后未分配信道的链路集合为L²=L¹-L₂；

重复上述过程，进行信道分配的第三轮、第四轮遍历，依此类推，直到集 合L中的所有链路均被分配信道，最终形成的已分配信道链路集合为L₁, L₂,…,L_n；

在信道分配过程中，对于链路集合L中任一链路i，其与L中已经分配信 道的任一链路j之间的无干扰可选信道集合U如下：

其中c_j为链路j使用的信道号；τ为链路i的无干扰可选信道与c_j的最小信 道号间隔，τ根据式（3）、式（4）确定；

${\mathrm{load}}_l=\underset{t\in T}{\Sigma }{p}_t\times I_{\mathrm{tl}}---\left(1\right)$

$\left(\begin{array}{cc}\tau \ge 5& d(i,j)=0\\ R^{\prime }\times \mathrm{Itr}\left(\tau \right)<d(i,j)\le R^{\prime }\times \mathrm{Itr}(\tau -1)& d(i,j)\ne 0\end{array}\right)---\left(3\right)$

其中d(i,j)为链路i和j之间的欧式距离；R′表示同信道下的干扰范围；Itr(τ) 表示当链路所使用的信道之间的信道号间隔为τ时的干扰范围缩减比；PSD（f） 表示功率谱密度函数；k为双径传播模型（Two-rayGround传播模型）中的路 径损耗因子，取值为2～4；

3）链路调度：将数据传输时间划分成n个调度时隙，按照L₁→L_n的顺序 每个时隙调度一个链路集合，在每个调度时隙内对相应的链路集合中所有链路 的数据流进行传输，最终实现网络中各链路数据的传输。

本发明的有益效果：

根据网络中各条流的流量及经过路径，确定网络中需要分配信道的链路及 其负载，按照链路负载对各链路进行降序排列，确定链路的信道分配次序。负 载重的链路优先被分配无干扰信道，优先得到数据传输的机会；重复遍历所有 需要分配信道的链路，为各链路分配满足无干扰约束的部分重叠信道，并将各 链路划分成不同链路集合，优点是：同一链路集合内的链路彼此互不干扰，彼 此相互干扰的链路被分到不同集合中；结合链路调度，将彼此相互干扰的链路 安排在不同时隙调度，同一时隙内调度的各链路彼此互不干扰，保证所有需要 传递负载的链路都得到传输数据的机会，实现无干扰数据传输。

附图说明

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

图1为本发明的负载感知无线Mesh网络部分重叠信道分配系统框图。

图2为本发明的负载感知无线Mesh网络部分重叠信道分配方法的总流程 图。

图3为本发明确定链路负载及信道分配次序的说明图。

图4为本发明信道分配的流程图。

图5为本发明确定链路的无干扰可选信道集合的说明图。

图6为本发明链路调度的流程图。

具体实施方式

如图1所示，本发明的负载感知无线Mesh网络部分重叠信道分配系统包 括：链路信道分配次序确定模块，信道分配模块，链路调度模块；

所述链路信道分配次序确定模块：首先根据网络中各条流的流量及经过路 径，确定网络中需要分配信道的链路及其负载。然后按照链路负载对各链路进 行降序排列，确定链路的信道分配次序，链路的负载越重则信道分配的次序越 靠前，对于负载相同的多个链路，信道分配次序随机选择。

设所有网络流的集合用T表示，每条流t∈T的流量为p_t，流经过的所有链 路即为网络中需要分配信道的链路集合L，则链路l∈L上的负载为：

${\mathrm{load}}_l=\underset{t\in T}{\Sigma }{p}_t\times I_{\mathrm{tl}}---\left(1\right)$

其中：I_tl为二进制变量，当流t经过链路l时，I_tl=1，否则I_tl=0。如图3，网 络中的流为t1～t5，则根据上式可以计算得出：链路AB上的负载为1.8，链路 BC上的负载为1.1，链路BD上的负载为1.0，链路BE上的负载为1.4。则链 路的信道分配次序依次为链路AB，BE，BC和BD。假设链路集合L有两条链 路的负载相同，则这两条链路的信道分配次序可以随机选择。

所述信道分配模块：重复遍历所有需要分配信道的链路，为各链路分配满 足无干扰约束的部分重叠信道，并将各链路划分成不同链路集合。

两条链路i=(u₁,v₁)和j=(u₂,v₂)之间的欧式距离d(i,j)定义为链路i的任一个 端点与链路j的任一个端点距离的最小值：

d(i,j)＝min(d(u₁,u₂),d(u₁,v₂),d(v₁,u₂),d(v₁,v₂))

其中：d(u₁,u₂)表示节点u₁、u₂之间的欧式距离，d(u₁,v₂)、d(v₁,u₂)、d(v₁,v₂) 分别表示对应节点之间的欧式距离。由图5可以看出链路i与j之间的距离d(i,j) 等于d(u₁,u₂)。

设链路i和j之间的欧式距离为d(i,j)，若链路i和j连接到同一个节点，则 链路i和j之间的欧式距离d(i,j)=0，则根据无干扰约束条件，两链路之间的信 道号间隔至少为5（即链路i与j的最小信道号间隔τ应满足τ≥5），否则如果链 路i和j同时传输，无论接收端位于何处都会彼此干扰，即连接到同一节点的 链路要满足正交约束。若链路i和j未连接到同一个节点，即d(i,j)≠0时，根 据无干扰约束条件，要求链路i与j的最小信道号间隔τ满足：

R′×Itr(τ)＜d(i,j)≤R′×Itr(τ-1)

其中R′表示同信道下的干扰范围；Itr(τ)表示当链路所使用的信道之间的信 道号间隔为τ时的干扰范围缩减比,用来量化部分重叠信道之间的干扰关系， Itr(τ)可以使用理论计算方法获得：

$\mathrm{Itr}\left(\tau \right)=k\sqrt{\frac{{\int }_{-\infty }^{+\infty }\mathrm{PSD}\left(f\right)\times \mathrm{PSD}(f-5\times \tau )\mathrm{df}}{{\int }_{-\infty }^{+\infty }\mathrm{PSD}{\left(f\right)}^2\mathrm{df}}}$

其中f表示信道的频率，PSD（f）表示功率谱密度函数；k为Two-rayGround 传播模型中的路径损耗因子，取值为2～4。

当链路j已经被分配信道c_j时，链路i的无干扰可选信道集合U为：

本发明使用干扰范围缩减比Itr（τ）量化部分重叠信道之间的干扰关系， 并使用理论计算方法获取Itr（τ）值，当假设Two-rayGround传播模型中的路 径损耗因子k取值为4，当收发信机使用滚降因子为1的升余弦滚降滤波器时， 对应不同信道号间隔τ的Itr（τ）值如表1所示。

表1使用滚降因子为1的升余弦滚降滤波器且路径损耗因子为4时的Itr （τ）值:

当收发信机使用不同类型滤波器时，网络都可以在进行信道分配之前通过 理论计算方法获取Itr（τ）值。这种获取干扰范围的方法具有很好的移植性， 适用于任何配置的网络。当给定同信道下的干扰范围R’时，信道号间隔为τ时 的部分重叠信道缩减干扰范围为Itr(τ)×R’。假设节点收发信机使用滚降因子为 1的升余弦滚降滤波器并假设同信道下的干扰范围R’为550m，节点u₁、u₂之 间的欧式距离d(u₁,u₂)为400m。当链路j已经被分配信道1时，由于550× 0.6928<400<550×0.8667，即Itr(2)×R’<d（u₁,u₂）<Itr(1)×R’，因此链路i与j 至少信道号间隔为2时才彼此无干扰，i的无干扰可选信道集合为 {3,4,5,6,7,8,9,10,11}。遍历需要分配信道的链路集合中的所有链路，即完成所述 信道分配。分配信道的具体过程如下：

信道分配第一轮遍历：首先，为链路集合L中负载最重的链路AB分配信 道1，并将该链路添加到已分配信道的链路集合L₁中；然后按照链路信道分配 次序为链路BE选取信道；取链路BE与AB之间的无干扰可选信道集合；若该 集合不为空，则选择无干扰可选信道集合中信道号最小的信道分配给链路BE， 并将链路BE添加到已分配信道的链路集合L₁中。其次为BC选取信道；设链 路BC与AB之间的无干扰可选信道集合为U1，链路BC与BE之间的无干扰 可选信道集合为U2；若U1和U2交集为空，则不为链路BC分配信道；再次 为BD选取信道；设链路BD与AB之间的无干扰可选信道集合为U3，链路 BD与BE之间的无干扰可选信道集合为U4，若U3和U4交集为空；则不为链 路BD分配信道；信道分配第一轮遍历结束，未分配信道的链路集合为L¹=L-L₁；

信道分配第二轮遍历：为链路BC分配信道1，并将该链路添加到已分配 信道的链路集合L₂中；然后为链路BD选取信道；若链路BD与BC的无干扰 可选信道集合不为空，则选择无干扰可选信道集合中信道号最小的信道分配给 链路BD，并将链路BD添加到已分配信道的链路集合L₂中，信道分配第二轮 遍历结束；最终形成的已分配信道链路集合为L₁,L₂。

链路调度模块：将数据传输时间划分成2个调度时隙，在第一个调度时隙 内对链路集合L₁内所有链路的数据流进行传输，在第二个调度时隙内对链路集 合L₂内所有链路的数据流进行传输，最终实现网络中各链路数据的传输。

如图2所示，本发明的负载感知无线Mesh网络部分重叠信道分配方法详 细过程如下：

步骤1）：根据网络中各条流的流量及经过的路径，确定网络中需要分配信 道的链路及其负载。

设所有网络流的集合用T表示，每条流t∈T的流量为p_t，流经过的所有 链路即为网络中需要分配信道的链路集合L，则链路l∈L上的负载为：

${\mathrm{load}}_l=\underset{t\in T}{\Sigma }{p}_t\times I_{\mathrm{tl}}---\left(1\right)$

其中：I_tl为二进制变量，当流t经过链路l时，I_tl=1，否则I_tl=0。如图3，网 络中的流为t1～t5，则根据上式可以计算得出：链路AB上的负载为1.8，链路 BC上的负载为1.1，链路BD上的负载为1.0，链路BE上的负载为1.4。则链 路的信道分配次序依次为链路AB，BE，BC和BD。假设链路集合L有两条链 路的负载相同，则这两条链路的信道分配次序可以随机选择。

按照链路负载对各链路进行降序排列，确定链路的信道分配次序，链路的 负载越重则信道分配的次序越靠前,则链路的信道分配次序依次为链路AB， BE，BC和BD。

步骤2）：重复遍历所有需要分配信道的链路，为各链路分配满足无干扰约 束的部分重叠信道，并将各链路划分成不同链路集合。

两条链路i=(u₁,v₁)和j=(u₂,v₂)之间的欧式距离d(i,j)定义为链路i的任一个 端点与链路j的任一个端点距离的最小值：

d(i,j)＝min(d(u₁,u₂),d(u₁,v₂),d(v₁,u₂),d(v₁,v₂))

其中：d(u₁,u₂)表示节点u₁、u₂之间的欧式距离，d(u₁,v₂)、d(v₁,u₂)、d(v₁,v₂) 分别表示对应节点之间的欧式距离。由图5可以看出链路i与j之间的距离d(i,j) 等于d(u₁,u₂)。

设链路i和j之间的欧式距离为d(i,j)，若链路i和j连接到同一个节点，由 于各链路之间的欧式距离d(i,j)=0，则根据无干扰约束条件，两链路之间的信 道号间隔至少为5（即链路i与j的最小信道号间隔τ应满足τ≥5），否则如果链 路i和j同时传输，无论接收端位于何处都会彼此干扰，即连接到同一节点的 链路要满足正交约束。若链路i和j未连接到同一个节点，即d(i,j)≠0时，根 据无干扰约束条件，要求链路i与j的最小信道号间隔τ满足：

R′×Itr(τ)＜d(i,j)≤R′×Itr(τ-1)

其中R′表示同信道下的干扰范围；Itr(τ)表示当链路所使用的信道之间的信 道号间隔为τ时的干扰范围缩减比,用来量化部分重叠信道之间的干扰关系， Itr(τ)可以使用理论计算方法获得：

$\mathrm{Itr}\left(\tau \right)=k\sqrt{\frac{{\int }_{-\infty }^{+\infty }\mathrm{PSD}\left(f\right)\times \mathrm{PSD}(f-5\times \tau )\mathrm{df}}{{\int }_{-\infty }^{+\infty }\mathrm{PSD}{\left(f\right)}^2\mathrm{df}}}$

其中f表示信道的频率，PSD（f）表示功率谱密度函数；k为Two-rayGround 传播模型中的路径损耗因子，取值为2～4。

当链路j已经被分配信道c_j时，链路i的无干扰可选信道集合U为：

本发明使用干扰范围缩减比Itr（τ）量化部分重叠信道之间的干扰关系， 并使用理论计算方法获取Itr（τ）值，当假设Two-rayGround传播模型中的路 径损耗因子k取值为4，当收发信机使用滚降因子为1的升余弦滚降滤波器时， 对应不同信道号间隔τ的Itr（τ）值如表1所示。

表1使用滚降因子为1的升余弦滚降滤波器且路径损耗因子为4时的Itr （τ）值:

当收发信机使用不同类型滤波器时，网络都可以在进行信道分配之前通过 理论计算方法获取Itr（τ）值。这种获取干扰范围的方法具有很好的移植性， 适用于任何配置的网络。当给定同信道下的干扰范围R’时，信道号间隔为τ时 的部分重叠信道缩减干扰范围为Itr(τ)×R’。假设节点收发信机使用滚降因子为 1的升余弦滚降滤波器并假设同信道下的干扰范围R’为550m，节点u₁、u₂之 间的欧式距离d(u1,u2)为400m。当链路j已经被分配信道1时，由于550× 0.6928<400<550×0.8667，即Itr(2)×R’<d（u₁,u₂）<Itr(1)×R’，因此链路i与j 至少信道号间隔为2时才彼此无干扰，i的无干扰可选信道集合U为 {3,4,5,6,7,8,9,10,11}。遍历需要分配信道的链路集合中的所有链路，即完成所述 信道分配。如图4所示，分配信道的具体过程如下：

信道分配第一轮遍历：首先，为链路集合L中负载最重的链路AB分配信 道1，并将该链路添加到已分配信道的链路集合L₁中；然后按照链路信道分配 次序为链路BE选取信道；取链路BE与AB之间的无干扰可选信道集合；若该 集合不为空，则选择无干扰可选信道集合中信道号最小的信道分配给链路BE， 并将链路BE添加到已分配信道的链路集合L₁中。其次为BC选取信道；设链 路BC与AB之间的无干扰可选信道集合为U1，链路BC与BE之间的无干扰 可选信道集合为U2；若U1和U2交集为空，则不为链路BC分配信道；再次 为BD选取信道；设链路BD与AB之间的无干扰可选信道集合为U3，链路 BD与BE之间的无干扰可选信道集合为U4，若U3和U4交集为空；则不为链 路BD分配信道；信道分配第一轮遍历结束，未分配信道的链路集合为L¹=L-L₁；

信道分配第二轮遍历：为链路BC分配信道1，并将该链路添加到已分配 信道的链路集合L₂中；然后为链路BD选取信道；若链路BD与BC的无干扰 可选信道集合不为空，则选择无干扰可选信道集合中信道号最小的信道分配给 链路BD，并将链路BD添加到已分配信道的链路集合L₂中，信道分配第二轮 遍历结束；最终形成的已分配信道链路集合为L₁,L₂。

步骤3）：如图6所示，将数据传输时间划分成2个调度时隙，在第一个调度 时隙内对链路集合L₁内所有链路的数据流进行传输，在第二个调度时隙内对链 路集合L₂内所有链路的数据流进行传输，最终实现网络中各链路数据的传输。