A Novel Energy-Efficient Reception Method Based on Random Network Coding in Cooperative Wireless Sensor Networks

Abstract

This paper presents an opportunistic reception (OR) algorithm for energy-efficient transmission in cooperative wireless sensor networks (WSNs), where the characteristics of random linear network coding and the energy consumption property of WSNs are jointly considered. In OR, the sensor nodes in intermediate cluster generate the independent coding vector through simple forwarding or decoding-recoding manners opportunistically, so that the number of received packets can be reduced. To evaluate the algorithm, we derive the average number of received packets, the transmitting nodes, and decoding failure probability under specific assumption. The obtained theoretical and simulation results verify the effectiveness offered by the proposed approach.

1. Introduction

Due to the wide range of applications, wireless sensor networks (WSNs) have attracted numerous research interests in recent years, such as target tracking [1], military surveillance [2], and environment monitoring [3]. In most cases, the sensor nodes in WSNs are equipped with low-complexity hardware and single antenna, which restrain their communication quality in wireless fading channels. Therefore, transmission reliability becomes one of the key issues in the applications of WSNs.

Cooperative communication (CC) [4] is one approach to improve transmission reliability of single-antenna devices. A transmitting node that uses CC can share its packet with neighboring nodes, and then these nodes can transmit the packet to the intended receiver cooperatively, thereby creating a virtual multiple-input-multiple-output (MIMO) system. The intended receiver can obtain diversity gains by combining the received signals, which brings a signal-to-noise ratio (SNR) advantage over the single-input-single-output (SISO) case. Several works have focused on the applications of CC in WSNs (cooperative WSNs); for example, Li et al. [5] proposed a space time block code- (STBC-) based cooperative scheme to improve the bit error rate (BER), while Cui et al. [6] employed CC to reduce the transmission energy of the sensor nodes. All these cooperative schemes require strict synchronization between the nodes; however, due to the inexpensive hardware and limited resources, strict synchronization is difficult to be realized in WSNs, which deteriorates the performance of CC [7].

On the other hand, by means of combining the incoming packets at intermediate nodes in the networks, network coding (NC) [8] brings a breakthrough to the transmission efficiency. As a class of NC, Li et al. demonstrated that the network throughput can achieve the max-flow-min-cut bound through linear network coding (LNC) [9]. Furthermore, Koetter and Médard [10] presented an algebraic framework to construct the NC coefficient for LNC. On the basis of that, random LNC (RLNC) [11–13] was proposed to reduce the complexity and make LNC to be deployed as the distributed manner. RLNC enables the intermediate nodes to select combination coefficient randomly from a Galois field of size q, while the incoming packets are also treated and combined as a vector over this field. In this way, RLNC provides a simple, yet effective, approach to improve the latency [14] and delay-tolerance [15] in wireless networks.

The distributed deployment and simplicity of RLNC loose the synchronization requirement, which makes it very suitable to be deployed in cooperative WSNs. Recent work [16] has employed RLNC to increase the redundancy of the original packets, so that the transmission reliability of the cooperative WSNs can be improved. In [16], the intermediate node tries to receive and combine all the incoming packets to construct its linear independent coding vector (CV). However, since the sensor nodes are usually deployed in hostile circumstances and powered by limited batteries, energy consumption [17, 18] is another important issue in cooperative WSNs. For popular sensor transceiver today, the receiving circuit energy consumption of a packet is even larger than the transmitting one, because decoding is a rather complex operation requiring a lot of computing power, which has been a big threat to the lifetime of the networks [19]. Therefore, it indicates that, for cooperative WSNs, not only transmission reliability [16] but also energy consumption characteristic should be taken into consideration in RLNC scheme design.

In this paper, we propose an opportunistic reception (OR) algorithm to reduce the received packets at the intermediate nodes. Different from the former work [16], by considering some characteristics of RLNC, our OR algorithm enables the intermediate sensor nodes to generate independent CV through simple forwarding or decode-and-select manners opportunistically. To examine its performance, the average number of received packets, the transmitting nodes, and decoding failure probability are derived under specific assumption. In this way, our study provides a trade-off between energy efficiency and transmission reliability for cooperative WSNs.

The remainder of this paper is organized as follows. Section 2 describes the system model. The proposed OR algorithm is presented in Section 3, and the corresponding performances are theoretically analyzed in Section 4. Simulation results are presented and compared for performance evaluation in Section 5. Finally, Section 6 concludes the paper.

2. System Model

We consider multihop clustered WSNs, in which a source node in the source cluster sends data to a sink with the aid of several intermediate clusters, as depicted in Figure 1. Each cluster is composed of n sensor nodes, and the operation of the system is broken into rounds. It is assumed that the source node has data to send in each round.

