Distributed Hybrid Localization Using RSS Threshold Based Connectivity Information and Iterative Location Update

Abstract

Resource constraints of wireless ad hoc and sensor networks prohibit high accuracy range-based localization schemes which require specialized hardware for ranging. On the other hand, cost-effective range-free schemes offer lower accuracy and grant their applicability only to large-scale networks. This paper proposes an efficient distributed hybrid solution which integrates received signal strength (RSS) based ranging and connectivity-based range-free approaches to improve the localization accuracy without any extra ranging hardware and to be adaptable to any network size. First, it configures the connectivity information using available RSS measurements and a predefined RSS threshold. Optimal RSS threshold value that minimizes the error for a particular network to be localized is derived as a function of the total number of nodes and the network size. And then, localization accuracy is further improved by introducing the use of regulated hop-count values. Finally, locations of the nodes are iteratively updated using both connectivity information and RSS-based distance information between the nodes to get more precise localization accuracy. Effectiveness of the proposed scheme is evaluated with both experiments and simulations, and results show that the proposed scheme achieves significant performance improvement over existing schemes.

1. Introduction

Accurate and low cost network localization is a critical requirement for the deployment of wireless ad hoc and sensor networks in a wide variety of location-aware applications like military battlefield awareness, habitat and environmental monitoring, health care, industrial process control, disaster relief, and target tracking. Although a large number of localization schemes [1] have been proposed so far, it is still a challenging work due to extremely limited resources available at each node. This paper aims to propose an efficient localization solution for improving the localization accuracy of wireless sensor networks without any extra hardware requirement.

Existing localization schemes can be labelled into ranging or range-based schemes [2] and range-free schemes [3] based on whether the range measurements are used or not. Ranging schemes are based on RSS [4], time-of-arrival (TOA) [5], time-differential-of-arrival (TDOA) [6], and angle-of-arrival (AOA) [7]. These kinds of localization methods give higher accuracy, but all of them except RSS-based methods require additional hardware for ranging, thus consuming more power and cost, which makes them less suitable for the resource-constrained wireless ad hoc and sensor networks. Low cost benefit of RSS has led to a number localization schemes which are based on RSS lateration [8, 9] and environmental profiling or RSS fingerprinting [10, 11] methods. However, due to the high variability of RSS, these methods require extensive channel calibrations and limit their applicability to the targeted specific network environments.

In contrast to the ranging schemes, range-free schemes determine the nodes’ locations by using the connectivity information or the number of hops between the nodes without any specific hardware support. Although they offer lower accuracy than the ranging approaches, they give low cost and less power consumption solutions. DV-HOP [12] is a well-known hop-count based scheme which relies on transforming the hop-count values between anchors and unknown nodes into distance information using the computed average size of a hop (hop-distance). A large number of DV-HOP based schemes [13–17] have been proposed to get more improved localization accuracy.

There are some other connectivity-based range-free schemes which seem more complicated but show better accuracy such as multidimensional scaling map (MDS-MAP) [18] scheme and self-organization map (SOM) based schemes. The method presented by Giorgetti et al. [19], which we name CSOM, employs the classical SOM [20] to the localization in which the SOM-winner node updates the weights (estimated locations) of its neighbors when they are found out to be outside its radio range. It uses centralized implementation and requires thousands of learning steps. Distributed SOM-based localization scheme (LS-SOM) is proposed in [21] in which each node finds incorrect location estimations of its neighbors based on whether they fall inside the radio range of their 2-hop neighbors or not. Then, the weights of neighbors with incorrect locations are updated. LS-SOM achieves performance improvement over CSOM and MDS-MAP methods with less anchor utilization.

Range-free localization schemes induce lower accuracy than range-based schemes as each node regards distance or proximity information between it and its neighbors as 1-hop (i.e., size of the radio range) although their Euclidean distances are different. In addition, existing range-free schemes demonstrate their effectiveness with simulation based performance evaluations on multihop large-scale networks using ideal disk communication model and there is still a lack of real world evaluations of them so far. More significantly, none of these researches takes into consideration the prominent error generation with small-scale networks due to the multihop nature of them.

