Method and system for allocating subcarriers to subscriber devices

[0001] This application is related to a co-pending application, Ser. No. 10/983,499, entitled “METHOD AND APPARATUS FOR RESOURCE ALLOCATION AND SCHEDULING,” filed Nov. 08, 2004, which is assigned to the assignee of the present application.

[0002] The present invention relates to the field of multi-carrier systems in wireless networks, and more specifically, to the allocation of subcarriers to subscriber devices of the wireless network.

[0003] In a wireless network, for example, a cellular network, data is transmitted from a Base Station (BS) to a subscriber device or vice versa. A multi-carrier system of the wireless network employs multiple subcarriers in each carrier channel of the network. Examples of multi-carrier systems include, but are not limited to, Orthogonal Frequency Division Multiplexed (OFDM) systems, Orthogonal Frequency Division Multiple Access (OFDMA) systems, and the like.

[0004] Subcarriers are allocated to subscriber devices for data transmission. Several methods are available for allocating subcarriers to subscriber devices. One of the known methods employs OFDMA for subcarrier allocation or selection. The method includes partitioning subcarriers into groups of clusters of subcarriers. When an indication of a selection by the subscriber of one or more groups is received, clusters in the groups are allocated, for use in the communication with the subscriber.

[0005] However, there are several design/engineering problems associated with the allocation of subcarriers to subscriber devices. This is because the data to be transmitted or received has certain Quality of Service (QoS) requirements, such as delay and throughput requirements. For example, voice data may have a small throughput requirement but stringent delay requirements. Further, data such as streaming video, Internet downloads, and file transfers have requirements that can vary at every instance of the transmission. Further, the base station (BS) and the subscriber device may have constraints such as transmit and receive power constraints. Moreover, carrier channel conditions may vary both across sub-carriers and subscriber devices. Therefore, it is difficult to satisfy the QoS requirements, given the carrier channel conditions and constraints.

[0011] Skilled artisans will appreciate that elements in the figures are illustrated for simplicity and clarity and have not necessarily been drawn to scale. For example, the dimensions of some of the elements in the figures may be exaggerated relative to other elements to help to improve understanding of embodiments of the present invention.

[0012] Before describing in detail the method for allocating the plurality of subcarriers to the plurality of subscriber devices in the wireless network, it should be observed that the present invention resides primarily in the method steps and system components, which are employed to achieve the allocation of the plurality of subcarriers to the plurality of subscriber devices.

[0013] Accordingly, the method steps and system components have been represented where appropriate by conventional symbols in the drawings, showing only those specific details that are pertinent to understanding the present invention, so as not to obscure the disclosure with details that will readily be apparent to those of ordinary skill in the art having the benefit of the description herein.

[0014] In this document, relational terms such as first and second, and so forth may be used solely to distinguish one entity or action from another entity or action, without necessarily requiring or implying any actual such relationship or order between such entities or actions. The terms “comprises,” “comprising,” or any other variation thereof, are intended to cover a non-exclusive inclusion, such that a process, method, article, or apparatus that comprises a list of elements does not include only those elements but may include other elements not expressly listed or inherent to such process, method, article, or apparatus. An element preceded by “. . . a” does not, without more constraints, preclude the existence of additional identical elements in the process, method, article, or apparatus that the element.

[0015] The term ‘another’, as used herein, is defined as at least a second or more. The terms ‘including’ and/or ‘having’, as used herein, are defined as comprising.

[0016] The present invention provides a method for allocating a plurality of subcarriers to a plurality of subscriber devices in a wireless network. The method includes identifying a set of characteristics for a transmission on each subcarrier of the plurality of subcarriers, and assigning a dynamic weight to at least one subscriber device of the plurality of subscriber devices. The dynamic weight is assigned at each decision instance of the transmission corresponding to the at least one subscriber device based on at least one of a throughput, delay, packet-loss and queue length requirement of one or more flows of the at least one subscriber device. Further, the method includes determining a set of optimum values for the set of characteristics based on the dynamic weight and a channel feedback. The set of optimum values are determined under a set of constraints for each subcarrier of the plurality of subcarriers. Further, at least one subcarrier of the plurality of subcarriers is allocated to at least one subscriber device based on at least one optimum value of the set of optimum values.

