Rigidity and Localization: An Optimization Perspective

Anthony Man-Cho So
The Chinese University of Hong Kong


Monday, March 15, 2010
5:00 - 6:00 PM
Terman Engineering Center, Room 453


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). 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 of universally 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.

---

Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html