Towards a Theory of Robust Localization against Malicious Beacon Nodes

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.


Published in:
Proceedings of the 27th IEEE International Conference on Computer Communication (INFOCOM 2008), 1391-1399
Presented at:
27th IEEE International Conference on Computer Communication (INFOCOM 2008), Phoenix, Arizona, USA, April 15-17, 2008
Year:
2008
Publisher:
IEEE Computer Society
Laboratories:


Note: The status of this file is: EPFL only


 Record created 2008-11-18, last modified 2018-03-18

n/a:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)