Coverage Problems in Wireless Sensor and RFID Systems
Tech report number
CERIAS TR 2005-40
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 Identification (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. This thesis studies 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. Moreover, we 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 insertion of new sensors. 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 $2\log 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.
2005 – 05 – 07
sensor network coverage
sensor networks, RFID systems, redundancy, coverage