Disjoint Identifying-Codes for Arbitrary Graphs- 08/19/2005

Moshe Laifenfeld

Identifying codes have been used in a variety of applications, including sensor-based wireless location detection in harsh environments. In such applications, a user determines his location through a unique signature (i.e. a codeword in an identifying code) based on sensor transmissions that he can hear. Adding sensors to such a system can increase its robustness at the expense of added signal interference and, consequently, decreased reliability. In this work we propose and develop an alternate approach to maintaining robustness and reliability through the use of "disjoint identifying codes", which reduces inter-sensor interference by dividing a system into physically separate and independent location determining sub-systems. We provide information-theoretic upper and lower bounds on the number of such sub-systems for a given connectivity graph, and we show that these bounds are asymptotically tight for a modification of Hadamard matrices.