Distributed Data Compression in Sensor Clusters: A Maximum Independent Flow Approach

Abstract

Let a cluster (network) of sensors be connected by the communication links, each link having a capacity upper bound. Each sensor observes a discrete random variable in private and one sensor serves as the cluster header or sink. Here, we formulate the problem of how to let the sensors encode their observations such that the direction of compressed data is a feasible flow towards the sink. We demonstrate that this problem can be solved in a distributed manner by adapting an existing maximum independent flow (MIF) algorithm in polynomial time. Further, we reveal that this algorithm in fact determines an optimal solution by recursively pushing the remaining randomness in the sources via unsaturated communication links towards the sink. For those networks with integral communication capacities, we propose an integral MIF algorithm which completes much faster than MIF. Finally, we point out that the nature of the data compression problem in a sensor cluster is to seek the maximum independent information flow in the intersection of two submodular polyhedra, which can be further utilized to improve the MIF algorithm in the future.