## 3 Problem Formulation  
We consider a WSN executing a sensing task, where the nodes operate in periods or _rounds_ whose duration is determined by their duty cycle. At each round each sensor samples the environment and produces a new data item that it sends to the sink, possibly along a multi-hop path. This behavior is typical of many WSN protocols, such as, for instance, Directed Diffusion [35]. As in most WSN applications, in our scenario the nodes are equipped with batteries that sustain completely their activities. Hence, an efficient use of the energy is of utmost importance in order to prolong the lifetime of the nodes. One of the most energy consuming components of a node is the radio. A radio interface has at least four states: idle, ready, Tx (transmission mode), and Rx (reception mode). Every state has a different energy consumption, which depends on the particular model and manufacturer of the node: In idle mode the energy consumption is very low, and in the rest of the states the energy consumption can be considered similarly high. To save energy, nodes need to keep the radio in idle mode as much as possible. This is the approach usually used in MAC protocols for WSN. On the other hand, while a node is in idle mode, the radio cannot receive nor send packets and the node behaves as if it was disconnected from the network. With the goal of saving energy in mind, the application manages a duty cycle that reflects the level of activity of the node. All operations that a node executes must fit in its duty cycle. In our approach we assume that the duty cycle of all of the nodes is identical; the MAC layer uses it to compute the check intervals which are then communicated to the neighboring nodes in order to share the same information. Network lifetime is commonly defined as the time elapsed between the beginning of the network activities and the time at which the first node of the network depletes its battery. We adopt this precise definition in this work. Note that, however, there exist other definitions for the network lifetime that may also apply. Let \(B\) be the initial energy at each node battery; the lifetime \(l(i)\) of a node \(i\) measured as the number of rounds can be expressed as:  
\[l(i)=\ \frac{B}{E(i)} \tag{1}\]where \(E(i)\) denotes the energy consumed by node \(i\) in a round. We are assuming that a node is alive as long as it performs all assigned functions. The lifetime of the network \(L\) is then:  
\[L=min_{i}\{l(i)\} \tag{2}\]  
Let us consider a WSN composed of \(n\) nodes, \(i_{1}\) to \(i_{n}\). Each node can communicate directly with its neighbors, _i.e._, with the nodes within its radio range. For the sake of simplicity we assume that if \(i_{j}\) is in range with \(i_{k}\) then \(i_{k}\) is also in range with \(i_{j}\), _i.e._, communication links are bidirectional. A node may also communicate with a remote node, _i.e._, a node which is not within its radio range, by a multi-hop path that consists of the set of nodes on the path. Let \(path(i_{1},i_{m})=\langle i_{1},i_{2},\ldots,i_{m}\rangle\) be an \(m\)-hop path connecting nodes \(i_{1}\) and \(i_{m}\), and let \(i_{k}\) be a node on this path. Then \(order(i_{k})\) denotes the place occupied by \(i_{k}\) in the path, _i.e._, \(order(i_{k})\) is the hop distance between \(i_{1}\) and \(i_{k}\). This relation ensures that \(order(i_{1})\leq order(i_{k})\leq order(i_{m})\). Note that the function \(order(i_{k})\) within the \(path(i_{1},i_{m})\) returns a number between 0 and \(m-1\). This function is later used in Equation (4). Routing decisions regarding the nodes on the path from a sender \(i_{1}\) to a receiver \(i_{m}\) are left to the routing protocol, in our case CTP. The nodes use BoX-MAC as the underlying data link protocol. This implies that the nodes along the path wake up to sample the channel after each check interval expires. At this time, they may either receive the neighbor's packets and forward them to the parent, or initiate a transmission.