# Multipath Cluster-Assisted Single Station Localization Based on SSA-GA in Outdoor NLOS Environment

Authors: Xi Liao; Sen Wang; Yang Wang; Yanting Che; Jihua Zhou; Jie Zhang
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

In this paper, we propose a novel multipath cluster-assisted single station localization method based on a genetic algorithm-based improved salp swarm algorithm (SSA-GA) to improve localization accuracy in an outdoor non-line-of-sight (NLOS) propagation environment. The scattering area model is presented which scatterers are considered Gaussian distribution for outdoor NLOS environments. The geometrical properties of propagation paths, such as angle of arrival and time of arrival, are jointly utilized to construct pseudoscatterer distribution. In order to filter the interference scatterers distributed outside the scattering region, the Gaussian kernel-based algorithm is developed. Furthermore, SSA-GA is proposed to solve the positioning objective functions constructed by pseudoscatterers clustering accurately. Results confirm the practicability of our newly proposed method, and the positioning error is less than 5% in outdoor NLOS propagation environment.


---

## Body

## 1. Introduction

In recent years, position location (also called localization or positioning) is a key application for the fifth generation (5G) of mobile communication technology, which has been a growing interest for a variety of applications such as navigation, industrial mines, rescue operations, and traffic management [1–3]. By measuring the range and the angle of the received signals between the mobile device and base stations based on the known locations of other reference points, the precise location knowledge of the transmitted source signal from a mobile station (MS) can be determined. Unfortunately, the majority of outdoor scenarios are characterized by the non-line-of-sight (NLOS) propagation conditions, due to specular reflections from obstacle surfaces such as mine cars, roadways, and buildings. Consequently, the localization environment is even more complex, which compromise the localization accuracy of current positioning technologies. Accurate and quick position location of MS is critical in urban environments under NLOS propagation conditions, especially for the implementation of the Federal Communications Commission’s (FCC) E-911 [4].In NLOS propagation environments, accurate single-site localization using a single base station (BS) for a wireless source signal is an attractive technique due to its convenience in deployment and operation compared with multiple-site localization techniques. A large number of researchers are actively working towards achieving an acceptable accuracy of single base station localization methods by using the measured parameters of multiple path signals, such as time of arrival (TOA), angle of arrival (AOA), and received signal strength (RSS). Details may refer to [5–10]. Time difference of arrival (TDOA) has been widely used in localization due to its low time synchronization requirements. In reference [11], the target position is estimated by using the transmission time difference between multiple different nodes and the target. Considering that three nodes can locate the target, a weighted average location algorithm based on Cramér–Rao lower bound (CRLB) is proposed to weight the average target positions estimated by different nodes. The weight is determined by the CRLB corresponding to the estimated target position. The simulation and measurement results show that the positioning error is less than 1 m in the indoor scenario. In addition, since TOA and RSS are both efficient over long and short distances, respectively, it is studied recently that with the combination of TOA and RSS, the spatial geometric distribution among the source, scatterers, and reflectors is used to construct the positioning objective function. In order to use multipath RSS-TOA to locate the target, an iterative generalized trust region subproblem (GTRS) framework is proposed in [12] to approximately solve the nonconvex maximum likelihood problem. The performance of GTRS model is further improved in [13] by considering that the directivity of the target will have a great impact on RSS measurements in different directions. Moreover, in reference [14], a second-order cone programming (SOCP) framework with convex hull constraints and soft regularization is proposed to solve the RSS-TOA localization problem, and the unknown transmission time and power information are considered to improve the robustness of the localization algorithm. Even though the method in literature [11–14] can use multipath information to locate target in NLOS propagation scenarios, however, it requires some assumptions or a priori conditions. For example, in [11], it is assumed that there are sight distance paths between multiple nodes and targets, and in [12–14], it is assumed that the NLOS measurement error of each multipath is the same, resulting in that the positioning algorithm is not applicable to actual NLOS propagation scenarios. Under NLOS propagation conditions, estimating the target positions accurately is challenging and has not been fully studied yet.The motivation of this paper is threefold. First, we use the Gaussian kernel-based algorithm to filter interference scatterers outside the scattering region. Second, an improved salp swarm algorithm (SSA) is proposed to determine the accurate location of source signal by enhancing the global search performance and robustness in NLOS environments. Last, we evaluate the performance of the proposed method, Levenberg-Marquardt (LM) algorithm, and SSA algorithm.


