Blind Carrier Frequency Offset Estimation Based on Gravitational Search Algorithm for Interleaved OFDMA Uplink Systems

Blind Carrier Frequency Offset Estimation Based on Gravitational Search Algorithm for Interleaved OFDMA Uplink Systems

Ann-Chen Chang

Department of Information Technology Ling Tung University

Taichung, Taiwan 408, R.O.C.

AbstractThis study deals with carrier frequency offset (CFO) estimation for interleaved orthogonal frequency division multiple access (OFDMA) uplink systems. Firstly, the gravitational search algorithm (GSA) with the center-symmetric (CS) trimmed correlation matrix and the multiple signal classification (MUSIC) criterion is presented for the purpose of efficient estimation. It has been shown that the estimate accuracy of the searching-based estimator strictly depends on the number of search grids used during the peaks searching process, which is time consuming and the required number of search grids is not clear to determine. However, the searching grid size is no need to know previously for the proposed GSA- based approach. Meanwhile, the advantage of inherent interleaved OFDMA signal structure also is exploited to conquer the problems of local optimization and the effect of ambiguous peaks for the proposed estimators. Finally, several simulation results are provided for illustration and comparison.

Keywords Carrier Frequency Offset; Interleaved OFDMA; Gravitational Search Algorithm; Multiple Signal Classification.

1. INTRODUCTION

   Emerging as a promising technology for next-generation wireless communications, the orthogonal frequency division multiple access (OFDMA) has drawn a lot of attention due to its high bandwidth efficiency and robustness to narrowband interference. OFDMA inherits from orthogonal frequency division multiplexing the weakness of being sensitive to inaccurate frequency references [1]. Inaccurate carrier frequency offset (CFO) will disrupt the orthogonality among subcarriers and lead to inter-carrier interference as well as multiple access interference (MAI), which degrades the system performance. In OFDMA uplink systems, every user transmits its signal to base station (BS) through different channel, thus the received signals at the BS are the mixture of all users. Due to the different propagation delays and channel attenuations, each user has different time delay and CFO at the receiver [2]. The estimation of time delays and CFOs all become multiple-parameter estimation problems. So this requires an accurate CFOs estimation and compensation method which becomes a more crucial task in multiuser environments in OFDMA uplink.

   For the interleaved OFDMA uplink systems, a blind CFO estimator [2] based on the estimation of signal parameters via rotational invariance technique (ESPRIT) exploits the inherent signal structure without pilot symbols. For the searching- based minimum variance distortionless response (MVDR) [1] and multiple signal classification (MUSIC) [3] estimators, the searching complexity and estimating accuracy strictly depend

   on the number of search grids used during the search, which is time consuming and the required number of search grids is not clear to determine. Unfortunately, the neighboring peaks cannot be distinguished for the MVDR and MUSIC estimators under relatively low signal-to-noise ratio (SNR) and large active users [4]. This implies that one users original peak location is pulled into an adjacent users range, severely distorting the original peak location [4]. It is well known that the polynomial root-version estimator has been proposed to improve the searching-based estimation [1, 5]. The resolution threshold performance of root-MVDR [1] and root-MUSIC

   [4] estimators is better than that of MVDR and MUSIC estimators, respectively, but for the noises dominant situation the appearance of both methods threshold performance is opposite.

   Recently, a novel heuristic search algorithm, called gravitational search algorithm (GSA), has been proposed motivated by the law of gravity and mass interactions [6]. It is characterized as a simple concept that is both easy to implement and computationally efficient. In GSA, the individuals, called agents, are a collection of masses which interact with each other based on the Newtonian gravity and the laws of motion. All agents move to a new place, the direction and distance are determined by their velocities. The agents share information using the gravitational force to guide the search toward the best location in the search space. By changing the velocities over time, the agents are likely to move toward the global optima. In this study, the feasibility of applying GSA to the MUSIC criterion is investigated for accurate CFO estimation of interleaved uplink OFDMA. First, in conjunction with the centro-symmetric (CS) trimmed correlation matrix [7] and the MUSIC criterion, the estimate performance of the centro-symmetric MUSIC (CSMUSIC) estimator can be improved under the low SNR case. Therefore, with a self-searched GSA and CSMUSIC scheme, the proposed CSMUSIC-GSA estimator does not require conventional spectral search, and can improve the CFO estimate accuracy. At each iteration, every agents can choice an appropriate acceleration along every dimension of search space according to its own situation. Finally, the proposed GSA-based estimators develop the CFO estimation by taking advantage of inherent structure of interleaved OFDMA signals. By dividing the whole possible CFO range into several smaller search ranges, the maximum value of fitness function is searched in each smaller range to get each users CFO. Therefore, the proposed estimators can conquer the effect of ambiguous peaks and local optimization.

