Localization from mere connectivity

Informations

• Publié par: jjggi
• Nombre de lectures: 121
• Langue: Français

Extrait

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. 201though 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