# Enjoy the Benefit of Network Coding: Combat Pollution Attacks in 5G Multihop Networks

Authors: Jian Li; Tongtong Li; Jian Ren; Han-Chieh Chao
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

In the upcoming 5G era, many new types of networks will greatly expand the connectivity of the world such as vehicular ad hoc networks (VANETs), Internet of Things (IoT), and device-to-device communications (D2D). Network coding is a promising technology that can significantly improve the throughput and robustness of these emerging 5G multihop networks. However, network coding is generally very fragile to malicious attacks such as message content corruption and node compromise attacks. To take advantage of network coding in performance gain while refraining malicious network attacks is an interesting and challenging research issue. In this paper, we propose a new error-detection and error-correction (EDEC) scheme that can jointly detect and remove the malicious attacks based on the underlying error-control scheme for general multihop networks that can model the 5G multihop networks. The proposed scheme can increase the throughput for network with pollution attacks compared to existing error-detection based schemes. Then we propose a low-density parity check (LDPC) decoding based EDEC (LEDEC) scheme. Our theoretical analysis demonstrates that the LEDEC scheme can further increase the throughput for heavily polluted network environments. We also provide extensive performance evaluation and simulation results to validate the proposed schemes. This research ensures the expected performance gain for the application of network coding in the 5G network under malicious pollution attacks.


---

## Body

## 1. Introduction

Most of the newly emerging networks in the 5G communication network can be modeled using multihop networks, including vehicular ad hoc networks (VANETs), Internet of Things (IoT), and device-to-device communications (D2D). New computing frameworks in the 5G network such as fog computing [1] can also be categorized into multihop networks. The network throughput and robustness could be improved when network coding is utilized. Many researchers have proposed to adopt network coding in the upcoming 5G network, such as in [2–4]. The core notation of network coding is that it allows the participating nodes to encode incoming packets at intermediate network nodes in a way that when a sink receives the packets, it can recover the original message. Network coding provides a trade-off between maximum multicast flow rate and computational complexity.Network coding was first introduced in the seminal paper by Ahlswedeet al. [5]. Liet al. [6] formulated the multicast problem in network coding as the max-flow from the source to each receiving node. They proved that linear coding is sufficient to achieve the optimum. This work made network coding simpler and more practical. Koetter and Medard [7] have shown that linear codes are sufficient to achieve the multicast capacity by coding on a large enough field. Hoet al. [8] have shown that using of random linear network coding is a more practical way to design linear codes. Gkantsidis and Rodriguez [9] have applied the principles of random network coding to the context of peer-to-peer (P2P) content distribution and have shown that file downloading times can be reduced. Esmaeilzadehet al. [10] proposed to use feedback-free random linear network coding in broadcasting layered video streams over heterogeneous single-hop wireless networks. Wuet al. [2] designed an efficient data dissemination protocol for VANETs using network coding. Leiet al. [3] applied network coding in Named Data Networking (NDN) in the 5G IoT network and improved the content delivery efficiency. Chiet al. [4] proposed to jointly utilize D2D communication and network coding to achieve high communication reliability in the ultra-dense 5G cell deployment.However, in the context of network coding, all participating nodes must encode the incoming packets according to a fixed coding algorithm. If a packet from an intermediate relay node is corrupted or being tampered, the entire communication may be disrupted.The main purpose of this paper is to develop schemes that can combat network pollution and malicious attacks from the network nodes based on error-control coding in multihop networks. We propose a new scheme that combines error-detection and error-correcting (EDEC) to combat network pollution attacks. In our scheme, the original message symbol is first encoded using an error-control code before encoded by network coding and transmitted. The application of error-control code gives intermediate nodes the capability to detect possible errors or pollution of the message. Unlike the existing schemes, when an intermediate node detects an error, the packet will continue to be forwarded. As long as the errors are correctable, the sink nodes will be able to recover the corrupted packets and decode the original packet symbols. Then we further extend the EDEC scheme and propose LDPC based EDEC (LEDEC) scheme. In the LEDEC scheme we treat the packets as LDPC codewords at the sink nodes and use the belief propagation algorithm (BPA) to decode the LDPC code. It can guarantee a certain network throughput even for a heavily polluted network environment, while the throughput becomes very low for error-detection based schemes. Moreover, we mainly focus on the throughput impact brought by different strategies (discard versus keep) towards corrupted packets.The major contributions of this paper are the following:(i)
We propose an EDEC scheme by combining a modified error-control code and network coding. The proposed EDEC scheme can increase the throughput for network environment with pollution attacks compared to existing error-detection based schemes.(ii)
We propose the LEDEC scheme by augmenting the EDEC scheme with the LDPC decoding. The proposed LEDEC can further improve the throughput even for network environment with heavy pollution.(iii)
We conduct extensive simulations to evaluate the performance of the proposed schemes and demonstrate the advantage of the proposed schemes.The rest of this paper is organized as follows: Section2 presents the related work. Preliminaries for network coding, error-control coding and the proposed modified error-control code are discussed in Section 3. Adversary model is also presented in Section 3. The EDEC scheme and performance analysis are described in Section 4. Section 5 presents the LDPC decoding and analysis of the LEDEC scheme. We conclude in Section 6.


## 2. Related Work

Existing work on pollution elimination can largely be divided into error-detection based schemes and error-correction based schemes. For error-detection based schemes, the errors are normally detected at the intermediate forward nodes. For error-correction based schemes, the errors are generally corrected at the sink node.While the error-correction based schemes seem to be more appealing, the computational complexity for encoding and decoding is relatively high [11]. These schemes are generally designed based on knowledge of the network topology, which makes these schemes less flexible to the current networks. Jaggiet al. [12] introduced the first polynomial-time rate-optimal network codes to correct the errors brought by malicious nodes. They also gave the theoretical network capacity with the existence of malicious nodes. However, the communication overhead of the scheme is significant. In [13], the authors proposed a network error-correcting code that combines the nonlinear coding at the source node and linear coding at the intermediate nodes. The code can achieve higher transmission rate than linear network error-correcting codes with exponential encoding and decoding complexity.The limitations of error-correction based schemes make error-detection attractive in some network scenarios. Krohnet al. [14] proposed to use homomorphic hash functions to guarantee correctness of the network flow. The main idea is that each intermediate node will check the correctness of the packets through homomorphic hash functions. If a packet fails the correctness check at an intermediate node, it will be discarded. This approach can reduce the communication overhead and can be used in random network coding. However, the computational complexity is still very high. When the network scale is large, computing too many hash values will also create high delay. Bonehet al. [15] provided cryptographic protection against pollution attacks by authenticating linear subspaces in network coding, which incurs less computation delay than [14]. Shanget al. [16] proposed new homomorphic signature schemes for generation-based network coding.In [17–20], homomorphic message authentication codes (MAC) were designed to detect polluted packets. Yuet al. [17] applied multiple MACs to each packet in secure XOR network coding to filter out polluted packets. Agrawalet al. [18] also designed a homomorphic MAC to check the integrity of network coded data with less computational overhead. Liet al. [19] proposed to use a symmetric key based homomorphic MAC algorithms to detect corrupted packets. In [21], the authors analyzed and improved two homomorphic authentication schemes homomorphic subspace signature (HSS) [22] and key predistribution-based tag encoding (KEPTE) [23] for network coding.To further reduce computational and communication overhead, Kehdiet al. [24] developed a simple error-detection basedNull Key scheme. Their idea is to partition the n-dimensional linear space over GF(qn) into two orthogonal subspaces of dimension k (symbol subspace) and n-k (null key space). Comparing to the homomorphic hash function, the null key scheme is more efficient and has virtually no message delay. Newellet al. [25] improved the work of [24] by splitting the null key into one large constant portion and another small periodically updated portion, making it more suitable for network coding in wireless environments.For all these error-detection based schemes, corrupted packets will be discarded. In packetized networks, a large message is divided into small packets. If a malicious node is able to continuously corrupt even a small fragment (packet) of the message, this fragment will be discarded. As a result, the whole message will be corrupted and the effective throughput will become lower and even close to zero in extreme situations. In our previous work [26], we proposed to keep the corrupted packets instead of dropping them; thus we could decode the corrupted packets in the intermediate forwarding nodes based on the subspace properties. In this paper we further generalize the idea and combine both error-detection and error-correction to guarantee a high throughput even for heavily polluted network environment.It is worth noting here that the authors in [27] proposed using a cooperative nonparametric statistical framework (COPS) for misbehavior mitigation in network coding. Their framework does not need the knowledge of the data packet contents and provides another possible way to combat the network pollution attacks.


## 3. Preliminaries

In this section, we will first introduce basic concepts and notations of network coding. Then we will present the preliminary for error-control code and our proposed modified error-control code, which is the base of our proposed schemes. At last we will present our adversarial model adopted in this paper.


### 3.1. Network Coding

