1 Introduction

Finding the coordinates of a mobile source is an interesting research topics in many areas, such as wireless sensor networks [1, 2], telecommunications [3], and mobile communications [4, 5]. For example, after the Federal Communications Commission (FCC) of the United States proposed to improve the emergency service [6], a lot of attention has been paid to mobile handheld device localization.

The coordinates of a mobile source can be estimated by utilizing its emitted signal measured from a number of separated sensors with known coordinates. Time-of-arrival (TOA) is a commonly used approach [7] to estimate the position of a mobile device. When there are no noise in the TOA measurements, the exact coordinates of the mobile source can be obtained. In the real situation, those TOA measurements are contaminated by noise. When the noise is Gaussian, we can use the maximum likelihood (ML) approach to estimate the coordinates of the mobile source. However, the ML function for finding the position of using the TOA measurements is highly nonlinear. Hence, finding out the global solution is not guaranteed. On the other hand, the TOA-based source localization can be formulated as least squares (LS) [8, 9] problems via linearization. Several numerical methods [8, 9] run at digital computers have been proposed for TOA-based mobile localization.

Since the pioneering results from Hopfield [10] and Chua [11] in the 1980s, analog neural circuits for solving optimization problems have attracted much attention. Hopfield [10] investigated an analog neural circuit for solving quadratic optimization problems. In [11], a canonical nonlinear programming circuit was proposed to solve nonlinear programming problems with inequality constraints. In [12, 13], a number of projection neural models have been proposed to solve constrained optimization problems. Apart from optimization, neural circuits can also be used for searching the maximum of a set of numbers [14–16]. In [17], the Lagrange programming neural network (LPNN) model is proposed to solve general nonlinear constrained optimization problems. A LPNN consists of two types of neurons: variable and Lagrangian neurons. The variable neurons seek for a state with the minimum objective value in a system, while the Lagrangian neurons are trying to constrain the system state into the feasible region. Compared with traditional numerical methods run at digital computers, solving optimization problem by neural circuit has several advantages. For instance, neural circuits can be realized by the VLSI or optical technologies that are able to achieve real-time computation. For many years, although many neural network models for engineering problems have been addressed, little attention has been paid to analog neural circuits for source localization.

This paper proposes an analog neural network technique based on LPNNs for TOA-based source localization. We first formulate the source localization problem as a constrained optimization problem. However, in this initial formulation, the stability at equilibrium points is not guaranteed. Hence, we introduce an augmented term in the objective function. Simulations demonstrate that the mean-square error (MSE) performance of our analog approach is close to the Cramér–Rao lower bound (CRLB).

This paper is organized as follows. Section 2 presents the backgrounds of LPNNs and source localization. In Sect. 3, we formulate the source localization problem as a constrained optimization problem. Then, we discuss the way to solve this problem based on LPNNs. Theoretical analysis on the stability of the neural model is also discussed. Section 4 presents our simulation results. As a comparison, MSEs of linear least squares (LLS) [8], two-step weighted least squares (TSWLS) [9], as well as CRLB are also included. We then conclude the paper in Sect. 5.

2 Background

2.1 Lagrange programming neural networks

In LPNNs, we consider a nonlinear optimization problem with equality constraints, given by

$$ \hbox{EP:}\,\hbox{min}\,f(\user2{x}), {\hbox{subject to}}\,\user2{h}(\user2{x})= {\bf 0}, $$
(1)

where \({\user2{x} \in \mathbb{R}^n}\) is the variable vector being optimized, and \({f:\mathbb{R}^n \rightarrow \mathbb{R}}\) (called objective function) is a scalar function. The vector valued function \({\user2{h}: \mathbb{R}^n \rightarrow \mathbb{R}^m (m<n)}\) describes the m equality constraints. In the LPNN approach, we assume that f and \(\user2{h}\) are twice differentiable.

The LPNN approach considers the Lagrangian function, given by

