GA-BP混合算法

GA-BP混合算法（精选三篇）

GA-BP混合算法 篇1

随着数字照相机的广泛使用,如何提高图像滤波效果成为一个重要的研究课题。椒盐噪声是数字图像和视频传输中常见的一种噪声,目前已有许多去除它的算法[1,2,3,4,5,6,7,8,9]。常用的椒盐噪声滤波算法有标准中值(SM)滤波算法[1]、极值中值(EM)滤波算法[2]、递进开关中值(PSM)滤波算法[3]等。这些算法虽然对消除椒盐噪声取得了一定的效果,但在实际应用中都有各自的局限性。SM算法简单快捷,但降噪能力有限,会造成图像模糊;EM和PSM算法都是先进行噪声定位再滤波[4,5],保护图像细节能力提高,但对于严重椒盐噪声污染的图像滤波效果差。

BP网络具有较好的泛化能力,适合解决判断图像像素是否为噪声像素的分类问题,但是BP网格大多采用沿梯度下降的搜索算法,因而对初始权向量异常敏感,其解很容易收敛于局部极小点。遗传算法[6]是模拟生物界遗传机制进行优胜劣汰的随机搜索算法,具有很强的全局搜索能力,很容易得到全局最优解,较好地克服了BP算法寻优过程中易陷入局部极小值的缺陷。本文采用基于GA-BP算法[7]的噪声检测方法来对图像中的椒盐噪声进行定位,使该网络在噪声像素的检测方面获得较好的效果,减少了错误分类的像素数量,并通过仿真结果验证了其正确性。在滤波部分,引入保边函数来保留图像的边缘和纹理等细节信息,尽可能的减少图像模糊,最后利用PRP算法求出目标函数的极值进而实现图像的去噪处理。

1 基于GA-BP算法的噪声检测模型

1.1 BP网络结构

典型的BP网络有输入层、隐含层和输出层3层构成。由于图像像素样本数据复杂程度较高,本文在3层BP网络基础上,增加了1个隐层,采用四层结构的BP网络。其中输入层、输出层神经元的个数由研究对象的输入、输出信息来确定,分别取3和1,隐层神经元的数目通过实验方法来确定,采用包含两个隐层的3-5-3-1结构的神经网络模型。

该BP网络有三个输入向量,分别为中值滤波的输出值、邻域绝对值差分法和当前像素值。各个输入向量定义如下:

1.1.1 中值滤波

中值滤波采用窗口大小为3×3的标准中值滤波器,窗口通过光栅扫描方式扫描整幅图像。设xij是像素点(i,j)的灰度值,W3[xij]表示以像素点(i,j)为中心,窗口尺寸为3×3区域上的灰度分布,med(W3[xij])表示对窗口W3[xij]内的所有点排序然后取中值,若mij为像素点xij经过中值滤波后的输出值,则:

取mij为BP网络的第一个输入向量。

1.1.2 邻域绝对值差分法

近年来,Garnett[5]提出了一种通用的噪声滤波算法,文中指出ROAD值在区分噪声像素和信号像素时是一个很重要的因素。其中ROAD定义如下:

设x=(i,j)是当前像素的位置,Xx是以x为中心包含9个元素的像素的集合,其中排除中心像素x在外的其余像素的集合定义为

对每个像素y∈Xx(0),其中像素x和像素y的灰度值Ix和Iy的绝对差定义为

对八个sx,y的值按升序排序使得sx,y(r)≤sx,y(r+)1,r=1,…,7。将4个最小的sx,y累加,得:

ROAD值表示当前像素与其邻近像素值的接近程度。由上可知,对于噪声像素ROAD值较高,而对于非噪声像素ROAD较低。取ROAD作为BP网络的第二个输入向量。

1.2 遗传BP网络

遗传算法优化BP网络是利用遗传算法全局性搜索的特点,寻找最为合适的网络连接权值。利用遗传算法优化BP网络首先要确定编码方案,设X(x1,x2,…,xn)为网络各层间的连接权值按顺序排列成的一个向量,其中xi(i=1,2,…,n)对应网络中某一确定连线上的权值,采用实数编码方式对该组中的每个xi(权值或阈值)进行编码,从而产生一个染色体X,每个染色体表示成一个与解向量相同长度的浮点数向量。

其次是确定种群规模。实验中选择的参数为:种群大小M=20,遗传代数G=50。经过G代遗传操作后,将最优个体解码便得到优化的BP网络。

