TL;DR
This paper tackles the challenge of maximizing data throughput in battery-powered wireless devices, where packets have individual deadlines and values, and only fully transmitted packets contribute. They introduce a novel "weighted throughput" metric and develop both an optimal offline algorithm (DLDP) and an efficient online heuristic (HST) to maximize this metric under energy and integrity constraints, even in fading wireless channels.
What Problem Does This Paper Address?
The Internet of Things (IoT) is rapidly expanding, with numerous wireless devices providing essential services. A fundamental limitation for many of these devices is their reliance on batteries, creating a critical trade-off between energy consumption and data transmission throughput. Existing research often focuses on maximizing the total number of transmitted bits, assuming sufficient energy and that partial transmissions contribute. However, in many real-world IoT applications (e.g., industrial sensors, smart city monitoring), data packets have specific deadlines and varying values, and crucially, only completely transmitted packets are useful. A partially transmitted packet might be entirely worthless, leading to wasted energy and no contribution to the overall objective. This paper addresses this gap by introducing the concept of "weighted throughput," which accounts for the value of integrally transmitted packets within their deadlines, and developing algorithms to maximize this metric under energy constraints, even in the presence of challenging fading wireless channels.
Methods
The paper proposes a two-pronged approach: an optimal offline algorithm and an online heuristic.
- Optimal Offline Algorithm (DLDP): This algorithm is designed to find the absolute best solution when all information (packet details, channel conditions) is known beforehand. It tackles the NP-hard problem by reformulating it to find the minimum energy required to achieve a certain total value. DLDP employs a two-layer dynamic programming approach:
- Layer 1 (Rate Policy): Determines the optimal power/rate allocation over time, considering the energy constraint. It leverages the concept of "water level" (related to power and channel fading) and uses a recursive approach to find the optimal water level distribution.
-
Layer 2 (Packet Selection): Determines which subset of packets to transmit to maximize the total value, considering their deadlines and the rate policy determined by Layer 1. This layer uses another dynamic programming approach to find the optimal packet selection. The algorithm combines these layers to compute the minimum energy for a given value, and then searches for the maximum achievable value within the given energy budget.
-
Online Heuristic Algorithm (HST): This algorithm is designed for scenarios where decisions must be made dynamically without complete future knowledge. HST uses the optimal DLDP algorithm as a building block. It operates in rounds, where in each round, it identifies "alive" packets (those that have arrived but not yet completed transmission) and uses DLDP to compute a local optimal solution for these packets within a limited energy budget. A "hesitation" parameter (
u) is introduced to allow the algorithm to gather more information before making a decision, balancing the need for timely transmission with the benefit of more informed choices. The algorithm iteratively allocates energy and updates the set of active packets.
Datasets
Not discussed in the paper. The paper focuses on theoretical algorithm design and simulation-based evaluation.
Key Insights and Ideas
- Weighted Throughput is Crucial: The paper highlights that simply maximizing transmitted bits is insufficient for many IoT applications. The concept of "weighted throughput" (sum of values of integrally transmitted packets) is a more relevant and practical metric.
- Integrity Constraint is Key: The requirement that packets must be fully transmitted to contribute value significantly complicates the problem, making it NP-hard and distinct from prior throughput maximization problems.
- Water Level as a Unifying Concept: The "water level" concept, derived from energy minimization problems, proves useful in determining optimal rate and power allocations, even in this more complex scenario with deadlines and packet selection.
- Two-Layer DP for Offline Optimality: The DLDP algorithm's success lies in its decomposition of the problem into two interconnected dynamic programming layers, addressing rate policy and packet selection separately but iteratively.
- Online Heuristic Leverages Offline Optimality: The HST algorithm effectively adapts the optimal offline solution for online decision-making, demonstrating that a locally optimal choice can lead to good overall performance in dynamic environments.
- "Hesitation" for Better Online Decisions: The introduction of the
uparameter in HST allows for a strategic delay in decision-making, enabling the algorithm to gather more information and make more informed choices, leading to better performance.
Key Results
- Offline Optimality: The paper presents the DLDP algorithm, which computes the optimal weighted throughput in pseudo-polynomial time, proving its optimality for the offline MTEF problem.
- Online Performance: Simulations show that the proposed online heuristic algorithm (HST) significantly outperforms baseline algorithms (Greedy, GreedyDrop, Truncation) in terms of achieved weighted throughput across various scenarios, including FIFO and non-FIFO tasks, varying energy budgets, fading factors, and packet values.
- Robustness: HST demonstrates robustness across different parameter settings, consistently outperforming other algorithms and validating its effectiveness in maximizing weighted throughput.
Limitations and Future Work
- Computational Complexity: The optimal offline algorithm DLDP has a pseudo-polynomial time complexity (O(n⁴LV²M)), which can be prohibitive for very large problem instances.
- Energy Dynamics: The paper suggests investigating the effect of energy dynamics, such as energy harvesting and wireless charging, on the weighted throughput.
- Multiple Access Scenario: The authors propose exploring variants of the problem, including the multiple access scenario, where multiple devices compete for the wireless channel.
Summary updated