A Multicast Algorithm for Wireless Sensor Networks Based on Network Coding

Abstract

We propose a set of distributed algorithms for improving the multicast throughput in wireless sensor networks. To this end, network coding is applied when exploiting path diversity with two disjoint paths to each multicast group receiver. We depart from the traditional wisdom that the multicast topology from source to receivers needs to be a tree and propose a novel and distributed algorithm to construct a 2-redundant multicast graph (a directed acyclic graph) as the multicast topology, on which network coding is applied. We conduct both analytical and simulation-based studies to evaluate the effectiveness and performance of our algorithm.

1. Introduction

Multicast mechanism is mainly used in sink nodes to send control messages to the sensor nodes in wireless sensor networks (WSNs), or in a sensor node to send data to multiple sink nodes. Multicast routing algorithm plays a vital role in WSN regarding the survival time and transmission efficiency of the WSNs.

Ahlswede et al. proposed network coding [1–3] in 2000. This method is useful for greatly improving the network throughput and reliability. Literatures [4, 5] have proved that in each multicast diagram, corresponding linear coding can be found to achieve minimum cut-maximum flow. Zhu et al. [6] found that the network coding has good performance and advantage in multicast network, but the network topology has different effect on the throughput and bandwidth of multicast; redundant multicast figure presented better efficiency and performance than the traditional multicast tree.

Jiang et al. [7] proposed a multicast tree algorithm through network coding, determined the relationship between cluster heads, and analyzed the algorithm performance using network calculus. Yuan et al. [8] analyzed the performance of network coding by the stochastic process. Li et al. [9] analyzed the end-to-end route delay performance based on the network coding using network calculus.

According to the WSN characteristic, considering the geographic and energy-aware routing (GEAR) [10], we constructed k-redundant multicast graph in the form of overlay network in this paper using the multicast algorithm based on network coding (MABNC). We improved the multicast performance by reducing the energy consumption.

2. Algorithm Description

The proposed algorithm is for sensor networks. Based on the geographic routing algorithms, k-redundant multicast graph was constructed. The network throughput and bandwidth utilization were improved, the effect of minimum cut to maximum flow was determined, and the network multicast routing performance was enhanced by utilizing the network coding mechanism.

Definition 1.

Redundancy multicast figure: redundancy multicast figure is a directed acyclic graph with a single multicast source node and has the following two properties.

$(1)$ All nodes belong to A, including the source node s, the relay node $A_1$ , and the receiving node $A_t$ . s is expressed as $\text{indegree}(s)=0$ and $\text{outdegree}(s)>0$ ; the forward nodes are $u\in A_I,\hspace{0.17em}\hspace{0.17em}\text{indegree}(u)\le k$ , and $\text{outdegree}(u)>0$ ; the receiving node is expressed as $T_i\in A_T,\hspace{0.17em}1\le i\le T,\hspace{0.17em}\hspace{0.17em}\text{indegree}(T_i)=k$ , and $\text{outdegree}(T_i)\ge 0$ .

$(2)$ Each side has a unit $\text{Bandwidth}$ ; k in-degree for the receiving node $T_i$ , whose independently maximum flow is k. The independent maximum flow refers to the maximum flow through the source node s to the receiving node $T_i$ .

Figure 1 shows that among the WSN nodes, the gathering and sensor nodes formed wireless sensor multiple hops self-organizing network through hierarchical forwarding and were connected; the first layer comprises the gathering node, the second layer comprises the cluster head node, and the third and fourth layers comprise the common sensor nodes. Figure 1 can be further decomposed into k-redundant multicast figure. Figure 2 shows that the gathering node can be the multicast source node s, the second and third layer nodes can be the multicast transit nodes, and the ordinary sensor nodes can be the receiving nodes. In this paper, $k=2$ . For the 2-redundant multicast figure, the key is how to build k-redundant multicast figure and how network coding can be reasonable.

Figure 1

WSN topology.

Figure 2

2-redundant network diagram.

2.1. Building and Maintaining k-Redundant Multicast Figure

Building k-redundant multicast figure needs to satisfy the following conditions to ensure the performance of multicast routing:

• (1)

  ensure minimum energy consumption;

• (2)

  build k-redundant multicast path from the source node s to the receiving node t;

