A fast network coding scheme for mobile wireless sensor networks

Abstract

In mobile wireless sensor networks, linear network coding has been shown to improve the performance of network throughput and reduce delay. However, the linear dependence of coded packets caused by linear network coding will result in significant instability of the entire network during data transmission. Moreover, current linear network coding schemes do not distinguish between the real-time requirements of different packets. To solve the above problems, a weighted Vandermonde echelon fast coding scheme is proposed based on an analysis of various coding schemes such as random and linear network coding. Weighted Vandermonde echelon fast coding scheme can reduce the dependence problem of the network coding matrix and distinguish between different packet priorities. The accuracy of the proposed weighted Vandermonde echelon fast coding method is investigated through a theoretical analysis and then its outstanding delivery performance is verified through discrete event simulation experiments.

Introduction

Compared to mature Internet technologies, a mobile wireless sensor network (MWSN) ¹ has numerous inherent uncertainties and problems that must be addressed, especially the problem of unstable network transmission caused by node mobility. Network coding provides an appropriate approach to solve these problems.^2–5

Since Ahlswede and Cai ⁶ first proposed the principle of network coding, many scientific researchers have shown strong interest in this area.^7,8 Because a network coding protocol can utilize network bandwidth more reasonably, it can significantly improve network performance in MWSNs that use multicast. Most of the traditional performance optimization schemes for MWSNs try to use each available communication link in the network to increase system bandwidth.^9–11 In the network coding method, in-network coding can significantly improve performance of the whole network when all the available links are utilized.

The network coding schemes adopted in MWSNs include random network coding, ¹² deterministic network coding,^13,14 and some optimized schemes.^15–17 During the random network coding process, ¹² data are packed with a global coding vector. Intermediate nodes recode these packets with their global encoding vectors when they receive these coded data packets from upstream nodes. This operation does not require knowledge of the topological information of the entire network. After receiving a certain number of coded packets, the destination node can acquire the original data by decoding these packets.

In deterministic network coding, the local coding coefficients of the intermediate nodes are fixed, and each coding vector is transmitted in the network simultaneously with the coding result. The deterministic network coding method was initially proposed by Koetter and Médard ¹³ This study designed a relatively complete linear network coding scheme based on the decomposition model of a global transition matrix. A deterministic network coding scheme presented by Fragouli et al. ¹⁴ applied an upper triangular matrix to perform video coding. The deterministic network coding scheme has the advantage of a stable coding coefficient; therefore, the transmission of the coding coefficient in the network involves only small amounts of information, which reduces network overhead.

The coding strategies of most network coding algorithms are based on random linear network coding. However, the main shortfall of random linear network coding is that it cannot ensure the linear independence of the coding vector. Consequently, the source node must send far more coded packets than the source packets (one original data block can be encoded to one source packet) to ensure that the destination node can decode the source packets successfully. This redundant packet requirement increases the network load significantly causing high energy consumption due to retransmission of useless packets. To achieve encryption, energy control, and linear independence of packets, deterministic network coding adopts a deterministic matrix to encode the packets, solving this problem through proper deterministic coding.

This article consists of the following: first, we study random linear coding and two deterministic network coding schemes (the upper triangular matrix coding and Vandermonde matrix coding). Then, we analyze the dependence between the coding matrix of the above coding strategies and their application scope. Subsequently, we propose a weighted Vandermonde echelon fast coding scheme (WVEFC) that, when applied to MWSNs, can ensure the independence of the coding matrix and distinguish coding in accordance with various real-time requirements of packets. The fast coding scheme significantly reduces the time required for large-scale node operations. Finally, we conduct simulation experiments and analyze the coding strategies of the network model. The results of the experiments show that the proposed coding scheme can ensure node coding efficiency and maintain a high data transmission throughput.

The rest of this article is organized as follows. In section “The linear dependence of network coding methods,” we analyze the linear dependence of the coding matrix in random linear coding and two deterministic network coding strategies (the upper triangular matrix coding and Vandermonde matrix coding). In section “The WVEFC algorithm,” we propose the fast coding algorithm called WVEFC to improve the robustness of MWSNs. Section “Simulation results” presents comparisons between the fast coding algorithm, WVEFC, proposed in this article and other coding algorithms to demonstrate the effectiveness and accuracy of WVEFC.

The linear dependence of network coding methods

Random network coding–based data transmission schemes sometimes fail when coded packets are not correctly received by the destination node. Moreover, coding vectors may have linear dependence. If the source node cannot find the problem in time, the entire scheme will fail. Therefore, redundancy strategies have been adopted in several optimized schemes^3–5 by which in-network nodes generate and transmit additional coded packets. In this way, these schemes ensure that a destination node can supplement the width of the decoding coefficient matrix by substituting these linear dependent vectors. Both network delay and transmission redundancy are important factors when evaluating the efficiency of these optimized network-coding-based schemes. In the following, we analyze the linear dependence problem of several classical schemes.

Dependence of random linear coding

Random linear coding refers to randomly choosing a set of coding coefficients from a specified Galois field. First, we consider selecting an $n\times n$ coding matrix from a Galois field, $\mathrm{GF}(2^M)(n=2)$

$$A_2=\left[\begin{array}{cc}{a}_{11}\hfill & a_{12}\hfill \\ \multicolumn{1}{c}{a_{21}}& a_{22}\hfill \end{array}\right]$$

(1)

If the row vectors of $A_2$ are linearly dependent, the coefficients should satisfy ${\mathrm{a}}_{11}/{\mathrm{a}}_{21}={\mathrm{a}}_{12}/{\mathrm{a}}_{22}$ . Therefore, the probability of linear dependence $P_R$ should satisfy

$$P_R=\frac{N_{R2}}{{(2^M-1)}^{n\times n}}$$

(2)

where $2^M$ refers to the size of the Galois field used in the encoding operation, n is the coding matrix dimension, and $N_{R2}$ refers to the possible number of linearly dependent vectors that occurs when a second-order coding matrix is used to conduct the coding operation. Obviously, $N_{R2}$ is a fixed value related to the order of the coding matrix.

The traditional deterministic network coding method performs well in square matrix coding. However, due to the unreliable data transmission characteristic of MWSNs, redundant coded packets must be encoded and transmitted through several optimized schemes. Therefore, the occurrence of linearly dependent coded packets should be considered when using an expanded coding matrix. Consider randomly obtaining an $n\times 2n$ coding matrix ${\overline{A}}_2$ coding coefficient in $\mathrm{GF}(2^M)(n=2)$

$${\overline{A}}_2=\left[\begin{array}{cccc}{a}_{11}\hfill & a_{12}\hfill & a_{13}\hfill & a_{14}\hfill \\ \multicolumn{1}{c}{a_{21}}& a_{22}\hfill & a_{23}\hfill & a_{24}\hfill \end{array}\right]$$

(3)

If column vectors are used to conduct encoding, because there are only two source packets, the destination node needs to receive only two random linearly independent coded packets to successfully decode the source packets. If the arbitrary two column vectors in ${\overline{A}}_2$ are linearly dependent, $a_{n_1{m}_1}$ , $a_{n_1{m}_2}$ , $a_{n_2{m}_1}$ , and $a_{n_2{m}_2}$ will definitely are guaranteed to satisfy the following

