The following detailed description is provided to assist the reader in gaining a comprehensive understanding of the various apparatuses and methods described herein. Accordingly, various changes, modifications, and equivalents of the apparatuses and methods described herein will be suggested to those of ordinary skill in the art. A method of allocating resources which can improve throughput by minimizing interference between cells or interference within cells when a plurality of relay nodes are installed is described below. In particular, an OFDMA scheme has been introduced in a next generation mobile communication system and a method of allocating resources considering the OFDMA is described below. Also, fairness for users is considered in view of resource allocation.

FIG. 1 is a diagram illustrating an exemplary Orthogonal Frequency Division Multiple Access (OFDMA) system. Referring to FIG. 1, the exemplary OFDMA system includes a base station 110; at least one relay station 121, 122, and 123; and at least one terminal 131, 132, 133, 134, and 135. It is assumed that there exists M number of the at least one relay station 121, 122, and 123 and K number of the at least one terminal 131, 132, 133, 134, and 135 in the exemplary OFDMA system. A total number of links, where subchannels can be allocated, are M(1+K)+K since K links exist between the base station 110 and the at least one terminal 131, 132, 133, 134, and 135; M links exist between the base station 110 and the at least one relay station 121, 122, and 123; and MK links exist between the at least one relay station 121, 122, and 123 and the at least one terminal 131, 132, 133, 134, and 135. A subchannel is respectively allocated to each of the links. Before the apparatus for allocating subchannels allocates the subchannels to the links, the apparatus determines a subchannel allocation coefficient using a queue length of the at least one terminal 131, 132, 133, 134, and 135 and a signal to interference plus noise ratio (SINR) of the at least one relay station 121, 122, and 123 and the at least one terminal 131, 132, 133, 134, and 135.

For example, the base station 110 and the at least one relay station 121, 122, and 123 may store the queue length information of the at least one terminal 131, 132, 133, 134, and 135. Accordingly, the apparatus for allocating subchannels may continuously update the queue length information of the at least one terminal 131, 132, 133, 134, and 135 by obtaining the queue length information of the at least one terminal 131, 132, 133, 134, and 135 from the base station and the at least one relay station 121, 122, and 123.

In another example, the apparatus for allocating subchannels may obtain SINR information from the at least one relay station 121, 122, and 123 and the at least one terminal 131, 132, 133, 134, and 135. In addition, the apparatus for allocating subchannels may be included in the base station 110. The base station 110 may also have the queue length information and the SINR information.

In another example, the apparatus for allocating subchannels may determine the subchannel allocation coefficient for each of the M(1+K)+K number of links based on all subchannels, where the subchannel allocation coefficient is proportional to the queue length, and a data rate is calculated using the SINR. In this example, the data rate may be calculated using:

[Equation 1]

where β is a received SINR value, and W indicates a bandwidth.

A subchannel allocation coefficient corresponding to an nth subchannel in a link formed between the base station and the terminal may be represented by:

[Equation 2]

where n indicates an nth subchannel, 0 indicates a base station, and k indicates a kth terminal. indicates a data rate between the base station and the kth terminal in the nth subchannel, and indicates a queue length of the kth terminal between the base station and the kth terminal.

A subchannel allocation coefficient corresponding to the nth subchannel in the link formed between the base station and the relay station, may be represented by:

[Equation 3]

where n indicates an nth subchannel, 0 indicates a base station, m indicates an mth relay station, and k indicates a kth terminal. indicates a data rate of an mth relay station between the base station and the mth relay station in the nth subchannel, and indicates a queue length which is calculated by deducting a queue length of the kth terminal between the mth relay station and the kth terminal from a queue length of the kth terminal between the base station and the kth terminal. If a queue length is a negative number, a subchannel allocation coefficient between the base station and the mth relay station is zero.

In a link formed between the relay station and the terminal, a subchannel allocation coefficient corresponding to the nth subchannel may be represented by:

[Equation 4]

where n indicates an nth subchannel, m indicates an mth relay station, and k indicates a kth terminal. indicates a data rate of the kth terminal between the mth relay station and the kth terminal in nth subchannel, and indicates a queue length of the kth terminal between the mth relay station and the kth terminal.

