CN1440164A - 基于线性能量函数的服务质量路由预计算算法 - Google Patents

Abstract

基于线性能量函数的服务质量路由预计算算法属于具有多个服务质量参数的服务质量路由技术领域，其特征在于：它是以采用线性能量函数把多个服务质量(QoS)参数转换成单一能量值为基础的。它先使用多个线性能量函数为每条链路计算出一组能量值，再据此以源节点为树根建立最短路径树，使得从根节点到达任意节点沿着该树的路径具有最小能量值，然后根据最短路径树计算出部分QoS路由表，最后把所有能量函数的这些部分QoS路由表组合在一起形成一个完整的QoS路由表。当能量函数的个数在7～10个之间时，其失效概率已经非常小了。

Description

基于线性能量函数的服务质量路由预计算算法

技术领域

基于线性能量函数的服务质量路由预计算算法属于互联网路由技术领域，尤其涉及具有多个服务质量参数的服务质量(QoS)路由技术。

背景技术

如何为应用提供不同的服务质量(Quality-of-service，QoS)保证是互联网络面临的一个重要难题，而服务质量路由(QoS Routing，QoSR)则是其中的一个核心技术和热点问题，它的主要作用是为QoS业务寻找能够同时满足多种QoS约束的可行路径。通常QoS限制可分为链路限制和路径限制。其中，链路限制可以转化为对整个路径上瓶颈链路的限制，如带宽；而路径限制则是对组成端到端路径上的所有链路的限制，如延迟。由于对链路限制来说，可以通过剪枝预先除去不符合要求的链路，从而保证在剩余子图中求得的路径符合链路限制，因此这个专利主要考虑多重(k＞＝2)路径限制(也称为多约束)的情况。

由于多约束的QoSR无法在多项式时间内求解，为此研究人员设计了很多启发式算法。然而这些算法往往具有很大的局限性：(1)计算复杂度过高、无法应用到实际环境中；(2)算法性能太低，找不到实际存在的可行路径；(3)算法只是针对某些特殊情况设计的，不具有普适性。这个专利提出一种基于线性能量函数的QoS路由预计算算法LEFPA(Linear EnergyFunction-based Precomputation Algorithm)，该算法使用多个线性能量函数为每条链路计算出一组能量值，然后根据这些能量值来计算QoS路由表。从而在进行基于服务质量的路由时，只需要通过查找路由表就可以完成路径的选择。

发明内容

本发明的目的在于提供一种基于线性能量函数的QoS路由预计算算法。

本发明所提出的方法的特征在于：算法采用线性能量函数将多个QoS参数转换成单一的能量值，进而根据这些能量值以源节点为树根，建立最短路径树(Shortest Path Tree，SPT)，使得从树根节点到达任意节点沿着该树的路径具有最小能量值。然后算法根据这个SPT计算出部分QoS路由表。由于算法使用多个线性能量函数，因此通过计算得到多个SPT及其对应多个的部分QoS路由表，最后将这多个表组合在一起，形成一个完整的QoS路由表。当QoS业务的路由请求到来时，只需要查找路由表就可以完成可行路径的计算和查找。在节点s上运行的该算法，依次含有以下步骤：

(1)初始化

输入：每个链路具有k个QoS参数的拓扑图G、根节点s、目标节点t；能量系数α=(α₁，α₂，…，α_k)，使能量系数分量的个数等于QoS参数，即为每个QoS参数定一个能量系数分量α_l∈[O，1]；能量函数的个数为B，它均匀分布在能量系数口的取值范围内，与QoS请求无关；(2)根据拓扑图G，针对B个能量系数向量中某一个尚未使用过的向量计算每条链路的能量值： $g_a\left(e\right)={\mathrm{\Σ}}_{l=1}^k{a}_l{w}_l;$ (3)从根节点s出发，计算从s到每一个节点一包括目标节点t-在内的最短路径树；(4)根据最短路径树产生部分路由表QoSR；(5)判断是否已经使用过了所有的B个向量：

