## 7 SensorNC Applications
### TDMA Optimization
#### 7.3.1 General TDMA Design Problem  
From those requirements, we formulate the TDMA design problem as an optimization problem for a tree network with \(n\) nodes where from each node, a flow is originating:  
\[ \begin{array}{ll}\max.&Z=\min_{1\leq i\leq n}\left\{f-s_{i}\right\}\\ \text{s.t.}&\sum_{i=1}^{n}s_{i}\leq f\\ &\forall i:\ d_{i}(f,\bar{s}|r,b,C)\leq D\\ &\forall i:\ \frac{s_{i}}{f}\cdot C\geq F_{i}r\\ &\forall i:s_{i}\geq 0,\ f\geq 0\\ \end{array} \qquad\text{(TDMA integrity)} \tag{1}\]  
Here, \(f\) is the cycle length of the repetitive TDMA frame, and \(s_{i}\) is the amount of time devoted to node \(i\) for sending (slot size of node \(i\)). These constitute the decision variables. For the parameters of the problem, we further have \(D\) as the maximum permissible delay that may be incurred by any flow in the sensor field, \(d_{i}(f,\bar{s}|r,b,C)=h(\gamma_{r,b},\beta_{i}^{\text{lo. }})\) as the actual maximum delay incurred by flow \(i\) (which is computed based on the PMOO analysis described in Algorithm 2), \(F_{i}\) as the number flows carried by node \(i\) (including the flow originating at node \(i\)), \(C\) as the medium rate (\"capacity\") and \(r\) as the maximum sustained rate for any flow, as well as \(b\) as the maximum burst of a flow. Note that we assume the sensors to have identical arrival curves \(\gamma_{r,b}\), as well as an identical delay requirement \(D\), which for many practical situations will be no restriction and makes the further analysis more tractable. The objective function reflects the fact that the minimum sleeping period over all nodes in the field should be maximized, thus achieving a maximum lifetime of the network. The TDMA integrity constraint captures the fact that all slot sizes together must fit into the TDMA frame. Obviously, the delay target should be met for all flows, which is captured by the delay constraints; also, all of the rate constraints must be met in order not to obtain infinite delay bounds for the flows. Of course, we also have non-negativity constraints for the decision variables. Unfortunately, this general modeling of the TDMA design problem results in a very hard to solve non-linear programming problem. The non-linearity is exhibited in the objective function, as well as in the delay constraints. Hence, the only viable approach is to simplify the problem structure if a solution shall be found for larger instances of the TDMA design problem. There are two intuitive approaches towards relaxing the problem:  
1. Equal slot sizing (ESS): the assignment may be made such that inside a fixed time slot length, each node can transmit enough data to meet all requirements. Traffic-proportional slot sizing (TPSS): slots may be assigned such that each node only claims the resources necessary to fulfil its own duties, depending on the input bandwidth and forwarded data streams. While the second relaxation approach may appear more efficient, it is also harder to set up. The first approach requires rather little information--the number of nodes and the bandwidth requirements of the node serving the highest number of flows--and the second method requires good knowledge of the topology, which may not always be at hand. Furthermore, in [8], it is shown that ESS is actually superior to TPSS, which is why we further focus on it. Two variables need to be controlled under ESS: the overall frame length \(f\) and the individual slot length \(s\). Obviously, with an increasing frame length, a node may sleep longer between transmission or reception phases, but delay is increased at the same time. For a given \(f\) in a network with \(n\) nodes, \(s\) is limited to values between an upper bound \(\frac{f}{n}\) and a lower bound that is given by the minimum bandwidth requirements. Next, we state the TDMA design problem under ESS, which as we show below is amenable to an analytical solution under TDMA service curves (over-)approximated by rate-latency service curves. TDMA Design under Equal Slot Sizing  
Under ESS, we now consider a common slot size \(s\) for all nodes.