A Two-Stage Range-Free Localization Method for Wireless Sensor Networks

Abstract

Range-free localization plays an important role in low-cost and large scale wireless sensor networks. Many existing range-free localization methods encounter high localization error, especially for the network with a coverage hole. One reason for high localization error is unreasonable distance estimation method. Another reason is that unknown nodes use the shortest distance which has large cumulative distance error to estimate their positions. In this paper, a two-stage centralized range-free localization algorithm (TCRL) is proposed. In the first stage, we design a novel rational distance estimation method to alleviate the distance estimation error between neighbor nodes based on the connectivity information and geometric features. In the second stage, a novel neighborhood function is derived from the estimated distances between neighbor nodes. Then a new localization strategy is proposed based on greedy idea. Finally, the proposed algorithm is compared with the same type algorithms in two network scenarios, namely, random deployment and random deployment with a coverage hole. The simulation results show that TCRL achieves more accurate and reliable results than most of existing range-free methods in the two network scenarios.

1. Introduction

A wireless sensor network (WSN) is composed of many battery-powered, low-cost sensor nodes deployed for generating specific event reports [1]. In many envisioned and existent applications, such as environmental monitoring, precision agriculture, and vehicle tracking, accurate location of sensor nodes is an indispensable requirement [2–4]. In addition, most routing algorithms of WSNs also require position information [5]. However, WSNs are often designed to operate in inaccessible regions and sensor nodes are deployed randomly, so the positions of sensor nodes are always uncontrollable. Although location awareness can be enabled in principle by the use of a global positioning system (GPS) or manual configuration, they are not suitable for the low-cost and large scale WSNs [6]. Sensor node localization has become an important area which attracts significant research interest.

A number of localization algorithms have been proposed recently for WSNs, which are generally classified into range-based and range-free localization schemes [7, 8]. For the range-based localization, all neighbor nodes must be able to measure the distances or angles between neighbor nodes using some measurement technique such as Time of Arrival (TOA) [9], Time Difference of Arrival (TDOA) [10], Received Signal Strength Arrival (RSSI) [11], and Angle of Arrival (AOA) [12]. The range-free localization only uses the connectivity information between neighbor nodes. In theory, the range-based methods can achieve more accurate estimated positions than the range-free methods. However, range-based methods always need some additional measuring devices. Although RSSI algorithm needs no extra hardware, the RSSI measurement is subject to negative effects of radio interference, obstacles, and individual differences of transmitters and receivers. So the range-based localization methods are not suitable for some low-cost and large scale WSNs.

In this paper, we focus on the range-free localization algorithms. Existing range-free algorithms encounter high localization error for WSNs, especially the network with a coverage hole. We explore most of existing range-free algorithms and find two reasons which lead to high localization error. One reason is that the distance estimation method is not good enough. This causes the distance estimation error which also contributes to the high localization error. Another reason is the unreasonable localization strategy. They always use the shortest distance between unknown nodes and anchor nodes to calculate the estimated positions by the trilateration or other methods [13]. Because the shortest distance path between an unknown node and an anchor node is often a zigzag one especially in the network with a coverage hole, compared with the direct line segment, it leads to high cumulative distance error and high localization error.

This paper studies how to alleviate the two problems mentioned above in existing range-free algorithms and then proposes a novel two-stage centralized range-free localization algorithm, called TCRL algorithm. Centralized localization algorithms mean nodes transmit data to a central site where the calculation is performed. Generally speaking, the centralized localization algorithms can get more positioning accuracy than the distributed algorithms because the central site can perform more complicated calculation. In the first stage, we analyze the geometric relationship between distance and intersection area of neighbor nodes and design a method to estimate more accurate distance between neighbor nodes only using the connectivity information and geometric features. In the second stage, we make a deep analysis on the estimated distance of neighbor nodes between two successive localization results and design a neighborhood function. Then a new localization strategy based on greedy idea is proposed. The localization strategy uses the neighborhood function and the estimated distance generated by the first stage between neighbor nodes to estimate the positions of unknown nodes. Because the localization strategy only uses the distance between neighbor nodes instead of the shortest distance, it can significantly reduce the cumulative distance error and localization errors. What is more, TCRL only uses connectivity information and introduces no extra hardware to measure distances between neighbor nodes, and it also does not need that sensor nodes are uniform deployed and the communication range is regular.

The rest of this paper is organized as follows: Section 2 summarizes related work. Section 3 describes TCRL algorithm including network model, distance estimation method, neighborhood function, and localization strategy. Section 4 tests the impact of various factors on TCRL and compares TCRL with the latest same type of algorithms to verify advantage and practicality of TCRL algorithm. Finally, we summarize this paper in Section 5.

2. Related Work

In range-free localization algorithms, nodes have no ability to measure distance or angle relative to their neighbor nodes. The range-free algorithm can be further divided into two categories: local techniques and hop-counting techniques.

In the local techniques, unknown nodes use the positions of anchor nodes to estimate their own positions. The paper [14] proposes the centroid algorithm. An unknown node estimates its position as the centroid of coordinates of its neighbor anchor nodes. A density-adaptive algorithm can reduce the localization error of the centroid algorithm if the anchor nodes are well deployed in paper [15]. The paper [16] proposes APIT algorithm. APIT divides the region into some small triangular regions between anchor nodes. Each unknown node estimates its position based on the center of gravity of the intersection of all the triangles that the unknown node resides in. The local range-free techniques always need a lot of anchor nodes and localization error is large.

