FORM -2
THE PATENTS ACT, 1970 (39 of 1970) & THE PATENTS RULES, 2003
PROVISIONAL
Specification
(See Section 10 and rule 13)


ORTHOGONAL FREQUENCY DIVISION MULTIPLE ACCESS
(OFDMA) SYSTEMS
TATA CONSULTANCY SERVICES LTD.,
an Indian Company of Nirmal Building, 9th floor, Nariman Point, Mumbai 400 021, Maharashtra, India
THE FOLLOWING SPECIFICATION DESCRIBES THE INVENTION



Field of the Invention:
This invention relates to Orthogonal Frequency Division Multiple Access (OFDMA) systems.
In particular, this invention envisages a novel way of providing long term Quality of Service (QoS) guarantee by dynamic subcarrier allocation in OFDMA systems.
Still particularly, this invention relates to development of a dynamic OFDMA subcarrier allocation system optimized to simultaneously maintain fairness and overall average long term data rate, which follows and converges to the QoS related minimum data rate of individual users in wireless dynamic OFDMA systems.
Background of the Invention:
The purpose of subcarrier allocation at the base station of dynamic OFDMA systems is to intelligently allocate the limited number of subcarriers among users to meet users' service requirements or QoS. Channel-aware subcarrier allocation achieves higher system performance than static subcarrier allocation due to its adaptive nature of aligning with the changes of wireless channel. OFDMA also referred to as Multi-user OFDM is characterized by a fixed number of orthogonal subcarriers to be allocated to the users. Due to the diversity of wireless mobile systems in frequency, time, and space, the OFDMA subcarriers can be allocated to the user in order to increase spectral efficiency and achieve user QoS requirement. The randomness of individual channel
2

fading leads to Multi-User Diversity (MUD). Assigning mutually disjoint subcarriers to the users by taking the advantage of MUD with apriori knowledge of channel condition to meet the individual QoS requirement in heterogeneous traffic condition is a challenging task. Due to the highly dynamic nature of mobile wireless channel, instantaneous QoS satisfaction guarantee for every user is very difficult, if not impossible. With the ever increasing demand of high data rate and tight QoS constraint of OFDMA-based next generation broadband wireless networks, the requirement of a dynamic subcarrier allocation scheme to meet the QoS of each user with a notion of fairness and system performance optimization is very important. Basically by principal, a well designed communication system should take the available degrees of freedom of the channel as much as possible. Advantages due to MUD in frequency domain is a research for quite some time. Wireless channel is normally very much dynamic in nature and over long duration, time diversity gain becomes high at fast fading. The present invention provides a framework in this direction by exploiting the time-diversity gain to optimize the system performance.
Summary of the Invention:
In accordance with this invention, a novel Long-Term Proportional Fair (LTPF) subcarrier allocation system in a dynamic OFDMA system is envisaged, adapted to provide a long term QoS guarantee to individual users and further adapted to follow every user's QoS profile in the long term by incremental optimization of proportional fairness and overall system rate maximization.
3

Experiments have been conducted with the system on a Matlab simulator and the results have confirmed the effectiveness and efficiency of the system of the invention.
Far development of the dynamic subcarrier allocation scheme in OFDMA systems, some assumptions are made regarding the network and system. The QoS is considered as minimum mean data rate requirement, which is a valid assumption for delay-tolerant applications. QoS guarantee to individual user is assumed in long term average basis and the average is computed over few frame duration, which is equal to the maximum latency can be sustained by the applications running in the current system. Constant Bit Error Rate (BER) and fixed QoS are considered within the period of averaging. Frequency Re-use factor of 1 is considered, so that all the subcarriers are available to be assigned to the users. By QoS profile, the plot of each user's minimum data rate requirement is implied. However, unlike most of the current OFDMA subcarrier frameworks, this invention does not assume homogeneity in QoS requirement. A heterogeneous traffic model, with diversified QoS demand by the users is considered. This is a very realistic assumption in the current and next generation broadband wireless networks.
The invention involves a novel dynamic OFDMA subcarrier allocation system which provides guaranteed convergence to QoS profile for individual user within fixed time duration in a diversified heterogeneous traffic condition. Rather than maintaining individual user's instantaneous QoS; importance is given to follow the Q0S profile of each of the users within fixed time duration, which is equal to the length of few frames. This system retains both the objective of proportional fairness and multi-user raw rate maximization. In
4

