D3D-MDS: A Distributed 3D Localization Scheme for an Irregular Wireless Sensor Network Using Multidimensional Scaling

Abstract

This paper proposes a distributed localization algorithm which can be applied to an irregular three-dimensional wireless sensor network, considering the algorithm accuracy and complexity. The algorithm uses clusters to eliminate the multihop distance errors. An anchor node position optimization scheme is proposed to maximize the uniformity of each subnetwork. The proposed algorithm also employs a new three-dimensional coordinate transformation algorithm, which helps to reduce the errors introduced by coordinate integration between clusters and improves the localization precision. The simulation and performance analysis results show that the localization accuracy of the D3D-MDS algorithm increases by 49.1% compared with 3D-DV-HOP and 38.6% compared with 3D-MDS-MAP. This distributed localization scheme also demonstrates a low computational complexity compared with other centralized localization algorithms.

1. Introduction

Localization has been an important topic in data-centric wireless sensor networks (WSNs) due to the special association between location information and the relevance of sensory data. Recently, a gradual but marked shift in the focus of 3D localization has taken place. While the 3D technique brings WSNs closer to reality, the localization complexity in computation and accuracy can be much higher than a 2D case.

The most straightforward method for 3D localization is to use the global positioning system (GPS). Nevertheless, having each node GPS-equipped is extremely expensive for large scale wireless sensor networks. Recently there has been growing interest in 2D localization protocols that use the connectivity information only [1]. This aims to produce a relative coordinate system for a network without reliance on extra hardware supplements [2–4]. These schemes can accurately recover the original network topology, up to scaling and rotation. Among the many studies, multidimensional scaling (MDS) based localization techniques have been proved to compute locations of high accuracy and request low node density. A state-of-the-art MDS based algorithm, MDS-MAP [5], takes an internode hop distance/estimated distance matrix as input and generates a set of relative coordinates for each node.

Currently, 3D localization has been widely investigated in the area of underwater sensor networks. Many centralized localization schemes are proposed to estimate node locations, such as 3D-DV-HOP [6] and 3D-MDS [7]. However, these schemes either suffer from high computation complexity or heavily depend on assumptions about the network environments, such as dense anchor deployment, the availability of depth information, and a relatively small network size. None of these schemes can work with connectivity information alone (or with a constant number of anchors) in an irregular large scale 3D WSN.

The above observation motivates our work in developing an effective 3D localization approach which can be used in a large scale wireless sensor network regardless of topology. Most importantly, a distributed localization algorithm is highly preferred in large scale 3D WSNs as it can achieve network localization at respective low computational cost. For some cases, a distributed localization algorithm could even fulfill partial localization.

In this paper, we propose a distributed 3D localization scheme for an irregular wireless sensor network using multidimensional scaling (D3D-MDS). The algorithm uses clusters to eliminate the multihop distance errors. An anchor node position optimization scheme is proposed to uniform each subnetwork. Also a new three-dimensional coordinate transformation algorithm inspired by camera calibration principle of computer vision is introduced in the proposed algorithm to reduce the errors of coordinate integration between clusters and improve the localization precision. The empirical result demonstrates the capability of D3D-MDS in higher accuracy and low computational cost. The contribution of proposed algorithm lies in the high localization accuracy, relative low computational complexity, and the distributed fashion of localization.

The remainder of this paper is organized as follows. Section 2 outlines the previous algorithms carried out on 3D localization and valuable ideas in 2D plane with respect to localization. The D3D-MDS algorithm is then described in detail in Section 3. Section 4 presents a description of the simulation scenarios and results. Algorithm performance evaluation in terms of accuracy and complexity is also discussed in this part. Finally, in Section 5, the conclusion and future work are listed.

2. Related Works

While extensive studies focus on localization techniques in two-dimensional space, few approaches have been proposed for three-dimensional locationing. Landscape 3D [8] is proposed as one of the first proposed robust localization techniques for 3D sensor deployments using range-based approach. Landscape 3D introduces the concept of mobile location assistants (LA) that are aware of their moving positions through GPS. Each location-unaware node uses RSSI to estimate its own location through LAs that are around. USP [9] tackles the localization problem in sparse 3D underwater sensor networks where the depth information of deployed sensors is available. USP utilizes a projection technique to map the problem to make using range estimation techniques for 2D terrestrial sensor networks possible. Shi et al. [10] introduce a 3D localization approach for WSNs. Similar to Landscape-3D, their localization approach makes use of a mobile beacon, which emits ultra-wideband (UWB) signals to achieve location positioning. Upon reception of the UWB signals, each sensor node measures the distance to the mobile anchor using the TOA technique. Although these methods are independent of node densities and network topologies, the major drawback relied on mobile beacon or extra hardware for the network.

