The Hybrid Taguchi-Genetic Algorithm for Mobile Location

Abstract

To estimate the mobile location is an important topic in wireless communication. It is well known that non-line-of-sight (NLOS) problem is the most pivotal part that causes the estimated error. When we transmit the signal from mobile station (MS) to base stations (BSs), the direct path between MS and BS is sealed off by some obstacles, and the signal measurements will measure the error due to the signal reflection or diffraction. The hybrid Taguchi-genetic algorithm (HTGA) combines the Taguchi method with the genetic algorithm (GA). In this paper, we bring up a novel HTGA algorithm that utilizes time of arrival (TOA) measurements from three BSs to locate MS. The proposed algorithm utilizes the intersections of three TOA circles based on HTGA to estimate the MS location. Finally, we compare HTGA with GA and find that the Taguchi algorithm can enhance genetic algorithm. We also can find that the average convergence of generation number will not be affected no matter which propagation models we use. Obviously HTGA is more robust, statistically sound, and quickly convergent than the other algorithms. The simulation results show that the HTGA can converge more quickly than GA and furthermore the HTGA can enhance the accuracy of the mobile location.

1. Introduction

The mobile positioning is an important research topic in wireless communication. In recent years, it has gained considerable attention. Several researchers are concentrated on how to achieve higher accuracy in positioning. There are several wireless location schemes such as signal strength (SS), angle of arrival (AOA), time of arrival (TOA), and time difference of arrival (TDOA) techniques. The location of a mobile station (MS) is measured by the TOA between three or more base stations (BSs) with velocity of light [1, 2] in TOA method. The direction of the arrival signal [1] is detected by an antenna array and a directive antenna in AOA scheme where the MS is constrained along a line. The location of an MS is measured by the difference of arrival time between three or more BSs [3] in TDOA method. In particular, time-based and angle-based categories have their own advantages and disadvantages. The angle-based schemes have to know the minimum of two BSs to determine the MS location and the BSs do not require synchronization. On the contrary, the time-based schemes require at least three BSs and need synchronization. However, the time-based schemes usually provide much better positioning accuracy than angle-based schemes. Nowadays, There are a lot of applications of wireless location services, such as the intelligent transportation system (ITS) [4] and the emergency 911 (E-911). The public safety officer can see the caller's phone number and accurate location by E-911, and ITS combines a variety of positioning technologies to enhance the safety and efficiency of the transportation systems.

Non-line-of-sight (NLOS) is an important issue in MS location estimation problem. The line-of-sight (LOS) propagation is usually unavailable, especially in urban or suburban areas. NLOS error is always positive and large that arises when a distance is estimated from a calculation [5]. Some methods for mitigating NLOS error have been proposed in the literature [6–11]. In [2], the geometrical location algorithm was proposed to reduce the NLOS error. In [12, 13], range-scaling algorithm (RSA) was proposed. To adjust TOA by scaling NLOS-corrupted TOA measurements with the utilization of the factors that are estimated from a constrained nonlinear optimization process is the way to mitigate the NLOS. Reference [14] proposed hybrid TDOA and AOA techniques for MS location estimation in wideband code-division multiple access (CDMA) cellular systems.

One of the important issues that affects the implementation of location scheme in wireless communication systems is hearability. The definition of hearability is the ability to receive sufficient signals from the number of neighboring BSs simultaneously as soon as the signal power level is defined. In rural areas, only 35% of signal strength indication received by three BSs is stronger than −100 dB; in contrast, it is about 84% in urban areas [15]. Usually, larger geographic area is covered by a BS in rural areas; an MS receives signals from neighboring BSs more difficultly, because each BS usually covers a large area and the hearability of an MS is very low for neighboring BSs.

Genetic algorithm (GA) was proposed by Holland [16], and it has utilized optimum approaches in various fields recently. GA has become one of the most important evolutionary computation methods. GA is an optimum approach method inspired by the ability of organisms to evolve. The major sources of such variation are genetic recombination and mutation. GA has been utilized in many applications in a variety of fields such as control engineering, aeronautics, image processing, and structure analysis. The authors of this paper proposed a novel positioning algorithm based on GA to locate MS when three BSs are available for location purpose [17].

