Online Energy Harvesting Problem Over An Arbitrary Directed Acyclic Graph Network

Rahul Vaze, Sibi Raj B. Pillai

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+\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.

Introduction

In the burgeoning field of "green" communications, energy harvesting (EH) is a transformative technology. By powering networks with renewable sources like solar or wind, we can create sustainable, long-lasting communication infrastructures. However, these energy sources are inherently unpredictable. Coordinating a complex network to transmit data efficiently when energy arrival times and amounts are unknown is a significant challenge.

Recent research by Rahul Vaze and Sibi Raj B Pillai addresses this by providing a near-optimal solution for minimizing transmission delay across arbitrary network topologies. Their work moves beyond simple point-to-point links to consider complex Directed Acyclic Graphs (DAGs), offering a robust framework for real-world network management.

Problem Formulation

Most existing literature on energy-harvesting communications focuses on isolated links or basic relay setups. This paper tackles the more general case of a network represented as a DAG, where a source node $s$ must deliver a fixed volume of data $B_0$ to a destination node $d$.

A communication network modeled as a Directed Acyclic Graph (DAG).

The problem is complicated by two primary factors:

  1. Uncertainty (Online Setting): Nodes only have causal information about energy arrivals. They cannot predict future "jolts" of power, making it impossible to pre-calculate a perfect transmission schedule.
  2. Interdependence: The optimal power allocation at any given node depends on the rates achieved by all other nodes in the network. Because the relationship between power $P$ and data rate $r$ is non-linear—governed by the Shannon capacity formula $r = \log(1+P)$—the flow of data does not follow standard linear max-flow principles.

Methods

The authors' solution involves a two-pronged approach: a high-level scheduling strategy and a low-level flow optimization algorithm.

The Lazy Online Algorithm

Rather than transmitting data immediately upon energy arrival, the proposed "Lazy" algorithm adopts a wait-and-see strategy. It estimates the time $t_0$ that an omniscient offline algorithm (with full knowledge of the future) would take to complete the transmission. The algorithm then waits until it has harvested sufficient energy to support a constant-rate transmission that completes in approximately $2t_0$. This approach ensures that the network doesn't exhaust its energy prematurely on sub-optimal transmission rates.

A Novel Max-Flow Formulation

To implement the lazy strategy, the authors formulated a new type of Max-Flow problem. In classical networks, each edge has a fixed capacity. In this EH model, a node has a total power budget that it must split among its outgoing edges.

The non-linear rate region for a node splitting power between two outgoing edges.

As shown in the figure above, splitting power $P$ into $\alpha P$ and $(1-\alpha)P$ results in a non-polymatroidal rate region. This non-linearity means that standard max-flow/min-cut theorems are inapplicable. To solve this, the authors developed FlowMax, an iterative algorithm designed to find the maximum flow under these specific power-to-rate constraints.

Key Insights and Results

  • Optimality of the Competitive Ratio: The paper proves that the competitive ratio of 2 is a fundamental limit for this problem. Even in simple networks, an online algorithm cannot perform better than twice as slow as an offline one. The proposed LAZYONLINE algorithm achieves a ratio of $2 + \delta$, making it theoretically optimal.
  • The Min-Cut/Max-Flow Gap: A surprising theoretical finding is that in this power-constrained environment, the "min-cut" of the network does not necessarily equal the "max-flow." This departure from classical network theory highlights the unique challenges of non-linear rate constraints.
  • Computational Efficiency: Numerical simulations demonstrate that the FlowMax algorithm converges to the global optimum very rapidly, often in fewer than five iterations for layered networks. This efficiency makes it suitable for real-time applications in dynamic EH environments.

Conclusion and Future Work

This research provides a rigorous foundation for managing data flow in energy-harvesting DAGs. While the current model assumes orthogonal (non-interfering) edges and full-duplex nodes, it sets the stage for more complex scenarios. Future work may explore the impact of finite battery capacities (energy overflow), half-duplex constraints, and interference-limited environments where links share the same frequency or time slots.

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 {\it lazy} online algorithm with a competitive ratio of $2+\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},
}
Figure