# DOA-Based Localization Method with Multiple ScreeningK-Means Clustering for Multiple Sources

Authors: Yankui Zhang; Daming Wang; Weijia Cui; Jiangdong You; Hao Li; Fei Liu
Journal: Wireless Communications and Mobile Computing
 (2019)

---

## Abstract

The existing angle-based localization methods are mainly suitable for the single source. Actually, there often exists situation which contains multiple target sources. To solve the problem of localization of multitarget sources, this paper presents aK-means clustering method based on multiple screening, which can effectively realize the localization of multiple sources based on DOA (direction of arrival) parameters. The method firstly establishes a cost function of position coordinates by using DOA parameters from the measuring position coordinates and then solves the cost function to obtain a complete set of real position coordinates and fuzzy position coordinates. As the distribution of real target coordinates is concentrated and the fuzzy target positions are scattered, the K-means clustering method is adopted to classify the coordinate set. In order to improve the positioning accuracy, a multiscreening process is introduced to screen the input samples before each clustering, and it can be finally concluded that clustering centers are the position coordinates of the target sources. Meanwhile, the complexity analysis and performance verification of this method are proposed. Simulation experiments show that this method can efficiently realize ambiguity-free, highly precise localization of multitarget sources.


---

## Body

## 1. Introduction

The existing two-step positioning method consists of two processes: parameter estimation and position calculation. The commonly used parameters mainly include time of arrival (TOA), time delay of arrival (TDOA), direction of arrival (DOA), and Doppler shift parameters [1–3]. The DOA parameter estimation is mainly based on array signal processing methods. The array signal processing methods have high accuracy, and they are simple to implement [4–7]. At present, the technology of DOA estimation based on array signal processing is relatively well developed, typical representatives are the MUSIC method, ESPRIT method, and root-MUSIC method [8–12].Localization is another important step to obtain the position coordinates of the target sources. Localization is generally based on parameter estimation. It mainly uses the geometric relationship between the observation position coordinates and the positioning parameters to establish the cost function of the target sources, and the source position coordinates can be obtained by solving the cost function [13, 14]. At present, typical methods include the least square method, Chan method, and Taylor-series expansion method. The least square method is used to solve the position coordinates in [15], and the position coordinates obtained by this method are suboptimal, not global optimal. In order to improve the least square method, [16,17] give a double least square position method, namely, the Chan method, which can obtain noniterative closed-form solutions, but it is sensitive to parameter errors and has poor performance under a low signal-to-noise ratio (SNR). The Taylor-series expansion method uses the Taylor series criterion to convert the nonlinear cost function into the linear form, and the target source coordinates can be obtained through the iterative processes. The authors of [18–21] introduced the general steps of Taylor series expansion position methods and analyzed the performance. The Taylor series expansion method can obtain better positioning accuracy through approximation and iteration, but it is sensitive to the initial values. In order to improve the robustness of the Taylor series expansion method, experts and scholars adopt different methods to optimize the initial values of Taylor series expansion. Li et al. [18] introduced the restriction conditions of the convergence region to ensure the convergence of iteration results. The authors of [19–21], respectively, adopted the steepest descent method and factor graph method to obtain a good initial value of iteration to improve the convergence probability of iteration process. Xiaowei et al. [22] combined the Chan method, Taylor-series expansion method, and Kalman filtering method to give a high-precision multipoint positioning method based on the TOAs. Location calculation is carried out by combining DOA parameters and TOA parameters or TDOA parameters in [23–27], which improve positioning accuracy. However, the observation stations are required not only to accurately obtain DOA parameters of target sources, but also to obtain TOA information.The above-mentioned methods are mainly aimed at the single-source model, and the position precision is not high. In order to solve the DOA-based multisource location, this paper presents a multiscreeningK-means clustering localization method. This method firstly establishes a cost function of the source position according to the coordinates of each observation position and DOA parameters and then solves the cost function to obtain a complete set of the source position coordinates. Because the obtained complete set contains “pseudotargets,” in order to eliminate the influence of the “pseudotargets,” the K-means clustering method is adopted to classify the real coordinates and the “pseudotargets.” To improve the positioning accuracy, screening samples are used as the input clustering data by the length of Euclidean distance, and the influence of fuzzy coordinates are gradually removed. Finally, the changeless clustering center can be obtained, which is the position coordinate of all target sources.The rest of this paper is organized as follows: Section2 introduces the localization calculation model based on DOA parameters; Section 3 presents the localization based on multiple screening K-mean clustering for multiple sources in detail and provides the step summary and the complexity analysis of this method ; Section 4 presents simulation experiments; and Section 5 summarizes this work.