The hybrid Taguchi-genetic algorithm (HTGA) was proposed by Jyh-Horng Chou. It combines both the Taguchi method [18–20] and the GA [21]. The Taguchi method replaced the crossover operation in the HTGA. The Taguchi method combined the systematic reasoning ability with crossover operations to select better genes. It used the crossover operations to generate the representative chromosomes and it will be the new potential offspring. Hence, the Taguchi algorithm can enhance genetic algorithms. In this way, the HTGA can quickly converge and be more robust and statistically sound [22–24]. HTGA has smaller standard deviations of function values than the orthogonal genetic algorithm with quantization (OGA/Q) proposed by [25]. It particularly proposes the following four enhancements in the HTGA with continuous variables for global optimization. First, a real coding technique utilizes continuous variables to solve optimization problems. Second, the crossover operators utilize an arithmetical operator derived from convex set theory to integrate the one-cut-point crossover. Third, the two-level orthogonal array, two tools of the Taguchi method, and signal-to-noise ratio (SNR) are applied in this study. The value of the object function decreases gradually during the iterations. Generally speaking, the value will converge when the solution does not change after specific number of generation. Fourth, the mutation operator is also derived from convex set theory. The proposed algorithm utilizes the intersections of three TOA circles, based on HTGA, to estimate the MS location in NLOS environments. Simulation results will show that we proposed a better method of location estimation compared with the Taylor series algorithm (TSA), linear lines of position algorithm (LLOP), and RSA. Moreover, HTGA is more robust and can converge more quickly than GA.

The remainder of this paper is organized as follows. In Section 2, we describe some related localization methods. Section 3 briefly describes how HTGA works. In Section 4, we propose the algorithm based on HTGA to estimate MS location. Section 5 compares the performance of the proposed algorithm with the other methods through simulation results. Finally, Section 6 draws some conclusions.

2. Related Localization Methods

2.1. The Taylor Series Algorithm (TSA)

We take the constraint on hearability into account, so the number of BSs is limited to three in this paper for estimating the location. The coordinates for BS1, BS2, and BS3 are given by $(X_{\mathrm{1}},Y_{\mathrm{1}})=(\mathrm{0,0})$ , $(X_{\mathrm{2}},Y_{\mathrm{2}})=(X_{\mathrm{2}},\mathrm{0})$ , and $(X_{\mathrm{3}},Y_{\mathrm{3}})$ , respectively. The distances between BS and the MS can be expressed as

$$\begin{array}{cc}& r_i=\sqrt{{(x-X_i)}^{\mathrm{2}}+{(y-Y_i)}^{\mathrm{2}}},\end{array}$$

(1)

where $(x,y)$ and $(X_i,Y_i)$ are the location of the MS and ith BS, respectively. Assume $(x_v,y_v)$ is the initial estimated position; then $x=x_v+{\delta }_x$ , $y=y_v+{\delta }_y$ . Using the Taylor series expansion by linearizing the TOA equations and keeping up with the second-order terms, the equation can be expressed as

$$\begin{array}{cc}& A\delta \cong z,\end{array}$$

(2)

where

$$\begin{array}{cc}& A=\left[\begin{array}{cc}{a}_{\mathrm{11}}& a_{\mathrm{12}}\\ a_{\mathrm{21}}& a_{\mathrm{22}}\\ a_{\mathrm{31}}& a_{\mathrm{32}}\end{array}\right],\hspace{1em}\hspace{1em}\delta =\left[\begin{array}{c}{\delta }_x\\ {\delta }_y\end{array}\right],\hspace{1em}\hspace{1em}z=\left[\begin{array}{c}{r}_{\mathrm{1}}-r_{v\mathrm{1}}\\ r_{\mathrm{2}}-r_{v\mathrm{2}}\\ r_{\mathrm{3}}-r_{v\mathrm{3}}\end{array}\right],\\ a_{i\mathrm{1}}={\frac{\partial r_i}{\partial x}|}_{x_v,y_v},\hspace{1em}\hspace{1em}\mathrm{\hspace{0.17em}\hspace{0.17em}}{a}_{i\mathrm{2}}={\frac{\partial r_i}{\partial y}|}_{x_v,y_v},\\ r_{vi}=\sqrt{{(x_v-X_i)}^{\mathrm{2}}+{(y_v-Y_i)}^{\mathrm{2}}},\hspace{1em}i=\mathrm{1,2},\mathrm{3}.\end{array}$$

(3)

The least-squares (LS) solution to the estimation problem can be expressed as

$$\begin{array}{cc}& \delta ={\left(A^{T}A\right)}^{-\mathrm{1}}{A}^{T}z.\end{array}$$

