Dellat: Delivery Latency Minimization in Wireless Sensor Networks with Mobile Sink

Adopting mobile data gathering in wireless sensor networks (WSNs) can reduce the energy consumption on data forwarding thus achieve more uniform energy consumption among sensor nodes. However, the data delivery latency inevitably increases in mobile data gathering due to the travel of the mobile sink. In this paper, we consider a delivery latency minimization problem (DLMP) in a randomly deployed WSN. Our goal is to minimize the travel latency of the mobile sink. We formulate the DLMP as an integer programming problem which subjects to the direct access constraint, the data transmission constraint and the route traverse constraint. We prove that the DLMP is an NP-Complete (NPC) problem, and then propose a substitution heuristic algorithm to solve it by shortening the travel route and having the mobile sink move and collect data at the same time. We compare the proposed algorithm with other two algorithms, a traveling salesman problem (TSP) heuristic algorithm and a random heuristic algorithm through simulations. Our extensive simulation results show that although all the three algorithms can shorten the data delivery latency in mobile data gathering, the proposed substitution heuristic algorithm is the most effective one.