Adaptive Beamforming with LMS

In a traditional beamforming application, the goal is to design an antenna whose radiation pattern points in a specific direction instead of just being purely isotropic. This directionality can be used as spatial filtering and is achieved in many different ways. One way is to use a directional antenna, such as a dish whose directionality is based on the physical direction the antenna is pointed. Another is to combine several antennas to form the desired radiation pattern or phased array.

A phased array antenna is able to create the desired radiation pattern by a judicious selection of complex weighting factors associated with each individual antenna. When added together the combined radiation pattern can be focused in a beam in the desired direction. The beam pattern is dependent on how many antenna elements are in the array, how they are spaced, and the frequency the antennas are receiving or transmitting on. In this project, the Uniform Linear Array will be used to demonstrate the properties of a phased array but there are many others.

A Uniform Linear Array (ULA) phased array is achieved by placing each antenna element along a straight line so that the antennas are equally spaced. The spacing of each element is dependent on the wavelength of the desired incoming signal.

This type of array simplifies the physical characteristics in the simulation later on but has a few practical drawbacks that will be discussed later.

While it is easy to calculate the complex weighting factors necessary for a ULA phased array when the angle of the desired incoming signal is known, but when the desired signal is transmitted at an angle the phased array is not pointed in, the signal will become severely attenuated and possibly useless to the receiver. Instead of having fixed complex weighting factors for the antenna elements, variable weights are introduced that can be changed or adapted to move the radiation pattern in the direction of the desired signal. This change would allow the phased array to track the desired signal in order to maintain the best signal quality. To change the weights accordingly, a digital signal processor will run a Least Mean Squares (LMS) algorithm in order to achieve the smallest error between a reference signal and the received signals.

LMS Algorithm

By applying adaptive control law to adaptive arrays from self-training systems Widrow introduced the LMS algorithm to beamforming.

The adaptive beamforming network consists of an array of antennas whose outputs are X.

$X = \{X_{0},X_{1},...,X_{n-1}\}$

Those outputs are then multiplied by the complex weights W.

$W = \{W_{0},W_{1},...,W_{n-1}\}$

To begin the adaptation process the error is calculated using a reference signal . The reference signal should be of the same form as the desired incoming signal. That error is fed into the LMS algorithm along with the input vector X and the set of weights W is updated as the algorithm tries to minimize the error. This process is then continued iteratively making successive corrections in the direction of the negative of the gradient vector.

Foundation Theory

The method of Steepest Decent is a recursive algorithm, that when the statistics of a signal are known is able to calculate the complex filter weights. But because that information is often unknown we must look for a way to estimate the statistics continuously. The LMS algorithm is based on the Steepest Decent method but uses an instantaneous estimation of the signal statistics to move in the direction of the negative of the gradient. Through the estimation process noise is introduced into the gradient.

The LMS algorithm starts out on the basis of minimizing the following function

$E\{|e(n)|^2\}$

This is the same as the Steepest Decent method. Then the update for the weight vector is

$w(n+1) = w(n) + \frac{1}{2}\mu[-\nabla J(n)]$

Where

$\nabla J(n) = -2p + 2Rw(n)$

R is the autocorrelation matrix and p is the cross-correlation vector. The LMS algorithm estimates the R matrix and p vector because they are dependent on the statistics of the received signal that is unknown. Using an instantaneous estimation

$\widehat{R} = x(n)x^h(n)$

$\hat{p} = x(n)d^*(n)$

So that

$\widehat{\nabla} = -2\hat{p}+2\widehat{R}\widehat{w}(n)$

By inserting this approximation into the steepest descent method for calculating the next filter weights we get

$w(n+1) = w(n) + \mu [d^*(n) -x^h(n)w(n)]$

From this equation, the filter weights can be iteratively calculated but there is still a problem of calculating the step size $\mu$

The step size $\mu$ influences the convergence of the LMS algorithm

