Research Article
Joint Monitoring and Routing in Wireless Sensor Networks using Robust Identifying Codes
@INPROCEEDINGS{10.1109/BROADNETS.2007.4550425, author={Moshe Laifenfeld and Ar Trachtenberg and Reuven Cohen and David Starobinski}, title={Joint Monitoring and Routing in Wireless Sensor Networks using Robust Identifying Codes}, proceedings={4th International IEEE Conference on Broadband Communications, Networks, Systems}, publisher={IEEE}, proceedings_a={BROADNETS}, year={2010}, month={5}, keywords={}, doi={10.1109/BROADNETS.2007.4550425} }- Moshe Laifenfeld
Ar Trachtenberg
Reuven Cohen
David Starobinski
Year: 2010
Joint Monitoring and Routing in Wireless Sensor Networks using Robust Identifying Codes
BROADNETS
IEEE
DOI: 10.1109/BROADNETS.2007.4550425
Abstract
Wireless Sensor Networks (WSNs) provide an important means of monitoring the physical world, but their limitations present challenges to fundamental network services such as routing. In this work we utilize an abstraction of WSNs based on the theory of identifying codes. This abstraction has been useful in recent literature for a number of important monitoring problems, such as localization and contamination detection. In our case, we use it to provide a joint infrastructure for efficient and robust monitoring and routing in WSNs. Specifically, we provide an efficient and distributed algorithm for generating robust identifying codes with a logarithmic performance guarantee based on a novel reduction to the set k-multicover problem; to the best of our knowledge, this is the first such guarantee for the robust identifying codes problem, which is known to be NP-hard. We also show how this same identifying-code infrastructure provides a natural labeling that can be used for near-optimal routing with very small routing tables. We provide experimental results for various topologies that illustrate the superior performance of our approximation algorithms over previous identifying code heuristics.