论文部分内容阅读
【摘要】介绍了现有的两种OVSF多码分配算法，并通过计算机仿真考察了它们在吞吐量、和阻塞率等指标上的性能。仿真结果表明，快速算法和传输所专利算法在吞吐量和阻塞率上的表现一样，但是快速算法更加快速、简单。因此快速算法可广泛应用于以OVSF码作为信道化码的各种DS-CDMA系统中。
【关键词】直接序列扩频码分多址;正交可变长扩频因子;多码分配算法
0.引言
直接序列扩频码分多址是当今移动通信系统空中接口的重要技术，是实现无线多媒体通信的关键。它采用正交可变扩频因子（OVSF）码作为信道化码，正交性的限制与码资源有限导致了码阻塞[1]现象。按照OVSF分配算法涉及码的个数分类，可分为单码分配算法和多码分配算法。单码分配的每次分配过程只涉及一个码，即从码树中选取一个码给当前呼叫，此码的容量不小于该呼叫请求的速率。多码分配主要用于数据业务。话音业务速率固定，只需用一个叶码支持，但数据业务请求的速率有多种，速率范围较宽，如果仍分配一个码将造成严重的码阻塞。多码分配可根据用户需求，灵活分配一个或几个OVSF码。多码分配要求移动终端具有使用多个码传输的能力，即具有多个RA KE接收机。用户设备能够支持的多码个数，称为多码能力，记为U（U为整数且U≥l）。
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 OVSF码树形结构（K=4）
与单码分配只涉及一个码不同，OVSF多码分配的每次分配过程涉及多个码的联合确定，即从码树中选取多个码给当前呼叫，这些码的容量和不低于呼叫请求的速率。当一个呼叫到达时，系统首先判断它请求的速率是否大于此时码树剩余容量，若大于则阻塞该呼叫，否则开始多码分配。
系统码字Ct是一个矢量，Ct（al，a2，a3，a4， a5，a6，a7，a8），表示当前OVSF码树中各层上空码的个数。元素ai的下标i=k+8-K，其中K是码树总层数， k是层序号。元素ai实际上是第k层上的碎片数。例如，9层码树（K=9），a8是叶码层（k=9）上的碎片数。如果某空码（k，n）是碎片，则它的兄弟码也是空码，它和它的兄弟码合并为它们的父码（也是空码），可计入Ct的ai-1，中。依此类推，除了a1外，a2～a8均为相应层上的碎片数。系统码字是一个动态矢量，每次码的分配和释放后都会更新。定义N（Ct）为码树当前空码的个数，N（Ct）= al+a2+a3+a4+a5+a6+a7+a8。定义W（Ct）为“重量”[2]，即系统码字为Ct的码树的可分配容量（单位是R，R是叶码层支持的速率），W（Ct）=al27+a226+a325+a424+a523+a622+a721+a8，在重量W（Ct）一定的条件下，若系统码字Ct左侧元素值越大，表明码树中能支持较高速率的空码越多，重载时码树利用率会越高。分配码字Copt：表征各层上分配给当前呼叫的码数，由多码分配算法计算得出。一次多码分配的结果，会因用户多码能力U的限制而改变。Copt的每一个ai可以是碎片，也可以不是和N（Copt）和W（Copt）分别为Copt中的码的总数与总容量。
1.1 快速算法[2]
此算法中，分配码字Copt经过两次二进制减法即可得到，所以称作快速算法。分配码字Copt =Ct-[Ct-（0，0，0，0，0，0，0，x）]。例如，Ct=（0，0，0，0，0，2，1，3），x=6，则Copt=（0，0，0，0，0，2，l，3）-[（0，0，0，0，0，2，l，3）- （0，0，0，0，0，0，0，6）]=（0，0，0，0，0，2，1，3）-（0，0，0，0，0，l，l，1）=（0，0，0，0，0，1，0，2）。分配后，新的系统码字为Ct1=Ct-Copt=（0，0，0，0，0，l，l，l）。
此算法经过两次二进制减法。第一步Ct1=Ct-（0，0，0，0，0，0，0，x），由于x出现在最低位，减法法则是低位相减、不够则向高位借1，所以Copt1留下的小SF码较多，体现“留小”的特点，符合码树利用率高准则。第二步Copt=Ct- Ct1，同样从低位开始减，不够向高位借，得到的Copt中小SF码较多，体现“码少”的特点，降低对移动终端的多码能力要求。两步配合，实現了高码树利用率前提下的低复杂度。
1.2 传输所专利算法[3]
在码树中从低层到高层逐级预算需要分配码的个数，从而得到Copt。算法描述如下。
假设码树共有K层，记第k层（0≤k≤K）上需要的码数期望值为Xk。设有一呼叫请求的速率为x。首先令k=K和XK=x，分配码字初始化为M={0，0，0，x}，然后在码树中按照从低层向高层的顺序进入下面的步骤。
在当前层（第k层）上分配Mk个码，并计算上一层的码数期望值Xk-1=（Xk-Mk）/2。Mk的取值原则是根据Xk值及该层上空码的总数ak，分配尽可能多的码：
A.如果Xk≤ak， Mk =Xk;
B.如果Xk≤ak且ak≠0，则Mk要么取ak要么取为ak-1， Mk的取值应保证得到的Xk-1值是0或正整数;
C.如果Xk>ak且ak=0，若Xk为偶数， Mk=0;若Xk为奇数，则向高位借1，本层分配l个码（Mk=1），余l个码。其父层上的空码数减l。 当完成码树中第k层的码数预算后，若Xk-1非0，就将k更新为k-1，回到B点，进入父层的码数预算;若Xk-1为0则预算过程结束，至此得M={Mk，0≤k≤K}，即Copt。由于码分配中的码数预算从底层到高层逐级进行，充分利用码树低层上的大SF码;又在需要借位且Xk为偶数（情况C）时直接将其父码分配出去，从而减少分配的码数。这两点分别对应快速算法遵循的“留小”和“码少”两个分配准则。
下面举例说明此算法的具体过程。呼叫请求的总速率x为16，码数序列为Ct=（1，2，3，4，5，0，0，5），初始化时令X8=16。
①先确定底层（第9层）需要分配的码的个数：由于X8>a8且a8≠0，则M8只可能取为a8或是a8-1，而为了保证沂X7=（X8-M8）/2=（16-M8）/2是一个整数，因此M8应取为4，此时X7=6（非0），将进入更高一层即第8层上的分配码个数确定。
②确定第8层需要分配的码的个数：由于a7=0，且X7为偶数，则M7=0，此时X6=3（非0）。
③确定第7层需要分配的码的个数：由于a6=0，且X6为奇数，因此M6=l，这个在第7层上的码是从第6层派生的，记录该情况，将a5修正为5-1=4。此时X5=（X6-M6）/2=1（非0）。
④确定第6层需要分配的码的个数：由于X5<a5，则M5=X5=1，由于此时X4=（X5-M5）/2=0，因此分配的第一过程结束，分配码字为（0，0，0，0，1，1，0，4）。
2.算法性能仿真与分析
为了找出性能最好的多码分配算法，对每种算法在相应的速率模型下及系统负荷下运行仿真，统计系统的吞吐量和阻塞率，呼叫的到达和离去均为泊松过程。仿真中选择三种速率模型模拟呼叫请求，分别为速率模型D、E、F。这三种模型都含有8种速率：1R，2R，3R，4R，5R，6R，7R，8R。其中一些速率可以用一个码或多个码来支持，如2R，4R和8R;另一些速率必须用多个码来满足，如3R，5R，6R和7R。速率模型D中，速率比为8：7：6：5：4：3：2：1。速率模型E中，速率比为1：1：1：1：1：1：1：1。速率模型F中，速率比为1：2：3：4：5：6：7：8。分别在GD，GE，GF三组系统负荷值下运行仿真。
2.1 吞吐量
吞吐量描述系统的承载能力，定义为单位时间里系统传输的数据量。鉴于系统接纳的呼叫所请求的速率是以R为基本单位，所以本文采用归一化吞吐量，单位是R/s，用以表示单位时间内系统接纳呼叫所请求的速率之和。定义式见式（1）。
（1）
式（1）中，Ri=2kR为第i次呼叫请求的速率，ti为第i次呼叫的服务时间。分母对时间的求和表明吞吐量是一段时间内的平均值。系统吞吐量的上限就是码树总容量2KR，对应于最理想的情况，即单位时间内系统码树上的码没有任何空码，全部码资源被充分利用。大多数情况下吞吐量均小于码树总容量，即T≤2KR。吞吐量数值上代表被用户使用的容量和，是一段时间内的平均值，表征了码资源利用程度的大小，T/2K即为码资源利用率。
吞吐量的数值与负载的轻重、呼叫请求速率类型、码分配算法以及码树大小有关。在其它条件相同，只有分配算法不同的前提下，大的吞吐量表示该算法能有效减少码阻塞，充分利用码资源。这是因为当码阻塞较少时，系统能接纳更多的高速率呼叫，使式（1）中的相同的分母下分子越大，即吞吐量越大。
图2是两种多码算法分别在D、E和F三种速率模型下的吞吐量。三张图中的直线是理想情况时的吞吐量与系统负荷的关系曲线，用来与实际情况比较。可以看到所有图中，代表快速算法和传输所专利算法的两条曲线均重叠，说明在快速算法和传输所专利算法下系统的吞吐量均一样。
2.2 阻塞率
阻塞率定义为被系统阻塞的呼叫数与总呼叫数之比，无量纲。这里阻塞包括容量阻塞和码阻塞。阻塞率是每个呼叫到达时被阻塞的概率。码阻塞率的数值与负载的轻重、呼叫请求速率类型、码分配算法有关。在其它条件相同，只有分配算法不同的前提下，小的阻塞率表示该算法总体阻塞呼叫的个数较少，同等时间内能为更多的呼叫分配码资源。
图3是两种多码算法分别在D、E和F三种速率模型下的阻塞率。可以看到所有图中，代表快速算法和传输所专利算法的两条曲线均重叠，说明在快速算法和传输所专利算法下系统的阻塞率均一样。
3.结论
仿真结果表明，快速算法和传输所专利算法在吞吐量和阻塞率上的表现一样，但是快速算法更加快速、简单。因此快速算法可广泛应用于以OVSF码作为信道化码的各种DS-CDMA系统中。
参考文献
[1]Thit Minn， Kai-Yeung Siu.Dynamic assignment of orthogonal variable spreading factor codes in W-CDMA[J]/IEEE Journal on Selected Areas in communications， volume 18， no.8， August 2000， Pages：1429-1440.
[2]Ray-Guang Cheng，Phone Lin，"OVSF code channel assignment for IMT-2000.Vehicular Technology Conference Proceedings"，The 5lst IEEE Vehicular Technology Conference，2000（VTC 2000 Spring），Volume 3.15-18 May 2000，Pages：2188-2192.
[3]何紅永，郭淑明.“正交可变扩频因子码的一种分配方法”[Z].授权发明专利，申请号01131225.4，申请日2001.09.03，公开号1337798，公开日2002.02.27，专利权人：信息产业部电信传输研究所、国家数字交换系统工程技术研究中心（郑州）.
【关键词】直接序列扩频码分多址;正交可变长扩频因子;多码分配算法
0.引言
直接序列扩频码分多址是当今移动通信系统空中接口的重要技术，是实现无线多媒体通信的关键。它采用正交可变扩频因子（OVSF）码作为信道化码，正交性的限制与码资源有限导致了码阻塞[1]现象。按照OVSF分配算法涉及码的个数分类，可分为单码分配算法和多码分配算法。单码分配的每次分配过程只涉及一个码，即从码树中选取一个码给当前呼叫，此码的容量不小于该呼叫请求的速率。多码分配主要用于数据业务。话音业务速率固定，只需用一个叶码支持，但数据业务请求的速率有多种，速率范围较宽，如果仍分配一个码将造成严重的码阻塞。多码分配可根据用户需求，灵活分配一个或几个OVSF码。多码分配要求移动终端具有使用多个码传输的能力，即具有多个RA KE接收机。用户设备能够支持的多码个数，称为多码能力，记为U（U为整数且U≥l）。
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 OVSF码树形结构（K=4）
与单码分配只涉及一个码不同，OVSF多码分配的每次分配过程涉及多个码的联合确定，即从码树中选取多个码给当前呼叫，这些码的容量和不低于呼叫请求的速率。当一个呼叫到达时，系统首先判断它请求的速率是否大于此时码树剩余容量，若大于则阻塞该呼叫，否则开始多码分配。
系统码字Ct是一个矢量，Ct（al，a2，a3，a4， a5，a6，a7，a8），表示当前OVSF码树中各层上空码的个数。元素ai的下标i=k+8-K，其中K是码树总层数， k是层序号。元素ai实际上是第k层上的碎片数。例如，9层码树（K=9），a8是叶码层（k=9）上的碎片数。如果某空码（k，n）是碎片，则它的兄弟码也是空码，它和它的兄弟码合并为它们的父码（也是空码），可计入Ct的ai-1，中。依此类推，除了a1外，a2～a8均为相应层上的碎片数。系统码字是一个动态矢量，每次码的分配和释放后都会更新。定义N（Ct）为码树当前空码的个数，N（Ct）= al+a2+a3+a4+a5+a6+a7+a8。定义W（Ct）为“重量”[2]，即系统码字为Ct的码树的可分配容量（单位是R，R是叶码层支持的速率），W（Ct）=al27+a226+a325+a424+a523+a622+a721+a8，在重量W（Ct）一定的条件下，若系统码字Ct左侧元素值越大，表明码树中能支持较高速率的空码越多，重载时码树利用率会越高。分配码字Copt：表征各层上分配给当前呼叫的码数，由多码分配算法计算得出。一次多码分配的结果，会因用户多码能力U的限制而改变。Copt的每一个ai可以是碎片，也可以不是和N（Copt）和W（Copt）分别为Copt中的码的总数与总容量。
1.1 快速算法[2]
此算法中，分配码字Copt经过两次二进制减法即可得到，所以称作快速算法。分配码字Copt =Ct-[Ct-（0，0，0，0，0，0，0，x）]。例如，Ct=（0，0，0，0，0，2，1，3），x=6，则Copt=（0，0，0，0，0，2，l，3）-[（0，0，0，0，0，2，l，3）- （0，0，0，0，0，0，0，6）]=（0，0，0，0，0，2，1，3）-（0，0，0，0，0，l，l，1）=（0，0，0，0，0，1，0，2）。分配后，新的系统码字为Ct1=Ct-Copt=（0，0，0，0，0，l，l，l）。
此算法经过两次二进制减法。第一步Ct1=Ct-（0，0，0，0，0，0，0，x），由于x出现在最低位，减法法则是低位相减、不够则向高位借1，所以Copt1留下的小SF码较多，体现“留小”的特点，符合码树利用率高准则。第二步Copt=Ct- Ct1，同样从低位开始减，不够向高位借，得到的Copt中小SF码较多，体现“码少”的特点，降低对移动终端的多码能力要求。两步配合，实現了高码树利用率前提下的低复杂度。
1.2 传输所专利算法[3]
在码树中从低层到高层逐级预算需要分配码的个数，从而得到Copt。算法描述如下。
假设码树共有K层，记第k层（0≤k≤K）上需要的码数期望值为Xk。设有一呼叫请求的速率为x。首先令k=K和XK=x，分配码字初始化为M={0，0，0，x}，然后在码树中按照从低层向高层的顺序进入下面的步骤。
在当前层（第k层）上分配Mk个码，并计算上一层的码数期望值Xk-1=（Xk-Mk）/2。Mk的取值原则是根据Xk值及该层上空码的总数ak，分配尽可能多的码：
A.如果Xk≤ak， Mk =Xk;
B.如果Xk≤ak且ak≠0，则Mk要么取ak要么取为ak-1， Mk的取值应保证得到的Xk-1值是0或正整数;
C.如果Xk>ak且ak=0，若Xk为偶数， Mk=0;若Xk为奇数，则向高位借1，本层分配l个码（Mk=1），余l个码。其父层上的空码数减l。 当完成码树中第k层的码数预算后，若Xk-1非0，就将k更新为k-1，回到B点，进入父层的码数预算;若Xk-1为0则预算过程结束，至此得M={Mk，0≤k≤K}，即Copt。由于码分配中的码数预算从底层到高层逐级进行，充分利用码树低层上的大SF码;又在需要借位且Xk为偶数（情况C）时直接将其父码分配出去，从而减少分配的码数。这两点分别对应快速算法遵循的“留小”和“码少”两个分配准则。
下面举例说明此算法的具体过程。呼叫请求的总速率x为16，码数序列为Ct=（1，2，3，4，5，0，0，5），初始化时令X8=16。
①先确定底层（第9层）需要分配的码的个数：由于X8>a8且a8≠0，则M8只可能取为a8或是a8-1，而为了保证沂X7=（X8-M8）/2=（16-M8）/2是一个整数，因此M8应取为4，此时X7=6（非0），将进入更高一层即第8层上的分配码个数确定。
②确定第8层需要分配的码的个数：由于a7=0，且X7为偶数，则M7=0，此时X6=3（非0）。
③确定第7层需要分配的码的个数：由于a6=0，且X6为奇数，因此M6=l，这个在第7层上的码是从第6层派生的，记录该情况，将a5修正为5-1=4。此时X5=（X6-M6）/2=1（非0）。
④确定第6层需要分配的码的个数：由于X5<a5，则M5=X5=1，由于此时X4=（X5-M5）/2=0，因此分配的第一过程结束，分配码字为（0，0，0，0，1，1，0，4）。
2.算法性能仿真与分析
为了找出性能最好的多码分配算法，对每种算法在相应的速率模型下及系统负荷下运行仿真，统计系统的吞吐量和阻塞率，呼叫的到达和离去均为泊松过程。仿真中选择三种速率模型模拟呼叫请求，分别为速率模型D、E、F。这三种模型都含有8种速率：1R，2R，3R，4R，5R，6R，7R，8R。其中一些速率可以用一个码或多个码来支持，如2R，4R和8R;另一些速率必须用多个码来满足，如3R，5R，6R和7R。速率模型D中，速率比为8：7：6：5：4：3：2：1。速率模型E中，速率比为1：1：1：1：1：1：1：1。速率模型F中，速率比为1：2：3：4：5：6：7：8。分别在GD，GE，GF三组系统负荷值下运行仿真。
2.1 吞吐量
吞吐量描述系统的承载能力，定义为单位时间里系统传输的数据量。鉴于系统接纳的呼叫所请求的速率是以R为基本单位，所以本文采用归一化吞吐量，单位是R/s，用以表示单位时间内系统接纳呼叫所请求的速率之和。定义式见式（1）。
（1）
式（1）中，Ri=2kR为第i次呼叫请求的速率，ti为第i次呼叫的服务时间。分母对时间的求和表明吞吐量是一段时间内的平均值。系统吞吐量的上限就是码树总容量2KR，对应于最理想的情况，即单位时间内系统码树上的码没有任何空码，全部码资源被充分利用。大多数情况下吞吐量均小于码树总容量，即T≤2KR。吞吐量数值上代表被用户使用的容量和，是一段时间内的平均值，表征了码资源利用程度的大小，T/2K即为码资源利用率。
吞吐量的数值与负载的轻重、呼叫请求速率类型、码分配算法以及码树大小有关。在其它条件相同，只有分配算法不同的前提下，大的吞吐量表示该算法能有效减少码阻塞，充分利用码资源。这是因为当码阻塞较少时，系统能接纳更多的高速率呼叫，使式（1）中的相同的分母下分子越大，即吞吐量越大。
图2是两种多码算法分别在D、E和F三种速率模型下的吞吐量。三张图中的直线是理想情况时的吞吐量与系统负荷的关系曲线，用来与实际情况比较。可以看到所有图中，代表快速算法和传输所专利算法的两条曲线均重叠，说明在快速算法和传输所专利算法下系统的吞吐量均一样。
2.2 阻塞率
阻塞率定义为被系统阻塞的呼叫数与总呼叫数之比，无量纲。这里阻塞包括容量阻塞和码阻塞。阻塞率是每个呼叫到达时被阻塞的概率。码阻塞率的数值与负载的轻重、呼叫请求速率类型、码分配算法有关。在其它条件相同，只有分配算法不同的前提下，小的阻塞率表示该算法总体阻塞呼叫的个数较少，同等时间内能为更多的呼叫分配码资源。
图3是两种多码算法分别在D、E和F三种速率模型下的阻塞率。可以看到所有图中，代表快速算法和传输所专利算法的两条曲线均重叠，说明在快速算法和传输所专利算法下系统的阻塞率均一样。
3.结论
仿真结果表明，快速算法和传输所专利算法在吞吐量和阻塞率上的表现一样，但是快速算法更加快速、简单。因此快速算法可广泛应用于以OVSF码作为信道化码的各种DS-CDMA系统中。
参考文献
[1]Thit Minn， Kai-Yeung Siu.Dynamic assignment of orthogonal variable spreading factor codes in W-CDMA[J]/IEEE Journal on Selected Areas in communications， volume 18， no.8， August 2000， Pages：1429-1440.
[2]Ray-Guang Cheng，Phone Lin，"OVSF code channel assignment for IMT-2000.Vehicular Technology Conference Proceedings"，The 5lst IEEE Vehicular Technology Conference，2000（VTC 2000 Spring），Volume 3.15-18 May 2000，Pages：2188-2192.
[3]何紅永，郭淑明.“正交可变扩频因子码的一种分配方法”[Z].授权发明专利，申请号01131225.4，申请日2001.09.03，公开号1337798，公开日2002.02.27，专利权人：信息产业部电信传输研究所、国家数字交换系统工程技术研究中心（郑州）.