用于基于优先权的具有可变调度周期和可变调度周期的调度器的方法、工作站和存储程序的介质

摘要

一种用于时间可调的基于优先权的调度器的系统和方法。利用可变的调度延续时间的灵活的调度算法能获取更好的系统容量利用。若数据到达缓存器中，在该缓存器中的数据超过缓存器深度，并且存在足够的功率以按照所请求的速率进行发送，则发送速率请求(408)。响应于该速率请求的速率分配(418)指示调度延续时间和可用于该调度延续时间的调度速率。调度延续时间小于或等于调度周期(508)。调度周期是一个时间间隔，在该时间间隔后调度器进行调度决定。调度周期是可变的和调度延续时间是可变的。优选将调度器应用到UMTS、CDMA2000或者HDR系统以进行反向链路速率调度。

说明书

根据35U.S.C.§119的优先权

本专利申请要求2003年1月13日提交、题目为“System andmethod for a Time-scalable Priority-Based Scheduler”的临时申请No.60/439,989的优先权，该临时申请被转让给其受让人，因而在此将其明确地引入，以作参考。

技术领域

本公开的实施例通常涉及无线通信，并且尤其涉及通信系统中时间可调的基于优先权的调度器。

背景技术

通信领域有许多应用，包括例如寻呼、无线本地环、网络电话和卫星通信系统。一种典型应用是用于移动用户的蜂窝电话系统(如这里所使用的，术语“蜂窝系统”包括蜂窝和个人通信服务(PCS)两种系统频率)。已经为这样的蜂窝系统研发了多种现代通信系统，所述现代通信系统被设计为允许多个用户接入共同的通信媒体。这些现代通信系统可以基于码分多址(CDMA)、时分多址(TDMA)、频分多址(FDMA)、空分多址(SDMA)、极分多址(PDMA)和本领域公知的其它调制技术。这些调制技术对从通信系统的多个用户接收的信号进行解调，从而能够增加通信系统的容量。在与之的连接中，已经建立起各种无线系统，包括例如高级移动电话服务(AMPS)、全球移动通信系统(GSM)和一些其它无线系统。

在FDMA系统中，将所有的频带分成许多较小的子带，给每个用户分配其自己的子带以接入通信媒体。或者，在TDMA系统中，在周期再现的时隙期间给每个用户分配整个频带。CDMA系统提供比其它类型系统更好的潜在优点，包括增大的系统容量。在CDMA系统中，在全部时间里给每个用户分配整个频带，但通过使用惟一的码字来区分其传输。

可以将CDMA系统设计为支持一个或多个CDMA标准，诸如(1)“TIA/EIA-95-B Mobile Station-Base Station Compatibility Standard forDual-Mode Wideband Spread Spectrum Cellular System”(IS-95标准)，(2)由名为“第3代合作伙伴计划”(3GPP)的联盟提供并以一组文档体现的标准(W-CDMA标准)，该组文档包括文档No.3G TS25.211、3G TS 25.212、3G TS 25.213和3G TS 25.214，(3)由名为“第3代合作伙伴计划2”(3GPP2)的联盟提供并以“TR-45.5 PhysicalLayer Standard for cdma2000 Spread Spectrum Systems”(IS-2000标准)体现的标准，以及(4)一些其它标准。

在上述所提到的CDMA通信系统和标准中，在许多用户之间同时共享可用频带，并且使用诸如软切换这样的技术来维持足够的质量以支持延时—敏感的服务，诸如语音。数据服务也可以实现。最近，已经提出了一些系统，该系统通过使用更高阶调制、来自移动台的载干比(C/I)的极快反馈、极快调度以及对较为宽松的延时要求的服务进行调度来提高数据服务的容量。利用这些技术的此种仅传数据(data-only)的通信系统的一个例子是高速数据速率(HDR)系统，其符合TIA/EIA/IS-856标准(IS-856标准)。

不同于其它上述所提到的标准，IS-856系统使用每个小区中可用的整个频带以在一个时间上将数据传输给单个用户。在确定服务哪个用户中使用的一个因子是链路质量。通过使用链路质量作为用于选择服务哪个用户的因子，当信道好时系统将较多比例的时间花费在以更高的速率发送数据上，从而避免使资源用于支持以效率低的速率进行的传输。最终的效果是更高的数据容量、更高的峰值数据速率和更高的平均吞吐量。

系统能够既支持延时敏感的数据，诸如在IS-2000标准中支持的语音信道或数据信道，也支持诸如在IS-856标准中描述的分组数据服务。在一个提案中描述了一个这样的系统，该提案由LG电子公司、LSI Logic公司、朗讯技术公司、北电网络公司、高通公司和三星公司联合提交给第3代合作伙伴计划2(3GPP2)。该提案在下述文档中有详细描述：2001年6月11日提交给3GPP2的文档编号为C50-20010611-009、题目为“Updated Joint Physical Layer Proposal for1xEV-DV”的文档；2001年8月20日提交给3GPP2的文档编号为C50-200100820-011、题目为“Results of L3NQS Simulation Study”的文档；以及2001年8月20日提交给3GPP2的文档编号为C50-20010820-012、题目为“System Simulation Results for the L3NQSFramework Proposal for cdma2000 1x-EVDV”的文档。这些文档后来都称作1xEV-DV提案。

对于反向链路上更有效的容量利用，多级调度是有用的。在像基站控制器(BSC)的中央实体上执行调度时的典型方案中，使用长的调度周期，这是因为：

a)调度的集中特性给出的大随机回程延时；和

b)同时调度多个移动终端(MS)的请求/许可开销。

然而，固定速率的长的调度延续时间具有以下缺点：

●在其缓存器中具有少量数据的移动终端不能在长的调度延续时间内进行高速传输。利用低的速率分配，就不能有效地利用容量；

●长的调度延续时间增加更长周期的数据受限的停止传输(DTX)的概率，因此浪费容量；以及

●平均分组延时大。

因此，为了最大化系统容量利用，使用可变调度延续时间的灵活调度算法可能更有用。

发明内容

这里所公开的实施例提供一种用于通信系统中时间可调的基于优先权的调度器的系统和方法。

