# Accurate Nodes Localization in Anisotropic Wireless Sensor Networks

Authors: Ahmad El Assaf; Slim Zaidi; Sofiène Affes; Nahi Kandil
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## 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.


---

## Body

## 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: Section2 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

Figure1 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 Na and Nu=N-Na denote the number of anchors and regular nodes, respectively. Without loss of generality, let xi,yi, i=1,…,Na, be the coordinates of the anchor nodes and xi,yi, i=Na+1,…,N, those of the regular ones.Figure 1
Network model (C-shaped topology).


## 3. Related Works and Motivation

In order to localize theith regular node (i.e., (Na+i)th node), the distances between it and at least 3 anchors are usually required. The kth anchor should then broadcast its coordinates xk,yk 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 nk=1 hop. Otherwise, it receives them after nk>1 hops. So far, in most previous algorithms, the ith regular node estimates its distance to the kth anchor dk-(Na+i) using only the information nk as(1)d^k-Na+i=nkh¯s,where h¯s is a predefined average hop size. Note that this distance estimation approach relies on the fact that, in highly dense WSNs,(2)dk-Na+i≈∑l=1nkhlholds. In (2), hl is the lth hop’s distance. h¯s is usually derived either analytically (i.e., h¯s=Ehl) 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:(3)h¯s=1NaNa-1∑k=1Na∑j=1Nadk-jnk,j,where nk,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 A1 through n1=6 hops. Its distance estimate to this anchor d^k-(Na+1) is derived using (1). As can be seen from Figure 2, if the blue obstacle does not exist, n1 would be much less than 6 and, hence, the distance from i to A1 is overestimated. Thus, using d^k-(Na+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, thekth anchor broadcasts through the network a message containing (xk,yk,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 nk=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 nk, the node updates nk to n, increases it by 1, and then broadcasts the resulting message. If nk 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 sk. The kth anchor then broadcasts sk over the network. Upon reception of all xk,yk,nk,sk, k=1,…,Na, each regular node estimates its distance only to its nearest anchor (i.e, k0=arg⁡minknk) and to the reliable anchors in the set sk0. 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, thekth 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 ek-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 ek-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(4)T1=d^k-j-dk-j=dk-jh¯sh¯s-dk-j,where the second line is due to the fact that d^k-j is obtained using (1). In (4), x refers to the ceiling function. Thus, a distance estimation error higher than T1 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 dk-j/h¯s and, hence, we should have ek-j≫T1. Therefore, we chose T1 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 Figure3. To circumvent this issue, we implement a finer selection at the regular node that discards each anchor having a number of hops larger than T2=2S/R. Note that T2 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
=
for  j=1 to Na and j≠k  do
d^k-j=nk×h-s
ek-j=d^k-j-dk-j
if  ek-j≤T1  then
sk=sk∪j
end if
end for
Broadcast the setsk of reliable anchorsAlgorithm 2:Localization algorithm for regular nodes.
%i refers to the ith regular node %
%ski is the set of the reliable anchors at the nearest anchor
node from theith regular node %
%si is the new set of reliable anchors at the ith
regular node %
s
i
=
c
=
0
for  k∈ski  do
if  hi-k≤T2  then
si=si∪k
c=c+1
end if
end for
for  j=1→c  do
d^ji=nji×h-s
end for
%ji denotes the jth reliable anchor node index in the
setsi %
%x^i, and 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 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 dk-j and dk-i, respectively. In order to derive(5)h¯s=EZ,we start by deriving the conditional cumulative distribution function (CDF) FZ∣X(z) of Z with respect to X.


### 6.1. Two-Dimensional (2D) Case

As can be shown from Figure4, Z≤z is guaranteed only if there are no nodes in the area Bz=F-Az where F=D(k,R)∩D(i,R), Az=F∩D(k,z), and D(·,⋆) 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. FZz can be then defined as(6)FZ∣Xzz=PZ≤z∣x=PE0,where P(E0) is the probability that the event E0={no nodes in the area BZ} occurs. Since the nodes are uniformly deployed in S, the probability of having K nodes in Bz follows a binomial distribution BinN,p where p=Bz/S. For relatively large N and small p, it can be readily shown that BinN,p can be accurately approximated by a Poisson distribution Pois(λBz) where λ=N/S is the average nodes density in the network. Consequently, for a large number of nodes N and small p, we have(7)FZ∣Xz=e-λBz.As can be seen from Figure 4, F=4ASec-Tr where ASec-Tr 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(8)F=2R2θ-a×h=2R2θ-sin⁡2θ2.Following the same approach as above, Az can be obtained as(9)Az=z2θz-sin⁡2θz2+R2θz′-sin⁡2θz′2.Furthermore, using some geometrical properties, we easily show that(10)θz=z+R1-2cos⁡θ2R1-cos⁡θθ,θz′=R-z2R1-cos⁡θθ.Substituting (10) into (9) and using (8), we have(11)Bz=R22θ-sin⁡2θ-θz′+sin⁡2θz′2-z2θz-sin⁡2θz2.Substituting (11) into (7) and using the resulting CDF to compute the mean of the random variable Z yields to(12)h¯s2D=R-3π∫0π/3∫0Re-λBzdzdθ.Note in (12) that we use the fact that θ∈[0,π/3] since θ=arccos⁡(x/2R) where x∈]R,2R]. It follows from (12) that h¯s2D 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), h¯s2D is also an increasing function of R. Figure 5 plots h¯s2D versus λ for different values of R. From this figure, the analytical h¯s2D approaches its empirical counterpart for small λ while the two curves almost coincide when the latter is large. This is expected since the approximation of BinN,p by PoisλF becomes more accurate as λ grows large. Figure 5 also shows that h¯s2D increases with λ and R, which corroborates the above discussion.Figure 4
2D distance analysis.Figure 5
Analytical and empirical results ofh¯s2D.


