DFDP: A Distributed Algorithm for Finding Disjoint Paths in Wireless Sensor Networks with Correctness Guarantee

Abstract

In wireless sensor networks, routing messages through multiple (node) disjoint paths between two sensor nodes is a promising way to increase robustness, throughput, and load balance. This paper proposes an efficient distributed algorithm named distributedly finding disjoint paths (DFDP) to find k disjoint paths connecting two given nodes s and t. A set of paths connecting s and t are disjoint if any two of them do not have any common nodes except s and t. Unlike the existing distributed algorithms, DFDP guarantees correctness; that is, it will output k disjoint paths if there exist k disjoint paths in the network or the maximum number of disjoint paths otherwise. Compared with the centralized algorithms which also guarantee correctness, DFDP is shown to have much better efficiency and load balance by theory analysis and simulation results.

1. Introduction

A typical wireless sensor network (WSN) comprises a large number of small-size battery-powered sensor nodes deployed in a large area. Since the radio transmitting range of sensor nodes is very limited, data exchanging in WSNs usually needs to be relayed in a multihop manner, which makes efficient message routing a crucial problem. Instead of routing messages through a single path, multipath routing, especially routing through multiple (node) disjoint paths, has become more and more popular [1–5]. Let s and t denote a routing request, that is, two sensor nodes that want to communicate with each other; a set of paths connecting s and t (i.e., $s~t$ paths) are (node) disjoint if any two of them do not have any common nodes except s and t.

Compared to transmitting data through a single path, transmitting data through multiple disjoint paths can increase throughput, robustness, and load balance of routing in WSNs. Sending multiple data packets through multiple disjoint paths simultaneously will increase the throughput between s and t dramatically. Since link and node failures are very common in WSNs, messages may be easily lost while they are routed along a single path. We can increase reliability by sending messages redundantly through multiple disjoint paths. On the other hand, routing messages often through a fixed single path would deplete the energy of the nodes on the path quickly. By routing messages through several disjoint paths, alternately, the network can gain a better load balance. Moreover, in some applications, a sensitive message can be easily captured by eavesdropping nodes while it is routed through a single path. However, if we break the sensitive message into small pieces and send these pieces through multiple disjoint paths, capturing the entire message would be much more difficult.

This paper investigates the k-disjoint-paths (k-DP) problem: in a WSN, given two nodes s and t, a positive integer k, finding k disjoint $s~t$ paths, we expect that the k-DP problem can be solved with correctness guarantee; that is, an algorithm will output min $\{k,k^{*}\}$ disjoint $s~t$ paths. Here, we assume that there exist up to $k^{*}$ disjoint $s~t$ paths in the given network.

There are some works [1–12] considering the problem of finding multiple disjoint $s~t$ paths. To the best of our knowledge, all the existing algorithms which can solve the k-DP problems with correctness guarantee are centralized algorithms. These centralized algorithms need to build the topology of the whole network and update it with every topology change, so their communication costs are overwhelming for a large-scale WSN. On the other hand, all the existing algorithms finding disjoint paths in a distributed way (so they are much more efficient) cannot guarantee correctness. Therefore, we have two challenges to solve the k-DP problem in WSNs: to guarantee correctness and to maintain efficiency.

This paper proposes a distributed algorithm named distributedly finding disjoint paths (DFDP) to solve the k-DP problem with correctness guarantee. DFDP finds disjoint paths in a totally distributed way; that is, each node participates by exchanging short messages with its one-hop neighbors (hereinafter, “neighbor” means one-hop neighbor) and the exchange of messages does not rely on any predefined structures. DFDP is very energy-efficient and can adapt to topology changes with very limited extra cost. Both theoretical analysis and simulation results confirm the energy-efficiency of DFDP. As far as we know, DFDP is the first totally distributed algorithm which can solve the k-DP problem with correctness guarantee.

The rest of the paper is organized as follows. Some related works are introduced in Section 2. After giving some preliminary definitions in Section 3, we describe the proposed distributed algorithm DFDP in Section 4. The simulation results which confirm the proposed algorithm's efficiency are presented in Section 5. Finally, we conclude the whole paper in Section 6.

2. Related Works

Some works consider finding two $s~t$ paths in a network. Two algorithms are presented in [13, 14] to find a pair of disjoint paths from each node to a fixed destination. The work in [15] considers the problem of finding two $s~t$ paths with the following optimizing goals: (1) the two identified paths are as disjoint as possible; (2) the second path is as short as possible compared with the first path. The work in [16] gives a distributed algorithm to check if the network configuration contains at least two disjoint paths between all node pairs.

For general k, some distributed algorithms [1, 3–5, 11, 12] are proposed for finding k disjoint $s~t$ paths in a network. These algorithms have the same basic idea. They find paths one by one (most of them find the shortest $s~t$ path). Once a path is found, it is fixed and all its internal nodes are removed from the network so that they cannot participate in another path. To solve the k-DP problem, these algorithms cannot guarantee correctness. Suppose that, in a network as shown in Figure 1, the users want to find $k=\mathrm{2}$ disjoint $s~t$ paths, and we have already found the first path $P_{\mathrm{1}}=(s,a,b,c,t)$ as shown by the bold lines in Figure 1(a). If we fix $P_{\mathrm{1}}$ , we cannot find another $s~t$ path disjoint from it, and we have to report nonexistence of two disjoint $s~t$ paths. However, there do exist two disjoint $s~t$ paths as shown in Figure 1(d). In some cases, the above mentioned distributed approaches can be very wrong in answering the k-DP problem by underestimating the disjoint paths. Suppose that the topology graph of a given network is as shown in Figure 2, in which the dashed lines denote paths. If the users want to find $k=\mathrm{5}$ disjoint $s~t$ paths and we find the first path as shown by the bold lines in Figure 2(a) and then fix this path, this path will be the only one $s~t$ path we can find, even though five disjoint paths do exist as shown in Figure 2(b).

