Patent Publication Number: US-8526417-B1

Title: Adaptive initialization for wireless schedulers

Description:
INTRODUCTION 
     Wireless systems are configured with channel-aware or channel-unaware wireless schedulers that provide network services to access terminals. The channel-unaware wireless schedulers are configured to ensure fair access to network services by providing equal access to the network services. The channel-unaware wireless schedulers, which do not monitor channel conditions, fail to maximize communication throughput at the base station because the channel-unaware wireless schedulers may allocate access to an access terminal, when the access terminal is experiencing poor channel conditions and is unable to efficiently communicate with a base station. The channel-aware wireless schedulers overcome the shortcomings of the channel-unaware schedulers by monitoring channel conditions associated with each access terminal connected to the base station. The channel-aware wireless schedulers utilize data about the channel conditions to schedule access terminals, when the channel conditions of the access terminal support efficient transmission of communications between the base station and the access terminal. 
     The channel-aware schedulers maximize base station throughput when compared to the channel-unaware schedulers. However, the channel-aware schedulers are subject to problems due to access terminals communicating in a bursty manner especially upon initialization. These problems cause the channel-aware wireless schedulers to stop scheduling some access terminals in favor of providing access to other access terminals, which may lead to starvation, i.e. limited or no access to network services, of the former access terminals. 
     SUMMARY 
     The present invention is defined by the claims below. Embodiments of the present invention solve at least the above problems by providing a wireless system, a method, and computer-readable media for, among other things, scheduling access terminals in a communication network to reduce starvation while maximizing throughput. The present invention has several practical applications in the technical arts including scheduling access terminals, calculating weighted average functions of the communication rate, adaptive initialization, and preventing starvation over a communication network. 
     In a first aspect, a set of computer-useable instructions provide a method to schedule time slots for communications between access terminals and base stations. In accordance with the computer-useable instructions, the base stations receive initialization requests from the access terminals. The requests include a desired communication rate for the access terminals based on the current channel conditions observed by the access terminals. In turn, the base stations periodically calculate weighted average functions of the communication rate for each access terminal based on a number of time slots that occurred since the initialization of the access terminal. Based on weighted average functions of the communication rate for each access terminal and the channel conditions, the base stations schedule an access terminal for communication. 
     In a second aspect, a wireless system includes base stations and access terminals that communicate over a communication network. The base stations are configured to select an access terminal to communicate over the communication network for each available time slot based on a weighted average and current channel conditions corresponding to each access terminal. Each base station includes an adaptive initialization component that is configured to assign an alpha value to each access terminal. The alpha value is utilized by the base stations to calculate appropriately weighted average functions of the communication rate during initialization periods of each access terminal to prevent the access terminal from receiving an unfair number of time slots and starving other access terminals. 
    
    
     
       BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS 
       Illustrative embodiments of the present invention are described in detail below with reference to the attached drawing figures, which are incorporated by reference herein and wherein: 
         FIG. 1  is an exemplary network diagram that illustrates a wireless system; 
         FIG. 2  is an exemplary component diagram that illustrates a base station included in the wireless system of  FIG. 1 ; 
         FIG. 3  is an exemplary graph that illustrates alpha values assigned to access terminals by an adaptive initialization component of a base station; and 
         FIG. 4  is an exemplary logic diagram that illustrates a method for scheduling access terminals. 
     
    
    
     DETAILED DESCRIPTION 
     Embodiments of the present invention provide wireless systems and methods for scheduling access terminals. The wireless systems are configured with channel-aware schedulers that intelligently select access terminals to communicate over the communication network. The channel-aware schedulers are configured with adaptive initialization components that assign dynamic alpha values to each access terminal. The channel-aware schedulers calculate weighted average functions of the communication for each access terminal based on, among other things, the alpha values generated by the adaptive initialization components. The alpha values enable the channel-aware schedulers to calculate weighted average functions of the communication rates during an initialization period for each access terminal. During the initialization period, the channel-aware schedulers servicing the access terminals are not equipped with large sets of historical values that represent previous communication rates of the access terminals. The alpha values provide the channel-aware schedulers with an appropriate factor for calculating weighted average functions of the communication rate for each access terminal. The use of the alpha value by the channel-aware schedulers enable the base station to avoid initialization-related starvation of the access terminals. Further, the channel-aware scheduler may improve access terminal communication experience and increases throughput and fairness for the wireless system and each access terminal. 
     Computer-readable media include both volatile and nonvolatile media, removable and nonremovable media, and media readable by a database, a switch, and various other network devices. Network switches, routers, and related components are conventional in nature, as are means of communicating with the same. By way of example, and not limitation, computer-readable media comprise computer-storage media and communications media. 
     A wireless system includes base stations, access terminals, and a communication network that connects the base stations and access terminals. In the wireless system, the base stations are configured with wireless schedulers that select time slots to assign to the access terminals. The wireless schedulers may include channel-aware schedulers that select access terminals based on, among other things, channel conditions observed by the access terminals and weighted average functions of the communication rate associated with each access terminal. 
       FIG. 1  is an exemplary network diagram that illustrates a wireless system  100 . The wireless system  100  includes a network  110 , access terminals  120 , and base stations  130 . 
     The network  110  may include wireless and wired networks. The network  110  comprises router  111 , packed data switching node  112 , and the Internet  113 , or any other network locations. The base stations  130  communicate with the access terminals  120  over the wireless network  110 . The base stations  130  connect to the router  111  to route communications received from the access terminals  120  to the Internet  113  and to route communications from the Internet  113  to the access terminals  120 . The router  111  connected to the base station  130  receives communications destined for the Internet  113  or other network locations from the base stations  130  and receives communications destined for the access terminals  120  from the Internet  113 . The router  111  forwards the communications to the packed data switching node  112  that is connected to the router  111 . The packet data switching node  112  receives and formats the communications and sends the formatted communication to the Internet  113  or any other location specified in the communication and vice versa. 
     The access terminals  120  are devices that generate or receive communication requests, i.e., voice, video, or data. The access terminals  120  include, but are not limited to, laptops, personal computers, mobile phones, personal digital assistants, smart phones, and other computing devices. In certain embodiments, the access terminals  120  monitor channel conditions on the network  110  and transmit the channel conditions to the base stations  130 . The access terminals  120  also transmit requests that specify a desired communication rate to the base station  130 . The access terminals  120  periodically send requests for a desired communication rate based on the current channel conditions to the base stations  130 . 
     The base stations  130  receive the communication requests and current channel conditions from the access terminals  120 . The base stations  130  are configured with wireless schedulers that select access terminals  120  to communicate in a time slot based on, among other things, the current channel conditions and weighted average functions of the communication rate associated with each access terminal. The base stations  130  schedule and select the access terminals  120  to communicate in a time slot when a specified function of the channel conditions and the weighted average functions are good in comparison with other access terminals. For example, in certain wireless schedulers: R i [t] is the current rate of ith access terminal  120  during time slot t; A i [t]=(1−α)A i [t−1] may be the weighted average function of the communication rate used for the ith access terminal  120  when the ith access terminal  120  is not scheduled in slot t; and A i [t]=(1−α)A i [t−1]+αR i [t] may be the weighted average function of the communication rate for the ith access terminal  120  when the ith access terminal  120  is scheduled in slot t. In such cases, the wireless scheduler may examine the ratio (R i [t]/A i [t]) for each access terminal  120  to select the access terminal  120  with the largest ratio. These wireless schedulers use the weighted average functions of the communication rate (A i [t]) and an adaptive alpha (α), which is further described in FIG.  2 ., to prevent starvation of other access terminals  120  that are not assigned to the time slot. 
     One of ordinary skill in the art appreciates and understands that the wireless system  100  has been simplified and that alternate arrangements are within the scope and spirit of the above description. 
     To prevent and minimize starvation of access terminals, the wireless schedulers utilized by the base stations are configured with an adaptive initialization component that assigns dynamic alpha values to the access terminals. Moreover, the wireless schedulers configured with the adaptive initialization component may overcome starvation caused by bursty traffic, i.e., packets received from the access terminals, or on-off behavior exhibited by the access terminals. The adaptive initialization component dynamically and adaptively assigns alpha values that are utilized by the wireless schedulers to calculate weighted average functions of the communication rate for each access terminal. Based on, among other things, the weighted average functions of the communication rate, the wireless schedulers schedule and select an access terminal to communicate during subsequent time slots. 
       FIG. 2  is an exemplary component diagram that illustrates a base station  130  included in the wireless system  100  of  FIG. 1 . The base station  130  includes a wireless scheduler  131 , an adaptive initialization component  132 , and storage  133 . 
     The wireless scheduler  131  selects access terminals to communicate during time slots, based on among other things, weighted average functions of the communication rate. The wireless scheduler  131  calculates the weighted functions of the average communication rate for each access terminal by utilizing the alpha values assigned to each access terminal. The wireless scheduler  131  stores the weighted average functions of the communication rate and the alpha values corresponding to the access terminals in the storage  133 . 
     The adaptive initialization component  132  generates and assigns alpha values (α) to each access terminal. The alpha values are generated based on the number of time slots that transpired since the access terminal was initialized at the base station  130 . When an access terminal attempts to access the communication network for the first time, or after a period of inactivity lacking historical information on communication rates, the base station  130  initializes the access terminal by creating a queue for the access terminal to store, among other things, alpha values, current rates, and weighted average functions of the communication rates for each time slot. The adaptive initialization component  132  assigns alpha values in an inverse relationship to the number of time slots that transpired since the access terminal was initialized. Thus, the adaptive initialization component  132  counts the number of time slots since initialization and assigns an alpha value of where 1/t is the number of transpired time slots for the access terminal. After an initialization period, the adaptive initialization component  132  assigns a constant alpha value. In other words, for each access terminal α=1/t during the initialization period and α=C after the initialization period where C is a constant. In certain embodiments, the constant alpha value is 1/T where the initialization period is T time slots, i.e., 1000 time slots. The alpha values allow the wireless scheduler  131  to perform comparisons between the functions, such as, R i [t]/A i [t], based on the weighted average functions of the communication rate associated with each access terminal, including long-term access terminals and short-term access terminals. The long-term access terminals are access terminals that have been connected to base station  130  past the end of the initialization period. The short-term access terminal are access terminals that are not beyond the initialization period of connection to the base station. 
     The storage  133  stores data for each access terminal that is connected to the base station  130 . The storage  133  includes a database, queue, or any other data structure that stores information for each access terminal. The information stored by the storage  133  may include, but is not limited to, current rate, the weighted average functions of the communication rate, and alpha values for each access terminal during each time slot after initialization. 
       FIG. 3  is an exemplary graph that illustrates alpha values assigned to access terminals by an adaptive initialization component of a base station. The graph  300  represents the distribution of alpha values generated by the adaptive initialization component and includes an initialization value  310 , a threshold value  320 , and time slots  330 . The alpha values are initialized with the initialization value  310 . The time period between the initialization value  310  and the threshold value  320  is the initialization period. During the initialization period, the alpha values decrease inversely as the number of time slots  330  increase. After the threshold value  320 , the alpha values are constant. In some embodiments, the alpha values are automatically updated, by the alpha component, when the number of time slots since the initialization value  310 , i.e., 1 is less than the number of time slots associated with threshold value  320 , i.e., 1000. Thus, when the access terminal is recently initialized one time slot earlier, the alpha component assigns the access terminal an alpha value of 1, in a second time slot after initialization, the access terminal is assigned an alpha value of 0.5, and the alpha component continues to update the alpha values with each subsequent time slot until the threshold  320  is passed. After the threshold  320  is passed, the alpha component assigns a constant alpha value of 0.001 to the access terminals. 
     In some embodiments, the wireless system includes a wireless scheduler that schedules access terminals based on, among other things, weighted average functions of the communication rate for each access terminal. When the access terminal is initialized at the base station, the wireless scheduler tracks the number of time slots that passed since the mobile was initialized. For each time slot, the base station stores the current rate for each access terminal, the weighted average functions of the communication rate for each access terminal, and the alpha values assigned to each access terminal, and other access terminal information to generate a history for each access terminal. The weighted average functions of the communication rate for each access terminal is calculated by the wireless schedulers using: an adaptive alpha value during an initialization period, where the access terminal is classified as a short term access terminal; or a constant alpha value, when the number of time slots for the access terminal passes a threshold associated with the initialization period. The adaptive alpha values enable the wireless scheduler to calculate appropriately weighted average functions of the communication rates for the long-term and short-term access terminals. Thus, the wireless scheduler causes the base station to schedule both long-term and short-term access terminals without starving the long-term access terminals in favor of the short-term access terminals or vice versa. 
       FIG. 4  is an exemplary logic diagram that illustrates a method for scheduling access terminals. Base stations communicate with the access terminals to receive initialization requests from the access terminals. In step  410 , the access terminals periodically transmit requests that specify a desired communication rate based on the current channel conditions observed by the access terminal. In step  420 , the base stations calculate weighted average functions of the communication rate for each access terminal based on a number of time slots that occurred since the initialization of the access terminal. In turn, the base stations schedule an access terminal to communicate during a subsequent time slot based on, among other things, the channel conditions and the weighted average functions of the communication rate associated with each access terminal, in step  430 . The scheduled access terminal communicates with the base station during the subsequent time slot. 
     In summary, a base station configured with a channel-aware wireless scheduler calculates weighted average functions of the communication rate for both long-term and short-term access terminals in a manner that provides an average that does not unfairly bias the wireless scheduler in favor of scheduling time slots for short-term access terminals to the detriment of the long-term access terminals. An adaptive initialization component included in the base station is utilized to assign alpha values that provide an appropriate indication of the relative importance of the average calculated for the access terminal during each time slot. 
     Many different arrangements of the various components depicted, as well as components not shown, are possible without departing from the spirit and scope of the present invention. Embodiments of the present invention have been described with the intent to be illustrative rather than restrictive. Alternative embodiments will become apparent to those skilled in the art that do not depart from its scope. A skilled artisan may develop alternative means of implementing the aforementioned improvements without departing from the scope of the present invention. 
     It will be understood that certain features and subcombinations are of utility and may be employed without reference to other features and subcombinations and are contemplated within the scope of the claims. Not all steps listed in the various figures need be carried out in the specific order described.