## 3 Alternative Paths for Message Streams in Cluster-Tree Wireless Sensor Networks
### Alternative-Path Definition Algorithm  
The _Alternative-Path Definition_ (ARounD-def) algorithm is performed by the PAN coordinator to find an alternative path for a given message stream. This way, after receiving a source-to-destination communication request, instead of considering the tree path, the PAN coordinator uses the available sensor nodes to define a _shorter inter-cluster path_ between source and destination nodes. This shorter inter-cluster path is related to the smaller number of overlapping clusters that the message stream should traverse from the source to the destination. Currently, the _number of clusters_ is being used, but other metrics could be also used to define the alternative path, e.g., _link quality_, _bandwidth_ or _energy capacity_. Consider an example of a cluster-tree network, where the pair source-destination is located in specific positions in the communication environment as shown in Figure 8.  
Figure 8 illustrates the cluster-tree path between the source and destination nodes. Along this path, each node must wait for the active period of their parent cluster, in order to communicate towards its cluster-head and send the data packets. According to this forwarding strategy, a message stream may face high end-to-end communication delays, which are highly dependent of the beacon scheduling strategy (favouring either bottom-up or top-down traffic, but not both) and of the network congestion behaviour near the PAN coordinator. Instead, the ARounD communication scheme defines a different path, exploiting overlapping clusters, and building a shorter inter-cluster path between source and destination nodes. Figure 9 illustrates an ARounD path for the same example. Note that the defined path also traverses some clusters but does not necessarily use cluster-head nodes to relay data packets from source to destination nodes. Figure 6: Cluster’s active period scheduling along the time. Figure 7: Duty cycle for the specific cluster 3, showing its active and inactive periods. The ARounD communication scheme defines a set of special nodes: the _ARounD Repeater Nodes_ (RP). This type of nodes are responsible for relaying data frames among overlapping clusters along the ARounD path, acting as border nodes between clusters. An RP node is a full function device that sits in the transmission range of two or more cluster-heads, independently of its functionality in the cluster-tree. In order to represent repeater nodes and define the collision domain of the cluster-tree network, we use an adjacency list, which is a structure for the representation of the connectivity. Thus, considering a cluster-tree network with \(N\) cluster-heads, the ARounD scheme defines a set of adjacency lists, one adjacency list per cluster-head. For each \(CH_{i}\) (\(1\leq i\leq N\)), it stores an array of the \(CH_{j}\) (\(1\leq j\leq N\)) adjacent to it. Based on these adjacency lists, we define a list of edges \(E=(RP_{i},RP_{j})\in CH_{i}\) / \(1\leq i,j\leq N\), that are ordered based on their energy capacities. Importantly, both the adjacency lists and the RP nodes are defined during the formation phase of the cluster-tree network through message exchanges. The re-ordering of list \(E\) is done throughout the life of the WSN. Figure 8: Standard cluster-tree path between the source and destination nodes. Figure 9: Alternative-Route Definition (ARounD) path between the source and destination nodes. The first step of the ARounD-def algorithm (lines 2-5 in Algorithm 1) is to use adjacency lists to obtain an inter-cluster graph. Based on this graph, it has all possible inter-cluster paths from a source node to a destination node. With this, the PAN coordinator defines the _shortest inter-cluster path_ between the pair of source and destination nodes, according to a shortest path algorithm (e.g., using the _[PERSON]'s_ algorithm [60]), and considering just the set of edges with an energy level above a predefine threshold.