在一个方面中，调度方法包括：若数据到达缓存器中，在该缓存器中的数据超过缓存器深度，并且存在足够的功率来按照所请求的速率进行发送，则发送速率请求；接收该速率请求；发送响应于该速率请求的速率分配，该速率分配指示调度延续时间和用于该调度延续时间的调度速率；接收该速率分配；以及，发送数据，该发送响应于该速率分配，其中在该调度延续时间内按照该调度速率持续地发送该数据。

在一个方面，调度方法包括：接收速率请求；发送响应于该速率请求的速率分配，该速率分配指示调度延续时间和用于该调度延续时间的调度速率；以及，在该调度延续时间内按照该调度速率持续地接收数据。

在另一方面，发送数据的方法包括：若数据到达缓存器中，在该缓存器中的数据超过缓存器深度，并且存在足够的功率来按照所请求的速率进行发送，则发送速率请求；接收响应于该速率请求的速率分配，该速率分配指示调度延续时间和用于该调度延续时间的调度速率；以及，发送数据，该发送响应于该速率分配，其中在该调度延续时间内按照该调度速率持续地发送该数据。

在一个方面，所述调度延续时间是最小的调度延续时间的整数倍。在一个方面，所述调度延续时间小于或等于调度周期，其中该调度周期是一个时间间隔，在该时间间隔后调度器进行调度决定。在一个方面中，调度周期是可变的。在一个方面中，调度延续时间是可变的。

附图说明

图1举例说明了具有三个移动台和两个基站的无线通信系统的一个实施例；

图2示出了按照一个实施例的由于R-SCH上的速率变化导致的设置点调整；

图3示出了按照一个实施例的调度延时定时；

图4示出了反向链路上移动台调度中的相关参数；

图5举例说明了按照一个实施例在第j扇区中的第k个MS的速率确定过程；

图6是按照一个实施例的基站的方框图；以及

图7是按照一个实施例的移动台的方框图。

详细描述

这里所使用的词语“典型的”是指“用作一个范例、实例和例子”。这里描述为“典型的”的任何实施例不应必须解释为优于其他实施例或比其他实施例具有优势。

无线通信系统可以包括多个移动台和多个基站。图1举例说明了具有三个移动台10A、10B、10C和两个基站12的无线通信系统的一个实施例。在图1中，该三个移动台显示为安装在车辆10A中的移动电话单元、便携式远程计算机10B和诸如可以在无线本地环或仪表读数系统中发现的固定位置单元10C。移动台可以是任何类型的通信单元，例如手持个人通信系统单元、诸如个人数据助理此类的便携式数据单元或者诸如仪表读数设备此类的固定位置数据单元。图1示出了从基站12到移动台10的前向链路14和从移动台10到基站12的反向链路16。

当移动台运动通过物理环境时，如在移动台和基站处所接收的，信号路径的数量和在这些路径上的信号强度经常发生变化。因此，一个实施例中的接收机使用称作搜索器元件的专用处理元件，该搜索器元件不断地扫描时域中的信道以确定在多径环境中存在信号、信号的时间偏移和信号的信号强度。搜索器元件也称为搜索引擎。搜索器元件的输出提供信息以用于确保解调元件跟踪最有利的路径。

在已转让给本发明的受让人的、1996年2月6日公布的、题目为“Demodulation Element Assignment in a System Capable of ReceivingMultiple Signals”的美国专利No.5,490,165中，描述了用于将解调元件分配给移动台和基站的一组可用信号的方法和系统。

当多个移动台同时发送时，来自一个移动台的无线电传输成为另一移动台的无线电传输的干扰，从而限制在反向链路(也称为上行链路)上可取得的吞吐量。为了有效地利用反向链路上的容量，1999年6月22日公布的、题目为“Method and Apparatus for Reverse LinkRate Scheduling”的美国专利No.5,914,950和1999年7月13日公布的、题目为“Method and Apparatus for Reverse Link Scheduling”的美国专利No.5,923,650已经介绍了在基站处的集中调度，这两个美国专利都已转让给本发明的受让人。

在一个典型实施例中，执行多级调度。在一个实施例中，多级调度包括基站级调度、选择器级调度和/或网络级调度。

在一个实施例中，灵活的调度算法的详细设计基于基本的理论原理：使用可由基站得到或测量的现有网络参数来限制反向链路系统容量。

在一个实施例中，对每个移动台的容量贡献的基站估计基于在给定的当前传输速率下测量的信号噪声之比(SNR)或统称为(Ecp/Nt)的导频能量与噪声加干扰之比(Ecp/(Io+No))。在已转让给本发明的受让人的、2001年11月5日提交的题目为“Method and Apparatus forDetermining Reverse Link Load Level for Reverse Link Data RateScheduling in a CDMA Communication System”的美国申请No.10/011,519中，披露了来自多径环境中所有分支的导频Ecp/Nt的测量。

根据对不同信道上处于当前速率的导频Ecp/Nt的测量值，对在这些信道上处于新的速率的移动台的容量贡献进行估计。

在一个实施例中，对移动台的速率分配请求区分优先次序。基于所执行的调度级别，维持调度器负责调度的所有移动台的列表。在一个实施例中，对于所有移动台，存在一个列表。或者，对于所有移动台，存在两个列表。如果调度器负责调度一个移动台在其激活集中所拥有的所有基站，则该移动台属于第一列表。可以维持分立的第二列表，以用于在其激活集中具有调度器不负责调度的基站的那些移动台。基于各种报告的、测量的或已知的参数来对移动台的速率请求区分优先次序，该参数最大化系统吞吐量，同时考虑移动台公平和他们的重要状态。

在一个实施例中，使用贪婪填充(Greedy Filling)方法。在GreedyFilling方法中，最高优先权移动台获得可用的扇区容量。将分配给该移动台的最高速率确定为该移动台能够发送的最高速率。在一个实施例中，基于所测量的SNR确定最高速率。在一个实施例中，基于Ecp/Nt来确定最高速率。在一个实施例中，还基于限制参数来确定最高速率。在一个实施例中，通过移动台的缓存器估计来确定最高速率。选择高速率减少传输延时和减少发射移动台所观察到的干扰。剩余的扇区容量分配给下一个具有较低优先权的移动台。由于减少干扰同时最大化容量利用，所以这种方法有助于最大化增益。