$0 \textless \mu \textless \frac{1}{\lambda_{max}}$

Where $\lambda_{max}$ is the largest Eigenvalue of the autocorrelation matrix R. A smaller value of $\mu$ will cause the algorithm to converge slowly, while a larger value of $\mu$ will cause the algorithm to converge faster.

Programming Considerations

Translating the LMS Algorithm Into a functioning program in MATLAB there are a few considerations that need to be addressed. The LMS Algorithm procedure is straightforward and can be implemented directly from the summary equations. But in order for the algorithm to converge a suitable step size $\mu$ needs to be calculated based on the input parameters to the program. Otherwise, the output will explode resulting in a suboptimal solution.

Interfaces and Data

In order to preform a simulation of the LMS algorithm, of a ULA beam former, a software suite called MATLAB was used. The software allows for basic digital signal processing to be preformed using built in commands. The implementation of the LMS algorithm uses mostly basic arithmetic but because of the complex nature of the weighting factors it would have been significantly harder to implement in another language, such as C. Another benefit of MATLAB is the ability to create accurate graphs and images of the calculated data allowing the user to come to quick conclusions about the simulation inputs.

Because the simulation has many variables that affect the outcome of the output the software has been set up as a simple script that allows the user full control over the data entry such as ULA size, the step size $\mu$ , or the frequency of the desired signal to name a few. Results of the simulation will display several graphs as well as information of the display several values such as SINR and DOA error.

Software

Simulation

The simulation software implements a phased uniform linear array and the digital signal processing aspects of the incoming signals. The physical phased antenna layer consists of N isotropic antenna elements set a distance $d = \frac{\lambda}{2}$ from each other in a straight line. The incoming signal is modeled as

$x(t) = s(t)a(\theta) + i(t)a(\theta_{i}) + n(t)$

Where $s(t)$ is the desired signal at incident angle $a(\theta)$ , the interfering signal $i(t)$ at incident angle $a(\theta_{i})$ , and the Additive White Gaussian Noise (AWGN) $n(t)$ . The signals are modeled in the time domain by adding a delay $\tau$ appropriate to the angle the signal is coming from

$\tau = \frac{d}{c^{sin(\theta)}}$

Where d is the distance between the antenna elements, c is the speed of light, and $\theta$ is the DOA. The incoming desired signal becomes of the form.

$X_{m}(t) = cos(\omega(t + m\tau))$

Where the $m$ is the index of the antenna element, so each antenna element receives a delayed version of the signal depending on the index.

This incoming signal is generated in discrete-time instances in order to speed up the simulation. The initial weighting vector is set to arbitrary values. All the values of the incoming signal can be varied to perform a beamforming application on different signal Frequencies, Amplitude, Direction of arrival (DOA), and LMS step size. The LMS Algorithm implementation is straight from the final theoretical equation. After the weights have been iteratively updated, according to the reference signal $d(n)$ , during the allotted adaptation time the error is plotted over the adaptation time along with how the signal is adapted to match the reference signal.

Where the reference signal is of the same form as the desired signal. After that, the approximate signal to interference plus noise (SINR) is displayed along with the number of iterations the LMS algorithm took to achieve its current state. To show the radiation pattern of the final antenna array the array response $H(\theta)$ needs to be calculated from the complex weights $w$

$H(\theta) = \sum_{1}^{M} w(m)e^{-j(M-1)\omega \frac{d}{c^{sin(\theta)}}}$

The array response is the sum of each antenna response with respect to the angle $\theta$ . Where $0 \le \theta \le \pi$ this is because the ULA organization of the antenna causes the array response to be replicated at corresponding angles from $0 \le \theta \le 2\pi$ . The error in the calculated DOA is then displayed as well.