### 6.2. Three-Dimensional (3D) Case

Since each node is able to communicate with any other node located at most atR 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)∩S(i,R) where S(·,⋆) is the sphere having the ·th node as a center and ⋆ as a radius. In 3D case, the CDF FZ∣Xz is then given by(13)FZ∣Xz=e-λvV-Vz,where Vz=S(k,z)∩S(i,R), λv=N/VT, and VT is the total volume where the WSN is deployed. As can be shown from Figure 6, V=2Vc where Vc is the volume of the spherical cap with height(14)h=2R-x2.Therefore, V is given by(15)V=112π2R-x24R+x.As far as Vz is concerned, from Figure 6, it is the sum of the volumes of two spherical caps with heights(16)hz1=R-z+xR+z-x2x,hz2=R-x+z-R+x+z2x.Vz is then given by(17)Vz=πR-x+z2x-zx+3z+2Rx+3z-3R212x.Substituting (15) and (17) into (13) and using the resulting CDF, we obtain(18)h¯s3D=R-1R∫R2R∫0Re-λvV-Vzdzdx.From (18), h¯s3D is an increasing function of λ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 ofh¯s3D.


## 6.1. Two-Dimensional (2D) Case

As can be shown from Figure4, Z≤z is guaranteed only if there are no nodes in the area Bz=F-Az where F=D(k,R)∩D(i,R), Az=F∩D(k,z), and D(·,⋆) 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. FZz can be then defined as(6)FZ∣Xzz=PZ≤z∣x=PE0,where P(E0) is the probability that the event E0={no nodes in the area BZ} occurs. Since the nodes are uniformly deployed in S, the probability of having K nodes in Bz follows a binomial distribution BinN,p where p=Bz/S. For relatively large N and small p, it can be readily shown that BinN,p can be accurately approximated by a Poisson distribution Pois(λBz) where λ=N/S is the average nodes density in the network. Consequently, for a large number of nodes N and small p, we have(7)FZ∣Xz=e-λBz.As can be seen from Figure 4, F=4ASec-Tr where ASec-Tr 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(8)F=2R2θ-a×h=2R2θ-sin⁡2θ2.Following the same approach as above, Az can be obtained as(9)Az=z2θz-sin⁡2θz2+R2θz′-sin⁡2θz′2.Furthermore, using some geometrical properties, we easily show that(10)θz=z+R1-2cos⁡θ2R1-cos⁡θθ,θz′=R-z2R1-cos⁡θθ.Substituting (10) into (9) and using (8), we have(11)Bz=R22θ-sin⁡2θ-θz′+sin⁡2θz′2-z2θz-sin⁡2θz2.Substituting (11) into (7) and using the resulting CDF to compute the mean of the random variable Z yields to(12)h¯s2D=R-3π∫0π/3∫0Re-λBzdzdθ.Note in (12) that we use the fact that θ∈[0,π/3] since θ=arccos⁡(x/2R) where x∈]R,2R]. It follows from (12) that h¯s2D 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), h¯s2D is also an increasing function of R. Figure 5 plots h¯s2D versus λ for different values of R. From this figure, the analytical h¯s2D approaches its empirical counterpart for small λ while the two curves almost coincide when the latter is large. This is expected since the approximation of BinN,p by PoisλF becomes more accurate as λ grows large. Figure 5 also shows that h¯s2D increases with λ and R, which corroborates the above discussion.Figure 4
2D distance analysis.Figure 5
Analytical and empirical results ofh¯s2D.