The apparatus for allocating subchannels may allocate subchannels to links formed in the OFDMA system once the subchannel allocation coefficient is determined using Equations 1 through 4.

The apparatus for allocating subchannels may also allocate a subchannel to each of the at least one link so that a total sum of the subchannel allocation coefficients is a maximum when subchannels are allocated to the at least one link, which may be represented by:

[Equation 5]

where and are indicator variables and have features as described below:

[Equation 6]

.

Referring to Equation 5, a single subchannel is allocated to each of the links in the OFDMA system; however, a total sum of subchannel allocation coefficients that changes depending on a subchannel in each link are compared, and a combination of a subchannel and a link whose total sum is a maximum, is determined. Since a number of links in the OFDMA system in this example is M(1+K)+K, when a number of a subchannel is N, a number of cases that subchannels may be allocated to a link is . Therefore, the apparatus for allocating subchannels may allocate a subchannel to a link to satisfy Equation 5 by comparing the combination of the subchannel and the link as many times as . Also, the apparatus for allocating subchannels may allocate a subchannel to a link using another method instead of the above described method. For example, an apparatus for allocating subchannels may select a link whose subchannel allocation coefficient (which may be calculated for each link) is a maximum, from among K links formed between the base station 110 and the at least one terminal (e.g., 131, 132, 133, 134, and 135) and an M link formed between the base station 110 and the at least one relay station (e.g., 121, 122, and 123). In this example, the at least one relay station 121, 122, and 123 selects a link whose subchannel allocation coefficient is a maximum, from among the K links formed between the at least one relay station 121, 122, and 123 and the at least one terminal 131, 132, 133, 134, and 135. Consequently, the apparatus for allocating subchannels may allocate a subchannel to a link using the selected links.

An operation to select a link whose subchannel allocation coefficient (which may be calculated for each link) is a maximum, from among the K links between the base station 110 and the at least one terminal (e.g., 131, 132, 133, 134, and 135) and the M links between the base station 110 and the at least one relay station (e.g., 121, 122, and 123), may be represented by:

[Equation 7]

→ .

An operation to select a link whose subchannel allocation coefficient is a maximum, from among the K links formed between the at least one relay station (e.g., 121, 122, 123) and the at least one terminal (e.g., 131, 132, 133, 134, and 135), may be represented by:

[Equation 8]

As described above, an exemplary list of selected links and subchannels is illustrated in Table I 210 of FIG. 2. Hereinafter, examples of allocating a subchannel to a link will be described with reference to FIG. 2.

FIG. 2 is a table illustrating an exemplary list of subchannels that may be allocated. Referring to Table I 210, the first column listing "n ₁ through n _N " _{represents a plurality of subchannels; the second column, labeled "BS," represents a base station 110; and the remaining columns, labeled R 1 through R M , each represent at least one relay station 121, 122, and 123. Also, D NM represents a subchannel allocation coefficient. Subchannel allocation coefficients of links selected according to Equation 7 are shown in the column labeled "BS" and subchannel allocation coefficients of links selected according to Equation 8 are shown for each column labeled R 1 to an R M .}

In one implementation, An apparatus for allocating subchannels may allocate a subchannel to a link so that a total sum of subchannel allocation coefficients of links, where a subchannel is allocated, is a maximum from among links selected using Equations 7 and 8. Referring to Table I 210, since a single subchannel is allocated to each link formed in the OFDMA system, a single link may be selected for each subchannel in the columns. Therefore, under this condition, links are selected so that a total sum of subchannel allocation coefficients of the selected links is a maximum, consequently a corresponding subchannel is allocated to the selected link.

FIG. 3 is a diagram illustrating an exemplary apparatus 310 for allocating subchannels. Referring to FIG. 3, the apparatus 310 for allocating subchannels may include a subchannel allocation coefficient determination unit 311 and a subchannel allocation unit 312.  The subchannel allocation coefficient determination unit 311 determines a subchannel allocation coefficient using a queue length of at least one terminal existing in an OFDMA system and an SINR of the at least one terminal and at least one relay station. The subchannel allocation coefficient determination unit 311 may determine the subchannel allocation coefficient, the subchannel allocation coefficient is proportional to the queue length and a data rate is calculated using the SINR. That is, using Equations 1 through 4, the subchannel allocation coefficient may be determined.