2. BACKGROUND

   1. Signal Model

      Consider the interleaved uplink of an OFDMA system with N subcarriers in which K active users simultaneously communicate with the BS through an independent multipath

      channel. The N subcarriers are interleaved into Q (Q K)

      where ()T denotes the transpose operation. Then, the ensemble correlation matrix of (2) is R E{YYH } AR AH 2I , where E{} and ()H denote the expectation and Hermitian operations, respectively. R E{SSH } is the correlation matrix of S and I is a

      s

      s

      subchannels, each of which has P N / Q subcarriers. And,

      each subcarrier is exclusively used by only one user. Subchannel qk contains the subcarriers with index

      Q Q identity matrix. For finite received signals samples, R is replaced by the estimated sample average R (1/ FP)F Y( )Y( )H and F is the total blocks of

      1

      {qk ,Q qk , , (P 1)Q qk } and the value of qk k 1

      observation. The cost function of the searching-based MVDR

      estimator [1] with the search grid are defined as

      with k 1, 2, ,Q . After removing the cyclic prefix (CP),

      the received signal of one OFDMA block at BS can be

      expressed as y(n) K r (n) z(n) , n 0, 1, , N 1 ,

      S ( ) Max [aH ( )R -1a( )]1

      MVDR

      (3)

      k 1 k

      where z(n) is the additive white Gaussian noise with zero

      where a( ) is the CFO scanning vector.

      z

      mean and variance 2 . The discrete channel impulse

      T

      between the kth user and BS is characterized by a Lk order finite impulse response filter as hk [hk (0), hk (1), , hk (Lk 1)] . The channel frequency response of the kth user is

   2. Searching-based MUSIC estimators

   The MUSIC is a noise subspace-based estimator for high resolution CFO estimation. Assume that the number of active users K is known. Then, the eigenvalue decomposition

   (EVD) of R is R Q e eH E EH E EH , where

   (v) Lk 1 h (l) exp( j2lv / N) for v 0, 1, , N 1

   i 1 i i i s s s z z z

   k l 0 k

   2 are the eigenvalues

   1 2 K K 1 Q z

   [2]. Let k (qk k ) / Q denote the effective CFO of the

   kth user, k (0.5, 0.5) denote the kth users CFO

   of R in the descending order. ei are the corresponding orthonormal eigenvector associated with i for

   normalized by the subcarrier spacing 2 / N , then the

   i 1, 2, , Q . Moreover, E [E E ] , both

   received signal sample from the kth user is given by

   Es [e1 e2

   eK ]

   and

   s z

   Ez [eK 1 eK +2

   eQ ]

   are

   P1

   2 np

   2 nk

   orthogonal and span the signal subspace and noise subspace

   rk (n) X k ( p)Hk ( p) exp{ j

   }exp{ j }

   P P

   (1)

   corresponding to R , respectively.

   s diag{1, 2 , , K }

   p0

   and

   z diag{K 1

   , K 2

   , , Q } . Furthermore,

   Es spans

   z k

   k z

   where

   X k ( p)

   is a set of P data streams of the kth user,

   the same signal subspace as that spanned by {a(

   K

   )}

   .

   k k 1

   Hk ( p) represents the sample from Hk (v) at v pQ qk .

   Thus, we have EH a( ) 0 and aH ( )E 0 for

   The structure of (1) has a special periodic feature with every

   k 1, 2, , K . The cost function of the MUSIC estimator

   samples,

   r(n P) K

   exp( j2k )rk (n)

   , where

   with the searching grid defined as [3] is given by

   k 1

   (0 Q 1) is an integer. In one OFDMA block,

   S ( ) Max [| aH ( )E EH a( ) |]1

   (4)

   n0

   {y(n)}N 1 can thus be arranged into a Q P

   matrix

   MUSIC z z

   The whole possible range ((0.5) / Q, (Q 0.5) / Q) is

   y(0)

   y(P)

   y(1)

   y(P 1)

   y(P 1)

   y(2P 1)

   divided into Q smaller search ranges, and then the search

   Y

   (2)

   rang ((qk 0.5) / Q, (qk 0.5) / Q)

   is set for the

   kth

   user

   when q belongs to the user k . The maximum value of cost

   y(N P) y(N P 1) y(N 1) k

   k

   function is calculated in each smaller range to get

   Therefore, Equation (2) in one block can be expressed as

   Y A( )S Z , where A() [a(1 ) a(2 ) a(M )] with

   respectively, rather than finding the K peaks in the whole range. Through K searches, { }K can be obtained. Hence,

   k k 1

   a( ) [1, e j 2 k , , e j 2 (Q1)k ]T

   , Z is a Q P

   noise

   Q q

   for k 1, 2, , K .

   k

   matrix,

   S D (BW)

   with W is a P P

   inverse discrete

   k k k

   To improve the CFO estimating accuracy, it can be

   T

   Fourier transform (IDFT) matrix, and indicates an

   further dealing R

   with a CS trim to mitigate the finite

   element-by-element product.

   B [b1 b2 bK ]

   with

   sample effect. Let R denote a sample estimate of R . If we

   b [X

   (0)H (0), X

   (1)H (1), , X

   (P -1)H (P -1)]T

   and

   assume that R is a CS matrix [7], i.e., R I RI , where

   Q

   k k k k k k k Q Q

   T

   D [d1 d2 dK ]

   with dk

   [1, e j 2 k / P , , e j 2 ( P1)k / P ]T ,

   I denotes the exchange matrix and () is the conjugate operation. A sample correlation matrix with the above

   property can be easily obtained by way of performing

   Q Q

   R 0.5(R I R I ) . Therefore, since R is a Toeplitz

   structure, R can be expected to be a better estimate of R

   than R is. Here, R is to replace R for performing EVD.

   where rand j is a random number in [0, 1] . According to the law of motion, the acceleration of an agent is proportional to the result force and inverse of its mass, so the acceleration of all agents should be calculated as

   Then, the improved noise subspace Ez

   can be obtained.

   acck (t 1) F k (t) / M

   (t)

   (8)

   Therefore, the CS trim is applied on the MUSIC estimator, and then the resulting improved estimator is termed CS- MUSIC estimator.

   The estimate performances of the searching-based CFO estimators are governed by the scanning grid size. Smaller grid size can improve estimate accuracy, but the required computational load also has relatively larger. For increasing

   i i ii

   where Mii is the mass of agent i . The updating formula of gravitational and inertial masses of agent i follows as bellow:

   Fitnessk (t) worstk (t)

   estimate performance and searching efficient, this study

   m i

   (9)

   presents the GSA-based optimization to replace the spectral searching approach. Therefore, the proposed GSA-based estimators with the MUSIC or MVDR criterion can increase the estimate accuracy and have robust capability in both of the low SNR scenarios.

   i bestk (t) worstk (t)

   i

   where Fitnessk (t) is the fitness value of the agent i at time

   t . Then, worstk (t) and bestk (t) are defined as follows:

