--------------------------------------------------------------------------------
Comments on SPASELOC: A Review.
--------------------------------------------------------------------------------
Michael Carter, Holly Jin, Michael Saunders, Yinyu Ye,
SPASELOC: An Adaptive Subproblem Algorithm for Scalable Wireless Sensor Network Localization, SIAM Journal on Optimization, 2006
https://www.stanford.edu/group/SOL/papers/SpaseLoc.pdf

Heuristic solution to a sensor-network localization problem, proposed by Carter & Jin, is limited to two Euclidean dimensions and applies semidefinite programming (SDP) to little subproblems. A large network is partitioned into smaller subnetworks (as small as one sensor) and then semidefinite programming and heuristics called SPASELOC are applied to localize each and every partition by two-dimensional distance geometry. Their partitioning procedure is one-pass, yet termed iterative; a term applicable only in so far as adjoining partitions can share localized sensors and anchors (absolute sensor positions known
a priori). But there is no iteration on the entire network, hence the term "iterative" is perhaps inappropriate. As partitions are selected based on "rule sets" (heuristics, not geographics), they also term the partitioning adaptive. But no adaptation actually occurs once a partition has been determined.

One can reasonably argue that semidefinite programming methods are unnecessary for localization of large sensor networks. In the past, these nonlinear localization problems were solved algebraically and computed by least squares solution to hyperbolic equations; called multilateration (literal meaning: having many sides, the shape of a geometric figure formed by nearly intersecting lines of position. Therefore, in navigation systems, obtaining a fix from multiple lines of position.) Indeed, practical contemporary numerical methods for global positioning by satellite (GPS) do not rely on semidefinite programming.

The beauty of semidefinite programming as relates to localization lies in convex expression of classical multilateration: So & Ye showed that the problem of finding unique solution, to a noiseless nonlinear system describing the common point of intersection of hyperspheres in real Euclidean vector space, can be expressed as a semidefinite program via distance geometry.

But the need for SDP methods in Carter & Jin is also a question logically consequent to their reliance on complicated and extensive heuristics for partitioning a large network and for solving a partition whose intersensor measurement data is inadequate for localization by distance geometry. While partitions range in size between 2 and 10 sensors, 5 sensors optimally, heuristics provided are only for 2 spatial dimensions (no higher-dimensional algorithm is proposed). For these small numbers it remains unclarified as to precisely what advantage is gained over traditional least squares.

Partitioning of large sensor networks is a logical alternative to rapid growth of SDP computational complexity with problem size. But when impact of noise on distance measurement is of most concern, one is averse to a partitioning scheme because noise-effects vary inversely with problem size. Since an individual partition's solution is not iterated in Carter & Jin and is interdependent with adjoining partitions, we expect errors to propagate from one partition to the next; the ultimate partition solved, expected to suffer most.

Heuristics often fail on real-world data because of unanticipated circumstances. When heuristics fail, generally they are repaired by adding more heuristics. Tenuous is any presumption, for example, that distance measurement errors have distribution characterized by circular contours of equal probability about an unknown sensor-location. That presumption effectively appears within Carter & Jin's optimization problem statement as affine equality constraints relating unknowns to distance measurements that are corrupted by noise. Yet in most all urban environments, this measurement noise is more aptly characterized by ellipsoids of varying orientation and eccentricity as one recedes from a sensor.
(Figure, courtesy Polaris Wireless, illustrates contours of equal sensor-location uncertainty.  To reject this notion is like siding with Copernicus; to accept it is the epiphany of Kepler.)

Each unknown sensor must therefore instead be bound to its own particular range of distance, primarily determined by the terrain. The nonconvex problem we must instead solve is:

Problem (SNL)

find x_i , x_j
subject to lo_bound_d_ij <= ||x_i - x_j||^2 <= hi_bound_d_ij for all ij

where x is position, d is distance square. (Recall, this can be realized as a semidefinite program.) By establishing these individual upper and lower bounds, orientation and eccentricity can effectively be incorporated into the problem statement.

Generally speaking, there can be no unique solution to the sensor-network localization problem because there is no unique formulation; that is the art of optimization. Any optimal solution obtained depends on whether or how the network is partitioned and how the problem is formulated. When a particular formulation is a convex optimization problem, then the set of all optimal solutions forms a convex set containing the actual or true localization. Measurement noise precludes equality constraints representing distance. The optimal solution set is consequently expanded; necessitated by introduction of distance inequalities admitting more and higher-rank solutions. Even were the optimal solution set a single point, it is not necessarily the true localization because there is little hope of exact localization by any algorithm once significant noise is introduced.

Carter & Jin gauge performance of their heuristics to the SDP formulation of author Biswas whom they regard as vanguard to the art.
https://www.stanford.edu/~yyye/adhocn4.pdf
https://www.stanford.edu/~yyye/combined_rev3.pdf

Biswas posed localization as an optimization problem minimizing a distance measure. Intuitively, minimization of any distance measure yields compacted solutions; precisely the anomaly motivating Carter & Jin. Their two-dimensional heuristics outperformed Biswas' localizations both in execution-time and proximity to the desired result. Perhaps, instead of heuristics, Biswas' approach to localization can be improved:

Biswas, Liang, Toh, Ye, Semidefinite Programming Approaches for Sensor Network Localization With Noisy Distance Measurements, IEEE, 2006.

The sensor-network localization problem is considered difficult. Rank constraints in optimization are considered more difficult. In Convex Optimization & Distance Geometry, Meboo, 2007, I present the localization problem as a semidefinite program (equivalent to (SNL)) having an explicit rank constraint which controls Euclidean dimension of an optimal solution. I show how to achieve that rank constraint only if the feasible set contains a matrix of desired rank; a problem formulation extensible to any spatial dimension.

https://meboo.convexoptimization.com/images/wedparty/Jin4.jpg

This image in the link represents a standardized problem proposed by Carter & Jin to test sensor network localization algorithms: Five vertical middle (red) nodes are anchors; the rest are sensors. Anchors are chosen here to cause failure in algorithms that depend on sensors within the convex hull of anchors. Radio range of bottom-left sensor is indicated by the arc. Measurable distance is represented by dot . in the corresponding connectivity matrix, whereas hollow dot o indicates distance between anchors (known to very high accuracy) while 0 denotes zero distance. Question marks ? indicate unknown distance; the graph is quite incomplete.

https://meboo.convexoptimization.com/images/wedparty/5lattice.jpg

Here, in this linked image, is a solution by convex iteration (implementing a rank constraint). The fact that the localized sensors are not compacted (not clustered together) is worthy of note. Minimization of any distance measure will compact an optimal solution. Many contemporary statements of the sensor network localization problem adhere to minimization of some distance measure. I advise against that to avoid the compaction phenomenon. Problem (SNL), instead, is my recommended statement of the sensor network localization problem.

The legacy of Carter & Jin is a sobering demonstration of the need for more efficient methods for solution of semidefinite programs, while that of So & Ye is the bonding of distance geometry to semidefinite programming. Elegance of our semidefinite problem statement for a sensor-network localization problem in any dimension should provide some impetus to focus more research on computation intensity (we need a simplex-like solver for SDP).

Read more...