## 2. Localization Model

It is assumed that there existD target sources transmitting plane waves to the measuring array. In order to calculate the position of the receiving signal source, the receiving station moves Q measuring positions. Each measuring position measures the DOAs of the target sources. The azimuth information of the target sources observed at the qth measuring position is θ1q,θ2q,…,θDq. For the convenience of expression, a two-dimensional coordinate system is established, and all observation positions are in the first quadrant. To simplify the calculation, the line of the measuring array is always parallel to the x coordinate axis. In practice, the line of the array may be nonparallel to the x axis; generally, it can be converted into the corresponding angle between the incoming wave direction and the positive x axis through simple coordinate rotation. If there is no special explanation, the following azimuth angles all refer to the angles between the incoming wave direction and the positive x axis. According to the spatial geometric relationship, one target source can be located by any two observation positions, which is located at the upper side or the lower side of the line determined by two observation positions. The target source only has one real position, and the other one is the “pseudotarget.” The spatial geometric relationship between observation point coordinates and target source position coordinates is shown in Figure 1.Figure 1
Geometric relation of observation point coordinates and target position coordinates.According to the geometric relationship of two-dimensional space,(1)xi,1p,q−xptanθip=yi,1p,q−yp,xi,1p,q−xqtanθiq=yi,1p,q−yq,(2)xi,2p,q−xptanθip=yp−yi,2p,q,xi,2p,q−xqtanθiq=yq−yi,2p,q,where xp,yp and xq,yq are the coordinates of the pth and qth observation positions; θip and θiq are the ith measured azimuths of the pth and qth observation positions; and the superscript represents the observation position index and the subscript represents the source target. In the angle-based localization, two observation positions can determine a target source, but the target source has angle ambiguity. xi,tp,q,yi,tp,q indicates the ith target position coordinates obtained from the pth and qth observation positions. Generally, the target position coordinates appear in pairs; that is, t∈1,2, i∈1,2,…,D, and p,q∈1,2,…,Q. According to the formulas (1) and (2), the position coordinates of the ith target source can be obtained as(3)xi,1p,q=yp−yq−xptanθip+xqtanθiq−tanθip+tanθiq,yi,1p,q=−yptanθiq+yqtanθip+xp−xqtanθiptanθiqtanθip−tanθiq,(4)xi,2p,q=yp−yq+xptanθip−xqtanθiqtanθip−tanθiq,yi,2p,q=yptanθiq−yqtanθip+xp−xqtanθiptanθiq−tanθip+tanθiq.Through the above analysis, it can be seen that as for the symmetry of DOAs, there is position ambiguity when two station positions are used for location calculation; that is, any two observation positions can obtain a group of source coordinates according to the DOAs, which include a true source location and a fuzzy source location. The fuzzy one is the “pseudotarget.”


## 3. Localization Based on Multiple ScreeningK-Mean Clustering for Multiple Sources

### 3.1. Method Introduction