(4)

An initial guess of the MS location starts the recursive process and then TSA repeats the iteration after computations. Because the initial guess of the MS location is not accurate enough, the iterative process is not always convergent [26, 27].

2.2. Linear Lines of Position Algorithm (LLOP)

The algorithm uses the linear equation derived from the original nonlinear range equations. The linear LOP equation passes through the intersections of the two circles for TOA measurements instead of circular LOP. The linear equations can be obtained by squaring and subtracting the distances between BS and the MS. The MS location can be expressed as [2]

$$\begin{array}{cc}& G\varphi =h,\end{array}$$

(5)

where $\varphi =\left[\begin{array}{c}x\\ y\end{array}\right]$ denotes the MS location, $G=\left[\begin{array}{cc}{X}_{\mathrm{2}}& \mathrm{0}\\ X_{\mathrm{3}}& Y_{\mathrm{3}}\end{array}\right]$ , and $h=(1/2)\left[\begin{array}{c}{r}_1^2-r_2^2+X_2^2\\ r_1^2-r_3^2+X_3^2+Y_3^2\end{array}\right]$ .

The LS solution to (5) is also given by

$$\begin{array}{cc}& \varphi ={\left(G^{T}G\right)}^{-\mathrm{1}}{G}^{T}h.\end{array}$$

(6)

2.3. Range-Scaling Algorithm (RSA)

Reference [12] utilizes TOA measurements from three BSs to estimate the MS location. The constrained optimization algorithm can find the normalized scale factors to adjust the measured distance error caused by NLOS. Some constraints on the normalized scale factors are based on the geometry of the cell layout of three BSs and the ranges of three BSs depicted in circles. The algorithm utilized the proposed object function written as the vector form to compute normalized scale factors and then mitigate the NLOS error with the utilization of the normalized scale factors.

3. The Hybrid Taguchi-Genetic Algorithm (HTGA)

HTGA combines the GA and the Taguchi method [22, 23]. In the HTGA, the Taguchi method replaces the step of crossover operation in GA. In GA, the crossover operation has two different ways, for example, single-point crossover and double-point crossover. Two ways can be chosen to find the crossover point randomly. In the Taguchi method, we can use the orthogonal array to calculate the SNR. And we can obtain the optimal chrome. The part of estimation method proposed by GA can be found in [17]. The following steps describe the HTGA approach, and Figure 1 shows the signal flow diagram.

Figure 1

The signal flow chart of the hybrid Taguchi-genetic method.

Step 1.

Input parameter setting includes population size = 50, crossover rate = 0.7, mutation rate = 0.02, reproduction rate = 0.28, and generation number = 30. Output parameter setting includes the optimal chromosome and fitness value.

Step 2 (initialization).

Execute the algorithm to generate an initial population. Calculate the fitness values of the population.

Step 3 (crossover operation).

We utilize the Taguchi method to do the crossover operation. The probability of crossover is determined by crossover rate.

Step 4.

Select a two-level orthogonal array. The orthogonal array L ₆₄ (2⁶³) is used in the proposed method.

Step 5.

Choose two chromosomes randomly at a time to execute matrix experiments.

Step 6.

Calculate the fitness value and SNRs in the experiment.

Step 7.

Calculate the effects of the different factors in the experiment.

Step 8.

Based on Step 7, generate an optimal chromosome.

Step 9.

Selection operation uses the roulette wheel approach.

Step 10 (mutation operation).

The probability of mutation is determined by mutation rate.

Step 11.

Generate offspring population.

Step 12.

If the condition is satisfied, then go to Step 13; if not, go back to Step 2.

Step 13.

Generate the population via HTGA.

4. Proposed Location Algorithm Based on HTGA

According to a point of view of geometric approach, each BS measured distance forms a circle, and the center of the circle is BS. Multiple TOA measurements can estimate the MS position by the intersection of the circles. As shown in Figure 2, each of the following three equations indicates a circle for TOA:

$$\begin{array}{l}\text{Circle}\mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{1}\text{:\hspace{1em}}{x}^{\mathrm{2}}+y^{\mathrm{2}}=r_{\mathrm{1}}^{\mathrm{2}}\\ {\text{Circle}\mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{2}\text{:\hspace{1em}}\left(x-X_{\mathrm{2}}\right)}^{\mathrm{2}}+y^{\mathrm{2}}=r_{\mathrm{2}}^{\mathrm{2}}\\ {\text{Circle 3:\hspace{1em}}\left(x-X_{\mathrm{3}}\right)}^{\mathrm{2}}+{(y-Y_{\mathrm{3}})}^{\mathrm{2}}=r_{\mathrm{3}}^{\mathrm{2}}.\end{array}$$

