一种基于粒子群算法的系统软防护组合优化方法

摘要

本发明一种基于粒子群算法的系统软防护组合优化方法包括以下步骤：按照系统功能将DSP、FPGA系统划分为N个功能模块；利用划分出的各功能模块，构造建立系统防护组合优化模型所需数据；根据划分出的功能模块以及得到的各功能模块的相关数据，建立系统防护组合优化模型；利用离散多目标粒子群算法对建立的系统防护组合优化模型进行求解，得到系统防护组合的一组最优解。本发明从系统角度对防护效果、防护代价进行了评估，以及对系统不同部位防护方法选择进行了优化，同可以用于指导DSP、FPGA系统中功能模块防护方法选择。

说明书

技术领域

本发明涉及一种基于粒子群算法的系统软防护组合优化方法，涉及针对 单粒子效应的DSP、FPGA系统防护组合的优化，可用于指导系统不同模 块防护方法的选择，属于系统可靠性领域。

背景技术

航天领域中的电子器件常常受会受到空间高能粒子的冲击而发生电路 逻辑状态的改变，这种现象被称为单粒子效应。单粒子效应会对航天器的安 全造成极大的威胁，因此人们对此十分关注。为了减轻单粒子效应对系统造 成的影响，需要对目标系统的不同部位进行适当的防护，但是，防护后往往 会带来额外的资源开销，因此，现有进行系统防护的做法大多为：首先，识 别出系统的脆弱点；然后，对系统的脆弱点进行防护。但是该做法存在下述 两点不足：1.虽然对系统的关键部位进行了防护，但是缺乏系统整体防护 效果和系统整体防护代价的定量分析；2.缺乏针对系统特定部位防护方法 的选择优化。

目前，有许多研究者对如何进行系统高效的防护进行了研究。例如，学 者Martin Hiller等人在IEEE transactions on computers上发表了文章 “EPIC:Profiling the Propagation and Effect of Data Errors in Software”， 文中提出的框架EPIC可以用于进行系统脆弱点的识别，从而在防护效果与 防护代价之间进行适当的权衡。但是这种方法缺乏从系统角度对防护效果、 防护代价的评估，以及对系统不同部位防护方法选择的优化。

发明内容

本发明的技术解决问题是：克服现有技术的不足，提供一种基于粒子群 算法的系统软防护组合优化方法，本发明通过各功能模块防护模型的建立和 整体分析，实现了系统级单粒子防护组合最优解的求解。

本发明的技术解决方案是：

一种基于粒子群算法的系统软防护组合优化方法包括步骤如下：

(1)按照系统功能将DSP、FPGA系统划分为N个功能模块；其中， 各功能模块通过信号传递互相连接，各功能模块为防护的基本单位，N为正 整数；

(2)利用划分出的各功能模块，构造建立系统防护组合优化模型所需 数据，所需数据包含如下：

(2a)构造功能模块M的输出信号错误发生概率矩阵P^M：

其中P^M(i,j)＝p_i,j^M表示在模块M输入信号全部正确、采用模块M所有 可用防护方法中的第i种防护方法的条件下，模块M内部发生一定数目的单 粒子翻转导致模块M第j个输出信号发生错误的概率；N^M表示模块M可用 防护方法总数；NO^M表示模块M输出信号总数；(对于DSP，常见的防护 方法有基于关键变量的LS-TMR方法、程序执行流程的跳转区间监测方法、 程序块三模冗余方法等；对于FPGA，有三模冗余方法、时间滤波冗余等)

(2b)构造功能模块M的输出信号错误传播概率向量Q^M：

其中Q^M(j)＝q_j^M表示在系统各个模块内部均不发生单粒子翻转的条件 下，模块M的第j个输出信号影响系统某一路输出信号的概率；

(2c)构造功能模块M的防护代价向量C^M，表示为：

其中C^M(i)＝c_i^M表示对模块M采用其本身所有可用防护方法中的第i种 防护方法时，模块M的防护代价；