$$\frac{a_{n_1{m}_1}}{a_{n_2{m}_1}}=\frac{a_{n_1{m}_2}}{a_{n_2{m}_2}}$$

(4)

where $n=1,2$ and $m=1,2,3,4$ . Therefore, the linear dependence probability $P{\prime }_R$ satisfies

$$P{\prime }_R=\frac{C_4^2{N}_{R2}}{C_4^2{(2^M-1)}^{n\times n}}=\frac{N_{R2}}{{(2^M-1)}^{n\times n}}=P_R$$

(5)

where n and $N_{R2}$ represent the coding matrix dimension and the number of column-linearly-dependent sets in the expanded matrix, respectively. Formula (5) shows that increasing the columns of the coding matrix alone without adding source packets has almost no influence on the probability of linear dependency during the entire network coding process. Two linearly independent coded packets are sufficient for the destination node to decode all the source data packets successfully. When there are more than two linearly dependent vectors, formula (5) is no longer suitable.

We consider an $n\times n$ coding matrix $(n=3)A_3$ with its value drawn from a Galois field, $\mathrm{GF}(2^M)$

$$A_3=\left[\begin{array}{ccc}{a}_{11}\hfill & a_{12}\hfill & a_{13}\hfill \\ \multicolumn{1}{c}{a_{21}}& a_{22}\hfill & a_{23}\hfill \\ \multicolumn{1}{c}{a_{31}}& a_{32}\hfill & a_{33}\hfill \end{array}\right]=\left[\begin{array}{ccc}{\alpha }_1\hfill & {\alpha }_2\hfill & {\alpha }_3\hfill \end{array}\right]$$

(6)

in which ${\alpha }_1$ , ${\alpha }_2$ , and ${\alpha }_3$ are the three column vectors of $A_3$ . Because there are three source packets, the destination node must receive three linearly independent coded packets to successfully decode the source information. Therefore, we must consider the linear dependence among the three vectors ${\alpha }_1$ , ${\alpha }_2$ , and ${\alpha }_3$ .

Assume ${\alpha }_i\in R^n(i=1,2,\dots ,m)$ , if there is a nonzero number $k_i\in R^n(i=1,2,\dots ,m)$ which satisfies $k_1{\alpha }_1+k_2{\alpha }_2+\cdots +k_m{\alpha }_m=0$ , then we can call ${\alpha }_1,{\alpha }_2,\dots ,{\alpha }_m$ linearly dependent.

In $A_3\in \mathrm{GF}(2^M)$ (which means all the elements in matrix $A_3$ are drawn from a Galois field $\mathrm{GF}(2^M)$ ), if ${\alpha }_1$ , ${\alpha }_2$ , and ${\alpha }_3$ are linearly independent, there must be $R(A_3)=3$ , where $R(A_3)$ represents the rank of $A_3$ . If ${\alpha }_1$ , ${\alpha }_2$ , and ${\alpha }_3$ are linearly dependent, $R(A_3)<n$ is satisfied. Therefore, we can calculate the probability $(P_{R3})$ of ${\alpha }_1$ , ${\alpha }_2$ , and ${\alpha }_3$ being linearly dependent

$$P_{R3}=\frac{N_{R3}}{{(2^M-1)}^{n\times n}}$$

(7)

where $N_{R3}$ refers to the number of linearly dependent coded packets that might possibly occur when a third-order coding matrix is used to conduct the linear coding operation.

Next, we consider an $n\times 2n$ expanding coding matrix $(n=3)$ with its value randomly drawn from a Galois field $\mathrm{GF}(2^M)$

$${\overline{A}}_3=\left[\begin{array}{cccccc}{a}_{11}& a_{12}& a_{13}& a_{14}& a_{15}& a_{16}\\ a_{21}& a_{22}& a_{23}& a_{24}& a_{25}& a_{26}\\ a_{31}& a_{32}& a_{33}& a_{34}& a_{35}& a_{36}\end{array}\right]=\left[\begin{array}{cccccc}{\alpha }_1& {\alpha }_2& {\alpha }_3& {\alpha }_4& {\alpha }_5& {\alpha }_6\end{array}\right]$$

(8)

If we denote $P{\prime }_{R3}$ as the probability of existing linearly dependent coded packets, the following formula is satisfied

$$P{\prime }_{R3}=\frac{C_6^3{N}_{R3}}{C_6^3{(2^M-1)}^{n\times n}}=\frac{N_{R3}}{{(2^M-1)}^{n\times n}}=P_{R3}$$

(9)

where $N_{R3}$ refers to the number of linearly dependent sets $(n=3)$ .

In conclusion, we can obtain $P{\prime }_{R3}=P_{R3}$ . In other words, when we use an $n\times n$ coding matrix with its value extracted from a Galois field $\mathrm{GF}(2^M)(m=4,n=3)$ to conduct a random linear coding operation, the probability of generating linearly dependent coded coefficient vectors is consistent with using an $n\times 2n$ expanded coding matrix (where the elements are drawn from the same Galois field).

In an actual sensor network, the number of packets sent by the source node is not fixed and neither is the number of extra coded packets sent to prevent linear dependence. Therefore, it is necessary to discuss a coding matrix with unknown dimensions. As shown by the proof given above, the probability of the coding vectors being linearly dependent when using an expanding matrix to conduct a random linear coding operation is basically consistent with that of the original matrix. We should take the $n_1\times n_2$ expanding coding matrix into consideration where M, $n_1$ , and $n_2$ are all unknown. The coding matrix $\overline{X}$ is shown below

$$\overline{X}=\left[\begin{array}{cccccc}{a}_{11}\hfill & a_{12}\hfill & \cdots \hfill & a_{1n_1}\hfill & \cdots \hfill & a_{1n_2}\hfill \\ \multicolumn{1}{c}{a_{21}}& a_{22}\hfill & \cdots \hfill & a_{2n_1}\hfill & \cdots \hfill & a_{2n_2}\hfill \\ \multicolumn{1}{c}{⋮}& ⋮\hfill & \ddots \hfill & ⋮\hfill & \hfill & ⋮\hfill \\ \multicolumn{1}{c}{a_{n_{1}1}}& a_{n_{1}1}\hfill & \cdots \hfill & a_{n_1{n}_1}\hfill & \cdots \hfill & a_{n_1{n}_2}\hfill \end{array}\right]$$

(10)

In accordance with the proof above, the probability $P_X$ of linearly dependent coding vectors is

$$P_X=\frac{N_X}{{(2^M-1)}^{n_1\times n_2}}=\frac{N_{R{n}_1}}{{(2^M-1)}^{n_1\times n_1}}$$

(11)

In formula (11), $n_1$ is the number of lines in the coding matrix, which is also the number of source packets that must be encoded; $n_2$ is the number of coded packets that satisfies $n_2=n_1+k$ ; and k refers to the number of extra coded packets sent due to the linear dependence of network coding. $N_X$ refers to the maximum combinations of the $n_1$ linearly dependent packets received and $N_{R{n}_1}$ refers to the maximum combinations of linearly dependent coded packets that could occur when using the n₁-order random square matrix to conduct the coding operation.

