Title of Invention | A SCHEDULER FOR FORWARD LINK RATE SCHEDULING AND METHODS THEREOF |
---|---|
Abstract | The present invention discloses a forward-link rate scheduling method and a scheduler, which method comprises the step of: gathering the information of the maximal scheduling resource available to the system, as well as the data service request information from the scheduling users, wherein the user scheduling measurement includes the short-term scheduling measurement, long-term scheduling measurement and normalized long-term scheduling measurement; creating the scheduling user queue in accordance with the scheduling measurement; allocating the rate and power in accordance with the scheduling user queue and the system-available scheduling resource; clearing the users which have obtained the resource from the scheduling user queue and notifying the allocation result to selectors and channel units. The invention allows for the wireless environment and available resource of the system comprehensively, which is capable of improving the utilization efficiency of the system resource, as well as reducing the transmission delay of scheduling user data, while allowing for the fairness of scheduling. |
Full Text | FORWARD-LINK RATESCHEDULING METHOD AND SCHEDULER I he present invention relates to the field of data communication, and in particular, relates to a method and scheduler for forward-link rate scheduling in high rate data service of CDMA system. BACKGROUND OF THF INVENTION With the incessant expanding of wireless services and the rapid developing of Internet services, single voice service has not satisfied users' requirements. Many users hope that a mobile communication system can provide most services of the existing communication network (including ISDN. ADSL). Therefore, in a new generation mobile communication system, data services represented by multimedia services will occupy a dominant position. It is demanded thai the system should provide stronger support for data services, and combination services of data and voice. To realize the object, it is a key to utilize wireless resources reasonably and efficiently according to characteristks of data services. When a base station needs to transmit a number of data to a remote user, it is an important process for utilizing wireless resources reasonably and efficiently to schedule rate allocated to the users. In a paper of "Down-Link Scheduling in CDMA Data Networks", it is proposed that if the base station allocates available system resources to only one user when scheduling, the utilization of forward link channel may be maximized. However the scheduling method is inclined excessively to the user with better channel environment, and causes longer time delay for the data of the user with relatively bad channel environment, which is unacceptable for most user because of its extremely unfairness. Therefore, a good rate scheduling method should both improve the utilization of wireless resources, and ensure fairness among the users in the system. US patent 6,229,79581, "System for Allocating Resources in a Communication System", provided a scheduling method giving attention both to resources utilization and user fairness. Assuming that an instantaneous rate allocated to a user by a base station is R, and an average rate is C, if R>C. the base station allocates a smaller weight to the user; if R When the .system schedules the user's rate, the scheduling smoothness is a non-negiigible iacioi. The so-called scheduling smoothness means that when increasing some users' priorities, the priorities of other users in the system should not be reduced rapidly. In other words, increasing and reducing of users' priorities should be a smooth process. It should be noted that the existing rate scheduling method can't synthetically consider users' wireless environment, available system resources, and scheduling smoothness, which should be considered and improved. SUMMARY OF THE INVENTION An object of the present invention is to provide a method for scheduling forward link rate in communication network. A further object of the present invention is to provide an apparatus for scheduling forward link rate in communication network. To realize the objects of the present invention, the present invention provides the following technical solutions: A method for forward-link rate scheduling of the present invention includes the steps as follows: a. collecting and obtaining maximum scheduling resources information available for a system and data service requirement information from scheduling users; b. calculating scheduling metrics of scheduling users, the scheduling metrics include short-term scheduling metrics, long-term metrics and normalized long-term metrics; c. creating a scheduling user queue according to scheduling metrics: d. allocating rate and power according to the scheduling user queue and scheduling resources available for the system; e. removing the user who has obtained the resources from the scheduling user queue, and sending the allocating result to a selector and at least one of channel units; and f. ending a scheduling cycle and waiting for scheduling the next cycle following the above steps. The above step c of creating a scheduling user queue further includes the following steps: c 1. creating an active scheduling user queue; c2. creating an inactive scheduling user queue: c3. checking if the long-term scheduling metric of an active scheduling user is larger than a fixed threshold constant 11; c4. checking if the difference between the long-term scheduling metric of the active scheduling user und the lor.g term scheduling metric of an inactive scheduling user is larger than a fixed threshold constant T?.; c5. inserting the inactive scheduling user in front of the active scheduling user and removing the inactive user from the inactive scheduling user queue: and c6. checking whether all active scheduling users have been polled, and ending the process if ture, or running steps c i to c5 repeatedly until all active scheduling users have been polled if false. In above step c3, if the long-term scheduling metric of an active scheduling user is larger than the fixed threshold constant Tl, next step c4 is executed sequentially; otherwise the step c6 will be executed directly. In above step c4, if the difference between the long-term scheduling metric of the active scheduling user and the long-term scheduling metric of an inactive scheduling user is larger than the fixed threshold constant T2, next step c5 is executed sequentially; otherwise the step c6 will be executed directly. The method for forward-link rate scheduling of the present invention further includes die following steps after the step e: checking if no any scheduling resources is available for system or the scheduling queue is empty; and returning to step d if false, or updating first the scheduling metric of scheduling users and then executing the step f if true. The process of updating the scheduling metric of scheduling users, further includes the following steps: el. updating target rates of scheduling users, the target rate may be a request rate of latest packet calling, or the maximum or average of latest scheduling rates of scheduling users; e2. updating the short-term scheduling metrics of scheduling users; e3. updating the long-term scheduling metrics of scheduling users; and e4. updating the normali/ed long-term scheduling metrics of scheduling users. I he present invention provides a scheduler tor forward link rate scheduling used by a base station of (.'DM \ communicating svslem ! he scheduler includes H memory, a timer and a controller. 1 he memory recei\es and saves data service request informauoii of scheduling users and maximum scheduling resources information of the system. The controller is connected with the output of the timer. The timer provides time setting for the controller to execute forward link rate scheduling. The controller and memory interconnect. The controller is employed to calculate scheduling metrics of scheduling users, create an scheduling user queue, allocate rate according to the scheduling user queue and scheduling resources available for system, remove a user who obtains the resources from the scheduling user queue, and send the allocating result to the selector and at ICUM vne of channel units. BRIEF DESCRIPTION OF THE DRAWINGS Figure 1 is a schematic diagram of a simplified CDMA communication system; Figure 2 is a structure schematic diagram of a base station including the scheduler of tk; present invention; Figure 3 is a structure schematic diagram of the scheduler of the present invention; Figure 4 is a flow chart of the scheduling method of the present invention; Figure 5 is a flow chart of creating a scheduling user queue according to the present invention; Figure 6 is a flow chart of the method for updating scheduling metric according to the present invention. DESCRIPTION OF THE PREFERRED EMBODIMENT(S) Code division multiple access (CDMA) is a multiple access modulation technology with the most competition in the new generation mobile communication. To illustration the present invention more clearly, CDMA communication system is introduced first. As shown in Figure 1. mobile station (MS) 107A or 107B communicates with base station controller (BSC) 105A through base transceiver station (BTS) 101A or 101 B. Sometime the MS may communicate with two base stations. For example, the MS 107B communicates with BTS 101A and 101B at the same time. BSC 105A also communicates with PSTN or ISDN through a mobile switching center (MSC) 103. Meanwhile a MSC 103 also connects with other BSC 105B. As shown in Figure 2, it is a structure schematic diagram of a base station including the scheduler of the present invention. Data source 201 contains lots of packet data that need to be sent to the remote MS 107. As the difference of practical system implementations. Data source 201 can be positioned in BSC 105 or MSC 103. A lot of selector units 205 and channel units 207 are inside the base station. Selector unit 205 is employed to control the communication between Data source 201 and channel unit 207. Selector unit 205 and channel unit 207 are both controlled by scheduler 203. Under the instructing of scheduler 203, selector unit 205 transfers the packei data stored in Data source 201 to channel unit 207. Channel unit 207 implements a series of processing for the data send by selector unit 205. In general, these processing include: adding control bit, adding CRC bit, adding trail bit, coding, interweaving, Wlash orthogonal modulating, and PN short code modulating, etc. Finally, transmitter 209 transmits the signals processed by channel unit to the remote MS. To be convenient for illustration, the structure of the scheduler of the present invention is introduced first. As shown in Figure 3 representing the internal structure of the scheduler, scheduler 203 includes memory 301, timer 303, and controller 305. Memory 301 is employed to store scheduling resources information available for the base station and data service request information. The scheduling resources information available for the base station includes the resources of power, rates, orthogonal .codes, channel units and so on to be allocated by the base station to the MS that requests a data service. Data service request information includes the identification of the mobile stations that requests the data services, the data traffic of MS, request rates, MS scheduling metrics, the latest scheduling rates, etc. Timer 303 provides time setting for controller 305 to implement forward link rate scheduling. Timer 303 may be realized by using a system clock, an oscillator on the circuit board locked on external signals, or a counter driven by receiving system memory cell and synchronized with the external signals. At the scheduling time, controller 305 implements rate scheduling for the MS of requesting data service according to the information provided by memory 301, and sends the rate scheduling result to the relevant selector unit 2C5 and channel unit 207. The present invention provides a method for forward link data scheduling in CDMA communication system. The system comprises at least a cell and at least one scheduling user. The method of the present invention includes the following steps: a. collecting and acquiring maximum scheduling resources information available for a system and data service requirement information for scheduling users; b. calculating scheduling metrics of scheduling users, the scheduling metrics include short-term scheduling metrics, long-term metrics and normalized long-term metrics; c. creating a scheduling user queue according to scheduling metrics; d allocating rate and power according to the scheduling user queue and scheduling resources available for the system: e. removing ;» user who has obtained the resources from the scheduling queue, and sending the allocating result to a selector and ai least one of channel units; and f. ending a scheduling cycle and waiting for scheduling a next cycle following the above steps. The method for forward link data scheduling of present invention further includes the following steps after the step e: checking if no any scheduling resources is available for the system or the scheduling queue is empty; and returning to step e if false, or updating first the scheduling metric of scheduling users and then executing the step f if true. The realization of the above method can refer to Figure 4 continuously. In Figure 4, since the method of the invention is realized by the software solidified in the controller 305, each step is denoted by a module. In the module 401, the controller 305 acquires the information of the maximal scheduling resource available for the system, and the data service reqaest information from the memory 301, which is a basis for the controller to schedule the rate. In the module 403, the controller 305 creates the scheduling user queue in accordance with the user scheduling metrics. The principle of creating the user queue is the higher the priority of the scheduling user, the upper it ranks in the scheduling user queue. In the module 405, the controller 305 allocates the rates to the scheduling users according to the sequence of the scheduling user queue, which is limited under the current available scheduling resources. In the module 407, the controller 305 removes the user who has obtained the resources from the scheduling user queue. Meanwhile, the controller 305 notifies relevant selector unit 205 to transmit the scheduling user data to the, channel unit 207. The channel unit 207 then processes the data according to the rate allocated by the controller 305. In the module 409, if the controller 305 detects that system still has available scheduling resources and the scheduling user queue is not empty, the controller 305 repeats the processes from the module 405 to the module 409; otherwise, implements the module 411 directly to update the schedulingmetric of the scheduling users. In the module 413, the controller 305 waits for the next scheduling period and repeats the processes from the module 401 to the module 411 according to the indication of timer 303. Please refer to Figure 5. In the step c, the creating of the scheduling user queue is implemented according to the following steps: v 1. creating an active scheduling user queue; c2. creating an inactive scheduling user queue; c.l. checking if the long-term scheduling metric of an active scheduling user is more than fixed threshold constant Tl; c4. checking if the difference between the long-term scheduling metric of the active scheduling user and the long-term scheduling metric of an inactive scheduling user is more than fixed threshold constant T2; c5. inserting the inactive scheduling user to the front of the active scheduling user and removing the inactive user from the inactive scheduling user queue; and c6. checking if all active scheduling users has been polled, and ending the process if ture, or running steps cl to c5 repeatedly until ali active scheduling users have been polled if false. In above step c3, if the long-term scheduling metric of an active scheduling user is larger than fixed threshold constant Tl, next step c4 is executed sequentially; otherwise the step c6 will be executed directly. In above step c4, if the difference between the long-tenn scheduling metric of the active scheduling user and the long-term scheduling metric of the inactive scheduling user is larger than the fixed threshold constant T2, next step c5 is executed sequentially; otherwise the step c6 will be executed directly. According to the above consideration, in order to describe easily we divide the mobile stations involved in scheduling into two classes: an active scheduling user, which has acquired the rate allocated by the controller 305 in the latest rate scheduling; an inactive scheduling user, which has not acquired the rate allocated by the controller 305. In the module 501, the controller 305 creates the active scheduling user queue according to the normalized long-term scheduling metric of the active scheduling users. The smaller the normalized long-term scheduling metric of the active scheduling user, the upper it ranks in the active scheduling user queue. In the module 503, the controller 305 creates the inactive scheduling user queue according to the normalized long-term scheduling metric of the inactive scheduling users. The creating principle is the same with that of the module 501. In the module 505, if the controller 305 detects that the long-term scheduling metric of the active scheduling user satisfies the equation (1), then the module 507 is executed; otherwise, the module 513 is executed. In the module 507, if the controller 305 detects that the long-term scheduling metric of the active scheduling user and the long-term scheduling metric of an inactive scheduling user satisfy the equation (2), then the module 509 is executed; otherwise, the module 511 is executed. Ti and T2 in the equation (1) and (2) arc all fixed threshold constant. Through selecting the threshold TI and T2 carefully, the rate scheduling for user can oe smoothly executed by system. In the module 509, the controller 305 inserts the inactive scheduling user before the related active scheduling user, and removes the inactive scheduling user from the inactive scheduling user queue. In the module 5! 1. the controller 305 detects if ail the inactive scheduling users have been traversed. If true, then the module 513 is executed; otherwise, repeat the process from the module 507 to the module 511. In the module 513, the controller 305 detects if all the active scheduling users have been traversed. If true, then the module 515 is executed: otherwise, repeat the process from the module 503 to the module 513. In the module 515, the controller 305 combines the active scheduling user queue and the inactive scheduling user queue (the active scheduling user queue is preceding) as the scheduling user queue, and then the process of creating the scheduling user queue is ended. the long-term scheduling metric of theactive scheduling user > TI (1) (the long-term scheduling metric of the active scheduling user) - (the long-term scheduling metric of the inactive scheduling user) > T2 (2) It should be noted that the method for creating the scheduling user queue is different with the difference of the system realizing For example, when the influence of signaling overhead for creating data service channels upon the forward-link utilization can be ignored, the controller can create the scheduling user queue only based on the normalized long-term scheduling metric. The smaller the normalized long-term scheduling metric of the scheduling user, the upper it ranks in the scheduling user queue. These methods are all included in the invention. Please refer to Figure 6. The process of updating the scheduling metric of the scheduling users further includes the following steps: el. updating the target rate of the scheduling user, because of the difference of the application situation, the target rate may be the request rate achieved by the latest packet calling, or the maximum value of the latest scheduling rates of the scheduling users, or the average value of the latest scheduling rates of the scheduling users: e2. updating the short-term scheduling metrics of the scheduling users; e3. updating the long-term scheduling metrics of the scheduling users; and e4. updating the normalized long-term scheduling metrics of the scheduling users. According to the above method, to facilitate the illustration, above steps of updating the scheduling metric of the scheduling user is described again as follows: In module 603. the controller 305 updates the short-term scheduling metric of the scheduling user. The definition of the short-term scheduling metric is defined by equation (3): denotes the instantaneous rate acquired by the scheduling user; R denotes the target rate of the scheduling user; a denotes the weight factor of relevant scheduling user. The weight factor ° has relation with the instantaneous rate acquired by the scheduling user and the resources consumed. For example, for a CDMA cellular system with the forward-link power limited, if the instantaneous rate acquired by the scheduling user is , the nominal power pi f.\ consumed by base station 101 for supporting the rate is v consumed by base station 101 for support the rate is ^r'1 , then the weight factor a can be gotten using equation (4), in which ^ is controlling factor, which reflects the degree that base station 101 prefers the scheduling users with better wireless channel environment The bigger the value of * , the more rate allocating opportunities obtained by the scheduling user with better wireless channel environment, and the bigger the capacity of forward-link resources. However, when system resources is lacking, a overmuch ^ value will cause that the users with bad wireless channel environment can not acquire rates for a long time. Therefore, the system engineers should consider the balance of the following two aspects when choosing the factor * : (1) increasing the capacity of the forward-link; and (2) avoiding the situation that the scheduling users with bad wireless channel environment cannot acquire the rate allocation for a long time or can only acquire very low rate allocation. (3) In module 605. the controller 305 updates the long-term scheduling metric of the scheduling users. The long-term scheduling metric reflects the satisfaction degree of the scheduling users for resource allocating during scheduling many times. Assume that the c short-term scheduling metric of a scheduling user at scheduling n times is AT DnD, then die lonj-term scheduling metric of the scheduling user at scheduling r. times, StiCn), is: (5) \\ herein, N is a fixed constant. In module 607, the controller 305 updates the normalized long-term scheduling metric of the scheduling user. The normalized long-term scheduling metric reflects the average satisfaction degree of the scheduling users for resources allocating during scheduling many times. Assume that the long-term scheduling metric of a scheduling user at scheduling n times is Sn(n), then the normalized long-term scheduling metric of the scheduling user at scheduling n times, SNITCH) is: n For a scheduling user of acquiring rate allocating first time, we assume that the original long-term scheduling metric and normalized long-term scheduling metric of the user before the rate allocating is acquired are both zero. Soft switch is not discussed in the process of module 607 above. As shown in Figure 1, when mobile station 107A ceases the communication with base station 101 and begins the communication with base station 101B, base station 101B should randomly allocate a original normalized long-term scheduling metric value to mobile station 107A to ensure the smoothness of the rate scheduling of base station 101B. The original normalized long-term scheduling metric value should be between the maximum normalized long-term scheduling metric value and the minimum normalized long-term scheduling metric value of the system. For the step of updating the target rate of the scheduling users, the target rate reflects the desired rate of the users. The target rate is allowed to have different reflecting forms, because of the difference of the system realization. For example, it can be replaced by the request rate achieved by the scheduling user for the latest packet calling, or the maximum value or average value among the latest several times scheduling rates of the scheduling users. These reflecting forms are all included in the invention. The above embodiment illustrates and describes the invention. A person skilled in the art c?n modify the embodiment without deviating from the principle and the range of the invention. For example, the transmitting power in equation (4) can be changed to the receiving power, and the invention can also be used to rate scheduling of the backward-link data service, which is not described in detail here. INDUSTRIAL PRACTICAL APPLICABILITY With the above scheduling method and scheduler, the invention can comprehensively considers the wireless environment and available system resources, improve effectively the utilization efficiency of the system resources, and reduce the transmission delay of scheduling user data. The present invention also considers the fairness between scheduling users. Meanwhile it also considers the smoothness of scheduling. With the smoothness of scheduling, on the one hand, the times of building and releasing for data service channel can be reduced. In general, more signaling overhead are needed for building and releasing service channel. The reducing of the times for building and releasing data service channel means the increasing of resources utilization efficiency. On the other hand, die user satisfaction degree to the system can be ensured at a certain extent. We Claim : 1. A scheduler for forward link rate scheduling, used by a base station of CDMA communication system, wherein the scheduler comprising; a memory (301), a timer (303) and a controller (305); the memory (301) receives and saves data service request information of scheduling users and maximum scheduling resources information of the system; the controller (305) is connected with the output of the timer (303) which provides time setting for the controller (305) to execute forward link rate scheduling; and the memory (301) is interconnected with the controller (305) which is employed to calculate scheduling metrics of scheduling users, create an scheduling user queue, allocate speed rate according to the scheduling user queue and scheduling resources available for system, remove a user who obtains the resources from the scheduling user queue, and send the allocating result to a selector (205) and at least one of channel units (207). 2. A method for forward link rate scheduling using a scheduler as claimed in claim 1 , wherein said method comprising the following steps: a) collecting and obtaining maximum scheduling resources information available for a system and data service requirement information from scheduling users and storing in the memory (301) b) calculating scheduling metrics of scheduling users using the controller (305) , the scheduling metrics with short-term scheduling metrics, long-term metrics and normalized long-term metrics; c) creating a scheduling user queue using the controller (305) according to scheduling metrics; d) allocating rate and power according to the scheduling user queue using the controller (305) and scheduling resources available for the system; e) removing the user who has obtained the resources from the scheduling user queue using the controller ( 305), and sending the allocating result to a selector and at least one of channel unit; and f) ending a scheduling cycle and waiting for scheduling the next cycle following the above steps, using timer (303). 3. The method as claimed in claim 2, wherein the step c of creating a scheduling user queue optionally the following steps: cl. creating an active scheduling user queue; c2. creating an inactive scheduling user queue; c3. checking if the long-term scheduling metric of an active scheduling user is larger than a fixed threshold constant Tl; c4. checking if the difference between the long-term scheduling metric of the active scheduling user and the long-term scheduling metric of an inactive scheduling user is larger than a fixed threshold constant T2; c5. Inserting the inactive scheduling user in front of the active scheduling user and removing the inactive user from the inactive scheduling user queue; and c6. checking whether all active scheduling users have been polled, and ending the process if true, or running steps cl to c5 repeatedly until all active scheduling users have been polled if false. 4. The method as claimed in claim 3, wherein in the step c3, if the long-term scheduling metric of an active scheduling user is larger than the fixed threshold constant Tl, next step c4 is executed sequentially; otherwise the step c6 will be executed directly. 5. The method as claimed in claim 3, wherein in the step c4, if the difference between the long-term scheduling metric of the active scheduling user and the long-term scheduling metric of an inactive scheduling user is larger than the fixed threshold constant T2, next step c5 is executed sequentially; otherwise the step c6 will be executed directly. 6. The method as claimed in claim 2, wherein the method optionally the following steps after the step e: checking whether no any scheduling resources is available for system or the scheduling queue is empty; and returning to step d if false, or updating first the scheduling metric of scheduling users and then executing the step f if true. 7. The method as claimed in claim 6, wherein the process of updating the scheduling metric of scheduling users optionally the following steps: el. updating target rates of scheduling users, the target rate is a request rate of latest packet calling, or the maximum or average of latest scheduling rates of scheduling users; e2. updating the short-term scheduling metrics of scheduling users; e3. updating the long-term scheduling metrics of scheduling users; and e4. updating the normalized long-term scheduling metrics of scheduling users. 8. A scheduler for forward link rate scheduling, used by a base station of CDMA communication system substantially as herein described with reference to the accompanying specification , examples and drawings. 9. A method for forward link rate scheduling substantially as herein described with reference to the accompanying specification, examples and drawings. |
---|
2535-DELNP-2005-Abstract-04-04-2008.pdf
2535-delnp-2005-claims-(02-06-2008).pdf
2535-DELNP-2005-Claims-04-04-2008.pdf
2535-delnp-2005-correspondence-others-(02-06-2008).pdf
2535-DELNP-2005-Correspondence-Others-04-04-2008.pdf
2535-DELNP-2005-Correspondence-Others-09-04-2008.pdf
2535-delnp-2005-correspondence-others.pdf
2535-delnp-2005-description (complete)-02-06-2008.pdf
2535-delnp-2005-description (complete).pdf
2535-DELNP-2005-Drawings-04-04-2008.pdf
2535-DELNP-2005-Form-1-04-04-2008.pdf
2535-DELNP-2005-Form-13-09-04-2008.pdf
2535-DELNP-2005-Form-2-04-04-2008.pdf
2535-DELNP-2005-Form-3-09-04-2008.pdf
2535-DELNP-2005-GPA-04-04-2008.pdf
2535-delnp-2005-pct-search report.pdf
2535-DELNP-2005-Petition-137-09-04-2008.pdf
Patent Number | 221057 | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Indian Patent Application Number | 2535/DELNP/2005 | ||||||||||||
PG Journal Number | 31/2008 | ||||||||||||
Publication Date | 01-Aug-2008 | ||||||||||||
Grant Date | 13-Jun-2008 | ||||||||||||
Date of Filing | 10-Jun-2005 | ||||||||||||
Name of Patentee | ZTE CORPORATION | ||||||||||||
Applicant Address | ZTE PLAZA, KEJI ROAD SOUTH, HI-TECH INDUSTRIAL PARK, NANHAN DISTRICT, SHENZHEN CITY, GUANGDONG PROVINCE 518057, P.R.CHINA | ||||||||||||
Inventors:
|
|||||||||||||
PCT International Classification Number | H04Q 7/22 | ||||||||||||
PCT International Application Number | PCT/CN2002/000809 | ||||||||||||
PCT International Filing date | 2002-11-13 | ||||||||||||
PCT Conventions:
|