(3)根据步骤(2)得到的数据建立系统防护组合优化模型；

(4)利用离散多目标粒子群算法对步骤(3)求出的系统防护组合优化 模型进行求解，得到满足系统输出信号出错率和系统防护代价最优的防护组 合，即求解一组Pareto最优系统防护组合最优解(Pareto最优解是根据 Pareto占优准则得到的一组互不占优的解集，并且该最优解集中的每个解 都不比求解空间中的其它解差)，使它们对应的f(k)为目标函数的最优取值。

所述步骤(3)中建立系统防护组合优化模型的具体实施方式如下：

(3a)根据各功能模块的输出信号错误发生概率矩阵P^M以及模块输出 信号错误传播概率向量Q^M，按下式计算系统某一路输出信号出错率E_sys：

其中N表示系统划分的功能模块总数；NO^M表示模块M的输出信号总 数；表示在假设模块M输入信号全部正确、采用模块M所有可用 防护方法中的第k_M种防护方法的条件下，模块M内部发生一定数目的单粒 子翻转导致模块M第j个输出信号发生错误的概率；q_j^M表示在假设系统各 个模块内部均不发生单粒子翻转的条件下，模块M的第j个输出信号影响系 统某一路输出信号的概率；

(3b)根据各功能模块的防护代价向量C^M，按下式计算系统整体防护 代价C_sys：

其中N表示系统中功能模块总数；表示系统中第M个模块采用其 可用防护方法中的第k_M种防护方法时的防护代价；

(3c)根据步骤(3a)中求出的系统输出信号出错率E_sys和步骤(3b) 中求出的系统整体防护代价C_sys，按下式构造系统防护组合优化模型：

其中k为系统防护组合(一个k表示一种系统防护组合)，取为 k＝[k₁,...,k_M,...,k_N]，并且k是由优化模型中两个目标函数f₁(k)和f₂(k)中的所 有自变量(k₁，...，k_N)构成的向量；其中k的第M个元素为k_M∈{1,...,N^M}, 表示模块M采用了其所有可用防护方法中的第k_M种防护方法。

所述步骤(4)的寻找最优解的具体实施方式如下：

(4a)根据步骤(3c)中求出的系统防护组合优化模型，将系统各个功 能模块的防护方法进行组合编码得到防护方法组合k，并将其与粒子群算法 的粒子相对应；

(4b)定义离散多目标粒子群算法相关参数；定义粒子群算法最大进化 迭代次数G；定义粒子自适应飞行参数以及ω；其中c₁表示粒子向个体 的局部最优解变化的权重因子，c₂表示粒子向全局最优解变化的权重因子， ω表示粒子向除个体历史最优及全局历史最优以外的位置变化的权重因子； c₁、c₂以及ω一起控制粒子位置的更新；定义内部种群POP中包含的粒子的 数目L，定义外部种群REP包含的粒子的最大数目H；定义空间超格对目标 空间各维划分的数目DIV；

(4c)初始化内部种群POP；

从步骤(4a)的系统防护方法组合中随机选出L个粒子作为内部种群；

(4d)评价内部种群POP；

根据步骤(3c)中求出的系统防护组合优化模型，计算各个粒子两个目 标函数f₁(k)、f₂(k)的值并将两者组合在一起作为POP中各粒子的适应值向 量，用于进一步根据Pareto占优准则评价内部种群POP中粒子对应的系统 防护组合方法的优劣；

(4e)初始化外部种群REP；

将内部种群中各粒子进行两两比较，并根据Pareto占优准则将内部种 群中对应非劣解的所有粒子复制到外部种群REP中，完成对REP的初始化；

(4f)初始化个体历史最优种群Pbest，所述的种群Pbest指保存了POP中 各个粒子当前探索到的个体最优位置，大小与POP相同；

将内部种群POP中的粒子依次复制到Pbest中，得到粒子群个体历史最优 Pbest，完成对Pbest的初始化；