$$ {{\mathcal{L}}} (\user2{x},\boldsymbol{\lambda}) = f(\user2{x}) + \boldsymbol{\lambda}^T \user2{h}(\user2{x}), $$
(2)

where \({\varvec{\lambda}} = [\lambda_1, \ldots, \lambda_m]^T\) is the Lagrangian multiplier vector.

A LPNN consists of two types of neurons, namely variable and Lagrangian neurons. The variable neurons hold the state variables \(\user2{x}.\) The Lagrangian neurons holds the Lagrange multipliers \({\varvec{\lambda}}.\) A LPNN searches an equilibrium point of (1) based on the dynamics, given by

$$ \frac{\hbox{d} \user2{x}}{\hbox{d}t} = -\nabla_x {{\mathcal{L}}}(\user2{x},{\boldsymbol{\lambda}}), {\hbox{and}} \frac{\hbox{d} \boldsymbol{\lambda}}{\hbox{d}t} = \nabla_\lambda {\mathcal L}(\user2{x},\boldsymbol{\lambda}). $$
(3)

In (3), the dynamics of state variables is used for minimizing the Lagrangian function, while the dynamics of Lagrangian multipliers is employed for constraining \(\user2{x}\) in the feasible region.

2.2 TOA-based source localization

In the TOA-based source localization problem shown in Fig. 1, there is a mobile source with unknown coordinates. The unknown source coordinates are denoted as \(\user2{c}=[c_1,c_2]^T.\) We use m (≥3) sensors for locating the mobile source. Let \(\user2{u}_i=[u_{i,1}u_{i,2}]^T\) be the coordinate vector of the ith sensor. The distance between the source and the ith receiver is denoted as

$$ d_i = \| \user2{c} - \user2{u}_i \|_2 $$
(4)

where \(\|\cdot\|_2\) stands for the 2-norm. Assume that there are only line-of-sight propagations from the mobile source to the sensors. The distances d i ’s can be determined from the one-way signal propagation times. Let \({\user2{d}}= [ d_1,\ldots,d_m ]^T\) be the true distances between the mobile source and sensors. Assuming that there are additive noise in the observed process, the measurement distances \(\hat{\user2{d}},\) can be modeled as

$$ \hat{\user2{d}} = \user2{d}+ \boldsymbol{\epsilon} $$
(5)

where \({\varvec{\epsilon}}\) is the noise vector.

Fig. 1
figure 1

The source localization problem. There are four sensors. If there are line-of-sight propagations from the mobile source to the sensors, the distances d i ’s can be determined from the one-way signal propagation times between the mobile source and sensors

Full size image

2.3 ML estimation

In general, it is difficult to determine the probability model of \({\varvec{\epsilon}}\) because the probability model depends on several complicated factors such as the nonlinear structure of the TOA estimator [18]. Hence, it is common to assume [19] that \({\varvec{\epsilon}}\) follows a Gaussian distribution with zero mean. Also, each component of \({\varvec{\epsilon}}_i\) is independent of one other. Then, the covariance matrix is given by \({\varvec{\varPhi}} = \hbox{diag}(\sigma_1^2,\ldots,\sigma_m^2).\)

In the ML estimator [20], we would like to find out an estimate of the mobile source position such that the objective function

$$ \frac{1}{2} (\hat{\user2{d}} - {\user2{g}})^T {\varvec{\varPhi}}^{-1} (\hat{\user2{d}} - {\user2{g}}) $$
(6)

is minimized, where \({{\user2{g}}: \mathbb{R}^2 \rightarrow \mathbb{R}^m}\) has its ith element, given by

$$ g_i = \| {\user2{c}} - {\user2{u}}_i \|_2. $$
(7)

It should be noticed that the objective function in (6) is a nonlinear function of the mobile source’s coordinates \(\user2{c}.\) Hence, finding the optimal solution may not be easy. A number of numerical methods have been proposed in [21, 22].

3 LPNN for ML estimation

The ML location estimation problem in (6) can be rewritten as a constrained optimization problem, given by