若存在没有使用过的向量，则返回步骤(2)：

若不存在没有使用过的向量，择把基于B向量产生的所有部分路由表组成一个完整的

QoS路由表。

所述的能量函数B的个数为7-10个

实验证明：即便是对于规模较大的网络，B=7时失效概率已经非常小，如节点数N=500时，在95％的置信度下失效概率Pr=0.0482±0.0022。

附图说明

图1.LEFPA算法流程图

图2.算法运用实例的网络拓扑图

图3.可行路径p’与超平面之间的位置关系

a.向量α与直线P的关系；

b.向量口的连续变化示意图。

图4.不可行区域与可行区域a.M_NOT与

的关系：b.最小能量路径的跳变示意图。

图5不可行区域与可行区域a.可行区域的凸性；b.不定区域示意图。

图6线性能量函数预计算算法LEFPA伪码描述

图7失效概率

图8失效概率Pr与能量函数个数刀的关系

图9产生随机QoS请求

具体实施方式

为了便于进一步描述该算法，我们首先给出几个定义和定理。

用有向图G(V，E)表示一个网络，其中V为节点集，元素v∈V称为图G的一个顶点(节点)；E为弧集，元素e_ij∈E记为e＝v_i→v_j称为图G的一条边。在QoSR中给每个链路e关联上一组相互无关的权值(w₁(e)，w₂(e)，…，w_k(e))称为链路e的QoS度量(权值)，简写为w(e)。其中对1≤l≤k有度量w_l(e)∈R⁺满足可加性，即对路径p＝v₀→v₁→…→v_n有 $w_l\left(p\right)={\mathrm{\Σ}}_{i=1}^n{w}_l(v_{i-1}\→v_i)$ 。

定义1：多重受限路径

对于给定的有向图G(V，E)、源节点s、目的节点t和k≥2重权值w_k(e)∈R⁺，以及限制向量c＝(c₁，c₂，…，c_k)，从s到t的路径p称为多重受限路径，如果对1≤l≤k有w_l(p)≤c_l,简写为w(p)≤c。

这里的w(e)和c都是k维向量。而对于给定的QoS请求及其限制条件c，QoSR的主要任务就是在当前网络状态下寻找满足要求的路径p，使得w(p)≤c。

1.线性能量函数分析

Dijkstra给出了单一度量下计算最短路径树(SPT)的算法，并且具有较低的算法复杂度。然而对于多重受限的QoSR问题涉及到同时考虑多种度量，因此导致问题变为NPC的复杂度而无法使用原有算法。一种可能的求解思路是将多种度量转化为单一度量。

定义2：线性能量函数g_a

令线性函数 $g_a\left(e\right)={\mathrm{\Σ}}_{l=1}^k{a}_l{w}_l$ 为链路e的能量函数，表示e的耗费值。其中a₁∈[0，1]为与e无关的系数(l＝1，2，…，k)，且 ${\mathrm{\Σ}}_{l=1}^k{a}_l=1,$ 并将满足该条件的向量a＝(a₁，a₂，…，a_k)称为能量系数。

基于这样的线性能量函数，我们将原来的多重受限路径问题转化为最小能量路径问题。能量函数的每个系数则表明了在计算“最优路径”时，该系数所对应的度量与其他度量相比的相对重要程度。

定理1：以g_a(e)为关键字使用Dijkstra算法，可以建立以节点s为根的最小能量树T(g_a)，满足沿着T(g_a)从s到任意节点t的路径p_T有g_a(pT)＝min_p(s，t)∈Gg_a(p(s，t))。

