APP下载

基于二次型规划考虑网络丢包的鲁棒状态估计

2012-03-07王中杰易总根

关键词:估计值鲁棒性数据包

王中杰,易总根

(同济大学电子与信息工程学院,上海201804)

随着通信网络的发展,基于网络的反馈控制系统(NCS)受到越来越多的关注[1-2].在NCS中,从传感器节点到控制节点和从控制节点到执行器节点之间的数据传输与通信都必须通过网络进行.而与此同时,由于微机电系统(MEMS)技术的发展,无线传感网络(WSN)的应用也越来越广泛[3].在WSN中,传感器节点感知并且收集数据然后发送给中心节点进行处理从而实现对物理系统的感知.由于网络的广泛应用,对这种类型的系统进行物理状态的估计与传统方法有许多不同之处.

由于网络环境的复杂性,比如网络带宽的有限性和网络的共享性,使得网络通信中总会存在不可靠性和不确定性.通常这些不确定性包括随机的延时、数据包丢失和测量失效.本文只考虑网络数据包丢包情形下的状态估计问题.对于该问题,文献[4]提出了一个用于间断观测的Kalman滤波器,对估计误差的统计收敛属性进行了研究,并且证明了在一定观测到达率下的存在性,而超过一定的阈值后误差将会发散.文献[5]从部分观测损失的方面提出了一种Kalman滤波,并且导出了适用于该情况下的滤波更新过程.文献[6]对数据包丢失进行了较为详细的描述与定义,并给出了一个考虑数据丢包的数学模型,基于这个模型设计了最优Η2滤波器.文献[7]将随机丢包率转换为系统中的一个随机参数,推导出了一种考虑随机参数和随机输入的通用Η∞范数滤波方法.在噪声是独立的时不变情况下,文献[8]设计了最优的全阶和降阶的状态估计器对具有数据包丢失的离散时间系统进行状态估计.文献[9]考虑了多数据包丢失的情况,并且在离散时间随机线性系统的框架下将这种情况转换为一个测量延时和滑动平均测量噪声,并且基于此设计了无偏的最优滤波器.文献[10]从概率角度考虑具有网络丢包的离散时间系统的状态估计问题.文献[11]从Markov链的角度提出了一个模型,该模型综合考虑了随机延时、数据包丢失和测量失效,并且基于此设计得到最优Kalman滤波器.文献[12]通过概率权值的方法得到了一个适用于具有多数据包丢失特性的非线性系统的非线性滤波器.文献[13]中将随机多数据包丢失假定为服从Bernoulli分布,并且设计了一种基于零均值高斯白噪声的Kalman滤波器.

尽管已经提出了很多关于网络数据包丢失的处理算法,但是大多数算法都不具有鲁棒性或者鲁棒性还不够,比如有些必须知道丢包率大小[12].当然也有一些具有鲁棒特性较好的算法,比如文献[6]和[7]中的算法,但是这两种算法的求解过程必须计算相对比较复杂的线性矩阵不等式(LMI)问题,尤其是当状态维数较大的时候,计算量会比较大,在实际应用中会受到一定的限制.即使是线性模型,当有数据包丢失时鲁棒状态估计会使得其变成一个非线性问题,也会造成算法的计算量上升.因此,为了在满足一定鲁棒性要求的前提下获得更高的计算效率,可以将鲁棒估计问题转化为具有更高求解效率的二次型规划问题(Quadratic Programming,QP)[14-16].

本文给出了一种网络数据包丢失情况下状态估计的数学模型描述,目的是将该鲁棒状态估计问题转化为向量优化问题,通过标量化方法将其转化为一个二次型规划问题.考虑到求解算法上的高效性,最后将该问题转化为l1正则化最小平方问题(l1-regularized least squares problem)求解.进一步加入动态更新过程就形成本文提出的基于二次型规划的鲁棒状态估计算法(Robust State Estimation Based on Quadratic Programming,RSE_QP).

1 问题描述

在状态估计过程中,首先要假定物理过程数学模型是已知的.通过这个数学模型,能够获得状态预测值.但是在实际的动态系统中,许多噪声信号会使真实的状态值与理论值不同.因此就需要一个对系统状态进行动态估计的滤波器,并且必须保证对系统噪声影响的鲁棒性.而其中最基本的思想是通过设计一个滤波器使得状态预测值与估计值之间误差最小,这样就能得到最优的状态估计.图1对状态估计原理进行了简单描述.

图1 状态估计原理图Fig.1 State estimation process

1.1 模型

