k-DAG Based Lifetime Aware Data Collection in Wireless Sensor Networks

Jingjing Fei, Hui Wu, Yongxin Wang

Abstract

Wireless Sensor Networks (WSNs) need to be organized for efficient data collection and lifetime maximization. In this paper, we propose a novel routing structure, namely k-DAG, to balance the load of the base station's neighbours while providing the worst-case latency guarantee for data collection, and a distributed algorithm for construction a k-DAG based on a Shortest Path DAG (SPD). In a k-DAG, the lengths of the longest path and the shortest path of each sensor node to the base station differ by at most k. By adding sibling edges to a SPD, our distributed algorithm allows critical nodes to have more routing choices. The simulation results show that our approach significantly outperforms the SPD-based data collection approach in both network lifetime and load balance.

Introduction

In Wireless Sensor Networks (WSNs), the network's "lifetime" is typically limited by the energy depletion of nodes closest to the base station. Because these nodes act as relays for the entire network, they consume battery power much faster than peripheral nodes. While Shortest Path Trees (SPTs) and Shortest Path DAGs (SPDs) provide basic routing, they often fail to optimize for load balancing, leading to premature network failure when critical near-root nodes fail. This research addresses the challenge of distributing the relaying burden across these bottleneck nodes without compromising data delivery latency.

The k-DAG Methodology

The proposed solution is the $k$-DAG, a routing structure where the difference between the longest and shortest paths from any node to the base station is constrained by a user-defined parameter $k$. This structure is built through a four-phase distributed algorithm:

  1. Initial Setup: Construction of a standard SPD and SPT.
  2. Distributed Naming: A unique naming scheme assigns IDs based on depth-first search (DFS) order, facilitating targeted communication from the base station.
  3. Load Calculation: Nodes calculate cumulative data loads (own data plus relayed traffic) in a bottom-up manner.
  4. Adding Sibling Edges: The base station identifies the most and least burdened child nodes and introduces "sibling edges" (links between nodes at the same level) to divert traffic, provided the $k$ latency constraint is maintained.
Figure 1: The distributed naming scheme assigns unique IDs to nodes based on a depth-first search order to facilitate efficient communication.

By incorporating "sideways" sibling edges, the $k$-DAG utilizes paths that traditional shortest-path algorithms ignore. This allows for strategic traffic diversion, particularly effective when implemented near the base station where entire sub-trees of traffic can be rerouted.

Figure 2: Illustration of child-parent data flow and load distribution within the network structure.

Key Results and Insights

The $k$-DAG approach was evaluated using the Cooja simulator across 60 network instances of 50 to 100 nodes. Key findings include:

  • Lifetime Extension: The $k$-DAG improved network lifetime by up to 82% in 50-node scenarios compared to standard SPD routing.
  • Enhanced Load Balancing: Using the Chebyshev Sum Inequality to measure balance, the $k$-DAG consistently outperformed SPD, showing improvements in the "balance factor" by up to 83%.
  • Latency-Lifetime Trade-off: The parameter $k$ serves as a tunable knob, allowing operators to trade increased maximum delay for significantly longer network longevity.
  • Efficiency: Most lifetime gains were captured by adding only the first 10-30% of potential sibling edges, demonstrating the algorithm's high efficiency.

Conclusion

The $k$-DAG structure provides a robust framework for maximizing WSN lifetime through intelligent load balancing and sibling edge utilization. While the current model assumes a static environment and perfect links, future work will explore integrating $k$-DAG with mobile base stations and duty-cycling sleep schedules to further enhance longevity in realistic, noisy environments.

Summary updated

Abstract

Wireless Sensor Networks need to be organized for efficient data collection and lifetime maximization. In this paper, we propose a novel routing structure, namely k-DAG, to balance the load of the base station's neighbours while providing the worst-case latency guarantee for data collection, and a distributed algorithm for construction a k-DAG based on a SPD (Shortest Path DAG). In a k-DAG, the lengths of the longest path and the shortest path of each sensor node to the base station differ by at most k. By adding sibling edges to a SPD, our distributed algorithm allows critical nodes to have more routing choices. The simulation results show that our approach significantly outperforms the SPD-based data collection approach in both network lifetime and load balance.
BibTeX
@article{fei2013k,
  author = {Jingjing Fei and Hui Wu and Yongxin Wang},
  title = {{k-DAG Based Lifetime Aware Data Collection in Wireless Sensor Networks}},
  journal = {International Journal of Wireless \& Mobile Networks},
  year = {2013},
  doi = {10.5121/ijwmn.2013.5502},
}
Figure