一种基于未来负载预测的自适应负载均衡方法

摘要

本发明提供了一种基于未来负载预测的自适应负载均衡方法，该方法利用马尔科夫链来预测下一时刻网络的负载，由此自适应调整触发负载均衡方法的门限以及进行接入控制的方法模型；该方法通过网络之前的负载状况由经过本发明定义的转移概率，计算出未来时刻处于轻载或重载的概率，由算出的概率根据本发明定义的负载效益函数，计算出该网络未来的负载效益值。当网络中有用户请求切换接入或新发起接入请求时，优先选择负载效益值小的网络作为目标网络接入，从而使得整个异构网络的负载均衡，有效地减少了切换的掉话率和接入阻塞率。同时，如预测到未来负载轻载概率大，就动态提高触发负载均衡方法门限，避免网络执行不必要的负载均衡。

说明书

技术领域

本发明涉及异构网络无线资源分配技术领域，特别涉及一种无线异构网中 基于未来负载预测的自适应负载均衡方法。

背景技术

未来通信系统的发展方向是异构网络的融合，为了更好地实现异构网络的 融合，需要研究适用于异构网络环境的无线资源管理技术，从而达到统筹优化 利用各接入网的无线资源、提高异构系统无线资源利用率的目的。负载均衡技 术作为无线资源管理的重要方面，能够有效避免系统负载分布不均、扩大系统 容量，是当前研究的重点。

目前，当很多移动用户（MN）同时要连接同一个基站或WLAN热点时，会发 生严重的接入拥塞，增加接入时延。现有的负载均衡方法，当重叠覆盖小区中 的负载超过所定义的负载平衡门限时，就有可能触发负载均衡策略的执行。门 限值设置得合适与否对于负载均衡方法的性能有很大影响。如果门限值设置得 太高，那么可能导致在系统已经出现拥塞的情况下仍然没有触发负载均衡操作； 如果门限值设置得太低，可能导致不必要的均衡，增加系统开销。触发负载均 衡操作的门限值可以分为两类，一类为固定门限值，另一类为可动态调整门限 值。固定门限值就是为系统各个小区预先设置门限值，设置完成后，只能通过 人工重新配置而更改。各个小区预先设置门限值可以相同值，也可以根据个小 区最大可用资源数目来为不同小区设置不同的门限值。可动态调整门限值也就 是门限值不是固定的，而是可以随着系统各小区负载的变换而动态变换。

但是，若任一小区过载立即触发负载均衡方法的执行，可能会出现这样一 种情况：小区临时过载后很快又恢复为平衡甚至轻载状态，此时执行负载均衡 方法就是多余的。

普遍解决方法：为了防止负载均衡方法频繁执行，设置一个迟滞定时器， 当小区呈现过载状态时，启动该定时器，到时候如果系统小区依然处于负载不 均的状态，再执行负载均衡方法。

该方法的不足：只有在网络过载达到先前设定的门限之后才能执行负载均 衡方法，没有预先预测防范的功能，且在这段时间之内，若有很多用户请求垂 直切换接入，此时过载的网络是接受还是拒绝接入请求，若接受则会降低网络 提供的性能，影响其他用户的Qos，拒绝则会造成呼叫阻塞率或掉话率的增大。 门限的设定也没有根据网络未来负载的实际情况进行动态的调整。而本发明能 够很好地解决上面的问题。

发明内容

本发明目的在于提供了一种基于未来负载预测的自适应负载均衡方法，该 方法由基站或者无线局域网接入点的前一时刻负载状态，通过马尔科夫转移函 数预测出下一时刻负载的状况，动态调整触发负载均衡方法门限，提出了有效 的接入控制自适应负载均衡方法。

