1 Introduction

With rapid development of microelectronics and wireless communications in recent years, wireless sensor networks (WSNs) have been widely used in a broad range of applications [1–4]. Although wireless sensor nodes are low-cost, small-sized and easy for deployment, they are powered by batteries and replacing the battery is not feasible in many applications. Hence, a critical challenge in WSNs is their finite lifetime [5]. Recent years have witnessed the emergence of a promising technology to address this issue - harvesting energy from environment to extend the lifetime of WSNs. Known examples of harvestable energy resources include solar [6], electromagnetic wave [7], thermal [8], wind [9], and vibration [10], which opens up a new research area referred to as rechargeable sensor networks (RSNs) [11, 12].

Consider an RSN with a number of source nodes and a sink node. Each source samples data and transmits data, through some other sources (relays) to the sink. If each source transmits data through a single path of time-invariable relays to the sink, the RSN is referred to as a static-routing RSN. Otherwise, if each source transmits data through multiple paths of time-variable relays to the sink, the RSN is referred to as a dynamic-routing RSN. Existing works on RSNs mainly focus on optimal lexicographic rate assignment [13], minimizing data loss [14] or maximizing total throughput [15], and network utility maximization (NUM) [16]. In this paper, our objective is to maximize the network utility. This paper will focus on the NUM problem in dynamic-routing RSNs, while the static-routing case has been well studied in the previous work [17]. In [17], each source has a single fixed relay. In other words, the routing structure is a given tree, and the NUM problem is rate control and energy management. In our work, each source needs to choose relays and determine flow rates. In this context, flow rates will be the additional variables in the problem formulation to design the optimal routing. Thus, rate control, routing, and energy management need to be jointly optimized. However, since the energy consumption rate for data transmission depends on routing and is no longer fixed as in the static-routing case, the problem would become more complicated to solve. In both cases, there exist two aspects of constraints on each source [18, 19]. One is the flow constraint, i.e., the incoming flow rate plus the sampling rate should not exceed the outgoing flow rate, and the flow rate should not exceed the link capacity. The other is the energy constraint, i.e., the energy consumption rate should be neither too large such that the source depletes the battery and stops working (aggressive case), nor too small such that the battery level reaches maximum and misses recharging opportunities (conservative case).

From the above, we need to jointly consider the flow and energy constraints to maximize the network utility of dynamic-routing RSNs. This problem is very challenging since the flow constraint is spatially coupled and the energy constraint is spatiotemporally coupled (energy causality). Therefore, the distributed NUM problem in dynamic-routing RSNs needs to be thoroughly investigated. Existing works either do not fully consider the two coupled constraints together, or heuristically remove the temporally-coupled part, both of which are not practical, and may degrade network performance. For example, the flow constraint is addressed in dynamic-routing WSNs [20]; however, the recharging technology and energy constraint are not taken into consideration. The energy constraint considered in [21] is that the energy consumption rate does not exceed the energy harvesting rate instead of the current battery level, let alone the finite battery capacity. Zhang et al. [22] consider the energy constraint that the energy consumption rate does not exceed the energy allocation; however, the energy constraint is heuristically solved without considering the global optimality.

In this paper, we take the attempt to jointly optimize rate control, routing, and energy management by carefully tackling the flow and energy constraints. To this end, we first decouple the original problem equivalently into separable subproblems by means of dual decomposition. Then we propose a distributed algorithm, which can converge to the globally optimal solution. The main contributions are summarized as follows:

  1. 1.

    By carefully tackling the flow and energy constraints through primal-dual approach, we propose a distributed algorithm to obtain the globally optimal solution.

  2. 2.

    Numerical results based on real solar data are presented to evaluate the optimality and scalability of the proposed algorithm.

The remainder of this paper is organized as follows. In Section 3, we formulate the NUM problem in dynamic-routing RSNs with the flow and energy constraints. The problem is dually decomposed into separable subproblems in Section 4. Then in Section 5, we propose a distributed algorithm to obtain the globally optimal solution. Numerical results are provided in Section 6, and concluding remarks are drawn in Section 7 with future work.

2 Related works

In RSNs, harvestable energy resources include solar, electromagnetic wave, thermal, wind, and vibration. The research on harvesting energy from these resources has drawn considerable attention in recent literatures, e.g., harvesting energy from wireless charging and wireless power transfer processes [23–25]. The problem of rate control, routing, and energy management in dynamic RSNs has been addressed by prior works. For example, Marašević et al. [26] provide a comprehensive algorithmic analysis of max-min fairness in energy harvesting networks by rate allocation and routing. Chen et al. [27] address the problem of joint energy allocation and routing to maximize the total utility of an RSN, without prior knowledge of the replenishment profile. They propose a low-complexity online solution that achieves asymptotic optimality. Liu et al. [28] study the problem of computing the lexicographically maximum data collection rate and routing paths for perpetual and fair data sensing. They compute the optimal rate when the routing structure is a given tree, and further jointly compute a routing structure and the near-optimal rate.

There are several recent works that aim to maximize the network utility of dynamic-routing RSNs. For example, Liu et al. [21] propose the QuickFix algorithm for computing the data sampling rate and routes, and the SnapIt algorithm to adapt the sampling rate to the battery level. They show that these two algorithms can track the instantaneous optimum network utility while maintaining the battery level at a target value. However, they only consider the energy consumption rate less than the energy harvesting rate instead of the current battery level, let alone the finite battery capacity. Without considering the current battery level, such constraints are not coupled across the time horizon, making the problem easier to solve. However, since the excessive harvested energy cannot be stored in the battery for later use, there is no flexibility to allocate the sampling rate evenly among sources and time horizon, and hence the network utility is not optimized. Zhang et al. [22] are concerned with how to maximize the overall network performance with finite battery capacity. They develop the BEAS algorithm to efficiently manage the battery energy usage, and the DSR2C algorithm for obtaining the optimal sampling rate and routing. They consider the energy constraint that the energy consumption rate does not exceed the energy allocation. Although the energy allocation problem is formulated based on the energy harvesting rate and current battery level, it is heuristically solved without considering the global optimality.