The main idea of network coding can be illustrated through the butterfly graph [6] in Figure 1. Assume the capacity of all the edges is C; the capacity of this network is 2C according to the max-flow min-cut theorem. Only by encoding the incoming bits x1, x2 at node 3, this network can achieve the maximum capacity.Figure 1
A simple example of network coding.In this paper, we adopt the notations of [7]. A network is equivalent to a directed graph G=(V,E), where V represents the set of vertices corresponding to the network nodes and E represents all the directed edges between vertices corresponding to the communication link. The start vertex v of an edge e is called the tail of e and written as v=tail(e), while the end vertex u of an edge e is called the head of of e and written as u=head(e).For a source nodeu, there is a set of symbols X(u)=(x1,…,xl) to be sent, where xi∈GF(2n),1≤i≤l. For a link e between relay nodes r1 and r2, written as e=(r1,r2), the symbol ye transmitted on it is the function of all the ye′ such that head(e′)=r1. And ye can be written as(1)ye=∑e′:heade′=r1βe′,e·ye′=∑i=1lβe,ixi=βex1x2⋮xl,where βe′,e∈GF(2) is the local network encoding coefficient, βe,i∈GF(2) is the global network encoding coefficient for symbol ye, and βe=βe,1,βe,2,…,βe,l is the network encoding vector. For a sink node v, there is a set of incoming symbols y1,…,ym from e′ where tail(e′)=v to be decoded.For network coding to achieve the expected benefits, all the participating nodes in the network should be free of network pollution and malicious attacks. Suppose, under the linear network coding, the sink node receivesm packet symbols y1,…,ym. It decodes the original message symbols x1,…,xl by solving a set of linear equations:(2)β1β2⋮βmx1x2⋮xl=β11…β1lβ21…β2l⋮⋱⋮βm1…βmlx1x2⋮xl=y1y2⋮ym.For clarity purpose, we number the network coding vectors βe received in the sink node from 1 to m. If all the relay nodes encode correctly and m≥l, the sink node can decode all the message symbols successfully.


### 3.2. Error-Control Coding

#### 3.2.1. Error-Detection

Suppose the original message symbols are in thek-dimensional linear space over GF(2k). After we encode the symbols using the k×n generating matrix G of an (n,k) block code, the encoded codewords will form a linear subspace over GF(2n) of dimension k. So there will be another n-k dimensional subspace over the n dimensional space, which is orthogonal to the codewords subspace. Denote a valid codeword by c and the bases for the n-k dimensional subspace by h1,…,hn-k; we have <c,hi>=0,1≤i≤n-k, where <·,·> represents the inner product.Let(n-k)×n matrix H=h1T,…,hn-kTT; H forms a parity check matrix of the codewords and satisfies(3)c·HT=0.Suppose r=c+e is a received codeword, where e is an n-tuple error generated by a malicious node. For the received word r, we can get thesyndrome of error pattern e as follows:(4)s=r·HT=c+e·HT=c·HT+e·HT=e·HT.For a received codewordr, there are two cases: (i) e equals to a legitimate codeword generated by G. In this case, although r contains error, the error is undetectable using conventional error-control coding techniques; (ii) e contains a nonzero projection to the orthogonal parity check subspace, which satisfies r·HT≠0. In this case, we can detect that the received word contains error.In network coding, supposecj’s are a set of valid codewords, c=∑jβjcj is a linear combination of these codewords, where βj is the network encoding coefficient. It can be easily verified that for 1≤i≤n-k,(5)c·hiT=∑jβjcj·hiT=0.Equation (5) ensures that we can still check the correctness of packet symbols using row vectors of H after they are encoded by network coding. Similar to [24], we call the row vectors hi,1≤i≤n-k null keys.


#### 3.2.2. Error-Correction

From (4), it is clear that r is a codeword if and only if s=0. The task of maximum likelihood decoding is to find the minimum weight error pattern e such that r·HT=e·HT. In this case, the received r is corrected to r+e=c.In linear network coding, although the packet symbols are not the original ones sent from source nodes, we can still perform error-correction using (4). Suppose r1,…,ri are received codewords from i incoming edges; e is the error vector added to the network encoding r=∑jβjrj and r′=r+e. If the error is within the correction capability of the error-control code, the syndrome will still be r′·HT=e·HT+∑jβjrj·HT=e·HT+0=e·HT. Thus we can correct the error using syndrome decoding.The error-detection and error-correction capabilities are determined by the(n,k) code structure. Based on the pollution levels of the network, we can select the error-control codes accordingly base on the following proposition.Proposition 1 (see [28]).
For an(n,k) block code with the minimum distance D, it can detect all the D-1 or less errors, or it can correct all the ⌊(D-1)/2⌋ or less errors.In our proposed schemes, the corrupted packets detected at the intermediate nodes will not be discarded. Both the intact and corrupted packets will be gathered by the sink nodes. The sink nodes can correct the corrupted packets and have a higher communication throughput than the error-detection based schemes.


### 3.3. Modified Error-Control Code

The error-detection based schemes mainly focus on detecting the corrupt packets. As mentioned in Section2, when a corrupt packet is detected, it will be discarded. So if an adversary continues to corrupt certain packets, these packets will be continuously dropped and the communication may never succeed. In this paper we try to utilize the corrupted packets to improve the throughput in these situations. To achieve this goal, we need to propose a modified error-control code.


#### 3.3.1. Limitations of Conventional Error-Control Code

A linear error-correcting code encodes the originalk bits message symbol m to an n bits codeword c using a k×n generating matrix G. Suppose the minimum distance is D, according to the results in Section 3.2.2, the maximum number of errors we can correct is ⌊(D-1)/2⌋. If the number of errors is more than this amount, we may correct the corrupted codeword into a false one, as illustrated in Figure 2.Figure 2
Limitations of error-control codes.


#### 3.3.2. Proposed Error-Control Code That Can Detect Erroneous Decodings

The conventional error-control code may have undetected decoding errors. This is an inherent nature. No matter how low we set the code rate, these undetected errors may still exist. The decoding errors can only be detected using mechanisms other than a stand-alone error-correcting code.Therefore, we propose to apply modified error-control code to both message symbols and network coding coefficients in (1). In this section, we will use the message symbol as an example. The original message symbol m is first mapped to a t bit value h using homomorphic hashes. Then h will be appended to m to form a new k+t bits message symbol. By encoding this new message symbol we can get the final codeword. So the code becomes an (n,k+t) code. By adding the extra bits, we can mitigate limitations of the conventional error-control code. Figure 3 illustrates the modified encoding scheme.Figure 3
The encoding process of modified error-control code in EDEC scheme.At the sink nodes, the decoded symbol is first split into two partsm′ and h′ after the decoding as shown in Figure 4. Then we calculate the mapping h′′ from m′. If h′′ and h′ are different, we can detect a decoding error. Our modification is equivalent to choose 2k message symbols from 2k+t symbols. Other message symbols in the 2k+t symbol space are considered to be illegal. Because the decoding algorithm only guarantees that the decoded codeword is in the k+t dimensional subspace, the decoded codeword belonging to the 2k+t-2k symbol space implies that the decoding contains error.Figure 4
The decoding process of modified error-control code in EDEC scheme.Theorem 2.
Suppose a decoding error occurs, the wrong codeword will be any codeword in the2k+t symbol space. So the probability of detecting an erroneous decoding is(6)p=2k+t-2k2k+t=2t-12t=1-12t.Through properly choosing the parametersk,t, we can detect erroneous decodings with little additional overhead.


### 3.4. Adversary Model

In network coding, a small error injected into an intermediate relay node may diffuse to many packets at the sink node, which will incur errors in the message symbols after the solving of (2). This can cause a significant waste of network resources and sometimes can even ruin the whole network communication. This kind of attack is calledpollution attack.In this paper, we assume that the malicious node can inject bogus packets into the network. If the succeeding relay nodes do not detect the bogus packets and produce network coded packets using the bogus packets, we call these packetscorrupted packets. The malicious nodes try to forge legitimate packets that can pass the check in (5). In error-detection based schemes that use null keys to check the validity of packet symbols, the source node will randomly distribute s null keys in each intermediate relay node for packet checking. The malicious node can increase its successful attack probability by producing bogus symbols orthogonal to the space spanned by the s null keys it receives.When the size of the generating matrix is large, we will use sparse matricesG and H to reduce the encoding and decoding complexity. Suppose there are b1’s in each row and in each column on average in matrix F=GH for b≪n, we have the following theorem.Theorem 3.
The probabilitypm that a malicious node successfully forges a valid symbol is (7)pm=kbwn-sbw,where nk is the number of k-combinations from a set of n elements and w≪n is the number of 1’s in a bogus symbol.Proof (sketch).
When the number of errors, which are1’s in the bogus symbol, is small compared to n, for each error bit with index i there will be b distinct vectors with 1’s at the index i in F. The bogus symbol will be linear dependent with these b vectors with high probability. Thus a bogus symbol with w errors (w≪n) will be linear dependent with at most bw vectors, which may include rows from both matrices G and H.
When a malicious node forges a symbol which is only linear dependent with the row vectors inG, it will successfully forge a valid symbol. Since the malicious node does not know the row vectors of the matrices G and H except for the null key vectors it has, these row vectors can be viewed as random to the malicious node. The successfully probability is the number of ways of choosing bw vectors in all the row vectors of G divided by that of choosing bw vectors in all the row vectors of F excluding the s null key vectors the malicious node has already known.For largen,k, the malicious node has to make w small to achieve a high probability pm. In a typical parameter setting with n=3232, k=3072, b=3, s=40, each intermediate node will receive 40 null keys randomly selected from 160 null keys. The successful probability of forging a valid symbol is shown in Figure 5. From the figure we can see that to achieve successful probability pm=0.5, the malicious node can only add 6 errors into a forged symbol, which are easily correctable by the (3232, 3072) code with minimum distance D=161.Thus for the malicious node, in order to produce bogus symbols that can pass the check, it will forge symbols with a small number of errors (1’s) and orthogonal to the null key vectors it has.Figure 5
Probability for a forged symbol to pass the check.For the error-control code used to detect the bogus symbols, the errors within the bogus symbols are correctable. However, in the error-detection based schemes that do not perform error-correcting, the bogus symbols that pass the intermediate check will result in a failure of decoding the original message symbols at sink nodes.


## 3.1. Network Coding

