# DDS: A Delay-Constrained Duty-Cycle Scheduling Algorithm in Wireless Sensor Networks
## 2 Related Work  
Duty cycling is an effective solution for reducing energy consumption in WSNs [11; 27; 28; 29; 30; 31; 32; 33]. However, since a long E2E delay can be a critical problem in duty-cycled WSNs, there have been a lot of studies that considered the E2E delay. Several studies [7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19] focused on minimizing the expected E2E delay. For example, [PERSON] et al. [14] proposed a sleep/wake scheduling scheme to minimize the E2E delay by increasing the active periods of the nodes according to the traffic load. Nodes are assigned different sleep/wake schedules considering three cases. The first is based on the node's distance from the sink, the second is the topological importance of the node (e.g., a node that is the forwarder for many nodes has a longer active duration), and the third is the occurrence of events (e.g., when an event occurs near the nodes, their active period increases). [PERSON] et al. [16] proposed a sleep/wake scheduling policy that aims at minimizing the E2E delay and maximizing the lifetime of event-driven WSNs. In their study, nodes maintain a list of forwarding candidates, each of which is assigned a priority. When a node wants to transmit a packet, it checks the channel for a certain period of time to find forwarding nodes that wake up in that period. If there is only one forwarder awake, the transmitter transmits the packet to this node. In the case of multiple forwarders, the transmitter selects the forwarder that has the highest priority. The expected E2E delay at each node is calculated based on the awake probability, the forwarding candidates, and the priority of the forwarders. Then, OAPF is proposed to find an optimal forwarding policy that minimizes the expected E2E delay. [PERSON] et al. [19] proposed a geographic routing algorithm, called optimal geographical progress (OGP), in order to reduce the expected packet latency in duty-cycled WSNs. Each node maintains a set of possible forwarders that make geographical progress of at least a threshold and forwards the packets to the first wake-up node among candidate forwarders. [PERSON] et al. showed that the threshold value has a great impact on the packet E2E delay, and a low latency can be obtained by using an appropriate threshold value. Since those studies only considered the expected E2E delay, they could not guarantee or control the portion of the packets that arrive at the sink within the delay bound. Note that even when the expected E2E delay is shorter than the delay bound, a large portion of the packets might reach the sink after the delay bound due to the variance in E2E delay. In contrast, our work estimates a probabilistic distribution of the E2E delay as a function of the duty cycle interval, the delay bound, and the required DSR. This enables the WSN to satisfy the delay bound constraint while lowering energy consumption by controlling the duty cycle interval. It is worthwhile to note one study that considered E2E delay distribution [26]. However, its objective was only to estimate the E2E delay distribution using a given fixed routing path, rather than to control network parameters to improve network performance (e.g., satisfying the delay requirement or reducing energy consumption). In addition, it required random variables for one-hop delays to be identically distributed, which may not be practical in certain network scenarios. A few studies [20; 21; 22; 25] considered the delay bound requirement in WSNs. For example, [PERSON] and [PERSON] [20] proposed a wake-up scheduling-based forwarding scheme to satisfy the delay bound while the network achieves a high packet delivery ratio. This scheme schedules the active and dormant states of each node based on the hop count and the expected delivery ratio to the sink. This study is different from ours in that it attempted to improve the packet delivery ratio rather than reducing energy consumption. In addition, this scheme requires time synchronization between neighboring nodes. [PERSON] et al.