再则确定适应度。适应度函数是优化问题中的目标函数。以训练集样本对为网络的输入和期望输出,根据激励函数logsig()计算网络输出。运行后计算网络的学习误差,取其均方误差作为目标函数E(x):

式中:x为种群中的个体,N为网络输入样本个数,M为输出层节点个数,yj(k)、yˆj(k)分别为第k个样本输入时,第j个输出节点的期望输出与实际输出。BP网络的一个重要特点是网络的输出值与期望的输出值之间的误差平方和越小,网络性能越好。为了确保遗传朝着适应度函数增大的方向进化,定义适应度函数为

1.3 遗传算子设计

1)选择。采用最优个体保存法和轮盘赌法相结合的策略。先保留父代个体中适应度最大的个体,直接进入下一代,再利用轮盘赌法对其他个体进行选择。这样可以使最优个体不丢失,同时适应度低的个体也有被选中的可能,保证了个体的多样性。

2)交叉。具体做法是先使用选择算子在群体中选择两个父体X1和X2,对于两个父体,采用算术交叉,即

式中:X 1′和X 2′为子代个体,X1和X2为父代个体,α为(0,1)之间的实数。

3)变异。首先用选择算子选出父个体,对于选定的个体X(x 1,x2,…,xn),采用均匀变异的方式进行变异,即在个体X中随机地选择一个分量kx用xk′来代替,其后代为X′(x 1,x2,…xk′,…,xn),其中,xk′=xk⋅1(-r),r为(0,1)之间的一个随机数。

1.4 决策器

决策器将BP网络的输出(设为yF)和阈值0.5进行比较,其输出定义为式(9),当y(n)为1表示当前像素为噪声像素。

1.5 基于GA-BP算法噪声检测的求解流程

本文利用基于GA-BP算法的噪声检测方法来检测图像中的椒盐噪声。首先,利用遗传算法优化BP网络,从而寻找最为合适的网络连接权值;再利用训练好的BP网络对含噪图像的像素进行分类,其整个算法流程如图1所示。

2 基于保边函数和PRP的图像去噪算法

噪声检测部分将图像像素分为两类:一类是噪声像素点组成的集合N;另一类为信号像素点组成的集合NC。定义如下:

设Vi,j是与当前处理的噪声像素(不包含该像素)相邻的四个像素的集合,对于噪声像素点(i,j),与它相邻的像素(m,n)可能为信号像素,也可能为噪声像素,因此

图像去噪的实质是对凸函数fN(y)[8,9,10]求极小值,其中fN(y)定义为

式中:参数β是用来控制权衡两方面的,β∈[1,10],在此取β=2[8]。其中第一项保证那些被误检测为噪声像素的信号像素的灰度值不被改变,第二部分是一个保边函数[8,9,10,11],其定义为

边缘保护与噪声滤波是一对矛盾。在式(13)中,变量α如果取值太小,大部分噪声被滤除,但是边缘模糊;相反,α如果取值太大,虽然细节得到了很好的保护,但是噪声却很难完全滤除,本文参考文献[8]取α=1.3。

在此,运用PRP[12]算法求该保边函数的极值。设其梯度为g(y),迭代初始值y0为噪声检测后图像相应块的数值。则第k次迭代后的值为

式中:tk为第k次迭代的步长,pk(y)为第k次迭代的方向,定义为

其中由于图像的像素值为整数,因此,收敛条件为

式中∑N为该图像块内含噪声像素点的个数。

3 实验仿真与分析

在仿真实验中,采用Pentium(R)4 CPU 2.93 GHz,内存256 M,Win XP,Matlab7.0平台,给256×256的标准Lena灰度图像添加椒盐噪声得到受污染的图像,在噪声密度为0.8(严重椒盐噪声污染)时分别用SM滤波算法、EM滤波算法、PSM滤波算法和本文算法进行实验,实验结果如图2。

从主观上看,本文算法滤波后的图像质量是最好的,视觉效果几乎接近原始图像;同时,细节也得到了很好的保护,如Lena的眼睛。

在客观上,数值也作为重要的性能指标,表1给出了各种滤波算法的数值指标,其中各指标定义如下:

式中:xi,j和yi,j分别表示原始图像滤波突袭那个的像素值。

