## 7 SensorNC Applications
### Optimal Sink Placement  
In many WSN applications, it is desired to collect the information acquired by sensors for processing, archiving and other purposes. The station where that information is required is usually the sink. For large-scale WSNs, a single-sink model is not scalable since message transfer delays, as well as energy consumption of the sensor nodes become prohibitive, due to the fact that most of the nodes would be far away from the sink, and thus, many hops must be traversed before the sink is reached. As a result, response times become excessive, and the lifetime of the WSN becomes very short. Therefore, it is sensible to deploy multiple sinks so that messages reach their destination with less hops, and consequently, response times are decreased and energy saved. If sinks are placed in good locations, this can reduce traffic flow and energy consumption for sensor nodes. In particular, we focus on strategies to minimize the maximum worst-case delay, which is important for any timely actuation based on the information collected by a WSN. In mathematical terms, we can pose the problem as follows:  
\[min.\max_{i\in\{1,\ldots,n\}}\left\{D_{i}\right\}\]  
with:  
\[D_{i}{=}f\left(\tau|\vec{\alpha},\vec{\beta}\right)\]  
Figure 10: Generic network calculus computations vs. sensor network calculus (SensorNC): (**a**) delay bounds and (**b**) computation time reduction. \[\tau = g(\vec{s}|\vec{p},\mathcal{R})\] \[\vec{p} = \left(p_{i}^{(x)},p_{i}^{(y)}\right)_{i=1,\ldots,n}\] \[\vec{s} = \left(s_{j}^{(x)},s_{j}^{(y)}\right)_{j=1,\ldots,k}\] \[p_{i},s_{i} \in\mathcal{F}\]  
Here, \(n\) denotes the number of sensor nodes, and \(\vec{p}\) is the vector of their locations in the sensor field \(\mathcal{F}\); these locations are assumed to be given. The values \(D_{i}\) are the worst-case delays for each sensor node \(i\). By minimizing the maximum worst-case delay in the field, it is ensured that response times are balanced as much as possible. \(k\) is the number of sinks, and the vector \(\vec{s}\) contains their locations; these locations are the actual decision variables of the optimization problem. This is somewhat hidden by the fact that the delays \(D_{i}\) are only indirectly, affected by the choice of the sink locations, because as a first-order effect, the \(D_{i}\) are a function of the topology \(\tau\) in which the WSN organized itself in the data flow towards the sinks and the arrival and service curves of the sensor nodes, denoted as \(\vec{\alpha}\) and \(\vec{\beta}\) in the formulas above. While the arrival and service curves are parameters for a given WSN scenario, the topology is, in turn, a function of the nodes' locations, the routing algorithm \(\mathcal{R}\) and the sinks' locations \(\vec{s}\), where however only the sinks' locations are variable, and the other two are again given parameters. Note, in particular, that we assume the routing algorithm to be given and not to be subject to the optimization. Although this could in principle be done, it would aggravate the problem further and is therefore left for further study. Therefore, in principle, we face a continuous optimization problem where the objective function is to minimize the maximum worst-case delay in the field subject to constraints that ensure that each sensor node is connected to a sink (possibly via multi-hop communication, determined by the routing algorithm), as well as some geographic constraints. Due to the highly non-linear, jumpy behavior of the worst-case delay function \(f\) and thus of the objective function, which results from the formulas derived by sensor network calculus, the direct solution of that optimization problem is practically infeasible. Therefore, a heuristic strategy for the sink placement problem that minimizes the maximum worst-case delay in WSNs based on the sensor network calculus framework was developed: genetic algorithm-based heuristic for sink placement (GASP).