## 2 Related Work
### MAC Protocols and Scheduling Algorithms for UWSN  
The propagation delay is one of the most studied factors in underwater MAC protocols. Researchers have been trying to adapt existing protocols and have been proposing new ones in order to address the differences between terrestrial and underwater acoustic networks.  
The original FAMA (Floor Acquisition Multiple Access) protocol [10] prevents packet collisions provided that the RTS and CTS frames are long enough. Given the long propagation delay of the underwater acoustic medium, these packet lengths are very high, hence [PERSON] _et al._ propose in [11] the Slotted FAMA MAC protocol. This protocol provides some energy savings since nodes do not have to transmit long RTS/CTS frames. However in this case, the slot length needs to be equal to the maximum propagation delay plus the transmission time of a CTS packet, which can lead to a low channel utilization.  
T-Lohi (Tone-Lohi), a hybrid between RTS/CTS and CSMA, is proposed in [12]. This protocol adapts automatically the contention time to the number of contending nodes. The nodes send a short packet called tone prior to the actual data packet to count the number of terminals contending for the channel. If a node does not receive any other tones, it starts the transmission. However, if it receives more tones, it adapts its backoff time depending on the number of tones received. The channel utilization of this protocol is within 30% of the theoretical maximum.  
[PERSON] _et al._ advocate for a CDMA-based MAC [13]. Their proposed MAC switches at each sender node from an ALOHA scheme, to transmit the header, to a CDMA-based scheme, to transmit the payload. This payload and the header are sent back-to-back in one transmission. A node first sends a short header with the spreading code and sends immediately the payload using this spreading code. Results show that this MAC scheme can achieve high network throughput in deep water communication and can dynamically adapt to compensate the multipath effect in shallow waters.  
There are some proposals that take advantage of the propagation delay and overlap multiple transmissions in order to increase the throughput. Authors in [14] propose ST-MAC, which is a centralized scheduling algorithm that constructs a Spatial-Temporal Conflict Graph (ST-CG) to describe the conflict delays. Authors take a vertex colouring approach and model the graph by assigning a color to each of its edges. In order to solve the vertex-colouring problem, ST-MAC divides the transmissions into multiple timeslots which may lead to suboptimal results [15].  
STUMP-WR [16] is also able of overlapping different transmissions using TDMA slots and scheduling them in a distributed manner. Given the distributed nature of the protocol, nodes can only use local information to perform their schedule, which may lead to suboptimal schedules. Moreover, it may not avoid all the possible interferences when facing the hidden terminal problem.  
In [15], [PERSON] _et al_. introduce a set of scheduling constrains to avoid interferences and propose a centralized scheduling algorithm to take advantage of the propagation delay. Later in [17] they extend this set of scheduling constrains to allow the schedule to be performed in a distributed manner using clusters of nodes.