The main idea of network coding can be illustrated through the butterfly graph [6] in Figure 1. Assume the capacity of all the edges is C; the capacity of this network is 2C according to the max-flow min-cut theorem. Only by encoding the incoming bits x1, x2 at node 3, this network can achieve the maximum capacity.Figure 1
A simple example of network coding.In this paper, we adopt the notations of [7]. A network is equivalent to a directed graph G=(V,E), where V represents the set of vertices corresponding to the network nodes and E represents all the directed edges between vertices corresponding to the communication link. The start vertex v of an edge e is called the tail of e and written as v=tail(e), while the end vertex u of an edge e is called the head of of e and written as u=head(e).For a source nodeu, there is a set of symbols X(u)=(x1,…,xl) to be sent, where xi∈GF(2n),1≤i≤l. For a link e between relay nodes r1 and r2, written as e=(r1,r2), the symbol ye transmitted on it is the function of all the ye′ such that head(e′)=r1. And ye can be written as(1)ye=∑e′:heade′=r1βe′,e·ye′=∑i=1lβe,ixi=βex1x2⋮xl,where βe′,e∈GF(2) is the local network encoding coefficient, βe,i∈GF(2) is the global network encoding coefficient for symbol ye, and βe=βe,1,βe,2,…,βe,l is the network encoding vector. For a sink node v, there is a set of incoming symbols y1,…,ym from e′ where tail(e′)=v to be decoded.For network coding to achieve the expected benefits, all the participating nodes in the network should be free of network pollution and malicious attacks. Suppose, under the linear network coding, the sink node receivesm packet symbols y1,…,ym. It decodes the original message symbols x1,…,xl by solving a set of linear equations:(2)β1β2⋮βmx1x2⋮xl=β11…β1lβ21…β2l⋮⋱⋮βm1…βmlx1x2⋮xl=y1y2⋮ym.For clarity purpose, we number the network coding vectors βe received in the sink node from 1 to m. If all the relay nodes encode correctly and m≥l, the sink node can decode all the message symbols successfully.


## 3.2. Error-Control Coding

### 3.2.1. Error-Detection

Suppose the original message symbols are in thek-dimensional linear space over GF(2k). After we encode the symbols using the k×n generating matrix G of an (n,k) block code, the encoded codewords will form a linear subspace over GF(2n) of dimension k. So there will be another n-k dimensional subspace over the n dimensional space, which is orthogonal to the codewords subspace. Denote a valid codeword by c and the bases for the n-k dimensional subspace by h1,…,hn-k; we have <c,hi>=0,1≤i≤n-k, where <·,·> represents the inner product.Let(n-k)×n matrix H=h1T,…,hn-kTT; H forms a parity check matrix of the codewords and satisfies(3)c·HT=0.Suppose r=c+e is a received codeword, where e is an n-tuple error generated by a malicious node. For the received word r, we can get thesyndrome of error pattern e as follows:(4)s=r·HT=c+e·HT=c·HT+e·HT=e·HT.For a received codewordr, there are two cases: (i) e equals to a legitimate codeword generated by G. In this case, although r contains error, the error is undetectable using conventional error-control coding techniques; (ii) e contains a nonzero projection to the orthogonal parity check subspace, which satisfies r·HT≠0. In this case, we can detect that the received word contains error.In network coding, supposecj’s are a set of valid codewords, c=∑jβjcj is a linear combination of these codewords, where βj is the network encoding coefficient. It can be easily verified that for 1≤i≤n-k,(5)c·hiT=∑jβjcj·hiT=0.Equation (5) ensures that we can still check the correctness of packet symbols using row vectors of H after they are encoded by network coding. Similar to [24], we call the row vectors hi,1≤i≤n-k null keys.


### 3.2.2. Error-Correction

From (4), it is clear that r is a codeword if and only if s=0. The task of maximum likelihood decoding is to find the minimum weight error pattern e such that r·HT=e·HT. In this case, the received r is corrected to r+e=c.In linear network coding, although the packet symbols are not the original ones sent from source nodes, we can still perform error-correction using (4). Suppose r1,…,ri are received codewords from i incoming edges; e is the error vector added to the network encoding r=∑jβjrj and r′=r+e. If the error is within the correction capability of the error-control code, the syndrome will still be r′·HT=e·HT+∑jβjrj·HT=e·HT+0=e·HT. Thus we can correct the error using syndrome decoding.The error-detection and error-correction capabilities are determined by the(n,k) code structure. Based on the pollution levels of the network, we can select the error-control codes accordingly base on the following proposition.Proposition 1 (see [28]).
For an(n,k) block code with the minimum distance D, it can detect all the D-1 or less errors, or it can correct all the ⌊(D-1)/2⌋ or less errors.In our proposed schemes, the corrupted packets detected at the intermediate nodes will not be discarded. Both the intact and corrupted packets will be gathered by the sink nodes. The sink nodes can correct the corrupted packets and have a higher communication throughput than the error-detection based schemes.


## 3.2.1. Error-Detection

Suppose the original message symbols are in thek-dimensional linear space over GF(2k). After we encode the symbols using the k×n generating matrix G of an (n,k) block code, the encoded codewords will form a linear subspace over GF(2n) of dimension k. So there will be another n-k dimensional subspace over the n dimensional space, which is orthogonal to the codewords subspace. Denote a valid codeword by c and the bases for the n-k dimensional subspace by h1,…,hn-k; we have <c,hi>=0,1≤i≤n-k, where <·,·> represents the inner product.Let(n-k)×n matrix H=h1T,…,hn-kTT; H forms a parity check matrix of the codewords and satisfies(3)c·HT=0.Suppose r=c+e is a received codeword, where e is an n-tuple error generated by a malicious node. For the received word r, we can get thesyndrome of error pattern e as follows:(4)s=r·HT=c+e·HT=c·HT+e·HT=e·HT.For a received codewordr, there are two cases: (i) e equals to a legitimate codeword generated by G. In this case, although r contains error, the error is undetectable using conventional error-control coding techniques; (ii) e contains a nonzero projection to the orthogonal parity check subspace, which satisfies r·HT≠0. In this case, we can detect that the received word contains error.In network coding, supposecj’s are a set of valid codewords, c=∑jβjcj is a linear combination of these codewords, where βj is the network encoding coefficient. It can be easily verified that for 1≤i≤n-k,(5)c·hiT=∑jβjcj·hiT=0.Equation (5) ensures that we can still check the correctness of packet symbols using row vectors of H after they are encoded by network coding. Similar to [24], we call the row vectors hi,1≤i≤n-k null keys.


## 3.2.2. Error-Correction

From (4), it is clear that r is a codeword if and only if s=0. The task of maximum likelihood decoding is to find the minimum weight error pattern e such that r·HT=e·HT. In this case, the received r is corrected to r+e=c.In linear network coding, although the packet symbols are not the original ones sent from source nodes, we can still perform error-correction using (4). Suppose r1,…,ri are received codewords from i incoming edges; e is the error vector added to the network encoding r=∑jβjrj and r′=r+e. If the error is within the correction capability of the error-control code, the syndrome will still be r′·HT=e·HT+∑jβjrj·HT=e·HT+0=e·HT. Thus we can correct the error using syndrome decoding.The error-detection and error-correction capabilities are determined by the(n,k) code structure. Based on the pollution levels of the network, we can select the error-control codes accordingly base on the following proposition.Proposition 1 (see [28]).
For an(n,k) block code with the minimum distance D, it can detect all the D-1 or less errors, or it can correct all the ⌊(D-1)/2⌋ or less errors.In our proposed schemes, the corrupted packets detected at the intermediate nodes will not be discarded. Both the intact and corrupted packets will be gathered by the sink nodes. The sink nodes can correct the corrupted packets and have a higher communication throughput than the error-detection based schemes.


## 3.3. Modified Error-Control Code

The error-detection based schemes mainly focus on detecting the corrupt packets. As mentioned in Section2, when a corrupt packet is detected, it will be discarded. So if an adversary continues to corrupt certain packets, these packets will be continuously dropped and the communication may never succeed. In this paper we try to utilize the corrupted packets to improve the throughput in these situations. To achieve this goal, we need to propose a modified error-control code.


### 3.3.1. Limitations of Conventional Error-Control Code

A linear error-correcting code encodes the originalk bits message symbol m to an n bits codeword c using a k×n generating matrix G. Suppose the minimum distance is D, according to the results in Section 3.2.2, the maximum number of errors we can correct is ⌊(D-1)/2⌋. If the number of errors is more than this amount, we may correct the corrupted codeword into a false one, as illustrated in Figure 2.Figure 2
Limitations of error-control codes.


### 3.3.2. Proposed Error-Control Code That Can Detect Erroneous Decodings

The conventional error-control code may have undetected decoding errors. This is an inherent nature. No matter how low we set the code rate, these undetected errors may still exist. The decoding errors can only be detected using mechanisms other than a stand-alone error-correcting code.Therefore, we propose to apply modified error-control code to both message symbols and network coding coefficients in (1). In this section, we will use the message symbol as an example. The original message symbol m is first mapped to a t bit value h using homomorphic hashes. Then h will be appended to m to form a new k+t bits message symbol. By encoding this new message symbol we can get the final codeword. So the code becomes an (n,k+t) code. By adding the extra bits, we can mitigate limitations of the conventional error-control code. Figure 3 illustrates the modified encoding scheme.Figure 3
The encoding process of modified error-control code in EDEC scheme.At the sink nodes, the decoded symbol is first split into two partsm′ and h′ after the decoding as shown in Figure 4. Then we calculate the mapping h′′ from m′. If h′′ and h′ are different, we can detect a decoding error. Our modification is equivalent to choose 2k message symbols from 2k+t symbols. Other message symbols in the 2k+t symbol space are considered to be illegal. Because the decoding algorithm only guarantees that the decoded codeword is in the k+t dimensional subspace, the decoded codeword belonging to the 2k+t-2k symbol space implies that the decoding contains error.Figure 4
The decoding process of modified error-control code in EDEC scheme.Theorem 2.
Suppose a decoding error occurs, the wrong codeword will be any codeword in the2k+t symbol space. So the probability of detecting an erroneous decoding is(6)p=2k+t-2k2k+t=2t-12t=1-12t.Through properly choosing the parametersk,t, we can detect erroneous decodings with little additional overhead.