The subchannel allocation unit 312 allocates a subchannel to at least one single link formed in the OFDMA system using the subchannel allocation coefficient determined in the subchannel allocation coefficient determination unit 311. The subchannel allocation unit 312 may allocate the subchannel to the at least one link so that a total sum of subchannel allocation coefficients of links, where subchannel is allocated, using Equations 5 and 6. The subchannel allocation unit 312 may select, for each subchannel, a link whose subchannel allocation coefficient is a maximum from among links formed between the base station 110 and the at least one terminal. In this example, the relay station may select, for each subchannel, a link whose subchannel allocation coefficient is a maximum from links formed between the relay station and the at least one terminal, using Equation 8. The subchannel allocation unit 312 may also allocate the subchannel to a link using the selected links so that a total sum of subchannel allocation coefficients of links, where the subchannel is allocated, is a maximum. The apparatus 310 for allocating subchannels may be included in the base station.  FIG. 4 is a diagram illustrating an apparatus 410 for controlling interference. Referring to FIG. 4, the apparatus 410 for controlling interference, at least one node 421, 422, 423, and 424, and a radio network controller 430 are illustrated. The apparatus may include, for example, an interference information receiving unit 411, a determination unit 412, an interference list creating unit 413, and reporting unit 414. In addition, the apparatus for controlling interference may be included in a base station.

The interference information receiving unit 411 receives, from at least one node 421, 422, 423, and 424, interference information regarding at least one subchannel which is allocated to at least one node 421, 422, 423, and 424. The at least one node 421, 422, 423, and 424 may generate a predetermined number of interference information for each subchannel, which is allocated to each node, set in an order of greatest interference power, and may transmit the interference information to the apparatus 410 for controlling interference. As an example, when a predetermined number is six, the at least one node 421, 422, 423, and 424 may generate six pieces of interference information for each subchannel in an order of greatest interference power, and may transmit the generated six pieces of interference information to the apparatus 410 for controlling interference.

The determination unit 412 determines whether a data rate of the at least one node 421, 422, 423, and 424 is greater than a threshold. The at least one node 421, 422, 423, and 424 may be at least one terminal distributed in the OFDMA system. For example, the determination unit 412 may determine the threshold by estimating a total sum of actual data rates of the at least one terminal 421, 422, 423, and 424 in a present frame using an actual data rate of the at least one terminal from a previous frame, which is described in detail below.

A total sum of actual data rates of the at least one terminal 421, 422, 423, and 424 in a previous frame is calculated using a total sum of an actual data rate from the previous frame of the at least one terminal 421, 422, 423, and 424 as below:

[Equation 9]

.

In this example, it is assumed that a number of the at least one terminal is K.

By using the total sum of data rates of the at least one terminal 421, 422, 423, and 424 in the previous frame which is calculated via Equation 9, the total sum of data rates of the at least one terminal 421, 422, 423, and 424 in a present frame may be estimated via Equation 10 as below:

[Equation 10]

where 0 < W < 1.

By using the total sum of data rates of the at least one terminal 421, 422, 423, and 424 in the present frame which is estimate via Equation 10, an average cumulative virtual data rate may be obtained, which may be calculated via Equation 11 as below:

[Equation 11]

.

Also, a cumulative actual data rate of a kth terminal from among the at least one terminal 421, 422, 423, and 424 may be represented by:

[Equation 12]

.

The determination unit 412 may determine whether the cumulative actual data rate of the kth terminal, which can be calculated via Equation 12, is greater than a threshold by having the average cumulative virtual data rate which can be calculated via Equation 11 to be the threshold. Equation 13 below shows whether a cumulative actual data rate is greater than the threshold is determined by having 95 % of an average cumulative virtual data rate of the terminal to be the threshold.

