## Part B: Network Design for Energy Optimization
### The Model and its Combinatorial Abstraction  
Sensors and Sensor Network  
The basic model \(M_{0}\) is used, with some additional assumptions (see section 1.3). Let \(n\) be the total number of _available_ sensor devices for deployment. Let \(S\) be the set of _possible_ deployment positions (i.e. the union of 3D curves as we described earlier). Let \(T\) be a period of time. For each sensor \(\sigma\) of the \(n\) available sensors, a placement act, \(A_{\sigma}\), is a decision (i) either not to deploy \(\sigma\) or (ii) to deploy \(\sigma\) in an initial position \(\overset{\rightarrow}{P}\) in \(S\), for a period \(T_{\sigma}\subseteq T\), with a pre-specified pattern of \(R_{1}(t),R_{2}(t)\) (\(t\in T_{\sigma}\)) and a possible trajectory of \(\sigma\) moving in \(S\) for all \(t\) in \(T_{\sigma}\). All the placement acts, together, form a sensor network \(N\). We assume here that \(N\) is capable of (somehow) reporting the sensing of local events (i.e. tracking events) to some set of sinks \(T_{N}\). A model for targets  
In contrast to models that allow only a single moving target, we allow _multiple_ targets. We assume that _the initial positions of all targets are arbitrary_. Also, we assume that _all targets arise in arbitrary _times_ during the network operation. With respect to target mobility, we assume that each target follows an arbitrary path in \(S\) which is however continuous i.e. we disallow the target to instantaneously \"jump\" to another location. Furthermore, _we do not limit the movement speed of targets_; we only assume that when a target enters the sensing area of an (awake) sensor, it does not manage to leave this area before being sensed. This limit on motion speed is rather trivial, since sensing speed is very high i.e. practically the time needed for a target to be sensed is very close to zero. The combinatorial model  
Assume a given complicated 3D domain, \(S\), with obstacles that disallow signal transmissions (e.g. a set of corridors in buildings or different shape obstacles in a mountain). By \"complicated\" we mean that the domain can be represented by _arbitrary_ three-dimensional curves (see also the problem description subsection), i.e. the only modeling restriction on the curves is their continuity. We further assume that the domain can be represented by the union of \(\lambda\) routes \(R_{1},\ldots,R_{\lambda}\) (each can be realized by e.g. a moving robot or air-vessel). We are also given a period \(T\) of time. We wish to equip each route with sensors (of varying capabilities e.g. varying transmission range and operation times) so that any moving object in the domain at any time \(t\) in \(T\) can be \"seen\" by at least three sensors (and, thus, its instantaneous position can be found by triangulation). If we can manage this, we can monitor the motion of any moving object within \(S\) during \(T\). A trivial, but very costly, solution is to equip _each route_ with sensors (in various points of the route) each operating during the whole \(T\) and being able to track any motion in a part of the route. However, one could _exploit overlaps of routes at certain places_, sensors that can monitor pieces of several routes (\"nearby\") during their operation, or even sensors on top of certain moving objects of our own that wander in the maze of routes. In order to argue about such economic tracking methods, we view each \(R_{i}\) partitioned into several \"route pieces\" \(r_{ij}\). Let \(n_{i}\) be the number of the pieces of \(R_{i}\). We also partition the period \(T\) into suitable _intervals_\(\tau_{1},\ldots,\tau_{k}\) so that \(T=\tau_{1}+\cdots+\tau_{k}\). We call an _\"element\"_ each pair (\(r_{ij},\tau_{m}\)), for \(1\leq i\leq\lambda\), \(1\leq j\leq n_{i}\) and \(1\leq m\leq k\). There are \(n=\left(\sum_{i=1}^{\lambda}n_{i}\right)\cdot k\) such elements. We can then describe sensor placements (that work for a certain duration each) as relations (sets) between those elements. For example: (a) a sensor placed at \(r_{i5}\) can also \"see\" \(r_{j7}\), \(r_{k30}\).