式中:A∈Rn×n;C∈Rm×n;x(k)∈Rn是状态向量;y(k)∈Rm是量测输出;{w(k)}和{v(k)}是稳态、零均值离散高斯白噪声过程,w(k)~N(0,W)是输入噪声,v(k)~N(0,V)是量测输出噪声,其中W和V为对应的方差值.

当物理过程与滤波器之间存在网络环境时,数据包的丢失必然存在.上面的模型是无法描述这样的情况的.如果要将网络丢包考虑到数学模型中,必须对上面的模型进行一定的修正,使用文献[14]中类似的方法,可以得到下面的模型:

式中增加项u(k)∈Rm是为了描述网络丢包的.在这个模型中,u(k)的值是可以调整的,这样可以模拟网络丢包现象.在时刻k,当没有丢包时,u(k)=0;当有丢包时,u(k)的值可以使得y(k)的某些分量的值为0,即存在丢包.由于一般情况下网络丢包的概率相对比较小,所以可以假定向量u(k)是稀疏的.

1.2 问题转化

存在这样一个事实,当一个系统可观测时,必须通过量测输出y(k)来对系统的状态进行估计.为了使状态估计更加准确,除了要考虑状态误差,y(k)理论值与实测值之间的误差应该尽可能小.因此,当要对一个动态系统的状态进行准确的估计与跟踪时,必须考虑输出误差的衡量和状态误差的衡量.定义输出误差的目标函数为J1,状态误差的目标函数为J2.

根据文献[14],输出误差的目标函数J1可以表示为

式中:h为一个调整参数.

由于v(k)=y(k)-C′x′(k)

因此优化问题(6)可以被用来衡量输出误差的最优值.

在标准的Kalman滤波中,存在一个如下形式的状态更新过程:

其中xk|k-1是时刻k时的状态预测值,而xk-1|k-1是时刻k-1时的状态估计值.为了得到时刻k时的状态估计值,可以使用下面形式的目标函数来衡量:

其中Pk|k-1是时刻k时的状态估计误差的先验协方差矩阵.通过上面的目标函数,状态的估计值可以通过下面的二次型优化问题求解得到.

通过上面的讨论,如果必须同时考虑输出误差与状态误差两部分,即必须要获得这两个目标函数的最小值,这个问题就成为一个多目标优化问题,也是一种向量优化的问题[17].因此,考虑网络数据包丢失的鲁棒估计问题可以描述成一个向量优化问题.下面用相应的向量优化问题来近似描述该鲁棒状态估计问题,首先定义一个向量函数J,有

然后可以得到该鲁棒状态估计问题的向量优化表达形式

为了得到时刻k的状态估计值,必须在已经得到的时刻k-1的状态估计值xk-1|k-1基础上对上述向量优化问题进行求解,得到向量优化问题的Pareto最优值[17].必须指出的是,通过该形式获得的估计值无法从理论上证明其为最优估计值,只是一个近似最优估计值,但可以使得这个鲁棒估计问题在求解效率上有很大的提高.

2 RSE_QP算法

对于一个完整的状态估计与跟踪算法,必须包括当前时刻的状态估计与状态更新过程.其中当前时刻状态估计就是要对上述向量优化问题模型进行求解,首先要将向量优化问题转化为标量优化问题,然后对该标量优化问题求解最优值得到当前状态估计值.

2.1 标量化

有很多种方法可以对向量优化问题进行求解.而在这些方法中,标量化(scalarization)方法较简单也较实用.通过标量化方法可以将向量优化问题转化为一个普通标量形式的优化问题,并且可以得到该问题的Pareto最优值.下面是转化的过程.

式中:θ1和θ2可以被认为是在优化过程中目标函数J中两部分的权重值.定义λ=θ1h,可得

上述的向量优化问题(10)可以等价为下面的标量二次型优化问题.

2.2 更新过程

进行上述标量化过程以后,得到的优化问题(13)是一个典型的二次型规划问题.而对该二次型优化问题求解时,只能得到时刻k的状态估计值,相当于一个静态估计过程.如果要对一个动态系统的状态进行状态跟踪与估计,必须要有每个时刻的更新过程.本文借助标准的Kalman滤波更新过程来对每个时刻的状态误差协方差Pk|k和增益矩阵K进行更新,更新过程的方程如下.

状态预测方程为

状态误差协方差预测方程为

Kalman增益方程为

状态更新方程为

状态估计误差后验协方差矩阵更新方程为

2.3 优化问题求解

对于上述二次型优化问题,求解的方法可以有很多种.为了寻求一种效率更高,通用性更好的方法.本文通过一定的转化,使得求解变得相对直接并且高效.在本文中,优化问题(13)将转化为标准的l1正则化最小平方问题.

