基于节点优先级的无线Mesh网络资源分配

发布日期：2025-01-04 15:55    点击次数：199

在无线Mesh网络中，随着通信距离增大，跳数增多，数据传输速率会明显降低，同时产生网络拥塞和信道干扰等问题，极大地影响网络吞吐量[1]。如何缓解无线Mesh节点负载，疏通整个网络，从而提高整体传输性能已成为至关重要的问题。 由于传统单射频单信道技术(single-radio single-channel，SRSC)信道切换频繁，不仅增加延迟，还需复杂的节点同步与信道切换机制[2, 3]。因此，无线Mesh网络引入了多射频多信道(multi-radio multi-channel，MRMC)技术[4]，使用多个正交信道与不同相邻节点通信，以减轻链路干扰。然而，实际无线Mesh网络节点接口数往往远小于系统可用信道数，故如何分配信道和无线射频接口，是MRMC无线Mesh网络所要面临的挑战。 常见的信道分配算法根据接口切换频率分为静态分配、动态分配和混合式3种。其中静态分配又分为公共信道分配(common channel assignment，CCA)和变化信道分配(varying channel assignment，VCA)。CCA中每个网络节点都分配相同的信道[5]，资源利用率不高。VCA中不同节点射频接口所分配的信道可能不同[6]，故不同的分配方案会得到不同的网络拓扑，其典型代表为分布式信道分配(D-HYA)算法[7]。混合式信道分配由前两者混合组成，其中一部分节点无线射频接口采用静态分配，其余则采用动态分配，代表算法有基于链路层协议(link layer protocol，LLP)[8]和基于干扰感知的广度优先搜索信道分配(breadth first search-channel assignment，BFS-CA)[9]算法。 以上文献多以最小化链路干扰为主，较少考虑链路负载分布的不同。实际网络中不同链路负载不一，对资源的需求亦有所区别。本文提出NPFCA的分配方案从无线Mesh网络整体出发，综合考虑链路间干扰和每条链路负载，对节点按负载不同进行优先级划分，以进一步提升网络容量，并使用离散粒子群优化(DPSO)算法快速求解。 1 系统模型 无线Mesh网络的系统模型主要包括网络模型和链路干扰模型。 1.1 网络模型 无线Mesh网络通常包括网关节点(mesh point collocated with a mesh portal，MPP)、Mesh节点(mesh point，MP)、接入节点(mesh access point，MAP)和用户终端。本文模型中所有节点均使用全向天线。此外，每个节点都可在不同射频和信道间进行切换，且每个射频接口都工作在半双工模式下。 若将无线Mesh网络拓扑表示为一个无向图G={V,E}，其中V为所有节点集合，网络节点总数N=|V|，将所有非重叠信道分别编号为1,2,…,K，则所有可用信道集合表示为CK={1,2,…,K}。设节点u∈V安装有R(u)个无线射频接口，且该节点使用的信道集合为C(u)，则R(u)和C(u)满足： $\left| {C(u)} \right| \le R(u) \le K,{\rm{ }}C(u) \subseteq {C_K}$ (1) 若用E表示网络链路集合，则链路总数L=|E|，对于u,v∈V，若存在euv∈E，则表示两节点间存在直接通信链路euv，即二节点互为相邻节点。节点u的相邻节点数表示为$N{B_u} = \{ i|i \in V,\exists {e_{ui}} \in E\} $，链路euv存在的条件为： ${x_{uv}} = \left\{ {\begin{array}{*{20}{c}} {k\begin{array}{*{20}{c}} {}&{k \in {C_K}且{e_{uv}} \in E} \end{array}}\\ {0\begin{array}{*{20}{c}} {}&{\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} {其他}&{} \end{array}}&{} \end{array}}&{} \end{array}} \end{array}} \end{array}} \right.$ (2) ${f_{uv}} = \left\{ {\begin{array}{*{20}{c}} {1\begin{array}{*{20}{c}} {}&{{x_{uv}} \ne 0} \end{array}}\\ {0\begin{array}{*{20}{c}} {}&{{x_{uv}} = 0} \end{array}} \end{array}} \right.$ (3) 式(2)中xuv表示链路euv上所分配信道的标号，当euv∈E，且分配了信道k∈CK时，有xuv=k；否则xuv=0。式(3)中fuv=k表示链路euv=k的有效情况，当euv=k被分配了信道，即xuv≠0，可得fuv=1；否则fuv=0。可用$F = \{ {f_{uv}}|u,v \in V{x_{uv}} \in X\} $表示无线Mesh网络中所有链路的有效情况。由式(2)可得，节点u所分配信道数为： $C(u) = \mathop {{\rm{card}}}\limits_{\begin{array}{*{20}{c}} {{x_{ui}} \ne {x_{uj}} \ne 0}\\ {i \ne j \in [1,N]} \end{array}} \{ {x_{ui}}|i \in V且{e_{ui}} \in E\} $ (1) 式中，card{}为返回集合中元素个数；条件xui≠xuj≠0，表示返回集合中不相同且不为零元素的个数，是节点u所有射频接口上分配的信道集合。 1.2 干扰模型 无线Mesh网络根据干扰源的定义不同，可分为物理干扰模型和协议干扰模型[10]。由于物理干扰模型较为复杂，故本文采用文献[11]中的协议干扰模型，将节点有效范围分为节点传输范围Rtx、节点载波侦听范围Rcs和节点干扰范围Ri。考虑到当Rcs和Ri不等时，节点可能因侦听和干扰范围不相匹配而无法准确把握网络状态，为便于分析，令Ri=Rcs，而Rcs一般为Rtx的2～2.78倍，本文取Rcs/Rtx=2。模型如图 1所示，当节点u通过信道k向节点v发送数据时，成功接收的充要条件是：1) v、u之间的距离满足d(u,v)≤Rtx；2) 对于其他使用信道k的节点w，均满足d(w,v)≥2d(u,v)。 图1 协议干扰模型示意图 由于节点间的通信是相互的，若要保证网络中任意两条链路ei和ej互不干扰，如图 2所示，条件2)应重写为： $D({e_j},{e_k}) \ge 2$ (2) 图2 基于链路的协议干扰模型 式中，D(ej,ek)表示链路ej和ek间任意两个节点间的最少通信跳数，由此可知网络中任意链路干扰范围为其两跳相邻节点内所有链路。据式(2)可得到无线网络G={V,E}的潜在干扰矩阵GC，对于其元素$\forall {\rm{g}}{{\rm{c}}_{ij}} \in GC$，i,j∈[1,L]，均有： ${\rm{g}}{{\rm{c}}_{ij}} = {\rm{g}}{{\rm{c}}_{ji}} = \left\{ {\begin{array}{*{20}{c}} {1\quad i、j\;\;\;相互干扰{\mkern 1mu} }\\ {0\quad i、j不相互干扰} \end{array}} \right.$ (3) 2 节点优先级划分及链路负载计算 无线Mesh网络中端到端数据流分为MP与MPP间的数据流和MP之间的数据流。对于前者，越靠近MPP负载越重，要提高性能必须尽可能减少链路干扰；而对于后者，往往相邻MP越多，该MP潜在负载越重。在实际网络中数据流以前者居多[12]，因此本文假设绝大部分数据流为第一类，并对节点设置优先级，MPP设为最高级，其余节点按网关的最小跳数分级，越少优先级越高。 以图 3中的无线Mesh网络为例，设节点3为MPP，分级结果如图 3b所示。根据节点优先级及其相邻节点数，得到相应链路eij的负载权重为： ${w_{ij}} = {\rm{N}}{{\rm{B}}_i}/{\rm{P}}{{\rm{L}}_i} + {\rm{N}}{{\rm{B}}_j}/{\rm{P}}{{\rm{L}}_j}$ (4) 图3 随机8节点无线Mesh网络拓扑分级示意图 即wij为链路eij两端节点各自相邻节点数与节点优先级比值之和，wij越大则优先级越高，反之亦然。 3 NPFCA信道资源分配优化模型 根据文献[7]，信道分配须遵守以下准则：1) 网络总可用信道数有限；2) 每个节点占用信道数不超过其射频接口数；3) 任意两节点可直连的必要条件是它们在彼此的Rtx内，且至少有一个共用信道。 根据式，实际干扰可为： $I({e_{ij}}{e_{uv}}) = \left\{ {\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} 1&{GC({e_{ij}},{e_{uv}}) = 1且{x_{ij}}{\rm{ = }}{x_{uv}} \ne 0\,} \end{array}}\\ {\begin{array}{*{20}{c}} 0&{其他\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} {}&{} \end{array}}&{} \end{array}}&{} \end{array}}&{} \end{array}}&{} \end{array}}&{} \end{array}} \end{array}} \end{array}} \right.$ (5) 在计算网络整体干扰度时，本文运用第2节提出的节点优先级策略，将网络节点按潜在负载分级，同时，在对同一节点的多条链路进行分配时，按照其负载权重wij分级，其值越大，优先分配权越高，以保证其干扰范围内的链路尽量不使用与之相同的信道。引入链路负载后的网络整体干扰度为： ${\rm{PL}}\_{\rm{CID}} = \frac{1}{2}\sum\limits_{{e_{ij}},{e_{uv}} \in E,{e_{ij}} \ne {e_{uv}}} {[I({e_{ij}}{e_{uv}})({w_{ij}} + {w_{uv}})]} $ (6) 基于式(6)的静态信道资源分配优化模型为： $\begin{array}{l} {\rm{Min (PL}}\_{\rm{CID)}}\\ {\rm{s}}{\rm{.t}}{\rm{.}}\;\;\;\;\left| {C(u)} \right| \le R(u) \le K,{\rm{ }}C(u) \subseteq {C_K} \end{array}$ (7) 式(7)为一个整数线性规划模型，其输入为网络拓扑、总可用信道数、节点接口数和MPP标号。尽管该问题可用LINGO[13]等商业软件求解，但无线Mesh网络信道分配优化问题已经被证实为一个NP问题[14]，求解时间随网络规模增加呈指数级递增。考虑到实用性，需要一种低复杂度的算法求解。 4 基于PSO的NPFCA分配优化方案 显然式(7)中的优化问题需要迭代求解，而传统迭代优化算法通常是从搜索空间中的一点按一定规则转移到另外一点，效率不高。针对此问题，本文引入粒子群优化(PSO)算法求解。该方法属于群智能优化算法，通过概率转移规则，从不同的初始点对搜索空间进行并行搜索，能快速发现最优解，因此更具实用性。 4.1 基于DPSO算法的信道分配方案 由于PSO算法[15]针对连续优化问题，因此必须将其离散化为DPSO才能应用于式(7)。在DPSO算法[16]中，若一个粒子群规模为M，第$i(i \in M)$个粒子在第d次迭代中的位置为$x_i^d$，速度为$v_i^d$，所经历的最优解为$pB_i^d$，整个种群所经历的最优解为$gB$，则粒子i将会根据式(8)和(9)式更新自己的速度和位置，有： $v_i^{d + 1} = \omega v_i^d + {c_1}{r_1}(pB_i^d - x_i^d) + {c_2}{r_2}(gB - x_i^d)$ (8) $x_i^{d + 1} = x_i^d + v_i^{d + 1}$ (9) 式中，$\omega $为惯性权重，赋予粒子一定的运动惯性；${c_1}$和${c_2}$为常数，称为学习因子，用于保证粒子向个体最优解和全局最优解靠近，且$\omega ,{c_1},{c_2} \in [0,1]$；${r_1}$、${r_2}$为均匀分布于[0, 1]之间的随机数。 将DPSO算法引入提出的NPFCA信道分配方案，则粒子的位置、速度及相关操作定义如下： 1) 粒子的位置：由式(2)中链路${e_{uv}}$上所分配的信道标号${x_{uv}}$组成粒子的位置矢量$X = \{ {x_{uv}}|u,v \in V{e_{uv}} \in E\} $，其中$X$对应一种信道分配方案，有$|X| = L = |E|$。 2) 粒子的速度：对应于信道分配中链路上信道标号的变化，定义为$V = ({v_1},{v_2}, \cdots ,{v_L})$。 3) 位置与位置的减法操作：即DPSO算法中两种信道分配方案的差别，记为$V = {X_2}\Theta {X_1}$，其元素${v_i}$通过逐一比较${X_2}$和${X_1}$中的元素${x_{2,i}}$和${x_{1,i}}$得到： ${v_i} = \left\{ {\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} {{x_{2,i}}}&{{\rm{if}}\begin{array}{*{20}{r}} {} \end{array}{x_{1,i}} \ne {x_{2,i}}} \end{array}}\\ {\begin{array}{*{20}{c}} 0&{\begin{array}{*{20}{r}} {\begin{array}{*{20}{r}} {} \end{array}} \end{array}{\rm{if}}\begin{array}{*{20}{r}} {} \end{array}{x_{1,i}} = {x_{2,i}}} \end{array}} \end{array}} \right.,{\rm{ }}i \in [1,L]$ (10) 4) 速度变化随机性引入：记为${V_2} = c \times {V_1}$，其中$c \in [0,1]$，具体操作为：生成随机数${\rm{rand}} \in [0,1]$，判断其同$c$的大小： ${v_{2,i}} = \left\{ {\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} {{v_{1,i}}}&{{\rm{rand}} \ge c} \end{array}}\\ {0\begin{array}{*{20}{c}} {}&{{\rm{rand}} < c} \end{array}} \end{array}} \right.,i \in [1,L]$ (11) 5) 速度更新操作：记作$V = {V_1} \oplus {V_2}$。具体计算如式所示： ${v_i} = \left\{ {\begin{array}{*{20}{c}} {{v_{1,i}}{v_{1,i}} \ne 0,{v_{2,i}} = 0}\\ {{v_{1,i}}{v_{1,i}} \ne 0,{v_{2,i}} \ne 0,{\rm{rand}} < 0.5,i \in [1,L]}\\ {\begin{array}{*{20}{c}} {{v_{2,i}}}&{其他} \end{array}} \end{array}} \right.$ (12) 6) 粒子位置更新操作：记为${X_2} = {X_1} + V$。按照维数逐一执行操作，如式所示： ${x_{2,i}} = \left\{ {\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} {{x_{1,i}}}&{{v_i} = 0} \end{array}}\\ {{v_i}\begin{array}{*{20}{c}} {}&{{v_i} \ne 0} \end{array}} \end{array}} \right.$ (13) 7) $p{B_i}$和$gB$的计算：根据式得到的网络整体干扰度PL_CID，判断出当前$p{B_i}$和$gB$并记录。 4.2 惯性权重与学习因子的设置 下面通过仿真寻找参数ω、${c_1}$和${c_2}$的最优配对。网络拓扑如图 4所示，相邻节点间距170m，仅纵向和横向相邻节点能直接通信。每个节点有3个无线射频接口，采用IEEE802.11a协议，可用正交信道数为12，粒子群规模为50，最大迭代次数100，通过10次计算取平均值。 图4 网格型拓扑结构图 先令$\omega = 1$，考察不同${c_1}$、${c_2}$取值下的迭代结果和收敛速度。具体结果如表 1～表 3所示。 表1 不同${c_1}$和${c_2}$配对下的网络干扰度 表2 不同${c_1}$和${c_2}$配对下的收敛速度(越小越好) 表3 不同$\omega $取值下网络干扰度和收敛速度 从表 1、表 2可知，当${c_1} = 0.6$，${c_2} = 0.4$时，收敛速度最快，当${c_1} = {c_2} = 0.2$时，网络干扰度最小，此时收敛速度同样较快。故综合考虑干扰度及收敛速度，取${c_1} = {c_2} = 0.2$为最优。表 3为${c_1} = {c_2} = 0.2$时不同$\omega $下的收敛结果及收敛速度。可见$\omega $的取值对优化结果影响并不明显，同时不难看出$\omega = 0.6$时，干扰度和收敛速度均最优。综上，最优设置为$\omega = 0.6$，${c_1} = {c_2} = 0.2$。 5 性能仿真和结果分析 本节主要对提出的基于DPSO的NPFCA信道分配算法进行仿真，并与文献[5]中的CCA和文献[12]中的C-HYA两种典型算法进行比较。仿真分别考察不同可用正交信道数和不同网络负载下NPFCA算法及两种参考算法的平均吞吐量。 5.1 仿真参数设置 网络平均吞吐量为[17]： $C = \sum\limits_N {{{s \times {N_r}} / {{T_p}}}} $ (14) 式中，$C$为网络吞吐量；$s$为数据包大小；${N_r}$为接收数据包数；${T_p}$为接收据包总时长；$N$为数据流数。所有仿真均使用表 4所示的公共参数设置。信道模型采用的对数距离模型${r_x} = {t_x} + {L_0} - 10n\log (d/{d_0})$，其中，${r_x}$为发送功率；${t_x}$为接收功率；$n$为路径损耗距离因子；$d$为节点间距；${d_0}$为系统参考距离；${L_0}$则表示参考距离的路径损耗。 表4 仿真系统的参数设置 所有仿真均使用HWMP先验式路由，且以相同模型和场景中20个随机种子仿真结果的平均值作为结果，基本符合网络数据的统计特性。 5.2 不同正交信道数性能对比 在实际网络中，可用正交信道数并非一成不变，故仿真旨在考察不同正交信道数对吞吐量的影响。设节点12为根节点，得到分级结果如表 5所示。 表5 32节点网格拓扑节点分级 随机选取5个MP同MPP建立速率为500 kb/s的固定码率(constant bit rate，CBR)数据业务，每个节点在仿真时长内随机选取时间发起数据传输，并持续50 s，如果从开始发起到仿真结束不足50 s，则以仿真结束为终止标记。仿真结果如图 5所示。 图5 不同正交信道数网络总吞吐量的比较 从图 5可以看出：随着正交信道数目的增加，本文的NPFCA方案以及C-HYA方案的网络吞吐量呈递增趋势，而CCA方案中由于所有节点均分配相同的3个正交信道，其网络总吞吐量并未发生改变；当信道数增加至9后NPFCA和C-HYA上升趋势变缓。在正交信道数为6时，本文的NPFCA方案吞吐量较CCA提升约32.9%，较C-HYA提升约11.2%，当可用正交信道数为12时，NPFCA方案吞吐量较CCA提升约46.8%，较C-HYA提升约5.5%。 5.3 不同网络负载性能对比 实验一：不同传输速率下的吞吐量比较。随机选取5个MP同MPP建立CBR业务，设置CBR流速率为200 kb/s～2 Mb/s，其余条件同上，全网可用正交信道数为6，结果如图 6所示。 图6 不同CBR传输速率下网络总吞吐量比较 由图 6可知，随着传输速率的增加，3种方案的吞吐量均随之增加，但逐步趋缓；本文的NPFCA方案在三者中性能最好，增长曲线最平滑，且随着传输速率的增加性能优势逐步扩大；当速率达到2Mb/s时，NPFCA吞吐量较CCA高60.6%，较C-HYA高17.0%。 实验2：不同CBR数据流数吞吐量比较。随机选取1～20个MP同MPP建立CBR业务，速率为500 kb/s，其余条件同上，结果如图 7所示。 图7 不同CBR数据流数下网络总吞吐量比较 观察图 7不难看出：随着数据流数增加，3种算法吞量开始均呈递增趋势，但是到后期反而有所下降，主要是因为当数据流增加到一定程度，网络中同时存在的数据流数达到甚至超过最大链路带宽负载，使得数据冲突严重；本文的NPFCA方案在数据流数为18时吞吐量达到最大值，随后才开始下降，较C-HYA方案来得更晚；此时NPFCA的性能较CCA和C-HYA分别有73.3%和10.6%的提升。 6 结束语 本文针对MRMC无线Mesh网络中拥塞和传输干扰问题，综合考虑了网络中链路干扰和链路负载分布，提出了一种基于节点优先级策略的静态信道分配优化方案NPFCA，以最小化网络整体干扰度，从而进一步提升网络吞吐量。该方案从实际应用角度出发，引入离散粒子群优化算法DPSO进行迭代收敛，以快速得到最优信道分配。仿真考虑了不同正交信道数和不同网络负载，结果表明，在不同的网络条件下，本文提出的NPFCA方案在吞吐量方面较传统的CCA和C-HYA方案分别有约32.9%～73.3%和5.5%～17.0%的提升。 本文的研究工作得到了国网四川省电力公司科技项目(52199715000H)的支持，在此表示感谢！