[Equation 13]

A threshold which is to be compared with the data rate of the t th terminal may be determined by deducting from each of left and right terms in Equation 13, which may be represented by:

[Equation 14]

.

Consequently, referring to Equation 14, the threshold determined in the determination unit 412 is .

In the above example, it has been assumed that the at least one node 421, 422, 423, and 424 is a terminal, however it is possible that the at least one node 421, 422, 423, and 424 may be the at least one relay station existing in the OFDMA system. For example, the determination unit 412 may determine whether a total sum of data rates of first hops of the at least one relay station 421, 422, 423, and 424 is greater than a threshold. Also, the determination unit 412 may determine a total sum of data rates of second hops of the at least one relay station 421, 422, 423, and 424.

The interference list creating unit 413 creates an interference list using an interference list received in the interference information receiving unit 411 once the determination unit 412 has determined the data rate of the at least one node 421, 422, 423, and 424 is not greater than the threshold. The interference list creating unit 413 may limit the interference of each subchannel, allocated to each node of the at least one node 421, 422, 423, and 424, in an order of greatest interference power, and may determine whether the data rates of the at least one node 421, 422, 423, and 424 is greater than the threshold. When the data rates of the at least one node 421, 422, 423, and 424 are greater than the threshold, the interference list creating unit 413 creates the interference list using the interference information about the limited interference. As an example, it is assumed the interference information receiving unit 411 receives six pieces of interference information for each subchannel from the kth terminal where three subchannels are allocated, and each piece of interference information is In ₁ , In ₂ , In ₃ , In ₄ , In ₅ , In ₆ . (n: subchannel, interference power: In ₁ >In ₂ >In ₃ >In ₄ >In ₅ >In ₆ ). As a result that the interference list creating unit 413 limits the interference for each subchannel in an order of greatest interference power, when a data rate of the kth terminal is greater than the threshold since I ₁₁ and I ₁₂ are limited in the first subchannel, when the data rate of the kth terminal is greater than the threshold since I ₂₁ is limited in the second terminal, and when the data rate of the kth terminal is greater than the threshold since I ₃₁ is limited in the third terminal, the interference list creating unit 413 creates an interference list for each subchannel using I ₁₁ , I ₁₂ , I ₂₁ , and I ₃₁ .

The reporting unit 414 transmits the interference list created in the interference list creating unit 413 to the radio network controller 430. The interference list creating unit 413 may limit the interference in the order of greatest interference power, and the reporting unit 414 may transmit that the interference list created by determining whether a data rate at the time of the limiting is greater than the threshold and the data rate value to the radio network controller 430.

The radio network controller 430 creates, using the interference list received from the apparatus for controlling interference, a base station list and a relay station list to limit data transmission for each subchannel, allocated to the OFDMA system, and also transmits the base station list and relay station list to at least one base station in the OFDMA system.

When the radio network controller 430 receives the interference list and the data rate from the apparatus for controlling interference, and the base station list and the relay station list to limit data transmission using the received interference list and the data rate are created so that all data rates in the OFDMA system become a maximum for each subchannel allocated to the OFDMA system, the interference list and the data rate being created by limiting the interference in the order of greatest interference power. This may be described by Equation 15.

[Equation 15]

Equation 15 represents selecting a base station and a relay station to limit data transmission for each subchannel allocated to the OFDMA system. R _i indicates a data rate which can be obtained in an ith cell in the case that a base station and a relay station in a jth cell are limited; x is an indicator to determine whether to limit signal transmission of a base station or a relay station in each cell. When x = 1, signal transmission is not limited, and when x = 0, signal transmission is limited.

