World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

HARDNESS AND APPROXIMATION OF GATHERING IN STATIC RADIO NETWORKS

    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

    • M. Bellare, O. Goldreich and M. Sudan, SIAM Journal on Computing 27(3), 804 (1998). Crossref, ISIGoogle 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 et al. , Gathering in specific radio networks , 8èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'06) ( 2006 ) . Google Scholar
    • J.-C. Bermond, L. Gargano and S. Perennes, Discrete Applied Mathematics 86, 145 (1998). Crossref, ISIGoogle Scholar
    • J.-C. Bermondet al., SIAM Journal on Computing 27(4), 917 (1998). Crossref, ISIGoogle 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 Scholar
    • J.-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
    • P. Bertin, J.-F. Bresse and B. L. Sage, France Telecom R&D 22, 16 (2005). Google Scholar
    • G. Bianchi, IEEE Journal of Selected Areas of Communication 18, 535 (2000). Crossref, ISIGoogle Scholar
    • V.   Bonifaci et al. , An approximation algorithm for the wireless gathering problem , 10th Scandinavian Workshop on Algorithm Theory (SWAT) ( ) ( 2006 ) . Google Scholar
    • I. Chlamtac and O. Weinstein, IEEE Transaction on Communications 39(3), 426 (1991). Crossref, ISIGoogle 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
    • M. Chrobak, L. Gasieniec and W. Rytter, Journal of Algorithms 43(2), 177 (2002). Crossref, ISIGoogle 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
    • M. L. Elkin and G. Kortsarz, Journal of Algorithms 52(1), 8 (2004). Crossref, ISIGoogle Scholar
    • I. Gaber and Y. Mansour, Journal of Algorithms 46(1), 1 (2003). Crossref, ISIGoogle 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 Scholar
    • L. 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
    • J. Hastad, Acta Mathematica 182, 105 (1999). CrossrefGoogle Scholar
    • J.   Hromkovic et al. , 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