## 3 Proposed Scheduling Algorithm
### Estimating Amount of Packets in Queue  
The transmission on a wireless link is determined probabilistically based on the PRR of the link. When a packet is transmitted on link \(<\)\(k\), \(P_{k}\)\(>\) with PRR \(R_{k}\), it will be transmitted to node \(P_{k}\) with probability \(R_{k}\) and stay in node \(k\) with probability (\(1-R_{k}\)). We expressed the amount of packets in the queue of a node in percentage, called QL (queue level), by considering the probabilistic transmission of the wireless link. For example, when node 3 has one packet to transmit in the queue and there is no packet in node 2, as shown in Figure 2b, \(QL_{2}\) = 0 and \(QL_{3}\) = 100. If node 3 transmits a packet to node 2 in a time slot, the QLs of nodes 2 and 3 change so that \(QL_{2}\) = 70 and \(QL_{3}\) = 30 after the time slot because the PRR of link \(<\)3,2\(>\) is 70%. We can estimate the amount of packets in the queue of a node by its QL. Higher QL means a higher number of packets in the queue. The proposed scheduling algorithm utilizes the QL information to determine a node to transmit in a time slot. We assumed that all nodes had a fixed number of packets at the beginning of each slot frame. After the convergecast tree is constructed, the scheduling server receives [\(T_{k}\), \(P_{k}\), \(R_{k}\)] from each sensor node k. After that, the scheduling server calculates \(PA_{k}\) and \(TS_{k}\) for each node \(k\) based on Equations (1)-(3). The proposed scheduling algorithm utilizes multiple channels and assigns multiple nodes to a time slot if they are not in duplex-conflicting relationship [8]. For scheduling, the server sets the following information to each node:  
* \(QL_{k}\) (QL of node \(k\)) is initialized to (\(100\times T_{k}\));
* \(MQL_{k}\) (Minimum QL of node \(k\)) is set to \(100\times\) (\(1-PA_{k}\)), which specifies the minimum QL of node \(k\) for a time slot to be assigned; and
* \(DC_{k}\) is a set of nodes that are in duplex-conflicting relationship with node \(k\)[7]. The proposed scheduling algorithm starts from the first time slot to decide the nodes to transmit among the nodes that have remaining time slots and their queue level is above their minimum level. The proposed algorithm uses a QL-based prioritization scheme to assign the current time slot to the nodes, which gives higher priority to the nodes with higher QL. The scheduling algorithm performs the following steps to determine the nodes that can transmit their packets in the current time slot. 1. Determine a set of nodes that need to be scheduled, \(N\), in the current time slot \(t\) (initially 0);
2. Prioritize the nodes in \(N\) based on \(QL_{k}\), \(TS_{k}\), and tree level of node \(k\);  
Figure 2: PA and TS values for each node in the example network of Figure 1 (**a**), and QL change after transmission on link \(<\)3,2\(>\) (**b**). Choose the node with the highest priority, \(n\), and assigns channel 0 of time slot \(t\) to node \(n\);
4. Delete \(n\) and the nodes in \(DC_{n}\) from \(N\);
5. Choose the next highest priority node, \(n\), in \(N\) and assigns the next available channel to node \(n\);
6. Repeat steps 4 and 5 until \(N\) becomes empty or there is no available channel; and
7. Adjust the QLs of nodes that are transmitting or receiving in time slot \(t\) considering the PRR values of the links and go to 1 for the next time slot \((t+1)\). Algorithm 1 shows the details of the proposed scheduling algorithm. After initializing the QL and MQL values of each node, we obtain a set of nodes, \(N\), to which time slots can be assigned in step 3. All the nodes in N have to satisfy that \(TS_{k}\geq 1\) and \(QL_{k}\geq MQL_{k}\) for each node k in \(N\). In the main loop of (4)-(18), the nodes in \(N\) are prioritized in the PRIORITIZE(\(N\)) function. We prioritized the nodes based on the order of the highest QL, the highest TS, and the highest tree level. In the loop of (7)-(14), we selected the nodes that can transmit in the current time slot ts at the same time and assign to the available channels.