contrast to the systems which provide proportional fair optimization and raw-rate maximization independently, the proposed system provides both kinds of optimizations simultaneously and reaches an optimum point when computed in long-term. This novel system is named 'Long Term Proportional Fair' (LTPF) QoS Follower Sub-carrier Allocation System.
The invention consists of three steps of OFDMA subcarrier allocation which are invoked sequentially. These steps are: (1) Initialize subcarrier allocation to the users at the start of the allocation process, (2) Comparison of achievable mean data rate due to the subcarrier allocation with the QoS parameter of minimum data rate requirement, (3) Assign subcarrier allocation to provide mean data rate converges to the QoS parameter.
In the initialization of subcarrier allocation to the users at the start of the allocation process, proportional fairness among the users is maintained in order to fulfill the data rate requirement in a reasonable way. The initialization phase is mainly based on preserving a balance between two mutually exclusive interests of wireless system optimization; viz., maximization of overall system throughput and fairness among the users. The advantages of MUD only contribute to a small portion of mobile users whose channel quality is good, which may not lead to a significant QoS performance improvement from entire network perspective. Proportional fair is considered to be a simple yet effective fairness notion and it is pure outcome fairness metric. Assignment of initial subcarriers to the users is based on the philosophy of simultaneously providing system throughput maximization as well fairness in optimum way. This is achieved by assigning the subcarriers following the scheme of maximizing the ratio of instantaneous channel condition to the already achievable data rate.
5

Comparison of achievable mean data rate due to the subcarrier allocation with the QoS parameter of minimum data rate requirement is done to avoid unnecessary subcarrier allocation to the user than its requirement. This is an important step of long term optimization, where instead of instantaneous data rate value of the user, mean data rate, computed up to that allocation cycle is taken in to account, which introduces time diversity gain, not possible in instantaneous data rate and QoS comparison.
The objective of assigning subcarrier allocation in the subsequent allocation cycles up to the fixed length, called the long term duration, is to converge the mean achieved data rate very close to QoS parameter, i.e., to follow the QoS profile of the system. This is a novel idea for optimizing OFDMA system performance by which the achievable data rate is converged to the QoS requirement of the user. This is done by defining the proportional fairness metric as a maximization of the ratio of instantaneous channel condition to the achieved mean data rate up to the time instant of computation. Users with mean data rate less than its required QoS value are only allowed to participate in the scheme of optimization, others are ignored. This idea of optimization in LTPF makes the subcarrier allocation scheme follow the QoS profile of the system within defined long term duration, as with the progression of time cycles, ergodicity and time diversity gain are achieved.
The invention is evaluated in a Matlab simulator for the purpose of evaluation of its performance. The metrics that are used for evaluating performance are: (1) Achieved mean data rate by the users at long term, (2) Achieved instantaneous data rate of the users at each allocation cycle and (3) Comparison of users'
6

achieved mean data rate by LTPF system and the QoS dependent minimum data rate requirement.
It is observed that the individual achievable mean data rate very closely follows the QoS profile in the long term, where as in the short term users' achievable data rate deviates appreciably from the QoS profile. With the progression of more time cycles, individual achievable mean data rate converges to the QoS requirement, a steady mean throughput for each user is achieved as well as the overall system performance is increased.
It is also observed that more the number of time cycles more is the probability that individual mean data rate converges to the minimum data rate requirement. But the long term duration, which is basically a few OFDMA frames, is bound to a constraint to allow the most demanding applications. But that does not degrade the performance of the system, as after some frame duration the achievable mean data rate reaches an optimum point, which confirms that inclusion of more time cycles or allocation instants does not fetch significant improvement in the performance.
Brief Description of the Accompanying Drawings:
The invention will now be described with reference to the accompanying drawings, in which
Figure 1 shows the Multiuser Dynamic OFDMA system architecture with LTPF system in accordance with this invention ;
7

