CHAPTER: 1
INTRODUCTION

1.1 Some basics elements of communication systems:
In [1] [21], it is mentioned that communication system means a system where transmission of data or information is done from one point to another by several processes. The processes consist of generation of an information signal, description of the information signal through a defined set of symbols, encoding of the symbols through communication channels, decoding and reproduction of original symbols and finally re-creation of the original information signal. All these features of a communication system can be described by three basic elements such as transmitter, channel and receiver.

Figure 1.1: Basic structure of communication system

1.2 Wireless communication background
In 1921, Detroit Michigan Police Dept. made the earliest significant use of Mobile radio in a vehicle in the United States. The system operated at a frequency close to 2 MHz. The channels soon became overcrowded. In 1940, new frequencies between 30 and 40 MHz were made available. Increasing the available channels encouraged a substantial buildup of police systems. Shortly thereafter other users found a need for this form of communication. Private individuals, companies and public agencies purchased and operated their own mobile units. In 1945, first public mobile telephone system in the U.S. was inaugurated in St. Louis, Missouri with three channels at 150 MHz. Six channels spaced 60 kHz apart were allocated for this service by the FCC, but the mobile equipment was not sophisticated enough to prevent interference. In 1947, a Public mobile system using frequencies in the 35 to 44 MHz band began operations along the highway between New York and Boston. These frequencies were thought to carry greater distances however a problem with skip-distance propagation carried interfering conversations for long distances. These early mobile telephone systems used push-to-talk operation. In 1949, FCC authorized separate radio channels to common carrier entities known as "Radio Common Carriers" (ROC). These companies do not provide public telephone service, but interconnect to the public telephone network to provide mobile telephone services equivalent to the wire line common carriers. In 1955, number of wire line channels available at 150 MHz was expanded from 5 to 11 by the creation of new channels between the old ones (channel spacing of 30 kHz). In 1956, 12 wire line channels were added near 450 MHz. All systems operated in a manual mode, with each call to or from a mobile unit being handled by a special mobile telephone operator. In 1964, a new system (150 MHz) was developed providing automatic channel selection for each call, eliminated the need to push-to-talk operation, and allowed customers to do their own dialing. In 1969, automatic capability was extended to the 450 MHz band and the so called "Improved Mobile Telephone System" (IMTS) became the standard for mobile telephone service in the U.S. [4] [20].

1.3 Evolution of wireless systems from 1G to 3G
1G is the first generation of wireless telephone technology. It is antecedent to the Mobile Radio technology also known as 0G. It is basically the analog telecommunication standards that were introduced in 1980. It used analog radio signal and digital signaling to connect the radio towers to the telephone system. The voice during a call is modulated to higher frequency typically 150MHz or up in this system. Advanced mobile phone systems (AMPS), Nordic mobile telephone (NMT) and Total access communication systems (TACS) were included in the first generation cellular systems. But it has many disadvantages to get along with. The first disadvantage was lack of security due to no encryption. Secondly, low data rates also drove it behind. Finally, it was not compatible with upcoming 2G. The 2nd generation of wireless telephone technology is known as 2G. It was first commercially launched in 1991. There are three major benefits of 2G system over 1G which are- 1. Phone conversations were digitized 2. More efficiency on spectrum which allowed greater penetration for signals 3. Data service
Apart from the benefits described above there are many other advantages of the 2G system. It is more energy efficient, allowed digital encoding of voice and error checking. It is also more secure than 1G as it was harder for others to eaves drop on calls and to make “cloned” handset. The 2G system started to use advanced digital technologies and its capacity was higher than before but at an affordable cost. Due to various kind of spectrum access, three major 2G standards were born, namely IS-136, IS-95 in the United States and Global system for Mobile in Europe. There are several high data rate versions such as, General Packet Radio Service (GPRS) and Enhanced Data Rates for GSM Evolution (EDGE) for GSM, IS-136 high speed (IS-136HS) for IS-136, and IS-95 high data rate (IS-95 HDR) for IS-95. 3G is the technology that came after 2G, also called the 3rd generation wireless telephone technology. It is based on the International Telecommunication Union (ITU) family of standards and was first commercialized in 2003. It provided higher network capacity and greater spectral efficiency than its predecessor 2G. It also enabled operators to provider a wider range of more advance services. So basically 3G took the existing 2G technology to the next level. There is some confusion about the data rates that 3G can provide as it is not always clear that what modes of the interfaces qualify as 3G. They support transmission rate up to several mega bits per second. However it is expected that 3G will provide minimum of 2Mbit/s and maximum of 14.4Mbit/s for stationary users, and 384kbit/s for moving users. The third and current generation of cellular system includes wideband code division multiple access (WCDMA) and CDMA2000. The next generation of wireless cellular systems is envisioned to be multicarrier based for its efficient bandwidth usage [1] [13] [18] [22].

1.4 Introduction of 4G technology
It has been a few years since the research on 4th generation mobile communication has begun. Many of the researches on 4G technology have already been published. It is likely that it will mainly extend the capabilities of its big brother which is known as 3G (3rd generation mobile communication). Because it will increase the capabilities of 3G, it will allow a greater range of applications and will also improve the universal access. Some of the features that will become available in 4G are High Definition Television (HDTV) (4-20 Mbps) and computer network applications (1-100 Mbps). So it will eventually replace WLAN and broadband as it incorporates both of their features. One of the main focuses of 4G will be to improve its spectral efficiency significantly as the 3G system cannot support high data rates services at low cost. In addition the Quality Of Service (QOS) must also need to be improved. To support many services the 4G system will require to have a QOS closer to 98-99.5% where today’s cellular systems have QOS around 90-95%. To achieve this QOS the system has to be more flexible and adaptive. QOS means that maintaining connectivity becomes more important than the data rate achieved. So depending on the transmission path the data rate may range from 1 kbps to 20 Mbps. From this it is clear that 4G systems needs to make significant improvement in spectral efficiency to provide true broadband access. And by making advances in network management, smart antennas, RF modulation, user allocation and resource allocation 4G can make it possible [1] [13] [19].

1.4.1 Special features of 4G Wireless Systems * Packet based infrastructure. * Higher data rate with lower cost. * Support for broadband services. * Flexibility and mobility of wireless systems like 3G, WiFi, WiMax etc. * Very high Quality Of Service (QOS). * Better scheduling and call admission control techniques. * Ad hoc networks and multi-hop networks.

1.4.2 Comparison between 3G and 4G
According to [1] [18] [19] we have the following:

Table 1.4.1 Comparisons of the basic features of 3G and 4G | 3G | 4G | Frequency Band | 1.8- 2.5 GHz | 2- 8 GHz | Bandwidth | 5-20 MHz | 5-20 MHz | Data rate | Up to 2Mbps (384 kbps WAN) | Up to 20 Mbps or more | Access | Wideband CDMA | Multi-carrier – CDMA or OFDM (TDMA) | FEC | Turbo- codes | Concatenated codes | Switching | Circuit/ Packet | Packet | Mobile top speeds | 200 kmph | 200 kmph |

1.4.3 Introduction OFDM as Main Premise of 4G
In [1] [19], for the main transmission technique for 4G, Orthogonal Frequency Division Multiplexing (OFDM) is being considered as most promising. This is because of its dexterous performance in combating multipath fading as well as Inter Symbol Interference (ISI) and in the use of the available bandwidth. This scheme was first proposed by Chang in 1966 for dispersive fading channels. OFDM is very similar to the Frequency Domain Multiplexing (FDM) technique. OFDM uses the same basic principals as FDM but can send multiple messages over a single radio channel. It is also more controlled and has improved spectral efficiency.
The system’s operating principle is that the original bandwidth is divided into narrow subcarriers and these subcarriers are put into service by using Simple Fast Fourier transform.

1.5 Motivations toward the objective of the thesis
ONE of the most challenging issues for future wireless communication systems is the provision of quality-of-service (QoS) guarantees to users over the harsh wireless channels given the limited resource availability. This necessitates the development of intelligent resource-management algorithms, as well as high-performance physical-layer techniques to provide high throughput, efficient resource use, and aggressive multiple access while functioning under bandwidth and power restrictions.
Recently, research and development of the OFDM has received considerable attention and have made a great deal of progress for the next generation wireless system due to its high data rate transmission capability with high bandwidth efficiency. OFDM divides the available bandwidth into N orthogonal sub channels. By adding a cyclic prefix (CP) to each OFDM symbol, the channel appears to be circular if the CP length is longer than the channel length. Each sub channel thus can be modeled as a time-varying gain plus Additive White Gaussian Noise (AWGN). [5] Its inherent multicarrier nature allows flexible frequency channel control so that the transmission power and constellation size can be adapted on every subcarrier to exploit the frequency-domain diversity and improve the attainable data rates .
Multiuser OFDM adds multiple access to OFDM by allowing a number of users to share an OFDM symbol. Two classes of resource allocation exist: fixed resource allocation [2] and dynamic resource allocation [7] [8] [9] [10] [11] [12]. In multiuser systems using fixed resource allocation schemes such as time-division multiple access (TDMA) or frequency-division multiple access (FDMA), each user is allocated a predetermined time slot or frequency band. A fixed resource allocation scheme is not efficient since the scheme is fixed regardless of the current channel condition. On the other hand dynamic resource allocation allocates a dimension adaptively based on channel gains. Due to time varying nature of the wireless channel, dynamic resource allocation makes full use of multiuser diversity to achieve higher performance. So, it motivates us to consider an adaptive multiuser subcarrier allocation scheme where the sub carriers are assigned and bits are assigned to the users based on the instantaneous channel information. In dynamic multiuser OFDM system, two classes of optimization schemes have been proposed: margin adaptive (MA) [1] [8] and rate adaptive (RA) [1] [5].In margin adaptive approach, the objective is to achieve overall minimum transmit power for a constant bit rate and BER. On the other hand, the objective of the rate adaptive approach is to maximize each user’s error free capacity for a given bandwidth and constant transmit power. These optimization problems are non-liner and hence computationally intensive to solve. In [14] the non-linear optimization problems were transferred into a linear optimization problem using integer variables. The optimal solution can achieve by integer programming but the complexity increases exponentially with the increase of constraints and variables. Assuming that the transmitter knows the instantaneous channel transfer functions of all users, many papers [5] [8] have demonstrated that significant performance improvement can be achieved if adaptive modulation is used with OFDM. In [15] the problem of optimal power allocation has also been studied taking in account the frequency selective nature of a user’s channel. In [16] Jang and lee proved that the sum capacity is maximized when each sub channel is assigned to the user with best subchannel gain and power is then distributed according to water-filling algorithm. But rate adaptation with proportional fairness is discussed in [5]. Viswanathan , Tse and Laroia pointed out that in multiuser systems, channel fading can be exploited as a source of randomness.
Wong et al. [8] proposed iterative searching algorithm that applies Lagrangian relaxation for optimum multiuser subcarrier, bit, and power allocation. The algorithm is close to the lower bound with requirement of high and complex computation. Zhang [17] proposed water-filling algorithm (transmit more signal power in the better channels and less signal power in the poorer channels) similar to Wong’s algorithm to avoid computational complexity. Y.B. Reddy et al introduced Genetic algorithm [9] and A. Imtiaz introduced Particle Swarm optimization [1] in resource allocation with significant improvements. However in all these researches MA and RA techniques have been implemented separately. So, this fact motivates us to formulate a technique that combines MA and RA techniques and performs a joint adaptive subcarrier, bit and power allocation in multiuser OFDM system.
In these research work, MOGA (Multi objective genetic algorithm) is introduced as a promising technique of adaptive resource allocation for multiuser OFDM system that combines MA and RA approach.

