由于蜂窝网络和WiFi网络的状态会出现异常改变，导致移动平台资源出现频繁的离线、掉线等情况，需要服务器能够快速处理客户端请求，又要求其在较短的时间内做出有效应答响应.结合以上分析，提出的负载均衡预测算法及调度策略实现流程如下.

1) 利用资源采集程序全面地收集服务器节点的负载，得出每个结点的负载时间序列值.

2) 使用基于回归树与K近邻^[1-3]方法来学习预测模型，提出一种适用于通信集群节点的负载时间序列的平滑处理方法，得出精度更高的负载预测值.

3) 对服务器节点进行区域划分，不同区域采用不同的动态调度策略.

1 动态负载均衡算法的实现 1.1 基于回归树和KNN结合的预测算法实现

采集静态和动态资源信息，周期T为10 s.如表 1和表 2所示.

假设服务器的综合性能指标为S (C_i), C_i表示第i个服务器节点，i∈(1, 2, …, N).

$\begin{align} & S({{C}_{i}})={{k}_{1}}{{S}_{\text{place}}}({{C}_{i}})+{{k}_{2}}{{S}_{\text{isp}}}({{C}_{i}})+ \\ & \quad {{k}_{3}}{{S}_{\text{type}}}({{C}_{i}})+\text{ }{{k}_{4}}{{S}_{\text{cpu}}}({{C}_{i}})+ \\ & {{k}_{5}}{{S}_{\text{memory}}}({{C}_{i}})+\text{ }{{k}_{6}}{{S}_{\text{bandwidth}}}({{C}_{i}})+ \\ & \quad \quad \quad {{k}_{7}}{{S}_{\text{disk}}}({{C}_{i}}) \\ \end{align}$

$\sum\limits_{i=1}^{7}{{}}{{k}_{i}}=1,{{k}_{i}}$表示各个指标的权重系数.

假设服务器节点的动态负载值为L (t_i), t_i表示第i个服务器节点，i∈(1, 2, …, N).

$\begin{align} & L({{C}_{i}})={{t}_{1}}{{L}_{\text{cpu}}}({{C}_{i}})+\text{ }{{t}_{2}}{{L}_{\text{memory}}}({{C}_{i}})+ \\ & \quad \quad {{t}_{3}}{{L}_{\text{in}}}({{C}_{i}})+\text{ }{{k}_{4}}{{L}_{\text{out}}}({{C}_{i}})+ \\ & \quad {{k}_{5}}{{L}_{\text{process}}}({{C}_{i}})+\text{ }{{k}_{6}}{{L}_{\text{tcp}}}({{C}_{i}})+ \\ & \quad \quad \quad \quad {{k}_{7}}{{L}_{\text{port}}}({{C}_{i}}) \\ \end{align}$

$\sum\limits_{i=1}^{7}{{}}{{t}_{i}}=1,{{t}_{i}}$表示各个参数的权重值.

结合服务器综合性能S和动态负载值L这两个重要参数来精确地评估当前服务器节点的负载能力.假设权值为X，X关于服务器性能和动态负载值两个参数的计算方法如下:

$X({{C}_{i}})=\frac{L({{C}_{i}})}{S({{C}_{i}})}$

通过计算得出的负载的时间序列{X (1), X (2), X (3), …, X (N)}负载时间序列预测^[4]是根据时间序列的历史数据{X (t-1), X (t-2), X (t-3), …, X (t-m+1) }预测未来t+τ时刻的值X (t+τ).参数τ是时间延迟.

分析文献[5-6]的平滑算法设计，提出一种部分的分支平滑算法.定义n_i^j为节点上的所属类别i的基数值.定义$通过下面的公式，就可以计算从V₁到V_d的所有可能性.

${{p}_{i}}^{j}=\frac{{{n}_{t}}^{j}+m{{p}_{t}}^{j-1}}{\sum\limits_{i\in c}{{}}{{n}_{i}}^{j}+m}$

其中：p_i^d为最底层叶节点的可能性，m为平滑参数. m设定为K, 2×K, 3×K中的最优值.设定一个阈值θ，即当前节点的权重低于预先设定的阈值θ时，就不再进一步向上平滑.因为随着从叶节点返回根节点的路径上，每次返回父节点时其训练样本数越来越大，相应地对预测样本的目标值的影响权重却越来越小.当权重值小于预设阈值时，就认为当前节点以及通往根节点的路径上的所有节点对最终的预测目标值的影响可以忽略不计.充分地利用从根节点到相应结果类的叶节点的路径上的节点信息，使得预测的结果更准确，并且使得预测在可能的某一个节点上停止，减少时间复杂度，使预测更精准更快速.

1.2 移动平台的负载均衡调度策略

根据得出的服务器节点负载预测结果，将所有的服务器节点按照负载预测值分为3个区域：空闲区、正常负载区、过载区.每个服务器节点被认为具有3种状态：空闲、正常、过载.根据其负载情况，将其分配到对应的区间中.将所有预测得到的服务器节点的负载值进行求和平均.

$\text{Load }\!\!\_\!\!\text{ Degre}{{\text{e}}_{\text{avg}}}=\sum\limits_{i=1}^{n}{{}}\frac{{{P}_{i}}}{n}$