本发明解决其技术问题所采用的技术方案是：一种基于未来负载预测的自 适应负载均衡方法，该方法由本发明提出的概率转移函数，通过马尔科夫链预 测出接入点下一时刻负载处于各种状态的概率，由预测出的概率通过本发明提 出的负载效益值函数计算出接入点下一时刻的负载效益值，以及门限该如何调 整。在重叠区域中，当MN需要进行切换或发起新的呼叫请求时，接入控制策略 会选择负载效益值最小的那个网络作为目标小区。

方法流程：

步骤1：对负载进行统一定义；

（1）对不同的无线异构网络接入技术进行分析，对于跨系统的负载均衡方 案，必须要有一个具有相同意义的负载参量；

（2）一个基站的总资源表示为一秒内在基站能够传送的数据符号的总数； 本发明负载定义为单位时间内，节点正在传输的符号数；

步骤2：编写计算某个网络当前负载的方法；

（1）将业务分为3类：语音业务、数据业务、流媒体业务；不同的业务其 数据速率不同；

（2）对于某个网络的负载Load＝load1+load2+load3，其中，load1为所有 语音业务的负载，load2为所有数据业务的负载，load3为所有流媒体业务的负载；

（3）根据实际负载状况，网络将处于轻载、平衡、过载和重载这四个状态 空间之一；

步骤3：转移概率函数的定义；

（1）网络负载下一时刻处于哪个状态的概率只与前一时刻状态有关，所以 负载处于某个状态的概率，这个随机过程满足连续时间马尔科夫链；通过网络 在单位时间内，负载的变化，即：增加的负载减去减少的负载，来确定转移概 率,而负载的变化又由该网络在单位时间内不同业务用户数的变化来计算；

（2）确定呼叫的到达和离去所服从的分布模型，划分各种状态的限制门限， 然后计算状态转移概率。

步骤4：计算每个网络当前的负载效益值；

为了更好地利用马尔科夫计算的负载处于各种状态的概率，使得网络对负 载情况有预知功能以方便用户选择负载合适的网络作为切换网络，本发明定义 了负载效益值，每个网络根据上一时刻负载效益值，以及此时网络负载处于轻 载、平衡、过载、重载的概率，计算出该时刻此网络的负载效益值，从而预测 节点负载状态；节点的负载效益值如下式所示：

$E_{t_{i+1}}\left(N_j\right)=P_{i+\mathrm{1,4}}\times P_{i+\mathrm{1,3}}\times \frac{E_{t_i}\left(N_j\right)}{P_{i+\mathrm{1,1}}\times P_{i+\mathrm{1,2}}}$

步骤5：自适应接入控制策略；

（1）每个网络节点每隔一个时间周期检查自己节点上的负载，若该节点上 的负载超过触发门限Thd0，则触发上述自适应负载均衡方法；对该节点下一时 刻的负载状态进行概率预测；

（2）当有新的呼叫或者有切换请求时，若有两个或两个以上的网络满足基 本的RSS接入条件，则接入控制会选择负载效益值最小的网络作为目标小区， 即

$\mathrm{Opt}-F:\mathrm{MinF}={\mathrm{Min}}_{\forall j\in x}{E}_{t_{i+1}}\left(N_j\right)$

（3）当某些节点长时间处于轻载或平衡状态时，可以不用一直进行着负载 均衡的方法，这样会浪费系统的计算资源，所以本发明设计了自适应触发门限 的计算方法。

有益效果：

1、从有效性，本发明合理预测未来负载，利用预测的结果进行接入控制来 平衡网络间的负载，达到了负载均衡的效果。

2、本发明应用于无线异构网中，通过预测未来负载，可以自适应提高或降 低触发负载均衡方法的门限，从而根据网络状态合理执行负载均衡方法，减少 系统资源的开销。

附图说明

图1为本发明状态定义示意图。

图2为本发明状态转移示意图。

图3为本发明的方法流程图。

具体实施方式

以下结合说明书附图对本发明创造作进一步的详细说明。

