Analysis of LMS and NLMS Adaptive Beamforming Algorithms

Analysis of LMS and NLMS Adaptive Beamforming Algorithms

PG Student.Minal. A. Nemade

Dept. of Electronics Engg.

Sinhgad College Of Engineering, Vadgaon(Bk.), Pune-41,India

Asst. Professor D. G. Ganage

Dept. of E&TC Engg.

Sinhgad College Of Engineering, Vadgaon(Bk.), Pune-41,India

Professor & Head M. B. Mali

Dept. of E&TC Engg.

Sinhgad College Of Engineering, Vadgaon(Bk.), Pune-41,India

Abstract – Mobile radio network with cellular structure demand high spectral efficiency for minimizing number of connections in a given bandwidth. One of the promising technologies is the use of Smart Antenna System which have become a practical reality after the advent of powerful, low cost and digital signal processing components. It is recognized as promising technologies for high user capacity in wireless networks by effectively reducing multipath and co-channel interference. The core of smart antenna is the selection of smart algorithms in adaptive array.These adaptive beamforming algorithms use different criterion to adapt the system for better performance and steer the main beam towards signal of interest. Basically, adaptive beamforming is technique in which array of antennas is exploited to achieve maximum reception in specific direction. An algorithm with small complexity, low computation cost, good convergence rate usually preferred. Step size is main parameter for both algorithm. In this paper, two non-blind algorithms: Least Mean Square (LMS) and Normalized Least Mean Square (NLMS) algorithms are discussed and results for both are shown.

Keywords:- Adaptive Beamforming, Convergence rate, LMS, NLMS, Smart Antenna System, Step Size

1. INTRODUCTION

   Smart antenna technology offers a significantly improved solution to reduce interference levels and improve the system capacity. Each users signal is transmitted and received by the base station only in the direction of that specific user. This drastically reduces overall interference level in the system. A smart antenna system consists of an array of antennas that together directs different transmission or reception beams towards each user in the antenna system. This method is called beamforming which is a signal processing technique used in sensor arrays for directional signal transmission or reception of signal[1]. This is achieved by combining elements in the array in a way where signals at particular angles experience constructive interference and while others experience destructive interferences. Beamforming process can be used at both the transmitting and receiving ends in order to achieve spatial selectivity. It has been found numerous applications in wireless communications, radio terminology, speech analogy, acoustics and biomedicine. Adaptive beamforming is used to detect and estimate the

   signal-of-interest at the output of sensorarray by means of data adaptive spatial filtering and the

   Interference rejection [2].

   The paper is organized as follows: Section II presents two adaptive beamforming algorithms. Section III presents result and discussion on bothalgorithm. Finally, Section IV concludes the paper.

