Method and system for scheduling radio resources in cellular networks

Abstract

A method for scheduling radio resource allocation among active flows within a wireless communication network. The method includes, at each working period of the scheduling method; for each active flow, checking presence of priority data to be transmitted within the current working period. Each active flow having priority data to be transmitted within the current working period is classified as a priority active flow. The remaining active flows are classified as non-priority active flows, the non-priority active flows having non-priority data that need not to be transmitted within the current working period. Radio resources are allocated among the priority active flows, and corresponding priority data are transmitted over the respective allocated resources. After completing priority data transmission, the radio resources are allocated among the non-priority active flows and corresponding non-priority data are transmitted over the respective allocated radio resources until the end of the current working period.

Claims

1. A method for scheduling radio resource allocation among active flows within a wireless communication network, the method comprising, at each working period of the scheduling method: for each active flow, checking presence of priority data to be transmitted within the current working period based on a comparison between data queued at a reference working period before the current working period and data transmitted between the reference working period and the current working period; classifying as a priority active flow each active flow having priority data to be transmitted within the current working period; classifying remaining active flows as non-priority active flows, the non-priority active flows having non-priority data that need not to be transmitted within the current working period; allocating radio resources among the priority active flows and transmitting the corresponding priority data over the respective allocated resources; and after completing priority data transmission, allocating the radio resources among the non-priority active flows and transmitting the corresponding non-priority data over the respective allocated radio resources until the end of the current working period.

2. The method according to claim 1, wherein the checking the presence of priority data to be transmitted within the current working period comprises, for each active flow: retrieving a number β of working periods required for the active flow to meet a respective maximum allowed delivery delay; and wherein the classifying priority active flows comprises, for each active flow: selecting as reference working period the (β-2)-th working period before the current working period, and classifying the active flow as priority active flow if data queued at the beginning of the selected reference working period before the current working period is greater than data transmitted between the selected reference working period and the current working period, the difference between the queued data and the transmitted data identifying the priority data to be transmitted within the current working period.

3. The method according to claim 2, further comprising associating a service class to each priority active flow according to an amount of priority data to be transmitted, the allocating radio resource and the transmitting the corresponding priority data being carried out beginning from priority active flows associated with a highest service class to the priority active flows associated with a lowest service class.

4. The method according to claim 1, wherein each working period comprises a plurality of transmission time intervals, the allocating radio resources among the priority active flows and the transmitting the corresponding priority data over the respective allocated radio resources being carried out at each transmission time interval until completing priority data transmission.

5. The method according to claim 4, for each transmission time interval the method further comprising classifying the priority active flows whose priority data transmission has been completed during the current transmission time interval as non-priority active flows.

6. The method according to claim 1, wherein the classifying priority active flows comprises classifying as priority active flow each multimedia/real-time active flow having priority data to be transmitted within the current working period, the non-priority active flows comprising non-priority multimedia/real-time active flows and best-effort active flows.

7. The method according to claim 6, wherein the best-effort active flows comprise web-browsing, e-mailing, and voice data traffic.

8. The method according to claim 6, wherein, for each transmission time interval and before an end of the current working period, the allocating the radio resources among the non-priority active flows comprises: computing a metric for each non-priority active flow, and allocating the radio resources among non-priority active flows having highest metrics.

9. The method according to claim 8, wherein the metric is in direct relationship to an instantaneous data rate reachable by the non-priority active flow and in reverse relation to an average rate thereof.

10. The method according to claim 9, wherein, for each non-priority multimedia/real-time active flow the metric is in direct relationship to a queuing delay of a first queued data packet, and in reverse relationship to a maximum allowed transmission delay.

11. The method according to claim 10, wherein the metric for each non-priority multimedia/real-time active flow is weighted by an amount depending on a respective service class.

12. A non-transitory computer readable medium including computer program loadable into at least one internal memory of a computer system with input units, output units, and processing units, the computer program comprising executable software configured to carry out the method according to claim 1, when running in the computer system.