各种滤波算法滤波性能的比较如表1所示。从客观上,由表1可以看出,本文的基于GA-BP算法的噪声检测器的漏检率为0,误判率稍高,当这些误判的噪声像素形成块的时候,尤其是位于图像边缘附近,传统的中值滤波将会改变他们的像素值,造成图像边缘的严重模糊。本文引入保边函数可以确保在去除噪声的同时尽可能多的保留图像的边缘和纹理等细节信息;采用噪声检测和滤波相分离的方法滤除图像中的噪声,仅对检测出的噪声像素进行处理,而对信息像素点则保留其灰度值不变,在相同的噪声密度下,本文算法对应的PSNR值较传统滤波算法有不同程度的提高。

4 结论

本文利用遗传算法优化BP网络的权值,得到全局最优的结果,将其作为神经网络的初始权值,可以提高神经网络的泛化性能;利用基于GA-BP算法的噪声检测模型可以正确的检测出噪声像素,为下一步的滤波奠定了基础;在滤波部分,引入保边函数使去除噪声的同时尽可能保护图像的边缘和细节信息不丢失,进而减少图像模糊。最后通过多次实验表明,该算法自适应能力强,运算效率高,滤波效果好,能有效地滤除椒盐噪声,较好地保留图像细节,是一种有效的图像去噪方法,可以用于受严重椒盐噪声污染的灰度图像滤波或视频降噪。

参考文献

[1]Nodes T A,Gallagher N C.Median filters:some modifications and their properties[J].IEEE Transactions on Acoustics,Speech,and Signal Processing(S0372-2112),1982,30(5):739-746.

[2]XING Zang-ju,WANG Shou-jue,DENG Hao-jiang,et al.A new filteringalgorithm based on extremum andmedian value[J].Journal of Imageand Graphics(S1006-8961),2001,6(6):533-536.

[3]WANG Zhou,ZHANG David.Progressive switching median filter for the removal of impulse noise from highly corrupted images[J].IEEE Transactions on Circuits System II(S1051-8215),1999,46(1):78-80.

[4]谢剑斌,刘通,任勇,等.一种用于抑制椒盐噪声的自适应快速滤波算法[J].中国图象图形学报,2009,14(5):843-847.XIE Jian-bin,LIU Tong,REN Yong,et al.An Adaptive Fast Filtering Algorithm for Removal of Salt and Pepper Noise[J].Journal of Image and Graphics,2009,14(5):843-847.

[5]Garnett R,Huegerich T,Chui C,et al.A universal noise removal algorithm with an impulse detector[J].IEEE Transactions on Image Processing(S1057-7149),2005,14(11):1747-1754.

[6]McInerney M,Dhawan A P.Use of genetic algorithms with back propagation in training of feed-forward neural networks[C]//Proceedings of IEEE International Conference on Neural Networks,San Francisco,CA,USA,March28-April1,1993:203-208.

[7]王园宇,李元宗.基于GA-BP算法的基片图像边缘检测[J].计算机工程与设计,2009,30(14):3455-3457.WANG Yuan-yu,LI Yuan-zong.Edge detection of ceramic substrate based on GA-BP algorithm[J].Computer Engineering and Design,2009,30(14):3455-3457.

[8]Chan Raymond H,Ho Chung-Wa,Nikolova Mila.Salt-and-Pepper Noise Removal by Median-Type Noise Detectors and Detail-Preserving Regularization[J].IEEE Transactions on Image Processing(S1057-7149),2005,14(10):1479-1485.

[9]何坤,周激流,刘昶,等.基于局部保边函数的低信噪比图像去噪[J].四川大学学报:工程科学版,2009,41(2):179-184.HE Kun,ZHOU Ji-liu,LIU Chang,et al.Low-SNR Image noise removal based on local edge-preserving function[J].Journal of Sichuan University:Engineering Science Edition,2009,41(2):179-184.

[10]Leah Bar,Nir Sochen,Nahum Kiryati.Image Deblurring in the Presence of Salt-and-Pepper Noise[J].Lecture Notes in Computer Science(S1006-1630),2005,3459:107-118.

[11]Bogdan Kwolek.Detail-Preserving Regularization Based Removal of Impulse Noise from Highly Corrupted Images[J].Lecture Notes in Computer Science(S1006-1630),2007,4432:599-605.

软件安全中混合加密算法 篇2

目前，根据不同软件系统所应用的领域，比较常见的加密算法有DES加密算法、RSA加密算法、Base64加密算法和维热纳尔加密算法等。

