## 1 Introduction
### The Energy Efficiency Challenge in Routing and Tracking  
Since one of the most severe limitations of sensor devices is their limited energy supply, one of the most crucial goals in designing efficient protocols for wireless sensor networks is minimizing the energy consumption in the network. This goal has various aspects, including: (a) minimizing the total energy spent in the network (b) minimizing the number (or the range) of data transmissions (c) combining energy efficiency and fault-tolerance, by allowing redundant data transmissions which however should be optimized to not spend too much energy (d) maximizing the number of \"alive\" particles over time, thus prolonging the system's lifetime and (e) balancing the energy dissipation among the sensors in the network, in order to avoid the early depletion of certain sensors and thus the breakdown of the network. We note that it is very difficult to achieve all the above goals at the same time. There even exists trade-offs between some of the goals above. Furthermore, the importance and priority of each of these goals may depend on the particular application. Thus, it is important to have a variety of protocols, each of which may possibly focus at some of the energy efficiency goals above (while still performing well with respect to the rest goals as well). In this paper, we focus on energy optimization. We investigate both on-line aspects of energy efficiency related to data propagation, as well as off-line network design issues, related to tracking, an important problem which is considered canonical in the literature. In particularly for routing we present three methodologically characteristic energy efficient protocols:  
* _The Local Target Protocol (LTP)_, that performs a local optimization trying to minimize the number of data transmissions. * _The Probabilistic Forwarding Protocol (PFR)_, that creates redundant data transmissions that are probabilistically optimized, to trade-off energy efficiency with fault-tolerance. * _The Energy Balanced Protocol (EBP)_, that focuses on guaranteeing the same per sensor energy dissipation, in order to prolong the lifetime of the network. Because of the complex nature of a sensor network (that integrates various aspects of communication and computing), protocols, algorithmic solutions and design schemes for all layers of the networking infrastructure are needed. Far from being exhaustive, we mention the need for frequency management solutions at the physical layer, for Medium Access Control (MAC) protocols to cope with multi-hop transmissions at the data link layer. Our approach focuses on routing and does not consider other important issues like link fading and hidden station interference, i.e. we assume that other network layers are resolving these issues. Also, regarding reliability, an endemic issue to wireless sensor networks, we consider permanent physical failures i.e. we do not deal with bad values from physical sensing or transient failures. The interested reader may use the excellent survey by [PERSON] _et al._[4] for a detailed discussion of design aspects of all layers of the networking infrastructure. For tracking, we study the problem of localizing and monitoring multiple moving targets in wireless sensor networks, from a network design perspective i.e. towards estimating the least possible number of sensors to be deployed, their positions and operation characteristics needed to efficiently perform the tracking task. To avoid an expensive massive deployment, we try to take advantage of possible coverage overlaps over space and time, by introducing a novel combinatorial model that captures such overlaps. Under this model, we abstract the tracking network design problem by a combinatorial problem of covering a universe of elements by at least three sets to ensure that each point in the network area is covered at any time by at least three sensors, and thus being localized, i.e.