## 3 Alternative Paths for Message Streams in Cluster-Tree Wireless Sensor Networks
### Network Model  
Assume a set of sensor nodes randomly deployed in a wide-scale environment. These nodes are organised in clusters according to the IEEE 802.15.4/ZigBee cluster-tree topology [5; 6]. It is worth mentioning that whenever there are link breakages or modifications of the network topology, there will be the need to rebuild the network. This reorganisation may be done following a strategy similar to the ones proposed by [7; 59]. For the sake of simplicity, we assume a static set of clusters and we also assume that the network topology does not change along the network lifetime. The network is composed of \(N\) coordinator nodes (including the PAN coordinator), that act as Cluster-Heads (_CHs_) of their clusters and periodically send beacon frames to synchronise their child nodes, such that:  
\[CH_{i}=(SD_{i},BI_{i}),\quad 1\leq i\leq N, \tag{3}\]  
where \(i\) is a unique identifier for the specific cluster, \(SD_{i}\) corresponds to the _Superframe Duration_ and \(BI_{i}\) is the _Beacon Interval_ of the cluster-head \(CH_{i}\). We assume that values for BO and SO are defined according to the load supported by each of the branches of the cluster-tree, considering a superframe duration allocation approach, as the one proposed by [59]. We also assume that the cluster's active periods were previously scheduled, considering a classical time division superframe scheduling approach, as the one proposed by [7]. Therefore, there are no beacon frame collisions caused by overlapping clusters. Importantly, for each node is assigned a hierarchical global address and all nodes operate over the same communication channel.  
Figure 5 illustrates an example of this random cluster-tree network with 200 nodes. The PAN coordinator is located in the centre of the wide-scale communication environment. The dot marks represent leaf nodes and the asterisk marks represent cluster-head nodes.  
Figure 6 shows a typical time division superframe scheduling scheme. As it can be seen, the cluster's active periods are organised along the time, in order to avoid interferences. Thus, during the active period of their clusters, sensor nodes can communicate with their coordinators (cluster-heads) and vice-versa. During the inactive periods, sensor nodes can sleep to save energy.  
Figure 5: Cluster-tree network obtained from simulations.  
Figure 7 shows the duty cycle for cluster 3, considering a cluster-tree time division superframe scheduling. Note that the active period of cluster 3 starts at instant _offset_ 3, where all of its sensor nodes wake up to sense the environment and to communicate. During the remaining inactive period, these nodes can sleep to save energy.  
The proposed ARounD communication scheme uses two algorithms (Alternative-Path Definition and Alternative-Path Activation algorithms) to establish an alternative path for specific source-to-destination message streams. These algorithms use available communication resources during the inactive periods of the underlying cluster-tree network. Importantly, ARounD communication algorithms use the current network topology and information gathered during the cluster-tree formation process. Thus, a topology modification will require both a reconfiguration of the cluster-tree WSN and an update of network information, in order to keep the operation of the ARounD algorithms. This issue is inherent to any static approach used in cluster-tree WSNs. However, the assessment of the reconfiguration time that a cluster-tree network takes to reconfigure its topology is out of the scope of this work. In the next subsections, we detail these algorithms and the related ARounD structures.