## 3.3.1. Limitations of Conventional Error-Control Code

A linear error-correcting code encodes the originalk bits message symbol m to an n bits codeword c using a k×n generating matrix G. Suppose the minimum distance is D, according to the results in Section 3.2.2, the maximum number of errors we can correct is ⌊(D-1)/2⌋. If the number of errors is more than this amount, we may correct the corrupted codeword into a false one, as illustrated in Figure 2.Figure 2
Limitations of error-control codes.


## 3.3.2. Proposed Error-Control Code That Can Detect Erroneous Decodings

The conventional error-control code may have undetected decoding errors. This is an inherent nature. No matter how low we set the code rate, these undetected errors may still exist. The decoding errors can only be detected using mechanisms other than a stand-alone error-correcting code.Therefore, we propose to apply modified error-control code to both message symbols and network coding coefficients in (1). In this section, we will use the message symbol as an example. The original message symbol m is first mapped to a t bit value h using homomorphic hashes. Then h will be appended to m to form a new k+t bits message symbol. By encoding this new message symbol we can get the final codeword. So the code becomes an (n,k+t) code. By adding the extra bits, we can mitigate limitations of the conventional error-control code. Figure 3 illustrates the modified encoding scheme.Figure 3
The encoding process of modified error-control code in EDEC scheme.At the sink nodes, the decoded symbol is first split into two partsm′ and h′ after the decoding as shown in Figure 4. Then we calculate the mapping h′′ from m′. If h′′ and h′ are different, we can detect a decoding error. Our modification is equivalent to choose 2k message symbols from 2k+t symbols. Other message symbols in the 2k+t symbol space are considered to be illegal. Because the decoding algorithm only guarantees that the decoded codeword is in the k+t dimensional subspace, the decoded codeword belonging to the 2k+t-2k symbol space implies that the decoding contains error.Figure 4
The decoding process of modified error-control code in EDEC scheme.Theorem 2.
Suppose a decoding error occurs, the wrong codeword will be any codeword in the2k+t symbol space. So the probability of detecting an erroneous decoding is(6)p=2k+t-2k2k+t=2t-12t=1-12t.Through properly choosing the parametersk,t, we can detect erroneous decodings with little additional overhead.


## 3.4. Adversary Model

In network coding, a small error injected into an intermediate relay node may diffuse to many packets at the sink node, which will incur errors in the message symbols after the solving of (2). This can cause a significant waste of network resources and sometimes can even ruin the whole network communication. This kind of attack is calledpollution attack.In this paper, we assume that the malicious node can inject bogus packets into the network. If the succeeding relay nodes do not detect the bogus packets and produce network coded packets using the bogus packets, we call these packetscorrupted packets. The malicious nodes try to forge legitimate packets that can pass the check in (5). In error-detection based schemes that use null keys to check the validity of packet symbols, the source node will randomly distribute s null keys in each intermediate relay node for packet checking. The malicious node can increase its successful attack probability by producing bogus symbols orthogonal to the space spanned by the s null keys it receives.When the size of the generating matrix is large, we will use sparse matricesG and H to reduce the encoding and decoding complexity. Suppose there are b1’s in each row and in each column on average in matrix F=GH for b≪n, we have the following theorem.Theorem 3.
The probabilitypm that a malicious node successfully forges a valid symbol is (7)pm=kbwn-sbw,where nk is the number of k-combinations from a set of n elements and w≪n is the number of 1’s in a bogus symbol.Proof (sketch).
When the number of errors, which are1’s in the bogus symbol, is small compared to n, for each error bit with index i there will be b distinct vectors with 1’s at the index i in F. The bogus symbol will be linear dependent with these b vectors with high probability. Thus a bogus symbol with w errors (w≪n) will be linear dependent with at most bw vectors, which may include rows from both matrices G and H.
When a malicious node forges a symbol which is only linear dependent with the row vectors inG, it will successfully forge a valid symbol. Since the malicious node does not know the row vectors of the matrices G and H except for the null key vectors it has, these row vectors can be viewed as random to the malicious node. The successfully probability is the number of ways of choosing bw vectors in all the row vectors of G divided by that of choosing bw vectors in all the row vectors of F excluding the s null key vectors the malicious node has already known.For largen,k, the malicious node has to make w small to achieve a high probability pm. In a typical parameter setting with n=3232, k=3072, b=3, s=40, each intermediate node will receive 40 null keys randomly selected from 160 null keys. The successful probability of forging a valid symbol is shown in Figure 5. From the figure we can see that to achieve successful probability pm=0.5, the malicious node can only add 6 errors into a forged symbol, which are easily correctable by the (3232, 3072) code with minimum distance D=161.Thus for the malicious node, in order to produce bogus symbols that can pass the check, it will forge symbols with a small number of errors (1’s) and orthogonal to the null key vectors it has.Figure 5
Probability for a forged symbol to pass the check.For the error-control code used to detect the bogus symbols, the errors within the bogus symbols are correctable. However, in the error-detection based schemes that do not perform error-correcting, the bogus symbols that pass the intermediate check will result in a failure of decoding the original message symbols at sink nodes.


## 4. Proposed EDEC Scheme and Evaluation

Similar to the null key scheme, our approach also utilizes the orthogonal space properties of the error-control code, but we use both the error-detection and error-correction techniques. The source node will encode the original message symbols using the modified error-control code prior to message transmission as shown in Figure6. The properties of the error-control code keep unchanged during the linear network coding. When a corrupted packet is detected, instead of dropping it, we forward it to the sink nodes so that the packet can be used along with other packets to recover the original messages. However, the corrupted packet will not participate in network coding in the subsequent relay nodes once it is detected to be corrupted. The sink node can make use of the corrupted packets according to the decoding results of the modified error-control code in Section 3.3.Figure 6
Apply error-control codes in linear network coding.


### 4.1. The Proposed EDEC Scheme

The proposed EDEC scheme is divided into two phases: initialization phase and transmission phase. The initialization phase is for null key and security parameter distribution while packet symbols are transmitted through network coding in the transmission phase.


#### 4.1.1. Initialization Phase

In the initialization phase, the source node will first distributes row vectors of the parity check matrix orthogonal to G in Algorithm 1 (null keys) to each of the relay nodes through a secret transmission protocol. Unlike normal linear network coding in which the network encoding vectors are attached to the start or the end of the packets, we propose to distribute the encoded encoding vectors to predetermined secret locations in the packets. The source node will send the location information to all the sink nodes during the initialization phase through the secure transmission protocol. This will prevent the malicious nodes from corrupting the encoding vector, which is essential for the data decoding. Moreover, the source node will also send the encoding matrix Gc for network encoding vectors and G for packet symbols to all the sink nodes. Once the initialization phase is done, the source nodes can multicast any number of packets to sink nodes. The overhead of the initialization phase is negligible.Algorithm 1:EDEC algorithm for source nodes.
(1) for packet i do (2) //Encode network encoding vectorβiin equation (1) using the modified error-control code (Figure 3) (3)hc← map(βi) (4) uc←βi∣hc (5)  Encoded network encoding vector ←uc⋅Gc (6)  Distribute the encoded network encoding vector into predetermined locations of the packet (7) for every symbol m of the packet do (8) //Encodemusing the modified error-control code (Figure3) (9) h← map(m) (10) u←m∣h (11)  Encoded symbol ←u⋅G (12) end for (13)  Send out the encoded symbols (14) end for


#### 4.1.2. Transmission Phase

In the transmission phase, the source node, relay nodes, and sink nodes will perform the proposed EDEC scheme according to Algorithms1, 2, and 3.Algorithm 2:EDEC algorithm for relay nodes.
(1) ifevery symbol in the received packet is intact then (2) ifx (a predetermined number) packets received then (3)  Generate x randomly, linearly combined packets using the received packets (network coding) (4)  Send out the network encoded packets (5) end if (6) else (7)  Mark the packet as corrupted and send it out (8) end ifAlgorithm 3:EDEC algorithm for sink nodes.
(1) A packet is received (2) Decode every symbol in the packet using the decoding algorithm for the modified error-control code (Figure 4) (3) Reassemble the encoded network encoding vector from the predetermined secret locations and decode the network encoding vector (4) if the network encoding vector and all symbols are decoded correctly then (5)ifthe packet is independent then (6)  Save the packet (7) ifl (in equation (2)) independent packets are saved then (8)  Solve the network coding equations (9) end if (10) end if (11) end ifIn Algorithm1, the source node will encode the network encoding vector βi using the modified error-control code with a much longer appendix and a much lower code rate, compared to the encoding of packet symbols. This can improve the error resistance and detection probability for erroneous decodings to guarantee the correctness of the network encoding vectors used for data decoding. Since there is only one network encoding vector in each packet, the overhead brought by this higher security level is negligible.Algorithm2 presents the EDEC algorithm for relay nodes. Since the null key vectors are already distributed in the initialization phase, the relay nodes can check whether a packet is intact.Algorithm3 presents the EDEC algorithm for sink nodes. Since a sink node has already received the encoding matrix Gc and G in Algorithm 1 in the initialization phase, it can perform the error-control code decoding and detect the erroneous decodings. When collecting enough intact packets, it can derive the original data symbols through the decoding of network code.


### 4.2. Simulation Results of EDEC Scheme

In this section, we first present the simulation platform for EDEC scheme. Then we will compare the EDEC scheme and the error-detection based schemes, which are represented by the null key scheme in the simulation.


