RI-MDS: Multidimensional Scaling Iterative Localization Algorithm Using RSSI in Wireless Sensor Networks

Abstract

To improve the feasibility and the convenience of localization methods for wireless sensor networks, a localization algorithm RI-MDS (RSSI-based iterative-multidimensional scaling) is proposed. The RI-MDS method is centralized and mainly focuses on improving localization accuracy. It collects RSSI vectors as ranging basis and combines the metric MDS method and the nonmetric MDS method to accomplish the relative localization. Then it uses the maximum likelihood method in affine transformation to transform the relative coordinates to absolute ones. Our method has no need for additional equipment on the WSN nodes. Simulation and field experiments show that the average localization error and the localization error ratio of the RI-MDS method are relatively lower and thus they are more feasible.

1. Introduction

Wireless sensor networks (WSNs) are very important for the IOT (Internet of Things). They are ad hoc networks via wireless communication and consist of a large number of smart nodes [1]. WSNs are widely used in applications such as medical, military, and environment surveillance. We deploy WSNs for information perception, collection, and management and send information to the observer. Usually, the sensor nodes are deployed randomly and the location of the nodes cannot be known. But in many applications the positions of the sensor nodes must be estimated first. As a result, the sensor localization is one of the important research tasks.

Due to the high cost and high energy consumption, it is impossible to use a GPS (Global Positioning System) on every sensor node. In general, we get the positions of sensor nodes by indirect estimation. Localization techniques for sensor nodes can be classified into range-based techniques and range-free techniques [2]. Range-based techniques estimate location by the received signal strength indicator (RSSI) [3], the time of arrival (TOA) [4], the angle of arrival (AOA) [5], and so forth. They perform localization via geometric calculation. The range-based method using RSSI is the most feasible and suitable due to the hardware overhead, the energy saving, and the technical stability. But range-based localization methods have physical limitation and measurement error. Range-free localization methods do not use additional devices. So, range-free localization methods estimate the positions according to the network connectivity, and the localization output is an interval with considerable error. According to the difference of localization reference, the localization algorithm can be classified into absolute positioning scheme and relative positioning scheme. The former produces global standard coordinate, and the latter produces local relative coordinate. Each method has its own pros and cons. The multidimensional scaling (MDS) localization method can fulfill both schemes according to the configuration of network.

The MDS algorithms also can be classified into metric MDS and nonmetric MDS (NMDS) according to whether it needs ranging or not [6]. The diversity matrix of metric MDS method comes from ranging, and the data are accurate comparatively. So it can reflect the similarity and the diversity of the entity quantitatively. While the nonmetric MDS has no special demand on the distance between nodes. Usually, the nonmetric MDS can gain a good performance only if the similarity or diversity of the node distance satisfies monotone increasing or monotone decreasing. It is found that the MDS localization methods always have significant error. The nonmetric MDS can get the approximate optimal solution via iterations, so it has higher tolerance to error. But the localization accuracy of nonmetric MDS greatly depends on initial configuration.

In this paper, we proposed a new type of MDS localization method—RSSI-based iterative-MDS (RI-MDS) method. It constructs the dissimilarity matrix RSSI values and combines the metric MDS scheme with the nonmetric MDS scheme. The initial position coordinates are calculated via metric MDS method and construct the relative position relationship via iterative nonmetric MDS. Then we transform the relative localization coordinates to the absolute localization coordinates using mathematical method. With the rational cooperation of these two kinds of MDS methods, the localization accuracy was improved. In addition, our RI-MDS needs no special device equipped. Extensive simulation experiments and field experiments show that the performance and the practicability of RI-MDS method are good. The main contributions can be summarized as follows: (1) improving the localization accuracy by combining the metric MDS method and the nonmetric MDS method and (2) improving the robustness by introducing the maximum likelihood estimation (MLE) method to the affine transformation process.

