## 2 Related Work
The protocol uses a data fusion strategy along the tree route and minimizes collisions by arranging the transmission sequence for the nodes within a cluster. The use of spanning trees for routing and clustering in WSNs is an important issue, and it is the focus of our study. The most common methods of constructing spanning trees are: depth first search (DFS) and breadth first search (BFS) [20]. The strategy followed by DFS is to visit the vertices reachable from a previous vertex, before visiting their adjacent vertices. The DFS method constructs trees with a few branches and leaves. The structure looks more like a path. Because of the tree depth, sensor nodes consume a lot of time and energy to send data to the sink. A large amount of time is also required to construct the DFS tree, since DFS is inherently sequential [21]. The strategy followed by BFS is to visit all adjacent vertices of a previous vertex before visiting other vertices. The BFS method constructs trees with many branches and consequently a small depth. BFS is the basis for algorithms that construct SPTs. In the context of WSNs, an SPT is a spanning tree rooted at the sink, such that the cost from any node to the sink is minimal. The cost \(cost(p)\) of a path \(p=<i,j,sink>\) is the sum of the costs of its constituent links:  
\[cost(p)=cost_{i,j}+cost_{j,sink}. \tag{1}\]Several different metrics have been proposed in the literature to compute the cost of the links [1]. Basic approaches use the number of hops and the distance to the sink. Distributed Bellman-Ford is used in [1, 22, 23] for constructing SPTs in WSNs. According to [12], the SPT is constructed by the iteration:  
\[W_{i}^{t+1}=\min_{j\in N_{i}}\quad cost_{i,j}+W_{j}^{t},\quad i\
eq 1, \tag{2}\]  
where \(N_{i}\) represents the set of neighboring nodes of \(i\), \(W_{i}^{t}\) is the weight of node \(i\) in step \(t\), _i.e._, the last estimated cost of the path from \(i\) to the root node computed at node \(i\), and \(cost_{i,j}\) is the cost assigned to the link between nodes \(i\) and \(j\). The initial conditions are \(W_{1}^{0}=0\) and \(W_{i}^{0}=\infty\) for \(i\
eq 1\). The pseudocode of DBF is presented in Algorithms 1 and 2. The sink initiates the tree construction by sending a broadcast message with its cost (Algorithm 1, Step 2). When a node \(i\) receives the message containing the weight of the sending node \(j\), it computes the path cost to the sink if it selects node \(j\) as the parent node. For doing so, node \(i\) adds the link cost to node \(j\) to the received weight. If the cost of the current route from node \(i\) to the sink exceeds the cost of the route that is being offered (Algorithm 2, Step 3), node \(i\) selects \(j\) as the temporary parent (Algorithm 2, Step 4), updates its weight (Algorithm 2, Step 5) and broadcasts a message with its new weight (Algorithm 2, Step 6). The algorithm ceases when there are no more messages in transit on the network. [PERSON] and [PERSON] [12] proved that the SPT is constructed even if some nodes are slower than others to propagate or calculate their weights. ```
1:\(parent_{sink}=sink\); \(W_{sink}=0\)
2: broadcast \(<sink,W_{sink}>\)
```  
**Algorithm 1**Distributed Bellman-Ford (DBF), initiator node. In [9], the authors argue that the DBF is unsuitable for WSNs because of its high energy cost and also because the sink cannot know whether the algorithm has terminated. To provide a suitable solution to construct SPTs in WSNs, the authors of [9] propose the SHM algorithm, which requires five types of messages (probe, acknowledgment (ack), pulse, pulseAck and pulseNack) and uses the hop count to the sink as the cost of the links. The algorithm is synchronous, and the sink is responsible for initializing and finalizing the spanning tree construction, which is performed in layers. To initiate the construction process, the sink broadcasts a message (probe) offering paternity and then waits for an acknowledgment message (ack) from each of its possible children.