Network computing : limits and achievability

Advancements in hardware technology have ushered in a digital revolution, with networks of thousands of small devices, each capable of sensing, computing, and communicating data, fast becoming a near reality. These networks are envisioned to be used for monitoring and controlling our transportation systems, power grids, and engineering structures. They are typically required to sample a field of interest, do 'in-network' computations, and then communicate a relevant summary of the data to a designated sink node(s), most often a function of the raw sensor measurements. In this thesis, we study such problems of network computing under various communication models. We derive theoretical limits on the performance of computation protocols as well as design efficient schemes which can match these limits. First, we begin with the one -shot computation problem where each node in a network is assigned an input bit and the objective is to compute a function f of the input messages at a designated receiver node. We study the energy and latency costs of function computation under both wired and wireless communication models. Next, we consider the case where the network operation is fixed, and its end result is to convey a fixed linear transformation of the source transmissions to the receiver. We design communication protocols that can compute functions without modifying the network operation. This model is motivated by practical considerations since constantly adapting the node operations according to changing demands is not always feasible in real networks. Thereafter, we move on to the case of repeated computation where source nodes in a network generate blocks of independent messages and a single receiver node computes a target function f for each instance of the source messages. The objective is to maximize the average number of times f can be computed per network usage, i.e., the computing capacity. We provide a generalized \textit{min- cut} upper bound on the computing capacity and study its tightness for different classes of target functions and network topologies. Finally, we study the use of linear codes for network computing and quantify the benefits of non-linear coding vs linear coding vs routing for computing different classes of target function