MDS-based Localization Scheme for Large-Scale
WSNs within Sparse Anchor Nodes
Xizhe Wang, Jian Qiu*, Jin Fan, Guojun Dai
Institute of Computer Application Technology
Hangzhou Dianzi University
Hangzhou, China, 310018
*qiujianhdu@gmail.com
Abstract—The purpose of this paper is to present a novel
localization scheme for sensor networks with large scale de-
ployment with sparse anchor nodes. In most wireless sensor
networks, sensed data are location-aware as they are only
useful with the location information. However, localization is
not a simple task according to the financial cost and technical
limitations. The deployment environment also affect the accuracy
of the localization. Many solutions have been introduced, but the
performance is still not satisfactory or the cost of hardware device
and computation complex are too high. In our proposed scheme,
fewer anchor nodes are required to reduce the cost. With the help
of modified Floyd algorithm and MDS-based Optimal Anchor
Nodes Selection algorithm, good performance can be achieved
in such sparse anchor situation. The analytical discussions and
simulation results both prove these improvements.
Index Terms—wireless sensors networks, MDS-based localiza-
tion, optimal anchor nodes selection, low anchors proportion
I. INTRODUCTION
In recent researches on wireless sensor networks (WSNs),
localization [1] has been one of the most important issues
as most of WSNs are designed as location-aware systems.
Many localization schemes have been introduced, which can
be classified into range-based or range-free due to positioning
schemes, indoor or outdoor due to surroundings.
Due to the characteristics of environment, range-based
schemes can perform well in outdoor localization, especially
in open wild where the multipath fading and abrupt small-
scale signal distortion [2] are much less significant than indoor
localization [3]. Trilateration [4] and MDS [5] are widely dis-
cussed as these algorithms are mathematically strict and easy
to implement. Their kernel issues focus on the approaches to
estimate distances between nodes and reference base facilities,
such as GPS system.
However, these types of techniques require every sensor
node to be equipped with a GPS or other sophisticated module
to serve ToA, TDoA, and AoA schemes [6]–[8], which cost
a large amount of budget. Researchers turn to anchor-based
schemes [1], [5], [9], [10], in which only part of the nodes
will be enhanced with sophisticated modules to reduce the
costs. These nodes are referred as anchor nodes. The remaining
nodes will be localized with the help of anchors. Localization
accuracy of conventional schemes is seriously relying on the
proportion of anchors and the density of networks. It becomes
deteriorated when either of the two key factors changes.
A few anchor-free schemes [11]–[13] have been introduced
for further reduction of costs. Actually, they are not real
anchor-free, otherwise the geographical location will never be
obtained. These schemes only use connectivity information
to establish relative maps, and translate them into absolute
coordinate systems by very few anchors. They claim to receive
good performance only when the networks are under certain
constraints. For instance, the distribution of nodes should be
relatively even, the network is isotropic that all nodes share
a uniform signal propagation model, etc. In real world, large-
scale WSNs are deployed at random, which present complex
shapes such as concave with holes [11], [14]–[16] due to
geographical conditions. In addition, the signal propagation
environment of nodes are not always stable, asymmetric links
may exist thus the connectivity may only be valid in a certain
proportion.
This paper proposes an MDS-based Optimal Anchor
Nodes Selection (OANS) localization scheme for randomly
deployed WSNs with sparse anchor nodes. This scheme main-
ly consists of two key algorithms, a modified Floyd algorithm
[17] and OANS algorithm focus on refining the estimation of
distances between nodes and anchors (N-A distances), which
is used to optimize the strategy of anchors selection. Both two
algorithms serve MDS by reorganizing limited data among
anchors and connectivity information.
The reminder of this paper is organized as follows. Section-
II outlines previous works about MDS-based localization
schemes and briefly analyzes MDS. Section-III describes the
scheme model and kernel algorithms. The strategy of anchor n-
odes selection is discussed in detail in Section-IV. Simulations
of large-scale WSNs are carried out in section-V followed by
data configuration base upon experiments. Finally, in section-
VI, the conclusion and future work are listed.
II. R
ELATED WORK
A. MDS-based Localization Schemes
MDS-based localization is a type of sensor network lo-
calization schemes which is location free, in which N-A
distances estimation is the key step. The schemes presented in
[18], [19] estimate distances by RSSI values sensed between
base stations and slightly altered in MDS computation. They