A Hybrid Localization Approach in 3D Wireless Sensor Network

Abstract

Location information acquisition is crucial for many wireless sensor network (WSN) applications. While existing localization approaches mainly focus on 2D plane, the emerging 3D localization brings WSNs closer to reality with much enhanced accuracy. Two types of 3D localization algorithms are mainly used in localization application: the range-based localization and the range-free localization. The range-based localization algorithm has strict requirements on hardware and therefore is costly to implement in practice. The range-free localization algorithm reduces the hardware cost but at the expense of low localization accuracy. On addressing the shortage of both algorithms, in this paper, we develop a novel hybrid localization scheme, which utilizes the range-based attribute RSSI and the range-free attribute hopsize, to achieve accurate yet low-cost 3D localization. As anchor node deployment strategy plays an important role in improving the localization accuracy, an anchor node configuration scheme is also developed in this work by utilizing the MIS (maximal independent set) of a network. With proper anchor node configuration and propagation model selection, using simulations, we show that our proposed algorithm improves the localization accuracy by 38.9% compared with 3D DV-HOP and 52.7% compared with 3D centroid.

1. Introduction

Knowing the accurate position of a certain object is crucial for many context aware applications in wireless sensor networks (WSNs), such as target tracking, geographic routing, and even energy management [1–3]. Therefore, many localization algorithms and related systems are proposed by leveraging different techniques towards the accurate and practical localization in WSNs. A detailed survey on location, localization, and localizability in WSNs can be found in [4].

The earliest attempt for 3D space localization is based on trilateration. The position of an unknown node can be determined based on the known coordinates of four reference nodes which are not in the same plane and the precise distances to them. Although absolutely accurate distances are generally unprocurable in practice, the Euclidean distance between two nodes in a wireless sensor network can be estimated by their shortest path with the per hop distance measured by received signal strength indicator (RSSI) or time difference of arrival (TDOA) or simply assumed as a constant.

With regard to the mechanisms used for estimating location in 3D environment, existing literature can be mainly grouped into two categories: range-based [5, 6] and range-free [7, 8] algorithms. The range-based algorithm is featured by the relatively high hardware requirements. Landscape-3D [9] is the first robust 3D range-based localization algorithm, in which the localization accuracy heavily relies on the expensive mobile beacon. The range-free algorithms are normally using connectivity information [10, 11] only to achieve localization, such as centralized algorithms 3D multidimensional scaling-map (3D MDS-MAP) [12], 3D DV-HOP [13], and 3D centroid [14], which are modified from 2D-plane scenarios. These approaches achieve coarse-grained localization at the cost of high computational complexity.

Recently, there has been growing interest in localization protocols that utilize the network topology characteristic [15]. CATL [12] splits the whole rugged network into several subsections and then carries out the localization in each subnetwork. It optimized the anchor node configuration to improve localization accuracy. Considering the node deployment strategy [16], the 3D range-free techniques always have strict network connectivity requirements, making them unsuitable for the large scale sensor networks.

In this paper, we propose a hybrid localization approach to overcome the shortage of range-free and range-based algorithms, by combining RSSI value and hop distance for 3D WSN localization, henceforth referred to as 3D-RDH algorithm. Our proposal utilizes the range-free technique by blending the RSS information under a proper selected model. As RSS data can be easily collected with current off-the-shelf equipment, it is the basis of many popular techniques for inferring the relative positions of the nodes in a WSN, whereas DV-HOP uses the network connectivity information to estimate unknown node location, especially considering the connectivity of 3D sensor network much higher than the 2D case. Inspired by the idea of virtual backbone [17] of a wireless sensor network, we place anchor nodes in the network based on maximum independent set (MIS) of the network to further improve the localization accuracy. Experimental results show that our proposal can achieve much higher localization accuracy compared with existing proposals.

Towards the accurate localization, a key is to identify the hybrid approach of localization and extract a graph of the network for anchor node configuration during deployment, which is, however, often impractical to achieve in reality. This is attributed to many fundamental engineering challenges as follows. Firstly, there is a lack of understanding of selecting proper localization techniques. Secondly, there are available schemes from the computer graphics community to find an independent set. They target high connectivity and low cost. The network is discrete and a sensor node can only obtain local information via message exchanges. A low communication complexity scheme to identify a MIS is necessarily required considering the limited resource of each sensor node. Lastly, since an independent set is discrete and arbitrary, it is not easy to clearly specify which nodes in a MIS can be selected as the anchor nodes. In this paper, we address the aforementioned challenges in one framework.

Our key contributions can be summarized in three key points. (i)

We develop an improved maximum independent set construction algorithm for a WSN considering communication complexity. We also prove that nodes chosen from a MIS are sufficient for anchor nodes configuration.

(ii)

A hybrid localization scheme is proposed to achieve 3D localization, which utilizes the range-based attribute RSSI to correct the range-free attribute hopsize.

(iii)

Via high fidelity simulations, we show that 3D-RDH algorithm can achieve much higher localization accuracy compared with other existing localization approaches in 3D environment.

The remainder of this paper is organized as follows. Section 2 outlines the previous algorithms carried out on DV-HOP localization and some problems of this traditional algorithm. Then the 3D-RDH algorithm is introduced in Section 3; it consists of four parts: anchor nodes deployment, RSSI model selection, the hop distance revision, and the whole procedure of the algorithm. Section 4 presents a description of the simulation scenarios and results. Algorithm performance evaluation in terms of accuracy and network connectivity is also discussed in this part. Finally, the conclusion and future work are discussed in Section 5.

2. Related Work

2.1. DV-HOP Algorithm

