（应用数学专业论文）计算机通信中两个随机问题的建模研究.pdf

复旦大学硕士学位论文 t b a l 3 69 摘要 本文分别采用一种特殊的排队系统( d m m d p 1 k ) 和马尔科夫决策理论就g p r s 流 控中的p c u 桶的容量和通信中多业务情况下信道在一定条件下的分配问题进行了研究并 建立了数学模型，结合数值例子，给出了实际问题的解决办法( 或结论) 本文在第一章中首先对经典排队论给出了介绍，指出了经典排队系统和本文第二章中 所采用的排队系统( d m m d p i k ) 的关系。然后我们考虑jg p r s 通信的p d u 流控设计 中的p c u ( 桶) 的容量问题。通过研究分析，我们发现：在一定的假设条件下，所研究的随机 系统可以用一d m m d p 1 k 排队系统来模拟，通过对系统的分析研究，结合数值实例，给 出了p d u 流控设计中p c u 桶的大小的一种估计方法。 在第二章，我们对马尔科夫决策过程理论进行了简单的介绍，并重点介绍了通过一致 吧的方法如何将转移率依赖于状态和决策的连续马尔科夫决策问题( c l m d p ) 转化为经典 j 带有不依绚状态和决策的一致转移率的离散马尔科夫决策问题( d t m d p ) 去解决，这种 巴想将在第三章的实际问题的解决卞得到重要的应用。 在第三章，我们考虑了通信中的另一个问题通信业务占用信道数的最大限问题。 已问题的解决是通过建立一个马尔科夫决策模型( 模型中的报酬函数为带有折扣的无期报 时) ，应用动态规划的方法并结合数值实例给出的。 关键词：g p r s ；d m m d p l k 排队系统；动态信道；c t m d p ；d t m d i ：一致化方法；动 规划。 复里盔堂亟圭堂笪煎塞 2 a b s t r a c t t w o t y p ep r o b l e m sh e l o n g i n gt od e s i g n i n ga n d c o n t r o lr e s p e c t i v e l ya r eo f t e ne n c o u n t e r e di n m a n ys t o c h a s t i cs y s t e m sf r o mv a r i o u sa r e a s ，s u c ha sc o m p u t e r c o n l n l u n i c a t i o nn e t w o r k s f l e x i b l e m a n u f a c t u r i n gs y s t e ma n de l e c t r o n i cc o m m e r c e ，ap r o b l e m o fd e s i g n i n g e s t i m a t et h es i z eo f p c ub u f f e ri ng p r sw i t hd m m d p 1 kq u e u e i n gs y s t e ma n da n o t h e rb e l o n g i n gt oc o n t r o l - - t h e o p t i m a la l l o c a t i o nf o rc h a n n e li ng e n e r a lc o m m u n i c a t i o na r es t u d i e db ym o d e l l i n g w i t ht h et h e o r y o fq u e n e i n ga n dm a r k o vd e c i s i o np r o c e s s e sr e s p e c t i v e l ya n di n t e r e s t i n gr e s u l t sa r eo b t a i n e d i l l c h a p t e r1 ，f i r s t ，w eg i v e ap r o f i l ef o rt h ec l a s s i c mt h e o r yo fq u e u e i n g ，a n dp o i n to u tt i l e r e l a t i o n s h i pb e t w e e nt h et h e o r yo fd m m d p l kq u e u e i n gs y s t e m sa n dt h ec l a s s i c a lo n e t h e n ， w ec o n s i d e rt h ep r o b l e mo fp c u c a p a c i t yi l lg p r s p d uf l u i dc o n t r o la n df i n dt h a tt h ep r o b l e m c a l lb es i m u l a t e db yad m m d p 1 kq u e u e i n gs y s t e m f i n m l y ，w eg i v eam e t h o dt oe s t i m a t e t i l ep c u c a p a c i t ya n da l s oi n c l u d ea ne x a m p l e i nc h a p t e r2 、w eg i v ea p r o f i l eo ft h et h e o r yo fm a r k o vd e c i s i o np r o c e s s e s ，a n dh i g h l i g h tt h e s o c a l l e du n i f o r m i z a t i o nw h i c hc a nc o n v e r tac o n t i n u o u st i m em o d e lw i t hs t a t e d e p e n d e n te x p o n e n t ，i a l t r a n s i t i o nr a t e sl oad i s c r e t em o d e lw i t has t a t e - i n d e p e n d e n tt r a n s i t i o nr a t ec t h i si d e aw i l lb e a p p l i e di nc h a p t e r3 h ic h a p t e r3 ，w ec o n s i d e ra n o t h e rp r o b l e m - - t h eo p t i m a la l l o c a t i o no fd m n n e li nc o n n l u n i c a t i o nw em o d e li tb yam a r k o vd e c i s i o np r o c e s s e sw i t hn o n h o r i z o n t a le x p e c t e dd i s c o u n t e dr e w a r d ，m i dt h e ng i v et i l em e t h o dt oa l l o c a t et h ec h a n n e la n da l s oi n c l u d ea ne x a n l p l e k e y w o r d s ：g p r s ；d m m d p 1 kq u e u e i n gs y s t e m ；d y n a m i cc h a n n e l ；c t m d p ；d t m d p ；u n i f o r m i z a t i o n ；d y n m n i cp r o g r a m m i n g 。 复旦大学硕士学位论文 前言 2 0 世纪中期以来，随着计算机通信网络、柔性制造系统( f m s ) 、电子商务( e c ) 等高 新技术的发展，提出了大量复杂随机系统的设计和控制问题相对准确地计算或估计一些 实际的相关参数对于优化系统设计，无疑是有现实意义的；而在随机系统的控制过程中， 相对准确地给出控制决策，此重大意义也是不言而喻的。本文分别采用一种特殊的排队系 统( d m m d p 1 k ) 和马尔科夫决策理论就通信( 见【1 1 】) 中两个有意义的随机问题( 分别 隶属于设计和控制) 进行了研究，建立了数学模型，并结合数值例子，给出了实际问题的 解决办法( 或结论) 之所以说d m m d p u k 是一特殊的排队系统，是与经典的排队系统 ( 见 1 | 1 s 】) 相比较而言的，当然它也不同于休假型的排队系统( 见【2 】) ，但它们皆是以 经典的排队论为基础发展起来的。在通信模型中无论输入还是输出，大多为马尔科夫调制 型的，常见的有马尔科夫调制泊松过程( m m p p ) ( 见【3 j ，【1 4 ) ，马尔科夫调制伯努力过程 ( m m b p ) ( 见1 1 7 】) ，马尔科夫调制定长过程( m m d p ) ( 见【2o 】) 等等也许正是由于来自现实世 界随机模型输入输出的多样性，才使使得古典排队论得以焕发勃勃生机。当然这期间，良 好的解析方法的提出，特别是n e u t s ( 1 9 8 1 ) 【1 4 】的矩阵几何理论，对排队论的发展做出了巨 大的贡献谈到随机模型和最优化方面的理论方法【1 2 】，就不得不谈一下马尔科夫决策过 程理论，它的产生已有4 0 多年的历史，国内进行此研究的有中科院应用数学所已故研究员 董泽清先生，以及现在的胡奇英、刘建庸先生等【1 0 1 ，国外这方面值得一读的理论专著是 【1 3 ，p u t e r m a n ，1 9 9 4 】这期间一篇有意义的里程碑式的文章是 1 8 ，l i p p m a n ，1 9 7 5 ，它给出 将转移率依赖于状态和决策的连续马尔科夫决策问题( c t m d p ) 转化为经典的带有不依赖 状态和决策的一致转移率的离散马尔科夫决策问题去解决的思想为后来的众多研究人员所 频频引用，足以说明这一思想火花的意义重大。有关动态规划的理论可参考【5 【6 1 ( 7 9 ， 这里就不再赘述本文余下部分的安排如下： 本文在第一章中首先对经典排队论给出了介绍，指出了经典排队系统和本文第二章中 所采用的排队系统( d m m d p 1 k ) 的关系然后我们考虑了g p r s 通信的p d u 流控设计 中的p c u ( 桶) 的容量问题通过研究分析，我们发现：在一定的假设条件下，所研究的随机 系统可以用一d m m d p 1 k 排队系统来模拟，通过对系统的分析研究，结合数值实例，给 出了p d u 流控设计中p c u 桶的大小的一种估计方法 在第二章，我们对马尔科夫决策过程理论进行了简单的介绍，并重点介绍了通过一致 化的方法如何将转移率依赖于状态和决策的连续马尔科夫决策问题( c t m d p ) 转化为经典 5 复旦大学硕士学位论文 的带有刁= 依赖状态和决策的一致转移率的离散马尔科夫决策问题( d t m d p ) 去解决，这种 思想将在第三章的实际问题的解决中得到重要的应用 在第三章，我们考虑了通信中的另一个问题通信业务占用信道数的最大限问题。 此问题的解决是通过建立一个马尔科夫决策模型( 模型中的报酬函数为带有折扣的无期报 酬) ，应用动态规划的方法并结数值实例给出的 6 第一章采用d m m d p 1 k 模型估计g p r s 中p c u 桶的容量 1 1 经典排队系统和d m m d p 1 k 排队系统的关系 经典排队系统( 也称经典随机服务系统) ，源于e r l a n g 关于电话服务的研究，第二次世 界大战以后得到迅猛发展，成为随机运筹学与应用概率论中最有活力的研究课题它不仅 建立了较完备的理论体系，而且在军事、生产、经济、管理、交通等领域得到广泛应用。经 典排队论中一个随机服务系统有三个构成部分：输入过程，排队规则和服务机构( 也称输 出过程) 。 ( 1 ) 输入过程：可以有各种各样的输入过程，例如 1 ) 定常输入：顾客有规则的等距到达，如每隔时间t 到达一个顾客，此时相继顾客到 达间隔t 的分布函数a ( t ) 为： ， a ( ) ： 1 。孤 ( 1 1 ) 【0 ，t r 产品通过传送带进入包装箱就是这种输入的例子 2 ) 最简单流( 泊松( p o i s s o n ) 流) 输入。 在长为t 的时间内到达k 个顾客的概率p k ( t ) 服从泊松分布，即： 删玎”学，扎， ( 12 ) 其相继顾客到达的时问间隔是独立同负指数分布的，参数即为a ，分布函数为： 4 “) = 1 一e 一“， o ； ( 13 ) 【0 ，t o 其它还有如：爱尔郎输入，超指数输入，一般独立输入，成批到达输入等等 ( 2 ) 排队规则：排队规则大致分为：损失制，等待制和混合制三种。等待制中由服务次 序的不同又可以分出若干种不同的规则，如：先到先服务( f c f i ) ，后到先服务( l c f e ) ，随 机服务，优先权服务等等 ( 3 ) 服务机构：服务台的个数可m 是一个或几个，可以是单个服务，也可以是成批服 务，具体常见的服务分布有： 复旦大学硕士学位论文 。 l 】定长分布：每一顾客的服务时间都是常数 0 为一常数 此外服务分布还有爱尔郎分布，超指数分布 的情形，服务时间依赖于队长的分布等等 t o ； 地； f 1 8 1 a “ 这里 x 表示不大于x 的最大整数部分此假设可称为整取性假设。由于随机变量龟( 。；) 为 指数分布的，因而我们可得到如下命题 命题1 2 1 若随机变量( 莓) 为指数分布的，则【一m ) z i f 1 一“) z ，和，一 1 ) 五1 九( “一a ) 召1 j 在正整数点上的分布皆为几何分布。 证明；( 我们以【( a 一胁) 五】在整数点上的分布为例来证明它) 由最大整数部分的定义 及随机变量五为参数是的指数分布，我们有： ：( e 一南) “( 1 一。一岛) ，：0 ，1 ，2 1 2 l“，o 篇 “h 卜 k 卜 一鳖弑 3 ( 11 0 ) r 1 1 1 1 ( 1 1 2 ) ( 11 3 ) ( m l ，0 ) ，( m 一1 ，) ) 按通常的 o o 00 p ( 。2 ) 一n j 4 。2 0 p ( m 1 1 ( 一2 ) a 麓一l 0 f 1 1 4 1 其中a ：= n 1 】( 衅= n 譬h ) 为( k + 1 ) ( k + 1 ) 方阵 下面我们计算n i ， ( “跫) ，考虑以下三种可能的情况： ( 1 ) = t l ：， 此时，如果k = 0 ，则当+ l q 。 0 ：则无论+ 1 一何值，皆有k + 1 ；k 。 所以： 萌，。= 尸f + - 一 万1 ) = 尸 0 ： 其它 。；。：jp “。一4 曼】：。一。，。；i ；。； ip ( 【( 毗一a ) z d k ) 2 ：o 。：， 2 d - “( 1 0 一胁) 2 k 1 ； i ： lp ；k = 0 其中n ：。击 n ；，h = 砖“( 1 一p ；) k h k 一 z ，l p 复旦大学硕士学位论文 其中p ：= e 砖 相应地将( 1 2 1 ) 式中的胁换为= e 砖即可得到n 譬 定义极限概率： t i ，；i 骢p ( k = i ，k 2 j )( 12 2 ) 其相应的向量为： h ；i ( 7 1 i ，0 ，q ，1 ，7 1 i ，k )( 1 ，2 3 ) 令 k 面= 丌l j( l ，2 4 ) j = 0 则面0 = o ，l ，2 ，8 ) 为状态空间s 的概率分布。 设p d u 流向单一m s 的甲均流速为矿，则： 矿：圭面。；( 1 2 5 )矿= 面；( 1 2 5 ) 且当a 0 是给定的一个标量折扣参数 复旦大学硕士学位论文 引理2 2 1 一个连续时i 司马尔科夫决策问题，具有报酬e 付。e 一r i b ( t ) ，n ( ) d f ) ，。 0 和独立于状态和控制的一致转移率e 等价于一个离散时间的马尔科夫决策问题，具有折 扣因子p = 丽c ，且每阶段报酬为： i ( s ，。) = ：i i 7 ；r ( s ，u ) ( 2 6 ) “十u 、 最优化方程取如下形式： v ( s ) 2 嬲n ) + 壶至躲( n ) v ( i ) 】 ( 2 7 ) 证明：假定对所有的s 和a ，( 。) = e ，且记： t 女：第k 次转移发生的时间( 为方便，t o = 0 ) ； t k = f k t k1第k 个转移的时间间隔； z k = x ( t k ) ：第k 次转移后的状态附t 茎 t 扎x ( t ) = z k ； “k = “( k ) ：第k 次转移的决策控制阿t 女t 0 ，令卢= e e 一) ，利用转移时间间隔的独立性则有： p = e p 7 ) _ 。4 0 c e 一曲d 7 c e dto= 羔 p = e e 7 ) =e 一司1 = ；鬲 一十l 所以 e f 嘛) = e p “( = e e 一) 。= 萨 所以 e 矿“。一t d r ：坠兰迎兰：盟二望! j t t -o 、 7 又固 1 8l 五一2i 干i 。 ( 2l o ) 则由( 28 ) ( 2 9 ) ( 21 0 ) 式可得： e 上8 “坝州妣) 2 壶三矿e 舭t ) ) ，o 卢 0 为连续折扣率。) 我们 应首先利用虚转移的技巧，将转移率一致化为c ( 不依赖于状态) ，然后我们再据引理2 2 1 将问题离散化，依据命题2 2 1 将原问题转化为等价的离散时间马尔科夫决策问题模型后去 给出解答。( 其中定理2 21 保证了最优方程解的存在唯一，进而保证最优决策的存在。) 此时变换后的转移概率和阶段报酬函数分别由( 2 1 2 ) 和( 2 1 4 ) 所确定；最优方程具有 ( 2 7 ) 的形式。 2 2 5 值迭代法简介 值迭代算法又称逐次逼近算法或动态规划算法，是在解决带折扣的马尔科夫决策问题 时用得最为广泛的一种算法。现将其算法步骤简单表述如下四步： 第一步；同定理2 , 2 1 一样记b 为定义在状态集s 上的有界函数空问，选择v o 口 和一个小的正数f 作为停机准则。 笫二步：对状态空间s 中的每一个状态s ，由式v ”1 ( s ) = m a x 。e a ( 。) r ( s ，n ) + 卢；s 阢，如) p ( j ) ) 解得v ”+ 1 ( s ) 。式中的其他字母的意义同( 3 2 ) 式。 第三步：如果 _ | v ”1 ( s ) 一v ”( s ) | f ，则将”“( s ) 作为v ( s ) 的近似转到第四步；否则n 增加1 返回到第二步。 第四步：对状态空间s 中的每一个状态s ，选择决策a 使r ( s ，o ) + 卢琵s p 。， ( 。) v 。( 动 最大。 注：第三步中的 f f 为某一范数。 复旦大学硕士学位论文 2 2 6 几个重要引理 引理2 2 2 任取v o b ，定义算子l 为 l v “( s ) 2 鼢( r ( s ，n ) 十卢三玑，葡州响) s j 令 l v ”( s ) = v n l - 1 ( s ) ，n2 1 则 j 骢( s ) = y ( s ) r 证明见p u t e r m a z l 1 3 1 定理6 3 1 其中b 和范数的意义同值迭代法中的规定一致。 引理2 2 3 如果0s 日 l ，则式： 与式 ( 2 1 6 ) 。m n z 南，( ) ( 2 1 7 ) 等价。 证明：如果q 十o y ( ，由第一式则：y = q4 - 日解之得： = 芒i ，且南2 ( ； 反之，若尚 o 由事件问的独立性和概率运算性质得 而 ( 3 2 ) p 乃 t ) = p 瓦】 t ) p e 2 r ) p l 3 r ) p l 1 r ) p e 2 r 扫 e 3 f ) ( 3 3 ) p 瓦f r ) = e 。”，i = 1 ，2 ，3( 3 4 ) 注意到当前系统中有i + 1 个上网者，令e 1 。，m = 1 ，2 ，i + 1 依次为这i 十1 个上网者离 线时所经历的时间，则e = m i n t 。t 。m = 1 ，2 ，i + 1 ) ，仍然由事件问的独立性，类似 于上述思路得， p 瓦， r ) = 1 ip t , i 。 r ( 3 j ) m ；l 而， p 正l 。 t ) = e ”，m = l ，2 ，i + 1( 3 6 ) 将式( 3 6 ) 代入( 3 5 ) 式得， p t ) = e - ( “1 ) “”( 3 7 ) 同理可得， p e 2 t ) = e 1 ”7( 3 8 ) p 冗3 t ) = e “”( 3 9 ) 将式( 3 4 ) ，( 3 7 ) ，( 3 8 ) ，( 3 9 ) 代入( 3 3 ) 式得， 所以相邻两次转移的时间间隔乃服从负指数分布，且转移率( 参数) 为 证毕 ( 3 儿) 复旦大学硕士学位论文 3 l 3 2 2 状态问的转移概率 转移率是单位时间内的转移次数，据此意义，由状态 转移到状态 的概率为芸等；由状态 转移到状态 的概率为五j 等；由 状态 转移到状态 的概率为芒：* ；由状态 转 移到状态 的概率为i ；由状态 转移到状态 的概率为i 立鼍；由状态 转移到状态 的概率为i 鲁- 。 综上所述，当采取决策a = 1 时，由状态 转移到状态s 的概率为： p ( 8 ) = 警訾， s = “j ，k 1 ，1 77 8 = ，j 1 ：( 3 1 2 、 s = ，七1 ； 8 = 1 = l ，2 ，3 同样道理，由状态 转移到状态s 的概率为 p ( s ) s = ，i l ； 8 = ； f 3 1 3 1 s = ，l ； s = ，f = 1 ，2 ，3 其中， n 也女2 ，1 = 2 p 1 + ( j 十1 ) p 2 + 七p 3 十a l 十a 2 + a 3 。 由状态 转移到状态s 的概率为： p ( s ) = j l 以，k ，3 ，1 s = ，i 1 ； 8 = ，j 卜( 3 1 4 、 s = ； 8 = ，z = 1 2 ，3 其中，p i ，j 】，3 ，l = 2 肛】+ j z 2 + ( 七4 - 1 ) m + a 1 十a 2 + a 3 。 而当i + j + m 且采取决策a = o 时，对任意的e 1 ，一l ，2 ，一2 ：3 ，一3 ) ，由状态 转移到状态s 的概