The hop-counting techniques usually use some methods to estimate the distance between nodes. The paper [17] proposes DV-Hop algorithm. An unknown node can estimate its position by trilateration algorithm if it estimates its distances to three and more than three anchor nodes. DV-Hop algorithm suffers from the hop-distance ambiguity problem. Those nodes with the same hop count to an anchor node will have the same estimated distance, although they do have different distances to an anchor. The reason is that the value of hops between neighbor nodes is 1 independent of the distance between neighbor nodes. To resolve this problem, some improved DV-HOP algorithms are proposed. The paper [18] uses RSSI to differentiate nodes from the same hop-count. The paper [19] uses neighbor information of nodes. The paper [20] uses combination of RSSI and neighbor information. The paper [21] uses RSSI of a node to sort its 1-hop neighbor nodes by decreasing order to obtain a high-dimensional signature. They can achieve better result than DV-HOP, but they implicitly assume that all nodes are uniformly distributed in the deployed region or use RSSI. However, in practice, large-scale deployment of nodes with a random manner hardly guarantees such a global uniform distribution and the variability of RSSI in practical environment makes distance estimators hard to determine the models’ parameters. The paper [22] proposed a new proximity measure, named RND, to represent the distance between neighbor nodes and designed DV-RND. DV-RND uses RND to replace the hop between neighbor nodes and can get better localization accuracy than other peer classical range-free algorithms. However, DV-RND assumes that four anchor nodes are deployed at four locations close to the four corners of the field and the localization results are still not good enough, especially for the network with a coverage hole. The paper [23] proposes CMDS algorithm to improve the localization accuracy for the network with a coverage hole, but it requires that nodes can measure distance using RSSI which is always affected by appearance of sensor nodes and characteristics of the surrounding terrain.

3. TCRL Algorithm

TCRL consists of two stages. In the first stage, a novel distance estimation method is proposed to generate accurate estimated distance between neighbor nodes. In the second stage, a novel localization strategy, just using the estimated distance between neighbor nodes, is designed. In this section, we introduce network model and describe TCRL in detail.

3.1. Network Model

In this paper, we just consider the static WSNs. In order to make the algorithm more practical, all nodes including unknown nodes and anchor nodes are randomly deployed in a 2-dimensional region. In addition, all nodes can only get connectivity information between neighbor nodes and do not need any additional hardware to measure RSSI or other pieces of information. Moreover, we make some assumptions which are not uncommon in many range-free localization schemes as follows: all nodes have the same communication radius, denoted by r. All communication links between neighbor nodes are symmetric. Each node can get information of all its neighbor nodes. All sensor nodes are connected; that is to say at least one routing path exists between any pair of nodes.

Note that two nodes are neighbor nodes if and only if $d_{ij}\le r$ , where $d_{ij}$ is the Euclidean distance between two nodes. We use $M_i=\{j\hspace{0.17em}|\hspace{0.17em}j\ne i\hspace{0.17em}\hspace{0.17em}\text{and}\hspace{0.17em}\hspace{0.17em}{d}_{ij}\le r\}$ to denote the set of neighbor nodes of node i. The network consists of n nodes, and there are m anchor nodes and $n\text{-}m$ unknown nodes among them. Anchor nodes are aware of their coordinates. We use A to denote anchor nodes and U to denote unknown nodes.

3.2. The First Stage of TCRL

Distance estimation is of great importance for accurate localization. In the first stage, we design a novel distance estimation method only using connectivity information and geometric features between neighbor nodes. Figure 1 shows the distance model between two neighbor nodes i and j.

Figure 1

The distance model between neighbor nodes.

In Figure 1, the black solid points are other neighbor nodes of nodes i and j. We can observe that the distance $d_{ij}$ between node i and its neighbor node j determines the size of the intersection area denoted by $S_{ij}$ , and $S_{ij}$ is inversely proportional to $d_{ij}$ . $S_{ij}$ can be calculated as follows:

$$\begin{array}{cc}& S_{ij}=\mathrm{2}{r}^{\mathrm{2}}\text{arccos}\left(\frac{d_{ij}}{\mathrm{2}r}\right)-d_{ij}\sqrt{r^{\mathrm{2}}-\frac{d_{ij}^{\mathrm{2}}}{\mathrm{4}}}.\end{array}$$

(1)

The ratio of $S_{ij}$ and the communication area S of node i can be calculated by

$$\begin{array}{cc}& \frac{S_{ij}}{S}=\frac{S_{ij}}{\pi r^{\mathrm{2}}}=\frac{\mathrm{2}}{\pi }\text{arccos}\left(\frac{d_{ij}}{\mathrm{2}r}\right)-\frac{d_{ij}}{\pi r}\sqrt{\mathrm{1}-{\left(\frac{d_{ij}}{\mathrm{2}r}\right)}^{\mathrm{2}}}.\end{array}$$

(2)

Equation (2) can also be written as

$$\begin{array}{cc}& y=\frac{S_{ij}}{\pi r^{\mathrm{2}}},\hspace{1em}\hspace{1em}x=\frac{d_{ij}}{\mathrm{2}r},\\ y=\frac{\mathrm{2}}{\pi }\text{arccos}\left(x\right)-\frac{\mathrm{2}}{\pi }x\sqrt{\mathrm{1}-x^{\mathrm{2}}}.\end{array}$$

(3)

Using Taylor series expansion, $\text{arccos}\left(x\right)$ and $x\sqrt{\mathrm{1}-x^{\mathrm{2}}}$ can be written as

$$\begin{array}{cc}& \text{arccos}\left(x\right)=\frac{\pi }{\mathrm{2}}-x-\frac{\mathrm{1}}{\mathrm{6}}{x}^{\mathrm{3}}-\frac{\mathrm{3}}{\mathrm{40}}{x}^{\mathrm{5}}-\cdots ,\\ x\sqrt{\mathrm{1}-x^{\mathrm{2}}}=x-\frac{x^{\mathrm{3}}}{\mathrm{2}}-\frac{\mathrm{1}}{\mathrm{8}}{x}^{\mathrm{5}}-\cdots .\end{array}$$

