Lossless In-Network Processing and Its Routing Design in Wireless Sensor Networks

In many domain-specific monitoring applications of wireless sensor networks (WSNs), such as structural health monitoring, volcano tomography, and machine diagnosis, the raw data in WSNs are required to be losslessly gathered to the sink, where a specialized centralized algorithm is then executed to extract some global features or model parameters. To reduce the large raw data transmission, in-network processing is usually employed. However, different from most existing in-network processing works that pre-assume some common computation/aggregation functions, in-network processing of a given centralized algorithm requires exact partitioning of the algorithm first and then appropriately assigning the partitioned computations into WSNs. We call this lossless in-network processing, which has not been studied much. Lossless in-network processing raises two questions: 1) what pattern should a centralized algorithm be partitioned into so that the partitioned computations can be flexibly assigned into a WSN with arbitrary topology? and 2) for each partition pattern, how should efficient routing for the resource-limited sensor nodes be designed? These two questions can be referred to as a topology-constrained computation partition problem and a computation-constrained routing design problem, respectively. In this paper, we first introduce some general patterns on the topology-constrained computation partition. Then, with the computation constraints in the patterns, we present a series of novel routing schemes customized for different cases of computation results. The work in this paper can also serve as a guideline for distributed computing of big data, where the data spreads in a large network.