Sage Journals: Discover world-class research

Abstract

In order to solve the node localization problem in wireless sensor networks, we propose a novel distributed weighted search localization algorithm (WSLA) in this paper. The WSLA adopts a modified received signal strength indicator-based range model to estimate the distances between nodes, utilizes the results of a centroid localization algorithm as the search initial point, and employs a new weighted search method to compute the positions of nodes in a distributed and recursive manner. The key ideas of the WSLA include a node localization precision classification scheme, a processing scheme for special nodes, and weight-based searches. Compared with three state-of-art localization algorithms—namely, maximum likelihood estimation (MLE), edge-based second-order cone programming + nonconvex sequential greedy (ESOCP + NCSG), and particle swarm optimization (PSO)—the simulation results show that localization performance of the WSLA is superior to that of MLE, ESOCP + NCSG, and PSO.

1. Introduction

A wireless sensor network (WSN) is a wireless ad hoc network that consists of a large number of tiny battery-powered, randomly deployed sensor nodes with limited processing, storage, and communication capacity [1]. Many WSN applications, for example, environmental monitoring, forest fire prevention, search and rescue, target detection, and tracking, require knowledge regarding sensor node positions [2]. Therefore, sensor nodes should have ability to localize their positions in many WSN applications.

Today, sensor nodes mainly have two methods of obtaining position information. The first is that sensor nodes are equipped with dedicated localization hardware (e.g., GPS) [3] or are manually configured after deployment. This method is simple and accurate, but it requires higher hardware or deployment costs, which are not acceptable in large-scale WSNs. Therefore, only a few nodes, known as anchor nodes, employ this method. The other method is that sensor nodes localize their positions using software localization techniques. This method has low costs and low energy consumption, with worse localization accuracy than the first method, but it can meet the requirements of most applications. Therefore, the majority of nodes employ this method; these nodes are called normal or unknown nodes.

In general, localization algorithms can be divided into two categories: range-based localization and range-free localization. In range-based localization, nodes are able to measure the distances or angles to their neighbors using received signal strength indicator (RSSI), time-of-arrival, time difference of arrival, angle-of-arrival, and so on [4, 5]. In range-free localization, for example, centroid localization, APIT, DV-Hop, and LAEP [6–10], nodes have no ability to measure the distances or angles to their neighbors and instead use connectivity or hop information to compute the positions of the nodes. Range-based localization can provide higher localization accuracy than range-free localization, but the latter is simpler and does not require extra hardware for measurement.

Localization algorithms can also be classified as centralized localization and distributed localization [11]. Centralized algorithms can process all range or connectivity information of the nodes from the global optimization angle. Therefore, their results are more accurate than those of distributed algorithms. However, they need to transmit a large amount of range or connectivity information to a fusion node (e.g., base station), which results in large energy communication and bandwidth consumption and shortens the lifespan of the entire network. Therefore, they are not suitable for large-scale resource-constrained WSNs. In contrast to centralized algorithms, distributed algorithms use only the local information available from its neighbors, and they are energy efficient and scalable to the size of a network. Therefore, distributed algorithms are more attractive for large-scale resource-constrained WSNs.

In this paper, we propose a distributed weighted search localization algorithm (WSLA) for node localization in WSNs. The WSLA adopts a modified RSSI-based range model to estimate the distances between nodes, and it employs a novel search method to compute node positions. To the best of knowledge, our contributions are as follows: (i)

In order to make the simulation results more consistent with the measured results of RSSI- based range model, we point out that the variance of the Gaussian random variable in the log-normal distribution path loss model should be proportional to the real distance.

(ii)

We propose a novel weighted search method, which has a heuristic search process, to solve the node localization problem in WSNs.

(iii)

In order to further improve the localization accuracy of our method, we propose a FIFO-based localization precision classification scheme, a processing scheme for localizing the special nodes, and a simple scheme for detecting nodes with a large localization error.

(iv)

We have evaluated the performance of the WSLA using extensive simulations, and the simulation results show that the localization performance of the WSLA is superior to that of three state-of-art localization algorithms, namely, maximum likelihood estimation (MLE), edge-based second-order cone programming + nonconvex sequential greedy (ESOCP + NCSG), and particle swarm optimization (PSO).

The remainder of this paper is organized as follows. In the next section, we review the related work about range-based localization. The RSSI-based range model in this paper is discussed in Section 3. In Section 4, we propose the WSLA in detail. The simulation experiments appear in Section 5, and we conclude this paper in Section 6.

2. Related Work

Range-based localization is often modeled as an optimization problem with an objective function that depends on the distances and positions of nodes. In general, even in the absence of range errors, it is possible to have a nonconvex optimization problem with many local minima. Therefore, it is impossible to localize nodes at their true positions with noisy range. The solution to the localization problem can be roughly divided into two categories: one based on mathematical optimization theories and the other based on intelligent search methods.

