Improving transmission reliability in wireless sensor networks using network coding

Abstract

Wireless sensor networks employed in industrial and other special applications have strict requirements concerning the transmission reliability, delays and energy efficiency. This paper proposes a scalable approach for increasing transmission reliability in wireless sensor networks, based on a cooperative scheme that uses Reed–Solomon codes as network code. The block error rate of the proposed coded transmission technique is analyzed in several scenarios and it is shown that our solution improves the error performance even for high coding rates. The paper proposes also a genetic algorithm based optimization of the network code functionality by selecting the most cooperation capable devices. The proposed network coding based solution is compared with automatic repeat request transmissions from the point of view of the resource usage, which influences the energy efficiency and the transmission delays. The evaluations performed show that network coded transmissions can ensure better error performance with significantly less resources.

1 Introduction

The significant development of wireless technologies in recent years allowed their integration in automation, security, agriculture and industrial applications which require sensing of various parameters [11]. Wireless sensor networks (WSNs) offer a high degree of flexibility of the sensing processes, but in the same time low power consumption and low costs are imposed [5] in applications like home automation, environmental supervision and agriculture. In industrial environments the cooperation capabilities characteristic to WSNs bring several advantages over traditional wired monitoring systems such as self-organization, rapid deployment, flexibility and intelligent processing capability [8]. WSNs employed in industrial control systems have to fulfill much stricter additional requirements in what concerns reliability, timing, delay and security [10]. In order to achieve these goals industrial WSN standards [10, 12] employ centralized timing and resource assignment, as well as path diversity and frequency diversity in the wireless transmission process.

Besides the quality of service (QoS) related aspects, energy efficiency remains a main requirement in industrial WSNs. Cross-layer based solutions are proposed in existing standards [12] and in theoretical studies [6] to meet these requirements. Another solution to save energy is to design efficient routing protocols in WSNs, like those proposed in [1, 22] and [17]. In [7] it was shown that organizing the network nodes in cooperative groups can reduce the global energy consumption of the WSN. Network coding (NC) techniques represent a particular form of cooperation and the solutions based on these techniques are also considered, a large number of studies dealing with NC in WSNs being available in the recent technical literature. In [19] and [24] NC techniques that allow each node to encode the overheard packets, thus decreasing the number of transmissions and power consumption are proposed, while in [2] and [9] the reliability aspects applicable to WSNs and other sensor networks are analyzed.

The employment of NC-based cooperation techniques in wireless networks in general and in WSNs in particular opens the door for more complex cooperative scenarios, like multiple source multiple relay (MSMR) cooperation. This approach received a significant attention from the research community, several cooperation scenarios being defined in the recent literature [3, 4, 25]. This approach is expected to bring significant performance improvements at the expense of increased system complexity. The reliability in WSNs could be also increased by using code-on-network-graph NC techniques, based on LDPC codes, as proposed in [16].

The NC scheme presented in this paper adapts the Reed–Solomon (RS) code based NC protocol proposed in [21] to clustered WSNs, each cluster containing a relatively small number (max. 15–20) of nodes. Such topologies are common in industrial applications, where the clusters of sensor nodes are connected through a backbone network [15]. The proposed solution has as goal the improvement of the transmission reliability, while taking into account the scalability, complexity and energy efficiency issues.

The structure of this paper is the following: Section 2 introduces the system model considered. Section 3 describes the NC technique proposed, while Sect. 4 presents the NC encoding and decoding algorithms. Section 5 describes the modeling of multi-hop transmission paths, derives the basic relations used to evaluate the network coded transmission’s performances, proposes an optimization method for the developed NC technique and analyzes the resource efficiency of the proposed solution compared to the classical automat repeat request (ARQ) technique used for error control in WSNs. Section 6 discusses the numerical results, and Sect. 7 concludes the paper.

2 System model

The paper considers a fixed cluster-tree topology [5], composed of several tree topologies with the same root, localized in a special node acting as an access point (AP) or gateway. This node connects the other nodes of the cluster to a backbone [15] or to a central controller [12]. Figure 1a depicts such a cluster composed of sensor devices or routers, as basic nodes [10], and a relay node (RN) able to overhear the transmissions of all, or most of the cluster’s nodes. Figure 1 also presents two particular topologies used in the performance analysis. The first test topology, Fig. 1b, represents a tree within which each node, excepting the root, has a single leaf, and whose main particularity is that the numbers $n_{k}$ of nodes located at $k$ hops from the root are equal, i.e., $n_{1} = n_{2} = \ldots = n_{z}$, for $k = 1 \ldots z$, where $z$ denotes the maximum number of hops. Within the second test topology, Fig. 1c, each node has two leaves. Its main particularity is the variable number of nodes located at $k$ hops from the root, described by: $n_{k} = 2^{k}n_{k-1}$, $k = 1 \ldots z$ and $n_{0} = 1$.

Fig. 1

Cluster-tree topology with relay node (a). NC enabled tree test topology one (b) and two (c)

All nodes of the topology are fixed and have the same transmission power, $P_{t}$. Each transmission link is affected by path loss and interference from other communication systems [12], the power of interference $P_{int}$ being considered constant in the entire network.

Two main assumptions are made regarding the distance $d_{i}$ between two nodes connected by a direct link $i$:

• (1) $d_{i} \ne const$ is not constant and its value is uniformly distributed in a finite interval $[d_{min}$, $d_{max} ]$, no restrictions being imposed for the positioning of the nodes;