(4g)更新内部种群POP；对POP中任意一个粒子k＝[k₁,...,k_M,...,k_N]进 行更新，更新的具体实现方式如下：

(4ga)从外部种群REP中目标空间稀疏的区域中随机选取一个粒子作 为粒子k的全局最优引导粒子，表示为：k^gb＝[k₁^gb,...,k_M^gb,...,k_N^gb]；

(4gb)从Pbest中取出粒子k的个体历史最优粒子，表示为：

k^pb＝[k₁^pb,...,k_M^pb,...,k_N^pb]；

(4gc)对粒子k中的任意一个元素k_M(对应模块M所选择的第k_M种防 护方法)，根据当前迭代次数t下c₁、c₂、ω的取值以及k_M与k_M^gb、k_M^pb的取 值是否相等，对粒子该元素k_M可以选择的各种取值赋予一定的概率权重向量 并使用轮盘赌的方法选择粒子k中该元素新的取值， 其中t＝1…G，r_i表示k_M取值为i的概率权重，即模块M的所有可用防护方 法中第i种防护方法被选中的概率；

(4h)根据步骤(4d)的方法重新评价更新后的内部种群POP；

(4i)更新外部种群REP

根据Pareto占优准则，将内部种群POP中各个粒子依次与外部种群REP 中的原有粒子进行比较，当内部种群中的某个粒子为非劣解时，将其插入外 部种群REP，同时删除外部种群REP中比该粒子劣的解；当向外部种群REP插 入一个新的粒子而外部种群REP满时，即外部种群中保存的Pareto最优解 的实际数目达到H时，首先利用空间超格提供的外部种群REP包含的粒子数 目信息，删除外部种群中位于目标空间密集区域的任意一个粒子，然后再插 入新的粒子；

(4j)更新个体历史最优种群Pbest；

如果内部种群POP中的某个粒子优于其在Pbest中的个体历史最优粒子， 那么使用这个粒子将Pbest中该粒子的个体历史最优粒子替换；否则，Pbest中 该粒子的个体历史最优粒子保持不变；

(4k)判断迭代是否结束：若未结束，则迭代次数加1并转步骤(4g)； 否则迭代结束，则将外部种群REP中的Pareto最优解导出，作为系统防护 组合的一组Pareto最优解，该解集可用于指导最终防护方法的选择。

所述步骤(4gc)中粒子k中元素k_M各种取值的概率权重的具体计算方 法如下：

(4gc1)概率权重向量计算分为四种情况：

(4gc11)当k_M＝k_M^gb＝k_M^pb时，R_M[k_M]＝1-ω，R_M其余元素取值为

(4gc12)当k_M＝k_M^pb,k_M≠k_M^gb时，R_M[k_M^pb]＝c₁，R_M[k_M^gb]＝c₂，R_M其余元 素取值为

(4gc13)当k_M＝k_M^gb,k_M≠k_M^pb时，R_M[k_M^pb]＝c₁，R_M[k_M^gb]＝c₂，R_M其余元 素取值为

(4gc14)当k_M≠k_M^gb,k_M≠k_M^pb时，若k_M^gb≠k_M^pb，R_M[k_M^pb]＝c₁，R_M[k_M^gb]＝c₂， R_M其余元素取值为若k_M^gb＝k_M^pb，R_M[k_M^pb]＝c₁+c₂，R_M其余元素取值 为

(4gc2)根据步骤(4gc1)求出的使用轮盘赌的 方法在集合{1,...,N^M}中选择k_M的新的取值。

本发明与现有技术相比的有益效果是：

(1)本发明根据系统输出出错率以及系统防护代价建立了系统防护组合 优化模型，从系统角度对防护效果、防护代价进行了评估，以及对系统不同部 位防护方法选择进行了优化，可以获取特定防护组合的量化评价方法，用于指 导DSP、FPGA系统中功能模块防护的选择。

