Circular Uncertainty method for range-only localization with imprecise sensor positions

Abstract

This study provides an effective new method to solve the range-only localization in the presence of sensor position errors. In practice, the sensors can stay only within a limited region whereas the target can be far from there. To increase the estimation capability, some peripheral measurements with moving sensors can be obtained, which results in the issue of imprecise sensor positions. In these situations, sensor positions also become unknown parameters which need to be jointly estimated together with the target location. Because of the large number of unknown parameters, reaching the global minimum becomes a significant challenge. Our study is dedicated to build a robust localization scheme for these scenarios. We propose a new search strategy, namely Circular Uncertainty which allows the localization system to safely find the global minimum of maximum likelihood cost function in case of imprecise sensor positions. Circular Uncertainty not only makes it possible to reach maximum likelihood estimation, but also significantly simplifies this task. Our solution is based on the observation that when the initial estimation is disturbed with new measurements, the disturbed estimation moves along the Circular Uncertainty which can be viewed as a circular valley along the cost surface. The new method is compared to nonlinear least squares as well as the squared range weighted least-squares algorithm which was previously designed in the literature specifically for localization with imprecise sensor positions. Since the proposed solution obtains maximum likelihood estimation, it attains Cramer Rao lower bound, where other competing methods partly fail.

1 Introduction

Sensor array processing is the field to deal with the data coming from multiple channels to achieve various tasks. Source localization, as a sub-area of sensor array processing, attempts to find the location of different of type of sources through the information from various sensors especially in noisy environments (Nehorai and Paldi 1994). There can be several types of error within the information utilized in source localization such as the error at measurements or the error at measurement positions etc. This study provides an effective new method to solve the localization problem by means of distance-to-target measurements in the presence of sensor position errors.

Source localization with imprecise sensor positions is an old research area which has been subject of many different applications since the late 1970s. The uncertainty in sensor positions first discussed for the large towed array of hydrophones in the field of underwater acoustic research. The distortion in the shape of the array of hydrophones due to the movement of the tow ship was mentioned as a reason of positional uncertainty in the receiving hydrophones (Hinich and Rule 1975; Bucker 1978; Carter 1979). This type of arrays is then regarded as randomly perturbed arrays and the initial Cramer Rao lower bound (CLRB) derivations are obtained for range and bearing estimation (Schultheiss and Ianniello 1980). In Rockah and Schultheiss (1987), it is mentioned that overall localization accuracy can be dominated by the uncertainty in the sensor positions. Therefore, they mentioned about calibrations of sensor array geometries for better localization of a single far-field source. In Krim and Viberg (1996), the uncertainty in the sensor positions is listed under additional topics of the sensor array processing.

In Chen et al. (2002), it is mentioned that error in sensor locations can emerge when the sensors are randomly deployed in an ad hoc network or when sensors move to different positions in time. In Ho et al. (2007), it has been discussed that in modern localization applications, the receivers can be airplanes or unmanned aerial vehicles (UAVs) therefore their positions as well as velocities can not be precisely known. Therefore, they explicitly mentioned that deployment of UAVs as moving receivers brings the issue of uncertainty in receiver positions. As a result, the new trend of using UAVs as moving sensors has increased the importance of localization with imprecise sensor positions. Therefore, localization with imprecise sensor positions via time difference of arrival (TDOA) or frequency difference of arrival (FDOA) have remained as an interesting research area until today. In Ho and Yang (2008), for TDOA based localization, a calibration emitter is proposed to calibrate the location of the sensors to compensate sensor position errors. In Qu and Xie (2012a, b), they give a significant emphasis to TDOA based source localization with random sensor position errors by dividing their study into two parts for specifically static sensors and then mobile sensors with imprecise positions. Li et al. (2015) deal with TDOA and FDOA based localization and Li and Ho (2016) discuss a TDOA based localization with inaccurate sensor positions. Array shape calibration is also discussed for direction of arrival (DOA) estimation (Zhang et al. 2017) and so on.

Imprecise sensor positions are also specifically discussed for source localization with distance-to-target measurements. In Srirangarajan et al. (2007) and Lui et al. (2009), they introduced distance based localization schemes in wireless sensor networks when both the locations of the nodes and the anchors are unknown or imprecise. They built semi-definite and second order cone programming to address this issue. In Ma and Ho (2011), the focus is directly on source localization by means of time of arrival (TOA) in the presence of sensor position errors. They build CRLB for range based localization of a source with imprecise sensor positions. They emphasized that the source localization is highly sensitive to the inaccuracy in sensor positions. Finally, they built a Weighted Least Square (WLS) solution for sensor position errors which are quite small. In Chen and Ho (2014), TOA and TDOA based localization with sensor position errors were discussed in terms of again WLS solutions but this time for larger sensor position error levels compared to Ma and Ho (2011). They also mentioned that maximum likelihood estimation (MLE) attains CRLB without explicitly presenting MLE solution in their paper. In Li et al. (2014), TOA based localization with sensor position errors is solved by a two-stage algorithm where an initial estimate for the location of source at the first stage is further improved at the second stage.

Distance-to-target measurements are nonlinear observations with respect to the unknown parameters namely the coordinates of the target location (Chen and Ho 2014). This situation makes target localization which is based on distance-to-target measurements a challenging task. Therefore, the estimators seeking the best possible estimation such as maximum likelihood estimation (MLE) require iterative searches along nonlinear cost surfaces. Iterative solutions are computationally expensive and their accuracy significantly depends on the initial points of the iterations. In various localization scenarios, MLE cost surface can be complicated with a couple of local minima and saddles points. Therefore, depending on the initial point, the minimization process can end up with a local minimum, so this can lead the performance of estimator to diverge from the ideal case. However, this study proposes a completely safe localization scheme without any convergence issue.

When the sensor positions have uncertainties in addition to the uncertainties in distance measurements, this situation brings an additional difficulty for localization system. In these cases, the positions of sensors also become unknown parameters which need to be jointly estimated together with the target location. The number of parameters to be estimated becomes very large, so reaching the global minimum becomes a significant challenge for iterative solutions (Chen and Ho 2014). Taking this fact into account, this study removes this issue by conveniently reducing the multi-dimensional search space to a single dimensional space by means of our proposed method called Circular Uncertainty. The method of Circular Uncertainty allows the localization system to safely find the global minimum even for complicated cost functions in the presence of imprecise sensor locations.

Distance based localization can be solved by nonlinear least squares (NLS) of errors of distance-to-target measurements. However, NLS solutions are not suitable to deal with the uncertainties in sensor positions. Weighted least squares (WLS) can be regarded as a special case of NLS where each term is skillfully weighted by taking the uncertainties in sensor positions into account. Weighting the squared distance errors can be quite useful to manage the uncertainties in sensor positions. However, to obtain a better scheme of localization, the cost of estimation must be a complete equation which includes two different parts for both distance-to-target measurement errors and sensor position errors. Therefore, in this study, the complete maximum likelihood cost function is established and solved in a smart and convenient way which guarantees to obtain the Cramer Rao Lower Bound (CLRB) in any condition.

In practical situations, the sensors can only be allowed to be located within a limited region whereas it is very likely that the target can be located far from this region. Our important observation is that while it is very common to encounter this type of localization scenario, it provides a very limited capability for estimating the angular position of the target via distance-to-target observations. Therefore, in addition to the central measurements taken within a limited region, a few number of peripheral measurements can be deployed to dramatically increase the estimation capability of localization system. However, to scan a broad peripheral area, the peripheral measurements can be designed as moving sensors, which, as a result, brings the issue of uncertainties in the positions of sensors. Moreover, both the error in the sensor positions and the error of distance measurements can be significantly high in practical situations. Therefore, the localization systems must be so robust that they keep functioning even under high level of noise and they must try to localize the target as accurate as possible in every case. Our study is dedicated to build this type of robust localization system.

In the rest of the paper, firstly CRLB for localization error is explicitly obtained for the case of imprecise sensor positions. Next, the basis of the new proposed method namely Circular Uncertainty is presented by visually displaying the cost surfaces of localization of targets. Then, a formal proof for Circular Uncertainty is provided. Circular Uncertainty significantly reduces the size of the search spaces of the minimization processes. It conveniently finds the global minimum of the MLE surface which gets quite complicated because of the uncertainties in the sensor positions. The performance of the new proposed method is tested by simulations for different scenarios, and also compared with the WLS solution of Chen and Ho (2014) which is specifically designed to attain CRLB in the presence of sensor position uncertainties. Our solution, which takes the advantage of obtaining MLE in a robust way, attains CRLB regardless of the noise level whereas other solutions partly fail to achieve this performance.