通过选择不同的优先权函数，可以基于指定的成本度量(merit)将Greedy Filling算法调整成常规的轮询、比例公平或最不公平调度。在考虑调度分级的情况下，上述方法有助于最大化容量利用。

移动台通过向基站发送请求消息来发起呼叫。一旦移动台从基站收到信道分配消息，其能够使用逻辑专用信道与基站进一步通信。在调度系统中，当移动台有数据要发送时，其能通过在反向链路上发送请求消息来发起在该反向链路上的高速数据传输。

考虑当前在IS2000 C版本中指定的速率请求和速率分配。但是，对于本领域技术人员显而易见的是本设计的范围不局限于IS2000。对于本领域技术人员显而易见的是，可以在具有用于速率分配的集中调度器的任何多址系统中实现实施例。

移动台过程

在一个实施例中，移动台(MS)至少支持以下信道的同时操作：

1、反向基本信道(R-FCH)

2、反向补充信道(R-SCH)

反向基本信道(R-FCH)：当仅传语音的MS具有激活的语音呼叫时，在R-FCH上承载该语音呼叫。对于仅传数据的MS，R-FCH承载信令和数据。在2002年6月的TIA/EIA-IS-2000.2，“MobileStation-Base Station Compatibility Standard for Dual-Mode WidebandSpread Spectrum Cellular System”中，规定了典型的R-FCH信道帧长度、编码、调制和交织。

在一个典型的实施例中，当MS不在R-FCH上发送语音、数据或信令时，零速率的R-FCH用于外环功率控制(PC)。零速率意味着最低速率。即使R-SCH上没有传输，也可以使用最低速率的R-FCH来维持外环功率控制。

反向补充信道(R-SCH)：按照一个实施例，MS支持用于分组数据传输的一个R-SCH。在一个典型实施例中，R-SCH使用由TIA/EIA-IS-2000.2中的无线配置(RC3)指定的速率。

在只支持单个数据信道(R-SCH)的一个实施例中，在控制信道上进行信令和功率控制。或者，只要R-SCH存在，就通过R-SCH承载信令和在R-SCH上承载外环功率控制。

在一个实施例中，移动台进行以下过程：

●多信道调整增益

●非连续传输和可变补充调整增益

●R-CQICH和其它控制信道的开销传输

●闭环功率控制(PC)命令

●在5-ms R-FCH上使用补充信道请求微型消息(SCRMM)或在20-ms R-FCH上使用补充信道请求消息(SCRM)的速率请求

多信道调整增益：当R-FCH和R-SCH同时激活时，执行在TIA/EIA-IS-2000.2中指定的多信道增益表调整以维持R-FCH正确的传输功率。所有信道速率的业务与导频(T/P)比在附录A的标称属性增益表中还被指定为标称属性增益值。业务与导频比意味着业务信道功率与导频信道功率之比。

非连续传输和可变补充调整增益：在每个调度周期可以由调度器将R-SCH速率分配给MS。当MS没有被分配R-SCH速率时，其在R-SCH上将不发送任何东西。如果MS被分配来在R-SCH上发送，但是其没有任何数据或足够的功率来按照所分配的速率进行发送，则其停止在R-SCH上发送。如果系统允许，则MS在R-SCH上自发地按照比所分配的速率低的速率进行发送。在一个实施例中，该可变速率R-SCH操作伴随着由TIA/EIA-IS-2000.2中所指定的可变速率SCH增益调整。假设所接收的导频SNR高得足以支持R-SCH上所分配的速率，调整R-FCH T/P。

R-CQICH和其它控制信道的开销传输：通过执行多信道增益调整来维持R-CQICH(或控制信道)正确的传输功率，仅传数据的MS按照CQICH与导频(或者控制与导频)(C/P)之比在CQICH和/或其他控制信道上发送额外的功率。处于软切换的MS的(C/P)值可以不同于未处于软切换的MS的(C/P)值。(C/P)表示由控制信道使用的总功率与没有进行多信道增益调整时的导频功率之比。

闭环功率控制(PC)命令：在一个实施例中，MS从其激活集内的所有基站(BS)中按照800Hz的速率为每一个功率控制组(PCG)接收一个PC命令。在反向业务信道和反向导频信道上PCG为1.25ms间隔。在合并了来自于同地协作的BS(给定小区中的扇区)的PC命令后，基于“Or-of-Downs”规则对导频功率进行+-1dB的更新。

利用两种方法之一进行速率请求。在第一种方法中，在TIA/EIA-IS-2000.5规定的5-ms R-FCH上利用补充信道请求微型消息(SCRMM)来执行速率请求。

在5-ms R-FCH上的补充信道请求微型消息(SCRMM)：在一个实施例中，每个SCRMM传输为24比特(或者具有速率为9.6kbps的每个5-ms FCH帧中的物理层帧开销的48比特)。

MS在5ms的任意周期间隔中发送SCRMM。如果需要发送5-msSCRMM，则MS中断当前20-ms R-FCH帧的发送，并取而代之在R-FCH上发送5-ms帧。在发送5-ms帧后，在R-FCH上20-ms周期中的任意剩余时间不再发送。在下一个20-ms帧的开始处重新建立20-ms R-FCH的非连续传输。

在第二个方法中，在20-ms R-FCH上利用补充信道请求消息(SCRM)执行速率请求。

取决于不同的实施例，可以在请求消息中发送不同的信息。在IS2000中，为了速率请求在反向链路上发送补充信道请求微型消息(SCRMM)或补充信道请求消息(SCRM)。

在一个实施例中，对于每个SCRM/SCRMM传输，应当由MS将以下信息报告给BS：

●最大请求速率

●队列信息

最大请求速率：为快速信道变化留出自由空间(headroom)后按照当前信道状态MS能够传输的速率就是最大数据速率。MS利用以下等式确定其最大速率：

$>>>R>max>>>(>power>)>>=>>>arg>max>>R>\left(\begin{array}{}>>>R>:>Pref>>(>R>)>>*>NormAvPiTx>>(>>PCG>i>>)>>*>>>>>>>(>1>+>T>/>P>)>>R>>+>>(>>>>(>T>/>P>)>>>9.6>k>>>+>C>/>P>)>>>(>>>Pref>>(>9.6>k>)>>>>Pref>>(>R>)>>>>)>>)>>>>>>\le >Tx>>(>max>)>>/>Headroom>\_>Rcq>>>>>>>\end{array}\right)$