Figure 1

An example of finding disjoint $s~t$ paths ( $k=\mathrm{2}$ ).

Figure 2

An example of incorrect answer.

In [17], a distributed algorithm is proposed to find k disjoint paths from every node to a fixed destination in a network. The algorithm is based on a shortest-path tree rooted at the destination. The work in [18] gives a distributed algorithm to find multiple disjoint $s~t$ paths for geographic routing. These two algorithms cannot guarantee correctness either.

We propose a pseudodistributed algorithm in [19] to solve the k-DP problem in WSNs with correctness guarantee. The algorithm does not process in a totally distributed manner. Although it does not need to collect the topology information of the whole network, it still needs to collect some topology information from the network, so it is not very efficient. Furthermore, the algorithm is complicated and hard to be implemented by sensor nodes.

In [2, 6–10, 20], some centralized algorithms are given for finding k disjoint $s~t$ paths in graphs. In particular, the algorithms in [6, 9, 20] can find k disjoint $s~t$ paths with the minimum total length. All these centralized algorithms guarantee correctness. If we use these centralized algorithms to solve the k-DP problem in a WSN, we will have to collect every node's neighbor list to build the topology of the whole network. The communication cost of such operation is very high for a large-scale network. On the other hand, to guarantee correctness, we have to update the network's topology with each topology change such as link failing, link recovering, node dying, and new node joining in. Since these topology changes happen frequently in WSNs, we need to pay a lot of communication to make the topology we built up-to-date.

The works in [21–23] consider the problem of finding the maximum number of length-bounded disjoint $s~t$ paths in graphs. A length-bounded path is a path whose length is no more than a user-specified threshold l. In [22], this problem is proven to be NP-hard for $l\ge \mathrm{5}$ . In [21], this problem is further proven to be APX-complete for $l\ge \mathrm{5}$ , which means that there is no polynomial time approximation scheme (PTAS) for this problem. A heuristic algorithm for this problem is given in [23] without approximation bound.

For k multiple $s~t$ paths, we can give each path a sequence number. Each edge has k costs to be in the $1\text{st},\dots ,k\text{th}$ path. Such a network is called a multicost network. Some centralized algorithms are given in [24–26] to find k disjoint $s~t$ paths in multicost networks with the minimum total cost. The works in [27] consider the problem of reliable data transmission in underwater sensor networks. Its solution is based on coding techniques rather than finding disjoint paths. To transmit a series of data packets, by effective coding, its algorithm ensures that certain amount of the packets missing does not affect our access to the complete data.

So far, all the existing algorithms which can solve the k-DP problem with correctness guarantee are centralized algorithms. These centralized algorithms need to build the topology of the whole network and update it with every topology change, so they are not applicable in WSNs. On the other hand, all the existing distributed algorithms cannot guarantee correctness, although they are efficient.

3. Preliminaries

The given WSN can be expressed as an undirected graph $G=(V,E)$ , where $V=\{v\hspace{0.17em}|\hspace{0.17em}v$ is a sensor node} and $E=\{(u,v)\hspace{0.17em}|\hspace{0.17em}$ there is a wireless link between $u\in V$ and $v\in V\}$ . Here, we assume that all the links are bidirectional; that is, u can hear v if v can hear u. Hereinafter, we do not distinguish the terms “network” and “graph.”

A path P in G is a subgraph which can be expressed as a sequence of distinct nodes $(v_{\mathrm{1}},\dots ,v_m)$ , where $v_i\in V$ and $(v_i,v_{i+\mathrm{1}})\in E$ . We say path $P=(v_{\mathrm{1}},\dots ,v_m)$ is a $v_{\mathrm{1}}~v_m$ path. Although we model the given network as an undirected graph, we still emphasize the direction of a path by nodes’ order in its expression or the words “from” and “to.” Thus, the direction of path $P=(v_{\mathrm{1}},\dots ,v_{i-\mathrm{1}},v_i,v_{i+\mathrm{1}},\dots ,v_m)$ is from $v_{\mathrm{1}}$ to $v_m$ . $v_i$ 's previous hop in P is $v_{i-\mathrm{1}}$ and its next hop in P is $v_{i+\mathrm{1}}$ . The default direction of each $s~t$ path is from s to t. A reverse segment of a $s~t$ path is a segment of the path along the direction from t to s. In the example of Figure 1(a), $(c,b,a)$ is a reverse segment of $s~t$ path $P_{\mathrm{1}}$ .

