Maximizing Lifetime of Range-Adjustable Wireless Sensor Networks: A Neighborhood-Based Estimation of Distribution Algorithm

Zong-Gan Chen, Ying Lin, Yue‐Jiao Gong, Zhi‐Hui Zhan, Jun Zhang

Abstract: Sensor activity scheduling is critical for prolonging the lifetime of wireless sensor networks (WSNs). However, most existing methods assume sensors to have one fixed sensing range. Prevalence of sensors with adjustable sensing ranges posts two new challenges to the topic: 1) expanded search space, due to the rise in the number of possible activation modes and 2) more complex energy allocation, as the sensors differ in the energy consumption rate when using different sensing ranges. These two challenges make it hard to directly solve the lifetime maximization problem of WSNs with range-adjustable sensors (LM-RASs). This article proposes a neighborhood-based estimation of distribution algorithm (NEDA) to address it in a recursive manner. In NEDA, each individual represents a coverage scheme in which the sensors are selectively activated to monitor all the targets. A linear programming (LP) model is built to assign activation time to the schemes in the population so that their sum, the network lifetime, can be maximized conditioned on the current population. Using the activation time derived from LP as individual fitness, the NEDA is driven to seek coverage schemes promising for prolonging the network lifetime. The network lifetime is thus optimized by repeating the steps of the coverage scheme evolution and LP model solving. To encourage the search for diverse coverage schemes, a neighborhood sampling strategy is introduced. Besides, a heuristic repair strategy is designed to fine-tune the existing schemes for further improving the search efficiency. Experimental results on WSNs of different scales show that NEDA outperforms state-of-the-art approaches. It is also expected that NEDA can serve as a potential framework for solving other flexible LP problems that share the same structure with LM-RAS.

Introduction

Wireless Sensor Networks (WSNs) are fundamental to modern monitoring applications, yet their operational longevity is strictly limited by the finite battery life of individual nodes. In many deployment scenarios, such as environmental monitoring or disaster recovery, battery replacement is impractical. Consequently, activity scheduling—the process of selectively activating sensors while others remain in a low-power sleep state—has emerged as a primary strategy for lifetime maximization.

While traditional research often assumes a fixed sensing range for each node, contemporary sensors frequently offer adjustable sensing ranges. This flexibility allows for more granular control over coverage and energy consumption but significantly complicates the optimization landscape. This paper presents the Neighborhood-Based Estimation of Distribution Algorithm (NEDA), a novel approach designed to tackle the Lifetime Maximization problem with Range-Adjustable Sensors (LM-RAS).

The LM-RAS Problem

The transition from fixed-range to range-adjustable sensors introduces two primary challenges. First, the search space expands exponentially. Instead of a binary on/off state, each sensor now possesses multiple activation modes corresponding to different ranges. Second, energy allocation becomes non-linear; higher sensing ranges typically consume energy at a rate that increases quadratically with distance.

Illustration of range-adjustable sensors covering multiple targets.

The goal of LM-RAS is to identify a set of "coverage schemes"—configurations where a subset of sensors is activated at specific ranges to cover all targets—and determine the optimal duration for each scheme to maximize the total network lifetime without exceeding any sensor's energy budget.

The NEDA Framework

NEDA addresses LM-RAS by decomposing it into two interdependent subproblems: the discovery of efficient coverage schemes and the optimization of their activation times. This is achieved through a recursive process that alternates between an evolutionary algorithm and Linear Programming (LP).

LP-Based Fitness Evaluation (LPFE)

A defining feature of NEDA is its use of LP for fitness evaluation. In standard evolutionary algorithms, fitness is often a direct calculation of an objective function. In NEDA, the "fitness" of an individual (a coverage scheme) is determined by the activation time assigned to it by an LP model. If the LP solver determines that a particular scheme can run for a long duration while maintaining network-wide energy constraints, that scheme is considered highly fit.

Neighborhood Sampling Strategy (NSS)

To maintain diversity and prevent premature convergence on a narrow set of schemes—which would prematurely deplete specific sensor batteries—NEDA employs a Neighborhood Sampling Strategy. Instead of building a global probabilistic model for the entire population, NSS constructs local models based on "neighborhoods" in the search space.

