已阅读5页,还剩51页未读, 继续免费阅读
(运筹学与控制论专业论文)视频点播系统中的优化模型研究与计算.pdf.pdf 免费下载
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
大连瑾工大掌嫒士学位论文 摘要 褪颧点播系统缝毽静圭鬻是多媒体数据,褥多媒体数磊遴零占舔磁盘空闽大、传输 带宽高,j ? i i 且处理肘占用的处理器资源较大。在大型的视频点播系统中,由于无法统 分配和管纛黼络带宽需求的笼限往藏网络带宽的有限往,容翁造成突发往网络拥塞和数 摄轰失,并发服务用户的数目不是缎多,很难满足明户购需求,为了从本质上解决这些 问艨,有效地降低肯干网络带宽消耗以及对现有带宽资源的充分利用成为视频点播系统 盼焦点闯憨,也是迫切霾要解决豹麓遂。铮澍这个瓣题,本文,建立了三令捷键模型, 得到了一个线性规划问题、个多目标规划问题和个非线性规划问题。分别讨论了解 蠡孽雾在蛙。赞霹多瓣掭怒翅阉瑟绘穗7 令然筏算法,铮列 线经矮鲻模委l 缭密7 令 贪婪算法。得到了带宽资源分配的最优方案,在某种程度上,从数学角度降低了骨干网 络辩宽豹游耗,实鬻了薅瑗有带宽资源辨充分秘用。 本文取得的主骥结果可概括如下: 第二章中,在纂于代理的视频点播系统中,以骨干两络带宽的消耗为目标函数,l ;l 代理的存储空间为主要约束条件,建立了一令优化模型,得到了一个线烃趣划翊题。讨 论了解的存在性及熊性质,给出模测的具体解法,用算例说明了模型的有效投。 第三露中,在蔟手找理熬援频患疆系统孛,菇了使瑗有带宽姿滚褥到宠分_ 摹l 弱,零 章,建立了个优化模型,得到了一个多且榜;规划问题。讨论了解的存在性,并且针对 该| 蓬透给& 了一个邀铽算滚,焉算翻说羁7 横鍪静蠢效健。 第四章中,在蒸于代理的视频点搔系统巾结合补丁策略,以骨于网络带宽的消耗为 霹标函数,黻代理的存储空间瓯及补丁( p a t c h i n g ) 窗口为主要约束条件,建立了一个 优化模型,褥到了一个非线性规划间题,讨论了解的存在性,针对该阉题绘臻了一个爨 婪簿法,用算例说明了模型的有效性。 关键蠲:褪频点瓣;代理;线性溉期; 线性撬翘;多曩拣艇潮 塑塑皇堡墨堑童墼垡! 燮! ! 堡鍪兰茎整 t h er e s e a r c ha n dc a l c u l a t i o no f o p t i m i z a t i o n m o d e l i nv o d s y s t e m f h ev o d s y s t e mh a n d l e sm a i n l ym u l t i m e d i ad a t a , w h i l et h em u l t i m e d i a 蠡t au s u a l l y n e e d sm u c hm o r ed i s ks p a c ea n db a n d w i d t h i nl a r g ev o d s y s t e m ,i t sn o te a s y t om a n a g e e f f i c i e n t l yn e t w o r kb a n d w i d t h s o , i t c a n h a r d l ys a t i s f yt h en e e do f t h e c u s t o m e r s f o rt h es a k e o f r e s o l v i n g t h e s e p r o b l e m s ,r e d u c i n g t h eb a c k b o n en e t w o r kb a n d w i d t h c o n s u m p t i o n b e c o m e s t h e f o c u s p r o b l e m o f v o d s y s t e m 。i n o r d e r t o s o l v e t h i s p r o b l e m ,w e b u i l d u p t h r e e m a t h e m a t i c a lm o d e l sa n dg e tal i n e a rp r o g r a m m i n g p r o b l e m ,am u l t i - o b j e c t i v ep r o g 黼t m n i n g p r o b l e m a n dan o n - l i n e a rp r o g r a m m i n g p r o b l e m f u r t h e r m o r e ,w e s h o wai t e r a t i v ea l g o r i t h mt o s o l v et h e m u l t i - o b j e c t i v ep r o g r a m m i n gp r o b l e m 。a n dw e s h o wa g r e e d ya l g o r i t h r a t os o l v et h e n o n * l i n e a r p r o g r a m m i n gp r o b l e m t h em a i nr e s u l t so b t a i n e di nt h i sd i s s e r t a t i o n m a y b es u m m a r i z e da sf o l l o w s : i n c h a p t e r2 i np r o x y - b a s e d v o d s y s t e m ,w e b u i l d u p am a t h e m a t i c a lm o d e l a n d g e t a l i n e a rp r o g r a m m i n g p r o b l e m a n d t h e o b j e c t i v e f u n c t i o ni st h eb a c k b o n en e t w o r kb a n d w i d t h c o n s u m p t i o na n d t h em a i nc o n s t r a i n tc o n d i t i o ni st h e p r o x yc a c h i n gs p a c e f i n a l l y ,w cs h o w m e t h o d st os o l v et h i s p r o b l e m , i n c h a p t e r3 , i np r o x y - b a s e dv o ds y s t e m ,w e b u n d u p am a t h e m a t i c a lm o d e la n d g e t a m u i t i - o b j e c t i v ep r o g r a m m i n gp r o b l e m f i n a l l y ,w es h o w ai t e r a t i v ea l g o r i t h mt os o l v et h i s p r o b l e m 。 i i lc h a p t e r 4 , i np r o x y - b a s e dv o d s y s t e m w i t h p a t c h i n gs t r a t e g y w eb u i l du p a m a t h e m a t i c a lm o d e la n d g e t an o n - l i n e a r p r o g r a m m i n gp r o b l e m a n dt h eo b j e c t i v ef u n c t i o ni s t h eb a c k b o n en e t w o r kb a n d w i d m c o n s u m p t i o n a n dt h em a i nc o n s t r a i n tc o n d i t i o ni st h e p r o x y c a c h i n gs p a c ea n dp a t c h i n gw i n d o w f i n a l l y , w es h o w a g r e e d ya l g o r i t h mt os o l v et h i sp r o b l e m k e y w o r d s :v i d e oo n d e m a n d ;p r o x y : p r o g r a m i n g :m u i f i o b j e c t i v ep r o g r a m m i n g n 独宅争陡说明 佟嚣帮重声骥:零琰攀往论文楚我个太盔静舞掺譬下进行鹣磷究 工作及敬褥研究成果。尽我所知,除了文中特别加以檬液和致谢的地方 矫,论文申不包含其他入已经发表溅撰写的研究成梁,谯不镪含为获褥 大连溪王大学藏英穗零链懿学懿或谨书襞蠖麓_ 避麓棰瓣。与我一鬻羔雩譬 黪瓣恚对本磷巍嚣徽豹更簸甥邑程谂交巾激了睡礴麴落臻并表忝了瀚 懑。 作者签名:麦壶:晕 日期:迹曼i 日丝望 大连理t 大学硬学佼论文 l 绪论 奉章烹婆穷缨了旎攘轰疆系统懿遗容窝发震,撰窭了囊 l 蓼援频点播系统撼甥嚣要瓣 决的问题:降低骨干网络带宽的消耗和对现有带宽资源的充分利用。 1 1 视频点播系统 1 1 1 视频点播系统简介 视频点播( v i d e o - o n - d e m a n d ) 【4 ,5 ,5 ,7 】是指用户可以在任何时间从服务器上获 取铿谚多媒体数据裂客户援放戆一耱瘦弱。它是当藏多媒搏遽嘏应翅瓣一矮藩浍技本, 是砸向未来的信息、通讯等相关技术相结台的新技术。同时它又是一项业务,泛指利用 交蓬式网臻将声音瀚像遴嚣实霹传徐,戳实现蘑户霹羧交互憨访翊逶臻l 琵务器所存储麓 丰富节目。视频点播( v i d e o - o n - d e m a n d ) 熟随着计算机网络技术、存储技术、多媒体 援沭能发鼹褥出现盼新的裰频应角澎式。在褫频点播系统中,厢户通过网络陶视频服务 器请求需要播放的带耳,视频服务器在用户w 以接受的时间内,在指定的接收设各上攒 放用户要求的视频带爵,并在播放的过程中响应顾客的交互请求。 近年来,随羲薅速诗算规网络、数字视频压缩戳及太容繁存姥嚣豹快速发震,援 频点播( v i d e o - o n - d e m a n d ) 服务成为现实,这使得我们能够快速、猴确、方便地从视 壤羹务器上获褥我懿嚣要静嵇惑。宅走洚蘩慧需求豢疰任餐辩瓣选择掰需靛僚怠,可广 泛成用于电影点播、远程教育、信憋点播、选程医疗等领域。 视颓熹播系统簸疆的主簧是多媒体数掇,丽多蕊体数据迸常占焉磁盘空阊大、传输 带宽高。丽且处理时占用的处理器资源较大。尽管嚼络带宽瓤视频服务器的到o 带宽、 处理能力都在不断键高,| ;蠹着视频服务应丽的不断普及,甩户数日币断的提商,系统资 源鹪提高仍然无法满足实繇应用的霭求,过多的用户数丑经常会造或服务器影o 荣宽戴 网络带宽的瓶颈( 戚称为系统传输信道的瓶颈) 。i 厦年来在备地进行的很多交互式f 包视 泵缓试骏中去# 存在羲这群戆趣题,扶缀大稚发上疆礴了援凝焱耱( v i d e o - o n - d e m a n d ) 服务的普及。 援菝纛疆蕊缓孛豹捷纯模墨l 鹾究与计棼 1 1 2 视频点播系统原理 视频点播主要由视频服务器、高速传输网络和客户端组成。服务器响应用户的点播 请求,将节瓣数蕹懿税频流豹方式遴遗高速蒋输潮络麓送到霜户端。 图1 1 1 揽频点播系统结构 图1 1 1 驻示了一个典型的视频点播系统缩构。用户为了点播节目荫先向视频服务 器发斑个意播请求,视频月醛务器收蚕g 精户的请求后,其中的调度器就根据特定的调度 方案决定何l l 寸在哪一个信道上传输所鬻的视频流,并将这一个馈道回传绘用户端。出予 多媒体数据的实时性,为了保证用户端的连续播放,视频服务器必须为视频流保留足够 的网络带宽翱服务器封珏带宽,嚣显在应答题户谤求i l 箨必须提爨翡裂端熬严揍鹑l 瑟努囊 量( q o s ) 服务器按调度器指定的j 预序从视频存储器中取出数据并以视频流的形式通 过黉徐痿遂发送至| j 雳户壤援产臻禳撵鼹疆务器绩数鬻拳控肇l 信惠获一个或多个将定静 信道上接收视频流数据,并进行缓存戏直接解码播放。通常情况下,一个用户在接收视 频数镶褥必须先离筏籁服务器发出请求。视频数锯的传输可黻通过荤点播送( u n i c a s t ) 或多点播送( m u l t i c a s c ) f 3 】完成在一个雄点播送连接中,服务器及网络为每个用户分配 一2 叁! 墼墨兰查篓堡主堂堡逵生 一令独立弱浚颧滚黎暹;恧程一令提供多惫攒送黢务懿瘸终中,骚务器霹数只遵过一个 信通将视频数据传输给多个阁户端。 1 1 3 视频点播系统研究方向综述 一个设计良好的视频点播系统必须能够容纳更多的节目,服务于更多的用户,同时 还婺傈持系统造侩的低廉。会建稍丽系统资游、设计麓篷价魄的系统寒满是不断增长的 用户需求是视频点播系统需溪解决的霪点问题。围绕这一中心问题,从多个方飚对视频 点播系统进行研究,目前主簧的研究方向c 2 3 】有: 1 节耳襻储系统设计 为了同时对尽可能多的用户服务,视频服务器的存储系统必须能够提供很高的f o 带宽。出予谨媸i 0 豢蠢受嫒 孛条 孛豹蔽铡,握毫存 凌系统豹器蛙戆力主要篡审在如秘 充分利用现有的存储硬件的l l o 上,麒目标戗括低延迟、灵活的交互能、大容凝的并发 薅户数、抵侩链、耪: 实袭等。磷究翡褥蘧檠串馋瑶程: 磁盘调度策略:由于连续媒体的实时性要求,传统的算法不能逝接应用到视频服 务器上,褫频服务器的磁盘调度算法应该在僳证每个数据流盼实时往的基础上,提高系 统的吞吐爨。 国数据放置策略:视频服务器在存储和访问视频文件时,需要通过减少磁头的寻邋 对耀窝响应辩闯,援糍磁蠢鹣豢宽剩翔率,壤龆单缒对阗豹蚕蛙量,这可瑷透避改善数 据的放置策略实现。 瑟次存簇蒙酶:霹予犬螫兹援簇羧务器系统,凳全采燃器蠹靛磁盘终受存稳究瑷 是不合理的,由于人们对节目的点播分布差辨很大,即大部分用户的点播请求集中在少 数豹热门节鬻上,这群入们弓l 速了绥次存储策略,将热门节嚣存诺程高速的磁盘上, 而姆其它节目存放穰低速的外存储设备上。那么如何确定热f 1 冷门节翻,如僻姆节目农 外存储设备和磁盘问换入换出就成为新的研究课题。 缓存管理和浚调度:为了使月骚务器在保持为用户提供连续视频滚粒嗣对,壤至g 捌 更麓的响应时间为慰多的用户服务,视频服务器必须充分茅用i o 带岚。设计精巧的的 3 篓篓塞堡蒌鎏皇箜i 燮型篓塞兰堡篓一。 存管理算法爵潋有簸魄实瑷多个弼户共享一个褫叛滚占溺懿i , o 带宽,述冒戳、溃除磁盘 访问即调度过程中造成的数据传输率抖动等问题;而流调度策略则通过调度各个数据流 的服务顺序,降低用户请求静初始延时,提商弗发服务的用户数目。 2 。传输信道的调度【1 8 】 在视频点播系统中,服务器将用户请求的节目以视频流的:疗式通遵高速网络传输到 用户遐,为了保证节避瓣黄竣震量,缀务器鬟罄为视频淀分配怒够戆暇务器及蟋络繁 宽。传输一个视频流所需的服务器及网络资源为一个信道。由于系统的信道数肖限,而 盈筏簇漉占蠲懿露宽缀离,戮茂售遂瓣骞效蠢鬻在筏颓焘撵系统中莛着十分重瑟懿作 用。 传统静撬频点播系统中,耱务器为每个用户分配一个独立的信道,这样用户数目的 增加将容易造成系统资源的耗尽。为此,人们提出了许多额的露效的傣道调度方案。当 前使用的视频点播系统中比较常用的髂道调度方案主要有两类: 囝单播方察。 服务器为每个用户分配一个独立的信道,这种方案的可伸缩性很差,很容易造成服 务嚣1 o 嫠宽凌网络辫宽戆糕颈。 国轮播或广播策略。 暇务器誉管是否宥稿产清求,将麓鹜在一个或多伞信道上薰复广播,显然,此时用 户为了从头器个节日,需要等待较长的一段时间。为了减少等待时间,需要农更多的 信道上广播,这样就存在信道数目和用户等待时间的矛盾问题。如果能利用网络组播技 术,让多个用户共享一条视频滚,将会大大提搿服务器及网络疑源救剽煺率。毖妇,若 一个用户在9 :o o 点播了一部节目,蜀个用户在9 ;0 5 点播了同一个节日,一种简单 可行瓣方法是熬一令嬲户等黪5 分镑,然嚣与瓣一个臻户共享一含褪菝漉,这榉蒙霹数 节省一个信道的资源了。而对于热门节目可以按定策路进行分块,并将各个分块在不 囊售遵上重复广撵,鼓蔼,障鬣了臻户等待薅瓣和系统信道数。这类新鸯孽方案通过多播 技术实现信道拱享,使得服务器在一个信道可以为多个并发用户请求提供服务,其主要 优点趋可伸缩性婷,穰掘用户和服务器行为的不问,可以分为用户初始化方案( c i i e n t , i n i t i a t e ds c h e m e ) 和服务器初始化方案( s e r v e r - i n i t i a t e d s c h e m e ) 。其中用户:幻贻亿方案 一4 炎逐理蔓丈擎蘸士攀经论交 又霹渡势舞虢酒黢方嶷( b a t c b i n g s c h e m 。) 攀,霹耩蛰t 穷桊( p a t c h i n g s c h e m e ) 冷* 1 0 ,i i 。1 4 ,1 6 1 而服务器初始化方察可分为非预取戚方案( n o n - p e r f e c t i n g s c h e m e ) 和 颡鼗式臻裘( p e f f 撼gs c h e m e ) 。t 嚣谱缝奔绥戮潺蠹袁黎鼗李 丁方寨。 批调艘方案的基本慰想是通避延迟对先魏用户请求的服务,实现搓一个储邋上g 陵努 鬻多瓣麓产,一次簸务豹掰蠢蘑户髂舞个“撵”( b a t c h ) ,穗舔抵之闻鞠褥黼称麓 蹴缝理时麟润疆( b a t c h t l , n e ) ,掰跌逶澈撬菇熬怂毽嚣瓣麟疑索 袋避愿产懿黢务瓣 辩+ 菝蔼,藩;现程一个稿港上服努麓多韵稻声。 魏整理繁臻缀交黻上藏多了瓣黢势瓣绥遂翡黉求,爨遮楚嚣进臻麓鬻产浆警愁辩 附俸为代价的。黼在 p 了力窳中,用户向服务器靛出点播请求后,酗上得到响成。儆分 辩鳃焉产馥蘩逶瑟黢苓楚鞭鼗懿,籍户一般鬻要鼓蹲令袭酒令疆土鼹蘩遂羔彀鼗黎。冀 旗本思想撼用户除了从分既绘他的倍道上接收数攒扑,还w 以同时从蜀一个健输同一个 褪躜漆靛楼滋主羧嫒鼗援,霞魏器骚麓产穗铗蕊话予疆菔遮率瓣i o 鬻竟蕊歉磐要鹣缕 菇。以下夯绍与睾 丁骞案嚣焚浆,b 个搬念。 魂, l l l a r 漉您楚毯禽憋夸帮鞲离容稳滗整翡媒体瀛,菸嚣程瓣凳裔鹅黼淹节褥播 救筑宠螫瓣翔。獭菜令漆爨第次棱熹撩霹,蓉凌嚣要麓这令碧瓣建交一令r e g u l a r 流。传送r e g u l a r 流的信邋为芷常倍游。 p a t c h i n g 流是毽鸯蒂莛开始鼯努熬个片断瓣媒钵滤;冀黛露攥鬟荧 ,一t ,。 茂中,f 。为当前的调度时悯,t ,为节目的r e g u l a r 流建立的时蛔。传邀p a t c h i n g 流的供 遂势章 丁馈遴。 斑敏妇抽噻窑鼯鬻繁鼷豹r e j a r 滚逡宠乏器,篝猫懿掰p a t c t 濑g 滚爱褥髑产演袋 合并舞i 巍商酶r e g u l a r 滤耐宠整播放节蠢的时阔范瞄。 鼹予个蕊瓣翡溃零,最要当葵每超道p a t c h i n g 褰器乏魏竣谣壤,孝裴犍瓣 p a t c h i n g 流避行服务戳合并使用r e g u l a r 流的数据。当超过了p a t c h i n g 窗口,就必须聪 建立个r e g u l a r 溢考爱瀵怒装求。 3 交豆斌控制 夸变曩式懿援鞭熹疆黎绫兔许溪户遥遵v c r ( v i d e oc a s s e t t er e c o r d e r ) 戴鹣炎嚣 控制( 鲫鬻髂、想辩、抉避、快邋警) 与瓣务器避嚣交互撵趣。交鬣还袭现筠避嚣壤逸 - s - 壤凝点攒篆统孛豹线纯摸型磷究与计冀 择广卷、套番耨藩懿纛详缨瓷麓、裸襻或注筏蘩一警鬣、溆菱、选器著魏妥物菇等。其 中,暂停和继续是最熟本的操作,实现起来不太困难。对于信道独立的用户,暂停和继 续只需要简单的通知服务器邵,而快迸和俊邋可以避避传输荧键帧的方式实蕊,僮可 能需要占用较多的服务器c p u 处理时阃或网终带宽。褥对于煎颟提到的采用新的调度 策略的系统,用户的信倒是不独立,程这种情况下用户无法独立遗、实时地控制视频。 当一个交互撩作发生射,翅户不褥不离开当蘸螅共享视频滚丽老寻找另一个视频滚,这 样就给系统的设计增加了难度。 4 。系绞薅系绩援 系统设诗鳃主袋毯耩是麓效遗攥瓣骚务器窖量、提亵黢务 器i o 带宽以及提高阚络带宽的利用率。而綦于代理的视频点播( v o d ) 系统除了需璎 瓣凌渡主嗣邃羚,:j 纛震要重燕簿决戳下见令 瓣题; 如何组织代联服务器? 即系统结构问磁。系统结构直接影响着系统的性能水平和 效率。代理菔务器的系统结褥主要鸯3 类:分层式代瑾服务器,分布妓代理臌务器及混 合式代理服务器。衣分层式系统中,代理服务器按照簿级分威不同豹屡次,用户请求的 是最底层的代理服务器,当没有命中时,请求逐层上传,直到和i ) 服务器i 分布式系统 中,多个 弋耀眼务器闼可以使羼菜静羚议进弦通信;褥混合式 弋理i 骚务器结会了分层式 系统和分布斌系统。 翅露缓存节嚣数据? 箨缓存( c a c h i n g ) 綮臻阏趱。找瑗骧务器浚诗匏一个重要 目标是提高用户的点击命中率,而由于视频节目需露占用很大的网络带宽和服务器姻 蒂宽,褪颥煮疆系绫的代瑶目鼗务器不仅需要掇高焉产静请求禽中率,述必须寄效嚣节餐 网络带宽和服务器带宽,因此设计出优秀的c a c h i n g 策略是纂予代理的视频点播系统的 一个根本随趱。 国代理服务器与中心服务嚣采用什么方式进行系统信道传输鲍分醚歉调度? 各令视 频服务器问采用什么方式进行通讯? 如何优化各个视频服务器问的负载平衡? 系统的功 能怎么分配魄较会遐? 采用卡 么撵豹体系结椽毙较台理? 翔您避嚣栏麓浮餐等等。这数 问题的不同解决方案对整个系统性能的影响十分关键,采用优秀的调度策略( 算法) , 整令系统豹效率藏熊箍著挺褰,蠢就澍这些| 、藤送懿骚究缀毒实际意义。 5 系统实现 7 。 援叛点媾系统中盼搬纯模型瞬楚与诗冀 当蔻,穗经有了缀多不戮类型靛援频点攫系统。麸鞋软转必圭瀚麓擎援菝滚应建 到以专用硬件平台或超级计算机的大型视频服务器。实现系统鬻要根据具体的威用需 求、簸模、平台等等来解决缀多实际的闼题, 如: 国服务器及用户间的有效的信令健输,服务器需要发送控制消息响应用户的请求, 告诉掰户它将何时在明5 一信道上传输用户所需的何种格式的视频数据。由于需要对这些 消息避荦亍缡码,爨此露必要对控制消息的设计傺系统的磅究。 国许可按制策略:主要解决服务器的综合资源分配问题,为保证先前服务的用户的 摄务矮霪,鼹务器惹樊根据当藤豹瑕努猿况与系统套羹决定是秀接受瑟戆蕊户揍求,热 何建立和实现一个有效的能直接反映当前资源状况的优化模型熙十分必舞的。 l 琵务予苓同酝羹靛耀产:一个槎频点接系统需要服务予文燕豹具有不嗣辊顼鑫存 储容凝或网络技术的拥护,适应这些不同配置的用户终端十分必要。 囝辩动、丢失和失序包:在p 随上实现时,p 阚瓣尽全力型服务( b e s t - - e f f o r t ) 涉 及到抖动、丢失和失序包的问题。 囝另外服务器可熊还需要对系统进行必要的管理如数据加密、用户牧限管珊、计费 管理、节目滚弦度统计等。 在实现上还需裂实现服务器缓存的有效管理、音视频数据的同步、媒体流速率控 裁、髂薅等麓题。 综上所述,我们可以得出这样的结论:充分利用服务器和网络资源为尽可能多的用 户提供离震蠹、多功耱静褫蒙瘾撵( v o d ) 自陵务是v o d 系统研究永恒不变的主题。在 未来的研究中,分布式v o d 系统信道调度方案和分布式v o d 系统实现姆是两个艟褥深 入的谍题。 本文主要从分布式v o d 系统信道调发方案角度出发,降低了嚣于网络劳宽懿澧 耗,间时使得网络带竟资源得以充分利用。 线性规划【2 6 】是运筹学的蘑要分支,它是一门实用憔很强的应用数学学科。这门学 科产生于2 0 数纪3 0 年代。1 9 3 9 年,瓣苏联数学家痰援漆维毒在生产缀织与疆+ 矧中 8 * 大连理工犬学硕士学像论文 懿数学方法一书孛,最早提出窝觋建了线接勰划阉麓。1 9 4 7 年,美毽数学容丹泽接 ( g b d a n t z i g ) 提出了一般的线性规划优化檬型和求解线性规划问题的通用方法一单 纯形法,麓这 j 擎摹萼奠定了慧魑。戴屠3 0 年谯线性勰划豹理论秘算法逐步丰赛发浸。 1 9 7 9 年,前苏联数学家哈奇扬提出避用求解线性不等式组的椭球法去求解线性规划问 题,劳迂骥该箕法是个多域式时矧箕法。这一工佟嶷有重蘩数理论懑义,毽实用效累 不饿。1 9 8 4 年,在燕国工作的印度数学家卡玛卡( n + k a r m a r k a r ) 提出了求解线性规划 螅投影尺度法,这是个有实愿意义豹多项式时闻冀法。这一工终等l 怒入嚣j 对滤焘算法 的燕注,此后相继出现了多种更为简便实用的内点算法。随着计算机技术的发展和普 及,线性规划豹应髑越来越广泛。它已成为人们为会霹繇g 用窝限资源巷定最佳决策斡蠢 力工其。 非线性溉划1 2 4 是计算数学和运筹学交叉的学科。它在工程、国防、经济簿许多熏 要领域有着广泛的应用。近二十年来,非线投规划一赢是一个十分活跃的研究领域。 非线性蕊娜从七十年代越就是数学规划中最受重褫的分支之一。特剐是变尺度算法 的* 起使国际涌现出来如p o w e l l 、f l e t c h e r 、d e n n i s 、等一批蒜名的非线性规划专家。避 年米,求解大规模j # 线经规翔的s q l 方法的成功应用,使得j 线性规划计算方法成为 大规模科研与工程计算的一个重要方向。八十年代初期兴起的信赖域法已是非线性舰划 的一个十分热门的研究课透,它进一步促进了非线健黼划的研究与应丽。 我国关予非线性规划的研究起始于1 9 7 0 年。当时,出华罗庚教授领导的c p 国科学 院数学研究衡运筹研究塞j c 幸优化方法避行研究、应用帮推广。尔后,必方、橇湘云、席 少艨、郑权簿教授对j 线性规划进杼了大量的科研。目前我们已有一犬批从事非线性规 鬈l 研究静专渡久员。在应用方蟊,疆牮罗庚教授推广优选法之后,钱令希、张可村、餍 济等教授又做了与多工作,融取得不少优秀的成果。 1 4 茹目标规划发展及其应用 多目标规划研究 2 7 1 多t - - 个的数值目标函数在给定的约柬条件下的最优化问题。 自予放定懑义上说,实际瓣最往豫海遂一般鄂是含眷多个蟊际的,闵诧多茚际痍鲻的 一9 - 攫塑塞堡墨笙皇鳖垫些堡型壁塞兰茎燕 , 一一 理论嚣l 方法焱现代经济藕享圭会发震中矮有十分广阔静藤雳范畴,它是避行经济、辩技、 军事和文化中重大科学决策和规划的肖力工具。 多目标规翊的两个主要起源是:在经济学中f y - e d g e w o r t h ( 1 8 7 4 年) 和g c a n t o r ( 1 8 9 5 年) 翻e h a u s d o r f f ( 1 9 0 6 年) 的有序空闽理论的建立。在5 0 年代,h w 。k u h n 和a w t u c k e r ( 1 9 5 1 年) 有关向量搬值理论的研究,g d e b r e u ( 1 9 5 4 年) 结含评价均 德方援豹工佟以及l h u r w i c z ( 1 9 5 8 年) 把溺题推意撼象空鲻麴尝试,必这学辩熬形 成作了重要的前期准备。直至7 0 年代和8 0 年代经过众多学者的努力,终于建立起来多 基椽筑慈| 蠢孽蘩零理论鏊礁,使宅成为寝矮数学瓣一令耱鹣学秘分支。 因为多于一个的数值目标可以表示为一个向量目标,所以多目标规划问题也称向量 稷德晒题。与哭含鸯一个数德嚣标溺数翡单鹜标数学辩娜闻麓不弱,辩子一个始定的多 目标规划问蹶,同时使其中备个目标蛹数都达至u 最优的最优解般是不存在的。因此, 在多目标规划的研究中,通常是考虑使它的向鳖目标脯数在某种意义下为非劣的所谓有 效麟,多刚零靓划理论主要磷究它关于务魏意义下豹露效解豹壤论。 1 5 零沦文的生要王l 睾 视频点援系绞处遴的主娶是多媒然数据,疆多媒体数据逶霉占臻磁盘窆秘大、建竣 带宽高,而凰处理时占用的处理器资源较大。在大型的视频点播系统中,由于无法统一 分嚣秘管理翳络带竟褥求豹燹羧牲及瓣络带窕鹣有限魏,容荔造成突发毪鼹络糖塞襄数 据丢失,并发服务用户的数目不是很多,很难满足用户的需求,为了从本质上解决这些 阕题,有效穗降低雷干两络带宽消耗戳及对现有带宽资源的充分利蕊成为视频点播系统 的焦点问题,也是迫切需要解决的问题。钟对这个阅联,本文,建立了三个优化模型, 得到了一个线性规划问题、一个多目标规划问题和一个菲线性规划问题。分别讨论了解 的存拦挫。铮对多基橡嫂划阏题给出了一个迭代算法,铮对棼线性援越摸壅绘囊了一个 贪婪算法。得到了带宽资源分配的最优方案,在某种稷度上,从数学角度降低了骨干网 络豢宽熬漤旋,实瑰t 对黟毒黪窕姿溅豹充努铡矮; 本文取得的主要结果可概括如下: 一l o 大连理l :人学硕士学位论文 第二章中,在基于代理的视频点播系统中,以骨干网络带宽的消耗为目标函数,以 代理的存储空间为主要约束条件,建立了一个优化模型得到了一个线性规划问题。讨 论了解的存在性及其性质,给出模型的具体解法,用算例说明了模型的有效性。 第三章中,在基于代理的视频点播系统中,为了使现有带宽资源得到充分利用,本 章,建立了一个优化模型,得到了一个多目标规划问题。讨论了解的存在性,并且针对 该问题给出了一个迭代算法,用算例说明了模型的有效性。 第四章中,在基于代理的视频点播系统中结合补丁策略,以骨干网络带宽的消耗为 目标函数,以代理的存储空间以及补丁( p a t c h i n g ) 窗口为主要约束条件,建立了一个 优化模型,得到了一个非线性规划问题。讨论了解的存在性,针对该问题给出了一个贪 婪算法,用算例说明了模型的有效性。 蹩皇堡墨鉴皇塑垡垡篓墅鏊兰茎塞 一 2 线性规翔模型 2 l 垂缓 瓣藩鬣颓点接( v i d e o - o n - d e m e n d ) 系凌懿难题是:在最大瀵是嚣l 声戆震求秘僳囊 通讯服务质量的同时如何充分利用网络资源。在大型的r o d 系统中,由于无法统一分配 和管避阚络鬻宽需求鹃无限佼激瓣络辩宽靛育黻往,入髑将c a c h i n g 豹蕙惩葶l 入r o d 系 统的设计,建立了基予代理服务器的视频点播系统,这群就可以将负载分布到附络上的 多个代理服务器上。代理服务器的设计必须有效的节省阏络的带宽和服务器带宽,因 此设计出优秀魏c a c h i n g 策略是解决代理服务器豹一个根本阔题。本章潋营干网络带宽 的消耗为目标函数,以代理存储空间为约束条件,建立了一个优化模型,得到了个线 蛙鬏鲻问题。淫论了熊戆存在蝰及其瞧覆,绘逝了强转特殊糖熬下麴线性掇剡鞠蘧,翔 算例说明了模型的有效性,飨出模型的具体解法,在浆种程度上解决了这个问蹶。 2 2 建立模型 2 2 1 假设前提 在s e r v e r - p r o x y - u s e r 框架基础之上,优化网络带宽的消耗。s e r v e r - p r o x y - u s e r 框繁簧求l 琵务器和蔫户之趣不麓壹搂联系,登须褥逶遥代理( p r o x y ) : 服务器不会搬绝服务,即服务器对用户的申请准入: 用户不会违约,& p 顾豁在允诲的播放盼延内不客中途邋出; 服务器向代理传送媒体数据的速度是等同的: 传输模式可靠,组播w 以得到; 不考虑网络拱动匏影豌。 2 ,2 2 褥号磐器 1 2 火逶理l :夫学疆士学穗论文 t 鞭努嚣逸代毽鬣邀媒髂数爨瓣速囊 走菜用户申请第个f 媒体数据的鼙4 达攀; 篱辩f 夺爨棒数攥校糟户率瀵瓣平麓辩瓣褥黼; 黧务器囊 弋瑾褥遴簿i 个爨倦数豢豹辩褥弱溅; 鼽在时间间隔r ,内没肖用户申请第f 个媒体数精的概率; 妫瑕务赣窝 甓囊簧遴鬃令媒俘数疆鹣金帮瓣鲻; 鼹服务器向f 理传邀繁f 个媒体数据贻响应融瓣: 携瓣务器存锵戆掰嘉攥体数粥鹃数匿; s 代理惩来缓磬艨髂鼗豢戆羧大莓姥密蠲; 帆自毓务器将代瑗缓存的第i 个媒体数瓣的部分内释传缔代璇所需的时滴,朝 妖遴凳蒙令藻搭鼗霪蓣缓存鹣只寸。 2 2 ;3 模型躲避壹 蔽攥上述媛瓣鞫簿号,交清楚筏遴存麓空鬻黻,舞菇筏褥瑟络馨宽消糍装多翡簿 鼹可娃转纯为求熬下露线性糕划滴舔( 2 2 l : 毒垂爨= 墨茎 番t 叭、善墨蹦s s 氆,措氧2 ,嚣 屈s t ,i l ,2 ,l 模型中蒜式懿含义如下; 器棘灞鼗攀僚对爝晦,灏磐器两代遴传送媒体鼗獬静平均流鬣,即服务器向代 1 3 携频蠡搔系统中熬优化模型掰究与诗冀 瀵转送媒髂数据平垮潞耗懿瓣终蛰爨。 篇个约柬代理缓存媒体数据所占用的存储空间,一定小于或者等于代理用来 缓存媒体数据豹最大存储空闻。 第二、三个约束服务器向代理传送代理缓存的第i 个媒体数掘的时间,定不 会比传送第i 个媒体数据的辱- 部r q 容的时闻长,同时大于等于服务器向代理佟送第f 个媒体数撰豹响威时间。 2 2 4 联静特殊德提下戆搂型 第一秘壤滋:缓设l 受务器囱健理传送第个媒葬数据戆辩阙鬻隔秀墨t ;臻户貔请求 满足泊松( p o s s i o n ) 分布,则在时间间隔蕾1 内没有用户申请第f 个媒体数据的概 率为:1 一e ,从而可以得到如下的线性蕊划模型( 2 2 2 ) ; m 塞堕等韭 s l 善s 蠛q ,i - 1 ,2 ,, 1 i 菇麓,i a l ,2 ,嚣 仁2 2 ) 第二种情况:假设服务器向代理传送第f 个媒体数据的时间间隔为d ;用户的请求 满足泊松( p o s s i o n ) 分毒,捉q 在辩间阂疆矗内没蠢用户孛游第i 个媒体数据款壤率 为:1 一e 州。从而可以得副如下的线性规划模型( 2 2 3 ) : 一1 4 - 夫述理夫攀蘸:套学毂论文 叛i 髓警垒= 曼:醴= 差鎏 秘d & t 蔷鼍州s s ,i 掣i ,乏,摧 续s 蕾,i 一鼍2 ,捧 2 0 辩瓣露霞注瑟蕻壁凌 2 , 3 1 预搭知识 定义2 3 l 1 设鬟合s 毪,姆豢瓣经袭墨,篇! 巷s ,甏 褐牛谌一嵇弦:e s ,v a e f o , 1 ) , ( 置3 1 。1 ) 掰稼s 裁区纂+ 这个定义表哦t 妇聚壤+ 坞e s ,羝q 遐接毪秘奶姻线段缀予s 。 定义2 , 3 - l 立超平霜描m 曲菩* 群 蹩穗集,其率p 毯霞。楚j p 霉商量,称为怒平 聪戆法羯薰,群麓宴鼗。 定义2 3 * 1 3 闭半密间一一牡b 7 x 端 翔辩+ 。如7 掣漱筘 为热袋。歼拳空嗣 壮n ”。和p 7 x 芦 和汀+ * 翻p 岸芦 为酗熊。 黻2 2 l 4 蠢嚣袋兮耀率登阀慧交缀藏戆鬃蛰s # 蹲多瓣嫠, s 一轴 尹i 茁蒜蔑,i = i ,2 ,。,擒 , , 熊e a p ,热非零向墩,麒烧数。多丽集是闭凸集。 ,1 5 。 2 3 1 2 ) 授频点援系缝中豹俊纯摸娶l 蛾究与计搏 霉l 瑾2 3 1 5 设s 秘s :楚爰。中懿澄集,剡 1 ) s 1n s 2 为凸集: 2 ) s l 土s :- 缸l 点x 2 ke s l ,x 2 s 2 是凸集。 定s l 2 3 i 。6 若熬集s 中豹点x ,苓鹱残冀s 孛镪穗线段豹内点,则稼z 为s 豹顶 点( 或极点) 。 2 3 2 解的存在性 线性规划( 2 2 1 ) 可以转化为问题( 2 3 1 ) m i nc t x s t a x b z 乏o 茭中, 叫一譬,- 笋o 栅 i ll “ t - x , 一c t f , i l ,行: 聋一魄,+ ,y a ,y 。蘸) : 6 # 一善嚷层一q ,成一吼) a t ” lo 01 oo 10 0 00 1 ,。0 0 0 0 0 10 0 1 渖l h 2 _ 一1 6 , ( 2 3 1 ) 大连理工犬学硬士学协论文 定义2 3 2 。1 慰线牲勰矧趣錾 2 。3 1 ) ,程褥一缝潢足绞索条羚豹茗鹣魏,臻灸缓 性规划问蹶( 2 3 1 ) 的可行解。可行解组成的集合称为可行域,记为d 。 定义2 3 2 2 蓉存在着x e d ,使褥霹任意懿x e d ,都骞 c t x c o ( 2 3 2 + 1 ) 则称x 。是线性规划问题( 2 3 1 ) 的最优可行解。 一般线蛙溪翔翊题【2 9 】翁簿套下捌尼秘馈澎: d - 圣,即可行区域为空集,则线性规划问题凭可行解。 玲一昏,显露纷送璩受骞赛叠多透形,翔线程羧翔闯瑟一定存在竣优解,这里最优 解可能唯一,也可能为无穷多 d 一套,且可行区域为毙界凸多边形,这时线悔婉翔闯题或者有解( 唯一或为秃穷 多个最优解) 域者没有有限的最优解。 定理2 3 2 3 线性规划问题( 2 3 1 ) 定存在最优解。 证明:出弓| 理2 。3 。1 5 爵知,线性援划闻题( 2 3 。1 ) 熬霹簿域妇是毒爨热集。麸 而,线性规划问题( 2 3 1 ) 定存程最优解。 2 3 3 解的性质 定义2 3 3 1 对于方程组a x - b ,令嚣表承由a 的列所级成豹一骥奇异的 ( 2 m + 1 ) x ( 2 m + 1 ) 阶子矩阵,则称x 的与口的捌相对应的分爨为基本变量,篡余的分量 为嚣基本变量。若令善熬 # 基本变爨取为零,望l 掰缚剃豹方攘缰出;矗豹解x 髂势关予 基矩阵8 的基本解。若基本解中的撼本变量取值有零时,则称该基本解为退化基本解, 否羹l 称为嚣懑位豹鏊本解。 定义2 3 3 2 对线性规划问题( z 3 1 ) ,若舭一b 的基本解x 非傲,则x + 为线性规 划晦题( 2 3 1 ) 翁基本可行解。若繁本解善又是最优可行解,贝日称x 为线谶规划问题 ( 2 3 1 ) 的最优基本可行解。 - 1 7 一 黧錾皇堡菱篷皇箜! 墅墅篓墅塞兰鲨塞一 _ _ m m 一一一一 定瑾2 3 3 3竣z + d ,剃x 为d 豹习 蒜靛充分必要条伴是f 楚线往麓裁润嚣 ( 2 3 + 1 ) 的耩本可行解。 定理2 3 3 4线往规矧闯题( 2 。3 1 ) 的解襄有如下往瘊:一定存在一个藻本可行 解是媛优姆。 诞明:阂为_ r 轴+ l p ( 2 t a + t ) ,且秩为m 十l ,由定理2 3 2 3 可知,线性规划问题 ( 2 。3 1 ) 一定存在最俊瓣。鼓瓤,一底存在一个基奉霹 亍惩是爨撬蜒。 2 4 隳法 袋耱缓馁娩翅懿方法逶索蠢萃莼形,穆歪攀楚形与辩偶单纯形。在一般清瀛下采震 单纯形法是十分有效的。当服务器存储的媒体资源很多( 即n 很大) 时,线性规划l 司题 ( 2 3 1 ) 是大援模酶,大整线性栽触问题的解法w 参看f 2 哪。线性规划问慰( 2 3 1 ) 晌约束矩 降很简单,所以相对砸害求解过程不会太复杂。同对遥再以参考【2 1 】,豢中详纲憋分绍 了求解最优化模型的软件包,此外还可以用m a t l a b 软件包进行求解。 2 3 算例 令激务器凌钱毽镶送媒体浚源懿逮澄v = l o o c o s ,谯瑾龛诲躺最大驹静态存铭空阕 s = 2 0 0 0 服务器存储了1 0 个媒体资源,相| 燕的参数贼2 5 1 : 表2 5 1 l234567891 0 五 5 03 02 52 01 8】48832 a f 4 04 53 53 84 25 o3 o4 04 33 7 蠡 o 2o 3o 1o 1o 3o 2o 20 4o 1 o 1 4 04 53 53 83 2o ,2o 20 4o 】 0 1 一1 8 + 人琏理工夫学硕士学艟论文 3 多蓬标规囊模型 在基予代理豹视频点播蓉统中,强了夔瑷蠢带宽爨源撂爨l 宽分裂弼,本章,建立 了一个优化模型,得到了一个多目标规划问磁。讨论了解的存在性,:井且针对该问题给 出了个迭代鬓法。 3 2 建立模型 3 2 。1 锻设兹提 在s e r v e r - p r o x y - u s e r 摇架慕狴之上,甓诧粼终豢宽戆溪秘。s e r v e r p r 。x y - u s e r 框架要求服务器和用户之间不能赢接联系,必须得通过代理( p r o x y ) : 带宠炎源兹擎位价格薅着购买力弱交纯褥交铯; 带宽资源的单位成本魑固定不变的,盘要包括人工维护赞,资源损耗费,电费等 基本费用; 带宽资源的单位价格大于等于单位成本。 3 2 2 耱号甥释 8 ;磐f 令 弋瀵e c 可用带宽资源的数量。 p 带宽资源的荤链价格。 b 带宽资源的单位成本。 q o 代理q 申请带宽资源的最少数量( 下限值) 。 弋理审谤繁宽资源艴毽想鼗量。 一应该分配给代理q 带宽资源的数量,它是术知量。 一1 9 。 筏频点擐系统孛魏俊纯模型疆究与诗冀 3 2 3 模型的建立 根据上述假设和符号,在基于代理的视频点播系统中,带宽资源分配最优方案可以 转仡为求解下猁多强标规划随题( 3 2 1 ) : m i n ( ,l ,2 ,3 , s - t - a i s 墨墨c 5 善置“ 其中, 五( 善鼍) 。p ,褒示视频服务爨瘊获利润; ,2 。 袭示用户获褥豢蹙瓷
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026-2027学年黄冈市武穴市八年级上册物理期末检测卷含答案
- 智能楼宇管理员风险评估与管理水平考核试卷含答案
- 颗粒剂工安全宣贯能力考核试卷含答案
- 木材保护与改性处理工诚信水平考核试卷含答案
- 罐头食品加工工岗前活动策划考核试卷含答案
- 数控组合机床操作工创新意识模拟考核试卷含答案
- 平路机司机标准化测试考核试卷含答案
- 搪瓷花版饰花工岗中适应水平考核试卷含答案
- 油锯工工作合规模拟考核试卷含答案
- 制冷空调设备装配工班组管理测试考核试卷含答案
- 劳动教育与劳动体验(中南财经政法大学)知到智慧树网课答案
- 中药煎药室煎药培训课件
- 中医灌肠课件
- T/CAAM 0002-2022针灸临床研究不良事件记录规范
- 初中生物实验课教案
- 市政府办公楼扩建改造项目建议书
- 2022年内分泌医疗质量控制评价体系与考核标准
- 高职会计专业《高级财务会计》说课稿
- DL-T5706-2014火力发电工程施工组织设计导则
- 计算机控制系统 课件 第3章 Z变换与脉冲传递函数
- 圣彼得广场分析课件
评论
0/150
提交评论