2-D DOA Estimation in a Cuboid Array Based on Metaheuristic Algorithms and Maximum Likelihood ()
1. Introduction
For a long time, antennas have been passive elements in communication systems. However, with the development of telecommunications involving cellular, multimedia and Wi-Fi systems, the necessity of enhancing the capacity of TX-RX systems, system performance and transmitted power has emerged.
Smart antennas are antenna arrays capable of dynamic identification of spatial signal signatures, such as the direction of arrival (DOA) of the signal. They are also called adaptive antennas because of the ability to suppress noise and interference. These antennas can be used to calculate beamforming vectors, which are used to track and locate the antenna beams of mobile users and thus improve the signals received [1].
An antenna by itself is not smart, so the term “smart antennas” refers to a group of antennas combined with smart signal processing algorithms. Figure 1 presents a generic illustration of these systems.
An antenna array is a set of sensors connected in a particular geometric arrangement in a signal processing system. This system should be able to combine the signals from each antenna to achieve high directivity and increased signal gain. In general, the arrangements are usually physically fixed. Signal processing algorithms take into account both signal and antenna array characteristics [1].
By estimating the incidence angle (DOA) of the electromagnetic waves in an antenna array, it is possible to estimate the position of the signal source. The DOA angle is the direction in which electromagnetic source radiation is located. This DOA angle is important for adjusting the weight of each antenna in the array to favor a specific direction and attenuate noise and interfering signals. The DOA estimation is a basic and central issue in sensor array signal processing, and it can be applied in many fields such as radar, sonar, communications.
The DOA estimation assists in beamforming techniques. This process consists of adjusting the antenna array to favor a given irradiation angle. Figure 2 presents a diagram with an antenna array receiving a flat wavefront. A significant weight w is assigned to the signal received by each antenna to produce the desired output y. The weight values are adjusted according to the DOA angle, favoring a certain direction of arrival. In Figure 2, the DOA angle is represented by
.
The beamforming technique enables directing the antenna radiation in a particular direction. In this way, the system capacity is increased, and the energy used may be reduced. Figure 3 compares two irradiation diagrams: one from an
Figure 1. Smart antennas: array of antennas combined with a smart signal processing system. Source: adapted from [2].
Figure 2. X(t) signals received by each antenna, with certain significance level w, to produce the output signal y. Source: adapted from [3].
Figure 3. Comparison of the radiation diagram of an omnidirectional antenna (case 1) with that of a smart antenna (case 2). Source: adapted from [3].
omnidirectional antenna and the other from a smart antenna. It can be noted that there is a greater directivity of antenna irradiation in case 2, thus favoring users and suppressing any noise coming from other directions.
The authors in [3] [4] present an approach for DOA estimation based on the maximum likelihood estimator. These techniques exhibit satisfactory performance when compared to other well-known algorithms in the field. In [5], the authors compare the performance of DOA estimation by considering selected antenna array geometries, thus demonstrating their advantages and disadvantages.
The multiple signal classification (MUSIC) algorithm is known in the literature as a robust and simple implementation algorithm. It is based on the orthogonality between the vectors that make up the direction matrix and the eigenvectors associated with the lowest eigenvalues of the correlation matrix, which correspond to the noise incident on the network elements. The method establishes a search mechanism for peak values of an established function [6].
The purpose of parameter estimation in processing noise-contaminated signals arriving from sensor arrays is to estimate parameters such as the DOA, the carrier wave propagation velocity or the temporal and spectral properties of signals such as amplitude, phase and frequency [7]. In this procedure, the number of wave sources, the arrangement geometry and statistical models of the signal and noise are known.
This work proposes to apply metaheuristic algorithms to enhance DOA estimation techniques by considering a function based on the maximum likelihood estimation technique as a function of evaluation [8]. The heuristic algorithms used are the genetic algorithm [9] and the firefly algorithm [10]. The performance results of these two algorithms are compared with those of the MUSIC algorithm. Heuristic algorithms are considered to be effective approaches for super-resolution DOA estimations such as Deterministic Maximum Likelihood (DML which are involved in nonlinear multi-dimensional optimization [11].
2. DOA Estimation
Flat wave incidence estimation using sensor arrays is an important topic in the field of signal processing. The sensor array consists of a set of sensors with a certain geometric arrangement in space. It is generally considered that this arrangement consists of identical and omnidirectional sensors; in other words, all sensors have the same gain regardless of the direction of wave incidence. All signals captured by the sensors are simultaneously sampled spatially. The sample vector in the array output is called the snapshot.
The estimated DOA value decreases as the signal-to-noise ratio (SNR) decreases the proximity of the incident angles increases and the number of sensors decreases.
In mobile communications, the estimation of the incidence angle mainly aims to achieve interference cancellation by forming an appropriate radiation pattern, which favors the reception of signals coming from one direction and at the same time nullifies interfering signals from other directions [2].
2.1. Signal Model and Arrangement Geometry
The signal source can be understood as any user transmitting data. Suppose that the m-th source produces a flat wave, as given by Equation (1).
(1)
where
is the amplitude of a signal varying with time;
is the carrier wave frequency;
is the wavelength in the propagation direction;
is the distance to the origin of a coordinate system; and
is the wave’s phase.
can be defined as a scalar representing the distance traveled between two sensors by the m-th source wavefront [4].
The signal captured by the k sensor due to the wave generated by the m source is given by Equation (2).
(2)
Consider a signal model with K sensors located in positions
and M incident flat waves in unit vector directions
. The value of M is known. The output of each sensor at time n (snapshot), considering the additive noise
, can be modeled according to Equation (3) [12].
(3)
Figure 4 shows the array geometry used in this work. It consists of 64 sensors arranged 4 × 4 × 4. The arrangement of the antenna is cuboidal, and the distance between each sensor is calculated according to the signal’s source frequency.
2.2. Deterministic Maximum Likelihood Estimator
The maximum likelihood estimator (MLE) is a parameter estimation method that is well known in the literature. Parameter estimates are effectuated directly from noise-degraded signal samples. The MLE is obtained from the probability density function of the sample vector. The advantage of the ML estimation is that it can be used to solve many complicated problems [8].
In this work, a variation of the MLE, called DMLE or deterministic maximum likelihood estimator, is adopted. As will be shown in this section, after some algebraic manipulations, this criterion leads to the minimization of a cost function
Figure 4. Cuboidal antenna array geometry (4 × 4 × 4).
that depends on the autocorrelation matrix of the samples. The minimum point is determined by m-dimensional searches.
The function to provide deterministic maximum likelihood estimation, FDMLE, is obtained from the probability density function of the sample vector and a parameter vector in the so-called likelihood function,
. This function is maximized by
, which is a generic parameter vector specified for each problem [13].
In this work, the noise present in the data vector
given by Equation (3) is considered to be white Gaussian noise with zero mean and variance
. This consideration also makes
itself a random Gaussian process, with the mean given by
and the correlation matrix given by
.
is the array of direction vectors, and
is the vector with complex amplitudes for the n-th snapshot.
The maximum likelihood function, for this case, is defined by [14]:
(4)
where
is the vector of signal frequencies;
is the noise variance; and K is the number of sensors (antennas) in the array.
According to [4], maximum likelihood estimates are defined as the arguments that minimize the negative of the log of Equation (4). Thus, we have:
(5)
Normalizing by N and neglecting some constant terms, we have:
(6)
Given the three independent parameters
,
, and
,
is fixed to estimate the other two parameters, as shown in [14]. The parameters
and
are calculated by Equation (7) and Equation (8).
(7)
(8)
where “tr” denotes the matrix trace,
is the covariance matrix of the samples and
is an orthogonal projector given by Equation (9).
(9)
where
is the K-order identity matrix.
Substituting Equations (7) and (8) into (6), we obtain the following equation:
(10)
where
(11)
FDMLE is a function that provides the deterministic maximum likelihood estimation (DMLE) of the parameter w, and it is also used as the evaluation function of the genetic algorithm and firefly algorithm.
3. Metaheuristic Algorithms
Most of the conventional optimization algorithms are deterministic, and among them are those that are based on function gradient information. An example is the Newton-Raphson method, which exhibits good performance for well-behaved functions [15]. However, regarding highly nonlinear, nonconvex, nondifferentiable, and nonsmooth problems, these gradient-based deterministic problems present convergence problems and often become stuck in local minima.
To circumvent this problem, it is necessary to use algorithms that are not based on the gradient of the function, such as stochastic algorithms. These algorithms, also called heuristic algorithms, randomly search for the best solution. This search is often somewhat targeted and ensures that the method uncovers a good solution [10]. Even if these algorithms do not offer an optimal solution, they can approach the overall optimal result and provide a good solution. Another positive point is that they are less affected by the behavior of each problem, making them more robust for many applications [10] [16].
In this work, two metaheuristic algorithms are utilized: the genetic algorithm (GA) and the firefly algorithm (FA).
3.1. Genetic Algorithm (GA)
One type of metaheuristic algorithm is the genetic algorithm. The genetic algorithm refers to a computational model that mimics the natural evolution based on Darwin’s theory of biological evolution, such as heredity, mutation, natural selection and recombination.
Genetic algorithms are implemented in such a way that a population of abstract representations of the solution is selected in search of better solutions. Genetic algorithms use probabilistic rules in their steps to determine the individuals of the population, following a probability density function, such as normal or uniform distribution, and not deterministic rules. The set of possible solutions of a genetic algorithm is called population. The population is made up of individuals, which in turn are composed of genes. Each individual is an abstraction of a possible solution so that the number of individual genes depends on each problem [9].
The genetic algorithm includes selection, crossover and mutation steps. In the selection stage, the best individuals are chosen as the parents. In [9], some ways to make this selection are presented, such as addicted roulette or tournament. In the crossover stage, there are combinations of the genes of the individuals chosen to be the parents in order to generate a new individual. Mutation is a modification added to the new individual’s genes, which introduces new types of genes into the population, thereby increasing the search space and avoiding local minimal [9].
In this work, a genetic algorithm was implemented to estimate the parameters
and
(DOA arrival angle) in a cuboid antenna array in a three-dimensional space. At the beginning of the developed algorithm, an initial population of thirty arbitrarily chosen individuals is generated, in which each individual has two genes. Each gene represents one of the parameters being estimated (
and
), as shown in Figure 5. Individuals are then evaluated by an objective function, which orders individuals from the smallest error to the largest error, that is, from the best to the worst individual. The valuation function used was FDMLE, based on the maximum likelihood criterion.
The stopping criterion of this algorithm was specified as the maximum number of generations. In this work, the maximum number of 100 generations was arbitrarily adopted. The technique of elitism was also inserted, that is, the maintenance of the best individual of the previous generation in the next generation. This approach ensures that, in the worst case, the worst individual of a given generation will still be better than or equal to the best individual of the previous generation. Therefore, elitism contributes to the algorithm converging to a good solution.
Next-generation parent selection occurs by tournament, where k individuals are chosen at random, and the best two will be the parents of a next-generation individual. The process is repeated until there are enough parents to keep the number of next generation individuals equal to that of the previous generation. The number k of individuals is determined by the
parameter. This parameter defines the percentage of the total population that will participate in the tournament. In this work,
was adopted; that is, from the thirty individuals of the population, twenty-one are randomly chosen for each tournament. This value attempts to contribute to a better choice of parents and simulates natural selection that acts on biological species. The most able parents produce more children, but the less able parents can also generate descendants. Priority should be given to individuals with an evaluation function, without completely disregarding those individuals with extremely low evaluation functions. If
is used, there is an increase in selection pressure and a risk of premature convergence, which causes the algorithm to fail to yield good results.
The exchange of genes between parents for the generation of children occurs in the crossing stage. A number
is randomly chosen, which is the probability decision variable. The value of
decreases with increasing generations but is a random value, as shown in Figure 6. If
is greater than
, where
is a random number between 0 and 1, the child will receive the gene from the first parent and otherwise will receive the gene from the second parent. This process
Figure 5. Genetic algorithm individuals with their two genes,
and
.
Figure 6. Decreased crossover rate with increasing generations.
occurs until the child has the same number of chromosomes as the parents. Figure 7 presents an example of the crossing between two individuals to generate a child with genes from both parents. Therefore, if
equals zero, the child receives the gene from the first parent, and if
equals one, the child receives the gene from the second parent.
In the mutation stage, a modification in a given gene occurs to perform the exploration of the search space. The procedure for changing the mutation rate was similar to the crossover rate case, although in an increasing direction (the mutation rate was increased, as opposed to the crossover rate, which was decreased). In this stage, it was defined that in the first generation, there is a 1% chance of individuals mutating and a 10% chance in the final generation. If there is a mutation, a mutation
that is applied to the gene is drawn. In this work,
was adopted; that is, when mutation occurs, each gene can have its value changed by up to 5%.
The new population is made up of parent-born children, plus the best individual of the previous generation (through elitism). The individuals are then evaluated again using FDMLE, and the algorithm is restarted.
3.2. Firefly Algorithm
There are several types of heuristic algorithms; it is currently estimated that there are over forty [17]. Many of these algorithms are inspired by the natural behaviors of some animals, such as swarms, ant colonies, bees, beetles and birds [18]. These algorithms utilize the principle of using a social behavior presented in a species and, from it, with their certain simplifications, elaborating mathematical codes to solve engineering problems [17].
Figure 7. Generic example of crossing between two individuals in the genetic algorithm.
The firefly algorithm was developed by Xin-She Yang and is based on the observation of the flashing firefly lights [10]. Bioluminescence is a biochemical process that produces light. For fireflies, this process has the following purposes: to serve as a mating ritual; to attract prey; and to function as a warning sign of nearby predators [19]. Therefore, the light signals of fireflies are of paramount importance for their survival. From this behavior of fireflies, a heuristic optimization algorithm called the firefly algorithm [10] was modeled.
As already mentioned, real fireflies are flying insects that glow using bioluminescence, presumably to attract mates. Each firefly may glow with a different intensity. In the firefly algorithm, fireflies that are better, that is, have a smaller error, emit a light with greater intensity. The better the representation of its objective function is in relation to the problem to be optimized, the closer this firefly is to the global minimum and the more intense the brightness is. In this way, other fireflies will also be attracted to brighter fireflies (close to the global minimum) and move away from lower luminosity fireflies (farther from the global minimum).
Light intensity is known to decrease according to the square of the distance [10]. Therefore, fireflies, although attracted to light, have a limited view of the bioluminescence of other fireflies. Equation (12) represents the luminous intensity G(r) as a function of a distance r.
(12)
where Gs is the light intensity of the source and r is the distance from the source.
Considering a light absorption coefficient
for a fixed distance r, one can write the light intensity G according to Equation (13).
(13)
where G is the original light source.
The expression
exhibits a singularity at
. Then, by combining this expression, which takes into account the effect of light scattering as a function of the inverse square of distance, with the expression of light absorption, one can approximate them in a Gaussian form according to Equation (14):
(14)
The attractiveness of a firefly
to other fireflies
is proportional to the light intensity of the fireflies
that the
firefly can see. The attractiveness
of one firefly for another is defined according to Equation (15).
(15)
where
is the attractiveness at
.
To calculate the distance between any two fireflies
and
, the Euclidean distance is used in a three-dimensional space. Moving a firefly i closer to a firefly j (which has superior brightness) is defined according to Equation (16).
(16)
The term
is the rectangular coordinate of the firefly. The second term of Equation (16) is related to attractiveness. The third term refers to a randomness added to the motion, so
is the randomness parameter (weight) and
is the vector of random numbers obtained from any probability distribution function [20]. If
, the movement has no randomness. On the other hand, if
and
, every move is random.
Choosing the parameters of the firefly algorithm depends on the problem to be optimized. However, there are some suggestions in the literature that apply to most cases [10]. It is suggested that
,
and
.
Interestingly, in the case of
, the attractiveness
tends to become constant with a value of
. This would equate to there being no absorption of light by light; i.e., the light does not decrease in all space. Therefore, the light of a firefly can be seen throughout the room, and a very bright spot can easily be found. On the other hand, if
, then
. This is the equivalent of all fireflies being unattractive to each other and their movements just being random.
To simplify the firefly algorithm, three rules were adopted: 1) it is assumed that all individuals are attracted to all others (there is no difference in sexuality); 2) the higher the brightness of a firefly is, the greater its attractiveness, such that it decreases with increasing distance due to the absorption of light by the medium; and 3) the brightness of a firefly is affected by its evaluation function (objective function), i.e., the better the value of its function is, the brighter the firefly. The brighter fireflies move (are attracted) to the other brighter fireflies [10].
Algorithm 1 summarizes the firefly algorithm developed in this paper.
4. Results
To perform the first simulations, a fixed position of the source was defined with
and
. As an evaluation criterion and comparison between algorithms, the square root of the mean square error (RMSE) between the real angle and the estimated angle is used for different SNRs, according to Equation (17). Table 1 presents the algorithm parameters considered in this work. These parameters were chosen arbitrarily, according the recommendations of [9] [21]. Several values were tested, and finally, those presented in Table 1 perform the smallest error.
(17)
Algorithm 1. FA implemented to estimate flatwave arrival angles.
Figure 8 shows the FDMLE surface for all
and
. This surface is an ideal case without any Gaussian noise, even though there are some local minima. In this work, one surface was generated for each SNR.
Since the signal sent from the source is degraded by white Gaussian noise, 100 experiments were performed for each SNR to ensure that the DOA angle estimation is not a particular case of specific noise and to show the robustness of the algorithms. The RMSE x SNR graphs (Figure 9) display the average RMSE for the 100 experiments. Obviously, the lower the RMSE value is, the closer the estimated angles are to the actual angles (smaller error).
Figure 8. FDMLE surface for all
and
.
It is possible to observe in Figure 9 that the firefly algorithm provides a smaller error than the MUSIC algorithm does for all SNRs from −10 dB to 10 dB. In addition, the genetic algorithm exhibits good performance, with a smaller error in general than that of MUSIC, except for some points with equal error such as SNR −2 dB.
To ensure that we can state that the firefly algorithm and genetic algorithm have better performance than the MUSIC algorithm for the case with a cuboid array and a single source, more simulations were performed. These simulations aim to guarantee that the metaheuristc algorithms (firefly and genetic algorithms) provide smaller errors for all angles of the source. To do that, angles
and
were varied from −90˚ to 90˚, one at a time, and the SNR was fixed at 0 dB. As shown in Figure 10, the
angle is fixed at −50˚, and
varies from −90˚ to 90˚. It is observed that the firefly and genetic algorithms provide smaller errors for almost all
angles than the MUSIC algorithm does. To analyze the performance with more accuracy, the mean error was calculated, as well as the standard deviation and minimum and maximum values, for all
angles. These values are presented in Table 2. They were obtained using Equation (17), and after that, it were calculated the mean, standard deviation, minimum and maximum value. It can be observed that the metaheuristic algorithms have smaller mean errors, standard deviations, and minimum and maximum errors than the MUSIC algorithm does.
Following the same methodology as that for
variation, the
angle was also varied. Figure 11 presents the comparison of the performance of the algorithms considered in this work. It is noted in Table 3 that, as in the previous case, the firefly and genetic algorithms also exhibit smaller errors than those of
Figure 9. Comparison of the estimation error of DOA of each algorithm versus SNR.
Figure 10. Comparison of the estimation error of DOA of each algorithm with a fixed SNR and variable
.
Table 2. Estimation error of DOA of each algorithm with variable
.
Table 3. Estimation error of DOA of each algorithm with variable
.
Figure 11. Comparison of the estimation error of DOA of each algorithm with a fixed SNR and variable
.
the MUSIC algorithm with respect to all statistical parameters (mean, standard deviation, minimum value, and maximum value).
5. Conclusions
In this work, it was proposed to apply the genetic algorithm and the firefly algorithm to estimate the incidence angles of electromagnetic waves in a specific type of antenna array, the cuboid array. The evaluation function of the algorithms was based on the maximum likelihood criterion. The results showed that the algorithms presented satisfactory results and were superior in most cases; that is, the algorithms provided smaller errors than those of the classic MUSIC algorithm.
It was also observed that the performance of heuristic algorithms is dependent upon their evaluation functions. It could be seen that with a decrease in the SNR, the FDMLE function exhibits a surface with more peaks and valleys so that heuristic algorithms encountered more difficulty in finding the global minimum; because of that, they exhibited greater error.
In future work, we intend to investigate the performances of other heuristic algorithms in DOA angle estimation and to test and compare the performance of these heuristic algorithms with other evaluation functions. We also intend to investigate the applications of other artificial intelligence techniques, such as artificial neural networks and fuzzy controllers, in DOA angle estimation.