3. GSA-BASED CFO ESTIMATION

   GSA is inspired from Newtons theory and can be

   bestk (t)

   j

   max

   j{1,…, NP }

   Fitnessk (t)

   (10)

   j

   considered as a collection of agents (candidate solutions) whose have masses proportional to their value of fitness function. During generations, all masses attract each other by

   worstk (t)

   min

   j{1,…, NP }

   Fitnessk (t)

   the gravity forces between them. A heavier mass has the bigger attraction force. Therefore, the heavier masses which are probably close to the global optimum attract the other

   For simplify, let Mai M pi Mii Mi , and

   i i j 1 j

   M (t) m (t) / NP m (t) . The velocity and position of the

   masses proportional to their distances. It starts with randomly

   ith

   agent for the kth

   user are calculated as

   i i i i

   placing all agents in search space. Suppose a system with NP

   i

   agents and k

   represent the position of ith

   agent, where k

   velk (t 1) rand velk (t) acck (t 1)

   (11)

   denotes the

   kth

   dimension of agent (the

   kth

   active user).

   Then during all iterations, the gravitational force from agent j on agent i at a specific iteration time t is defined as follow [6]:

   k (t 1) k (t) velk (t 1)

   i i i

   where randi is a random number in the interval [0, 1] .

   (12)

   F

   ij

   k G(t)

   M pi (t) Maj (t)

   Rij (t)

   ( k (t) k (t))

   (5)

   At first all agents are initialized with random values and each agent k (0) is a candidate solution which represents the

   j i

   i

   desired impinging angle. After initialization, velocities for all agents are defined using (11). Meanwhile the gravitational

   where

   i j 1, 2, , NP

   and

   k 1, 2, , K .

   M aj is the

   constant, total forces, and accelerations are calculated as (6), (7), and (8), respectively. The positions of agents are

   active gravitational mass related to agent j ,

   M pi

   is the

   calculated using (12). If the movement of agent exceeds the

   passive gravitational mass related to agent i ,

   G(t) is

   searching space, the position of agent will be re-generalized

   gravitational constant at time t , is a small constant, and

   Rij (t) is the Euclidian distance between two agents i and j . The G(t) is calculated as

   randomly. Also, the fitness function of the desired kth user obeys the CSMUSIC criterion as bellow

   i i z z i

   Fitnessk (t) [aH ( k (t))E EH a( k (t))]1

   (13)

   G(t) G0 exp{t / Ns }

   (6)

   Finally, the CSMUSIC-GSA estimator will be stoppd by meeting an end criterion and return the best solution.

   where G0

   and are initial value of gravitational constant

   Abbreviations and Acronyms

   and descending coefficient, respectively, Ns is maximum number of iterations. The total force that acts on agent i at iteration time t is calculated as

   NP