13. A wireless communications network comprising: at least one network cell, the at least one network cell comprising a station providing radio coverage over the network cell and at least one further station for putting into communication the station with at least one corresponding user equipment within the network cell, at least one between the station and the at least one further station comprising a scheduler unit for autonomously scheduling allocation of radio resources among active flows within the network cell; the scheduler unit configured to: for each active flow, check presence of priority data to be transmitted within the current working period based on a comparison between data queued at a reference working period before the current working period and data transmitted between the reference working period and the current working period; classify as a priority active flow each active flow having priority data to be transmitted within the current working period; classify remaining active flows as non-priority active flows, the non-priority active flows having non-priority data that need not to be transmitted within the current working period; allocate radio resources among the priority active flows and transmit the corresponding priority data over the respective allocated radio resources; and after completing priority data transmission, allocate the radio resources among the non-priority active flows and transmitting the corresponding non-priority data over the respective allocated radio resources until the end of the current working period.

14. The wireless communications network according to claim 13, wherein the wireless communications network is a cellular network based on LTE/LTE-Advanced technology.

15. The wireless communication network according to claim 14, wherein the station has a first transmission power and a first area coverage, and the at least one further station has a second transmission power and a second area coverage, the first transmission power being higher than the second transmission power and the first area coverage being wider than the second area coverage.

Description

BRIEF DESCRIPTION OF THE ANNEXED DRAWINGS

(1) These and other features and advantages of the present invention will be made apparent by the following description of some exemplary and non limitative embodiments thereof; for its better intelligibility, the following description should be read making reference to the attached drawings, wherein:

(2) FIG. 1 schematically shows a cellular network portion wherein the solution according to one or more embodiments of the present invention may be applied;

(3) FIG. 2 schematically shows a flow chart illustrating a sequence of operations of a scheduling algorithm according to an embodiment of the present invention, and

(4) FIG. 3 schematically shows a timeline of the scheduling algorithm.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS OF THE INVENTION

(5) With reference to the drawings, a cellular network 100 wherein the solution according to one or more embodiments of the invention may be applied is illustrated in FIG. 1. The cellular network 100 (e.g., compliant with the 3GPP LTE/LTE-Advanced standard) comprises a plurality (only one depicted in the figure) of fixed-location transceiver nodes or stations, also known as eNodeB, such as the eNodeB 105. One or more eNodeBs, such as the eNodeB 105, provide for radio coverage over a geographic area, also referred to as network cell, such as the network cell 110, for allowing user equipments (UEs) within the network cell (such as the UEs 115—e.g., mobile phones—within the network cell 110) to exchange data (e.g., web browsing, e-mailing or voice data traffic—also referred to as best-effort flows—and/or data traffic for multimedia/real-time applications—also referred to as multimedia/real-time flows).

(6) As visible from the figure, the cellular network 100 also comprises a plurality (three, in the example at issue) of low-power, small coverage nodes (e.g., pico, micro, femto and/or relay nodes) 120, each one identifying a respective small cell within the network cell (or macro cell) 110 for increasing network capacity (especially at macro cell 110 edges) and to autonomously facilitate communication between some, or all, the UEs 115 within the macro cell 110 and the eNodeB 105.

(7) For the sake of completeness, as well known by those having ordinary skill in the art, the eNodeBs, such as the eNodeB 105, form the radio access network; in turn, the radio access network is generally communicably coupled with one or more core networks (not shown), which may be coupled with other networks, such as Internet and/or public switched telephone networks (not illustrated).

(8) According to an embodiment of the present invention, the eNodeB 105 and the nodes 120 (e.g., through a scheduler unit, or scheduler, thereof) are configured to autonomously implement a scheduling algorithm aimed at properly scheduling radio resources allocation among multimedia/real-time flows and best-efforts flows that are active in the network cell 110 (hereinafter, multimedia/real-time active flows and best-effort active flows).

(9) In the following, radio resources allocation according to 3GPP specifications will be considered. According to 3GPP specifications, radio resources are allocated in time/frequency domain. In time domain, radio resources are distributed every transmission time interval (TTI), each one lasting 1 ms and comprising two time slots of 0.5 ms, whereas in frequency domain the whole bandwidth is divided into 180-kHz sub-channels (corresponding to 12 consecutive and equally spaced sub-carriers). A time/frequency radio resource, spanning over one TTI lasting 1.0 ms in time domain and over one sub-channel in frequency domain, will be referred to as PRB (“Physical Resources Block”), and corresponds to the smallest radio resource that can be allocated to a UE for data transmission.

(10) With reference now to FIG. 2, it schematically shows a flow chart illustrating a sequence of operations of a scheduling algorithm 200 according to an embodiment of the invention. For the sake of description ease, reference will be also made to FIG. 3, which schematically shows a timeline of the scheduling algorithm 200.