Hereinafter, the operations of the radio network controller 430 according to Equation 15 will be described by taking an example of a case of an nth subchannel. It is assumed , the radio network controller 430 receives a data rate when interference is limited and the interference list from the apparatus for controlling interference is in the first cell; the received data rate and the received interference list are analyzed when signal transmission of the base station is limited or when the relay station in the second cell and the third cell is limited; and an estimated data transmission rate in the first cell is R ₁ . It is also assumed that the radio network controller 430 receives a data rate when interference is limited and the interference list from the apparatus for controlling interference is in the second cell; that the received data rate and the received interference list are analyzed when signal transmission of the base station or the relay station in the first cell is limited; and an estimated data transmission rate in the second cell is R ₂ . It is also assumed that the radio network controller 430 receives a data rate when interference is limited and the interference list from the apparatus for controlling interference is in the third cell; the received data rate and the received interference list are analyzed when signal transmission of either the base station or the relay station is in the first cell is limited; and an estimated data transmission rate in the third cell is R ₃ . This may be represented by:

[Equation 16]

.

The radio network controller 430 selects a base station or a relay station to limit data transmission for each subchannel from among base stations and relay stations in the OFDMA system by obtaining x ₁ , x ₂ , and x ₃ satisfying Equation 16, thereby creating an interference list. For example, if Z in Equation 16 is a maximum when x ₁ =0, x ₂ =1, x ₃ =1 are satisfied, the radio network controller 430 has a base station or a relay station in the first cell; either the a base station list or a relay station list may limit data transmission; and the radio network controller 430 may transmit the base station list or the relay station list to a plurality of base stations in the OFDMA system.

FIG. 5 is a flowchart illustrating exemplary operations of an exemplary apparatus for controlling interference. Referring to FIG. 5, a radio network controller 510, an apparatus for controlling interference 520, and at least one node 530 are illustrated. In 541, the at least one node 530 generates interference information for at least one subchannel, allocated to the at least one node 530.

For example, the at least one node 530 may generate a predetermined number of interference information for each subchannel, set in an order of greatest interference power. In operation 542, the generated interference information is transmitted to the apparatus 520 for controlling interference. In operation 543, the apparatus 520 for controlling interference determines whether a data rate of the at least one node 530 is greater than a threshold. For example, the at least one node 530 may be a terminal and determining whether a data rate of the at least one terminal 530 is greater than the threshold may be determined using Equations 9 through 14.

Also, as an example, the at least one node 530 may be a relay station and a total sum of data rates of a first hop of the at least one relay station 530 is greater than total sum of data rates of a second hop of the at least one relay station 530 may be determined.

In operation 544, as a result of the determination in operation 543, when the data rate of the at least one node 530 is not greater than the threshold, the apparatus 520 for controlling interference creates an interference list using the interference information. In operation 545, the interference list created in the operation 544 is transmitted to the radio network controller 510. The apparatus 520 for controlling the interference limits the interference of each subchannel, allocated to the at least one node 530, in the order of greatest interference power, and determines whether the data rates of the at least one node 530 is greater than the threshold, and, when the data rates of the at least one node 530 is greater than the threshold, creates the interference list using the interference information about the limited interference, consequently may transmit the data rate which can be obtained by limiting the interference, and the interference list to the radio network controller 510. In operation 546, by using the interference list received by the radio network controller 510 in operation 545, a base station list and a relay station list to limit data transmission for each subchannel, allocated to the OFDMA system, are created from among at least one base station and relay station in the OFDMA system.

As an example, the radio network controller 510, via Equation 15, may create the base station list and relay station list to limit data transmission so that a total sum of data rates for each subchannel in the OFDMA system is a maximum. In operation 547, the base station list and the relay station list created in operation 546 is transmitted to at least one base station in the OFDMA system.

FIG. 6 is a flowchart illustrating an exemplary method of allocating subchannels. In operation 610, a subchannel allocation coefficient is determined using a queue length of at least one terminal in the OFDMA system and an SINR of the at least one terminal and at least one relay station in the OFDMA system. In one implementation, the subchannel allocation coefficient may be determined using Equations 1 through 4.

In operation 620, a total sum of subchannel allocation coefficients of links, where a subchannel is allocated, is compared. In operation 630, whether the total sum of subchannel allocation coefficients is the maximum is determined as a result of the comparison in operation 620. In one implementation, operation 630 may be determined via Equations 5 through 6. As a result of the determination in operation 630, when the total sum of the subchannel allocation coefficients are not the maximums, operation flow returns to operation 620, and the comparison operation is repeated until a total sum of subchannel allocation coefficients is a maximum. As a result of the determination in operation 630, when a combination of a subchannel and a link whose total sum of subchannel allocation coefficients is a maximum is determined, a subchannel is allocated to a link to generate such combination in operation 640.

