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 δ r with transmission range δ r is connected for some constant 0 < δ ≤ 1/3^1/α , where r is the maximum transmission range determined by the maximum power, an approximation algorithm is presented with at most b ³(log2 n + 6) + (R−1)(μ 1 + μ 2) time slots, where n is the number of nodes, R is the radius of graph G δ r with respect to the sink, and b, μ 1, μ 2 are constants. Since both R and log2 n are lower bounds for the optimal latency of aggregation in the unit disk graph G δ r , our algorithm has a constant‐approximation ratio for the aggregation problem in G δ r .