An Efficient Reliable Communication Scheme in Wireless Sensor Networks Using Linear Network Coding

Abstract

We address the modeling and design of linear network coding (LNC) for reliable communication against multiple failures in wireless sensor networks (WSNs). To fulfill the objective, we design a deterministic LNC scheme RDLC based on the average number of path failures simultaneously happening in the network other than the maximum number of path failures. The scheme can significantly improve the network throughput comparing with the traditional approaches. In our study, we also investigate the potential of random linear code RRLC for providing reliable communication in WSNs and prove the low bound of the probability that the RRLC can provide the reliable communication. Finally, extensive simulation experiments have been conducted, and the results demonstrate the effectiveness of the proposed LNC schemes.

1. Introduction

In recent years, wireless sensor network (WSN) has attracted significant attention for future generations of wireless applications in industry, agriculture, and military [1–5]. Despite its salient potentials, there are still many challenges to be addressed. In this paper, we will investigate how to provide reliable data transmissions in WSNs, which is very challenging because not only the wireless medium is vulnerable to severe channel fading and interference but also the sensor node always faces to energy exhaustion and physical damage.

Clearly, how to provide reliable communication in WSNs can be studied from multiple layers, including the physical layer and the MAC layer [6–9]. In this work, we will focus on the network layer and transport layer. Particularly, we will study how to provide reliable communication in WSNs against loss of data packets.

To provide reliable communication against node or link failures, there are two kinds of traditional approaches [10]: the proactive recovery and the reactive recovery, which aim at recovering the data transmission when node or link failures happen. The proactive recovery approaches can recover data transmission immediately when a link or node failure occurs, because it reserves the bandwidth (in backup paths) between the source node and the destination node in advance and the data flow is simultaneously transmitted on both primary paths and backup paths. On the other hand, the proactive recovery approaches do not provide any immediate recovery in advance. When the failure occurs on the routing paths of the data flow, the affected flow will be retransmitted to the destination by using available bandwidth in the network. Therefore, although the proactive recovery approaches can recover data transmission immediately when the link or node failures happen, network resources (e.g., bandwidth on the backup paths) are wasted when no failure happens. For the proactive recovery approaches, although network resources are used efficiently (no network resource is reserved in advance), the procedure of transferring the data traffic from the failed paths to the new routing paths incurs a considerable delay to data communications.

Following its success in maximizing network throughput [11–15], linear network coding (LNC) has recently been shown to be a promising approach that can achieve reliable communication with much better efficiency, because it can be used to provide protection in a proactive manner with the bandwidth cost in a reactive manner [16–20]. LNC has been first introduced by Kamal [16, 19] to provide 100% protection against single link failures in optical network. Recently, the design of reliable communication based on LNC has attracted an increasing amount of attention in optical networks [16], wireless networks [18], and hybrid wireless-optical access networks [20], respectively. However, in these studies, the LNC scheme, which can generate large number of linear combinations of original data packets to provide reliable communication when link or node failures happen, is designed according to the maximum number of failures ( $f_{\max \hspace{0.17em}}$ , i.e., the worst case) happening simultaneously. In this case, with such LNC schemes, the destination can receive sufficient coded data packets and recover the original data packets, as long as the number of failures happening simultaneously is no more than $f_{\max \hspace{0.17em}}$ . However, the number of failures happening simultaneously in WSNs varies at different times in practice. When the number of failures happening simultaneously in the network is less than $f_{\max \hspace{0.17em}}$ , the network throughput decreases because the capacity of the WSN is wasted by the redundant coded data packets transmitted in the WSN.

Therefore, our key idea is to increase the number of original data packets transmitted and recovered in the transmission rounds with large number of failures happening simultaneously, by utilizing the redundant coded data packets transmitted in the transmission rounds with fewer failures happening simultaneously in the network to improve the network throughput.

Figure 1 gives an example to compare the network throughput that can be achieved by LNC scheme based on the maximum number of failures $f_{\max \hspace{0.17em}}$ and the LNC scheme based on the average number of failures $f_{\exp \hspace{0.17em}}$ (denoted in Section 2.1). Specifically, in the WSN, there are 4 edge-disjoint paths between the source S and the destination (sink) D. Suppose that $f_{\max \hspace{0.17em}}=\mathrm{2}$ and $f_{\exp \hspace{0.17em}}=\mathrm{1}$ . Without loss of generality, we assume that 2 path failures happen in time slot 1 and no failure happens in time slot 2. Different LNC schemes are shown in Figures 1(a) and 1(b), in which the notation “ $S_{\mathrm{1}}:{\mathbf{x}}_{\mathrm{1}}+{\mathbf{x}}_{\mathrm{2}}$ ” on a link denotes the link is used to transmit a coded symbol ${\mathbf{x}}_{\mathrm{1}}+{\mathbf{x}}_{\mathrm{2}}$ at time slot 1. Moreover, for LNC schemes shown in both Figures 1(a) and 1(b), the coded data packets transmitted on the links belonging to the same path are same in given time slot.

Figure 1

Reliable communication using LNC: an example.

Since the $f_{\max \hspace{0.17em}}=\mathrm{2}$ , in Figure 1(a), the LNC scheme designed based on $f_{\max \hspace{0.17em}}$ can ensure that the destination can decode and recover even if $\mathrm{2}$ path failures happen. However, no failure happens in time slot 2, which decreases the network throughput because the capacity of the WSN is wasted by the redundant coded data packets transmitted in time slot 2. On the other hand, in Figure 1(b), the LNC scheme was designed based on $f_{\exp \hspace{0.17em}}$ , in which part of original data packets sent previously is still encoded into the following time slots. In this case, the network throughput can be improved by utilizing the redundant coded data packets transmitted in time slot 2. Specifically, with different LNC schemes, the sink can recover 4 original data packets in 2 time slots (i.e., the achieved network throughput is $\mathrm{2}$ ) in the case shown in Figure 1(a), while the sink can recover 6 original data packets in 2 time slots (i.e., the achieved network throughput is $\mathrm{3}$ ) in the case shown in Figure 1(b). Obviously, the LNC scheme based on the average number of path failures can significantly improve the network throughput.

In this paper, we will design an efficient LNC scheme based on the average number of path failures, to provide reliable communication in WSNs. It must be noted that our study in this paper is different to our previous work in [21], where we have investigated the LNC design for providing $N+k$ protection in the wireless mesh networks. Specifically, as we can see from the rest of the paper, the main differences include the following.

Firstly, different LNC designs are given to provide reliable communication in this paper. The deterministic LNC scheme proposed in Section 3 achieves the network throughput $N=L-\lceil f_{\exp \hspace{0.17em}}\rceil$ (L denotes the number of edge-disjoint paths between the source and the destination and $f_{\exp \hspace{0.17em}}$ is the expected number of path failures per time slot), while the LNC scheme proposed in [21] does not ensure that the network throughput can achieve $N=L-\lceil f_{\exp \hspace{0.17em}}\rceil$ . Therefore, the deterministic LNC scheme proposed in this paper can achieve higher network throughput than our previous work in [21]. Moreover, in this paper, we also investigate the potential of standard random LNC to thwart path failures in WSNs and analyze the lower bound of the probability that a random LNC can provide reliable communication. On the other hand, the work in [21] only considered the deterministic LNC design.

Secondly, comparing with the work in [21], we not only give the theoretical design of deterministic LNC scheme and random LNC scheme but also conduct considerable simulations with four parameters to demonstrate the effectiveness of the proposed LNC schemes, from view of both network throughput and recovery delay. We also show the impact of the size of finite field on the performance of the proposed random LNC schemes, which is not investigated in [21].

The rest of the paper is organized as follows. Section 2 describes the system models and problem description. In Section 3, we design a deterministic LNC scheme to provide reliable communication in WSNs and give the theoretically analysis to show the achieved network throughput. The analysis of the usage of random LNC to realize reliable communication in WSNs is shown in Section 4. Simulation results are given in Section 5. Finally, we conclude the paper in Section 6.

2. Reliable Communication against Multiple Failures in WSNs Based on LNC

In this section, we will describe the problem studied in this paper. Specifically, we first introduce the network model. We then give the description of the reliable communication problem.

2.1. The Network Model