Another kind of major methods on 3D localization employs centralized algorithm to compute the actual coordinate of each unknown node instead of using range-based approaches. The centroid-based approach [11] is among the earliest works of connectivity-based localization. A node estimates its location simply by calculating the centroid of audible anchors’ locations. If anchors are placed uniformly, then the localization can be achieved with high accuracy. However, the accuracy cannot be assured for ad hoc or mobile WSNs with such technique. Other centralized algorithms, like DV-HOP, MDS-MAP, and so forth, are modified from 2D-plan scenarios. In [12] the authors propose cluster-based approach named CBLALS. In each cluster, the intercluster range measurement errors are corrected using triangle principle. The evaluation of CBLALS with respect to DV-Distance (3D) shows that CBLALS has much better positioning accuracy than DV-Distance (3D). A novel centroid localization method that significantly improves the basic centroid localization algorithm is presented in [13]. Each unknown node randomly selects four anchor nodes to form a series of tetrahedrons which are used to calculate its own position. However, for a large scale wireless sensor network, with the limited power and computation capability of each sensor node, centralized algorithms can be extremely expensive at cost of computational and time complexity.

CATL [14] is a recent state-of-the-art localization algorithm that can be adopted into a 3D scenario. The key idea of CATL is to identify notch nodes where the hop-count of the shortest path between the nodes deviates the true Euclidean distance. CATL then uses an iterative notch-avoiding multilateration scheme to localize the network. The performance of CATL heavily depends on proper deployment of some beacon nodes. In addition, due to the iterative procedure, CATL suffers from error propagation.

Zhao et al. [15] propose a localization algorithm for complex 3D surface. It formulates the localization problem under a practical setting with estimated link distances (between nearby nodes) and nodal height measurements and introduces a layered approach to promote the localizability of such 3D surface sensor networks. The nodal height measurements can be obtained by measuring atmospheric pressure through pressure sensors. The algorithm employs the idea that 3D surface localization problem can be reduced to the localization problem on 2D plane with the known nodal height. However, the extra hardware is quite expensive; for example, the Crossbow MTS400/MTS420 sensor board equipped with intersema MS55ER pressure sensor is priced at 467 US dollars. In addition, the layered approach in this algorithm is extremely computationally expensive. It is not suitable for large scale energy-constrained WSNs.

3. A Distributed 3D Localization Scheme for an Irregular Wireless Sensor Network Using Multidimensional Scaling

In our paper, we propose a distributed localization technique in 3D wireless sensor network environments where sensor nodes can be randomly deployed regardless topology. For complete network localization, we assume that the network is fully connected, which means at least one routing path exists between any pair of sensor nodes on the network. Also, no sensor node has mobility in the network. The rough procedures of 4 steps are shown as Algorithms 1, 2, 3, and 4 and the details of each step will be introduced next. (I)

Anchor node placement: assuming we have the boundaries of the network (boundary identification is out of the scope of this work as it was fully discussed in work [16–19]), we identify a series of edge nodes from the network boundaries. Then an anchor node configuration algorithm is proposed in this part to achieve relatively high localization accuracy by optimizing the anchor nodes placement.

(II)

Node clustering: the subnetworks are generated from node clustering. Each subnetwork is identified by an anchor node and a group of unknown nodes nearby. After node clustering, each subnetwork will achieve relative localization by MDS algorithm. The node clustering algorithm will guarantee each cluster is composed of unknown nodes which have the minimum hop information to their cluster head (anchor node).

(III)

Local relative map establishment: we propose an improved MDS technique to build the relative map for each cluster. MDS-MAP has a computational overhead of $O (n^{3})$ in a network of n nodes and, in particular, results in significant localization accuracy error in environments with holes. Thus, this paper proposes an improved MDS algorithm which yields smaller accuracy error in all environments.

(IV)

Global map establishment: finally, we will combine the coordinates of all the clusters into a global map. Note that the combination process will need to be known each sensor in the cluster of the new coordinates. We develop a new three-dimensional coordinate transformation algorithm inspired by camera calibration principle of computer vision to reduce the errors of coordinate integration between clusters.

Algorithm 1: Anchor nodes configuration.

begin

input: A bitmap $I m$ of size $w \times l$

output: A partition of the bitmap

(1) for each sensor node do

(2) establish the neighbor table by receiving the messages from other nodes;

(3) Arbitrary node p whose order number is p obtains its k-hop

neighborhood $N_{p} (k = 1,2)$ , then $n N_{p}$ will be obtained.

(4) Here we let $d_{p}$ denotes the the network connectivity of p within two hops

(5) $\bar{d}$ is the average network connectivity, which is calculated from 2/5 of $n N_{p}$ .

if $d_{p} < (1 - ω) \times \bar{d}$ ( $0 < ω < 1$ ) then

(6) nodes p is an edge node.

(7) for each edge node p do

(8) if no nodes is marked as an anchor node in this neighborhood then

(9) flooding a message within $E d g e S p a c i n g$ ; an anchor node position is identified

(10) if the flooding message is heard then

(11) cancel the flooding

Algorithm 2: Node clustering.

Data: anchors nodes, unknown nodes

Result: Based on the anchor nodes clusters

(1) begin

(2) m represents the number of anchors nodes in the network;