The rest of this paper is organized as follows. A brief introduction to the state of the art of the MDS localization methods is presented in Section 2. In Section 3, the details of our RI-MDS method are given. Performance analysis of our RI-MDS algorithm is provided in Section 4, and conclusions are drawn in Section 5.

2. Related Work

The MDS technology is widely used in psychometrics and psychophysics. It itself is a data analysis method on a group of data structures which represent distances using geometric figure. It is first applied in localization of wireless sensor networks by Shang et al. [7]. They illustrated how the MDS can solve the localization problem by taking a pile of suspended small ball as an example; that is, we called their method classical MDS algorithm (MDS-MAP). Later, Shang and Ruml improved the MDS-MAP in [8]. The MDS localization method has strong robustness and higher accuracy even in sparse network. Furthermore, the MDS method can fulfill both the absolute localization and the relative localization. Lots of MDS-like WSNs localization methods have been proposed in [9–11]. The MDS method itself belongs to the centralized computational algorithm. It runs high strength computations on the sink nodes or on the backend server. There are two ways to improve it: (1) to develop new MDS methods based on distributed computation and (2) to improve the localization accuracy of the MDS method. In view of the fact that the MDS method has a high computational time complexity, [12, 13] use the distributed MDS methods. They divided the whole network into several clusters. In the cluster, the head node fulfills the MDS method to work out the node local positions and converts the local position coordinates to the global position coordinates by using the coordinates of some communal nodes. The distributed MDS method increases the network overhead and causes accumulative errors, although it can improve the performance of localization algorithm. In this paper, we focus on how to improve the localization accuracy of centralized MDS method. In [14], Amar et al. divide the sensor nodes into two groups according to the connectivity. Then they adopted MDS method in the group with the higher connectivity and extended the localization process to another group by the least square method. The error accumulation makes the localization accuracy that should be improved. Ma et al. [15] showed that the distance of nodes can be estimated by the hop counts which can be represented by a real number. However, the improvement of localization accuracy is trivial. Other researchers applied the range-based MDS algorithm using the mobile anchor nodes [16]. Although the redundancy of dissimilarity matrix is increased, the anchor node with mobility is necessary, and the design of mobile path is thus complex. A linear WLS-based weighted MDS estimating method is proposed in [17], which can get an accuracy close to Cramér–Rao lower bound (CRLB) for sufficiently small noise conditions; it is modified to operate in partially connected WSN scenarios. The literature [18] estimates the distance of indirect communication nodes using the shortest possible theoretical distance instead of Dijkstra algorithm. Although it improves the dissimilarity matrix accuracy to some extent, the improvement of localization accuracy is limited because of the lack of the subsequent error eliminate process. The most important research questions relating to centralized MDS method are how to generate the relative coordinates which can really reflect the monotonous relationship of nodes and how to eliminate the error produced in the previous step.

3. RI-MDS Localization Algorithm

3.1. The Basic Idea of RI-MDS

The range-free MDS methods take advantage of the relationship in which the distances and the diversities of nodes are monotonous. It improves localization accuracy via iterative computation. Range-free methods have the great tolerance to the measurement error via iterative calculations. But the localization accuracy of the range-free MDS methods tends to be influenced largely by initial configuration. The value of RSSI suffers the impact of environment, but we can acquire the relatively actual initial location information of nodes by simplicity treatment. The impact of environment can be eliminated in some degree via iterative calculation of NMDS. The localization error also can be further eliminated in the coordinate translation process by applying maximum likelihood estimation (MLE).

According to the analysis mentioned above, we proposed the RI-MDS localization method which adopted the RSSI values to construct the dissimilarity matrix and utilized the NMDS method to calculate the relative coordinates. Sensor nodes collect the RSSI values t times to construct the distance vectors and transmit the distance vectors to the sink node. Sink node constructs the dissimilarity matrix using the distance vectors. By combining metric MDS method with the nonmetric MDS method, sink node acquires the relative coordinates of sensor nodes, and then the relative coordinates are transformed to the absolute coordinates. The algorithm flow of RI-MDS is depicted in Figure 1.

