Keywords

1 Introduction

Wireless Sensor Networks (WSN)[1] is a combination of sensor, embedded computing and wireless network communication, which is exploited in several applications such as military defense, industry and agriculture, urban management, etc. With the increase in the amount of information and service diversification, energy-efficiently transmission has become very important for WSN which the energy is constrained. Therefore, research on optimizing the routing protocol in WSN to save energy consumption and extend the network lifetime is of great significance.

Traditional wireless sensor networks protocols such as AODV [2], DSR [3] with minimum hops or expectation transmission times for routing criterion which don’t consider the node energy. Network coding was first proposed by Ahlswede et al. [4] which allowed intermediate nodes to integrate multiple packets into one packet for transmission. It has been shown to be able to achieve sufficiently favorable performance in obtaining high throughput and reducing the transmission energy consumption [5,6,7]. However, these protocols often gain a limited performance improvement in balancing the network traffic with the increasing of data flows. Considering the above limitations, we propose an energy-aware routing mechanism based on network coding, which can make routing decisions with the awareness of both coding opportunity and energy of nodes.

2 Coding-aware Condition

In [8], the author proposed a distributed coding-aware routing mechanism (DCAR), which could concurrently discover the available paths and potential coding opportunities. DCAR can detect coding opportunities on the entire path to achieve high throughput, thus eliminating the “two-hop" coding limitation in COPE. So in this paper, we adopt the coding conditions given in DCAR.

Let a denotes a node and N(a) denotes the set of one-hop neighbors of node a. Let \(a \in F\) denotes a is along the flow F. Let \(U({\mathbf{{a}},F})\) and \(D({\mathbf{{a}},F})\) indicate the set of all upstream nodes of node a in flow F and the set of all downstream nodes respectively. If two flows \({F_1}\) and \({F_2}\) intersect at a node c, packets of them can be encoded for transmission at node c, if and only if the following coding conditions are met:

  1. (1)

    There exists \({d_1} \in \mathrm{{D}}(\mathbf{{c}},{F_1})\) such that \({d_1} \in \mathrm{{N}}({s_2})\), \({s_2} \in \mathrm{{U}}(\mathbf{{c}},{F_1})\), or \({d_1} \in \mathrm{{U}}(\mathbf{{c}},{F_2})\)

  2. (2)

    There exists \({d_2} \in \mathrm{{D}}(\mathbf{{c}},{F_2})\) such that \({d_1} \in \mathrm{{N(}}{s_1}\mathrm{{)}}\), \({s_1} \in \mathrm{{U}}(\mathbf{{c}},{F_1})\), or \({d_2} \in \mathrm{{U}}(\mathbf{{c}},{F_1})\).

3 Routing Strategy

3.1 Routing Metric

Coding cost. With network coding in data transmission of wireless sensor network, if a new flow can be encoded with existing flows, it requires no additional cost in “free-ride" by existing flows. However, a new data flow does not always fully carry on other existing flows due to the mismatch transmission rate in actual network. Therefore, we combine the network coding with the transmission rate of data flows to decide the coding cost function of nodes.

Consider a link \({n_i} \rightarrow {n_j}\), the coding cost of node \({n_j}\) is denoted by cost (j).