(3) for $i \leftarrow 1$ to m do

(4) for $j \leftarrow 1$ to m do

(5) if i and j can communicate with each other directly then

(6) if $i \neq j$ then

(7) $n e i g h b o r_m a t r i x (i, j) = 1$ ;

(8) else

(9) $n e i g h b o r_m a t r i x (i, j) = 0$ ;

(10) else

(11) $n e i g h b o r_m a t r i x (i, j) = I n f$ ;

(12) $n e i g h b o r_m a t r i x$ can indicates the connectivity relationship between nodes;

$S h o r t e s t P a t h (n e i g h b o r_m a t r i x)$ ;

(13) n represents the number of unknown nodes in the network;

(14) for $i \leftarrow 1$ $t o$ n do

(15) if it has a minimum hop with an anchor node or one more anchor node

then

(16) put it into the cluster of the anchor node;

(17) Then clusters are built and some special nodes called common nodes may exist more than one cluster.

Algorithm 3: Local relative map establishment.

Data: clusters based on the anchors nodes

Result: the relative maps in each cluster

(1) begin

(2) for each cluster do

(3) Corporator of each cluster obtain the hop-count square matrix $D_{i}$ ;

(4) Compute the inner product matrix $B_{i}$ ;

(5) Apply singular value decomposition on matrix $B_{i}$ ;

(6) Extract the first three largest eigenvalues and eigenvectors;

(7) Obtain the relative map of this cluster.

Algorithm 4: Global map establishment.

Data: the local relative coordinates of k clusters

Result: the global map of the netwok

(1) begin

(2) for $i \leftarrow 1$ to k do

(3) for $j \leftarrow 1$ to k do

(4) work out the common nodes number matrix between cluster i and cluster j;

(5) find out the coordinates of the common nodes between clusters;

(6) screen out the coordinates of other ordinary nodes in each cluster;

(7) sort the clusters by the number of the common nodes;

(8) for $m \leftarrow 1$ to $(k - 1)$ do

(9) each time screen two clusters sharing most common nodes to merge;

(10) firstly, use the coordinates of common nodes in two clusters to work out the

parameters of 3D transformation algorithm;

(11) secondly, normalize the other ordinary nodes’ coordinates in each clusters until there is only one big cluster.

(12) finally, the global map contain all the relative coordinates of the network.

3.1. Anchor Nodes Placement

Anchor node placement plays an important role in the quality of spatial localization. As we all know, nodes near the network periphery are more representative of the network layout than interior nodes. In our work, we assumed that network boundary is available and used the edge nodes [20] to find the optimized positions for anchor nodes. Although edge nodes share the common property of being close to the network periphery, they may not cover all the network boundaries. The edge nodes are those representative nodes used to obtain all the major corners in the network. Therefore, the edges nodes detection is more effective than detecting a full and tight boundary. Based on the network edge detecting method [20], we propose an anchor node configuration optimization algorithm to achieve relatively high localization accuracy.

3.1.1. Finding the Network Edge Nodes

The network edges represent a set of boundary nodes where, near the periphery of the network, the identification of edge nodes is described as follows. (1)

Each node obtains its own neighbor nodes to establish a neighbor table. Then all nodes exchange information with its own neighbor node to obtain its two hops neighbor nodes. The reason we choose the network connectivity within two hops is that the influence of the network connectivity within one hop is so susceptible to communication noise that large error can be made.

(2)

All nodes in the network broadcast message packets in the form of flooding. The message packet contains the ID number of the node and network connectivity within two hops, so that each node can obtain the network connectivity within two hops of the other nodes. Through the above data, we can obtain a roughly uniform random sample about the network connectivity within two hops of all nodes. In order to avoid the small deviation of border nodes network connectivity and simplify the operation, the average network connectivity $\bar{d}$ within two hops is calculated from a fraction of samples (we use 2/5 in our experiments).

(3)

Based on the network connectivity $\bar{d}$ within two hops, the network edge nodes can be screened in accordance with the following methods: arbitrary sensor node p compares its own network connectivity $d_{p}$ within two hops and with the average network connectivity $\bar{d}$ within two hops, if $d_{p} < (1 - ω) \times \bar{d}$ , ω satisfied $0 < ω < 1$ , and then the node p will be marked as the edge node. Through this method, we can get a set of the edge nodes of the network.

3.1.2. Anchor Nodes Placement

Having obtained the set of the edge nodes of the network, we can deploy anchors nodes on the network edges so that more effective localization can be obtained. The algorithm chooses uniformly sampled distribution of nodes from the set of the edge nodes with density controlled by a small system parameter EdgeSpacing (typically 3 in our setting). Every edge node asynchronously floods a message in its 3-hop neighborhood, it marks itself as one possible anchor position and then notifies the neighborhood. If a node hears such a flood before its own action, then it cancels its own flooding. After a sufficient time, the hop distance of all these selected nodes between each other is roughly the same. The anchors nodes are then placed in the sampled network edges.

3.2. Node Clustering