$$ \min_{{\user2{c, g}}} \frac{1}{2} (\hat{\user2{d}} - {\user2{g}})^T {\varvec{\varPhi}}^{-1} (\hat{\user2{d}} - {\user2{g}}) $$
(8a)
$$\hbox{s.t.}\,g_i^2 = \| {\user2{c}} - {\user2{u}}_i \|^2, \quad i=1,\ldots,m $$
(8b)
$$ g_i \geq 0, \quad i=1,\ldots,m $$
(8c)

Since there are m equality constraints and m inequality constraints in (8c), the problem may not be solved by the LPNN approach directly. As the distance vector \(\hat{\user2{d}}\) contains only nonnegative elements, we can remove the m inequality constraints in (8c). Therefore, we have the following theorem.

Theorem 1

The optimization problem in (8) is equivalent to

$$ \min_{ {\user2{c, g}} } \frac{1}{2} (\hat{\user2{d}} - {\user2{g}})^T {\varvec{\varPhi}}^{-1} (\hat{\user2{d}} - {\user2{g}}) $$
(9a)
$$ \hbox{s.t.}\,g_i^2 = \| {\user2{c}} - {\user2{u}}_i \|_2^2, \quad i=1,\ldots,m, $$
(9b)

where the m inequality constraint in (8c) is removed.

Proof

We will show that if \(({\user2{c}^*, \user2{g}^*})\) is an optimal solution of (9), then \(g_i^\star \geq 0\) for all i. Note that if the above statement is true, then the m inequality constraints in (8c) can be removed. Let \(({\user2{c}^*, \user2{g}^*})\) be the optimal solution of (9). From the definition, the minimal objective function value in (9) is given by

$$ (\hat{\user2{d}} - {\user2{g}}^* )^T {\varvec{\varPhi}}^{-1} (\hat{\user2{d}} - {\user2{g}}^* ) = \sum_{i=1}^m \frac{1}{\sigma_i^2} ( \hat{d}_i - g^*_i )^2. $$
(10)

From basic algebra, we have

$$ \sum_{i=1}^m \frac{1}{\sigma_i^2} ( \hat{d}_i - g^*_i )^2 \geq \sum_{i=1}^m \frac{1}{\sigma_i^2} ( |\hat{d}_i| - |g^*_i| )^2.$$
(11)

Since the measurement distances \(\hat{d}_i\)’s are greater than or equal to zero, we have

$$ \sum_{i=1}^m \frac{1}{\sigma_i^2} ( |\hat{d}_i| - |g^*_i| )^2 = \sum_{i=1}^m \frac{1}{\sigma_i^2} ( \hat{d}_i - |g^*_i| )^2. $$
(12)

From (11) and (12), we have

$$ \sum_{i=1}^m \frac{1}{\sigma_i^2} ( \hat{d}_i - g^*_i )^2 \geq \sum_{i=1}^m \frac{1}{\sigma_i^2} ( \hat{d}_i - |g^*_i| )^2. $$
(13)

Inequality (13) implies that the minimal objective function value \(\sum\nolimits_{i=1}^m \frac{1}{\sigma_i^2} ( \hat{d}_i - g^*_i )^2\) is greater than or equal to the function value achieved by the feasible point \(({\user2{c}}^*, \hbox{abs}({\user2{g}}^*)).\) Since \(({\user2{c}}^*,{\user2{g}}^*)\) is the optimal solution, the equality in (13) must hold. Furthermore, the equality in (13) holds if and only if \({\user2{g}}^* = \hbox{abs}({\user2{g}}^*).\) Hence, the global optimal solution must satisfy g * i  ≥ 0 for all i. Hence, the m inequality constraint in (8c) can be removed and the proof is complete. □

With Theorem 1, the constrained optimization problem for TOA-based source localization can be rewritten as

$$ \min_{{\user2{c, g}}} \frac{1}{2} (\hat{\user2{d}} - {\user2{g}})^T {\varvec{\varPhi}}^{-1} (\hat{\user2{d}} - {\user2{g}}) $$
(14a)
$$ \hbox{s.t.}\,g_i^2 = \| {\user2{c}} - {\user2{u}}_i \|_2^2, \quad i=1,\ldots,m. $$
(14b)