2 The basis for the research

2.1 Cramer Rao lower bound for localization with imprecise sensor locations

In this part, we formulate CRLB for localization with imprecise sensor positions. When there are N independent distance observations from N different sensor locations, the Fisher information matrix is as the following (Bishop et al. 2010),

$$\begin{aligned} I\left( {x,y} \right) = \frac{1}{\sigma _D^2 } \left[ {{\begin{array}{l@{\quad }l} \mathop \sum \limits _{i=1}^N \frac{\left( {x-x_i } \right) ^{2}}{\left( {x-x_i } \right) ^{2}+\left( {y-y_i } \right) ^{2}}&{} \mathop \sum \limits _{i=1}^N \frac{\left( {x-x_i } \right) .\left( {y-y_i } \right) }{\left( {x-x_i } \right) ^{2}+\left( {y-y_i } \right) ^{2}} \\ \mathop \sum \limits _{i=1}^N \frac{\left( {x-x_i } \right) .\left( {y-y_i } \right) }{\left( {x-x_i } \right) ^{2}+\left( {y-y_i } \right) ^{2}}&{} \mathop \sum \limits _{i=1}^N \frac{\left( {y-y_i } \right) ^{2}}{\left( {x-x_i } \right) ^{2}+\left( {y-y_i } \right) ^{2}} \\ \end{array} } } \right] \end{aligned}$$

(1)

where $(x,\, y)$ is the target location and $(x_i ,\, y_i )$’s are the sensor positions where distance-to-target measurements are taken for $i=1,..,N$. Distance measurements are obtained with the standard deviation $\sigma _D$. This Fisher Information Matrix is only for localization with precise information for sensor positions. Therefore, we need to obtain Fisher information for the case of imprecise sensor positions. Now, let us define the whole measurement model when sensor positions are imprecise,

$$\begin{aligned} D_i= & {} \sqrt{\left( {x-x_i } \right) ^{2}+\left( {y-y_i } \right) ^{2}}+ W_i \sim N\left( {0,\sigma _D } \right) \end{aligned}$$

(2)

$$\begin{aligned} X_i= & {} x_i +Z_i \sim N\left( {0,\sigma _X } \right) \end{aligned}$$

(3)

$$\begin{aligned} Y_i= & {} y_i +T_i \sim N\left( {0,\sigma _Y } \right) \end{aligned}$$

(4)

where $D_i$ is distance measurement at the sensor position ($x_i$, $y_i )$. The sensors are physically in their exact positions ($x_i$,$y_i )$. But, we do not have the precise information for the sensor positions. However, this does not affect $D_i$ measurements. Therefore, we need also to model the position of sensors as imprecise information. Consequently, in addition to $D_i$ namely distance to target measurement, ($X_i$, $Y_i )$ is also included within model as the observation of ith sensor position i.e. ($x_i$, $y_i )$. In this model, $W_i$, $Z_i$ and $T_i$ represent the zero-mean normal distributed error terms within $D_i$, $X_i$ and $Y_i$ respectively. The standard deviations of $D_i$, $X_i$ and $Y_i$ are $\sigma _D$, $\sigma _X$ and $\sigma _Y$ respectively.

Now, based on the addition rule of Fisher Matrix, we can write the Fisher information for the measurement model that we have just defined above as the following,

$$\begin{aligned} I( {\vec {q}} ) = \sum _{{i = 1}}^{N} I_{{D_{i} }} ( {\vec {q}} ) + ~\sum _{{i = 1}}^{N} I_{{X_{i} }} ( {\vec {q}} ) + ~\sum _{{i = 1}}^{N} I_{{Y_{i} }} ( {\vec {q}} ) = I_{D} ( {\vec {q}} ) + ~I_{X} ( {\vec {q}} ) + ~I_{Y} ( {\vec {q}} ) \end{aligned}$$

(5)

where ${\vec {q}}$ is parameter set, which defines the location of the target and all sensors,

$$\begin{aligned} \vec {q} = \left[ {x~,~y,~x_{1} ~,~y_{1} ,~ \ldots ,~x_{N} ~,~y_{N} } \right] \end{aligned}$$

(6)

If we define a $2\times 2$ matrix such that,

$$\begin{aligned} A_i = \left[ {{\begin{array}{l@{\quad }l} {\frac{\left( {x-x_i } \right) ^{2}}{\left( {x-x_i } \right) ^{2}+\left( {y-y_i } \right) ^{2}}}&{} {\frac{\left( {x-x_i } \right) .\left( {y-y_i } \right) }{\left( {x-x_i } \right) ^{2}+\left( {y-y_i } \right) ^{2}}} \\ &{} \\ {\frac{\left( {x-x_i } \right) .\left( {y-y_i } \right) }{\left( {x-x_i } \right) ^{2}+\left( {y-y_i } \right) ^{2}}}&{} {\frac{\left( {y-y_i } \right) ^{2}}{\left( {x-x_i } \right) ^{2}+\left( {y-y_i } \right) ^{2}}} \\ \end{array} }} \right] \end{aligned}$$

(7)

The information matrix for a single distance-to-target measurement $D_i$ becomes,

$$\begin{aligned} I_{{D_{i} }} \left( {\vec {q}} \right) = \frac{1}{{\sigma _{D} ^{2}}} \left[ {\begin{array}{l@{\quad }l@{\quad }l@{\quad }l@{\quad }l@{\quad }l} {A_{i}} &{}\underline{0}&{}\ldots &{}{A_{i}}&{}&{}\\ \underline{0}&{}\underline{0}&{}&{}&{}&{}\\ \vdots &{}&{}\ddots &{}&{}&{}\\ {A_{i}}&{}&{}&{}{A_{i}}&{}&{}\\ &{}&{}&{}&{}\underline{0}&{}\\ &{}&{}&{}&{}&{}\underline{0}\\ \end{array} }\right] \end{aligned}$$

(8)

where 0 is the $2\times 2$ zero matrix. Therefore, FIM for all distance measurements are,

$$\begin{aligned} \begin{aligned} I_{{D}} \left( {\vec {q}} \right) = \frac{1}{{\sigma _{D} ^{2}}} \left[ {\begin{array}{cccccc} \sum \limits _{{i = 1}}^{N}{A_{i}} &{}{}{A_{1}}&{}{}\ldots &{}{}{A_{i}}&{}{}\ldots &{}{}{A_{N}}\\ {A_{1}}&{}{}{A_{1}}&{}{}&{}{}&{}{}&{}{}\\ \vdots &{}{}&{}{}\ddots &{}{}&{}{}&{}{}\\ {A_{i}}&{}{}\underline{0}&{}{}&{}{}{A_{i}}&{}{}&{}{}\\ \vdots &{}{}&{}{}&{}{}&{}{}\ddots &{}{}\underline{0}\\ {A_{N}}&{}{}&{}{}&{}{}&{}{}\underline{0}&{}{}{A_{N}}\\ \end{array} }\right] \end{aligned} \end{aligned}$$

(9)

FIM for measurements of x positions of all sensor is,

$$\begin{aligned} I_X \left( Q \right) =\frac{1}{\sigma _X ^{2}}\left[ {{\begin{array}{l@{\quad }l@{\quad }l@{\quad }l@{\quad }l@{\quad }l@{\quad }l@{\quad }l} 0&{}&{}&{}&{}&{}&{}&{}\\ &{}0&{}&{}&{}&{}&{}&{}\\ &{}&{}1&{}&{}&{}&{}&{}\\ &{}&{}&{}0&{}&{}&{}&{}\\ &{}&{}&{}&{}1&{}&{}&{}\\ &{}&{}&{}&{}&{}0&{}&{}\\ &{}&{}&{}&{}&{}&{}\ddots &{}\\ &{}&{}&{}&{}&{}&{}&{}\ddots \\ \end{array}}}\right] \end{aligned}$$

(10)

and FIM for measurements of y positions of all sensors is,