Matlab Code

	%Tom Schucker
	clear;

	%%
	c = 3e8; % Speed of light

	M = 16; % Number of antennas in ULA
	A = 2; % Amplitude of the desired signal
	f = 2.4e9; % frequency in Hz
	lambda = c/f; % Wavelength of desired signal
	d = lambda/2; % Distance between antennas in meters (m)
	theta = pi/3; % Desired incoming wave front DOA
	tau = (d/c)*sin(theta); % Time delay between recived signal

	Pn = .1; % noise factor

	% Interfearing signal variables
	theta_i = pi/4;
	tau_i = (d/c)*sin(theta_i);
	A_i = 0; % amplitude of interference
	f_i = 1e9;

	% complex adjustment weights vector initialization
	w = zeros(M,1);
	w(1) = 1;
	for n = 2:M
	w(n) = 1;
	end
	%w = rand(M,1);

	ts = 1/(500*f); % sample time
	t = 0:ts:(1/f)*6; % adaptation time

	X = zeros(M,1);% incoming signal vector initialization
	Error = zeros(1,size(t,2)); % Error signal vector initialization
	D = zeros(1,size(t,2));% Desired signal vector initialization
	Y = zeros(1,size(t,2));% recived signal vector initialization
	N = zeros(1,size(t,2));% noise signal vector initialization
	I = zeros(1,size(t,2));

	draw_dec_count = 1;
	frame_count = 1;
	polfig = figure;
	polfig.Visible = 'off';
	loops = floor(length(t)/10);
	pol_movie(loops) = struct('cdata',[],'colormap',[]);

	%run LMS algorithem
	mu = .04;% LMS step size

	for tl = 1:size(t,2)
	D(tl) = cos(2piftlts); % Reference Signal
	N(tl) = Pn*randn(); % AWGN
	for n = 1:M
	% Incoming signals
	X(n,1) = Acos(2piftstl + 2pif(n-1)tau) + N(tl) + A_icos(2pif_itstl + 2pif_i(n-1)tau_i);
	end
	S = w.*hilbert(X);
	Y(tl) = sum(S);
	Error(tl) = conj(D(tl)) – Y(tl);
	w(:) = w(:) + muXError(tl);% next weight calculation

	% Array Response
	if draw_dec_count > 10
	draw_dec_count = 0;

	omega = 0:0.0001:2*pi;
	H = 0;
	for m = 1:M
	H = H + w(m)exp(-1i(m-1)(d/c)sin(omega)2pi*f);
	end
	mag_H = abs(H);
	[mm, i] = max(mag_H);

	% draw frame
	polar(omega,mag_H);
	drawnow
	pol_movie(frame_count) = getframe;
	frame_count = frame_count + 1;
	else
	draw_dec_count = draw_dec_count + 1;
	end

	end

	polfig.Visible = 'on';
	movie(pol_movie);

	%%
	% plot adaptation process
	figure;
	plot(t, real(Error));
	title('LMS Error over time');
	xlabel('Time (s)');
	ylabel('LMS Error');

	figure;
	plot(t, D, t, real(Y));
	title('Beamforming Output Durring Adaptation Process');
	legend('Reference Signal', 'Received Signal');
	xlabel('Time (s)');
	ylabel('Signal Amplitude');

	% Signal to interference plus noise ratio
	SINR = snr(Y,N + I)

	% LMS iteration length
	iteration_length = size(t,2)

	% Calculate different approximated DOA
	DOA_1 = i*.0001
	DOA_2 = abs(pi – DOA_1)

	% Calculate the DOA error
	DOA_error = abs(min([DOA_1- theta, DOA_2- theta]))

	% Plot radiation patterns
	figure;
	polar(omega,mag_H);
	title('ULA Radiation Pattern Polar');
	xlabel('Degrees');
	ylabel('Magnitude');

	figure;
	plot(omega,mag_H);
	title('ULA Radiation Pattern Cartesian');
	xlabel('Radians');
	ylabel('Magnitude');

	mag_H2 = 10*log(abs(H));
	mag_H3 = mag_H2 – max(mag_H2);
	figure;
	plot(omega,mag_H3);
	title('Normalized ULA Radiation Pattern');
	xlabel('Radians');
	ylabel('Db');

