English
导航菜单
学术报告sensor network localization
日期：2011-07-26 阅读：2408
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.
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.
地址：上海市东川路800号电子信息与电气工程学院
邮编：200240 邮箱：seiee@sjtu.edu.cn
Copyright © 2022上海交通大学电子信息与电气工程学院 版权所有
欢迎关注上海交大电院公众号