Figure 1

Algorithm flowchart of RI-MDS.

3.2. Algorithm Design and Description

The description of RI-MDS algorithm follows.

Algorithm Input. It is RSSI distance vectors of nodes.

Algorithm Output. It is the absolute location coordinates of nodes.

The steps of RI-MDS algorithm are as follows.

Step 1. Sensor nodes collect the pairwise RSSI values for t times to form the distance vector and transmit these distance vectors to sink node.

Step 2. Sink node calculates the average RSSI values and acquires the ranging values according to 1. The dissimilarity matrix $[p_{i j}]$ was constructed based on the ranging values:

\begin{matrix} d = 1 0^{(Rssi - E) / 10 n}, \end{matrix}

(1)

where d denotes distance and E and n are constants which are related to the antenna gain and environment. The ranging value is influenced by the environment factor E greatly, but it can be degraded by the subsequent NMDS iterations.

Step 3. According to the known distance information, the average distance of single hop $D_{ave}$ can be acquired. Distances of nodes which cannot communicate directly are estimated by the shortest path algorithm; then, the integrity of $[p_{i j}]$ is provided by adding these distances. Calculating the relative coordinate $X^{0}$ by using the classical MDS algorithm on the dissimilarity matrix $[p_{i j}]$ is acquired in Step 2. We can get the distance matrix $[d_{i j}^{k}]$ based on $X^{0}$ .

Step 4. Calculate the relative position coordinate $X^{r}$ of each node via nonmetric MDS algorithm.

Step 5. Select several anchor nodes (more than 3 noncollinear nodes in two-dimensional space and more than 4 noncoplanar nodes in three-dimensional space). Convert the relative coordinate $X^{r}$ of each node to the absolute one by utilizing the affine transform based on the absolute coordinates of these anchor nodes.

Step 4 is a key step; it adopted nonmetric MDS method to compute the coordinates of nodes iteratively such that the STRESS is satisfied. The detailed description follows.

Input of Step 4. The threshold value ε of the stress coefficient and the initial position coordinate $X^{0}$ are acquired in Step 3.

Output of Step 4. It is the relative position coordinates $X^{r}$ of each node.

Initialization. Initialize the iterations K as 0.

The process of Step 4 follows.

Step 4.1. Acquire the intermediate variable matrix $[{\overset{⌢}{d}}_{i j}^{k}]$ by utilizing the PAV algorithm [19] on $[d_{i j}^{k}]$ and dissimilarity matrix $[p_{i j}]$ acquired in Step 3. The value of ${\overset{⌢}{d}}_{i j}^{k}$ must satisfy the following conditions for any nodes a, b, c, and d, where $p_{ab} < p_{cd}$ :

if $d_{ab}^{k} < d_{cd}^{k}$ , then ${\overset{⌢}{d}}_{ab}^{k} = d_{ab}^{k}$ , ${\overset{⌢}{d}}_{cd}^{k} = d_{cd}^{k}$ ;

if $d_{ab}^{k} \geq d_{cd}^{k}$ , then ${\overset{⌢}{d}}_{ab}^{k} = {\overset{⌢}{d}}_{cd}^{k} = (1 / 2) (d_{ab}^{k} + d_{cd}^{k})$ .

Step 4.2. The iterations counter $K = K + 1$ ; calculate the new coordinate $X_{k}$ of each node by utilizing the steepest descent method:

\begin{matrix} X_{i}^{k} = X_{i}^{k - 1} + \frac{a}{n - 1} \sum_{i \neq j} (1 - \frac{{\overset{⌢}{d}}_{i j}^{k - 1}}{d_{i j}^{k - 1}}) (X_{j}^{k - 1} - X_{i}^{k - 1}), \end{matrix}

