A Theory of Network Localization - Essay Example

Summary Introduction Position servicing is an essential step for many computer and networking agencies. The concept of sensor networks is generally thought of as futuristic sources of finding the locations. The sensor nodes need to know their locations in order to detect and record events and to route packets using geometric routing. Manual configuration and location handling is a primitive method to determine the location of a node. However, this is unlikely to be feasible for large-scale deployments and scenarios in which nodes move often. GPS is another possibility, however it is costly in terms of both hardware and power requirements. Furthermore, since GPS requires line-of-sight between the receiver and satellites, it may not work well in buildings or in the presence of obstructions such as dense vegetation, buildings, or mountains blocking the direct view to the GPS satellites. Recently, novel schemes have been proposed to determine the locations of the nodes in a network where only some special nodes (called beacons) know their locations. In these schemes, network nodes measure the distances to their neighbors and then try to determine their locations. The process of computing the locations of the nodes is called network localization. Although the designs of the previous schemes have demonstrated great engineering ingenuity and their effectiveness in certain settings verified through extensive simulations, some fundamental questions have not been addressed. As a result, the previous schemes are mainly heuristic-based and a full theoretical foundation of network localization is still lacking. The problem of network localization in which some nodes know their locations and other nodes determine their locations by measuring the distances to their neighbors was investigated. Here is the process. Formulation of the Network Localization Problem The study was undertaken to find out what were the precise conditions required for unique network localizability. To find this out a network localization problem was formulated. Beginning with a network N in real d-dimensional space (where d 2 or 3) consisting of a set of m > 0 nodes labeled 1 through m that represent special "beacon" nodes together with n - m > 0 additional nodes labeled m + 1 through n that represent ordinary nodes. Each node is located at a fixed position in Rd and has associated with it a specific set of "neighboring" nodes. The essential property we will require in this paper is that the definition of a neighbor be a symmetric relation on {1, 2,,n} in the sense that node j is a neighbor of node i if and only if node i is also a neighbor of node j. Under these conditions, N's neighbor relationships can be conveniently described by an undirected graph GN = (V, EN) with vertex set V {1, 2,...,n} and edge set EN defined so that (i, j) is one the graph's edges precisely when nodes i and j are neighbors. We assume throughout that GN is a connected graph. The network localization problem with distance information is to determine the locations pi of all nodes in Rd given the graph of the network GN, the positions of the beacons pj, j {1, 2, ...,m} in Rd, and the distance N =(i, j)between each neighbor pair (i, j) EN. Solvability Solvability of the following theorem depends on the global rigidity. . Global Rigidity Global Rigidity can be explained by the following theorem. The formation Fq is generically globally rigid if every sufficiently small perturbation q of p creates a globally rigid formation Fq. A graph G is redundantly rigid in Rd if the removal of any single edge results in a graph that is also generically rigid in Rd. Fig. 3 suggests, a graph needs to be generically redundantly rigid to ensure generic global rigidity. In grounded graphs each vertex represents a network node and two vertices in the graph are connected if the distance between the two is known; that is, when the distance between the two nodes is measured or when the two nodes are beacon nodes and their distance is implicitly known. So a network has a unique localization if and only if its corresponding grounded graph is generically globally rigid. To check if a network in the plane is unique localizable, the corresponding grounded graph just needs to be check if it is 3-connected and redundantly rigid. By setting conditions and inductive sequences, unique localizable networks both in the plane and in 3-space were also checked. A network with a bi-connected grounded graph is uniquely localizable if two-hop neighbors are connected, e.g., by doubling the range of distance measurements in a sensor network. The resulting figures and graphs can assure any designer of a network that the constructed network is uniquely localizable, thus avoiding expensive trial-and-error procedures. Globally Rigid Graphs To find out the computational complexity of network localization, analysis of the complexity of realization of globally rigid graphs was done. For a realistic formulation of the realization problem it is required that the edge lengths be noisy measurements of underlying edge lengths subject to bounded errors. With a probability of 1, these error-corrupted edge lengths did not correspond to realizable weights causing this to become an approximation problem i.e., finding an assignment of coordinates for the graph vertices so that the resulting discrepancies with the noisy weights are below a tolerance parameter. By using a reduction from set partition, it can be shown that realization of globally rigid weighted graphs with exact, edge weights is still hard. To construct the reduction real numbers are used which could potentially be irrational. Unit Disk Graphs Arbitrary globally rigid graphs may not necessarily be the best concept; therefore Unit Disk Graphs were also used. The construction if Unit Disk Graphs relies on a folding fan construction in which pairs of nodes close to each other in the unique realization may possibly not have an edge between them. In these kinds of graphs a distance measurement is present between any pair of sensors if they are within some disk radius parameter r of each other. However even when limited to this idealized class of graph, localization is still NP-hard. To avoid precision issues involving irrational distances, input to the problem is presented with the distances squared was assumed. A decision version of the localization problem is considered which is called Unit Disk Graph Reconstruction. This problem essentially finds out if a particular graph with given edge lengths can be physically realized as a unit disk graph with a given disk radius in two dimensions. Random Geometric Graphs in the Plan To find the complexity of network localization in typical network deployment scenarios Random Geometric Graphs in the Plane were studied. Geometric graphs are defined in terms of point formations. By applying the 3-connectivity condition for global rigidity and using a result that 6-connectivity is sufficient for global rigidity in the plane, it was concluded that GN(r) is globally rigid with high probability for some Trilateration Graphs Furthermore, the density dependent average-case complexity of network localization in realistic settings like sensor networks and study a class of graphs in the plane called trilateration graphs were explored. A simple localization protocol was studied for random sensor networks we call ITP. A random sensornet Sn(r) is a sensornet of n sensors with sensing radius r placed at random on [0, 1]2 by a two-dimensional Poisson point process. A beacon is a sensor that knows its position. Simulations The random geometric graphs in 3-space were simulated by generating points randomly in [0, 1]3 and placing four beacons in the center of the unit cube within sensing range of each other. Then the ITP was simulated by localizing nodes in computational rounds in which the positions for all nodes connected to four nodes with known position were determined. The simulation was terminated when a round did not determine the position of any node. For three values of r the percentages of nodes whose positions can be determined were tracked. An increasingly sharp phase transition in the percentage of localizable nodes as we increase n was observed as a result of the first simulation. In the second simulation, the smallest radius at which the percentage of localizable nodes is greater than 95 percent was calculated. The analytical asymptotic resulted more accurately models actual behavior as n increased. The difference for small n can be explained by the contribution of logarithmic terms in the localization probability that becomes significant when n is small. The last simulations investigated the number of computational rounds necessary to localize all nodes that can be localized. At an observation for n 2; 000 the percentage of localized nodes at a given step increased dramatically with modest increases in sensing radius. As a result of the simulations, it was found that the trilateration graphs were uniquely localizable and the locations of the nodes can be computed efficiently. Also it was found that random geometric graphs are trilateration graphs with high probability if a certain node density or communication radius is reached. Conclusion The unique localization of networks from distance measurements shares a number of features with work in several other active fields of study: rigidity and global rigidity in frameworks, the coordination of formations of automonous agents, and geometric constraints in CAD. Specifically, a formation and then a graph for each network were constructed so that the localization problem for the network was uniquely solvable, almost always, if and only if the corresponding graph was generically globally rigid. From these connections, specific results were drawn which showed that the trilateration networks were uniquely localizable for almost all initial locations. The localization problem with precise distance is not in general numerically well-posed since, even if it is solvable with the given data, it may be unsolvable with data arbitrarily close to that which is given. In practical terms, this means that special attention must be paid to the computation process and to assessing the significance of approximate solutions. It also means that only graphs which are generically globally rigid are capable of having computationally stable solutions for given data sets. However, it is realized that even approximate solutions are hard to compute due to the hardness of the localization problem. Work Cited From James Aspenes, Tolga Eren, et al. (DECEMBER 2006), "A Theory of Network Localization", IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 5, NO.12, Accessed on July 16, 2007. Read More