根据节点上信道切换的频率可将信道分配算法分为静态、动态和混合式3种类型。

常见的静态信道分配算法有CLICA^[10]、CTA^[4]、MesTiC^[1]等。静态分配算法一旦分配信道后，在很长一段时间内不再发生改变。这种分配方式虽缺少灵活性，但能保证网络的连通性，考虑到WMN骨干网的拓扑相对稳定，静态分配算法在静态拓扑网络中效果显著。但实际应用中，网络拓扑结构、节点状态、数据流等频繁变化，致使静态分配算法无法直接运用。

动态信道分配算法以D-HYA^[11]为代表，根据网络实时状态的变化而自动进行信道切换，实现网络性能的最佳配置。虽然动态分配反映了网络的实时信息，但频繁切换导致的延迟使得切换期间无法正常传输，降低了网络性能。

混合式信道分配算法以HMCP^[12]和LLLA^[13]为代表。该类算法兼具前两者的优点，用静态分配的信道接口交换控制信息，剩下的接口可动态切换信道，用于进行数据传输。

综合来看，信道分配面临复杂度高和可扩展性差两个主要困难。因此，需要结合网络和应用的特点来设计适用的信道分配算法。

本文采用文献[14]定义的协议模型对网络中的干扰进行建模。定义无线Mesh网络为G(V, E)，其中V和E分别表示节点和链接集合， $|V| = N$ 表示网络中节点的总数，假定每个节点的信号传播范围和干扰范围相同。相关定义如下。

1) 网络拓扑图(NG)。网络拓扑图用一个 $N \times N$ 的二维矩阵来表示，若两个节点在彼此的通信范围之内，在网络拓扑图中对应值为1。给定节点 ${v_i},{v_j} \in [1,N]$ ，信号的传输半径为 ${T_r}$ ，节点之间的距离为 $D({v_i},{v_j})$ ，则网络拓扑图矩阵定义为：

如果 ${\rm{NG}}({v_i},{v_j}) = 1$ ，则表示节点 ${v_i}$ 和 ${v_j}$ 在彼此的通信范围之内。

2) 天线节点配置向量(radio-node configuration vector, RNC)，表示网络中各节点及其上的天线数量，定义 ${\bf{RN}}{{\bf{C}}_r} = \{ i\} $ 为 $r$ 天线配置于节点 ${v_i}$ 上，其中 $r$ 为天线编号，且 $r \in [1,R]$ ； $R$ 表示网络中所有节点上配置的天线数的总量。

3) 多天线网络拓扑图(multi-radio network topology graph, MRNG)，以网络拓扑图NG和节点天线配置向量 ${\bf{RN}}{{\bf{C}}_r}$ 为基础计算得到。对于给定的天线 ${r_k}$ 和 ${r_l}$ ( ${r_k},{r_l} \in [1,R]$ )，若天线 ${r_k}$ 和 ${r_l}$ 分别安装在节点 ${v_i}$ 和 ${v_j}$ 上，即有 ${v_i} \in {\bf{RN}}{{\bf{C}}_{{r_k}}}$ 和 ${v_j} \in {\bf{RN}}{{\bf{C}}_{{r_l}}}$ ，则多天线网络拓扑图定义为：

式中， ${\rm{MRNG}}({r_k},{r_l}) = 1$ 表示天线 ${r_k}$ 和 ${r_l}$ 之间相连。

4) 天线链路关系矩阵(radio-link matrix, RLM)，以多天线拓扑图为依据，先后为链路进行编号，得到天线链路关系矩阵来表示天线和链路的对应关系。配置了天线的网络中链路的总数量为 $E' = \sum\limits_{k = 0}^R {\sum\limits_{l = k + 1}^R {{\rm{MRNG}}({r_k},{r_l})} } $ ，可通过计算MRNG的上三角矩阵中非0的个数而得。RLM是一个大小为 $|R| \times |E'|$ 的矩阵，其定义为：

式中， ${\rm RLM}({r_k},e) = 1$ 表示链路 $e$ 的一个端天线是 ${r_k}$ ；否则， ${r_k}$ 不是链路 $e$ 的端天线。

