Radio Resource Allocation Algorithm Based On Graph Theory In Femtocell Networks

As a complement and expansion of cellular network, femtocell has been widely used in mobilecommunication system. The emergence of femtocell gives new ideas to solve the indoor coverageand provides high system capacity and data rate. However, femtocell brings the problem of thecross-layer interference between the macrocell and femtocells as well as the same-layer interferencebetween femtocells. How to allocate resources efficiently to reduce interference and guarantee theQuality of Service (QoS) while improving the system throughput and spectrum utilizationefficiency has become an important research topic.This thesis introduces the basic concept of femtocell and OFDM technology. The downlinkinterference and different ways of spectrum allocation in macrocell and femtocell networks aredeeply studied. After giving the basic concepts of graph theory, the vertex coloring algorithm andchannel assignment problem are associated. Then the existing interference coordination algorithmbased on graph theory is researched and analyzed.The spectrum reuses issue based on the random graph in femtocell and cellular networks isresearched and analyzed by using the theory of the random graph. Formulas are derived and themaximum number and minimum number of resource blocks (RBs) are obtained to meet theminimum requirement of the system. Then they are compared with the simulation results of twoclassical heuristic algorithms based on vertex coloring of graph theory. The simulation resultsshow that the maximum value theoretical calculated gives a good estimate of the number of RBswhen the macrocell and femtocells using the different spectrum. When the macrocell users andfemtocells share the same spectrum and the probability of interference between the macro link andthe femtocell link is little, the number of required RBs is close to the minimum value theoreticalcalculated.A graph coloring based clustering algorithm for channel allocation is proposed to analysis thespectrum allocation problem in two layers networks. Firstly, the Signal to Interference plus NoiseRatio (SINR) of the macrocell user is calculated and the available subchannels of the correspondingset of femtocells which have large interference to the macrocell user are adjusted. Secondly, theundirected interference graph and the directed and weighted graph are constructed in femtocellnetworks. At last, each user is allocated all the available spectrum resources dynamically by usingan improved cluster based algorithm. The interference is mitigated in the whole network. Simulation results show that the proposed algorithm can improve the femtocells throughput and thespectral efficiency with the constraint on SINR requirements of macrocell users.Ajoint spectrum allocation algorithm based on graph theory is also proposed to reduce theinterference in OFDM multi-cell scenario that comprises of macrocells and femtocells. The ratio ofRBs which macrocell users occupied is obtained by genetic algorithm. After considering the impactof the macro base station and small scale fading to the femtocell users on different RBs, multiinterference graphs are established and the spectrum is allocated dynamically. The simulationresults show that the proposed algorithm can meet QoS requirements of the macrocell users andmaximize the total throughput of femtocells.