（计算机应用技术专业论文）基于多agent的iptv节目调度系统.pdf

哈尔滨工程大学硕十学位论文 摘要 近年来，随着宽带计算机网络技术的发展及视频技术的日趋成熟，i p t v 应运而生。然而，视频具有带宽高、数据量大及实时性强的特征，这使得大 量用户的同时点播常常造成网络带宽的瓶颈，网络传输能力的不足阻碍了 i p t v 的广泛应用。因此，论文力图通过节目调度系统的设计，用尽可能少的 资源为大量用户提供i p t v 服务。 ， 。 多a g e n t 技术是目前计算机科学领域中非常重要、研究活跃的内容之一， 是解决分布式、实时性问题的一种新的途径。论文以多a g e n t 技术为理论基 础，对i p t v 节目调度问题进行探讨和研究。 论文首先对i p t v 节目调度做了简要介绍，讨论了i p t v 节目调度系统的 性能的评价指标；其次，对基于多a g e n t 的i p t v 节目调度系统做了详细的系 统设计，阐述了系统的工作进程，并且提出了a g e n t 的基于记忆演化的强化 学习；再次，在对a g e n t 之间的通信与协商机制进行分析对比的基础上，提 出了适用于i p t v 节目调度系统的a g e n t 之间的通信与协商算法：最后，进行 了算法的验证实验并且对实验结果进行分析，验证了模型和算法的有效性。 关键词：多a g e n t ；i p t v 节目调度；记忆演化；强化学习；通信与协商 哈尔滨工程大学硕十学位论文 a b s t r a c t r e c e n t l y , a l o n g 1 i t l l t h e 黜f g e n o ft h ei n t 锄吼嬲ap e r v 船i v e c o n 删i l i l i c a t i m e d i u ma n dam a t u r ev i d e ot e c h n o l o 鼢m t ve m e r g e s 、 ，i t l it h e t i m er e q u i r e h o w 册, d u et ot h eh i 曲b 锄d 诵d mr e q u i r e m 黜，b i gb l o c i 【so f 也曲ma n dr e a l 砸m em 咖o fv i d e o ，t h el z a n s m i s $ i o na b i l i t yo ft i l en e t w o r ka r e p r o v i n gt 0b eb o t t l e n e c ki i lt h e 、v i d e s p r e a du s a g eo f “d e os t r e a m i n go v e rt l l e i n t c m 眈kt h i sd i s s e r t a t m l l ，w cd e s i 鲫ac o n t e n td e l i v e r ys y s t e mo f i p t vi no r d e r t op r o v i d cs e i c i n gf o rm o r e1 1 c c e s $ u s e r sw i t hl e s sb 柚d 、i d t hr e s o u r c e s m 啪a g e n tt e e l m o 蛔i so n eo ft h em o s ti m p o r t a n ts t u d i e sa n da c t i v e c o n 】眦si nc o m p u t e rs c i e n c ed o m a i na tp r e s e n t , i tp r o v i d e san e ww a yf o rt h e r e s e a r c ho fd i s t f i b m e da n dr e a l t i m ep r o b l e m s a l o n g 、v i t l lt h em d t i - a g e n t t e c b l l o l o g y t h i sd i s s e r t a f i o nd i 峭s e san c 啊t m e t h o dt dd e a l 、v i t l lt l l e c o n t e m d c l i v e r yp r o b l e mo f 口t v f i r s to fa 1 1 t h ed i s s e r t a d o ni n t r o d u c e sc o n t e r l td e l i v e r yo fi p t vb r i e f l y ，a n d 敝u s s e st h ei n d e xo fp e r f o r m a n c ci l lt h i ss y s t e m s e c o n d l y , t h i sd i s s e r t a t i o np u t s f o r w a r dt h ep r e n m i n a r yd 髂i 弘o fc 0 雠m td e l i v e r ys y s t e mo fm t 址e x p a l i a t eo n t h ep r o c c 豁o ft h es y s t e m a l s ot h ed i s s e r t a t i o np u t sf o l w a r dam e m o r ye v o l i n i o n b a s e d i n f 妇m 饥tl e a r n i n g 蛔f i t h m t h i r d l y , b a s e do nt h ed r a w b a c i 【so ft h e p r e s e n te o m m u n i c a t i o na n dc o o r d i n a t i o nm e t l l o d s t h i sd i s s e r t a t i o np u t sf o r w a r d t h ec 0 删倒a n dc o o r d i n a t i o nm e t h o dw h i c hi sf i tf o rt h ec o n t e n t & l i v e r y s y s t e mo fp t 、，m o s t a tl a s t , t h i sd i s s e r t a t i o nr e a l i z e st h em o d e la n d 姆f i t h m t h r o u g he ) 【p e r i i m n ta n da n a l y z e st h e 托辄l 乜o ft h ec x p e r i m e n ti l lo l d e r 幻v c r i 分 t h ee f f e c to f t h i sm o d e la n da j g o r i t h m y w o r d s ：m u m a g e n t ； c o n t e n t d e l i v e r y o fl p t v m e m o r ye v o l u t i o n ； r e i n f o r e e m 髓tl e a r n i n g ；c o m m u n i e a t i o na n dc 0 0 r d i n a t i o n 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的 指导下，由作者本人独立完成的。有关观点、方法、 数据和文献的引用已在文中指出，并与参考文献相对 应。除文中已注明引用的内容外，本论文不包含任何 其他个人或集体已经公开发表的作品成果。对本文的 研究做出重要贡献的个人和集体，均已在文中以明确 方式标明。本人完全意识到本声明的法律结果由本人 承担。 作者( 签字) ：蔓11 垫丝 日期：阳7 年1 月 哈尔滨= 【= 程丈学硕十学 7 = 论文 1 1 引言 第1 章绪论 进入2 0 世纪9 0 年代以后，随着科学技术的进步，互联网的发展，信息 化革命使整个世界发生了巨大改变。特别是互联网的迅猛发展，改变了人们 传统的行为习惯，人们更倾向于主动的获取信息。对于电视媒体这个百姓生 活中最不可缺少的信息来源来说，传统的有线电视技术缺乏对用户管理的功 能，单一的频道形式使用户的个性化需求难以体现，媒体的多样性被简单成 一种单向的传播，不能满足人们及时、主动地观看电视节目的需求。i p t v ( i n t e r n e tp r o t o c o lt e l e v i s i o n ，即互联网协议电视) 应运而生，它是一 种能够将传统媒体转变成全新的、互动式的、个性化需求体验的技术，是在 现有电信宽带网络上将视频媒体融合到电信业务中的最佳技术。通过i p t v 的 应用，可以实现包括：视频点播、视频直播、上网浏览等丰富的业务形式。 鉴于网络结构的现状，目前i p t v 业务的运营基本采用多节点部署方案。 现存的大部分解决方案是将节目中心的节目全部或大部分存储到节点上。这 将导致低效的存储空间使用、不必要的节目复制“- 。i p r r v 系统可以通过一个 完善的节目调度系统，动态的调整节点上缓存的节目的分布，从而提高存储 空间的利用率。为了确保在现有带宽条件下i p t v 业务的正常运营，为了使提 供i p r v 业务的运营商都能受益，并且要使每个运营商都有比竞争对手更强的 竞争实力，就必须加强对i p t v 节目调度问题的研究，因此，如何高效的进行 i p t v 节目调度已经引起人们的广泛关注。特别是国际上一些著名的企业。如 k a s e n n a 公司、从a m a i 公司等在i p t v 节目调度实践中取得的成就，更使人们 坚信i p t v 节目调度是提高i p t v 竞争力的一个有效途径，因而吸引了许多学 者和企业界人士对i p t v 节目调度问题进行研究和实践。 人工智能技术( a r t i f i c i a li n t e l l i g e n c e ) ”是研究如何使机器( 计算 机) 具有智能的科学和技术，特别是人类智能如何在计算机上实现与再现的 科学和技术，是计算机科学的一个分支。随着人们对人工智能技术研究的发 哈尔滨工程大学硕士学位论文 展，计算机网络等的迅速普及和人们认识上的进步，人工智能逐渐转向对人 工智能的核心问题 g e n t 技术的研究“，a g e n t 技术以其特有的自治性、 合作性、反应性等特点，成为继对象技术后，计算机领域的又一次飞跃。目 前，全球范围的a g e n t 研究的浪潮正在兴起，包括计算机、人工智能以及其 它行业的研究人员正在对该技术进行更深入的研究并将其引入到各自的研究 领域m 一，为更有效她解决生产实际问题提供新的工具。 随着a g e n t 技术与i p t v 的蓬勃发展，将两者结合已逐渐成为人工智能领 域的一个研究热点。如何将先进的a g e n t 技术应用于i p t v 领域，是近几年来 计算机研究者寻找的个新焦点。本文的工作正是基于这样一个背景开展的， 在研究过程和实践中，针对i p t v 节目调度问题的现状，结合计算机与人工智 能领域的最新理论成果多a g e n t 技术，进行基于多a g e n t 技术的i p t v 节 目调度问题的探讨与研究，以期为i p t v 节目调度问题的实际解决提供有益的 探索。 1 2 研究的目的与意义 据专家预测，到2 0 0 6 年，全球i p t v 业务收入将达到8 0 亿美元，用户数 将超过8 0 0 万；到2 0 0 8 年，随着欧洲、亚洲各地区的i p r r v 运营商准备就绪， 北美地区、亚洲、欧洲的i p t v 市场份额分别上升至2 8 4 、4 3 跳、1 6 9 。 全球用户数将超过2 0 0 0 万，约为目前用户数的l o 倍，i p t y 具有巨大的市场 空间和发展前景。在i p t v 业务的运营中，如何在日益复杂和不断变化的分布 式动态环境中，在确保骨干网络负载最小的前提条件下，调度节目、优化节 点上缓存的节目的分布、高效的使用存储空间是i p t v 研究中最困难、最具有 挑战性的课题。对i p t v 节目调度问题的研究不仅使i p r v 业务能够更好的满 足用户需求，提高i p t v 业务的运营商的竞争实力。而且，对典型的分稚式、 动态资源调度这类复杂调度问题提出了新的解决方案。因此，对i p t v 节目调 度问题进行研究是具有很高实用价值的。 同时，多a g e n t 技术是近年来人工智能领域探讨的热点，多个具有自治 特性和智能特性的a g e n t 在一起，进行协调、协商、协作，以期高效的完成 各种各样的合作任务是非常有效的，但不能对a g e n t 技术的研究仅仅停留在 2 哈尔滨工程大学硕士学位论文 理论方面，必须和现代较为先进的技术相结合，解决许多实际问题。多a g e n t 技术和i p t v 领域的结合正是这样的一个尝试。将先进的多a g e n t 技术限定在 一个具体的应用领域进行研究，可以丰富其学术价值，同时很好的解决实际 问题也是进行学术研究的宗旨。 目前，i p t v 和多a g e n t 技术均是业界研究的热点和难点，对i p t y 节目 调度问题的研究，必然可以极大的推动i p t y 的发展，提高其市场竞争力，同 时将多a g e n t 技术的研究成果运用于更多的领域，也将会极大的推动多a g e n t 技术在理论方面的研究发展。 1 3 国内外相关领域研究现状 目前，国内外许多专家学者对与i p t v 节目调度类似的调度问题进行了研 究，将他们所做的研究按照解决调度问题的方法分为如下几类。 1 传统方法。传统方法是对调度问题进行数学抽象，在此基础上建立数 学模型，然后通过运筹学等方法以及最优控制理论求取最优控制”一- 。由于所 研究对象、问题的不确定性、复杂性、多变性、高度非线性等状况，人们往 往难以对所研究问题建立起精确的数学模型来进行描述，传统方法难以解决 实时性、突发性很强的复杂对象的问题，传统方法的最优控制在实际应用中 未必最优。 2 智能控制方法。随着现代科技的快速发展，计算机技术、控制理论和 控制方法的不断发展，采用新的计算机技术、人工智能技术进行调度控制， 已经成为调度控制发展的必然要求。许多专家学者提出了运用智能控制技术 解决分布式调度问题w ，应用模糊控制理论、专家系统等方法来解决类似调度 问题的研究十分广泛。智能控制通过模拟人的智能的决策方法来达到控制的 目的，是一种非模型的控制方法，该方法在处理复杂性、不确定性的问题时， 显示出强大的效果，但是智能控制技术一般以智能推理为核心，在实际应用 中很难达到预期效果。 3 多a g e n t 方法。近年来，随着计算机技术、信息技术以及各类相关技 术的迅猛发展，多a g e n t 技术的研究也在不断深入，许多专家学者运用多 a g e n t 方法解决调度问题m m 多a g e n t 系统中每个a g e n t 都是一个具有相同 哈尔滨丁：程大学硕士学位论文 的问题求解方法的自治系统，能利用局部信息进行自主规划，并能通过规划 推理解决局部冲突实现协作，从而完成与自身相关的局部目标。多a g e n t 技 术将大的复杂系统建造成小的，彼此相互通信及协调的，易于管理的系统， 采用多a g e n t 技术解决调度问题，具有很强的鲁棒性和可靠性。并具有较高 的问题求解效率。 多a g e n t 系统所具有的分布性、开放性、适应性和鲁棒性使其成为描述 i p t v 节日调度系统的理想工具，多a g e n t 系统强调分布式自主决策，强调各 个a g e n t 之间协作解决问题的能力，这些特点正好符合i p t v 节目调度问题的 特征，因此本文以多a g e n t 技术为基础，对i p t v 节目调度问题进行了研究。 且前已有的研究成果在各个相关领域都取得了较好的成果，但是仍然存在许 多阀题，总的来说有以下几点： i 缺少整体指导和分析； 2 几乎所有的行为都是基于自私的角度进行的，有时容易顾此失彼，造 成资源的浪费； 3 学习能力弱，很难完全适应环境的变化。 为了解决上述问题，本文对多垴e n t 之间的学习、协商、通信问题进行 了研究，并将其应用到i p t v 节目调度闯题中。 1 4 课题主要研究内容 1 i p t v 节目调度闯题与调度系统性能指标的研究 i p t v 是个新兴的领域，目前还没有关子i p r v 节日调度问题解决方寨的 优劣的共识，论文通过对i p r v 节日调度的工作原理的分析，探讨了衡量i p t v 节目调度系统的优劣的性能指标。 2 基于多a g e n t 的i p t v 节目调度系统控制结构的研究 根据a g e n t 的特点，结合i p t v 节目调度问题的实际情况，论文探讨了采 用多a g e n t 理论建立w r y 节目调度系统的控制结构。 3 i n 节目调度系统中a g e n t 模型结构的研究 根据a g e n t 技术所具有的模拟自治性实体的特征，进行基于多a g e n t 技 术的i p t v 节目调度问题的研究，在论文中探讨了i p l t 节日调度系统中各 哈尔滨1 ：稃大学硕十学位论文 a g e n t 所具有的结构特征。 4 i p 节目调度系统中a g e n t 的强化学习算法的研究 强化学习算法的巨大优势已为人们所普遍接受，并广泛的运用到各种领 域中去，以提高系统对环境的适应性。在论文中，对如何在i p t v 节目调度系 统中更好的采用强化学习算法进行了进一步的研究。 5 i p t v 节目调度系统中a g e n t 之间的协商与通信的研究 根据| g e n t 的协作性，在论文中探讨了i p t v 节目调度系统中a g e n t 之间 的协商与通信机制，通过规范的通信语言和合理的协商过程，试图找到合理 的解决方案。 6 基于多a g e n t 的i p t v 节目调度系统的实验 基于多a g e n t 的i p t v 节目调度系统的研究是一个庞大的、长期的研究过 程，需要大量的人力、物力的投入，作为对该研究的初步尝试，在目前的情 况下，在北京世纪鼎点软件有限公司的鼎点天源实际系统上做了对比实验， 为今后进一步的工作奠定了基础。 5 哈尔滨工程大学硕士学位论文 第2 章i p t v 节目调度 2 1l p t v 节目调度的环境 i p t v 受到各大运营商越来越多的重视，不过，良好的发展前景与制约其 发展的瓶颈问题是并存的，当前的网络传输能力是制约i p t v 发展的一个瓶颈 问题。在网络传输能力短时间内不可能大幅提高的情况下，只有采用多节点 部署方案，才可使在现有带宽条件下进行i p t v 业务的运营成为可能。 基于多节点部署的思路，目前国内外有基于c d n ( c o n t e n td e l i v e r y n e t w o r k ，即互联网内容发布网络) 结构和基于分布式结构两种调度技术路线。 1 基于c d n 结构 c d n 是一个建立并覆盖在互联网之上、由分布在不同区域的节点服务器 群组成的虚拟网络。c d n 技术是一种解决互联网性能不佳问题的有效手段。 其基本思路是通过在网络各处放置边缘( e d g e ) 服务器，从而能够实时地根 据网络流量和各节点的连接、负载状况以及到用户的距离和响应时间等综合 信息将用户的请求重新导向离用户最近的服务节点上。c d n 系统更多的是强 调如何有效的将中心节点的数据高速、准确的分发到边缘节点。但是，c d n 系统的构建理念，是基于传统的网络文件内容分发，然后逐步增加视频内容 分发功能的，在面对成百上千节点的流媒体覆盖网络对。将无法有效为最终 用户提供高质量的服务。 2 基于分布式结构 分布式结构是一种完全面向流媒体传输的多视频节点的协同工作系统， 与c d n 技术不同，它通常采用软件实现，具有部署灵活，成本低廉，易于维 护和扩展的优势。分布式结构中，各节点的能力是均衡的，它们之间是相互 协作的关系，节目内容依据使用情况和运营规则在整个系统中动态流动。分 布式结构更加适应信息动态和不确定的宽带互联网应用环境，因此也是大规 模部署i p t v 业务的理想技术模式。 鉴于分布式结构更加适应信息动态和不确定的宽带互联网应用环境，是 6 哈尔滨工程大学硕士学位论文 大规模部署i p t v 业务的理想技术模式，本文采用多a g e n t 技术解决基于分布 式结构的i p t v 系统中的节目调度问题。 2 2i p t v 节目调度的技术要求 i p t v 节目调度问题可能发生在不同的运营商之间，或者同一个运营商的 不同的局部地区之间。当用户点播节目的同时，系统就会收集用户点播的细 节，这些交互接着引发一连串的动作，包括节目发送动作，系统收集到的资 料会被送给i p t v 节目调度系统以调整缓存中节目分布。根据对i p t v 节目调 度问题的具体实际情况的分析，用户的点播请求是大量的、动态变化的、随 机的。那么，为了满足这些需求，i p t v 节目调度系统必须满足以下要求： 1 快速、正确收集用户的需求，进行i p t v 节目调度需要采集大量的历 史信息，并且对历史信息进行统计分析： 2 以最低代价( 最小的平均用户响应时问，最多的本地满足用户请求数， 最低的平均带宽利用率等) 做出正确的迎合用户需求的决策； 3 根据环境的变化，做出正确的适合环境的决策； 4 在整个调度过程中，从取得用户点播细节到完成节目调度的过程中， 完成正确的决策。 2 3i p t v 节目调度的性能指标 为了便于比较和评价调度系统满足技术要求的程度，先讨论i p t v 节目调 度系统的性能的评价指标。 对文中涉及的有关概念进行定义。 定义2 1 ：在系统中，称在某一局部地区提供i p t v 服务的一组服务器为 节点。单个节点通常由一个应用服务器、一个管理服务器、若干媒体服务器 组成。 定义2 2 ：称节目在磁盘上存储的块为i p t v 节目调度的最小粒度。 i p t v 是个新兴的领域，目前还没有关于i p t v 节目调度问题解决方案的 优劣的共识，本文通过对i p t v 节目调度的工作原理的分析，提出如下四项性 能指标衡量i p t v 节目调度系统的优劣。 7 哈尔滨工程大学硕士学位论文 1 调度算法的平均执行时间延迟 。 ， 对多节点部署方案中的每个节点来说，调度策略的实际执行时间与最适 合此节点的调度策略执行时间经常存在不一致的情况。因为i p t v 节目调度问 题具有动态时变性，如果实际执行时间与最适合执行时间偏差较大，不仅会 导致调度策略失效，调度系统性能降低，而且会对此节点上i p t v 业务的运营 产生不良影响。因此，调度算法的执行时间延迟是衡量i p t v 节日调度系统的 一个重要指标。一 i k k i 。 f = ! 二。一( 2 - 1 ) 以 其中，r 表示调度算法的平均执行时间延迟，n 表示此统计周期内执行的 调度策略的数目，r 。表示调度策略产生的时间，k 表示调度策略执行的时 间，r 越小系统性能越高。 2 骨干网络的平均数据流量 系统的目的是避免现有的网络传输能力成为运营i p t v 的瓶颈，尽可能满 足更多的用户需求，尽可能减少网络的数据流量。因此，骨干网络的平均数 据流量是衡量i p t v 节耳调度系统的一个重要指标。 y 6 = l ( 2 2 ) 仃 其中，表示骨干网络的平均数据流量，n 表示此统计周期内骨干网络 上传输的节目数，6 j 表示每个节目的大小，占。越小系统性能越高。 3 本地服务失效频率 本地服务失效频率是指在一段统计周期内，用户点播请求不能在节点本 地被满足的次数占总用户点播请求数的百分比。 | ，对：坐墼 ( 2 3 ) 1 7 ， 其中，玎表示本地服务失效频率，n 表示此统计周期内总用户点播请求数， 表示不能在节点本地满足的用户点播请求数，譬越小系统性能越高 4 平均响应时间 0 哈尔滨工程大学硕士学位论文 平均响应时间是指用户从发出点播请求到待到视频服务的时间总体分布 情况。好的系统应该尽快做出正确的迎合用户需求的决策，从而降低平均响 应时间。因此，平均响应时间是衡量i p t v 节目调度系统的一个重要指标。 k k ) t = l 一 ( 2 4 ) 再 其中，t 表示平均响应时间，n 表示此统计周期内发出请求的用户数，z 0 表示用户得到视频服务的时间，表示用户发出点播请求的时间，t 越小系 统性能越高。 在实际应用中，要从不同的角度去考虑这几个指标来设计合理的i p t v 节 日调度系统。本文根据系统的性能指标，设计了基于多a g e n t 的i f r v 节目调 度系统。 2 4i p t v 节目调度的基本原理 2 4 1i p l y 的定义 业界对于i p t v 的定义众说纷纭最初，大家都认为i p r v 就是在互联网 上看电视，但随着i p t v 技术的迅速发展，业界人士对于i p t v 的定义进行了 不断的扩充，i g r v 的内涵已经远远超出了通过互联网看电视的说法，到目前 为止，业内一致认为：i p t v 是互联网协议电视，是一种基于宽带互联网与宽 带接入，以机顶盒或其它具有视频编解码能力的数字化设备作为终端，为用 户提供多种交互式多媒体服务的宽带增值业务，其应该包括视频点播( v o d ) 和t v 直播这两种最基本的业务。 2 4 2i p t v 节目调度 由于i n t e r n e t 的迅速发展，i p t v 用户数的迅速增长，i p t v 行业内部及 i p t v 同数字电视的激烈竞争，使得骨干网络承载的压力越来越大，运营商越 来越需要控制运营成本，为用户提供越来越好的服务，所以i p ? v 节目调度越 来越重要。 一 。 。， i p t v 节目调度即通过收集用户点播信息，分析预测用户的需求，从而生 9 哈尔滨工程大学硕士学位论文 | _ i ；目；一 成相应的调度策略，并执行这些调度策略的过程的总称。它连接用户、节点 和节目中心，根据用户需求的变化，动态的调整节点上缓存的节目的分布。 图2 1 表示了一个简单的i p t v 节目调度关系，图中详细的说明了i p t v 节目 调度的层次关系。 图2 i 简单的i p t v 节目调度关系图 2 4 3 基本的i p t v 节目调度模式 研究 1 2 ，1 3 表明，随着互联网与w w w 技术的发展，人们更乐于及时、主 动地观看电视节目，用户需求为主的模式正迫使传统、以推力为主的模式转 而成为拉力为主的模式。图2 2 说明了上述模式的改变，这是i 阿v 节目调度 的。推”和“拉”的模式的图形表示。在传统的“推”模式里，节目被“推” 到用户手中。而在“拉”模式里，用户实际开始了i p t v 节目调度的第一步行 动。 推：而1 苏3 、厂_ 推：f ! ! ! 竺卜一三，掣毒1 1 塞 扭臣叵 享互瑟 弋丑三嚣扭【! 竺 - 掣灿一! ：l 卜二；： 图2 2 推式与拉式的i p t v 节目调度 。 一般而言，。拉”的概念比较简单而且有吸引力。为了解决i p t v 节目调 度问题，本文试图用多a g e n t 技术去分析i p t v 节目调度问题内部的关系，解 决问题。 0 哈尔滨工程大学硕士学位论文 2 4 4l p t v 节目调度的要素 从较高的层次划分，i p t v 节目调度可分成四个关键过程：收集统计信息、 生成调度策略、执行调度策略和效能测量。它们的功能如下 1 收集统计信息。它的功能在于及时、有效的收集与i p t v 节目调度相 关的信息，并对信息进行合理的统计，是保障i p t v 节目调度成功进行的基础 步骤。 2 生成调度策略。它的重点在于适时、适所和正确的生成调度策略，而 生成调度策略的发展趋势是具备预知需求和补充节目的能力，它的目标主要 是能够处理需求的不确定的动态变化。 3 执行调度策略。执行调度策略过程主要完成节目调度的真正行动。 4 效能测量。可以追踪i p t v 节目调度系统本身健全与否，为了做出明 智的选择和快速响应环境瞬息万变的情况，这种测量是必须的。 2 4 5i p t v 节目调度的基本结构 i p t v 节目调度是一个非常重要的概念，i p t v 节目调度系统发展至今，主 要有两种不同复杂程度的系统结构。 1 集中式。即建立一个调度控制中心，对众多节点实行节目调度控制。 这种系统结构的优点是可以对所有的节点实行统一的、一致的节目调度控制， 可以根据所有节点的情况，对节点进行全局最优节目调度控制；缺点是信息 的处理量比较大，调度的周期比较长，很难根据每个节点的环境的变化灵活 的产生、调整调度策略。集中式的调度系统结构比较适用于节点比较少的情 况。 2 分布式。即在每个节点上建立一个调度控制中心，此调度控制中心只 负责本节点的节目调度控制。这种系统结构的优点是信息的处理量比较小， 调度的周期比较短，可以根据本节点的环境变化灵活的产生、调整调度策略； 缺点是不能实行统的、一致的节目调度控制，很难达到全局最优节目调度 控制。分布式的调度系统结构比较适用于节点比较多的情况。 上述的两种i p t v 节目调度的基本结构，都在实际应用中取得了良好的效 果，但是又都具有一定的局限性。本文将两者结合，为了适应节点很多的情 况，在基于多a g e n t 的i p t v 节目调度系统中设立管理a g e n t ，在整个系统中， 啥尔滨工程大学硕士学位论文 除了管理a g e n t 对于各节点的调度模块有控制权外，各节点的调度模块之间 是平等、自治的关系。这种组织结构是介于完全集中式与分布式之间的一种 结构形式。既可以在一定程度上对系统进行集中控制，又可以发挥节点的自 治性和灵活性。采用混合式的系统结构，较好的克服了两者的缺点。本文的 工作正是基于这种结构展开的。 2 5 本章小结 在这章中，对i p t v 节目调度的背景及相关理论进行了详细的介绍，从 i p t v 节目调度的环境、特点、评价w r y 节目调度系统的性能指标到i p t v 节 目调度的基本原理，都进行了细致的分析。从这一章的论述中可以看出，i p t v 节目调度的特点能够充分体现多a g e n t 技术的优越性，为采用多a g e n t 技术 解决i p t v 节目调度问题奠定了基础一通过本章的介绍，对i p t v 节目调度问 题有了一个总体的认识，这样，对课题的实现也更容易理解。 1 2 哈尔滨工程大学硕士学位论文 第3 章基于多a g e n t 的i p t v 节目调度系统 3 1 系统的体系结构 3 1 1 面向i p t v 节目调度的a g e n t 的特征 由于i p t v 节目调度系统是由一系列具有协调能力的a g e n t 组成的，它们 的每个个体都具有a g e n t 的普遍特性，但同时它们又是比较特别的，因为它 们是适用于商业领域的，基于这个前提，同时为了使a g e n t 具有更好的作用， 假设本系统的a g e n t 还应该具有如下的特征： 1 a g e n t 可以封装和管理一个或多个独立的控制流程，它可以给其它 a g e n t 提供服务，可以对内部和外部的时间做出相应的反映，同时它还可以 进行一些后台管理，例如监控自己的行为、监控外部环境等； 2 在分布式环境中，a g e n t 可以对自己和其它a g e n t 进行区分，并对当 前情况有较为全面的了解； 3 a g e n t 在通常状态下是静态的，但是如果有需要它也可以进行移动， 成为m o b il ea g e n t 以便同其它a g e n t 进行及时通信，同时实现跨平台； 4 a g e n t 具有推理能力，可以根据自己的决策机制和当前的情况做出一 定的推理和决策； 5 a g e n t 之间可以进行协商，可以在一定程度上提供信息和资源共享； 6 a g e n t 都是友好的，它们都期望自己和集体的利益都能够得到保障 3 1 2 系统的体系结构模型 基于上述特征给出基于多a g e n t 的i p t v 节目调度系统的体系结构模型， 如图3 i 所示 系统由统计a g e n t 、策略a g e n t 、调度a g e n t 、管理a g e n t 组成，其中一 个节点对应个调度a g e n t 、一个策略a g e n t 、一个统计a g e n t ，所有节点对 应一个管理a g e n t 。每类a g e n t 都有自己特定的功能，在稍后将会给出详尽 的说明。在此体系结构模型的基础上，可以使得i p t v 节目调度的关系清晰， 哈尔滨工程大学硕士学位论文 结构明确。后面的工作都是基于这个体系结构模型开展的，此体系结构模型 使得i p t v 节目调度的各个层次功能明确，提高了i p t v 节目调度的灵活性， 便于合理的进行i p t v 节目调度，保证整个系统的高效、稳定。本章的余下部 分将用于说明各类型a g e n t 的功能，重点构造策略a g e n t 和管理a g e n t 。 图3 1 基于多a g e n t 的i p t v 节目调度系统的体系结构模型 一个节点上的调度a g e n t 、策略a g e n t 、统计a g e n t 负责处理与本节点节 目调度相关的问题，称之为单节点节目调度模块。i p t v 调度系统由若干个单 节点节目调度模块组成。单节点节目调度模块的结构如图3 2 所示。 图3 2 单节点节目调度模块结构图 1 4 哈尔滨工程大学硕士学位论文 3 2 功能a g e n t 及系统的工作进程 3 2 1 功能a g e n t 1 统计a g e n t 统计a g e n t 负责感知节点所处环境发生的变化，提取环境状态特征等有 关信息，主要是一定时间段内的用户点播请求特征、变化趋势和节点的状态 特征等。 2 策略a g e n t 经统计a g e n t 处理过的信息发送给策略a g e n t ，用于推理决策、形成调 度策略。策略a g e n t 按照功能划分为三部分：策略形成部分、调度协商部分、 策略修正部分。策略形成部分根据统计a g e n t 传送过来的信息生成节目调度 策略；调度协商部分负责处理关联节点间的协商闯题，以及接收管理a g e n t 发送的协商控制指令，并将控制效果反馈给管理a g e n t ；策略修正部分根据 策略执行后的反馈修正策略库中的调度策略，使系统生成的调度策略能自动 的适应环境以便取得最佳的调度效果。策略a g e n t 的结构图如图3 3 所示。 输入名争?输出 一7 图3 3 策略a g e n t 的结构图 3 调度a g e n t 调度a g e n t 根据策略a g e n t 形成的调度策略，执行相应的行为。调度a g e n t 完成了i p t v 节日调度系统中对节目的实际调度功能。 4 管理a g e n t 管理a g e n t 主要负责统观整个调度系统，管理a g e n t 从整体的角度对系 统进行控制，每个节点的策略a g e n t 每隔一定时间向管理a g e n t 发送有关自 身的一些信息，管理a g e n t 根据这些信息以及自身所具有的关于被控节点的 哈尔滨工程大学硕士学位论文 知识，制定相应的控制指令，从而实现对经验知识的有效利用。系统管理员 通过管理a g e n t 的人机界面发送协商控制指令给节点，接收到管理a g e n t 发 送的协商控制指令的节点无条件的执行管理a g e n t 的协商控制指令，并将控 制的效果反馈给管理a g e n t ，以利于管理a g e n t 更新经验知识。管理a g e n t 的结构如图3 4 所示。 图3 4 管理a g e n t 的结构图 3 2 2 系统的工作进程 每个节点上的调度任务由此节点拥有的统计a g e n t 、策略a g e n t 、调度 a g e n t 合作完成。单节点节目调度模块上的每个调度任务的执行是一种具有 反馈的过程，其工作进程如图3 5 所示。 图3 5 调度任务执行的工作进程图 调度任务首先触发一个统计a g e n t 进程，统计a g e n t 根据节点环境信息 进行统计，统计出用户需求的特征，变化趋势、节点的状态特征等；然后触 1 6 哈尔滨工程大学硕士学位论文 发一个策略a g e n t 进程，策略a g e n t 根据统计结果制定出最适合在此节点上 执行的调度策略；最后触发一个调度a g e n t 进程。调度a g e n t 负责执行策略 a g e n t 产生的调度策略。执行调度策略后，本调度任务执行结束，节点环境 发生了变化。新的调度任务触发新的统计a g e n t 进程、策略a g e n t 进程、调 度a g e n t 进程，进行新一轮的调度。 3 3 基于记忆演化的多a g e n t 系统强化学习 i p t v 节目调度问题具有动态时变性，所以对于作为系统基本单元的单节 点节目调度模块来说，它必须能够进行适用于动态环境的学习，即当节点环 境发生变化时，单节点节目调度模块能够调整调度策略，使产生的调度策略 在新环境下最优。单节点节目调度模块能够实时的、动态的、自主的感知并 作用于不断变化着的外部环境，为了实现这种动态实时的学习，在本文中采 用了基于记忆演化的强化学习方法 3 3 1 强化学习方法 强化学习( r e i n f o r c e m e n tl e a r n i n g ) ”“1 是来源于生物学中的条件反射 理论，其基本思想是以环境提供的加强信号作为性能评价的反馈，完成从状 态到行为的映射的学习。学习者并不被告知应采取的正确行为，而是通过试 探寻找可以产生最大回报的行为在许多情况下，采取的行为不仅影响立即 回报，而且影响对以后状态的回报。试验一失败搜索及延迟的回报是强化学 习的两个重要特征。 标准的a g e n t 强化学习框架结构如图3 6 所示。a g e n t 由状态感知器i 、 学习器l 、动作选择器p 三个模块组成。状态感知器i 把环境状态s 映射成 a g e n t 内部感知i ；动作选择器p 根据当前策略选择动作a 作用于环境霄：学 习器l 根据环境状态的奖赏值r 以及内部感知i ，更新a g e n t 的策略知识；w 在动作a 的作用下将导致环境状态的变迁s 。强化学习技术的基本原理是： 如果a g e n t 的某个动作导致环境正的奖赏( 强化信号) ，那么a g e n t 以后产生 这个动作的趋势便会加强：反之a g e n t 产生这个动作的趋势减弱。 1 7 哈尔滨工程大学硕士学位论文 图3 6 强化学习的框架结构图 在强化学习中，涉及两个比较难解决的问题w ：其一是时间信誉度 ( t e m p o r a lc r e d i t ) 分配问题，假定一个学习a g e n t 完成一系列的行为并得 到了一定的输出结果，这就要求学习系统应能很快决定如何为每个( 状态， 行为) 对分配奖励或惩罚，以便调整决策，提高性能：其二是结构化信誉度 ( s t r u c t u r a lc r e d i t ) 分配问题，当问题空间太大不能完全搜索时，a g e n t 应该能够根据相似状态下的经验对新状态进行猜测。 强化学习实际上并不是一种算法，它只是对一类问题的描述，这类问题 基本概括起来就是：a g e n t 如何将内在状态映射到行为，并获得回报最大化， 并且这种映射不是事先获得的，而是a g e n t 根据尝试及回报，通过学习建立 的。任何能够解决这类问题的算法都可以称为强化学习算法。 强化学习在动态调度领域已经有了广泛的应用，如：文献 1 9 - 2 2 将强化 学习应用到了生产调度中的车间作业调度问题，文献 2 3 2 5 应用强化学习研 究了电梯群的调度问题。但目前其成功应用的领域还只限于简单系统，在复 杂系统中，由于无法为整个系统制定统一的学习策略，因此，强化学习往往 无法发挥明显的作用。解决这一问题的根本途径只能是将复杂问题分解，利 用强化学习基于目标驱动，直接与环境交互的特点，对分解后的问题实施强 化学习，并通过分解问题的主动交互，实现整个复杂问题的强化学习。这也 是多a g e n t 系统与强化学习结合的根本原因。 通过试验一失败搜索方法，利用不确定的环境奖赏值来发现最优行为策 略是强化学习的主要特征和难点。对于i f i t 节目调度问题来说，用户的需求 信息是大量的，用户的需求特征是多样性的、动态变化的、不确定的、有时 候甚至存在比较诡异的变化，所以，通过试验一失败搜索，单纯依靠环境的 1 8 哈尔滨工程大学硕士学位论文 奖赏值来调节策略的选择和修改，要花费较长的时间，并且很难达到理想的 效果。在本文的设计中，通过记忆演化模型来对大量的需求信息进行过滤、 分类等加工处理，以此来减少得到最优调度策略所需要花费的时间，提高学 习的效率。 3 3 2 记忆演化模型 记忆是认知科学中非常重要的问题之一人通过各种感知器官从外界获 得信息，再在记忆中存储下来，使得知识积累下来并在以后得以应用。记忆 机制的存在使得人类得到了学习的可能。研究记忆机制的演化，成为研究机 器学习的条有益的道路。 在认知心理学领域，科学家们通过一系列试验，根据记忆过程中信息保 持的时间长短不同，将记忆分成瞬时记忆( s e n s o r yi n f o r m a t i o nm e m o r y ) 、 短期记忆( s h o r t - t e r mm e m o r y ) 和长期记忆( l o n g - t e r