2. ADAPTIVE BEAMFORMING ALGORITHM

   The adaptive beam forming algorithms can be classified into various categories: non blind adaptive and blind adaptive algorithms. Non blind algorithms use training sequence d(n) to update the complex weight vectors while blind algorithms do not but use some properties of desired signal. LMS, NLMS, and RLS are non-blind algorithms while CMA is blind algorithm. Basically, Adaptive beamforming is a technique in which an array of antennas is exploited to achieve maximum reception in a specified direction by estimating the signal arrival from a desired direction. It not only direct main beam in desired directions but also introduces nulls at interfering directions. Adaptive antenna arrays are able to adjust dynamically update their weights to the changing signal conditions [3] Thus weights are usually computed according to the characteristics of the received signals, which are periodically sampled. Most adaptive algorithms are derived by first creating a performance criterion which includes minimum mean squared error (MSE), maximum Signal-to-interference and noise ratio (SINR), maximum likelihood (ML), minimum noise variance, minimum output power, maximum gain and then generating a set of iterative equations to adjust weights such that the performance criterion is satisfied for given signal. These criteria are often expressed as cost functions which are typically inversely associated with the quality of the signal at the array output [4]. As the weights are iteratively adjusted cost function of signal becomes smaller and smaller in amount. When the cost function is minimized, the performance criterion is obtain and algorithms are said to have converged. The weight vectors are adjusted on account of factors like Rate of convergence, Tracking, Robustness and Computational requirements.

   1. LMS algorithm

      LMS algorithm was first developed by Widrow and Hoff in 1960. The design of this algorithm was stimulated by the Wiener-Hopf equation. By modifying the set of Wiener-Hopf

      Fig. 1. LMS adaptive beamforming network [2]

      equations with the stochastic gradient approach, a simple adaptive algorithm that can be updated recursively was developed. This algorithm was later on known as the least- mean-square (LMS) algorithm.It does not require measurement of correlation functions nor matrix inversion. Basic idea behind LMS filter is to approach the optimum filter weights by updating filter weights in manner to converge optimum filter weight. Algorithm starts by assuming small weights (zero in most cases) and at each step by gradient of mean square error weights are updated [5]. Most of the non- blind algorithms try to minimize the mean squared error between the desired signal d(n) and the array output y(n).

      As shown in Fig.1, the outputs of the individual sensors are linearly combined after being scaled using corresponding weights such that the antenna array pattern is optimized to have maximum possible gain in the direction of the desired signal and nulls in direction of interferers. The weights here will be computed using LMS algorithm based on Minimum Squared Error (MSE) criterion. Therefore, the spatial filtering problem involves estimation of signal from the received signal by minimizing the error between the reference signal d(n), which closely matches or has some extent of correlation with the desired signal estimate and the beamformer output y(n) [6].This is a classical Weiner filtering problem for which the solution can be iteratively found using the LMS algorithm. The signal x(n) received by multiple antenna elements are multiplied with the coefficients in a weight vector w(series of amplitude and phase coefficients) which adjusted the phase and the amplitude of the incoming signal accordingly. This weighted signal is summed up, resulted in the array output y(n). An adaptive algorithm is then employed to minimize the error e(n) between a desired signal d(n) and the array output y(n).

      e(n) = d(n) – y(n)…(1)

      For beamformer, the output at time n, y(n) is given by a linear combination of the data at the k sensors can be,

      y n = wH n x(n)…….(2)

      where,

      w = w1 wk H ..(3) and

      x n = x1 xk ..(4)

      where H denotes Hermitian (complex conjugate)transpose. The weight vector w is a complex vectors. The process of weighting these complex weights w1 wk H adjusted their amplitudes andphases suchthat when added together forms the desired beam.The LMS algorithm is an MMSE weight adaptationalgorithm that uses the steepest descent algorithm. The algorithm recursively computes and updates the weight vector. This is intuitively reasonable that successive corrections to the weight vector in the direction of the negative of the gradient vector should eventually lead to the MMSE, at which point the weight vector assumes its optimum value. The LMS algorithm avoids matrix inverse operation by using the instantaneous gradient vector J(n) to update theweight vector. Let w(n) denotes the value of the weight vector at time n. The update value of the weight vector at time n+1 is w(n+1) can be written as,

      w n + 1 = w n + 1 J(n) (5)

      2

      where is the step size which controls the speed of convergence and its value is usually between 0 to 1.An exact measurement of the instantaneous gradient vector is not possible since this would require a prior

      knowledge of both the covariance matrix Rand the cross- correlation vector r. Instead, an instantaneous estimate of the gradient vector J(n) is used which is given by,

      J n = 2r n + 2R n w(n)..(6) Where,

      R n = x n xH (n)… (7)

      And

      r n = d n x(n)… (8)

      are the instantaneous estimates of Randrdefined in Equation respectively. Substituting Equations (6), (7) and (8) into Equation (5), the weight vector can be found that,

      w n + 1 = w n + r n R n w n

      = w n + x(n) d n xH n w(n)

      = w n + x n e(n)..(9)

      The LMS algorithm can be described by the following three equations,

      y n = wH n x(n)(I)

      e n = d n y(n)…(II)

      w(n + 1) = w n + x n e(n).(III)

      The LMS algorithm is a member of stochastic gradient algorithms since the instantaneous estimate of the gradient vector is a random vector that depends on the input vector x(n). The rate of convergence is slow for a small value of but this gives a good estimation of the gradient vector since a large amount of data is taken into account [7]. The algorithm requires knowledge of the transmitted signal. This is accomplished by sending periodically some known pilot sequences that is known to the receiver. As stated above, step size is a positive real-valued constant which controls the

      size of the incremental correction applied to the weight vector as we proceed from one iteration cycle to the next. The performance of the algorithm depends on the step size parameter, which controls the convergence speed and the variation of the learning curve. LMS algorithm uses the Method of Steepest-Descent to update the weight vector.

   2. NLMS algorithm

   NLMS algorithm developed by Haykin in 2002. It is formulated as extension of LMS method [6]. It can persist over a wide range of step-sizes. The normalized least mean square (NLMS) algorithm has superior convergence properties than the least mean square (LMS) algorithm. However, weight noise effect of the NLMS algorithm is large so that the steady state residue power is larger than that for the LMS algorithm. A generalized NLMS algorithm is developed based upon the pseudo inverse of an estimated covariance matrix. A preliminary evaluation indicates improved performance can be attained but the implementation complexity might be high. Theoretically, LMS method is the most basic method for calculating the weight vectors. However in practice, an improved LMS method that is Normalized-LMS (NLMS) is used to achieve stable calculation and faster convergence. The NLMS algorithm can be formulated as a natural modification of the LMS algorithm based on stochastic gradient algorithm. Gradient noise amplification problem occurs in the standard form of LMS algorithm. This is because the product vector x(n)e*(n) in Equation (9) at iteration n applied to the weight vector w(n) is directly proportional to the input vector x(n). This can be solved by normalized the product vector at iteration (n+1) with the square Euclidean norm of the input vector x(n) at iteration n. The final weight vector can be updated by,

