（物理电子学专业论文）基于神经网络的信元优化调度和相位特征识别.pdf

_ 摘要 摘要 人工神经网络在优化控制和模式识别方面得到了广泛的应用。本文对人工神 经网络方法在删( a s y n c h f o n o l l st r 趾s f e rm o d e ，异步传输模式) 信元优化调度和 三维物体相位特征识别中的应用进行了研究。 1 基于神经网络的信元优化调度：在多重队列中采用每条入线在同一个时 隙内可传送多于一个信元的策略，提出了两种新的h o p f i e l d 神经网络的能量函 数，进而利用h o p n e l d 神经9 嘲络实现对信元的控制和调度。计算机仿真模拟比较 表明，我们所提出的这两种方法均提高了吞吐率，减少了信元时延，并降低了信 元丢失率，消除了队头阻塞造成的性能恶化，提高了a t m 交换结构的性能，实 现了信元整体上的优化排程控制。由于h o p f i e l d 神经网络易于电子或光电技术实 现，交换结构和缓冲器也无需加速，因此，这两种方法不失为有效的信元优化调 度方案。 2 基于神经网络的相位特征识别：提出一种基于人工神经网络的三维物体 相位特征识别方法。首先利用波长扫描数字全息技术提取物体的相位特征，然后 将物体的这些相位特征作为学习模式训练一个b p 神经网络，最后利用训练好的 网络对三维物体进行识别，计算机模拟表明，对于具有小尺度变化的透明、半透 明三维物体识别，该方法的正确识别率为1 0 0 ，而且还具有一定的容错性。这 为透明或半透明三维物体进行小尺度不变性识别提供了一个新的方法。 关键词：人工神经网络，信元调度，交换结构，相位特征，数字全息 a b s l r _ a c t 旭s t r c t a r t i f i c i a ln e u r a ln e t w o r kh a sb 咄u s e df b rs o l v i n go 砸m a lc o n 仰1a n dp a t t e m r e c o g n i t i o np r o b l e m sc x t e n s i v e l y k1 h i sd i s s e r t a t i o n ，w ec o n c e n 似ea i l ra t t e n t i o n t o a p p l y i l l g 枷f i c i a ln e u r a l n e 伽o r ki nb o t hc e uo 加m a ls c h e d u l i n gi na t m e n v i r o n m e n t sa n d p h a s ef e a t m er e c o g n i t i o no f 3 一do b j e c t s 1 c e uo p d m a ls c h e d l d i n gb a s e do nn e 啪ln e 俩o r k t w on e we n e r g y 矗m c t i o n so fh o p f i e l dn e u m ln e t w o i ka r c e m p l o y e db a s e do n t h em u l t i p l e i n p u t - q u e u i n gc o o p e r a t i n gw i t h 也ep o l i c yo fm o r et h a no n ec e 廿a n s f c r r e di ne a c h i n p u tl i n ed u d n ge v e r yt i m es l o t ，a 1 1 dt h 髓w eu s et h eh o p f i e l dn e l l r a ln e 柳o r kt o c o n 仕o la n ds c h e d u l em ec e l l s t h ec o m p u t e rs i m u l a t i o nr e s u l t ss h o wt h a t0 1 1 r 印p r o a c h e sn o to n l y 黟e a yi m p r o v em e 血r o u 曲p u tb u ta l s ol o w e rd o w nt h ec e l l l o s sp m b a b i l i t ya 1 1 dr e d u c et l l ea v e m g el a t e n c yo f a t ms w i t c h i n gf a b r i c s t h a ti st h e p e 墒加a n c e so fa t ms w i t c h i n gf a b r i c sa r ci m p m v e dd u et or e d u c i n g 出eh e a do f 1 i n eb l o c k i n g ( h o lb l o c k i n 曲c o n s i d c 血gp a m l l e li 1 1 f o 衄a t i o np r o c e s s i n g ，e a s y a c c o m p l i s h m e n tb ye l e c 订o n i c o ro p t o e l e c 订o n i c t e c h l l i q u eo fh o p f l e l dn e u r a l n e t 、) l ，o r ka i l dt h ea t ms w i t c h i n gf a b r i ca n dt h eb u 虢rw i t h o u ts p e e d u p ，t h e 抑o a p p m 毗h c sp m p o s e di nt h i sd i s s e r t a t i o na r ee c t i v ec e l ls c h e d u l i n gs c h e m e s 2 p h a s ef b a n r e c o 印i t i o nb a s e do nn e u r a in e 铆o r k ：an e wa p p m a c hb a s e d o p h a s ef e a m r e sc 砌b i n e dw i 廿ln e l l r a ln e 呐o r km o d e l i sp r o p o s e df o rr c c o g n i z i n g 3 一do b j e c t si n t h i sd i s s e n a t i o n ，f i r s t ，m ep h a s ef e a t u r e so fa 仕a 1 1 s p a r e mo r s e m i 仃a n s p a r 班l t 3 一d o b j e c t w e r ee x 仃a c t e d b yw a v e l e n g 山一s c a 衄i n gd i g i t a l h 0 1 0 9 r a p h ya n dn u m 甜c a lr c c o n s 咖c “o nt e c h n i q u e 1 1 1 e n ，ab pn e u r a ln e 撕o r k 删n e db yt h o s er e c o n s t n l c t e di m a g e si n c l u d i n gt h ep h a s ef e a t i l r e so f3 一do b j e c t s w a su s e dt or e c o g n i z et h ei n p u to b j e c t s t h ec o m p u t e rs i m u l a t i o n ss h o wt 1 1 a tm e c o c c tr e c o 印m o nm t ei su pt o1 0 0 f o rt h et r a i n i l l go b j e c t so ro n e sw i ms o m e s c a l ev a r i a n c e nd e m o n s 廿a t e st h a tt h em 砒o dw ep m p o s e di se n e c t i v e 山di t 酉v e san e ww a yf o rr e c o g i l i z i n gt h e 订 m s p 盯衄to rs e m i 订a n s p a r e m3 - do b j e c t sw i m s o m es c a l ei n v a a n c e k e y w o r d s ：a n i f i c i a ln e 啪ln e t w o r k ，c e us c h e d u l 抽岛a t ms w i t c h i gf a b r i c ， p h a s e f e a t i l i ，d i 百t a lh o l o g m p h y i i 。9 7 5 0 1 郑重声明 本人的学位论文是在导师指导下独立撰写并完成的，学位论文没有剽窃、抄 袭等违反学术道德、学术规范的侵权行为，否则，本人愿意承担由此产生的一切 法律责任和法律后果，特此郑重声明。 糊一c 形枷问 2 彳年占月如日 引言 引言 人工神经网络f a n i f i c i a ln e m ln e 脚。血s ：a m 哪，是由大量简单的处理单元 f 神经元n e u r d n s ) 广泛互连而成的自适应非线性动态系统，是对人脑的抽象、 简化和模拟，反映人脑的基本特性【l j 。它至少在两个方面与人脑相似：( i ) 获得 的知识是从外界环境中学习得来的：( i i ) 互连神经元的连接强度，即突触权值， 用于储存获得的知识( 2 。3 。由于神经网络的分布式存储、大规模自适应处理能力 尤其是其高度的学习能力和窖错能力，所以它在几乎所有的工程应用领域得到 了广泛应用，如模式识别与图像处理、控制与优化、预测与管理、信号处理和 检测、通信等【4 “。本文基于神经网络的上述特征，把神经网络的方法应用到信 元优化调度和相位特征识别的研究，取得了比较好的效果，下面将分别说明之。 基于神经网络的信元优化调度 随着社会信息化程度的提高，网络需要传输的信息量急剧增多，对嘲络的带 宽要求越来越高，使得交换系统成为高速宽带网络发展的瓶颈，因此提高通信网 络交换系统的性能有着极其重要的意义。a t m ( a s y n c h m n o u st f a n s f e rm o d e ，异 步传输模式) 交换技术代表了网络和通信技术发展的未来方向【6 】，作为其关键技 术的a t m 交换结构( a t ms w i c h i n gf a b r i c ：a s f ) 及其调度算法成为近年来人们的 研究热点。其中缓冲策略或称为排队策略是a t m 交换结构设计中的重要内容， 对a t m 交换结构的性能具有重要的影响。按缓冲器所在的位置，交换结构可以 分为输入缓冲、输出缓冲和中央缓冲三种，其中输入缓冲方式因具有存储带宽低、 对缓冲器的速率要求较低、硬件实现简单、扩展性较好的特点【7 。8 】，所以被越来 越多的高性能路由器和交换机所采用，如c i s c o1 2 0 0 0 系列【9 】t i n v 2 t e r a 【1 哪和 b b n 等，其调度算法引起了越来越多的人的研究兴趣 7 】 1 2 】_ 18 1 。传统的输入缓 冲方式是采用单个先进先出( f i r s ti nf i r s to u t ：f i f o ) 排队规则的输入队列，存 在队头阻塞( h e a do f l i n eb l o c k i n g ：h o lb l o c k i n g ) 现象。理论分析表明，对于 采用f i f o 规则的输入缓冲方式的a t m 交换机，在随机的均匀业务流模型下，交 换端口能达到的最大吞吐率被限制在0 5 8 6 【1 9 。为克服f i f o 所产生的队头阻塞现 象，提出了很多的规则和调度算法旧18 】 2 0 2 ”，如开窗策略、加速算法、多重队列 方法、输入扩展等改进方法。这些方法实质上都是放弃了先进先出的原则，在一 定程度上都减小了队头阻塞，提高了吞吐率，但依然存在一些缺点，如平均信元 延时比较大、实现结构复杂或不能实时实现等。迄今为止，大多数多重队列的研 引言 究都集中在虚拟输出队列( v i 咖a lo u t p u tq u e u i n g ：v o q ) 【1 5 16 2 0 之2 1 上，它是在 每条入线上设置n 个f 坪o 队列，去往不同输出端口的信号排在不同的队列，每个 队列对应于1 个输出端口，在每个时隙，每条入线只能传送1 个信元。虚拟输出队 列可以使交换结构的吞吐率达到o 9 9 以上，但在虚拟输出队列中，原来n n 的交 换结构就需要有n 2 个输入队列，因而所需要的缓冲器也扩展为n 2 个，增加了系 统成本和实现难度，特别是n 比较大的时候，可能导致系统无法实现。信元调度 实际上是一个有约束条件的优化问题，在高速交换系统中，信元的时隙通常只有 几微秒，由于一般的调度算法的计算复杂度高，用传统的软件方法解决这个优化 问题时，无法达到交换速率的要求，而用硬件实现时又比较复杂，如广泛应用的 并行迭代匹配( p a m l l e l i t e r a t i v em a t c h i n g ：p 皿v i ) 算法，对于1 6 1 6 的交换结构， 需要将近6 4 0 0 0 个复杂的门器件。众所周知，实现难度的减小和成本的减低大都 以牺牲系统的性能为代价，那么在实现难度和成本相同的情况下，得到最好的系 统性能是我们所追求的。 h o p f i e l d 神经网络( h o p f i e l d n e u m ln 咖o r l ( s ：h n n ) 具有高度并行处理能力 和易于电路8 1 【2 3 1 或光电技术口4 1 实现等特点，尤其擅长解决优化问题。为此本文使 用h n n 进行信元的优化调度。本文基于i n n 网络模型，提出在多重队列中采用 每条入线在同一个时隙内可传送多于一个信元的策略1 1 4 】【】7 】，通过提出两种新的 能量函数，实现对信元的控制和调度。通过对几种不同调度策略和算法在不同交 换结构规模以及不同到达率时性能参数的比较，可以发现我们所提方法在相同条 件下，具有更好的吞吐率，降低了信元丢失率，而且较大程度的减少了信元平均 时延。计算机模拟与分析表明该方法不仅具有较好性能，而且大大地减小了系统 实现难度和实现成本，实现了a t m 交换机中信元的整体优化排程控制。 基于神经网络的相位特征识别 三维物体识别在机器人工件抓取、工业产品检测、军事预警、医学图像分 析以及在某些危险环境中具有广泛的应用，是当今非常活跃的研究领域，半个 世纪以来受到各国研究者的广泛关注。基本思想是：首先选取物体的某些特征 作为基元，在确定基元之间的相互关系后，将物体表示成一个关系属性图，物 体的模型就是识别系统在识别物体前所获得的物体的表示关系属性图，最 后系统通过从图像中抽取出的物体的关系属性图与物体的模型进行匹配来识别 物体。具体来说三维物体识别系统必须解决两个问题：( 1 ) 三维物体模型表达 ( 构造) 方法：( 2 ) 物体描述和物体模型之间的匹配算法。在众多的理论和方 法中弘”，2 0 世纪8 0 年代兴起的成为当时主流的三维模型特征识别方法的拓 扑图法，成功地采用了许多在拓扑和图论上的成熟算法，用图匹配的方法来寻 引言 找和识别特征，虽然取得了许多成果，但是存在以下几个缺点：仅仅用拓扑 信息表示特征不充分；交叉特征的引入会严重改变拓扑图的原有结构；基 于图论的搜索匹配算法计算量大；每个类特征都需要定义很多特征子图作为 范例【3 3 l 。始于上世纪9 0 年代的人：e 神经网络的识别方法，通过神经网络对样 本集的训练来实现特征识别，为解决特征识别问题开拓了一个新的思路，详见 论文文献 3 3 】。但是几乎所有的方法都是基于物体的几何特征或者它的颜色、 纹理等特征进行识别的，这在很多情况下是切实可行的，但是，对于一些几乎 是透明的物体，比如说一些生物薄膜、细胞等，这些方法显然是行不通的。因 为这样的物体其几何特征、颜色或纹理可能没有多少变化，然而经过它们的光 的相位却会发生改变，据此我们提出一种基于相位特征的三维物体识别方法 畔 。首先利用波长扫描数字全息技术【3 5 1 提取物体的相位特征。同传统的再现方 法相比具有以下优点：其再现波长可以和记录时的波长完全相同，不会产生任 何由于波长不匹配造成的误差；数字全息避免了全息像的多次曝光和化学处理 过程，因而具有高的衍射效率。 神经网络作为一个特殊的映射机制，可以把不同的模式映射到一个或多个 神经元中以实现对这些模式的识别或者分类。在得到物体的相位特征后，就可 以选用神经网络的方法进行识别。当一个神经网络模型用三维物体的相位特征 训练后，嘲络的互连权重就已经包含了该训练物体的相位信息，依此可以用来 对输入的物体进行识别。实验表明，对于具有小尺度变化的透明、半透明三维 物体识别，该方法的正确识别率为1 0 0 ，而且还具有一定的容错性。 本论文研究内容及其章节安排 1 第一章是人工神经网络的介绍，在这一章首先简要介绍神经网络的基本知 识、基本原理，然后对本文将用到的b p 神经网络和h o p “e l d 神经网络进 行较为详细的介绍。 2 第二章是基于神经网络的a t m 信元优化调度，这一章首先介绍a t m 交换系 统信元调度的基础知识，然后介绍两种采用新的能量函数的h o p f i e l d 神经 网络实现信元优化调度的模型和计算机模拟分析。 3 第三章是基于神经网络的三维物体相位特征识别，这一章首先介绍了物体 相位特征提取的方法，然后介绍如何用b p 神经网络的方法对三维物体识 别。 4 第四章是总结与展望。 第l 章人工神经网络 第1 章人工神经网络 1 1 神经网络概述 神经网络是由大量执行简单非线性运算的基本单元( 亦称神经元) 相互连 接而构成的并行信息处理系统，是一种植根于许多学科的技术，它涉及到神经 科学、数学、统计学、物理学、计算机科学和工程学，有着非常广泛的应用背 景，这门学科的发展对未来的科学技术发展将有重要的影响f 2 ”6 。 它是从生理、心理和认知等各种不同视角出发，对人脑的结构和运行方式 进行各种层次的借鉴，以便在计算机上实现具有人类智能行为特点的各个层次 功能陋j 。它是对人脑信息处理机制进行的某种简化、抽象和模拟，反映了人脑 的许多基本特征。所以人工神经网络基本出发点就是模拟人脑，它的研究从一 开始就是借助于神经元的生理结构模型，因此我们有必要先介绍一下作为人脑 基本组成单元的生物神经元的结构。 1 1 1 生物神经元结构 神经元( n e u r o n ) 是神经系统的基本单位，图1 1 为神经元的基本结构。 图l - l神经元基本结构【3 7 】 图中主要组成简介： 1 神经元胞体是整个神经元的主体，相当于一个信息处理器，对来自于其它 神经元的信号求和，并产生神经脉冲信号； 2 树突感受突触( 突触：图中未标出，是调节神经元之间相互作用的基本结 构和功能单位) 传来的信息，并将响应传向神经元胞体； 羔堕三! ! 丝堕竺 3 轴突输出神经元胞体产生的神经脉冲信号。末端形成很多分歧( 神经末梢) ， 每条神经末梢与其它神经元通过突触相连并传递信号。 脑神经生物科学研究结果表明，每个人的大脑中含有1 0 1 l 1 0 1 2 个神经元， 每个神经元又约束1 0 3 1 0 4 个突触。神经元通过突触形成的网络，传递神经元 之间的兴奋与抑制。大脑的全部神经元构成极其复杂的拓扑网络群体，用于实 1 1 2 人工神经元模型 人工神经元是对大脑神经细胞的模拟和近似，是人工神经网络操作的基本 信息处理单位。图l - 2 显示的即是人工神经元的模型，它是人工神经网络的设 计基础。 突触权值 图1 2 人工神经元的非线性模型2 1 输出儿 图1 2 中主要部分说明： 1 突触或连接链每一个都以其权值或强度作为特征。突触权值璐。的意义是连 到神经元j 】 的突触m 上的输入信号所对应的激活强度： 2 加法器用于求输入信号被神经元的相应突触加权的和。此操作构成个线 性组合器： 3 激活函数以) ，用来限制神经元输出振幅，一般为非线性处理函数。 由上我们可得出对神经元七的方程描述式： y t2 m t 圳= ，( 善一+ 钆) ( 1 _ 1 ) 对照图l l 、图l - 2 ，我们不难发现图1 2 中的l 即是模拟图1 1 中的2 、3 功能； 图l 2 中的2 、3 即是模拟实现图1 1 中的l 的功能! 要季特别指出的是，在人工神经元的理论模型中，常用的激活函数月) 的基 本形式为一些最简单的非线性函数，但随着研究的深入，也出现了一籀微复 第l 章人工神经网络 杂一点的激活函数形式。下面列举其中较常用的几个： 1 硬取阈函数( h a r dl i n l i t c rf l l n c t i o n ) ：( 见图1 3 ) m ，任m 哗 z ， o 甜= o 甜 + 口， m ) = 形，一n ” 帆 ( 1 5 ) il ， “ 一d l “，。 + 1 一口 o 七a ： 一1 图1 5 饱和取阀函数 1 1 3 神经网络的网络结构与类别 网络的拓扑结构是神经刚络的一个重要特征，从连接方式看，主要有两种： 前馈型网络和反馈型网络( 也称递归网络) 。下图是神经网络的主要类别及其网 络结构示意图。 国圈凰国 图1 6 神经网络的类别和结构9 ” 第1 章人工神经网络 1 前馈型网络( f e e d f b r w a r dn e 嗽ln e m o r k s ) 前馈型网络也称前向神经网络或多层前向网络。在前馈型网络中，各神经 元接收前一层的输入，并将计算结果输出给下一层，层内神经元之间没有相互 作用，没有反馈，如上图。除了输入层外，隐藏层和输出层都实现一定的运算 。常见的前馈型网络有单层感知机( p e r c 印仃o n ) 【4 1 4 2 ，多层感知机( m u l t i l a y e r p e r c e p t r o n s ：m l p s ) 【槲，径向基函数( r a d i a lb 船i sf l m c t i o n ：r b f ) 【槔4 鄂，支持 向量机( s u p p o r tv e c t o fm a c h i n e ：s v m ) 【4 6 。4 7 1 掣2 1 。 多层感知机因采用误差背向传播( e 们rb a c kp r o p a g a t i o n ) 学习算法( 4 舡4 9 1 而得名，简称反向传播( b a c k p r o p ) 或b p 网络，有着极其广泛的应用，如非线 性不可分模式的分类问题、非线性函数的逼近问题等。关于这种神经网络模型 将在下一节重点介绍。 2 反馈型神经网络( f e e d b a c k n e l l m ln e 哳o r k s ) 反馈型神经网络是指拓扑结构中有反馈的神经网络，这类神经网络的输出 都要通过某种途径反馈到它的输入端去。常见的反馈型网络有h 0 口f i e l d 网络， w t a 网络( w i n i l e r l 址e m l ：w t a ) 即胜者全取，元胞自动机( c e l l u l a r a 朋t o m a t a ) ， 波尔兹曼神经网络( b o l t z m 髓) 等。其中最著名的一种反馈模型神经网络就是 h o p 丘e l d 网络渺硎，它是1 9 8 2 年美国加州理工学院( c a l i f o m i ai n s t i t i l t eo f 1 k 1 1 t l o l o g y ：c i t0 r c a l t e c h ) 生物物理学教授j h o p f i e l d 首先提出并论证了这种 网络的动力学特点和重要应用，而得到广泛的重视和巨大的发展。这类神经网 络在实现联想存储器和全局并行寻优等方面有重要的应用。关于这种神经网络 模型将在第三节重点介绍。 1 2 b p 神经网络 1 2 1 b p 神经网络的网络结构 虽然多层神经网络可以解决非线性分类的问题，但是由于没有适当的训练 方法，导致了在2 0 世纪6 0 年代和7 0 年代人们对人工神经网络研究兴趣的衰退， 直到8 0 年代中期r 砌e l h a n 和m c c l e l l a i l d 等学者重新阐述了使用可微的 s i g m o i d 函数的误差反传学习算法，不仅为解决多层网络的学习问题开辟了一 条成功之路，而且从客观上将神经网络的研究推向了高潮5 5 1 。 图1 7 是隐藏层为一层时b p 神经网络的嘲络结构示意图。 一苎! 兰王! ! 丝塑竺 xyz ny 。m 嘞l 输入层 隐藏层输出层 图1 7 b p 神经网络网络结构图 结构参数 输入层( i ) 隐藏层( h ) ， 输出层( o ) 神经元数 n ，i = 1 ，2 ，n m ，j = 1 ，2 ，m l ，k ：1 ，2 ，l 状态矢量 i 2 h ，工：，h r 哥= y ，y ：，y 。 7 j = 毛，z ：，乇】r 激活函数 一二 无 八) = ( v f ) ，( ) = ，( 芝_ ，j ) f - 0 扛0 连撒重 矿州盏奠z 谚制乏善。0 闽值矢量 简化表示 学习参数 训练样本 样本矢量 输出误差 输出方差 样本方差 平均方差 学习目标 y 。= 【v o - ，确】7 矿。= w o l ，：，w o 。】r n m l p ，五j p ：l 如p 孑和= z f w ，墨w ，毋】r 五： 研w ，叫w ，啦r 2 ( 以一z 女) ，七= l ，2 ，三( 1 6 ) f = 要杰( ，) z 二t = l 乞：妻壹( 碰w 一：z 上 = l ( 1 7 ) ( 1 8 ) 手= 击砉矗= 去砉( 叫1 2 ( 1 。) 乞磊，坳= 1 ，2 ，p 第1 章人工神经网络 权重初值 _ ( o ) = i v f ( o ) i ， v j ， 矿( o ) = 1 w ( o ) i ， w ，| 】 学习步长 o 口 l 动量常数0 玎 l 迭代次数 输出层背传误差 隐藏层背传误差 1 2 2b p 算法 f o ，。( 巧) 为单调增长型函数， ；z 一1 ( k ) o 肌 - 譬o ( 1 3 5 ) d l 、。 ! 等茎o ，即h n n 的能量函数e 是时间的单调减函数。因此h o p f i e l d 神经 d l 1 1 3 3 连续型h n n 的能量函数的进一步讨论 按照式( 1 3 1 ) 定义的能量函数，由于存在右面第2 项，因此不是l i a p u n o v 函数，从而引起了很多运算上的困难和问题。因此，j j h 叩f i e l d 以及其他的 研究者都将这一项去掉而采用下面的定义方法： 1 e = 一寺乃m 巧一 k ( 1 3 6 ) 。# i j = l= 1 为了不脱离硬件电路实现的背景，h 叩f i e l d 提出将该项去掉的前提是式 ( 1 2 6 ) 中的参数取得足够小，这样( 1 2 6 ) 式表示的函数就非常接近于阶越函数， z _ 1 ) 在【o ，1 ) 区间中非常接近于o ，因此( 1 3 1 ) 式中右边第2 项的积分项可以 略去。 后来一些研究者从一开始就不顾电路背景，而直接按照式( 1 3 6 ) 定义e 。然 后再从该能量函数出发来定义系统的运行规则： 第l 章人工神经网络 警一熹 s ， 卉a k 、 在实际的运算以及解决优化问题时，无论采用哪一种定义都是可行的，而 式( 1 2 6 ) 总是决定了输入到输出的转换函数，在没有电路背景的约束条件下，其 中的参数“。可取为任意大于o 的实数。【5 l 1 3 4 连续型h n n 的优化计算 1 9 8 5 年，j j h o p f i e l d 和d w t a l l l 【巧妙地将连续型 玎q n 应用于旅行商 问题( t h v e l i n gs a l e s m a np r o b l e m ：t s p ) 的求解，取得了良好的效果，为组合 优化问题的求解开辟了新的途径。 式( 1 3 5 ) 表示随着递归过程的进行，网络的能量也在减小，直到达到它 的局部最小值。这个局部最小值点就是网络状态空间的吸引子，如图1 1 0 所示， 网络初始化为状态空间中的一点，随着向其所在吸引域中的吸引子运动，形成 运动轨迹。如果能构造适当的能量函数，从而使网络状态空间的吸引子就是能 量函数的最小值点，这样，我们就可以利用h o p f i e l d 神经网络模型来解决组合 优化问题了1 5 “。 图1 1 0 状态空间中吸引子、吸引域以及运动轨迹示意图 第2 章基于神经网络的信元优化调度 第2 章基于神经网络的信元优化调度 2 1 1 a t m 交换 2 1 a t m 信元调度基础 删即异步交换模式，它采用了固定长度的信元( c e l l ) ，综合了传输、复 用和交换技术，向用户提供高速带宽，使用户可以在一个网上传送综合业务。 它是i t u t ( 国际电联电信部) 确定用作宽带综合业务数字网b i s d n ( b r o a d b 粕di n t e g r a t e ds e n ，i c e sd 蟛t a ln e t 、】l ，o r k ) 的模式。a t m 交换应实现高速、 高吞吐率和高服务质量的交换，提供灵活的带宽分配，适应从低速率到高速率 的带宽业务的交换要求。 信元是a t m 特有的分组单元，语言、数据、视频等各种不同类型的数字 信息都可以被分割成一定长度的信元。它的长度为5 3 字节( b y t e ) ，分成两部分， 如图2 1 ，其中开头的5 个字节称为信头( c e l lh e a d e r ) ，包含有用于表征去向的 逻辑地址、优先级等控制信息；其余4 8 个字节为信息域，或者称为净荷( p a y l o a d ) ，用来装载不同用户的业务信息。任何业务的信息在发送前都要经过分割， 封装成统一格式的信元，在接收端完成相反的操作以恢复业务数据原来的形式。 图2 1a t m 信元组成图 a t m 交换的基本特点如下： 1 固定长度的信元中继 采用很短的信元( 5 3 字节) 可以减少交换节点内部的缓冲器容量以及排队时 延和时延抖动。信元的长度固定则有利于简化交换控制和缓冲器管理。 2 信头简化 信头中包含的控制信息的多少反映了交换节点的处理开销，因此要尽量的 使信头简化。 3 a t m 是一种统计时分复用技术 它将一条物理信道划分为多个具有4 i 同传输特性的逻辑信道提供给用户， 实现网络资源的按需分配。 第2 章基于神经网络的信元优化调度 4 a t m 是面向连接的传输技术 在传输数据之前，必须先要建立端到端的连接，这不是物理连接，而是虚 连接( r h l a lc o n n e c t i o n ：v c ) 。所有信息，包括用户数据、信令和网管数据都通 过虚连接传输。 5 支持多种q o s ( q u a l 时o f s e r v i c e ) 不同业务对传输和交换质量要求不同，有的对实时性要求高，要求时延小； 有的要求无失真地传送信息，对信元丢失或者错误敏感。因此a t m 交换应该 允许业务提出不同的q o s 要求，并在保证服务质量的前提下，更有效的利用网 络带宽。 6 全面的多媒体支持 a t m 支持语言、数据、图像等各种低速和高速业务，是一种不同于其它的 交换方式、与业务无关的全新的交换方式，可以有效的利用带宽。 评价a 1 m 交换系统性能的主要参数有：吞吐率、信元平均时延和信元丢 失率。 ( 1 ) 吞吐率 吞吐率是指平均每个时隙交换结构的每个输出端口所传送的信元数。每个 时隙，相当于在一定传送速率下一个信元的传送时间。最大吞吐率是指在最大 负荷下( 即到达率p 为1 ) 时的吞吐率的值，最大值为l 。吞吐率是衡量一个交 换系统性能的主要指标。 ( 2 ) 信元平均时延 信元平均时延是指平均每一个信元进入交换系统到离开交换系统的时间。 信元平均时延主要由两部分组成：一部分是交换时延，由查找路由表所用的时 间和交换结构传输速率决定；另一部分是排队时延，指的是信元在缓冲器中等 待的时间。第一部分是固定的，取决于交换机的设计和制造技术标准，第二部 分主要是由于信元出线阻塞而在缓冲器中等待，它的长短与调度算法的优劣密 切相关。 ( 3 ) 信元丢失率 信元丢失率是指在一个给定的时间里，交换系统丢弃的信元数与输入到交 换系统的信元总数的比率。由于竞争和阻塞，信元必须在缓冲器中等待，在实 际交换系统中，缓冲器的长度不可能无限长，因此缓冲器满了以后，后继进入 的信元只有被交换系统丢弃。 通常，吞吐率大的交换系统，其信元平均时延和丢失率就小；吞吐率小的 交换系统，其信元平均时延和丢失率就大。 第2 章基于神经网络的信元优化调度 2 1 2a t m 交换结构 a t m 交换结构是实现a 1 m 交换的关键技术之一，是a t m 交换系统中必 不可少的重要组成部分。 i ii sjl - i 。 厂卫 l ，ill | 1l | li1 i 5i l 7l i - ii2 l。 卫 il 2i i2ii2 l 。 入 ll t i 4 i2 li21 l 二田 jl 1 图2 2a r m 交换结构示意图 l 2 n 图2 2 是具有n 条入线和n 条出线的a 1 m 交换结构示意图，在入线和出 线上给出了信元流的示例，数值表示目的地址( 出线号) 。 a t m 交换结构应能实现任意出入线之间的信元交换，也就是任一入线上的 任一逻辑信道的信元要能够被交换到任一出线上的任一逻辑信道中去。为此， a t m 交换结构应该具有信头交换、选路和排队这三项基本功甜”】。 本文主要研究对象是交换结构的排队功能，所以，下面将着重介绍排队的 相关知识。关于交换结构的其它功能以及交换结构的分类与结构模型，请参考 文献 1 4 】【5 7 5 8 】等。 2 1 3 a t m 基本排队机制 由于a t m 是统计复用的异步时分交换，在建立连接后的传送信息阶段， 经常会发生在同一时刻有多个信元争抢公用资源的情况，为解决信元对交换介 质等交换资源的竞争，必须对信元进行排队，在时间上将各个信元分开，以免 在发生资源争抢时丢失信元。这是通过a t m 的排队机制实现的。 排队机制或称缓冲机制，是a t m 交换中的一个极其重要的内容，对a 1 m 交换机性能有着决定性的影响：队列的溢出会引起信元的丢失，信元排队是产 生交换时延和时延抖动的主要原因。为了防止阻塞引起的信元丢失，必须在输 入端口( 或称为入线) 、输出端口( 或称出线) 和交换结构中分别或者全部设置 缓冲器，而缓冲器的设置方式是煳m i 交换结构中的重要问题，在很大程度上 影响到交换结构的性能和复杂性。 第2 章基于神经网络的信元优化调度 根据缓冲器设置位置的不同，a 1 阻讧的基本排队机制主要分为三种：输入缓 冲、输出缓冲和中央缓冲。 1 输入缓冲 输入缓冲( i l l p u tb u 疵血喀) 或称输入排队，是在交换结构的每条入线上设 置缓冲器，对信元进行排队，如图2 3 所示，控制模块根据各输出线的忙闲、 输入队列的状态、交换结构的状态，选择队列中不会产生阻塞的信元通过交换 结构。输入缓冲一般采用简单的先进先出( f i r s tm f i r s t0 u t ：f i f o ) 的排队规则。 这样，当入线上的每个时隙到来时，各个非空队列的队首信元进行竞争，去往 不同出线的信元能通过交换结构而传送到出线，在竞争中失败的信元留在输入 缓冲器中，等待下一时隙( 下一轮) 的竞争和传送。 n 交换 结构 图2 - 3 输入缓冲方式示意图图2 4 队头阻塞( h o l ) 示意图 输入缓冲机制存在队头阻塞( h e a d o f l i n e b l o c k i n g ：h o l b l o c k i n g ) 现象。 所谓队头阻塞，是指在发生出线竞争时，排在竞争失败的信元( 处于队头位置) 之后的去往空闲出线的信元也不能传送的现象，如图2 4 所示。缓冲器内的数 字表示该信元要去的输出线地址。输入线1 和3 缓冲器中的队首信元同时竞争 输出线l ，在一个时隙内交换结构只能选择一个信元，假定输入线l 在竞争中 获胜，队首信元传送至输出线1 ，输入线3 中的队首信元竞争失败，留在缓冲 器中等待下一轮的机会。输入线2 和4 的队首信元分别传送往输出线4 和2 。 此时，输出线3 在该时隙内空闲，无信元传送，而在输入线3 中队列的第2 个 信元分明是要到输出线3 ，由于其队头信元在竞争中失败以及f i f 0 规则，因此 也不能传送，造成交换性能的下降和交换资源的浪费，这就是所谓的h o l 阻 塞现象。 队头阻塞降低了交换结构的利用率，使得输出线的传送效率降低。分析表 明，在随机的均匀业务流模型下，当输入线n 很大时，采用f i f o 规则的输入 缓冲机制的最大吞吐率仅为o 5 8 6 。 2 输出缓冲 输出缓冲( o u t p u tb u 脑r i r 喀) 是在每条出线上设置缓冲器，如图2 5 所示。 输出缓冲机制由于交换结构没有内部阻塞，也没有h o l 阻塞现象，所以吞吐 二二 l 2 3 4 第2 章基于神经网络的信元优化调度 率高于输入缓冲机制，在理想的输出缓冲交换系统中，吞吐率可达1 0 0 。为 解决出线竞争，一个理想的采用输出缓冲的无阻塞的交换结构最好能够使得每 个输出端口在一个时隙内，可以同时接受所有的输入端发来的信元，假如输入 端口数为n ，则每个输出端必须能够接收最多n 个信元，否则就会造成信元丢 失。要做到这一点，就要提高交换结构的处理速度和缓冲器的访问速度。于是 引入了加速因子( s p e e d u pf a c t o r ) 的概念。首先交换结构必须要以端口速度 n 倍( 即加速因子为n ) 的处理速度工作，才能在个时隙内将全部的n 个信 元传送到一个输出端口，其次，输出端口缓存的写入速度必须是端口速度的n 倍，才能在一个时隙内接收所有n 个信元。 n 工旷- 工卜n 图2 5 输出缓冲方式示意图 输出缓冲机制的优点是控制简单，缺点是硬件复杂度比输入缓冲机制高得 多。由于采用了光纤传输信息，使得数据传输速度的增长超过了集成电路工艺 进步所能达到的信元处理速度，因此在现有的技术条件下，要想使交换系统中 的交换结构处理速度和缓冲器访问速度比端口速度更快是非常困难的，所以输 出缓冲机制并不适合于高速大容量交换系统。另外输出缓冲系统的信元丢失率 要高于输入缓冲方式，为了达到相同的信元丢失率输出缓冲需要更大的缓冲器， 增加了硬件实现的复杂度。 3 中央缓冲 在中央缓冲机制中，交换结构分为两个部分，缓冲器设置在两个交换结构 中间，所有入线和出线共用一个大缓冲器，所有信元都经过这一缓冲器进行缓 存，如图2 6 所示： n 工叶 工叶 n 图2 6 中央缓冲方式示意图 中央缓冲机制的优点是缓冲器利用率高，相对于每个输入输出有一个可变 第2 章基于神经网络的信元优化调度 的动态队列。缺点是缓冲器管理复杂，需要有一套复杂的存储管理机制；可靠 性差，当中央队列的某个信元发生错误时，可能会影响任何一个连接；速率在 三种机制中是最高的，输入输出端的速率都必须为所有端口速率之和。 综合上面三种缓冲机制，输入缓冲机制结构简单、实现容易，而且对缓冲 器速率要求较低，因此它被广泛应用于高速和大容量交换系统中，如c i s c o 1 2 0 0 0 系列，t i n v 2 t e r a 和b b n 等。但是，输入缓冲机制存在h o l 阻塞现象， 为了克服这一现象，提高输入缓冲方式的吞吐率，可以对输入缓冲器的队列设 置和排队规则加以改进，当然这也会不同程度地带来硬件和控制的复杂性。以 下介绍三种主要的改进方法：开窗( w i n d o w ) 方法、输入扩展、多重队列。 输入缓冲的改进方法 ( 1 ) 开窗方法 l - n _ 图2 7 开窗方法示意图 l n 窗口方法也称预视( 1 0 0 k a h e a d ) 方法或者旁路( b y p a s s ) 方法，如图2 7 所示，它是在每个输入缓冲器规定定的窗口宽度w ，使得在一个时隙内每条 入线可以有w 个信元可以参与出线竞争。h o l 阻塞是由于f i f o 规则引起的， 窗口方法实际上是采用了按序进入随机取出( f i r s t i n r a n d o m o u t ：f i r o ) 的服 务原则，这样，就可以在很大程度上避开队头阻塞，使交换结构获得更大的利 用。窗口越宽，吞吐量改善越多，但对控制模块的处理速度要求也就越高。w 是个可调参数，w = l 时，就对应先进先出队列情况。 ( 2 ) 输入扩展 l - n _ 图2 8 输入扩展示意图 l n 输入扩展，如图2 8 所示，是将每条入线在进入交换结构前扩展为s 个端 口，使得原有的n n 的交换结构变为( n s ) n 的交换结构。这样，每条 入线有s 个信元参与出线竞争。因为输入扩展方法可使得每条入线在同一时隙 第2 章基于神经网络的信元优化调度 内传送多于1 个信元，所以当扩展度s 等于窗口方法中的窗口宽度w ，可望具 有更高的吞吐率。 ( 3 ) 多重队列 交换 结构 图2 9 多