Gradient Based Multipath Reliable Transmission Strategy with Fault Tolerance for Wireless Sensor Networks

Abstract

Fault tolerance and reliable transmission are hot issues in wireless sensor networks. For the problems that the fault of nodes or links will affect the transmission stability and reliability of the network, a gradient based multipath reliable transmission strategy with fault tolerance is presented for wireless sensor networks. Firstly nonuniform clustering topology is established in nonequal clustering probability based on twice K-means algorithm. Then it calculates the comprehensive measurements (CM) of cluster heads by the quality evaluation function and establishes the contour lines. Finally gradient based multiple disjoint transmission paths are established by the mechanisms of load balance and linear erasure coding. It also establishes the transmission mathematical model to analyze the performance of the network. Simulation shows that this strategy has good performance of fault tolerance. It improves the transmission reliability of the network and energy efficiency.

1. Introduction

The reliability of data transmission is an important index to evaluate the performance of wireless sensor networks (WSNs). The stable topology routing is established to realize the effective and reliable data transmission giving the consideration to the balance of energy consumption, low transmission delay, and so forth [1]. However, owing to the characteristics of the network itself, such as ad hoc network with no center, dynamic topology changes, source restriction of the computing, transmission, and energy consumption, as well as the unpredictability of the working scenario especially brought by vibration and electromagnetic interference, failures of nodes or links often occurred which lead to data loss or retransmission. This seriously affects the data receiving rate, accuracy rate, and the average transmission delay. Finally it lowers the transmission stability and reliability, weakens the reservation function, and brings great challenges to the existing network technologies [2].

A network with good performance has characteristics of reliable data transmission, efficient energy consumption, and low transmission delay. When the malfunction occurs, the network can adaptively adopt the reasonable fault-tolerant control scheme to deal with the failure and continue to provide highly credible computational service. So fault tolerance becomes the key technology to improve the transmission stability and reliability of the network. Now it attracts much attention and becomes one of the hot issues in wireless sensor networks [3].

The reliable transmission strategy with fault tolerance mainly contains multipath transmission routing, network coding, packets retransmission, and so forth [1, 4–11]. Unquestionably, the network has better performance when it adopts the optimal combination of some methods or combined control optimization with other layers [4, 11]. Therefore, the core of reliable transmission with fault tolerance is to establish an effective topology and data coding based multipath transmission mechanism. Multipath routing transmission technology with fault tolerance is to establish multiple transmission paths between the source node and the destination node to improve the load balance and transmission bandwidth. Network coding based redundancy transmission mechanism is to transmit the coded packets along multiple paths and to decode and to reconstruct the certain number of coded packets received at the destination node into the source data. Network coding should be combined with multipath transmission and load balance mechanism. Therefore, it is essential to establish the multipath data coding transmission based on an effective topology.

This paper mainly studies the issues that the node failure or link quality affects the stability and reliability of data transmission in network layer and presents a gradient based reliable multipath transmission strategy with fault tolerance. It mainly includes the establishment of the network topology by twice K-means nonuniform clustering algorithm and the establishment of gradient based multipath transmission mechanism according to nodes’ CM (comprehensive measurement). By adopting the mechanism of erasure coding and load balance, it decodes the received packets and reconstructs them into source data at the destination node to improve the reliable transmission and fault tolerance.

Our work makes the following new contributions. (1) Twice K-means algorithm is adopted to do the nonuniform cluster splitting to establish and optimize the hierarchical clustering topology. By this way, it can realize the load balance, improve the efficiency of energy consumption, and avoid the hot issue. (2) Contour lines are established according to the nodes’ CM to establish the gradient based multiple disjoint transmission paths between the adjacent hierarchical nodes. Combining with mechanism of erasure coding and load balance, complexity of the establishment of multipath routing is reduced and the performance of fault tolerance is improved. (3) Load balance mechanism based mathematical model is established to do the theoretical analysis on the performance of the network. Simulations are done to evaluate the performance of reliability and fault tolerance.

The rest of this paper is organized as follows: related work is in Section 2. Section 3 presents the network topology by twice K-means nonuniform clustering algorithm. Section 4 presents the establishment of multipath gradient routing according to nodes’ CM; furthermore, it establishes the mathematical model and does the theory analysis and proof on the network's performance. Section 5 is the simulations and analysis. The conclusion is in Section 6.

2. Related Works

2.1. Coding Based Multipath Transmission Technology

Coding based multipath transmission technology for fault tolerance is to transmit the encoding packets along multiple paths established between the source node and the destination node. Certain amount of encoded fragments received at the destination node is reconstructed into the source data. By the mechanism of redundant routing and network coding, load balance and transmission bandwidth are improved to realize fault tolerance and transmission reliability.

Energy efficient reliable multipath routing using network coding (NC-EERMR) [4] is to establish the multipath routing in a distributed way through multiple hops. Sub-Branch Multi-Path Routing Protocol (SMRP) [5], based on Secure and Efficient Intrusion-Fault Tolerant Protocol (SEIF) which is DM model, improves the fault tolerance and credibility by the mechanism of multiple routing selection in the distributed authentication way. Self-selecting reliable path routing (SRP) [6] which is based on SSR (self-selecting routing) and SHR (self-healing routing) has the transmission fault tolerance by establishing the multiple paths. Mixed multipath mechanism H-SPREAD [7] is based on the hybrid multipath data acquisition mechanism and adopts the key sharing and backup path for any node to improve security and reliability of data transmission. Network coding based multipath reliable transmission route (NC-RMR) [1] adopts BM mode to establish the logical backup for any path. DD (directed diffusion) [12] establishes the multipath transmission mode to deal with the node failure and topology changes through three phases: flooding the interests, establishing the gradient, and dynamically optimizing transmission routing. DD based multipath routing algorithm [8] strengthens the multiple paths with high quality and low transmission delay and [9] presents the DM based distributed multipath routing algorithm with high energy efficiency and scalable characteristic which can adjust data flow by the load balance mechanism. VR (distance vector routing) [10] that combines the coding algorithm and multipath transmission mechanism establishes paths by the light-weight flooding only when needing transmitting the data [11]. However, it is difficult to obtain the accurate amount of the paths.

2.2. Gradient Based Transmission Routing

Nodes in the network are divided into different hierarchies according to gradient values defined by the distance or hops to the destination node, nodes’ energy level, and transmission delay so as to establish the gradient based transmission routing by a certain strategy.

The energy balance nonuniform clustering gradient based routing (EBCAG) [13] transmits the data packets along the gradient descent direction to the destination node according to the gradient value decided by the minimum hops between the source node and the destination node. GBR (gradient-based routing) [14], which contains competitive algorithm GBR-C and adaptive GBR-C, is to establish two forward hops to minimize the probability of data retransmission. In gradient broadcast algorithm (U-GRAB) [15], the transmission decision depends on the node's practical degree and it preferentially selects the noncrowded channel and energy-efficient nodes for transmission. GBR (gradient-based routing) [16], based on DD protocol, transmits the data along the path with maximum gradient value determined by minimal hop to the destination node. FGS (fine-grain gradient sinking) [17, 18] introduces average weighted mechanism based on the HGS (hop gradient sinking) model and converts hop count information into fine gradient information as the reference to establish data transmission strategy. Data aggregating ring (DAR) [19] classifies the nodes by the hop counts, the data packets are not always transmitted along the gradient direction to the destination node through multiple hops, and the data with other gradient values can be directly forwarded to the destination node through only one hop by the load balance mechanism. In [20], the nodes are distributed in the different hierarchical circle areas based on the nodes’ nonuniform distribution strategy, it establishes the shortest transmission path also among different hierarchical circle areas. Gradient based routing MR2-GRADE [21] presents the greedy algorithm based GRADE-GF and lighted flooding algorithm based GRADE-RF. Reference [22] studies the gradient model based network's upper and lower bounds of the survival time. Gradient broadcast (GRAB) [23] allows nodes with low gradient values to forward data simultaneously to form the multipath routing. However, it lowers the transmission reliability owing to the conflicts of twice forwarding.

