基于频谱系数和比例公平算法的网络调度优化策略

周忠华, 彭智朝

(1. 广东财经大学 网络信息中心, 广州 510320； 2. 天津大学 计算机科学与技术学院, 天津 300050)

在无线网络通信系统中, 无线网络资源管理技术是关键, 其在满足用户相关要求的条件下, 尽可能使资源调度和优化最合理, 以提高无线网络通信系统的资源利用率, 同时保持用户的公平性[1].

无线网络通信系统资源优化调度是一个与时序密切相关的问题, 其目标为每个用户在抢夺资源时, 根据调度优先级顺序建立一个用户服务队列, 包括多方面内容, 如调度代价、 调度目标、 调度规则等. 相对于其他内容, 调度规则更重要, 也称为调度策略, 是无线网络通信系统资源优化调度问题的核心[2-4]. 最初的无线网络通信系统资源优化调度策略基于数据分组理论, 首先构建用户服务质量满意度的相关约束条件, 然后对数据传输时间进行分组, 再根据分组时间先后对数据进行传输, 以获得更优的无线网络通信系统资源利用率. 由于该策略只考虑数据分组, 未考虑用户之间的差异性, 因此无线网络通信系统资源利用率较低, 无法满足目前无线网络通信系统的实际应用要求[5-6]. 之后, 人们提出了一种基于用户分组的无线网络通信系统资源优化调度策略, 相对于基于数据分组的调度策略, 其无线网络通信系统资源优化调度综合性能更优, 因此已成为当前的主要研究方向[7]. 在无线网络通信系统资源优化调度过程中, 吞吐量和公平性是评价调度结果的关键指标, 其中无线网络通信系统的吞吐量描述资源利用效率, 表示单位时间内的数据传输量, 而公平性主要从用户角度出发, 即用户对服务质量的满意度, 描述资源利用的公平性, 公平性越高表示用户获得的资源越均衡. 因此, 一个性能优异的无线网络通信系统资源优化调度策略必须考虑吞吐量和公平性. 目前的无线网络通信系统资源优化调度策略主要分为3类: 第一类为轮询调度策略, 假设无线网络通信系统服务范围内的调度优先级相等, 每个用户被调度的概率相同, 使用户获得服务的机会均等, 该策略可获得理论上最优的公平性, 但由于其未考虑用户的信道质量差异性, 信道质量差的用户获得较多的资源, 会对无线网络通信系统的吞吐量产生不利影响, 因此无法有效兼顾公平性和吞吐量的平衡; 第二类为基于最大载干比的调度策略, 基本工作原理与轮询调度策略相反, 其设置了一个调度器, 在每个周期内, 尽可能选择信道质量最好的用户实现调度, 使信道质量越好的用户获得资源的概率越高, 使无线网络通信系统的吞吐量达到最大, 但信道质量差的用户获得资源的概率很小, 公平性较差, 缺陷明显； 第三类为比例公平调度策略, 其工作原理与前两类策略不同, 首先为每个用户设置一个优先级, 而用户优先级包含瞬时传输速率和历史平均传输速率, 以体现用户信道质量, 提高信道质量差用户获得资源的概率, 克服了轮询调度策略只追求公平性和最大载干比调度策略只追求吞吐量的缺陷, 较好地兼顾了吞吐量和公平性, 已成为无线网络通信系统中最常用的资源优化调度策略. 但在实际应用中, 比例公平调度策略也存在不足, 如考虑用户的业务量对资源分配的影响, 以及资源损失严重等[8-11].

为了解决当前无线网络通信系统资源优化调度过程中存在的问题, 本文设计一种基于频谱系数和比例公平算法的无线网络通信系统资源调度优化策略. 首先建立无线网络通信系统的信道模型, 通过自适应遗传算法确定最合理的频谱系数; 然后根据比例公平算法将无线网络通信系统的资源分配给用户, 并针对传统比例公平算法的不足进行改进; 最后在MATLAB 2016平台上对无线网络通信系统的性能进行分析.

1 无线网络通信系统的信道模型

无线网络通信系统通过信道进行信号传输, 因此信号传输质量与信道质量密切相关, 由于其他因素的干扰, 信号在信道传输过程中, 会产生一些衰变, 即发生路径损耗. 若考虑路径损耗因素, 则第u个用户的无线网络通信系统信道模型为

