Performance Evaluation of Localization Algorithms for WSNs

Abstract

In recent years, the use of wireless sensor networks has been increasing. Localization is a fundamental problem in wireless sensor networks (WSNs), since location information is essential for diverse applications such as tracking, quality network coverage, health, and energy efficiency. In this paper performance of localization algorithms such as range-free, range-based, and fuzzy-based decision is evaluated. We introduce a modification of an algorithm by providing weights to the correlation matrix to improve correctness. In all the cases the accuracy, precision, and computational complexity are evaluated as performance metrics. Location algorithms are evaluated using two scenarios, a first stage where all nodes are randomly distributed in a given area and a second scenario where four APs (access points) are placed on fixed positions and unknown nodes are randomly distributed within the sensing area. The received signal strength (RSS) is used to estimate the position of a node of interest. In the simulation results we show how our modified algorithm improves localization. On the other hand, we also have acceptable accuracy using distance-based algorithms, but they are more complex computationally.

1. Introduction

WSNs have attracted the attention of the scientific community to be the technology for the future, to sense the environment wirelessly with devices extremely small and inexpensive [1]. In many applications, the sensed information is useful only when the location from where such information was measured is known. Thus, sensor nodes need to estimate their position [1, 2]. Additionally, WSNs need more efficient and robust protocols to further optimize network resources, such as energy and response time, depending on the position of the nodes. The precise location of sensors at low cost is a critical requirement for deployment of WSNs in a wide variety of applications (see [3, 4]), such as animal tracking, which allows analyzing animal behavior and interactions with other species, logistics, where sensors report their location when required to be found, and health, where location of equipment and medical employees in emergencies [5] is needed.

Node localization is described according to a reference coordinate system, defined by anchor nodes with known positions [6]. However, in reconfigurable networks such as ad hoc and sensor networks, connectivity is not always direct, and anchor nodes or access points are connected through multiple hops to the node of interest (NOI) [6, 7]. In a multihop scenario, [3], neighboring nodes provide information of the NOI (unknown coordinates) and help to estimate its location. Currently there are many techniques for determining the distance between sensor nodes. GPS systems are very useful in outdoor scenarios; however, their performance is affected adversely in indoor scenarios [6, 8], and the increase in hardware for the sensors and energy consumption make it difficult for GPS to be considered as an integral solution. Also, traditional multilateration techniques can be of use in certain scenarios where estimation is based on signal strength, time, or angle of arrival. In time of arrival (TOA) technique, the nodes physically calculate distance through speed and time of signal propagation. In angle of arrival (AOA) distance to the NOI is estimated by using the direction of the signal received by nodes usually through an antenna array. In time difference of arrival (TDOA), nodes calculate the time difference to avoid dependence on departure time of signal, and multilateration is achieved combining these differences from several anchor nodes. In received signal strength indicator (RSSI) the power received by the node is used to calculate the propagation loss and estimate distance, using theoretical or empirical model of path loss [1].

This paper presents a performance evaluation of RSS-based localization algorithms. These techniques are a perfect fit to be implemented in simple systems, since AOA-based distance estimation involves costly hardware, TOA requires perfect synchronization, and TDOA is coverage limited [9]. The performance evaluation algorithm is carried out to determine the efficiency and the relevance in the use of localization or positioning algorithms in wireless sensor networks. We briefly introduce range-free and range-based position location algorithms, as well as those based on fuzzy decision techniques to later modify one of the algorithms by assigning weights to the correlation matrix and show how this change improves accuracy. All the algorithms are analyzed using root mean squared (rms) error between the estimated position and the true location of the NOI. We show that our proposed algorithm performs well for different noise scenarios and with increasing network node density. We provide a qualitative analysis of performance of the algorithms and a computing complexity analysis in terms of processing time as a function of node density as means to help one decide the best position location technique to apply.

The rest of the paper is organized as follows. Section 2 formally presents the fundamental position location problem and the signal propagation model that is used throughout the paper. In Section 3 the localization techniques are described, which are classified into two types: range-based and range-free algorithms. Section 4 presents a modification of the weighted least squares multilateration algorithm. Meanwhile, in Section 5, the performance of these algorithms is evaluated under two scenarios, and the main results obtained are shown in terms of defined performance metrics. The two main scenarios consist of a randomly generated node network and a structured set of four reference nodes with a randomly generated node network. Finally we highlight the main conclusions of this research and references that support it.

2. Problem Statement

Consider a set of sensor nodes on a two-dimensional plane where a NOI with unknown coordinates $p=\left(x,y\right)$ is to be located. There is also a set of N anchor nodes of known coordinates $p_i=\left(x_i,y_i\right)$ , $i=\mathrm{1,2},\dots ,N$ , within the NOI transmission range, where the power received by anchor node i from a signal transmitted by the NOI is denoted by $v_i$ .

The log-normal propagation model is used to estimate the power received, where the signal power is inversely proportional to the separation distance $d^{-n}$ , where n is the path loss exponent. This model is expressed by

$$\begin{array}{cc}& P_{R,\text{dB}}\left(d\right)=A-\mathrm{10}n\log \frac{d}{d_{\mathrm{0}}}+X_{\sigma },\end{array}$$

(1)

where A is the average power received at a reference distance $d_0$ . $X_{\sigma }$ is a Gaussian random variable with zero mean and standard deviation σ in dB. Typical values for the path loss exponent are in the range of 1.5 through 5 and for σ in the range of values from 4 to 12 dB; see [6, 10]. Multilateration is used in order to estimate the position of the NOI.

3. Related Work: Localization Techniques