[0017] The present invention also provides a method for optimizing subcarrier allocation for a plurality of subscriber devices in a wireless network. The method includes identifying a set of characteristics for transmissions on a plurality of subcarriers. The method also includes assigning a dynamic weight to one or more subscriber devices of the plurality of subscriber devices at each decision instance of a transmission corresponding to the one or more subscriber devices based on at least one of the throughput, delay, packet-loss and queue length requirements of one or more flows of one or more subscriber devices. The method further includes determining a set of optimum values of the set of characteristics for each subcarrier of the plurality of subcarriers based on the dynamic weight and a channel feedback. The set of optimum values are determined under a set of constraints for each subcarrier of the plurality of subcarriers. The subcarriers of the plurality of subcarriers are grouped into a set of bundles based on the set of optimum values for each subcarrier of the plurality of subcarriers. A bundle of the set of bundles is allocated to the one or more subscriber devices based on the set of optimum values for each subcarrier in the bundle.

[0018] The present invention further provides a system in a base station suitable for allocating a plurality of subcarriers to the plurality of subscriber devices in a wireless network. The system includes an identifier, an assignor, an optimizer and an allocator. The identifier is capable of identifying a set of characteristics for a transmission on each subcarrier of the plurality of subcarriers. The assignor assigns a dynamic weight to at least one subscriber device of the plurality of subscriber devices at each decision instance of the transmission corresponding to the at least one subscriber device based on at least one of the throughput, delay, packet-loss and queue length requirements of one or more flows of the at least one subscriber device. The optimizer is capable of determining a set of optimum values for the set of characteristics based on the dynamic weight and a channel feedback. The set of optimum values are determined under a set of constraints for each subcarrier of the plurality of subcarriers. Based on at least one optimum value of the set of optimum values, the allocator is capable of allocating at least one subcarrier of the plurality of subcarriers to at least one subscriber device.

[0019] Various embodiments of the present invention provide a method and system for allocating a plurality of subcarriers to a plurality of subscriber devices in a wireless network. Embodiments of the present invention described below pertain to wireless networks employing multi-carrier systems such as time division multiplexed and frequency division multiplexed systems. Examples of frequency division multiplexed systems include Orthogonal Frequency Division Multiplexed (OFDM) systems and Orthogonal Frequency Division Multiple Access (OFDMA) systems. However, the present invention is not limited to multi-carrier systems only.

[0020] FIG. 1 shows a wireless network 100 in which various embodiments of the present invention can be practiced. The wireless network 100 includes subscriber devices 102 and 104, and a Base Station (BS) 106. Examples of the subscriber devices 102 include, but are not limited to, a Code Division Multiple Access (CDMA) cellular telephone, a cellular modem, a Personal Digital Assistant (PDA) with a wireless interface, a laptop device with a wireless interface, Consumer Premises Equipment (CPE) with a wireless interface, and other mobile devices. The subscriber devices, for example, the subscriber devices 102 and 104, communicate with the BS 106 through a carrier channel of the wireless network 100.

[0021] FIG. 2 shows a carrier channel 202 between the subscriber devices 102 and 104 and the BS 106, in accordance with an embodiment of the present invention. The carrier channel 202 includes multiple subcarriers, for example, subcarriers 204, 206, 208, and 210. The subscriber devices 102 and 104 communicate with the BS 106 through the carrier channel 202. For the purpose of the communication, the subcarriers of the carrier channel need to be allocated to the subscriber devices of the wireless network.

