In this paper, we design a heuristic interference-graph-based time division multiple access (IG-TDMA) protocol for underwater acoustic sensor networks (UW-ASNs) to improve the network performance. A general underwater communication scenario is considered for the protocol design, where the communication network topology is modeled as a three-dimensional (3D) scenario and the mobility of sensor nodes is also taken into consideration. In this protocol, we introduce a dynamic and flexible spatial reuse strategy and formulate the interference scenario as a dynamic interference graph according to the nodes' position distribution and a preset interference-free threshold. To achieve high spatial reuse efficiency with low computational complexity, we propose a heuristic interference graph clustering algorithm for the protocol. Simulations verify the performance advantages of our proposed protocol over the carrier sense multiple access with collision avoidance (CSMA/CA) protocol and the traditional TDMA protocol.