FIG. 7 is a flowchart illustrating an exemplary method of allocating subchannels. In operation 710, a total sum of subchannel allocation coefficients of links where subchannel is allocated is compared. In operation 720, a link whose subchannel allocation coefficient is a maximum is selected for each subchannel, from among links between a base station and a terminal and between the base station and a relay station.

In one implementation, operation 720 may be selected using Equation 7. In operation 730, a link whose subchannel allocation coefficient is a maximum is selected for each subchannel, from among links between the relay station and the terminal. In one implementation, operation 730 may be selected via Equation 8. In operation 740, a subchannel is allocated to a link using links selected in operations 720 and 730 so that a total sum of subchannel allocation coefficients is a maximum.

FIG. 8 is flowchart illustrating an exemplary method of controlling interference.

In operation 810, interference information is received from at least one node in the OFDMA system. In one implementation, a predetermined number of the at least one node is generated in an order of greatest interference power, and the interference information may be transmitted. In operation 820, a data rate of the at least one node is compared with a threshold. In operation 830, whether the data rate of the at least one node is greater than the threshold is determined. In one implementation, the at least one node may be at least one terminal, and determining whether a data rate of at least one terminal is greater than the threshold is calculated using Equations 10 through 14.

In another example, the at least one node may be at least one relay station, and it may be determined whether a total sum of data rates of first hop of the at least one relay station is greater than the threshold. As a result of the determination in operation 830, when the data rate of the at least one node is greater than the threshold, the operation is terminated. However, as a result of the determination in operation 830, when the data rate of the at least one node is not greater than the threshold, interference is limited for each subchannel; allocated to the at least one node in an order of greatest interference power; and the data rate of the at least one node is compared with the threshold in operation 840.

In operation 850, whether the data rate of the at least one node which can be obtained by limiting the interference is greater than the threshold is determined. As a result of the determination in operation 850, when the data rate of the at least one node which can be obtained by limiting the interference is not greater than the threshold, operation 840 is repeated. However, as a result of the determination in operation 850, when the data rate of the at least one node which can be obtained by limiting the interference is greater than the threshold, an interference list is created using the interference information about the limited interference in operation 860. In operation 870, the interference list created in operation 860 and the data rate of the at least one node which can be obtained by limiting the interference are transmitted to a radio network controller.

For example, the radio network controller may create a base station list and a relay station list for each subchannel allocated to the OFDMA system via Equation 15, using the interference list and data rate transmitted from operation 870 and the controller may transmit the base station list and relay station list to at least one base station.

The method of allocating subchannels and for controlling interference in an OFDMA system as described above may be recorded in computer-readable media including program instructions to cause a processor to implement or carry out various operations embodied by a computer to form a specific machine or apparatus. A non-exhaustive list of examples of media may include, alone or in combination with the program instructions, at least data files, data structures, and the like. A non-exhaustive list of examples of computer-readable media may include magnetic media such as hard disks, floppy disks, and magnetic tape; optical media such as CD ROM disks and DVD; magneto-optical media such as optical disks; and hardware devices that are specially configured to store and perform program instructions, such as read-only memory (ROM), random access memory (RAM), flash memory, and the like. A non-exhaustive list of examples of program instructions may include both steps, procedures, instructions embodied in machine code, such as produced by a compiler, and files containing higher level code that may be executed by the computer using an interpreter or other programming. Such hardware devices may be configured to act as one or more software modules in order to perform the exemplary method described above.

A number of exemplary embodiments have been described above. Nevertheless, it will be understood that various modifications may be made. For example, suitable results may be achieved if the described techniques are performed in a different order and/or if components in a described system, architecture, device, or circuit are combined in a different manner and/or replaced or supplemented by other components or their equivalents. Accordingly, other implementations are within the scope of the following claims.