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

• Formulate delivery latency minimization problem (DLMP) as an integer programming.
• Prove the NP completeness of DLMP.
• Propose a substitution heuristic algorithm to plan the travel route of the mobile sink by point.
• Minimize delivery latency by a relaxed linear programming.
• Extensive simulations validate the effectiveness of the proposed heuristic algorithm.

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.