# Efficient Resource Scheduling for Multipath Retransmission over Industrial WSAN Systems
## 4 The Proposed Scheduling
### Transmissions Release Algorithm  
As mentioned before, the multipath scheme requires that a packet on a device is transmitted three times at most, including initial transmission and two retransmissions. Thus, we first need to generate all the transmissions and their corresponding orders for a flow before allocating slots and channels. Algorithm 1 is the function of \(TransmissionRelease(F)\), which can generate all transmissions and transmission orders for a flow, according to a given graph \(G\). Actually, the period \(p\) and the routing \(\phi\) of the flow are already known and we mainly focus on producing the collections \(X\) and \(E\) to complete the flow. The initial transmission and the first retransmission use PRP, and the second retransmission uses ARP. A link in \(\phi\) releases two transmissions if it is used for PRP; otherwise, it releases only one transmission for ARP. To obtain all the transmissions, we traverse all the links in \(\phi\) from the source node to the destination node by a first in and first out (\(FIFO\)) pipe. Meanwhile, \begin{table}
\begin{tabular}{c l} \hline \hline
**Symbols** & **Description** \\ \hline \(D_{i}\) & the number of links \(l_{ji}\) in a subgraph, where the node \(n_{i}\) is the \\ \(H[t][c]\) & the transmission allocated for time slot \(t\) and channel \(c\) \\ \(W\) & the collection of time slots, which are already allocated for transmission \\ \(C_{t}\) & the collection of available channels at time slot \(t\) \\ \(\Omega_{t}\) & the collection of all the transmissions allocated to time slot \(t\) \\ \(\Psi_{t}\) & the collection of available sinks at time slot \(t\) \\ \(|C_{t}|_{t},|\Psi_{t}|\) & the number of corresponding elements in the collection \\ \hline
**Functions** & **Description** \\ \hline \(Add(y,Y)\) & the function responsible for adding an element \(y\) into the collection \(Y\) \\ \(Del(y,Y)\) & the function responsible for deleting an element \(y\) into the collection \(Y\) \\ \(ASort(Y,z)\) & the function responsible for sorting all the elements in \(Y\) in ascending \\ order, according to feature \(z\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Symbols and functions. to generate the transmission order, we give each \(n_{i}\) a transmission collection \(X^{\prime}(n_{i})\), which involves the already generated transmissions. The destination node of these transmissions is \(n_{i}\). A node will be put into the \(FIFO\) and obliged to release the transmission until the number of transmissions in its collection \(X^{\prime}(n_{i})\) is equal to \(D_{i}\). \(D_{i}\) is the in-degree of \(n_{i}\), which can be calculate by Equation (8). \[D_{i}=\sum l_{ji},l_{ji}\in\phi \tag{8}\]  
To illustrate the function of \(TransmissionRelease(F)\), we consider the topology shown in Figure 2 as an example. The flow is generated by node \(n_{1}\) and transmitted to node \(n_{10}\). As shown in Figure 3, the generated transmissions in \(X\) are in released sequence after executing Algorithm 1. For example, the first released transmission is \(x(n_{1},n_{2})\), and the fourth is \(x(n_{2},n_{6})\). The transmissions in \(X\) also need sequence collection \(E\) to further explain their routing order, where \(e(2,4)\) represents that the 4 th transmission \(x(n_{2},n_{6})\) must occur after the second transmission \(x(n_{1},n_{2})\). The transmissions without orders can occur simultaneously, which means they can be allocated for the same slot with different channels. We can see that the two adjacent transmissions may not be in continuous order, such as the 6 th transmission \(x(n_{2},n_{4})\) and 7 th transmission \(x(n_{3},n_{4})\). We also notice that \(E\) has two orders, \(e(5,18)\) and \(e(12,18)\), where the transmission \(x(n_{6},n_{10})\) should go after the 5 th and 12 th transmissions. Actually, we only need to comply with the latter order, \(e(12,18)\), which should be considered in slot and channel allocation.