3. RESULTS AND DISCUSSION

   In this section, result of basic performance of adaptive beamforming algorithm by varying parameters related to algorithm are mentioned. The comparison between two training based algorithm is investigated by simulations using MATLAB® 7.8.0.(R2009a). Basic idea behind adaptive filter is to approach the optimum filter weights by updating filter weights in manner to converge optimum filter weight.

   Fig. 2. Combined MSE Curve for LMS & NLMS

   Algorithm starts by assuming small weights (zero in most cases) and at each step by gradient of mean square error weights are updated. So to study basic performance of adaptive algorithm first we have to observe MSE curve. For this, parameters to be considered here as number of bits are 500, channel length of 3, step size is 0.003, SNR of 20 dB with initialization of weight vector from zero.Combined MSE

   2

   w n + 1 = w n +

   a+ x n

   x(n)e..(10)

   curves for LMS and NLMS algorithms are shown in Fig. 2 and from figure it is clear that convergence speed of NLMS

   where the NLMS algorithm reduces the step size to make the large changes in the update weight vectors. This prevents the update weight vectors from diverging and makes the algorithm more stable and faster converging than when a fixed step size is used. Equation (10) represents the normalized version of LMS (NLMS), because step size is divided by the norm of the input signal to avoid gradient noise amplification due to x(n). Here the gradient estimate is divided by the sum of the squared elements of the data vector [8]. This algorithm has two distinct advantages over the least mean square (LMS) algorithm: potentially-faster convergence speeds for both correlated and whitened input data and stable behavior for a known range of parameter values independent of the input data correlation statistics. Moreover, the NLMS algorithm requires a minimum of one additional multiplication, division and addition over the LMS algorithm to implement for shift-input data.

   faster than LMS.

   1. Case 1

      As stated above performance of algorithm depends on step size parameter. So here we took three different step sizes 0.05(green), 0.025(red) and 0.005(cyan) are used.

      Fig. 3 Simulation of LMS for different step sizes

      From Fig. 3 and 4 it is observed that LMS takes more time to estimation compare to NLMS though it covers steady state error early. For smaller value of step size, both gives response with steady state error from the start of output.

   2. Case 2

      In this case we varied the amount of input noise by changing variance of noise data. Since variance is square of standard deviation, so we can consider different values of standard deviation for testing. The three different values of standard

      Fig. 4. Simulation of NLMS for different step sizes

      deviation of noise data taken are 0.05(green), 0.1(red) and 0.2(cyan). Results are shown in Fig. 4 and 5.

      Fig. 5.Simulation of LMS for different noises

      Fig. 6.Simulation of NLMS for different noises

      From Fig. 5 and 6 it is observed that the filter made by LMS changes mostly in stop band with change in noise variance while that of NLMS almost remains same. This shows that NLMS behavior towards change in noise variance remains consistent.

   3. Case 3

   We illustrated the effect of antenna element on resolution, using few representative beam-patterns.Aperture is the distance between the first and last elements. Figure 7 and 8 shows beam-pattern for N=4, 8, 16, and 32 with enter elements spacing fixed at d= /2. Aperture is the distance between the first and last elements. Therefore, the corresponding aperture in wavelengths is 2, 4, 8, and 16. Clearly, increasing the aperture yields better resolution with improvement for each of the successive two fold increase in apeture length.

   Fig. 7. Beam-pattern for 4, 8, 16, and 32 elements respectively (with common element spacing of d= /2) for LMS.

   Fig. 8. Beam-pattern for 4, 8, 16, and 32 elements respectively (with common element spacing of d= /2) for NLMS.

   From Fig. 7 and 8 it is depicts that the label of first side lobe is -13dB below the main lobe peak in case of LMS and -28dB below the main lobe peak in case of NLMS.