[0022] FIG. 3 is a flowchart depicting a method for allocating the subcarriers to the subscriber devices in the wireless network 100, in accordance with an embodiment of the present invention. At step 302, a set of characteristics is identified for a transmission on each subcarrier of the carrier channel. In an embodiment of the present invention, the transmission is directed from a subscriber device to the BS 106 or is an uplink transmission. In another embodiment of the present invention, the transmission is directed from the BS 106 to the subscriber device or is a downlink transmission. The set of characteristics are selected from a Modulation and Coding Scheme (MCS), data rate, and/or power of the transmission for each subcarrier of the carrier channel.

[0023] At step 304, a dynamic weight is assigned to the subscriber device, for example, the subscriber device 102 at each decision instance. The decision instance is also referred to as a scheduling instance or a frame of the transmission. The subscriber device has one or more flows to transmit at the decision instance. Different flows can have different Quality of Service (QoS) requirements. Multiple cases can be imagined: one, different dynamic weights for each flow (since QoS requirements are different) and a big joint optimization across users and flows; two, different dynamic weights for each flow (since QoS requirements are different) and a collective dynamic weight per user for optimization. The value of the dynamic weight is based on the QoS requirements of the flows of the subscriber device at each decision instance of the transmission. The QoS requirements may include a throughput, delay, packet-loss and/or queue-length requirement of the flows of the subscriber device.

[0024] At step 306, a set of optimum values for the set of characteristics is determined. The set of optimum values are determined based on the dynamic weight and a channel feedback. The channel feedback refers to a feedback that is provided to a transmitting subscriber device or a transmitting BS regarding a state of the carrier channel. The state of the carrier channel includes transmission conditions such as Signal to Noise-plus-Interference Ratio (SINR), Additive White Gaussian Noise (AWGN) in the carrier channel, a channel gain, and/or an equivalent rate that can be supported at the measured SINR. The channel feedback is used because values in the set of optimum values for the set of characteristics depend on the transmission conditions of the carrier channel.

[0025] Further, the set of optimum values are determined under a set of constraints for each subcarrier of the carrier channel. In an embodiment of the present invention, the set of constraints include uplink or downlink constraints, or a combination thereof. Examples of downlink constraints include, but are not limited to, base station transmit power, data available for each subscriber device, information pertaining to the transmission, such as whether it is a new transmission or a retransmission, the maximum number of subcarriers allowed per subscriber device, and the like. Examples of uplink constraints include, but are not limited to, subscriber device transmit power, the data available for each subscriber device, information pertaining to the transmission, such as whether it is a new transmission or a retransmission, and the maximum number of subcarriers allowed per subscriber device. The set of constraints may further include a set of subscriber device constraints. Examples of the subscriber device constraints include, but are not limited to, receiver capability constraints of the subscriber device in the downlink, and transmitter capability constraints of the subscriber device in the uplink. Examples of receiver capability constraints include a receiver's incapability to decode certain modulation schemes, reorder buffer size, and the like. Examples of transmitter capability constraints include a transmitter's incapability to transmit/encode certain modulation schemes, and other transmitter constraints.

[0026] The set of optimum values are determined by optimizing a rate vector. For the wireless network having, for example, N subscriber devices represented by {S₁, . . . , S_i, . . . , S_N}, the general form of the rate vector V_t at a decision instance t is given by:

[0027] $\begin{array}{cc}{V}_t=\underset{v\in R\left({\eta }_t\right)}{\mathrm{argmax}}\sum _i{w}_i{v}_i& \left(1\right)\end{array}$
where η_t represents the collective (of all users) channel state at time t, R(η_t) is the rate region at time t, v_i is a rate for the subscriber device S_i, and w_i is the dynamic weight assigned to v_i. Note that the data rate here is the total rate of transmission over all the sub-carriers allocated to a user since multiple sub-carriers can be assigned to a user.

[0028] The process of optimization will now be explained, for example, for an OFDMA downlink. For the OFDMA downlink, for which the carrier channel includes, for example, M subcarriers represented by {C₁, . . . , C_i, . . . C_M}, equation (1) takes the form:

[0029] $\begin{array}{cc}\underset{0\le p_{\mathrm{ij}}\le \frac{x_{\mathrm{ij}}{s}_{\mathrm{ij}}}{e_{\mathrm{ij}}},0\le x_{\mathrm{ij}}\le 1}{\max }\sum _{i,j}{w}_i{x}_{\mathrm{ij}}\log \left(1+\frac{p_{\mathrm{ij}}{e}_{\mathrm{ij}}}{x_{\mathrm{ij}}}\right)& \left(2\right)\\ \mathrm{subject}\mathrm{to}\sum _{i,j}{p}_{\mathrm{ij}}\le P,\sum _i{x}_{\mathrm{ij}}\le 1\forall j& \left(3\right)\end{array}$
where p_ij is the power for the subscriber device S_i in the subcarrier C_j, x_ij is the fraction of C_j used by S_i, e_ij is the channel state or condition for S_i in C_j. For example, e_ij can be the normalized SINR for S_i in C_j. Also, s_ij is the maximum SINR for S_i in C_j

[0030] In one embodiment of the present invention, equation (2) is solved using the method of Lagrange multipliers. Using the method of Lagrange multipliers, equation (2) reduces to:

[0031] $\begin{array}{cc}\underset{\lambda \ge 0,\mu \ge 0}{\min }\underset{0\le p\le \frac{\mathrm{xs}}{e},0\le x\le 1}{\max }L\left(p,x,\lambda ,\mu \right)& \left(4\right)\end{array}$
where L(p,x,λ,μ) is the Lagrangian given by:

[0032] $\begin{array}{cc}L\left(p,x,\lambda ,\mu \right)=\sum _{i,j}{w}_i{x}_{\mathrm{ij}}\log \left(1+\frac{p_{\mathrm{ij}}{e}_{\mathrm{ij}}}{x_{\mathrm{ij}}}\right)+\lambda \left(P-\sum _{i,j}{p}_{i,j}\right)+\sum _j{\mu }_j\left(1-\sum _i{x}_{i,j}\right)& \left(5\right)\end{array}$
where λ and μ are the Lagrange multipliers. Here p denotes the matrix of p_ij for all i and j, and x, s and e are similarly defined. λ is a first Lagrange multiplier, and μ is redefined as a subscriber metric. The subscriber metric μ is given as:
μ_ij=w_ih(λ,w_i,e_ij,s_ij)  (6)
where h( ) is a computable function, s_ij is the maximum SINR for S_i in C_j, and e_ij can be obtained from the channel feedback. One example of h( ) is