The purpose of clustering [21] is to subsection the network and reduce the computation of the algorithm and guarantee the accuracy. Each anchor node is selected as a cluster head. There are two conditions that must be considered: (i)

all the unknown nodes must be assigned to clusters,

(ii)

each two neighboring clusters must have four common nodes, in order to merge coordinates between clusters.

Based on those two requirements, the node clustering algorithm is described as follows. (1)

After all the nodes initialize, every anchor node in the network floods broadcasting packets to neighboring nodes. The packets contain the anchors ID and hop count (initial value is 0).

(2)

Each unknown node maintains a storage list which records the information of minimum-hop anchor node. The basic principle of maintenance is when a node receives a new anchor packet, there will appear two different cases. If the current storage list is empty, the unknown node will store the information of the packet; if not empty, the node will compare the current hop count in the stored packet with the hop count in new anchors packet and the storage list will store the smaller hop count of these two data.

(3)

When each node finishes the above steps, the hop count of the nodes will be plus 1 and it will be transmitted to the node's neighboring node. As a result, every unknown node receives all the anchor packets and updates the storage list. If a node has received the same anchor node information, the storage list will maintain the minimum hop information. It will ensure that the unknown node gets the minimum hop information from anchors nodes.

(4)

After all nodes obtain the smallest hop count information from the corresponding anchor, the unknown nodes will select the anchor node. From the anchor nodes that will be selected the unknown nodes have the smallest hop count, and they put these anchors nodes as its cluster head node [21] and then join the cluster. On the border between two clusters, a node will be a common node if it joined at least two clusters at the same time. In 3D space, merging two coordinate system together must have at least 4 common nodes, which will be introduced in the following part.

3.3. Local Relative Map Establishment

So far the network has been decomposed into several clusters. Every cluster has an anchor node as the cluster head, whose role is in charge of the process of local relative map establishment. Within each cluster, the cluster head computes the shortest distance between each node in current cluster by receiving the information from other nodes in this cluster. Based on the established distance matrix, a local relative map will be established by MDS-MAP algorithm. In this paper, the algorithm based on MDS we uses consists of 4 steps.

Firstly, let $N_{i}$ be the number of sensors in the network and computes an $N_{i} \times N_{i}$ distance square matrix $D_{i}$ , which represents the square of the pairwise distance between two nodes. Secondly, calculate the inner product matrix $B_{i}$ of the pairwise distance matrix $D_{i}$ . The relationship between $B_{i}$ and $D_{i}$ satisfied the following formulas: $B_{i} = - (1 / 2) E D_{i} E$ , and E represents Nth identity matrix. Thirdly, MDS applies SVD (singular value decomposition) on matrix $B_{i}$ to extract all eigenvalues and their corresponding eigenvectors of matrix $B_{i}$ . Finally, the first three largest eigenvalues and eigenvectors give a relative map with relative location for each node.

3.4. Global Map Establishment

After each cluster establishes its local relative map, now we need to combine them to a global map. There are two points that must be concerned: the order of merging cluster and the method for 3D coordinate translation when the global map was established. (i)

During the clustering, every two adjacent clusters have some common nodes, whose coordinates are assigned from two different coordinate systems. The merging process of two clusters is started from the greatest weight of a pair of two clusters. Here the weight means the number of common nodes between pairs.

(ii)

3D coordinate merging algorithm is a key step, and the correspondence between two coordinate systems heavily affects the performance of D3D-MDS. We use an improved transformation algorithm to achieve rigid transformation between coordinate systems (each local map has its own coordinate system) so that the relative coordinates of each local map can then be transformed to the absolute global coordinates of the whole network.

3.4.1. 3D Coordinate Transformation Algorithm

The 3D coordinate transformation algorithm is the key of transforming local relative coordinates to global absolute coordinates. There are many algorithms proposed for coordinate transformation in computer graphics, such as Horn algorithms [22] and several other methods [23–25]. The Horn algorithm consists of three main aspects: rotation, transformation and scaling factors. However, in our problem space, relative coordinate systems share the global metrics (the distance/hop counts between each node); therefore, only rotation and transformation are involved when two coordinate systems merge [26, 27].

We propose an approach which uses the homogeneous coordinates to achieve different coordinate merges. Homogeneous coordinates are a coordinate representation method which uses $N + 1$ coordinates to describe N coordinates. If the homogeneous coordinates of a point are multiplied by a nonzero scalar, then the resulting coordinates represent the same point. The idea is derived from the camera calibration principle of computer vision as shown in Figure 1. The coordinates of P are in the camera coordinate system $(x_{p}, y_{p}, z_{p})$ , while in the world coordinates coordinate system is $(X_{p}, Y_{p}, Z_{p})$ . The transformation formula between these two coordinate systems is shown in

\begin{matrix} [\begin{bmatrix} x_{p} \\ y_{p} \\ z_{p} \\ 1 \end{bmatrix}] = [\begin{bmatrix} R_{3} \times_{3} & T_{3} \times_{1} \\ O_{3} \times_{1} & 1 \end{bmatrix}] [\begin{bmatrix} X_{p} \\ Y_{p} \\ Z_{p} \\ 1 \end{bmatrix}] . \end{matrix}