Figure 1

System model of cooperative WSNs.

The transmission round consists of four phases, as shown in Figure 2. Phase I is the intrasource cluster broadcasting, as shown in Figure 2(a); the source node splits the original data into m packets as $\mathbf{P}=(P_{\mathrm{1}},\dots ,P_k,\dots ,P_m{)}^T$ and then broadcasts it to the other nodes in the source cluster, named as $r_{Si}$ , $i=\mathrm{1},\dots ,n$ . It is assumed that the intracluster communication is error-free, so $r_{Si}$ randomly selects a $\mathrm{1}\times m$ CV ${\mathbf{V}}_{Si}=(V_{Si}^{(\mathrm{1})},\dots ,V_{Si}^{(k)},\dots ,V_{Si}^{(m)})$ and combines all the incoming packets to generate its data as

$$\begin{array}{cc}& P_{Si}={\mathbf{V}}_{Si}·\mathbf{P}.\end{array}$$

(1)

Note that $P_k$ , $V_{Si}^{(k)}$ , and $P_{Si}$ are the elements over Galois field of size q and $V_{Si}^{(k)}$ is randomly selected with probability $1/q$ .

Figure 2

Transmission procedure of cooperative WSNs.

Phase II is the source-intermediate cluster transmission, as depicted in Figure 2(b). In this phase, each $r_{Si}$ transmits its outgoing packet to the intermediate cluster in the next hop. Note that the outgoing packet encapsulates both CV ${\mathbf{V}}_{Si}$ and data $P_{Si}$ . Each sensor node in the intermediate cluster, named as $r_{Ii}$ , tries to receive all the packets [16] from the source cluster. After that, it recodes all the successfully received data as

$$\begin{array}{cc}& P_{Ii}={\mathbf{A}}_{Ii}·{\left[\dots ,P_{Sj},\dots ,P_{Sk}\right]}^T.\end{array}$$

(2)

${\mathbf{A}}_{Ii}=(\dots ,A_{Ii}^{(j)},\dots ,A_{Ii}^{(k)})$ is also a randomly selected L-length vector over Galois field, where L is the number of successfully received packets at $r_{Ii}$ . With (1), we rewrite the coded data $P_{Ii}$ as the product of a CV and P :

$$\begin{array}{cc}& P_{Ii}={\mathbf{V}}_{Ii}·\mathbf{P},\end{array}$$

(3)

where ${\mathbf{V}}_{Ii}={\mathbf{A}}_{Ii}·[\dots ,{\mathbf{V}}_{Sj}^T,\dots ,{\mathbf{V}}_{Sk}^T{]}^T$ . After that, each $r_{Ii}$ reencapsulates ${\mathbf{V}}_{Ii}$ and $P_{Ii}$ into its outgoing packet, and the recoding and reencapsulation procedure is shown in Figure 3.

Figure 3

Recoding and recapsulation procedure.

Phase III is the inter-intermediate clusters communications, as shown in Figure 2(c). In this phase, if $r_{Ii}$ fails to receive all the incoming packets in Phase II, it keeps silent. Otherwise, $r_{Ii}$ sends its recapsulated packet to the next cluster. The remaining intermediate clusters perform the operation in the same manner as the one in Figure 2(b), so the coded packets are delivered one by one, until the last cluster near the sink.

Phase IV is the decoding phase, in which the sink tries to receive all the packets from the last cluster nearby, as shown in Figure 2(d). We assume that

$$\begin{array}{cc}& {\mathbf{P}}_D={\left(P_{I^{\prime }\mathrm{1}},\dots ,P_{I^{\prime }k},\dots ,P_{I^{\prime }w}\right)}^T\end{array}$$

(4)

is the w received coded data, and

$$\begin{array}{cc}& {\mathbf{V}}_D={\left[{\mathbf{V}}_{I^{\prime }\mathrm{1}}^T\dots ,{\mathbf{V}}_{I^{\prime }k}^T,\dots ,{\mathbf{V}}_{I^{\prime }w}^T\right]}^T\end{array}$$

(5)

is the w received CVs, in which $P_{I^{\prime }k}$ and ${\mathbf{V}}_{I^{\prime }k}$ are extracted from the packet of $r_{I^{\prime }k}$ . Thus, (4) can be rewritten as

$$\begin{array}{cc}& {\mathbf{P}}_D={\mathbf{V}}_D·\mathbf{P},\end{array}$$

(6)

and if no less than m out of the CVs in ${\mathbf{V}}_D$ are linearly independent, the original data P can be recovered through Gaussian elimination [11]. Otherwise, the decoding failure occurs at sink.

3. Opportunistic Reception Algorithm