$>>NormAvPiTx>>(>>PCG>i>>)>>=>>\alpha >Headroom>>>>TxPiPwr>>(>>PCG>i>>)>>>>Pref>>(>Rassigned>)>>>>+>>(>>>1>->\alpha >>Headroom>>)>>\times >NormAvPiTx>>(>>PCG>>i>->1>>>)>>>>$

其中，Pref(R)是TIA/EIA-IS-2000.2内的属性增益表中所指定的“导频参考电平”，TxPiPwr(PCG_i)是在功率中断的情况下在对MS侧应用了功率约束后的实际发送导频功率，NormAvPiTx(PCG_i)是归一化平均发送导频功率。在选择自由空间和基于BS所允许的速率来确定最大请求速率方面，MS可以更保守或更激进。

在一个实施例中，MS利用以下两种方法之一来接收许可信息：

方法a：在5-ms前向专用控制信道(F-DCCH)上的来自BS的增强补充信道分配微型消息(ESCAMM)，该增强补充信道分配微型消息(ESCAMM)具有所指定的调度延续时间的速率分配。

方法b：在前向物理数据信道(F-PDCH)上的来自BS的增强补充信道分配消息(ESCAM)，该增强补充信道分配消息(ESCAM)具有所指定的调度延续时间的速率分配。

分配延时取决于回程(backhaul)和传输延时，并且根据用于速率许可的方法而不同。在调度延续时间期间，执行以下过程：

·在R-FCH用于发送自发数据和用于外环PC的一个实施例中，如果在其缓存器中有一些数据，则MS按照9600bps的自发速率发送数据。否则，MS按照1500bps的速率发送空的R-FCH帧。

·如果MS具有比能够在R-FCH上承载的数据更多的数据和如果其具有足够功率以按照所分配的速率来进行发送，则MS在给定的20-ms周期内按照所分配的R-SCH速率来进行发送(给信道变化保留自由空间)。否则，在该帧期间在R-SCH上没有发送或者MS按照满足功率约束的较低速率来发送。如果以下等式被满足，则在给定的20-ms周期之前的编码延时(Encode_Delay)，MS决定其有足够的功率以在该20-ms周期内按照所分配的速率R在R-SCH上发送：

其中，Pref(R)是TIA/EIA-IS-2000.2内的属性增益表中所指定的“导频参考电平”值，NormAvPiTx(PCG_i)是归一化平均发送导频功率，(T/P)_R是对应于速率R和用于所有信道速率的业务与导频之比，并且在附录A内的标称属性增益表中被指定为标称属性增益值，(T/P)_RFCH是FCH上业务与导频之比，(C/P)是由控制信道所使用的总功率与没有进行多信道增益调整时的导频功率之比，Tx(max)是最大的MS发送功率，Headroom_Tx是MS考虑到信道变化而保持的自由空间。

在R-SCH传输之前的Encode_Delay PCG，每帧进行一次DTX确定。如果MS在R-SCH上停止发送，则其按照以下功率发送：

$>>TxPwr>>(>PCGi>)>>=>PiTxPwr>>(>PCGi>)>>[>1>+>>(>>>(>T>/>P>)>>>R>FCH>>>+>>(>c>/>p>)>>)>>>(>>>Pref>>(>>R>FCH>>)>>>>Pref>>(>R>)>>>>)>>]>>>$

在实际传输之前的编码延时(Encode_Delay)，MS对传输帧进行编码。

基站过程

在一个实施例中，BS执行以下基本功能：

·对R-FCH/R-SCH进行解码

·功率控制

解码R-FCH/R-SCH

当MS同时发送多个业务信道时，在与相应的Walsh序列相关后，对每个业务信道进行解码。

功率控制

为了保持所期望的服务质量(QoS)，在CDMA系统中功率控制是必须的。在IS-2000中，将每个MS的RL导频信道(R-PICH)闭环功率控制到所期望的阈值。在BS处，该称作功率控制设置点的阈值与所接收的Ecp/Nt比较以生成功率控制命令(闭环PC)，其中Ecp是每码片的导频信道能量。为了在业务信道上取得所期望的QoS，在BS处的阈值随着业务信道的去除(erasure)而变化，并且当数据速率发生变化时必须调整该阈值。

由于以下而发生设置点校正：

·外环功率控制

·速率变化

外环功率控制：如果存在R-FCH，则基于R-FCH的去除来校正功率控制设置点。如果不存在R-FCH，则当MS正在发送数据时，基于某些控制信道或R-SCH的去除来校正外环PC。

速率变化：在R-SCH上的不同数据速率要求反向导频信道的不同最优设置点。当在R-SCH上数据速率发生变化时，BS通过当前的和下一个R-SCH数据速率之间的导频参考电平(Pref(R))差值来改变MS的接收Ecp/Nt。在一个实施例中，在C.S0002-C内的标称属性增益表中规定了给定数据速率R的导频参考电平Pref(R)。因为闭环功率控制使所接收的导频Ecp/Nt达到设置点，所以BS按照下一个所分配的R-SCH数据速率来调整外环设置：

Δ＝Pref(R_new)-Pref(R_old)

如果R_new＞R_old，则在新的R-SCH数据速率之前PCG进行设置点调整。否则，该调整发生在R-SCH帧边界。因此导频功率利用图2所示的闭环的1dB步长近似地上升或下降到正确的电平。

图2示出了按照一个实施例的在R-SCH上由于速率变化导致的设置点调整。图2的纵轴示出了基站控制器(BSC)202、基站收发信机子系统(BTS)接收机导频功率204和移动台速率206的设置点。MS速率开始为R₀ 208。当R-SCH数据速率增加，即R₁＞R₀ 210时，按照Pref(R₁)-Pref(R₀)212来调整设置点。当R-SCH数据速率减少，即R₂＜R₁ 214时，按照Pref(R₂)-Pref(R₁)216来调整设置点。

调度器过程