(1)

Figure 1

Coordinate system.

The rigid transformation from world coordinates to camera coordinates needs two kinds of transformation: rotation and translation transformation. As shown in formula (2), $R_{3} \times_{3}$ represents the rotation transformations which include the rotation transformation of x, y, and z axis. $θ_{x}$ , $θ_{y}$ , and $θ_{z}$ are used to represent the rotation angle of the camera coordinate system around X axis, Y axis, and Z axis of the world coordinate system, respectively. $R_{x}$ , $R_{y}$ , and $R_{z}$ represent the corresponding rotation matrix, respectively:

\begin{array}{l} R_{3} \times_{3} = R_{z} R_{y} R_{x}, \\ R_{x} = [\begin{bmatrix} 1 & 0 & 0 \\ 0 & \cos θ_{x} & - \sin θ_{x} \\ 0 & \sin θ_{x} & \cos θ_{x} \end{bmatrix}], \\ R_{y} = [\begin{bmatrix} \cos θ_{y} & 0 & \sin θ_{y} \\ 0 & 1 & 0 \\ - \sin θ_{y} & 0 & \cos θ_{y} \end{bmatrix}], \\ R_{z} = [\begin{bmatrix} \cos θ_{z} & - \sin θ_{z} & 0 \\ \sin θ_{z} & \cos θ_{z} & 0 \\ 0 & 0 & 1 \end{bmatrix}] . \end{array}

(2)

And

T_{3} \times_{1}

in formula (1) represents the translation transformation matrix of original point from world coordinates to camera coordinates.

The proposed approach for coordinate transformation in this paper is described as follows: suppose there are two clusters named cluster A and cluster B, and the 3D coordinates of one point p in both cluster are $(x_{A}, y_{A}, z_{A})$ in cluster A and $(x_{B}, y_{B}, z_{B})$ in clustr B. We use formula (3) to merge the two coordinates:

\begin{matrix} [\begin{bmatrix} x_{A} \\ y_{A} \\ z_{A} \\ 1 \end{bmatrix}] = M_{B A} [\begin{bmatrix} x_{B} \\ y_{B} \\ z_{B} \\ 1 \end{bmatrix}] = [\begin{bmatrix} R & T \\ O & 1 \end{bmatrix}] [\begin{bmatrix} x_{B} \\ y_{B} \\ z_{B} \\ 1 \end{bmatrix}] . \end{matrix}

(3)

More specifically,

\begin{matrix} [\begin{bmatrix} x_{A} \\ y_{A} \\ z_{A} \\ 1 \end{bmatrix}] = [\begin{bmatrix} R_{1} & R_{2} & R_{3} & T_{x} \\ R_{4} & R_{5} & R_{6} & T_{y} \\ R_{7} & R_{8} & R_{9} & T_{z} \\ 0 & 0 & 0 & 1 \end{bmatrix}] [\begin{bmatrix} x_{B} \\ y_{B} \\ z_{B} \\ 1 \end{bmatrix}] . \end{matrix}

(4)

M_{B A}

is the coordinate transformation matrix from cluster B to cluster A. There are 12 variables, which expressed the rotation matrix R and translational matrix

T = [T_{x}, T_{y}, T_{z}]^{T}

. The rotation matrix

\begin{matrix} R = [\begin{bmatrix} R_{1} & R_{2} & R_{3} \\ R_{4} & R_{5} & R_{6} \\ R_{7} & R_{8} & R_{9} \end{bmatrix}] \end{matrix}

(5)

should meet the orthogonal condition:

\begin{array}{l} R_{1}^{2} + R_{4}^{2} + R_{7}^{2} = 1 \\ R_{2}^{2} + R_{5}^{2} + R_{8}^{2} = 1 \\ R_{3}^{2} + R_{6}^{2} + R_{9}^{2} = 1 \\ R_{1} R_{2} + R_{4} R_{5} + R_{7} R_{8} = 0 \\ R_{1} R_{3} + R_{4} R_{6} + R_{7} R_{9} = 0 \\ R_{2} R_{3} + R_{5} R_{6} + R_{8} R_{9} = 0; \end{array}

(6)

if we make use of the orthogonal condition, three common nodes is enough to calculate the matrix. However, it needs to solve the nonlinear equations, which suffers from high computational complexity and low accuracy. Considering node energy consumption and computational capabilities, we make use of homogeneous coordinates of multiple common nodes and use least square method to solve the transformation matrix.

Formula (4) then can be written as the following matrix form: $X_{A} = M_{B A} X_{B}$ ; here $X_{A}$ and $X_{B}$ are homogeneous coordinates of common nodes in cluster A and cluster B, respectively. Using more common nodes can improve the precision of merging.

