Dynamic subchannel and bit allocation in a multiuser-mimo/OFDMA system

BACKGROUND OF THE INVENTION

1. Field of the Invention

0001The present invention relates generally to a mobile communication system, and more particularly to a scheme for optimizing subchannel and bit allocation in a multicarrier-based mobile communication system.

2. Description of the Related Art

0002A multiple-input multiple-output (MIMO) system in the downlink can be broken down to multiple parallel independent single-user MIMO systems. Further, when the orthogonal frequency division multiple access (OFDMA) technology is applied to the downlink MIMO system, a multiuser-MIMO/OFDMA system is provided. In this system, data streams for users are multiplexed over space and frequency, and thus the users receive the spatially multiplexed data streams.

0003<figref idref="f0001">FIG. 1</figref> is a conceptual diagram illustrating subchannels of a multiuser-multiple-input multiple-output/orthogonal frequency division multiple access (MIMO/OFDMA) system. In the multiuser-MIMO/OFDMA system as illustrated in <figref idref="f0001">FIG. 1</figref>, there are space division multiple access (SDMA) subchannels in which each user occupies several MIMO subchannels, for each orthogonal frequency division multiplexing (OFDM) subcarrier. The users generate MIMO subchannels using the MIMO technologies, and transmit data through the generated MIMO subchannels. A more important feature of a multiuser-MIMO/OFDMA system design is that SDMA channels are allocated to users, and bits are loaded to the MIMO subchannels allocated to a single user for adaptive modulation.

0004Document <patcit id="pcit0001" dnum="US2003128658A1"><text>US 2003/128658 A1 (WALTON JAY ROD</text></patcit> [<patcit id="pcit0002" dnum="US20030710A1"><text>US] ET AL) 10 July 2003 (2003-07-10</text></patcit>) discloses techniques to allocate resources (transmission channels and transmit power) to multiple terminals in a multiple-access MIMO-OFDM and techniques for scheduling terminals for data transmission on the downlink and/or uplink in a MIMO-OFDM system based on the spatial and/or frequency "signatures" of the terminals.

0005For subchannel and bit allocation, optimal and suboptimal schemes have been proposed to minimize the overall transmission power under the data rate constraint or to maximize a data rate under the transmission power constraint. For a multiuser-multiple-input single-output (MISO)/OFDM system, a bit allocation scheme for maximizing a signal-to-noise ratio (SNR) has been proposed. More specifically, a suboptimal scheme that takes into account interference and a data rate in a multiuser-MISO/OFDMA system has been proposed. However, when the data rate constraint is present, there is a drawback that the suboptimal scheme can be applied only to an OFDMA system.

SUMMARY OF THE INVENTION

0006Accordingly, the present invention has been designed to solve the above and other problems occurring in the prior art. Therefore, it is an aspect of the present invention to provide a subchannel and bit allocation method for efficiently allocating subchannels in an orthogonal frequency division multiple access (OFDMA) system using multiple antennas.

0007It is another aspect of the present invention to provide a subchannel and bit allocation method for improving a power gain, and frequency use efficiency by performing adaptive modulation according to channel state.

0008The above and other aspects of the present invention can be achieved by a resource allocation method in a multiuser-multiple-input multiple-output/orthogonal frequency division multiple access (MIMO/OFDMA) system including a base station for transmitting signals through a plurality of transmitter antennas, and a plurality of terminals for receiving the signals through receiver antennas. The resource allocation method includes determining a number of subchannels for each user according to a channel environment; and allocating a modulating scheme for each subchannel according to the determined number of subchannels.

BRIEF DESCRIPTION OF THE DRAWINGS

0009The above and other aspects and advantages of the present invention will be more clearly understood from the following detailed description taken in conjunction with the accompanying drawings, in which: <ul id="ul0001" list-style="none" compact="compact"><li><figref idref="f0001">FIG. 1</figref> is a conceptual diagram illustrating subchannels of a multiuser-multiple-input multiple-output/orthogonal frequency division multiple access (MIMO/OFDMA) system;</li><li><figref idref="f0002">FIG. 2</figref> is a block diagram illustrating a multiuser-MIMO/OFDMA base station to which a subchannel and bit allocation method in accordance with the present invention is applied; and</li><li><figref idref="f0003">FIG. 3</figref> is a flow chart illustrating the subchannel and bit allocation method in accordance with the present invention.</li></ul>

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

0010A subchannel and bit allocation method in accordance with preferred embodiments of the present invention will be described in detail herein below with reference to the accompanying drawings. More specifically, the present invention provides an optimal scheme for subchannel and bit allocation, and a suboptimal scheme for separately performing the subchannel and bit allocation.

0011<figref idref="f0002">FIG. 2</figref> is a block diagram illustrating a multiuser-multiple-input multiple-output/orthogonal frequency division multiple access (MIMO/OFDMA) base station to which a subchannel and bit allocation method in accordance with the present invention is applied. Referring to <figref idref="f0002">FIG. 2</figref>, the multiuser-MIMO/OFDMA base station includes a modulation unit 21, a precoding unit 23, and an OFDMA transmission unit 27. The modulation unit 21 includes a plurality of adaptive modulators 21a for processing input data of multiple users. The precoding unit 23 includes a plurality of precoders 23a for precoding signals output from the adaptive modulators 21a, and a plurality of adders 25 for adding outputs of the precoders 23a. The OFDMA transmission unit 27 includes a plurality of Inverse Fast Fourier Transform (IFFT) and parallel-to-serial (P/S) modules 27a, and a plurality of cyclic prefix (CP) insertion modules 27b for inserting CPs into output signals of the IFFT and P/S modules 27a.

0012The multiuser-MIMO/OFDMA base station further includes a subchannel and bit allocation module 29 for generating information necessary for subchannel and bit allocation using feedback information received from terminals, and providing the generated information to the modulation unit 21 and the precoding unit 23.

0013The above-described base station transmits signals of <i>N</i> subcarriers through <i>N_t</i> transmitter antennas 28. It is assumed that the channel is flat fading in the present invention. The base station receives downlink channel information from all <i>K</i> user terminals, allocates a set of subchannels to each user terminal, and determines the number of bits to be transmitted through each channel.

0014The subchannel and bit allocation information is transmitted to user terminals through a separate control channel. When each user terminal has <i>N_R</i> receiver antennas and <i>N_T</i> = <i>M</i>·<i>N_R</i>, where <i>M</i> is an integer greater than or equal to 2, <i>M</i> different user terminals occupy <i>M</i> SDMA subchannels per subcarrier, and each user terminal receives <i>N_R</i> spatially multiplexed bit streams through MIMO processing. The bit streams are referred to as MIMO subchannels. Ω<i>_n</i> denotes an indicator set for <i>M</i> user terminals occupying <i>M</i> SDMA subchannels of the <i>n</i> -th subcarrier. Ω<i>_n</i> consists of <i>M</i> integers chosen from {1,2,···,<i>K</i>}. When an <i>N_R</i>×1 vector is defined by <i>X_n,k</i>, <maths id="math0001" num=""><math display="inline"><msub><mi>X</mi><mrow><mi>n</mi><mo>,</mo><mi>k</mi></mrow></msub><mo>=</mo><mfenced open="{" close="}"><mtable columnalign="left"><mtr><mtd><mi>information symbol vector</mi><mo>,</mo><mi>if</mi><mspace width="1em" /><mi>k</mi><mo>∈</mo><msub><mi mathvariant="normal">Ω</mi><mi>n</mi></msub></mtd></mtr><mtr><mtd><mn>0</mn><mo>,</mo><mi>otherwise</mi><mo>,</mo></mtd></mtr></mtable></mfenced><mn>.</mn></math><img file="EP1598975B1_D0001.tif" /></maths>

0015When <i>X</i>_{<i>n</i>,<i>k</i>} is multiplied by an <i>N_T</i>×<i>N_R</i> processing matrix, <i>S_n,k</i> = <i>F_n,k X_n,k</i> is yielded and ∑ _{<i>k</i>∈Ωn}<i>S_n,k</i> is transmitted through the <i>n</i> -th subcarrier. However, when <i>X_n,k</i> = 0, such multiplication is unnecessary.

0016When the matrix <i>F_n,k</i> is properly chosen, the multiuser interference in ∑_{<i>k</i>∈Ω<i>n</i>}, <i>S_n,k</i> can be eliminated, and <i>S</i>_{<i>n</i>,<i>k</i>} and <i>k</i> ∈ Ω<i>_n</i> can be recovered at a receiver. The matrix <i>F_n,k</i> provides <i>M</i> SDMA subchannels associated with single-user MIMO subchannels, such that each user terminal can spatially multiplex <i>N_R</i> data streams.

0017A transmitter transmits data to <i>K</i> user terminals through all <i>M · N · N_R</i> subchannels under the following conditions:

0018Condition 1: <i>M</i> SDMA subchannels per subcarrier should be allocated to <i>M</i> different user terminals.

0019Condition 2: All <i>N_R</i> MIMO subchannels associated with one SDMA subchannel should be allocated to a single user terminal occupying the SDMA subchannel.

0020When <i>M</i> = 1, the multiuser-MIMO/OFDMA system is switched to a single-user-MIMO/OFDMA system in which each subcarrier with <i>N_R</i> MIMO subchannels is occupied by a single user terminal. In this case, <i>N_T</i> = <i>N_R</i> , <i>F_n,k</i> = <i>E</i>_{<i>n</i>,<i>k</i>} , and Condition 1 is unnecessary.

0021Another form of the multiuser-MIMO/OFDMA system is a multiuser-multiple-input single-output (MISO)/OFDMA system having a single receiver antenna, where <i>N_R</i> = 1. In this case, <i>M</i> = <i>N_T</i>, <i>F_n,k</i> = <i><o ostyle="single">N</o>_n,k</i>, and Condition 2 is unnecessary.

0022An optimal subchannel and bit allocation scheme based on integer programming (IP) in accordance with the present invention will be described herein below. For convenience, it is assumed that the number of SDMA subchannels for each OFDM subcarrier is 2, i.e., <i>M</i> = 2.

0023A data rate <i>R_k</i> of the <i>k</i> -th user terminal can be expressed as shown in Equation (1). <maths id="math0002" num="(1)"><math display="block"><mtable columnalign="left"><mtr><mtd><msub><mi>R</mi><mi>k</mi></msub></mtd><mtd><mo>=</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>l</mi><mo>=</mo><mn>1</mn></mrow><msub><mi>N</mi><mi>R</mi></msub></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>p</mi><mo>=</mo><mn>1</mn><mo>,</mo><mi>p</mi><mo>≠</mo><mi>k</mi></mrow><mi>K</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>c</mi><mo>=</mo><mn>1</mn></mrow><mi>C</mi></munderover></mstyle><mi>c</mi><mo>⋅</mo><msub><mi>ρ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi><mi>p</mi><mi>c</mi></mfenced></mtd></mtr><mtr><mtd><mspace width="1em" /></mtd><mtd><mo>≜</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>l</mi><mo>=</mo><mn>1</mn></mrow><msub><mi>N</mi><mi>R</mi></msub></munderover></mstyle><msub><mi>c</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi></mfenced></mtd></mtr></mtable><mo>,</mo></math><img file="EP1598975B1_D0002.tif" /></maths> where <maths id="math0003" num=""><math display="inline"><msub><mi>c</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi></mfenced><mo>=</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>p</mi><mo>=</mo><mn>1</mn><mo>,</mo><mi>p</mi><mo>≠</mo><mi>k</mi></mrow><mi>K</mi></munderover></mstyle><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>c</mi><mo>=</mo><mn>1</mn></mrow><mi>C</mi></munderover></mstyle><mi>c</mi><mo>⋅</mo><msub><mi>ρ</mi><mfenced><mi>n</mi><mi>l</mi><mi>p</mi><mi>c</mi></mfenced></msub><mo>,</mo></math><img file="EP1598975B1_D0003.tif" /></maths> and <i>C</i> is the maximum number of bits per symbol that can be loaded to one subchannel.

0024If the <i>k</i> -th and <i>p</i> -th user terminals occupy two SDMA subchannels of the <i>n</i> -th subcarrier, and <i>c</i> bits are allocated to the <i>l</i>-th MIMO subchannel associated with an SDMA subchannel of the <i>k</i> -th user terminal, ρ<i>_k</i>(<i>n</i>,<i>l</i>,<i>p</i>,<i>c</i>) = 1. Otherwise, ρ<i>_k</i>(<i>n</i>,<i>l</i>,<i>p</i>,<i>c</i>) = 0.

0025In Equation (1), <i>c_k</i>(<i>n</i>,<i>l</i>) denotes the number of bits allocated to the <i>l</i>-th MIMO subchannel of the <i>k</i> -th user terminal when the <i>k</i> -th user terminal occupies one of the SDMA subchannels of the <i>n</i> -th subcarrier. The transmission power allocated to the <i>k</i> -th user terminal can be expressed as shown in Equation (2). <maths id="math0004" num="(2)"><math display="block"><msub><mi>P</mi><mi>k</mi></msub><mo>=</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>l</mi><mo>=</mo><mn>1</mn></mrow><msub><mi>N</mi><mi>R</mi></msub></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>p</mi><mo>=</mo><mn>1</mn><mo>,</mo><mi>p</mi><mo>≠</mo><mi>k</mi></mrow><mi>K</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>c</mi><mo>=</mo><mn>1</mn></mrow><mi>C</mi></munderover></mstyle><mfrac><mrow><msub><mi>f</mi><mi>k</mi></msub><mfenced><mi>c</mi></mfenced></mrow><mrow><msubsup><mi>α</mi><mi>k</mi><mn>2</mn></msubsup><mfenced><mi>n</mi><mi>l</mi><mi>p</mi></mfenced></mrow></mfrac><mo>⋅</mo><msub><mi>ρ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi><mi>p</mi><mi>c</mi></mfenced></math><img file="EP1598975B1_D0004.tif" /></maths>

0026In Equation (2), <i>f_k</i>(<i>c</i>) is the received power required to stably receive <i>c</i> bits per symbol. α<i>_k</i>(<i>n</i>,<i>l</i>,<i>p</i>) is an equivalent channel gain of the <i>l</i> -th MIMO subchannel of the <i>k</i> -th user terminal when the <i>k</i> -th and <i>p</i> -th user terminals occupy two SDMA subchannels of the <i>n</i> -th subcarrier.

0027It is assumed that the MIMO subchannels are ordered according to their equivalent channel gains without loss of generality, i.e., |α<i>_k</i>(<i>n</i>,1,<i>p</i>)|≥|α<i>_k</i>(<i>n</i>,2,<i>p</i>)|,∀<i>k</i>,<i>n</i>,<i>p</i>.

