Accurate Nodes Localization in Anisotropic Wireless Sensor Networks

Abstract

An accurate localization algorithm tailored for anisotropic wireless sensors networks (WSNs) is proposed in this paper. Using the proposed algorithm, each regular or position-unaware node estimates its distances only to reliable anchors or position-aware nodes. The latter are properly chosen following a new reliable anchor selection strategy that ensures an accurate distance estimation making thereby our localization algorithm more precise. It is shown that the proposed algorithm is implementable in both 2-dimensional (2D) and 3-dimensional (3D) scenarios. A power saving mechanism aiming to enhance the WSN lifetime is also envisaged in this paper. It is proven that the proposed algorithm could easily incorporate such a mechanism. Simulations show that our algorithm, whether combined or not with the power saving mechanism, consistently outperforms the best representative localization algorithms currently available in the literature in terms of accuracy, even with the presence of nonuniform node distribution or radiation irregularities.

1. Introduction

Due to their reliability, low cost, and ease of deployment, wireless sensor networks (WSNs) are emerging as a key tool for many applications such as environment monitoring, disaster relief, and target tracking [1, 2]. A WSN is a set of small and low-cost sensor nodes with limited communication capabilities. The latter are often deployed in a random fashion to collect some physical phenomena from the surrounding environments such as temperature, light, and pressure [3]. Due to their limited transmission ranges, the sensor nodes are often unable to directly communicate with a remote access point (AP). For this reason, they recur to multihop communication through several intermediate nodes that successively forward their gathered data to the AP. However, the sensing data are very often meaningless if the location from where they have been measured is unknown, which makes their localization a fundamental and essential issue in WSNs. So far, many localization algorithms have been proposed in the literature and mainly fall into two categories: range-based and range-free algorithms.

To properly localize the regular or position-unaware nodes, range-based algorithms exploit the measurements of the received signal characteristics such as the time of arrival (TOA), the angle of arrival (AOA), or the received signal strength (RSS) [4–6]. These signals are, in fact, transmitted by nodes having prior knowledge of their positions, called anchors (or landmarks). Although the range-based algorithms stand to be very accurate, they are unsuitable for WSNs. Indeed, these algorithms require high power to ensure communication between anchors and regular nodes which are small battery-powered units. Furthermore, additional hardware is usually required at both anchors and regular nodes, thereby increasing the overall cost of the network. Moreover, the performance of these algorithms can be severely affected by noise, interference, and/or fading. Unlike range-based algorithms, range-free algorithms, which rely on the network connectivity to estimate the regular node positions, are more power-efficient and do not require any additional hardware and, hence, are suitable for WSNs [7–21]. Due to these practical merits, range-free localization algorithms have garnered the attention of the research community. Unfortunately, in anisotropic environments where obstacles and/or holes may exist, range-free algorithms do not provide sufficient accuracy due to large errors occurring when mapping the hops into distance units. Indeed, in such environments, it is very likely that the shortest path between an anchor and a regular node is curved, thereby resulting in overestimation of the distance between these two nodes. The more obstacles and/or holes there are, the larger distance estimation errors and, consequently, less accurate localization there are.

In this paper, we propose a novel range-free localization algorithm tailored for anisotropic WSNs. Using the proposed algorithm, each regular node estimates its distances only to reliable anchors. The latter are properly chosen following a new reliable anchor selection strategy that ensures an accurate distance estimation thereby making our localization algorithm more precise. New average hop sizes’ expressions are also developed in this paper for both 2D and 3D scenarios. We show that the obtained expressions are very accurate especially for high nodes densities. Furthermore, a power saving mechanism aiming to enhance the WSN lifetime is envisaged. We prove that our proposed algorithm could easily incorporate such a mechanism. Simulations show that our algorithm, whether combined or not with the power saving mechanism, consistently outperforms the best representative range-free localization algorithms currently available in the literature in terms of accuracy, even with the presence of nonuniform node distribution or radiation irregularities.

The rest of this paper is organized as follows: Section 2 describes the network model. Section 3 presents the related works and defines the motivation scenario. Section 4 proposes a novel localization algorithm while Sections 5 and 6 introduce a new reliable anchor selection strategy and a novel distance estimation technique, respectively. A power saving mechanism aiming to enhance the WSN lifetime is envisaged in Section 7. Simulation results are discussed in Section 8 and concluding remarks are made in Section 9.

2. Network Model