Figure 2 shows details of the Comparison of data rate achievable for the users and QoS related minimum data rate requirement when 1 frame-duration is taken as long term duration;
Figure 3 shows: User achievable data rate at each frame-duration or allocation instants when long term duration is equal to 1 frame-duration;
Figure 4 shows the Cumulative Distribution Function of the users' achievable rate when 1 frame-duration is taken as the long term duration;
Figure 5 shows the Comparison of data rate achievable for the users and QoS related minimum data rate requirement when 2 frame-durations is taken as long term duration;
Figure 6 shows the User achievable data rate at each frame-duration or allocation instants when long term is equal to 2 frame-durations;
Figure 7 shows the Comparison of data rate achievable for the users and QoS related minimum data rate requirement when 6 frame-durations is taken as long term duration;
Figure 8 shows the User achievable data rate at each frame-duration or allocation instants when long term duration is equal to 6 frame-durations;
Figure 9 shows the Comparison of data rate achievable for the users and QoS related minimum data rate requirement when 10 frame-durations is taken as long term duration;
8

Figure 10 shows the User achievable data rate at each frame-duration or allocation instants when long term duration is equal to 10 frame-durations;
Figure 11 shows the Cumulative Distribution Function of the users' achievable rate when long term duration is equal to 10 frame durations;
Figure 12 shows the Comparison of data rate achievable for the users and QoS related minimum data rate requirement when 20 frame-durations is taken as long term duration; and
Figure 13 is a Table showing Simulation Parameters.
Detailed Description of Invention:
The invention discloses a subcarrier allocation system that optimizes the performance of dynamic OFDMA systems. The system is named as 'Long Term Proportional Fair1 (LTPF) subcarrier allocation system. The LTPF subcarrier allocation system dynamically allocates OFDMA subcarriers to the users in such a way that in long term the individual user's QoS requirement is achieved as well as fairness among the users is maintained even in heterogeneous traffic conditions. Here, rather than maintaining individual user's instantaneous QoS, emphasis is given to follow QoS profile of all the users in long term to retain the objectives of both proportional fairness and multi-user raw rate maximization. In contrast to the systems which provide proportional fair optimization and raw-rate maximization independently, LTPF system carries out both kinds of optimizations, viz. fairness and raw rate maximization simultaneously, and reaches an optimum point when computed in long term. It provides long term
9

QoS guarantee (mainly throughput requirement satisfaction) to individual users and follows individual user's QoS profile in long term by incremental optimization of proportional fairness and overall system rate maximization.
OFDMA subcarrier allocation systems assign mutually disjoint sub-carriers to the users mostly with the purpose of meeting the individual QoS requirement by dynamically allocating the OFDMA subcarriers in channel-aware way. The optimization goal of the system is either to attain maximum aggregate throughput or to provide fairness among the users. The objectives of fair optimization and overall system throughput maximization are very much opposite in nature. Providing fairness is basically a Min-max problem. However by providing fairness, system performance is compromised, although most of the users get satisfied. In contrast sum-rate maximization assures enhanced system performance, while some of the users get dissatisfied. To overcome the problem of mutual exclusivity of fairness and system performance, LTPF system, instead of achieving instantaneous fairness or capacity maximization, provides both fairness and capacity maximization in long term by intelligently allocating the mutually disjoint OFDMA subcarriers dynamically to meet individual user's QoS or at least the overall QoS profile in an average term. It is very much difficult and computationally expensive to satisfy each user's instantaneous data rate requirement. User satisfaction and the interests of the service providers both can be preserved if individual user's QoS is maintained. The performance of most of the current and next generation wireless broadband network applications do not degrade much if mean QoS guarantee is provided, where the mean is computed over few frame durations. From this perspective, LTPF system is proposed which instead of achieving instantaneous fairness or capacity maximization, allocates the OFDMA subcarriers to the users to meet its
10

