The lifetime maximization problem in wireless sensor networks with a mobile sink: mixed-integer programming formulations and algorithms

Abstract

This article considers the problem of maximizing the lifetime of a wireless sensor network with a mobile sink. The sink travels at finite speed among a subset of possible sink locations to collect data from a stationary set of sensor nodes. The considered problem chooses a subset of sink locations for the sink to visit, finds a tour for the sink among the selected sink locations, and prescribes an optimal data routing scheme from the sensor nodes to each location visited by the sink. The sink’s tour is constrained by the time it spends at each location collecting data. Two variations of this problem are examined based on assumptions regarding delay tolerance. Exact mixed-integer programming formulations to model this problem are provided along with cutting planes, preprocessing techniques, and a Benders decomposition algorithm to improve its solvability. Computational results demonstrate the effectiveness of the proposed methods.

Keywords:

• Wireless sensor networks
• lifetime maximization
• sink trajectory
• mixed-integer programming
• mobile sink