From (14), one may suggest that we can construct the following Lagrangian function:

$$ \begin{aligned} {{\mathcal{L}}} (\user2{c, g}, \boldsymbol{\lambda}) = & \frac{1}{2} (\hat{\user2{d}} - {\user2{g}})^T {\varvec{\varPhi}}^{-1} (\hat{\user2{d}} - {\user2{g}})\\ & + \sum_{i=1}^m \lambda_i (g^2_i - \| {\user2{c}} - {\user2{u}}_i \|_2^2), \end{aligned} $$
(15)

where \({\varvec{\lambda}} = [ \lambda_1, \ldots, \lambda_m ]^T\) is the Lagrangian multiplier vector. Afterward, we can use (15) to drive the neural dynamics for solving the ML location estimation problem defined by (14). However, our preliminary experiment finds that the second-order gradient of the Lagrangian function at an equilibrium point may not be positive. Hence, the neural dynamics may not be stable. As a result, an equilibrium point \((\user2{x}^*,{\varvec{\lambda}}^*)\) may not be stable.

To improve the convexity and the stability [17], we introduce an augmented term \({C_o}/{2} \sum\nolimits_{i=1}^m (g_i^2 = \| {\user2{c}} - {\user2{u}}_i \|_2^2)^2\) into the objective function, where C o is a large positive constant. With the augmented term, the optimization problem (14) can be modified as

$$ \min_{{\user2{c, g}} } \frac{1}{2} (\hat{\user2{d}} - {\user2{g}})^T {\varvec{\varPhi}}^{-1} (\hat{\user2{d}} - {\user2{g}}) +\frac{C_o}{2} \sum_{i=1}^m (g_i^2 - \| {\user2{c}} - {\user2{u}}_i \|_2^2)^2 $$
(16a)
$$ \hbox{s.t.}\,g_i^2 = \| {\user2{c}} - {\user2{u}}_i \|_2^2, \quad i=1,\ldots,m $$
(16b)

In (16), we have an additional term in the objective function. However, at an equilibrium point \((\user2{g}^{*}, {\user2{c}}^{*}),\) the constraints are satisfied, i.e., \({g_i^*}^2 = \| {\user2{c}^*} - {\user2{u}}_i \|_2^2, \quad i=1,\ldots,m.\) That means, at an equilibrium point, the additional term \({C_o}/{2} \sum_{i=1}^m (g_i^{* 2} = \| {\user2{c}}^{*} - {\user2{u}}_i \|_2^2)^2\) is equal to zero. So, adding this augmented term does not change the objective function value at the equilibrium point.

Let \(\user2{x}=[\user2{c}^T \user2{g}^T]^T.\) From (16) and the concept of LPNNs, we can set up the Lagrangian function for source localization, given by

$$ \begin{aligned} {\mathcal L}_{ml} (\user2{c, g}, \boldsymbol{\lambda}) = & \frac{1}{2} (\hat{\user2{d}} -{\user2{g}})^T {\varvec{\varPhi}}^{-1} (\hat{\user2{d}} - {\user2{g}})\\ & + \frac{C_o}{2} \sum_{i=1}^m (g_i^2 - \| {\user2{c}} - {\user2{u}}_i \|_2^2)^2\\ &+ \sum_{i=1}^m \lambda_i (g^2_i - \| {\user2{c}} - {\user2{u}}_i \|_2^2). \end{aligned} $$
(17)

In (17), \(\user2{c}\) and \(\user2{g}\) are state variables, while \(\lambda_i\)’s are Lagrangian variables. That means, there are m + 2 state variable neurons to hold state variables \(\user2{c}\) and \(\user2{g}\), and m + 2 state Lagrangian neurons to hold the Lagrangian variables λ i ’s.

With (17), from (3), the dynamics of the network is given by

