面向拥塞控制的WMN联合功率控制与信道分配

李志军, 王恩东, 刘 丹

(吉林大学 通信工程学院, 长春 130012)

0 引 言

路由选择与信道分配及部分重叠信道的有效利用是保证无线Mesh网络中多播通信质量的重要技术[1-4]。但随着用户数量和服务质量(QoS: Quality of Service)要求的不断增长, 需要设计有效的WMN(Wireless Mesh Network)资源分配方案, 以充分利用有限的网络资源以保证网络业务的服务质量[5]。

文献[6-11]从不同角度研究了通过功率和信道的有效分配改善WMN整体性能。但大多数联合优化方案通常不能准确捕捉网络负载与干扰分布, 同时现有联合资源分配模型大多未考虑网络瓶颈链路和网络拥塞情况对资源分配的影响, 降低了资源分配的合理性及网络整体性能。笔者通过负载模型和干扰模型, 根据干扰链路的负载因素设计干扰权重, 捕捉通信链路的干扰区域内各干扰链路对同一信道的竞争程度, 更加准确地衡量了网络干扰环境和干扰链路负载因素对网络链路资源分配的影响。为有效避免网络拥塞[12], 定义网络拥塞避免系数衡量网络拥塞程度, 构建网络拥塞避免系数最小化的联合资源分配模型, 并在QDJPCA(Q-Learning and Differential evolution based Joint Power control and Channel assignment Algorithm)算法[13]的基础上, 提出一种面向拥塞控制的联合功率控制与信道分配算法(CCJPCA： Congestion Control oriented Joint Power control and Channel assignment Algorithm)。

1 系统模型与问题描述

1.1 网络模型

WMN可通过物理拓扑连接图G(N,E)表示, 其中N={1,2,…,nv}和E={1,2,…,ne}分别代表拓扑连接图中节点与边的集合。网络可配置的信道集合为φ={1,2,…,nc}。每个节点将能配置的最大发射功率Pmax等分为np个功率等级,Γ={1,2,…,np}代表节点能配置的功率等级集合。令F={1,2,…,nf}代表网络的数据流集合, 任意数据流(s,d)的流经路径由能有效避免链路信道分配冲突的拓扑控制算法[14]确定, 同时根据网络数据流的流经路径捕捉每条链路的流量负载。

1.2 负载模型

图1 WMN数据流负载分布示意图Fig.1 Load distribution of WMN

令fsd代表任意数据流(s,d)从源节点s经中间路由器转发到达目的节点d的数据流速率, WMN数据流的负载分布示意图如图1所示。

任意特定数据流(s,d), 任意节点s,d,m,n∈N满足流量守恒定律, 即

1.3 干扰模型

为任意链路(m,n)分配信道c和功率等级p进行传输时, 其接收的干扰功率

根据物理干扰模型[13], 令PN为噪声功率, 链路(m,n)分配信道c和功率等级p时的信干噪比

信干噪比的计算方式增加了干扰权重, 即

其中F为网络数据流集合；Tmn为链路(m,n)的干扰链路集合。

1.4 问题描述

xmn1T=1∀m,n∈N,m≠n

(6)

其中1为1×nc维单位向量。

ym1T≤Im∀m∈N

(7)

其中Im为节点m的网络接口数。

∀m,n∈N,m≠n

(8)

根据网络节点之间的距离选取无线传播模型, 计算每个网络节点到达其邻居节点的最小发射功率等级。如果节点m和节点n之间的距离小于临界距离, 则选取自由空间传播模型, 否则选取双径传播模型。临界距离

dcritical=4πhthr/λ

(9)

其中hr和ht分别为收、 发天线的高度；λ为波长。

自由空间传播模型的最小发射功率等级为

(10)

双径传播模型的最小发射功率等级为

(11)

其中Gr和Gt分别为收发天线增益；Rthresh为接收节点能正常接收信号的接收门限；dmn为节点m和节点n之间的欧氏距离。

因此链路(m,n)分配的发射功率等级p需满足

pmn≤p≤np∀m,n∈N,m≠n,p∈Γ

(12)

为有效避免网络拥塞, 链路(m,n)承载的流量负载需小于其链路容量, 即满足