According to the above analysis, the position coordinate of a target source can be determined by using two observation stations with a fuzzy location. Therefore, three observation positions can be used to uniquely determine a source coordinate and achieve the purpose of eliminating the false targets and preserving the true targets. The positioning schematic with three observations is shown in Figure2.Figure 2
Geometric relation of a source target coordinate and three observation positions.As shown in Figure2, three stations can determine six positions, and three of them have overlapped with each other: xi,1p,g,yi,1p,g,​xi,1p,q,yi,1p,q, and xi,1q,g,yi,1q,g are all real target locations in Figure 2. Red positions represent the “pseudotargets”; that is, xi,2p,g,yi,2p,g, xi,2p,q,yi,2p,q, and xi,2q,g,yi,2q,g are fuzzy positions. Since there are scenarios with multiple sources in the real environment, it is impossible to effectively match azimuth parameters by using the traditional three-station positioning method. In order to solve the problem of nonfuzzy solution of multitarget source position coordinates, the K-means clustering algorithm is introduced in this section. According to the information theory, the more useful the information obtained, the more accurate the source position coordinates estimated. Similarly, any two observation stations in a space can determine one group of source position coordinates, if all observation position coordinates are placed in the same two-dimensional space, the positions of true targets would be more and more concentrated, and the positions of pseudotargets would be more and more divergent. This is also the basis of the K-means clustering algorithm used in this paper, which can realize the multitarget position calculation without angle matching.Firstly, the possible position coordinates of all targets are calculated according to formulas (1) and (2), and there are 2D2CQ2 groups of position coordinates, where CQ2 represents the number of selected stations from Q observation positions. Therefore, the initial input sample number of the K-means clustering method is D2QQ−1; that is, the size of the complete coordinate set is D2QQ−1. The K-means clustering method firstly takes any D position coordinates in the complete set as an initial clustering center, and one initial clustering center represents a class. Then, the rest coordinate positions are classified according to the Euclidean distance. The Euclidean distance is defined as follows:(5)dxi,tp,q,yi,tp,q,xmid,ymid=xi,tp,q−xmid2+yi,tp,q−ymid2,where xmid,ymid is a clustering center, and xi,tp,q,yi,tp,q is the element in a complete coordinate set. After classification of all the elements of the complete coordinate set, the statistical average of the coordinates in the class is taken as the new clustering center, which is the updated clustering center. The general K-means clustering method is to repeat formula (5) for reclassification until the clustering center no longer changes. Actually, it is impossible to keep the clustering center completely unchanged. A smaller value should be selected as the threshold, and if the change of clustering center is smaller than this threshold, it means that the clustering method has converged.According to the introduction of the localization model, it can be seen that the true coordinate positions in the complete coordinate set are overlapped or distributed more intensively, while the “pseudotarget” positions are dispersed. Therefore, if the dispersed coordinates are forcibly classified in the clustering process, the final position accuracy will be decreased. In order to reduce the influence of “pseudotargets” on the positioning results, before repeating the reclassification, the complete set should be screened. In the screening process, the positions that are closer to the clustering center will be retained, and the farther ones will be discarded. As each of the two observation positions determines a true source position; that is,CQ2 common positions in the complete set are the true locations of the target sources, so each cluster center can only retain CQ2 closest coordinate positions and discard the rest. In this way, the final results of the output clustering centers are the D target source coordinates. The flow chart of the method is shown in Figure 3.Figure 3
Flow chart of multiple screeningK-means clustering method.


### 3.2. Summary of Method Steps

This paper gives a DOA-based localization method with multiple screeningK-Means clustering for multiple sources, which can realize the position solution of DOA parameters and is the core content of the two-step positioning technology. This method can not only realize the position solution of DOA parameters, but also can be used to realize the target source position solution of TOAs or DOAs, and TOAs. This method gives a location screening method when the number of sources or the number of observations are large, which effectively improves the position estimation accuracy. Based on the above analysis, the steps of this method are summarized as follows:Step 1. According to the observation positions and DOA information at each observation position, the cost function of the source coordinates is established as shown in formulas (3) and (4), and the complete set of position coordinates of all the sources is obtained.Step 2. Get the initial clustering center based on the complete coordinate set and input data into the K-means clustering method. Calculate the Euclidean distances between the elements of the coordinate set and the clustering center according to formula (5), and then, recluster according to the Euclidean distances.Step 3. Update the clustering center, then recalculate the Euclidean distances between each sample coordinate in the complete set and the new clustering centers, reserving the coordinate positions of the smallest CQ2 Euclidean distances as the new input data and reclustering with K-means method.Step 4. Update the cluster centers, and determine whether the updated cluster centers change with respect to the cluster centers in Step 3. Repeat Step 3 if the cluster centers change. If the cluster centers are stable, output the cluster centers as the location coordinates of the target sources.


### 3.3. Complexity Analysis

The complexity of this algorithm mainly comes from two parts: the solution of complete coordinate set and the application of multiple screeningK-means clustering method. The computation of complete coordinate set mainly includes formulas (3) and (4). The computational complexity is O16CQ2; that is, O8Q2−8Q. The K-means clustering method is an iterative method. The number of iterations depends on the selection of initial values of the input samples. For the sake of measuring the computational complexity conveniently, the number of iterations is set to ϒ. The complexity of the iteration process is mainly concentrated on the calculation of Euclidean distances of formula (5). The complexity of calculating Euclidean distances in an iteration operation is O3D3QQ−1, and the computational complexity of ϒ iterations is O3ϒD3QQ−1. In summary, the computational complexity of this method is O3ϒD3+8QQ−1.


## 3.1. Method Introduction

