Network-Coding-Based Energy-Efficient Data Fusion and Transmission for Wireless Sensor Networks with Heterogeneous Receivers

Abstract

This paper proposes a multirate network coding scheme to improve the energy efficiency of wireless sensor networks (WSNs). Firstly, a five-layer network model is introduced, in which a perfect solution can always be achieved. Then, a network topology which belongs to the five-layer network model will be established from the given sensor networks so that the receivers can receive data at a higher rate without introducing excessive additional transmissions, which improves the energy efficiency as a result. The performance of the proposed scheme is evaluated in a simulated instance, and the result shows that 9% of transmission overhead can be saved compared with traditional scheme.

1. Introduction

How to improve energy efficiency is a main issue in the field of wireless sensor networks (WSNs) since sensor nodes are always deployed in a serious environment and the power is supplied by batteries with limited energy. There are many different methods addressing the energy efficiency issue of WSNs, such as topology control [1, 2], coverage control [3, 4], and data fusion [5]. Network coding [6] is a relatively new technology proven to be effective in improving the throughput and energy efficiency. Network coding can be divided into three parts (i.e., encoding at source node, re-encoding at intermediate nodes, and decoding at receivers). Encoding and re-encoding are used to linearly mix original packets or received packets, so any encoded packet may include the information of multiple original packets. For this reason, network coding can be grouped under data fusion.

In the traditional computer communication networks, the principle of network design is to make the intermediate devices perform straightforward function, while the complicated function is performed in the devices working on the border of networks. Therefore, for a long time, it was generally believed that additional operations at the intermediate nodes would not generate any benefits. However, Ahlswede et al. reversed this belief in their study [6] by proving that after network coding, the network could transmit at the rate of multicast capacity (h) equal to the minimal max-flow to different receivers. This rate cannot be always obtained in traditional store-and-forward networks. After that, network coding has attracted many researchers’ attention. Li et al. [7, 8] proved that linear network coding is sufficient to achieve the multicast capacity. Ho et al. [9] proposed the Random Linear Network Coding (RLNC) in which the encoding coefficients are randomly selected from a specified finite field. Based on RLNC, Chou et al. [10] proposed a practical network coding scheme which has been widely employed in subsequent studies [11–13]. Moreover, there were some coding schemes based on deterministic algorithm in previous studies [14–16].

Network coding has been proven to be energy efficient in both the wired networks and wireless networks, and many researchers have proposed various network-coding-based routing protocols to improve the energy efficiency of WSNs. We observe that, in most traditional network coding schemes, all receivers receive data at the same rate equal to the multicast capacity. However, when wireless network is adopted to transmit media information, such as figure, sound, and video, the receivers prefer receiving as fast as possible, so it is desirable to transmit at a higher rate, which may even be higher than multicast capacity. Take Figure 1, for example.

Figure 1

Multicast network with heterogeneous receivers.

In Figure 1, the max-flows of nodes A, B, and C are 2, 3, and 2, respectively, so multicast capacity h of this network is 2. Note that there are two links becoming bottlenecks, which are highlighted in red. If network coding is not allowed, receivers cannot simultaneously achieve multicast capacity due to the bottlenecks, which is shown in Figure 1(a). In Figure 1(b), multicast capacity can be achieved after using network coding. Furthermore, with the coding scheme shown in Figure 1(c), the nodes A and C could receive data at rate of 2 and node B could receive data at the rate of 3, which implies that the total transmission rate has been increased. Such a scheme enables the receivers to receive more data in a transmission period, so the total required transmission times for a given amount of data will be reduced. Based on this idea, this paper proposes a scheme to improve the energy efficiency of WSNs.

Figure 1(c) is a simple example which shows that certain additional throughput can be obtained. In Figure 1, the max-flows for the three receivers are 2, 2, and 3, respectively. With the new encoding scheme, the transmission rate can be increased by 11.6%. In some practical networks, max-flow for each receiver may be different. For example, if the max-flows are 2, 3, and 4, respectively, then the multicast capacity is 2. Therefore, 1/3 of bandwidth is given up of traditional network coding is employed. If we can make all the receivers receive data at the rate of individual max-flows, the average transmission rate will be increased by 50%. In this example, we observe that the network can transmit more data to receivers in a transmission period without involving excessive links. In this sense, the energy efficiency can be increased, especially when the receivers have different max-flows.

Before network coding was proposed, many researchers [17, 18] addressed the multirate multicast networks by employing layered coding, in which the source node encodes data stream into a base layer and several enhancement layers. If a receiver requires the data on layer k, it must obtain the data on layers $\mathrm{1},\dots ,k-\mathrm{1}$ . In some recent studies [19, 20], the layered multicasting method was combined with network coding to increase the throughput of networks. Figure 2 shows the layered coding scheme.

Figure 2

Layered coding scheme.

Figure 2 can be considered as an 8-by-8 matrix, and the area without shadow is filled with zero. After encoding original packets, it is feasible for the receivers to decode the first and second packets with vectors in row 1 and row 2. Similarly, with the packets in layer 1 and layer 2, the receivers can decode the first five packets, and all the eight packets can be obtained with the data in all 3 layers. In this way, the receivers can receive data at different rates.

Moreover, there are also some studies [19–22] on the practical applications based on multi- rate network coding, such as the multimedia communication. Sundaram et al. [21] proposed a polynomial time algorithm to construct multi-rate network codes for multimedia communication network with heterogeneous receivers. Xu et al. [22] also addressed the construction of multirate network codes through linear programming, and they provided two algorithms to improve the throughput of video stream. When network coding is combined with layered multicast, re-encoding can be performed within the same layer or across different layers, which are regarded as inter-layer network coding and intra-layer network coding. In general, inter-layer network coding outperforms intra-layer network coding, so this paper mainly focuses on the former.