1.6 Problem Statement
This thesis paper mainly deals with Adaptive resource allocation of multiuser OFDM system (using both fair and unfair scheduling). For proper clarification of these, first two conventional methods of OFDMA resource allocation have been deployed. Of the two methods, the margin adaptive approach, minimizes the overall transmit power for a constant bit rate and overall bit error rate (BER). The second one, rate adaptive approach, deals with the maximum throughput for a constant power and BER. In this thesis, both the approaches have been implemented using Genetic Algorithm. Most importantly, in this paper, a new optimization scheme is formulated that combines the above two approaches. This combined scheme has been implemented using Multi Objective Evolutionary Algorithms-1) Multi Objective Genetic Algorithm (MOGA) and 2) Non-dominated Sorting Genetic Algorithm (NSGA). This research work reflects that evolutionary approaches can be applied in adaptive resource allocation without performance degradation. GA (for MA and RA approach), MOGA and NSGA (for combined approach) all have been implemented for both the cases of fair and unfair scheduling. In unfair scheduling, no restrictions are applied on the subcarrier allocation to the users or on the bit allocation to the users. Here, the subcarriers are allocated to the users according to the dynamic channel conditions by water filling algorithm. This process does not follow proper scheduling in the sense that any of the users can even obtain zero subcarrier, or subcarriers having worst channel gains or subcarriers having zero bits. So, in this paper a fairness approach has been implemented which puts a restriction in subcarrier in such a way that each user must be allocated a minimum number of subcarriers transmitting a minimum number of bits. Concept of priority is also implemented to decide the priority level of different users. The fair scheduled allocation may not give the optimum result but a constant fairness with a constant bit rate of individual users is preserved, which is more practical and efficient.

1.7 Organization of the Thesis
This thesis paper is organized as follows. Chapter 1 has already given an idea on basic communication system, evolution of mobile communication or wireless communication from 0G to 4G (next generation), and use of OFDM in the 4G systems and discussion of the problem we are trying to solve.
Chapter 2 gives a detail description of OFDM systems, different multiple access techniques, resource allocation schemes of an OFDMA system and introductory discussion of GA, MOGA and NSGA. Chapter 3 introduces the proposed OFDMA system model, presents the optimization objective functions as well as develops the algorithms for Margin adaptive (using GA), Rate adaptive (using GA), and the combined approach(using MOGA and NSGA) along with their flowcharts. Chapter 4 provides the numerical and comparative results of different systems proposed in Chapter 3.This Chapter also gives a clear comparison of proposed algorithms for MA and RA using GA with different existing ones. As there are no previous researches on combined approach, a comparison is given between GA, MOGA and NSGA in terms of execution time. Chapter 5 concludes the research by stating total outcome of the research work and by invoking the scopes of the future exploration.

CHAPTER 2
BASIC PRINCIPLES OF OFDM, RESOURCE ALLOCATION AND INTRODUCING DIFFERENT EVOLUTIONARY ALGORITHMS

2.1 Overview of OFDM
OFDM is a special form of multicarrier modulation (MCM), where a single data stream is transmitted over a number of lower rate subcarriers. The communication channel is divided in to several sub carriers which contain same equal bandwidth and the subcarriers are orthogonal to each other. It is worth mentioning here that OFDM can be seen as either a modulation technique or a multiplexing technique. One of the main reasons to use OFDM is to increase the robustness against frequency selective fading and narrowband interference. In a single carrier system, a single fade or interferer can cause the entire link to fail, but in a multicarrier system, only a small percentage of subcarriers will be affected. Error correction coding can then be used to correct the few erroneous subcarriers [1] [3].

2.1.1 Basic concepts of Orthrogonality
In [23], the main feature of OFDM is orthogonality of the sub carriers. Actually all sub carriers are sine wave or cosine wave. Two different functions are orthogonal when they are multiplied and integrated over a symbol period, and the result of this mathematical manipulation is zero.
Let us take two sub carriers functions with different frequencies.
S1= sin iwt S2= cos jwt
F(t)= S1 * S2 =siniwt*cosjwt=12*2*siniwt*cosjwt=12sini+jwt+12sini-jwt …(2.1.1.1)
Now integrating f(t) over a given symbol period (0<t<T),
02πftdt= 02π12sini+jwt dt+1202π12sini-jwt dt……….(2.1.1.2)
We know over a period the integral of sine or cosine function is zero.
02πftdt=0…. (2.1.1.3)
So, this satisfies the condition of orthogonality.
The technique can be used in an alternative way. Like the receiver will look for a particular function. So, the results from all other function will be zero except the particular function.
0Tsi t sj tdt=K ,i=j0 , i≠j …………..……… (2.1.1.4)
This equation can be written for an unmodulated real OFDM signal.
Sk (t) =sin2πkf0 t, 0<t<T, k=1,2,…..M 0, otherwise………………… (2.1.1.5)
Where f0 is the subcarrier spacing, M is the no of sub carriers, T is the symbol period. Since the highest frequency component is Mf0, the transmission bandwidth is also Mf0.

2.1.2 Frequency domain orthogonality
In [1], the orthogonality property of OFDM can also be viewed by looking at its spectrum. From the following figure we can see that in the frequency domain, each OFDM subcarrier has a frequency response like sinc(x), sin(x)/x. This is because the symbol time corresponds to the inverse of carrier spacing. From the receivers point of view, each OFDM symbol is transmitted for a fixed time (TFFT) and it doesn’t face any tapering ate the ends.
This symbol time corresponds to the inverse of the subcarrier spacing of 1/TFFT Hz. This waveform which is rectangular in time domain becomes a sinc frequency response in the frequency domain. The waveform of sinc has a main lobe which has the highest magnitude. The side lobes gradually decay away from the main lobe which corresponds with the magnitude of the frequency difference from the center. Each carrier has a peak at the center and the nulls are evenly spaced with a frequency gap which is equal to the carrier spacing.
As the peak of a subcarrier corresponds to the nulls of all the other subcarriers, it results in orthogonality. The spectrum gives discrete samples when it is detected using Discrete Fourier Transformation (DFT). The samples only correspond to the peaks if the DFT is time synchronized. Therefore overlapping frequency of the subcarriers doesn’t affect the receiver.

2.1.3 An OFDM transceiver
From [2], we can assume an OFDM system as the following:

Figure 2.1.3: OFDM transceiver
* The incoming serial data is first converted from serial to parallel and grouped into x bits each to form a complex number. The complex numbers are modulated in a baseband fashion by the IFFT. And then are converted back to serial data for transmission.
*A guard interval is inserted between symbols to avoid inter symbol interference (ISI) which is caused by multipath distortion. The discrete symbols are transformed in to analog and low pass filtered for RF up-conversion.
*The receiver performs the inverse process of the transmitter. One tap equalizer is used to correct channel distortion. The tap coefficients of the filter are calculated based on channel information.

2.1.3.1 Guard intervals
Form [1] [24], we know in communications, guard intervals are used to ensure that distinct transmissions do not interfere with one another. In the case of OFDM system, these transmissions belong to the same user.
In the case of OFDM, if we take Nc subcarriers, the whole bandwidth is divided in to Nc times less symbol rate than a single transmission.
For multipath propagation causes inter symbol interference, but the low symbol rate modulation schemes suffer less from that. It is better to transmit a number of low-rate streams in parallel instead of a single high-rate stream. For the duration of each symbol is long, it is possible to insert a guard interval between the OFDM symbols, thus eliminating the inter symbol interference.

2.1.3.2 Serial to parallel conversion
From [1], the data comes from the user or the data which is to be transmitted, always is in the form of a serial data stream. The serial data stream should be converted in to parallel data stream in order to send through the several subcarriers. The data allocated to the each symbol depends on the modulation scheme used and the number of subcarriers. In the adaptive subcarrier modulation schemes, the modulation scheme may vary for each subcarrier as well as the number of the bits. Actually the serial to parallel conversion stage fills the subcarriers with their desired payload. At the receiver the reverse process takes place with the data from the carriers converted back to the original serial data stream.

2.1.3.3 Subcarrier implementation
When the subcarriers are allocated with the bits for transmission, they are mapped using a modulation scheme to a subcarrier amplitude and phase, which is represented by a complex In- phase and Quadrature –phase (IQ) vector. Subcarrier modulation is implemented by a lookup table, which makes it very efficient to implement. In the receiver, first mapping the received IQ vector is used to get back to the data word which is the carrier demodulation. During transmission noise and distortion are added to the signal because of thermal noise, signal power reduction and imperfect channel equalization. For each received signal IQ vector, the receiver has to estimate the most likely original transmission vector. This is achieved by finding the most likely original transmission vector that is closest to the received vector [1].

2.1.3.4 RF modulation
RF modulation can be done by implementing analog techniques or using digital up converter. However the digital modulation shows better performance [1].