Figure 1 illustrates the system model of N WSN nodes uniformly deployed in a 2D square area S in the presence of a rectangle obstacle which makes the network topology C-shaped. All nodes are assumed to have the same transmission capability (i.e., range) denoted by R. Each node is able to directly communicate with any other node located in the disc having that node as a center and R as a radius, while it communicates in a multihop fashion with the nodes located outside. Due to the high cost of the global positioning system (GPS) technology, only a few nodes commonly known as anchors are equipped with it and, hence, are aware of their positions. The other nodes, called hereafter position-unaware or regular nodes for the sake of simplicity, are oblivious to this information. As shown in Figure 1, the anchor nodes are marked with red triangles and the regular ones are marked with blue circles. If two nodes are able to directly communicate, they are linked with a dashed line that represents one hop. Let $N_a$ and $N_u=N-N_a$ denote the number of anchors and regular nodes, respectively. Without loss of generality, let $\left(x_i,y_i\right)$ , $i=\mathrm{1},\dots ,N_a$ , be the coordinates of the anchor nodes and $\left(x_i,y_i\right)$ , $i=N_a+\mathrm{1},\dots ,N$ , those of the regular ones.

Figure 1

Network model (C-shaped topology).

3. Related Works and Motivation

In order to localize the ith regular node (i.e., $(N_a+i)$ th node), the distances between it and at least 3 anchors are usually required. The kth anchor should then broadcast its coordinates $\left(x_k,y_k\right)$ through the network. If the ith regular node is located in the coverage area of this anchor (i.e., the disc $D(k,R)$ having the kth anchor as center and R as radius), it receives the coordinates in $n_k=\mathrm{1}$ hop. Otherwise, it receives them after $n_k>\mathrm{1}$ hops. So far, in most previous algorithms, the ith regular node estimates its distance to the kth anchor $d_{k-(N_a+i)}$ using only the information $n_k$ as

$$\begin{array}{cc}& {\widehat{d}}_{k-\left(N_a+i\right)}=n_k{\bar{h}}_s,\end{array}$$

(1)

where ${\bar{h}}_s$ is a predefined average hop size. Note that this distance estimation approach relies on the fact that, in highly dense WSNs,

$$\begin{array}{cc}& d_{k-\left(N_a+i\right)}\approx {\displaystyle \sum }_{l=\mathrm{1}}^{n_k}{h}_l\end{array}$$

(2)

holds. In (2), $h_l$ is the lth hop's distance. ${\bar{h}}_s$ is usually derived either analytically (i.e., ${\bar{h}}_s=E\left\{h_l\right\}$ ) as with LAEP [13] or heuristically as with DV-Hop [7] by computing the mean hop size of all the shortest paths between anchors as follows:

$$\begin{array}{cc}& {\bar{h}}_s=\frac{\mathrm{1}}{N_a\left(N_a-\mathrm{1}\right)}{\displaystyle \sum }_{k=\mathrm{1}}^{N_a}\hspace{0.17em}{\displaystyle \sum }_{j=\mathrm{1}}^{N_a}\frac{d_{k-j}}{n_{k,j}},\end{array}$$

(3)

where $n_{k,j}$ is the number of hops between the kth and jth anchors. Although heuristical and analytical algorithms are proven to be sufficiently accurate in isotropic WSNs (i.e., where obstacles do not exist), their accuracies substantially deteriorate in anisotropic WSNs (AWSNs). Indeed, in such type of networks, it is very likely that the shortest paths between one regular node and some anchors are not straight lines due to the presence of an obstacle, as can be observed from Figure 2. This unfortunately causes an overestimation of the distances between the regular node and these anchors, when mapping the number of hops into distance, thereby hindering localization accuracy. In the example of Figure 2, the regular node 1 communicates with the anchor node $A_{\mathrm{1}}$ through $n_{\mathrm{1}}=\mathrm{6}$ hops. Its distance estimate to this anchor ${\widehat{d}}_{k-(N_a+\mathrm{1})}$ is derived using (1). As can be seen from Figure 2, if the blue obstacle does not exist, $n_{\mathrm{1}}$ would be much less than 6 and, hence, the distance from i to $A_{\mathrm{1}}$ is overestimated. Thus, using ${\widehat{d}}_{k-(N_a+i)}$ when performing multilateration will undoubtedly result in an imprecise localization. An interesting approach to circumvent this issue is to properly select the anchors so that overestimation stemming from situations similar to the one illustrated in Figure 2 is avoided or minimized. Based on this reliable anchor selection, several localization algorithms for AWSNs have been so far proposed such as pattern-driven in [20] and RAL in [21]. Despite their valuables to the advancement of knowledge and know-how in this key topic, we will later see that they still leave room for significant additional accuracy improvements in AWSNs.

Figure 2

Motivation scenario.

In the following, we develop a novel localization algorithm based on new reliable anchor selection strategy and prove that it outperforms all the aforementioned algorithms.