This paper proposes a multirate network coding scheme to improve the energy efficiency of WSNs. This scheme can improve energy efficiency on three aspects: firstly, it can reduce the number of intermediate nodes in which re-encoding operation is required, thus reducing the number of required transmission links; secondly, it can make maximal data fusion with the original packets, which ensures that more data can be sent to receivers in a transmission period; thirdly, this scheme can work on a very small finite field, which indicates that the computation overhead of network coding is low.

The remainder of this paper is organized as follows. In Section 2, some closely related studies are introduced. In Section 3, some preliminaries of linear network coding and employed network model will be described; Section 4 describes the proposed multirate network coding scheme. Section 5 describes some algorithms in the proposed scheme. The result of performance evaluation is provided in Section 6. Finally, the conclusion is made in Section 7.

2. Related Works

Koetter and Médard [23] proved that the perfect solution that can make each receiver receive data at individual max-flow does not always exist. Wu et al. [24] also addressed this issue, and they proved that it is an NP-hard problem to find the multirate solutions that maximize the total transmission rate. Although the perfect solution does not always exist and maximization of the total transmission rate is an NP-hard problem, it is feasible to design algorithms to achieve a good solution.

Kim et al. [25] proposed two prominent heuristic algorithms to construct multirate network codes, called Min-Req and Min-Cut. The two algorithms first determine the max-flows from source node to each node (including both the intermediate nodes and receivers) and then push back the rate requirements from receivers to the source node in an order opposite to the topological order. All the intermediate nodes forward their rate requirements to source node according to Min-Req policy or Min-Cut policy. After the pushback stage, the network code for each link will be assigned according to their rate requirements. Although both methods are efficient and straightforward in implementation, there are some disadvantages. Firstly, all the intermediate nodes and receivers require the knowledge of their max-flows to the source node, so the max-flow algorithm (such as Ford-Fulkerson) needs to be performed many times. Secondly, the decoding at intermediate nodes is required, which will incur higher computation and storage overhead. Thirdly, the link usage rate of these two schemes is very high.

To avoid the decoding operation at intermediate nodes, Widmer et al. [26] also proposed an algorithm. Compared with the two algorithms of Kim et al. [25], the algorithm could achieve a close or even higher throughput. This is a promising scheme in the field of multirate network code construction. Their scheme can be further improved because their flow allocation algorithm may limit the ability of network coding sometimes. When a link has multiple incoming links and is shared by multiple receivers, network coding will be necessary to increase the throughput. However, in their method, the link will be firstly assigned to the receiver with smallest max-flow. After this, when assigning flows for strong receivers, the layer on this link cannot be merged with higher layers or the weak receiver cannot successfully decode. Therefore, their method disqualifies the link for network coding. Theoretically, if network coding is not performed at the intermediate nodes, the potential of network coding will be limited.

Through these algorithms, a good solution can be found for a given network topology. For WSNs, after the sensor nodes are deployed into the environment, the first step is to establish routes such that all nodes are organized into a network. In this paper, we transfer the burden of multirate network code calculation to routing establishment. We will establish a subgraph from the given graph. In the subgraph, we expected that it is straightforward to construct multirate network codes. To this end, we propose a five-layer network model. In this network model, it is easy to construct the multirate network codes. When constructing routing, we ensure that the subgraph must belong to the five-layer network model, and then we can easily assign multirate network codes for WSNs.

In our previous study [27], we also addressed the issue of energy efficiency of WSNs by introducing network coding, and we showed that after combining network coding and opportunistic multipath routing, the energy efficiency could be improved. Through further study on network coding, we observe that the energy efficiency can be further improved. The differences between this paper and the previous one include the following: firstly, a single-rate network coding scheme was employed in the previous study, while a multirate network coding scheme is proposed in this one; secondly, in that paper, it was assumed that all the intermediate nodes were able to reencode, while the number of re-encoding nodes is reduced in this one, which implies that the re-encoding overhead and transmission delay can be reduced; thirdly, in the previous study, the coding scheme was based on a randomized algorithm [10], while the algorithm employed in this paper is a deterministic one proven to be able to perform over a very small finite field. Therefore, the computation overhead of coding is reduced.

Our contribution can be summarized as follows: firstly, we proposed a five-layer network model for multirate network coding and showed that it is easy to assign multirate network codes for the five-layer network model. Moreover, we showed that a perfect solution always exists in the network model. Secondly, we provided a method to establish routing for sensor networks such that the established network belongs to a five-layer network model, and therefore the burden of calculating network codes is reduced. Thirdly, we introduced multirate network coding into WSNs to increase the energy efficiency of transmission.

3. Preliminaries

3.1. Linear Network Coding

Generally, a network can be demonstrated by a directed graph $G=(V,E)$ , where V refers to the node set and E refers to the link set. The node set V consists of a source node S, multiple intermediate nodes, and one or more receivers T. According to previous studies, the network with multiple source nodes can be transformed into the network with one source node, so this paper only addresses the network with one source node. The child node set of node v is denoted by $Child(v)$ , and $|Child(v)|$ represents the number of child nodes in the set. Similarly, $Parent(v)$ refers to the parent set of node v. In addition, $\text{MF}(v)$ represents the max-flow from node v to the source node, and r represents the maximal value in $\{\text{MF}(v_i)\}$ , $v_i\in T$ .