According to the above analysis, the position coordinate of a target source can be determined by using two observation stations with a fuzzy location. Therefore, three observation positions can be used to uniquely determine a source coordinate and achieve the purpose of eliminating the false targets and preserving the true targets. The positioning schematic with three observations is shown in Figure2.Figure 2
Geometric relation of a source target coordinate and three observation positions.As shown in Figure2, three stations can determine six positions, and three of them have overlapped with each other: xi,1p,g,yi,1p,g,​xi,1p,q,yi,1p,q, and xi,1q,g,yi,1q,g are all real target locations in Figure 2. Red positions represent the “pseudotargets”; that is, xi,2p,g,yi,2p,g, xi,2p,q,yi,2p,q, and xi,2q,g,yi,2q,g are fuzzy positions. Since there are scenarios with multiple sources in the real environment, it is impossible to effectively match azimuth parameters by using the traditional three-station positioning method. In order to solve the problem of nonfuzzy solution of multitarget source position coordinates, the K-means clustering algorithm is introduced in this section. According to the information theory, the more useful the information obtained, the more accurate the source position coordinates estimated. Similarly, any two observation stations in a space can determine one group of source position coordinates, if all observation position coordinates are placed in the same two-dimensional space, the positions of true targets would be more and more concentrated, and the positions of pseudotargets would be more and more divergent. This is also the basis of the K-means clustering algorithm used in this paper, which can realize the multitarget position calculation without angle matching.Firstly, the possible position coordinates of all targets are calculated according to formulas (1) and (2), and there are 2D2CQ2 groups of position coordinates, where CQ2 represents the number of selected stations from Q observation positions. Therefore, the initial input sample number of the K-means clustering method is D2QQ−1; that is, the size of the complete coordinate set is D2QQ−1. The K-means clustering method firstly takes any D position coordinates in the complete set as an initial clustering center, and one initial clustering center represents a class. Then, the rest coordinate positions are classified according to the Euclidean distance. The Euclidean distance is defined as follows:(5)dxi,tp,q,yi,tp,q,xmid,ymid=xi,tp,q−xmid2+yi,tp,q−ymid2,where xmid,ymid is a clustering center, and xi,tp,q,yi,tp,q is the element in a complete coordinate set. After classification of all the elements of the complete coordinate set, the statistical average of the coordinates in the class is taken as the new clustering center, which is the updated clustering center. The general K-means clustering method is to repeat formula (5) for reclassification until the clustering center no longer changes. Actually, it is impossible to keep the clustering center completely unchanged. A smaller value should be selected as the threshold, and if the change of clustering center is smaller than this threshold, it means that the clustering method has converged.According to the introduction of the localization model, it can be seen that the true coordinate positions in the complete coordinate set are overlapped or distributed more intensively, while the “pseudotarget” positions are dispersed. Therefore, if the dispersed coordinates are forcibly classified in the clustering process, the final position accuracy will be decreased. In order to reduce the influence of “pseudotargets” on the positioning results, before repeating the reclassification, the complete set should be screened. In the screening process, the positions that are closer to the clustering center will be retained, and the farther ones will be discarded. As each of the two observation positions determines a true source position; that is,CQ2 common positions in the complete set are the true locations of the target sources, so each cluster center can only retain CQ2 closest coordinate positions and discard the rest. In this way, the final results of the output clustering centers are the D target source coordinates. The flow chart of the method is shown in Figure 3.Figure 3
Flow chart of multiple screeningK-means clustering method.


## 3.2. Summary of Method Steps

This paper gives a DOA-based localization method with multiple screeningK-Means clustering for multiple sources, which can realize the position solution of DOA parameters and is the core content of the two-step positioning technology. This method can not only realize the position solution of DOA parameters, but also can be used to realize the target source position solution of TOAs or DOAs, and TOAs. This method gives a location screening method when the number of sources or the number of observations are large, which effectively improves the position estimation accuracy. Based on the above analysis, the steps of this method are summarized as follows:Step 1. According to the observation positions and DOA information at each observation position, the cost function of the source coordinates is established as shown in formulas (3) and (4), and the complete set of position coordinates of all the sources is obtained.Step 2. Get the initial clustering center based on the complete coordinate set and input data into the K-means clustering method. Calculate the Euclidean distances between the elements of the coordinate set and the clustering center according to formula (5), and then, recluster according to the Euclidean distances.Step 3. Update the clustering center, then recalculate the Euclidean distances between each sample coordinate in the complete set and the new clustering centers, reserving the coordinate positions of the smallest CQ2 Euclidean distances as the new input data and reclustering with K-means method.Step 4. Update the cluster centers, and determine whether the updated cluster centers change with respect to the cluster centers in Step 3. Repeat Step 3 if the cluster centers change. If the cluster centers are stable, output the cluster centers as the location coordinates of the target sources.


## 3.3. Complexity Analysis