0028The optimal subchannel and bit allocation problem for minimizing the total transmission power required to transmit data at a rate of {<i>R</i>₁,...,<i>R_K</i>} can be formulated as shown in Equation (3). <maths id="math0005" num="(3)"><math display="block"><mtable columnalign="left"><mtr><mtd><msub><mi>P</mi><mi>T</mi></msub><mo>=</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>K</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>l</mi><mo>=</mo><mn>1</mn></mrow><msub><mi>N</mi><mi>R</mi></msub></munderover></mstyle><mspace width="2em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>p</mi><mo>=</mo><mn>1</mn><mo>,</mo><mi>p</mi><mo>≠</mo><mi>k</mi></mrow><mi>K</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>c</mi><mo>=</mo><mn>1</mn></mrow><mi>C</mi></munderover></mstyle><mfrac><mrow><msub><mi>f</mi><mi>k</mi></msub><mfenced><mi>c</mi></mfenced></mrow><mrow><msubsup><mi>α</mi><mi>k</mi><mn>2</mn></msubsup><mfenced><mi>n</mi><mi>l</mi><mi>p</mi></mfenced></mrow></mfrac><mo>⋅</mo><msub><mi>ρ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi><mi>p</mi><mi>c</mi></mfenced></mtd></mtr><mtr><mtd><mi>Constraints</mi><mo>:</mo></mtd></mtr><mtr><mtd><msub><mi>ρ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi><mi>p</mi><mi>c</mi></mfenced><mo>∈</mo><mfenced open="{" close="}"><mn>0</mn><mn>1</mn></mfenced></mtd></mtr><mtr><mtd><msub><mi>R</mi><mi>k</mi></msub><mo>=</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover></mstyle><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>l</mi><mo>=</mo><mn>1</mn></mrow><msub><mi>N</mi><mi>R</mi></msub></munderover></mstyle><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>p</mi><mo>=</mo><mn>1</mn><mo>,</mo><mi>p</mi><mo>≠</mo><mi>k</mi></mrow><mi>K</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>c</mi><mo>=</mo><mn>1</mn></mrow><mi>C</mi></munderover></mstyle><mi>c</mi><mo>⋅</mo><msub><mi>ρ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi><mi>p</mi><mi>c</mi></mfenced><mo>,</mo><mo>∀</mo><mi>k</mi></mtd></mtr><mtr><mtd><mn>0</mn><mo>≤</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>c</mi><mo>=</mo><mn>1</mn></mrow><mi>C</mi></munderover></mstyle><msub><mi>ρ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi><mi>p</mi><mi>c</mi></mfenced><mo>≤</mo><mn>1</mn><mo>,</mo><mo>∀</mo><mi>k</mi><mo>,</mo><mi>n</mi><mo>,</mo><mi>l</mi><mo>,</mo><mi>p</mi></mtd></mtr><mtr><mtd><mn>0</mn><mo>≤</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>K</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>p</mi><mo>=</mo><mn>1</mn><mo>,</mo><mi>p</mi><mo>≠</mo><mi>k</mi></mrow><mi>K</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>c</mi><mo>=</mo><mn>1</mn></mrow><mi>C</mi></munderover></mstyle><msub><mi>ρ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi><mi>p</mi><mi>c</mi></mfenced><mo>≤</mo><mn>2</mn><mo>,</mo><mo>∀</mo><mi>n</mi><mo>,</mo><mi>l</mi></mtd></mtr><mtr><mtd><mn>0</mn><mo>≤</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>l</mi><mo>=</mo><mn>1</mn></mrow><msub><mi>N</mi><mi>R</mi></msub></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>c</mi><mo>=</mo><mn>1</mn></mrow><mi>C</mi></munderover></mstyle><msub><mi>ρ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi><mi>p</mi><mi>c</mi></mfenced><mo>≤</mo><msub><mi>N</mi><mi>R</mi></msub><mo>⁢</mo><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi></mfenced><mo>,</mo><mo>∀</mo><mi>k</mi><mo>,</mo><mi>n</mi><mo>,</mo><mi>p</mi></mtd></mtr><mtr><mtd><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>K</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>p</mi><mo>=</mo><mn>1</mn><mo>,</mo><mi>p</mi><mo>≠</mo><mi>k</mi></mrow><mi>K</mi></munderover></mstyle><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi></mfenced><mo>=</mo><mn>2</mn><mo>,</mo><mo>∀</mo><mi>n</mi></mtd></mtr><mtr><mtd><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi></mfenced><mo>=</mo><msub><mi>δ</mi><mi>p</mi></msub><mfenced><mi>n</mi><mi>k</mi></mfenced><mo>,</mo><mo>∀</mo><mi>k</mi><mo>,</mo><mi>n</mi><mo>,</mo><mi>p</mi></mtd></mtr><mtr><mtd><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi></mfenced><mo>∈</mo><mfenced open="{" close="}"><mn>0</mn><mn>1</mn></mfenced><mo>,</mo><mo>∀</mo><mi>k</mi><mo>,</mo><mi>n</mi><mo>,</mo><mi>p</mi></mtd></mtr></mtable></math><img file="EP1598975B1_D0005.tif" /></maths>

0029In Equation (3), <i>P_T</i> denotes an intensity of the total transmission power. If the <i>k</i> -th and <i>p</i> -th user terminals occupy two SDMA subchannels associated with the <i>n</i> -th subcarrier, δ<i>_k</i>(<i>n,p</i>) = 1. Otherwise, δ<i>_k</i>(<i>n,p</i>) = 0.

0030In Equation (3), an inequality <maths id="math0006" num=""><math display="inline"><mn>0</mn><mo>≤</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>c</mi><mo>=</mo><mn>1</mn></mrow><mi>C</mi></munderover></mstyle><msub><mi>ρ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi><mi>p</mi><mi>c</mi></mfenced><mo>≤</mo><mn>1</mn><mo>,</mo><mo>∀</mo><mi>k</mi><mo>,</mo><mi>n</mi><mo>,</mo><mi>l</mi><mo>,</mo><mi>p</mi></math><img file="EP1598975B1_D0006.tif" /></maths> is needed because <i>c</i> bits (<i>c</i> ∈ {0,···, <i>C</i>}) are allocated to each MIMO channel. <maths id="math0007" num=""><math display="inline"><mn>0</mn><mo>≤</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>K</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>p</mi><mo>=</mo><mn>1</mn><mo>,</mo><mi>p</mi><mo>≠</mo><mi>k</mi></mrow><mi>K</mi></munderover></mstyle><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>c</mi><mo>=</mo><mn>1</mn></mrow><mi>C</mi></munderover></mstyle><msub><mi>ρ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi><mi>p</mi><mi>c</mi></mfenced><mo>≤</mo><mn>2</mn><mo>,</mo><mo>∀</mo><mi>n</mi><mo>,</mo><mi>l</mi><mo>,</mo></math><img file="EP1598975B1_D0007.tif" /></maths><maths id="math0008" num=""><math display="inline"><mn>0</mn><mo>≤</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>l</mi><mo>=</mo><mn>1</mn></mrow><msub><mi>N</mi><mi>R</mi></msub></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>c</mi><mo>=</mo><mn>1</mn></mrow><mi>C</mi></munderover></mstyle><msub><mi>ρ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi><mi>p</mi><mi>c</mi></mfenced><mo>≤</mo><msub><mi>N</mi><mi>R</mi></msub><mo>⁢</mo><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi></mfenced><mo>,</mo><mo>∀</mo><mi>k</mi><mo>,</mo><mi>n</mi><mo>,</mo><mi>p</mi><mo>,</mo></math><img file="EP1598975B1_D0008.tif" /></maths><maths id="math0009" num=""><math display="inline"><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>K</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>p</mi><mo>=</mo><mn>1</mn><mo>,</mo><mi>p</mi><mo>≠</mo><mi>k</mi></mrow><mi>K</mi></munderover></mstyle><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi></mfenced><mo>=</mo><mn>2</mn><mo>,</mo><mo>∀</mo><mi>n</mi><mo>,</mo><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>k</mi></mfenced><mo>=</mo><msub><mi>δ</mi><mi>p</mi></msub><mfenced><mi>n</mi><mi>k</mi></mfenced><mo>,</mo><mo>∀</mo><mi>k</mi><mo>,</mo><mi>n</mi><mo>,</mo><mi>p</mi><mo>,</mo></math><img file="EP1598975B1_D0009.tif" /></maths> and δ<i>_k</i> (<i>n, p</i>) ∈ {0,1}, ∀<i>k</i>, <i>n</i>, <i>p</i> are included to satisfy Conditions 1 and 2. An optimal solution of the problem is obtained by IP using binary variables.

0031When <i>M</i> = 1 (single-user-MISO/OFDMA), one of the user indices <i>p</i> and the corresponding summations can be removed from Equation (3). As a result, a condition of δ<i>_k</i>(<i>n</i>,<i>p</i>)=δ<i>_p</i>(<i>n</i>,<i>k</i>),∀<i>k</i>,<i>n</i>,<i>p</i> is discarded. Furthermore, in this case, an inequality <maths id="math0010" num=""><math display="inline"><mn>0</mn><mo>≤</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>K</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>p</mi><mo>=</mo><mn>1</mn><mo>,</mo><mi>p</mi><mo>≠</mo><mi>k</mi></mrow><mi>K</mi></munderover></mstyle><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>c</mi><mo>=</mo><mn>1</mn></mrow><mi>C</mi></munderover></mstyle><msub><mi>ρ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi><mi>p</mi><mi>c</mi></mfenced><mo>≤</mo><mn>2</mn><mo>,</mo></math><img file="EP1598975B1_D0010.tif" /></maths> ∀<i>n</i>,<i>l</i> required to meet only Condition 1 is discarded.

0032When <i>N_R</i> = 1 (multiuser-MISO/OFDMA), the index <i>l</i> for MIMO subchannels and the corresponding summations can be removed from Equation (3). In this case, <maths id="math0011" num=""><math display="inline"><mn>0</mn><mo>≤</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>l</mi><mo>=</mo><mn>1</mn></mrow><msub><mi>N</mi><mi>R</mi></msub></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>c</mi><mo>=</mo><mn>1</mn></mrow><mi>C</mi></munderover></mstyle><msub><mi>ρ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi><mi>p</mi><mi>c</mi></mfenced><mo>≤</mo><msub><mi>N</mi><mi>R</mi></msub><mo>⁢</mo><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi></mfenced><mo>,</mo><mo>∀</mo><mi>k</mi><mo>,</mo><mi>n</mi><mo>,</mo><mi>p</mi></math><img file="EP1598975B1_D0011.tif" /></maths> of Equation (3) becomes <maths id="math0012" num=""><math display="inline"><mn>0</mn><mo>≤</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>c</mi><mo>=</mo><mn>1</mn></mrow><mi>C</mi></munderover></mstyle><msub><mi>ρ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi><mi>c</mi></mfenced><mo>≤</mo><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi></mfenced><mo>,</mo><mo>∀</mo><mi>k</mi><mo>,</mo><mi>n</mi><mo>,</mo><mi>p</mi></math><img file="EP1598975B1_D0012.tif" /></maths> including <maths id="math0013" num=""><math display="inline"><mn>0</mn><mo>≤</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>c</mi><mo>=</mo><mn>1</mn></mrow><mi>C</mi></munderover></mstyle><msub><mi>ρ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi><mi>p</mi><mi>c</mi></mfenced><mo>≤</mo><mn>1</mn><mo>,</mo></math><img file="EP1598975B1_D0013.tif" /></maths>∀<i>k</i>, <i>n</i>, <i>l</i>, <i>p</i> of Equation (3). Accordingly, <maths id="math0014" num=""><math display="inline"><mn>0</mn><mo>≤</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>c</mi><mo>=</mo><mn>1</mn></mrow><mi>C</mi></munderover></mstyle><msub><mi>ρ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi><mi>p</mi><mi>c</mi></mfenced><mo>≤</mo><mn>1</mn><mo>,</mo></math><img file="EP1598975B1_D0014.tif" /></maths> ∀<i>k</i>, <i>n</i>, <i>l</i>, <i>p</i> can be discarded.

0033In the case of the multiuser-MISO/OFDMA system (for convenience, <i>M</i> = 2), a single MIMO subchannel associated with a single SDMA subchannel exists. Accordingly, a MIMO subchannel index <i>l</i> can be removed, and only Condition 1 needs to be satisfied. The optimization problem in Equation (3) can be simplified as shown in Equation (4). <maths id="math0015" num="(4)"><math display="block"><mtable columnalign="left"><mtr><mtd><msub><mi>P</mi><mi>T</mi></msub><mo>=</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>K</mi></munderover></mstyle><mspace width="1em" /><mfenced open="[" close="]" separators=""><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover></mstyle><mspace width="2em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>p</mi><mo>=</mo><mn>1</mn><mo>,</mo><mi>p</mi><mo>≠</mo><mi>k</mi></mrow><mi>K</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>c</mi><mo>=</mo><mn>1</mn></mrow><mi>C</mi></munderover></mstyle><mfrac><mrow><msub><mi>f</mi><mi>k</mi></msub><mfenced><mi>c</mi></mfenced></mrow><mrow><msubsup><mi>α</mi><mi>k</mi><mn>2</mn></msubsup><mfenced><mi>n</mi><mi>l</mi><mi>p</mi></mfenced></mrow></mfrac><mo>⋅</mo><msub><mi>ρ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi><mi>c</mi></mfenced></mfenced></mtd></mtr><mtr><mtd><msub><mi>ρ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi><mi>c</mi></mfenced><mo>∈</mo><mfenced open="{" close="}"><mn>0</mn><mn>1</mn></mfenced></mtd></mtr><mtr><mtd><msub><mi>R</mi><mi>k</mi></msub><mo>≤</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>p</mi><mo>=</mo><mn>1</mn><mo>,</mo><mi>p</mi><mo>≠</mo><mi>k</mi></mrow><mi>K</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>c</mi><mo>=</mo><mn>1</mn></mrow><mi>C</mi></munderover></mstyle><mi>c</mi><mo>⋅</mo><msub><mi>ρ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi><mi>c</mi></mfenced><mo>=</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover></mstyle><msub><mi>c</mi><mi>k</mi></msub><mfenced><mi>n</mi></mfenced><mo>,</mo><mo>∀</mo><mi>k</mi></mtd></mtr><mtr><mtd><mn>0</mn><mo>≤</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>K</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>p</mi><mo>=</mo><mn>1</mn><mo>,</mo><mi>p</mi><mo>≠</mo><mi>k</mi></mrow><mi>K</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>c</mi><mo>=</mo><mn>1</mn></mrow><mi>C</mi></munderover></mstyle><msub><mi>ρ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi><mi>c</mi></mfenced><mo>≤</mo><mn>2</mn><mo>,</mo><mo>∀</mo><mi>n</mi></mtd></mtr><mtr><mtd><mn>0</mn><mo>≤</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>c</mi><mo>=</mo><mn>1</mn></mrow><mi>C</mi></munderover></mstyle><msub><mi>ρ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi><mi>c</mi></mfenced><mo>≤</mo><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi></mfenced><mo>,</mo><mo>∀</mo><mi>k</mi><mo>,</mo><mi>n</mi><mo>,</mo><mi>p</mi></mtd></mtr><mtr><mtd><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>K</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>p</mi><mo>=</mo><mn>1</mn><mo>,</mo><mi>p</mi><mo>≠</mo><mi>k</mi></mrow><mi>K</mi></munderover></mstyle><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi></mfenced><mo>=</mo><mn>2</mn><mo>,</mo><mo>∀</mo><mi>n</mi></mtd></mtr><mtr><mtd><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi></mfenced><mo>=</mo><msub><mi>δ</mi><mi>p</mi></msub><mfenced><mi>n</mi><mi>k</mi></mfenced><mo>,</mo><mo>∀</mo><mi>k</mi><mo>,</mo><mi>n</mi><mo>,</mo><mi>p</mi></mtd></mtr><mtr><mtd><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi></mfenced><mo>∈</mo><mfenced open="{" close="}"><mn>0</mn><mn>1</mn></mfenced><mo>,</mo><mo>∀</mo><mi>k</mi><mo>,</mo><mi>n</mi><mo>,</mo><mi>p</mi></mtd></mtr></mtable></math><img file="EP1598975B1_D0015.tif" /></maths>

0034In Equation (4), if the <i>k</i> -th and <i>p</i> -th user terminals occupy two SDMA subchannels of the <i>n</i> -th subcarrier, and <i>c</i> bits are allocated to an MIMO subchannel associated with an SDMA subchannel of the <i>k</i> -th user terminal, <i>ρ_k</i>(<i>n,l</i>,<i>c</i>) = 1. Otherwise, <i>ρ_k</i>(<i>n,l,c</i>) = 0.

0035In Equation (4), α<i>_k</i>(<i>n</i>, <i>p</i>) is an equivalent channel gain of the <i>k</i> -th user terminal when the <i>k</i> -th and <i>p</i> -th user terminals occupy two SDMA subchannels of the <i>n</i> -th subcarrier. In the data rate constraint of <maths id="math0016" num=""><math display="inline"><msub><mi>R</mi><mi>k</mi></msub><mo>=</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>p</mi><mo>=</mo><mn>1</mn><mo>,</mo><mi>p</mi><mo>≠</mo><mi>k</mi></mrow><mi>K</mi></munderover></mstyle><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>c</mi><mo>=</mo><mn>1</mn></mrow><mi>C</mi></munderover></mstyle><mi>c</mi><mo>⋅</mo><msub><mi>ρ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi><mi>c</mi></mfenced><mo>=</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover></mstyle><msub><mi>c</mi><mi>k</mi></msub><mfenced><mi>n</mi></mfenced><mo>,</mo><mo>∀</mo><mi>k</mi><mo>,</mo></math><img file="EP1598975B1_D0016.tif" /></maths><maths id="math0017" num=""><math display="inline"><msub><mi>c</mi><mi>k</mi></msub><mfenced><mi>n</mi></mfenced><mo>=</mo><mstyle displaystyle="false"><msubsup><mi mathvariant="normal">Σ</mi><mrow><mi>p</mi><mo>=</mo><mn>1</mn><mo>,</mo><mi>p</mi><mo>≠</mo><mi>k</mi></mrow><mi>K</mi></msubsup></mstyle><mspace width="1em" /><mstyle displaystyle="false"><msubsup><mi mathvariant="normal">Σ</mi><mrow><mi>c</mi><mo>=</mo><mn>1</mn><mspace width="2em" /></mrow><mi>C</mi></msubsup></mstyle><mi>c</mi><mo>⋅</mo><msub><mi>ρ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi><mi>c</mi></mfenced></math><img file="EP1598975B1_D0017.tif" /></maths> denotes the number of bits allocated to an MIMO subchannel of the <i>k</i> -th user terminal when the <i>k</i> -th user terminal occupies one of the SDMA subchannels of the <i>n</i> -th subcarrier.

0036In the single-user MIMO/OFDMA system, only Condition 2 should be satisfied because there is one SDMA subchannel per subcarrier. A user index <i>p</i> can be removed.

