# Escalator: An Autonomous Scheduling Scheme for Convergecast in TSCH
## 5 Analysis of Escalator
### Proof of the Conflict-Freeness of Convergecast Schedule  
We prove that the schedule of the convergecast slotframe is conflict-free using the wireless conflict model. First, we prove that the schedule of the convergecast slotframe does not cause the primary conflict defined in Definition 1. The convergecast slotframe creates unicast and broadcast links between the parent and child nodes along the DODAG topology. We prove that the schedule generated by Escalator does not cause a primary conflict by showing that there is no conflict in the links between the parent and children. Theorem 5.1: _The unicast and broadcast links generated by the schedule of the convergecast slotframe do not cause the primary conflict._  
Proof: We show the orthogonality of the unicast and broadcast links generated by the convergecast slotframe, proving that the primary conflict does not occur. A schedule for the convergecast slotframe of a node consists of the four operations assigned by the timeslot allocation mechanism, as described in Section 4.1. For node \(v_{i}\), SET_BT(\(i\)) and SET_RX(\(i\),\(i\)) assign \(BT_{i}\) and \(RX_{ii}\) operations to the same timeslot of \(i\times 2-1\). However, since \(v_{i}\) does not receive \(v_{i}\) packets, \(RX_{ii}\) is not used. SET_BR(\(i\),\(j\)) and SET_TX(\(i\),\(j\)) assign \(BR_{ij}\) and \(TX_{ij}\) operations to the same timeslot of \(j\times 2\) for nodes \(v_{i}\) and \(v_{j}=p(v_{i})\). However, since \(v_{j}\) is the parent of \(v_{i}\), \(TX_{ij}\) is not used. In the convergecast slotframe, the broadcast links are always assigned to the timeslot for which unicast links are not used via SET_BT and SET_BR. Thus, unicast and broadcast links generated by the schedule of the convergecast slotframe are orthogonal. Theorem 5.2: _There is no primary conflict among nodes with the same parent in the convergecast slotframe._  
Proof: We show the orthogonality of the schedule among nodes with the same parent in the convergecast slotframe, proving that the primary conflict does not occur. Let nodes \(v_{i}\) and \(v_{j}\) (\(i\
eq j\)) have the same parent, then \(SG(v_{i})\bigcap SG(v_{j})=\emptyset\). Therefore, the schedules of \(v_{i}\) and \(v_{j}\) assigned by the timeslot allocation mechanism do not use the same timeslot except \(BR\) operations. Furthermore, since \(H_{v_{i}}=H_{v_{j}}\), the schedule of \(v_{i}\) and \(v_{j}\) is not influenced by the sliding slot frame. Therefore, the schedules of \(v_{i}\) and \(v_{j}\) are orthogonal to each other. Theorem 5.3: _There is no primary conflict between the parent and child nodes in the convergecast slotframe._  
Figure 8: Conflicts in TDMA wireless networks. Proof. : We show that in the convergecast slotframe, it is impossible for the parent and the child nodes to transmit or receive data simultaneously, thus proving that the primary conflict does not occur. Let nodes \(v_{i}\) and \(v_{j}\in C(v_{i})\). By the timeslot allocation mechanism, \(v_{i}\) and \(v_{j}\) assign \(TX\) and \(BR\) to even timeslots and assign \(RX\) and \(BT\) to odd timeslots. Since \(H_{v_{j}}=H_{v_{i}}+1\), the schedule of \(v_{j}\) is shifted one more left than the schedule of \(v_{i}\) by the sliding slotframe mechanism. Therefore, if \(v_{i}\) executes \(TX\) in even timeslots and executes \(RX\) in odd timeslots, \(v_{j}\) executes \(TX\) in odd timeslots and executes \(RX\) in even timeslots. As with unicast, if \(v_{i}\) executes \(BT\) in odd timeslots and executes \(BR\) in even timeslots, \(v_{j}\) executes \(BT\) in even timeslots and executes \(BR\) in odd timeslots. Therefore, it is not possible to transmit or receive data simultaneously in one timeslot between two nodes that have a parent child relation. Corollary 1: _The schedule of the convergecast slotframe does not cause the primary conflict._  
Proof. : The convergecast slotframe creates unicast and broadcast links only between the parent and child nodes along the DODAG topology. The unicast and broadcast links of the convergecast slotframe do not cause the primary conflict by Theorem 1.