Suppose that we have found n disjoint $s~t$ paths $P_{\mathrm{1}},\dots ,P_n$ in the given network. The nodes (edges) in the found paths are called occupied nodes (edges), and the other nodes (edges) are called unoccupied nodes (edges). Let v be an occupied node. We, respectively, use $prev(v)$ and $next(v)$ to denote v's previous hop and next hop in the found path that v belongs to. For example, in the network as shown in Figure 1(a), after finding $P_{\mathrm{1}}$ , b is an occupied node. $prev(b)=a$ and $next(b)=c$ .

After finding some disjoint $s~t$ paths, we convert the original graph G to another graph $G^{*}$ by replacing each path edge with a directed edge along the direction from t to s. In $G^{*}$ , each found path becomes a “river” flowing from t to s. In the example of Figure 1(a), after finding $P_{\mathrm{1}}$ , we convert G to $G^{*}$ as shown in Figure 1(b). Actually, $G^{*}$ is another way to interpret G. In the following, we do not distinguish the path in G and its corresponding path in $G^{*}$ .

We say that a path follows the crossing restriction if the path does not go through any occupied nodes except by going downstream on some river in $G^{*}$ for at least one hop (i.e., going through a reverse segment of some found path). A path following the crossing restriction is called a CR-path. After finding the first path $P_{\mathrm{1}}$ , let us examine some paths in the converted graph as shown in Figure 1(b). $Q_{\mathrm{1}}=(s,d,a,f)$ is not a CR-path because it goes through occupied node a by directly crossing the river. $Q_{\mathrm{2}}=(s,d,a,b,c,e)$ is not a CR-path because it goes through occupied nodes $a,b,c$ by going upstream on the river. $Q_{\mathrm{3}}=(s,d,e,c,b,a,f)$ is a CR-path because it goes through occupied nodes $c,b,a$ by going downstream on the river for segment $(c,b,a)$ .

A CR-path from s to t is an augmenting path. By adding an augmenting path $P_a$ to the found paths $P_{\mathrm{1}},\dots ,P_n$ , we can get $n+\mathrm{1}$ disjoint $s~t$ paths, where “add” means adding the edges that only belong to $P_a$ and removing the overlapping edges of $P_a$ and $P_{\mathrm{1}},\dots ,P_n$ . In the example of Figure 1(a), after finding the first path $P_{\mathrm{1}}=(s,a,b,c,t)$ , we can find an augmenting path $P_a=(s,d,e,c,b,a,f,g,t)$ as shown by bold lines in Figure 1(c). By adding $P_a$ to $P_{\mathrm{1}}$ , we can get two disjoint $s~t$ paths $P_{\mathrm{1}}^{\prime }=(s,d,e,c,t)$ and $P_{\mathrm{2}}^{\prime }=(s,a,f,g,t)$ as shown by bold lines in Figure 1(d).

Lemma 1.

After finding n disjoint $s~t$ paths, there exist more than n disjoint $s~t$ paths if and only if there exists an augmenting path [8].

Lemma 1 can be easily proven by transforming the problem of finding disjoint paths to a maximum flow problem. It means that we can find the maximum number of disjoint $s~t$ paths by searching for augmenting path repeatedly.

4. Distributed Algorithm DFDP

In the given network G, the users specify two nodes s and t and a positive integer k; the proposed algorithm DFDP will output $\min \{k,k^{*}\}$ disjoint $s~t$ paths. Here, we assume that there exist up to $k^{*}$ disjoint $s~t$ paths in the given network. DFDP is iteratively searching for augmenting path and adding it to the paths found before. There are two procedures in each iteration. Procedure 1 searches for an augmenting path $P_a$ . Procedure 2 adds $P_a$ to the paths found before to generate more disjoint paths. DFDP is given by Algorithm 1. We assume that each message contains the sender's ID. Each occupied node v knows $prev(v)$ and $next(v)$ .

Algorithm 1: Distributedly finding disjoint paths (DFDP).

  Input: two nodes s and t; a positive integer k

  Output:   $\min \{k,k^{\mathrm{*}}\}$ disjoint $s~t$ paths

(1)  repeat

(2)    Call Procedure 1;

(3)    if cannot find a path from s to t in $G^{\mathrm{*}}$   then

(4)       Output all the found paths and stop;

(5)    Call Procedure 2;

(6) until Find k disjoint $s~t$ paths

Procedure 1: Finding augmenting path.

   Input:  n disjoint $s~t$ paths $P_{\mathrm{1}},\dots ,P_n$

   Output: an augmenting path $P_a$

   /*   Each node   $v\ne s$   executes the following pseudo-codes while

       receiving a FIND-AP message (Let the sender beu); Start

       with  s  broadcasting a FIND-AP message.                */

(1)   case  v is an unoccupied node:

(2)     if UN_ $phcr(v)=$ NULL then

(3)       UN_ $phcr(v)\leftarrow u$ ;

(4)       Broadcast a FIND-AP message;

(5)   case  v is an occupied node and u is not $prev(v)$ or $next(v)$ :

(6)     if FHR_ $phcr(v)=$ NULL then

(7)       FHR_ $phcr(v)\leftarrow u$ ;

(8)       if   $v=t$   then

(9)         Start Procedure 2;

(10)     else

(11)       Send a FIND-AP message to $prev(v)$ ;

(12) case  v is an occupied node and $u=next(v)$ :

(13)   if OHR_ $phcr(v)=$ NULL then