2.1.3.5 FFT and IFFT
In [23], forward FFT takes a random signal, multiplies it successively by complex exponentials over the range of frequencies, sums each product and plots the results as a coefficient of that frequency. The coefficients are called a spectrum and represent “how much” of that is present in the input signal. The results of the FFT in common understanding is a frequency domain signal.
We write FFT in sinusoids as xk=n=0N-1xnsin2πknN+ jn=0N-1xncos2πknN ………….. (2.1.3.5.1)
Here, x(n) = the coefficients of the sines and cosines of frequency 2πk/N, where k is the index of the frequencies over the N frequencies, and n is the time index. x(k) is the value of the spectrum for the kth frequency and x(n) is the value of the signal at time n.
The inverse FFT takes this spectrum and converts this spectrum and converts the whole thing back to time domain signal by again successively multiplying it by a range of sinusoids,
The equation for IFFT is
Xn= n=0N-1xksin2πknN-jn=0N-1xkcos⁡2πknN…………. (2.1.3.5.2)

2.1.4 The OFDM System Model
In [1], the data stream into blocks of N data symbols in the transmitter. These blocks, called OFDM symbols, are represented by a vector xn=[x0,m, x1,m,x2,m, …….. ,xN-1.m]T. Next each data block is processed with IDFT operation and a length Ncp cyclic prefix is added to the data block. The mth OFDM symbol for the resulting complex discrete time signal is ………………………… (2.1.4.1)
Here, n is the timing index
The complete time signal is found as
………………………………………. (2.1.4.2)
In general term it can be said that the received signal is the sum of a linear convolution with the discrete channel impulse response h(n) and the Additive White Gaussian Noise (AWGN), w(n). In addition it is assumed that the transmitter and the receiver are perfectly synchronized. Based on the fact that the cyclic prefix is sufficiently longer to accommodate the channel impulse response, the linear convolution becomes circular one. Thus the received signal becomes
…………………………………… (2.1.4.3)
In the receiver the incoming sequence r(n) is split into two blocks and the cyclic prefix associated with each block is removed. This results in a vector rm=[r(zm),r(zm+1),……,r(zm+N-1)]T with zm=m(N+Ncp)+Ncp. The received data symbol yk,m is given by ………………………………….. (2.1.4.4)
Substituting r(n)

………………………. (2.1.4.5)
Where ,

2.2 Overview of multiple access techniques in OFDM Systems
There are various multiple access techniques which are added to the OFDM transmission. And these are orthogonal frequency division multiplexing –time division multiple access (OFDM-TDMA), Orthogonal Frequency Division Multiple Access (OFDMA), Multi Carrier Code Division Multiple Access (MC-CDMA).

2.2.1 OFDM-TDMA
In OFDM-TDMA, a time slot is located to each user which is multiple of an OFDM symbols period. In this time slot a user will occupy all the subcarriers that means only one user is given the privilege to transmit over all sub channels at the allocated time [1].

2.2.2 OFDMA
The OFDMA is the multi-user edition of OFDM system where the subcarriers are divided among the users and all users if a channel can transmit or receive data at the same time by using allocated subcarrier. There are some advantages of OFDMA. Actually each user uses different subcarrier, so the probability of fading and interference based on the location and propagation characteristics of each user decreases dynamically. In OFDMA, the base station actually issues subcarrier to the users depending on the various constrains imposed on the users. Different number of sub-carriers can be assigned to different users, in view to support differentiated Quality of Service (QoS), i.e. to control the data rate and error probability individually for each user [1] [25].

2.2.3 MC-CDMA
In [1], the MC_CDMA system uses a spreading code to send data symbol on multiple subcarriers. Though multiple users’ signals overlap in time and frequency domain, they can be separated easily by using the spreading codes. So, in a sense, MC-CDMA is a combination of OFDM and CDMA schemes and incorporates the benefits of both these approaches.

2.3 Overview of Resource Allocation in OFDMA Systems
Resource allocation is one of the major components of high speed wireless communication systems. It is also a very challenging issue, for there are limited resources available such as total transmitted power and total bandwidth at the base station. To have an optimum performance the recourses should be allocated intelligently to meet the user requirement. Actually there are two kinds of allocation such as static allocation and dynamic allocation. In static allocation, the total power and band width are fixed, as well as users. So it is not actually efficient way to allocate available resources in the present scenario where number of users’ increases as well as their necessity. So the now a days the dynamic allocation is actually taking the place of the static one. To allocate the available resources among the users, two methods, margin adaptive process and rate adaptive process.

2.3.1 Margin Adaptive Approach
From [1], in margin adaptive approach, the resource allocation is actually done by minimization of power with a constant bit rate and it actually deals with the allotment of subcarrier, bit and power to a number of users where all users transmit in all users transmit in all time slots.
The minimum transmit power is obtained by,
P=n=1Nk=1Kfbn,k∝(n,k)2……………………………….. (2.3.1.1)
Where,
P= the total transmit power, bn,k = the byte rate for kth user on the nth subcarrier, α2 n,k = channel gain squared for nth sub-carrier in addition to kth user,
And the required received power expressed by, fbn,k=No3 Q-1 BERn42 (2bn,k -1)…………………… (2.3.1.2)
Here N0 stands for noise power spectral density and BERn designates the bit error rate for nth subcarrier.
Qx=12πx∞e-t22 dt and here Q-1 denotes the inverse Q function.

2.3.2 Rate adaptive approach
From [1], in rate adaptive approach, the total transmit power is set to be constant and is denoted by, k=1Kn=1NSk,n=S……………………………………… (2.3.2.1)
Where, S = the total transmit power Sk,n= is the transmit power for kth user and the nth subcarrier.
The equation for the rate adaptive approach is,
Rk=k=1Kn=1Nρk,n Nlog21+pk,nhk,n2N0BN………………………………… (2.3.2.2)
Where, K = the number of users N = the total number of carriers N0 = the power spectral density of additive white Gaussian noise B = total bandwidth pk,n = the power allocated for user k in the subcarrier n, hk,n = the channel gain for user k and subcarrier n ρk,n = only be the value of either 1 or 0, indicating whether subcarrier n is used by user k or not.

2.3.3 Unfair and Fair Scheduling
In [1], the fair scheduling means actually distributing the resources with fairness. There are two kind of fair scheduling. These are fair scheduling by data rate and fair scheduling by subcarriers. Fairness in data rate means each user has to transmit a minimum rate of data irrespective of the situation. Fairness in sub channel means each user must have a minimum number of sub channel allocated through which they will transmit data irrespective of the situation.

2.4 Introducing Genetic Algorithm, Multi objective Genetic Algorithm and Non-dominated sorting genetic algorithm for Resource allocation in OFDMA
Adaptive resource allocation knowing channel information has been shown to achieve higher system performance than static resource allocation. As the number of user and the data rate requirement is increasing day by day, it is becoming more important to intelligently allocate limited resources. Moreover, the subcarrier allocation between multiple users has many different combinations, making the solution space very large. So, in this thesis we used evolutionary approaches such as Genetic Algorithm, Multi objective Genetic Algorithm and Non-dominated sorting genetic algorithm. These algorithms are described in following sections

2.4.1 Introduction to Genetic algorithm
Genetic algorithm (GA) is a modern search technique to solve problems which need optimization. GA is an algorithm which makes it easy to search a large search space. Genetic algorithms are a particular class of evolutionary algorithms (also known as evolutionary computation) that use techniques inspired by evolutionary biology such as inheritance, mutation, selection, and crossover (also called recombination).[26]

2.4.1.1 Biological Background
GA’s are based on based on Darwin’s theory of evolution which states that “Individuals less suited to the environment are less likely to survive and less likely to reproduce; individuals more suited to the environment are more likely to survive and more likely to reproduce and leave their inheritable traits to future generations, which produces the process of natural selection. This slowly effected process results in populations changing to adapt to their environment, and ultimately, these variations accumulate over time to form new species.” [27]Some important biological concepts from which the idea of GA is developed is given below Chromosomes and Genetics: Genetic information is stored in the chromosomes. Each chromosome is build of DNA. Again the chromosome is divided in parts: genes. The entire combination of genes is called genotype. The genotype of an organism is the inherited instructions it carries within its genetic code. Phenotypes result from the expression of an organism's genes as well as the influence of environmental factors and possible interactions between the two. [27]
Natural selection: According to the origin of species natural selection is “Preservation of favorable variations and rejection of unfavorable variations.”[27]
Reproduction and Mutation: Genetic information is shared between the parents in order to create new offspring. Mutation means, that the elements of DNA are a bit changed. These changes are mainly caused by errors in copying genes from parents.

2.4.1.2 Basics of Genetic Algorithm
Genetic algorithms are implemented as a computer simulation in which a population of abstract representations (Chromosomes) of candidate solutions (individuals) to an optimization problem evolves toward better solutions [1]. Traditionally Individuals or current approximations are encoded as strings, chromosomes, composed over some variables, so that genotypes (genes or chromosome values) are uniquely mapped onto the decision variable (phenotypic) domain. Mostly, Solutions are represented as binary strings of 0s and 1s because that is beneficial to other procedure like selection, reproduction and mutation, although there are other representations. The evolution process starts with a set of populations of randomly generated individuals and it happens in generations. In each generation, first a portion of the population survives according to the fitness of every individual in the populations. Then, multiple individuals are selected (selection), and modified (recombination and mutation) to form a new set of population. This population is merged with the initial population to form a new population and the second generation begins with this population set. The process continues in this way until maximum number of generation (user defined) is produced or a satisfactory level has been reached for the population.

2.4.1.2.1 Population Representation and Initialization
The most commonly used representation of initial population (chromosomes) in the GA is that of the single-level binary string. Here, each decision variable in the parameter set is encoded as a binary string and these are concatenated to form a chromosome. Whilst binary-coded GAs are most commonly used, there is an increasing interest in alternative encoding strategies, such as integer and real-valued representations. Having decided on the representation, the first step in the GA is to create an initial population. This is usually achieved by generating the required number of individuals using a random number generator that uniformly distributes numbers in the desired range. For example, with a binary population of Nind individuals whose chromosomes are Lind bits long, Nind*Lind random numbers uniformly distributed from the set {0, 1} would be produced. An initial population can be initiated within a specific range.

