容错算法

容错算法（精选四篇）

容错算法 篇1

信息隐藏是将隐秘信息隐藏于其他掩护媒体而传输的一种保密通信方式[1,2,3]。文本信息隐藏技术是将具有特殊意义的文本隐藏在数字产品中,以有效解决文本信息的安全存储,传输及版权保护等问题。有效的隐藏技术一般要求具有较好的不可见性、鲁棒性、安全性及较大的隐藏容量[4]。数字图像因其包含大量的冗余信息使得隐藏的空间很大,从而成为信息隐藏的最主要的载体之一[5]。结合数字图像水印,可将本文算法看作一种有意义文本信息隐藏在数字图像中的技术,既隐藏了文本信息,又可当作一种信息量小,表达意义直观的文本信息水印。

针对文本信息的特殊性,即信息的任何一点误差将导致字符的改变,就可以使文本含义改变。如一个汉字在计算机内存储需要两个字节,即十六位二进制数编码,若二进制编码其中一位改变(0变1或1变0),这个汉字就不是原来的特定字符,而是另外的一个字符了。这样的改变在文本语义上是不允许的。故此需要对文本信息进行必要的预处理,以减小字符敏感性对文本语义信息的影响。同时考虑文本信息的安全性,本文采用的是对文本信息编码后的字符串进行复合混沌加密和纠错编码,以增加系统的安全性和抗攻击能力。且将文本信息冗余嵌入到原始图像的不同小波系数中,达到文本信息提取有鲁棒性。该算法在提取信息是不需要原始图像,属于一种盲算法。

1 文本信息的预处理

1.1 文本信息的编码

计算机系统并不能直接处理图形的字符,而是将每个字符先用对应的一个代码表示,系统显示该字符时通过其代码在系统的字库中查找该字符的点阵图。最初的时候,人们收录了字符并按照一定规则组成了一个字符编码的集合—ANSI(即美国通用标准组织,各项国际标准的制定者,包括ANSI文字编码标准)的ASCII码(美国信息交换标准代码),它使用7位(bits)来表示一个字符,如字符“a”的ASCII码为1100001,这样共能表示128(2的7次方)个字符,其中包括了英文字母、数字、标点符号等常用字符。

由于每种语言都制订了自己的字符集,导致最后存在的各种字符集实在太多,在国际交流中要经常转换字符集,十分不便。于是为了方便信息交流,人们又重新收录了字符集—Unicode[6],它为所有字符都分配了一个惟一对应的编码。此外还有区位码等不同编码方式,但对于多语种的中国Unicode码才是解决多民族文字编码之路[7]。而且对于跨国语言Unicode码也有很好的支持。

本文就采用了一种Unicode编码,它使得本文系统支持其他各种文字的信息隐藏。

实验用的文本“中南林业科技大学”经过编码后为“ 4E2D535767974E1A79D1628059275B66”。

1.2 容错设计

考虑到信息隐藏系统与通信系统的相似性,将文本信息隐藏问题等效为一个数字通信模型,从而应用数字通信中的信号编码理论和方法来改善系统的稳健性。隐藏数据对应要传输的数据,宿主图像对应隐藏数据的传输信道,攻击即通信信道的噪声干扰。该信道是高误码率信道,而通信理论中的纠错编码能够纠正信道中的误码[8]。

纠错编码方法有很多种,如BCH编码、RS编码、Turbo编码等。其中较简单且有效的是汉明码,因此采用了(7, 4)汉明码进行纠错编码。

设a0,a1,a2,a3是原始信息位;r0,r1,r2是监督码元,则它们满足如下关系:

$\{\begin{array}{l}r{}_0=a{}_0\oplus a{}_1\oplus a{}_2\\ r{}_1=a{}_0\oplus a{}_1\oplus a{}_3\\ r{}_2=a{}_0\oplus a{}_2\oplus a{}_3\end{array}$

原码和监督码元满足偶校验关系:

$\{\begin{array}{l}s{}_0=r{}_0\oplus a{}_0\oplus a{}_1\oplus a{}_2\\ s{}_1=r{}_1\oplus a{}_0\oplus a{}_1\oplus a{}_3\\ s{}_2=r{}_2\oplus a{}_0\oplus a{}_2\oplus a{}_3\end{array}$

上述的(7,4)汉明码可以纠正码组中的一位误码。

1.3 复合混沌序列加密

考虑到不仅要做到信息让人无法发觉,即使发觉也不能获取信息。所以在文本信息编码后嵌入之前引入加密机制,让其误认为为获取无用信息的双重保障。

并且由于容错设计中纠错编码的监督码元集中于各个数据码元的后部,具有较明显的统计规律,而且由于本文在文本信息编码的时候采用的编码方式是一种公开的方式,那么为了加强系统的抗攻击能力,系统破解需要一种具有良好加密特性的加密机制。

混沌现象是在非线性动力系统中出现的确定性的、类似随机的过程,这种过程既非随机又非收敛,并且对初始值有极其敏感的依赖性。通过混沌系统对初始值的敏感依赖性,可以提供数量众多、非相关、类随机而又确定可再生的信号[9]。混沌系统是一种复杂的非线性动力学系统,由于混沌具有良好的伪随机特性、轨道的不可预测性、对初始状态及控制参数极端敏感等特性,它在保密通信,图像加密等方面有广泛的应用。

本算法在(0,1)上的两个特殊的函数构造出一个复合混沌迭代系统[10,11],定义为,

$\begin{array}{l}f{}_q(x),q=0,1f{}_0(x)=\sqrt{|2x-1|}\\ f{}_1(x)=1-\sqrt{|2x-1|}\end{array}$

由此可以得到两个迭代函数,xn+1=fq(xn),q=0.1。通过两个函数互相迭代计算出来的一系列值经过一个非线性变换,可以消除它们之间的相关性。可以证明,经过非线性变换后得到的二进制序列具有独立同分布的特性,即意味着任何相邻的两位数据之间不存在相关度,不能通过统计特性分析从已知的某一位数据推算出下一位的值[12] 。

因为待加密的信息,可能是很不均匀的,引入一个近乎均匀的0,1序列与其进行异或运算,去“同化”待隐藏信息序列,使得到的最终参加隐藏运算序列是0,1近乎均匀分布的序列。

复合混沌序列加密后的均匀特性可以将原始码元和监督码元进行有效分离,以减小攻击对秘密数据的影响,同时由于并未改变数据的码元构成,故不影响系统的容错能力。

2 信息隐藏算法

2.1 图像的离散小波变换

离散小波变换(DWT)在信息隐藏和数字水印中的应用越来越广泛[13]。DWT方法不仅可以将图像分解到频域中,同时还保留了图像在空间上的分布,如图1所示。变换后的低频成分是图像的平滑部分,是对原始图像的最佳逼近,图像的大部分能量都集中在此,因此为了提高鲁棒性,常常在此区域嵌入信息。

本文采用的是基于提升格式的整数小波变换[14],该方法由Sweldens首先提出,整数小波提升在继承经典小波变换多分辨率分解特性的基础上,具有更为灵活和优良的性质,其所需的运算仅仅为整数加法和位移,因此运算速度大大提高。

2.2 文本信息的隐藏算法

①文本信息进行Unicode编码后二值化;

②将上述编码进行分组采用了(7, 4)汉明码进行纠错编码;

③将进行容错设计后的编码进行复合混沌加密;

④对原始载体图像(n×n)做小波变换,得到多个子带。由于不同频率子带抗攻击的能力不同,故将预处理后的数据重复嵌入不同子带可以分散攻击造成的影响;

⑤由于文本数据的特殊性,为了降低其各个字符间的相关性,将原始图像的低频部分和中频部分分别等分成大小为(8×8)的数据块,在每一个频带中根据密钥Key生成与字符个数一致的数据块标号;

⑥在以上选择的数据块中按量化中心极限定理[15]嵌入编码和加密后的隐藏数据。设预处理后的数据为w;

先用特定步长对选定系数进行量化:$Q{}_{\frac{{\rm M}}{2}\times \frac{{\rm N}}{2}}^{LL}(i,j)=$$\lfloor \frac{S{}_{\frac{{\rm M}}{2}\times \frac{{\rm N}}{2}}^{LL}(i,j)}{△}\rfloor$。其中,⎣」为向下取整符号。然后根据量化中心极限定理对量化后的系数进行调整:

若mod$\left(Q{}_{\frac{{\rm M}}{2}\times \frac{{\rm N}}{2}}^{LL}(i,j),2\right)=w(i,j)$,则调整后的载体数据为,

$S{}_{\frac{{\rm M}}{2}\times \frac{{\rm N}}{2}}^{LL}´(i,j)=Q{}_{\frac{{\rm M}}{2}\times \frac{{\rm N}}{2}}^{LL}(i,j)\times △+p\times △;$

若mod$\left(Q{}_{\frac{{\rm M}}{2}\times \frac{{\rm N}}{2}}^{LL}(i,j),2\right)\ne w(i,j)$,则调整后的载体数据为,

$S{}_{\frac{{\rm M}}{2}\times \frac{{\rm N}}{2}}^{LL}´(i,j)=\left(Q{}_{\frac{{\rm M}}{2}\times \frac{{\rm N}}{2}}^{LL}(i,j)-1\right)\times △+p\times △$,如果rem(x,△)<p×△;

$S{}_{\frac{{\rm M}}{2}\times \frac{{\rm N}}{2}}^{LL}´(i,j)=\left(Q{}_{\frac{{\rm M}}{2}\times \frac{{\rm N}}{2}}^{LL}(i,j)+1\right)\times △+p\times △$,如果rem(x,△)≥p×△;

其中,$S{}_{\frac{{\rm M}}{2}\times \frac{{\rm N}}{2}}^{LL}´(i,j)$为调整以后的系数,$i=1,2,\cdots ,\frac{{\rm M}}{2}$;$j=1,2,\cdots ,\frac{{\rm N}}{2}$

其中特定步长根据图像的纹、亮度等人眼视觉特征确定。

⑦ 逆小波变换,调整逆变换系数,由系数调整算子ξ将双精度实数改为无符号8位整数,得到隐藏信息的载体图像。

3 隐藏信息的提取

信息隐藏过程的反过程就可以提取出隐藏信息,具提步骤如下:

① 对待检测图像(n×n)进行整数小波变换,得到多个子带;

② 将低频部分和中频部分分别等分成大小为(8×8)的数据块,利用密钥Key在定位每一个频带中选择要提取信息数据的数据块号;

③ 然后用隐藏信息时的特定步长对选定系数进行量化:

$Q{}_{\frac{{\rm M}}{2}\times \frac{{\rm N}}{2}}^{LL}´(i,j)=\lfloor \frac{S{}_{\frac{{\rm M}}{2}\times \frac{{\rm N}}{2}}^{LL}(i,j)}{△}\rfloor$

④ 隐藏信息的提取方式可表示为:w′(i,j)=mod$\left(Q{}_{\frac{{\rm M}}{2}\times \frac{{\rm N}}{2}}^{LL}´(i,j),2\right)$。 其中w′(i,j)为提取出的所隐藏信息。

⑤ 将所提取信息数据进行解密;

⑥ 将解密后的信息进行纠错控制;

⑦ 最后重组所隐藏信息,译码后转化为文本信息显示。

4 实验分析

实验采用256×256大小的灰度图像Lena作为原始图像;采用“中南林业科技大学”作为欲隐藏文本信息。利用峰值信噪比(PSNR)作为图像的客观评价标准。

实验结果如图2所示,其中PSNR为41.308 8, 基本无视觉差异。在未受到任何攻击下,提取并恢复出的文本信息为“中南林业科技大学”。

实验结果表明,隐藏于图像低频子带中的信息,对于JPEG压缩、高斯噪声、低通滤波等攻击较高频要好,而隐藏于中高频子带的数据,对于直方图均衡化、伽码校正、图像增强等攻击比较鲁棒。因此,对于不同的攻击类型,可以有针对性的从不同的频率子带中提取信息,以期正确的结果。

从表1可以看出,该算法具有较强的鲁棒性。对于椒盐噪声攻击,在噪声密度不超过0.02 时,可以完全正确的提取文本信息;对于裁剪攻击,当裁剪的比例高达75%时,仍能完全正确的提取文本信息。

对应攻击效果如图3所示。

5 结束语

提出了一种新颖的文本信息隐藏算法,以有意义的文本信息作为隐藏数据,其信息量小无形中增大了可隐藏信息的容量,结合通信理论中的容错设计对数据进行纠错编码,并且通过混沌序列对数据加密,增强了信息隐藏系统的安全性。并结合小波变换,在承受不同攻击的能力表现不同的多频带隐藏,并且重复隐藏信息,提高了算法系统的鲁棒性。其又可当作一种信息量小,表达意义直观的文本信息水印。实验证明该系统对多种常见攻击具有较好的鲁棒性。

容错算法 篇2

目前嵌入式系统中最常关注的是瞬时 故障( transient fault) 容错问题,因为暂态故障会导致维护成本超90%[1]。安全至关重要的系统在遇到故障时需满足时限并正确运行,否则可能导致灾难性的后果。目前的实时任务调度算法,一般采用优先级配置调度,一般以经典的RM、EDF调度算法为基础,会假设任务间是相互独立[2,3,4],或者假设为周期任务[5],更偏向于理论性。而在考虑嵌入式系统本身运作时,调度任务需同时考虑任务的有序性以及任务间数据相关性,即,只有所有直接前驱任务都已完成,才能激活后继任务。DAG图[6,7,8,9]可以很好的实际描述出任务依赖性。基于DAG的调度一般采用列表调度,比如MCP、ETF、和BDCP就是三种经典的表调度 算法,是改进的 依赖关系 任务调度[10]。DBLF[11]是前三种调度算法的改进,不过采取的是启发式方法,虽然降低调度长度,但预测性不够好,不适用于系统设计。

为此,本文根据任务间依赖关系,提出一种基于DAG的容错调度算法FT - DAG。为具备更好的观察性和调试能力,选用BDCP优先级配置策略,本文的容错调度算法只对BDCP进行容错设计,是在同步节点处添加时间冗余,同步节点的定义在后面有相关规定,它在本文的功能是使同步节点的直接后继节点集具备相同的起始时间。

FT - DAG的优点。同步节点是指用有向图描述的节点任务集中,那些直接后继个数超过1的节点。而FT - DAG算法通过在同步节点处增加时间冗余,不仅能保障故障出现后系统在符合截止期的情况下,有足够的时间进行重执行容错,还可以保障同步节点前继任务,在出现瞬态故障的情况下,不对其后继节点的执行产生影响,特别是每个同步节点的冗余时间可动态释放,因为BDCP是动态计算每个节点的最早起始时间、最晚起始时间,因此在某个同步节点执行完毕,即其所有前继也都已完成后,可释放剩余的冗余时间,从而把后续的节点执行时间相应提前,减少调度长度,增大容错能力。本文通过一个实例和仿真实验进行验证。

1 系统模型

有向图中,关键路径通常起着非常重要的作用,基于关键路径的列表调度通常优于其它调度算法[12],本文构造的调度列表就是基于关键路径的。关键路径是DAG中任务开始结点到结束结点的所有路径中路径长度最大的路径,记为CP( CriticalPath) ,关键路径上的任务为关键任务,记为CPN( Critical Path Node) 。

故障出现后进行任务重执行,在目前容错应用、容错研究中被广泛使用[5,13]。本文添加可动态释放的冗余时间t的目的就是实现故障任务重执行,而不影响后续任务。图1中描述了t的大小,f表示V1- Vj出现的故障个数,u表示重执行响应时间。

2 任务模型

DAG任务模型中的节点表示任务,有向边表示任务间的依赖关系[1]。用G = { V,E,C,D} 表示。其中V = { V1,V2,…,Vi,…} 表示节点的集合,也就是任务的集合。E表示有向边的集合,是任务间优先级及数据依赖关系。Ci代表任务Vi的最大执行时间开销。Di表示截止期限。本文假设任务间的通信开销开销为0。如图2所示,为一个包含9个任务节点、12个依赖关系的DAG。根据任务依赖性,若要执行任务Vi,那么Vi必须在调度表已经就绪,且其所有前驱节点的执行已经完成,才激活Vi。

假设ind( vi) 表示节点Vi的入度,也就是其直接前驱节点的个数; outd( vi) 表示节点Vi的出度,代表其直接后继节点个数。ind( vi) = 0的结点为起始结点,也称祖先节点,标志调度的开始,如V1表示整个工程开始; outd( vi) = 0的结点为汇聚节点,记为Vsink,Csink= 0,是调度完成的标志。例如V5表示V5所有前驱节点集已经完成,直接后继节点集可以开始。

3 FT - DAG 容错调度算法

定义1把的节点叫做同步节点,表示方式是sV i( synchronous node,s V∈V) 。Vi和s Vi表示的是同一个节点,只是两种不同的命名,s V是同步节点集合,图2中用深色圆表示。

定义2某个同步节点的父亲节点,指的是从同步节点s Vi开始,逆序遍历,找到离s Vi最近的outd( vj) > 1的节点Vj,就说Vj是节点s Vi的父亲节点。根据定义及DAG性质,一个同步节点只能有一个父亲节点,但一个父亲节点可以有多个同步儿子节点。

定义3 pred( svi) 表示同步节点s Vi的前继集合,集合中包含其父亲节点Vj到s Vi以及s Vi本身的所有节点集( 其父亲节点Vj若未执行,也包含进来;否则,不包含) 。

同步节点的功能是,对于被定为同步节点的节点,其直接后继节点集具备相同的起始时间。这样,在同步节点s Vi处添加时间冗余后,pred( svi) 的执行不会影响后面的任务,提高了系统预测性、调试能力以及可观察性。

3. 1 调度策略设计

用FTScheduling Strategy( ) 表示容错调度策略,如图3所示。第1行是初始化调度表L,创建有向图; 第2行是分别采用顺序和逆序遍历的方式搜索出同步节点及与之相对应的父亲节点,s Vipred( svi) ;第3行是是指系统新建任务如果被分配了TCB或栈空间以及其他资源,并且具备运行能力后,就放入入就就绪绪调调度度表表LLss;; 第第44行行是是根根据据文文献献[[1100]]中中的的BBDD-CP调度算法给就绪任务集配置优先级,并规定在处理器获取了优先级最高的那个节点后,就把这个节点从调度表中移除,并动态计算剩下的节点集的ES( Earliest Start) 、LS ( Latest Start) ,再次进行BDCP配置。

如ES的表达式式( 1) ,其中j表示同步节点s Vi到其父亲节点有x个前驱结点,Vik为s Vi的第k个前驱结点。

第7、8行是指,如果同步节点准备就绪,就在对应的ES( sV i) 时刻插入冗余时间t,t的表达式见式( 2) ,其中f代表瞬时故障的个数。显而易见,根据t的表达式可知,t足够大来容忍pred( svi) 任务集中出现的f个故障。u为故障响应时间。

3. 2 容错调度算法

嵌入式实时操作系统中,调度是内核的主要职责之一,其主要任务就是决定资源空闲时,轮到了哪个任务运行。多数实时内核采用基于优先级调度的算法,并且每个任务总是具备三个状态: 等待、就绪、运行。图4是本文的容错调度算法FTDAGScheduling的具体描述。

如图4所示,优先级最高的节点开始执行后就从就绪优先级就绪表Ls中移除( 行2) ; 系统启动后,就绪表中至少已经就绪好一个任务,才开始调度,调度起始于任务中的祖先节点( 行3) ; 每个节点的最早起始时间总是在处理器空闲时计算获得( 行4) ; 如果正准备执行的节点是同步节点,就在此处插入冗余时间t,实现此同步节点之前任务在出现故障后仍不影响后面任务的执行( 行5、6,t的表达式见式( 3) ) ; 如果正在执行的节点属于某个同步节点前继集合,就一直执行8 - 9,直到pred( svi) 都已执行完毕,其中行9用递归的形式实现任务重执行,f为限定的递归次数,也代表每个pred( svi) 可容忍的故障数目; 行10释放剩下的冗余时间t',其表达式见式( 3) ,Vk代表出现故障的那个节点,并且后续将被执行的节点的起始时间都相应的提前t'; 调度的终止是直到调度到outd( vk) = 0的汇聚节点。

3. 3 实例验证

所举实例如图2所示,它的关键路径及最早、最晚起始时间具体计算方法见文献[14],这里不再重复。从图2可有,同步节点集合s V = { V5,V8,V9} ,pred( sv5) = { V1,V2,V3 ,V5} 。如果图2中的任务都准备就绪,那么初始状态如表1所示,实例中假设每个同步节点与其父亲节点之间的故障数目f = 1,其动态容错演示如图5所示。

从图5可知,步骤1为就绪任务优先级分配,冗余时间都是考虑出现一个瞬时故障的情况; 步骤2,先执行pred( sv5) ,占用添加的冗余时间重执行出现故障的V3,富裕的冗余时间为3个单位时间,意味着把优先级低于同步节点s V5的节点都相应的提前3个单位时间; 步骤3,冗余时间释放,记录新的起始时间,开始下一个同步节点s V8前驱集合pred( sv8)任任务务的的执执行行,,其其他他行行为为和和步步骤骤22相相同同;; 步步骤骤44,,释释放放上一个同步节点处的剩余冗余时间,继续执行; 步骤5,一直执行到汇聚节点,就表示整个调度的完成。

从图5的调度过程以及结果可以看出,FT DAG不仅实现了有依赖关系任务集的容错执行,其实际执行所用时间还会适当小于预设时间,验证了其好的容错能力和低容错开销性。

4 实验结果与分析

为了评估所提算法的可行性和有效性,本文以有依赖关系的任务图为背景,比较FT - DAG容错调度算法和FT - EDF容错调度算法。分析随着故障数目变化时,这两种调 度算法各 自的系统 容错开销。

容错开销用β表示,其中δFTDAG为FT - DAG容错调度时整个应用程序端对端的最大延时,δFTEDF为FT - EDF容错调度时整个应用程序端对端的最大延时,δBDCP为不考虑容错时整个应用程序的端到端最大延时。

因此图5中所举实例的容错开销的计算方式为:

对于生成依赖任务集,本文采用的是随机创建大小不一的时延进程,任务的大小由延时的大小确定,本实验随机创建包含V = 20、30、40、50、60个随机进程的DAG图,每种类型的DAG又生成5种依赖关系。分别比较故障数目f = 1、2、3时,各δ、β的变化。这时,一共产生75幅DAG图,比对统计次数为150次。

表2显示的是对应的容错开销平均值。可以看出,随着故障数目的增加,两种调度算法的容错开销都呈指数增长,且BDCP随着故障的增加,在f = 3时,可能导致任务的不可调度,此时δ > 1。对于FT - EDF,FT - DAG具备更短的调度长度,同样条件下,容错能力更优。

5 结束语

本文从嵌入式系统中不止有独立任务,还有有依赖关系的任务这一出发点,根据DAG的性质,以及关键路径调度算法的优势,在改进的关键路径调度算法BDCP上加入容错性能,实现实时系统容错能力。

本文用一个实例和仿真实验验证所提算法。结果显示,该调度算法因为同步节点的添加,大大增强了可观察性。改进的关键路径任务调度的采用,相比传统的动态EDF调度,大大缩小调度长度,减少了容错开销,并且,添加的冗余时间也是可动态移除,更进一步减少实际调度长度,提高系统容错能力。

摘要：首先针对任务间有依赖关系的任务,建立了有向图(DAG)任务模型;随后,采用动态关键路径调度策略BDCP(Better List Scheduling Algorithm)进行静态调度;最后是以BDCP为基础,在同步节点处添加可重叠的时间冗余,提出了FT-DAG(Fault Tolerant DAG)容错调度算法。同步节点是指DAG中那些直接前继个数大于1的节点。同步节点恢复技术具备容错、提升调试能力以及更少的容错开销。通过一个实例展现FT-DAG的调度过程,并把FT-EDFFT容错调度算法与之对比,验证所提算法的优势。

容错算法 篇3

关键词：无线传感器网络,虚拟骨干树,带宽聚类,故障容错路由算法

0 引言

无线传感器网络(Wireless Sensor Network,WSN)[1,2]已在环境监控、工业控制、医疗保健、军事用途、区域监控等领域得到广泛应用[3]。传感器节点在传感、计算和通信过程中会消耗能量,影响传感器网络系统的寿命[4,5]。因此,有效降低通信过程的开销和整体能量消耗非常重要。

文献[6]提出了一种故障节点容错算法(Vita Min算法),通过对数据包的跟踪为每个树节点找到到达汇聚节点的最短路径,利用一个集中和动态策略控制汇聚节点的移动性,增加网络的寿命。然而,在重要节点转换时,该算法不能形成完整骨干结构。文献[7]提出一种能量感知的虚拟骨干树(Energy Virtual Backbone Tree,EVBT),EVBT将一个广播请求数据包发送给其传感范围内的所有节点,接收到这个数据包的节点计算出这个数据包的适应度因子和时间延迟td,这个节点开始等待直到td到期。这个过程并不需要进行大量的计算,算法主要目的是减少能量消耗并增强网络的持久性,但是到达汇聚节点路由线路经常并不是最近的。文献[8]提出了改进的EVBT(m-EVBT)通过利用节点间的距离和能量消耗信息减少总的能量消耗,能量消耗信息用于识别上游的关系,而能量消耗信息是通过一个EVBT结构请求数据包进行传输,只有当节点所含有的能量大于阈值时,才考虑是否将其作为树节点,m-EVBT利用一个集中和动态策略可以控制汇聚节点的移动性,增加网络的寿命。文献[9]提出了一种节能数据聚集协议(EDGA),该协议通过将节点的剩余能量作为计算度量以达到减少能量消耗的目的,然而,在网络稳定性方面存在不足。

本文提出了一种基于带宽有效聚类结合随机虚拟骨干树的WSN容错模型(Bandwidth-Efficient Clustering and Random Virtual Backbone tree,BC-RVBT),采用移动汇聚节点选取树节点。根据树节点的适合度值将非树节点随机重新分布到所有合格的树节点中,有效解决了传统骨干树算法的问题,降低了总能耗,提高了WSN的使用寿命,具有较好的适应性。

1 带宽有效聚类

带宽聚类和RVBT树构建的共同目标都是减少总能耗和通信成本,带宽聚类减少了数据包总量,有利于构建骨干树。

网络模型是WSN中不同簇类{C1,C2,⋯,Cn}间的一个连接图G(V,E),含有异构节点和移动汇聚点[10]。模型如图1所示,每个区域中的簇头CH和多个节点用顶点集合‘V’和无线连接边‘E’表示。网络中的‘V’节点是随机分布的,利用多跳聚类算法将这些节点分配到‘n’簇类中。少量的节点‘h’(30~40 J)配置比一般节点‘u’(20 J)更高的能量。每个簇类中含有‘N’个节点,将∀u,h∈N节点作为簇类成员,利用这些成员生成固定尺寸的可变数据包。为了生成数据包,在CH上定义一个适当的压缩聚合函数[10]。

式中:Xi和Yj分别表示簇类中‘u’和‘h’节点生成数据包个数。函数所示为每个节点生成数据包的相关性,使用聚合函数的目的是:增加带宽利用率(簇类内部聚合),减少通信开销(成本)和最小化网络中的能量消耗率。

带宽聚类分为三个阶段:第一阶段,将随机分布的异构节点编入簇类的编号中,表示每平方区域中用于簇类内部和簇类之间聚合的CH;第二阶段,用CH对可变簇类成员生成的数据包进行聚合,生成的数据包的尺寸是固定的;第三阶段,每个CH作为一个独立节点进行簇类间的聚类操作,最后,汇聚节点通过减少数据包总量的方式对数据包进行聚合,从而减少通信成本。

2 虚拟骨干树模型构建

2.1 骨干树构建

带宽聚类后,簇类已经进行了聚类操作,在减少能耗和通信成本的同时,也为骨干的构建创造了更好的条件。图2为本文的骨干树系统,包含一个汇聚节点和传感器节点,将传感器节点划分为树节点和非树节点。树节点主要用于数据的感知、发送和接收,为了延长网络的寿命,利用最小的能量代价和最小的距离将非树节点发出的所有数据发送到汇聚节点。实验证明这样的骨干树可以减少数据包的能量消耗、增加网络寿命、没有快速的耗尽任何特定节点并维护了节点间的寿命。

传感器网络中的每个节点都含有一个可变能量级[11,12]。最初,所有能量级大于阈值(Th)的节点被暂时定为树节点。从汇聚节点开始通过连接所有合格的节点构成一棵树。如果一个树节点的能量逼近其阈值或拥有许多关联,那么这个节点会变成一个热点,由于热点要传输许多数据包,因此会很快耗尽能量。直接利用家属子树节点和相关的非树节点寻找一个新的父母树节点。一个节点只要拥有父亲节点,就不必去寻找一个新的父亲节点。算法1说明了每个树节点是如何找到可达树节点。

算法1:虚拟骨干树结构初始化

本文算法所用符号说明如下:Ni为节点i;TN为树节点;NTN为非树节点;RTN为可达树节点;Si为节点i的感知范围;Dependents为将一个节点的子树节点和相关的非树节点作为其家属;Th为一个树节点所需的最小能量或能量阈值。

2.1.1 为子树节点找到合适的父亲节点

当一个树节点希望重新分布其家属时,这个树节点指导其子节点去寻找一个新的父亲节点。子树节点对这个行为进行初始化如算法2所示。一个子树节点在其感知范围内扫描并找到了可达树节点的名单,如果在其范围内仅找到了一个节点,那么选取这个节点作为父亲节点;如果在其范围内找到了多个可作为父母的树节点,那么选取拥有最高适应度因子的节点作为父亲节点;如果没能发现一个合适的节点,那么这个子树节点仍然作为其先前父亲节点的子节点以维护网络正常运行。

算法2:一个子树节点选取新的父亲节点

2.1.2 为相关的非树节点找到一个父亲节点

对于每个非树子节点,找到的可达树节点都位于其感知范围内。在这些可达树节点中,选取最短上游距离的节点作为父亲节点。当节点Ni没有家属时,其变成一个非树节点,根据最小适应度值选取子树节点的父母,根据最小上游距离选取子非树节点的父母,如算法3所示。

算法3:非树节点选取新的父亲节点

2.2 骨干重构

当硬件发生错误或节点的能量完全耗尽时这个节点可能发生错误[12]。算法4对重构机制进行了介绍,树节点定期检查其能量是否低于Th,如果树节点的能量低于Th,那么这个树节点就变成一个非树节点。如果t表示一个失效的树节点,那么t的所有子树节点被分配给其他节点。一个子树节点在其感知范围内搜寻所有的树节点,选取其中拥有最高适应度因子的树节点作为其父母。如果这个子树节点感知范围内没有其他树节点,那么这个子树节点在其感知范围内检测所有非树节点。

算法4:重构骨干

3 随机虚拟骨干树

随机虚拟骨干树(RVBT)与虚拟骨干树很多部分都相同,如骨干构建与重构,不同的是虚拟骨干树仅选取含有最大适应度因子的树节点作为父亲节点[12],而本文根据适应度因子选取所有的树节点作为父亲节点。选取一个随机父母,根据权重函数,为发送到汇聚节点的数据包随机选取父母树节点,最初,利用式(2)计算汇聚点可达的所有树节点的适应度因子之和:

一开始对前者的树节点进行排序,在区间[0,sum]中随机生成一个数值,如果这个值位于区间[0,fitnessfactor(i,0)]内,那么选取树节点t0作为父母;如果生成的值位于区间[fitnessfactor(i,0),fitnessfactor(i,0)+finessfactor(i,1)]内,那么选取树节点t1作为父母。计算节点t被选为一个树节点父母的概率如下:

利用式(3)计算的距离可以完成选取过程。对于一个指定的非树节点j,有:

利用式(5)计算选取节点t作为一个非树节点父母的概率为:

本文一开始对节点进行部署时,大多数节点含有的能量大于能量阈值。用path(n)表示汇聚节点到节点n的路径,通过树节点对所有节点‘n’的路径进行定义。当节点距离汇聚节点很远时,利用单个虚拟骨干可能不足以进行覆盖。因此,在初始化构建虚拟化骨干后,一些汇聚节点较远的节点其路径path(n)为无穷大。根节点构造一个‘n’节点并再次建立一个虚拟骨干,于是形成了一些离散度虚拟骨干,在重建过程中,将一些非树节点转化为树节点,必要时可以将所有非树节点进行转化。如果设置的一个节点N的开销cost(N)过高,汇聚节点通过自身的更新采用其他的根节点和虚拟骨干,这样汇聚节点就能定期的访问节点N。当节点失效后,如果选取了许多新的根节点,那么相应形成新的离散结构,汇聚节点将定期访问这些根节点[13,14]。如果汇聚节点覆盖范围内存在多个破损,那么形成‘n’个非重叠组。因此对于汇聚节点来说至少存在‘n’个根节点为其收集数据,每个组中至少含有一个。根据N-of-N寿命概念[15],如果在部署区域中仅剩下很少的节点,那么网络中必须形成骨干。只要活跃节点的个数不为零,汇聚节点就持续收集数据并维护N-of-N寿命。

4 仿真实验与分析

在结合Mac/802.15.4的NS2仿真器[16]平台上对本文算法进行仿真,其目标是既能形成一个低数据率、低能耗和低成本的无线网络,又可以在设备层级上实现无线联通。

仿真实验在200×150平方单元的矩形区域内分别放置了100和200个节点(在某些对比实验中,放置更多)。如果一个树节点的家属数量过多,此时这个树节点的能量将会迅速耗尽,因此树节点的家属个数对树节点具有很大的影响,能量耗尽的树节点变成非树节点。为了避免这个问题的发生,树节点的家属个数必须保持最小。在BC-RVBT中,对每个树节点家属的个数进行隐式检查。

4.1 传输能量消耗比较

网络传输能量消耗是网络容错算法的重要评价标准。在每个节点上运行BC-RVBT中的所有模块,每个节点根据本文提出的算法将其状态从树节点变为非树节点。

在NS2中通过修改cc文件可以获取每个节点的能量耗损,当执行tcl文件时获取每个节点的能量耗损。通过网络仿真工具可以生成图形表示,仿真事件序列存储在跟踪文件内。当一个节点的能量低于能量阈值时,只能永远作为一个非树节点。在节点个数为100和200时,利用Vita Min[6],m-EVBT[8],EVBT CDS[12]和本文算法传送数据,对传送数据时总能量,消耗进行仿真,图3和图4给出了仿真实验结果。对于一级能量模型最优的传送范围为39 m左右,因此传送范围超过40 m后传感器节点的能量消耗将会增加,但是,增加传输范围将会消耗更多的电池电量。同时也可以看出,本文算法BC-RVBT总能耗最低。

4.2 恢复延迟比较

恢复延迟即故障恢复需要的平均时间是网络容错算法的重要标志,其定义如下:

式(6)中:dh为切换机制的平均延迟;di为动态干扰抑制时间延迟;k为邻居节点数量。

图5和图6分别为100个节点和200个节点的拓扑结构下几种算法的恢复延迟。随着故障节点数的增加,延迟也逐渐增加。由于可能存在距离超过3跳的故障节点导致同步故障恢复,因此降低了故障恢复延迟。同时延迟的增加与故障节点数目也相关,因为邻居节点变成故障节点的恢复机制以顺序方式执行。从图5和图6可以看出本文算法BC-RVBT平均增长斜率最小,即恢复延迟所需的时间最少。

随着节点数从100增加到200,延迟时间也随之增加。这是因为当节点数量增加时,故障节点的邻居节点也增加且恢复这些节点的时间也增加。然而,随着网络节点逐渐增加,本文算法故障恢复延迟达到一个常量。如图7所示,随着节点数增加,故障恢复延迟也增加,之后保持常量。随着节点密度的增加,故障恢复时间变为常量,因为故障节点可能存在更多的邻居节点且由于同步恢复使得延迟保持为常量;所以本文算法在恢复延迟方面具有更好的效果。

4.3 平均路由路径长度与家属节点方差比较

基于CDS的虚拟骨干通过计算跳的数量获取最短的平均路由路径长度。然而,家属节点的数量是一个非常重要的变量,能够导致树节点的失效并影响网络寿命。负载均衡虚拟骨干在所有树节点的家属数量中最小,但是获取的平均路由路径长度太大。本文提出的算法利用一个比负载均衡虚拟骨干短的路由路径长度,负载均衡骨干在某种程度上最小化了家属的个数。当发送一个信息时随机选取父亲节点,这使得家属分布更加合理。表1为基于能量、负载和距离的父亲节点请求式随机选取结果,这种机制有助于提高网络的寿命。

表1给出了平均路由路径长度和家属节点方差方面的比较,可以看出本文算法BC-RVBT路由路径最短,家属节点的方差最小。因此,本文根据随机化的权重函数给予所有的树节点相同的似然性,随机化权重函数在维持相同级别的能量消耗的情况下最小化重新分布,避免了含有较高适应度因子和能量间的频繁再分布。

5 结语

容错算法 篇4

保证系统正常运行的两大要素是故障诊断的准确性和实时性，因此，对于故障诊断与容错控制技术来说，近年来，人工智能的快速发展与应用，为动态系统在线辨识提供了一个重要的平台,尤其是Albus提出的一种模拟小脑学习机构的小脑模型关节控制器CMAC(cerebellar model articulation controllers)[6,7]，以其局部泛化和收敛速度的优势得到广泛关注,并在模式识别﹑智能控制诸多领域得到应用。

本文采用一种改进的基于信度分配的CMAC(ICA-CMAC)神经网络学习算法，利用其在线故障检测技术的优势，并且与容错算法相结合，实现系统的故障自我检测与排除能力。将仿真系统设置一定的参数，当其检测到故障时，启动在线故障评估器进行在线故障诊断，利用ICA-CMAC神经网络对故障信息的学习结果，将其整合到控制律算法中，利用故障信息重新构造控制信号。

1改进的基于信度分配的CMAC神经网络模型(ICA-CMAC)

CMAC的主要结构就是将学习的数据存储在存储单元中,每次输入将激活不同的单元格，其输出是这些激活单元中数据的代数和。常规CMAC是利用误差平均分配来调整权值的,根据误差的大小，将其按照平均分配的原则将其存储到NL个存储单元中，但是由于每个存储单元的学习过程都不一样，因此经过多次重复之后，他们有不一样的可信度。在常规的CMAC学习算法中。这一点没有考虑到这些可信度，产生“腐蚀”效应。

根据以上分析，将这些不同的单元格的学习过程分开对待，一种改进的基于信度分配的CMAC神经网络模型被提了出来[20]，给定一个参数，它代表学习的历史过程。单元格被更新的次数越大多，则表示存储在其中值越有可信度。相反的，更新的次数越少，则表示其可信度较低。更具体的算法说明见文献[8]。

2 非线性系统控制律重构与容错控制系统仿真

2.1容错控制器设计[8]

考虑如下未知的连续非线性故障系统，其离散模型可写为：

此处为状态矢量y(k)的已知非线性函数，Δt为采样周期，βi(k-Ti)为故障，Ti是发生故障的仿真时刻，fi(·)代表第i个故障。容错控制的目标就是在系统存在故障的情况之下，根据故障的大小，找到一个控制信号，使得系统回到原来预期的状态，而控制信号的大小又与故障的大小密切相关。一般说来，故障是未知的。在系统中设计一个阈值，一旦误差大于阈值则故障发生，将系统的实际输出数值与仿真系统的预期输出数值的差，作为ICA-CMAC神经网络在线辨识的预期输出值，也就是学习的目标函数，进行故障在线学习，如果误差小于阈值，表明在线辨识达到要求的精度，ICA-CMAC网络收敛。可用神经网络来近似故障,并且用一个容错控制律u2(k)可来代替正常的控制律u1(k)。

2.2容错控制系统仿真

为了进一步说明所提故障诊断与容错控制算法的有效性，在正常系统模型上加入未知故障，系统由以下方程表达：

其中令假定其为未知的故障，b表示未知增益。

式(2)中Δt=0.01,m=1,k1=100,T=50,c=5。动态故障模型的参数都为未知量。

参考输入：,期望输出：

ICA-CMAC的参数为：k=0.85,β1=1,NL=18，系统的仿真结果表明，系统在正常情况下，其输出与预期输出没有偏差，在系统发生故障时，在无容错控制的情况下，系统输出与预期的轨迹出现较大误差。当系统检测到故障之后，切换为纠错控制律u2(k)后系统的输出特性。切换控制律之后系统的性能得到了改善，在容错控制器成功地驱动未知故障系统回到期望的输出轨迹上。当故障被系统检测到后，初始化故障在线评估器在线辨识故障，同时切换为纠错控制信号u2(k)，开始时，由于ICA-CMAC网络刚开始学习，还未完全收敛，容错效果较差;但随着时间的变化，在大约30个周期之后系统渐渐回到期望输出的轨迹上来了。

从仿真结果可以看出，改进的基于信度分配的CMAC神经网络能即时准确地在线辨识系统故障，在此基础上应用故障评估器输出重构控制律成功驱动故障系统回到期望曲线，使系统稳定。

3小结

本文将CMAC的自组织竞争算法与基于信度分配的权值调整算法相结合，提出基于信度分配的CMAC神经网络故障在线学习算法，在此基础上实现动态非线性系统的在线容错控制，成功驱动故障系统回到期望曲线;对系统仿真结果表明，所提故障诊断与容错控制算法有较好的实际应用前景。

参考文献

[1]Patton R.J.,Fault-tolerant control:The 1997 situation(survey),Proceeding Of International Federation of Automatic Control(IFAC)Sym-posium.Fault detection,supervision,and safety for technical processes,Hull,England,1997,pp.1029-1052.

[2]Isermann R.,Schwarz R.,Stolzl S.,Fault-tolerant drive-by-wire systems-concepts and realization,Proceeding Of International Federa-tion of Automatic Control(IFAC)Symposium.Fault detection,supervision,and safety for technical processes:Safeprocess,Budapest,2000,pp.1-15.

[3]杨萍,张洪钺.基于双观测器的无刷电机闭环系统故障诊断[J].控制工程,2005,12(s1):183-186.

[4]Nikolaou N G,Antoniadis I A.Rolling element bearing fault diagnosis using wavelet packets[J].NDT&E International,2002,35(3):197-205.

[5]陈理渊,黄进.电机故障诊断的多传感器数据融合方法[J].电力系统及其自动化学报,2005,17(1):48-53.

[6]Albus J.S.,A new approach to manipulator control:The cerebellar model articulation controller(CMAC),Journal of Dynamic Systems,Measurement,and Control,1975,97(2):220-227.

[7]Albus J.S.,J.S.Albus,Data storage in cerebellar model articulation controller(CMAC),Journal of Dynamic Systems,Measurement,andControl,1975,97(2):228-233.