minimum mean data-rate requirement within few frame duration or at least follows the overall QoS profile in long term. By this way, it overcomes the problem of mutual exclusivity of fairness and system performance. Here, by QoS profile only the user's minimum data-rate requirement is taken into consideration. The heterogeneity of the traffic, which consists of variable data rate requirement, is also assumed. As QoS guarantee to the user is the most priority objective for next generation wireless broadband systems, the LTPF system is very much pertinent and effective.
The Multiuser OFDMA system architecture with Resource allocation module is shown in Fig. 1. A wireless cellular network is assumed, but only a single cell with one base station (BS) serving total K users is considered and the interference from adjacent cells is treated as background noise. The invention considers following system parameter definitions and assumptions:
1. Total available Bandwidth: B
2. Total number of users: K and total number of OFDMA subcarriers = N and frequency reuse factor equals to 1.
3. The sub-carriers are: Ώ1, Ώ.2 -.-.ΏN, whereΏ n = B/N and Ώn< Bc, Bc = Coherence Bandwidth of the channel.
4. Total available Transmitter Power = PT. Pkn is the transmit power for nth
subcarrier when transmitted to kth user.
5. Channel Gain for subcarrier n for user k at tr allocation instant =
6. Allocation Duration =Δ , where Δ ad = MxTf\ M = 1, 2 ..., Tf= frame-duration and is taken as the unit allocation duration. = Coherence
11

time of the channel and Aad >> rc, when the system is implemented for long term computation. LTPF is unique in this sense that, more with the value of Aad, optimization approaches to theoretical limit of least probability of error as per Bernoulli's Law of Large Numbers, which justifies the intuitive interpretation that the expected value of a random variable is basically long term average when sampled repeatedly. The condition Tf> rc condition fetches more optimization. In other words, Δ ad
should be as large as possible to extract the most out of LTPF.
7. Achievable rate for kth user at tth instant =

where pkm - 1 if nth subcarrier assigned to kth user at tth time instant, else equals to 0,

where Nt is the total noise psd and SNR_gap =

8. Minimum individual rate requirement for K users = where yk is constant over
9. Proportional Fairness index at tth allocation instant
12

10.Total achievable data rate for k^ user at the end of allocation duration and total achievable system data rate/ capacity at Aad is

The invention is an optimized OFDMA sub-carrier allocation scheme, which instead of instantaneous optimization, allocates OFDMA sub-carriers to optimize the performance over few allocations and assures QoS guarantee in an average basis within that pre-defined allocation duration. The idea is formulated below:

Equations (1-4) describes LTPF optimization scheme. It can be noticed that more the value of M, the more ergodic the optimization scheme becomes; at M=l, the optimization is purely proportional fair. It can also be noted that more time diversity gain would be achieved with the increasing value of M, i.e.
(5)
Basically LTPF incurs the advantage of time diversity (TD) gain, when QoS parameter computation time (Δ ad) is more than the channel coherence time.
The invention discloses a novel system, hereinafter referred to as the Long Term Proportional Fair (LTPF) Subcarrier Allocation System. LTPF algorithm as proposed below carries out long term maximization of user's mean achievable data rate subject to minimum data rate constraint:
13



2. Assign initial subcarriers to the users from proportional fairness index, at t = 0
while ) do
fork=l:K

end while
3. Incorporate long term notion and time diversity gain
fort =
while
fork=l:K
if
calculate
14


fc I — wk I

end for
The invention, which is basically a novel subcarrier allocation scheme in dynamic OFDMA systems, involves the following three steps.
In the initialization of subcarrier allocation to the users at the start of the allocation process proportional fairness criteria is maintained in order to fulfill the data rate requirement of the users in a reasonable way. The initialization phase is mainly based upon maintaining a balance between two mutually exclusive interests of wireless system optimization. One is trying to maximize overall system throughput while the other attempts to offer fairness among the users by compromising on the system throughput. Assignment of initial subcarriers to the users is based on the philosophy of simultaneously providing system throughput maximization as well fairness in an optimum way. This is achieved by assigning the subcarriers following the scheme of maximizing the ratio of instantaneous channel condition to the already achievable data rate.
15