Putting n pairs of common nodes coordinates $(x_{A i}, y_{A i}, z_{A i})$ , $(x_{B i}, y_{B i}, z_{B i}) (i = 1,2, \dots, n)$ into formula (4), we can get the formula (7) as follows:

\begin{array}{l} {[x_{A 1}, y_{A 1}, z_{A 1}, x_{A 2}, y_{A 2} z_{A 2}, \dots, x_{A n}, y_{A n}, z_{A n}, ]}^{T} \\ = [\begin{bmatrix} x_{B 1} & y_{B 1} & z_{B 1} & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & x_{B 1} & y_{B 1} & z_{B 1} & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & x_{B 1} & y_{B 1} & z_{B 1} & 1 \\ x_{B 2} & y_{B 2} & z_{B 2} & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & x_{B 2} & y_{B 2} & z_{B 2} & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & x_{B 2} & y_{B 2} & z_{B 2} & 1 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ x_{B n} & y_{B n} & z_{B n} & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & x_{B n} & y_{B n} & z_{B n} & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & x_{B n} & y_{B n} & z_{B n} & 1 \end{bmatrix}] \\ \times {[R_{1}, R_{2}, R_{3}, T_{x}, R_{4}, R_{5} R_{6}, T_{y}, R_{7}, R_{8}, R_{9}, T_{z}]}^{T} . \end{array}

(7)

The equations have the same form as linear equations

A X = b

. Having solved the equation, we can get 12 parameters of transformation matrix X. To reduce the error, we use the singular value decomposition (SVD) method to get least square solution. If A is a

m \times n

matrix, (7) shows that A is full column rank, so the equations have the only least squares solution:

\begin{matrix} A = U W V^{T}, \end{matrix}

(8)

where

W = diag (w_{1}, w_{2}, \dots, w_{n})

w_{1} \geq w_{2} \geq \dots \geq w_{n} \geq 0

w_{i}

is the singular value of matrix A, U is a

m \times m

matrix, V is a

n \times n

matrix,

U = (u_{1}, u_{2}, \dots, u_{m})

, and

V = (v_{1}, v_{2}, \dots, v_{n})

, where

u_{i}

and

v_{i}

are the corresponding left and right singular vectors of

w_{i}

. U and V are orthogonal matrix. So least squares solution of

A X = b

\begin{matrix} X = A^{+} b = V W^{- 1} U^{T} b . \end{matrix}

(9)

Here,

A^{+}

is the generalized inverse matrix of A. Then we get transfer matrix

M_{B A}

, and two coordinate systems of the transfer relationship show as

\begin{array}{l} [\begin{bmatrix} x_{A i} \\ y_{A i} \\ z_{A i} \\ 1 \end{bmatrix}] = M_{B A} [\begin{bmatrix} x_{B i} \\ y_{B i} \\ z_{B i} \\ 1 \end{bmatrix}] \\ = R [\begin{bmatrix} x_{B i} \\ y_{B i} \\ z_{B i} \\ 1 \end{bmatrix}] + T, i = 1,2, \dots, n . \end{array}

(10)

By formula (10), we can merge two clusters into a bigger one.

3.4.2. Global Map Establishment

The global map is established from finding the linear transformation matrix between two selected neighboring clusters. Each round, two neighboring clusters which have the most common nodes will be selected to merge. The merging process will end when all clusters are merged as one cluster and the global map establishment is completed. At the end, all the absolute coordinates of the unknown nodes have been estimated.

4. Simulations and Performance Analysis

We evaluate proposed D3D-MDS algorithm performance in terms of localization accuracy and time complexity. Then we compare it with two centralized algorithms: 3D MDS-MAP and 3D DV-HOP. 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 let $\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 ranges of sensor nodes. Given the limited computation, storage, and energy resources available at individual sensor nodes, it is highly desirable to achieve low computational complexity in localization, especially for a large scale network. The consuming time of different network size is observed as well.

4.1. Simulation Setup

The experiments were carried out in a cube area with the fixed size of 300 m × 300 m × 300 m. A cubic communication blind zone with the fixed size of 160 m × 300 m × 220 m was set to simulate nonuniform conditions, as shown in Figure 2. We deployed 200 sensor nodes randomly in a three-dimensional space. The distances between nodes are calculated by RSSI, and signal transmission model of node uses logarithmic normal distribution model, as showed in

\begin{matrix} P (d) = P (d_{0}) - 10 k lg (\frac{d}{d_{0}}) + e . \end{matrix}

(11)

Figure 2

Nodes distribution.

Among the formula (11), $P (d)$ is the power received from the d distance node; $P (d_{0})$ is the power that received the $d_{0}$ distance node; k is path loss coefficient, which is equal to 4 to simulate the outdoor environment; e denotes signal measurement error, obey normal distribution whose mean is 0 and variance is 4. The simulation results are presented in Figure 2.

4.2. Localization Accuracy

We observe the localization accuracy variation with respect to different anchors nodes. 200 unknown sensor nodes are randomly deployed in a three-dimensional space as shown in Figure 2 with different number of anchor nodes.