(7)

The three circles intersect at a point if there is no measured error or NLOS, and the point is the MS location. However, the location accuracy will degrade seriously because the NLOS error is very common in our life. Furthermore, the NLOS error appears as a positive bias at all times and is therefore greater than the true values, and consequently the circles will overlap with each other finally forming a region. The true MS location should be inside the overlap region of the three circles as shown in Figure 2, that is, the area surrounded by U, V, and W. The intersections that are within this are defined as the feasible intersection. The feasible intersections have to satisfy the following three equations simultaneously:

$$\begin{array}{cc}& x^2+y^2\le r_1^2,\\ {\left(x-X_2\right)}^2+y^2\le r_2^2,\\ {\left(x-X_3\right)}^2+{(y-Y_3)}^2\le r_3^2.\end{array}$$

(8)

Figure 2

Geometric layout of the three circles of TOA method.

The possible MS location has to satisfy the above three equations, so we can estimate the location using the feasible intersections of the three circles, U, V, and W. By solving the circle equations (7), we can obtain the feasible intersections of three circles. The coordinates of U, V, and W are represented as $(Ux,Uy)$ , $(Vx,Vy)$ , and $(Wx,Wy)$ . Reference [12] proposed a nonlinear object function which can be seen as a cost function. It is the sum of the square of the distance from MS location to the intersection of the three circles. The object function of HTGA is

$$\begin{array}{l}f\left(x,y\right)={(x-U_x)}^2+{(y-U_y)}^2+{(x-V_x)}^2\\ \hspace{1em}+{\left(y-V_y\right)}^2+{\left(x-W_x\right)}^2+{\left(y-W_y\right)}^2.\end{array}$$

(9)

Another problem is to avoid the condition of the NLOS error being too large; that is, one circle is fully covered by another circle. If $r_i>L_{ij}+r_j$ , we adjust the measured TOA to $r_i=L_{ij}+r_j$ ( $i,j=\mathrm{1,2},\mathrm{3}$ ; $i\ne j$ ). There is at least one intersection for any two circles to ensure the algorithm is applied. We apply HTGA to obtain the approximation of the MS location. We should calculate the ranges of variables first in order to do the encoding. The ranges of variables x and y are the maximum and minimum among the three points U, V, and W:

$$\begin{array}{cc}& x_{\min }=\min \{Ux,Vx,Wx\};\hspace{1em}\hspace{1em}{x}_{\max }=\max \{Ux,Vx,Wx\}\\ y_{\min }=\min \left\{Uy,Vy,Wy\right\};\hspace{1em}\hspace{1em}{y}_{\max }=\max \left\{Uy,Vy,Wy\right\}.\end{array}$$

(10)

We restrict chromosome in the overlap region of the three circles except for the upper bound and lower bound of the variables; that is to say, we only compute chromosomes which satisfy the three inequalities (8). This method can reduce the probability of bad convergence and computation complexity. The value of the object function decreases gradually during the iterations. Generally speaking, the value will converse when the solution does not change after specific number of generation.

5. Simulation Results

Computer simulations are conducted to illustrate the performance of the proposed positioning schemes. In the simulations, the coordinates of BSs are as BS₁: (0, 0), BS₂: (1732 m, 0), and BS₃: (866 m, 1500 m). Five thousand independent trials are performed for each simulation (and the region is formed by the points BS₁, BS₂, and BS₃ with sides I, J, and K being of uniform distribution). And the MS location is chosen randomly within the region as shown in Figure 3. Adjusting the parameter of GA affects just a little the result because of the good convergence. We set the parameter as the following analysis: number of generation = 30, crossover rate = 0.7, and mutate rate = 0.002. We take the NLOS effects into account in the simulation. Two propagation models are adopted, namely, circular disk of scatterers model (CDSM) [25] and uniformly distributed noise model [12], respectively.

Figure 3

Cell layout showing the relationship between the true ranges and inter-BS distances.