针对不同算法的各自特点，本文首先自定义一种简单的初始加密算法，再对维热纳尔加密算法进行了优化改进，最后结合Base64加密算法共同组成混合加密算法，在很大程度上提高了加密算法的安全性。

2 基础加密算法

2.1 初始加密算法

初始加密算法是根据明文信息中的字符组成，再借助字符的ASCII码，进行相应的变换运算，从而使原有的真实信息进行伪装，避免被轻易的破解，提高了系统加密保护的安全系数。

在一般的软件系统加密过程中，组成明文信息的字符一般可以分为大写英文字母、小写英文字母、阿拉伯数字和其他特殊字符等四部分。

因此，在定义初始加密算法时，需要根据不同种类的字符进行一定的变换运算处理。

具体如下：第一类变换：明文信息的字符是英文字母时，明文在[A，M]范围内，密文为明文的ASCII码值加45;明文在[N，Z]范围内，密文为其ASCII码值加19;明文在[a，m]范围内，密文为其ASCII码值减19;明文在[n，z]范围内，密文为其ASCII码值减45。

第二类变换：明文信息的字符是阿拉伯数字时，明文在[0，4]范围内，密文等于明文乘以2再加1;明文在[5，9]范围内，密文等于明文乘以2再减10。

第三类：当明文信息是其他特殊字符时，密文与明文相同。

2.2 Base64加密算法

Base64加密算法主要的考虑了三个问题，第一为是否加密;第二为加密算法复杂程度和效率;第三为如何处理传输。

加密是必须的，但是加密的主要目的不是让用户发送非常安全的Email。

而是要达到一眼望去完全看不出内容就行。

基于这个目的加密算法，其复杂程度和效率也就不能太大或太低。

2.3 改进的维热纳尔加密算法

维热纳尔密码是一个非常著名的多码加密法，主要是通过采用定义好的维热纳尔方阵，以及自定义的密钥对明文信息进行加密。

以前对于维热纳尔方阵的定义，是通过以二十六个大写英文字母为依据，依次循环不断改变排列顺序，组成26×26级的方阵。

为了提高此算法的复杂度，同时提高保密性能，本文在二十六个大写英文字母的基础之上，再将十位阿拉伯数字随机插入到英文字母序列中，最终构建成36×36级的改进维热纳尔方阵。

在维热纳尔加密算法中，除了维热纳尔方阵之外，还需要明文字符集和密钥。

明文字符集主要是用来记录组成维热纳尔方阵所需要的字符。

密钥是用来在对明文信息加密过程中，指定字符所对应的加密字符。

因此，在改进的维热纳尔加密算法中，改进维热纳尔方阵、明文字符集和密钥，分别记为A、M和K。

改进微热纳尔方阵的明文字符集M定义为：

M={A，B，9，C，8，D，E，7，F，6，G，H，5，I，4，J，K，3，L，2，M，N，1，O，P，0，Q，R，S，T，U，V，W，X，Z}

密钥K定义为：

K={9，D，7，F，6，I，B，X，0，K，P}

因此，针对上述定义的密钥K，对明文信息字符串“HISENSE”进行加密变换，得到的密文是“ILY4UD7K49G”。

3 混合加密算法的设计

混合加密算法是在上述基础加密算法的基础上，由初始加密算法、改进优化的维热纳尔加密算法以及Base64加密算法共同组成的，并且其实现的过程必须按照固定的顺序依次进行，即先使用自己定义的初始加密算法，再使用改进优化的维热纳尔加密算法，最后使用Base64加密算法。

以明文信息字符串“chongq”为例，应用混合加密算法进行加密处理，具体的实现步骤如下：

第一步：字符串“chongq”经过初始加密算法之后，得到的加密字符串为“PUBATD”。

第二步：将改进优化的维热纳尔加密算法中的所使用的密钥K设定为：K={9，D，7，F，6，I}。

利用密钥K对字符串“PUBATD”继续进行加密处理，得出的加密信息字符串为“QZF7B3”。

第三步：使用Base64加密算法继续对字符串“QZF7B3”进行加密换算，得到加密字符串为“UVpGN0Iz”。

在计算机网络信息飞速发展的时代，信息加密算法已经成为研究软件安全的一个重要领域，取得了大量的研究成果。

