Abstract-Knc~ing the positions of the nodes in a network is essential to many nest generation perrasive and sensor network functionalities, Although many network Incalkation systems have recently been pmposed and evaluated. there has been no systematic study ofpartially localizable networks, Le., networks in which there exist nodes whose positions cannot be uniquely determined. There is no existing study which correctly identifies precisely which nodes in a network are uniquely localizable and which 3re not. This absence of a sufficient uniqueness condition permits the computation of erroneous positions that may in turn lead applications to produce flawed results. In thi5 paper, in addition to demonstrating the relevance of networks that may not be fully localizable. we design the first framework for two dimensional network lncalization with an efficient component to correctly determine which nodes are 1ocaIizahle and which are not. Implementing this system, we conduct comprehensive evaluations of network localizahility, providing guidelines for both network design and deployment. Furthermore, we study an integration of traditional geographic routing with geographic routing over virtual coordinates in the partially localizable network setting. We show that this novel cross-layer integration yields good performance, and argue that such optimbations will be likely he necessary to ensure acceptable application performance in partially localizable networks, sensors need to know their positions; in order to detect events and track targets, the uackinp sensors need to know their positions to pinpoint the movement of the tagets and to implement efficient state transfer (e.g.. [45]). Given the importance of knowing the positions of the network nodes, much research effort has been invested into network localization, which refers to the process of determining these positions. Two straightforward methods to achieve locaiization are manual configuration and the Global Positioning System (GPS) [IS] Motivated by above observations. in this paper we propose the concept of the pctrtially localizable n e t~w r k (PLN). These are networks in which not ail nodes can be uniquely localized. We believe that partially localizable networks are likely to be the most prevalent networks in practice. The first major challenge in studying PLNs is to identify the uniquely localizable nodes. In this paper. we present a sufficient graph-theoretic condition for a node to be uniqueky localizable. Applying the condition, we identify localizable nodes by efficiently partitioning the network into components which are redMndantl?. rigid and triconnecred. Coordinates for the nodes in these components can then be uniquely determined subject to error due to noise in the distance measurements. We note that in simulations under realistic conditions. nodes determined to be uniquely localizable by our tests are only very rarely rendered ambiguous by errors in edge length measurements as described in [251. Since our algorithm identifies localizable nodes efficiently, we are also able to use it to thoroughly explore appropriate network parameters in order to achieve a desired localizationdependent application goal. For the first time, it is possible to observe exactly haw many nodes one can expect to be localizable in medium density and sparsely connected random networks. Using our tool, we are also able to guide the deployment of networks by adding nodes systematically to the network so as to increase the proportion of localizable nodes. As applications progress and adapt to operation in PLNs, our tool will undoubtedly find uses in more sophisticated planning and analysis tasks. The second major challenge in studying PLNs is to determine how to best make use of nodes that cannot be uniquely localized. One possibility is for applications to simply ignore such nodes as if they do not exist. but this is clearly a worst-case option. The application setting in which we study this issue is geographic routing over PLNs. We propose an integration of geographic routing without location information and standard geographic routing. We show that hy using virtual localization techniques for the non-localizable nodes: one can achieve a higher routing success rate between localized nodes than by ignoring non-localizable nodes. The contributions of this paper can be summarized as We propose the novel PLN paradigm. We develop efficient algorithms to ascertain which nodes can be uniquely localized and which cannoc. Implementing our systcm. we conduct comprehensive experimental evaluations of network localizability: and describe implications on both network design and on the use of novel network deployment algorithms. We argw that a cross-layer approach involving feedback between the localization layer and the application layer should be adopted in PLNs. As an example of this. we study an integration of geographic routing without locaiion information and standard geographic routing. We show that this cross-layer integration improves network per'formance. The rest of this paper is organized as follows. In Section 11, we formulate the unique localizability problem, derive canditions for a node to be uniquely Localizable, and present our algorithm to identify the nodes that can be localized. In Section 111, we apply the algorithm to explore the parameter space of the localization problem. In Section IV, we present our algorithms for geographic routing in PLNs. We discuss related work in Section V. Our conclusions and future work are described in Section VI.  In the network-localizability-problem formulation, we have a network in real d-dimensional space { d = 2 or 3) consisting of a set of R? > 0 nodes labeled 1 through m which represent "beacons" together with .n -m > 0 additional nodes labeled 7 n + 1 through n. which represent sensors. Each node is located at a fixed position in Wd and has associated with it a specific sei of "neighboring" nodes. Let G = { V , E } be the network with vertex set V = {l, 2 , . . . , n} and edge set E defined so that ( i , j ) is one of the graph's edges precisely in the case h a t nodes i and j are neighbors. The netuiork localization probletn with emcl diJtance information is to determine the locations p i of all network nodes in Rd given the graph of the network 6, the positions of the beacons p j ; j E (1: ' 1: . . . ~ m } in Rdl and the distance between each neighbor pair ( i j ) E E. The n e h r f o r~-b c a l i , . a b~~~~ problem is to determine if there 314 is exactly one set of vectors {pmtl:. . .yn} in Rd which is consistent with the given data G. ~I~, I J~. , 1 . , p r , L ) . and If there is exactly one set, we say that the network is localizable. We can see that the network-localizability problem is closely related with the Euclidean graph realization problem in which coordinates are assigned to vertices of a weighted graph such that the distance between coordinates assigned to nodes joined by an edge is equal to the weight of the edge. Cleariy7 if the graph G of a network is uniquely realizable. the network is localizable up to global rotations. translations, and reflections. However. this connection to Euclidean graph realization is still incomplete. The network-localizability problem is not equivalcnt to the unique realizability of 6. but of a graph with a slightly layer edge set that includes edges from every beacon to every other. We call this augmented graph the p1'01~7ckd prupli of rhe network. In the graph abstraction. an edge represents a distance constraint between its endpoints. Since the distance between each pair of beacons is known. edges must exist between all pairs of beacons. This observation is crucial in order to capture all available constraints in the network. If he grounded graph of lhe network is uniquely realizable. then the network is uniquely localizable up to rotations, translations, and reflections. In two dimensions, three non-collinear beacons are necessary to resolve the global orientation of the network to a single possibility. Now that we have defined the network-localizahility problem and its grounded graph abstraction, we can proceed to describe the precise conditions for unique localizabitity. We must first state that the following is a generic characterization of unique realizability, i.e., one that holds for aI1i2osl all configurations of network nodes. What this means is that for all network configurations other than a set of configurations containing certain degeneracies among node positions, unique localizabiIity is a graph-theoretic property of the network connectivity and independent of the positions of the nodes. Given this fact, randomization aids in the classification of networks as uniquely realizable. For any reasonable prohability distribution on node positions, degenerate configurations have zero probability of appearing, and one can be justified in assuming the network nodes to be in general position. It is worth noring however, that in the presence of errors in edge length measurements. configurations indistinguishable from degenerate may very well occur. We begin wid1 descriptions of the three ways in which a graph can fail to have a unique realization. A realization of a graph may be subject to deformations that allow the coordinates assigned to vertices to vary continuously while simultaneously satisfying all of the edge constraints. This non-uniqueness can either be continuous or discontinuous. A graph is,oexible if it admits a continuous deformation other than globaI rotation. translation. and reflection; otherwise. it is caIled rigid. Flexible graphs have an infinite number of realizations. Fig. 1 shows a flexible network. The figure also provides a counter example to the claim that if a node has three nodr-disjoint paths to three distinct beacons. it is uniquely localizable. Fig. 1
A recent paper REF ] discusses the notion of localizable nodes in a graph.
Network localization in partially localizable networks
Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies.
Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies.
Computer Science