Create a network of RPi over evolving networks (WiFi/4G/other)

Hello all
I'm managing a fleet of IoT devices based on RPi. We are currently using ZeroTier to make them discover each other even if they are in different locations. However this solution is not working as we want, as we lose connection and need to restart the RPi when then networking between two of the devices changes.
The main change that can occur is the devices going out of WiFi range, which is expected so each of them has a 4G modem.

More concrete example:
Device A sends telemetry to device B. Both are in the same ZeroTier network and can communicate together (ping/ssh is fine).
Moving device A out of range of the WiFi make it lose the link to B. Both are still connected to internet, but cannot see each others anymore. Restarting device A solves the issue while it stays out of WiIFi range.
My diagnostic is that ZeroTier hole-punching works against us. If we lose the first link it used to punch a direct route then it is not able to find a new route.

I'm open to changing from ZeroTier to another service that would allow SSH access to the devices as well as communication between them.

Thanks for any help/suggestions anyone can provide.