（计算机科学与技术专业论文）cdma前向链路速率分配研究及网格实现.pdf

c d 帆前向链路速率分配研究及网格实现 摘要 本文根据c d m a 2 0 0 0 和w c d m a 前向链路的数据传输特点，抽 象出一个理论模型，并研究一种递阶s i r 分配和速率分配算法，用于 前向链路的大规模数据传输。其中数据用户的q o s 通过时延、误码率 以及描述吞吐量和数据用户公平性的效用函数来表示。算法采用大系 统递阶分层控制结构实现，移动台根据用户特定的本地信息独立地调 整s i r 目标，而基站根据来自各移动台有限的反馈信息，同时调整各 用户的数据速率。 仿真结果对比了单用户与多用户系统总的吞吐量，证明时分调度 能够最大限度的提高带宽利用率，但是在链路建立、拆除方面花费了 更多时间，可能导致较大时延。码分调度则刚好相反，节省了链路建 立、拆除花费，但是带宽利用率降低。 算法已应用于移动通信网络优化网格n o p g r i d 的速率分配子系 统中。借助网格环境提供的并行编程接口和工作流引擎，实现了任务 并行和分层控制。 关键词码分多址速率分配递阶控制网格 r e s e a r c ho nr a t ea s s i g n m e n to ft h ec d m a f o r w a r dl i n ka n di t si m p l e m e n t a t i o no n g r i de n v i r o n m e n t i nm i sp 印e r ，w ea b s t r a c tat h e o r e t i c a lm o d e la c c o r d i n gt ot h e c h a r a c t e r i s t i c so fd a t at r a n s m i s s i o n ，a n ds t u d yah i e r a r c h i c a ls i ra n dr a t e a s s i g n m e n ta l g o r i t h m t h ea l g o r i t h mc a nb eu s e di nt h el a r g es c a l eo f d a 诅t r a n s m i s s i o no nt h ef o n v a r dl i n k t h eq o sf o rd a 诅u s e r si ss p e c i f i e d b yd e l a ya n de r r o rr a t ec o n s t m i n t sa sw e l la su t i l i t ym n c t i o n sw h i c h r e p r e s e n tt h et 王1 r o u g h p u ta n df a i m e s s 锄o n gd a t au s e r s t h ea l g o r i t l l l l li s i m p l e m e n t e du s i n g t h eh i e r a r c h i c a lc o n t r o ls t n l c t u r eo fl a 唱es c a l e s y s t e m s m o b i l e si n d e p e n d e n t l ya d j u s tt h es i rt a r g e t sa c c o r d i n gt ot h e u s e r ss p e c i f i cl o c a l i n f o 姗a t i o n ，a n dm eb a s es t a t i o na d j u s tt h ed a t ar a t e s j o i n t l yf o ra l lt h cd a t au s e r sb a s e do nl i m i t e df e e d b a c km f o n n a t i o n 行o m t h em o b i l e s t h es i m u l a t i o nr e s u l t ss h o wt h ec o n t r a s t so ft h es i n g i e u s e rs y s t e m t h r o u 曲p ma 1 1 dt h em u l t i - u s e r ss y s t e mt i l r o u 曲p u t i tp r o v e st h a tt 1 1 et i m e d i v i s i o nd i s p a t c h i n gc a n m a x i m a l l yi n c r e a s et h ea v a i l a b i l i t yr a t i oo fb a l l d w i d t h ，b u ti tw i l ls p e n tm o r et i m eo ne s t a b l i s h i n ga i l dd e s t r o y i n g1 i n k s ， w h i c hm a yc a u s es o m em o r ed e l a y 0 nm eo p p o s i t e ，t h ec o d ed i v i s i o n d i s p a t c h i n gs a v e st h et i m ef o re s t a b l i s h i n ga n dd e s t r o y i n gl i n k s ，b u th a sa l o w e ra v a i l a b i l i t yr a t i oo fb a n dw i d t h t h ea l g o r i t h mh a sb e e n 印p l i e dt ot h er a t ea s s i g n i n gs u b s y s t e mo f n o p g r i d ( g r i do fm o b i l e1 e l e c o m m u n i c a t i o n sn e t w o r k0 p t i m i z i n g ) t h et a s k sp a r a l l e l i z a t i o na r l dh i e r a r c h i c a lc 衄t r o la r ei m p l e m e n t e du s i n g t h ep a r a l l e lp r o g r a m m i n gi n t e r f a c ea n dt l l ew o r k n o w e n g i n e ，w h i c ha r e p r o v i d e db yt h eg r i dp l a t f o 蛳 k e yw o r d s ： c d m a ，r a t ea s s i g n m e n t ，b i e r a r c h i c a ic o n t r o i ，g r i d i i 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 3 逵鱼 日期： 兰竺2 圣刍自! 自 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅：学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名：i 垂! i 导师签名： 吐爻 日期： 丝：2 基生日i 自 日期：2 塑2 基生目殂 c d m a 前向链路速率分配研究及网格实现 第一章概述 1 1c d m a 2 0 0 0 、w c d m a 与高速数据业务 第三代移动通信( 3 g ) 最早由联合国标准化组织国际电信联盟( i t i n t e m a t i o n a lt e l e c o m m u i l i c a t i o n u l l i o n ) 于1 9 8 5 年提出，1 9 9 6 年更名为国际移动 通信2 0 0 0 ( i m t - 2 0 0 0 ，i n t e m a t i o n a lm o b i l et e l e c o m m u n i c 鲥o n s2 0 0 0 ) ，其本来的含 义是系统工作在2 0 0 0 m h z 频段、最高业务速率可达2 0 0 0 k b i 讹、原定于2 0 0 0 年左右丌始商用。 3 g 标准的目标是为用户提供质量更佳的移动话音、移动宽带数据和移动多 媒体业务，提供更大的系统容量和更高的频谱利用率，满足人们对通信个性化 的需求，而且能在全球范围内实现无缝漫游。 i t u 针对3 g 规定了5 种陆地无线技术，其中w c d m a 、c d m a 2 0 0 0 和 t d s c d m a 是3 种主流技术。下面我们主要介绍w c d m a 和c d m a 2 0 0 0 。 w c d m a 主要由欧洲提出，是基于g s m 发展而来的3 g 技术规范。w c d m a 是最早、也是最完善的3 g 移动通信体制，为全球3 g 运营商广泛采用。2 0 0 1 年l o 月份，日本n t td o c o m o 开通了第一个w c d m a 商用网络，截至2 0 0 6 年1 0 月，商用网络增加到1 2 3 个，用户数突破8 0 0 0 万。w c d m a 已经完全成 熟起来，其增长速度超越历史同期g s m 的发展速度。w c d m a 定位于提供移 动的、有服务质量保证的多媒体业务，它的空中接口定义了完善的无线信道和 高层协议。同时，它的接入网、核心网也都定义了相应的各层协议与之配合。 目的在于完善地支持多媒体业务，并提供相应的服务质量保证机制。 c d m a 2 0 0 0 是在c d m a o n e 基础上发展的3 g 技术。c d m a 2 0 0 0 是美国 向i t u 提出的第三代移动通信空中接口标准的建议。c d m a 2 0 0 0 标准是一个体 系结构，包含一系列子标准。由c d m a o n e 向3 g 演进的途径为：c d m a o n e i s - 9 5 bc d m a 2 0 0 01 x 和c d m a 2 0 0 0i x e v 。其中c d m a 2 0 0 01 x 之后属于第三 代技术。由于无线网络高速分组业务的不断需求，c d m a 2 0 0 0l x 并不能满足这 些业务的不同要求，为了在c d m a 2 0 0 0l x 基础上进一步增强功能，以便与 w c d m a 竞争，q u a l c o m m 、l u c e m 、m o t o r l o a 等提出了c d m a 2 0 0 01 xe v 。 1 xe v 是c d m a 2 0 0 01 x 进一步发展的前景所在，它的演进又被划分为两个发 展阶段，第一个发展阶段为1 】【e v - d o ( d a t a0 l i l l y ) 。e v d o 是在和l x 话音业务 不同的独立单载波上提供分组数据业务( 本身不提供话音业务) ；第二个发展阶 段是1 x e v d v ( d a t a a i l dv o i c e ) ，数据信道与话音信道合一。目前有多种候选方 c d m a 前向链路速率分配研究及网格实现 案，如摩托罗拉、诺基亚等提出的1 栅m e 。e x d v 可以和话音业务共享单 载波提供的分组数据业务。 c d m a 2 0 0 0 系统是基于二代的i s 9 5 系统，而w c d m a 系统是基于二代 的g s m 系统，两种系统都比较成熟，尽管它们在分组业务上有不少共同点， 但是因为制式和标准的不同，还存在一定的差异。 w c d m a 和c d m a 2 0 0 0 系统的主要差别在于码片速率、下行链路信道的 结构和网络同步。c d m a 2 0 0 0 在5 m h z 带宽的直扩下行链路上采用 3 6 8 6 4 m c h i p s 码片速率，在多载频下行链路上采用1 2 2 8 8 m c h i p ，s 码片速率。 w c d m a 的直扩方式采用4 0 9 6 m c h i p s 。多载频方式是因为c d m a 2 0 0 0 与现有 i s 一9 5 同相位偏移来产生。由于是同步网络操作，这种方式是可能的。而w c d m a 为异步网络，采用不同的码长而不是同一码的不同相位偏移来区分小区和用户。 码结构影响到如何完成码同步、小区选择和切换同步。 事实上，c d m a 2 0 0 0 分组业务系统无论是网络结构还是使用的标准，都比 w c d m a 要简单实用一些。特别是标准，c d m a 2 0 0 0 较多地采用了r f c 系列， 这些标准比较成熟，可以缩短开发周期，减少开发费用。当然，也正是因为简 单，c d m a 2 0 0 0 中有些地方不够严谨，不如w c d m a 完善，但是从现有的现 场实验结果来看，c d m a 2 0 0 0 无论在业务传输速度方面，还是在传输质量方面， 都可以较好地满足用户对3 g 分组业务的需求。 包括c d m a 2 0 0 0 和w c d m a 在内的所有第三代建议的标称带宽为5 m h z 。 选择这一带宽有几个原因。首先，对于第三代系统，5 m h z 带宽可以获得 1 4 4 k b i 低和3 8 4 k b i 魄的数据速率，并且可以提供合理的容量。即使2 m b i 幽的 峰值速率也可以在有限的条件下提供。其次，频谱的缺乏要求采用小而合理的 最小频谱分配，尤其是当系统要在已被第二代系统占用的频率带宽内部署时。 第三，较宽的5 m h z 带宽比较窄的带宽更能解决多径问题，从而增加分集，改 进性能。已经有提议采用l o 、1 5 、2 0 m h z 带宽，便之能更有效地支持最高的 数据速率。 提供高速数据业务是第三代移动通信系统的一个重要特征，高速数据业务 与传统的话音业务相比，二者主要有以下区别。 表l i 数据业务与话音业务： 数据业务 话音业务 延时要求 允许一定程度的延时对延时比较敏感 误比特率要求较高较低 是否允许分组重传允许不允许 c d m a 前向链路速率分配研究及两格实现 用户问服务质量差别差别很大 差另0 很，j 、 l 前反向业务对称性前向业务是反向业务的好几倍对称 f 有两种基本的分组调度方式用来解决多用户的高速率数据信道分配问题， 分别为码分调度和时分调度。 码分调度具有以下特点： 1 多个用户可以同时被分配信道； 2 所有用户共享容量，用户增加，每个用户所分配的速率降低； 时分调度具有以下特点： 1 在某时段( 如l o m s ) 内，容量只分配给一个用户： 2 所有用户共享容量，用户增加，每个用户获得信道的时间减少： 表1 2 码分调度与时分调度： 码分调度时分调度 优点有较长的传送时间，资源利用率高速率使得每比特的能量更小；干扰 高，干扰变化小，容易预测；每更少；高速率使得时延低 个用户的速率低使得上行链路的 覆盖范围更广 缺点 低速率导致传输时延长；每比特连接建立开销大；干扰变化大；受终 能量高导致干扰大：总吞吐量低端功率限制，上行链路覆盖范围小 1 2 前向链路速率分配研究现状 高速数据业务的速率分配问题在c d m a 2 0 0 0 和w c d m a 系统的前向链路 尤为突出。这是因为对于传统的蜂窝系统而言，其承担的主要业务是话音业务 以及有限的数据业务，如短消息业务，对于系统内所有用户来说，发出的信息 和收到的信息大致相当，也就是说反向链路、前向链路的业务量是对称的。但 是对于c d m a 2 0 0 0 和w c d m a 系统来说，由于业务种类的扩展，前、反向链 路的业务量将会有很大的差异，前向链路的业务量是反向链路的业务量好几倍。 比如说，对于使用移动笔记本计算机进行网上浏览的用户而言，接收到的信息 量远大于发出的信息量。而这类业务将会成为未来无线通信的主要业务之一。 因此，c d m a 2 0 0 0 和w c d m a 系统在很大程度上将受限于前向链路。 目前对于c d m a 蜂窝系统数据业务速率分配问题的研究主要集中在国 外，例如，文献【1 1 】研究了在高速率无线接入网中，前向链路数据用户的吞吐 量表现。研究指出系统获得优异的性能得益于灵活有效的速率控制机制，文章 c d m a 前向链路速率分配研究及网格实现 中提出的算法利用了无线通信网络用户的内在差异性，改进了信号处理机制， 同时，文章也提出接入终端根据本地测量的信息申请传输速率的思路。文献【1 2 】 也对c d m a 前向链路高速数据速率分配进行了研究，主要针对用户公平性与系 统吞吐量之间的关系进行展开，主要侧重于增加用户公平性，近似于目前 w c d m a 系统的调度方式，提出了两种协调策略，一种是通过使用空闲周期减 少其它小区的干扰，另一种是使用预定的软切换周期。文献 1 3 往要对c d m a 系统反向链路速率和功率分配进行了研究，主要针对控制多径衰落，通过减少 传输速率而控制整体的功率，文章也提出需要基站控制移动终端的传输速率。 这些研究对本文提出的前向速率分配模型有很好的借鉴意义，但是所有这些研 究都只考虑了单用户的系统，即在同一时间内，只有一个用户接收前向链路数 据。这使它们的应用受到一定限制。 1 3 速率分配的并行实现与网格 由于c d m a 系统的前向链路速率分配具有层次结构，分配涉及基站和相 关的多个激活终端，同时为了达到较为精确的计算结果需要增加迭代次数，所 以计算具有较高的复杂度，单机上运算需要花费相当长的计算时间。 网格是专门针对复杂科学计算应用的一种新型计算模式，这种计算模式能 够把整个网络里面的各种异构资源整合成一台巨大的超级计算机。利用集群、 高性能p c 机等搭建的网格所提供的并行环境，可以将巨量的计算任务分布到 多个c p u 上运行，轻松的实现分布式计算。借助网格优秀的计算能力，在网格 上实现速率分配的并行化，解决了前向链路速率计算复杂度高的问题。 同时，网格作为第三代i m e m e t ，整合了包括数据库、信息获取、计算相关 的各种资源，最大化的实现互联网上所有资源的全部连通，为用户提供一体化 服务。借助网格的信息发布机制，使得前向链路速率可以作为一个服务面向所 有用户。另一方面，利用网格的并行编程接口和工作流引擎，对于服务开发者 来说，网格的底层传输调度机制是透明的，这使得服务开发流程更为简单。 1 4 本文研究内容 本文研究的主要内容包括：前向链路速率分配抽象系统模型的建立、如何 应用大系统递阶分层建立二级求解模型、如何应用遗传算法实现并行求解、如 何借助网格环境实现并行算法，同时通过仿真实验数据，比较并分析了算法收 敛性、并行加速比以及时分调度与码分调度的优势与劣势。 论文结构如下： 4 c d m a 前向链路速率分配研究及网格实现 第一章是概述，介绍一些背景知识、前向链路速率分配的研究现状。 第二章介绍c d m a 2 0 0 0 与w c d m a 系统的数据业务分析，并从中抽象出 前向链路速率分配的理论模型。 第三章重点介绍c d m a 系统前向链路速率分配模型，主要从模型建立， 算法描述方面着手，其中两个子闯题分别是移动台s 瓜分配算法以及基站速率 分配算法。针对基站速率分配算法重点研究了基于遗传算法的求解以及并行实 现方法。 第四章是针对前向链路速率分配仿真的研究，从遗传算法收敛性、并行效 率、以及速率分配效率等方面作了分析。 第五章是基于网格的并行前向链路速率分配，介绍了移动通信网络优化网 格，重点介绍速率分配子系统各个模块的具体实现方法。 最后一章结束语，总结全文，提出进一步研究方向。 c d m a 前向链路速率分配研究及同格实现 第二章c d m a 2 0 0 0 与w c d m a 系统数据业务分析 2 1c d m a 2 0 0 0 数据业务分析 2 1 1c d m a 2 o 分层结构 为实现高度模块化的设计，使系统具有灵活性和可伸缩性，c d m a 2 0 0 0 系 统采用了分层的结构体系，不同的层次由不同的标准来规范。c d m a 2 0 0 0 的层 次结构如图2 1 所示，可以分为物理层、链路层和上层三个层次。这种分层结 构可以支持话音业务、数据业务、信令业务及上述任意组合的业务。其中，物 理层和链路层支持国际标准化组织( i s o y 开放系统互联参考模型( o s i ) 下面两层 相对应的协议和业务，所有链路层以上的业务( 类似0 s i 模型网络层、传输层、 会议层、表示层和应用层的功能) 则由上层完成。 上层( u p p e rl a y e r ) 又叫层三( l a y e r3 ) 。上层主要完成呼叫业务处理、移动 性管理、无线资源管理等功能。从图2 1 可以看出，它主要包括三项基本业务： 话音业务、数据业务和高层信令。话音业务指话音电话业务，包括p s t n 接入、 移动到移动话音业务和i n t e m e t 电话等；数据业务指给移动用户提供的任何一 种形式的数据业务，包括分组数据业务( 例如i p 业务) 、电路数据业务( 例如 b i s d n 仿真业务) 和短消息业务等；商层信令主要指控制移动操作的信令的交 互，包括i s 一9 52 g 信令业务和c d m a 2 0 0 0 上层信令业务，上层通过底层( 链路 层) 提供的服务，按照通信协议规定的语法和定时关系发送和接收基站和移动台 之间的信令消息，保证系统的承载业务顺利的完成。c d m a 的高层信令消息按 照作用分类主要有以下几类： ( 1 ) 系统开销消息，如同步参数、系统参数消息和接入参数消息等，其功能是 传递系统初始建立连接所必需的一些参数，这类消息基本由i s 9 5 中相应的消 息扩展而来，并且具有兼容性。 ( 2 ) 业务协商消息，其功能是在建立业务连接时实现更合理的申请和使用无线 资源，这些消息体现了c d m a 2 0 0 0 较之i s 9 5 在数据业务上的增强。 ( 3 ) 有关切换的消息，包括软切换和硬切换，这部分的消息对系统的性能和容 量有密切的关系。 ( 4 ) 有关c d m a 位蔑服务的消息，位置服务的目的是使移动用户能根据其所在 的地理区域或位置获得个性化的、量身定制的服务。如用户可根据自己的喜好， 获得当前所处地点附近的餐饮、购物或娱乐等消息。 6 c d m a 前向链路速率分配研究及同格实现 上层支持先进的多媒体业务，c d m a 2 0 0 0 上层不但能够支持多种业务同时 进行，还具有一套先进的q o s 管理机制，可以发送或动态地调整每个业务的质 量参数。 上层 i s - 9 5 层电 c d m a 2 0 0 0其它上分组数话音电路数 o s j ( 3 7 ) 层 路信令上层信令层信令据业务业务据业务 i s 一9 5 信令 c d m a 2 0 0 0 其它上 分组数电路数 层信令 空层 l a c 第2 层 信令第2 层 据第2 层 据 子层 第2 层 链路层 m a c 分组或数据业务的 o s i 第2m a c 信令的p l i c f p l i c f m a c 信令的p l d c f分组或数据业务的p l d c f于层 p l d c fm u x 和q o s 子层 v_l 物 吧层 0 s l 第1c d m a 2 0 0 0 物理层 层 p l i c f = 独立于物理层的会聚功能 p l d c f 哟理层决定的会聚功能 图2 1c d m a 2 0 0 0 分层结构 2 1 2c d m a 2 0 0 0 前向数据业务分析 前向补充信道( r c 3 一r c 9 ) 或前向补充码分信道( r c l r c 2 ) 是专门用于前向 链路高速数据业务传输的信道。通常，当数据业务量比较小时，基站只用阿向 基本信道传输数据业务，而只有当前向链路数据业务量比较大或用户要求高速 数据服务时，基站才用前向补充信道( r c 3 一r c 9 ) 或前向补充码分信道( r c l r c 2 ) 以较高的速率传输数据。前向补充信道或前向补充码分信道专用来向用户传输 数据，而用于控制数据业务传输的信令则在前向基本信道上发送，而当前向基 本信道也比较繁忙时，基站则用前向专用控制信道传送信令消息以保证信令消 息的可靠传输。 基站对前向补充码分信道和前向补充信道的分配需要占用较多的资源，如 功率资源、正交码资源等，同时，它们也给其它用户带来了干扰，但是，由于 数据业务的突发性较强，因此总的看来，前向补充码分信道和前向补充信道的 建立提高了系统的吞吐量。 c d m 前向链路速率分配研究及网格实现 图2 2c d m a 2 0 0 0 前向链路信道 2 2w c d m a 数据业务分析 2 2 1 w c d m a 分层结构 w c d m a 系统如图所示。从系统结构和功能上看，w c d m a 系统主要由用 户终端设备( u e ) 、无线接入网( u t r a n ) 以及核心网( c n ) 三部分构成。此外核心 网还可以与外部网络通信，以提供更丰富的业务，如许多基于因特网的业务。 无线接入网和核心网的发展不同，核心网受到有线网络技术发展的影响较 大，从现有的g s m g p r s 核心网平台开始，以平滑演进的方式逐步过渡到全 i p 通信网络；而无线接入网可以采用革命性的变化，其目标是提高无线资源利 用率( 频谱利用率) 和灵活地提供多种业务。 3 g p p 所规范的w c d m a 系统包括无线接入网络和核心网络两大部分。无 线接入网络采用先进的w c d m a 技术，核心网络采用灵活的、可从g s m 网络 平滑演进的分层体系结构。 w c d m a 系统将向可实现资源共享的水平分层结构演进，在水平方向上可 分为接入层和非接入层。 c d m a 前向链踏速率分配研究及弼格实现 非 接 入 屡 接 入 层 控制面 用户面 1分组域公用电路域分组业务电路业务 图2 3w c d m a 分层结构 网络结构由下至上分为：接入层、控制层和应用层。接入层提供各种业务 承载：控制层负责各种控制信息即信令的交换，如各种移动管理信令和话务连 接信令；应用层为用户提供各种上层的应用。 这种水平分层结构将通信业务与控制消息分开，便于多种网络之间的资源 共享，提高设备利用率，又因其结构的灵活性和开放性，使得网络的平滑演进 和不同网络的逐渐融合成为可能。例如：移动网络和分组数据网络能够共享接 入层的传输资源和应用层的各种服务器。又如：如果需要将传输网从由俐 交换机组成的a t m 网络改为由i p 路由器组成的i p 网络，主要的变化发生在按 入层，控制层和应用层则不需要变化或只需作微小变化。而如果上层应用要调 整，受影响的只是相关应用服务器，控制层和接入层不受影响。 w c d m a 系统在垂直方向上可划分为用户面和控制面，如图2 3 。 控制面负责系统各实体间的控制信令消息的承载，包括所有的w c d m a 特 定控制信令( 应用协议及用于传输这些应用协议的信令承载) ：用户面承载用户 设备到网络部分的用户数据，包括数据流和用于承载这些数据流的数据承载， 用户发送和接收的所有信息都是通过用户面来进行传输的。 2 2 2 w c d m a 前向数据业务分析 w c d m a 中有三种类型的传输信道用于传输分组数据：公共传输信道、专 用传输信道和共享传输信道。公共信道即前向链路上的随机接入信道。公共信 9 c d m a 前向链路速率分配研究及网格实现 道的优点是信道建立时间短，缺点是没有反馈信道，同时干扰大，所以公共信 道最适合传送量小的分组业务或者t c p 连接建立期的小分组包、低速率传输。 专用信道的优点是可以使用快速功率控制和软切换，这些特性提高了它们的无 线性能，同时产生较小的干扰，专用信道的速率可以是k b i 讥2 m b i 体，而且使 用中可以动态改变速率，缺点是建立一个专用信道需要较长时期。共享信道的 作用是传输突发分组数据，其工作原理是：在多个用户之间以时分方式共享一 个物理信道，也即使用一个正交码，以节省前向链路上有限的正交码资源。相 对于专用信道来说，共享信道具有更高的码资源利用率。一般来说，共享信道 与一个低速率的专用信道并行使用，专用信道承载控制信息，包括快速功率控 制指令。由于共享信道的工作特点所限，它不能使用软切换。共享信道适合传 递t c p 慢启动期以及正常期的大分组包。 2 3 前向链路速率分配理论模型 3 g 标准下的w c d m a 与c d m a 2 0 0 0 实现方式有所不同。在前向链路速率分 配过程中，w c d m a 通常在共享信道上采用码分调度方式，即多个用户接入时， 以功率为资源进行分配。而c d m a 2 0 0 0 的e v d 0 系统，则以时分调度方式实现， 即多个用户接入时，以时间片为资源进行分配。同时e v - d o 的另一个特点是，当 移动台接收的载于比比较低时，基站通过降低其传输速率，增加数据的重复度来 等效增加用户的载干比。即移动台请求传输速率，而基站根据调度算法决定是否 批准该请求并且决定数据的传输时刻。但是，不论哪种系统，它们的共同特点是： 在前向链路中，每个移动台都是独立获得自己的载干比，并且由基站判决对激活 终端的传输速率。 在此基础上，本文将前向链路的速率分配过程抽象成为一个理论模型，叙 述如下： 在c d m a 系统的前向链路上，每个移动台独立地选择自己的s i r 目标，以获 得某个误帧率性能。然后，移动台发送一连串的功控比特，通知基站增大或减小 发射功率以达到s i r 目标。s 服目标由每个移动台根据给定的用户局部信道信息确 定。即各个激活终端独立的收集信道、干扰信息，然后根据提供的p r e r 参数( 端 到端的q o s 保证) 计算移动台s i r 目标表。s i r 目标表是帧重传的决策表，对于数据 用户，由于对于时间延迟不敏感，但对f e r 要求比较严格，所以采用重传机制保 证p r e r 达到用户要求。假定所有用户物理层的帧和数据段同步。在一个数据段 内，用户的数据速率不变，r j j 重发一个错误帧的最大次数是2 次。来自某用户 的一个数据帧最初发射时，移动台定的目标s i r 是扎。当接收的数据帧出错时， 移动台通过上行链路控制信道向基站发射一个n a k 消息，请求重发该帧。如果 1 0 c 】) m a 前向链路速率分配研究厦网格实现 第一次重传失败，那么第二次重传以系统的最大s i r 限制进行尝试，最大限度的 保证移动台可以收到正确的数据帧。所有用户的数据传输速率由基站分配，基站 负责维护通信网络的稳定性和最优化系统性能。移动台通过上行控制信道，将每 比特最小s i r 作为参数传递给基站。基站获得所有激活终端的信息，根据激活终 端数量，按照一定策略将它们分配在不同的业务信道上。对于每一个信道，所有 激活终端的参数构成一组向量组，根据这组向量组，选择合适的用户效用函数。 用户的效用函数定义为数据速率r 的函数，通过调整效用函数的形状，可以在系 统的吞吐量和公平性之间得到一个灵活的折中。 c d m 前向链路速率分配研究及网格实现 第三章c d m a 系统前向链路速率分配模型 3 1 前向链路速率分配模型 3 1 1 建模基本原理 前向链路速率分配算法具有分层结构，而且基站与激活终端问的信息传递 很有限，非常适合分布式实现方式。本文采用大系统递阶分层控制结构建模。 在大工业过程中，计算机在线稳态优化控制常用的是递阶控制结构，如下 图所示。图中既有直接控制层又有优化层，而优化层本身又是一个两级结构， 由局部决策单元级和协调器组成。 优化层 直接控 制层 图3 1 大系统遵阶控制结构 由大系统的分散或递阶控制结构可以看出，大系统的一个关键问题是问题 的分解。将一个全局性问题分解为若干子问题，分解可以按照地域、分布、功 能等来进行。本文应用大系统递阶分层控制将基站针对激活终端的速率分配优 化问题分解为移动台s i r 分配算法和速率分配算法两级求解结构，这种功能上 的分解称为垂直分解。同时在解决第二步基站速率分配算法的时候，将运算过 程分配到若干并行子系统，并有一个运算节点作为主控节点，这种分解称为水 平分解。 如图3 2 所示，各个移动台作为局部决策单元，首先进行移动台s 承分配， 求得每比特最小s i r ，然后将结果返回给基站子系统，基站子系统将收集到的 每比特最小s i r 作为协调变量进行全局的优化，将速率分配结果，即每个移动 台申请到的速率返回给终端。 1 2 商旱崩案 a 忱前向链路速率分配研究及两格实现 图3 2 基站移动台模型结构 实际上，协调是多级递阶控制中的一个关键，协调器控制着下一层许多局 部决策单元，协调器的任务就是通过对下层局部决策单元的干预，来保证它们 分别找到的决策能满足整个大工业过程的总目标函数优化的要求。因此协调器 不断地和下级局部决策单元交换信息内容，同时按照一定的策略进行比较或者 计算，并发出对各个子过程局部决策单元的干预信息，以起到协调作用。落实 在大系统递阶控制模型中，基站子系统充当协调器的角色。 3 1 2 速率分配问题建模 考虑一个业务信道同时响应n 个激活终端的请求，s i r 和速率分配算法的 目标是在一个数据段传输开始时为每一个用户寻找一组s i r 和速率参数，以优 化这个数据段传输期间的总效用。约束条件有两个：( 1 ) 所有用户的总的前向链 路功率不应超过极限功率c 。( 2 ) 对于每一个数据用户，p r e r 不应超过极限g 。 这一优化问题可用数学公式表述如下： 选择矢量s j = ，r f = 正。，：，i ，r ) ，其中产1 ，2 ，n ，使得 s 翌冬，善u ，( r ) 式( 3 1 ) s u b j e c t t o 万c 式( 3 2 ) p r e r is o 式( 3 3 ) y 。，。s 。 m 2 1 ，2 ，3i = 1 ，2 ， n式( 3 4 ) r m rs 尺。 i 1 ，2 ，n 式( 3 5 ) 其中式( 3 2 ) 是对平均功率的约束，式( 3 3 ) 是用户的q o s 需求，式( 3 4 ) 是s 瓜 约束，式( 3 - 5 ) 是传输速率上下限约束。 由于采用速率控制模式，所以假定传输功率尸可以由功率控制算法控制调 j磊可旦竺幕匀 r，l x rl 整，以获得用户i 的s i r 目标。 设变量置为用户i 的每比特平均s 吸，则 置4 署赢 其中： 元， 传输数据段平均链路增益 l用户i 所受到的来自其它小区的干扰和热噪声 w 信道的扩频带宽 式( 3 6 ) 式变型为 ；，= 等( 粪j ，圳) 将所有激活终端用户的功率相加可得： 豁= 姜等善n ；| ；鬻 进一步推导，合并等式的同类项，并且由功率约束可得 盟 努箍卯 ” l 一- 二= ! ：! 鲁 化简可得： 兰笔孚砒c 台矽万，“一、3 。 令a ，= t i 。f hj + c 、f w 则功率约束可以以式( 3 1 2 ) 表示： 口，置置c 式( 3 6 ) 式( 3 7 ) 式( 3 8 ) 式( 3 9 ) 式( 3 1 0 ) 同时五可以通过下式与各次s 取目标相关联，下式是各激活终端每比特平 均s 瓜的概率表达： 3 置= 乃以( m ) 其中吼( 研) 为激活终端i 第m 次接收数据成功的概率，也就是说，之前的 1 4 血 i a 前向链路速率分配研究及网格实现 m 1 次数据都传输失败。 另外，后砌卫差错率的计算公式为： 3 p 冠积，= 兀z ( y 。) t i 要求p 兄职。s s o 为了使优化问题有解，文中约定： 33 兀；( ) o 。x 为问题的可行解域。 对于规模不大的约束最优化问题，罚函数法具有良好的应用效果。在实现 算法中由于在生成初始种群时引入了边界约束，所以结果的离散性不是很大。 采用静态罚函数法就可以解决优化问题。 由于目标函数值恒小于0 ，所以目标函数可以定为： 峄善u ，( b )1 善( c + 7 吃) 7 矽4 以+ r s c 峄善u ( r ) + 胁d o m 砌o ，o a ) m 前向链路速率分配研究及网格实现 i f ( c + ，1 1 ) 矿+ 置+ r ， c 式( 3 - 2 9 ) ，l 系统的主要函数为 v o i di i l i t i a l i z e ( v o i d ) ；初始化函数，将参数文件数据读入临时变量 v o i d “a l u a t e ( v o i d ) ； 计算各组变量针对效用函数的适应度 v o i dk e e p 圮b e s t ( v o i d ) ；将各个个体的最优解保存在临时变量中 v o i de l i t i 蜮v o i d ) ；n 和n + l 代做比较，寻找n + 1 中适应度最低与适应度 最高的因子，如果n 代中遗传下来的因子( 适应度最高) 优于n + 1 代，则用其替 换n + 1 代中最差的因子。如果n 代中遗传下来的因子( 适应度最高) 差于n + 1 代，则将n + 1 代的最优因子保存在l 临时变量中，进入下一次遗传。 v o i ds e l e c t l ( v o i d ) ；计算整体一代所有因子的相对适应度，选择最优的存 活。 v o i dc r o s s o v 叫v o i d ) ；交叉运算，结合来自父代种群的信息产生新的个体。 交叉运算采用段交叉，随机生成交叉点，交叉点前半段进行交换。父代逐一进 行一定概率的交叉运算。 v o i dm u t a t e ( v o i d ) ；变异运算，选择一个个体，选择其中的若干基因变量， 在限制范围内以定义的变异概率进行变异，采用实值变异方式。 算法采用遗传算法求解非线性规划问题的方法，以人口数作为并行划分依 据和算法结束条件，各个节点独立计算，分若干次交换代中最优因子，将交换 得到的最优因子和局部环境中的最优因子做比较，选取相对优质的进入本地的 下次选择。通过这种机制可以有效的防止求解陷入局部最优。实现流程参见5 2 节。 3 3 3 并行遗传机制的实现方法 通常来说，实现并行遗传机制的方法大体可分为如下两类：标准型并行方 法和分解型并行方法。标准型并行方法并未改变串行遗传算法的基本特点，它 在一个总体的环境中实现进化运算，所以它需要使用一个统一的群体，实现时 也需要一个全局存储器，还需要有一个统一的控制机构来协调群体的遗传进化 过程及群体之间的通讯过程。由于群体的遗传进化过程是在这么多需要进行统 一和协调的环境中进行，这样就需要有一种较好的协调策略，即使是这样，协 调起来也比较费时，所以这种实现方法对遗传算法的运行速度提高不大。 分解型并行方法将整个群体分解为若干子群体，各个子群体被分配在不同 的处理机上，它们各自串行运行所在处理机上的基本遗传算法，然后在适当的 c d m a 前向链路速率分配研究及弼格实现 时候，各处理机之间相互交换一些信息。这种实现方法比较符合生物自然进化 的过程并充分地利用了遗传算法的天然并行结构和群体特性，所以实现起来比 较简单。目前，这种实现方法在遗传算法的并行化中得到了广泛的使用。 本文使用分解型并行方法实现遗传机制。这种方法将群体分布在各个处理 机的局部存储器中，独立地对各组个体进行遗传进化操作，所以能够有近似线 性的加速比，能够有效地提高遗传算法的运算速度，而且由于保持了各处理机 上子群体进化的局部特征，所以这种方法还能够有效地回避遗传算法的早熟现 象。 本文在构造并行遗传算法时采用了如下原则。在问题划分上，采用粗粒度 的子群体划分方式，即将整个群体均匀地分配到各个处理机，每一处理机上分 配有多个个体。在信息交换方式上，采用轮换方式，即参与计算的若干个节点 依次交换信息。信息交换内容采用择优交换，即交换子群体中最好的个体，替 换子群体中最差的个体。交换时间是以同步方式在进化过程的中间时刻进行若 干次信息交换。交换信息量为一个个体。 流程如下图： c d m 前向链路速率分配研究及罔格实现 照上下界2 束初始群体 个体适应度评 价 3 4 时间窗调用模式 圈3 4 基站并行遗传算法 y 选择并交换最 优个体 胃 土! f结束 由于系统中可能有多个激活终端同时申请速率分配服务，而它们要求传输 的数据量不同，同时各个激活终端由于所处位置、信号强度、干扰强度等不同 造成的信道差异，所申请到的速率也会有不同。所以，所有的移动台不可能在 同一时间完成数据传输，必定会有移动台逐步的停止带宽占用，释放申请的资 源。 为了解决这一问题，对前向链路的速率分配采用时间窗调用模式。思路如 下：在每个微小的固定时隙内，基站对移动台的前向传输速率不变。同时，由 基站在每个固定时隙开始前，统计各个移动台的s i r ，剩余传输量，并计算申 请服务的移动台数，同时准备各个移动台的数据，然后才调用基站速率分配算 法。如果a 移动台在某个时隙结束后，统计其剩余传输量小于等于o ，则意味 辜鬲茶 霉雨鬲毒一歪!王玄毒变觫 差去善銮一 c d m a 前向链路速率分配研究及网格实现 着对a 的速率分