• (3)

  guarantee the minimum amount of transit nodes built from the source node to all of the receiving nodes;

• (4)

  maintain the least link load stressed to ensure the minimum times being forwarded on the same physical link of the same packet.

The whole process can be divided into three steps as follows: $(1)$ build a preliminary figure that can contain all nodes; $(2)$ simplify the preliminary figure to k-redundant multicast figure; $(3)$ combine the receiving node t.

2.1.1. Building Preliminary Figure

In building a preliminary figure, when a new node joins a preliminary diagram, GEAR mechanism is used. The nearest preliminary node will be chosen to lead the joining of preliminary to be transshipment node and form the preliminary figure of each node, as shown in Figure 3(a).

Figure 3

Conversion of the origin figure to 2-redundant multicast figure.

2.1.2. Building k-Redundant Multicast Figure

Figure 3 shows that for each receiving node, two unmutual crossed best route paths need to be established from the source node in a preliminary figure. The pros and cons of a path are mainly evaluated through a tree tuple.

Definition 2.

Path evaluation: the quality of the link from the source node s to the receiving node t must be evaluated. If the link quality is a triple, the edge of the preliminary figure (or the link between two nodes i, j) is set to e; that is, ${\text{path}}_{s\to t}$ goes through m transshipment nodes. The quality evaluation function of side $e_{ij}$ is

$$\begin{array}{l}w\left(e_{ij}\right)=\alpha \times D_{ij}+\beta \times \text{Bandwidth}\left(e_{ij}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}+\lambda \times \text{Latency}\left(e_{ij}\right),\end{array}$$

(1)

where α, β,  and  λ are the normalized parameters, $D_{ij}$ is the distance between two nodes, $\text{Bandwidth}$ is the direct $\text{bandwidth}$ of the two nodes, and $\text{Latency}$ refers to the time delay between the two nodes. The quality assessment of the entire link is

$$\begin{array}{l}w\left({\text{path}}_{s\to t}\right)=(D,\text{Bandwidth}\left({\text{path}}_{s\to t}\right),\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.5em}\text{Latency}\left({\text{path}}_{s\to t}\right))\\ \hspace{1em}\hspace{1em}D=D_{t1}+D_{12}+\cdots +D_{ms}\\ \text{Bandwidth}\left({\text{path}}_{s\to t}\right)\\ \hspace{1em}=\min (\phantom{\text{Bandwidth}\left({\text{e}}_m\right)}\text{Bandwidth}\left(e_1\right),\text{Bandwidth}\left(e_2\right),\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.5em}\hspace{1em}\dots ,\text{Bandwidth}\left({\text{e}}_m\right))\\ \hspace{1em}\text{Latency}\left({\text{path}}_{s\to t}\right)=\sum _{i=1}^m\text{Latency}\left(e_i\right).\end{array}$$

(2)

In Formula (2), the minimum $\text{Bandwidth}$ side should be the evaluation value when evaluating the path $\text{Bandwidth}$ because in the path, only the flow of the minimum $\text{Bandwidth}$ edge can be the maximum flow of the entire path.

In WSNs, as the sensor nodes join or quit dynamically, the network topology changes. The preliminary figure also changes. The path quality evaluation and calibration can be performed periodically. When a better path occurs, the existing path must be replaced with the better path to guarantee at least two or more unmutual crossed best route paths from the receiving node t to the source node s.

To transform the distributed graph into 2-redundant multicast figure, according to the definition requirements of 2-redundant multicast figure, the following requirements must be satisfied.

• (1)

  In multicast figure, the degrees (i.e., the sum of indegree and outdegree) of all nodes, including the source node s, the transmitted node u, and the receiving node t, should not be greater than $\mathrm{\Delta }$ , where $\mathrm{\Delta }$ is the number of the multicast figure layer and is the height of the tree. As shown in Figure 3(b), the highest layer is 4.

• (2)

  The source node s should has k child node, and $2\le k\le \mathrm{\Delta }-\mathrm{1}$ .

• (3)

  $\text{degree}(u)\le \mathrm{\Delta }$ , and $1\le \text{indegree}(u)\le k$ .

• (4)

  If the child node of the transfer u is the receiving node t, then the transfer u child node's number is not greater than $\mathrm{\Delta }-1-\text{indegree}(u)$ .