## 2. Scattering Region Model

The present problem is aimed at determining the location of source signal, e.g., a mobile station (MS), in a NLOS environment by using a single base station (BS) based on scattering area model. The Gaussian-based scattering area model is introduced to describe spatial geometric distribution of scatterers and MS, which can be used in achieving high precision under NLOS propagation conditions [15], compared with the conventional ring of scattering (ROS) model and the disk of scattering (DOS) model [16]. The MS-BS geometry is given in Figure 1.Figure 1
Illustration of the MS-BS geometry based on the scattering area model.Although the NLOS propagation environments might involve multiple-bound reflection and refraction paths, single-bounce reflection is assumed in this paper due to well-fitting for modelling the multipath propagation in outdoor areas. Furthermore, we assume that the source signal is scattered by the scatterersS1,S2,⋯,SN in the scattering area SA1,SA2,⋯,SAM to reach the base station (BS), where each multipath signal corresponds to a scatterer. The i-th path can be parameterized by the propagation distance Li (measured as the propagation distance between the MS and the BS) and the azimuth AOA θi (measured from the positive x-axis). The propagation distance of the i-th path from MS to BS is Li=c×ti,i=1,2,⋯,N, where c denotes the speed of light and ti is the TOA of the i-th multipath signal. The objective is to determine the unknown MS position, denoted in the Cartesian coordinate as x,y.In order to take full advantage of multipath information, pseudoscatterers are introduced. The pseudoscatterer is equivalent to the transmitter position corresponding to the received multipath signal in LOS propagation environment, and each available multipath corresponds to a pseudoscatterer. A certain geometric relationship between the distribution of pseudoscatterer and scatterers and target is depicted in Figure2, where Si′ denotes the pseudoscatterers corresponding to the i-th multipath and ri represents the signal propagation distance from the i-th scatterer to MS. The target positioning process is as follows.Figure 2
Pseudoscatterers distribution.


### 2.1. Step 1: Extraction of Pseudoscatterer Centres

In this paper, the BS is deployed at a known position, denoted as (xB, yB) in the Cartesian coordinate in Figure 2. Use the propagation distance Li and the AOA θi of the i-th path to determine the pseudoscatterers location xi′,yi′, which can be expressed in available information form as
(1)xi′=Li×cosθi+xByi′=Li×sinθi+yB.Letx^j,y^j,j=1,2,⋯,M represent the centres of the scattering area. Note that if in the azimuth AOA, the propagation distance parameters for all paths corresponding to the scattering centres have already been estimated in advanced, the positioning objective function can be constructed to estimate the target position.The clustering algorithm can be used to obtain the pseudoscatterer clustering centres ofS1′,S2′,⋯,SM′. After that, the multipath parameters of the scattering area centres can be obtained from the pseudoscatterer clustering centres by (1). The corresponding parameters Lj,θj are given as follows:
(2)Lj=x∧j′2+y∧j′2θj=arctany∧j′/x∧j′,where x^j′,y^j′ is the cluster centre of the pseudoscatterer.


### 2.2. Step 2: Construction of Positioning Objective Function