证明：因为g_a(e)为线性函数，满足 $g_a(e_1+e_2)={\mathrm{\Σ}}_{l=1}^k{a}_l{w}_l(e_1+e_2)$ ${=\mathrm{\Σ}}_{l=1}^k{a}_l{w}_l\left(e_1\right)+{\mathrm{\Σ}}_{l=1}^k{a}_l{w}_l\left(e_2\right)=g_a\left(e_1\right)+g_a\left(e_2\right)$ 。所以可以首先算出每个链路的能量值g_a(e)，然后以单一权值g_a(e)为关键字代替原Dijkstra算法中的链路花费，然后使用原有算法以s为源建立SPT。由于原算法能够保证从s到任意节点沿着该SPT的路径具有最小的花费，因此以g_a(e)为关键字的算法保证p_T为从s到t的具有最小能量的路径，即g_a(P_T)＝min_p(s，t)∈Gg_a(p(s，t))。

以满足定义2的能量系数a为自变量，我们将最小能量树T(g_a)简记为T_a，而将沿着T(g_a)从s到t的路径p_T记为p_a。这样，问题转化为对给定的图G和源目的对(s，t)，能量系数a取遍空间所有可能的取值时，集合{p_a|_a}具有什么样的性质，如元素的分布、元素的个数等。为了便于研究，我们给出路径权值空间的概念，下文的分析都将在这个空间中进行。

定义3：路径权值空间

称W^k＝W₁×W₂×…×W_k为路径权值空间，如果对任意p∈G有w₁(p)∈W₁。

对于通常取值w₁(e)∈R⁺，可以令W_l=R⁺，这样对任意p有w_l(p)∈W_l，因此p为W^k中的点，即p∈W^k，而上述集合{p_a|_a}成为W^k中的点集。

定理2：对给定的图G和源目的对(s，t)及能量系数a，令 $g_{\mathrm{opt}}={\mathrm{\Σ}}_{l=1}^k{a}_l{w}_l\left(p_a\right),$ 则任意从s到t的路径p必然在空间W^k的超平面 $P=\left\{p\right|{\mathrm{\Σ}}_{l=1}^k{a}_l{w}_l\left(p\right)=g_{\mathrm{opt}}\}$ 的上方。

证明：采用反证法，若存在一点p′在超平面P的下方，则 $g_{\mathrm{opt}}={\mathrm{\Σ}}_{l=1}^k{a}_l{w}_l\left(p_a\right)>{\mathrm{\Σ}}_{l=1}^k{a}_l{w}_l\left(p^{\′}\right),$ 这与定理1中g(p_a)＝min_p(s,t)∈Gg(p(s，t))矛盾。所以如果在空间W^k中还有其他点p′，则p′必然位于超平面P的上方。

以k＝2举例，如图3a所示对给定的向量a，以能量值g_a为关键字使用Dijkstra算法计算，得到从s到t的能量最少的路径p_a。则过点p_a且垂直于向量a的垂线P构成了对空间W²的一个划分：所有从s到t的路径p′必然位于超平面P的上方。值得注意的是，由于网络拓扑图的离散性，对于连续变化的向量a，其对应的p_a在W^k空间中并不会连续变化，因此这种映射a

p_a并不是单射。如图3b所示，给定向量从a′连续变化到a″时，最小能量函数的路径不变，即p_b＝p_a对b∈[a′，a″]。这样，一个点p_a将对应多个连续变化的超平面P(b)。

2.解空间可行性分析

下面我们给出整个解空间W^k的一个划分，包括不可行区域M_NOT、必可行区域M_FEASIBLE和不定区域M_UNKNOW，使得对于任意QoS请求能够很方便的判断是否存在可行路径，如果存在则可以给出一条可行路径。

定义4：不可行区域

在解空间W^k中，对给定向量a所构造的上述超平面P，点集M(a)＝{w|w∈W^k，w位于P(a)下方}称为由a所确定的不可行区域， 称为不可行区域。

定理3：对给定解空间W^k中的不可行区域M_NOT，如果一个从s到t的QoS请求c∈M_NOT，则不存在可行路径p满足w(p)≤c。