空闲区的服务器节点状态：Load_Degree<Load_Degree_avg×50%.

正常负载区的服务器节点状态：Load_Degree_avg×50%<

Load_Degree<Load_Degree_avg×(1+50%).

过载区的服务器节点状态：

Load_Degree>Load_Degree_avg×(1+50%).

在负载均衡器上会维护一张负载状态表，在固定的每个周期T内更新一次，该表管理了3个区域内的所有服务器节点.每当一个新的请求到达时，会根据这张负载状态表，选定一个区域，使用该区域的调度策略选取一台服务器节点进行分配服务.

1) 空闲区域内的调度策略

当来自移动平台的请求连接到来的频率很快，在短时间内会集中到来时，将在空闲区域内通过一个快速的调度算法，能够保证可以以很快的速度分配新来的连接请求.

提出一个基于优先级队列的轮询调度算法.优先级队列每次从队列中取出的是具有最高优先级的元素.调度过程如下.

① 在轮询调度的前一步，即创建队列时，将空闲区域内的节点按负载值递增排序，将负载值较小的标记为较高的优先级.即负载值最小的节点拥有最高优先级，负载值最大的节点拥有最低优先级.

② 生成一个循环队列并且在分配连接时循环遍历该队列.

③ 每次从优先级队列中，按照优先级情况取出对应的服务器节点来提供服务.节点的负载情况会在每个周期T内更新一次，节点优先级的情况也会实时变化.

2) 正常负载区域内的调度策略

当请求连接到来的频率相对较慢，要保证在正常负载区域内得到一个负载值递增有序的节点序列，并且对于该区域的节点添加和删除要有较小的时间复杂度完成，因此考虑引入基于改进的红黑树排序的调度策略.对红黑树进行改进，使得该特殊的二叉排序树支持值相等的节点存在.由于红黑树的特有性质，可以使得整棵二叉树接近平衡二叉树，使得最终的查找、插入和删除的时间复杂度为O(log n).负载均衡的调度步骤如下.

① 对正常区域内的服务器节点，根据服务器节点的负载预测值进行遍历，将此服务器节点入树，构建一棵改进的红黑树.

② 得到该红黑树后，对红黑树进行中序遍历，形成一个递增的数列，服务器节点的负载预测值将形成一组由小到大的递增数列.

③ 当来自移动平台的请求到来时，选择具有较小负载的且满足条件的服务器进行连接分配.服务器节点分配好请求连接后，它的负载值也会发生变化，下一周期会重新调整得到一个新的红黑树.

④ 在周期T内，出现有服务器的负载超过正常负载的区间，则将该服务器节点从红黑树上删除，将删除的节点移入过载区间.

⑤ 在周期T内，如果过载区域里的服务器节点的负载值下降到正常状态，则将该服务器节点从过载区域中删除，动态得添加新的服务器到正常可用区域内.

2 实验方案与结果分析

针对负载均衡服务器分别采用3种负载均衡算法：加权轮询调度，最小连接数算法，和提出的基于分类回归树(CART, classification and regression tree)和K近邻(KNN，k-nearest neighbor)算法结合的动态负载均衡算法，使用Tsung分别模拟1 000、5 000、10 000用户的注册和登录，向负载均衡调度服务器发起XMPP请求连接.从多个角度来分析得出该算法在连接响应时间、连接建立速率、吞吐量等方面的优越性.在用户连接登录数为1 000、5 000、10 000的情况下，每0.5 s模拟一个用户注册并登录，算法性能的对比，如表 3~表 5所示.

采用了本预测算法的调度策略，预先获得各节点的负载变化，减少了由于负载信息传递时延带来的误差，使得响应的时间能够有效的缩减.从连接响应时间的角度，该算法较原始的算法减少了近25%的响应时间.

从建立连接的平均速率可以看到，本预测算法在登录数为1 000、5 000、10 000的模拟过程中，速率都在不断提升，在短时1万个用户访问到来，在每秒能够建立38个请求连接，相对于原始的最小连接数算法有近1.3倍的速率提升，有更快的处理速度，更强的适应能力.在压力测试时间变化的情况下，对整个通信服务器集群的吞吐量进行了采集获取，并使用gnuplot对吞吐量的变化进行了绘图分析，如图 1~图 3所示.

上面的3幅图中的横坐标表示该压力测试的时间，纵坐标的单位是bit/s，接收量的带圆点曲线是响应的总大小，发送量的带断点曲线是发出请求的总大小.对于请求连接的增加，从1 000~5 000再到1万的连接量，系统表现的吞吐量也随着增加，并且能较长时间维持较大的吞吐量.系统的吞吐量在高水平维持的时间总体较长，平均吞吐量在140 kbits/s，体现了本预测算法和动态调度策略在对于系统的资源利用率上能够充分使用系统集群的空闲能力，将节点的资源能够利用起来，比原始的多种静态和动态算法能够有更大的吞吐量，适应于环境更复杂，连接更频繁的移动平台情况.

3 结束语

经过实验分析，该算法对于负载值的预测更精准，动态调度策略的适应能力更强.对于原始的加权轮询和最小连接数算法，在连接响应时间上减少了25%，在连接建立的平均速率上提升了近1.3倍的处理能力，有着更强的适应性和吞吐能力.