The complexity of this algorithm mainly comes from two parts: the solution of complete coordinate set and the application of multiple screeningK-means clustering method. The computation of complete coordinate set mainly includes formulas (3) and (4). The computational complexity is O16CQ2; that is, O8Q2−8Q. The K-means clustering method is an iterative method. The number of iterations depends on the selection of initial values of the input samples. For the sake of measuring the computational complexity conveniently, the number of iterations is set to ϒ. The complexity of the iteration process is mainly concentrated on the calculation of Euclidean distances of formula (5). The complexity of calculating Euclidean distances in an iteration operation is O3D3QQ−1, and the computational complexity of ϒ iterations is O3ϒD3QQ−1. In summary, the computational complexity of this method is O3ϒD3+8QQ−1.


## 4. Simulation Experiments

In this section, the simulation experiments of the multiple screeningK-means clustering localization method are given. In order to measure the performance of the proposed method, the definition of the root mean square error (RMSE) is given, which is the deviation between the estimated source position coordinates (the final output cluster centers) and the real source position coordinates. The RMSE is defined as(6)RMSE=1TD∑j=1T∑i=1Dxi−x^i,j2+yi−y^i,j2,where xi,yi is the real location coordinate of the ith source, x^i,j,y^i,j is the estimated location coordinate of the ith source by the jth Monte Carlo experiment, and T is the Monte Carlo number. In order to verify the effectiveness of the proposed method, the position distribution scatter plots of the screening coordinates, the RMSE with angle deviation, and the RMSE performance with different number of observation points are given. The simulation conditions are set as shown in Table 1.Table 1
Simulation conditions for the experiments.
Simulation parameters
Value
Source coordinates
8000,4000
,
5000
,
−
3000
Observation locations
0,1400
,
6000,0
,
10000,50
,
16000,0
,
21000,10000
Monte Carlo number
T
=
200
DOA deviation
0
∼
0.5
∘Simulation 1.
Location distribution of input samples with each screening.
In this Monte Carlo experiment, location distribution of the initial complete coordinate set and coordinates distribution with first, second, and third screening are given. The angle deviation is 0.5 degree, and the simulation results are shown in Figure4; it can be seen from the scatter distribution figures that after screening of initial values, the interference of pseudo targets is effectively eliminated and the degree of aggregation of input samples is improved.Figure 4
Scatter plot of position coordinates of the input samples. (a) Initial sample, (b) with first screening, (c) with second screening, (d) with third screening.
(a)
(b)
(c)
(d)Simulation 2.
Performance simulation of RMSE with different angle deviations.
Localization methods based on DOA parameters are sensitive to angle deviation because even if the angle deviation is small, it will cause large position deviation in a long distance, and it changes approximately linearly with the increase of distance. The RMSE performance of the position accuracy with DOAs deviation of0∼0.5∘ is given in this Monte Carlo experiment, as shown in Figure 5. Simulation results show that when the angle deviation is small, the position estimation accuracy is high. With the increase of the angle deviation, the RMSE shows an upward trend. Whether small angle deviation or large angle deviation, this method can effectively calculate the position coordinates.Figure 5
RMSE performance with different angle deviation.Simulation 3.
RMSE performance simulation with different numbers of observation locations.
The more the number of observation locations, the more the sample coordinates obtained and the more valuable the information used. According to the knowledge of information theory, the positioning accuracy will be improved with adding useful information. This Monte Carlo simulation experiments of the RMSE performance when the number of observation positions is varied from 3 to 10. The simulation results are shown in Figure6. The simulation results indicate that when the number of observation location increases, the RMSE decreases. Moreover, the coordinates of observation locations have a great influence on the RMSE performance.Figure 6
RMSE performance with different numbers of observation points.


## 5. Conclusion

In order to achieve high-precision location of multiple sources without ambiguity based on DOA parameters, this paper introduces theK-means clustering algorithm into location measurement and presents a multisource localization method based on multiscreening K-means clustering. Firstly, the cost function of the target source position coordinates is established according to the observation position coordinates and the DOAs parameters, and the complete coordinate set of source positions is obtained by solving the cost function. In order to remove the “pseudotargets” in the complete set, the K-means clustering method is adaptively improved in this paper. The aggregation degree of the input sample positions is increased through multiple screening and gradually narrows the distance between the clustering center and the real target coordinates. Finally, the location measurement without ambiguity and high precision of multisources can be realized. Complexity analysis and simulation experiments are given to verify the effectiveness of the proposed method. This method gives a location screening method when the number of sources or the number of observations are large, which can not only realize the position solution of DOA parameters, but also can be used to realize the target source position solution of TOAs or DOAs, and TOAs.



---

*Source: 5643752-2019-09-11.xml*