4. Proposed Localization Algorithm

As a first step of any anchor-based localization algorithm, the kth anchor broadcasts through the network a message containing $(x_k,y_k,n)$ where n is the hop-count value initialized to one. When a node receives this message, it stores the kth anchor position as well as the received hop-count $n_k=n$ in its database, adds one to the hop-count value, and broadcasts the resulting message. Once this message is received by another node, its database information is checked. If the kth anchor information exists and the received hop-count value n is smaller than the stored one $n_k$ , the node updates $n_k$ to n, increases it by 1, and then broadcasts the resulting message. If $n_k$ is smaller than n, the node discards the received message. However, when the node is oblivious to the kth anchor position, it adds this information to its database and forwards the received message after increasing n by 1. This mechanism will continue until all nodes become aware of all anchors’ positions and their corresponding minimum hop counts. In order to avoid the situation illustrated in Figure 2, we propose a reliable anchor selection phase in the second step of our algorithm. In the next section, we introduce a new selection strategy where the kth anchor properly selects a set of reliable anchors among all of those in the network denoted by $s_k$ . The kth anchor then broadcasts $s_k$ over the network. Upon reception of all $\left(x_k,y_k,n_k,s_k\right)$ , $k=\mathrm{1},\dots ,N_a$ , each regular node estimates its distance only to its nearest anchor (i.e, $k_{\mathrm{0}}=\text{arg}{\mathrm{m}\mathrm{i}\mathrm{n}}_k{n}_k$ ) and to the reliable anchors in the set $s_{k_{\mathrm{0}}}$ . The regular nodes finally compute their own positions exploiting their available distances’ estimates by performing multilateration [22].

In what follows, we develop our proposed reliable anchor selection strategy as well as our distance estimation technique.

5. Reliable Anchor Selection Strategy

After receiving all anchors’ information, the kth anchor becomes aware of its own position as well as those of all other anchors in the network and, hence, is able to compute all true distances separating it from the latter. On the other hand, this anchor could also compute the estimate of the distance to any other anchor j and the corresponding estimation error $e_{k-j}$ stemming from the use of (1). Nevertheless, due to the anisotropic topology of the WSN considered here, errors could be too large if we fall in a situation such as that in Figure 2. Consequently, a threshold on $e_{k-j}$ is required to guarantee some reliability of the jth anchor with respect to the kth anchor. If the topology of the WSN was isotropic, the estimation error of the distance between these anchors would be

$$\begin{array}{cc}& T_{\mathrm{1}}={\widehat{d}}_{k-j}-d_{k-j}=⌈\frac{d_{k-j}}{{\bar{h}}_s}⌉{\bar{h}}_s-d_{k-j},\end{array}$$

(4)

where the second line is due to the fact that ${\widehat{d}}_{k-j}$ is obtained using (1). In (4), $⌈x⌉$ refers to the ceiling function. Thus, a distance estimation error higher than $T_{\mathrm{1}}$ occurs only if the shortest path between the kth and the jth anchors is curved due to the presence of obstacles between the two nodes. In such a case, the number of hops between the latter is much larger than $d_{k-j}/{\bar{h}}_s$ and, hence, we should have $e_{k-j}\gg T_{\mathrm{1}}$ . Therefore, we chose $T_{\mathrm{1}}$ as a threshold below/above which an anchor is deemed reliable or not, respectively. Finally, in order to ensure an accurate distance estimation, each regular node will estimate its distance only to the nearest anchor and to those rated reliable by the latter.

However, some anchors deemed reliable by the nearest anchor could be found unreliable by the regular node, since the shortest path from the latter to these anchors may be curved as shown in Figure 3. To circumvent this issue, we implement a finer selection at the regular node that discards each anchor having a number of hops larger than $T_{\mathrm{2}}=⌈\sqrt{\mathrm{2}S}/R⌉$ . Note that $T_{\mathrm{2}}$ is the maximum number of hops that may occur if the shortest path is not curved. Processing steps at the anchors and regular nodes are summarized by localization Algorithms 1 and 2, respectively.

Algorithm 1: Localization algorithm for anchor nodes.

% k refers to the kth anchor node %

$$s_k=\left\{\right\}$$

for   $$j=\mathit{1}$$ to $$N_a$$ and $$j\ne k$$   do

    $${\widehat{d}}_{k-j}=n_k\times {\stackrel{-}{h}}_s$$

    $$e_{k-j}={\widehat{d}}_{k-j}-d_{k-j}$$

   if   $$e_{k-j}\le T_{\mathrm{1}}$$   then

     $$s_k=s_k\cup \left\{j\right\}$$

   end if