证明：由M_NOT的定义可见，M_NOT实际上是由向量a的不断连续变化所对应的所有M(a)构成的并集。如果一个QoS请求c∈M_NOT，则根据定义必然存在向量a所构造的超平面P(a)，使得c位于P(a)下方。根据定理2，任意从s到t的路径，p′必然位于P(a)的上方，因此不存在可行路径p满足w(p)≤c。

定义5：可行区域

在解空间W^k中，点集

称为可行区域，其中M_NOT的补集 $\stackrel{\‾}{M_{\mathrm{NOT}}}=W^k\backslash M_{\mathrm{NOT}}$ 。

例如，W²空间中对于最小能量点唯一的网络来说，非可行区域与可行区域如图4a所示，其中M_NOT=M_NOT(a′)∪M_NOT(a″)。而对于一般情况下具有多个最小能量点时，则要考虑多个向量a对应同一个最小能量路径点p_a的情况，如图4b所示。给定向量从a′连续变化成为a″时，所求得的最小能量路径始终保持为p_a；而当给定向量从b′连续变化成为b″时，所求得的最小能量路径始终保持为p_b。其中，给定向量从a″变化到b′时引起的最小能量路径的跳变过程中，有向量a″＝b′，也就是对于这个向量存在多个最小能量点p_a和p_b。这种跳变引入了一个很好的性质：虽然最小能量点是离散的，但不可行区域是连续的。

定理4：可行区域M是凸集，并且p_a都在M的边界，而对M的任一顶点都存在向量a使得p_a为该顶点。

证明：分三步分别证明上述各个子命题。

(1)现证可行区域M是凸集：对给定向量a，所对应的超平面将解空间分成不可行区域和可行区域两个部分，各成为一个半空间，因此可行区域M_NOT(a)＝W^k\M_NOT(a)是一个凸集。而 因为多个凸集的交集是凸集，所以M_AVL是凸集。

(2)现证任意p_a都在M的边界：对任一p_a，以向量a为法向量过点p_a作超平面P(a)，则根据定理2有M在P(a)的一侧，因此p_a在M的边界。

(3)现证M的顶点都存在向量a使得p_a为该点：对_x为M的顶点，因为M是凸集，存在一个过点x的平面P(a)使得M在P(a)的一侧，其中a为平面的法向量。由于M为向上开放的集合，即(∞，∞，…，∞)∈M，因此M必在P(a)的上方。所以以a为给定向量，必然可以求得p_a=x。

例如，随着能量函数的不同，有多个最小能量路径时，如图5a所示可行区域M_AVL为一个凸集，且M_AVL的每个顶点必为一条最小能量路径。

下面我们进一步将M_AVL分为两个部分：必可行区域M_FEASIBLE和不定区域M_UNKNOW。

定义6：必可行区域和不定区域

称 $M_{\mathrm{FEASIBLE}}=\left\{p\right|\∃a,p\≥p_a\}$ 为必可行区域，称M_UNKNOWN＝M_AVL-M_FEASIBLE为不定区域。

例如图5b所示，W²空间中M_FEASIBLE、M_UNKNOW以及M_NOT之间的关系。

定理5：对于任意的QoS请求c，如果c∈M_FEASIBLE，则必然存在可行路径。

证明：由M_FEASIBLE的定义可见， a使得p_a≤c，因此路径p_a即为可行路径。

基于上述理论分析，首先使用预计算的方式将向量a不断变化，并保存所有最小能量路径组成的集合{p_a}，而对后续的QoS请求c则只需要根掘{p_a}就可以查找出可行路径。这个过程中，需要对QoS请求c进行分类：(1)不存在可行路径：c∈M_NOT；(2)不确定是否存在可行路径：c∈M_UNKNOWN；(3)存在可行路径：c∈M_FEASIBLE。

