## 3 Proposed Algorithm
Even though we chose \(\alpha=0.1\) for the comparisons between DBF and EBF, computer simulations show that values between 0.06 and 0.1 are appropriate. The choice of a particular \(\alpha\) depends on the application and on the goal that one intends to reach. The larger the value of \(\alpha\), the larger the reduction in the number of messages and in the execution time; however, the quality of the constructed tree decreases with \(\alpha\). With respect to the multiple paths, the strategy is to make sensor nodes store all received paternity offers in order to construct a set of alternative parents. This strategy is inspired by the SHM algorithm. If a parent candidate sends multiple offers, only the last one is stored. Similarly to the DBF and assuming that Node 1 is the sink node, the construction of the SPT is given by iteration:  
\[W_{i}^{t+1}=\min_{j\in N_{i}}\quad cost_{i,j}+W_{j}^{t},\quad i\
eq 1, \tag{3}\]  
starting from the initial conditions \(W_{1}^{0}=0\) and \(W_{i}^{0}=\infty\) for \(i\
eq 1\) and subject to the constraint:  
\[adv_{i,j}\geq\alpha, \tag{4}\]  
where parameter \(adv_{i,j}\) is the advantage of the route offered by \(j\) with respect to the cost of the current route of node \(i\) and can be calculated by:  
\[adv_{i,j}=\left(W_{i}^{t}-\left(cost_{i,j}+W_{j}^{t}\right)\right)/W_{i}^{t}. \tag{5}\]  
Algorithms 3 and 4 present the EBF pseudocode. The sink initiates the tree construction by broadcasting a message with its cost (Algorithm 3, Step 2). When a node \(i\) receives the message containing the weight of the sending node \(j\) and it does not have a parent node, node \(i\) performs the following steps, represented in Algorithm 4:1. [label=()]
2. Selects \(j\) as temporary parent (Step 4);
3. Updates its weight (Step 5);
4. Broadcasts a message with its new weight (Step 6). ```
1:\(parent_{sink}=sink\); \(W_{sink}=0\)
2: broadcast \(<sink,W_{sink}>\)
```  
**Algorithm 3**Efficient Bellman-Ford (EBF), initiator node. ```
1:\(parent_{i}=null\); \(W_{i}=\infty\); AP\({}_{i}=\emptyset\)
2:while node \(i\) receives \(<j,W_{j}>\) message from node \(j\)
3:if\(parent_{i}=null\)then
4:\(parent_{i}=j\)
5:\(W_{i}=W_{j}+cost_{i,j}\)
6: broadcast \(<i,W_{i}>\)
7:else
8:if\((\exists(j,x)\mid x\in\Re\land(j,x)\in\text{AP}_{i})\)then
9:\(\text{AP}_{i}=\text{AP}_{i}\setminus\{(j,x)\}\)
10:endif
11:if\((W_{i}-(W_{j}+cost_{i,j}))/W_{j}\geq\alpha\)then
12:if\(parent_{i}\
eq j\)then
13:\(\text{AP}_{i}=\text{AP}_{i}\cup\{(parent_{i},W_{i})\}\)
14:\(parent_{i}=j\)
15:endif
16:\(W_{i}=W_{j}+cost_{i,j}\)
17: broadcast \(<i,W_{i}>\)
18:endif
19:if\(parent_{i}\
eq j\)then
20:\(\text{AP}_{i}=\text{AP}_{i}\cup\{(j,W_{j}+cost_{i,j})\}\)
21:endif
22:endif
23:endifwhile
```  
**Algorithm 4**EBF, non initiator node. Otherwise, if node \(i\) already has a parent node, it adds the link cost to the node \(j\) to the received weight and computes the advantage of the new route with respect to the current route. If the advantage of the new route is at least equal to \(\alpha\) (Algorithm 4, Step 11), node \(i\) performs the following steps, represented in Algorithm 4:  
1. [label=()]
2. Checks if \(j\) is its parent. If \(j\) is not its parent, then node \(i\) adds the parent node to the set of alternative parents (Steps 12 and 13). The set of alternative parents of node \(i\) is denoted by \(AP_{i}\). 3. Selects \(j\) as the temporary parent (Step 14). This check is required to ensure that the current parent node is not added to the set of alternative parents;3. Updates its weight (Step 16);
4. Broadcasts a message with its new weight (Step 17). However, if the new route is not considered sufficiently advantageous, node \(i\) simply adds \(j\) together with its weight plus the cost of the link \((i,j)\) to the set of alternative parents (Steps 19 and 20). Inevitably \(j\) becomes the parent node or becomes part of the set of alternative parents.