# LTDA-MAC v2.0: Topology-Aware Unsynchronized Scheduling in Linear Multi-Hop UWA Networks +
## 2 Linear TDA-MAC
### Greedy Optimization Algorithm  
The high computational complexity of the GA + PSO method proposed in [8] stems from the need to minimize a nonlinear discontinuous objective function in \(N_{\text{sn}}(N_{\text{sn}}+1)/2\) dimensions, resulting in a vast non-convex solution space. To reduce the computational cost of LTDA-MAC schedule optimization we propose a new greedy algorithm that iterates over every Tx delay in \(T_{\text{Rx}}\) and chooses a locally optimal value for it in isolation. To ensure that valid LTDA-MAC schedules are produced by such an iterative greedy optimization approach, we impose the following constraints on the Tx delays. Firstly, the minimum transmit delay assigned to node \(n\) for transmitting its own data packet is:  
\[\forall n\in\{1..N_{\text{sn}}\},\ T_{\text{m}}[n,n]=\left\{ \begin{array}{ll} \tau_{\text{rp}}+2\tau_{\text{g}},&n<N_{\text{sn}}\\ \tau_{\text{g}},&n=N_{\text{sn}},\end{array} \right. \tag{3}\]  
where \(T_{\text{m}}[i,j]\) is the minimum transmit delay that can be assigned to node \(i\) for transmitting a packet generated by node \(j\). The above constraint ensures that those nodes that need to forward a REQ packet further down the chain, have time to do it before transmitting their data packet up the chain. Secondly, the minimum transmit delay for forwarding other nodes' packets is defined as follows:  
\[\forall n,k\in\{1..N_{\text{sn}}\},\ k>n, \tag{4}\] \[T_{\text{m}}[n,k]=2\big{(}\tau_{\text{p}}[n{+}1]+\tau_{\text{g}} \big{)}+\tau_{\text{rp}}+\tau_{\text{dp}}+T_{\text{tx}}[n{+}1,k],\]  
where \(\tau_{\text{p}}[i]\) is the propagation delay on the \(i^{\text{th}}\) link between adjacent nodes of the linear network topology, i.e., \(\forall i\in\{1..N_{\text{sn}}\},\ \tau_{\text{p}}[i]=T_{\text{p}}[i,i{+}1]\). The above constraint ensures that a node cannot forward a data packet from another node before actually receiving it. Note that in this paper all values in \(T_{\text{Rx}}\) are relative to the time of the REQ packet reception, i.e., \(T_{\text{tx}}[i,j]\) is defined as the time between node \(i\) receiving a REQ packet and transmitting the data packet generated by node \(j\). This is different to the original definition of \(T_{\text{tx}}\) in [8]. This new definition decouples the Tx delays assigned to multiple nodes for forwarding the same data packet up the chain, and enables our proposed greedy algorithm to optimize them in isolation. Our proposed greedy optimization method is shown in Algorithm 1. It iterates over every value in \(T_{\text{tx}}\) in the order that maximizes the chances of scheduling simultaneous spatially separated transmissions. For every Tx delay \(T_{\text{tx}}[i,j]\), the algorithm starts by evaluating the LTDA-MAC schedule using \(T_{\text{tx}}[i,j]=T_{\text{m}}[i,j]\), i.e., the minimum possible value according to (3) and (4). If there are collisions in the schedule, \(T_{\text{tx}}[i,j]\) is incremented by \(\tau_{\text{step}}\), and the schedule is evaluated again. This incremental search continues until the schedule is collision-free. In the experiments reported in this paper the value of \(\tau_{\text{step}}\) was set to \(\tau_{\text{guard}}/2\) which achieved a good trade-off between the algorithm's ability to find good solutions and its computational cost. Incorporating more sophisticated variable step methods is a subject of further work.