To facilitate the analysis, we simplify the above model to a two-hop one, which is the basic building block of more complex multihop networks. Firstly, according to the principle of RLNC [11], it should be confirmed that the only purpose of combining all the incoming packets at the sensor nodes [16] is nothing else but generating linearly independent CV. From this perspective, the linear combination in (3) can be replaced by the following two manners. (1) Forwarding: since ${\mathbf{V}}_{Si}$ and ${\mathbf{V}}_{Sj}$ are randomly selected by $r_{Si}$ and $r_{Sj}$ , $\forall i,j\in \{\mathrm{1},\dots ,n\}$ , $i\ne j$ , it is naturally guaranteed that they are linearly independent of each other at high probability; in other words, they can be directly employed as the CV of the sensor nodes in intermediate cluster. For example, $r_{I\mathrm{1}}$ and $r_{I\mathrm{2}}$ can simply forward the packets from $r_{S\mathrm{1}}$ and $r_{S\mathrm{2}}$ , respectively, without receiving and combining other packets anymore. (2) Decoding-recoding: if $r_{Ii}$ successfully receives m packets, the received data can be written as

$$\begin{array}{cc}& {\mathbf{P}}_I={\mathbf{V}}_S·\mathbf{P},\end{array}$$

(7)

in which

$$\begin{array}{cc}& {\mathbf{P}}_I={\left(P_{I\mathrm{1}},\dots ,P_{Ik},\dots ,P_{Im}\right)}^T,\\ {\mathbf{V}}_S={\left[{\mathbf{V}}_{S\mathrm{1}}^T,\dots ,{\mathbf{V}}_{Sk}^T,\dots ,{\mathbf{V}}_{Sm}^T\right]}^T.\end{array}$$

(8)

$r_{Ii}$ can decode P by solving (7), and, then, it locally recodes P as

$$\begin{array}{cc}& P_{Ii}={\mathbf{A}}_{Ii}·\mathbf{P}.\end{array}$$

(9)

In this way, $r_{Ii}$ successfully generates linearly independent CV while further reception is also avoided.

By considering the above two characteristics, we propose a reception algorithm for the nodes in intermediate cluster to reduce the received packets. Let $L_j$ be the number of successfully received packets at $r_{Ij}$ . ${\Phi }_U$ is the index set of the nodes which fail to generate independent CV, while ${\Phi }_{S\mathrm{1}}$ and ${\Phi }_{S\mathrm{2}}$ are those which generate independent CV due to forwarding and decoding-recoding, respectively. $F_j$ is the flag to identify whether $r_{Ij}$ is selected from ${\Phi }_{S\mathrm{1}}$ , through the value true or false. Thus, the pseudocode description of the proposed algorithm is presented in Algorithm 1.

Algorithm 1: OR algorithm.

Initialization: $${\mathrm{\Phi }}_{\mathrm{U}}=\{\mathrm{1},\dots ,n\},{\mathrm{\Phi }}_{\mathrm{S}\mathrm{1}}={\mathrm{\Phi }}_{\mathrm{S}\mathrm{2}}=\mathrm{⌀}$$ . $$L_j=\mathit{0}$$ , $$F_j$$ = true, $$\forall j\in {\mathrm{\Phi }}_{\mathrm{U}}$$ .

(1)   for   $$i=\mathit{1}$$ to n,

(2)   $$r_{\mathrm{S}i}$$ transmits its packet.

(3)   for   $$\forall j\in {\mathrm{\Phi }}_{\mathrm{U}}$$ ,

(4)       $$r_{\mathrm{I}j}$$ receives and updates $$L_j$$ .

(5)      if    $$L_j==\mathit{1}$$ && $$F_j=true$$ ,

(6)       j is removed from $${\mathrm{\Phi }}_{\mathrm{U}}$$ to $${\mathrm{\Phi }}_{\mathrm{S}\mathrm{1}}$$ .

(7)      elseif   $$L_j==m$$ && $$F_j=false$$ ,

(8)      j is removed from $${\mathrm{\Phi }}_{\mathrm{U}}$$ to $${\mathrm{\Phi }}_{\mathrm{S}\mathrm{2}}$$ .

(9)      end if

(10)  end for

(11)   Select an element w from $${\mathrm{\Phi }}_{\mathrm{S}\mathrm{1}}$$ with probability $$\mathrm{1}/|{\mathrm{\Phi }}_{\mathrm{S}\mathrm{1}}|$$ ,

(12)    $$r_{\mathrm{I}w}$$ forwards its received packet in Phase III,

(13)    $${\mathrm{\Phi }}_{\mathrm{S}\mathrm{1}}={\mathrm{\Phi }}_{\mathrm{S}\mathrm{1}}-\{w\}$$ .

