# Real-Time Communication Support for Underwater Acoustic Sensor Networks +
## 5 Scheduling and Real-Time Feasibility Conditions
Therefore, the condition and response time should be reformulated to count the reduction in the bandwidth and the frame granularity imposed by the TDMA:  
\[U=\sum_{h=1}^{m}\frac{1}{T_{h}}\leq 1/T_{f} \tag{13}\] \[\min\delta\ \ \ \text{s.t.}\ \ \delta=T_{f}\sum_{h=1}^{m}\left\lceil \frac{\delta}{T_{h}}\right\rceil \tag{14}\]  
Example:  
In order to illustrate the different aspects discussed in the previous sections, next we present a simple example. Figure 3 shows a seven node network with the labels in the edges denoting the transmission delay between adjacent nodes. We added in this case an additional path between each pair of nodes that represents a delayed arrival, multipath transmission. For simplicity of presentation, we assume that the delay in both directions is the same. The solution to the ILP model produces a frame of 11 slots in which all nodes transmit and receive. Table 3 shows the slot allocation. Figure 3: 7-node network example with multipath. Let us suppose that node \(a\) has to send a message to node \(g\). According to the proposed epidemic routing, it implies that the message is received by nodes \(b\) and \(e\) in slots 10 and 11 respectively. Once the message is received, both nodes will forward it to all their neighbors. In this case, both nodes \(e\) and \(b\) will forward the message in slot 12. At this point it is interesting to mention that the message will be received by node \(a\) in slots 17, 18, 19 and 20. The node will know in this way that its message has been forwarded by both nodes. Also nodes \(b\) and \(e\) will receive the copy of the message sent by each other, but they will discard it as it has been already received. Nodes \(c\) and \(f\) will receive the message at slot 17. These nodes have to wait for the next frame to forward the message, in this case until slot 25. The message is finally received at node \(g\) coming from node \(f\) at slot 29, while the other branch still requires another frame as the message is received by node \(d\) in slot 29, and in the next frame at slot 38 will forward it to node \(g\), that will receive the message at slot 42. We have assume for this analysis that the message was ready to be sent when node \(a\) was able to transmit in the first place. However, the worst case condition may happen when the message is generated just after the slot for node \(a\) has passed. In that case, another 11 slots should be added to the total delay. The worst case transmission time is then 40 and 53, respectively for each path. If the deadline associated to this message \(D_{ae}\geq 53\), then both paths are feasible; in other case, if \(40\leq D_{ae}\leq 52\) only the shortest path is feasible and if \(D_{ae  
In Table 5 the worst case response time in each node according to Equation (14) is shown:  
Based on Table 5 and the number of hops in each path, the worst case end-to-end delay may be computed and compared with the deadline of the message. With this information, those routes that not satisfy the messages deadlines are discarded. In Table 6 all the possible paths for message \(m_{ag}\) are shown, and the worst case delay is computed. As it can be seen, the last route is not feasible, since node \(c\) will not forward \(m_{ag}\) when it is received from node \(f\).