Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We studied the minimum-latency gossiping (all-to-all broadcast) problem in multi-hop wireless networks defined as follows. Each node in the network is initially given a message and the objective is to design a minimum-latency schedule such that each node distributes its message to all other nodes. We considered the unit-size message model, in which different messages cannot be combined as one message, and the unit disk graph model, in which a link exists between two nodes if and only if their Euclidean distance is less than 1. This problem is known to be NP-hard in such models. In this work we designed a gossiping scheme that significantly improved all current gossiping algorithms in terms of approximation ratio. Our work has approximation ratio 27, a great improvement of the current state-of-the-art algorithm (which has ratio 1000+).

REFERENCES

• 1: Reuven Bar-Yehuda , Amos Israeli , Alon Itai, Multiple communication im multihop radio networks, SIAM Journal on Computing, v.22 n.4, p.875-887, Aug. 1993 [doi>10.1137/0222055]
• 2: Jean-Claude Bermond , Luisa Gargano , Adele A. Rescigno , Ugo Vaccaro, Fast Gossiping by Short Messages, Proceedings of the 22nd International Colloquium on Automata, Languages and Programming, p.135-146, July 10-14, 1995
• 3: Jean-Claude Bermond , Luisa Gargano , Adele A. Rescigno , Ugo Vaccaro, Fast Gossiping by Short Messages, SIAM Journal on Computing, v.27 n.4, p.917-941, Aug. 1998 [doi>10.1137/S0097539795283619]
• 4: Bogdan S. Chlebus , Leszek Gąsieniec , Andrzej Lingas , Aris T. Pagourtzis, Oblivious gossiping in ad-hoc radio networks, Proceedings of the 5th international workshop on Discrete algorithms and methods for mobile computing and communications, p.44-51, July 2001, Rome, Italy [doi>10.1145/381448.381454]
• 5: Malin Christersson , Leszek Gasieniec , Andrzej Lingas, Gossiping with Bounded Size Messages in ad hoc Radio Networks, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.377-389, July 08-13, 2002
• 6: M. Chrobak , L. Gasieniec , W. Rytter, Fast broadcasting and gossiping in radio networks, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.575, November 12-14, 2000
• 7: Marek Chrobak , Leszek Gasieniec , Wojciech Rytter, A Randomized Algorithm for Gossiping in Radio Networks, Proceedings of the 7th Annual International Conference on Computing and Combinatorics, p.483-492, August 20-23, 2001
• 8: Marek Chrobak , Leszek Gasieniec , Wojciech Rytter, Fast broadcasting and gossiping in radio networks, Journal of Algorithms, v.43 n.2, p.177-189, May 2002 [doi>10.1016/S0196-6774(02)00004-4]
• 9: Andrea E. F. Clementi , Angelo Monti , Riccardo Silvestri, Selective families, superimposed codes, and broadcasting on unknown radio networks, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.709-718, January 07-09, 2001, Washington, D.C., United States
• 10: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 11: M. Flamini and S. Perennes. Lower bounds on the broadcasting and gossiping time of restricted protocols, 1999. Technical Report, INRIA.
• 12: C. Florens, M. Franceschetti, and R. J. McEliece. Lower bounds on data collection time in sensory networks. IEEE Journal on Selected Areas in Communications, 22(6).
• 13: Robert W. Floyd, Algorithm 97: Shortest path, Communications of the ACM, v.5 n.6, p.345, June 1962 [doi>10.1145/367766.368168]
• 14: Rajiv Gandhi , Srinivasan Parthasarathy , Arunesh Mishra, Minimizing broadcast latency and redundancy in ad hoc networks, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778442]
• 15: Leszek Gąsieniec , Andrzej Lingas, On adaptive deterministic gossiping in ad hoc radio networks, Information Processing Letters, v.83 n.2, p.89-93, 31 July 2002 [doi>10.1016/S0020-0190(01)00312-X]
• 16: Leszek Gasieniec , Igor 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: Foundations of Information Technology in the Era of Networking and Mobile Computing, p.193-205, August 25-30, 2002
• 17: L. Gasieniec, I. Potapov, and Q. Xin. Time efficient gossiping in known radio networks. In SIROCCO'04: the 11th Colloquium on Structural Information and Communication Complexity, pages 173--184, 2004.
• 18: S. C.-H. Huang, P.-J. Wan, X. Jia, H. Du, and W. Shang. Minimum-latency broadcast scheduling in wireless ad hoc networks. In INFOCOM'?07: the 26th Annual IEEE Conference on Computer Communications, pages 733--739, 2007.
• 19: Piotr Indyk, Explicit constructions of selectors and related combinatorial structures, with applications, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.697-704, January 06-08, 2002, San Francisco, California
• 20: Xiaohua Jia, A distributed algorithm of delay-bounded multicast routing for multimedia applications in wide area networks, IEEE/ACM Transactions on Networking (TON), v.6 n.6, p.828-837, Dec. 1998 [doi>10.1109/90.748092]
• 21: Deying Li , Xiaohua Jia , Hai Liu, Energy Efficient Broadcast Routing in Static Ad Hoc Wireless Networks, IEEE Transactions on Mobile Computing, v.3 n.2, p.144-151, April 2004 [doi>10.1109/TMC.2004.10]
• 22: F. Manne and Q. Xin. Optimal gossiping with unit size messages in known topology radio networks. In CAAN'06: the 3rd Workshop of Combinatorial and Algorithmic Aspects of Networking, pages 125--134, Berlin/Heidelberg, 2006. Springer.
• 23: Sze-Yao Ni , Yu-Chee Tseng , Yuh-Shyan Chen , Jang-Ping Sheu, The broadcast storm problem in a mobile ad hoc network, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.151-162, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313525]
• 24: Krishnamurthi Ravishankar , Suresh Singh, Asymptotically optimal gossiping in radio networks, Discrete Applied Mathematics, v.61 n.1, p.61-82, July 7, 1995 [doi>10.1016/0166-218X(93)E0176-Y]
• 25: K. Ravishankar and S. Singh. Gossiping on a ring with radios. ParallelProcessing Letters, 6(1):115?126, 1996.
• 26: Y. Xu. An O(n^1:5) deterministic gossiping algorithm for radio networks. Algorithmica, 36(1).

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms

Keywords:
TDMA, broadcast, gossip