# 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
Let \(P(h_{j}\leq h_{j}|n_{j}^{i})\) denote the probability that the one-hop delay of an arbitrary packet to be transmitted by node \(n_{j}^{i}\) is not larger than \(h_{j}\). A random variable, \(w_{j}^{k}\), is defined as the wake-up time for node \(n_{j}^{k}\) from among \(u_{j}^{i}\) PFCs of node \(n_{j}^{i}\) during a duty cycle interval where \(k=1,2,\ldots,u_{j}^{i}\). Let \(w_{j}^{k}\) denote a given value for random variable \(w_{j}^{k}\). Since nodes wake up once, and they independently choose a random wake-up time in each duty cycle interval, the probability that node \(n_{j}^{k}\) wakes up before \(w_{j}^{k}\) is \(P(w_{j}^{k}\leq w_{j}^{k})=\frac{w_{j}^{k}}{T}\) where \(0\leq w_{j}^{k}\leq T\). Furthermore, node \(n_{j}^{i}\) selects the first wake-up node from among \(u_{j}^{i}\) nodes. Therefore, the one-hop delay of a packet transmitted by node \(n_{j}^{i}\) is the earliest wake-up time of \(u_{j}^{i}\) nodes. The probability \(P(\mathrm{h}_{j}>h_{j}|n_{j}^{i})\), in which the one-hop delay of an arbitrary packet to be transmitted by node \(n_{j}^{i}\) is greater than \(h_{j}\), equals the probability that \(u_{j}^{i}\) forwarding candidates of node \(n_{j}^{i}\) wake up after \(h_{j}\), and it can be expressed as follows:  
\[ \begin{split} P(\mathrm{h}_{j}>h_{j}|n_{j}^{i})&= \prod_{k=1}^{u_{j}^{i}}P(\mathrm{w}_{j}^{k}>h_{j})=\prod_{k=1}^{u_{j}^{i}} \left[1-P(\mathrm{w}_{j}^{k}\leq h_{j})\right]=\prod_{k=1}^{u_{j}^{i}}\left(1- \frac{h_{j}}{T}\right)\\ &=\left(1-\frac{h_{j}}{T}\right)^{u_{j}^{i}}\end{split}  \tag{5}\]  
Therefore, the probability that the one-hop delay of an arbitrary packet to be forwarded by node \(n_{j}^{i}\) will not be greater than \(h_{j}\) can be calculated as follows:  
\[ \begin{split} F(h_{j}|n_{j}^{i})&=P(\mathrm{h}_{j }\leq h_{j}|n_{j}^{i})=1-P(\mathrm{h}_{j}>h_{j}|n_{j}^{i})\\ &=1-\left(1-\frac{h_{j}}{T}\right)^{u_{j}^{i}}\end{split}  \tag{6}\]  
From Equations (4) and (6), the marginal probability mass function of the one-hop delay, \(F(h_{j})\) of group \(j\), can be calculated using the law of total probability as follows:  
\[F(h_{j})=\sum_{k=1}^{N_{j}}F(h_{j}|n_{j}^{k})P(n_{j}^{k})=\sum_{k=1}^{N_{j}} \left[1-\left(1-\frac{h_{j}}{T}\right)^{u_{j}^{k}}\right]P(n_{j}^{k}) \tag{7}\]  
According to Equation (7), the probability density function \(f(h_{j})\) is expressed as follows:  
\[f(h_{j})=\frac{dF(h_{j})}{dh_{j}}=\sum_{k=1}^{N_{j}}\frac{u_{j}^{k}}{T}\left(1 -\frac{h_{j}}{T}\right)^{u_{j}^{k}-1}P(n_{j}^{k}) \tag{8}\]  
Mean \(\mu_{j}\) and variance \(\sigma_{j}^{2}\) of one-hop delay \(\mathrm{h}_{j}\) are calculated as follows:  
\[ \begin{split}\mu_{j}&=E[\mathrm{h}_{j}]=\int_{0}^{T }h_{j}f(h_{j})dh_{j}=T\sum_{k=1}^{N_{j}}\frac{P(n_{j}^{k})}{u_{j}^{k}+1}\\ &=\psi_{j}T\end{split}  \tag{9}\]  
\[ \begin{split}\sigma_{j}^{2}&=E[(\mathrm{h}_{j}-\mu_ {j})^{2}]=E[\mathrm{h}_{j}^{2}]-E[\mathrm{h}_{j}]^{2}=\int_{0}^{T}h_{j}^{2}f(h_ {j})dh_{j}-\mu_{j}^{2}\\ &=T^{2}\sum_{k=1}^{N_{j}}\left[\frac{2P(n_{j}^{k})(u_{j}^{k}+1)-( u_{j}^{k}+2)(P(n_{j}^{k}))^{2}}{(u_{j}^{k}+1)^{2}(u_{j}^{k}+2)}\right]\\ &=\omega_{j}^{2}T^{2}\end{split}  \tag{10}\]  
We obtain \(\psi_{j}\) and \(\omega_{j}\) using the information collected in the group determination phase, as follows:  
\[ \begin{split}\psi_{j}&=\sum_{k=1}^{N_{j}}\frac{P(n_ {j}^{k})}{u_{j}^{k}+1}\\ \omega_{j}^{2}&=\sum_{k=1}^{N_{j}}\left[\frac{2P(n_ {j}^{k})(u_{j}^{k}+1)-(u_{j}^{k}+2)(P(n_{j}^{k}))^{2}}{(u_{j}^{k}+1)^{2}(u_{j} ^{k}+2)}\right]\end{split}  \tag{11}\]