(14)   for   $$\forall j\in {\mathrm{\Phi }}_{\mathrm{S}\mathrm{1}}$$ ,

(15)      $$F_j=false$$ , j is removed from $${\mathrm{\Phi }}_{\mathrm{S}\mathrm{1}}$$ to $${\mathrm{\Phi }}_{\mathrm{U}}$$ .

(16)  end for

(17)  for   $$\forall j\in {\mathrm{\Phi }}_{\mathrm{S}\mathrm{2}}$$ ,

(18)    $${\mathrm{\Phi }}_{\mathrm{S}\mathrm{2}}={\mathrm{\Phi }}_{\mathrm{S}\mathrm{2}}-\{j\}$$ ,

(19)     $$r_{\mathrm{I}j}$$ decodes and recodes P by (7) and (9),

(20)    $$r_{\mathrm{I}j}$$ transmits the packet in Phase III.

(21)  end for

(22) end for

We propose an example to illustrate the effectiveness of OR algorithm. As depicted in Figure 4, an OR process is presented when $m=2$ , $n=4$ . In Figure 4(a), $r_{S\mathrm{1}}$ successfully broadcasts its packet to all the nodes in intermediate cluster, except for $r_{I\mathrm{1}}$ , which experiences link failure. According to the reception state, $L_i$ is updated, $i=\mathrm{1,2},\mathrm{3,4}$ , while indexes 2, 3, and 4 are removed from ${\Phi }_U$ to ${\Phi }_{S\mathrm{1}}$ . Figure 4(b) depicts the node selection in ${\Phi }_{S\mathrm{1}}$ ; that is, one of the nodes in ${\Phi }_{S\mathrm{1}}$ is selected to generate its CV by the manner of forwarding. Here, we assume that index 3 is selected, so it is deleted while the others are removed from ${\Phi }_{S\mathrm{1}}$ to ${\Phi }_U$ . Besides, $r_{I\mathrm{3}}$ is ready to transmit and will not receive packets anymore. In Figure 4(c), $r_{S\mathrm{2}}$ broadcasts and all the nodes in intermediate cluster try to receive, except for $r_{\text{I}\mathrm{3}}$ . Similarly, $L_i$ is updated and index i is classified into ${\Phi }_{S\mathrm{1}}$ or ${\Phi }_{S\mathrm{2}}$ according to the rules of OR. In Figure 4(d), since index 1 is the only element of ${\Phi }_{S\mathrm{1}}$ , $r_{I\mathrm{1}}$ is selected to forward the packet of $r_{S\mathrm{2}}$ . Meanwhile, because ${\Phi }_{S\mathrm{2}}=\{\mathrm{2,4}\}$ , $r_{I\mathrm{2}}$ and $r_{I4}$ will generate their CVs by the decoding-recoding. Thus, all the nodes are ready to transmit, without further reception from $r_{S\mathrm{3}}$ and $r_{S\mathrm{4}}$ . In this example, $1+2\times 3=7$ packets are received in total. Comparing with $4\times 4=16$ packets by the manner of combination [16], the merit of OR is revealed.

Figure 4

An example of OR process.

4. Performance Analysis

To evaluate the performance of OR, we derive the mathematical expectation of the received packets, the transmitting nodes, and the decoding failure probability when $m=2$ , $n=4$ . (In fact, it is difficult to exhaust all the cases with large values of m and n. However, the low parameters do not influence the evaluation result of this paper. On the other hand, it has been proved in [20] that $m=2$ is optimal for NC and $n=4$ can also be used to describe the cluster with many nodes, in which 4 are alive while the others are asleep.) For simplicity, it is assumed that all incoming links at any sensor node exhibit the same value of failure probability P.

4.1. Mathematical Expectations of the Received Packets and Transmitting Nodes

In OR algorithm, $r_{Ij}$ is able to generate independent CV only in the following 2 cases: (1) index $j\in {\Phi }_{S\mathrm{1}}$ as well as j is selected from ${\Phi }_{S\mathrm{1}}$ ; (2) index $j\in {\Phi }_{S\mathrm{2}}$ . Let V and VV denote these two events, respectively, and we denote d as the number of the sensor nodes that generate independent CV. In this way, CV generation can be presented by a d-size vector which consists of V and VV. For example, (V, VV) represents the event that in total 2 sensor nodes generate independent CV through cases (1) and (2), respectively. Thus, all cases of CV generations can be described by such vectors, as shown in Table 1.

Table 1

All cases of CV generations.

d	Vector description
1	(V)
2	(V, V), (V, VV)
3	(V, V, V), (V, V, VV), (V, VV, VV)
4	(V, V, V, V), (V, V, V, VV), (V, V, VV, VV), (V, VV, VV, VV)