(14)     OHR_ $phcr(v)\leftarrow u$ ;

(15)     Broadcast a FIND-AP message;

Procedure 2: Tracing augmenting path.

   Input:  n disjoint $s~t$ paths $P_{\mathrm{1}},\dots ,P_n$ ; an augmenting path $P_a$

   Output:   $n+\mathit{1}$ disjoint $s~t$ paths ${\mathrm{P}}_{\mathit{1}}^{\prime },\dots ,{\mathrm{P}}_{n+\mathit{1}}^{\prime }$

   /*   Each node   $v\ne t$   executes the following pseudo-codes while

           receiving a TRACE -AP message (Let the sender be u ); Start s

       with  t  sending  aTRACE-AP message  to FHR_ $phcr(t)$ .     */

(1)   case  v is an unoccupied node:

(2)     Mark itself as an occupied node;

(3)      $prev(v)\leftarrow$ UN_ $phcr(v)$ ;

(4)      $next(v)\leftarrow u$ ;

(5)     Send a TRACE-AP message to UN_ $phcr(v)$ ;

(6)   case  v is an occupied node and $u\ne prev(v)$ :

(7)     Still mark itself as an occupied node;

(8)      $next(v)\leftarrow u$ ;

(9)     Send a TRACE-AP message to OHR_ $phcr(v)$ ;

(10) case  v is an occupied node and $u=prev(v)$ and FHR_ $phcr(v)=$ NULL:

(11)   Mark itself as an unoccupied node;

(12)   Send a TRACE-AP message to OHR_ $phcr(v)$ ;

(13) case  v is an occupied node and $u=prev(v)$ and FHR_ $phcr(v)\ne$ NULL:

(14)   Still mark itself as an occupied node;

(15)    $prev(v)\leftarrow$ FHR_ $phcr(v)$ ;

(16)   Send a TRACE-AP message to FHR_ $phcr(v)$ ;

4.1. Finding Augmenting Path

Suppose that we have found n disjoint $s~t$ paths $P_{\mathrm{1}},\dots ,P_n$ in the first n iterations. In the ( $n+\mathrm{1}$ )th iteration, Procedure 1 searches for an augmenting path by finding a CR-path from s to each node in the network.

To make sure that the paths we found follow the crossing restriction, we divide the nodes in a CR-path into three categories: unoccupied node (UN), first hop of a reverse segment (FHR), and other hops in a reverse segment (OHR) of some found path. In the example of Figure 1(b), for CR-path $P_a=(s,d,e,c,b,a,f,g,t)$ , the nodes $\{d,e,f,g\}$ are UNs, node c is a FHR, and nodes $\{b,a\}$ are OHRs.

Each unoccupied node v maintains variable UN_ $phcr(v)$ to record v's previous hop in the CR-path we found from s to v. Each occupied node v maintains variables FHR_ $phcr(v)$ and OHR_ $phcr(v)$ . FHR_ $phcr(v)$ records v's previous hop in the CR-path we found from s to v with v as a FHR. OHR_ $phcr(v)$ records v's previous hop in the CR-path we found from s to v with v as an OHR.

Procedure 1 starts with s broadcasting a FIND-AP message. The other nodes find a CR-path from s to themselves by exchanging FIND-AP messages. Each FIND-AP message has an empty data field. Next, we discuss the following four cases.

Case 1.

Unoccupied node v receives a FIND-AP message (let the sender be u). It means that we find a CR-path (denoted by Q) from s to v and u is v's previous hop in Q. Since v is an unoccupied node, v is an UN in Q. To further extend Q as a CR-path, v's next hop in this path could be any neighbor of v. In this case, if UN_ $phcr(v)$ is not set yet, we set UN_ $phcr(v)$ to u and let v broadcast a FIND-AP message (lines 2–4 in Procedure 1).

Case 2.

Occupied node v receives a FIND-AP message from u and u is $prev(v)$ . It means that we find a path Q from s to v and u is v's previous hop in Q. Since u is $prev(v)$ , Q does not follow the crossing restriction. In this case, we let v discard the message.

Case 3.

Occupied node v receives a FIND-AP message from u and u is not $prev(v)$ or $next(v)$ . It means that we find a CR-path Q from s to v and u is v's previous hop in Q. Since u is not $prev(v)$ or $next(v)$ , v is a FHR in Q. To further extend Q as a CR-path, v's next hop in this path must be $prev(v)$ . In this case, if FHR_ $phcr(v)$ is not set yet, we set FHR_ $phcr(v)$ to u and let u send a FIND-AP message to $prev(v)$ (lines 6–11 in Procedure 1).

Case 4.

Occupied node v receives a FIND-AP message from u and u is $next(v)$ . It means that we find a CR-path Q from s to v and u is v's previous hop in Q. Since $u=next(v)$ , v is an OHR in Q. To further extend Q as a CR-path, v's next hop in this path could be any neighbor of v except $next(v)$ . In this Case, if OHR_ $phcr(v)$ is not set yet, we set OHR_ $phcr(v)$ to u and let u broadcast a FIND-AP message (lines 13–15 in Procedure 1). Although this message will be redundantly received by $next(v)$ , $next(v)$ will discard this message according to Case 2.

