# DDS: A Delay-Constrained Duty-Cycle Scheduling Algorithm in Wireless Sensor Networks
## 1 Introduction
The sink collects the network parameters (e.g., the number of nodes in each group, the number of potential forwarders, and the data generation rate). Using the collected information, the one-hop delay distribution of each group is obtained as a function of the duty cycle interval, the delay bound, and the required DSR. Since our work considers custom node deployment, one-hop delay at nodes in different groups may have different distributions. So, we cannot apply the classical central limit theorem [24] to the network scenario under consideration. Note that the Lyapunov central limit theorem [24] is used to estimate the distribution of a sum of random variables which can be non-identically distributed. Therefore, the DDS scheme uses the Lyapunov theorem to determine the E2E delay distribution. Finally, the maximal duty cycle interval that satisfies the given delay bound requirement is determined by using the obtained E2E delay distribution. We also note that the proposed algorithm can overcome the limitations of our previous work [25], which assumed that nodes are randomly deployed following a uniform distribution in a circular area. By estimating the delay distribution based on the collected network topology information, the algorithm in this work is suitable for general cases where node deployment scenarios depend on various user demands. Moreover, existing studies [25; 26] had to assume that one-hop delays of different node groups are identically distributed in order to use the classical central limit theorem. In contrast, this work allows each node group to have a different delay distribution by proving the Lyapunov condition and using the Lyapunov central limit theorem [24], which results in a higher performance in practical WSN scenarios. In order to validate the performance of DDS, we compare DDS with four algorithms: the optimal anycast packet-forwarding (OAPF) [16], the optimal geographical progress (OGP) [19], and two extended deadline-aware scheduling and forwarding (DASF) [25] algorithms. The proposed algorithm was evaluated using performance metrics, including the achieved DSR, the total energy consumption by nodes in the network, and the average E2E delay. Simulation results show that DDS outperforms other existing algorithms in terms of the delay requirements (i.e., the given delay bound and DSR) and energy consumption. Although the average E2E delay under DDS is longer than that of OAPF and OGP, DDS satisfies the delay requirements (i.e., the required DSR) in various test scenarios (e.g., varied delay bounds, required DSR, and event rates), while OAPF and extended DASF could not satisfy the delay requirement in some cases. Moreover, DDS achieves better energy efficiency than OGP. In summary, the main contributions of our work are listed as follows:  
* This work proposes the delay-constrained duty-cycle scheduling (DDS) algorithm to achieve low energy consumption while satisfying the delay requirement in duty-cycled WSNs. Unlike several existing works [7; 8; 9; 10; 11; 12; 20; 21; 22] which needed strict time synchronization, DDS does not require time synchronization nor wake-up synchronization. Moreover, in contrast to some studies which assumed a specific node deployment [18; 19; 25] (i.e., uniformly random distribution), the proposed duty-cycle scheduling algorithm can be applied to WSNs with various node deployment scenarios. * We define the problem of maximizing the duty cycle interval subject to the delay requirement in duty-cycled WSNs. The sink first collects the network topology information, on the basis of which the one-hop delay distribution is computed. Then, the E2E delay distribution is estimated as a function of the duty cycle interval using the Lyapunov central limit theorem, which allows nodes in different groups to have different delay distributions. Finally, the maximal duty cycle interval is determined using the estimated E2E delay distribution to minimize consumed energy while satisfying the delay requirement.