Abstract
Deploying radio-capable gateways at the sea surface can mitigate the limitations of acoustic communications in underwater sensor networks (UWSN). Finding the best placement for gateways is formulated as an ILP problem. The choice of gateway candidate locations can affect both the feasibility and the quality of the solution. In this paper, we show the limitation of using a regular mesh of candidate locations, and present a novel algorithm for defining candidate locations that both reduces the complexity of the optimization problem and enhances the feasibility and quality of the solution.