2.4.1.2.2 The Objective and Fitness Function
Objective function is a function associated with an optimization problem which determines how good a solution is or provides a measure of how individuals have performed in the problem domain. A fitness function is a particular type of objective function that quantifies the optimality of a solution (that is, a chromosome) in a genetic algorithm so that that particular chromosome may be ranked against all the other chromosomes. The fitness is decided according to the nature of the problem. In the case of a minimization problem, the lowest numerical value of the associated objective function is declared as the fittest individual. In many cases, the fitness value corresponds to the number of offspring that an individual can expect to produce in the next generation.

2.4.1.2.3 Selection
Selection is the stage of a genetic algorithm in which individual genomes are chosen from a population for later breeding (recombination or crossover). According to Darwin's evolution theory the best ones should survive and create new offspring. Similarly, during each successive generation a portion of the initial or existing population is selected as parents for reproducing new child solutions. Selection methods are such that fitter solutions which are measured by a fitness function have more probability to be selected. There are many methods how to select the best chromosomes, but popular and well-studied selection methods include [5]- * Roulette Wheel Selection Methods * Stochastic Universal Sampling
2.4.1.2.4 Crossover (Recombination)
In genetic algorithms, crossover is a genetic operator used for producing new chromosomes. It is analogous to natural reproduction and biological crossover. Like those, crossover produces new individuals that have some parts of both parent’s genetic material (characteristics).Types of crossover : * Single point Crossover * Multipoint Crossover * Uniform Crossover
Single point Crossover: The simplest recombination operators are that of single point crossover. In this method one crossover point i is selected uniformly at random between 1 and the string length, l, minus one [1, l-1], and the genetic information exchanged between the individuals about this point, then two new offspring strings are produced. Consider the following two parent binary strings. The two offspring below are produced when crossover point i=6 is selected Child 2
100101011101
Child 1
101101000100
Parent 2
100101000100
Parent 1
101101011101

Figure 2.4.1.2.4.1: Single point crossover

Multipoint Crossover: For multi-point crossover, m crossover positions Xi are selected uniformly at random between 1 and the string length, l, minus one [1, l-1], with no duplicates and sorted into ascending order. Then, the bits between successive crossover points are exchanged between the two parents to produce two new offspring. The section between the first allele position and the first crossover point is not exchanged between individuals. This process is illustrated in figure 2.4.1.2.4.2.

Figure 2.4.1.2.4.2: Multipoint Crossover (m=4)
Uniform Crossover: In uniform crossover scheme two parents are combined according to a crossover mask to produce two new offspring. A crossover mask, the same length as the chromosome structures is created at random and the parity of the bits in the mask indicates which parent will supply the offspring with which bits. Consider the following two parents, crossover mask and resulting offspring:
Parent 1= 101010011010
Parent 2= 011101101111
Mask = 011000111011
Child1 = 001101011110
Child2 = 111010101011 Here, if the bit of the mask is 0 then two Parent solutions interchange their information, and if the mask bit is 1 then they do not interchange information. In this way they produce two offspring solution sharing the characteristics of the both.

2.4.1.2.5 Mutation
After selection and crossover, a new population full of individuals is produced. Some are directly copied, and others are produced by crossover. In order to ensure that the individuals are not all exactly the same, sometimes a small chance of mutation is allowed. The probability of mutation is usually between 1 and 2 tenths of a percent. Usually considered as a background operator, the role of mutation is often seen as providing a guarantee that the probability of searching any given string will never be zero and acting as a safety net to recover good genetic material that may be lost through the action of selection and crossover [26]. Binary mutation changes the value of the bit (0 to 1 or 1 to 0) at the loci selected to be the mutation point. It is also possible that a given binary string (solution) may be mutated at more than one point.

Mutation point

1
1
0
1
1
1
1
1
0
0

Figure 2.4.1.2.5: Binary Mutation

2.4.1.2.6 Reinsertion
To maintain the size of the initial or original population, the new individuals have to be reinserted into the old population. Similarly, if not all the new individuals are to be used at each generation or if more offspring are generated than the size of the old population then a reinsertion scheme must be used to determine which individuals are to exist in the new population.

2.4.1.2.7 Termination of the GA
Generational process of the GA is repeated until a termination condition has been reached. As GA is a stochastic search method, it is difficult to formally specify convergence criteria. Sometimes, the fitness of a population remains static for a number of generations. So the application of normal termination criteria which is to terminate after reaching a predefined optimal value becomes problematic. A common practice is to terminate the GA after a pre- specified number of generations and then test the quality of best members of the population against the objective function. In the case when no acceptable solutions are found, the GA may be restarted. In summary common terminating conditions are: * A solution is found that satisfies objective criteria * Fixed number of generations reached * Allocated budget (computation time) reached * Manual inspection * Combinations of the above

2.4.2 Multi-objective Optimization and Decision-making
As soon as there are many (possibly conflicting) objectives to be optimized simultaneously, there is no longer a single optimal solution but rather a whole set of possible solutions of equivalent quality. Consider for example, design of a communication system. Possible objectives could be: minimum transmit power, maximum throughput, maximum SNR (minimum noise) etc. The use of multi-objective optimization (MO) in engineering design in general, recognizes that most practical problems require a number of design criteria to be satisfied simultaneously. Mathematically,minxϵΩF(x). Where x =[x1, x2, ..., xk] and Ω define the set of free variables, x, subject to any constraints and F(x) = [f1(x), f2(x), …, fn(x)] are the design objectives to be minimized. Clearly, for this set of functions, F(x), it can be seen that there is no one ideal ‘optimal’ solution, rather a set of Pareto-optimal solutions for which an improvement in one of the design objectives will lead to a degradation in one or more of the remaining objectives. Such solutions are also known as non-inferior or non-dominated solutions to the multi-objective optimization problem. Assuming a minimization problem, dominance is defined [31] [32] as follows:
Definition: 1 (Pareto dominance): A given vector u=(u1,…..,un) is said to dominate v=v1,…,vn if and only if u is partially less than v , i.e.(up<v).
Definition: 2 (Pareto optimality): A solution Xu∈U is said to be Pareto-optimal if and only if there is no Xv∈U for which v=fXv=v1,…,vn dominates u=fXu=u1,…,un. The corresponding objective vectors are simply called non-dominated. The set of all non-dominated vectors is known as the non-dominated set, or the trade off surface, of the problem. In the general case, it is impossible to find an analytical expression of the line or the surface that contains these points.

2.4.2.1 Multi Objective Genetic Algorithm (MOGA)
Fonseca and Fleming first used the non-dominated classification of a GA population in MOGA. MOGA differs from standard GA in the way fitness is assigned to each solution in the population. The rest of the algorithm (the stochastic universal sampling, a single-point crossover, and a bit-wise mutation) is the same as that in a classical GA. The distinctive features of MOGA are briefly discussed below.

2.4.2.1.1 Population Initialization, Evaluation and Ranking
At first a randomly selected population is initiated within a specific range. Each individual of the population is evaluated using the objective functions. Then, each solution is checked for its domination in the population and a rank value is assigned to it. The definition of dominated, non-dominated solution and the ranking procedure can be explained through Figure 2.4.2.1.1. Here, a two-objective (2D objective space) minimization problem is considered. The solution point( solution of objective1 vs. solution of objective 2) that fall close to either the axes or origin of 2D objective space are better than those away from axes or origin.
In the objective space, Solution I (or corresponding individual) provides better performance than solution G in terms of both objectives and we are assuming that both objectives have equal priority. In other words G is dominated by I. Similarly solution C dominates solution I. But it cannot be said that solution A dominates solution B or vice versa because each one provides better performance for different objectives. Some solutions may be found, such as, A,B,C,D, E etc. falling on outer edge and close to the axes or origin and with one objective better than
Pareto Optimal Set Non –Dominated Solutions Dominated Solutions

O
B
J
E
C
T
I
V
E
2

O B J E C T I V E 1

Figure 2.4.2.1.1: Dominated and Non-dominated Solutions With rank values (Pareto Ranking)

Other, and form a set called non-dominated solution set or Pareto optimal set. A, B, C, D, E etc. are called non-dominated because no other solutions provide better performance in the objective space. On the other hand, individuals, falling away from the edges, such as, F, G, H, I, J etc. are called dominated solutions since many individuals provide better performance than these in terms of both objectives. Non-dominated individuals are all therefore considered to be best performers and thus assigned the same rank 0. Other solutions are ranked according to their degree of dominance, i.e., number of solutions that are better than that in terms of both objectives. To a solution i, a rank ri is assigned as: ri=0+ ni………………………….. (2.4.2.1.1)
Where ni is the number of solutions that dominate solution i. In this way, dominated solutions such as F are assigned a rank 2 and G is assigned a rank 5. The maximum rank of any solution cannot be more than N (the population size). It is clear that the ranking procedure may not assign all possible ranks (between 1 and N) to any population. For example, ranks 3 and 4 are missing in the population used in the Figure 2.4.2.1.1. Detail on ranking can be found in (Fonseca, 1995).

2.4.2.1.2 Fitness Assignment Suitable Fitness assignment schemes include rank based fitness mapping. Exponential rank-based fitness assignment is illustrated in Figure 2.4.2.1.2. Here, individuals are sorted by their cost-in

Figure 2.4.2.1.2: Rank Based Fitness assignment this case the values from Figure 2.4.2.1.2 and assigned fitness values according to an exponential rule in the first instance, shown by the narrow bars in Figure 2.4.2.1.2 . A single fitness value is then derived for each group of individuals sharing the same cost (rank), through averaging, and is shown in the figure by the wider bars. 2.4.2.1.3 Fitness Sharing
Originally introduced as an approach to sampling multiple fitness peaks, fitness sharing helps counteract the effects of genetic drift by penalising individuals according to the number of other individuals in their neighborhood. In order to maintain diversity among non-dominated solutions, Fonseca and Fleming have introduced niching among the solutions of each rank. Niche count, initially set to zero, is incremented by a certain amount for every individual in the population, including itself. A sharing function determines the contribution of other individuals to the niche count as a function of their mutual distance in genotypic, phenotypic, or objective space. Raw fitness values are then weighted by the inverse of the niche count and normalized by the sum of the weights prior to selection. The total fitness in the population is redistributed, and thus shared, by the population. However, a problem with the use of fitness sharing is the difficulty in determining the niche size (or niche radius), σshare i.e. how close together individuals may be before degradation occurs. In Figure 2.4.2.1 .3 solutions of region A, B and C are penalized and assigned a new fitness.