In this paper, it is assumed that the scattering area centres in the urban environment are known to bex^j,y^j,j=1,2,⋯,M. The centre of the scattering area can be obtained with the aid of satellite map or the distribution of surrounding buildings. The signal propagation distance is equal to the sum of the distance of the signal from BS to the scatterer and from the scatterer to MS, which can be calculated as
(3)x−x∧j2+y−y∧j2=Lj−x∧j−xB2+y∧j−yB2,j=1,2,⋯,M,where xB,yB and x,y are the locations of BS and MS, respectively. lj, i.e., the distance from MS to the centre of each scattering area, is shown as
(4)lj=Lj−xj−xB2+yj−yB2,j=1,2,⋯,M.Taking theM-th scattering centre as the reference, the distance difference between the other scattering centres and the M-th scattering centre to the MS can be expressed as
(5)x−xM2+y−yM2−x−x∧j2+y−y∧j2=lM−lj,j=1,2,⋯,M−1.In fact, due to the presence of parameter estimated errors, the target position in (5) does not have a closed-form solution. The solution process needs to be transformed into a nonlinear optimization problem. We can devise the objective equation as a set of errors, which can be defined as follows:
(6)φjx,y=x−xM2+y−yM2−x−x∧j2+y−y∧j2−lM‐lj,j=1,2,⋯,M‐1.The MS position can be obtained by minimizing the sum of objective functions for all errors, so the positioning objective function is constructed as(7)minψx,y=1M−1∑j=1M−1φj2x,y.


## 2.1. Step 1: Extraction of Pseudoscatterer Centres

In this paper, the BS is deployed at a known position, denoted as (xB, yB) in the Cartesian coordinate in Figure 2. Use the propagation distance Li and the AOA θi of the i-th path to determine the pseudoscatterers location xi′,yi′, which can be expressed in available information form as
(1)xi′=Li×cosθi+xByi′=Li×sinθi+yB.Letx^j,y^j,j=1,2,⋯,M represent the centres of the scattering area. Note that if in the azimuth AOA, the propagation distance parameters for all paths corresponding to the scattering centres have already been estimated in advanced, the positioning objective function can be constructed to estimate the target position.The clustering algorithm can be used to obtain the pseudoscatterer clustering centres ofS1′,S2′,⋯,SM′. After that, the multipath parameters of the scattering area centres can be obtained from the pseudoscatterer clustering centres by (1). The corresponding parameters Lj,θj are given as follows:
(2)Lj=x∧j′2+y∧j′2θj=arctany∧j′/x∧j′,where x^j′,y^j′ is the cluster centre of the pseudoscatterer.


## 2.2. Step 2: Construction of Positioning Objective Function

In this paper, it is assumed that the scattering area centres in the urban environment are known to bex^j,y^j,j=1,2,⋯,M. The centre of the scattering area can be obtained with the aid of satellite map or the distribution of surrounding buildings. The signal propagation distance is equal to the sum of the distance of the signal from BS to the scatterer and from the scatterer to MS, which can be calculated as
(3)x−x∧j2+y−y∧j2=Lj−x∧j−xB2+y∧j−yB2,j=1,2,⋯,M,where xB,yB and x,y are the locations of BS and MS, respectively. lj, i.e., the distance from MS to the centre of each scattering area, is shown as
(4)lj=Lj−xj−xB2+yj−yB2,j=1,2,⋯,M.Taking theM-th scattering centre as the reference, the distance difference between the other scattering centres and the M-th scattering centre to the MS can be expressed as
(5)x−xM2+y−yM2−x−x∧j2+y−y∧j2=lM−lj,j=1,2,⋯,M−1.In fact, due to the presence of parameter estimated errors, the target position in (5) does not have a closed-form solution. The solution process needs to be transformed into a nonlinear optimization problem. We can devise the objective equation as a set of errors, which can be defined as follows:
(6)φjx,y=x−xM2+y−yM2−x−x∧j2+y−y∧j2−lM‐lj,j=1,2,⋯,M‐1.The MS position can be obtained by minimizing the sum of objective functions for all errors, so the positioning objective function is constructed as(7)minψx,y=1M−1∑j=1M−1φj2x,y.


## 3. Parametric Clustering of Multipath Signals

