## 3 Alternative Paths for Message Streams in Cluster-Tree Wireless Sensor Networks
### Alternative-Path Activation Algorithm  
The _Alternative-Path Activation_ (ARounD-act) algorithm defines the activation instants (schedule) for the selected RP nodes, which is also performed by the PAN coordinator. The activation instant of an RP node is a crucial issue. Due to the current cluster-tree communication, the ARounD communication must be adequately scheduled; otherwise, it can generate collisions and interferences with the previously scheduled cluster-tree communication. To prevent these problems, the ARounD communication scheme activates the RP nodes during their inactive periods and only when there is no activity in the neighbourhood. We define the _ARounD Activity Period_ as the period during which an RP node can be activated without interfering with the cluster-tree communication. Within this context, we define two types of ARounD activity periods, as follows:  
* _Global ARounD Activity Period_ (GAP): period during which there are no active clusters in the cluster-tree network;
* _Local ARounD Activity Period_ (LAP): period during which there are no active clusters in the neighbourhood of the RP node. The GAP period means that all nodes in the cluster-tree are inactive. Considering that the beacon interval (\(B1\)) must be large enough to ensure that all superframe durations (\(SD_{i}\)) can be scheduled and that there is also some available spare time during BI, the GAP period is defined based on the following protocol constraint:  
\[BI=GAP+\sum_{i=1}^{N}SD_{i}, \tag{4}\]  
Thus, during the GAP period, RP nodes can be activated without generating interferences with the underlying cluster-tree network. In turn, the LAP period means that exists at least one activated cluster in the cluster-tree network, but that those clusters are not in the neighbourhood of the RP nodes. Therefore, a special care must be taken of when activating RP nodes, as these nodes may generate interferences with the cluster-tree network. Unlike the GAP period, which is the same for all RP nodes, the LAP period is dependent of the clusters in the neighbourhood of the RP nodes. For this reason, considering the ARounD path and the RP nodes, the ARounD-act algorithm avoids the active periods of the clusters and of their  
Figure 10: Applying the ARounD-def Algorithm: (**a**) Selecting repeater nodes for the first pair of clusters; (**b**) Selecting repeater nodes for the second pair of clusters. neighbours in the cluster-tree network. In this way, an RP node that becomes active to perform the ARounD communication does not generate interferences with the remaining clusters that are active in the cluster-tree network. Thus, considering both the cluster-tree scheduling and the nodes that belong to the ARounD path (source, destination and RP nodes), the target of the ARounD-act algorithm is to define the activation instants for each of these nodes. For each ARounD node it will be defined a transmission time (ARounD Tx time) and a reception time (ARounD Rx Time), except for the source and destination nodes that will only have, respectively, a defined transmission and reception time. When the ARounD-act algorithm (Algorithm 2) is launched, the PAN coordinator starts exploring the clusters' active period scheduling (line 3 in Algorithm 2), in order to search the first _ARounD activity period_ (GAP or LAP, but preferably GAP) that is larger or equal to the required period to allocate to the source node (as transmission node) and to the next RP node (as reception node) of the ARounD path. After, the algorithm searches for other _activity period_ for this same RP node (now, as transmission node) and to the next RP node (as reception node). This procedure is recursively performed until reaching the destination node (lines 2-14 in Algorithm 2). Whenever the ARounD-act algorithm is not able to find any existing ARounD activity periods to allocate to all RP nodes (lines 13 and 14 in Algorithm 2), the algorithm fails and the next higher layer is notified.