HARDNESS AND APPROXIMATION OF GATHERING IN STATIC RADIO NETWORKS
Abstract
In this paper, we address the problem of gathering information in a specific node (or sink) 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 general lower bounds on the number of rounds required to gather into a sink of a general graph, and present an algorithm working on any graph, with an approximation factor of 4. We also show that the problem of finding an optimal strategy for gathering is NP-HARD, for any values of dI and dT. If dI > dT, we show that the problem remains hard when restricted to the uniform case where each vertex in the network has exactly one piece of information to communicate to the sink.
This work has been supported by the European projects AEOLUS and COST Action TIST 293 (GRAAL), and is part of the CRC CORSO with France Telecom R&D. Nelson Morales is funded by a CONICYT/INRIA doctoral grant. An extended abstract of this research was presented at FAWN 2006, Pisa, Italy.
References
- SIAM Journal on Computing 27(3), 804 (1998). Crossref, ISI, Google Scholar
-
J.-C. Bermond , R. Corrêa and J. Yu , Gathering algorithms on paths under interference constraints ,6th Conference on Algorithms and Complexity ( 2006 ) . Google Scholar -
J.-C. Bermond , Gathering in specific radio networks ,8èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'06) ( 2006 ) . Google Scholar - Discrete Applied Mathematics 86, 145 (1998). Crossref, ISI, Google Scholar
- SIAM Journal on Computing 27(4), 917 (1998). Crossref, ISI, Google Scholar
J.-C. Bermond , T. Kodate and S. Perennes , Gossiping in Cayley graphs by packets, Proceedings of 8-th Franco-Japanese, 4-th Franco-Chinese Conference on Combinatorics and Computer Science,Lecture Notes on Computer Science 1120 (Springer, 1995) pp. 301–315. Google ScholarJ.-C. Bermond and J. Peters , Efficient gathering in radio grids with interference,Septièmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'05) (2005) pp. 103–106. Google Scholar- France Telecom R&D 22, 16 (2005). Google Scholar
- IEEE Journal of Selected Areas of Communication 18, 535 (2000). Crossref, ISI, Google Scholar
-
V. Bonifaci , An approximation algorithm for the wireless gathering problem ,10th Scandinavian Workshop on Algorithm Theory (SWAT) ( ) ( 2006 ) . Google Scholar - IEEE Transaction on Communications 39(3), 426 (1991). Crossref, ISI, Google Scholar
M. Christersson , L. Gasieniec and A. Lingas , Gossiping with bounded size messages in ad-hoc radio networks, Proceedings of 29th International Colloquium on Automata, Languages and Programming (ICALP'02),Lecture Notes in Computer Science 2380 (Springer-Verlag, 2002) pp. 377–389. Google Scholar- Journal of Algorithms 43(2), 177 (2002). Crossref, ISI, Google Scholar
S. A. Cook , The complexity of theorem proving procedures, Proc. 3rd Annual ACM Symposium on Theory of Computing (1971) pp. 151–158. Google Scholar- Journal of Algorithms 52(1), 8 (2004). Crossref, ISI, Google Scholar
- Journal of Algorithms 46(1), 1 (2003). Crossref, ISI, Google Scholar
J. Galtier , Optimizing the IEEE 802.11b performance using slow congestion window decrease, Proc. 16th ITC Specialist Seminar on Performance Evaluation of Wireless and Mobile Systems (2004) pp. 165–176. Google ScholarL. Gasieniec and I. Potapov , Gossiping with unit messages in known radio networks, Proceedings of the IFIP 17th World Computer Congress - TC1 Stream / 2nd IFIP International Conference on Theoretical Computer Science (Kluwer, B. V., 2002) pp. 193–205. Google Scholar- Acta Mathematica 182, 105 (1999). Crossref, Google Scholar
-
J. Hromkovic , Dissemination of Information in Communication Networks: Broadcasting, Gossiping, Leader Election, and Fault-Tolerance ,Springer Monograph ( Springer-Verlag , 2005 ) . Google Scholar - R. Klasing, N. Morales, and S. Perennes. On the complexity of bandwidth allocation in radio networks with steady traffic demands. Technical report, INRIA Research Report RR-5432 and I3S Research Report I3S/RR-2004-40-FR, 2004 . Google Scholar
- P. M ühlethaler. 802.11 et les réseaux sans fil. Eyrolles, 2002 . Google Scholar