$$\begin{aligned} I_Y \left( Q \right) =\frac{1}{\sigma _Y ^{2}}\left[ {{\begin{array}{l@{\quad }l@{\quad }l@{\quad }l@{\quad }l@{\quad }l@{\quad }l@{\quad }l} 0&{}&{}&{}&{}&{}&{}&{}\\ &{}0&{}&{}&{}&{}&{}&{}\\ &{}&{}0&{}&{}&{}&{}&{}\\ &{}&{}&{}1&{}&{}&{}&{}\\ &{}&{}&{}&{}0&{}&{}&{}\\ &{}&{}&{}&{}&{}1&{}&{}\\ &{}&{}&{}&{}&{}&{}\ddots &{}\\ &{}&{}&{}&{}&{}&{}&{}\ddots \\ \end{array}}}\right] \end{aligned}$$

(11)

If the standard deviations of sensor position errors are equal in x and y-axis namely,

$$\begin{aligned} \sigma _S =\sigma _X = \sigma _Y \end{aligned}$$

(12)

then, FIM of measurements of positions of all sensors can be written as,

$$\begin{aligned} I_S \left( {\vec {q}} \right) =\frac{1}{\sigma _S ^{2}}\left[ {{\begin{array}{l@{\quad }l@{\quad }l@{\quad }l@{\quad }l@{\quad }l@{\quad }l@{\quad }l} 0&{}&{}&{}&{}&{}&{}&{}\\ &{}0&{}&{}&{}&{}&{}&{}\\ &{}&{}1&{}&{}&{}&{}&{}\\ &{}&{}&{}1&{}&{}&{}&{}\\ &{}&{}&{}&{}1&{}&{}&{}\\ &{}&{}&{}&{}&{}1&{}&{}\\ &{}&{}&{}&{}&{}&{}\ddots &{}\\ &{}&{}&{}&{}&{}&{}&{}\ddots \\ \end{array}}}\right] \end{aligned}$$

(13)

Finally, the total FIM is as the following:

$$\begin{aligned} I\left( {\vec {q}} \right) = ~I_{D} \left( {\vec {q}} \right) + ~I_{S} \left( {\vec {q}} \right) \end{aligned}$$

(14)

The lower bound for the mean squared distance error of any localization scheme can be calculated by summing the first two diagonal elements of the inverse of the total FIM, i.e. $I^{{ - 1}} ( {\vec {q}}$) . The overall effect of having some level of uncertainty in the sensor positions is to levitate the CRLB for all levels of distance error.

2.2 Maximum likelihood solution for target localization with imprecise sensor positions

The ordinary NLS solution for range-only target localization can be written as the following (Buehrer and Venkatesh 2012):

$$\begin{aligned} \left( \hat{x}, \hat{y}\right) = ~\mathop {{\text {argmin}}}\limits _{{\left( {x,y} \right) }} \mathop \sum \limits _{{i = 1}}^{N} \left( {\sqrt{\left( {x - X_{i} } \right) ^{2} + ~\left( {y - Y_{i} } \right) ^{2} } - ~D_{i} } \right) ^{2} \end{aligned}$$

(15)

where ($X_i$, $Y_i )$ is the observed position of ith sensor and $D_i$ is the distance measurement at this sensor. Dedicated to minimize only the overall error in distance measurements, this solution neglects if the sensor positions are imprecise, however still it can be a convenient way to solve the localization problem with imprecise sensor positions. Therefore, ordinary distance NLS will be always included during our simulations as a baseline solution. The ordinary distance NLS can be MLE solution when sensor positions are precise. However, for imprecise sensor positions, the cost of estimation must be a complete equation which includes two different parts for both distance-to-target measurement errors and sensor position errors. Therefore, to obtain MLE cost function, let us write the log likelihood of all parameters in ${\vec {q}}$ as the following (see “Appendix”):

$$\begin{aligned} \ln p\left( {\vec {D},\vec {X},~\vec {Y};\vec {q}} \right)= & {} - ~\frac{1}{{\left( {\sigma _{D} } \right) ^{2} }}\mathop \sum \limits _{{i = 1}}^{N} \left( {\sqrt{\left( {x - x_{i} } \right) ^{2} + ~\left( {y - y_{i} } \right) ^{2} } - ~D_{i} } \right) ^{2}\nonumber \\&- ~\frac{1}{{\left( {\sigma _{S} } \right) ^{2} }}~\mathop \sum \limits _{{i = 1}}^{N} \left[ {\left( {X_{i} - x_{i} } \right) ^{2} + ~\left( {Y_{i} - y_{i} } \right) ^{2} } \right] + K \end{aligned}$$

(16)

where is K is a constant such that,

$$\begin{aligned} K=- N \ln \left( {\sqrt{2 \pi \left( {\sigma _D } \right) ^{2}}} \right) -2 N \ln \left( {\sqrt{2 \pi \left( {\sigma _S } \right) ^{2}}} \right) \end{aligned}$$

(17)

From this point of view, we can propose a maximum likelihood estimation (MLE) for all parameters of the parameter set ${\vec {q}}$ as the following:

$$\begin{aligned}&\left( {{\hat{x}} ,{\hat{y}} ,{\hat{x}} _1 ,{\hat{y}} _1 \ldots {\hat{x}} _N , {\hat{y}} _N } \right) \nonumber \\&\quad =\mathop {\hbox {argmin}}\limits _{\left( {x,y,x_1 ,y_1 \ldots x_N , y_N } \right) } \left( {{\begin{array}{l} { \frac{1}{\left( {\sigma _D } \right) ^{2}}\mathop \sum \limits _{i=1}^N \left( {\sqrt{\left( {x-x_i } \right) ^{2}+ \left( {y-y_i } \right) ^{2}}- D_i } \right) ^{2}} \\ {+ \frac{1}{\left( {\sigma _S } \right) ^{2}} \mathop \sum \limits _{i=1}^N \left( {X_i -x_i } \right) ^{2}+ \left( {Y_i -y_i } \right) ^{2}} \\ \end{array} }} \right) \end{aligned}$$

(18)

This MLE function allows us to take into account the errors in sensor positions to better estimate the target positions. To obtain the MLE solution, we need to find the global minimum of the MLE cost in a $\left( {2N+2} \right)$ dimensional space of the parameters included within ${\vec {q}}$. Estimating jointly all these parameters, i.e. the location of target and all of the sensor positions at the same time, is a quite difficult joint estimation problem. Therefore, we have built a new concept, namely Circular Uncertainty, in order to conveniently search for the global minimum of the MLE function.

3 Methodology

3.1 A new concept in range-only localization: circular uncertainty

With the motivation to solve maximum likelihood localization problem when sensor positions are imprecise, we propose a new search strategy, which we called Circular Uncertainty. Circular Uncertainty roughly means that once “ a base cost surface” is established by means of a couple of central measurements which are confined to a limited area, in case some new measurements are received which disturb the initial estimation, the disturbed new estimation has a tendency to move along a particular circle or arc. We name this special circle as Circular Uncertainty of the base central measurements. Let us start to introduce this concept by demonstrating examples of NLS cost surfaces obtained via some central measurements with precise positions.

Fig. 1

Circular Uncertainty demonstration by means of examples of NLS cost surfaces

In Fig. 1a, the sensors are circularly located around the origin, then noisy distance measurements are obtained in accordance with the distance measurement model in (2). Based on these distance measurements, the value of distance NLS cost function shown in (15) is obtained for all the (x, y) points, so the distance NLS cost surface is obtained. In Fig. 1a, this NLS cost surface is depicted as a contour plot. As seen, the global minimum of NLS cost surface naturally occurs around the target. However, the interesting point is that this NLS cost function have a tendency to stretch along a special circle, so it has a croissant-like shape surrounding the origin.

The croissant-like shape of contour of NLS surface is due to the fact that there exist a few central distance-to-target measurements and the target is located far from the measurement points. As a result, the angular position error of the target dominates the overall error of the NLS solution. In other words, NLS solution for this scenario has a limited capability for estimating the angular position of the target compared to its radial position. When we plot the NLS surface with respect to polar coordinates as shown in Fig. 1b, it can be seen that NLS surface has a neat appearance which resembles a bivariate normal distribution with a diagonal covariance matrix. Of course, while the distribution can be an ordinary normal distribution along radial coordinate, it must be a circular normal distribution (i.e. von Mises distribution) along angular coordinate because of the periodicity of the angular coordinate. It can be observed that the variance along the angular coordinate is quite larger than the variance along the radial coordinate. In this sense, because this distribution is a bivariate normal distribution in polar coordinates as seen Fig. 1b, then its Cartesian counterpart shown in Fig. 1a can be viewed as a circularly wrapped bivariate normal distribution around the origin of Cartesian plane. Consequently, this explains the croissant-like shape of NLS surface in Fig. 1a.

