Efficient Broadcasting in Self-organizing Multi-hop Wireless Networks

  • Nathalie Mitton
  • Eric Fleury
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3738)


Multi-hop wireless networks (such as ad-hoc or sensor networks) consist of sets of mobile nodes without the support of a pre-existing fixed infrastructure. For the purpose of scalability, ad-hoc and sensor networks may both need to be organized into clusters and require some protocols to perform common global communication patterns and particularly for broadcasting. In a broadcasting task, a source node needs to send the same message to all the nodes in the network. Some desirable properties of a scalable broadcasting are energy and bandwidth efficiency, i.e., message retransmissions should be minimized. In this paper, we propose to take advantage of the characteristics of a previous clustered structure to extend it to an efficient and scalable broadcasting structure. In this way, we build only one structure for both operations (organizing and broadcasting) by applying a distributed clustering algorithm. Our broadcasting improve the number of retransmissions as compared to existing solutions.


multi-hop wireless networks self-organization broadcasting 


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Amis, A., Prakash, R., Vuong, T., Huynh, D.: Max-Min D-cluster formation in wireless ad hoc networks. In: Proceedings of the IEEE INFOCOM, Tel-Aviv, Isral. IEEE, Los Alamitos (2000)Google Scholar
  2. 2.
    Cartigny, J., Ingelrest, F., Simplot-Ryl, D.: RNG relay subset flooding protocol in mobile ad-hoc networks. In: IJFCS, pp. 253–265 (2003)Google Scholar
  3. 3.
    Chen, G., Garcia, F., Solano, J., Stojmenovic, I.: Connectivity-based k-hop clustering in wireless networks. In: HICSS 2002, Hawaii, USA (January 2002)Google Scholar
  4. 4.
    Chiang, C., Wu, H., Liu, W., Gerla, M.: Routing in clustered multihop, mobile wireless networks with fading channel. In: ICCS/ISPACS 1996, Singapore (November 1996)Google Scholar
  5. 5.
    Ephremides, A., Wieselthier, J., Baker, D.: A design concept for reliable mobile radio networks with frequency hoping signaling. In: IEEE, vol. 75, pp. 56–73 (1987)Google Scholar
  6. 6.
    Fernandess, Y., Malkhi, D.: k-clustering in wireless ad hoc networks. In: POMC, Toulouse, France (2002)Google Scholar
  7. 7.
    Lim, H., Kim, C.: Multicast tree construction and flooding in wireless ad hoc networks. In: ACM MSWiM Workshop at MobiCom 2000, Boston, MA, USA (August 2000)Google Scholar
  8. 8.
    Lin, C., Gerla, M.: Adaptive clustering for mobile wireless networks. IEEE JSAC 15(7), 1265–1275 (1997)Google Scholar
  9. 9.
    Mitton, N., Busson, A., Fleury, E.: Self-organization in large scale ad hoc networks. In: MED-HOC-NET 2004, Bodrum, Turkey (June 2004)Google Scholar
  10. 10.
    Mitton, N., Busson, A., Fleury, E.: Broadcast in self-organizing wireless multi-hop network. Research report RR-5487, INRIA (February 2005)Google Scholar
  11. 11.
    Mitton, N., Fleury, E., Guerin-Lassous, I., Tixeuil, S.: Self-stabilization in self-organized multihop wireless networks. In: WWAN 2005, Columbus, Ohio, USA (June 2005)Google Scholar
  12. 12.
    Nikaein, N., Labiod, H., Bonnet, C.: DDR-distributed dynamic routing algorithm for mobile ad hoc networks. In: MobiHoc, Boston, MA, USA, November 20 (2000)Google Scholar
  13. 13.
    Qayyum, A., Viennot, L., Laouiti, A.: Multipoint relaying: An efficient technique for flooding in mobile wireless networks. In: HICSS 2002, Hawaii, USA (January 2002)Google Scholar
  14. 14.
    Stojmenovic, I., Seddigh, M., Zunic, J.: Dominating sets and neighbor elimination-based broadcasting algortithms in wireless networks. IEEE TPDS 13(1) (January 2002)Google Scholar
  15. 15.
    Stojmenovic, I., Wu, J.: Broadcasting and activity scheduling in ad hoc networks. In: IEEE Mobile Ad Hoc Networking, pp. 205–229 (2004)Google Scholar
  16. 16.
    Wu, J., Li, H.: A dominating set based routing scheme in ad hoc wireless networks. Telecommunication Systems, 13–36 (2001)Google Scholar
  17. 17.
    Wu, J., Lou, W.: Forward node set based broadcast in clustered mobile ad hoc networks. Wireless Communications and Mobile Computing 3(2), 141–154 (2003)CrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Nathalie Mitton
    • 1
  • Eric Fleury
    • 1
  1. 1.INRIA/ARES – INSA de LyonVilleurbanne Cedex

Personalised recommendations