DV-HOP algorithm [18] is proposed by Niculescu and Nath in the Navigate project. It can be divided into three steps. Firstly, each anchor node broadcasts a beacon to be flooded throughout the network. Then all nodes can obtain the shortest hop count away from each anchor. Next, each anchor node calculates its own average single hopsize based on the following equation,

\begin{matrix} {Hopsize}_{m} = \frac{\sum ‍ \sqrt{{(x_{m} - x_{n})}^{2} + {(y_{m} - y_{n})}^{2}}}{\sum ‍ h_{n}}, \end{matrix}

(1)

and then broadcasts it to the whole network. In this formula,

(x_{m}, y_{m})

and

(x_{n}, y_{n})

are two different anchor nodes' locations, and

h_{n}

is the hop count from anchor n to m. The unknown nodes then work out the estimated physical distance between themselves and the anchor nodes based on the average hopsize. Finally, the unknown node can estimate its location by using triangulation or maximum likelihood estimates.

2.2. Problems of DV-HOP Algorithm in Real Practice

DV-HOP algorithm provides an effective localization in large scale WSNs. However, it still faces several challenges. First, the approach of accumulating the hop count is rough. DV-HOP algorithm views the hop count between arbitrary two neighboring nodes as 1, regardless of the real distance between them. Besides that, the average hopsize calculated from the rough hop count can lead to an inaccurate estimated distance between an anchor node and an unknown node. The estimated coordinates of unknown nodes may also be incorrect.

To address these challenges, there are many algorithms proposed to improve the DV-HOP algorithm in 2D environment. Literature [19] requires the anchor nodes deploying at the boundary of the network, so that the average hop distance can be improved, while literature [20] focuses on the range correction. The improved algorithm proposed in [20] enhances the localization accuracy by calculating the distance between the unknown node and anchor nodes based on multiplying the distance correction factor.

These algorithms mentioned above improve the position accuracy at the expense of localization rate and computational complexity. For example, although deploying the anchor nodes in the boundary of the network can improve the average single hop distance accuracy, the localization rate can be decreased. More importantly, although correcting the average hop distance by correction coefficient can improve the accuracy, the approach of elevating the accuracy through loop calculation may increase the computational overhead and the time complexity.

In recent years, hybrid location techniques have attracted increasing research efforts. Literature [21] is a hybrid localization algorithm based on DV-Distance and the twice-weighted centroid in WSN. It combines two range-free schemes to achieve more precise location. This approach uses the DV-Distance localization algorithm to get the cumulative distance and the rough-estimated coordinate for calculating twice-weighted factors. This algorithm can increase location accuracy by 20% compared with traditional centroid algorithm, but its experimental environment is in an ideal environment. It is not proper for the actual WSN environment. Different from [21], literature [22] utilizes the advantages of two range-based techniques. The two widely used ranging techniques are time of arrival (TOA) using ultra-wideband (UWB) and received signal strength (RSS) using WiFi signals. This approach cannot be widely used in large scale WSNs as it involves additional hardware for each node.

2.3. Anchor Nodes Placement

Only a few studies of WSN localization are focused on the anchor nodes in 3D space. How to choose and place reference nodes plays an important role in the positioning accuracy. Literature [23] shows that localization is closely related to the placement method of anchor nodes. However, those studies are based on 2D plane only. Literature [24] proves that the placement of anchor nodes has a great impact on the location performance. It however lacks further description on how to place reference nodes in 3D environment. This paper proposes an anchor nodes placement approach based on network backbone [25, 26] and designs an anchor nodes selection algorithm in order to improve the localization accuracy under the same condition.

3. 3D-RDH Algorithm

In this section, a hybrid localization approach for 3D WSN which combines the RSS data and hop distance is presented. It improves the range-free technique DV-HOP by introducing reference RSSI value to revise the hop distance. In addition, an anchor node configuration scheme and RSSI model are discussed in the proposed algorithm.

3.1. Anchor Placement

Anchor placement plays an important role in the quality of spatial localization. Inspired by virtual backbone, we deploy our anchor nodes based on the MIS of a network. Virtual backbone of a network contains backbone nodes of the network and it is used to solve the problems such as the notorious broadcast storm problem. The virtual backbone of the network can be obtained by previous algorithm [25, 27, 28]. The configuration of anchor nodes will be identified by sampling the induced topology of a MIS in the network.

3.1.1. Preliminaries

We first introduce some important notations and concepts used in the paper as follows. (i)

SUG (simple undirected graph): given a simple undirected graph $G (V, E)$ , V represents the vertices of the graph and E represents the edges of the graph.

(ii)

IS (independent set): an independent set I of V is a subset of V such that $\forall u, v \in V$ , $u v \notin E$ .

(iii)