定义链路(m,n)的拥塞避免系数为

∀m,n∈N,m≠n

(15)

以反映链路的拥塞程度。若ηmn≤1, 说明该链路容量能满足其业务需求。ηmn越小, 说明链路(m,n)的剩余带宽越多, 越有利于接纳其他新的业务请求；ηmn越大, 说明链路(m,n)越拥塞, 越容易成为网络的瓶颈链路。

任意数据流(s,d)流经路径的拥塞避免系数取决于路径中的瓶颈链路, 即数据流(s,d)流经路径中最拥塞的链路, 可表示为

整个网络的拥塞避免系数取决于全网瓶颈链路, 即全网数据流的流经路径中最拥塞的链路, 可表示为

综合考虑链路的流量负载和链路容量, 以θmax为优化目标, 构建如下网络拥塞避免系数最小化的联合资源分配模型

即针对满足式(2)条件的特定网络业务, 为数据流经路径中的链路分配功率等级和传输信道, 实现网络拥塞控制。

2 联合功率控制与信道分配算法

2.1 算法框架

图2 CCJPCA算法的流程图Fig.2 Flow chart of CCJPCA algorithm

为解决式(1)～式(17)所构建的联合资源分配模型, 笔者在QDJPCA算法的基础上, 提出了CCJPCA算法。图2为CCJPCA算法的流程图, 主要通过混合编码策略、Q学习自适应变异策略和概率选择策略保证算法的有效性。通过设计功率与信道混合编码策略, 实现了差分进化过程中链路功率与信道变量的共同优化。Q学习自适应变异策略将Q学习算法和差分进化算法相结合, 在选择变异策略时, 借助Q学习算法的单步回报机制评价不同变异策略的性能表现, 并依据其更新Q值矩阵, 从而选择合适的变异策略实现链路功率与信道资源配置的全局优化。概率选择策略以一定概率保留较差的链路功率与信道分配结果, 相对增加了进化过程中网络资源配置的多样性, 避免陷入局部最优解。

2.2 算法步骤

∀m,n∈N,m≠n

(19)

其中i∈{1,2,…,Np}为个体序号；Np为种群规模；H∈{1,2,…,Hm}为进化代数； |N|为网络节点数。混合编码结构中元素rmn由链路(m,n)分配的信道编号cmn和功率等级pmn组成, 可表示为

rmn=(cmn,pmn) ∀m,n∈N,cmn∈φ,pmn∈Γ

(20)

随机产生信道编号和功率等级为

cmn=rand(1,2,…,nc),pmn=rand(1,2,…,np)

(21)

若cmn=0或pmn=0, 表示链路(m,n)不连通。

3)Q学习自适应变异。为实现个体变异策略的自适应选择, 提出Q学习自适应变异策略。该策略通过Q学习算法的回报机制[15]回传不同变异策略的性能表现, 以自适应地根据回报函数值, 选择具有最大累积折扣回报的变异策略。Q学习自适应变异策略将DE/best/1、 DE/target-to-best/1和DE/best/1/Either-Or变异策略[15]映射为Q学习代理的动作, 即将最优变异策略选择问题转化为Q学习代理的最优动作选择问题。

4) 个体杂交。个体杂交操作采用动态变化的交叉因子。在差分进化算法初期, 交叉因子处于最大值, 个体杂交操作将尽可能的保留变异个体, 以保证算法的全局搜索能力。随着迭代次数的增加, 交叉因子逐渐减小, 逐渐倾向于局部搜索, 需要限制交叉因子的最小值保证种群多样性, 避免陷入局部最优解。个体杂交操作生成的杂交个体为

其中rand[0,1]为在0～1均匀分布的随机数。交叉因子R=0.5+0.5(1-H/Hm), 其在Hm次进化中逐渐减小, 算法将由全局搜索逐渐过渡到局部搜索, 有效保证了变异个体的存活概率与算法的收敛特性。

获取当前种群最优个体的适应度函数值, 判断是否更新全局最优个体Rbest和全局最优适应度函数值fbest。迭代执行3)～5), 直至达到最大迭代次数。CCJPCA算法借助链路功率与信道混合编码策略, 通过获取全局最优个体Rbest, 即可同时获得最优功率与信道分配结果。

