# Real-Time Communication Support for Underwater Acoustic Sensor Networks +
## 4 System Model
### Real-Time Message Model  
In this paper, we assume that any node may transmit a message to any other node in the network, if there is a valid path between them. We denote as \(m_{ij}\) a message from node \(i\) to node \(j\). We also assume all messages require one time slot to be transmitted, and that they have associated a period \(P_{ij}\). It may occur that the activity in certain applications is sporadic. In that case, the period is associated to the minimum interval of time between two successive events. For the real-time analysis, if the node has no message to send, a short _hello_ message is transmitted to keep both the network topology and synchronization updated. These messages are received by neighbors, but they are not propagated along the network.  
A real-time message should be received before a certain instant, named deadline. The message is said to be hard real-time if missing a deadline has catastrophic consequences. For instance, in a tsunami warning system, the message alerting the arrival of waves should be received in the coast with enough time to allow the evacuation of the people in the potentially affected area. If some deadlines are allowed to be missed, the system is said to be soft real-time [56]. These cases are related to applications in which there are timing requirements, but these are not stringent. Nodes should implement some priority policy for scheduling the messages. In this paper, the Deadline Monotonic Scheduling is proposed. As there may be many different deadlines, messages are grouped for reducing the number of priority levels that nodes should handle [57]. In the proposed model considerations are taken to have some degree of redundancy to provide fault-tolerance in the case of transmissions failures [58].  
In systems like those considered in this paper, deadlines \(D_{ij}\) are usually larger than the periods, as messages take a long time before reaching the sink. With this, we define the set of messages as \(Z=\{m_{ij}(P_{ij},D_{ij})\}\). The deadline is used to stop propagating messages once it is clear they are not going to be received on time. This is implemented with a deadline stamp that is reduced in each hop. When the time needed to reach the destination is greater than the remaining time denoted by the deadline stamp, the message is discarded. This may happen in the case a node is overloaded with higher priority messages.  
As nodes can only transmit in the slot allocated in the frame, if there are more than one message in the queue, then they should use as many frames as necessary to send all the messages. In case that all nodes in a route have their queues empty, in the worst case, the end-to-end delay for a message will be the amount of necessary hops, plus one time the frame length. This is a necessary condition for the system to be schedulable. In case of the network presented in Figure 2 that has five nodes and six edges with the same delay in both directions (for simplicity), the minimum frame is the one presented in Table 2. As it can be seen, it has a length of six slots. For a message starting in node \(a\) and destination in node \(e\) (i.e., \(m_{ae}\)) there are two hops, therefore, at least three frames or 18 slots are needed.  
Figure 2: 5-node network example.  
Within each node, when there are more than one message to be sent, a scheduling policy should be followed to guarantee the deadlines.