（计算机应用技术专业论文）呼叫接入控制的学习优化方法.pdf

呼叫接入控制的学习优化方法 摘要 资源管理是网络控制的重要组成部分，特别是随着各种网络新业务的出现， 使得其在网络控制中的地位日益突出。由于网络资源的有限性，如何提高用户 满意度，获得资源的最合适配置，提高自身收益是每个网络运营商追求的目标。 呼叫接入控制( c a l la d m i s s i o nc o n t r o l ，c a c ) 是网络资源管理的重要手段，它 可以通过对不同的类型业务实施不同的接入策略实现资源的合理配置，达到提 高网络收益和用户满意度的目的。论文主要使用强化学习优化方法解决综合业 务网络和蜂窝无线通信网络的接入控制问题。 在综合业务网络中，论文分别研究了固定报酬和累计报酬方式下c a c 问题， 建立了系统的连续时间m a r k o v 决策过程( c t m d p ) 。通过对c a c 问题特征分析， 结合事件驱动优化学习方法的思想，研究了基于后状态q 值更新方式的事件驱 动q 学习。解决了算法在c a c 中的应用问题，实验结果表明该算法能够有效解 决c a c 问题，并且节省存储空间。 在无线蜂窝网络中，论文研究了切换呼叫优先的c a c 问题。针对问题特征， 建立了c t m d p 模型。通过赋予切换呼叫更大的报酬提高切换呼叫的优先级，并 采用事件驱动q 学习算法求解该问题。最后通过仿真实例说明，与总是接受策 略相比，事件驱动q 学习能够提高网络收益，降低切换呼叫掉线率。 关键词：资源管理；呼叫接入控制；事件驱动：连续时间m a r k o v 决策过程； 强化学习 i i l e a r n i n go p t i m i z a t i o na p p r o a c ht o c a l la m d i s s i o nc o n t r o l a b s t r a c t r e s o u r c em a n a g e m e n ti ss i g n i f i c a n ti nt h en e t w o r kc o n t r 0 1 e s p e c i a l l yw i t ht h e e m e r g e n c eo fn e wb u s i n e s sn e t w o r k s ，i th a sb e c o m em o r ep r o m i n e n ti nt h en e t w o r k c o n t r 0 1 a st h en e t w o r kr e s o u r c e sa r el i m i t e d i t se a c hn e t w o r ko p e r a t o r sg o a lt h a t h o wt o i m p r o v ec u s t o m e rs a t i s f a c t i o n ，g e tt h em o s ta p p r o p r i a t ea l l o c a t i o no f r e s o u r c e sa n de n h a n c et h er e v e n u e c a l la d m i s s i o nc o n t r 0 1 ( c a l la d m i s s i o n c o n t r o l ，c a c ) i sa ni m p o r t a n tp a r to ft h em a n a g e m e n to fn e t w o r kr e s o u r c e s w h i c h c a na c h i e v et h er a t i o n a la l l o c a t i o no fr e s o u r c e s ，r e a c ht h eg o a lo fi m p r o v i n gt h e n e t w o r kf o rr e v e n u ea n dc u s t o m e rs a t i s f a c t i o n t h r o u g ha c t u a l i z i n gd i f f e r e n t a d m i s s i o n p o l i c i e s f o rd i f f e r e n t t y p e s o f o p e r a t i o n a li m p l e m e n t a t i o n t h e a d m i s s i o nc o n t r o li ss t u d i e db yr e i n f o r c e m e n tl e a r n i n ga p p r o a c hi nt h ei n t e g r a t e d s e r v i c en e t w o r k sa n dc e l l u l a rw i r e l e s sc o m m u n i c a t i o nn e t w o r k si nt h ep a p e r c a cu n d e rt h ef i x e dr e w a r da n dc u m u l a t i v er e w a r di ss t u d i e di nt h ei n t e g r a t e d s e r v i c e sn e t w o r k s t h es y s t e mi sm o d e la s c o n t i n u o u s t i m em a r k o vd e c i s i o n p r o c e s s ( c t m d p ) c o m b i n e de v e n t d r i v e no p t i m i z a t i o no ft h o u g h ta n dt h e c h a r a c t e r i s t i c so fc a c ，t h ea f t e r s t a t e se v e n t - d r i v e nq l e a r n i n gi sp r o p o s e d ，w h i c h s l o v et h ea p p l i c a t i o no fa l g o r i t h mt oc a c t h ee x p e r i m e n tr e s u l t ss h o wt h a tt h e a l g o r i t h mp r o p o s e dc a ns o l v ea d m i s i o nc o n t r o lp r o b l e me f f e c t i v e l ya n dn e e dl e s s d a t as t o r a g e t h ea d m i s s i o nc o n t r o lp r o b l e mo fh a n d o f fc a l l p r i o r i t yi s s t u d i e di nt h e c e l l u l a rw i r e l e s sc o m m u n i c a t i o n sn e t w o r k s a c c o r d i n gt ot h ep r o b l e md e s c r i p t i o n ， w em o d e li ta sc t m d p t h ep r i o r i t yo fh a n d o f fc a l li si m p r o v e db yg i v i n gi t a g r e a t e rr e w a r d ，a n dw eu s ee v e n t - d r i v e nql e a r n i n ga l g o r i t h mt os o l v et h ep r o b l e m f i n a l l y ，s i m u l a t i o ne x a m p l e si l l u s t r a t et h a t ，c o m p a r e dt o a l w a y sa c c e p tp o l i c y ， t h ee v e n t _ d r i v e nql e a r n i n gc a nh e i g h t e np r o f i ta n dl o w e rh a n d o f fc a l l d r o p p i n g p r o b a b i l i t y k e y w o r d s ：r e s o u r c em a n a g e m e n t ；c a l la d m i s s i o nc o n t r o l ；c o n t i n u n o u s t i m e m a r k o vd e c i s i o np r o c e s s ；e v e n td r i v e n ；r e i n f o r c e m e n tl e a r n i n g i l i 插图清单 图1 - 1d e d s 研究的范畴7 图1 - 2 强化学习的一般结构9 图3 - 1 后状态q 值更新过程2 2 图3 2 两种q 学习的平均报酬变化曲线图2 4 图3 3c = ( 4 ，1 5 ，1 2 ) 时，两种q 学习的平均报酬变化图2 5 图3 4 旯= ( 2 5 ，2 5 ，2 0 ) 时，两种q 学习的平均报酬变化图2 5 图3 5 元= ( 3 0 ，2 0 ，2 5 ) 时，两种q 学习的平均报酬变化图2 9 图3 6 旯= ( 2 5 ，1 5 ，2 o ) 时，两种q 学习的平均报酬变化图2 9 图3 7 旯= ( 2 5 ，2 5 ，2 0 ) 时，两种q 学习的平均报酬变化图3 0 图4 - 1 蜂窝小区网络通信模型图3 4 图4 - 2 长期平均报酬变化图3 7 图4 - 31 类业务切换呼叫掉线率变化图3 8 图4 - 42 类业务切换呼叫掉线率变化图3 8 图4 52 = 3 。l ，5 1 ，8 1 时，事件驱动q 学习的平均报酬学习值变化图3 9 图4 6 兄= 3 8 时，事件驱动q 学习的平均报酬变化图3 9 v i i 表格清单 各类业务参数2 4 不同策略的长期平均报酬和各类业务拒绝率2 6 不同的l 类业务报酬对应各类业务的拒绝率2 6 各类业务参数2 8 五= ( 3 0 ，2 0 ，2 5 ) 时，两种q 学习的各性能参数表3 0 z = ( 3 0 ，2 0 ，2 5 ) 时，不同策略的长期平均报酬和各类业务拒绝率3 1 旯= ( 2 5 ，1 5 ，2 0 ) 时，不同策略的长期平均报酬和各类业务拒绝率3 1 旯= ( 2 5 ，2 5 ，2 0 ) 时，不同策略的长期平均报酬和各类业务拒绝率3 1 不同的2 类业务报酬率对应各类业务拒绝率3 1 各类业务相关参数3 7 v i i i 1 2 3 4 5 6 7 8 9 l 一 一 一 一 一 一 一 一 一 一 3 3 3 3 3 3 3 3 3 4 表表表表表表表表表表 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所 知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得金目巴王些太堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签字嘲，j 为签字日期圳。年中月；o 日 学位论文版权使用授权书 本学位论文作者完全了解金目巴工些太堂有关保留、使用学位论文的规定，有权保留并向 国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人授权金月曼王些太 ! l 可以将学位论文的全部或部分论文内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名：仁何澎 导师签名： 签字日期：26 晖午月乡疹日 签字日期：) o o 年乒月多口日 学位论文作者毕业后去向： 工作单位： 通讯地址： 电话： 邮编： 致谢 本文是在唐昊教授的指导下完成的，从论文的选题、研究方案的制定以及论 文的写作，唐老师一直给予我耐心指导、热心帮助和严格要求。他渊博的专业知识， 严谨的治学作风，敏锐的学术思想，诲人不倦的高尚师德，积极进取的科研精 神，朴实无华、平易近人的人格魅力深深的感染和激励着我。不仅使我掌握了 基本的研究方法和专业知识，还使我明白了很多为人处世的道理。三年以来， 唐老师不仅在学业上给以精心的指导，同时还在思想、生活上给我以无微不至 的关怀，在此谨向唐老师致以崇高的敬意和衷心的感谢。 特别要对韩江洪教授及其领导下的分布式控制实验室的老师们表示最诚挚 的谢意，在近三年的研究生学习期间，他们为我的研究和论文工作创造了有利 的科研环境和学术氛围，提出了多方面的宝贵建议。感谢实验室的周雷老师和 程文娟老师对我的热心指导和帮助。 感谢实验室的万海峰、岳峰、王金田、孔风、张晓艳、毛沙、郭一明、任 玲、穆自立、柴雪霞、刘文静等同学，感谢他们在课题研究中给予我的启示和 帮助。 感谢室友李鸿明和张敏生，是他们和我共同维系着彼此之间兄弟般的感情，维系 着寝室那份家的融洽，感谢他们对我支持和鼓舞。 感谢计算机学院和学校有关单位的领导、老师的关怀和支持。感谢所有帮助过我 的人们。 最后特别感谢我的家人，感谢他们对我始终如一的关怀和支持。 i v 作者任付彪 2 0 1 0 年4 月 第一章绪论 本章简要介绍网络资源管理、呼叫接入控$ 1 j ( c a l la d m i s s i o nc o n t r o l ，c a c ) 、 离散事件动态系统( d i s c r e t ee v e n td y n a m i cs y s t e m ，d e d s ) 、强化学习 ( r e i n f o r c e m e n tl e a r n i n g ，r l ) 的基本知识和相关研究。 1 1 研究的目的和意义 近年来，随着各种网络技术的迅速发展，网络用户及网络使用量呈现高速 增长趋势，网络的快速发展对传统资源分配与优化问题提出新的挑战。传统的 网络资源分配策略研究没有考虑服务满意度对资源优化分配所产生的影响，而 单纯地以提高资源利用率为目标，资源利用越充分，表示分配算法的效率越高。 随着网络运作呈现出商业化特性，网络服务出现多样化需求，“服务 被突出到 更为显著的位置。新的网络发展背景为网络资源优化分配策略问题研究赋予了 新的内涵。资源利用率已不再是资源分配唯一的优化目标，用户满足度、资源 适度分配，系统效率等要素在优化分配过程中也须考虑。 资源分配的首要问题是按什么标准进行性能测度。测度的表征从不同的角 度出发，会有不同的含义。目前，性能测度主要有三个方面： 1 ) 网络资源利用率：就网络资源本身而言，资源利用率无疑是资源分配性 能的最重要测度。 2 ) 用户满意度：对于网络用户而言，用户的服务质量( q u a l i t yo fs e r v i c e ， q o s ) 必须和其支付的报酬相关。 3 ) 网络运营商利益：对于网络运营商而言，他们关注如何使系统用户满意 度最大，如何获得整体资源的合适配置度，以提高自身收益。 一个有效的资源分配策略需要实现资源的最合适配置，提高服务商的收益 和用户的满意度，因此，探索资源分配策略具有十分重要的意义。呼叫接入控 制是网络资源管理的重要手段，它可以通过对不同的类型业务实施不同的接入 策略实现资源的合理配置，达到提高网络收益和用户满意度的目的。本文主要 研究呼叫接入控制问题，目的是寻找最优的资源分配策略。 1 2 网络资源管理概述 资源管理是网络控制问题的重要组成部分，它包括有线网络资源管理和无 线网络资源管理。有线网络资源管理的目标是实现网络的可靠、经济、正常的 运用，最大限度的利用网络资源，提高网络运营质量和效率，为用户提供良好 的服务。目前，有线网络资源管理的各项技术已经十分成熟，因此它的研究理 论和方法可以作为无线网络资源管理的参考。 随着无线通信网络的发展和移动用户的增加，无线资源管理( r a d i o r e s o u r c em a n a g e m e n t ，r r m ) 成为当前资源管理研究的热点。无限资源主要包 括码字、功率、频率和时隙，r r m 就是通过合理地动态分配这些无线资源，有 效地降低系统的干扰，提高系统的容量，保证通信链路的质量。r r m 负责空中 接1 2 1 资源的利用，当每一个移动用户进入网络时，网络需要为其分配适当的基 站、信道、发射功率，以实现满足用户的q o s 要求的同时，使具有固定硬件设 备的无限网络获得最大的容量。 无线网络是一个开放的、实时变化的网络， 用户随时都会发起或中断呼叫，并在网络内部移动，因此，r r m 要求实时且充 分的利用网络内部的资源。其基本出发点是在网内话务量分布不均匀，且信道 的状态因信号衰落和干扰而起伏变化状况下，设法灵活地分配和及时调整可用 资源，即资源分配。无线资源管理手段主要包括接入控制、切换控制、拥塞控 制、功率控制、分组调度、以及信道分配管理等，下面给出这些控制的简要介 绍。 接入控制：接入控制主要是负责决定新的呼叫请求是否接入系统。当有新 用户接入请求时，接入控制首先判断是否接受用户请求，当接收请求时，需要 执行接入控制过程。接入控制的目的是在有限系统容量的基础上，以不牺牲已 有连接的服务自量为前提，尽可能多的对新到达连接请求予以接纳的决策问题。 切换控制：负责处理用户的移动性，当移动用户从一个小区进入另一个小 区时，必然发生切换。切换控制就是运用一定的策略，保证用户越区切换或系 统间切换时通话的连接不间断，并且使通信质量达到预定的q o s 要求。现代移 动通信中切换包括硬切换和软切换两种操作，硬切换指移动终端被连接到不同 的通信系统、不同频率的频率分配或不同的空中接口特性时，必须断掉原来的 无线信道，才能使用新小区无线信道进行通信。软切换指移动终端连接到另 个小区时，不需要中断当前服务小区的业务信道，当呼叫处于两个( 或两个以 上) 小区边缘时，同时接受两个小区的服务，当某个新小区的信号大于旧小区 信号且稳定时，才发生切换。 拥塞控制：主要负责连接网络的负荷信息，并把信息提供给其他模块。当 网络出现拥塞时，它以目标方式在给定的限制条件范围内维持网络无线资源的 使用。 功率控制：主要作用是在维持链路通信质量的前提下，尽可能少的消耗资 源，使空中接口的干扰电平维持最小，从而保证移动用户的q o s 要求，它能减 少干扰并增加系统容量； 分组调度控制：主要作用是使各分组用户合理地使用系统的可用资源，为 各个用户分配数据速率和分组长度。具体的调度速率由网络负荷情况决定。 信道分配管理：通过固定分配或者是动态分配，以最有效的方式利用可用 的无线频率资源，把信道分配到系统的小区级别或是分层级别上。 1 3呼叫接入控制简介 1 3 1 概述 c a c 是网络资源管理的重要手段，是解决用户q o s 和提高网络收益的关 键技术【l 。3 】。c a c 负责用户的接入请求允许判断，是接入技术的功能实体。c a c 在有线网络就已经出现，它最早是由a t m 网络提出的，a t m 对c a c 的定义为： 对于一个已知呼叫连接请求，根据其业务特征、要求的服务质量和网络资源的 当前状况进行比较，决定是否接纳一个新连接请求。c a c 的目标是在保障已有 接纳连接的q o s 的前提下，接受尽可能多的新连接，充分利用网络资源。c a c 接受一个新呼叫的判断标准为以下两个：首先新呼叫是否会影响已在线呼叫的 服务质量，其次为网络能否满足新呼叫的q o s 要求。只有网络能满足呼叫的服 务质量要求时，呼叫请求才有可能被接受，否则拒绝呼叫请求。c a c 需要解决 的基本问题是，如何准确的估计已有网络资源使用量和如何有效地结合呼叫要 求来判断能否接受呼叫。 1 3 2 主要方案 c a c 方案需要综合考虑服务商的收益、用户的满意度和网络资源利用率，因此， 设计一个有效的c a c 方案不仅充满挑战性，而且具有重要意义，一个有效的c a c 方案 通常需要具备以下几点： 1 ) 能够为用户提供q o s 保证。无论对于新呼叫还是已经存在的呼叫，网络 应能保证这些呼叫的持续性。 2 ) 具备良好的适应能力。新业务类型的不断增加必然会导致用户对网络的 需求变得的更加复杂，一个有效的的c a c 方案应容易调节并适应这些变化。 3 ) 具有设计简单和处理速度快的特点。一个有效的c a c 方案应保证系统的 软硬件设计尽量简单，并尽可能减少处理时间，以提高系统的有效性，从而保 证对不同用户的各种需求做出及时的反应。 c a c 在有线网络就已经出现，有线网络的c a c 方案已经十分成熟，下面 简要介绍几种常用的方案。 1 ) 基于测量速率的方案 该方案的原理是：如果已存在连接流的带宽和新请求连接的速率之和小于 网络为流分配的带宽，则接纳呼叫，否则拒绝呼叫， 2 ) 基于接纳窗口的方案 该方案主要是计算出一个流的接纳控制区，使得资源利用率和丢包率比值 最大，只有在接纳区域内的流才会被接纳。 3 ) 基于等效容量的方案 等效容量是指某一类连接的速率累加的估计值，并假设实际的速率会以一 定概率超过该估计值，基于等效容量、新流的峰值以及配给流的带宽容量，给 3 出接纳控制。p e t e rm a r c a c h 等利用等效容量方案，研究了单节点收益最大化的 c a c 问题。文章把问题建模为m d p 模型，研究了问题基于神经元动态规划的 优化求解算法，并分析了随机策略迭代算法和t d ( 0 ) 算法的优缺点，指出学习 算法探索状态空间的重要性【4 】。周亚平等将m d p 与性能势相结合，给出该问题 状态相关的策略迭代算法，并且通过实际算例证实了基于状态的优化策略要优 于基于节点占用带宽的优化策略【5 】。 随着无线移动通信的飞速发展，移动网络接入控制技术成为当前研究的重 点。在无线通信网络中，每类业务的呼叫可以分为两种：新呼叫和切换呼叫。 新呼叫指用户需要使用网络时，向小区基站发射的呼叫，切换呼叫指正在通信 的移动用户因需要转移到新的小区基站而发起的呼叫。对无线网络用户来说， 一个呼叫在连接过程中被中断比接入时受阻更加令人难以接受，因此，c a c 通 常给予切换呼叫更高的优先级。无线网络c a c 的设计方案包括以下几种口 3 l 。 1 ) 考虑业务之间优先级的呼叫接入控制 在无线网络中存在多种通信业务，不同的业务具有不同的特征，例如实时 业务对传输特性的要求比非实时业务高，因此在系统中其优先级别也比比非实 时业务高，c a c 方案可以把考虑的重点放在这些业务的优先级上。在业务优先 级作为考虑重点时，为了保证高优先级别能够获得更好的通信质量，系统一般 会为它们分配一定的专门信道，如在系统中分配一定的信道给实时业务专用， 但当这些信道空闲时，可以被非实时业务用户使用；同时实际业务在需要时可 以随时抢占这些被非实时业务占用的信道【6 ，1 7 1 。 2 ) 考虑切换呼叫优先的呼叫接入控制 前面提到，与新呼叫受阻相比，用户更难以接受切换呼叫的中断，因此很 多c a c 方案考虑切换呼叫的特殊性，旨在减少切换呼叫掉线率。目前采用的方 法主要包括信道保护方法和切换排队方法。 信道保护方法指为已经接纳新呼叫小区的所有相邻小区都预留信道，以备 将来此新呼叫需要切换的时候使用捧】。然而这种预留方法为了保证切换呼叫的 资源分配，预留了过多的信道，不便于实际应用。为了使预留信道数更为合理， 人们对此做了大量研究，提出了多种预留方法，主要包括：a 、利用系统过去的 统计特性来决定预留的保护信道数【9 】，b 、根据正在通信的本地和相邻小区的用 户数及其位置自适应调整预留给切换的保护信道数【l 们。 切换排队方法主要分为三种情况】：a 、当系统有足够的空间时，接纳所 有的呼叫；b 、当系统中资源不足时，新呼叫被阻止，切换呼叫进行排队等候； c 、当有空闲资源时，队列中的切换呼叫得到服务。 3 ) 基于用户数量的呼叫接入控制 系统可以考虑本小区和相邻小区的用户数量，本小区用户数量反映小区当 前状态，邻居小区的用户数量反映切换呼叫的可能性，总切换到达率与邻居小 4 区用户数量成正比，邻居小区的数量可以考虑两个或多个。基于用户数的c a c 方案根据确定接纳用户阈值的方式不同分为两种：基于爱尔兰b 公式确定阈值 和基于接收功率确定阈值。根据爱尔兰b 公式，将阻塞概率取为最大允许值， 求出的用户数作为可接纳各类用户数门限，接纳区域为各类业务用户数之和小 于等于此门限。 4 ) 最优或近似最优的呼叫接入控制 最优的c a c 方案的优化目标是，在满足服务质量要求下，最大化资源利 用率。k w o n 等给出了蜂窝无线通信网络c a c 问题的s m d p 模型，并通过线性 规划算法求解最优策略，在满足服务质量约束要求的同时，实现最大化资源利 用率引。然而，随着无线网络小区容量增大和业务类型不断增多时，系统的状 态空间和决策空间也会变得很大，状态空间和决策空间会呈指数增加，求解最 优策略会变得十分复杂，甚至无法求解。另外，线性规划算法需要确切的系统 参数( 状态转移概率矩阵) ，对系统模型要求较高，不利于系统的在线学习优化 和实际应用。智能控制方法近年来得到的快速的发展，它通过模拟人类大脑思 维实现算法控制。主要包括基于进化机制的控制、模糊控制，神经网络、专家 控制等，不少研究者把这些智能方法应用到c a c 的控制当中，取得了一些研究 成果1 3 , 1 4 】。 5 1 基于报酬的c a c 方案 在多业务的无线网络中，不同业务接入系统时所付报酬存在差别。对系统 来说，它总是希望获得更多的收益，因此优化无线网络的报酬在c a c 起着重要 的作用，在多业务的无线网络中，将c a c 方案优化的目标定为报酬函数是常 用的方法，这类c a c 方案通常可以转化为求解最优化问题【l5 。 】。y uf e i 将报 酬定义为资源利用率，并把适应多媒体的q o s 保证问题转化为m a r k o v 决策过 程问题，给出了一种基于q 学习的带宽配置策略的优化算法。该算法能够实现 在线优化，并且不依赖于参数系统，得到的是对随机策略的近似值，取得了较 大的一致化报酬。对于平均准则的优化，该算法具有较大的计算复杂度i l 引。 s e n o u c i 采用q 学习求解最优c a c 策略，其报酬函数为实际的报酬，实验结果 证实q 学习算法比预留带宽方法更有效【1 6 】。s i l v a n o 提出一种新的报酬函数定 义，报酬函数综合了到达率、离开率和环境报酬，给出了一种基于模型的强化 学习接入控制算法【l7 1 。w e l o n g 则利用预留带宽方法研究最优化报酬c a c 问题 【l 引，并证实当报酬函数定义满足某些特性时，最优策略是一个可控的有限策略， 由于报酬函数定义时需要满足一定特性，其求解过程复杂。 6 ) 基于公平性的c a c 设计方案 高优先级业务一般比低优先级用户更易接入，但在比较极端的情况下，高 优先级业务过多时，系统为了接入高优先级业务，就会导致低优先级业务的阻 塞，长期下去，低优先级业务就很难接入，其阻塞率急剧增大，因此各业务接 入的公平性就显得十分重要，公平性c a c 方案目标就是提升各类业务之间资源 使用的公平性。比较常用公平性方法是：当某个业务过载时( 拒绝率较高) 那 就提高该类业务的优先级f 1 9 】。 7 ) 利用预测信息的呼叫接入控制 随着无线网络技术的发展，小区能够给提供一些关于即将到来呼叫请求的 预测信息，因此可以利用用户移动的预测信息来合理地调整保护信道数。如果 能够准确的预测用户的移动信息，则可以在用户可能到达的目的地预留保护信 道，而不是所有的小区，显然，这样将大大提高资源的利用率，同时可以减少 新呼叫的阻塞率。j o r g e 利用切换呼叫预测信息求解c a c 问题【2 0 1 ，给出该问题 的动态规划和强化学习求解算法，算法实现了资源的合理配置，有效的减少了 用户的c d p 和c b p ，显示了利用预测信息解决c a c 问题的优势。部分研究者 考虑多个小区c a c 的情景【2 1 , 2 2 】。这其实是为了提供更准确的预测信息，多个 小区交互信息，必然提高了预测的准确性。k w o n 在研究单个小区情景的基础 上，给出了多个小区c a c 接入问题的线性规划算法【2 1 1 。c h a oc h i c h a o 给出两 个小区的c a c 问题模型，讨论了该问题的策略迭代求解算法【22 1 。同时考虑多 个小区的c a c 问题时，系统十分复杂，问题难以求解，因此，关于多小区c a c 问题研究相对较少。 综上所述，应用需求日益多样化和各种新技术的发展不断推动着c a c 向智 能化、最优化及目标多元化方向发展。因此，如何解决综合考虑服务商利益和 用户的q o s 需求的接纳问题是当前c a c 发展的重要趋势之一。 1 4离散事件动态系统及强化学习 1 4 1 离散事件动态系统 粗略的说，d e d s 是指系统状态的变化由离散事件触发而引起的一类动态 系统。不同于传统的一些控制系统，该类系统演化过程不能由通常物理学定律 来描述，在d e d s 中，系统状态的演化是受事件驱动的，状态的变化方式是跳 跃式的，而时间与状态空间都具有明显的非线性性。离散由哈佛大学最早是由 何毓琦等学者在上世纪八十年代前后正式提出的【23 1 ，经过最近二三十年的快速 发展，d e d s 的性能分析和优化已经成为系统和控制理论中的一个新兴分支与 前沿方向。 d e d s 主要是复杂的人造系统，从原理上说，d e d s 属于运筹学( o p e r a t i o n r e s e a r c h ) 的范畴。然而，d e d s 发展至今已从控制论和系统论中吸取了许多有 益的养分。特别是由于d e d s 的人造系统的特征，人工智能在d e d s 的发展也 起到了相当大的作用。另外，计算机技术的发展，极大的拓宽了d e d s 的研究 视野，为d e d s 的发展带来了新的活力。目前，d e d s 的理论研究已经涉及人 工智能、运筹学、系统理论、控制论和计算机科学等多个学科。d e d s 的研究 6 范畴如图1 1 所示。d e d s 在当今高速发展的科技社会中有着十分广泛应用背 景，比如通讯网络、计算机系统、自动生产线、柔性加工系统、计算机集成制 造系统、军事指挥等。正是基于对这类人造系统的行为和性能研究的需要，推 动着d e d s 理论的形成和飞速发展【2 3 圳】。 图卜1d e d s 研究的范畴 在d e d s 中，对系统行为演化过程起决定作用的是一系列的离散事件，系 统行为可以用其演化过程的状态序列和事件序列来刻画。离散事件的发生，触 发系统的状态变化，在d e d s 的状态发生变化的同时，d e d s 将按照系统的运 行规则响应这一事件，进而又引发其他离散事件的发生。例如，在通信网络的 c a c 系统中，呼叫到达、呼叫离开可以认为是两个离散事件，事件的发生会引 起系统状态的变化，状态的变化会影响事件的发生。 由上可见，d e d s 的主要特征表现为【3 2 】： 1 ) 系统状态由一批符号和离散变量特征，状态只能在离散事件点上瞬时发 生变动。 2 ) 离散事件发生具有异步性，事件或过程的具有并发性。 3 ) 状态或时间的发生具有一定的序列性 4 ) 离散事件是研究d e d s 的主体。 5 ) 状态演化具有不确定性。 d e d s 研究中最基本的一个问题是系统的建模，不同的模型和工具通过对 不同层次、侧面( 视图) 的系统行为进行描述、分析和调控，从而形成了一套模 型体系以及用它们来解决实际问题的方法。根据所用模型和采用工具的不同， d e d s 的研究领域大体可分三层，即逻辑层次、代数层次和性能统计层次【33 1 。 d e d s 的不同层次采用不同的方法和模型，逻辑层次研究中的主要方法有自动 机和形式语言、p e t r i 网、有限域代数等【3 4 37 1 ，代数层次的主要研究方法有极大 极小代数、有限递归过程、通讯序贯过程等【3 8 , 3 9 】。统计性能层次中的研究主要 采用的模型有m a r k o v 模型、半m a r k o v 模型、广义半m a r k o v 模型、各种排队 网络和仿真方法等。目前m d p s m d p 的优化理论及应用研究己成为当前的研 究热点之一，国内外学者已做出了一些重要成果 3 0 , 3 3 , 4 0 - 4 7 】。 m d p 是研究m a r k o v 型随机系统的最优序贯决策问题的有效方法【30 1 ，所谓 序贯决策是指在一系列相继的或连续的决策时刻点上作出决策( 行动) ，在每个 决策时刻点，决策者根据观察到的状态，从候选的若干个决策中选择一个决策 并付诸实施于系统，这时决策者从系统中获得一定的报酬( 或费用) ，同时实施 的决策控制将会影响系统的转移概率，从而影响系统在下一决策时刻点所处的 状态，也就是系统在下一个决策时刻点处的状态是随机的。在这一新的决策时 刻点上，决策者要观察系统所处的新的状态( 即收集新的信息) 并采取新的策略， 如此按上述步骤一步步进行下去。需要指出的是，在每一决策时刻采取的决策 不仅会影响当前决策时刻的系统运行和报酬( 代价) ，而且都会影响下一决策时 刻系统的运行和保持( 代价) 。因此这类决策的中心问题是确定每个时刻如何选 择行动，以使系统运行的全过程在某种意义下达到最优。m d p 优化控制方法主 要包括两大类，一类是基于理论计算的优化方法，这类优化方法需要具体模型 参数，常用的算法有线性规划( l p ) 、梯度方法、策略迭代( p i ) 和数值迭代 ( v i ) 等。另一类是基于仿真的优化方法，这类方法通过仿真或在线学习的方 法获得逼近策略，适合于模型参数未知或不全知的情况。常用的仿真学习算法 有强化学习( r e i n f o r c e m e n tl e a r n i n g ，简称r l ) 和神经元动态规划 ( n e u r o - d y n a m i cp r o g r a m m i n g ，简称n d p ) 。 s m d p 是研究和控制m a r k o v 随机系统的一种数学模型1 4 2 , 4 3 j ，它根据 m a r k o v 过程的状态，按照一定的策略从其可行控制集合中选取最佳行动，从而 可以使系统在某种准则下的性能达到最优。上世纪九十年代，曹希仁教授和陈 翰馥院士通过单样本轨道的摄动分析( p a ) ，提出了m a r k o v 性能势理论【44 | ，并 揭示了m a r k o v 性能势、无穷小摄动分析( i p a ) 与m d p 三者之间的联系，并 给出了m d p 在有限行动集下基于性能式的优化理论和算法。在此基础上，曹 希仁教授提出了s m d p 性能势的概念【45 1 。性能势理论为m d p 的优化提供了一 个统一的框架。性能势可以看成是泊松方程的解，本质上同差分代价( d i f f e r e n c e c o s t ) 、相对代价( r e l a t i v ec o s t ) 或b i a s 概念相刚4 6 1 。运用性能势理论，从泊松 方程入手，可以在较少的假设条件下建立起m d p 基于性能势的最优性原理和 最优性方程，且容易证明其最优解的存在性定理。因此，在系统模型参数己知 时，可以用基于性能势理论的梯度方法或策略迭代、数值迭代算法来进行m d p 数值求解1 3 引。另外，性能势也可以定义在一条样本轨道上，并通过仿真或在线 学习一条样本轨道来估计。以此为基础，可以建立基于样本轨道的仿真和在线 优化算法 4 7 1 。这种算法适用于系统模型未知的问题的优化求解。 通信网络中的c a c 系统就是一个典型的离散事件动态系统，因此可以通过 建立它的m d p s m d p 模型，然后采用理论计算如策略迭代、数值迭代、线性规划 等算法对其进行优化。但是由于c a c 系统的状态空间较为复杂，理论计算在实 际中往往不可行，本文重点研究通信网络系统c a c 问题基于强化学习的仿真优 化方法。 1 4 2 强化学习 学习是人类获取知识的主要形式，也是人类具有智能的显著标志，是人类 提高智能水平的基本途径。关于学习，至今没有一个精确的、能被公认的定义。 学习这一概念在日常生活中使用及其广泛，非常通俗，进行这一研究的人们可 以从不同的学科角度、不同的理解来表示学习。根据反馈的不同，学习技术可 以分为监督学习( s u p e r v i s e dl e a r n i n g ) 、非监督学习( u n s u p e r v i s e dl e a r n i n g ) 和强化学习。 强化学习( 又称在激励学习) 是一种重要的机器学习方法，是由著名学者 m i n s k y 在上世纪五十年代提出的钉，目前，它在智能控制、机器人及分析预测 等领域有许多应用。与非监督学习和监督学习相比，强化学习的优势在于接受 环境的反馈信息不直接依赖于指导，因而具有更灵敏的效果。在现实生活中许 多复杂非线性实际系统难以设计出可计算学习，因此要求智能系统能够通过试 错( t r i a l a n d e r r o r ) 的方式从动态环境中在线学习以寻求解决问题的方法。这 类通过试错进行学习的问题统称为强化学习问题，解决这类问题的技术称为强 化学习技。强化学习是一种学习技术同时也是一类方法，是解决一类问题的方 法。 强化学习思想来源于人类对动物学习过程的长期观察。强化学习的研究历 史主要可划分为两个阶段：第一阶段是5 0 年代至6 0 年代，为强化学习的形成 阶段：第二个阶段是8 0 年代后，为强化学习的发展阶段。在六七十年代，强化 学习研究进展比较缓慢，对强化学习的研究与监督学习混淆在一起，强化学习 的研究进入低谷。进入8 0 年代后，随着人们对人工神经网络的研究不断地取得 进展，以及计算机技术的进步，人们对强化学习的研究又出现了高潮，逐渐成 为机器学习研究中活跃领域。 图卜2 强化学习的一般结构 9 所谓强化学习就是指从环境到行动映射的学习，以使行动回报最大化或代 价最小化【49 1 。在标准的强化学习问题中，学习主体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 产生这个行为策略的趋势便减弱。强化学习的一般结构如图1 2 。 强化学习一般都是以m d p 模型为依据，m d p 模型具有无记忆性，即当前 状态向下一状态转移的概率和奖赏值只取决于当前状态和选择的行动，而与历 史状态和历史行动无关。因此强化学习算法分为两类：基于模型法( m o d e l 。b a s e d ) 和无模型法( m o d e l f r e e ) 。模型相关的强化算法是直接计算最优策略，模型无关 强化学习算法是先进行模型的学习，再根据模型知识推导最优策略。研究者们 提出了许多强化学习算法，从最初的t d 算法开始，强化学习算法的研究走过 了漫长的道路。迄今为止，较有影响的强化学习算法有如下几种。 1 ) 动态规划 动态规划( d y n a m i cp r o g r a m m i n g ，d p ) 算法是所有强化学习算法的理论 基础，但是由于其需要确切的系统参数，而且必须对整个状态集进行操作和迭 代，计算量大，不适用于大规模随机决策问题。 2 ) 蒙特卡罗算法 m o n t e c a r l o 算法无需环境模型，其直接与环境进行交互，能够利用仿真或 者与环境进行交互的试验数据进行学习。m o n t e c a r l o 算法只需对部分状态集进 行操作，并应用性能评价函数进行策略改进，算法的实现简单有效。其性能评 价函数如下 y ( s ) = y ( s ) + r ( g y ( s ) ) 其中z ( s ) 为状态s 时的性能评价函数，y 为学习步长，g 为奖惩。该算法缺点是 要等到一个试验( 训练) 过程结束，获得全部奖惩后，才能够进行评价函数的 迭代。 3 ) t d 算法 一步t d ( t e m p o r a ld i f f e r e n c e ) 算法，即t d ( 0 ) 算法，是一种自适应的策略 迭代算法，又名自适应启发批评算法( a d a p t i v eh e u r i s t i cc r i t i c ，a h c ) 。该算法 由s u t t o n 于1 9 8 8 年提出【4 9 1 ，所谓一步t d 算法，是指a g e n t 获得的瞬时奖赏 值仅回退一步，也就是说只是修改了相邻状态的估计值。t d ( o ) 算法如下： y ( s ) = y ( s ) + r ( g 一口y ( j ) 一矿 ) ) 其中v ( s ) 指在状态j 下获得的奖赏和，v ( s ) 指状态转