在实际应用中，对上述第1类情况可以直接拒绝该QoS请求，或者进行QoS协商。而对第2类不能判断的情况，则希望发生的概率越小越好，我们在第四部分的性能评价中，通过模拟给出了数值结果，说明使用最小能量路径集{p_a}不能判定的概率非常小，而绝大部分是另外两类的QoS请求。此外，我们还通过实验证明了，一个位于不可判定区域中的QoS请求，具有可行路径的概率非常小。因此一旦这类情况发生，我们可以在对整个算法性能影响很小的前提下，将其视为第1类情况并拒绝该QoS请求。对第3类情况，我们则可以从{p_a}中找到一个满足要求的元素作为可行路径。

由于实际算法中不能实现向量a的连续变化，而无法保证找到集合{p_a)中的所有元素，因此增大了不定区域M_UNKNOW。因此有必要验证：基于个数很少的离散变化的向量a所构成的集合{p_a}，所计算的不定区域M_UNKNOW对算法总体性能的影响。

由于需要将a的离散取值与网络无关，因此我们首先归一化网络度量，即任一度量在所有条链路上配置的最大值都相同，即max_e∈Ew_l(e)为与l无关的常数。

算法流程图如图1所示。下面首先通过一个实例来说明算法是如何工作的。网络拓扑结构如图2.a所示，其中每条链路包含延迟和抖动两个参数，通过路由协议交互，节点s已经具有全部网络状态信息。现在，节点s使用LEFPA算法计算QoS路由表。假设算法配置的B＝2，则首先计算出能量函数的系数a＝(1，0)，对应能量函数g_a(e)＝w₀。这时，使用该能量函数建立SPT如图2.b所示，并基于该SPT建立部分路由表。然后，再更改能量函数的系数a＝(0，1)，对应能量函数g_a(e)＝w₁。这时，使用该能量函数建立SPT如图2.c所示，并基于该SPT建立部分路由表。最后将两部分路由表综合在一起，形成最终的QoS路山表。其中，从s到t的路径有两条：(sacdt)和(sbcdt)。

我们对2度量的情况设计了基于线性能量函数的预计算算法LEFPA，如图6所示。在节点s上运行的LEFPA算法可以分成以下几个步骤：(a)根据配置产生B个向量a＝(a₁，a₂)(第3-4行)；(b)针对每个向量a和给定的拓扑图G，计算每个链路的能量值g_a(e)(第5-6行)：(c)以g_a为能量函数，使用Dijkstra算法计算以s为源节点的最小能量树T(a)(第7行)；(d)保存从s到每个节点的最小能量路径到QoS路由表(第8-9行)。其中，保存最小能量路径p_a(s，t)时，只需要查看已有从s到t的路径的最后一条p_b(s，t)是否与当前所计算出的路径相同，即是否有p_b(s,t)＝p_a(s，t)，从而可以避免多次保存同一条路径(可由定理4的凸性和定理2保证)。由于对线性函数g_a(e)的操作满足保序性，因此只要网络状态信息一致，各个节点节点使用同样的向量a所产生的路由表不会构成回路。

下面分析该算法的计算复杂度。设网络G的节点数为n＝|V|，边数m＝|E|。则步骤(b)的计算复杂度为O(m)；采用改进的dijkstra′s算法，步骤(c)的复杂度为O(nlogn+m)；步骤(d)的复杂度为O(n)。因此，整个预计算算法的计算复杂度为O(B(m+nlogn+n))。这实际上约为单一度量下原有dijkstra′s算法的B倍。

LEFPA算法通过保存最小能量路径产生了QoS路由表，由于避免保存相同路径，因此QoS路由表的规模将不大于原单一度量下路由表规模的B倍。对于2约束QoSR应用，当QoS请求c(s，t)到达时，只需要在路由表内从s到t的路径中(至多为B条)查找是否存在p_a(s，t)≤c(s，t)。如果存在则返回该p_a(s，t)；否则拒绝该QoS请求。而对于单约束求最优的QoSR应用(如DCLC)，则可以在路由表内从s到t的路径中(至多为B条)查找满足约束的最优路径。假设原单一度量下路由表的查找次数为L，则通过折半查找的方式可以实现QoS路由表的查找次数为L+[log₂B]。

