Randomization for robust communication in networks, or Brother, can you spare a bit?

Communication strategies for large distributed networks such as sensor networks or wireless ad-hoc networks should be robust to unknown environmental conditions. Arbitrarily varying channels (AVCs) are one way of modeling unknown interference. A recent result of the authors showed that for a Gaussian arbitrarily varying channel a small secret key shared by the transmitter and receiver could enable them to use a randomized code that is robust to the AVC interference. The question of how to acquire this small secret key is discussed for both sensor networks and ad-hoc wireless networks. For sensor networks some examples are given in which a sparse underlying signal can be reconstructed from correlated observations at the transmitter and receiver. For ad-hoc networks a cellular model for distributing the randomization is proposed and the benefits of feedback are analyzed. All of these operations can be viewed as a one-time operation - once each link has its own secret key, it can be updated at no cost to the data rate.