Universal Rigidity: Towards Accurate and Efficient Localization of Wireless Networks
Universal Rigidity: Towards Accurate and Efficient Localization of Wireless Networks
复制标题
DOI：
10.1109/infcom.2010.5462057
复制
发表时间：
2010-03
期刊：
影响因子：
--
通讯作者：
Zhisu Zhu;A. M. So;Y. Ye
中科院分区：
文献类型：
--
作者：
Zhisu Zhu;A. M. So;Y. Ye
无线自组织网络和传感器网络中的一个基本问题是确定节点的位置。通常，这样的问题是复杂的节点的位置不能唯一确定的存在。大多数现有的工作使用刚性理论的整体刚性的概念来解决非唯一性问题。然而，这样的概念并不完全令人满意，因为已经表明，即使已知网络定位实例是全局刚性的，确定节点位置的问题通常仍然是棘手的。在本文中，我们建议使用普遍刚性的概念来弥合这种脱节。虽然泛刚性的概念比全局刚性的概念更具限制性，但它涵盖了一大类网络，并且与网络局部化问题的有效可解性更相关。具体而言，我们表明，无论是决定一个给定的网络定位实例是否普遍刚性的问题，并确定一个普遍刚性的实例的节点位置的问题，可以有效地解决使用半定规划（SDP）。然后，我们给出了泛刚性实例的各种构造。特别是，我们表明，三边图是一般普遍刚性的，从而证明不仅是丰富的普遍刚性的实例类，但也有事实，三边图具有更强的几何性质比以前已知的。最后，我们应用我们的结果来设计一种新型的边缘稀疏启发式算法，该算法可以减少输入网络的大小，同时可以证明保留其原始的本地化属性。这种启发式的应用之一是加快现有的凸优化的定位算法。仿真结果表明，我们的加速方法在准确性和计算时间方面都与现有方法相比非常有利。
A fundamental problem in wireless ad-hoc and sensor networks is that of determining the positions of 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 paper, 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. Finally, we apply our results to design a novel edge sparsification heuristic that can reduce the size of the input network while provably preserving its original localization properties. One of the applications of such heuristic is to speed up existing convex optimization-based localization algorithms. Simulation results show that our speedup approach compares very favorably with existing ones, both in terms of accuracy and computation time.