# A Deadline-Aware Scheduling and Forwarding Scheme in Wireless Sensor Networks
## 2 Related Work  
In this section, we present existing studies on routing and scheduling protocols that consider the delay issue in a WSN, and we compare these to our algorithm. There is synchronous and asynchronous scheduling in duty-cycled WSNs. In synchronous protocols, nodes cooperate with each other and concurrently switch a radio on and off [10; 11; 12]. For example, [PERSON] _et al._[10] proposed sensor medium access control (S-MAC) in which a node randomly chooses and announces its awake schedule if it has not received a schedule from its neighboring nodes. When receiving a neighboring node's schedule, it will follow this schedule, _i.e._, it synchronizes with other nodes. Unlike synchronous scheduling, in asynchronous protocols [13; 14], every node independently chooses its own sleep scheduling. Hence, senders and receivers do not need to wake up at the same time. In order to ensure packet transmission, nodes exchange scheduling information or periodically broadcast beacon messages. For instance, [PERSON] _et al._[13] developed berkeley media access control (B-MAC), in which a node that wants to transmit a frame sends a long preamble to make sure that the next hop can hear the packet. Since asynchronous scheduling is much simpler than synchronous, our algorithm uses asynchronous scheduling. However, unlike existing asynchronous scheduling algorithms, we consider a forwarding strategy and delay-bound requirement. There have been several routing protocols that consider E2E delay in duty-cycled WSNs [4; 5; 8]. In these protocols, a node makes a forwarding decision based on one-hop delay (_i.e._, the node selects the next hop that has a low one-hop delay among nodes in the candidate set). For instance, [PERSON] _et al._[4] proposed random asynchronous wakeup (RAW), in which each node randomly selects its scheduling. Each node also maintains a forwarding candidate set (FCS), which includes nodes closer to the destination than itself by a given threshold distance. In order to forward packets, a sensor node will choose the closest node to the sink among all active nodes in the FCS. If there is no active node in the FCS, the node will wait for the closest node in the FCS to wake up. In addition, [PERSON] _et al._[PERSON] et al. (2016) proposed lukewarm potato forwarding (LPF) in which each node can predict the wake-up time of its neighboring nodes. In LPF, nodes initially build the shortest path tree rooted at the sink. To forward data, a node sends the packet to its parent in the tree if the wait time until its parent wakes up is less than a given threshold value. Otherwise, the packet is transmitted to the node that wakes up earliest among neighboring nodes that are closer to the sink. In order to obtain the wake-up time of neighboring nodes, all nodes use the same pseudo random number generation algorithm, but different seed values. Using a local seed, each node initially generates its active time. When a node wakes up, it broadcasts its local seed, \(s_{n}\), and a random number, \(S_{n}\). By receiving \(s_{n}\) and \(S_{n}\), a node is able to predict the next active time of its neighboring node. Compared to our algorithm, the listed protocols only try to reduce the E2E delay instead of meeting a given delay bound in WSNs. Additionally, they require more information to be exchanged than our algorithm. For instance, in the RAW algorithm, nodes need to exchange beacon messages that include the node ID, clock, schedule, lifespan and location whenever nodes switch on the radio. In the case of LPF, sensor nodes broadcast the node ID, a local seed and a newly-generated random number, \(S_{n}\), when they wake up. In contrast, our work only requires nodes to broadcast the node ID and group number. Moreover, RAW, LPF and the gradient-based multi-path routing protocol (GMRP) [PERSON] et al. (2016) require time-synchronization [PERSON] et al. (2016); [PERSON] et al. (2016) between nodes, whereas our algorithm does not. In order to find the path with the least delay, [PERSON] _et al._[PERSON] et al.