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{matrix} {RSS}_{i j} = P_{ref} - 10 n \log_{10} (\frac{d_{i j}}{d_{0}}) + X_{σ}, \end{matrix}

(1)

where

d_{i j}

is the distance between nodes i and j, n is the path-loss exponent corresponding to the propagation channel, and

X_{σ}

denotes a zero mean Gaussian random variable with standard deviation (σ) caused by shadowing. The term

P_{ref}

is the power measured at a reference distance

d_{0}

which is set to 1 m in this paper. Then, from (1), the distance information can be estimated from

{RSS}_{i j}

\begin{matrix} d_{i j} = 1 0^{(P_{ref} - {RSS}_{i j} + X_{σ}) / 10 n} . \end{matrix}

(2)

To determine the values of radio propagation characteristics, n and $X_{σ}$ , 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_{σ}$ based on the measured experimental RSS values and the theoretical based RSS values. Let ${RSS}_{i}$ be the mean value of measured RSS samples at each distance point i and let ${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{matrix} E (n) = \sum_{i = 1}^{PT} {({RSS}_{i} - {Est}_{i})}^{2}, \end{matrix}

(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

σ^{2}

can be obtained by

\begin{matrix} σ^{2} = \frac{E (n)}{PT} . \end{matrix}

(4)

According to the mathematical formulations, with $P_{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_{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 = 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, ${{RSS}_{i j}^{1}, {RSS}_{i j}^{2}, \dots, {RSS}_{i j}^{t}}$ , are collected and the mean RSS value of these samples ( ${RSS}_{i j}$ ) is utilized to define the connectivity information $C_{i j}$ between them as follows:

\begin{matrix} C_{i j} = \{\begin{cases} 0, & if {RSS}_{i j} < {RSS}_{th} (not-connected) \\ 1, & if {RSS}_{i j} \geq {RSS}_{th} (connected), \end{cases} \end{matrix}

(5)

where RSS_th is the predefined RSS threshold.

According to (5), only the pair of nodes whose ${RSS}_{i j}$ 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	$7.5 \times 7.5$ m² grid topology network with 36 nodes (LOS)
2	$15 \times 15$ m² grid topology network with 36 nodes (LOS)
3	$25 \times 25$ m² grid topology network with 36 nodes (LOS)
4	$7.5 \times 7.5$ m² 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	$40 \times 40$ m² random topology network with 40 nodes
6	$40 \times 40$ m² random topology network with 60 nodes
7	$40 \times 40$ m² random topology network with 80 nodes
8	$40 \times 40$ m² 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 $({RSS}_{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_{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{matrix} R \geq \sqrt{\frac{- \ln (1 - p^{1 / N_{total}})}{φ π}}, \end{matrix}

(6)

where p is the probability that no node in the network is isolated and φ is the node density (

φ = N_{total} / A

). From (6), the lowest bound of the radio range to achieve a connected wireless ad hoc network is

\begin{matrix} R_{0} = \sqrt{\frac{- \ln (1 - p^{1 / N_{total}})}{φ π}} . \end{matrix}

(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

({RSS}_{th-opt})

for different number of nodes and the network size is calculated from this lowest bound using

\begin{matrix} {RSS}_{th-opt} = P_{ref} - 10 n \log_{10} R_{0} . \end{matrix}

(8)

Tables 3 and 4 show the ${RSS}_{th-opt}$ values derived from (8) with $R_{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 ${RSS}_{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{matrix} C_{i j} = \{\begin{cases} 0, & if {RSS}_{i j} < {RSS}_{th-opt} (not-connected), \\ 1, & if {RSS}_{i j} \geq {RSS}_{th-opt} (connected) . \end{cases} \end{matrix}

(9)

Table 3

${RSS}_{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

${RSS}_{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 ( $λ_{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_{u j}$ ).

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_{u j} = 1$ ), u calculates the regulated hop-count between u and j ( ${RH}_{u j}$ ) using (10) to get more precise proximity information:

\begin{matrix} {RH}_{u j} = \frac{d_{u j}}{R_{0}}, \end{matrix}

(10)

where

d_{u j}

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_{σ}

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

{RH}_{u j}

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

{Rhdist}_{i}

using

\begin{matrix} {Rhdist}_{i} = \frac{\sum_{k \neq i}^{} | λ_{i} - λ_{k} |}{\sum_{k \neq i} {RH}_{i k}}, \end{matrix}

(11)

where

| λ_{i} - λ_{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{matrix} {dist}_{u k} = {Rhdist}_{i} * {RH}_{u k}, \end{matrix}

(12)

where

{dist}_{u k}

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 ( $ω = [\begin{bmatrix} X & Y \end{bmatrix}]$ ). Therefore, the actual locations of unknown nodes are denoted by $ω_{i}$ ( $i = 1,2, \dots, N$ , where N is the total number of unknown nodes) and the estimated locations of the nodes are denoted by ${\bar{ω}}_{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 = 1$ to $N_{i}$ do ⊳ $N_{i}$ : number of node i's neighbors

$V_{i j} = \frac{d_{i j} - |{\bar{ω}}_{i} (m) - {\bar{ω}}_{i j} (m)|}{|{\bar{ω}}_{i} (m) - {\bar{ω}}_{i j} (m)|} ({\bar{ω}}_{i} (m) - {\bar{ω}}_{i j} (m))$

end for

Stage 3: Update location

${\bar{ω}}_{i} (m + 1) = \frac{1}{N_{i} + 1} [{\bar{ω}}_{i} (m) + \sum_{j = 1}^{N_{i}} (V_{i j} + {\bar{ω}}_{i} (m))]$

$m \leftarrow m + 1$ ⊳m = current iteration number

repeat

Stage 1 to Stage 3

until $m ⩾ T$ ⊳T = total iterations

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

First, the nodes broadcast location exchange packet so that each node i has location information ( ${\bar{ω}}_{i j}$ ) about its neighbor j ( $j = 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{ω}}_{i j}$ ) is received, distance information ( $d_{i j}$ ) 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{ω}}_{i}$ calculates the revising vector $V_{i j}$ for each neighbor j based on the estimated location of j and the RSS-based distance between them ( $d_{i j}$ ) using

\begin{matrix} V_{i j} = \frac{d_{i j} - |{\bar{ω}}_{i} (m) - {\bar{ω}}_{i j} (m)|}{|{\bar{ω}}_{i} (m) - {\bar{ω}}_{i j} (m)|} ({\bar{ω}}_{i} (m) - {\bar{ω}}_{i j} (m)), \end{matrix}

(13)

where

{\bar{ω}}_{i} (m)

and

{\bar{ω}}_{i j} (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{matrix} {\bar{ω}}_{i} (m + 1) = \frac{1}{N_{i} + 1} [{\bar{ω}}_{i} (m) + \sum_{j = 1}^{N_{i}} ‍ (V_{i j} + {\bar{ω}}_{i} (m))] . \end{matrix}

(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{matrix} err = \frac{1}{N} \sum_{i = 1}^{N} ‍ |ω_{i} - {\bar{ω}}_{i}| . \end{matrix}

(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 ( $err = 6.4$ m, $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 ( $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 ( $err = 0.64$ m, $std-dev = 0.3$ ).

Figure 16

Localization error for NLOS environment ( $err = 0.94$ m, $std-dev = 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 ( $std-dev = 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.

Footnotes

Conflict of Interests

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

Acknowledgment

This research has been supported by Japan's Ministry of Education, Culture, Sports, Science and Technology “Global Centers of Excellence (GCOE) Program.”

References

Poovendran

Wang

C. L.

Roy

Secure Localization and Time Synchronization for Wireless Sensor and Ad Hoc Networks 2007

New York, NY, USA

Springer

Chaurasia

Analysis of range-based localization schemes in wireless sensor networks: a statistical approach

Proceedings of the 13th International Conference on Advanced Communication Technology (ICACT '11)

February 2011

Seoul, Republic of Korea

Huang

Blum

B. M.

Stankovic

J. A.

Abdelzaher

Range-free localization schemes for large scale sensor networks

Proceedings of the 9th Annual International Conference on Mobile Computing and Networking (MobiCom '03)

September 2003

81 95

2-s2.0-1542329081

Patwari

Hero

A. O.

III Perkins

Correal

N. S.

O'Dea

R. J.

Relative location estimation in wireless sensor networks

IEEE Transactions on Signal Processing 2003 51 8 2137 2148

2-s2.0-0042665374

10.1109/TSP.2003.814469

Hofmann-Wellenhof

Lichtenegger

Collins

Global Positioning System: Theory and Practice 1997 4th

New York, NY, USA

Springer

Savvides

Han

C. C.

Strivastava

M. B.

Dynamic fine-grained localization in ad-hoc networks of sensors

Proceedings of the 7th Annual International Conference on Mobile Computing and Networking

2001

166 179

10.1145/381677.381693

Niculescu

Nath

Ad hoc positioning system (APS) using AOA

Proceedings of the 22nd Annual Joint Conference on the IEEE Computer and Communications Societies (INFOCOM '03)

2003

1734 1743

2-s2.0-0041973656

Luo

O'Brien

W. J.

Julien

C. L.

Comparative evaluation of Received Signal-Strength Index (RSSI) based indoor localization techniques for construction jobsites

Advanced Engineering Informatics 2011 25 2 355 363

10.1016/j.aei.2010.09.003

2-s2.0-79954424875

Yang

Chen

Indoor localization using improved rss-based lateration methods

Proceedings of the IEEE Global Telecommunications Conference (GLOBECOM '09)

December 2009

10.1109/glocom.2009.5425237

2-s2.0-77951606407

10.

Bahl

Padmanabhan

V. N.

RADAR: an in-building RF-based user location and tracking system

Proceedings of the IEEE INFOCOM

March 2000

775 784

2-s2.0-0033872896

11.

Jiang

Guibas

Fingerprinting mobile user positions in sensor networks: attacks and countermeasures

IEEE Transactions on Parallel and Distributed Systems 2012 23 4 676 683

10.1109/tpds.2011.213

12.

Nicolescu

Nath

Ad-hoc positioning systems (APS)

Proceedings of the IEEE Global Communication Conference (GLOBECOM '01)

2001

San Antonio, Tex, USA

13.

Wang

Dong

Yan

A novel range-free localization based on regulated neighborhood distance for wireless ad hoc and sensor networks

Computer Networks 2012 56 16 3581 3593

10.1016/j.comnet.2012.07.007

2-s2.0-84866044693

14.

Niculescu

Nath

DV Based Positioning in Ad Hoc Networks

Telecommunication Systems 2003 22 1–4 267 280

10.1023/a:1023403323460

2-s2.0-0038703640

15.

M. J.

Wang

Analysis of hop-count-based source-to-destination distance estimation in wireless sensor networks with applications in localization

IEEE Transactions on Vehicular Technology 2010 59 6 2998 3011

10.1109/TVT.2010.2048346

2-s2.0-77954595516

16.

Kumar

Lobiyal

D. K.

An advanced DV-Hop localization algorithm for wireless sensor networks

Wireless Personal Communications 2013 71 2 1365 1385

10.1007/s11277-012-0880-3

2-s2.0-84879839943

17.

Liu

Luo

Long

Zhou

Improved DV-hop localization algorithm based on the ratio of distance and path length

Journal of Information and Computational Science 2012 9 7 1875 1882

2-s2.0-84864321664

18.

Shang

Ruml

Zhang

Fromherz

Localization from connectivity in sensor networks

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

10.1109/TPDS.2004.67

2-s2.0-8744271199

19.

Giorgetti

Gupta

S. K. S.

Manes

Wireless localization using self-organizing maps

Proceedings of the 6th International Symposium on Information Processing in Sensor Networks (IPSN '07)

April 2007

293 302

10.1145/1236360.1236399

2-s2.0-35348921252

20.

Kohonen

Self-Organizing Maps 2001 3rd

Berlin, Germany

Springer

21.

Tinh

P. D.

Kawai

Distributed range-free localization algorithm based on self-organizing maps

EURASIP Journal on Wireless Communications and Networking 2010 2010 315 324

692513

2-s2.0-78751534391

10.1155/2010/692513

22.

Maung

N. A. M.

Kawai

An improved hybrid localization scheme for wireless ad hoc and sensor networks

Proceedings of the IEEE 24th Annual International Symposium on Personal, Indoor, and Mobile Radio Communications (PIMRC '13)

September 2013

London, UK

3181 3185

10.1109/pimrc.2013.6666694

2-s2.0-84893252817

23.

Maung

N. A. M.

Kawai

Experimental evaluations of RSS threshold-based optimised DV-HOP localisation for wireless ad-hoc networks

Electronics Letters 2014 50 17 1246 1248

10.1049/el.2014.1541

24.

XBeeZB http://www.digi.com/

25.

CC2591, http://www.ti.com/lit/ds/symlink/cc2591.pdf

26.

MICAz: Wireless Measurement System Datasheet, Crossbow Technology

27.

Rappaport

T. S.

Wireless Communications: Principles and Practice 2002 2nd

Englewood Cliffs, NJ, USA

Prentice Hall

28.

Arduino Uno, http://arduino.cc/en/Main/arduinoBoardUno

29.

Bettstetter

On the minimum node degree and connectivity of a wireless multihop network

Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC '02)

June 2002

80 91

2-s2.0-0242696202