Sage Journals: Discover world-class research

Abstract

In energy harvesting wireless sensor networks, energy imbalance among sensor nodes is detrimental to network performance and battery life. Particularly, nodes that are closer to a data sink or have less energy replenishment tend to exhaust the energy earlier, leading to some sub-regions of the environment being left unmonitored. Existing research efforts focus on the energy management based on the assumption that the energy harvesting process is predictable. Unfortunately, such an assumption is not practicable in real-world energy harvesting systems. With the consideration of the unpredictability of the harvestable energy, in this article, we adopt the stochastic Lyapunov optimization framework to jointly manage energy and make routing decision, which could help mitigate the energy imbalance problem. We develop two online policies: (1) Energy-balanced Backpressure Routing Algorithm for lossless networks and (2) Enhanced Energy-balanced Backpressure Routing Algorithm for time varying wireless networks with lossy links. Both Energy-balanced Backpressure Routing Algorithm and Enhanced Energy-balanced Backpressure Routing Algorithm are distributed, queuing stable, and do not require the explicit knowledge of the statistics of the energy harvesting. The simulation data show that our developed algorithms can achieve significantly higher performance in terms of energy balance than existing schemes such as Original Backpressure Algorithm and the Backpressure Collection Protocol.

Keywords

Energy harvesting backpressure routing and stochastic optimization

Introduction

A cyber physical system (CPS) is referred to as a system that integrates the computation and physical processes to monitor and control the physical entities related to physical world. As an extremely critical component in CPS, wireless sensor networks (WSNs) have been widely used in the domain of CPS to observe and cognize the complicated physical system, by leveraging computing and network resources to enable data collection and data transmission.^1,2 Nonetheless, energy supply represents one of the most challenging technological hurdles in WSNs. In traditional battery-powered WSNs, batteries are the dominant energy source and the network lifetime is limited due to the limited battery capacity. To prolong the lifetime of networks, developing completely self-powered wireless electronics has received significant interest. Harvesting energy from environment^3–5 is considered a promising technique in this direction.

Although energy harvesting technologies provide numerous extra energy for nodes, they also pose challenges in balancing energy among nodes. Not only nodes closer to a data sink, but also nodes having less energy replenishment tend to run out their energy at an earlier stage. Although those nodes can be available again after harvesting enough energy from the environment, traffic congestion caused by energy exhaustion will occur, making some sub-regions of the environment being left unmonitored. One simple example of energy imbalance problem is illustrated in Figure 1. The network topology consists of five sensor nodes and a sink. Nodes N₁–N₅ sense the environment and deliver the sensory data to the sink. Note that if $N_{1}$ selects $N_{5}$ as the relay node, $N_{5}$ will run out of its energy and become inactive quickly, due to a low energy harvesting rate and the traffic load of $N_{2}$ . Nonetheless, if $N_{5}$ alternatively delivers packets over the link $(N_{1}, N_{3})$ , the energy of nodes will be better balanced and the network will remain active and functional for a much longer duration.

Figure 1.

An example of energy imbalance problem.

Existing researches^6–10 mainly focused on developing energy management algorithms for energy harvesting wireless sensor networks (EHWSNs) with predictable energy. Nonetheless, a number of energy harvesting processes cannot be accurately predicted in real-world energy harvesting systems (e.g. stochastic harvesting process and partially predictable energy profile).⁶ In addition, the overhead of executing an energy prediction algorithm should be taken into account in resource-limited WSNs. Although some existing works^11–13 proposed energy management schemes for EHWSNs with a stochastic energy harvesting, only the network utility or throughput maximization were focused.

In this article, with the consideration of the energy profile as a stochastic process, we jointly design the energy management and routing process to mitigate the energy imbalance problem^14–16 (also referred to as the hot-spots problem in Challen et al.¹⁵ and Abdulla et al.¹⁶). We tackle this problem using the Lyapunov optimization approach developed in Neely et al.^17,18 The main idea of this technique is to integrate a penalty and utility information into queue backlog gradients, which decrease toward the sink. Using the information about queue backlogs, residual energy and link states, nodes can make the packet routing, power allocation, and forwarding decisions independently. Based on this idea, we first develop an online algorithm, called the Energy-balanced Backpressure Routing Algorithm (EBRA) for lossless networks. In EBRA, greedy decisions are made in every time slot based on the queue backlog and the residual energy information of one-hop neighbors. Our experimental data demonstrate that EBRA can significantly improve the performance in terms of energy balance while guaranteeing the network stability. In addition, we develop an Enhanced Energy-balanced Backpressure Routing Algorithm (EEBRA) for time varying wireless networks with lossy links (lossy networks).

The major contributions of our work are summarized as follows:

We model a queue-based network system and define reasonable penalty functions for links. We show how to incorporate the penalty minimization into the backpressure framework and overcome the energy imbalance problem.

We propose the EBRA for a lossless network. EBRA is a low-cost distributed routing algorithm based on the Lyapunov optimization framework. This algorithm tries to balance the energy among nodes meanwhile stabilizing the network.

We extend EBRA to EEBRA and adapt it for time varying wireless networks with lossy links. EEBRA does not require the knowledge of the harvestable energy process nor the channel statistics. It can be easily implemented in practical WSNs due to its low complexity.