Different from aforementioned works, this paper is concerned with the NUM problem in dynamic-routing RSNs with the flow and energy constraints. Our goal is to jointly optimize rate control, routing, and energy management by carefully tackling the flow and energy constraints. Besides, the proposed distributed algorithm can converge to the globally optimal solution.

3 System model and problem formulation

3.1 System model

We now consider a dynamic-routing RSN with a set \(\mathcal {N} \triangleq \left \{1,\cdots ,N\right \}\) of source nodes and one sink node s, as shown in Fig. 1a, where d i j (or d i s ) is the physical distance between source i and source j (or sink s). Each source has a solar photovoltaic panel and a rechargeable battery, such that the excessive harvested energy can be stored in the battery for future use. Each source consumes energy in its battery to sample data and transmit data to the sink via multi-hop communications. We assume a time-slotted system where the time cycle of energy harvesting is divided into a set \(\mathcal {H} \triangleq \left \{1,\cdots ,H\right \}\) of equal time slots. In this paper, we consider one day (daytime) as a time cycle, e.g., from 8:00 to 16:00. An example of the energy harvesting rate (J/s) over this time cycle is shown in Fig. 1b, which is based on the real solar data collected from the Baseline Measurement System at the NREL Solar Radiation Research Laboratory [29] on December 12, 2012. If we assume that the duration (granularity) of a time slot is Δ=10 min, then the total number of time slots is H=48. Since this work mainly focuses on jointly optimizing rate control, routing, and energy management to maximize the network utility of dynamic-routing RSNs, the channel model and link scheduling in the MAC layer can be referred to existing literatures [30]. The prime role of MAC is to coordinate access to and transmission over a common medium (wireless channel). The survey [30] provides a comprehensive state-of-the-art study on WSN MAC protocols, which can be trivially employed in RSNs.

Fig. 1
figure 1

System model

Full size image

Some important notations used in this paper are summarized in Table 1. In the remainder of this work, we also use the following mathematical notations: ∥x∥2 denotes the \(\mathcal {L}_{2}\) (Euclidean) norm of x; [⋅]+ denotes max{⋅,0}; \({\left [\cdot \right ]_{a}^{b}}\) denotes min{max{⋅,a},b}; f ′(⋅) denotes the first derivative of function f(⋅); and f −1(⋅) denotes the inverse of function f(⋅).

Table 1 Summary of notations
Full size table

3.2 Flow constraint

At each time slot \(h \in \mathcal {H}\), let \({r_{i}^{h}}\) denote the source i’s sampling rate, and \(f_{ij}^{h}\) (or \(f_{is}^{h}\)) for the flow rate from source i to source j (or sink s). The link from source i to source j (or sink s) has finite link capacity \(c_{ij}^{h}\) (or \(c_{is}^{h}\)), which changes at each time slot \(h \in \mathcal {H}\). We consider fractional routing in this paper. Thus, the flow constraint of each sourceFootnote 1 is

$$ \sum\limits_{j \in \mathcal{N}} {f_{ji}^{h}} + {r_{i}^{h}} \le \sum\limits_{j \in \mathcal{N} \cup \{s\}} {f_{ij}^{h}}, $$
(1)
$$ f_{ij}^{h} \le c_{ij}^{h} \quad \forall j \in \mathcal{N} \cup \{s\}, $$
(2)

which indicates that the incoming flow rate plus the sampling rate should not exceed the outgoing flow rate,Footnote 2 and the flow rate should not exceed the link capacity. This is the spatially-coupled constraint which couples one link’s flow rate with those of others.

3.3 Energy constraint

At each time slot \(h \in \mathcal {H}\), let \({\pi _{i}^{h}}\) denote the source i’s energy harvesting rate, which is a random variable as shown in Fig. 1b. In this paper, we assume it to be predicted and estimated with high accuracy based on historical data and advanced technology [31]. Each source consumes energy for sensing and communication (including data reception and transmission). Let \({e_{i}^{r}}\) and \({e_{i}^{s}}\) denote the source i’s energy consumption rates for receiving and sampling a unit of data, respectively. Further, let \(e_{ij}^{t}\) (or \(e_{is}^{t}\)) denote the source i’s energy consumption rate for transmitting a unit of data to source j (or sink s) which is d i j (or d i s ) apart: \(e_{ij}^{t} = \alpha _{1} + \alpha _{2} d_{ij}^{\beta }\) (or \(e_{is}^{t} = \alpha _{1} + \alpha _{2} d_{is}^{\beta }\)), where α 1,α 2>0 are the constant coefficients and β is the path loss exponent (2≤β≤4 for the free-space and short-to-medium-range radio communication) [32]. The total (here the term “total” includes receiving, sampling, and transmitting) energy consumption rate of each source is defined by

$$ {\psi_{i}^{h}} \triangleq {e_{i}^{r}} \sum\limits_{j \in \mathcal{N}} {f_{ji}^{h}} + {e_{i}^{s}} {r_{i}^{h}} + \sum\limits_{j \in \mathcal{N} \cup \{s\}} {e_{ij}^{t} f_{ij}^{h}}, $$
(3)

where one source’s flow rate is coupled with those of others.

Let \({B_{i}^{h}}\) denote the source i’s battery level at the end of time slot h, which is calculated as

$$ {B_{i}^{h}} = \left[ B_{i}^{h-1} + {\pi_{i}^{h}} {\Delta} - {\psi_{i}^{h}} {\Delta} \right]_{0}^{B_{i}^{\max}}, $$
(4)

where Δ indicates the duration (granularity) of a time slot, and \(B_{i}^{\max }\) denotes the source i’s battery capacity. For ease of presentation, define a surplus variable [16, 28]

$${\delta_{i}^{h}} \triangleq \left[ B_{i}^{h-1} + {\pi_{i}^{h}} {\Delta} - {\psi_{i}^{h}} {\Delta} - B_{i}^{\max} \right]^{+} $$