As it can be seen from the simulation results of Figure 3, the proposed D3D-MDS algorithm achieves better localization accuracy than the other two no matter how many the anchor nodes are placed in the network. For example, with 11 anchor nodes, D3D-MDS has an average error of about 41%, whereas the 3D-MDS-MAP has an average error of about 67% and the 3D-DV-Hop has an average error of about 81%. The localization error of proposed algorithm decreases as the number of anchor nodes increases until it exceeds 11. This can be explained by cumulative errors which are introduced by multiple rounds of cluster merging.

Figure 3

Localization error versus anchor nodes number.

The connectivity level of a network will affect localization accuracy too. We observe the localization error changes through varying the connectivity of the network. Simulation results show that the higher connectivity of the network can result in better performance in terms of accuracy as shown in Figure 4. The performance of proposed D3D-MDS scheme exceeds the other two algorithms when the network connectivity level is more than 14. It is expected as centralized range-free algorithms only perform well in regular topology. In our simulation scenario, the localization error of centralized algorithms mainly comes from the distance between two nodes which is obtained by the shortest path algorithms while proposed D3D-MDS uses clusters to decompose the network into regular shape and yields to good accuracy performance.

Figure 4

Localization error versus connectivity.

4.3. Time Complexity

The time consuming of the algorithms is relative to the computational complexity. Given n sensor nodes in a network and k anchors nodes, then according to the algorithm we know there are k clusters in the network. The time complexity of clustering algorithm is $O (n)$ . If the average number of sensor nodes in every cluster is $m (m = c / n)$ , the time complexity of computing the coordinates in every cluster is $O (k m^{3})$ . The time complexity of merging the coordinates in different cluster is $O (n)$ , and that of transforming the relative coordinates to absolute coordinates is $O (n)$ too. The time complexity of our proposed D3D-MDS algorithm is $O (k m^{3})$ . Compared with the time complexity of the 3D-MDS-MAP and 3D-DV-HOP, the time complexity decreases from $O (n^{3})$ to $O (k n^{2})$ . As shown in Figure 5, the consuming time of proposed algorithms can achieve approximately 100% improvements better than 3D-MDS and 50% better than 3D-DV-HOP with a relative big network size ( $n = 800$ ). Also Figure 5 shows that the consuming time increases with the network size. This is because a larger network consists of more clusters and thus requires more iterations to complete the localization process.

Figure 5

Time complexity.

4.4. Localization Rate

The proposed algorithm can fulfill partial localization in some extreme network topologies where other centralized algorithms may fail. Here the partial localization rate is described by the ratio of the number of nodes that can be positioned to all nodes. For example, we deployed 200 unknown sensor nodes randomly in a three-dimensional space shown as Figure 6. We carried out the simulation in case the network connectivity is 4.1179 and get that the partial localization rate is 53.4%. However, 3D-DV-HOP and 3D-MDS cannot locate the network when the network connectivity is lower than 8, and this feature can be clearly seen in Figure 7. We confirm that the partial localization rate has been improved via using our D3D-MDS algorithm. For example, when the network connectivity is lower than 7.6, our proposed algorithm has the localization rate between 42.45% and 100%, while the other two algorithms cannot execute the localization.

Figure 6

Partial localization.

Figure 7

Partial localization rate.

5. Conclusion

We present a new distributed method, D3D-MDS, for localization of wireless sensor networks regardless of topology. Our simulation results have shown that it can achieve low location errors and computational complexity, with high scalability to large-size wireless sensor networks. We also explore the influence of anchor nodes and connectivity on the algorithm. All these factors could affect the localization average error and location coverage of the algorithm. Simulation results show that our D3D-MDS is better than the other two algorithms mentioned in this paper, and it overcomes a series of difficulties in node identification, network decomposition, MDS computation, and global map reconstruction. All these are achieved in a way that is discrete, distributed, and low message and computation overhead. Future work may investigate proposed algorithm under more complicated irregular topology and explore the possibility using 3D localization results to facilitate data processing [28–30] in sensor networks.

Footnotes

Conflict of Interests

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

Acknowledgment

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

References

Liu

Yang

Wang

Jian

Location, localization, and localizability

Journal of Computer Science and Technology 2010 25 2 274 297

10.1007/s11390-010-9324-2

2-s2.0-77952154160

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

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

Liu

Locating sensors in the wild: pursuit of ranging quality

