OVSF码保留分配算法研究

杨恺

【摘要】提出1种为每类呼叫预留资源的信道化码分配算法。将新算法与已有的单一分区法、混合分区法1、混合分区法2等保留算法进行比较,计算机仿真表明,分区借码法在公平性和码阻塞率方面最好,是公平和吞吐量最好的保留算法。该算法简单、有效和公平，可应用于以OVSF码作为信道化码的各种DS-CDMA系统。

【关键词】直接序列扩频码分多址正交可变长扩频因子保留分配算法

直接序列扩频码分多址是当今移动通信系统空中接口的重要技术，是实现无线多媒体通信的关键。它采用正交可变扩频因子（OVSF）码作为信道化码，正交性的限制与码资源有限导致了码阻塞[1]现象。码阻塞降低了码资源的利用率，还使大部分码资源被低速率呼叫抢夺，使分配过程对高速率呼叫不公平。对用户而言，码分配算法应对各种速率的呼叫都公平对待。现有的单一分区法中全部的码资源由各类呼叫独立占用，发生阻塞时各区域剩余的资源不能共享;混合分区法中资源的共享程度不够充分，且总有利于高速率呼叫。本文提出的分区借码法可以将“最空闲”的资源分配给“最有需要”的呼叫，吞吐量更大，分配更公平。

一、OVSF码和保留分配算法

如图1所示，码树的每个节点表示1个OVSF码。1个OVSF码可以用其所在层的层号k（k=0，1，2，…K）和层中所处的位置号n（n=1，2，…N）完全确定，记为（k，n）。若码a是由上层的码b派生的，则a是b的子码，b是a的父码。由上层某个码派生的本层相邻的2个码互为兄弟码。被分配出去的码称为忙码。因其父码或子码是忙码而不能被分配的码称为禁码。其余的称为空码。有时系统的容量足以支持新呼叫请求的速率，但由于被占用的码分布较分散，被禁用的码较多，无法找到与呼叫请求的速率对应的码，不得不阻塞此呼叫，这种阻塞称为码阻塞。码阻塞降低了码资源的利用率，造成系统资源浪费。

按照算法的目的分类，可分为①以减少码阻塞为目的（从系统的角度）的单码分配算法和多码分配算法；②以公平分配为目的（从用户的角度）的保留分配算法。

1.1单一分区算法

按照各速率呼叫的发生概率，将码树分为无重叠的若干区域，每个区支持一种速率，区数等于速率类型数,使所有速率的呼叫的阻塞率趋同。例如，对于各速率呼叫的个数比为1R:2R:4R:8R=8:4:2:1，称之为速率模型A，容量比为1:1:1:1，对码树进行等容量分区[2]，各区的码个数之比为8:4:2:1，如图2。

但是，单一分区法下码树并不总能精确地按照各速率呼叫的发生概率来划分，并且分配过程中各速率呼叫的发生概率比例会有变化，事先划分好的每个区域不能与之匹配。因此，单一分区法很不灵活。

1.2混合分区算法

参考各速率呼叫的发生概率，将码树分为有部分重叠的若干区域，区数等于速率类型数。每个区支持两种以上的速率，重叠区域允许两种速率的呼叫共享，每种速率的呼叫在本区域中没有可空码时有权使用下层相邻重叠区域中的码。例如，当高速率业务比重较大时，将一个5层码树进行混合分区，如图3。图中，为2R、4R和8R保留的区域大小比单一分区大了一倍，速率为iR的呼叫不但可以被分配对应区域中的码，还能被分配iR/2区域中的码。这种混合策略称为混合分区法1[2]。如果重叠区域允许三种速率的呼叫共享,速率为iR的呼叫可以被分配iR/2和iR/4对应区域中的码，这种策略称为混合分区法2[2]， 如图4所示。

单一分区法和混合分区法都预先将码树划区，每区的码只分给对应的呼叫，分配过程中各区域范围不变。

二、分区借码法

每类呼叫的阻塞率相互间越接近，则系统分配时对各类呼叫越公平。本文从码阻塞率切入，提出一种分区借码算法，其思路是将阻塞率低的那类呼叫的码资源借给阻塞率最大的那类呼叫。

算法步骤如下码所述：①用第1节中三种码树分区法的任何一种（如采用单一分区法）将码树分区；②分配过程中更新记录所有类呼叫的阻塞率，并按从小到大排序； ③当一个第j类呼叫在对应区找不到空码时，则判断该类呼叫的阻塞率PB（j）在所有类呼叫的阻塞率中是否最大，若是跳到④，否则跳到⑤；④按阻塞率从小到大依次向其它类呼叫对应的区借码，该区有码可借则跳到⑥。否则，发生阻塞，分配失败，退出；⑤发生阻塞，分配失败，退出；⑥将该区中借得的码分配给该呼叫，分配成功，退出。

三、算法性能分析

3.1公平性

本文采用公平系数来衡量算法对系统公平性的影响，F（0≤F≤1）越接近1 表示系统越“公平”，即各种速率请求的接入成功率越接近。式（1）中，PB ( j ) 为第j（0≤j≤j-1）类请求的阻塞率。阻塞率是所有被系统阻塞的请求数与总请求数之比，包括容量阻塞和码阻塞。

F= （1）

为了找出公平性、吞吐量和阻塞率等方面最好的算法，分别采用单一分区法、混合分区法1和混合分区法2、分区借码法共四种保留分配算法，在速率模型A及相应的系统负荷下运行，统计系统的公平系数、吞吐量和阻塞率，呼叫的到达和离去均为泊松过程。在某个保留区域内寻找空码时均采用极左单码分配算法[3]。系统负荷分别取GA={2.1，4.1，6.2，8.2，10.3}。其中，10.3是公平性最好的借码分区法在阻塞率为10%时的系统负荷值,其它值是它们的20%、40%、60%和80%。

参见图5，四种算法中，系统使用分区借码法时的公平系数F最接近1，说明分区借码法的公平性最好。这是因为分区借码法尽量用阻塞率最小的区中空闲码资源借给阻塞率最大的区，缩小了各类呼叫阻塞率的差距。此外，分区借码法比混合分区法更公平的一个主要原因是具有动态性，它时刻统计着每类呼叫的阻塞率，当某一类呼叫阻塞较多时，其它類呼叫的区域将借码给它，这种做法本身就体现了“公平”;而混合分区法则是在分配前静态地划分码树，分配开始后，高速率呼叫可以借用低速率呼叫的资源，而反之则不行，资源调配的灵活程度相形见绌。

3.2吞吐量和阻塞率

四种算法中，分区借码法的吞吐量最大，阻塞率最小，说明同等条件下分区借码法能接入最多的呼叫。单一分区法中全部码资源由各类呼叫独立占用，发生阻塞时各区域空闲的资源不能共享互借；混合分区法中资源的共享程度不够充分，且总有利于高速率呼叫。分区借码法根据当前各类呼叫的阻塞情况充分共享码资源，将“最空闲”的资源分配给“最有需要”的呼叫，所以吞吐量更大。

四、结论

已有的三种保留分配算法仅根据业务构成的先验知识，在分配开始之前就已划分好资源，因此应付不了变化的实际业务。分区借码算法是对已有的保留分配算法的改进，它先按已有的算法为每类呼叫预留资源，在分配过程中根据每类呼叫的阻塞率的变化，协调空闲的码资源，尽量将阻塞率最低的那类呼叫的码资源借给阻塞率最大那类呼叫，使各类呼叫的阻塞率趋于一致，实现公平分配，同时接入了更多的呼叫。因此，分区借码法是最公平、吞吐量最大、阻塞率最小的保留分配算法。