3. Topology Establishment for Multipath Transmission

3.1. Network Topology

For large scale of wireless sensor networks, multipath reliable transmission mechanism which is based on nonuniform clustering topology by twice K-means clustering algorithm has good performance of fault tolerance. The nodes are uniformly distributed in the rectangular area and the destination node is located on the right. Nodes closer to the destination node are clustered by larger probability, so smaller scale and more quantity of clusters are formed near the destination node. The clustering topology is as shown in Figure 1.

Figure 1

Clustering topology.

3.2. Twice K-Means Based Nonuniform Clustering Algorithm

k objects are randomly selected as the initial clustering center and the clusters which the object belongs to are adjusted after many rounds iterations by the principle of minimum distance. Clustering topology is finally established until the clustering results are no longer changing. K-means based iterations through random selection of cluster heads can establish the optimized clustering topology with good performance of compactness within clusters and alienation among clusters. Hops that is from a cluster head to the destination node are calculated by the interest packets flooded among cluster heads. Cluster heads are divided into n hierarchical areas; clusters are split in larger clustering probability when n is smaller. Through twice K-means clustering optimization, smaller scale and more quantity of clusters are formed which are nearer to the destination node. This clustering topology can avoid the hot issue in the energy consumption. The algorithm is described as follows.

Step 1.

Set the parameters $[p,e_{\text{ini}}(i),{\epsilon }_{\text{amp}},E_{\text{fuse}},E_{\text{elec}},E_{\text{tx}},E_{\text{rx}}]$ and randomly select k nodes as the initial clustering centers $c_{\mathrm{1}},c_{\mathrm{2}},\dots ,c_k$ by the probability $p=0.2$ , $p=k/N$ ; it is determined by the scale of network and quantity of cluster heads.

Step 2.

Divide each object to the nearest clusters with the center $c_i(\mathrm{1,2},\dots ,k)$ within the coverage power by the principle of minimum distance. Nodes assigned to the same center belong to the same cluster. Therefore, k clusters are formed.

Step 3.

Calculate new center $c_i^{\prime }$ of the clusters; that is, $V_{c_i^{\prime }}=(\mathrm{1}/N_i){\sum }_{X\in C_i}X$ , where $N_i$ is the number of nodes in the ith cluster $C_i$ . X means the distance from one object to the center $c_i^{\prime }$ and new center $c_i^{\prime }$ is one of the nodes in the cluster with $\min V_{c_i^{\prime }}$ .

Step 4.

Judge $c_i^{\prime }=c_i?$ If unequal, turn to Step 2 until $c_i^{\prime }=c_i$ , which means the centers of the clusters no longer change.

Step 5.

Flood the interest packets among cluster heads and learn minimum hops from each cluster head to the destination node.

Step 6.

Judge the number of nodes in each subcluster $m\ge \lfloor \mathrm{1}/p\rfloor /(n^{\prime }-(j-\mathrm{1}))$ in the nth area, where $n=(j-\mathrm{1},j)(\text{Hops}/n^{\prime }),\hspace{0.17em}j=\mathrm{1,2},\dots ,n^{\prime }$ . $n^{\prime }$ is variant of hierarchy, Hops means the hops from the destination node to the source node. If valid, the existing clusters will split into $(n^{\prime }-(j-\mathrm{1}))$ subclusters in the nth area.

Step 7.

Randomly select the cluster heads in the nth hierarchical area and repeat Steps 2–4 to do the twice K-means based cluster splitting until the clustering optimization for all nodes in n hierarchical areas has been finished.

3.3. Characteristics of Twice K-Means Nonuniform Clustering Algorithm

K-means based nonuniform clustering method selects the cluster heads by the probability p which is determined by the scale of the network and quantity of cluster heads. Twice K-means based clustering algorithm is applied in the whole network. n hierarchical areas are divided according to the hops from the cluster heads to the destination node. Existing clusters will be split into a number of subclusters by certain rules. K-means clustering algorithm is used for locally twice optimization in each area so that the nonhierarchical topology is formed. It has good characteristics as follows. (1) The complexity of K-means based nonuniform clustering algorithm is $\text{O}(k(N-k{)}^{\mathrm{2}})$ , where k means the number of clusters and N means the number of nodes. Complexity of twice K-means nonuniform clustering algorithm is $\text{O}(k^{\prime }(N-k^{\prime }{)}^{\mathrm{2}})$ , where $k<k^{\prime }<N$ . The algorithm is with low computational complexity to establish the nonuniform topology owning to the simple mathematical iteration so that it can avoid the hot issues in the energy consumption. (2) It avoids not only flooding the interest packets among all the nodes in the network but also using the physical address for the hierarchical division. Interest packets are flooded among the cluster heads and the hierarchical clusters division is carried out according to the hops. Locally twice K-means optimization in the limited area of the networks is done so that it can lower the energy consumption.

3.4. Realization of Twice K-Means Nonuniform Clustering Algorithm

The following pseudocode shows the detailed process of realization of twice K-means nonuniform clustering algorithm. It contains two parts: k-means clustering algorithm and clusters’ splitting. First k-means clustering algorithm is carried out among the initial clusters until the optimum cluster topology is established. Then clusters’ splitting is done by the setting threshold values and finally k-means clustering algorithm is carried out again to optimize the clustering. The pseudocode is as Pseudocode 1.

Pseudocode 1

(1) set the parameters

(2) randomly select k nodes by the probability p as the initial clusters

(3) for $i=1$  :  $n-k$

(4) for $j=1$  : k

(5) calculate the $dist(i,j)$

(6) if min $\left\{dist\left(i,j\right)\right\}$

(7) if $dist(i,j)\le R_i$

(8) node i→cluster j

(9) m++

(10) endif

(11) endif

(12) endfor

(13) endfor

(14) for $i1=1$  : k

(15) for $j1=1$  : m

(16) calculate $c_i^{\prime }$ by $V_{c_i^{\prime }}=\left(\mathrm{1}/N_i\right){{\displaystyle \sum }}_{X\in C_i}^{}X$

(17) if $c_i^{\prime }=c_i$

(18)  $c_i^{\prime }$ →new cluster

(19) endfor

(20) endfor

(21) interests flooding

(22) get the minimum hops to destination node

(23) for $n2=1$  : n

(24) for $q=1$  : k

(25) if $m\ge \lfloor \mathrm{1}/p\rfloor /\left(n^{\prime }-\left(j-\mathrm{1}\right)\right)$

(26) cluster q→ $\left(n^{\prime }-\left(j-\mathrm{1}\right)\right)$ clusters

(27) endif

(28) endfor

(29) recycle Step  (2) to  (18)

(30) endfor

4. Establishment of Gradient Based Multipath Transmission Routing

4.1. Calculate Nodes’ CM and Establish the Contour Lines

4.1.1. Calculate Cluster Heads’ CM

