Not to be crass, but wouldn't any low bandwidth sound-based protocol be easy to rig up for underwater? Obviously there's a bit of adaptation required, but it shouldn't be _that_ hard to set up a 28.8k modem with a directional speaker and microphone rigged up to point vaguely toward each other (i.e. at the surface pointing down and on the sub pointing up). Hell, even automated Morse code sending literal text messages at 3 sps is better than nothing.