Location Detection using Identifying Codes - 07/18/2002

Saikat Ray

Recent advancementments in sensor technology have made it possible to install a network of tiny, low cost sensors on existing infrastructure that is capable of providing real-time information "in situ" in case of a disaster, an essential component for enhancing the safety and effectiveness of recovery operations. Location detection systems form an integral part of such systems to utilize the information provided by the sensor network to the fullest extent by locating the source or extent of hazard and harmonizing the operation by locating and moving the crew optimally. Existing location detection systems are not designed for use in emergency situations and thus lack essential characteristics, such as robustness. Therefore, in this work we propose a novel framework for providing robust location detection, which generalizes current approaches of indoor location detection. The key idea is to allow sensor coverage areas to overlap, instead of keeping them disjoint, but ensure that each position is covered by a unique set of sensors. This design also makes it possible to use physical layers that are not short range, such as RF, without losing resolution. The main design challenge is to position the sensors intelligently so that the number of sensors is minimized. Our approach to this is to model the site as a graph and computing an "identifying code" on this graph. Identifying codes identify vertices of a graph based on the neighbors of a given node. Determination of an optimal identifying code for an arbitrary graph is known to be NP-complete and most of the current work focus on regular graphs. However, it is very hard, if not impossible, to overlay a regular graph onto a given area full of obstacles. Therefore, we have proposed and analyzed a polynomial-time algorithm (N^2 log N) to generate "irreducible" identifying codes for arbitrary topologies. The standard identifying codes are, however, not robust. Therefore, we have generalized identifying codes to incorporate robustness and also extended ID-CODE algorithm to produce r-robust irreducible codes for arbitrary graphs in polynomial time. An r-robust code can tolerate up to 'r' errors. Moreover, in our approach each position is covered by a set of sensors that may include sensors situated far away. This special diversity provides a graceful degradation of the system in contrast to most of the existing systems. The performance of our proposed algorithms has been evaluated through simulations. We used random, connected graphs to model the site. Simulation results show that the codes produced by our algorithms are close to a known theoretical lower bound and hence close to the optimal solution. The talk will be concluded by describing interesting future challenges, both theoretical and technology related, which are essential to materialize our conceptual design.