We assume that, at the beginning of each iteration, UN_ $phcr(v)=$ NULL for each unoccupied node and FHR_ $phcr(v)=$ OHR_ $phcr(v)=$ NULL for each occupied node. For example, UN_ $phcr(v)=$ NULL means that v (as an UN) has not received a FIND-AP message yet in the current iteration. It can be implemented by the following mechanism. Each node v maintains a variable $round(v)$ to denote the number of the current iteration. At the beginning of each new iteration, s updates the iteration number by adding 1 to the number of the last iteration. This number is included by every FIND-AP message so that each node can update its $round(v)$ . When v receives a FIND-AP message whose iteration number is larger than $round(v)$ , it sets UN_ $phcr(v)=$ NULL if v is an unoccupied node or FHR_ $phcr(v)=$ OHR_ $phcr(v)=$ NULL if v is an occupied node.

4.2. Tracing Augmenting Path

At first, let us describe the last hop in a reverse segment of some found path. In the example of Figure 1, after finding the augmenting path $P_a$ as shown in Figure 1(c), we say a is the last hop of the reverse segment $(c,b,a)$ . By adding $P_a$ to the paths found before, a should be an occupied node, $prev(a)$ does not change, and $next(a)$ changes to its next hop in $P_a$ , that is, f. In a CR-path, the last hop of a reverse segment is certainly an OHR.

Suppose that we find an augmenting path $P_a$ in Procedure 1. Procedure 2 adds $P_a$ to the paths found before. Starting from t, in sequence, each node in $P_a$ sends a TRACE-AP message (with empty data field) to its previous hop in $P_a$ . At first, t sends a TRACE-AP message to FHR_ $phcr(t)$ to start the procedure. Next, we discuss the following four cases.

Case 5.

Unoccupied node v receives a TRACE-AP message (let the sender be u). Then v is an UN in $P_a$ and its next hop in $P_a$ is u. Its previous hop in $P_a$ should be UN_ $phcr(v)$ . To add $P_a$ to the paths found before, v becomes an occupied node. $prev(v)$ should be UN_ $phcr(v)$ and $next(v)$ should be u. In this case, we let v execute lines 2–5 in Procedure 2.

Case 6.

Occupied node v receives a TRACE-AP message from u and u is not $prev(v)$ . Then v's next hop in $P_a$ is u. Since u is not $prev(v)$ , v is the last hop in a reverse segment of some found path. Of course, v is an OHR in $P_a$ . v's previous hop in $P_a$ should be OHR_ $phcr(v)$ . By adding $P_a$ to the paths found before, v is still an occupied node. $prev(v)$ does not change and $next(v)$ changes to u. In this case, we let v execute lines 7–9 in Procedure 2.

Case 7.

Occupied node v receives a TRACE-AP message from u and u is $prev(v)$ and FHR_ $phcr(v)=$ NULL. Then v's next hop in $P_a$ is u. Since u is $prev(v)$ , v is not the last hop in a reverse segment. Since FHR_ $phcr(v)$ is NULL, v is an OHR in $P_a$ and its previous hop in $P_a$ should be OHR_ $phcr(v)$ . By adding $P_a$ to the paths found before, v becomes an unoccupied node. In this case, we let v execute lines 11-12 in Procedure 2.

Case 8.

Occupied node v receives a TRACE-AP message from u and u is $prev(v)$ and FHR_ $phcr(v)\ne$ NULL. Then v's next hop in $P_a$ is u. Since u is $prev(v)$ , v is not the last hop in a reverse segment. Since FHR_ $phcr(v)$ is not NULL, v is a FHR in $P_a$ and its previous hop in $P_a$ should be FHR_ $phcr(v)$ . By adding $P_a$ to the paths found before, v is still an occupied node. $prev(v)$ changes to FHR_ $phcr(v)$ and $next(v)$ does not change. In this case, we let v execute lines 14–16 in Procedure 2.

4.3. An Example of DFDP's Execution

In the example of Figure 1, after finding the first $s~t$ path $P_{\mathrm{1}}$ as shown in Figure 1(a), the nodes execute DFDP as follows.

Procedure 1 starts with s broadcasting a FIND-AP message, which is received by a and d. a will discard the message according to Case 2.

Receiving the FIND-AP message from s, according to Case 1, d sets UN_ $phcr(d)=s$ and then broadcasts a FIND-AP message, which is received by a and e. Although the message will be also received by s, s will discard the message.

Receiving the FIND-AP message from d, according to Case 3, a sets FHR_ $phcr(a)=d$ and then sends a FIND-AP message to s (s will discard the message).

Receiving the FIND-AP message from d, according to Case 1, e sets UN_ $phcr(e)=d$ and then broadcasts a FIND-AP message, which is received by d and c. Since UN_ $phcr(d)$ is set yet, d discards the FIND-AP message from e.

Receiving the FIND-AP message from e, according to Case 3, c sets FHR_ $phcr(c)=e$ and then sends a FIND-AP message to b.

Receiving the FIND-AP message from c, according to Case 4, b sets OHR_ $phcr(b)=c$ and then broadcasts a FIND-AP message, which is received by a.

Receiving the FIND-AP message from b, according to Case 4, a sets OHR_ $phcr(a)=b$ and then broadcasts a FIND-AP message, which is received by s and f (s will discard the message).

