Localization and location verification in sensor networks

Sensor networks are still in need of efficient algorithms to bootstrap and maintain network operation in order for them to become a practical technology. Localization continues to be a challenging problem for such networks. Typically sensor networks consist of thousands of nodes disseminated haphazardly over some area without location awareness. A localization algorithm is thus necessary to locate the nodes for data integrity and network operation. We study what can be achieved using connectivity information alone for localization, in particular, in situations where the network shape is complex. We present our algorithm that exploits the global rigidity property of combinatorial Delaunay complex on selected landmark nodes. The key insight is that the combinatorial Delaunay complex has a unique realization in the plane. Thus an embedding of the landmarks by simply gluing the Delaunay triangles properly recovers the faithful network layout. We also demonstrate how this algorithm can be performed without any knowledge of the network boundary by selecting landmarks according to an incremental Delaunay refinement method. In addition, we illustrate how the algorithm works in 3D where nodes are equipped with altimeters to get altitude information. We then tackle the related problem of location verification where the objective is to correctly assess location claims of un-trusted (potentially compromised) nodes. The mechanisms we introduce prevent a compromised node from generating illicit event reports for locations other than its own. To achieve this goal, in a process we call location certification, data routed through the network is tagged by participating nodes with belief ratings, collaboratively assessing the probability that the claimed source location is indeed correct.