如图1、图2和图3所示，本发明提供了一种基于未来负载预测的自适应负 载均衡方法，该方法包括如下步骤：

步骤1、负载的定义

为了对负载进行统一的定义，屏蔽不同无线接入技术的资源不一致性，将负 载定义如下：

$\mathrm{load}\left(i\right)=\underset{i}{\Sigma }\frac{R_b\left(i\right)}{R_c\left(i\right)}{R}_m\left(i\right)\mathrm{SF}\left(i\right)$     —式（1）

其中，R_b(i)为每个用户要求有质量保证的比特速率，这里可以用来区分用户 不同的业务，如：话音业务为16kbps，多媒体业务为384kbps；R_m(i)为调制速率； R_c(i)为编码速率；SF(i)为扩频因子。

步骤2、编写计算某个网络当前负载的方法

对于某个网络的负载定义为：

Load＝load1+load2+load3       —式（2）

其中，load1为所有语音业务的负载，load2为所有数据业务的负载，load3 为所有流媒体业务的负载。计算出某个网络当前负载，由图1的状态定义图， 根据网络负载情况划分为轻载、平衡、过载和重载四种情况之一。

其中，$\left(\begin{array}{c}\underset{‾}{\mathrm{Thd}1=0.3*C_{\max }}\\ \underset{‾}{\mathrm{Thd}2=0.6*C_{\max }}\\ \underset{‾}{\mathrm{Thd}3=0.8*C_{\max }}\\ \mathrm{Thd}4=1*C_{\max }\end{array}\right)$    —式（3）

步骤3、转移概率函数的定义

由于网络负载处于某个状态的状态空间为：轻载、平衡、过载和重载。而 下一时刻处于哪个状态的概率只与前一时刻状态有关，所以负载处于某个状态 的概率这个随机过程满足连续时间马尔科夫链。如何能正确地由前一时刻推算 出下一时刻负载处于某个状态的概率，就需要定义正确合理的转移概率函数。 这里通过网络在单位时间内，负载的变化来确定转移概率,而负载的变化又可以 由该网络在单位时间内不同业务用户数的变化来计算。由概率论我们知道通信 系统中，不同用户业务到达与离去的概率都是服从确定的分布模型，因此，状 态转移概率就可根据分布模型计算，从而确定了处于各个状态的概率。

下面，首先确定呼叫的到达和离去所服从的分布模型，然后计算状态转移 概率。

对于通信系统，假设有n个终端，在每个单位时刻，各终端只有发起呼叫 和不发起呼叫两种可能，因此对着n个终端判断是否发起呼叫就是一个n重伯 努利试验。各个终端发起呼叫的概率为P，不发起呼叫的概率为1-P（无论呼叫 是什么业务类型，上述假设都成立，只是概率P大小不同），因此，无论发起的 是话音呼叫、数据业务还是流业务，k个呼叫发起的概率都可以由式（4）计算。

$P(X=k)=\left(\begin{array}{c}n\\ k\end{array}\right)p^k{(1-p)}^{n-k},k=\mathrm{0,1,2},...,n$    —式（4）

同样，若网络中已有呼叫数为n，在各个决策时刻，每个呼叫也只有离去和 不离去两种可能，因此对于这n个呼叫判断是否离去也是一个n重伯努利试验。 若每个呼叫离去的概率为p，不离去的概率为1-p，则无论离去的是何种业务， k个呼叫离去的概率也是都可以用上式计算。

根据泊松定理可知，若n很大，p很小时有一下近似式：

$\left(\begin{array}{c}n\\ k\end{array}\right)p^k{(1-p)}^{n-k}\approx \frac{{\lambda }^k{e}^{-\lambda }}{k!}(\lambda =\mathrm{np})$      —式（5）

其中，就是泊松分布的概率密度函数，即当随机变量X服从泊松分布 时，其概率密度为

$P(X=k)=\frac{{\lambda }^k{e}^{-\lambda }}{k!},k=\mathrm{0,1,2},...$     —式（6）