5) 潜在的链路干扰图(possible link interference graph, PLI)，表示两条链路之间的潜在干扰关系，当且仅当这两条链路在实际通信时分配了相同的信道，潜在干扰才会转化成真实干扰。其定义如下：

式中， ${e_1},{e_2}$ 为链路的序号，且 ${e_1},{e_2} \in [1,E']$ ； $\sum\limits_{r = 1}^R {{\rm{RLM}}(r, {e_1})\, \, \wedge \, \, {\rm{RLM}}(r, {e_2}) = 1} $ 表示链路 ${e_1}$ 与链路 ${e_2}$ 有且仅有一个相同的端天线； ${\bf{PL}}{{\bf{I}}_1}$ 表示链路 ${e_1}$ 与链路 ${e_2}$ 的相邻关系，当 ${\rm{PL}}{{\rm{I}}_1}({e_1}, {e_2}) = 1$ 时表示两条链路相邻，反之则表示不相邻。给定 ${\bf{PL}}{{{\bf{I'}}}_2} = {\bf{PL}}{{\bf{I}}_1} \times {\bf{PL}}{{\bf{I}}_1}$ ，定义：

式中， ${\bf{PL}}{{{\bf{I'}}}_2}$ 是一个过渡矩阵，通过计算 ${\bf{PL}}{{{\bf{I}}}_1}$ 与自身的矩阵乘可得。 ${\bf{PL}}{{{\bf{I}}}_2}$ 通过将 ${\bf{PL}}{{{\bf{I'}}}_2}$ 中的结果进一步量化为0或1， ${\bf{PL}}{{{\bf{I}}}_2}$ 表示链路 ${e_1}$ 与 ${e_2}$ 是不相同的两条链路，这两条链路经过两跳相邻的节点，且链路的两个端天线至少有一个是相邻的。

当两条潜在干扰链路上都分配相同信道时则变为真实存在的干扰。通过将 ${\bf{PL}}{{\bf{I}}_1}$ 与 ${\bf{PL}}{{\bf{I}}_2}$ 做异或运算，从而计算出链路相互之间的潜在干扰矩阵 ${\rm{PLI}}({e_1}, {e_2}) = {\rm{PL}}{{\rm{I}}_1}({e_1}, {e_2}) \oplus {\rm{PL}}{{\rm{I}}_2}({e_1}, {e_2})$ ，表示链路 ${e_1}$ 与链路 ${e_2}$ 之间存在潜在干扰。

6) 链路的信道分配矩阵(link-channel assignment matrix, LCAM)，表示链路及其上信道的分配关系，定义如下：

式中，e表示MRNG中链路的序号，且有 $e \in [1,E']$ ；c为信道的序号，且 $c \in [1,C]$ 。如果 ${\rm{LCAM}}(e, c) = 1$ ，则链路e上分配了信道c。

7) 节点信道分配矩阵(node-channel assignment matrix, NCAM)，表示节点上已经分配的信道信息。通过节点链路矩阵和链路信道分配矩阵中的数据来计算NCAM。NCAM的建立是为了在信道分配后，判断真实的信道干扰情况，定义为：

式中，n为节点序号，且 $n \in [1,N]$ ；r为天线序号，且 $r \in [1,R]$ ；e为链路序号，且 $e \in [1,E']$ ；c为网络中可用信道，且 $c \in [1,C]$ ； ${\rm{NCAM}}(n,c) = 1$ 表示节点n上分配了信道c，可以通过RNC，MLB和LCAM计算得到节点的信道分配矩阵。

8) 真实链路干扰图(real-link interference graph, RLI)，表示链路之间的干扰关系，通过PLM与LCASSIGN计算而得，作为优化模型中计算适应度的主要依据，定义为：

