（基础数学专业论文）基于竞争学习的数据广播调度.pdf

云南掘苑大学鞭士学位论文 摘疆 传统静客户鹰务器模式，当丈量客户经用系绫，蒺经蕤变差，系统豹翡瘦 时间变慢、有效性减弱。为解决这一系列的问题，人们开始对数据广播进行研究。 毽楚广播方式没鸯考虑裂客户瓣嚣求，为了经二著缀好熬羧疑，展开了基予骞户 需求的数据广播的研究。因丽基于需求的数据广播在 n t e r n e l 、无线通讯等领域 其裔缀好酶应瘸裁景。 基于需求的数据广播的核心问题是对响应客户需求的广播调度算法进行研 究，进丽加以设计、并实现。本文在对已有的研究成果旗础上提出了繁予竞争学 习的数据广播调发算法。 本文分析了神经网络的原理，采用神经髑络方法，按照竞争学习黔观点，较 全嚣避考虑影响诞凄驰诺多瓣豢，设计较好静数据广疆调发算法旗子竞争学 习的数据广播调度( d a t ab r o a d c a s ts c h e d u l i n gb a s e do nc o m p e t i t i o nl e a r n i n g - - - d b s b c l ) ，搜数据广撵其鸯嶷努懿矬戆。营是，率文将竞争学习痰蠲子簿决数 据广播调度问题，同时考虑了几种影响调艘的产生因索。所提出的算法与其他算 法耀魄具存曼好静姊震瞧( s t r e t c h ) ，以及铰好戆平均等特薅阁。其次，在竞争 学习的基础上，本文使用动态修改网络结构改进了学习模型。将学习模型建立在 神经元可变的鏊破上。第三，零文对已有爨适应滔攮算法中幻重置方麟麴警戒线 判定方法用触发条件替换，并将它应用于孵决数据广播调度问题。 关键字：数据广播调皮算法竞争学习 a b s t r a c t t r a d i t i o n a lc l i e n t s e r v e rm o d e ，w h e na b u n d a n tc l i e n t su s e ，t h ep e r f o r m a n c eo ft h e c l i e n tb e c o m e sb a d ，t h er e s p o n s et i m es l o w , t h ee f f i c i e n tc h a r a c t e rb e c o m e sd e c r e a s e i no r d e rt or e s o l v eas e r i a lo fp r o b l e m s ，t h er e s e a r c ho fd a t ab r o a d c a s tg e n e r a t e s b u t t h eb r o a d c a s td o e s n tc o n s i d e rt h en e e do ft h ec l i e n t s ，t ob o t hu s et h ed a t ab r o a d c a s t a n dc o n s i d e rt h en e e do ft h ec l i e n t s ，m a n yp e o p l eb e g i nt or e s e a r c ho i l d e m a n dd a t a b r o a d c a s ts p r e a d s ot h eo n d e m a n db r o a d c a s th a sg o o df o r e g r o u n di ni n t e r n e ta n d w i r e l e s sc o m m u n i c a t i o nd o m i n a n t t h ek e y p r o b l e mo f t h eo n d e m a n dd a t ab r o a d c a s tl i e si nt h eb r o a d c a s t s c h e d u l i n g a l g o r i t h mr e s p o n d e dt h en e e do ft h ec l i e n t sa n dd e s i g n i n gt h ea l g o r i t h ma n dr e a l i z i n g i t w ep r o p o s ed a t ab r o a d c a s ts c h e d u l i n gb a s e do nc o m p e t i t i o nl e a r n i n go nt h e r e s e a r c ho ff 0 1 t n e rr e s e a r c h e r so nt h eb a s eo fr e s e a r c hr e s u l t t h i sa r t i c l ea n a l y z e st h ep r i n c i p l eo fn e u r a ln e t w o r k ，a d o p t st h em e t h o do fn e u r a l n e t w o r k ，a c c o r d i n gt ot h ev i e wo fc o m p e t i t i o nl e a r n i n g ，c o n s i d e r i n gi n t e l l i g e n t l yt h e m a n yf a c t o r si n f l u e n c es c h e d u l i n g ，d e s i g n i n gab e t t e rd a t ab r o a d c a s ts c h e d u l i n g a l g o r i t h m d a t ab r o a d c a s ts c h e d u l i n gb a s e d o nc o m p e t i t i o nl e a r n i n g ( d b s b c l ) a n d m a k i n gt h eb r o a d c a s th a sb e t t e rp e r f o r m a n c e f i r s t ，t h i sa r t i c l ea p p l i e sc o m p e t i t i o n l e a r n i n gf o rr e s o l v i n gt h ep r o b l e mo fd a t ab r o a d c a s ts c h e d u l i n ga n dc o n s i d e r st h e f a c t o r si n f l u e n c i n gs c h e d u l i n g c o m p a r e dw i t ht h eo t h e ra l g o r i t h m s ，i th a sb e t t e r s t r e t c ha n db e t t e ra v e r a g ew a i tt i m e s e c o n d ，b a s e do nt h ec o m p e t i t i o nl e a r n i n gw e u s ed y n a m i cm o d i f yn e t w o r ks t m c t u r ei m p r o v i n gt h el e a r n i n gm o d e l w ee s t a b l i s h l e a r n i n gm o d e lo nd y n a m i cv a r i e t y t h i r d ，t h i sa r t i c l er e p l a c e sv i g i l a n c ec h e c kf o r a r o u s i n gc o n d i t i o no fr e s e te q u a t i o no fa d a p t i v er e s o n a n c et h e o r y , a n da p p l i e si tf o r r e s o l v i n gd a t ab r o a d c a s ts c h e d u l i n gp r o b l e m k e yw o r d s ：d a t ab r o a d c a s t s c h e d u l i n ga l g o r i t h mc o m p e t i t i o nl e a r n i n g 独创性声明 y7 7 s z 9 7 本人声明所呈交的学位论文是我个人在导师指导下进 行的研究工作及取得的研究成果。尽我所知，除文中已经标 明引用的内容外，本论文不包含任何其他个人或集体已经发 表或撰写过的研究成果。对本文的研究做出贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的 法律结果由本人承担。 学位论文作者签名：翮凑挈 阳时年7 月8b 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文 的规定，即：学校有权保留并向国家有关部门或机构送交论 文的复印件和电子版，允许论文被查阅和借阅。本人授权云 南师范大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保 存和汇编本学位论文。 学位论文作者签名：黑粤 d 计年7 月gb 指导教师签名：乏砂哏 卅一年7 月乎日 致谢 衷心感谢我的导师霞幼明教授，感谢夏老师直以来对我的谆谆 教导和对我的启迪和帮助。夏老师繁高的人格龋质，严谨的治学态度， 广博的知识，精益求精的科研作风，丰富扎实的专业知识，正直的为 人，敏锐的学术思想和惠我的工作精神使我受益非浅，并极大的影响 和鞭策了我。在撰写论文麓闻，跌论文的选题、构思、查阅文麸、骛 改到定稿，每步都包含着您的殷切期望，悉心指导和帮助，这将对 我今蜃靛学习酾工作，乃至入生遵籍都涛产生积校囊上豹影晌。 衷心感谢云南师范大学计算机科学与信息技术学院对我多年来 的培养，感谢游养生老雾器，陈玉华老 攀霹其强老掰对我的关心帮帮助。 衷心感谢大理学院计算机与信息工程学院段利华院长，何昌书 记，左匿超戮院长，顾应弦剽院长，张智铨副书记秘其他阍警对我的 关心，支持和帮助。 最后，衷心感谢我的父母，感谢他们对我奠大的关爱并且始终鼓 励和支持我的学韭。感谢我的弟弟绘我学盟上的帮助和支掩，以及生 活上的关心。我永远爱您们! 1 引言 随着通信、互联网、移动技术的发展，信息不断地提供给遍及世界的广大的用户，使得 大规模的数据传播应用得以极大的发展。w o r l d w i d ew e b 为基于数据传播的应用提供了 广泛的发展平台，并广泛地使用客户朋务器( c l i e n t s e r v e r ) 模式。但是当大量的用户同时 使用时，这种基于网络的系统性能变差，这时响应时间变慢，有效性减弱。 为解决这一系列的问题，人们开始关注对数据广播的研究。数据广播可解决由大规模数 据传播引起的服务器的可扩充性问题。同时人们发现如果不考虑客户的需求，服务器将数 据单一地广播给客户将极大的浪费带宽，而且存在很大的盲目性。为了解决数据可扩充性问 题，同时考虑客户的需求，a l l o y 提出了基于需求的广播 n k f r 9 9 。基于需求的广播既利用 了广播的带宽优势将数据广播给客户，又有传统客户月务器模式的优点，考虑了客户的需 求，因此具有良好的性能，并有广阔的发展前景。 研究基于需求的数据广播系统的关键在于响应客户请求的广播调度算法。目前的研究方 法主要是基本的调度算法【a 玎n u 9 8 】，包括：先来先服务算法，请求数最多优先算法，( d 等待最长的优先算法，最短服务时间优先算法。还有近期研究的算法：它们综合考虑两 种或三种因素：有的用乘的方法如：r x w 算法 a k f r 9 9 ， h k f r 9 9 1 ， a k f r 9 7 j as i n a 算法 x u t a 0 3 。用除的方法如：最长的总的s t r e t c h 优先的算法【s h c h 0 2 】， s h c h 0 3 。 用乘除结合的算法，如s t o b s - q 算法 s h c h 0 3 】。 本文首先研究了基本的调度算法：先来先服务算法( f i r s tc o m ef i r s ts e r v i c e 简称为 f c f s ) ，考虑到达时间。请求数最多优先算法( m o s tr e q u e s tf i r s t 简称为m r f ) 请求数 量越多，累计到达时间越长。( 多等待最长的优先算法( l o n g e s tw a i tf i r s t 简称为l w f ) 考 虑等待时问。( d 最短服务时间优先算法( s h o r t e s ts e r v i c et i m ef i r s t 简称为s s t f ) 考虑服 务时间和长度。因而，本文研究一种综合考虑基于时间因素的算法，这些因素包括：到达日_ j 问、累计到达时间、等待时间和服务时间。使系统有较好公平性，并有较少平均等待时间， 较好可伸展性( s t r e t c h ) 值。 本文的研究方法是使用神经网络的原理和方法，按照竞争学习的观点，综合考虑影响调 度的诸多因素，设计了一种基于需求的数据广播调度算法，使数据广播具有良好的性能。 首先，本文将竞争学习应用于解决数据广播调度问题，同时考虑了几种影响调度的产生 因素。所提出的基于需求的数据广播调度算法与其他算法相比具有更好的可伸展性 ( s t r e t c h ) ，以及较好的平均等待时间。 其次，在竞争学习的基础上，本文通过动态修改网络结构改进了学习模型。将学习模型 建立在神经元可变的基础上。 第三，本文对已有自适应谐振算法中的重置方程的警戒线判定方法用触发条件替换，并 将它应用于解决数据广播调度问题。 2 2 竞争学习概述 2 1 联想学习 联想学习是无监督学习的基础，使网络具有在经常一同出现的模式之间学习关联的能 力。一旦学习成功，关联能力将使网络能执行有用的任务，如回忆和模式识另o m a l a 0 2 。 联想是指系统中输入和输出之间的任何联系，其中当模式a 输入到系统时，将产生模式 b 的反应。当两个模式关联时，输入模式被称为刺激，输出模式称为响应。 h e b b 规则认为：当刺激与响应同时产生时，网络将加强它们的联系。以后，当只有刺 激时也能产生响应。 h e b b 规皿：w ( 口) = w ( q - 1 ) d - a a ( q ) p 1 ( 口) 一用( 鼋一1 ) = ( 1 一y ) w ( q - 1 ) + a a ( q ) p 1 ( 口) h e b b 规则存在个问题：要求刺激不断重复，否则联想就会丢失。一个更好的i n s t a r 规则是在i n s t a r 神经元活跃时允许权值衰减，i n s t a r 规则如下： ，w ( q ) ；f w ( g - i ) + c t a f ( 口) ( p ( 9 ) - - i w ( q 一1 ) ) 另一种与i n s t a r 规则相关的联想学习规则，即k o h o n e n 规则： 。w ( q ) = ，w ( q - 1 ) + a ( p ( q ) - j w ( q - 1 ) ) 2 2 竞争网络 h a m m i n g 网络是竞争网络中最简单的例子，它的输出层神经元互相竞争以确定胜者。 竞争与联想学习规则相结合可以建立强大的自组织网络，即无监督网络。下面以h a m m i n g 网络为例说明竞争学习【m a r i a 0 2 。 前馈层 递归层或竞争层 图2 - 1h a m m i n g 网络 3 2 2 1h a n m i n g 网络 h a m m i n g 网络由两层组成。第一层( 有i n s t a r 的那一层) 将输入向量与原型向量联系起 来，第二层采用竞争方式决定哪种原型向量最接近输入向量。h a m m i n g 网络的结构如图2 - 1 所示。 2 2 2 第一层 一个i n s t a r 只能识别一种模式。为了能确定多种模式，就必须有多种i n s t a r ，h a m m i n g 网络实现了这一点。假设要让网络识别以下的原型向量： p l ，p 2 ，“，p o 第一层权值矩阵为w 1 ，偏值向量b 1 是 w 1 = 1 w r 2 w r 3 w r p ； p ： ! p ： b 1 ； r 月 权值矩阵的每一行都代表我们要识别的种原型向量，b 1 的每一个元素都设为等于每 个输入向量的元素个数r 。 第一层的输出是 a 1 ：w 1 p b 1 ： p ：p + r p ；p + 胄 p + r 2 2 3 第二层 第二层是竞争层。这一层的神经元用前馈的输出初始化。然后神经元相互竞争以确定 胜者。竞争过后，只有一个神经元有非零输出f m a r i a 0 2 。 以下公式中上标l 表示第一层，上标2 表示第二层。p o s l i n 是正线性函数，当输入值 小于0 时，输出值为0 ，当输入值大于或等于0 时，输出值等于输入值。 第一层的输出a l 用来初始化第二层： 数 a 2 ( 0 ) = a 1 然后，第二层的输出用如下递归关系更新 a2 0 + 1 ) = p o s l i n ( w 2 a 2 ( f ) ) 第二层的权值矩阵w 2 的对角元素都被设为1 ，不在对角线上的元素，设为某个小的负 4 i = j z j 1 ( 其中0 - j ，即自适应谐振理论( a d a p “v er e s o n a n c et h e o r y 简称为 a r t x ) ，它可以用来克服学习过程中的稳定性阃题。 自适应谐振理论( a r t l ) 由三个部分组成：第一层、第二层和调整子系统【c a g r 8 7 a 】。 3 2 1 自适应谐振的第一层 第一层的主要用途是比较输入模式和来自第二层的期望值模式，自适应谐振的第一层 和第二层分别记为l 1 、l 2 。如果模式不能密切匹配，那么调整予系统会墓置第二层；如果 模式能足够正确匹配，第一层将结合期望值和输入形成一个新的原型模式。 a r t l 第一层的激励输入由输入模式和l 1 一l 2 的期望值结合构成；抑制输入则由来自第 二层的增益信号构成。a r t l 第一层结构如图3 - 2 所示。 7 增益控制 图3 - 2a r t l 网络的第一层 a l 图3 - 2 中，上标1 代表第一层的信号，上标2 代表第二层的信号，p - 是一个非负数值， 代表对网络的激励输入( 使响应增加的输入) p - 是一个非负数值，代表抑制输入( 使响应 减少的输入) 。偏置值b + 和b 。是决定神经元响应的上限和下限的非负常量，激励输入为 【+ w 1 ) p ，抑制输入是r w l 】p 。w 2 ：1 是第二层到第一层的连接权。这里，p + w 2 ：l a 2 ( f ) 是输入 模式与l 2 l l 期望值的和。 第一层的运算方程为： e d n l ( f ) ，出- n 1 ( f ) + ( + b 第一层的输出计算为 a 1 = h a r d l i m + ( n 1 ) 其中，h a r d l i m 称为硬极限函数，即当输入小于0 时，输出为0 ；当输入大于0 时，输 出为1 。 8 3 2 2 自适应谐振的第二层 自适应谐振的第二层是一个连续的i n s t a r 层，其作用为：第一，规格化这一层的总活跃 度；第二，它对模式产生对比度增强，即加强中心，抑制周围，从而获得最大输入的神经元 将支配响应。第三，它像短期记忆那样通过存储对比度增强模式操作。a r t 2 的结构如图 3 3 所示。 加强中心 抑制周围 图3 - 3a f ( t i 网络的第二层 图3 - 3 中：上标1 表示第一层的信号，上标2 表示第二屡的信号，w 1 = 2 表示第层到第 二层的连接权。传输函数，是一个“快于线性”的传输函数( t r a n s f e rf u n c t i o n ) ，例如：当 ，2 伽) = ，1 2 时，该函数是一个快于线性的传输函数。它用于“加强中心，抑制周围”的反馈 连接。t + w 2 i f 2 ( n 2 ( f ) ) + 1 i ”8 1 是激励输入，+ w2 提供了“加强中心”的反馈连接， 【一w 2 】f z ( n 2 ( f ) ) 是抑制输入，。w 2 提供“抑制周围”的反馈连接。 第二层的运算方程为 9 旦塑d t = 一n 2 0 ) + ( + b 2 一n 2 ( r ” + w 2 f 2 ( n 2 。) ) + w ”a 1 一( n 2 ( f ) + 一b 2 ) 【_ w 2 】f 2 ( n 2 。) ) 3 2 3 调整子系统 a r t l 体系结构的一个关键元素是“调整子系统”。它的作用是判定l 2 l 1 ( 反馈作用) 期望值与输入模式之间是否充分匹配。当匹配不充分时，调整子系统会向第二层发出一个重 置信号。曩置信号将导致前一个获胜神经元长时期抑制，使得该神经元对系统的影响减小， 从而使另一个神经元在竞争中获胜。调整子系统结构如图3 4 所示。 p 圉3 - 4a r t l 的调整子系统 调整子系统的运算方程为 s 旦型堕：n 。o ) + ( + 6 。一。q ) ) + w 。p 卜o 。o ) + 功。) 一w 。a ，) d f 图3 _ 4 及上式中：上标0 表示调整子系统层中的信号。 3 2 4 学习规则 l 1 l 2 连接使用一种i n s t a r 学习过程进行学习。l 2 l 1 连接使用一种o u t s t a r 学习过程回 e 。每当输入模式和期望值发生了适当的匹配，在调整子系统的控制下，w “2 和w 2 = 1 都会 被更新，其中，w ”和w 2 。1 分别是l 1 l 2 、l 2 - l 1 的连接权值。这个匹配过程及随后的适应 过程统称为谐振。 1 0 w ”的学习规则是i n s t a r 规则的改进型，表示如下： 曼呸掣。口；协；w 也o ) 姘w 】a - m j w l 2 m - b - w a - o ) d f w 2 ：1 的学习规则是一个典型的o u s t a r 方程： ! 尘雩；堡旦8 ，2 v 儿一，2 ：，( f ) + 。- o ) 】 _ 8 f t 一f i f + a 1 ( f ) i 出 ”一。 3 3 自适应谐振理论( a r ：1 1 2 ) a r t 2 是a r t l 的推广，它即能处理离散数据，又能处理连续数据，具有从复杂多变的 背景噪声中提取并增强信号的能力。与a r t l 一样，a r t 2 也有两层神经元，能通过自动学 习将学习结果储存在权值矩阵中。a r t 2 有三大模块，两层神经元及一个重值模块。 a r t 2 的第一层称为f 1 层，一个信号进入f l 层后，与原有的信号混合，归一化，迭 代，直至平稳，然后才进入第二层f 2 。第二层中各神经元展开竞争，取极大值为预选的获 胜者。第二层中的预选获胜者还须进一步接受警戒线检验，通不过者将被重置，通过者才是 真正的获胜者，具有修改权向量的特权，权值使用差分方程进行修改。 a r t 2 理论有稳定性与可塑性的统一，迅速自稳定等特点。本文在第五章对a r t 2 进行 了修改，将自适应谐振算法中的重置方程的警戒线判定方法用触发条件替换，并将它应用于 解决数据广播调度问题，改进的算法有较好的性能。在本文的第五章将详细阐述。 4 基于竞争学习的数据广播调度 数据r 播即服务器将数据通过广播通道广播给客户，但是，如果不考虑客户的需求，服 务器将数据单一的广播给客户将极大的浪费带宽。为解决这一问题，展开了基于需求的数据 广播研究，其关键在于研究调度算法。 奉章介绍、分析先来先服务算法、请求数最多优先算法、等待最长的优先算法、最短服 务时间优先算法，有关r xw 算法、s i n a 算法、最长的总的s t r e t c h 优先的算法、乘除结 合的算法、s t o b s a 算法等广播算法的详细情况可参见综述。在此研究基础上，设计并实 现了基于竞争学习的数据广播调度的算法。 4 1 基本的调度算法分析 先来先服务( f i r s tc o m ef i r s ts e r v i c e 简称为f c f s ) 基本思想为：数据项按照他们请求的顺序来广播。根据数据项的到达时间进行排队，队 列中先到的排在最前面，后到的排在后面，并按照先入先出的原则进行广播。所有请求根据 到达时问都被公平对待。 最多请求数优先( m o s tr e q u e s tf i r s t 简称为m r f ) 基本思想为：服务器先广播具有最大请求数的数据项，需求量大的数据项被优先广播， 而需求量少的数据项广播的机会较少。这样需求量较少的数据项会产生饥饿状态。 最长等待时间优先( l o n g e s t w a i t f i r s t 简称为l w f ) 基本思想为：该算法选择等待时问最长的数据项进行广播。该算法的性能具有比f c f s 和m r f 更优的性能，但是对于大规模的系统，算法的系统开销较大，为产生个调度决定， 数据项必须重新计算所有数据项在某个调度点上的总等待时间，因此，增加了算法的时间复 杂度。 最短服务时间优先( s h o r t e s ts e r v i c et i m ef i r s t 简称为s s t f ) 基本思想为：该算法是种基于数据长度的调度算法，服务器选择具有最短服务时间的 数据项进行广播，也就是选择最小长度的数据项进行广播。该算法会导致长度较大的数据项 产生饥饿状态。 4 2 基于竞争学习的数据广播调度 本文所提出的基于竞争学习的数据广播调度算法根据先来先服务算法( f i r s tc o m ef i r s t s e r v i c e 简称为f c f s ) ，考虑到达时间；请求数最多优先算法( m o s t r e q u e s t f i r s t 简称为m r f ) 数据项请求数量越多，累计到达时间越长；等待最长的优先算法( l o n g e s t w a i tf i r s t 简称为 删吓) 考虑数据项等待时间：晟短服务时间优先算法( s h o r t e s ts e r v i c et i m ef i r s t 简称为s s t f ) 考虑服务时间和数据长度等所涉及的多种因素：到达时间、累计到达时间、等待时间和服务 1 2 时间( 即数据长度) ，所设计的算法使数据项之间具有较好公平性，并有较少平均等待时间， 较好伸展性( s w e t c h ) 值。 在基于竞争学习的数据广播调度算法中，按照竞争学习的观点，采用神经网络的方法， 综合考虑影响调度的诸多因素，因此，使数据广播具有良好的性能。 广播调度模型由两个隐藏层( 中间层) 组成神经网络：第一层使用联想学习原理的i n s t a r 规则，修改权值向量，第二层是竞争层，采用竞争的方式确定哪一个神经元获胜。 基于竞争学习的数据广播调度算法的输入：输入数据项由四个属性组成：到达时阃，累 计到达时间，近似等待时间和服务时间，运用竞争学习的观点学习权值矩阵，确定每个项的 权值大小，同时考虑输出，把输出作为影响因素，来进行学习。( 其中，近似等待时间即从 发出请求到开始广播这些数据项的时间) 。 该算法的输出：根据学习的结果，将输出的列向量的四个分量求和，得到输出值。对各 项对应的输出值排序，得到调度的先后次序。 基于竞争学习的数据广播调度算法的模型如图4 1 所示； 输入层 前馈层 递归层或竞争层 输出层 图4 - 1 基于竞争学习的数据广播调度算法的模型 图4 - 1 中将前馈层抽象为竞争学习规则即i n s t a r 规则或k c h o n c n 规则。第二层则抽象 为竞争层。 4 2 1 竞争层 第二层的神经元总是激活自己而抑制所有其他神经元，这称为竞争。竞争层中取最大净 输入的神经元为获胜神经元，将它的值取为1 ，而其他的神经元的值取为o 。 】3 输入层 竞争层 图4 - 2 竞争层 c 输入向量p 由一个数据项的四个特征组成：到达时间p l ：o 累计到达时间p 2 ；o 近 似等待时间p 3 ；服务时间d 4 ；其中，近似等待时间即从发出请求到开始广播这些数据项 的时间。 权值向量存储在w 矩阵中，权值w 与四个神经元连接，代表对应的四个因素：到达时 间，累计到达时间，近似等待时间和服务时间。每一行对应( 连接) 一个神经元，权值代表 各因素的重要性。 连接神经元权值矩阵为： wa 对权值矩阵作归一化处理。 首先提交第一个向量p l ： p 1 = 暇， 吼。 嵋， ， 马 召2 马 口j 嵋： ： ： 4 2 3 4 1 2 9 2 8 暇。 。 ， w 4 3 m 。 。 。 将输入向量p 。进行归一化处理的结果记为：【耳，毋：，且；，b ：r 。 求出净输入 n = w p l = w ： 比： ： 哌： 磁， 既 ， 峨。 嵋。 ； 。 既 马 马 岛 b j 0 4 0 2 0 8 o 3 然后进行竞争，即胜者全得的竞争，找到最大净输入的神经元的下标，即获胜神经元 1 4 的的下标，将它的输出为1 ，其它神经元的输出为0 。 如果有两个相同的输出比较服务时间小的项获胜。 计算：a = c o m p e t ( n ) 如 a = c o m p e t 0 4 o 2 o 8 o 3 则第三个神经元获胜。 4 2 2 前馈层 图2 - 1 和图4 - 的含义不完全一致，前馈层抽象为竞争学习规则。 前馈层根据联想的原理j n s m 规则修改权值矩阵： 。w ( q ) z l w ( q - 1 ) + a d ，( q ) ( p ( q ) 一i w ( q 一1 ) ) ( 4 1 ) ，_ ( q ) 表示第i 个神经元的修改后权值，即第q 次的权值，w ( q - 1 ) 表示第i 个神 经元原来的权值，即第q 次的权值。 n 是学习率，取为0 1 之间的值，学习速度较快则，q 较大：反之亦然。它可根据实际 情况选取。 d i ( q ) 作为调节因子；如果要求有良好的伸展性( s t r e t c h ) ，那么，d i ( q ) 为数据项的伸 展性( s t r e t c h ) ；如果要求有趣好的平均等待时间，那么，d ，( q ) 为数据项的平均等待时间。 ( 1 ) 要求具有良好的伸展性( s t r e t c h ) 。一个数据项： 。， 响应时间等待时间+ 服务时间 近似等待时间+ 服务时间 m 砌5 丽丽。1 萄丽_ 。丽菊摘一( 4 。) 对于多个数据项计算如下： ( 4 - 3 ) ( 2 ) 要求有良好的平均等待时间 一个数据项： 平均等待时间；现在广播时间+ 这一项的服务时间一塑翌盟罴掣 1 5 ( 4 4 ) 对于多个数据项计算总等待时间 总等待时间= 现在广播时间+ 第一个项的服务时间一塑二霉竺曩薯；擎塑 + 现在广播时间+ 第一项服务时间+ 第二项的服务时间一笪亏差兰蔷；萎塑+ ( 4 5 ) 平均等待时间t 恧翥薹； c 。c ， 调节因子d ( q ) 是根据上面给出不同的学习函数计算得到的。 更新权值使用i n s h a r 规则，对于特殊情况，可以使用k o h o n e n 规则 对刚才的输入p t ，是第三个神经元获胜，用k o h o n e n 规则更新第三个神经元的权值。 3 w “； w o “+ a ( p 1 一t w 。“) ( 4 7 ) 然后对每一个输入进行同样的分析，竞争，然后修改权值。 如果最后得到收敛的权值矩阵，即权值矩阵 一w ls ，后一次学习得到的权值矩阵 与前一次得到的权值矩阵的值小于某一个较小的正数。那么竞争学习完成。 4 2 3 进行排序并选择调度 本文将修改后的权值矩阵乘以每一个数据项对应的输入，对于每一个输入，得到一个列 向量。将列向量的各个分量求和。这样，每一个数据项对应一个输出值。同样，输出值大表 示数据项重要，输出值小表示它不太重要。 对所有数据项的输出值按照其大小进行排序，按照排序的结果将数据项广播出去。 如果有相同的输出值，先广播服务时间短的数据项。 4 2 4 算法描述 基于竞争学习的数据广播调度算法在m a t l a b 环境下实现【张志涌，2 0 0 3 ， 闻新， 2 0 0 0 ，【飞恩科技产品研发中心，2 0 0 3 ，【刘志俭，2 0 0 0 。 基于竞争学习的数据广播调度算法的基本思想是：其输入筵随机产生的具有四个特征即 到达时间，累计到达时间，近似等待时间和服务时间。神经元之间进行竞争，获胜的神经元 将可以修改权值，对每一个输入都进行学习，直到输入学习完成。将最终学习好的权值矩阵 乘以输入，对应于每一个输入都得到一个输出的列向量，将列向量的各个分量求和，得到一 个输出值。对这些输出值进行排序，得到需要广播调度的先后次序。 1 6 基于竞争学习的数据广播调度算法描述： 1 【初始化】随机产生4 4 的权值矩阵谬。将权值矩阵进行归一化处理：控制变量q 置为1 。 2 【随机产生输入向量】随机产生n 个输入向量，它们由四个分量组成，每个分量对应 于到达时间累计到达时间，近似等待时间和服务时间。 3 【学习速率，闽值，循环次数m a x 】由用户给定：学习速率q ，它是0 - 1 之间的一个 数；阀值0 ，循环次数m a x 。 4 学习权值矩阵 依次循环处理n 输入向量： 4 1 取输入向量并对它进行归一化处理，使输入向量的范数慨j f = 1 。 4 2 求出权值矩阵与输入向量的内积。 4 3i 竞争】神经元进行竞争，根据公式a = c o t a p e t ( w p ) ，选择具有最大值的神 经元为获胜神经元，有相同的最大值时，选择具有服务时间小的为获胜神经元。 4 4 对获胜的神经元修改权向量，。曹( q ) l j w ( q 一1 ) + a d f ( q ) ( p ( q ) - - i w ( q - 1 ) ) 。 4 5 【判断】如果b w ( q ) - f w ( q 一1 ) 卜口或q m a x ，那么，转向5 ；否则，转向4 3 。 5 【输出值的计算】将最后学习的权值矩阵乘以一个输入向量，得到一个列向量，将列 向量的各个分量求和，这样每一个输入向量对应一个输出值。 6 排序并调度】将所有的输出值进行排序。排序的结果即作为广播数据项的先后次 序。如果有相同的输出值，先广播服务时间短的数据项。 4 2 5 对基于竞争学习的数据广播调度算法示例说明 在下列数据中随机产生的2 0 个数据项，将基于竞争学习的数据广播调度算法与先来先 服务算法( f c f s ) ，最长等待时间优先算法( l w f ) ，及最短服务时间优先算法( s s t f ) 比 较，用m a t l a b 进行试验得数据结果。试验结果表明，最短服务时间优先算法具有最大的 伸展性( s t t e t c h ) 值，而基于竞争学习的数据广播具有最小的伸展性( 咖t c h ) 值，具有更好的性 能。 先来先服务算法的最小伸展性( s t r e t c h ) 值：m i n s t r e t c h i x i a n = 5 4 3 最长等待时间优先的昂小伸展性( s t r e t c h ) 值：m i n s t r e t c h d e n g = 4 3 5 最短服务时间优先算法的晟小伸展性( s t r e t c h ) 值：m i n s t r e t c h f u = 8 7 6 竞争学习算法得到的最小伸展性( s t r e t c h ) 值：m i n s t r e t c h j i n g = 2 7 3 1 7 数据项数为2 0 时的最p j 、s t r e t c h 值 1 0 0 。i图圈 i8 0 j l + 悃h l i 一1 群嘲il ，嘲 u f c f s w fs s t f j z x 图4 - 3 数据项数为2 0 时的最小s tr e t c h 值 1 8 5 自适应谐振模型的改进及其应用 本章将自适应谐振模型的工作思想用于对数据广播进行调度，但是，自适应谐振模型中 采用的警戒线依赖专家主观给出阈值，本文对此进行了改进，提出了一个客观评价标准 多数据项的可伸展性和平均等待时间。改进的自适应谐振模型算法的基本思想如下：首先， 综台考虑影响调度的因素，将一个数据项的四个特征：到达时间，累计至h 达时间，等待时间， 服务时间作为的自适应谐振模型算法的输入；其次，修改了重置方程中的触发条件；第三， 将修改后的权值矩阵乘以每一个数据项对应的输入，对于每一个输入，得到一个列向量。将 列向量的各个分量求和。这样，每一个数据项对应个输出值。对所有数据项的输出值进行 排序，按照排序的结果将数据项广播出去。如果有相同的输出值，可采用下列策略之一，先 广播服务时间短的数据项或先广播到达时问早的数据项。本文将这种改进的算法称为改进自 适应谐振模型算法( i m p r o v e m e n t a l g o r i t h mo f a d a p t i v er e s o n a n c e t h e o r y 简称为i a o a r t ) 。 5 1a r t 2 的拓扑结构 a r t 2 有三大模块，两层神经元f 1 层，f 2 层及一个重置模块。f 1 层中有1 7 1 个神经处 理单元，f 2 层中有n m 个神经处理单元，两层连接采用全连接，图5 - 1 显示了f 1 层中第i 个神经处理单元与f 2 层中第j 个神经处理单元的连接，从i 到j 的权记为z j i ，从j 到i 的权 记为毛i ，i _ 1 ，m ；j = m + i ，n 。 5 1 1f l 层 f l 层又分为3 个子层：下子层f l l ，其功能是输入信号；中子层f 1 2 ，其功能是混合输 入信号和反馈信号，并进行相关处理；上子层f 1 3 ，其功能是接收来自f 2 层的反馈信号。 图中大黑点表示归一化运算，小黑点表示一个节点( 小处理单元) 。当时间离散化时，上行箭 头表示传递当前t 时刻的前馈信息，下行箭头表示传递前一时刻t - i 的反馈信息。第i 个神 经处理单元除了包含三个大节点以外还包含六个节点。下子层有一对节点w i ，x i ，中子层有 一对节点u f 和7 i ，上子层有一对节点p i 和q f 。 5 1 2 f 2 层 f 2 层是竞争网络，与a r t l 中相仿。 5 1 3 重置模块 a r t 2 有重置模块，与a r t j 中相仿。 1 9 5 2f 1 层短期记忆方程 f l 层短期记忆方程的作用是对信号的一个短暂存储。 在f 1 层的输入向量i ( t ) 由四个分量组成：到达时间i ，、累计到达时间i z 、近似等待时 间1 3 和服务时间1 4 ，其中，近似等待时间为从发出请求到开始广播这些数据项的估计时间。 一个信号i ( t ) 进入f 】层后，其分量分别进入各自对应的神经处理单元，它与神经处理 单元中原有信号混合，并进行归化、迭代过程，直至平稳，然后与f 2 层发生联系。这段 时间内f 1 层神经元的各节点状态叫做短期记忆，信号混合、归一化、迭代以及记忆方程由 f 列公式给池。 a f ( u j 图5 1 r t 2 的神经元和结构示意图 分量形式 p 。；“。+ g ( y j k j q ；= p i “e l k l l ) h i = q ( e + v ；= f ( x ，) + b ，( q ，)v = 【f ( x ，) ， w i = i i + 口“二 z ，w i ( e + l h l ) 向量形式 p = u + d z j q = p 他+ | | p | | ) u = v ( e + ) ，f ( x 。) i t + 6 【，( q ，) ，f ( q 。) 】 w = i + a l l x f = w f “e + ) 归一化 归一化 信号混合 归一化 上面公式中j 为f 2e p 通过竞争预选的神经元，该点向下的权向最为 2 jt ( 2 ，z j mr 。参数n ，b 均为较大的正数，学习参数0 d l ，弱归一化参数e 取较 小的正数，这样x ，q ，u 都是靠近单位球面内侧的向量，是一种近似的归一化，而不是严格 的归一化。函数“) 如下 m ，2 = 0sxs0 os 工s 1 式中截尾参数。取小的正数，它的作用是消除噪声，如输入或反馈的数据太小，就视为随机 扰动的噪声予以滤除。函数g ( ) 如下 毗，。倚 如乃= m a x 仉： ，为厂2 中未被强行抑制的单亍日 其它 5 3f 2 层短期记忆方程 记 l = 烨“ 它是f 2 中第j 个神经元处理单元收到的杀自f 1 的信号的整合值。f 2 中各单元展开竞 争，取极大 t j = m n x t 第j 个单元成为预选的获胜者。无论j 是否通过警戒线检验，它都将自己的长期记忆即 权向量z ，= 1 2 j 】，z r 反馈到f 1 3 。 5 4 自适应谐振原来的重置方程 f 2 中预选获胜者j 还须进一步接受警戒线检验，通不过者将被重置，通过者才是真正 的获胜者，具有修改自己长期记忆( 即权向量) 的特权。本章将专家根据主观经验的警戒线 替换为通过客观数据计算出来的触发条件值。 将f 1 中的u i 和p i 咀适当的比例加权迭加，然后弱归一化得： 。 竺翌! “e + i i + c i l p l i 式中