Approximation for a scheduling problem with application in wireless networks

A network of many sensors and a base station that are deployed over a region is considered. Each sensor has a transmission range, an interference range and a carrier sensing range, which are r, αr and βr, respectively. In this paper, we study the minimum latency conflict-aware many-to-one data aggregation scheduling problem: Given locations of sensors along with a base station, a subset of all sensors, and parameters r, α and β, to find a schedule in which the data of each sensor in the subset can be transmitted to the base station with no conflicts, such that the latency is minimized. We designe an algorithm based on maximal independent sets, which has a latency bound of (a + 19b)R + Δb ? a + 5 time slots, where a and b are two constant integers relying on α and β, Δ is the maximum degree of network topology, and R is the trivial lower bound of latency. Here Δ contributes to an additive factor instead of a multiplicative one, thus our algorithm is nearly a constant (a + 19b)-ratio.