MLE is a simple method for computing the extreme values of math functions with limited computational complexity [12]. MLE and its improvement versions have become the basic methods used for WSN localization. The performance of MLE-based localization is very good in the absence of range errors. However, its localization accuracy deteriorates rapidly with noisy range. Multidimensional scaling (MDS) is another kind of classic range-based algorithm, and a set of localization algorithms based on MDS is proposed in [13]. In [14], Costa et al. proposed distributed weighted MDS for localization, which adopts a weighted cost function, an adaptive neighbor selection method, and a majorization method to achieve node localization.

Recently, a number of approaches that relax the original localization nonconvex problem to derive a convex problem have been proposed. After relaxation, the convex problem can be efficiently solved using the currently available optimization techniques, such as the interior point method. Two convex relaxation techniques are involved in these algorithms: semidefinite programming (SDP) relaxation in [15, 16] and second-order cone programming (SOCP) relaxation in [11, 17, 18]. Compared with SDP relaxation, SOCP relaxation, although weaker (and thus less accurate), has a simpler structure and allows for efficient distributed implementation. The drawback of the relaxation methods is that even when the original problem is uniquely localizable, the relaxed problem may not be [19]. In addition, both SDP and SOCP rely on a sophisticated optimization package that cannot be easily implemented on a sensor node with limited resources.

Search-based localizations are another kind of WSN localization algorithm, and this kind of algorithm has the potential to achieve relatively high accuracy with relatively low complexity. Zhang et al. achieved localization with genetic algorithm (GA) in [20], which adopts two new genetic operators: single-vertex-neighborhood mutation and descend-based arithmetic crossover. Kulkarni and Venayagamoorthy proposed a distributed particle swarm optimization (PSO) approach for localization in [21]. Shekofteh et al. proposed a localization algorithm based on tabu search (TS) and simulated annealing (SA) in [22], where TS is a dynamic neighbor search technique that drives the search by escaping from local optima and avoiding the cycling. Wang et al. proposed a sequence search (SS) based localization algorithm in [23] that can improve localization accuracy by optimizing the localization sequence. Manjarres et al. proposed a harmony search (HS) localization algorithm in [24] that mimics the improvisation process of musicians seeking the best harmony. The main drawback of these search-based algorithms is that the search points are generated randomly, which results in a very slow convergence process, and they cannot ensure convergence to the global optima.

3. Improved RSSI Range Model

The basic idea of the RSSI range model is to estimate the distance between the receiving and the transmitting nodes by measuring the transmitted loss rate of the radio signal, and its key is the path loss model of signal propagation. The most used path loss model in RSSI range is the log-normal distribution model [4], which is as follows:

\begin{matrix} P_{r, d B} (d) = P_{r, d B} (d_{0}) - 10 * n_{p} * \log (\frac{d}{d_{0}}) + X_{σ}, \end{matrix}

(1)

where

d_{0}

is the reference distance; d is the distance between the transmitting node and the receiving node;

P_{r, d B} (d_{0})

is the path loss at

d_{0}

distance to the transmitting node;

n_{p}

is the path loss constant and usually equals 2~6; and

X_{σ}

is a Gaussian random variable with a mean of 0 and a variance of σ. According to (1), the distance d can be obtained as follows:

\begin{array}{l} d = d_{0} * 1 0^{(P_{r, d B} (d_{0}) + X_{σ} - P_{r, d B} (d)) / 10 * n_{p}} \\ = d_{0} * 1 0^{(P_{r, d B} (d_{0}) + X_{σ} + P_{T} - P_{R}) / 10 * n_{p}} . \end{array}

(2)

In (2), $P_{T}$ (dbm) is the power of the transmitting node, and $P_{R}$ (dbm), measured by RSSI, is the power of the receiving node. In the traditional RSSI range model, $n_{p}$ and σ are assumed to be a constant value. Using this model, when $n_{p}$ = 3, $P (d_{0})$ = −30 dbm, $P_{T} = 0$ dbm, and σ = 2, the RSSI simulation data are as shown in Figure 1. We find that theoretical RSSI data and the simulated average RSSI data match very well.

Figure 1

RSSI simulation data, $n_{p}$ = 3, $P (d_{0})$ = −30 dbm, $P_{T} = 0$ dbm, $σ = 2$ .

The actual measured RSSI data in [25] are shown in Figure 2. We can see that there exists a visible difference between Figures 1 and 2, which shows that the traditional RSSI-based range model is too optimistic.

Figure 2

RSSI measured data in [25].

According to the results in [25–27], the features of the measured RSSI data in the open outdoor environment are as follows: (i)

The actual measured RSSI value is close to the estimated value of (1) when the distance is small (e.g., shorter than 10 m) but fluctuates around the estimated value of (1) when the distance is far.

(ii)

The actual measured RSSI value is a normal distribution at the same point.

(iii)

Range error is proportional to distance, which means the error is small when the distance is short, and longer distances result in more errors.

Therefore, in our RSSI range model, we assume $n_{p}$ = 3, $P (d_{0})$ = −30 dbm, and $P_{T}$ = 0 dbm, but we also assume that $σ = n f \times d$ . $n f$ is used to control the total noise level, and d indicates that the range error is proportional to the distance. Using this model, the simulated RSSI data are shown in Figure 3. We can see that Figure 3 is more consistent with Figure 2 compared with Figure 1.

Figure 3