首先,定义

从公式(17)和(19)可以得到

根据式(3)

将公式(20)和(21)代入公式(12)中,目标函数可以做如下变换:

定义

可以证明Q是一个正定矩阵,下面是证明过程.

设存在任意的一个非零向量α,有

由于V和Pk|k-1都是正定的,因此

这样就得到Q是一个正定矩阵.对其进行Cholesky分解,可以表示成如下形式:

式中:M为上三角矩阵.通过公式(22)和(27),可以得到目标函数的描述.

通过上述变换,优化问题(13)已转化为一个标准的l1正则化最小平方问题.

使用一种截短牛顿内点法(truncated Newton interior-point method,TNIPM)[18]进行求解.

求解过程中,参数λ的值是用来设定向量u(k)的稀疏程度的,其值由数据丢包的多少决定.当没有数据丢包时,可以设定λ的值非常大;而当存在数据包丢失时,可以通过下面的方法进行自适应设定:

其中0<k<1,依据一定的经验,k的值应该要远小于1,在本文中设定k=0.01.

2.4 算法流程

通过上述讨论,当前时刻的状态估计可以通过求解相应的l1正则化最小平方问题得到,然后通过Kalman动态更新过程动态进入下一步的状态估计,以下是整个RSE_QP算法运行流程.

Step 1 初始化x0,P0|0=P0.

Step 2 当k≥1,根据公式(14),(15)和(16),计算xk|k-1,Pk|k-1,P-1k|k-1和K(k)的值.

Step 3 获得时刻k的测量值y(k),然后利用公式(19)计算e(k).

Step 4 利用l1正则化最小平方问题求解器求解优化问题(29)得到u(k)的值.

Step 5 根据公式(17)和(18)更新xk|k和Pk|k.

Step 6 让k=k+1,跳转到step 2.

3 仿真实验

为了验证本文所提出的对于网络数据包丢失的算法的有效性,本文分别给出了利用二阶和高阶(以四阶为例)离散线性时不变系统的模型对算法进行仿真实验.

3.1 二阶系统仿真

利用二阶离散线性时不变系统的模型对算法进行仿真实验,其数学模型形式如下[6]:

图2与图3分别是仿真过程中两个状态x1和x2的仿真结果.从图中可以看到,本文算法(RSE_QP)能够很好地满足估计和跟踪实际状态的任务,并且跟踪效果比标准的Kalman滤波(KF)好,表明本文算法体现出一定的鲁棒性,能够较好地处理具有网络数据包丢失的情况.

在图4中,使用状态误差的均方根(RMS)来评价估计结果,在每一时刻k,对状态所有分量进行计算得到其均方根.图5是在整个仿真过程中网路丢包的分布图.结合这两个图,可以看到当存在数据丢包时,本文算法估计过程中的误差均方根要远小于标准的Kalman滤波算法,反映了在具有丢包情况下本文算法的优越性.

通过改变仿真过程中网络丢包率的大小进一步验证本文算法的鲁棒性.图6显示了仿真实验结果,整个仿真过程中,设置了不同的丢包率,对于每种丢包率下都仿真100个时间间隔并且求取100个均方根的平均值得到仿真实验结果图.从图6中可以看出,随着丢包率的增加,平均均方根总体趋势是增加的,但从增长的速度来看,本文算法明显慢于标准的Kalman滤波算法,也反映本文算法是具有鲁棒性的.

图6 不同数据丢包率下的平均误差均方根(二阶)Fig.6 Average RMS under different network packet dropout(2nd order)

3.2 高阶系统仿真

利用四阶离散线性时不变系统的模型对算法进行仿真实验,其数学模型形式如下:

与二阶系统仿真类似,设定W=diag(1,1,1,1),V=diag(0.01,0.01,0.01,0.01),P0|0=P0=diag(1,1,1,1),x0=[1 1 1 1 ]T,参数θ1=θ2=1.其他仿真参数与二阶系统一致,并且丢包分布图也一致.同样在整个仿真过程中,将本文提出的算法与标准的Kalman滤波算法进行比较分析.

图7~10分别是仿真过程中4个状态x1,x2,x3,x4的仿真结果.从图中可以看到,本文算法针对高阶系统同样能够较好地进行状态的跟踪,在丢包的情况下可以看出本文算法能很好地平滑跟踪过程,较好地完成状态估计任务.