In the actual scenario, scatterers are not only distributed in the specified scattering area but also exist far away from the scattering area. These scatterers are called interference scatterers in this paper. When clustering the pseudoscatterer, the pseudoscatterer corresponding to the interference scatterers will affect clustering and the final positioning accuracy. Therefore, it is necessary to identify and filter the interference scatterers. In this paper, the Gaussian kernel function is used to filter interference scatterers.The Gaussian kernel function describing the distance between two individuals is used to eliminate the effect of interference scatterers. Let the location of the two pseudoscatterers bexi′,yi′ and xj′,yj′, respectively. And then Gaussian kernel function dij with width parameter σ is defined as
(8)dij=exp−xi′−xj′2+yi′−yj′22σ2.The largerdij indicates that the two pseudoscatterers are closer. Since the interference scatterers are distributed outside the scattering area and the number of them is relatively small, the distribution of interference scatterers is sparse. By comparing the distribution density of scatterers, the interference scatterers can be identified and filtered. In this paper, a reference radius dave is set as the average Gaussian kernel of the pseudoscatterers, which is expressed as
(9)dave=1ANdnm,n∈X,m∈X,n≠m,where dnm is the Gaussian kernel between any two unequal pseudoscatterers Sn′ and Sm′, AN=CN2 is the number of times for the randomly selected two pseudoscatterers, N denotes the number of pseudoscatterers, and X is the set of all pseudoscatterers.The filtering process of interference scatterers is as follows. First a pseudoscattererSi′ is selected to calculate the Gaussian kernel dij of this scatterer with another pseudoscatterer Sj′. Second, we compare dij with dave. When dij>dave, Sj′ is an adjacent pseudoscatterer of Si′. Third, we calculate the number of all adjacent pseudoscatterers for all pseudoscatterers by the above method as S1,S2,⋯,SN. Finally, the N/5 scatterers are filtered out by comparing the distribution density. The pseudocode is shown in Algorithm 1.Algorithm 1: Interference scatterers filtering.
Inputxi′,yi′,i=1,2,⋯,N,σ,s1,s2,⋯,sN=01:fori=1,2,⋯,N do2:forj=1,2,⋯,N,j≠ido3:   Calculatedij by (8)4:end for5:end for6: Calculatedave by (7)7:fori=1,2,⋯,Ndo8:forj=1,2,⋯,N,j≠ido9:ifdij<davethen10:si=si+111:end if12:end for13:end for14: Select4/5N scatterers xi′,yi′ with large siOutputxi′,yi′,i=1,2,⋯,4/5N


## 4. Proposed Location Algorithm

