Online Energy Harvesting Problem Over an Arbitrary Directed Acyclic Graph Network

Rahul Vaze, Sibi Raj B. Pillai

In the world of "green" communications, energy harvesting (EH) is a game-changer. Imagine a network of sensors or relays powered entirely by solar or wind. While sustainable, these energy sources are notoriously unpredictable. How do you coordinate a complex network to send data as fast as possible when you don't know when the next "jolt" of power will arrive?

A new paper by Rahul Vaze and Sibi Raj B Pillai, titled "Online Energy Harvesting Problem Over An Arbitrary Directed Acyclic Graph Network," provides a near-optimal solution to this problem for arbitrary network topologies.

TL;DR

The authors present a "lazy" online algorithm for minimizing data transmission delay in networks powered by energy harvesting. They prove their algorithm achieves a competitive ratio of $2 + \delta$ (meaning it's at most twice as slow as an omniscient offline optimizer), which is the theoretical best possible performance for this class of problems.

What Problem Does This Paper Address?

Most existing research on energy-harvesting communications focuses on simple setups: a single transmitter-receiver pair or a basic relay. However, real-world networks are complex webs—mathematically represented as Directed Acyclic Graphs (DAGs).

The challenge is two-fold:

  1. Uncertainty: In an "online" setting, nodes only know about energy after it has been harvested. They cannot see into the future to plan the perfect transmission schedule.
  2. Interdependence: In a network, the optimal power allocation at one node depends on the rates of all other nodes. Because the relationship between power and data rate is logarithmic (the Shannon capacity formula), the "flow" of data doesn't behave like standard water-in-a-pipe max-flow problems.

The authors aim to find a strategy that minimizes the time to deliver a fixed amount of data ($B_0$) from a source to a destination across an arbitrary DAG.

Methods

The researchers break the problem down into two main components:

1. The Lazy Online Algorithm

Instead of trying to transmit data the moment a tiny bit of energy arrives, the "Lazy" approach waits. It estimates the time $t_0$ it would take an optimal offline algorithm (which knows the future) to finish. It then waits until it has collected enough energy to support a constant-rate transmission that finishes in roughly $2t_0$.

2. A Novel Max-Flow Formulation

To make the lazy strategy work, the authors had to solve a new kind of Max-Flow problem. In standard networks, each edge has a fixed capacity. Here, a node has a total power budget it can split among its outgoing edges.

  • Because the rate $r = \log(1+P)$, splitting power $P$ into $\alpha P$ and $(1-\alpha)P$ results in a "non-polymatroidal" rate region.
  • This means standard max-flow/min-cut theorems don't apply. The authors developed a new iterative algorithm called FlowMax to solve this specific optimization problem.

Datasets

As a theoretical paper in information theory and communications, it does not use external real-world datasets. Instead, the authors evaluate their algorithms using:

  • Synthetic DAG Topologies: Specifically, "layered networks" where nodes are organized in ranks.
  • Numerical Simulations: They compare their FlowMax algorithm against standard convex optimization solvers to verify its convergence and accuracy.

Key Insights and Ideas

  • The Power of 2: The competitive ratio of 2 is a fundamental limit. Even in a simple two-node network, an online algorithm can't do better than being twice as slow as an offline one. This paper shows that this limit holds even for massive, complex networks.
  • Min-Cut is Not Max-Flow: One of the most surprising theoretical findings is that in this specific power-constrained setting, the "min-cut" of the network does not necessarily equal the "max-flow." This is a departure from classical network flow theory.
  • Complexity vs. Performance: The algorithm's performance is controlled by a parameter $\delta$. By increasing computational complexity slightly ($O(\log(1/\delta))$), you can get the competitive ratio arbitrarily close to the theoretical floor of 2.

Key Results

  • Optimality: The proposed LAZYONLINE algorithm is proven to be an optimal online algorithm in terms of competitive ratio.
  • Convergence: The FlowMax algorithm is shown to converge to the global optimum for layered networks, effectively handling the non-linear constraints of the Shannon capacity formula.
  • Efficiency: Simulations demonstrate that FlowMax typically converges in very few iterations (e.g., fewer than 5 iterations for the test cases shown), making it practical for real-time network management.

Limitations and Future Work

  • Orthogonal Edges: The current model assumes that links do not interfere with each other (e.g., they use different frequencies or time slots). While the authors provide a brief extension for Multiple Access Channels (MAC), a full treatment of interference-limited networks remains open.
  • Battery Constraints: The paper assumes batteries are large enough that no energy is ever wasted (no overflow). In tiny IoT sensors with small capacitors, energy overflow is a real concern that would require a more complex "energy-aware" flow strategy.
  • Half-Duplexing: The nodes are assumed to be full-duplex (can send and receive at the same time). Extending this to half-duplex nodes—the standard for most current wireless hardware—is noted as a significantly more challenging problem.

Summary updated

Abstract

A communication network modelled by a directed acyclic graph (DAG) is considered, over which a source wishes to send a specified number of bits to a destination node. Each node of the DAG is powered by a separate renewable energy source, and the harvested energy is used to facilitate the source destination data flow. The challenge here is to find the optimal rate and power allocations across time for each node on its outgoing edges so as to minimize the time by which the destination receives a specified number of bits. An online setting is considered where an algorithm only has causal information about the energy arrivals. Using the competitive ratio as the performance metric, i.e., the ratio of the cost of the online algorithm and the optimal offline algorithm, maximized over all inputs, a lazy online algorithm with a competitive ratio of $2{\pmb {+}}\delta $ for any $\delta >0$ is proposed. Incidentally, 2 is also a lower bound to the competitive ratio of any online algorithm for this problem. Our lazy online algorithm is described and analyzed via defining a novel max-flow problem over a DAG, where the rate on the subset of outgoing edges of any node are related/constrained. An optimal algorithm to find max-flow with these constraints is also provided, which may be of independent interest.
BibTeX
@article{vaze2019online,
  author = {Rahul Vaze and Sibi Raj B. Pillai},
  title = {{Online Energy Harvesting Problem Over an Arbitrary Directed Acyclic Graph Network}},
  journal = {IEEE Trans. Green Commun. Netw.},
  year = {2019},
  url = {https://openreview.net/forum?id=UtDfVf0HZ9},
}

Loading related content...

Figure