Localization techniques are mainly classified into two categories: range-based and range-free [11]. Range-based techniques need to estimate distances between nodes and the NOI in order to estimate its position. Distance is usually estimated using RSSI, TOA, or TDOA. Some of these techniques are multilateration [7]; multidimensional scaling (MDS) [12]; ad hoc positioning systems [13]; and circular positioning and hyperbolic algorithms [14]. Range-free techniques are those where NOI position estimation is not based on the distance estimation between nodes but on the solution to heuristic or optimization problems with a decentralized characteristic [15]. This group of techniques includes DV-Hop [7, 16, 17]; approximate point in triangle [7, 18]; centroid [7]; rectangular intersection [19]; circular intersection [19]; and hexagonal intersection [19] among others. In this section, we present briefly several range-free and range-based techniques that will be compared to our proposed algorithm in Section 5.

3.1. Range-Free Techniques

Range-free localization techniques involve the received signal strength in order to estimate separation distance to the NOI and calculate its position. Within this group, there are some techniques that require knowing the location of reference nodes to estimate the position of other nodes, such as APIT [18, 20], which creates all possible combinations of triangles with three reference nodes to estimate the overlapped area of these triangles where the NOI is found by calculating the centroid of the intersection area of the triangles. The advantage of this method is that it is accurate for high density networks, but their computational cost is very high as more triangles are added. There are also other methods based on the same criteria as APIT, for example, the circular intersection algorithm, which finds the area resulting from the intersection of circles centered at the nodes. This method is also computationally costly. However, rectangular intersection algorithm requires less computational complexity, since the resulting figure from the intersection of boxes is a rectangle. Nevertheless, the rectangular intersection algorithm is less accurate than the circular intersection algorithm [19]. Given a set of receivers or anchor nodes within transmission range of a node to be located, we can formulate the idea of the centroid by approximating the coordinate of the unknown node as the average of a set of known N anchor node positions $p_i$ [21]

$$\begin{array}{cc}& p=\frac{\mathrm{1}}{N}{{\displaystyle \sum }}_{i=\mathrm{0}}^N{p}_i.\end{array}$$

(2)

In the following, we describe range-free algorithms based on the centroid and nearest neighbor techniques, with a brief introduction of the form in which position is estimated.

3.1.1. Weighted Centroid Localization (WCL) Algorithm

The centroid localization (CL) approach assumes that all anchor nodes are approximately equidistant from the NOI. However, [22] argues that some reference nodes are more likely than others to be close to the NOI, thus under this argument it proposes the weighted centroid localization (WCL) scheme that uses weights to improve location accuracy. It assigns greater weight to the positions of those anchor nodes closer to the NOI and less weight to the farthest ones. The weighted centroid is computed as

$$\begin{array}{cc}& p=\frac{{\sum }_{i=\mathrm{0}}^N{w}_i{p}_i}{{\sum }_{i=\mathrm{0}}^N{w}_i},\end{array}$$

(3)

with the weights $w_i=d_i^{-k}$ , where $d_i$ is the known distance, estimated by some approach such as TOA, TDOA, AOA, or RSS [9], between the NOI and the anchor node. The exponent influences the degree of estimation of the unknown node. The values are determined manually according to [23], for example, for a transmission range of 10 m, $k=1$ , and for a transmission range of 20 m, $k=2$ .

3.1.2. Relative Weighted Localization (RWL) Algorithm

This approach is similar to that of the WCL scheme, except that the weights are assigned by a linear relationship of the RSS measured values of each receiver [24]. Denote ${\upsilon }_i$ as the current RSS value measured at anchor node i and also define the maximum value as ${\upsilon }_{\max }$ , the minimum value as ${\upsilon }_{\min }$ , and the RSS value range measured by every receiver as $v^{\Delta }=v_{\max }-v_{\min }$ . Then the centroid for RWL or the NOI position is calculated by

$$\begin{array}{cc}& p=\frac{{\sum }_{i=\mathrm{1}}^N\left(v_i-{\upsilon }_{\min }\right)p_i}{{\sum }_{i=\mathrm{1}}^N\left(v_i-{\upsilon }_{\min }\right)}.\end{array}$$

(4)

3.1.3. Relative Exponential Weighted Localization (REWL)

REWL scheme is a variant of the WCL scheme where the weight increases exponentially with the power of RSS [24]. In this way, the effect of the closest nodes is further accentuated in the computed centroid. Consider factor λ as a positive real value between 0 and 1; then the weights of each receiver are computed as

$$\begin{array}{cc}& w_i={(\mathrm{1}-\lambda )}^{(v_{\max }-{\upsilon }_i)}.\end{array}$$

(5)

The exponent takes positive real values; therefore, weights $w_i$ take only real values in the interval $[\mathrm{0,1}]$ . The centroid is calculated by

$$\begin{array}{cc}& p=\frac{{\sum }_{i=\mathrm{1}}^N{\left(\mathrm{1}-\lambda \right)}^{(v_{\max }-{\upsilon }_i)}{p}_i}{{\sum }_{i=\mathrm{1}}^N{\left(\mathrm{1}-\lambda \right)}^{(v_{\max }-{\upsilon }_i)}}.\end{array}$$

(6)

Figure 1 shows the behavior of the weights described in the algorithms for RWL and REWL for three different values of the weighting factor λ. One can see that receiver weight is increased as power received (RSS) improves when the value of λ increases. The weight changes significantly when RSS is above −80 dBm for λ above 0.2.

Figure 1

Example of relative span weights.

3.1.4. Centroid Algorithm with Fuzzy Logic

This is another variant of the REWL scheme where fuzzy logic system (FLS) is used to assign weights to a given set of anchor nodes. This mechanism consists of a fuzzifier, the inference mechanism, and the defuzzifier. The fuzzifier block is responsible for allocating the linguistic values to the input variable, for example, {low, medium, high}. The outputs of this block are membership functions, the inference mechanism is where a set of rules or conditions if-then is assigned, and the defuzzifier performs the conversion of the fuzzy set to a value.

In this method, the RSS is used as an input parameter, which takes values from the interval $\left[0,{\text{RSSI}}_{\max }\right]$ and then levels, within such interval, are described as output variables and defined as weight levels. Table 1 shows the fuzzy rules assigned to each weight level [25, 26]. It is possible in some cases that sensor nodes receive low power levels and then the weight should be low; otherwise the weight is high.