4. SIMULATION RESULTS

   For illustrating the performance of the proposed estimators, several simulation results are conducted. For comparison, the results of the ESPRIT [2], MUSIC [4], root-

   i j ij

   F k (t) rand F k (t)

   j 1, j i

   (7)

   MUSIC [4], MVDR [1], root-MVDR [1], MVDR-GSA, and

   MUSIC-GSA estimators are also provided. It is noted that the fitness functions of MVDR-GSA, MUSIC-GSA, and CSMUSIC-GSA estimators are (3), (4), and (13), respectively.

   The parameters in the OFDMA uplink system are

   K 8 ,

   number of particles and the number of iterations for GSA-

   N 1024 , Q 32 , and P 32 . All OFDMA signals were

   based estimators are

   N p 12

   and

   Ns 80 , respectively. It

   k l

   k l

   generated with binary phase-shift-keying (BPSK) modulation and the average received signal power from all users is the same. Each user transmits signal to BS through independent multipath channel. The channel taps hk (l) are modeled as statistically independent Gaussian random variables with zero mean and an exponentially decaying power profile, E[h (l)2 ] e(l /5) , 0 l L 1, where is a normalized

   k k

   factor used to set the channel power to unity and Lk 10 [2]. As indices of evaluation, the mean square error (MSE) and the input SNR of the kth user were defined as

   also demonstrates that both of large agent and iteration numbers have better estimation resolution. The total required complex multiplications (CM) of the estimators contain the CM of computing fitness (objective) function and the CM of search (iteration) procedure. For computing the fitness function, the CM of the GSA-based and searching-based estimators are equal. However, the proposed advantage is the reduction of computational complexity by reducing the number of the search while maintaining comparable

   performance. According to [4], a proper choice is 104 in

   the scenario range [0 dB, 30 dB] . Assume that all the

   1

   MSE (1/ M )

   K

   k 1

   ( )2

   and

   searching grid of searching-based estimators are

   104 ,

   k z

   SNR 20log E[r (n)2 ]/ 2 , where is the number of Monte Carlo runs. For all simulations, the CFOs are

   {0.4041, 0.3355, 0.0407, 0.1175,

   then the number of searching F1 10001. But, the calculating fitness function number of the CSMUSIC-GSA is only

   0.1254, 0.2193, 0.3612, 0.4091} . For searching-based estimators, the proper searching grids are set to 104 in the scenario range [0 dB, 30 dB] [4]. In GSA, the gravitational constant G(t) is set using (6), where G0 =100 ,

   =20 , and a small constant = 510-3 . All GSA start with

   random initializations and are terminated if the maximum

   N p Ns 960 . However, the required N p and Ns of the GSA-based estimators are less than those of the searching- based estimators for all SNR cases, respectively. It is clearly

   that the proposed GSA-based estimators have high searching

   efficiency.

   0

   10

   10

   iteration (the total age of system) Ns is reached. Each of the -1

   simulation results presented is after one OFDMA block

   MVDR-GSA, SNR = 0dB

   MVDR-GSA, SNR = 10dB

   MVDR-GSA, SNR = 20dB

   MVDR-GSA, SNR = 30dB

   processed and is the average of

   103

   runs with

   -2 MUSIC-GSA, SNR = 0dB

   10 MUSIC-GSA, SNR = 10dB

   MUSIC-GSA, SNR = 20dB

   independent noise samples for each run.

   -3 MUSIC-GSA, SNR = 30dB

   MSE

   10 CSMUSIC-GSA, SNR = 0dB

   CSMUSIC-GSA, SNR = 10dB

   -4 CSMUSIC-GSA, SNR = 20dB

   0

   10

   MVDR-GSA, SNR = 0dB

   MVDR-GSA, SNR = 10dB

   -1

   10 MVDR-GSA, SNR = 20dB

   MVDR-GSA, SNR = 30dB

   -2 MUSIC-GSA, SNR = 0dB

   10 MUSIC-GSA, SNR = 10dB

   MUSIC-GSA, SNR = 20dB

   -3 MUSIC-GSA, SNR = 30dB

   10 CSMUSIC-GSA, SNR = 30dB

   -5

   10

   -6

   10

   -7

   MSE

   10 CSMUSIC-GSA, SNR = 0dB

   CSMUSIC-GSA, SNR = 10dB

   10

   2 4 6 8 10 12 14 16 18 20

   Number of Agents

   -4 CSMUSIC-GSA, SNR = 20dB

   10 CSMUSIC-GSA, SNR = 30dB

   Fig. 2. MSE versus the number of agents.

   -5

   10 0

   ESPRIT

   root-MVDR

   root-MUSIC MVDR MUSIC

   CSMUSIC

   MUSIC

   MVDR-GSA

   MUSIC-GSA

   CSMUSIC-GSA

   10

   -6

   10 -1

   10

   -7

   10

   10

   0 10 20 30 40 50 60 70 80 90 100 -2

   Number of Iterations

   MSE

   10

   Fig. 1. MSE versus the number of iterations. -3

   We investigate the effects of parameters {N

   p , Ns } on the 10

   -4

   10

   MSE performance with SNR as parameters. Fig. 1 depicts -5

   MSE versus the number of iterations Ns for GSA-based

   -6

   10

   estimators under the number of agents (particles)

   N p 12 ,

   whereas Fig. 2 depicts MSE versus the number of agents N p for GSA-based estimators under the number of iterations Ns 80 . It also demonstrates that the performance of the

   GSA-based estimators heavily depend on the selected the number of iterations and the number of agents. In the scenario range [0 dB, 30 dB] , the proper choices of the

   -7

   10

   1 2 3 4 5 6 7 8 9 10

   Number of Blocks

   Fig. 3. MSE versus the number of blocks.

   Fig. 3 shows the results of MSE versus the number of blocks under SNR=15dB . Clearly, increasing the number of blocks induces the performance improvement for all estimation methods. It shows that all GSA-based approaches have the same convergence speed. Fig. 4 presents MSE of the CFO estimation versus SNR. By using the correlation matrix with a CS trim to mitigate the finite sample effect, the CSMUSIC estimator has better performance improvement especially under the low SNR case. However, the statistical behavior of the root-MVDR estimator for a single data block appears difficult to establish. Observe that the accuracy of the CFO estimation of the searching-based estimators is governed by the search grid size whereas all GSA-based estimators do not suffer from this limitation. Again, these figures are presented to verify the efficiency of the proposed estimators.

   1

   ESPRIT

   root-MVDR

   root-MUSIC MVDR

   MUSIC

   CSMUSIC

   MVDR-GSA

   MUSIC-GSA

   CSMUSIC-GSA

   10

   0

   10

   -1

   10

   -2

   10

   MSE

   -3

   10

   -4

   10

   -5

   10

   -6

   10

   REFERENCES

   1. C. C. Shen and A. C. Chang, Blind CFO estimation based on decision directed MVDR approach for interleaved uplink OFDMA systems, IEICE Trans. Communications, vol. E97-B, no. 1, pp. 137145, Jan. 2014.

   2. J. H. Lee, S. Lee, and K. J. Bang, Carrier frequency offset estimation using ESPRIT for interleaved OFDMA uplink systems, IEEE Trans. Vehicular Technology, vol. 56, no. 5, pp. 32273231, Sept. 2007.

   3. Z. Cao, U. Tureli, and Y. D. Yao, Deterministic multiuser carrier- frequency offset estimation for interleaved OFDMA uplink, IEEE Trans. Communications, vol. 52, no. 9, pp. 15851594, Sept. 2004.

   4. A. C. Chang, Blind CFO estimation based on decision directed MUSIC technique for interleaved uplink OFDMA, Journal of the Chinese Institute of Engineers, vol. 38, no. 5, pp. 573582, Oct. 2015.

   5. Y. Y. Wang and S. J. Yang, On the CFO estimation for interleaved OFDMA uplinks, Journal of the Franklin Institute -Engineering and Applied Mathematics, vol. 353, no. 1, pp. 256263, Jan. 2016.

   6. E. Rashedi, H. Neamabadi-Pour, and S. Saryazdi, GSA: a gravitational search algorithm, Information Sciences, vol. 179, no. 13, pp. 22322248, June 2009.

   7. J. P. Delmas, On adaptive EVD asymptotic distribution of centro- symmetric covariance matrices, IEEE Trans. Signal Processing, vol. 47, no. 5, pp. 14021406, May 1999.

   -7

   10

   0 5 10 15 20 25 30

   SNR (dB)

   Fig. 4. MSE versus SNR.

5. CONCLUSIONS

This study has presented GSA-based searching CFO estimation methods with the MVDR/MUSIC criterion, named as the MVDR-GSA, MUSIC-GSA, and CSMUSIC-GSA

estimators, to achieve the CFO estimate accuracy under a single data block. By dividing the whole possible CFO range into Q smaller search ranges, the maximum value of fitness

function is calculated in each smaller range to get each users CFO. Therefore, the convergence of GSA to the global maximum is confirmed.

ACKNOWLEDGMENT

This research was supported by the Ministry of Science and Technology under grant number MOST 105-2221-E-275- 001.