本文中所设计的混合加密算法，是由三种加密算法组成的，也可以在此基础之上，再增加几种著名的加密算法或自己设计的新算法，只有跟随时代发展而同步进步的技术才有更广阔的的应用空间和更长的生命周期。

[参考文献]

[1]何茗.加密解密算法的实现及改进[J].西南民族大学学报(自然科学版)..1.

[2]徐荣峰.加密算法及其应用研究[D].西北工业大学..

[3]刘玉珍，王丽娜，傅建明，等，译.密码编码学与网络安全原理与实践[M].第三版，北京：电子出版社..

[4]佟晓筠，杜宇，等.基于软件安全混合加密技术的研究[J].计算机工程. 2004.12.

混合加密算法在物联网信息安全传输系统中的应用【2】

[摘 要]混合密码技术是一种新兴的密码技术，兼顾了对称密钥和非对称密钥的优点，表现除较高强度和速度，确保了信息传输的完整性、保密性、不可否认性。

随着信息产业的发展，传统的交流个体人、机器之间的通信已经不能满足日益发展的应用要求，用户呼唤一种人与各种事物间的，或是事物与事物之间的信息交流。

需求的迫切及计算机、网络技术的发展，促进物联网技术的诞生，该技术开启了人类社会信息化进程的新篇章。

[关键词]混合密码技术 物联网 信息安全

从体系架构上看，物联网分为三层。

其中，感知层存在安全性威胁，因为不论是普通节点还是汇聚节点都容易收到攻击，比如拒绝服务攻击，或是非法控制和破坏[I]。

试想一下，假设我们在系统的感知节点没有采取任何安全措施或安全防护不够全面的话 ，并且所感知的信息还涉及国家、军队的重要设施的敏感信息，一旦被非法的第三方获取，其损失是不可估量和弥补的。

通过分析我们得出，在感知节点可以采用硬件加密芯片、公钥基础设PKI和密码技术等安全技术手段来保证节点收集信息的安全三要素。

一、混合密码技术在物联网信息安全传输系统中的设计

按照物联网的三层架构设计，原始数据信息通过感知设备被采集，转发到采集终端，再进入安全系统进行敏感信息处理。

信息安全保密系统首先对转发过来的信息进行隔离处理后进入加密模块处理。

数据通过智能通信接口模块转发至网络层，再到应用层的智能通信接口模块，最终数据进入隔离、解密后被服务器接收。

物联网信息安全传输系统主要包括信息采集收发子系统、智能通信接口子系统、信息安全保密子系统。

其中信息安全保密子系统用于保证感知信息的传输安全;主要用于信息传输信道的选择和信息收发等。

主要包含由内、外网处理单元、网络隔离模块、信息加解密模块、身份认证模块。

