# Real-Time Communication Support for Underwater Acoustic Sensor Networks +
## 5 Scheduling and Real-Time Feasibility Conditions  
UW-ASN share a common physical channel. In Section 4.2 we have discussed the computation of a minimum frame to guarantee that each node transmits and receives messages at specific slots. In the rest of the frame, the node may sleep thus saving energy. This is possible only after the network topology has been learned by the nodes, since they have conducted the synchronization process [14]. Real-time operation requires that messages arrive without errors and within their deadlines; in this section we present the necessary conditions for this. On the other hand, in Section 4.4 we described the epidemic routing to provide redundancy in the transmission. In each frame, the message advances one hop from the source to destination following different paths. At this point is where the scheduling policy in the nodes becomes important. A node may receive during one frame a message from every neighbor and besides it may generate its own messages. A message may be delayed within node \(i\) for \(\delta_{i}\) frames depending on the load. A policy to order the message transmission is necessary in order to bound \(delta\). In the worst case, the end-to-end delay for a message from node \(a\) to node \(b\) following path \(j\) with \(n\) hops is given by the following expression:  
\[\Delta_{ab}^{j}=T_{f}((n+1)+\sum_{i=1}^{n+1}\delta_{i}) \tag{10}\]  
Equation (10) has two terms. The first one computes the delay associated to the path used. The most common solutions for path discovery are based on Dijkstra algorithm to determine the shortest path from any node in the network to any other node (SPF, shortest path first), or the Bellman-Ford distance vector algorithm. In the present case, the computation of the shortest path is more simple as in each frame duration (\(T_{f}\)) the message completes one hop. If \(n\) is the number of hops in path \(j\), a message being transmitted as soon as it is received requires \(n+1\) frames to reach the destination node if it is generated just after the slot in which the source node has the chance to transmit. The shortest path is the one with less hops. Those paths that are not able to forward the message before its deadline are not followed and they can be used to forward other messages. The second term in (10) refers to the waiting time in the queues of intermediary nodes. Average waiting time in the queue may be computed from [PERSON]'s theorem [60], but to bound it, it is necessary to compute the response time according to the scheduling policy used in the node. The best path for underwater networks is not necessary the one with lower delay in the transmission, as nodes may be overloaded with messages and long delays may take place in each hop. Energy demand is another aspect that should be considered as underwater nodes depend on batteries and these are not easily replaceable. This is a strong reason to use alternative paths even if the transmission has long delays. The most simple scheduling policy in the nodes is First-In, First-Out (FIFO), but it may happen that a message with a higher priority is postponed in favor of another one with a lower priority. Real-time scheduling policies have been studied in the past and different feasibility conditions and response time analysis have been proved for them. In this paper, we assume a periodic monotonic scheduling policy (RMS) in which higher priorities are given to tasks with shortest periods. In [61] the response time for a set of \(m\) periodic, independent and simultaneously released messages is proved to be given by:  
\[\min R\ \ \ \text{s.t.}\ \ \ R=\sum_{h=1}^{m}\left\lceil\frac{R}{T_{h}}\right\rceil \tag{11}\]  
where \(R\in\{1,2,\ldots\}\). Equation (11) is solved iteratively. A solution exists if and only if:  
\[U=\sum_{h=1}^{m}\frac{1}{T_{h}}\leq 1 \tag{12}\]  
Condition (12) considers that the message can be transmitted at any instant. In the case of the UW-ASN proposed in this paper, the possibility of accessing the channel is limited to the allocated slot within the frame.