（信息与通信工程专业论文）dscdma系统中ovsf码分配算法研究.pdf

浙江人学坝i 。学位论文 摘要 直接序列扩频码分多埘：是第代移动通信系统空中接口的基本技术，是实现无线多媒体通信 的关键。它采用正交可变扩频因子( o v s f ) 码作为信道化码，正交性的限制与码资源有限导致了 码阻塞现象。码阻塞不仅降低了码资源的利用率，造成系统资源浪费，还使大部分码资源被低速 率的呼叫抢占，使分配过程对高速率的呼叫不公平。有效地减少甚至消除码阻塞，充分利用有限 的o v s f 码资源，实现公平分配成了o v s f 码分配算法需要解决的问题。 本文提出以算法目的分类，将迄今公开发表的几十种分配算法分为以战少码阻塞为目的 ( 从系统的角度) 的单码分配算法和多码分配算法；以公平分配为目的( 从用户的角度) 的保 留分配算法。并提出吞吐量、阻塞率、码阻塞率和公平系数等指标，用来定量评价三类分配算法 在这瓯方面的性能。根据o v s f 码及其分配过程的特点，本文以自行设计的业务模型和o p n e t 仿真模型为平台，分别对单码、多码和保留三种分配算法进行了仿真、研究。 研究单码分配算法时，首先介绍了已提出的随机、极左、紧凑和权熏四种分配算法。通过仿 真比较它们的吞吐量、阻塞率和码阻塞率，综合评价了四种算法的性能，并得出权重算法在减少 码阻塞方面最优的结论。然后在对现有算法局限性研究的基础上，提出综合性能更优的极左碎片 分配算法。其处理远比权重算法简单，在码资源利用方面与权重算法几乎一样高效，在接入不同 速率类型的呼叫时与权重算法几乎一样公平。系统采用极左碎片算法既能加快分配速度，减少 用户等待时间，又能较充分地利用o v s f 码资源，公平对待各类用户。 研究o v s f 多码分配算法时，将整个分配过程分为确定分配码字和确定码位置两个阶段，介 绍了分属这两个阶段的各种算法。比较仿真缩果与单码算法，发现多码分配算法更能有效减少或 消除码阻塞，其代价是硬件复杂度增加；将同阶段或同步中算法的仿真结果作了比较，并做出了 评价。然后针对3 g p p 2 中多码能力为2 的规定，仿真考察了此时算法的性能，发现存在码阻塞。 最后综合各阶段各步中的所有算法，得到在减少码阻塞方面最有效、计算量最小的两个阶段多码 算法组合。 研究o v s f 保留分配算法时，首先介绍了现有的单一分区、混合分区l 和混合分区2 三种分 配算法。通过仿真比较它们的公平系数，综合评价了三种算法的公平性。在对现有算法局限性研 究的基础上，提出更优的分区借码分配算法。它是现有算法的改进，它不仅在分配前为每类呼叫 预留码资源而且在分酉己过程中及时协调各区资源的使崩，使分配更公平，吞吐量更大。 关键词： 直接序列扩频码分多址，正交可变长扩频因子，码阻塞，分配，单码分配算法，多码分配算法， 保留分配算法 浙江大学钡士学位论文 a b s t r a c t d i r e c ts e q u e n c ec o d ed i v i s i o nm u l t i p l ea c c e s s ( d s c d m a ) i sab a s i ct e c h n o l o g yo fa i ri n t e r f a c e i nt h et h i r dg e r n e r a t i o n ( 3 g ) m o b i l ec o m m u n i c a t i o ns y s t e m s ，a n dt h ek e yf o ri m p l e m e n t a t i o no f m u l t i m e d i ac o m m u n i c a t i o n i t e m p l o y so r t h o g o n a lv a r i a b l es p r e a d i n gf a c t o r ( o v s f ) c o d e s a s c h a n n e l i z a t i o nc o d e c o d eb l o c k i n gi sc a u s e db yt h eo r t h o g o n a l i t yc o n s t r a i n ta n dt h el i m i t e dn u m b e ro f o v s fc o d e s ，w h i c hl e a d st ow a s t eo fc o d er e s o u r c ea n du n f a i r n e s sf o rh i g h r a t ec a l l s t h e r e f o r e ， o v s fc o d e sa s s i g n i n ga l g o r i t h m ss h o u l dm a k ef u l lu s eo fc o d er e s o u r c eb ya l l e v i a t i n ge v e n e l i m i n a t i n gc o d eb l o c k i n ga n dh e l ps y s t e mb e i n gf m r t oe a c hk i n do f c a l l s w ec l a s s i f i e dt e n so fe x i s t i n ga s s i g n i n ga l g o r i t h m si n t ot w ok i n d s ：( 1 ) a i m i n gt oa l l e v i a t ec o d e b l o c k i n gf o rs y s t e m ，i n c l u d i n gs i n g l e c o d ea s s i g n i n ga l g o r i t h m ( s a a ) a n dm u l t i - c o d ea s s i g n i n g a l g o r i t h m ( m a a ) ；( 2 ) a i m i n gt om a k es y s t e mf a i rt oe a c hk i n do fc a l l s ，i n c l u d i n gr e s e r v e da s s i g n i n g a l g o r i t h m ( r a a ) t h r u o u g h p u t ，b l o c k i n gp r o b a b i l i t y ( b p ) ，c o d eb l o c k i n gp r o b a b i l i t y ( c b p ) a n d f a i m e s si n d e xw e r eu s e dt oe v a l u a t ea l lt h r e ek i n d so fa l g o r i t h m sq u a n t i t a t i v e l y w es t u d i e ds a a ， m a aa n dr a aw i t ht r a f f i cm o d e la n do p n e ts i m u l a t i o nm o d e ld e s i g n e da c c o r d i n gt ot h ef e a t u r e so f o v s fc o d ea n da s s i g n n m e n tp r o c e s s f o u re x i s t i n gs a aa l g o r i t h m sw e r ep r e s e n t e da tf i r s t t h e ya l er a n d o m ，t e f t m o s t ，n o n a r r a n g e a b l e c o m p a c ta s s i g n m e n tr n c a ) a n dw e i g h ta l g o r i t h m s ，a f t e ra n a l y z i n gt h e i rp e r f o r m a n c e sb yc o m p a r i n g t h e s i m u l a t i o nr e s u l t so f t h r o u g h p u t ，b pa n dc b p , w ec a nc o n c l u d et h a tt h ew e i g h ta t g o f i t h e ai st h eb e s t t oa l l e v i a t ec o d eb l o c k i n g t h e nan e ws a an a m e dl e f f m o s t f r a g m e n ta s s i g n m e n t ( l f a ) w a sp r o p o s e d a f t e ri n v e s t i g a t i n gt h ew e a k n e s so fe x i s t i n ga l g o r i t h m s c o m p a r i n gw i t ht h ew e i g h ts c h e m e ，l f ah a s m u c hl o w e rc o m p u t a t i o n a lc o m p l e x i t yw i t hn e a r l yc b pa n df a i r n e s s b ye m p l o y i n gl f at h es y s t e m c a nm a k ea s s i g n m e n tf a s t e rt oh e l pu s e r sw a i tl e s s ，u l i l i z eo v s fc o d er e s o u r c et h o r o u g h l y , a n db ef a i r t oa n yt y p e so f c a l l s w h e ns t u d y i n gm a a ，w ed i v i d e dt h ew h o l ea s s i g n m e n ti n t ot w op h a s e s ：( 1 ) g e r i n ga s s i g n i n g c o d e w o r d ( g a c ) ；a n d ( 2 ) g e r i n gc o d e s l o c a t i o n ( g c l ) e x i s t i n gs c h e m e si ng a c a n dg c lw e r ea l l i n t r o d u c e d i tw a sf o u n dt h a tm m ai sb e r e rt h a ns a ai na l l e v i a t i n go re l i m i n a t i n gc o d eb l o c k i n g ，a t t h ec o s to fh a r d w a r ec o m p l e x i t y m u r e o v e r ，w ee v a l u a t e da l lm a aa l g o r i t h m si nd i f f e r e n tp h a s e so r s t e p sb ys i m u l a t i o n ，a n dn o t i c e dt h a tc o d eb l o c k i n ga p p e a r e dw h e nt h eu s e re q u i p m e n t c a l ls u p p o r to n l y t w oc o d e sa ss p e c i f i e di n3 g p p 2 a sar e s u l to f t h a t ，t h eo p t i m u ma l g o r i t h mf o rt h ew h o l em a ac a nb e o b t a i n e db yc o m b i n i n ge v e r yb e s ta l g o r i t h mi na l lp h r i s e sa n ds t e p s w h e ni tc o m e st or a a ，f i r s t l yw ee x p l a i n e de x i s t i n ga p p r o a c h e si n c l u d i n gs o l op a r t i t i o n ( s p ) ， h y b r i dp a r t i t i o ni ( h p l ) a n dh y b r i dp a r t i t i o n2 ( h v 2 ) ，a n di n v e s t i g a t e dt h e i rp e r f o r m a n c e si nf a i r n e s sb y s i m u l a t i o n an e wr a an a m e dp a r t i t i o n & b o r r o w ( p b ) w a sp r o p o s e d ，w h i c hi s f a i r e rt h a no l d s c h e m e s b e s i d e sp r e s e r v i n gc o d er e s o u r c e ，i tt r i e st oa s s i g nac o d ef o rt h ec a l lw i t hh i g h t e s tb p b o r r o w e df r o ma n o t h e rp a r t i t i o nw i t hl o w e rb p , a n dm a k eaf a i r e ra s s i g n m e n ta n dh i g h e rt h r o u g h p u t ， k e y w o r d s ：d s - c d m a ，o v s kc o d eb l o c k i n g , a s s i g n m e n t , s i n g l e - c o d ea s s i g n i n ga l g o r i t h m ， m u l t i c o d e - c o d ea s s i g n i n ga l g o r i t h m ，r e s e r v a t i o na s s i g n i n ga l g o r i t h m i i 浙江大学硕+ 学位论文 第一章绪论 与前她代系统相比，第三代移动通信( t h et h i r dg e n e r a t i o nm o b i l ec o m m u n i c a t i o n ，3 g ) 系统 的主要特征是可提供丰富多彩的移动多媒体业务( m u l t i p l em e d i as e r v i c e ，m m s ) ，其传输速率在高 速移动环境中支持1 4 4 k b s ，步行慢速移动环境中支持3 8 4 k b s ，静止状态下支持2 m b s t l i 。其设 计目标是为了提供比第二代系统更大的系统容量、更好的通信质量，而且要能在全球范隔内更好 地实现无缝漫游及为用， l l 提供包括话音、数据及多媒体等在内的多种业务。 空中接口( a i r i n t e r f a c e ，a i ) 是移动通信系统中基站和用户终端之间的接e l 。空中接f j 采用无线 电波传递信息，所以空中接口义称为无线接口。直接序列扩频码分多址( d i r e c ts e q u e n c ec o d e d i v i s i o nm u l t i p l e a c c e s s ，d s c d m a ) 是3 g 系统空中接口的基本技术，足3 g 标准中的重要部分， 是实现无线多媒体通信的关键。d s c d m a 基于a n s i - 4 1 核心网，它采用频分双t ( f r e q u e n c y d i v i s i o nd u p l e x ，f d d ) x 作方式，码片速率3 8 4 m c s ，采用自适应天线及多用户检测等新技术， 并可支持频率间切换。与第二代无线传输技术相比，d s c d m a 具有更大的通信容量、较高的 数据传输率和较强的抗干扰性能，能支持更高带宽业务和提供更灵活的多种混合业务。 1 2o v s f 码的采用 d s c d m a 技术的基础是正交的信道化码。d s c d m a 系统支持多速率数据传输的基本方案 有两种。是多码( m u c o d e ) 方案( m c c d m a ) 1 2 嘲。在f 行，按照一个用户要求的速率，为该 用户分配多个等长的信道化码1 4 1 。这个方案要求移动接收机中有多个r a k e 合并器，每个码道 个合并器。这使移动接收机的复杂度大为增加。二是正交可变扩频因子( o r t h o g o n a lv a r i a b l e s p r e a d i n gf a c t o r ，o v s f l 码方案( o v s f c d m a ) ，用单个不同长度的码支持不同速率的业务p f 。 这个方案被广泛接受，己用于实际c d m a 系统。 采用具有二进制树状结构5 1 的o v s f 码作为信道化码来支持多速率数据传输附f ”就是根据 呼叫请求的速率分配相应的o v s f 码，由。r 码片速率恒定，将长的信道化码分配给低速率业务， 短的信道化码分配给高速率业务。分配给用户的码必须和正在使用的所有码相互正交1 7 j ，即没有 父子关系。所以，一个o v s f 码被古用时，和它有父子关系的码都会被禁用。 有时系统的容量足以支持新呼叫请求的速率，但由于系统中被占用的码在码树中分布较分 散，被禁用的码较多，无法找到与呼叫请求的速率对应长度的码，不得不阻塞此呼叫，这种阻塞 称为码阻塞( c o d eb l o c k i n g ) f ”。码阻塞降低了码资源的利用率，造成系统资源浪费。 l 浙江人学硕。学位论文 当请求高速率的呼叫较多时，d s c d m a 系统是码受限的1 8 ( c o d e l i m i t e d ) 。随着多媒体业务 种类和数量的增加，c d m a 系统的码阻塞问题l 二经凸显。2 0 0 2 年底，杭州联通c d m a 2 0 0 0i x 现 网( 加拿大北方电讯敬备，r c 3 无线配置i i ) 已经出现码阻塞现象。在数据用，_ l 反映无法接入 时进行测试，发现功率仍有3 d b 富裕( 只有一半功率l l 在使用中) ，连接数和占用的系统容量并 不多。从日忐分析表明，当时已没有词分配的信道化码。 信道化码属于d s c d m a 移动通信系统的无线资源。码资源管理是无线资源管理( 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 ) 的主要内容之一，对系统资源利用率、网络吞吐量、接入延迟均有 明显影响。给用户合理地分配o v s f 码，不仅能减少码阻塞，提高码资源利用率，还可以使速率 请求小同的用户公平地使用码资源。因此，需要深入研究o v s f 码的分配算法，找到虽“合理” 的做法。 1 3 o v s f 码分配算法分类及研究现状 从2 0 0 0 年第一篇研究o v s f 码分配的论文发表以来，共提出了几十种分配算法。本文从不 同角度将它们分类如下。 以战少码阻塞为目的( 从系统的角度) ：单码分配算法和多码分配算法； 以公平分配为f l 的( 从用户的角度) ：保留分配算法。 在研究这些文献时发现，人多数论文都详尽地介绍了所提出的算法。其中大多以减少或消除 码阻塞为主要目的，采用阻塞率、码阻塞率和系统吞吐量来评价算法的性能；只有少数以公平分 配为目的，采用公平系数来评价算法的性能。然而，这些文献均局限于各自的算法，只有个别论 文分析比较了两至三个算法，均没有对已有算法进行分类和比较分析，没有在各种条件下考察比 较这些算法的性能和适用性。 1 4 本文主要贡献与结构 本文深入研究了o v s f 码的特征及其分配过程，以减少码阻塞和公平分配为两个主要目的， 比较分析了各类分配算法，分别找到了最佳的分配方法。 本文的主要贡献有： 将o v s f 码分配算法分类，合理设计了九种业务模型，并统一算法评价指标。 分析仿真现有的四种单码分配算法，仿真比较了它们的阻塞率、码阻塞率和吞吐量，得 出权重算法为其中最好的算法。 提出一种新的单码分配算法一极左碎片法，是简单、高效和公平的综合性能最好的单 码分配算法。 分析仿真多码分配的两个阶段六种算法，仿真比较了它们的阻塞率、码阻塞率和吞吐量， 2 浙江人学颂l 学位论文 得出多码分配过程中每一阶段每一步最好的算法。 分析仿真现有的= 种保留分配算法，仿真比较了它们的公平系数，得出混合分区法2 为已有的最公平的算法。 提出一种新的保留分配算法一分匮借码法，是最公平、吞吐量最大综合性能最好的保 留分配算法。 本文的后续内容安排如f ： 第二章解释，o v s f 码的产生过程和结构、码阻塞的产生，介绍j - 三种分配的特点，给出了 算法的各评价指标。 第三章设计建立了业务模型，i ：给出仿真方法及其参数设置。 第四、五和六章是本文的蘑点。第四章介绍现有的四种分配算法：随机、极左、紧凑和权重， 通过仿真比较各种分配算法的各吐量、阻塞率和码阻塞率，得出权重算法为其中最好的算法。在 对现有算法局限性研究的基础上，提出综合性能更优的极左碎片分配算法。 第五章介绍了o v s f 多码分配的两个阶段，比较分析了现有的六种算法，通过仿真比较各种 分配算法的吞吐量、阻塞率和码阻塞率，得山多码分配过程中每一阶段每一步最好的算法。 第六章比较分析了o v s f 码保留分配的三种算法，通过仿真比较它们的公平系数，得出混合 分区法2 为其中最公平的算法。在对现有算法局限性研究的基础上，提出更公平、吞吐量更大的 分区借码分配算法。 第七章总结研究工作，展望下一步研究的方向。 3 浙汀大学顺十学位论文 第二章o v s f 码分配及算法评价指标 本章首先讲述了o v s f 码的产生、码树结构、码及码树的弃量、止交性、码的状态和刚阻塞， 接着解释了译码分配、多码分配和保留分配二种分配的过程，最后提出了五个评价算法性能的指 标。这些内容都是后续章1 ，丌展算法研究的基础。 2 1o v s f i 马 正交可变扩频因子( o r t h o g o n a lv a r i a b l es p r e a d i n gf a c t o r , o v s f ) 码是a d a c h i 于1 9 9 7 年提出 的旧，已经被3 g p p 标准化组织采纳为第三代移动通信d s c d m a 系统支持多速率业务的土要方 案之。 2 1 1o v s f 码递归产生的方法 将 ，阶的哈达玛矩阵记为珥”它是一个n n 方阵。n - 2 1 ，i 是一个整数。凰中的第”行的 行向量记为士“”) ，n - 1 ，n 。上“可以由马崛求得q 甘。= ( 1 ) ( 2 ) ( 3 ) ( 4 ) i i t n l 、 h 。( ) 风，：o ) h 。( 1 ) h m m i | m 1 ，：( 2 ) q 。，：( 2 ) h ，2 ( 2 ) 4 ，2 ( 2 ) i j m 心f h m 悄f 2 、 h n j l t nf hh 。( n 2 、 ( 2 - d 式中，且w 2 协) 是n 2 阶的哈达玛矩阵h n a 中第”行的行向量，凰，：( h ) 是岛忸( n ) 的补债。岛v 中的 行向量局“ ) 是一个长度为j v 的沃尔什序列。将坼 ”) 用做d s 4 2 d m a 系统的信道化码，删称其 是扩麴这l ( s p r e a d i n g f a c t o r , s f ) 为 ，的扩频序列，或扩频码。根据( 2 1 ) 式，可递! j _ | 地产生具有树 形结构1 5 】的o v s f 码。 2 1 2 树型结构 由式( 2 - 】) 产生的护频码( o v s f 码) 具有树型结构，如图2 i 所示。其中，图( a ) 是将o v s f 码表示为按层自上而r 排列的一叉树层号七= o ，1 ，2 - - - k ，各层的扩频因子s f - - 2 ；图( b ) 则按层自 左至右排列。尽管实际自k + i 层，习惯上称之为k 层码树。 码树的每个节点表示个o v s f 码；码树的筇k 层( = 0 ，l ，2 ，田包含2 。个码，每个码的匠度 码树的每个诲点表示个o v s f 码；码树的第七层( k - - 0 ，i 2 ，蜘包含2 。个码，每个码的艮度 4 浙江大学坝士学位论文 第二章o v s f 码分配及算法评价指标 本章首先讲述了o v s f 码的产生、码树结构、码及码树的容量、正交性、码的状态和码阻塞， 接着解释了单码分配、多码分配和保留分配二种分配的过程，最后提出了五个评价算法性能的指 标。这些内容都是后续章1 ，开展算法研究的基础。 2 1o v s f 码 正交可变扩频因子( o n h o g o n a lv a r i a b l es p r e a d i n gf a c t o r , o v s f ) 码是a d a c h i 于1 9 9 7 年提出 的嘲，已经被3 g p p 标准化组织采纳为第三代移动通信d s c d m a 系统支持多速率业务的主要方 案之一。 2 1 1o v s f 码递归产生的方法 将阶的哈达玛矩阵记为n ，它是一个n x n 方阵。n = 2 。，i 是一个整数。z “中的第n 行的 行向量记为岛“”) ，n = l ，n 。f 如可以由h n a 求得 h m = 口。( 1 ) 。( 2 ) 风( 3 ) 巩( 4 ) 乩( 一1 ) h m t 风，：( 1 ) 日。，：( 1 ) 风，：( 1 ) 风，：( 1 ) q ，：( 2 ) 日。，：( 2 ) h ，2 ( 2 ) h ，2 ( 2 ) h n | 2 ( n h 2 1 h n | l ( n 2 ) 厅n | 2 ( n 2 ) ( 2 1 ) 式中，h m z ( n ) 是n 2 阶的哈达玛矩阵h n l 2 中第n 行的行向量，t n ，：0 ) 是z 2 ( 月) 的补值。h n 中的 行向量岛“”) 是一个长度为- 的沃尔什序列。将岛k ”) 用做d s - c d m a 系统的信道化码，则称其 是扩频因子( s p r e a d i n gf a c t o r , s f ) 为的扩频序列，或扩频码。根据( 2 - 1 ) 式，可递归地产生具有树 形结构1 5 】的o v s f 码。 2 1 2 树型结构 由式( 2 - 1 ) 产生的扩频码( o v s f 码) 具有树型结构，如图2 1 所示。其中，图( a ) 是将o v s f 码表示为按层自上而r 排列的二叉树，层号t = o ，1 ，2 , - - - k ，各层的扩频因子s f = 2 ；图( b ) 则按层自 左至右排列。尽管实际有翩- 】层，习惯上称之为k 层码树。 码树的每个：符点表示一个o v s f 码；码树的第k 层( 女卸，1 ，2 ，叼包含2 。个码，每个码的艮度 4 浙江大学硕士学位论文 n = 2 匕s f 。一个o v s f 码可以川其所在层的层号k ( k = - 0 ，1 ，2 ，和所在层的位置号n ( n = l ，2 ，肋 完全确定，农示为( 如7 ) 。码树中码的位置可山左至右编号( 图2 1 a ) 或由：至下编号( 图2 1 b ) 。 例如图2 1 a 中( 1 ，1 ) 表示码树第1 层( 仁1 ) 的左起第1 个码，其扩频因子s f = 2 1 = 2 ：图2 1 b 中( 3 ，8 ) 表示码树第3 层的左起第8 个码，其扩频网子s f = 2 3 = 8 。 ( 0 ，1 ) = 1 第k = 0 层，s f = i 第k = l 层，s f = 2 1 1 ，1 ，1 】第k = - 2 层，s f = 4 o 空码。禁码忙码 ( a ) 自上而卜排列的二义树 第k = - k = 3 层s f = 8 f b ) 由左至右排列的二叉树 图2 1o v s r 码的树型结构( k = 3 ) 位于整个码树最顶端的码称为根码( r o o t ) ；位于码树最底层的码称为叶码0 e a f ) 。若码a 是由 上层的码b 递归产生的，则称码a 是码b 的子码( c h i l d ) ，码b 是码a 的5 e 码( f a t b e r ) 。由上层某个 码派生的本层相邻的两个码互为兄弟码( b r o t h e r ) ，称它们为一组，第k 层上共有2 “组，每组有左 右两个码。同层的所有码互称为邻码( n e i g h b o o 。以码树的任一节点为根节点，可递归产生码树 的一个子树( s u b t r e e ) ，该根节点称为子树根码( m o to fs u b t r e e ) 。例如，图2 1 a 中码( o ，1 ) 为根码； 码( 3 ， ) ( f 1 ，2 ，8 ) 为叶码。码( 3 ，8 ) 的父码是( o ，1 ) 、( 1 ，2 ) 和( 2 ，4 ) ；码( 1 ，2 ) 的父码是( o ，1 ) ，子码是( 2 ，4 ) 和( 3 ，8 ) 。码( 3 ，7 ) 和码( 3 ，8 ) 互为兄弟码，它们是一组；码( 2 ，帕( ”= 1 ，2 ，4 ) 互为邻码。以码( 1 ，2 ) 作为 子树根码可产生一个子树，该子树包括( 2 ，3 ) 、( 2 ，4 ) 、( 3 ，5 ) 、( 3 ，6 ) ，( 3 ，7 ) 和( 3 ，8 ) 。 浙江大学硕士学位论文 2 1 3 正交性 分配给每个呼l a t i 的o v s f 码用作信道化码，必须相互止交。码树中具有r 面两种关系的码相 互正交。 1 位丁码树同一层所有的码是相互正交的； 2 码树上任何随个不同层的码，只要彼此没有父f 关系，两者是相互正交的。 2 1 4 码的状态 根据自身及其父码、子码的分配与否，一个码可以处丁三种状态中的一种。已被分配出去的 码称为忙码( b u s yc o d e ) i “1 。因其父码或子码是忙码而不能被分配的码称为禁码( t i e dc o d e ) 。其 余的称为空码( f r e ec o d e ) 。只有处丁空码状态的码才能分配给用户，处于其它两种状态时均不可。 其中，窄码义分为碎片和非碎片，自身为空码但兄弟码是忙码或禁码的称为碎片( f r a g m e n t ) ，否 则为非碎片( n o n f r a g m e n t ) 。如图2 1 a ，( 2 ，2 ) 和( 3 ，5 ) 为忙码；( 0 ，1 ) 、( 1 ，1 ) 、( 1 ，2 ) 、( 2 ，3 ) 、( 3 ，3 ) 和( 3 ，4 ) 为禁码；( 2 ，1 ) 、( 2 ，4 ) 、( 3 ，1 ) 、( 3 , 2 ) 、( 3 ，6 ) 、( 3 ，7 ) 和( 3 ，8 ) 为空码，即只有它们能分配给用户。在所 有的空码中，( 2 ，1 ) 、( 2 ，4 ) 和( 3 ，6 ) 为碎片，( 3 ，1 ) 、( 3 ，2 ) 、( 3 ，7 ) 和( 3 ，8 ) 均为非碎片，可见非碎片总是 成对出现。 当一个忙码使用完毕后就变为空码，称为释放，它的部分父码( 与相同父码的其它码的状态 有关) 和全部子码从禁码变为空码。见图2 1 a ，如果码( 2 ，2 ) 被释放后，其父码( 1 ，1 ) 和其子码( 3 ，3 ) 、 ( 3 ，4 ) 三个码的状态都会从禁码变为空码。但( 2 ，2 ) 另一个父码( o ，1 ) 的状态为禁码不变，这是因为( o ，1 ) 的子码( 3 ，5 ) 仍是忙码。 每次码的分配或释放后，系统会及时记录和更新每个码的状态。码树上所有码的状态的集合 称为码树状态。 2 1 5 码及码树的容量 按每个呼叫请求的速率，系统将指配相应 = = 度的码。将码树中叶码支持的速率记为rb p s ， 称叶码的容量为r ，则第t 层的一个码支持的速率为2 ( “rb p s ，也称该码的容量是2 ( k - k 碗。 由于o v s f 码之间的正交性限制，码树总容量等于所有叶码的容量和2 r 。 码树的刺余容量指的是当前o v s f 码树上所有状态为空码的叶码容量之和，也即可分配给 用户的容量总数。码树剩余容量的上限等于码树总容量2 r 。总有用户在使用码，所以码树剩余 容量总小于该上限。 从码资源的角度来看，码树总容量就是系统总容量，码树剩余容量也即系统剩余容量。 6 浙江人学颀l j 学位论义 2 1 6 码阻塞 当新呼叫请求的速率大丁系统剩余容量，圳呼叫被阻塞，称发生，容量阻塞。 若某时刻码树剩余容量足以支持新呼叫请求的速率，但由丁| 忙码在码树中分布较分散，冈正 交性限制造成较多禁码，找不到合适的空码，而不得不拒绝该呼叫，此时呼叫也被阻塞，称发生 了码阻塞【8 1 。 例如，幽2 1 a 中用黑色节点表示忙码，码树剩余容量是5 r 。若此时到达的呼叫请求速率是 4 r ，则由于i q 树不存在容量等于或人于4 r 的空码( s f 2 ，艇1 ) ，所以不得不拒绝该呼叫，发生 了码阻塞。 2 2o v s f 码分配 o v s f 码分配是指，新到呼叫向系统请求其所需的速率，系统为其分配一个或多个o v s f 码 的过程。最终若找到呼叫所需的码则分配成功，否则分配失败。 通信协议的选择与硬件的不同决定r 用户终端所能支持o v s f 码的个数，有的用户终端只能 支持一个码，有的则能支持几个码。因此，为用户分配一个码和多个码的分配过程分别称作单码 分配和多码分配。 高速率呼n u 总比低速率呼叫更容易被阻塞，有时为了顾及不同业务时分配的公平性，系统将 为高速率业务保留一定的码资源这种带有资源预留做法的分配称为保留分配。 f 面对以上三种分配作具体阐述。 2 2 1 单码分配 o v s f 单码分配的每次分配过程只涉及一个码，即从码树中选取一个码给当前呼叫，此码的 容量不小于该呼叫请求的速率。 具体过程是，当一个请求速率为i r ( z r 2 r ) 的呼叫到达时，系统首先判断汛是否大于此 时码树剩余容量，若大于则阻塞该呼叫( 发生容量阻塞) ，否则在支持f r 的码所在的第 觑女= k l o g ：，) 层上，按某种方法选择一个空码给该呼叫。找到则分配成功，否则阻塞该呼叫 ( 发生码阻塞) 。 单码分配应用范围很广，既可支持话音业务( 叶码，s f 最大) ，也可支持数据业务( 小s f 码) ；单码分配不受削户终端支持码个数的限制，可用于任何一种d s c d m a 系统；单码分配硬 件复杂度小，易于实现。 7 浙江大学硕士学位论文 2 2 2 多码分配 多码分配主要用丁- 数据业务。活音业务速率i 剐定，只需用个| | 码支持，但数据业务请求的 速率有多种，速率范围较宽，如果仍分配一个码将造成严重的码阻塞。多码分配可根据用户需求， 灵活分配一个或几个o v s f 码。例如，3 g p p 2 弘议【i ”中，c d m a 2 0 0 0 】x 的前向链路可以有两个补 充信道( s u p p l e m e n tc h a n n e l ，s c h ) 传输数据业务，即能为用户分配一个或两个o v s f 码。 多码分配要求移动终端具有使用多个码传输的能力，即具有多个r a k e 接收机。用户设备 ( u s e re q u i p m e n t ，u e ) 能够支持的多码个数，称为多码能力，记为u ( u 为整数且【硅1 ) 。例 如，3 g p p 2 协议”“规定，c d m a 2 0 0 0l x 中u e 的多码能力u 为2 。与单码分配方案相比，多码分 配的硬件复杂度较大，不易实现。 o v s f 多码分配每次分配过程涉及多个码的联合确定，即从码树中选取多个码给当前呼叫， 这些码的容量和不低于呼n q 请求的速率。这多个码相互正交，可以等长( 码树上同一层) ，也可 以不等长( 码树上不同层) ，这与1 2 节中的m c - - c d m a 不同，m c - - c d m a 方案中的分配给 用户的多个码是等长码。 o v s f 多码分配的过程较单码分配要复杂。具体过程是，当一个请求速率为承( i r 2 k r ) 的呼叫到达时，系统首先判断爪是否大丁此时码树剩余容量，若大于则阻塞该呼叫( 发生容量 阻塞) ，否则依次进入下面两个阶段开始分配，如图2 2 。 j 每层分配几个码)ll( 层中的位置号) l 图2 2 多码分配的两个阶段 1 确定分配码字阶段，系统按某种方法确定码树上每层各分配几个码给呼叫，它们的和就是 分配给该呼叫总的码的个数； 2 确定码的位置阶段，按某种方法选择该层的哪j l 个码给呼叫。若能找到所有这些码则分配 成功，否则阻塞该呼叫( 发牛码阻塞) 。 2 2 3 保留分配 o v s f 码保留分配事先为每一类请求速率的呼叫按某个方法预留一定码资源，以免分配过程 中被其它类的呼叫抢占，使系统对所有的呼叫公平分配。 具体过程是，当一个请求速率为i r ( r 2 x r ) 的呼r t q 蛰j 达时，系统首先判断浓是否大于此 时系统为该类呼叫所保留资源中的剩余容量，若人于则阻塞该呼叫( 发生容量阻塞) ，否则进入 上面的瞽码分配过程( 多码能力( ，为1 时) 或多码分配过程( 多码能力口人于j 时) 。 已有的保留分配比单码分配和多码分配只多了分配前预留资源的步骤，后面的过程完全一 样。重要的是，保留分配站在用户的角度上考虑，体现了“以人为本”。 8 浙江人学硕j 一学位论文 2 2 4o v s f 分配算法 单码分配、多码分配和保留分配中的采州的方法分别称为单码分配算法、多码分配算法和保 留分配算法。矗_ f = 的单码分配算法和多码分配算法能有效减少码阻塞；好的保留算法能使分配过程 更公平。 2 3 分配算法评价指标 本文采用吞吐量、阻塞率和码阻塞率三个指标米评价单码、多码算法在减少码阻塞上的性能； 采用公平系数来评价保留算法在公平分配上的性能；采用计算复杂度来评价三种单码分配算法在 计算量上的性能。 2 3 1 吞吐量r 吞吐量描述系统的承载能力，定义为单位时问里系统传输的数据量。鉴于系统接纳的呼叫所 请求的速率是以r 为基本单位，所以本文采用归一化吞吐量，单位是r s ，用以表示单位时间内 系统接纳呼叫所请求的速率之和。定义式见式( 2 2 ) 。 e ( 2 2 ) 式中，r , - - 2 k r 为第i 次呼叫请求的速率， 为第i 次呼叫的服务时间。分母对时间的求和表明吞 吐量是一段时间内的平均值。系统吞吐量的上限就是码树总容量2 k r ，对应于最理想的情况，即 单位时间内系统码树上的码没有任何空码，全部码资源被充分利用。大多数情况下吞吐量均小于 码树总容量，即r 2 5 。 各吐量数值上代表被用户使用的容量和，是一段时间内的平均值，表征了码资源利用程度的 大小，t 2 x 即为码资源利用率。 吞吐量的数值与负载的轻重、呼叫请求速率类型、码分配算法以及码树大小有关。在其它条 件相同，只有分配算法不同的前提下，大的吞吐量表示该算法能有效减少码阻塞，充分利用码资 源。这是因为当码阻塞较少时，系统能接纳更多的高速率呼叫，使式( 2 - 2 ) 中的相同的分母下分子 越人，即吞吐量越大。 2 3 2 阻塞率p b 阻塞率定义为被系统阻塞的呼叫数与总呼叫数之比，无量纲。这里阻塞包括容量阻塞和码 阻塞。阻塞率是每个呼叫到达时被阻塞的概率。 9 浙江火学硕+ 学位论文 码阻塞率的数值1 j 负载的轻重、呼叫请求速率类型、码分配算法有关。在其它条件相同， 只有分配算法不同的前提f ，小的阻塞率嵌示该算法总体阻塞呼叫的个数较少，同等时间内能为 更多的呼叫分配码资源。由丁阻塞包括容量阻塞和码阻塞，所以阻塞率并不直接反映算法在减少 码阻塞上面的性能。 2 3 3 码阻塞率j c b 码阻塞率定义为i 鲥码阻塞而末接纳的呼叫个数与呼叫总数之比，无量纲。 码阻塞率的数值与负载的轻重、呼叫请求速率类型、码分配算法有关。在其它条件相同， 只有分配算法不浏的前提下，码阻塞率直接反映算法在减少码阻塞卜面的性能，小的码阻塞率表 示该算法能有效地减少码阻塞。 2 3 4 公平系数f 本文采用公平系数一”1 来表征系统对业务的公平性 ，：黠烈1j 卜b ( ，) 】2 ( 2 - 4 ) j t i r ，2 kj 式中o f 1 ，越接近1 表示系统越“公平”，即请求各种速率的呼叫的接入成功率越接近；式 中，聊) 为请求速率为，的呼叫的阻塞率，j 的取值区间由呼叫请求的速率类型决定，j 是速率类 型的总数。例如，当呼叫请求的速率类型共有l r 、2 r 、4 r 和8 r 四种时，则，e 1 r ，2 r , 4 r , 8 r ， j = 4 。 码阻塞率的数值与负载的轻重、呼叫请求速率类型、码分配算法有关。在其它条件相同， 只有分配算法不同的前提r ，公平系数越接近i 的表示该算法使系统在对待不同种类业务时越公 平。 2 3 5 计算复杂度 因步骤不同，不同的分配算法的计算复杂度也不一样。计算复杂度小的算法能使分配过程更 快速，用户等待的时间更少。第4 4 1 小节用选择一个空码平均所需时间来定量分析比较三种单