Advertisement
Published in:
2011 | OriginalPaper | Chapter
Optimal Time Data Gathering in Wireless Networks with Omni–Directional Antennas
Authors : Jean-Claude Bermond, Luisa Gargano, Stephane Perénnes, Adele A. Rescigno, Ugo Vaccaro
Published in: Structural Information and Communication Complexity
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We study algorithmic and complexity issues originating from the problem of data gathering in wireless networks. We give an algorithm to construct minimum makespan transmission schedules for data gathering when the communication graph
G
is a tree network, the interference range is
any
integer
m
≥ 2, and no buffering is allowed at intermediate nodes. In the interesting case in which all nodes in the network have to deliver an arbitrary non-zero number of packets, we provide a closed formula for the makespan of the optimal gathering schedule. Additionally, we consider the problem of determining the computational complexity of data gathering in general graphs and show that the problem is NP–complete. On the positive side, we design a simple (1 + 2/
m
) factor approximation algorithm for general networks.