• (2) $d_{i} = const, \forall i$ is constant and its value is uniformly distributed in a finite interval $[d_{min}$, $d_{max} ]$, no other restrictions being imposed for the positioning of the nodes.

The second assumption will be used only in the case of the first test topology.

Each link of the topology is modeled as a block erasure channel (BLEC) characterized by its block error rate (BLER) value ensured by its modulation scheme. Computation of the bit error rate (BER) of a wireless transmission using an IEEE 802.15.4 physical layer (frequently used in industrial WSNs) in the mentioned conditions can be done according to [11]:

$$\begin{aligned} BER_{link_{i}}(SIR_{i}) = \frac{1}{30} \sum _{k=2}^{16} \left( (-1)^{k} \left( {\begin{array}{c}k\\ 16\end{array}}\right) e^{20SIR_{i}(\frac{1}{k}-1)} \right) , \end{aligned}$$

(1)

where $SIR_{i}$ is the signal to interference ratio at the receiver on link $i$.

The BLER of a transmission frame having $L$ bits at a specified $SIR$ can be computed according to:

$$\begin{aligned} BLER_{link_{i}}(SIR_{i}) = 1-(1-BER_{link_{i}}(SIR_{i}))^{L} \end{aligned}$$

(2)

Considering the free space radio propagation model the $SIR$ parameter at the receiver is given by:

$$\begin{aligned} SIR_{i} = \frac{P_{t}}{P_{int}} \frac{\lambda ^{2}}{(4 \pi )^{2}} \frac{1}{d_{i}^{2}} = SIR_{0}ct_{\lambda } \frac{1}{d_{i}^{2}}, \end{aligned}$$

(3)

where $SIR_{0}$ is the signal to interference ratio at the transmitter, $ct_{\lambda }$ is a parameter depending on the wavelength and $d_{i}$ is the physical length of the link.

Based on this model both the BER and BLER parameters of a transmission link could be expressed as functions of the distance between the nodes connected by the link.

$$\begin{aligned} BER_{link_{i}}(d_{i}) = \frac{1}{30} \sum _{k=2}^{16} \left( (-1)^{k} \left( {\begin{array}{c}k\\ 16\end{array}}\right) e^{20SIR_{0}ct_{\lambda } \frac{1}{d_{i}^{2}} (\frac{1}{k}-1)} \right) \end{aligned}$$

(4)

$$\begin{aligned} BLER_{link_{i}}(d_{i}) = 1-(1-BER_{link_{i}}(d_{i}))^{L} \end{aligned}$$

(5)

We also assume that the network has a centralized controller [10], which performs the resource allocation and routing throughout the entire network. The central element also controls the coding operations performed in each cluster.

3 The proposed solution

The NC-based solution proposed hereinafter for the system model described above aims at the following targets:

• Improve the reliability of the transmissions while fulfilling the delay requirements;

• Ensure a high degree of scalability;

• Modify as less as possible the routing, scheduling, power management and other network operations;

• Ensure an easy integration in various WSNs built according to the considered network model but having different characteristics and operation modes.

The NC-based transmission technique proposed uses a single RN per cluster. The RN is equipped with a more sensitive receiver than the ordinary nodes, and is positioned in such a way to be able to decode the data received from the cluster’s nodes with BLER values obeying some statistical distribution, and to have line-of-sight connection to the central node. The RN is placed within the intersection of all nodes’ coverage areas (Fig. 1a depicts only the coverage areas of some nodes, the larger ones, in order to simplify the figure). The RN performs the NC-encoding of the correctly decoded blocks overheard from the cluster’s nodes and generates one or several check blocks which are sent to the cluster’s AP, which performs the NC decoding. The number of check blocks generated by the RN is selected such that a target BLER after decoding is ensured and the requirements related to the efficiency of the transmission are fulfilled. The check blocks generated by the RN bring increased path diversity in the cluster, besides providing a coding gain.

The proposed solution requires changes at the AP level, since it should be able to perform the NC-decoding, and at the network controller level which has to assign resources for the RN-AP link and has to control the NC process by selecting the best code and by activating/deactivating the NC operations. No changes would be required at the ordinary device level and within the routing algorithms.

4 Coding and decoding operations

In [18] the trade-off between transmission and processing energy consumption in a sensor node employing convolutional codes was investigated in order to select the error control code to be used to maximize the network lifetime. In our solution maximum distance separable (MDS) codes, like RS codes [20], are used as network code. The MDS codes provide good error and erasure correction capabilities and are one of the best choices as network codes for small number of nodes and relays. The coding operations performed by the RN are presented in Fig. 2.

Fig. 2

The NC coding operations performed by the RN

The NC encoder is located in the RN, which receives, demodulates and decodes the equal-size blocks generated by the $N_{D}$ nodes of the cluster. Each node generates a single block in each assigned time slot. It is supposed that the receivers of the RN and AP can identify the correctly received blocks, e.g. by means of the cyclic redundancy check (CRC), thus transforming the channels into erasure channels. Each block is split into $t$ symbols of the $GF(2^{s})$ finite field, $s$ being the number of bits/symbol. The symbols of all blocks are RS-encoded by selecting one symbol at the time from each block, thus generating $N_{check}$ check blocks, each composed of $t$ symbols, as shown in Fig. 2 for $N_{check} = 2$. The parameters of the selected RS ($n$, $k$) code have to fulfill: $k \ge N_{D}$; $n - k \ge N_{check}$. The encoder processes in each time slot only the blocks correctly decoded from the cluster’s nodes.

