# LTDA-MAC v2.0: Topology-Aware Unsynchronized Scheduling in Linear Multi-Hop UWA Networks +
## 2 Linear TDA-MAC
### LTDA-MAC Schedule Optimization  
Deriving an LTDA-MAC schedule for a given LUASN deployment requires a joint optimization of \(N_{\text{sn}}(N_{\text{sn}}+1)/2\) values in \(\mathbf{T_{\text{tx}}}\) that minimize the frame duration:  
\[\min \tau_{\text{frame}}\left(\mathbf{\mathcal{N}},\mathbf{T_{\text{tx}}}\right)\] (2a) s.t. \[n_{\text{col}}\left(\mathbf{\mathcal{N}},\mathbf{T_{\text{tx}}},\tau_{ \text{g}}\right)=0, \tag{2b}\]  
where \(\tau_{\text{frame}}\left(\mathbf{\mathcal{N}},\mathbf{T_{\text{tx}}}\right)\) is defined as the time between the sink node sending the initial REQ packet and receiving the final data packet, \(n_{\text{col}}(\mathbf{\mathcal{N}},\mathbf{T_{\text{tx}}},\tau_{\text{g}})\) is the number of collisions caused by the transmitted/received packets overlapping in time at any node, \(\tau_{\text{g}}\) is the _desired guard interval_ specifying the minimum allowed time separation between scheduled packets, and \(\mathbf{\mathcal{N}}\) is a representation of a given network topology described below.  
We define the network deployment parameters as a tuple \(\mathbf{\mathcal{N}}=\{\mathbf{I},\mathbf{T_{\text{p}}},\tau_{\text{rp}},\tau_{\text{dp}}\}\), where \(\mathbf{I}\) is the interference matrix, \(\mathbf{T_{\text{p}}}\) is the matrix of propagation delays between every pair of nodes, and \(\tau_{\text{rp}}\) and \(\tau_{\text{dp}}\) are the REQ and data packet duration, respectively. \(\mathbf{I}\) and \(\mathbf{T_{\text{p}}}\) are computed by the master node during the network discovery stage, and can then be periodically updated based on the timing of received data packets. This process is appropriate for tracking the topology of a quasi-stationary UASN, as described in [21]. \(\mathbf{I}\) and \(\mathbf{T_{\text{p}}}\) are \(N\times N\) matrices, where \(N=1+N_{\text{sn}}\) is the total number of nodes, including one master (sink) node and \(N_{\text{sn}}\) sensor nodes. \(\mathbf{I}\) is a binary matrix, where \(I[i,j]=1\) if node  
Figure 2: Example of an LTDA-MAC schedule, where the master node gathers the data from three sensor nodes. R—REQ packet, D—data packet (Reprinted with permission from ref. [8]. Copyright 2019 IEEE Networking Letters.).  
can interfere with node \(i\), and \(I[i,j]=0\) otherwise. \(T_{\text{p}}[i,j]\) is the propagation delay from node \(i\) to node \(j\).  
The number of packet collisions in a candidate LTDA-MAC schedule \(n_{\text{col}}(\mathbf{\mathcal{N}},T_{\text{Rx}},\tau_{\text{g}})\) depends on the specific pattern of interfering links, propagation delays and packet durations, different for every network deployment. We found it intractable to solve this optimization problem analytically for an arbitrary network topology \(\mathbf{\mathcal{N}}\) (a formal proof of complexity of this problem is a subject of further work). Therefore, in [8] we proposed a heuristic \"simulation-in-the-loop\" optimization algorithm comprising two stages: (1) GA for initial coarse optimization, (2) PSO for converging on a locally optimal solution. There, the packet collision constraint (2b) is evaluated algorithmically by calculating the Tx and Rx times of every packet in a single frame. If any pair of Tx/Rx packets overlaps in time at the same node, _or is separated by less than_\(\tau_{\text{g}}\), a collision is detected and \(n_{\text{col}}(\mathbf{\mathcal{N}},T_{\text{Rx}},\tau_{\text{g}})\) is incremented. The drawback of this approach is its need to evaluate many candidate solutions before converging. The purpose of this paper is to propose an alternative heuristic optimization algorithm that produces better LTDA-MAC schedule solutions and that is significantly more computationally efficient.