end for

Broadcast the set $$s_k$$ of reliable anchors

Algorithm 2: Localization algorithm for regular nodes.

% i refers to the ith regular node %

% $$s_{k_i}$$ is the set of the reliable anchors at the nearest anchor

node from the ith regular node %

% $$s_i$$ is the new set of reliable anchors at the ith

regular node %

$$s_i=\left\{\right\}$$

$$c=\mathrm{0}$$

for   $$k\in s_{k_i}$$   do

   if   $$h_{i-k}\le T_{\mathrm{2}}$$   then

     $$s_i=s_i\cup \left\{k\right\}$$

     $$c=c+\mathrm{1}$$

   end if

end for

for   $$j=\mathrm{1}\to c$$   do

    $${\widehat{d}}_{j_i}=n_{j_i}\times {\stackrel{-}{h}}_s$$

end for

% $$j_i$$ denotes the jth reliable anchor node index in the

set $$s_i$$ %

% $${\widehat{x}}_i$$ , and $${\widehat{y}}_i$$ can be estimated using multilateration %.

Figure 3

Reliable anchors.

6. Distance Estimation Technique

We propose in this work to estimate each regular-anchor distance using (1). To this end, one should accurately derive the average hop size ${\bar{h}}_s$ between any two consecutive nodes on the shortest path between any regular and anchor nodes. Let us consider a two-hop scenario where the kth node communicates with the ith node through an intermediate node j. In what follows, we denote by Z and X the random variables that represent the distances $d_{k-j}$ and $d_{k-i}$ , respectively. In order to derive

$$\begin{array}{cc}& {\bar{h}}_s=E\left\{Z\right\},\end{array}$$

(5)

we start by deriving the conditional cumulative distribution function (CDF) $F_{Z\hspace{0.17em}|\hspace{0.17em}X}(z)$ of Z with respect to X.

6.1. Two-Dimensional (2D) Case

As can be shown from Figure 4, $Z\le z$ is guaranteed only if there are no nodes in the area $B_z=F-A_z$ where $F=D(k,R)\cap D(i,R)$ , $A_z=F\cap D(k,z)$ , and $D(·,\star )$ is the disc having the ·th node as a center and ⋆ as a radius. It is noteworthy that F is nothing but the forwarding zone area where any potential intermediate node must exist. $F_Z\left(z\right)$ can be then defined as

$$\begin{array}{cc}& F_{Z\hspace{0.17em}|\hspace{0.17em}X}\left(z\right)\left(z\right)=P\left(Z\le z\hspace{0.17em}|\hspace{0.17em}x\right)=P\left(E_{\mathrm{0}}\right),\end{array}$$

(6)

where $P(E_{\mathrm{0}})$ is the probability that the event $E_{\mathrm{0}}=\{$ no nodes in the area $B_Z\}$ occurs. Since the nodes are uniformly deployed in S, the probability of having K nodes in $B_z$ follows a binomial distribution $\mathrm{B}\mathrm{i}\mathrm{n}\left(N,p\right)$ where $p=B_z/S$ . For relatively large N and small p, it can be readily shown that $\mathrm{B}\mathrm{i}\mathrm{n}\left(N,p\right)$ can be accurately approximated by a Poisson distribution $\mathrm{P}\mathrm{o}\mathrm{i}\mathrm{s}(\lambda B_z)$ where $\lambda =N/S$ is the average nodes density in the network. Consequently, for a large number of nodes N and small p, we have

$$\begin{array}{cc}& F_{Z\hspace{0.17em}|\hspace{0.17em}X}\left(z\right)=e^{-\lambda B_z}.\end{array}$$

(7)

As can be seen from Figure 4, $F=\mathrm{4}{A}_{\mathrm{S}\mathrm{e}\mathrm{c}-\mathrm{T}\mathrm{r}}$ where $A_{\mathrm{S}\mathrm{e}\mathrm{c}-\mathrm{T}\mathrm{r}}$ is the green sector area minus the dashed triangle area. Please note that this equality holds only when the two circles have the same radius R (i.e., the kth and jth nodes have the same transmission capability). F is then given by

$$\begin{array}{cc}& F=\mathrm{2}\left(R^{\mathrm{2}}\theta -a\times h\right)=\mathrm{2}{R}^{\mathrm{2}}\left(\theta -\frac{\text{sin}\left(\mathrm{2}\theta \right)}{\mathrm{2}}\right).\end{array}$$

(8)

Following the same approach as above, $A_z$ can be obtained as