#### 4.2.1. Simulation Platform

We simulate the EDEC scheme using ns-2. The scenario is set as a grid network with one source node, a number of relay nodes, and sink nodes. All the nodes are set as wireless nodes using wireless physical layer and 802.11 MAC protocol. The wireless channel is set to TwoRayGround. Once a node receives a packet, it will start the corresponding operations depending on its type (source, relay, malicious, and sink) and the packet content.Figure7 shows the topology of the simulated network. The source node is located at the lower left corner and 13 sink nodes lie at the upper right. The rest of the nodes are all intermediate nodes that can relay packets. In the simulation, we randomly choose a number of intermediate nodes as malicious nodes to perform pollution attacks. These nodes try to send out bogus packets that can pass the intermediate check as described in Section 3.4 to pollute the network. We can change the number of malicious nodes to evaluate performance of the algorithms under different network conditions. The percentage of malicious nodes is about 20% in Figure 7. The rest of the intermediate nodes act as relay nodes. After receiving a packet, they will first conduct pollution detection. In the error-detection based schemes, if the packet is corrupted, it will be dropped. In our proposed EDEC scheme, we will continue to forward the corrupted packet to the sink nodes. However, the corrupted packet will not participate in the succeeding network coding. The nodes behaviors will be detailed in the next section.Figure 7
Simulation scenario.Because the packets are transmitted through broadcasting, although the MAC protocol is IEEE 802.11, we will still have packets collisions that will eventually influence the simulation results. In this paper, we only focus on evaluating the proposed EDEC and LEDEC schemes. According to the transmission range of a single node, adjacent nodes are assigned different time slots (see Figure8) to avoid packets collisions. This can guarantee that the transmission range belonging to the same time slot would not overlap. We divide the entire time duration into 9 time slots and the duration of each time slot is 100 ms. The nodes are allowed to send packets only if they are in their own slots. If not, they will have to wait until their next slots. In Figure 8 is an example in which the nodes belonging to time slot 2 can simultaneously transmit without packet collision.Figure 8
Illustration of the 9 time slots to avoid packets collisions.


#### 4.2.2. Nodes Design

Four types of nodes are designed according to the algorithms described in Section4.1 on the simulation platform.(a) Source Node. In the simulation, the source node has l=32 data packets to send. After initializing the network according to Section 4.1.1, the source node will encode the network encoding vector βi for each packet using the modified error-control code presented in Figure 3 with t=32. According to Theorem 2, the probability of detecting an erroneous decoding for the network encoding vector is 1-2-32, which means once the decoded network encoding vector passes the verification in Figure 4, we can view the network encoding vector as intact. Then the source node will distribute the encoded network encoding vector into predetermined locations in each packet. We fragment each packet embedding the encoded network encoding vector into symbols with the size 3056 bits and encode each packet symbol using the modified error-control code with t=16. At last, the encoded packets are sent out into the network.(b) Relay Nodes. Relay nodes will perform EDEC scheme according to Algorithm 2. Because the network is collision free and all the transmitted packets can be received, each packet only needs to be transmitted once. To utilize network coding efficiently while minimizing the transmission delay, each relay node will perform network encoding for every x=4 valid packets it receiveds.(c) Malicious Nodes. We assume that the malicious nodes will not perform network encoding. They only send out forged packets and conduct pollution attacks as described in Section 3.4.(d) Sink Nodes. Sink nodes will decode both the modified error-control code and network code according to Algorithm 3.


#### 4.2.3. Simulation Results

We conduct simulations under different percentages of malicious relay nodes. The throughput comparison between the EDEC scheme and the error-detection based schemes is shown in Figure9. From the figure we can see that the EDEC scheme outperforms the error-detection based schemes in throughput: (i) When the percentage of malicious nodes is less than 10%, the two schemes have almost the same performance. (ii) With the increasing of malicious nodes, the performance of error-detection based schemes degrades significantly, while the throughput of the EDEC scheme remains almost unchanged. (iii) When the percentage of malicious nodes is larger than 40%, the throughput of the EDEC scheme begins to decrease because the cumulative number of errors in packet symbols becomes too large to correct by the modified error-control code. The uncorrectable packet symbols have the same degrading effect on the throughput as the packets discarded in the error-detection based schemes.Figure 9
Throughput comparison between EDEC scheme and the error-detection schemes.


## 4.1. The Proposed EDEC Scheme

The proposed EDEC scheme is divided into two phases: initialization phase and transmission phase. The initialization phase is for null key and security parameter distribution while packet symbols are transmitted through network coding in the transmission phase.


### 4.1.1. Initialization Phase

In the initialization phase, the source node will first distributes row vectors of the parity check matrix orthogonal to G in Algorithm 1 (null keys) to each of the relay nodes through a secret transmission protocol. Unlike normal linear network coding in which the network encoding vectors are attached to the start or the end of the packets, we propose to distribute the encoded encoding vectors to predetermined secret locations in the packets. The source node will send the location information to all the sink nodes during the initialization phase through the secure transmission protocol. This will prevent the malicious nodes from corrupting the encoding vector, which is essential for the data decoding. Moreover, the source node will also send the encoding matrix Gc for network encoding vectors and G for packet symbols to all the sink nodes. Once the initialization phase is done, the source nodes can multicast any number of packets to sink nodes. The overhead of the initialization phase is negligible.Algorithm 1:EDEC algorithm for source nodes.
(1) for packet i do (2) //Encode network encoding vectorβiin equation (1) using the modified error-control code (Figure 3) (3)hc← map(βi) (4) uc←βi∣hc (5)  Encoded network encoding vector ←uc⋅Gc (6)  Distribute the encoded network encoding vector into predetermined locations of the packet (7) for every symbol m of the packet do (8) //Encodemusing the modified error-control code (Figure3) (9) h← map(m) (10) u←m∣h (11)  Encoded symbol ←u⋅G (12) end for (13)  Send out the encoded symbols (14) end for


### 4.1.2. Transmission Phase

In the transmission phase, the source node, relay nodes, and sink nodes will perform the proposed EDEC scheme according to Algorithms1, 2, and 3.Algorithm 2:EDEC algorithm for relay nodes.
(1) ifevery symbol in the received packet is intact then (2) ifx (a predetermined number) packets received then (3)  Generate x randomly, linearly combined packets using the received packets (network coding) (4)  Send out the network encoded packets (5) end if (6) else (7)  Mark the packet as corrupted and send it out (8) end ifAlgorithm 3:EDEC algorithm for sink nodes.
(1) A packet is received (2) Decode every symbol in the packet using the decoding algorithm for the modified error-control code (Figure 4) (3) Reassemble the encoded network encoding vector from the predetermined secret locations and decode the network encoding vector (4) if the network encoding vector and all symbols are decoded correctly then (5)ifthe packet is independent then (6)  Save the packet (7) ifl (in equation (2)) independent packets are saved then (8)  Solve the network coding equations (9) end if (10) end if (11) end ifIn Algorithm1, the source node will encode the network encoding vector βi using the modified error-control code with a much longer appendix and a much lower code rate, compared to the encoding of packet symbols. This can improve the error resistance and detection probability for erroneous decodings to guarantee the correctness of the network encoding vectors used for data decoding. Since there is only one network encoding vector in each packet, the overhead brought by this higher security level is negligible.Algorithm2 presents the EDEC algorithm for relay nodes. Since the null key vectors are already distributed in the initialization phase, the relay nodes can check whether a packet is intact.Algorithm3 presents the EDEC algorithm for sink nodes. Since a sink node has already received the encoding matrix Gc and G in Algorithm 1 in the initialization phase, it can perform the error-control code decoding and detect the erroneous decodings. When collecting enough intact packets, it can derive the original data symbols through the decoding of network code.


## 4.1.1. Initialization Phase

In the initialization phase, the source node will first distributes row vectors of the parity check matrix orthogonal to G in Algorithm 1 (null keys) to each of the relay nodes through a secret transmission protocol. Unlike normal linear network coding in which the network encoding vectors are attached to the start or the end of the packets, we propose to distribute the encoded encoding vectors to predetermined secret locations in the packets. The source node will send the location information to all the sink nodes during the initialization phase through the secure transmission protocol. This will prevent the malicious nodes from corrupting the encoding vector, which is essential for the data decoding. Moreover, the source node will also send the encoding matrix Gc for network encoding vectors and G for packet symbols to all the sink nodes. Once the initialization phase is done, the source nodes can multicast any number of packets to sink nodes. The overhead of the initialization phase is negligible.Algorithm 1:EDEC algorithm for source nodes.
(1) for packet i do (2) //Encode network encoding vectorβiin equation (1) using the modified error-control code (Figure 3) (3)hc← map(βi) (4) uc←βi∣hc (5)  Encoded network encoding vector ←uc⋅Gc (6)  Distribute the encoded network encoding vector into predetermined locations of the packet (7) for every symbol m of the packet do (8) //Encodemusing the modified error-control code (Figure3) (9) h← map(m) (10) u←m∣h (11)  Encoded symbol ←u⋅G (12) end for (13)  Send out the encoded symbols (14) end for


## 4.1.2. Transmission Phase