0037Accordingly, the optimization problem can be expressed as shown in Equation (5). <maths id="math0018" num="(5)"><math display="block"><mtable columnalign="left"><mtr><mtd><msub><mi>P</mi><mi>T</mi></msub><mo>=</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>K</mi></munderover></mstyle><mspace width="1em" /><mfenced open="[" close="]" separators=""><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>l</mi><mo>=</mo><mn>1</mn></mrow><msub><mi>N</mi><mi>R</mi></msub></munderover></mstyle><mspace width="2em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>c</mi><mo>=</mo><mn>1</mn></mrow><mi>C</mi></munderover></mstyle><mfrac><mrow><msub><mi>f</mi><mi>k</mi></msub><mfenced><mi>c</mi></mfenced></mrow><mrow><msubsup><mi>α</mi><mi>k</mi><mn>2</mn></msubsup><mfenced><mi>n</mi><mi>l</mi></mfenced></mrow></mfrac><mo>⋅</mo><msub><mi>ρ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi><mi>c</mi></mfenced></mfenced></mtd></mtr><mtr><mtd><mi>Constraints</mi><mo>:</mo></mtd></mtr><mtr><mtd><msub><mi>ρ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi><mi>c</mi></mfenced><mo>∈</mo><mfenced open="{" close="}"><mn>0</mn><mn>1</mn></mfenced></mtd></mtr><mtr><mtd><msub><mi>R</mi><mi>k</mi></msub><mo>=</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>l</mi><mo>=</mo><mn>1</mn></mrow><msub><mi>N</mi><mi>R</mi></msub></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>c</mi><mo>=</mo><mn>1</mn></mrow><mi>C</mi></munderover></mstyle><mi>c</mi><mo>⋅</mo><msub><mi>ρ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi><mi>c</mi></mfenced><mo>=</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>l</mi><mo>=</mo><mn>1</mn></mrow><msub><mi>N</mi><mi>R</mi></msub></munderover></mstyle><msub><mover><mi>c</mi><mo>^</mo></mover><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi></mfenced><mo>,</mo><mo>∀</mo><mi>k</mi></mtd></mtr><mtr><mtd><mn>0</mn><mo>≤</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>c</mi><mo>=</mo><mn>1</mn></mrow><mi>C</mi></munderover></mstyle><msub><mi>ρ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi><mi>c</mi></mfenced><mo>≤</mo><mn>1</mn><mo>,</mo><mo>∀</mo><mi>k</mi><mo>,</mo><mi>n</mi><mo>,</mo><mi>l</mi></mtd></mtr><mtr><mtd><mn>0</mn><mo>≤</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>l</mi><mo>=</mo><mn>1</mn></mrow><msub><mi>N</mi><mi>R</mi></msub></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>c</mi><mo>=</mo><mn>1</mn></mrow><mi>C</mi></munderover></mstyle><msub><mi>ρ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi><mi>c</mi></mfenced><mo>≤</mo><msub><mi>N</mi><mi>R</mi></msub><mo>⁢</mo><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi></mfenced><mo>,</mo><mo>∀</mo><mi>k</mi><mo>,</mo><mi>n</mi></mtd></mtr><mtr><mtd><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>p</mi><mo>=</mo><mn>1</mn></mrow><mi>K</mi></munderover></mstyle><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi></mfenced><mo>=</mo><mn>1</mn><mo>,</mo><mo>∀</mo><mi>n</mi></mtd></mtr><mtr><mtd><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi></mfenced><mo>∈</mo><mfenced open="{" close="}"><mn>0</mn><mn>1</mn></mfenced><mo>,</mo><mo>∀</mo><mi>k</mi><mo>,</mo><mi>n</mi></mtd></mtr></mtable></math><img file="EP1598975B1_D0018.tif" /></maths>

0038In Equation (5), if the <i>k</i> -th user terminal occupies one SDMA subchannel of the <i>n</i> -th subcarrier, <i>c</i> bits are allocated to the <i>l</i> -th MIMO subchannel associated with the SDMA subchannel of the <i>k</i> -th user terminal, ρ<i>_k</i>(<i>n</i>,<i>l</i>,<i>c</i>) = 1. Otherwise, ρ<i>_k</i>(<i>n</i>,<i>l</i>,<i>c</i>) = 0.

0039In Equation (5) and its constraint <maths id="math0019" num=""><math display="inline"><msub><mi>R</mi><mi>k</mi></msub><mo>=</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>l</mi><mo>=</mo><mn>1</mn></mrow><msub><mi>N</mi><mi>R</mi></msub></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>c</mi><mo>=</mo><mn>1</mn></mrow><mi>C</mi></munderover></mstyle><mi>c</mi><mo>⋅</mo><msub><mi>ρ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi><mi>c</mi></mfenced><mo>=</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>l</mi><mo>=</mo><mn>1</mn></mrow><msub><mi>N</mi><mi>R</mi></msub></munderover></mstyle><msub><mover><mi>c</mi><mo>^</mo></mover><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi></mfenced><mo>,</mo><mo>∀</mo><mi>k</mi><mo>,</mo></math><img file="EP1598975B1_D0019.tif" /></maths><i>α_k</i>(<i>n,l</i>) and <maths id="math0020" num=""><math display="inline"><msub><mi>c</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi></mfenced><mo>=</mo><mstyle displaystyle="false"><msubsup><mi mathvariant="normal">Σ</mi><mrow><mi>c</mi><mo>=</mo><mn>1</mn></mrow><mi>C</mi></msubsup></mstyle><mi>c</mi><mo>⋅</mo><msub><mi>ρ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi><mi>c</mi></mfenced></math><img file="EP1598975B1_D0020.tif" /></maths> denote an equivalent channel gain and the number of bits associated with the <i>l</i>-th MIMO subchannel of the <i>k</i> -th user terminal, respectively, when the <i>k</i> -th user terminal occupies an SDMA subchannel of the <i>n</i> -th subcarrier. If the <i>k</i> -th user terminal occupies an SDMA subchannel of the <i>n</i> -th subcarrier, a binary variable δ<i>_k</i>(<i>n</i>) = 1. Otherwise, δ<i>_k</i>(<i>n</i>) = 0.

0040Conventionally, IP requires an exponential time algorithm whose complexity rapidly increases with the number of constraints and variables.

0041Now, the behavior of the optimal IP algorithm is examined through computer simulation, and several observations are performed in relation to bit allocation.

0042The optimal IP algorithm was simulated using multiuser-MIMO/OFDMA, multiuser-MISO/OFDMA, and single-user-MIMO/OFDMA systems. Table 1 describes system parameters used in the simulation. <tables id="tabl0001" num="0001"><table frame="all"><title>Table 1</title><tgroup cols="4"><colspec colnum="1" colname="col1" colwidth="37mm" /><colspec colnum="2" colname="col2" colwidth="42mm" /><colspec colnum="3" colname="col3" colwidth="43mm" /><colspec colnum="4" colname="col4" colwidth="45mm" /><thead><row><entry align="center" valign="top" /><entry align="center" valign="top">Multiuser-MIMO/OFDMA</entry><entry align="center" valign="top">Multiuser-MISO/OFDMA</entry><entry align="center" valign="top">Single-user-MIMO/OFDMA</entry></row></thead><tbody><row><entry align="center"><i>N_T</i></entry><entry align="center">4</entry><entry align="center">2</entry><entry align="center">2</entry></row><row><entry align="center"><i>N_R</i></entry><entry align="center">2</entry><entry align="center">1</entry><entry align="center">2</entry></row><row><entry align="center"><i>M</i></entry><entry align="center">2</entry><entry align="center">2</entry><entry align="center">1</entry></row><row><entry align="center"># of FFT(<i>N</i>)</entry><entry align="center">64</entry><entry align="center">64</entry><entry align="center">64</entry></row><row><entry align="center">Total # of subchannels</entry><entry align="center">256</entry><entry align="center">128</entry><entry align="center">128</entry></row><row><entry align="center"># of users (<i>K</i>)</entry><entry namest="col2" nameend="col4" align="center">4</entry></row><row><entry align="center"># of max. bits (<i>C</i>)</entry><entry namest="col2" nameend="col4" align="center">12</entry></row><row><entry align="center">Required BER</entry><entry namest="col2" nameend="col4" align="center">10^-4</entry></row><row><entry align="center">Channel</entry><entry namest="col2" nameend="col4" align="left">8-tap frequency selective Rayleigh fading channels with exponentially decaying power profiles were assumed. The channel parameters were fixed during one frame period. The average channel magnitudes of the different users were generally unequal and the difference, denoted by <i>γ</i>, between the strongest and weakest channels of the four users was either zero or 30 dB.</entry></row></tbody></tgroup></table></tables>

0043For the multiuser-MIMO/OFDMA system, Table 2 describes the number of subchannels allocated to each user terminal and the number of bits allocated to each subchannel where <i>R</i>₁ = <i>R</i>₂ = <i>R</i>₃ = <i>R</i>₄ = 256. <tables id="tabl0002" num="0002"><table frame="all"><title>Table 2</title><tgroup cols="10"><colspec colnum="1" colname="col1" colwidth="14mm" /><colspec colnum="2" colname="col2" colwidth="26mm" /><colspec colnum="3" colname="col3" colwidth="14mm" /><colspec colnum="4" colname="col4" colwidth="28mm" /><colspec colnum="5" colname="col5" colwidth="14mm" /><colspec colnum="6" colname="col6" colwidth="14mm" /><colspec colnum="7" colname="col7" colwidth="14mm" /><colspec colnum="8" colname="col8" colwidth="14mm" /><colspec colnum="9" colname="col9" colwidth="14mm" /><colspec colnum="10" colname="col10" colwidth="14mm" /><thead><row rowsep="0"><entry align="center" valign="top"><i>γ</i> (dB)</entry><entry rowsep="1" align="center" valign="top">MIMO subchannel group</entry><entry rowsep="1" align="center" valign="top">User k</entry><entry rowsep="1" align="center" valign="top"># of assigned MIMO subchannels</entry><entry namest="col5" nameend="col9" rowsep="1" align="center" valign="top"># of MIMO subchannels with <i>c_k</i>(<i>n</i>,<i>l</i>) = <i>i</i> bits</entry><entry align="center" valign="top">Ratio</entry></row><row><entry /><entry /><entry /><entry /><entry align="center" valign="top"><i>i</i> = 2</entry><entry align="center" valign="top"><i>i</i> = 4</entry><entry align="center" valign="top"><i>i</i> = 6</entry><entry align="center" valign="top"><i>i</i> = 8</entry><entry align="center" valign="top"><i>i</i> = 10</entry><entry /></row></thead><tbody><row><entry morerows="9" align="center">0</entry><entry morerows="4" align="center"><i>l</i> = 1</entry><entry align="center">1</entry><entry align="center">34</entry><entry align="center">0</entry><entry align="center">13</entry><entry align="center">21</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="char" char="." charoff="13">0.77</entry></row><row><entry align="center">2</entry><entry align="center">28</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">28</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="char" char="." charoff="13">0.87</entry></row><row><entry align="center">3</entry><entry align="center">32</entry><entry align="center">0</entry><entry align="center">9</entry><entry align="center">23</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="char" char="." charoff="13">0.73</entry></row><row><entry align="center">4</entry><entry align="center">34</entry><entry align="center">0</entry><entry align="center">15</entry><entry align="center">19</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="char" char="." charoff="13">0.83</entry></row><row><entry align="center">Total</entry><entry align="center">128</entry><entry align="center">0</entry><entry align="center">37</entry><entry align="center">91</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="char" char="." charoff="13" /></row><row><entry morerows="4" align="center"><i>l</i> = 2</entry><entry align="center">1</entry><entry align="center">30</entry><entry align="center">21</entry><entry align="center">9</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="char" char="." charoff="13">0.58</entry></row><row><entry align="center">2</entry><entry align="center">27</entry><entry align="center">10</entry><entry align="center">17</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="char" char="." charoff="13">0.50</entry></row><row><entry align="center">3</entry><entry align="center">31</entry><entry align="center">21</entry><entry align="center">10</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="char" char="." charoff="13">0.57</entry></row><row><entry align="center">4</entry><entry align="center">32</entry><entry align="center">23</entry><entry align="center">9</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="char" char="." charoff="13">0.49</entry></row><row><entry align="center">Total</entry><entry align="center">120</entry><entry align="center">75</entry><entry align="center">45</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="char" char="." charoff="13" /></row><row><entry morerows="1" align="center">30</entry><entry morerows="1" align="center"><i>l</i> = 1</entry><entry align="center">1</entry><entry align="center">63</entry><entry align="center">31</entry><entry align="center">32</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="char" char="." charoff="13">0.88</entry></row><row rowsep="0"><entry align="center">2</entry><entry align="center">28</entry><entry align="center">0</entry><entry align="center">1</entry><entry align="center">27</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="char" char="." charoff="13">0.79</entry></row><row><entry rowsep="0" align="center" /><entry rowsep="0" align="center" /><entry align="center">3</entry><entry align="center">20</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">4</entry><entry align="center">16</entry><entry align="center">0</entry><entry align="char" char="." charoff="13">0.74</entry></row><row><entry rowsep="0" /><entry rowsep="0" /><entry align="center">4</entry><entry align="center">17</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">10</entry><entry align="center">7</entry><entry align="char" char="." charoff="13">0.72</entry></row><row><entry rowsep="0" /><entry /><entry align="center">Total</entry><entry align="center">128</entry><entry align="center">31</entry><entry align="center">33</entry><entry align="center">31</entry><entry align="center">26</entry><entry align="center">7</entry><entry align="char" char="." charoff="13" /></row><row><entry rowsep="0" /><entry morerows="4" align="center"><i>l</i> = 2</entry><entry align="center">1</entry><entry align="center">33</entry><entry align="center">33</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="char" char="." charoff="13">0.42</entry></row><row><entry rowsep="0" /><entry align="center">2</entry><entry align="center">25</entry><entry align="center">6</entry><entry align="center">18</entry><entry align="center">1</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="char" char="." charoff="13">0.46</entry></row><row><entry rowsep="0" /><entry align="center">3</entry><entry align="center">20</entry><entry align="center">0</entry><entry align="center">8</entry><entry align="center">12</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="char" char="." charoff="13">0.57</entry></row><row><entry rowsep="0" /><entry align="center">4</entry><entry align="center">17</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">15</entry><entry align="center">2</entry><entry align="center">0</entry><entry align="char" char="." charoff="13">0.56</entry></row><row><entry /><entry align="center">Total</entry><entry align="center">95</entry><entry align="center">39</entry><entry align="center">26</entry><entry align="center">28</entry><entry align="center">2</entry><entry align="center">0</entry><entry align="char" char="." charoff="13" /></row></tbody></tgroup></table></tables>

0044Because equivalent channel gains of two MIMO subchannels (<i>N_R</i> = 2), {α<i>_k</i>(<i>n</i>,<i>l</i>,<i>p</i>),<i>l</i> = 1, 2}, are different in most cases, the results are sorted into two groups. The first group includes resulting values associated with an MIMO subchannel with a larger equivalent channel gain α<i>_k</i>(<i>n</i>,l,<i>p</i>), and the second group includes the rest. In relation to channels with the same channel gain (γ = 0), subchannels are almost equivalently distributed to user terminals. That is, 28 to 34 subchannels of Group 1 are allocated to each user, and 27 to 32 subchannels of Group 2 are allocated to each user. Where γ = 30 <i>dB</i>, a large number of subchannels were allocated to User Terminal 1 with the lowest average channel magnitude, and a small number of subchannels were allocated to User Terminal 4 with the highest average channel magnitude. This occurred because <i>R</i>₁ = <i>R</i>₂ = <i>R</i>₃ = <i>R</i>₄.

0045It is important to observe that the optimal IP often loaded the same number of bits (or constellation size) for subchannels allocated to one user. This indicates that <i>c_k</i>(<i>n</i>,<i>l</i>) in Equation (1) tends to be the same regardless of <i>n</i>. More specifically, <i>c_k</i>(<i>l</i>) indicates the dominant constellation.

0046When γ = 0 <i>dB</i> , <i>c</i>₁(1) = 6 because 21 out of 34 MIMO subchannels were loaded 6 bits. The remaining 13 subchannels were loaded 4 bits. Accordingly, the dominant constellation for each pair of (<i>k</i>,<i>l</i>) can be found.