$$ \begin{aligned} \frac{\hbox{d} \user2{c}}{\hbox{d}t} = & -\frac{\partial {\mathcal L}_{ml}(\user2{c, g}, \boldsymbol{\lambda})}{\partial \user2{c}}\\ = & 2\sum_{i=1}^m (\lambda_i- C_o (g_i^2- \| {\user2{c}} - {\user2{u}}_i \|_2^2))(\user2{c}-\user2{u}_i), \end{aligned} $$
(18)
$$ \begin{aligned} \frac{\hbox{d} g_i}{\hbox{d}t} = & -\frac{\partial {\mathcal L}_{ml}(\user2{c, g}, \boldsymbol{\lambda})}{\partial g_i}\\ =& \frac{1}{\sigma_i^2} ( \hat{d}_i \!-\!g_i) - 2C_o g_i (g_i^2 - \| {\user2{c}} - {\user2{u}}_i \|_2^2) - 2 \lambda_i g_i, \end{aligned} $$
(19)
$$ \begin{aligned} \frac{\hbox{d} \lambda_i}{\hbox{d}t} = & \frac{\partial {\mathcal L}_{ml}(\user2{c, g}, \boldsymbol{\lambda})}{\partial \lambda_i }\\ = & g_i^2 -\| {\user2{c}} - {\user2{u}}_i \|_2^2. \end{aligned} $$
(20)

A realization of this LPNN is shown Fig. 2. There are 2m + 2 function blocks to calculate the inputs of the neurons. Also, there are 2m + 2 integrators to update the states of the neurons.

Fig. 2
figure 2

Realization of a LPNN for TOA-based source localization

Full size image

In LPNNs [17], apart from the convexity, another requirement for the local stability is that the gradient vectors \(\{\nabla_{\user2{x}} h_1(\user2{x}^*),\ldots, \nabla_{\user2{x}} h_m (\user2{x}^*)\}\) of the constraints at an equilibrium point \(\user2{x}^*, \{\nabla_{\user2{x}} h_1(\user2{x}^*),\ldots, \nabla_{\user2{x}} h_m (\user2{x}^*)\},\) should be linearly independent.

In our case, we let

$$ \user2{x} = \left[ \begin{array}{c} \user2{c}\\ \user2{g} \end{array}\right], $$
(21a)
$$ \user2{x}^* = \left[ \begin{array}{c} \user2{c}^* \\ \user2{g}^* \end{array} \right], $$
(21b)
$$ h_i(\user2{x}) = h_i(\user2{c, g}) = g^2_i - \| {\user2{c}} - {\user2{u}}_i \|_2^2, $$
(21c)

for \(i=1,\ldots,m.\) In our approach, the gradient vectors at the equilibrium point \(\user2{x}^*\) are given by

$$ \left\{ \left[ \begin{array}{c} -2(\user2{c}^* - \user2{u}_1)\\ 2 g_1^* \\ 0 \\ \vdots \\ 0 \end{array} \right],\cdots \cdots, \left[ \begin{array}{c} -2(\user2{c}^* - \user2{u}_m) \\ 0 \\ \vdots \\ 0\\ 2 g_m^* \end{array} \right]\right\}. $$
(22)

That means, if g * i  ≠ 0 for all i, the equilibrium point is a stable point. At the equilibrium point \({g^*_i}^2 = \| {\user2{c}}^* - {\user2{u}}_i \|_2^2.\) Hence, if the estimated coordinates are not equal to one of sensor’ coordinates, the dynamics around the equilibrium point is stable.

4 Simulation results

We conduct several computer simulations to evaluate the accuracy of the proposed analog neural model.

4.1 Neural dynamics

