# Asymmetric Propagation Delay-Aware TDMA MAC Protocol for Mobile Underwater Acoustic Sensor Networks
## The APD-TDMA
### Initialization Phase  
The initialization phase can be performed by following the sequential approach of [37; 40]. This sequential method is suitable for a dense network due to contention-free feature. However, in sparse network, the required time to complete the initialization phase can be improved by a  
Figure 1: Network model. -function-based scheme. We present a contention-based method suitable for the initialization phase of a sparse network. The initialization phase of the APD-TDMA consists of several initialization time slots for broadcasting an IRQ packet to get the positions of UNs and receiving initialization response (IRP) packets. The duration of initialization time slot, denoted by \(TS_{Init}\), is given by  
\[TS_{Init}=2\cdot\tau_{max}+\tau_{IRQ}+\tau_{IRP}, \tag{1}\]  
in which \(\tau_{IRQ}\) and \(\tau_{IRP}\) are the duration of the IRQ packet and the IRP packet, respectively, and in which \(\tau_{max}\) is the maximum propagation delay between the SN and a UN. Note that \(\tau_{max}\) is the propagation delay, assuming that a UN is located at the communication boundary of the SN. Let us consider that two UNs, denoted by UN\({}_{1}\) and UN\({}_{2}\), send their IRP packet as soon as they receive an IRQ packet. The distance between UN\({}_{i}\) and SN is denoted by D\({}_{i}\). If we assume that the departure time of the IRQ packet is zero, then the arrival time of IRP packet of UN\({}_{i}\) is given by \(\tau_{IRQ}+2\times\frac{D_{i}}{c}\), in which \(c\) is the sound speed at the sea water, typically 1500 m/s [39]. The IRP packets of UN\({}_{1}\) and UN\({}_{2}\) are overlapped if  
\[\left|\left(\tau_{IRQ}+2\times\frac{D_{1}}{c}\right)-\left(\tau_{IRQ}+2 \times\frac{D_{2}}{c}\right)\right|=\frac{2|D_{1}-D_{2}|}{c}<\tau_{IRP} \tag{2}\]  
Considering that \(0\leq D_{i}\leq R\), and that the length of the line defined by (2) is \(c\times\tau_{IRP}\), we can get the probability \(p\) for the collision of two IRP packets as follows  
\[p=\frac{c\times\tau_{IRP}}{R}, \tag{3}\]  
in which \(R\) is the network range, and in which we assumed that the distribution of node's position is uniform. Since there are \(\frac{N(N-1)}{2}\) possible collisions with \(N\) nodes and the number of collisions is reduced by a factor of \(p\) for each IRQ packet retransmission, the expected value of the required time to finish the initialization phase (RTFIP) is given by  
\[\sum_{k=1}^{\infty}k\cdot TS_{Init}(1-p)^{\frac{M_{k}(M_{k}+1)}{2}}, \tag{4}\]  
in which we assumed that the network topology changes randomly due to mobility. In (4), \(M_{k}\) is defined by following recurrence equation:  
\[M_{1}=N,\ M_{k+1}=\frac{M_{k}(M_{k}+1)}{2}. \tag{5}\]  
In general, an IRP packet is a very short packet with a duration of less than a few milliseconds. For example, \(p\) can be made smaller than \(10^{-3}\) with 10 kbps acoustic modem at the range of 1 km. If we assume that \(p=10^{-3}\) and \(N=10\), the RTFIP is \(TS_{Init}\) with the probability of 0.95 from (4). On the other hand, the RTFIP of [37; 40] is simply given by  
\[N\times TS_{Init}. \tag{6}\]  
Therefore, if the network parameters including data rate of modem, communication range, and number of nodes are given, we can decide which of the two methods to apply. However, Equation (4) is not valid for a static topology, because the retransmission of an IRQ packet cannot resolve the IRP packet collisions. In this case, the remaining collisions after IRQ-IRP exchange can be resolved by applying selective random backoff as follows. Figure 2 illustrates the procedure of the initialization phase. In the first initialization time slot, the SN broadcasts an IRQ packet and waits for IRP packets from UNs. The SN extracts the position of each UN from successfully received IRP packets. If the collision of IRP packets is detected at the SN, a re-initialization request (RIRQ) packet is broadcasted by the SN at the end of the first initialization time slot. The RIRQ packet includes the list of ID whose IRP packet is successfully received.