As is known, the “XOR” operation used in Figure 1 is the simplest and most efficient network coding scheme, in which the required field size is 2. In a network with complicated topology, a general method of linear network coding should be employed. When the source node needs to multicast some original packets to a group of receivers, it will firstly select h original packets $P=\{p_{\mathrm{1}},p_{\mathrm{2}},\dots ,p_h\}$ and then obtain a $(n\times h)$ matrix G to encode the h original packets. After using a random or deterministic algorithm, the generator matrix G will be obtained, and then new packets $Y=\{y_{\mathrm{1}},y_{\mathrm{2}},y_{\mathrm{3}},\dots ,y_n\}$ can be calculated, as shown in the following:

$$\begin{array}{l}Y=GP=\left[\begin{array}{lll}{g}_{\mathrm{11}}& \cdots & g_{\mathrm{1}h}\\ ⋮& \ddots & ⋮\\ g_{n\mathrm{1}}& \cdots & g_{nh}\end{array}\right]{\left[p_{\mathrm{1}},p_{\mathrm{2}},\dots ,p_h\right]}^T⟹y_k\\ =\sum _{i=\mathrm{1}}^h\left(g_{ki}\times p_i\right),\hspace{1em}k\in \left(\mathrm{1},\dots ,n\right).\end{array}$$

(1)

After obtaining the new packets, the source node sends the packets Y out along with the corresponding coefficient vectors to its child nodes. If an intermediate node receives one encoded packet, it will forward the packet; if it receives more than one encoded packet, it will reencode the received packets before sending them out. When a receiver gets encoded packets or reencoded packets from its parent nodes, the received coefficient vectors in these packets will form a receiving matrix R according to which the receivers can recover the original packets $P=\{p_{\mathrm{1}},p_{\mathrm{2}},\dots ,p_h\}$ through the Gauss eliminating method.

For multirate network coding, the scheme is supposed to make the receivers receive data at different rates, which implies that the receiver could decode part of P from the data it receives, even if it could not decode all the data in P.

3.2. Network Model

Although network coding is proven to be efficient in both the unicast network and multicast network [28], we mainly discuss it in the multicast network, and the unicast network can be considered as a special case of multicast network. In general, the multicast network includes the following several kinds.

Figure 3(b) shows the classical butterfly model, in which there are two receivers, each with two disjoint paths to the source node S, and there is also an intermediate node which needs re-encoding. The network topology shown in Figure 3(a) can also be considered as a multicast network since there are two receivers, and the two receivers are connected to the same group of parent nodes, so they have equal status. For the network topology shown in Figure 3(c), there are three receivers, and each receiver is connected to a different group of parent nodes. In a practical network, the network may be one of these kinds or their combination. In this paper, we try to address the multicast network in generalized networks, so we generalize the multicast network from the following directions.

• (i)

Generalized Case 1: the multicast capacity should be generalized to $h\ge \mathrm{2}$ , and the max-flow for each receiver may be different.

(ii)

Generalized Case 2: the number of re-encoding intermediate nodes should be generalized. For example, in Figure 3(b), there is only one intermediate node which needs re-encoding, while in a generalized multicast network, the number is increased.

(iii)

Generalized Case 3: the number of the child nodes of the source node $|Child(S)|$ should be greater than the multicast capacity; that is, $|Child(S)|>h$ .

Figure 3

Different kinds of multicast network.

In this paper, we construct the multirate network codes for generalized multicast network mentioned above. To this end, we firstly introduce a five-layer network model as shown in Figure 4. The five-layer network model includes Cases 1 and 2, and it can be easily extended to Case 3. Moreover, due to the topology feature of the five-layer network model, it is easy to assign multirate network codes for such kind of network model. In this paper, we will establish routing such that the established network belongs to the five-layer network model, and then the work to assign network codes could be simplified.

Figure 4

Five-layer network model.

In the five-layer network model, r is the maximal value of max-flows from each receiver to the source node. Obviously, r is greater than the multicast capacity (h) or equal to h when all the receivers have the same max-flow. The number of intermediate re-encoding nodes may be greater than 1. Moreover, the receivers may have different max-flows. It should be noted that the concept of “layer” in the network model is different from that in the layer coding scheme. In the five-layer network model, layer x represents the nodes in $(x-\mathrm{1})$ hops from the source node, while in the layer coding scheme, layer x represents the encoding vectors with which the receivers could decode the original packets.

In this paper, we firstly provide a method to construct the multirate network codes for the five-layer network model, in which Cases 1 and 2 are included. However, Case 3 is not included in the five-layer network model. Then, based on the construction method for the five-layer network model, we propose an edge-eliminating method to construct multirate network codes for the network in Case 3 in Section 4.5.

Notice that, in the five-layer network model, each receiver has several disjoint routes to the source node, and there are four hops from the source node to each receiver. In a practical network, after the routes for each receiver have been established, the number of disjoint routes must be equal to its max-flow, but the hops in each route may be different. Take the network shown in Figure 1 for example; there are some routes to the receivers in two hops. In this case, the network can also be considered as a five-layer network since the network has the features of five-layer network model. On the other hand, if the hops to receivers are greater than 5, it can also be considered as a five-layer network. Therefore, the five-layer network model represents the networks in which $\text{MF}(i)$ disjoint routes are established for receiver i, and some links may become the bottlenecks between the third layer and the fourth layer.

4. Proposed Energy-Efficient Network Coding Scheme

Network coding can be divided into three parts: encoding at the source node, re-encoding at the intermediate nodes, and decoding at the receivers, which can be expressed by the following equation:

$$\begin{array}{cc}& \mathrm{\hspace{0.17em}\hspace{0.17em}}{\left(TG\right)}^{-\mathrm{1}}TGP=P.\end{array}$$

(2)

