(19) United States
`(12) Patent Application Publication (10) Pub. No.: US 2002/0183066 A1
`Pankaj
`(43) Pub. Date:
`Dec. 5, 2002
`
`US 20020183066A1
`
`(54) METHOD AND APPARATUS FOR
`SCHEDULING TRANSMISSIONS IN A
`
`COMMUNICATION SYSTEM
`
`(76)
`
`Inventor: Rajesh K. Pankaj, San Diego, CA
`(US)
`
`Correspondence Address:
`Sarah Kirkpatrick, Manager
`Intellectual Property Administration
`QUALCOMM Incorporated
`-
`5775 Morehouse Drive
`San Diego, CA 92121_1714 (US)
`
`(21) Appl. No‘.
`
`09/974,933
`
`(22)
`
`Ffled;
`
`()ct_ 10, 2001
`
`Related US, Application Data
`
`(60) Provisional application No. 60/283,885, filed on Apr.
`12, 2001.
`
`Publication Classification
`
`Int. Cl.7 ..................................................... .. H04Q 7/20
`(51)
`(52) U.S. Cl.
`.......................................... .. 455/453; 455/450
`
`(57)
`
`ABSTRACT
`
`.
`l\/llethod and apparatus for a generalized schedu1erTftcl)r scfieg-
`u mg transmissions in a communications system.
`e sc. e -
`uler is defined by a priority function of the channel condition
`d f .
`.
`. Th
`1.
`d
`h d 1
`.
`d
`d
`an
`airness criteria.
`egenera ize sc e u er isa apte ‘to
`apply a variety of combinations of channel condition metrics
`and user
`fairness metrics. The. scheduler distinguishes
`among classes of users, allowing individual processing per
`class. In one embodiment, a system controller receives a
`Delivery Priority Parameter (DPP) for each of a plurality of
`users, and maps each DPP to a corresponding common
`Mapped Priority Parameter (MPP). An operating point is
`determined and a corresponding MPP value for each of the
`users is applied to schedule transmissions.
`
`102E
`
`ERICSSON EXHIBIT 1003
`ERICSSON EXHIBIT 1003
`ERICSSON V. IV
`ERICSSON V. IV
`IPR20l5-01872
`IPR2015-01872
`
`

`
`Patent Application Publication
`
`Dec. 5, 2002 Sheet 1 of 15
`
`US 2002/0183066 A1
`
`
`
`<—..G_u_
`
`

`
`Patent Application Publication
`
`Dec. 5, 2002 Sheet 2 of 15
`
`US 2002/0183066 A1
`
`AT
`
`/124
`
`126
`
`122
`
`SECTORS
`
`AN
`
`120\
`
`FIG.1B
`
`

`
`Patent Application Publication
`
`Dec. 5, 2002 Sheet 3 of 15
`
`US 2002/0183066 A1
`
`202
`
`204
`
`210
`
`RECEIVE DRCS FROM USERS i=1, 2, ..., N
`
`
`
`I
`
`DETERMINE THROUGHPUT OF EACH USER i=1,
`2, ..., N BASED ON TRANSMISSION BITS
`
`I
`
`
`
`Ti/T. g G?
`FOR AI’.L USERS:
`i=1, 2, ...N;
`
`i=1, 2,
`N
`
`
`
`
`DETERMINE
`SCHEDULE TO
`ACHEIVE Ti/TISG
`MAINTAIN Ti/Tj S G
`
`
`
`
`
`DETERMINE
`
`SCHEDULE TO
`
`
`
`
`APPLY SCHEDULE
`
`
`FIG. 2
`
`

`
`Patent Application Publication
`
`Dec. 5, 2002 Sheet 4 of 15
`
`US 2002/0183066 A1
`
`250 \
`
`START
`
`INITIALIZE WEIGHTS FOR EACH USER
`
`252
`
`254
`
`
`
`
`
`
`
`
`SELECT USER WITH MIN WEIGHT
`
`COMPUTE RATE THRESHOLD, RTH
`
`
`
`
`
`RATE FOR USER
`>
`
`Rm?
`
`
`WEIGHT OF USER =
`WEIGHT OF USER + DATA
`
`
` WEIGHT OF USER = WEIGHT
`
`
`OF USER + K x ( DATA)
`
`
`FIG. 3
`
`