L(db,u)=K+10αlgdb,u,

(1)

其中:b为无线网络通信系统的中心;db,u为信号衰变程度. 用户u的无线网络通信范围内在第t时刻瞬时信号的信噪比计算公式为

(2)

其中:Ho,u,n(t)为子带频率响应;Pc为功率分配;Iu,n(t)和N0分别为噪声和相应的功率频谱密度; Δf为子载波带宽;Iu,n(t)和Δf分别为

(3)

Δf=Bb/Nsc.

(4)

平均功率分配为

(5)

其中FC和FE分别为无线网络通信系统的中心和边缘区域[11].

无线网络通信系统有多个通信中心, 每个中心有Nsc个子载波, 无线网络通信系统在第n个基通信中心数据的传输速率为

r(γu,n(t))=Nscρ(γu,n(t)).

(6)

由于受外界环境因素的干扰, 无线网络通信系统的数据传输可能会产生一定错误, 因此真实的数据传输速率为

(7)

其中θ(γu,n(t))的确定方式为

(8)

2 传统比例公平调度策略

在比例公平调度策略中, 每个用户都有一个调度优先级, 在第t个时隙, 调度优先级计算公式为

(9)

其中:ri(t)为第i个用户的瞬时传输速率;Ri(t)为第t个时隙的平均传输速率. 当t=1时,Ri(t)=1,pi(t)越大, 则用户分配到的资源越多; 随着无线网络通信系统工作时间的不断增加,Ri(t)不断增大,pi(t)随之变小, 则一些用户就无法分配到资源. 在每个时隙完成时, 用户均会对Ri(t)进行更新处理：

(10)

其中tc表示参考时隙数. 比例公平调度策略的工作流程如图1所示.

图1 比例公平调度策略的工作流程Fig.1 Workflow of proportional fairness scheduling strategy

3 无线网络通信系统资源调度优化策略设计

3.1 确定最优频谱系数

在无线网络通信系统的资源调度优化策略中, 由于要考虑吞吐量, 而吞吐量与网络频谱系数密切相关, 因此要选择最优频谱系数的信道使用户接入通信系统. 设Sa表示无线网络通信系统的平均时延,Su和Sd分别表示上行链路和下行链路的时延, 则最优频谱系数就是尽可能选时延最小的信道, 计算公式为

式中相关参数见文献[2]. 由式(11)可见, 其为一个典型的NP难问题, 常规算法无法求解其最优解, 因此本文采用自适应遗传算法, 先对式(11)的最优解进行搜索, 再根据最优解确定最优频谱系数.

遗传算法对式(11)求解的基本思想为： 首先初始化种群, 每个个体代表式(11)问题的一个可行解, 并对每个个体的优劣进行评价, 根据评价结果排序, 选择较好的个体直接进入下一代种群, 然后将未直接进入下一代种群的个体进行自适应的交叉、 变异操作, 产生新种群, 同样对新种群个体的优劣进行评价, 不断重复上述步骤, 直至达到最大进化代数时, 输出最优个体, 最后根据最优个体的解码结果得到式(11)的最优解.

在算法初期, 自适应遗传算法的交叉概率Pc和变异概率Pm分别为

(12)

(13)

其中:fmax和favg分别表示最大和平均适应度值；Pc0和Pm0分别表示Pc和Pm的初值;k为进化代数, 应满足

(14)

在算法后期, 自适应遗传算法的交叉概率Pc和变异概率Pm分别为

(15)

(16)

3.2 改进的比例公平调度策略

传统比例公平调度策略基于数据传输的瞬时速率和信道质量使用户尽可能多地获得资源, 增加用户增益, 是一种长期公平； 对于一个用户, 尤其对一些有访问时延上限的用户, 无法保证其短期公平, 即在其允许访问时延范围内, 得到有效资源分配, 无法获得高质量服务, 因此本文提出一种改进的比例公平调度策略. 在无线网络通信系统的资源调度优化时, 考虑用户所允许的访问时延, 则调度判决计算公式为

(17)

其中：Ti(t)为第t个时隙的吞吐量；λc为最大访问时延;λi(t)为到t时隙已产生的访问时延. 已产生访问时延的更新公式为