0047When the same experiment are repeated 1,000 times as shown in Table 3, it was observed that about 70 % of <i>c_k</i>(<i>n</i>,<i>l</i>) were equal to their corresponding dominant constellation <i>c_k</i>(<i>l</i>), and almost all <i>c_k</i>(<i>n,l</i>) were in the neighborhood of <i>c_k</i>(<i>l</i>). <tables id="tabl0003" num="0003"><table frame="all"><title>Table 3</title><tgroup cols="3"><colspec colnum="1" colname="col1" colwidth="98mm" /><colspec colnum="2" colname="col2" colwidth="14mm" /><colspec colnum="3" colname="col3" colwidth="16mm" /><thead><row><entry align="center" valign="top" /><entry align="center" valign="top"><i>γ</i> = 0<i>dB</i></entry><entry align="center" valign="top"><i>γ</i> = 30<i>dB</i></entry></row></thead><tbody><row><entry align="center"><maths id="math0021" num=""><math display="block"><mi>Pr</mi><mfenced separators=""><msub><mi>c</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi></mfenced><mo>=</mo><msub><mi>c</mi><mi>k</mi></msub><mfenced><mi>l</mi></mfenced><mrow><mo>|</mo></mrow><mstyle displaystyle="false"><munderover><mo>∑</mo><mrow><mi>p</mi><mo>=</mo><mn>1</mn><mo>,</mo><mi>p</mi><mo>≠</mo><mi>k</mi></mrow><mi>K</mi></munderover></mstyle><mstyle displaystyle="false"><munderover><mo>∑</mo><mrow><mi>c</mi><mo>=</mo><mn>1</mn></mrow><mi>C</mi></munderover></mstyle><msub><mi>ρ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi><mi>p</mi><mi>c</mi></mfenced></mfenced><mo>=</mo><mn>1</mn></math><img file="EP1598975B1_D0021.tif" /></maths></entry><entry align="char" char="." charoff="13">0.69</entry><entry align="char" char="." charoff="12">0.74</entry></row><row><entry align="center"><maths id="math0022" num=""><math display="block"><mtable columnalign="left"><mtr><mtd><mi>Pr</mi><mfenced separators=""><msub><mi>c</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi></mfenced><mo>=</mo><msub><mi>c</mi><mi>k</mi></msub><mfenced><mi>l</mi></mfenced><mrow><mo>|</mo></mrow><mstyle displaystyle="false"><munderover><mo>∑</mo><mrow><mi>p</mi><mo>=</mo><mn>1</mn><mo>,</mo><mi>p</mi><mo>≠</mo><mi>k</mi></mrow><mi>K</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="false"><munderover><mo>∑</mo><mrow><mi>c</mi><mo>=</mo><mn>1</mn></mrow><mi>C</mi></munderover></mstyle><msub><mi>ρ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi><mi>p</mi><mi>c</mi></mfenced><mo>=</mo><mn>1</mn></mfenced></mtd></mtr><mtr><mtd><mo>+</mo><mi>Pr</mi><mfenced separators=""><msub><mi>c</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi></mfenced><mo>=</mo><msub><mi>c</mi><mi>k</mi></msub><mfenced><mi>l</mi></mfenced><mo>±</mo><mn>2</mn><mrow><mo>|</mo></mrow><mstyle displaystyle="false"><munderover><mo>∑</mo><mrow><mi>p</mi><mo>=</mo><mn>1</mn><mo>,</mo><mi>p</mi><mo>≠</mo><mi>k</mi></mrow><mi>K</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="false"><munderover><mo>∑</mo><mrow><mi>c</mi><mo>=</mo><mn>1</mn></mrow><mi>C</mi></munderover></mstyle><msub><mi>ρ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi><mi>p</mi><mi>c</mi></mfenced><mo>=</mo><mn>1</mn></mfenced></mtd></mtr></mtable></math><img file="EP1598975B1_D0022.tif" /></maths></entry><entry align="char" char="." charoff="13">0.99</entry><entry align="char" char="." charoff="12">0.99</entry></row></tbody></tgroup></table></tables>

0048The observation regarding the dominant constellation is essential to obtain a suboptimal algorithm.

0049Table 2 describes a ratio of average subchannel gains <maths id="math0023" num=""><math display="inline"><msubsup><mi>α</mi><mi>k</mi><mn>2</mn></msubsup><mfenced><mi>l</mi></mfenced></math><img file="EP1598975B1_D0023.tif" /></maths> and <maths id="math0024" num=""><math display="inline"><msubsup><mover><mi>α</mi><mo>‾</mo></mover><mi>k</mi><mn>2</mn></msubsup><mfenced><mi>l</mi></mfenced><mn>.</mn></math><img file="EP1598975B1_D0024.tif" /></maths> This ratio had only a small variation. Accordingly, this ratio will also be useful for the suboptimal algorithm.

0050When <i>R</i>₁ = <i>R</i>₂ = <i>R</i>₃ = <i>R</i>₄ = 128 in the multiuser-MISO/OFDMA system and the single-user-MIMO/OFDMA system, Tables 4 and 5 show the resulting number of subchannels allocated to each user terminal and the number of bits allocated to each subchannel. <tables id="tabl0004" num="0004"><table frame="all"><title>Table 4</title><tgroup cols="9"><colspec colnum="1" colname="col1" colwidth="14mm" /><colspec colnum="2" colname="col2" colwidth="14mm" /><colspec colnum="3" colname="col3" colwidth="51mm" /><colspec colnum="4" colname="col4" colwidth="14mm" /><colspec colnum="5" colname="col5" colwidth="14mm" /><colspec colnum="6" colname="col6" colwidth="14mm" /><colspec colnum="7" colname="col7" colwidth="14mm" /><colspec colnum="8" colname="col8" colwidth="14mm" /><colspec colnum="9" colname="col9" colwidth="14mm" /><thead><row rowsep="0"><entry align="center" valign="top"><i>γ</i> (<i>dB</i>)</entry><entry rowsep="1" align="center" valign="top">User k</entry><entry rowsep="1" align="center" valign="top"># of assigned MIMO subchannels</entry><entry namest="col4" nameend="col8" rowsep="1" align="center" valign="top"># of MIMO subchannels with <i>c_k</i>(<i>n</i>) = <i>i</i> bits</entry><entry align="center" valign="top">Ratio</entry></row><row><entry /><entry /><entry /><entry align="center" valign="top"><i>i</i> = 2</entry><entry align="center" valign="top"><i>i</i> = 4</entry><entry align="center" valign="top"><i>i</i> = 6</entry><entry align="center" valign="top"><i>i</i> = 8</entry><entry align="center" valign="top"><i>i</i> = 10</entry><entry /></row></thead><tbody><row><entry morerows="4" align="center">0</entry><entry align="center">1</entry><entry align="center">33</entry><entry align="center">2</entry><entry align="center">31</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="char" char="." charoff="13">0.83</entry></row><row><entry align="center">2</entry><entry align="center">30</entry><entry align="center">0</entry><entry align="center">26</entry><entry align="center">4</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="char" char="." charoff="13">0.76</entry></row><row><entry align="center">3</entry><entry align="center">32</entry><entry align="center">6</entry><entry align="center">20</entry><entry align="center">6</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="char" char="." charoff="13">0.75</entry></row><row><entry align="center">4</entry><entry align="center">33</entry><entry align="center">2</entry><entry align="center">31</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="char" char="." charoff="13">0.81</entry></row><row><entry align="center">Total</entry><entry align="center">128</entry><entry align="center">10</entry><entry align="center">108</entry><entry align="center">10</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="char" char="." charoff="13" /></row><row><entry morerows="4" align="center">30</entry><entry align="center">1</entry><entry align="center">54</entry><entry align="center">44</entry><entry align="center">10</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="char" char="." charoff="13">0.88</entry></row><row><entry align="center">2</entry><entry align="center">32</entry><entry align="center">7</entry><entry align="center">18</entry><entry align="center">7</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="char" char="." charoff="13">0.80</entry></row><row><entry align="center">3</entry><entry align="center">21</entry><entry align="center">0</entry><entry align="center">5</entry><entry align="center">10</entry><entry align="center">6</entry><entry align="center">0</entry><entry align="char" char="." charoff="13">0.89</entry></row><row><entry align="center">4</entry><entry align="center">20</entry><entry align="center">0</entry><entry align="center">1</entry><entry align="center">14</entry><entry align="center">5</entry><entry align="center">0</entry><entry align="char" char="." charoff="13">0.87</entry></row><row><entry align="center">Total</entry><entry align="center">127</entry><entry align="center">51</entry><entry align="center">34</entry><entry align="center">31</entry><entry align="center">11</entry><entry align="center">0</entry><entry align="center" /></row></tbody></tgroup></table></tables><tables id="tabl0005" num="0005"><table frame="all"><title>Table 5</title><tgroup cols="10"><colspec colnum="1" colname="col1" colwidth="14mm" /><colspec colnum="2" colname="col2" colwidth="25mm" /><colspec colnum="3" colname="col3" colwidth="14mm" /><colspec colnum="4" colname="col4" colwidth="26mm" /><colspec colnum="5" colname="col5" colwidth="14mm" /><colspec colnum="6" colname="col6" colwidth="14mm" /><colspec colnum="7" colname="col7" colwidth="14mm" /><colspec colnum="8" colname="col8" colwidth="14mm" /><colspec colnum="9" colname="col9" colwidth="14mm" /><colspec colnum="10" colname="col10" colwidth="17mm" /><thead><row><entry morerows="1" rowsep="0" align="center" valign="top"><i>γ</i>(dB)</entry><entry morerows="1" align="center" valign="top">MIMO subchannel group</entry><entry morerows="1" align="center" valign="top">User k</entry><entry morerows="1" align="center" valign="top"># of assigned MIMO subchannels</entry><entry namest="col5" nameend="col9" align="center" valign="top"># of MIMO subchannels with <i>c_k</i>(<i>n,l</i>) = <i>i</i> bits</entry><entry rowsep="0" align="center" valign="top">Ratio</entry></row><row><entry align="center" valign="top"><i>i</i> = 2</entry><entry align="center" valign="top"><i>i</i> = 4</entry><entry align="center" valign="top"><i>i</i> = 6</entry><entry align="center" valign="top"><i>i</i> = 8</entry><entry align="center" valign="top"><i>i</i> = 10</entry><entry align="center" valign="top"><maths id="math0025" num=""><img file="EP1598975B1_D0025.tif" /></maths></entry></row></thead><tbody><row><entry morerows="9" align="center">0</entry><entry morerows="4" align="center"><i>l</i> = 1</entry><entry align="center">1</entry><entry align="center">19</entry><entry align="center">0</entry><entry align="center">14</entry><entry align="center">5</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="char" char="." charoff="11">0.87</entry></row><row><entry align="center">2</entry><entry align="center">16</entry><entry align="center">0</entry><entry align="center">3</entry><entry align="center">13</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="char" char="." charoff="11">0.82</entry></row><row><entry align="center">3</entry><entry align="center">14</entry><entry align="center">0</entry><entry align="center">3</entry><entry align="center">11</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="char" char="." charoff="11">0.74</entry></row><row><entry align="center">4</entry><entry align="center">15</entry><entry align="center">0</entry><entry align="center">4</entry><entry align="center">11</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="char" char="." charoff="11">0.71</entry></row><row><entry align="center">Total</entry><entry align="center">64</entry><entry align="center">0</entry><entry align="center">24</entry><entry align="center">40</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="char" char="." charoff="11" /></row><row><entry morerows="4" align="center"><i>l</i> = 2</entry><entry align="center">1</entry><entry align="center">19</entry><entry align="center">17</entry><entry align="center">2</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="char" char="." charoff="11">0.66</entry></row><row><entry align="center">2</entry><entry align="center">16</entry><entry align="center">13</entry><entry align="center">3</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="char" char="." charoff="11">0.60</entry></row><row><entry align="center">3</entry><entry align="center">14</entry><entry align="center">3</entry><entry align="center">11</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="char" char="." charoff="11">0.47</entry></row><row><entry align="center">4</entry><entry align="center">14</entry><entry align="center">5</entry><entry align="center">9</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="char" char="." charoff="11">0.62</entry></row><row><entry align="center">Total</entry><entry align="center">63</entry><entry align="center">38</entry><entry align="center">25</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="char" char="." charoff="11" /></row><row><entry morerows="9" align="center">30</entry><entry morerows="4" align="center"><i>l</i> = 1</entry><entry align="center">1</entry><entry align="center">38</entry><entry align="center">17</entry><entry align="center">21</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="char" char="." charoff="11">0.83</entry></row><row><entry align="center">2</entry><entry align="center">11</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">8</entry><entry align="center">3</entry><entry align="center">0</entry><entry align="char" char="." charoff="11">0.90</entry></row><row><entry align="center">3</entry><entry align="center">8</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">5</entry><entry align="center">3</entry><entry align="char" char="." charoff="11">0.84</entry></row><row><entry align="center">4</entry><entry align="center">7</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">7</entry><entry align="char" char="." charoff="11">0.96</entry></row><row><entry align="center">Total</entry><entry align="center">64</entry><entry align="center">17</entry><entry align="center">21</entry><entry align="center">8</entry><entry align="center">8</entry><entry align="center">10</entry><entry align="char" char="." charoff="11" /></row><row><entry morerows="4" align="center"><i>l</i> = 2</entry><entry align="center">1</entry><entry align="center">5</entry><entry align="center">5</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="char" char="." charoff="11">0.40</entry></row><row><entry align="center">2</entry><entry align="center">11</entry><entry align="center">0</entry><entry align="center">5</entry><entry align="center">6</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="char" char="." charoff="11">0.43</entry></row><row><entry align="center">3</entry><entry align="center">8</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">3</entry><entry align="center">5</entry><entry align="center">0</entry><entry align="char" char="." charoff="11">0.54</entry></row><row><entry align="center">4</entry><entry align="center">7</entry><entry align="center">0</entry><entry align="center">0</entry><entry align="center">1</entry><entry align="center">4</entry><entry align="center">2</entry><entry align="char" char="." charoff="11">0.64</entry></row><row><entry align="center">Total</entry><entry align="center">31</entry><entry align="center">5</entry><entry align="center">5</entry><entry align="center">10</entry><entry align="center">9</entry><entry align="center">2</entry><entry align="center" /></row></tbody></tgroup></table></tables>

0051We can also find the same observation regarding the dominant constellation and the ratio between average subchannel gains as in the multiuser-MIMO/OFDMA system. <i>c_k</i> denotes the dominant constellation in the multiuser-MISO/OFDMA system.

0052When γ = 0 <i>dB</i>, <i>c</i>₁ = 4 because 31 out of 33 subchannels were loaded 4 bits. The remaining two subchannels were loaded 2 bits (refer to Table 4). Accordingly, the dominant constellation for each user terminal <i>k</i> can be found. From Table 5, the dominant constellation <i>c_k</i>(<i>l</i>) in the single-user-MIMO/OFDMA system can also be determined. Further, in Table 5, ratios between average subchannel gains only have a small variation.

Suboptimal Subchannel and Bit Allocation

0053A preferred embodiment of the present invention separates the subchannel and bit allocation problem into two steps to reduce complexity.

0054In the first step, subchannels are allocated under the assumption of dominant constellation.

Dominant Constellation of Multiuser-MIMO

/

OFDMA