view raw adaptive_beamforming_lms.m hosted with ❤ by GitHub

Performance

Evaluated on two paramenters ULA size and step size

ULA Length

To evaluate the LMS algorithm implementation used in the above MATLAB code the first metric that will be used is how many elements the ULA contains and what varying the number does to the various aspects of the implementation. Increasing the length of the ULA will allow a more focused beam this can be shown by graphing the array response of the calculated antenna weights. As the Array increases in elements the main lobes of the Array response lengthen and their width decreases. This essentially focuses the beam and can allow for better SINR. This is because when the beam width decreases, while maintaining its directionality interfering signals are attenuated to a higher degree.

Simulation Parameters

Name	Variable	Value
Amplitude of the desired signal	A	2
Desired frequency in Hz	f	2.4e9
Desired incoming wave DOA	theta	pi/3
Noise factor	Pn	0.1
Amplitude of the desired signal	A_i	1
Interfering frequency in Hz	f_i	1e9
Interfering wave DOA	theta_i	pi/4
LMS step size	mu	0.01
Sample time	ts	1/(500*f)
Adaptation time	t	0:ts:(1/f)*6

ULA Size	SINR (dB)	DOA Error
4	17.2850	0.4918
8	17.8972	0.8910
16	19.1970	0.0019
32	21.2776	0.0019
64	28.0938	0.0010

From the above figures, calculated SINR, and DOA error the LMS implementation can be shown to be more effective as the number of elements in the array increase. This is shown best by how the SINR increases as the number of antennas increases. The error in the DOA also decreases when starting at a 16-element array, so as the array increases in size the LMS algorithm is better able to track the signal. The increase in element size also enables the ULA to better reject the interference signal at $\frac{\pi}{4}$ radians shown by the normalized beam patterns below.

ULA Size	Interfering Signal Attenuation (dB)
16	-16.83
64	-41.73

The main reason why the LMS algorithm is doing poorly in detecting the DOA in length 4 and length 8 element arrays is that it cannot physically overcome the interfering signal due to its high amplitude, if the amplitude of the interfering signal is decreased we get the following result in the figure below that shows that LMS implementation is able to get a better approximation of the DOA.

ULA Size = 8 No Interference DOA Error = 0.0253

Using the maximum of the array response to calculate the DOA has its drawbacks because (8-array) has lobes in the correct direction but due to the size of the interfering signal large lobes are shown to be the DOA of the desired signal.

As the size of the ULA increases another aspect of the LMS algorithm is affected. For the previous simulation parameters as the number of elements in the array increases the convergence time of the algorithm decreases.

Comparing the two simulation results, using the above figures, the 32-element array converges about two times faster than the 8-element array. The complete simulation time was 3000 iterations; so using a 32-element ULA would allow the simulation time to be reduced by a factor of two with comparable SINR to the full simulation time. This aspect of convergence time and step size will be discussed next.

LMS Step Size

In the previous example, the array element size influenced the convergence time. The LMS step size $\mu$ determines how fast the algorithm converges or if it converges at all. To measure this the simulation parameters were set to a 16-element ULA and the LMS step size $\mu$ is varied while the other variables remain constant.

From the error result with the step size $\mu = 0.01$ the convergence time takes up the entire adaptation time for the error to decrease to an acceptable value. When the step size is increased to $\mu = 0.04$ the convergence time decreases, in which the error starts at a much higher value but then decreases to a small error value much more quickly in comparison.

To demonstrate the problem of using an LMS step size that is larger than the maximum allowable value the simulation step size was increased to $\mu = 0.05$ the error becomes unstable as shown in the figure below.

Conclusion