In (2), P is called the data matrix, and it represents the original packets $[p_{\mathrm{1}},p_{\mathrm{2}},p_{\mathrm{3}},\dots ,p_r]$ , in which each row vector is an original packet, G is called the generator matrix, and T is called the transfer matrix. After employing network coding, P will experience transformations for three times: firstly, $GP$ corresponds to the encoding at the source node; secondly, multiplying the result of $GP$ by matrix T represents the re-encoding operation at the intermediate nodes; finally, multiplying the result of $(T(GP))$ by matrix $(TG{)}^{-\mathrm{1}}$ represents the decoding operation at the receivers. It should be noted that there are r row vectors in P, and the length of these vectors is arbitrary. Moreover, matrix G and matrix T must be square matrices. In a generalized multicast network, there is more than one receiver. If a network coding scheme makes (2) hold for each receiver, the network coding scheme can be considered valid. It should be noted that different receivers may have different generator matrices and transfer matrices, but they have the same data matrix.

Equation (2) shows the condition of valid network codes, but it holds only in single-rate network coding, where the receivers receive at the same rate h ( $h=r$ ). For each receiver, there must be a generator matrix and transfer matrix satisfying (2) in the unirate network coding scheme. However, in a multirate network ( $r>h$ ), (2) only holds for the receiver with r disjoint routes to the source node, and any other receiver may obtain less than r packets from a subset of the r disjoint routes.

Therefore, the design of multirate network codes can be considered as consisting of the following steps: firstly, we need to obtain a full-rank generator matrix and a transfer matrix for the receiver with r disjoint routes to the source node; secondly, we must ensure that all the other receivers can receive as much data as possible.

4.1. Encoding at the Source Node

In this section, we address how to construct multirate network coding without considering the re-encoding operation at the intermediate nodes; in other words, the transfer matrix in (2) is assumed to be an identity matrix.

For the five-layer network model, the only work of the source node is to obtain a full-rank generator matrix. Generally speaking, many methods can be used to obtain a full-rank matrix. For example, the Vandermonde square-matrix must be a full-rank matrix. By multiplying an upper triangle matrix with a lower triangle matrix, it will definitely generate a full-rank matrix. In a single-rate network coding scheme, all the receivers have the same max-flows, so they must be able to decode simultaneously as long as they receive all the encoded packets. However, in a multirate network coding scheme, the number of disjoint routes for each receiver may be different. The receivers with r disjoint routes can successfully decode r original packets, but the receivers with $k\hspace{0.17em}\hspace{0.17em}(k<r)$ disjoint routes cannot receive r linearly independent packets. In this case, if the receivers want to decode k original packets with k received packets, the receiving matrix R must satisfy that $r-k$ unknown elements are indexed by zero in all the k received vectors.

4.2. Re-Encoding at the Intermediate Nodes

As a matter of fact, in a network-coding-based transmission scheme, the improvement of network performance, such as higher throughput and lower energy consumption, always benefits from the re-encoding operation at the intermediate nodes. Without the re-encoding operation, the scheme cannot be considered as a network coding scheme but only a channel coding scheme, and therefore the benefits of network coding cannot be obtained. As mentioned above, the principle of network design is to make the intermediate nodes perform simple functions. However, network coding employs the re-encoding operation at intermediate nodes, which may increase the complexity. Generally speaking, because the re-encoding operation can significantly improve the network performance, such as the throughput and energy efficiency, it is considered worthwhile to use network coding. Although it is proven that the re-encoding operation does more good than harm, we believe that it is necessary to reduce the number of intermediate re-encoding nodes without sacrificing any performance gain of network coding.

From (2), we know that the receiver can decode the original packets under the condition that both matrices G and T are full-rank matrices. In Section 4.1, we ensure that the generator matrix for each receiver is full-rank, and in this section we describe our method to construct the full-rank transfer matrix T. The transfer matrix T is determined by the intermediate nodes, which implies that the re-encoding operation at any intermediate contributes to the transfer matrix T. In accordance with the theory of matrices, we obtain the following theorem.

Theorem 1.

A sufficient and necessary condition for an invertible square matrix M is that $\exists$ a finite number of elementary matrices $P_{\mathrm{1}},P_{\mathrm{2}},\dots ,P_n$ such that $M=P_{\mathrm{1}}{P}_{\mathrm{2}}\cdots P_n$ .

Therefore, we observe that if the transfer matrix T is full-rank, it must be derived from multiple elementary matrices. If we can ensure that each re-encoding operation at the intermediate nodes is equivalent to one or several elementary transformations, the transfer matrix must be full-rank. Our re-encoding method is based on this idea. On the other hand, if a transformation is not equivalent to one or several elementary transformations, the corresponding re-encoding operation must result in a failure at the receiver. In this case, we obtain Lemma 2.

Lemma 2.

A sufficient and necessary condition for a valid re-encoding operation at an intermediate node is that the re-encoding operation must be equivalent to one or several elementary transformations.

Now, the problem of re-encoding at the intermediate nodes is translated into a pure mathematical problem. Next, we will provide our method and show that re-encoding operation of our method must satisfy the condition in Lemma 2 in the five-layer network model.

First of all, we discuss the re-encoding operation on the butterfly model and then extend the discussion to the five-layer network model. In the butterfly model as shown in Figure 3(b), the following transfer matrices can be obtained:

$$\begin{array}{cc}& \text{Left}\hspace{0.17em}\hspace{0.17em}\text{Sink}\hspace{0.17em}\hspace{0.17em}R=\left[\begin{array}{cc}\mathrm{1}& \mathrm{0}\\ \mathrm{1}& \mathrm{1}\end{array}\right]=TG=T\left[\begin{array}{cc}\mathrm{1}& \mathrm{0}\\ \mathrm{0}& \mathrm{1}\end{array}\right],⟹T=\left[\begin{array}{cc}\mathrm{1}& \mathrm{0}\\ \mathrm{1}& \mathrm{1}\end{array}\right],\\ \text{Right}\hspace{0.17em}\hspace{0.17em}\text{Sink}\hspace{0.17em}\hspace{0.17em}R=\left[\begin{array}{cc}\mathrm{1}& \mathrm{1}\\ \mathrm{0}& \mathrm{1}\end{array}\right]=TG=T\left[\begin{array}{cc}\mathrm{1}& \mathrm{0}\\ \mathrm{0}& \mathrm{1}\end{array}\right],⟹T=\left[\begin{array}{cc}\mathrm{1}& \mathrm{1}\\ \mathrm{0}& \mathrm{1}\end{array}\right].\end{array}$$

(3)

Obviously, both transfer matrices are elementary matrices. Then, we prove that, in the single rate multicast network model, the re-encoding operation also satisfies the condition in Lemma 2. Before this, let us discuss the number of re-encoding intermediate nodes. According to our assumption, the source node needs to establish h disjoint routes for each receiver, so we consider the upper bound of the number $h-\mathrm{1}$ , and the lower bound is 0; that is, there are no intermediate nodes required to perform network coding. For each receiver, there are h disjoint routes to the source node. We consider that the difference in the number of hops does not affect the network-coding-based transmission scheme, and at most $(h-\mathrm{1})$ routes will become the bottlenecks. If the number of shared routes is h, the network model will be reduced to the case as shown in Figure 3(a); that is, all the receivers are connected to the same group of parent nodes.

Then, we come back to the discussion of the validity of re-encoding operation at the intermediate nodes in the single-rate multicast network. Note that if the proposition holds when the number of re-encoding nodes is $h-\mathrm{1}$ , it will definitely hold when the number of re-encoding nodes is less than $h-\mathrm{1}$ , so we only need to prove the case in which the number of re-encoding nodes is $h-\mathrm{1}$ . Let the generator matrix be $[{\alpha }_{\mathrm{1}},{\alpha }_{\mathrm{2}},{\alpha }_{\mathrm{3}},\dots ,{\alpha }_h{]}^T$ , in which each element represents a row vector, and after re-encoding at the intermediate node, the received coefficient matrix is $[{\alpha }_{\mathrm{1}},{\alpha }_{\mathrm{2}}\oplus {\alpha }_{\mathrm{1}},{\alpha }_{\mathrm{3}}\oplus {\alpha }_{\mathrm{2}},\dots ,{\alpha }_h\oplus {\alpha }_{h-\mathrm{1}}{]}^T$ , which must be a full-rank matrix. Therefore, the condition in Lemma 2 is satisfied. The difference between our method and the pervious deterministic methods is that we ensure the transfer matrix is full-rank when establishing routing, while the previous method assigned network codes after the route establishment. Therefore, our method must ensure that there are no braided routes from layer 2 to layer 3, while the previous methods do not have this restriction.

So far, we provide our method to obtain the full-rank matrices G and T, so the receivers in single-rate network coding must be able to decode. Moreover, the receiver with the maximal max-flow (r) in multirate network coding is able to decode as well. We wonder whether the other receivers in multirate network coding could decode. To this end, we need to address the influence of re-encoding on the decoding of the receivers first.

4.3. Influence of Re-Encoding on Decoding of Receivers

In this section, we address whether the re-encoding operation at intermediate nodes influences the decoding of receivers whose max-flows are less than r in the multirate network coding. In the single-rate network coding, the re-encoding operation will not result in decoding failure at the receivers as long as it is ensured that the re-encoding operation equals one or several elementary transformations. However, it will result in decoding failure in the multirate network coding scheme. In this section, an example will be provided to show the influence of re-encoding at the intermediate nodes on multirate network coding; then, the reason will be addressed; finally, how our method for intermediate nodes can be used to avoid decoding failure will be discussed.

Example 3.

Take the network in Figure 5, for example.

As shown in Figure 5, there are three disjoint routes from the source node to receiver A and two disjoint routes to receiver B. After employing re-encoding at the intermediate node X, the receiver A can successfully decode the three original packets. However, the receiver B can only obtain one packet.

Recall that our objective is to avoid the decoding failure induced by the intermediate nodes, and in the meantime the network could multicast at a high rate. Intuitively, we consider that receiver B in Figure 5 can receive data at a high rate, so we need to know what the maximal multicast rate is in our model.

Figure 5

Re-encoding in multirate network coding.

4.4. Maximal Transmission Rate in Five-Layer Network Model

In the five-layer network model, the receivers may have different max-flows. We wonder whether there is a method to make each receiver receive data at the rate of individual max-flow, which suggests that the total transmission rate equals $\sum \text{MF}(t)$ , $t\in T$ . $\text{MF}(t)$ refers to the max-flow from source node to receiver t in the established subgraph. Take the network in Figure 6, for example.

Figure 6

Five-layer network with heterogeneous receivers.

