1Energy-Constrained Bi-Objective Data Muling in Underwater Wireless Sensor Networks

Abstract—For underwater wireless sensor networks (UWSNs), data muling is an effective approach to data gathering, where sensor data are collected when a mobile data mule travels within the wireless communication range of the sensors. However, given the constrained energy available on a data mule and the energy consumption of its motions and communications a data mule may be prevented from visiting every deployed sensor in a tour. We formulate the tour planning of a data mule collecting sensor data in UWSNs as an energy-constrained bi-objective optimization problem termed the Underwater Data Muling Problem (UDMP). UDMP has the two conflicting objectives of maximizing the number of sensors contacted and minimizing the length of a tour, while satisfying the energy constraint on the data mule at all times. We design two heuristic algorithms to solve one special case and one generalized case of this NP-hard problem, respectively. Each algorithm computes a set of Pareto-efficient solutions addressing the tradeoff between the two optimization objectives to facilitate tour planning. Simulation results validate the effectiveness of both algorithms. Index Terms—Underwater wireless sensor networks, data muling, tour planning, heuristic algorithm. F