The RS-decoding process performed in the AP is presented in Fig. 3. The correctly decoded data and the check blocks provided by the channel decoders, from the cluster’s nodes and RN respectively, are applied to the RS decoder. In the same time, the correctly decoded data blocks are sent to the selection units. These units generate the final decoded data blocks for each sensor device, $Data D_{i}$, according to the following rule:

• $Data D_{i} = Chan. dec. D_{i}$ output, if $Ch. dec. D_{i}$ succeeded;

• $Data D_{i} = RS$ decoder output $i$, if $Chan. dec. D_{i}$ failed & RS decoder succeeded;

• $Data D_{i} = Erasure$, if $Ch. dec. D_{i}$ failed & RS decoder failed.

It can be noticed that the NC decoding does not affect the “normal” operations of the network, the data decoded by the RS decoder being considered only if the direct transmission fails, and in this way the NC operations bring not only coding gain, but also an extra diversity in the network.

Fig. 3

The NC decoding operations performed by the AP

5 Performance analysis

5.1 Transmission path modeling

Each transmission path between the nodes of the topology and the root node is modeled as a Block Erasure Channel characterized by its BLER. The BLER on a path composed of z links is expressed by:

$$\begin{aligned} \begin{array}{rcl} BLER_{path-z} =&{}&{} \sum _{i=1}^{z}BLER_{link_{i}}\\ &{}&{}\quad - \sum _{i,j,i \ne j}BLER_{link_{i}}BLER_{link_{j}}\\ &{}&{}\quad + \sum _{i,j, k, i \ne j \ne k}BLER_{link_{i}}\\ &{}&{}\quad \times \,BLER_{link_{j}}BLER_{link_{k}}\\ &{}&{}\quad - \cdots \approx \sum _{i=1}^{z}BLER_{link_{i}} \end{array} \end{aligned}$$

(6)

The $cdf$ of the $BLER_{path}$ approximations error, $er_{BLER}$, for $BLER_{link} < 0.1$ and different values of $z$ is given in Table 1. These results were obtained based on a statistical analysis and they show that for $z < 5$ the approximation error is around 5 %, while for $z = 5$ it is around 10 %.

Table 1 CDF of the $BLER_{path}$ approximation error, $er_{BLER}$, for various values of the number of hops $z$

In our study the BLER approximation errors less than 10 % are considered acceptable and the composite BLER of multihop paths will be approximated as in relation (6).

Due to the monotonicity of the functions defined by Eqs. (4) and (5), which gives the relation between the BER and BLER parameters and the link length $d$, and due to the uniform distribution of the distances $d_{i}$, the $BLER_{link_{i}}$ parameter will be uniformly distributed between $BLER_{m} = BLER_{link}(d_{min})$ and $BLER_{M} = BLER_{link}(d_{max})$. The probability density function ($pdf$) of the BLER on the link is expressed as:

