# DDS: A Delay-Constrained Duty-Cycle Scheduling Algorithm in Wireless Sensor Networks
## 4 A Delay-Constrained Duty-Cycle Scheduling Algorithm
### Duty Cycle Interval Determination  
When estimating the E2E delay distribution, previous researchers [25; 26] used the classical central limit theorem [24] to approximate the E2E delay distribution. To this end, they assumed that the random variables for the one-hop delay of different groups are identically distributed. As a result, the node deployments for the groups have to be the same, which may not be practical in many WSN deployment cases. In order to address this limitation, we estimate the E2E delay distribution using the Lyapunov central limit theorem [24], which does not require random variables for the one-hop delay of groups to be identically distributed. As a result, our work is more suitable for various node deployment scenarios, e.g., in buildings or outdoors, in deterministic or nondeterministic node deployment layouts. In this section, we first use the Lyapunov central limit theorem to approximate the E2E delay distribution. Then, the duty cycle interval is inferred from the obtained E2E delay distribution. Since the sink is always active, the one-hop delay of the first hop is zero. If packets that have the longest E2E delay satisfy the delay bound, all packets in the network can satisfy the delay bound. Therefore, we consider the packets' E2E delay, which is transmitted by nodes in group \(g\) and expressed as follows:  
\[\mathrm{d}=\sum_{k=2}^{g}\mathrm{h}_{k} \tag{12}\]  
where \(\mathrm{h}_{2},\mathrm{h}_{3},\cdots,\mathrm{h}_{g}\) are independently and non-identically distributed random variables. Note that the one-hop delay is less than the duty cycle interval \(|\mathrm{h}_{k}|\leq T\ \forall k\). Each one-hop delay \(\mathrm{h}_{j}\) has the mean \(\mu_{j}\) and variance \(\sigma_{j}^{2}\), which are determined by Equations (9) and (10), respectively. Let \(\mathrm{r}_{j}=\mathrm{h}_{j}-\mu_{j}\). The mean and variance of a random variable \(\mathrm{r}_{j}\) are calculated as follows:  
\[E[\mathrm{r}_{j}]=E[h_{j}]-\mu_{j}=0 \tag{13}\]  
\[ \begin{split} Var[\mathrm{r}_{j}]&=E[(\mathrm{r}_{ j}-E[\mathrm{r}_{j}])^{2}]=E[\mathrm{r}_{j}^{2}]-E[\mathrm{r}_{j}]^{2}\\ &=E[\mathrm{r}_{j}^{2}]=E[(\mathrm{h}_{j}-\mu_{j})^{2}]\\ &=\sigma_{j}^{2}\end{split}  \tag{14}\]  
Let \(s_{g}\) be calculated as follows:  
\[s_{g}^{2}=\sum_{k=2}^{g}Var[\mathrm{r}_{k}]^{2}=\sum_{k=2}^{g}E[\mathrm{r}_{k} ^{2}]=\sum_{k=2}^{g}\sigma_{k}^{2} \tag{15}\]  
The Lyapunov central limit theorem states that if \(\{\mathrm{r}_{2},\mathrm{r}_{3},\ldots\mathrm{r}_{g}\}\) is a sequence of independent random variables that has a zero mean and a finite variance, and if the Lyapunov condition holds, the sum of \(\frac{\mathrm{r}_{k}}{s_{g}}\) converges to the standard normal distribution as \(g\) approaches infinity:  
\[\sum_{k=2}^{g}\frac{\mathrm{r}_{k}}{s_{g}}\rightarrow\mathcal{N}(0,1) \tag{16}\]  
The Lyapunov condition for a sequence of \(\{\mathrm{r}_{2},\mathrm{r}_{3},\ldots,\mathrm{r}_{g}\}\) is expressed as follows:  
\[\lim_{g\rightarrow\infty}\sum_{k=2}^{g}\frac{1}{s_{g}^{2+\delta}}E\big{[}| \mathrm{r}_{k}|^{2+\delta}\big{]}=0 \tag{17}\]  
where \(E\big{[}|\mathrm{r}_{k}|^{2+\delta}\big{]}\) is the \((2+\delta)^{th}\) moment of the random variable \(\mathrm{r}_{k}\) for some \(\delta>0\). Therefore, we first prove that random variables \(\{\mathrm{r}_{2},\mathrm{r}_{3},\ldots,\mathrm{r}_{g}\}\) satisfy the Lyapunov condition with the following lemma. **Lemma 1**. : _Let \(\{r_{2},r_{3},\ldots,r_{g}\}\) be independent random variables for which \(|r_{j}|\leq T\) with \(j=2,3,\ldots,g\) and \(\lim_{g\to\infty}\dfrac{T}{s_{g}}=0\). Then, \(\{r_{2},r_{3},\ldots,r_{g}\}\) satisfy the Lyapunov condition._  
Proof. : Since \(\mathrm{h}_{j}\) is the one-hop delay of group \(\mathrm{j}\), we have \(0\leq\mathrm{h}_{j}\leq T\) and \(0\leq\mu_{j}\leq T\). In other words, \(\mathrm{h}_{j}-\mu_{j}\leq T\) and \(\mathrm{h}_{j}-\mu_{j}\geq-T\).