Nearly Constant Approximation for Data Aggregation Scheduling in Wireless Sensor Networks

Abstract

Data aggregation is a fundamental yet time-consuming task in wireless sensor networks. We focus on the latency part of data aggregation. Previously, the data aggregation algorithm of least latency [1] has a latency bound of (Delta - 1) <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R</i> , where Delta is the maximum degree and R is the network radius. Since both Delta and <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R</i> could be of the same order of the network size, this algorithm can still have a rather high latency. In this paper, we designed an algorithm based on maximal independent sets which has an latency bound of 23 <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R</i> + Delta - 18. Here Delta contributes to an additive factor instead of a multiplicative one; thus our algorithm is nearly constant approximation and it has a significantly less latency bound than earlier algorithms especially when Delta is large.