## 3 Proposed Scheduling Algorithm
### Estimating Amount of Packets in Queue
``` //NCH:the number of available channels //T\({}_{k}\):the number of packets that node \(k\) transmits in each slot frame //T\({}_{S}\):the number of time slots that needs to be assigned to node \(k\) //PA\({}_{k}\):the per-hop link PRR of link \(<\)k,R\({}_{k}\)> //DC\({}_{k}\):a set of nodes that are duplex-conflicting with node \(k\) (1) Initialization:QL\({}_{k}\) = 100 \(\times\) T\({}_{k}\); MQL\({}_{k}\) = 100 \(\times\) (1-PA\({}_{k}\)); (2) Its = 0; ch = 0; (3)N \(\leftarrow\) a set of nodes which satisfiesTS\({}_{k}\)\(\geq\) 1 and QL\({}_{k}\)\(\geq\)MQL\({}_{k}\); (4) while (N is not empty) { } (5) PRIORITITZE(N); // prioritize the nodes in N (6) \(M\leftarrow\) q; (7) while(ch < N\({}_{ch}\)) { (8) \(n\gets N(0)\); (9) assign (ts, ch) to link <n,P\({}_{n}\)>; (10) \(M\leftarrow\) M\(\cup\)<n,P\({}_{n}\)>; (11) DLETE_DC(N), n); // delete n and nodes in DC\({}_{n}\) from N (12) if (N is empty) break; (13) \(\mathit{ch}\leftarrow\mathit{ch}+1\); (14) } (15) ADJUST_TS_QL(M); // adjust TS, QL of nodes in M (16) \(\mathit{ts}\leftarrow\mathit{ts}+1\); ch = 0; (17) \(N\leftarrow\mathit{a}\) set of nodes which satisfiesTS\({}_{k}\)\(\geq\) 1 and QL\({}_{k}\)\(\geq\)MQL\({}_{k}\); (18) } (19) ASSIGN_ADDITIONAL_TS(); // check the QL of nodes and assign additional time slots when QL\({}_{k}\)\(\geq\)MQL\({}_{k}\) Function:PRIORITZE(N) //N:a set of nodes to which a slot can be assigned (1) Sort the nodes in N in descending order of QL values; (2) In the case of a tie, sort the nodes in N in descending order of TS values; (3) In the case of a tie, sort the nodes in N in descending order of tree level; Function:DLETE_DC(N, n) //N:a set of nodes to which a slot can be assigned //n:selected node //DC\({}_{n}\):a set of duplex-conflicting nodes with node n (1) Delete n and all nodes in DC\({}_{n}\); Function:ADJUST_TS_QL(M) //M:a set of links with channels assigned //R\({}_{k}\):PRR of link <k,P\({}_{k}\)> (1) for (each link <k,P\({}_{k}\)> in M) { (2) \(TS_{k}=TS_{k}\)-1; (3) if (QL\({}_{k}\) > 100) then (4) tx_amount = 100; (5) else (6) tx_amount = QL\({}_{k}\); (7) QL\({}_{k}\) = QL\({}_{k}\) -(tx_amount \(\times\) R\({}_{k}\)); (8) QL\({}_{\bar{\bar{\bar{\bar{\bar{\bar{\bar{\bar{\bar{\bar{\bar{\bar{\bar{\bar{ \bar{\bar{\bar{\bar{\bar{ \bar{       }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}\))))))



## 4 Performance Evaluation

We evaluated the performance of the proposed scheduling algorithm and compared it with the approach in [12] using the Cooja simulator on the Contiki platform [15]. The existing approaches in [10; 11; 12] for guaranteeing the end-to-end reliability used two types of time slots: dedicated and shared time slots. The shared time slot scheme can reduce the number of time slots by utilizing the advantage of statistical multiplexing of independently transmitted packets. We also used the shared time slot approach in this paper. After determining the number of time slots for each node, the scheduling algorithm decides the time-slot number and channel number for each time slot assigned to the nodes. The scheduling of the existing approaches are similar, so we only compared it with the approach in [12] (we call this a flow-based approach). For fair comparison, we used the same example in [12], which is shown in Figure 4a. The scheduling result of the flow-based approach for the example on a 3-channel network is shown in Figure 4b. We assumed that all sensor nodes had one packet to transmit at the beginning of each slot frame and the target end-to-end reliability of packets was 99%. Figure 4c shows the MQL and TS values for scheduling in the proposed scheduling

Figure 3: Scheduling steps (**a**) and the assignment result (**b**) for the sample graph in Figure 1 with 2-channels. algorithm and the scheduling result of the proposed algorithm is shown in Figure 4d. The number of assigned time slots of the proposed algorithm is 23, which is one time slot less than that of the flow-based approach.