法律状态公告日
法律状态信息
法律状态
2014-06-04
授权
授权
2012-06-27
实质审查的生效 IPC(主分类):H04L12/56 申请日:20111123
实质审查的生效
2012-05-09
公开
公开
技术领域
本发明涉及移动通信组网方法体系中的状态处理技术领域,具体 涉及一种基于节点间链路反馈控制机制的节点状态控制方法。
背景技术
移动网络就是节点移动的网络,由于节点的移动引入了网络拓扑 结构的不确定性,从而对节点状态及路径状态的平稳性产生了不利影 响,为移动网络的组网以及网络协议和系统设计带来了新的技术难 度。
状态处理分状态获取和状态控制,状态获取分为节点状态获取和 路径状态获取,状态控制又分为节点状态控制和路径状态控制。
一般用于描述节点状态的度量参数主要有可用带宽(剩余出口带 宽)、缓冲区排队长度、节点处理能力(AdHoc网用)、延时的概率密 度函数PDF等。获取PDF的方法有两种:节点状态测量和节点状态 探测。状态获取过程要求采样要独立,且采样数据足够多。节点状态 测量是对节点状态进行定时或不定时观察,获取状态的样本值,从而 获得节点状态的PDF。节点状态探测是一个节点通过向网络发送探测 包,以获取其它节点状态的样本值,从而获得其它节点状态的PDF 函数。由于在一般情况下,节点状态测量要求的平稳时间远小于节点 状态探测,在接入网中,基本都采用节点状态测量的方法。
节点状态更新总是与节点状态平稳性联系在一起的,并通过状态 发布过程实现。只有当节点状态变化过程是非平稳随机过程,才需要 进行状态更新。而在网络中,节点状态不可能是平稳的,网络各节点 的与其它节点状态有关的行为都依赖于状态更新方法。由于网络中节 点状态变化过程是一个非平稳随机过程,当节点状态统计特征变化 时,需要根据节点状态的统计变化量,决定是否对其它节点发布状态 并更新本节点的状态。
路径状态获取方法有两种。方法一:源节点根据接收到的网络各 节点状态,计算到达目标节点的各路径延时的概率密度函数。在节点 状态独立的假设下,可通过计算路径中各节点的延时的概率密度函数 的卷积获得路径的延时概率密度函数(路径状态)。方法二:源节点 周期性地向网络中各节点发送探测包,根据目的节点收到探测包的延 时,统计各路径的延时概率密度函数(路径状态)。
状态控制分为节点状态控制和路径状态控制。而路径的状态主要 由节点状态决定。因此状态控制的目的实际主要是通过网络机制或 QoS保证机制的作用,保证节点状态平稳。
节点状态平稳是实现QoS保证的基本条件。节点状态平稳是指 节点状态在时间上具有短时平稳性。也就是可以认为在两次状态更新 期间,节点状态近似一个平稳的随机过程,它的统计特性,如均值、 方差和概率分布近似不变。所有QoS保证机制(整形、接纳控制、 调度、路由等)的设计都应围绕使节点状态平稳这一基本前提。
发明内容
(一)要解决的技术问题
本发明所要解决的技术问题是:如何保持节点移动网络中节点状 态的平稳性。
(二)技术方案
为解决上述技术问题,本发明提供了一种基于节点间链路反馈控 制机制的节点状态控制方法,该方法中,假设各节点状态相互独立, 且该方法包括以下步骤:
S1、建立链路数据率的控制目标;
S2、利用节点间链路状态反馈控制机制来实现所述控制目标,所 述节点间链路状态反馈控制机制包括:链路的尾节点对数据率的预测 与对反馈控制量的计算,以及首节点对输出数据率的控制。
优选地,尾节点根据输入数据率对尾节点的其他出口链路的稳定 性影响的预测结果计算得到所述反馈控制量;首节点的输出数据率根 据所述反馈控制量和对链路数据率的稳定性要求计算得到。
优选地,步骤S1具体为:
设E={ei,j},vi,vj∈V,Ts表示控制周期,对任意一条从节点p到节 点S链路ep,S,p,S∈V,任意第k个控制周期的数据率Rp,S(k)用这个周 期的平均数据率求出,k为正整数,V表示网络中所有节点的集合, V={v1,v2,...,vM};ei,j表示从节点vi到节点vj的有向链路,对于链路ei,j, 节点vi是vj的上一节点,vj是vi的下一节点,节点vi称为链路ei,j的首节点, vj称为链路ei,j的尾节点;E表示网络中所有有向链路的集合, E={ei,j}(vi,vj∈V);
如果在第k-1周期中,链路ep,S的数据率为Rp,S(k-1),则要求在第 k个周期的数据率Rp,S(k)满足式(1)
Rp,S(k)≤maxRp,S(k)=Rp,S(k-1)+α(Cp,S-Rp,S(k-1)) (1)
其中,maxRp,S(k)表示第k周期为保持链路稳定所要求的最大数 据率,α为控制参量,Cp,S表示链路ep,S的传输容量;
式(1)就是对链路数据率的控制目标。
优选地,步骤S2中,对数据率的预测与对反馈控制量的计算过 程具体为:
在第k-1个周期,根据前L个周期输入输出对数据率的统计值, 分别预测每个输入输出对数据率在k个周期的值得到输入输 出对数据率矩阵的预测矩阵和每条输入链路数据率的预测值 L≤k-1,表示节点S的邻节点p到邻节点n的数据率 的预测值;
节点S根据第k-1个周期的统计量Rp,S(k-1),计算得到第k个周 期为保持链路稳定所要求的最大数据率maxRp,S(k);
比较和maxRp,S(k),如果则相应地修正 该链路所包含的输入输出对数据率的预测值,得到新的预测量 同样,对其它输入输出对数据率的预测值进行修正,得到修 正后的输入输出对数据率矩阵的预测矩阵
对数据率预测矩阵求行和,得到第k周期输出链路数据率的 预测值对于输出链路eS,n,如果则 第k个周期与链路eS,n相关的输入输出对数据率的允许量与预 测值相同,否则按比例减小每个与链路eS,n相关的输入输出对数据率 的预测值,作为第k个周期的输入输出对数据率允许量,从而得到第k 周期的节点S分配给相邻节点的输入输出数据率允许量构成的向量 XS*(k);
对数据率矩阵的预测矩阵求列和,得到节点S对每条输入链 路的数据率的反馈控制量R*p,S(k)。
优选地,首节点对输出数据率进行控制具体为:
节点p根据从节点S接收到的反馈控制量和链路数据率的控制目 标,计算每个周期k的输出数据率,并由链路的首节点在其相应的端 口通过令牌生成速率可变的令牌桶对输出数据率进行控制。
优选地,节点的每个输出端口按照所述控制周期调整令牌生成速 率。
(三)有益效果
本发明由于采用了节点间链路状态反馈控制机制,通过对链路数 据率的预测和相邻节点间的反馈控制实现对链路数据率变化的控制。 将该方法应用于路由机制和拥塞控制,可以大幅度降低业务在传输过 程中的丢包率,减小网络中节点排队长度,从而降低数据包在节点的 延时。
附图说明
图1是本发明实施例的方法流程图;
图2以节点S为主要研究点的邻节点连接图;
图3为LFCS控制机制示意图;
图4为反馈量的计算流图。
具体实施方式
下面对于本发明所提出的一种基于节点间链路反馈控制机制的 节点状态控制方法,结合附图和实施例详细说明。
首先介绍本发明中用到的节点状态独立性假设。
节点状态独立的假设在QoS研究中经常使用,因为它可以使很多 问题的研究得到简化。在以链路延时为节点状态,以延时的概率密度 函数为状态信息的QoS机制中,这个假设尤其重要。没有这个假设, 端到端路径延时的概率密度函数的计算是NP-Hard问题。如果这个假 设成立,而且网络中各链路延时的概率密度函数是已知的,那么所有 路径延时的概率密度函数都可通过链路延时概率密度函数的卷积得 到。进而可以很容易地计算出各个路径的度量参数,如延时的均值、 方差和丢包率。
在自治域系统中,尚未对这一假设的合理性进行验证。自治域系 统是具有自己独立选路策略的管理区域。例如,由一个公司的内部网 络或一个学校的校园网可以认为是一个自治域系统。在一个自治域系 统内,路由器的选路功能通过运行内部网关协议(Interior Gateway Protocol,IGP)实现。自治域之间的选路通过外部网关协议(Exterior Gateway Protocol,EGP)进行。自治域系统之间的通信与自治域系统 内部使用的IGP协议是相互独立的。将网络分成多个独立的控制域可 以使得网络更加易于管理,并且允许网络运营商ISP在其自治域系统 内部选用任何的内部网关协议。自治域系统中,业务按一定的顺序在 网络中传输,共享网络资源,一定会引起节点状态间的相关性。但由 于自治域系统一般连通性较好,各节点都有多个输入输出端口。因此, 大量业务在路由节点合并与分开的平均效果可以减弱相邻节点状态 间的相关性,使它们近似地具有独立性。如果这个设想成立,将给以 延时为约束条件的路由问题的求解带来极大的方便。
为了验证节点状态独立性假设,构建了基于美国MCI(Microwave Communication Industry)互联网服务商的网络拓扑结构的源路由(状 态路由)仿真平台,通过自相似业务仿真研究自治域系统节点状态独 立性问题。将仿真得到的实际测量的概率函数结果与理论计算结果 (假设节点状态独立,用链路延时概率函数的卷积计算路径延时的概 率函数)进行比较。首次采用K-L散度法对路径延时的均值、方差和 丢包率等参数进行比对。仿真结果表明,在自治域系统中,节点状态 是近似独立的,基于这一假设计算得到的路径参数与实际情况十分接 近,可以在以链路延时的概率密度函数为状态信息的QoS路由中作为 多约束路径求解的依据。
下面介绍本发明的节点间链路反馈控制机制LFCS。
为了提高节点状态的保持概率,本发明引入了状态控制机制,对 节点状态进行控制。以节点每个出口所连接的有向链路的可用带宽作 为受控状态度量参数。选择可用带宽度量参数作为受控状态主要是考 虑到可用带宽是一个重要的网络服务质量的度量参数(网络服务质量 的度量参数包括可用带宽、延时、延时抖动、跳数、丢包率和代价), 而且,在数据包传输过程中,除了数据包所经过的节点的跳数,该路 径的其他度量参数都与传输路径的可用带宽有关。
对于任意一条链路,其物理带宽固定,可用带宽等于物理带宽与 实际数据率(也称为实际数据传输速率)之差。因此,以实际数据率 作为控制对象,通过对链路实际数据率变化的控制,完成对节点可用 带宽的控制。
下面是对方法中所用到的符号的说明。
(1)V表示网络中所有节点的集合,V={v1,v2,...,vM};
(2)ei,j表示从节点vi到节点vj的有向链路,对于链路ei,j,节点vi是vj的 上一节点,vj是vi的下一节点,节点vi称为链路ei,j的首节点,vj称为链 路ei,j的尾节点;
(3)E表示网络中所有有向链路的集合,E={ei,j}(vi,vj∈V);
(4)dij表示链路ei,j∈E的线路延时;
(5)Ci,j表示链路ei,j的传输容量,一般Ci,j是一个固定量;
(6)Ri,j表示链路ei,j的实际数据传输速率,简称数据率;
(7)Ri,j*表示链路ei,j上允许的最大数据传输速率;
(8)Bi,j表示链路可以提供的带宽,简称可用带宽,Bi,j=Ri,j*, 假设S是网络中一个路由节点(S∈V),节点S的邻节点个数为N;
(9)Vs表示V中任一节点S的邻节点的集合;
(10)xi,S,j表示节点S的邻节点i到邻节点j的数据率,称为节点S的一个 输入输出对(i到j)的数据率。i ∈Vs,j∈Vs,且i=j时,xi,S,j=0;
(11)Xs表示节点S的输入输出对的数据率矩阵
可以看出,Xs是一个对角线元素为零的矩阵。
本发明的方法包括以下步骤:
S1、首先建立控制目标:
为了提高节点状态(可用带宽)的保持概率,周期地对链路的实 际数据率变化进行控制。
设E={ei,j}(vi,vj∈V),Ts表示控制周期。对任意一条从节点p到节 点S链路ep,S,p,S∈V,任意第k个控制周期的实际数据率Rp,S(k)用这 个周期的平均数据率求出,k为正整数,即:
Rp,S(k)=第k个周期中链路ep,S传输的业务总量/Ts。
如果在第k-1周期中,链路ep,S的实际数据率为Rp,S(k-1),则要求 在第k个周期的实际数据率Rp,S(k)必须满足式(1)
Rp,S(k)≤maxRp,S(k)=Rp,S(k-1)+α(Cp,S-Rp,S(k-1)) (1)
其中,maxRp,S(k)表示第k周期为保持链路稳定所要求的最大数 据率,α为一个常数,称为控制参量,且0≤α≤1。α值的选取直接 影响着控制系统的稳定性,链路利用率和链路状态的维持度。Cp,S表 示链路ep,S的传输容量。
当α=1时,maxRp,S(k)=Cp,S (2)
当α=0时,maxRp,S(k)=Rp,S(k-1) (3)
而且Rp,S(k)≤maxRp,S(k)≤Cp,S
式(1)就是对链路实际数据率的控制目标。
S2、利用节点间链路状态反馈控制机制来实现所述控制目标:
下面设计了一种节点间链路状态反馈控制机制来实现式(1)的 控制目标。节点间链路状态控制是一种周期性的控制,包括两个过程: S21、链路的尾节点对数据率的预测与反馈控制量的计算;S22、首节 点对输出数据率的控制。
其中,尾节点的反馈控制量根据输入数据率对尾节点的其他出口 链路的稳定性影响的预测结果计算得到;首节点的输出数据率则根据 反馈控制量和对链路数据率的稳定性要求计算得到。
以链路ep,S输出数据率的控制过程为例进行说明。如图2所示。
图2中节点p为链路ep,S的首节点,S为链路ep,S的尾节点,节点 p、n都是S的邻节点,节点p是输入节点,节点n是输出节点,与S 相邻的节点个数为N。
节点S对链路数据率的预测与反馈控制量的计算:
节点S以Ts为控制周期观测并统计每个输入输出对的数据率,得 到每个周期的输入输出对的数据率xp,S,n(k),k为周期数,p,n∈Vs。
在第k-1个周期,根据前L个周期(L≤k-1)输入输出对数据率 的统计值,分别预测每个输入输出对数据率在k个周期的值 得到输入输出对数据率矩阵的预测矩阵和每条输入链路数据率 的预测值
根据链路的控制目标,链路的数据率在每个周期的增长量是受限 的。节点S根据第k-1个周期的统计量Rp,S(k-1),计算得到第k个周 期为保持链路稳定所要求的最大数据率maxRp,S(k)。
比较和maxRp,S(k)。如果则相应修正(修 正方式见下式(13))该链路所包含的输入输出对数据率的预测值, 得到新的预测量同样,可以对其他的输入输出对数据率的预 测值进行修正,得到修正后的输入输出对数据率矩阵的预测矩阵
求第k周期的节点S分配给相邻节点的输入输出数据率允许量构 成的矩阵XS*(k)的方法为:对数据率预测矩阵求行和,得到第k 周期输出链路数据率的预测值对于输出链路eS,n,如果 则第k个周期与链路eS,n相关的输入输出对 数据率的允许量与预测值相同,否则按比例减小每个与链路 eS,n相关的输入输出对数据率的预测值,作为第k个周期的输入输出对 数据率允许量。这样就得到了Xs*(k)。
对数据率矩阵的预测矩阵求列和,就可以得到节点S对每条 输入链路的数据率的反馈控制量R*p,S(k)。
以上步骤为预测过程与反馈控制量产生过程的描述。
下面介绍首节点对输出数据率的控制过程。
节点p根据从节点S收到的反馈控制量和链路数据率的控制目标, 计算每个周期k的实际输出数据率,以Rp,S(k)为例:
通过令牌生成速率可变的令牌桶完成输出数据率控制。
图3是以链路ep,S为例的链路状态控制机制的示意图。图3中, 阴影部分标记了节点p与节点S之间的链路ep,S数据率的反馈控制过 程。其中,流量统计与预测过程和反馈量的计算与反馈包的发送过程 是由链路ep,S的尾节点S完成的,节点端口数据输出控制过程是在首节 点p完成的。其中,RCPS,p(k)表示第k个周期,节点S发往节点p的反馈 控制包,BuffS,p(k)表示第k个周期中节点p到节点S的输出端口的缓冲区 数据量,ρS,p(k)表示第k周期控制输出的令牌桶的令牌生成速率。
下面,对节点间链路状态反馈控制机制(LFCS)的各个过程进 行详细介绍。
首先介绍流量统计与预测过程
由于链路控制是在相邻节点间完成的,而一般网络邻节点间链路 的物理延时比较小,因此为链路流量的预测提供了可能。下面以图2 为例说明流量统计与预测过程。
在预测过程中,节点S对它的每个输入输出对数据率xi,S,j进行单独 预测,得出第k个周期的预测值,用表示。然后由每个输入输 出对数据率的预测值构成输入输出对数据率预测矩阵,用表示 对第k个周期的预测矩阵。
由于每个输入输出对数据率是单独进行预测的,介绍预测算法 时,将xp,S,n(k),简记为xk,其预测值简记为
预测算法描述:
借鉴指数加权的递归最小平方算法RLS(Recursive Least Square),利用自适应FIR滤波器进行预测。对两个相邻节点间的数 据流进行预测,因此可以根据链路延时合理设计控制周期Ts,使得只 需要做一步预测。
假设预测记忆长度为L,FIR非递归滤波器中,wi(i=0,1,...,L)是滤 波器的系数。令W=[w0,...,wL-1]T为滤波器的系数矢量。采用指数加权 的递归最小平方算法时动态改变滤波器的系数矢量,预测时,
Φk=[xk-1,...,xk-L]T=[zk,...,zk-L+1]T
自适应滤波器寄存器赋值:
预测误差:
增益向量:
自适应滤波器系数向量:
误差相关矩阵:
预测输出:
其中λ称为遗忘因子(0<λ<1)。如果记忆长度为L,则L=-1/logλ。
初始值的确定:
初始值的具体取值方法:
令
式(4)~(11)中各符号为现有FIR非递归滤波器中所涉及的符 号,为现有技术。其中,Φk是记忆长度为L的L维滤波器观测值组成 的向量;xk是滤波器输入序列,也就是前面介绍的输入输出对数据率 xp,S,n(k);zk是滤波器的第K次观测值。
确定初始值w0和P0时,也可以简单地令w0=0,P0=1/σI(其中I是单 位阵,σ是一个小正数)。σ的典型值为100/Var[z(0)]。
预测值由以上的预测算法得到。
反馈控制量的计算与反馈包的发送:
反馈控制量的计算:
节点S的每个出口速率受到各个入口速率的影响。为了使各个出 口所连接的链路满足式(1)的控制目标,节点S根据输入输出对数据 率的预测值,计算可以接受的每个输入链路的到达速率(即允许的输 入链路速率R*i,S(k)),此允许到达速率就是节点S对输入链路的上一级 节点的反馈控制量。S通过反馈包RCPS,i将反馈控制量通过给链路ei,S的 上一级节点。
仍然以图2为例,反馈控制量的计算过程如下。
得到预测值以后,节点S根据该值进行相应的分配。得到预测矩 阵后进行以下计算:
1)预测p到S的输入链路的速率:
2)判决是否需要修正预测值:
比较与maxRp,S(k)(根据(1)式求得)。根据链路稳定要 求,在周期k,链路数据率不会超过maxRp,S(k)。如果需要修正相关输入输出对数据率的预测值。
3)修正预测值:
(13)
同理,可以得到其他的
4)预测S到节点j的链路输出量:
5)计算输入输出数据率允许矩阵(输入输出数据率允许量构成 的矩阵)调整系数:
6)计算输入输出数据率允许矩阵元素值:
7)计算输入链路允许速率:(17)
反馈量的计算可以用图4所示的流图表示。
反馈包的发送:
如果仅存在一个j∈N,使得βS,j(k)<1,则节点S对除节点j以外的 节点进行反馈控制,反馈控制量为如果有两个以上的 βS,j(k)<1,则节点S对其所有相邻节点进行反馈控制。如果所有的 βS,j(k)≥1,则本周期不做反馈控制。
节点端口数据输出控制过程
链路实际数据率的控制由链路的首节点在其相应的端口采用令 牌生成速率可变的令牌桶完成。设计思路:节点的每个输出端口按照 统计周期TS周期地调整令牌生成速率ρp,S(k)。
这里以链路ep,S∈E为例说明实现过程。Rp,S(k)在以下说明中都简 记为Rk。其他相关标记都类似简记。
设链路ep,S第k个周期结束时,输出令牌桶中的令牌个数为Yk个。 第k个周期的统计输出数据率是Rk。
第k+1个周期的链路上实际允许输出数据率为:
其中maxRk+1=Rk+α(C-Rk)(根据式(1)求得,是该输出端 口收到的反馈控制量。
则第k+1个周期中,链路最大允许输出数据量为:Rk+1Ts
第k+1个周期中的该端口输出令牌生成速率ρk+1需要满足(18)、 (19)两式:
ρk+1t+Yk=Ct (18)
ρk+1(Ts-t)+Ct≤Rk+1Ts (19)
其中C是链路ep,S的物理带宽。t,(0≤t≤T),是一个周期内以满速 (就是以最大链路容量)进行发送的时间。
最大允许的ρk+1以由足(18)、(19)两式在(19)式取等号时 求出。
因此按照(20)式可以周期地递推输出令牌桶的令牌生成速率。
以上实施方式仅用于说明本发明,而并非对本发明的限制,有关 技术领域的普通技术人员,在不脱离本发明的精神和范围的情况下, 还可以做出各种变化和变型,因此所有等同的技术方案也属于本发明 的范畴,本发明的专利保护范围应由权利要求限定。
机译: 用于触发由用户设备实现的非周期性信道状态信息反馈的设备,具有反馈模块,该反馈模块生成用于过程的反馈,并且包括报告的报告通过物理上行链路共享信道发送到节点
机译: 基于计算节点参与状态的计算节点过程控制机制
机译: 通过基于节点处的业务从正常状态转变为第一低功率状态或者在接收到准予第二请求的消息的第二低功率状态时从家庭状态转变为第一低功率状态,来对家庭娱乐网络中的节点进行功率管理的方法和装置节点的低功耗状态