(18)

由式(18)可知, 当λi(t)=0时, 第i个用户获得资源调度机会. 一个用户所允许的访问时延值越大, 则其K*越大, 获得资源调度概率越大. 由式(17)可见, 改进的比例公平调度策略可有效保证短期服务时间, 具有较好的短期公平性, 较好地解决了传统比例公平调度策略中存在的短期服务时间公平与传输速度之间的矛盾.

4 实验分析

4.1 实验参数

为了分析本文提出的无线网络通信系统资源调度优化策略的有效性和优越性, 选择传统公平比例策略和文献[1]的资源调度优化策略进行对比实验, 利用MATLAB 2016工具箱实现仿真测试, 主要分析短期公平性、 长期公平性、 吞吐量和吞吐率等性能, 无线网络通信系统的参数设置列于表1.

表1 无线网络通信系统的主要仿真参数Table 1 Main simulation parameters of wireless network communication system

4.2 短期服务时间保证分析

短期服务时间保证性能通常采用访问时延概率进行评价, 访问时延概率越小, 表示短期服务时间越有保证, 即短期公平性越好, 计算公式为

(19)

3种无线网络通信系统资源调度优化策略的访问时延概率变化曲线如图2所示. 由图2可见, 随着访问时延的不断增加, 所有策略的访问时延概率均逐渐减小, 即短期公平性越来越好, 在相同访问时延条件下, 本文无线网络通信系统资源调度优化策略的访问时延概率明显小于对比策略, 表明本文策略降低了用户等待资源分配的时间, 可更好地保证用户的短期服务时间.

4.3 长期公平性分析

图3 不同策略下服务时间率的对比Fig.3 Comparison of service time rates of different strategies

当无线网络通信系统的数量为10时, 3种无线网络通信系统资源调度优化策略服务时间率(用户服务时间与总服务时间之比)的对比如图3所示. 由图3可见, 对比策略的服务时间率变化范围较大, 说明用户获得的服务时间不公平, 信道质量好的用户占用了更多的服务时间, 而本文策略的服务时间率变化范围较小, 很平均, 这主要是由于本文策略考虑了用户所允许的访问时延, 克服了对比策略存在的缺陷, 改善了用户服务时间的长期公平性.

4.4 吞吐量增益分析

吞吐量增益值为信道传输速率与服务时间率的乘积, 不同策略下吞吐量增益的对比结果如图4所示. 由图4可见, 本文无线网络通信系统资源调度优化策略的吞吐量增益值大于1, 而对比策略的吞吐量增益值均小于1, 这主要是由于对比策略无法为访问时延受限的用户提供短期公平性, 而本文策略通过自适应遗传算法确定最优频谱系数, 根据最优频谱系数用户接入的信道, 可实现良好的信道传输速率, 用户服务短期公平性更优, 服务时间率更大, 能获得更优的吞吐量增益, 从而验证了本文策略的优越性.

4.5 无线网络通信系统的平均吞吐率分析

不同策略下无线网络通信系统的平均吞吐率变化曲线如图5所示. 由图5可见, 本文策略的无线网络通信系统平均吞吐率明显高于对比策略, 表明本文策略较好地解决了当前无线网络通信系统资源调度过程中存在的吞吐问题, 获得了较好的无线网络通信系统资源调度优化结果.

图4 不同策略下吞吐量增益的对比Fig.4 Comparison of throughput gains of different strategies

图5 不同策略下平均吞吐率的对比Fig.5 Comparison of average throughput of different strategies

综上所述, 本文针对当前无线网络通信系统资源调度和优化过程中存在的不足, 首先采用自适应遗传算法对频谱系数优化的数学模型进行求解, 找到最优频谱系数的信道, 使用户尽可能获取高质量的信道; 然后考虑访问时延受限的用户, 采用改进公平比例策略实现无线网络通信系统的资源调度和优化; 最后通过对比实验分析了无线网络通信系统资源调度策略的综合性能. 实验结果表明, 本文策略可较好地保证用户服务的短期和长期公平性, 提高了用户的吞吐量增益, 使无线网络通信系统的平均吞吐率得到显著改善, 具有广阔的应用前景.