Time-bounded Localization Algorithm based on
Distributed Multidimensional Scaling for Wireless
Sensor Networks
Ferdews Tlili
ENSI, University of Manouba
HANA Research Group
Tunis, Tunisia
Email: ferdews.tlili@gmail.com
Abderrezak Rachedi
University of Paris-Est (UPEM)
Computer Science lab. (LIGM UMR8049)
Marne-la-Vallee, France
Email: rachedi@univ-mlv.fr
Abderrahim Benslimane
French University of Egypt
Informatics Research Center (CRI)
Cairo, Egypt
Email: abderrahim.benslimane@ufe.edu.eg
Abstract—Many applications of Wireless Sensor Networks
(WSN) require to achieve the positions of the sensor nodes
within a given time bound. In this paper we study the relative
and physical localizability of WSN in a given time bound.
We propose a new distributed and time bounded localization
algorithm based on Multidimensional Scaling (MDS) method in
WSN called D-MDS localization time algorithm. We compare the
proposed algorithm to the existing algorithm based on the well-
known Trilateration method. The simulation results show that the
proposed algorithm outperforms the existing approach based on
Trilateration method in terms of the number of localized nodes
in the network and the number of anchors required to physically
localize the sensors. The D-MDS localization time algorithm
localizes a large number of nodes for a low node degree in a time
bound. Moreover it is able to physically localize the network with
a low number of anchors compared with the algorithm based on
Trilateration method.
Index Terms—Wireless Sensor Networks, Localization algo-
rithm, Localizability, Multidimensional Scaling (MDS), Local
Coordinate System.
I. INTRODUCTION
Wireless Sensors Networks (WSN) are composed of many
sensing-nodes that collect and gather information about the
environment. For years, many researches have been focused
on different limitations of WSN such as the connection of
WSNs to the Internet [1], the management of the distributed
data base for WSN [2] and the localization of nodes in WSNs
[3]. In this work, we tackle the problem of localization in
wireless sensors networks.
The sensor nodes require knowing their positions in order
to track the objects and to route the packets by using the
geometrical routing [4]. The issue of localization is widely
dealt with in order to improve localization accuracy where
many techniques and technologies [5] are used. However,
many military and civilian systems require to confine the
localization time.
In literature, the localization time is a recent topic. In [6],
Cheng et al. describe a study of the time bounded localization
for WSN. They define a localization time algorithm based
on multilateration method. The main objective of relative and
physical localization time algorithm is to maximize the number
of localized nodes in a given time bound and to minimize
the number of anchors required to physically localize the
network. In this paper, we propose to use Multidimensional
Scaling (MDS) method as a basic method for localization time
algorithm.
The MDS method [7] is easy to apply for the localization of
sensors compared with Trilateration method. Indeed, for MDS
method, the node requires a single measure of distance to any
neighbor node to calculate its relative position. However, for
Trilateration method, the node requires the distances to at least
three localized and non collinear nodes in order to compute its
position. Moreover the MDS method outperforms Trilateration
method in terms of position accuracy as shown in [8]. That’s
why, in this work we propose a new distributed and time
bounded localization algorithm based on the MDS method.
In addition, we evaluate the performance of the proposed
algorithm, and we compare it with Cheng et al. algorithm [6].
The remainder of this paper is organized as follows: In
section II, we propose a look over the related works. Then, we
present a preliminaries for time localization in section III. We
describe the localization time bounded algorithm based on the
MDS method in section IV. In section V, we analyze the time
complexity of our proposed algorithm. The simulation results
are discussed in section VI. Finally, the conclusion and future
work are given in section VII.
II. R
ELATED WORK
In literature, there are various distributed localization algo-
rithms. These algorithms can be classified into two categories:
full distributed iterative localization algorithms [9] and cluster-
based localization algorithms [10].
The full distributed iterative localization algorithms [9]
consist in calculating the positions of unlocalized nodes which
have at least the distance with three non collinear localized
nodes at each iteration. The sensor nodes with known location
information (or with the local coordinate system (LCS)) are
called anchors. The new localized nodes are considered as
anchors which contribute to localize other nodes in the next
iteration. The main problem of this category of algorithms
IEEE ICC 2014 - Ad-hoc and Sensor Networking Symposium
978-1-4799-2003-7/14/$31.00 ©2014 IEEE 233
资源评论