调度器可以与BSC或BTS或位于网络层中的某个单元协作。调度器与负责调度共享较低层资源的那些MS的每个部分可以是多级的。例如，未处于软切换(SHO)的MS可以由BTS来调度，而处于SHO的MS可以由与BSC协作的那部分调度器来调度。出于调度的目的，将反向链路容量分布在BTS和BSC之间。

在一个实施例中，以下假设用于按照一个实施例的调度器和与调度相关的各个参数：

1、集中调度：调度器与BSC同地协作，并且负责同时调度横跨多个小区的MS。

2、同步调度：所有R-SCH数据速率传输是时间对齐的。所有数据速率分配持续一个调度周期的延续时间，其对于系统中的所有MS是时间对齐的。该调度延续时间周期表示为SCH_PRD。

3、语音和自发R-SCH传输：在通过速率分配将容量分配给R-SCH上的传输之前，调度器察看来自MS的挂起(pending)的速率请求，并且提前考虑(discount for)给定小区中的语音和自发传输。

4、速率请求延时：与经由SCRM/SCRMM的速率请求相关的上行链路请求延时表示为D_RL(请求)。其是从请求发送的时间到请求可用于调度器时的延时。D_RL(请求)包括请求空中传递的延时部分、在小区处请求的解码时间和从小区到BSC的回程延时，并且D_RL(请求)被建模成均匀分布随机变量。

5、速率分配延时：与经由ESCAM/ESCAMM的速率分配相关的下行链路分配延时表示为D_FL(分配)。其为在进行速率决定的时刻与MS接收到最终分配的时刻之间的时间。D_FL(分配)包括从调度器到小区的回程延时、分配的空中传递的传输时间(基于所选择的方法)和在MS处的解码时间。

6、可用的Ecp/Nt测量值：用于调度器中的Ecp/Nt测量值应当是在最近的帧边界处可用于该调度器的最新值。该测量的Ecp/Nt由BTS接收机定期地报告给调度器，所以对于BSC接收机该Ecp/Nt被延时。

图3示出了按照一个实施例的调度延时定时。所示出的数量是由位于BSC的调度器所使用的典型数量的一个例子，但是实际的数量取决于回程延时和所配置系统的负荷情形。

横轴示出了SCH帧边界250、在点A之前最近的SCH帧边界252、点A254、调度时间256和作用时间258。所示出的Ecp/Nt测量窗口260开始于SCH帧边界250，结束在点A之前的最近SCH帧边界252。最近的帧边界的时间262示出为从点A之前的最近SCH帧边界252到点A 254。获取从BTS到BSC的信息的时间(6PCG)示出为开始于点A 254和结束在调度时间256。作用时间延时(ActionTimeDelay)266(方法a为25 PCG，方法b为62 PCG)示出为开始于调度时间256和结束在作用时间258。用于方法a和b的作用时间延时的典型值在表1中给出。

调度、速率分配和传输时间线(Transmission Timeline)

调度周期SCH_PRD指时间间隔，在该时间间隔后在BTS或BSC上的调度器或处于网络级别的调度器进行调度决定。调度器唤醒(wake up)每个SCH_PRD并为下一个调度周期发送调度许可。但是，在调度周期中MS的调度延续时间是可变的。MIN_SCH_DUR是MS的最小调度延续时间，并且MS的调度延续时间为MIN_SCH_DUR的倍数但不超过SCH_PRD。

在一个执行同步调度的实施例中，与请求、许可和传输相关的许多事件是周期性的，其周期为SCH_PRD。

图4举例说明了按照一个实施例的速率请求、调度和速率分配的定时示意图。纵轴示出了BSC(调度器)402和移动台404的时间线。MS创建SCRMM 406并向BSC(调度器)408发送速率请求。该速率请求包括在该SCRMM中，该SCRMM在R-FCH上发送。与经由SCRM/SCRMM的速率请求相关的上行链路请求延时表示为D_RL(请求)410。每个调度周期414进行一次调度决定412。在调度决定412之后，在前向信道上将ESCAM/ESCAMM 416从BSC发送到MS，表示速率分配418。D_FL 420是与经由ESCAM/ESCAMM的速率分配相关的下行分配延时。往返时间422是往返速率请求所花费的时间。其为从速率请求到速率分配的时间。

时间线特征如下：

·调度定时

·调度速率传输

·调度速率延续时间

调度定时：每个调度周期调度器操作一次。如果在t_i时刻执行第一个调度决定，则调度器在t_i，t_i+SCH_PRD_i，t_i+SCH_PRD_i+SCH_PRD_i+1...时刻进行操作。

调度速率传输：假定必须使用充足的前置时间(lead time)来向MS通知调度决定，则调度决定必须在ESCAM/ESCAMM消息的作用时间减去固定延时，即作用时间延时，到达。相应的调度周期是{s_i，s_i+SCH_PRD_i}，{s_i+SCH_PRD_i，s_i+SCH_PRD_i+SCH_PRD_i+1}，{s_i+SCH_PRD_i+SCH_PRD_i+1，s_i+SCH_PRD_i+SCH_PRD_i+1+SCH_PRD_i+2}...，其中，s_i-t_i表示作用时间延时。作用时间延时的值取决于调度器所处的位置。如果多级调度器的调度级位于BSC，则作用时间延时比调度级位于BTS的情形要大，以确保大多数MS以高概率接收ESCAM/ESCAMM消息。

调度速率延续时间：在{s_i，s_i+SCH_PRD}之间的任意调度周期中，MS能够具有可变的调度延续时间(SCH_DUR)。参数MIN_SCH_DUR是分配的最小调度延续时间，而SCH_PRD是分配的最大延续时间。SCH_DUR是调度时确定的变量，并且从一个调度时刻到另一调度时刻变化。在一个实施例中，SCH_PRD是MIN_SCH_DUR的整数倍。假设SCH_PRD/MIN_SCH_DUR＝n。假设调度周期中MIN_SCH_DUR的连续时间块被索引为i＝1，2，...，n。如果j+k-1＜＝n，则被调度来在第j块开始的分配可以被调度来在k个连续块内持续发送。因此，在调度周期{s_i，s_i+SCH_PRD}中，MS调度延续时间是由{s_i+(j-1)MIN_SCH_DUR，s_i+(j-1+k)MIN_SCH_DUR}得到。对于该分配，SCH_DUR/MIN_SCH_DUR＝k，并且在接下来的延续时间为SCH_DUR的调度周期中也一样，将MS调度为在SCH_DUR的延续时间内持续进行发送。