(2)本发明对离散粒子群算法中粒子位置的更新方式进行了改进，引入 了自适应参数控制离散空间中粒子取值迭代的更新；使用该机制可以通过设置 自适应参数值从而更方便的控制粒子群对解空间搜索。

附图说明

图1为本发明流程图；

图2本发明使用的离散多目标粒子群算法中自适应参数的设置方法示 意图。

具体实施方式

下面结合附图对本发明的具体实施方式进行进一步的详细描述。

如图1所示，本发明一种基于粒子群算法的系统软防护组合优化方法， 包括步骤如下：

(1)按照系统功能将DSP、FPGA系统划分为N个功能模块；其中， 各功能模块通过信号传递互相连接，各功能模块为防护的基本单位，N为正 整数；

(2)利用划分出的各功能模块，构造建立系统防护组合优化模型所需 数据，所需数据包含如下：

(2a)构造功能模块M的输出信号错误发生概率矩阵P^M：

其中P^M(i,j)＝p_i,j^M表示在模块M输入信号全部正确、采用模块M所有 可用防护方法中的第i种防护方法的条件下，模块M内部发生一定数目的单 粒子翻转导致模块M第j个输出信号发生错误的概率；N^M表示模块M可用 防护方法总数；NO^M表示模块M输出信号总数；对于DSP，常见的防护方 法有基于关键变量的LS-TMR方法、程序执行流程的跳转区间监测方法、程 序块三模冗余方法等；对于FPGA，有三模冗余方法、时间滤波冗余等。

(2b)构造功能模块M的输出信号错误传播概率向量Q^M：

其中Q^M(j)＝q_j^M表示在系统各个模块内部均不发生单粒子翻转的条件 下，模块M的第j个输出信号影响系统某一路输出信号的概率；Q^M(j)＝q_j^M的确定方式：模块M有H种输入排列组合，其中对M输出信号j产生变化 影响的组合个数为H₁，其中H₁组合中使得输出信号j对系统某一路输出影响 组合个数为H₂，H₂与H₁的比值为错误传播概率。

(2c)构造功能模块M的防护代价向量C^M，表示为：

其中C^M(i)＝c_i^M表示对模块M采用其本身所有可用防护方法中的第i种 防护方法时，模块M的防护代价；防护代价指不同功能采用防护方法后， 不同功能模块的资源占用量相加得到系统总体的资源占用量；

(3)建立系统防护组合优化模型，具体实现方式如下：

(3a)根据各功能模块的输出信号错误发生概率矩阵P^M以及模块输出 信号错误传播概率向量Q^M，按下式计算系统某一路输出信号出错率E_sys：

其中N表示系统划分的功能模块总数；NO^M表示模块M的输出信号总 数；表示在假设模块M输入信号全部正确、采用模块M所有可用 防护方法中的第k_M种防护方法的条件下，模块M内部发生一定数目的单粒 子翻转导致模块M第j个输出信号发生错误的概率；q_j^M表示在假设系统各 个模块内部均不发生单粒子翻转的条件下，模块M的第j个输出信号影响系 统某一路输出信号的概率；任何模块的任意输出信号出现错误并传播到系统 的某一路输出信号，均会导致该系统输出信号出错这一事件的发生，因此为 了计算E_sys，首先计算系统输出信号正确这一事件发生的概率，然后用1减 去该概率；

(3b)根据各功能模块的防护代价向量C^M，按下式计算系统整体防护 代价C_sys：

其中N表示系统中功能模块总数；表示系统中第M个模块采用其 可用防护方法中的第k_M种防护方法时的防护代价；

(3c)根据步骤(3a)中求出的系统输出信号出错率E_sys和步骤(3b) 中求出的系统整体防护代价C_sys，按下式构造系统防护组合优化模型：