The sensor geometry in Fig. 1a is a special one, so it may be wondered if this type of behavior exists for random sensor geometries. In Fig. 1c for a random measurement geometry located roughly around the origin, it can be again observed that NLS surface stretches along a special circle i.e. not along some other type of closed curve. For this case, the croissant shape is not symmetric around the global minimum, but it still perfectly stretches along a circle. Consequently, we will name this circle as “the Circular Uncertainty” of the particular cost surface. Intuitively, we will the define the parameters of the circular uncertainty as:

$$\begin{aligned} \left( {x_{CU} , y_{CU} } \right) =\left( {\frac{1}{N}\mathop \sum \limits _{i=1}^N x_i , \frac{1}{N}\mathop \sum \limits _{i=1}^N y_i } \right) \end{aligned}$$

(19)

$$\begin{aligned} r_{CU} =\frac{1}{N}\mathop \sum \limits _{i=1}^N D_i \end{aligned}$$

(20)

where $\left( {x_{CU} , y_{CU} } \right)$ is the center and $r_{CU}$ is the radius of the Circular Uncertainty. The center of Circular Uncertainty is defined as the centroid of measurement points, and the radius of the Circular Uncertainty is defined as the average distance measurements. The important property of Circular Uncertainty is that global minimum of cost surface occurs along the Circular Uncertainty. In Fig. 1a, c, it can be observed that the global minimum is located along the Circular Uncertainty. In Fig. 1d, another interesting point can be observed that when NLS cost surface has a local minimum, this local minimum also occurs along the Circular Uncertainty.

Next, it may be wondered if Circular Uncertainty starts to occur only after some specific number of measurements. In Fig. 1e, the NLS cost surface of only two measurements are shown where there must be two global minima. Surprisingly, in spite of the existence of only two measurements (and consequently two global minima), NLS surface still tends to stretch along the Circular Uncertainty. The Circular Uncertainty of this surface is quite visible in 3D plot of the NLS surface shown in Fig. 1f. If we consider that a single distance measurement is also basically a circular uncertainty, then it can be argued that the defined Circular Uncertainty always occurs regardless of the number of measurements.

At the beginning of this section, we mentioned that once “a base cost surface” is established by means of a couple of central measurements, in case of receiving some new measurements which disturb the initial estimation, the disturbed new estimation has a tendency to move along the Circular Uncertainty trajectory. This situation occurs because of the croissant shape of the NLS surface along the Circular Uncertainty. Circular Uncertainty is basically “a circular valley” within the surface of NLS cost function as demonstrated in Fig. 1f. When new measurements are received which disturbs the initial estimation, the new disturbed estimation will move along this “circular valley” instead of climbing the hillsides.

This phenomenon is depicted in Fig. 2 where there are two base measurements creating a Circular Uncertainty. In addition to these base measurements, a third measurement with a sensor position error is obtained. Finally, based on these three measurements, the location of the target is estimated and then plotted as a small circular point in Fig. 2. When we repeatedly add a random error to the position of third measurement, and then force NLS localization to locate the target as a Monte Carlo simulation, we can obtain a set of disturbed NLS solutions. Due to the above explanations, the disturbed solutions are accumulated along the Circular Uncertainty. A similar picture can be observed in literature (see Fig. 9 in Olson et al. 2006), yet the authors did not pay attention to the above defined Circular Uncertainty phenomenon.

Fig. 2

The distribution of disturbed NLS solutions along the Circular Uncertainty

Eventually, we can list “the properties of Circular Uncertainty” which helps to create a new understanding in range-only localization of targets:

• 1. Global minimum occurs along the Circular Uncertainty trajectory (possibly with a small deviation).

• 2. Local minima (if any) have a tendency to occur along the Circular Uncertainty.

• 3. When the initial estimation is disturbed with new measurements, the disturbed estimation moves along the Circular Uncertainty trajectory, which is the circular valley of the cost surface.

