（运筹学与控制论专业论文）多层优化在spusu系统中的应用研究.pdf

摘要 本文利用多层优化方法研究了s - p u s u 通信系统，分别对单服务器单媒体、单服 务器多媒体、多服务器单媒体、多服务器多媒体的s p u 系统进行了研究，得到了若干 双层和三层规划模型，并从诱导型对策的角度证明了上述模型解的存在性在定条件 下，给出了诱导型策略的显式形式另外，用多层规划方法研究了多媒体通信系统( s u ) 的中心式准入控制模型和多媒体通信系统( s - p u ) 的分布式准入控制模型，基于多层优 化模型给出了中心式和分布式准入控制算法本文取得的主要结论概括如下： 1 第2 章首先研究了多服务器多媒体s - p u 通信系统，分别对多服务器多媒体s p 系 统和多服务器多媒体p u 系统以及多服务器多媒体s - p u 通信系统进行了研究，建 立了若干双层规划模型和三层规划模型证明了上述模型的解的存在性，并给出了解 的表示形式当多个服务器合作时，得到了上层是n a s h 平衡的三层s t a c k e l b e r g 平 衡模型然后把多服务器单媒体s - p u 系统、单服务器多媒体s - p u 系统以及单服 务器单媒体s - p u 系统作为多服务器多媒体s - p u 系统的特殊情形进行了讨论给 出了相应的模型及解的存在性结论 2 第3 章建立了多媒体( s u ) 通信系统的中心式准入控制的双层优化模型，并用变分 分析的水平一致有界性理论证明了下层规翊问题的最优解集是独点集给出了基于 该模型的中心式准入控制算法还建立了多媒体( s - p u ) 通信系统的分布式准入控 制的若干三层优化横型，其中有的三层优化模型包含混合平衡点并用变分分析的 水平一致有界性理论证明了下层规划问题和中层规划问题的最优解集都是单点集 给出了基于上述模型的分布式准入控制算法 关键词：双层优化，三层优化，s t a c k e l b e r g 平衡，n a s h 平衡，诱导型策略，中心式准 入控制算法，分布式准入控制算法，s - p - u 通信系统，混合平衡模型 a b s t r a c t t h i sd i s s e r t a t i o ni sd e v o t e dt ot h es t u d yo ns - p - u s - uc o m m u n i c a t i o ns y s t e m sb y u s i n gt h e o r i e s a n dm e t h o d so fm u l t i l e v e lo p t i m i z a t i o n s - p uc o m m u n i c a t i o ns y s t e m s w i t hs i n g l e - s e r v e ra n ds i n g l e - m e d i a ，s i n g l e - s e r v e ra n dm u l t i m e d i a ，m u l t i s e r v e ra n ds i n g l e - m e d i aa sw e l la sm u l t i - s e r v e ra n dm u l t i m e d i a ，r e s p e c t i v e l y , a r es t u d i e di nt h i st h e s i s t h e i r c o r r e s p o n d i n gb i l e v e ia n dt h r e e - l e v e lo p t i m i z a t i o nm o d e l sa r ee s t a b l i s h e d i nt h i st h e s i s f u r t h e r m o r e ，w ep r o v e de x i s t e n c e so fs o l u t i o n st ot h e s em o d e l sb yu s i n gi n c e n t i v es t r a t e g y , a n do b t a i n e de x p l i c i tf o r m u l a t i o n so fi n c e n t i v es t r a t e g yu n d e rs o m e s u i t a b l ea s s u m p - t i o n s i na d d i t i o n ，s um u l t i m e d i ac o m m u n i c a t i o ns y s t e m sw i t hc e n t r a l i z e da d m i s s i o n c o n t r o la n dd i s t r i b u t e da d m i s s i o nc o n t r o la r ea l s os t u d i e db yu s i n gt h e o r i e sa n dm e t h o d s o fm u l t i l e v e lo p t i m i z a t i o n ，a n dt h e i rc o r r e s p o n d i n go p t i m i z a t i o nm o d e l sa r ea l s oe s t a b l 扭h e d b a s e do nt h e s eo p t i m i z a t i o nm o d e l s ，w ec o n s t r u c t e dr e s p e c t i v e l yc e n t r a l i z e da n d d i s t r i b u t e da d m i s s i o nc o n t r o la l g o r i t h m st h em a i nr e s u l t so b t a i n e di nt h ed i s s e r t a t i o n ， m a yb es u m m a r i z e da 8f o l l o w s ： 1 c h a p t e r2i sd e v o t e d t ot h es t u d yo ns - p s y s t e mw i t hn m l t i s e r v e ra n d m u l t i m e d i a p u s y s t e mw i t hm u l t i s e r v e ra n d m u l t i m e d i aa n ds - p us y s t e mw i t hm u l t i s e r v e ra n d m u l t i m e d i a t h e i rc o r r e s p o n d i n gb i l e v e la n dt h r e e l e v e lo p t i m i z a t i o nm o d e l sa r ee s - t a b l i s h e d ，a n dt h ee x i s t e n c e so fs o l u t i o n so fa b o v em o d e i sa r ep r o v e d ，a n df o r m u l a t i o n s o ft h e i rs o l u t i o n sa r eo b t a i n e d u n d e rt h ec o n d i t i o nt h a tm u l t i s e r v e rc o o r d i n a t e d ， w eo b t a i n e dat h r e e l e v e ls t a c k e l b e r ge q u i l i b r i u mm o d e lw i t hu p p e rl e v e lb e i n gn a s h e q u i l i b r i u m a tl a s t ，s - p us y s t e m s w i t hm u l t i - s e r v e ra n d s i n g l e - m e d i a ，s i n g l e s e r v e r a n dm u l t i m e d i a ，a n ds i n g l e s e r v e ra n ds i n g l e - m e d i a ，a ss p e c i a lc a s e so fs - p us y s t e m s w i t hm u l t i s e r v e ra n dm u l t i m e d i a ，a r ed i s c u s s e d ，a n dt h e i rc o r r e s p o n d i n gr e s u l t sa r e o b t a i n e d 2 c h a p t e r3 1 sd e v o t e dt ot h er e s e a r c ho nam u l t i m e d i as us y s t e mw i t hc e n t r a l i z e da d m i s s i o nc o n t r o ia n dm u l t i m e d i as p us y s t e mw i t hd i s t r i b u t e da d m i s s i o nc o n t r 0 1 i n t h i sc h a p t e r t h e i rc o r r e s p o n d i n gm u l t i l e v e io p t i m i z a t i o nm o d e l sa r ee s t a b l i s h e d 治 p r o v et h a to p t i m a ls o l u t i o n s e t so fl o w e rl e v e lo p t i m i z a t i o n so fb i l e v e lo p t i m i z a t i o n m o d e l sa r es i n g l e t o n ，a n dt h a to p t i m a ls o l u t i o n s e t so fl o w e ra n dm i d d l el e v e lo p t i m i z a t i o n so ft h r e e - l e v e lo p t i m i z a t i o nm o d e l sa r eb o t hs i n g l e t o nb yu n i f o r mb o u n d e d n e s so f1 e v e i s e t si nv a r i a t i o n a la n a l y s i s i na d d i t i o n w ec o n s t r u c t e dr e s p e c t i v e l y i l l c e n t r a l i z e da n dd i s t r i b u t e da d m i s s i o nc o n t r o la l g o r i t h m s k e yw o r d s ：b i l e v e lo p t i m i z a t i o n ，t h r e e - l e v e lo p t i m i z a t i o n ，s t a c k e l b e r ge q u i l i b r i u m ， n a s he q u i l i b r i u m ，i n c e n t i v es t r a t e g y , c e n t r a l i z e da d m i s s i o nc o n t r o la l g o r i t h m ，d i s t r i b u t e d a d m i s s i o nc o n t r o la l g o r i t h m ，s - p uc o m m u n i c a t i o ns t s t e m s ，m i x de q u i l i b r i u mm o d e l 第一章绪论 本章简要地对论文的选题背景以及理论背号作以综述，概述所研究的 内容以及所取得的主要结果，并给出了论文研究所需的预备知识一诱导型 策略 1 1 选题背景 由于i n t e r n e t 用户的急剧增加，如果每个用户都申请一个地址，会极大的浪费i n t e r n e t 的地址资源，因此是既不经济又无必要的另一方面，在多媒体通信中，每个用户都要 求网络提供良好的服务质量( q o s ) ，保证q o s 的一种方法是为每个请求q o s 的连接预 留足够的资源( s s h e n k e r ( 1 9 9 5 ) 7 0 ) ，然而许多分布式多媒体应用具有大容量、突发性等 特点，而且用户往往希望自已获得的网络资源越多越好，这就很容易造成拥塞并使应用 q o s 降低( 傅晓晚等( 2 0 0 2 ) ( 3 6 1 ) 为了缓鳃s e r v e r 的压力、避免拥塞从丽保证q o s ，需要 在s e r v e r 下设立若干个代理服务器( p r o x y ) 从根本上来说，代理服务器就是防火墙技术中应用层网关的实现形式，是一种同时 扮演用户机和服务器两种角色的中介程序作为代理服务器，它接受内部网( i n t r a n e t ) 中 用户机所发出的对外部网( i n t e f n e t ) 的一切访问请求同时，在完成对这些请求的审核 后，将其转换为自己的请求传送给i n t e r n e t 服务器i n t e r n e t 服务器接受访问请求后作 出应答，并将应答传回给代理服务器代理服务器把这些应答分别发送回原来的i n t r a n e t 中提出请求的用户机因此，对于i n t e r n e t 上的服务器来说，它就是一个普通的用户机 除了必要的身份认证外，代理服务器在用户使用时完全是透明的” 使用代理服务器的好处很多：一、节省用户的访问时间，大量的i n t e r n e t 站点信息 在网内用户访问后被缓冲到了代理服务器的高速缓冲器中，用户对i n t e r n e t 的访问很多 是从代理服务器的c a c h e 中提取信息，使得用户感觉i n t e r n e t 的速度在提高，从而节省 了用户的访问时间；二、降低i n t e r n e t 的拥塞程度，代理服务器承受了大量网内用户对 i n t e r n e t 的访问压力，减少了用户直接访问i n t e r n e t 的次数，使得i n t e r n e t 节省了大量的 带宽，降低了i n t e r n e t 的拥塞程度；三、节省本地网络用户的开销，一台带有较大c a c h e 的代理服务器，可以大大降低一个网络用户访问i n t e r n e t 流量的成本，从而节省了本地 网络用户的开销；四，增加了网络的安全性，因为外界用户无法直接与i n t r a n e t 中的用 户进行通信，从而减少了i n t r a n e t 受攻击的可能性，增加了网络的安全性；五、通过内 部的身份认证，管理员可以为不同用户设置不同的访问权限 正因为代理服务器的上述特点，被广泛应用于网络通信中然而目前研究网络通信的 文章讨论的都是服务器一用户( s e r v e r s u s e r s ) 系统，如网络资源分配( 张敬辕等( 2 0 0 2 ) f 8 7 1 ， 查垄垄三查兰堕主兰垡鲨窭：垒星垡垡垄! ! 旦笪旦墨堕主堕窒旦堕窒 rg u e r i n e t 础( 1 9 9 1 ) f 4 1 】) 、准入控制( wk e d w a r de t a l ( 1 9 9 9 ) 2 9 ，e c h a n ge t a l ( 1 9 9 4 ) f l s ) 、流量控制( h l o w s t e v e n ( 1 9 9 9 ) 7 7 ) 等等把代理服务器作为服务器的缓7 申器 或高速缓存器阱降低访问时间( m r h o w a r de ta 1 ( 1 9 9 8 ) 4 6 1 ) ，响应时间( c d m u r t a e t a 1 ( 1 9 9 9 ) 6 2 ) ，存储管理( e p m a r k a t o se ta 1 ( 2 0 0 2 ) 【s s l ) ，批处理( k hb e a k e t a 1 ( 2 0 0 1 ) ；1 ) 等等 本文充分考虑代理服务器的双重身份特性，把代理服务器看成服务器和用户之间的 独立单元，这样通信系统由原来的服务器一用户( s e r v e r s - u s e r s ) 系统变为服务器一代理 服务器用户( s e r v e r s p r o x i e s u s e r s ) 系统，简称s - p u 系统在这个系统中，服务器是 通过代理服务器给用户提供服务，换句话说，每个用户都向代理服务器提出请求，代理 服务器准入后由代理服务器向服务器提出申请 服务器一代理服务器一用户( s e r v e r s - p r o x i e s - u s e r s ) 系统的优点是： 1 比原来的服务器一用户系统更符合实际的网络系统，因为代理服务器被广泛应用于 实际的网络通信中； 2 能够实现分布式准入控制，它的响应时间显然小于中心式准入控制的响应时间也 就是说，能够提高网络的服务质量 1 2 理论背景 由于在s - p u 系统中，s e r v e r s 对p r o x i e s 有权决定提供哪类服务，因此在整个系 统中处于领导地位因此建立s - p 系统的双层规划模型时，可利用对策论的s t a c k e l b e r g 平衡来建立模型同样，p r o x i e s 对u s e r s 也处于领导地位，所以用s t a c k e l b e r g 平衡建 立p u 系统的双层规划模型这种层次关系同样存在于整个s - p u 系统，故s - p u 系 统的三层优化模型也是由s t a c k e l b e r g 平衡得到即这里建立的多层优化模型是以对策论 的s t a c k e l b e r g 平衡为工具建立的所以我们先看对策论在网络通信中的应用 对策论可以定义为对理性决策者之间冲突与合作的数学模型的研究，是分析涉及两个 或更多个参与者且其决策会影响相互之间福利的局势提供一般的数学方法对策论( g a m e t h e o r y ) 所研究的局势，不仅仅是“游戏( g a m e ) ”一词所表示的消遣活动描述对策论更 确切的术语应该是“冲突分析”或相互影响的决策理论” 对策论按有关局中人之间的地位是否平等可分为平等对策、组对策和递阶对策三类 平等对策还可以按局中人的人数以及局中人之间是否合作进行分类，如二人合作非合 作对策，多人合作非合作对策递阶对策按局中人的决策方式可分成主从对策f l e a d e r - f o l l o w e rg a m e ) 和诱导对策( i r t c e n t t v eg a m e ) 递阶对策也可按递阶结构的层数，同层 间是否合作进行细分 2 第一章绪论 关于主从对策，盛昭瀚和井元伟作了一系列工作，见文献盛昭瀚( 1 9 9 8 ) 6 8 j 和井元 伟( 1 9 8 8 ) 4 8 1 及他们的参考文献关于诱导对策在第四节具体讨论 a a l a z a r ( 1 9 8 3 ) f 5 6 将对策论思想引入了网络通信中利用n a s h 平衡思想研究了 运行点( o p e r a t i o np o i n t ) 在此基础上，l th s i a o 等( 1 9 8 5 ) 【4 2 】明确定义了n a s h 平 衡，且证明了它的存在性 lt h s i a o 等通过定义一个窗1 3 模式机制( w i n d o w t y p e m e c h a n i s m s ) 研究了系统中r 个用户流量控制的n a s h 平衡及其存在性每一个用户的目 标是在平均时延( a v e r a g et i m ed e l a y ) 约束下极大化平均吞吐量( a v e r a g et h r o u g h p u t ) 由于n a s h 平衡的公平性，在通信系统中被广泛应用n a s h 平衡用于流量控制问 题，见文献e a l t m a ne ta l ( 1 9 9 9 ) 1 i ，r t m a h e s w a r a ne ta l ( 1 9 9 8 ) 1 5 r ，r m a z u m d a re t a l ( 1 9 9 0 ) 6 0 ，r m a z u m d a r e ta l ( 1 9 9 1 ) 6 1 ，s js h e n k e re tm ( 1 9 9 5 ) 【6 9 】等；s j s h e n k e r e ta 1 ( 1 9 9 5 ) 6 9 1 等用n a s h 平衡研究了多类业务的最优流量控制问题，采用n a s h 谈判解 作为系统的优化指标，给出了n s u s h 平衡的唯一性条件并证明了n a s h 平衡是p a r e t o 最 优；n a s h 平衡用于网络价格问题，见文献r c o c c h ie ta 1 ( 1 9 9 3 ) 【2 1 1 ，j l ，r i c h a z de t a l ( 1 9 9 9 ) 6 4 l 等；n a s h 平衡用于网络路由问题，见文献e a l t m a n e tu 1 ( 1 9 9 9 ) 1 1 等 p d u b e y ( 1 9 8 6 ) 【2 6 指出，非合作条件下的n a s h 均衡对系统的资源利用率往往都不 是最好的，在网络设计与规划阶段，增加特定链路的带宽有时还将恶化网络的传输性能 因此，网络管理者如何“引导”用户提高网络整体传输性能是非合作对策模型下的一个 关键问题讨论在具有“积”形式的网络存在n a s h 均衡，而且在用户采用基于q o s 约 束的最佳策略( b e s t r e p l y ) 时，采用同步或异步迭代算法均收敛于n a s h 均衡解并提出 建立网络收费站的方法，但仅限于理论分析 pd u b e y ( 1 9 8 6 ) 【2 6 】中虽然有s t a c k e l b e r g 策略的思想，但s t a c k e l b e r g 平衡出现在 网络通信的研究中是c d o u l i g e r i se ta l ( 1 9 s s ) p 5 它们考虑了两个用户且每一个用户的 目标是在平均时延约束下极大化平均吞吐量用户的到达过程是参数分别为a 1 和a 2 的 p o i s s o n 过程服务是参数为肛的指数分布用户的势函数( p o w e rf u n c t i o n ) 为 其中 a 只( m ，p ) = 薷i ，i = l ，2 u l m j m 是第i 个用户的吞吐量； d ( q i ) 是第i 个用户的平均时延， 觑是正常数 c d o u l i g e r i s 等给出了系统的s t a c k e l b e r g 平衡点 ( 们舻( 尚，两糯) 3 大连理工大学博士学位论文：多层优化在s p u s u 系统中的应用研究 但是，c d o u l i g e r i se ta l ( 1 9 s 8 ) 没有给出s t a c k e l b e r g 模型x i - r e nc a oe ta l ( 2 0 0 0 1 11 j ，x i r e nc a o e t a i ( 2 0 0 2 ) 1 2 】在研究网络价格问题时，建立了s t a c k e l b e r g 模型，而 没有讨论其解的情况，用数值算例比较了s t a c k e l b e r g 平衡点和合作对策的解在通信系 统中，建立了s t a c k e l b e r g 模型并研究它的解的文献是井元伟等( 2 0 0 1 ) 4 9 1 井元伟等在研究网络流量( 弹性流量e l a s t i ct r a f f i c ) 问题时，分别建立了用户模型 和系统模型，然后建立网络模型将两者联系起来 u s e r ，( 以；a 。) ：m a x 玩( z ；) 一a 。z 。 s t 。0 其中玩( ) 是用户s 的效用函数，儿是单位流量对用户s 的价格 s y s t e m ( u , 日：a ，c ) ：m “羔l 仉( 。) s t h y = o a y c z ，”0 其中日和a 是0 - 1 矩阵，y 是流的流型( f l o wp a t t e r n l n e t w o r k ( h , a ，c ：a ) ：m a x 是l 九 8 t h y = z a ysc z ，y 0 并证明了 和 ra 。( z ；一z ，) z 。， 挑( 岛) = 2o ， 【( 以( 。) 玩( 。：) ) 。 如果z 。 z 。a 分别是上述模型的线性和非线性诱导策略其中吼是网络确定的常数，。：是所考虑的 点 本文的第二章在井元伟和x i r e nc a o 等的工作基础上，用s t a c k e l b e r g 平衡理论研 究了这里所提出的通信系统s - p u ，对s - p 和p - u 系统分别建立了双层s t a c k e l b e r g 平 衡模型，对s - p u 系统建立了三层s t a c k e l b e r g 平衡模型，并且结合n a s h 平衡建立了若 干个具有混合平衡的双层和三层优化模型证明了上述模型的解( 诱导策略) 的存在性并 给出了线性和非线性诱导策略的存在性条件 d 第一章 绪论 应用埘策论研究通信系统准入控制问题的文献是l g m a s o ne ta i ( 1 9 9 3 ) 【5 9 ，z d z i o n ge ta 1 ( 1 9 9 6 ) 2 7 1 和陈惠民等( 1 9 9 8 ) 1 7 1 等， l gm a s o ne ta 1 ( 1 9 9 3 ) 5 9 1 和z d z i o n ge ta l ( 1 9 9 6 ) 2 7 给出了阻塞概率平衡( b l o c k - i n ge q u a l i z a t i o n ) 与对策论的r a i l i a 解是一致的、通信量极大( t r a f f i cm a x i m i z a t i o n ) 的 性能函数和改进的t h o m s o n 解( m o d i f i e dt h o m s o ns o l u t i o n ) 是一致的的结论 假定第j 类呼叫以参数a ，的p o i s s o n 分布到达，服务占用时间服从均值盯1 的指数 分布，所需带宽为d 。由于不同的呼叫产生不同的阻塞概率，呼叫准入控制的目的是网 络给所有的呼叫类提供公平的访问把呼叫类看成是对策论的局中人，呼叫准入准则看 成仲裁人 他们得到的阻塞概率平衡是 m “6 n = ( 1 一b j ) + l 一击( 1 一) 其中 = 1 鲁； a d = 如如町1 ； 。 a 3 = x j d 3 吒i j b 是第j 类呼叫的访问率( a c c e p t a n c er a t e ) 标准化阻塞概率为 从而阻塞概率平衡与对策论的r a i f f a 解当呸= 6 j 时，是一致的 陈惠民等( 1 0 0 8 ) p r l 根据【业务的等效带宽表征了网络为确保该业务的q o s 而必须 分配的资源”这一特性，以等效带宽作了连接准入控制的准则具体通过定义基于时延 带宽积的收益函数 其中 c ( l ，b ) = ，( l ) 十k ( c 7 + 2 b t ) n c l ( 1 一n c l ) 】 n 为源到目的所经过的交换节点数； 5 嘶 南 岵 大连理工大学博士学位论文：多层优化在s e u s u 系统中的应用 ! 窒 c 为用户原始的数据包长度； 为加上由于传输差错或信元丢失而导致重发的数据后的总长，将上述因素都视为 信元丢失就由c 7 = c l l + o l ( l ) t ； 三为单交换节点上的信元丢失率； 口( 是由于信元丢失引起数据重发的影响因子； b 为链路分配的可用带宽； t 为源到目的节点的传输时间； f ( l ) 是加权函数，根据不同业务的服务质量要求，随信元丢失率的增大而衰减 第i 类业务的收益函数定义为 蛳= c i ( l i ，b 。) ，i = 1 ，2 ，一， 再定义偏好函数 = u i + i f l ( n 一1 ) 卜口“； j 。 利用合作对策模型 m a 。x ：u v l 砚) ( 1 2 1 ) 实现了准入控制 准入过程为：当第i 类业务的呼叫请求到来时，估计该业务的等效带宽阢f 有计算公 式) ，用遗传算法求解模型( 12 1 ) ，得该类业务所能获得的带宽鼠设已准入的第i 类业 务占用的链路带宽为鼠，则当鼠一旦 6 。时，准入第i 类业务的呼叫；否则拒绝 本文的第三章利用对策论的s t a c k e l b e r g 平衡理论研究了通信系统的准入控制问题 分别建立了s u 系统的中心式准入控制和s - p _ u 系统的分布式准入控制的多层优化模 型，其中包括具有混合平衡的多层优化模型给出了上述多层优化模型的解的存在性条 件，在此基础上给出了中心式准入控制算法和分布式准入控制算法 1 3 本文研究的内容及主要结果 本文把代理服务器看作服务器和用户之间的一个独立实体来考虑所以这里讨论的 通信系统是s e r v e r s p r o x i e s - u s e r s 系统，简称为s - p u 系统利用对策论的n a s h 平衡 和s t a c k e l b e r g 平衡，研究了s p - u 系统建立了若干多层优化模型，并证明了这些模型 解的存在性利用多层优化理论研究了多媒体通信系统的准入控制问题，给出了中心式 和分布式准入控制算法取得的结果概括如下： 6 嚣一章绪 论 第2 章首先研究了多服务器多媒体s - p u 通信系统，分别对多服务器多媒体s - p 系 统和多服务器多媒体p - u 系统以及多服务器多媒体s - p u 通信系统避行了研究，建立了 若干双层规划模型和三层规划模型证明了上述模型的解的存在性，并给出了解的表示 形式，当多个服务器合作时，得到了上层是n a s h 平衡的三层s t a c k e l b e r g 平衡模型如 m 淋。兀墨ls 瓯( t “，c i k ) s t 露“c i c ，m a - x m a x t 。c tk ) t p ；( t “，c ik ，珞k ，瓯) s t c 。m i n 墨瓯i 兰c r a a x t 0 m a x t j 啪y 奶巧k ( z t f k ，c l i n ) s t t l j k 0 j = l ，2 ，一，饥 七= l ，2 ，- 一， 然后把多服务器单媒体s - p u 系统、单服务器多媒体s - p u 系统以及单服务器单媒体 s - p u 系统作为多服务器多媒体s - p u 系统的特殊情形进行了讨论给出了相应的模型 及解的存在性结论 第3 章建立了多媒体( s - u ) 通信系统的中心式准入控制的双层优化模型，如 i n a x 。，墨l 弓。“g 。 s t c 20 墨ly o z “8 m “q ，( ) 一c y x f j y 0 s t ， y l j f 0 ，1 ) 0s 。b f = 12 并用变分分析的水平一致有界性理论证明了下层规划问题的最优解集是独点集给出了 基于该模型的中，f l , 式准入控制算法还建立了多媒体( s - p u ) 通信系统的分布式准入控 7 查壅堡坠兰墼丝篓塾垒墅些婴塑坚绁丝墅生一 制的若干三层优化模型 m a x c ，c ；：c j i y j i s , t c j 0 芒。诉，茎8 y “ o ，1 i i i d x 扣) 链埽( j ；) 一弓z j t 翰，+ c 吾x h t m 弹 s t 0 z j 。s 召 g j2 0 墨1 x 。t 墨g ； m a x ，w q d x l j i ) 一咣x m ” s , t 0 x 1 ) i 鼠 ， o ，1 ) i = 1 2 z = 1 ，2 ，一， m 还建立了包括具有混合平衡点的三层优化模型 m a x 兀冬，c 毛z 彬y k j ； s t c k j 0 磐1 茁幻 ts b y k ，t 0 ，1 m a x q ”) 叫柳；( z k ，。) 一，z 协，剪 ”+ 托 m 幻z s t 0 曼x k j l sb g 柳0 鉴l x l 幻，m 材 甄k m a , x x 。( x f 幻。) 一x 州t m 蜘 s t 0 五坷i 鼠 靳埘t o ，1 ) 1 = l ，2 ，一， i ：12 m 并用变分分析的水平一致有界性理论证明了下层规划问题和中层规划问题的最优解集都 是单点集、给出了基于上述模型的分布式准入控制算法 8 第一章绪论 1 4 诱导策略 1 4 1 双层规划问题的诱导策略 考虑一个l e a d e r 和一个f o l l o w e r 进行的诱导对策问题，l e a d e r 的策略集，目标函 数和决策变量分别为u r “，j l = j l ( u ， ) 和u uf o l l o w e r 的策略集，目标函数 和决策变量分别为v 印，j v = j f ( u ，”) 和”v 它们的目的是选择各自的决策变 量u u 和u v 使得各自的目标函数达到极小，对策的规则是l e a d e r 先宣布自己 的诱导策略u = 1 ( u ) ，f o l l o w e r 以此作为约束解决自己的最优化问题，然后l e a d e r 遵守 自己的策略并执行由其决定的决策量问题是l e a d e r 如何选择u = 7 ( ) 使最后得到的 九= j l ( ，u ) 最小。 l e a d e r 采用的策略1 ：v 一矿要有引导f o l l o w e r 的作用，就应具有如下性质： 办( 1 ( u ) ，u ) 在y 中只有。处取得极小值，且面= 1 ( o ) ，具有这样性质的策略，y 称为诱 导策略，l e a d e r 的所有可能的策略集合记为r ，并对任意7 f ，记k = ( “，u ) i “= ，( ) ，口v ) 诱导策略是l e a d e r 宣布的一种巧妙的决策对应关系，在这种对应关系下，f o l l o w e r 从自身的利益出发，作出的决策正是l e a d e r 所希望的诱导策略又称为鼓励性策略或激 励性策略 主从对策( 又称s t a c k e l b e r g 对策) 是英国经济学家v s t a c k e l b e r g 在1 9 5 2 年开始 研究静态经济问题时，提出的一种对策模型关于主从对策的一般性介绍，可参见t b a s a r ( 1 9 8 2 ) ( 6 ，郑应平( 1 9 8 7 ) 【9 0 】，更深入的研究可参见t b a s a r ，j b3 r c r u z ，y p z h e n g 等人的工作 主从策略的概念提出来以后，c h e n ，s i a a m ，c r u z 等人在2 0 世纪7 0 年代初将主从 策略引入动态对策的研究( c c h e r te ta 1 0 9 7 2 ) 1 6 1 ，m s i a a me ta 1 ( 1 9 7 3 ) 7 2 ， 7 3 】，m s i m a a n ( 1 9 7 7 ) 7 4 d ，引起人们普遍的兴趣，又提出了一系列新的概念，如开环策略，反馈 策略，闭环策略等等 人们开始研究动态主从对策时发现，局中人由于拥有不同的动态信息而使用不同的 动态策略时。局中人的目标函数的最好值大不一样( c c h e ne ta l ( 1 9 7 2 ) 1 6 j ，b fg a r d n e r e t a 1 ( 1 9 7 7 ) 3 7 1 ，b f c a r d n e re ta 1 ( 1 9 7 8 ) 3 8 ) tb a s a re ta 1 ( 1 9 7 9 ) 5 】研究了l e a d e r 的目标函数最好值的下确界，并证明了在一定条件下存在实现此下确界的l e a d e r 的策 略，b a s a r 称之为“队优”( “t e a m - o p t i m a l s t r a t e g y ) ，还提出了求此策略的“间接法” 其思想是，对于l e a d e r 来说，最好的对策结果不过是双方合作所得出的共同优化结果 这样，就可以先用常规方法求解共同最优决策，也就是所谓的t e a m 解然后设计一个 策略，使在此策略之下。对策结果达到t e a m 解 t ，b a s a re ta l ( 1 9 7 9 ) 先求出l e a d e r 的目标函数达到最好值时要求l e a d e r ，f o l l o w e r 9 大连理工大学博士学位论文：多屡优化在s p u s u 系统中的应用研究 采取的决策，然后寻找实现此决策的策略，这里隐含着诱导的思想t b a s a re ta 1 ( 1 9 7 9 ) 中所谓的“队优”策略实际上是一种诱导策略，只是它没有把l e a d e r ，f o l l o w e r 双方的决 策变量联系起来，而是通过中间变量( 状态变量) 来实现对f o l l o w e r 的引导 t b a s a re tu l ( t 9 7 9 ) 虽然为诱导策略的提出提供了契机，但诱导策略在控制文献中 似乎首先由yc h oe ta 1 ( 1 9 8 1 ) 4 3 提出h o 等人提出诱导策略这个概念后， y c h oe ta i ( 1 9 8 2 ) 【4 4 ，( 1 9 8 4 ) 4 5 1 对诱导问题作过透彻的分析许多学者对诱导问题作过研 究，其中美国的y ch o ，p bl u h ，t ，sc h a n g ，tb a s a r 和中国的郑应平( 1 9 8 2 ) 8 8 1 ， ( 1 9 8 6 ) 8 9 、张嗣瀛( 1 9 8 6 ) 8 6 】、徐春晖( 1 9 9 0 ) 8 3 的工作具有代表性 以上工作都是针对局中人的目的是极小化其目标函数而进行的而本文建立的模型 中要求极大值，因此首先要把相关的概念和结果转化成极大问题的情况 定义l4 1 如果存在u = ，y ( ) 使得 i ；a r g m a x 。 矗( “， ) fu = 7 ( u ) ”y )( 1 4 1 ) 并且百= 7 ( o ) ，则称( 面，i ) 是可诱导的，7 称为l e a d e r 在( 毛，o ) 处的诱导策略( i n c e n t i v e s t r a t e g y ) 引理1 4 2 m = s u p 。i n f 。如( “， )( 1 4 2 ) 若m 如( e ，i ) ，则( a ，o ) 不可诱导 定义143 如果存在某一7 r ，使得u 包含( 口，o ) ，且对任意( u 1 ， 1 ) ，( 铲，u 2 ) 嵋，满 足 j k u o ，v 0 ) 兰a 办( 1 ， 1 ) + ( 1 一a ) j _ ( u 2 ，u 2 )( 1 43 ) 其中 o = a v l + ( 1 一a ) u 2 ，u o = 7 ( ”o ) ，a 1 0 ，1 】，则称办在( 豇，口) 处具有约束凹性， 当不等式( 1 4 ，3 ) 严格成立时，称易在( 匠，口) 处具有严格约束凹性 引理l4 4 若矗是uxv 上的( 严格) 凹函数，则j f 在uxv 上的任意占、都具有( 严 格) 约束凹性 引理1 4 5 设妇是可微函数，则 ( 1 ) 矗在( ，日) u v 处具有约束凹性的充要条件是：存在，y r ，使得( f i , o ) k 且对任意( d ，口) ，( 札，口) k 都有 j f ( u ，u ) j p ( 五，面) + v ：j f ( 1 ( o ) ，o ) ( u 一面) ( 144 ) 其中可j 矗( 7 ( 口) ，。) ( ”一。) = ( 掣，掣) 7 b 1 0 第一章绪论 ( 2 ) 办在( 再，口) u v 处具有严格约束凹性的充要条件是：不等式( 144 )