# Efficient Resource Scheduling for Multipath Retransmission over Industrial WSAN Systems
## 4 The Proposed Scheduling
### CEM-RM Algorithm
Therefore, the condition can be expressed as follows:  
\[\sum_{i=0}^{k-1}|X_{i}|\cdot\left\lfloor\frac{p_{k}}{p_{i}}\right\rfloor+|X_{ k}|\leq\left\lfloor\frac{p_{k}}{\kappa}\right\rfloor\cdot|C|,\forall F_{k}\in F^{\prime} \tag{10}\]0 \[\sum_{i=0}^{k-1}|X_{i}|\cdot\left\lfloor\frac{p_{k}}{p_{i}}\right\rfloor+|X_{ k}|\leq\left\lfloor\frac{p_{k}}{\kappa}\right\rfloor\cdot|C|,\forall F_{k}\in F^{\prime} \tag{10}\]1 \[\sum_{i=0}^{k-1}|X_{i}|\cdot\left\lfloor\frac{p_{k}}{p_{i}}\right\rfloor+|X_{ k}|\leq\left\lfloor\frac{p_{k}}{\kappa}\right\rfloor\cdot|C|,\forall F_{k}\in F^{\prime} \tag{10}\]2 \[\sum_{i=0}^{k-1}|X_{i}|\cdot\left\lfloor\frac{p_{k}}{p_{i}}\right\rfloor+|X_{ k}|\leq\left\lfloor\frac{p_{k}}{\kappa}\right\rfloor\cdot|C|,\forall F_{k}\in F^{\prime} \tag{10}\]3 \[\sum_{i=0}^{k-1}|X_{i}|\cdot\left\lfloor\frac{p_{k}}{p_{i}}\right\rfloor+|X_{ k}|\leq\left\lfloor\frac{p_{k}}{\kappa}\right\rfloor\cdot|C|,\forall F_{k}\in F^{\prime} \tag{10}\]4  
The above two conditions represent the situations of node interference and scheduling interference in slot and channel scheduling. The difference between the designed algorithm and RM algorithms is that we assign the communication resources by the order of each flow, instead of the slot sequence. Thus, we traverse all the transmissions in each period-sorted flow (lines 3 and 6) and assign the slots and channels to each transmission. To avoid interference, the scheduling should be adjusted when the allocation meets these conditions. We add all assigned transmissions at time slot \(t\) into \(\Omega_{t}\). We define \(C_{t}\) and \(\Psi_{t}\) as the collections of available channels and sinks at time slot \(t\), respectively. Their elements will be removed by the \(Del()\) function when the corresponding channels or sinks have already assigned. Moreover, \(\varpi_{\tau}\) is used to record the slot offset allocated to the transmission \(\tau\) in every flow, and it is responsible for finding the earliest available slot which does not break the routing order (lines 11-13). There could be several transmissions at a CES. Thus, changing a normal slot to a CES means that the slot expands for multiple transmissions. With the above considerations, we can finally obtain the scheduling table \(H\) when all transmissions are scheduled within their period. In the algorithm, we define \(|N_{F}|\) and \(|X_{F}|\) as the maximum number of nodes and transmissions, respectively, and they are all related to the length of the flow. For example, for a four-hop flow in a routing tree topology, \(|N_{F}|\) is less than 24. All the nodes have a PRP except the sink node and have an ARP except the first-hop nodes and the sink node. Thus, \(|X_{F}|\) is less than \(2\times(2^{4}-1)+1\times(2^{3}-1)=37\). The number of iterations of the \"**for**\" loop in line 3 and the \"**while**\" loop in line 6 are \(O(\gamma)\) and \(O(|H|)\), respectively. Moreover, the time complexities in line 2, line 4, line 11, and line 14 are \(O(\gamma log(\gamma))\), \(O(|N_{F}|^{3})\), \(O(|X_{F}|)\), and \(O(T/p_{m})\), respectively. Therefore, the time complexity in a worst case is \(O(\gamma log(\gamma)+\gamma(|N_{F}|^{3}+|H||X_{F}|+|H|\cdot T/p_{m}))\). In practicality, the periods of different applications could not have much difference; thus,transmission based on the packet's absolute deadline, while LLF schedules a transmission based on the packet's laxity, which is defined as the transmission's deadline minus remaining transmission time. The schedules of individual RM and LLF are not suitable with our applications due to the quantity of nodes and period. Therefore, we also add multiple sinks into each compared scheduling policy for fairness. Thus, we respectively denote the two schedules as M-RM and M-LLF in the following simulations and experiments. Different topology structures need different quantities of communication resources. Thus, four kinds of topology structures are generated for comparison, which are denoted as Tp1, Tp2, Tp3, and Tp4.