2.3 算法时间复杂度

CCJPCA算法的时间复杂度主要由Q学习自适应变异策略的相关操作决定。Q学习自适应变异策略中的Q学习过程, 仅利用子代个体信息与其父代个体信息, 每次学习的复杂度为O(1)。在Hm次种群进化中, 种群中每个个体需根据子代个体与其父代个体的适应度函数值的变化进行自主学习, 同时计算并更新Q值, 以指导下一次变异策略的选择, 故Q学习过程的时间复杂度为O(HmNp)。在合理选择变异策略的条件下, 种群中Np个个体在Hm次迭代中需进行HmNp次个体变异操作, 故个体变异过程的时间复杂度为O(HmNpJ), 其中J为问题解的维数即网络有效链路数。因此, CCJPCA算法的总时间复杂度为O(HmNp+HmNpJ)。

3 性能评价与分析

笔者在NS-3仿真平台上进行算法性能仿真。依次在400 m×400 m和750 m×750 m的区域中随机部署10个和20个网络节点, 每个节点配置3个网络接口, 网络信道数为3, 节点最大发射功率为0.28 W, 功率等级数为5, 数据包接收门限为-64.3 dBm, 负载感知门限为-78 dBm。网络数据流为恒定比特率流, 数据包长度为512 Byte。CCJPCA算法的参数为α=0.1,χ=ε=0.9,Np=20,Hm=100。

3.1 性能仿真及分析

在部署10个节点的WMN中对比CCJPCA算法与遍历算法的最优值近似程度, 并与下列算法对比收敛特性： 1) QDJPCA算法[12]； 2) 状态聚类Q学习[12]与对立差分进化算法(QODE：Q-Learning and Opposition based Differential Evolution)[14]。鉴于遍历算法的计算量随网络规模扩大呈指数递增关系, 为验证CCJPCA算法提升网络性能的程度, 通过NS-3仿真平台在部署20个节点的WMN中与下列算法对比网络性能： 1) QDJPCA算法[12]； 2) 基于功率控制的拓扑控制与信道分配算法e-TICA2[14]； 3) 干扰最小化信道分配与固定功率控制算法(GC-FP： Greedy Channel assignment-Fixed Power control)[7]； 4) 随机信道分配与固定功率控制算法(RC-FP： Random Channel assignment Fixed Power control)。

3.1.1 最优值近似程度与收敛速度

图3 CCJPCA算法的最优值近似程度及收敛性Fig.3 Approximate degree and convergence of CCJPCA number of data streams

仿真验证CCJPCA算法的最优值近似程度与收敛特性, 结果如图3所示。由图3可见, 经过20次迭代后, CCJPCA算法收敛到全局最优值, 验证了算法的有效性。这是因为CCJPCA算法设计了功率与信道混合编码策略, 在迭代过程中可实现二者共同进化, 保证了优化目标的最优值近似程度。在收敛速度方面, 通过Q学习自适应变异策略和动态交叉因子策略, 可有效保证算法收敛速度。

3.1.2 数据流数量对网络性能的影响

固定网络数据流发包速率为400 kByte/s, 将网络数据流数量由1条依次递增至8条。比较分析CCJPCA算法在网络性能方面的改善程度, 仿真结果如图4～图6所示。

图4 不同数据流数下的网络整体吞吐量 图5 不同数据流数下的网络平均丢包率 Fig.4 Average network throughput comparison under different Fig.5 Average packet loss ratio comparison under different number of data streams

图4表明, 随着网络数据流数量的增加, 网络整体吞吐量呈现增长趋势, 增长率由于网络资源的限制呈现下降趋势, CCJPCA算法相比其他算法能获得更高的网络整体吞吐量。当网络中存在6条数据流时, CCJPCA算法的网络整体吞吐量为1 788.12 kByte/s, 相比QDJPCA、 e-TICA2、 GC-FP和RC-FP算法分别提高了16.9%、30.3%、48.6%和61.9%。在网络拥塞避免系数最小化的联合资源分配模型下, CCJPCA算法能准确捕捉网络负载分布和干扰分布, 为承载网络流量的链路更加合理的分配功率与信道, 增加并行传输的数据流数, 获得更高的网络整体吞吐量。