$$\begin{array}{cc}& A_z=z^{\mathrm{2}}\left({\theta }_z-\frac{\text{sin}\left(\mathrm{2}{\theta }_z\right)}{\mathrm{2}}\right)+R^{\mathrm{2}}\left({\theta }_z^{\prime }-\frac{\text{sin}\left(\mathrm{2}{\theta }_z^{\prime }\right)}{\mathrm{2}}\right).\end{array}$$

(9)

Furthermore, using some geometrical properties, we easily show that

$$\begin{array}{cc}& {\theta }_z=\sqrt{\frac{z+R\left(\mathrm{1}-\mathrm{2}\text{cos}\left(\theta \right)\right)}{\mathrm{2}R\left(\mathrm{1}-\text{cos}\left(\theta \right)\right)}}\theta ,\\ {\theta }_z^{\prime }=\sqrt{\frac{R-z}{\mathrm{2}R\left(\mathrm{1}-\text{cos}\left(\theta \right)\right)}}\theta .\end{array}$$

(10)

Substituting (10) into (9) and using (8), we have

$$\begin{array}{l}{B}_z=R^{\mathrm{2}}\left(\mathrm{2}\theta -\text{sin}\left(\mathrm{2}\theta \right)-{\theta }_z^{\prime }+\frac{\text{sin}\left(\mathrm{2}{\theta }_z^{\prime }\right)}{\mathrm{2}}\right)\\ -z^{\mathrm{2}}\left({\theta }_z-\frac{\text{sin}\left(\mathrm{2}{\theta }_z\right)}{\mathrm{2}}\right).\end{array}$$

(11)

Substituting (11) into (7) and using the resulting CDF to compute the mean of the random variable Z yields to

$$\begin{array}{cc}& {\bar{h}}_s^{\mathrm{2}\mathrm{D}}=R-\frac{\mathrm{3}}{\pi }{{\displaystyle \int }}_{\mathrm{0}}^{\pi /\mathrm{3}}{{\displaystyle \int }}_{\mathrm{0}}^R{e}^{-\lambda B_z}dz\hspace{0.17em}d\theta .\end{array}$$

(12)

Note in (12) that we use the fact that $\theta \in [\mathrm{0},\pi /\mathrm{3}]$ since $\theta =\text{arccos}(x/\mathrm{2}R)$ where $x\in \mathrm{\hspace{0.17em}\hspace{0.17em}}]R,\mathrm{2}R]$ . It follows from (12) that ${\bar{h}}_s^{\mathrm{2}\mathrm{D}}$ increases with the nodes density λ. This is expected since it is very likely that the per-hop distance increases when the number of nodes located inside F increases if, of course, R is fixed. From (12), ${\bar{h}}_s^{\mathrm{2}\mathrm{D}}$ is also an increasing function of R. Figure 5 plots ${\bar{h}}_s^{\mathrm{2}\mathrm{D}}$ versus λ for different values of R. From this figure, the analytical ${\bar{h}}_s^{\mathrm{2}\mathrm{D}}$ approaches its empirical counterpart for small λ while the two curves almost coincide when the latter is large. This is expected since the approximation of $\mathrm{B}\mathrm{i}\mathrm{n}\left(N,p\right)$ by $\mathrm{P}\mathrm{o}\mathrm{i}\mathrm{s}\left(\lambda F\right)$ becomes more accurate as λ grows large. Figure 5 also shows that ${\bar{h}}_s^{\mathrm{2}\mathrm{D}}$ increases with λ and R, which corroborates the above discussion.

Figure 4

2D distance analysis.

Figure 5

Analytical and empirical results of ${\bar{h}}_s^{\mathrm{2}\mathrm{D}}$ .

6.2. Three-Dimensional (3D) Case

Since each node is able to communicate with any other node located at most at R meters from it, its transmission coverage in the 3D case is spherical. Let us denote by V the forwarding zone defined as $V=S(k,R)\cap S(i,R)$ where $S(·,\star )$ is the sphere having the ·th node as a center and ⋆ as a radius. In 3D case, the CDF $F_{Z\hspace{0.17em}|\hspace{0.17em}X}\left(z\right)$ is then given by

$$\begin{array}{cc}& F_{Z\hspace{0.17em}|\hspace{0.17em}X}\left(z\right)=e^{-{\lambda }_v\left(V-V_z\right)},\end{array}$$

(13)

where $V_z=S(k,z)\cap S(i,R)$ , ${\lambda }_v=N/V_T$ , and $V_T$ is the total volume where the WSN is deployed. As can be shown from Figure 6, $V=\mathrm{2}{V}_c$ where $V_c$ is the volume of the spherical cap with height

$$\begin{array}{cc}& h=\frac{\mathrm{2}R-x}{\mathrm{2}}.\end{array}$$