In this section, the problem in (7) is solved using a simple yet computationally efficient iterative algorithm. The salp swarm algorithm (SSA) [17] is often used to solve nonlinear optimization problems; however, the SSA converges slowly and tends to fall into local optimum. In order to solve the above problems, this paper proposes SSA-GA. Firstly, the salp population is divided into two populations, i.e., the leaders xi=x1i,x2i,⋯,xdi,i=1,2,⋯,n/2 and the followers ẋi=ẋ1i,ẋ2i,⋯,ẋdi,i=1,2,⋯,n/2, respectively, and n is the number of individuals. The leader finds the food position based on the population information iteratively, which is the optimal solution for the objective function. The followers follow the leader to reach the optimal solution position. The quality of each position is evaluated by calculating fitness which is the value obtained by bringing the individual position into the objective function. In the l-th iteration, the j-th position of the i-th leader xji can be obtained as follows:
(10)xji=Fj+c1uj−djc2+djc3≥0Fj−c1uj−djc2+djc3≤0i=1,2,⋯,n/2,where Fj denotes the j-th position of the food, c1=2e−4l/L2 is the parameter that can be used to adjust the movement range of the leader, and L corresponds to the maximum iteration. c2 and c3 are random numbers uniformly generated in the interval of 0,1. Moreover, uj and dj indicate the upper bound and lower bound of j-th position. To effectively enhance the global search capability of the optimization algorithm, inspired by the genetic algorithm, crossover mutation is introduced to update the leader position, which can be expressed as follows:
(11)xji=xjiPm<rand0,1rand0,1×uj−djPm≥rand0,1,where pm is the variation probability of the leader. When pm is greater than the random value within 0,1, the xji is randomly assigned to a value in the range uj to dj. For crossover cases, the leader position can be updated as follows:
(12)x1n,x2n,⋯,xdnx1m,x2m,⋯,xdm=x1n,⋯,xd′n,xd′+1m,⋯,xdmx1m,⋯,xd′m,xd′+1n,⋯,xdnpc≥rand0,1,where pc represents crossover probability of the leader. The subscript d′ is the starting position of crossover. x1n,x2n,⋯,xdn and x1m,x2m,⋯,xdm are the position of two random leaders. When pc is greater than the random value within 0,1, two individuals start crossover at the d′-th position.The fitness of the crossed and mutated leaders is calculated to compare with the corresponding old leaders, and a new population of leaders is created using the better leaders (in the sense of fitness function). The optimum leader is first selected by calculating the fitness function, and then the position of the first follower can be calculated by(13)ẋj1l+1=12ẋj1l+xjbestl,where xjbest represents the j-th position of the best fitness leader. ẋj1 is the j-th position of the first follower. Finally, combined with the position of oneself and other individuals, the position of followers can be iterated by
(14)ẋjil+1=12ẋjil+ẋji−1li=2,3,⋯,n/2.The pseudocode of SSA-GA is shown in Algorithm2.Algorithm 2: Genetic algorithm-based improved salp swarm algorithm.
Inputn,L,pc,pm,u,d1: Initializing populationsSl2:while terminate condition has not been met do3:fori=1,2,⋯,ndo4:   Calculate fitness of salpxil5:end for6:F=the best search salp7:  Updatec18:  Divide the population into two parts: leadersxi and followers ẋi9:fori=1,2,⋯,n/2do10:   Update the position of the leaders by (10)11:end for12:fori=1,2,⋯,n/4do13:ifpc>rand0,114:    Update the position ofxi,xi+n/4 by (12)15:end if16:end for17:fori=1,2,⋯,n/2do18:ifpm>rand0,119:    Update the position of thexi by (11)20:end if21:end for22:  Set the population after crossover mutation asHl23:  Update populationsSl+1=combine (Hl,Sl)24:  Calculate the optimal position of leaderxbest25:  Update the position of the first follower by (13)26:fori=1,2,⋯,ndo27:   Update the position of followers by (14)28:end for29:end whileOutput The best global solution F


## 5. Algorithm Complexity Analysis

In this paper, SSA-GA is used to estimate the target location. We analyse and compare the average computing time complexity of SSA-GA and traditional SSA. This paper assumes that the population number of each iteration in SSA-GA and SSA isN1, the number of iterations is L¯, and the update time of position iteration for each leader and follower is T1 and T2, respectively. In the iteration process, T1≈T2. And the time for calculating individual fitness is T3. When SSA-GA runs for the maximum time, the leader population will cross-mutate each time. Because the time of individual cross-mutation is much less than that of calculating individual fitness, the time of cross-mutation can be ignored. After cross-mutation, the leader will recalculate the fitness. So, the total operation time of SSA-GA can be calculated as T′=L¯×N1×T1/2+N1×T1/4+N1×L1/2+N1×T2/2. The total operation time of SSA is T″=L¯×T1+N1−1×T2. The above two formulas are simplified to obtain that the average computational time complexity of SSA-GA and SSA is O7×L1×N1/4 and OL1×N1, respectively.


## 6. Results and Analysis