Property 1 will allow us to conveniently find the global minimum of the cost surface of localization when sensor positions are precise. Property 3 will further allow us to handle the issue of imprecise sensor positions via Circular Uncertainty. The overall idea of Circular Uncertainty is visually demonstrated by means of a movie to give more tangible understanding of this concept (https://youtu.be/sj5CUsZs8W8).

3.2 Proof of Circular Uncertainty

In this section, our new concept i.e., Circular Uncertainty which has just introduced in the previous section will be proved by formulating the polar equation of the NLS solution. The r value which minimizes the NLS cost for a specific the direction $\theta$ can be expressed as the following:

$$\begin{aligned} {\hat{r}} \left( \theta \right) = \mathop {\hbox {argmin}}\limits _r \mathop \sum \limits _{i=1}^N \left( {\sqrt{\left( {r \hbox {cos}\left( \theta \right) -X_i } \right) ^{2}+ \left( {r \hbox {sin}\left( \theta \right) -Y_i } \right) ^{2}}- D_i } \right) ^{2} \end{aligned}$$

(21)

Therefore, the r value minimizing the NLS cost shown in (21) must satisfy the following condition:

$$\begin{aligned} \frac{\partial }{\partial r}\mathop \sum \limits _{i=1}^N \left( {\sqrt{\left( {r \hbox {cos}\left( \theta \right) -X_i } \right) ^{2}+ \left( {r \hbox {sin}\left( \theta \right) -Y_i } \right) ^{2}}- D_i } \right) ^{2}= 0 \end{aligned}$$

(22)

When the derivate in (22) is accomplished, the following equation is obtained:

$$\begin{aligned} \mathop \sum \limits _{i=1}^N \left[ {2 \left( {D_i - {\tilde{D}} _i \left( r \right) } \right) \frac{\cos \left( \theta \right) \left( {r \hbox {cos}\left( \theta \right) -X_i } \right) +\sin \left( \theta \right) \left( {r \hbox {sin}\left( \theta \right) -Y_i } \right) }{{\tilde{D}} _i \left( r \right) }} \right] =0 \end{aligned}$$

(23)

where ${\tilde{D}} _i \left( r \right)$ represents the distance between the point ($r\cos \left( \theta \right) ,r\sin \left( \theta \right) )$ and the position of ith sensor $\left( {x_i ,y_i } \right)$ as shown in Fig. 3. $D_i$ is the distance-to-target measurement obtained by the ith sensor. As seen in Fig. 3, the line which passes through the origin with the angle $\theta$ with respect to x-axis is labeled as $L_\theta$. It can be observed that the nominator of the division at right in (23) is the projection of the line segment with the length ${\tilde{D}} _i$ on the line $L_\theta$. Therefore, (23) can be rewritten as:

$$\begin{aligned} \mathop \sum \limits _{i=1}^N \left[ {\left( {D_i - {\tilde{D}} _i } \right) \frac{{\tilde{D}} _i \cos \left( {\alpha _i } \right) }{{\tilde{D}} _i }} \right] =0 \end{aligned}$$

(24)

where $\alpha _i$ is the angle between $L_\theta$ and the line segment connecting the points ($r\cos \left( \theta \right) ,r\sin \left( \theta \right) )$ and $\left( {x_i ,y_i } \right)$. After canceling the common terms, the following expression is obtained:

$$\begin{aligned} \mathop \sum \limits _{i=1}^N \left[ {D_i \cos \left( {\alpha _i } \right) - {\tilde{D}} _i \cos \left( {\alpha _i } \right) } \right] =0 \end{aligned}$$

(25)

Fig. 3

The proof for Circular Uncertainty and its parameters

Then, we can replace ${\tilde{D}} _i \cos \left( {\alpha _i } \right)$ by $\left( {r-S_i^p } \right)$, so the following expression appears:

$$\begin{aligned} \mathop \sum \limits _{i=1}^N \left[ {D_i \cos \left( {\alpha _i } \right) - \left( {r- S_i^p } \right) } \right] =0 \end{aligned}$$

(26)

where $S_i^p$ is the projection of the line segment connecting the origin to the position of ith sensor $\left( {x_i ,y_i } \right)$ onto the line $L_\theta$ as shown in Fig. 3. Obviously, $S_i^p$ is a function of $\theta$, while $\alpha _i$ is a function of both $\theta$ and r, consequently (26) can be rewritten as the following:

$$\begin{aligned} \mathop \sum \limits _{i=1}^N \left( {S_i^p \left( \theta \right) + D_i \cos \left[ { \alpha _i \left( {\theta ,r} \right) } \right] - r} \right) = 0 \end{aligned}$$

(27)

The difficult point is that $\alpha _i$ is a function of r, so finding the root of (27) becomes a complex task. To simplify this task, for sufficiently large r values, $\cos \left[ {\alpha _i \left( {\theta , r} \right) } \right]$ can be roughly approximated as 1. This approximation is consistent with the case of Circular Uncertainty where the central measurements are scattered just around the origin, and the target is assumed to be located in a point far from the measurements. Finally by means of this approximation, the following equation appears:

$$\begin{aligned} \mathop \sum \limits _{i=1}^N \left( {S_i^p \left( \theta \right) + D_i - r} \right) \approx 0 \end{aligned}$$

(28)

Therefore, the r value which minimizes the NLS cost for a specific the direction $\theta$ can be formulated as the following:

$$\begin{aligned} {\hat{r}} \left( \theta \right) \approx \frac{1}{N}\mathop \sum \limits _{i=1}^N S_i^p \left( \theta \right) + \frac{1}{N}\mathop \sum \limits _{i=1}^N D_i \end{aligned}$$

(29)

The first term in (29) is just the projection of the centroid of the sensor positions onto the line $L_\theta$ as shown in (30) and (31). And, the second term in (29) is the average of the measured distances by the central measurements. Therefore, (29) is the proof for our new concept i.e., Circular Uncertainty and for its parameters which have been intuitively defined in the previous section.

$$\begin{aligned}&{\hat{r}} \left( \theta \right) \approx \frac{1}{N}\mathop \sum \limits _{i=1}^N \left[ {\cos \left( \theta \right) \sin \left( \theta \right) } \right] \left[ {{\begin{array}{l} {x_i } \\ {y_i } \\ \end{array} }} \right] + \frac{1}{N}\mathop \sum \limits _{i=1}^N D_i \end{aligned}$$

(30)

$$\begin{aligned}&{\hat{r}} \left( \theta \right) \approx \left[ {\cos \left( \theta \right) \sin \left( \theta \right) } \right] \left( {\frac{1}{N}\mathop \sum \limits _{i=1}^N \left[ {{\begin{array}{l} {x_i } \\ {y_i } \\ \end{array} }} \right] } \right) + \frac{1}{N}\mathop \sum \limits _{i=1}^N D_i \end{aligned}$$

(31)

Fig. 4

a The simulation setup—a sample measurement scheme and b the RMS distance error of localization: Circular Uncertainty and NLS

3.3 Solving NLS equation via Circular Uncertainty

In this section, it is demonstrated how Circular Uncertainty can be utilized to conveniently solve the NLS equation in (15). By means of Circular Uncertainty, the size of search space will be reduced. As mentioned above, global minimum occurs along the Circular Uncertainty possibly with a small deviation. Therefore, the global minimum must be searched along the Circular Uncertainty whose parameters are defined in (19) and (20). Let us write the equation of Circular Uncertainty as a function of $\theta$ as the following:

$$\begin{aligned} x\left( \theta \right)= & {} x_{CU} +r_{CU} \hbox {cos}\left( \theta \right) \end{aligned}$$

(32)

$$\begin{aligned} y\left( \theta \right)= & {} y_{CU} +r_{CU} \hbox {sin}\left( \theta \right) \end{aligned}$$

(33)

Therefore, the NLS equation in (15) can be rewritten as the following:

$$\begin{aligned} \left( {{\hat{\theta }} } \right) = \mathop {\hbox {argmin}}\limits _{\left( \theta \right) } \mathop \sum \limits _{i=1}^N \left( {\sqrt{\left( {x_{CU} +r_{CU} \hbox {cos}\left( \theta \right) -X_i } \right) ^{2}+ \left( {y_{CU} +r_{CU} \hbox {sin}\left( \theta \right) -Y_i } \right) ^{2}}- D_i } \right) ^{2}\nonumber \\ \end{aligned}$$

(34)

As seen, the size of search space is reduced by means of Circular Uncertainty. Furthermore, because $\theta$ is periodic, only the range $\left( {0,2\pi } \right]$ is of interest instead of infinite intervals for x or y in (15). In Fig. 4a, the setup of a Monte Carlo simulation which consists of 1000 iterations is shown. In each iteration, the eight sensors are randomly positioned within the square area limited by the interval [−10, 10] along x and y axis. The target (emitter or source) is randomly located anywhere within the interval [−80, 80] along x and y axis, yet it is not allowed to stay close to the origin smaller than 30 units i.e. not inside the circle drawn as dashed line. In Fig. 4b, the performances of localization by Circular Uncertainty and conventional distance NLS are shown as root mean squared (RMS) distance error. As seen, both distance NLS and Circular Uncertainty can attain CRLB. However, in Sect. 4.3, it will be shown that the execution time of the Circular Uncertainty is quite smaller than NLS. Therefore, Circular Uncertainty is found to be a convenient solution when all sensor positions are precise. However, the real benefit of this solution will be apparent in the next sections in which the issue of imprecise sensor positions is discussed.

3.4 MLE solution by Circular Uncertainty

In practical situations, the sensors can only be allowed to be located within a limited region and the target can be located far from the sensors. In order to increase estimation capability, in addition to the central measurements taken within a limited region, a few number of peripheral measurements can be deployed. However, to scan a broad peripheral area, the peripheral measurements can be designed as moving sensors, which, as a result, brings the issue of uncertainties in the positions of sensors as discussed in the literature (Ho et al. 2007). In this section, it is demonstrated how Circular Uncertainty can be utilized to conveniently solve the MLE for this type scenario in which there are uncertainties in sensor positions for peripheral measurements. First, let us rewrite the parameters of the Circular Uncertainty as the following:

$$\begin{aligned} \left( {x_{CU} , y_{CU} } \right)= & {} \left( {\frac{1}{M}\mathop \sum \limits _{i \in C} x_i , \frac{1}{M}\mathop \sum \limits _{i \in C} y_i } \right) \end{aligned}$$

(35)

$$\begin{aligned} r_{CU}= & {} \frac{1}{M}\mathop \sum \limits _{i \in C} D_i \end{aligned}$$

(36)

where C is the set of central measurements with precise positions and M is the number of elements in this set. In accordance with the Circular Uncertainty equations of (32) and (33), MLE equation in (18) can be rearranged as the following:

$$\begin{aligned}&\left( {{\hat{\theta }} , \left\{ {{\hat{x}} _j ,{\hat{y}} _j | j\in P} \right\} } \right) \nonumber \\&\quad =\mathop {\hbox {argmin}}\limits _{\left( {\theta , \left\{ {x_j ,y_j | j\in P} \right\} } \right) } \left( {{\begin{array}{l} { \frac{1}{\left( {\sigma _D } \right) ^{2}}\mathop \sum \limits _{i \in C} \left( {\sqrt{\left( {x\left( \theta \right) -x_i } \right) ^{2}+ \left( {y\left( \theta \right) -y_i } \right) ^{2}}- D_i } \right) ^{2}} \\ {+\mathop \sum \limits _{j \in P} \left\{ {{\begin{array}{l} {\frac{1}{\left( {\sigma _D } \right) ^{2}} \left( {\sqrt{\left( {x\left( \theta \right) -x_j } \right) ^{2}+ \left( {y\left( \theta \right) -y_j } \right) ^{2}}- D_j } \right) ^{2} } \\ {+\frac{1}{\left( {\sigma _S } \right) ^{2}} \left( {\left( {X_j -x_j } \right) ^{2}+ \left( {Y_j -y_j } \right) ^{2}} \right) } \\ \end{array} }} \right\} } \\ \\ \end{array} }} \right) \qquad \quad \end{aligned}$$

(37)

where P is the set of peripheral measurements with imprecise positions. In order to find the global minimum, the number of parameters to be estimated is $2L+2$ where L is the number of measurements with imprecise positions (i.e. the size of the set P). By means of Circular Uncertainty, this number is reduced to $2L+1$ by representing both x and y-axis of the target as a function of $\theta$. Moreover, if we also achieve to represent the imprecise sensor positions minimizing the MLE cost as a function of $\theta$, then the total number of parameters to be estimated will be reduced to 1 i.e. only $\theta$. Let us consider the estimation of a single imprecise sensor position which minimizes jointly distance and sensor position errors given the location of the target $\left( {x\left( \theta \right) , y\left( \theta \right) } \right)$ :

$$\begin{aligned} \left( {{\hat{x}} _j ,{\hat{y}} _j } \right) =\mathop {\hbox {argmin}}\limits _{\left( {x_j ,y_j } \right) } \left( {{\begin{array}{l} { \frac{1}{\left( {\sigma _D } \right) ^{2}}\left( {\sqrt{\left( {x\left( \theta \right) -x_j } \right) ^{2}+ \left( {y\left( \theta \right) -y_j } \right) ^{2}}- D_j } \right) ^{2}} \\ {+ \frac{1}{\left( {\sigma _S } \right) ^{2}} \left( {\left( {X_j -x_j } \right) ^{2}+ \left( {Y_j -y_j } \right) ^{2}} \right) } \\ \end{array} }} \right) \end{aligned}$$

(38)

First of all, in order to minimize (38), the estimated position of the sensor $\left( {{\hat{x}} _j , {\hat{y}} _j } \right)$, the measured position of the sensor $\left( {X_j , Y_j } \right)$ and the location of the target $\left( {x, y} \right)$ must linearly align because of triangular inequality.

Fig. 5

The estimated position of the sensor $\left( {{\hat{x}} _j , {\hat{y}} _j } \right)$, the measured position of the sensor $\left( {X_j , Y_j } \right)$ and the location of the target $\left( {x, y} \right)$ must linearly align

Let us designate the distance error as $\varDelta$ and the sensor position error as $\delta$. In Fig. 5a, an estimation for the sensor position is shown which does not lie on the line which passes through $\left( {X_j , Y_j } \right)$ and $\left( {x\left( \theta \right) , y\left( \theta \right) } \right)$. It is apparent that the projection point of this estimation onto this line would yield smaller $\varDelta$ and $\delta$ so a smaller cost value. Therefore, the solution of (38) must be located on the line which passes through the measured position of the sensor $\left( {X_j , Y_j } \right)$ and the location of the target $\left( {x\left( \theta \right) , y\left( \theta \right) } \right)$ as shown in Fig. 5b. For this scheme, we need to only find the lengths of $\varDelta$ and $\delta$. Therefore, solving (38) can be equivalently achieved by solving the following equation:

$$\begin{aligned} \left( {{\hat{\varDelta }} , \hat{\delta } } \right) = \mathop {\hbox {argmin}}\limits _{\left( {\varDelta , \delta } \right) } \left( {\frac{1}{\left( {\sigma _D } \right) ^{2}} \left( \varDelta \right) ^{2}+ \frac{1}{\left( {\sigma _S } \right) ^{2}} \left( \delta \right) ^{2}} \right) \end{aligned}$$

(39)

subjected to the constraint:

$$\begin{aligned} \varDelta + \delta = \zeta =\sqrt{\left( {x\left( \theta \right) -X_j } \right) ^{2}+ \left( {y\left( \theta \right) -Y_j } \right) ^{2}}- D_j \end{aligned}$$

(40)

where $\zeta$ is the difference between the measured distance $D_j$ and the distance between the target and the measured position of the sensor $\left( {X_j , Y_j } \right)$. If we insert the following equity into the cost function shown in (39):

$$\begin{aligned} \varDelta =\zeta -\delta \end{aligned}$$

(41)

and then if we take the derivative of this cost function with respect to $\delta$, we obtain the following the equation:

$$\begin{aligned} 2 \left( {\sigma _D } \right) ^{2} \delta -2 \left( {\sigma _S } \right) ^{2} \left( {\zeta -\delta } \right) =0 \end{aligned}$$

(42)

Therefore, the estimated value of $\delta$ which minimizes (39) is as the following:

$$\begin{aligned} \hat{\delta } =\frac{\left( {\sigma _S } \right) ^{2}}{\left( {\sigma _S } \right) ^{2}+ \left( {\sigma _D } \right) ^{2}} \left( {\sqrt{\left( {x\left( \theta \right) -X_j } \right) ^{2}+ \left( {y\left( \theta \right) -Y_j } \right) ^{2}}- D_j } \right) \end{aligned}$$

(43)

Based on this value, we can write the estimated sensor position $\left( {{\hat{x}} _j ,{\hat{y}} _j } \right)$ which minimizes (38) is as the following:

$$\begin{aligned} {\hat{x}} _j =X_j + \hat{\delta } \frac{\left( {x-X_j } \right) }{\sqrt{\left( {x-X_j } \right) ^{2}+ \left( {y-Y_j } \right) ^{2}}} \end{aligned}$$

(44)

$$\begin{aligned} {\hat{y}} _j =Y_j + \hat{\delta } \frac{\left( {y-Y_j } \right) }{\sqrt{\left( {x-X_j } \right) ^{2}+ \left( {y-Y_j } \right) ^{2}}} \end{aligned}$$

(45)

Finally, we can write (44) and (45) as the functions of $\theta$:

$$\begin{aligned}&{\hat{x}} _j \left( \theta \right) =X_j + \frac{\left( {\sigma _S } \right) ^{2}}{\left( {\sigma _S } \right) ^{2}+ \left( {\sigma _D } \right) ^{2}}\nonumber \\&\quad \left( {1-\frac{D_j }{\sqrt{\left( {x\left( \theta \right) -X_j } \right) ^{2}+ \left( {y\left( \theta \right) -Y_j } \right) ^{2}}}} \right) \left( {x\left( \theta \right) -X_j } \right) \end{aligned}$$

(46)

$$\begin{aligned}&{ \hat{y}} _j \left( \theta \right) =Y_j + \frac{\left( {\sigma _S } \right) ^{2}}{\left( {\sigma _S } \right) ^{2}+ \left( {\sigma _D } \right) ^{2}} \nonumber \\&\quad \left( {1-\frac{D_j }{\sqrt{\left( {x\left( \theta \right) -X_j } \right) ^{2}+ \left( {y\left( \theta \right) -Y_j } \right) ^{2}}}} \right) \left( {y\left( \theta \right) -Y_j } \right) \end{aligned}$$

(47)

To sum up, we can rewrite the MLE cost function in (37) as a function of $\theta$:

$$\begin{aligned} \left( {{\hat{\theta }} } \right) =\mathop {\hbox {argmin}}\limits _\theta \left( {{\begin{array}{l} { \frac{1}{\left( {\sigma _D } \right) ^{2}}\mathop \sum \limits _{i \in C} \left( {\sqrt{\left( {x\left( \theta \right) -x_i } \right) ^{2}+ \left( {y\left( \theta \right) -y_i } \right) ^{2}}- D_i } \right) ^{2}} \\ {+\mathop \sum \limits _{j \in P} \left\{ {{\begin{array}{l} {\frac{1}{\left( {\sigma _D } \right) ^{2}} \left( {\sqrt{\left( {x\left( \theta \right) -{\hat{x}} _j \left( \theta \right) } \right) ^{2}+ \left( {y\left( \theta \right) -{\hat{y}} _j \left( \theta \right) } \right) ^{2}}- D_j } \right) ^{2} } \\ {+\frac{1}{\left( {\sigma _S } \right) ^{2}} \left( {\left( {X_j -{\hat{x}} _j \left( \theta \right) } \right) ^{2}+ \left( {Y_j -{\hat{y}} _j \left( \theta \right) } \right) ^{2}} \right) } \\ \end{array} }} \right\} } \\ \\ \end{array} }} \right) \nonumber \\ \end{aligned}$$

(48)

After representing the imprecise sensor positions as a function of $\theta$, the total number of parameters to be estimated within MLE equation in (37) is reduced from $2L+1$ to 1, in other words, the global minimum will be only searched through the parameter $\theta$.

4 Simulations

4.1 Imprecise sensor positions within central measurements

In this section, a Monte Carlo simulation which consists of 1000 iterations is conducted for the scenario where there are eight central measurements with precise position together with three central measurements with imprecise positions. The standard deviation of the sensor position error $\sigma _S$ is set to 3. Fig. 6a shows the simulation setup by means of a sample measurement scheme. In each iteration, while both the sensors and target are randomly positioned, they are subjected to the same constraints of Fig. 4a (concerning the positions of the sensors and the target). In Fig. 6b, the performance of various localization techniques are compared to each other by means of RMS distance error of localization.

Fig. 6

a The simulation setup—a sample measurement scheme with eight central precise and three central imprecise measurements and b the RMS distance errors for various localization method

Distance NLS is the localization which simply minimizes the conventional NLS cost function in (15) without taking the uncertainties in sensor positions into account. Circular Uncertainty is the localization technique that we have introduced in (34). Circular Uncertainty in (34) again does not take the uncertainties in sensor positions into account. “Circ. Unc. + Dist NLS” is the method where the estimation of the Circular Uncertainty is used as the initial point of Distance NLS. The significance of this type initialization will be apparent in the next sections. For this scenario, these methods i.e. Distance NLS, Circular Uncertainty and “Circ. Unc. + Dist NLS” have the equivalent rate of performance which is significantly above CRLB. SR-WLS is the abbreviation of the squared range weighted least-squares introduced by Chen and Ho (2014). They introduce this algorithm in order to conveniently solve the localization problems with imprecise sensor positions. Unlike MLE, SR-WLS avoids jointly estimating the target and the sensor positions. It solves a least squares equation whose terms are skillfully weighted by also taking the uncertainties in the sensor positions into account.

While implementing SR-WLS, because we assume that the standard deviation of sensor position errors along x and y axis are the same i.e. $\sigma _S$ and the errors are independent, the A matrix (introduced in Chen and Ho 2014) is removed during calculation of the weighting matrix W as shown below:

$$\begin{aligned} W=\left[ {B \left( {Q_D + Q_S } \right) B } \right] ^{-1} \end{aligned}$$

(49)

where $Q_D$ is the diagonal matrix whose diagonal elements are $\left( {\sigma _D } \right) ^{2}$, and $Q_S$ is an $11\times 11$ matrix as the following:

$$\begin{aligned} Q_S =\left[ \begin{array}{l@{\quad }l@{\quad }l@{\quad }l@{\quad }l@{\quad }l} { 0}&{} &{}&{}&{}\\ &{} \ddots &{}&{}&{}\\ &{} &{} 0 &{}&{}&{}\\ &{}&{}&{}{\sigma _S^2 }&{} &{} \\ &{}&{}&{}&{} {\sigma _S^2 }&{} \\ &{}&{}&{}&{} &{} {\sigma _S^2 } \\ \end{array} \right] _{11x11} \end{aligned}$$

(50)

and B is the matrix as defined in Chen and Ho (2014). While constructing $Q_S$, it is assumed that the last three measurements have imprecise positions. By removing the matrix A, the need for an initial estimation for the target position mentioned in Chen and Ho (2014) is also removed.

As seen in Fig. 6b, SR-WLS and MLE by the Circular Uncertainty in (48) introduced in the previous section can attain CRLB while the former methods which do not take the uncertainties in the sensor positions into account fail to achieve this performance. SR-WLS weights the sensor according to their closeness to target, the relative error level in distance measurements and the standard deviation of sensor positions. In this sense, for the simulation setup that we have defined in Fig. 6a, SR-WLS opts to weight the three sensors with imprecise positions with smaller numbers. By doing this, SR-WLS reduces the importance of these sensors because they are not reliable due to their uncertain positions. This is the justification of the success of SR-WLS in attaining CRLB. However, a trade-off will occur when you need to heavily rely on the sensors with imprecise positions if they are peripheral measurements instead of central ones. Therefore, the true benefit of MLE with Circular Uncertainty will be more apparent in the next sections.

4.2 The benefit of peripheral measurements

It has been discussed that when there are only central sensors which take distance-to-target measurements, the localization suffers from a low capability of estimating the angular position of the target. Therefore, in addition to the central measurements, a few number of peripheral measurements can be deployed to increase the estimation capability of localization system. To scan a broad peripheral area, the peripheral measurements can be designed as moving sensors which at the end brings the issue of uncertainties in the positions of peripheral sensors. Nevertheless, in this section, it is shown how peripheral measurements even with imprecise positions can significantly increase the performance of the localization systems. In Fig. 7, two CRLBs are shown for two different localization scenarios. Both of these two scenarios employ the same number of measurements i.e. eight measurements with precise positions and three measurements with imprecise positions. However, the distinction is that in the first scenario, three imprecise measurements are the central ones together with other eight measurements while in the second scenario, they are employed as peripheral measurements. The first scenario is the one which is already shown in Fig. 6a and the second scenario is depicted in Fig. 8a. In the second scenario, the peripheral measurements are allowed to be randomly distributed within peripheral area just like the target, however they are not allowed to get close to the target smaller than 5 units. The standard deviation of the sensor position error $\sigma _S$ is set to 3. As seen in Fig. 7, the peripheral measurements can significantly increase the performance of the range-only localization system. Please note that RMS distance errors are plotted in log-scale, so the difference between these two CRLBs points to a significant increase in the performance.

Fig. 7

Increase in the performance of localization systems by means of peripheral measurements

4.3 The simulation including peripheral measurements with imprecise positions

In this section, the simulation including peripheral measurements with imprecise positions is presented. A Monte Carlo simulation which consists of 1000 iterations is conducted to determine the localization performance of the algorithms. The simulation setup is depicted in Fig. 8a by means of a sample measurement scheme where there are eight central measurements with precise positions and three peripheral measurements with imprecise positions and the standard deviation of the sensor position error $\sigma _S$ is set to 3. In each iteration, the sensors and the target are randomly positioned in accordance with the peripheral and central constraints settled in previous simulations. As depicted previously, in order to take the advantage of the peripheral measurements, the localization system must rely on the peripheral measurements even though their positions are imprecise. The first method shown in Fig. 8b is Distance NLS. Because of peripheral measurements, the surface of the conventional distance NLS cost function becomes somewhat complicated, so the conventional distance NLS suffers from local minima. Therefore, Distance NLS presents the worst performance in this scenario because of convergence issues. However, Circular Uncertainty that we have introduced in (34) presents a better performance compared to distance NLS. We have mentioned that Circular Uncertainty is a safe and reliable way of obtaining global minimum. When the estimation of Circular Uncertainty is employed as the initial point of Distance NLS, then Distance NLS can be also guided to obtain the global minimum. Therefore, “Circ. Unc. + Dist. NLS” has the same level of RMS error with Circular Uncertainty, and this level is quite smaller than that of only Distance NLS. In this context, the important advantage of Circular Uncertainty which safely obtains the global minimum becomes visible.

Fig. 8

a The simulation setup—a sample measurement scheme with eight central precise and three peripheral imprecise measurements, b the RMS distance errors for various localization methods

The next thing to be discussed about Fig. 8b is that SR-WLS fails to attain CLRB for high level of distance-to-target measurement errors. It has been discussed that the strategy of the SR-WLS is to reduce the weights of the measurements with imprecise positions in order not to rely on these measurements. However, our major aim here is to take the advantage of the peripheral measurements as much as possible despite their positions are imprecise in order to exploit all available information for localization of the target. Therefore, this situation creates a trade-off for SR-WLS. On the other hand, as a complete basis for estimation, the MLE solution can apparently do better than weighted least squares algorithms. MLE solution automatically takes the standard deviations of errors in distance measurements and imprecise sensor positions into account. Not only these, it also takes the geometry or the arrangement of sensors into account, which guarantees a superior performance. Eventually, our proposed method, i.e. MLE by Circular Uncertainty, can demonstrate better performance compared to all other competing methods. Circular Uncertainty or “Circ. Unc. + Dist. NLS” can not attain CRLB for low $\sigma _D$ levels and oppositely SR-WLS can not attain CRLB for high $\sigma _D$ levels. However, MLE by Circular Uncertainty can always attain CRLB for all levels of $\sigma _D$ as seen in Fig. 8b.

Table 1 Average execution times of the algorithms when these algorithms are performed on an ordinary desktop computer

Finally, average execution times of these algorithms are provided in Table 1, when these algorithms are performed on an ordinary desktop computer with Intel Core(TM) i7-3630QM CPU@2.40 GHz Processor and 16 GB RAM via MATLAB. As can be seen, Circular Uncertainty has the smallest execution time (0.049 s) while Distance NLS follows it with an important gap. Circular Uncertainty attains this performance gain because it skillfully reduces the NLS localization problem to a simple task. Circular Uncertainty searches the global minimum in a one-dimensional space while distance NLS makes a two-dimensional search. Circ. Unc. + Dist NLS comes after these methods with 0.071 s. After these three methods which do not take the uncertainty in the sensor positions into account, SR-WLS comes with 0.073 s of execution time in average. This execution time is quite closer to that of Distance NLS or Circ. Unc. + Dist NLS. The success of SR-WLS in terms of execution time is that it makes use of the squared ranges in order not deal with square roots in the estimation cost function. The last method in terms execution time is MLE by Circular Uncertainty. However, the average execution time of MLE by Circular Uncertainty and SR-WLS are almost same. When it is considered that this method achieves a very complicated task and it outperforms all the other methods in terms of localization error, MLE by Circular Uncertainty appears as the most effective method among others. When, there exist uncertainties in sensor positions, the success of MLE by Circular Uncertainty in terms of both localization accuracy and execution time is due the fact that it reduces the multi-dimensional search space in into one-dimensional space without decreasing the localization accuracy.

5 Conclusion

In localization systems, the biggest problem with the MLE solution is that it is said to be computationally inefficient. Moreover, because of local minima or irregular cost functions, attempting to reach MLE solution can be sometimes problematic or even impossible. In this study, a new method called Circular Uncertainty is introduced to effectively and reliably solve a very complicated MLE problem. Circular certainty not only makes it possible to reach MLE solutions, but also significantly simplifies this task. A high dimensional joint estimation problem is reduced to the estimation of only a single parameter i.e. $\theta$. The success of Circular Uncertainty is to innovatively handle the range-only localization problem with solid observations. Future studies can take the advantage of this or other similar structures to make the complex localization problems easy or possible.

Appendix

In this section, the MLE cost function of range-only localization in the presence of uncertainties of sensor positions is explained in detail. The multivariate likelihood function of all parameters in ${\vec {q}}$ based on the distance-to-target and sensor position measurements can be written as the following,

$$\begin{aligned} p\left( {\vec {D},\vec {X},~\vec {Y};\vec {q}} \right)= & {} \frac{1}{{\sqrt{\left( {2\pi } \right) ^{N} ~~\left| {C_{D} } \right| } ~}}e^{{ - ~\left( {\vec {D} - ~\vec {\mu }_{d} } \right) ~~C_{D} ^{{ - 1}} \left( {\vec {D} - ~\vec {\mu }_{d} } \right) ^{T} ~}} ~~\nonumber \\&\cdot \frac{1}{{\sqrt{\left( {2\pi } \right) ^{N} ~~\left| {C_{X} } \right| } ~}}e^{{ - ~\left( {\vec {X} - ~\vec {\mu }_{x} } \right) ~~C_{X} ^{{ - 1}} ~\left( {\vec {X} - ~\vec {\mu }_{x} } \right) ^{T} }} \nonumber \\&\cdot ~~\frac{1}{{\sqrt{\left( {2\pi } \right) ^{N} ~~\left| {C_{Y} } \right| } ~}}~~e^{{-~\left( {\vec {Y} - ~\vec {\mu }_{y} } \right) ~~C_{Y} ^{{ - 1}} ~\left( {\vec {Y} - ~\vec {\mu }_{y} } \right) ^{T} }} \end{aligned}$$

(51)

where $C_D$, $C_X$ and $C_Y$ are the covariance matrices of the distance-to-target measurements as well as the measurements of x and y position of the sensors respectively. ${\vec {\mu }}_d$ is the vector of the distance-to-target values as a vector valued function of the parameters in ${\vec {q}}$,

$$\begin{aligned} \vec {\mu }_{d} = \left[ {\begin{array}{c} {\sqrt{\left( {x - x_{1} } \right) ^{2} + ~\left( {y - y_{1} } \right) ^{2} } }\\ \vdots \\ {\sqrt{\left( {x - x_{i} } \right) ^{2} + ~\left( {y - y_{i} } \right) ^{2} } } \\ \vdots \\ {\sqrt{\left( {x - x_{N} } \right) ^{2} + ~\left( {y - y_{N} } \right) ^{2} } } \\ \end{array} } \right] ^{T} \end{aligned}$$

(52)

Furthermore, ${\vec {\mu }}_x$ and ${\vec {\mu }}_y$ are the vectors of the x positions and the y positions of the sensors respectively based on the parameters in ${\vec {q}}$. Because of the measurement model that is defined in (2), (3) and (4), all measurements are independent, so the covariance matrices are diagonal ones as the followings,

$$\begin{aligned} C_D= & {} \left[ {{\begin{array}{l@{\quad }l@{\quad }l@{\quad }l} {\sigma _D ^{2}}&{} &{} &{}\\ &{} {\sigma _D ^{2}}&{} &{}\\ &{} &{} \ddots &{}\\ &{}&{}&{} {\sigma _D ^{2}} \\ \end{array} }} \right] _{NxN} \end{aligned}$$

(53)

$$\begin{aligned} C_X= & {} C_Y =\left[ {{\begin{array}{l@{\quad }l@{\quad }l@{\quad }l} {\sigma _S ^{2}}&{} &{} &{}\\ &{} {\sigma _S ^{2}}&{} &{}\\ &{} &{} \ddots &{}\\ &{}&{}&{} {\sigma _S ^{2}} \\ \end{array} }} \right] _{NxN} \end{aligned}$$

(54)

Therefore, (51) can be rewritten as the following expression,

$$\begin{aligned} p\left( {\vec {D},\vec {X},~\vec {Y};\vec {q}} \right)= & {} {} \left( \frac{1}{{\sqrt{{2\pi ~\sigma _{D} ^{2} ~}}}}\right) ^{N}e^{{ - ~\frac{1}{{\left( {\sigma _{D} } \right) ^{2} }}\mathop \sum \nolimits _{{i = 1}}^{N} \left( {\sqrt{\left( {x - x_{i} } \right) ^{2} + ~\left( {y - y_{i} } \right) ^{2} } - ~D_{i} } \right) ^{2} ~}} ~\nonumber \\&\cdot \left( \frac{1}{\sqrt{{2\pi \sigma _s ^{2} } }}\right) ^{N}e^{- \frac{1}{\left( {\sigma _S } \right) ^{2}} \mathop \sum \nolimits _{i=1}^N \left( {X_i -x_i } \right) ^{2}} . \left( \frac{1}{\sqrt{{2\pi \sigma _s ^{2} }}}\right) ^{N} e^{ - \frac{1}{\left( {\sigma _S } \right) ^{2}} \mathop \sum \nolimits _{i=1}^N \left( {Y_i -y_i } \right) ^{2}}\nonumber \\ \end{aligned}$$

(55)

Finally, the log-likelihood of the all the parameters in ${\vec {q}}$ can be written as the following,

$$\begin{aligned} \ln p\left( {\vec {D},\vec {X},~\vec {Y};\vec {q}} \right)= & {} - ~\frac{1}{{\left( {\sigma _{D} } \right) ^{2} }}\mathop \sum \limits _{{i = 1}}^{N} \left( {\sqrt{\left( {x - x_{i} } \right) ^{2} + ~\left( {y - y_{i} } \right) ^{2} } - ~D_{i} } \right) ^{2}\nonumber \\&- ~\frac{1}{{\left( {\sigma _{S} } \right) ^{2} }}~\mathop \sum \limits _{{i = 1}}^{N} \left[ {\left( {X_{i} - x_{i} } \right) ^{2} + ~\left( {Y_{i} - y_{i} } \right) ^{2} } \right] + K \end{aligned}$$

(56)

where is K is a constant such that,

$$\begin{aligned} K=- N \ln \left( {\sqrt{2 \pi \left( {\sigma _D } \right) ^{2}}} \right) -2 N \ln \left( {\sqrt{2 \pi \left( {\sigma _S } \right) ^{2}}} \right) \end{aligned}$$

(57)