In this way, f sets UN_ $phcr(f)=a$ and g sets UN_ $phcr(g)=f$ . Receiving FIND-AP message from g, t sets FHR_ $phcr(t)=g$ . Therefore, augmenting path $P_a=(s,d,e,c,b,a,f,g,t)$ is found as shown by bold lines in Figure 1(c).

Procedure 2 starts with t sending a TRACE-AP message to FHR_ $phcr(t)=g$ .

Receiving the TRACE-AP message from t, according to Case 5, g marks itself as an occupied node, sets $prev(g)=$ UN_ $phcr(g)=f$ and $next(g)=t$ , and then sends a TRACE-AP message to f.

Receiving the TRACE-AP message from g, according to Case 5, f marks itself as an occupied node, sets $prev(f)=$ UN_ $phcr(f)=a$ and $next(f)=g$ , and then sends a TRACE-AP message to a.

Receiving the TRACE-AP message from f, according to Case 6, a still marks itself as an occupied node, sets $next(a)=f$ ( $prev(a)$ is still s), and then sends a TRACE-AP message to OHR_ $phcr(a)=b$ .

Receiving the TRACE-AP message from a, according to Case 7, b marks itself as an unoccupied node and then sends a TRACE-AP message to OHR_ $phcr(b)=c$ .

Receiving the TRACE-AP message from b, according to Case 8, c still marks itself as an occupied node, sets $prev(c)=$ FHR_ $phcr(c)=e$ ( $next(c)$ is still t), and then sends a TRACE-AP message to e.

In this way, e marks itself as an occupied node and sets $prev(e)=d$ and $next(e)=c$ . d marks itself as an occupied node and sets $prev(d)=s$ and $next(d)=e$ . Now, we add $P_a$ to $P_{\mathrm{1}}$ and generate two disjoint $s~t$ paths $P_{\mathrm{1}}^{\prime }$ and $P_{\mathrm{2}}^{\prime }$ as shown in bold lines in Figure 1(d).

4.4. Correctness and Complexity

By the description of Sections 4.1 and 4.2, after finding n disjoint $s~t$ paths $P_{\mathrm{1}},\dots ,P_n$ , Procedure 1 will find an augmenting path if there exists one, and Procedure 2 is a correct way to add the augmenting path to $P_{\mathrm{1}},\dots ,P_n$ . By Lemma 1, we can get the following theorem.

Theorem 2.

DFDP will output min $\{k,k^{*}\}$ disjoint $s~t$ paths, where $k^{*}$ is the maximum number of disjoint $s~t$ paths in the given network.

Suppose that there are N nodes in the given network. In Procedure 1, each unoccupied node sends at most one FIND-AP message and each occupied node sends at most two FIND-AP messages. In Procedure 2, each node in $P_a$ sends one TRACE-AP message and the other nodes do not send any messages. Both FIND-AP message and TRACE-AP message have constant length (empty data field), so the communication complexity of DFDP is $O(N·\min \{k,k^{*}\})$ . The time complexity of DFDP is $O(N·\min \{k,k^{*}\})$ too.

4.5. Dealing with Topology Changes

Let us consider three types of topology changes.

Type 1.

During the processing of DFDP, the nodes or links in some found path fail. This type of topology changes will cause s not to receive the expected number of TRACE-AP messages (one plus the number of disjoint paths found in the last iteration) in the current iteration. Therefore, we can set a timer for the execution of each iteration. The timer is triggered by s at the beginning of each iteration. If the timer expires and s has not received the expected number of TRACE-AP messages, s knows that there is node or link failure in the path from which it has not received TRACE-AP message. Let the failed path be $P_i^{\prime }$ . Before going into the next iteration, DFDP frees the nodes in $P_i^{\prime }$ by tracing them from both s and t. With the topology changes, DFDP still guarantees correctness. The extra cost for DFDP to deal with this type of topology changes is tracing the failed path (which can be neglected compared to the total cost of the algorithm) and one more iteration of the algorithm (which is inevitable).

Type 2.

During the processing of DFDP, the topology beyond the found paths changes. Since each node participates in DFDP by communicating with its neighbors and the exchange of messages does not rely on any predefined structures, DFDP can handle this type of topology changes while guaranteeing correctness without any modification.

Type 3.

After the execution of DFDP ( $\min \{k,k^{*}\}$ paths have been used for routing), the nodes or links in some found path fail. After detecting the path failure, we can free the nodes in the failed path and execute one more iteration of DFDP to find one more disjoint path. The extra cost for DFDP to deal with this type of topology changes is also tracing the failed path and one more iteration of the algorithm.

On the contrary, to handle all the three types of topology changes and guarantee correctness, centralized algorithms have to collect the whole network's topology once again, which is a very expensive operation for WSN.

5. Simulation Results

We use a simulator written in C++ to evaluate the proposed algorithm. The simulator is a high level simulator which neglects the MAC layer. The effective transmitting radius of each sensor node is set to 50 m. Each packet has a 6-byte header containing the information of destination's ID (2 bytes), sender's ID (2 bytes), packet type (1 byte), and packet length (1 byte). The data field of each packet contains up to 50 bytes.

