An Energy Efficient Stable Election-Based Routing Algorithm for Wireless Sensor Networks

Jin Wang, Zhongqi Zhang, Feng Xia, Weiwei Yuan, Sungyoung Lee

TL;DR

This paper proposes a novel energy-efficient routing algorithm (MSE) for wireless sensor networks (WSNs) that utilizes a mobile sink and a modified Stable Election Protocol (SEP). By intelligently selecting cluster heads based on residual energy and employing a mobile sink to balance data collection load, MSE significantly extends network lifetime and improves data delivery compared to traditional static sink approaches like LEACH and SEP.

What Problem Does This Paper Address?

Wireless Sensor Networks (WSNs) are crucial for monitoring diverse environments, but their limited energy supply poses a significant challenge. Traditional WSN routing protocols often suffer from the "hot spot" problem, where nodes near a fixed sink node are overburdened with data relaying, leading to premature energy depletion and network partition. While mobile sinks offer a promising solution to this by distributing the load, existing mobile sink protocols often lack robust energy management or efficient cluster head selection mechanisms, especially in non-uniform network distributions. This paper aims to address these limitations by proposing an energy-efficient routing algorithm that combines the benefits of a mobile sink with an enhanced cluster head election process.

Methods

The proposed algorithm, Mobile sink-based improved algorithm for Stable Election (MSE), builds upon the Stable Election Protocol (SEP) and incorporates a mobile sink. Key methodological aspects include:

  • Modified Stable Election Protocol (SEP): The algorithm considers a heterogeneous network where some nodes have higher initial energy (advanced nodes). Cluster head selection is based on a weighted probability that considers both the residual energy of a node and its initial energy, adjusted by an energy factor for advanced nodes. This ensures a more balanced distribution of cluster head roles.
  • Mobile Sink Trajectory: A mobile sink moves along a predetermined trajectory in the center line of the sensing field, back and forth, to collect data from cluster heads. This dynamic movement helps to alleviate the hot spot problem by rotating the data collection burden.
  • Hierarchical Routing: The network is divided into clusters, with cluster heads responsible for collecting data from normal sensor nodes.
  • Cluster Head Selection: The selection of cluster heads is based on minimizing the associated additional energy and residual energy at each node.
  • Route Set-up and Maintenance: The algorithm includes phases for setting up routes and maintaining them, particularly addressing scenarios where cluster heads might fail or become blocked. In such cases, a normal cluster head can attempt to connect directly to the mobile sink or find an alternative advanced cluster head.
  • Energy Model: The paper uses a first-order radio energy model to quantify energy consumption for transmitting and receiving data, considering factors like distance and amplifier models.

Datasets

Not discussed in the paper. The evaluation is based on simulations.

Key Insights and Ideas

  • Mobile Sink as a Load Balancer: The core insight is that a mobile sink, when strategically employed, can effectively balance the data relaying load across sensor nodes, preventing the rapid depletion of energy in nodes close to a fixed sink.
  • Heterogeneity-Aware Cluster Head Selection: Recognizing that WSNs are often heterogeneous (nodes with different energy capacities), the MSE algorithm's cluster head selection mechanism intelligently leverages this by giving advanced nodes a higher probability of becoming cluster heads, but still balancing this with residual energy considerations.
  • Combined Approach for Longevity: The synergy between a mobile sink and an energy-aware, heterogeneous-aware cluster head selection protocol is crucial for achieving significantly longer network lifetimes.
  • Dynamic Adaptation: The route maintenance phase demonstrates an ability to adapt to node failures, preventing complete network partition and maintaining data flow, albeit with potential reconfigurations.

Key Results

The paper presents simulation results demonstrating the effectiveness of the MSE algorithm:

  • Network Lifetime: MSE significantly outperforms LEACH and SEP in terms of network lifetime. The first node dies at round 525 in MSE, compared to 100 for LEACH and 211 for SEP, representing a 2.5x and 5x improvement over SEP and LEACH, respectively.
  • Energy Consumption: MSE exhibits lower energy consumption compared to LEACH, with a more linear consumption curve.
  • Data Delivery: MSE achieves a higher number of packets received by the sink. It delivers approximately 4 times more packets than LEACH and 2 times more than SEP over its operational lifetime.
  • Influence of Sink Location: The paper shows that sink location influences energy consumption, with nodes further from the sink consuming more energy. The mobile sink mitigates this effect.

Limitations and Future Work

  • Static Trajectory: The current MSE algorithm uses a static, pre-defined trajectory for the mobile sink. The authors acknowledge that in real-world scenarios, blocks or changes in the environment might make this trajectory suboptimal.
  • Synchronization and Location Awareness: The paper's assumptions of fixed, synchronized, and location-aware sensors are difficult to achieve in practice and can consume significant energy.
  • Communication Delay: The communication delay between sensor nodes is not explicitly considered in the current model.

Future work suggested by the authors includes:

  • Multiple Mobile Sinks: Investigating the use of multiple mobile sinks to further enhance performance.
  • Adjustable Trajectories: Developing mechanisms for mobile sinks to dynamically adjust their trajectories based on network conditions or environmental changes.
  • Reduced Assumptions: Designing protocols with fewer assumptions about sensor capabilities (e.g., less reliance on synchronization and precise location awareness).
  • Communication Delay Consideration: Incorporating communication delay into the routing protocol design.

Summary updated

BibTeX
@inproceedings{wang2013energy,
  author = {Jin Wang and Zhongqi Zhang and Feng Xia and Weiwei Yuan and Sungyoung Lee},
  title = {{An Energy Efficient Stable Election-Based Routing Algorithm for Wireless Sensor Networks}},
  booktitle = {Sensors},
  year = {2013},
  url = {https://openreview.net/forum?id=Y0wKq3JYpP},
}
Figure