1Maximum Achievable Throughput in a Wireless Sensor Network Using In-network Computation for Statistical Functions

Abstract—Many applications require the sink to compute a function of the data collected by the sensors. Instead of sending all the data to the sink, the intermediate nodes could process the data they receive to significantly reduce the volume of traffic transmitted: this is known as in-network computation. Instead of focusing on asymptotic results for large networks as is the current practice, we are interested in explicitly computing the maximum achievable throughput of a given network when the sink is interested in the first M statistical moments of the collected data. Here, the k-th statistical moment is defined as the expectation of the k-th power of the data. Flow models have been routinely used in multi-hop wireless networks when there is no in-network computation and they are typically tractable for relatively large networks. However, deriv-ing such models is not obvious when in-network computation is allowed. We develop a discrete-time model for the real-time network operation and perform two transformations to obtain a flow model that keeps the essence of in-network computa-tion. This gives an upper bound on the maximum achievable throughput. To show its tightness, we derive a numerical lower bound by computing a solution to the discrete-time model based on the solution to the flow model. This lower bound turns out to be close to the upper bound proving that the flow model is an excellent approximation to the discrete-time model. We then provide several engineering insights on these networks. Index Terms—Sensor networks, in-network computation, throughput, flow model. I