In the transmission phase, the source node, relay nodes, and sink nodes will perform the proposed EDEC scheme according to Algorithms1, 2, and 3.Algorithm 2:EDEC algorithm for relay nodes.
(1) ifevery symbol in the received packet is intact then (2) ifx (a predetermined number) packets received then (3)  Generate x randomly, linearly combined packets using the received packets (network coding) (4)  Send out the network encoded packets (5) end if (6) else (7)  Mark the packet as corrupted and send it out (8) end ifAlgorithm 3:EDEC algorithm for sink nodes.
(1) A packet is received (2) Decode every symbol in the packet using the decoding algorithm for the modified error-control code (Figure 4) (3) Reassemble the encoded network encoding vector from the predetermined secret locations and decode the network encoding vector (4) if the network encoding vector and all symbols are decoded correctly then (5)ifthe packet is independent then (6)  Save the packet (7) ifl (in equation (2)) independent packets are saved then (8)  Solve the network coding equations (9) end if (10) end if (11) end ifIn Algorithm1, the source node will encode the network encoding vector βi using the modified error-control code with a much longer appendix and a much lower code rate, compared to the encoding of packet symbols. This can improve the error resistance and detection probability for erroneous decodings to guarantee the correctness of the network encoding vectors used for data decoding. Since there is only one network encoding vector in each packet, the overhead brought by this higher security level is negligible.Algorithm2 presents the EDEC algorithm for relay nodes. Since the null key vectors are already distributed in the initialization phase, the relay nodes can check whether a packet is intact.Algorithm3 presents the EDEC algorithm for sink nodes. Since a sink node has already received the encoding matrix Gc and G in Algorithm 1 in the initialization phase, it can perform the error-control code decoding and detect the erroneous decodings. When collecting enough intact packets, it can derive the original data symbols through the decoding of network code.


## 4.2. Simulation Results of EDEC Scheme

In this section, we first present the simulation platform for EDEC scheme. Then we will compare the EDEC scheme and the error-detection based schemes, which are represented by the null key scheme in the simulation.


### 4.2.1. Simulation Platform

We simulate the EDEC scheme using ns-2. The scenario is set as a grid network with one source node, a number of relay nodes, and sink nodes. All the nodes are set as wireless nodes using wireless physical layer and 802.11 MAC protocol. The wireless channel is set to TwoRayGround. Once a node receives a packet, it will start the corresponding operations depending on its type (source, relay, malicious, and sink) and the packet content.Figure7 shows the topology of the simulated network. The source node is located at the lower left corner and 13 sink nodes lie at the upper right. The rest of the nodes are all intermediate nodes that can relay packets. In the simulation, we randomly choose a number of intermediate nodes as malicious nodes to perform pollution attacks. These nodes try to send out bogus packets that can pass the intermediate check as described in Section 3.4 to pollute the network. We can change the number of malicious nodes to evaluate performance of the algorithms under different network conditions. The percentage of malicious nodes is about 20% in Figure 7. The rest of the intermediate nodes act as relay nodes. After receiving a packet, they will first conduct pollution detection. In the error-detection based schemes, if the packet is corrupted, it will be dropped. In our proposed EDEC scheme, we will continue to forward the corrupted packet to the sink nodes. However, the corrupted packet will not participate in the succeeding network coding. The nodes behaviors will be detailed in the next section.Figure 7
Simulation scenario.Because the packets are transmitted through broadcasting, although the MAC protocol is IEEE 802.11, we will still have packets collisions that will eventually influence the simulation results. In this paper, we only focus on evaluating the proposed EDEC and LEDEC schemes. According to the transmission range of a single node, adjacent nodes are assigned different time slots (see Figure8) to avoid packets collisions. This can guarantee that the transmission range belonging to the same time slot would not overlap. We divide the entire time duration into 9 time slots and the duration of each time slot is 100 ms. The nodes are allowed to send packets only if they are in their own slots. If not, they will have to wait until their next slots. In Figure 8 is an example in which the nodes belonging to time slot 2 can simultaneously transmit without packet collision.Figure 8
Illustration of the 9 time slots to avoid packets collisions.


### 4.2.2. Nodes Design

Four types of nodes are designed according to the algorithms described in Section4.1 on the simulation platform.(a) Source Node. In the simulation, the source node has l=32 data packets to send. After initializing the network according to Section 4.1.1, the source node will encode the network encoding vector βi for each packet using the modified error-control code presented in Figure 3 with t=32. According to Theorem 2, the probability of detecting an erroneous decoding for the network encoding vector is 1-2-32, which means once the decoded network encoding vector passes the verification in Figure 4, we can view the network encoding vector as intact. Then the source node will distribute the encoded network encoding vector into predetermined locations in each packet. We fragment each packet embedding the encoded network encoding vector into symbols with the size 3056 bits and encode each packet symbol using the modified error-control code with t=16. At last, the encoded packets are sent out into the network.(b) Relay Nodes. Relay nodes will perform EDEC scheme according to Algorithm 2. Because the network is collision free and all the transmitted packets can be received, each packet only needs to be transmitted once. To utilize network coding efficiently while minimizing the transmission delay, each relay node will perform network encoding for every x=4 valid packets it receiveds.(c) Malicious Nodes. We assume that the malicious nodes will not perform network encoding. They only send out forged packets and conduct pollution attacks as described in Section 3.4.(d) Sink Nodes. Sink nodes will decode both the modified error-control code and network code according to Algorithm 3.


### 4.2.3. Simulation Results

We conduct simulations under different percentages of malicious relay nodes. The throughput comparison between the EDEC scheme and the error-detection based schemes is shown in Figure9. From the figure we can see that the EDEC scheme outperforms the error-detection based schemes in throughput: (i) When the percentage of malicious nodes is less than 10%, the two schemes have almost the same performance. (ii) With the increasing of malicious nodes, the performance of error-detection based schemes degrades significantly, while the throughput of the EDEC scheme remains almost unchanged. (iii) When the percentage of malicious nodes is larger than 40%, the throughput of the EDEC scheme begins to decrease because the cumulative number of errors in packet symbols becomes too large to correct by the modified error-control code. The uncorrectable packet symbols have the same degrading effect on the throughput as the packets discarded in the error-detection based schemes.Figure 9
Throughput comparison between EDEC scheme and the error-detection schemes.


## 4.2.1. Simulation Platform

We simulate the EDEC scheme using ns-2. The scenario is set as a grid network with one source node, a number of relay nodes, and sink nodes. All the nodes are set as wireless nodes using wireless physical layer and 802.11 MAC protocol. The wireless channel is set to TwoRayGround. Once a node receives a packet, it will start the corresponding operations depending on its type (source, relay, malicious, and sink) and the packet content.Figure7 shows the topology of the simulated network. The source node is located at the lower left corner and 13 sink nodes lie at the upper right. The rest of the nodes are all intermediate nodes that can relay packets. In the simulation, we randomly choose a number of intermediate nodes as malicious nodes to perform pollution attacks. These nodes try to send out bogus packets that can pass the intermediate check as described in Section 3.4 to pollute the network. We can change the number of malicious nodes to evaluate performance of the algorithms under different network conditions. The percentage of malicious nodes is about 20% in Figure 7. The rest of the intermediate nodes act as relay nodes. After receiving a packet, they will first conduct pollution detection. In the error-detection based schemes, if the packet is corrupted, it will be dropped. In our proposed EDEC scheme, we will continue to forward the corrupted packet to the sink nodes. However, the corrupted packet will not participate in the succeeding network coding. The nodes behaviors will be detailed in the next section.Figure 7
Simulation scenario.Because the packets are transmitted through broadcasting, although the MAC protocol is IEEE 802.11, we will still have packets collisions that will eventually influence the simulation results. In this paper, we only focus on evaluating the proposed EDEC and LEDEC schemes. According to the transmission range of a single node, adjacent nodes are assigned different time slots (see Figure8) to avoid packets collisions. This can guarantee that the transmission range belonging to the same time slot would not overlap. We divide the entire time duration into 9 time slots and the duration of each time slot is 100 ms. The nodes are allowed to send packets only if they are in their own slots. If not, they will have to wait until their next slots. In Figure 8 is an example in which the nodes belonging to time slot 2 can simultaneously transmit without packet collision.Figure 8
Illustration of the 9 time slots to avoid packets collisions.


## 4.2.2. Nodes Design

Four types of nodes are designed according to the algorithms described in Section4.1 on the simulation platform.(a) Source Node. In the simulation, the source node has l=32 data packets to send. After initializing the network according to Section 4.1.1, the source node will encode the network encoding vector βi for each packet using the modified error-control code presented in Figure 3 with t=32. According to Theorem 2, the probability of detecting an erroneous decoding for the network encoding vector is 1-2-32, which means once the decoded network encoding vector passes the verification in Figure 4, we can view the network encoding vector as intact. Then the source node will distribute the encoded network encoding vector into predetermined locations in each packet. We fragment each packet embedding the encoded network encoding vector into symbols with the size 3056 bits and encode each packet symbol using the modified error-control code with t=16. At last, the encoded packets are sent out into the network.(b) Relay Nodes. Relay nodes will perform EDEC scheme according to Algorithm 2. Because the network is collision free and all the transmitted packets can be received, each packet only needs to be transmitted once. To utilize network coding efficiently while minimizing the transmission delay, each relay node will perform network encoding for every x=4 valid packets it receiveds.(c) Malicious Nodes. We assume that the malicious nodes will not perform network encoding. They only send out forged packets and conduct pollution attacks as described in Section 3.4.(d) Sink Nodes. Sink nodes will decode both the modified error-control code and network code according to Algorithm 3.


## 4.2.3. Simulation Results

We conduct simulations under different percentages of malicious relay nodes. The throughput comparison between the EDEC scheme and the error-detection based schemes is shown in Figure9. From the figure we can see that the EDEC scheme outperforms the error-detection based schemes in throughput: (i) When the percentage of malicious nodes is less than 10%, the two schemes have almost the same performance. (ii) With the increasing of malicious nodes, the performance of error-detection based schemes degrades significantly, while the throughput of the EDEC scheme remains almost unchanged. (iii) When the percentage of malicious nodes is larger than 40%, the throughput of the EDEC scheme begins to decrease because the cumulative number of errors in packet symbols becomes too large to correct by the modified error-control code. The uncorrectable packet symbols have the same degrading effect on the throughput as the packets discarded in the error-detection based schemes.Figure 9
Throughput comparison between EDEC scheme and the error-detection schemes.