Packets will be lost or retransmitted due to path's poor quality. This will cause more local energy consumption and serious congestion. Path quality has direct influence on the reliability of packets forwarding. The residual energy determines the survival time of the network. Therefore, the way only using hops as a criterion to evaluate the quality of routing has failed to meet the requirements of the network service quality. By selecting the hops to the destination node, residual energy and transmission delay to comprehensively evaluate the nodes’ quality, the preferred cluster heads are selected to establish the optimal transmission path. This has great significance to improve the transmission reliability.

Definition 1.

Comprehensive measurement (CM) of a node is defined to set the appropriate weighting factor to calculate CM for each cluster head according to parameters of hops to the destination nodes, residual energy, and transmission delay. The node's comprehensive measurement function is defined as

$$\begin{array}{cc}& \text{CM}\left(i\right)=w_{\mathrm{1}}\frac{E\left(i\right)}{E_{\text{ini}}\left(i\right)}+w_{\mathrm{2}}\frac{\text{Hop}\left(i\right)}{\text{Ho}{\text{p}}_{\max }\left(i\right)}+w_{\mathrm{3}}\frac{\text{delay}\left(i\right)}{\text{dela}{\text{y}}_{\text{path}}\left(i\right)},\end{array}$$

(1)

where $w_{\mathrm{1}}+w_{\mathrm{2}}+w_{\mathrm{3}}=\mathrm{1}$ , $E_{\text{ini}}(i)$ represents the initial energy of the cluster that cluster head i belongs to, $\text{Ho}{\text{p}}_{\max }(i)$ represents the maximum hops of the path that cluster head i is on, and $\text{dela}{\text{y}}_{\text{path}}(i)$ represents the transmission delay of the path that cluster head i is on.

4.1.2. CM Based Contour Line among Clustering Heads

Definition 2.

All nodes’ CM values are hierarchically divided, the nodes with equal hierarchy values have similar CM values, and the connection line among the cluster heads with the same hierarchy value is defined as CM based contour line.

Each cluster head's CM is calculated by formula (1). Nodes are divided into n hierarchies $\{(k-\mathrm{1})/n,k/n\}\text{CM},\hspace{0.17em}k=\mathrm{1,2},\dots ,n$ . When $\text{C}{\text{M}}_{\text{node}}\in \{(k-\mathrm{1})/n,k/n\}\text{CM}$ , the node's gradient $G_{\text{node}}=k$ . CM based contour lines on cluster heads are shown as in Figure 2.

Figure 2

Contour lines on cluster heads.

4.2. Establishment of Multipath Gradient Routing

4.2.1. Multipath Gradient Routing

Gradient based multipath routing is an on-demand distributed routing presented to solve the issue of blind broadcasting, directed transmission, and quick establishment of multiple paths. Gradient value is used to restrict the direction of interest packets’ broadcasting and data transmission. When data are being needed to transmit, n global optimal paths are distributed established from the source node to the destination node according to the cluster heads’ CM. This strategy mainly includes the phases of topology establishment, nodes’ CM calculation, multipath routing establishment, routing maintenance, and so forth.

When the source node has packets to be transmitted, it firstly reports to its cluster head. The cluster head selects the node with the minimum distance on the next contour lines along the gradient direction as the next hop within the transmission power coverage to establish the first optimal transmission path. Then the cluster head selects one node as the next hop which is with the minimum distance on the next contour lines and within the transmission power coverage but not belonging to the established transmission paths to establish the suboptimal path. Finally multiple paths are established from the source node to the destination node as shown in Figure 3.

Figure 3

Gradient based multipath routing.

The detailed steps are as follows.

Step 1.

To initialize the parameters [ $w_{\mathrm{1}},w_{\mathrm{2}},w_{\mathrm{3}},\hspace{0.17em}p,{\epsilon }_{\text{amp}},E_{\text{fuse}},E_{\text{elec}},E_{\text{tx}},E_{\text{rx}}\hspace{0.17em}\delta ,e_{\text{ini}}(i),\Delta t,S_p$ ], the source node reports to its cluster head when it has the packets needing to be transmitted to the destination node.

Step 2.

To establish the first optimal path, the cluster head selects the nearest cluster head on the contour line with $G^{\prime }=G-\mathrm{1}$ within its transmission power coverage as the next hop according to its CM and G; namely, $\{\min \mathrm{dist}(i,j),\mathrm{dist}(i,j)\le R_i\}$ , $i,j$ , respectively, represent neighbor hierarchical cluster heads on the established path and $R_i$ represents the transmission power coverage of cluster head i. So the first gradient optimal path to the destination node is established.

Step 3.

To establish the second suboptimal path, the cluster head selects the second nearest nodes on the contour line with $G^{\prime }=G-\mathrm{1}$ but not on the established paths also within its transmission power coverage as the next hop to establish the second suboptimal gradient multihop path to the destination node.

Step 4.

After establishing the necessary paths, the destination node will forward the paths’ information back to the source node along the established multiple paths and it includes nodes’ energy information, transmission delay, success rate of the data transmission, and so forth. Source node then encodes the packet by the linear erasure coding algorithm and allocates the coded fragments into multiple paths by load balance mechanism.

Step 5.

In the time interval $t_{\text{network}}^{\prime }=\min \{\max \{(t(M+K)q_i^{\prime }/\Omega ){\sum }_{k=\mathrm{1}}^{n_i-\mathrm{1}}({\prod }_{j=\mathrm{1}}^{k-\mathrm{1}}{q}_i^{j-\mathrm{1}})\},t_{\text{set}}\}$ , the destination node decodes the received encoded fragments and reconstructs them into the source packet, where $t_{\text{set}}$ is the setting time parameter, $M+K$ is quantity of coded fragments at the destination node, t is the time interval of unit packet Ω required at each node, and $q_i^{\prime }$ is the normalized value of success rate of data transmission q on each link.

4.2.2. Maintenance of the Multipath Gradient Routing

After the establishment of multiple transmission paths and packets transmission, the node will go into a dormant state and wait for the next event trigger by the MAC layer protocol control. Maintenance of the multipath gradient routing includes two main parts: error reporting and routing repair. Routing error report means that the node sends the error report to the source node and requests a repair when a fault node or invalid link is detected in the routing. If the former node of the fault node or link decides to make a repair, it will launch the routing repair process. The node firstly stores the received packets and then selects the node on the next contour line and not belonging to other routing as the next hop to reestablish the routing. Furthermore, it sends the routing requests message to the destination node. The repair work finished when the destination node receives and replies to the request. Finally, the packets in the cache queue are forwarded along this newly established path.

Multipath gradient routing has the performance of fault tolerance. For example, $(n_i,n_j)$ in $\text{pat}{\text{h}}_{\mathrm{3}}$ is with fault in Figure 3, so the node $n_i$ selects the near node on the contour line that does not belong to the other path as the next hop instead of the existing fault node or link, or it applies redundant transmission by network coding mechanism to realize the fault tolerance and transmission reliability.

4.2.3. Characteristics of the Gradient Multipath Routing

( 1) High Transmission Reliability and Fault Tolerance. Multipath gradient routing, established in a dynamic distributed way, forwards the coded fragments along multiple paths so that it can avoid data loss caused by failures of a node or link. Decoding transmission mechanism can tolerate a certain amount of data loss. By allocating more fragments to the optimal path for transmission, load balance mechanism can reduce packet loss rate and improve the receiving rate of coded fragments at the destination node and the success rate of the source packet transmission.