Penalising the fitness of the solutions based on σshare

σshare

σshare

σshare
Region A
Region C
Region B
Solutions

O B J E C T I V E 1
O
B
J
E
C
T
I
V
E
2

Figure 2.4.2.1.3: Fitness sharing

An alternative, but analogous, approach to niche count computations are kernel density estimation methods as used by statisticians (Silverman, 1986) [33]. Instead of a niche size, a smoothing parameter, h, whose value is also ultimately subjective, issued. However, guidelines for the selection of suitable values for h have been developed for certain kernels, such as the standard normal probability density function and Epanechnikov kernels. The Epanechnikov kernel may be written as (Silverman, 1986):
Kedh=0.5 Cn-1n+21-dh20 otherwise……………… (2.4.2.1.3.1)
Here, n is the number of decision variables Cn is the volume of the unit n dimensional sphere, and d/h is the normalized Euclidean distance between individuals. Apart from the constant factor, 0.5 Cn-1 , this kernel is a particular case of the family of power law sharing functions proposed by Goldberg and Richardson (1987) [34].Silverman (1986) gives a smoothing factor that is approximately optimal in the least mean integrated squared error sense when the population follows a multivariate normal distribution for the Epanechnikov kernel Ke(d) as Eqn …. for a population with N individuals and identity covariance matrix. h= 8 Cn-1n+4(2π)n/N1/(n+4)……………….. (2.4.2.1.3.2)
Where populations have an arbitrary sample covariance matrix, S, this may simply be ‘sphered,’ or normalized, by multiplying each individual by a matrix R such that RRT=S-1. This means that the niche size, which depends on S and h, may be automatically and constantly updated, regardless of the objective function, to suit the population at each generation.

2.4.2.1.4 Selection, Pair up, Recombination and mutation
Like normal GA, the stochastic universal sampling (SUS) method is then used to select the best individuals. However; mating restrictions (pair up) are employed in order to protect genetic drifts and premature convergence. GA operators, namely crossover (recombination) and mutation are employed on the selected individuals to create a new population and the loop continues until optimum value is reached.

2.4.2.2 Introduction to Non-dominated sorting Genetic algorithm II (NSGA-II)
Kalyanmoy Deb first proposed the non-dominated sorting classification with crowding function [1] of a GA population in NSGA-II. NSGA differs from MOGA in terms of fitness assignment and fitness sharing. The distinctive features of NSGA are briefly discussed below.

2.4.2.2.1 Population Initialization, Evaluation and Ranking
Like always at first a randomly selected population (parent) P of size N is initiated within a specific range. Each individual of the population is evaluated using the objective functions. Then, each solution is checked for its domination in the population. The non-dominated solutions are identified and put in a group called first non-dominated front. In order to find the members in the next non-dominated front, the solutions of the first front are discounted temporarily and the above procedure of checking domination and assigning solutions in a front is repeated. This is done by following procedure (Figure 2.4.2.2.1).

2nd non-dominated front
1st non-dominated front

3rd non-dominated front
O B J E C T I V E 1
O
B
J
E
C
T
I
V
E
2

Figure 2.4.2.2.1: Non-dominated sorting (in 2D objective space)

First, for each solution we calculate two entities: 1) domination count np, the number of solutions which dominate the solution, and 2) Sp, a set of solutions that the solution dominates. All solutions in the first non-dominated front will have their domination count as zero. Now, for each solution p with np=0, each (q) member of its Sp and reduce its domination count by 1. As a result domination count becomes zero for any memberq, and becomes a part of separate list Q. These members are part of the second non-dominated front. This process continues until all fronts are identified. Then each solution is ranked according to their level of non-dominated front.

2.4.2.2.2 Diversity preservation by crowded-comparison approach
In NSGA-II the sharing function approach of MOGA is replaced with a crowded-comparison approach. This approach can be best described by following two procedures.
1) Density Estimation: To find an estimate of the crowd around a particular solution in the population, the average distance between two points on either side of this point along each of the objectives. This quantity idistance is termed as crowding distance and it is used as an estimate of the perimeter of the cuboid formed by using the nearest solutions as vertices. In Figure 2.4.2.2.2 the crowding distance of the ith solution in its front is the average side length of the cuboid.

O
B
J
E
C
T
I
V
E
2
O B J E C T I V E 1

Figure 2.4.2.2.2: Crowded-distance calculation (in 2D objective space) 2) Crowded-Comparison operator: The crowded-comparison operator ( ) makes sure that the selection process at the various stages of the algorithm finds a uniformly spread-out Pareto-optimal front. Kalyanmoy [35] assumed that every individual i in the population has two attributes: 1) non- domination rank (irank) and 2) crowding distance (idistance) . A partial order is defines as i j , if (irank< jrank ) or ((irank = jrank ) and (idistance> jdistance )). This means if two solutions have two differing non-domination rank, then the best one is chosen, otherwise if both solutions have same rank then the solution with less crowd is preferred.

2.4.2.2.3 Rest of the algorithm introducing Parent-Child population approach After assigning fitness using non-domination sorting and crowd-comparison, the usual selection, recombination and mutation operators are used to create a offspring population Q of size N. Then, a combined population R= P ∪ Q is formed of size 2N. Then again R is sorted according to non-domination; crowded comparison operator is again used to assign fitness. Now the best N solutions (or fittest solution) chosen to form a new population P2. Then the above procedures are applied on the new population and the process continues. Step-by –step procedure is shown in Figure 2.4.2.2.3

R= P υ Q P2

Fitness assignment
Q
P
Selection,
Recombination
Mutation
Fitness assignment

Rejected

Figure 2.4.2.2.3: NSGA-II procedure

Note: Algorithmic structures, pseudo codes and flowcharts of Genetic algorithm, Multi objective genetic algorithm and Non-dominated sorting genetic algorithm are given in Appendix A.

CHAPTER 3
MODELING AND DESCRIPTION OF SYSTEM

In this chapter, the proposed multiuser OFDM system model is introduced with analytical expressions as well as structural view of the used system. The optimization objective functions (both for Margin Adaptation and Rate Adaptation) are also presented. A concept of joint subcarrier, bit, and power allocation scheme (resource allocation schemes) is developed with necessary discussion and algorithms. The optimization system models of GA,MOGA and NSGA are presented.

3.1 System Model of OFDMA systems for Resource allocation

3.1.1 Basic Structure
In OFDMA active subcarriers are divided into subsets of subcarriers termed as subchannels which are assigned to multiple users for simultaneous transmission. The subcarriers that form a particular subchannel may not be necessarily adjacent. To maintain the orthogonality among the subcarriers in the uplink of OFDMA systems, the signals from all active users should arrive at the base station simultaneously. [1] This is accomplished by an initial uplink synchronization called the ranging process. In this thesis, periodic ranging has been considered where transmitted power as well as the corresponding bits/subchannel/user is allocated to different users according channel state condition. Allocations of these resources are accomplished after a certain period in a dynamic nature.
In this thesis, an OFDMA system in a particular cell in cellular structure has been considered. Different users (suppose k users) reside over a particular hexagonal cell and always try to synchronize with the corresponding base station (Figure 3.1.1.1). The base station allocates the available resources to the users according to some well defined algorithm for efficient and reliable transmission of data. Resource allocation is done by a base station by communicating with the available users through uplink and downlink transmission. (Figure 3.1.1.2)

User 2
User 1

User 5
User 6
Base Station

User 4
User 3

Figure 3.1.1.1: Structural model of an OFDMA system in a particular cell

User

Subcarrier Channel And Information Bit allocation

DATA
Subcarrier, bit and power information for user K
Subchannel Vector
Subcarrier Allocation Algorithm
Bit Allocation Algorithm
1
2
.
.
K
OFDM
Transceiver
OFDM
Transceiver
Figure 3.1.1.2: Multiuser OFDM System Block for proposed system

A multiuser OFDM system is shown in Figure 3.1.1.2. In the base station, all channel information is sent to the subchannel/subcarrier allocation algorithm and bit allocation algorithm through feedback channels from all users in the cell. Bit allocation algorithm uses both the channel information and subcarrier allocation algorithm to allocate bits. The resource allocation scheme made by these algorithms is forwarded to the OFDM transmitter. The transmitter then selects different numbers of bits from different users to form an OFDM symbol. The resource allocation scheme is updated as fast as the channel state information (CSI) is collected. There are many ways to collect CSI. CSI may be estimated at the receiver and fed back to the Base station transceiver. However, in this paper, it is assumed that perfect instantaneous channel information is available at the base station and only the broadcast scenario is studied. It is also assumed that the subchannel, bit and power allocation information is sent to each user by a separate channel (control channel).

3.2 Modeling of the proposed system
A multiuser OFDM system having K ( k= 1,2,…,k) users and N(n=1,2,…,N) subcarriers is considered throughout the rest of the paper. In the Base station, the serial data from the users are fed into the transmitter. In order to overcome frequency selective fading causing inter-symbol interference, the bandwidth of each sub-carrier is chosen to be sufficiently smaller than the coherence bandwidth of the channel. In our system, we assume that the instantaneous channel gains on all of the subcarriers of all the users as well as user priority are known to the base station transmitter. Using known CSI, resource allocation module in BS applies joint sub-carrier ,bit and power allocation to assign different sub-carrier to different user the number of bits/OFDM symbol to be transmitted on every sub-carrier in such a way so that transmitted power is minimum(MA approach) and bit rate is maximum(RA approach). Depending on the number of bits assigned to a subcarrier adaptive modulator will use a corresponding modulation scheme. The basic transmission block diagram for a multiuser OFDM system is given in Figure 3.1.2.The CSI is put into the joint subcarrier, bit and power allocation algorithm block with the users and bits and the output are the allocation of the different user to the different subcarrier, also the selection of number of bits to be transmitted on each subcarrier and allocation of power. The adaptive modulator takes the allocated bits to adjust the modulation scheme. Then the signals are passed through the IFFT block and also pass through the guard interval block to add guard interval. The channel here is taken as a Rayleigh fading channel. The information of subcarrier and bit allocation are sent to the receiver by a different control channel. At the receiver first the guard interval is removed and then the signal is passed through the FFT block. Then a demodulator is used to demodulate the signal and at this point the bit and subcarrier information is used to extract bit for the exact user.