4. CONCLUSION

In this paper, two adaptive Non-blind beamforming algorithms are discussed which needs pilot signal to train the beamformer weights. These algorithms are used in smart antenna system in coded form to generate beam in the look direction. LMS algorithm is the most popular adaptive algorithm because of its low computational complexity. However, it suffers from slow and data dependent convergence behavior. From results mentioned in this paper should conclude that NLMS algorithm is an equally simple but more robust variant of the LMS algorithm which exhibits a better balance between simplicity and performance than the LMS algorithm. From results greater the aperture, the finer the resolution of the array which is its ability to distinguish between closely spaced sources.

REFERENCES

1. S.Radhika and SivabalanArumugam, A survey on different adaptive algorithms used in adaptive filters, International

   Journal of Engineering Research & Technology (IJERT), Vol. 1Issue 9, November- 2012.

2. S. K. Imtiaj, ItisahaMisra, and RathindranathBiswas Comparative study of BeamforminTechniques

   Using LMS and SMI algorithm in Smart antenna", IEEE International Conference on Communication, Devices and Intelligent Systems (CODIS), June 2012.

3. Alokpandey, L. D. Malviya, Vineet Sharma, Comparative Study of LMS and NLMS Algorithms in Adaptive Equalizer",

   International Journal of Engineering Research and Applications (IJERA), Vol. 2, Issue 3,pp.1584-1587, May-June 2012.

4. M. Yasin, Dr. ParvezAkhtar and Dr. Valiuddin, Performance analysis of LMS and NLMS for smart antenna system",

   International Journal of Computer Applications, Vol. 4 No. 9 August 2010.

5. A. Udawat, Dr. P. C. Sharma and Dr. S. Katiyal, Performance analysis and comparison of adaptive beamforming algorithms for

   smart antenna systems",IJRRAS pp. 55-59, April 2010.

6. Muhhamad Salman Razzaq and Noor M. Khan,Performance comparison of adaptive beamforming algorithms for smart antenna

   system", World Applied Science Journal(WASJ)11, Vol. 7, pp. 775-785, July 2010.

7. ShaheraHossain, Mohammadtariqul Islam and Seiichi , Adaptive Beamforming algorithms for Smart Antenna

Systems",International Conference on Control and Systems , pp. 754-758, May 2008.