# Real-Time Communication Support for Underwater Acoustic Sensor Networks +
## 1 Introduction
If the deadline is missed, the message is no longer valid and may have serious consequences for the communication process [13]. A feasible real-time schedule is one in which all messages comply with their deadlines. Real-time message scheduling in multi-hop networks (like UW-ASN) is a complex problem that requires the use of routing and queuing techniques. If all nodes in the network have a direct link to the rest of the nodes, the problem may be solved using an integer linear programming (ILP) approach. However, whena message should go through intermediate nodes, we have to decide not only when a node should transmit (i.e., a medium access control problem), but also how to select the appropriate path. In this case, the shortest path is not always the best one, as a per node scheduling should be incorporated in the analysis. In fact, a node holding more than one message has to schedule their transmissions, thus introducing additional delays. In a recent study, we proposed a network model and a simple distributed medium access control (MAC) protocol for the case of UW-ASN [14] that helps address part of this problem. The network is modeled as a tree with a sonobuoy as root, and sensors as leaves. The information flows from the leaves to the root using intermediate nodes for aggregating the information collected from the previous layer of the tree. The synchronization process is performed in a hierarchical way, from the root to the leaves. At each layer, a synchronizing node is selected following certain rules, and these nodes are in charge of aggregating messages during the data transmission stage. The proposed algorithm considered the possibility of re-configuring the tree periodically. However, this working strategy was not designed to operate under real-time constraints, and the possibility of transferring data between any pair of nodes was not evaluated. In this paper, we extend such a network model and also the algorithm proposed in [14], in order to include real-time constraints and message transfers between any pair of nodes in the system. The article also proposes a Time Division Multiple Access (TDMA) protocol based on a genetic algorithm, which includes an off-line allocation and scheduling algorithm. The feasibility conditions are given for the system to operate with hard real-time constraints. The reflected signals are used as backup, and an epidemic routing is evaluated as a strategy to improve the probability of conducting a correct message propagation, by introducing thus an opportunistic behavior in the network to provide fault tolerance. The suitability of the proposal is evaluated using simulations. For that purpose, a framework was developed using SimPy [15]. In the simulations we measured some important aspects like the throughput and goodput, messages end-to-end delay, fault tolerance, and real-time behavior. The results show that the chosen routing policy and the priority management of the queues in intermediate nodes provide a robust system, even in the case of faulty nodes or links. The network behavior is within the theoretical computed margins verifying the validity of the analytic approach. The simulation results show that the UW-ASN can be used by different applications providing enough reliability. This is an important result, as this kind of network may be used to support pervasive systems and also ambient intelligence scenarios. On the other hand, it is important to remark that the model proposed for UW-ASN is analytic, therefore the network performance evaluation can be automated allowing designers of both, protocols and underwater ubiquitous systems, to model their solutions (and evolve them) with minimal effort. Thus, these people can follow a prototyping-evaluation-tuning cycle until the solution is suitable enough to be implemented. This dynamic for modeling UW-ASN should help reduce development costs and risks, and increase the effectiveness of the resulting systems and protocols. Next section discusses the related work.