Figure 3.1.2: Multi User OFDM system
3.3 Proposed Algorithms for Different Resources Allocation Schemes
In this thesis we allocated subcarriers and bits to different users (knowing dynamic channel conditions) through evolutionary approaches. For Margin adaptive scheme and Rate adaptive scheme we have used Genetic algorithm (GA) and for Combined margin and rate adaptive scheme we have used Multi objective genetic algorithm (MOGA) and Non-dominated sorting genetic algorithm (NSGA). Each of the algorithms is analyzed for unconstrained case as well as fair scheduled case.

OFDMA Resource Allocation

Margin Adaptive Scheme

Rate Adaptive Scheme
Combined Margin and Rate Adaptive Scheme

Optimization by GA
Optimization by MOGA
Optimization by NSGA

Unfair
Fair
Unfair
Fair
Fair
Unfair

Figure 3.3: Different proposed systems for resource allocations

3.3.1 Margin and Rate Adaptive Resource Allocation Using Genetic algorithm (GA) for Multiuser OFDM Systems

3.3.1.1 Modeling of the fitness Function for MA approach
Let, bn,k indicates the number of bits transmitted by the kth user by using the nth subcarrier where 0<bn,k<B and bn,k is an integer. bn,k also determines the mode of adaptive modulation. It is assumed that the system acquires its channel state information from dynamic channel estimation scheme. Let |H|n,k represents the channel gain for nth subcarrier and kth user. The required transmission power for the specified bit error rate at bn,k bits per symbol is given by [1], pn,k= fbn,k|H|n,k2
In multiuser scenario, not more than one user is considered to share a particular subscriber. Mathematically it is expressed as λn,k=1 if bn,k≠00 if bn,k=0
We assume that the channel is ISI –free and has gain |H|. The probability of two- dimensional symbol error in QAM is closely approximated as
Pe=4Qdmi n2σ
Where Q(x) is the serro8r function and dmin is the minimum distance between QAM constellation points at the channel output and is given by dmin2=d2H2 Here, d=the distance between the constellation points at the channel output.
We defined a convenient SNR gap,
3Γ=dmin24σ2
Here 2σ2 is defined as the noise power. In QAM the number of bits to be transmitted is defined as b=log2M=log21+SNRΓ Here M denotes number of QAM levels and SNR=P|H|22σ2 where P is the transmitted power.
So from the above equations we can derive the fitness function of the margin adaptive optimization problem. And the equation is [1],
Pind=No3|H|2Q-114BER22b-1
So total power transmitted can be written as [1],
Ptotal=n=1Nk=1Kfbn,kHn,k2 × λn,k………....... (3.3.1.1.1a)
Where, fbn,k=No3 Q-1BERn422bk,n-1……………….(3.3.1.1.1b)

3.3.1.2 Fitness Function for RA approach
In the rate adaptive process, we will minimize the bit rate for a fixed BER and for the constant transmitted power. The fitness function we used here is derived by using Shannon’s theorem of maximum capacity of a dedicated channel. The function of rate adaptive approach is given by [1]-
Rk=k=1Kn=1Nρk,nN log21+Pk,nHk,n2NoBN…………. (3.3.1.1.2) Here K= the number of users N= the number of total subcarriers No = the power spectral density of the white Gaussian noise B= total bandwidth Pn,k= power allocated for the user k and the subcarrier n Hn,k= the channel gain for the user k and the subcarrier n ρn,k=only be 1 or 0, indicating whether subcarrier n is used by user k or not
And each subcarrier can only be used by one user at a time.

3.3.1.3 Setting of the initial population of MA and RA approach
First the binary data from different user is made into parallel an then mapped according to different modulation schemes like BPSK, QPSK, 16QAM, 64QAM etc. The selection of modulation scheme decides the number of bits to be transmitted. The allocation of subcarrier to the user is first made randomly as it indicates the initial population. After that, by using water filling algorithm, we allocate the number of bits to the particular subcarrier. And from the conventional algorithm, it is decided that the number of bits to be allocated to a subcarrier depends on the channel state information. So,
Initial population =g1,1⋯g1,N⋮⋱⋮gNind,1⋯gNind,N. gi,j represents the random assignment of user to a particular subcarrier j for ithchromosome.
There will be other implicit initial population called sub initial populations. One is of channel state information and other one is of number of bits. The wireless channels are quasi static. The channel state information is of each subcarrier is generated randomly and subject to Raleigh fading.
Let the random variable R, so the probability distributions function:
PRr=2rΩe-r2Ω
Where, Ω=E(R2)
Then according to the Raleigh distribution, the channel matrix becomes-
Channel matrix =ch1,1⋯ch1,N⋮⋱⋮chNind,1⋯chNind,N
Where chi,j represents the channel gain for a user to a particular subcarrier j for ithchromosome.
The bits from the corresponding users are allocated to the subcarrier according to the conventional water-filling algorithm.
Bit matrix= b1,1⋯b1,N⋮⋱⋮bNind,1⋯bNind,N
Here bi,j represents the number of bits for a user to a particular subcarrier j for ith chromosome.
The bit and the channel matrixes are used for evaluate the total power for an OFDM symbol.

3.3.1.4 Unfair scheduling
The equation of the power minimization problem is- argmin n=1Nk=1Kf(bn,k)Hn,k2×λn,k
Here,
n=1Kλn,k=1 for n=1,2,………,N n=1Nk=1Kλn,k=N for bn,k∈ 0,1,2,………,B
Rk=n=1Nbn,kfor k=1,2,………,K
The equation of the bit rate minimization problem is- argminρn,k Pn,kn=1Nk=1Kρn,kNlog21+Pk,nHk,n2N0BN
Here,

n=1Nk=1KPn,k≤Ptotal
Pn,k≥0 for all n,k ρn,k=0,1for all n,k k=1Kρn,k=1 for all n

3.3.1.4 Fair Scheduling
In this thesis, fair scheduling is formulated in such a way so that a minimum number of bits are allocated to each user. So, the constrain applied in previous unfair scheduling for MA and RA approach (section 3.3.1.3) is bk ≥ bmin , where bk is the number of bits for a particular user K

3.3.1.5 Optimization Procedure
First, initial and sub initial populations are generated using known CSI. Then objective or fitness function (For MA approach Equation 3.3.1.1.1 or for RA approach Equation 3.3.1.1.2) is evaluated using initial and sub initial populations. Then the usual GA operations like selection, recombination, mutation, insertion is performed and the loop continues until the termination criteria (in our case maximum generation) is reached. Flowchart of our proposed optimization procedure of both MA approach and RA approach is given in Appendix A.

3.3.2 Combined MA and RA scheme using MOGA and NSGA

3.3.2.1 Fitness Functions for Combined approach
In MOGA and NSGA, the number of fitness function depends on number of objectives. As we have two objectives of minimizing power and maximizing bit rate, there are two fitness functions in our proposed Combined scheme. Fitness function for power is Equation (3.3.1.1.1) and fitness function for bit rate is Equation (3.3.1.1.2).

3.3.2.2 Setting of the initial population of combined approach
Like MA approach and RA approach, First the binary data from different user is made into parallel an then mapped according to different modulation schemes like BPSK, QPSK, 16QAM, 4QAM etc. The selection of modulation scheme decides the number of bits to be transmitted. The allocation of subcarrier to the user is first made randomly as it indicates the initial population. Then, by using water filling algorithm, we allocate the number of bits to the particular subcarrier according to corresponding channel state information. So
Initial population =g1,1⋯g1,N⋮⋱⋮gNind,1⋯gNind,N
Here gi,j represents the random assignment of user to a particular subcarrier j for ith chromosome.There will be other implicit initial population called sub initial populations. One is of channel state information, one is of number of bits and one is of transmitted power. The channel state information of each subcarrier is generated randomly and subject to Raleigh fading. Then according to the Raleigh distribution, the channel matrix becomes-
Channel matrix =ch1,1⋯ch1,N⋮⋱⋮chNind,1⋯chNind,N
Where chi,j represents the channel gain for a user to a particular subcarrier j for ith chromosome.
The bits from the corresponding users are allocated to the subcarrier according to the conventional water-filling algorithm.
Bit matrix= b1,1⋯b1,N⋮⋱⋮bNind,1⋯bNind,N.
Here bi,j represents the number of bits for a user to a particular subcarrier j for ithchromosome.
The bit and the channel matrixes are used for evaluate the total power for an OFDM symbol.
The transmitted power matrix is found from the following equation,
Pi,j = No3|chi,j|2Q-114BER22bi,j-1, where bi,j is the number of bits for a user to a particular subcarrier j for ith chromosome (taken from bit matrix) and chi,j represents the channel gain for a user to a particular subcarrier j for ith chromosome. So the power matrix is formulated as below
Power matrix= P1,1⋯P1,N⋮⋱⋮PNind,1⋯PNind,N
Where Pi,j represents the channel gain for a user to a particular subcarrier j for ith chromosome. The bit, channel and power matrixes are used for evaluate the total bit rate for an OFDM symbol.

3.3.2.3 Unfair Scheduling
The equation of the power minimization problem is: argmin n=1Nk=1Kf(bn,k)Hn,k2×λn,k
And the equation of the bit rate minimization problem is-argminρn,k Pn,kn=1Nk=1Kρn,kNlog21+Pk,nHk,n2N0BN
Here,
n=1Kλn,k=1 for n=1,2,………,N n=1Nk=1Kλn,k=N for bn,k∈ 0,1,2,………,B n=1Nk=1KPn,k≤Ptotal Pn,k≥0 for all n,k ρn,k=0,1for all n,k
3.3.2.4 Fair Scheduling
In this case also, fair scheduling is formulated in such a way so that a minimum number of bits are allocated to each user. So, the constrain applied in previous unfair scheduling for combined approach (section ) is bk ≥ bmin , where bk is the number of bits for a particular user K

3.3.2.5 Optimization Procedure
First, initial and sub initial populations are generated using known CSI. Then objective or fitness functions are evaluated simultaneously using initial and sub initial populations. Then, while using MOGA the usual operations like non-dominated solution based fitness assignment, fitness sharing, selection, recombination, mutation are performed and and while using NSGA the usual operations like non-dominated front based fitness assignment, crowding based fitness sharing, selection, recombination, mutation, insertion, union, united population fitness assignment, rejection are performed and the loop continues until the termination criteria (in our case maximum generation) are reached. Flowchart of our proposed optimization procedure of both MOGA and NSGA for Combined approach is given in Appendix A.

