Mismatched side information in wireless network compression via overhearing helpers

Recently, we proposed wireless network compression via memory-enabled overhearing helpers as an endeavor to reduce the traffic load on the wireless gateway via elimination of the redundant data in the network. In this setup, each memory-enabled helper overhears the data packets previously sent by the wireless gateway to various mobile clients within its coverage and uses them toward forming a model about the content of the packets from the traffic. The resulting model is then used as side information by the wireless network compression module in a two-part code to reduce the overall cost of delivering a packet to a client over links with asymmetric cost (where the helper-client link is far less costly than the gateway-client link). One main challenge in this scenario is the fact that memory-enabled overhearing helpers do not receive all of the sequences sent to the mobile clients (as there is no feedback in place in the overhearing link), resulting in mismatched side information between the encoder (i.e., gateway) and the helper. In this paper, we present an information theoretic formulation for the mismatched side information problem. We study this problem in the context of universal lossless compression and derive bounds on the average minimax redundancy of encoding each packet. Our results also lead to construction of coding schemes for the mismatched side information using two-part codes.