loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Fourth IEEE International Conference on Pervasive Computing and Communications Workshops (PERCOMW'06)
Hardness and approximation of Gathering in static radio networks
Pisa, Italy
March 13-March 17
ISBN: 0-7695-2520-2
J.-C. Bermond, Universite de Nice-Sophia Antipolis, France
N. Morales, Universite de Nice-Sophia Antipolis, France
S. Perennes, Universite de Nice-Sophia Antipolis, France
J. Galtier, France Telecom Research and Development
R. Klasing, LaBRI - Universite Bordeaux 1 - CNRS, France
In this paper, we address the problem of gathering information in a central node of a radio network, where interference constraints are present.We take into account the fact that, when a node transmits, it produces interference in an area bigger than the area in which its message can actually be received. The network is modeled by a graph; a node is able to transmit one unit of information to the set of vertices at distance at most dT in the graph, but when doing so it generates interference that does not allow nodes at distance up to dI (dI = dT ) to listen to other transmissions. Time is synchronous and divided into time-steps in each of which a round (set of non-interfering radio transmissions) is performed. We give a general lower bound on the number of rounds required to gather on any graph, and present an algorithm working on any graph, with an approximation factor of 4. We also show that the problemof finding an optimal strategy for gathering (one that uses a minimum number of time-steps) does not admit a Fully Polynomial Time Approximation Scheme if dI \ge dT , unless P=NP, and in the case dI = dT the problem is NP-hard.
Citation:
J.-C. Bermond, N. Morales, S. Perennes, J. Galtier, R. Klasing, "Hardness and approximation of Gathering in static radio networks," percomw, pp.75-79, Fourth IEEE International Conference on Pervasive Computing and Communications Workshops (PERCOMW'06), 2006
Usage of this product signifies your acceptance of the Terms of Use.