A distributed hybrid localization scheme (H-RSSSOM) is proposed in our previous work [22] which improves the accuracy of the range-free localization by integrating the RSS-based ranging and the SOM-based range-free localization. It applies the invalid neighbor set obtained from the connectivity information of 2-hop neighbors and the RSS-based distance information in the SOM-based location learning steps. It shows preferable performance improvement over DV-HOP, CSOM, LS-SOM, and other schemes without using any extra ranging hardware. However, it also does not consider the performance degradation problem with small-scale networks.

Large error generation of localization schemes using the connectivity information with small-scale network scenarios is pointed out in our previous work [23]. Wireless modules widely used for the localization purpose in wireless ad hoc and sensor networks have the radio range capability of tens to hundred meters [24–26]. With small-scale network scenarios, every node in the network may become within the radio range of every other node (a single hop network where each node has direct communication link with all other nodes). Then, all unknown nodes are 1-hop away from all the anchors, and localization using hop-count based approaches gives similar position estimates for all the nodes and generates a large error amount. Likewise, SOM-based schemes will not update the weights of the nodes with incorrect locations since all SOM-winner nodes find all of their neighbors falling inside the radio range of them. In fact, existing cost-effective range-free solutions are applicable only to large-scale networks although location-aware applications are ranging from small-scale to large-scale scenarios. H-RSSSOM could not also show preferable accuracy although it combines both RSS-based ranging and the range-free approach since it is not available to achieve the invalid neighbor set information.

In this paper, an efficient hybrid localization scheme is proposed which addresses the aforementioned challenges and improves the localization performance with three stages. First, connectivity information of the network is configured by using the available RSS measurements and the predefined RSS threshold to make the proposed scheme robust to any network size. The optimal RSS threshold which shows the minimum amount of error for a particular network to be localized is derived as a function of the total number of nodes and the network size. Secondly, the use of regulated hop-count values is introduced to minimize the localization error due to the hop-distance ambiguity. Finally, locations of unknown nodes are estimated using the proposed iterative location update algorithm which utilizes both connectivity information and the RSS-based distance information between the nodes to get more precise localization accuracy. Experimental and simulation results indicate that the proposed scheme shows significant improvement in localization performance without any extra hardware. The rest of the paper is organized as follows. Section 2 presents the radio propagation model considered and Section 3 describes the detailed workflow of the proposed iterative localization scheme. Section 4 discusses the experimental and simulation based performance evaluations of the proposed scheme and finally in Section 5, conclusions and future considerations to our proposed scheme are presented.

2. Radio Propagation Model

Log-normal shadowing model [27] is a more general propagation model suitable for both indoor and outdoor environments. Using it, RSS can be related to the distance between the two nodes by the following expression:

$$\begin{array}{cc}& {\text{RSS}}_{ij}=P_{\text{ref}}-\mathrm{10}n{\log }_{\mathrm{10}}\left(\frac{d_{ij}}{d_{\mathrm{0}}}\right)+X_{\sigma },\end{array}$$

(1)

where $d_{ij}$ is the distance between nodes i and j, n is the path-loss exponent corresponding to the propagation channel, and $X_{\sigma }$ denotes a zero mean Gaussian random variable with standard deviation (σ) caused by shadowing. The term $P_{\text{ref}}$ is the power measured at a reference distance $d_{\mathrm{0}}$ which is set to 1 m in this paper. Then, from (1), the distance information can be estimated from ${\text{RSS}}_{ij}$ as

$$\begin{array}{cc}& d_{ij}=\mathrm{1}{\mathrm{0}}^{\left(P_{\text{ref}}-{\text{RSS}}_{ij}+X_{\sigma }\right)/\mathrm{10}n}.\end{array}$$

(2)

To determine the values of radio propagation characteristics, n and $X_{\sigma }$ , which could contribute to large signal strength variability, preliminary experiments are conducted in different propagation environments: (1) line-of-sight (LOS) environment, which is the Ritsumeikan University Gym, and (2) non-line-of-sight (NLOS) environment, which is the experiment room of Ritsumeikan University with PCs, desks, and dividers. XBee Series 2 modules [24] mounted on Arduino Uno and Arduino Wireless Shield [28], shown in Figure 1, are used in our experiments. These modules have the ability to measure RSS values of the incoming packets without any extra ranging hardware.

Figure 1

XBee Series 2 module mounted on Arduino Wireless Shield.

Transmitter and receiver are placed in different separation distances and twenty samples of RSS measurements are collected at each distance point. Resulting experimental mean RSS values for different distances are illustrated with solid lines in Figure 2.