4.1 Used Specification for Total System
4.1.1 Specification for multiuser OFDM
In our thesis work, all simulations have been done with the MATLAB 7.1. A simulator is created to serve our purpose. In simulator some specific values are taken which are mentioned in the following table
Table 4.1.1 Parameters of multiuser OFDM simulator Parameter | Value | Number of subcarriers(if otherwise not stated) | 64( for MA and RA approach)8 ( for combined approach) | Number of users(if otherwise not stated) | 2, 4, 6, 8 | Channel | Rayleigh | Modulation Scheme | No modulation (0 bits), QPSK (2 bits), 16 QAM (4 bits) and 64 QAM (6 bits) | Channel state information | known |

4.1.2 Parameter setting for Genetic algorithm, Multi Objective Genetic Algorithm, and Non Dominated Sorting Genetic Algorithm
In [1] it is shown that low value of initial population size degrades the overall performance of GA. We have assumed an initial population size of 80, number of generations is from 0 to 200. For GA, crossover probability 0.6 and mutation probability is 0.03 is assumed. If not otherwise mentioned, all the other optimizers use the specification of above.

4.2 Optimization of Resources Allocation of MA and RA schemes using GA
4.2.1 Margin Adaptive Approach by GA
4.2.1.1 Minimum Transmit Power Obtained by GA using Margin Adaptive Approach (Unconstrained Approach)
Taking initial population size of 80, the GA is used to allocate the resources for multiuser OFDM system. The minimum power is calculated by GA for 10 times (Table 4.2.2.1.1) and five of them are shown in the convergence curve (Figure 4.2.1.1.1).

Figure 4.2.1.1.1: Convergence curve for MA approach (Unfair scheduling)
Table 4.2.2.1.1 Margin Adaptive approach (Unconstrained approach) Margin Adaptive approach (Unconstrained approach) | Run | Minimum Transmit Power (in dbm) (By GA) | 1 | 6.8686 | 2 | 4.6267 | 3 | 4.8094 | 4 | 6.6407 | 5 | 4.0704 | 6 | 6.1382 | 7 | 3.4729 | 8 | 4.2117 | 9 | 4.8927 | 10 | 5.1915 | Mean | 5-09228 |

4.2.1.2 Minimum Transmit Power Obtained by GA using Margin Adaptive Approach (Fair scheduled Approach)
As stated previously, in this thesis, fairness has been introduced in such a way so that each user gets a minimum number of bits (information). The minimum power is calculated by GA for 10 times (Table 4.2.1.2.1) and three of them are shown in the convergence curve (Figure 4.2.1.2.1).
Figure 4.2.1.2.1: Convergence curve for MA approach (Fair scheduling)

Table 4.2.1.2.1 Minimum transmit power evaluation by GA (Fair scheduled approach) Margin Adaptive approach (Fair scheduled approach) | Run | Minimum Transmit Power (in dbm) (By GA) | 1 | 20.6803 | 2 | 20.559 | 3 | 20.106 | 4 | 20.053 | 5 | 21.064 | 6 | 19.998 | 7 | 19.976 | 8 | 20.154 | 9 | 20.678 | 10 | 20.554 | Mean | 20.38223 |

4.2.1.3 Comparison between the unconstrained approach and the fair scheduled approach for Margin Adaptive Resource Allocation scheme

Figure 4.2.1.3.1: Comparison between Fair and unfair Scheduling using GA
It can be seen very clearly that in fair scheduled case the minimum transmit power is almost 4 times of the unconstrained case. It is obvious that if we want to maintain a minimum bit rate we have to use more power. So, fair scheduling may not give the optimum result, but they are more practical.

4.2.2 Rate Adaptive Approach by GA
4.2.2.1 Maximum sum capacity (in bits/s/Hz)Obtained by GA using Margin Adaptive Approach (Unconstrained Approach)
As stated previously, the throughput for an OFDMA system is calculated for a constant transmit power of 1W, Bandwidth of 16.25 MHz, and the AWGN of -80 dBW /Hz . The maximum sum capacity is calculated by GA for 10 times (Table ) and five of them are shown in the convergence curve (Figure....).

Figure4.2.2.1 Maximum throughput evaluation by GA (Unconstrained approach) Run | Maximum sum capacity(in bits/s/Hz) | 1 | 10.3075 | 2 | 10.4283 | 3 | 10.1091 | 4 | 10.4572 | 5 | 10.4328 | 6 | 10.1911 | 7 | 10.2353 | 8 | 10.1805 | 9 | 10.2279 | 10 | 10.4873 | Mean | 10.3057 |

Figure: 4.2.2.1 Convergence curve for RA approach (Unfair scheduling)

4.2.2.2 Maximum sum capacity (in bits/s/Hz) Obtained by GA using Margin Adaptive Approach (Constrained Approach)
The maximum sum capacity for fair scheduled approach is calculated by GA for 10 times (Table 4.2.2.2) and three of them are shown in the convergence curve (Figure 4.2.2.2 ).

Table 4.2.2.2 Maximum throughput evaluation by (Constrained approach) Rate Adaptive Approach (constrained) | Run | Maximum sum capacity(in bits/s/Hz) | 1 | 10.432 | 2 | 10.209 | 3 | 10.308 | 4 | 10.005 | 5 | 10.067 | 6 | 10.987 | 7 | 9.856 | 8 | 9.998 | 9 | 9.112 | 10 | 10.445 | mean | 10.1419 |

Figure 4.2.2.2: Convergence curve for RA approach (Fair scheduling)
4.2.2.3 Comparison between the unconstrained approach and the fair scheduled approach for Margin Adaptive Resource Allocation scheme
As our constraint was to transmit a minimum number of bits to each user, maximum sum capacity is almost sane in both the cases.
4.2.3 Comparison with previous algorithms in calculating the total transmit power in Margin adaptive approach
In following table comparison with some previous algorithms are mentioned ( all using same parameters)
Table 4.2.3.1: Comparison with previous algorithms Used method or Algorithm | Total transmit power(in dBm) for 4users | TDMA | 12 | FDMA | 15.5 | Jang algotihm | 16 | GA | 5 |

From the table it can be seen that GA provides a better result. So, we have proved that using GA for intelligent and efficient resource allocation is a good choice. 4.3 Combined Approach by MOGA and NSGA
In this section we have demonstrated convergence curve and discussed how our problem is handled using MOGA and NSGA. The Evolutionary algorithm parameters are same as before, parameters for calculating power is also same, but we are considering an adaptive power allocation scheme instead of constant power used in RA approach. The main objective of this section is to give a clear comparison between our combined resource allocation scheme using MOGA, NSGA and Margin adaptive, Rate adaptive scheme using GA .As stated before multi objective optimizations are used for mainly practical applications. So, we have demonstrated results in this section only for fair scheduling. But in case of comparison between all the algorithms in terms of execution time, results of unfair scheduling are also presented.
4.3.1 Combined Approach by MOGA
The Pareto optimal solution set for a particular run (Figure 4.3.1.1) is given below.

Figure 4.3.1.1: Pareto optimum set for a particular run

In the above figure, all the solutions are dominated. So, base station will now chose a solution based on a predefined priority. While allocating subcarriers to the users randomly, MOGA finds the optimum values as well as the corresponding subcarrier allocation (Figure 4.3.1.2)

Sub1 | Sub2 | Sub3 | Sub4 | Sub5 | Sub6 | Sub7 | Sub8 | 4 | 3 | 2 | 1 | 3 | 4 | 2 | 1 | Sub9 | Sub10 | Sub11 | Sub12 | Sub13 | Sub14 | Sub15 | Sub16 | 3 | 4 | 2 | 2 | 1 | 3 | 4 | 2 | Sub17 | Sub18 | Sub19 | Sub20 | Sub21 | Sub22 | Sub23 | Sub24 | 2 | 4 | 3 | 4 | 3 | 3 | 1 | 2 | Sub25 | Sub26 | Sub27 | Sub28 | Sub29 | Sub30 | Sub31 | Sub32 | 1 | 3 | 4 | 1 | 1 | 2 | 4 | 2 | Sub33 | Sub34 | Sub35 | Sub36 | Sub37 | Sub38 | Sub39 | Sub40 | 3 | 3 | 1 | 2 | 2 | 1 | 3 | 4 | Sub41 | Sub42 | Sub43 | Sub44 | Sub45 | Sub46 | Sub47 | Sub48 | 4 | 4 | 2 | 2 | 1 | 3 | 4 | 2 | Sub49 | Sub50 | Sub51 | Sub52 | Sub53 | Sub54 | Sub55 | Sub56 | 3 | 1 | 2 | 3 | 4 | 2 | 3 | 1 | Sub57 | Sub58 | Sub59 | Sub60 | Sub61 | Sub62 | Sub63 | Sub64 | 3 | 1 | 3 | 3 | 2 | 4 | 4 | 1 |

Figure: 4.3.1.2 Subcarrier allocation

So, base station allocates the subcarriers to users accordingly so that a minimum transmit power and maximum capacity is preserved. In our case we chose the solution which has the minimum transmit power from the pareto optimal solution set. Results from calculating minimum transmit power and maximum sum capacity 10 times using MOGA is given below and three of them are shown in Figure 4.3.1.3.
Table 4.3.1.1 Combined Margin and Rate Adaptive Approach (MOGA)

Combined Margin and Rate Adaptive Approach (MOGA) | Run | Minimum transmit power(in dBm) | Maximum sum capacity(in bits/s/Hz) | 1 | 12.33 | 8.74 | 2 | 8.34 | 5.98 | 3 | 8.46 | 6.54 | 4 | 8.84 | 6.65 | 5 | 8.43 | 6.42 | 6 | 8.45 | 6.52 | 7 | 14.4 | 8.6 | 8 | 12.56 | 8.75 | 9 | 12.45 | 8.66 | 10 | 8.86 | 6.43 | mean | 10.312 | 7.329 |