其中k为系统防护组合(一个k表示一种系统防护组合)，取为 k＝[k₁,...,k_M,...，k_N]，并且k是由优化模型中两个目标函数f₁(k)和f₂(k)中的所 有自变量(k₁，...，k_N)构成的向量；其中k的第M个元素为k_M∈{1,...,N^M}, 表示模块M采用了其所有可用防护方法中的第k_M种防护方法；

(4)利用离散多目标粒子群算法对步骤(3)求出的系统防护组合优化 模型进行求解，得到满足系统输出信号出错率和系统防护代价最优的防护组 合，即求解一组Pareto最优系统防护组合(Pareto最优解是根据Pareto占 优准则得到的一组互不占优的解集，并且该最优解集中的每个解都不比求解 空间中的其它解差)，使它们对应的f(k)为目标函数的最优取值；

(4a)根据步骤(3c)中求出的系统防护组合优化模型，将系统各个功 能模块的防护方法进行组合编码得到防护方法组合k，并将其与粒子群算法 的粒子相对应；

(4b)定义离散多目标粒子群算法相关参数；定义粒子群算法最大进化 迭代次数G；定义粒子自适应飞行参数以及ω；其中c₁表示粒子向个体 的局部最优解变化的权重因子，c₂表示粒子向全局最优解变化的权重因子， ω表示粒子向除个体历史最优及全局历史最优以外的位置变化的权重因子； c₁、c₂以及ω一起控制粒子位置的更新；其中，如图2所示λ、ω根据用户需 求进行设置，而c₁、c₂可由方程与c₁+c₂+ω＝1联立求解(此时λ、ω为 常数)；定义内部种群POP中包含的粒子的数目L，定义外部种群REP包含 的粒子的最大数目H；定义空间超格对目标空间各维划分的数目DIV(空间 超格技术为多目标优化算法中为保持解在目标空间中分布的均匀性而采用 的一种技术；对二维目标空间来说，空间超格将当前目标空间，即目前探索 到的，以(f₁^min,f₂^min)和(f₁^max,f₂^max)为对角线的矩形区域，划分为DIV×DIV的网 格)；

(4c)初始化内部种群POP；

从步骤(4a)的系统防护方法组合中随机选出L个粒子作为内部种群；

(4d)评价内部种群POP；

根据步骤(3c)中求出的系统防护组合优化模型，计算各个粒子两个目 标函数f₁(k)、f₂(k)的值并将两者组合在一起作为POP中各粒子的适应值向 量，用于进一步根据Pareto占优准则评价内部种群POP中粒子对应的系统 防护组合方法的优劣；例如假设k_A与k_B是系统防护组合优化模型的两个解， 当且仅当f_i(k_A)≤f_i(k_B)，并且f_j(k_A)<f_j(k_B)，则称k_APareto 占优于k_B；

(4e)初始化外部种群REP；

将内部种群中各粒子进行两两比较，并根据Pareto占优准则将内部种 群中对应非劣解的所有粒子复制到外部种群REP中，完成对REP的初始化；

(4f)初始化个体历史最优种群Pbest，所述的种群Pbest指保存了POP中 各个粒子当前探索到的个体最优位置，大小与POP相同；

将内部种群POP中的粒子依次复制到Pbest中，得到粒子群个体历史最优 Pbest，完成对Pbest的初始化；

(4g)更新内部种群POP；对POP中任意一个粒子k＝[k₁,...,k_M,...,k_N]进 行更新，更新的具体实现方式如下：

(4ga)从外部种群REP中目标空间稀疏的区域(选取的具体实现可以 借助轮盘赌方法：假设包含粒子的空间超格有n个，每个空间超格中粒子的 数目分别为s₁,…,s_n；首先计算每个空间超格被选中的概率为 然后产生一个[0,1]之间的随机数rand，如果 则第j个空间超格被选中，目标空间稀疏的区域 即指包含粒子数目较少的目标空间超格)中随机选取一个粒子作为粒子k的 全局最优引导粒子，表示为：k^gb＝[k₁^gb,...,k_M^gb,...,k_N^gb]；

