# FD-LTDA-MAC: Full-Duplex Unsynchronised Scheduling in Linear Underwater Acoustic Chain Networks
## 2 FD-LTDA-MAC Protocol
, \tag{1}\]  
where,  
\[T_{tom}^{FD}[i,i]=T_{tx}[i,i]-\tau_{rp}, \tag{2}\]  
\[T_{tor}^{FD}[i,j]=T_{tx}[i,j]-\tau_{dp}, \tag{3}\]  
Figure 3: FD-LTDA-MAC schedules in a three-hop network. \(T_{own}^{FD}[i,i]\) represents the transmit delays incurred by node \(i\) for sending its own data packet(s) and \(T_{forw}^{FD}[i,j]\) represents transmit delays for node \(i\) to forward node \(j\)'s data packet(s) given that \((i<j)\). Furthermore, \(T_{tx}[i,i]\) and \(T_{tx}[i,j]\) represent the respective transmit delays for a node sending its own data and relaying data from a node down the chain based on the traditional LTDA-MAC scheme. Transmission schedules are derived by optimally solving for \(N_{sn}(N_{sn}+1)/2\) values in \(T_{tx}^{FD}\) and the solution yields a minimum frame duration (\(\tau_{\text{frame}}(\mathcal{N},T_{tx}^{FD})\)) with zero packet collisions (\(\eta_{col}(\mathcal{N},T_{tx}^{FD},\tau_{g})\)), where \(\tau_{g}\) is the allowable guard interval between scheduled packets and \(\mathcal{N}\) is a tuple that represents a typical underwater full-duplex chain network topology. The full network topology is defined by an (\(N\times N\)) interference binary matrix, \(\mathbf{I}\), propagation delay matrix, \(\mathbf{T_{p}}\), REQ and data packet durations, \(\tau_{rp}\) and \(\tau_{dp}\). The interference matrix can be expressed as:  
\[\mathbf{I}= \begin{pmatrix}I[1,1]&I[1,2]&\cdots&I[1,N]\\ I[2,1]&I[2,2]&\cdots&I[2,N]\\ \vdots&\vdots&\ddots&\vdots\\ I[N,1]&I[N,2]&\cdots&I[N,N]\end{pmatrix} , \tag{4}\]  
where \(I[i,j]=1\) if node \(i\) is in interference range of node \(j\), and \(I[i,j]=0\) otherwise. Additionally, the propagation delay from node \(i\) to node \(j\) is given as \(T_{p}[i,j]\). The FD-LTDA-MAC protocol uses a greedy algorithm to derive collision-free transmission schedules by iterating over transmit delays in \(T_{tx}^{FD}\) to check for overlaps in time in any pair of transmit/receive packets at a node, or where a separation between scheduled packets is less than \(\tau_{g}\). It compares the data transmission, interference, and reception times to detect a full-duplex transmission, and then forces the algorithm to choose a starting point for the transmit delay search, selecting a local optimal value for it. Moreover, in the case of full-duplex transmission, the initial schedule is modified by removing the allowable separation, \(\tau_{g}\), between the REQ packet interference and transmit data packet at a node. This is because, in full-duplex transmission mode, a receive/transmit overlap in time at a node does not count as a collision but a successful transmission, thus, adding \(\tau_{g}\) becomes unnecessary. Additionally, in evaluating the schedule, the additional delay incurred at a node given full-duplex transmission is \(\tau_{g}\). The minimum transmit delay constraint to be imposed on any transmitting node to send its own data packet is given as:  
\[\forall n\in\{1..N_{sn}\},\ T_{m}^{FD}[n,n]= \begin{cases}\tau_{rp}+\tau_{g},&n< N_{sn}\\ \tau_{g},&n=N_{sn}\end{cases} , \tag{5}\]  
where \(T_{m}^{FD}[n,n]\) is the minimum transmit delay for a node to send its own data. Similarly, the minimum transmit delay constraint imposed on a node for relaying a data packet up the chain from a node further down the chain is represented as:  
\[\forall n,k\in\{1..N_{sn}\},k>n, \tag{6}\] \[T_{m}^{FD}[n,k]=2\tau_{p}[n+1]+\tau_{g}+\tau_{rp}+T_{tx}[n+1,k],\]  
where \(T_{m}^{FD}[i,j]\) is the minimum transmit delay assigned to node \(i\) for transmitting a packet generated by node \(j\) and \(\tau_{p}[i]\) is the propagation delay on the \(i\)th link between adjacent nodes of the network. This constraint provides for the allowable time for a node to receive a packet while transmitting another data packet. Nonetheless, for a node transmitting its own data packet up the chain and forwarding a data packet received from a node further down the chain in a half-duplex mode will resort to the respective minimum transmit delay [18]. \[\forall n\in\{1..N_{sn}\},\;T_{m}[n,n]=