Towards optimal wireless sensor network lifetime in three dimensional terrains using relay placement metaheuristics

Highlights：

• We propose a mixed-integer programming model as a basis to achieve lower bound solutions. However, mixed-integer linear programming solvers have exponential complexity and do not scale well to large instances.

• We propose an approximate two-phase relay node deployment strategy in 3D, which includes 2 sub-problems: The optimal flow capacity problem (OFC3D) and the optimal sensor assignment problem (OSA3D).

• An exact maximum flow and binary search algorithm is proposed to solve OSA3D, and a novel local search is proposed for OFC3D. The two algorithms are used in conjunction to generate full solutions to ORP3D.

• We evaluate the efficiency of the proposed algorithm through various experimental scenarios and compare the results with lower bound solutions.

摘要

•We study The Optimal Relay Node Placement Problem (ORP3D) to maximize the network lifetime of wireless sensor networks in three-dimensional terrains. The main idea of our approach is reducing sensor energy consumption by optimizing relay nodes placement.•We propose a mixed-integer programming model as a basis to achieve lower bound solutions. However, mixed-integer linear programming solvers have exponential complexity and do not scale well to large instances.•We propose an approximate two-phase relay node deployment strategy in 3D, which includes 2 sub-problems: The optimal flow capacity problem (OFC3D) and the optimal sensor assignment problem (OSA3D).•An exact maximum flow and binary search algorithm is proposed to solve OSA3D, and a novel local search is proposed for OFC3D. The two algorithms are used in conjunction to generate full solutions to ORP3D.•We evaluate the efficiency of the proposed algorithm through various experimental scenarios and compare the results with lower bound solutions.