n positions. Only three such
‘anchor nodes’ are necessary to provide absolute positionsPermission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are for all the nodes in the network.
not made or distributed for profit or commercial advantage and that copies The next section of the paper describes MDS-MAP in more
bear this notice and the full citation on the first page. To copy otherwise, to detail. We will then provide an overview of previous propos-
republish, to post on servers or to redistribute to lists, requires prior specific
als before presenting our empirical evaluation. Our presen-
permission and/or a fee.
tation focuses on a centralized version of the algorithm, al-MobiHoc’03, June 1–3, 2003, Annapolis, Maryland, USA.
Copyright 2003 ACM 1-58113-684-6/03/0006 ...$5.00.
201though we will brie y mention how the computation can be cloud were shattered and the beads fell to the o or, one
distributed. We will examine the performance of MDS-MAP could imagine trying to recreate the arrangement based on
on networks of 100 to 200 nodes, with node locations either the recorded interpoint distances. One would try to deter-
chosen randomly or according to a rough grid or hexagon mine a location for each bead such that the distances in the
layout. We consider a variety of node densities (nodes per new arrangement matched the desired distances. This recre-
communications radius) and a variety of ranging errors when ation process is exactly the problem that multidimensional
using the estimated distances between neighbors. We will scaling (MDS) solves. Intuitively, it is clear that while the
2see that MDS-MAP recovers more accurate maps of node O(n ) distances will be more than enough to determine O(n)
locations while using much less information. coordinates, the result of MDS will be an arbitrarily rotated
and ipp ed version of the true original layout because the
interpoint distances make no reference to any absolute co-2. LOCALIZATION USING MDS-MAP
ordinates.
We consider the node localization problem under two dif-
MDS has its origins in psychometrics and psychophysics.
ferent scenarios. In the rst, only proximity (or connectiv-
It can be seen as a set of data analysis techniques that dis-
ity) information is available. Each node only knows what
play the structure of distance-like data as a geometrical pic-
nodes are nearby, presumably by means of some local com-
ture [1]. MDS starts with one or more distance matrices (or
munication channel such as radio or sound, but not how far
similarity matrices) that are presumed to have been derived
away these neighbors are or in what direction they lie. In
from points in a multidimensional space. It is usually used
the second scenario, the proximity information is enhanced
to nd a placement of the points in a low-dimensional space,
by knowing the distances, perhaps with limited accuracy,
usually two- or three-dimensional, where the distances be-
between neighboring nodes.
tween points resemble the original similarities. MDS is of-
In both cases, the network is represented as an undirected
ten used as part of exploratory data analysis or informa-
graph with vertices V and edges E. The vertices corre-
tion visualization. By visualizing objects as points in a
spond to the nodes, of which there exist m 0 special
low-dimensional space, the complexity in the original data
nodes with known positions, which we will call anchors. For
matrix can often be reduced while preserving the essential
the proximity-only case, the edges in the graph correspond
information. MDS is closely related to principal component
to the connectivity information. For the case with known
analysis, and is also related to factor analysis and cluster
distances to neighbors, the edges are associated with values
analysis.
corresponding to the estimated distances. We assume that
There are many types of MDS techniques. They can be
all the nodes being considered in the positioning problem
classi ed according to whether the similarity data is qualita-
form a connected graph, i.e., there is a path between every
tive (nonmetric MDS) or quantitative (metric MDS). They
pair of nodes.
can also be classi ed according to the number of similar-
There are two possible outputs when solving the local-
ity matrices and the nature of the MDS model. Classical
ization problem. One is a relative map and the other is an
MDS uses one matrix. Replicated MDS uses several matri-
absolute map. The task of nding a relative map is to nd an
ces, representing distances measurements taken from several
embedding of the nodes into either two- or three-dimensional
subjects or under di eren t conditions. Weighted MDS uses
space that results in the same neighbor relationships as the
a distance model which assigns a di eren t weight to each
underlying network. Such a relative map can provide cor-
dimension. Finally, there is a distinction between deter-
rect and useful information even though it does not neces-
ministic and probabilistic MDS. In deterministic MDS, each
sarily include accurate absolute coordinates for each node.
object is represented as a single point in a multidimensional
Relative information may be all that is obtainable in situa-
space, whereas in probabilistic MDS each object is repre-
tions in which powerful sensors or expensive infrastructure
sented as a probability distribution over the entire space.
cannot be installed, or when there are not enough anchors
We focus on classical metric MDS in this paper. Classical
present to uniquely determine the absolute positions of the
metric MDS is the simplest case of MDS: the data is quanti-
nodes. Furthermore, some applications only require relative
tative and the proximities of objects are treated as distances
positions of nodes, such as in some direction-based routing
in a Euclidean space [15]. The goal of metric MDS is to nd
algorithms. Sometimes, however, an absolute map is re-
a con guration of points in a multidimensional space such
quired. The task of nding an absolute map is to determine
that the inter-point distances are related to the provided
the absolute geographic coordinates of all the nodes. This is
proximities by some transformation (e.g., a linear transfor-
needed in applications such as geographic routing and target
mation). If the proximity data were measured without error
discovering and tracking.
in a Euclidean space, then classical metric MDS would ex-
As we will show below, our method can potentially gener-
actly recreate the con guration of points. In practice, the
ate both results, depending on the number of anchor nodes.
technique tolerates error gracefully, due to the overdeter-
The method rst generates a relative map of the network
mined nature of the solution. Because classical metric MDS
and then transforms it to absolute positions if su cien t an-
has a closed-form solution, it can be performed e cien tly
chors are available. Before we describe the details of our
on large matrices.
method, we rst introduce multidimensional scaling (MDS),
Let p refer to the proximity measure between objects iijwith a focus on classical MDS, which is used to generate the
and j. The Euclidean distance between two points X =i
relative map.
(x ;x ; ;x ) and X = (x ;x ; ;x ) in an m-i1 i2 im j j1 j2 jm
2.1 Multidimensional Scaling (MDS)
Imagine a small cloud of