In this paper, we consider a multihop wireless sensor network as a directed acyclic graph $G=(V,E)$ , where V is the set of sensor nodes and E is the set of edges. We assume that each edge in G has the same unit capacity. Note that the capacity of different edges can be different in practice. However, we can always convert an edge with a certain capacity C (a nature number) data units to C edges with unit capacity. Suppose that all data packets have the same unit size. There are one source S, one destination D and L edge-disjoint paths between them. We assume that it will cost one time slot that the source sends L coded packets through L edge-disjoint paths and gets the feedback from the destination.

Although the wireless medium is vulnerable and the sensor node always faces energy exhaustion and physical damage, LNC can be designed to tolerate the link or node failures and provide reliable communications in WSNs. Specifically, L coded data packets are generated at the source node by linearly combining original data packets and transmitted through L edge-disjoint paths in each time slot. Since there will be different number of edge-disjoint paths failing simultaneously in different transmission rounds, we denote $p_i$ as the probability that i edge-disjoint paths are failed simultaneously, where $\mathrm{1}\le i\le L$ . Therefore, $f_{\exp \hspace{0.17em}}={\sum }_{i=\mathrm{1}}^L‍i{p}_i$ is the expected number of path failures per time slot. Let $N=L-\lceil f_{\exp \hspace{0.17em}}\rceil$ .

Suppose that the data stream arrive rate is N data packets per time slot; the data packets arrived are firstly buffered at the source S, waiting for encoding and transmission towards the destination D. We will design an LNC scheme to protect the data stream with arrive rate N.

2.2. The LNC Scheme

In practical LNC schemes, the source node first divides the whole file into fix-size original packets. Then, the coded packets can be generated by encoding the original packets together. Moreover, each coded packet in the network corresponds to an encoding vector, which consists of the coding coefficients that it is produced with respect to the set of original packets. When the destination node received sufficient coded packets, it can decode and recover the original packets according to their encoding vectors.

Due to the limited computational capability of the sensor nodes in WSNs, we assume that the intermediate sensor nodes simply store and forward encoding packets. Such assumption is practical because coding operations require extra computation capability which imposes the processing overheads and may slow down the switching speed.

2.3. Problem Description

To improve the network throughput, we design the LNC schemes based on the expected number of path failures per time slot ( $f_{\exp \hspace{0.17em}}$ ). However, since the number of path failures may exceed $f_{\exp \hspace{0.17em}}$ in some time slots, which may cause that the destination cannot decode the received coded data packets, it is desirable to utilize the redundant coded data packets transmitted in the transmission rounds with fewer failures ( $<f_{\exp \hspace{0.17em}}$ ) to improve the network throughput.

Therefore, in this paper, we aim to design an LNC scheme providing reliable communication in WSNs to achieve network throughput $N=L-\lceil f_{\exp \hspace{0.17em}}\rceil$ , in which $f_{\exp \hspace{0.17em}}$ is the expected number of path failures per time slot. We will show in the rest of the paper that the original data packets can be recovered by the destination and the network throughput N can be achieved, if only the average number of failures is no more than $f_{\exp \hspace{0.17em}}$ .

2.4. Notations

To facilitate further discussions, we summarize main notations to be used throughout the rest of the paper in Table 1. We also denote the $L\times iN$ dimensional matrix ${\mathrm{\Lambda }}_i$ as follows:

$$\begin{array}{cc}& {\mathrm{\Lambda }}_i=\left(\begin{array}{ccccc}\mathrm{1}& {\lambda }_{\left(i-\mathrm{1}\right)L+\mathrm{1}}& {\lambda }_{\left(i-\mathrm{1}\right)L+\mathrm{1}}^{\mathrm{2}}& \cdots & {\lambda }_{\left(i-\mathrm{1}\right)L+\mathrm{1}}^{i*N-\mathrm{1}}\\ \mathrm{1}& {\lambda }_{\left(i-\mathrm{1}\right)L+\mathrm{2}}& {\lambda }_{\left(i-\mathrm{1}\right)L+\mathrm{2}}^{\mathrm{2}}& \cdots & {\lambda }_{\left(i-\mathrm{1}\right)L+\mathrm{2}}^{i*N-\mathrm{1}}\\ & \cdots & & & \\ \mathrm{1}& {\lambda }_{iL}& {\lambda }_{iL}^{\mathrm{2}}& \cdots & {\lambda }_{iL}^{i*N-\mathrm{1}}\end{array}\right),\end{array}$$

(1)

where ${\lambda }_{i_{\mathrm{1}}}\ne {\lambda }_{i_{\mathrm{2}}}$ , for all $i_{\mathrm{1}}\ne i_{\mathrm{2}}$ .

Table 1

Symbol	Definition
Bold font	Vectors, matrixes
Normal font	A normal number
${𝔽}_q$	A finite field of size q, over which the LNC is defined
${\{\mathit{B}\}}_i^j$	A set of vector composed by $i_{th}$ to $j_{th}$ row vectors of matrix B
${\left[\mathit{B}\right]}_{i,j}^{m,n}$	A matrix composed by the $i_{th}$ to $j_{th}$ row and $m_{th}$ to $n_{th}$ column of matrix B
${\left[\mathit{B}\right]}_i$	The $i_{th}$ row vector of matrix B
${\left[\mathit{B}\right]}_{i,j}$	The matrix composed by the $i_{th}$ to $j_{th}$ row vectors of matrix B
$\text{[}\mathit{V}\text{]}$	The matrix formed by vectors in the set V as its rows
Rank (B)	The rank of a matrix B
${\mathit{m}}_{i,j}$	The $j_{th},j\le N$ original data packet arrived at time slot i
${\mathit{M}}_i$	N original data packets ${\mathit{M}}_i=\{{\mathit{m}}_{i,1},\dots ,{\mathit{m}}_{i,N}\}$ arrived at time slot i
L	The number of edge-disjoint paths between the source and the destination
${\mathit{0}}_{m\times n}$	A $m\times n$ dimensional zero matrix
N	$N=L-\lceil f_{\exp \hspace{0.17em}}\rceil$ , in which $f_{\exp \hspace{0.17em}}$ is the expected number of path failures per time slot
Span (·)	Linear span of a set of row vectors of a matrix
Dim (·)	Dimension of a linear space
P(A)	The probability that condition A is satisfied

3. Reliable Communication Using Deterministic Linear Network Coding

In this section, we provide a deterministic LNC scheme to provide reliable communication (RDLC) for multiple failures in WSNs.

We assume that a buffer exists in the source to buffer the newly arrived data packets and parts of original data packets arrived previously. We also assume that the destination has a buffer to buffer the coded data packets which have not been decoded. At the end of each time slot, the destination sends an acknowledgment to the source in order to report the number of coded data packets received in this time slot. Then, according to the number of coded data packets received by the destination in the previously time slots, the source first removes some original data packets arrived perviously in its buffer and then generates L new coded data packets by encoding the original data packets arrived previously and the newly arrived data packets together. After that, the source sends the L new coded data packets to the destination. At the end of time slot t, for  all $t\ge \mathrm{1}$ , if the destination has totally received no less $tN$ coded data packet, it can decode and recover the $tN$ original data packets, clear its buffer and send an acknowledgment to notify the source that all the received coded data packets are decoded.

We denote the N original packets arrived at time slot t as ${\mathbf{M}}_t=\{{\mathbf{m}}_{t,\mathrm{1}},\dots ,{\mathbf{m}}_{t,N}\}$ . The details of RDLC scheme is shown in Algorithms 1 and 2.

Algorithm 1: Encoding at the source.

At time slott:

N original data packets ${\mathit{M}}_t=\{{\mathit{m}}_{t,1},\dots ,{\mathit{m}}_{t,N}\}$ are arrived and stored into its buffer;

if  t = 1 then

 Generate L coded packets: ${\mathrm{\Lambda }}_1[{\mathit{M}}_1]$ and send them to the destination through L edge-disjoint paths;

end  if

