算法改进设计

算法改进设计（精选十篇）

算法改进设计 篇1

关键词：SIFT,图像匹配,特征点提取,图像处理

0 引言

图像匹配作为实现复杂的图像处理和视频处理的前提,是未来机器视觉处理技术发展的基础,在智能视频监控、机器人视觉、医疗手术、遥感测绘等领域有着非常广泛的应用,如何提高图像匹配速度和准确性将直接关系到整个机器视觉处理系统的效率和性能[1,2,3]。

目前,常用的图像匹配算法可以分为基于区域的图像匹配算法和基于特征点的图像匹配算法,其中基于区域的图像匹配算法由于计算复杂、效率低,往往不具备实用性[4]。而相对于区域匹配算法,基于特征点的图像匹配算法在处理过程中只需要对图像中的特征点进行处理和分析,因此极大地降低了图像匹配过程中的处理时间,计算时间复杂度极低,并且具有较高的匹配精度和可靠性,成为了目前应用最为广泛的图像匹配算法[5]。在基于特征点的图像匹配处理过程中,通常包括特征点检测、特征匹配、变换模型估计和图像重采样及变换等功能操作。具体地,特征点检测和匹配即是整个基于特征点的图像匹配的关键,而且又是图像匹配技术的应用前提,同时也已然成为当今图像处理技术领域的研究热点之一[6]。SIFT算法作为目前公认的最为理想的、普适性特征点提取算法,由其检测的特征点具有旋转、尺度、反射和光照等不变性,而且表现出极强的鲁棒性。但是该算法的时间复杂度却颇高,随着对智能视频处理速度的显著提升,使得强化完善SIFT算法的实时性和精准性,即已成为未来SIFT算法在复杂的图像处理系统中进一步拓展应用的研究攻关重点[7]。虽然目前国内外相关专家和机构都已根据自己的需求针对SIFT算法实施了一定的改进,如哈佛大学Ke等人提出的一种PCA-Sift算法通过降维技术有效地降低了SIFT算法的时间复杂度,但是同时也降低了角点检测精度,李晓明等人提出的改进的SIFT算法,主要根据遥感图像的处理特点进行提速,只是在遥感图像处理方面取得了较好的效果,但不适合其他图像处理,并且又降低了算法鲁棒性[8]。刘佳等人[3]用32维特征点描述向量,再运用欧式距离确定匹配点剔除误匹配点,提高了匹配正确率。刘辉等人[9]用Canny算子去除边缘点的影响,并配合以RANSAC方法消除误匹配,改进SIFT算法。冯政寿等人[10]用Harris算子结合张春美等人[11]的改进算法,以降低算法复杂度。综上可知,从目前图像处理技术相关应用领域对图像匹配处理的需求,以及已有的SIFT算法研究来看,在保证SIFT算法精度、鲁棒性的同时、优化提升基于SIFT算法的图像匹配速度则是今后图像匹配处理中亟需解决的核心焦点课题之一[12,13]。

结合这一背景需求,本文以SIFT特征点提取算法为基础,对其加入了合理改进,并基于Harris算法[14]提出了一种改进的SIFT算法以在确保sift算法鲁棒性和精度的同时提升其处理效率,对获得可观图像处理系统性能具有非常重要的现实意义。

1 相关理论基础

1.1 Harris算子

Harris算子是基于Morave算法的演化推理而来,其在图像匹配过程中的角点特征提取方面具有优秀强大的效率优势[15]。该算法中,角点检测的计算数学模型如式(1)所示:

式中,w(x,y)为高斯平滑因子,E表示在像素点(x,y)的地方移动一个(u,v)的窗口的亮度变化值,也就是与此像素点对应的一个梯度值,究其实质就是利用了图像二维信号的自相关的特点[16],并根据式(1)的原理,采用泰勒公式对其进行展开,同时忽略展开后的高阶项,就可以得到如下简化后的处理模型:

式中,Ix和Iy分别代表像素点(x,y)在水平方向和竖直方向的求导结果,根据泰勒公式展开后的简化模型可以看出,在该模型中每个像素点都有一个与之相对应的四元矩阵M,通过该矩阵就可以计算得到该像素点的相关的梯度信息。

基于上述简化后的数学模型,定义M的特征值为λ1和λ2,那么根据这2个特征值就可以得到相关的像素点的变化量,同时再通过定义相关的阈值,就可以根据特征值的大小对像素点进行分区,如果λ1和λ2都较小则判定其为平坦区域,一个较大、一个较小即确定其为边缘区域的像素点,否则可断定该点为角点,基于这一原理,就可以从图像中快速提取出相应的角点,具体计算模型如下:

式中,det表示矩阵M的行列式,trace为矩阵M的迹,k为系数,其取值通常设置在0.04~0.2之间,综上就是Harris算子提取角点特征的基本原理。相对于SIFT算子,Harris算子对角点的检测效率极高、检测的角点特征分布均匀,并且可以实现对角点特征的定量提取,但是抗噪能力却会略差,而且也容易受到干扰。

1.2 SIFT算子

SIFT算法作为目前图像处理领域公推的一种性能较好的算法,其检测精度和鲁棒性极强。基于SIFT算法的特征点检测是建立在多尺度分析理论基础之上,在应用SIFT进行特征点检测过程中,首先需要根据图像生成相应的参考图像和待匹配的图像的多尺度空间,在多尺度空间生成之后,再将不同尺度下的图像被检测出的局部极值点设置为后续进一步检测的候选特征点,同时通过提出低对比度和边缘相应点对该候选集合施行进一步的优化,其中在对特征点进行描述的过程中主要是计算出每个角点的主方向,而后就以角点为中心的圆形邻域为基础进行直方图统计,并根据直方图统计结果生成相应的特征描述因子,此后计算特征描述因子的距离,与预先设置的阈值进行比较,再次对候选集合加以进一步优化,最终确定候选匹配点,从而建立整合有匹配图像和参考图像的空间映射。

该过程中,多尺度空间的建立原理主要是构建一个高斯金字塔和高斯差分金字塔模型,具体如图1所示。

在尺度空间上进行局部极值点检测,将其加入到候选特征点点集合中,研究实现示意图如图2所示。

在SIFT算子中的特征描述重点是通过计算像素点(x,y)的梯度模值以及指示方向来提供定义的,其数学模型如下:

式中,L(x,y)为像素点(x,y)的尺度函数,m(x,y)为梯度模值,θ(x,y)为方向。

基于上述模型,在匹配的过程中就可以通过计算以特征点为中心的邻域的直方图,得到梯度方向的直方图,并且利用一个标准差σ为1.5L(x,y)的高斯噪声对梯度方向的直方图进行加权,如此处理后的像素点即已赋予了位置、尺度和方向3个信息;利用这些特征信息构建一个特征描述符,从而最大程度地保证其在光照变化、旋转幅度和比例缩放过程中能够保持不变性,最终实现具有极强鲁棒性的图像匹配。

论述至此,给出了就是基于SIFT算子进行图像精准匹配的完整过程,分析研究该过程发现,由于在SIFT算子中,设定特征是通过一个二维方向直方图来进行描述,获得了突出的刻画效果,但是处理过程也将趋于复杂,时间复杂度较高。

2 基于改进SIFT算法的图像匹配算法

2.1 图像匹配算法基本原理

综合上述对SIFT算法基本原理的展开分析,可以得到利用SIFT算法进行图像匹配的基本流程如图3所示。由图3可知,整个图像匹配包括特征点提取、特征点匹配、变换模型估计和图像重采样与变换4个过程。具体地,在特征点提取的过程中主要是建立多尺度空间(即高斯金字塔和高斯差分金字塔)和进行尺度空间的极值点检测;特征点匹配主要是利用BBF算法进行像素点搜索,同时构建出特征点之间的欧式距离关系模型,再通过设置阈值来判定参照比较而确定候选匹配特征点集合,并利用Opencv提供的RANSAC算法对特征点集合完成进一步优化,得到精确的特征点集合,实现精准匹配;变换模型的估计过程主要是利用变换模型来描述匹配图像和待匹配图像之间的变换关系,并且计算出相关的模型参数;图像重采样与变换主要是采用插值算法对变换后的图形进行插值,最终完成2个图像的精准匹配。

2.2 SIFT算法的改进

结合前文对Harris算法的原理分析,其在角点特征检测上相对于SIFT算法具有明显优势,在算法结果上表现出更好的实时性和更高的算法效率。因此在改进SIFT算法中,本文采用Harris算法进行角点提取,也就是将SIFT算法的角点提取使用Harris算法实现。同时,为了有效提升SIFT算法的效率,本文重点采用了主成分分析方法对其进行数学降维处理,就是在SIFT处理过程中找出一些综合变量来替代原来的复杂变量,限制前提是保持彼此之间的数学关系和变换关系恒定不变;处理过程中主要是利用仿射变换模型来近似地建立了SIFT匹配过程中的图像变换表示,同时利用RANSAC算法进行误匹配点检测和提取,深度提升其匹配精度,使得改进后的SIFT算法可以在获得较高匹配精度的同时,又极大地提高算法的效率。改进后的SIFT算法的实现流程如图4所示。

3 实验结果及分析

基于前文改进的SIFT算法和未改进的SIFT算法的原理,研究中采用opecv2.0开发库构建图像匹配系统,对本文设计提出的算法进行测试,测试结果如图5所示。通过图5可以看出,改进后的SIFT匹配算法得到的结果与原算法结果保持一致。同时仿真结果指出,改进后的算法得到的匹配特征点为218个,而原算法为421个,匹配的特征点虽然减少,但是匹配的特征点却更加均匀精确,如此即使得匹配时间大大降低:改进后的算法匹配时间提升了42 ms,只需要12 ms就能快速地实现匹配。

为了完善研究结论,文中继而设计给出了基于改进后算法而获得的图像拼接效果,如图6所示。可以看出,改进后的算法在提高效率的同时,也可以保持较高的匹配精度和准确性。

