Towards a Theory of Robust Localization Against Malicious Beacon Nodes
Towards a Theory of Robust Localization Against Malicious Beacon Nodes
复制标题
DOI：
10.1109/infocom.2008.197
复制
发表时间：
2008-04
期刊：
影响因子：
--
通讯作者：
S. Zhong;Murtuza Jadliwala;S. Upadhyaya;C. Qiao
中科院分区：
文献类型：
--
作者：
S. Zhong;Murtuza Jadliwala;S. Upadhyaya;C. Qiao
在存在恶意信标节点的情况下定位是无线网络中的一个重要问题。虽然在这个问题上已经取得了很大的进展，但一些基本的理论问题仍然没有得到解答：在恶意信标节点存在的情况下，什么是保证二维位置估计误差有界的充要条件？在这些充要条件下，哪类定位算法可以提供这个误差界？在本文中，我们试图回答这些问题。具体地说，我们证明了，当恶意信标的数量大于或等于某个阈值时，不存在可能存在有界误差的定位算法。此外，当恶意信标的数量低于该阈值时，我们识别出一类能够确保定位误差有界的定位算法。我们还概述了这类算法中的两种，其中一种算法在最坏的情况下保证在多项式时间内(提供信息的信标数)完成，另一种算法基于启发式算法，实际上是有效的。为了完备性，我们还将上述结果推广到三维情形。实验结果表明，该方法具有很好的定位精度和计算效率。
Localization in the presence of malicious beacon nodes is an important problem in wireless networks. Although significant progress has been made on this problem, some fundamental theoretical questions still remain unanswered: in the presence of malicious beacon nodes, what are the necessary and sufficient conditions to guarantee a bounded error during 2-dimensional location estimation? Under these necessary and sufficient conditions, what class of localization algorithms can provide that error bound? In this paper, we try to answer these questions. Specifically, we show that, when the number of malicious beacons is greater than or equal to some threshold, there is no localization algorithm that can have a bounded error. Furthermore, when the number of malicious beacons is below that threshold, we identify a class of localization algorithms that can ensure that the localization error is bounded. We also outline two algorithms in this class, one of which is guaranteed to finish in polynomial time (in the number of beacons providing information) in the worst case, while the other is based on a heuristic and is practically efficient. For completeness, we also extend the above results to the 3-dimensional case. Experimental results demonstrate that our solution has very good localization accuracy and computational efficiency.