Multi-vehicle teams are being used more and more frequently to solve increasingly complex problems [1, 2]. In order for the team to work effectively, the vehicles must communicate to coordinate their efforts. In applications with high quality communication links, the vehicles are able to operate almost as a single entity. But in more harsh and dynamic environments, such as underwater, communication is severely limited, making cooperation and coordination much more difficult [3]. Message collision is a significant problem in underwater acoustic networks, but can be overcome by using Time Division Multiple Access (TDMA). TDMA assigns each vehicle a time slot to communicate in to avoid multiple vehicles communicating at the same time. TDMA, however, introduces constraints not generally considered by routing algorithms in limited bandwidth networks. In this paper we identify the need for intelligent solutions that can alleviate undesired bottlenecks and message traffic in poor communication networks of multi-agent systems under TDMA constraints. We then present simulation results of preliminary strategies that attempt to overcome some of the communication challenges in such a network.