In Table 1, when $d=1$ , a possible sample of (V) can be written as (V₁, O, O, O). These 4 elements represent the reception situation of the 4 sensor nodes in intermediate cluster after Phase II, where V₁ denotes that a node successfully receives the packet from $r_{S\mathrm{1}}$ , while O represents that a node fails to receive all the incoming packets. To derive the probability of each case, we introduce the following lemma.

Lemma 1.

In the proposed OR algorithm, if the CV generation is represented by a vector consisting of only one element V, then the sensor nodes that fail to generate independent CV can successfully receive at most $m-1$ packets.

Proof.

If $r_{Ii}$ successfully receives m packets, the index i will be included in ${\Phi }_{S\mathrm{2}}$ and $r_{Ii}$ will generate CV by (7) and (9), so the corresponding vector description will contain the element VV, which contradict the hypothesis.

With Lemma 1, it can be deduced that, in all samples of (V), the sensor nodes that fail to generate independent CV can receive at most 1 ( $m=\mathrm{2}$ ) packet. Thus, all possible samples of (V) can be listed in Table 2.

Table 2

All possible realizations of (V).

Case	Possible sample
1	(V1, O, O, O), (V2, O, O, O), (V3, O, O, O), (V4, O, O, O)
2	(V1, V1, O, O), (V2, V2, O, O), (V3, V3, O, O), (V4, V4, O, O)
3	(V1, V1, V1, O), (V2, V2, V2, O), (V3, V3, V3, O), (V4, V4, V4, O)
4	(V1, V1, V1, V1), (V2, V2, V2, V2), (V3, V3, V3, V3), (V4, V4, V4, V4)

Let $P_i$ denote the probability of the event that $\{d=i\}$ , $i=\mathrm{0,1},\mathrm{2,3},4$ . In Table 2, the event $\{d=1\}$ can be divided into 4 cases; for each case, the probability is denoted as $P_{\mathrm{1}i}$ , so $P_{\mathrm{1}}$ can be expressed as

$$\begin{array}{cc}& P_{\mathrm{1}}=\mathrm{Pr}\left(d=\mathrm{1}\right)={\displaystyle \sum }_{i=\mathrm{1}}^{\mathrm{4}}{P}_{\mathrm{1}i}.\end{array}$$

(10)

Each case is further divided, and $P_{\mathrm{1}i}$ can be written as

$$\begin{array}{cc}& P_{\mathrm{1}i}={\displaystyle \sum }_j{P}_{\mathrm{1}i}^{\left(j\right)},\end{array}$$

(11)

where $P_{\mathrm{1}i}^{(j)}$ denotes the probability of the jth sample of case i in Table 2. Let N denote the total number of the received packets by intermediate cluster per transmission round, and its mathematical expectation can be written as

$$\begin{array}{cc}& E\left(N\right)={\displaystyle \sum }_{k=\mathrm{0}}^{\mathrm{4}}\mathrm{\hspace{0.17em}}{\displaystyle \sum }_i\mathrm{\hspace{0.17em}}{\displaystyle \sum }_j{P}_{ki}^{\left(j\right)}{N}_{ki}^{\left(j\right)},\end{array}$$

(12)

where $N_{ki}^{(j)}$ is the number of received packets in the corresponding sample. $E(N)$ can be used to evaluate the average energy consumption of the network by the reception per round.

We take $P_{\mathrm{12}}^{(\mathrm{1})}$ as an example to show the derivation. As listed in Table 2, it can be derived as

$$\begin{array}{l}{P}_{\mathrm{12}}^{\left(\mathrm{1}\right)}=\mathrm{Pr}\left(\text{sample}=\left({\text{V}}_{\mathrm{1}},{\text{V}}_{\mathrm{1}},\text{O},\text{O}\right)\right)\\ =\left(\begin{array}{l}\mathrm{4}\\ \mathrm{2}\end{array}\right)P^{\mathrm{8}}\left(\begin{array}{l}\mathrm{2}\\ \mathrm{1}\end{array}\right)\left(\mathrm{1}-P\right)\left(\frac{\mathrm{1}}{\mathrm{2}}\right)\left(\mathrm{1}-P\right)P^{\mathrm{3}},\end{array}$$

(13)