The linear dependence of adopting an upper triangular matrix as the coding matrix

When an upper triangular matrix is adopted to conduct the linear coding operation, its coding coefficients are randomly extracted from a Galois field $\mathrm{GF}(2^M)$ (only specified coefficients are set to 0). The format is shown in formula (12)

$$B=\left[\begin{array}{ccccc}{b}_{11}\hfill & b_{12}\hfill & \cdots \hfill & b_{1n-1}\hfill & b_{1n}\hfill \\ \multicolumn{1}{c}{}& b_{22}\hfill & \cdots \hfill & b_{2n-1}\hfill & b_{2n}\hfill \\ \multicolumn{1}{c}{}& \hfill & \ddots \hfill & ⋮\hfill & ⋮\hfill \\ \multicolumn{1}{c}{}& \hfill & \hfill & b_{n-1n-1}\hfill & b_{n-1n}\hfill \\ \multicolumn{1}{c}{}& \hfill & \hfill & \hfill & b_{\mathrm{nn}}\hfill \end{array}\right]$$

(12)

where $b_{n_1{n}_2}$ is randomly generated from $\mathrm{GF}(2^M)$ . If an $n\times n$ upper triangular matrix is adopted for the coding operation, the n coded packets must be linearly independent. Therefore, this study considers using the expanding matrix of the upper triangular matrix to conduct the coding operation