由于LEFPA算法中B的取值对算法性能和复杂度都有很大影响，下面通过广泛深入的模拟实验给出B与算法性能的关系，并说明在实际应用中B取一个很小的数值(如B＝7)就能够得到很好的性能。

目前，我们已经通过大量的模拟实验验证了该算法的路由性能(路由成功率)，包括对算法绝对性能的评价、相对性能的评价、以及和其他算法的比较，都说明该算法具有很好的性能。

我们使用与QoS请求无关的“不定区域比例法”来评价LEFPA算法的绝对性能。评价QoSR算法性能的常用方法有两种。(1)竞争率：算法能够找到可行路径的请求数目与存在可行路径的请求数目的比值；(2)路由成功率：算法能够找到可行路径的请求数目与所模拟的总请求数目的比值。

这两种评价方法的区别在于作为分母的QoS请求是否在一定具有可行路径。这两种方法都有一个共同的缺陷：计算结果很大程度上依赖于所产生的QoS请求的限定条件，即QoS限制的分布。对于大规模网络拓扑图来说，很难判断一个QoS请求是否存在可行路径，因此路由成功率得到了广泛的应用。然而路由成功率更大程度上依赖于QoS请求的限制条件，而不同的文献采用不同的产生方法，这导致路由成功率失去了绝对数值的评价意义，只有在同一批数据的相对比较中才有意义。

为避免这个问题，本文采用与QoS请求无关的“不定区域比例法”，把使用LEFPA算法不可判定的区域作为算法失效区域，而模拟实验就是分析算法的失效概率 $\mathrm{Pr}=\frac{M_{\mathrm{UNKNOWN}}}{M_{\mathrm{NOT}}+M_{\mathrm{AVL}}}$ 与B的关系。如图7所示，由于M_UNKNOWN为有界区域，而M_NOT和M_AVL都是无界区域，因此我们分别取最上面的点p_a和最右面的点p_b作为边界点，上式的分母就是图7中所有阴影部分(为矩形)的面积。

基于N个节点的完全随机拓扑图，我们为每个链路产生了在[1，1000]区间内均匀分布的两种度量w₁(e)和w₂(e)，且两者相互无关。我们分别模拟了网络节点数N为50、100、200和500的情况，并对每种情况产生了10个拓扑图，在每个拓扑图上随机进行100次源节点的选取(一个节点可能被选取多次)，每个源节点s使用LEFPA算法分别以B个线性能量函数 计算最小能量路径。其中，a_i＝(i/(B-1)，(1-i)/(B-1))，i＝0，1，…，B-1。每个源节点s则以网络中的每个节点，作为目标节点，求得 ${\mathrm{Pr}}_s=\frac{1}{N}{\mathrm{\Σ}}_{t\∈G}{\mathrm{Pr}}_s\left(t\right),$ 然后对所有源节点s再求平均值得到 $\mathrm{Pr}=\frac{1}{100}\mathrm{\Σ}{\mathrm{Pr}}_s$ 。最后通过对10个同类拓扑图所对应的10个Pr的统计，得到其均值和95％的置信区间 Pr±σ。

在节点数分别为50、100、200和500的拓扑图中，失效概率Pr与B的关系如图8所示。中间的折线为每类10个图的平均值，上下两条线表示了95％的置信区间。从图中的数据可见，当网络的节点数较少时，不定区域所占的比例非常小；而随着节点数的增加Pr增大。这是因为节点数少的网络对两个度量中的任何一个进行优化的能力小；而节点数多的网络能够选择的路径较多，从而对路径优化能力强。这使得图7中最上面的点p_a相对更靠近纵坐标，而最右面的点p_b相对更靠近横坐标。此外，随着可选路径的增多，置信区间的范围渐小，说明了LEFPA算法对大规模网络的适应性。

