Minimizing broadcast latency and redundancy in ad hoc networks

Rajiv Gandhi, Srinivasan Parthasarathy, Arunesh Mishra

Research output: Contribution to conferencePaper

124 Citations (Scopus)

Abstract

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 wireless networks. Our objective is to minimize the latency and the number of retransmissions in the broadcast. We show that minimum latency broadcasting is NP-hard for ad hoc wireless networks. We also present a simple and 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 retransmissions are within O(1) times their respective optimal values. Our algorithm and analysis extends 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)
Pages222-232
Number of pages11
StatePublished - Nov 19 2003
EventMOBIHOC 2003: PROCEEDINGS OF The Fourth ACM International Symposium on Mobile Ad Hoc Networking and Computing - Annapolis, MD, United States
Duration: Jun 1 2003Jun 3 2003

Other

OtherMOBIHOC 2003: PROCEEDINGS OF The Fourth ACM International Symposium on Mobile Ad Hoc Networking and Computing
CountryUnited States
CityAnnapolis, MD
Period6/1/036/3/03

Fingerprint

Ad hoc networks
Broadcasting
Redundancy
Wireless ad hoc networks

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Keywords

  • Ad hoc networks
  • Approximation algorithms
  • Broadcasting
  • NP-hardness

Cite this

Gandhi, R., Parthasarathy, S., & Mishra, A. (2003). Minimizing broadcast latency and redundancy in ad hoc networks. 222-232. Paper presented at MOBIHOC 2003: PROCEEDINGS OF The Fourth ACM International Symposium on Mobile Ad Hoc Networking and Computing, Annapolis, MD, United States.
Gandhi, Rajiv ; Parthasarathy, Srinivasan ; Mishra, Arunesh. / Minimizing broadcast latency and redundancy in ad hoc networks. Paper presented at MOBIHOC 2003: PROCEEDINGS OF The Fourth ACM International Symposium on Mobile Ad Hoc Networking and Computing, Annapolis, MD, United States.11 p.
@conference{f35919c2852a4a78a25e9a5e9906635a,
title = "Minimizing broadcast latency and redundancy in ad hoc networks",
abstract = "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 wireless networks. Our objective is to minimize the latency and the number of retransmissions in the broadcast. We show that minimum latency broadcasting is NP-hard for ad hoc wireless networks. We also present a simple and 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 retransmissions are within O(1) times their respective optimal values. Our algorithm and analysis extends 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.",
keywords = "Ad hoc networks, Approximation algorithms, Broadcasting, NP-hardness",
author = "Rajiv Gandhi and Srinivasan Parthasarathy and Arunesh Mishra",
year = "2003",
month = "11",
day = "19",
language = "English (US)",
pages = "222--232",
note = "MOBIHOC 2003: PROCEEDINGS OF The Fourth ACM International Symposium on Mobile Ad Hoc Networking and Computing ; Conference date: 01-06-2003 Through 03-06-2003",

}

Gandhi, R, Parthasarathy, S & Mishra, A 2003, 'Minimizing broadcast latency and redundancy in ad hoc networks' Paper presented at MOBIHOC 2003: PROCEEDINGS OF The Fourth ACM International Symposium on Mobile Ad Hoc Networking and Computing, Annapolis, MD, United States, 6/1/03 - 6/3/03, pp. 222-232.

Minimizing broadcast latency and redundancy in ad hoc networks. / Gandhi, Rajiv; Parthasarathy, Srinivasan; Mishra, Arunesh.

2003. 222-232 Paper presented at MOBIHOC 2003: PROCEEDINGS OF The Fourth ACM International Symposium on Mobile Ad Hoc Networking and Computing, Annapolis, MD, United States.

Research output: Contribution to conferencePaper

TY - CONF

T1 - Minimizing broadcast latency and redundancy in ad hoc networks

AU - Gandhi, Rajiv

AU - Parthasarathy, Srinivasan

AU - Mishra, Arunesh

PY - 2003/11/19

Y1 - 2003/11/19

N2 - 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 wireless networks. Our objective is to minimize the latency and the number of retransmissions in the broadcast. We show that minimum latency broadcasting is NP-hard for ad hoc wireless networks. We also present a simple and 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 retransmissions are within O(1) times their respective optimal values. Our algorithm and analysis extends 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.

AB - 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 wireless networks. Our objective is to minimize the latency and the number of retransmissions in the broadcast. We show that minimum latency broadcasting is NP-hard for ad hoc wireless networks. We also present a simple and 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 retransmissions are within O(1) times their respective optimal values. Our algorithm and analysis extends 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.

KW - Ad hoc networks

KW - Approximation algorithms

KW - Broadcasting

KW - NP-hardness

UR - http://www.scopus.com/inward/record.url?scp=0242527322&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0242527322&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:0242527322

SP - 222

EP - 232

ER -

Gandhi R, Parthasarathy S, Mishra A. Minimizing broadcast latency and redundancy in ad hoc networks. 2003. Paper presented at MOBIHOC 2003: PROCEEDINGS OF The Fourth ACM International Symposium on Mobile Ad Hoc Networking and Computing, Annapolis, MD, United States.