Sensor network localization with imprecise distances
Introduction
In sensor networks, sensors’ location information is vital in location-aware applications and influences network performances when algorithms like geographic routing are used. Hence, localization is crucial in the development of low-cost sensor networks where it is not feasible for all the nodes’ locations to be directly measurable via GPS or other similar means. The locations of some of the nodes have to be inferred by utilizing estimated distances to their nearby nodes. Hence, as pointed out in [7], the first and the most fundamental phase of most localization algorithms [9], [10], [11] is the determination of the distances between sensor nodes whose locations are to be computed and “anchor nodes”. An anchor node is a node whose location is assumed to be known during the current computation. An anchor node may be a node with a GPS device, or a node with a tentative estimated location in an iterative computation process [11], or a point in the trajectory of a mobile beacon [13], etc. Distances between sensors and anchors can be obtained via direct measurements if they are within sensing range of one another; otherwise, approximation methods such as sum-dist [7], [11] and DV-hop [9], [10] can be used to estimate the sensor–anchor distances. No matter which method is used to obtain the distances, the data acquired are usually imprecise compared with the true distances because of measurement noise and estimation errors. Because the true distances between nodes are interdependent, these inaccuracies have undesirable consequences of causing inconsistency with respect to geometric relations, and sometimes may even cause localization algorithms to collapse. For example, in a 2D scenario, triangulation fails due to nonexistence of feasible solutions when the distances are not consistent with the fact that all sensors live on a plane.
However, because there are geometric and algebraic relations among the true distances between the nodes, the errors associated with these imprecise distances are not independent. It follows that one can exploit this dependence by seeking, for example, to find that set of errors which would yield true distances as close as possible (in some metric) to the measured imprecise distances. These errors are then associated with the imprecise distances to correct those distances and use the corrected values to provide a nominal location for the sensor whose position is to be determined, by lateration [9], [10], min–max optimization [11], or any of the other appropriate methods.
In this paper, a novel technique is presented which describes the geometric relations among the sensor–anchor distances as one or multiple quadratic equality constraints. The key step is to use the Cayley–Menger determinant that is defined in the following section. Although inequality constraints usually variations of the triangle inequality where the sum of the lengths of two sides of the triangle must be greater than the third have been discussed before [15], the equality constraints reported in this paper disclose more insightfully the dependency among distances between nodes. Furthermore, these equality constraints can be utilized to estimate errors in the measured or computed distances. One specific estimation approach presented in this paper is to solve a least squares problem where the objective is to minimize the sum of the squared errors in the distances that are measured or computed by a sensor.
The rest of the paper is organized as follows. In Section 2, the definition of the Cayley–Menger determinant is introduced as well as related classic results in Distance Geometry. In Section 3, geometric relations among nodes’ positions are formulated as quadratic constraints by using the Cayley–Menger determinant. In Section 4, we show that errors in the imprecise distance information can be estimated by solving an optimization problem. In Section 5, we provide a computational example.
Section snippets
Cayley–Menger determinants
The Cayley–Menger matrix of two sequences of n points, and , is defined aswhere , is the Euclidean distance between the points and . The Cayley–Menger bideterminant [3] of these two sequences of n points is defined as
This determinant is widely used in distance geometry theory [1], [3] which
Geometric relations as equality constraints
In this section, we will illustrate how one can describe the geometric relations among the distances between nodes as algebraic constraints, which are, to be precise, quadratic algebraic equations. We first consider the two-dimensional case, and the result will then be generalized to the three-dimensional case.
An optimization problem
Given all the algebraic constraints obtained in the last section, we now try to estimate the error in the inaccurate distances between sensor nodes and anchor nodes. One approach is to formulate the problem as a least squares problem to minimize the sum of the squared errors. Other objective functions are also adoptable depending on the specific application context. As discussed in [8], the least squares approach is sometimes not the most appropriate one to use. We use it here simply because of
A computational example
In this section, we will give an example to demonstrate the steps introduced in previous sections to solve the localization problem. We consider the simplest scenario in 2D as depicted in Fig. 1 where sensor 0, which is the sensor we want to localize, can measure its distances to three beacons 1, 2 and 3 whose coordinates are , and respectively. The noisy distance measurements acquired by sensor 0 are , and .
First, we will determine the
Conclusions
This paper introduces the Cayley–Menger determinant as an important tool for formulating the geometric relations among node positions in sensor networks as quadratic constraints. It also discusses solutions to optimization problems to estimate the errors in the inaccurate measured distances between sensor nodes and anchor nodes. The solution of the optimization problem, when used to adjust noisy distance measurements, gives a set of distances between nodes which are completely consistent with
References (16)
- et al.
Distributed localization in wireless sensor networks: a quantitative comparison
J. Comput. Networks
(2003) - et al.
Localized positioning in ad hoc networks
J. Ad Hoc Networks
(2003) Theory and Applications of Distance Geometry
(1953)- H.S.M. Coxeter, Introduction to Geometry, second ed., Wiley, New York, 1969, p....
- et al.
Distance Geometry and Molecular Conformation
(1988) Least squares with a quadratic constraint
Numer. Math.
(1981)Numerical methods for solving linear least squares problems
Numer. Math.
(1965)- et al.
Quadratically constrained least squares and quadratic problems
Numer. Math.
(1991)
Cited by (100)
Cooperative Localization Using Received Signal Strength and Least Squares Estimation Methods
2023, Proceedings of the 2023 13th International Conference on Indoor Positioning and Indoor Navigation, IPIN 2023NLOS Mitigation Algorithm by Distance Geometric Constrain for Mine-Used Underground Monorail Crane Localization
2023, IEEE Transactions on Instrumentation and MeasurementStability analysis method and application of multi-agent systems from the perspective of hybrid systems
2021, Measurement and Control (United Kingdom)Second-Order Online Nonconvex Optimization
2021, IEEE Transactions on Automatic ControlPeer-to-Peer Relative Localization of Aerial Robots with Ultrawideband Sensors
2021, IEEE Transactions on Control Systems Technology
- 1
The work of Cao and Morse was supported in part, by grants from the US Army Research Office and the US National Science Foundation and by a gift from the Xerox Corporation.
- 2
The work of Anderson was supported by National ICT Australia, which is funded by the Australian Government's Department of Communications, Information Technology and the Arts and Australian Research Council through the Backing Australia's Ability initiative and the ICT Center of Excellence Program.