as the “missed energy”, whose physical meaning is the amount of the harvested energy that cannot be stored in the source i’s battery at time slot h if the battery is full. If the source i’s battery at time slot h is not full, then \({\delta _{i}^{h}}=0\). By use of \({\delta _{i}^{h}}\), Eq. 4 can be recursively calculated by

$$ \begin{array}{lllllll} {B_{i}^{h}} & = B_{i}^{h-1} + {\pi_{i}^{h}} {\Delta} - {\psi_{i}^{h}} {\Delta} - {\delta_{i}^{h}} \\ & = {B_{i}^{0}} + \sum\limits_{t=1}^{h} {{\pi_{i}^{t}} {\Delta}} - \sum\limits_{t=1}^{h} {{\psi_{i}^{t}} {\Delta}} - \sum\limits_{t=1}^{h} {{\delta_{i}^{t}}}, \end{array} $$
(5)

where the source i’s initial battery level \({B_{i}^{0}}\) is assumed to be known.

With finite battery capacity, the energy consumption rate of each sourceFootnote 3 is constrained by

$$ 0 \le {B_{i}^{h}} = B_{i}^{h-1} + {\pi_{i}^{h}} {\Delta} - {\psi_{i}^{h}} {\Delta} - {\delta_{i}^{h}} \le B_{i}^{\max}, $$
(6)

which indicates that the energy consumption rate should be neither too large such that the source depletes the battery and stops working (aggressive case), nor too small such that the battery level reaches maximum and misses recharging opportunities (conservative case).

By substituting (5) for \({B_{i}^{h}}\), Eq. 6 can be rewritten as

$$0 \le {B_{i}^{h}} = {B_{i}^{0}} + \sum\limits_{t=1}^{h} {{\pi_{i}^{t}} {\Delta}} - \sum\limits_{t=1}^{h} {\left( {\psi_{i}^{t}} {\Delta} + {\delta_{i}^{t}} \right)} \le B_{i}^{\max}. $$

For simplicity, we define a variable

$$ {D_{i}^{h}} \triangleq \sum\limits_{t=1}^{h} {\left( {\psi_{i}^{t}} {\Delta} + {\delta_{i}^{t}} \right)} $$
(7)

as the source i’s accumulated energy demand from beginning to time slot h, and two constants

