映射优化范文（精选7篇）
映射优化 第1篇
FPGA是可重构的集成电路,其特点是由大量可编程的布线结构包围的可编程逻辑模块。目前大部分FPGA器件都包含基于K个输入查看表(K-LUT)的可编程逻辑模块,一个K-LUT含有2K个真值表配置位,因此K-LUT可以实现任意的K个输入功能。对于一个给定电路而言,实现给定电路的LUT数量决定了基于FPGA实现的尺寸和代价。因此,在FPGA CAD流程中最重要的的阶段之一就是技术映射,技术映射将一个优化过的电路描述映射到目标FPGA体系结构中的一个LUT网络中。
在技术映射过程中,常常将技术映射看为覆盖问题。例如,在图1中给出了将一个电路映射到LUT的过程。图1a是初始的门级网络,图1b是使用4-LUT对初始网络的可能覆盖,图1c给出了由覆盖产生的LUT网络[1]。在所给出的映射中,标号为x的门同时属于两个LUT,即复制了x。有时,为了最小化LUT网络面积,必须复制门电路。
对于小的子电路来说,实现面积优化没有问题。设f(i0,i1,…,in)是任意函数,如果以3-LUT或2-LUT实现,可以使用图2所示的可配置虚拟网络(Configurable Virtual Network,CVN)来实现面积的优化。CVN是由连接到变量i0,i1,…,in的输入线与三个2-LUT组成。交叉位置允许LUT输入选择来自其它LUT的任意输入线或输出线。交叉点上的每一个“开关”由一个虚拟配置位进行配置,其中0代表交叉点是不连接的,而1表示交叉点是连接的。如同为每个2-LUT设置真值表配置位一样,通过控制虚拟配置位,可以枚举包含三个2-LUT的每一种可能的电路配置[2]。
在式(1)及(2)中,可以看到网络fnet的输出作为布尔表达式,其中表达式中包括变量i0,i1…,in、虚拟配置位V1…Vm及真值表配置位L1…Lo。在这两个式中,需要提出的是,对于i0,…,in所有的值来说,V1…Vm及L1…Lo的赋值对fnet(i0,i1…,in,V1…Vm,L1…Lo)引起的变化是否等同于f(i0,i1…,in),这个问题可以从布尔可满足性(Boolean Satisfiability,SAT)中获得确切的答案[2]。给定在交集范式(Conjunctive Normal Form,CNF)中的一个布尔表达式,其中表达式是由句子的一个乘积组成的,而每个句子是由文字的和组成的,试图对变量进行赋值,使每个句子至少有一个文字的值为真。
2 对面积的再综合
所谓针对面积的再综合,必须以原有的LUT电路为基础,其目的是在维持原有功能的基础上,试图降低电路图中的LUT数量。
2.1 将综合问题转化为布尔可满足性
确定一个n可达的锥面是否能用X个n-LUT实现的方法将其进行再综合到用X-1个或更少的n-LUT的n可达锥面中,验证的方法是使用SAT。完成的过程时首先生成一个比初始的锥面所包含的LUT数量更少的n可达的没有扇出的锥面(Fanout Free Cone,FFC),然后,将代表初始锥面功能的真值表赋给CNF表达式。如果该CNF表达式是可满足的,再综合成一个新的FFC是可行的。
为了更清晰地表达这个过程,图3中的3a是由三个2-LUT组成的初始锥面,其功能实现了一个三输入。由于该锥面只有三个输入,将图3a再综合成图3b并节省一个LUT是可行的。为了确定是否可以从图3a再综合到图3b,图3b必须转换成一个CNF表达式,如果表达式是满足的,则再综合是可行的[3]。
CNF等式能够表达电路的所有合法向量,例如,在图4中,当且仅当图4a中的信号A、B及Z与一个AND门的功能相对应时(如(A=0,B=X,Z=0)、(A=X,B=0,Z=0)或(A=1,B=1,Z=1)),式(1)才满足。与此相同,只有类似(A=1,B=1,C=0,Z=1,Y=0)的合法向量时,式(2)才满足。
为了实现这种再综合的检查,首先应该形成CNF的等式,其次,应该根据锥面的真值表限制在CNF等式中的输入与输出变量。最后,利用一个SAT解决器来检查可满足的赋值[4]。例如,将一个两输入的锥面映射到图4b的电路上,将C设置为配置位。为了检查两输入的函数f(1,1)=1是可达的,可以通过判断是否满足F2(A=1,B=1,C,Z,Y=1)=1来实现。很明显,当C=1时其返回值为真值。但是,这只能说明f(1,1)=1是可行的,即只是一个真值表的值。为了在整个锥面上验证一个再综合的电路,即验证整个真值表,其CNF等式将反复计算2n次,以形成一个新的CNF等式,其中n为所映射锥面的扇入数量。基本电路CNF等式的每一次重复计算都对应着锥面真值表中的一个值。因此,需要强调的是,为了检查初始的锥面是否能够与再综合的电路相匹配,可以通过在一个新的CNF式上完成SAT的检验来实现。
再返回到图3中初始的LUT例子,下面的步骤将给出如何实现这些转换。图5是图3b的细节图,该图清楚地给出了CNF构造的内部连线及配置位。在这些步骤中,f代表需要进行再综合的锥面的函数,Xi代表输入向量x1x2x3=i和fi=f(Xi)。
步骤1:针对再综合电路中的每一个元素各生成一个CNF等式,见式(3)及(4)。
步骤2:从式(3)及式(4)中形成电路CNF等式。式(5)是一个与电路的输入与输出(x1-3,f)、内部连线(M)及配置位(L1-8)变量相关的表达式。
步骤3:重复式(5)并根据f函数对输入与输出变量进行约束。
在式(6)中,使用在每一个Gresynth(Xi,fi)实例中的同一变量(L1-8)来代表配置位,在每一个实例中的所有其他信号都有不同的变量[5]。这就保证了在每一个真值表的值都有唯一的配置位。最后,如果锥面与再综合的结构是对应的,式(6)通过SAT检验后将返回真值。
2.2 生成锥面
许多算法可以生成并存储图中所有的再综合锥面,其中有一种算法是从PI到PO按照拓扑排序遍历图来生成再综合锥面。在每一个内部LUT中,通过与输入LUT的锥面结合来产生新的锥面。本文中,如果锥面所有的输入不超过(n+e),其中n为最大的再综合锥面扇入数,e为扩充值,则锥面产生算法与其他锥面结合。只有将e设为足够高的数值,该启发式算法才可以加速锥面生成的过程,而不会严重影响再综合解决方案的质量。
对于有1个以上扇出的锥面必须特别处理。例如图6,如果将a到e的LUT再综合到f到g的LUT,则必须将c到e的LUT复制,以保持LUT c的扇出。这样,该再综合算法总的节约只有1个,而如果LUT c没有扇出,则会节约3个。
3 结束语
本文提出一种可以帮助理解最新FPGA映射算法最优性的方法,主要思想是将电路的每个部分再综合,直到其达到最优状态。下一步的工作是寻找改进该局部优化再综合的方法。通过测试自定义硬件加速方法以改善锥面再综合的运行时间,研究使用don’t care来降低CNF的复杂度并增加再综合研究领域的敏捷性。
摘要：为了提高FPGA技术映射算法的质量,提出了一种基于布尔可满足性(SAT)的算法,在实现系统功能的前提下,可以将一个子电路映射到数量最少的查看表中。通过将该算法迭代应用于已经完成映射的电路局部,在许多情况下,可以使用更少的查看表来完成。
关键词：布尔可满足性,FPGA,再综合,映射优化,查看表
参考文献
[1]Altera.Component selector guide[S].ver18.0,2007.
[2]Chai D,Jiang J,Jiang Y,et al.MVSIS 2.0 Programmer's Manual[R].UC Berkeley,Technical report,2003.
[3]Farrahi,Sarrafzadeh M.Complexity of the Lookup-Table Minimization Problem for FPGA Technology Mapping[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2003,13(11):1319-1332.
[4]Cong J,Wu C,Ding Y.Cut ranking and pruning:Enabling a general and efficient FPGA mapping solution[C].FPGA,2007:29-35.
映射优化 第2篇
制造单元是一种制造功能体,它负责完成制造系统内的独立生产任务,数据的采集与传递伴随着整个制造过程的始终。 通过感知识别将物理与信息世界联系起来,整合、分析感知识别方法与制造单元中的各种实体感知属性。通过建立映射关系,优化感知手段和方法,以期提高获取感知数据的效率。
2制造单元感知技术分析
对于分析制造单元系统中的感知数据信息可以遵从以下方法,即分析某感知属性中的数据信息是通过那些感知量在反映的,又有多少种感知设备可以获取这些感知量,最后再通过哪些传感网络可以高效的传输这些信息。因此,研究感知技术的关键问题就在于对感知量、感知设备和感知网络三者的分类及其相互关系的分析。
2.1感知量
按信号输入类型可分为机械量、电学量、热学量、化学量等。但在实际的感知过程中,应结合实际情况和现有技术条件对感知属性与感知量的关系加以定义。
2.2感知设备
随着自动识别技术、物联网等新兴智能感知技术的崛起,传统传感器已越来越无法满足需求。通过研究制造单元实体的分类,对感知设备的选用进行如下分析:
(1)制造对象感知属性首先需要主动感知对象的编号,可选设备为条码或其他能自动记录信息的感知设备,影响因素为现场工况、制造条件及编码长度等。其次需要感知对象的外形、尺寸、加工精度等信息,可选设备为非接触式在线检测传感器如电感传感器、顶针探测器等,影响因素为传感器的测量精度、测量数据的稳定性等因素。
(2)制造状态感知属性首先需要感知运行情况中执行信号的相关信息,可选设备为PLC控制下的I/O侦听系统。其次需要感知设备负载的启动、能耗以及实时波动情况等信息,可选设备为电磁类传感设备。
(3)制造环境感知属性需要感知对象所处空间的相关信息,如辐射、噪声、粉尘、气体等元素,可选设备为电磁辐射传感器、颗粒传感器、声音传感器、气压传感器等,影响因素为制造单元所处空间中的主要环境因子。
(4)制造物流感知属性首先需要感知对象的物流编号,可选设备为条码或RFID等具备信息存储功能的感知设备。 其次需要感知物流设备的运行参数信息, 可选设备为传送带上的速度传感器或电感传感器等。最后需要感知对象的物流位置等信息,可选设备为摄像头或GPS定位系统。物流位置可通过或摄像头进行感知。
(5)制造人员感知属性首先需要感知对象的人员信息,可选设备为标签存储或者RFID传感设备。其次需要感知对象的位置用以对生产空间和布局进行合理安排,可选设备为摄像头。
3制造单元感知信息特点
制造单元包含产品底层信息是整个制造行业的基础和源头,依照前文对制造单元感知属性以及对相关信息的综合感知分析,可知制造单元产品底层信息包含以下特性:
1)感知数据海量性:由于制造单元中包含了众多的物理实体和生产设备,且每种物理实体或生产设备所包含可感知量的相关参数也颇具数量,又由于连续生产导致感知时间跨度较大。因此在实际生产过程中,对制造单元进行全方位感知将会产生海量的感知数据。
2)感知数据异构性:由于对制造单元不同属性信息进行感知所使用的传感器种类不同,且不同种类传感器检测参量和数据结构也各具特点,因此会造成制造单元的感知数据存在异构性。
3)感知数据关联性:虽然制造单元的生产过程中不同种类的感知数据是独立采集的,但因为制造单元本身属性的内在联系使这些不同种类的感知数据形成一个有机的整体来支撑整个信息系统,因此感知数据必然存在关联性。
4)感知信息时空多变性:制造单元作为一种独立制造功能体,具备空间和时间的多种同台属性。在产品的生产过程中, 生产设备的运转过程,原材料的添加和产品的产出,生产设备中的能量转换等数据信息都处于动态变化中。因此,感知设备的感知能力应具备时间上的实时性和空间上的变换性。
5)感知信息模糊性:感知设备类型和感知环境等外在因素会影响制造单元中感知信息的获取。所以对于感知制造单元某一属性元素时需要确定相应的精度范围,在面对海量的感知信息时应根据所确定的精度范围进行宏观或微观、定量或定性、冗余或缺少、离散或连续等模糊属性。
6)信息感知方式多样性:不同产品制造单元生产过程具有多样性,因此获取的感知属性参量也多种多样,也必然造成感知方式的多样性。
4感知映射关系模型描述
对于制造单元感知映射关系模型的描述,可以定义为制造单元感知集合间的映射关系。根据感知属性的技术特点,可将感知集合分为四类:感知对象集合、感知量集合、感知设备集合和感知网络集合。然后在这些集合中分别讨论实体与各种感知属性之间的关系,最终使两两集合之间建立约束关系。感知映射关系模型如图1。
5感知映射模型优化及求解方法
在感知映射模型中任意两组集合之间都有可能建立映射,且映射关系多种多样。 为更高效的获取感知数据,需要优化感知映射模型,完善感知方法和处理数据信息。
基值设定:设定感知属性为aii ∈ 1,2,…,N),N为全体感知属性集合; 设定感知量为bi(i ∈ 1,2,…,M),M为全体感知量集合;设定感知识别设备为cii ∈ 1,2,…,O),O为全体感知识别设备集合;设定感知网络为di(i ∈ 1,2,…,P), P为全体感知网络集合。
本文将通过三个目标函数对映射关系模型进行优化:
1)成本最小目标函数:
表示种类为i的传感器的单价,包含购买、安装、维护传感器,数据采集及处理等各种费用;表示使用第j种传感网络所产生的费用。映射模型的最小成本可表示为传感器单价与传感网络使用费之和的最小值。
2)延时最小目标函数:
表示种类为j的传感网络传输延时。 映射模型的最小延时可表示为延时时间的最小值。
3)稳定性最高目标函数:
表示种类为i的感知识别设备的工作稳定性;表示种类为j的感知网络的传输稳定性。映射模型的最大稳定性可表示为感知识别设备的工作稳定性与感知网络的传输稳定性之和的最大值。
约束函数:
1)数量上限约束:
用于优化的映射集合任选值的个数, 不可大于感知量、感知识别设备、传感网络中最小集合个数。
2)精度约束:
其中Accuracy(zj) 表示种类为j的感知识别设备的有效精度值,Accuracy*(z) 表示待感知的额定精度值。感知设备的有效精度值必须满足一定的额定精度要求。
在面对无法直接求解的多目标问题时,通常采用的手段是将多目标问题转化成一个或多个单目标问题求解。本文选择线性加权求和的单目标求解法,将分别乘以权重系数的目标函数相加最优解目标函数。在求解过程中,若遇到统一纲量问题,可将目标函数具体值与集合中子目标函数值的最大值相除得到;若遇到权重问题,可视目标函数的重要程度加以选取。 由此可得,单目标求最小值函数:
其中为统一纲量,为权重值,且权重值满足。
由于式(4)、(5) 分别为数量上限约束函数,精度约束函数,为得到稳定性目标最小函数值需将式(3) 取倒数。具体步骤为:
1) 构建感知属性- 感知量- 感知设备- 感知网络四要素组成的感知映射关系模型;基于关系模型,在制造单元的感知对象中选定感知属性,籍此逐步建立对应的感知映射集合。
2) 简化求解过程,确定目标函数参数及权重,统一函数纲量。将多目标函数转换为一个或多个单目标函数进行求解。
3) 选择目标函数,优化参数计算,判断约束关系,确定约束条件。若满足约束条件则在新的函数参数集中进行选择计算;反之则丢弃所选函数参数。
4) 完成运算,根据运算结果确定感知设备、感知网络的最优型号。
6结语
本文以制造单元为研究对象,以感知属性为研究节点,有效的对制造单元实体元素进行了分类,梳理了感知量、感知识别设备、传感网络的分类与关系。又建立了以感知实体- 感知量- 感知识别设备- 传感网络为映射关系的多对多映射模型, 对其进行了定性描述。最后利用将多目标问题转化为单目标问题的优化方法,建立映射模型目标函数,设置约束条件,通过纲量归一以及线性加权求和的方式求解目标函数。
摘要：在现代化的生产过程中,需要对制造单元各可感知量进行全程监控,但感知对象数量众多,感知设备种类庞杂,传感网络资源有限,这就需要建立一个基于感知过程的最优映射集合模型,并对其求解。本文通过分析制造单元感知技术,列举感知信息的特点,描述了由感知属性-感知量-感知设备-感知网络组成的感知映射关系模型。最后运用数学的方法对多目标的映射模型进行了优化并实现了求解。
映射优化 第3篇
传统射频电路设计主要借助于解析公式法,但由于公式法的局限性,电路的性能优化主要依赖于后期的调校。主流的优化思路即采用高频仿真软件对电路进行建模优化,然而在解决一些复杂电磁问题时依然可能导致这一优化方案无法有效实施。空间映射[1](SM)算法作为近些年发展起来的一种优化算法,其在射频电路优化方面有着广阔的应用前景。一般射频电路的设计优化问题可根据模型的设计参数(如物理尺寸x)与辅助参数(如介电常数εr、介质厚度h等)分别在商业电磁仿真软件Agilent ADS和Ansoft HFSS中建立粗糙模型和精细模型。凭借两模型之间的数学联系(即映射关系)建立代理模型,至此可将精细模型的优化问题转移至对代理模型的优化上。而精细模型仅用作验证设计参数是否满足设计指标。
文献[2]中提出了隐式空间映射(ISM)算法。作者考虑到辅助参数对射频电路同样具有显著的影响,可使用辅助参数代替传统的数学公式来建立映射关系。然而,在运用标准隐式空间映射算法时,一般迭代优化过程中均可能出现假收敛[7,8](即优化运算落入某个局部最优解停滞的情况),导致建立的映射关系不理想,这也间接影响了后期的优化工作,让整个优化过程变得效率低下。为了解决该问题,本文将差分进化算法[3,4](DE)引入参数提取过程中,通过搜索全局最优解获取理想的映射关系。最后通过优化一种多层结构滤波器来验证该算法的可行性,并与标准算法的运算结果作比较。
1 算法简介
1.1 隐式空间映射算法
一般的空间映射法优化问题可表示为:
式中,xf*表示需要求解的精细模型最优解,Rf代表其响应,x代表过程设计参数,U表示与设计指标ε、Rf(x)相关的目标函数。
隐式空间映射算法在精细模型与粗糙模型之间引入了代理模型[10]的概念。可通过调节辅助参数xp(如介质常数εr、介质厚度h等)建立两模型的映射关系:
通过迭代更新辅助参数xp,匹配粗糙模型与当前精细模型的响应,从而可求得代理模型的辅助参数xp值:
其中,Rc为粗糙模型响应,xp(i)为ISM算法在第i次迭代后提取的辅助参数向量,xc(i)为提取的设计参数。
由精细模型与粗糙模型响应建立的目标函数为:
式(4)为第i次迭代的目标函数。当匹配误差ε(i)小于设定的标准值ε时[2],可认为当前的粗糙模型为代理模型。
最终,ISM算法的最优解问题,可转化为求解代理模型的最优解:
若将xs(i+1)代入精细模型获得的响应Rf(xs(i+1))满足指标要求,则其可作为最终设计值:
反之,则需要按照上述步骤再一次进行迭代优化,直至满足设计指标。
1.2 算法改进
隐式空间映射算法的关键部分是如何建立理想的映射关系。然而,由于参数提取过程存在着不确定性,导致算法在某次执行之后未能获得较为理想的结果,甚至可能存在恶化的现象。而参数提取过程的不稳定性将直接决定映射关系的优劣。差分进化算法是一种用于最优解问题的启发式算法[4],其特有的记忆能力使其可以跟踪当前的搜索情况,并实时调整搜索策略,实现自适应寻优。因此,该算法所具有的全局收敛性和稳定性能较好地弥补隐式空间映射算法在参数提取过程中的不足。为了简化DE算法部分的表达,用向量组xj代替辅助参数向量xp(j为辅助参数的数量),至此算法重心转移到代理模型的获取问题。以下是针对辅助参数xp的处理过程:
其中,D为解空间的维数,[xj-,xj-]为第j个分量的可行域。差分进化算法的执行包括种群初始化、变异、交叉和选择等五个基本步骤:
(1)种群初始化
从可行域内获取初始种群u:
式中,rand[0,1]表示[0,1]之间产生的随机数,g表示当前种群的代数。
(2)变异
每个向量对包括了父代种群中两个成员{xgr2,xgr3}。变异向量由下式产生:
式中,r1,r2,r3∈[1,2,…,NP],且r1≠r2≠r3≠i,NP≥4。F控制差分向量缩放。
(3)交叉试探向量由下式产生:
式中,CR为交叉算子,决定着vig+1对uig+1的贡献值;rand(j)保证试探向量至少有一维变量由变异向量贡献。
(4)边界条件
将落入可行域外的新成员用可行域内随机产生的向量替代:
(5)成员选择
让试探向量成员ug+1i与当前种群中的成员xgi竞争:
选择的过程即是将种群中的成员(即辅助参数)代入粗糙模型中进行反复验证的过程。当新成员的响应优于父代时取子代;反之,保留父代。
当所有成员通过了粗糙模型验证,种群便完成了一次更新(即辅助参数xp完成了一次更新),重复执行上步直至种群中某个成员的粗糙模型响应与当前精细模型响应较好地匹配。至此,便可优化当前的粗糙模型(即代理模型)以搜索最优设计参数。以上为借助于差分进化理论指导隐式空间映射算法完成整个优化工作的说明。改进的隐式空间映射算法流程如图1所示。
2 应用实例
基于LTCC工艺的滤波器[5]在移动通信领域应用广泛,其滤波器结构复杂,使得高频仿真费时费力。本文运用改进的隐式空间映射算法优化LTCC滤波器,验证该算法在应用于复杂射频电路设计时的高效性,并与标准算法的性能作比较。
滤波器的设计指标:
滤波器模型采用9层陶瓷基片。基片厚度h的初值均设为0.1 mm,介电常数εr均设为8.0。假设Hi、εri分别为第i层的介质厚度和介电常数。介质的厚度H1=H2=h1,H3=H4=h2,H5=H6=h3,H7=H8=h4,H9=h5;介电常数εr1=εr2=e1,εr3=εr4=e2,εr5=εr6=e3,εr7=εr8=e4,εr9=e5。辅助参数为xp=[h1,h2,h3,h4,h5,e1,e2,e3,e4,e5]T,滤波器设计变量x=[L1,L2,L3,L4,L5,W1,W2,W3,W4,W5]T,W6为固定值。
根据公式法获得滤波器初始设计参数x(0)=[0.12,0.42,1.06,0.43,0.15,0.29,1.10,1.99,0.64,0.12]Tmm。精细模型的仿真由HFSS执行,粗糙模型则是由ADS运行。差分进化算法对辅助参数xp的处理则在MATLAB中进行。根据设计参数与辅助参数在ADS软件中建立粗糙模型如图2所示。在HFSS中建立的精细模型如图3所示。图4为精细模型最初的响应。由图可知,精细模型响应的中心频率f存在着较大的偏移,而且带内衰减值|S11|、中心插入损耗和带外抑制值|S21|均未达到设计要求。图5为DE算法经历几次迭代后(即种群的迭代,非ISM算法的迭代),从种群中获取与原精细模型最为相近的粗糙模型响应。此时可视为ISM算法第一次建立映射关系(即获得了代理模型),并可凭此模型代替精细模型完成之后的优化任务。根据流程图所示步骤,经过一系列操作后,最终优化效果如图6所示。
精细模型响应Rf的中心频率为f=2.4 GHz,带内回波损耗大于18 d B,中心插入损耗约为0.1 d B,带外衰减也均满足了设计指标。使用新算法仅需精细模型4次介入验证,而标准空间映射算法则需8次才能达到同等的优化效果。两模型的仿真均在主频为2.6 GHz的Intel core i5平台上执行,粗糙模型的一次仿真平均耗时约30 s,精细模型则需花费近20分钟。将改进算法与标准算法的优化用时作统计对比,如表1所示。由于改进算法的粗糙模型执行次数相对标准算法要多出一些,所耗时间也有所增加,但其只需要较少精细模型仿真来进行验证。另外,改进算法中MATLAB耗时基本可以忽略。从最终两算法总耗时情况来看,改进算法在效率上具有明显优势。两者迭代趋势见图7,标准算法在执行到第二次迭代时出现了劣化现象,精细模型响应与设计指标的误差变大,整个过程的收敛趋势过于缓慢,而改进算法则非常稳健地下降直至满足设计指标。
3 结语
本文针对隐式空间映射算法作了改进,在参数提取的过程中引入差分进化算法。通过搜索辅助参数的全局最优解,避免优化过程的假收敛情况,从而获取了良好的映射关系(即理想的代理模型)。实验结果表明,引入差分进化算法后只是少量增加了粗糙模型的运算次数,却换得更为理想的映射关系,从而大大加快了整体的优化速度。由此可见,差分进化算法的引入对隐式空间映射算法的优化过程控制具有很好的指导意义。
参考文献
[1]Bandler J W,Biernacki R M,Chen S H.Space mapping technique for electromagnetic optimization[J].IEEE Transactions on Microwave Theory and Techniques,1994,42(12):2536-2544.
[2]Bandler J W,Cheng Q S,Nikolova N K,et al.Implicit space mapping optimization exploiting preassigned parameters[J].IEEE Transactions on Microwave Theory and Techniques,2004,52(1):378-385.
[3]Lopez C I L,Van Willigenburg L G,Van Straten G.Efficient Differential Evolution Algorithms for Multimodal Optimal Control Problem-s[J].Applied Soft Computing,2003,3(2):97-122.
[4]Rocca P,Oliverri G,Massa A.Differential Evolution as Applied to Electromagnetics[J].IEEE Antennas and Propagation Magazine,2011,53(1):38-49.
[5]刑孟江.基于LTCC工艺的射频无源器件建模与研究[D].西安:西安电子科技大学微电子学与固态电子学系,2012.
[6]Bandler J W,Cheng Q S,Dakroury S A.Space-mapping:the state of the art[J].IEEE Transactions on Microwave Theory and Techni-ques,2004,52(1):337-361.
[7]Koziel S,Bandler J W,Cheng Q S.Constrained parameter extraction for microwave design optimization using implicit space mapping[J].IET Antennas and Propagation Magazine,2011,5(10):1156-1163.
[8]Koziel S,Cheng Q S,Bandler J W.Implicit space mapping with adaptive selection of preassigned parameters[J].IET Antennas and Propagation Magazine,2010,4(3):361-373.
[9]Koziel S,Bandler J W,Cheng Q S.Adaptively Constrained Parameter Extraction for Robust Space Mapping Optimization of Microwave Circuits[J].IET Antennas and Propagation Magazine,2010,5(10):205-208.
映射优化 第4篇
关键词：无线传感器网络,基因位映射,量子遗传算法,能耗优化,粒子群
无线传感器网络是具有自组织多级跳特征的, 由大量传感器以无线通信方式组成的网络系统, 它与移动自组网相比, 节点的能量有限, 因此计算能力和通信距离受限[1]。针对无线传感器网络能量均衡和有效利用一直都是无线传感器网络研究的重要内容[2]。文献[3]提出了LEACH (low-energy adaptive clustering hierarchy) 算法进行节点簇头竞选, 依靠轮流机制均衡网络系统能量, 该算法在节点多级跳时会出现离簇头节点较远的节点能耗过大而提前死亡;文献[4]提出了EEUC算法, 设置阈值来判定节点是否可以成为簇头, 判定成为簇头的节点根据接收的节点信号计算间距, 从而构成不同的竞争域, 使得节点能量较大的成为簇头节点, 簇头在下级跳时选择节点能量最大的进行数据转发。但该算法的参数需要人工给定, 算法性能稳定性差;文献[5]提出了一种人工免疫响应的最小能耗拓扑控制算法, 以调整节点的发射功率来选择合适的节点参与数据转发, 但该算法对于节点发射功率的不能自适应控制, 对抗体亲和力计算函数的合理性没有论证。针对以上研究, 现提出进化激励的无线传感器网络节点分簇路由能量优化算法, 通过对节点进行簇头竞争, 将网络系统进行节点分簇, 然后将簇间的数据交互能耗优化问题转化成为簇间最优能耗跳级数的节点路由路径搜索问题。实验证明该算法可有效地延长网络系统的生命周期。
1 无线传感器网络节点能量优化路由模型
设无线传感器网络中节点i发送k比特数据到通信半径为d的节点j所需能耗为ET, 则
节点j接收数据的能耗为ER, 则
式中, εamp为节点信号放大系数, Eelec是电路能耗。
设节点融合数据时, 能耗为E (k) , 则
无线传感器网络节点的能耗主要包括簇内通信和簇间通信能耗, 簇头能耗主要是簇内成员节点数据交互和簇头节点接收发送数据所需的能耗, 则
式中, 簇内成员节点个数为m, 第i个节点和簇头的间距为di。则簇内能耗的降低可通过减少簇内成员节点数据交互次数, 或者构造簇头为中心聚类簇来实现。
簇间能耗主要是簇头节点以跳级模式进行数据交互时所需的汇聚节点能耗, 则
式中, 第i个簇头的邻居簇头个数为q, 第i个簇头下一级跳簇头节点的距离为di。
无线传感器网络分簇路由是将网络分为若干簇单元, 每个簇单元由簇头节点和若干个成员节点组成。分簇包括簇头节点竞选和新簇构造。簇头节点竞选时依照竞争机制, 选择节点能量高于网络平均能量的节点作为候选竞争节点。竞争域为节点邻域, 设邻域半径为Ri, 则
式中, 节点数据到汇聚节点距离区域为{dmax, dmin}, 节点si和汇聚节点的间距为d (si, sink) , 竞选最大半径为R, 则候选竞争节点的域半径为节点与汇聚节点间距的单调递增函数。
设无线传感器网络中簇头节点通过簇间多级跳进行数据转发, 并将其数据信息传递到汇聚节点, 因此节点的能量距汇聚节点越近, 能耗越大, 但簇内能耗的降低可均衡簇间能耗, 实现簇头能耗均衡。由于簇间节点需要在邻域范围内的邻居簇头中选择中继节点作为多级跳中转数据转发节点, 因此合理地对多级跳中继节点进行选择, 是无线传感器网络分簇节点路由能量优化和延长网络寿命的关键。
设无线传感器网络簇头节点和汇聚节点的关系为图G (V, E) , 令V={S, H1, H2, …, Hm}为节点集合, m为簇头数目, Eij∈E为Hi到H的传输成本, 则有
式中, 簇头节点i转发k比特数据到距离为d的簇头j时所需能耗为C (i, j) , 则:
设无线传感器网络中有N个节点, 经过分簇聚类后生成k个簇, 则无线传感器网络节点能量优化问题可转化为网络系统节点从发送簇头到目的簇头的最优能耗路径问题。即
2 基因位迭代映射的进化算法
2.1 量子遗传算法
2.1.1 量子比特编码与测量
量子遗传算法[6]中的最小单位为量子比特位, 它定义为复数对。量子比特是作为信息存储单位的物质介质双态量子系统, 是二维复向量空间中的单位量, 因此它可以表示为空间中两个量子态的叠加。设|φ〉=α|0〉+β|1〉, 其中0为自旋向下态, 1为自旋向上态, |〉为量子态, 〈α, β〉分别为〈0, 1〉的复数概率幅, 且|αi|2+|βi|2=1, (i=1, 2, …, m) , |α|2可看为量子自旋向下的概率, |β|2可看为量子自旋向上的概率。则当量子比特位为0时, |α|2=1, |β|2=0;当量子比特位为1时, |α|2=0, |β|2=1;当量子比特位为叠加态时, |α|2≠0, |β|2≠0, 即量子比特位处于中间叠加态。
使用该方法进行二进制编码, 令0态对应染色体各基因位映射值0, 1态为染色体各基因位值为1;|αi|2和|βi|2分别表示基因位上取值, 〈0, 1〉的概率。设系统有M个量子比特位, 则该系统的概率幅P可表示为
设种群规模为N, 则P={P1, P2, …, Pn}。对种群的个体进行测量, 将个体的不确定概率进行状态确定, 则个体Pj∈P (j=1, 2, …, n) 为长度M的二进制串编码 (X1, X2, …, Xm) , 其中在区间[0, 1]内随机生成概率数R, 若R≥|α|2, 令X1为1, 否则为0。
2.1.2 量子旋转门
量子旋转门通过量子门变换矩阵来实现种群的更新。量子门变换矩阵是可逆的归一化矩阵, 即U*U=UU*=1 (U*为U的共轭转置矩阵) 。常用的量子旋转门为
式中, [αi, βi]T为染色体中对应为测量的第i个量子位, θi为旋转角, 其调整策略为θi=s (αi, βi) Δθi, 具体取值参见文献[7], 其中染色体第i位对应xi, 当前种群中最优染色体j的第i位为besti, 旋转角度的大小为Δθi, 适应度评估函数为f (x) , 旋转角度的方向为s (αi, βi) 。
显然, 按照上式可使算法收敛, 不同的Δθi取值, 算法的收敛效果不同。
2.2 量子遗传算法的改进
2.2.1 染色体基因测量长度的自适应评估
现有的二进制编码量子遗传算法基于固定编码长度, 对于不同的问题其算法求解精度低、收敛速度较慢。且当染色体基因长度测量值较短时, 可能无最优解;相反则会耗时在进化计算过程中, 最优解也无法保证。因此对种群适应度值计算的精度要求需要对基因长度进行自适应计算, 保证染色体基因长度在进化计算过程中可以满足算法的精度要求, 并具有较好的计算效率。
设基因长度自变量的计算精度为Xa, 则
式中, (Max, Min) 为值域的最大值和最小值, N为二进制编码的染色体基因长度。
染色体等位基因长度的计算步骤如下:
Step1初始化染色体长度Len, 对其赋予较小的整数, 并对其自变量精度进行计算;
Step2随机地对选择的个体的适应度值进行计算;
Step3对选择的个体进行扰动, 扰动范围为±自变量值的计算精度, 对扰动个体的适应度值变化进行计算;
Step4对扰动个体的适应度值变化进行排序, 输出最大值;
Step5对扰动个体的适应度变化最大值判定其是否满足种群适应度值计算精度的要求, 若不满足, 则增加染色体的基因长度, 转step3进行迭代;
Step6输出符合自变量精度要求的染色体基因编码长度Len。
根据以上算法对染色体基因长度进行自适应调整计算, 将Len的值作为相应的染色体基因编码长度, 可以有效地解决染色体基因固定长度算法中存在的求解精度较低或收敛速度较慢的问题。
2.2.2 改进粒子群算法的量子旋转角度动态调整
对染色体基因长度进行自适应计算时, 随机的扰动系数Δθi影响着算法的收敛速度。当Δθi较大时, 算法的搜索值域较大, 搜索解的间距变大会引起算法的搜索精度降低;否则当Δθi取值较小, 算法的搜索值域较小, 搜索解的间距变小会引起算法搜索的收敛速度较慢。因此对量子旋转角度进行动态调整, 以当前解空间的位置与当前最优解空间的汉明距离为度量, 若当前个体与当前最优解的距离较远, 则对扰动系数Δθi赋予较大的值, 减少其进化迭代次数;否则赋予较小的系数值, 增强其局部搜索的精度。这和粒子群算法中的全局搜索和局部搜索特征相同, 将当前个体与当前最优个体最接近距离的搜索解问题转化为粒子的全局寻优问题, 则粒子的惯性为线性递减时, 算法收敛的极值点未必为解的极值点, 对惯性值赋予动态的惯性值有利于算法进入局部搜索, 更能接近最优解。文献[8]提出了粒距, 设在第t次迭代计算时第j个粒子在第i维空间中的粒距为dij (t) , 则
因此其粒子的汉明粒距为Ham Dij (t) =|xij (t) , gbesti (t) |, 代表两个染色体基因向量中相应位置不同个体的个数, 则
对当前第t次迭代计算的粒子在旋转角度方向s (αi, βi) 上按照基因长度自适应计算的精度及扰动的适应值变化进行排序, 构成当前粒子个体的粒子粒距序列, 将当前粒子个体在粒距序列对中的概率进行计算, 若当前粒子个体的扰动适应度值最大, 且计算精度最高, 当前个体越接近最优解。设当前环境中粒距序列为X (dm) , 则当前粒子个体i的特征响应函数J的属于第n个粒距的概率为
式中, |n|为当前个体扰动时计算的最接近的粒距对, 其满足条件为
且代表第m个粒距中第i个粒子的第j维旋转角度上的特征响应函数均值。|m|为当前计算中总的粒距数目, 则粒子个体i在当前迭代计算中的信息熵为
设当前粒距序列对中随机地选择粒子i', 其特征响应函数值为J'i, 则
…, n, 其中|J'1|为粒距的粒子个体特征响应函数值的中位数均值。则满足约束条件的粒距为粒距序列对中的第n'个粒距, 则粒子在粒距中的平均信息熵为
则对于任意迭代计算的粒子惯性权函数时, 有:
式中, wstart=0.95, wend=0.05, tmax=1 000。
2.2.3 自适应变异算子
当进化算法执行到一定阶段时, 种群粒子个体的多样性会降低, 从而影响粒子较难收敛到全局极值点。现有的量子遗传算法主要是通过量子非门来实现量子比特的变异, 文献[9]分析了这种变异的局限性, 分析表明该变异策略有可能对于变异前的搜索范围仅增加了一个较小的局部区域, 当算法的种群多样性降低, 陷入局部搜索时很难跳出局部最优解空间。因此引入柯西变异、高斯变异和利维变异算子, 对粒子种群的多样性进行组合改进, 以1/3的概率选择变异算子, 对量子比特进行变异操作。设粒子个体随机扰动的特征响应函数J为粒子的速度v, 粒子个体的相邻位序为位置x, 全局最优速度为vg, 全局最优位置为xg, 则有
式中 (δ, δg) 表示柯西随机分布的尺度参数为1。
式中 (N, Ng) 表示高斯分布的均值为0, 方差为1。
式中, (L (α) , Lg (α) ) 为利维随机分布, α=1.3, 详见文献[10]。
在进行变异时, 对每次选择的变异算子变异后的后代适应度值进行评估, 若利用该变异算子进行变异操作的后代适应度值相比较未经变异或适应度值低的后代其成为最优解的几率要高, 则选择该变异算子。通过该方法逐步对种群中所有粒子的最优变异算子进行自适应选择, 选择步骤如下。
每个变异算子迭代繁殖的进步值评估
式中, pji (t) 和cji (t) 分别为变异算子i在迭代t次时父辈和子辈的适应度值, Mi为选择变异算子i时参与变异的个体数量。
每个变异算子的激励值计算
式中, Si是经过变异算子i变异后子辈有更好适应度值的粒子个体数量, pi (t) 是在第t次迭代繁殖时选择变异算子i的概率, α为 (0, 1) 间的随机权重, N是变异算子的个数, ci是变异算子的惩罚因子, 则
对变异算子赋予最大的激励值, 使其尽可能对每次迭代中的局部最优值进行变异。
子辈变异算子选择概率的更新
式中, γ为变异算子的最小选择概率, 其值设为0.01。子辈变异算子的选择概率主要依据四个因素:进步值、最小选择概率、历史选择概率和最优的突变概率, 每次迭代繁殖后, 都会相应地变异算子选择概率进行更新。
3 基于基因位迭代映射的无线传感器网络能量优化分簇算法
网络能量优化算法。
Step1网络节点竞选分簇;
Step2初始化遗传个体种群, 将解可行域中的候选解作为染色体进行二进制编码, 并根据设定的计算精度进行自适应编码长度计算;
Step3初始化每个个体的基因概率幅为
Step4对染色体个体的基因位进行观测, 计算每个个体的适应度值;
Step5依据量子旋转角度更新策略对量子进行旋转, 旋转系数根据改进的粒子群算法的个体信息熵赋值。利用量子旋转对种群进行迭代更新, 可以得到子辈的种群;
Step6设置初始的种群个体变异算子概率为1/3;
Step7对于每个个体, 若其适应度值大于历史最好位置的适应度值, 更新pi;
Step8对于每个个体, 若其适应度值大于全局最优位置的适应度值, 更新pg;
Step9若第一适应度计算值不为零, 则step10, 否则计算个体的第二适应度值, 将其值与个体历史最好位置pi作比较, 若更优, 则更新pi;若pi更新后, 将其值与个体种群历史最好位置pg作比较, 若更优, 则更新pg;
Step10根据变异算子对种群中一定比例的个体进行变异操作;
Step11计算粒子的进步值和激励值, 选择三个变异算子中最好的变异算子, 并在每次迭代繁殖后更新算子的选择概率;
Step12赋予全局最优个体邻居粒子最大的激励变异率, 并选择最优邻居变异率中最大值生成p'g;
Step13对比p'g和pg, 选择最优的值进行子辈繁殖;
Step14迭代地进行繁殖, 输出符合收敛条件的节点通信路由路径;否则转Step4。
4 实验仿真
实验仿真环境:Intel Corei5—5 304 G内存Windows XP系统的PC机, 仿真平台为NS2。为了对该算法进行验证, 将其与LEACH和ENCA算法进行对比, 能耗参数设置参照ENCA算法, 参数见表1。
节点分簇时, 依据节点剩余能量进行竞选, 节点能量的有效利用和聚类是网络寿命延长的关键。图1为三种算法在同一参数环境下的能耗。
图1可知, 本文算法在整体上比LEACH算法和ENCA算法能耗更优。这主要是由于本文算法在进行节点数据转发时将最小能耗问题转化为最优能耗路径搜索问题, 利用改进的遗传算法进行候选路径编码, 在量子旋转角度时利用粒子群算法进行最优旋转角度计算, 保证了节点能耗的最优化。但LEACH算法的簇头信息要在整个网络系统中传递, 节点的数据广播半径也较大, 节点的能耗偏大, 当节点竞选簇头时, 对节点持有能量没有进行约束, 可能会导致能量最小的节点当选为簇头节点。而ENCA算法虽然对节点能量进行了约束, 但是簇头选择是局部最优, 网络系统的整体能耗最优难以保证。
在同等参数条件下对三种算法中的网络存活节点个数进行统计, 取300次实验中存活节点的平均数进行网络生命周期对比, 仿真如图2所示。
由图2可知, 本文算法相对比LEACH算法和ENCA算法网络生命周期更优, 相对比ENCA算法, 本文算法的生命周期延长了18%。
5 结语
通过对无线传感器网络节点分簇路由能耗模型进行研究, 对网络系统能耗产生的主要问题进行分析, 提出以分簇减少节点的基于基因位迭代映射的无线传感器网络能量优化分簇算法, 利用量子遗传算法对簇间节点跳级路由路径进行映射, 在网络生命周期内进行数据的多级转发, 对具有最优能耗的节点跳级路径进行搜索, 有效地提高了节点的能量利用率。
参考文献
[1] Akyildiz I F, Su W, Sankarasubramaniam Y, et al.Wireless sensor networks:a survey.Computer Networks, 2002;38 (4) :393—422
[2] Ren Fengyuan, Huang Haining, Lin Chuang.Wireless sensor networks.Journal of Software, 2003;14 (7) :1282—1291
[3] 赖娟.基于改进的蚁群算法中文词语自动分类技术研究.科技通报, 2012;28 (2) :152—154
[4] Li Chengfa, Ye Mao, Chen Guihai, et al.An energy-efficient unequal clustering mechanism for wireless sensor networks.//Proc of IEEE International Conference on Mobile Ad hoc and Sensor System.Washington DC:[s.n.], 2005;14 (7) :1582—1691
[5] 陈拥军, 袁慎芳.无线传感器网络最小能耗拓扑控制研究.电子科技大学学报, 2012;41 (4) :568—573
[6] Han K H, Kim J H.Genetic quantum algorithm and its application to combinatorial optimization problem//Proc of IEEE Congress on EvolutionaryComputation, 2000:1354—1360
[7] 梁昌勇, 柏桦, 蔡美菊.量子遗传算法研究进展.计算机应用研究, 2012;29 (7) :2401—2405
[8] 阳春华, 谷丽姗, 桂卫华.自适应变异的粒子群优化算法.计算机工程, 2008;16:188—190
[9] 王竹荣, 杨波, 吕兴朝.一种改进的量子遗传算法研究.西安理工大学学报, 2012;28 (2) :145—151
映射优化 第5篇
混沌是一种复杂的非线性、非平衡的动力学过程[1]。混沌是自然和人类社会普遍存在的一种现象。混沌现象中,初值或参数发生微妙变化,结果就会大不一样。甚至一些一维非线性迭代函数就能够显示混沌特性,这类现象的数学模型十分简单。因此有人寻找这种混沌函数作为密码算法中的密钥流产生器,用以构成性能良好的密码系统。
本文实现了对Txt文本文件进行加密解密。软件环境是Microsoft Window XP Professional操作系统,编程环境是Microsoft Visual Studio 6.0,算法采用C++语言编写。加密系统适应了高速网络传输的信息保密需要,使网络传输更科学、更安全。即使文本信息在传输过程中被截获,也是一些杂乱无章的乱码。
1 Logistic映射与Henon映射
Logistic映射是一个一维一次映射。考虑Logistic方程Xn+1=r Xn(1-Xn),当r>3.57(令r∞=3.57)时,时间序列x1、x2、x3….xn,如同分布在[0,1]上的随机数,称为混沌。
Henon映射是一个二维非线性映射,因其独特的混沌吸引子而被人们所关注。Hitzl等对Henon映射作了深入研究,并将其推广到三维的情形,即
称为广义的三维Henon映射,当1.07≤a≤1.097和b=0.3时,式出现混沌现象。
2 算法实现
本文分别用Logistic映射和Henon映射产生和明文相同长度的密钥流。加密时,将明文与密钥进行异或处理,从而产生密文。解密时,将密文与明文进行异或处理,从而产生明文。加密和解密是个逆过程。本文实现了对txt文本文件进行加密和解密。加密解密结果如图1、2所示。
3 实验分析
3.1 序列分析
密钥流的性质直接关系到整个流密码系统的安全性,是一个极为重要的指标。我们对改造算法产生的密钥流进行频率测试、游程测试和自相关性测试等。在实验中,我们删除了序列的前1000个序列,然后取序列的连续100000个比特进行测试,其结果如表1所示。
从表中数据对比可以看出该改造算法得出的伪随机序列具有以下特征:序列中的0的个数和1的个数几乎相等;序列中长度为1的游程约占游程总数的1/2,长度为2的游程约占游程总数的1/4,长度为3的游程占游程总数的1/8,…,在同长度的所有游程当中,0的游程和1的游程各占一半。
3.2 仿真实验
我们对Logistic映射产生的序列进行了仿真实验。映射的参数我们取为3.58,映射的初值我们取为0.53。我们取序列的长度为1000。X轴方向的值就是序列的第几个。Y轴方向的值就是xi的值。从图3我们可以看到,混沌序列具有便历性和非周期性。序列几乎覆盖了0到1的任意点。序列杂乱无章,没有出现周期性。
我们对Henon映射产生的序列进行了仿真实验。映射的参数我们取为1.08,映射的初值我们分别取为0.4、0.6和0.8。我们取序列的长度为1000。X轴方向的值就是序列的第几个。我们将此序列向右移动100位。然后我们把映射的参数取为1.0801,产生新的序列。然后我们把新的序列和原来的序列xi进行比较,得出两个序列的差值。Y轴方向的值就是xi的差值。从图4可以看到,混沌序列对初值极端敏感。初值相差0.0001,序列便产生巨大的变化。把新的序列和原来序列比较,相同的个数和不同的个数接近。
4 结论
通过序列分析和仿真实验,证明了混沌映射具有对初值极端敏感、便历性、非周期性和类随机性等特点。我们可以将混沌映射的初值和参数作为加密系统的密钥,将混沌映射产生的序列作为加密系统的密钥流,从而实现对Txt文本文件进行加密和解密。加密系统所产生的序列符合随机序列的随机特性应该具有的几个主要的概率特征,混沌序列非常适合用于作为密码算法中的密钥流产生器,用以构成性能良好的密码系统。
参考文献
[1]向菲,丘水生.基于混沌系统互扰的流密码设计[J].物理学报,2008(10).
[2]张连俊.图像混沌加密技术分析[J].现代情报,2005(8).
映射优化 第6篇
关键词：混沌,图像加密,Cat映射,Henon映射
0 引 言
随着多媒体通信技术的迅速发展,大量包含情报的图像信息在网上传输越来越频繁,图像的安全和加密技术变得越来越重要。1997年,Fridrich 首次将混沌加密方法应用到图像加密中[1,2]。此后,许多学者致力于混沌图像加密方法的研究,混沌加密技术作为一种新的加密技术得到了快速的发展。常用的混沌图像加密的思想主要有三种:对图像像素空间位置置乱,对图像灰度值变换,对空间位置与灰度值均进行加密操作。所谓空间位置置乱,就是通过某种方式打乱图像像素的排列,使得原始图像的内容变得杂乱无章。图像灰度值变换,是通过混沌映射产生的混沌序列与原始图像的灰度值进行某种运算,通过改变原始图像的灰度值而达到加密的目的。但是目前绝大多数混沌加密算法实质上是单一的图像像素值置乱或图像像素位置置乱,而单一的使用其中任一种都无法保证图像具有较高的安全性。图像像素值置乱对于唯密文攻击具有较强的安全性,但对于已知明文的攻击,存在一定的安全隐患;图像像素位置置乱只改变了图像的位置,没有改变图像像素值,因此,这种加密方法,攻击者可以通过像素比较的方法加以破解。
本文利用Arnold cat映射和Henon映射,构造出一种双混沌加密系统。首先利用Arnold cat映射构造位置置乱矩阵,通过位置置乱矩阵对图像的各像素点的位置进行置换, 然后利用Henon映射进行像素值置乱。实验结果表明,该算法具有较高的安全性和快速性,能够抵抗统计攻击和穷举攻击等。
1 两个离散混沌系统:Cat映射和Henon映射
1.1 Cat映射
Cat映射是 Arnold 在遍历理论研究中提出的一种变换,设有单位正方形上的点(x,y),将点(x,y)变到另一点(x′,y′)的变换为:
此变换称作二维Arnold变换,简称Arnold变换[3]。
对于数字图像,我们把上面的二维Arnold变换作如下改变:
其中,xn、yn是N×N图像的像素点位置,a、b是系统的参数,取正整数。该变换通过把原图像中像素点(xn,yn)变换到加密图像中像素点(xn + 1 ,yn + 1 ),改变原图像的像素点位置,从而实现加密。但单纯依靠置乱像素位置安全性不高,因为置乱后图像的像素值并没有改变,所以图像的像素直方图不变;另外由于Cat映射具有庞加莱回复性[4,5],经过多次迭代后可以恢复出原始图像,于是需要一步对置乱后的图像进行像素值层面上的加密。
1.2 Henon映射
随着混沌加密技术的发展,单纯的基于一维混沌映射的加密技术已经不能满足实际要求,级联几个一维混沌系统或者发展高维的混沌系统成为了发展的必然。Henon映射[6]是应用最为广泛的二维混沌映射之一,其映射方程T如下:
T:
当a=1.4,b=0.3时系统处于混沌状态。
由映射方程可以看出,Henon映射是由两个变量x和y同时确定迭代方程,这比单纯联立两个相互独立的一维混沌方程要复杂很多。
2 算法设计
本文采用的加密方法的流程图如图1所示。
加密过程如下:
1) 输入要加密的图像A,得到图像的大小M×N,进行边界填充0(黑色),使图像长和宽相等。假设处理后的图像大小为N×N。
2) 进行像素位置置乱。输入密钥(a,b,n),a和b为控制参数,n为置乱的次数。取a=3,b=4,n=10,按照公式(2)把图像A进行像素位置置乱,得到置乱加密后的图像A1。
3) 产生Henon混沌序列。取a=1.4,b=0.3,x0=0.20,y0=0.10按照公式(3)进行迭代1000次后开始取值,产生两组N×N的序列,分别是{xk|k=0,1,2,…,N×N},{yk|k=0,1,2,…,N×N}。
4) 对产生的两组混沌序列进行一定的处理。取每个元素的小数点后第4、5、6位组成一个新的整数序列,对产生的整数序列对256进行取余,并将结果转化成二进制。
5)像素值置乱加密。将Cat映射加密产生的图像A1的像素点的值转化成二进制,并与产生的两组混沌序列的对应元素进行异或处理。
公式为:xk⊕yk⊕A1(k),其中A1(k)为第k个点的像素值。共运算N×N次,完成全部加密。
6) 将N×N个结果再转化为十进制,变回二维图像,完成图像像素值的置乱加密。
解密过程为上述过程的逆过程。
3 仿真实验和算法分析
按照本文算法,对488×520的Lena图像,在CPU T5450,2G内存的电脑上进行Matlab仿真实验,加密时间为0.413091秒,加密前后的图像如图2所示。其中(a)为原始图像,(b)为按照本文中所给出的加密密钥进行加密后的图像。
3.1 密钥空间分析
为了防止被穷举攻击,加密方案必须具有尽可能大的密钥空间。在本文中,采用Cat映射变换和Henon映射加密相结合的方式进行。Cat映射变换需要三个控制参数,Henon映射需要2个控制参数和2个初始值。Henon映射2个初始值的精度为10-16,加密过程中的密钥空间为1032,加上2个控制参数和Cat映射的三个参数,本文算法的密钥空间远远大于1032,可以有效地抵抗穷举攻击。
3.2 密钥敏感性测试
加密密钥敏感性测试结果如图2所示,其中(a)为原始图像,(b)为按照本文中所给出的加密密钥进行加密后的图像,(c)为正确解密后的图像,(d)为把Henon映射中的正确解密密钥x0=0.20增加一微小量0.000 000 000 000 01后的解密图像。从加密解密图中我们可以看出,当解密密钥在不小于10-16的范围内进行微小变化时,解密的图像变化很大,导致了解密失败。所以本算法对密钥具有极强的敏感性。
3.3 直方图分析
加密后图像的直方图与原始图像的直方图如图3所示,上图是加密前,下图是加密后图像的直方图。从图中可以看出加密后图像的像素值分布非常均匀,很好地掩盖了原始图像的分布规律,增加了恶意攻击者的破译难度。
3.4 不动点比和灰度平均变化值
不动点比和灰度平均变化值是反映图像加密前后灰度变化程度的变量。通过本文采用的加密算法加密的图像的不动点比为0.3846%,灰度平均变化值为76.389,从这个值可以看出本算法的置乱效果较好。
3.5 信息熵
信息熵反映的是图像中的灰度分布情况,分布越均匀,信息熵越大,包含的不确定信息就越多。本文中原始图像和加密后图像的信息熵分别为6.7181和7.9683,从上述数据可以看出加密后的图像信息熵明显增大,接近灰度级为256的图像的最大信息熵8。
3.6 相邻像素的相关性
表1所示为原始图像和其加密图像在三个方向上的相邻像素之间的相关系数。可见,原始图像的相邻像素相关性较大,加密后的图像相邻像素的相关性接近于0,达到了很好的扩散的目的。
相邻像素的相关性反映出图像像素的扩散程度,相关性越小说明加密算法的扩散效果越好。所以加密时,应该让加密后图像的相邻像素的相关性尽可能地降到最小。从原始图像和加密后的图像中分别从水平、垂直和对角方向选取10000对像素对,测试其三个方向的像素相关性,并计算相关系数。
4 结 论
混沌理论作为一门新兴的学科已经显示出巨大的研究潜力,把它和密码学相结合,对一些重要的图像信息进行加密,对于确保图像信息的安全具有非常重要的作用。对图像信息应用Arnold cat映射和Henon映射进行双重加密,在位置置乱的基础上再进行图像像素值的置乱,有效地实现了混淆和扩散的目的,克服了单纯依靠像素位置置乱或者像素值置乱存在的问题,提高了图像信息的安全性。通过实验分析,本文所提出的算法具有较好的可行性和较高的安全性。
参考文献
[1]Fridrich J.Symmetric ciphers based on two-dimensional chaotic maps[J].International Journal of Bifurcation and Chaos,1998,8(6):1259-1284.
[2]Fridrich J.Image encryption based on chaotic maps[J].Systems,Man and Cybernetics Computational Cybernetics and Simulation,1997,2(1):1105-1110.
[3]丁纬,闫伟齐,齐东旭.基于Arnold变换的数字图像置乱技术[J].计算机辅助设计与图形学学报,2001,13(4):338-341.
[4]Chen G R,Mao Y B,Chui C K.ASymmetric Image Encryption Scheme Based on3D Chaotic Cat Maps[J].Chaos,Solitons and Fractals,2004,21(3):749-761.
[5]田云凯,贾传荧,王庆武.基于Arnold变换的图像置乱及其恢复[J].大连海事大学学报,2006,32(4):107-109.
纹理映射技术算法综述 第7篇
纹理映射 (Texture Mapping) 是将纹理空间中的纹理像素映射到屏幕空间中的像素的过程, 是绘制复杂场景真实感图形的最为常用技术之一, 是计算机图形学中引人注目的研究方向之一。近年来, 随着计算机技术的飞速发展, 纹理映射技术研究也有了长足的发展, 其应用领域也越来越广阔。传统的光照模型只考虑到物体表面法向的变化, 并且将其表面视为一个镜面, 反射率视为一个常数, 只能生成颜色单一的光滑景物表面。实际景物的表面存在丰富的纹理细节, 对光线的反射是一个漫反射, 传统的技术方法难以模拟实现, 纹理映射技术的出现为解决上述问题提供了方法。利用计算机模拟制作真实感图形是纹理映射应用的主要方向。
纹理映射的实质是建立了从屏幕空间到纹理空间的映射和纹理空间到景物空间的映射两个映射关系。应用合适的纹理, 可以方便地制作真实感图形, 而不必花费更多的时间去考虑物体的表面纹理。纹理映射在宏观层面一般使用颜色纹理, 为物体表面贴上真实的色彩花纹, 模拟真实的现实色彩;在亚宏观层面, 则采用更精细的几何纹理, 以表现物体表面的凹凸不平、纹理细节以及光线阴暗与明亮的变化;对于复杂的、连续的曲面进行仿真, 则需要过程纹理映射来模拟。
2 纹理映射算法综述
根据使用纹理函数的不同, 纹理可分为一维纹理、二维纹理和三维纹理;根据纹理的表现形式, 纹理又可分为颜色纹理、几何纹理和过程纹理三大类。从数学的观点来看, 映射M可用下式描述:
若F可逆, 则
纹理映射算法一般有以下三个步骤:
(1) 定义纹理对象, 获取纹理;
(2) 定义映射函数。在纹理空间和物体表面空间定义相应的映射函数;
(3) 选择纹理的重采样方法。通过映射函数将纹理映射到物体空间后, 选择一种重采样方法, 降低映射纹理的各种走样。
纹理映射技术算法主要是解决建立怎样的映射函数, 怎样合理合成纹理, 减少映射后纹理的形变与走样, 怎样剔除映射后纹理图像中的光照效果, 体现真实效果。纹理映射发展了很多算法来解决这些问题, 如正向映射法、逆向映射法、两步法、环境映射等。
2.1 二维纹理映射
2.1.1 正向映射法
正向映射法一般采用Catmull算法, 该算法通过映射函数, 将纹理像素坐标与物方曲面坐标进行一一匹配, 确纹理像素坐标在物方曲面的位置及大小, 按双线性插值将纹理像素中心灰度值赋予物方曲面上相应点, 并取对应点处的赋予的纹理颜色值作为该曲面处像素中心采样点的表面纹理属性, 再用光照模型来模拟计算该曲面点处的光亮度, 赋予其灰度值。正向映射算法可表示为:
具体流程图1所示。
正向映射实现相对较为简单容易, 但是缺点也非常明显, 首先纹理映射值只是纹理图像的灰度值, 再者在映射过程中物方空间与纹理空间并不能完全对应, 而是会产生一定的变形, 这就导致纹理映射到物方曲面时, 部分区域没有对应的纹理像素或多余的纹理像素, 从而产生空洞或多射, 引起图形混淆, 因而正向映射在实际应用中很少使用。但由于正向映射能够顺序存取纹理图案, 故能在计算中节约大量的存储空间, 提高计算速度, 对于小计算量的映射还是有较强的应用性。
2.1.2 逆向映射法
逆向映射法实际上是正向映射一个逆向, 该方法也称之为屏幕扫描法。逆向映射法是通过映射函数, 将物方曲面坐标反算至纹理空间坐标, 将物方空间与纹理空间一一对应, 在利用重采样方法对纹理影像进行重采样, 计算对应物方曲面空间的坐标中心的像素值, 再将计算结果赋予物方曲面即可。逆向映射法算法可如下表示:
算法流程表示见图2所示。
逆向映射法克服了正向映射法的缺点, 能有效实现图形反混淆, 实现了纹理空间与物方空间的完全对应, 因而在不仅纹理映射中广泛使用, 在计算机图像处理中也在使用这一思想, 如遥感影像纠正时, 便采用了逆向映射的原理。逆向映射法要对物方空间进行基线扫描, 计算变换矩阵, 搜索基线上每一个像元, 对于每个像元又需要随时进行重采样, 为了提高计算效率, 要求动态存储纹理图案, 这也导致逆向映射法计算需要占用大量的存储空间。为了提高逆向映射算法的计算效率, 学者们做了大量研究, 也提出了很多改进算法, 这些算法主要是分为两个方向: (1) 基于纹理图像, 对图像的搜索和匹配做出优化; (2) 基于场景, 重建三维场景来优先获取像素信息。这些算法都极大的提高了逆向映射算法的计算效率。
2.1.3 两步法纹理映射技术
复杂的物方曲面一般是非线性的, 很难直接用数学函数进行参数化, 故而很难建立物方空间与纹理空间的对应关系。两步法纹理映射技术便主要解决了这种无参数化曲面的纹理映射问题, 其基本思想是建立一个中间三维曲面, 将纹理空间到景物空间的映射分解为纹理空间至中间三维曲面, 中间三维全面至物方空间两个简单映射的复合, 从而避免了对景物表面重新参数化。
两步法纹理映射的基本过程可分解为:
(1) 建立如下映射, 将二维纹理空间映射至一个简单的中间三维物体表面, 这一映射过程称之为T映射
(2) 将上述映射到中间三维物体表面上的纹理映射到物方景物表面, 可称之为T'映射:
两步法纹理映射可以较好的解决物方曲面无法参数化时进行映射的问题, 但是由于物方曲面并不能只用一种简单的三维曲面进行模拟, 所以必须采用交互式的方法, 不断变换中间三维曲面, 以保证与物方曲面的相似度, 才可以保证最终的纹理映射效果。示意图见图3所示。
2.1.4 环境映射
环境映射技术是模拟出光滑表面对周围环境的反射技术, 实际上就是将一幅包含物体周围环境场景的纹理映射到物方空间表面, 这样就可在不使用光线跟踪算法等复杂算法的情况下, 在一定程度上模拟出物体对周围环境的映射, 而无须使用像光线跟踪算法这种复杂的计算技术将空间光照模型作为纹理映射到物体表面。环境映射示意图见图4所示。
1976年, Blinn和Newell就提出第一个环境映射算法, 通过将环境纹理贴到球体的映射空间上;1986年, Greene提出立方体环境纹理, 立方体环境纹理映射采样均匀, 绘制简单, 可以从照片直接生成效果很好。球形环境映射和立方环境映射也是环境映射最为常用的两种方法。
环境纹理映射效果与光线跟踪算法相比较, 计算速度快, 效率高, 但是环境纹理映射只是对实际反射的一种近似模拟, 并且没有自反射, 不能反射自身情况。
2.1.5 几何纹理映射
有些物方空间曲面并不是光滑的, 而是凹凸不平的, 光线照射在上面时会产生随机漫反射现象, 采用固有的映射方法并不能很好的模拟这种效果, 故而Blinn提出通过对物方表面各采样点的位置作微小扰动, 改变物方表面微观的几何形状, 从而引起景物表面上光线的法向变化, 导致物方表面光亮度发生突变, 从而产生凹凸不平的真实感, 故几何纹理映射又叫凹凸纹理映射。几何纹理映射有两种方法, 几何扰动法和法向扰动法, 其流程见图5所示。
二维纹理映射是将二维的纹理图像映射至二维的物方空间曲面, 是二维至二维的变换, 是一种线性映射, 而一般情况下物方空间曲面与纹理图像都是非线性对应关系, 纹理图像映射至物方曲面都会产生变形, 导致场景或物体表面的看起来不真实, 不逼真;对具有多个曲面拼接的景物表面进行二维映射, 并不能保证相邻曲面间映射纹理的连续性。在模拟白云、烟雾、水汽等不规则的自然现象时, 二维映射只是一张图片, 并不能对其进行360度旋转观看。针对上述问题, Peachey和Perlin在1985年分别提出了自己的三维纹理映射方法。三维纹理映射是直接将纹理定义在三维空间中, 仅仅是一个比例关系, 所以映射也变成一个简单的嵌入映射, 映射的纹理点与物方三维空间点通过映射函数一一对应, 这样就没有了变形的说法, 也就容易处理图像走样。三维纹理映射还可以通过优化纹理映射技术, 减少纹理变形、扭曲, 剔除纹理图形中的光照信息, 实现纹理无缝拼接。三维纹理映射主要用于实现木材、云彩、火焰、烟气等自然景观的模拟映射。
2.2 纹理映射新技术
2.2.1 位移映射
位移映射也叫映射转移、置换贴图技术, 由Matrox提出, 是与几何纹理映射、法向映射、视差映射等完全不同一种映射技术。位移映射需要使用两张纹理图像, 一幅高度图像, 一幅表面纹理图像, 将纹理化图像上的像元点沿高度图表面法线移动, 移动时需按照高度图像中的数值 (网格顶点数值) 进行, 从而混合形成真正的具有凹凸效果的映射模型。位移映射图见图7所示。位移映射改变了模拟物方空间网格曲面本身的几何信息和拓扑信息, 再通过光线和阴影渲染, 可以逼真地展现出静态物体表面的凹凸细节, 也可以模拟动态的物体或场景, 如大海波涛涌动的情形, 使模拟的场景和物体更具有真实感。
2003年, 微软亚洲研究院的王力锋等人提出的VDM (View-Dependent Displacement Mapping) 基于视点的位移映射。与传统位移映射不同, VDM不需对模型网格进行细分, 也可以将沿视线方向对物方空间有不同的细节纹理映射, 其能够对自身阴影、遮挡和轮廓边缘等细节进行正确精细的绘制。VDM对每个像素进行处理, 通过硬件加速, 可以进对复杂结构的模型行实时的渲染绘制, 并非常逼真。VDM映射效果图见图8所示。
2.2.2 过程纹理
过程纹理映射是三维纹理映射的一种算法。三维纹理在构造中需要庞大的三维数组, 其内存消耗巨大, 而通过定义简单的过程迭代函数生成三维纹理, 称之为过程纹理。过程纹理是基于一种解析表达的数学模型, 通过计算机计算生成复杂纹理来模拟物体。1985年Peachey用一种简单的规则三维纹理函数首次成功的模拟了木制品的纹理效果, Peachey效果图见图9所示。其基本思想如下:
(1) 采用一组共轴圆柱体面定义表面纹理;
(2) 模拟真实感纹理。
(1) 扰动:对共轴的圆柱体面半径进行正弦或其他数学函数的扰动, 使之木纹发生变化;
(2) 扭曲:在圆柱方向加一个小扭曲量, 使得木纹有较小的扭曲;
(3) 倾斜:沿圆柱体轴的某一方向发生倾斜, 使得木纹产生波动, 形成逼真的效果。
2.2.3 其他方法
对于改进纹理映射还有湍流函数法、Fourier纹理合成技术, 多边形格网参数化、近似调和映射技术、离散光滑插值参数化技术等, 这些方法都从不同程度上优化了纹理映射技术, 提高了技术的计算效率, 增强了纹理映射的效果, 使得真实感更强, 虚拟效果更佳。
三维纹理映射解决了二维纹理映射中不连续映射和变形问题, 但是三维映射需要对每一个空间点就是复杂计算, 故而对计算机硬件配置要求较高, 过程纹理映射解决了这一问题, 其计算相对简单, 效率高。
3 结束语
近年来随着计算机技术迅速发展, 纹理映射技术研究也有了极大的进步, 本论述概述了纹理映射的发展历程, 介绍了几种常规的方法以及当前最新的几种纹理映射优化方法, 总结了历年来纹理映射的一些经典算法, 以供研究者查漏补缺。
摘要：纹理映射技术随计算机技术的发展, 经历了二维纹理映射到三维纹理映射, 再到过程纹理映射的一个过程。在这个过程中, 纹理映射算法层出不穷, 各有优劣。通过系统地总结纹理映射技术的发展历史和纹理映射发展历史中的几种经典算法, 从应用的角度给出了纹理映射技术的各种常用算法, 并比较其中几种算法的优劣。
【映射优化】相关文章：
映射技术07-16
映射模型07-21
模式映射08-30
数据库映射07-05
映射的概念教学设计05-16
汉英文字借用与心理映射论文12-02
一种新的构造单向一一映射的方法02-09
浅析隐喻映射能力培养对英语词汇学习的意义──以辽东学院为例09-12
优化环境下的优化传播06-02