Figure 2

RSS variation over distance.

Then, minimum mean square error (MMSE) method is applied to estimate n and $X_{\sigma }$ based on the measured experimental RSS values and the theoretical based RSS values. Let ${\text{RSS}}_i$ be the mean value of measured RSS samples at each distance point i and let ${\text{Est}}_i$ be the theoretical RSS data estimated using (1) for the same point. Then, the sum of squared errors can be obtained by

$$\begin{array}{cc}& E\left(n\right)={\displaystyle \sum }_{i=\mathrm{1}}^{\text{PT}}{\left({\text{RSS}}_i-{\text{Est}}_i\right)}^{\mathrm{2}},\end{array}$$

(3)

where PT is the total number of distance points. The value of path-loss exponent n which minimizes the squared error can be derived by equating the derivative of $E(n)$ to zero and then solving it for n. After calculating the value of n, the variance ${\sigma }^{\mathrm{2}}$ can be obtained by

$$\begin{array}{cc}& {\sigma }^{\mathrm{2}}=\frac{E\left(n\right)}{\text{PT}}.\end{array}$$

(4)

According to the mathematical formulations, with $P_{\text{ref}}$ of −40 dBm, calculated values of n and σ are 1.7 and 3.6, respectively, for LOS environment, and 2.6 and 6.2, respectively, for NLOS environment which will be utilized throughout our research in accordance with the radio propagation environment. $P_{\text{ref}}$ is determined by averaging the RSS values measured at one meter distance from a transmitter in all directions. RSS values for different distances estimated using (1) with resulting n and σ are illustrated by dotted lines in Figure 2.

3. Proposed Distributed Hybrid Localization Scheme

There are three main stages in our proposed scheme: (i) connectivity configuration stage, (ii) initial location estimation stage, and (iii) iterative location update stage.

3.1. RSS Threshold Based Connectivity Configuration Stage

In this section, the proposed RSS threshold based connectivity configuration and derivation of the optimal RSS threshold are discussed.

3.1.1. Neighborhood Definition Using the RSS Threshold