Table 1

Fuzzy logic rules for edge weight.

Rule	If RSS is as follows	Then weight is as follows
Rule $$\mathit{1}$$	Very low	Very low
Rule $$\mathit{2}$$	Low	Low
Rule $$\mathit{3}$$	Medium	Medium
Rule $$\mathit{4}$$	High	High
Rule $$\mathit{5}$$	Very high	Very high

This method of fuzzy logic was modeled for Mamdani fuzzy inference system and Sugeno fuzzy inference system; the differences between Mamdani and Sugeno output membership functions are either constant or linear [27–29].

Mamdani Fuzzy Inference System. In this method, the fuzzy logic system was modeled with Mamdani fuzzy inference [27, 28], the input parameter (RSS) was broken down into five trapezoidal membership functions, named {VL, L, M, H and VH}, (see Figures 2 and 3) and output parameter (weight) was decomposed into five triangular membership functions, named {VL, L, M, H and VH}.

Figure 2

Fuzzy membership function of RSS.

Figure 3

Fuzzy membership function of weight.

Sugeno Fuzzy Inference System. In this method, the fuzzy logic system was modeled with Sugeno fuzzy inference [29, 30]. The input parameter RSS was decomposed into five trapezoidal membership functions, named {VL, L, M, H and VH}, and the output parameter weight was decomposed into five linear membership functions. Figure 4 shows the decompositions for input parameter RSS.

Figure 4

Fuzzy Membership function of RSS.

Finally, to estimate location of NOI, the WCL scheme is used. Then location of the position of the NOI is calculated using expression (3).

Combined Mamdani-Sugeno Fuzzy Inference System. For this approach, the location estimate of a NOI is performed by combining Mamdani [27] and Sugeno [29] schemes; then the location of the NOI is calculated as follows:

$$\begin{array}{cc}& p=\frac{(x_{\text{mam}}+x_{\text{sug}},y_{\text{mam}}+y_{\text{sug}})}{\mathrm{2}},\end{array}$$

(7)

where $(x_{\text{mam}},y_{\text{mam}})$ are the estimated coordinates for Mamdani fuzzy inference system and $(x_{\text{sug}},y_{\text{sug}})$ are the estimated coordinates for Sugeno fuzzy inference system.

3.1.5. K-Nearest Neighbor

This method is divided into two stages: offline stage and online stage [31]. In the offline stage, RSS from m nodes is measured by fixed anchor nodes in order to create a map or fingerprint of the area. During the online stage the fingerprints are used and compared against the measured RSS values from the NOI. Then, those K fingerprints that are closest to the measured RSS values are used in an algorithm. Let ${\text{RSS}}_{ij}$   be the measured value of the fingerprint j to anchor reference i, where $j=[\mathrm{1,2},\dots ,m]$ , and m the number of fingerprints. Also, let ${\text{RSS}}_{Ti}$ be the measured RSS value of the NOI to reference i. Then, find the Euclidean distance between the RSS values as

$$\begin{array}{cc}& d_j=\sqrt{{\displaystyle \sum }_{i=\mathrm{0}}^m{\left({\text{RSS}}_{Ti}-{\text{RSS}}_{ij}\right)}^{\mathrm{2}}}.\end{array}$$

(8)

With distances $d_i$ in (8), choose those K nodes with the smallest values of distances. Then the estimated position is calculated using the coordinates of the K nearest neighbors, by the centroid

$$\begin{array}{cc}& p=\frac{\mathrm{1}}{K}{\displaystyle \sum }_{k=\mathrm{1}}^K\left(x_k,y_k\right),\end{array}$$

(9)

where $\left(x_k,y_k\right)$ are the coordinates of each of the K nodes.

3.1.6. K-Nearest Neighbor with Fuzzy Logic

This approach uses the Euclidean distance to determine the K nearest neighbors, used as input parameter in order to calculate weights through fuzzy systems.

Fuzzy Inference System (FIS). In this method, Sugeno type inference is preferred to Mamdani-type inference [31]; five constants are proposed to be used as the output membership function with values {0, 0.25, 0.5, 0.75, 1}, which have linguistic values {very small, small, medium, large, and very large}. Figures 5 and 6 show such decompositions.

Figure 5

Input parameter.

Figure 6

Output parameter.

There are five proposed rules for this method.

• (i)

  If distance is very close then weight is very large.

• (ii)

  If distance is close then weight is large.

• (iii)

  If distance is medium then weight is medium.

• (iv)

  If distance is far then weight is small.

• (v)

  If distance is very far then weight is very small.

The weights are calculated by FIS and the coordinates of the K nearest neighbors are used to calculate the position of the NOI. The NOI coordinates are computed as

$$\begin{array}{cc}& p=\frac{{\sum }_{k=\mathrm{1}}^K\left(x_k,y_k\right)w_k}{{\sum }_{k=\mathrm{1}}^K{w}_k},\end{array}$$

(10)

where $\left(x_k,y_k\right)$ are the coordinates of the K nearest neighbor and $w_k$ is the weight assigned to each K neighbor.

3.2. Range-Based Techniques

Range-based techniques require the separation distance between the NOI and the anchor nodes. These algorithms achieve greater accuracy than the range free algorithms, but the accuracy is highly dependent on the position of the anchor nodes. In the following subsections, some range based algorithms are described such as weighted least squares (WLS) multilateration, circular and hyperbolic positioning algorithm, and the weighted hyperbolic positioning algorithm.

3.2.1. Weighted Least Squares Multilateration

In the presence of noise or inaccurate measurement, the range of the ith anchor node to the NOI is expressed as [7]

$$\begin{array}{cc}& r_i=f_i\left(x,y\right)+n_i,\end{array}$$

(11)

