Identifying codes - 07/30/2010

Niloofar Fazlollahi

Abstract: First introduced by Mark Karpovsky, identifying codes are a subset of nodes in a given graph (called codewords) that form a unique vicinity (called identifying set) around every node. There is lots of analytical work regarding identifying codes in the literature including: theoretical bounds, construction algorithms for the simplest definition above or other variants. In addition to generic graphs there are some results for specific graph topologies and others for random graphs.

Identifying codes are suggested for various applications in the literature. Examples are fault monitoring in multi-processor networks, location detection in wireless sensor networks or compact routing [1,2]. Authors in [1] have introduced for the first time robust identifying codes: codes that remain identifying even if a certain number of codewords are added or removed from identifying sets. Such codes are a good fit for real world sensor networks where sensor or link failures may happen.

In my research I try to extend application of identifying codes to sensor networks for location detection and routing. In particular we raise the requirement for a connected identifying code. Previous work on location detection in sensor networks using identifying codes have ignored the fact that there should be some sort of connectivity in any network to perform routing. We have proposed an algorithm that constructs a connected identifying code as a superset of an identifying code. We show the number of added codewords does not exceed the number of codewords in the original identifying code (if the original identifying code happens to be connected, in practice the algorithm will add no codeword). We also claim the number of added codewords to the original identifying code is minimum (still to be validated). This work is going to be extended in all or part of the following directions: complexity analysis and implementation design, making the algorithm fully distributed, producing connected robust identifying code, experimental evaluation.

The other topic I am working on is probabilistic analysis of robust identifying codes in random graphs. This is an extension of existing unpublished work by Moshe Laifenfeld. He has provided a lower bound on the number of codewords required in a random graph such that a partial identifying code results with a high probability. My analysis is still incomplete.

[1] Saikat Ray and Rachanee Ungrangsi and Francesco De Pellegrini and Ari Trachtenberg and David Starobinski, "Robust Location Detection in Emergency Sensor Networks", in proceedings of INFOCOM'03 [2] Moshe Laifenfeld, Ari Trachtenberg, Reuven Cohen, David Starobinski, "Joint Monitoring and Routing in Wireless Sensor Networks Using Robust Identifying Codes", Mobile Networks and Applications, Volume 14 , Issue 4 (August 2009)

-- JiaxiJin - 29 Jul 2010