$$\{\begin{array}{c}\overline{B}=\left[\begin{array}{ccccccc}{b}_{11}\hfill & b_{12}\hfill & \cdots \hfill & b_{1n_1-1}\hfill & b_{1n_1}\hfill & \cdots \hfill & b_{1n_2}\hfill \\ \multicolumn{1}{c}{}& b_{22}\hfill & \cdots \hfill & b_{2n_1-1}\hfill & b_{2n_1}\hfill & \cdots \hfill & b_{2n_2}\hfill \\ \multicolumn{1}{c}{}& \hfill & \ddots \hfill & ⋮\hfill & ⋮\hfill & \cdots \hfill & ⋮\hfill \\ \multicolumn{1}{c}{}& 0\hfill & \hfill & b_{n_1-1n_1-1}\hfill & b_{n-1n_1}\hfill & \cdots \hfill & b_{n_1-1n_2}\hfill \\ \multicolumn{1}{c}{}& \hfill & \hfill & 0\hfill & b_{n_1{n}_1}\hfill & \cdots \hfill & b_{n_1{n}_2}\hfill \end{array}\right]\hfill \\ \multicolumn{1}{c}{\overline{B}=\left[\begin{array}{cccc}{\beta }_1\hfill & {\beta }_1\hfill & \cdots \hfill & {\beta }_{n2}\hfill \end{array}\right]}\end{array}$$

(13)

where ${\beta }_i(0<i<n_2)$ is the column vector of matrix $\overline{B}$ . If $\overline{B}$ is used to conduct the coding operation, the probability $P_{\overline{B}}$ of linear dependency satisfies

$$P_{\overline{B}}=\frac{N_{\overline{B}}}{{(2^M-1)}^{n_1\times (n_2-n_1)}+{(2^M-1)}^{\frac{n_1\times (n_1-1)}{2}}}$$

(14)

where $n_1$ refers to the number of source packets that needs to be encoded, which is also the number of lines in the coding matrix; $n_2$ refers to the column number of the coding matrix that must be sent; and $N_{\overline{B}}$ refers to the maximum combinations of linearly dependent coded packets that could occur when using an upper triangular expanding matrix $\overline{B}$ to conduct the linear coding operation. Because the source node needs to send only $n_1$ source packets, it needs to consider at most $n_1$ linearly dependent coded packets that could be generated

$$\begin{array}{c}F1F2\hfill \\ \overline{B}=\left[\begin{array}{cccc}{b}_{11}\hfill & b_{12}\hfill & \cdots \hfill & b_{1n_1-1}\hfill \\ \multicolumn{1}{c}{}& b_{22}\hfill & \cdots \hfill & b_{2n_1-1}\hfill \\ \multicolumn{1}{c}{}& \hfill & \ddots \hfill & ⋮\hfill \\ \multicolumn{1}{c}{}& 0\hfill & \hfill & b_{n_1-1n_1-1}\hfill \\ \multicolumn{1}{c}{}& \hfill & \hfill & 0\hfill \end{array}|\begin{array}{c}{b}_{1n_1}\cdots b_{1n_2}\hfill \\ \multicolumn{1}{c}{b_{2n_1}\cdots b_{2n_2}}\\ \multicolumn{1}{c}{⋮\cdots ⋮}\\ \multicolumn{1}{c}{b_{n-1n_1}\cdots b_{n_1-1n_2}}\\ \multicolumn{1}{c}{b_{n_1{n}_1}\cdots b_{n_1{n}_2}}\end{array}\right]\hfill \end{array}$$

(15)

For convenience, matrix $\overline{B}$ is divided into two sub-matrices in formula (15): $F_1$ , the upper triangular matrix of $n_1\times (n_1-1)$ , and $F_2$ , the random matrix of $n_1\times (n_2-n_1+1)$ . Thus, the $n_1$ coding column vectors will be selected from $F_1$ and $F_2$ . Because $F_2$ is a random matrix, the number of possible linearly dependent coded packets should be determined in accordance with two situations: (1) when the sub-matrix $F_2$ is linearly independent and (2) when it is linearly dependent. We denote the probability of linear dependence when using these two coding matrices by $P_{\overline{B}}^{\mathrm{nc}}$ and $P_{\overline{B}}^c$ , respectively.

• 1. When $F_2$ is linearly independent, the number of linearly dependent coded packets that could occur is denoted by $N_{\overline{B}}^{\mathrm{nc}}$

$$P_{\overline{B}}^{\mathrm{nc}}=\frac{N_{\overline{B}}^{\mathrm{nc}}}{{(2^M-1)}^{n_1\times (n_2-n_1)}+{(2^M-1)}^{\frac{n_1\times (n_1-1)}{2}}}$$

(16)

$$N_{\overline{B}}^{\mathrm{nc}}=N_{F_1}^{\mathrm{nc}}+N_{F_2}^{\mathrm{nc}}+N_{F_1{F}_2}^{\mathrm{nc}}$$

(17)

where $N_{F_1}^{\mathrm{nc}}$ represents the number of linearly dependent coded packets that could possibly occur, while the selected $n_1$ column vectors consist of $(n_1-1)$ column vectors from $F_1$ and 1 column vector from $F_2$ . In accordance with the nature of the upper triangular matrix $\overline{B}$ , it is impossible for the first $(n_1-1)$ columns to be linearly dependent with any other column; thus, $N_{F_1}^{\mathrm{nc}}=0$ .

We denote $N_{F_2}^{\mathrm{nc}}$ as the possible number of linearly dependent coded packets when the selected $n_1$ column vectors are all from $F_2$ . Because the column vectors of $F_2$ are linearly independent, $N_{F_2}^{\mathrm{nc}}=0$ .

We denote $N_{F_1{F}_2}^{\mathrm{nc}}$ as the possible number of linearly dependent coded packets when the selected $n_1$ column vectors consist of some from $F_1$ and some from $F_2$ . Assume that x column vectors are selected from $F_1$ and $(n_1-x)$ column vectors are selected from $F_2$ . Then, ${\overline{B}}_{F_1{F}_2}$ is as follows

$${\overline{B}}_{F_1{F}_2}=\left[\begin{array}{cccccc}{b}_{11}& \cdots & b_{1x}& b_{1x+1}& \cdots & b_{1n_1}\\ b_{1n_1}& \cdots & b_{2x}& b_{2x+1}& \cdots & b_{2n_1}\\ ⋮& & & ⋮& \cdots & ⋮\\ b_{p1}& & b_{ix}& b_{ix+1}& \cdots & b_{i{n}_1}\\ 0& \ddots & ⋮& ⋮& \cdots & ⋮\\ ⋮& & b_{qx}& b_{jx+1}& \cdots & b_{j{n}_1}\\ ⋮& & 0& ⋮& \cdots & ⋮\\ ⋮& & ⋮& ⋮& \cdots & ⋮\\ 0& & 0& b_{n_{1}x+1}& \cdots & b_{n_1{n}_1}\end{array}\right]=\left[\begin{array}{cccccc}{\beta }_1& \cdots & {\beta }_x& {\beta }_{x+1}& \cdots & {\beta }_{n_2}\end{array}\right]$$

(18)

In ${\overline{B}}_{F_1{F}_2}$ , for any column vector ${\beta }_l(0\le l\le x)$ selected from $F_1$ , a new matrix ${\overline{B}}_{F_1{F}_2}^l$ is generated

$${\overline{B}}_{F_1{F}_2}^l=\left[\begin{array}{cccc}{b}_{1l}& b_{1x+1}& \cdots & b_{1n_1}\\ b_{2l}& b_{2x+1}& \cdots & b_{2n_1}\\ ⋮& ⋮& \cdots & ⋮\\ b_{il}& b_{ix+1}& \cdots & b_{i{n}_1}\\ 0& ⋮& \cdots & ⋮\\ ⋮& b_{jx+1}& \cdots & b_{j{n}_1}\\ ⋮& ⋮& \cdots & ⋮\\ ⋮& ⋮& \cdots & ⋮\\ 0& b_{n_{1}x+1}& \cdots & b_{n_1{n}_1}\end{array}\right]=\left[\begin{array}{ccccc}{\beta }_l& \cdots & {\beta }_{x+1}& \cdots & {\beta }_{n_1}\end{array}\right]$$

(19)

In ${\overline{B}}_{F_1{F}_2}^l$ , the column vectors ${\beta }_{x+1},{\beta }_{x+2},\dots ,{\beta }_{n_1}$ are linearly independent, there exists nonzero number $k_l,k_{x+1},k_{x+2},\dots ,k_{n_1}$ which satisfies $k_l{\beta }_l+k_{x+1}{\beta }_{x+1}+k_{x+2}{\beta }_{x+2}+\cdots +k_{n_1}{n}_1=0$ .

On the row $m(m>i)$ , there is $k_{l}0+k_{x+1}{b}_{\mathrm{mx}+1}+k_{x+2}{b}_{\mathrm{mx}+2}+\cdots +k_{n_1}{b}_{m{n}_1}=0$ ; consequently, we have $k_{x+1}{b}_{\mathrm{mx}+1}+k_{x+2}{b}_{\mathrm{mx}+2}+\cdots +k_{n_1}{b}_{m{n}_1}=0$ . Therefore, we can reach the following conclusion: the first i rows of sub-vectors in ${\beta }_l,{\beta }_{x+1},{\beta }_{x+2},\dots ,{\beta }_{n_1}$ are linearly dependent, but the first i rows of sub-vectors in ${\beta }_{x+1},{\beta }_{x+2},\dots ,{\beta }_{n_1}$ are linearly independent. Assume that the number of possible linearly dependent coded packets is $N_{{\overline{B}}_{F_1{F}_2}^{l}i}$ , that the sub-vectors from row i to row $n_1$ are linearly dependent in ${\beta }_{x+1},{\beta }_{x+2},\dots ,{\beta }_{n_1}$ , and that the number of possible linearly dependent coded packets is $N_{{\overline{B}}_{F_1{F}_2}^l(n-i)}$ . Because b is a random number generated from $\mathrm{GF}(2^M)$ , both $N_{{\overline{B}}_{F_1{F}_2}^{l}i}$ and $N_{{\overline{B}}_{F_1{F}_2}^l(n-i)}$ can be obtained through formula (11) in section “Dependence of random linear coding.” Therefore, we have

$$N_{{\overline{B}}_{F_1{F}_2}^l}=N_{{\overline{B}}_{F_1{F}_2}^{l}i}\times N_{{\overline{B}}_{F_1{F}_2}^l(n-i)}=N_{\mathrm{Ri}}\times N_{R(n_1-i)}$$

(20)

where ${\beta }_l$ is any column vector from $F_1$ . Therefore

$$\begin{array}{cc}\multicolumn{1}{c}{N_{\overline{B}}^{\mathrm{nc}}}& =N_{F_1}^{\mathrm{nc}}+N_{F_2}^{\mathrm{nc}}+N_{F_1{F}_2}^{\mathrm{nc}}\hfill \\ \multicolumn{1}{c}{}& =N_{F_1{F}_2}^{\mathrm{nc}}=N_{{\overline{B}}_{F_1{F}_2}}=\sum _{x=1}^{n_1-1}{C}_{n_1-1}^x\left(C_x^1{N}_{{\overline{B}}_{F_1{F}_2}^l}\right)\hfill \\ \multicolumn{1}{c}{}& =\sum _{x=1}^{n_1-1}{\mathrm{xC}}_{n_1-1}^x{N}_{\mathrm{Ri}}\times N_{R(n_1-i)}\hfill \end{array}$$

(21)

• 2. If $F_2$ is linearly dependent, we can calculate the possible number of linearly dependent coded packets $N_{\overline{B}}^c$ as follows

$$P_{\overline{B}}^c=\frac{N_{\overline{B}}^c}{{(2^M-1)}^{n_1\times (n_2-n_1)}+{(2^M-1)}^{\frac{n_1\times (n_1-1)}{2}}}$$

(22)

$$N_{\overline{B}}^c=N_{F_1}^c+N_{F_2}^c+N_{F_1{F}_2}^c$$

(23)

where $N_{F_1}^c$ represents the number of possible linearly dependent coded packets when the selected $n_1$ column vectors of $\overline{B}$ consist of $(n_1-1)$ column vectors from $F_1$ and 1 column vector from $F_2$ . In accordance with the nature of the upper triangular matrix, in $\overline{B}$ , it is impossible for the first $(n_1-1)$ columns to be linearly dependent with any other column; therefore, $N_{F_1}^c=0$ .

We denote $N_{F_2}^c$ as the number of linearly dependent coded packets when the selected $n_1$ column vectors are all from $F_2$ in $\overline{B}$ . Given that the column vectors of $F_2$ are linearly dependent, $N_{F_2}^c=N_{R{n}_1}>0$ .

We denote $N_{F_1{F}_2}^c$ as the possible number of linearly dependent coded packets when the selected $n_1$ column vectors are drawn from $F_1$ and $F_2$ simultaneously. Assume that x column vectors are drawn from $F_1$ ; therefore, the remainder $(n_1-x)$ column vectors are extracted from $F_2$ . This type of coding matrix ${\overline{B}}_{F_1{F}_2}$ has been analyzed above for the linearly independent matrix $F_2$ ; therefore, we will not elaborate further here.

Because the column vectors of sub-matrix $F_2$ are linearly dependent, the linear dependence of the column vectors in ${\overline{B}}_{F_1{F}_2}$ includes two situations: (1) in ${\overline{B}}_{F_1{F}_2}$ , the column vectors from $F_2$ are linearly dependent and (2) in ${\overline{B}}_{F_1{F}_2}$ , the column vectors from $F_2$ are linearly independent. In the first situation, ${\overline{B}}_{F_1{F}_2}$ is complicated and will not be discussed in this article. In the second situation, the number of possible linearly dependent coded packets during operation $N_{F_1{F}_2}^c$ should be equal to $N_{F_1{F}_2}^{\mathrm{nc}}$ . In conclusion, considering the existence of the first situation, we can obtain

$$N_{F_1{F}_2}^c\ge N_{F_1{F}_2}^{\mathrm{nc}}$$

(24)

Therefore, in accordance with formulas (17), (22)–(24), we can obtain

$$N_{\overline{B}}^{\mathrm{nc}}=N_{F_1}^{\mathrm{nc}}+N_{F_2}^{\mathrm{nc}}+N_{F_1{F}_2}^{\mathrm{nc}}\le N_{F_1}^c+N_{F_2}^c+N_{F_1{F}_2}^c=N_{\overline{B}}^c$$

(25)

If an upper triangular expanding matrix $\overline{B}$ is adopted to conduct the linear coding operation, the probability of generating linearly dependent coded packets $P_{\overline{B}}$ satisfies

$$P_{\overline{B}}\ge \frac{N_{\overline{B}}^{nc}}{{\left(2^M-1\right)}^{n_1\times (n_2-n_1)}+{\left(2^M-1\right)}^{\frac{n_1\times \left(n_1-1\right)}{2}}}=\frac{{\displaystyle \sum _{x=1}^{n_1-1}x{C}_{n_1-1}^x{N}_{Ri}\times N_{R\left(n_1-i\right)}}}{{\left(2^M-1\right)}^{n_1\times (n_2-n_1)}+{\left(2^M-1\right)}^{\frac{n_1\times \left(n_1-1\right)}{2}}}$$

(26)

Linear dependence of adopting the Vandermonde matrix as the coding matrix

Given the special characteristics of the Vandermonde matrix, the network coding results are different from those randomly obtained matrices. If the Vandermonde matrix is adopted to conduct the linear coding operation, the nodes need to select only a group of unequal constants to establish a Vandermonde matrix. In accordance with the characteristics of the Vandermonde matrix, any column of this matrix is linearly independent. Therefore, using the Vandermonde matrix to conduct linear coding, the coding operation is guaranteed to generate linearly independent coded packets. The general idea is that a Vandermonde expanding matrix $\overline{F}$ is adopted to conduct linear coding (as shown in formula (27))

$$\overline{F}=\left[\begin{array}{cccccc}{f}_1^0\hfill & f_2^0\hfill & \cdots \hfill & f_{n_1}^0\hfill & \cdots \hfill & f_{n_2}^0\hfill \\ \multicolumn{1}{c}{f_1^1}& f_2^1\hfill & \cdots \hfill & f_{n_1}^1\hfill & \cdots \hfill & f_{n_2}^1\hfill \\ \multicolumn{1}{c}{⋮}& ⋮\hfill & \ddots \hfill & \cdots \hfill & \cdots \hfill & ⋮\hfill \\ \multicolumn{1}{c}{f_1^{n_1-1}}& f_2^{n_1-1}\hfill & \cdots \hfill & f_{n_1}^{n_1-1}\hfill & \cdots \hfill & f_{n_2}^{n_1-1}\hfill \end{array}\right]$$

(27)

in which $f_1$ , $f_2$ , …, $f_{n_2}$ are $n_2$ unequal integers that are nonzero elements. Because there are only $n_1$ source packets in this transmission task, the destination node needs to receive only $n_1$ linearly independent coded packets to decode all the source information. For the Vandermonde expanding matrix $\overline{F}$ , any of its n₁-order sub-matrices is a new Vandermonde matrix $F\prime$ . The coded packet obtained through the linear coding of the column vector set of $F\prime$ is guaranteed to be linearly independent. Therefore, using a Vandermonde expanding matrix to conduct linear coding, we can ensure the linear independence of coded data packets. However, using a Vandermonde expanding matrix to conduct the linear coding operation has two shortcomings: first, the calculation is complicated and requires large amounts of computation to obtain the coding matrix; second, due to the high linear independence of a Vandermonde matrix, the original data can be decoded only after the destination node has received all the coded packets, which does not benefit the transmission of priority control commands in the network application.

The WVEFC algorithm

In MWSNs, transmitted information can be classified into two categories. The first is data, which are generally sent from the sensor node to the sink node and may require encryption, in which case eavesdropping nodes cannot decode any information from the source packets even if they obtain some coded packets. The second is control information, which is generally sent from the sink node to the sensor nodes. Control information is used to make timely adjustments to the overall network deployment when the network environment changes, to better adapt data transmission to the environment. Control information consists of only simple control commands that do not require encryption.

If the traditional full-rank matrix network coding method is adopted, taking the Vandermonde expanding matrix as an example, the control commands can be decoded only after the destination node has received all the packets. However, these control commands often need to be identified by the node quickly, so that the control changes can be made. Some data also contain time-sensitive information that the destination node should receive as soon as possible. The above problems cannot be solved by adopting the traditional network coding scheme. However, the WVEFC can be used to solve them.

The basic idea of WVEFC is that the source node divides data information into different groups when it assigns a transmission task. The basis of grouping is the priority-secret (P-S) weight of data. The P-S weight reflects the importance and timeliness of this packet, for example, the information contained in the packet should not be wiretapped, or a huge loss could occur if a packet becomes invalid or fails to reach the destination node in time. The coding matrix ${\overline{F}}_{\mathrm{PC}}$ is as follows

$${\overline{F}}_{PC}=\left[\begin{array}{ccccccccc}{b}_{11}& b_{12}& b_{13}& \cdots & f_{n_1-1}^0& f_{n_1}^0& f_{n_1+1}^0& \cdots & f_{n_2}^0\\ & b_{22}& b_{23}& \cdots & f_{n_1-1}^1& f_{n_1}^1& f_{n_1+1}^1& \cdots & f_{n_2}^1\\ & & b_{33}& \cdots & f_{n_1-1}^2& f_{n_1}^2& f_{n_1+1}^2& \cdots & f_{n_2}^2\\ & 0& & & \cdots & \cdots & \cdots & \cdots & \cdots \\ & & & & f_{n_1-1}^{n_1-1}& f_{n_1}^{n_1-1}& f_{n_1+1}^{n_1-1}& \cdots & f_{n_2}^{n_1-1}\end{array}\right]$$

(28)

${\overline{F}}_{\mathrm{PC}}$ is an $n_1\times n_2$ –order matrix $(n_2>n_1)$ . In which, the sub-matrix, which consists of the first $n_1$ column vectors, is an upper triangular matrix, while the rest of the sub-matrix (including column $n_1$ ) is a Vandermonde expanding matrix. If ${\overline{F}}_{\mathrm{PC}}$ is adopted to conduct the coding operation, $n_2$ coded packets will be generated. Regardless of how large the value of $n_2$ , any $n_1$ packets selected from these $n_2$ coded packets will be linearly independent. Because of the nature of the coding matrix discussed above, the destination node needs to receive only $n_1$ coded packets to successfully decode the source packets.

In the WVEFC coding scheme, different column vectors in ${\overline{F}}_{\mathrm{PC}}$ are adopted for different coding requirements. For the priority control command which does not require encryption, the first column can be used for coding. After receiving this packet, any node can immediately adopt a scheme in accordance with the command. The basic principle of WVEFC is that priority packets and unimportant packets should be coded by the column vectors with smaller indices, while the secret and non-priority packets should be coded by those with larger indices.

In this article, the packets transmitted over the network are divided into data information packets and control information packets. Both types of packets are classified into five levels, from one to five, denoted as $P_{\mathrm{level}}$ and $S_{\mathrm{level}}$ . The smaller the number, the higher the level

$$P_{\mathrm{level}}=1,2,\dots ,5$$

$$S_{\mathrm{level}}=1,2,\dots ,5$$

The coding matrix ${\overline{F}}_{\mathrm{PC}}$ is an $n_1\times n_2(n_2>n_1)$ -order matrix, where $n_2=n_1+k$ , and the value of k refers to the number of packets that requires redundant coding to improve the delivery rate of packets; therefore, the value of k is related to network conditions. In this article, the only network conditions considered are the packet loss probability and the transmission radius of a node. Assume that the packet loss probability of nodes in the network is L, and the average transmission radius of the network nodes is R (in m). Then

$$k=\mathrm{aL}+\frac{b}{R}$$

in which a and b are adjustable parameters that are generally set to 50 and 400, respectively. Unless stated otherwise, the values of these two parameters are constant in the remainder of this article.

Before each coding operation, in addition to specifying the row and column numbers of the generated coding matrix, we also need to specify the sequence in which packets need to be coded. This sequence should be determined by the priority and secrecy levels of a packet. In the matrix to be encoded, assume that the column index of each packet to be coded is $P_{\mathrm{Index}}$ . Then, we have

$$\begin{array}{l}{P}_{Index}=\left(0.5\times Type+a\frac{\left(P_{level}-1\right)}{5}+b\frac{\left(5-S_{level}\right)}{5}\right)\\ \times C_{num},a+b=\frac{1}{2}\end{array}$$

where a and b are adjustable parameters that represent different degrees of importance for the coding node; these two parameters are generally regarded as equally important, that is, $a=1/4$ and $b=1/4$ . Type refers to category of packet, it is set to 1 if the packet is data, while 0 if the packet is control information. If there is a conflict in the value of $P_{\mathrm{Index}}$ , the number closest to the current $P_{\mathrm{Index}}$ should be found in accordance with the hash algorithm of linear probing, that is, successively look for a usable index (e.g. $P_{\mathrm{Index}}+1$ , $P_{\mathrm{Index}}+2$ ) until a usable column number is found.

In conclusion, the procedure to encode $n_1$ packets with the coding scheme proposed in this section is summarized in the following steps:

• Step 1: Calculate the number of packets that requires redundant coding $k=\mathrm{aL}+(b/R)$ . Then, the column number of the coding matrix can be determined by $n_2=n_1+k$ ;

• Step 2: Generate the $n_1\times n_2$ fast coding matrix ${\overline{F}}_{\mathrm{PC}}$ ;

• Step 3: Determine the position of $n_1$ column vectors packets in D, where D represents the matrix to be coded

  $$P_{\mathrm{Index}}=(0.5\times \mathrm{Type}+a\frac{(P_{\mathrm{level}}-1)}{5}+b\frac{(5-S_{\mathrm{level}})}{5})\times C_{\mathrm{num}}$$

• Step 4: Obtain the final coded matrix through the coding matrix obtained in Step 2

$$D\prime ={\overline{F}}_{\mathrm{PC}}\times D$$

During each coding operation, in accordance with the requirement of the actual situation, the first $n_1$ column vectors of ${\overline{F}}_{\mathrm{PC}}$ can be expanded from a triangular matrix to an echelon matrix $\overline{F}{\prime }_{\mathrm{PC}}$

$$\begin{array}{c}F1F2\hfill \\ {\overline{F}}_{\mathrm{PC}}=\left[\begin{array}{ccccccccc}{b}_{11}\hfill & b_{12}\hfill & b_{13}\hfill & \cdots \hfill & f_{n_1-1}^0\hfill & f_{n_1}^0\hfill & f_{n_1+1}^0\hfill & \cdots \hfill & f_{n_2}^0\hfill \\ \multicolumn{1}{c}{}& b_{22}\hfill & b_{23}\hfill & \cdots \hfill & f_{n_1-1}^1\hfill & f_{n_1}^1\hfill & f_{n_1+1}^1\hfill & \cdots \hfill & f_{n_2}^1\hfill \\ \multicolumn{1}{c}{}& b_{23}\hfill & b_{33}\hfill & \cdots \hfill & f_{n_1-1}^2\hfill & f_{n_1}^2\hfill & f_{n_1+1}^2\hfill & \cdots \hfill & f_{n_2}^2\hfill \\ \multicolumn{1}{c}{}& 0\hfill & \hfill & \ddots \hfill & \cdots \hfill & \cdots \hfill & \cdots \hfill & \cdots \hfill & \cdots \hfill \\ \multicolumn{1}{c}{}& \hfill & \hfill & \hfill & f_{n_1-1}^{n_1-1}\hfill & f_{n_1}^{n_1-1}\hfill & f_{n_1+1}^{n_1-1}\hfill & \cdots \hfill & f_{n_2}^{n_1-1}\hfill \end{array}\right]\hfill \\ F3F4\hfill \end{array}$$

(29)

in which $\overline{F}{\prime }_{\mathrm{PC}}$ is only a type of representative change. The P-S weight of a packet should be set in accordance with the requirements, and the packets that have close weights or internal connections should be coded with a column vector set that has the same number of nonzero elements, so that the node can decode these packets first. In accordance with the nature of ${\overline{F}}_{\mathrm{PC}}$ proved as shown in the proof above, any $n_1$ coded packets are linearly independent when $F1$ and $F3$ in $\overline{F}{\prime }_{\mathrm{PC}}$ are adopted to conduct the linear coding operation. For the same reason, any $n_1$ coded packets are linearly independent when $F3$ and $F4$ are adopted to conduct a linear coding operation. The destination node only needs to receive more than $n_1$ coded packets to decode all the source packets.

However, it is possible to find linear dependence of any $n_1$ coded packets when we use certain column vectors from $F_1$ to $F_3$ and column vectors from $F_2$ to $F_4$ to conduct the coding operation simultaneously. The reason for this kind of linear dependence is that we cannot ensure the linear dependence of column vectors because of the zero elements in $F_3$ . In this situation, the coding matrix degenerates into an upper triangular matrix, as discussed in section “The linear dependence of adopting an upper triangular matrix as the coding matrix.” Due to the nature of the Vandermonde matrix in $F_2$ and $F_4$ , refer to formula (23) in section “The linear dependence of network coding methods,” its linear dependence $P_{\mathrm{WVEFC}}$ satisfies

$$P_{\mathrm{WVEFC}}<P{\prime }_{\mathrm{WVEFC}}\le P_{\overline{B}}$$

(30)

where $P{\prime }_{\mathrm{WVEFC}}$ refers to the probability of existing linearly dependent coded packets when using a random number as an element in the upper triangular matrix and the expanding part of the Vandermonde matrix, while $P_{\overline{B}}$ refers to the probability of existing linearly dependent coded packets when using the upper triangular matrix constructed in section “The linear dependence of adopting an upper triangular matrix as the coding matrix” to conduct linear coding.

The WVEFC coding scheme has four advantages: first, the WVEFC is energy efficient. When too many packets do not require encoding, the coefficients in columns satisfying $n<n_1$ are preferred to conduct the coding operation, which can reduce the calculation time. In MWSNs, it is essential for nodes to save energy because their reserves are generally limited. Second, the WVEFC is computationally efficient. In accordance with the previous proof, $n_1$ packets randomly selected from the packets obtained through the WVEFC coding scheme could cause a certain degree of linear independence, but the WVEFC generally performs better than the common linear coding method. Third, the WVEFC is safe. To ensure that packets requiring fast responses can be decoded as soon as possible, different coding methods should be adopted for packets with different P-S weights, so that the destination node does not need to conduct decoding operations until it has obtained more than $n_1$ packets. The encryption applied to packets means that it is impossible for intercepting nodes to decode any packet if they obtain only a small number of packets. Fourth, the WVEFC is simple to use. In the WVEFC coding scheme, generating the coding matrix is simple. The WVEFC coding matrix consists of an upper triangular matrix and a Vandermonde expanding matrix, where the upper triangular matrix is randomly generated and the expanding matrix requires only a small amount of power operations. Compared with the Vandermonde coding matrix alone, due to the addition of the random upper triangular matrix, the WVEFC coding matrix requires significantly less computational overhead and reduces the probability of linear dependence.

Simulation results

In this section, we provide results of a simulation to demonstrate the efficiency of the WVEFC fast coding algorithm proposed in this article. The experiment was coded using VC++ 6.0 and MATLAB 7.0. Table 1 shows the parameters used in the experiment.

Table 1.

Simulation parameters.

Parameter	Value
Network	$3000\times 3000({\mathrm{m}}^2)$
Node speed	Random
Node pause time	Random
Packet type	CBR
Packet size	512 byte

CBR: constant bit rate.

The epidemic routing model used in this experiment is typical for a restricted network. Because packet transmission can be achieved through broadcast, this model is suitable for the tested network coding schemes.

The delivery time of network data is related to the size of the data flow in the network. Here, 50 nodes are randomly deployed in the network, the node radius is 600 m, the deployment area is a $3000\times 3000({\mathrm{m}}^2)$ rectangle, the node speed varies between −50 and $50\mathrm{m}/\mathrm{s}$ , and the element in the random coding matrices is generated from a $\mathrm{GF}(2^8)$ .

Figure 1 depicts the relation between delivery time and data stream. It shows that the upper triangular expanding matrix coding method has no obvious correlation with the order of the coding matrix. Due to linear independence, the WVEFC coding scheme also has no obvious correlation with the order of the coding matrix. However, random linear coding is significantly related to the delivery time of random linear expanding coding and the order of the coding matrix. In the high-order coding matrix, the delivery time of random linear coding and random linear expanding coding is close to both the WVEFC and the Vandermonde expanding schemes.

Figure 1.

The relation between delivery time and data stream.

In the random epidemic routing network, the communication radius of a node is still an important factor that might affect the efficiency of the whole network. For different node radii, adopting different strategies leads to significantly different network performances. In a real wireless network, different nodes generally have different communication radii. In the following, we will analyze the impact of radius change on different network protocols.

In the simulation network, 50 nodes are randomly deployed; the node movement area is a $3000\times 3000({\mathrm{m}}^2)$ rectangle, the node speed varies between −50 and $50\mathrm{m}/\mathrm{s}$ , the random numbers are selected from $\mathrm{GF}(2^2)$ , $\mathrm{GF}(2^4)$ , $\mathrm{GF}(2^6)$ , and $\mathrm{GF}(2^8)$ , respectively, and two packets need to be sent from the source node.

Figure 2 depicts the influence of increasing node transmission radius with a different coding field on transmission delay. We find that by increasing the size of coding field, the possibility of linearly dependent packets appearing will gradually decline in the following schemes: random linear coding, random linear expanding, and upper triangular expanding matrix coding. With an increase in the power exponent in the Galois field, the performances of several coding methods converge. When the Galois field $\mathrm{GF}(2^8)$ is adopted, the transmission delays of the network are consistent across different network coding methods. In the following, we will simulate sending three packets.

Figure 2.

Transmission delay for sending two packets in a 50-node network.

Similar to the above environment, 50 nodes are randomly deployed in the simulation network, the node movement area is a $3000\times 3000({\mathrm{m}}^2)$ rectangle, the node speed varies between −50 and $50\mathrm{m}/\mathrm{s}$ , and random numbers are selected from $\mathrm{GF}(2^2)$ , $\mathrm{GF}(2^4)$ , $\mathrm{GF}(2^6)$ , and $\mathrm{GF}(2^8)$ , respectively.

Figure 3 depicts the change in transmission delay as the node radius gradually increases when the source node needs to send three packets. As the random number field range increases, in the networks that use random linear coding, random linear expanding coding, or upper triangular expanding matrix coding, the possibility of linearly dependent packets occurring gradually declines. As the power exponent in the Galois field increases, the performances of several coding methods converge. Through a comparison with Figure 2, we find that as the Galois field changes, the transmission delays converge faster.

Figure 3.

Transmission delay of sending three packets in a 50-node network.

When a source node needs to send four source packets, the coding methods require using a fourth-order coding matrix; the linear dependence of coded packets will have change further as shown in Figure 4.

Figure 4.

Transmission delay from sending four packets in a 50-node network.

Figure 4 depicts the change in network transmission delay as the node radius gradually increases in the following environment: 50 nodes are randomly deployed, node movement occured within a rectangle area of $3000\times 3000({\mathrm{m}}^2)$ , node speed varies between −50 and $50\mathrm{m}/\mathrm{s}$ , and random numbers are selected from $\mathrm{GF}(2^2)$ , $\mathrm{GF}(2^4)$ , $\mathrm{GF}(2^6)$ and $\mathrm{GF}(2^8)$ , respectively. As the random number field range increases, in the networks that use random linear coding, random linear expanding coding, or upper triangular expanding matrix coding, the possibility of linearly dependent packets occurring gradually declines. Through comparisons with Figures 2 and 3, we find that as the Galois field increases, the possibility of linear dependence of coded packets declines.

In the following, based on the previous experimental data and conclusions, we investigate the probability of generating linearly dependent packets in different conditions involving different network coding methods, sending different numbers of packets from the source node, and adopting different Galois fields. The results are shown in Figures 5–7.

Figure 5.

The relation between the probability of linear dependence in two-order matrices and the size of the Galois fields.

Figure 6.

The relation between the probability of linear dependence in a three-order matrix and the size of the Galois fields.

Figure 7.

The relation between the probability of linear dependence in a four-order matrix and the size of the Galois fields.

Figure 5 depicts the probability of linearly dependent packets appearing when delivering two packets under different coding fields. The coding operation requires using a second-order coding matrix or a second-order expanding coding matrix. We find that the probabilities of both the WVEFC coding scheme and the Vandermonde expanding matrix coding scheme are 0; therefore, in these two types of networks, the curve overlaps with the horizontal axis. The network that uses the upper triangular expanding matrix coding method has the highest probability of linearly dependent packets occurring. In accordance with the relation between linear dependence and the number of known zeros, we can conclude that the method adopting upper triangular expanding matrix has the highest probability of linearly dependent packets appearing because the upper triangular expanding matrix has the highest number of known zeros. The probabilities of random linear coding and random linear expanding coding are basically the same, which also testifies the validity of formula (11). In the following, we analyze sending three packets from the source node, as shown in Figure 6.

Figure 6 depicts the probability of linearly dependent packets appearing when delivering three packets under different coding fields. The probabilities of both the WVEFC and Vandermonde expanding matrix coding scheme are 0. The probabilities of random linear coding and random linear expanding coding are basically the same. Among these schemes, the upper triangular expanding matrix coding scheme has the highest probability of linearly dependent packets appearing in the network, but it is only a slight increase. The probabilities of linearly dependent packets appearing in the networks that use random linear coding and random linear expanding coding both decline.

Figure 7 depicts the probability of linearly dependent packets appearing when delivering four packets under different coding fields. The probabilities of both the WVEFC and Vandermonde expanding matrix coding scheme remain at 0. The probability of linearly dependent packets appearing with the upper triangular expanding matrix coding method is the highest, while the probabilities of random linear coding and random linear expanding coding are basically identical. To conclude, Figures 5–7 show that in networks that use network coding, the probability of linearly dependent packets satisfies two rules:

1. The probability of linearly dependent packets appearing declines as $\mathrm{GF}(2^M)$ increases.

2. In the network that uses the upper triangular expanding matrix coding scheme, the probability of linearly dependent packets appearing is not dependent on the order of the coding matrix, while in the networks that use random linear coding and random linear expanding coding, the probabilities of linearly dependent packets appearing decline as the order of the coding matrix increases.

During the experiments, when using the WVEFC algorithm and Vandermonde expanding matrix coding, the number of linearly dependent packets is 0. In all 10,000 experiments, in the networks that used WVEFC for coding, the number of linearly dependent packets has been 0. The experiments also showed that WVEFC has the same efficiency as the Vandermonde expanding matrix coding method but is more flexible. Moreover, the WVEFC can provide different coding strategies for source packets with different weights, so it can adjust transmission efficiency and coding as needed. It can also significantly reduce time that nodes have to operate in the network, which saves node energy. These qualities are particularly important in MWSNs, which have poor computation ability and limited energy reserves.

When using the WVEFC algorithm, the fast delivery capability is shown in Figures 8 and 9. In both experiments, 50 nodes were randomly deployed in the network, node movement occurred within a rectangular area of $3000\times 3000({\mathrm{m}}^2)$ , node speed varies between −50 and $50\mathrm{m}/\mathrm{s}$ , the communication radius was 400 m, and the random number was drawn from the Galois field $\mathrm{GF}(2^8)$ .

Figure 8.

The relation between the percentage of control information packets and average delivery time.

Figure 9.

The relation between number of packets and average delivery time.

In Figure 8, 50 packets were sent in total, which involved control information packets (priority level 1 and secrecy level 5) and data information (priority level 5 and secrecy level 1). In Figure 8, the curve shows the change in the average delivery time of messages as the ratio of control messages to total messages increased. Generally speaking, in all coding methods, the delivery time changes very little as the ratio of control messages changes. The WVEFC coding method and the upper triangular expanding matrix coding method provide faster network delivery because both these two coding matrixes involve a triangular matrix; consequently, a large proportion of the control messages can be decoded quickly, while other coding methods need to decode all the messages at one time. Comparing these two methods, the delivery time of the network that uses WVEFC coding is shorter than that of the upper triangular expanding matrix. This probably occurs because the probability of linearly dependent columns appearing in the WVEFC coding matrix is lower; therefore, it requires fewer packets for decoding.

Figure 9 depicts experiments in which several packets need to be sent; the control information packets (priority level 1 and secrecy level 5) account for 20% of the packets. The data information packets (priority level 5 and secrecy level 1) account for the other 80%. The curve shows the change in the average packet delivery time as the number of packets increases. We can see that in all coding methods, as the number of packets increases, the delivery time also increases. The WVEFC coding method, upper triangular expanding matrix coding method, and Vandermonde expanding matrix coding method all provide rapid network delivery. The first two methods involve a triangular matrix; consequently, a large proportion of the control messages can be decoded quickly. However, because of high linear dependence, the delivery time of the upper triangular expanding matrix is longer than that of the WVEFC coding method. As for the Vandermonde expanding matrix coding method, because the linear dependence of its coding matrix is 0, nodes can decode all messages after receiving a very small number of packets. However, because of its more complicated computation, its delivery is slower than that of the WVEFC coding method.

Conclusion and future work

This article studied the network instability caused by the linear dependence of a coding matrix during network coding in MWSN environments; several coding methods were selected for comparison. We proposed a new fast coding algorithm, called WVEFC, and verify the advantages of this algorithm through simulation experiments. Without considering the delay caused by the computation required for the network coding itself, our proposed algorithm is as efficient as the Vandermonde expanding matrix coding method. Considering that the Vandermonde expanding matrix wastes a large amount of node computation resources and takes longer, our WVEFC algorithm achieves better overall system performance. In the fast delivery experiment shown in Figure 8, the WVEFC algorithm exhibits better performance than other coding algorithms.

In this article, the specific number of columns in WVEFC or how various nodes negotiate the number of columns is not regulated. In MWSN environments, node energy is limited; therefore, during the node coding process, node energy consumption should also be considered when selecting a coding scheme. Therefore, in future work, we plan to investigate the balance point between the number of columns in WVEFC coding and network environment conditions to further strengthen the practicality of the WVEFC method in a real-world environment with limited energy.