Scaling Bounds for Function Computation over Large Sensor Networks

We develop order bounds on the refresh rate of computing two classes of functions over large multi-hop sensor networks - namely, type-threshold (e.g. max) and type-sensitive functions (e.g. average). The refresh rate quantifies how often the function can be re-computed with new data at sensor nodes. We first show that for type-threshold functions an optimal refresh rate of theta(1) is possible over networks whose connectivity graphs have finite degree. Next, even for a simple representative type-sensitive function, we show that the maximum refresh rate that can be achieved in a wide class of networks of n nodes with any multi-hop digital comunication scheme is at most theta(1/log n)m, if the goal is to compute the function with deterministic guarantees. On the other hand, we show that relaxing the requirements to allow probabilistic guarantees enables a refresh rate of theta(1) over any graph with bounded degree and a refresh rate of theta(1/log n) for random planar networks. Further, for such networks operating over an AWGN channel with signal power path-loss, we show that even a refresh rate of theta(1) can be achieved with vanishing distortion when the power path-loss exponent is strictly less than 4. Thus, relaxing deterministic computation guarantees of probabilistic requirements enables sizeable improvement in refresh rates.