## 3 Proposed Algorithm  
The design of the proposed algorithm was guided by the following goals:  
* Low communication overhead: excessive message exchange reduces network lifetime;
* Simplicity: the algorithm must demand few computational resources and must not require network topology knowledge;
* Scalability: the solution must be efficient for networks composed of large number of nodes;
* Distributed approach: centralized solutions are unsuitable for WSNs;
* Suitable for wireless networks: the algorithm must construct the routing structure even in the event of message losses or node failures;
* Resilience: the solution must provide multiple paths to the sink;
* Quality of the tree: the quality of the constructed tree must be at least sub-optimal. Our algorithm is called efficient Bellman-Ford (EBF), and it is based on the Bellman-Ford distributed asynchronous version in order to inherit certain characteristics: simplicity and tolerance to message losses or node failures during the execution of the algorithm. DBF is tolerant to message losses and \begin{table}
\begin{tabular}{l c c c} \hline \hline
**Features** & **DBF** & **SHM** & **DFS** \\ \hline Absence of synchronization overhead & \(\bullet\) & & \(\bullet\) \\ Demands few computational resources & \(\bullet\) & & \\ Constructs a resilient structure & & \(\bullet\) & \\ Lack of termination detection & \(\bullet\) & & \\ Inflexible with respect to the metric used to compute the cost of the links & & \(\bullet\) & \(\bullet\) \\ Sensors have to know the network topology & & \(\bullet\) & \(\bullet\) \\ Non-tolerant with respect to message losses or node failures & & \(\bullet\) & \(\bullet\) \\ Excessive message exchange & \(\bullet\) & \(\bullet\) & \\ Non-scalable runtime & & & \(\bullet\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Main features of the algorithms: DBF, shortest hop multipath (SHM) and depth-first search (DFS). node failures, because messages are always broadcast and the algorithm does not require any complex synchronization. Therefore, nodes never remain indefinitely waiting for a message to continue the execution of the algorithm, and hence, a reliable message delivery strategy is unnecessary. Moreover, only a single message is enough for a node to select its parent in the routing structure and to keep the network connected. Logically, the greater the number of lost messages, the lower the quality of the constructed tree. As with DBF, the proposed EBF demands few computational resources, and sensors do not need to know their neighbors. The quality of the trees constructed by both algorithms is evaluated utilizing as metrics the average distance and hop count with respect to the sink. These metrics are directly affected by the number of lost messages during the algorithm execution. Thus, the larger the number of lost messages, the worse the quality of the constructed tree. The excessive message exchange is the main drawback of the DBF algorithm. The more connected the network and the larger the number of sensors, the worse is the performance of DBF. The reason for the low performance in this aspect is the use of the flooding approach. Nodes accept and retransmit to all of their neighbors any paternity offer more advantageous than the offer accepted earlier in terms of the metric to construct the tree. The main difference of EBF with respect to DBF is the inclusion of a strategy to reduce both the number of messages required to construct the tree and the runtime, making it practical for WSNs. Nodes accept and retransmit an offer only if its advantage over the offer previously accepted is greater than or equal to a factor \(\alpha\), \(0<\alpha<1\). The value of \(\alpha\) determines how much a new offer must be more advantageous than the current accepted offer in order to replace it. The value of \(\alpha\) must be chosen so that the quality of the tree is not considerably affected. When \(\alpha=0\), EBF is equivalent to DBF.