Each node i in the network broadcasts t packets from which each receiving node j  ( $j=\mathrm{1,2},\dots ,N_i$ , where $N_i$ is the total number of nodes in i's communication range) measures the RSS values. A set of RSS samples between nodes i and j, $\{{\text{RSS}}_{ij}^1,{\text{RSS}}_{ij}^2,\dots ,{\text{RSS}}_{ij}^t\}$ , are collected and the mean RSS value of these samples ( ${\text{RSS}}_{ij}$ ) is utilized to define the connectivity information $C_{ij}$ between them as follows:

$$\begin{array}{cc}& C_{ij}=\left\{\begin{array}{cc}\mathrm{0},\hfill & \text{if}\hspace{0.17em}\hspace{0.17em}{\text{RSS}}_{ij}<{\text{RSS}}_{\text{th}}\left(\text{not-connected}\right)\hfill \\ \mathrm{1},\hfill & \text{if}\hspace{0.17em}\hspace{0.17em}{\text{RSS}}_{ij}\ge {\text{RSS}}_{\text{th}}\left(\text{connected}\right),\hfill \end{array}\right.\end{array}$$

(5)

where RSS_th is the predefined RSS threshold.

According to (5), only the pair of nodes whose ${\text{RSS}}_{ij}$ value exceeds the threshold is considered as connected and regarded as neighbors in the proposed solution.

3.1.2. Optimal RSS Threshold Selection

Since RSS threshold value is a predefined parameter, which threshold value should be set becomes a question. We provide an empirical and theoretical based answer for determining the optimal RSS threshold.

Let us first clarify definitions of the connectivity used in this paper. The term “disconnected” is used when there are isolated nodes in the network, “connected” is used when every node can reach other nodes in the network via a wireless multihop path, and “fully connected” is used when every node in the network is within the radio range of other nodes and they can reach each other via a direct link.

Table 1 illustrates a list of experiment scenarios conducted for the optimal RSS threshold selection. We configure the connectivity information of the network with different RSS threshold values and estimate locations of the nodes using DV-HOP scheme to evaluate the effect of RSS threshold setting on the performance of range-free localization.

Table 1

Experiment scenarios.

Case	Environment
1	$$\mathit{7.5}\times \mathit{7.5}$$  m2 grid topology network with 36 nodes (LOS)
2	$$\mathit{15}\times \mathit{15}$$  m2 grid topology network with 36 nodes (LOS)
3	$$\mathit{25}\times \mathit{25}$$  m2 grid topology network with 36 nodes (LOS)
4	$$\mathit{7.5}\times \mathit{7.5}$$  m2 grid topology network with 36 nodes (NLOS)

Figure 3 shows the experimental results on mean localization errors using different RSS threshold values for the aforementioned scenarios in Table 1. According to the results, it is observed that when too large threshold values are used, the network becomes disconnected and locations of isolated nodes could not be estimated. It is noticeable and conclusive from the results that, for all experimental cases, minimum localization error is achieved with a threshold value at which the network becomes connected. After that, localization error increases with decreasing the threshold value and reduces to a certain error level which is the case where the network becomes fully connected.

Figure 3

Experimental results of RSS threshold setting effect for grid topology networks.

We confirm these observations with computer simulations. Simulations are conducted on the same network scenarios as in the experiments. The radio propagation environments are modelled using (1) in which the values of n and σ calculated in Section 2 are applied for the related propagation environments. According to the results in Figure 4, simulation results are highly consistent with the experimental results and the threshold values at which the network becomes connected show the minimum amount of error as in the experiments.

Figure 4

Simulation results of RSS threshold setting effect for grid topology networks.

Additionally, extensive simulations are conducted for the network scenarios shown in Table 2 to evaluate the effect of RSS threshold setting on the localization performance for random topology networks. Here, radio propagation characteristics for NLOS case are applied to model the indoor environment. It can be clearly seen from the results in Figure 5 that using RSS threshold values at which the network becomes connected give the optimal localization accuracy for all cases.

Table 2

Simulation scenarios.

Case	Environment
5	$$\mathit{40}\times \mathit{40}$$  m2 random topology network with 40 nodes
6	$$\mathit{40}\times \mathit{40}$$  m2 random topology network with 60 nodes
7	$$\mathit{40}\times \mathit{40}$$  m2 random topology network with 80 nodes
8	$$\mathit{40}\times \mathit{40}$$  m2 random topology network with 100 nodes

Figure 5

Simulation results of RSS threshold setting effect for random topology networks.

Based on these findings, we derive an approximate formula for the optimal RSS threshold $({\text{RSS}}_{\text{th-opt}})$ value from the minimum radio range required for the network to be connected. In most cases of the practical interest of localization scenarios, the total number of nodes ( $N_{\text{total}}$ ) and the area of interest (A) are the prior information. Using these information, the probabilistic bound of the radio range to avoid isolated nodes and to achieve a connected wireless ad hoc network is defined as (6) based on the mathematical derivations in [29]:

$$\begin{array}{cc}& R\ge \sqrt{\frac{-\ln (\mathrm{1}-p^{\mathrm{1}/N_{\text{total}}})}{\phi \pi }},\end{array}$$

(6)

where p is the probability that no node in the network is isolated and φ is the node density ( $\phi =N_{\text{total}}/A$ ). From (6), the lowest bound of the radio range to achieve a connected wireless ad hoc network is

$$\begin{array}{cc}& R_{\mathrm{0}}=\sqrt{\frac{-\ln (\mathrm{1}-p^{\mathrm{1}/N_{\text{total}}})}{\phi \pi }}.\end{array}$$

(7)

At this lowest bound, the network becomes connected, from which the connectivity becomes increased with increasing the radio range until the network becomes fully connected. Therefore, the optimal RSS threshold value $({\text{RSS}}_{\text{th-opt}})$ for different number of nodes and the network size is calculated from this lowest bound using

$$\begin{array}{cc}& {\text{RSS}}_{\text{th-opt}}=P_{\text{ref}}-\mathrm{10}n{\log }_{\mathrm{10}}{R}_{\mathrm{0}}.\end{array}$$

(8)

Tables 3 and 4 show the ${\text{RSS}}_{\text{th-opt}}$ values derived from (8) with $R_{\mathrm{0}}$ determined by (7) in which the probability of 99% is set (i.e., $p=0.99$ ). It means the threshold value is determined to assure that almost all the nodes in the network are connected. Apparently from the results, derived ${\text{RSS}}_{\text{th-opt}}$ values are highly consistent with those resulted from the experiment and simulation based studies illustrated in Figures 3, 4, and 5. Therefore, in our proposed scheme, the optimal RSS threshold value for a certain network scenario to be localized is first calculated using (8), and then connectivity information is configured using

$$\begin{array}{cc}& C_{ij}=\left\{\begin{array}{cc}\mathrm{0},\hfill & \text{if}\hspace{0.17em}\hspace{0.17em}{\text{RSS}}_{ij}<{\text{RSS}}_{\text{th-opt}}\left(\text{not-connected}\right),\hfill \\ \mathrm{1},\hfill & \text{if}\hspace{0.17em}\hspace{0.17em}{\text{RSS}}_{ij}\ge {\text{RSS}}_{\text{th-opt}}\left(\text{connected}\right).\hfill \end{array}\right.\end{array}$$

(9)

Table 3

$${\text{RSS}}_{\text{th-opt}}$$ values for grid topology networks.

	Case  1	Case  2	Case  3	Case  4
Derived values	−45	−50	−54	−48
Experiment	−45	−50	−53	−47
Simulation	−46	−50	−54	−47

Table 4

$${\text{RSS}}_{\text{th-opt}}$$ values for random topology networks.

	Case  5	Case  6	Case  7	Case  8
Derived values	−66	−64	−62	−61
Simulation	−66	−64	−62	−60

3.2. Initial Location Estimation Stage Using Regulated Hop-Count Values

After configuring the connectivity information, initial locations of the nodes are estimated. First, each anchor i broadcasts a packet containing anchor ID, its location ( ${\lambda }_i$ ), and the hop-count value initialized to zero. Each intermediate receiving node u determines whether the sender node j is its neighbor or not using the RSS threshold based connectivity information ( $C_{uj}$ ).

With traditional range-free schemes, if the two nodes are regarded as neighbors, distance or proximity information between them is regarded as 1-hop (i.e., size of the radio range) since the only available information is the radio range. As illustrated in Figure 6, all neighbors of anchor i (node 1 and node 2) are regarded as 1-hop away from i which leads to the same distance estimates although their Euclidean distances to i are different which could result in erroneous location estimation.

Figure 6

Sample scenario using traditional and regulated hop-count values.

In our proposed solution, if j is defined to be neighbor of u ( $C_{uj}=1$ ), u calculates the regulated hop-count between u and j ( ${\text{RH}}_{uj}$ ) using (10) to get more precise proximity information:

$$\begin{array}{cc}& {\text{RH}}_{uj}=\frac{d_{uj}}{R_{\mathrm{0}}},\end{array}$$

(10)

where $d_{uj}$ is the distance information between nodes u and j estimated using (2) based on the mean RSS measurements between them in the connectivity configuration stage and $X_{\sigma }$ of zero. By using the regulated hop-count values, more precise proximity information between neighbors can be obtained as illustrated by dotted lines in Figure 6. After that, u finds the hop-count value to the particular anchor ID in the received packet by adding ${\text{RH}}_{uj}$ with the hop-count value in the packet. If the new hop-count value is larger than old value stored at u for that anchor, u simply ignores the packet. Else, old value is replaced with the new value and u forwards the packet with the new hop-count value. After getting the location information and hop-count values of all anchors, each anchor i estimates the regulated hop-count based hop-distance value ${\text{Rhdist}}_i$ using

$$\begin{array}{cc}& {\text{Rhdist}}_i=\frac{{\sum }_{k\ne i}^{}|{\lambda }_i-{\lambda }_k|}{{\sum }_{k\ne i}{\text{RH}}_{ik}},\end{array}$$

(11)

where $|{\lambda }_i-{\lambda }_k|$ is the distance between anchors i and k.

Each unknown node u uses the hop-distance value informed by nearby anchor i to estimate distance between it and other anchors using

$$\begin{array}{cc}& {\mathrm{dist}}_{uk}={\text{Rhdist}}_i*{\text{RH}}_{uk},\end{array}$$

(12)

where ${\mathrm{dist}}_{uk}$ is the distance between node u and each anchor k ( $k=1,2,\dots ,G$ , where G is the total number of anchors). Then, lateration method is applied to get initial locations of unknown nodes.

3.3. Iterative Location Update Stage

After the initial location estimation stage, locations of the nodes are iteratively updated to get more precise localization accuracy. Our proposed iterative location update algorithm is based on the RSS threshold based connectivity information and the RSS-based distance information among neighbors.

For simplicity, we use ω to represent X and Y coordinate values of two-dimensional location information ( $\omega =\left[\begin{array}{cc}X& Y\end{array}\right]$ ). Therefore, the actual locations of unknown nodes are denoted by ${\omega }_i$ ( $i=\mathrm{1,2},\dots ,N$ , where N is the total number of unknown nodes) and the estimated locations of the nodes are denoted by ${\bar{\omega }}_i$ . The update process is based on the distributed manner in which all nodes concurrently calculate their own location update without a central node in each iteration. Simplified algorithm of the proposed iterative location update is illustrated in Algorithm 1.

Algorithm 1: Iterative location update algorithm.

Stage 1: Exchange location information

Stage 2: Calculate revising vectors

for $$j=\mathit{1}$$ to $$N_i$$ do  ⊳ $$N_i$$ : number of node i's neighbors

   $$V_{ij}=\frac{d_{ij}-\left|{\bar{\omega }}_i\left(m\right)-{\bar{\omega }}_{ij}\left(m\right)\right|}{\left|{\bar{\omega }}_i(m)-{\bar{\omega }}_{ij}(m)\right|}\left({\bar{\omega }}_i(m)-{\bar{\omega }}_{ij}(m)\right)$$

end for

Stage 3: Update location

$${\bar{\omega }}_i(m+\mathrm{1})=\frac{\mathrm{1}}{N_i+\mathrm{1}}\left[{\bar{\omega }}_i\left(m\right)+{\displaystyle \sum }_{j=\mathrm{1}}^{N_i}\left(V_{ij}+{\bar{\omega }}_i\left(m\right)\right)\hspace{0.17em}\hspace{0.17em}\right]$$

$$m\leftarrow m+\mathrm{1}$$       ⊳m = current iteration number

repeat

  Stage 1 to Stage 3

until $$m⩾T$$           ⊳T = total iterations

return $${\bar{\omega }}_i(T)$$     ⊳ final location estimation for node i

First, the nodes broadcast location exchange packet so that each node i has location information ( ${\bar{\omega }}_{ij}$ ) about its neighbor j   ( $j=\mathrm{1,2},\dots ,N_i$ , where $N_i$ is the number of i's neighbors). The exchange packet contains the current iteration number (m), node ID, and its estimated location.

When location information from neighbors ( ${\bar{\omega }}_{ij}$ ) is received, distance information ( $d_{ij}$ ) between each node i and each of its neighbors j is estimated from the mean RSS measurement between them in the first stage using (2). After that, each node i with location ${\bar{\omega }}_i$ calculates the revising vector $V_{ij}$ for each neighbor j based on the estimated location of j and the RSS-based distance between them ( $d_{ij}$ ) using

$$\begin{array}{cc}& V_{ij}=\frac{d_{ij}-\left|{\bar{\omega }}_i\left(m\right)-{\bar{\omega }}_{ij}\left(m\right)\right|}{\left|{\bar{\omega }}_i\left(m\right)-{\bar{\omega }}_{ij}\left(m\right)\right|}\left({\bar{\omega }}_i\left(m\right)-{\bar{\omega }}_{ij}\left(m\right)\right),\end{array}$$

(13)

where ${\bar{\omega }}_i(m)$ and ${\bar{\omega }}_{ij}(m)$ represent the location information of node i and its neighbor j, respectively, at iteration m.

Then, these update vectors are used as guidance to update the location of node i using (14) if it is not an anchor:

$$\begin{array}{cc}& {\bar{\omega }}_i\left(m+\mathrm{1}\right)=\frac{\mathrm{1}}{N_i+\mathrm{1}}\left[{\bar{\omega }}_i\left(m\right)+{\displaystyle \sum }_{j=\mathrm{1}}^{N_i}‍\left(V_{ij}+{\bar{\omega }}_i\left(m\right)\right)\right].\end{array}$$

(14)

These processes are in a single iteration and all the nodes repeat T iterations to get higher location accuracy. Location updates obtained from the final iteration are the estimated locations of the nodes.

4. Performance Evaluations

This section provides experimental and simulation based performance evaluations of the proposed scheme. Experimental-based performance comparisons between our proposed scheme, DV-HOP, and RSS lateration based method for both LOS and NLOS environments are conducted. Figure 7 illustrates the network environments where experiments are carried out. We consider two-dimensional location estimation and the heights of the sensors are set to 70 cm. Additionally, performance of the proposed scheme is compared with LS-SOM and H-RSSSOM since they depict relatively better performance among existing schemes proposed for improving the accuracy of cost-effective connectivity-based range-free localization. Due to the real world implementation complexity of LS-SOM and H-RSSSOM, we conduct computer-based simulations to evaluate the performance of them. XBee Series 2 modules used in our experiments have the radio range capability of up to 40 m in NLOS environment and 120 m in LOS environment. Thus, these values will be utilized in the simulations to reflect the real world environment. The following mean localization error value (err) is used as a localization accuracy evaluation function:

$$\begin{array}{cc}& \mathrm{err}=\frac{\mathrm{1}}{N}{\displaystyle \sum }_{i=\mathrm{1}}^N‍\left|{\omega }_i-{\bar{\omega }}_i\right|.\end{array}$$

(15)

Figure 7

Experiment environments.

4.1. Localization Performance for Grid Topology Networks

At first, experiments are conducted in the LOS environment where 36 nodes are placed in a 25 × 25 m² grid topology as illustrated in Figure 8, which corresponds to Case 3 in Table 1. Throughout this section, actual locations of unknown nodes are marked with square symbols (■), locations of anchors with asterisk symbols (*), and estimated locations of unknown nodes with circles (∘). Metric unit of meter (m) is used in all network deployments. We first apply DV-HOP to locate the unknown nodes in the network. According to the experimental results, every node becomes within the radio range of other nodes, and in fact, similar location estimates for all unknown nodes are resulted with DV-HOP for this network scenario, giving a large localization error of 10.57 m with the standard deviation (std-dev) of 3.7, as illustrated by triangle in Figure 8.

Figure 8

Actual topology.

Figure 9 shows experimental results on the initial location estimations of the proposed scheme. The line connecting the actual location and the estimated location represents the amount of error. Due to the better integration of the RSS threshold based connectivity configuration and the regulated hop-count values, initial location estimation results of the proposed scheme achieve 38% performance improvement over DV-HOP.

Figure 9

Initial location estimation using proposed scheme ( $\mathrm{err}=6.4$  m, $\text{std-dev}=2.3$ ).

Comparison between error distributions per each node after the initial location estimation stage of the proposed scheme using the regulated hop-count values and the traditional hop-count values is illustrated in Figure 10. As we can see clearly from the results, using the traditional hop-count values shows more error amount on most nodes and 10% higher accuracy is achieved with the regulated hop-count values.

Figure 10

Error distribution per node.

Experimental result on topology regeneration after the iterative location update of the proposed scheme is illustrated in Figure 11. According to the results, our proposed scheme gives around 55% higher localization accuracy than DV-HOP. As well, it reduces a large amount of error generated by DV-HOP on most nodes as shown in Figure 12. Figure 13 illustrates the localization error per number of iterations. As we can see, localization accuracy of the proposed scheme becomes mostly stable from 20 iterations. Although localization error of 4.5 m is obtained at 100 iterations, only 4% performance improvement is achieved compared to that of 20 iterations. The higher number of iteration results in the larger communication and computation overheads. To minimize the communication and computational cost while achieving the acceptable accuracy, total iteration number of 20 is used in our experiments.

Figure 11

Location estimation using proposed scheme ( $\mathrm{err}=4.7$  m, std-dev $=2.2$ ).

Figure 12

Error distribution per node.

Figure 13

Iteration effect on mean localization error.

Simulation environment for the same network scenario shown in Figure 8 is built to evaluate the localization accuracy of LS-SOM and H-RSSSOM. Figure 14 depicts the comparison between error distributions per each node for LS-SOM, H-RSSSOM, and the proposed scheme. LS-SOM relies on finding incorrect locations of the nodes to update using the connectivity information of 2-hop neighbors. As each node becomes within the radio range of every other nodes, incorrect locations of the nodes are not updated and it could not show improvement in localization accuracy as illustrated in Figure 14. With H-RSSSOM, each node uses both the invalid neighbor set obtained from connectivity information of 2-hop neighbors and the RSS-based distance information among 1-hop neighbors to calculate revising vectors for estimating the location updates of its neighbors. Unlike LS-SOM, it updates locations of neighbors using the revising vector calculated based on RSS-based distance information, resulting in better accuracy than LS-SOM. But, it still could not achieve preferable localization accuracy since the invalid neighbor set information is not available.

Figure 14

Error distribution per node.

4.2. Localization Performance for Different Propagation Environments

To evaluate the impact of multipath fading on different environments, additional experiments are conducted in both LOS and NLOS environments (Case 1 and Case 4 in Table 1). Figures 15 and 16 plot the localization performance of the proposed scheme for the network scenarios in Case 1 and Case 4, respectively.

Figure 15

Localization error for LOS environment ( $\mathrm{err}=\mathrm{0.64}$  m, $\text{std-dev}=\mathrm{0.3}$ ).

Figure 16

Localization error for NLOS environment ( $\mathrm{err}=\mathrm{0.94}$  m, $\text{std-dev}=\mathrm{0.59}$ ).

According to the results, the proposed scheme offers 80% performance improvement over DV-HOP in LOS environment and 70% in NLOS environment since the mean error of 3.2 m ( $\text{std-dev}=\mathrm{1.1}$ ) resulted with DV-HOP for both cases. We also carry out experiments to locate the nodes in these scenarios using the RSS lateration based localization in which distance information between each unknown node and anchors is calculated based on the RSS measurements between them. Then, lateration method is applied to estimate locations of unknown nodes. Although the radio propagation characteristics derived for these network environments are utilized for estimating the distance from RSS, it still shows a large amount of error as we can see in Figure 17 since the RSS variability is typically high due to antenna orientation and radio propagation. As well, the signal strength is largely affected by obstructed materials especially in NLOS environment.

Figure 17

Performance comparison for LOS and NLOS environments.

Simulation based performance evaluations of LS-SOM and H-RSSSOM for the same network scenarios and environments are also conducted. According to the results in Figure 17, the proposed scheme shows superior performance among them in both LOS and NLOS environments since the RSS threshold based connectivity information, regulated hop-count values, and the RSS-based distance information are effectively integrated, instead of using the RSS measurement or the connectivity information itself for the localization purpose.

We also present simulation based evaluations of the proposed scheme for the same network scenarios in Figure 17. Although localization results obtained from the simulations show a small amount of higher accuracy than experimental-based evaluation results, the two results are well consistent in both LOS and NLOS environments.

4.3. Localization Performance for Random Topology Networks

We additionally conduct computer-based simulations to evaluate the effectiveness of our proposed scheme for the random topology network scenarios shown in Table 2.

For each case, ten different random topology network scenarios are generated and radio propagation environments are modelled using LOS radio propagation characteristics. Then, locations of the nodes for each scenario are estimated using the proposed scheme, LS-SOM, and H-RSSSOM. Figure 18 illustrates the performance comparisons for these random topology network scenarios in which the localization error for each case represents the mean value of localization errors of ten different network scenarios. It is noticeable from the results that the proposed scheme works well with random node placements and shows superior performance among them.

Figure 18

Performance comparison for random topology networks.

5. Conclusions

This paper proposes an efficient localization scheme consisting of three stages which improves the performance of connectivity-based localization for resource-constrained wireless ad hoc and sensor networks. Derivation of the optimal RSS threshold from the total number of nodes and the network size and configuring the connectivity using the optimal threshold in the first stage make our proposed scheme applicable to both small- and large-scale networks and minimize the prominent error amount. In the second stage, the use of regulated hop-count values in our proposed scheme reduces the localization error due to the hop-distance ambiguity problem. Integration of the RSS ranging and the connectivity-based range-free approaches in the proposed iterative location update algorithm in the third stage allows us to achieve better localization accuracy than considering the connectivity alone, as well as reducing the localization error due to high RSS variability. Experimental evaluations demonstrate that our proposed scheme significantly improves the localization accuracy without any extra hardware. In addition, simulations reveal that the proposed scheme is effective under different network configurations. With little overhead, the proposed RSS threshold based connectivity configuration can also be applied as a transparent supporting layer for any state-of-the-art hop-count or connectivity-based schemes to make them adaptable to small- to large-scale networks.

Limitation of our proposed scheme is that we consider the network environment to be static. Further consideration to our current work is to extend the proposed scheme to give high localization accuracy for the network scenarios in which there are both static and mobile nodes.