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.