The fourth rule is used to ensure that at least one outdegree's value of the transit nodes is vacant for adding new transit nodes and for realizing the extensibility and scalability of the multicast figure. When adding a new receiving node to the multicast figure, we can determine the new transit node rapidly to receive the join requests and improve the search speed of convergence.

2.1.3. Receiving Node to Join

Given the low energy of node and the complex network environment of WSNs, the node failure or sleep scheduling causes rapid changes in the network topology. Therefore, the flexible mechanism of the receiving node is needed to join.

The node that can receive the joining node is defined as the transiting node of leave.

Definition 3.

The transiting node of leave denotes that its child nodes are not the leave nodes in the multicast figure. As shown in Figure 4, $U3$ , $U4$ , $U5$ , and $U6$ are all the transiting nodes of leave.

Figure 4

Tree consisting the transiting node.

Definition 4.

Saturated node: in the transiting node of leave, if the degree is $\text{degree}(u)=\mathrm{\Delta }-1$ , then the node is a saturated node, such as $U4$ and $U5$ nodes in Figure 3. Otherwise, it is an unsaturated node, such as $U3$ and $U6$ nodes.

The receiving node t to join the process of multicast is also added to the tree that consists of the transfer nodes in Figure 4. The process can be divided into two steps as follows: $(1)$ finding the proper unsaturated node to join in the tree; $(2)$ finding k that does not cross paths connected to the source node s.

Figure 5 shows the joining of the node T in the multicast diagram. The node T determines first whether a node of multicast diagram exists in the neighbor nodes. The following three situations exist.

• (i)

  Two or more than two nodes exist. According to the function of the link quality evaluation in Formula (1), two nodes are chosen from many eligible nodes and the request of access is initiated. The node T has two neighbor nodes (i.e., $U6$ and $U7$ ), which are the nodes of diagram in Figure 5. They are requested to join in the multicast diagram.

• (ii)

  If only one node exists, links to join and begins flooding search until another multicast diagram node is found.

• (iii)

  Requests are flooded until two multicast diagram nodes are found if the neighbor node does not exist in the multicast diagram nodes.

Figure 5

Node to join.

Two mutually cross paths ( $Pf$ and $Ps$ ) must be built when the node t connects to the multicast diagram. Let $uf$ be the father node of t in the path of $Pf$ . Specific algorithms are presented in Algorithm 1.

Algorithm 1: Node t building the algorithm of path Pf.

The receiving node t:

From the neighbor node of tor by flooding, find k unsaturated

nodes $\left\{u_i\right\}$ that are not on the path $Pf$ :

  (1) Send paths to $\left\{u_i\right\}$ ;

  (2) Request the unsaturated node $u_i$ and let the best  

paths ${\text{Path}}_{s\to u_i}$ from the source node s to $u_i$ and the weight value   $w({\text{Path}}_{s\to u_i})$ return;

  (3)  $u=\text{Find best path}(t,\left\{u_i\right\},\{{\text{Path}}_{s\to u_i}\}$ , $\{w({\text{Path}}_{s\to u_i})\})$ ,

where Find best path() is as follows:

   The link quality evaluation of query nodes $u_{\mathrm{1}},u_{\mathrm{2}},\dots ,u_m$ is

  $w({\text{Path}}_{s\to u_i})=(D,\text{Bandwidth}({\text{Path}}_{s\to u_i})$ , $\text{Latency}({\text{Path}}_{s\to u_i}))$ for

every unsaturated node $u_i$ ,

 Calculate $w({\text{Path}}_{s\to u_i}\cup e_{u_{i}t})$ ;

 Choose the best path to return;

 The transiting node $u_i$ is

     Receive the requests of the best path ${\text{Path}}_{s\to u_i}$ and the weight value $w({\text{Path}}_{s\to u_i})$ sending from $Pf$ and t;

  If ${\text{Path}}_{s\to u_i}$ and $Pf$ non-intersect, then

      Send ${\text{Path}}_{s\to u_i}$ and $w({\text{Path}}_{s\to u_i})$ ;

      If ${\text{Path}}_{s\to u_i}$ and $Pf$ intersect, but $u_i$ shows another non-intersect path, then $P_i$ and $Pf$ non-intersect.

$Pf$ is the path of the receiving node to the source node. The following setup of another path $Ps$ with $Pf$ is not the path of the cross, as shown in Algorithm 2.