The improved RSSI range model, $n f = 0.5$ .

4. The Proposed WSLA

4.1. Localization Problem in WSNs

The WSN can be represented by an undirected graph $G = (N, E)$ , where N is the set of all sensors and E is the set of edges. The set N consists of a set of anchors, $N_{A}$ , a set of unknown nodes, $N_{U}$ , and $N = N_{A} \cup N_{U}$ . We denote $x r_{i}$ as the real coordinates of a node i, and $x r_{i}$ is 2-dimension vector. An edge $(i, j) \in E$ if nodes $i, j$ are neighbors; that is, they are in the communication range, R, of each other: $d r_{i j} = ‖x r_{i} - x r_{j}‖ \leq R$ , where $d r_{i j}$ is the real distance between nodes i and j, and $‖\cdot‖$ denotes the 2-norm. We denote $d e_{i j}$ as the estimated distance between nodes i and j and denote D as the set of all available noisy range: $D = {d e_{i j} | (i, j) \in E}$ . The estimated coordinates of a node i, $x e_{i}$ , could be obtained in a distributed manner by solving (3), where $N_{i}$ is the neighbor set of a node i: $N_{i} = {j |$ the node j is the neighbor of node $i}$ . Consider

\begin{matrix} \min_{x e_{i}} \sum_{j \in N_{i}} {(‖x e_{i} - x e_{j}‖ - d e_{i j})}^{2} . \end{matrix}

(3)

4.2. The Basic Search Scheme

The proposed WSLA runs in a round manner to recursively localize the unknown nodes. In each round, it mainly employs a novel heuristic search method to localize the nodes as follows, where $x e_{i}^{(k)}$ denotes the estimated coordinates of the node i at the kth round.

Step 1.

Determine the initial search point $x e_{i, 0}^{(k)}$ . If a node i is not localized before, the WSLA uses the centroid of its neighbors, defined in (4), as the initial search point; otherwise, it uses $x e_{i}^{(k - 1)}$ , the localization position of the last round, as the initial search point

\begin{matrix} x e_{i, 0}^{(k)} = \frac{1}{m} \sum_{j = 1}^{m} x e_{j}^{(k - 1)}, j \in N_{i}, m = |N_{i}| . \end{matrix}

(4)

Step 2.

Take N equal interval points from the circle whose center is $x e_{i, 0}^{(k)}$ and radius is search_step, which is shown in Figure 4. In our simulations, N is equal to 8, and the coordinates of these N search points are as follows:

\begin{matrix} x e_{i, l}^{(k)} = x e_{i, 0}^{(k)} + s e a r c h_s t e p \times {[\cos θ_{l}, \sin θ_{l}]}^{T}, \\ θ_{l} = (l - 1) * \frac{2 π}{N}, l = 1,2, \dots, N . \end{matrix}

(5)

Figure 4

The proposed heuristic search scheme.

Step 3.

Calculate the value of the objective function, defined in (6), at the above $N + 1$ search points (including the circle center). In (6), $w (j)$ is the weight of the node j, which is defined in (7):

\begin{array}{l} f (x e_{i, l}^{(k)}) = \sum_{j = 1}^{m} {(‖x e_{i, l}^{(k)} - x e_{j}^{(k - 1)}‖ - d e_{i j})}^{2} \times w (j), \\ j \in N_{i}, l = 0,1, \dots, N . \end{array}

(6)

In order to enhance the localization accuracy, the WSLA classifies nodes into four classes— $N_{A}$ (anchor nodes), $N_{H}$ (high-precision nodes), $N_{L}$ (low-precision nodes), and $N_{U}$ (unknown nodes)—and assign a different weight for the different type of nodes, as shown in (7), by extensive simulations. The design guideline is to assign a larger weight to more accurate nodes (e.g., anchor nodes) and to assign a smaller weight to less accurate nodes (e.g., low-precision nodes):