In this example, there are six sensors, i.e., m = 6, shown in Fig. 3. Their coordinates are \((10, 0), (5, 5\sqrt{3}), (-5,5\sqrt{3}), (-10,0), (-5,-5\sqrt{3})\) and \((5,-5\sqrt{3}).\) The coordinates of the mobile source are (−4,4). The TOA measurement errors are uncorrelated zero-mean Gaussian random variables with identical variances, i.e., \(\sigma^2 = \sigma_1^2 = \sigma_2^2 = \cdots = \sigma_m^2.\) Figure 4 shows the dynamics of the estimated source coordinates under three noise levels for a single trial. For small noise levels, say, σ 2 = 0.1, the network settles down in less than one characteristic time. When we increase the noise level to σ 2 = 1, the network is still able to settle down within 10 characteristic times.

Fig. 3
figure 3

Coordinates of six sensors and mobile device in Sect. 4.1

Full size image
Fig. 4
figure 4

Dynamics of estimated source coordinates

Full size image

4.2 Fixed source location

In this section, we study the effectiveness of our analog network model. Three sets of sensor positions with m = 4, 6 and 8, shown in Fig. 5, are considered. The mobile source is at (−4,4). The TOA measurement errors are uncorrelated zero-mean Gaussian random variables with identical variances, i.e., \(\sigma^2 = \sigma_1^2 = \sigma_2^2 = \cdots = \sigma_m^2.\) As a comparison, we also consider two benchmark location estimators: the LLS [8] and TSWLS [9]. They are conventional numerical methods for TOA-based source localization. In the simulation, we include the CRLB. It is well known [9] that the performance of the TSWLS is close to the CRLB for sufficiently small noise conditions.

Fig. 5
figure 5

Three sets of sensors used in Sects. 4.2 and 4.3

Full size image

For each set of sensor positions and each noise level, the experiment is repeated 1,000 times. Figure 6 plots MSEs of estimated mobile source coordinates under various settings. From the figure, we observe that as we increase the number of sensors, the performance of various algorithms becomes better. The performance of the proposed analog neural model is better than of the LLS algorithm over a wide range of measurement noise levels. Also, the performance of the proposed analog neural model is comparable with that of the TSWLS and is close to the CRLB. For instance, for the case of four sensors, when the noise level is equal to −5 dB, the MSE of using the LLS algorithm is equal to −3.91 dB. Using the TSWLS or our analog neural approach, we can reduce the MSE value to −4.87 dB. Note that the CRLB value is equal to −5.78 dB when the noise level is equal to −5 dB.

Fig. 6
figure 6

The performance of various algorithms under different settings. The mobile source is fixed at (−4,4). The coordinates of the sensors are shown in Fig. 3

Full size image

4.3 Random source location

In this section, the sensor positions are identical to those of Sect. 4.2. However, the source position is randomly chosen at each of the 1,000 independent runs. The location is uniformly distributed on a circle centered at the origin with radius 15. Figure 7 shows the corresponding MSE performance.

Fig. 7
figure 7

The performance of various algorithms under different settings. The source location is uniformly distributed on a circle centered at the origin with radius 15. The sensors are shown in Fig. 3

Full size image

From the figure, we also observe that as we increase the number of sensors, the performance of various algorithms becomes better. The performance of the proposed analog neural model is better than of the LLS algorithm. Also, the performance of the proposed analog neural model is comparable with that of the TSWLS. For instance, for the case of six sensors, when the noise level is equal to −5 dB, the MSE of using the LLS algorithm is equal to −4.21 dB. Using the TSWLS approach, the MSE is reduced to −6.44 dB. Using our analog neural approach, we can also get a similar MSE value. Note that the CRLB value is equal to −7.10 dB when the noise level is equal to −5 dB.

5 Conclusion

In this paper, we have showed that the TOA-based localization can be formulated as a constrained optimization problem. We then propose an analog neural network model, based on LPNNs, to solve this problem. To improve the stability at equilibrium points, we add an augmented term in the objective function. Simulations demonstrate that in terms of MSE, there is no significant difference between our analog approach and the traditional TSWLS numerical method. Also, the MSE performance of our analog approach is close to CRLB. This paper assumes that line-of-sight propagation holds. One of the future directions is to extend our approach to handle nonline-of-sight cases. Note that the conventional LS methods or TSWLS are not effective for such scenarios.