(2) Load Balance and High Efficiency of Energy Consumption. Parameters of node's hops, energy consumption, and transmission delay are comprehensively considered when establishing the multipath gradient routing. All nodes in a cluster are repeatedly selected as the cluster head when the energy consumption reaches a certain threshold. The coded fragments are to be allocated to multiple disjoint paths. When the data is finished transmitting to the destination node along multipaths or the residual energy of any cluster head reaches the set threshold, the network will calculate the nodes’ CM and establish the contour lines and the multiple transmission paths to the destination again. With this optimization it can prolong the network lifetime.

(3) Low Complexity and Low Transmission Delay. The multipath gradient routing with load balance mechanism has lower computational complexity. Each node only stores neighbor nodes’ CM and it can establish multipath routing in a distributed way, not needing to store the global information of the nodes or paths. Computational complexity mainly reflects in establishing the topology and multipath gradient routing. The computation of K-means based nonuniform hierarchical clustering routing is lower owing to its establishment according to CM in a distributed way. Multipath routing with load balance mechanism can lower the transmission delay. During the time $t_{\text{network}}^{\prime }=\min \{\max \{(t(M+K)q_i^{\prime }/\Omega ){\sum }_{k=\mathrm{1}}^{n_i-\mathrm{1}}({\prod }_{j=\mathrm{1}}^{k-\mathrm{1}}{q}_i^{j-\mathrm{1}})\},t_{\text{set}}\}$ , it can complete once the data is transmitted. Characteristics of transmission delay will be analyzed in the next segment.

4.2.4. Realization of Multipath Gradient Routing Algorithm

The following pseudocode shows the establishment process of multipath gradient routing. It is based on the clustering topology. In the algorithm, it firstly calculates the CM of cluster head and establishes the contour lines. Then it establishes multiple gradient transmission paths according to the multipath establishing rules. After this, it sends the interest packets, evaluates the quality of paths, and establishes the maintenance mechanism of multipath gradient routing. The pseudocode is as Pseudocode 2.

Pseudocode 2

(1) set the parameters

(2) for $i=1$  : n_clusternodes

(3) calculate CM by the formula (1)

(4) calculate $G_{\text{node}}=k$ if $\text{C}{\text{M}}_{\text{node}}\in \left\{\left(k-\mathrm{1}/n\right),\left(k/n\right)\right\}\text{CM}$

(5) endfor

(6) if packets (node i)→destination

(7) for $j=1$  : k

(8) for $l=n$  : 1

(9) if node $m\notin$ path j

(10)  if G(node m) = $n-1$ and $dist(i,m)$ →minimum

(11)  establish path( $i,m$ )

(12)  endif

(13)  endif

(14)  endfor

(15)  endfor

(16)  interests(Source→Destination)

(17)  evaluate the quality of paths by ${{\displaystyle \sum }}_{i=1}^n\text{CM}(i)$

(18)  packets(Destination→Source)

4.3. Mathematical Model and Performance Analysis

4.3.1. Mechanism of Linear Erasure Coding

Assume that $Mb$ size packets will be transmitted at the source nodes, which means quantity of M packets, and each packet is b bytes size. $Mb$ packets will be decomposed into $(M+K)$ fragments by erasure coding mechanism and each fragment is $(M/(M+K))b$ bytes. Quantity of $x_i\hspace{0.17em}(i=\mathrm{1,2},\dots ,n)$ coded fragments are allocated to and forwarded along ith paths by load balance mechanism. Due to $M+K$ fragments being transmitted at the source node, thus ${\sum }_{i=\mathrm{1}}^n{x}_i={\mathit{X}}^T\mathbf{1}=M+K$ , where $\mathit{X}=[x_{\mathrm{1}},x_{\mathrm{2}},\dots x_n{]}^T$ , $x_i$ represents the quantity of coded fragments allocated to ith paths. $\mathbf{1}$ is the matrix all with 1. At least M coded fragments received at the destination node can be decoded and reconstructed into source packet successfully. Suppose $z_i$ coded fragments are received on the $\text{pat}{\text{h}}_i$ , the probability that the received encoded fragments can be successfully reconstructed into the source packet is

$$\begin{array}{cc}& p_{\text{succ}}=p\left[{\displaystyle \sum }_{i=\mathrm{1}}^n{z}_i\ge M\right].\end{array}$$

(2)

$p_{\text{succ}}$ represents the successful transmission rate of packets which reflects the transmission reliability of network layer. Now assume that $\mathit{q}=[q_{\mathrm{1}},q_{\mathrm{2}},\dots q_n]$ represents the successful transmission rate of each path and all transmission paths are independent from each other. It has

$$\begin{array}{cc}& p_{\text{succ}}\ge Q\left(\mathit{x},\mathit{q},K\right),\end{array}$$

(3)

where

$$\begin{array}{cc}& Q\left(\mathit{x},\mathit{q},K\right)={\displaystyle \sum }_{j=\mathrm{0}}^K\frac{e^{-\lambda \left(x\right)}{\left[\lambda \left(\mathit{x}\right)\right]}^j}{j!},\\ \lambda \left(\mathit{x}\right)={\displaystyle \sum }_{i=\mathrm{1}}^n\ln \left(q_i^{-x_i}\right)=-{\displaystyle \sum }_{i=\mathrm{1}}^n{x}^T\ln \mathit{q}.\end{array}$$

(4)

also $\ln \mathit{q}=[\ln q_{\mathrm{1}},\ln q_{\mathrm{2}},\dots ,\ln q_n{]}^T$ ; the multipath transmission model is as shown in Figure 4.

Figure 4

Multipath transmission model.

Figure 4 shows the multipath transmission model. $N_{\text{sour}}$ represents source sensor node and it has quantity of $M+K$ coded fragments that will be transmitted to destination node, $N_{\text{dest}}$ represents destination sensor node on which the source packets can be successfully transmitted only when at least quantity of M coded fragments are received at the destination nodes, $x_i$ means the quantity of coded packets allocated to the ith transmission paths established from $N_{\text{sour}}$ to $N_{\text{dest}}$ , $q_i^{\mathrm{2}}$ represents packets successful transmission rate form node $N_i^{\mathrm{2}}$ to $N_i^{\mathrm{3}}$ on the ith transmission paths, $Z_i$ represents the received coded packets at node $N_{\text{dest}}$ from the ith transmission paths, ${\sum }_{i=\mathrm{1}}^n{z}_i$ represents the received coded packets at node $N_{\text{dest}}$ from all established transmission paths, and ith path is independent of $(i+\mathrm{1})$ th path owning to that multiple paths are uncrossed.

4.3.2. Success Rate of Packet Transmission

Transmission reliability of network can be evaluated by the success rate of data transmission. In the model it is defined as rate of coded fragments received at the destination node and all coded fragments needed being transmitted at the source node. ${\eta }_{\text{data}}$ represents success rate of data transmission:

$$\begin{array}{cc}& {\eta }_{\text{data}}=\frac{M}{M+K}.\end{array}$$

(5)

Success rate of data transmission for the jth link on $\text{pat}{\text{h}}_i$ is defined as the multiplication of successful transmission rate of each former link on $\text{pat}{\text{h}}_i$ . It is defined as follows:

$$\begin{array}{cc}& q_i^j={\displaystyle \prod }_{l=\mathrm{1}}^j{q}_i^l.\end{array}$$

(6)

For the above definition of success rate of data transmission, success rate of data transmission for the ith path from the source node to the destination node can be deduced as follows:

$$\begin{array}{cc}& q_i={\displaystyle \prod }_{k=\mathrm{1}}^{n_i-\mathrm{1}}{q}_i^k.\end{array}$$

(7)

Quantity of received coded fragments at the destination node for $\text{pat}{\text{h}}_i$ can be calculated by success transmission rate $q_i$ and the quantity of allocated packets $x_i$ of $\text{pat}{\text{h}}_i$ :

$$\begin{array}{cc}& x_i^{\prime }=x_i·{\displaystyle \prod }_{k=\mathrm{1}}^{N_{\text{node}}-\mathrm{1}}{q}_i^k.\end{array}$$

(8)

According to (5), for calculating the success rate of data transmission, quantity of coded fragments received at the destination node should be gotten. For the whole network, quantity of total received coded fragments at the destination node is

$$\begin{array}{cc}& x={\displaystyle \sum }_{i=\mathrm{1}}^n{x}_i^{\prime }={\displaystyle \sum }_{i=\mathrm{1}}^n(x_i·{\displaystyle \prod }_{k=\mathrm{1}}^{N_{\text{node}}-\mathrm{1}}{q}_i^k),\end{array}$$

(9)

where ${\sum }_{i=\mathrm{1}}^n{x}_i=M+K$ .

Success rate of data transmission in the model is

$$\begin{array}{cc}& {\eta }_{\text{data}}^{\prime }=\frac{n}{M+K}=\frac{\left({\sum }_{i=\mathrm{1}}^n\left(x_i·{{\displaystyle \prod }}_{k=\mathrm{1}}^{N_{\text{node}}-\mathrm{1}}{q}_i^k\right)\right)}{(M+K)}.\end{array}$$

(10)

If the received packets can be reconstructed into source packets, it has ${\eta }^{\prime }\ge \eta$ .

4.3.3. Load Balance Mechanism

Due to the restrained resources of calculation and transmission, all encoded fragments at the source node should not be transmitted on each established path. If not, this will lead to a large number of redundant packets transmission in the network and consume more energy. Transmission delay will occur due to packets collision. Furthermore, it does not need too much redundant packets to reconstruct the source data at the destination node. Too much redundant packets will also cause great resources waste of decoding calculation and the storage of destination node. Therefore, multipath based load balance mechanism should be adopted. Different quantity of encoded fragments at the destination node is allocated to paths with different quality to transmit.

Firstly, it is to normalize each path's success rate of data transmission $q_i={\prod }_{k=\mathrm{1}}^{n_i-\mathrm{1}}{q}_i^k$ , $i\in (\mathrm{1,2},\dots ,n)$ . It has

$$\begin{array}{cc}& q_i^{\prime }=\frac{{{\displaystyle \prod }}_{k=\mathrm{1}}^{n_i-\mathrm{1}}{q}_i^k}{{\sum }_{i=\mathrm{1}}^n{{\displaystyle \prod }}_{k=\mathrm{1}}^{n_i-\mathrm{1}}{q}_i^k},\end{array}$$

(11)

where ${\sum }_{i=\mathrm{1}}^n{q}_i^{\prime }=\mathrm{1}$ . Therefore the quantity of coded fragments allocated to $\text{pat}{\text{h}}_i$ is $q_i^{\prime }(M+K)$ .

The quantity of coded fragments received at the destination node is

$$\begin{array}{cc}& x^{\prime }={\displaystyle \sum }_{i=\mathrm{1}}^n{q}_i^{\prime }\left(M+K\right){\displaystyle \prod }_{k=\mathrm{1}}^{n_i-\mathrm{1}}{q}_i^k.\end{array}$$

(12)

Lemma 3.

The quantity of coded fragments received at the destination node by the load balance mechanism is equal to or greater than it, not by the load balance mechanism; namely, $x^{\prime }\ge x$ .

Proof.

$x^{\prime }={\sum }_{i=\mathrm{1}}^n{q}_i^{\prime }(M+K){\prod }_{k=\mathrm{1}}^{n_i-\mathrm{1}}{q}_i^k$ , $x={\sum }_{i=\mathrm{1}}^n{x}_i{q}_i$ , where $q_i^{\prime }={\prod }_{k=\mathrm{1}}^{n_i-\mathrm{1}}{q}_i^k/{\sum }_{i=\mathrm{1}}^n{\prod }_{k=\mathrm{1}}^{n_i-\mathrm{1}}{q}_i^k$ .

• (1)

When $q_{\mathrm{1}}=q_{\mathrm{2}}=q_i=\cdots =q_n$ ,

$$\begin{array}{l}x={\displaystyle \sum }_{i=\mathrm{1}}^n{x}_i{q}_i=q_i\left(M+K\right),\hfill \\ x^{\prime }={\displaystyle \sum }_{i=\mathrm{1}}^n{q}_i^{\prime }\left(M+K\right){\displaystyle \prod }_{k=\mathrm{1}}^{n_i-\mathrm{1}}{q}_i^k\hfill \\ =\frac{{\sum }_{i=\mathrm{1}}^n\left(M+K\right)q_i^{\mathrm{2}}}{{\sum }_{i=\mathrm{1}}^n{q}_i}=q_i(M+K)x^{\prime }=x.\hfill \end{array}$$

(13)

(2)

When $(q_{\mathrm{1}},q_{\mathrm{2}},\dots ,q_n)$ is not all equal, when $x_{\mathrm{1}}=x_{\mathrm{2}}=x_i=\cdots =x_n$ ,

$$\begin{array}{l}{x}^{\prime }={\displaystyle \sum }_{i=\mathrm{1}}^n{q}_i^{\prime }\left(M+K\right){\displaystyle \prod }_{k=\mathrm{1}}^{n_i-\mathrm{1}}{q}_i^k=\frac{{\sum }_{i=\mathrm{1}}^n\left(M+K\right)q_i^{\mathrm{2}}}{{\sum }_{i=\mathrm{1}}^n{q}_i},\hfill \\ x={\displaystyle \sum }_{i=\mathrm{1}}^n{x}_i{q}_i=\frac{(M+K)}{n}{\displaystyle \sum }_{i=\mathrm{1}}^n{q}_i,\hfill \\ \frac{x^{\prime }}{x}=\frac{n{\sum }_{i=\mathrm{1}}^n{q}_i^{\mathrm{2}}}{{\left({\sum }_{i=\mathrm{1}}^n{q}_i\right)}^2}=n·{\displaystyle \sum }_{i=\mathrm{1}}^n{\left(\frac{q_i}{{\sum }_{i=\mathrm{1}}^n{q}_i}\right)}^2\hfill \\ =n·{\displaystyle \sum }_{i=\mathrm{1}}^n{\left(q_i^{\prime }\right)}^{\mathrm{2}}\ge \mathrm{1},\hspace{1em}\text{for}\hspace{0.17em}\hspace{0.17em}{\displaystyle \sum }_{i=\mathrm{1}}^n{q}^{\prime }=\mathrm{1},\hfill \end{array}$$

(14)

let

$$\begin{array}{cc}& f(q_{\mathrm{1}}^{\prime },q_{\mathrm{2}}^{\prime },\dots ,q_n^{\prime },\lambda )={\displaystyle \sum }_{i=\mathrm{1}}^n{\left(q_i^{\prime }\right)}^{\mathrm{2}}-\lambda \left({\displaystyle \sum }_{i=\mathrm{1}}^n{q}^{\prime }-\mathrm{1}\right)=\mathrm{0}.\end{array}$$

