Constant-approximation for optimal data aggregation with physical interference

In this paper, we study the aggregation problem with power control under the physical interference. The maximum power is bounded. The goal is to assign power to nodes and schedule transmissions toward the sink without physical interferences such that the total number of time slots is minimized. Under the assumption that the unit disk graph G <Subscript> δ <Emphasis Type="Bold">r </Subscript> with transmission range δ <Emphasis Type="Bold">r is connected for some constant 0 > δ ≤ 1/3<Superscript>1/α </Superscript>, where <Emphasis Type="Bold">r is the maximum transmission range determined by the maximum power, an approximation algorithm is presented with at most b <Superscript>3</Superscript>(log<Subscript>2</Subscript> n + 6) + (R−1)(μ <Subscript>1</Subscript> + μ <Subscript>2</Subscript>) time slots, where n is the number of nodes, R is the radius of graph G <Subscript> δ <Emphasis Type="Bold">r </Subscript> with respect to the sink, and b, μ <Subscript>1</Subscript>, μ <Subscript>2</Subscript> are constants. Since both R and log<Subscript>2</Subscript> n are lower bounds for the optimal latency of aggregation in the unit disk graph G <Subscript> δ <Emphasis Type="Bold">r </Subscript>, our algorithm has a constant-approximation ratio for the aggregation problem in G <Subscript> δ <Emphasis Type="Bold">r </Subscript>. Copyright Springer Science+Business Media, LLC. 2013