式中， ${e_1},{e_2} \in [1,E']$ ； ${\rm{RLI}}({e_1}, {e_2}) = 1$ 表示链路 ${e_1}$ 与链路 ${e_2}$ 相互干扰，反之则不会干扰。

在MIMO-WMN中，链路上的流量可以通过在时间t内，链路两端的节点经过相关天线发送的数据总流量来进行计算，定义 ${\rm{LS}}{{\rm{R}}_e}$ 为链路e的发送速率。假设链路 ${r_1}$ 两端天线是 ${r_2}$ 和 $e \in E'$ ，当 $e \in E'$ ， ${\rm{RLM}}({r_1}, e) = 1$ 和 ${\mathop{\rm RLM}\nolimits} ({r_2}, e) = 1$ 时，则链路e上的发送速率 ${\rm{LS}}{{\rm{R}}_e} = ({\rm{SPk}}{{\rm{t}}_{r1}}(t) + {\rm{SPk}}{{\rm{t}}_{r2}}(t))/t$ 。

其中， ${\rm{SPk}}{{\rm{t}}_{r1}}(t)$ 表示时间段t内，天线r发送的数据流量。 ${\rm{LS}}{{\rm{R}}_e}$ 表示链路在时间段t内的归一化数据流量，即链路e的发送速率。

基于PSO的信道分配算法中，采用适应度模型作为算法优化目标评价函数。适应度函数以网络中链路的干扰程度和发送速率为基础加权计算而得：

式中， $\sum\limits_{{e_2}}^E {{\rm{RLI}}({e_1}, {e_2})} $ 表示链路 ${e_1}$ 受到的来自其他链路的同信道干扰总和； $\alpha, \beta $ 是[0, 1]区间内取值的调节因子。由此，对任意两条链路 ${e_1}, {e_2} \in \left[ {1, E'} \right]$ ，网络中全部链路的适应度函数定义为：

以最小化适应度函数为目标，优化模型受两个主要约束条件制约，即信道资源和天线资源。

首先，任何一个链路上分配的信道数不允许多于1个，根据PLI的定义，该约束条件可定义为：

式中， ${\rm{lChRs}}{{\rm{t}}_e} = 1$ 表示链路e上的信道分配违背了链路的信道约束，否则表示分配是合理的。

其次，网络中任何一个节点上分配的信道总量不能超过此节点上配置的天线总量。该约束可定义为：

${\rm{fChRs}}{{\rm{t}}_n} = 1$ 时节点n上的信道分配违背了该约束。

根据上述两个约束可以得出信道分配约束条件要同时满足 ${\rm{lCHRs}}{{\rm{t}}_e} = 0$ 和 ${\rm{fChRs}}{{\rm{t}}_n} = 0$ 。

若某条链路 ${e_1}$ 上的信道分配违背了前述定义的约束条件，则需要进行适当的调整，从而避免全局的重新分配。假设链路 ${e_1}$ 上已经分配了信道 ${c_1}$ 、 ${c_2}$ 和 ${c_3}$ ，该链路 ${e_1}$ 在当前信道分配下的性能指标为：

式中， ${\rm{LCA(}}{e_1}, {e_2}, c{\rm{)}} = {\rm{LCAM(}}{e_1}, c{\rm{)LCAM(}}{e_2}, c{\rm{)}}$ ； ${\rm{RLI}}({e_1}, {e_2}){\rm{LCA}}({e_1}, {e_2}, c)$ 表示链路 ${e_1}$ 与链路 ${e_2}$ 都分配了信道c之后的干扰值。此时定义调整策略为：在 $c \in \{ {c_1}, {c_2}, {c_3}\} $ 中，链路 ${e_1}$ 保留 $\min \{ {\rm{lperf}}({e_1}, c)\} $ 指定的信道c，保证一条链路上只分配一个信道。

如果某个节点n上违背了信道分配的约束条件，假设节点n上配置有天线 ${r_1}$ 、 ${r_2}$ 和 ${r_3}$ ，且节点n上分配了信道 ${c_1}$ 、 ${c_2}$ 和 ${c_3}$ ，计算为节点n分配信道c后的性能指标为：

式中， ${\rm{RN}}{{\rm{C}}_r} = n$ ； ${\rm{RLI}}({e_1}, {e_2}){\rm{LCA}}({e_1}, {e_2}, c){\rm{RLM}}(r, {e_1})$ 代表节点n的天线 ${r_1}$ 上建立链路 ${e_1}$ ，且 ${e_1}$ 上分配了信道c时的干扰值。由此， ${\rm{nperf}}(n, r, c)$ 表示节点n的天线r上分配c信道的性能指标。最终调整为在 $c \in \{ {c_1}, {c_2}, {c_3}\} $ 中，为节点n保留 $\min \{ {\rm{nperf}}(n, r, c)\} $ 所指定的信道。

基于PSO的优化算法的关键在于粒子的速度和位置，在粒子群优化算法中粒子的速度和位置满足：

式中，i是迭代种群的变量；t是种群中粒子的迭代变量； ${X_i}(t)$ 表示第i个粒子在第t次迭代中的位置。 ${c_1}$ 、 ${c_2}$ 和 ${c_3}$ 是在[0, 1]区间内服从均匀分布的变量； ${p_i}(t)$ 代表第i个粒子在第t次迭代中的个体最优值； ${p_g}$ 表示粒子的全局最优解； $ \otimes $ 算子作为乘法运算符，表示Sigmoid随机选择操作； $ \oplus $ 表示加法操作； ${c_2}{p_i} \otimes {x_i}(t)$ 表示局部认知的部分； ${c_3}({p_g} \otimes {x_i}(t))$ 表示全局认知的部分。

在信道分配模型中，定义通信链路为单个独立的粒子，通信链路上分配的信道为粒子的位置，信道切换的概率定义为粒子的移动速度，即在节点上对应的链路选择某个信道的概率函数。基于如上的定义，建立的信道分配模型可以表示为：

式中， $X_k^t$ 表示第k个信道分配方案中第个t链路上分配的信道； $P_k^{t -1}$ 表示第k个信道分配方案中链路 $t -1$ 上分配的最优信道； ${G^{t -1}}$ 表示所有的种群中链路 $t -1$ 上分配的最优信道； $c \otimes F({x_1}, {x_2})$ 算子依据Sigmoid函数进行随机选择，如果Sigmoid生成的随机数比 $c$ 小，信道切换到 ${x_1}$ ，否则切换到 ${x_2}$ ； ${\rm{Random}}(1, C)$ 表示在 $C$ 个信道中随机选择一个。

综合上述定义，本文设计的基于PSO的信道分配算法，以最小化适应度函数为目标，同时满足天线和信道分配等约束条件，即：

目标函数：min(fitness)

约束条件： $\sum\limits_{e = 1}^{E'} {{\rm{lChRs}}{{\rm{t}}_e}} = 0$ 和 $\sum\limits_{n = 1}^N {{\rm{fChRs}}{{\rm{t}}_n} = 0} $ 。

通过模型的建立和适应度函数的定义，基于PSO的无线Mesh网络信道分配算法主要包括两个步骤：算法初始化、迭代优化最终解。

算法1：PSOCA//基于粒子群优化的信道分配算法

//采集网络各节点信息，获得各参数初始化值

//模型参数初始化： $\alpha $ , $\beta $ , 种群规模POPSIZE, 最大迭代次数MAX_Iteration等。

$j = 0$ ; //初始化循环迭代变量

WHEN $j < {\rm{MAX\_Iteration}}$ DO

{

    初始化粒子种群initiate()；

    初始化种群迭代变量 $k = 1$ ；

    WHEN $k < {\rm{POPSIZE}}$ DO

    {

         $t = 0$ ; 初始化粒子的位置矢量迭代变量

        IF $t < {\rm{EDGE\_COUNT}}$ THEN

             ${\rm{updateLoc}}(X(i, k))$ ；//更新粒子位置

        ELSE {

            verify and adjust result()；

            //约束条件检查及分配调整

             ${\rm{fitness}}()$ ；//适应度计算

            Localbest()；//局部最优解计算}

    }

    globalbest()；//计算全局最优解

}

仿真实验在NS2模拟器中进行，增加了多输入多输出天线(multiple input multiple output, MIMO)的配置，并修改节点配置函数。假定节点均匀分布，每个节点的通信半径、干扰半径、可用的信道总数和无线射频接口数量均相同。模拟以无线Mesh网络的骨干网为主，即假定网络中的节点具有较小的移动性。实验中随机选择发送数据的源节点及接收数据的目的节点。经过多次实验，计算平均值作为最终的结果。

为比较基于PSO的信道分配算法(PSOCA)的性能，测试中选取单信道单接口(SISO)和基于Ramon的信道分配算法进行比较，分别从网络吞吐量、端到端时延和丢包率3个方面进行测试和分析。

1) 网络吞吐量性能分析

网络吞吐量(network throughput)指单位时间内节点可以接收的数据包总量。随着节点发送速率的变化，三者的吞吐量测试结果如图 1所示。

图  1  网络吞吐量对比

如图 1所示，基于多信道的两种方案(PSOCA及Ramon)比单信道方案获得更好的吞吐量。另外，PSOCA获得最好的网络吞吐量，因为该算法有效地降低了网络干扰，从而提升网络吞吐量。

2) 端到端时延分析

端到端传输时延表示每个数据包从离开发送节点至接收节点之间所经过的平均时间延迟。仿真时，在单网关节点网络中，随机设置1个和3个源节点，平均端到端时延的结果分别如图 2和图 3所示。

图  2  平均端到端时延(单网关-1个源节点)

图  3  平均端到端时延(单网关-3个源节点)

由图 2和图 3可知，在数据量不大的情况下，单天线单信道情况下的平均端到端时延较低。因为此时网络中数据量较小，路由相对固定。相反，多信道多天线的通信方式下的平均端到端时延相对较高，因为信道的切换和重新分配使得数据包的传输受到一定程度的影响。

3) 丢包率分析

丢包率指丢失的数据包在所有发送数据包中所占的百分比。在单网关节点网络中，分别设置1~3个发送源节点，得到的丢包率性能分别如图 4、图 5和图 6所示。

图  4  丢包率对比(单网关-单源节点)

图  5  丢包率对比(单网关-2个源节点)

图  6  丢包率对比(单网关-3个源节点)

如图 4所示，在单天线单信道的场景中丢包率维持在较高的比例，而采用多信道多天线能够降低网络中的丢包率。另外，基于PSO的信道分配算法中丢包率维持在较为平稳的水平，而仅仅采用Ramon的多天线多信道的方式呈现出较好的性能。这是因为，Ramon的配置脚本中假设网络中天线数量大于可用信道的数量，没有信道切换的开销。

如图 5及图 6所示，随着网络中源节点的增加，节点发送数据包的增多，基于PSO的信道分配算法呈现出最好的性能，随着数据量的增大，丢包率趋于稳定状态。初始时的波动是因为信道的动态切换所导致的，但一旦稳定后，由于PSO对网络干扰进行了最佳优化，因此获得了良好的性能。

综合来看，基于PSO的信道分配算法在网络吞吐量和丢包率两个方面均比单信道单天线固定信道算法及同类算法呈现出更好的性能，但因信道的动态切换，导致平均端到端延迟有所增加。

应用范围的扩大和需求的持续增长都对无线Mesh网络提出更高的性能需求。MCMR虽能有效改善网络性能，但信道分配算法的复杂度、最优解计算和可扩展性都有待借鉴新方法加以优化。利用粒子群优化算法具有计算复杂度低、优化性能良好的优点，设计了基于PSO的信道分配算法。仿真实验结果表明，基于PSO的信道分配算法在网络吞吐量和丢包率方面均比同类算法展现出了更好的性能。但该算法受限于信道切换所造成的临时性网络传输中断，在平均端到端延迟方面还有待进一步改善，可行的改善途径应注重静态分配信道和动态分配信道两者的结合和优化，这也是下一步的主要工作。

信道分配问题因其本身的复杂度较高，在有限的时间范围内不能得到合理的全局最优解，只能适用于实时性和精确度要求不高的场景。因此要对信道分配算法进行优化，而优化的算法不局限于群体智能优化算法。未来可以引入更好的优化算法来降低现有算法的复杂度，使其能在有限时间内得到较好的方案。目前的优化算法只考虑了网络中的干扰和链路的发送速率，为了取得更好的全局效应，还可以考虑结合更多的性能指标。