where $\left(\begin{array}{c}\mathrm{4}\\ \mathrm{2}\end{array}\right)P^{\mathrm{8}}$ stands for the probability that 2 out of 4 nodes in intermediate cluster fail to receive all the incoming packets. In this sample, the remaining 2 nodes both successfully receive the packet from $r_{\text{S}\mathrm{1}}$ , and one of them is selected with probability 1/2 to forward this packet, so the factor $\left(\begin{array}{c}\mathrm{2}\\ \mathrm{1}\end{array}\right)$ in (13) stands for the above event. $(\mathrm{1}-P)P^{\mathrm{3}}$ accounts for the probability that a node successfully receives the packet from $r_{S\mathrm{1}}$ , but it is selected to neither forward nor successfully receive the rest of incoming packets. Meanwhile, we can calculate $N_{\mathrm{12}}^{(\mathrm{1})}=\mathrm{1}+\mathrm{4}+\mathrm{4}+\mathrm{4}=\mathrm{13}$ for this sample, since the node that is selected to simply forward receives only one packet, while the others receive all 4 incoming ones.

In Table 1, for the vector descriptions that only contain the element V, the possible samples and probabilities can be derived in similar way. For the ones that contain both V and VV, we take (V, VV) as an example. We denote ${\text{V}}_i$ and ${\text{V}}_i{\text{V}}_j$ as the samples of V and VV, respectively. Thus, the following lemma can be proved.

Lemma 2.

In OR algorithm, all the realizations of (V, VV) can be written as the form of $({\text{V}}_i,{\text{V}}_i{\text{V}}_j)$ , $\forall i,j\in \{\mathrm{1,2},\mathrm{3,4}\}$ , $i\ne j$ .

Proof.

If a sample of (V, VV) can be expressed as $({\text{V}}_m,{\text{V}}_i{\text{V}}_j)$ , $m\ne i$ , then according to OR it can be concluded that, besides ${\text{V}}_m$ and ${\text{V}}_i{\text{V}}_j$ , the sample must contain the element ${\text{V}}_i$ . This fact indicates that the realization is a case of (V, V, VV), which contradicts the assumption.

With Lemma 2, all the samples of $(\text{V},\text{VV})$ can be expressed as in Table 3, where ${\Phi }_{\mathrm{31}}=\{\text{O},{\text{V}}_{\mathrm{1}}\}$ , ${\Phi }_{\mathrm{32}}=\{\text{O},{\text{V}}_{\mathrm{2}}\}$ , and ${\Phi }_{\mathrm{33}}=\{\text{O},{\text{V}}_{\mathrm{3}}\}$ . The calculation is similar to the one of (V); for example, let $P_{\mathrm{21}}^{(\mathrm{2})}$ denote the probability of $({\text{V}}_{\mathrm{1}},{\text{V}}_{\mathrm{1}}{\text{V}}_{\mathrm{2}},{\text{V}}_{\mathrm{1}},\text{O})$ , and it can be written as

$$\begin{array}{l}{P}_{\mathrm{21}}^{\left(\mathrm{2}\right)}=\mathrm{Pr}\left(\text{sample}=\left({\text{V}}_{\mathrm{1}},{\text{V}}_{\mathrm{1}}{\text{V}}_{\mathrm{2}},{\text{V}}_{\mathrm{1}},\text{O}\right)\right)\\ =\left(\frac{\mathrm{1}}{\mathrm{3}}\right)\left(\begin{array}{l}\mathrm{4}\\ \mathrm{1}\end{array}\right)\left(\begin{array}{l}\mathrm{3}\\ \mathrm{1}\end{array}\right)\left(\begin{array}{l}\mathrm{2}\\ \mathrm{1}\end{array}\right){\left(\mathrm{1}-P\right)}^{\mathrm{4}}{P}^{\mathrm{7}},\end{array}$$

(14)

while $N_{\mathrm{21}}^{(\mathrm{2})}=\mathrm{1}+\mathrm{2}+\mathrm{4}+\mathrm{4}=\mathrm{11}$ . In this way, all the possible samples and probabilities of (V, VV) can be derived, so as the ones that contain both V and VV in Table 1. By substituting these results into (12), $E(N)$ can be obtained. The derivations of the other possible samples and probabilities listed in Table 1 are presented in the appendix.

Table 3

All possible realizations of ( $$\text{V}$$ , VV).