In this section, the performance of the proposed method is analyzed comprehensively through Monte Carlo simulations under various parameter settings. Consider a typical outdoor NLOS propagation environment, let the positioning range be500m×500m, and the position of the BS is 0,0. The measurement errors of AOA θ~i and TOA t~i are taken to be Gaussian distributed with a mean value of 5%. The scatterers obey the Gaussian distribution in the scattering region with known radius and centre, in which the mean value is the centre of the scattering region. Each positioning results are the average of 100 Monte Carlo simulations. The specific simulation setup parameters are shown in Table 1.Table 1
Parameter settings.
ParameterSymbolValueBase station coordinatesxB,yB0,0Maximum number of iterationsL100Number of scattering areasM3Number of scattering pointsN100Positioning range500m×500mAOA measurement errorθ~i5%TOA measurement errort~i5%Width parameterσ200First, we study the performance scatterer filtering. Figure3 depicts the clustering results with and without filtering out interference scatterers. It can be seen that the interference scatterers are thinly distributed and filtered out. Furthermore, the number of interference scatterers increases from 12 to 17. Figure 4(a) shows the cluster centre error with and without filtered interference scatterers. As shown in Figure 4(a), filtering scatterers can effectively decrease the clustering centre error for different numbers of interference scatterers. In order to comprehensively evaluate the effect of filtering interference scatterers on positioning accuracy, Figure 4(b) presents the positioning error with and without filtering out interference scatterers.Figure 3
Clustering results with and without filtering out interference scatterers. (a) Unfiltered. (b) Filtered.
(a)(b)Figure 4
Influence of filtering interference scatterers. (a) Clustering centre error. (b) Positioning error.
(a)(b)The cumulative distribution functions (CDF) of positioning errors for the SSA-GA, SSA, and LM algorithms [18] are represented in Figure 5. Here, the maximum number of iterations is set to 50. The results show that the localization results using the SSA-GA are better than those solved by the other two optimization algorithms; it is because the proposed SSA-GA has better global search ability and avoids the occurrence of local optimization, and the target position is more accurate.Figure 5
CDF of positioning error using different methods.In the actual positioning scenario, there are measurement errors in the multipath parameters. Figure6 illustrates the influence of the test errors of AOA and TOA on positioning accuracy. It is shown that with the increase of AOA and TOA errors, the positioning performance decreases. During localization, AOA is only used for scatterer filtering. TOA is used to construct the target equation, so the localization performance decreases more rapidly with the increase of TOA error.Figure 6
Influence of parameter error on the positioning result.For three scattering regions with a given radius and number of scatterers, Figure7 shows the positioning error using three optimization algorithms. We can derive that the proposed SSA-GA has higher localization accuracy compared to the SSA and LM algorithms in Figure 7, and the positioning error is less than 5%. The positioning error becomes larger as the radius of the scattering area increases. And when the number of scattering scatterers increases, the positioning error becomes lower.Figure 7
Effect of optimization algorithm on positioning performance. (a) SSA-GA. (b) SSA. (c) LM.
(a)(b)(c)In order to further study the factors affecting positioning accuracy, we simulate the proposed method in a different number of scattering regions. We obtained the positioning errors of the proposed method under the conditions of 3, 4, 5, and 6 scattering regions, respectively, as shown in Figure8. Figures 8(a) and 8(b) show the positioning error when the positioning range is 300m×300m and 400m×400m, respectively. It can be seen that when the number of scattering areas is less than 6, the positioning error fluctuates in a small range, and with the increase in the number of scattering regions, the aggregation of scatterers decreases, resulting in the obvious increase in positioning error.Figure 8
Influence of the number of scattering regions on positioning performance. (a) The range of positioning area is300m×300m. (b) The range of positioning area is 400m×400m.
(a)(b)


## 7. Conclusion

In this paper, the problem of target localization in outdoor NLOS propagation environment is addressed by fused AOA and TOA measurements. Firstly, the Gaussian kernel function is used to judge and filter the interference scatterers to improve the clustering accuracy of multipath parameters. Furthermore, a heuristic optimization algorithm SSA-GA is proposed to solve the target localization function. The algorithm expands the leader population in SSA and iterates the leader position through cross and mutation, which overcomes the local optimal problem of traditional algorithms and improves the positioning accuracy. Finally, the simulation results verify the effectiveness of the proposed localization method in a NLOS propagation environment and show that the positioning error is within 5% of the positioning range. The main direction of future work is to verify the applicability of the proposed positioning algorithm in a three-dimensional NLOS environment and carry out multipath measurements in the actual scenario to verify the positioning accuracy of the proposed positioning method.



---

*Source: 8585978-2022-07-27.xml*