In Figure 6, the max-flows for nodes A, B, and C are 2, 4, and 3, respectively, and the symbols a, b, c, and d represent the encoding vectors. The network coding scheme must ensure that node A can decode two original packets from $Parent(A)$ , B can decode four original packets from $Parent(B)$ , and C can decode 3 packets with $Parent(C)$ . Then, we address whether there exist network codes which can make all the three receivers receive data at individual max-flows. We believe that, for the five-layer network model, the multirate network codes which make each receiver t ( $t\in T$ ) receive at the rate of $\text{MF}(t)$ always exist. Then, we explain this perspective in the five-layer network, in which r is arbitrary and the receivers have different max-flows. If we consider that valid network codes must exist, what we need to do is to provide an encoding scheme to satisfy the condition, even though there might be many encoding schemes which could satisfy the condition. From the five-layer network model, we know that the receivers are in the fifth layer, and they are connected to the nodes in the fourth layer. Each receiver may be connected to different groups. We observe that if the global encoding vectors for the links from layer 4 to layer 5 are $n_{\mathrm{1}}{e}_{\mathrm{1}},n_{\mathrm{2}}{e}_{\mathrm{2}},\dots ,n_r{e}_r$ ( $e_i$ is an identity vector with the ith element being 1), respectively, each receiver i, $i\in T$ must be able to get original packets, and the number of original packets must be equal to its max-flow. From (2), we know that if the packets from layer 3 to layer 4 are original packets, then there exists generator matrix G such that $GT=I$ , where I is an identity matrix. In the last section, we pointed out that the transfer matrix T in the five-layer network model must be a full-rank matrix. Therefore, if the generator matrix G is set to be the inverse of T, then $GT$ must be equal to an identity matrix; thus, all the receivers must be able to receive data at the rate of individual max-flows.

We have shown that it is feasible to multicast at a total rate of $\sum \text{MF}(t)$ , $t\in T$ , in the five-layer network model. Then, we come back to address the re-encoding operations at the intermediate nodes, and the only work of intermediate nodes is to mix the input packets into new packets, which has been proven to be valid for the five-layer network model. For the source node, it must satisfy two conditions: firstly, the generator matrix must be a full-rank matrix; secondly, each receiver (t) receives data at the rate of $\text{MF}(t)$ . We proved that the transfer matrix T must be full-rank in the five-layer network model, and therefore $T^{-\mathrm{1}}$ must satisfy condition 1. Moreover, in such encoding scheme, the packets transmitted from layer 3 to layer 4 are original packets, so the second condition can also be satisfied.

4.5. Extend the Method to the Network of Case  3

As mentioned in the last section, the multicast network could be divided into several categories. Moreover, in accordance with Figure 3, we observe that source nodes in Figures 3(a) and 3(b) have two outgoing links, but the source node in Figure 3(c) has three outgoing links even though the multicast capacity for each network is 2. If we divide the network according to the number of outgoing links of the source node, there will be two categories: in one case, $|Child(S)|$ is greater than the multicast capacity (h) and in the other case, $|Child(S)|$ equals h. We observe that the design of multirate network codes for the first category could be transformed to that for the second category. To this end, we propose an edge-eliminating method.

Example 4.

Take the network in Figure 7, for example.

Figure 7

An example of edge-eliminating method.

In the network shown in Figure 7, the max-flows for nodes A, B, C, and D are 2, 2, 2, and 3, respectively. The disjoint routes to node D are $S\text{-}F\text{-}D$ ,   $S\text{-}G\text{-}D$ , and $S\text{-}H\text{-}D$ , so we need to eliminate node E and its associated links. Then, the resulting topology is shown in Figure 7(b), and the new max-flows for nodes A, B, C, and D are 1, 1, 1, and 3, respectively. In the new topology, there are no intermediate nodes needed to be reencoded, which implies that the transfer matrix is an identity matrix. Therefore, the network codes generated by the source node will not be affected by any intermediate nodes. The only work of the source node S is to obtain a 3-by-3 generator matrix $G^{\prime }$ to encode the original packets, which must guarantee that all the receivers could receive at their new max-flows. After obtaining the matrix $G^{\prime }$ , the source node needs to assign a global encoding kernel for $Link(S,E)$ , which must guarantee that the nodes in $Child(E)$ will obtain a new packet. Since the encoding vector is 3-dimensional, nodes A, B, and C could receive at rate 1 and node D could receive at rate 3, and the network codes assigned to $Link(S,F)$ , $Link(S,G)$ , and $Link(S,H)$ must be $n_{\mathrm{1}}{e}_{\mathrm{1}}$ , $n_{\mathrm{2}}{e}_{\mathrm{2}}$ , and $n_{\mathrm{3}}{e}_{\mathrm{3}}$ ( $n_i\ne \mathrm{0}$ , $e_i$ is an identity vector with the ith element being 1), respectively. However, we find that we cannot provide a 3-dimensional encoding vector for $Link(S,E)$ such that the nodes A, B, and C can simultaneously achieve their original max-flows.

Then, we consider whether all the receivers can receive data at the rate of their max-flows in the network of Case 3. When we encode the original data at source node, we select a 3-by-3 matrix as the generator matrix for Figure 7(b) since the maximal max-flow to receivers in Figure 7(b) is 3 and the number of outgoing links is 3. Recall that it is impossible to provide a 3-dimensional encoding vector such that the rate of receivers A, B, and C can be increased by 1, so if we provide a 4-dimesional encoding vector $n_i{e}_i\hspace{0.17em}\hspace{0.17em}(i=4)$ , the receivers could achieve their individual maxi-flows, respectively. Then, the generator matrix G will be extended to a 4-by-4 matrix $(e_4,e_1,e_2,e_3)$ .

In the example, $(|Child(S)|-r)$ equals 1, and if $|Child(S)|$ is much greater than r, the multirate network codes can be gradually obtained with the same method. Therefore, we consider that the construction of multirate network codes for the multicast network as shown in Figure 3(c) can be transformed into the construction of multirate network codes for the five-layer network model.

4.6. Disadvantage of the Proposed Scheme