通常，SCH_DUR≤SCH_PRD。在图4所示的例子中，SCH_DUR＜SCH_PRD。SCH_PRD 424包括N个块，而SCH_DUR包括k个块。

图5举例说明了按照一个实施例的用于第j扇区中的第k(不要与上述的k个连续块混淆)个MS的速率确定过程。图5示出了在调度周期内的可变调度延续时间。在一个实施例中，调度器具有时间可调的调度延续时间。调度延续时间随着取决于MS传输请求的优先权的时间、在该时间的最大可支持速率和移动台队列估计而变化。移动台队列估计是队列(即缓存器)中数据量的估计。最大可支持速率基于MS功率约束。

横轴502表示调度器时间线，其中t_i表示调度时刻。横轴504表示许可的作用时间的开始s_i。s_i-t_i指定作用时间延时506。调度延续时间周期SCH_PRD 508示出为具有四倍于MIN_SCH_DUR 510的延续时间，即四个块。出于示例的目的，选择数量四。对于本领域技术人员显而易见的是SCH_PRD可以选择为除了四之外的实现复杂性所允许的任何整数。MIN_SCH_DUR 510是MS的最小调度延续时间，MS的调度延续时间是以MIN_SCH_DUR的倍数逐步变化的但不超过SCH_PRD 508。

纵轴512表示第j扇区的容量，横轴514表示在调度周期内的一个延续时间MIN_SCH_DUR的块。与轴512相交的水平线516表示在调度周期508期间允许调度器填入(fill in)的最大容量数。

Cj(i)表示在第i块上第j扇区的可用容量。因此，Cj(1)518表示在第1块上第j扇区的可用容量。Cj(2)520表示在第2块上第j扇区的可用容量。Cj(3)522表示在第3块上第j扇区的可用容量。Cj(4)524表示在第4块上第j扇区的可用容量。

在按照调度器优先权列表对第k个MS 530进行调度的时刻，调度器扫描连续块的不同组合以便如果被调度则MS能够发送最大数据量。因为第一块中的可用容量518仅允许小的速率分配，所以调度器可以选取具有高的速率分配的第二和第三块。如果MS没有足够的数据要发送，则不给第四调度块中第k个MS分配速率。

共享区域526和528表示由向第k个MS 530的分配所消耗的容量。在该例子中，在Cj(1)518上没有足够可用的容量用作在Cj(2)520上使用的容量；因此，被使用的容量位于Cj(2)520上。在Cj(4)524上有足够的容量用作在Cj(2)520和Cj(3)522上使用的容量，但在Cj(2)520和Cj(3)522上有足够的可用容量，因此不需要使用在Cj(4)524上的任何可用容量。因此，在SCH_PRD期间，四个块中的仅有两个用于发送。

调度器描述和过程

调度实体在该实体负责调度的系统中维持在该系统中的所有MS列表。其还维持在每个MS激活集中的BS列表。通过与每个MS关联，调度器存储MS队列长度的估计

在MS在请求消息中报告队列长度的一个实施例中，可以使用以下系列更新来维持MS队列估计。在任一以下事件发生后更新队列长度估计

1、收到请求消息。作为一个例子，在IS-2000中，使用补充信道请求消息(SCRM)或补充信道请求微型消息(SCRMM)来请求速率和报告MS发送缓存估计：被更新为：

如果在收到请求消息时调度实体知道上行链路延时，则可以获取较佳的估计。然后，在请求被发送和由调度器接收的延续时问内，调整MS发送缓存的变化。

2、在每个分组信道解码后：

在IS-2000中，存在反向基本信道(R-FCH)和反向补充信道(R-SCH)，并且使用它们来承载数据。在分组解码后的情况下，按照如下的规定来更新队列估计：

$>ver>>Q>^>>=ver>>Q>^>>->>(>Correc>>t>FCH>>*>>R>tx>>>(>FCH>)>>+>>(>>Correct>SCH>>*>>R>tx>>>(>SCH>)>>)>>*>20>ms>+>>>>$

(Correct_FCH·PL_FCH_OHD+Correct_SCH·PL_SCH_OHD)

其中，PL_FCH_OHD和PL_SCH_OHD分别为在R-FCH和R-SCH上的物理层开销；Correct_FCH和Correct_SCH分别为R-FCH和R-SCH的指示器函数。

3、在调度时刻t_i，调度器在下一个调度许可开始时估计MS的队列长度：

(R_assigned×20ms-PL_SCH_OHD)×(RemainingSchDur/20ms)

其中，R_assigned是在当前调度周期期间在R-SCH上所分配的速率，RemainingSchDur是用于在调度时刻t_i之后MS按照R_assigned速率在R-SCH上发送的剩余时间。

调度算法

调度算法具有以下特征：

a)基于MS请求的速率、其队列估计、分配的吞吐量和其它优先权度量来对MS速率请求区分优先次序，

b)用于最大容量利用和增大时分复用(TDM)增益的GreedyFilling，以及

c)从MS缓存器清空最大数据的本地Greedy Filling。考虑以下所示的用于调度延续时间{s，s+SCH_PRD}的调度算法。

图5举例说明了在扇区j中第k个MS的速率确定过程。

初始：对MS速率请求区分优先次序。与每个MS相关的是优先计数PRIORITY。基于诸如信道状态、估计的MS缓存器中队列长度、所请求的速率和所分配的吞吐量这样的各种因素来更新MS的PRIORITY。

1、假设负载约束为Load_j≤max Load，以便限制大于某个阈值的热噪声增量(rise-over-thermal)。假设C_j(r)表示在第r个最小调度块{s+(r-1)·MIN_SCH_DUR，s+r·MIN_SCH_DUR}中在扇区j上的可用容量(图5)。第一步，计算由于导频传输和在基本信道上的传输(由于语音或数据导致的)而导致的在SCH_PRD期间所消耗的容量，并且相应地更新在每个最小调度块中的可用容量。在扇区负载用于容量估计的一个实施例中，按照以下更新可用的容量：