The rest of this article is organized as follows. In section “Related work,” we conduct literature review. In section “Network model and problem formalization,” we present the network model and the problem formulation. In section “Design of energy balance routing scheme,” we present EBRA and EEBRA, respectively. In section “Analysis,” we present the analysis of EBRA and EEBRA. In section “Performance evaluation,” we show the performance evaluation and results. In section “Discussion,” we discuss issues (e.g. how our work helps achieve the management of sensor networks with a large amount of data). Finally, we conclude the article in section “Conclusion.”

Related work

In a CPS or WSN, the knowledge discovery will be helpful for deeper scientific understanding of human–physical world interaction. For example, Boukerche et al.¹⁹ proposed a data mining technique to extract behavioral patterns about sensor nodes during the operation and the obtained behavioral patterns can help enhance the quality of service (QoS) of WSNs. Haghighi et al.²⁰ developed a middleware to detect changes in context. Their proposed method is lightweight and is more suitable for WSNs, which have limited computational resources. Considering that mining the interesting knowledge from the massive amount of data gathered from WSNs is a challenge, Rashid et al.²¹ proposed a new type of behavioral pattern, also referred to as share-frequent sensor patterns, to improve the performance of WSNs in a resource management process.

There have been a number of research efforts on developing energy management schemes in WSNs.^{6–10,14,22,23} For example, Zhao et al.¹⁴ developed a linear programming (LP)-based scheme to maximize network lifetime. Nonetheless, this method is not suitable for EHWSNs and LP requires the statistics of the energy harvesting process. Gorlatova et al.⁶ developed a dynamic programming (DP)-based scheme to maximize the energy utility of a single node as well as the scheme to maximize the utility of data rates for a link. Nonetheless, DP requires the knowledge of the harvestable energy process and its computational overhead increases when the network size grows. Yang et al.¹⁰ addressed the issue of the lexicographic max-min rate allocation problem in solar-powered WSNs and proposed an optimization framework to solve the problem in a distribute manner. Although all these schemes are well implemented in other networks, they cannot be directly used in EHWSNs with stochastic energy harvesting.

The stochastic Lyapunov optimization^{11–13,18,24,25} provides powerful theoretical tools to design scheduling and control algorithms in a backpressure style. A typical goal of the Lyapunov optimization is to optimize a performance objective while stabilizing the network. Because of its adaptation of dynamic systems and performance guarantees, the Lyapunov optimization has been used in both designing scheduling and routing schemes. For example, a close-to-optimal utility is achieved in Gatzianas et al.¹¹ and Huang and Neely.¹² Backpressure Collection Protocol (BCP)²⁴ incorporates the expected number of transmissions (ETX) minimization into the backpressure framework and reduces the cost per packet in the process of data transmission. Mao et al.¹³ developed a scheme to maximize the long-term average sensing rate for all combinations of finite and infinite data and energy buffer sizes. Nonetheless, none of these schemes focus on the energy imbalance problem.

Close to our study, Sarkar et al.²⁶ developed a throughput-optimal routing and scheduling policy, which considers energy fairness and does not need to know the packet and energy arrival rates for EHWSNs. Nonetheless, their developed energy marking process can only work in the network with static links. Different from the existing research, our proposed scheme is designed for dynamic lossy networks and does not require the knowledge of packet rates, energy arrival rates, and the statistics of channel qualities.

Network model and problem formalization

A wireless multi-hop sensor network for data collection can be formalized as a directed graph $(N, L)$ , where $N = {1, 2, \dots, N}$ is the set of vertices that represent sensor nodes, and $L = {(n, m), n, m \in N}$ is the set of edges that represent communication links. Denote $N_{n}$ as the set of one-hop neighboring nodes of n and node n itself. Denote $N_{n}^{out}$ as the set of nodes m with $(n, m) \in L$ and $N_{n}^{in}$ be the set of nodes m with $(m, n) \in L$ . Note that the network model in this article is different from the one in Neely et al.^25,27 We assume that there is only one commodity in the network, which is the data collection commodity for the sink.

Traffic and transmission models

In this article, we consider that the time is divided into identical discrete time slots. In each slot, the network decides the number of packets to admit, which is denoted as $λ_{n} (t)$ . We also assume that $0 \leq λ_{n} (t) \leq λ_{\max}$ for all nodes $n \in N$ with some finite value $λ_{\max}$ at all time. Denote $S (t)$ as the network channel state vector, and denote $s_{n, m} (t)$ as the link (channel) state between node n and m at slot t. We assume that $S (t)$ is independent and identically distributed (i.i.d.) and is in some finite set $S$ . The number of packets sent from node n to m at slot t is denoted as $μ_{n, m} (t)$ , and the power allocated to transmit and receive those pockets are as follows

p_{n, m} (t) = p_{n, m} (s_{n, m} (t), μ_{n, m} (t))

(1)

and

p_{n, m}^{r} (t) = p_{n, m}^{r} (s_{n, m} (t), μ_{n, m} (t))

(2)

respectively. We also assume that $μ_{n, m} (t)$ , $p_{n, m} (t)$ , and $p_{n, m}^{r} (t)$ satisfy constraints, including

0 \leq μ_{n, m} (t) \leq μ_{\max}

(3)

0 \leq p_{n, m} (t) \leq p_{\max}

(4)

and

0 \leq p_{n, m}^{r} (t) \leq p_{\max}^{r}

(5)

for some finite values $μ_{\max}$ , $p_{\max}$ , and $p_{\max}^{r}$ . In addition, p and $p^{r}$ have the following properties: For any link $(n, m), (n, m') \in L$ , if the link state $s_{n, m}$ is better than $s_{n, m'}$ , we have

