# A Deadline-Aware Scheduling and Forwarding Scheme in Wireless Sensor Networks
## 1 Introduction  
Wireless sensor networks (WSNs) have been widely used in many applications [1, 2], such as military surveillance, agriculture and environment monitoring. A large number of sensors are deployed in a certain region to measure a parameter, and then, they send the data to a sink node. Since sensors are usually provided with a limited battery, reducing energy consumption has attracted a great deal of attention.  
Duty cycling is a useful solution to reduce consumed energy and prolong network lifetime. However, sleep scheduling results in a high delay, since a node has to wait for the next hop to be active instead of transmitting data immediately [3]. We note that, in some applications, packets are required to arrive at the sink within a certain period of time. For example, the detection of critical events (e.g., forest fire detection [1]) should be reported to the sink node within a specific delay bound. Thus, in order to respond quickly to important events, a delay-constrained forwarding algorithm with a bounded latency is highly desired in practice.  
There have been several studies on both routing and scheduling protocols in order to deal with end-to-end (E2E) delay problems [4; 5; 6; 7; 8; 9]. However, those existing algorithms require global information [7] (e.g., all one-hop delays and communication links in the network), a high message complexity [6; 9] or costly time synchronization between nodes [4; 5; 8]. Moreover, none of them can estimate the distribution of E2E delay given the network parameters before sensor nodes are deployed in WSNs; _i.e._, they can predict neither the packet arrival time at the sink nor the fraction of packets that will reach the destination within a specific period of time.  
In order to address the limitations of existing algorithms, we propose a delay-constrained forwarding algorithm, namely deadline-aware scheduling and forwarding (DASF), which guarantees that packets arrive at the sink with the required probability, or delay-constrained success ratio (DCSR), while maximizing the duty cycle interval. In DASF, the distribution of E2E delay is estimated as a function of the duty cycle interval and the number of potential forwarders (\(m\)), whose distribution is also approximated given the network model and parameters. Then, the maximal value of the duty cycle interval is selected with which the required DCSR is satisfied.  
Using the selected duty cycle interval, each node under DASF schedules its sleep and wake-up times independently. The sender node forwards the packet to the node that wakes up first among the potential forwarders. DASF does not require time synchronization between sensors in WSNs. Moreover, it enables a human operator to assess E2E delay and perform resource planning (e.g., setting the number of nodes) before actual deployment.  
In order to validate the proposed scheme, simulations are performed using various scenarios. Simulation results show that DASF can achieve the required DSCR and outperforms existing algorithms in terms of E2E delay and delay-constrained success ratio (DCSR).  
The rest of this paper is organized as follows. Sections 2, 3 and 4 present related work, the problem definition and the network model, respectively. Then, Section 5 describes a delay-constrained forwarding algorithm in detail. Simulation results are presented in Section 6, and Section 7 concludes the paper and discusses future work.