同样在图11中,使用状态误差的均方根来评价估计结果,在每一时刻k,对状态所有分量进行计算得到其均方根.同时,在图12中,改变丢包率,验证本文算法的鲁棒性.从图中也可以看出,对高阶系统鲁棒性也同样得到了提高,丢包率变化的干扰很小.

4 结论

本文考虑了网络数据包丢失情况下状态估计问题,给出了一种新的包含数据包丢失描述的模型,并且将此鲁棒状态估计问题转化为一个二次型规划问题,最终经过一定的转换利用标准的l1正则化最小平方问题求解器得到所要估计的状态.通过仿真可以看到,本文算法具有较好的鲁棒特性,能很好地进行动态系统的鲁棒状态估计,由于其属于二次型规划问题,容易实现,有较高的运算效率,因此具有较好的工程应用性.

[1] Hespanha J P,Naghshtabrizi P,Xu Y.A survey of recent results in networked control systems[J].IEEE Transactions on Automatic Control,2007,95(1):138.

[2] Zhang W,Branicky M S,Phillips S M.Stability of networked control systems[J].IEEE Control System Magazine,2001,21:84.

[3] Akyildiz I F,Su W,Sankarasubramaniam Y,et al.Wireless sensor networks:a survey[J].Computer Networks,2002,38(1):393.

[4] Sinopoli B,Schenato L,Franceschetti M,et al.Kalman filtering with intermittent observations[J].IEEE Transactions on Automatic Control,2004,49(9):1453.

[5] Liu X,Goldsmith A.Kalman filtering with partial observation losses[C]//43rd IEEE Conference on Decision and Control.Atlantis:IEEE,2004:4180-4186.

[6] Sahebsara M,Chen T,Shah S L.Optimal H2filtering with random sensor delay,multiple packet dropout and uncertain observations[J].Int J Control,2007,80(2):292.

[7] Sahebsara M,Chen T,Shah S L.Optimal H∞filtering in networked control systems with multiple packet dropouts[J].Systems &Control letters,2008,57(9):696.

[8] Sun S,Xie L,Xiao W.Optimal full-order and reduced-order estimators for discrete-time systems with multiple packet dropouts[J].IEEE Transactions on Signal Processing,2008,56(8):4031.

[9] Sun S,Xie L,Xiao W.Optimal filtering for systems with multiple packet dropouts[J].IEEE Transactions on Circuits and Systems—II:express briefs,2008,55(7):695.

[10] Shi L,Epstein M,Murray R M.Kalman filtering over a packet-dropping network:aprobabilistic perspective[J].IEEE Transactions on Automatic Control,2010,55(3):594.

[11] Moayedi M,Soh Y C,Foo Y K.Optimal kalman filtering with random sensor delays,packet dropouts and missing measurements[C]//American Control Conference.St.Louis:IEEE,2009:3405-3410.

[12] Chen J,Li J,Ma L.Nonlinear filtering with multiple packet dropouts[C]//International Conference on Image Analysis and Signal Processing.Hangzhou:IEEE,2010:83-88.

[13] Xu Y,Wang W.Kalman filtering for systems with multiple packet dropouts[C]//The 8th World Congress on Intelligent Control and Automation.Ji’nan:IEEE,2010:4996-5001.

[14] Fuchs J J.An inverse problem approach to robust regression[C]//IEEE International Conference on Acoustics,Speech,and Signal Processing.Phoenix:IEEE,1999:1809-1812.

[15] Borguet S,Leonard O.A sensor-fault-tolerant diagnosis tool based on a quadratic programming approach[J].Journal of Engineering for Gas Turbines and Power,2008,130(2):021605.

[16] Mattingley J,Boyd S.Real-time convex optimization in signal process[J].IEEE Transactions on Signal Processing,2010,27(3):50.

[17] Boyd S,Vandenberghe L.Convex optimization[M].Cambridge:Cambridge University Press,2004.

[18] Kim S,Koh K,Lustig M,et al.An interior-point method for large-scale l1-regularized least squares problems[J].IEEE Journal of Selected Topics in Signal Processing,2007,1(4):606.

猜你喜欢

估计值鲁棒性数据包
二维隐蔽时间信道构建的研究*
武汉轨道交通重点车站识别及网络鲁棒性研究
民用飞机飞行模拟机数据包试飞任务优化结合方法研究
荒漠绿洲区潜在生态网络增边优化鲁棒性分析
一道样本的数字特征与频率分布直方图的交汇问题
基于确定性指标的弦支结构鲁棒性评价
C#串口高效可靠的接收方案设计
2018年4月世界粗钢产量表(续)万吨
一种基于三维小波变换的鲁棒视频水印方案
2014年2月世界粗钢产量表