$$\begin{aligned}&p_{BLER-link}(x)\nonumber \\&\quad = {\left\{ \begin{array}{ll} \frac{1}{BLER_{M}-BLER_{m}}, &{}\quad \text {if } x \in [BLER_{m}, BLER_{M}] \\ 0, &{}\quad \text { otherwise} \end{array}\right. }\nonumber \\ \end{aligned}$$

(7)

where $BLER_{m} = 0.01$, and $BLER_{M} = 0.1$.

The upper BLER limit was selected knowing that a $BLER = 0.1$ is commonly considered in communication systems as the maximum value over a transmission link. A similar distribution of the BLER values is also assumed on the node/device-RN links.

Based on the approximation of the path’s BLER given by (6) the pdf of this parameter when the link’s BLER is uniformly distributed according to (7) is given by (8):

$$\begin{aligned} p_{BLER-path-z} = \prod _{i=1}^{z} *p_{BLER-link_{i}}(x), \end{aligned}$$

(8)

where $\prod *$ denotes the convolutional product.

The $pdf$ of the link’s BLER, $p_{BLER-link}(x)$, is given by Eq. (7) with $BLER_{M} = 0.1$. For $z = 2$ and $3$ the $p_{BLER-path-z}(x)$ $pdfs$ are given by (9) and (10).

$$\begin{aligned}&p_{BLER-path-2}(x) = p_{BLER-path-1}(x) *p_{BLER-path-1}(x)\nonumber \\&\quad ={\left\{ \begin{array}{ll} p^{2}(x-2B_{m}), &{}\quad \text {if } x \in [2B_{m}, B_{M}+B_{m}] \\ p^{2}(2B_{M}-x), &{}\quad \text {if } x \in [B_{M}+B_{m}, 2B_{M}] \\ 0, &{}\quad \text {otherwise} \end{array}\right. } \end{aligned}$$

(9)

$$\begin{aligned}&p_{BLER-path-3}(x) = p_{BLER-path-1}(x) *p_{BLER-path-2}(x)\nonumber \\&\quad = \frac{p^{3}}{2}\left\{ \begin{array}{ll} (x-3B_{m})^{2}, \quad \text {if } x \in [3B_{m}, B_{M}+2B_{m}] \\ (\sqrt{6}B_{M}-\sqrt{6}B_{m})^{2}-(x-3B_{M})^{2}-(x-3B_{m})^{2}, \\ \qquad \qquad \qquad \qquad \text {if } x \in [B_{M}+2B_{m}, 2B_{M}+B_{m}] \\ (x-3B_{M})^{2}, \quad \text {if } x \in [2B_{M}+B_{m}, 3B_{M}] \\ 0, \qquad \qquad \qquad \quad \text {otherwise} \end{array}\right. \nonumber \\ \end{aligned}$$

(10)

Relations (9) and (10) show the increase of the path’s $BLER_{M}$ value with the increase of the number of hops. Fig. 4 presents the probability density functions of the $BLER_{path-z}$ for different number of hops.

Fig. 4

Probability density function of $BLER_{path-z}$ for transmission paths with 1, 2 and 3 hops

In the particular case when the distance between any two nodes of the topology is constant (as in the case of test topology one) and the approximation given by (6) holds the path BLER is uniformly distributed according to:

$$\begin{aligned}&p_{BLER-path-z}(x) \nonumber \\&\quad = \left\{ \begin{array}{ll} \frac{1}{BLER_{max}-BLER_{min}}, &{}\quad \text { if } x \in \left[ BLER_{min}, BLER_{max}\right] , \\ 0, &{}\quad \text {otherwise}, \end{array}\right. \nonumber \\ \end{aligned}$$

(11)

where $BLER_{min} \!=\! z BLER_{m}$, and $BLER_{max} \!=\! zBLER_{M}$.

5.2 Analysis of the network coded transmission reliability

According to the operating principle of the NC decoder described in Sect. 4, the BLER affecting the blocks transmitted by node $D_{i}$, after the NC-decoding, is given by:

$$\begin{aligned} \begin{array}{rcl} BLER_{D_{i}} &{} = &{} 1 - Pcor_{D_{i}} \\ Pcor_{D_{i}} &{} = &{} 1 - BLER_{D_{i}-AP} + P_{coop}^{D_{i}}(1 - PE_{bl(D_{i})}) \end{array}, \end{aligned}$$

(12)

where $P_{coop}^{D_{i}} = 1-BLER_{D_{i}-RN}$ represents the probability of correct decoding at RN of the block generated by $D_{i}$, $BLER_{D_{i}-AP}$ is the BLER on the $D_{i} - AP$ path and $PE_{bl(D_{i})}$ is the probability of erroneous decoding by the RS decoder of the $D_{i}$ data block.

The $PE_{bl(D_{i})}$ probability can be computed using Eq. (13), as proven in [21]. Note that, when all the cluster’s nodes are involved in the NC operations, i.e., their blocks are correctly decoded by the RN, the $PE_{bl(D_{i})}$ probability is identical for all nodes:

$$\begin{aligned} PE_{bl(D_{i})} = \sum _{k = N_{check}+1}^{N_{Dc} + N_{check}}Pt, \end{aligned}$$

(13)

where

$$\begin{aligned} Pt = \sum _{\begin{array}{c} BL' \in BL^{(k)} \\ bl(D_{i}) \in BL' \end{array}} \left( \prod _{bl \in BL'}BLER(bl) \cdot \prod _{bl \in BL \setminus BL'}(1-BLER(bl)) \right) , \end{aligned}$$

(14)

where $N_{Dc}$ denotes the number of nodes decoded correctly by the RN, $N_{check}$ represents the number of check blocks, $BL$ represents the set of the data blocks generated by all nodes of the cluster, correctly decoded by RN, and of the check blocks generated by RN, $BL^{(k)}$ denotes the family of $k$-block long subsets of $BL$ and $bl(D_{i})$ represents a block sent by node $D_{i}$.

The average number of nodes whose blocks are decoded correctly by the RN can be computed using relation (14) and (15), as in [21]:

$$\begin{aligned} N_{D-mean} = \sum _{l=1}^{N_{D}}p_{l} \cdot l \end{aligned}$$

(15)

$$\begin{aligned} p_{l} = \sum _{d' \in D^{(l)}} \biggl ( \prod _{D_{i} \in D'}P_{coop}^{D_{i}} \cdot \prod _{D_{i} \in D \setminus D'}(1-P_{coop}^{D_{i}}) \biggr ), \end{aligned}$$

(16)

where $p_{l}$ represents the probability of having $l$ nodes decoded correctly by the RN, $D$ is the set of all nodes of the cluster and $D^{(l)}$ denotes the family of $l$-long subsets of $D$.

Note that it is assumed that interference is affecting the entire period of the transmitted blocks having as consequence that: $p_{error-symbol} = p_{error-block}$.

5.3 Optimization of the network coded operations

5.3.1 Optimization criteria

The improvement of the $BLER_{D_{i}}$ performance could be achieved, at least in some situations, by selecting a smaller number of nodes whose blocks are encoded by the RN, if received correctly, while taking into account the BLER of the $D_{i}-AP$ and $D_{i}-RN$ paths. In the current scenarios, based on fixed-topology networks, the optimization process is part of the network planning and maintenance operations and has to be performed at network deployment or when significant changes occur in topology or in the interference level. We consider the following optimization criteria:

$$\begin{aligned} crit. \text { } 1:\min \overline{BLER_{D_{i}}} = \min \left( \frac{1}{N_{D}} \sum _{i=1}^{N_{D}}BLER_{D_{i}} \right) \end{aligned}$$

(17)

$$\begin{aligned} crit. \text { } 2: \min \max _{i = \overline{1, N_{D}}}(BLER_{D_{i}}) \end{aligned}$$

(18)

The optimization is performed using a Genetic Algorithm (GA) [13] briefly described below. The use of this type of optimization algorithm is motivated by its flexibility in formulating complex optimization problem involving a large number of variables and by the good optimization performances provided. The main shortcoming of GAs, their need of extensive computation, is not very important in the assumptions of this paper, which involve network planning and/or network restructuring.

5.3.2 The GA based network code optimization

The flow chart of the GA used for the optimization of the NC operation is presented in Fig. 5. The algorithm uses the topology and the link’s BLER distributions, to provide the set of nodes, $N_{NC}$ in number, whose blocks are encoded by the RN, if the node-RN transmissions are decoded correctly. Each chromosome is a subset of the cluster’s nodes set, having $N_{D}$ elements, and is represented as a string of $N_{D}$ binary symbols having $N_{NC}$ non-zero values and each position in the string is associated with a node. A ’1’ value on position $i$ means that node $D_{i}$ is involved in NC while a ’0’ value means that node $D_{i}$ is not involved in NC.

Fig. 5

Flow chart of the GA based optimization of the NC operations

The initial population is formed of $N_{pop} = 30-40$ random chromosomes and is evaluated according to the optimization criteria defined by (17) or by (18), and the fitness value of each chromosome is obtained. After the initial evaluation, a new population is built based on the GA’s operations: selection, crossover and mutation.

In each iteration from the current population, $P$ (selection pressure, $P = 4$) chromosomes are selected randomly, and the one with the best fitness value is kept. This process is repeated until the new population is complete. After selection, the chromosomes undergo a one-point crossover according to the crossover probability (20 %) and after that a random binary mutation takes place according to the mutation probability (2 %). The new population is evaluated similarly to the initial one, and the best chromosome of the generation and its fitness value are stored. New populations are formed until the algorithm reaches the maximum number of generations imposed, $N_{gen} = 20 - 30$. The chromosome having the best fitness value is selected out of the stored ones; this chromosome contains the final subset of the $N_{NC}$ nodes involved in the NC operations.

5.4 Analysis of NC and ARQ transmissions resource efficiency

Besides transmission reliability, both the latency of the transmitted data and the energy efficiency has to be taken into consideration when designing WSNs for industrial or other special applications. Ensuring the transmission reliability can be achieved both by forward error correction (FEC) techniques (at link or at network level) and by ARQ based techniques, the latter being the solution of choice in the standardized and currently implemented WSN solutions. A comparision between ARQ based transmission and FEC transmission techniques based on RS code was presented in [23].

Both the latency in recovering of the transmitted data blocks and the energy efficiency (especially the latter one) depend significantly on the amount of network resources employed. In our particular situation the resources are represented by time slots allocated for transmission.

We will compare the resource efficiency of the proposed network coded transmission and of an uncoded transmission using ARQ and graph routing [10] in the condition of similar BLER performance ensured for the nodes of the cluster. The analysis will be performed in the case of a simple star topology with only single hop paths and the tree topology one described in Sect. 2, the obtained conclusions being valid also for other tree topologies.

In Fig. 6 the principle of ARQ operations based on graph routing for the relay enhanced star topology is presented. In this case we can identify two graphs: the direct graph represented by the direct $D_{i} - AP$ links and the cooperation graph represented by the $D_{i}-RN-AP$ paths. In order to provide path diversity the ARQ operations are implemented in the following way (see Fig. 6): each device performs the first transmission in the direct graph using the direct link to the AP; if this transmission fails the first retransmission is taking place in the cooperation graph, using the path passing through the RN. If this second transmission fails, the following retransmission (if allowed) is taking place in the direct graph; the process is repeated until the packet is correctly decoded or the maximum number of transmissions is reached. Note that the RN can use for retransmissions only de direct $RN-AP$ link.

Fig. 6

ARQ operations performed in a star topology when using graph-based routing

If we consider that a number of $N_{t}$ transmissions are allowed (including the first transmission attempt) for each node, including the RN, the BLER of a device $D_{i}$ using the ARQ technique described, $BLER_{ARQ-D_{i}}$ is given by:

$$\begin{aligned} BLER_{ARQ-D_{i}}(N_{t}) = 1 - \sum _{r=1}^{N_{t}}p(r)P_{correct}(r), \end{aligned}$$

(19)

where $P_{correct}(r)$ is the probability of a correctly received block on one of the paths and is given by:

$$\begin{aligned} P_{correct}(r)= {\left\{ \begin{array}{ll} 1-BLER_{D_{i}-AP}, \quad \text { if } r \text { odd} \\ (1-BLER_{D_{i}-RN}) \sum _{r=1}^{N_{t}}BLER_{RN-AP}^{r-1}&{}\\ \quad (1-BLER_{RN-AP}), \quad \text { if } r \text { even} \end{array}\right. } \end{aligned}$$

(20)

and $p(r)$ is the probability of the source reaching the transmission with index $r$ and can be computed using the formula:

$$\begin{aligned} p(r) = {\left\{ \begin{array}{ll} bler(k), &{}\quad \text { if}\ r \ge 2 \\ 1, &{}\quad \text { if}\ r=1, \end{array}\right. } \end{aligned}$$

(21)

where

$$\begin{aligned} bler(k) = {\left\{ \begin{array}{ll} BLER_{D_{i}-AP}, &{}\quad \text {if } k \text { odd}\\ BLER_{D_{i}-RN}, &{}\quad \text {if } k \text { even} \end{array}\right. } \end{aligned}$$

(22)

Based on relations (21) and (22) $p(r)$ can be expressed as:

$$\begin{aligned} p(r) = {\left\{ \begin{array}{ll} BLER_{D_{i}-AP}^{\lfloor r/2 \rfloor }BLER_{D_{i}-RN}^{\lfloor (r-1)/2 \rfloor }, &{}\quad \text {if } r \ge 2 \\ 1, &{}\quad \text {if } r = 1 \end{array}\right. } \end{aligned}$$

(23)

The maximum amount of resources (time slots) required by the network coded, $N_{res-NC}$, and by the ARQ enabled transmissions, $N_{res-ARQ}$, are given by:

$$\begin{aligned} N_{res-NC} = N_{D}+N_{check} \end{aligned}$$

(24)

$$\begin{aligned} N_{res-ARQ} = \left( 2N_{t} - N_{t} mod 2 \right) N_{D} \end{aligned}$$

(25)

Based on the amount of the necessary resources the transmission rates corresponding to the NC and ARQ enabled transmissions can be computed as:

$$\begin{aligned} R_{NC} = \frac{N_{D}}{N_{res-NC}}; \quad R_{ARQ} = \frac{N_{D}}{N_{res-ARQ}} \end{aligned}$$

(26)

considering that each device is transmitting at each moment one block and all blocks have the same number of bits $L$.

In the case of a relay enhanced tree topology, which includes multihop links (see the test topologies described in Sect. 2) the proposed ARQ operations are a bit modified for the network nodes located at more than one hop distance from the AP. For these nodes the first transmission takes place in the cooperation graph, i.e. on the $D_{i}-RN-AP$ path, which is the shortest path for more than two hops. The next transmission, if necessary, is taking place in the direct graph and so on.

Taking as starting point the reasoning presented in the case of the simple star topology the $BLER_{ARQ-D_{i}}$ parameter for nodes located at $z_{i}>1$ hops from the AP can be derived as:

$$\begin{aligned} BLER_{ARQ-D_{i}}(N_{t}) = 1 - \sum _{r=1}^{N_{t}}p(r)P_{correct-D_{i}}(r), \end{aligned}$$

(27)

where $p(r)$ is the defined by:

$$\begin{aligned} p(r) = {\left\{ \begin{array}{ll} BLER_{D_{i}-RN}^{\lfloor r/2 \rfloor }BLER_{D_{i}-D_{i-1}}^{\lfloor (r-1)/2 \rfloor }, &{}\quad \text {if } r \ge 2 \\ 1, &{}\quad \text {if } r = 1 \end{array}\right. } \end{aligned}$$

(28)

and $P_{correct-D_{i}}(r)$ is given by:

$$\begin{aligned}&P_{correct-D_{i}}(r)\nonumber \\&\quad = {\left\{ \begin{array}{ll} (1-BLER_{D_{i}-D_{i-1}})(1-BLER_{ARQ-D_{i-1}}), &{} \\ \qquad \text { if } r \text { even} \\ (1-BLER_{D_{i}-RN}) \sum _{r=1}^{N_{t}}BLER_{RN-AP}^{r-1}&{}\\ \quad (1-BLER_{RN-AP}), &{} \\ \qquad \text { if } r \text { odd} \end{array}\right. } \end{aligned}$$

(29)

Note that for nodes located at 1 hop distance from the AP relations (19)–(23) can be applied.

The maximum amount of resources required by the NC and by the ARQ enabled transmissions, $N'_{res-NC}$ respectively $N'_{res-ARQ}$ are given by:

$$\begin{aligned} N'_{res-NC} = N_{D}+N_{check}+\sum _{k=1}^{N'_{D}}(N_{hop-k}-1) \end{aligned}$$

(30)

$$\begin{aligned} N'_{res-ARQ} = {\left\{ \begin{array}{ll} N_{D}+\sum _{k=1}^{N'_{D}}(N_{hop-k}-1) &{} \text {, if } N_{t} = 1 \\ \left( 2N_{t} - N_{t} mod 2 \right) N_{D} + 2\lfloor N_{t}/2 \rfloor \\ \quad \sum _{k=1}^{N'_{D}}(N_{hop-k}-1) &{} \text {, if } N_{t} \ge 2 \end{array}\right. } \end{aligned}$$

(31)

where $N'_{D}$ is the number of nodes/devices located at more than one hop distance from the AP and $N_{hop-k}$ represents the number of hops on the $D_{k}-AP$ path.

Relation (31) is obtained based on the Eqs. (32) and (33). The first equation gives the maximum amount of resources required by a node at one hop from the AP, $N_{res-ARQ-D_{1}}$:

$$\begin{aligned} N_{res-ARQ-D_{1}} = \left( 2N_{t} - N_{t} mod 2 \right) \end{aligned}$$

(32)

The second Eq. (33) gives the relation between the resources required by a node located at $z_{i}$ hops away from the AP and a node on the same path but located at $z_{i-1} = z_{i}-1$ hops from the AP:

$$\begin{aligned} N_{res-ARQ-D_{i}} = N_{res-ARQ-D_{i-1}}+2\bigg \lfloor \frac{N_{t}}{2} \bigg \rfloor \end{aligned}$$

(33)

6 Numerical results and discussions

6.1 Network coded transmission BLER performance evaluation

The following test scenarios were considered:

• (A) $N_{D} = 24$, $d_{i} = const$, number of hops $z = 5$, tree test topology 1 (Fig. 1b), $BLER_{D_{i}-AP}$ distributed uniformly between $[0.01, 0.5]$, $BLER_{D_{i}-RN}$ distributed uniformly between $[0.01, 0.25]$, $BLER_{RN-AP} = 0.1$;

• (B) $N_{D} = 24$, $d_{i} \ne const$, $z = 5$, test topology 1, $BLER_{link}$ uniformly distributed according to (7), $BLER_{D_{i}-AP}$ distributed according to (8), the same conditions as in scenario A for $BLER_{D_{i}-RN}$ and $BLER_{RN-AP}$;

• (C) $N_{D} = 24$, $d_{i} \ne const$, $z = 5$, test topology 2 (Fig. 1c), $BLER_{link}$ distributed according to (7), $BLER_{D_{i}-AP}$ distributed according to (8), the same conditions for $BLER_{D_{i}-RN}$ and $BLER_{RN-AP}$.

$N_{check} \in \{1, 2, 4, 6\}$ in each of the above scenarios.

At first, the mean and the maximum values of $BLER_{D_{i}}$, $i = 1 \ldots N_{D}$, were evaluated in the three scenarios considered for several sets of $BLER_{D_{i}-AP}$ and $BLER_{D_{i}-RN}$ probabilities generated according to (7) and (8) and for different NC coding rates $R_{NC} = N_{D}/(N_{D} + N_{check})$. The BLER improvement factors, $G_{av}$ and $G_{max}$, defined by (34), were evaluated for each set of $BLER_{D_{i}-AP}$ and $BLER_{D_{i}-RN}$ probabilities and for each coding rate considered. Figures 7 and 8 present the average values over all experiments of the $G_{av}$ and $G_{max}$ parameters. In all these experiments we assumed $N_{Dc} = N_{D}$, to point out the capabilities of the “pure” NC technique. The corresponding average and maximum values of the $BLER_{D_{i}}$ for the uncoded case are given as reference in Table 2.

$$\begin{aligned} \begin{aligned}&G_{av} = \frac{\overline{BLER_{D_{i}-AP}}_{i = \overline{1,N_{D}}}}{\overline{BLER_{D_{i}}}_{i = \overline{1,N_{D}}}} \\&G_{max} = \frac{\max _{i = \overline{1,N_{D}}}(\overline{BLER_{D_{i}-AP})}}{\max _{i = \overline{1,N_{D}}}(\overline{BLER_{D_{i}})}} \end{aligned} \end{aligned}$$

(34)

Fig. 7

$G_{av}$ BLER improvement factor versus $R_{NC}$

Fig. 8

$G_{max}$ BLER improvement factor versus $R_{NC}$

Table 2 Mean and maximum values of $BLER_{D_{i}}$ in the uncoded scenario

These results show that significant decreases of $BLER_{D_{i}}$ can be provided by the NC-coded approach, even for NC-coding rates as high as $R_{NC} = 0.8 - 0.85$, in all test scenarios. Smaller improvement factors $\in [1.2 - 10]$ can be obtained for very high coding rates as $R_{NC} = 0.92 - 0.96$ according to the distribution of the $BLER_{D_{i}-AP}$ probabilities.

In a second set of experiments the NC operation was optimized using a GA, targeting the minimization of the mean and maximum values of $BLER_{D_{i}}$, and hence the number of nodes involved in the NC operation was $N_{NC} \le N_{D}$ even if all node’s transmissions are correctly decoded by the RN.

Figures 9 and 10 show the relative BLER improvement factors, $G_{r-av}$ and $G_{r-max}$, (the average values over all experiments) obtained with the NC operation optimized according to criteria (17) and (18), for all the three scenarios.

$$\begin{aligned} \begin{array}{rcl} G_{r-av} &{} = &{} G_{av-optimized}/G_{av-non-opt} \\ G_{r-max} &{} = &{} G_{max-optimized}/G_{max-non-opt} \end{array} \end{aligned}$$

(35)

Fig. 9

$G_{r-av}$ relative BLER improvement factor versus $R_{NC}$

Fig. 10

$G_{r-max}$ relative BLER improvement factor versus $R_{NC}$

The optimization of the NC operation, provides increased BLER improvement factors only for very high NC coding rates, such as $R_{NC}= 0.92-0.96$. The increases of the $G_{r}$ factors are as large as $1.1-1.8$, depending on the distribution of $BLER_{D_{i}-AP}$. For smaller coding rates only improvements of $G_{r-max}$ are provided for uniformly distributed $BLER_{D_{i}-AP}$ values.

The previous performance evaluations were realized in the worst case condition regarding the NC-decoder error probability $PE_{bl(D_{i})}$, i.e., all nodes of the cluster, excepting maybe $D_{i}$ (the node whose performance are analyzed), were involved in NC operation (i.e., $N_{D} = N_{Dc}$), or all nodes selected by the GA are involved in NC operations (i.e., $N_{NC} = N_{Dc}$). But due to the non-ideal $D_{i}-RN$ links, only the nodes whose blocks are correctly decoded by the RN are network coded, i.e., $N_{Dc} < N_{D}$ or $N_{Dc} < N_{NC}$, which decreases the coding rate of the RS code employed as network code. Figure 11 gives the average number of nodes involved in the NC operations vs. the number of nodes in the cluster, for equal BLER and uniformly distributed BLER on the $D_{i}-RN$ links.

Fig. 11

The average no. of network coded nodes versus $BLER_{D_{i}-RN}$

The results show that for $BLER_{D_{i}-RN}$ values smaller than 0.1 the average number of network coded nodes is larger than 90 % of $N_{D}$, but if the $BLER_{D_{i}-RN}$ values are distributed in a larger interval, such as $[0.01, 0.4]$, the average number of NC coded nodes drops to 75–80 % of $N_{D}$, decreasing in this way the RS coding rate. Such great $BLER_{D_{i}-RN}$ values should be considered only when we have one RN/cluster and poor $D_{i}-RN$ links.

Figure 12 presents the $G_{av}$ BLER improvement factor provided in scenario A, characterized by uniformly distributed $BLER_{D_{i}-AP}$, in the case when the NC-decoder error probability, $PE_{bl(D_{i})}$, is computed considering the real number of nodes correctly decoded by RN, $N_{Dc} < N_{D}$ or $N_{Dc} < N_{NC}$ if GA based optimization is employed. It can be noticed the improvement of the BLER by taking into account the real RS coding rate. The results of Fig. 12 were obtained in the condition that 90 % of the nodes were correctly decoded by the RN and by considering several sets of the $BLER_{D_{i}-AP}$ and $BLER_{D_{i}-RN}$ probabilities generated according the uniform distribution (see scenario A). The BLER improvement factor provided by the GA optimized system also increases, but the additional gain brought by the optimization decreases with the decrease of the coding rate.

Fig. 12

$G_{av}$ BLER improvement factor versus $R_{NC}$, and the percentage of devices involved in network coding

6.2 NC and ARQ based transmissions resource efficiency evaluation

The following test scenarios were considered:

• (A) $N_{D}=8$, star topology, each node is located at one hop from the AP, all links (direct and relay links) have the same BLER, i.e. each link has the same SNR (Signal to Noise Ratio) and is using the same transmission/modulation technique;

• (B) $N_{D}=8$, tree test topology one, number of hops $z=4$, all links have the same BLER.

$N_{check} \in \{4, 8, 16 \}$, $N_{t} \in \{1, 2, 3 \}$.

In Fig. 13 are presented the BLER versus SNR performance of the network coded and ARQ enabled transmissions for the nodes of the star topology considered (scenario A). The BLER parameter is computed according to relations (12)–(15) for the network coded case respectively according to relations (19)–(23) for the ARQ case. The $BLER_{link}$ parameter is computed according to relations (1) and (2). The transmission rate parameters, $R_{NC}$ and $R_{ARQ}$, computed according to (26) and the rate of the RS code employed are also presented for each test case, the amount of resources required being proportional with $1/R_{transmission}$.

Fig. 13

BLER versus SNR performance of the network coded and ARQ transmissions in the case of the star test topology for various no. of retransmissions and coding rates

The obtained results show that for large BLER values the network coded transmission using a rate 2/3 RS code has the same BLER performance as the ARQ transmissions with one retransmission, i.e. $N_{t}=2$. For smaller values of BLER the network coded transmission has significantly better performance and the coded transmission requires less than half of the ARQ transmission’s resources. A network coded transmission using a rate 1/2 RS code has the same BLER performance as the ARQ transmission with two retransmissions, i.e. $N_{t}=3$, at large values of BLER, while for small BLER values the coded transmission has significantly better performance. The amount of resources required by the network coded transmission is again less than half of the resources required by the reference ARQ transmission. A coded transmission using a rate 1/3 RS code has significantly better performance, in the entire range of the BLER parameter, than the considered ARQ transmissions, while still requiring fewer resources. It is clear that for each $N_{t}$ value it is possible to find a coding solution with better performance and a smaller amount of necessary resources compared to the ARQ technique using $N_{t}$ transmissions.

In Fig. 14 are presented the BLER versus SNR performance of the network coded and ARQ enabled transmissions for the nodes of the tree topology considered (scenario B), nodes which are located at one hop distance from the AP.

Fig. 14

BLER versus SNR performance of the network coded and ARQ transmissions in the case of the tree test topology for various no. of retransmissions and coding rates

The conclusions obtained for the star topology are also valid in this case. For each number of transmissions, $N_{t}$, of the ARQ technique we can find a network coding solution which ensures better BLER performance and requires less resources, more exactly the maximum amount of resources required by the coding solution is around half of the resources required by the ARQ transmission.

The evaluations performed show that the BLER versus SNR performance of nodes located at 2, 3 and 4 hop distance from the AP are similar. Both in the case of the network coded and the ARQ transmissions, the BLER values of these nodes are slightly larger due to the effect of the multihop transmissions, but the conclusions obtained previously are perfectly valid.

7 Conclusions

The paper proposes a NC-based algorithm, which employes RS codes, for improving the transmission reliability in wireless sensor networks with cluster-tree topologies assisted by a relay node. The solution is highly scalable and requires minimal changes of the transmission schemes in order to integrate network coding techniques. The performance of the NC-based algorithm were evaluated for three scenarios with different distributions of the BLER values affecting the transmission paths connecting the nodes to the cluster head. The evaluation shows that significant gains in BLER can be obtained even for coding rates $R_{NC} > 0.8$.

The paper proposes a GA-based optimization method of the NC algorithm, which selects the nodes involved in the NC operation, targeting to maximize the cluster’s global performance. It is shown that the optimization process can improve acceptably the coding gain only for $R_{NC} > 0.85$. The evaluations considered both the case when all nodes are involved in network coding as well as the more real case when only a percentage of the cluster’s nodes are network coded.

The proposed NC-based error control algorithm was compared from the point of view of the BLER performance and the resource efficiency with classical ARQ transmission methods adapted for WSNs. The evaluations performed show that for similar or even significantly better BLER performance the proposed NC-based transmission method requires less network resources, being avoided the retransmissions of the lost data blocks transmitted over multi-hop paths. In this way the energy efficiency is improved, not being necessary to use energy (i.e. to allocate time slots) for retransmissions of the lost packets, while the amount of energy necessary (i.e. the number of time slots) to transmit the few NC check blocks is significantly lower. Due to the same reasons the network coded transmission ensures lower delays of the transmitted data blocks compared to the ARQ transmission, which is important in the case of industrial or other special monitoring applications.