where $f_i\left(x,y\right)=\sqrt{{\left(x-x_i\right)}^2+{(y-y_i)}^2}$ is the Euclidian distance from the NOI to the ith anchor node. Define vector q as $\mathbf{q}={\left[\begin{array}{cc}x& y\end{array}\right]}^{\mathbf{H}}$ , where (x, y) are the NOI coordinates; then given a set of N noisy observations $\mathit{r}=\mathit{f}\left(\mathbf{q}\right)+\mathit{n}$ , the least squares (LS) optimization problem is [7, 32]

$$\begin{array}{cc}& \widehat{\mathbf{q}}=\underset{\mathbf{q}}{\arg \hspace{0.17em}\min }{\left[\mathit{r}-\mathit{f}\left(\mathbf{q}\right)\right]}^{\mathit{H}}\left[\mathit{r}-\mathit{f}\left(\mathbf{q}\right)\right].\end{array}$$

(12)

Whenever the noise covariance matrix K is known, a variant of the LS problem is called WLS problem, which is posed as follows [32]:

$$\begin{array}{cc}& \widehat{\mathbf{q}}=\underset{\mathbf{q}}{\arg \hspace{0.17em}\min }{\left[\mathit{r}-\mathit{f}\left(\mathbf{q}\right)\right]}^{\mathit{H}}{\mathbf{K}}^{-\mathbf{1}}\left[\mathit{r}-\mathit{f}\left(\mathbf{q}\right)\right].\end{array}$$

(13)

Equation (13) describes a nonlinear optimization problem; then by first-order Taylor series of the function vector $\mathbf{f}\mathbf{\left(}\mathbf{q}\mathbf{\right)}$ around the known point ${\mathbf{q}}_{\mathbf{0}}$ (which is assumed sufficiently close to the true position vector q), the nonlinear problem is solved; by linearizing it (e.g., see [7, 32]) to get the Linear LS (LLS) problem

$$\begin{array}{cc}& {\mathit{f}}_{\mathit{l}}\left(\mathbf{q}\right)=\mathit{f}\left({\mathbf{q}}_{\mathbf{0}}\right)+\mathbf{D}\left(\mathbf{q}-{\mathbf{q}}_{\mathbf{0}}\right),\end{array}$$

(14)

where

$$\begin{array}{cc}& \mathbf{D}=\left[\begin{array}{cc}{\left.\frac{\partial {\mathit{f}}_{\mathrm{1}}\left(\mathbf{q}\right)}{\partial x}\right|}_{\mathbf{q}={\mathbf{q}}_{\mathbf{0}}}& {\left.\frac{\partial {\mathit{f}}_{\mathrm{1}}\left(\mathbf{q}\right)}{\partial y}\right|}_{\mathbf{q}={\mathbf{q}}_{\mathbf{0}}}\\ ⋮& ⋮\\ {\left.\frac{\partial {\mathit{f}}_N\left(\mathbf{q}\right)}{\partial x}\right|}_{\mathbf{q}={\mathbf{q}}_{\mathbf{0}}}& {\left.\frac{\partial {\mathit{f}}_N\left(\mathbf{q}\right)}{\partial y}\right|}_{\mathbf{q}={\mathbf{q}}_{\mathbf{0}}}\end{array}\right],\\ {\left.\frac{\partial {\mathit{f}}_i\left(\mathbf{q}\right)}{\partial x}\right|}_{\mathbf{q}\mathbf{=}{\mathbf{q}}_{\mathbf{0}}}\mathbf{=}\hspace{0.17em}\frac{x_{\mathrm{0}}-x_i}{\sqrt{{\left(x_i-x_{\mathrm{0}}\right)}^{\mathrm{2}}+{\left(y_i-y_{\mathrm{0}}\right)}^{\mathrm{2}}}}\mathbf{,}\hspace{1em}i=\mathrm{1},\dots N,\\ {\left.\frac{\partial {\mathit{f}}_i\left(\mathbf{q}\right)}{\partial y}\right|}_{\mathbf{q}\mathbf{=}{\mathbf{q}}_{\mathbf{0}}}\mathbf{=}\hspace{0.17em}\frac{y_{\mathrm{0}}-y_i}{\sqrt{{\left(x_i-x_{\mathrm{0}}\right)}^{\mathrm{2}}+{\left(y_i-y_{\mathrm{0}}\right)}^{\mathrm{2}}}}\mathbf{,}\hspace{1em}i=\mathrm{1},\dots N.\end{array}$$

(15)

Redefining the observation vector r, such that ${\mathbf{r}}^{\prime }=\mathbf{r}-\mathbf{f}\left({\mathbf{q}}_{\mathbf{0}}\right)+\mathbf{D}{\mathbf{q}}_{\mathbf{0}}$ , then the WLS estimator is given by

$$\begin{array}{cc}& \widehat{\mathbf{q}}={\left({\mathbf{D}}^{\mathit{H}}{\mathbf{K}}^{-\mathbf{1}}\mathbf{D}\right)}^{-\mathit{1}}{\mathbf{D}}^{\mathit{H}}{\mathbf{K}}^{-\mathbf{1}}{\mathbf{r}}^{\prime }.\end{array}$$

(16)

By expanding vector ${\mathbf{r}}^{\prime }$ and moving terms, we obtain the WLS estimator, [32], which is rewritten as

$$\begin{array}{cc}& \widehat{\mathbf{q}}={\mathbf{q}}_{\mathit{0}}+{\left({\mathbf{D}}^{\mathit{H}}{\mathbf{K}}^{-\mathbf{1}}\mathbf{D}\right)}^{-\mathit{1}}{\mathbf{D}}^{\mathit{H}}{\mathit{K}}^{-\mathbf{1}}\left[\mathbf{r}-\mathbf{f}\left({\mathbf{q}}_{\mathbf{0}}\right)\right].\end{array}$$

(17)