`
`Patent Application Publication
`
`Dec. 5, 2002 Sheet 5 of 15
`
`US 2002/0183066 A1
`
`400 \
`
`START
`
`}
`
`START TIMER K
`® NO
`
`404
`
`YES
`
`———————————N RECEIVE DRCS FROM USERS
`
`402
`
`408
`
`408
`
`DETERMINE THROUGHPUT OF
`EACH USER BASED ON
`TRANSMISSION BITS
`
`
`
`
`
`
`
`T/Tjg G?
`FOR ALL USERS:
`
`i=1, 2, ...N;
` 414
`j=1, 2,
`N
`
`YES
`
`
`
`
`SCHEDULE TO
`SCHEDULE TO
`MAINTAIN TI/Tjg G
`ACHEIVE Ti/Tj sca
`
`
`
`DETERMINE
`
`DETERMINE
`
`
`
`APPLY SCHEDULE
`
`}
`
`416
`
`FIG. 4A
`
`

`
`Patent Application Publication
`
`Dec. 5, 2002 Sheet 6 of 15
`
`US 2002/0183066 A1
`
`DETERMINE PRIORITY FUNCTION Ri(t) FOR
`EACH USER
`
`SELECT A WINNER BASED ON R(t)
`
`420
`
`422
`
`TRANSMIT TO WINNER
`
`424
`
`YES
`
`
`
`
`PENDING DATA?
`
`NO
`
`FIG. 4B
`
`

`
`Patent Application Publication
`
`Dec. 5, 2002 Sheet 7 of 15
`
`US 2002/0183066 A1
`
`600
`
`\'\
`
`602
`
` DETERMINE MIN WEIGHT OF ALL
`
`USERS M
`
`DETERMINE COLLAR K
`
`CALCULATE ( M + K)
`
`
`
`
`OR USERS WITH VALID DRC
`
`AND PENDING DATA:
`IS AT LEAST ONE USER
`
`NO
`
`WEIGHT <= ( M + K)
`
`
`
`SELECT
`USER WITH
`
`MIN WEIGHT
`
`
`
`
`SELECT USER OF THE AT LEAST
`ONE USER BASED ON CHANNEL
`
`
`
`CONDITION METRIC
`
`UPDATE WEIGHTS OF USER
`
`SELECTED
`
`
`
`FIG. 5
`
`

`
`Patent Application Publication
`
`Dec. 5, 2002 Sheet 8 of 15
`
`US 2002/0183066 A1
`
`700 \
`
`START
`
`MEASURE CHANNEL CONDITION AND
`
`DETERMINE APPROPRIATE CHANNEL
`CONDITION INDICATOR
`
`f/ 702
`
`SELECT FAIRNESS INDICATOR
`
`K
`
`DETERMINE FAIRNESS INDICATOR AS A K
`
`FUNCTION OF THROUGHPUT
`
`EVALUATE EACH USER AS A FUNCTION OF
`CHANNEL CONDITION INDICATOR AND
`FAIRNESS INDICATOR
`
`APPLY SCHEDULE
`
`DETERMINE SCHEDULE BASED ON
`EVALUATIONS
`
`703
`
`710
`
`712
`
`END
`
`FIG. 6
`
`

`
`Patent Application Publication
`
`Dec. 5, 2002 Sheet 9 of 15
`
`US 2002/0183066 A1
`
`._._ZDmm._.Zm__>_mZm
`._m_zz<_._oI§mm
`agmm_.5om_:om
`
`mmm_zm__<n_
`
`mo5m_._m_m
`
`._Om._.ZOO
`
`._mzz<_._o
`
`
`
`v_Z_w<._.<n_
`
`/com
`
`§
`
`5,3
`
`momaom
`
`mww
`
`mmm
`
`._m_zz<_._o
`
`%mm_._:n_m__._ow
`
`.w.._M
`
`mowmmoomm
`
`N.6_u_
`
`moBm:m_m
`
`._.Zm__>_m_._m_
`
`§
`
`wmm_zm_<u_
`
`mokomzmm
`
`II:m_o<uEm:z_
`
`
`
`v_m_O>>._.m_Z._.mv_0<n_
`
`
`
`
`
`
`
`
`
`
`
`
`

`
`Patent Application Publication
`
`Dec. 5, 2002 Sheet 10 of 15
`
`US 2002/0183066 A1
`
`900 \
`
`902
`
`904
`
`906
`
`908
`
`
`
`
`DETERMINE MINIMUM WEIGHT M
`
`DETERMINE RANGE VALUE 0
`
`CALCULATE RANGE AS M + C
`
`DETERMINE GROUP OF USERS IN THE RANGE
`
`910
`
`AT LEAST ONE
`
`USER IN THE GROUP WITH
`
`PENDING DATA AND
`
`NO
`YES
`
`
`
`VALID DRC?
`
`
`912
`
`DETERMINE GROUP OF
`USERS OUTSIDE OF RANGE
`
`
`
`SELECT USER FROM THE
`GROUP
`
`END
`
`FIG. 8
`
`