(15)

If and only if $q_{\mathrm{1}}^{\prime }=q_{\mathrm{2}}^{\prime }=\cdots =q_n^{\prime }=\mathrm{1}/n$ , it has

$$\begin{array}{cc}& \min \left(f(q_{\mathrm{1}}^{\prime },q_{\mathrm{2}}^{\prime },\dots ,q_n^{\prime },\lambda )\right)\end{array}$$

(16)

and when $(x_{\mathrm{1}},x_{\mathrm{2}},\dots x_n)$ is not all equal, let $f(q_{\mathrm{1}}^{\prime },q_{\mathrm{2}}^{\prime },\dots ,q_n^{\prime },x_{\mathrm{1}},x_{\mathrm{2}},\dots x_n,{\lambda }_{\mathrm{1}},{\lambda }_{\mathrm{2}})={\sum }_{i=\mathrm{1}}^n(x_i{q}_i^{\prime })-{\lambda }_{\mathrm{1}}({\sum }_{i=\mathrm{1}}^n{x}_i-(M+K))-{\lambda }_{\mathrm{2}}({\sum }_{i=\mathrm{1}}^n{q}_i-\mathrm{1})=\mathrm{0}$ , and do the partial derivative, respectively, to eight parameters and simultaneous equation solution; when $x_{\mathrm{1}}=x_{\mathrm{2}}=\cdots =x_n=(M+K)/n$ and $q_{\mathrm{1}}=q_{\mathrm{2}}=\cdots =q_n=\mathrm{1}/n$ , $(M+K)/n\le f(q_{\mathrm{1}}^{\prime },q_{\mathrm{2}}^{\prime },\dots ,q_n^{\prime },x_{\mathrm{1}},x_{\mathrm{2}},\dots x_n)<(M+K)$ , it has $E(x^{\prime })<E(x)$ .

4.3.4. Efficiency of Energy Consumption

Assume that energy consumption is $e_i^k$ when transmitting k bit fragments on $\text{pat}{\text{h}}_i$ ; $e_i^k$ and the node's available energy $E_i^k$ do not vary during the data transmission. So the total energy consumption of the unit byte's transmission on $\text{pat}{\text{h}}_i$ is the sum of energy consumption of the unit byte's transmission on each link of $\text{pat}{\text{h}}_i$ ; namely,

$$\begin{array}{cc}& e_i={\displaystyle \sum }_{k=\mathrm{0}}^{n_i-\mathrm{1}}{e}_i^k,\end{array}$$

(17)

where $n_i$ is the ith node of the $\text{pat}{\text{h}}_i$ .

Energy consumption vector of the unit byte is ${\mathbf{E}}_b=[e_{\mathrm{1}},e_{\mathrm{2}},\dots ,e_n{]}^T$ , so energy consumption for successfully transmitting $M+K$ fragments without packet loss is $E_{\text{total}}(\mathit{x},{\mathbf{E}}_b)=b(M+K)x^T{E}_b$ . When nodes’ residual energy on $\text{pat}{\text{h}}_i$ runs out, the maximum quantity of the transmitted fragments is

$$\begin{array}{cc}& M_i^e=\underset{\mathrm{1}\le k\le n_i}{\min }\left\{\frac{E_i^k}{b{e}_i^k}\right\}\end{array}$$

(18)

$M_i^e$ is determined by

$$\begin{array}{cc}& M_i^e⟵\underset{\mathrm{1}\le k\le n_i}{\min }\left\{M_i^e,\frac{E_i^k}{b{e}_i^k}\right\}.\end{array}$$

(19)

Packet loss exists during the transmission by load balance mechanism. The energy consumption of data transmission of the kth link on $\text{pat}{\text{h}}_i$ is

$$\begin{array}{cc}& E_i^k=b{x}_i{\displaystyle \prod }_{j=\mathrm{1}}^{k-\mathrm{1}}{e}_i^k{q}_i^{j-\mathrm{1}}.\end{array}$$

(20)

Energy consumption of transmitting $x_i$ fragments on $\text{pat}{\text{h}}_i$ is

$$\begin{array}{cc}& E_{\text{pat}{\text{h}}_i}^k=b{\displaystyle \sum }_{k=\mathrm{1}}^{n_i-\mathrm{1}}\left(x_i{\displaystyle \prod }_{j=\mathrm{1}}^{k-\mathrm{1}}{e}_i^k{q}_i^{j-\mathrm{1}}\right).\end{array}$$

(21)

Energy consumption of transmitting $M+K$ fragments is

$$\begin{array}{cc}& E_{\text{network}}=b{\displaystyle \sum }_{i=\mathrm{1}}^n\left({\displaystyle \sum }_{k=\mathrm{1}}^{n_i-\mathrm{1}}\left(x_i{\displaystyle \prod }_{j=\mathrm{1}}^{k-\mathrm{1}}{e}_i^k{q}_i^{j-\mathrm{1}}\right)\right),\end{array}$$

(22)

where ${\sum }_{i=\mathrm{1}}^n{x}_i=M+K$ .

Energy consumption of data transmission of the kth link on $\text{pat}{\text{h}}_i$ by load balance mechanism is

$$\begin{array}{cc}& E_i^{\prime k}=b\left(M+K\right)q_i^{\prime }{\displaystyle \prod }_{j=\mathrm{1}}^{k-\mathrm{1}}{e}_i^k{q}_i^{j-\mathrm{1}},\end{array}$$

(23)

where ${\sum }_{i=\mathrm{1}}^n{q}^{\prime }=\mathrm{1}$ .

Energy consumption of transmitting $x_i$ fragments on $\text{pat}{\text{h}}_i$ is

$$\begin{array}{cc}& E_{\text{pat}{\text{h}}_i}^{\prime k}=b\left(M+K\right)q_i^{\prime }{\displaystyle \sum }_{k=\mathrm{1}}^{n_i-\mathrm{1}}\left({\displaystyle \prod }_{j=\mathrm{1}}^{k-\mathrm{1}}{e}_i^k{q}_i^{j-\mathrm{1}}\right).\end{array}$$

(24)

Energy consumption of transmitting $M+K$ fragments by load balance mechanism for the whole network is

$$\begin{array}{cc}& E_{\text{network}}^{\prime }=b(M+K){\displaystyle \sum }_{i=\mathrm{1}}^n\left(q_i^{\prime }{\displaystyle \sum }_{k=\mathrm{1}}^{n_i-\mathrm{1}}\left({\displaystyle \prod }_{j=\mathrm{1}}^{k-\mathrm{1}}{e}_i^k{q}_i^{j-\mathrm{1}}\right)\right).\end{array}$$

(25)

Therefore, energy consumption of successful transmitted fragments, respectively, by load balance mechanism and not by it is defined as

