Improving the energy efficiency and performance of sensor and RFID networks by exploiting spatial redundancy

Spatial query execution is an essential functionality of a sensor network, where a query gathers sensor data within a specific geographic region. Redundancy within a sensor network can be exploited to reduce the energy cost incurred in the querying process, which is a very limited resource in sensor networks. One approach to reduce the energy cost of a query is to self-organize the network, in response to a query, into a topology that involves only a small subset of the sensors sufficient to process the query. This set of active sensors should be sufficient to cover the region required to be monitored. Also, they should form a connected communication graph, so that they can autonomously respond to application queries and/or tasks. Such a set of active sensor is called a connected sensor cover.; In this report, we design and analyze algorithms for selecting a minimum energy-cost connected sensor cover. In particular, we design a centralized approximation algorithm that constructs a topology involving a near-optimal connected sensor cover. We prove that the size of the constructed topology is within an O(log n) factor of the optimal size, where n is the network size. We also design a distributed localized algorithm that is empirically shown to be performing well. Our algorithms are shown to be extensible to variable radii sensor models, where larger transmission and sensing radii entail higher energy cost. We also make our algorithms adaptable for fault tolerance. Specifically, our algorithms address the k 1-connected k2-cover problem.; Radio frequency identification (RFID) is a technology where a reader device can "sense" the presence of a specific object in the neighborhood by remotely reading an ID embedded in a tag device attached to the object. To improve coverage, multiple RFID readers can be deployed in a geographically dispersed fashion. In this report, we also consider the problem of fast reading of RFID tags in a multiple reader environment. We develop centralized algorithms in a slotted time model to read all the tags using near-optimal number of time slots. Two link layer models are considered---one suitable for scenarios where tag distribution in the physical space is unknown, the other where tag distribution is known or can be estimated a priori. For each of these link layer models, we consider three different cases, where single, multiple, or an unlimited number of frequency channels are available. The problem of reading tags in optimal number of time slots is NP-hard in both the link layer models. We design approximation algorithms for the single channel and unlimited channel cases, and heuristic algorithms for the multiple channel case. Through extensive simulation, we show that the heuristic algorithms perform well by empirically comparing their performances to the approximation algorithms for the special case of one channel. Empirical evaluations also show that our designed algorithms are much superior to Color-wave, an existing algorithm solving similar problems.