To simulate energy consumption, we set the parameters of sensor nodes according to TelosB motes [28]. The supply voltage is $\mathrm{3.0}$  V. When MCU is on and radio is on TX or RX mode, the node's current is 22 mA. The transmit bit rate is 250 kbps. Therefore, the energy consumption for the sender to send 1-bit data (or for the receiver to receive 1-bit data) successfully is $\mathrm{2.64}\times \mathrm{1}{\mathrm{0}}^{-\mathrm{7}}$  J. For the TelosB sensor node, the energy consumption to transmit one-bit data can be used for MCU to execute more than $\mathrm{400}$ instructions, so we neglect the energy consumption for computing.

We compare our algorithm DFDP with the centralized algorithm in [6] (denoted by CA), the pseudodistributed algorithm in [19] (denoted by EA), and the distributed algorithm in [5] (denoted by DA). CA collects the topology information of the whole network (each node's neighbor list) to the sink and finds disjoint paths at the sink. CA can find k disjoint $s~t$ paths with the minimum total length. CA is a good representation of the centralized algorithms in [2, 6–10]. All these centralized algorithms have to collect the topology information of the whole network, so they have the same communication cost. On the other hand, all of them guarantee correctness, so they find the same number of disjoint paths. DA finds paths iteratively. In each iteration, DA finds a $s~t$ path and removes the internal nodes of the path from the network. As we know, DA is the most efficient algorithm for finding disjoint paths with no other constraints. Note that DA cannot guarantee correctness; that is, DA may only find $n<k$ paths when there do exist k disjoint $s~t$ paths in the given network.

At first, let us compare the efficiency of four algorithms in theory. Suppose that there are N nodes and M edges in the network. Let d be the diameter of the network. The energy consumption of the algorithms is mainly determined by data communication. We already know that the communication complexity of DFDP is $O(N·\min \{k,k^{*}\})$ . CA collects the topology information of the whole network. Each node is $O(d)$ hops away from the sink on average, so the information of each edge is transmitted $O(d)$ hops to the sink on average and the communication complexity of CA is $O(dM)$ . EA has bad upper bound on communication complexity. In the worst case, EA has to collect the topology information of the whole network in each iteration, so its communication complexity is $O(dM·\min \{k,k^{*}\})$ . DA is the simplest algorithm to find disjoint path although it cannot guarantee correctness. In each iteration, each node sends one message with constant length to find a new path from s to t, so the communication complexity of DA is $O(N·\min \{k,k^{*}\})$ . We know that $k\ll d$ in most applications. In the aspect of communication complexity, DFDP and DA are much better than CA and EA. Although with the same communication complexity compared with DA, DFDP can guarantee correctness, whereas DA cannot.

We evaluate the performances of the algorithms at four aspects: (1) path number, (2) average path length, (3) energy-efficiency, and (4) load balance. “Path number” is the number of disjoint $s~t$ paths found by the algorithms. “Average path length” represents the quality of the disjoint paths. We use “average energy/path number” to measure algorithms’ energy-efficiency, where “average energy” is the average energy consumption of each node in the network. Load balance is measured by “max energy/path number,” where “max energy” is the maximum energy consumption of any node in the network.

There are two groups of simulations. In Group 1, 2500 sensor nodes are randomly deployed in a 1500 m × 1500 m area. In Group 2, 2500 sensor nodes are deployed as a $\mathrm{50}\times \mathrm{50}$ grid and each node dies or sleeps with $\mathrm{25}\%$ probability. As a result, 1859 nodes are left as alive nodes in the grid. The comparison of the algorithms is conducted for different k, that is, the number of the paths the users want to find. To get each result, we performed $\mathrm{10}$ simulations with different $(s,t)$ pairs and took their average value. The $(s,t)$ pairs are generated randomly.

The comparison results for Group 1 are given in Figure 3. The path number of the four algorithms is given in Figure 3(a). With the growth of k, all the four algorithms find more disjoint paths, until they reach their “limits.” DA finds no more disjoint paths when $k\ge \mathrm{7}$ . CA, EA, and DFDP find no more disjoint paths when $k\ge \mathrm{10}$ . Since CA, EA, and DFDP all guarantee correctness, they always find the same number of disjoint paths. When $k\le \mathrm{3}$ , all the four algorithms can find k disjoint paths. When $k\ge \mathrm{4}$ , compared with DA, the other three algorithms find more disjoint paths. CA, EA, and DFDP can find the maximum number of the disjoint paths in the network, whereas DA cannot. For $k=\mathrm{10}$ , compared with DA, the other three algorithms find $\mathrm{20.3}\%$ more disjoint paths.

Figure 3

Simulation results for Group 1 (2500 nodes are randomly deployed in a 1500 m × 1500 m area).

Next, we want to compare the average path length of the four algorithms. For different $(s,t)$ pairs, the difference of paths’ average lengths may be very large. To compare fairly, for each $(s,t)$ pair, we set the value of CA to 1 and normalize the values of the other three algorithms. The average path length of the four algorithms for Group 1 is given in Figure 3(b). The centralized algorithm (CA) always finds disjoint paths with the minimum total length. EA and DFDP almost have the same performance as CA in this aspect. In all cases, the average path length of DFDP is at most $\mathrm{3}\%$ higher than the one of CA. When $k=\mathrm{10}$ , the average path length of DA is even less than the one of CA. This is because DA finds less disjoint paths and all the algorithms have the trends to find shorter path first.

The energy-efficiency of the four algorithms for Group 1 is given in Figure 3(c). No matter what value k is, CA collects the topology information of the whole network, so the energy cost of CA does not change with k. With CA finding more disjoint paths, it is more energy-efficient, until it finds the maximum number of disjoint paths. EA finds paths iteratively and collects an abstract of the network topology in each iteration. With finding more disjoint paths, EA needs to collect more and more complicated topology information and becomes less and less energy-efficient. When $k>\mathrm{7}$ , EA is even worse than CA in this aspect. DFDP and DA also find paths iteratively and their energy cost for each iteration is steady. DFDP and DA almost have the same performance in this aspect, and both of them are much more energy-efficient than CA and EA.

The load balance of the four algorithms for Group 1 is given in Figure 3(d). Note that the value of the y-axis increases logarithmically. Since CA collects the topology information of the whole network, the nodes near the sink need to send and receive a large amount of data, so CA is two orders of magnitude worse than the other three algorithms in this aspect. Although EA is much better than CA, it is still a “collecting” algorithm, so it is not as good as DFDP and DA in terms of load balance. By finding more disjoint paths, sometimes DFDP even gains a better load balance compared with the simplest distributed algorithm (DA).

The specific simulation results for Group 1 when $k=\mathrm{10}$ are shown in Table 1. “Average Comm. Bytes” is the average number of bytes sent and received by each node in the network. “Max Comm. Bytes” is the maximum number of bytes sent and received by any node in the network.

Table 1

The simulation details for Group 1 when $k=\mathrm{10}$ .

Performance	Algorithms
	CA	EA	DFDP	DA
Path number	7.1	7.1	7.1	5.9
Average path length	1	1.03	1.03	0.99
Average Comm. Bytes	845	1023	353	291
Max Comm. Bytes	58495	1616	814	683
Average energy ( $\times \mathrm{1}{\mathrm{0}}^{-\mathrm{7}}$  J)	17842	21605	7462	6136
Max energy ( $\times \mathrm{1}{\mathrm{0}}^{-\mathrm{7}}$  J)	1235407	34123	17196	14431

The comparison results for Group 2 are given in Figure 4. The path number of the four algorithms is given in Figure 4(a). With the growth of k, all the four algorithms find more disjoint paths. DA reaches its “limit” when $k=\mathrm{3}$ , whereas CA, EA, and DFDP reach their “limits” when $k=\mathrm{4}$ . Since CA, EA, and DFDP all guarantee correctness, they always find the same number of disjoint paths. When $k=\mathrm{4}$ , compared with DA, the other three algorithms find $\mathrm{47.8}\%$ more disjoint paths.

Figure 4

Simulation results for Group 2 (1859 nodes are randomly deployed in a $\mathrm{50}\times \mathrm{50}$ grid).

The average path length of the four algorithms for Group 2 is given in Figure 4(b). The centralized algorithm (CA) always finds disjoint paths with the minimum total length. Note that CA, EA, and DFDP find the same number of disjoint paths. No matter what the value of k is, the average path length of DFDP is at most $\mathrm{2}\%$ higher than the one of CA.

The “average energy/path number” of the four algorithms for Group 2 is given in Figure 4(c). In the aspect of energy-efficiency, DFDP and DA are much better than CA and EA. DFDP and DA almost have the same energy-efficiency, but DFDP finds more disjoint paths.

The “max energy/path number” of the four algorithms for Group 2 is given in Figure 4(d). In the aspect of load balance, CA is two orders of magnitude worse than the other three algorithms. DA and DFDP almost have the same performances and both of them are significantly better than EA. The specific simulation for Group 2 when $k=\mathrm{4}$ is shown in Table 2.

Table 2

The simulation details for Group 2 when $k=\mathrm{4}$ .

Performance	Algorithms
	CA	EA	DFDP	DA
Path number	3.4	3.4	3.4	2.3
Average path length	1	1.04	1.02	0.84
Average Comm. Bytes	348	170	56	40
Max Comm. Bytes	14792	568	249	172
Average energy ( $\times \mathrm{1}{\mathrm{0}}^{-\mathrm{7}}$  J)	7351	3590	1183	844
Max energy ( $\times \mathrm{1}{\mathrm{0}}^{-\mathrm{7}}$  J)	312416	11995	5263	3629

Let us summarize the simulation results for Group 1 and Group 2. Compared with DA, DFDP finds significantly more disjoint paths. In the aspect of energy-efficiency and load balance, DFDP is almost the same as DA. CA, EA, and DFDP find the same number of disjoint paths with almost the same length. However, in the aspect of energy-efficiency and load balance, DFDP is much better than CA and EA.

6. Conclusion

This paper proposes an efficient distributed algorithm DFDP to find k disjoint paths connecting two given nodes s and t in a WSN. Unlike the existing distributed algorithms for this problem, DFDP guarantees correctness. Compared to the existing centralized algorithms which also guarantee correctness, DFDP is much more efficient. Compared to the state-of-the-art distributed algorithms for the same problem, DFDP has the same energy-efficiency and load balance, with the important advantage that DFDP guarantees a correct answer, whereas the compared algorithms do not. In conclusion, DFDP is correct and efficient to find disjoint paths between two nodes in a WSN.