(11) The scheduling algorithm 200 has a working period T.sub.WP, e.g. multiple (by a predefined, preferably integer, amount α) of a TTI—thus, T.sub.WP=αTTI. In other words, each working period T.sub.WP comprises α TTI.sub.k (k=1, 2, . . . , α).

(12) At the beginning of each working period T.sub.WP (time instant t), multimedia/real-time active flows to be delivered (i.e., checked as having data to be transmitted) within the current working period T.sub.WP are classified as priority active flows (as will be discussed shortly, based on a comparison between data queued at a reference working period before the current working period and data transmitted between the reference working period and the current working period), and put into a priority group (block 205)—however, in an alternative embodiment, also best-effort active flows having data to be transmitted within the current working period T.sub.WP are classified as priority active flows. Hereinafter, for the sake of description ease, any time instant (such as time instant t) is intended as normalized on working period T.sub.WP.

(13) Classifying multimedia/real-time active flows as priority active flows is performed by taking into account the following parameters: D.sub.i: maximum allowed delay for delivering (i.e., queuing and transmitting data of) the i-th multimedia/real-time active flow associated with a required (multimedia/real-time) service. D.sub.i=β.sub.iT.sub.WP, where β.sub.i=D.sub.i/T.sub.WP is the number of working periods T.sub.WP required for i-th multimedia/real-time active flow delivering. Thus, assuming that a certain amount of data of the i-th multimedia/real-time active flow have been queued during a working period T.sub.WP between (n.sub.i−1) and n.sub.i time instants, transmission of such queued data should be completed within time instant t=(n.sub.i−1+β.sub.i)—time deadline—for meeting maximum allowed delay D.sub.i requirement. Q.sub.i(t−β.sub.i+2): amount of data (of the i-th multimedia/real-time active flow) queued at the (β.sub.i−2)-th working period T.sub.WP before the current working period T.sub.WP. Thus, as will be readily understood from below, the (β.sub.i−2)-th working period T.sub.WP before the current working period T.sub.WP is used, in the exemplary disclosed embodiment, as reference working period T.sub.WP for checking whether an active flow (e.g., a multimedia/real-time active) has priority data to be transmitted within the current working period T.sub.WP (anyway, any reference working periods T.sub.WP, i.e. the reference working period T.sub.WP for each i-th active flow could be selected according to respective criteria, e.g. not necessarily dependent from the β.sub.i parameter). By definition, the current working period T.sub.WP is the (β.sub.i−1)-th working period T.sub.WP from data queuing at (t−β.sub.i+2) time instant, i.e. the last one available for completing queued data transmission. In the example at issue (data queued between (n.sub.i−1) and n.sub.i, time instants), when t=(n.sub.i−2+β.sub.i), Q.sub.i(t−β.sub.i+2) parameter is the overall amount of queued data Q.sub.i(n.sub.i) that, from time instant n.sub.i (i.e., at the beginning of the reference working period T.sub.WP), should be transmitted before time deadline for meeting said maximum allowed delay D.sub.i requirement.

(14) $\underset{j=1}{\overset{{\beta }_i-2}{.Math.}}{q}_i\left(t-j\right)$ overall amount of data of the i-th multimedia/real-time active flow transmitted during the latest β−2 working periods T.sub.WP before the current working period T.sub.WP (i.e., between the reference working period T.sub.WP and the current working period T.sub.WP). As will be better disclosed shortly, if the current working period T.sub.WP is the last one available for delivering the i-th multimedia/real-time active flow, and i-th multimedia/real-time active flow delivery has not been carried out already, the amount

(15) $\underset{j=1}{\overset{{\beta }_i-2}{.Math.}}{q}_i\left(t-j\right)$  is lower than the amount Q.sub.i(t−β.sub.i+2) and the multimedia/real-time i-th active flow will be classified as priority active flow for the current working period T.sub.WP.

(16) Upon reception/calculation/retrieval of D.sub.i, Q.sub.i(t−β.sub.i+2) and

(17) $\underset{j=1}{\overset{{\beta }_i-2}{.Math.}}{q}_i\left(t-j\right)$
parameters of each i-th multimedia/real-time active flow, i-th multimedia/real-time active flows are classified as priority active flows (for the current working period Tw) if

(18) $Q_i\left(t-{\beta }_i+2\right)-\underset{j=1}{\overset{{\beta }_i-2}{.Math.}}{q}_i\left(t-j\right)>0,$