[0033] $h\left(\lambda ,w,e,s\right)=\{\begin{array}{cc}0& \lambda \ge \mathrm{we}\\ \frac{\lambda }{\mathrm{we}}-1-\log \left(\frac{\lambda }{\mathrm{we}}\right)& \frac{\mathrm{we}}{1+s}\le \lambda <\mathrm{we}\\ \log \left(1+s\right)-\frac{\lambda }{\mathrm{we}}s& \lambda <\frac{\mathrm{we}}{1+s}\end{array}$
It can be observed from equation (6) that μ depends on the function h( ), which is a function of the dynamic weight, subscriber usage, and Signal to Interference-plus-Noise Ratio (SINR) (more generally, channel condition) of the transmission. In general, the subscriber metric is a function of at least one of the dynamic weight, subscriber usage, and/or SINR of the transmission. In equation (6), w_i, e_ij, and s_ij are known. The value of h( ) can be easily computed by determining λ. In another embodiment of the present invention, an approximate value of h( ) is used.

[0034] Therefore, the function in equation (4) is optimized by determining a minimizing λ, or that value of λ for which the function has a minimum value. In one embodiment of the present invention, this can be achieved by using standard iterative algorithms. For example, three points in the range of λ are determined so that a middle point of the three has a lower value than the other two. The other two values are referred to as extreme points. In this way, two different intervals are obtained on either side of the middle point. The process is then repeated around the middle point in either of the intervals to converge to an optimal value of λ. The value of μ is then determined by using the value of λ. The process may also be stopped/halted after a predetermined number of iterations. In this case, an approximate or an estimate of λ is obtained.

[0035] In an alternate embodiment of the present invention, an arbitrary value of λ is used to estimate the value of μ. For example, the value of λ can be selected arbitrarily based on the dynamic weight and the channel feedback of the carrier channel.

[0036] Once the value of λ and μ are obtained, these values can be used to compute the optimum values of the characteristics in the set of characteristics.

[0037] At step 308, the subcarriers are allocated to the subscriber devices based on at least one optimum value of the set of optimum values. In one embodiment of the present invention, that subcarrier is allocated to the subscriber device for which the value of the corresponding subscriber metric is maximum. For example, the subcarrier C_j is allocated to the subscriber device S_i when the value of μ_ij is maximal or highest amongst the subscriber metric values for the subcarriers {C₁, . . . , C_i, . . . C_M} and the subscriber device S_i. For the purpose of the allocation, the subcarriers of the carrier channel 202 are grouped into a set of bundles based on the set of optimum values for each subcarrier. A bundle is then allocated to one or more subscriber devices, for example, the subscriber device 102, based on the set of optimum values for each subcarrier in the bundle. The subcarriers can be grouped into bundles by using different methods. For example, frequency hopping methods such as in Flash-OFDM can be used to group the subcarriers. Also, contiguous allocation methods such as band Advanced Modulation and Coding (band-AMC) sub-channelization in IEEE 802.16d/e can be used. Further, interleaving methods such as Fully Used Sub-Channelization (FUSC) and Partially Used Sub-Channelization (PUSC) in IEEE 802.16d/e can be used. In addition, other subchannelizations from IEEE 802.16d/e like O-PUSC (Optional-PUSC), TUSC (Tile used Sub-channelization), or O-TUSC (Optional-TUSC) may also be used.

[0038] Once the subcarriers are allocated to the subscriber devices, an optimal power is allocated to the subcarriers. For example, the power p_ij is determined and allocated to the subcarrier C_j for the transmission of S_i.

[0039] For the OFDMA uplink, for which the carrier channel includes, for example, M subcarriers represented by {C₁, . . . , C_i, . . . C_M}, equation (1) takes the form:

[0040] $\begin{array}{cc}\begin{array}{c}\underset{0\le p_{\mathrm{ij}}\le \frac{x_{\mathrm{ij}}{s}_{\mathrm{ij}}}{e_{\mathrm{ij}}},0\le x_{\mathrm{ij}}\le 1}{\max }\sum _{i,j}{w}_i{x}_{\mathrm{ij}}\log \left(1+\frac{p_{\mathrm{ij}}{e}_{\mathrm{ij}}}{x_{\mathrm{ij}}}\right)\\ \mathrm{subject}\mathrm{to}\sum _j{p}_{\mathrm{ij}}\le P_i\forall i,\sum _i{x}_{\mathrm{ij}}\le 1\forall j\end{array}& \left(7\right)\end{array}$
where p_ij is the power for the subscriber device S_i in the subcarrier C_j, P_i is the maximum power that subscriber device S_i can use, x_ij is the fraction of C_j used by S_i, e_ij is the channel state or condition for S_i in C_j. For example, e_ij can be the normalized SINR for S_i in C_j. Also, s_ij is the maximum SINR for S_i in C_j

[0041] In one embodiment of the present invention, equation (7) is solved using the method of Lagrange multipliers. Using the method of Lagrange multipliers, equation (2) reduces to:

[0042] $\underset{\lambda \ge 0,\mu \ge 0}{\min }\underset{0\le p\le \frac{\mathrm{xs}}{e},0\le x\le 1}{\max }L1\left(p,x,\lambda ,\mu \right)$
where L1(p,x,λ,μ) is the Lagrangian given by:

[0043] $L1\left(p,x,\lambda ,\mu \right)=\sum _{i,j}{w}_i{x}_{\mathrm{ij}}\log \left(1+\frac{p_{\mathrm{ij}}{e}_{\mathrm{ij}}}{x_{\mathrm{ij}}}\right)+\sum _i{\lambda }_i\left(P_i-\sum _j{p}_{i,j}\right)+\sum _j{\mu }_j\left(1-\sum _i{x}_{i,j}\right)$
where λ and μ are the Lagrange multipliers. λ is a first Lagrange multiplier that is concerned with the power constraint at the transmitter of the subscriber unit, and μ is redefined as a subscriber metric. The subscriber metric μ is given as:
μ_ij=w_ih(λ_i,w_i,e_ij,s_ij)

[0044] where h( ) is a computable function, and s_ij is the maximum SINR for S_i in C_j. e_ij can be obtained from measurements made the base-station. For TDD systems, the feedback from the subscriber can also be used, owing to reciprocity of the channels.

[0045] FIG. 4 shows a block diagram illustrating a system in the BS 106 suitable for allocating the subcarriers to the subscriber devices in the wireless network, in accordance with an embodiment of the present invention. The system includes an identifier 402, an assignor 404, an optimizer 406, and an allocator 408. The identifier 402 identifies the set of characteristics for the transmission on each subcarrier of the subcarriers of the carrier channel. The assignor 404 assigns the dynamic weight to the subscriber devices, for example, subscriber devices 102 and 104 at each decision instance of the transmission corresponding to the subscriber devices. The assignment of the dynamic weight is based on at least one of the throughput, delay, packet-loss, or queue length requirements of the flows of the subscriber devices. The optimizer 406 is capable of determining the set of optimum values for the set of characteristics based on the dynamic weight and the channel feedback. The set of optimum values are determined under the set of constraints for each subcarrier of the carrier channel. Based on the optimum values of the set of optimum values, the allocator 408 groups the subcarriers into the bundles to allocate the subcarriers to the subscriber devices.

[0046] Embodiments of the present invention have the advantage that they easily accommodate different bundling or grouping methods such as frequency hopping and interleaving, along with channel quality feedback and additional constraints. The dynamic weights based on the QoS requirements allow for an equitable distribution of the subcarriers in the carrier channel, and therefore, an equitable throughput distribution among the subscriber devices. Hence, embodiments of the present invention satisfy the QoS requirements in spite of the carrier channel conditions and constraints.

[0047] It will be appreciated that the modules described herein may be comprised of one or more conventional processors and unique stored program instructions that control the one or more processors to implement, in conjunction with certain non-processor circuits, some, most, or all of the functions of the modules described herein. The non-processor circuits may include, but are not limited to, a radio receiver, a radio transmitter, signal drivers, clock circuits, power source circuits, and user input devices. As such, these functions may be interpreted as steps of a method to perform {allocating a plurality of subcarriers to a plurality of subscriber devices}. Alternatively, some or all functions could be implemented by a state machine that has no stored program instructions, or in one or more application specific integrated circuits (ASICs), in which each function or some combinations of certain of the functions are implemented as custom logic. Of course, a combination of the two approaches could be used. Thus, methods and means for these functions have been described herein.

[0048] It is expected that one of ordinary skill, notwithstanding possibly significant effort and many design choices motivated by, for example, available time, current technology, and economic considerations, when guided by the concepts and principles disclosed herein will be readily capable of generating such software instructions and programs and ICs with minimal experimentation.

[0049] In the foregoing specification, the invention and its benefits and advantages have been described with reference to specific embodiments. However, one of ordinary skill in the art appreciates that various modifications and changes can be made without departing from the scope of the present invention as set forth in the claims below. Accordingly, the specification and figures are to be regarded in an illustrative rather than a restrictive sense, and all such modifications are intended to be included within the scope of present invention. The benefits, advantages, solutions to problems, and any element(s) that may cause any benefit, advantage, or solution to occur or become more pronounced are not to be construed as a critical, required, or essential features or elements of any or all the claims. The invention is defined solely by the appended claims including any amendments made during the pendency of this application and all equivalents of those claims as issued.