This paper presents a cooperative distributed planning algorithm that ensures network connectivity for a team of heterogeneous agents operating in dynamic and communication-limited environments. The algorithm, named CBBA with Relays, builds on the Consensus-Based Bundle Algorithm (CBBA), a distributed task allocation framework developed previously by the authors and their colleagues. Information available through existing consensus phases of CBBA is leveraged to predict the network topology and to propose relay tasks to repair connectivity violations. The algorithm ensures network connectivity during task execution while preserving the distributed and polynomial-time guarantees of CBBA. By employing under-utilized agents as communication relays, CBBA with Relays improves the range of the team without limiting the scope of the active agents, thus improving mission performance. The algorithm is validated through simulation trials and through experimental indoor and outdoor field tests, demonstrating the real-time applicability of the approach.