Using Mobile Sinks in WSN: Computational Complexity and a Theoretical Bound

In this paper, we study the lifetime optimization problem in wireless sensor networks using mobile sink nodes. This problem is inherently difficult since we need to consider both sink scheduling and data routing. Through a simple case study we develop a novel notation named the Placement pattern (PP) to bound traffic patterns with candidate locations. This significantly decreases the number of elements needed to be scheduled. Based on the PP, we mathematically formulate this optimization problem as a Mixed-integer non-linear programming (MINLP), which is very tough and time consuming to solve. By proving that the problem is NP-complete, we point out that instead of seeking an optimal algorithm, heuristic algorithms, especially those with performance guarantee, would be much more desirable to develop. Furthermore, in order to help identify performance gains of heuristic algorithms proposed in the future, we develop a Linear programming (LP) formulation which serves as an upper bound by adopting a reformulation and relaxation technique.