(19) namely if the overall amount of data (of the i-th multimedia/real-time active flow) queued at the beginning of (β.sub.i−2)-th working period T.sub.WP before the current working period T.sub.WP is greater than the overall amount of data transmitted during the latest β−2 working periods T.sub.WP before the current working period T.sub.WP (i.e., between the reference working period T.sub.WP and the current working period T.sub.WP).

(20) If the inequality of above is not satisfied, it means that, for the i-th multimedia/real-time active flow, queued data having time deadline at (t+1) time instant have not been transmitted already at (current) time instant t. Thus, the current working period T.sub.WP is the last one available for transmitting such queued data, and the i-th multimedia/real-time active flow is classified as priority active flow.

(21) In order to meet maximum allowed delay D.sub.i requirement, the following amount of data q.sub.i(t) (or priority data) has to be transmitted between t and (t+1) time instants:

(22) $q_i\left(t\right)=Q_i\left(t-2+{\beta }_i\right)-\underset{j=1}{\overset{{\beta }_i-2}{.Math.}}{q}_i\left(t-j\right)$

(23) If instead the inequality of above is satisfied, it means that, for the i-th multimedia/real-time active flow, queued data having time deadline at (t+1) time instant have already been transmitted before (current) time instant t—thus, the i-th multimedia/real-time active flow is not considered as priority active flow.

(24) All i-th multimedia/real-time active flows not considered as priority active flows are classified, together with best-effort active flows, as non-priority active flows and put into a non-priority group (block 210).

(25) Distinguishing multimedia/real-time active flows from best-effort active flows, and classifying as priority active flows the multimedia/real-time active flows having priority data to be transmitted for meeting target delay D.sub.i (and hence QoS) requirement, identifies an upper-layer scheduling (ULS) entity, as opposed to lower-layer scheduling LLS entities that, as will be discussed below, are instead aimed at properly allocating PRBs among priority and non-priority active flows.

(26) In order to make the scheduling algorithm 200 compliant with 3GPP specifications, PRB and data transmission are performed at each TTI.sub.k.

(27) At the first TTI.sub.l of the current working period T.sub.WP (after ULS scheduling), a priority active flows LLS (or LLS.sub.P) entity is run. Broadly speaking, at each TTI.sub.k, and until the priority group has emptied, LLS.sub.P entity allocates PRBs among the active flows within the priority group, transmits the priority data q.sub.i(t), and erases the i-th priority flow whose priority data q.sub.i(t) have been completely transmitted from the priority group.

(28) In the proposed scheduling algorithm 200, LLS.sub.P entity is identified by functional blocks 215-240.

(29) In this respect, the scheduling algorithm 200 checks, at the decision block 215, whether the priority group is empty. In the negative case, exit branch N of the decision block 215, at the current TTI.sub.k PRB allocation among the i-th priority active flows is carried out at block 220 (e.g., by exploiting Proportional Fair, Maximum Throughput, or Earliest Due Date scheduling strategies), priority data q.sub.i(t) are transmitted over allocated PRBs (block 225), and the priority group is updated by erasing the i-th active flows whose priority data transmission has been completed within the current TTI.sub.k (see block 230), until current TTI.sub.k ending (see decision block 235).

(30) More specifically, priority data q.sub.i(t) are transmitted (and the priority group updated) while current TTI.sub.k has not ended, as conceptually represented in the figure by loop-connection between exit branch N of the decision block 235 and block 225.

(31) Upon current TTI.sub.k ending (exit branch Y of the decision block 235), the following TTI.sub.k is considered by updating the k value (see block 240), thereafter the operation flow goes back to block 215, where LSS.sub.P entity is run (as before) until the priority group has not emptied.

(32) Before the new LSS.sub.P entity is run, a check aimed at ascertaining whether k≦α—i.e. the (new) current TTI.sub.k is still comprised within the current working T.sub.WP—could be performed (so as to start a new working period T.sub.WP otherwise). However, this is not necessary. Indeed, as will be readily understood shortly, being the scheduling algorithm 200 also conceived for handling non-priority multimedia/real-time active flows whose queued data delay is closing to maximum allowed delay before best-effort active flows, priority data are certainly transmitted before working period T.sub.WP end.

(33) Considering back the decision block 215, when all priority flows have transmitted the respective priority data q.sub.i(t) (exit branch Y), a non-priority active flows LLS (or LLS.sub.NP) entity is run (functional blocks 245-270). As far as LLS.sub.NP entity running is concerned, analogous functional block will not be detailed again.