4 结束语

算法改进设计 篇2

改进遗传算法在桁架结构优化设计中的应用

文章针对简单遗传算法的早熟现象及不能处理带有复杂约束的`优化问题,提出了一种基于乘子法与伪并行遗传算法的改进遗传算法,并将其应用于桁架结构优化设计中.计算结果表明改进遗传算法全局寻优能力强.

作 者：施雷 王琦 张文鹏 SHI Lei WANG Qi ZHANG Wen-peng 作者单位：南昌航空大学航空与机械工程学院,江西,南昌,330063刊 名：南昌航空大学学报(自然科学版) ISTIC英文刊名：JOURNAL OF NANCHANG HANGKONG UNIVERSITY(NATURAL SCIENCES)年，卷(期)：200923(1)分类号：V214.1 V214.19关键词：乘子法 伪并行遗传算法 结构优化设计

算法改进设计 篇3

关键词:谐波分析 神经网络 遗传算法 MATLAB

中图分类号:TM1文献标识码:A文章编号:1007-3973(2010)06-083-02

随着现代工业科技的发展,电力电子装置的应用越来越广泛,非线性和时变性电子装置大量投入到电网使得电力系统中的非线性负荷急剧增加,导致了配电网中电压和电流波形的严重失真,由此而产生了电网谐波污染问题,谐波的产生降低了电能质量,直接影响工业用电设备和居民用电设备的正常安全运行。另一方面随着科技的发展,各种精密仪器的投入使用对电能质量提出了更高的要求。谐波问题作为降低电能质量问题的核心内容对电力系统的安全经济运行带来了巨大的挑战 。

对谐波含量准确进行分析计算时保证谐波治理效果的重要前提,本文采用遗传算法改进神经网络算法进行谐波含量计算,其实时性和结果精确性都有较大提高。

1谐波含量计算问题

原始理想的电压和电流波形应该是标准的正弦波波形, 可以假设电源瞬时电压为

考虑到负载电流发生畸变,含有谐波分量,根据傅里叶级数将负载电流分解为:

其中,为基波有功电流;为基波无功电流;为高次谐波电流,可以将式(2)改写成权值模式:

对谐波含量的分析计算目标即为求出的值,其中体现高次谐波的含量 。实际电网中由于电力系统为三相系统,偶次谐波基本消除,因此只考虑奇次谐波,占总谐波含量97%以上的谐波集中在25次谐波以下,本文只分析25次以下(包括25次)奇次谐波含量,根据以上分析,式(4)可以简化成

其中 谐波分析即为求取式(5)中权值系数 的值。

2基于神经网络谐波检测算法

本系统采用单层感知器—误差修正学习法 。由式(5)可知,神经网络谐波权值计算可用如图1所示,作为网络的输入,为理论电流:

为实测电流值,也就是期望电流值,为期望电流值与网络实际输出之差,即误差信号:

误差信号为驱动控制信号,其目的是修正调节各次谐波权值,使网络输出一步一步接近期望输出 ,这一目标通过最小化性能指标来实现 ,性能指标定义如下:

权值修正法则如下:

其中表示第n个输入量第k+1表示第次迭代后结果,为学习率,为学习误差,为第n个输入向量。

综合以上分析可知,采用单层感知器-误差修正神经网络的谐波算法计算步骤如下:

(1)给定初始谐波权值

初始权值赋值可采用在规定区间内的随机赋值法,初值赋值区间为[-2,2]。

(2)给定当前输入

由前面分析可知为神经网络输入,输入量在不同的时刻t不同,因此必须建立查表机制来查询不同时刻的网络输入,用表示第n次迭代中第个输入量( 的顺序依次编号)。

(3)由权值和输入量计算网络输出值

(4)根据网络输出和期望输出计算学习误差,如式(7)所示。

(5)根据学习误差调节权值

其中表示第次迭代中第n个输入量的连接权值

(6)回到2继续进行下一次迭代计算

基于单层感知器-误差修正学习网络最大的优点就是迭代过程相对简单,最后系统能稳定收敛到目标范围。但系统的稳定性受系统反馈参数影响较大,学习率的选取对于系统重复学习过程中的稳定性和收敛性是非常重要的,的值过大,会加快收敛速度但误差过大,的值过小,学习速度过慢,也将影响系统实时响应速度。

3遗传算法改进神经网络算法

上一节中提到的单层感知器-误差修正神经网络是一种简单的寻优算法,但神经网络权值寻优算法存在全局搜索能力差的缺点,初始权值随机性过大影响网络的泛化能力,而遗传算法可以对复杂的,非线性的、多峰的不可微函数实现最优全局搜索,能有效利用历史信息来推测下一代更优质的寻优点集 。这样不断进化,最后收敛到一个最适应环境的个体上,进而得出问题的最优解。因此,可以先用遗传算法对初始权值进行优化,在大范围解空间定位出适用于优化目标的较好搜索空间,然后利用神经网络在这一个较小解空间进行局部寻优,这样既可以避免在寻优过程陷入局部最优,还可以加快算法收敛。据此本文将遗传算法与单层感知器-学习修正神经网络算法进行结合来优化谐波含量计算。遗传算法进化步骤如下 :

第一步:确定决策变量和约束条件

包括基波权值在内,一共有13组,总共有26个权值,谐波权值的范围一般在[-1,1],权值可能溢出,本文将权值范围扩大到[-2,2],即:

第二步:建立优化模型

优化目标为使得性能指标到合理范围

第三步:确定编码、解码方法

对于每一个权值其取值区间为[-2,2],由于遗传算法计算目的为搜索最优区间,而非最优解,因此将[-2,2]区间以0.2为单位分为20等份,计算最终目标只需求出最优解所在区间即可,可知每个权值从-2到2有21个取值可能,可用4位二进制编码串表示,一共有26个权值,按照的顺序需要104位二进制编码串来表示,这便构成了染色体编码方法。解码时先将104位的二进制编码串截成26段4位二进制编码串,每一段编码串表示一个权值编码,设某一段编码为,解码后表示权值实际值为,可知

第四步:确定个体评价方法

可知个体评价方法即为性能指标控制到合理范围。

第五步:设计遗传算子

选择运算选用比例选择算子;交叉运算使用单点交叉算子;编译运算使用基本位变异算子。

第六步:设定遗传算法运行参数

包括群体大小、终止代数、交叉概率和变异概率

结合前面神经网络算法的分析,可得出遗传算法改进神经网络算法计算谐波的总计算流程,如图2所示:

4MATLAB仿真分析

根据前面对算法的分析,使用MATLAB提供的神经网络和遗传算法工具性进行仿真处理 。设置遗传算法群体大小为80,终止代数为100,交叉概率为0.7,变异概率为0.001,神经网络算法学习率为0.1,使用遗传算法改进神经网络算法的训练样本曲线如图3所示,单独使用神经网络算法的训练样本曲线如图4所示:

由图3和图4可知,采用遗传算法改进神经网络算法进行谐波分析,在遗传算法完成100步迭代后适应度最高样本的训练误差已经降到,此后进行神经网络训练到160步后训练误差已经降到,相比单独使用神经网络算法,需要到350步训练误差才能到,可见采用遗传算法改进神经网络算法大大加快了迭代速度和计算结果的准确性。

5遗传算法改进神经网络算法的优点

使用遗传算法改进神经网络算法为谐波计算分析提出了新的解决思路,主要特点包括:(1)全局搜索能力强,算法精确度高 。(2)抗干扰能力强.。(3)自适应能力强。智能算法进行谐波分析作为一种新兴的谐波分析思路,但是由于智能算法对于训练样本的依耐性非常大,算法参数的设置对于整体计算精度和效率影响非常大,现场应用不够,因此还需作更为深入的探索研究。

注释:

吕润如. 电力系统高次谐波[M].北京:中国电力出版社,1998.

危韧勇,李志勇.基于人工神经元网络的电力系统谐波测量方法[J]. 电网技术,1999,23(12):20-23.

焦李成.神经网络计算[M].西安:西安电子科技大学出版社,1993.

危韧勇,李志勇,李群湛.一种基于ANN理论的谐波电流动态检测方法研究[J]. 铁道学报,2000,22(1):40-43.

陈国良,王熙法,庄镇泉,王东生.遗传算法及其应用[M].北京:人民邮电出版社,1999.

王小平,曹立民.遗传算法-理论、应用于软件实现[M].西安:西安交通大学出版社,2002.

常巍,谢光军,黄朝峰.MATLAB R2007 基础与提高[M].北京:电子工业出版社,2007.

一种改进的AODV路由算法设计 篇4

Ad Hoc网络在特殊环境中具有重要的应用潜力, 路由协议是Ad Hoc中最重要的技术。在Ad Hoc中, 路由主要分为表驱动式路由、基于约束的路由[1]和按需路由等。AODV是按需路由中最重要的一种[2], AODV路由协议是一种按需距离向量路由协议, 在该协议中, 网络中的每个节点在需要进行通信时才发送路由分组, 而不会周期性地交换路由信息以得到其它所有主机的路由。AODV协议具有距离向量路由协议的一些特点, 即各节点路由表只维护本节点到其它节点的路由, 而无须掌握全网拓扑结构。它通过使用目的节点序列号, 实现无环路由, 并且避免了无穷计数的问题。为了避免单向链路引起的错误操作, 协议引入了一个黑名单, 把和自己是单向链路的邻居节点放入黑名单中。

在AODV协议中, 当源节点要发送数据包到目标节点的时候, 如果在自己的路由缓存中没有找到这个目标节点的路由, 那么该节点就会发送RREQ分组启动路由发现过程。传统的AODV路由在网络拓扑结构改变后, 有链路修复性能差、数据传输延迟大、路由重建时间长等缺点。基于以上的这些缺点, 本文提出了一种改进的AODV路由协议 (B-RTAODV) 。目的是使AODV更适用于网络拓扑变化快的环境, 能在链路中断后迅速找到可用路由。

1B-RTAODV协议

B-RTAODV路由协议在路由发现过程中, 并不像传统的AODV协议那样只找到一条到目标节点的路径, 就丢弃其它的路由信息。它采用了备份路由的思想[3]: (1) 源节点和目的节点间建立多条路径, 并依据跳数决定这些路径的优先级;当源节点发送数据时, 选择具有较高优先级的路径进行通信, 当主路由 (即优先级最高的路由) 中断时, 选择次高优先级的路由通信。由于源节点和目的节点间存在多条路径, 当主路由中断时, 能选择次优路径通信, 减少了重找路由的开销; (2) 路径中每个节点的路由表里需要保存路径中下两跳邻居节点的信息, 当链路中断时, 断路的上游节点尝试在两跳范围内修复; (3) 通过在B-RTAODV的Hello信息中, 加入邻居节点的信息, 来维护路径。

B-RTAODV需要在原AODV中进行改进的地方:

(1) 路由结构中添加优先级字段, 表示备份路由的候选顺序;

(2) 拓展原RREQ、RREP、HELLO封包格式及路由表结构;

(3) 目的节点添加定时器, 当收到第一个RREQ时启动定时器, 对其后一段时间内的RREP都要回复;

(4) 改进链路中断后的处理, 第一条链路中断后, 判断当前是否有可修复路由, 有则修复路由。没有则使用备份路由, 并提高该备份路由的优先级。

1.1主路由的选择

B-RTAODV路由协议在路由发现过程中采用了备份路由思想:保存源节点和目的节点间的多条路径, 其中一条为主路径, 其余为备份路径, 主路径和备份路径依据优先级高低区分。主路径优先级最高, 值为1, 第一备份路径优先级次之, 值为2, 以此类推。优先级高低根据路径跳数来决定。

1.2目的节点缓存机制

为有效对比源和目的节点间的多条路由, B-RTAODV路由协议改进了原AODV的路由机制, 即在协议中取消中间节点回复RREQ的功能 (通过设置RREQ协议帧中的D和G标识位) , 同时在目的节点处添加RREQ缓存。当目的节点收到第一个RREQ时, 启动RREQ缓存定时器, 在其后一段时间内缓存收到的所有RREQ。当定时器超时, 比较RREQ携带的路径信息, 根据主路由选择机制为每条路径附上优先级, 并发送RREP回复每条路由。这样, 当源节点收到所有的RREP后, 源节点和目的节点间将建立好按优先级排序的多条路由。缓存的RREQ数目最多限制为N, 即仅保存最优的N条路由。

目的节点缓存RREQ比源节点缓存RREP更实用, 当目的节点按照缓存RREQ的优先级回复RREP时, 路径中的转发节点将会知道路径的优先级。

1.3备份路由相关性问题

备份路由的相关性问题较复杂也难以解决。所谓相关性是指:源节点和目的节点间建立的多条路由中有相同路径。显然, 如果某链路中断时, 将导致相关路径同时失效。因此, 在多路径路由中, 要尽量避免路径相关问题。

完全解决路径相关问题是很复杂的, 在随机网络环境中, 往往绝对独立的多条路由是很难找到的。在B-RTAODV中, 借鉴AODV的原有机制和改进目的节点的处理方式, 在不引入额外开销的情况下, 尽量避免备份路径的相关性。简单描述为:

(1) 延用AODV的路由建立过程, 当中间节点收到RREQ时, 将记录RREQ的广播ID号, 如果先前已收到相同的RREQ, 则丢弃该分组。这样, 保证每个节点只转发一次RREQ;

(2) 在目的节点处, 仅回复来自不同上一跳节点的RREQ。

1.4协议操作

与传统的AODV路由协议相比, B-RTAODV在路由建立、路由维护、路由中断处理与路由恢复等方面进行了改进。

(1) 路由建立

源节点有数据发送时, 查找自己的路由表, 如果当前没有找到目的节点的路径, 则发送RREQ查找路由。在广播RREQ以前, 源节点在PATH_DISCOVERY_TIME时间内缓存RREQ ID和RREQ发起者的IP地址。以这种方式, 若节点再从它的邻居那里收到同样的RREQ报文, 它将不对此进行重新处理和转发。RREQ ID和发起者的IP地址联合起来标志一个独一无二的RREQ报文。

为比较源节点和目的节点间的多条路径, 在改进的AODV中, 取消中间节点回复RREP的机制。即便中间节点有到目的节点的路由也不回复RREP, 由目的节点统一回复。

目的节点收到第一个RREQ时, 将启动RREQ缓存定时器, 缓存其后一段时间内收到的来自同一源节点的所有RREQ。目的节点缓存的RREQ定时器超时, 将根据主路由选择机制计算每个RREQ对应路径的优先级, 并根据优先级高低依次回复RREP。RREP中携带对应路由的优先级rt_pri。中间节点收到目的节点回复的RREP, 将建立到目的节点的路由, 并记录RREP中携带的路径优先级rt_pri。源节点收到目的节点回复的RREP, 建立到目的节点的路由, 并记录路径优先级。当源节点收到目的节点回复的所有RREP时, 建路过程结束。

自此, 源节点和目的节点已建立好带有优先级的多条备份路由。路由建立后, 源节点选择优先级最高的路径发送数据。

(2) 路由维护

主路由以及备份路由的维护与AODV原有机制相同。采用定时发送hello分组的做法确认相邻节点间的链路。一般通过链路层通告或者向下一跳发包时使用被动确认方式监听信道中下一跳是否在尝试发送数据。

(3) 路由中断处理

对于原AODV, 路由中断后, 将启动重新找路过程。在改进的AODV中, 由于保存了多条路径, 当主路由中断时, 只要源节点和目的节点间仍存在其它路径, 不发送RREQ重新找路, 选择次优路径通信。只有当源节点和目的节点间的所有可用路径均中断时, 才发送RREQ重新找路。

(4) 路由恢复

路由修复由链路的上游节点负责, 若节点发现正在使用的路由, 在本节点与下一跳节点之间出现故障。节点将根据路由信息, 并结合两跳范围内的节点信息, 进行路由修复。如图1所示, 路由A-B-E-D-F在链路B-E处断裂, 节点B将负责路由修复, 节点B根据路由信息, 知道到目的节点F的路由的下两跳为节点D。于是, B从管理的邻居节点信息中, 寻找一个B和D的公共邻居节点C。找到后, 节点B修正到F的路由, 将下一跳节点E用C替换, 并将路由有效期更改为链路B-C的生存期。然后, B就用修正后的路由转发分组。C收到分组后, 如果它有到F的有效路由, 则用自己的路由转发分组;如果没有有效路由, 则将分组转发给节点B在分组的“下两跳节点”域中说明的节点D。D收到分组后, 继续转发。

2性能仿真分析

基于NS2, 本节对改进的B-RTAODV协议进行性能分析。在以下仿真分析中, 本文将备份路由数目为2、3时的B-RTAODV性能与AODV相比较。在图示中, 分别以B-RTAODV2、B-RTAODV3来表示备份数为2和3的情况。为求仿真结果的普遍性, 以下仿真的每种场景进行了10次仿真, 求取平均值。

网络环境 30个无线节点均匀分布在一平面矩形区域内 (1200m×400m) , 仿真时间500s;应用层采用cbr业务源, 数据分组大小恒为512字节, 业务流发送速度为1packet/s;节点移动模型为NS-2自带的random waypoint模型, 节点暂停时间为0s;节点移动平均速度为3m/s。

2.1分组投递率

从图2可看出, B-RTAODV2和B-RTAODV3的分组投递率比AODV低, 因为B-RTAODV采用了RREQ缓存机制, 其找路时延将高于AODV, 找路过程中会导致部分数据包丢失。但是两者差异仅为1%个数量级, 可以说B-RTAODV虽然引入了备份路由机制, 增加了协议复杂度, 但是并未较大降低AODV的性能。此外, 从B-RTAODV2和B-RTAODV3对比看得:两者分组投递率基本相等, 且变化规律明显, 随着网络中cbr数的增加它们的分组投递率也略有增加。由此可得:在网络负载较轻, 网络拓扑变化不频繁的环境中, 备份路径的多少并不是影响B-RTAODV分组投递率的关键因素, 备份路径增加也未对B-RTAODV性能造成影响。

2.2端到端的时延

从图3可看出, AODV的延迟时间最短, B-RTAODV2和B-RTAODV3基本相等, AODV与B-RTAODV最大相差0.01s。端到端延迟受很多因素影响:包括找路延迟、排队延迟以及链路中断引起的重新找路延迟等。在本次仿真中, 延迟主要是由于找路延迟造成的。B-RTAODV采用了RREQ缓存机制, 其找路时延将高于AODV, 从仿真结果中也得到了很好的验证。但RREQ引入的延迟相对AODV不是太显著, 其影响在可容忍范围内。因此, B-RTAODV虽然引入了多路径机制, 增加了协议复杂度, 但是并未降低AODV的性能。

从B-RTAODV2以及B-RTAODV3对比:两者端到端延迟基本相等, 且变化规律不明显。因此可得出:在网络负载较轻, 网络拓扑变化不频繁的环境中, 备份路径的多少并不是影响B-RTAODV端到端时延的关键因素, 备份路径增加也未对B-RTAODV性能造成影响。

2.3路由重建时间

从图4看出, AODV路由重建时间最长, 而B-RTAODV2与B-RTAODV3路由重建时间均比AODV短, 最大相差0.1s。三者路由重建时间都随cbr数的增加而增加。因为在传统的AODV中, 随着节点移动建立好的路径被中断, 它将重新发送RREQ来建立路径。而在B-RTAODV中路径被中断后, 链路断开的上游节点也将进行两跳内路由修复, 其结果是B-RTAODV的路由重建时间比传统的AODV短。

2.4路由开销

从图5看出:AODV与B-RTAODV开销基本相等。因为在本次仿真中, 路由开销主要于AODV本身的hello机制导致, 而hello分组是定时发送, 其开销仅与仿真时间有关。

此外随着cbr业务源个数增大, 三者的开销都略微上升, 这是因为cbr连接数增多, 即源节点个数增多, 必然导致发送更多的RREQ。这充分体现了AODV“按需查找路由”的特性。

综上所述, 在网络负载较轻, 网络拓扑变化不频繁的环境中, B-RTAODV在路由重建上明显优于AODV, 备份路由机制的引入, 提高了AODV在普通网络环境中断路后的性能, 但其分组投递率比AODV下降了1%个数量级。

3结论

传统AODV路由在网络拓扑结构改变后, 链路修复性能差, 数据传输延迟大, 路由重建时间长。本文通过设置多条优先级链路来减少链路修复范围。基于NS2仿真平台的实验表明改进的AODV更适应于拓扑变化快的环境, 并能在链路中断后迅速找到可用路由。

参考文献

[1] Ko Y B, Yaidya H H.location-aided routing (LAR) in mobile ad hoc networks[J].Wireless Networks, 2000, 6 (4) :307-321.

[2]Perkings C E, Royer E M, Das S R.RFC 3561:ad hoc on demand dis-tance vector (AODV) routing[EB/OL].2003-02.http://www.elook.org/computing/rfc/rfc3561.txt.

基于DV―Hop定位算法的改进 篇5

摘要：针对DV-Hop算法采用跳数乘以平均每跳跳距估算节点间的跳距，利用三边测量法或极大似然估计法估算节点坐标信息，算法过程存在缺陷从而造成定位误差过高的问题。为此提出一种基于节点密度区域划分的DVHop改进算法（DZDVHop），依据网络的连通度和节点密度限制参与估算的信标节点的跳数，采用加权质心法估算定位坐标。Matlab仿真测试结果表明，在相同的网络硬件和拓扑结构环境下，改进后的算法能有效地减少节点通信量，且平均定位误差率比传统的DVHop算法减少了13.6%左右，提高了定位精度。〖BP）〗

针对DVHop算法采用跳数乘以平均每跳跳距估算节点间的跳距，利用三边测量法或极大似然估计法估算节点坐标信息，算法过程存在缺陷从而造成定位误差过高的问题。为此提出一种基于节点密度区域划分的DVHop改进算法（DZDVHop），依据网络的连通度和节点密度限制参与估算的信标节点的跳数，采用加权质心法估算定位坐标。Matlab仿真测试结果表明，在相同的网络硬件和拓扑结构环境下，改进后的算法能有效地减少节点通信量，且平均定位误差率比传统的DVHop算法减少了13.6%左右，提高了定位精度。

关键词：

无线传感器网络；密度区域划分；节点定位；限跳机制

中图分类号：TP393

文献标志码：A

0引言

现代电子技术、检测技术和信号处理等技术的进步，促进了低功耗、多功能智能传感器的快速发展[1]。无线传感器网络（Wireless Sensor Network，WSN）是指由大量成本低廉的具有智能感知能力、计算能力、无线通信能力的传感器节点组成的网络，它可以感知、采集和处理网络覆盖区域内目标对象的信息[2-3]。作为一种新型信息获取的系统，WSN广泛应用于军事、环境监测、城市交通、灾难防控等众多领域[4]。节点定位问题是传感器网络进行目标识别、监控、定位等应用的前提，也是传感器网络应用的关键技术之一[5-7]。研究节点定位算法的意义主要体现在两方面：一是，WSN中的多数应用都依赖于传感器节点或者被检测目标的地理位置信息，不知检测目标位置而获取的任何信息都是没有意义的[8]；二是，WSN网络的运行和管理需要节点位置信息的支持。因此，准确估算节点位置，在传感器网络的应用中起着至关重要的作用。

节点定位技术分为基于测距（Range Based）的定位算法和无需测距（Range Free）的定位算法两类[3]1283，[5]39，[8]3。基于测距的定位算法原理是：通过测量节点与节点间的直线距离或角度信息估算未知节点的坐标位置，目前这类测距技术主要有RSSI（Received Signal Strength Indicator）、TOA（Time of Arrival）、TDOA（Time Difference on Arrival）和AOA（Angle of Arrival）等[1]77，[5]40。基于测距定位算法的优点是定位精度较高，缺点是网络中的节点需要增加特殊的测距设备，从而导致节点成本较高。而无需测距的定位算法原理是：不需要测量节点间的实际距离以及节点间的方位角，只根据网络中节点间的连通性、同向性等信息，就可以估算出未知节点的坐标位置，常用的无需测距技术有：APIT（Approximate PointinTriangulation test）、质心算法、DVHop（Distance VectorHop）和Amorphous等算法[5]40，[9]。无需测距定位算法的优点是：组网成本低、网络资源开销少，缺点是定位误差率稍高。实践证明无需测距定位技术更能适合多数WSN的应用，而在众多无需测距的定位算法中，DVHop算法以其算法过程的简单性和实效性成为目前应用较多的种类之一[7]2468。WSN中的节点分为两类：一类是预先已知自身位置信息的传感器节点，称之为信标节点（或“锚节点”），信标节点的坐标信息既可以通过全球定位系统（Global Positioning System，GPS）等技术自动获得，也可以在部署网络时靠人工设置[8]6；第二类节点是预先并不知道自身的位置，通常称之为待定位节点或者未知节点。这些未知节点的位置信息就需要利用本文和相关研究所探讨的相关定位算法进行估算。

1经典DVHop算法描述

美国Rutgers University的〖BP（〗Dragos 〖BP）〗Niculescu等将距离矢量路由与GPS原理相结合提出了一系列分布式定位算法（Ad Hoc Positioning System，APS）[10]。APS共包括DVHop、DV Distance、Euclidean、DV Coordinate、DV Bearing和DV Radial等6种类型。其中应用较多的是DVHop，DVHop的执行过程可归纳为以下3个阶段[1]77，[5]40，[11]。首先，接收并存储未知节点与它邻近的每个信标节点间最小跳数；信标节点向邻居节点广播包含自身地理位置信息的分组，这样网络中的所有节点都能记录下自己到每个信标节点的最小跳数。其次，计算未知节点与信标节点的跳距；每个信标节点根据上述第一个阶段的操作，记录下了自己与其他信标节点的坐标值以及它们间的跳数。最后利用式（1），就可以估算出自己的平均每跳跳距。其中：（xi，yi）、（xj，yj）是信标节点i和j的坐标，hj是信标节点i与j之间的跳数。

基于改进差分进化算法的无功优化 篇6

关键词：差分进化算法；改进；线损；无功优化

中图分类号：TM714.3 文献标识码：A 文章编号：1674-1161（2014）12-0022-03

差分进化算法是近几年来新兴的基于群体智能的随机优化算法，其原理简单，有较强的全局收敛性，适用于解决一些复杂的优化问题。目前差分进化算法已经广泛应用于电力系统的无功优化领域，并取得了较好的效果。但是该算法也存在过早收敛、易于陷入局部最优解、收敛速度慢的缺点。因此，本研究提出一种改进的差分进化算法，将群体随机动态分成多个子群体，同时采用自适应控制参数策略，以克服早熟问题，跳出局部最优解。并在IEEE 57节点测试系统上对该算法的可行性进行验证，证明该改进差分进化算法具有较高的收敛性和搜索精度，且具有较强的跳出局部最优解能力。

1 基本差分进化算法（DE）

基本差分算法是通过对种群中的个体进行变异、交叉和选择操作来实现择优进化的算法。其中：变异是指把种群中两个个体的加权差向量加到第3个个体上产生中间个体的过程；交叉是指将中间个体与当前个体按照一定的规则混合产生新的试验个体的过程；选择是指在试验个体的目标函数值小于当前个体的目标函数值的前提下，试验个体替代下一代当前个体的过程。

2 改进差分进化算法（IDE）

该改进算法将种群中的个体随机动态分成多个子种群，以增强个体间的信息交换，保持解的多样性；变异尺度因子F与交叉概率CR采用自适应机制，以平衡局部搜索与全局搜索。该算法的主要特点描述如下。

2.1 动态交换与多群体分组

为增强个体之间的信息交换，提高种群的多样性，提出将种群个体随机动态分成多个子群体小组。在每一次迭代中，种群个体被随机分成3个子群体小组；每个子群体小组中的个体按适应度从好到坏降序排列，则可得到3个子群体小组中各自的最好个体；用得到的3个最好个体更新每个子群体小组中倒数3个相对差的个体，完成一次个体间的信息交换。被分隔的3个子群体小组重新合并为1个种群，在下一次迭代中将重新随机划分为3个子群体小组，再次得到每个子群体小组中最好个体，将得到的3个最好个体与上一次迭代中得到的个体进行比较，保留优秀个体。这样可以实现不同群体间动态交换信息和增强差分进化算法跳出局部最优解的能力的目的。

2.2 自适应变异尺度因子F

自适应变异尺度因子F是根据差分向量变化的幅度来自适应调整的。如果差分向量的两个不同个体在搜索空间中距离很远，则生成的差分向量值很大，F应取较小的值，以提高全局搜索的能力；反之，如果差分向量的两个不同个体在搜索空间中距离很近，F应取较大的值。F自适应策略可表示为：

Fkji=Fn+（Fm-Fn） （1）

式中：Fkji为当前代k所处子群体j中第i个个体变异尺度因子；Fm和Fn分别为变异尺度因子的上、下限；fkja，fkjb和fkjc分别为当前代k所处子群体j中更新第i个个体F值时随机选择的3个个体中最优、次优和最差的个体适应度。

2.3 自适应交叉概率CR

自适应交叉概率CR通过对比当前代所处子群体中个体适应度与该子群体平均适应度来自适应调整CR值。在当前代所处子群体中个体适应度不小于该子群体的平均适应度，即个体适应度相对较差的情况下，CR采用式（2）中（a）的更新策略；在当前代所处子群体中个体适应度小于该子群体的平均适应度的情况下，CR采用式（2）中（b）更新策略。

式中：CRkji为当前代k所处子群体j中第i个个体交叉概率；CRm和CRn分别为交叉概率上、下限；fkji为当前代k所处子群体j中第i个个体的适应度；，fkjmin，fkjmax分别为当前代k子群体j的平均适应度、最小适应度和最大适应度。

CRk-1jix是随着进化代数k的不同而逐代更新的，其更新策略为：

3 仿真与分析

为了验证改进差分进化算法（IDE）的有效性，测试系统对IEEE 57节点进行了无功优化计算。利用仿真工具MATLAB 7.0，分别与基本差分进化算法（DE）、常规遗传算法（GA）、自适应遗传算法（AGA）、全面学习的粒子群优化算法（CLPSO），以及带惯性权重的粒子群优化算法（PSO-w）进行比较。为了验证IDE性能，比较的指标包括：有功网损最好值（Best（p.u.）），标准方差（Std.Dev），有功网损平均值（Mean（p.u.）），有功网损节省率（Psave）。表1列出了IEEE 57节点测试系统无功优化的系统有功网损结果，图1给出了基于各种算法的无功优化的系统有功网损收敛曲线。

由表1可以看出：相较其他几种算法，IDE能够搜索到全局最优或接近全局最优解，获得的有功网损最好值、有功网损平均值更小。同时，基于IDE求解的IEEE 57节点测试系统的最优网损相比系统的初始网损下降了14.654 7%，比其他算法节省率Psave高，尤其在较大系统中IDE优越性更明显。从标准方差（Std.Dev）的角度来看，IDE的方差也小于其他算法，说明IDE更具稳定性。

图1显示了基于各种算法的系统有功网损Ploss随迭代次数变化的收敛曲线，充分验证了表1中结果的正确性；同时也充分表明了IDE不仅能在寻优初期保持良好的多样性，而且在寻优后期也能具有良好的收敛性。

4 结论

本研究提出了改进差分进化算法，并将该算法应用于电网无功优化问题中。通过对IEEE 57节点测试系统的仿真，证明该算法能够在保证算法多样性的基础上，具备良好的收敛性和较强的稳定性，是解决电网无功优化问题的有效工具。

参考文献

[1] 袁晓辉，苏安俊，聂浩，等.差分进化算法在电力系统中的应用研究进展[J].华东电力，2009，27（3）：135-148.

[2] 张勇军，任震，李邦峰.电力系统无功优化综述[J].电网技术，2005，19（1）：23-34.

[3] 刘波，王凌，金以慧.差分进化算法研究进展[J].控制与决策，2007，18（5）：521-531.

[4] 赵树本，张伏生，钟继友，等.自适应差分进化算法在电力系统无功优化中的应用[J].电网技术，2010，34（6）：123-145.

[5] A.NOBAKHTI，H.WANG.A simple self-adaptive differential evolution algorithm with application on the ALSTOM gasifier[J].Applied Soft Computing，2008，4（1）：298-310.

算法改进设计 篇7

单元制造是成组技术在企业中的具体应用,通过合理的单元构建、单元内机器布局以及单元间的布局,可以有效提高企业的生产效率、缩短准备时间和提前期,以及降低在制品成本等,从而降低企业的物料搬运成本、工具使用成本、设备成本以及员工聘用成本。因此近30年来国内外许多学者对其进行了大量的研究。

单元构建的方法有可视化编码、聚类分析、模糊聚类法、图论法、启发式算法、仿真模拟技术、数学规划法与智能技术等[1,2,3,4,5,6,7,8]。数学规划法应用智能技术解决单元构建问题,由于其目标函数及约束条件的任意选择性特点与实际生产过程中零件结构、批量以及工艺路径的多样性相符合,且便于应用计算机等先进手段的运用,因此这种方法在单元构建中最具应用潜力。

由于制造单元构建问题较复杂,虽然学者们已经提出了大量的规划模型,但是具有可实施性的制造单元应该是多种关联因素共同作用的结果,这些因素包括产品投产数量、加工的单位时间、加工工艺路径、设备能力、同种类型设备的数量(可选设备)等[9],因此目前所考虑的数学规划模型中,还存在以下问题:(1)考虑同种设备只有一台,而实际情况是同种设备可能有2台或2台以上;(2)没有考虑零件操作存在多路径的问题,或者即使考虑到该问题,但是每条路径中的操作顺序没有明确;(3)同种设备的数量直接影响产品生产过程中的搬运次数和搬运成本,设备数量越多,则势必会减少物料的搬运次数,但是同样会增加设备的折旧和维修成本,然而在目前学者的研究中都没有同时考虑物料搬运成本与机器的折旧和维修成本这两个成本因素。

因此本文在假设单元布局为直线形而单元内机器布局为直线形或者L形的基础上,就以上三方面问题进行改进,提出一个一般性的单元制造0-1非线性整数规划模型,同时确定产品和机器的划分、机器布局以及单元布局使得总搬运成本与机器维修和折旧成本为最小。

1 模型分析

1.1 相关参数

p表示零件,p=1,2,…,P;i,j表示机器,i,j=1,2,…,M;r表示路径,r=1,2,…,RP;op表示操作,op=1,2,…,OP;k,k′表示单元,k,k′=1,2,…,K;s,q表示单元内机器所处的位置;g,h表示单元所处的位置;Nmax为单元内允许拥有的最多机器数;Nmin为单元内允许拥有的最少机器数;Dintra为单元内相邻机器的移动距离;Dinter为相邻单元间的移动距离;Ni为第i种机器最多拥有的台数;Cintra为单元内的单位移动成本;Cinter为单元间的单位移动成本;Dp为第p种零件的年需求量;Bp为第p种零件的移动批量;Ci为第i种机器每年的维修和折旧成本;W为一个无穷大的数。

Xipr(op)=1表示第p种零件的第r条路径的第op个操作需要使用机器i,否则Xipr(op)=0;Xik=1表示第k个单元拥有机器i,否则Xik=0;Xiks=1表示第i种机器位于第k个单元的第s个位置,否则Xiks=0;Xkg=1表示第k个单元位于第g个位置,否则Xkg=0;Xpr=1表示第p种零件选择第r条路径进行操作,否则Xpr=0;Xipr(op)k=1表示第p种零件的第r条路径的第op个操作在单元k中的机器i上操作,否则Xipr(op)k=0。

1.2 模型分析

目标函数:

其中,单元内的移动成本为

单元间的移动成本为

机器的年维修和折旧成本为

并且α+β+γ=1。

约束条件:

上述模型中目标函数表示综合考虑单元构建、机器布置和单元布置的情况下,使得总搬运成本和机器购买成本为最低。

约束条件中,式(1)和式(2)表示单元尺寸的限制;式(3)表示每种机器最多能够购买的数量;式(4)表示每种零件只能选择一条路径进行操作;式(5)表示如果某个零件的某条路径被选择,则该路径上的所有操作都必须进行;式(6)表示每个位置至多只能放置一台设备;式(7)表示每个设备只能放置于一个位置;式(8)表示每个单元只能固定于一个位置;式(9)表示每个位置只能设置一个单元;式(10)表示变量Xipr(op)k和变量Xpr以及变量Xipr(op)之间的关系;式(11)表示变量Xipr(op)k、Xik、Xpr、Xkg和Xiks均为0-1变量。

2 改进遗传算法

目前学者们已经提出了很多种制造单元构建问题模型的求解算法,如两阶段法、粒子优化算法、混合遗传算法、神经网络法、模糊算法等[9?16]。遗传算法是一种高效、并行、全局性的概率搜索算法。相比于传统的优化方法,遗传算法具有较好的全局搜索性能、不容易陷入局部最优等优势,适用于处理大规模的复杂非线性优化问题。但是针对不同的数学模型,由于变量和约束条件的特殊性,在运用基本遗传算法时往往会根据具体问题进行算法改进来适应模型的求解。针对上述提出的0-1非线性整数规划模型,鉴于其变量的复杂性以及较强的关联性,本文采用双层遗传算法、精英策略以及自适应算法来进行模型的求解,既加快了求解的速度,又有利于获得模型更好的满意解。

2.1 染色体编码

本文采取二进制编码和整数编码混合的方法进行变量染色体的设定。变量Xik和Xipr(op)k采取二进制编码,而Xiks、Xpr和Xkg则采取整数编码方式,如图1所示。通过这种编码方式可以使得随机选取的个体满足式(4)和式(6)~式(9)。

2.2 双层遗传算法流程

由于变量Xik和Xpr与变量Xiks和Xipr(op)k之间存在较强的关联性,且对目标函数都有一定的贡献性,因此在运用遗传算法求解模型时,采用双层遗传算法来防止大量无效解的产生,从而加快运算速度。即首先确定变量Xik、Xpr和Xkg的初始种群,在对这三个变量运用遗传算法进行循环时,对与之相关的Xiks、Xipr(op)k变量再套用遗传算法进行迭代优化,找出与每组Xik、Xpr和Xkg变量相对应的使得目标函数最优的Xiks、Xipr(op)k。通过双层遗传算法既可体现遗传算法适者生存的本质,又可以保证所有的变量均满足式(5)和式(10)。具体过程如图2所示。

2.3 主层遗传算法

(1)选择策略。选择策略采用的是随机竞争选择方式。先通过普通方法计算选择概率,然后采用轮盘赌方法选出染色体对,通过染色体对之间的比较,使高适应度值的个体进入复制阶段。

(2)交叉算子。根据染色体结构,本文采用三点交叉方式进行交叉操作,在交配池中随机选取一对进行交叉的染色体后,再随机生成3个交叉点进行交叉,如图3所示。

(3)变异算子。对变量Xik和Xpr采用单点变异方式进行变异,变量Xkg则不进行变异。

(4)自适应算法。根据Srinvia提出的自适应遗传算法,交叉算子和遗传算子会随着个体适应度值自动改变。交叉概率Pc和变异概率Pm按照以下公式自适应调整:

其中,fmax为群体中最大适应度值;favg为每一代群体的平均适应度值;f′为待交叉的两个中较大适应度值;f为要变异个体的适应度值;Pc1=0.9;Pc2=0.6;Pm1=0.1;Pm2=0.01。

2.4 二层遗传算法

针对变量Xik和Xpr染色体个体的进化,通过二层遗传算法对与之有一定关联的Xiks和Xipr(op)k变量的染色体进行循环迭代,从而得到每一组Xik和Xpr的染色体相对应的Xiks和Xipr(op)k较优染色体。在第二层遗传算法中染色体的选择采用随机选择的方式任意选择一条染色体,然后根据相应的变异方式进行变异,其中不进行交叉过程。如图4所示,针对Xiks变量的染色体编码,每一单元分别选择两个不为零的随机点进行换位变异。而变量Xipr(op)k的染色体为0-1编码,因此迭代过程中采用单点变异的方法。

2.5 精英策略

在每一次迭代完成时,为了提高群体进化水平,本算法还加入了精英策略方法。也就是每次迭代完成后的父代群体和子代群体合并,并按照适应度的高低进行排列,选择适应度高的Y1个群体作为下一次迭代的父代群体,以此保证每次迭代完成后的群体均为最优群体,并采用最优群体作为后代复制的基础。

2.6 迭代终止

对于主层次遗传算法,为了获得更好的适应度值,循环次数较多,一般T1取500~1000,而对于二层遗传算法,由于针对每一个变量Xik和Xpr染色体个体的改变都要进行一次迭代,同时在迭代的过程中容易出现重复的编码值,因此一次循环的次数可以相对较少,一般T2取20~50。

3 算例分析

本文应用上述模型和改进遗传算法对一个复杂算例进行建模,该问题共有18种机器和17种产品,每种产品有2条路径和3~6个操作,具体情况见表1。通过改进遗传算法对该问题进行求解,在第900代时收敛于最优解,到1000代时获得的最优解见表2,各零件选择的路径分别为2_2_1_1_1_1_2_2_2_2_1_2_2_1_2_1_2,设备6、10、15各有两台,而其他设备均为一台,同时存在4次单元间的移动,历代最优适应度值如图5所示。

4 结束语

面对越来越激烈的市场竞争压力,以及客户对产品的多样化、个性化的需求和交付条件,许多企业已经或正在由传统的大批量生产方式向多品种、小批量的方式转变。在此背景下,各种先进的生产制造系统和生产制造方式被提出并应用于企业的生产实践。单元制造系统由于兼顾了大批量生产的成本和质量优势,以及多品种、小批量生产的快速响应能力,越来越受到企业的欢迎。

算法改进设计 篇8

1)要积极引导学生的选课需求,避免盲目选课、扎堆选课的情况出现。

2)尽可能满足学生的选课需求,让多数学生能够中选,避免出现部分学生多次中选,部分学生无中选的情况。

3)系统应该足够智能化,注重易用性和便利性,尤其是数据的整理、发布等重要操作,要求具备基本计算机操作能力的工作人即可完成。

4)系统运行稳定,效率高,安全性好,易于维护。

1 网络选课系统常用算法分析

1.1“先来先选”算法

从选课系统的设计发展来看,最简单的选课算法是“先来先选”式的,选课系统根据学生登记选课的时间先后来确定中选学生,当选课人数达到该门课程最大限选人数时,就结束该门课程的选课。“先来先选”算法会导致选课系统开放初期会有大量学生涌入选课系统,影响系统效率,极端情况下甚至会出现网络堵塞,服务器崩溃等问题。因此“先来先选”的办法已经逐渐被各类选课系统淘汰。

1.2 优先算法

优先算法一般都采用了预选和正选两阶段结合的方式,预选阶段所有选修课不设选课人数限制,学生可以在和必修课无冲突的情况下,任意进行选修课的选择。预选阶段结束以后,选课系统暂时关闭,进行后台的筛选处理。对于选课人数小于课程容量的课程,所有选课学生都可以中选;但若选课人数大于课程容量,则需要进行筛选。

对于上述“筛选”过程,又衍生出了多种优先算法,以期能够较为公平的处理学生的选课结果。常见的优先算法有“年级优先”“专业优先”“志愿优先”等。“年级优先”和“专业优先”算法顾名思义,前者一般将高年级学生作为优先考虑的对象,首先满足他们的选课需求,再考虑低年级学生的需求。而“专业优先”则优先考虑本专业学生中选本专业的选修课,在优先满足本专业学生的选课需求以后,再满足外专业的学生。“志愿优先”算法则略为复杂,首先是在预选阶段,学生需确定所选选修课的优先志愿选择(根据学生一学期规定可选选修课门数来确定,一般为2-3级志愿),在正选阶段,首先满足第一志愿学生的选课需求,再依次满足二、三志愿学生的需求。

1.3 优先算法存在的问题

可以看到,各类优先算法都是设定了一个“优先对象”首先满足优先对象的选课需求,再考虑其他对象。各类算法“优先对象”设定的群体不同,在一定程度上解决了“选谁不选谁”的问题,但对于选课公平的考虑均欠妥。我们来考虑这样两个问题:

在极端的情况下:所有的优先原则都已使用,依然存在“选课人数大于课程容量”的现象,那么多出来的这部分人该怎么处理?各类优先算法的处理方式多采用“平均分布概率”算法来进行抽签,也就是说最后多出来的这部分学生,采取随机抽签的方式来解决“选谁不选谁”的问题。

在上述的前提下,又会出现这样的问题:在最后的选课结果上,会有学生中选多门课程,而有学生无中选课程的情况出现。实际上这样的情况在选课系统实现中,是应该极力避免的。

造成这样问题的原因在于人为地设定了一个“优先群体”,虽然保障了“优先群体”的选课权利,却未能很好地顾及非优先群体的选课权利。而使用“随机抽签”算法对非优先群体进行筛选,在一定程度上也破坏了选课的公平与公正。优先法的选课,更多的是满足了“优先群体”的选课需求,而忽视了对于非优先群体的公平,对于解决全校公共选修课的选课问题,优先算法是不适合的。

1.4 排除算法的提出

优先算法提出的初衷,在于首先考虑解决大部分学生的选课需求,将大问题转换为小问题的思路来解决问题。然而对于“小问题”的处理最终会回归到使用“平均分布概率”来进行抽签筛选,因此尚未有比“平均分布概率”算法更好的算法提出之前,问题就聚焦到前置算法的设计上,使得用“平均分布概率”算法进行抽签,能做到尽可能的公平。

如何保证每位学生都有中选的机会?如何确保冷门课程和热门课程的人数平衡?是我们对改进选课算法考虑得比较多的问题。首先从优先算法的弊端出发,我们认为不应该人为地设置一个“优先群体”来进行筛选,否则有违公平选课的初衷。另外从公平的角度考虑,我们认为已经中选课程的学生,其选课的优先级应该比未中选的学生低。出于这两方面的考虑,我们认为在使用“平均分布概率”算法来对选课学生进行筛选之前,应该尽可能的降低未中选的学生人数,亦即参与“平均分布概率”抽签的学生人数。因此我们设计了一套“排除算法”,来解决上述的问题。

2 排除选课算法的具体实现

排除算法同样适用于分为预选和正选两阶段的选课形式,在预选结束以后,对于所有的选修课按照如下流程进行筛选:

1)考虑所有选课人数小于课容量的课程,将选择此类课程的所有学生,全部标记为中选状态。满足条件的课程标记为处理完毕。

2)我院公共选修课允许学生每学期选择三门。第二步开始考察所有选课人数大于课容量课程,依次排除已经中选了2门以上、2门、1门的学生。每次排除以后都考察是否有课程的选课人数已经小于或等于课容量,满足条件的课程标记为处理完毕,同时标记相应学生为中选状态。

3)再次考察剩余的选课人数大于课容量的课程,排除在待选集合中还有的学生,也就是说保留仅选择了这一门课程的学生。

4)上述流程处理完毕以后,若还存在选课人数超课容量的课程,则用平均分布概率算法进行筛选,直到所有课程的中选人数小于和等于课容量的状态。

具体的流程图如图1。

程序在抽签阶段不涉及数据的删除,所有选课学生的信息都暂存在临时的“上课学生表选修”sk_skxsbxx中,选修课名单的筛选操作都在这个表中进行。在选课对未中签的学生只是把SFZQ(是否中签)字段标为0。每次选课的结果可以通过该字段进行统计。

sk_skxsbxx表使用的字段如表1所示。

对于最后的抽签程序,使用SQL语句来实现,可以参考下例:

上面SQL的意思是:在备选学生表sk_skxsbxx中,在满足条件课程号:

kch='2007108'和课序号:kxh='1001'和是否中签标识sfzq是空的集合中随机抽取5条。

实施“排除选课算法”以后,预选阶段选课人数不受课容量的限制,只要学生喜欢的课每个学生都可以选,这样可以在一定程度上反映某一门课程的受欢迎程度。

在筛选阶段由于系统在尽量满足每个学生在至少有一门课中选的前提下,再对结果进行随机筛选,因为对于绝大部分学生来说选课机会和中选几率是公平的,并且和学生选课的时间、专业、成绩等因素无关。可以保证绝大部分的学生都至少有一门选修课中选,最后需要利用平均分布概率算法进行筛选抽签的课程,一般只有少数热门课程,并且最后进行抽签的学生人数,也会大大少于实际选择该门课程的学生人数(大部分学生已经中选其他课程)学生无法中选课程的几率。

“排除选课算法”的实施,可以在“课程总容量”尚未远远大于“需选课学生人数”的情况下,比较好的解决学生公平选课的问题。在目前我院的应用当中,已经取得了比较好的效果。具体的反映就大大减轻了“补选”阶段的工作量,所有的选修课名单在“正选”阶段就可以全部确定了。

3 除选课算法外的其他工作

诚然,无论是我院采用的排除抽签选课法还是其他已有的各类算法,都只是在上课学生人选上进行的筛选,为了让学生能够更有目的、有规划地进行选课,在选课算法的优化设计之外还有应该在学生选课阶段对学生进行积极的引导。一是避免部分热门课程选课人数过于集中,导致中选率过低,二是增加部分冷门课程的选课人数,让尽可能多的学生所选课程都能中选。为此我们在选课系统中增加了实时中选率显示和推荐课程显示。

实时中选率通过计算已课程容量和已选课人数的比值,显示该门课程在目前状态下的中选几率,学生在选课时可以看到每门课程的中选率,以方便规划自己的选课。

假设一门课程课程容量为P1,已选课人数为P2,则当P1>=P2时,中选率显示为100%;当P1

算法改进设计 篇9

关键词：绩效评价,模糊算法,复合元素

随着信息技术的飞速发展和日趋激烈的商业竞争,企业的各项事务处理也逐渐采用科学化现代化的管理。尤其是对员工的绩效考核,传统的考核存在很多管理者主观的影响,因此传统的绩效考核方法已经不能满足企业的生存和发展需要。所以,应用模糊算法进行绩效评价系统设计,对于客观评价员工绩效具有非常实用的价值。

1绩效评价技术

1.1评价指标类型

1.2评价指标权重

评价指标权重的确定要首先对权重系数进行确定,绩效评价权重系数可以用主观赋权法根据评价指标的重要性确定权重系数,也可以基于客观赋权法根据评价指标取值的变化程度赋权,还可以将二者结合起来组成组合赋权法。

1.3评价指标集结

2模糊理论

2.1基本描述方式

模糊理论的基本表述方式如下所示:

设模糊形式背景(即要被挖掘的数据库)为公式

若:,则,

设,上和下近似一般形式如下:

则,上述关系集合可被划分为:

那么可以称之为:P相对于D拥有模糊分类能力。且满足如下关系:

2.2基本描述

属性集合B相对于属性集合A的条件信息熵H(B/A)可以定义为:

2.3基本思想

以任选特定模糊综合评价属性a∈C和b∈C为例,特定元素模糊综合评价算法将其关系界定为:

2.4算法流程

基于以上给出的定义,一个由下到上的算法可以描述如下:用CO表示决策表的核,B表示约简属性集合。模糊综合评价算法令B=CO,将相对于B补充性最大的属性聚集到B中,进行遍历直至与条件C属性集合相同,即H(D/B)=H(D/C)结束,此时的B即为最小相对约简。

输出:相对约简B

(2)计算条件属性集相对于决策属性集的核属性集CO,以及候选属性集A=C-CO。

(3)计算每一个属性对的互补度量。

(6)计算条件熵H(D/B)。如果H(D/B)≠H(D/C)跳到(5)。否则,程序终止,此时B即为最终的约简。

现有的模糊聚类算法多是基于特定元素模糊综合评价算法这类模糊绩效评价算法的主要问题在于:员工绩效评价是一个多元素、多层次的评价体系,特定元素模糊综合评价算法缺乏对负责绩效评价的整体性研究,而且算法缺乏层次性,因此以上两类算法均不适合对复杂的员工绩效评价系统的数据挖掘工作。

3算法设计

3.1算法主体结构

确定评价因素集假设对事物评价,有n个评价因素组成的评价集。

评价结果集

假设评价结果的等级有m种,

确定因素权重

通常其结果也是和实际情况相符的。一级因素相对于评价对象的权重集为:

二层因素相对于一层因素的权重集为:

在模糊绩效评价系统设计中,评价指标权重是主要的核心数据,评价指标权重反映的是在不同因素下对员工绩效的评定内容,按照不同的评价方式进行评价,再进行综合决策,以便于更加客观、公平、公正地对员工进行绩效考核,此过程中的各个权重指标直接影响到员工的综合评价结果,对员工的评价决策也具有非常重要的作用。在一定程度上权重是依据管理者经验给予赋值,其具有一定的主观性,但是通过不同评价者的主观综合评定,便能较为客观地反映出实际的状况。

3.2算法过程

建立加权特定元素评价矩阵:首先确定单个因素对员工绩效的评价等级隶属度,其中因素ui结果为一模糊子集ri,如果所组成的评价小组有k个成员,每位成员给每一个因素评价一个等级,若评价因素ui等级,则:

当评价组的成员不同时,设由k人组成评价组,评价成员根据不同类型(领导、同事、客户等)分为P类,其中第类的人数为k,则:

k=k1+k2+…+kp

权重分别为:

a=a1+a2+…+ap

若评价因素为ui为等级vi的各类人分别为:

k=kij1+kij2+…+kijp

则就可以得到:

假设每个因素都可以使用模糊量Ri进行表示,那么模糊矩阵表示n个因素的评价结果为:

其中i=1,2,…,n;j=1,2,…,m。

3.3算法绩效评价结果确定

基于复合元素的绩效综合评价公式:

其中,●为合成运算,这里采用M(∧,∨)模型,

B为综合评价结果,bj表示评价对象对评价集中第j个等级的隶属度。如果评价结果出现了两个相同的隶属度,评价则缺乏客观性。所以设计的绩效评价系统采用了加权平均算法解决此问题,具体设计如下:

则评价结果为:

例如,在员工的绩效评价考核调研得出的,100-85分为优秀,84-70分为良好,69-60分为中等,低于60分为差,设赋值后的矩阵为R,则:

则评价结果为:

通过改进的模糊算法绩效评价系统在使用简单的矩阵乘法公式计算下,便能够得到公司每位员工的综合评价分数,此分数能够较为客观地反映出员工绩效的真实情况,再根据优秀、良好、中等、差4个等级的划分,将满分100分划分为:100-85分为优秀,84-70分为良好,69-60分为中等,低于60分为差,这样就能够客观的衡量员工的绩效考核成绩,以便于企业对员工更好地进行人事管理。

4结语

基于模糊算法的绩效评价算法是绩效管理系统中知识发现及特征提取中的一个重要问题,给出了一种基于复合元素的模糊评价算法。实验结果验证了算法的可行性及有效性。本算法时间消耗很大,下一步工作需要找到方法来减少属性间互补性的计算方法时间消耗,同时应将该方法扩展到不完备、不一致系统中。

参考文献

[1]邓晓诗.企业人力资源有效性分配研究[J].人力资源管理,2011,(12):192-193.

[2]谢晋.模糊算法在高校教师评价系统中的应用研究[J].软件,2015,(8):22-24.

[3]吕虹云,李楠楠.多项目管理中的人力资源配置问题研究[J].经济研究导刊,2011,(1):130-132.

[4]毛辉俐.论公路监理行业人力资源成本控制[J].当代经济,2010,(24):115-115.

蓝牙通信中误码率改进的算法设计 篇10

关键词：家庭网络,蓝牙通信,干扰,跳频频率,误码率

当前将私人计算机、家用照明及智能电器、智能水电煤表、报警系统连接而形成的系统称为家庭网络[1]。家庭网络不仅能在自己的家里形成智能联网, 还能连接到智能小区里的网络, 同时也能联网。随着科技的发展, 无线网络一定会是家庭网络的最终表现形式[2,3]。而在家庭网络中, 蓝牙较其他多种无线通信方式来说, 是最合适的选择。蓝牙由于自身稳定的系统、简单易操作、造价低廉、开放性等特点, 可以广泛地应用到各个领域[4,5,6,7]。所以, 研究使用蓝牙作为通信方式的家庭网络是一项非常具有实际意义的课题, 关系着提升整个居民的生活品质[8]。蓝牙采用了全球通用的2.4 GHz ISM频段, 而这一频段全部的无线电系统都已开发, 所以蓝牙在此频段工作时, 会遭受较大的干扰。为了使链路不受干扰, 能够平稳地工作, 且能够尽可能地抵抗外界的干扰, 蓝牙采取了快速跳频以及短包技术[9]。假如有来自外界的干扰频率与此刻的跳频频率恰好相等, 那么会产生很大的干扰, 而如今的跳频不能够自动地避开干扰。如果系统可以察觉出有干扰, 同时还能够调整载波频率, 该系统才能够避免干扰。笔者基于这一背景, 进行了蓝牙通信中误码率改进算法内核的设计及性能对比研究, 这一研究在保持了跳频序列较强功能的基础上显著降低了误码率, 具有较强的实用及理论价值。

1 误码率改进算法内核的设计

1.1 内核系统的改进

由于蓝牙跳频算法的构架简单、功能强、能够生成较为均匀的跳频序列, 很大程度上改善了蓝牙系统的干扰抵抗性。然而, 在2.4 GHz频段中会有很多无法预估的干扰源出现, 跳频频率会受到影响。想要提升蓝牙抵抗以及避开干扰的能力, 下文对跳频算法做了优化, 且具有自适应功能。

本方法的主要思想是如果有干扰频率G, 此刻的跳频时隙采用蓝牙跳频算法计算出下一频率, 把此刻的频率与干扰频率对比, 假如相同, 就把下一个时隙频率增添偏移量, 让其离开该频段, 等待下一时隙发生, 这个时隙的频率和干扰频率已分离, 不存在干扰;假如不同, 那么下一时隙频率还是保持不变。当不存在干扰时, 经过改善优化的处理方法和原来的频率方法一样。图1为改善优化处理方法的内核。主设备时钟用CLK27-0表示, 下一个时隙用CLK'27-0来表示, 蓝牙设备标志用A27-0表示。各控制信号的具体表示见图

未优化算法采用图1中上半部分方案, 即首先进行5位X与5位A的相加运算, 并进行模32操作;然后将得到的数据与4位B进行异或运算;接着进行排列处理, 排列处理由多层的蝶型运算组成, 按照控制字的方法进行处理;最后将排列处理的结果加上一个常数, 并且取模79, 能够得到0~78的7位数fout, 再把fout寻址存储在79跳频的寄存器组里。

本文的优化处理方法要尽量避免干扰频率, 需要在未优化算法的基础上添加新模块。经过优化后算法的主要思想是:首先要把7位寄存器的初值赋零;通过跳频算法计算得出目前的跳频频率, 记为f'out;然后把7位寄存器与fout进行加法运算, 得到的结果xout即为此刻时隙最终数据结果, 并且把其映射到79跳频列表里。在进行对比的模块里, 这里的干扰频率记为G, 按照7位二进制的方式进行表达。假如不存在干扰频率, 将开关置1, 此时无需进行比较操作, 把7位寄存器的值全部清除。假如存在干扰频率, 把开关置2, 对f'out与G作比较运算。当f'out与G的值相同时, 寄存器赋值m, 即前文所述偏移值, 在文中设定m=32。当f'out与G的值不同时, 把寄存器值清空。下一个时隙出现时, 同样可以得到当前时刻的跳频频率fout和下一时隙跳频频率f'out。这个过程与之前的时隙是相同的, 第一步也是把fout和寄存器中的值进行加法运算, 若寄存器值是m, 可表明前个时隙里已知fout受到干扰频率的干扰, 把fout进行m的加法或者减法, 使其避开该频段, 把xout映射跳频列表里;然后把下一f'out与G作对比, 按照对比得出的结果进行设定寄存器值。干扰频率会出现2个或2个以上的情况, 那么就应进行多次对比, 由于时间的限制, 要在下组出现之前完成, 以确保时隙的一致性。

1.2 跳频序列算法

在全球通用技术标准中, 蓝牙一共有10种可供选择的跳频。其中, 有5种是应用在79跳频系统里, 而剩下的5种应用在23跳频系统里。在这里, 研究的是79跳频在连通之后形成的信道跳频序列, 并且是基于蓝牙的跳频算法。蓝牙系统是把ISM频段按79个带宽以及载频间距均为1 MHz进行区分。蓝牙所用的信道是以跳频或时分联合的方式进行的。其信道分成的时隙为625μs, 一般跳频是每秒1 600跳, 并且任意的一个时隙都对应不一样的频道。主设备的信息参数影响着跳频序列在匹克网信道上的关键因素。通常情况下, 主设备所用的时钟是以28位数示意, 蓝牙的时钟是取312.5μs, 即一个时隙的一半为其最小单位。蓝牙主设备的地址低28位和时钟地址高27位影响着跳频序列。跳频算法的基本原理图见图2。

这里论述处理一个信道跳频序列的方式。首先从主设备79跳频以及地址高22位的时钟地址中选择不间断的32跳频段;然后将所有的27位时钟以及设备标识形成一个5位序号, 取32跳频段里的其中一个, 随意访问这些跳频点。依照偏移量在跳频段里选择其他的32跳频段, 以此类推。跳频列表是寄存器, 其中放置79个跳频频率的标号。首先把跳频列表里放置的全部偶数频率进行排序, 再把全部的奇数频率按照顺序进行排序, 最终得到的列表见图3。这样一来, 32位的一跳频频段就可以把64 MHz的频带全部囊括, 可以涵盖79 MHz带宽的80%以上。依照这种方式, 能够划分228个跳频序列, 是一个非常庞大的数据。完整的一跳频序列维持的时间有227×625μs, 约23 h。所以若几个匹克网都在同一区间里, 那么跳频序列之间能够产生频率相撞的概率降低了很多, 这样就能够达到蓝牙系统需要满足序列相关性的条件。需要对蓝牙设备标识以及时钟转换的时候, 跳频序列会马上进行转换, 十分简便快捷。

2 新旧系统对比仿真及性能分析

2.1 未改进系统算法内核的抗干扰性能

第一步进行定频干扰下系统仿真, 假如在任何时间系统所产生的干扰频率与幅度都是相同的, 设定干扰频率与幅度分别为20与15, 对系统进行105步跳变, 其中每一步跳变需要一个跳频时隙时间, 仿真结果见图4。

图4a表示对系统可能会造成的干扰源, 也就是Scope1波形图其中的一部分;图4b表示对系统造成的实际干扰, 也就是Scope2波形图中的一部分, 如果输入、输出信号差值为0, 则表示这个时隙的干扰信号对系统没有干扰, 同理, 如果不为0, 则情况相反。因此在定频干扰下, 一般干扰都会影响到系统信号的传输, 系统本身的抗干扰性除外。误码率可达到0.005 901, 通过误码率计算器可以看到这个系统10 000步跳变下的误码率, 同样可以获得下文中所涉及的误码率。接下来进行随机频率及幅度干扰下的系统仿真, 假如在任何时间系统可随机产生79个跳频频率的干扰频率与幅度, 对系统进行105步跳变, 图5为仿真结果图。

随机频率随机幅度干扰与定频干扰图差不多, 图5a表示对系统可能会造成的干扰, 也就是Scope1波形图其中的一部分;图5b表示对系统实际造成的干扰, 也就是Scope2波形图其中的一部分, 如果对应输入、输出信号的差值为0, 则表示这个时隙的干扰信号对系统没有干扰, 同理, 如果不为0, 则情况相反。因此在变频干扰下, 一般干扰都会影响到系统信号的传输, 系统本身的抗干扰性除外。由仿真结果可知, 变频干扰下, 旧系统的误码率最高可以达到0.006 501, 故传输精度极差。

2.2 改进系统算法内核的抗干扰性能

首先还是进行定频干扰下系统仿真, 假如在任何时间系统所产生的干扰频率与幅度都是相同的, 设定干扰频率与幅度分别为20与15, 将新旧系统中的定频干扰频率设置成一样的, 这样可以更好地对仿真结果进行对比, 对系统进行105步跳变, 仿真结果见图6。

图6b所表示的是对系统实际造成的干扰, 可以看到在5 000~10 000步之间的跳变中, 输入、输出信号的差值都是0, 这就表明在以上时隙中, 干扰信号并未对系统造成干扰。所以在同样的定频干扰下, 新系统可完全不受干扰频率的影响, 其抗干扰性有了很大的提升。接下来进行随机频率及幅度干扰下的系统仿真, 仍然假如在任何时间系统可随机产生79个跳频频率的干扰频率与幅度, 对系统进行105步跳变, 图7为仿真结果图。

由仿真结果可以知道, 在变频干扰情况下, 新系统的抗变频干扰性能要远远优于原系统, 可以抵抗大多数的干扰, 平均误码率比较低, 只有0.002 900, 与原系统相比, 其误码率有了约55.4%的下降。在此, 有一点需要说明:根据制定的改进方案, 可通过对下一时隙的跳频频率加某一偏移量就可以完全不受当前干扰频率的影响, 但是存在这样的可能性, 在下一时隙真的来临时, 而干扰频率也正好发生改变, 因为在仿真中干扰频率及其持续的时隙均是随机的, 此时发生改变的干扰频率可能刚好影响到跳频频率, 在这种情况下, 该改进方案也就会没有了原有的用途。

2.3 系统误码率对比

最后再次比较两个系统的误码率, 以进一步对新系统的抗干扰性能进行证明。图8为两路解调误码率的曲线图。

从图8中可以很明显地看到, 新系统在定频干扰下可脱离干扰, 数据传输准确无误, 可消除误码情况。新系统在随机频率干扰下的误码率有了很大的降低, 约为原系统的50%以上。

3 小结

众所周知, 蓝牙系统的跳频算法构架并不复杂, 生成的跳频具有较好的性能, 符合系统要求, 消除了系统工作环境出现的大量干扰。然而, 2.4 GHz的频段会出现很多不能预估的干扰源, 所以很容易出现跳频频率与干扰频率碰撞。为避免这种碰撞带来的干扰, 本文做了优化措施以提升系统对干扰的抵御能力。经过研究分析可知, 经过优化后的跳频序列一样符合蓝牙系统的要求。优化后的系统和传统的方法相比, 误码率缩减了55.39%, 使得系统的抵御干扰能力得到了很大的提升。这种方法简单易操作, 不仅能够避免干扰, 又保持了跳频序列的较强功能, 在理论上、实际中都有重要意义。

参考文献

[1]禹帆.蓝牙技术[M].北京:清华大学出版社, 2002.

[2]张凌, 姚萌.蓝牙通信过程解析与研究[J].计算机应用研究, 2002 (9) :146-147.

[3]VIVEK A S, MIEHAEL P M.Fingerprint identification using space invariant transforms[J].Pattern Recognition, 2002 (23) :609-619.

[4]MEHTRE B M, CHATTERJEE B.Segmentation of fingerprint images-a composite method[J].Pattern Recognition, 1989, 22 (4) :381-385.

[5]杨瑞.基于蓝牙通信的短信平台设计与实现[J].计算机应用与软件, 2011 (2) :218-219.

[6]黄凌霄.基于VC++的双机蓝牙通信的实现[J].洛阳师范学院学报, 2012 (2) :68-70.

[7]LIN H, WANG Y F, JAIN A.Fingerprint image enhancement:algorithm and performance evaluation[J].IEEE Trans.Pattern Analysis and Machine Intelligence, 1998, 20 (8) :777-789.

[8]OGORMAN L, NICKERSON J V.Matched filter design for fingerprint image enhancement[C]//Proc.International Conference on Acoustics, Speech, and Signal Processing.New York, US:IEEE Press, 1988:916-919.