Minimizing broadcast latency and redundancy in ad hoc networks

Rajiv Gandhi, Arunesh Mishra, Srinivasan Parthasarathy

Research output: Contribution to journalArticlepeer-review

83 Scopus citations


Network wide broadcasting is a fundamental operation in ad hoc networks. In broadcasting, a source node sends a message to all the other nodes in the network. In this paper, we consider the problem of collision-free broadcasting in ad hoc networks. Our objective is to minimize the latency and the number of transmissions in the broadcast. We show that minimum latency broadcasting is NP-complete for ad hoc networks. We also present a simple distributed collision-free broadcasting algorithm for broadcasting a message. For networks with bounded node transmission ranges, our algorithm simultaneously guarantees that the latency and the number of transmissions are within O(1) times their respective optimal values. Our algorithm and analysis extend to the case when multiple messages are broadcast from multiple sources. Experimental studies indicate that our algorithms perform much better in practice than the analytical guarantees provided for the worst case.

Original languageEnglish (US)
Pages (from-to)840-851
Number of pages12
JournalIEEE/ACM Transactions on Networking
Issue number4
StatePublished - 2008

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


  • Ad Hoc networking
  • Approximation algorithms
  • Broadcast algorithms
  • Wireless scheduling


Dive into the research topics of 'Minimizing broadcast latency and redundancy in ad hoc networks'. Together they form a unique fingerprint.

Cite this