Case	Possible sample
1	$$({\text{V}}_{\mathrm{1}},\mathrm{\hspace{0.17em}\hspace{0.17em}}{\text{V}}_{\mathrm{1}}{\text{V}}_{\mathrm{2}},\mathrm{\hspace{0.17em}\hspace{0.17em}}{\text{V}}_i,\mathrm{\hspace{0.17em}\hspace{0.17em}}{\text{V}}_i)$$ ,   $$\forall {\text{V}}_i\in {\mathrm{\Phi }}_{\mathrm{31}}$$
2	$$({\text{V}}_{\mathrm{1}},\mathrm{\hspace{0.17em}\hspace{0.17em}}{\text{V}}_{\mathrm{1}}{\text{V}}_{\mathrm{3}},\mathrm{\hspace{0.17em}\hspace{0.17em}}{\text{V}}_i,\mathrm{\hspace{0.17em}\hspace{0.17em}}{\text{V}}_i)$$ ,   $$\forall {\text{V}}_i\in {\mathrm{\Phi }}_{\mathrm{31}}$$
3	$$({\text{V}}_{\mathrm{1}},\mathrm{\hspace{0.17em}\hspace{0.17em}}{\text{V}}_{\mathrm{1}}{\text{V}}_{\mathrm{4}},\mathrm{\hspace{0.17em}\hspace{0.17em}}{\text{V}}_i,\mathrm{\hspace{0.17em}\hspace{0.17em}}{\text{V}}_i)$$ ,   $$\forall {\text{V}}_i\in {\mathrm{\Phi }}_{\mathrm{31}}$$
4	$$({\text{V}}_{\mathrm{2}},\mathrm{\hspace{0.17em}\hspace{0.17em}}{\text{V}}_{\mathrm{2}}{\text{V}}_{\mathrm{3}},\mathrm{\hspace{0.17em}\hspace{0.17em}}{\text{V}}_i,\mathrm{\hspace{0.17em}\hspace{0.17em}}{\text{V}}_i)$$ , $$\forall {\text{V}}_i\in {\mathrm{\Phi }}_{\mathrm{32}}$$
5	$$({\text{V}}_{\mathrm{2}},\mathrm{\hspace{0.17em}\hspace{0.17em}}{\text{V}}_{\mathrm{2}}{\text{V}}_{\mathrm{4}},\mathrm{\hspace{0.17em}\hspace{0.17em}}{\text{V}}_i,\mathrm{\hspace{0.17em}\hspace{0.17em}}{\text{V}}_i)$$ , $$\forall {\text{V}}_i\in {\mathrm{\Phi }}_{\mathrm{32}}$$
6	$$({\text{V}}_{\mathrm{3}},\mathrm{\hspace{0.17em}\hspace{0.17em}}{\text{V}}_{\mathrm{3}}{\text{V}}_{\mathrm{4}},\mathrm{\hspace{0.17em}\hspace{0.17em}}{\text{V}}_i,\mathrm{\hspace{0.17em}\hspace{0.17em}}{\text{V}}_i)$$ , $$\forall {\text{V}}_i\in {\mathrm{\Phi }}_{\mathrm{33}}$$

Similarly, the mathematical expectation of transmitting nodes $E(d)$ can be obtained as

$$\begin{array}{cc}& E\left(d\right)={\displaystyle \sum }_{i=\mathrm{0}}^{\mathrm{4}}{d}_i{P}_i,\end{array}$$

(15)

where $P_i$ is derived in the Appendix. $E(d)$ can be used to evaluate the average energy consumption of the network by the transmission per round.

4.2. Decoding Failure Probability

As defined in Section 2, the decoding failure probability can be expressed as

$$\begin{array}{cc}& P_f=\mathrm{Pr}\left(s<m\right)={\displaystyle \sum }_{i=\mathrm{0}}^n\mathrm{Pr}\left(s<m\hspace{0.17em}|\hspace{0.17em}d=i\right)P_i,\end{array}$$

(16)

where s denotes the number of independent CVs at sink. In [21], it has been proved that two randomly selected CVs are correlated with each other at very small probability (5.63 × 10⁻⁸) when $q=256$ . In fact, small values of q increase the correlation of randomly selected CVs, which will dominate the decoding performance. On the other hand, too large value is also unnecessary, which increases the complexity. Hence, we assume that s equals the number of successfully received packets by sink. In our studied case, $m=2$ , $n=4$ , and it is assumed that all incoming links at sink exhibit the same failure probability $P_{rd}$ . Thus, $\mathrm{Pr}(s<m\hspace{0.17em}|\hspace{0.17em}d=i)$ can be written as

$$\begin{array}{cc}& \mathrm{Pr}\left(s<\mathrm{2}\hspace{0.17em}|\hspace{0.17em}d=i\right)=\mathrm{1},i=\mathrm{0,1},\\ \mathrm{Pr}\left(s<\mathrm{2}\hspace{0.17em}|\hspace{0.17em}d=\mathrm{2}\right)=\mathrm{1}-{\left(\mathrm{1}-P_{rd}\right)}^{\mathrm{2}},\\ \mathrm{Pr}\left(s<\mathrm{2}\hspace{0.17em}|\hspace{0.17em}d=\mathrm{3}\right)=P_{rd}^{\mathrm{3}}+\left(\begin{array}{c}\mathrm{3}\\ \mathrm{1}\end{array}\right)\left(\mathrm{1}-P_{rd}\right)P_{rd}^{\mathrm{2}},\\ \mathrm{Pr}\left(s<\mathrm{2}\hspace{0.17em}|\hspace{0.17em}d=\mathrm{4}\right)=P_{rd}^{\mathrm{4}}+\left(\begin{array}{c}\mathrm{4}\\ \mathrm{1}\end{array}\right)\left(\mathrm{1}-P_{rd}\right)P_{rd}^{\mathrm{3}}.\end{array}$$