Proceedings of the 8th ACM Conference on Embedded Networked Sensor Systems (SenSys '10)

2010

Zürich, Switzerland

295 308

10.1145/1869983.1870012

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

Niculescu

Nath

Ad hoc positioning system (APS)

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

2001

San Antonio, Tex, USA

2926 2931

10.1109/GLOCOM.2001.965964

Shang

Ruml

Improved MDS-based localization

Proceedings of the 23rd AnnualJoint Conference of the IEEE Computer and Communications Societies (INFOCOM '04)

2004

2640 2651

10.1109/infcom.2004.1354683

2-s2.0-8344247710

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

Tampa, Fla, USA

IEEE

239 246

10.1109/lcn.2006.322106

2-s2.0-46149101238

Cheng

Teymorian

A. Y.

Cheng

Underwater localization in sparse 3D acoustic sensor networks

Proceedings of the 27th IEEE Communications Society Conference on Computer Communications (INFOCOM '08)

April 2008

Phoenix, Ariz, USA

798 806

10.1109/infocom.2007.56

2-s2.0-51349120278

10.

Shi

Huo

Fang

A 3D node localization scheme for wireless sensor networks

IEICE Electronics Express 2009 6 3 167 172

2-s2.0-61349134819

10.1587/elex.6.167

11.

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

12.

Shu

Zhang

Liu

Zhou

Cluster-based three-dimensional localization algorithm for large scale wireless sensor networks

Journal of Computers 2009 4 7 585 592

2-s2.0-78651560566

13.

Chen

Huang

Martins

H. C.

Sezaki

Novel centroid localization algorithm for three-dimensional wireless sensor networks

Proceedings of the 4th International Conference on Wireless Communications, Networking and Mobile Computing (WiCOM '08)

October 2008

1 4

2-s2.0-58049105386

10.1109/wicom.2008.841

14.

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

15.

Zhao

Jin

Xia

Localization in 3D surface sensor networks: challenges and solutions

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

March 2012

Orlando, Fla, USA

55 63

10.1109/infcom.2012.6195798

2-s2.0-84861611446

16.

Dong

Liu

Liao

Fine-grained boundary recognition in wireless ad hoc and sensor networks by topological methods

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

May 2009

135 144

2-s2.0-70450177435

10.1145/1530748.1530767

17.

Fekete

S. P.

Kroller

Pfisterer

Buschmann

Neighborhood-based topology recognition in sensor networks

Proceedings of the International Workshop on Algorithmic Aspects of Wireless Sensor Networks

2004

18.

Saukh

Sauter

Gauger

Marron

P. J.

Rothernel

On boundary recognition without location information in wireless sensor networks

Proceedings of the International Conference on Information Processing in Sensor Networks (IPSN '08)

April 2008

St. Louis, Mo, USA

207 218

10.1109/IPSN.2008.11

19.

Wang

Gao

Mitchell

J. S. B.

Boundary recognition in sensor networks by topological methods

Proceedings of 12th Annual International Conference on Mobile Computing and Networking (MOBICOM '06)

2006

ACM

122 133

20.

Tan

Jiang

Zhang

Yin

Kermarrec

A.-M.

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

ACM Transactions on Sensor Networks 2013 10 1, article 6

10.1145/2529976

2-s2.0-84890376405

21.

Shon

Choo

An interactive cluster-based MDS localization scheme for multimedia information in wireless sensor networks

Computer Communications 2012 35 15 1921 1929

2-s2.0-84865721783

10.1016/j.comcom.2012.05.002

22.

Horn

B. K. P.

Closed-form solution of absolute orientation using unit quaternions

Journal of the Optical Society of America A 1987 4 4 629 642

10.1364/josaa.4.000629

23.

Hung

Y. Y.

Lin

Shang

H. M.

Park

B. G.

Practical three-dimensional computer vision techniques for full-field surface measurement

Optical Engineering 2000 39 1 143 149

10.1117/1.602345

2-s2.0-0033882235

24.

Chen

Brown

G. M.

Song

Overview of three-dimensional shape measurement using optical methods

Optical Engineering 2000 39 1 10 22

10.1117/1.602438

2-s2.0-0033895371

25.

Lorusso

Eggert

D. W.

Fisher

R. B.

A comparison of four algorithms for estimating 3-D rigid transformations

Proceedings of the British Conference on Machine Vision (BMVC '95)

1995

237 246

26.

Golovinskiy

Funkhouser

Consistent segmentation of 3D models

Computers and Graphics 2009 33 3 262 269

2-s2.0-67349151121

10.1016/j.cag.2009.03.010

27.

Zhang

Sheffer

Cohen-Or

Zhou

Van Kaick

Tagliasacchi

Deformation-driven shape correspondence

Computer Graphics Forum 2008 27 5 1431 1439

10.1111/j.1467-8659.2008.01283.x

2-s2.0-53149085721

28.

Jiang

Cheng

Wang

Tan

Continuous multidimensional top-k query processing in sensor networks

Proceedings of the IEEE INFOCOM

April 2011

Shanghai, China

793 801

10.1109/infcom.2011.5935301

2-s2.0-79960882186

29.

Jiang

Jin

Wang

Parameter-based data aggregation for statistical information extraction in wireless sensor networks

IEEE Transactions on Vehicular Technology 2010 59 8 3992 4001

10.1109/TVT.2010.2062547

2-s2.0-77958105941

30.

Jiang

Jin

Wang

Prediction or not? An energy-efficient framework for clustering-based data collection in wireless sensor networks

IEEE Transactions on Parallel and Distributed Systems 2011 22 6 1064 1071

2-s2.0-79955521337

10.1109/tpds.2010.174