## 5. LDPC Decoding and LEDEC Scheme

In the EDEC scheme, only linearly independent packets participate in the network decoding at the sink nodes. Corrupted or linearly dependent packets will not be used, which is a waste of the resource. In this section, through utilizing these packets to recover more message symbols using low-density parity check (LDPC) decoding, we propose an LDPC decoding based EDEC (LEDEC) scheme.


### 5.1. LDPC Code

LDPC linear block code was first introduced by Gallager in 1962 [29]. One of the important characteristics of LDPC code is its sparse parity check matrix. By using iterative decoding, LDPC code can achieve error-correction performance close to Shannon bounds [30]. LDPC codes can be categorized as the regular LDPC code, of which the parity check matrix H has a fixed number of 1’s per column and per row, and the irregular LDPC code, of which the parity check matrix may have different numbers of 1’s in each column and each row. In this section, we will formulate the network coding to the irregular LDPC code.


### 5.2. Decoding of LDPC Code

The iterative decoding algorithm, known as belief propagation algorithm (BPA), is generally used to decode the LDPC code. Among all the channel models the BPA algorithm for the binary erasure channel (BEC) is the simplest, where only three numbers need to be considered:0, 1, and x (erasure). The BPA can be described over the Tanner graph [31], which is a bipartite graph. In a Tanner graph, there are two types of nodes: the symbol nodes (corresponding to the received bits) and the check nodes (corresponding to the rows of the parity check matrix). An illustrative example of the parity check matrix and its Tanner graph is shown in Figure 10. In the parity check matrix, every row represents a parity check equation. The symbol nodes, which correspond to the bits equal to 1’s in a row of the parity check matrix, are connected to the check node which corresponds to the same row. These nodes and edges in the Tanner graph express the parity check equation of that row. In Figure 10, node h1 represents the first row of the parity check matrix. The first, second, and third elements of the first row in parity check matrix are 1’s, so symbol nodes d1, d2, and d3 are connected to h1 in the Tanner graph.Figure 10
An illustrative example of parity check matrix and Tanner graph.The decoding algorithm can be described through Algorithm4.Algorithm 4:BPA decoding algorithm for BEC.
(1) while There are check nodes connected to only one unknown symbol node do (2) forEach of these check nodes do (3) The unknown symbol node ← xor (All of the other symbol nodes connected to the check node) (4) end for (5) end while (6) if All the unknown symbol nodes are recovered then (7)  Decode successfully (8) end if


### 5.3. Relationship between Linear Network Code and LDPC Code

In linear network coding, packets are linearly combined at the intermediate nodes. The packets received at the sink nodes satisfy (2). In the network code decoding part of the EDEC algorithm, only independent valid packets are used. However, there is also helpful information in the linearly dependent packets or corrupted packets. If we can exploit and use these packets, the system performance can be further improved. Denote the received encoding vector as βi=(βi,1,…,βi,l), where 1≤i≤m and m is the number of received packets. Then the generation matrix of the block network code GN can be defined as(8)GN=β1T⋯βlT,βl+1T⋯βmTT.As an example, suppose there is only one bit xi in each original packet of the source node for 1≤i≤l. Define x=x1,…,xlT. In this case, each received packet in the sink nodes also contains only one bit yj for 1≤j≤m. Denote all the m received packets as a vector y=y1,…,ymT. We have the following encoding equation:(9)y=GNx.Theorem 4.
The linear network code can be viewed as a rateless LDPC code and can be decoded using the BPA algorithm.Proof (sketch).
Since we can have an uncertain number ofm>l received encoded bits in the encoding equation (9), we can view the network code as a rateless code. The generating matrix GN can be rewritten as(10)GN=P1P2=IlP2P1-1P1,where matrix P1 can be made as an l×l full rank matrix through row exchange after l independent packets are received, P2 is an (m-l)×l matrix, and Il is an l×l identity matrix. The corresponding parity check matrix HN can be written as(11)HN=P2P1-1TIm-l,where Im-l is an (m-l)×(m-l) identity matrix. We can verify the correctness of HN by verifying the follow equation:(12)HNTGN=P2P1-1TIm-lTIlP2P1-1P1=0.After deriving the corresponding parity check matrix HN, we can decode the linear network code using the BPA algorithm. The linear network code can be viewed as a rateless LDPC code and has the property of error-control codes.Although linear network codes can be viewed as rateless LDPC codes, the BPA algorithm cannot be used to decode a network code if the network code is derived after the decoding of a conventional error-control code, because we cannot detect the incorrect decodings which should be viewed as erasures. For the modified error-control codes in the EDEC scheme, we can determine the erroneous decodings and mark the corresponding bits as erasures. Therefore, we can decode the linear network code using the BPA algorithm. Figure11 illustrates this main idea of the LEDEC scheme.Figure 11
Main idea of the LEDEC scheme.


### 5.4. Theoretical Analysis

Through the information in linearly dependent packets, the LEDEC scheme can get additional benefits from BPA decoding of the LDPC code. Consider the case in which the percentage of malicious nodes is high, most of the packets are corrupted by the malicious nodes. The error-detection based schemes cannot work because all of the packets are discarded. The EDEC scheme does not work well either because with high erasure probabilityPe there will not be enough correctable packets to solve the network coding equations (2).For the LEDEC scheme, letλd denote the probability that an edge from a check node is connected to a symbol node of degree d, and ρd denote the probability that an edge from a symbol node is connected to a check node of degree d in the Tanner graph of the corresponding LDPC code. The generating functions for an LDPC code is defined as: λ(x)=∑dλdxd-1, ρ(x)=∑dρdxd-1. According to [32], the maximal fraction of erasures that a random LDPC code with given generating functions can correct is bounded by Pmax=min⁡x/λ(1-ρ(1-x))(0<x<1) with probability at least 1-O(n-3/4), where n is the length of the code. For the throughput of the LEDEC scheme, we have Theorem 5.Theorem 5.
The throughput of the LEDEC scheme is(13)F=∑i=0N·PmaxNiPei1-PeN-i,where Pmax=min⁡x/λ(1-ρ(1-x))(0<x<1), Pe is the erasure probability, N is the number of packets a sink node received, and · is the floor function.Proof.
Suppose a sink node receivesN packets and the erasures in the packets are independent; the distribution of the number of erasures i in N received packet symbols is a binomial distribution with Pr(i)=NiPei1-PeN-i,0≤i≤N as the probability mass function (PMF).
The proposed scheme can combat all erasures up toN·Pmax with probability at least 1-O(N-3/4), which is close to 1. Thus the throughput can be written as F=∑i=0⌊N·Pmax⌋Pr(i).


### 5.5. Performance Analysis and Simulation

In this section, we provide simulation results of the LEDEC scheme on the simulation platform presented in Section4.2. All the settings and parameters are the same as in Section 4.2.


#### 5.5.1. Nodes Design

For the LEDEC scheme, the source node, relay nodes, and malicious nodes are the same as those in Section4.2. The decoding process in the sink nodes is different, in which all packets received will be used. The BPA decoding will not start until the sink nodes collect all the l=32 independent packets. After receiving l=32 independent packets, we can use the BPA algorithm to decode whenever a new packet arrives. However, there is a trade-off in determining when to start the BPA algorithm. When the algorithm is performed too frequently, the computational overhead will be high. On the other side, if we do not start the BPA decoding until we have collected a large number of packets, the communication delay will be high. To get a trade-off, the sink nodes will trigger the BPA decoding upon the receiving of every 10 new packets. This process will continue until all the message symbols have been successfully decoded.


#### 5.5.2. Simulation Results

Same as in Section4.2.3, the simulations in this section are carried out under different percentage of malicious relay nodes. One example of the parity check matrix (transposed) generated in the linear network coding is shown in Figure 12. In this example, the sink node receives 90 packets and decodes the linear network code using the BPA algorithm. In the figure, white squares represent 0 and black squares represent 1. The performance of the LEDEC scheme is shown in Figure 13.Figure 12
An example of the parity check matrix (transposed) in network coding.Figure 13
Performance evaluation of the LEDEC scheme.Remark 6.
When the percentage of the malicious nodes is less than40%, the performance of the LEDEC scheme is slightly better than the EDEC scheme. This is because the sink nodes can successfully correct most of the errors in the corrupted packets and decode the original symbols using error-free packet symbols.Remark 7.
Because the sink nodes can recover extra information from the corrupted packets, when the percentage of malicious nodes is between40% and 60%, the LEDEC scheme outperforms the EDEC and the error-detection based schemes.


## 5.1. LDPC Code

LDPC linear block code was first introduced by Gallager in 1962 [29]. One of the important characteristics of LDPC code is its sparse parity check matrix. By using iterative decoding, LDPC code can achieve error-correction performance close to Shannon bounds [30]. LDPC codes can be categorized as the regular LDPC code, of which the parity check matrix H has a fixed number of 1’s per column and per row, and the irregular LDPC code, of which the parity check matrix may have different numbers of 1’s in each column and each row. In this section, we will formulate the network coding to the irregular LDPC code.


## 5.2. Decoding of LDPC Code

