Lecture Notes in Computer Science, 2009, Volume 5682/2009, 428-437, DOI: 10.1007/978-3-642-03417-6_42

An Approximation Algorithm for Conflict-Aware Many-to-One Data Aggregation Scheduling in Wireless Sensor Networks

Qinghua Zhu and Deying Li

View Related Documents

Abstract

A network of many sensors and a base station that are deployed over a region is considered. Each sensor has a transmission range, a interference range, and a carrier sensing range, which is 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 sensors, and parameters r,α, and β, 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 designed an nearly a constant ratio approximation algorithm and a heuristic algorithm for the problem. Extensive simulations have been done to show the performances of the two algorithms.

Keywords  Conflict-aware - many-to-one data aggregation - latency - approximation algorithm - wireless sensor network

Fulltext Preview

Image of the first page of the fulltext document