$$\begin{aligned} \mathrm{{cost}}\left( j \right) = \left\{ \begin{array}{l} 0 \qquad \qquad {n_j}\text { with coding, }{R_{req}} \le R\\ \frac{{{R_{req}} - R}}{{{R_{req}}}} \,\,\,\,\,\,\,\, {n_j}\text { with coding, }{R_{req}} > R\\ 1 \qquad \qquad {n_j}\text { without coding} \end{array} \right. , \end{aligned}$$
(1)

where R is the matching rate, i.e. the transmission rate of the existing flow, \({R_{req}}\) is the request transmission rate of the new flow.

Node congestion degree. Adopting the coding-aware, we can select the node with coding opportunities as the next-hop node to improve the network throughput. However this will lead to a large amount of data flows converge to the coding node, and the energy of this node is consumption very quickly. To avoid the network link failure caused by the energy depletion, we predict the congestion degree in the next-hop node according to the speed of energy consumption.

Each node updates its congestion degree after a sampling period T. The congestion degree of node is denoted by v(t).

$$\begin{aligned} \mathrm{{v}}\left( \mathrm{{t}} \right) = \frac{{{E_{res}}\left( {t - 1} \right) - {E_{res}}\left( t \right) }}{{T \cdot {E_{initial}}}}\mathrm{{ }}\mathrm{{.}} \end{aligned}$$
(2)

where \({E_{initial}}\) donates the initial energy of nodes, \({E_{res}}\left( t \right) \) expresses the residual energy of nodes after t cycles. v(t) formulates the energy consumption speed of nodes at the t cycle, which represents the current congestion degree. The larger value of v(t) shows the more data flows go through the node within period T, which indicates the more serious congestion. Therefore the congestion degree of nodes is considered in route selection to balance the traffic of the whole network.

Path transmission cost. Consider a path \(\mathrm{{L: s}} \rightarrow {n_1} \rightarrow {n_2} \rightarrow {n_i} \rightarrow {n_j} \cdots \rightarrow {n_k} \rightarrow \mathrm{{d}}.\) The cost function C(L) is defined as the sum cost of all links on this path.

$$\begin{aligned} \begin{array}{l} \mathrm{{C}}\left( \mathrm{{L}} \right) = \mathop \sum \limits _{i = 1}^k \mathrm{{C}}\left( {\mathrm{{Lin}}{\mathrm{{k}}_{ij}}} \right) \\ \mathrm{{C}}\left( {\mathrm{{Lin}}{\mathrm{{k}}_{ij}}} \right) = \mathrm{{\alpha cost}}\left( \mathrm{{j}} \right) + \mathrm{{\beta }}{\mathrm{{v}}_j},\mathrm{{ }}\alpha + \beta = 1\mathrm{{ ,}} \end{array} \end{aligned}$$
(3)

where \(\mathrm{{Lin}}{\mathrm{{k}}_{ij}}\) indicating the condition that node \({n_i}\) selects \({n_j}\) as the next-hop by considering the coding opportunities and congestion degree of \({n_j}\), and \(\mathrm{{C}}\left( {\mathrm{{Lin}}{\mathrm{{k}}_{ij}}} \right) \) is the cost of \(\mathrm{{Lin}}{\mathrm{{k}}_{ij}}\), and are tuning factors which can be adjusted adaptively according to current network state.

Routing metric function. Apart from the transmission cost, balancing the network residual energy is important when selecting a transmission path. We donate as the normalized minimum residual energy of nodes on the path.

$$\begin{aligned} \mathrm{{\varepsilon }} = \frac{{{E_{min}}}}{{{E_{initial}}}}\mathrm{{ }}\mathrm{{.}} \end{aligned}$$
(4)

Based on above analysis, we propose a novel energy-aware routing metric M(L).

$$\begin{aligned} \mathrm{{M}}\left( \mathrm{{L}} \right) = \frac{{C\left( L \right) }}{{Max\ \varepsilon }}\mathrm{{,}} \end{aligned}$$
(5)

where C(L) is the path transmission cost, Max is the maximum of minimum residual energy of nodes. The optimal path can be obtained by searching the minimum M(L). Then an optimal route will be selected which can not only keep the transmission cost at a low level but also protect the node with low energy, thus balancing the energy and traffic as well as extending the lifetime of network.

3.2 Routing Process

Packet format. Considering the node coding opportunities, congestion degree and the residual energy in route selection, we modify the RREQ as shown in Fig. 1. In addition to the basic routing information such as source ID, destination ID and routing ID, RREQ also increases the routing request rate (\({R_{req}}\)), coding cost, node congestion (v), minimum residual energy (), and so on.

Fig. 1.
figure 1

RREQ packets format.

Full size image

Route discovery. By using route discovery process we obtain the optimal path of data transmission in wireless sensor networks, and more details about this route discovery process can be referred to [7]. It’s worth noting that during this period, the RREQ packet is updated by the transmission cost of path and the minimum residual energy of nodes, and then the new routing metric \(M{(L)_{new}}\) is calculated and compared with previous \(M{(L)_{original}}\) by the following formula. Finally the smaller one will be saved, and this intermediate node continue to broadcast to the next node.

$$\begin{aligned} \mathrm{{M}}\left( \mathrm{{L}} \right) = \left\{ {\begin{array}{*{20}{c}} {M{{\left( L \right) }_{new}},\mathrm{{ }}M{{\left( L \right) }_{new}} \le M{{\left( L \right) }_{original}}}\\ {M{{\left( L \right) }_{original}},\mathrm{{ }}M{{\left( L \right) }_{new}} > M{{\left( L \right) }_{original}}} \end{array}} \right. \mathrm{{.}} \end{aligned}$$
(6)

Route maintenance. When the energy of node is unable to meet the transmission energy, the routing link will be failure. So we set the threshold of the minimum residual energy \({\varepsilon _h}\). If the residual energy of node is lower than \({\varepsilon _h}\), the local routing maintenance will be triggered. Then this node exchange information with its neighbors to find a new link instead and thus preventing routing interrupt.

4 Experimental Results and Analysis

In this section, we conduct simulations to evaluate the performance of NCEAR using MATLAB compared with AODV [2], COPE [5] and ERPNC [7]. The simulation area size is set to 300 m with 30 static nodes placed randomly, and all nodes connected by wireless link. Each node is initially set to 50 J and the communication radius is set to 30 m. The link bandwidth is set to 2 Mbit/s. The period T of predicting congestion degree of nodes is set to 5 s, and the minimum residual energy threshold is set to 5 J. The number of flows in network is varied from 2 to 20. Simulation results are taken from an average of 20 experiments.

Figure 2(a) shows the network throughput situation of four protocols. At the beginning, the performance of network throughput of four protocols are roughly the same. With the number of data flows increasing, the advantage of COPE, ERPNC and NCEAR begin to emerge which can utilize network coding opportunities to increase the network throughput. ERPNC and NCEAR can further improve performance by using the distributed network coding to perceive potential coding opportunities compared with COPE which utilize passive encoding. The performance of NCEAR is better than ERPNC with considering the coding opportunities and congestion degree in selecting the next-hop node.

Fig. 2.
figure 2

Experimental results

Full size image

Figure 2(b) shows the residual energy variance of nodes for four protocols. With the increase of data flows, these protocols become unbalanced gradually in network remaining energy. The performance of NCEAR and ERPNC is more balanced than AODV and COPE with considering the residual energy of nodes. NCEAR is capable of considering the congestion degree as well as the minimal residual energy of nodes in the path, which is superior to ERPNC and has further balanced the energy consumption of network.

Figure 2(c) depicts the network lifetime of four protocols. It can be seen that the lifetime of network will decrease as the increase of data flows. The network lifetime of NCEAR is longest with considering the coding opportunities and balancing the energy and traffic of network.

5 Conclusion

In this paper, an energy-aware routing protocol based on network coding (NCEAR) is proposed for the data transmission, which incorporates potential coding opportunities and congestion degree of node into route selection. It can reduce the energy consumption and balance the network traffic. In addition, the routing metric of NCEAR considers the node with minimum residual energy in the transmission path and sets the threshold of minimum residual energy in routing maintenance, thus effectively avoiding the link failure and reducing the number of routing maintenance caused by energy shortage. Simulation results demonstrate that the protocol achieves favorable performance in increasing the network throughput, prolonging the network lifetime and balancing the energy and traffic of network. resents its corresponding label, and \(\phi \) donates the kernel function.