Steady and fair rate allocation for rechargeable sensors in perpetual sensor networks

Kai-Wei Fan, Zizhan Zheng, Prasun SinhaSenSys 2008 · DOI

TL;DR

This paper tackles the challenge of fairly and efficiently allocating data collection rates in sensor networks powered by renewable energy. They introduce novel centralized and distributed algorithms that compute optimal, lexicographically maximum rates, ensuring no sensor runs out of power while maximizing overall data throughput.

What Problem Does This Paper Address?

Modern sensor networks are increasingly deployed for long-term environmental monitoring, often in remote or harsh locations. To achieve perpetual operation, these networks rely on renewable energy sources like solar or wind. However, the intermittent and dynamic nature of harvested energy, coupled with the energy costs of sensing and communication, makes it difficult to guarantee continuous data collection from all nodes without battery depletion. Existing approaches often struggle to balance fairness (ensuring all nodes contribute and receive a reasonable rate) with maximizing overall data throughput, especially when considering the time-varying energy availability. This paper aims to bridge this gap by developing algorithms that can compute optimal, fair data rates that adapt to the fluctuating energy supply.

Methods

The core of this work lies in developing algorithms for "lexicographic rate assignment." This means prioritizing the rates of nodes that are "lower" in some defined order (e.g., those with lower initial rates) to maximize their rates first, then moving to the next lowest, and so on, until all rates are maximized without violating constraints.

  • Centralized Algorithm: This approach uses a linear programming (LP) formulation to jointly compute the optimal data collection rate for each node and the flow of data across network links. It requires global knowledge of the network topology, energy harvesting profiles, and energy costs.
  • Distributed Algorithm: Recognizing the limitations of centralized control in sensor networks, the authors propose a distributed, asynchronous algorithm. This algorithm assumes pre-determined routing paths (a "routing tree") and allows nodes to compute their optimal rates iteratively. It leverages a "Maximum Rate" procedure to determine a node's maximum sustainable rate given its energy harvesting capabilities and then uses an "Update Rate" mechanism to refine these rates based on information from neighboring nodes. This distributed approach avoids the need for a central LP solver, making it more practical for resource-constrained sensor nodes.

Datasets

The paper evaluates its algorithms using:

  • Measured Solar Cell Data: Figure 4 shows current measurements from a solar cell over a 48-hour period, illustrating the variability of solar energy.
  • Simulated Recharging Profiles: For experiments, they use the measured solar data as a baseline and generate variations to simulate different recharging scenarios (sunny vs. partly cloudy days).
  • External Solar Data: Figure 9 uses solar profile data collected from six different locations in California, simulating diverse environmental conditions for sensor nodes.
  • Testbed Experiments: A key evaluation was performed on a testbed with 155 TmoteSky sensor motes (MoteLab), simulating various scenarios, including different recharging profiles and network topologies.

Key Insights and Ideas

  • Lexicographic Fairness is Key: The paper argues that simply maximizing the average rate isn't sufficient; a lexicographical approach ensures that nodes that are already struggling get their rates boosted first, leading to a more robust and fair system.
  • Dynamic Rate Adjustment is Crucial: The algorithms are designed to adapt to the fluctuating energy supply, a critical factor for rechargeable sensor networks.
  • Distributed Approach is Feasible: The development of a distributed algorithm demonstrates that achieving optimal lexicographic rate assignment is possible even in resource-constrained, decentralized sensor networks.
  • Routing Tree Impact: The performance of the distributed algorithm is shown to be sensitive to the routing tree structure. More balanced trees lead to better rate assignments, highlighting the interplay between routing and energy management.
  • Granularity Matters: The resolution of the recharging profile data (e.g., hourly vs. minute-by-minute) impacts the ability to prevent nodes from running out of energy, presenting a trade-off between data accuracy and memory/storage constraints.

Key Results

  • Optimality Proofs: The paper provides theoretical proofs for the optimality of both the centralized and distributed algorithms.
  • Testbed Validation: Experiments on a 155-node testbed show that the distributed algorithm (DLEX) closely matches the performance of a centralized LP solver, with differences attributed to precision limitations in sensor node computation.
  • Performance Comparison: DLEX outperforms a naive approach (NAVG) that simply uses the average recharging rate, significantly reducing the percentage of time nodes run out of energy and improving overall throughput.
  • Topology Impact: Higher transmission power (leading to denser networks and potentially more balanced routing trees) results in better lexicographic rate assignments.

Limitations and Future Work

  • Fixed Routing Assumption: The distributed algorithm assumes pre-determined routing paths. Future work aims to develop distributed algorithms that can jointly determine optimal routing and rate assignments.
  • Granularity of Recharging Data: The use of hourly recharging data can lead to occasional energy runouts. Using finer-grained data (e.g., minute-by-minute) improves performance but increases memory requirements. Future work could explore adaptive granularity or mechanisms to reserve buffer energy.
  • Link Quality and Battery Leakage: The current models do not explicitly account for packet loss due to poor link quality or battery leakage. The authors suggest incorporating these factors into the cost functions or control packets.
  • Balanced Tree Construction: Computing a load-balanced tree is NP-hard. Future work includes exploring distributed algorithms for creating balanced trees and investigating multipath routing schemes for better rate assignment.

Summary updated

BibTeX
@inproceedings{fan2008steady,
  author = {Kai-Wei Fan and Zizhan Zheng and Prasun Sinha},
  title = {{Steady and fair rate allocation for rechargeable sensors in perpetual sensor networks}},
  booktitle = {SenSys},
  year = {2008},
  doi = {10.1145/1460412.1460436},
}
Figure