二、 模型的`体系结构

基于物联网的信息安全传输系统中，由服务器、安全传输接口、单双向隔离通道、客户端组成的安全保密子系统。

服务器负责算法管理和密钥管理 ;数据传输接口和单向双向隔离通道负责加密数据发送的管理 ;客户端负责解密文件、传送公钥和更改密码。

模型的体系结构图如下：

三、混合密码技术在物联网信息安全传输系统中的应用

在实际的物联网通信系统中， 除考虑保密系统的安全性外，加解密速率、加密灵活性等因素。

部分物联网的信息安全传输系统采用硬件加密技术，虽说一次一密保证了信息的安全，但是额外的设备费用和硬件较高的故障率同时也给系统带来了其他的安全问题。

在对称加密算法中，公开密钥负责数字签名与密钥管理，私有密钥负责明文加密。

前面我们已经分析了AES和ECC算法， 在数字签名和密钥管理方面ECC 算法能够轻松的实现;而对于在较长明文加密中，AES 算法能提供更快的加密速度。

用MD5 算法辅助，因此综合运用 ECC算法和 AES 算法，再辅助于MD5算法就构成了本模型中混合加密算法的方案。

⑴密钥的产生

G为Ep(a，b)椭圆曲线上选的一个基点，其阶数为n(n是大素数 )，并且G(x，y)是公开的。

随机地确定一个整数(区间为 [1，n-1] )，k做为私有密钥，并计算 K=kG，K为公开密钥[5]。

⑵加密和解密

公钥加密：设 Ke 为 AES 的初始密钥，发送方在r上，r ∈ {1，2，…，n-1}取一随机数，计算 u=rKP(KP 为 B 的公钥 )，R1=rG，rG(x1，y1)，v=x1Ke，可以得到(u，v) ，发送给接收方。

至此实现对AES 算法密钥加密。

私钥解密：Ks 为接收方的私钥。

用私钥计算 R1=Ks-1u，得到 Ke=x1-1v。

⑶签名及认证

选取一个公开消息摘要函数，用MD5算法计算消息摘要 H(m)。

生成签名：发送方在区间{1，2，…，n-1)上，取L随机数。

计算R2=LG，LG (x2，y2)，e=x2H(m)，k1=L+eKS，w=k1G，可以得到(w，e) ，作为发送方的签名消息。

身份认证 ：计算 R=w-eKeP=(x1，yr)，则使 e=xrH(m)成立就是有效的签名，相反为无效的签名。

总之，混合密码算法结合了对称密钥和非对称密钥的优点，更易于加密和密钥分配，结合了AES算法和 ECC算法的混合加密算法具有易于理解和实现的优点，同时又兼具安全性高的优势。

在基于物联网的信息安全传输系统中，对数据信息来源的真实性进行鉴别，有效信息传输安全性的防护，从而保证系统资源的保密性、完整性与不可抵赖性等的基本安全属性要求。

混合密码算法集合了非对称密钥和对称密钥算法的特点与一体，具有运算速度快，安全性高和存储空间小的优势，更适合于物联网这样的一些受限环境中。

参考文献：

[1]苏逸.物联网发展存在的问题及前景[J].才智，2011，(22)：76-77.

[2]黄河明.数据加密技术及其在网络安全传输中的应用[D].厦门大学，.05.

GA-BP混合算法 篇3

关键词：软件容错；majority；median；表决；算法

中图分类号：TP3文献标识码：A文章编号：1007-9599 (2011) 06-0000-02

Hybrid Voting Algorithm Based on Majority and Median Voting Algorithm

Wang Yu

(School of Foreign Languages,Hunan University of Technology,Zhuzhou412008,China)

Abstract:In this paper,and the median combined with majority voting algorithm,the problem is well improved:the first use of majority voting algorithm to work,when there can not vote on the situation,dispersion calculations,if safety is less than a set threshold,Median voting algorithm is used to deal with this situation,if greater than the safety threshold,the output signal of a no vote.The final simulation shows:with majority voting system and the median is a feasible method to improve the voting system output accuracy;error rate although slightly increased,but the majority can not be output to improve the situation,while a certain degree of accuracy improved.The proposed voting algorithm can be applied to the need to improve output accuracy and can be appropriate to reduce the security applications,test results show that for continuous signals and discrete signals have good results.

Keywords:Software fault tolerance;Majority;Median;Voting;Algorithm

表决技术应用在很多领域中：表决系统可以结合分类器而广泛的应用于模式识别领域中。当然还有软件系统中通过容错配合多个专家系统进行共同协作解决问题，以提高可靠性。表决系统可用在分布式系统的人工排除问题中，比如，当集群工作站在因为网络问题等断开联系时来控制升级过程；

表决技术中具有安全性的典型代表就是majority表决，在n个模块中，有超过一半以上模块的数据结果相同，则输出较多模块都输出的结果。当少于一半的模块有一致结果，则输出一个无法表决的安全信号。

在需要实现安全性的应用中，majority是首选的安全表决机制，由于输出率较低，所以对majority进行修改。本文特点：使用majority的安全性来进行表决，对majority无法确定结果是正确或者错误的情况，使用median表决算法，这样能够通过median表决算法的强大选择能力进行数据输出，提高整个系统的有效性。

本文包括以下内容：首先介绍混合表决系统，之后在实验中与其他表决方法进行比较；最后再对本文中的表决系统进行性能评价及得出结论。主要评价的方面有：在测试中，表决的输出率及准确率。为了检验混合表决系统是否具有更优良的性能，我们进行了测试和测试的数据统计分析，从结果来看，相对于基本的majority模型有较好改善。

一、相关算法

应用算法是依赖于系统的设计，由于表决算法是基于诸如NMR/NVP[24]等系统，所以应用表决算法的过程是：首先建立NMR/NVP系统，系统中处理同一数据的模块共由n种不同实现方法完成。当输入数据后，n个模块分别处理，得到n个结果，交由表决算法处理。

（一）Majority算法

majority算法基于如下选择方法：对于某一个具体计算，如果有超过一半的模块有同一个输出数值，则输出该数值，否则输出无法表决的信号。可见该算法对于数据输出有安全性，即使用无法表决信号来通知系统应该进行暂停或者其他处理。

（二）median算法

majority算法基于如下选择方法：在奇数个模块组成的系统中，对模块输出的数据进行排序（通常是实数排序），选择处于正中间位置的那个数据作为整体的输出（如，对7个数排序后取第4个为输出）。可见该算法有百分之百的输出结果的能力，但是没有对系统通知暂停的信号。

二、混合表决

（一）结合majority和median

对于majority和median表决的特点经过分析后，可以发现两者的特性互有不同，但也说明两者特性具有互补性。本文中介绍的算法流程是，首先使用majority进行表决，之后对majority无法解决的数据进一步处理：对数据进行排序，如果最大和最小的数据间距超过某个范围，则输出无法表决，即安全信号，否则使用median处理majority的无法表决情况。

（二）算法流程

在实际使用majority表决算法时，通常使用一个边界极限的概念来确定数据间的一致程度：如果两个数据的距离在某个极限内，则认为两个数据是同一个数据。使用极限来确定数据的一致在数模、模数转换中很常见。

算法中涉及系统参数有：

t：应用majority时判断两个数据一致的极限

thres：MM的算法极限参数，数据离散度大于此参数，则输出安全信号，否则使用median进行表决

算法使用如下流程：

第一步：用V={v1 v2 v3 …vn}表示N个变量结果的集合

第二步：对V进行升序排序，排序后的集合为Vasc={va1 va2 va3 …van}

第三步：建立距离集合D，D={d1 d2 d3 …dn-1}，di=|vai+1–vai|，i=1，…，n-1.

第四步：如果D中至少有一个数据满足dj

第五步：如果D中没有数据满足djthres则输出无法表决，否则使用median进行表决输出

（三）算法表决举例

为了更好描述算法的机制，在表1中用数据示例说明，数据1和数据2及数据3都是由原始信号混合噪声后的待表决数据集，以模拟3模块冗余（TMR）情况。设定majority的极限为0.5，选用median的极限为2。在表一中，可以看到原始信号为2.0时，通过混合表决算法可以得到正确输出，而原始信号为1.5时，混合表决也仍能保持安全性，输出一个无法表决的信号。

三、结论

在连续和离散信号的测试中，结果表明，本文提出的MM表决算法相对于单纯的majority和median表决算法都有一定优势：相对于majority表决算法，MM能够提高输出率，这在对于安全性要求不是极其严格，并且需要较高输出率的情况是非常适合的，另外相对于median表决算法（median表决算法在测试中表现出与weighted value表决算法相似的性能），MM能够表现出较高的正确率和median所不具有的安全性，MM表现了majority和median的折中，即能够一定程度上保证安全性，又能输出较多结果。针对不同的系统和具体环境分析，若适合应用MM表决算法，则将比majority、median、weighted value等表决算法得到更好的输出。

参考文献：

[1]M. Ahammad and M.Ammar．＂Performance Characterization of Quorum-Consensus Algorithms for Replicated Data＂Proceedings of the 7th Symposium on Reliability in Distributed Software and Database Systems，1987:161-167

[2]Sherif Yacoub,Xiaofan Lin,S simske,J Burns.＂Automating the Analysis of voting Systems＂.Proceedings of the 14th International Symposium on Software Reliability Engineering.IEEE,2003:1071-9458/3

[3]F.Di Giandomenico and L.Strigini.＂Adjudicators for Diverse-Redundant Components＂.9th Symposium on Reliable Distributed Systems.Huntsville.Alabama.IEEE,1990:114-123

[4]T.K.Ho,J.J.Hull,and S.N. Srihari.＂Decision Combination in Multiple Classifier Systems＂.IEEE Transactions on PAMI,1994,16(1):66-75

[5]Li Shao-ming,Yin Qian,Guo Ping,Lyu Michael R.＂A Hierarchical Mixture of Software Reliability Model for Prediction＂.Applied Mathematics and Computation,2007,vol.185:1120-1130

[6]尹乾,李邵明,郭平.“软件可靠性分层模型的案例研究”.软件技术进展.梅宏,刘超.北京:机械工业出版社,2004:242-246

[作者简介]王昱（1981-），男，硕士研究生，湖南工业大学助教，研究方向：计算机。