Patent Publication Number: US-8996051-B1

Title: Satellite system resource allocation optimization

Description:
TECHNICAL FIELD 
     This invention relates generally to data communications in a satellite communications system, and in particular, to techniques for optimizing allocation of system resources to user terminals. 
     BACKGROUND 
     The assignee of the present invention manufactures and deploys spacecraft for, inter alia, broadband data communications services from geosynchronous orbit. Market demands for such spacecraft have imposed increasingly stringent requirements on spacecraft payloads. For example, broadband service providers desire spacecraft with payloads offering dynamically scalable data rates to a large number of user terminals. 
     A multi-beam antenna (MBA) system generates a set of user spot beams that define a coverage area which may extend, in aggregate, across a large region on the ground. Within any given spot beam, a large and dynamically varying number of user terminals may be simultaneously demanding system resources (bandwidth or other antenna beam resource). Moreover, the demand from any individual user terminal will vary temporally and/or spatially as the user terminal experiences variations in signal to noise ratio (SNR) and/or (for a mobile user terminal) moves about within or between spot beams. 
     Optimization techniques applied to the problem of bandwidth allocation are disclosed, for example by Iiduka, et al., in “Fixed Point Optimization Algorithms for. Network Bandwidth Allocation Problems with Compoundable Constraints,” by Goode, U.S. Pat. No. 6,718,552, and by Kelly, U.S. Pat. Pub. No. 20010043575, the disclosures of which are hereby incorporated by reference in their entirety into the present patent application. 
     The above mentioned techniques attempt to optimize network bandwidth utilization, but do not necessarily optimize the experience of the users (customers). As a result, an improved approach to dynamically assigning bandwidth or other system resources to user terminals is desirable. 
     SUMMARY 
     The present inventors have appreciated that resource allocation to users may be optimized by minimizing the number of “unsatisfied users” at any moment of time. Bandwidth is an important example of a system resource, with respect to which an “unsatisfied” user may be defined as one that is provided a bandwidth less than a desired bandwidth ω des =T des /s, where T des  is the throughput desired by the user, and s is the spectral efficiency of the user&#39;s user terminal. A “satisfied” user, on the other hand, is one that is provided a bandwidth greater than or equal to ω des . When total available bandwidth A is not less than aggregate desired bandwith Ω, the bandwidth demand for each user terminal or element is at least satisfied. When A is less Ω, however, bandwidth is allocated to each user terminal such that an aggregate number of user terminals that are supplied respective bandwidth not less than respective ω des  is maximized. 
     In an embodiment, resources are allocated to each of a plurality of user terminals, the user terminals being configured for data communication with a satellite via a common antenna beam. A bandwidth b i  is dynamically allocated, within the common antenna beam, to each user terminal i such that, when total available bandwidth A of the common antenna beam is not less than the total desired bandwidth Ω=Σ i=1   n  ω i  of the antenna beam, b i  is no less than ω i , where: ω i  is bandwidth demand at user terminal i, approximately equal to T i-des /s i ; T i-des  is proportional to a throughput requirement by user terminal i; and s i  is an estimated spectral efficiency of user terminal i. When A is less than Ω, bandwidth b i  is allocated to each user terminal such that the aggregate number of user terminals supplied respective bandwidth not less than ω i  is maximized. 
     In an embodiment, b i  may be no greater than A/Ω×ω i . 
     In another embodiment, when A is less than Ω, a first portion A 1  of bandwidth A may be assigned to satisfy respective bandwidth demand ω i  of each user terminal of a first subset of the user terminals and a second portion A 2  of bandwidth A may be proportionately assigned to partially satisfy each user terminal of a second subset of the user terminals. Advantageously, no user terminal in the first subset of user terminals has a respective bandwidth demand greater than a respective bandwidth of any user terminal in the second subset of terminals. 
     In an embodiment, a hierarchical ordering of user terminals may be generated on the basis of a respective ω i  such that ω 1 ≦ω 2 ≦ω 3 ≦ . . . ≦ω n , where: for a first subset of user terminals, for which ω j  is not greater than A−Σ i=1   k−1  ω i , each terminal in the first subset is allocated respective bandwidth b i  of not less than ω i ; and for a second subset of user terminals, for which ω k  is greater than A−Σ i=1   k−1  ω i , a remaining bandwidth Â=A−Σ i=1   k−1  ω i  is allocated to one or more of user terminals in the second subset. 
     In a further embodiment, the remaining bandwidth Â may be allocated to each of the one or more user terminals in the second subset such that the allocated respective bandwidth b k  for each user terminal in the second subset of terminals is approximately Â×ω i /Σ i=k   n  ω i . 
     In an embodiment, resources are allocated to each of a plurality of user terminals, the user terminals configured for data communication with a satellite via a common antenna beam. A resource r i  may be dynamically allocated to each user terminal i such that, when the total resource A allocated to the antenna beam is not less than the total desired resource Ω of the antenna beam, r i  is approximately equal to A/Ω×ω i , where ω i , is resource demand at user terminal i, approximately proportional to d i /s i , where d i  is proportional to a throughput requirement per user terminal i and s i  is an estimated spectral efficiency at user terminal i. When A is less than Ω, resource r i  may be allocated to each user terminal such that an aggregate number of user terminals supplied a respective resource not less than ω i , is maximized. 
     In an embodiment, a satellite is configured for data communication via a common antenna beam with a plurality of user terminals. The satellite and the plurality of user terminals are communicatively coupled with a controller, the controller configured to control the allocation of resources to each of a plurality of user terminals, by dynamically allocating, within the common antenna beam, a bandwidth b i  to each user terminal i such that, when total available bandwidth A of the common antenna beam is not less than the total desired bandwidth Ω=Σ i=1   n  ω i  of the antenna beam, b i  is no less than ω i , where: ω i  is bandwidth demand at user terminal i, approximately equal to T i-des /s i ; T i-des  is proportional to a throughput requirement by user terminal i; and s i  is an estimated spectral efficiency of user terminal i. When A is less than Ω, bandwidth b i  may be allocated to each user terminal such that an aggregate number of user terminals supplied respective bandwidth not less than ω i , is maximized. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Features of the invention are more fully disclosed in the following detailed description of the preferred embodiments, reference being had to the accompanying drawings, in which like reference numerals designate like structural element, and in which: 
         FIG. 1A  and  FIG. 1B  show an example of a flow diagram illustrating an optimized technique for allocating a satellite system resource according to an embodiment. 
         FIG. 2  shows an example system for implementing an optimized technique for allocating a satellite system resource according to an embodiment. 
       Throughout the drawings, the same reference numerals and characters, unless otherwise stated, are used to denote like features, elements, components, or portions of the illustrated embodiments. Moreover, while the subject invention will now be described in detail with reference to the drawings, the description is done in connection with the illustrative embodiments. It is intended that changes and modifications can be made to the described embodiments without departing from the true scope and spirit of the subject invention as defined by the appended claims. 
     
    
    
     DETAILED DESCRIPTION 
     Specific exemplary embodiments of the invention will now be described with reference to the accompanying drawings. This invention may, however, be embodied in many different forms, and should not be construed as limited to the embodiments set forth herein. Rather, these embodiments are provided so that this disclosure will be thorough and complete, and will fully convey the scope of the invention to those skilled in the art. 
     The terms “spacecraft”, “satellite” and “vehicle” may be used interchangeably herein, and generally refer to any orbiting satellite or spacecraft system. 
     The present inventor has developed improved system resource assignment techniques for a multi beam antenna system. The techniques optimize resource assignment by minimizing the number of “unsatisfied users” at any moment of time. Bandwidth is an important example of a system resource, with respect to which an “unsatisfied” user may be defined as one that is provided a bandwidth less than ω des =T des /s, where T des  is the throughput desired by the user, and s is the spectral efficiency of the user&#39;s user terminal. A “satisfied” user, on the other hand, is one that is provided a bandwidth greater than or equal to ω des . It will be appreciated that s may vary temporally and/or as a function of user terminal location within the beam, or other factors. 
     A total bandwidth demand in a given beam may be defined as Ω=Σ i=1   n  ω i , where n is the number of elements, for example, the number of user terminals, assigned to the beam, and ω i  is the bandwidth desired at user terminal i, defined as ω i =T i-des /s i  where is the T i-des  is the throughput desired by element i, and s i  is the estimated spectral efficiency of user terminal i. 
     Where the total available bandwidth is represented by A, if A≧Ω (i.e. the bandwidth available is at least sufficient to meet the bandwidth demand), bandwidth may be assigned to each user terminal proportionately to the bandwidth desired per element as follows: b i =A/Ω×ω i , where b i  is the bandwidth assigned to user terminal i. 
     Put shortly, where A≧Ω, the bandwidth demand for each user terminal or element is satisfied, and an excess available bandwidth may be allocated proportionally to demand. 
     Where A&lt;Ω, however, the total bandwidth allotted to the beam is insufficient to meet the desired throughput of every element/user terminal. In such case, advantageously, the bandwidth b i  allocated to each user terminal is determined such that a number of user terminals supplied respective bandwidth not less than ω i , is maximized. 
     In an embodiment, in order to maximize the number of elements that achieve their respective desired throughput, bandwidth is first assigned to the elements that require the least amount of bandwidth to meet their desired throughput requirement, and then the remaining bandwidth is proportionately assigned to the elements whose throughput requirements will not be met. For example, bandwidth may be allocated to elements on a hierarchical basis according to a respective ω i =T i-des /s i . It will be appreciated that parameters T i-des  and s i  may vary dynamically with time, in manner that is not predictable a priori. As a result, the hierarchical allocation of bandwidth may, advantageously, also be dynamically adjusted in real or near real time. 
     In an embodiment, hierarchical allocation of bandwidth may be accomplished in the following manner. Bandwidth may assigned to each element/user terminal on a priority basis such that, where ω 1 ≦ω 2 ≦ω 3 ≦ . . . ≦ω n , demand of terminal  1  is fully satisfied first, before any bandwidth is allocated to terminal  2 ; then the demand of terminal  2  is fully satisfied before any bandwidth is allocated to terminal  3 , and so on. Thus, for a first subset of user terminals, including terminals  1  through j where ω j  is not greater than A−Σ i=1   j−1  ω i , each user terminal may be allocated respective bandwidth b i  no less than ω i =T i-des /s i . Advantageously, b i  may be approximately equal to ω i . For a second subset of user terminals, where ω k  is greater than A−Σ i=1   k−1  ω i , each user terminal may be allocated respective bandwidth b i =Â×ω i /Σ i=k   n  ω i , where Â=A−Σ i=1   k−1  ω i . 
     Put shortly, when A&lt;Ω, the bandwidth demand for each user terminal in the first subset is satisfied, and each user terminal in the second subset is allocated a portion of the remaining bandwidth proportionate to its demand. 
       FIG. 1A  shows an example of a flow diagram illustrating an optimized technique for allocating bandwidth according to an embodiment. In an embodiment, method  100  may be performed by a satellite system controller, a processor or computer apparatus located on the ground, at for example, a control center, or on a satellite. 
     Method  100  may begin at block  101 , where an estimate may be made of (1) initially available bandwidth A and (2) total initially desired bandwidth Ω, where Ω=Σ i=1   n  ω i  and ω i =T i-des /s i . Advantageously, estimates of A and Ωmay be updated dynamically in real, or near real time, based, for example, on continuously or frequently updated values of n, T i-des , and s i . 
     At block  102 , for example, an updated determination may be made of (1) available bandwidth A and (2) total desired bandwidth Ω. 
     At block  103 , a decision may be made as to whether or not A&gt;Ω. If A&gt;Ω, then method  100  may proceed to block  104  and allocate a bandwidth b i  to each user terminal i such that b i  is no less than than ω i . On the other hand, if A&lt;Ω, method  100  may proceed to block  110  and allocate a bandwidth b i  to each user terminal i such that an aggregate number of user terminals supplied respective bandwidth not less than ω i  is maximized. 
     Advantageously, after executing either of block  104  or block  110 , method  100  may return to block  102 , either immediately, or following a set time delay (not shown). 
       FIG. 1B  shows a further example of a flow diagram illustrating an optimized technique for allocating bandwidth. More particularly  FIG. 1B  illustrates in more detail an implementation of block  110 . 
     According to the illustrated implementation, at block  111 , a hierarchical ordering of user terminals may be generated on the basis of respective desired bandwidth ω i , such that ω 1 ≦ω 2 ≦ω 3 ≦ . . . ≦ω n . 
     At block  112 , j may be set, initially, to equal 1. At block  113  a determination may be made whether or not ω j ≦A−Σ i=1   j−1  ω i . 
     If a determination is made at block  113  that ω j ≦A−Σ i=1   j−1  ω i , the method may proceed to block  115  where a bandwidth b j  may be allocated to user terminal j such that b j  is no less than than ω j . At block  116 , j may be incremented, that is j may be set to equal j+1. At block  117 , a determination may be made whether or not j equals n. When the determination is made that j does not equal n, the method may return to block  115 . On the other hand, when the determination is made that j equals n, the method may return to block  102  ( FIG. 1A ). 
     When a determination is made at block  113  that ω j &gt;A−Σ i=1   j−1  ω i , a remaining bandwidth Â×ω i /Σ i=k   n  ω i  may be distributed to one or more user terminals to which bandwidth has not been previously allocated. In an embodiment, each such user terminal k may be allocated a portion of the remaining bandwidth Â such that the allocated respective bandwidth b k  for each user terminal k is approximately Â×ω i /Σ i=k   n  ω i . 
     Referring now to  FIG. 2 , system  200  illustrates satellite  211  configured for data communication via a common antenna beam (not illustrated) with a number of user terminals  216 . The data communication may be carried out over bidirectional user link  217  within the common antenna beam. Satellite  211  and user terminals  216  may be communicatively coupled, directly or indirectly, with controller  220 . In the illustrated embodiment, for example, satellite  211  is communicatively coupled, via feeder link  213 , with gateway ground terminal  212 , which is communicatively coupled with controller  220  via signal line  221 . User terminals  216  may be communicatively coupled directly with controller  220 , as illustrated, via signal line  222 . In addition, or alternatively, user terminals  216  may be communicatively coupled with controller  220  via user link  217 , satellite  211 , feeder link  213 , gateway  212 , and signal lines  221 . 
     Controller  220  may be configured to dynamically allocate a resource to each user terminal using the above-described techniques. More particularly, controller  220  may be configured to make determination of (1) initially available bandwidth A and (2) total initially desired bandwidth Ω, where Ω=Σ i=1   n  ω i  and ω i =T i-des /s i . Advantageously, estimates of A and Ω may be updated dynamically in real, or near real time, based, for example, on continuously or frequently updated values of n, T i-des , and s i . 
     Controller  220  may be configured to periodically update the above determination. The update may be made continuously or at intervals of a few seconds or minutes, for example. Controller  220  may be further configured to determine whether or not A&gt;Ω. If A&gt;Ω, then controller  220  may allocate a bandwidth b i  to each user terminal i such that b i  is no less than than ω i . On the other hand, if A&lt;Ω, controller  220  may allocate a bandwidth b i  to each user terminal i such that an aggregate number of user terminals supplied respective bandwidth not less than ω i , is maximized. 
     Thus, techniques for optimizing allocation of satellite system resources to user terminals has been disclosed. The foregoing merely illustrates principles of the invention. It will thus be appreciated that those skilled in the art will be able to devise numerous systems and methods which, although not explicitly shown or described herein, embody said principles of the invention and are thus within the spirit and scope of the invention as defined by the following claims.