Network lifetime maximization in sensor networks with multiple mobile sinks

In this paper we deal with the network lifetime maximization problem under multiple mobile sink environments, namely, the h-hop-constrained multiple mobile sink problem, which is defined as follows. Given a stationary sensor network with K mobile sinks that traverse and sojourn in a given space of locations in the monitoring area, assume that the total travel distance of each sink is bounded by a given value L and the maximum number of hops from each sensor to a sink is bounded by an integer h ≥ 1, the problem is to find an optimal trajectory for each mobile sink and determine the sojourn time at each sojourn location in the trajectory such that the network lifetime is maximized. We first formulate this problem as a joint optimization problem consisting of finding an optimal trajectory and determining the sojourn time at each chosen location. We then show that the problem is NP-hard. We instead devise a novel three-stage heuristic, which consists of calculating the sojourn time profile at each potential sojourn location, finding a high-quality trajectory for each mobile sink, and determining the actual sojourn time at each sojourn location. We finally conduct extensive experiments by simulations to evaluate the performance of the proposed algorithm in terms of network lifetime. We also investigate the impact of constraint parameters on the network lifetime. The experimental results demonstrate that the performance of the proposed heuristic is highly comparable to the optimal one, and the ratios of network lifetime of the proposed algorithm to the optimal network lifetime are ranged from 56% to 93%. © 2011 IEEE.