Coverage in Wireless Sensor and RFID Systems

Coverage Problems in Wireless Sensor and RFID Systems

The rapid self-configuration, ease of deployment and small cost of components, coupled with the tremendous potential in areas of environmental and structural monitoring, supply chain automation, identification of products at check-out points, access control and security, motivate the popularity of wireless sensor networks, the recent interest generated by wireless Radio Frequency Identifier (RFID) systems and their envisioned integration. While the autonomous operation and random deployment of components are the principal causes of the low set up cost of these systems, they also become the source of fundamental problems. In this work we study the problem of extending the network lifetime in the context of sensor and RFID systems by defining and detecting redundant components whose simultaneous deactivation maintains the initial network coverage.

For wireless sensor networks, we reduce the problem to the computation of Voronoi diagrams. We also examine the impact of redundancy elimination on the related problem of coverage-boundary detection. We present efficient distributed algorithms for computing and maintaining solutions for the redundant sensor elimination problem and coverage boundary problem in cases of sensor failures or new sensor deployment. We prove the safety and liveness properties of our algorithms, and characterize their time complexity and traffic generated. Using detailed simulations, we also quantify the impact of system parameters such as sensor density, transmission range and failure rates on network traffic.

In the context of wireless RFID systems, we provide an efficient solution to a fundamental problem generated by reader collisions occurring at tags. We prove that an optimal solution for the redundant-reader problem is NP-hard and propose a randomized approximation algorithm. We conduct elaborate experiments on realistic topologies in order to evaluate the accuracy, message overhead and efficacy of the protocols. Our simulations show that by repeating each query log m times and using 2log m time units for each query, where m is the total number of RFID readers, each reader can discover more than 99% of the covered RFID tags. Moreover, even without the existence of a centralized entity, we discover consistently more than half of the redundant readers of a greedy algorithm using centralized information.

Publications

Bogdan Carbunar, Ananth Grama, Jan Vitek, Octavian Carbunar. "Redundancy and Coverage Detection in Sensor Networks". ACM Transactions on Sensor Networks (TOSN), Volume 2, Issue 1, February 2006 [pdf]

Bogdan Carbunar, Murali K. Ramanathan, Mehmet Koyuturk, Ananth Grama, Christoph Hoffmann. "Redundant-Reader Elimination in RFID Systems". In Proceedings of the 2nd IEEE International Conference on Sensor and Ad Hoc Communications and Networks (SECON), Santa Clara, September 2005 [pdf]

Bogdan Carbunar, Ananth Grama, Jan Vitek, Octavian Carbunar. "Coverage Preserving Redundancy Elimination in Sensor Networks". In Proceedings of the 1st IEEE International Conference on Sensor and Ad Hoc Communications and Networks (SECON), Santa Clara, October 2004 [pdf]

Bogdan Carbunar, Ananth Grama, Jan Vitek. "Distributed and Dynamic Voronoi Overlay Maintenance for Coverage Detection and Distributed Hash Tables in Ad Hoc Networks". In Proceedings of the 10th IEEE International Conference on Parallel and Distributed Systems (ICPADS), Newport Beach, July 2004 [pdf]