MIS (maximal independent set): an independent set $V^{'}$ of V is a subset of V such that $\forall u, v \in V$ , $u v \notin E$ , for $\forall u \in V - V^{'}$ , there exists a $v \in V^{'}$ satisfying $u v \in E$ .

(iv)

DS (dominating set): in a graph $G (V, E)$ , a dominating set D of $G (V, E)$ is a subset of V such that, for $\forall u \in V - D$ , there exists a $v \in D$ satisfying $u v \in E$ .

(v)

CDS (connected dominating set): if all nodes in DS induce a connected graph, DS is a connected dominating set.

(vi)

MCDS (minimum connected dominating set): among all connected dominating sets of V, the one with the smallest cardinality is called the minimum connected dominating set.

3.1.2. Network Model Definition

We model the wireless sensor network as a SUG (simple undirected graph) denoted as $G (V, E)$ . Here, V represents the set of sensor nodes and E represents the set of edges. An edge $u v \in E$ if and only if $u, v \in V$ and the Euclidean distance between u and v is smaller than 1 unit. Sensor nodes in SUG can communicate with each other if this distance is at most 1 unit.

3.1.3. MIS Construction

MIS is a node set, and, in this set, arbitrary two nodes are not connected and all the nodes outside the set are connected with at least one node in the MIS. MIS is frequently used as the basis of constructing a network virtual backbone as it can include as much as possible nodes which are evenly dispersed in a network. Inspired by virtual backbone, we come up with the idea that is based on MIS to choose anchor nodes. There are many existing works about MIS construction [25, 29]. For example, literature [25] constructs the backbone via algebraic connectivity and introduces a new metric, namely, connectivity efficiency, as a benchmark when constructing the backbone. In our work, we adopt the algorithms about MIS construction proposed in [29–31] and apply them in our simulation. Through literature [28], we can know that the nodes number in MIS is $8 \times N_{o p t} + 3$ ; here $N_{o p t}$ is the nodes number of MCDS. MCDS (minimum connected dominating set) is composed of the minimum number nodes of all CDS in a network.

To construct MIS, firstly we define several functions: color $(p)$ represents the state of node p. Color “white” indicates the initial state. Color “red” indicates that the node is in the ready state. Color “black” indicates that the node is a master. Color “gray” indicates that the node is a slave node. Message $(p)$ represents the information broadcasted by the node p, “manager,” “subordinate,” and “ready.” Node p in different states will broadcast different messages. For example, when a node becomes the master, it will broadcast “manager” information to its neighbors, while a slave node broadcasts “subordinate”; if a node receives “subordinate” information, it will become a ready node and broadcast “ready” information.

At the beginning of the construction, we will choose an arbitrary node to be the leader as the initial node or choose it by the leader election algorithm. After the election of the leader, the state transformation process of each node is shown in the following steps.

Step 1.

If node p is a leader, the leader will be directly promoted to be a master. The color of this node will be changed to black from white.

Step 2.

If an initial node p receives “manager” information from master U and the color of this node is white, then node U will be the master of p and p becomes a slave node. Node p's color will be changed to gray from white and it will broadcast “subordinate” information.

Step 3.

If an initial node p receives “subordinate” information, the node will enter the ready state and becomes a ready node. Node p's color will be changed to red from white and it will broadcast “ready” information.

Step 4.

If a node p's color is white or red and it receives the “ready” information, then the state of this node does not change and node p only records the red neighbors' information.

Step 5.

If node p's color is red, then compare all the red nodes in the network and choose the node that has the minimum ID as the next master. Change node p's color to black and its message to “managers.”

The end condition of Algorithm 1 is that there does not exist any white node in the network. Through this algorithm, several star shaped structures are produced. In each star structure, a black node as a master connects multiple grey slave nodes.

Algorithm 1: MIS construction.

begin

input: a nodes set A consists of all nodes in the network (The serial number ID of each node is known)

output: MIS of the network

(1) Initialization:

(2) the ID number of each node is known;

(3) set all nodes' color as white;

(4) set all nodes' message as null.

(5) A leader node p produced by the leader election algorithm, then set:

(6) color(p) = black; message(p) = “manager”;

(7) for each node q in A do

(8) if $c o l o r (q) = = w h i t e$ then

(9) if q receives “manager” message then

(10) color(q) = gray;

(11) message(q) = “subordinate”;

(12) if q receives “subordinate” message then

(13) color(q) = red;

(14) message(q) = “ready”;

(15) if $c o l o r (q) = = r e d$ then

(16) Put q and q's neighbors whose color is red into array M;

(17) Choose the minimum ID from all ID in M;

(18) And find the coordinate node r to become a master;

(19) Then set: color(r) = black;

message(r) = “manager”;

(20) Repeat (7–19) until there doesn't exist white node in whole network;

Lemma 1.

The size of maximum independent set in $G = (V, E)$ is at least 4 and at most $(8 o p t + 3)$ ; $o p t$ is the size of MCDS of G in the theory.

Proof.

It can be known that the size of maximum independent set is at least 4 according to the concept of MIS. Let M be the maximum independent set of V, and let T be the corresponding spanning tree of the MCDS in the theory. Consider an arbitrary preorder traversal of T given by $v_{1}, v_{2}, v_{3}, \dots, v_{o p t}$ . Let $M_{1}$ be the set of nodes in M that are adjacent to $v_{1}$ . For any $2 \leq i \leq o p t$ , let $M_{i}$ be the set of nodes in M that are adjacent to $v_{i}$ but not adjacent to $v_{1}, v_{2}, \dots, v_{i - 1}$ . Then $M_{1}, M_{2}, \dots, M_{o p t}$ form a partition of M. Based on literature [32], it is clear to know that $v_{1}$ can be adjacent to at most 11 independent nodes. So the following equation can be obtained:

\begin{matrix} |M_{1}| \leq 11, \\ |M_{i}| \leq 8 . \end{matrix}

(2)

For any

2 \leq i \leq o p t

, at least one node in

v_{1}, v_{2}, \dots, v_{i - 1}

is adjacent to

v_{i}

. Therefore,

\begin{matrix} |M| = \sum_{i = 1}^{o p t} ‍ |M_{i}| = |M_{1}| \leq 11 + 8 (o p t - 1) = 8 o p t + 3 . \end{matrix}

(3)

Then the size of maximum independent set in $G = (V, E)$ is at least 4 and at most ( $8 o p t + 3$ ), $o p t$ is the size of MCDS of G in the theory.

According to the process of MIS construction, for any vertex u in a maximal independent set I, the length of the shortest path from u to its closest vertex in I is either two hops or three hops. In the following MIS construction simulation, nodes are randomly distributed in an area of $300 m \times 300 m$ and the communication radius of the network is set as $100$ m. Figure 1 shows the simulation results of MIS construction. Figure 1(a) shows MIS construction result when the total number of sensor nodes is 150. To see the result of MIS clearly, here we only show the dominating nodes are marked as red. And Figure 1(b) shows the results of MIS construction when the total number of nodes in the network is chosen from $[80 100 120 140 160 180 200]$ .

Figure 1

The simulation result of MIS construction.

From Figure 1, it can be seen that the size of MIS is more than 4, which can meet the requirement of anchor nodes. According to [33], the size of independent set in $G = (V, E)$ is at most $(8 o p t + 3)$ ; $o p t$ is the size of MCDS of G in theory. The detailed proof is shown in [33].

3.1.4. Anchor Nodes Deployment

With established MIS of the network, we start to place the anchors. The serial number of each node in MIS can be known. Here, we mark the MIS as M. The selection approach is based on the cluster analysis. We use hop count similarity method to divide the whole nodes set to several clusters. Firstly, we generate N uniformly dispersed ( $4 \leq N \leq 8 \times N_{o p t} + 3$ ) nodes as seed nodes in the network region. Each node in M calculates the hop counts from N seed nodes. It will be put into cluster S when it has the shortest hop count with seed node S. For example, if we need deploy 10 anchor nodes, we generate 10 seed nodes and divide the whole MIS nodes set into 10 clusters. Next, choose a node q in ${cluster}_{1}$ randomly and put q's serial number into an array B. Then find nodes that have the largest hop count with q in other clusters and record their serial number in B. According to this method find all proper nodes in each cluster. Finally we can get a certain number of nodes as a basis to deploy anchor nodes. The detail is listed as Algorithm 2.

Algorithm 2: Anchor nodes deployment.

begin

input: a nodes set M of MIS (The serial number of each node is known)

output: N serial number used to deploy anchor nodes

(1) Generate $N (4 \leq N \leq 8 * N_{o p t} + 3)$ uniformly dispersed nodes as seed nodes in the network region.

(2) for each node P in M do

(3) calculate the hop counts from N seed nodes.

(4) if the hop count between P and seed node $S_{i}$ is least then

(5) P belongs to $S_{i}$ .

(6) Then M is divided into N cluster.

(7) Define int $i (1 \leq i \leq N)$ as the serial number of N cluster.

(8) Choose one node q randomly in $c l u s t e r_{1}$ and put q's serial number into array B.

(9) if $i < N$ then

(10) Find the largest hop count between q and the node r in $c l u s t e r_{i + 1}$ ;

(11) Use array B to record the node r's serial number;

(12) i++;

(13) for $i = 1 : N$ do

(14) return $B_{i}$ ;

(15) N serial number is obtained, then return them.

3.2. RSSI Communication Propagation Model Selection

The proper propagation model selection is critical in the proposed algorithm, as it directly affects the way we calculate path loss. The path loss can reflect the distance between arbitrary two sensor nodes. Within our knowledge, the RSSI value is easily affected by the wireless signal reflection, absorption, and other noises. Figure 2 demonstrates that the increasing RSSI value can largely reflect a relative closer distance between two nodes.

Figure 2

The relationship between RSSI attenuation value and distance.

Many channel models have been proposed for outdoor and indoor environments. We group them into two categories: regular model and irregular model. In regular model, the received signal strength is represented by the difference between the emission signal strength and the transmission loss. However, in practical applications, the regular model cannot reflect the exact channel state. This is due to the fact that the propagation range of radio signals in real world will be affected by shadow effect, reflections propagation, refraction propagation, scatter propagation, propagation, diffraction propagation, and other factors, which makes the relationship between signal strength and distance difficult to determine. In view of this circumstance, several irregular models are proposed, such as DOI model and RIM model [34].

In our tests, we choose the DOI model to capture the reference RSSI value as RIM model is too sensitive to the environment. DOI (degree of irregularity) is defined as the percentage of the variation degree in the wireless communication's unit direction about the maximum path loss. DOI model is a universal wireless propagation model. The DOI model is on the basis of the following formula:

\begin{matrix} P_{R} (d) = P_{T} - P_{L} (d_{0}) - 10 η \log_{10} \frac{d}{d_{0}} \times k_{i} . \end{matrix}

(4)

Here,

P_{R} (d)

is the received signal power in dB at distance d;

P_{T}

is the emission signal power;

P_{L} (d_{0})

is the path loss power at distance

d_{0}

; η is the path loss exponent; d is the distance between the sending and receiving end. In the above formula, except

K_{i}

, other symbolic meanings are the same as that of the regular model's formula mentioned above. And here,

K_{i}

is the path loss coefficient of concordance and i is used to represent the different directions,

i \in [0,360]

K_{i}

can be calculated according the following formula:

\begin{matrix} K_{i} = \{\begin{cases} 1, & i = 0; \\ K_{i} \pm rand \times DOI, & 0 < i < 360 \cap i \in N, \\ |K_{0} - K_{359}| \leq DOI . \end{cases} \end{matrix}

(5)

Therefore we can calculate the different

K_{i}

value from all different directions.

3.3. The Hop Distance Revision

As showed in the above introduction of the traditional DV-HOP algorithm, the hopsize is calculated based on the hop count. The hop count and hopsize are both modified in the proposed algorithm.

When hop count between unknown node and anchor node is 1, we use the distance calculated based on the RSSI attenuation value to replace the distance estimated by using the average single distance. As we all know, the distance estimated by RSSI attenuation value is relatively precise within the communication range. For example, as shown in Figure 3, $P_{1}$ , $P_{2}$ , $P_{3}$ , and $P_{4}$ are anchor nodes and A, B, C, D, E, and F are the unknown nodes. The real distance between 2 terminal nodes is marked as red while the RSSI value between two nodes is marked as blue number. According to the method of the traditional DV-HOP algorithm, the average single hop distance of $P_{2}$ can be calculated by the following formula: ${hopsize}_{P_{2}} = (40 + 40 + 40) / (4 + 6 + 5) = 8$ . From this, we can work out the distance between node A and the anchor node $P_{2}$ to be 8, while the real distance between them is 25 m. However, if we use the RSSI attenuation value, we can get a RSSI attenuation value $- 110.4502$ dBm, and then using DOI model we can calculate a more precise distance value $25.5092$ m, which improves the distance measurement greatly compared to traditional method. To find further evidence, several rounds of simulations were carried out to show the association between RSSI value and corresponding distance. Table 1 shows the distances with respect to relative RSSI value between anchor node $P_{2}$ and node A. We set the communication radius to 30 m and the DOI (degree of irregularity) to 0.015. Then we get these measurements shown in Table 1. From these data, it is clear to see that the estimated results are closer to the real distance and they have a difference of about 2 meters.

Table 1

RSSI attenuation value versus correspondent distance.

Times	1	2	3	4	5	6	7	8	9	10
RSS_loss (dBm)	−110.3591	−110.7924	−110.2467	−109.9668	−109.4674	−108.7275	−109.1796	−109.3454	−109.2531	−109.6217
Distance (m)	24.2090	25.0976	23.6837	23.1195	23.0766	22.8823	23.8736	24.8204	24.9281	25.6947

Figure 3

The distance error.

When hop count is greater than 1, decimal counts are accumulated in the proposed algorithm. In our approach, we set the beacon of anchor nodes with the following information: ID number, location, hop counts initialized to zero, and $R_{i j}$ . Particularly, the forth term $R_{i j}$ is defined as the decimal hop count between nodes i and j. It can be calculated by the formula: $R_{i j} = {RSSI}_{loss} / Ref$ . Here, “Ref” is the corresponding RSSI value to the communication radius. $R_{i j}$ represents the ratio of the RSSI attenuation value between two nodes i and j and Ref.

We can also clearly represent this method using Figure 4. Given the communication radius 30 m, we can get the “Ref” $- 122.4880$ dBm. Anchor node $P_{1}$ broadcasts beacons to the whole network and node C receives. C increases the hop count by 1 and set $R_{P_{1} C}$ to $- 90.3225 / - 122.4880 = 0.7374$ . $- 90.3225$ is the RSSI attenuation from $P_{1}$ to C. Then C broadcasts the beacon, and B receives. B also increases the hop count by 1; now the hop count between B and $P_{1}$ is $2$ . Besides, B set $R_{P_{1} B}$ is equal to the sum of $R_{P_{1} C}$ and $R_{CB}$ . It can be computed by the following formula: $R_{P_{1} B} = R_{P_{1} C} + R_{CB} = 0.7374 + 0.7963 = 1.5337$ . With the propagation of these beacons, the hop count and $R_{i j}$ can be obtained. With the combination of Freud's law, we can get the shortest hop count and $R_{i j}$ between two nodes of the whole network. Then the average hop distance of $P_{2}$ is shown by the following formula: ${Hopsize}_{P_{2}} = (40 + 40 + 40) / (3.3065 + 4.5901 + 3.8019) = 10.2577$ .

Figure 4

The procedure of 3D-RDH algorithm.

Through the preceding calculation method, the average hop distance of $P_{1}$ , $P_{3}$ , and $P_{4}$ can also be calculated, ${Hopsize}_{P_{1}} = 12.69$ , ${Hopsize}_{P_{3}} = 12.82$ , and ${Hopsize}_{P_{4}} = 11.91$ , while the hopsize of these four anchors is separately 9.95, 8, 9.95, and 9.23 by using the traditional approach. Besides, the hop count between A and $P_{1}$ , $P_{3}$ , $P_{4}$ can also be obtained. Using traditional method, the result is 3, 5, and 4, while using our proposed approach the result is 2.2128, 3.7379, and 2.9497. Then we can estimate the distance between the four anchor nodes and A using the following formula: ${Distance}_{estimated} = Hopsize * hop count$ . We can get the estimated distance between B and the four anchors: $A- P_{1}$ : $12.69 \times 2.2128 = 28.08$ , $A- P_{2}$ : 25.51 (hop count = 1), $A- P_{3}$ : $12.82 \times 3.7379 = 47.92$ , and $A- P_{4}$ : $11.91 \times 2.9497 = 35.1$ . According to the calculation result of the traditional approach, we can get the distances between A and these four anchor nodes as follows: 29.85, 8, 49.75, and 36.92. By comparing the two sets of data, it is clear to see that the previous group is closer to the actual distance.

3.4. The Procedure of 3D-RDH Algorithm

The flow chart of the proposed algorithm is shown in Figure 4. It can be described as follows.

(1) Broadcast the information of the anchor nodes: each anchor node generates and broadcasts a beacon containing its own information: ID number, location, hop count initialized to 0, and $R_{i j}$ ; here i is the ID number of the anchor node and j is its neighbor node number. When a neighbor node m receives a beacon message of anchor node P, m will increase the hop count by 1 and set the $R_{P m}$ to the ratio of the RSSI value from P and the reference Ref. Then node m will carry on forwarding the new beacon message. When the message arrives at its neighbor node n, the hop count will be accumulated by 1, and $R_{P n}$ can be obtained by adding $R_{P m}$ to $R_{m n}$ . The beacon message will be passed throughout the whole network following Freud's law. In the end, the shortest hop count and $R_{i j}$ of the whole network between nodes can be calculated and recorded.

(2) Calculate the distance between the unknown and anchor nodes: with the known distance between anchor nodes, the average hop distance of each anchor node is computed. Next, for neighboring nodes of anchor nodes, the distance between them can be obtained directly through the propagation model with RSSI value. For unknown nodes with hop count ≥ 2, the distance can be calculated by the multiple of $R_{i j}$ and the average hopsize of this anchor node.

(3) Estimate the coordinates of the unknown: based on the preceding steps, the unknown can estimate its own coordinate by using maximum likelihood estimate. Suppose there are $n (n \geq 4)$ reference nodes in 3D network and their coordinates are $(x_{1}, y_{1}, z_{1}), (x_{2}, y_{2}, z_{2}), (x_{3}, y_{3}, z_{3}), \dots, (x_{n}, y_{n}, z_{n})$ separately, the coordinate of unknown node P is $(x, y, z)$ , and the distance between P and m reference nodes $(m \leq n)$ that have connectivity with P is $d_{1}, d_{2}, \dots, d_{m}$ . Then the following equation set can be obtained based on space distance formula between two nodes:

\begin{array}{l} {(x_{1} - x)}^{2} + {(y_{1} - y)}^{2} + {(z_{1} - z)}^{2} = d_{1} \\ {(x_{2} - x)}^{2} + {(y_{2} - y)}^{2} + {(z_{2} - z)}^{2} = d_{2} \\ {(x_{3} - x)}^{2} + {(y_{3} - y)}^{2} + {(z_{3} - z)}^{2} = d_{3} \\ ⋮ \\ {(x_{m} - x)}^{2} + {(y_{m} - y)}^{2} + {(z_{m} - z)}^{2} = d_{m} . \end{array}

(6)

After subtracting the last formula separately, the previous

m - 1

formula can be simplified as the following formula set:

\begin{array}{l} 2 (x_{1} - x_{m}) x + 2 (y_{1} - y_{m}) y + 2 (z_{1} - z_{m}) z \\ = (x_{1}^{2} + y_{1}^{2} + z_{1}^{2}) - (x_{m}^{2} + y_{m}^{2} + z_{m}^{2}) - (d_{1}^{2} - d_{m}^{2}); \\ 2 (x_{2} - x_{m}) x + 2 (y_{2} - y_{m}) y + 2 (z_{2} - z_{m}) z \\ = (x_{2}^{2} + y_{2}^{2} + z_{2}^{2}) - (x_{m}^{2} + y_{m}^{2} + z_{m}^{2}) - (d_{2}^{2} - d_{m}^{2}); \\ ⋮ \\ 2 (x_{m - 1} - x_{m}) x + 2 (y_{m - 1} - y_{m}) y + 2 (z_{m - 1} - z_{m}) z \\ = (x_{m - 1}^{2} + y_{m - 1}^{2} + z_{m - 1}^{2}) \\ - (x_{m}^{2} + y_{m}^{2} + z_{m}^{2}) - (d_{m - 1}^{2} - d_{m}^{2}) . \end{array}

(7)

Then we set

\begin{matrix} A = \{\begin{matrix} 2 (x_{1} - x_{m}) & 2 (y_{1} - y_{m}) & 2 (z_{1} - z_{m}) \\ 2 (x_{2} - x_{m}) & 2 (y_{2} - y_{m}) & 2 (z_{2} - z_{m}) \\ ⋮ \\ 2 (x_{m - 1} - x_{m}) & 2 (y_{m - 1} - y_{m}) & 2 (z_{m - 1} - z_{m}), \end{matrix} \\ b = \{\begin{cases} (x_{1}^{2} + y_{1}^{2} + z_{1}^{2}) - (x_{m}^{2} + y_{m}^{2} + z_{m}^{2}) - (d_{1}^{2} - d_{m}^{2}); \\ (x_{2}^{2} + y_{2}^{2} + z_{2}^{2}) - (x_{m}^{2} + y_{m}^{2} + z_{m}^{2}) - (d_{2}^{2} - d_{m}^{2}); \\ ⋮ \\ (x_{m - 1}^{2} + y_{m - 1}^{2} + z_{m - 1}^{2}) \\ - (x_{m}^{2} + y_{m}^{2} + z_{m}^{2}) - (d_{m - 1}^{2} - d_{m}^{2}), \end{cases} \\ X = \{\begin{cases} x \\ y \\ z . \end{cases} \end{matrix}

(8)

And we can obtain the following equation:

A X = b

. Then, the coordinates of the unknown nodes can be obtained based on the minimum variance estimation standard as follows:

\begin{matrix} \hat{X} = {(A^{T} A)}^{- 1} A^{T} b . \end{matrix}

(9)

4. Performance Evaluation

4.1. Simulation Setup

In this section, we carry out simulations to verify the performance of RDH-3D algorithm. We evaluate the performance of the proposed algorithm in terms of accuracy and compare the performance with two centralized 3D range-free techniques: 3D DV-HOP and 3D centroid. Localization error is used to represent the localization accuracy and is defined as follows. Let l denote the distance between two neighboring nodes computed based on the established coordinates and $\hat{l}$ denote the ground-truth distance between them. We define the network-wide average of $|l - \hat{l}| / r$ to be the average location error, where r is the maximum radio communication range of sensor nodes. The simulation is set up in a regular cube area with fixed size of 300 m × 300 m × 300 m. 200 sensor nodes are randomly deployed in the scenario with variable number of anchor nodes. The communication radius of each node is set to 100. The communication model uses DOI model, DOI = 0.015. Figure 5 shows the location error figure when 9 anchor nodes are deployed.

Figure 5

Positioning error figure.

4.2. The Number of Anchor Nodes

It can be seen from Figure 6 that the proposed algorithm can outperform the other two algorithms regardless the number of anchor nodes. Here, $3 D-RDH (*)$ shows the localization result when the anchor nodes are deployed randomly in the network. Generally, the localization error decreases as the number of anchor nodes increases within limits. For the same number of anchor nodes, it is obvious to see that our 3D-RDH algorithm achieves better performance than the 3D DV-HOP in the same scenario. For example, with 10 anchor nodes, 3D-RDH has an average error of about 38%, whereas the traditional DV-HOP algorithm and the 3D centroid algorithms have reached an average error of about 65% and 61%. 3D-RDH improves accuracy by 37% compared with traditional 3D range-free algorithm. Besides, the performance of 3D-RDH is better than $3 D-RDH (*)$ without anchor nodes placement, and the former improves accuracy by an average of 12% compared with the latter.

Figure 6

Localization error versus anchor nodes.

4.3. Network Connectivity

The connectivity level of a network will affect localization accuracy too. We observe the localization error changes through varying the connectivity of the network. As shown in Figure 7, our proposed algorithm achieves the best localization accuracy compared with the other two algorithms. As the network connectivity increases, range-free techniques obtain better localization accuracy. This can be explained by the distance calculation which could be more precise given a higher connectivity network. When the connectivity is 20, the proposed algorithm exceeds 3D DV-HOP up to 38.9% and surpasses the 3D centroid algorithms up to 51.8%.

Figure 7

Localization error versus network connectivity.

5. Conclusion and Future Work

In this paper, we propose a hybrid sensor localization scheme. Our simulation studies reveal that our proposed algorithm 3D-RDH is an effective localization approach for 3D wireless sensor network. With the proper selection of signal propagation model and proposed anchor node configuration strategy, the 3D-RDH can improve localization accuracy by up to 52.7%. Future work will include investigation of applying the proposed algorithm under different irregular 3D network and RSSI refinement. In this work, we assumed that there is no hole existing in the 3D network. More research in network topology partition will be needed if we apply the proposed algorithm to different irregular 3D network. Also, the RSSI training set could be optimized in the future to obtain more accurate RSSI references.

Footnotes

Conflict of Interests

The authors declare that the work described is original research that has not been published before. No conflict of interests exists in this work.

Acknowledgment

This work is supported by the National Natural Science Foundation of China under Grant nos. 61190113 and 61401135.

References

Shu

Cheng

Chen

TOC: localizing wireless rechargeable sensors with time of charge

Proceedings of the IEEE Conference on Computer Communications (IEEE INFOCOM ′14)

April 2014

Toronto, Canada

388 396

10.1109/infocom.2014.6847961

Cheng

Zhang

Chen

Sun

Shen

A distributed TDMA scheduling algorithm for target tracking in ultrasonic sensor networks

IEEE Transactions on Industrial Electronics 2013 60 9 3836 3845

10.1109/TIE.2012.2208439

2-s2.0-84877780644

Zhuang

Pan

Cai

Minimizing energy consumption with probabilistic distance models in wireless sensor networks

Proceedings of the IEEE Conference on Computer Communications (INFOCOM ′10)

March 2010

San Diego, Calif, USA

1 9

10.1109/INFCOM.2010.5462073

Liu

Yang

Wang

Jian

Location, localization, and localizability

Journal of Computer Science and Technology 2010 25 2 274 297

2-s2.0-77952154160

10.1007/s11390-010-9324-2

Zhao

Jin

Xia

Localization in 3D surface sensor networks: challenges and solutions

Proceedings of the IEEE Conference on Computer Communications (INFOCOM ′12)

March 2012

55 63

10.1109/infcom.2012.6195798

2-s2.0-84861611446

Qiu

Wang

Dai

Improving the indoor localization accuracy for CPS by reorganizing the fingerprint signatures

International Journal of Distributed Sensor Networks 2014 2014 13

415710

10.1155/2014/415710

2-s2.0-84897526437

Liu

Rendered path: range-free localization in anisotropic sensor networks with holes

Proceedings of the 13th Annual ACM International Conference on Mobile Computing and Networking (MobiCom ′07)

September 2007

51 62

10.1145/1287853.1287861

2-s2.0-37749028750

Doherty

El Ghaoui

Pister

K. S. J.

Convex position estimation in wireless sensor networks

Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies

April 2001

Anchorage, Alaska, USA

IEEE

1655 1663

2-s2.0-0035013232

10.1109/INFCOM.2001.916662

Zhang

Zhou

Cheng

Landscape-3D: a robust localization scheme for sensor networks over complex 3D terrains

Proceedings of the 31st Annual IEEE Conference on Local Computer Networks (LCN ′06)

November 2006

239 246

10.1109/lcn.2006.322106

2-s2.0-46149101238

10.

Shang

Ruml

Zhang

Fromherz

M. P. J.

Localization from mere connectivity

Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC ′03)

June 2003

201 212

2-s2.0-0242612017

11.

Liu

Wang

Jiang

Wang

Approximate convex decomposition based localization in wireless sensor networks

Proceedings of the IEEE Conference on Computer Communications (INFOCOM ′12)

March 2012

Orlando, Fla, USA

1853 1861

10.1109/infcom.2012.6195560

2-s2.0-84861582100

12.

Tan

Jiang

Zhang

Kermarrec

A.-M.

Connectivity-based and anchor-free localization in large-scale 2D/3D sensor networks

Proceedings of the 11th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc ′10)

September 2010

191 200

10.1145/1860093.1860120

2-s2.0-78649275345

13.

Huang

Blum

B. M.

Stankovic

J. A.

Abdelzaher

Rangefree localization schemes for large scale sensor networks

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

2003

81 95

14.

Bulusu

Heidemann

Estrin

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

IEEE Personal Communications 2000 7 5 28 34

10.1109/98.878533

2-s2.0-0034291601

15.

Pan

Hou

Y. T.

Cai

Shi

Shen

S. X.

Topology Control for Wireless Sensor Networks

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

September 2003

286 299

2-s2.0-1542358975

16.

Liu

Ren

Chen

Shen

X. S.

Design principles and improvement of cost function based energy aware routing algorithms for wireless sensor networks

Computer Networks 2012 56 7 1951 1967

10.1016/j.comnet.2012.01.023

2-s2.0-84862810099

17.

Ding

Willson

J. K.

Lee

Construction of directional virtual backbones with minimum routing cost in wireless networks

Proceedings of the IEEE INFOCOM

April 2011

1557 1565

2-s2.0-79960876258

10.1109/infcom.2011.5934946

18.

Niculescu

Nath

Ad hoc positioning system (APS)

Proceedings of the IEEE Global Telecommunicatins Conference (GLOBECOM ′01)

November 2001

2926 2931

2-s2.0-0035684931

19.

Huang

Selvakennedy

A range-free localization algorithm for wireless sensor networks

Proceedings of the IEEE 63rd Vehicular Technology Conference (VTC ′06)

May 2006

349 353

20.

Wanming

Tao

Qinghu

Huawei

Yumei

Yajin

Lei

A localization algorithm based on discrete imprecision range measurement in wireless sensor networks

Proceedings of the IEEE International Conference on Information Acquisition (ICIA ′06)

August 2006

Shandong, China

644 648

10.1109/icia.2006.305801

2-s2.0-46249108721

21.

Zhao

Jia

A hybrid localization algorithm based on DV-Distance and the twice-weighted centroid for WSN

Proceedings of the 3rd IEEE International Conference on Computer Science and Information Technology (ICCSIT ′10)

July 2010

590 594

10.1109/iccsit.2010.5564625

2-s2.0-77958578774

22.

Bargshady

Alsindi

N. A.

Pahlavan

Akgul

F. O.

Bounds on performance of hybrid WiFi-UWB cooperative RF localization for robotic applications

Proceedings of the IEEE 21st International Symposium on Personal, Indoor and Mobile Radio Communications Workshops (PIMRC ′10)

September 2010

Instanbul, Turkey

IEEE

277 282

10.1109/PIMRCW.2010.5670379

23.

Han

Choi

Lim

A novel reference node selection algorithm based on trilateration for indoor sensor networks

Proceedings of the 7th IEEE International Conference on Computer and Information Technology (CIT ′07)

October 2007

1003 1008

10.1109/cit.2007.4385216

2-s2.0-38049076377

24.

Coluccia

Ricciato

On ML estimation for automatic RSS-based indoor localization

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

May 2010

Modena, Italy

IEEE

495 502

10.1109/iswpc.2010.5483724

2-s2.0-77954797060

25.

Wan

Alzoubi

Frieder

Distributed construction of connected dominating set in wireless ad hoc networks

Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '02)

2002

1597 1604

10.1109/INFCOM.2002.1019411

26.

Guo

Qian

Moayeri

Backbone construction for heterogeneous wireless ad hoc networks

Proceedings of the IEEE International Conference on Communications (ICC ′09)

June 2009

1 5

10.1109/icc.2009.5198773

2-s2.0-70449465854

27.

Alzoubi

X.-Y.

Wang

Wan

P.-J.

Frieder

Geometric spanners for wireless ad hoc networks

IEEE Transactions on Parallel and Distributed Systems 2003 14 4 408 421

10.1109/tpds.2003.1195412

2-s2.0-0037957308

28.

Zhong

Wang

Connected dominating set in 3-dimensional space for ad hoc network

Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC ′07)

March 2007

3612 3615

10.1109/wcnc.2007.661

2-s2.0-36349011445

29.

Cheng

Ding

D. H.

Jia

Virtual backbone construction in multihop ad hoc wireless networks

Wireless Communications and Mobile Computing 2006 6 2 183 190

10.1002/wcm.378

2-s2.0-33645521024

30.

Lee

Howard

Constant approximation for virtual backbone construction with guaranteed routing cost in wireless sensor networks

Proceedings of the IEEE INFOCOM

April 2011

1737 1744

10.1109/infcom.2011.5934967

2-s2.0-79960877514

31.

Lee

CDS-based virtual backbone construction with guaranteed routing cost in wireless sensor networks

IEEE Transactions on Parallel and Distributed Systems 2013 24 4 652 661

10.1109/tpds.2012.177

2-s2.0-84874964051

32.

Wan

P.-J.

Alzoubi

K. M.

Frieder

Distributed construction of connected dominating set in wireless ad hoc networks

Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM ′02)

June 2002

1597 1604

2-s2.0-0036346466

33.

Zhong

Wang

Connected dominating set in 3-dimensional space for ad hoc network

Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC ′07)

March 2007

3609 3612

2-s2.0-36349011445

10.1109/wcnc.2007.661

34.

Zhou

Krishnamurthy

Stankovic

J. A.

Models and solutions for radio irregularity in wireless sensor networks

ACM Transactions on Sensor Networks 2006 2 2 221 262

10.1145/1149283.1149287

2-s2.0-33746895103