## 5 Multi-Path Routing Protocol
### Multi-Path Searching Algorithm  
If it is only required to confirm that the network is \(1-connected\) or not, one can simply run the depth-first search or breadth-first search, both having \(O(|V|+|E|)\). The work in [124] employs the breadth-first search algorithm to judge whether a node caused the network partitions. In this case, the link rebuilding strategy will start to achieve the topology connectivity. The work in [125] proposes an optimal algorithm to find the single-source shortest non-negative path with complexity \(O(|E|+|V|\log|V|)\). The finding the maximum number of \(k-disjoint\) path problem can be solved by network flow theory, specifically the minimum cut or maximum flow theory. There are many polynomial time algorithms solving maximum flow problems. So far, the best algorithm has complexity \(O(|V||E|\log\frac{|V|^{2}}{|E|})\)[96]. The multi-path from the source and destination for all nodes can be found in \(O(kN^{2})\) running the time algorithm [34]. However, for the WSNs, there are always some special considerations, such as the computational capacity, that need to be considered before implementing the algorithm, so an \(O(kN^{2})\) running time perhaps is unacceptable in the WSNs. Hence, the problems that have been solved in graph theory may be either hard or even impossible to apply to WSNs, because they have an unacceptable algorithm complexity. Therefore, the heuristic algorithms are more feasible. For example, a greedy algorithm can work as follows: first, the algorithm runs to choose one path to the destination by selecting the best hop at each step, then running the same algorithm again to find the second path except for the node (link) that has already been chosen, and so on, such as routing protocols [8, 126, 127]. The work in [8] realizes a multi-path routing algorithm by means of only using the local information. The sink first floods data to the destination according to the metric, like lowest delay or loss. In the end, the primary path is established, as the path (Sink-A-B-Destination) in Figure 9. After that, the destination sends the \"alternative path reinforcement\" to the sink by choosing the second preferred neighbor, and along the way back to the source, each neighbor chooses the second preferred neighbor that has not been chosen before. If it has been chosen, it has to choose another one. As illustrated in Figure 9, the path (Destination-B) has been chosen in the primary path, so at this step it will not choose (Destination-B) as part of the secondary path. Instead, it will select (Destination-F-E-Sink) as the secondary path. Finally,the \(2-disjoint\) path is formed. Note that: (1) this method only uses the local information; and (2) during the time used in setting up the network to find the multi-path, it might take a somewhat long time and consume too much energy. The multi-path algorithms are preferably distributed, e.g., [128, 129]. The work in [128] is a distributed algorithm to find out a complete disjoined path. It is based on any other existing routing protocols to find the multi-path from the source to the destination and then proposes a distributed algorithm to refine those paths in order to eliminate the paths that have mutual interference. The work in [129] proposes a new routing protocol called GRAd, which is a routing protocol that makes no attempt to identify which of its neighbors are delivering a packet. It considers the mobility of sensor nodes. The nodes travel towards randomly chosen locations at random speeds and pause for a fixed amount of time after reaching the destination. The simulation results show that GRAd is robust in the face of a changing topology, because it enlists multiple neighbor nodes to relay messages from one place to another. Even if one node moves out of place, other nodes are often available to deliver the packet without resorting to rebuilding the route. However, a negative consequence of this high robustness as [129] shows is that the routing load is high.