$$\begin{array}{cc}& {\eta }_{\text{energy}}^{\prime }=\frac{E_{\text{network}}^{\prime }}{x^{\prime }}\frac{b(M+K){\sum }_{i=\mathrm{1}}^n\left(q_i^{\prime }{\sum }_{k=\mathrm{1}}^{n_i-\mathrm{1}}\left({{\displaystyle \prod }}_{j=\mathrm{1}}^{k-\mathrm{1}}{e}_i^k{q}_i^{j-\mathrm{1}}\right)\right)}{{\sum }_{i=\mathrm{1}}^n{q}_i^{\prime }(M+K){{\displaystyle \prod }}_{k=\mathrm{1}}^{n_i-\mathrm{1}}{q}_i^k},\\ {\eta }_{\text{energy}}=\frac{E_{\text{network}}}{x}=\frac{b{\sum }_{i=\mathrm{1}}^n\left({\sum }_{k=\mathrm{1}}^{n_i-\mathrm{1}}\left(x_i{{\displaystyle \prod }}_{j=\mathrm{1}}^{k-\mathrm{1}}{e}_i^k{q}_i^{j-\mathrm{1}}\right)\right)}{{\sum }_{i=\mathrm{1}}^n(x_i·{{\displaystyle \prod }}_{k=\mathrm{1}}^{N_{\text{node}}-\mathrm{1}}{q}_i^k)}.\end{array}$$

(26)

Lemma 4.

The energy efficiency of the network by load balance mechanism is higher than not by it; namely ${\eta }_{\text{energy}}^{\prime }<{\eta }_{\text{energy}}$ .

Proof.

$E_{\text{network}}^{\prime }$ - $x^{\prime }$ has the same linear relationship with $E_{\text{network}}$ -x. If $\{e_i^k,i=\mathrm{1,2},\dots ,n\}$ are all equal, it has ${\eta }_{\text{energy}}^{\prime }={\eta }_{\text{energy}}$ . Each path's quality is not equal due to different length of links and different total length of paths, as well as unequal transmitting power of the nodes, so $\{e_i^k\}$ are not equal to each other.

Suppose energy consumption of unit byte's transmission of each link on one path is equal; namely, $\{e_i^k,k=\mathrm{1,2},\dots ,n_i-\mathrm{1}\}$ is equal. Equal quantity of fragments $x^{\mathrm{\prime \prime }}$ is allocated to optimal $\text{pat}{\text{h}}_i$ and suboptimal $\text{pat}{\text{h}}_{i+\mathrm{1}}$ :

$$\begin{array}{l}\Theta =\frac{{\eta }_i}{{\eta }_{i+\mathrm{1}}}=\frac{b{x}^{\mathrm{\prime \prime }}{\sum }_{k=\mathrm{1}}^{n_i-\mathrm{1}}\left({{\displaystyle \prod }}_{j=\mathrm{1}}^{k-\mathrm{1}}{e}_i^k{q}_i^{j-\mathrm{1}}\right)/x^{\mathrm{\prime \prime }}{{\displaystyle \prod }}_{k=\mathrm{1}}^{n_i-\mathrm{1}}{q}_i^k}{b{x}^{\mathrm{\prime \prime }}{\sum }_{k=\mathrm{1}}^{n_i-\mathrm{1}}\left({{\displaystyle \prod }}_{j=\mathrm{1}}^{k-\mathrm{1}}{e}_{i+\mathrm{1}}^k{q}_{i+\mathrm{1}}^{j-\mathrm{1}}\right)/x^{\mathrm{\prime \prime }}{{\displaystyle \prod }}_{k=\mathrm{1}}^{N_{\text{node}}-\mathrm{1}}{q}_i^k}\hfill \\ <\frac{q_i{e}_i^k/q_i}{q_{i+\mathrm{1}}{e}_{i+\mathrm{1}}^k/q_{i+\mathrm{1}}}<\frac{e_i^k}{e_{i+\mathrm{1}}^k}<\mathrm{1},\hfill \end{array}$$

(27)

where $e_i^k<e_{i+\mathrm{1}}^k$ . So the efficiency of energy consumption on the optimal path is higher than it on the suboptimal path when transmitting the same quantity of fragments. For the same $M+K$ fragments needing to be transmitted at the source node, it has higher energy consumption efficiency for the optimal path under the load balance mechanism which allocates more fragments to higher quality path; namely, ${\eta }_{\text{energy}}^{\prime }<{\eta }_{\text{energy}}$ .

4.3.5. Transmission Delay

The delay usually refers to the time interval from the moment that the source packet is begun to send the at the source node to the moment that it is received successfully at the destination node; it mainly includes producing delay, queuing delay, transmitting delay, and sending delay; namely, $t_{\text{total}}=t_{\text{gen}}+t_{\text{que}}+t_{\mathrm{tran}}+t_{\text{sen}}$ . The queuing delay $t_{\text{que}}$ constitutes the main part of the delay; it has $t_{\text{total}}\approx t_{\text{que}}$ .

Assume that the time interval t is needed at each node when unit packet Ω is transmitted; thus the transmission delay of the allocated packets on the ith path is

$$\begin{array}{cc}& t_i=\frac{t(M+K)q_i^{\prime }}{\Omega }\hspace{0.17em}{\displaystyle \sum }_{k=\mathrm{1}}^{n_i-\mathrm{1}}\left({\displaystyle \prod }_{j=\mathrm{1}}^{k-\mathrm{1}}{q}_i^{j-\mathrm{1}}\right).\end{array}$$

(28)

Thus the transmission delay of the whole network is

$$\begin{array}{l}{t}_{\text{network}}=\max \left\{\frac{t\left(M+K\right)q_i^{\prime }}{\Omega }\hspace{0.17em}{\displaystyle \sum }_{k=\mathrm{1}}^{n_i-\mathrm{1}}\left({\displaystyle \prod }_{j=\mathrm{1}}^{k-\mathrm{1}}{q}_i^{j-\mathrm{1}}\right)\right\},\hfill \\ \phantom{\left\{\frac{t\left(M+K\right)q_i^{\prime }}{\Omega }\hspace{0.17em}\right\}}\hspace{0.17em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.5em}\hspace{0.5em}\hspace{1em}\hspace{0.5em}i=\mathrm{1,2},\dots ,n.\hfill \end{array}$$

(29)

However, when $M+K$ coded fragments are sent at the source node by load balance mechanism, source packet can be reconstructed by receiving $M^{\prime }$   ( $M^{\prime }\ge M$ ) coded fragments in the set time $t_{\text{set}}$ . Thus the transmission 参 与 delay of the network is

$$\begin{array}{cc}& t_{\text{network}}^{\prime }=\min \left\{\max \left\{\frac{t\left(M+K\right)q_i^{\prime }}{\Omega }{\displaystyle \sum }_{k=\mathrm{1}}^{n_i-\mathrm{1}}\left({\displaystyle \prod }_{j=\mathrm{1}}^{k-\mathrm{1}}{q}_i^{j-\mathrm{1}}\right)\right\},t_{\text{set}}\right\}.\end{array}$$

(30)

The transmission delay of the same quantity of packets in single-path transmission mode is

$$\begin{array}{cc}& t_{\text{network}}^{\mathrm{\prime \prime }}=\frac{t(M+K)}{\Omega }{\displaystyle \sum }_{k=\mathrm{1}}^{n_i-\mathrm{1}}\left({\displaystyle \prod }_{j=\mathrm{1}}^{k-\mathrm{1}}{q}_{}^{j-\mathrm{1}}\right).\end{array}$$

(31)

Beyond the doubt, $t_{\text{network}}^{\mathrm{\prime \prime }}>t_{\text{network}}\ge t_{\text{network}}^{\prime }$ .

5. Simulation and Analysis

Assumptions. (1) Network node is static and each node's location is known; (2) the initial state of the nodes is equal; each has the same parameters and initial energy; (3) the network node is in full duplex work mode; (4) the nodes are randomly and uniformly distributed in the rectangular area.

