Security And Robustness Of Localization Techniques For Emergency Sensor Networks

Recent advancement in radio and processor technology has seen the rise of Wireless Sensor Networks (WSN) as a reliable and cost-effective tool for real-time information gathering and analysis tasks during emergency scenarios like natural disasters, terrorist attacks, military conflicts, etc. Post-deployment localization is extremely important and necessary in these applications. But, current distributed localization approaches are not designed for such highly hostile and dynamic network conditions. This dissertation studies the adverse effects of factors like cheating behavior, node disablement and measurement inconsistencies on the corresponding localization protocols and attempts to provide simple and efficient solutions in order to overcome these problems. The first problem addressed in this dissertation is, how to perform efficient distance-based localization in the presence of cheating beacon nodes? This dissertation attempts to answer two fundamental questions in distance-based localization: (i) In the presence of cheating beacons, what are the necessary and sufficient conditions to guarantee a bounded localization error? and (ii) Under these conditions, what class of algorithms can provide that error bound? In this part of the dissertation, it is shown that when the number of cheating beacons is greater than or equal to some threshold, there is no localization algorithm that can guarantee a bounded error. Furthermore, it is also proved that when the number of malicious beacons is below that threshold, a non-empty class of bounded error localization algorithms can be identified. Two secure distance-based localization algorithms are outlined and their performance is verified using simulation experiments. The next part of the dissertation underscores the lack of fault-tolerance in existing localization protocols and proposes simple mechanisms to overcome this problem. Sensor node disablement adversely affects the overall node deployment distribution and the efficiency of localization techniques that depend on this distribution, for example, signature-based techniques. In order to improve the fault-tolerance in these schemes, it is important to first construct a probabilistic model for node disablement. In this direction, the phenomenon of sensor node disablement is modeled as a stochastic time process. A novel deployment strategy that non-uniformly deploys sensor nodes over the monitored area is also outlined. Then, a fault-tolerance related improvement to existing localization schemes is proposed, which discards observations from unhealthy groups of nodes during the localization process. In order to overcome the complexity concerns, a simple signature-based technique, called ASFALT, is also proposed. ASFALT estimates the target location by first predicting distances to known location references using the underlying node distribution and a simple averaging argument. Extensive measurements from simulation experiments verify the fault-tolerance and performance of the proposed solutions. In the final part of this dissertation, the problem of efficiently mitigating inconsistencies in location-based applications is addressed. Inconsistencies in location information, caused by cheating behavior or measurement errors can be modeled using a weighted, undirected graph and a cheating location function that can assign incorrect locations to the nodes or a cheating (but verifiable) distance function that can assign inconsistent distances to edges. In either case, an edge relation where the assigned edge distance is not within some very small factor of the Euclidean distance between the connecting nodes represents some inconsistency and is referred to as an inconsistent edge. The problem of efficiently mitigating location inconsistencies in the network can then be formulated as an optimization problem that determines the largest induced subgraph (obtained by eliminating a subset of vertices) containing only consistent edges. Two optimization problems can be stated. The first maximizes the number of vertices in the consistent subgraph, while the second maximizes the number of consistent edges in the consistent subgraph. Combinatorial properties including hardness and approximation ratio for these problems are studied and intelligent solution strategies are proposed. A comparative analysis that verifies the practical efficiency of these algorithms by using measurements from simulation experiments is also presented.