Minimizing Broadcast Latency and Redundancy in Ad Hoc Networks

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 nu...

Full description

Saved in:
Bibliographic Details
Published in:IEEE/ACM transactions on networking 2008-08, Vol.16 (4), p.840-851
Main Authors: Gandhi, R., Mishra, A., Parthasarathy, S.
Format: Article
Language:English
Subjects:
Ad Hoc networking
Ad hoc networks
Algorithm design and analysis
Algorithms
Approximation algorithms
broadcast algorithms
Broadcasting
Delay
Mathematical analysis
Messages
Networks
Optimization
Performance analysis
Protocols
Redundancy
Routing
Scheduling algorithm
Wireless communication
wireless scheduling
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 re spective 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.
ISSN:1063-6692
1558-2566
DOI:10.1109/TNET.2007.905588