图6 不同数据流数下的网络平均端到端时延Fig.6 Average end-to-end delay comparison under different number of data streams

由图5可见, 在不同数据流数条件下, CCJPCA算法的网络平均丢包率均能获得不同程度的改善。当网络中存在6条数据流时, CCJPCA算法的网络平均丢包率为25.3%, 相比QDJPCA、e-TICA2、GC-FP和RC-FP算法分别降低了14.2%、 32.8%、 40.4%和49.6%。可得出通过设计拥塞避免系数, CCJPCA算法能根据网络负载分布, 优先为高负载链路分配网络资源, 实现网络拥塞控制。

由图6可见, CCJPCA算法的网络平均端到端时延始终低于其他算法。当网络中存在6条数据流时, CCJPCA算法的网络平均端到端时延为2.55 s, 相比QDJPCA、 e-TICA2、 GC-FP和RC-FP算法分别降低了17.7%、 25.2%、 38.3%和46.2%。主要由于CCJPCA算法能基于全网信息实现全局优化, 为每条链路有效分配网络资源, 避免了瓶颈链路带来的网络拥塞问题, 从而减少网络排队和重传时延。

3.1.3 发包速率对网络性能的影响

图7 不同发包速率下的网络整体吞吐量Fig.7 Average network throughput comparison under different packet rates

固定网络数据流数量为6, 将网络数据流发包速率由200 kByte/s依次递增至550 kByte/s。比较分析CCJPCA算法在网络性能方面的改善程度, 仿真结果如图7～图9所示。

图7表明, 随着发包速率的增加, 网络逐渐变得拥塞, 网络整体吞吐量呈现先增后减的趋势。当网络数据流发包速率为450 kByte/s时, CCJPCA算法的网络整体吞吐量为1 970.2 kByte/s, 相比QDJPCA、 e-TICA2、 GC-FP和RC-FP算法分别提高了11.6%、 48.7%、 71.6%和119.4%。这是因为CCJPCA算法通过优化拥塞避免系数, 在链路干扰可控和保护瓶颈链路的基础上, 解决网络拥塞问题, 获得网络吞吐量的提高。

由图8可见, CCJPCA算法的网络平均丢包率始终低于其他算法。当网络数据流发包速率为450 kByte/s时, CCJPCA算法的网络平均丢包率为28.1%, 相比QDJPCA、e-TICA2、GC-FP和RC-FP算法分别降低了13.3%、40.4%、50.7%和56.2%。仿真结果表明, CCJPCA算法能更好地为链路分配功率与信道, 在不同发包速率条件下, 最大限度地利用网络资源, 降低网络平均丢包率。

由图9可见, 当网络数据流发包速率较低时, 网络平均端到端时延的改善程度较明显。当网络数据流发包速率为450 kByte/s时, CCJPCA算法的网络平均端到端时延为3.25 s, 相比QDJPCA、e-TICA2、GC-FP和RC-FP算法分别降低了21.2%、27.9%、32.9%和43.8%。证明了CCJPCA算法在改善网络拥塞方面的有效性。

图8 不同发包速率下的网络平均丢包率 图9 不同发包速率下的网络平均端到端时延 Fig.8 Average packet loss ratio comparison under different packet rates Fig.9 Average end-to-end delay comparison under different packet rates

4 结 语

笔者引入负载模型与干扰模型更加准确地捕捉网络负载与干扰分布, 通过优化网络拥塞避免系数衡量网络拥塞程度, 构建网络拥塞避免系数最小化的联合资源分配模型。针对所构建的联合资源分配模型, 提出CCJPCA算法。该算法通过混合编码策略实现了链路功率与信道变量的共同进化, 借助Q学习算法的回报机制对不同变异策略的性能表现进行评价, 从而实现变异策略的自适应选择。NS-3仿真结果表明, 在所构建的联合资源分配模型下, CCJPCA算法能优先为网络瓶颈链路分配网络资源, 避免网络拥塞, 提升网络整体性能。