This last equation finds the WLS estimator $\widehat{\mathbf{q}}$ with just one recursion, by considering $\widehat{\mathbf{q}}$ as the position ${\widehat{\mathbf{q}}}_{\mathit{0}}$ . This recursion is given by [33]

$$\begin{array}{cc}& \widehat{\mathbf{q}}\left(n+\mathbf{1}\right)=\mathbf{q}\left(n\right)+{\left({\mathbf{D}}^{\mathit{H}}{\mathbf{K}}^{-\mathbf{1}}\mathbf{D}\right)}^{-\mathit{1}}{\mathbf{D}}^{\mathit{H}}{\mathbf{K}}^{-\mathbf{1}}\left[\mathbf{r}-\mathbf{f}\left(\widehat{\mathbf{q}}\left(n\right)\right)\right].\end{array}$$

(18)

The above expression shows that the position of the NOI is iteratively computed until convergence is obtained when the term $\left[\mathbf{r}-\mathbf{f}\left(\widehat{\mathbf{q}}\left(n\right)\right)\right]$ tends to zero.

3.2.2. Circular Positioning Algorithm

This approach (see [14]) consists on finding the position of the node that minimizes the sum of squared errors in a set of n estimated distances. If $(x_i,y_i)$ is the true position of anchor node i and ${\widehat{d}}_i$ is the estimated distance to anchor node, then the mean squared error (MSE) is given by

$$\begin{array}{cc}& \epsilon ={\displaystyle \sum }_{i=\mathrm{1}}^n{\left(\sqrt{{\left(x_i-x\right)}^{\mathrm{2}}+{\left(y_i-y\right)}^{\mathrm{2}}}-{\widehat{d}}_i\right)}^{\mathrm{2}}.\end{array}$$

(19)

The position of the mobile node can be calculated iteratively with the straight gradient method

$$\begin{array}{cc}& {\left[\begin{array}{c}\widehat{x}\\ \widehat{y}\end{array}\right]}_{k+\mathrm{1}}={\left[\begin{array}{c}\widehat{x}\\ \widehat{y}\end{array}\right]}_k-\alpha {\left[\begin{array}{c}\frac{\partial \epsilon }{\partial x}\\ \frac{\partial \epsilon }{\partial y}\end{array}\right]}_{x={\widehat{x}}_k,y={\widehat{y}}_k}.\end{array}$$

(20)

This method requires an initial position, which may be the centroid of the locations of the anchor nodes.

3.2.3. Hyperbolic Positioning Algorithm

The hyperbolic positioning algorithm [14] converts the nonlinear problem into a linear problem that can be solved with a least squares estimator. The distance between a mobile node and an anchor node is expressed as

$$\begin{array}{cc}& {d_i}^{\mathrm{2}}={\left(x_i-x\right)}^{\mathrm{2}}+{\left(y_i-y\right)}^{\mathrm{2}}.\end{array}$$

(21)

Expanding (21), the resulting expression is

$$\begin{array}{cc}& \mathrm{2}x{x}_i+\mathrm{2}y{y}_i={x_i}^{\mathrm{2}}+{y_i}^{\mathrm{2}}-{d_i}^{\mathrm{2}}+{d_{\mathrm{1}}}^{\mathrm{2}}.\end{array}$$

(22)

Rewriting (22) in matrix form gives

$$\begin{array}{cc}& \left[\begin{array}{cc}\mathrm{2}{x}_{\mathrm{2}}& \mathrm{2}{y}_{\mathrm{2}}\\ ⋮& ⋮\\ \mathrm{2}{x}_n& \mathrm{2}{y}_n\end{array}\right]\left[\begin{array}{c}x\\ y\end{array}\right]=\left[\begin{array}{c}{x_{\mathrm{2}}}^{\mathrm{2}}+{y_{\mathrm{2}}}^{\mathrm{2}}-{d_{\mathrm{2}}}^{\mathrm{2}}+{d_{\mathrm{1}}}^{\mathrm{2}}\\ ⋮\\ {x_n}^{\mathrm{2}}+{y_n}^{\mathrm{2}}-{d_n}^{\mathrm{2}}+{d_{\mathrm{1}}}^{\mathrm{2}}\end{array}\right].\end{array}$$

(23)

Therefore, the problem is formulated as

$$\begin{array}{cc}& \mathbf{H}\mathbf{p}=\tilde{\mathbf{b}},\end{array}$$

(24)

where $\mathbf{H}=\left[\begin{array}{cc}\mathrm{2}{x}_{\mathrm{2}}& \mathrm{2}{y}_{\mathrm{2}}\\ ⋮& ⋮\\ \mathrm{2}{x}_n& \mathrm{2}{y}_n\end{array}\right]$ , $\mathbf{p}=\left[\begin{array}{c}x\\ y\end{array}\right]$ , and $\tilde{\mathbf{b}}$ is the vector:

$$\begin{array}{cc}& \tilde{\mathbf{b}}=\left[\begin{array}{c}{x_{\mathrm{2}}}^{\mathrm{2}}+{y_{\mathrm{2}}}^{\mathrm{2}}-{{\tilde{d}}_2}^2+{{\tilde{d}}_{\mathrm{1}}}^{\mathrm{2}}\\ ⋮\\ {x_n}^{\mathrm{2}}+{y_n}^{\mathrm{2}}-{{\tilde{d}}_n}^{\mathrm{2}}+{{\tilde{d}}_{\mathrm{1}}}^{\mathrm{2}}\end{array}\right].\end{array}$$

(25)

Therefore, position p of NOI is calculated by

$$\begin{array}{cc}& \mathbf{p}={\left({\mathbf{H}}^{\mathit{T}}\mathbf{H}\right)}^{-\mathbf{1}}{\mathbf{H}}^{\mathit{T}}\tilde{\mathbf{b}}.\end{array}$$

(26)

3.2.4. Weighted Hyperbolic Positioning Algorithm