CDSM is the first NLOS propagation model which assumes that there are scatterers spreading around the MS when the signal travels between MS and BSs [25]. The signal goes through a single reflection at the scatterers. The sum of the distances between the BS and the scatterer and between the MS and the scatterer is the measured ranges. Figure 4 shows the geometry of CDSM, where p is the scatterer point. The measured ranges are the sum of the distances between the BS and the scatterer $(r_b)$ and between the MS and the scatterer $(r_s)$ . The measured AOA at the BSs is the angle between the BSs and the scatterer where the signal is reflected. If the scatterer point is on the circle, the AOA measurement will be the maximum. Thus, if the scatterer radius is larger, the estimation error will be larger. The probability of lower range error is larger than the higher one.

Figure 4

Geometry of circular disk of scatterers model (CDSM).

Figure 5 shows the cumulative distribution functions (CDFs) of the location error for different algorithms using the CDSM. The radius of the scatterers is considered to be 200 m. Note that the proposed method is always better than TSA and LLOP for the error model considered. The positioning precision of the proposed HTGA is slightly better than that of RSA and GA.

Figure 5

The CDF of the location error for various methods.

MS location accuracy is measured in terms of root-mean-square (RMS) error between the actual MS location and the desired MS location. The radius effect of the CDSM on the average location error compared with other existing methods is as shown in Figure 6. It can also be observed that the sensitivity of the proposed methods with respect to the NLOS effect is much less than that for TSA and LLOP. Obviously the average location error of the proposed HTGA is slightly less than RSA and GA. The simulations result shows that the proposed HTGA can yield the MS location more accurately than the other algorithms.

Figure 6

Average location error versus the radius of scatters.

The uniformly distributed noise model [12] is applied for the second NLOS propagation model. The TOA measurement error is assumed to be uniformly distributed over ( $0,U_i$ ). $U_i$ is the upper bound of the measurement error for i = 1, 2, 3. For example, if we set the upper bound of error as 200 m, the TOA measurement error will be uniformly distributed over (0, 200 m). The effect of various methods used with upper bound of NLOS error on the average location error is shown in Figure 7, in which we estimate the average location error of the mobile station in terms of RMS error. When the upper bound of NLOS error increases, the RMS error increases. Simulation results show that the proposed HTGA has better location estimation than TSA, LLOP, RSA, and GA.

Figure 7

Average location error versus the upper bound of NLOS errors.

The relationships between the fitness value and the number of generation for HTGA and GA are, respectively, shown in Figures 8 and 9. HTGA outperforms traditional GA in obtaining the optimal solutions because of its fast convergence ability. When we take the location estimation of MS at each generation, the generation is considered to be convergent if the difference of the estimated MS and best performance is less than 0.01.

Figure 8

The convergence speed of GA and HTGA in each generation by using CDSM.

Figure 9

Some of the convergence results of GA and HTGA in each generation for uniformly distributed noise model.

Figures 10 and 11, respectively, show the performance of the average generation numbers for convergence between HTGA and GA, in which the CDSM model and uniformly distributed noise model are applied. We can obtain the average generation number after running five thousand times. Note that the average generation number of HTGA and GA is, respectively, 14 and 26 when we choose the maximal generation number as 30. We also can find that the average generation number is independent of the propagation models.

Figure 10

Convergence generation number versus the radius of scatters.

Figure 11

Convergence generation number versus the upper bound of NLOS errors.

Simulation results show that, no matter which NLOS propagation model is considered, the proposed HTGA can always give better location estimation. Note that both HTGA and GA approach can provide more accurate MS location estimations. Although the performances of HTGA and GA are very close, HTGA still converges faster than GA. Therefore, there are many discussions about this phenomenon [22, 23]. The simulation results show that the proposed HTGA can reduce the number of iterations and decrease the calculation complexity. In mobile communication device, the computational complexity is an important topic. The proposed HTGA method can solve this problem. Thus the mobile device can decrease the computational complexity and power resources.

6. Conclusion

In this paper, we propose the schemes based on HTGA to estimate MS location from three BSs. In order to eliminate NLOS errors and without any a priori information about the NLOS error, the proposed methods utilize all the feasible intersections which are generated by three TOA circles to estimate the MS location. Obviously HTGA is not only robust but also quicker than GA. We also can found that the average generation number for convergence is not dependent on the propagation models. Simulation results show that the location accuracy of the proposed methods is much better comparing with the standard TSA, LLOP, RSA, and GA. On the other hand, reducing the signal-processing time of the mobile device can increase not only the processing capabilities available for other purposes but also the saving of the power of battery.