The NEDA workflow for generating new individuals via probabilistic modeling.

As shown in the figure, NEDA identifies a neighborhood of similar individuals, builds a univariate probabilistic model from their traits, and samples new individuals from this distribution. This localized approach ensures that the algorithm explores a wide variety of coverage configurations, effectively distributing the energy load across the network.

Heuristic Repair Strategy (HRS)

Random sampling often results in "broken" schemes where some targets remain unmonitored. NEDA incorporates a Heuristic Repair Strategy (HRS) to address this. The HRS first performs a Refinement step, activating sensors with the highest remaining energy to cover gaps. It then follows with a Reduction step, where sensing ranges are minimized or redundant sensors are deactivated to ensure the scheme is "nondominated"—meaning no range can be further reduced without losing coverage.

Experimental Results

The performance of NEDA was evaluated against state-of-the-art methods, including the Column Generation Genetic Algorithm (CGGA) and AR-Iterative, across various network scales.

  • Longevity: In large-scale simulations with 1,000 sensors and 100 targets, NEDA demonstrated superior longevity, outperforming AR-Iterative by up to 7.8% and significantly exceeding baseline greedy approaches.
  • Computational Efficiency: NEDA proved to be remarkably faster than its competitors. For instance, in a 400-sensor scenario, NEDA reached its optimal solution in approximately 343 seconds, compared to 1,290 seconds for CGGA—a nearly fourfold improvement in speed.
  • Scalability: The algorithm maintained robust performance as network complexity increased, suggesting its viability for large-scale real-world WSN deployments.

Conclusion

NEDA provides a powerful framework for maximizing the lifetime of range-adjustable WSNs. By integrating evolutionary search with linear programming and employing a neighborhood-based sampling strategy, it effectively navigates the complex search space of LM-RAS. Beyond WSNs, the "flexible LP" framework introduced in this work holds potential for application in other domains where constraints are themselves subject to optimization, such as logistics and industrial scheduling.

Summary updated

Abstract

Sensor activity scheduling is critical for prolonging the lifetime of wireless sensor networks (WSNs). However, most existing methods assume sensors to have one fixed sensing range. Prevalence of sensors with adjustable sensing ranges posts two new challenges to the topic: 1) expanded search space, due to the rise in the number of possible activation modes and 2) more complex energy allocation, as the sensors differ in the energy consumption rate when using different sensing ranges. These two challenges make it hard to directly solve the lifetime maximization problem of WSNs with range-adjustable sensors (LM-RASs). This article proposes a neighborhood-based estimation of distribution algorithm (NEDA) to address it in a recursive manner. In NEDA, each individual represents a coverage scheme in which the sensors are selectively activated to monitor all the targets. A linear programming (LP) model is built to assign activation time to the schemes in the population so that their sum, the network lifetime, can be maximized conditioned on the current population. Using the activation time derived from LP as individual fitness, the NEDA is driven to seek coverage schemes promising for prolonging the network lifetime. The network lifetime is thus optimized by repeating the steps of the coverage scheme evolution and LP model solving. To encourage the search for diverse coverage schemes, a neighborhood sampling strategy is introduced. Besides, a heuristic repair strategy is designed to fine-tune the existing schemes for further improving the search efficiency. Experimental results on WSNs of different scales show that NEDA outperforms state-of-the-art approaches. It is also expected that NEDA can serve as a potential framework for solving other flexible LP problems that share the same structure with LM-RAS.
BibTeX
@article{chen2020maximizing,
  author = {Zong-Gan Chen and Ying Lin and Yue‐Jiao Gong and Zhi‐Hui Zhan and Jun Zhang},
  title = {{Maximizing Lifetime of Range-Adjustable Wireless Sensor Networks: A Neighborhood-Based Estimation of Distribution Algorithm}},
  journal = {IEEE Transactions on Cybernetics},
  year = {2020},
  doi = {10.1109/tcyb.2020.2977858},
}
Figure