The traditional hyperbolic positioning algorithm calculates the position of the mobile node through (26). However, this linear problem could also be solved using weighted least squares estimator, as proposed in [34]. In this case, the position of the mobile node may be estimated as

$$\begin{array}{cc}& \mathbf{p}={\left({\mathbf{H}}^{\mathit{T}}{\mathbf{S}}^{-\mathbf{1}}\mathbf{H}\right)}^{-\mathbf{1}}{\mathbf{H}}^{\mathit{T}}{\mathbf{S}}^{-\mathbf{1}}\tilde{\mathbf{b}},\end{array}$$

(27)

where S is the covariance matrix of vector $\tilde{\mathbf{b}}$ and could be expressed as

$$\begin{array}{cc}& \mathbf{S}=\left[\begin{array}{cccc}\mathrm{1}+{\left(\frac{d_{\mathrm{2}}}{d_{\mathrm{1}}}\right)}^{\mathrm{4}}& \mathrm{1}& \dots & \mathrm{1}\\ \mathrm{1}& \mathrm{1}+{\left(\frac{d_{\mathrm{3}}}{d_{\mathrm{1}}}\right)}^{\mathrm{4}}& \dots & \mathrm{1}\\ ⋮& ⋮& \ddots & ⋮\\ \mathrm{1}& \mathrm{1}& \dots & \mathrm{1}+{\left(\frac{d_n}{d_{\mathrm{1}}}\right)}^{\mathrm{4}}\end{array}\right].\end{array}$$

(28)

It can be observed that in (28) the elements of S depend on the real distance between NOI and the anchor nodes. Therefore, in order to use the estimator in (27) in a real deployment, it is necessary to approximate the real distances $d_i$ by the estimated distances ${\tilde{d}}_i$ .

4. WLS Modified Multilateration Algorithm

The proposed localization algorithm is a modified version of WLS. Consider (13) which represents the WLS optimization problem with noise covariance matrix K which influences the location error of the NOI. This matrix contains values of the variance of Gaussian random variables seen by anchor nodes ( ${\sigma }_i$ for anchor node i) that affect the accuracy of the localization of the NOI. A scenario where variances in K were equal would lead us to give the same weight to each anchor node; that is, anchor nodes would be equally likely to be close to the NOI.

Accuracy is improved by using a matrix R whose main diagonal contains the square of the estimated distances of the NOI to the anchor nodes; that is,

$$\begin{array}{cc}& \mathbf{R}=\left[\begin{array}{cccc}{r_{\mathrm{1}}}^{\mathrm{2}}& \mathrm{0}& \cdots & \mathrm{0}\\ \mathrm{0}& {r_{\mathrm{2}}}^{\mathrm{2}}& \cdots & \mathrm{0}\\ ⋮& ⋮& \ddots & \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \cdots & {r_N}^{\mathrm{2}}\end{array}\right].\end{array}$$

(29)

Matrix R only affects matrix K, balancing the effect of the variances in K; therefore, multiplying both matrices, we obtain a new matrix $\mathbf{K}\mathbf{R}$ whose main diagonal has the terms ${\left({\sigma }_i{r}_i\right)}^2$ .

This modification implies that each element of matrix $\mathbf{K}\mathbf{R}$ has a different weight, since the value of the anchor distance to NOI $r_i$ is different from each other node. Equation (13) can be expressed for the proposed algorithm as

$$\begin{array}{cc}& \widehat{\mathbf{q}}=\underset{\mathbf{q}}{\arg \hspace{0.17em}\min }{\left[\mathbf{r}-\mathbf{f}\left(\mathbf{q}\right)\right]}^{\mathit{H}}{\left(\mathbf{K}\mathbf{R}\right)}^{-\mathit{1}}\left[\mathbf{r}-\mathbf{f}\left(\mathbf{q}\right)\right].\end{array}$$

(30)

As seen in (30), matrix ${(\mathbf{K}\mathbf{R})}^{-\mathit{1}}$ has in its diagonal terms ${\left({\sigma }_i{r}_i\right)}^{-2}$ . Therefore, if $r_i$ increases, then the weight for anchor node i decreases. Following the same steps as shown in previous sections, we can get from (30) the expression

$$\begin{array}{cc}& \widehat{\mathbf{q}}={\mathit{q}}_{\mathit{0}}+{\left({\mathbf{D}}^{\mathbf{H}}{{\mathbf{R}}^{-\mathbf{1}}\mathbf{K}}^{-\mathbf{1}}\mathbf{D}\right)}^{-1}{\mathbf{D}}^{\mathit{H}}{\mathbf{R}}^{-\mathbf{1}}{\mathbf{K}}^{-\mathbf{1}}\left[\mathbf{r}-\mathbf{f}\left({\mathbf{q}}_{\mathbf{0}}\right)\right].\end{array}$$

(31)

Rearranging terms in (31) and considering that WLS multilateration algorithm is iterative lead to

$$\begin{array}{ll}& \widehat{\mathbf{q}}\left(n+\mathit{1}\right)\\ \hspace{1em}=\widehat{\mathbf{q}}\left(n\right)+{\left({\mathbf{D}}^{\mathbf{H}}{\left(\mathbf{K}\mathbf{R}\right)}^{-\mathit{1}}\mathbf{D}\right)}^{-\mathit{1}}{\mathbf{D}}^{\mathit{H}}{\left(\mathbf{K}\mathbf{R}\right)}^{-\mathit{1}}\left[\mathbf{r}-\mathbf{f}\left(\widehat{\mathbf{q}}\left(n\right)\right)\right].\end{array}$$

(32)

The main objective is to know the impact of matrix $\mathbf{K}\mathbf{R}$ on the algorithm.

5. Performance Evaluation

In this section, the localization algorithms introduced in previous sections are evaluated using three metrics: accuracy measured by mean squared error (MSE), precision in terms of standard deviation (SD), and computational complexity.