Algorithm 2: Algorithm of node t building the path Pf.

 The receiving node t:

 If the neighbor node of t is an unsaturated node $\left\{u_i\right\}$ ,

      u = Find best path $\left(t,\left\{u_i\right\}\right)$

     $uf=u_i$    $\begin{array}{cc}& pf=Pf\cup u_i\end{array}$ .

   If the neighbor nodes of T are all saturated nodes,

        Search the whole multicast tree

         until an unsaturated node is found,

      u = Find best path $\left(t,\left\{u_i\right\}\right)$

       $uf=u_i$    $\begin{array}{cc}& pf=Pf\cup u_i\end{array}$

   Find best path() is defined as follows:

 Find best path $\left(t,\{u_{\mathit{1}},u_{\mathit{2}},\dots ,u_m\}\right)$ .

 The link quality evaluation of query nodes is $u_{\mathrm{1}},u_{\mathrm{2}},\dots ,u_m$ ,

   $w({\text{Path}}_{s\to u_i})=(D,\text{Bandwidth}({\text{Path}}_{s\to u_i})$ , $\text{Latency}({\text{Path}}_{s\to u_i}))$ ,

 for every unsaturated node $u_i$ ,

  calculate $w({\text{Path}}_{s\to u_i}\cup e_{u_{i}t})$

  Choose the best path to return.

2.2. k-Redundant MABNC

We established k redundant multicast diagram with a special topology based on the above work. The basic characteristic is that every receiving node has k paths. According to this characteristic, we designed a distributed networking coding mechanism to optimize the performance of the wireless sensor multicast. The maximum multicast traffic can be obtained under the same conditions.

In network coding, each transiting node assigns the appropriate coding vector according to certain rules to encode the forwarding data. The receiving node decodes the original data when it collects enough data and coding vector. Data are then received. The core key of this process is to distribute suitable coding vectors to each relay node.

In the tree of k-redundant multicast diagram, for example, 2-redundant multicast, each receiving node has two mutually crossed paths to the source node s. The source node s sends the data a and b in parallel at the same time. The encoding is mainly conducted on the relay node $u_i$ , and the receiving node t can receive the coding vector and coding data at the same time. The source node s generates and distributes each relay node with the suitable coding vector. The generated function of coding vector is expressed as $g(m)$ . The coefficient generation is elucidated in [4]. The encoding vectors are assumed as follows:

$$\begin{array}{cc}& \left\{{\left(p_{\mathrm{1}},q_{\mathrm{1}}\right)}^T,{\left(p_{\mathrm{2}},q_{\mathrm{2}}\right)}^T,\dots ,{\left(p_m,q_m\right)}^T\right\}.\end{array}$$

(3)

The encoding vectors satisfy the following rules:

• (1)

  $p_i,q_i$ are on the domain and linearly independent;

• (2)

  ( $p_i,q_i$ ) and ( $p_j,q_j$ ) are linearly independent, and $i\ne j$ ;

• (3)

  ${(p_i,q_i)}^T$ is the coefficient of a code and can encode the data

  $$\begin{array}{cc}& c_i=\left(a,b\right){\left(p_i,q_i\right)}^T=p_i·a+q_i·b.\end{array}$$

  (4)

$c_i$ and $c_j$ are also linearly independent. In $C=(c_1,c_2,\dots ,c_m)$ , the source node is assumed to produce five coding coefficients: ${(\mathrm{1,0})}^T,{(\mathrm{0,1})}^T,{(\mathrm{1,1})}^T,{(\mathrm{2,1})}^T,\hspace{0.17em}\hspace{0.17em}\text{and}\hspace{0.17em}\hspace{0.17em}{(\mathrm{1,2})}^T$ ; then $C=\{a,b,a+b,2a+b,a+2b\}$ . Any two groups of data in C are linearly independent. They can obtain the data a and b when the nodes of leave receive the two groups of data.

The core problem in the whole process is that how to make the relay node assigns the appropriate coding vector. The relay node is divided into the following two classes for processing:

• (i)

  the relay nodes of indegree 1: as codes are not needed currently, the code vectors must be assigned;