(4)

According to (3) and (4), (2) can be written as

$$\begin{array}{cc}& \frac{S_{ij}}{\pi r^{\mathrm{2}}}=\mathrm{1}-\frac{\mathrm{2}}{\pi }\left(\frac{d_{ij}}{r}\right)+\frac{\mathrm{1}}{\mathrm{12}\pi }{\left(\frac{d_{ij}}{r}\right)}^{\mathrm{3}}+\frac{\mathrm{1}}{\mathrm{320}\pi }{\left(\frac{d_{ij}}{r}\right)}^{\mathrm{5}}+\cdots .\end{array}$$

(5)

Because $d_{ij}$ is the distance between neighbor nodes, the value range of $d_{ij}/r$ must be $0\le d_{ij}/r\le 1$ . From (5), we can observe that $S_{ij}/\pi r^2$ is mainly determined by $2(d_{ij}/r)/\pi$ , so it is approximate linear function relationship between $S_{ij}/\pi r^2$ and $d_{ij}/r$ . When $d_{ij}/r$ is denoted by p, Figure 2 gives the corresponding value of $S_{ij}/\pi r^2$ denoted by q in (2).

Figure 2

The value of q corresponds to the value of p.

Figure 2 also verifies that it is an approximate linear relationship between $S_{ij}/\pi r^2$ and $d_{ij}/r$ . In (2), when $d_{ij}/r$ is 0, $S_{ij}/\pi r^2$ is 1. When $d_{ij}/r$ is 1, $S_{ij}/\pi r^2$ is 0.391. We can get a linear function as follows:

$$\begin{array}{cc}& \frac{d_{ij}}{r}=\frac{\mathrm{1}}{\mathrm{0.609}}\left(\mathrm{1}-\frac{S_{ij}}{\pi r^{\mathrm{2}}}\right).\end{array}$$

(6)

The value of $S_{ij}$ is unknown; however, the density of sensor nodes is high for range-free wireless sensor networks and Figure 1 shows the area is direct ratio to the number of nodes, so $S_{ij}$ can be estimated by

$$\begin{array}{cc}& S_{ij}\approx \sigma ·\frac{N_{ij}}{N_i}·\pi r^{\mathrm{2}},\end{array}$$

(7)

where $N_{ij}=|M_i\cap M_j|+2$ is the number of nodes within the intersection area $S_{ij}$ and $N_i=\left|M_i\right|+1$ is the number of nodes within the communication range of node i. σ is a correction parameter to make (7) more accurate and the concrete value will be given in the following test. In practice, $N_{ij}$ and $N_i$ can be easily obtained by exchanging the neighbor information between nodes i and j. Finally, we can get an important equation from (6) and (7):

$$\begin{array}{cc}& {\text{NDR}}_{ij}=\frac{d_{ij}}{r}=\frac{\mathrm{1}}{\mathrm{0.609}}\left(\mathrm{1}-\sigma ·\frac{N_{ij}}{N_i}\right),\end{array}$$

(8)

where ${\text{NDR}}_{ij}$ is used to denote the neighbor distance relationship from node i to its neighbor node j. However, because all nodes are randomly deployed, it is not uncommon that $N_i\ne N_j$ . That is to say it is not uncommon that ${\text{NDR}}_{ij}\ne {\text{NDR}}_{ji}$ . Since the bigger the $N_i$ is, the more accurate the estimated $S_{ij}$ in (7) is, we use the equation as follows to estimate $\text{NDR}$ between neighbor nodes i and j in this paper:

$$\begin{array}{cc}& {\text{NDR}}_{ij}={\text{NDR}}_{ji}=\frac{d_{ij}}{r}=\frac{\mathrm{1}}{\mathrm{0.609}}\left(\mathrm{1}-\sigma ·\frac{N_{ij}}{\max \left(N_i,N_j\right)}\right),\end{array}$$

(9)

where the function $\max (N_i,N_j)$ is used to take the maximum of $N_i$ and $N_j$ . From the (9) we can estimate the distance between neighbor nodes $d_{ij}$ as follows:

$$\begin{array}{cc}& {\tilde{d}}_{ij}=r·{\text{NDR}}_{ij}.\end{array}$$

(10)

However, because ${\text{NDR}}_{ij}$ is an estimated value and not accurate enough, the estimated distance is also not accurate. Hence, after we get the $\text{ND}{\text{R}}_{ij}$ between neighbor nodes, we can use the Floyd-Warshall shortest path algorithm to calculate the shortest NDR-path which is the one with the minimum value of all NDR-path between two anchor nodes. Then we can compute a NDR correction factor ${\lambda }_{\text{NDR}}$ as follows:

$$\begin{array}{cc}& {\lambda }_{\text{NDR}}=\frac{{\sum }_{k=\mathrm{1}}^m{\sum }_{s=\mathrm{1}}^m{d}_{ks}}{{\sum }_{k=\mathrm{1}}^m{\sum }_{s=\mathrm{1}}^m\text{minND}{\text{R}}_{ks}},\end{array}$$

(11)

where $d_{ks}$ is the Euclidean distance between anchor nodes k and s. $\text{minND}{\text{R}}_{ks}$ is the value of the shortest NDR-path between anchor nodes k and s. m is the number of anchor nodes. Finally, we can estimate the distance between two neighbor nodes as follows:

$$\begin{array}{cc}& {\tilde{d}}_{ij}={\tilde{d}}_{ji}={\lambda }_{\text{NDR}}*{\text{NDR}}_{ij}.\end{array}$$

(12)

3.3. The Second Stage of TCRL

From the first stage, we can get the estimated distances between neighbor nodes. The goal of localization algorithm is to estimate the positions of unknown nodes as accurate as possible. In existing range-free algorithms, the distance between neighbor nodes is obtained; an unknown node estimates the shortest-distances to more than three anchor nodes and then uses trilateration or other algorithms to estimate its position. However, the shortest path between two nodes is often zigzag, especially in a network with coverage hole as shown in Figure 3.

Figure 3

The shortest-distance path and real distance path in a concave area.

In Figure 3, i is an unknown node and j is an anchor node. The dotted line between i and j is the real distance, and the solid curve between i and j is the shortest distance path. We can see the error between the shortest distance and real distance is very large. The localization error must be large by using the shortest-distance. Considering this, we propose a novel localization strategy only using the distances between neighbor nodes instead of the shortest-distance between nodes which are not neighbor nodes.

We consider localization problem as a combinatorial optimization problem. The purpose of the proposed algorithm is to optimize the objective function $\text{CF}$ shown in

$$\begin{array}{cc}& \text{CF}={\displaystyle \sum }_{i=m+\mathrm{1}}^n\hspace{0.17em}{\displaystyle \sum }_{j\in M_i}^{}{\left({\tilde{d}}_{ij}-{\stackrel{-}{d}}_{ij}\right)}^{\mathrm{2}},\\ {\bar{d}}_{ij}=\sqrt{{\left({\bar{x}}_i-{\bar{x}}_j\right)}^{\mathrm{2}}+{\left({\bar{y}}_i-{\bar{y}}_j\right)}^{\mathrm{2}}},\end{array}$$

(13)

where $\text{CF}$ is the squared error between the estimated distances and corresponding correct distances of neighbor nodes. $M_i$ is the set of neighbor nodes of unknown node i. ${\tilde{d}}_{ij}$ is the estimated distance obtained from the first stage. In this paper, we consider the estimated distance ${\tilde{d}}_{ij}$ as the correct distance. ${\bar{d}}_{ij}$ is estimated distance calculated by the estimated positions. $({\bar{x}}_i,{\bar{y}}_i)$ and $({\bar{x}}_j,{\bar{y}}_j)$ are the estimated positions of nodes i and j. Note that if j is an anchor node, $({\bar{x}}_i,{\bar{y}}_i)=(x_j,y_j)$ . Next, we will give the design of neighborhood function.

The purpose of neighborhood function is to generate a new solution from an old one. In this paper, a solution is a set of estimated positions of unknown nodes. We know the correct distance ${\tilde{d}}_{ij}$ obtained from the first stage. We assume that the estimated positions of two neighbor unknown nodes i and j in the new solution are correct, which are denoted by $({\bar{x}}_i^{\text{new}},{\bar{y}}_i^{\text{new}})$ and $({\bar{x}}_j^{\text{new}},{\bar{y}}_j^{\text{new}})$ . They must meet the following relationship:

$$\begin{array}{l}{\left({\bar{x}}_i^{\text{new}}-{\bar{x}}_j^{\text{new}}\right)}^2+{\left({\bar{y}}_i^{\text{new}}-{\bar{y}}_j^{\text{new}}\right)}^2\hfill \\ ={\tilde{d}}_{ij}^2={\left[\frac{{\tilde{d}}_{ij}}{{\overline{do}}_{ij}}\cdot \left({\bar{x}}_i^{\text{old}}-{\bar{x}}_j^{\text{old}}\right)\right]}^2+{\left[\frac{{\tilde{d}}_{ij}}{\overline{d{o}_{ij}}}\cdot \left({\bar{y}}_i^{\text{old}}-{\bar{y}}_j^{\text{old}}\right)\right]}^2,\hfill \\ \overline{d{o}_{ij}}=\sqrt{{\left({\bar{x}}_i^{\text{old}}-{\bar{x}}_j^{\text{old}}\right)}^2+{\left({\bar{y}}_i^{\text{old}}-{\bar{y}}_j^{\text{old}}\right)}^2},\hfill \end{array}$$

(14)

where $({\bar{x}}_i^{\text{old}},{\bar{y}}_i^{\text{old}})$ and $({\bar{x}}_j^{\text{old}},{\bar{y}}_j^{\text{old}})$ denote the estimated positions of nodes i and j in the old solution. ${\overline{do}}_{ij}$ is the distance calculated by the old solution. From (14), we can obtain the relation of abscissa and ordinate as follows:

$$\begin{array}{cc}& {\bar{x}}_i^{\text{new}}-{\bar{x}}_j^{\text{new}}=\frac{{\tilde{d}}_{ij}}{{\overline{do}}_{ij}}·\left({\bar{x}}_i^{\text{old}}-{\bar{x}}_j^{\text{old}}\right),\\ {\bar{y}}_i^{\text{new}}-{\bar{y}}_j^{\text{new}}=\frac{{\tilde{d}}_{ij}}{{\overline{do}}_{ij}}·\left({\bar{y}}_i^{\text{old}}-{\bar{y}}_j^{\text{old}}\right).\end{array}$$

(15)

We can see that (15) are the sufficient condition of (14). If an unknown node i meets (15) with all its neighbor nodes including unknown nodes and anchor nodes, we consider that the estimated position of unknown node i must be the correct position because the value of $\text{CF}$ is 0 and meets the following equations:

$$\begin{array}{l}\sum _{k\in A,k\in M_i}\left({\bar{x}}_i^{\text{new}}-x_k\right)+\sum _{j\in U,j\in M_i}\left({\bar{x}}_i^{\text{new}}-{\bar{x}}_j^{\text{new}}\right)\hfill \\ =\sum _{k\in A,k\in M_i}\frac{{\tilde{d}}_{ik}}{{\overline{do}}_{ik}}\cdot \left({\bar{x}}_i^{old}-x_k\right)\hfill \\ +\sum _{j\in U,j\in M_i}\frac{{\tilde{d}}_{ij}}{\overline{d{o}_{ij}}}\cdot \left({\bar{x}}_i^{\text{old}}-{\bar{x}}_j^{\text{old}}\right),\hfill \\ \sum _{k\in A,k\in M_i}\left({\bar{y}}_i^{\text{new}}-y_k\right)+\sum _{j\in U,j\in M_i}\left({\bar{y}}_i^{\text{new}}-{\bar{y}}_j^{\text{new}}\right)\hfill \\ =\sum _{k\in A,k\in M_i}\frac{{\tilde{d}}_{ik}}{\overline{d{o}_{ik}}}\cdot \left({\bar{y}}_i^{\text{old}}-y_k\right)\hfill \\ +\sum _{j\in U,j\in M_i}\frac{{\tilde{d}}_{ij}}{\overline{d{o}_{ij}}}\cdot \left({\bar{y}}_i^{\text{old}}-{\bar{y}}_j^{\text{old}}\right),\hfill \\ \overline{d{o}_{ik}}=\sqrt{{\left({\bar{x}}_i^{\text{old}}-x_k\right)}^2+{\left({\bar{y}}_i^{\text{old}}-y_k\right)}^2}.\hfill \end{array}$$

(16)

Equations (15) are the sufficient condition of (16). That is to say, if the estimated position of node i meets (16), it may be the correct position. Of course, it may not be the correct position. However, because we use ${\tilde{d}}_{ik}/{\overline{do}}_{ik}$ and ${\tilde{d}}_{ij}/{\overline{do}}_{ij}$ to correct the coordinates of nodes i and all its neighbor nodes, $({\bar{x}}_i^{\text{new}},{\bar{y}}_i^{\text{new}})$ may be more accurate than $({\bar{x}}_i^{\text{old}},{\bar{y}}_i^{\text{old}})$ . Just because of this uncertainty, we use the objective function $\text{CF}$ to distinguish the quality of the two solutions. If all unknown nodes meet (16), we can get an important equation as follows:

$$\begin{array}{cc}& \left(N\mathrm{1}+N\mathrm{2}\right)·U^{\text{new}}-NA·A=\left(D\mathrm{1}+D\mathrm{2}\right)·U^{\text{old}}-D\mathrm{3}·A,\end{array}$$

(17)

where the matrix A is the coordinate of anchor nodes and $NA$ denotes the correct neighbor relationship between unknown nodes and anchor nodes. $n{a}_{ik}$ is 1 if an unknown node i and anchor node k are neighbor nodes, otherwise 0. $U^{\text{old}}$ and $U^{\text{new}}$ , respectively, denote the estimated coordinates matrixes of all unknown nodes of old and new solutions. The parameter matrixes $N\mathrm{1}$ , $N\mathrm{2}$ , $D\mathrm{1}$ , $D\mathrm{2}$ , and $D\mathrm{3}$ can be calculated as follows:

$$\begin{array}{cc}& N{\mathrm{1}}_{ij}=\left\{\begin{array}{cc}{\displaystyle \sum }_{j=m+\mathrm{1}}^{n}n{u}_{ij}\hfill & i=j\hfill \\ -n{u}_{ij}\hfill & i\ne j,\hfill \end{array}\right.\\ N{\mathrm{2}}_{ij}=\left\{\begin{array}{cc}{\displaystyle \sum }_{k=\mathrm{1}}^{m}n{a}_{ik}\hfill & i=j\hfill \\ \mathrm{0}\hfill & i\ne j,\hfill \end{array}\right.\\ D{\mathrm{1}}_{ij}=\left\{\begin{array}{cc}{\displaystyle \sum }_{j=m+\mathrm{1}}^{n}n{u}_{ij}·\frac{{\tilde{d}}_{ij}}{{\overline{do}}_{ij}}\hfill & i=j,\hspace{0.17em}\hspace{0.17em}{\overline{do}}_{ij}\ne \mathrm{0}\hfill \\ -n{u}_{ij}·\frac{{\tilde{d}}_{ij}}{{\overline{do}}_{ij}}\hfill & i\ne j,\hspace{0.17em}\hspace{0.17em}{\overline{do}}_{ij}\ne \mathrm{0}\hfill \\ 0\hfill & \text{otherwise},\hfill \end{array}\right.\\ D{\mathrm{2}}_{ij}=\left\{\begin{array}{cc}{\displaystyle \sum }_{k=\mathrm{1}}^{m}n{a}_{ik}·\frac{{\tilde{d}}_{ik}}{{\overline{do}}_{ik}}\hfill & i=j,\hspace{0.17em}\hspace{0.17em}{\overline{do}}_{ik}\ne \mathrm{0}\hfill \\ 0\hfill & \text{otherwise},\hfill \end{array}\right.\\ D{\mathrm{3}}_{ik}=\left\{\begin{array}{cc}n{a}_{ik}·\frac{{\tilde{d}}_{ik}}{{\overline{do}}_{ik}}\hfill & {\overline{do}}_{ik}\ne \mathrm{0}\hfill \\ 0\hfill & \text{otherwise},\hfill \end{array}\right.\end{array}$$

(18)

where $n{u}_{ij}$ is 1 if unknown nodes i and j are neighbor nodes, otherwise 0. From (17), we can get the neighborhood function as follows:

$$\begin{array}{lll}{U}^{\text{new}}\hfill & =\hfill & \text{inv}(N1+N2)\hfill \\ \hfill & \hfill & \cdot \left[(D1+D2)\cdot U^{\text{old}}+(NA-D3)\cdot A\right].\hfill \end{array}$$

(19)

Equation (19) can generate a new solution from an old one. Through the preceding descriptive analysis, the new solution is not always better than the old solution, so we use the objective function $\text{CF}$ to distinguish the quality of the two solutions. Next, we will use this neighborhood function to propose a localization strategy based on the greedy ideas.

We have introduced the objective function and the design of neighborhood function. Then, the localization strategy is proposed. Algorithm 1 is the structure of localization strategy. At the beginning, some known data is loaded. Such as the correct neighbor relationship between nodes and the estimated distances between neighbor nodes obtained from the first stage. Then, an initial solution $U^{\text{old}}$ (line 5) is generated. In the loop (lines 9–13), a local optimal solution $U^{\text{new}}$ is generated. Here, $comCF(U^{\text{old}})$ is used to calculate the value of $\text{CF}$ of an old solution. generateSolution $(U^{\text{old}})$ is used to generate a new solution by an old one based on the neighborhood function. $minDif(minDif\ge 0)$ denotes the minimum difference between two $\text{CF}$ values of old and new solutions. We use $\text{CF}$ to distinguish the quality of the two successive solutions. Because the localization strategy is based on the greedy idea, we just accept the better solution (a solution is better than another one if and only if its value of $\text{CF}$ is smaller). The value of $minDif$ cannot be small enough. $maxNum$ is the maximum iteration number.

Algorithm 1: The structure of the localization strategy of TCRL.

(1)   localization(minDif, maxNum, p)

(2)    load some known data;  finalSolution is null;

(3)     $$minCF$$ = inf;

(4)    for i = 1: p

(5)      $$U^{\text{old}}$$ = randomly generate an initial solution;

(6)      $${CF}_{\text{old}}$$ = $$comCF$$ ( $$U^{\text{old}}$$ );

(7)      $${CF}_{\text{new}}$$ = $${CF}_{\text{old}}$$ ;

(8)      $$k=\mathit{0}$$ ; $$U^{\text{new}}$$ = $$U^{\text{old}}$$ ;

(9)     While $$k==\mathit{0}\parallel$$ ( $${CF}_{\text{old}}-{CF}_{\text{new}}\ge minDif\hspace{0.17em}\&\&\hspace{0.17em}k\le maxNum$$ )

(10)     $$k=k+\mathit{1}$$ ; $${CF}_{\text{old}}$$ = $${CF}_{\text{new}}$$ ; $$U^{\text{old}}$$ = $$U^{\text{new}}$$ ;

(11)     $$U^{\text{new}}$$ = generateSolution( $$U^{\text{old}}$$ );

(12)     $${CF}_{\text{new}}$$ = comCF( $$U^{\text{new}}$$ );

(13)   end

(14)    $$U^{\text{old}}$$ = $$U^{\text{new}}$$ ;

(15)    $$U^{\text{new}}$$ = correction( $$U^{\text{old}}$$ );

(16)    $${CF}_{\text{new}}$$ = comCF( $$U^{\text{new}}$$ );

(17)   if $$minCF\ge {CF}_{\text{new}}$$

(18)     $$finalSolution=U^{\text{new}}$$ ;

(19)     $$minCF$$ = $${CF}_{\text{new}}$$ ;

(20)   end

(21)  end

In order to get more accurate estimated positions, we add a correction operation correction $(U^{\text{old}})$ in line 15. We can use the estimated positions of unknown nodes and real positions of anchor nodes to calculate the estimated neighbor relationship between all nodes. If the estimated neighbor relationship of an unknown node is the same with the correct neighbor relationship, this unknown node is positioning accuracy in most cases and elevated to an anchor node. Otherwise it will be identified as a wrong localization node and need to be localized again. correction $(U^{\text{old}})$ is an iterative process. The steps of correction $(U^{\text{old}})$ are as follows.

Step 1.

If the estimated neighbor relationship of an unknown node is correct, the unknown node is elevated to an anchor node. Find all unknown nodes that can be elevated to anchor nodes. The estimated positions of these nodes are the finally location coordinates. If there is no unknown node that can be elevated to an anchor node, go to Step 3. Otherwise, go to Step 2.

Step 2.

A new set of anchor nodes and unknown nodes is generated after Step 1. Using the loop (line 5–13) and the new set of anchor nodes, we can generate another set of estimated positions of the new set of unknown nodes. Go to Step 1.

Step 3.

Output the estimated positions of all unknown nodes.

From the description above, we can see that the localization strategy is a local search algorithm. The result is a local optimal solution. To make the result more accurate, we can perform the localization strategy for p times (line 4) with different initial solutions and choose the final solution by the lowest value of $\text{CF}$ .

4. Simulation and Results

In order to evaluate the performance of TCRL algorithm, many simulations are performed using MATLAB. We just discuss the comparison with the DV-HOP [17] and DV-RND [22] algorithms, because DV-HOP algorithm is the forerunner of range-free algorithm using hop-counting technique and DV-RND algorithm is the latest range-free algorithm.

We consider a 100 m × 100 m deployment field with 200 sensor nodes. In order to make the test more close to the real environment, all sensor nodes including the unknown nodes and anchor nodes are randomly distributed and all nodes can only get connectivity information between neighbor nodes and do not need any additional hardware to measure RSSI or other pieces of information.

We compare their performances for distance estimation and node localization in two network scenarios: random network deployment shown in Figure 4(a) and random network deployment with a coverage hole shown in Figure 4(b). The coverage hole is 20 m × 60 m. We also test various factors of WSNs and evaluate their influence on algorithms, such as the number of anchor nodes and different communication range r. We simulate 100 different network deployments to obtain relatively fair results.

Figure 4

Two random network deployments.

The test is divided into two sections. The first section is used to verify the effectiveness of distance estimation method of TCRL proposed by this paper in Section 3.2. The second is to verify the effectiveness of localization strategy of TCRL described in Section 3.3.

4.1. Comparison of Estimated Distance Error

In this section, we compare the estimated distance error of three algorithms, DV-HOP, DV-RND, and TCRL. To evaluate the performance of these algorithms, we define estimated distance error (EDE). EDE is the average absolute difference between the estimated distances and corresponding real inter-node distances:

$$\begin{array}{cc}& \text{EDE}=\frac{\mathrm{1}}{r{\sum }_{i=m+\mathrm{1}}^n\left|M_i\right|}{\displaystyle \sum }_{i=m+\mathrm{1}}^n\hspace{0.17em}{\displaystyle \sum }_{j\in M_i}\left|d_{ij}-{\tilde{d}}_{ij}\right|\times \mathrm{100}\%,\\ d_{ij}=\sqrt{{\left(x_i-x_j\right)}^{\mathrm{2}}+{\left(y_i-y_j\right)}^{\mathrm{2}}},\end{array}$$

(20)

where $\left|M_i\right|$ is the number of neighbor nodes of unknown node i; $d_{ij}$ is the real distance between neighbor nodes; ${\tilde{d}}_{ij}$ is the estimated distance generated by the distance estimation method; $(x_i,y_i)$ and $(x_j,y_j)$ , respectively, denote the true positions of nodes i and j. In order to make the test more comprehensive, we test the impact of different communication range and number of anchor nodes on the EDEs. All results are averaged over 100 different network deployments.

The impact of communication range on EDE is shown in Figure 5.

Figure 5

Impact of the communication range on EDE in two network deployments.

In Figure 5, we set the number of anchor nodes to 20. The variation of communication range is from 13 m to 25 m. If the communication range is less than 13 m, sometimes the network is not connected. Figure 5(a) is the results of network without a coverage hole and Figure 5(b) is the results of network with a coverage hole.

In fact, all range-free localization algorithms for sensor network are sensitive to connectivity. Connectivity of sensor network is related to three main factors, namely, number of nodes, node distribution, and communication range of node. As range-free localization algorithm is usually used in low-cost and random deployed large scale wireless sensor networks, number of nodes and node distribution are not key factors of connectivity. Under these circumstances, communication range has a more important effect on localization algorithm because it determines the coverage density of the network which is essential for network connectivity.

Figure 5 shows that the EDEs of DV-RND and TCRL algorithms decrease as the communication range increases in the two network deployments. Connectivity improvement has a positive impact on these two algorithms. The EDEs of DV-HOP have little change as the communication range increases because increased communication range confused node when hop count is carried out. Figure 5 also shows that the distance estimation method of TCRL is always better than DV-HOP and DV-RND in both two network deployments independent of the communication range. It is observed that TCRL always outperforms the DV-HOP and DV-RND in EDE.

We also test the impact of the correction parameter σ in (9) on the distance estimation method of TCRL algorithm. Figure 6 shows the results.

Figure 6

Impact of the correction parameter σ on EDE in two network deployments.

As mentioned above, although range-free localization algorithm is usually applied to large scale wireless sensor networks, number of nodes may not large enough and well-distributed to ensure an accurate estimation of intersection area $S_{ij}$ using (7). Considering this, we adopt σ as a correction parameter. From Figure 6, we can see that the EDEs of TCRL increase when $\sigma >1$ and the EDEs of TCRL with $\sigma =0.9$ are always smaller. This verifies the effectiveness of the correction parameter σ and we set $\sigma =0.9$ in subsequent test. Next, we test the impact of the number of anchor nodes on EDE, the results is shown in Figure 7.

Figure 7

Impact of the number of anchor nodes on EDE in two network deployments.

In Figure 7, the communication range is 25 m, and σ of TCRL is 0.9. The variation range of number is from 3 to 20. Figure 7(a) is the test results of network without a coverage hole and Figure 7(b) is the test results of network with a coverage hole. We can see that the EDEs of the three algorithms are almost invariant as the number of anchor nodes increases. It is also clearly observed that the distance estimation method of TCRL always has smaller EDEs than that of DV-HOP and DV-RND in both network deployments independent of the number of anchor nodes.

In general, no matter how much the communication range is and how many anchor nodes there are, TCRL algorithm always has smaller EDEs than DV-HOP and DV-RND in both network deployments. This test section verifies that the distance estimation method of TCRL described in Section 3.2 is always more accurate than DV-HOP and DV-RND, especially for the network with a coverage hole.

4.2. Comparison of Localization Error

In this section, we compare the localization error of four algorithms, DV-HOP, DV-RND, DV-NDR, and TCRL. Note that DV-NDR uses the estimated distances generated by the first stage of TCRL to calculate the estimated positions of unknown nodes by traditional trilateration. By comparison of DV-NDR and TCRL algorithms, we can verify the effectiveness of localization strategy of TCRL described in Section 3.3. To evaluate the performance of localization algorithms, we define localization error (LE) as follows:

$$\begin{array}{cc}& \text{LE}=\frac{\mathrm{1}}{r\left(n-m\right)}·{\displaystyle \sum }_{i=m+\mathrm{1}}^n\sqrt{{\left(x_i-{\bar{x}}_i\right)}^{\mathrm{2}}+{\left(y_i-{\bar{y}}_i\right)}^{\mathrm{2}}}\times \mathrm{100}\%.\end{array}$$

(21)

Because the localization strategy of TCRL described in Section 3.3 is a local optimization algorithm, the positioning result has direct relation to the initial solution when the neighborhood function is fixed. Before comparing the performance of the four algorithms, we first test the impact of different types of initial solution on TCRL algorithm. In this paper, we design two types of initial solution. One type, denoted by same-position, is that the initial positions of all unknown nodes are in the same random position. The other type, which is denoted by different-position, is that all the initial unknown nodes are in the different random positions. Figures 8(a) and 8(b) show the results.

Figure 8

Impact of different types of initial solution on LE of TCRL in two random network deployments.

In Figure 8, we set that the number of anchor nodes is 20, $r=25$  m, and $\sigma =0.9$ . We test 10 different initial solutions for each type of initial solution. Figure 8(a) shows the test results in random network deployment and Figure 8(b) shows the results in the network with a coverage hole. It is clearly seen that the positioning results generated by the same-position initial solution are always more accurate and stable than the different-position initial solution, especially for the network deployment with a coverage hole. So we use the initial solution generated by the same-position way in later tests. Figure 8 also shows that the different initial solutions result in different Les. In order to get more accurate positioning results, TCRL is performed p trials with p different initial solutions and generate p sets of different positioning results. Then we choose the final positioning results by the lowest value of CF. In this paper, the value of $minDif$ is 0.001; $maxNum$ is 2000 and p is 5 in Algorithm 1. Next, we will test the impact of different communication ranges on LE. Figures 9(a) and 9(b) show the results.

Figure 9

Impact of communication range on LE in two network deployments.

In Figure 9, we set the number of anchor nodes to 20 and $\sigma =0.9$ . The variation range of communication range is from 13 m to 25 m. Figures 9(a) and 9(b) show the LEs versus different communication range. Note that DV-NDR uses the estimated distances generated by the first stage of TCRL to calculate the estimated positions of unknown nodes by traditional trilateration. We can see that the LEs of four algorithms decrease as the communication range increases. Meanwhile, the LEs of TCRL are always lower than DV-HOP, DV-RND and DV-NDR, especially in network with a coverage hole. Through the comparison of TCRL and DV-DNR, we can approve the effectiveness of localization strategy described in Section 3.3. Next, we will test the impact of the different number of anchor nodes on LE. Figures 10(a) and 10(b) show the results.

Figure 10

Impact of the number of anchor nodes on LE in two random network deployments.

In Figure 10, the communication range is 25 m and $\sigma =0.9$ . Note that the variation range of the number of anchor nodes is from 4 to 20 in Figure 10. Because the LEs are very large when the number of anchor nodes is 3, we use Table 1 to show the results. We can see that the LEs are very large except TCRL.

Table 1

The average computation time and average LE.

Algorithm	Without a coverage hole	With a coverage hole
DV-HOP	418.707	399.594
DV-RND	191.893	144.012
DV-NDR	164.932	130.915
TCRL	39.137	37.421

Figure 10(a) shows that the LEs of the four algorithms decrease as the number of anchor nodes increases and the changing trend is very smooth in network deployment without a coverage hole. Figure 10(b) shows that the LEs of TCRL decrease as the number of anchor nodes increases and the changing trend of other three algorithms is not obvious in network with a coverage hole. In a word, whatever the network deployment, the TCRL algorithm has the enormous advantage in localization error compared with DV-HOP, DV-RND, and DV-NDR, especially in the network with a coverage hole.

In summary, TCRL algorithm always achieves more accurate positioning results than DV-HOP and DV-RND in the two random network scenarios independent of communication range and number of anchor nodes. Through the comparison of TCRL and DV-NDR, we can also verify the effectiveness of the localization strategy of TCRL described in Section 3.3.

5. Conclusions

In this paper, we explore existing range-free algorithms and find two reasons which lead to high localization error. In order to alleviate the two problems in existing range-free algorithms, we propose a novel two-stage centralized range-free localization algorithm, called TCRL. In the first stage, we analyze the relationship between distance and intersection area of neighbor nodes and approve that it is an approximate linear function between them. We use this linear function to get a new neighbor distance relationship NDR between neighbor nodes. We also calculate a NDR correction factor ${\lambda }_{\text{NDR}}$ . Finally, we can obtain the estimated distance between neighbor nodes by ${\lambda }_{\text{NDR}}$ and NDR. Because the shortest distance path between an unknown node and an anchor node is often a zigzag one, especially in the network with a coverage hole, compared with the direct line segment, it leads to distance overestimation and high localization errors by trilateration method. Hence, in the second stage of TCRL, we make an in-depth analysis on the distance between neighbor nodes and design a novel neighborhood function. Then we propose the localization strategy of TCRL based on greedy idea. Using the estimated distance generated by the first stage of TCRL and the localization strategy described by the second stage of TCRL, we can get a set of accurate estimated positions of unknown nodes. Finally, we do a lot of experiments. To make the test scenario closer to the reality, all the sensor nodes are randomly deployed in a region and nodes can only get the connectivity information and do not need any additional hardware to measure RSSI or other pieces of information. We test the impact of different communication range and number of anchor nodes on the estimated distance errors and localization errors to separately verify the effectiveness of distance estimation method and localization strategy of TCRL. The test results show that TCRL algorithm always outperforms DV-HOP and DV-RND in the two network deployments, no matter how much the communication range is and how many anchor nodes there are, especially for the network deployment with a coverage hole.