if  t > 1 then

 Receives $ACK(c_{t-1}$ ) from the destination;

 if   $c_{t-1}=-1$   then

  Clear the buffer, set $t=1$ and get ready for a new transmission round;

 else

  Remove the $c_{t-1}$ earliest arrived data packets in the buffer;

  Generate L coded data packets:

   $\left[\begin{array}{c}{\mathit{m}}_{t,1}^{\prime }\\ ⋮\\ {\mathit{m}}_{t,L}^{\prime }\end{array}\right]=[{\mathit{0}}_{L\times {\sum }_{i=1}^{t-1}{c}_i}\hspace{1em}{[{\mathrm{\Lambda }}_t]}_{1,L}^{1,tN-{\sum }_{i=1}^{t-1}{c}_i}]\left[\begin{array}{c}[{\mathit{M}}_1]\\ ⋮\\ {[\mathit{M}}_t]\end{array}\right]$

  Send each coded packet ${\mathit{m}}_{t,i}^{\prime }$ with encoding vector

   ${\mathbf{v}}_{t,i}={[{\mathit{0}}_{L\times {\sum }_{i=1}^{t-1}{c}_i}\hspace{1em}{[{\mathrm{\Lambda }}_t]}_{1,L}^{1,tN-{\sum }_{i=1}^{t-1}{c}_i}]}_i$ through path i to the receiver, $\forall i\in \{1,\dots ,L\}$ ;

 end  if

end  if

Algorithm 2: Decoding at the destination.

At time slott:

Received $c_t$ coded data packet in time slot t;

If   ${\sum }_{i=1}^t{c}_i\ge tN$   then

 Extend each received encoding vector ${\mathit{v}}_{i,j}$ to its corresponding global encoding vector ${\mathit{v}}_{i,j}^{\prime }$ with length tN by adding $(t-i)N$ zeros, i.e., ${\mathit{v}}_{i,j}^{\prime }=[{\mathit{v}}_{i,j}\hspace{1em}{\mathit{0}}_{1\times (t-i)N}]$ ;

 Suppose that the matrix ${\mathit{Y}}_T$ is composed by the global encoding vectors of the received TN coded packets as its rows and the matrix ${\mathit{M}}^{\prime }$ is composed by corresponding coded packets as its rows;

 Decode and recover the tN original data packets as follows:

  $\left[\begin{array}{c}[{\mathit{M}}_{\mathrm{1}}]\\ ⋮\\ [{\mathit{M}}_t]\end{array}\right]={\mathit{Y}}_T^{-\mathrm{1}}{\mathit{M}}^{\prime }$ ;

 Clear the its buffer and send a $ACK(-1)$ to the source;

else

 Store the $c_t$ coded data packet to its buffer;

 Send a $ACK(c_t)$ to the source;

end  if

Suppose that $c_t$ denotes the number of coded data packets received by the destination at the end of time slot t; we have $c_t\le L$ , for all $t>\mathrm{0}$ . Let

$$\begin{array}{cc}& T=\underset{t:t>\mathrm{0}}{\min \hspace{0.17em}}\left\{t\mid {\sum }_{i=\mathrm{1}}^t‍c_i\ge tN\right\}.\end{array}$$

(2)

Next, we will prove that the destination can decode and recover the $TN$ original data packets once it receives no less than $TN$ coded data packets.

Lemma 1.

When $T=\mathrm{1}$ , the destination can decode and recover the N original data packets.

Proof.

When $T=\mathrm{1}$ , the destination can receive $c_{\mathrm{1}}\ge N$ coded data packets. The global encoding vector of each coded data packets is one row vector in the matrix ${\mathrm{\Lambda }}_{\mathrm{1}}$ . According to the matrix ${\mathrm{\Lambda }}_{\mathrm{1}}$ , any N rows can construct a square $N\times N$ dimensional Vandermonde matrix. Since ${\lambda }_i\ne {\lambda }_j$ , for all $i\ne j$ , the determinant of the $N\times N$ dimensional Vandermonde matrix is not equal to 0. Hence, the destination receives N coded data packets with N linearly independent global encoding vectors. Therefore, the destination can decode and recover the N original data packets.

Lemma 2.

When $T=\mathrm{2}$ , the destination can decode and recover the $\mathrm{2}N$ original data packets.

Proof.

When $T=\mathrm{2}$ , the destination receives no less than $\mathrm{2}N$ coded data packets. We suppose that it receives $c_{\mathrm{1}}$ coded data packets in time slot 1. Without loss of generality, let these coded data packets be $[{\mathrm{\Lambda }}_{\mathrm{1}}{]}_{\mathrm{1},c_{\mathrm{1}}}^{\mathrm{1},N}[{\mathbf{M}}_{\mathrm{1}}]$ . Since the destination receives no less than $\mathrm{2}N$ coded data packets we can select $\mathrm{2}N-c_{\mathrm{1}}$ coded data packets received by the destination in time slot 2. Without loss of generality, let these coded data packets be $[{\mathbf{0}}_{c_{\mathrm{2}}\times c_{\mathrm{1}}}\hspace{0.17em}\hspace{0.17em}[{\mathrm{\Lambda }}_{\mathrm{2}}{]}_{\mathrm{1},c_{\mathrm{2}}}^{\mathrm{1,2}N-c_{\mathrm{1}}}]\left[\begin{array}{c}[{\mathbf{M}}_{\mathrm{1}}]\\ [{\mathbf{M}}_{\mathrm{2}}]\end{array}\right]$ . Therefore, the matrix ${\mathbf{Y}}_{\mathrm{2}}$ composed by global encoding vectors of the coded packets as its rows can be represented by

$$\begin{array}{cc}& {\mathbf{Y}}_{\mathrm{2}}=\left[\begin{array}{ccc}{\left[{\mathrm{\Lambda }}_{\mathrm{1}}\right]}_{\mathrm{1},c_{\mathrm{1}}}^{\mathrm{1},c_{\mathrm{1}}}& {\left[{\mathrm{\Lambda }}_{\mathrm{1}}\right]}_{\mathrm{1},c_{\mathrm{1}}}^{c_{\mathrm{1}}+\mathrm{1},N}& \mathbf{0}\\ \mathbf{0}& {\left[{\mathrm{\Lambda }}_{\mathrm{2}}\right]}_{\mathrm{1,2}N-c_{\mathrm{1}}}^{\mathrm{1},N-c_{\mathrm{1}}}& {\left[{\mathrm{\Lambda }}_{\mathrm{2}}\right]}_{\mathrm{1,2}N-c_{\mathrm{1}}}^{N-c_{\mathrm{1}}+\mathrm{1,2}N-c_{\mathrm{1}}}\end{array}\right].\end{array}$$

(3)

Next, we will prove that $\text{Rank}({\mathbf{Y}}_{\mathrm{2}})=\mathrm{2}N$ . If $c_{\mathrm{1}}=\mathrm{0}$ , then $c_{\mathrm{1}}+c_{\mathrm{2}}=c_{\mathrm{2}}\ge \mathrm{2}N$ . We have $\det \hspace{0.17em}({\mathbf{Y}}_{\mathrm{2}})=\det \hspace{0.17em}([{\mathrm{\Lambda }}_{\mathrm{2}}{]}_{\mathrm{1,2}N}^{\mathrm{1,2}N})\ne \mathrm{0}$ because $[{\mathrm{\Lambda }}_{\mathrm{2}}{]}_{\mathrm{1,2}N}^{\mathrm{1,2}N}$ is a $\mathrm{2}N\times \mathrm{2}N$ dimensional Vandermonde matrix. Otherwise, if $c_{\mathrm{1}}>\mathrm{0}$ , obviously, the block matrix $[{\mathrm{\Lambda }}_{\mathrm{1}}{]}_{\mathrm{1},c_{\mathrm{1}}}^{\mathrm{1},c_{\mathrm{1}}}$ in the left upper corner of the matrix ${\mathbf{Y}}_{\mathrm{2}}$ is $c_{\mathrm{1}}\times c_{\mathrm{1}}$ dimensional and has full rank. Therefore, each column vector in $[{\mathrm{\Lambda }}_{\mathrm{1}}{]}_{\mathrm{1},c_{\mathrm{1}}}^{c_{\mathrm{1}}+\mathrm{1},N}$ can be written as a linear combination of the column vectors in $[{\mathrm{\Lambda }}_{\mathrm{1}}{]}_{\mathrm{1},c_{\mathrm{1}}}^{\mathrm{1},c_{\mathrm{1}}}$ . Since the $(\mathrm{2}N-c_{\mathrm{1}})\times c_{\mathrm{1}}$ dimensional block matrix in the left lower corner of the matrix ${\mathbf{Y}}_{\mathrm{2}}$ is zero matrix, the matrix ${\mathbf{Y}}_{\mathrm{2}}$ can be transformed to be matrix ${\mathbf{Y}}_{\mathrm{2}}^{\prime }$ by column transformation:

$$\begin{array}{l}{\mathbf{Y}}_{\mathrm{2}}^{\prime }=\left[\begin{array}{lll}{\left[{\mathrm{\Lambda }}_{\mathrm{1}}\right]}_{\mathrm{1},c_{\mathrm{1}}}^{\mathrm{1},c_{\mathrm{1}}}& \mathbf{0}& \mathbf{0}\\ \mathbf{0}& {\left[{\mathrm{\Lambda }}_{\mathrm{2}}\right]}_{\mathrm{1,2}N-c_{\mathrm{1}}}^{\mathrm{1},N-c_{\mathrm{1}}}& {\left[{\mathrm{\Lambda }}_{\mathrm{2}}\right]}_{\mathrm{1,2}N-c_{\mathrm{1}}}^{N-c_{\mathrm{1}}+\mathrm{1,2}N-c_{\mathrm{1}}}\end{array}\right]\\ \hspace{1em}\hspace{0.17em}=\left[\begin{array}{ll}{\left[{\mathrm{\Lambda }}_{\mathrm{1}}\right]}_{\mathrm{1},c_{\mathrm{1}}}^{\mathrm{1},c_{\mathrm{1}}}& \mathbf{0}\\ \mathbf{0}& {\left[{\mathrm{\Lambda }}_{\mathrm{2}}\right]}_{\mathrm{1,2}N-c_{\mathrm{1}}}^{\mathrm{1,2}N-c_{\mathrm{1}}}\end{array}\right],\end{array}$$

(4)

and $\det \hspace{0.17em}({\mathbf{Y}}_{\mathrm{2}})=\det \hspace{0.17em}({\mathbf{Y}}_{\mathrm{2}}^{\prime })$ .

We have

$$\begin{array}{l}\det \hspace{0.17em}\left({\mathbf{Y}}_{\mathrm{2}}\right)=\det \hspace{0.17em}\left(\left[\begin{array}{ll}{\left[{\mathrm{\Lambda }}_{\mathrm{1}}\right]}_{\mathrm{1},c_{\mathrm{1}}}^{\mathrm{1},c_{\mathrm{1}}}& \mathbf{0}\\ \mathbf{0}& {\left[{\mathrm{\Lambda }}_{\mathrm{2}}\right]}_{\mathrm{1,2}N-c_{\mathrm{1}}}^{\mathrm{1,2}N-c_{\mathrm{1}}}\end{array}\right]\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}=\det \hspace{0.17em}\left({\left[{\mathrm{\Lambda }}_{\mathrm{1}}\right]}_{\mathrm{1},c_{\mathrm{1}}}^{\mathrm{1},c_{\mathrm{1}}}\right)\det \hspace{0.17em}\left({\left[{\mathrm{\Lambda }}_{\mathrm{2}}\right]}_{\mathrm{1,2}N-c_{\mathrm{1}}}^{\mathrm{1,2}N-c_{\mathrm{1}}}\right).\end{array}$$

(5)

Since the block matrix $[{\mathrm{\Lambda }}_{\mathrm{1}}{]}_{\mathrm{1},c_{\mathrm{1}}}^{\mathrm{1},c_{\mathrm{1}}}$ is a $c_{\mathrm{1}}\times c_{\mathrm{1}}$ dimensional Vandermonde matrix, $[{\mathrm{\Lambda }}_{\mathrm{2}}{]}_{\mathrm{1,2}N-c_{\mathrm{1}}}^{\mathrm{1,2}N-c_{\mathrm{1}}}$ is a $(\mathrm{2}N-c_{\mathrm{1}})\times (\mathrm{2}N-c_{\mathrm{1}})$ dimensional Vandermonde matrix and $x_i\ne x_j$ , for all $i\ne j$ , we have $\det \hspace{0.17em}([{\mathrm{\Lambda }}_{\mathrm{1}}{]}_{\mathrm{1},c_{\mathrm{1}}}^{\mathrm{1},c_{\mathrm{1}}})\ne \mathrm{0}$ and $\det \hspace{0.17em}([{\mathrm{\Lambda }}_{\mathrm{2}}{]}_{\mathrm{1,2}N-c_{\mathrm{1}}}^{\mathrm{1,2}N-c_{\mathrm{1}}})\ne \mathrm{0}$ .

Therefore, we have $\det \hspace{0.17em}({\mathbf{Y}}_{\mathrm{2}})\ne \mathrm{0}$ , which indicates that $\text{Rank}({\mathbf{Y}}_{\mathrm{2}})=\mathrm{2}N$ , that is, when $i=\mathrm{2}$ , the destination can decode and recover the original data packets if it receives no less than $\mathrm{2}N$ coded data packets.

Theorem 3.

The destination can decode and recover the $TN$ original data packets as long as it totally receives no less than $TN$ coded data packets at the end of T time slots.

Proof .

According to Lemmas 1 and 2, the theorem holds when $T=\mathrm{1,2}$ . When $T=t+\mathrm{1},t>\mathrm{1}$ , it means that ${\sum }_{i=\mathrm{1}}^j‍c_i<jN$ , for all $j\le t$ and ${\sum }_{i=\mathrm{1}}^{t+\mathrm{1}}‍c_i\ge (t+\mathrm{1})N$ . When ${\sum }_{i=\mathrm{1}}^{t+\mathrm{1}}‍c_i=(t+\mathrm{1})N$ , that is, $c_T=TN-{\sum }_{i=\mathrm{1}}^t‍c_i$ , without loss of generality, let these coded data packets be

$$\begin{array}{cc}& \left[\begin{array}{cc}{\mathbf{0}}_{c_t\times {\sum }_{i=\mathrm{1}}^{t-\mathrm{1}}‍c_i}& {\left[{\mathrm{\Lambda }}_t\right]}_{\mathrm{1},c_t}^{\mathrm{1},tN-{\sum }_{i=\mathrm{1}}^{t-\mathrm{1}}‍}\end{array}\right]\left[\begin{array}{c}\left[{\mathbf{M}}_{\mathrm{1}}\right]\\ ⋮\\ \left[{\mathbf{M}}_t\right]\end{array}\right].\end{array}$$

(6)

The matrix ${\mathbf{Y}}_T$ composed by the global encoding vectors of these $TN$ coded packets as its rows can be represented by

$$\begin{array}{cc}& \left[\begin{array}{ccccc}{\left[{\mathrm{\Lambda }}_{\mathrm{1}}\right]}_{\mathrm{1},c_{\mathrm{1}}}^{\mathrm{1},c_{\mathrm{1}}}& *& \cdots & *& *\\ \mathbf{0}& {\left[{\mathrm{\Lambda }}_{\mathrm{2}}\right]}_{\mathrm{1},c_{\mathrm{2}}}^{\mathrm{1},c_{\mathrm{2}}}& \cdots & *& *\\ & & \cdots & \ddots & \\ \mathbf{0}& \mathbf{0}& \cdots & \mathbf{0}& {\left[{\mathrm{\Lambda }}_T\right]}_{\mathrm{1},c_T}^{\mathrm{1},\left(t+\mathrm{1}\right)N-{\sum }_{i=\mathrm{1}}^t‍c_i}\end{array}\right].\end{array}$$

(7)

Similarly to the proof of Lemma 2, the block matrix $[{\mathrm{\Lambda }}_{\mathrm{1}}{]}_{\mathrm{1},c_{\mathrm{1}}}^{\mathrm{1},c_{\mathrm{1}}}$ in the left upper corner of the above matrix is $c_{\mathrm{1}}\times c_{\mathrm{1}}$ dimensional and has full rank. Therefore, each column vector in $[{\mathbf{Y}}_T{]}_{\mathrm{1},c_{\mathrm{1}}}^{c_{\mathrm{1}}+\mathrm{1},TN}$ can be written as a linear combination of the column vectors in $[{\mathrm{\Lambda }}_{\mathrm{1}}{]}_{\mathrm{1},c_{\mathrm{1}}}^{\mathrm{1},c_{\mathrm{1}}}$ . Since the $(TN-c_{\mathrm{1}})\times c_{\mathrm{1}}$ dimensional block matrix in the left lower corner of the matrix ${\mathbf{Y}}_T$ is zero matrix, the elements in between $\mathrm{1}$ to $c_{\mathrm{1}}$ row and $c_{\mathrm{1}}+\mathrm{1}$ to $TN-c_{\mathrm{1}}$ will be transformed to zeros in matrix ${\mathbf{Y}}_T$ by column transformation. And then by using the full rank block matrix $[{\mathrm{\Lambda }}_{\mathrm{2}}{]}_{\mathrm{1},c_{\mathrm{2}}}^{\mathrm{1},c_{\mathrm{2}}}$ , the elements in between $c_{\mathrm{1}}+\mathrm{1}$ to $c_{\mathrm{1}}+c_{\mathrm{2}}$ row and $c_{\mathrm{1}}+c_{\mathrm{2}}+\mathrm{1}$ to $TN-c_{\mathrm{1}}$ will be transformed to zeros in matrix ${\mathbf{Y}}_T$ by column transformation.

