## 3 The Sensor Network Calculus
### Sensor Network System Model  
WSNs are often oriented towards a single base station such that the employed routing protocol can form a sink tree. This commonly-found class of operations can be abstractly modeled as shown in Figure 1. Only traffic from sensors to the base station is explicitly taken into account in this model. The majority of traffic flows in this direction. Traffic in the opposite direction, e.g., topology control messages or node configurations, can be considered in the service curves for sensor-to-sink communication; for instance, by assuming strict priority. Overall, the network calculus model arranges the sensor nodes as servers in a directed acyclic graph as depicted in Figure 1.  
\begin{table}
\begin{tabular}{l l} \hline \hline
**Quantifier** & **Definition** \\ \hline \(\mathcal{F}_{0}\) & Non-negative, wide-sense increasing functions passing through the origin \\ \(\gamma_{r,b}\in\mathcal{F}_{\text{TB}}\) & Token-bucket functions with bucket size \(b\) and rate \(r\) \\ \(\beta_{R,T}\in\mathcal{F}_{\text{RL}}\) & Rate-latency functions with rate \(R\) and latency \(T\) \\ \(R_{i}\) & Input function of the flow originating at node \(i\) \\ \(R_{i}\) & Aggregate input function for all flows at node \(i\) \\ \(R_{i}^{*}\) & Aggregate output function for all flows at at node \(i\) \\ \(\alpha_{i}\), \(\alpha^{f}\) & Arrival curve, arrival curve of flow \(f\) \\ \(\alpha_{i}\) & Arrival curve of the flow originating at node \(i\) \\ \(\bar{a}_{i}\) & Aggregate arrival curve for all flows at node \(i\) \\ \(\alpha_{i}^{*}\) & Aggregate output arrival curve for all flows at node \(i\) \\ \(\beta_{i}\), \(\beta_{i}\) & Service curve, service curve of node \(i\) \\ \(\beta^{\text{lo.}}\), \(\beta_{i}^{\text{lo.}}\) & Left-over service curve, left-over service curve of node \(i\) \\ \(\beta_{i}\otimes\beta_{j}\) & Service curve concatenation with min-plus convolution \(\otimes\) \\ \(\alpha\dot{\oslash}\beta\) & Output bound computation with (adapted) min-plus deconvolution \(\oslash\) \\ \(\beta\ominus\alpha\) & Left-over service curve computation with non-decreasing subtraction \\ \(D(t)\), \(D_{i}\) & Delay at time \(t\) and the time-invariant delay bound at node \(i\) \\ \(B(t)\), \(B_{i}\) & Backlog at time \(t\) and the time-invariant backlog bound at node \(i\) \\ \hline \hline \end{tabular}
\end{table}
Table 1: Network calculus notation for functions of arrivals and service, as well as their min-plus algebraic manipulation and performance bounds.  
The system model takes the following aspects into account: each sensor senses its environment, reports data to the sink and forward measurements generated by other sensors in the network, i.e., the traffic seen by any sensor \(i\) consists of an input function \(R_{i}\) derived from its own sensing and, in case it is not a leaf node in the sink tree, the forwarded data from its child nodes _child_\((i,1)\),..., _child_\((i,n_{i})\), where \(n_{i}\) denotes the number of these nodes connected to sensor node \(i\). As all of this input data are forwarded by sensor \(i\), an output function \(R_{i}^{*}\) results. This output function is processed by sensor \(i\)'s parent node.