0055<maths id="math0026" num=""><math display="block"><msub><mi>c</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi></mfenced><mo>=</mo><mrow><mo>{</mo></mrow><mtable columnalign="left"><mtr><mtd><msub><mi>c</mi><mi>k</mi></msub><mfenced><mi>l</mi></mfenced><mo>,</mo></mtd><mtd><mi mathvariant="italic">if</mi><mstyle displaystyle="false"><munderover><mo>∑</mo><mrow><mi>p</mi><mo>=</mo><mn>1</mn><mo>,</mo><mi>p</mi><mo>≠</mo><mi>k</mi></mrow><mi>K</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="false"><munderover><mo>∑</mo><mrow><mi>c</mi><mo>=</mo><mn>1</mn></mrow><mi>C</mi></munderover></mstyle><msub><mi>ρ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi><mi>p</mi><mi>c</mi></mfenced><mo>=</mo><mn>1</mn></mtd></mtr><mtr><mtd><mn>0</mn><mo>,</mo></mtd><mtd><mi mathvariant="italic">otherwise</mi><mn>.</mn></mtd></mtr></mtable></math><img file="EP1598975B1_D0026.tif" /></maths>

Dominant Constellation of Multiuser-MISO

/

OFDMA

0056<maths id="math0027" num=""><math display="block"><msub><mi>c</mi><mi>k</mi></msub><mfenced><mi>n</mi></mfenced><mo>=</mo><mrow><mo>{</mo></mrow><mtable columnalign="left"><mtr><mtd><msub><mi>c</mi><mi>k</mi></msub><mo>,</mo></mtd><mtd><mi mathvariant="italic">if</mi><mstyle displaystyle="false"><munderover><mo>∑</mo><mrow><mi>p</mi><mo>=</mo><mn>1</mn><mo>,</mo><mi>p</mi><mo>≠</mo><mi>k</mi></mrow><mi>K</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="false"><munderover><mo>∑</mo><mrow><mi>c</mi><mo>=</mo><mn>1</mn></mrow><mi>C</mi></munderover></mstyle><msub><mi>ρ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi><mi>c</mi></mfenced><mo>=</mo><mn>1</mn></mtd></mtr><mtr><mtd><mn>0</mn><mo>,</mo></mtd><mtd><mi mathvariant="italic">otherwise</mi><mn>.</mn></mtd></mtr></mtable></math><img file="EP1598975B1_D0027.tif" /></maths>

Dominant Constellation of Single-User-MIMO

/

OFDMA

0057<maths id="math0028" num=""><math display="block"><msub><mi>c</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi></mfenced><mo>=</mo><mrow><mo>{</mo></mrow><mtable columnalign="left"><mtr><mtd><msub><mi>c</mi><mi>k</mi></msub><mfenced><mi>l</mi></mfenced><mo>,</mo></mtd><mtd><mi mathvariant="italic">if</mi><mstyle displaystyle="false"><munderover><mo>∑</mo><mrow><mi>c</mi><mo>=</mo><mn>1</mn></mrow><mi>C</mi></munderover></mstyle><msub><mi>ρ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi><mi>c</mi></mfenced><mo>=</mo><mn>1</mn></mtd></mtr><mtr><mtd><mn>0</mn><mo>,</mo></mtd><mtd><mi mathvariant="italic">otherwise</mi><mn>.</mn></mtd></mtr></mtable></math><img file="EP1598975B1_D0028.tif" /></maths>

0058In the second step, bits are distributed to subchannels allocated in the first step. Accordingly, the assumption in the first step is not assumed in this step. The subchannel allocation in the first step can be performed via suboptimal algorithms, while the bit allocation in the second step can adopt a greedy algorithm. By separately performing subchannel and bit allocation, this yields a suboptimal algorithm that is considerably simpler to implement than the optimal IP approach.

Subchannel Allocation

0059Using the dominant constellation of the multiuser-MIMO/OFDMA, the optimal subchannel allocation problem in the first step can be expressed as shown in Equation 6. <maths id="math0029" num="(6)"><math display="block"><mtable columnalign="left"><mtr><mtd><msub><mi>P</mi><mi>T</mi></msub><mo>=</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>K</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>p</mi><mo>=</mo><mn>1</mn><mo>,</mo><mi>p</mi><mo>≠</mo><mi>k</mi></mrow><mi>K</mi></munderover></mstyle><msub><mi>g</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi></mfenced><mo>⋅</mo><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi></mfenced><mspace width="1em" /><mi mathvariant="italic">for</mi><mspace width="1em" /><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi></mfenced><mo>∈</mo><mfenced open="{" close="}"><mn>0</mn><mn>1</mn></mfenced></mtd></mtr><mtr><mtd><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>K</mi></munderover></mstyle><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>p</mi><mo>=</mo><mn>1</mn><mo>,</mo><mi>p</mi><mo>≠</mo><mi>k</mi></mrow><mi>K</mi></munderover></mstyle><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi></mfenced><mo>=</mo><mn>2</mn><mo>,</mo><mo>∀</mo><mi>n</mi></mtd></mtr><mtr><mtd><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover></mstyle><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi></mfenced><mo>≤</mo><mi>N</mi><mo>,</mo><mo>∀</mo><mi>k</mi><mo>,</mo><mi>p</mi></mtd></mtr><mtr><mtd><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover></mstyle><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>p</mi><mo>=</mo><mn>1</mn><mo>,</mo><mi>p</mi><mo>≠</mo><mi>k</mi></mrow><mi>K</mi></munderover></mstyle><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi></mfenced><mo>=</mo><msub><mi>r</mi><mi>k</mi></msub><mo>,</mo><mo>∀</mo><mi>k</mi></mtd></mtr><mtr><mtd><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi></mfenced><mo>=</mo><msub><mi>δ</mi><mi>p</mi></msub><mfenced><mi>n</mi><mi>k</mi></mfenced><mo>,</mo><mo>∀</mo><mi>k</mi><mo>,</mo><mi>n</mi><mo>,</mo><mi>p</mi></mtd></mtr></mtable></math><img file="EP1598975B1_D0029.tif" /></maths>

0060In Equation (6), <maths id="math0030" num=""><math display="inline"><msub><mi>g</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi></mfenced><mo>=</mo><msubsup><mi mathvariant="normal">Σ</mi><mrow><mi>l</mi><mo>=</mo><mn>1</mn></mrow><msub><mi>N</mi><mi>R</mi></msub></msubsup><mo>⁢</mo><mfrac><mrow><msub><mi>f</mi><mi>k</mi></msub><mfenced separators=""><msub><mi>c</mi><mi>k</mi></msub><mfenced><mi>l</mi></mfenced></mfenced></mrow><mrow><msubsup><mi>α</mi><mi>k</mi><mn>2</mn></msubsup><mfenced><mi>n</mi><mi>l</mi><mi>p</mi></mfenced></mrow></mfrac></math><img file="EP1598975B1_D0030.tif" /></maths> and <maths id="math0031" num=""><math display="inline"><msub><mi>r</mi><mi>k</mi></msub><mo>=</mo><mfrac><msub><mi>R</mi><mi>k</mi></msub><mrow><msubsup><mi mathvariant="normal">Σ</mi><mrow><mi>l</mi><mo>=</mo><mn>1</mn></mrow><msub><mi>N</mi><mi>R</mi></msub></msubsup><mo>⁢</mo><msub><mi>c</mi><mi>k</mi></msub><mfenced><mi>l</mi></mfenced></mrow></mfrac><mo>,</mo></math><img file="EP1598975B1_D0031.tif" /></maths> and <maths id="math0032" num=""><math display="inline"><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover></mstyle><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi></mfenced><mo>≤</mo><mi>N</mi><mo>,</mo><mo>∀</mo><mi>k</mi><mo>,</mo><mi>p</mi></math><img file="EP1598975B1_D0032.tif" /></maths> is an auxiliary constraint, which is always true due to <i>δ_k</i>(<i>n,p</i>)∈ {0,1}. The auxiliary constraint is included for the purpose of finding a useful observation. Equation (6) is considerably simpler than the original IP of Equation (3).

0061Furthermore, an efficient heuristic algorithm can be found for the following observation.

0062Observation 1: Suppose that {<i>c_k</i>(<i>l</i>)} are known. Then, {<i>f_k</i>(<i>c_k</i>(<i>l</i>))} becomes known and Equation (6) takes the form of a transportation problem that can be relaxed to linear programming (LP).

0063In Equation (6), the combination of two user terminals <i>k</i> and <i>p,</i> {(<i>k</i>,<i>p</i>)}<i>,</i> is supplied to each subcarrier depending on the costs {<i>g_k</i>(<i>n</i>,<i>p</i>) . δ<i>_k</i>(<i>n</i>,<i>p</i>) is the number of units shipped from the combination (<i>k</i>,<i>p</i>) to the <i>n</i> -th subcarrier if the <i>k</i> -th and <i>p</i> -th users occupy two SDMA subchannels of the <i>n</i> -the subcarrier. The constraints in Equation (6) are the demand and supply constraints, respectively, of the transportation problem.

0064In the case of transportation, it is straightforward to show that IP is relaxed to LP.

0065In addition, there are efficient heuristic algorithms. One such algorithm is known as Vogel's method capable of being modified to take account of the additional constraints of <maths id="math0033" num=""><math display="inline"><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover></mstyle><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>p</mi><mo>=</mo><mn>1</mn><mo>,</mo><mi>p</mi><mo>≠</mo><mi>k</mi></mrow><mi>K</mi></munderover></mstyle><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi></mfenced><mo>=</mo><msub><mi>r</mi><mi>k</mi></msub><mo>,</mo></math><img file="EP1598975B1_D0033.tif" /></maths> ∀<i>k</i> and δ<i>_k</i>(<i>n,p</i>) = δ<i>_p</i>(<i>n</i>,<i>k</i>), ∀<i>k,n,p</i> in Equation (6), even though the whole optimization in Equation (6) cannot be relaxed to LP. In the suboptimal algorithm in accordance with the present invention, the problem is solved using the modified Vogel's method.

0066Before solving the optimization problem in the first step, {<i>c_k</i>(<i>l</i>)} in the dominant constellation can be obtained during an initial phase. Evaluation of {<i>c_k</i>(<i>l</i>)} requires the following assumption on the channel gain: <maths id="math0034" num=""><math display="block"><msubsup><mi>α</mi><mi>k</mi><mn>2</mn></msubsup><mfenced><mi>n</mi><mi>l</mi><mi>p</mi></mfenced><mo>=</mo><mrow><mo>{</mo></mrow><mtable columnalign="left"><mtr><mtd><msubsup><mi>α</mi><mi>k</mi><mn>2</mn></msubsup><mfenced><mi>l</mi></mfenced><mo>,</mo></mtd><mtd><mi mathvariant="italic">if</mi><mspace width="1em" /><msub><mi mathvariant="italic">δ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi></mfenced><mo>=</mo><mn>1</mn></mtd></mtr><mtr><mtd><mn>0</mn><mo>,</mo></mtd><mtd><mi mathvariant="italic">otherwise</mi></mtd></mtr></mtable><mo>,</mo></math><img file="EP1598975B1_D0034.tif" /></maths> where <maths id="math0035" num=""><math display="inline"><msubsup><mi>α</mi><mi>k</mi><mn>2</mn></msubsup><mfenced><mi>l</mi></mfenced></math><img file="EP1598975B1_D0035.tif" /></maths> is the average of all subchannel gains associated with the <i>k</i> -th user and MIMO subchannel group <i>l</i>.

0067Under the above assumption, Equation (6) can be simplified as shown in Equation (7). <maths id="math0036" num="(7)"><math display="block"><mtable columnalign="left"><mtr><mtd><msub><mi>P</mi><mi>T</mi></msub><mo>=</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>K</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>l</mi><mo>=</mo><mn>1</mn></mrow><msub><mi>N</mi><mi>R</mi></msub></munderover></mstyle><mfrac><mrow><msub><mi>f</mi><mi>k</mi></msub><mfenced separators=""><msub><mi>c</mi><mi>k</mi></msub><mfenced><mi>l</mi></mfenced></mfenced></mrow><mrow><msubsup><mi>α</mi><mi>k</mi><mn>2</mn></msubsup><mfenced><mi>l</mi></mfenced></mrow></mfrac><mo>⋅</mo><mfrac><msub><mi>R</mi><mi>k</mi></msub><mrow><mstyle displaystyle="false"><msubsup><mi mathvariant="normal">Σ</mi><mrow><mi>l</mi><mo>=</mo><mn>1</mn></mrow><msub><mi>N</mi><mi>R</mi></msub></msubsup></mstyle><msub><mi>c</mi><mi>k</mi></msub><mfenced><mi>l</mi></mfenced></mrow></mfrac></mtd></mtr><mtr><mtd><mi>Constraint</mi><mo>:</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi mathvariant="normal">k</mi><mo>=</mo><mn>1</mn></mrow><mi>K</mi></munderover></mstyle><mfrac><msub><mi>R</mi><mi>k</mi></msub><mrow><mstyle displaystyle="false"><msubsup><mi mathvariant="normal">Σ</mi><mrow><mi>l</mi><mo>=</mo><mn>1</mn></mrow><msub><mi>N</mi><mi>R</mi></msub></msubsup></mstyle><msub><mi>c</mi><mi>k</mi></msub><mfenced><mi>l</mi></mfenced></mrow></mfrac><mo>=</mo><mn>2</mn><mo>⁢</mo><mi>N</mi></mtd></mtr></mtable><mo>,</mo></math><img file="EP1598975B1_D0036.tif" /></maths> where <maths id="math0037" num=""><math display="inline"><msubsup><mi mathvariant="normal">Σ</mi><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></msubsup><mspace width="1em" /><msubsup><mi mathvariant="normal">Σ</mi><mrow><mi>p</mi><mo>=</mo><mn>1</mn><mo>,</mo><mi>p</mi><mo>≠</mo><mi>k</mi></mrow><mi>K</mi></msubsup><mo>⁢</mo><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi></mfenced></math><img file="EP1598975B1_D0037.tif" /></maths> is replaced with <maths id="math0038" num=""><math display="inline"><msub><mi>R</mi><mi>k</mi></msub><mo>/</mo><msubsup><mi mathvariant="normal">Σ</mi><mrow><mi>l</mi><mo>=</mo><mn>1</mn></mrow><msub><mi>N</mi><mi>R</mi></msub></msubsup><mo>⁢</mo><msub><mi>c</mi><mi>k</mi></msub><mfenced><mi>l</mi></mfenced><mo>,</mo></math><img file="EP1598975B1_D0038.tif" /></maths> due to the constraint of <maths id="math0039" num=""><math display="inline"><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover></mstyle><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>p</mi><mo>=</mo><mn>1</mn><mo>,</mo><mi>p</mi><mo>≠</mo><mi>k</mi></mrow><mi>K</mi></munderover></mstyle><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi></mfenced><mo>=</mo><msub><mi>r</mi><mi>k</mi></msub><mo>,</mo></math><img file="EP1598975B1_D0039.tif" /></maths> ∀<i>k</i> in Equation (6).

0068The solution <maths id="math0040" num=""><math display="inline"><mrow><mo>{</mo></mrow><msubsup><mi>c</mi><mi>k</mi><mo>*</mo></msubsup><mfenced><mi>l</mi></mfenced></math><img file="EP1598975B1_D0040.tif" /></maths> of Equation (7) can be obtained by introducing a Lagrange multiplier µ and using a numerical technique, such as vector-form Newton's method.

0069Although the obtained <maths id="math0041" num=""><math display="inline"><mrow><mo>{</mo></mrow><msubsup><mi>c</mi><mi>k</mi><mo>*</mo></msubsup><mfenced><mi>l</mi></mfenced></math><img file="EP1598975B1_D0041.tif" /></maths> are not integers, they can still be used for the optimization in Equation (6).

0070The optimization in Equation (6) is an IP problem with much computational load.

0071As described above, to reduce the load, a heuristic subchannel allocation algorithm is developed by modifying Vogel's method. The modification is to put the additional constraints of <maths id="math0042" num=""><math display="inline"><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover></mstyle><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>p</mi><mo>=</mo><mn>1</mn><mo>,</mo><mi>p</mi><mo>≠</mo><mi>k</mi></mrow><mi>K</mi></munderover></mstyle><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi></mfenced><mo>=</mo><msub><mi>r</mi><mi>k</mi></msub><mo>,</mo></math><img file="EP1598975B1_D0042.tif" /></maths> ∀<i>k</i> and <i>δ_k</i>(<i>n,p</i>) = <i>δ_p</i>(<i>n,k</i>), ∀<i>k,n,p</i> in Equation (6) into the suitable steps of Vogel's method.

0072To describe the heuristic algorithm, the following notations are necessary: <i>S</i> and <i>U</i> denotes sets of subcarrier and user indices, respectively. These sets are defined in Equation (8) and Equation (9). <maths id="math0043" num="(8)"><math display="block"><mi>S</mi><mo>⊆</mo><mfenced open="{" close="}"><mn>1</mn><mn>2</mn><mo>…</mo><mi>N</mi></mfenced></math><img file="EP1598975B1_D0043.tif" /></maths><maths id="math0044" num="(9)"><math display="block"><mi>U</mi><mo>⊆</mo><mrow><mo>{</mo><mfenced><mi>k</mi><mi>p</mi></mfenced><mrow><mo>|</mo></mrow><mi>k</mi><mo>=</mo><mn>1</mn><mo>,</mo><mo>…</mo><mo>,</mo><mi>K</mi><mo>,</mo><mi>p</mi><mo>=</mo><mn>1</mn><mo>,</mo><mo>…</mo><mo>,</mo><mi>K</mi><mo>,</mo><mi>k</mi><mo>≠</mo><mi>p</mi></mrow></math><img file="EP1598975B1_D0044.tif" /></maths>

0073<i>P_n</i> is the penalty defined as the difference between the two smallest cost values in {<i>g_m</i>(<i>n</i>,<i>p</i>)|<i>k</i> = 1,..., <i>K</i>, <i>p</i> = 1,...,<i>K</i>, <i>k</i> ≠ <i>p</i>}. More specifically, <maths id="math0045" num=""><math display="inline"><msub><mi>P</mi><mi>n</mi></msub><mo>=</mo><msubsup><mi>g</mi><mi>k</mi><mfenced><mn>2</mn></mfenced></msubsup><mfenced><mi>n</mi><mi>p</mi></mfenced><mo>-</mo><msubsup><mi>g</mi><mi>k</mi><mfenced><mn>1</mn></mfenced></msubsup><mfenced><mi>n</mi><mi>p</mi></mfenced><mo>,</mo></math><img file="EP1598975B1_D0045.tif" /></maths> where <maths id="math0046" num=""><math display="inline"><msubsup><mi>g</mi><mi>k</mi><mfenced><mi>i</mi></mfenced></msubsup><mfenced><mi>n</mi><mi>p</mi></mfenced></math><img file="EP1598975B1_D0046.tif" /></maths> denotes the <i>i</i> -th smallest value among {<i>g_k</i>(<i>n,p</i>)|<i>k</i> = 1,...,<i>K</i>, <i>p</i> = 1,...,<i>K</i>,<i>k</i> ≠ <i>p</i>}. At the beginning, <i>S</i> = {1,2,...,<i>N</i>} and <i>U</i> = {(<i>k</i>, <i>p</i>)|<i>k</i> =1,..., <i>K</i>, <i>p</i> =1,..., <i>K</i>, <i>k</i> ≠ <i>p</i>. The heuristic algorithm is stated as follows: <i>Initialization</i> Set δ_k(n,p) to zero for all <i>k</i>, <i>n</i>, and <i>p</i>. Subcarrier index set <i>S</i> = {1,2,...,<i>N</i>} Subcarrier index set {(k,p)|<i>k</i> = 1,...,<i>K</i>,<i>p</i> = 1,...,<i>K,k</i> ≠ <i>p</i>}<i>.</i> Calculate initial penalties {P_n|<i>n</i> = 1,...,<i>N</i>} <i>Iteration</i> Repeat the following operations until S becomes the null set n̂ = <i>a</i>rg max_<i>m</i>S<i>P_n</i> (k̂,p̂) = arg min_(k.p)∈<i>_<u>U</u><u>g</u>_k</i>(<i>n̂</i>,<i>p</i>) Set δ<i>_k</i> (n̂, p̂) to one. δ_p̂(n̂, k̂) also becomes one due to δ<i>_k</i>(<i>n,p</i>) = δ<i>_p</i>(<i>n,k</i>), ∀<i>k,n,p</i>. Then S = S - {n̂} since <maths id="math0047" num=""><math display="inline"><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>K</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>p</mi><mo>=</mo><mn>1</mn><mo>,</mo><mi>p</mi><mo>≠</mo><mi>k</mi></mrow><mi>K</mi></munderover></mstyle><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi></mfenced><mo>=</mo><mn>2</mn><mo>,</mo></math><img file="EP1598975B1_D0047.tif" /></maths> ∀<i>n</i> is met. If <maths id="math0048" num=""><math display="inline"><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>p</mi><mo>=</mo><mn>1</mn><mo>,</mo><mi>p</mi><mo>≠</mo><mi>k</mi></mrow><mi>K</mi></munderover></mstyle><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi></mfenced><mo>=</mo><msub><mi>r</mi><mi>k</mi></msub><mo>,</mo></math><img file="EP1598975B1_D0048.tif" /></maths> ∀<i>k</i> is satisfied, then U = U - {(k̂,p̂) and update the penalties for the subcarriers whose indices are in the set S.

0074For each iteration of this algorithm, the size of the subcarrier index set S is reduced by one, due to the constraints of <maths id="math0049" num=""><math display="inline"><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>K</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>p</mi><mo>=</mo><mn>1</mn><mo>,</mo><mi>p</mi><mo>≠</mo><mi>k</mi></mrow><mi>K</mi></munderover></mstyle><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi></mfenced><mo>=</mo><mn>2</mn><mo>,</mo><mo>∀</mo><mi>n</mi></math><img file="EP1598975B1_D0049.tif" /></maths> and <i>δ_k</i>(<i>n</i>,<i>p</i>) <i>= δ_p</i> (<i>n, k</i>), ∀<i>k,n,p</i> in Equation (6). The user index set U is reduced and the penalty {<i>P_n</i>} is updated, whenever the constraint of <maths id="math0050" num=""><math display="inline"><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>p</mi><mo>=</mo><mn>1</mn><mo>,</mo><mi>p</mi><mo>≠</mo><mi>k</mi></mrow><mi>K</mi></munderover></mstyle><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi></mfenced><mo>=</mo><msub><mi>r</mi><mi>k</mi></msub><mo>,</mo></math><img file="EP1598975B1_D0050.tif" /></maths> ∀<i>k</i> in Equation (6) is satisfied for a certain <i>k</i>.

0075In summary, the subchannel allocation for the suboptimal approach in accordance with the present invention is as follows:

Heuristic

0076Step 1: Evaluate real-valued <maths id="math0051" num=""><math display="inline"><mrow><mo>{</mo></mrow><msubsup><mi>c</mi><mi>k</mi><mo>*</mo></msubsup><mfenced><mi>l</mi></mfenced></math><img file="EP1598975B1_D0051.tif" /></maths> from Equation (7) using the vector-form Newton's method.

0077Step 2: Substitute <maths id="math0052" num=""><math display="inline"><mrow><mo>{</mo></mrow><msubsup><mi>c</mi><mi>k</mi><mo>*</mo></msubsup><mfenced><mi>l</mi></mfenced></math><img file="EP1598975B1_D0052.tif" /></maths> for {<i>c_k</i>(<i>l</i>)} in Equation (6) and solve Equation (6) using the above-described modified Vogel's method to obtain {δ<i>_k</i>(<i>n</i>,<i>p</i>)}.

0078The overall heuristic algorithm for subchannel allocation requires <i>O</i>(<i>K</i>²) operations for one iteration of the vector-form Newton's method, and requires <i>O</i>(<i>NK</i>⁴) operations for the heuristic algorithm. This is a polynomial-time algorithm that can be applied to real-time multiuser-MIMO/OFDMA systems.

0079Except for the values of <maths id="math0053" num=""><math display="inline"><msub><mi>g</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi></mfenced><mo>=</mo><mfrac><mrow><msub><mi>f</mi><mi>k</mi></msub><mfenced><msub><mi>c</mi><mi>k</mi></msub></mfenced></mrow><mrow><msubsup><mi>α</mi><mi>k</mi><mn>2</mn></msubsup><mfenced><mi>n</mi><mi>p</mi></mfenced></mrow></mfrac></math><img file="EP1598975B1_D0053.tif" /></maths> and <maths id="math0054" num=""><math display="inline"><msub><mi>r</mi><mi>k</mi></msub><mo>=</mo><mfrac><msub><mi>R</mi><mi>k</mi></msub><msub><mi>c</mi><mi>k</mi></msub></mfrac><mo>,</mo></math><img file="EP1598975B1_D0054.tif" /></maths> the channel allocation method in the multiuser-MISO/OFDMA system is the same as the optimization method in Equation (6). Accordingly, the proposed heuristic algorithm can be applied to the multiuser-MISO/OFDMA system. <maths id="math0055" num="(10)"><math display="block"><mtable columnalign="left"><mtr><mtd><msub><mi>P</mi><mi>T</mi></msub><mo>=</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>K</mi></munderover></mstyle><msub><mi>g</mi><mi>k</mi></msub><mfenced><mi>n</mi></mfenced><mo>⋅</mo><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi></mfenced></mtd></mtr><mtr><mtd><mi>Constraints</mi><mo>:</mo></mtd></mtr><mtr><mtd><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi></mfenced><mo>∈</mo><mfenced open="{" close="}"><mn>0</mn><mn>1</mn></mfenced></mtd></mtr><mtr><mtd><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>K</mi></munderover></mstyle><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi></mfenced><mo>=</mo><mn>1</mn><mo>,</mo><mo>∀</mo><mi>n</mi></mtd></mtr><mtr><mtd><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover></mstyle><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi></mfenced><mo>=</mo><msub><mi>r</mi><mi>k</mi></msub><mo>,</mo><mo>∀</mo><mi>k</mi></mtd></mtr></mtable><mspace width="2em" /><mo>,</mo></math><img file="EP1598975B1_D0055.tif" /></maths> where <maths id="math0056" num=""><math display="inline"><msub><mi>g</mi><mi>k</mi></msub><mfenced><mi>n</mi></mfenced><mo>=</mo><msubsup><mi mathvariant="normal">Σ</mi><mrow><mi>l</mi><mo>=</mo><mn>1</mn></mrow><msub><mi>N</mi><mi>R</mi></msub></msubsup><mo>⁢</mo><mfrac><mrow><msub><mi>f</mi><mi>k</mi></msub><mfenced separators=""><msub><mi>c</mi><mi>k</mi></msub><mfenced><mi>l</mi></mfenced></mfenced></mrow><mrow><msubsup><mi>α</mi><mi>k</mi><mn>2</mn></msubsup><mfenced><mi>n</mi><mi>l</mi></mfenced></mrow></mfrac></math><img file="EP1598975B1_D0056.tif" /></maths> and <maths id="math0057" num=""><math display="inline"><msub><mi>r</mi><mi>k</mi></msub><mo>=</mo><mfrac><msub><mi>R</mi><mi>k</mi></msub><mrow><msubsup><mi mathvariant="normal">Σ</mi><mrow><mi>l</mi><mo>=</mo><mn>1</mn></mrow><msub><mi>N</mi><mi>R</mi></msub></msubsup><mo>⁢</mo><msub><mi>c</mi><mi>k</mi></msub><mfenced><mi>l</mi></mfenced></mrow></mfrac><mn>.</mn></math><img file="EP1598975B1_D0057.tif" /></maths> This is again an IP problem, but it is considerably simpler than the original IP in Equation (5).

0080Furthermore, we can find some suboptimal algorithms for this problem due to the following observation: <ul id="ul0002" list-style="none" compact="compact"><li>Observation 2: Suppose that {<i>c_k</i>(<i>l</i>)} are known. Then, {<i>f_k</i>(<i>c_k</i>(<i>l</i>))} become known and Equation (10) takes the form of a transportation problem that can be relaxed to linear programming (LP).</li></ul>

0081In Equation (10), <i>N</i> subcarriers are supplied to <i>K</i> users depending on the costs {<i>g_k</i>(<i>n</i>)}. δ<i>_k</i>(<i>n</i>) is the number of units shipped from the <i>n</i> -th subcarrier to the <i>k</i> -th user. The constraints of <maths id="math0058" num=""><math display="inline"><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>K</mi></munderover></mstyle><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi></mfenced><mo>=</mo><mn>1</mn><mo>,</mo></math><img file="EP1598975B1_D0058.tif" /></maths> ∀<i>n</i> and <maths id="math0059" num=""><math display="inline"><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover></mstyle><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi></mfenced><mo>=</mo><msub><mi>r</mi><mi>k</mi></msub><mo>,</mo></math><img file="EP1598975B1_D0059.tif" /></maths> ∀<i>k</i> in Equation (10) are the supply and demand constraints, respectively, of the transportation problem. As described above, a transportation problem can be solved by LP relaxation and Vogel's method.

0082Before solving the optimization problem in the first step, {<i>c_k</i>(<i>l</i>)} can be obtained during an initial phase.

0083Evaluation of {<i>c_k</i>(<i>l</i>)} requires the following assumption on the channel gain: <maths id="math0060" num=""><math display="block"><msubsup><mi>α</mi><mi>k</mi><mn>2</mn></msubsup><mfenced><mi>n</mi><mi>l</mi></mfenced><mo>=</mo><mrow><mo>{</mo></mrow><mtable columnalign="left"><mtr><mtd><msubsup><mi>α</mi><mi>k</mi><mn>2</mn></msubsup><mfenced><mi>l</mi></mfenced><mo>,</mo></mtd><mtd><mi mathvariant="italic">if</mi><mspace width="1em" /><msub><mi mathvariant="italic">δ</mi><mi>k</mi></msub><mfenced><mi>n</mi></mfenced><mo>=</mo><mn>1</mn></mtd></mtr><mtr><mtd><mn>0</mn><mo>,</mo></mtd><mtd><mi mathvariant="italic">otherwise</mi></mtd></mtr></mtable><mo>,</mo></math><img file="EP1598975B1_D0060.tif" /></maths> where <maths id="math0061" num=""><math display="inline"><msubsup><mi>α</mi><mi>k</mi><mn>2</mn></msubsup><mfenced><mi>l</mi></mfenced></math><img file="EP1598975B1_D0061.tif" /></maths> is the average of all subchannel gains associated with the <i>k</i> -th user and MIMO subchannel group <i>l</i>.

0084Under the above assumption, the optimization problem in Equation (10) can be simplified as shown in Equation (11). <maths id="math0062" num="(11)"><math display="block"><mtable columnalign="left"><mtr><mtd><msub><mi>P</mi><mi>T</mi></msub><mo>=</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>K</mi></munderover></mstyle><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>l</mi><mo>=</mo><mn>1</mn></mrow><msub><mi>N</mi><mi>R</mi></msub></munderover></mstyle><mfrac><mrow><msub><mi>f</mi><mi>k</mi></msub><mfenced separators=""><msub><mi>c</mi><mi>k</mi></msub><mfenced><mi>l</mi></mfenced></mfenced></mrow><mrow><msubsup><mi>α</mi><mi>k</mi><mn>2</mn></msubsup><mfenced><mi>l</mi></mfenced></mrow></mfrac><mo>⋅</mo><mfrac><msub><mi>R</mi><mi>k</mi></msub><mrow><mstyle displaystyle="false"><msubsup><mi mathvariant="normal">Σ</mi><mrow><mi>l</mi><mo>=</mo><mn>1</mn></mrow><msub><mi>N</mi><mi>R</mi></msub></msubsup></mstyle><msub><mi>c</mi><mi>k</mi></msub><mfenced><mi>l</mi></mfenced></mrow></mfrac></mtd></mtr><mtr><mtd><mi>Constraint</mi><mo>:</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi mathvariant="normal">k</mi><mo>=</mo><mn>1</mn></mrow><mi mathvariant="normal">K</mi></munderover></mstyle><mfrac><msub><mi>R</mi><mi>k</mi></msub><mrow><mstyle displaystyle="false"><msubsup><mi mathvariant="normal">Σ</mi><mrow><mi>l</mi><mo>=</mo><mn>1</mn></mrow><msub><mi>N</mi><mi>R</mi></msub></msubsup></mstyle><msub><mi>c</mi><mi>k</mi></msub><mfenced><mi>l</mi></mfenced></mrow></mfrac><mo>=</mo><mi>N</mi></mtd></mtr></mtable><mo>,</mo></math><img file="EP1598975B1_D0062.tif" /></maths> where <maths id="math0063" num=""><math display="inline"><msubsup><mi mathvariant="normal">Σ</mi><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></msubsup><mspace width="1em" /><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi></mfenced></math><img file="EP1598975B1_D0063.tif" /></maths> is replaced with <maths id="math0064" num=""><math display="inline"><mfrac><msub><mi>R</mi><mi>k</mi></msub><mrow><msubsup><mi mathvariant="normal">Σ</mi><mrow><mi>l</mi><mo>=</mo><mn>1</mn></mrow><msub><mi>N</mi><mi>R</mi></msub></msubsup><mo>⁢</mo><msub><mi>c</mi><mi>k</mi></msub><mfenced><mi>l</mi></mfenced></mrow></mfrac><mo>,</mo></math><img file="EP1598975B1_D0064.tif" /></maths> due to the constraint of <maths id="math0065" num=""><math display="inline"><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover></mstyle><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi></mfenced><mo>=</mo><msub><mi>r</mi><mi>k</mi></msub><mo>,</mo></math><img file="EP1598975B1_D0065.tif" /></maths> ∀<i>k</i> in Equation (10). Thereafter, the solution <maths id="math0066" num=""><math display="inline"><mrow><mo>{</mo></mrow><msubsup><mi>c</mi><mi>k</mi><mo>*</mo></msubsup><mfenced><mi>l</mi></mfenced></math><img file="EP1598975B1_D0066.tif" /></maths> of Equation (11) can be obtained by introducing a Lagrange multiplier µ and using a numerical technique, such as vector-form Newton's method.

0085Finally, the suboptimal approaches to the subchannel allocation in the single-user-MIMO/OFDMA system in accordance with the present invention are as follows:

Suboptimal LP

0086Step 1: Evaluate real-valued <maths id="math0067" num=""><math display="inline"><mrow><mo>{</mo></mrow><msubsup><mi>c</mi><mi>k</mi><mo>*</mo></msubsup><mfenced><mi>l</mi></mfenced></math><img file="EP1598975B1_D0067.tif" /></maths> from Equation (11) using the vector-form Newton's method.

0087Step 2: Substitute <maths id="math0068" num=""><math display="inline"><mrow><mo>{</mo></mrow><msubsup><mi>c</mi><mi>k</mi><mo>*</mo></msubsup><mfenced><mi>l</mi></mfenced></math><img file="EP1598975B1_D0068.tif" /></maths> for {<i>c_k</i>(<i>l</i>)} in Equation (10) and solve Equation (10) using LP after dropping the integer constraints from {<i>δ_k</i>(<i>n,p</i>)} in order to obtain {δ<i>_k</i>(<i>n</i>,<i>p</i>)}.

Heuristic

0088Step 1: Evaluate real-valued <maths id="math0069" num=""><math display="inline"><mrow><mo>{</mo></mrow><msubsup><mi>c</mi><mi>k</mi><mo>*</mo></msubsup><mfenced><mi>l</mi></mfenced></math><img file="EP1598975B1_D0069.tif" /></maths> from Equation (11) using the vector-form Newton's method.

0089Step 2: Substitute <maths id="math0070" num=""><math display="inline"><mrow><mo>{</mo></mrow><msubsup><mi>c</mi><mi>k</mi><mo>*</mo></msubsup><mfenced><mi>l</mi></mfenced></math><img file="EP1598975B1_D0070.tif" /></maths> for {<i>c_k</i>(<i>l</i>)} in Equation (10) and solve Equation (10) using Vogel's method to obtain {δ<i>_k</i>(<i>n</i>,<i>p</i>)}.

0090The computational load required by Vogel's method is <i>O</i>(<i>NK</i>²), while the computation load for LP is <i>O</i>(<i>N</i>⁴). Because usually <i>N</i> >> <i>K</i>, Vogel's method is considerably simpler to implement than LP.

0091The overall heuristic algorithm for subchannel allocation requires <i>O</i>(<i>K</i>²) operations for one iteration of the vector-form Newton's method, and requires <i>O</i>(<i>NK</i>²) operations for the heuristic algorithm. This is a polynomial-time algorithm that can be applied to real-time single-user-MIMO/OFDMA systems.

Bit Allocation

0092The bit allocation problem in the multiuser-MIMO/OFDMA system can be expressed as shown in Equation (12). <maths id="math0071" num="(12)"><math display="block"><mtable columnalign="left"><mtr><mtd><msub><mi>P</mi><mi>T</mi></msub><mo>=</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>K</mi></munderover></mstyle><mfenced open="[" close="]" separators=""><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>p</mi><mo>=</mo><mn>1</mn><mo>,</mo><mi>p</mi><mo>≠</mo><mi>k</mi></mrow><mi>K</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>l</mi><mo>=</mo><mn>1</mn></mrow><msub><mi>N</mi><mi>R</mi></msub></munderover></mstyle><mfrac><mrow><msub><mi>f</mi><mi>k</mi></msub><mfenced separators=""><msub><mi>c</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi></mfenced></mfenced></mrow><mrow><msubsup><mi>α</mi><mi>k</mi><mn>2</mn></msubsup><mfenced><mi>n</mi><mi>l</mi><mi>p</mi></mfenced></mrow></mfrac><mo>⋅</mo><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi></mfenced></mfenced></mtd></mtr><mtr><mtd><mi>Constraint</mi><mo>:</mo><msub><mi>R</mi><mi>k</mi></msub><mo>=</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover></mstyle><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>p</mi><mo>=</mo><mn>1</mn><mo>,</mo><mi>p</mi><mo>≠</mo><mi>k</mi></mrow><mi>K</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>l</mi><mo>=</mo><mn>1</mn></mrow><msub><mi>N</mi><mi>R</mi></msub></munderover></mstyle><msub><mi>c</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi></mfenced><mo>⋅</mo><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi></mfenced><mo>,</mo><mo>∀</mo><mi>k</mi></mtd></mtr></mtable><mo>,</mo></math><img file="EP1598975B1_D0071.tif" /></maths> where only {<i>c_k</i>(<i>n,l</i>)∈ {0,...,<i>C</i>}} are treated as variables since {<i>δ_k</i>(<i>n,p</i>)} are already determined through the subchannel allocation.

0093Equation (12) reveals that the bit allocation for each user can be independently performed. Under the constraint <maths id="math0072" num=""><math display="inline"><msub><mi>R</mi><mi>k</mi></msub><mo>=</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>p</mi><mo>=</mo><mn>1</mn><mo>,</mo><mi>p</mi><mo>≠</mo><mi>k</mi></mrow><mi>K</mi></munderover></mstyle><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>l</mi><mo>=</mo><mn>1</mn></mrow><msub><mi>N</mi><mi>R</mi></msub></munderover></mstyle><msub><mi>c</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi></mfenced><mo>⋅</mo><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi></mfenced><mo>,</mo><mo>∀</mo><mi>k</mi><mo>,</mo></math><img file="EP1598975B1_D0072.tif" /></maths><maths id="math0073" num=""><math display="inline"><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>K</mi></munderover></mstyle><mspace width="1em" /><mfenced open="[" close="]" separators=""><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>p</mi><mo>=</mo><mn>1</mn><mo>,</mo><mi>p</mi><mo>≠</mo><mi>k</mi></mrow><mi>K</mi></munderover></mstyle><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>l</mi><mo>=</mo><mn>1</mn></mrow><msub><mi>N</mi><mi>R</mi></msub></munderover></mstyle><mfrac><mrow><msub><mi>f</mi><mi>k</mi></msub><mfenced separators=""><msub><mi>c</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi></mfenced></mfenced></mrow><mrow><msubsup><mi>α</mi><mi>k</mi><mn>2</mn></msubsup><mfenced><mi>n</mi><mi>l</mi><mi>p</mi></mfenced></mrow></mfrac><mo>⋅</mo><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi></mfenced></mfenced></math><img file="EP1598975B1_D0073.tif" /></maths> for each <i>k</i> is minimized, and the total power <i>P_T</i> is eventually minimized. This fact indicates that the bit allocation for each user can be performed as in the case of single-user OFDM. Accordingly, it is possible to apply the greedy algorithm proposed for single-user OFDM.

0094Equations (13) and (14) are the bit allocation problems of multiuser-MISO/OFDMA and single-user-MIMO/OFDMA systems, respectively. <maths id="math0074" num="(13)"><math display="block"><mtable columnalign="left"><mtr><mtd><msub><mi>P</mi><mi>T</mi></msub><mo>=</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>K</mi></munderover></mstyle><mfenced open="[" close="]" separators=""><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>p</mi><mo>=</mo><mn>1</mn><mo>,</mo><mi>p</mi><mo>≠</mo><mi>k</mi></mrow><mi>K</mi></munderover></mstyle><mfrac><mrow><msub><mi>f</mi><mi>k</mi></msub><mfenced separators=""><msub><mi>c</mi><mi>k</mi></msub><mfenced><mi>n</mi></mfenced></mfenced></mrow><mrow><msubsup><mi>α</mi><mi>k</mi><mn>2</mn></msubsup><mfenced><mi>n</mi><mi>p</mi></mfenced></mrow></mfrac><mo>⋅</mo><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi></mfenced></mfenced></mtd></mtr><mtr><mtd><mi>Constraint</mi><mo>:</mo><msub><mi>R</mi><mi>k</mi></msub><mo>=</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover></mstyle><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>p</mi><mo>=</mo><mn>1</mn><mo>,</mo><mi>p</mi><mo>≠</mo><mi>k</mi></mrow><mi>K</mi></munderover></mstyle><msub><mi>c</mi><mi>k</mi></msub><mfenced><mi>n</mi></mfenced><mo>⋅</mo><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>p</mi></mfenced><mo>,</mo><mo>∀</mo><mi>k</mi></mtd></mtr></mtable></math><img file="EP1598975B1_D0074.tif" /></maths><maths id="math0075" num="(14)"><math display="block"><mtable columnalign="left"><mtr><mtd><msub><mi>P</mi><mi>T</mi></msub><mo>=</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>K</mi></munderover></mstyle><mfenced open="[" close="]" separators=""><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>l</mi><mo>=</mo><mn>1</mn></mrow><msub><mi>N</mi><mi>R</mi></msub></munderover></mstyle><mfrac><mrow><msub><mi>f</mi><mi>k</mi></msub><mfenced separators=""><msub><mi>c</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi></mfenced></mfenced></mrow><mrow><msubsup><mi>α</mi><mi>k</mi><mn>2</mn></msubsup><mfenced><mi>n</mi><mi>l</mi></mfenced></mrow></mfrac><mo>⋅</mo><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi></mfenced></mfenced></mtd></mtr><mtr><mtd><mi>Constraint</mi><mo>:</mo><msub><mi>R</mi><mi>k</mi></msub><mo>=</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover></mstyle><mspace width="1em" /><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>l</mi><mo>=</mo><mn>1</mn></mrow><msub><mi>N</mi><mi>R</mi></msub></munderover></mstyle><msub><mi>c</mi><mi>k</mi></msub><mfenced><mi>n</mi><mi>l</mi></mfenced><mo>⋅</mo><msub><mi>δ</mi><mi>k</mi></msub><mfenced><mi>n</mi></mfenced><mo>,</mo><mo>∀</mo><mi>k</mi></mtd></mtr></mtable></math><img file="EP1598975B1_D0075.tif" /></maths>

0095Like the case of the multiuser-MIMO/OFDMA system, Equations (13) and (14) are also solved using the greedy algorithm.

0096The bit allocation for multiuser-MIMO/OFDMA and multiuser-MISO/OFDMA systems requires <i>O</i>(<i>NK</i>²) operations, while the bit allocation for single-user-MIMO/OFDMA needs <i>O</i>(<i>NK</i>) operation.

0097The optimal IP and suboptimal algorithm were examined. For comparison, also considered were the random algorithm where subchannels were randomly allocated and bits were allocated by the greedy algorithm. Accordingly, the parameters were the same as those in Table 1.

0098For the multiuser-MIMO/OFDMA system, the simulation results were the average of 100 trials.

0099Table 6 shows the resulting transmission power for various {<i>R</i>₁,<i>R</i>₂,<i>R</i>₃,<i>R</i>₄} and γ ∈ {0,30} [<i>dB</i>]<i>.</i><tables id="tabl0006" num="0006"><table frame="all"><title>Table 6</title><tgroup cols="8"><colspec colnum="1" colname="col1" colwidth="14mm" /><colspec colnum="2" colname="col2" colwidth="14mm" /><colspec colnum="3" colname="col3" colwidth="14mm" /><colspec colnum="4" colname="col4" colwidth="14mm" /><colspec colnum="5" colname="col5" colwidth="14mm" /><colspec colnum="6" colname="col6" colwidth="26mm" /><colspec colnum="7" colname="col7" colwidth="24mm" /><colspec colnum="8" colname="col8" colwidth="24mm" /><thead><row><entry morerows="1" align="center" valign="top"><i>γ</i> (<i>dB</i>)</entry><entry namest="col2" nameend="col5" align="center" valign="top">Bits/OFDM symbol</entry><entry morerows="1" align="center" valign="top">Optimal IP (dB)</entry><entry morerows="1" align="center" valign="top">Heuristic (dB)</entry><entry morerows="1" align="center" valign="top">Random (dB)</entry></row><row><entry align="center" valign="top"><i>R</i>₁</entry><entry align="center" valign="top"><i>R</i>₂</entry><entry align="center" valign="top"><i>R</i>₃</entry><entry align="center" valign="top"><i>R</i>₄</entry></row></thead><tbody><row><entry morerows="2" align="center">0</entry><entry align="center">256</entry><entry align="center">256</entry><entry align="center">256</entry><entry align="center">256</entry><entry align="char" char="." charoff="14">39.93</entry><entry align="char" char="." charoff="15">40.24</entry><entry align="char" char="." charoff="16">42.93</entry></row><row><entry align="center">128</entry><entry align="center">128</entry><entry align="center">384</entry><entry align="center">384</entry><entry align="char" char="." charoff="14">40.38</entry><entry align="char" char="." charoff="15">40.93</entry><entry align="char" char="." charoff="16">43.10</entry></row><row><entry align="center">64</entry><entry align="center">64</entry><entry align="center">448</entry><entry align="center">448</entry><entry align="char" char="." charoff="14">41.03</entry><entry align="char" char="." charoff="15">41.56</entry><entry align="char" char="." charoff="16">43.31</entry></row><row><entry morerows="2" align="center">30</entry><entry align="center">256</entry><entry align="center">256</entry><entry align="center">256</entry><entry align="center">256</entry><entry align="char" char="." charoff="14">55.92</entry><entry align="char" char="." charoff="15">57.86</entry><entry align="char" char="." charoff="16">62.41</entry></row><row><entry align="center">128</entry><entry align="center">128</entry><entry align="center">384</entry><entry align="center">384</entry><entry align="char" char="." charoff="14">50.74</entry><entry align="char" char="." charoff="15">52.20</entry><entry align="char" char="." charoff="16">57.08</entry></row><row><entry align="center">64</entry><entry align="center">64</entry><entry align="center">448</entry><entry align="center">448</entry><entry align="char" char="." charoff="14">46.71</entry><entry align="char" char="." charoff="15">48.01</entry><entry align="char" char="." charoff="16">53.31</entry></row></tbody></tgroup></table></tables>

0100As expected, the optimal IP yielded the minimum <i>P_T</i> for all cases. The <i>P_T</i> values from the suboptimal algorithm were reasonably close to the minimum values. The performance gap between the optimal IP and the suboptimal algorithm did not exceed 0.55 dB, when γ = 0 <i>dB</i> , and 1.94 dB, when γ = 30 <i>dB</i> . The random algorithm was worse than the others. That is, the maximum additionally required power was 3.00 dB, when <i>γ</i> = 0 <i>dB</i>, and 6.60 dB, when γ = 30 <i>dB.</i>

0101To further examine the performance degradation of the algorithms against the optimal IP, additional experiments with the optimal IP were performed for various {<i>R</i>₁,<i>R</i>₂,<i>R</i>₃,<i>R</i>₄}.

0102Table 7 describes the data rates obtained by the additionally required power of the heuristic and random algorithms with respect to the optimal IP. <tables id="tabl0007" num="0007"><table frame="all"><title>Table 7</title><tgroup cols="6"><colspec colnum="1" colname="col1" colwidth="14mm" /><colspec colnum="2" colname="col2" colwidth="14mm" /><colspec colnum="3" colname="col3" colwidth="14mm" /><colspec colnum="4" colname="col4" colwidth="14mm" /><colspec colnum="5" colname="col5" colwidth="14mm" /><colspec colnum="6" colname="col6" colwidth="26mm" /><thead><row><entry morerows="1" align="center" valign="top"><i>γ</i> (<i>dB</i>)</entry><entry namest="col2" nameend="col5" align="center" valign="top">Bits/OFDM symbol</entry><entry morerows="1" align="center" valign="top">Optimal IP (dB)</entry></row><row><entry align="center" valign="top"><i>R</i>₁</entry><entry align="center" valign="top"><i>R</i>₂</entry><entry align="center" valign="top"><i>R</i>₃</entry><entry align="center" valign="top"><i>R</i>₄</entry></row></thead><tbody><row rowsep="0"><entry morerows="8" rowsep="1" align="center">0</entry><entry align="center">256</entry><entry align="center">256</entry><entry align="center">256</entry><entry align="center">256</entry><entry align="char" char="." charoff="14">39.93</entry></row><row rowsep="0"><entry align="center">262</entry><entry align="center">262</entry><entry align="center">262</entry><entry align="center">262</entry><entry align="char" char="." charoff="14">40.24</entry></row><row><entry align="center">316</entry><entry align="center">316</entry><entry align="center">316</entry><entry align="center">316</entry><entry align="char" char="." charoff="14">42.93</entry></row><row rowsep="0"><entry align="center">128</entry><entry align="center">128</entry><entry align="center">384</entry><entry align="center">384</entry><entry align="char" char="." charoff="14">40.38</entry></row><row rowsep="0"><entry align="center">140</entry><entry align="center">140</entry><entry align="center">396</entry><entry align="center">396</entry><entry align="char" char="." charoff="14">40.93</entry></row><row><entry align="center">186</entry><entry align="center">186</entry><entry align="center">442</entry><entry align="center">442</entry><entry align="char" char="." charoff="14">43.10</entry></row><row rowsep="0"><entry align="center">64</entry><entry align="center">64</entry><entry align="center">448</entry><entry align="center">448</entry><entry align="char" char="." charoff="14">41.03</entry></row><row rowsep="0"><entry align="center">76</entry><entry align="center">76</entry><entry align="center">460</entry><entry align="center">460</entry><entry align="char" char="." charoff="14">41.56</entry></row><row><entry align="center">116</entry><entry align="center">116</entry><entry align="center">500</entry><entry align="center">500</entry><entry align="char" char="." charoff="14">43.31</entry></row><row rowsep="0"><entry morerows="8" rowsep="1" align="center">30</entry><entry align="center">256</entry><entry align="center">256</entry><entry align="center">256</entry><entry align="center">256</entry><entry align="char" char="." charoff="14">55.92</entry></row><row rowsep="0"><entry align="center">306</entry><entry align="center">306</entry><entry align="center">306</entry><entry align="center">306</entry><entry align="char" char="." charoff="14">57.86</entry></row><row><entry align="center">424</entry><entry align="center">424</entry><entry align="center">424</entry><entry align="center">424</entry><entry align="char" char="." charoff="14">62.41</entry></row><row rowsep="0"><entry align="center">128</entry><entry align="center">128</entry><entry align="center">384</entry><entry align="center">384</entry><entry align="char" char="." charoff="14">50.74</entry></row><row rowsep="0"><entry align="center">150</entry><entry align="center">150</entry><entry align="center">406</entry><entry align="center">406</entry><entry align="char" char="." charoff="14">52.20</entry></row><row><entry align="center">246</entry><entry align="center">246</entry><entry align="center">502</entry><entry align="center">502</entry><entry align="char" char="." charoff="14">57.08</entry></row><row rowsep="0"><entry align="center">64</entry><entry align="center">64</entry><entry align="center">448</entry><entry align="center">448</entry><entry align="char" char="." charoff="14">46.71</entry></row><row rowsep="0"><entry align="center">78</entry><entry align="center">78</entry><entry align="center">464</entry><entry align="center">464</entry><entry align="char" char="." charoff="14">48.01</entry></row><row><entry align="center">148</entry><entry align="center">148</entry><entry align="center">532</entry><entry align="center">532</entry><entry align="char" char="." charoff="14">53.31</entry></row></tbody></tgroup></table></tables>

0103For example, when γ = 0 <i>dB</i>, 40.24 dB, which was needed for {256,256,256,256} using the heuristic algorithm in Table 6, achieved {262,262,262,262} with the optimal IP. The performance degradation of the heuristic algorithm was less than 12 bits/OFDM symbol per user, when γ = 0 <i>dB</i>, and was less than 50 bits/OFDM symbol per user, when γ = 30 <i>dB</i>. In the case of random algorithm, the maximum loss was 60 bits/OFDM symbol per user, when γ = 0 <i>dB</i>, and 128 bits/OFDM symbol per user, when γ = 30 <i>dB</i>.

0104As indicated above, the simulation results for the multiuser-MISO/OFDMA systems were the average of 100 trials.

0105Table 8 shows the resulting transmission power <i>P_T</i> for various {<i>R</i>₁, <i>R</i>₂, <i>R</i>₃, <i>R</i>₄} and γ ∈ {0,30} [<i>dB</i>]<i>.</i><tables id="tabl0008" num="0008"><table frame="all"><title>Table 8</title><tgroup cols="8"><colspec colnum="1" colname="col1" colwidth="14mm" /><colspec colnum="2" colname="col2" colwidth="14mm" /><colspec colnum="3" colname="col3" colwidth="14mm" /><colspec colnum="4" colname="col4" colwidth="14mm" /><colspec colnum="5" colname="col5" colwidth="14mm" /><colspec colnum="6" colname="col6" colwidth="26mm" /><colspec colnum="7" colname="col7" colwidth="24mm" /><colspec colnum="8" colname="col8" colwidth="24mm" /><thead><row><entry morerows="1" align="center" valign="top"><i>γ</i> (<i>dB</i>)</entry><entry namest="col2" nameend="col5" align="center" valign="top">Bits/OFDM symbol</entry><entry morerows="1" align="center" valign="top">Optimal IP (dB)</entry><entry morerows="1" align="center" valign="top">Heuristic (dB)</entry><entry morerows="1" align="center" valign="top">Random (dB)</entry></row><row><entry align="center" valign="top"><i>R</i>₁</entry><entry align="center" valign="top"><i>R</i>₂</entry><entry align="center" valign="top"><i>R</i>₃</entry><entry align="center" valign="top"><i>R</i>₄</entry></row></thead><tbody><row><entry morerows="2" align="center">0</entry><entry align="center">128</entry><entry align="center">128</entry><entry align="center">128</entry><entry align="center">128</entry><entry align="char" char="." charoff="14">38.28</entry><entry align="char" char="." charoff="15">38.84</entry><entry align="char" char="." charoff="16">42.71</entry></row><row><entry align="center">64</entry><entry align="center">64</entry><entry align="center">192</entry><entry align="center">192</entry><entry align="char" char="." charoff="14">38.93</entry><entry align="char" char="." charoff="15">39.92</entry><entry align="char" char="." charoff="16">42.86</entry></row><row><entry align="center">32</entry><entry align="center">32</entry><entry align="center">224</entry><entry align="center">224</entry><entry align="char" char="." charoff="14">39.87</entry><entry align="char" char="." charoff="15">40.83</entry><entry align="char" char="." charoff="16">43.18</entry></row><row><entry morerows="2" align="center">30</entry><entry align="center">128</entry><entry align="center">128</entry><entry align="center">128</entry><entry align="center">128</entry><entry align="char" char="." charoff="14">55.15</entry><entry align="char" char="." charoff="15">56.70</entry><entry align="char" char="." charoff="16">62.02</entry></row><row><entry align="center">64</entry><entry align="center">64</entry><entry align="center">192</entry><entry align="center">192</entry><entry align="char" char="." charoff="14">50.12</entry><entry align="char" char="." charoff="15">51.67</entry><entry align="char" char="." charoff="16">57.02</entry></row><row><entry align="center">32</entry><entry align="center">32</entry><entry align="center">224</entry><entry align="center">224</entry><entry align="char" char="." charoff="14">46.40</entry><entry align="char" char="." charoff="15">47.74</entry><entry align="char" char="." charoff="16">53.48</entry></row></tbody></tgroup></table></tables>

0106As expected, the optimal IP showed the minimum <i>P_T</i> for all cases. The <i>P_T</i> values from the suboptimal algorithm were reasonably close to the minimum values. The performance gap between the optimal IP and the suboptimal algorithm was less than 0.99 dB, when γ = 0 <i>dB</i>, and 1.55 dB, when γ = 30 <i>dB</i>. The random algorithm was worse than the others. That is, the maximum additionally required power was 3.93 dB, when γ = 0 <i>dB</i>, and 7.08 dB, when γ = 30 <i>dB</i>.

0107For the single-user-MIMO/OFDMA system, the simulation results were the average of 20 trials.

0108The resulting transmission power <i>P_T</i> is shown in Table 9. <tables id="tabl0009" num="0009"><table frame="all"><title>Table 9</title><tgroup cols="9"><colspec colnum="1" colname="col1" colwidth="14mm" /><colspec colnum="2" colname="col2" colwidth="14mm" /><colspec colnum="3" colname="col3" colwidth="14mm" /><colspec colnum="4" colname="col4" colwidth="14mm" /><colspec colnum="5" colname="col5" colwidth="14mm" /><colspec colnum="6" colname="col6" colwidth="24mm" /><colspec colnum="7" colname="col7" colwidth="25mm" /><colspec colnum="8" colname="col8" colwidth="24mm" /><colspec colnum="9" colname="col9" colwidth="24mm" /><thead><row><entry morerows="1" align="center" valign="top"><i>γ</i> (<i>dB</i>)</entry><entry namest="col2" nameend="col5" align="center" valign="top">Bits/OFDM symbol</entry><entry morerows="1" align="center" valign="top">Optimal IP (dB)</entry><entry morerows="1" align="center" valign="top">Suboptimal LP (dB)</entry><entry morerows="1" align="center" valign="top">Heuristic (dB)</entry><entry morerows="1" align="center" valign="top">Random (dB)</entry></row><row><entry align="center" valign="top"><i>R</i>₁</entry><entry align="center" valign="top"><i>R₂</i></entry><entry align="center" valign="top"><i>R₃</i></entry><entry align="center" valign="top"><i>R₄</i></entry></row></thead><tbody><row><entry morerows="2" align="center">0</entry><entry align="center">128</entry><entry align="center">128</entry><entry align="center">128</entry><entry align="center">128</entry><entry align="char" char=".">37.05</entry><entry align="char" char=".">37.24</entry><entry align="char" char="." charoff="15">37.30</entry><entry align="char" char="." charoff="16">40.57</entry></row><row><entry align="center">64</entry><entry align="center">64</entry><entry align="center">192</entry><entry align="center">192</entry><entry align="char" char=".">37.24</entry><entry align="char" char=".">37.46</entry><entry align="char" char="." charoff="15">37.56</entry><entry align="char" char="." charoff="16">41.06</entry></row><row><entry align="center">32</entry><entry align="center">32</entry><entry align="center">224</entry><entry align="center">224</entry><entry align="char" char=".">37.56</entry><entry align="char" char=".">37.80</entry><entry align="char" char="." charoff="15">37.84</entry><entry align="char" char="." charoff="16">40.82</entry></row><row><entry morerows="2" align="center">30</entry><entry align="center">128</entry><entry align="center">128</entry><entry align="center">128</entry><entry align="center">128</entry><entry align="char" char=".">52.52</entry><entry align="char" char=".">53.11</entry><entry align="char" char="." charoff="15">53.41</entry><entry align="char" char="." charoff="16">55.95</entry></row><row><entry align="center">64</entry><entry align="center">64</entry><entry align="center">192</entry><entry align="center">192</entry><entry align="char" char=".">47.42</entry><entry align="char" char=".">47.49</entry><entry align="char" char="." charoff="15">48.43</entry><entry align="char" char="." charoff="16">52.59</entry></row><row><entry align="center">32</entry><entry align="center">32</entry><entry align="center">224</entry><entry align="center">224</entry><entry align="char" char=".">43.36</entry><entry align="char" char=".">43.70</entry><entry align="char" char="." charoff="15">44.29</entry><entry align="char" char="." charoff="16">49.79</entry></row></tbody></tgroup></table></tables>

0109In Table 9, the optimal IP yielded the minimum <i>P_T</i> for all cases. The <i>P_T</i> values from the suboptimal algorithms were reasonably close to the minimum values. The performance gap between the optimal IP and the suboptimal LP algorithm did not exceed 0.24 dB, when γ = 0 <i>dB</i>, and did not exceed 0.59 dB, when γ = 30 <i>dB</i>. In the case of the heuristic algorithm, the gap was less than 0.32 dB, when γ = 0 <i>dB</i>, and was less than 0.01 dB, when γ = 30 <i>dB</i>. The random algorithm was worse than the others. That is, the maximum additionally required power was 3.82 dB, when γ = 0 <i>dB</i>, and 6.43 dB, when <i>γ</i> = 30 <i>dB.</i>

0110To compare the performance of the above three systems, additional simulations were performed when all systems has the same number of subchannels. The parameters were shown in Table 10 and the heuristic algorithm was applied. <tables id="tabl0010" num="0010"><table frame="all"><title>Table 10</title><tgroup cols="4"><colspec colnum="1" colname="col1" colwidth="37mm" /><colspec colnum="2" colname="col2" colwidth="42mm" /><colspec colnum="3" colname="col3" colwidth="43mm" /><colspec colnum="4" colname="col4" colwidth="45mm" /><thead><row><entry align="center" valign="top" /><entry align="center" valign="top">Multiuser-MIMO/OFDMA</entry><entry align="center" valign="top">Multiuser-MISO/OFDMA</entry><entry align="center" valign="top">Single-user-MIMO/OFDMA</entry></row></thead><tbody><row><entry align="center">N_T</entry><entry align="center">4</entry><entry align="center">4</entry><entry align="center">4</entry></row><row><entry align="center">N_R</entry><entry align="center">2</entry><entry align="center">1</entry><entry align="center">4</entry></row><row><entry align="center">M</entry><entry align="center">2</entry><entry align="center">4</entry><entry align="center">1</entry></row><row><entry align="center"># of FFT(N)</entry><entry align="center">64</entry><entry align="center">64</entry><entry align="center">64</entry></row><row><entry align="center">Total # of subchannels</entry><entry align="center">256</entry><entry align="center">256</entry><entry align="center">256</entry></row><row><entry align="center"># of users (K)</entry><entry namest="col2" nameend="col4" align="center">4</entry></row><row><entry align="center"># of max. bits (C)</entry><entry namest="col2" nameend="col4" align="center">12</entry></row><row><entry align="center">Required BER</entry><entry namest="col2" nameend="col4" align="center">10⁴</entry></row><row><entry align="center">Channel</entry><entry namest="col2" nameend="col4" align="left">8-tap frequency selective Rayleigh fading channels with exponentially decaying power profiles were assumed. The channel parameters were fixed during one frame period. The average channel magnitudes of the different users were generally unequal and the difference, denoted by γ , between the strongest and weakest channels of the four users was either zero or 30 dB.</entry></row></tbody></tgroup></table></tables>

0111In Table 10, the simulation results were the average of 100 trials.

0112Table 11 shows the resulting transmission power <i>P_T</i> for various {<i>R</i>₁, <i>R</i>₂ ,<i>R</i>₃, <i>R</i>₄} and γ ∈ {0,30} [<i>dB</i>]<i>.</i><tables id="tabl0011" num="0011"><table frame="all"><title>Table 11</title><tgroup cols="8"><colspec colnum="1" colname="col1" colwidth="14mm" /><colspec colnum="2" colname="col2" colwidth="14mm" /><colspec colnum="3" colname="col3" colwidth="14mm" /><colspec colnum="4" colname="col4" colwidth="14mm" /><colspec colnum="5" colname="col5" colwidth="14mm" /><colspec colnum="6" colname="col6" colwidth="32mm" /><colspec colnum="7" colname="col7" colwidth="33mm" /><colspec colnum="8" colname="col8" colwidth="32mm" /><thead><row><entry rowsep="0" align="center" valign="top"><i>γ</i> (<i>dB</i>)</entry><entry namest="col2" nameend="col5" align="center" valign="top">Bits/OFDM symbol</entry><entry rowsep="0" align="center" valign="top">Multiuser-MIMO/OFDMA (dB)</entry><entry rowsep="0" align="center" valign="top">Multiuser-MISO/OFDMA (dB)</entry><entry rowsep="0" align="center" valign="top">Single-user-MIMO/OFDMA (dB)</entry></row><row><entry valign="top" /><entry align="center" valign="top"><i>R</i>₁</entry><entry align="center" valign="top"><i>R</i>₂</entry><entry align="center" valign="top"><i>R</i>₃</entry><entry align="center" valign="top"><i>R</i>₄</entry><entry valign="top" /><entry valign="top" /><entry valign="top" /></row></thead><tbody><row><entry morerows="2" align="center">0</entry><entry align="center">256</entry><entry align="center">256</entry><entry align="center">256</entry><entry align="center">256</entry><entry align="char" char=".">40.28</entry><entry align="char" char=".">44.93</entry><entry align="char" char=".">38.52</entry></row><row><entry align="center">128</entry><entry align="center">128</entry><entry align="center">384</entry><entry align="center">384</entry><entry align="char" char=".">41.06</entry><entry align="char" char=".">48.41</entry><entry align="char" char=".">38.79</entry></row><row><entry align="center">64</entry><entry align="center">64</entry><entry align="center">448</entry><entry align="center">448</entry><entry align="char" char=".">41.70</entry><entry align="char" char=".">51.29</entry><entry align="char" char=".">38.90</entry></row><row><entry morerows="2" align="center">30</entry><entry align="center">256</entry><entry align="center">256</entry><entry align="center">256</entry><entry align="center">256</entry><entry align="char" char=".">57.88</entry><entry align="char" char=".">64.46</entry><entry align="char" char=".">54.26</entry></row><row><entry align="center">128</entry><entry align="center">128</entry><entry align="center">384</entry><entry align="center">384</entry><entry align="char" char=".">52.35</entry><entry align="char" char=".">57.22</entry><entry align="char" char=".">49.29</entry></row><row><entry align="center">64</entry><entry align="center">64</entry><entry align="center">448</entry><entry align="center">448</entry><entry align="char" char=".">48.09</entry><entry align="char" char=".">53.53</entry><entry align="char" char=".">45.68</entry></row></tbody></tgroup></table></tables>

0113As shown in Table 11, the single-user-MIMO/OFDMA, which has the maximum number of receiver antennas, yielded the minimum <i>P_T</i> and the multiuser-MISO/OFDMA, which has the minimum number of receiver antennas, yielded the maximum <i>P_T</i>. The performance gap between the single-user-MIMO/OFDMA and the multiuser-MIMO/OFDMA did not exceed 2.8 dB, when γ = 0 <i>dB</i>, and did not exceed 3.62 dB, when γ = 30 <i>dB</i>. The multiuser-MISO/OFDMA was worse than the others. That is, the maximum additionally required power was 12.39 dB, when γ = 0 <i>dB</i>, and 10.20 dB, when <i>γ</i> = 30 <i>dB.</i>

0114<figref idref="f0003">FIG. 3</figref> is a flow chart illustrating a subchannel and bit allocation method in accordance with the present invention. As illustrated in <figref idref="f0003">FIG. 3</figref>, the subchannel and bit allocation method computes channel gain and transmission rate information using feedback information from terminals in Step S301, and computes an average channel gain according to a computed channel gain for each user in Step S302. When the average channel gain for each user has been determined, the average number of bits to be allocated to a corresponding user is determined in Step S303. The number of subchannels to be allocated to each user is determined in Step S304. Subchannels are allocated to each user according to the determined number of subchannels in Step S305.

0115After the subchannels are allocated to each user, a modulation scheme is determined on a channel-by-channel basis in Step S306.

0116As is apparent from the description above, the subchannel and bit allocation method for multiuser-MIMO/OFDMA systems (including its special systems) in accordance with the present invention can optimize subchannel and bit allocation using IP. Further, the subchannel and bit allocation method in accordance with the present invention can obtain the performance close to that of the optimal IP algorithm using an efficient suboptimal algorithm for separately performing a subchannel and bit allocation process.

0117Additionally, the subchannel and bit allocation method in accordance with the present invention can considerably improve frequency use efficiency as well as a power gain by adaptively allocating subchannels and bits according to channel environments, as compared with a system using a fixed modulation scheme.

0118While the present invention has been shown and described with reference to certain preferred embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the scope of the present invention as defmed by the appended claims.