p_{n, m} (s_{n, m}, μ_{n, m}) \leq p_{n, m'} (s_{n, m'}, μ_{n, m'})

(6)

and

p_{n, m}^{r} (s_{n, m}, μ_{n, m}) \leq p_{n, m'}^{r} (s_{n, m'}, μ_{n, m})

(7)

In addition, $p_{n, m} (s_{n, m}, μ_{n, m})$ and $p_{n, m}^{r} (s_{n, m}, μ_{n, m})$ are non-decreasing functions of $μ_{n, m}$ .

Energy model

In this article, we assume that each node in the network has a finite energy buffer. The residual energy of node n at slot t is denoted as $E_{n} (t)$ and $E_{n} (t)$ is in $[0, E_{\max}]$ for all $n \in N$ and $t \in N_{+}$ , where $E_{\max}$ represents the max energy buffer size. We use $E (t) = (E_{1} (t), E_{2} (t), \dots, E_{n} (t))$ to denote the residual energy vector of the network. Denote $h_{n} (t)$ as the energy harvested in slot t by node n and denote $H (t) = (h_{1} (t), h_{2} (t), \dots, h_{n} (t))$ as the energy harvesting vector. In addition, $h_{n} (t)$ is in $[0, h_{\max}]$ , where $h_{\max}$ is a finite value. For the sake of simplicity, we assume that energy is only consumed during the data transmissions. Therefore, in every slot t, we have the following

\sum_{m \in N_{n}^{out}} p_{n, m} (t) + \sum_{m \in N_{n}^{in}} p_{m, n}^{r} (t) \leq E_{n} (t) + h_{n} (t)

(8)

The above inequality means that the energy consumed by node n must be no more than the available energy of n. Considering that $h_{n} (t)$ varies over time, it is hard to know the available energy exactly. To make sure that node n will not run out of its energy at slot t, we consider the available energy constraint as follows

\sum_{m \in N_{n}^{out}} p_{n, m} (t) + \sum_{m \in N_{n}^{in}} p_{m, n}^{r} (t) \leq E_{n} (t)

(9)

In addition, the residual energy of node n at slot $t + 1$ can be represented by

\begin{array}{l} E_{n} (t + 1) \\ = m i n [E_{n} (t) - \sum_{m \in N_{n}^{o u t}} p_{n, m} (t) - \sum_{m \in N_{n}^{i n}} p_{m, n}^{r} (t) + h_{n} (t), E_{m a x}] \end{array}

(10)

Date queue model

Denote $Q_{n} (t)$ as the data queue length of node n at slot t and denote $Q (t) = (Q_{1} (t), Q_{2} (t), \dots, Q_{N} (t))$ as the data queue vector of the network. Then, we have the data queue length of node n at slot $t + 1$

\begin{array}{l} Q_{n} (t + 1) \leq [Q_{n} (t) - \sum_{m \in N_{n}^{o u t}} μ_{n, m} (t)] + \\ + \sum_{m \in N_{n}^{i n}} μ_{m, n} (t) + λ_{n} (t) \end{array}

(11)

where $[x]^{+} = \max [x, 0]$ . Equation (11) is inequality rather than an equality because $\sum_{m \in N_{n}^{in}} μ_{m, n} (t)$ may be more than the number of actual endogenous arrivals to the node n at slot t. (When node m does not have enough data to forward, idle-fill may be used. The actual endogenous arrivals to node n are none-idle packets received by node n.) We consider a network with a queue backlogs $Q (t)$ is stable if the following constraint is satisfied

\underset{t \to \infty}{lim \sup} \frac{1}{t} \sum_{r = 0}^{t - 1} \sum_{n = 1}^{N} E [Q_{n} (r)] < \infty

(12)

Problem formulation

Our design goal is to design a joint energy management and routing decision scheme so that the energy imbalance problem can be overcome. The basic idea of our approach is based on the Lyapunov optimization approach developed in Neely et al.^17,18

Denote $A$ as the set of all possible control actions (i.e. routing and energy management actions). For a control action $a (t) \in A$ , we define $g = g (a (t))$ as the penalty function of $a (t)$ and $\bar{g}$ as the long time average penalty of $a (t)$ . Our objective is to find a control action $a (t)$ to minimize $\bar{g}$ while meeting the energy available constraint defined in equation (9) and the queue stability constraint defined in equation (12)

\begin{matrix} \min : \bar{g} \\ s . t . (9), (10), (11), (12), \forall m, n \in N \end{matrix}

(13)

Design of energy balance routing scheme

In this section, we first give an overview of our approaches. We then present EBRA for the energy-imbalanced problem in lossless networks. EBRA uses the energy information and queue length of one-hop neighboring nodes to make routing and forwarding decisions. (The forwarding decisions determine whether to transmit packets and how much packets should be transmitted at slot t. Those decisions can also be seemed as data admission control and power allocation decisions.) Finally, we extend EBRA to the time varying wireless networks with lossy links.

Figure 2 shows the detail of our approaches. As we can see from the figure, when a node needs to send packets, it will first check its queue backlog length and residual energy and make penalty estimations for every link based on the information collected from the network (e.g. channel states, residual energy, and queue backlog of neighbors). Note that the channel states can be obtained through mechanisms such as link metric estimation in BCP, and the energy and queue backlog information can be obtained by adding information in a packet head field for disseminating the information or by broadcasting beacons. Then, the controller will make the routing decision and the forwarding decision based on these penalty estimations. The queue backlog and energy information will also be updated after that.

Figure 2.

Overview of EBRA and EEBRA.

Algorithm design in lossless networks

