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 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 communication scheme is at most $Theta(1/log n)$, 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/loglog{n})$ for random planar networks. Further, for such networks operating over an AWGN channel with signal power path-loss, we show that even 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 to probabilistic requirements enables sizeable improvement in refresh rates.