This work addresses the problem of determining the positions of a set of nodes (underwater vehicles, in the present context) through two-way time-of-flight measurements (equivalently, ranges) and interpacket delays (equivalently, range differences). The approach is based on reconstruction and factorization of Euclidean Distance Matrices (EDM), which provides a solid framework to deal with noisy measurements and partial loss of data, while retaining a compact mathematical formulation. The paper discusses techniques for gathering range and range difference data (interrogation schemes) and assesses the performance of EDM completion algorithms to deal with incomplete measurements or outliers.