(17)

By substituting (17) and $P_i$ into (16), the decoding failure probability can be obtained.

5. Simulation Results

We compare OR with NC based cooperative communication (NCCC) in [16], in terms of $E(N)$ , $E(d)$ , lifetime, and $P_f$ . The simulation model follows the simplified two-hop one in Section 3 with $m=2$ , $n=4$ , and $q=256$ . We define the lifetime as the time that the first node in intermediate cluster dies, which is widely used in the literatures. The energy model in [19] is employed, which has transmitting circuit energy of 45 nJ/packet and receiving circuit energy of 135 nJ/packet, and all the nodes have the initial energy of 500 mJ.

Figure 5 presents the mathematical expectation of received packet $E(N)$ conditioned to the link failure probability P. For OR, the theoretical values are calculated by (12). It shows that our theoretical analysis perfectly matches the simulation results, and OR always yields less received packets comparing with NCCC. In the figure, the theoretical and simulation results also confirm that, for OR, the maximum and minimum values of $E(N)$ are 16 and 7 when $P=1$ and 0, respectively. These points show the performance of OR when the link is in extreme state, for the sample (O, O, O, O) corresponds to $N=16$ while $({\text{V}}_{\mathrm{1}},{\text{V}}_{\mathrm{1}}{\text{V}}_{\mathrm{2}},{\text{V}}_{\mathrm{1}}{\text{V}}_{\mathrm{2}},{\text{V}}_{\mathrm{1}}{\text{V}}_{\mathrm{2}})$ corresponds to $N=7$ . Due to less reception, OR consumes less receiving circuit energy than NCCC.

Figure 5

Mathematical expectation of received packet $E(N)$ versus P.

Figure 6 shows the mathematical expectation of transmitting nodes $E(d)$ versus P. For OR, the theoretical values are calculated by (15). It shows that OR is close to NCCC when P is near 0, which indicates that these two algorithms supply similar redundancy for original data when the link is in good state. In brief, OR always enables less nodes to transmit under the same P. Combining this result with the one in Figure 5, we can conclude that OR consumes less energy than NCCC.

Figure 6

Mathematical expectation of transmitting nodes $E(d)$ versus P.

Figure 7 presents the lifetime comparisons, in which the minimal residual energy of the nodes is simulated after each round. The result shows that OR can support more transmission rounds than NCCC when the energy is exhausted. Besides, it also shows that when $P=0.01$ , OR performs better than $P=0.3$ . This result corresponds well with the one in Figure 5, because smaller value of P will yield less received packets, which dominate the energy consumption in the employed model.

Figure 7

Lifetime comparisons.

Figure 8 depicts the gradient comparisons of the minimal residual energy presented in Figure 7. This metric essentially reflects the energy consumption per round. We observe that, for NCCC, the gradient is fixed to −585 nJ. This is due to the fact that each node will always receive 4 packets and transmit 1 per round. Comparing with NCCC, the result shows that OR always yields less gradient, and it fluctuates with time. This is caused by the dynamic manner selection, through which the nodes opportunistically generate their CVs. Moreover, it also shows that superior link quality yields smaller gradient for OR.

Figure 8

Gradient comparisons.

Figure 9 depicts the decoding failure probability $P_f$ versus P. It indicates that OR performs close to NCCC when P is near 0, which corresponds well with the result in Figure 6. Again, our theoretical analysis matches the simulations very well. On the other hand, the gap between the two compared algorithms grows as $P_{rd}$ increases, which shows that OR is less efficient under poor relay-sink links. However, different from our simplified model, the sink generally locates in the sink cluster in practice and hence the other sensor nodes in the sink cluster also help to receive, which yields superior reception performance even when $P_{rd}$ is in poor state.

Figure 9

Decoding failure probability $P_f$ versus P.

6. Conclusion

In this paper, we proposed an energy-efficient OR algorithm to reduce the energy consumption of the sensor nodes in cooperative WSNs. The theoretical and simulation results show that OR outperforms NCCC in energy consumption, while it also obtains similar decoding failure probability to that of NCCC when the incoming links are in good state. The proposed algorithm provides a trade-off between energy efficiency and transmission reliability.