• (ii)

  the relay nodes of indegree 2: the encoding vector is $v_u={(v_1,v_2)}^T$ . Thus, for data x and y that passed through u, the code is $(x,y)v_u=(x,y){(v_1,v_2)}^T=v_{1}x+v_{2}y$ .  u is then sent to the outside of the path.

The distribution of transiting node coding vector is divided into two stages, namely, the distribution and diffusion phases. Generated by the source node s, the corresponding distribution vector is assigned to each relay node. According to Algorithm 3, the source node s distributes the network coding vector to each node in the multicast diagram. The relay node has two indegrees that respond to the request and only one indegree that does not respond to the request. Assuming that a node responds to the request, the node s generates $m+j$ coding vectors, where m coefficient vectors are sent to m requesting nodes and j is the source node $s^{\prime }$ number of child nodes. As shown in Algorithm 4 at the diffusion stage, the source node s first distributes j coding vectors generated at the distribution stage to $s^{\prime }$ nodes of child. The child nodes will further distribute the coding vectors to its downstream nodes to diffuse. In the process, the following two types of nodes are needed to handle:

Algorithm 3: Stage of coding vector distribution.

   Send $P_i$ and $w(p_i)$ ;

   If Indegree $(u_i)=\mathit{1}$ ,

   Contact the child node c of the source node s, and

the subtree of c contained $u_i$ . The unsaturated node v is

then searching in the subtree of c.

Return the

path $P=p(s\to v)\cap p(v\to u)$ and $w(P)$ .

Algorithm 4

  Source node S:

 Broadcast to each relay node of multicast diagram to

distribute coding vector;

 set T = (largest RTT) × 2;

 set timer t = 0, initialize m = 0;

 while ( $t\le T$ )

  Receive $〈\text{request code, address of}\hspace{0.17em}\hspace{0.17em}u〉$ ;

   $m=m+\mathrm{1}$ ;

  node addr [m] = address of u;

   $j=$ Obtain the child nodes of the node s’ number;

  Obtain

  $\begin{array}{c}g(m+j)=\{(p_{\mathrm{1}},q_{\mathrm{1}}{)}^T,(p_{\mathrm{1}},q_{\mathrm{1}}{)}^T\\ \end{array}$ , $\dots ,(p_{m+j},q_{m+j}{)}^T\}$

 for $i=\mathit{1}$ to m

 send $〈\text{code},(p_i,q_i{)}^T〉$ to

      node addr [m];

 Receive the distribution code of the transit node u;

 If indegree $(u)=\mathit{1}$ , then

  Do nothing

 If indegree $(u)=\mathit{2}$ , then

  send message $〈\text{request code, address of}\hspace{0.17em}\hspace{0.17em}u〉$ to s;

 Wait to receive $〈\text{newcode},(p_i,q_i{)}^T〉$ ;

 Set $w\left(u\right):p_u=p_i,\hspace{0.17em}{q}_u=q_i$ .

node u of indegree 1: when receiving the coding vector ${(p_i,q_i)}^T$ from its parent node, the encoding vectors $w(u):p_u=p_i,\hspace{0.17em}{q}_u=q_i$ are set;

node u of indegree 2: the node u is already at the distribution stage $w(u):p_u=p_i,\hspace{0.17em}{q}_u=q_i$ . From two father nodes v, two vectors are obtained at the diffusion stage (Algorithm 5). Supposing ${(p_1,q_1)}^T$ and ${(p_2,q_2)}^T$ , then $v_u={(v_1,v_2)}^T$ . With 1 and 2 to represent the received data from two sides, then $(\alpha ,\beta ){(v_1,v_2)}^T$ is sent to all of the nodes on the edge of the data. We then have

$$\begin{array}{cc}& \left(a,b\right)\left(\begin{array}{cc}{p}_{\mathrm{1}}& p_{\mathrm{2}}\\ q_{\mathrm{1}}& q_{\mathrm{2}}\end{array}\right)=\left(\alpha ,\beta \right).\end{array}$$

(5)

Algorithm 5: Diffusion stage.

 Source node S:

 S has produced $(m+j)$ coding vector.

 For $i=\mathrm{1}$ to j

 send $〈\text{code},g(m+j)〉$ to s’ jth child node addr [j];

 The node of indegree 1 is as follows:

     Receive $(p_i,\hspace{0.17em}{q}_i{)}^T$ sent from its father node;

   Set $w(u):p_u=p_i,\hspace{0.17em}{q}_u=q_i$ ;

    The node of in-degree 2 is as follows:

Receive the coding vectors ${\left(p_{\mathit{1}},q_{\mathit{1}}\right)}^T$ and ${\left(p_{\mathit{2}},q_{\mathit{2}}\right)}^{\mathrm{T}}$ ;

Set $v_u={\left(\begin{array}{cc}{p}_{\mathrm{1}}& p_{\mathrm{2}}\\ q_{\mathrm{1}}& q_{\mathrm{2}}\end{array}\right)}^{-\mathrm{1}}\left(\begin{array}{c}{p}_u\\ q_u\end{array}\right)$ .

The node u is sent to its degree of edge data as follows:

$$\begin{array}{cc}& \left(a,b\right)\left(\begin{array}{c}{p}_u\\ q_u\end{array}\right)=\left(\alpha ,\beta \right){\left(\begin{array}{cc}{p}_{\mathrm{1}}& p_{\mathrm{2}}\\ q_{\mathrm{1}}& q_{\mathrm{2}}\end{array}\right)}^{-\mathrm{1}}\left(\begin{array}{c}{p}_u\\ q_u\end{array}\right).\end{array}$$

(6)

The comprehensive Formulas (5) and (6) can be obtained as follows:

$$\begin{array}{cc}& v_u={\left(\begin{array}{cc}{p}_{\mathrm{1}}& p_{\mathrm{2}}\\ q_{\mathrm{1}}& q_{\mathrm{2}}\end{array}\right)}^{-\mathrm{1}}\left(\begin{array}{c}{p}_u\\ q_u\end{array}\right).\end{array}$$

(7)

In the above process, the relay node u distributes the appropriate coding vector. According to the above analysis, the receiving node t can be decoded to obtain $(a,b)$ as it receives any two coded data.

Theorem 5.

In the 2-redundant multicast tree, after coding and forwarding by the middle node, the receiving node t can encode to obtain $(a,b)$ sent from the source node s.

Proof.

Two mutually disjoint paths $Pf$ and $Ps$ exist according to the construction of 2-redundant multicast tree after the source s multicast forwarded the date $(a,b)$ . Given that the source node s is linearly independent,  ${(p_1,q_1)}^T,{(p_2,q_2)}^T,\dots ,{(p_m,q_m)}^T$ is generated when coding vector. The assumption that the node t from two paths of encoded data is linearly independent can be proved if the two paths of the transit node coding vectors are proved to be linearly independent.

This assumption can be verified using Formulas (5) and (6). If Formulas (5) and (6) were established, $\left(\begin{array}{cc}{p}_{\mathrm{1}}& p_{\mathrm{2}}\\ q_{\mathrm{1}}& q_{\mathrm{2}}\end{array}\right)$ must be reversible, that is, $\left(\begin{array}{cc}{p}_{\mathrm{1}}& p_{\mathrm{2}}\\ q_{\mathrm{1}}& q_{\mathrm{2}}\end{array}\right)$ is linearly independent.

3. Performance Analysis

3.1. k-Redundant Multicast Algorithm Complexity Analysis

The entire network node number is assumed as n from the preliminary figure to construct multicast tree. The main work is to build a tree diagram, of which the whole process is similar to the Bellman-Ford algorithm. The complexity is expressed as ( $VE$ ), where V is for the entire figure on the number of nodes n, and E is used to determine the number of edges. The overall complexity of the algorithm is $O(n^{\wedge }2)$ .

The main task of the receiving node joining is to find neighbor nodes. The number of control message is about $O(n^{\wedge }2)$ . The receiving node in 2-redundant multicast figure finds suitable unsaturated node. The search process is aimed to find tree. The worst case is $O(\log n)$ .

3.2. Network Coding Complexity Analysis

By distributing phase in the entire coding vector, the initialization of message transmission is the broadcasting of multicast tree. The number of packets is O(n). A total of m messages are in response. The message number is O(m). The diffusing phase of coding vector is to spread from each relay node to the child nodes. The number of packets is 2n, so that the overall number of message is O(n).