Comparison of achievable mean data rate due to the subcarrier allocation with the QoS parameter of minimum mean data rate requirement is done to avoid unnecessary more subcarrier allocation to the user than its requirement. This is an important step of long term optimization, where instead of instantaneous data rate value of the user, mean data rate, computed up to that allocation cycle is taken in to account, which introduces time diversity gain, not possible in instantaneous data rate and QoS comparison.
The objective of assigning subcarrier allocation in the subsequent allocation cycles up to the fixed length, called the long term duration is to attempt mean achieved data rate to get very close to QoS parameter or in other word, to follow the QoS profile of the system. This is a novel idea of optimization of system performance by which the achievable data rate is converged to the QoS requirement of the user. This is done by defining the proportional fairness metric as a maximization of the ratio of instantaneous channel condition to the already achieved mean data rate up to the time instant of computation. Users with mean data rate less than its required QoS value are only allowed to participate in the scheme of optimization else will be ignored. This idea of optimization in LTPF makes the subcarrier allocation scheme follow the QoS profile of the system within defined long term duration, as with the progression of time cycles, ergodicity and time diversity gain are achieved.
On the basis of simulation parameters depicted in Figure 13 as Table 1, experiments are conducted to test the effectiveness of the system. Figure 2 shows the comparison of data rate achievable for the users and QoS related minimum data rate requirement when 1 frame-duration is taken in the computation of mean value. It shows that very less data rate is achieved when
16

only 1 frame-duration is taken into account for computing the QoS parameter of minimum required data rate. The data rate achieved also does not follow the QoS parameter. The duration of 1 frame is considered as short term duration. The absence of ergodicity and time diversity gain is the cause of this kind of characteristics of achievable data rate. Fig. 3 depicts the corresponding achievable data rate at each frame-duration or allocation, while Fig. 4 shows the corresponding Cumulative Distribution Function (CDF) of the achievable data rate. Fig. 5 depicts the comparison of data rate achievable for the users and QoS related minimum data rate requirement when 2 frame-durations is taken as long term duration. It shows some improvement of achievable data rate as well as the QoS following characteristics as some kind of long term notion is incorporated. Fig. 6 shows the corresponding achievable data rate at each frame-duration or allocation instants. Fig. 7 depicts the comparison of data rate achievable for the users and QoS related minimum data rate requirement when 6 frame-durations is taken as long term duration. It shows considerable enhancement of achievable data rate and QoS follower characteristics. Fig. 8 shows corresponding achievable data rate at each frame-duration or allocation instants. Fig. 9 depicts comparison of mean achievable data rate for the users and QoS related minimum data rate requirement when 10 frame-durations is taken as long term duration. It unambiguously supports the claim of QoS following characteristics of LTPF system. Fig. 10 shows the corresponding achievable data rate at each frame-duration or allocation instants, while CDF of the achievable rate is shown in Fig. 11. The claim is clearly supported by Fig. 12, where comparison of data rate achievable and QoS related minimum data rate requirement when 20 frame-durations is taken as long term duration. Fig. 12 clearly shows the convergence of mean data rate achieved by the users to their QoS data rate requirement. Thus,
17

from the experiments conducted the effectiveness of LTPF system is observed and establishes the claim of long term QoS follower characteristics.
Although the invention has been described in terms of particular embodiments and applications, one of ordinary skill in the art, in light of this teaching, can generate additional embodiments and modifications without departing from the spirit of or exceeding the scope of the claimed invention. Accordingly, it is to be understood that the drawings and descriptions herein are proffered by way of example to facilitate comprehension of the invention and should not be construed to limit the scope thereof.
18
Dated this 25th day of September, 2008.