(4gb)从Pbest中取出粒子k的个体历史最优粒子，表示为：

k^pb＝[k₁^pb,...,k_M^pb,...,k_N^pb]；

(4gc)对粒子k中的任意一个元素k_M(对应模块M所选择的第k_M种防 护方法)，根据当前迭代次数t下c₁、c₂、ω的取值以及k_M与k_M^gb、k_M^pb的取 值是否相等，对粒子该元素k_M可以选择的各种取值赋予一定的概率权重向量 并使用轮盘赌的方法选择粒子k中该元素新的取值， 其中t＝1…G，r_i表示k_M取值为i的概率权重，即模块M的所有可用防护方 法中第i种防护方法被选中的概率；粒子k中元素k_M各种取值的概率权重的 具体计算方法如下：

(4gc1)概率权重向量计算分为四种情况：

(4gc11)当k_M＝k_M^gb＝k_M^pb时，R_M[k_M]＝1-ω，R_M其余元素取值为

(4gc12)当k_M＝k_M^pb,k_M≠k_M^gb时，R_M[k_M^pb]＝c₁，R_M[k_M^gb]＝c₂，R_M其余元 素取值为

(4gc13)当k_M＝k_M^gb,k_M≠k_M^pb时，R_M[k_M^pb]＝c₁，R_M[k_M^gb]＝c₂，R_M其余元 素取值为

(4gc14)当k_M≠k_M^gb,k_M≠k_M^pb时，若k_M^gb≠k_M^pb，R_M[k_M^pb]＝c₁，R_M[k_M^gb]＝c₂， R_M其余元素取值为若k_M^gb＝k_M^pb，R_M[k_M^pb]＝c₁+c₂，R_M其余元素取值 为

(4gc2)根据步骤(4gc1)求出的使用轮盘赌的 方法在集合{1,...,N^M}中选择k_M的新的取值。

由于采用的是轮盘赌方法选择相对解结果占优的粒子k_M，因此在设该粒 子的R_M[k_M]时候，将取较大概率权重值赋予该粒子。如图2所示，根据ω、λ 变化关系曲线，随着迭代次数，该值呈现递减规律，同时再根据c₁、c₂的换 算关系，在专利中分别设置的占优粒子的R_M[k_M]取值是呈现递增规律，符合 设计原理。其它粒子权重和将是1-R_M[k_M]，虽然在此轮的迭代中这些粒子并 非被选中，但是下轮迭代粒子中可能有被选中，因此为这些剩余粒子赋予平 均概率权重，用于保证下轮迭代对剩余粒子可能被选中的机会均衡。

(4h)根据步骤(4d)的方法重新评价更新后的内部种群POP；

(4i)更新外部种群REP

根据Pareto占优准则，将内部种群POP中各个粒子依次与外部种群REP 中的原有粒子进行比较，当内部种群中的某个粒子为非劣解时，将其插入外 部种群REP，同时删除外部种群REP中比该粒子劣的解；当向外部种群REP插 入一个新的粒子而外部种群REP满时，即外部种群中保存的Pareto最优解 的实际数目达到H时，首先利用空间超格提供的外部种群REP包含的粒子数 目信息，删除外部种群中位于目标空间密集区域的任意一个粒子，然后再插 入新的粒子；

(4j)更新个体历史最优种群Pbest；

如果内部种群POP中的某个粒子优于其在Pbest中的个体历史最优粒子， 那么使用这个粒子将Pbest中该粒子的个体历史最优粒子替换；否则，Pbest中 该粒子的个体历史最优粒子保持不变；

(4k)判断迭代是否结束：若未结束，则迭代次数加1并转步骤(4g)； 否则迭代结束，则将外部种群REP中的Pareto最优解导出，作为系统防护 组合的一组Pareto最优解，该解集可用于指导最终防护方法的选择。

本发明说明书中未作详细描述的内容属于本领域技术人员的公知技术。