# Escalator: An Autonomous Scheduling Scheme for Convergecast in TSCH
## 3 Related Work  
### Scheduling of WSNs based on TDMA and Channel Hopping  
TDM-A and channel hopping-based WSNs require scheduling to generate timeslot and channel schedules for communication between nodes. The number and order of timeslots scheduled for a node determine the throughput of the node and the end-to-end delay of the packet transmission. In addition, the scheduling of timeslots and channels considering both the interference of wireless networks and the conflicts of the schedule can improve the reliability of the network. Since scheduling determines the performance of the network, an efficient scheduling scheme is required to improve the network performance. Several schemes have been proposed for efficient scheduling. These schemes could be classified into centralized, decentralized and autonomous scheduling schemes, depending on which the scheduling is actually performed. The centralized scheduling schemes aim at generating an optimal schedule by using the information such as the link status and traffic requirements of the nodes collected by the central entity of the network such as the system manager. The Industrial Wireless Sensor Networks (IWSNs) such as Wireless HART and International Society of Automation (ISA) 100.11a, use the centralized scheduling for high reliability and real-time performance. [PERSON] et al. [14] proved that the scheduling problem is NP-complete and suggested both the node-based and the level-based heuristic scheduling algorithms. [PERSON] et al. [15] proposed a reliable path generation algorithm based on Wireless HART. The authors define reliability requirements of the graph and propose algorithms for graph generation and timeslot assignment satisfying the requirements. In TASA (Traffic Aware Scheduling Algorithm) [16], the central entity generates a schedule based on the network connectivity graph and traffic requirements, taking into account the conflicts and interactions between links. In the distributed scheduling schemes, unlike the centralized schemes, scheduling functions are distributed across nodes. The nodes exchange information such as the link status and traffic requirements and use this information to determine the schedule. Therefore, the distributed scheduling can respond to network changes more quickly than the centralized schemes, which collect information from the central entity and determine the schedule. [PERSON] et al. [17] proposes a decentralized scheduling algorithm for mobile nodes in the TSCH network. Mobile nodes maintain their network connectivity through advertisements and link creations using a rendezvous slot. DeTAS (Decentralized Traffic Aware Scheduling) [18] generates a macro-schedule that assigns non-overlapping timeslot sections per DODAG in a multi-sink topology. In addition, each DODAG root performs a micro-schedule with respect to the traffic of the nodes for the assigned timeslot section. [PERSON] et al. [19] proposed a distributed scheduling scheme based on a Proportional, Integral and Derivative (PID) control algorithm. Nodes calculate the required number of timeslots using the number of packets in the queue at the start of the slotframe and perform the negotiation and reservation of timeslots with neighbor nodes using the 6 top protocol [13]. DeAMON (Decentralized Adaptive Multi-hop scheduling for 6 TiSCH Networks) [20] gradually creates a schedule in the direction toward the root node starting from a leaf node that has no children. Through this, sequential schedules considering the packet forwarding path are generated to minimize the end-to-end latency. Furthermore, each node collects the schedule information of neighboring nodes through overhearing and generates a schedule capable of parallel communication using the schedule information. The Leapfrog Collaboration [21] provided path diversity using redundant paths. The nodes select an alternative parent in addition to the default parent and create a timeslot schedule so that the same packet can be sent to both parents.