$>>>C>j>>>(>r>)>>=>max>Load>->>\Sigma >>j>\in >ActiveSet>>>>>>Sinr>j>>>(>0>,>E>[>>R>FCH>>]>)>>>>1>+>>Sinr>j>>>(>0>,>E>[>>R>FCH>>]>)>>>>,>\forall >r>=>1,2>,>.>.>.>n>,>>>$

其中，max Load是满足热噪声增量中断准则的最大负载。如果MS在R-SCH上被分配了速率R_i，则Sinr_j(R_i，E[R_FCH])表示在扇区j中的估计Sinr，E[R_FCH]是在R-FCH上传输的预期速率。

按照它们的PRIORITY的降序来对MS速率请求区分优先次序。因此，具有最高PRIORITY的MS位于队列顶部。

2、设置k＝1，

3、对于d从1到n，在可用功率和队列中可用数据的约束下，计算MS能够在d个连续最小调度块内连续地发送的最大速率R_max^k(d)。在一个实施例中，其中MS基于其功率限制来报告最大速率或者BS能够估计MS的最大功率约束速率，调度器能够如以下所示的根据其队列估计来确定R_max^k(d)。

$>sup>>R>max>ksup>>>(>d>)>>=>min\left(\begin{array}{}>>>>R>max>>>(>power>)>>,>>>>>>>arg>min>>R>>\{>R>|ver>>Q>^>>>(>f>)>>\le >>(>9600>\times >20>ms>->PL>\_>FCH>\_>OHD>)>>\times >>(>SCH>\_>PRD>/>20>ms>)>>>>>>+>>(>R>\times >20>ms>->PL>\_>SCH>\_>OHD>)>>\times >>(>i>\times >MIN>\_>SCH>\_>DUR>/>20>ms>)>>>>>>OR>307.2>kbps>\}>>>>>>>\end{array}\right)$

R_max(power)是给定其功率限制时MS能够支持的最大速率。在最近接收到的SCRM/SCRMM消息中报告最大速率。

4、基于每个最小调度块中的R_max^k(d)(d＝1，...，n)和可用容量C_j(r)，确定分配给第k个MS的速率R_k(r，d)，该速率从第r个块开始并持续d个连续块。所选择的R_k^*(r^*，d^*)值最大化在调度周期{s，s+SCH_PRD}内的任意连续间隔中所发送的数据，同时选择这样的间隔中最小的间隔来最大化TDMA增益。

初始MS队列为空，Q(e)＝0， $>sup>>R>k>*sup>>>(>>r>*>>,>>d>*>>)>>=>0>.>>>$

以下的迭代法找出用于最大化Q(e)同时选择最小调度延续时间的r^*、d^*和R_k^*(r^*，d^*)。

对于d＝1：n，

若Q(e)＜(R_max^k(d)×20ms-PL_SCH_OHD)×(d×MIN_SCH_DUR/20ms){

对于r＝1：n-d+1，

确定在间隔{s+(r-1)MIN_SCH_DUR，s+(r-1+d)MIN_SCH_DUR}中是否可以调度第k个MS。

定义C_av(j)为在开始于第r块的d个连续块中可用最大容量的最小者。如果按照恒定速率在d个连续块的延续时间MIN_SCH_DUR内持续调度，则这是MS能使用的最大容量。数学上，C_av(j)＝min{C_j(r)，C_j(r+1)，...，C_j(r+d-1)}。在优先权列表中位于第k个位置的仅传数据的MS可以分配速率R_k(r，d)，该速率为

$>>>R>k>>>(>r>,>d>)>>=>min>\{sup>>R>max>ksup>>>(>d>)>>,>>>arg>max>>R>\left(\begin{array}{}>>>R>|>>C>av>>>(>j>)>>->>>>Sinr>j>>>(>R>,>E>[>>R>FCH>>]>)>>>>1>+>>Sinr>j>>>(>R>,>E>[>>R>FCH>>]>)>>>>>>>>+>>>>Sinr>j>>>(>0>,>E>[>>R>FCH>>]>)>>>>1>+>>Sinr>j>>>(>0>,>E>[>>R>FCH>>]>)>>>>\ge >0>;>\forall >j>\in >ActiveSet>>(>k>)>>>>>>\}>>>若\end{array}\right)$

若Q(e)＜(R_k(r，d)×20ms-PL_SCH_OHD)×(d×MIN_SCH_DUR/20ms){

保存：r^*＝r，d^*＝d和 $>sup>>R>k>*sup>>>(>>r>*>>,>>d>*>>)>>=>>R>k>>>(>r>,>d>)>>.>>>$

Q(e)＝(R_k(r，d)×20ms-PL_SCH_OHD)×(d×MIN_SCH_DUR/20ms)}

结束}结束

将可用容量更新为：

$>>>C>j>>>(>l>)>>=>>C>j>>>(>l>)>>->>>>Sinr>j>>>(>>R>k>>,>E>[>>R>FCH>>]>)>>>>1>+>>Sinr>j>>>(>>R>k>>,>E>[>>R>FCH>>]>)>>>>+>>>>Sinr>j>>>(>0>,>E>[>>R>FCH>>]>)>>>>1>+>>Sinr>j>>>(>0>,>E>[>>R>FCH>>]>)>>>>;>>>$

j∈ActiveSe(k)，l＝r，r+1，...，r+d-1。

5、如果R_maxk(1)＞0和 $>sup>>R>k>*sup>>>(>>r>*>>,>>d>*>>)>>=>0>,>>>则增大MS的PRIORITY。否则，不改变MS的PRIORITY。$

6、k＝k+1；如果k＜列表中MS的总数，则转到步骤3，否则停止。

为了压缩封装和容量的有效利用，大的n是理想的。但是，如上所述，这增加算法的复杂性。所以调度器实现可以选取不同的SCH_PRD和n值，并且对这种折衷进行不同地管理。

                        表1

                   基线的具体参数

  参数  典型值  备注  Headroom_Req  5dB  保守的速率请求为长  期的信道变化保留功  率自由空间  减少R-SCH上的  DTX  Headroom_Tx  2dB  减少在R-SCH传输的  延续时间期间功率中  断的概率  平均发射功率滤波器  系数α_Headroom  1/16  按照过滤方案在几个  PCG内计算归一化平  均发送导频功率  作用时间延时  (方案a)  31.25ms  基于期望的ESCAM  延时，包括2PCG MS  编码延时  作用时间延时  (方案b)  77.5ms  基于在-5dB的主扇区  形状的F-PDCH上的  期望ESCAM延时。  这包括2PCG MS编  码延时

