## 2 Background
### Related Work
Following this approach, a specific cluster is able to receive the parent's superframe in a given timeslice and schedule its superframe in an adjacent timeslice. The clusters are scheduled within a major cycle, which is cyclically repeated. In order to avoid inter-cluster collisions, a set composed of the PAN coordinator and all the clusters that can be reached in an even number of hops are scheduled in a given timeslice; then, all other clusters are scheduled in alternate timeslices. [PERSON] et al. [58] proposed an IEEE 802.15.4-based cluster-tree formation protocol, named Multi-Channel Cluster Tree (MCCT), which uses multiplexed transmissions across different channels, in order to avoid beacon collisions. In addition, it uses a shared control channel for the cluster-tree construction and maintenance operations. Thus, a node just scans the control channel to request an association. The joining node defines its parent cluster-head based on the number of associated children. The cluster-head with lower number of children is selected. Thus, the association process occurs during the active period, using the channel of the specific cluster-head. These works use multi-channel approaches in order to avoid beacon collisions, which add overheads related to the channel's maintenance and control. [PERSON] et al. [7] proposed the Time Division Beacon Frame Scheduling (TDBS) approach, which defines a Superframe Duration Scheduling (SDS) algorithm for cluster-tree networks. In this approach, superframe duration and beacon frames of a given cluster are scheduled in the inactive periods of its neighbour clusters to avoid inter-cluster interferences. The schedulability condition of SDS is both necessary and sufficient, and is obtained considering the duty cycle information of nodes [15]. The TDBS approach defines minor and major cycles to schedule a cluster set with different superframe durations and beacon intervals. All clusters are organised within the defined major cycle, based on the Least Common Multiple (LCM) of the beacon periodicities for all clusters. The major cycle is divided in minor cycles, which are used to sequentially fit all clusters. In this approach, clusters are organised in an increasing order of beacon periodicities. To break ties, these clusters are organised in a decreasing order of superframe durations. Clusters are sequentially organised within the minor cycles, until reaching the end of the major cycle. TDBS defines the start time for all clusters in a collision-free scheduling scheme. However, it does not consider any message stream prioritisation and therefore may not be adequate to support time-sensitive applications. [PERSON] and [PERSON] [14] present a Time-Division Cluster Scheduling (TDCS) mechanism to avoid inter-cluster collisions and to meet all end-to-end deadlines of time-bounded message streams. This mechanism employs a pure time-division scheduling approach, avoiding the inter-cluster collision problem. Besides, it aims to define the maximum TDCS period (major cycle) in order to minimise the energy consumption of the nodes. This is a challenging task because it is necessary to consider the message stream requirements, meeting all their end-to-end deadlines. To solve this problem, the authors formulate the TCDS approach as a cyclic extension of the Resource Constrained ProjectScheduling with Temporal Constraints (RCPS/TC), which defines a feasible schedule considering the temporal and resource constraints of a set of tasks. After modelling this problem, they use an integer linear programming algorithm to solve the scheduling problem. The main weakness of TDBS and TDCS approaches is the use of an off-line scheduling approach, that assumes static network conditions. Thus, [PERSON] et al. [39] presented an interesting alternative to modify the scheduling at run-time, in order to provide QoS (Quality of Service) to message streams. Basically, they proposed the use of two different techniques: Dynamic Cluster Re-ordering (DCR) and Dynamic Bandwidth Re-allocation (DBR).