Scheduling Sinks in Wireless Sensor Networks: Theoretic Analysis and an Optimal Algorithm

Sink scheduling is shown to be a promising scheme in wireless sensor networks. However, previous approaches on this topic suffer from poor performance due to lack of joint considerations. Therefore, in this paper, we aim to fill in the research blank. First, we develop a novel notation Placement Pattern (PP) to bound time-varying routes with placement of sinks. This bounding technique transforms time-related constraints into pattern-based ones and allows us to formulate this optimization in pattern domain. If there is only one sink, we develop a polynomial time algorithm to solve it optimally. If there are multiple sinks, we develop a column generation based approach to solve it efficiently. Simulations not only demonstrate the efficiency of proposed algorithms but also substantiate the importance of sink mobility for energy-constrained sensor networks.