First Stage of Evaluation. The analyzed localization techniques were evaluated in a scenario with a square area of 1000 m × 1000 m. A total of M = 10,000 different realizations of node distributions were evaluated. For each scenario, a random node was chosen to represent the node to locate (NOI). Nodes were generated randomly in scenarios from 100 up to 900 nodes in the deployment area. For each realization, standard deviation σ of the RSS is varied from 4 up to 12 dB. A value of RSS is calculated for every anchor or reference node, using the log-normal shadowing propagation model, [10], given by (1), with $n=4$ and $A\left(\text{dB}\right)=-30\hspace{0.17em}$ dB. RSS was calculated considering a node with a transmission range of 100 m, a sensitivity of −92 dBm and a transmission power of 1 mW (0 dBm). Variable d is the distance to be estimated between the NOI and an anchor node. Anchor nodes are also chosen from the randomly distributed nodes surrounding the NOI. In order to have uncorrelated noise in different anchor nodes, the separation distance between any pair of anchor nodes is required to be at least 20 m. When this is not true the realization is discarded and a new one is generated. See that the 20 m requirement is not for the separation distance of the NOI and anchor nodes which could be close to the NOI as Figure 7 shows in an example of the node distribution. Centroid algorithms CL, WCL, RWL, REWL, WLS multilateration, and centroid with FIS were evaluated in scenarios as that shown.

Figure 7

Distribution of nodes in 1000 m × 1000 m area.

5.1. Performance Metrics

Accuracy. This metric is the mean squared error (MSE) of the estimated position and the true position of the NOI throughout all the realizations; that is, if (x, y) is the real position of the NOI and $\left(x_k,y_k\right)$ is the estimated position in realization $k=\mathrm{1,2},\dots ,M$ , this metric is given by

$$\begin{array}{cc}& \text{MSE}=\frac{\mathrm{1}}{M}{\displaystyle \sum }_{k=\mathrm{1}}^M{\left(x-x_k\right)}^{\mathrm{2}}+{\left(y-y_k\right)}^{\mathrm{2}}.\end{array}$$

(33)

Precision. This metric considers the distance error distribution, while the accuracy considers the average value of those errors. When two techniques are compared, a technique with concentrated distance errors on small values is preferred.

Computational Complexity. It refers to the number of mathematical operations performed by an algorithm during its execution.

Figures 8 and 9 show the rms error obtained for each location algorithm for 100 and 500 nodes in the network, respectively. As for rms error, WLS multilateration algorithm has the best performance for small noise levels. In general, it can be seen that the algorithms improve as node density increases.

Figure 8

rms error versus (σ Noise) for 100 nodes.

Figure 9

rms error versus (σ Noise) for 500 nodes.

Figure 10 shows how the rms error decreases for each location algorithm, as node density increases in the network. WLS multilateration scheme shows best performance for the scenario with low noise (4 dB). Figure 11 shows the comparison to the algorithms based on fuzzy systems, where we observe that our proposed method (WLS multilateration) has the best performance; we also note that Sugeno FIS performs better than Mamdani FIS.

Figure 10

rms error as node density changes for $\sigma =4$  dB.

Figure 11

rms error as node density changes for $\sigma =4$  dB.

In Figure 12, we show the comparison of the method proposed and those range-based algorithms. The scenario shows that as node density increases, rms error is reduced, but our method proposed has better performance even when noise has levels of 8 dB.

Figure 12

rms error as node density changes for $\sigma =8$  dB.

In order to present in detail the precision of each localization algorithm for a certain node density and noise level, we use the cumulative distribution function (CDF).

Figures 13 and 14 show the curves of the CDF for analyzed location algorithms with noise levels of $\sigma =4\hspace{0.17em}$ dB for a 100 node network. Figure 13 shows that the CL algorithm presents the less precision, while the WLS Multilateration scheme presents the best precision. For lower noise values, a significant change is observed in the WLS multilateration scheme. In comparison, Figure 14 shows the CDF of the fuzzy algorithms and once again the method proposed WLS has the best precision. Meanwhile, Figures 15 and 16 show that the precision of WLS multilateration scheme degrades when noise increases.

Figure 13

CDF of rms error σ = 4 dB 100 nodes.

Figure 14

CDF of rms error σ = 4 dB 100 nodes.

Figure 15

CDF of rms error σ = 8 dB 100 nodes.

Figure 16

CDF of rms error σ = 8 dB 100 nodes.

Figures 17 and 18 show the rms error using different values of noise level for a 100 and a 500 node network, respectively. In Figure 17 it is observed that the performance of the circular positioning algorithm is closed to that of the proposed algorithm, improving performance for high noise levels, that is, beyond 10 dB. When density increases to the 500 node network, we can see that the circular positioning algorithm has practically the same performance as that of the WLS method proposed.

Figure 17

rms error for a 100-node network.

Figure 18

rms error for a 500-node network.

These figures show that for low noise levels all algorithms have similar rms error behavior, but when noise level is higher, the performance of the WLS multilateration scheme is better. The improvement of the circular positioning algorithm is due to its use of the estimation performed by the weighted hyperbolic algorithm as the initial position. Figure 18 shows the weighted hyperbolic algorithm greatly improving the rms error.

Second Stage of Evaluation. Figure 19 shows the proposed second stage, in which the location algorithms of centroid, fuzzy centroid, WLS multilateration, and nearest neighbor were evaluated. 10,000 tests are performed for each location algorithm. Every test generates a random NOI node.

Figure 19

Evaluation stage in a 10 × 10 m area.

The received signal strength was calculated by log-normal shadowing model [27], where $n=4$ (loss-exponent in free space) and $P_o\left(\text{dB}\right)=-40\hspace{0.17em}\text{dBm}$ at a distance of 1 m, which was calculated considering a transceiver with a transmission range of 20 m indoors, a sensitivity of $-92\hspace{0.17em}\text{dBm}$ and a transmission power of 1 mW (0 dBm).