$$\left\{ \begin{array}{l} {L_{i}^{h}} \triangleq {U_{i}^{h}} - B_{i}^{\max} \\ {U_{i}^{h}} \triangleq {B_{i}^{0}} + \sum\limits_{t=1}^{h} {{\pi_{i}^{t}} {\Delta}} \end{array} \right. $$

to be the lower and upper bounds of the energy constraint. Thus, the energy constraint of each source is

$$ {L_{i}^{h}} \le {D_{i}^{h}} \le {U_{i}^{h}}, $$
(8)

where the energy consumption rate of each source is coupled across the time horizon. This is the spatiotemporally-coupled constraint which couples one source’s flow rate with those of others across the time horizon.

3.4 Problem formulation

The source i attains utility \(W \left ({r_{i}^{h}} \right )\) when it samples data at rate \({r_{i}^{h}}\) at time slot h, where the utility can be a specific performance (e.g., data gathering) required by applications. The utility function W(⋅) is assumed to be continuously differentiable, increasing, and strictly concave [16]. For example, let \(W \left ({r_{i}^{h}} \right ) \triangleq \log \left ({r_{i}^{h}} \right )\), which is known to guarantee the fairness of each source. The NUM problem in dynamic-routing RSNs is to maximize the network utility \(\sum \nolimits _{h \in \mathcal {H}} { \sum \nolimits _{i \in \mathcal {N}} {W \left ({r_{i}^{h}} \right )} }\) over the sampling rate matrix \(\boldsymbol {R} \triangleq \left [ {r_{i}^{h}} \right ]_{i \in \mathcal {N}, h \in \mathcal {H}}\), flow rate matrix \(\boldsymbol {F} \triangleq \left [f_{ij}^{h}\right ]_{i \in \mathcal {N}, j \in \mathcal {N} \cup \{s\}, h \in \mathcal {H}}\), and missed energy matrix \(\boldsymbol {\Delta } \triangleq \left [ {\delta _{i}^{h}} \right ]_{i \in \mathcal {N}, h \in \mathcal {H}}\), under the flow constraints (1) and (2), and energy constraint (8):

Primal Problem:

$$\begin{array}{@{}rcl@{}} \underset{\boldsymbol{R},\boldsymbol{F},\boldsymbol{\Delta}}{\max} && \sum\limits_{h \in \mathcal{H}} { \sum\limits_{i \in \mathcal{N}} {W \left( {r_{i}^{h}} \right)} } \\ \text{s.t.} && \left\{ \begin{array}{l} (1),~(2),~\text{and}~(8) \\ {r_{i}^{h}},f_{ij}^{h},{\delta_{i}^{h}} \ge 0 \end{array} \quad \forall i \in \mathcal{N},\forall h \in \mathcal{H}. \right. \end{array} $$
(9)

4 Dual decomposition

With the coupled flow and energy constraints, especially the spatiotemporally-coupled constraint(8) which couples one source’s flow rate with those of others across the time horizon, the primal problem (9) is very challenging. However, by means of dual decomposition [33–35], we can decouple the original problem equivalently into separable subproblems and then solve them locally. Due to strong duality, the primal problem and its dual problem are equivalent.

4.1 Lagrangian

Define the Lagrangian

$$\begin{array}{@{}rcl@{}} && \mathcal{L} \left( \boldsymbol{R},\boldsymbol{F},\boldsymbol{\Delta};\boldsymbol{\Lambda},\boldsymbol{M} \right) = \sum\limits_{h \in \mathcal{H}} { \sum\limits_{i \in \mathcal{N}} {W \left( {r_{i}^{h}} \right)} } \\ && + \sum\limits_{h \in \mathcal{H}} { \sum\limits_{i \in \mathcal{N}} { \Big[ {\lambda_{i}^{h}} \left( {D_{i}^{h}} - {L_{i}^{h}} \right) + {\mu_{i}^{h}} \left( {U_{i}^{h}} - {D_{i}^{h}} \right) \Big] } }, \end{array} $$

where we relax the energy constraint (8) by introducing the Lagrangian multipliers \({\lambda _{i}^{h}},{\mu _{i}^{h}} \ge 0\) (interpreted as the energy multipliers) for each source at each time slot, and \(\boldsymbol {\Lambda } \triangleq \left [ {\lambda _{i}^{h}} \right ]_{i \in \mathcal {N}, h \in \mathcal {H}}\), \(\boldsymbol {M} \triangleq \left [ {\mu _{i}^{h}} \right ]_{i \in \mathcal {N}, h \in \mathcal {H}}\) are the energy multiplier matrixes.

Note that if we set \({\lambda _{s}^{h}}={\mu _{s}^{h}}=0\) (no energy constraint on the sink), and define a variable

$$ {\epsilon_{i}^{h}} \triangleq \sum\limits_{t=h}^{H} { \left( {\lambda_{i}^{t}} - {\mu_{i}^{t}} \right) } $$
(10)

as the comprehensive energy multiplier for each source (obviously \({\epsilon _{s}^{h}} = 0\)) at each time slot, then we have

$$\left\{ \begin{array}{l} \sum\limits_{h \in \mathcal{H}} {\Big[ \left( {\lambda_{i}^{h}} - {\mu_{i}^{h}} \right) {D_{i}^{h}} \Big]} = \sum\limits_{h \in \mathcal{H}} {\left( {\psi_{i}^{h}} {\Delta} + {\delta_{i}^{h}} \right) {\epsilon_{i}^{h}}} \\ \sum\limits_{i \in \mathcal{N}} {{\psi_{i}^{h}} {\epsilon_{i}^{h}} {\Delta}} = \sum\limits_{i \in \mathcal{N}} { \left[ {r_{i}^{h}} {e_{i}^{s}} {\epsilon_{i}^{h}} {\Delta} + \sum\limits_{j \in \mathcal{N} \cup \{s\}} {f_{ij}^{h} \left( e_{ij}^{t} {\epsilon_{i}^{h}} \!+ {e_{j}^{r}} {\epsilon_{j}^{h}} \right) {\Delta}} \right] }. \end{array} \right. $$

The above equations can be proved through the expansion of both sides and mathematical induction.

Thus, the Lagrangian is rewritten as

$$\begin{array}{@{}rcl@{}} && \mathcal{L} \left( \boldsymbol{R},\boldsymbol{F},\boldsymbol{\Delta};\boldsymbol{\Lambda},\boldsymbol{M} \right) = \sum\limits_{h \in \mathcal{H}} { \sum\limits_{i \in \mathcal{N}} { \left( -{\lambda_{i}^{h}} {L_{i}^{h}} + {\mu_{i}^{h}} {U_{i}^{h}} \right) } } \\ && + \sum\limits_{h \in \mathcal{H}} { \sum\limits_{i \in \mathcal{N}} {\left[ \!W \left( {r_{i}^{h}} \right) + p_{i}^{e,h} {r_{i}^{h}} \,+\,\!\! \sum\limits_{j \in \mathcal{N} \cup \{s\}} {\omega_{ij}^{e,h} f_{ij}^{h}} + {\epsilon_{i}^{h}} {\delta_{i}^{h}} \right]} }, \end{array} $$

where

figure f

denote the energy price for each source i, the energy weight for each link (i,j), respectively.

4.2 Subproblem and dual problem

The dual function is the maximum value of the Lagrangian over the system variables R, F, and Δ:

$$\mathcal{D} \left( \boldsymbol{\Lambda},\boldsymbol{M} \right) = \underset{\boldsymbol{R},\boldsymbol{F},\boldsymbol{\Delta}}{\sup} \mathcal{L} \left( \boldsymbol{R},\boldsymbol{F},\boldsymbol{\Delta};\boldsymbol{\Lambda},\boldsymbol{M} \right). $$

Define Subproblem:

$$ \begin{array}{lllllll} & F^{h} \left( \boldsymbol{\Lambda},\boldsymbol{M} \right) \triangleq \\ & \underset{{r_{i}^{h}},f_{ij}^{h}}{\max} \sum\limits_{i \in \mathcal{N}} { \left[ W \left( {r_{i}^{h}} \right) + p_{i}^{e,h} {r_{i}^{h}} + \sum\limits_{j \in \mathcal{N} \cup \{s\}} {\omega_{ij}^{e,h} f_{ij}^{h}} \right] } \\ & \text{s.t.} \left\{ \begin{array}{l} (1)~\text{and}~(2) \\ {r_{i}^{h}},f_{ij}^{h} \ge 0 \end{array} \quad \forall i \in \mathcal{N} \right. \end{array} $$
(12)

as the h th Lagrangian to be maximized at time slot h, and

Subproblem:

$$ {G_{i}^{h}} \left( \boldsymbol{\Lambda},\boldsymbol{M} \right) \triangleq \underset{{\delta_{i}^{h}} \ge 0}{\max} \left( {\epsilon_{i}^{h}} {\delta_{i}^{h}} \right) $$
(13)

as the (i,h)th Lagrangian to be maximized by source i at time slot h. Thus, the dual function is rewritten as

$$\begin{array}{@{}rcl@{}} \mathcal{D} \left( \boldsymbol{\Lambda},\boldsymbol{M} \right) & =& \sum\limits_{h \in \mathcal{H}} { \sum\limits_{i \in \mathcal{N}} { \left( -{\lambda_{i}^{h}} {L_{i}^{h}} + {\mu_{i}^{h}} {U_{i}^{h}} \right) } } \\ && + \sum\limits_{h \in \mathcal{H}} {F^{h} \left( \boldsymbol{\Lambda},\boldsymbol{M} \right)} + \sum\limits_{h \in \mathcal{H}} { \sum\limits_{i \in \mathcal{N}} {{G_{i}^{h}} \left( \boldsymbol{\Lambda},\boldsymbol{M} \right)} }. \end{array} $$

The dual problem is to minimize the dual function over the energy multipliers Λ and M:

Dual Problem:

$$\begin{array}{@{}rcl@{}} \underset{\boldsymbol{\Lambda},\boldsymbol{M}}{\min} && \mathcal{D} \left( \boldsymbol{\Lambda},\boldsymbol{M} \right) \\ \text{s.t.} && {\lambda_{i}^{h}},{\mu_{i}^{h}} \ge 0 \quad \forall i \in \mathcal{N},\forall h \in \mathcal{H}. \end{array} $$
(14)

The dual problem (14) can be iteratively solved using the subgradient projection method, and the energy multipliers are updated in an opposite direction to the subgradient of the dual function:

$$\left\{ \begin{array}{l} \lambda_{i}^{h,k+1} = \left[ \lambda_{i}^{h,k} - \gamma_{\lambda} \frac{\partial \mathcal{D}\left( \boldsymbol{\Lambda}^{k},\boldsymbol{M}^{k} \right)}{\partial \lambda_{i}^{h,k}} \right]^{+} \\ \mu_{i}^{h,k+1} = \left[ \mu_{i}^{h,k} - \gamma_{\mu} \frac{\partial \mathcal{D}\left( \boldsymbol{\Lambda}^{k},\boldsymbol{M}^{k} \right)}{\partial \mu_{i}^{h,k}} \right]^{+}, \end{array} \right. $$

where γ λ ,γ μ >0 are the step sizes which adjust the convergence rate, and \(k \in \mathbb {N}^{+}\) denotes the index of iterations.

Theorem 1

The primal problem ( 9 ) has strong duality.

Proof

First, the primal problem (9) is the maximization over a concave function, which is equivalent to the minimization over a convex function. Then, the inequality constraint functions (1), (2), and (8) are affine. It is proved in [33](@var1@Sec. 5.3.2@var1@) that strong duality holds since (9) satisfies the constraint qualification. □

With strong duality, the optimal duality gap is zero. Therefore, to solve the primal problem (9) is equivalent to solving its dual problem (14).

5 Solution

By means of dual decomposition, the global optimization problem (9) has been equivalently decoupled into separable local optimization subproblems. The dual function is composed of two subproblems: (12) is joint rate control and routing; and (13) is energy management — to determine the missed energy due to finite battery capacity. We solve these subproblems in the context of joint rate control, routing, and energy management.

5.1 Joint rate control and routing

Since the primal problem (9) of maximizing the network utility across the time horizon has reduced to the subproblem (12) of maximizing that separately at each time slot, we drop the superscript h from the notation for simplicity:

Primal Problem 2:

$$\begin{array}{@{}rcl@{}} \underset{\boldsymbol{r},\boldsymbol{f}}{\max} && \sum\limits_{i \in \mathcal{N}} { \left[ W \left( r_{i} \right) + {p_{i}^{e}} r_{i} + \sum\limits_{j \in \mathcal{N} \cup \{s\}} {\omega_{ij}^{e} f_{ij}} \right] } \\ \text{s.t.} && \left\{ \begin{array}{l} \sum\limits_{j \in \mathcal{N}} {f_{ji}} + r_{i} \le \sum\limits_{j \in \mathcal{N} \cup \{s\}} {f_{ij}} \\ f_{ij} \le c_{ij} \quad \forall j \in \mathcal{N} \cup \{s\} \\ r_{i},f_{ij} \ge 0 \end{array} \quad \forall i \in \mathcal{N}, \right. \end{array} $$
(15)

where \(\boldsymbol {r} = \left [ r_{i} \right ]_{i \in \mathcal {N}}\) is the sampling rate vector, and \(\boldsymbol {f} = \left [f_{ij}\right ]_{i \in \mathcal {N}, j \in \mathcal {N} \cup \{s\}}\) is the flow rate matrix. Similarly, since the problem has the spatially-coupled constraint which couples one link’s flow rate with those of others, it is very challenging. However, by means of dual decomposition, we can decouple it equivalently into separable subproblems and then solve them locally. Due to strong duality, the primal problem and its dual problem are equivalent.

Define the Lagrangian

$$\begin{array}{@{}rcl@{}} \mathcal{L} \left( \boldsymbol{r},\boldsymbol{f};\boldsymbol{\nu} \right) & =& \sum\limits_{i \in \mathcal{N}} { \left[ W \left( r_{i} \right) + {p_{i}^{e}} r_{i} + \sum\limits_{j \in \mathcal{N} \cup \{s\}} {\omega_{ij}^{e} f_{ij}} \right] } \\ && + \sum\limits_{i \in \mathcal{N}} {\nu_{i} \left( \sum\limits_{j \in \mathcal{N} \cup \{s\}} {f_{ij}} - \sum\limits_{j \in \mathcal{N}} {f_{ji}} - r_{i} \right)}, \end{array} $$

where we relax the flow constraint by introducing the Lagrangian multiplier ν i ≥0 (interpreted as the flow multiplier) for each source, and \(\boldsymbol {\nu } = \left [ \nu _{i} \right ]_{i \in \mathcal {N}}\) is the flow multiplier vector. Note that if we set ν s =0 (no flow constraint on the sink), then we have

$$\sum\limits_{i \in \mathcal{N}} {\nu_{i}\! \left( \sum\limits_{j \in \mathcal{N} \cup \{s\}} \!\!{f_{ij}} - \sum\limits_{j \in \mathcal{N}} {f_{ji}} \right)} \,=\, \sum\limits_{i \in \mathcal{N}} { \sum\limits_{j \in \mathcal{N} \cup \{s\}} \!\!{f_{ij} \left( \nu_{i} - \nu_{j} \right)} }. $$

Thus, the Lagrangian is rewritten as

$$\mathcal{L} \left( \boldsymbol{r},\boldsymbol{f};\boldsymbol{\nu} \right) = \sum\limits_{i \in \mathcal{N}} { \left[ W \left( r_{i} \right) + p_{i} r_{i} + \sum\limits_{j \in \mathcal{N} \cup \{s\}} {\omega_{ij} f_{ij}} \right] }, $$

where

figure g

denote the comprehensive price for each source i, the comprehensive weight for each link (i,j), respectively.

The dual function is the maximum value of the Lagrangian over the system variables r and f:

$$\mathcal{D} \left( \boldsymbol{\nu} \right) = \underset{\boldsymbol{r},\boldsymbol{f}}{\sup} \mathcal{L} \left( \boldsymbol{r},\boldsymbol{f};\boldsymbol{\nu} \right). $$

Define

Subproblem 2:

figure h

as the i th Lagrangian to be maximized by source i. Thus, the dual function is rewritten as

$$\mathcal{D} (\boldsymbol{\nu} ) = \sum\limits_{i \in \mathcal{N}} { \Big[ X_{i} (\nu_{i} ) + Y_{i} (\boldsymbol{\nu} ) \Big] }. $$

The dual problem is to minimize the dual function over the flow multiplier ν: Dual Problem 2:

$$\begin{array}{@{}rcl@{}} \underset{\boldsymbol{\nu}}{\min} && \mathcal{D} (\boldsymbol{\nu} )\\ \text{s.t.} && \nu_{i} \ge 0 \quad \forall i \in \mathcal{N}. \end{array} $$
(18)

The dual problem (18) can be iteratively solved using the gradient projection method, and the flow multiplier is updated in an opposite direction to the gradient of the dual function:

$$\nu_{i}^{m+1} = \left[ {\nu_{i}^{m}} - \gamma_{\nu} \frac{d \mathcal{D}\left( \boldsymbol{\nu}^{m} \right)}{d {\nu_{i}^{m}}} \right]^{+}, $$

where γ ν >0 is the step size which adjusts the convergence rate, and \(m \in \mathbb {N}^{+}\) denotes the index of iterations.

Theorem 2

The primal problem ( 15 ) has strong duality.

Proof

The proof is similar to that of Theorem 1. □

With strong duality, the optimal duality gap is zero. Therefore, to solve the primal problem (15) is equivalent to solving its dual problem (18).

By means of dual decomposition, the global optimization problem (15) has been equivalently decoupled into N separable local optimization subproblems (17a) and (17b) at each source. The dual function is composed of two subproblems: (17a) is rate control — to determine the sampling rate; and (17b) is routing — to determine the outgoing flow rate. We solve these subproblems in the context of joint rate control and routing.

  1. 1.

    Rate control: for the subproblem (17a) at each source, given \({\nu _{i}^{m}}\), the sampling rate

    $$ \tilde r_{i} = \left[ \left( W^{\prime} \right)^{-1} \left( -{p_{i}^{m}} \right) \right]^{+} $$
    (19)

    is unique due to the strict concavity of W(⋅). Besides, the function (W ′)−1(⋅) is monotonely decreasing. Under arbitrary \({\nu _{i}^{m}}\), the local maximizer \(\tilde r_{i}\) may not be globally optimal. However, by duality theory, there exists dual optimal \(\hat \nu _{i}\) such that \(\hat r_{i}\) will be globally optimal.

  2. 2.

    Routing: for the subproblem (17b) at each source, given ν m, the outgoing flow rate can be iteratively solved using the gradient projection method:

    $$ \tilde f_{ij} = \left[ \tilde f_{ij} + \theta_{f} \omega_{ij}^{m} \right]_{0}^{c_{ij}} \quad \forall j \in \mathcal{N} \cup \{s\}, $$
    (20)

    where 𝜃 f >0 is step size which adjusts the convergence rate.

From the above, given dual optimal \(\hat {\boldsymbol \nu }\) from the dual problem (18), each source can solve the subproblems (17a) and (17b) distributively without the need to coordinate with other sources. In other words, the flow multipliers \(\hat {\boldsymbol \nu }\) serve as coordination signals which align the local optimality of Eq. 17a and 17b with the global optimality of Eq. 15.

Recall that the subproblems (17a) and (17b) have the local optimal solutions \(\tilde {r}_{i}\) and \(\left [ \tilde {f}_{ij} \right ]_{j \in \mathcal {N} \cup \{s\}}\), respectively. Thus, we have

$$\left\{ \begin{array}{l} X_{i} \left( {\nu_{i}^{m}} \right) = W \left( \tilde r_{i} \right) + {p_{i}^{m}} \tilde r_{i} \\ Y_{i} \left( \boldsymbol{\nu}^{m} \right) = \sum\limits_{j \in \mathcal{N} \cup \{s\}} {\omega_{ij}^{m} \tilde f_{ij}}, \end{array} \right. $$

and

$$\frac{d \mathcal{D}\left( \boldsymbol{\nu}^{m} \right)}{d {\nu_{i}^{m}}} = \sum\limits_{j \in \mathcal{N} \cup \{s\}} {\tilde f_{ij}} - \sum\limits_{j \in \mathcal{N}} {\tilde f_{ji}} - \tilde r_{i}. $$

We obtain the following flow multiplier update rule:

$$ \nu_{i}^{m+1} = \left\{ {\nu_{i}^{m}} - \gamma_{\nu} \left[ \sum\limits_{j \in \mathcal{N} \cup \{s\}} {\tilde f_{ij}} - \left( \sum\limits_{j \in \mathcal{N}} {\tilde f_{ji}} + \tilde r_{i} \right) \right] \right\}^{+}, $$
(21)

which indicates that, if the source’s incoming flow rate plus sampling rate \(\left (\sum \nolimits _{j \in \mathcal {N}} {\tilde f_{ji}} + \tilde r_{i} \right )\) exceeds its outgoing flow rate \(\sum \nolimits _{j \in \mathcal {N} \cup \{s\}} {\tilde f_{ij}}\), the flow multiplier ν i will rise, decreasing the comprehensive price p i and weight \(\left [ \omega _{ji} \right ]_{j \in \mathcal {N}}\), and increasing the comprehensive weight \(\left [ \omega _{ij} \right ]_{j \in \mathcal {N} \cup \{s\}}\), which will in turn decrease the sampling rate \(\tilde r_{i}\) and incoming flow rate \(\left [ \tilde f_{ji} \right ]_{j \in \mathcal {N}}\), and increase the outgoing flow rate \(\left [ \tilde f_{ij} \right ]_{j \in \mathcal {N} \cup \{s\}}\), and vice versa.

From the discussion, each source can be treated as processors in the distributed computation system to solve the problem (15). We propose a distributed algorithm (Algorithm 1) in the context of joint rate control and routing (JR 2), which converges to the optimal solution. Given the energy price \(\boldsymbol {p}^{e} \triangleq \left [ {p_{i}^{e}} \right ]_{i \in \mathcal {N}}\) and weight \(\boldsymbol {\omega }^{e} \triangleq \left [ \omega _{ij}^{e} \right ]_{i \in \mathcal {N}, j \in \mathcal {N} \cup \{s\}}\), the JR 2 algorithm will return the optimal sampling rate \(\hat {\boldsymbol r}^{h}\) and flow rate \(\hat {\boldsymbol f}^{h}\) in a distributed manner. The algorithm runs until flow multipliers ν converge within a small range ε, which indicates the error tolerance (stopping criterion).

figure i

5.2 Joint rate control, routing, and energy management

  1. 1.

    Joint rate control and routing: for the subproblem (12) at each time slot, given the energy price p e,h and weight ω e,h, the JR 2 algorithm will return the optimal sampling rate \(\hat {\boldsymbol r}^{h}\) and flow rate \(\hat {\boldsymbol f}^{h}\) in a distributed manner.

  2. 2.

    Energy management: for the subproblem (13) at each source at each time slot, given Λ k, M k, the missed energy can be iteratively solved using the gradient projection method:

    $$ \hat {\delta_{i}^{h}} = \left[ \hat {\delta_{i}^{h}} + \theta_{\delta} \epsilon_{i}^{h,k} \right]^{+}, $$
    (22)

    where 𝜃 δ >0 is the step size which adjusts the convergence rate.

From the above, given dual optimal Λ ∗ and M ∗ from the dual problem (14), each source can solve the subproblems (12) and (13)distributively without the need to coordinate with other sources or time slots. In other words, the energy multipliers Λ ∗ and M ∗ serve as coordination signals which align the local optimality of Eqs. 12 and 13 with the global optimality of Eq. 9.

Recall that the subproblems (12) and (13) have the local optimal solutions \(\hat {\boldsymbol r}^{h}\), \(\hat {\boldsymbol f}^{h}\), and \(\hat {\delta _{i}^{h}}\), respectively. Thus, we have

$$\left\{ \begin{array}{l} F^{h} \left( \boldsymbol{\Lambda}^{k},\boldsymbol{M}^{k} \right) = \sum\limits_{i \in \mathcal{N}} { \left[ W \left( \hat {r_{i}^{h}} \right) + p_{i}^{e,h,k} \hat {r_{i}^{h}} + \sum\limits_{j \in \mathcal{N} \cup \{s\}} {\omega_{ij}^{e,h,k} \hat f_{ij}^{h}} \right] } \\ {G_{i}^{h}} \left( \boldsymbol{\Lambda}^{k},\boldsymbol{M}^{k} \right) = \epsilon_{i}^{h,k} \hat {\delta_{i}^{h}}, \end{array} \right. $$

and

$$\left\{ \begin{array}{l} \frac{\partial \mathcal{D}\left( \boldsymbol{\Lambda}^{k},\boldsymbol{M}^{k} \right)}{\partial \lambda_{i}^{h,k}} = \hat {D_{i}^{h}} - {L_{i}^{h}} \\ \frac{\partial \mathcal{D}\left( \boldsymbol{\Lambda}^{k},\boldsymbol{M}^{k} \right)}{\partial \mu_{i}^{h,k}} = {U_{i}^{h}} - \hat {D_{i}^{h}}. \end{array} \right. $$

We obtain the following energy multiplier update rules:

figure j

which indicates that, if the source’s accumulated energy demand \(\hat {D_{i}^{h}}\) is less than the lower bound \({L_{i}^{h}}\) (conservative case), the energy multiplier \({\lambda _{i}^{h}}\) will rise, increasing the comprehensive energy multiplier \({\epsilon _{i}^{h}}\), and thereby the energy price \(p_{i}^{e,h}\) and weight \(\omega _{ij}^{e,h}\), which will in turn increase the energy consumption rate \(\hat {\psi _{i}^{h}}\) and missed energy \(\hat {\delta _{i}^{h}}\); however, if it exceeds the upper bound \({U_{i}^{h}}\) (aggressive case), \({\mu _{i}^{h}}\) will rise, decreasing \({\epsilon _{i}^{h}}\), and thereby \(p_{i}^{e,h}\) and \(\omega _{ij}^{e,h}\), which will in turn decrease \(\hat {\psi _{i}^{h}}\) and \(\hat {\delta _{i}^{h}}\).

From the discussion, each source can be treated as processors in the distributed computation system to solve the NUM problem in dynamic-routing RSNs with the flow and energy constraints. We propose a distributed algorithm (Algorithm 2) in the context of joint rate control, routing, and energy management (JR 2E), which converges to the globally optimal solution. Given the network topology and configuration, energy consumption rate and energy harvesting profile, and link/battery capacity and initial battery level, the JR 2E algorithm will return the globally optimal sampling rate R ∗, flow rate F ∗, and missed energy Δ ∗ in a distributed manner. Note that the JR 2E algorithm involves two levels of iterations: the upper-level iteration, i.e., Eq. 23a and 23b, adjusts the energy multipliers of each source at each time slot to satisfy the energy constraint; while the lower-level iteration, i.e., Eq. 21 in the JR 2 algorithm, adjusts the flow multiplier of each source to satisfy the flow constraint. The algorithm runs until energy multipliers Λ and M converge within a small range ε, which indicates the error tolerance (stopping criterion). The communication overhead is a few signaling messages to broadcast by each source. The amount of signaling messages is relatively small, compared to that of one day’s sampling data. Besides, since we assume the energy harvesting rate to be predicted and estimated with high accuracy, the algorithm performs only once at the beginning of the time cycle (one day) in an offline manner. Compared to the amount of battery capacity and one day’s energy harvesting, the signaling energy has relatively small impact on the problem investigated.

figure k

6 Numerical results

6.1 Simulation setup

In this section, we provide numerical results to demonstrate the performance of the proposed algorithm. Each source has a 37 ×33 m m 2 solar photovoltaic panel, and a super capacitor as the rechargeable battery, whose capacity is 304 J. Besides, each source has a wireless transceiver module such as Telos [36], and the energy consumption rates for receiving and sampling a unit of data are 0.069 J/k b and 0.0054 J/k b, respectively [16, 28]. The energy consumption rate for transmitting a unit of data over a physical distance d is (0.003+0.0002 ×d 3.14) J/k b [32]. We use the real solar data collected from the Baseline Measurement System at the NREL Solar Radiation Research Laboratory [29]. For example, the data at noon on December 12, 2012 is 512 W/m 2, so the energy harvesting rate at that time is 0.625 J/s, as shown by the energy harvesting profile in Fig. 1b.Footnote 4 Assume that the initial battery level of each source is zero. Let the utility function be \(W \left ({r_{i}^{h}} \right ) \triangleq \log \left ({r_{i}^{h}} \right )\), which is known to guarantee the fairness of each source. The above simulation parameters are summarized in Table 2 for reference. All the following results are obtained by MATLAB R2011a running on a laptop PC with Intel Core i5-3320 CPU @ 2.6 G H z, 4 GB RAM memory, and 32-bit Windows 7 OS.

Table 2 Parameter setting
Full size table

6.2 Joint rate control and routing

We first consider the case of joint rate control and routing. In order to clearly illustrate the simulation result, we consider a simple dynamic-routing RSN comprised of two source nodes and one sink node, with the network topology and physical distances shown in Fig. 1a. The link capacity is set as 0.5 kbps in order to evaluate the impact of link capacity on the simulation result. The reason is that, since the network scale is small, if the link capacity is set too large, then the flow constraint will be slack. At one time slot, given the energy price and weight of all sources p e=[−1,−1] and ω e=[−3,−1;−1,−1], the JR 2 algorithm returns the optimal sampling rate and flow rate of all sources. The iterative process is shown in Fig. 2a. Initially each source begins with an arbitrary flow multiplier. Through iteration, it is observed that the sampling rate of each source and the flow rate of each link converges to the optimum. The solution obtained by the JR 2 algorithm is shown in Fig. 2b, which satisfies the flow constraint and yields the maximum network utility.

Fig. 2
figure 2

Joint rate control and routing

Full size image

6.3 Joint rate control, routing, and energy management

We then consider the case of joint rate control, routing, and energy management. Given the network topology and configuration [shown in Fig. 1a], and energy harvesting profile [shown in Fig. 1b], the JR 2E algorithm returns the globally optimal sampling rate, flow rate, and missed energy of all sources at all time slots. The simulation results are shown in Fig. 3. It is observed that the sampling rates are allocated evenly among sources and time horizon. The reason is that, for the logarithmic utility function, the flatter the curves of source rate, the higher the network utility. Across the time horizon, no source depletes the battery and stops working. The solution obtained by the JR 2E algorithm satisfies both the flow and energy constraints, and yields the maximum network utility.

Table 3 Comparison between JR 2E and YALMIP solutions
Full size table

6.4 Optimality and scalability

Fig. 3
figure 3

Joint rate control, routing, and energy management

Full size image

In this paper, we propose the JR 2E algorithm to solve the problem (9) in a distributed manner. As a nonlinear problem (NLP), it could be centrally solved through an NLP solver. On one hand, to demonstrate the global optimality of the distributed algorithm, we compare the solution of JR 2E with that of a centralized solver YALMIP [37]. On the other hand, to investigate the scalability issue of the JR 2E algorithm, we extend the above simulation to densely-deployed and large-scale RSNs with more sources. We consider dynamic-routing RSNs with the number of sources equal to 2 l, which increases exponentially with l. To be more practical, we set the link capacity as 10 kbps based on some real WSN platforms [38]. In Table 3 we list sample solutions for comparison. It is observed that the JR 2E and YALMIP solutions are almost the same, where the very small differences result from the error tolerance ε (here we choose 10−4). Since JR 2E can achieve almost the same results as a centralized solver, its global optimality is guaranteed. This is where our propose algorithm outperforms existing distributed approaches. On the other hand, we can see that YALMIP returns NaN (not a number) when the source number is larger than 26, while JR 2E reports out of memory when the source number is larger than 211. This is because the centralized approach requires the control center with large memory space and powerful computing capability, while the distributed approach distributes the memory space and computing capability to each source, at the cost of increased communication overhead.

7 Conclusion and future work

In this paper, the NUM problem in dynamic-routing RSNs with the flow and energy constraints has been fully investigated. The challenge lies in that the flow constraint is spatially coupled and the energy constraint is spatiotemporally coupled. We attempt to jointly optimize rate control, routing, and energy management by carefully tackling the flow and energy constraints. By means of dual decomposition, we decouple the original problem equivalently into separable subproblems, which can be locally solved. Based on this, we propose a distributed algorithm to obtain the globally optimal solution. Numerical results based on real solar data are presented to validate our theoretical analysis.

Based on our work in dynamic-routing RSNs, selecting only one path per source is harder since it is not allowed to split traffic. It will be formulated as a mixed-integer linear programming (MILP) problem and will be considered as our future work. On the other hand, since the energy harvesting rate can be considered as a random variable, how its stochasticity will affect the network utility needs to be further investigated. Besides, if the energy harvesting rate cannot be accurately predicted, especially over long interval, then the proposed algorithm should be performed at each time slot. In this online manner, the signaling messages and energy may not be ignored, and their impact on the problem investigated is worth exploring.