## 3 Alternative Paths for Message Streams in Cluster-Tree Wireless Sensor Networks
### Alternative-Path Definition Algorithm
In the current version of algorithm, we have used the remaining node energy level as input parameter for shortest path algorithm. However, other metrics can be used, such as the link quality level. ```
input :Adjacency List C; \(MStream_{m}\): \([SRC_{m},\,DEST_{m}]\); output :\(RPnodes\) = set of Repeater nodes;
1 // First Step: to define the shortest inter-cluster path
2\(Cluster_{src}\) = get_Cluster(\(SRC_{m}\));; // Get the cluster ID of the source node
3\(Cluster_{dest}\) = get_Cluster(\(DEST_{m}\));; // Get the cluster ID of the destination node
4\(ARounD\_Path_{m}\) = Dijkstra_Algorithm(C, \(Cluster_{src}\), \(Cluster_{dest}\));
5\(cluster2 cluster_{m}\) = set of pairs of \(ARounD\_Path_{m}\);
6 // Second Step: to select the repeeater nodes
7 for (each pair[\(Cluster_{i},Cluster_{j}\)]\(\in cluster2 cluster_{m}\))do
8 if (leaf_RP(\(Cluster_{i}\), \(Cluster_{j}\)) \(\
eq\) 0) then
9\(RPnodes_{i,j}\) = selectRP(leaf_RP(\(Cluster_{i}\), \(Cluster_{j}\)));
10 else
11\(RPnodes_{i,j}\) = selectRP(\(cluster\)-head_RP(\(Cluster_{i}\), \(Cluster_{j}\)))
12
13 return\(RPnodes\);
```  
**Algorithm 1**Alternative-Path Definition (ARounD-def) Algorithm  
After defining the shortest inter-cluster path (ARounD path), the next step is to select the repeeater nodes that will relay data packets along this path. In order to structure and optimise this selection, we decompose this path (set of clusters) as a sequence of pairs of clusters (called _pairs of ARounD clusters_, lines 4 and 5 in Algorithm 1). For each pair of clusters, the selected repeeater nodes are responsible for relaying data frames from the initial cluster to the next cluster. Figure 10 illustrates the selection of repeeater nodes for the pairs of ARounD clusters. As it can be seen, the ARounD-def algorithm selects a specific repeeater node for the first pair of clusters. Following the ARounD path, the algorithm selects repeeater nodes for the second pair of clusters and, finally, the destination node is reached. This selection process of repeeater nodes uses an optimisation algorithm (lines 7-11 in Algorithm 1), in order to select the most adequate set of RP nodes. For this, ARounD keeps two lists of repeeater nodes for each pair of clusters: list of _leaf_ RPs, which contains RP nodes that act as leaf nodes in the cluster-tree network; and a list of _cluster-head_ RPs, with RP nodes that act as cluster-heads. As long as we are dealing with full function devices, both type of RP nodes can act as repeeter nodes during the ARounD communication. Importantly, in these two lists, RP nodes are ordered based on their energy capacities, being selected the node with more remaining energy. In order to select an RP node between a pair of clusters belonging to the ARounD path, the proposed scheme firstly inspects the list of _leaf_ RPs, to save energy of cluster-heads that are responsible to keep the cluster-tree topology. If there are no available leaf RPs with a remaining energy level above the predefined threshold, the algorithm selects a cluster-head node to act as RP node in the ARounD path. The _selectRP_ function (lines 9 and 11 in Algorithm 1) implements the mechanisms to select an RP node among the available RP nodes in each list. This function can be implemented using other selection criteria, such as: random approaches, link quality of nodes or based on the physical position (location-aware protocols) [61; 62]. After selecting the repeater nodes for each pair of ARounD clusters, the next step performed by the PAN coordinator is to define their activation times.