(14)

Therefore, V is given by

$$\begin{array}{cc}& V=\frac{\mathrm{1}}{\mathrm{12}}\pi {\left(\mathrm{2}R-x\right)}^{\mathrm{2}}\left(\mathrm{4}R+x\right).\end{array}$$

(15)

As far as $V_z$ is concerned, from Figure 6, it is the sum of the volumes of two spherical caps with heights

$$\begin{array}{cc}& h_{z\mathrm{1}}=\frac{\left(R-z+x\right)\left(R+z-x\right)}{\mathrm{2}x},\\ h_{z\mathrm{2}}=\frac{\left(R-x+z\right)\left(-R+x+z\right)}{\mathrm{2}x}.\end{array}$$

(16)

$V_z$ is then given by

$$\begin{array}{l}{V}_z\\ =\frac{\pi {\left(R-x+z\right)}^{\mathrm{2}}\left(\left(x-z\right)\left(x+\mathrm{3}z\right)+\mathrm{2}R\left(x+\mathrm{3}z\right)-\mathrm{3}{R}^{\mathrm{2}}\right)}{\mathrm{12}x}.\end{array}$$

(17)

Substituting (15) and (17) into (13) and using the resulting CDF, we obtain

$$\begin{array}{cc}& {\bar{h}}_s^{\mathrm{3}\mathrm{D}}=R-\frac{\mathrm{1}}{R}{{\displaystyle \int }}_R^{\mathrm{2}R}{{\displaystyle \int }}_{\mathrm{0}}^R{e}^{-{\lambda }_v\left(V-V_z\right)}dz\hspace{0.17em}dx.\end{array}$$

(18)

From (18), ${\bar{h}}_s^{\mathrm{3}\mathrm{D}}$ is an increasing function of ${\lambda }_v$ and R. This observation is further verified by the empirical results in Figure 7.

Figure 6

3D distance analysis.

Figure 7

Analytical and empirical results of ${\bar{h}}_s^{\mathrm{3}\mathrm{D}}$ .

7. Power Saving Mechanism

In order to provide the required operational power, WSN nodes are usually equipped with batteries or energy harvesting devices. However, the batteries have a very limited capacity while energy harvesting using the technologies so far developed is not only very expensive, especially if embedded in large scale WSNs but also unable to provide the sufficient amount of energy. This makes power saving a crucial mechanism in WSNs. If such a mechanism is not taken into account during the localization process, it may hinder localization accuracy. In what follows, we will show how a power saving mechanism could be easily incorporated in our proposed localization algorithm. Although several power saving mechanisms exist in the literature, we are only concerned in this paper by the most basic mechanism which consists in switching periodically each node between the awake (i.e., power on) and the sleep (i.e., power off) states to save power and, hence, increase the WSN lifetime. Using this mechanism, the time is equally divided into cycles where each node independently decides whether to be awake or asleep. This causes the randomization of the number of available (i.e, in the awake state) nodes assumed to be equal to N in (12) and (18) may hinder localization accuracy. To circumvent this issue, we propose to substitute N in these two equations by the average number of available nodes $N_{\mathrm{a}\mathrm{v}}$ . Assuming that the time required to perform the proposed algorithm does not exceed one cycle, $N_{\mathrm{a}\mathrm{v}}$ is given by

$$\begin{array}{cc}& N_{\mathrm{a}\mathrm{v}}={\displaystyle \sum }_{i=\mathrm{1}}^N{p}_i^{\mathrm{a}\mathrm{w}},\end{array}$$

(19)

where $p_i^{\mathrm{a}\mathrm{w}}$ is the probability that the ith node is in the awake state. If this probability is the same across the network (i.e., $p_i^{\mathrm{a}\mathrm{w}}=p^{\mathrm{a}\mathrm{w}}$ , $i=\mathrm{1},\dots ,N$ ), $N_{\mathrm{a}\mathrm{v}}$ would be reduced to $N{p}_i^{\mathrm{a}\mathrm{w}}$ . Using the latter result in (12) and (18) yields to

$$\begin{array}{cc}& {\bar{h}}_s^{\mathrm{2}\mathrm{D}}=R-\frac{\mathrm{3}}{\pi }{{\displaystyle \int }}_{\mathrm{0}}^{\pi /\mathrm{3}}{{\displaystyle \int }}_{\mathrm{0}}^R{e}^{-\lambda p^{\mathrm{a}\mathrm{w}}{B}_z}dz\hspace{0.17em}d\theta ,\end{array}$$

(20)