对于本领域技术人员显而易见的是其他值也可以用于表1中的参数。对于本领域技术人员还显而易见的是更多或更少的参数可以用于特定的实现。

本领域技术人员将会理解，在不脱离本发明的范围的情况下，可以互换方法的步骤。本领域技术人员还将理解，可以使用各种不同的工艺和技术中的任意技术来表示信息和信号。例如，在整个以上描述中所提及的数据、指令、命令、信息、信号、位、符号，以及码片可以由电压、电流、电磁波、磁场或粒子，光场或粒子，或者上述的任意组合来表示。

本领域技术人员应当理解可以使用任意各种技术和方法来表示信息和信号。例如，在整个上面的描述中提及的数据、指令、命令、信息、信号、位、符号和码片都可以由电压、电流、电磁波、磁场或粒子、光场或粒子，或者上述的任意组合来表示。

图6是按照一个实施例的BS 12的方框示意图。在下行链路上，通过发射(TX)数据处理器612接收和处理(例如格式化、编码等)下行链路的数据。通过与每个信道相关的参数设置来确定该信道的处理，并且在一个实施例中，可以按照标准文档的描述来执行每个信道的处理。然后将已处理的数据提供给调制器(MOD)614，并且对其进一步处理(例如，被信道化、加扰等)以提供已调制数据。发射机(TMTR)单元616然后把该经过调制的数据转换成一个或多个模拟信号，进一步对该模拟信号进行调整(例如，放大、滤波和上变频)以提供下行链路信号。通过双工器(D)622来路由该下行链路信号并经由天线624发送给目的MS。

图7是按照一个实施例的MS 106的方框示意图。通过天线712接收下行链路信号，通过双工器714将其路由，并提供给接收机(RCVR)单元722。接收机单元722调整(例如，滤波、放大和下变频)该接收的信号并进一步数字化该已调整的信号以提供采样。然后解调制器724接收和处理(解扰、信道化和数据解调制)该采样以提供符号。解调制器724可以实现瑞克接收机，该瑞克接收机能够处理该接收信号的多个情形(或多径分量)并提供合并的符号。接收(RX)数据处理器726然后解码该符号、检查所接收的分组和提供解码后的分组。解调制器724和RX数据处理器726的处理分别与调制器614和TX数据处理器612的处理互补。

在上行链路上，上行链路的数据、导频数据和反馈信息由发射(TX)数据处理器742来处理(例如，格式化、编码等)，进一步由调制器(MOD)744来处理(被信道化、加扰等)，并且由发射机单元746来调整(例如，转换成模拟信号、放大、滤波和上变频)以提供上行链路信号。标准文档描述了用于上行链路的数据处理。上行链路信号通过双工器714路由并经由天线712发送给一个或多个BS 12。

参考回到图6，在BS 12上，上行链路信号由天线624接收，通过双工器622路由，并提供给接收机单元628。接收机单元628调整(例如，下变频、滤波和放大)该接收的信号并进一步数字化该已调整的信号以提供采样流。

在图6所示的实施例中，BS 12包括许多信道处理器630a至630n。每个信道处理器630可以被分配来处理一个MS的采样流，以恢复由该分配的MS在上行链路上发送的数据和反馈信息。每个信道处理器630包括：(1)处理(例如，解扰、信道化等)采样以提供符号的解调制器632，以及(2)进一步处理该符号以向所分配的MS提供解码后的数据的RX数据处理器634。

控制器640和730分别控制在BS和MS上的处理。每个控制器还可以被设计为执行全部或部分调度过程。控制器640和730所需的程序代码和数据可以分别存储在存储器单元642和732中。

本领域技术人员还会明白，这里结合所公开的实施例描述的各种示例性的逻辑框、模块、电路和算法步骤均可以电子硬件、计算机软件，或二者的结合来实现。为了清楚地示出硬件和软件之间的可交换性，以上对各种示例性的组件、方框、模块、电路和步骤均以其功能性的形式进行总体上的描述。这种功能性是以硬件实现还是以软件实现依赖于特定的应用和整个系统所施加的设计约束。熟练的技术人员能够针对每个特定的应用以多种方式来实现所描述的功能性，但是这种实现的结果不应解释为引起背离本发明的范围。

利用一个通用处理器，数字信号处理器(DSP)，专用集成电路(ASIC)，现场可编程门阵列(FPGA)或者其他可编程的逻辑器件，分立门或者晶体管逻辑，分立硬件组件，或者它们之中的任意组合可以实现或执行结合这里公开的实施例描述的各种示例性的逻辑框图，模块和电路。一个通用处理器可能是一个微处理器，但是在另一种情况中，处理器可能是任何常规的处理器，控制器，微控制器，或者状态机。一个处理器也可能被实现为计算设备的组合，例如，DSP和微处理器的组合，多个微处理器，一个或者更多结合DSP核心的微处理器，或者任何其他此种结构。

结合这里公开的实施例描述的方法或者算法可直接体现为硬件，由处理器执行的软件模块，或者这二者的组合。一个软件模块可能存在于RAM存储器，闪存，ROM存储器，EPROM存储器，EEPROM存储器，寄存器，硬盘，移动磁盘，CD-ROM，或者本领域熟知的任何其他形式的存储媒质中。一种典型存储媒质与处理器耦合，使得处理器能够从该存储媒质中读信息，且可向该存储媒质写信息。在替换实例中，存储媒质可能与处理器集成。处理器和存储媒质可能存在于一个ASIC中。该ASIC可能存在于一个用户站中。在一个替换实例中，处理器和存储媒质可以作为用户站中的分立组件存在。

提供所述公开的实施例的上述描述可使得本领域的技术人员能够实现或者使用本发明。对于本领域的技术人员来说，这些实施例的各种修改是显而易见的，并且这里定义的总体原理也可以在不脱离本发明的范围和主旨的基础上应用于其他实施例。因此，本发明并不限于这里示出的实施例，而是与符合这里公开的原理和新颖特征的最广范围相一致。