Abstract
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.
Keywords
sensor networks, RFID systems, redundancy, coverage