(34) Broadly speaking, at each TTI.sub.k, and until ending of all available TTI.sub.ks of the current working period T.sub.WP (see decision block 265), PRBs allocation among non-priority active flows is carried out (see block 245), and corresponding (non-priority) data are transmitted over allocated PRBs (block 250) until current TTI.sub.k ending (see loop-connection between decision block 255 and block 245).

(35) PRBs allocation is performed among selected non-priority active flows. In this respect, a metric is calculated for both multimedia/real-time active flows and best-effort active flows, and the active flows having highest metrics are selected for PRBs allocation.

(36) Preferably, the metric for best-effort active flows (M.sub.BEi) is calculated as
M.sub.BEi=r.sub.i/R.sub.i,
where r.sub.i is the instantaneous data rate reachable by the i-th active flow, being known the channel quality measured by UE that acts as source or destination of the active flow, and R.sub.i is the average rate of the i-th active flow.

(37) As mentioned above, in order to provide a different weight to non-priority multimedia/real-time active flows whose queued data delay is close to maximum allowed delay D.sub.i, the metric for each i-th multimedia/real-time active flow (M.sub.Ai) is calculated as:
M.sub.Ai=r.sub.i/R.sub.i*δHOL*(D.sub.i−HOL).sup.γ

(38) where HOL is the Head of Line packet delay of a given queue, and γ is a factor (e.g., equal to, or greater than 1) taking into account the weight of time deadline assigned to the considered data packet.

(39) This guarantees a major priority to multimedia/real-time active flows and fairness among best-effort applications.

(40) Upon current TTI.sub.k ending (exit branch Y of the decision block 255), the following TTI.sub.k is considered by updating the k value (see block 260), and, upon current working period T.sub.WP ending (exit branch Y of the decision block 265), the following working period is considered (block 270) and the scheduling algorithm 200 is run back.

(41) Naturally, in order to satisfy local and specific requirements, a person skilled in the art may apply to the solution described above many logical and/or physical modifications and alterations. More specifically, although the present invention has been described with a certain degree of particularity with reference to preferred embodiments thereof, it should be understood that various omissions, substitutions and changes in the form and details as well as other embodiments are possible. In particular, different embodiments of the invention may even be practiced without the specific details set forth in the preceding description for providing a more thorough understanding thereof; on the contrary, well-known features may have been omitted or simplified in order not to encumber the description with unnecessary details. Moreover, it is expressly intended that specific elements and/or method steps described in connection with any disclosed embodiment of the invention may be incorporated in any other embodiment as a matter of general design choice.

(42) More specifically, the solution according to an embodiment of the invention lends itself to be implemented through an equivalent method (by using similar steps, removing some steps being not essential, or adding further optional steps); moreover, the steps may be performed in different order, concurrently or in an interleaved way (at least partly).

(43) For example, the proposed scheduling algorithm could be extended, at the LLS.sub.P level, for differently handling multimedia/real-time active flows belonging to different service classes (e.g., gold, silver, bronze) according to the amount of priority data to be transmitted.

(44) In this respect, PRBs allocation and priority data transmission can be carried out beginning from priority active flows associated with highest (e.g., gold) service class to priority active flows associated with lowest (e.g., bronze) service class.

(45) Additionally or alternatively, weighted metrics could be used (e.g., in case that LLS.sub.P makes use of opportunistic, such as Proportional Fair scheduling approaches). In this respect, for each (multimedia/real-time) active flow, weight could be applied to the metric calculated by opportunistic scheduling approach. By way of example only, such weight can be set as having decreasing value from gold to bronze service classes (e.g., 1.6, 1.3 and 1, respectively).

(46) In addition, analogous considerations apply if the wireless communication network has a different structure or comprises equivalent components, or it has other operating features. In any case, any component thereof may be separated into several elements, or two or more components may be combined into a single element; in addition, each component may be replicated for supporting the execution of the corresponding operations in parallel. It should also be noted that any interaction between different components generally does not need to be continuous (unless otherwise indicated), and it may be both direct and indirect through one or more intermediaries.

(47) Moreover, although explicit reference has been made to wireless communication network based on the LTE/LTE-Advanced standard, it should be understood that it is not in the intentions of the Applicant to be limited to the implementation of any particular wireless communication system architecture or protocol. In this respect, it is also possible to provide that, with suitable simple modifications, the proposed scheduling algorithm may be applied also to other open or proprietary communication protocols, for example, WiMAX, among them.