# Real-Time Communication Support for Underwater Acoustic Sensor Networks +
## 4 System Model
### Network Model  
At this point it is useful to consider time as a discrete variable. Time can be seen as a sequence of slots \(t\) numbered \(\{1,2,\ldots,n\}\). Even if time is continuous, in order to handle nodes accessing to the transmission channel, the division in time slots facilitates the allocation and provides an efficient tool to separate possible transmission and reception interference within the nodes. Under this approach, the slot duration is a design decision that considers silent intervals, both at the beginning and at the end of it. These intervals account for variations in the transmission propagation speed, for example, caused by currents or for the need to turn off the receiver while transmitting. In this way, a node transmits a message during the slot, but it does not mean that all the time is used for the transmission. This concept is explained for the case of frame boundaries as guard times in [36]. In previous UW-ASN TDMA proposals, the slot time included the longest propagation delay. Although this guarantees that no collisions are produced, for the case of acoustic underwater transmissions where propagation time is usually higher than packet length, this approach wastes too much time [48; 54; 55]. Considering the previous definitions, the network can be modeled as a directed graph \(G=(V,E)\), in which \(V\) is the set of network nodes and \(E\) is the set of edges (i.e., links between network nodes). If two nodes \(u\) and \(v\) are within transmission range, there are two sets of edges connecting them \(\Theta(u,v)=\{e_{h}(u,v)\}\) and \(\Theta(v,u)=\{e_{h}(v,u)\}\), where \(h\) numerates the links. Each edge of the graph has a label that represents the transmission delay between the nodes measured in _time slots_ (\(\tau_{wh}\)). The set of nodes that have a direct link with \(i\in V\) is the neighbor set, and it is denoted \(N(i)\). The multipath effect described in previous section is modeled with many edges with different weights among two neighbor nodes representing the different paths and propagation delays. Table 1 shows the notation used in the model. As collisions are important only if they are produced at the node, there are four different scenarios to consider as stated in [36]. The first scenario is when two messages arrive simultaneously to a node; this case is named the Rx-Rx. The second scenario is produced when two messages tried to be transmitted simultaneously in a node; this is the Tx-Tx case. The third scenario is when a message is transmitted at the time that another message is being received; this is the Tx-Rx case. The last one is named the Rx-Interference case and it arises when a message interferes another one in a node. The interfering message has a different destination node; this last case is similar to the Rx-Rx. Figure 1: Example of multipath transmission. In the case of the multipath, the collision can be produced with any of the message replicas, therefore special care in the slot time assignment should be taken. As the transmission medium is water and the signal is acoustic, the presence of several edges between two neighbor nodes does not imply independent paths; all of them are used whenever a node transmits. In [43] we presented an integer linear programming (ILP) model to minimize the frame length. However, such a model does not consider the transmission delay, and different solutions with the same objective function value have different frame sizes. In [48] the authors proposed a TDMA scheme similar to the one proposed in this paper, but they use continuous time. They named the graph model as the local conflict graph problem and show that it is a NP-Hard problem; however, they do not consider the multipath effect. In this paper, we modify this previous model to include the maximum delay in the objective function, and with this, the minimum frame (if exists) is found.