Identifying code - 11/19/2010

Niloofar Fazlollahi

Abstract: Identifying codes have been proposed as an abstraction for implementing monitoring tasks such as indoor localization using wireless sensor networks. In this approach, sensors' radio coverage overlaps in unique ways over each identifiable region, according to the codewords of an identifying code. While connectivity of the underlying identifying code is necessary for routing data to a sink, existing algorithms that produce identifying codes do not guarantee such a property. In this work, we show that the decision problem regarding existence of a connected identifying code is NP-complete. As such, we propose a novel polynomial-time approximation algorithm called ConnectID that transforms any identifying code into a connected version that is also an identifying code and is provably at most twice the size of the original.

We provide an efficient implementation of ConnectID. We prove a cubic complexity in the graph size using our implementation.

We analyze the performance of ConnectID when the input identifying code is robust to at most r failures, thus leading to an r-robust connected identifying code. Our analysis based on the error correcting codes shows that the robust connected identifying code size is significantly less than twice that of the original identifying code. We evaluate the performance of ConnectID on various random graphs, and our simulations show that the connected codes generated are actually at most 25% larger than their non-connected counterparts. Our simulations with robust input identifying codes reveal that robustness provides connectivity for free.

-- JiaxiJin - 18 Nov 2010