By step to step column transformation, the matrix ${\mathbf{Y}}_T$ can be finally transformed to be ${\mathbf{Y}}_T^{\prime }$ :

$$\begin{array}{cc}& \left[\begin{array}{ccccc}{\left[{\mathrm{\Lambda }}_{\mathrm{1}}\right]}_{\mathrm{1},c_{\mathrm{1}}}^{\mathrm{1},c_{\mathrm{1}}}& \mathbf{0}& \cdots & \mathbf{0}& \mathbf{0}\\ \mathbf{0}& {\left[{\mathrm{\Lambda }}_{\mathrm{2}}\right]}_{\mathrm{1},c_{\mathrm{2}}}^{\mathrm{1},c_{\mathrm{2}}}& \cdots & \mathbf{0}& \mathbf{0}\\ & & \cdots & \ddots & \\ \mathbf{0}& \mathbf{0}& \cdots & \mathbf{0}& {\left[{\mathrm{\Lambda }}_T\right]}_{\mathrm{1},c_T}^{\mathrm{1},\left(t+\mathrm{1}\right)N-{\sum }_{i=\mathrm{1}}^t‍c_i}\end{array}\right].\end{array}$$

(8)

Obviously, $\det \hspace{0.17em}({\mathbf{Y}}_T^{\prime })={\prod }_{i=\mathrm{1}}^T‍\det \hspace{0.17em}([{\mathrm{\Lambda }}_i{]}_{\mathrm{1},c_i}^{\mathrm{1},c_i})$ . Since each matrix $[{\mathrm{\Lambda }}_i{]}_{\mathrm{1},c_i}^{\mathrm{1},c_i}$ is a square Vandermonde matrix and $x_i\ne x_j$ , for all $i\ne j$ , we have $\det \hspace{0.17em}([{\mathrm{\Lambda }}_i{]}_{\mathrm{1},c_i}^{\mathrm{1},c_i})\ne \mathrm{0}$ , for all $i\in \{\mathrm{1},\dots ,T\}$ . Therefore, $\det \hspace{0.17em}({\mathbf{Y}}_T^{\prime })\ne \mathrm{0}$ . Since the column transformation on a matrix does not change the rank of the matrix, the matrix ${\mathbf{Y}}_T$ has full rank, that is, the destination can decode and recover $TN$ organical packets.

When $c_T>TN-{\sum }_{i=\mathrm{1}}^t‍c_i$ , the destination can randomly select $TN-{\sum }_{i=\mathrm{1}}^t‍c_i$ coded data packets. Together with the ${\sum }_{i=\mathrm{1}}^t‍c_i$ coded packets received from time slot 1 to time slot t, the destination have $TN$ coded packets. Similarly to the above proof, we can have the destination that can decode and recover $TN$ original packets.

Corollary 4.

If the average number of path failures is no more than $f_{\exp \hspace{0.17em}}$ , then the network throughput $N=L-\lceil f_{\exp \hspace{0.17em}}\rceil$ can be achieved.

Proof.

When the average number of path failures is no more than $f_{\exp \hspace{0.17em}}$ , we have the average number of coded packets received by the destination in each time slot is $L-f_{\exp \hspace{0.17em}}$ . Therefore, there exists a time slot T that the destination totally receives $T(L-f_{\exp \hspace{0.17em}})$ coded data packets at the end of T time slots. Since $N=L-\lceil f_{\exp \hspace{0.17em}}\rceil <L-f_{\exp \hspace{0.17em}}$ , the destination totally receives $T(L-f_{\exp \hspace{0.17em}})>TN$ coded data packets at the end of T time slots. Therefore, according to Theorem 3, we have that the destination can decode and recover the $TN$ original data packets, that is, the network throughput $N=L-\lceil f_{\exp \hspace{0.17em}}\rceil$ is achieved.

4. Reliable Communication Using Random Linear Network Coding

In the previous section, we have discussed how to construct linear network code at the source node in a deterministic manner to provide the reliable communication. In practice, random linear coding has been widely used in the literature [15, 22], because of the simplicity of the coding scheme. With random linear coding, random linear combinations of the packets can be forwarded by a node, which the node received previously, to outgoing edges. It has been proved in pervious work that such a simple approach can obtain valid linear codes for multicast with probability $(\mathrm{1}-d/q{)}^{\eta }$ , where η is the number of edges with associated randomized coefficients, q is the size of the finite field, and d is the number of destination nodes.

In this section, we investigate the behavior of the random linear coding, when it is applied to the reliable communication problem we discuss in this paper. The usage of such linear code is similar to the one we discussed in Section 3. The coding operations are only done at the source node and destination node. The major difference is that, instead of computing the coding matrix ${\mathbf{Y}}_i$ at the source node, the elements of $L\times iN$ dimensional coding matrix ${\mathbf{B}}_i$ for time slot i are randomly chosen from the finite field ${𝔽}_q$ according to the number of coded packets received by the destination in each time slot. We referred to such random linear coding scheme as reliable random linear coding RRLC. Since the destination does not need to send an acknowledgment to notify the source that the number of coded packets received in each time slot, the communication overhead of RRLC, is smaller than the RDLC. We also show that the RRLC can ensure that the destination can recover the $iN$ original packets when it receives $iN$ coded packets with high probability.

Specifically, the L coded data packets sent during time slot i can be represented by

$$\begin{array}{cc}& {\mathbf{B}}_i\left[\begin{array}{c}\left[{\mathbf{M}}_{\mathrm{1}}\right]\\ ⋮\\ \left[{\mathbf{M}}_i\right]\end{array}\right].\end{array}$$

(9)

Suppose that the number of coded packets received within time slot i by the destination node d is $c_i$ , without loss of generality, let these coded data packets be

$$\begin{array}{cc}& {\left[{\mathbf{B}}_i\right]}_{\mathrm{1},c_i}\left[\begin{array}{c}\left[{\mathbf{M}}_{\mathrm{1}}\right]\\ ⋮\\ \left[{\mathbf{M}}_i\right]\end{array}\right].\end{array}$$

(10)

Suppose the $({\sum }_{w=\mathrm{1}}^i‍c_w)\times (iN)$ dimensional matrix ${\bar{\mathbf{B}}}_i$ is

$$\begin{array}{cc}& \left[\begin{array}{ccccc}{\left[{\mathbf{B}}_{\mathrm{1}}\right]}_{\mathrm{1},c_{\mathrm{1}}}& \mathrm{0}& 0& \cdots & 0\\ {\left[{\mathbf{B}}_{\mathrm{2}}\right]}_{\mathrm{1},c_{\mathrm{2}}}^{\mathrm{1},N}& {\left[{\mathbf{B}}_{\mathrm{2}}\right]}_{\mathrm{1},c_{\mathrm{2}}}^{N+\mathrm{1,2}N}& 0& \cdots & 0\\ & \cdots & \ddots & & \\ {\left[{\mathbf{B}}_i\right]}_{\mathrm{1},c_i}^{\mathrm{1},N}& {\left[{\mathbf{B}}_i\right]}_{\mathrm{1},c_i}^{N+\mathrm{1,2}N}& {\left[{\mathbf{B}}_i\right]}_{\mathrm{1},c_i}^{\mathrm{2}N+\mathrm{1,3}N}& \cdots & {\left[{\mathbf{B}}_i\right]}_{\mathrm{1},c_i}^{\left(i-\mathrm{1}\right)N+\mathrm{1},iN}\end{array}\right].\end{array}$$

(11)

Therefore, the total coded packets received by the destination node D during i time slots can be represented by

$$\begin{array}{cc}& {\bar{\mathbf{B}}}_i\left[\begin{array}{c}\left[{\mathbf{M}}_{\mathrm{1}}\right]\\ ⋮\\ \left[{\mathbf{M}}_i\right]\end{array}\right].\end{array}$$

(12)