## 6.2. Three-Dimensional (3D) Case

Since each node is able to communicate with any other node located at most atR 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)∩S(i,R) where S(·,⋆) is the sphere having the ·th node as a center and ⋆ as a radius. In 3D case, the CDF FZ∣Xz is then given by(13)FZ∣Xz=e-λvV-Vz,where Vz=S(k,z)∩S(i,R), λv=N/VT, and VT is the total volume where the WSN is deployed. As can be shown from Figure 6, V=2Vc where Vc is the volume of the spherical cap with height(14)h=2R-x2.Therefore, V is given by(15)V=112π2R-x24R+x.As far as Vz is concerned, from Figure 6, it is the sum of the volumes of two spherical caps with heights(16)hz1=R-z+xR+z-x2x,hz2=R-x+z-R+x+z2x.Vz is then given by(17)Vz=πR-x+z2x-zx+3z+2Rx+3z-3R212x.Substituting (15) and (17) into (13) and using the resulting CDF, we obtain(18)h¯s3D=R-1R∫R2R∫0Re-λvV-Vzdzdx.From (18), h¯s3D is an increasing function of λ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 ofh¯s3D.


## 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 toN 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 Nav. Assuming that the time required to perform the proposed algorithm does not exceed one cycle, Nav is given by(19)Nav=∑i=1Npiaw,where piaw is the probability that the ith node is in the awake state. If this probability is the same across the network (i.e., piaw=paw, i=1,…,N), Nav would be reduced to Npiaw. Using the latter result in (12) and (18) yields to(20)h¯s2D=R-3π∫0π/3∫0Re-λpawBzdzdθ,(21)h¯s3D=R-1R∫R2R∫0Re-λvpawV-Vzdzdx,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=104 m2 and in a cubic volume V=104 m3 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.
(a)
W-shaped network topology
(b)
S-shaped network topologyAs an evaluation criterion, we propose to use the normalized root mean square error (NRMSE) defined as follows:(22)e=∑i=1Nuxi-x^i2+yi-y^i2NuR.All the following results are obtained by averaging over 100 trials.Figure9 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 withNa=20 in C-, W-, and S-shaped network topologies in 2D and 3D cases.
(a)
C-shape
(b)
C-shape
(c)
W-shape
(d)
W-shape
(e)
S-shape
(f)
S-shapeFigure10 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 withNa=20 in C-, W-, and S-shaped network topologies for 2D and 3D cases.
(a)
C-shape
(b)
C-shape
(c)
W-shape
(d)
W-shape
(e)
S-shape
(f)
S-shapeFigure11 illustrates the localization NRMSE’s CDF achieved by DV-Hop, RAL, pattern-driven, and our proposed algorithm with N=200 and Na=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 withN=200 and Na=20 in C-, W-, and S-shaped network topologies in 2D and 3D cases.
(a)
C-shape
(b)
C-shape
(c)
W-shape
(d)
W-shape
(e)
S-shape
(f)
S-shapeFigure12 plots the localization NRMSEs achieved by our proposed algorithm and its counterparts versus the anchors number with N=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 withN=200 in C-, W-, and S-shaped network topologies in 2D and 3D cases.
(a)
C-shape
(b)
C-shape
(c)
W-shape
(d)
W-shape
(e)
S-shape
(f)
S-shapeFigure13 displays the localization NRMSEs achieved by the proposed algorithm and its counterparts versus paw 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 paw increases. This is expected since the number of potentially available nodes increases with paw 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 paw 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 versuspaw in C-, W-, and S-shaped network topologies in 2D and 3D cases.
(a)
C-shape
(b)
C-shape
(c)
W-shape
(d)
W-shape
(e)
S-shape
(f)
S-shapeFigure15 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.
(a)
Perimeter
(b)
GridFigure 15
Proposed algorithm’s NRMSE versus anchors’ placements in C-, W-, and S-shaped network topologies in 2D and 3D cases.
(a)
C-shape
(b)
C-shape
(c)
W-shape
(d)
W-shape
(e)
S-shape
(f)
S-shapeFigures16 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 withNa=20 assuming nonuniform nodes’ deployment in C-, W-, and S-shaped network topologies in 2D and 3D cases.
(a)
C-shape
(b)
C-shape
(c)
W-shape
(d)
W-shape
(e)
S-shape
(f)
S-shapeFigure 17
Localization NRMSE versus DOI withN=200 and Na=20 in C-, W-, and S-shaped network topologies in 2D and 3D cases.
(a)
C-shape
(b)
C-shape
(c)
W-shape
(d)
W-shape
(e)
S-shape
(f)
S-shape


## 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.



---

*Source: 105682-2015-06-02.xml*