`
`Patent Application Publication
`
`Dec. 5, 2002 Sheet 11 of 15
`
`US 2002/0183066 A1
`
`0.
`n.
`2
`
`FIG.9A
`
`

`
`Patent Application Publication
`
`Dec. 5, 2002 Sheet 12 of 15
`
`US 2002/0183066 A1
`
`DPP
`
`FIG.9B
`
`E F
`
`E<__
`r:cO
`LlJD_
`n.
`O
`
`MPP
`
`

`
`Patent Application Publication
`
`Dec. 5, 2002 Sheet 13 of 15
`
`US 2002/0183066 A1
`
`FIG.9C
`
`MPP
`
`OPERATING
`
`POINT
`
`

`
`Patent Application Publication
`
`Dec. 5, 2002 Sheet 14 of 15
`
`US 2002/0183066 A1
`
`FIG.9D
`
`MPP
`
`‘Z’
`i=5<n:_
`mo
`IJJD.
`n.
`O
`
`

`
`Patent Application Publication
`
`Dec. 5, 2002 Sheet 15 of 15
`
`US 2002/0183066 A1
`
`1200
`
`“
`
`RECEIVE DPP; FOR USERS I,...., N
`
`(1202
`
` 1204
`
`DPPk = DPPj
`FOR ALL M
`IN {i,..., N}
`
`
`
`CORRESPONDING MPP SCALE
`
`1212
`
`MAP EACH DPP; TO A
`l
`DETERMINE OPERATING POINT K
`
`r1205
`
`1208
`
`
`APPLY GENERALIZED
`SCHEDULER:
`
`
`f (A, U)
`
`
`
`
`APPLY MPP OPERATING POINT TO
`
`EACH USER
`
`
`
`FIG. 10
`
`

`
`US 2002/0183066 A1
`
`Dec. 5, 2002
`
`METHOD AND APPARATUS FOR SCHEDULING
`TRANSMISSIONS IN A COMMUNICATION
`SYSTEM
`
`REFERENCE TO RELATED CO-PENDING
`APPLICATIONS
`
`there is a need for a method and
`[0009] Accordingly,
`apparatus for scheduling transmissions in a communication
`system with application to multiple classes of users. Addi-
`tionally,
`there is a need for a scheduling method and
`apparatus that accommodates a variety of different sched-
`uling priorities.
`
`[0002] The present Application for Patent is related to U.S.
`application No. Ser. 09/796,583, filed Feb. 27, 2001 entitled
`“SYSTEM FOR ALLOCATING RESOURCES INA COM-
`
`MUNICATION SYSTEM,” assigned to the assignee hereof
`and hereby expressly incorporated by reference herein.
`
`BACKGROUND
`
`[0003]
`
`1. Field
`
`[0004] The present invention pertains generally to com-
`munications, and more specifically to a method and appa-
`ratus for scheduling transmissions in a communication sys-
`tem.
`
`[0005]
`
`2. Background
`
`[0006] Communication systems, and wireless systems in
`particular, are designed with the objective of efficient allo-
`cation of resources among a variety of users. Wireless
`systems in particular aim to provide sufficient resources to
`satisfy the requirements of all subscribers while minimizing
`costs. Various scheduling algorithms have been developed,
`each based on a predetermined system criteria.
`
`In a wireless communication system employing a
`[0007]
`Code Division-Multiple Access, CDMA,
`scheme, one
`scheduling method assigns each of the subscriber units all
`code channels at designated time intervals on a time multi-
`plexed basis. Acentral communication node, such as a Base
`Station, BS,
`implements the unique carrier frequency or
`channel code associated with the subscriber to enable exclu-
`sive communication with the subscriber. TDMA schemes
`
`may also be implemented in landline systems using physical
`contact relay switching or packet switching. A CDMA
`system may be designed to support one or more standards
`such as:
`(1) the “TIA/EIA/IS-95-B Mobile Station-Base
`Station Compatibility Standard for Dual-Mode Wideband
`Spread Spectrum Cellular System” referred to herein as the
`IS-95 standard; (2) the standard offered by a consortium
`named “3rd Generation Partnership Project” referred to
`herein as 3GPP; and embodied in a set of documents
`including Document Nos. 3G TS 25.211, 3G TS 25.212, 3G
`TS 25.213, and 3G TS 25.214, 3G TS 25.302, referred to
`herein as the W-CDMA standard; (3) the standard offered by
`a consortium named “3rd Generation Partnership Project 2”
`referred to herein as 3GPP2, and TR-45 .5 referred to herein
`as the cdma2000 standard, formerly called IS-2000 MC, or
`(4) some other wireless standard.
`
`In a communication system, and a wireless system
`[0008]
`in particular, users are typically assigned to classes, wherein
`each class has an associated system performance criteria.
`For example, each class may be treated differently with
`respect to a fairness criteria, wherein each user in a class is
`treated similarly. Classes may be treated according to the
`priority of each class. In one system, users are classified
`according to services used in the system, such as according
`to a service plan. Several classes may be present within one
`communication system.
`
`SUMMARY
`
`[0010] Embodiments disclosed herein address the above
`stated needs by providing a means for scheduling data
`transmissions in a wireless communication system. A gen-
`eralized scheduler allows scheduling of multiple mobile
`stations, wherein each mobile station may have a different
`delivery priority parameter. The delivery priority parameter
`defines the parameter used to affect the desired data trans-
`mission delivery rate. For example, a delivery priority
`parameter may be desired throughput, desired time allot-
`ment, desired time delay, etc. The delivery priority param-
`eter values are each mapped to a common scale, referred to
`as a mapped priority parameter. An operating point is then
`selected and the corresponding mapped priority parameter
`values for each mobile user extracted. The generalized
`scheduler then schedules mobile users using a common
`mapped priority parameter value. In other words, each user
`is scheduled to achieve a same proportion within the corre-
`sponding delivery priority parameter range.
`
`[0011] According to one aspect, in a wireless communi-
`cation system a scheduling method includes receiving chan-
`nel condition indicators from a plurality of mobile users,
`wherein the channel condition indicators correspond to
`forward link communications, determining a fairness indi-
`cator as a function of throughput to the plurality of mobile
`users, and determining a transmission schedule for the
`plurality of mobile users, wherein the transmission schedule
`is a function of the channel condition indicators and fairness
`indicators.
`
`In another aspect, a program embodied on a com-
`[0012]
`puter-readable medium containing computer-executable
`instructions, includes a first set of instructions for processing
`channel condition indicators received from a plurality of
`mobile users, a second set of instructions for determining a
`fairness indicator as a function of throughput to the plurality
`of mobile users, and a third set of instructions for determin-
`ing a transmission schedule for the plurality of users as a
`function of the channel condition indicators and the fairness
`indicators.
`
`In still another aspect, a method for transmitting
`[0013]
`data between one remote station of a plurality of remote
`stations and a base station in a wireless communication
`
`system includes receiving at the base station information
`transmitted by the one remote station, and adjusting at least
`one grade of service parameter particular to the one remote
`station based on the information.
`
`In yet another aspect, a method for scheduling data
`[0014]
`transmissions in a wireless communication system includes
`receiving a value for a delivery priority parameter from each
`of a plurality of mobile users, if any of the delivery priority
`parameters are different types, mapping each delivery pri-
`ority parameter to a mapped priority parameter, and deter-
`mining an operating point based on the mapped priority
`parameters of the plurality of mobile users.
`
`

`
`US 2002/0183066 A1
`
`Dec. 5, 2002
`
`[0015] According to another aspect, an apparatus in a
`wireless communication system includes a processing ele-
`ment, and a memory storage element coupled to the pro-
`cessing element, the memory storage element adapted for
`storing computer-readable instructions for implementing:
`receiving a delivery priority parameter from each of a
`plurality of mobile user, mapping each delivery priority
`parameter to a mapped priority parameter, and determining
`an operating point based on the mapped priority parameters
`of each the plurality of mobile users.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`[0016] The features, objects, and advantages of the pres-
`ently disclosed method and apparatus will become more
`apparent from the detailed description set forth below when
`taken in conjunction with the drawings in which like refer-
`ence characters identify correspondingly throughout and
`wherein:
`
`[0017] FIG. 1A is a wireless communication system;
`
`[0018] FIG. 1B is a wireless communication system sup-
`porting high data rate transmissions;
`
`[0019] FIG. 2 is a flow diagram of a Grade Of Service,
`GOS, and algorithm for scheduling data transmissions in a
`wireless communication system.
`
`[0020] FIG. 3 is a flow diagram of a scheduling algorithm
`for data transmissions in a wireless communication system;
`
`[0021] FIGS. 4A and 4B are flow diagrams of a propor-
`tional-fair algorithm for scheduling data transmissions in a
`wireless communication system;
`
`[0022] FIG. 5 is a flow diagram of a combination sched-
`uling algorithm, implementing a proportional-fair algorithm
`and a GOS algorithm in a wireless communication system;
`
`[0023] FIG. 6 is a flow diagram of a generalized scheduler
`for a wireless communication system;
`
`[0024] FIG. 7 is a wireless communication system sup-
`porting a combination scheduling algorithm such as illus-
`trated in FIGS. 5 and 6; and
`
`[0025] FIG. 8 is a flow diagram of a scheduling algorithm
`for a wireless communication system.
`
`[0026] FIG. 9A illustrates a mapping of various delivery
`priority parameter ranges to a common mapped priority
`parameter range.
`
`[0027] FIG. 9B, 9C, and 9D illustrate determination of
`various operating points over multiple mapped priority
`parameters.
`
`[0028] FIG. 10 illustrates a flow diagram of a generalized
`scheduler.
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`[0029] Amodern day communication system is required to
`support a variety of applications. One such communication
`system is a code division multiple access (CDMA) system
`which conforms to the “TIA/EIA-95 Mobile Station-Base
`Station Compatibility Standard for Dual-Mode Wideband
`Spread Spectrum Cellular System” and its progeny, herein-
`after referred to as IS-95. The CDMA system allows for
`
`voice and data communications between users over a ter-
`
`restrial link. The use of CDMA techniques in a multiple
`access communication system is disclosed in U.S. Pat. No.
`4,901,307, entitled “SPREAD SPECTRUM MULTIPLE
`ACCESS COMMUNICATION SYSTEM USING SATEL-
`LITE OR TERRESTRIAL REPEATERS”, and U.S. Pat. No.
`5,103,459, entitled “SYSTEM AND METHOD FOR GEN-
`ERATING WAVEFORMS IN A CDMA CELLULAR
`
`TELEPHONE SYSTEM”, both assigned to the assignee of
`the present invention and incorporated by reference herein.
`
`In a CDMA system, communications between
`[0030]
`users are conducted through one or more base stations. In
`wireless communication systems, forward link refers to the
`channel through which signals travel from a base station to
`a subscriber station, and reverse link refers to channel
`through which signals travel from a subscriber station to a
`base station. By transmitting data on a reverse link to a base
`station, a first user on one subscriber station communicates
`with a second user on a second subscriber station. The base
`station receives the data from the first subscriber station and
`
`routes the data to a base station serving the second sub-
`scriber station. Depending on the location of the subscriber
`stations, both may be served by a single base station or
`multiple base stations. In any case, the base station serving
`the second subscriber station sends the data on the forward
`
`link. Instead of communicating with a second subscriber
`station, a subscriber station may also communicate with a
`terrestrial Internet through a connection with a serving base
`station. In wireless communications such as those conform-
`
`ing to IS-95, forward link and reverse link signals are
`transmitted within disjoint frequency bands.
`
`[0031] FIG. 1A serves as an example of a communica-
`tions system 100 that supports a number of users and is
`capable of implementing at least some aspects and embodi-
`ments of the invention. Any of a variety of algorithms and
`methods may be used to schedule transmissions in system
`100. System 100 provides communication for a number of
`cells 102A through 102G, each of which is serviced by a
`corresponding base station 104A through 104G, respec-
`tively. In the exemplary embodiment, some of base stations
`104 have multiple receive antennas and others have only one
`receive antenna. Similarly, some of base stations 104 have
`multiple transmit antennas, and others have single transmit
`antennas. There are no restrictions on the combinations of
`transmit antennas and receive antennas. Therefore,
`it
`is
`possible for a base station 104 to have multiple transmit
`antennas and a single receive antenna, or to have multiple
`receive antennas and a single transmit antenna, or to have
`both single or multiple transmit and receive antennas.
`
`[0032] Terminals 106 in the coverage area may be fixed
`(i.e., stationary) or mobile. As shown in FIG. 1A, various
`terminals 106 are dispersed throughout the system. Each
`terminal 106 communicates with at least one and possibly
`more base stations 104 on the downlink and uplink at any
`given moment depending on, for example, whether soft
`handoff is employed or whether the terminal is designed and
`operated to (concurrently or sequentially) receive multiple
`transmissions from multiple base stations. Soft handoff in
`CDMA communications systems is well known in the art
`and is described in detail in U.S. Pat. No. 5,101,501, entitled
`“Method and system for providing a Soft Handoff in a
`CDMA Cellular Telephone System”, which is assigned to
`the assignee of the present invention.
`
`

`
`US 2002/0183066 A1
`
`Dec. 5, 2002
`
`[0033] The downlink refers to transmission from the base
`station to the terminal, and the uplink refers to transmission
`from the terminal to the base station. In the exemplary
`embodiment, some of terminals 106 have multiple receive
`antennas and others have only one receive antenna. In FIG.
`1A, base station 104A transmits data to terminals 106A and
`106] on the downlink, base station 104B transmits data to
`terminals 106B and 106], base station 104C transmits data
`to terminal 106C, and so on.
`
`Increasing demand for wireless data transmission
`[0034]
`and the expansion of services available via wireless com-
`munication technology have led to the development of
`specific data services. One such service is referred to as High
`Data Rate (HDR). An exemplary HDR service is proposed
`in “EIA/TIA-IS856 cdma2000 High Rate Packet Data Air
`Interface Specification” referred to as “the HDR specifica-
`tion.” HDR service is generally an overlay to a voice
`communication system that provides an efficient method of
`transmitting packets of data in a wireless communication
`system. As the amount of data transmitted and the number
`of transmissions increases, the limited bandwidth available
`for radio transmissions becomes a critical resource. There is
`a need, therefore, for an efficient and fair method of sched-
`uling transmissions in a communication system that opti-
`mizes use of available bandwidth. In the exemplary embodi-
`ment, system 100 illustrated in FIG. 1A is consistent with a
`CDMA type system having HDR service.
`
`[0035] FIG. 1B illustrates an architecture reference model
`for a communication system 120 having an Access Network,
`AN, 122 communicating with an Access Terminal, AT, 126
`via an air interface 124. In one embodiment, the system 10
`is a Code Division-Multiple Access, CDMA, system having
`a High Data Rate, HDR, overlay system, such as specified
`the HDR standard. The AN 122 communicates with AT 126,
`as well as any other ATs within system 120 (not shown), by
`way of the air interface 124. The AN 122 includes multiple
`sectors, wherein each sector provides at least one Channel.
`A Channel is defined as the set of communication links for
`transmissions between the AN 122 and the ATs within a
`
`given frequency assignment. A Channel consists of a For-
`ward Link (FL) for transmissions from the AN 122 to AT
`126 and a Reverse Link (RL) for transmissions from the AT
`126 to the AN 122.
`
`[0036] For data transmissions, the AN 122 receives a data
`request from the AT 126. The data request specifies the data
`rate at which the data is to be sent, the length of the data
`packet transmitted, and the sector from which the data is to
`be sent. The AT 126 determines the data rate based on the
`
`quality of the Channel between AN 122 and AT 126. In one
`embodiment the quality of the Channel is determined by the
`Carrier-to-Interference ratio, C/I. Alternate embodiments
`may use other metrics corresponding to the quality of the
`Channel. The AT 126 provides requests for data transmis-
`sions by sending a Data Rate Control, DRC, message via a
`specific channel referred to as the DRC channel. The DRC
`message includes a data rate portion and a sector portion.
`The data rate portion indicates the requested data rate for the
`AN 122 to send the data, and the sector indicates the sector
`from which the AN 122 is to send the data. Both data rate
`
`and sector information are typically required to process a
`data transmission. The data rate portion is referred to as a
`DRC value, and the sector portion is referred to as a DRC
`cover. The DRC value is a message sent to the AN 122 via
`
`the air interface 124. In one embodiment, each DRC value
`corresponds to a data rate in kbits/sec having an associated
`packet
`length according to a predetermined DRC value
`assignment. The assignment includes a DRC value specify-
`ing a null data rate. In practice, the null data rate indicates
`to the AN 122 that the AT 126 is not able to receive data. In
`
`one situation, for example, the quality of the Channel is
`insufficient for the AT 126 to receive data accurately.
`
`In operation, the AT 126 continuously monitors the
`[0037]
`quality of the Channel to calculate a data rate at which the
`AT 126 is able to receive a next data packet transmission.
`The AT 126 then generates a corresponding DRC value; the
`DRC value is transmitted to the AN 122 to request a data
`transmission. Note that
`typically data transmissions are
`partitioned into packets. The time required to transmit a
`packet of data is a function of the data rate applied.
`
`[0038] This DRC signal also provides the information,
`which the channel scheduler uses to determine the instan-
`
`taneous rate for consuming information (or receiving trans-
`mitted data) for each of the remote stations associated with
`each queue. According to an embodiment, a DRC signal
`transmitted from any remote station indicates that the remote
`station is capable of receiving data at any one of multiple
`effective data rates. Such a variable rate transmission system
`is described in detail in U.S. Pat. No. 6,064,678, entitled
`“Method for Assigning Optimal Packet Lengths in a Vari-
`able Rate Communication System,” issued May 16, 2000,
`assigned to the assignee of the present invention and incor-
`porated by reference herein.
`
`[0039] One example of a communication system support-
`ing HDR transmissions and adapted for scheduling trans-
`missions to multiple users is illustrated in FIG. 7. FIG. 7 is
`detailed hereinbelow, wherein specifically, a base station
`820 and base station controller 810 interface with a packet
`network interface 806. Base station controller 810 includes
`
`a channel scheduler 812 for implementing a scheduling
`algorithm for transmissions in system 800. The channel
`scheduler 812 determines the length of a service interval
`during which data is to be transmitted to any particular
`remote station based upon the remote station’s associated
`instantaneous rate for receiving data (as indicated in the
`most recently received DRC signal). The service interval
`may not be contiguous in time but may occur once every n
`slots. According to one embodiment, the first portion of a
`packet is transmitted during a first slot at a first time and the
`second portion is transmitted 4 slots later at a subsequent
`time. Also, any subsequent portions of the packet are trans-
`mitted in multiple slots having a similar 4 slots spread, i.e.,
`4 slots apart from each other. According to an embodiment,
`the instantaneous rate of receiving data Ri determines the
`service interval length Li associated with a particular data
`queue.
`
`In addition, the channel scheduler 812 selects the
`[0040]
`particular data queue for transmission. The associated quan-
`tity of data to be transmitted is then retrieved from a data
`queue 830 and provided to the channel element 826 for
`transmission to the remote station associated with the data
`
`queue 830. As discussed below, the channel scheduler 812
`selects the queue for providing the data, which is transmitted
`in a following service interval using information including
`the weight associated with each of the queues. The weight
`associated with the transmitted queue is then updated.
`
`

`
`US 2002/0183066 A1
`
`Dec. 5, 2002
`
`[0041] Note that it may be possible for the user to receive
`a packet correctly even if only a portion of the packet is
`transmitted. This occurs when the channel condition is better
`
`than anticipated by the user. In that case, the user may send
`an “ACK” signal to the base station indicating that
`the
`packet
`is already correctly received and the remaining
`portions of the packet need not be transmitted. When this
`happens, the entire data packet is effectively transmitted to
`the user over a shorter service interval thereby increasing the
`effective data rate at which the packet is transmitted. The
`base station then reassigns the time slots that were originally
`scheduled to transmit the remaining portions of that packet
`to transmit another packet either to the same user or to a
`different user. This process is generally referred to as Auto-
`matic Repeat reQuest
`
`is
`In a system supporting ARQ, a data packet
`[0042]
`scheduled for a predetermined number of transmissions,
`wherein each transmission may include different informa-
`tion. The multiple transmissions are interposed with other
`packets sequentially. When a receiver has received sufficient
`information to decode and process the packet, the receiver
`sends an indication to the transmitter that no further infor-
`
`mation is required for the current packet. The transmitter is
`then free to schedule the slots originally scheduled for the
`current packet to another packet. In this way, the system
`resources are conserved and the transmission time to the
`receiver is reduced.
`
`[0043] A block diagram illustrating the basic subsystems
`of an exemplary variable rate communication system is
`shown in FIG. 7. Base station controller 810 interfaces with
`
`packet network interface 806, Public Switched Telephone
`Network, PSTN, 808, and all base stations in the commu-
`nication system (only one base station 820 is shown in FIG.
`7 for simplicity). Base station controller 810 coordinates the
`communication between remote stations in the communica-
`
`tion system and other users connected to packet network
`interface 806 and PSTN 808. PSTN 808 interfaces with
`
`users through a standard telephone network (not shown in
`FIG. 7).
`
`[0044] Base station controller 810 contains many selector
`elements 816, although only one is shown in FIG. 7 for
`simplicity. Each selector element 816 is assigned to control
`communication between one or more base stations 820 and
`
`one remote station (not shown). If selector element 816 has
`not been assigned to a given remote station, call control
`processor 818 is informed of the need to page the remote
`station. Call control processor 818 then directs base station
`820 to page the remote station.
`
`[0045] Data source 802 contains a quantity of data, which
`is to be transmitted to a given remote station. Data source
`802 provides the data to packet network interface 806.
`Packet network interface 806 receives the data and routes
`the data to the selector element 816. Selector element 816
`then transmits the data to each base station 820 in commu-
`
`nication with the target remote station. In the exemplary
`embodiment, each base station 820 maintains a data queue
`830, which stores the data to be transmitted to the remote
`station.
`
`[0046] The data is transmitted in data packets from data
`queue 830 to channel element 826.
`In the exemplary
`embodiment, on the forward link, a “data packet” refers to
`a quantity of data which is a maximum of 1024 bits and a
`
`quantity of data to be transmitted to a destination remote
`station within a predetermined “time slot” (such as z1.667
`msec). For each data packet, channel element 826 inserts the
`necessary control fields.
`In the exemplary embodiment,
`channel element 826 performs a Cyclic Redundancy Check,
`CRC, encoding of the data packet and control fields and
`inserts a set of code tail bits. The data packet, control fields,
`CRC parity bits, and code tail bits comprise a formatted
`packet. In the exemplary embodiment, channel element 826
`then encodes the formatted packet and interleaves (or reor-
`ders) the symbols within the encoded packet. In the exem-
`plary embodiment, the interleaved packet is covered with a
`Walsh code, and spread with the short PNI and PNQ codes.
`The spread data is provided to RF unit 828 which quadrature
`modulates, filters, and amplifies the signal. The forward link
`signal is transmitted over the air through an antenna to the
`forward link.
`
`[0047] At the remote station, the forward link signal is
`received by an antenna and routed to a receiver. The receiver
`filters, amplifies, quadrature demodulates, and quantizes the
`signal. The digitized signal is provided to a demodulator
`(DEMOD) where it is despread with the short PNI and PNQ
`codes and decovered with the Walsh cover. The demodulated
`
`data is provided to a decoder which performs the inverse of
`the signal processing functions done at base station 820,
`specifically the de-interleaving, decoding, and CRC check
`functions. The decoded data is provided to a data sink.
`
`[0048] The hardware, as pointed out above, supports vari-
`able rate transmissions of data, messaging, voice, video, and
`other communications over the forward link. The rate of data
`
`transmitted from the data queue 830 varies to accommodate
`changes in signal strength and the noise environment at the
`remote station. Each of the remote stations preferably trans-
`mits a Data Rate Control, DRC, signal to an associated base
`station 820 at each time slot. The DRC signal provides
`information to the base station 820, which includes the
`identity of the remote station and the rate at which the
`remote station is to receive data from its associated data
`
`queue. Accordingly, circuitry at the remote station measures
`the signal strength and estimates the noise environment at
`the remote station to determine the rate information to be
`
`transmitted in the DRC signal.
`
`[0049] The DRC signal transmitted by each remote station
`travels through a reverse link channel and is received at base
`station 820 through a receive antenna coupled to RF unit
`828. In the exemplary embodiment, the DRC information is
`demodulated in channel element 826 and provided to a
`channel scheduler 812 located in the base station controller
`810 or to a channel scheduler 832 located in the base station
`
`820. In a first exemplary embodiment, the channel scheduler
`832 is located in the base station 820.
`In an alternate
`embodiment, the channel scheduler 812 is located in the
`base station controller 810, and connects to all selector
`elements 816 within the base station controller 810.
`
`In the first-mentioned exemplary embodiment,
`[0050]
`channel scheduler 832 receives information from data queue
`830 indicating the amount of data queued up for each remote
`station, also called queue size. Channel scheduler 832 then
`performs scheduling based on DRC information and queue
`size for each remote station serviced by base station 820. If
`queue size is required for a scheduling algorithm used in the
`alternate embodiment, channel scheduler 812 may receive
`queue size information from selector element 816.
`
`

`
`US 2002/0183066 A1
`
`D