From above theoretical analysis, the destination D can decode and recover the set of $iN$ original packets ${\bigcup }_{t=\mathrm{1}}^i‍{\mathbf{M}}_t$ , if and only if $\text{Rank}({\bar{\mathbf{B}}}_i)=iN$ .

Next, we will give the lower bound of the probability that the destination D can decode and recover the original packets once it totally receives no less than $iN$ coded packets after time slot i.

We set ${\sum }_{k=\mathrm{1}}^{\mathrm{0}}‍f(x)=\mathrm{0}$ and ${\prod }_{k=\mathrm{1}}^{\mathrm{0}}‍f(x)=\mathrm{1}$ , for all function $f(x)$ . We first prove a lemma.

Lemma 5.

If ${\sum }_{w=\mathrm{1}}^{i^{\prime }}‍c_w\le i^{\prime }N$ , for all $i^{\prime }\le i$ , the probability that the $({\sum }_{w=\mathrm{1}}^i‍c_w)\times (iN)$ dimensional matrix ${\bar{\mathbf{B}}}_i$ has full rank is

$$\begin{array}{cc}& \prod _{w=\mathrm{1}}^i\prod _{j={\sum }_{k=\mathrm{1}}^{w-\mathrm{1}}‍c_k+\mathrm{1}}^{{\sum }_{k=\mathrm{1}}^w‍c_k}\left(\mathrm{1}-\frac{\mathrm{1}}{q^{wn-j+\mathrm{1}}}\right).\end{array}$$

(13)

Proof.

Obviously, the matrix ${\bar{\mathbf{B}}}_i$ has full rank, if and only if

$$\begin{array}{cc}& {\left[{\bar{\mathbf{B}}}_i\right]}_j\notin \mathrm{Span}\hspace{0.17em}\left({\left[{\bar{\mathbf{B}}}_i\right]}_{\mathrm{1},j-\mathrm{1}}\right),\hspace{1em}\forall j\in \left\{\mathrm{1},\dots ,{\sum }_{w=\mathrm{1}}^i‍c_w\right\}.\end{array}$$

(14)

We first give the theoretical analysis on the first $c_{\mathrm{1}}$ row vectors in the matrix ${\bar{\mathbf{B}}}_i$ . Suppose that the first j, $(j\in \{\mathrm{1},\dots ,c_{\mathrm{1}}-\mathrm{1}\})$ rows of ${\bar{\mathbf{B}}}_i$ are selected and $[{\bar{\mathbf{B}}}_i{]}_{j^{\prime }}\notin \mathrm{Span}\hspace{0.17em}([{\bar{\mathbf{B}}}_i{]}_{\mathrm{1},j^{\prime }-\mathrm{1}})$ , for all $j^{\prime }\{\mathrm{1},\dots ,j\}$ , that is, $\text{Rank}([{\bar{\mathbf{B}}}_i{]}_{\mathrm{1},j})=j$ , for the $j+\mathrm{1}$ th row vector of the matrix ${\bar{\mathbf{B}}}_i$ , the total number different vectors can be selected from the finite filed is $q^N$ , because $[{\bar{\mathbf{B}}}_i{]}_{j+\mathrm{1}},\text{for\hspace{0.17em}\hspace{0.17em}all}\mathrm{\hspace{0.17em}\hspace{0.17em}}j\in \{\mathrm{1},\dots ,c_{\mathrm{1}}-\mathrm{1}\}$ that have the first N elements randomly selected in finite filed ${𝔽}_q$ and other elements are 0. Let ${\sigma }_{j+\mathrm{1}}$ be the number of vectors which can be selected as the $j+1$ th row vector of the matrix ${\bar{\mathbf{B}}}_i$ such that $[{\bar{\mathbf{B}}}_i{]}_{j+\mathrm{1}}\notin \mathrm{Span}\hspace{0.17em}([{\bar{\mathbf{B}}}_i{]}_{\mathrm{1},j})$ . The total number of vectors in $\mathrm{Span}\hspace{0.17em}([{\bar{\mathbf{B}}}_i{]}_{\mathrm{1},j})$ is $q^j$ . Therefore, if $[{\bar{\mathbf{B}}}_i{]}_{j+\mathrm{1}}\notin \mathrm{Span}\hspace{0.17em}([{\bar{\mathbf{B}}}_i{]}_{\mathrm{1},j})$ , we have ${\sigma }_{j+\mathrm{1}}=q^N-q^j$ .

Similarly, we then give the probability that the matrix ${\bar{\mathbf{B}}}_i$ has full rank.

Suppose that the first $j,(j\in \{{\sum }_{k=\mathrm{1}}^{w-\mathrm{1}}‍c_k+\mathrm{1},\dots ,{\sum }_{k=\mathrm{1}}^w‍c_k-\mathrm{1}\})$ rows of ${\bar{\mathbf{B}}}_i$ are selected and $[{\bar{\mathbf{B}}}_i{]}_{j^{\prime }}\notin \mathrm{Span}\hspace{0.17em}([{\bar{\mathbf{B}}}_i{]}_{\mathrm{1},j^{\prime }-\mathrm{1}})$ , for all $j^{\prime }\in \{\mathrm{1},\dots ,j\}$ , that is, $\text{Rank}([{\bar{\mathbf{B}}}_i{]}_{\mathrm{1},j})=j$ , for the $j+\mathrm{1}$ th row vector of the matrix ${\bar{\mathbf{B}}}_i$ , the total number different vectors can be selected from the finite filed which is $q^{wN}$ , because $[{\bar{\mathbf{B}}}_i{]}_{j+\mathrm{1}}$ for all $j\in \{{\sum }_{k=\mathrm{1}}^{w-\mathrm{1}}‍c_k+\mathrm{1},\dots ,{\sum }_{k=\mathrm{1}}^w‍c_k-\mathrm{1}\}$ have the first $wN$ elements randomly selected in finite filed ${𝔽}_q$ and other elements are 0. Let ${\sigma }_{j+\mathrm{1}}$ be the number of vectors which can be selected as the $j+\mathrm{1}$ th row vector of the matrix ${\bar{\mathbf{B}}}_i$ such that $[{\bar{\mathbf{B}}}_i{]}_{j+\mathrm{1}}\notin \mathrm{Span}\hspace{0.17em}([{\bar{\mathbf{B}}}_i{]}_{\mathrm{1},j})$ . The total number of vectors in $\mathrm{Span}\hspace{0.17em}([{\bar{\mathbf{B}}}_i{]}_{\mathrm{1},j})$ is $q^j$ . Therefore, if $[{\bar{\mathbf{B}}}_i{]}_{j+\mathrm{1}}\notin \mathrm{Span}\hspace{0.17em}([{\bar{\mathbf{B}}}_i{]}_{\mathrm{1},j})$ , we have ${\sigma }_{j+\mathrm{1}}=q^{wN}-q^j$ .

Let σ be the number of matrix ${\bar{\mathbf{B}}}_i$ that can be constructed in the finite field which satisfies the condition shown in (14). We have

$$\begin{array}{cc}& \sigma =\prod _{j=\mathrm{1}}^{{\sum }_{k=\mathrm{1}}^i‍c_k}{\sigma }_j=\prod _{w=\mathrm{1}}^i\prod _{j={\sum }_{k=\mathrm{1}}^{w-\mathrm{1}}‍c_k+\mathrm{1}}^{{\sum }_{k=\mathrm{1}}^w‍c_k}\left(q^{wN}-q^{j-\mathrm{1}}\right).\end{array}$$

(15)

The total number of different matrix ${\bar{\mathbf{B}}}_i$ with dimension $({\sum }_{k=\mathrm{1}}^i‍c_k)\times (iN)$ is $q^{{\sum }_{k=\mathrm{1}}^i‍k{c}_{k}N}$ , because there are ${\sum }_{k=\mathrm{1}}^i‍k{c}_{k}N$ elements randomly selected in finite filed ${𝔽}_q$ and other elements are 0 in matrix ${\bar{\mathbf{B}}}_i$ .

Therefore, the probability that the matrix ${\bar{\mathbf{B}}}_i$ has full rank is

