Scaling Bounds for Function Computation over Large Networks

We develop order bounds on the refresh rate of computing functions over large multi-hop sensor networks, with finite degree (finite neighbors for each node). The refresh rate quantifies how often the function can be re-computed with new data at sensor nodes. Giridhar and Kumar (2005) considered deterministic function computation for two important classes of functions (type-threshold and type-sensitive functions) and showed that for networks with high degree (random planar geometric graph with n nodes and average degree Theta(log n)), type- threshold functions (e.g. max) are easy to compute (refresh rate of Theta(1/log(n))), and type-sensitive functions (e.g. average) can be computed only at a rate Theta(1/log(n)). In this paper, we first show that type-threshold functions can be computed at an optimal refresh rate of Theta(1) over networks with finite degree. However, the computation of type-sensitive function do not become uniformly faster as the graph degree becomes smaller. We demonstrate that while some type-sensitive functions (such as computing parity) are not hard to compute in finite degree graphs (we can achieve a refresh rate proportional to (1/d), where d is the maximum graph degree), there exist type-sensitive functions (e.g., computing the average to one-bit precision) in this class that cannot be deterministically computed faster than Theta(1/log n) even for finite degree graphs. However, by relaxing the requirements to allow probabilistic guarantees, computing the average can be achieved at a refresh rate of Theta(1) over any graph with bounded degree and a refresh rate of Theta(1/ log log n) for random planar networks. Further, for random planar networks operating over an AWGN channel with signal power path-loss, we show that even refresh rates 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 sizea