In a lossless network, there is only one element in the channel state set $S$ . This can occur in a static network with low date rates when all links are in good qualities and the network has little collisions. We assume that the energy harvesting process $H$ is a stochastic process and nodes know their own residual energy (e.g. by measuring the battery voltage), the residual energy, and queue backlog length of one-hop neighbor nodes.

In a backpressure-based network, queue backlog gradients decrease toward the sink. This means that nodes with less queue backlog is closer (i.e. smaller geographical distance or fewer hop counts) to the sink. To balance the energy among nodes, it is better to choose neighbors with more residual energy and less queue backlog gradients. (Nodes with more residual energy are usually with better energy replenishment or lower traffic loads.) Accordingly, we use the penalty function of link $(n, m)$ as follows

f_{n, m} = E_{\max} - 1_{Δ Q_{n, m}} \cdot E_{m}

(14)

where

1_{Δ Q_{n, m}} = {\begin{matrix} 1 & if Δ Q_{n, m} > 0 \\ 0 & otherwise \end{matrix}

(15)

Note that forwarding packets to the node m with $Q_{n, m} \leq 0$ may result in routing loops. Therefore, the penalty function sets the penalty of link $(n, m)$ to the maximum (i.e. $E_{\max}$ ) when $Q_{n, m} \leq 0$ . Otherwise, $f_{n, m}$ decreases when $E_{m}$ increases.

To incorporate the penalty function minimization into the backpressure framework, we formalize the following optimization problem

\begin{matrix} \min : g = \sum_{n \in N} \sum_{m \in N_{n}^{out}} μ_{n, m} (t) \cdot f_{n, m} (t) \\ s . t . (9), (10), (11), (12), \forall m, n \in N \end{matrix}

(16)

Then, we define the Lyapunov function as follows

L (t) \overset{Δ}{=} \frac{1}{2} \sum_{n \in N} [Q_{n} (t)]^{2}

(17)

Denote $Z (t)$ as

Z (t) = (Q (t), E (t))

(18)

and define the one-slot conditional Lyapunov drift as follows

Δ (t) \overset{Δ}{=} E {L (t + 1) - L (t) | Z (t)}

(19)

Then, we have following lemma:

Lemma 1

Under any routing and scheduling action and feasible power allocation that satisfies constraint (9) at slot t, we have

\begin{matrix} Δ (t) + V \cdot E {\sum_{n \in N} \sum_{m \in N_{n}^{out}} μ_{n, m} (t) \cdot f_{n, m} (t) | Z (t)} \\ \leq B - E {\sum_{n \in N} \sum_{m \in N_{n}^{out}} μ_{n, m} (t) \cdot [Δ Q_{n, m} (t) + V \cdot {(1}_{Δ Q_{n, m} (t)} \cdot E_{m} (t) - E_{\max})] | Z (t)} \end{matrix}

(20)

where

B = N^{2} \cdot (μ_{\max}^{2} + \frac{1}{2} λ_{\max}^{2} + \frac{1}{2} λ_{\max}^{2} \cdot μ_{\max})

(21)

and V is a constant, which trades system queue occupancy for penalty minimization.

Proof

The proof is similar to Georgiadis et al.²⁷ and Alresaini et al.,²⁸ and we omit it here for brevity.▪

Define the weight per outgoing link as follows

W_{n, m} (t) = Δ Q_{n, m} (t) + V \cdot (1_{Δ Q_{n, m} (t)} \cdot E_{m} (t) - E_{\max})

(22)

Then, we present the EBRA. The algorithm is to minimize the right-hand side (RHS) of equation (20) subject to constraint defined in equation (9). (To minimize the time average penalty while stabilizing the network, algorithms based on the Lyapunov optimization framework can be designed to greedily minimize a bound (i.e. RHS of equation (20)) on the drift-plus-penalty expression (i.e. right-hand side (LHS) of equation (20)) on each slot t.)

Energy-balanced Backpressure Routing Algorithm

At the beginning of every slot t, every node n observe $Q_{m} (t)$ and $E_{m} (t)$ of all nodes $m \in N_{n}^{out}$ , and do:

Routing decision. It computes weights for every neighbor m using equation (22) and finds the link $(n, m^{*})$ with the highest weight as the outgoing link.

Forwarding decision. If $W_{n, m^{*}} (t) > 0$ , it forwards as many packets as the link $(n, m^{*})$ can admit; otherwise, the packets are held until the metric is recomputed.

Queue and energy update. It updates $Q_{n} (t + 1)$ according to equation (11) and computes $E_{n} (t + 1)$ (e.g. using analog-to-digital converters of the node).

The routing decision maximizes $Δ Q_{n, m} (t) + V \cdot (1_{Δ Q_{n, m} (t)} \cdot E_{m} (t) - E_{\max})$ in the RHS of equation (20), and the forwarding decision will find a suitable $μ_{n, m^{*}} (t)$ to minimize the RHS of equation (20). If $W_{n, m^{*}} (t) > 0$ , the maximum value of $μ_{n, m^{*}} (t)$ will be computed under the constraint defined in equation (11) and $μ_{n, m^{*}} (t) \leq μ_{\max}$ . Otherwise, $μ_{n, m^{*}} (t) = 0$ . Note that data transmissions only occur when $Δ Q_{n, m} (t) > 0$ , node n simply only needs to compute weights for those neighbors who have less queue backlog than node n. If the length of a slot time is carefully selected and only one packet can be transmitted per slot (e.g. as in BCP²⁴), the forwarding decision can also be simplified further. Every forwarding node n only needs to check whether there is enough energy for it and the receiver $m^{*}$ to send and receive a packet instead of deriving the maximal value of $μ_{n, m^{*}} (t)$ .

Algorithm design in lossy networks

In a lossy wireless network, the channel state is time varying and the network does not know the channel statistics because of the unreliability of wireless communication. Note that if nodes choose links with poor qualities to forward packets, data transmission will be energy inefficient according to the properties of p and $p^{r}$ . We now show how to balance nodes’ energy in lossy wireless networks.

To represent link quality, we use the ETX as BCP. Assume that node n wakes up at slot t, and transmits $μ_{n, i} (t)$ packets to node i, we denote $E'_{n} (t + 1)$ , $E'_{i} (t + 1)$ , and $E'_{j} (t + 1)$ as follows

\begin{matrix} {E'}_{j} (t + 1) = E_{j} (t) \\ {E'}_{i} (t + 1) = E_{i} (t) - p_{n, i}^{r} (ET X_{n, i} (t), μ_{n, i} (t)) \\ {E'}_{n} (t + 1) = E_{n} (t) - p_{n, i} (ET X_{n, i} (t), μ_{n, i} (t)) \\ j \in N_{n} \land μ_{n, j} (t) = 0, i \in N_{n} \land μ_{n, i} (t) > 0 \end{matrix}

(23)

where $E'_{n} (t + 1)$ , $E'_{i} (t + 1)$ , and $E'_{j} (t + 1)$ represent the residual energy of nodes in $N_{n}$ at the beginning of slot $t + 1$ without the consideration of the energy harvested at slot t.

Considering that the energy harvesting process is unknown, we balance $E'_{m} (t + 1)$ with $m \in N_{n}$ instead of $E_{m} (t + 1)$ as follows

Lexicographically maximize {E'_{m} (t + 1), m \in N_{n}}

(24)

To achieve the goal above, node n needs to compute the lexicographical order of ${E'_{m} (t + 1), m \in N_{n}}$ for every neighbor when it selects them as the next hop. The complexity can be $O (d_{n}^{3})$ in the routing decision stage, where $d_{n}$ is the degree of node n, that is, $| N_{n} | - 1$ .

Considering that the node with the least-residual energy most likely suffers from the hot-spots problem, we first divide nodes in $N_{n}$ into two classes at slot t: (1) class one only includes the node with the least-residual energy and (2) class two includes other nodes. Then, we solve the above optimization problem as follows: If node n is the node with the least-residual energy, we select the link with the best quality to relay packets. Otherwise, we select the node with the largest-residual energy as the next hop. According to the property of p, the next hop $m^{*}$ selected by the approximate approach can be represented by

m^{*} = {\begin{matrix} \arg min_{m \in N_{n}^{out}} ET X_{n, m} & if E_{n} = min_{i \in N_{n}^{out} ⋃ {n}} E_{i} \\ \arg max_{m \in N_{n}^{out}} E_{m} & otherwise \end{matrix}

(25)

The complexity of the approximate approach is only $O (d_{n})$ in the routing decision stage and the approximate approach does reduce the energy consumption of nodes in class one. The reasons can be explained. First, every node in class one will select the best link to transmit packets, leading to the lowest energy costs per packet. Second, nodes in class two will try to avoid forwarding packets to nodes in class one if there are any other relay nodes in class two.

To incorporate the approximate approach into the backpressure framework, we use the penalty function of link $(n, m)$ , which is defined as follows

f_{n, m} = {\begin{matrix} - ε_{1} \cdot 1_{Δ Q_{n, m}} & if E_{n} = min_{i \in N_{n}^{out} ⋃ {n}} E_{i} \land \\ m = \arg min_{m \in N_{n}^{out}} ET X_{n, m} \\ E_{\max} - 1_{Δ Q_{n, m}} \cdot E_{m} & otherwise \end{matrix}

(26)

where $ε_{1}$ is a small constant larger than 0.

Then, we present the EEBRA. At the beginning of every slot t, every node n observe $Q_{m} (t)$ and $E_{m} (t)$ of all nodes $m \in N_{n}^{out}$ , and compute $W_{n, m} (t)$ according to equations (22) and (26). It then selects

m^{*} = \arg max_{m \in N_{n}^{out}} {W_{n, m} (t) | Δ Q_{n, m} (t) > 0}

(27)

as the next hop if $m^{*}$ exists. It also makes forwarding decisions, queue, and energy updates just as EBRA does.

Analysis

In this section, we show the performance analysis of EBRA and EEBRA. We assume that the channel states $S (t)$ and energy harvesting vector $H (t)$ are i.i.d. in all slots. We also assume $a^{*} (t)$ is a control action using a stationary and randomized policy, and the objective $g^{*}$ of problem (13) can be achieved by $a^{*} (t)$ under the energy available constraint defined by equation (9) and queue stability constraint defined in equation (12). Then, we have the following theorem:

Theorem 1

If there are positive constants V, B, $ε$ , and C such that for all slots t and all vectors $Z (t)$ , the one-slot conditional Lyapunov drift satisfies

\begin{matrix} Δ (t) + V \cdot E {\sum_{n \in N} \sum_{m \in N_{n}^{out}} μ_{n, m} (t) \cdot f_{n, m} (t) | Z (t)} \\ \leq B - ε \sum_{n \in N} Q_{n} (t) + V \cdot g^{*} + C \end{matrix}

(28)

the network is strongly stable and the following results (a) and (b) are true.

(a) The time average backlog in lossless networks satisfies

\begin{matrix} \underset{t \to \infty}{limsup} \frac{1}{t} \sum_{r = 0}^{t - 1} \sum_{n = 1}^{N} E [Q_{n} (r)] \leq \frac{B + C + V \cdot g^{*}}{ε} \\ \leq \frac{B + C + V \cdot N \cdot μ_{\max} \cdot E_{\max}}{ε} \end{matrix}

(29)

and the time average backlog in lossy networks satisfies

\begin{matrix} \underset{t \to \infty}{limsup} \frac{1}{t} \sum_{r = 0}^{t - 1} \sum_{n = 1}^{N} E [Q_{n} (r)] \\ \leq \frac{B + C + V \cdot N \cdot μ_{\max} \cdot (E_{\max} + ε_{1})}{ε} \end{matrix}

(30)

(b) The long time average penalty satisfies

sup \bar{g} = \underset{t \to \infty}{limsup} \frac{1}{t} \sum_{r = 0}^{t - 1} E {g (t)} \leq g^{*} + \frac{B + C}{V}

(31)

Proof

The proof is similar to the proof of Lemma 1 in Neely.²⁵ According to Neely,²⁵ (b) is true and the following in equation is true:

\begin{matrix} \underset{t \to \infty}{limsup} \frac{1}{t} \sum_{r = 0}^{t - 1} \sum_{n = 1}^{N} E [Q_{n} (r)] \\ \leq \frac{B + C + V \cdot N \cdot μ_{\max} \cdot (f_{\max} - f_{\min})}{ε} \end{matrix}

(32)

Therefore, (a) is true according to equations (14) and (26).▪

Unlike the penalty function used in Moeller et al.²⁴ and the utility function used in Neely,²⁵ the penalty functions in our article depend on the residual energy vector $E (t)$ , which may result in C varying with V. Nonetheless, we denote that, C is at most $O (V)$ . The reason is that equation (28) will be valid if $C + V \cdot g^{*} \geq V \cdot g$ . Therefore, the time average queue length of EBRA and EEBRA are both $O (V)$ according to the equations (29) and (30).

Performance evaluation

In this section, we provide simulation results of our algorithms. We consider a data collection in a wireless network, which consists of 4 × 4 nodes shown in Figure 3. All the links in the network are bidirectional. Node 1 is the sink node, while the others sense data and forward it to the sink. The energy buffer size of node 1 is set to $+ \infty$ , while the others are set to 2000 units. Each unit of energy can be used to send a packet and a retransmission also costs one unit of energy. For the sake of simplicity, we assume that the reception power $p^{r}$ is negligible. The initial energy of the sink is also set to $+ \infty$ and the others are set to 1000 units. We also assume that nodes can forward at most one packet per time slot.

Figure 3.

A 4 × 4 data collection network.

In both the lossless network scenario and the lossy network scenario, we assume that for every node n, the energy harvested at slot t, that is, $h_{n} (t)$ , is i.i.d. and equally distributed in $[0, 2 {\bar{h}}_{n}]$ , where ${\bar{h}}_{n}$ is initialized to a random value in $[0, 1]$ . The data collection rate $r (t)$ , that is, the packets generated at slot t, is a random value and equally distributed in $[0, 2 r]$ .

We run our EBRA and the Original Backpressure Routing Algorithm (OBRA)²⁹ for 2 × 10⁵ slots, respectively, under different date rates. The results are shown in Figures 4 and 5 and Table 1. Figure 4 shows the average queue length under different data collection rates with the step size 0.005. We can observe that the average queue length of both EBRA and OBRA is slightly larger than 0 when $r \leq 0.075$ . (We denote the average queue length $\bar{Q} = \frac{1}{N} \sum_{n = 1}^{N} Q_{n} (t)$ with $t = 2 \times 10^{5}$ . If the queue is stable, the time average queue length is approximately equal to $N \cdot \bar{Q}$ . Otherwise, the time average queue length is approximately proportional to $\bar{Q}$ according the setting of our experiments. We evaluate $\bar{Q}$ instead of time average queue length here.) This is because the network must maintain queue sizes to provide a gradient for data flow. Meanwhile, there is no traffic congestion caused by running out of energy in all nodes. Due to the lack of energy in some nodes, the average queue length begins to increase as the data sensing rate r increasing when $r > 0.08$ .

Figure 4.

The average queue size of OBRA and EBRA.

Figure 5.

The lowest node energy of OBRA and EBRA.

Table 1.

The number of failed nodes in lossless networks.

Scheme	The number of failed nodes
Scheme	r = 0.06	r = 0.065	0.07 ≤ r ≤ 0.09	r = 0.095
OBRA	0	1	3	3
EBRA	0	0	0	3

OBRA: Original Backpressure Routing Algorithm; EBRA: Enhanced Energy-balanced Backpressure Routing Algorithm.

Figure 4 shows that the average queue length of EBRA is smaller than that of OBRA with the same r. (According to Huang and Neely¹² and Moeller et al.,²⁴ a smaller average queue size is related to a better performance of packet delay.) Figure 5 shows the simulation results of the lowest node energy, that is, $E_{n} (t) = min_{i \in N} E_{i} (t)$ with $t = 2 \times 10^{5}$ . We can observe that some node is running out of energy in OBRA with $r \geq 0.065$ , while with $r \geq 0.095$ in EBRA. This means that EBRA allows a higher data rate than OBRA while experiencing no energy exhaustion. Table 1 shows the number of failed nodes in OBRA and EBRA. From Table 1, we can observe that node failure only occurs when $r \geq 0.095$ in EBRA, while three nodes fail when $r = 0.07$ in OBRA. This is mainly because EBRA always tries to avoid forwarding packets to nodes with less residual energy and EBRA also can reduce unnecessary energy consumption caused by a routing loop.

Figure 6 shows the relationship between the variable V and the average queue length. Considering that the trend of different rates is almost the same, we only plot curves for $r = 0.07$ , $r = 0.08$ , and $r = 0.09$ . We can see that the average queue length increases as V becomes larger. Figure 7 shows the relationship between the lowest node energy and V. We only plot curves for $r = 0.085, 0.09, and 0.095$ as all the energy buffers is almost full when $r \leq 0.08$ . The lowest node energy increases as V becomes larger. The results shown in Figures 6 and 7 match the results from Theorem 1, where V can be seen as a parameter that trades the system queue occupancy for the penalty minimization in the lossless network scenario.

Figure 6.

Average queue length versus V.

Figure 7.

The lowest node energy versus V.

In the lossy network scenario, we run OBRA, BCP, and EEBRA for 2 × 10⁵ slots under different data rates. The variable v is set to 1 for both BCP and EEBRA. The results are shown in Figures 8 and 9 and Table 2. To be specific, Figure 8 shows the average queue length of OBRA, BCP, and EEBRA versus the data collection rates. The average queue length of OBRA is the largest among these three schemes, while EEBRA is slightly larger than BCP. This is mainly because BCP chooses the best link in every packet transmission. Figure 9 shows the simulation results of the lowest node energy under different data rates and Table 2 shows the number of failed node of these three schemes. The results demonstrate that EEBRA allows a higher data rate than both OBRA and BCP while experiencing no energy exhaustion. There are two reasons leading to the results, one is that nodes in class one will select the best downlinks to forward packets, and the other is that nodes in class two will not choose nodes in class one as the next hop if there are any other nodes on their downlinks.

Figure 8.

Average queue length in the lossy network.

Figure 9.

The lowest node energy in the lossy network.

Table 2.

The number of failed nodes in lossy networks.

Scheme	The number of failed nodes
Scheme	r = 0.01	r = 0.015	r = 0.02	r = 0.025	r = 0.035	r = 0.04	r = 0.045	r = 0.05	r = 0.055
OBRA	0	1	1	3	5	6	6	6	6
BCP	0	0	1	1	1	5	5	5	5
EEBRA	0	0	0	0	0	0	1	1	5

OBRA: Original Backpressure Routing Algorithm; EBRA: Enhanced Energy-balanced Backpressure Routing Algorithm; BCP: Backpressure Collection Protocol.

Figure 10 shows the relationship between the variable V and the average queue length. As in EBRA, the average queue length increases as V grows. Unlike EBRA, the routing decision made by nodes in class one is irrelevant to V according to equations (22) and (26). The reason for running out of energy of the first failed node is that the energy harvested cannot afford to transmit the sensing data of its own. Therefore, increasing V contributes little to improve the energy level of the first failed node. Nonetheless, the increase in V does grow the average queue length while decreasing the energy consumed.

Figure 10.

Average queue length versus V in the lossy network.

Discussion

In a CPS, sensor nodes obtain measurements from the physical components, process those measurements, and then send the measured data to the controller through networks. The discovery of useful knowledge from the measured data will be very helpful for conducting a deeper scientific understanding of human–physical world interaction. To this end, a number of research works have been focusing on extracting the useful knowledge from the measured data obtained by sensor nodes.

Nonetheless, sensing, transmitting, and processing the measured data takes both network and computing resources, which are limited in WSNs. How to reasonably schedule the limited resources in WSNs is challenging, especially when the measured data is massive. In this article, we focus on designing an efficient energy scheduling algorithm to balance the energy of nodes so that the network lifetime can be prolonged. To handle a large-scale data, we adopt the Lyapunov optimization framework to design our algorithms. The Lyapunov optimization framework^{11–13,18,24,25} has been proved to be a powerful tool to design networks with maximized throughput and our algorithms takes the advantage of the Lyapunov optimization framework (i.e. achieving a maximized network throughput). This benefit is very useful to WSNs, especially when the data collected by sensors are large.

Conclusion

In this article, we addressed the energy imbalance among sensor nodes in EHWSNs and presented the EBRA for energy balance in EHWSNs. EBRA is a distributed online algorithm and does not need to know the harvestable energy process. We show that EBRA achieves a better performance in both the time average network congestion and the energy balance than that of the OBRA while guaranteeing the network stability. We also developed the EEBRA for lossy networks. Our evaluation data show that EEBRA achieves a better performance in terms of energy balance than that of OBRA and BCP while guaranteeing the network stability.

Footnotes

Academic Editor: Jaime Lloret

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was sponsored by the following funds: the National Natural Science Foundation of China under grant 61502381, the Fundamental Research Funds for the Central Universities under grant xjj2015065, and the China Post Doctoral Science Foundation under grant 2015M570836.

References

Cheng

Gao

. Approximate physical world reconstruction algorithms in sensor networks. IEEE T Parall Distr 2014; 25: 3099–3110.

Chen

Yan

. Ubiquitous monitoring for industrial cyber-physical systems over relay-assisted wireless sensor networks. IEEE T Emerg Top Computing 2015; 3: 352–362.

Percy

Knight

Cooray

. Supplying the power requirements to a sensor network using radio frequency power transfer. Sensors 2012; 12: 8571–8585.

Krishnan

Ezhilarasi

Uma

. Pyroelectric-based solar and wind energy harvesting system. IEEE T Sustain Energy 2014; 5: 73–81.

Romani

Filippi

Tartagni

Micropower design of a fully autonomous energy harvesting circuit for arrays of piezoelectric transducers. IEEE T Power Electr 2014; 29: 729–739.

Gorlatova

Wallwater

Zussman

Networking low-power energy harvesting devices: measurements and algorithms. IEEE T Mobile Comput 2013; 12: 1853–1865.

Lin

Shroff

Srikant

Energy-aware routing in sensor networks: a large system approach. Ad Hoc Netw 2007; 5: 818–831.

Chetto

Optimal scheduling for real-time jobs in energy harvesting computing systems. IEEE T Emerg Top Computing 2014; 2: 122–133.

Martinez

Zhou

Wastage-aware routing in energy-harvesting wireless sensor networks. IEEE Sens J 2014; 14: 2967–2974.

10.

Yang

Mccann

JA.

Distributed optimal lexicographic max-min rate allocation in solar-powered wireless sensor networks. ACM Trans Sens Netw 2014; 11: 9:1–9:35.

11.

Gatzianas

Georgiadis

Tassiulas

Control of wireless networks with rechargeable batteries [transactions papers]. IEEE T Wirel Commun 2010; 9: 581–593.

12.

Huang

Neely

MJ.

Utility optimal scheduling in energy-harvesting networks. IEEE/ACM T Netw 2013; 21: 1117–1130.

13.

Mao

Koksal

Shroff

NB.

Near optimal power and rate control of multi-hop sensor networks with energy replenishment: basic limitations with finite energy and data storage. IEEE T Automat Contr 2012; 57: 815–829.

14.

Cheng

Perillo

Heinzelman

WB.

General network lifetime and cost models for evaluating sensor network deployment strategies. IEEE T Mobile Comput 2008; 7: 484–497.

15.

Challen

Waterman

Welsh

. Idea: integrated distributed energy awareness for wireless sensor networks. In: Proceedings of the 8th international conference on mobile systems, applications, and services (MobiSys), San Francisco, CA, 15–18 June 2010, pp.35–48. New York: ACM.

16.

Abdulla

AEAA

Hiroki

Nei

Extending the lifetime of wireless sensor networks: a hybrid routing algorithm. Comput Commun 2012; 35: 1056–1063.

17.

C-p

Neely

MJ.

Network utility maximization over partially observable Markovian channels. Perform Eval 2013; 70: 528–548.

18.

Neely

MJ.

Stochastic network optimization with application to communication and queueing systems. Synth Lectures Commun Netw 2010; 3: 1–211.

19.

Boukerche

Samarah

Harbi

. Knowledge discovery in wireless sensor networks for chronological patterns. In: Proceedings of 33rd IEEE conference on local computer networks (LCN), Montreal, QC, 14–17 October 2008, pp.667–673. New York: IEEE.

20.

Haghighi

Musselle

CJ.

Dynamic collaborative change point detection in wireless sensor networks. In: Proceedings of 2013 international conference on cyber-enabled distributed computing and knowledge discovery (CyberC), Beijing, China, 10–12 October 2013, pp.332–339. New York: IEEE.

21.

Rashid

Gondal

Kamruzzaman

Share-frequent sensor patterns mining from wireless sensor network data. IEEE T Parall Distr 2015; 26: 3471–3484.

22.

Alrajeh

Khan

Lloret

. Secure routing protocol using cross-layer design and energy harvesting in wireless sensor networks. Int J Distrib Sens N 2013; 2013: 374796.

23.

Alrajeh

Khan

Lloret

. Artificial neural network based detection of energy exhaustion attacks in wireless sensor networks capable of energy harvesting. Ad Hoc Sens Wirel Netw 2014; 22: 109–133.

24.

Moeller

Sridharan

Krishnamachari

. Routing without routes: the backpressure collection protocol. In: Proceedings of the 9th ACM/IEEE international conference on information processing in sensor networks, Stockholm, Sweden, 12–15 April 2010, pp.279–290. New York: ACM.

25.

Neely

MJ.

Energy optimal control for time-varying wireless networks. IEEE T Inform Theory 2006; 52: 2915–2934.

26.

Sarkar

Khouzani

MHR

Kar

Optimal routing and scheduling in multihop wireless renewable energy networks. IEEE T Automat Contr 2013; 58: 1792–1798.

27.

Georgiadis

Neely

Tassiulas

Resource allocation and cross-layer control in wireless networks. Found Trends Netw 2006; 1: 1–144.

28.

Alresaini

Sathiamoorthy

Krishnamachari

. Backpressure with adaptive redundancy (BWAR). In: Proceedings IEEE Infocom, March 2012, pp.2300–2308, https://arxiv.org/pdf/1108.4063.pdf

29.

Tassiulas

Ephremides

Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE T Automat Contr 1992; 37: 1936–1948.

On energy-balanced backpressure routing mechanisms for stochastic energy harvesting wireless sensor networks

Abstract

Keywords

Introduction

Related work

Network model and problem formalization

Traffic and transmission models

Energy model

Date queue model

Problem formulation

Design of energy balance routing scheme

Algorithm design in lossless networks

Lemma 1

Proof

Energy-balanced Backpressure Routing Algorithm

Algorithm design in lossy networks

Analysis

Theorem 1

Proof

Performance evaluation

Discussion

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References