The iterative decoding algorithm, known as belief propagation algorithm (BPA), is generally used to decode the LDPC code. Among all the channel models the BPA algorithm for the binary erasure channel (BEC) is the simplest, where only three numbers need to be considered:0, 1, and x (erasure). The BPA can be described over the Tanner graph [31], which is a bipartite graph. In a Tanner graph, there are two types of nodes: the symbol nodes (corresponding to the received bits) and the check nodes (corresponding to the rows of the parity check matrix). An illustrative example of the parity check matrix and its Tanner graph is shown in Figure 10. In the parity check matrix, every row represents a parity check equation. The symbol nodes, which correspond to the bits equal to 1’s in a row of the parity check matrix, are connected to the check node which corresponds to the same row. These nodes and edges in the Tanner graph express the parity check equation of that row. In Figure 10, node h1 represents the first row of the parity check matrix. The first, second, and third elements of the first row in parity check matrix are 1’s, so symbol nodes d1, d2, and d3 are connected to h1 in the Tanner graph.Figure 10
An illustrative example of parity check matrix and Tanner graph.The decoding algorithm can be described through Algorithm4.Algorithm 4:BPA decoding algorithm for BEC.
(1) while There are check nodes connected to only one unknown symbol node do (2) forEach of these check nodes do (3) The unknown symbol node ← xor (All of the other symbol nodes connected to the check node) (4) end for (5) end while (6) if All the unknown symbol nodes are recovered then (7)  Decode successfully (8) end if


## 5.3. Relationship between Linear Network Code and LDPC Code

In linear network coding, packets are linearly combined at the intermediate nodes. The packets received at the sink nodes satisfy (2). In the network code decoding part of the EDEC algorithm, only independent valid packets are used. However, there is also helpful information in the linearly dependent packets or corrupted packets. If we can exploit and use these packets, the system performance can be further improved. Denote the received encoding vector as βi=(βi,1,…,βi,l), where 1≤i≤m and m is the number of received packets. Then the generation matrix of the block network code GN can be defined as(8)GN=β1T⋯βlT,βl+1T⋯βmTT.As an example, suppose there is only one bit xi in each original packet of the source node for 1≤i≤l. Define x=x1,…,xlT. In this case, each received packet in the sink nodes also contains only one bit yj for 1≤j≤m. Denote all the m received packets as a vector y=y1,…,ymT. We have the following encoding equation:(9)y=GNx.Theorem 4.
The linear network code can be viewed as a rateless LDPC code and can be decoded using the BPA algorithm.Proof (sketch).
Since we can have an uncertain number ofm>l received encoded bits in the encoding equation (9), we can view the network code as a rateless code. The generating matrix GN can be rewritten as(10)GN=P1P2=IlP2P1-1P1,where matrix P1 can be made as an l×l full rank matrix through row exchange after l independent packets are received, P2 is an (m-l)×l matrix, and Il is an l×l identity matrix. The corresponding parity check matrix HN can be written as(11)HN=P2P1-1TIm-l,where Im-l is an (m-l)×(m-l) identity matrix. We can verify the correctness of HN by verifying the follow equation:(12)HNTGN=P2P1-1TIm-lTIlP2P1-1P1=0.After deriving the corresponding parity check matrix HN, we can decode the linear network code using the BPA algorithm. The linear network code can be viewed as a rateless LDPC code and has the property of error-control codes.Although linear network codes can be viewed as rateless LDPC codes, the BPA algorithm cannot be used to decode a network code if the network code is derived after the decoding of a conventional error-control code, because we cannot detect the incorrect decodings which should be viewed as erasures. For the modified error-control codes in the EDEC scheme, we can determine the erroneous decodings and mark the corresponding bits as erasures. Therefore, we can decode the linear network code using the BPA algorithm. Figure11 illustrates this main idea of the LEDEC scheme.Figure 11
Main idea of the LEDEC scheme.


## 5.4. Theoretical Analysis

Through the information in linearly dependent packets, the LEDEC scheme can get additional benefits from BPA decoding of the LDPC code. Consider the case in which the percentage of malicious nodes is high, most of the packets are corrupted by the malicious nodes. The error-detection based schemes cannot work because all of the packets are discarded. The EDEC scheme does not work well either because with high erasure probabilityPe there will not be enough correctable packets to solve the network coding equations (2).For the LEDEC scheme, letλd denote the probability that an edge from a check node is connected to a symbol node of degree d, and ρd denote the probability that an edge from a symbol node is connected to a check node of degree d in the Tanner graph of the corresponding LDPC code. The generating functions for an LDPC code is defined as: λ(x)=∑dλdxd-1, ρ(x)=∑dρdxd-1. According to [32], the maximal fraction of erasures that a random LDPC code with given generating functions can correct is bounded by Pmax=min⁡x/λ(1-ρ(1-x))(0<x<1) with probability at least 1-O(n-3/4), where n is the length of the code. For the throughput of the LEDEC scheme, we have Theorem 5.Theorem 5.
The throughput of the LEDEC scheme is(13)F=∑i=0N·PmaxNiPei1-PeN-i,where Pmax=min⁡x/λ(1-ρ(1-x))(0<x<1), Pe is the erasure probability, N is the number of packets a sink node received, and · is the floor function.Proof.
Suppose a sink node receivesN packets and the erasures in the packets are independent; the distribution of the number of erasures i in N received packet symbols is a binomial distribution with Pr(i)=NiPei1-PeN-i,0≤i≤N as the probability mass function (PMF).
The proposed scheme can combat all erasures up toN·Pmax with probability at least 1-O(N-3/4), which is close to 1. Thus the throughput can be written as F=∑i=0⌊N·Pmax⌋Pr(i).


## 5.5. Performance Analysis and Simulation

In this section, we provide simulation results of the LEDEC scheme on the simulation platform presented in Section4.2. All the settings and parameters are the same as in Section 4.2.


### 5.5.1. Nodes Design

For the LEDEC scheme, the source node, relay nodes, and malicious nodes are the same as those in Section4.2. The decoding process in the sink nodes is different, in which all packets received will be used. The BPA decoding will not start until the sink nodes collect all the l=32 independent packets. After receiving l=32 independent packets, we can use the BPA algorithm to decode whenever a new packet arrives. However, there is a trade-off in determining when to start the BPA algorithm. When the algorithm is performed too frequently, the computational overhead will be high. On the other side, if we do not start the BPA decoding until we have collected a large number of packets, the communication delay will be high. To get a trade-off, the sink nodes will trigger the BPA decoding upon the receiving of every 10 new packets. This process will continue until all the message symbols have been successfully decoded.


### 5.5.2. Simulation Results

Same as in Section4.2.3, the simulations in this section are carried out under different percentage of malicious relay nodes. One example of the parity check matrix (transposed) generated in the linear network coding is shown in Figure 12. In this example, the sink node receives 90 packets and decodes the linear network code using the BPA algorithm. In the figure, white squares represent 0 and black squares represent 1. The performance of the LEDEC scheme is shown in Figure 13.Figure 12
An example of the parity check matrix (transposed) in network coding.Figure 13
Performance evaluation of the LEDEC scheme.Remark 6.
When the percentage of the malicious nodes is less than40%, the performance of the LEDEC scheme is slightly better than the EDEC scheme. This is because the sink nodes can successfully correct most of the errors in the corrupted packets and decode the original symbols using error-free packet symbols.Remark 7.
Because the sink nodes can recover extra information from the corrupted packets, when the percentage of malicious nodes is between40% and 60%, the LEDEC scheme outperforms the EDEC and the error-detection based schemes.


## 5.5.1. Nodes Design

For the LEDEC scheme, the source node, relay nodes, and malicious nodes are the same as those in Section4.2. The decoding process in the sink nodes is different, in which all packets received will be used. The BPA decoding will not start until the sink nodes collect all the l=32 independent packets. After receiving l=32 independent packets, we can use the BPA algorithm to decode whenever a new packet arrives. However, there is a trade-off in determining when to start the BPA algorithm. When the algorithm is performed too frequently, the computational overhead will be high. On the other side, if we do not start the BPA decoding until we have collected a large number of packets, the communication delay will be high. To get a trade-off, the sink nodes will trigger the BPA decoding upon the receiving of every 10 new packets. This process will continue until all the message symbols have been successfully decoded.


## 5.5.2. Simulation Results

Same as in Section4.2.3, the simulations in this section are carried out under different percentage of malicious relay nodes. One example of the parity check matrix (transposed) generated in the linear network coding is shown in Figure 12. In this example, the sink node receives 90 packets and decodes the linear network code using the BPA algorithm. In the figure, white squares represent 0 and black squares represent 1. The performance of the LEDEC scheme is shown in Figure 13.Figure 12
An example of the parity check matrix (transposed) in network coding.Figure 13
Performance evaluation of the LEDEC scheme.Remark 6.
When the percentage of the malicious nodes is less than40%, the performance of the LEDEC scheme is slightly better than the EDEC scheme. This is because the sink nodes can successfully correct most of the errors in the corrupted packets and decode the original symbols using error-free packet symbols.Remark 7.
Because the sink nodes can recover extra information from the corrupted packets, when the percentage of malicious nodes is between40% and 60%, the LEDEC scheme outperforms the EDEC and the error-detection based schemes.


## 6. Conclusion

In the paper, we focus on combating pollution attacks in multihop networks that utilize network coding, which can model most of the newly emerging networks in the 5G network. Our purpose is to maintain the network throughput even when the percentage of malicious nodes is large (≥30%). We first introduce an error-detection and error-correction (EDEC) scheme. By utilizing the information available in the corrupted packets, the network throughput can be increased with only a slight increase of the computational overhead compared to the error-detection based schemes. To further increase the throughput for the network environment with heavy pollution, we introduce LEDEC scheme that enables channel information be exploited and belief propagation algorithm (BPA) be used for the packet symbol recovery. This scheme can guarantee the throughput under the heavy pollution (percentage of malicious nodes is larger than 40%). We formulate the throughput of the LEDEC scheme through theoretical analysis and conduct comprehensive simulations to evaluate the performance. Our extensive simulation results show that the LEDEC scheme achieves better throughput than the EDEC scheme.



---

*Source: 3473910-2018-12-02.xml*