# DDS: A Delay-Constrained Duty-Cycle Scheduling Algorithm in Wireless Sensor Networks
## 4 A Delay-Constrained Duty-Cycle Scheduling Algorithm
### Estimation of One-Hop Delay Distribution  
Since the E2E delay is the sum of the one-hop delays, estimating the one-hop delay distribution of each group is necessary to obtain the E2E delay distribution. The one-hop delay of packets depends on the active/dormant schedules of the transmitters' PFCs. With a larger number of PFCs, the one-hop delay can be shorter. In addition, nodes transmit not only their own packets but also packets received  
Figure 2: Example of data transmission phase. from other nodes. Thus, nodes may transmit a different number of packets from the others. Note that the one-hop delay experienced by a group also depends on the number of packets to be transmitted. For instance, assume that nodes A and B in group 3 have to transmit 10 packets to nodes in group 2, and the one-hop delays of nodes A and B are 1 s and 10 s, respectively. If the number of packets to be transmitted by nodes A and B are the same, the sum of one-hop delays for the 10 packets is \(5\times 1+5\times 10=55\) s, and the average is 5.5 s. On the other hand, if nodes A and B transmit nine packets and one packet, respectively, the sum of one-hop delays for the 10 packets is \(9\times 1+1\times 10=19\) s, and the average will be 1.9 s. Therefore, we consider both the number of PFCs and the number of packets to be transmitted in order to estimate the one-hop delay distributions of the groups. To facilitate the discussion, suppose that every node generates only one data packet destined for the sink. Let expected packet(s) to be transmitted (EPT) denote the number of packets that a node has to forward to the sink. Let \(u_{j}^{i}\) and \(v_{j}^{i}\) denote the number of PFCs and the EPT of node \(n_{j}^{i}\), respectively. As a result, the \(i\)th node in group \(j\) has to transmit \(v_{j}^{i}\) packets to the earliest awake node from among \(u_{j}^{i}\) potential forwarders. The EPT for node \(n_{j}^{i}\) depends on the number of node \(n_{j}^{i}\)'s PFCs, as follows:  
\[v_{j}^{i}=1+\sum\limits_{k=1}^{N_{j+1}}\alpha_{j}^{k}\frac{v_{j+1}^{k}}{u_{j+1 }^{k}} \tag{3}\]  
where 1 is the number of packets generated at node \(n_{j}^{i}\). The term \(\sum\limits_{k=1}^{N_{j+1}}\alpha_{j}^{k}\frac{v_{j+1}^{k}}{u_{j+1}^{k}}\) represents the number of packets received from other nodes. \(\alpha_{j}^{k}\) is a coefficient with respect to node \(n_{j}^{k}\). If node \(n_{j}^{i}\) is a PFC of node \(n_{j+1}^{k}\), \(\alpha_{j}^{k}=1\); otherwise, \(\alpha_{j}^{k}=0\). Figure 1 also shows the EPT for each node in the network. Nodes \(n_{3}^{1}\) and \(n_{3}^{2}\) in group 3 generate one packet and do not receive any packets from the others. Thus, node \(n_{3}^{1}\) and \(n_{3}^{2}\) have the same EPT, i.e., \(v_{3}^{1}=v_{3}^{2}=1.0\). Since node \(n_{2}^{1}\) only forwards packets from node \(n_{3}^{1}\) and \(u_{3}^{1}=2\), the EPT for node \(n_{2}^{1}\) is \(v_{2}^{1}=1.0+\frac{v_{3}^{1}}{u_{3}^{1}}=1.0+\frac{1.0}{2}=1.5\) packets. Let us define \(P(n_{j}^{i})\) as the probability that an arbitrary packet in group \(j\) is forwarded by node \(n_{j}^{i}\). With a larger EPT for node \(n_{j}^{i}\), the probability that this node transmits a packet is higher. Therefore, \(P(n_{j}^{i})\) depends on the EPT of the nodes, and can be expressed as follows:  
\[P(n_{j}^{i})=\frac{v_{j}^{i}}{\sum\limits_{k=1}^{N_{j}}v_{j}^{k}} \tag{4}\]  
As shown in Figure 1, nodes \(n_{2}^{1}\), \(n_{2}^{2}\), and \(n_{2}^{3}\) in group 2 have 1.5 EPT, 2.5 EPT, and 1.0 EPT to forward, respectively. Thus, the total number of packets to be transmitted by the nodes in group 2 are \(1.5+2.5+1.0=5.0\) packets. According to Equation (4), the probabilities that nodes \(n_{2}^{1}\), \(n_{2}^{2}\), and \(n_{2}^{3}\) transmit packets is \(\frac{1.5}{5.0}=0.3\), \(\frac{2.5}{5.0}=0.5\), \(\frac{1.0}{5.0}=0.2\), respectively. Then, the one-hop delay distribution of each group is obtained based on the number of PFCs and the EPT. Let \(h_{j}\) denote the random variable for the one-hop delay of group \(j\), and let \(h_{j}\) be a given value for random variable \(h_{j}\).