Figure 20 shows the performance in terms of the rms error for the location algorithms when implemented in the network of Figure 19. For lower noise levels of up to $\sigma =2\hspace{0.17em}$ dB, WLS multilateration scheme has better performance than all presented algorithms. Making a general comparison of the analyzed algorithms, REWL algorithm $(\lambda =0.1)$ has lower rms error for noise levels above $\sigma =3\hspace{0.17em}$ dB compared to the other algorithms. Thus for low noise levels, WLS multilateration has the best performance and for higher noise levels REWL $(\lambda =0.1)$ has the best performance. Figure 21 shows performance comparison to the fuzzy algorithms where REWL $(\lambda =0.1)$ is the best algorithm.

Figure 20

rms error for 100 node network.

Figure 21

rms error for 100 node network.

Analysis of the Computational Complexity. The evaluation of the computational complexity of the location algorithms range-based and range-free is very important, as this performance metric determines the computational cost of the algorithm or the amount of computer resources used by the algorithm to solve a problem. The computational complexity of the localization algorithms presented in this paper was evaluated through the number of elementary operations performed by the algorithm during its execution. Figure 22 shows the number of operations per second of range-based algorithms. In this Figure, it can be seen that the WLS multilateration scheme is computationally more complex, thus resulting in the hyperbolic algorithm with lower computational complexity.

Figure 22

Processing time versus node density for range-based algorithms.

Figure 23 shows the number of operations per second of range-free algorithms. In this figure, it is observed that REWL algorithm is computationally more complex, and thus resulting in the CL algorithm with the lower computational complexity.

Figure 23

Processing time versus node density for range-free algorithms.

Comparing Figures 22 and 23, it is shown that range-based algorithms are computationally more expensive than the range-free algorithms.

Analysis of the WLS Multilateration and WLS Modified Multilateration Algorithms. The first evaluation scenario uses the same signal propagation model. In this section we show the results of performance of the proposed algorithm WLS modified and that of WLS multilateration.

Figure 24 shows that the WLS multilateration algorithm performed better MSE and SD for low noise levels; however, the modified algorithm has improved performance for high values of the noise random variable. The performance of this algorithm is not significant in this scheme, as the node density is low, which affects the WLS multilateration algorithm proposed.

Figure 24

rms error for 100 node network.

Finally, Figure 25 shows the rms error for WLS and the proposed WLS modified algorithm. It can be seen that the WLS multilateration proposed algorithm with the modification exceeds with a wide difference the WLS multilateration algorithm in performance. This is because the node density is high hence improving accuracy of the algorithm. Therefore, a higher density of nodes improves performance of the proposed algorithm.

Figure 25

rms error for 500 node network.

Results Discussion. Table 2 summarizes the performance of each location algorithm, using performance metrics of rms error, precision, complexity, and node density, in terms of quality indicators of performance as follows: very bad, bad, fair, good, and very good.

Table 2

Quality performance metrics.

Algorithm/metric	rms error	Precision	Complexity	Node density
CL	Fair	Fair	Very good	>10
WCL	Good	Good	Very good	>9
RWL	Fair	Fair	Good	>9
REWL	Good	Good	Good	>9
Mamdani FIS	Fair	Fair	Fair	>5
Sugeno FIS	Good	Good	Fair	>9
Hyperbolic	Good	Good	Bad	>9
Weighted hyperbolic	very good	Very good	Bad	>9
Circular	Very good	Very good	Very bad	>5
WLS	Very good	Very good	Very bad	>5

Table 2 shows that range-based algorithms have better precision and rms error that range-free algorithms, but they are more complex. It is observed that the complexity of these algorithms is bad for the positioning algorithms weighted hyperbolic and hyperbolic and very bad for the circular positioning algorithm and WLS multilateration. Comparing the Centroid algorithms, WCL algorithm is better because it is less complex than the REWL algorithm. Sugeno FIS is more efficient than Mamdani FIS, because the range-free algorithms exhibit more robustness for the 900 node scenario. The circular positioning algorithm and WLS multilateration exhibit robustness for node densities 500 nodes.

Table 3 shows the number of operations required by each of the algorithms analyzed. It can clearly be seen that range-based algorithms require a larger number of operations than their range-free counterparts. The results also show that range-based algorithms have polynomial complexity because the multiplication and matrix inversion needed in those algorithms have complexity $O\left(n^3\right)$ . In a sensor network, a regular node requires considerable processing time for range-based location algorithms; instead, it is recommended to have the information processed in a data fusion center or a central computer to which sensor nodes would send it since nodes would be of low power consumption and need to be energy efficient. Besides, the efficiency of these algorithms can be improved employing parallelization techniques for matrix operations. Range-free algorithms would be a better implementation choice for WSNs.

Table 3

Number of operations.

Number of nodes/algorithm	5	11	17	25
CL	27	57	87	127
WCL	37	79	121	177
RWL	51	105	159	231
REWL	365	899	1433	2145
Hyperbolic	184	418	652	964
Weighted hyperbolic	500	4796	18020	58500
Circular	4613	13589	31843	80593
WLS	6287	20057	46561	111687

6. Conclusions

Given a WSN, the information of RSS and neighboring nodes can be used to estimate the position of an unknown node. By analyzing the algorithms evaluated, range-free algorithms are computationally more efficient than range-based schemes, because it requires more processing time. This paper shows that the centroid algorithm based on Sugeno FIS is computationally more efficient than Mamdani FIS, even in terms of precision and accuracy. It also demonstrates that WCL and REWL are the most efficient centroid algorithms. We introduced a modification to the WLS algorithm by assigning weights to the correlation matrix and showed that it improves accuracy. Range-based algorithms offer better precision than the range-free algorithms, but these schemes require more processing time and also are highly dependent on the position of the anchor nodes, so the coverage is a factor important for range-based algorithms. Therefore, range-free algorithms are more robust than range-based algorithms.