This implementation of adaptive beamforming using the LMS algorithm performs the necessary adaptation process to form a radiation pattern of a ULA in the direction of the desired signal. By introducing AWGN and an interfering signal into the array input a better real-life simulation is produced. This simulation environment more accurately tests this LMS implementation to see how well it would be able to perform under non-ideal circumstances that occur in nature. From the above analysis, the LMS implementation works well in these non-ideal conditions when the Array size is larger than 8 elements, rejecting interfering signals by a greater degree as the array size increases. One issue that remains problematic in the implementation is if the input signals have too large of combined amplitude the LMS algorithm becomes unstable due to a step size larger than $\frac{1}{\lambda_{max}}$ . This means that in a practical scenario the step size needs to be small enough to handle the maximum of the incoming signals, which could be difficult to know.

Since the implementation was programmed using the MATLAB software it does not have the same computational speed in real-time as other languages. But if the number of iterations that the LMS implementation uses to converge is used in order to show the speed and efficiency, we find that the convergence iteration number is highly dependent on the input signal, array size, and $\mu$ . In order to improve the current state of the program information on the actual environment the antenna system would be working in would provide for a more accurate representation of how well the LMS algorithm is working when compared to other systems. Another improvement that could be made is for the simulation to automatically decide which step size the LMS algorithm can use in the adaptation process based on the initial variables. In order to make sure the code works properly a large portion of time was spent setting up the simulation environment that the LMS implementation runs in. This includes determining how to set up the ULA along with how to receive the incoming desired signal based on the DOA. Along with the simulation environment the discretization of the signals allows for the program to iteratively generate the received signals and perform the LMS update in the same step. This lends itself to a more real-time application where the program only works on the current sample in order to generate a result.

Since there are numerous variables that the program uses to simulate the adaptive beamforming application there could be bugs in the code, the most likely place these would occur is in the LMS step size because it is not generated from the other input variables. The LMS algorithm has many uses and applications but for adaptive beamforming, it is a simple to program process and works well in situations where the overall computing power of a system is limited and the environment where this is used is well understood.

LMS Beamforming Convergance

As an additional step that shows the progression of the beamforming at each step I plotted the $H(\theta)$ at each step to show conceptually how the beam forms over time.

References

[1] Antenna-Theory.com: http://www.antenna-theory.com/arrays/main.php

[2] Dhande, R. J. (2014). ADAPTIVE BEAMFORMING USING LMS ALGORITHM . International Journal of Research in Engineering and Technology , 3 (5), 589-593.

[3] Haykin, S. (2014). Digital Communications Systems. John Wiley & Sons.

[4] Hogade, P., Chougale-Patil, M. J., & K.Bodhe, D. (2012). Analysis of Improved and Traditional LMS Beamforming Algorithm for Smart Antenna. Journal of Engineering Reaserch and Applications , 2 (3), 1816-1820.

[5] Naidu, P. S. (2009). Sensor Array Signal Processing. Boca Raton, Florida, United States: CRC Press.

[6] Nicolau, E., & Zaharia, D. (1989). Adaptive Arrays. New York, New York, United States: Elsevier.

[7] Rahaman, D. M., Hossain, M. M., & Rana, M. M. (2013). Least Mean Square (LMS) for Smart Antenna . Universal Journal of Communications and Network , 1 (1), 16-21.

[8] Reddy, B. S., Bhalchandra, D. A., & Ratnaparkhe, D. V. (2014). Adaptive Digital Beam Forming using LMS Algorithm . IOSR Journal of Electronics and Communication Engineering , 9 (2), 63-68.

[9] Shameem, L. S., & Khan, D. H. (2014). Performance Comparison of LMS, SMI, and RLS Adaptive Beamforming Algorithms for Smart Antennas. International Journal of Computer Science And Technology, 3 (2), 973-977.

This work was originally created for one of my various university projects and I have adapted it for this blog as I felt it had significant value for other students learning array processing.