$$\begin{array}{l}\frac{\sigma }{q^{{\sum }_{k=\mathrm{1}}^i‍k{c}_{k}N}}=\frac{{\prod }_{w=\mathrm{1}}^i‍{\prod }_{j={\sum }_{k=\mathrm{1}}^{w-\mathrm{1}}‍c_k+\mathrm{1}}^{{\sum }_{k=\mathrm{1}}^w‍c_k}‍\left(q^{wN}-q^{j-\mathrm{1}}\right)}{q^{{\sum }_{k=\mathrm{1}}^i‍k{c}_{k}N}}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}=\prod _{w=\mathrm{1}}^i\prod _{j={\sum }_{k=\mathrm{1}}^{w-\mathrm{1}}‍c_k+\mathrm{1}}^{{\sum }_{k=\mathrm{1}}^w‍c_k}\left(\mathrm{1}-\frac{\mathrm{1}}{q^{wN-j+\mathrm{1}}}\right).\end{array}$$

(16)

Theorem 6.

If the total number of coded packets received by destination d during the first i time slots is no less than $iN$ , that is, ${\sum }_{w=\mathrm{1}}^i‍c_w\ge iN$ and for all $i^{\prime }<i$ , ${\sum }_{w=\mathrm{1}}^{i^{\prime }}‍c_w<i^{\prime }N$ , the lower bound of the probability that can decode and recover the set of $iN$ original packets ${\bigcup }_{t=\mathrm{1}}^i‍{\mathbf{M}}_t$ is

$$\begin{array}{cc}& \prod _{w=\mathrm{1}}^i\prod _{j={\sum }_{k=\mathrm{1}}^{w-\mathrm{1}}‍c_k+\mathrm{1}}^{\min \hspace{0.17em}\left({\sum }_{k=\mathrm{1}}^w‍c_k,iN\right)}\left(\mathrm{1}-\frac{\mathrm{1}}{q^{wn-j+\mathrm{1}}}\right).\end{array}$$

(17)

Proof.

The destination node D can decode and recover the set of $iN$ original packets ${\bigcup }_{t=\mathrm{1}}^i‍{\mathbf{M}}_t$ , if and only if $\text{Rank}({\bar{\mathbf{B}}}_i)=iN$ . Since ${\sum }_{w=\mathrm{1}}^i‍c_w\ge iN$ and for all $i^{\prime }<i$ , ${\sum }_{w=\mathrm{1}}^{i^{\prime }}‍c_w<i^{\prime }N$ , we have $c_i\ge iN-{\sum }_{w=\mathrm{1}}^{i-\mathrm{1}}‍c_w$ . Obviously, if the first $iN$ row vectors are linearly independent, $\text{Rank}([{\bar{\mathit{B}}}_i{]}_{1,iN})=iN$ , we have $\text{Rank}({\bar{\mathbf{B}}}_i)=iN$ . Therefore, the probability that $\text{Rank}({\bar{\mathbf{B}}}_i)=iN$ is lower bounded by the probability that $\text{Rank}([{\bar{\mathbf{B}}}_i{]}_{\mathrm{1},iN})=iN$ . According to matrix $[{\bar{\mathbf{B}}}_i{]}_{\mathrm{1},iN}$ , the number of row vectors in it belonging to time slot i is $c_i^{\prime }=iN-{\sum }_{w=\mathrm{1}}^{i-\mathrm{1}}‍c_w$ . Therefore, from the Lemma 5, the probability that $\text{Rank}([{\bar{\mathbf{B}}}_i{]}_{\mathrm{1},iN})=iN$ is

$$\begin{array}{l}\frac{{\prod }_{w=\mathrm{1}}^{i-\mathrm{1}}‍{\prod }_{j={\sum }_{k=\mathrm{1}}^{w-\mathrm{1}}‍c_k+\mathrm{1}}^{{\sum }_{k=\mathrm{1}}^w‍c_k}‍\left(q^{wN}-q^{j-\mathrm{1}}\right){\prod }_{j={\sum }_{k=\mathrm{1}}^{i-\mathrm{1}}‍c_k+\mathrm{1}}^{iN}‍\left(q^{iN}-q^{j-\mathrm{1}}\right)}{q^{{\sum }_{k=\mathrm{1}}^{i-\mathrm{1}}‍k{c}_{k}N+\left(iN-{\sum }_{k=\mathrm{1}}^{i-\mathrm{1}}‍c_k\right)iN}}\\ \hspace{1em}=\prod _{w=\mathrm{1}}^i\prod _{j={\sum }_{k=\mathrm{1}}^{w-\mathrm{1}}‍c_k+\mathrm{1}}^{\min \hspace{0.17em}\left({\sum }_{k=\mathrm{1}}^w‍c_k,iN\right)}\left(\mathrm{1}-\frac{\mathrm{1}}{q^{wn-j+\mathrm{1}}}\right).\end{array}$$

(18)

Since the probability that $\text{Rank}({\bar{\mathbf{B}}}_i)=iN$ is lower bounded by the probability that $\text{Rank}([{\bar{\mathbf{B}}}_i{]}_{\mathrm{1},iN})=iN$ , the probability that $\text{Rank}({\bar{\mathbf{B}}}_i)=iN$ is large than

$$\begin{array}{cc}& \prod _{w=\mathrm{1}}^i\prod _{j={\sum }_{k=\mathrm{1}}^{w-\mathrm{1}}‍c_k+\mathrm{1}}^{\min \hspace{0.17em}\left({\sum }_{k=\mathrm{1}}^w‍c_k,iN\right)}\left(\mathrm{1}-\frac{\mathrm{1}}{q^{wn-j+\mathrm{1}}}\right).\end{array}$$

(19)

5. Performance Evaluation

In this section, we conduct simulations to compare the scheme that without considering reliable communication (denoted as Unreliable Communication Scheme) the linear coding schemes are designed for recovering from maximum number of edge failures and the proposed linear coding schemes.

In the transmission scheme without network protection, the source sent totally L original packets along the L paths between the source node and the destination node in each time slot, until the destination node receive all the L original packets. Since each path may fail in each time slot, the destination may wait for some time slots to receive all the L original packets.

In the linear coding schemes designed for recovering from maximum number of edge failures, the scheme codes $L-f_{\max \hspace{0.17em}}$ original packets in each time slot and makes sure that the destination can decode all of them even if the maximum number of edge failures happens in one time slot (i.e., the worst case). However, such a scheme will waste lots of throughput of the network, because the number of edge failures probably is less than the maximum number of edge failures. We denote such schemes as LCW scheme.

Therefore, in our coding scheme, we code the packets sent in the pervious time slots with the new packets together which can fully utilize the available paths in the network to achieve higher throughput. To achieve this goal, in the proposed linear coding scheme, the destination receives coded packets instead original packets in each time slot which may not be decoded immediately. Therefore, the destination may wait for some time slots to receive enough coded packets to decode and recover all the original packets sent by the source node in the past time slots. However, we will show in this section that we can decrease a bit of throughput to achieve a much low decoding delay.

The objectives of the simulation conducted in this work are as follows.

• (i)

To compare the throughput achieved when using different schemes under different parameter settings. The throughput is referred to as the total number of original packets recovered (or reviewed) in the past time slots divided to the total number of time slots.

(ii)

To compare the recovery delay using different schemes under different parameter settings. The delay will cause by different schemes to receive (or decode and recover) all the original packets sent by the source node in the past time slots.

5.1. Simulation Setup

We have four parameters in our simulations.

• (i)

The number of paths between the source node and the destination node, L, which varies from 10 to 20.

(ii)

The maximum number of paths between the source node and the destination node which can simultaneously fail, $f_{\max \hspace{0.17em}}=\lfloor \alpha L\rfloor$ , in which α varies from 0.2 to 0.7.

(iii)

The number of original packets coded (or sent) in each time slots, N, which varies from 2 to $\lfloor L-F_{\max \hspace{0.17em}}/\mathrm{2}\rfloor -\mathrm{1}$ .

(iv)

The size of finite field, $q={\mathrm{2}}^r$ , in which r varies from 1 to 7.

In a network G, we suppose that there are L edge-disjoint paths between the source node S and the destination node D. In each time slot, there may be $f^{\prime }$ , $\mathrm{0}\le f^{\prime }\le f_{\max \hspace{0.17em}}$ edges failure and the packets transmitted on these paths cannot be received by the destination node D. In the simulation, we randomly select $f^{\prime }$ in $\{\mathrm{0},\dots ,f_{\max \hspace{0.17em}}\}$ and then select $f^{\prime }$ paths in the L paths which will fail in the following one time slot.

For each combination of parameters L, $f_{\max \hspace{0.17em}}$ , N and q, we generate $\mathrm{100}$ instances. For each instance, we evaluate the performance of the data transmission using unreliable communication scheme, the linear coding schemes designed for recovering from maximum number of edge failures, and the proposed linear coding schemes.