图8表明，即便是对于规模较大的网络，B＝7的失效概率Pr已经非常小了(如N＝500时，在95％的置信度下Pr＝0.0482±0.0022。这说明对于实际网络应用来说，使用10个均匀分布的线性函数已经能够找到足够多的具有不同特点路径，而继续增大B则找到的路径在很大概率上是重复的，这与的结论类似。

前面已经论证了不定区域的面积(失效概率Pr)非常小，下面再进一步论证位于不定区域的QoS请求c∈M_UNKNOWN，其可行性也非常小。为此，我们在图7所示的不定区域中随机产生QoS约束，然后使用目前所见到的性能最好的算法之一H_MCOP计算可行路径，如图9所示。实验数据表明，B＝7时H_MCOP算法的路由成功率在5％以下，而绝大多数请求不具有可行路径。

综合考虑：(1)不定区域的面积(失效概率Pr)非常小；(2)位于不定区域的QoS请求，其可行性非常小。因此，LEFPA算法拒绝位于不定区域的QoS请求，所引入的误判(拒绝具有可行路径的QoS请求)概率非常小(约为0.05×0.05＝0.25％)，所以算法具有很高的性能。此外，由于计算路由所依赖的网络状态信息所固有的陈旧性，因此可以认为如此小的误判概率将不再是影响实际路由性能的主要因素。

综上所述，下一代提供QoS的网络可以继续沿用目前Internet路由的预计算方式，只需要在计算最小路径树时稍加更改，将单一的最小花费变成最小能量，而使用与网络无关的B(B＝7)个均匀分布的线性能量函数来计算最小能量树，这样预计算的复杂度只增加为原来的B倍。考虑可能存在的重复路径，所计算出的路由表将小于现在路由表规模的B倍，现有的路由查找技术完全能够胜任。

由于基于服务质量的网络是国际互联网发展的必然方向，而网络中的路由器为了提供QoS的支持，就需要使用QoSR算法，因此QoSR算法也必然广泛的应用在下一代互联网中。由于我们所设计的启发式算法LEFPA不仅具有很高的基本性能，而且符合现在Internet的路由计算方式——预计算。因此，LEFPA算法具有广泛的适用性，是下一代互联网可能采用的QoSR算法。

由此可见，本发明达到了预期目的。

Claims (2)

1.基于线性能量函数的服务质量路由预计算算法其特征在于：它是借助于路由器硬件平台以采用线性能量函数把多个服务质量(QoS)参数转换成单一的能量值为基础的；它先使用多个线性能量函数为每条链路计算出一组能量值，进而根据这些能量值以源节点为树根，建立最短路径树，使得从树根节点到达任意节点沿着该树的路径具有最小能量值，再根据这些最短能量树计算出部分QoS路由表，最后把所有能量函数的这些部分QoS路由表组合在一起，形成一个完整的QoS路由表，它依次含有以下步骤：

(1)初始化输入：每个链路具有k个QoS参数的拓扑图G、根节点s、目标节点t；能量系数a＝(a₁，a₂，…，a_k)，使能量系数分量的个数等于QoS参数，即为每个QoS参数定一个能量系数分量a₁∈[0，1]；能量函数的个数为B，它均匀分布在能量系数a的取值范围内，与QoS请求无关；

(2)根据拓扑图G，针对B个能量系数向量中某一个尚未使用过的向量计算每条链路的能量值： $g_a\left(e\right)={\mathrm{\Σ}}_{l=1}^k{a}_l{w}_l;$

(3)从根节点s出发，计算从s到每一个节点—包括目标节点t—在内的最短路径树；

(4)根据最短路径树产生部分路由表QoSR；

(5)判断是否已经使用过了所有的B个向量：

若存在没有使用过的向量，则返回步骤(2)；

若不存在没有使用过的向量，择把基于B向量产生的所有部分路由表组成一个完整的QoS路由表。

2.根据权利要求1所述的基于线性能量函数的服务质量路由预计算算法，其特征在于：所述的能量函数B的个数为7～10个。

Images