Figure 4.3.1.3: Pareto optimum set for three runs
4.3.2 Combined Approach by NSGA
Here, same parameters are used as used in MOGA. The output of NSGA from a particular run is given below (Figure 4.3.2.1)

Figure: 4.3.2.1: Solution set of NSGA for a particular run
Here, each ‘+’ represents one solution. Though it looks like there are a lot of solutions, and it will be tough to choose only one solution, but it can be solved in two ways. One is applying the concept of again finding the dominant solution among these solutions. But more 90% of these solutions are non-dominant. Secondly, the solutions are so closely spaced if we take the upper ceiling of transmit power and lower limit of the capacity, only a few solution is found in the final solution set(Figure 4.3.2.2). So, it becomes easier for Base station to choose a solution and performs a effective resource allocation.

Solutions

Figure 4.3.2.2: Solution set of Figure 4.3.2.1 after rounding the values

Results from calculating minimum transmit power and maximum sum capacity 10 times using NSGA is given in Table 4.3.2.2 and three of them is shown in Figure 4.3.2.3.
Table 4.3.2.2 Combined Margin and Rate Adaptive Approach (NSGA)

Combined Margin and Rate Adaptive Approach (NSGA) | Run | Minimum transmit power(in dBm) | Maximum sum capacity(in bits/s/Hz) | 1 | 11 | 8 | 2 | 13 | 10 | 3 | 12 | 10 | 4 | 10 | 6 | 5 | 12 | 8 | 6 | 12 | 8 | 7 | 11 | 8 | 8 | 11 | 10 | 9 | 12 | 10 | 10 | 13 | 10 | mean | 11.7 | 8.8 |

Figure 4.3.2.3: Solution set of NSGA for a particular run

4.4 Comparison between proposed algorithms

First a comparison is given between MOGA and NSGA for calculating maximum bit rate (Table 4.4.1 and Figure 4.4.1). Then a comparison is given between MOGA, NSGA and GA for calculating minimum transmits power in Table (Table 4.4.2 and Figure 4.4.2). All results are considered for fair scheduled case.

Table: 4.4.1: Maximum Sum capacity for 10 runs (fair scheduled) Run | MOGA | NSGA | | Maximum sum capacity(in bits/s/Hz) | Maximum sum capacity(in bits/s/Hz) | 1 | 8.74 | 8 | 2 | 5.98 | 10 | 3 | 6.54 | 10 | 4 | 6.65 | 6 | 5 | 6.42 | 8 | 6 | 6.52 | 8 | 7 | 8.6 | 8 | 8 | 8.75 | 10 | 9 | 8.66 | 10 | 10 | 6.43 | 10 | mean | 7.329 | 8.8 |

Figure: 4.4.1 Comparison between MOGA and NSGA in terms of bit rate

Table 4.4.2: Minimum transmit powers for 10 runs (fair scheduled)

Run | MA | MOGA | NSGA | | Minimum transmit power(in dBm) | Minimum transmit power(in dBm) | Minimum transmit power(in dBm) | 1 | 20.6803 | 12.33 | 11 | 2 | 20.559 | 8.34 | 13 | 3 | 20.106 | 8.46 | 12 | 4 | 20.053 | 8.84 | 10 | 5 | 21.064 | 8.43 | 12 | 6 | 19.998 | 8.45 | 12 | 7 | 19.976 | 14.4 | 11 | 8 | 20.154 | 12.56 | 11 | 9 | 20.678 | 12.45 | 12 | 10 | 20.554 | 8.86 | 13 | mean | 20.38223 | 10.312 | 11.7 |

Figure: 4.4.2: Comparison between Combined approach (MOGA, NSGA) and MA approach (GA) in terms of minimum transmit power.

From Table 4.4.1 and 4.4.2 and Figure 4.4.1, 4.4.2 we can see that our proposed combined scheme using GA and MOGA gives much better result than just results in MA scheme using GA. So, our proposed combined scheme is much better than MA scheme in terms of calculating minimum power. Again, from above tables and figures we can see that for power and bit rate calculation MOGA and NSGA almost provides the same results.
Now the most important achievement in our thesis is shown. A comparison between combined scheme using MOGA, NSGA and both MA and RA scheme using GA is given in terms of Execution time in following tables.( Table 4.4.3-4.4.6 ). The summary is shown in Figure 4.4.3.
Table 4.4.3 Execution times For Number of Subcarriers = 8 and Unfair scheduling

Run | Execution time of MA(in seconds)(By GA) | Execution time of RA(in seconds)(By GA) | Execution time of MA and RA together (in seconds) | Execution timeOf Combined scheme(in seconds)(By MOGA) | Execution timeOf Combined scheme(in seconds)(By NSGA) | 1 | 23.183 | 10.245 | 33.42 | 21.824 | 12.093 | 2 | 24.624 | 11.049 | 35.67 | 22.515 | 12.103 | 3 | 25.476 | 11.145 | 36.62 | 23.315 | 12.876 | 4 | 23.115 | 9.567 | 32.68 | 22.426 | 12.009 | 5 | 25.007 | 9.959 | 34.96 | 20.810 | 12.408 | 6 | 24.224 | 11.103 | 35.32 | 22.212 | 12.629 | 7 | 23.115 | 10.043 | 33.15 | 23.432 | 11.996 | 8 | 22.036 | 9.697 | 31.73 | 20.876 | 11.984 | 9 | 23.598 | 11.335 | 34.93 | 21.125 | 12.567 | 10 | 24.536 | 11.289 | 35.82 | 22.470 | 12.588 | Mean | 23.8914 | 10.5432 | 34.43 | 22.1005 | 12.3253 |

Table 4.4.4: Execution times For Number of Subcarriers = 8 and Fair scheduling Run | Execution time of MA(in seconds)(By GA) | Execution time of RA(in seconds)(By GA) | Execution time of MA and RA together (in seconds) | Execution timeOf Combined scheme(in seconds)(By MOGA) | Execution timeOf Combined scheme(in seconds)(By NSGA) | 1 | 19.72 | 12.55 | 32.27 | 22.02 | 18.85 | 2 | 20.56 | 11.86 | 32.42 | 22.08 | 17.67 | 3 | 19.14 | 10.76 | 29.9 | 21.45 | 18.64 | 4 | 18.78 | 11.87 | 30.65 | 22.56 | 16.56 | 5 | 20.56 | 13.87 | 34.43 | 21.56 | 17.56 | 6 | 21.78 | 13.77 | 35.55 | 20.88 | 18.32 | 7 | 19.56 | 12.87 | 32.43 | 21.67 | 19.56 | 8 | 18.89 | 13.76 | 32.65 | 22.45 | 20.87 | 9 | 18.76 | 13.32 | 32.08 | 21.34 | 16.54 | 10 | 18.54 | 12.56 | 31.1 | 20.45 | 16.34 | Mean | 19.629 | 12.719 | 32.348 | 21.646 | 18.091 |

Table 4.4.5: Execution times For Number of Subcarriers = 64 and Unfair scheduling Run | Execution time of MA(in seconds)(By GA) | Execution time of RA(in seconds)(By GA) | Execution time of MA and RA together (in seconds) | Execution timeOf Combined scheme(in seconds)(By MOGA) | Execution timeOf Combined scheme(in seconds)(By NSGA) | 1 | 122.27 | 30.259948 | 152.980 | 175.679 | 85.666 | 2 | 126.374 | 30.3648 | 156.667 | 180.321 | 81.511 | 3 | 125.465 | 30.214 | 155.739 | 184.105 | 82.682 | 4 | 123.435 | 31.110 | 154.545 | 176.123 | 81.365 | 5 | 121.675 | 29.420 | 151.095 | 173.461 | 84.586 | 6 | 128.264 | 31.472 | 158.736 | 172.235 | 85.662 | 7 | 126.453 | 32.319 | 158.772 | 170.471 | 80.365 | 8 | 123.212 | 32.678 | 155.891 | 182.323 | 84.232 | 9 | 130.717 | 32.605 | 163.322 | 182.149 | 87.368 | 10 | 131.213 | 31.385 | 162.598 | 181.235 | 85.266 | Mean | 125.9078 | 31.18277 | 157.0345 | 177.8102 | 83.8703 |

Table 4.4.6: Execution times For Number of Subcarriers = 64 and fair scheduling Run | Execution time of MA(in seconds)(By GA) | Execution time of RA(in seconds)(By GA) | Execution time of MA and RA together (in seconds) | Execution timeOf Combined scheme(in seconds)(By MOGA) | Execution timeOf Combined scheme(in seconds)(By NSGA) | 1 | 98.56 | 49.99 | 148.55 | 167.64 | 125.37 | 2 | 100.45 | 50.61 | 151.06 | 173.26 | 124.36 | 3 | 98.47 | 51.20 | 149.67 | 170.24 | 122.45 | 4 | 100.56 | 50.55 | 151.11 | 168.65 | 128.67 | 5 | 120.67 | 48.66 | 169.36 | 155.67 | 129.65 | 6 | 100.46 | 51.54 | 152 | 165.67 | 129.45 | 7 | 99.87 | 50.45 | 150.32 | 158.67 | 130.23 | 8 | 120.45 | 51.66 | 172.11 | 167.45 | 122.56 | 9 | 110.47 | 52.45 | 162.92 | 169.45 | 126.67 | 10 | 112.46 | 50.86 | 163.32 | 163.45 | 124.59 | Mean | 106.242 | 50.797 | 157.042 | 166.015 | 126.4 |

Figure 4.4.3: Comparison between Combined approach (MOGA, NSGA) and Sum of separate MA and RA approach (GA) in terms of Execution time.

Figure 4.4.3 shows that for a low number (8) of subcarrier both MOGA and NSGA outperform the sum of separate MA and RA using GA in terms of execution time in both fair and unfair scheduling. As the number of subcarriers (64) is increasing the complexity of computation also increases in MOGA and NSGA. But even for 64 subcarriers, combined approach using NSGA outperforms all other algorithms in term of execution time.
All the comparison clears several facts * All the proposed dynamic algoriithms overperforms the static ones( TDMA,FDMA) and jhang’s dynamic algorithm. * Proposed combined scheme using NSGA outperforms MA and RA resource allocation scheme in terms of optimizing resources as well as execution time. * Proposed combined scheme using NSGA shows almost equivelant results to our proposed combined scheme using MOGA but outperforms MOGA interms of execution time.