泊松分布过程同时也是平稳增量过程，由式（7）可计算出某类业务增加K 个呼叫或者减少K个呼叫的概率：

$P\{X(t+s)-X\left(s\right)=k\}=e^{-\mathrm{\lambda t}}\frac{{\left(\mathrm{\lambda t}\right)}^k}{k!},k=\mathrm{0,1,2}...$   —式（7）

其中，k为某个网络的某一种业务在t时间段里用户数的变化，由用户数的 变化可以计算出该种业务负载的变化。

本发明可以证明，到达和离去都是服从泊松分布的，根据泊松分布的特性， 该系统每次只能处理一个呼叫的请求，也就是说只能有一个呼叫进入系统或者 离开系统或者发生切换。呼叫的到达率和离去率分别为：λ_i(i＝1,2,3,...)和 μ_i(i＝1,2,3,...)，其中，i=1,2,3,…分别表示语音业务、数据业务、流媒体业务等。

根据图1将网络分为：1、轻载；2、平衡；3、过载；4、重载四种状态。 设第i个时刻，网络处于以上4种状态的概率分别为则在第i+1 时刻，网络处于各个状态的概率为其中P_i,i+1为一步转移概率矩阵。

结合图1和图2，设i时刻网络的负载为load（i），在i+1时刻，到达的 新呼叫个数为a，离开网络的呼叫个数为b，新呼叫所需要的负载为load（a）， 离开的呼叫所减少的负载为load（b），若在i时刻网络处于状态1，即处于轻 载状态，则下一时刻网络处于状态1、2、3、4的转移概率为：

P(i+1＝1/i＝1)＝P(-load(i)＜＝load(a)-load(b)＜＝thd1-load(i)/i＝1)

P(i+1＝2/i＝1)＝P(thd1-load(i)＜＝load(a)-load(b)＜＝thd2-load(i)/i＝1)

P(i+1＝3/i＝1)＝P(thd2-load(i)＜＝load(a)-load(b)＜＝thd3-load(i)/i＝1)

P(i+1＝4/i＝1)＝P(thd3-load(i)＜＝load(a)-load(b)＜＝thd4-load(i)/i＝1)

若在i时刻网络处于状态2，即处于平衡状态，则下一时刻网络处于状态1、 2、3、4的转移概率为：

P(i+1＝1/i＝2)＝P(-load(i)＜＝load(a)-load(b)＜＝thd1-load(i)/i＝2)

P(i+1＝2/i＝2)＝P(thd1-load(i)＜＝load(a)-load(b)＜＝thd2-load(i)/i＝2)

P(i+1＝3/i＝2)＝P(thd2-load(i)＜＝load(a)-load(b)＜＝thd3-load(i)/i＝2)

P(i+1＝4/i＝2)＝P(thd3-load(i)＜＝load(a)-load(b)＜＝thd4-load(i)/i＝2)

若在i时刻网络处于状态3，即处于重载状态，则下一时刻网络处于状态1、 2、3、4的转移概率为：

P(i+1＝1/i＝3)＝P(-load(i)＜＝load(a)-load(b)＜＝thd1-load(i)/i＝3)

P(i+1＝2/i＝3)＝P(thd1-load(i)＜＝load(a)-load(b)＜＝thd2-load(i)/i＝3)

P(i+1＝3/i＝3)＝P(thd2-load(i)＜＝load(a)-load(b)＜＝thd3-load(i)/i＝3)

P(i+1＝4/i＝3)＝P(thd3-load(i)＜＝load(a)-load(b)＜＝thd4-load(i)/i＝3)

若在i时刻网络处于状态4，即处于过载状态，则下一时刻网络处于状态1、 2、3、4的转移概率为：

P(i+1＝1/i＝4)＝P(-load(i)＜＝load(a)-load(b)＜＝thd1-load(i)/i＝4)