The simulation is based on PC with processor i3-2100 and 4G RAM as well as Matlab simulation scenario. In the simulation, 150 nodes are randomly deployed in the area $[\mathrm{200,200}]$ . Destination node is located at the coordinate $[\mathrm{200,100}]$ on the right side of the area. Set the parameter $w_{\mathrm{1}}=\mathrm{0.3}$ , $w_{\mathrm{2}}=\mathrm{0.5}$ , $w_{\mathrm{3}}=\mathrm{0.2}$ and the probability $p=0.15$ . Communication model is based on the clustering topology. The initial energy of each node is set with 1000 nJ. The model of energy consumption and parameters ${\epsilon }_{\text{amp}}$ , $E_{\text{fuse}}$ , $E_{\text{elec}}$ , $E_{\text{tx}}$ , and $E_{\text{rx}}$ refer to [24, 25]. The size of source packet $S_p$ is set with 2000 bits. Fault node is defined as the node in which energy consumption achieves the initial threshold value $\delta =\mathrm{0.3}{e}_{\text{ini}}(i)$ and $e_{\text{ini}}(i)$ is the initial energy of a node. The network life is defined as the period from the starting of the networking operation to the moment that 10% of the network nodes’ energy runs out. The sensor data are acquired and transmitted periodically. The node reconstructs the received coded fragments into the source packets at a certain interval $\Delta t$ . Now the comparison is made among three methods: (1) the presented multipath gradient routing with reliable transmission and fault tolerant; (2) DD routing protocol [12]; (3) FGS [17].

5.1. Network Topology

The clustering topology, nodes’ comprehensive measurement, and contour lines are simulated in this section.

Figure 5 shows the random distribution of the nodes. 150 nodes are randomly deployed in the area $[\mathrm{200,200}]$ . The coordinate of the destination node is $[\mathrm{200,100}]$ showed in a red circle. Figure 6 shows the clustering mode based on the first round K-means clustering algorithm. Cluster heads are randomly selected by the probability p. Clusters shown in Figure 6 are randomly formed and the scales are almost equal. Quantity of nodes in each cluster is almost the same whether the cluster is near or far from the destination node.

Figure 5

Random distribution of the network nodes.

Figure 6

Clustering mode based on once K-means algorithm.

Figure 7 shows the clustering mode based on twice K-means cluster splitting and optimization. In order to form the hierarchical clustering topology, it does the cluster division on the clusters which has higher CM and does the second round K-means algorithm based clustering after the first round clustering. Simulation shows that cluster splitting is carried out on the clusters which are near to the destination node. Finally smaller scale and larger quantity of clusters are formed in this area. As a result, clusters being near to the destination node have fewer nodes. The clusters which are far from the destination node have more quantity of nodes.

Figure 7

Clustering mode based on twice K-means clustering.

Figure 8 shows the contour lines which are established among the cluster heads. After calculations of cluster heads’ CM, all nodes’ CM values are hierarchically divided. The nodes with equal hierarchy values have similar CM values according the rules presented above. Now hierarchies of all cluster heads’ CM (comprehensive measurements) are determined. CM based contour lines are established to connect the cluster heads with the same hierarchy values which are marked in red color. From Figure 8, it finally forms 10 contour lines. These contour lines have different hierarchical values and prepare for establishing the multiple transmission paths.

Figure 8

Contour lines among cluster heads.

5.2. Characteristics of the Data Transmission

Packet reception rate and accuracy are adopted to reflect the characteristics of data transmission. This is closely related to the link quality and performance of fault tolerance. Packet reception rate and accuracy can reflect the link quality and performance of fault tolerance. Packet receiving rate is defined as the quantity ratio of received packets and source packets. The higher the packet receiving rate is, the lower the packets lose in the transmission process and the better the quality of the links is. Simulation of the packet receiving rate is shown in Figure 9.

Figure 9

Comparison of the receiving rate of transmission packets.

Figure 9 shows comparison of the receiving rate of transmission packets. Now it gives the ratio of the received packets and all source packets when the network runs at 1000–2000 times. The presented algorithm in the study and FGS keep a high data receiving rate in $[\mathrm{0.95,1}]$ and are relatively stable. The data receiving rate of DD routing protocol varies in $[\mathrm{0.90,0.98}]$ and the packet receiving rate is relatively low and declines dramatically in the later operation stage. From Figure 9, the presented algorithm in the study has higher packet receiving rate than any other two algorithms and it is also shown to be smooth and steady. This illustrates that the presented algorithm has less packet loss during the process of packets transmission. It has better performance of reliable packets transmission.

Data accuracy is defined as the quantity ratio of the received packet that can be reconstructed into source data and the source packets. It reflects the accuracy of data decoding and reconstruction, the simulation is shown in Figure 10.

Figure 10

Comparison of the accuracy rate of transmission data.

Figure 10 shows the comparison of the packets accuracy rate in the packets transmission among the presented algorithm, FGS and DD routing. It shows that data accuracy rate is higher than the data receiving rate at the same network operation times, because the data decoding transmission mechanism allows certain coded packets loss and does not affect the reconstruction into the source packet. This means that it still has higher data accuracy rate even if some coded packets are lost. The accuracy rate of the transmission data varies steadily and keeps within [0.95, 1] along with the network operation. The accuracy rate of the presented method and FGS keeps higher which is within [0.98, 1] when the network runs at 1000–2000 times. The presented algorithm has superior performance in data accuracy.

5.3. Performance of Energy Consumption and Load Balance

Energy consumption model of data transmission is adopted from [24, 25]. The balance of energy consumption refers to that the residual energy keeps at the similar level during each operation time.

In Figure 11, the part in red, green, and blue, respectively, presents the residual energy when network runs at 600, 1000, and 1400 times. It can be concluded that the residual energy keeps at the similar level during three randomly selected times. For example, the residual energy varies within $[750,850]$ when it is running at 600 times. It shows the good performance of energy consumption and load balance.

Figure 11

Residual energy when the network is running at 600, 1000, and 1400 times.

Figure 12 shows comparison of average residual energy of all the nodes, including the cluster heads and cluster members, on the contour lines 1, 4, and 7 which are selected randomly when the network runs at 1000–2000 times. From Figure 12, the average residual energy of the nodes on three contour lines is almost the same. When the network runs at 1800 times, the residual energy on contour line 1 declines obviously. From this point, it reflects good performance in the balance of nodes’ energy consumption.

Figure 12

Comparison of average residual energy of three randomly selected contour lines.

6. Conclusions

The stability and reliability of transmission are much important to the performance of wireless sensor networks. The failures of nodes or links will lower the transmission reliability and increase the transmission delay and energy consumption. The multipath gradient based reliable transmission strategy with fault tolerance presented in this study mainly includes establishing the nonuniform clustering topology based on twice K-means algorithm, calculating the cluster heads’ CM and contour lines, and establishing multiple gradient based disjoint transmission paths. The balance mechanism based on the multipath transmission is also studied so that the encoded fragments are allocated and forwarded along multiple paths. The encoded fragments are decoded and reconstructed into the source data to realize fault tolerance in transmission. Mathematical model is established to analyze and evaluate the performance of the network. Simulations show that the gradient based multipath routing with load balance mechanism has fast effective clustering topology and distributed multipath establishment. Gradient based routing can lower the complexity of the multipath routing establishment and energy consumption. The algorithm improves the success rate of the coded fragments, the accuracy of the source packet, and efficiency of the energy consumption. Finally it improves performance of fault tolerance and reliability of data transmission.