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.

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

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
...Show more