\begin{matrix} w (j) = \{\begin{cases} 1 & S_{j} is anchor node \\ 0.5 & S_{j} is high precision node \\ 0.125 & S_{j} is low precision node \\ 0 & S_{j} is unknown nodes. \end{cases} \end{matrix}

(7)

Step 4.

We assume that the point $x e_{i, \min}^{(k)}$ , defined in (8), is the minimum value in the current search iteration. Then, the WSLA updates $x e_{i, 0}^{(k)}$ and search_step according to (9) and (10) for the next search iteration:

\begin{matrix} f (x e_{i, \min}^{(k)}) = \min_{l = 0,1, \dots, N} \{f (x e_{i, l}^{(k)})\}, \end{matrix}

(8)

\begin{matrix} x e_{i, 0}^{(k)} = x e_{i, \min}^{(k)}, \end{matrix}

(9)

\begin{matrix} s e a r c h_s t e p = α * s e a r c h_s t e p . \end{matrix}

(10)

Step 5.

Repeat Steps 2–4 until search_step is less than stop_th. Finally, the estimated coordinates of a node i are $x e_{i, 0}^{(k)}$ at the last search iteration, which is called the best estimated point (BEP) of the node i in the current round.

Remark 1.

In (10), α is the convergence factor, which can control the convergence speed and belongs to $(0,1)$ in theory; stop_th is the search stopping threshold. The localization accuracy and complexity of the WSLA are mainly determined by α and stop_th, and generally speaking, the smaller stop_th is and the larger α is, the higher the localization accuracy and complexity will be.

4.3. The Localization Scheme of Special Nodes

In general, the BEP of a node i may be not unique if one of the following conditions is satisfied: (1) the number of its known neighbors is less than 3 or (2) its known neighbors are collinear or near collinear. This situation appears frequently in the initial several rounds of the WSLA or when the node is near to the boundary of network. From the angle of improving localization accuracy, the WSLA should ignore these nodes. However, if these nodes cannot be localized, the WSLA maybe cannot run because all nodes may not have three or more known neighbors in the first round. Therefore, to quickly realize higher localization coverage, we propose the following localization methods for these special nodes.

(1) A Node with One Known Neighbor. The first special case is that a node i has one known neighbor in the early rounds of the WSLA. In this case, any point on the circle whose center is its known neighbor and whose radius is the range distance between them can satisfy (3) or (8); the WSLA takes the position of its known neighbor as its localization position in the current round. We expect that the localization error of i will decrease with the running of the WSLA when more neighbors become known in the following rounds.

(2) A Node with Collinear or Near Collinear Neighbors. The second special case is that a node i has collinear or near collinear neighbors. A typical scene is shown in Figure 5, where node C has two neighbors, A and B, and hence the neighbors of node C are collinear. Both points $P_{1}$ and $P_{2}$ are the possible BEP because they both satisfy (3) or (8); $P_{1}$ is near node C, with a small localization error, and P₂ is far from node C, with a large localization error. Because we do not know whether the search result in Section 4.2 is $P_{1}$ or $P_{2}$ , we choose point D as the final BEP to avoid a large localization error. Similar to the first case, we also expect that the localization error of i will decrease with the running of the WSLA when more neighbors become known in the following rounds.

Figure 5

Node localization with two neighbors.

Point D can be obtained using the following steps: (a)

Make a straight line $A B$ , the connecting line of points A and B.

(b)

Make the vertical line of $A B$ from $P_{1}$ or $P_{2}$ .

(c)

Take the intersection (point D) of the two lines as the final BEP of C.

We assume that the coordinates of A, B, $P_{1}$ (or $P_{2}$ ), and D are $(x_{A}, y_{A})$ , $(x_{B}, y_{B})$ , $(x_{P}, y_{P})$ , and $(x_{D}, y_{D})$ , respectively, and then the coordinates of D are as follows:

\begin{matrix} x_{D} = \frac{(b_{1} - b_{2})}{(k_{2} - k_{1})}, \\ y_{D} = k_{1} x_{D} + b_{1}, \end{matrix}

(11)

where

\begin{matrix} k_{1} = \frac{(y_{A} - y_{B})}{(x_{A} - x_{B})}, \\ k_{2} = - \frac{1}{k_{1}}, \\ b_{1} = y_{A} - k_{1} x_{A}, \\ b_{2} = y_{P} - k_{2} x_{P} . \end{matrix}

(12)

4.4. Node Localization Precision Classification Scheme

We define a FIFO queue $Q_{i}$ with a size of $l_{q}$ for each node i, and we denote $q_{i}$ as the quantity of the elements in $Q_{i}$ . After each round, we put the BEP of node i into queue $Q_{i}$ and calculate the centroid of polygon $Ψ_{i}$ which is formed by all elements in queue $Q_{i}$ .

At the beginning, there are only anchor nodes and unknown nodes in the networks. During localization algorithm running, the WSLA gradually classifies unknown nodes into $N_{H}$ and $N_{L}$ according to the following rule:

Rule 1.

The WSLA classifies node i into $N_{H}$ if all following conditions are satisfied: (i)

Its queue $Q_{i}$ is full, namely, $q_{i} = l_{q}$ .

(ii)

The distance from any element in $Q_{i}$ to the centroid of $Ψ_{i}$ is not greater than a threshold $T_{d}$ .

Rule 2.

The WSLA classifies node i into $N_{L}$ if any of the following conditions are satisfied: (i)

Its queue $Q_{i}$ is not full but not empty, namely, $0 < q_{i} < l_{q}$ .

(ii)

The distance from some element in $Q_{i}$ to the centroid of $Ψ_{i}$ is greater than the threshold $T_{d}$ .

An example of node localization precision classification is shown in Figure 6. In Figure 6, we assume $q_{i} = l_{q} = 5$ ; that is to say, $Q_{i}$ is full. Because the distance from any element in $Q_{i}$ to the centroid of $Ψ_{i}$ is not greater than $T_{d}$ in Figure 6(a), this node is classified into $N_{H}$ . In Figure 6(b), the distance from $(x_{3}, y_{3})$ to the centroid is greater than $T_{d}$ ; thus, this node is classified into $N_{L}$ .

Figure 6

An example of node localization precision classification.

In addition, we also observe that the node localization sequence has an obvious influence on the localization accuracy for some localization scenes, as described in [23]. Specifically, in the initial several rounds of the WSLA, if a node with a large localization error takes part in the localization process of other nodes, its localization error may propagate due to the recursive localization method and thus results in a network localization accuracy decline. In order to avoid the emergence of this situation, in the initial several rounds (e.g., the first 30% rounds), the WSLA employs the following method to detect the node with a large localization error.

Rule 3.

If the absolute difference value between $d_{i j}$ (network distance) and $d e_{i j}$ (range distance) from node i to j in $N_{i}$ is greater than the error threshold err_th, we think that i is not localized accurately, and the WSLA classifies i into $N_{U}$ by 25% probability and $N_{L}$ by 75% probability to avoid or decrease the localization error propagated. Rule 3 is concluded as shown in

\begin{array}{l} \forall i, \exists j \in N_{i}, \\ |d_{i j} - d e_{i j}| > err_th, \\ d_{i j} = ‖x e_{i}^{(k)} - x e_{j}^{(k - 1)}‖ \\ ⟹ \{\begin{cases} i \in N_{U} & p = 0.25 \\ i \in N_{L} & p = 0.75 . \end{cases} \end{array}

(13)

4.5. The Specific Flow of the WSLA

The specific steps of the WSLA in each round are as follows.

Step 1 (node broadcasting).

All nodes except unknown nodes broadcast their messages, for example, transmitting power, ID, coordinates, and types, at the beginning of each round.

Step 2 (RSSI ranging).

All nodes except anchor nodes receive messages from their neighbors and calculate the range distances according to (2). In our simulations, each node carries out 10 RSSI ranges in each round, and the final range distance is the average results.

Step 3 (node localization).

If the number of known neighbors of node i is larger than 1, the WSLA employs the search method in Section 4.2 to search its BEP.

Step 4 (Special node processing).

If node i is a special node, the WSLA employs the scheme in Section 4.3 to compute its new BEP.

Step 5 (node classification).

The WSLA puts the BEP into queue $Q_{i}$ and determines the localization type of the current round based on the Rules 1–3 in Section 4.4.

In addition, when the position errors of anchor nodes is not zero, the WSLA degrades the anchor nodes into low precision nodes to refine their positions after running 15 rounds.

5. Simulation Experiments

To prove the localization accuracy of the WSLA, we have carried out extensive simulations using MATLAB software.

5.1. Experiment Parameters

The default simulation parameters are as follows: the number of total nodes is 108, including 8 anchor nodes and 100 unknown nodes; the positions of the anchor nodes are fixed and their coordinates are [0.1, 0.1], [0.1, 0.5], [0.1, 0.9], [0.5, 0.1], [0.5, 0.9], [0.9, 0.1], [0.9, 0.5], and [0.9, 0.9]; the unknown nodes are uniformly distributed in a square region of 1 × 1; the communication range $R = 0.22$ , leading to an average connectivity of the nodes of about 13; and $n f = 0.3$ , initial_step $= 0.75 \times R$ , max_round = 60, $T_{d}$ = 0.01R, and stop_th $= 0.01 \times R$ ; in addition, we set err_th $= 0.005 R + 0.1 \times n a$ , and $n a$ is the maximum position errors of the anchor nodes; that is, $‖x e_{i} - x r_{i}‖ \leq n a$ , $i \in N_{A}$ , where $x r_{i}$ and $x e_{i}$ are the real coordinates and the localized coordinates of the node i and the default value of $n a$ is $0.2 R$ . The experimental results are the averaged results of 30 experiments, and the range error $ε_{r}$ and localization error $ε_{l}$ , defined in (14) and (15), respectively, are used as the performance standard:

\begin{matrix} ε_{r} = \frac{1}{M} \sum_{(i, j)} \frac{|d e_{i j} - d r_{i j}|}{R}, \end{matrix}

(14)

\begin{matrix} ε_{l} = \frac{1}{N} \sum_{i = 1}^{N} \frac{‖x e_{i} - x r_{i}‖}{R}, N = |N_{U}| . \end{matrix}

(15)

In (14),

d e_{i j}

and

d r_{i j}

are the range distances and the real distances between nodes i and j; M is the total range time.

5.2. The Performance of the WSLA

(1) The Convergence Process of the WSLA. We first examine the convergence performance of the WSLA in the ideal range condition, that is, $n f = 0$ , leading to $d e_{i j} = d r_{i j}$ . In this experiment, we reset the following parameters: stop_th $= 0.001 \times R$ , $T_{d} = 0.001 R$ , max_round = 120, $n f = 0$ , and $n a = 0$ . The convergence process of the WSLA is presented in Figure 7.

Figure 7

The convergence process of the WSLA.

From Figure 7, we can observe the following. $(1)$ The WSLA is convergent, and the localization error in the initial several rounds is relatively large because the number of known neighbors of each node is relatively small. $(2)$ Even in ideal conditions, the WSLA cannot converge to 0. In our 30 experiments, the best scene and the worst scene converge to about 0.001R and 0.021R, respectively, and all scenes converge to about 0.006R on average. The reason that the WSLA cannot converge to 0 is because stop_th is not equal to zero, and sometimes the WSLA may fall into the local optima. $(3)$ The convergence process is not strictly monotonic. After the WSLA runs about 60 rounds, the average localization error is near 0.01R, and it decreases only 0.004R during the last 60 rounds. Therefore, in the following experiments, we set that max_round = 60.

(2) The Relationship between $ε_{l}$ and stop_th. Second, we examine the relationship between $ε_{l}$ and stop_th in the ideal range condition. In this experiment, nf = 0, na = 0, and the other parameters are set to their default values. The relationship between $ε_{l}$ and stop_th of the WSLA is presented in Figure 8.

Figure 8

The relationship between $ε_{l}$ and stop_th.

From Figure 8, we can see that the correlation between $ε_{l}$ and stop_th is significant. Specifically, the smaller stop_th is, the lower the localization error will be. However, a small stop_th means more search points and thus the time complexity of the WSLA will increase. In addition, when stop_th equals R, the WSLA will degrade into a centroid localization algorithm because it cannot search any points. In order to achieve the tradeoff between localization error and complexity, in the following experiments, we set stop_th to 0.01R, which means that the WSLA searches 7 iterations and a total of 57 points in each round. Figure 8 also shows that the WSLA makes a vast improvement compared to the centroid localization algorithm when stop_th = 0.01R.

(3) The Relationship between $ε_{l}$ and nf or na. Third, we show the localization performance of the WSLA with the variation of nf or na, and the results are presented in Figure 9.

Figure 9

The relationship of between $ε_{l}$ and nf or na.

From Figure 9, we can see the following. (1) Both range errors and localization errors increase with the growth of nf, but range errors increase faster than localization errors. (2) The WSLA is more sensitive to na than nf. Specifically, the change of $ε_{l}$ is up to about 0.1R when na varies from 0 to 0.5R, and by comparison, the change of $ε_{l}$ is only about 0.007R when nf varies from 0 to 0.5.

(4) The Relationship between $ε_{l}$ and the Node Connectivity. In this experiment, we set nf = 0.3 and na = 0.2R, and vary the node connectivity by changing the number of unknown nodes. The relationship between $ε_{l}$ and the connectivity is shown in Figure 10, and we find that (1) $ε_{l}$ decreases with the growth of the connectivity, and (2) after the average connectivity of the nodes reaches 22, the change of $ε_{l}$ is very small.

Figure 10

Localization error versus the number of nodes.

(5) The Localization Results of a Typical Scene. Finally, we give the straightforward localization results of one typical scene. In this experiment, all parameters are default values. The reason we choose this scene is that its localization error is slightly larger than the average localization error. In Figure 11, ○ denotes the real position of anchor nodes, × denotes the real position of unknown nodes, and ◊ denotes the localized position of nodes. The green nodes are high-precision nodes and the red nodes are low-precision nodes. By comparing Figures 11(a)–11(c), we can obviously see that the localization error becomes gradually smaller, and from Figure 11(d), we can see that the $ε_{l}$ of 88% nodes is less than 0.15R. Therefore, the localization performance of the WSLA is good.

Figure 11

The localization results of one typical scene.

5.3. Performance Comparison with MLE, PSO, and ESOCP + NCSG

In this section, we have compared the localization error of the WSLA with that of MLE [12], ESOCP + NCSG [11], and PSO [21], which are three representatives of state-of-art localization algorithms. Specifically, MLE is representative of a simple localization algorithm, PSO is representative of a search-based localization algorithm, and ESOCP + NCSG is representative of a complex relaxation-based localization algorithm. In this experiment, we use the range model in [11], as shown in (16); the other parameters are the same as the default parameters. The parameters of PSO are set as follows: population = 30, iterations = 60; acceleration constants $c_{1}$ = $c_{2}$ = 2.0; inertial weight is decreased linearly from 0.9 in the first iteration to 0.4 in the last iteration. In addition, to better demonstrate the performance of the WSLA, we also show the performance of the basic search localization algorithm (SLA), which does not employ a localization precision classification scheme, a processing scheme for special nodes, and a simple scheme for detecting nodes with large localization errors. The experimental results are shown in Figure 12:

\begin{matrix} d e_{i j} = d r_{i j} * |(1 + n f * rand n)|, \end{matrix}

(16)

where

d e_{i j}

and

d r_{i j}

are the range distance and real distance, respectively;

n f

also represents the error level; rand n is the random variable subjected to standard normal distribution N (0, 1).

Figure 12

Performance comparison with other localization algorithms.

From Figure 12, we can see the following: $(1)$ The localization performance of the WSLA is the best of these five algorithms. $(2)$ MLE and ESOCP + NCSG are more sensitive to range errors than PSO, SLA, and the WSLA. $(3)$ All the algorithms are sensitive to the position errors of anchor nodes. The explanations for the high performance of the WSLA are as follows. $(1)$ Compared with PSO, the WSLA has a heuristic search process and can significantly reduce the number of search points, for example, it searches 57 points per node, while PSO searches 1800 points per node in each round. $(2)$ Compared with ESOCP + NCSG, the WSLA does not carry out its objective function in any form of relaxation. $(3)$ Compared with MLE, the WSLA has better fault tolerance to range errors and the distribution of neighbors. $(4)$ More importantly, the WSLA has integrated three schemes, namely, a FIFO-based localization precision classification scheme, a processing scheme for localizing the special nodes, and a simple scheme for detecting nodes with large localization errors, to further improve its localization accuracy.

6. Conclusion

The localization technique is one of the key techniques in practical WSN application. On the basis of analyzing the error distribution features of the traditional RSSI-based range model and the measured RSSI data, we improve the RSSI-based range model. We also propose a novel WSLA, which is a range-based heuristic distributed localization algorithm for WSNs. The innovative ideas of the WSLA include a FIFO-based localization precision classification scheme, a processing scheme for special nodes, and a weight-based search. The performance of the WSLA is evaluated by comparing it with three state-of-art localization algorithms, namely, MLE, ESOCP + NCSG, and PSO. The experimental results show that the localization performance of the WSLA is superior to that of MLE, ESOCP + NCSG, and PSO. The features of our algorithm are distributed, low complexity with $O (m)$ (m is the number of one-hop neighbor nodes), easy implementation, and high localization accuracy. Therefore, it has good reference value in engineering practice. Our future works will study the adaptive parameter settings of the WSLA and evaluate its localization performance in real WSNs.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgments

The authors would like to thank the anonymous reviewers for their valuable feedback to this paper. The work was supported in part by The National Science Foundation of China under Grant no. 61100044, Zhejiang Province Science and Technology Innovation Focused Team Foundation under Grant no. 2013TD03, and Zhejiang Province Science and Technology Project under Grant no. 2013C31100.

References

Stojmenovic

Handbook of Sensor Networks Algorithms and Architectures 2005

John Wiley & Sons

Suo

Wan

J. F.

Huang

Zou

C. F.

Issues and challenges of wireless sensor networks localization in emerging applications

Proceedings of the International Conference on Computer Science and Electronics Engineering (ICCSEE ’12)

March 2012

Hangzhou, China

447 451

10.1109/iccsee.2012.44

2-s2.0-84861060330

Bulusu

Heidemann

Estrin

GPS-less low-cost outdoor localization for very small devices

IEEE Personal Communications 2000 7 5 28 34

10.1109/98.878533

2-s2.0-0034291601

Al Alawi

RSSI based location estimation in wireless sensor networks

Proceedings of 17th IEEE International Conference on Networks (ICON '11)

2011

Singapore

118 122

Zhang

Höflinger

Reindl

TDOA-based localization using interacting multiple model estimator and ultrasonic transmitter/receiver

IEEE Transactions on Instrumentation and Measurement 2013 62 8 2205 2214

10.1109/tim.2013.2256713

2-s2.0-84880573026

Chen

Shu

Fan

Wang

Hara

The insights of DV-based localization algorithms in the wireless sensor networks with duty-cycled and radio irregular sensors

Proceedings of the IEEE International Conference on Communications (ICC ’11)

June 2011

Kyoto, Japan

1 6

2-s2.0-80052142473

10.1109/icc.2011.5963365

Doherty

Pister

K. S. J.

El Ghaoui

Convex position estimation in wireless sensor networks

Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '01)

April 2001

Anchorage, Alaska, USA

1655 1663

2-s2.0-0035013232

Tan

H. B.

Liu

Research and implementation of APIT positioning algorithm in WSN

Proceedings of the 9th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD '12)

May 2012

Sichuan, China

IEEE

2212 2215

2-s2.0-84872903555

10.1109/fskd.2012.6234209

Wang

X. D.

Wang

D. M.

Agrawal

D. P.

Range-free localization using expected hop progress in wireless sensor networks

IEEE Transactions on Parallel and Distributed Systems 2009 20 10 1540 1552

10.1109/tpds.2008.239

2-s2.0-70349088999

10.

Zhang

Q. G.

Huang

J. W.

Wang

J. H.

Jin

J. M.

Zhang

A new centralized localization algorithm for wireless sensor network

Proceedings of the 3rd International Conference on Communications and Networking in China

2008

Hangzhou, China

625 629

11.

Shi

Chen

Jiang

Distributed wireless sensor network localization via sequential greedy optimization algorithm

IEEE Transactions on Signal Processing 2010 58 6 3328 3340

10.1109/TSP.2010.2045416

MR2756859

2-s2.0-77952561798

12.

Coluccia

Ricciato

On ML estimation for automatic RSS-based indoor localization

Proceedings of the IEEE 5th International Symposium on Wireless Pervasive Computing (ISWPC '10)

May 2010

Modena, Italy

495 502

10.1109/iswpc.2010.5483724

2-s2.0-77954797060

13.

Shang

Ruml

Zhang

Fromherz

Localization from connectivity in sensor networks

IEEE Transactions on Parallel and Distributed Systems 2004 15 11 961 974

10.1109/TPDS.2004.67

2-s2.0-8744271199

14.

Costa

J. A.

Patwari

Hero

A. O.

III

Distributed weighted-multidimensional scaling for node localization in sensor networks

ACM Transactions on Sensor Networks 2006 2 1 39 64

10.1145/1138127.1138129

2-s2.0-33745240949

15.

Lui

K. W. K.

W.-K.

H. C.

Chan

F. K. W.

Semi-definite programming algorithms for sensor network node localization with uncertainties in anchor positions and/or propagation speed

IEEE Transactions on Signal Processing 2009 57 2 752 763

2-s2.0-60549110264

10.1109/tsp.2008.2007916

MR2603398

16.

Ding

Tian

Han

A distributed node localization algorithm for wireless sensor network based on MDS and SDP

Proceedings of the International Conference on Computer Science and Electronics Engineering (ICCSEE ’12)

March 2012

Hangzhou, China

624 628

10.1109/iccsee.2012.93

2-s2.0-84861024912

17.

Srirangarajan

Tewfik

A. H.

Luo

Z. Q.

Distributed sensor network localization using SOCP relaxation

IEEE Transactions on Wireless Communications 2008 7 12 4886 4895

2-s2.0-58149114571

10.1109/t-wc.2008.070241

18.

Naddafzadeh-Shirazi

Shenouda

M. B.

Lampe

Second order cone programming for sensor network localization with anchor position uncertainty

IEEE Transactions on Wireless Communications 2014 13 2 749 763

10.1109/twc.2013.120613.130170

2-s2.0-84896390215

19.

Naraghi-Pour

Chacon Rojas

A novel algorithm for distributed localization in wireless sensor networks

ACM Transactions on Sensor Networks 2014 11 1, article 1

20.

Zhang

Wang

Jin

Zhang

Genetic algorithm based wireless sensor network localization

Proceedings of the 4th International Conference on Natural Computation (ICNC '08)

October 2008

Jinan, China

IEEE

608 613

10.1109/icnc.2008.206

2-s2.0-57649202059

21.

Kulkarni

R. V.

Venayagamoorthy

G. K.

Bio-inspired algorithms for autonomous deployment and localization of sensor nodes

IEEE Transactions on Systems, Man and Cybernetics 2010 40 6 663 675

2-s2.0-77958150809

10.1109/tsmcc.2010.2049649

22.

Shekofteh

S. K.

Khalkhali

M. B.

Yaghmaee

M. H.

Deldari

Localization in wireless sensor networks using tabu search and simulated annealing

Proceedings of the 2nd International Conference on Computer and Automation Engineering (ICCAE ’10)

February 2010

Singapore

752 757

10.1109/iccae.2010.5451779

2-s2.0-77952643496

23.

Wang

H. S.

McDonald-Maier

Optimization and sequence search based localization in wireless sensor networks

Proceedings of the 3rd International Conference on Emerging Security Technologies (EST '12)

September 2012

Lisbon, Portugal

155 160

2-s2.0-84869401693

10.1109/est.2012.25

24.

Manjarres

Ser

J. D.

Gil-Lopez

Vecchio

Landa-Torres

Lopez-Valcarce

On the application of a hybrid harmony search algorithm to node localization in anchor-based wireless sensor networks

Proceedings of the 11th International Conference on Intelligent Systems Design and Applications (ISDA '11)

November 2011

Córdoba, Spain

IEEE

1014 1019

10.1109/ISDA.2011.6121791

25.

C.-C.

Chung

W.-Y.

Mitigation of multipath fading effects to improve indoor RSSI performance

IEEE Sensors Journal 2008 8 11 1884 1886

10.1109/JSEN.2008.2006453

2-s2.0-67650309025

26.

Fang

Zhao

Geng

Xuan

Cui

RSSI variability characterization and calibration method in wireless sensor network

Proceedings of the IEEE International Conference on Information and Automation (ICIA '10)

June 2010

Harbin, China

IEEE

1532 1537

10.1109/icinfa.2010.5512318

2-s2.0-77955740884

27.

Daiya

Ebenezer

Murty

S. A. V. S.

Raj

Experimental analysis of RSSI for distance and position estimation

Proceedings of the IEEE International Conference on Recent Trends in Information Technology (ICRTIT '11)

June 2011

Tamil Nadu, India

IEEE

1093 1098

10.1109/icrtit.2011.5972367

2-s2.0-80052215396

A RSSI-Based Distributed Weighted Search Localization Algorithm for WSNs

Abstract

1. Introduction

2. Related Work

3. Improved RSSI Range Model

4. The Proposed WSLA

4.1. Localization Problem in WSNs

4.2. The Basic Search Scheme

Step 1.

Step 2.

Step 3.

Step 4.

Step 5.

Remark 1.

4.3. The Localization Scheme of Special Nodes

4.4. Node Localization Precision Classification Scheme

Rule 1.

Rule 2.

Rule 3.

4.5. The Specific Flow of the WSLA

Step 1 (node broadcasting).

Step 2 (RSSI ranging).

Step 3 (node localization).

Step 4 (Special node processing).

Step 5 (node classification).

5. Simulation Experiments

5.1. Experiment Parameters

5.2. The Performance of the WSLA

5.3. Performance Comparison with MLE, PSO, and ESOCP + NCSG

6. Conclusion

Footnotes

Conflict of Interests

Acknowledgments

References