Time: 3:00-4:00 July 27th
Wednesday
Lecture
Room: 520 Pao Yue-Kong Library
Title: Rigidity and Localization: An Optimization
Perspective
Abstract:
A fundamental problem in wireless ad-hoc and
sensor networks is that of determining the
positions of sensor nodes. Often, such a problem is complicated by the presence of nodes whose positions
cannot be uniquely determined. Most
existing work uses the notion of global rigidity from rigidity theory to address the non-uniqueness issue.
However, such a notion is not entirely
satisfactory, as it has been shown that even if a network localization instance is known to be globally rigid, the
problem of determining the node positions
is still intractable in general. In this talk,
we propose to use the notion of universal rigidity to bridge such disconnect. Although the notion of universal rigidity is
more restrictive than that of global
rigidity, it captures a large class of networks and is much more relevant to the efficient solvability of the
network localization problem. Specifically,
we show that both the problem of deciding whether a given network localization instance is universally rigid
and the problem of determining the node
positions of a universally rigid instance can be solved efficiently using semidefinite programming (SDP). These
results can be viewed as sufficient
conditions for a certain SDP to have a unique low rank solution. Then, we give various constructions of
universally rigid instances. In particular,
we show that trilateration graphs are generically universally rigid, thus demonstrating not only the
richness of the class ofuniversally rigid instances, but also the fact that
trilateration graphs possess much stronger
geometric properties than previously known. Based on the theory, we introduce an edge sparsification procedure
that can provably preserve the
localizability of the original input, but the SDP problem size is greatly reduced.