(2)

where n stands for the number of nodes and a represents the iteration increment of the steepest descent method. Properly speaking, the value of a should be recalculated in every iteration. But what the value of a can influence is not the result of algorithm but is the convergence. So we adopted

a = 0.2

[20].

Step 4.3. Recalculate the pairwise distance information of nodes to update the distance matrix $[d_{i j}^{k}]$ .

Step 4.4. Calculate the STRESS coefficient via formula 3. If the $STRESS > ε$ , then go to Step 4.2; otherwise, the Step 4 is finished. Consider

\begin{matrix} {STRESS}^{'} = \sqrt{\frac{\sum_{i = 0, j = 0, i \neq j}^{n} {({\overset{⌢}{d}}_{i j} - d_{i j})}^{2}}{\sum_{i = 0, j = 0, i \neq j}^{n} {d_{i j}}^{2}} .} \end{matrix}

(3)

The last step of the RI-MDS is coordinate transformation. Assuming

(x_{1}, y_{1}), (x_{2}, y_{2}), \dots, (x_{m}, y_{m})

is the relative position coordinates of m nodes, the corresponding absolute localization coordinates are

(x_{1}^{'}, y_{1}^{'}), (x_{2}^{'}, y_{2}^{'}), \dots, (x_{m}^{'}, y_{m}^{'})

. The coordinate transformation matrix is acquired as formula 4 by conducting mirror operation (optional), zoom operation, rotation, and translation by sequence:

\begin{matrix} [\begin{bmatrix} x_{m}^{'} \\ y_{m}^{'} \\ 1 \end{bmatrix}] = [\begin{bmatrix} λ \cos θ & \pm λ \sin θ & b_{x} \\ λ \sin θ & \mp λ \cos θ & b_{y} \\ 0 & 0 & 1 \end{bmatrix}] \cdot [\begin{bmatrix} x_{m} \\ y_{m} \\ 1 \end{bmatrix}], \end{matrix}

(4)

where θ stands for the angle that the coordinate axis rotates counterclockwise around the origin and

b_{x}

and

b_{y}

are movement distances of origin on the x-axis and y-axis, respectively.

Applying the relative coordinates and the absolute coordinates of m nodes into formula 4, we get

\begin{array}{l} x_{1}^{'} = λ \cos θ x_{1} \pm λ \sin θ x_{1} + b_{x}, \\ x_{2}^{'} = λ \cos θ x_{2} \pm λ \sin θ x_{2} + b_{x}, \\ ⋮ \\ x_{m}^{'} = λ \cos θ x_{m} \pm λ \sin θ x_{m} + b_{x}, \\ y_{1}^{'} = λ \cos θ y_{1} \mp λ \sin θ y_{1} + b_{y}, \\ y_{2}^{'} = λ \cos θ y_{2} \mp λ \sin θ y_{2} + b_{y}, \\ ⋮ \\ y_{m}^{'} = λ \cos θ y_{m} \mp λ \sin θ y_{m} + b_{y} . \end{array}

(5)

Acquire the estimated values of arguments

λ \sin θ

λ \cos θ

b_{x}

, and

b_{y}

by applying the MLE method on 5. These values are in the sense of least mean square error. And we get the linear transformation equation:

\begin{array}{l} x^{'} = λ \cos θ x \pm λ \sin θ y + b_{x}, \\ y^{'} = λ \sin θ x \mp λ \cos θ y + b_{y} . \end{array}

(6)

Acquire the absolute coordinates of the other n-m nodes via applying 6 successively.

3.3. Algorithm Time Complexity Analysis

RI-MDS method has seven main steps as mentioned above, covering the Dijkstra shortest path algorithm, classical MDS method, nonmetric MDS method, affine transformation and coordinate transformation, and so forth. Due to the RSSI information can be acquired easily. The RI-MDS method can be fulfilled conveniently. The time complexity analysis of these steps follows. (1)

The time complexity of Dijkstra shortest path algorithm is $O (n^{2})$ .

(2)

The time complexity of metric MDS is $O (n^{2})$ .

(3)

The time complexity of the nonmetric MDS is $O (n^{4})$ . This step is the most time-consuming step, but in line with the variation of the stress coefficient the number of iterations changed too. So, the RI-MDS has great flexibility.

(4)

The time complexity of affine transformation is $O (m^{3})$ , where m is the number of nodes that needed transformation.

(5)

The time complexity of the coordinate transformation is $O (n - m)$ .

4. Experiments Analysis

4.1. Simulation Environment

To verify the effectiveness and the performance of RI-MDS, simulation experiments are conducted. Due to so many matrix calculations in MDS algorithm, the MATLAB simulator is suitable. For the performance comparison under different nodes deployments, we adopt two kinds of nodes deployments; the random deployment and grid deployment are tested, respectively. In the grid deployment, the nodes are not set at the cross of the gird line preciously but with small deviation to the grid cross.

4.2. Wireless Propagation Model

The classical wireless propagation model with random interference is employed to simulate the RSSI variation. The model mentioned above is described as follows:

\begin{matrix} P (d) [dBm] = P (d_{0}) [dBm] - 10 n \log (\frac{d}{d_{0}}) + X_{σ}, \end{matrix}

(7)

where d stands for the distance between a couple of nodes,

d_{0}

is the reference distance, and n denotes the path-loss exponent, which can be from 2 to 4 generally.

P (d_{0})

represents the received signal strength where the distance of sender and receiver is

d_{0}

;

P (d)

stands for the same meaning when the nodes distance is d.

X_{σ}

is the Gaussian white noise, which can be generated by Gaussian random function where the average value is 0 and the variance is σ. By utilizing above model, we can simulate the RSSI values where the nodes distance is given.

4.3. Simulation Experiment Design and Evaluation Indicators

The most commonly used indicators are the average localization error (ALE) and the localization error ratio (LER) and these two indicators are given in formulas 8 and 9, respectively:

\begin{matrix} ALE = \frac{\sum_{i = 1}^{n} \sqrt{{(|X_{i}^{'} - X_{i}|)}^{2}}}{n}, \end{matrix}

(8)

\begin{matrix} LER = \frac{ALE}{r} \times 100 %, \end{matrix}

(9)

where n denotes the number of nodes,

X_{i}^{'}

represents the measuring coordinate of node i,

X_{i}

denotes the real coordinate of node i, and r stands for the communication radius.

There are four parts in our experiments. (1)

Performance comparison of the proposed algorithm under the random deployment and the grid deployment with different average network connectivity: in the random deployment, 200 nodes are randomly scattered in an area of 1000 by 1000 units, and the number of nodes in grid scene depends on the grid unit length. Given the length of grid unit is 50 units, the network connectivity is adjusted by changing the communication radius. Furthermore, the amount of anchors is 4.

(2)

LER comparison of the proposed RI-MDS method with the improved MDS (IMDS) algorithm in [18] under two deployments with different connectivity: there are still 4 anchors and 200 nodes randomly scattered in the area of 1000 by 1000 units. The network connectivity is adjusted by changing the communication radius.

(3)

The algorithm performance with various amounts of anchor nodes being evaluated by changing the number of anchor nodes in our simulations: the average network connectivity is varied from 8 to 14 with step size 2. And the amount of anchors is changed from 3 to 8. The simulation area is still 1000 by 1000 units in which sensor nodes are deployed randomly.

(4)

Experiments for evaluating the algorithm performance with various ranging errors being conducted: the network connectivity is varied from 8 to 12 with step size 2, and the amount of anchor nodes is 4. The ranging error varies from 5% to 10% with step size 5%.

4.4. Simulation Result and Analysis

Simulation results (Figure 2) suggest that, along with the network average connectivity increase, the LER of the RI-MDS algorithm declines under both of these two deployments. And the LER of the RI-MDS under grid deployment is better than under random deployment, especially in the low connectivity.

Figure 2

Performance comparison of localization error of RI-MDS method in different deployment.

By analyzing the principle of RI-MDS algorithm, we know that there are regular distribution characteristics in the grid deployment. And the diversities of nodes are mainly reflected in connectivity. The connectivity of nodes is stable and sufficient; hence the diversity of nodes is similar in redundancy, and the localization accuracy is relative even. So we draw the conclusion mentioned above.

Furthermore, the localization accuracy of civil GPS system is about 10 meters. While most of wireless sensor nodes have a communication radius about from 30 m to 50 m, the localization algorithm can be regarded as being practicable only when the LER is less than 25%. The LER gets the practicability when the network average connectivity is 8 and 14, respectively, under the two deployments as we can see in Figure 2.

The results of second simulation experiment are shown in Figures 3 and 4, respectively. We can draw a conclusion from Figures 3 and 4 that the LER of the RI-MDS method is 5% to 10%, which is lower than the IMDS algorithm regardless of what deployment is used. We can also note that the LER decline trend of the IMDS is slowed down when the network average connectivity reaches more than 16. However, the LER of RI-MDS method is declining along with the connectivity increasing in the same situation. The feature mentioned above became more obvious under the grid deployment.

Figure 3

Average network connectivity versus average localization error rate in random deployment scenario.

Figure 4

Average network connectivity versus average localization error rate in gird deployment scenario.

We can deduce, based on the algorithm principle analysis, that since the IMDS method belongs to metric algorithm, and merely takes the ranging distance as the diversity for all nodes. So the data redundancy is increased along with the network connectivity increased under the situation that more location relationships are introduced. And result in localization accuracy increased, whereas there are lots of data collision in the diversity relationships because the diversity information has measure error introduced by simulation. The more the network connectivity is increasing, the more the redundancy collision is increased. The data collision offset the localization accuracy improvement by introducing more redundancy at a certain extent. Thus the localization accuracy cannot be improved significantly. But the RI-MDS method uses the distance value as the input; thus it reduces the system error in transforming the RSSI to distance. In addition it applies the nonmetric MDS iterative algorithm to eliminate the error introduced by the data redundancy increasing. Thus, the localization accuracy of RI-MDS can still improve obviously under the same situation.

Figure 5 indicates that the localization accuracy increase of RI-MDS is small whatever the network connectivity is, under the condition that the amount of anchor nodes is more than 5. Meanwhile, the localization performance is satisfactory when the network connectivity is higher than 10, whatever the amount of anchor nodes is. Therefore, we can draw a conclusion that our RI-MDS scheme can work well with anchor sparse network as long as the network connectivity is not significantly low.

Figure 5

Localization performance of RI-MDS in various network connectivities and various amounts of anchor nodes.

As shown in Figure 6, the localization accuracy of RI-MDS declines with the ranging error increase. However, the performance of RI-MDS is good enough in the case that the network connectivity is higher than 10. We draw the same conclusion mentioned above.

Figure 6

Localization performance of RI-MDS in various network connectivities and various ranging errors.

4.5. Field Experiment and Analysis

The field experiments are fulfilled on the GAINSJ hardware platform. The sensor nodes of GAINSJ adopt the ZigBee integrated solution of Jennic Company and support the IEEE802.15.4 protocol. The GAINSJ sensor nodes are made in one chip, with so strong security and flexibility that satisfied all kinds of demand in WSNs applications.

The GAINSJ development kits are composed of sensor nodes based on JN5139 chip, software development kits, ZigBee protocol analysis program, iSnamp-J visual background program, and development tutorial documents.

The experiment scene (Figure 7) is a rectangular area witch edge length of 12 meters and covered by small square gridding with 60 cm edge length. From N1 to N9 denote the position of 9 sensor nodes, respectively. All of the nodes have the same configuration and run the same program prewritten by Flash Programmer.

Figure 7

Field experiment scenario.

The field experiment process is described as following.

Step 1. Input the real position coordinates of all nodes by PC data processing program. Assign the beacon nodes which used to transform the relative coordinates to global coordinates.

Step 2. The sink node broadcasts network construction packets, and then all of the nodes join the network, respectively, according to the distribution picture.

Step 3. Sink node schedules the nodes from N1 to N9 and sends the ranging packets in turns. In each round, only one node sends the ranging packet. The other nodes record the RSSI value when receiving the ranging packet.

Step 4. All of the nodes submit the data collected in Step 2 after every node has sent the ranging packet. Then, the sink node transmits these data to the data process program on PC terminal.

Step 5. The data process program calls the RI-MDS algorithm to calculate the localization coordinates and display these coordinates via GUI.

The field experiment repeats 10 times and the number of beacon nodes is 4. We adopt the absolute localization error of every time to make comparison. The LER, maximum localization error, and the minimum localization error are shown in Figure 8.

Figure 8

The average localization error, the maximum localization error, and the minimum localization error of RI-MDS method.

The field experiment of [21] is based on the same hardware platform and the same scene; the typical value of LER in [21] ranged from 2 m to 6 m, while the LER ranged from 1.5 m to 4 m when using the RI-MDS method. By comparison, it is shown that the RI-MDS method has a better performance and higher localization accuracy.

By comparing the experimental data, if we convert the average localization accuracy of field experiment to the LER value, the value is better than the LER in simulation. Because the number of beacon nodes is nearly one half of the total node numbers and the network size is so small that all nodes can communicate with others, the dissimilarity matrix is full of diversity data. The localization method should not have to supplement the diversity data by the shortest path algorithm, and therefore the introduced error is reduced. So, the localization accuracy of field experiment is better than that in simulation.

So, it is feasible to improve the localization accuracy by some computational cost sacrifice, due to the computational performance raised along with the hardware price declining. The RI-MDS algorithm would be of more economic advantage when the network scale and the localization area are extended continuously. However, the localization information collection process needs the sink node scheduling, and the time complexity is raised with the increase of network dimension. So the node energy consumption and the algorithm feasibility have to meet the challenge with the network scale increasing. We must adopt some particular strategies to solve this problem in the large-scale network mentioned above.

5. Conclusion

We proposed the RI-MDS localization method based on RSSI ranging. The RI-MDS method takes full advantage of both metric MDS algorithm and nonmetric MDS algorithm. The algorithm design is presented in detail, and the theoretical analysis of RI-MDS method is proposed. We verified the algorithm performance via simulation and performed the field experiments in real WSNs to illustrate the actual performance of RI-MDS. All the experiments prove that the RI-MDS method is feasible and practicable and its performance is better than IMDS algorithm. The RI-MDS method can be applied to the WSNs in the centralized computation applications. In the future, we are going to develop the cluster-based RI-MDS method to meet the demand of high accuracy in anisotropic network.

Footnotes

Conflict of Interests

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

Acknowledgments

This research was supported by The National Natural Science Foundation of China (61379023) and the Natural Science Foundation of Zhejiang Province of China (LY12F02036).

References

Akyildiz

I. F.

Sankarasubramaniam

Cayirci

Wireless sensor networks: a survey

Computer Networks 2002 38 4 393 422

10.1016/s1389-1286(01)00302-4

2-s2.0-0037086890

Gao

A novel mobile localization method for distributed sensor network with non-line-of-sight error mitigation

International Journal of Distributed Sensor Networks 2014 2014 9

154896

10.1155/2014/154896

2-s2.0-84899931984

Shi

Huo

Fang

A 3D node localization scheme for wireless sensor networks

IEICE Electronics Express 2009 6 3 167 172

10.1587/elex.6.167

2-s2.0-61349134819

Niculescu

Nath

Ad hoc positioning system (APS) using AOA

Proceedings of the 22nd Annual Joint Conference on the IEEE Computer and Communications Societies

April 2003

1734 1743

2-s2.0-0041973656

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

2-s2.0-84866044693

10.1016/j.comnet.2012.07.007

France

S. L.

Carroll

J. D.

Two-way multidimensional scaling: a review

IEEE Transactions on Systems, Man and Cybernetics Part C: Applications and Reviews 2011 41 5 644 661

10.1109/tsmcc.2010.2078502

2-s2.0-80052069040

Shang

Ruml

Zhang

Localization from mere connectivity

Proceedings of the 4th International ACM Symposium on Mobile Ad Hoc Networking and Computing

2003

Annapolis, Md, USA

201 212

Shang

Ruml

Improved MDS-based localization

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

March 2004

2640 2651

10.1109/INFCOM.2004.1354683

Latsoudas

Sidiropoulos

N. D.

A fast and effective multidimensional scaling approach for node localization in wireless sensor networks

IEEE Transactions on Signal Processing 2007 55 10 5121 5127

10.1109/TSP.2007.896101

MR2729718

2-s2.0-35148838909

10.

Wei

H. W.

Wan

Chen

Z. X.

S. F.

A novel weighted multidimensional scaling analysis for time-of-arrival-based mobile location

IEEE Transactions on Signal Processing 2008 56 7 3018 3022

10.1109/tsp.2007.914349

2-s2.0-46749127869

11.

Stone

Camp

A survey of distance-based wireless sensor network localization techniques

International Journal of Pervasive Computing and Communications 2012 8 2 158 183

10.1108/17427371211245373

2-s2.0-84883205701

12.

Shon

Choo

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

Computer Communications 2012 35 15 1921 1929

10.1016/j.comcom.2012.05.002

2-s2.0-84865721783

13.

Ding

Yang

Sun

Distributed localization algorithm for wireless sensor network based on multidimensional scaling and the shortest path distance correction

Transactions of Tianjin University 2009 15 4 237 244

10.1007/s12209-009-0042-1

2-s2.0-69849103206

14.

Amar

Wang

Leus

Extending the classical multidimensional scaling algorithm given partial pairwise distance measurements

IEEE Signal Processing Letters 2010 17 5 473 476

10.1109/lsp.2010.2043890

15.

M. J.

Wang

Lim

H. B.

Range-free wireless sensor networks localization based on hop-count quantization

Telecommunication Systems 2012 50 3 199 213

10.1007/s11235-010-9395-y

2-s2.0-84870437972

16.

Kim

Lee

Kim

Mobile beacon-based 3D-localization with multidimensional scaling in large sensor networks

IEEE Communications Letters 2010 14 7 647 649

10.1109/LCOMM.2010.07.100513

2-s2.0-77955603655

17.

Chan

F. K.

H. C.

Efficient weighted multidimensional scaling for wireless sensor network localization

IEEE Transactions on Signal Processing 2009 57 11 4548 4553

10.1109/TSP.2009.2024869

MR2744107

2-s2.0-70350488507

18.

Stojkoska

B. R.

Kirandziska

Improved MDS-based algorithm for nodes localization in wireless sensor networks

Proceedings of the IEEE EuroCon

July 2013

Zagreb, Croatia

IEEE

608 612

10.1109/EUROCON.2013.6625044

19.

Kruskal

J. B.

Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis

Psychometrika 1964 29 1 1 27

MR0169712

20.

Peng

R. F.

Luo

Nonmetric MDS-based localization algorithm in wireless sensor network

Computer Science 2008 35 10 219 223

21.

Huan

In-bulding localization system based on wireless sensor networks

Journal of Mechanical & Electrical Engineering 2011 28 8 910 913