In general, the network code construction algorithms include centralized algorithms and decentralized algorithms. The main difference between these two algorithms is that the former requires overall network topology of the network, while the latter does not. In the last section, we consider that our scheme is not a decentralized one, because the source node in our model requires the knowledge of the network topology, such as all the routes to each receiver. In addition, because the re-encoding operation at intermediate nodes will influence decoding at the receivers in the multirate multicast network, the source node in our scheme requires a network topology from which the transfer matrix can be formulated. Therefore, our method cannot work in a decentralized manner. After the multirate network codes are calculated, a notification will be broadcasted to the nodes in the networks such that every intermediate node gets the information of the GEVs of incoming links and outgoing links, as well as the strategy of re-encoding.

In the literature [25], the authors provided a pushback algorithm to implement the decentralized network coding scheme. In their pushback algorithm, each receiver needs to initialize a message to allow its parent nodes to gather information of the network, and each intermediate node forwards the message to their parent nodes until all messages reach the source node. In our method, each receiver needs to broadcast a routing establishment packet (REP) in which its own ID number is included in the route table. For each intermediate node, if it has not received the packet, it will add its ID number into the route table and forward the packet to its parent nodes. At last, the source node will have the knowledge of the overall network topology, and then it will calculate the max-flow for each receiver. In a practical network, the routing establishment algorithm and code assignment algorithm only perform once before the data dissemination, so we consider the overhead affordable.

5. Algorithms

5.1. Routing Establishment Algorithm

We need to explain why we prefer to establish disjoint routes for each receiver before the data dissemination. After deploying the sensor nodes in the environment, some links will be established as long as two nodes are in the transmission radius of each other. The max-flow for each receiver may be obtained with the classical Ford-Fulkerson method, and then some redundant links should be eliminated. Otherwise, more energy will be consumed, and these redundant transmissions will not help improving the performance of network. Most importantly, elimination of the redundant links will not reduce the transmission rate. Therefore, we consider it necessary to establish disjoint routes to the source node for each receiver.

Our scheme must be based on the routing establishment algorithm, and the disadvantage of this idea is that it disables the network to work in a decentralized manner. However, in static WSNs, the routing establishment algorithm only performs once, so we believe that the decision does much more good than harm, and the computation overhead of the algorithm is affordable.

5.2. Encoding Scheme

After calculating the max-flows for each receiver with Algorithm 1, the source node will obtain an adjacency matrix A in which the network topology is stored. Algorithm 2 shows the encoding operation at the source node.

Algorithm 1: Routing establishment algorithm.

(1) //  Step  1. Broadcast routes establishment packet (RDP)

(2) Each receiver broadcasts a RDP

(3) For each non-receiver receiving RDP

(4)   If node id in the routing node list

(5)     Give up the packet.

(6)   Else

(7)     Add its node id in the routing node list of RDP.

(8)   Endif

(9)   Continue broadcasting the received RDP to the network.

(10) Endfor

(11) // The source node calculates the max-flow for each receiver with Ford-Fulkerson method.

(12) For node $i=1:t$           % t is the number of receivers.

(13)     flow(i) = GetMaxflow(i)

(14) Endfor

(15)   Establish flow(i) disjoint routes for each receiver(i).

(16)   r = MaxValue(flow(i))            % Get the big value in flow(i), $i\in [\mathrm{1},t]$

(17)   If there is a link braided with the links belonging to receiver with max-flow of r

(18)     Remove the link from the network;

(19)   Endif

Algorithm 2: Encoding scheme at the source node.

(1) // Step  1. Obtain the generator matrix.

(2) If   $n\ge m$      // the number of outgoing links is greater than m

(3)  Use the edge eliminating method to transform the network into five-layer network.

(4) End

(5)  Calculate the transfer matrix T from the matrix A.

(6)   $G=T^{-\mathrm{1}}$ ,      // G and T are $r\times r$ matrices.

(7) For   $i=1:1:r$

(8)     $Y_i={{\displaystyle \sum }}_{i=\mathrm{1}}^r(g_{ki}\times p_i),k\in (\mathrm{1},\dots ,r)$    // $p_i(i\in [\mathrm{1},r])$ are original packets.

(9) End

(10)  If   $n\ge m$

(11)    For   $i=r+1:1:m$

(12)       Add a node $V_i$ and its associated links.

(13)       Assign a global encoding kernel to link(S, $V_i$ ) such that the receivers

(14)       connecting to this node $V_i$ receive a new packet.

(15)     End

(16) End

(17) For   $i=1:1:m$

(18)  The source node sends $Y_i$ to the ith child node.

(19) End

Next, we address the strategies for the intermediate nodes. In our network model, there are two cases of intermediate nodes: firstly, in the case of $|Parent(V)|>\mathrm{1}$ and $|Child(V)|=\mathrm{1}$ , the intermediate node V needs to perform network coding to mix input packets; secondly, in the case of $|Parent(V)|=\mathrm{1}$ and $|Child(V)|\ge \mathrm{1}$ , node V needs to forward input packet to all output links without any change. In the network model, the case of $|Parent(V)|>\mathrm{1}$ and $|Child(V)|>\mathrm{1}$ will not appear since we only assign one link for each node in layer 3, which can be considered as the worst kind of bottleneck. Note that the re-encoding operation is only performed at the node whose outgoing link is shared by more than one route. The other intermediate nodes do not need to perform re-encoding. In this sense, the number of re-encoding nodes has been reduced.

For the receivers, they need to receive and decode. The work of decoding is to solve a system of linear equations, and the classical Gauss eliminating method can be employed.

6. Simulation and Analysis

In our simulations, the source node needs to transmit 30 M bits of data to the receivers, and the transmission capacity for each link is 1 M bits per second. The simulated network consists of a source node, three receivers (denoted by A, B, and C, resp.), and 17 intermediate nodes, as shown in Figure 8.

Figure 8

Simulated network topology.