In the aspect of time delay, the maximum delay from the source node s to the receiving node is T. The source node s in the coding vector distribution stages sets the timing to 2T and initializes the broadcast message for T; thus, the overall worst case is 3T. During the diffusion stage, t is assumed as any two nodes’ maximum delay in the multicast figure. As the distributed algorithm is used, the extension of coding vector is generally not greater than t. Accordingly, the overall coding time delay is O(T).

3.3. Simulation Analysis

3.3.1. Simulation Illustration

To evaluate and analyze the performance of multicast, the NS platform is used for simulation. The experimental environment is as follows: 500 sensor nodes are distributed to 100 m by 100 m square area randomly; the receiving node is 100, and the gathering node is in the network center. The signal collision and the influence of random factors, such as wireless channel interference, are ignored. The other important parameters used in the experiment are shown in Table 1. The topology of the network simulation is shown in Figure 6.

Table 1

Simulation parameters.

Parameter	Value
$d_{\mathit{0}}$ (m)	75
Node initial energy (J)	1–3
$E_{\text{elec}}$	5 nJ/bit
${\epsilon }_{\text{fs}}$	10 pJ/(bit·m2)
${\epsilon }_{\text{mp}}$	0.0013 pJ/(bit·m4)
Message size	4000 bits

Figure 6

Topology of network simulation.

3.3.2. Simulation Analysis

The comparative analyses of several aspects, such as the average energy consumption of nodes, end-to-end delay, and packet loss rate, with the traditional multicast mechanism based on tree and the tree multicast mechanism based on network coding are conducted.

( 1) Average Energy Consumption of Nodes. The node energy consumption is that in WSNs, the average energy consumption in the node running is computed as follows:

$$\begin{array}{cc}& \text{average}\left({\text{noden}}_i\right)=\frac{\mathrm{1}}{n}\sum _{i=\mathrm{1}}^{n}E\left(n_i\right),\end{array}$$

(8)

where n is the number of sensor nodes. As shown in Figure 7, the whole simulation ran for 256 s. The first 120 s is for the building of multicast topology. At this time, the energy consumption is more in the three algorithms. The following 136 s is for the data's multicast process. Based on the simulation curve, the computational cost of the MABNC algorithm of multicast figure based on network coding increased compared with the traditional multicast mechanism based on tree and tree multicast routing algorithms. However, the data retransmission times are effectively reduced and smaller energy consumption is yielded by using the network coding mechanism. Literature [11] indicates that in the sensor network, the bit data of energy consumption that the node sent is equivalent to 1000 times computing. Using the network coding can reduce the number of nodes sending data effectively. Compared with the tree routing mechanism based on network coding, the building and multicasting are more concise by using k-redundant multicast figure and can achieve the maximum theoretical flow of multicast routing.

Figure 7

Average energy of node consumption.

( 2) End-to-End Delay. Overall, the simulation running time is 1000 s. The first 120 s is for building a multicast topology, and the remaining time is for multicasting. As shown in the simulation Figure 8, the tree-based multicast routing mechanism of time delay is the largest. The second is the multicast mechanism by using the mechanism of network coding. As the sensor network nodes change dynamically, the topology is not stable. The tree-based multicasting mechanism needs to maintain and adjust tree and influences the performance of multicast. In the multicasting mechanism of k-redundant based on network coding, the time delay centered in three kinds of algorithm of end-to-end delay. The tree multicasting routing based on network coding has the best performance. After using k redundant, as a result of overlay routing, a bottom support of GEAR is needed and sometime delay is spent.

Figure 8

End-to-end delay.

( 3) Rate of Packet Loss. The rate of packet loss is the index of robustness to reflect the multicast routing algorithm. As shown in Figure 9, in the three kinds of multicast routing mechanism, the packet loss rate is higher because the sensor network environment is complicated and rapid changes exist in the network topology. The algorithm of k-redundant multicast routing has the least rate of packet loss. As k-redundant algorithm uses the idea of multipath, the network robustness is slightly better than the other two kinds of routing.

Figure 9

Packet loss rate.

4. Summary

This paper aims to design the requirements of multicast routing protocol based on WSN as follows: energy efficiency, expandability, robustness, and fast convergence. Based on network coding, k-redundant multicast protocol is proposed and its working process is described. The routing protocol is simulated at the platform of NS2.31. The simulation result indicates that the protocol routing has lower rate of packet loss, small delay, and relatively low cost of the entire network nodes.