5.2. Simulation Results

We compare the network throughput and the recovery delay of the proposed RDLC and RRLC schemes with LLW scheme and the unreliable communication scheme.

Firstly, in Figure 2, we set $q={\mathrm{2}}^{\mathrm{2}}$ , $\alpha =\mathrm{0.4}$ , $f_{\max \hspace{0.17em}}=\lfloor \alpha L\rfloor$ , $N=\lceil L-f_{\max \hspace{0.17em}}/\mathrm{2}\rceil -\mathrm{1}$ and vary L in the range of $[\mathrm{10,20}]$ .

Figure 2

$q={\mathrm{2}}^{\mathrm{2}}$ , $\alpha =\mathrm{0.4}$ , $f_{\max \hspace{0.17em}}=\lfloor \alpha L\rfloor$ , $N=\lceil L-f_{\max \hspace{0.17em}}/\mathrm{2}\rceil -\mathrm{1}$ .

In Figure 2(a), the throughput of all the four schemes increases with the increase of the number of edge-disjoint paths between the source node and the destination node. The reason is that the more the number of edge-disjoint paths exist between the source node and the destination node the more packets can be transmitted successfully to the destination. The throughput of the LLW scheme is higher than the unreliable communication scheme, because the LLW scheme exploits the LNC to ensure that all the original packets sent in one time slot can be recovered by the destination node which limit the number of original packets transmitted in each time slot. On the other hand, the unreliable communication scheme will transmit the same set of original packets many times to make sure the destination node can successfully receive all of them. The throughput of the proposed RDLC and RRLC schemes are much higher (more than $\mathrm{25}\%$ compared with LLW and more than $\mathrm{40}\%$ compared with the unreliable communication scheme when L grows sufficiently large), because the proposed schemes fully utilize the unfailed paths to transmit coded packets. Since the number of original packets transmitted in each time slot is the same in the proposed RDLC and RRLC schemes, the two schemes has the same throughput.

In Figure 2(b), the recovery delay of the unreliable communication scheme is higher than the other three schemes. The unreliable communication scheme will transmit the same set of original packets many times to make sure the destination node can successfully receive all of them. The recovery delay of the LLW scheme is always one time slot because a limited number of original packets are transmitted in each time slot to make sure the destination can decode and recover them in one time slot. The recovery delay of the proposed RDLC and RRLC schemes are between the unreliable communication scheme and the LLW scheme. Therefore, we can observe that the proposed RDLC and RRLC schemes can achieve highest throughput and moderate recovery delay. The figure also shows that the recovery delay of the RRLC scheme is higher than the recovery delay of the RDLC scheme. The reason is that according to the theoretical analysis a destination may not be decode and recover the original packets when using the RRLC scheme, even if it totally received more than $i*N$ coded packets during the past i time slots. Therefore, when using the RRLC scheme, the destination will wait more time slots to achieve the same throughput as the RDLC scheme.

Secondly, in Figure 3, we set $L=\mathrm{16}$ , $q={\mathrm{2}}^{\mathrm{2}}$ , $f_{\max \hspace{0.17em}}=\lfloor \alpha L\rfloor$ , $N=\lceil M-f_{\max \hspace{0.17em}}/\mathrm{2}\rceil -\mathrm{1}$ and vary α in the range of $[\mathrm{0.2,0.9}]$ .

Figure 3

$L=\mathrm{16}$ , $q={\mathrm{2}}^{\mathrm{2}}$ , $f_{\max \hspace{0.17em}}=\lfloor \alpha L\rfloor$ , $N=\lceil M-f_{\max \hspace{0.17em}}/\mathrm{2}\rceil -\mathrm{1}$ .

In Figure 3(a), the throughput of all the four schemes decreases with the increase of α, because the number of edge-disjoint paths between the source node and the destination node is fixed but the number of failure paths increases. We can observe that the throughput of LLW scheme will be lower than the unreliable communication scheme when α grows sufficiently large. The reason is that when α grows sufficiently large, the throughput of of LLW scheme $L-f_{\max \hspace{0.17em}}$ will decrease to zero, while the unreliable communication scheme can exploit unfailed paths to transmit packets. The throughput of the proposed RDLC and RRLC schemes are much higher (more than $\mathrm{60}\%$ compared with the unreliable communication scheme when α grows sufficiently large).

In Figure 3(b), the recovery delay of the proposed RDLC, RRLC schemes, and the unreliable communication scheme increase with the increase of α. Moreover, The recovery delay of the unreliable communication scheme is higher than the other three schemes. The recovery delay of the LLW scheme is always one time slot because a number of original packets transmitted in each time slot decreases when the α increase to make sure the destination can decode and recover them in one time slot.

Thirdly, in Figure 4, we set $L=\mathrm{16}$ , $q={\mathrm{2}}^{\mathrm{2}}$ , $\alpha =\mathrm{0.4}$ , $f_{\max \hspace{0.17em}}=\lfloor \alpha L\rfloor$ , $N<\lceil M-f_{\max \hspace{0.17em}}/\mathrm{2}\rceil$ .

Figure 4

$L=\mathrm{16}$ , $q={\mathrm{2}}^{\mathrm{2}}$ , $\alpha =\mathrm{0.4}$ , $f_{\max \hspace{0.17em}}=\lfloor \alpha L\rfloor$ , $N<\lceil M-f_{\max \hspace{0.17em}}/\mathrm{2}\rceil$ .

In Figure 4(a), the throughput of the proposed RDLC, RRLC schemes increases with the increase of N, because the throughput of the proposed RDLC, RRLC schemes can achieve N only if N is no more than the total number of paths minus the average number of path failures each time slot. In our simulation, the condition is that $N\le L-f_{\max \hspace{0.17em}}/2$ . Therefore, in Figure 4(a), the throughput of the proposed RDLC, RRLC schemes can achieve N. Obviously, N does not have impact on the throughput of the unreliable communication scheme and the LCW scheme. We can see in Figure 4(a) that the throughput of the proposed RDLC, RRLC schemes outperforms the other two schemes when N is sufficiently large.

Figure 4(b) shows that the values of N also do not have impact on the recovery delay of the unreliable communication scheme and the LCW scheme. On the other hand, the recovery delays of the proposed RDLC, RRLC schemes increase with the increase of achievable throughput. However, by selecting a suitable value of N, a transmission can achieve a higher throughput with a lower delay compared with the unreliable communication scheme and the LCW scheme.

Finally, in Figure 5, we set $L=\mathrm{16}$ , $\alpha =\mathrm{0.4}$ , $f_{\max \hspace{0.17em}}=\lfloor \alpha L\rfloor$ , $N=\lceil M-f_{\max \hspace{0.17em}}/\mathrm{2}\rceil -\mathrm{1}$ .

Figure 5

$L=\mathrm{16}$ , $\alpha =\mathrm{0.4}$ , $f_{\max \hspace{0.17em}}=\lfloor \alpha L\rfloor$ , $N=\lceil M-f_{\max \hspace{0.17em}}/\mathrm{2}\rceil -\mathrm{1}$ .

In Figure 5(a), the throughput of the proposed RDLC, RRLC schemes, the unreliable communication scheme, and the LCW scheme do not change because the throughput of them does not related with the size of the finite field. However, as we showed in Section 4, the size of the finite field has impact on the decoding probability that the destination to recovery the original packets when using the RRLC scheme. Therefore, the increase of the size of the finite field will increase the decoding probability and reduce the recovery delay. The trends of the recovery delay of the RRLC scheme shown in Figure 5(a) are consistent with our theoretical analysis. The recovery delay of the other three schemes does not related with the size of the finite field.

6. Conclusion

In this paper, we have explored the power of LNC to provide reliable communication for multiple failures in WSNs. The key idea is to design the LNC scheme based on average number of path failures, in which part of original data packets sent previously is still encoded into the following time slots, in order to improve the network throughput by utilizing the redundant coded data packets transmitted in the transmission rounds with fewer failures happening simultaneously in the WSN. Specifically, we first give the design of deterministic LNC scheme based on the average number of path failures, by which the network throughput is significantly improved comparing with the traditional approaches designed based on the maximum number of path failures. We also have investigated the behavior of the random LNC, when it is applied to the reliable communication problem studied in this paper. We have given the performance evaluation, which demonstrates the effectiveness of the proposed LNC schemes.