After performing the routing establishment algorithm, the numbers of disjoint routes to the receivers A (node 20), B (node 21), and C (node 19) are 5, 4, and 3, respectively. Therefore, receiver A will first finish receiving all the data. After receiver A has received all the data, the source node needs to send the remaining data to receivers B and C. At that moment, the data required by the two receivers might be different. Take Figure 1 for example; after receiver B has received $(a,b,c)$ , receiver A requires packet c, while receiver C requires packet a. If some links are shared by the receivers which have not received all the data, the source node must reencode the remaining packets so that the network could transmit at a higher rate.

Based on the simulated network topology, we evaluated the performance of our scheme in terms of decoding rate, throughput, and energy efficiency.

6.1. Decoding Rate

As mentioned above, the network codes can be obtained with either a randomized algorithm or a deterministic algorithm. For a multirate multicast network, there is also a certain amount of work based on the randomized algorithm [25, 26]. We conducted some experiments and obtained some results of the proposed scheme and the previous randomized algorithms.

In Figure 9, we observe that the proposed scheme can be performed over a very small finite field and all the receivers must be able to decode, since it ensures that the generator matrix and transfer matrix are full-rank matrices, while the randomized algorithm may require a relatively larger finite field as the probability of successful decoding increases with the increase of finite size.

Figure 9

Decoding rates of randomized scheme and the proposed scheme.

In general, when computing over a Galois field, it is necessary to generate a 2-dimensional multiplication table and a 2-dimensional division table to accelerate the computation, and the size of the tables is proportional to the field size. When the size is large, it will require a long time to construct the two tables and a large space to store the two tables. Accordingly, the computation overhead and storage overhead over a small finite field are less than those over a large finite field.

According to previous studies, the randomized algorithm used to obtain the network codes has its distinct advantages. For example, it can work in a decentralized manner. However, we consider that, in multirate network coding, a deterministic network coding scheme might be a better choice. In single-rate network coding, all the receivers require the same number of independent packets, and the re-encoding operation does not affect the decoding at receivers as long as it equals the elementary transformation. However, in the multirate network coding scheme based on random algorithm, the receivers may fail to decode even if it is ensured that the re-encoding operation is equivalent to the elementary transformations. If the re-encoding operation is performed on the same layer of each receiver, the decoding will not be affected; however, if the re-encoding operation is performed between different layers, the receiver may be unable to decode.

6.2. Improvement of Throughput

In Figure 10, we observe that the total transmission durations of these three schemes are the same due to the bottleneck caused by the receiver with the least max-flow. After applying the proposed scheme, the total transmission rate has been increased because the slope of the proposed scheme is greater than that of SRNC before the receiver with a high transmission rate has received all the data. After that, the source node starts to transmit the remaining data for other receivers, and the receivers which have received all the data do not receive data any more. Therefore, the slope of the proposed scheme becomes smaller than that of SRNC.

Figure 10

Total throughputs of different schemes.

Although these methods take the same amount of time, the proposed scheme can significantly improve the performance, because in this scheme, the receivers with r disjoint routes could quickly finish receiving the original data. In this paper, there is only one source node. In a practical network, when a receiver receives all the data, it can be considered as a second source, and if this is the case, the performance of network can be further improved.

Therefore, in this experiment, the performance of Min-Cut is better than that of the traditional SRNC, and the proposed scheme has the best performance. We have to admit that Min-Cut can provide multiresolution multicast, while the proposed scheme cannot. The aim of this paper is to increase the throughput and energy efficiency of WSNs, so the proposed scheme is useful from this perspective.

6.3. Improvement of Energy Efficiency

We know that energy consumption is proportional to the total transmission times, and if a scheme can enable all the receivers to receive all the data with less transmission times, the scheme can be considered as energy-efficient. In the SRNC scheme, since the number of routes to each receiver equals the multicast capacity (h), the receivers with more than h routes to the source node must give up some routes so that the transmission energy will be saved or some redundant data will be received without any performance gain. On the other hand, after a receiver with high max-flows has received all the data, the routes to the receivers will be given up to avoid redundant transmission unless the routes are shared by other receivers. In this way, the comparison between the proposed scheme and the previous schemes is reasonable and fair.

In accordance with Figure 11, the energy consumption in SRNC does not change during all 10 transmission periods. For the proposed scheme, the energy consumption is greater than that of SRNC since more links are required to transmit. After the receiver with high max-flow has received all the data, some links are removed, and therefore the energy consumption is smaller than that of SRNC. Then, we accumulate all the energy consumption during each period, and the result shows that the energy consumption of the proposed scheme is less than that of SRNC. Specifically speaking, 9 percent of transmission overhead can be saved in the simulated instance. Moreover, the energy efficiency of Min-Cut is higher than that of SRNC but lower than that of the proposed scheme.

Figure 11

Energy consumptions of different schemes.

In our simulated instance, there are only three receivers. We consider that the proposed scheme could provide more performance gain in the network with more heterogeneous receivers.

7. Conclusions

This paper proposes a multirate network coding scheme to improve the energy efficiency of WSNs. The proposed scheme can improve the energy efficiency on three aspects. Firstly, it can reduce the number of re-encoding nodes without compromising the performance of network coding; secondly, the network can transmit more data in a transmission period, and therefore the energy efficiency can be enhanced; thirdly, the scheme can work over a very small finite field.

In the future, some research should be conducted to improve the performance of WSNs and the theory of multirate network coding.

• (1)

For a generalized network model, we failed to make the source node work in a decentralized manner. In the future work, efforts should be made to improve this problem.

(2)

Our routing establishment method may degenerate the theoretical throughput in some networks; how to avoid this problem is worthy of further research.