P(i+1＝2/i＝4)＝P(thd1-load(i)＜＝load(a)-load(b)＜＝thd2-load(i)/i＝4)

P(i+1＝3/i＝4)＝P(thd2-load(i)＜＝load(a)-load(b)＜＝thd3-load(i)/i＝4)

P(i+1＝4/i＝4)＝P(thd3-load(i)＜＝load(a)-load(b)＜＝thd4-load(i)/i＝4)

步骤4、计算每个网络当前的负载效益值

单纯以网络的实际负载值作为切换指标，就没有结合网络预测负载状态的 情况。为了更好地利用马尔科夫计算的负载处于各种状态的概率，使得网络对 负载情况有预知功能以方便用户选择负载合适的网络作为切换网络，本发明定 义了负载效益值，每个网络根据上一时刻负载效益值，以及此时网络负载处于 轻载、平衡、过载、重载的概率，计算出该时刻此网络的负载效益值，如下式 （8）所示：

$E_{t_{i+1}}\left(N_j\right)=P_{i+\mathrm{1,4}}\times P_{i+\mathrm{1,3}}\times \frac{E_{t_i}\left(N_j\right)}{P_{i+\mathrm{1,1}}\times P_{i+\mathrm{1,2}}}$    —式（8）

其中，为j网络在t_i时刻负载效益值，P_i+1,1P_i+1,2P_i+1,3P_i+1,4为节点在t_i+1分别 处于状态1、2、3、4的概率。

步骤5、自适应接入控制策略

每个网络节点N_j每隔一个时间周期检查自己节点上的负载，若该节点上的 负载超过预备门限Thd0（每个节点的初始Thd0＝0.4*C_max），则触发上述自适应负载均 衡方法，对该节点下一时刻的负载状态进行概率预测，从而计算出下一时刻该 节点的负载效益值。当有新的呼叫或者有切换请求时，如有两个或两个以上的 网络满足基本的RSS接入条件时，接入控制会选择负载效益值最小的网络作为 目标小区，即

$\mathrm{Opt}-F:\mathrm{MinF}={\mathrm{Min}}_{\forall j\in x}{E}_{t_{i+1}}\left(N_j\right)$   —式（9）

其中，x为所有网络节点的集合。

定义全局平均负载效益值，在每个时刻系统中所有节点负载效益值的平均， 用_{avg_E}来表示，n表示所有节点的数目，则有：

$\mathrm{avg}\_E=\frac{\underset{j=1}{\overset{n}{\Sigma }}{E}_{t_{i+1}}\left(N_j\right)}{n}$      —式（10）

当某些节点长时间处于轻载或平衡状态时，可以不用一直执行负载均衡的 方法，这样会浪费系统的计算资源，所以本发明设计了自适应触发门限的计算 方法：

（1）初始时，对于节点j的预备门限Thd0设为固定值0.4*C_max；

（2）在t_i+1时刻，节点j的负载效益值为同时可以计算出全局平均 负载效益值为avg_E；

（3）若则说明此节点下一时刻负载轻，没有必要进行负 载均衡，或者触发负载均衡策略的门限值（即Thd0）可以相应的提高一个步长Δ； 相反，若则说明此节点下一时刻负载重，为了保证能触发负 载均衡方法，门限值（即Thd0）相应的降低一个步长Δ。

结合图3，网络中的每个节点都计算着本节点当前时刻的负载值，若负载大 于动态预备门限值，则此节点执行负载均衡方法，根据当前时刻负载状态以及 转移概率预测出下一时刻负载处于各种状态的概率，计算出对应的负载效益值， 以及该节点下一时刻的预备门限是降低还是提高一个步长。

当有一个新的呼叫或者切换到达该节点时，选择满足式（9）或者负载效益 值小于avg_E的网络节点接入，保证新的呼叫接入到负载较轻的网络中，从而达 到系统负载均衡。