$$\begin{array}{cc}& {\bar{h}}_s^{\mathrm{3}\mathrm{D}}=R-\frac{\mathrm{1}}{R}{{\displaystyle \int }}_R^{\mathrm{2}R}{{\displaystyle \int }}_{\mathrm{0}}^R{e}^{-{\lambda }_v{p}^{\mathrm{a}\mathrm{w}}\left(V-V_z\right)}dz\hspace{0.17em}dx,\end{array}$$

(21)

respectively.

8. Simulations Results

In this section, we evaluate by simulations the performance of the proposed algorithm in terms of localization accuracy using Matlab. These simulations are conducted to compare, under the same network settings, the proposed algorithm with some of the best representative localization algorithms currently available in the literature, that is, DV-Hop [7], RAL [21], and pattern-driven [20]. Simulations are run both in 2D and 3D cases. In the 2D case, nodes are assumed to be uniformly deployed in a square area $S=\mathrm{1}{\mathrm{0}}^{\mathrm{4}}$  m² and in a cubic volume $V=\mathrm{1}{\mathrm{0}}^{\mathrm{4}}$  m³ in the 2D and 3D cases, respectively. Besides the C-shaped network topology in Figure 1, we consider two other anisotropic topologies commonly used in the context of WSN: W-shaped and S-shaped topologies as depicted in Figures 8(a) and 8(b), respectively.

Figure 8

Anisotropic WSN topologies.

As an evaluation criterion, we propose to use the normalized root mean square error (NRMSE) defined as follows:

$$\begin{array}{cc}& e=\frac{{\sum }_{i=\mathrm{1}}^{N_u}\sqrt{{\left(x_i-{\widehat{x}}_i\right)}^{\mathrm{2}}+{\left(y_i-{\widehat{y}}_i\right)}^{\mathrm{2}}}}{N_{u}R}.\end{array}$$

(22)

All the following results are obtained by averaging over 100 trials.

Figure 9 plots the localization NRMSE achieved by DV-Hop, RAL, pattern-driven, and our proposed algorithm versus the node density with a constant number of anchors set to be 20 in C-, W-, and S-shaped network topologies. Figures 9(a), 9(c), and 9(e) provide the results of the 2D case, while Figures 9(b), 9(d), and 9(f) provide those of the 3D case. As can be shown from these figures, the proposed algorithm always outperforms its counterparts. Indeed, in the 2D case (3D case), it is up to about 80% (180%), 70% (100%), and 60% (60%) more accurate than DV-Hop, RAL, and pattern-driven, respectively. Furthermore, our algorithm achieves almost the same performance in the three network topologies while DV-Hop's, RAL's, and pattern-driven's performance, which are already poor in the C-shaped topology, severely deteriorate in the W-shaped topology, more so in the S-shaped topology.

Figure 9

Localization NRMSE versus node density with $N_a=\mathrm{20}$ in C-, W-, and S-shaped network topologies in 2D and 3D cases.

Figure 10 shows the NRMSEs’ standard deviations achieved by all localization algorithms for different node densities in the C-, W-, and S-shaped network topologies. Figures 10(a), 10(c), and 10(e) provide the results of the 2D case, while Figures 10(b), 10(d), and 10(f) provide those of the 3D case. As can be seen from these figures, the NRMSEs’ standard deviations achieved by DV-Hop, RAL, and pattern-driven slightly decrease when the node density increases while the one achieved by the proposed algorithm substantially decreases. This means that implementing our algorithm in any network topology guarantees an accurate localization for any given realization. This result is very interesting in terms of implementation strategy, since it proves that the result in Figure 9 becomes more and more meaningful as λ grows large.

Figure 10

Localization NRMSE's standard deviation versus node density with $N_a=20$ in C-, W-, and S-shaped network topologies for 2D and 3D cases.

Figure 11 illustrates the localization NRMSE's CDF achieved by DV-Hop, RAL, pattern-driven, and our proposed algorithm with $N=\mathrm{200}$ and $N_a=\mathrm{20}$ in the C-, W-, and S-shaped network topologies. Figures 11(a), 11(c), and 11(e) provide the results of the 2D case, while Figures 11(b), 11(d), and 11(f) provide those of the 3D case. Using the proposed algorithm, up to 80% (90%) of the regular nodes could estimate their position within twice the transmission range in the 2D case (3D case). In contrast, up to 38% (10%) and 42% (60%) of the nodes achieve the same accuracy with RAL and pattern-driven, respectively, and about 0% (10%) with DV-Hop. This further proves the efficiency of our new algorithm.

Figure 11

Localization NRMSE's CDF with $N=200$ and $N_a=20$ in C-, W-, and S-shaped network topologies in 2D and 3D cases.

