# Concurrent Transmission Based on Distributed Scheduling for Underwater Acoustic Networks
## 3 Concurrent Transmission Based on Distributed Scheduling
### Joint Optimization of Sending Sequence and Time
#### 3.3.2 Sending Sequence Optimization  
In Section 3.3.1, the optimized data sending time of each source node can be obtained using Equation (3) when the sending sequence is given. However, the total transmission time changes with the sending sequence due to the unequal propagation delays among different nodes. Therefore, the sending sequence should also be optimized to achieve better performance. If there are \(N\) pairs of nodes that succeed in handshaking in a transmission cycle, there will be \(N!\) sending sequence combinations, which requires a huge amount of computation when \(N\) becomes large. So, we propose a dynamic programming-based method to jointly optimize the sending sequence and time.  
In the proposed method, the optimization problem is modeled by a state machine with \(N+2\) states. These states include the starting state, ending state, and state \(\{ST_{i}|1\leq i\leq N\}\) which correspond to the \(N\) source nodes. The state machine starts from the starting state and ends at the ending state. The starting state can transfer to state \(ST_{i}\). State \(ST_{i}\) can transfer to the ending state. State \(ST_{i}\) can transfer to state \(ST_{j}\), where \(i\
eq j\), without any loops in the state transfer sequence. Define the cumulative weight of a state transfer sequence as the total transmission time. Then, the sending sequence optimization problem is equivalent to determine a state transfer sequence with the minimum cumulative weight. To simplify the discussion, we assume that all the data packets have the same sizes of \(L^{data}\). The proposed method can be implemented using the following steps:1. Create \(N\) transition paths from the starting state to state \(ST_{i}\), \(1\leq i\leq N\), and initialize the cumulative weights of these transition paths to 0. Set the iteration time \(r=1\).
2. For each surviving path, the states contained in this path are deleted from the state set \(Q=\{ST_{1},ST_{2},\ldots,ST_{N}\}\) to obtain a new state set \(Q_{k,r}\), where \(k\) is the index of the surviving path. Transfer the state machine from the current state to a new state in \(Q_{k,r}\). The sending time of the corresponding new node is given by: \[T_{k,r}^{data}=\left\{\begin{array}{l}D,r=1\\ \max[T_{k,l}^{data}+L^{data}+\max[D_{s_{kl}d_{kr}}-D_{s_{lr}d_{kr}},D_{s_{kl} d_{kl}}-D_{s_{lr}d_{kl}}]]I=1\sim r-1]+C,r>1\end{array}\right.,\] (5) where \(T_{k,l}^{data}\) denotes the sending time of the \(l\)-th source node in the \(k\)-th surviving path. \(s_{kl}\) and \(d_{kl}\) denote the \(l\)-th source node and its corresponding destination node in the \(k\)-th surviving path, respectively; and \(D_{s_{kl}d_{kj}}\) denote the propagation delay from \(s_{ki}\) to \(d_{kj}\). The cumulative weight of the new path can be given by: \[W_{k,r}^{data}=\max\{T_{k,j}^{data}+L^{data}+D+C\Big{|}i=1\sim r\}.\] (6)
3. Select the path with the least cumulative weight from all the paths that transfer to state \(ST_{i}\), \(1\leq i\leq N\), as the surviving path and delete the others. Set the current state of each surviving path to the new state added in the \(r\)-th iteration.
4. If \(r<N\), then \(r=r+1\) and repeat steps 2-4 for another iteration. Otherwise, all surviving paths transfer from the current state to the ending state. The state sequence in the surviving path with the smallest cumulative weight is the optimized sending sequence.  
The proposed method only has \(N\) iteration steps, so the calculation complexity is low. However, because the increased weight is not fixed as many dynamic programming problems and will change with the prior state sequence in a path, the proposed method does not guarantee obtaining the best solution.