On multi-path aggregation of duplicate-sensitive functions

Resumo

Previous decades brought about a revolution in radio and microprocessor technology that made possible a plethora of new applications. In particular, the possibility of using many inexpensive sensor nodes interconnected by wireless networks (WSN) for a number of ends, such as pollution monitoring and defense, draw the attention of the research community. WSN are usually heavily resource-constrained. Of particular relevance is energy, since in many applications nodes should operate during long periods from batteries. The literature on this topic reveals many techniques to improve energy efficiency, one of them being the use of network aggregation. However, the problem of aggregation of duplicate sensitive summaries (e.g. sum, average, histogram, etc.) in multi-path routing networks is not fully resolved. This paper addresses this problem by sending redundant aggregated information through different paths, so data can be reconstruct to obtain the exact summary, provided that there is at least one feasible path. Two algorithms are presented, one better suited for networks dominated by link errors and another suited to networks where the predominant error source is node failures. The algorithms are light during normal network operation, with the most intensive processing performed during the initialization phase. The approach presented here in outperform previous solutions found in the literature in two key aspects: complete topology independence and aggregation depth independence.