Figure 12 plots the localization NRMSEs achieved by our proposed algorithm and its counterparts versus the anchors number with $N=\mathrm{200}$ in the C-, W-, and S-shaped network topologies in both 2D and 3D cases. As can be observed from this figure, all algorithms become more accurate as the number of anchors in the network increases. From Figure 12, the NRMSE achieved by the proposed algorithm decreases more rapidly than those achieved by DV-Hop, RAL, and pattern-driven. This is expected since the number of potentially reliable anchors increases with the total number of anchors and, hence, localization is more accurate. This is in contrast with DV-Hop in which each regular node estimates its distance to all anchors (i.e., even those with curved shortest path) in the network, thereby hindering localization accuracy. The fact that the NRMSE achieved by the proposed algorithm decreases more rapidly than that achieved by pattern-driven and RAL proves that our anchors selection strategy is more reliable and efficient than that in [20, 21].

Figure 12

Localization NRMSE versus anchors number with $N=\mathrm{200}$ in C-, W-, and S-shaped network topologies in 2D and 3D cases.

Figure 13 displays the localization NRMSEs achieved by the proposed algorithm and its counterparts versus $p^{\mathrm{a}\mathrm{w}}$ in the C-, W-, and S-shaped network topologies in both 2D and 3D cases. As can be observed from this figure, localization accuracy of each algorithm improves when $p^{\mathrm{a}\mathrm{w}}$ increases. This is expected since the number of potentially available nodes increases with $p^{\mathrm{a}\mathrm{w}}$ and, hence, the nodes density increases. Furthermore, from Figure 13, if the proposed algorithm accounts for the power saving mechanism, its achieved NRMSE remains almost constant when $p^{\mathrm{a}\mathrm{w}}$ increases. This highlights another advantage of our algorithm over its counterparts, namely, its ability to efficiently incorporate a power saving mechanism.

Figure 13

Localization NRMSE versus $p^{\mathrm{a}\mathrm{w}}$ in C-, W-, and S-shaped network topologies in 2D and 3D cases.

Figure 15 plots the localization NRMSEs achieved by the proposed algorithm and its counterparts versus the nodes density with different anchors placement strategies: perimeter, grid, and random as depicted in Figures 14(a), 14(b), and 8, respectively. This figure shows that the grid anchors’ placement is the most efficient strategy in W- and S-shaped topology while the random anchors’ placement is the best in the C-shaped topologies. This result is very interesting since it proves that the performance of each strategy is closely related to the network topology. In other words, if the latter is known beforehand, we will be able to select the appropriate strategy when deploying the WSN.

Figure 14

Anchors’ placements illustrated C-shaped topology.

Figure 15

Proposed algorithm's NRMSE versus anchors’ placements in C-, W-, and S-shaped network topologies in 2D and 3D cases.

Figures 16 and 17 plot the localization NRMSEs achieved by the proposed algorithm and its counterparts versus the nodes density and the degree of range irregularity (DoI), respectively. In Figure 16, a nonuniform nodes’ deployment is assumed while in Figure 17 the transmission range is no longer assumed circular. A range irregularity model similar to that in [23] was implemented instead. From these figures, the localization NRMSEs achieved by all algorithms deteriorate due to both nonuniform nodes’ deployment and range irregularity. This is expected since these phenomena are not taken into account when designing the proposed algorithm and its counterparts. However, as could be observed from Figures 16 and 17, the proposed algorithm remains more accurate than its counterparts. This further proves the increased robustness of our proposed algorithm to model imperfections.

Figure 16

Localization NRMSE with $N_a=20$ assuming nonuniform nodes’ deployment in C-, W-, and S-shaped network topologies in 2D and 3D cases.

Figure 17

Localization NRMSE versus DOI with $N=200$ and $N_a=20$ in C-, W-, and S-shaped network topologies in 2D and 3D cases.

9. Conclusion

In this paper, we proposed a novel range-free localization algorithm tailored for anisotropic WSNs. Using the proposed algorithm, each regular node estimates its distances to reliable anchors only. The latter are properly chosen following a new reliable anchor selection strategy that ensures an accurate distance estimation thereby making our localization algorithm more precise. New average hop sizes’ expressions were also developed in this paper for both 2D and 3D scenarios. We showed that the obtained expressions are very accurate especially for high nodes densities. Furthermore, a power saving mechanism aiming to enhance the WSN lifetime was envisaged. We proved that our proposed algorithm could easily incorporate such a mechanism. Simulations showed that our algorithm, whether combined or not with the power saving mechanism, consistently outperforms the best representative range-free localization algorithms currently available in the literature in terms of accuracy, even with the presence of nonuniform node distribution or radiation irregularities.